Diffie-Hellman Key Exchange: How to Share a Secret

How can two computers share a piece of secret information without anyone else knowing? Diffie-Hellman key exchange is one of the core algorithms in cryptography for solving this problem. In this video, we build an intuition for how the algorithm works and why it's secure.
***
Spanning Tree is an educational video series about computer science and mathematics. See more at spanningtree.me
To be notified when a new video is released, sign up for the Spanning Tree mailing list at spanningtree.s...
You can support the Spanning Tree channel at ko-fi.com/span...
Spanning Tree is created by Brian Yu. brianyu.me/
Email me at [e-mail] to suggest a future topic.

[@epicdude1817]

My favourite thing about this channel is that they take seemingly complex algorithms and break it down so that it’s easy to understand!

[@hampus23]

💯

[@4pmvim]

And with cute renditions of the code at that!

[@c2vi_dev]

yup, absolutely the best thing ever!!!

[@vinniepeterss]

yep😮

[@NibbyBanana]

The problem with DH on its own is that there is no way to verify the calculated public parameters. So an attacker can sit in the middle and perform the handshake with both parties, generate a secret key and maintain the session. The attack decrypts the data from party A, is able to look at it and store it, then encrypt it to party B and vice versa. It does need to be an active attack, because otherwise there would be no way to retrieve the secret key. So you still need PKI for making sure that the public parameters you receive are from the correct party.

[@M_1024]

Is there a way to counter this?

[@NibbyBanana]

@@M_1024 Yes. You use certificates on the server side, so you have a means to send the public parameters to the server and back safely. This uses asymmetric encryption, which is a lot slower, so it's only used for the handshake. And if the server later got hacked and the RSA keys are compromised, you still cannot decrypt sessions, because DH achieves perfect forward secrecy. The signing is only neccesary to combat an active attack and verifying the public parameters, otherwise DH is perfect.

[@loganhodgsn]

The other part of security: authentication!

[@M_1024]

@@NibbyBanana This only works if you can be sure that some communication is with the right person. For example lets say that Alice tries to verify that Bob is really Bob. If she Has Bobs public verification key, she can do this, but first she has to get that key, which in practice is easy, but in theory could be impossible

[@NibbyBanana]

@@M_1024 Yes, that's the entire point of the certificates, and why you'd need PKI. To make sure the public paramters are from the right person.

[@marvinwaleed]

I learned about the DH key exchange back in University and even got the test questions correct without ever really understanding it. This video was fabulous - because NOW I understand. Insanely well done!

[@bertik2326]

Wow, this is the second time you have dropped a video with a theme I'm currently learning for an exam in a few days.

[@marekkamyk5518]

Good luck!!

[@mufaddaldiwan8555]

I think one thing you forgot to mention is why both would get the same key when raising it to their secret number. Operation by person with secret number c = (A^b mod M)^c --- (A^b mod M is what he received from other person) = (A^b)^c mod M --- (property of modular arithmetic) -> 1 = (A^bc) mod M --- (exponent property) = (A^c)^b mod M --- (multiplication is associative) = (A^c mod M) ^ b --- same as eq. 1 = The operation that person with secret number b would do This implies both of them end up with the same output which is the key

[@mufaddaldiwan8555]

There is a flaw in this as attacker can become a mediator between two communicating parties. Intercepts communication Creates shared key k1 with A and k2 with B Both A and B think they are communicating well but a mediator attacker sits in middle and reads and manipulates messages xD

[@Knirin]

@@mufaddaldiwan8555 Thanks for going over a basic version of the proof for why both parties get the same result. Diffie Helman gives you secrecy but not authentication . We use other means to add authentication to the chain.

[@unvergebeneid]

Diffie-Hellman is one of those problems where you could naively swear that it's impossible to solve. And yet!

[@kevinscales]

Yeah, the trick is to notice that the problem isn't to find an irreversible operation, that is impossible (when you know the operation and the result nothing can prevent you from, in the worst case, trying every number as input until you find one that gives you the same result), you can make reversing it prohibitively expensive, and that is all you actually need making the problem not as impossible as you initially frame it.

[@kevinscales]

As is typical, actually understanding a problem is the hard part of solving a problem.

[@unvergebeneid]

@@kevinscales Did you read this in a fortune cookie? I mean, you could always define "understanding" in such a way for this sentence to be true but then it's not really a useful statement, is it? Understanding a^n + b^n = c^n is not all that difficult. Understanding it deeply enough to solve it clearly is. So the word "understanding" is doing _a lot_ of heavy lifting here.

[@mtranchi]

That red robot looks scary.

[@k-vn-7]

Gotta stay alert. Red Guy out there lurkin'.

[@mtranchi]

@@k-vn-7 cross-hairs on him

