How does RSA Cryptography work?

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

[@剑胆琴心吉他弹唱]

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.

[@BruceLee-qc2lm]

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]

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

[@davidb.e.6450]

This comment is underrated💯👌

[@Moocow2003]

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.

[@annorome]

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

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

[@dianam.7297]

Thank you for mentioning 🙏🙏

[@rusty9060]

glad you mentioned that "e" is a known constant

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

[@HutS-e5c]

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

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

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

[@JalebJay]

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

[@michaellatsky]

Awesome thanks! I made a whole working demo!!

[@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: kzbin.info/www/bejne/hITKYYKgnp2lg9E

[@marzougnabil6901]

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

[@conoro774]

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

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

[@eggtimer2]

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

[@garydunken7934]

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]

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]

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

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

[@ellaberlowitz9138]

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

[@uroosaimtiaz]

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

[@bananalord8575]

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

[@CinemaBiohazard]

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!

[@darkbot081]

I still don't understand the "calculating d" part. He says the number d (in first example) is so equation e*d = 1 (mod40). As I understand 1 mod anything will always be 1, therefore we need to find d so e * d = 1, which seems impossible

[@Joe-vj1fz]

Modulus math is confusing because everything is written as (mod x). But when you see something like e*d = 1 (mod 40) this really means: (e*d) mod 40 = 1. i.e. What two numbers e & d equal 1 when their product is set to mod x. I do not know why the notation is like this, but when you see (mod x) at the end just assume everything is performing the (mod x) computation.

[@ouardi-b2y]

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

[@augustpreisler1565]

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

[@augustpreisler1565]

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

[@michaellatsky]

Screw the haters, thx bro for vid

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

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

[@0xAlmighty]

Thanks, it cleared my doubts :)

[@claudiatrujillociafre3865]

Sir, thank you very much 🙏

[@h0ax]

Does message needs to be smaller than n?

[@techbrokerala]

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

[@alinekoh2]

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]

@@alinekoh2 Thank you ❣️

[@HutS-e5c]

@@alinekoh2 Can you explain more please?

[@dangerbirb4981]

@@HutS-e5c Use Fermat's Little Theorem. Look that up and it will explain the process.

[@_a.lva.n]

Merci beaucoup

[@goldenera7090]

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?

[@GiseleandPrincesseBluePrint]

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

[@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]

@@bee_irlthank you, I was so confused

[@HutS-e5c]

@@bee_irl How can "d*e ≡ 1 (mod (p-1)(q-1))", mean "d*e mod ((p-1)(q-1)) = 1" ?

[@bee_irl]

@@HutS-e5c for the second one, i meant "mod" as in the modulo operator, where *8 mod 3 = 2*. (% in most programming languages)

[@HutS-e5c]

@@bee_irl I am not really understanding. It looks that it is a property for the modulus arithmetic to write the mod on the right side or the left side. Thank you anyway.

[@firstnamesecondname5341]

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

[@ephrembedhaso7741]

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

[@roccopatella5681]

Thanks!!😌

[@youuuuu10]

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

[@AspiringAuthor-mw9ri]

How would a proof of RH impact cryptography?

[@wannabeactuary01]

Brilliant and thanks

[@subhanjaved5143]

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

[@MM-gw7ik]

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]

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

[@ahmedal-kharusi9053]

d=27 how is that ?

[@mohamadalimoussawe1737]

m=5

[@rexa5073]

What if m is higher than p*q?

[@davidfoo6974]

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

[@KeringKirwa]

does not work for m = 10.

[@deadend4425]

yea for m = 104 too

[@martinplayer23]

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

[@nyahahahhaha]

enter shor's algorithm

[@henrydeutsch5130]

3 = 10 mod 7

[@henrydeutsch5130]

3 = 17 mod 7

[@tafadzwapchitenhe1092]

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

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

[@IvanManchur]

How to find d quickly?

[@JarppaGuru]

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

[@henrydeutsch5130]

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

[@JarppaGuru]

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]

He is talking about numbers but only writes letters 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]

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

[@Neuroszima]

Dude, he told you how RSA works, it is all in the video. That's all the title said wuold explain

[@iteerrex8166]

Like I hinted an *introduction* should start with axioms and first principles, and build up from there. Giving a recipe that each ingredient required a dozen logical steps to get to, is not an introduction. It’s a lecture to advanced students, or a chat with your colleagues.

[@zstar8397]

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.

[@kdbwiz]

Nudge nude wink wink - rote teaching. Example lacking any insight. How it works? Nothing to see here.