# The Mathematics of Diffie-Hellman Key Exchange | Infinite Series

Skip to content
# The Mathematics of Diffie-Hellman Key Exchange | Infinite Series

##
100 thoughts on “The Mathematics of Diffie-Hellman Key Exchange | Infinite Series”

### Leave a Reply

Career In Forensic Science

Only a physicist could make a video on a math channel and feel like he has to excuse himself for talking about math

Nice job! Next you should do elliptic curve cryptography 🙂

thumbs down for the annoying sound effects.

Ya, I wish creators didn't shy away from getting "scooped" by other youtubers. Like you said, it is always nice to hear it twice cause a lot of times you just hear different things from different presenters, even if the material is nearly identical!

wonderful!

where can I learn the modular arithmetic relevant to this topic?

Look mommy! I'm famous!

I also totally agree. One of the many wonderful things about YT is that you guys aren't forced to compete for a time-slot like in old media, we can just have it all. It was still a funny coincidence though.

Great video, as usual. Keep it up!

We have an error in the animations at0:20and1:24!(thanks to Olivier Halligon (+croco049) for pointing them out — see his original comment here: https://www.youtube.com/watch?v=ESPT_36pUFc&lc=UgwUnHtCzE7xYWNaY7l4AaABAg).We intended the animation to show Alice using asymmetric (i.e. public key) encryption to encrypt the symmetric key and send it to Bob. To do that, Alice should have encrypted the key with

Bob'spublic key so that only Bob could decrypt it (with his private key). What this animation instead shows (accidentally, b/c we inserted the wrong animation and didn't catch it before uploading) is Alicedigitally signingthe symmetric key with her ownprivatekey, i.e.authenticatingthat it came from her, sinceanyonein the outside world (not just Bob) could decrypt it now using Alice's (and only Alice's) public key.Sorry about this! I'm really pissed at myself for not catching it before we uploaded. I'll do a better job of that in the future. Thanks for having eagle eyes and catching our mistakes. It's hugely helpful.

So to synthesize a key they both run this process a couple of times to get a series of numbers do they?

Oh boy….

Gabe, I don't know how do you do to make things so interesting … but keep going! (incl. pace and mathematical "gory" details ^^). Miss your hosting on PBS Space Time, tho.

I remember proving the exponentiation in cyclic groups thing in my abstract algebra class in university. Thanks for making me remember that.

GABE IS BACK!!!!! YAY!!!!!

I love the implicit support of cryptocurrencies. You guys are awesome

I was expecting something like this, but not because of Computerphile — instead, because of Art of the Problem's 2012 video on Diffie-Hellman, which manages to find a simple way of explaining the necessary modular arithmetic through an analogy to mixing colors. Also a good watch.

Of course, I do wonder what happens if both Alice and Bob choose the same number by accident, since there's no way to know until after they have already established communications. (I'm sure there's a way to find out, and modern protocols will just try again if this happens…)

Almost tuned out at the beginning, but then he started talking about gt and nt, then I was like: ah! Here's something I can work with. Then I stayed.

These videos are much better when you understand what's going… Nice episode.

The ending was so awkward.

A bit confusing; the public asymmetric key in the animation has a symmetric blade…

what if eve intercepts both party's DH key exchange process and generates a shared AES key with alice and bob so instead of alice and bob sharing a key with each other, alice and eve share a key and eve and bob share a key

this way if alice sends a message to bob, eve will be able to decrypt it but bob cant but eve can intercept the message, decypher it an pretend to be alice then re encrypts it again and send it off to bob.

there's no real way in DH to stop this since you are not able to identify that the message is actually coming from who the sender claims themselves to be which is what RSA offers with it's public and private key system. so unless there's a way to use DH with certainty that the sender is who they say they are then DH isn't really a possible alternative to RSA right?

“Decaf Gabe” HAHAHA FUCK

I encrypt my messages by exchanging corn muffin mix and mayonnaise keys: Jiffy-Hellman's.

The NSA can't do it computationally, but they instead pushed hard for many major security companies to adopt certain standards in their choice of keys that had certain relations to each other that allowed the NSA to crack them much faster. I don't know enough cryptography to get the details, but basically they knew a mathematical fact about certain keys because they specially prepared them in advance to have that relationship. If you didn't know they did that, you couldn't possibly figure it out, but if you did have the info then you could crack the security of anyone using that standard. And they used their power over things like government contracts to get that standard adopted as widely as possible.

So yeah, the NSA can't CONPUTATIONALLY crack RSA, but they cracked most RSAs years ago using their other tools in combination with clever math.

Is Diffie-Hellman a type of hash-based cryptography?