[@samueltaylor4989]

It’s the eyes, you know people who squint or have eyebrows turned down are evil.

[@CyberGyat-im4bp]

sus

[@k-vn-7]

@@CyberGyat-im4bp 😆

[@ImNetheN]

a more efficient algorithm to find x^p: the main idea is that a^b * a^b = a^(2 * b) so you can double the exponent in 1 operation instead of increasing it by one. the code of the function would look something like this: function pow(x, p) if (p == 1) return x if (p is even) { int y = pow(x, p / 2); return y * y; } if (p is odd) return x * pow(x, p -1) and you can just take the mod on every step

[@WackoMcGoose]

There's another method I like that has a great analogy, but requires a type of cryptography that you can _swap the steps of and still get the same result_ (think A XOR B XOR C == A XOR C XOR B). The analogy is, Alice comes up with a secret, puts it in a box with Padlock A (only she has A's key) and mails it to Bob, who _puts his own Padlock B on it_ and mails it back (the contents are now "double encrypted"). Alice now unlocks Padlock A so the box only has Padlock B on it, and mails it back again to Bob, who unlocks his own padlock and retrieves the secret, that they then share for regular communication. They never unlocked each other's locks, and the box was never in flight without at least one lock on it.

[@thesquatchdoctor3356]

Been wondering this for 15 years

[@dakotaboy80]

This concept has been explained to me several times in classroom settings, but this video is the first time it actually made sense to me.

[@theAstarrr]

I recommend Khan Academy's series on it as well

[@programing_with_santunu]

"You are the greatest teacher I have ever seen." 😊👍

[@foobargorch]

worth mentioning that in more modern cryptography the same idea is used on elliptic curves, but the cool thing is this is a pretty black box approach, the higher level key agreement protocol doesn't care about the underlying mathematical structure used so long as it's an Abelian group where reversing the group operation is hard and it turns out that defining an addition operation on the solutions to elliptic curve equations gives a very good tradeoff between efficiency and (presumed) hardness.

[@RoyNisimov]

Great vid as always! I got into cryptography because of your video about AES! I think a video about Shamir's Secret Sharing could be interesting too.

[@The_Pariah]

You are an absolute nerd. And that's **exactly** why I keep watching your videos. Keep up the fantastic work.

[@tanvirhasanmonir1627]

Thank you so much. Very easy to understand even though the topic is complex.

[@69k_gold]

Omg, it was this simple! Computerphile did a very poor job in this concept. I love your videos and those cute robots man, you know your stuff really well

[@JariNestel]

I need to disagree with this: 1. The Water Color video is just for the non math person: kzbin.info/www/bejne/hJ6want3Z7KEfas 2. The Math behind explains deeper and why exponentiation is safe: kzbin.info/www/bejne/j5vVl6CVpLeCZtk While this video is a mix between, but completely fails to explain why exponentiation is safe, if the communicating parties used the exponentiation iteratively as shown in this video, brute forcing it would be as hard as encrypting it. While multiplying previous powers gives a great benefit to efficiency, reducing your cost to from linear to logarithmic, assuming you know your target exponent. And if you assume the person watching this video knows how exponentiation can be sped up, there would be no need to watch this video in the first place, cause that's literally everything going on.

[@69k_gold]

​@@JariNesteloh thanks, I totally missed the second video you mentioned

[@faker7622]

Thank you very much to make such simple explenations so people like me can understand it much easier and your animation help a lots. I hope you will make more videos like this for such complicated topic

[@theAstarrr]

Great video! Second only to Khan Academy's explanation - they did a really good job on their series. But I'd recommend either one to someone interested in cryptography, security, and that stuff.

[@fouler3606]

Thank you for the amazing educational content and adorable animations! it helps me as a student studying computer science in university I find your videos a nice and small research video on topics that I don't always encounter in the syllabus so thank you for everything :)

[@Meghana_Nallamilli]

Just when I needed it! I’m working on understanding AES-GCM encryption and ECDH key exchange for an internship

[@Katchi_]

Or.... or.... you could read the fing man.

[@Meghana_Nallamilli]

@@Katchi_ huh??

[@sobevj]

It's very concise and you learn a lot in a short time, and if you want to learn the source code, it'll be easier!

[@Guilhem34]

This protocol is used in SSH, a widely used cryptographic software. However you are susceptible to MITM at first generation. This is why checking the public key is important.

[@Valo_iO]

Well explained, great video!

[@saksi_mata]

I am subscribed just because your animation is so cute and the explanation about the problem at hand was really spot on.

[@kebien6020]

One reason for wanting to do this instead of Asymmetric key cryptography is that Symmetric tends to be much more efficient for encription and decription. If you want ALL traffic to be encrypted, it better have a low overhead over sending plaintext.

