*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: kzread.info/dash/bejne/d4eEtsFsZtO7dsY.html&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

6 жыл бұрын

Don't be afraid to demonstrate more explicit mathematics.

@yamansanghavi

6 жыл бұрын

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

@pbsinfiniteseries

6 жыл бұрын

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 KZread got rid of Annotations, because that would be an even easier (and better) way to remedy the situation.

@victorvalencia6466

6 жыл бұрын

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

@pbsinfiniteseries

6 жыл бұрын

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.

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

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

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

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

@skebess

6 жыл бұрын

lol, epic

@Sam_on_YouTube

6 жыл бұрын

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

@pbsinfiniteseries

6 жыл бұрын

Touché

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

@seanspicer516

5 жыл бұрын

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

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

**elliptic curves intensifies**

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

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.

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

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

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

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

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

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!

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.

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

@mattybowards7471

6 жыл бұрын

rudy pornhub

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.

Great stuff. Thanks for this!

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

Intense, but brief. Nice!

Gabe, the Mind blower!

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

That was veyyy clear!! Thanks!

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

6 жыл бұрын

Kabitu1 KZread already has it queued up next for me 😂

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

Awesome episode

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.

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

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.

Love those crypto episodes!!!

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

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!

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

@screwhalunderhill885

6 жыл бұрын

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

What I learned in Abstract Algebra class finally feels useful

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

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.

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

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.

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.

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

wonderful!

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

Gabe!

Welcome back

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!

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

@michaelwestern11

5 жыл бұрын

Ah a joker!

Just one day before my cibersecurity exam. Thanks

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

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

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.

Looking forward to elliptic curve Diffie-Hellman :)

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

yay group theory... finally!!!

thanks

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?

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

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

Heck yes its gabe! We miss you gabe.

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

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

6 жыл бұрын

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

6 жыл бұрын

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

6 жыл бұрын

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

6 жыл бұрын

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

6 жыл бұрын

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

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

Ooohhhh I bet the next cryptography vid is on Elliptic Curves

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

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

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

6 жыл бұрын

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

6 жыл бұрын

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

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.

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

Elliptic curves!

the next video will be about elliptic curves 😊

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.

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

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

Oh boy....

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

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.

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?

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.

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.

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.

Next episode, Elliptic curves

Dat characterization of the cyclic totient groups tho

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

@wilddogspam

6 жыл бұрын

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

6 жыл бұрын

You can also watch the condensed intro of modular arithmetic that Kelsey did in this earlier video (to which I referred in this episode): kzread.info/dash/bejne/Y2aFla-rmJOZd84.html

@shaylempert9994

6 жыл бұрын

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

@pbsinfiniteseries

6 жыл бұрын

Oh, absolutely.

“Decaf Gabe” HAHAHA FUCK

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

@screwhalunderhill885

6 жыл бұрын

I'm more of a 1.25 guy

@mattybowards7471

6 жыл бұрын

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

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

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

6 жыл бұрын

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.

Can we talk about eliptic curve crypto

+1 for Rusty's face

How did 625 turn into 9?

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

@franzluggin398

6 жыл бұрын

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

6 жыл бұрын

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.

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

6 жыл бұрын

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

@PsyKosh

6 жыл бұрын

Thanks.

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

@romajimamulo

6 жыл бұрын

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

@jake1996able

6 жыл бұрын

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

@romajimamulo

6 жыл бұрын

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

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.

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.

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?

Math

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

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.