How does RSA Cryptography work?

Рет қаралды 61,880

Жыл бұрын

Oxford Sedleian Professor of Natural Philosophy Jon Keating explains the RSA Cryptography Algorithm. Get 25% off Blinkist premium and enjoy 2 memberships for the price of 1! Start your 7-day free trial by clicking here www.blinkist.com/tomrocksmaths
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.
Blockchain Travel: • 🇬🇧Bletchley Park, Home...
Produced by Dr Tom Crawford at the University of Oxford. Tom is an Early-Career Teaching and Outreach Fellow at St Edmund Hall: www.seh.ox.ac.uk/people/tom-c...
For more maths content check out Tom's website tomrocksmaths.com/
You can also follow Tom on Facebook, Twitter and Instagram @tomrocksmaths.
/ tomrocksmaths
/ tomrocksmaths
/ tomrocksmaths
Get your Tom Rocks Maths merchandise here:
beautifulequations.net/collec...

Пікірлер: 89

@TomRocksMaths Жыл бұрын

Get 25% off Blinkist premium and enjoy 2 memberships for the price of 1! Start your 7-day free trial by clicking here www.blinkist.com/tomrocksmaths

@creatorofimages7925 11 ай бұрын

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.

@BruceLee-qc2lm 8 ай бұрын

I'm experiencing this right now and it's so annoying. In College, they are very exact with the things they teach you. University Discrete Math though is like... learn EVERYTHING from these two chapters and only some of it will be on the test. I learned cartesian product, sets and matrices for them to not be on the test...

@kayakMike1000 7 ай бұрын

Rivest, Shamir, and Adelman probably bounced a lot of ideas amongst each other.

@davidb.e.6450 7 ай бұрын

This comment is underrated💯👌

@Moocow2003 4 ай бұрын

The calculation of d is the only part of this otherwise excellent tutorial that leaves me confused. I've tried other RSA tutorials too and none of them explain d. I've tried decrypting m with different values of d and it works the same each time, but I don't know why that's the case. Also not sure how to find d without using an online tool to calculate it, which seems pretty counterproductive for a tutorial video.

@creatorofimages7925 4 ай бұрын

@@Moocow2003Funnily enough, you will find a perfect approach to finding out private exponent d on videos that do not even attempt to explain RSA. Trying to find it to link it here.

@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

@dianam.7297 3 ай бұрын

Thank you for mentioning 🙏🙏

@rusty9060 2 ай бұрын

glad you mentioned that "e" is a known constant

@hollywoodzero2915 Жыл бұрын

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.

@huyhuynh5575 Жыл бұрын

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.

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

@uroosaimtiaz 3 ай бұрын

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

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

@ellaberlowitz9138 9 ай бұрын

tysm for this, helping me pass my assignments :) a godsend, well explained!

@augustpreisler1565 3 ай бұрын

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

@JalebJay Жыл бұрын

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

@michaellatsky 8 ай бұрын

Awesome thanks! I made a whole working demo!!

@0xAlmighty 2 ай бұрын

Thanks, it cleared my doubts :)

@firstnamesecondname5341 Жыл бұрын

Thanks Tom for this 🫡 great video. I’d read Gordon Welchman The Hut Six Story, a fantastic read

@augustpreisler1565 3 ай бұрын

How do you calculate the value of d when the calculations become more difficult?

@0briang0 Жыл бұрын

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

@TomRocksMaths Жыл бұрын

I have another video where I talk to Jon about his research here: kzfaq.info/get/bejne/hLmXY7Kbzp7WfaM.html

@garydunken7934 4 ай бұрын

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.

@tcarni21 4 ай бұрын

