When I first taught Diffie Helman I read the following
1) Alice and Bob agree on p a prime and g a generator
2) Alice picks a, sends g^a to Bob, Bob picks b, sends g^b to Alice
3) Alice computes (g^b)^a and Bob computes (g^a)^b so they both have g^{ab}
I knew how to find a prime- pick a number of length n (perhaps make sure the last digit is not even) and test for primality, if not then try again, you'll get one soon enough. I did not know how to find g. I had thought you first find p, and then given p you find g. I then figured out that you make actually pick p to be a safe prime, so q=(p-1)/2 is a prime, and then just pick random g and test them via computing g^2 and g^q: if neither is 1 then g is a generator. You will find a generator soon enough.
That was all fine. But how come my source didn't say how to find g.?You need to know that to run the algorithm. That was years ago. Then I wondered how common it is for an explanation to not say how to find g. So I Googled ``Diffie-Helman'' I only record those that had some technical content to them, and were not about other DH such as Elliptic Curves.
0) The Original DH paper Page 34: alpha is a fixed primitive element of GF(alpha). No mention of how to find either the prime q or the prim root alpha.
1) Wikiepdia: ... protocol uses the mult group of integers mod p, where p is a prime and g is a prim root mod p. NO mention of how they find p or g.
2) Wolfram's MathWorld: They agree on two prime numbers g and p, where p is large and g is a prim root mod p. In practice it is good to choose p such that (p-1)/2 is also prime. They mention (p-1)/2 but not for the reason I give. (There are algorithms for Discrete Log that do well if (p-1)/2 has many factors.)
3) Comparatech: Alice and Bob start out by deciding two numbers p and g. No mention of how to find p or g.
4) Searchsecurity Won't bother quoting, but more of the same, no mention of how to find p or g.
5) The Secret Security Wiki Alice and Bob agree on p and g.
6) Science Direct More of the same.
7) Notes from a UCLA Crypto Course YEAH! They say how to find g.
8) Brilliant (yes that really is the name of this site) Brilliant? Not brilliant enough to realize you need to say how to find p and g.
9) OpenSSL Hard to tell. Their intuitive explanation leaves it out, but they have details below and code that might have it.
I looked at a few more but it was the same story.
This is NOT a RANT or even a complaint, but its a question:
Why do so few expositions of DH mention how to find p,g? You really need to do that if you really want to DO DH.
Speculation
1) Some of the above are for the laymen and hence can not get into that. But some are not.
2) Some of them are for advanced audiences who would know how to do it. Even so, how to find the generator really needs to be mentioned.
3) Goldilocks: Some papers are for the layman who would not notice the gap, and some papers are for the expert who can fill in the gap themselves, so no paper in between. I do not believe that.
4) The oddest of the above is that the original paper did not say how to find g.
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.
ReplyDeleteThe choice of the prime though.... ¯\_(ツ)_/¯
-David
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).
ReplyDeleteThe 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.
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.
ReplyDeleteIf my post was about
ReplyDeleteGee, what IS a good source for how to find the generator in
DH then YES, I would have asked the esteemed Jon Katz.
However, my post was about
Gee, how come many sources, including the original, do not
include how to find the generator. Hence YES I should have
asked Jon Katz WHY many papers and online sources leave out
this crucial information. Which I will do, though the
answer `see Katz-Lindell book for a good explanation' is
worth knowing, though not what I am asking for.
bill g.
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.
ReplyDelete(Not sure if I should make this a direct apply to your comment or
Deletea reply to my reply or...)
THANKS- yes, that is better than what I had and worth knowing.
Yes, I said this in the post.
ReplyDeleteMy point was not `gee, how to do this'
My point was `why is this step left out'
You gave a randomized procedure that uses exponentiation with a large exponent. What I suggested was deterministic and involved only a squaring.
DeleteThis comment has been removed by the author.
DeleteThis is all speculation, but there could be several reasons:
ReplyDelete- In the original DH paper I don't think they cared much about implementation. The fact that a generator exists was enough for them.
- 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.
- 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.
- 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.