[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Some stuff about Diffie-Hellman (and more :-)
Quite a few misconceptions here, I'm afraid:
From: [email protected] (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.
> 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.
> 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.
> 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.
> K = (C ** b) % m
>[...]
> 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.
> 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.
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.
Hal