# Diffie-hellman key exchange | Journey into cryptography | Computer Science | Khan Academy

– [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.

Amazing video!!

What's keeping an intercepting hacker to get the public key and simply act as a negotiating peer?

Thanks

So what happens in the following instance when eve controls network traffic? (aka you connected to a bogus wifi hotspot)

Alice chooses 15

Bob chooses 13

Alice sends 6 ( which was the result of (3^15)mod17 )

Bob sends 12 ( which was the result of (3^13)mod17 )

but eve replaces Alice's 6 and Bob's 12 with some number, lets say 4

Bob and eve are now "out of sync" because they each believe the other sent them something they did not.

they will each calculate the (not so)shared private key to be the following.

Alice: (12^15)mod17 = 8

Bob: (6^13)mod17= 10

for each consecutive message, eve can decipher , re-encrypt, and forward it with the correct key based on who sent it.

if a message comes from Alice it is decoded with 8, read by eve, encoded with 10, and sent on its way to Bob.

if a message comes from Bob, it is decoded with 10, read by eve, encoded with 8 and sent on its way to Alice.

neither Alice nor bob know that their conversation has been compromised, and eve can fully decrypt everything they say to each other.

Where is your God now? ;D

can someone explain why the initial modulus and the generator are prime?

Excellent!

Great video! Noticed a couple of mistakes though. In 1:18 it falsely shows 3^(13^15) mod 17. It should be (3^13)^15 mod 17 = 3^(13*15) mod 17 = 3^(15*13) mod 17 = (3^15)^13 mod 17.

can i know what software is this?

Good explanation of Diffie-Hellman formula – http://security.stackexchange.com/a/45971/126789

That background music creeps me out…

Beautiful

Really good explained!!! Thanks!

'Art of the problem' v=3QnD2c4Xovk He is, as far as I know the owner of this material. You have hereby been reported to 'Art of the problem.'

Would be nice to talk about finite fields, and Galois field.

Here is one way for eve to hack it, he can pretend to be Bob and send Alice a message sighed by her secret number, in this example, alice does not have a way to identify the coming message is signed by Bob or Even, if she was tricked it was Bob and signed with her secrete number and send to public, eve can then use her secrete number to crack the information, while bob can not.

At 1:53; Eve can only get 3 as 12^6 mod 17 or get 13 as 6^12 mod 17. We know that 13 – 3 = 10, and 10 is the shared secret. Is this just a coincidence?

Thanks. Perfectly explained in 2mins.

Khan Academy is the one. Teaches this better than anybody

I'm having a hard time understanding part of this, but then again I am not very familiar with the ideas themselves. If A and B publicly agree to the formula, then wouldn't their private number, and thus the ciphertext itself, be vulnerable since the attacker knows both the equation and the result of the variable that is the private number?

If I am correct on this point then does the security come from the fact that very big numbers are used? I just looked up that part and it seems that these problems are harder to work backwards than they are forwards.

With that said however, my next question regards the vulnerability of the device doing the actual calculations. There must be special software to manage the calculations and do the other things necessary since it cannot be done by hand, and therefore the actual encryption may not be vulnerable but the software itself could be right? And software vulnerabilities seem much easier than trying to break encryption in general. And does this hold true for public-key cryptography in general?

The last thing I wanted to touch upon is the fact that it seems dangerous to base the cipher on the difficulty in working an equation backwards on the computer's part, because computing power is increasing at a relatively steady rate. If quantum computers ever reach the point of being more like the personal computers of today, it is hard to imagine that, eventually, such algorithms will remain secure. I suppose that there could be multiple possible solutions in some cases, but this should not be a problem for figuring out the plaintext. If that day ever comes, are there other practical ways that provide message security? I know that the one-time pad system is quite inefficient and harder to implement in a digital manner, while by hand it is relatively easy, and thus it is hard to imagine this system ever gaining popularity despite its perfect encryption with proper use.

Then there is the fact that if there needs to be a secure channel to exchange a secret key or password, then why not just transfer the message via that secure channel?

excellent calculations. wow 👌

Would you know how to implement this into Python code?