Cryptology 1
Fall 2002

Diffie-Hellman Key exchange protocol

[ Home ] [ Up ] [ DH Attacks ] [ DH Efficiency/security ]

The first ever public key protocol was introduced by Diffie and Hellman. The security of the system is related to the difficulty of the Discrete Logarithm Problem.

Patent

The Diffie Hellman system works as follows: Two parties who wish to send encrypted messages to each other are going to agree on a secret symmetric encryption key by means of a public negotiation (i.e., open to any eavesdroppers). For the sake of exposition, assume that the parties are Alice and Bob. Once the key is negotiated, they will use it to encrypt messages.

The key negotiation:

Step 1: Alice and Bob publicly agree on a large prime number P as the encryption modulus.

Step 2: Alice and Bob publicly agree on a number Q < P for which the least x such that Q^x = 1 mod P is large. One may assume that Q is a primitive root of P.

Step 3: Alice secretly chooses a number, A, not revealed to Bob or anyone, and then publicly reveals

A* (= Q^A mod P)

to Bob.

Similarly, Bob secretly chooses a number, B, not revealed to Alice or anyone, and then publicly reveals the value

B* (= Q^B mod P)

to Alice.

Step 4: Alice and Bob each separately computes the common secret key, DHS.

Alice's computation: DHS = (B*)^A mod P.

Bob's computation: DHS = (A*)^B mod P.

Notice that even though an eavesdropper sees both A* and B*, the eavesdropper cannot compute DHS from this knowledge, unless the eavesdropper can first compute A or B -- i.e., the discrete logarithm of A* or B* to the base Q mod P.

The encryption of messages.

The encryption schema will be a simple "shielding" schema.

Now if Alice wants to send Bob a message, she first transforms it to a number, say M, by some standard agreed upon method. Then she proceeds as follows:

Compare M with P. If M>P, then chop M into a number of pieces M₁,...,M_k such that each is smaller than P, and after being labelled as to which piece it is, the labelled piece, which we still denote by an M_i for convenience, is still smaller than P.

Then Alice encrypts these pieces by the formula

E_i = M_i*DHS mod P.

Note that Alice is essentially using the secret number DHS to "shield" the message being sent from eavesdroppers.

The decryption of messages.

Since P is a prime number, we also know that gcd(DHS,P)=1, and thus the equation

DHS*x = 1 mod P

has a solution in N_P. Let this solution be denoted by UDHS ("unshielding for DHS").

When Bob receives E_i, Bob decrypts it by removing the shield DHS thus:

D_i = E_i*UDHS mod P.

Observe that for each i, D_i = M_i, and Bob can now recover the original message.

Intuitively, the prime number P acts as the container for the message, while the secret number DHS acts as a lock and the secret number UDHS acts as a key for unlocking the given lock.