Diffie-Hellman key exchange
Exchanging a secret paint color
One way to see that it is possible for two parties to agree on a secret without having to exchange it directly is to consider the paint analogy.
This illustration is taken from Wikipedia article on the Diffie- Hellman key exchange protocol.
The idea is the Alice and Bob want to agree on a paint color known only to them. It’s assumed that when paint is transported between them everyone knows the color of that paint. It’s also assumed that it is not possible to separate a paint into the two paints mixed together to create it.
In this diagram, the yellow paint is known to everyone. Alice and Bob each have their secret paints and each forms a mixture of that with the yellow paint. Eve sees these mixtures but can’t separate the yellow out and so can’t recover the secret paint colors. When Alice and Bob now mix their secret paint with the mixture sent by the other, they both have a paint that’s a combination of yellow, Alice’s secret red, and Bob’s secret turquoise. That is, they both end up with the brown paint, which is their shared secret.
Exchanging a secret integer
Now we’ll do this mathematically. Here is how Alice and Bob can securely exchange a key. The values in green indicate that they are public, those in red that they are private to one of the parties.
1. Alice selects 𝑝 = 31, 𝛼 = 3 and publishes them.
2. Alice selects 𝑥 = 8 and keeps it secret. Bob chooses 𝑦 =
12 and keeps it secret.
3. Alice sends 𝛼𝑥 𝑚𝑜𝑑 𝑝 = 38 𝑚𝑜𝑑 31 = 20. Bob
sends𝛼𝑦 𝑚𝑜𝑑𝑝=312 𝑚𝑜𝑑31=8.
4. Alice calculates (𝛼𝑦)𝑥 𝑚𝑜𝑑 𝑝 = 88 𝑚𝑜𝑑 31 = 16. Bob calculates (𝛼𝑥)𝑦 𝑚𝑜𝑑 𝑝 = 2012 𝑚𝑜𝑑 31 = 16.
Eve sees the values 𝛼𝑥 𝑚𝑜𝑑 𝑝 and 𝛼𝑦 𝑚𝑜𝑑 𝑝. We are relying on the not yet proven idea that modular exponentiation is hard to invert. If so, this is an example of a one-way function: Easy to calculate, difficult to reverse.
For best security, 𝛼 should be a primitive element modulo 𝑝. This means that the sequence 𝛼, 𝛼2, 𝛼3, … , 𝛼𝑝−1 takes on all of the values from 1 to 𝑝 − 1. This means that on average Eve would have to try at least half of the possible exponents to find𝛼𝑥 𝑚𝑜𝑑𝑝,𝛼𝑦 𝑚𝑜𝑑𝑝.
Referring to the paint example, the values 𝛼 and 𝑝 are the yellow paint. The values 𝑥 and 𝑦 are, respectively, Alice’s and Bob’s secret paint. The value 𝛼𝑥 𝑚𝑜𝑑 𝑝 is the paint Alice sends publicly to Bob and 𝛼𝑦𝑚𝑜𝑑 𝑝 is the paint Bob sends to Alice. The value 𝛼𝑥𝑦 𝑚𝑜𝑑 𝑝 is the shared secret color (the brown paint).
This shows that, surprisingly, it is possible to exchange secret messages without first sharing a secret key.
What we’re relying on here is that Eve cannot quickly compute discrete logarithms. That is, given 𝛼, 𝑝, 𝛼𝑥 𝑚𝑜𝑑 𝑝, Eve cannot quickly compute 𝑥.
One implementation issue to consider is how to compute a modular exponentiation efficiently.