How does RSA Cryptography work?

RSA encryption is used everyday to secure information online, but how does it work? And why is it referred to as a type of public key cryptography? Professor Jon Keating worked alongside the UK intelligence agency GCHQ for many years, and therefore knows a thing or two about encrypting secret messages. Here, he explains how the RSA algorithm works in general, and goes through 2 worked examples with small prime numbers.

The algorithm relies on the idea that whilst it is very easy to multiply two prime numbers together, it is extremely difficult to break up a large number (with several hundred digits) back into its prime factors. Using some clever results from Number Theory - including Fermat's Little Theorem and the Euler Totient Function - the message can be decrypted only if you know the original prime factors. This means advertising the product of the primes, or 'public key', enables people to send you a message without compromising the security of the encryption system. Even if the message is intercepted, it can only be decoded with knowledge of the prime factors - and these are incredibly difficult to obtain.

This video is sponsored by Blinkist.

Additional images and footage are used under a creative commons licence – links below.

You can also follow Tom on Facebook, Twitter and Instagram @tomrocksmaths.

Get your Tom Rocks Maths merchandise here:

[OryxGuitar]

Most challenging part left for “exercise” in the course is the calculation of d.

I learned it the hard way. Here is what I learn: Calculate the e and d at the same time so you have both public key and private key handy.

For example with p=5, q=11, one can come up with 3x27 = (5-1)x(11-1) x 2 +1
Which will make e=3, and d=27.

You publish (55, 3) as public key and
When an encrypted message comes, you use (55, 27) as private key to decrypt.

[annorome]

What I find absolutely stupid, is how people go over the most important parts in University, like you just did with the calculation of the private exponent d. That kind of education leaves lectures without a reason to visit. If it is just recitation and the critical parts are not explained at Uni, one should not pay and visit. The whole course is then down the drain. That is really sad. For example the sentence "There are tricks to do it." Why can't he just say, that it has to do with repeated exponentiation? He does not need to put it on the board but at least give hints. Explicit education ALWAYS beats implicit education, because you are not demanded to come up with an idea from nothing. How would you be able to do that without some prior knowledge? That's not, how people learn! People just don't come up with ideas out of thin air. And to add, I think this is just a University-snobby way to show that you are smarter by leaving people without anything to work out s.t. if they don't see a solution, they think they are stupid. Little do the people know that most of the professors also don't come up with their stuff on their own, while pretending that they are. It is an artifical way to make themselves and their topics look complex and untouchable, while they clearly are not. Just unnecessary and anti-didactic.

[tellator]

Thank you very much. All I've needed is these formulas, but in videos I watched no one writes them directly in understandable manner. That's great manual, thanks

[amarioguy]

Just a quick PSA for anyone choosing keys: the public exponent is usually advised to be 65537 nowadays due to security issues with e=3

[huyhuynh]

Thank a lot, I try to find this for a long time. People just say that Using Public key to Encrypt, and Decrypt by Private key, and now I know what happens.

[RebeccaSilver]

This takes me back to when I was a kid and me and my best friend used to send coded messages to each other, our codes were much simpler 😂 it takes me back to good memories.

[oldwillsy]

This was great - it inspired me to write a short Python script to automate the process. It's slow with bigger primes, but works perfectly!

[HutS-ec]

Someone helps me please:
At 4:55 he explained the meaning of: c = m^e (the mod parenthesis) by saying that you subtract number of n from m^e until you get c . This means that c is smaller than m^e. This means you have a smaller number = a bigger number then (the mod parenthesis) both at the same side.
But at 6:47 he wrote: de = 1 (the mod parenthesis). Notice how 1 is the smallest integer number ever and it is at the same side of (the mod parenthesis).

[hollywoodzero]

Fantastic videos. Keep them coming. Also, the Pokemon catch algorithm got me hooked on the channel. My kids also loved it and are super interested in how math works in the world.

[JalebJay]

I love rsa over aes for theory, but I remember my class of cryptography focused so much more on aes/des.

[JasonOvalles]

A channel where I can learn about RSA encryption, fluid mechanics, and Pokémon catch rates? Absolutely amazing!!

If you ever start a Patreon (or anything similar), I would love to contribute!

[uroosaimtiaz]

Thanks Tom! The examples were great for reviewing concepts :)

[marzougnabil]

Have no idea why u do not explain the math behind d as it is the most difficult part in the process.

[ouardi-by]

Thank you so much it was a really good video about explaining the RSA algorithm

[briang]

I hope there's going to be a part 2 🤞

[garysilvester]

This hindges on p and q being large such that the advertised n is hard to factor back into the primes p and q. Given the recommended sizes of p and q, how many large enough prime combinations are there to work with such that someone in the middle can't just use a big lookup table for n to see what its prime factors are instead of trying to directly factor n?

[michaellatsky]

Awesome thanks! I made a whole working demo!!

[bananalord]

Amazing! Better explained than any of my real life teachers ever thank you!

[garydunken]

Thanks for the great explanation on how RSA works. I have 2 questions:
1. At 10:53 - When calculating e, shouldn't it be a coprime of both n and PHI(n)? i.e. coprime of both 55 and 40, not just 40?
2. At 12:54 I understood n and e form the public key part, and d is the private key that is needed to decrypt a ciphered message encrypted with public key. Based on the shown formula for d, does that mean there can be multiple values for d for a given public key (i.e. multiple private keys!)? In the example shown, d can be 27, 67, 107, 147, ... !! Please confirm.
Until this day, I thought there can be only 1 possible private key for a given public key. But it looks like we could have many private keys to decrypt a message that is encrypted with corresponding public key.

[augustpreisler]

Fantastic video! Great explanation, keep up the good work!