The Mathematics of Diffie-Hellman Key Exchange | Infinite Series

[@pbsinfiniteseries]

*We have an error in the animations at **0:20** and **1:24**!* (thanks to Olivier Halligon (+croco049) for pointing them out -- see his original comment here: kzbin.info/www/bejne/e4SzhZJpa9WIfMU&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's* public 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 Alice *digitally signing* the symmetric key with her own *private* key, i.e. *authenticating* that it came from her, since *anyone* in 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.

[@umbraemilitos]

Don't be afraid to demonstrate more explicit mathematics.

[@yamansanghavi]

Hey Gabe, Will you come back at Space-Time with Matt?

[@pbsinfiniteseries]

Short answer -- because in order to do that, we have to take the whole video down and upload it as a brand new video. If an error is major enough that it would constitute egregious misinformation, we would of course take it down and re-upload. But it's something that we feel we can correct with a comment, then we just pin a comment. It's a shame that KZbin got rid of Annotations, because that would be an even easier (and better) way to remedy the situation.

[@victorvalencia6466]

PBS Infinite Series How did i get hacked then??? Can you guys do an episode on how hackers get around encryption???

[@pbsinfiniteseries]

I mean, yeah, but I should have caught it. We go through a few cycles of review after the animator and sound editor put the final cut together before uploading, and our production timeline sometimes gets pretty tight. So when everyone's running around like a headless chicken, we might miss something. Still, I'm still pissed that it slipped by me. I'll try to me more careful going forward.

[@naftilos76]

Crystal-clear English, no silly jokes, precise descriptions and for god's name no camera trying to focus on a whiteboard. Excellent work.

[@ryanmcnamara9945]

This series was amazing, I'm so sad it's no longer being produced.

[@lovaaaa2451]

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

[@Melomathics]

lol, epic

[@Sam_on_YouTube]

There is a limited audience for that joke. But this is that audience.

[@pbsinfiniteseries]

Touché

[@brianhorne820]

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

[@deepjoshi356]

Computerphile also made video for it. This is what we want. More options for the same contents. Both are good.

[@seanspicer516]

ee.stanford.edu/~hellman/publications/24.pdf just wiki or google scholar stuff ur interested in.

[@shubhamshinde3593]

Gabe teaching diffie hellman!! Now, thats gotta be good...

[@Melomathics]

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.

[@theskycuber4213]

**elliptic curves intensifies**

[@AceHack00]

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.

[@ThomasJedi]

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.

[@BeCurieUs]

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!

[@nickgraham3665]

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

[@hristo.bogdanov]

Welcome back mate :) So nice to see you presenting videos again :)

[@mattiarosso84]

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

[@Rattiar]

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. ;)

[@rydohg]

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

[@ChurchOfThought]

Great video. I don't think you talk too fast at all. You are my favorite host of all Gabe!

[@ludvercz]

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!

[@screwhalunderhill885]

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

[@burningchrome8622]

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.

[@DanielFoland]

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

[@nickolasrudolph]

both you guys are doing a good job, keep it up

[@mattybowards7471]

rudy pornhub

[@bilthon]

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

[@Celastrous]

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

[@screwhalunderhill885]

The worst part is that he knows exactly how eager we are too see the next one.

[@ReaperUnreal]

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

[@KekusMagnus]

What I learned in Abstract Algebra class finally feels useful

[@SicilianDefence]

Gabe, the Mind blower!

[@baumulrich]

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!

[@ikarienator]

Gabe!

[@FrancoisBothaZA]

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

[@Kabitu1]

Gemoetric one-way functions.. oh goodness, you're gonna cover that elliptic curve nonsense I've never understood jack shit of, aren't you? Can't wait.

[@theHusky2490]

Kabitu1 KZbin already has it queued up next for me 😂

[@croco049]

Doesn't the animation at 0:20 show *signing* the red key, not *encrypting* it? In the animation we see Alice using her *private* key on the red key, and Bob using Alice's *public* key to get the red key back… but if you do it that way that means that Eve can also use Alice's public key to discover the red key! _(That protocol shown in the animation is to sign the message, not to encrypt it)_ Instead, to transmit the red key securely, Alice should encrypt the red key using *Bob's public key* so that only Bob can retrieve the encrypted red key and decrypt it using his own *private* key. (The same animation appears at 1:24 with the same mistake)

