tag:blogger.com,1999:blog-3722233.post3523309889572389823..comments2021-07-26T10:31:15.102-05:00Comments on Computational Complexity: Presentations of Diffie-Helman leave out how to find gLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger10125tag:blogger.com,1999:blog-3722233.post-41075234620332274952020-06-19T09:19:00.965-05:002020-06-19T09:19:00.965-05:00(Not sure if I should make this a direct apply to ...(Not sure if I should make this a direct apply to your comment or<br />a reply to my reply or...)<br />THANKS- yes, that is better than what I had and worth knowing.<br /><br />GASARCHhttps://www.blogger.com/profile/03615736448441925334noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-37671639970993884962020-06-19T09:17:32.011-05:002020-06-19T09:17:32.011-05:00This comment has been removed by the author.GASARCHhttps://www.blogger.com/profile/03615736448441925334noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-54004642143642585902020-06-19T09:16:50.515-05:002020-06-19T09:16:50.515-05:00This is all speculation, but there could be severa...This is all speculation, but there could be several reasons:<br />- In the original DH paper I don't think they cared much about implementation. The fact that a generator exists was enough for them.<br /><br />- For much of the early work, I think as long as people understood that finding g can be done (say, in polynomial time), they weren't very concerned with how exactly it was done.<br /><br />- Finding p and g is somewhat tangential to the main point of these papers; it's not mentioned for the same reason that papers on RSA don't talk about how to implement modular arithmetic.<br /><br />- From a mathematical point of view, finding a generator g is pretty straightforward -- you can come up with the algorithm yourself after a semester of undergrad algebra. Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-3283388376889110682020-06-19T09:15:35.557-05:002020-06-19T09:15:35.557-05:00You gave a randomized procedure that uses exponent...You gave a randomized procedure that uses exponentiation with a large exponent. What I suggested was deterministic and involved only a squaring.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-46891600323834468532020-06-19T09:11:38.369-05:002020-06-19T09:11:38.369-05:00Yes, I said this in the post.
My point was not `ge...Yes, I said this in the post.<br />My point was not `gee, how to do this'<br />My point was `why is this step left out'<br /><br />GASARCHhttps://www.blogger.com/profile/03615736448441925334noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-48047996141474997752020-06-19T07:58:05.513-05:002020-06-19T07:58:05.513-05:00BTW, it is even easier to find a generator of Z*_p...BTW, it is even easier to find a generator of Z*_p when (p-1)/2 is prime: take any element of Z*_p other than the identity and square it.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-2236226758865915572020-06-18T23:50:08.699-05:002020-06-18T23:50:08.699-05:00If my post was about
Gee, what IS a good s...If my post was about<br /> Gee, what IS a good source for how to find the generator in<br /> DH then YES, I would have asked the esteemed Jon Katz.<br /><br />However, my post was about<br /> Gee, how come many sources, including the original, do not <br /> include how to find the generator. Hence YES I should have<br /> asked Jon Katz WHY many papers and online sources leave out<br /> this crucial information. Which I will do, though the <br /> answer `see Katz-Lindell book for a good explanation' is <br /> worth knowing, though not what I am asking for.<br />bill g.GASARCHhttps://www.blogger.com/profile/03615736448441925334noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-20003712367144129452020-06-18T21:27:31.694-05:002020-06-18T21:27:31.694-05:00The Katz-Lindell book not only discusses in detail...The Katz-Lindell book not only discusses in detail choosing p (which nowadays is not a safe prime) and g (which is trivial when using a prime-order group, as you should be when doing Diffie-Hellman), but even gives an algorithm for finding a generator in non-prime cyclic groups. I believe Katz was in your department. You should really talk to him.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-63201571406893462902020-06-17T20:39:08.844-05:002020-06-17T20:39:08.844-05:00I'm kind of sad that page was your first intro...I'm kind of sad that page was your first introduction to Brilliant.org! Wiki content like that is mostly older user-generated stuff, and it definitely falls into the trap of not really having a clear idea of who its audience actually is (in that sense, I think your speculations 1-3 are perhaps too generous, in that they apply that these things were written with a clear audience in mind).<br /><br />The core of our site nowadays is our interactive courses, and we're still trying to figure out what to do with the legacy material. We've got a lot of foundational computer science material to build up first, but once we get to the point we're exploring cryptography and key exchange, we'll definitely need to get this right.Rob Simmonshttps://www.blogger.com/profile/10418846191120040668noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-49058018996215440992020-06-15T10:46:15.492-05:002020-06-15T10:46:15.492-05:00Hi Bill, I think they assume one can efficiently f...Hi Bill, I think they assume one can efficiently find a primitive element; practically speaking, this is true. But the choice of the actual primitive element does not affect security, since one can reduce breaking DH with a given alpha to breaking it with any other alpha.<br /><br />The choice of the prime though.... ¯\_(ツ)_/¯<br /><br />-DavidDavid Cashhttps://www.blogger.com/profile/11278459496685269110noreply@blogger.com