Can two friends, Alice and Bob, communicate in public (with eavesdroppers!)
and nevertheless come to agree on a secret only they share. We'll see that
this is possible through a procedure called Diffie-Hellman. So to analyze this,
I've divided the situation up into three regimes. In the middle here, I've got "the
room." That's where Alice and Bob are actually communicating. That's public
knowledge. Over here, I've got Alice's mind: that's just the stuff that Alice
knows. And over here I've got Bob's mind: that's just the stuff that Bob knows. So
Alice and Bob will communicate in the, in the public space, in the room. And Alice
and Bob will agree to start with the color yellow. Now Alice will pick a
secret color; her secret color will be blue. And Bob will pick a secret color;
his secret color will be red. Then Alice will mix the public color yellow with
her secret color blue in order to get green. And she'll announce that color
green to the room. Now Bob already came up with his secret color, red. He'll mix
the public color yellow with his secret color red in order to get orange. And
he'll reveal orange to the room. Now at this point what do people know: everybody
in the room knows about yellow, about green, about orange... but only Alice knows
her secret color blue. And only Bob knows his secret color red.
At this point Alice heard Bob say orange so Alice is gonna take what Bob said,
orange, and mix it in with her secret color, blue, in order to get a new secret
color, brown. that well only Alice knows but what's Bob gonna do? Bob heard Alice
say green and Bob will mix what Alice said, green, in with his secret color, red,
in order to also get brown. And at this point, Alice and Bob agree on a secret.
They both know the secret "brown." Nobody in the room knows about brown! Only Alice
and Bob know about brown. This is great. And really from a certain point of view,
it seems impossible that Alice and Bob were able to make this work. Right, Alice
and Bob are communicating publicly. They're not whispering to each other.
Everything they say is out in the open, and yet, even though
they're communicating publicly, at the end of their public conversation, Alice
and Bob end up having knowledge that only Alice and Bob have. Now we told this
story with paint and mixing colors. I'm going to recast this story with more
numbers. Okay so let's see that again. We're again going to start with the the
same structure. We've got the room where Alice and Bob are speaking publicly.
We've got Alice's mind: stuff that only Alice knows. And we've got Bob's mind:
stuff that only Bob knows. So you do the same kind of argument, but instead of
just with colors, we're gonna use numbers. So Alice and Bob agree on a number, 2,
and then Alice picks a random number; let's say it's 24, and Bob will pick his
own random number, 17, and crucially only Alice knows the number 24 and only Bob
knows the number 17. If we imagine that we've got a sort of mixing function M
which takes in two numbers and mixes them together somehow to produce a new
number. So here, the room, the public knowledge, was this number 2 that Alice
and Bob agreed on, and Alice had picked this random secret number 24. She'll mix
the public knowledge 2 with her secret number 24, and let's suppose that after
that mixing process is done, she gets the number 20. She'll announce that number 20
to the room. Bob's gonna do the same kind of game. He had already picked that
secret number 17 that only he knows. He'll mix it in with the public number
2 and maybe that mixing function in this case will produce the number 21.
He'll then take that number 21, and announce it to the room. Now Alice heard
Bob say 21, so Alice will take what Bob said, and mix it in with her originally
chosen secret number of 24. Let's say in this case that mixing process results in
the number 25. Bob will do the complimentary thing: Bob heard Alice say
20, and Bob will mix the number 20 with his originally chosen number of 17. He'll
also get 25. And at this moment Alice and Bob agree on the shared secret. They both
agree that their secret is 25, even though nobody in the room could deduce
that their shared number was 25. Well the key thing here is that if I mix with 24
and then with 17 I get the same thing as if I mixed with 17 and then with 24.
I really want something like this to hold in general. All right, if I mix with 𝑎 and
then with 𝑏 that should be the same thing as mixing with 𝑏 and then mixing
with 𝑎, and that's a crucial property. Alice is taking the number that Bob
revealed and mixing it with her secret number.
Bob's taking the number Alice revealed and mixing it with his secret number.
It's vitally important for them to both get the same number at the end. That
mixing 𝑎 and then 𝑏 is the same as mixing in 𝑏 and then 𝑎. But how do we
find a function 𝘔 with this property? Well here's an example. We could just
define our mixing function to be multiplication, and that's pretty good
because if I mixed with 𝑎 and then with 𝑏, well that's 2 times 𝑎 times 𝑏, which is
the same thing as 2 times 𝑏 times 𝑎, which means mixing with 𝑎 and then with
𝑏 is the same thing as mixing with 𝑏 and then with 𝑎. But actually this is a
terrible choice of mixing function! why is this just a bad choice? Well it's
because unmixing is possible! I mean, if if Alice picks her secret number 𝑎 and
then reveals the result of mixing 2 with 𝑎, reveals 𝑥 publicly to the room, then
when the people in the room hear 𝑥, they can just divide in order to recover 𝑎.
Right, one way to say this is that unmixing is possible, and you can't hide
a secret, say, by mixing together paint, if you can unmix the paint. We need a better
technique. So Alice and Bob will publicly agree on a prime number 𝑝 and a
generator 𝑔 then we'll define the mixing function 𝑀(𝑥,𝑦) as being 𝑥ʸ
reduced modulo 𝑝, and this choice of mixing function has the key property
that if we mix with 𝑎 and then with 𝑏, that's the same thing as mixing with 𝑏
and then with 𝑎, and the reason is because even if we're reducing mod 𝑝,
(𝑔ᵃ)ᵇ is the same thing as (𝑔ᵇ)ᵃ.
The key feature though is this last condition: that unlike the case of
multiplication, where I can undo multiplication just by dividing, here
to undo this exponentiation I would have to do a discrete logarithm. I'd have to
be able to take logs mod 𝑝, and there's no efficient method known for
doing that. One remaining question is which prime to agree on. Well here's a
prime number that Alice and Bob could agree on:
2¹⁰²⁴ − 2⁹⁶⁰ − 1 + 2⁶⁴ ( ⌊ 2⁸⁹⁴ π ⌋ + 129093 )
This is an officially provided prime number, uh, for
these purposes. I mean, if you look in some of the, well, the closest thing the
Internet has to governance documents, these RFC documents, you'll see this
prime number listed there. You might be wondering why π is playing a role in
this prime, this recommended prime number. Well, if you look at this prime number in,
let's say hexadecimal, most of the digits of this number are actually hexadecimal
digits of π, and this way, this is a nothing-up-my-(oh, I don't have sleeves)
but, it's a nothing-up-my-sleeve-number. Right, it's a number that's that's chosen
to emphasize the fact that the people choosing it didn't rig the number
somehow. Right they can't control the digits of π, so they've got a number
which is mostly digits they couldn't control. Even though this is a nothing-up-
my-sleeve-number, it's probably not great that lots and lots of people are using
this specific prime number for this algorithm. Take a look at this paper. Let me
read a little bit of this paper to you. "We estimate that even in the 1024-bit
case, the computations are plausible given nation-state resources. A small
number of fixed or standardized groups are used by millions of servers;
performing precomputation for a single 1024-bit group would allow passive
eavesdropping on 18% of popular HTTPS sites." So even if we can't do the
unmixing in general, even if there's no general efficient solution to the discrete
log problem, it's possible for nation-states, somebody with a lot of
resources, to do a ton of precomputation for a specific prime 𝑝, and consequently
massively speed up the discrete log problem for that
particular prime. And that's potentially a threat to our ability to communicate
secretly. There's lots more to say about crypto, and we're gonna get to more
crypto in this course, but I hope you already appreciate how just a little bit
of number theory can shine a tremendous amount of light on questions of how the
internet works and how we're able to communicate secretly online.