Yes, d can be multiple numbers, there is no unique private key. But think about it, it doesn't need to be a single answer. If you use one of the examples of the video, you could use N, M and C to try to bruteforce the value of D, and it would be nearly instant with basically any computer. However, as you increase the values of P and Q, the smallest valid value of D also increases exponentially. For P=5 and Q=11, you would have to try 27 possibilities of D until you could decrypt the message. If we use 5 digit prime numbers for P and Q (for example, 14159 and 52021, you would have to calculate +52million possibilities for D before you arrive at a valid result. So you use P and Q with hundreds or digits, it becomes basically impossible to calculate a nice D value within our lifetime. I tried to simplify here, but this is the basic idea

@Moocow2003 4 ай бұрын

@@tcarni21 Ah, that makes a little more sense. What I don't understand is that when I try decrypting C with different values of D I get the same answer (equal to M) each time. So I don't really get what the point of having different options is if I get the same, correct, answer whichever one I use.

@MM-gw7ik 5 ай бұрын

How is it that p is still the inverse of e when calculating mod n since the calculation to find p was done mod (p-1) (q-1) ?

@renedelatorre2138 4 ай бұрын

The answer to your question is about half a semester of elementary number theory.😭

@wannabeactuary01 Жыл бұрын

Brilliant and thanks

@ScouseRobert Жыл бұрын

Excellent video, really enjoyed it. Thank you. Would love it if there was a follow up from either you detailing the proof of how the decoding "Magic Trick" recovers the original message.

@goldenera7090 8 ай бұрын

is "d" unique? ie can it be only a unique value OR it could be a subset from which I can choose value of d?

@DenArtist 7 ай бұрын

I think d can be different but I usually see the smallest being prefered, I don't know if its a good practice. But definitely, d can vary! just like e

@techbrokerala Жыл бұрын

How can we compute 13^27 mod 55, is there any simple solution for this?

@alinekoh2 11 ай бұрын

yes, Fast Exponentiation formula. take 27 and look for divation to 2 powers. 16-8-4-2-1 = 27, take out only those wich sum to 27, here are 16 + 8 + 2 + 1 = 27. so, now you take original 13^27; start from 13^1 mod 55 = 13. second 13^2 mod55 = 4 mod55. and so one....or just use the Fast Exponentiation formula

@techbrokerala 11 ай бұрын

@@alinekoh2 Thank you ❣️

@h0ax 8 ай бұрын

Does message needs to be smaller than n?

@claudiatrujillociafre3865 3 ай бұрын

Sir, thank you very much 🙏

@roccopatella5681 Жыл бұрын

Thanks!!😌

@subhanjaved5143 Жыл бұрын

Sir can you please made a vidoe on discrete mesh and Variational technique..🙏♥️

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

@bananalord8575 8 ай бұрын

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

@CinemaBiohazard 7 ай бұрын

Indeed! I'm going through the Odin Project currently and I was confused on how RSA works, but I do now in a general sense. This is incredibly neat! Thank you!

@eggtimer2 Жыл бұрын

I wish there was a video that shows some proofs. What's on KZfaq all is slightly off or omits assumptions.

@tariqzafarkhan Жыл бұрын

nice job to find perfect-root along prime number thats must be sound 5,7,13,27 & so on and my opinion cryto is not been consider as schedule banking.

@KW-md1bq Жыл бұрын

Not to nitpick, but isn't Jon finding d such that de mod (p-1)(q-1) = 1 ? As opposed to finding d such that de = 1 (mod (p-1)(q-1)) 1 modulo anything bigger than 1 is 1?

@bee_irl Жыл бұрын

That's supposed to be "d*e ≡ 1 (mod (p-1)(q-1))", which would indeed mean "d*e mod ((p-1)(q-1)) = 1"... The first is the standard notation, I guess he just used that out of habit, but wrote "=" instead of "≡" (congruency) because... it's easier? Looks simpler?

@burdettboy213 8 ай бұрын

@@bee_irlthank you, I was so confused

@marzougnabil6901 6 ай бұрын

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

@conoro774 5 ай бұрын

because finding d is extremely hard to do without a pc. he says theres ways to do it as a challenge but hes just lying 😂😂

@ephrembedhaso7741 2 ай бұрын

how did you get value of d , the rest is simply

