About this video
Alice and Bob publicly agree on a prime modulus (17) and generator (3). Each picks a private random number (15 and 13), sends 3 to that power mod 17 publicly, then raises the other's public result to their own private number. Both get the same shared secret (10), because they computed 3 to the power of both private numbers with the exponents in a different order, while Eve is stuck on the discrete logarithm problem.
You'll be able to
- describe the steps of the Diffie-Hellman key exchange.
- explain why Alice and Bob end up with the same shared secret.
- explain why Eve cannot find the secret from the public numbers.
Key words
- key exchange
- A way for two people to agree on a shared secret key, even over a public channel.
- private number
- A random number each person keeps secret, like Alice's 15 and Bob's 13.
- public result
- The generator raised to a private number, mod the prime, which is sent openly.
- shared secret
- The number both Alice and Bob calculate (10 here) that Eve can't work out.
Transcript
- [Voiceover] Now, this is our solution. First, Alice and Bob agree publicly on a prime modulus and a generator, in this case, 17 and three. Then, Alice selects a private, random number, say 15, and calculates three to the power 15, mod 17, and sends this result publicly to Bob.
Then Bob selects his private, random number, say 13, and calculates three to the power 13, mod 17 and sends this result publicly to Alice. And now, the heart of the trick. Alice takes Bob's public result and raises it to the power of her private number to obtain the shared secret, which in this case is 10.
Bob takes Alice's public result and raises it to the power of his private number, resulting in the same shared secret. Notice they did the same calculation, though it may not look like it, at first. Consider Alice, the 12 she received from Bob was calculated as three to the power 13, mod 17.
So her calculation was the same as three to the power 13, to the power 15, mod 17. Now consider Bob, the six he received from Alice was calculated as three to the power 15, mod 17. So his calculation was the same as three to the power 15, to the power 13. Notice they did the same calculation with the exponents in a different order.
When you flip the exponent, the result doesn't change. So they both calculated three raised to the power of their private numbers. Without one of these private numbers, 15 or 13, Eve will not be able to find the solution. And this is how it's done. While Eve is stuck grinding away at the discrete logorithm problem, and with large enough numbers, we can say it's practically impossible for her to break the encryption in a reasonable amount of time.
This solves the key exchange problem. It can be used in conjunction with a pseudorandom generator to encrypt messages between people who have never met.
Video © Khan Academy, used under CC BY-NC-SA. Watch on Khan Academy. Puzzicle is not affiliated with Khan Academy.