How does RSA Cryptography work?
ฝัง
- เผยแพร่เมื่อ 12 ม.ค. 2023
- 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...
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
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
Thank you for mentioning 🙏🙏
glad you mentioned that "e" is a known constant
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.
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...
Rivest, Shamir, and Adelman probably bounced a lot of ideas amongst each other.
This comment is underrated💯👌
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.
@@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.
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.
Thanks Tom! The examples were great for reviewing concepts :)
Fantastic video! Great explanation, keep up the good work!
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.
tysm for this, helping me pass my assignments :) a godsend, well explained!
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.
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!
Awesome thanks! I made a whole working demo!!
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?
Amazing! Better explained than any of my real life teachers ever thank you!
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!
Thanks, it cleared my doubts :)
Thanks Tom for this 🫡 great video.
I’d read Gordon Welchman The Hut Six Story, a fantastic read
I love rsa over aes for theory, but I remember my class of cryptography focused so much more on aes/des.
I hope there's going to be a part 2 🤞
I have another video where I talk to Jon about his research here: th-cam.com/video/NSg0Oji8rMo/w-d-xo.html
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.
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
@@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.
How do you calculate the value of d when the calculations become more difficult?
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.
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.
Sir, thank you very much 🙏
Brilliant and thanks
Sir can you please made a vidoe on discrete mesh and Variational technique..🙏♥️
Thanks!!😌
how did you get value of d , the rest is simply
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) ?
The answer to your question is about half a semester of elementary number theory.😭
Does message needs to be smaller than n?
How can we compute 13^27 mod 55, is there any simple solution for this?
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
@@alinekoh2 Thank you ❣️
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?
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
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!
I wish there was a video that shows some proofs. What's on TH-cam all is slightly off or omits assumptions.
How would a proof of RH impact cryptography?
d=27 how is that ?
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?
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?
@@bee_irlthank you, I was so confused
Would've been nicer if he explained the computation under congruence. Not everyone knows how to do modular arithmetic.
Have no idea why u do not explain the math behind d as it is the most difficult part in the process.
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 😂😂
Screw the haters, thx bro for vid
What if m is higher than p*q?
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
m=5
How to find d quickly?
does not work for m = 10.
yea for m = 104 too
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
3 = 10 mod 7
3 = 17 mod 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.
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
He is talking about numbers but only writes letters on the board 🤔🤦♂️😝
Pretty bad instruction, nothing is motivated. Tell me what’s going before you write a bunch of shit on the board
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.
But the vid was so useful!
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.
He does say the origin at the end. Might have been better to set it up mentioning Fermat's/Euler's Theorem
@@JalebJay I turned it off a few mins in.
Agreed. The fact this guy is a professor of anything just illustrates how terrible the quality of teaching is at the University of Oxford
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));
}
Awesome thanks!
Nudge nude wink wink - rote teaching. Example lacking any insight. How it works? Nothing to see here.