April 19, 2024
The Diffie-Hellman Key Exchange Protocol
It took a combination of smart thinking and number theory to solve the problem of key distribution. How can you pass the receiver of your ciphertext the key to decipher your message, without passing him, or her, an unsecured key? You might choose to use another key to secure the first key, but that would require another key, which in turn would require another key, and so on and so forth. In 1976 Diffie and Hellman provided a solution to the problem of exchanging keys over an insecure network.
Some students have expressed bewilderment as to how this process works. The Diffie-Hellman protocol was one method proposed for the exchange of one-time session keys for use with the Clipper chip. If you are interested, here is an explanation, but note that you do not have to know or understand anything at all about what follows for M150.
Here is how it works.
Alice and Bob wish to exchange information, but they know Eve is listening and can intercept any exchange they make. Alice and Bob will employ something called a one-way function (more on this later). This particular function is a modular exponential function and can be expressed mathematically as
gk mod p
Suffice to say that p is a very large prime number, k
and g are integers and g < p
(g is known as a generator and will need to satisfy certain other
conditions, but we can ignore those for the purpose of this discussion).
The function employs modular arithmetic. If you think that you know nothing
of modular arithmetic, think again. You employ it whenever converting times
on a clock, which is why it is sometimes called clock arithmetic. Someone
says "I'll be there at 14.00 hours." You immediately use modular
arithmetic to convert this to 2 o'clock.
The mathematical process used to calculate this result employs a finite set of numbers (twelve in this case) arranged in a loop from 1 to 12. By calculating the difference between 14 and 12, producing 2, one can quickly arrive at the time on a twelve hour clock. Alternatively, you may have divided 14 by 12 and calculated the remainder, thus giving the same result. There is obviously some kind of relationship between the integer numbers 2, 14 and 12.
It helps to realise, when dealing with modular arithmetic, that the "clock" can contain any number of integers that we choose. A consequence of this, for example, is that there exists a relationship between the numbers 5, 20 and 15 when employing a fifteen integer "clock".
Modular arithmetic is about congruence. The definition of congruence states:
If the difference between two integer numbers a and b
is divisible by an integer m so that the result is itself an
integer, we say that a and b are congruent modulo
m. An alternative is to say that a is congruent
to b modulo m, which is mathematically expressed
as
a ≡ b(mod m)
The symbol ≡ means "is congruent", the number
b is called the residue, or remainder, and m is
called the modulus. So, for the two examples of clock arithmetic mentioned
above we can write
2 ≡ 14 mod 12
and
5 ≡ 20 mod 15
The function that Alice and Bob are using takes matters a little further in that it is also exponential. By this I mean that a base number, in this case g, is being raised to some power, or exponent, which in this example is represented by k. As I have mentioned, this type of function has a special property. It is called one-way because, under certain conditions, it is impossible to determine k from any output produced by this function. This property made it supremely suitable for Diffie and Hellman's solution.
Alice and Bob not only agree to the use of the same function, but they also agree to use the same values of p and g. This information is exchanged and therefore Eve knows both the function and the values of p and g.
Alice now chooses, or rather her software generates, a random integer, which I will call a. Alice keeps this number private; she does not transmit it to Bob. Similarly Bob chooses his own private number b. They now substitute their private numbers into the function and each derive a number, which I will call na and nb respectively.
So Alice computes
na ≡ ga mod p
Bob computes
nb ≡ gb mod p
Alice and Bob exchange na and nb and consequently Eve also has access to these values.
Finally Alice computes
ka ≡ (nb)a mod p
and Bob computes
kb ≡ (na)b mod p
Now this is where the beauty of this solution becomes apparent, because firstly
(nb)a mod p = (na)b mod
p
∴ ka = kb
Alice and Bob can now use ka and kb
as a shared key to encrypt and exchange messages. (Proof of this can be found
here)
Secondly, since Eve does not have access to the numbers a and
b, remember that Alice and Bob have kept these private, she is
unable to compute a value for the key. The reason for this is that if p
is large enough (a 308 digit prime is considered sufficiently large) the two
modular functions
na ≡ ga mod p
nb ≡ gb mod p
will resist any attempt to solve for a and b, despite
knowing na , nb, g
, and p.
This is why the function is considered, under certain circumstances, to be one-way. So far as is known, nobody has been able to offer mathematical proof that such functions actually exist; it is only conjecture. Currently though, given a prime of sufficient size, it is computationally impossible to calculate the values of a and b, which is good enough for Alice and Bob!
Unfortunately the Diffie-Hellman key exchange protocol was later shown to be susceptible to a breach of security.
Eve intercepts the value na sent from Alice to Bob.
Eve substitutes this with her own value nx, which
she computes by using her own private value x
nx ≡ gx mod p
and sends nx to Bob, who now thinks that this is Alice's
public number. Bob sends his value nb to Alice and
once again Eve intercepts. She sends nx to Alice,
who thinks that this is Bob's public number.
Alice computes
ka ≡ (nx)a mod p
and Bob computes
kb ≡ (nx)b mod p
Eve can compute two keys, one, kxa, for deciphering , and possibly modifying, Alice's messages
(nx)a mod p = (na)x mod p
∴ ka = kxa
and another key, kxb, for deciphering, and possibly modifying, Bob's messages
(nx)b mod p = (nb)x mod p
∴ kb = kxb
You can't keep a good man down though, and Diffie was very good indeed. He subsequently corrected this flaw.
Alice and Bob are now required to authenticate themselves to each other by the use of digital certificates and signatures. Eve cannot forge these without Alice and Bob knowing. Once authentication of each of the parties is achieved, Alice and Bob can proceed as before.
Next page » Clipper
Previous page « Key Distribution
⇑ Up to top of page