@AspiringAuthor-mw9ri 2 ай бұрын

How would a proof of RH impact cryptography?

@ahmedal-kharusi9053 3 ай бұрын

d=27 how is that ?

@youuuuu10 Ай бұрын

Would've been nicer if he explained the computation under congruence. Not everyone knows how to do modular arithmetic.

@michaellatsky 8 ай бұрын

Screw the haters, thx bro for vid

@JarppaGuru 4 ай бұрын

1:04 no need find n. you find p and q then n =p*q then you create private key using someone public key xD, but its fine n is public too LOL

@rexa5073 6 ай бұрын

What if m is higher than p*q?

@davidfoo6974 23 күн бұрын

Here's a "d" that I prepared earlier. 🤣

@mohamadalimoussawe1737 3 ай бұрын

m=5

@user-xb8jc9bq3b 3 ай бұрын

How to find d quickly?

@user-me1ry6lg6d 4 ай бұрын

does not work for m = 10.

@deadend4425 3 ай бұрын

yea for m = 104 too

@martinplayer23 2 ай бұрын

Because the message must be incommensurate with the selected number n For example 10 and 55 are both divisible by 5, it cant be like that for it to work. I dont know why it doesnt work for 104 tho, maybe some human error in calculation

@henrydeutsch5130 4 ай бұрын

3 = 10 mod 7

@henrydeutsch5130 4 ай бұрын

3 = 17 mod 7

@tafadzwapchitenhe1092 6 күн бұрын

"13^27(mod55) should be pretty simple ?" "i did last night "😏

@JarppaGuru 4 ай бұрын

14:00 u did not. we have so called calculator before u born lol. paper!, but we know answer is 7 if you calculate 27 correct LOL

@johannez9123 8 ай бұрын

He is talking about numbers but only writes letters on the board 🤔🤦‍♂️😝

@henrydeutsch5130 4 ай бұрын

Pretty bad instruction, nothing is motivated. Tell me what’s going before you write a bunch of shit on the board

@zstar8397 7 ай бұрын

Hey hope you are doing alright just I wanna say that GOD loved the world so much he sent his only begotten son Jesus to die a brutal death for us so that we can have eternal life and we can all accept this amazing gift this by simply trusting in Jesus, confessing that GOD raised him from the dead, turning away from your sins and forming a relationship with GOD.

@iteerrex8166 Жыл бұрын

I have NEVER liked this type of introduction to a topic. For example: These are the steps to finding the transpose of a matrix 🤮 It was until advanced classes when we drove everything from the ground up, that I was happy about it.

@JalebJay Жыл бұрын

He does say the origin at the end. Might have been better to set it up mentioning Fermat's/Euler's Theorem

@iteerrex8166 Жыл бұрын

@@JalebJay I turned it off a few mins in.

@TheAcer4666 Жыл бұрын

Agreed. The fact this guy is a professor of anything just illustrates how terrible the quality of teaching is at the University of Oxford

@TheAcer4666 Жыл бұрын

this is a truly awful lecture. Just blathering through definitions off written notes, pulling everything out of nowhere without any motivation. The actual motivating points behind RSA are far more interesting than this drone.

@michaellatsky 8 ай бұрын

But the vid was so useful!

@SatheshSivashanmugam Жыл бұрын

Small script in Java using the above example. public static void main(String[] args) { BigInteger p=new BigInteger("5"); BigInteger q=new BigInteger("11"); BigInteger n= p.multiply(q); BigInteger e= new BigInteger("3"); //plain text BigInteger m=new BigInteger("7"); //Encryption BigInteger encrypted = m.modPow(e, n); System.out.println("cipher:: " + encrypted); //Decryption BigInteger d = e.modInverse(p.subtract(BigInteger.ONE).multiply(q.subtract(BigInteger.ONE))); System.out.println("d: " + d); System.out.println("decrypted:: " + encrypted.modPow(d, n)); }

@TomRocksMaths Жыл бұрын

Awesome thanks!