Department of Mathematics
Boise State University
Mathematics 124
Fall 2004

Diffie-Helman Key Exchange.

[ Back ] [ Home ] [ Up ] [ Next ]

It sometimes happens that unless the parties to a communication do something extra to protect the confidentiality of their communication, the protocol permits others to view their communication. A typical solution to this problem is for the two parties to agree about a method of concealing the contents of their communication by means of a public negotiation. Diffie and Helman proposed a method which can also be used in the context of a given RSA crypto-system. Here is one such approach:

An RSA system with encryption modulus R is given. The parties, A and B, wish to communicate a piece of information M which was digitally signed by a third party, and carries only the third party's digital signature. Anyone with access to that third party's encryption exponent s can view the contents of M by computing M^s mod R. Unfortunately, the communicating parties do not have access to the factorization of R, and thus cannot create their own encryption exponents and corresponding decyption exponents relative to R.

It would of course be possible for them to create their own encryption exponents RA, and RB, larger than R, and to then create key-pairs s and t relative to these, and to publicize these to each other. Another solution (the Diffie-Helman key exchange method) would be to use the existing R as follows:

1. The two parties agree on a large number k< R such that gcd(k,R)=1.
2. Then A secretly chooses a number a, not revealed to anyone, and
3. B chooses a number b, not revealed to anyone.
4. A sends B the number k^a mod R, and B sends A the number k^b mod R.
5. A, upon receiving k^b mod R, raises this number to the power a mod R -- say the answer is U.
6. B, upon receiving k^a mod R, raises this number to the power b mod R -- the answer is also U.
7. Now they solve the equation U*x = 1 mod R. Due to the choice of k, this has a solution. Let V be this solution.
8. A "shields" M as follows: Shield = U*M mod R. Then A sends B the shielded version, Shield, of M. Observe that for an eavesdropper to obtain the contents, the eavesdropper needs to know U -- which is hard to compute because the eavesdropper must find both a and b to do this -- which amounts to being able to solve the discrete logarithm problem.
9. B "unshields" the number Shield as follows when B receives it: Compute V*Shield mod R. Note that since U*V = 1 mod R, this computation reveals M, and now B can use normal methods for handling M.

In the RSA-system, the security of the system is based on the difficulty of the factoring problem. For the Diffie-Hellman system, a different problem's difficulty underlies the security of the system: Given k and R and m, find x so that k^x mod R = m. This is known as the discrete logarithm problem.