[@SuperLlama88888]

Wow, straightforward and clear explanation! Thank you for this video!

[@Hi2uGaming]

I have an exam on this topic tomorrow and you uploaded this today. Right time ! lucid explanation thanks

[@Katchi_]

Liar.

[@rhysbaker2595]

Oh hey, this amazing channel that I love uploaded! :D

[@tacuacito6416]

I just discovered your channel! Amazing video! 10/10 But what would happen if red guy: 1. Generated his own secret and modular exponent. 2. Intercepted or stopped green's modular exponent from reaching blue. 3. Sent his own modular exponent to blue, pretending it is from green. Wouldn't he be able to read blue's messages now?

[@thefrub]

This is a great explanation! I wish I had this when I was taking my cryptography class last year

[@mauisstepsis5524]

I love your content. This is the best intro to DH key exchange

[@lostvayne871]

That red guy is a masterpiece!!!

[@MOOBBreezy]

What a great cryptography lesson! Thank you!

[@AjinGixtas]

Cool vid :)

[@foobarf8766]

You touched on the discrete log problem, so compression functions and their special case of one way hashing next please!

[@brianarsuaga5008]

Huh, I knew and studied this, technically, but this made it less "black magic" where the math was concerned. Thanks!

[@ChristopherOBrienPSU]

Best explanation of DH that I've ever seen

[@lucas-pcs]

Thanks for sharing !! Those animations makes so easy to understand the algorithm

[@ShNazem]

You explain very understandable thank you.

[@CultKosmosa]

thank you, I have been implementing d-h exchange when communicating with telegram server but this video gave me a much better understanding than reading code or text, I guess I am a visual learner

[@jakob5481]

I feel like this would also be a good moment to make a video about the euler phi function since it massively simplifies such calculations

[@tirana.1887]

Best explanation out there! Came here after watching several videos on the matter. This was the best by far. Thanks!

[@StefanReich]

Diffie-Hellman relies on the same principle (modular exponentiation) that RSA uses to allow asymmetric encryption. Incredible inventions if you think about it

[@QualityDoggo]

iirc they're often used together -- key exchange versus encryption

[@jameslovering9158]

Thank you, that was easy to follow !

[@arpitkumar4525]

Wow! First time I saw the beauty in Maths

[@ArcherNX1701]

Thanks for making the explanation so simple. Would you make another vid that explians how quantum computing can break this? And any solution post-quantum?

[@deschia_]

Found your channel from this video. You just earned a sub. Great content.

[@lisakanifer5081]

Small nitpick near the end. TL;DR: You don't have to use primitive roots for your base. It is not sufficient to choose any prime number modulus, as an attacker can use something called the Pohlig-Hellman algorithm if one less than the prime only has small prime factors. Bad prime example: 306557831 is a prime, but 306557831 - 1 = 306557830 = 2 * 5 * 53 * 67 * 89 * 97, and this makes it weak. Good prime example: 489678227 is a prime, and 489678227 - 1 = 489678226 = 2 * 244839113, and this makes it strong. In fact, these primes are called safe primes. Now suppose you've chosen the safe prime modulus in the example. If you avoid a base of 1, 0, or -1, you're guaranteed to go through at least 244839113 values, so pretty much any base works. Pohlig-Hellman makes sure having 489678226 values doesn't make it harder, so there's no need to find a primitive root.

[@Mahm00dM0hanad]

Well explained, thanks a lot

[@cdvgter]

This is explained so well!

[@Anythiny]

its always fun to watch ur explaination

[@clementdato6328]

The fact that I didn’t turn on all notifications for this channel is mind-blowing

[@Krosis_]

Truly mind blowing

[@novmoon5724]

Congratulations on your upcoming wedding! The lady is so beautiful and wonderful, she would be one of the great breadwinners for the family! congratulate!

[@kacper7516]

One of the best explanation

[@ricardopassos1180]

It ain't much, but it's my way of saying thanks for your work

[@roborogue_]

great video!

[@cee2615]

I have no interest in the content of the videos, I just absolutely love the little guys in the video and have to watch because of their cuteness … too cute

[@benjaminkpaul]

brian yu is a genius😊😅

[@Stvk]

I love video like this, can you do block cipher mode of operation (especially XTS), RSA, ECC and Lattice cryptography?

[@callisoncaffrey]

Good explanation gets a like.

[@tanmaybora359]

You are the best!

[@fastrobreetus]

Great video!

[@zudwa9280]

Dustin Hoffman seems to be not only a good actor but a pretty smart guy too.

[@pjn2001]

Might be a bit simplistic but would like to request a video on hole punching (networking). Maybe if combined with some other networking concept it could be a bit more viable. Thank you

