HomeОбразованиеRelated VideosMore From: Eddie Woo

The RSA Encryption Algorithm (1 of 2: Computing an Example)

1758 ratings | 177588 views
Html code for embedding videos on your blog
Text Comments (133)
Graham Bond (9 days ago)
4=mod((round(x))^5,14) {x>0} first x on the left =2
Graham Bond (10 days ago)
I have RSA deciphered from boredom :-) mod(n, round(x))=0 gives immediately p and q
Thomas patrickson (11 days ago)
Thank you so much, great video and your a great teacher.
Rakhi Dhavale (23 days ago)
This teacher is a amazing with his teaching skills 👍🏻
Md Anwar Jamal (24 days ago)
really fantastic Sir
محمد (1 month ago)
this teacher is GOLD
Zhaoxun Yan (1 month ago)
The "lock" analogy is much better than the "public key" terminology. I came up with this idea soon after I learned the RSA and I am not alone. I wonder why they have not changed the terminology yet?!
Nick HOLMES (1 month ago)
I wonder what time the Yoga class turns up.
game BOXNZ (1 month ago)
ur gay
Daniel Ustarez (1 month ago)
An asian guy using calculator? *dishonor*
2 hours of lecture in my uni and I didn't understand shit, 8 min of video and I feel super confident about rsa. Thanks man you a great professor
Brent Edds (1 month ago)
I want a teacher like this
Brent Edds (1 month ago)
7:09 no [money] cookies :P
Arul Murugan (2 months ago)
Best explanation ever. Love you Eddie woo.
Jijus Chreest (2 months ago)
"Sir, is it always going to be 11?" How dumb can americans be?
asjkiea12 (1 month ago)
"How dumb can americans be?" Your edginess is very impressive. You must be very proud.
soundhar gs (3 months ago)
Oh man! The way you handled yourself is awesome and the lecture was so clear and perfect one i have ever seen!
Neil Ashworth (4 months ago)
If I had Eddie as my teacher I'd have done SO much better in math.
Tony Joseph (4 months ago)
George Henderson (4 months ago)
I figured it out in about a minute and a half.
MetraMan09 (6 months ago)
disrespectful class. have to blame the teacher on that one though... gotta coral the herd!
Arzu Arzu (6 months ago)
29 Oct. is my birthday !
Max Echendu (6 months ago)
Gets new YouTube account.. Realizes he's not subscribed to Eddie Woo the master of knowledge... Flips... Punches a hole through a wall... Calms down... Smiles... Watches video... You can continue scrolling the comments now...
Tomasz Górka (6 months ago)
Have to say this, you saved my life, that's the best explanation on the web and I have to do this as a homework for tomorrow, thanks!
Codingmaster (6 months ago)
LOL EZ FLOATS ! XD ! ( 7:38 )
Michael S (6 months ago)
Don't need calculator to do 4^11 mod 14, the nice thing about mod is you can do stuff like 4^11=4*16^5, which reduces to 4*2^5 mod 14 and now the previous calculation gives 16 mod 14 which is 2.
Ben Terry (6 months ago)
You explained clearly in 8 minutes what I couldn't fathom in a 2 hour lecture, Thank you, you're a credit to good teaching.
ali ulo (7 months ago)
I wonder if all slightly more complicated concepts could be be explained in such a lucid way, or this particular problem allows for it. Anyway, that's no all to it: my respect, Teacher:-)
Bryan Shepard (7 months ago)
The reason he got 1.99....88 instead of 2 is because of floating-point arithmetic. For a computer, the fraction 1/3 does not have an infinite number of 3's, because the computer doesn't have an infinite amount of memory. When a computer stores a number into memory, if must first allocate how much memory that number will occupy (usually a power-of-two-times-eight number of bits). Then it stores as many significant digits as it can, but most of the time this means some get chopped off at the end or rounded off. As we do math with these truncated numbers, the effect of rounding errors grows.
Mister Fister (2 months ago)
Thank you although I somewhat doubt that that is the answer as I don't think that he expects those kids to know this.
danielsan (8 months ago)
@eddie. thanks
Buda Yen (8 months ago)
You send me D
John Goh (9 months ago)
Hi Eddie is there anyway subset sum problem can be used to modify RSA?
Double Orts (9 months ago)
Bright guy
Dex Hunter (9 months ago)
Best teacher!
Defender2516 (9 months ago)
Girls if your going to talk, PLEASE LEAVE the classroom and go talk outside. Sometimes good teaching lessons are just absolutely wasted on students who don't even know why they are there.
Matt T (9 months ago)
Man... This is the definition of a good teacher. You can explain things very well and in a succinct manner. Great video!
Achmad Alfian Hidayat (9 months ago)
nice bro..
Navi Crazzy (10 months ago)
someone, please give him something to eat...
Dimitris Xatzimixail (10 months ago)
very good
PoisonedHive (10 months ago)
Eddie, you helped me pass my Codes & Codebreaking Unit at Uni. Thanks!
brbl (10 months ago)
Where did 11 come from?
Melik Can SARIYER (14 days ago)
e.d(mod6)=1 e=5 5.d(mod9)=1 d can be 5,11, 17,23,29,35 etc.
Dominic F (8 months ago)
See the 2/2 video.
ArcaneRainFell (8 months ago)
You first generate a "private key" which is 11 in the example and only then derive a "public key" from it, he just didn't get into details.
Imisambi (11 months ago)
how did you pick the numbers... 11...and 5 ..? was is related to extended euclidean algorithm..? thanks!
Imisambi (11 months ago)
just looked and saw there's part 2..!
Lambert Brother (11 months ago)
I used p=3, q=5, e=7, d=23, encrypted the message 'C' and the result was 'C'.
John Runyon (1 year ago)
You'd be awful screwed if the plaintext was O...
bobbyj joel (1 year ago)
Brilliant teacher.
Nigel Bess (1 year ago)
1:14 is now relevant on r/dankmemes
Patrick s (1 year ago)
Didn't they ban the B emoji from the sub? Edit: I'm an idiot. That's why you would want to encrypt it of course.
Dawn Ripper (1 year ago)
Uhh, can't you just multiply 299593 by 14 and see the difference between that and the original number which is 2, btw?
Tanveer Hasan (1 day ago)
i guess thats the "easier way" someone else mentioned on the video.
Aydin Akcasu (10 months ago)
That would be better, then no rounding error
Rika B. (10 months ago)
lol that's what i do xD but if you have the mod function on your calc then i guess use it
Miguel o'Hara (1 year ago)
DawnRipper that's the way I would've done it, but I think when using a calculator this ways better
Worldaviation 4K (1 year ago)
This makes more sense than some other videos that i searched for in other places with the fictional alice and bob. Proper detail like in this video with the actual numbers is far better than other videos i've seen elsewhere
thisistraightgarbage (1 month ago)
I hate Alice and Bob. I know they're a historical artifact, but they don't make the concepts any clearer.
Benny B (1 year ago)
Great video, thanks for the help! :)
pwr (1 year ago)
Brian Sy (1 year ago)
Excuse me sir Woo, is the 14 the public key? Because 5 and 11 is a private key right?
CalcuNi1256 (11 months ago)
Max Sy 14 isn’t even a real key. It’s just an extra number required to finish encryption or decryption. In the video example, (5,14) is your public key and (11,14) is your private key
Anar Key (1 year ago)
"Does that make sense... yes"... fascinating but I do struggle...
Reuben! Edmunds (1 year ago)
How would you put this into code so you could put it into a computer so it's a lot faster to decrypt and encrypt
6:40 it would be easier if you divide 4194304 by 14 which equals to 299593.14... then we take the integer part (299593) and multiply by 14 which is equal to 4194302.. and now if we subtract 4194302 from 4194304 and we get 2 which is equal to number B
Akib Mahmud (5 months ago)
What will be the calculation for (1/17) mod 60 ? ( Ans: 53)
Dawn Ripper (1 year ago)
Exactly what I was thinking!
Arjit Gupta (1 year ago)
just worked it out on 88^7 mod 187(william stalings example).... works like a charm. Thanks man
drew shepard (1 year ago)
haha exactly what i was thinking when he was doing the video. The reason he got the 1.999 is because when he did the division he got a repeating decimal and you cant really multiply a repeating decimal the calculators got to chop the number off somewhere.
you are smart guy!! Thank you very much for a nice lecture!
Eggsr2bcrushed (1 year ago)
Shame such a great teacher is stuck with students who don't seem to care or see the significance.
Abdul Basith Miah (1 year ago)
Thank you so much, Eddie Woo. This is helping me for my Uni exam next week. ;) 👍🏻👍🏻👍🏻
Hussam Ashraf (1 year ago)
would've been hella lot funnier if he wanted to send "D"
Get Ya Luv (1 year ago)
How many subjects do you teach ? like I watched your videos in 3 courses
Sahil Kale (1 year ago)
Btw the trick of finding a mod was really neat
Sahil Kale (1 year ago)
U are awesome
Jeffrey Chan (1 year ago)
Wonderful explanation.
Abdullah Buhadod (1 year ago)
Nice Video, very clear and easy to understand . Thank you so much
Liza Anzen (1 year ago)
I Wish you were my teacher :(
Amin Hussain Ali (2 years ago)
good job
Oliver Lindenskov (2 years ago)
If b=2, and then I suppose a=1, wouldn't a always encrypt to a?
SpudHead (1 year ago)
Things like this are the reason vector based padding schemes are used on top of RSA to hide stuff like that.
DrTryloByte (1 year ago)
Yes but a is not special in that regard. If you have an encrypted number you can always guess the original by trying out values. For example the encrypted B=2 in the video which was D=4 can be "decrypted" without knowing the key 11 by just trying out B=2 and seeing that (2^5) mod 14 is 4=D. In other words you can verify if your guess is correct quite easily but you cant calculate the original text without knowing 11 or guessing alot.
wadasian (1 year ago)
this is only an example, i'm not sure what is actually used, but i'm assuming ascii where a is 97, and the first proper symbol (space) is 32
obryan thorpe (2 years ago)
can you do more rsa videos
Creepy_Redstone TPR (2 years ago)
im stuck on a really comlicated problem : how the hell does ie 2 to the power of 5 become 32 i going to 7th grade and im bored of the simple boring stuff in school (maybe not simple but basic like who does want to learn about numbers lower than 0 how to multiply divide and learn %(don't know how to spell that in eng so here is the "letter") using a grid of 100 blocks) like how is that not lowering students iQ's?
Plasmaboo (1 year ago)
"to the power of", is in short, how many time you multiply the number by itself. So 2 to the power of 5 is 2*2*2*2*2=32 Not sure if you needed that, but whatever.
RFI-Crypto Lab (2 years ago)
If quantum computers ever become real, if they haven't already to the most sophisticated nation states, is it true that ALL RSA no matter the key size will be effectively broken?
JosefsensDK (2 years ago)
ECC is not under development. I use it everyday, and i bet you do too. :)
RFI-Crypto Lab (2 years ago)
HyperionNyx I wonder what the nation states brute force capability is? Do you think they could brute force AES 128? Supposedly if they have acres of super computers or purpose built systems, how many keys a second could be tested? I know it will never be revealed, but if I had to venture a guess it would be 2^80 keys per second. That is a SWAG.
HyperionNyx (2 years ago)
Quantum computers won't come for a very long time, as nations will want to keep them top-secret to secretively break encrypted text.
Nick Shields (2 years ago)
Yes, that is true. Elliptic curve cryptography is currently in development which is supposed to replace RSA when quantum computing becomes a thing.
Steven Weissenhofer (2 years ago)
Nice example to explain RSA encryption. You do one of my pet peeves though around 6:20 minutes. You write 4194304 (mod 14) = 299593.14285 etc (that is 4^11 ÷ 14) but these two things are not equal. This line needs to be deleted so equation just reads 4194304 (mod 14) = 2. Common type of mistake from students which teachers need to be wary of so as to set the right example. I wish $2 = $299593.14, I would be getting all the $2 coins I could.
Siddharth Parashar (2 years ago)
toobtuber (2 years ago)
Here's the problem I see with this: The Public Key in this case "5, 14" is only supposed to be able to encrypt and only the private "11, 14" can decode. However, the public key can decode too as follows: Cipher-text D = 4 4^5 = 1024 (mod 14) = 2 2 = B Original text.
Dominic F (8 months ago)
Marci, your maths for generating the keys is correct but you have slightly misunderstood how to use the keys. Public = (2081, 3713) Private = (1789, 3713) If I wanted to send you a message I would see your public key, and use it to encrypt the message. As you showed I could encrypt '13' to 2611, and you could decrypt it using your private key back to 13. However, if you wanted to send me something, and ensure I knew it was you, you don't 'double encrypt' by using the public key twice. You would see MY public key, encrypt your message using it, then 'sign' it using YOUR private key (not public). When I get the message, I then decrypt the signature using your PUBLIC key, then the message using my own PRIVATE key. I can know the message is from you as decrypting the signature would result in a value that makes sense. This is possible because anything encrypted with my private key can also be decrypted with my public key, in the exact same way anything encrypted with my public key can be decrypted with my private. Important here is that whichever way is used an outside party can only ever see and use my public key.
Marci Matuz (1 year ago)
It's just a coincidence because of small prime numbers. If you pick: p = 47, q = 79 ==> n = 3713 Your public key: e = 2081 -> "2081, 3713" Your private key: d = 1769 -> "1769, 3713" Suppose that you want to send an Enter (ASCI: 13) Encryption/Cipher-text: 13 ^ 2081 % 3713 = 2611 Decryption: 2611 ^ 1769 % 3713 = 13 (OK) But if you use twice your Encryption tool: 2611 ^ 2081 % 3713 = 1830 (Not OK - it isn't even a valid ASCI character)
Dev Acc (1 year ago)
They are supposed to work both ways. See challenge-response protocol for authentication: I send you a random string, you encrypt it with your private key (d) and send it back to me. Using your public key (e), I decrypt your message. If I get the original string back, your identity is confirmed (supposing you've kept your private key private ;) )
Eggsr2bcrushed (1 year ago)
simply a coincidence with these tiny numbers but real RSA uses numbers hundreds of characters long
J. Yung (2 years ago)
Nope, they should works both way. What can decrypt can be used to encrypt or vice versa
what (2 years ago)
goddammit girl what's the easy way
Bryan Shepard (7 months ago)
The easy way is to take note of the integer part after dividing by the modulus (14). Enter the original operand (4194304) and subtract the integer part of the quotient (299593). Keep subtracting again and again until the difference is less than the modulus. This seems like it's really more steps (and it is), BUT on most calculators you can just keep hitting = to repeat the last operation on the new answer. This has the added benefit of eliminating problems with floating-point arithmetic (which, btw, is why he got the answer 1.99999999999988).
Chad Zeluff (2 years ago)
+Ram Dent Just take the integer value: 299593, and multiply it by the value you're using to mod, 14. This equals 4194302. Take the original 4194304, subtract the value we calculated, and end up with 2.
681726 (2 years ago)
Maths is too hard, I'm gonna doing some yoga.
SHARIUL HASHMI (10 months ago)
nice name
ejail001 (2 years ago)
Great video, but those students are insubordinate.
Psych (1 year ago)
lul wut
Michael O'Halloran (3 years ago)
Very well explained, thanks very much for the video
gfdgdsa (3 years ago)
I don't see why you can't solve simply knowing the public key and the cyphertext. (and the algorithm). I.e.: Knowing cyphertext D (which is 4) and public key (5, 14) and of course knowing the algorithm isn't it simple to solve for x as so?: x^5 (mod 14) = 4 Or perhaps the point is that it is very difficult to figure this out when the key such as 14 can be a huge number??? On just a few tries (1-14) I could finally figure out that x=2 and break the encryption using the public key rather than private key. And even if the key could be a large number I could still (in theory) write a computer program algorithm to figure it out in any case. Might be slow but still doable in theory.
gobimage (2 years ago)
Yeah it should work in theory, eventually, but the idea is it takes like a couple lifetimes for a modern computer to figure it out when we use a 1024 bit number.
Josh Adams (2 years ago)
+gfdgdsa Zack is right. The problem lies with trying to work out the original prime numbers used to generate the Public key. It is easy to work out a solution to a problem when given two numbers that need to multiplied together. However take that same answer and hide the original two factors that made up the problem (The Private Key), and it becomes a LOT harder to work out. For example if you wanted to multiply 2348703470234 x 02398402384092 using a calculator you would get the answer 5633136002534379357117528. The calculator arrives at this conclusion almost instantly. However when presented with the following problem: ? x ? = 5633136002534379357117528, that same calculator would not be able to provide an answer. This is known as a "Factoring" problem, and in order to work out the solution the calculator or computer would need to search through all the possible numbers that could be multiplied together in order to equal that result. This may sound like it should be pretty easy, but the searching involved in working out these factors could easily take decades, and in many cases even centuries to work out. If you are still a little unsure I would recommend watching some videos on the "P vs NP" Problem. This problem explains why modern cryptography still works today, even with modern supercomputers that are capable of calculating vast amounts of mathematical possibilities every second.
PopeLando (3 years ago)
Quite right, too. I meant 300-odd digits. (doh!) :-)
gfdgdsa (3 years ago)
+PopeLando I'm rolling my eyes PopeLando
PopeLando (3 years ago)
+gfdgdsa Just for fun I've spent the last few days generating probably around 100 1024-bit (~77 decimal digit) prime numbers which I guarantee aren't on yours or anybody else's list of 'the latest prime numbers'.
Sander Verweij (3 years ago)
I dont get where the 11 comes from
Jeffrey Chan (1 year ago)
The explanation is in the part 2 of this video.
Nils Eriksson (3 years ago)
+Sander Verweij that the whole point. at around 4.40 he says that he will go thru how hard it is to calculate.
Hermoine Granger (3 years ago)
How would we encrypt a multi-lettered message? For example how would you encrypt the message "hi". Please help!
PopeLando (3 years ago)
In the real world you don't encypher messages one letter at a time. But at the same time, with 2048-bit keys you can't encrypt longer than about 250 characters at one time. So a short message would be broken up, and book-length encryption is done by only using this method to pass a normal symmetric cypher, and then use that to encrypt the big message.
PopeLando (3 years ago)
You use a much bigger number for the modulus. (With 14 you can't even encrypt the whole alphabet, let alone multiple letters!) Then you treat 'hi' as a single large number. 'h' is ASCII 72 (hex 48) and 'i' is 73 (h 49), so 'hi' is 72x256 +73 or 18,546 -which in hex is 4849, which is why we calculate it that way. Then having found a modulus n bigger than that and coprime with 5 you calculate 18546^5 mod n. This gives your encyphered result. Only you know n (and specifically the large primes used to generate n) so you can calculate the inverse of 5 mod n, called d. Then given your encyphered code c, calculate c^d mod n to get hex 4849, the word 'hi'
TheReaverOfDarkness (3 years ago)
7:36 my calculator gives me exactly 2. Yours doesn't if it isn't maintaining a proper floating point decimal.
101chorochoro (3 years ago)
He explains everything clear and simple. Thank you very much.
Lubor Hagen (3 years ago)
I am glad you post this video! Really helpfull.
Daniel my (3 years ago)
You made something that seems super hard become super easy, thank you!
Ryan Handspiker (2 years ago)
+Daniel my It is easy when dealing with small numbers. When dealing with 4096 bit primes it becomes much harder to solve.

Would you like to comment?

Join YouTube for a free account, or sign in if you are already a member.