Hal sez:
Quite a few misconceptions here, I'm afraid:
That'll teach me to write these things purely from memory without my references.
From: rcain@netcom.com (Robert Cain)
In the Diffie-Hellman exchange there is a well-known-prime, w, and a well-knwon-modulus, m.
w is supposed to be a "generator" of the group of integers mod m. It does not have to be prime. It is supposed to be such that the series w**0, w**1, w**2,...,w**m-1 does not repeat but goes through all the integers less than m. Testing for such w's is pretty easy if you know the factorization of m, involving a few arithmetic tests.
Yes, I remember that now about w but I believe that m should be prime.
For those interested that don't know I think it then proceeds as follows (don't have notes in front of me so please someone correct me if I'm misremembering it) where ** is the power or exponentiation operator and % is the modulus operator:
1) Bob generates a one time random prime, b, then computes
b does not have to be prime; it is a random number less than m.
Absolutely correct.
B = (w ** b) % m and sends B to Carol.
2) Carol generates a one time random prime, c, then computes
Likewise, c does not have to be prime; it is a random number less than m.
Again, correct.
C = (w ** c) % m and sends C to Bob.
3) Bob generates a session key:
Carol does this, not Bob.
K = (B ** c) % m
4) Carol generates a session key:
Bob does this, not Carol.
Oops, one more check of those equations and that would probabaly have jumped out at me. Sorry for swapping them (but as a newbie here I now know that you folks have your chops (a drumming term) when it comes to the math of this stuff.)
Now, the tutorial over :-), the question is; is there a "standard" well-known-prime, w, and a "standard" well-known-modulus, m, and if ^^^^^-- generator not, let's define one.
I don't think there is a need for this. The two sides need to agree on a pair but they could just pick it at the beginning. If everyone uses the same m,w it would help attackers of the scheme to focus their efforts on these numbers. I believe there was some discussion of using well-known numbers in the Digital Signature Standard (which is based on the same problem as DH) but I don't know what the resolution was.
Well, any two pair of boxes that are going to employ this have to use the same numbers obviously so they will be available to crunch any given exchange against and the only thing anyone can "focus their efforts" on is the exchange itself and I don't think knowing w amd m for a long time helps that problem any. I am just think that a pair should be selected, every implementation should use them to help with interoperability and they should be defined with simply stated, remembered and coded algorithms rather than just a long string of digits.
I suppose that PGP uses a well known pair but they are big and not easy to hand around without going through media (I think.)
PGP does not uses DH and has no well known numbers.
Ah, I assumed it did somewhere because Phil and I had a fair bit of email about this last year and he convinced me that D-H was the way to go because cracking one session gives no help toward breaking the next one.
If you do want well known numbers, I really think it will not be that bad just to put them into the program. Coming up with an algorithm to choose and test a generator from scratch is probably going to be larger and certainly going to be far slower than just hard-wiring the number in.
Maybe larger but I'll bet a lot easier to remember. :-) The slowness need not be a factor since a developer only need generate them once and save them in non-volatile ram which will be required for public keys anyway. If they just exist as numbers, we have to get them on some media that we can then use to transfer them into a device or type them in. It just seems easier if a simple algorithm could be specified. I'm not anal about this I just thought it an easier way and one that is more likely to insure interoperability. Peace, Bob -- Bob Cain rcain@netcom.com 408-354-8021 "I used to be different. But now I'm the same." --------------PGP 1.0 or 2.0 public key available on request.------------------