[@arcanogameplays]

Best explanation out there

[@official_noself]

Could you please explain how can you prevent if red person takes both of the b mod m shared publicly and gives other parties his own version of secret key calculation. Therefore both parties think they agreed on a key but in fact agreed on red person’s keys. Throughout the whole process red person can open the message and encrypt it again to send to receiver as it is coming from other party.

[@g0fher]

Can you talk abount quantum key distribution in next videos? Something like bb84, there are a lot of cool things to show in that algorithm.

[@tomcruise3003]

All of this just to say good morning!? I'd go back to bed at that point

[@Fakyp]

Good video, but it still doesnt solve the question you asked in the old video "How to Send a Secret Message" about MITM

[@QualityDoggo]

Yes. You need to have some way to secure/verify part of at least one communication -- this could be done with public/private keys which are trusted and setup out of band. The good part is you can then continue the conversation with encryption

[@ashb2483]

Great vid!

[@eyobsolomon4663]

Really, thank you so much!

[@annantsharma91]

Keep up the good work, loved it ❤

[@andreujuanc]

Brilliant! thanks for such good video

[@TNewton001]

Thanks!

[@VerifyBot]

This is a great video. This topic is so important yet I haven't found to many great simple to understand resources. Thanks a lot and keep uploading! :)

[@pbezunartea]

Great video, thanks!

[@hvnterblack]

good material

[@melonberry6771]

I like your content, please make more

[@timleferink]

Nice video. Think you can greatly improve audio with some sound deadening 😁

[@guoard]

Great job!

[@mandolinic]

In practice, how many bits should the number base and the modulus be?

[@cloverberry721]

Is this method better and/or more common than using asymmetric encryption to establish a symmetric key?

[@devr4j]

thanks it was helpful

[@Cosmo-ai]

The math just hurts my head. I understand, but at 7:00 I just have a hard time visualizing how you can both end up with the same number after taking answer to exponents of secret number

[@Freeethink]

Instead of calculating for example 3^(5) mod 19 in one go, you use the algo shown at 5:00. In this algorithm you use the last solution for the next step in algorithm. So if I want to have the modulo from an exponent of 5 I repeat the steps of the algorithm 5 times. But only the solution of the penultimate step is needed to calculate my final solution (yet we do the rest because the penultimate solution needs the step before and so on and so on). But, if somebody gave us the solution for step 5 for example and want to go to an exponent of 11, we can use the solution of step 5 and just go from there to 11. And that's what this exchange uses. You want to have 5 as your private key and I want to have 6. I take your answer from doing 5 steps and do my 6 steps reaching the answer of the algo after 11 steps. You do the same, take the answer of my 6 steps and do your 5 steps, also reaching 11 steps. We both don't actually know, that 11 steps have been done in total, you only know that my answer plus your number of steps gives the same result as your answer plus my number of steps. So the attacker might intercept your answer, but does not know how many steps to add to get the result we both know have. The attacker can in theory use one of our shared answers plus the information of the base and modulo to invert the operation and find out which exponent one of us used and thus know the number of steps needed to add to the other answer, but that is computationally nigh impossible.

[@farnone6166]

what is this timing i have a test on this in a few days

[@MichaelDarrow-tr1mn]

clearly this means you win

[@alex_zetsu]

Is this a follow up to the three pass protocol video?

[@madara2887]

Hi Brian, it’d be nice if you could make videos about important algorithms like Bellman-Ford, Floyd Warshall, BFS, DFS, Prim etc.

[@Katchi_]

Right... because there are no books on the subject...

[@DavidNBooth]

Amazing video

[@jeanjcl]

This is way too well explained, thank you!

[@ATOM-vv3xu]

Why (if at all) is this preferable to asymmetric encryption?

[@alooooshm]

Keep it up. Animations help a lot!

[@zix2421]

Interesting

[@Laff700]

I wonder if there's a symmetric key cryptography algorithm which is unconditionally secure.

[@lbqg637]

this video is so good

[@hobrin4242]

how is diffie hellman different from sending over a public key?

[@imrrodri]

Great video! I'm subscribing to your channel

[@freckhard]

I assume there are some more or less clever ways to find the primitive root modulo n on each ones side? Or is it just trying until it is "good enough"?

[@hitomi7922]

Dumb question, since there seems to be a preference for a "good" base and modulus, doesn't that also mean someone building a sort of rainbow table just has to compute all the combinations of the "good" pairings?

[@QualityDoggo]

that's why the exponent should be massive

[@chri-k]

The problem is that the numbers involved are MASSIVE. Such a table wouldn't fit into the entire universe even if you managed to compute it. ( the base almost always is 3 )

[@JKTCGMV13]

Sick