Diffie-Hellman Key Exchange: How to Share a Secret

Рет қаралды 132,475

Ай бұрын

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.substack.com/
You can support the Spanning Tree channel at ko-fi.com/spanningtree
Spanning Tree is created by Brian Yu. brianyu.me/
Email me at brian@spanningtree.me to suggest a future topic.

Пікірлер: 185

@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 11 күн бұрын

yup, absolutely the best thing ever!!!

@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!!

@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

@mtranchi Ай бұрын

That red robot looks scary.

@k-vn-7 15 күн бұрын

Gotta stay alert. Red Guy out there lurkin'.

@mtranchi 15 күн бұрын

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

@samueltaylor4989 7 күн бұрын

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

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

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

@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." 😊👍

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

@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 :)

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

@SuperLlama88888 Ай бұрын

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

@lucas-pcs Ай бұрын

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

@MOOBBreezy Ай бұрын

What a great cryptography lesson! Thank you!

@Valo_iO Ай бұрын

Well explained, great video!

@mauisstepsis5524 2 күн бұрын

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

@sobevj 21 күн бұрын

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!

@ChristopherOBrienPSU Ай бұрын

Best explanation of DH that I've ever seen

@deschia_ Ай бұрын

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

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

@kacper7516 Ай бұрын

One of the best explanation

@Hi2uGaming Ай бұрын

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

@Katchi_ Ай бұрын

Liar.

@thefrub Ай бұрын

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

@cdvgter 27 күн бұрын

This is explained so well!

@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: kzfaq.info/get/bejne/hNN9bKtyl7O1d30.html 2. The Math behind explains deeper and why exponentiation is safe: kzfaq.info/get/bejne/j9CimdCQ1LizYKs.html 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

@annantsharma91 Ай бұрын

Keep up the good work, loved it ❤

@Anythiny 29 күн бұрын

its always fun to watch ur explaination

@roborogue_ Ай бұрын

great video!

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

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

@pbezunartea Ай бұрын

Great video, thanks!

@jameslovering9158 24 күн бұрын

Thank you, that was easy to follow !

@arcanogameplays Ай бұрын

Best explanation out there

@Mahm00dM0hanad 14 күн бұрын

Well explained, thanks a lot

@rhysbaker2595 Ай бұрын

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

@andreujuanc Ай бұрын

Brilliant! thanks for such good video

@ashb2483 6 күн бұрын

Great vid!

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

@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

@tanmaybora359 Ай бұрын

You are the best!

@guoard Ай бұрын

Great job!

@eyobsolomon4663 Ай бұрын

Really, thank you so much!

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

@DavidNBooth Ай бұрын

Amazing video

@callisoncaffrey Ай бұрын

Good explanation gets a like.

@melonberry6771 Ай бұрын

I like your content, please make more

@AjinGixtas Ай бұрын

Cool vid :)

@devr4j Ай бұрын

thanks it was helpful

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

@imrrodri Ай бұрын

Great video! I'm subscribing to your channel

@lbqg637 Ай бұрын

this video is so good

@arpitkumar4525 Ай бұрын

Wow! First time I saw the beauty in Maths

@TNewton001 14 күн бұрын

Thanks!

@lostvayne871 Ай бұрын

That red guy is a masterpiece!!!

@brianarsuaga5008 18 күн бұрын

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

@tirana.1887 Ай бұрын

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

@hvnterblack Ай бұрын

good material

@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

@clementdato6328 Ай бұрын

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

@Krosis_ 6 күн бұрын

Truly mind blowing

@official_noself 2 күн бұрын

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.

@foobarf8766 Ай бұрын

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

@benjaminkpaul Ай бұрын

brian yu is a genius😊😅

@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

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

@Stvk Ай бұрын

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

@ArcherNX1701 17 күн бұрын

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?

@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! :)

@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"?

@stachowi Ай бұрын

Brian!!!!

@cloverberry721 Ай бұрын

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

@zudwa9280 Ай бұрын

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

@ricardopassos1180 Ай бұрын

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

@JKTCGMV13 Ай бұрын

Sick

@alooooshm Ай бұрын

Keep it up. Animations help a lot!

@jeanjcl Ай бұрын

This is way too well explained, thank you!

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

@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

@zix2421 5 күн бұрын

Interesting

@alex_zetsu Ай бұрын

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

@tomcruise3003 13 күн бұрын

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

@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

@farnone6166 Ай бұрын

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

@MichaelDarrow-tr1mn Ай бұрын

clearly this means you win

@hobrin4242 Ай бұрын

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

@ATOM-vv3xu Ай бұрын

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

@Laff700 Ай бұрын

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

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

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

@beaverbuoy3011 Ай бұрын

Ooh!

@timleferink 18 күн бұрын

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

@068LAICEPS Ай бұрын

❤

@donwald3436 Ай бұрын

How do you know which computer is Diffie and which computer is Hellman?

@sarthak-salunke 21 күн бұрын

❤❤

@userou-ig1ze 15 күн бұрын

It might be more interesting to do this in the real world without mod functions, as in actually exchange a physical key

@optimistcarrot4915 Ай бұрын

why could you not for example use a bitwise AND or XOR instead of the +? since their order does not matter and they aren't reversible

@cahdoge Ай бұрын

Nice thinking, but that dosen't work. AND would result in a key, that is mostly zeroes, making it useless, since it dosen't properly scramble your communication. XOR is easily reversible (just run it again, similar to +) so it's no good either.

@Ggdivhjkjl Ай бұрын

Why not just look for prime numbers when attacking?

@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 22 күн бұрын

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.