[@pbsinfiniteseries]

Yep, that was a gaffe on our part. I just saw it, too. Good eye, guys! We'll figure out to post a correction.

[@rkpetry]

'unfortunately' youtube discontinued their Annotation feature for fixing the video directly... (and they've never implemented a fast-redirect for upgrades)...

[@SKyrim190]

Ok, I have one question. How do you check/know computationally fast if a number is a generator in a cyclic group? From what I've understand both Alice and Bob must agree on a generator, but the definition of generators involves raising it to successive powers until it cycles through...which seems to be the same thing Eve has to do in order to solve a DLP...so unless there is a sneaky way of checking if a number is a generator, Alice and Bob will take a long time until they transmit a message

[@pirmelephant]

I think you can just universally agree on N and then find a generator of the group. Then N and g are always part of the protocoll and no checking needs to be done.

[@SKyrim190]

Frederik Huber That makes sense although it would limit the options to a kind of a database previously generated. I though those kind of things were created and checked "on the fly" as needed by Alice and Bob

[@pirmelephant]

I'm not an expert but I guess it would be way easier to compensate the loss of security by universally agreeing on N by choosing N even bigger (and looking for extra properties that are outlined in the wikipedia article - at least in the german one). This way you have the same security but can find your shared key faster. If I understand said wiki-article N and g seem to be a static part of the protocol.

[@RCSDominoToppling]

I was wondering the same thing. My (admittedly uneducated) guess is that there's a sneaky way of checking if a number is a generator. For instance, for any mod-N group that contains w numbers (has order w), any generator g will always have a period of length w. Therefore, g^w mod N = 1 mod N. So, let's say we suspect that some number x might be a generator. We could go and calculate x^w mod N and see if we get 1 mod N. If we do, then we know that either x is a generator, or x has a period whose length is a factor of w. But if w was a prime number, then we would know that x is a generator. So if you have a mod-N group that contains a prime number of elements, you can check to see which numbers are generators relatively easily. That's probably not how they really do it, but, regardless, it seems like there should be a way to feasibly verify if a number is a generator.

[@igncrdrgz]

I was wondering the exact same thing... We demand for an explanation! :)

[@Calm_Energy]

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.

[@zechordlord]

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.

[@TheyCallMeNewb]

Intense, but brief. Nice!

[@Ouvii]

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.

[@andlabs]

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...)

[@adrboe3027]

I actually got along with the math pretty ok, great job explaining!

[@epsiloncentauri6067]

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

[@michaelwestern11]

Ah a joker!

[@Convergant]

Do ECDH next please :) (Elliptic Curves Diffie Hellman)

[@bastawa]

Love those crypto episodes!!!

[@lucasgasparino6141]

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 KZbin on the subject, and it's a pretty interesting mathematical problem. Cheers!

[@Andrei-ds8qv]

That was veyyy clear!! Thanks!

[@petrusboniatus]

Just one day before my cibersecurity exam. Thanks

[@dman375]

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

[@thisaccountisdead9060]

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.

[@rodrigoqteixeira]

Is there any way to consistently generate a valid g from a random big N?

[@rodrigoqteixeira]

It is almost perfect. However, there is one single literally impossible to avoid problem. If eve does all the steps that Bob is suposed to do and all steps Alice is supposed to do, pretending to be the person each one wants to talk to. She can agree on a key with Alice and agree on another key with Bob without neither ever knowing. She can then proceed to send manually the messages each one wants to send eachother while having the power to read, change, remove, and even add fake messages.

[@seanspicer516]

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

[@paperstars9078]

what is this geometrical one way funciton? I need to know! I am super interested!

[@gravitycompels]

Heck yes its gabe! We miss you gabe.

[@mapi5032]

Great stuff. Thanks for this!

[@saarrrcamscms226]

Awesome episode

[@shaileshrana7165]

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

[@deslomator]

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.

Will you guys do an episode about El Gamal and/or DSA as well? :D

[@artstsym]

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)?

[@AshleyKitto]

Welcome back

[@jenspettersen7837]

Looking forward to elliptic curve Diffie-Hellman :)

[@sudarshanprajapati1339]

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

