How prime numbers protect your privacy

Most of us have probably heard about encryption before, but have you ever wondered how it works? This video explores the math behind the RSA cryptosystem, a very popular encryption method that set the stage for asymmetric cryptography.
► Join my Discord server: / discord
This video was made as part of the Summer of Mathematical Exposition organized by @3blue1brown
► Sources:
- en.wikipedia.org/wiki/RSA_(cr...)
- / rsa-gradually-leaves-t...
- en.wikipedia.org/wiki/Prime_n...
► Learn more about...
- Bézout's identity: en.wikipedia.org/wiki/B%C3%A9...
- The extended Euclidean algorithm: en.wikipedia.org/wiki/Extende...
- Modular exponentiation: en.wikipedia.org/wiki/Modular...
► Stock footage from: pixabay.com/
🎵 Music from Epidemic Sound, register with my link to support the channel and get a discount:
www.epidemicsound.com/referra...
Chapters:
0:00 - Intro
0:35 - Alice and Bob
01:10 - Encryption
02:01 - Asymmetric cryptography
03:22 - Rivest-Shamir-Adleman
03:50 - Modular congruence
04:59 - The RSA Equation
05:52 - Prime numbers
07:27 - Generating a keyset
09:19 - Implementation
10:25 - Proof of correctness
12:42 - Conclusion
#SoME2

[@NamePointer]

What is this? A new video already? It hasn't even been a year yet! Just kidding, I'm really happy that I managed to upload a second video this summer. This one is quite different from my usual style though, but I wanted to participate in SoME2. Please let me know what you think!

[@pichu8959]

it was a great video, a nice refresher of the topic

[@Ravioli1586]

It was very helpful to understand these concepts mathematically. Thanks for the video!!

[@NoNTr1v1aL]

Absolutely amazing video! Subscribed.

[@zenhookah9296]

glad you are still around keep up the good work

[@conando025]

Great Video there's only a slight problem I have with it. Namely that you say that the private key is for encryption and the public key for description, while this is probably the most common use case it can lead to confusion when thinking about digital signatures since there the roles are reversed. Just something that took me a while when first learning about public key crypto

[@NamePointer]

You're absolutely right. I should have pointed out that there are usecases where the keys' roles are reversed. I didn't think about it because I only talked about RSA in the context of message encryption, but the math I showed also works for private key encryption.

[@lolcat69]

A new video of name pointer :O Edit: Man, this is such an interesting topic, after watching this video, I can say, I learn something new, and I understand most of it, I live this chanell and the guy that make this videos, keep the good work :D

[@SFSylvester]

This was great! Hope you're able to put out more explainers one day!

[@alex-yk8bh]

Great educational video!

[@AviPars]

Great video! Subbed

[@johnchessant3012]

good explanation

[@annoyingman6184]

Nice video can you make a tutorial channel where you implement the topics in one program

[@featherless656]

Cool video, would be cool to see you remake discord lol

[@RSLT]

Very Interesting and informative Great Job. Quick note p and q don't have to be prime numbers. They need to prime to each other! This is one of the reasons the Riemann hypothesis and prime numbers theories are super important.

[@NamePointer]

Thank you for the feedback! However, if p and q are not primes, the proof of correctness wouldn't be valid anymore, as it used Fermat's little theorem which requires them to be primes, or am I missing something?

[@orangeoranj8007]

@@NamePointer The proof can be amended with Euler's theorem, which generalizes Fermat's little theorem.

[@brendawilliams8062]

Thankyou.

[@lbirkert]

What would happen if the man in the middle just send it's own key instead of proxy the public key of person b so he could be able to decrypt the messages and reencrypt them using the public key of person b so nobody would notice anything?

[@NamePointer]

Although modifying and injecting messages is a lot more difficult than just reading them, what you describe could be a significant security threat if an attacker succeeded to do so. Luckily, there is something called "Signing" to combat that. You can learn more about it on the RSA Wikipedia page.

[@fullfungo4476]

But you already know Bob’s public key. That’s the starting state of the algorithm. No one sends their public keys. This is because RSA is a secure encryption algorithm, not secure communication algorithm.

[@NamePointer]

@Fullfungo actually, the public keys have to be sent once after having been generated, otherwise, how is the other person supposed to know it?

[@conando025]

@@NamePointer true but in the use case of https that is done through a chain of trust and the DNS servers since one public key is enough to start a secure conversation. And you shouldn't be using RSA for communication since it's way to inefficient compared to a symmetric encryption like AES so most of the time RSA is simply used as a method to securely establish an AES tunnel

[@whannabi]

@@conando025 you're right about its usage.

[@hhhharis622]

Bro I was expecting a NordVPN ad the whole video🤣

[@NamePointer]

The irony is that the video shows that you don't actually need a VPN to have an encrypted internet connection, you just have to use secure apps and only access HTTPS websites!

[@Baezor]

Super cool and well-made video, I still have no idea what I just watched though.

[@brendawilliams8062]

It seems to me a bunch of different triangulations that you don’t want to step on toes with. I never investigated computers.

[@Baezor]

@@brendawilliams8062 the quantum mainframe can obliterate rsa, good luck prime numbers, you bout to be cyber cracked by the triangulations of the quantum spherical nature of the encrypted 4-dimensional realms

[@brendawilliams8062]

@@Baezor I just can’t get it. All I can figure is prime numbers are dangerous.

[@Baezor]

@@brendawilliams8062 exactly! prime numbers are actually evil!

[@brendawilliams8062]

@@Baezor that is what I thought. You can’t work on anything that’s been bought and sold.

[@pianoforte611]

Oof, that opening sentence stung.

[@abhi36292]

Alice and bob definitely didnt touch grass for the last 6 months, lol

[@ItsNat21_]

gotta love cryptography

[@majokuhn]

Luckly I had it in school

[@keremino]

namepointer its been 11 months please make a new video im getting so bored in my basement

[@NamePointer]

Ok

[@thegamerboss2440]

@@NamePointerhuh

[@taxevasiongaming]

Yes lads

[@minheepark4896]

Huh suddenly you seem like Nas daily :|

[@JM-us3fr]

6:10 Your definition of prime numbers is not quite correct. Specifically, you need to replace your use of the word “integer” with “positive integer.” If you were trying to allow for negative primes, then you can’t say “greater than one” and “…product of _smaller_ positive integers…” You would have to say “Nonzero” and “Can’t be written as the product of two nonunits (e.g. not +1 or -1)” respectively.

[@NamePointer]

Thanks for the feedback, however I explicitly said "greater than one" to account for that

[@JM-us3fr]

@@NamePointer Yes, but you didn’t say that the _two factors_ had to be greater than one or even positive. Just “smaller integers.” Thus, a factorization like 7=(-1)(-7) would rule out 7 from being prime, by your definition.

[@NamePointer]

Oh yes I understand you now. Thanks for pointing that out!

[@JM-us3fr]

@@NamePointer No problem.

[@TorvoTheMighty]

U quit again aye?

[@NamePointer]

No

[@sandychen1381]

Where are you

[@portalguy1432]

i dont even remember subscribing to this guy

[@aviee2046]

Same lol

[@NamePointer]

I hope you enjoyed the video though :)

[@portalguy1432]

@@NamePointer didn’t watch it though no hard feelings

[@lolcat69]

@@portalguy1432 that is rude man...

[@sleepntsheep1169]

@@portalguy1432 lets go find who asked