How does RSA Cryptography work?

Подписаться 187 тыс.

Просмотров 56 тыс.

50% 1

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

Опубликовано:

12 янв 2023

Ссылка:

Скачать:

Готовим ссылку...

Добавить в:

Мой плейлист

Посмотреть позже

Комментарии : 84

@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

@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 Месяц назад

Thank you for mentioning 🙏🙏

@rusty9060 15 дней назад

glad you mentioned that "e" is a known constant

@creatorofimages7925 9 месяцев назад

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 6 месяцев назад

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 6 месяцев назад

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

@davidb.e.6450 5 месяцев назад

This comment is underrated💯👌

@Moocow2003 2 месяца назад

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 2 месяца назад

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

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

@uroosaimtiaz Месяц назад

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

@michaellatsky 6 месяцев назад

Awesome thanks! I made a whole working demo!!

@ellaberlowitz9138 7 месяцев назад

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

@augustpreisler1565 2 месяца назад

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

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

@bananalord8575 6 месяцев назад

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

@CinemaBiohazard 5 месяцев назад

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!

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

@JalebJay Год назад

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

@0xAlmighty 21 день назад

Thanks, it cleared my doubts :)

@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: ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-NSg0Oji8rMo.html

@firstnamesecondname5341 Год назад

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

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

@wannabeactuary01 Год назад

Brilliant and thanks

@claudiatrujillociafre3865 2 месяца назад

Sir, thank you very much 🙏

@subhanjaved5143 Год назад

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

@garydunken7934 2 месяца назад

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 2 месяца назад

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 2 месяца назад

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

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

@roccopatella5681 Год назад

Thanks!!😌

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

@augustpreisler1565 2 месяца назад

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

@goldenera7090 6 месяцев назад

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 5 месяцев назад

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

@MM-gw7ik 4 месяца назад

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 2 месяца назад

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

@techbrokerala Год назад

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

@alinekoh2 10 месяцев назад

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 10 месяцев назад

@@alinekoh2 Thank you ❣️

@h0ax 6 месяцев назад

Does message needs to be smaller than n?

@eggtimer2 Год назад

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

@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 7 месяцев назад

@@bee_irlthank you, I was so confused

@AspiringAuthor-mw9ri Месяц назад

How would a proof of RH impact cryptography?

@ephrembedhaso7741 9 дней назад

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

@ahmedal-kharusi9053 2 месяца назад

d=27 how is that ?

@michaellatsky 6 месяцев назад

Screw the haters, thx bro for vid

@JarppaGuru 2 месяца назад

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

@marzougnabil6901 4 месяца назад

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

@conoro774 4 месяца назад

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 😂😂

@rexa5073 4 месяца назад

What if m is higher than p*q?

@mohamadalimoussawe1737 2 месяца назад

m=5

@henrydeutsch5130 2 месяца назад

3 = 10 mod 7

@henrydeutsch5130 2 месяца назад

3 = 17 mod 7

@user-xb8jc9bq3b 2 месяца назад

How to find d quickly?

@user-me1ry6lg6d 2 месяца назад

does not work for m = 10.

@deadend4425 Месяц назад

yea for m = 104 too

@martinplayer2348 Месяц назад

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

@zstar8397 6 месяцев назад

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.

@JarppaGuru 2 месяца назад

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 7 месяцев назад

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

@henrydeutsch5130 2 месяца назад

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

@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 6 месяцев назад

But the vid was so useful!

@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

@SatheshSivashanmugam 11 месяцев назад

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 11 месяцев назад

Awesome thanks!