My only comment about pacing was that the new woman (sorry, I'm terrible with names) has a particularly high pitched voice which I find hard to follow at high speeds. Not an issue for you or even most female voices. That is not a criticism, just my experience. Her last video went slower, which was better for me.

Can't wait for the next episode, what a cliffhanger

Right at the end…

ARE YOU SURE ABOUT THAT?

Can we talk about eliptic curve crypto

Gabe! Good to see you're still working for the PBS YouTube channels.

Am I the only one that watches most Youtube videos at double speed (and therefore don't really have a problem with people talking quickly?)

It seems like every cryptographic algorithm inherently has to depend on the computational infeasibility of the solutions…I wonder why is that the only case?!?

Im still mad at this guy because of the tides video.

So now we have three hosts… what's happening here?

You mentioned that there would be sources for a more advanced approach to this in the description, but I don't see any. Did I misunderstand?

Glad to see Gabe doing maths now!

I made a video on DH with Prof. Vaudenay with a quite different (hopefully complementary) explanation: https://www.youtube.com/watch?v=kOlCU4not0s

i barely comment on YT but this needs to be said: this is the only channel where i enjoy the speed a lot. however it could be a bit faster.

If someone is interested by a small function (python) to show the cyles like at 3:51:

'''

def cycle(x, mod):

for i in range(1,mod):

print(str(x)+"^"+str(i)+"= "+str(math.pow(x,i))+" mod "+str(mod)+" = "+str(math.pow(x,i)%mod)+" mod "+str(mod))

'''

ex:

>>> cycle(3,5)

3^1= 3.0 mod 5 = 3.0 mod 5

3^2= 9.0 mod 5 = 4.0 mod 5

3^3= 27.0 mod 5 = 2.0 mod 5

3^4= 81.0 mod 5 = 1.0 mod 5

Welcome back mate 🙂 So nice to see you presenting videos again 🙂

How do Alice and Bob know they are communicating with each other to exchange/generate the keys in the first place and not a eves dropper?

Any hipsters using ECW key exchange? I'm working on transparent server-less automated opportunistic double-ratchet key exchange, (based on https://github.com/whispersystems/libsignal-protocol-javascript )

Some function based in geometry but useful to crypto?Could it be related to lattices?Hmm…

Wow… Listening fast… I watch all my youtube videos at x1.5 speed…. So I must be a fast listener. Down side is that if I ever meet you in person, I will be wondering "Why is he talking so slowly?"

I'd love some extra detail in videos

*elliptic curves intensifies*Will you guys do an episode about El Gamal and/or DSA as well? 😀

Hey, this may be a really stupid question, but it's not the first time I noticed this: You mentioned mathematical details being filled in by references mentioned below… but I don't see any links/mentions to any references in the description. Where should I be looking for these extras that the videos mention are "reference below" in general, since this isn't the first time I can't find any mentions/links/etc in description to references that the video says are "mentioned below" (I don't think you meant just the previous videos in the series?)

I came up with the following while watching the video, but it is too simple to be an original idea, so something must be wrong with it:

Alice and Bob have their own private keys for encryption schemes that commute. Alice encrypts a message and then sends it to Bob. Bob then encrypts the message further and sends it back to Alice. Since their encryption schemes commute, Alice can now decrypt the message and it will be as if only Bob had encrypted it in the first place. She does this and sends it once more to Bob, who decrypts it to get the original contents.

This would eliminate the need for trapdoor/"one-way" functions.

Of course this transaction would likely only be used to get a shared key in order to only pass along each message once.

aw shit gabe back in the house! ive missed since space time. your vids on GR was the first time it actually started to make sense to me. after the 5th or 6th watch through of the whole 4 part series. we cant all b PHDs. glad ur back, ur great.

I love the pacing. There are way too many videos (especially tutorials) on YouTube that take eons to get to the crux of the matter.

Next episode, Elliptic curves

Very nice Gabe! Seeing how you are also a physicist I bet a video on quantum cryptography would be within your realm of expertise and fun to watch.

There's an artifact in the green bubble at 1:07 / 1:06 -> +/- 3s

Amazing video as usual! Keep on going on cryptography! Gabe and Tai-Danae are amazing hosts: definitely on par with the great Kelsey!!!

WHAAAAAAAAAT?!?!!? didn't realise youleft spacetime for infinite

This is so freaking cool.

Also on the subject trying to understand someone speaking fast, or in some other manner that makes it hard to understand, there is a channel on youtube where I can't actually understand the guy if I haven't been watching him regularly; it takes me a few minutes to adjust. Imperial Dane is an interesting speaker.

A really good channel on introduction to cryptography https://www.youtube.com/user/christofpaar

It's treatment of ECC was really good

Super curious about one-way geometric functions! Can I 3D print it? 😀

I hope the geometric one isn't blockchain…

Intense, but brief. Nice!

What I learned in Abstract Algebra class finally feels useful

What I don't get in this process, is what prevents Eve from saying to Bob "I am Alice", saying to Alice "I am Bob", and just send it's own numer, as a man in the middle. If she has the power to listen on Bob and Alice, she should have the power, to stop the communication, and mess prevent them from knowing that anything happend.

I can use RSA to solve this problem, but if I use RSA, I can just use it to share my AES key, and not handle all this math.

Dat characterization of the cyclic totient groups tho

+1 for Rusty's face

13:18 A bigger plot twist at the end than Usual Suspects. Good show.

I think using curves is going to be in the next episode on encryption – so possibly this will tie into what Tai-Danae has been doing on geometry? That was just a guess though – I hadn't managed to decrypt Gabe's thoughts behind what he said at the end of this episode.

I miss videos with Kelsey

Elliptic curves!

hey dude, i was a fan back in the days when you ran spacetime (it's still great dont get me wrong) but im happy to see you found a new equally awesome gig! just wanted to say keep it up, like your style!

Could you give bounds on the number of computations needed to crack the algorithm? Petaflops are on their way in the public sphere, and I'm not sure what "really huge" means in terms of computation time, or how many flops I'd need to crack the password in say… an hour. Crypto seems to be less about "unbreakability" and more about making it more expensive to break than there are resources for, but those costs require quantification.

There is a much easier way for Eve to eavesdrop than solving the DLP. She can just slightly tamper with the key exchange achieving simultaneous double impersonation, better known as Man-in-the-Middle. If she knows about the Diffie-Hellman key exchange protocol then she can just have separate key exchanges with both Bob and Alice in where Alice thought she exchanged keys with Bob and Bob thought he exchanged keys with Alice but in reality, Eve exchanged her own keys with each of them respectively. She can then decrypt stuff from Bob and re-encrypt it for Alice and vice versa. The way we get around this today is signatures and even those could be forged without DNS and out of band certificate authorities already existing on phones, computers, devices, etc… Technologies such as bitcoin, blockchain, and Iota's tangle try to solve this in a different decentralized way by massively distributing your public keys to tons of different people "nodes" and therefore reducing the chance that someone could have been in the middle of all of those transactions.

Also would be great if you guys could go over Quaternions, Octonions, Sedenions, i.e. Cayley-Dickson constructions and how they relate to Clifford Algebras, Lie Groups, and Lie Algebra including good books to read up more on the subject. Thanks, love the show.

Love those crypto episodes!!!

miss this guy… he should come back to Space Time.. and he reminds of Joe gatto

This involved Number Theory. Can you do videos with Information Theory which mostly involves infinite computational power for the adversary? Because in few years when quantum computers overtake computational infeasibility will not matter.

Great stuff. Thanks for this!

Hey that's the dude from spacetime. Glad to see you here sir!

hi gabe

That vocal crackle is unbearable. Please, please adjust your mic setup.

Would quantum algorithms help with searching for the DLP? If so, that basically shoots at least the common methods to exchange symmetric keys, basically making them useless.

Do ECDH next please 🙂 (Elliptic Curves Diffie Hellman)

Woah dude. What a video. Loved the pace and that you go into the math a bit. Great job.

I prefer the fast pace

As for the comment on pacing… I actually watch most videos on 1.5x speed. You really can get used to it. And the glory of vods is that if you missed something, you can back it up and slow it back down.

As a more-computery guy, I really liked watching Computerphile's take on DH and then you guys'. They gave me the concepts and then you nailed down the nitty gritty. I thought the two shows were perfect complements. While I know you didn't actually plan it that way, I'm going to pretend you did and applaud your amazing accidental colab. 😉

Really nice video. I had to watch it many times (and rewatch Kelsey's one) to understand it. I'd still like to know why generators are the linchpin of DH (perhaps because they provide the biggest brute force search space?), and how to check that a number is a generator.

5:20 What is the purpose of saying "odd prime"? I don't think any primes are even. (except 2)

Great video here, I especially like your visuals! Just one tiny point you might want to consider making: RSA also uses modular math. I know you said you'll gloss over many details, but for new student to cryptography, they would benefit from knowing just how significantly important prime numbers are because modular arithmetic is used in BOTH rsa & dh for the key exchange portion of those protocols.

Ooohhhh I bet the next cryptography vid is on Elliptic Curves

It's your fault if i watch the GDC's and Ted's talk at 1.25x speed!

I really miss Kelsie.

Do generators always generate each member of the group exactly once before cycling? If so, this presumably requires starting over when both parties generate the same value for A/B (an unlikely occurrence at higher values, but still)?

Alice encrypts her message with her private key. She sends it to Bob. Instead of decrypting it, Bob encrypts it with his private key. He sends it back to Alice. Alice decrypts the message with her key. She sends it back to Bob. Bob decrypts it with his key, revealing the original message.

It takes 3x as long in sending, but I can wait 2 extra seconds to get a critical message knowing it’s safe.

I like the speed! Thanks man great video. To anyone saying he was going too fast, that's what the pause button is for.

I'm 7 months late for this, but youtube does have a 0.75 speed feature….

gotta say learning rsa the first (ish?) time i saw beauty in maths. god dam beautiful.

Can we know what we transmit? Like is there a way to know that 9 will be transmitted to both?

He said references for more details about Deffie-Hellman protocol are in description. I found none.

First, I love this channel! I've started with PBS space-time, but this infinite series is the one that strikes home for me! So, I know it's out of topic for this video, but could you please consider doing an episode on domain decomposition method and parallel solution of PDEs? There's no decent video on YouTube on the subject, and it's a pretty interesting mathematical problem.

Cheers!

the music and the boops are the worst

https://arxiv.org/pdf/1708.03521.pdf

All of cryptography methods known to man as of now are time-independent, hence cipher space is fixed thus it's popentially predictable. Same message and key will provide the same cipher no matter when you encrypt the messsge. That's Turing machine can crack it.