A method whereby two parties can generate a shared secret, using arithmetic in a residue class of naturals modulo a prime. Its security is based on factoring, which is probably as hard as the D__L__P, which is probably in N__P, which is probably very hard.
- http://www.apocalypse.org/pub/u/seven/diffie.html
- http://www.ietf.org/rfc/rfc2631.txt
- ftp://ftp.rsasecurity.com/pub/pkcs/ascii/pkcs-3.asc
Basically:
- Alice and Bob are going to generate a shared secret
- Everybody knows the prime, p, which defines a field of residue classes P, and the base (aka generator), g, which is in P
- Alice and Bob each generate random numbers in P; these are their secret keys, xA and xB
- Alice and Bob then compute public keys y, by y = (g ^ x) % p
- Note that x and y are an asymmetric key pair, with the encryption operation being m -> (m ^ x/y) % p. Is that right?
- Alice and Bob exchange their public keys, y.
- Alice and Bob can now compute a shared secret z, z = (yA ^ xB) % p = (yB ^ xA) % p
This works because (g ^ a) ^ b = (g ^ b) ^ a = g ^ (a . b) in a prime residue field.
Note that g is not necessarily any number; the R__F__C says:
$
RFC2631 2.2.1:
p is a large prime
q is a large prime
g = h^{(p-1)/q} mod p, where
h is any integer with 1 < h < p-1 such that h{(p-1)/q} mod p > 1
(g has order q mod p; i.e. g^q mod p = 1 if g!=1)
CategoryCryptography
CategorySoftware