tag:blogger.com,1999:blog-3722233.post3523309889572389823..comments2024-03-02T02:08:38.816-06: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.Anonymousnoreply@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