[@anselmschueler]

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

[@xwtek3505]

There is no next episode :(

[@shaylempert9994]

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

[@wilddogspam]

Khan academy seems to have a course specifically on it, but any algebra books that cover congruence should also cover the basics related to modular arithmetic. www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/what-is-modular-arithmetic

[@pbsinfiniteseries]

You can also watch the condensed intro of modular arithmetic that Kelsey did in this earlier video (to which I referred in this episode): kzbin.info/www/bejne/Z2O0ZIConZVmfc0

[@shaylempert9994]

PBS Infinite Series I've seen it already :) But it seems like there is so much more to the topic.

[@pbsinfiniteseries]

Oh, absolutely.

[@ismetpilev869]

Nice job! Next you should do elliptic curve cryptography :)

[@paulmann1289]

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?

[@52flyingbicycles]

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.

[@michaelgraff6978]

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.

[@KcKc-bh6lu]

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.

[@conoroneill8067]

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

[@screwhalunderhill885]

I'm more of a 1.25 guy

[@mattybowards7471]

Conor O'Neill i watch 3 at once on 4 different screens the fourth is pornhub

[@deepjoshi356]

Elliptical curve will be there in future series but please add Merkel puzzle also. Some history will also be good.

[@peerdox2275]

Can you please make a video explaining how to publish a research paper if one has an idea for a new one way function? or maybe make a video on a similar area related to research publishing?

[@ClarenceSimukanzye]

How did 625 turn into 9?

[@kasperskyroman]

Hoped for elipic Curve DH in generall Field :( Are there security holes if N is prime? in RSA it´s a produkt of 2 primes, just questing the reason.

[@TheMadRyaner]

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?

[@pbsinfiniteseries]

They must have gotten lost in the shuffle when we uploaded the vid. I'll add them when I get back to my computer later today. Thanks for the heads up.

[@ThingEngineer]

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

[@atrumluminarium]

Ooohhhh I bet the next cryptography vid is on Elliptic Curves

[@PsyKosh]

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?)

[@pbsinfiniteseries]

No, I didn't just mean previous videos. I need to update the description with some links to papers.

[@PsyKosh]

Thanks.

[@raindropdreams8]

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.

[@yohlane]

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

[@thetexasranger]

Next episode, Elliptic curves

[@paulthompson9668]

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

[@JohnMeinel]

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.

[@Sam_on_YouTube]

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.

[@AceHack00]

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.

[@austinnguyen9107]

yay group theory... finally!!!

[@shaylempert9994]

wonderful!

[@SuviTuuliAllan]

+1 for Rusty's face

[@jake1996able]

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

[@romajimamulo]

Jake K. No, they just do it with huge enough numbers that what they generate is a good key

[@jake1996able]

Romaji ok. but how then do you encrypt your actual messages with a single number?

[@romajimamulo]

Jake K. AES uses that huge number to tell how them how to scramble or unscramble their messages.

[@StefanGliga48]

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

[@docopoper]

So do asymmetric encryption algorithms exist currently that quantum computers can't mathematically break?

[@franzluggin398]

What do you mean with "mathematically"? If you mean "with an already-known algorithm that a quantum computer could use", then probably not. There are factoring algorithms, discrete logarithm and square root algorithms out there that would run in polynomial time on a quantum computer. If one were already found, however, it's one of those things that might not make it to the public for quite a while, e.g. if some goverment tried to keep it a secret, "just in case".

[@docopoper]

Huh, fair point. By mathematically I meant based on our understanding of the mathematics of quantum computers and how they let us rotate problems. Like I assume there must be one way functions that can't be overcome by what quantum computers let us do in principle. So I was wondering if any of the current algorithms have that feature. Though I guess it's a super hard question.

[@Ariana-dn4mm]

Elliptic curves!

[@muggyate]

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?

[@ianprado1488]

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

[@adfzr]

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.

[@Mo-kv9hg]

the next video will be about elliptic curves 😊

[@xxPYROxxJONESxx]

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

[@phizzhead53]

Can we talk about eliptic curve crypto

[@seabiscuitthechallenger6899]

With the four public numbers and some algebra the key can be uncovered 😈

[@seabiscuitthechallenger6899]

kzbin.info/www/bejne/oH3If4ton76oi9U