I'm currently revising for my cryptography final year exam, and this video is the best RSA explanation I've found anywhere. Just a shame that some of his class doesn't keep quiet, they don't realise they're listening to a genius!
I enjoy the background ambience of the audience, it's normal for them to make some noise, it also makes it feel less lonely, unlike many other such videos. Eddie Woo's enthusiasm is the absolute best though!
We need more teachers like this... He's teaching faster, more accurate and more fun and energetic it sometimes doesn't even feel like he is teaching but is telling us a nice story
same, I had such an amazing teacher, but he only teaches secondary and i miss his classes now that i m doing my degree, gems like these teachers are needed at each uni or school
That is the case very often. Quite a lot of teachers/professors want to seem smarter by making their topic appear more complex than it actually is. If you understood everything and can simplify what they are saying and they react insulted, you know they're just trying to show off instead of teaching.
he kinda skipped over the most important steps like: using euclid's algorithm to solve de = 1 (mod n), fermat's little theorem and euler's theorem . There is at least half of a semester of learning about discrete math before you could truly learn RSA in a rigorous manner. Understandable for HS teaching but in uni u need to understand the proof behind things, not just the equations.
I remember studying 3 courses on Cryptography during my Masters in Theoretical Computer Science taught by a renowned research leader in the field, but I haven't seen anyone explain RSA so beautifully!
Well, he only explained a very simplified RSA. Though understanding simplified way first probably would help to understand underlying formulas and stuff better. Btw maybe he does in the next video I did not check.
@@gytisx13 No I think he leaves it at this level without going deeper that because he's teaching high schoolers. In all of Eddie's videos it seems like he struggles to dumb down his lessons as to not intimidate his young students and keep them engaged. It's sad that he's such a caring teacher that even when he tries to do that students talk during class (4:10) or give up saying it's so hard (7:54). Like he says its to complicated explain the mod calculator "trick" that takes about 2 seconds to understand. Or why the the number of coprimes of the product of two primes is just the product of 1 minus each prime (which is explained in a simple understanding of prime numbers). I feel like his highschool students not really caring is what has made him into such a great teacher. Compare that to college where the students are so compelled to learn for the high tuition or job prospects but it causes the opposite effect: professors can bullshit their lecture slides and put little to no effort into class.
@@wonderfulworldofmarkets9033 you said it's very easy to understand why the amount of coprimes with pq between 1 and pq is (p-1)(q-1) but i have tried so hard and still can't figure it out, can you explain for me why that is the case? Edit: nvm i figured it out after asking
Right? I think most teachers care more about being in power than their students learning. One time all the students in our class collected our notes and shared them on Google Drive so that we could learn Chemistry better and the teacher found out and threatened that she would fail us if we did it again. She cared more about us struggling to write down notes + pay attention rather than us learning the material and getting better grades. Compare that to Eddie who happily uploads his lectures on youtube! Sometimes the current school system / current school teachers are so backwards.
I've worked in cyber security for 10+ years and Eddie just explained RSA better than I've ever understood it. Love his style of teaching so much, it is so elegant and succinct!
For people who are wondering what happened at 11:14 The private key d is derived from the following formula: d = (k*Φ(n) + 1) / e for some integer k At step 5 instead of doing what Eddie did, I'd suggest for you to use this formula instead which is basically the same thing. The little trick here is that k has to be such an integer, that k*Φ(n) + 1%e=0 (% stands for the mathematical mod) So let us try and find k for the above example where Φ(n)=6 and e=5 if k=1, 1*6+1%e = 2 if k=2, 2*6+1%e = 3 if k=3, 3*6+1%e = 4 if k=4, 4*6+1%e = 0 if k=5, 5*6+1%e = 1 if k=6, 6*6+1%e = 2 if k=7, 7*6+1%e = 3 if k=8, 8*6+1%e = 4 if k=9, 9*6+1%e = 0 So k=9 is our answer. Notice that we did not stop at k=4, because that would give us d=5 and the idea here is that d and e cannot be the same. Hence, for k=9 d = (k*Φ(n) + 1) / e = 11.
what if we choose 17 of 11? using 17 for the secret key decrypts the message. so can there be multiple "d" for the same "e"? wouldnt that make different private keys?
You do realise that he's teaching a class of high school kids yeah? If you throw your equations at them they will be bored the hell out. Keep your explanation to the simplest form like Eddie was doing here
I'm at the end of my first semester of a cyber security degree and I just can't get over how brilliantly explained this was. There is SO much more to teaching than just dumping knowledge out there - this video should be shown to all university professors as an example of top level teaching. A wonderful teacher you are Eddie.
amazing video! shame when there are people in the class not wanting to listen and yet so many people around the world who would kill to be in their place..
well i dont completely agree his explanation is good no doubt about it but do u consider how bored the students might be ? other teachers may not be good at teaching ? they were exhausted and wanted a break but didnt get 1. So its only natural to talk with others or do something that may disturb teacher
I'm 63, worked for over 40 years in data networking, software development and project management in the telecom industry. Thanks to Mr Woo, I now understand the underlying logic of encryption/decryption. You're never to old to learn and Mr Woo is an exceptional teacher. Thank you.
Dude you jusy killed it, I learnt RSA in like 20mins which my teacher couldn't fully deliver in a 2 hours lecture. You are a really brilliant teacher and you explain stuff so well right down at the level of a student 👌👌
Currently learning network security and cryptography as one of my uni subjects. I have to say this video really helped me to understand the RSA algorithm. Brilliant teacher!
wow...... I never learned cryptography, never had any experience over higher level math. I understood every step. This is great. Very late to the party, but I like Eddie Woo's lectures
Great explanation. A shame the class was so disruptive. I would have been laser focused if I was there. It's one of my favorite clever-math things I've come across. I always revisit it from time to time.
I learned more about RSA encryption through this video than I have ever learned from any other article, book, or video. Thank you so much for making these videos!!!! Instantly subbed!!!
Eddie, this was a GREAT presentation of this, holy smokes. I'm in an online CompSci curriculum, and I had to learn this last year. The math seemed really difficult at the time, and now watching your video for a refresher as we get into SSL/TLS/RSA/HTTPS, it seems so simple! Thanks for keeping these videos up! Also I laughed my ass off "I know you think you're talking softly, but you're not talking as softly as you think you are." you're obviously a very well tempered professor who's great with students. Don't ever lose that man!
omfg how old are the students?! they should be grateful they have such an explanation before their eyes. i certainly did not learn this in highschool, and in the university there were no kids...therefore i am intrigued
I was working for hours and hours to try to get an understandable and digestable explanation of RSA and you did it for me so beautifully I couldn't have asked for more. Now 1 or 2 years later when I wanted to refresh my memory because I wanted to start working on an encryption project of my own I remember how well you explained it to me and came right back. Thank you for explaining this complex topic to me so well, and setting an amazing example for teachers everywhere.
Eddie, not only I'm learning math in a great way, I'm also learning a lot about education just by watching your videos. Keep up the awesome work you do!!
I may not aspire to become a teacher, but I am already looking up to you for the contributions your online lessons bring to us students. Keep up the good work :)
I was struggling with the various components of this algorithm, but this explanation clarified everything. Just a fantastic contribution. Thanks so much for making this!
Amazing how you explained RSA encryption to a class of high school students, and as someone who works in computer science, i have never seen this concept explained so beautifully.
Note that in this example, e=5 and d=11, but 5 and 11 are the same when used as the exponent power mod 14. That is the lock is the same as the key in this particular case (which defeats the purpose). Also, the formula for Phi (Euler's totient function) given here only works for N that is the product of 2 primes. In general, if p is the list of the prime factors of N, phi(N) = prod(p-1) * N/prod(p). Which is to say that if you factor N, phi will be the product of the unique primes minus 1, times the repeated factors. For example N=5x5x7=175, phi(N) = 4x6x5 since the 5 factor is repeated.
He's such an expressive teacher and really wants to impart all the knowledge he has. The students should be more respectful(silent) when he's working so hard for them!
The fact that this dude just dropped some major RSA knowledge bombs while simultaneously dealing with a classroom of what I presume are unruly and disrespectful college students(aka ADULTS), is amazing. This is the best cryptography video I have ever seen, hands down.
He sort of said that when he showed that d was added to the encryption formula e(mod phi(N)). What he did not explain is why d*e*(mod phi(N)) has to be 1. Also, he didn't tell them the maximum length of the message is limited to N. So, for instance, with his numbers it would not have been possible to encrypt the letter 'Z' in one step.
Gah! I'm just learning this stuff and while watching the previous video I used the proper algorithm to figure out the d, but all I could get was 5 and I couldn't figure out where he got 11. So now it turns out I was right all along! James Grime at Numberphile did the same thing - picked numbers so tiny you end up with e = d (which destroys the whole point!)
When I say I clutched my head and my mind was blown- HOLY ASDFGHJKL- ENLIGHTENMENT!! Couple more hours before my finals, and I finally get what RSA means for the very first time this entire semester!!
If you're doing it on paper, you could expect it would take a long time. Luckily, computers are REALLY good (and fast) at doing multiplication and modulo arithmetic. Using massive numbers, with the aid of a computer that has already been given the process, it shouldn't take more than a few seconds. Even with extremely massive numbers. The power of RSA comes from one thing that this brilliant teacher didn't cover in this video, and that is the fact that factoring larger and larger numbers take exponentially more time. One easy way to get the value of D is if you have de(mod phi(N)), d = e*phi(N)-1. The number 29 would work equally well as 11. We can check 5*29=145. 145/6~24.167... or 14 45 mod 6 = 1. With small numbers, there seem to be a lot of options for D. But as we'll see, the bigger we make P and Q (and by extension, phi(PQ)), the more disparate and hard-to-guess D becomes. Once you decide on prime values for P and Q, the rest of the math is trivial for a computer. But, you never tell anyone those values. They only get to know that the product of P*Q=14. Let's say you chose larger numbers, and their product is 143. It's not super hard, but it's not trivial (11 and 13). Now try 44,747,819... it's getting harder (6599 and 6781). Now try that with two prime numbers that are 400+ digits long. It will take all the computers in the world longer than the age of the Universe to figure that out... UNLESS you already know one or both of the factors! The largest known prime number has over 23 million digits. Good luck, Eve!
Why did we choose 11 as the private key? 5 seems to also do the work, but the math is easier. Did we choose it for the sake of the example, or is there another reason?
The point of RSA is an asymmetric encryption. Where sender and receiver of the message didn't have same key. If he use (5,14) for both sender and receiver will have same key. This coincident can happen because he use 2, and 7 as 'p' and 'q' for the sake of simplicity in calculation. If we use bigger prime number for 'p' and 'q', most of the time sender and receiver will have different key (asymmetrical). for example if we use (7,33) to encrypt , we can't use (7,33) to decrypt the message. let says we send B or 2. 2^7 mod 33 = 29 if we tried to decrypt using (7,33) we got : 29^7 mod 33 = 17 (it's wrong message, it should be 2). but if we use (3,33) to decrypt the message : 29^3 mod 33 = 2.
@@illiacvie I think that is not what he meant. He's not trying to use the same key, he's asking why at 11:12 he didn't chose 5 , as he went for 11. I've tried to look for an answer, but I've only found that the number "e" can be calculated with another method, but nothing on the "reasons it's a little harder to explain". Maybe it's in the extended euclidean algorithm, but that i haven't checked myself
Isn;t it weird that you can actually decrypt the cipertext with the lock. 4^5 = 1024, 1024/14 = 73.1428......, that - 73 gives 0.1425... and if you mulitiply this by 14 it gives back 2. I mean, am I the only one to notice this. It isnt a good formula or just not a good example of the RSA algorithm.
I know this comment comes from 3 years ago... But oh well I can't help to reply.. On 09:00 there's step 5, de(mod Φ(N))=1, where the value of e is already known as 5 5.d(mod 6)=1, in mod 6, every 6th step will always gives remainder of 0 So to complete 5.d(mod 6)=1 equation, we'll pick 6th step minus 1 The d value can be (6,12,18,24,30) minus 1 = 5,11,17,23,29 So the decryption key can be (5,14) or (11,14) or (17,14) and so on. To proof if above decryption keys are correct, let's calculate back: 1) key (5,14) -> 4^5 (mod 14) = 1,024-(74x14) = 2 -> (5,14) is correct 2) key (11,14) -> 4^11(mod14) = 4,194,304-(299,593x14) = 2 -> correct 3) key (17,14) -> 17,179,869,184-(1,227,133,513x14) = 2 -> correct So the conclusion is: He choose 11 because the decryption keys can be 5,11,17,23,29 Hope this helps someone in the future.. :D
@@auroraaa._. You didn't understand the question. If the keys can be any of the set {5, 11, 17...} why choose 11 versus 17, etc.? The question is: What actually defines a public versus private key? Is this arbitrary? Computational speed limit? Crypto-strength? How do you weigh this?
@@AverageJoe8686 He chose 11 over 5 (or 17) because he wants to shows that on simpler math, the key can be multiple. This happens because he used smaller number on p & q. What defines a public key? The logic is like this, when you lock your door on your house, you will always choose to use complicated one. So thieves will have longer time to break through your door, even though the thief can just use hacksaw, or TNT as 'bruteforce' way to break your lock. In real usage, the decryption key usually only has 1 or several possible key due to usage of high modulus number, on my previous comment, there's mod 6, so in every 6th thep, there will be a valid key. So if we use (for example) mod 1,000,000,000 the key is only valid for every 1,000,000,000th step. I hope you get what I mean
@@auroraaa._. You still didn't get it. 11,000th prime versus 17,000th prime. Is this arbitrary? Computational speed limit? Crypto-strength? How do you weigh this?
@@AverageJoe8686 Nowadays, the minimum acceptable crypto strength for RSA is 1024-bit, or equivalent to 80-bit symmetric key. RSA is an asymmetric system, while an example of a symmetric system is AES (Advanced Encryption Standard). The strength of RSA 1024-bit key is more or less equivalent to AES 80-bit key, it is also approximately equivalent to another encryption algorithm known as Triple DES. The 1024-bit here is not the string length, where as 'abcdef' is 6 string length. The algorithm use Base64 encoding to cope with the string length. Below is the strength equivalency between symmetric key and asymmetric key: 80 = 1024, 112 = 2048, 128 = 3072, 192 = 7680, 256 = 15360 The difficulty of breaking 112-bit compared to 80-bit strength is 2^48 times more difficult. A 80-bit key strength is recommended to be obsolete at 2010 by the National Institute of Standard and Technology (further read: csrc.nist.gov/CSRC/media/Projects/Key-Management/documents/transitions/Transitioning_CryptoAlgos_070209.pdf) RSA 512-bit can be broken by a normal 2GHz PC in about 73 days, requiring 5 GB of diskspace and 2 GB of RAM. NIST determine the obsoletion of a key strength by calculating the speed and computational power needed for a key to be broken. And also, English is not my first language, so if your question is not answered yet, perhaps you can rephrase it.
He means to share a common factor of 14 from my understanding. Because 2 is a factor of 14 and it also is a factor of 8, 10 and 12. Therefore they share a common factor. :-)
He mainly meant common factor with 2; all even numbers (here, because we are dealing with 14 = even) will share at least common factor, i.e., the number 2. Therefore, they're all eliminated.
Eddie, as a current student at university I cannot thank you enough for your clear and simple explanation. No one in the world can explain something so complex in such an easy to understand way. Cheers Pal :)
Thank you for much for explaining this. I have been wondering why prime numbers are important for RSA but couldn't find anyone using an example like this! Your students are lucky to have you!!!!
Great work Mr. Woo! I too am doing a MSc exam! Elegant explination! Very subtle behaviour management skills aswell. I hope your students recognise the fantastic teacher they have!
you can clearly see, that he himself is passionate about the things he teaches. This helps alot in bringing the point across. Have seen so many videos where they only explain the theory or explain it with an example that has very large numbers and are hard to follow. This is the best explenation of the RSA algorythm i could find on YT and i have watched a lot of videos. Great teacher. He is not getting the attention he deserves for his genious.
Eddie, I love the passion you bring to your classroom [and your videos]! I ran into an issue with your explanation: if the modulus < number of characters in the set of possible characters being encoded, the decryption will not return the original character since the modulus 'repeats'. So if you're encoding the upper alphabet (A - Z), the modulus would have to be 31. Also, if the modulus results in a zero or one remainder, your resulting encryption/decryption will be either a zero or a one (raise zero and one to a power and the result is zero or one, respectively). Try encrypting/decrypting 'hello'; the decrypt comes as 'hella' since the letter 'o' is the 15th letter. The public key (5,14) encrypt produces a remainder of 1. The decrypt of 1 is also 1.
Mate, I've been using RSA for my entire career and never bothered to learn the maths behind it, thinking it'll be a waste of time. Thanks to your video, now I know it's not impossible to comprehend. Thanks!
my doctor explains this in a 3 hours lecture and i can't see the big picture of the algorithm or where these numbers are exactly come from, you are amazing thank you 😄
This is incredibly useful. I'm a grade 9 student who needed to get a refresher on RSA for a school thing, and this vide was simple enough that I could easily understand it.
Hi Mr. Thadeus, i'm Enoch. I'm not good at English but i really like Cryptography, i found these videos are highly helpful so i watched these by reading the English subtitles and translate to my language where necessary. Unfortunately there're not subtitles, so could you please help me to add subtitles on this video? Thanks
If you can't explain it simply, you don't understand it well enough....Albert Einstein Clearly, you nailed the topic as this is the simplest, most intuitive and most elegant explanation I have seen so far.
Defenitely he is the best instructor, I'm here because of my java communication encryption homework for MSc CSE. Greetings from Hungary! :) Keep it up!
One of the greatest lessons which I have watched. Good luck!!! I could easily understand the main concept of this algorithm. Thank you so much for your brilliant explanation absolutely free !!!
I'm currently revising for my cryptography final year exam, and this video is the best RSA explanation I've found anywhere. Just a shame that some of his class doesn't keep quiet, they don't realise they're listening to a genius!
+Billy Rebecchi its realy good to watch some one explaining things in this manner ...
Billy Rebecchi agreed
me too preparing for final exam...
Not for a final, but I used this so i can test out my program to see if it was written correctly.
I enjoy the background ambience of the audience, it's normal for them to make some noise, it also makes it feel less lonely, unlike many other such videos. Eddie Woo's enthusiasm is the absolute best though!
4:10 "I KNOW you think you are talking softly. You are not talking softly" LOL ROASTED
7:50 "Is it really that hard? :(" This dude just casually destroying kids while teaching RSA, amazing.
He might be saying "Is it really that hard to STFU?"
such a smooth way to burn
@@Subtitles00 That was encrypted message for "Stfu bit*h!". Only people with some processing power are able to decipher such messages.
Obviously this class has mentally challenged people who should not be there.
We need more teachers like this...
He's teaching faster, more accurate and more fun and energetic it sometimes doesn't even feel like he is teaching but is telling us a nice story
That's how it is when a teacher is actually passionate about what they're teaching. :P
Feels like he is teaching to me. The whiteboard is a giveaway
I want to go to this secondary school instead of my university. lol
same, I had such an amazing teacher, but he only teaches secondary and i miss his classes now that i m doing my degree, gems like these teachers are needed at each uni or school
wait, its a secondary school?
@@tanveerhasan2382 yh
what? secondary school, learning rsa wtf? Some people are so lucky. Damn i wish i had that in my school
I fell u bro
You're an exceptionally talented teacher. Thank you
Yeah hes great
"Every sixth multiple is a multiple of sixth"
Genius
Starting to think the concepts in my uni lectures are probably actually quite simple, just the delivery is horrible.
same
That is the case very often. Quite a lot of teachers/professors want to seem smarter by making their topic appear more complex than it actually is.
If you understood everything and can simplify what they are saying and they react insulted, you know they're just trying to show off instead of teaching.
I am in a cryptography class right now, and this is literally the easiest explanation I have found... I agree with you 100%
Academic institutions make a profit off making things seem more difficult than they are
he kinda skipped over the most important steps like: using euclid's algorithm to solve de = 1 (mod n), fermat's little theorem and euler's theorem . There is at least half of a semester of learning about discrete math before you could truly learn RSA in a rigorous manner. Understandable for HS teaching but in uni u need to understand the proof behind things, not just the equations.
I remember studying 3 courses on Cryptography during my Masters in Theoretical Computer Science taught by a renowned research leader in the field, but I haven't seen anyone explain RSA so beautifully!
if Eddie Woo explains it better than your teacher, than Eddie is the leader in the Theoretical Computer Science.
Well, he only explained a very simplified RSA. Though understanding simplified way first probably would help to understand underlying formulas and stuff better.
Btw maybe he does in the next video I did not check.
@@gytisx13 No I think he leaves it at this level without going deeper that because he's teaching high schoolers. In all of Eddie's videos it seems like he struggles to dumb down his lessons as to not intimidate his young students and keep them engaged. It's sad that he's such a caring teacher that even when he tries to do that students talk during class (4:10) or give up saying it's so hard (7:54).
Like he says its to complicated explain the mod calculator "trick" that takes about 2 seconds to understand. Or why the the number of coprimes of the product of two primes is just the product of 1 minus each prime (which is explained in a simple understanding of prime numbers).
I feel like his highschool students not really caring is what has made him into such a great teacher. Compare that to college where the students are so compelled to learn for the high tuition or job prospects but it causes the opposite effect: professors can bullshit their lecture slides and put little to no effort into class.
@@wonderfulworldofmarkets9033 you said it's very easy to understand why the amount of coprimes with pq between 1 and pq is (p-1)(q-1) but i have tried so hard and still can't figure it out, can you explain for me why that is the case?
Edit: nvm i figured it out after asking
I'd trade ten of my current professors to get you to teach me.
lol
Right? I think most teachers care more about being in power than their students learning. One time all the students in our class collected our notes and shared them on Google Drive so that we could learn Chemistry better and the teacher found out and threatened that she would fail us if we did it again. She cared more about us struggling to write down notes + pay attention rather than us learning the material and getting better grades. Compare that to Eddie who happily uploads his lectures on youtube! Sometimes the current school system / current school teachers are so backwards.
I've worked in cyber security for 10+ years and Eddie just explained RSA better than I've ever understood it. Love his style of teaching so much, it is so elegant and succinct!
For people who are wondering what happened at 11:14
The private key d is derived from the following formula:
d = (k*Φ(n) + 1) / e for some integer k
At step 5 instead of doing what Eddie did, I'd suggest for you to use this formula instead which is basically the same thing.
The little trick here is that k has to be such an integer, that k*Φ(n) + 1%e=0
(% stands for the mathematical mod)
So let us try and find k for the above example where Φ(n)=6 and e=5
if k=1, 1*6+1%e = 2
if k=2, 2*6+1%e = 3
if k=3, 3*6+1%e = 4
if k=4, 4*6+1%e = 0
if k=5, 5*6+1%e = 1
if k=6, 6*6+1%e = 2
if k=7, 7*6+1%e = 3
if k=8, 8*6+1%e = 4
if k=9, 9*6+1%e = 0
So k=9 is our answer. Notice that we did not stop at k=4, because that would give us d=5
and the idea here is that d and e cannot be the same.
Hence, for k=9
d = (k*Φ(n) + 1) / e = 11.
Thank you very much, I need it for a Covid App and your explanation was very useful!! 😁
what if we choose 17 of 11? using 17 for the secret key decrypts the message. so can there be multiple "d" for the same "e"? wouldnt that make different private keys?
You do realise that he's teaching a class of high school kids yeah? If you throw your equations at them they will be bored the hell out. Keep your explanation to the simplest form like Eddie was doing here
how can we apply this for huge numbers, we can't cycle through millions of possibilities when e is too long, it'll take way too much time
thanks, also does using extended euclidean algorithm have similar pattern?
Finally. 40 years old and today I just understood exactly how RSA works, how and why the math actually works. Thank you!
Best explanation on youtube
exactly!!!!
His enthusiasm is extrodinary and his delivery is second to none. A genius in understanding material, and teaching! You've got a bright future!
Man you're brilliant. Make some online courses and world will be better !
I'm at the end of my first semester of a cyber security degree and I just can't get over how brilliantly explained this was. There is SO much more to teaching than just dumping knowledge out there - this video should be shown to all university professors as an example of top level teaching. A wonderful teacher you are Eddie.
amazing video! shame when there are people in the class not wanting to listen and yet so many people around the world who would kill to be in their place..
I agree
well i dont completely agree
his explanation is good no doubt about it
but
do u consider how bored the students might be ? other teachers may not be good at teaching ? they were exhausted and wanted a break but didnt get 1. So its only natural to talk with others or do something that may disturb teacher
@@silverzero9524 Thats all assumption. Why are you speaking for them 😂
So trueee!
In uni and have a professor who sits and reads verbatim from slides for an hour. I would love to have someone as enthusiastic as Eddie teach me.
Whenever I can't figure out a math concept, I look for an Eddie Woo video on it. You are an excellent teacher, sir.
I'm 63, worked for over 40 years in data networking, software development and project management in the telecom industry. Thanks to Mr Woo, I now understand the underlying logic of encryption/decryption. You're never to old to learn and Mr Woo is an exceptional teacher. Thank you.
Dude you jusy killed it, I learnt RSA in like 20mins which my teacher couldn't fully deliver in a 2 hours lecture.
You are a really brilliant teacher and you explain stuff so well right down at the level of a student 👌👌
Currently learning network security and cryptography as one of my uni subjects. I have to say this video really helped me to understand the RSA algorithm. Brilliant teacher!
2 of 2? I feel robbed! We were getting to all of the good stuff. :(
The best explanation to RSA that I've seen. Thank you!
This man is such an amazing teacher I'm literally sitting here being awestruck about how great he is at explaining this topic.
Eddie, you are the best teacher that I have seen in my life, I started my career as CS Teacher with Asia' s largest school.
wow...... I never learned cryptography, never had any experience over higher level math.
I understood every step. This is great.
Very late to the party, but I like Eddie Woo's lectures
honestly, this guy is easily in the top 1% of teachers. if hes being paid accordingly, i.e. he should be earning millions IMO.
Great explanation. A shame the class was so disruptive. I would have been laser focused if I was there. It's one of my favorite clever-math things I've come across. I always revisit it from time to time.
"is it really that hard? " *sad and kinda disapointed face*
Nothing sadder than a sad Eddie ☹️
I thought a thug life meme would start at that point
aw :c
did someone leave? or was a student talking again?
I thought the student was talking again
You're an amazing math teacher.
I learned more about RSA encryption through this video than I have ever learned from any other article, book, or video. Thank you so much for making these videos!!!! Instantly subbed!!!
Eddie, this was a GREAT presentation of this, holy smokes. I'm in an online CompSci curriculum, and I had to learn this last year. The math seemed really difficult at the time, and now watching your video for a refresher as we get into SSL/TLS/RSA/HTTPS, it seems so simple! Thanks for keeping these videos up! Also I laughed my ass off "I know you think you're talking softly, but you're not talking as softly as you think you are." you're obviously a very well tempered professor who's great with students. Don't ever lose that man!
What a power in your deliver :) luvd it
omfg how old are the students?! they should be grateful they have such an explanation before their eyes.
i certainly did not learn this in highschool, and in the university there were no kids...therefore i am intrigued
Students are teenagers. This is high school
When you're a teenager, you got more important things to worry about than coprime numbers and modular arithmetics :)
dawg you assume everyone on earth has the same mindset/priorities as you do lmao. you have the benefit of hindsight
@@ArtyomPalvelev Oh yeah I am sure they are discussing vital issues much more important than their education. Give me a break.
@@ArtyomPalvelev poor mentality
I was working for hours and hours to try to get an understandable and digestable explanation of RSA and you did it for me so beautifully I couldn't have asked for more. Now 1 or 2 years later when I wanted to refresh my memory because I wanted to start working on an encryption project of my own I remember how well you explained it to me and came right back. Thank you for explaining this complex topic to me so well, and setting an amazing example for teachers everywhere.
Eddie, not only I'm learning math in a great way, I'm also learning a lot about education just by watching your videos. Keep up the awesome work you do!!
Eddie you're a great man. You made my life so much easier. Thank you for this!
I may not aspire to become a teacher, but I am already looking up to you for the contributions your online lessons bring to us students. Keep up the good work :)
I was struggling with the various components of this algorithm, but this explanation clarified everything. Just a fantastic contribution. Thanks so much for making this!
Amazing how you explained RSA encryption to a class of high school students, and as someone who works in computer science, i have never seen this concept explained so beautifully.
Note that in this example, e=5 and d=11, but 5 and 11 are the same when used as the exponent power mod 14. That is the lock is the same as the key in this particular case (which defeats the purpose).
Also, the formula for Phi (Euler's totient function) given here only works for N that is the product of 2 primes. In general, if p is the list of the prime factors of N, phi(N) = prod(p-1) * N/prod(p). Which is to say that if you factor N, phi will be the product of the unique primes minus 1, times the repeated factors. For example N=5x5x7=175, phi(N) = 4x6x5 since the 5 factor is repeated.
He's such an expressive teacher and really wants to impart all the knowledge he has. The students should be more respectful(silent) when he's working so hard for them!
I was thinking the exactly same.
The fact that this dude just dropped some major RSA knowledge bombs while simultaneously dealing with a classroom of what I presume are unruly and disrespectful college students(aka ADULTS), is amazing. This is the best cryptography video I have ever seen, hands down.
The best lecturer I have ever seen... Thank you so much sir. I am so happy
Thank you so much. I thought I would never ever understand this
thank you so much i understood every word you said
You did an incredible job explaining this concept, thank you so much! I wish there were more teachers like you.
What a briliant explanation! I can't believe, some of the students did not listen carefully, you're an amazing teacher!
I think it's worth to note that d is a multiplicative inverse of e mod (p-1)(q-1)
He sort of said that when he showed that d was added to the encryption formula e(mod phi(N)). What he did not explain is why d*e*(mod phi(N)) has to be 1.
Also, he didn't tell them the maximum length of the message is limited to N. So, for instance, with his numbers it would not have been possible to encrypt the letter 'Z' in one step.
@@iycgtptyarvg why not? If my N is 247. What is the highest number I can encrypt/decrypt?
@@MrNoxiium [0,246]. But, with his numbers you cannot do more than [0,13].
How can you talk in his class!! You teach beautifully Eddie!
These kids are being spoiled lol my prof in college can't explain anything in 90 minutes yet I feel comfortable about RSA with you :) thank you!
Watching in 2020! Even I'm annoyed AF at the talking student(s). This explanation was amazingly easy to follow, thank you!!
Gah! I'm just learning this stuff and while watching the previous video I used the proper algorithm to figure out the d, but all I could get was 5 and I couldn't figure out where he got 11. So now it turns out I was right all along! James Grime at Numberphile did the same thing - picked numbers so tiny you end up with e = d (which destroys the whole point!)
Eddie Woo, the man, the myth, the legend... he is the lord of this mathematical world, a deity among mere mortals... we love you Eddie, we love you.
Nerd
When I say I clutched my head and my mind was blown-
HOLY ASDFGHJKL-
ENLIGHTENMENT!! Couple more hours before my finals, and I finally get what RSA means for the very first time this entire semester!!
Man, you are a life saver... i don't care how old this video is it still holds up. thank you for such an awesome explanation
Such a complicated thing made simple !
QuantuMuffin yes
I have a few questions:
1. Why do we need to pick e between 1 and Φ(N)?
2. Why when we find d, it's found in such a way that de mod Φ(N) = 1?
Eddie makes math easy and the communication is impeccable. well done!!
Thank you very much for this upload, sir. This is by far the best explanation of the RSA algorithm. It all makes sense finally.
"... one times six, whaaaaat" :D
how do you check if your chosen e and d fulfill these criteria for insanely large numbers tho?
If you're doing it on paper, you could expect it would take a long time. Luckily, computers are REALLY good (and fast) at doing multiplication and modulo arithmetic. Using massive numbers, with the aid of a computer that has already been given the process, it shouldn't take more than a few seconds. Even with extremely massive numbers. The power of RSA comes from one thing that this brilliant teacher didn't cover in this video, and that is the fact that factoring larger and larger numbers take exponentially more time.
One easy way to get the value of D is if you have de(mod phi(N)), d = e*phi(N)-1. The number 29 would work equally well as 11. We can check 5*29=145. 145/6~24.167... or 14 45 mod 6 = 1. With small numbers, there seem to be a lot of options for D. But as we'll see, the bigger we make P and Q (and by extension, phi(PQ)), the more disparate and hard-to-guess D becomes.
Once you decide on prime values for P and Q, the rest of the math is trivial for a computer. But, you never tell anyone those values. They only get to know that the product of P*Q=14. Let's say you chose larger numbers, and their product is 143. It's not super hard, but it's not trivial (11 and 13). Now try 44,747,819... it's getting harder (6599 and 6781). Now try that with two prime numbers that are 400+ digits long. It will take all the computers in the world longer than the age of the Universe to figure that out... UNLESS you already know one or both of the factors! The largest known prime number has over 23 million digits. Good luck, Eve!
Incredible teacher, with real passion and energy. Eddie really enjoys the job. Thank you for the excellent lecture.
I am very bad at maths and have been trying to get my head around RSA for ages and this video is what made it click for me. Thank you!
Why did we choose 11 as the private key? 5 seems to also do the work, but the math is easier. Did we choose it for the sake of the example, or is there another reason?
The point of RSA is an asymmetric encryption. Where sender and receiver of the message didn't have same key.
If he use (5,14) for both sender and receiver will have same key.
This coincident can happen because he use 2, and 7 as 'p' and 'q' for the sake of simplicity in calculation.
If we use bigger prime number for 'p' and 'q', most of the time sender and receiver will have different key (asymmetrical).
for example if we use (7,33) to encrypt , we can't use (7,33) to decrypt the message.
let says we send B or 2.
2^7 mod 33 = 29
if we tried to decrypt using (7,33) we got : 29^7 mod 33 = 17 (it's wrong message, it should be 2).
but if we use (3,33) to decrypt the message : 29^3 mod 33 = 2.
@@illiacvie I think that is not what he meant. He's not trying to use the same key, he's asking why at 11:12 he didn't chose 5 , as he went for 11.
I've tried to look for an answer, but I've only found that the number "e" can be calculated with another method, but nothing on the "reasons it's a little harder to explain". Maybe it's in the extended euclidean algorithm, but that i haven't checked myself
Isn;t it weird that you can actually decrypt the cipertext with the lock. 4^5 = 1024, 1024/14 = 73.1428......, that - 73 gives 0.1425... and if you mulitiply this by 14 it gives back 2. I mean, am I the only one to notice this. It isnt a good formula or just not a good example of the RSA algorithm.
This is the most understandable explanation of RSA I've found. Thank you!
This is the best explanation of RSA I've seen yet. Great work!
but in that case, we could have many decryption keys. ain't it?
Sorry why did you pick the 11 again? tHANKS
I know this comment comes from 3 years ago... But oh well I can't help to reply..
On 09:00 there's step 5, de(mod Φ(N))=1, where the value of e is already known as 5
5.d(mod 6)=1, in mod 6, every 6th step will always gives remainder of 0
So to complete 5.d(mod 6)=1 equation, we'll pick 6th step minus 1
The d value can be (6,12,18,24,30) minus 1 = 5,11,17,23,29
So the decryption key can be (5,14) or (11,14) or (17,14) and so on.
To proof if above decryption keys are correct, let's calculate back:
1) key (5,14) -> 4^5 (mod 14) = 1,024-(74x14) = 2 -> (5,14) is correct
2) key (11,14) -> 4^11(mod14) = 4,194,304-(299,593x14) = 2 -> correct
3) key (17,14) -> 17,179,869,184-(1,227,133,513x14) = 2 -> correct
So the conclusion is: He choose 11 because the decryption keys can be 5,11,17,23,29
Hope this helps someone in the future.. :D
@@auroraaa._. You didn't understand the question. If the keys can be any of the set {5, 11, 17...} why choose 11 versus 17, etc.?
The question is: What actually defines a public versus private key? Is this arbitrary? Computational speed limit? Crypto-strength? How do you weigh this?
@@AverageJoe8686 He chose 11 over 5 (or 17) because he wants to shows that on simpler math, the key can be multiple. This happens because he used smaller number on p & q.
What defines a public key?
The logic is like this, when you lock your door on your house, you will always choose to use complicated one. So thieves will have longer time to break through your door, even though the thief can just use hacksaw, or TNT as 'bruteforce' way to break your lock.
In real usage, the decryption key usually only has 1 or several possible key due to usage of high modulus number, on my previous comment, there's mod 6, so in every 6th thep, there will be a valid key.
So if we use (for example) mod 1,000,000,000 the key is only valid for every 1,000,000,000th step.
I hope you get what I mean
@@auroraaa._. You still didn't get it.
11,000th prime versus 17,000th prime. Is this arbitrary? Computational speed limit? Crypto-strength? How do you weigh this?
@@AverageJoe8686 Nowadays, the minimum acceptable crypto strength for RSA is 1024-bit, or equivalent to 80-bit symmetric key.
RSA is an asymmetric system, while an example of a symmetric system is AES (Advanced Encryption Standard).
The strength of RSA 1024-bit key is more or less equivalent to AES 80-bit key, it is also approximately equivalent to another encryption algorithm known as Triple DES.
The 1024-bit here is not the string length, where as 'abcdef' is 6 string length. The algorithm use Base64 encoding to cope with the string length.
Below is the strength equivalency between symmetric key and asymmetric key:
80 = 1024, 112 = 2048, 128 = 3072, 192 = 7680, 256 = 15360
The difficulty of breaking 112-bit compared to 80-bit strength is 2^48 times more difficult.
A 80-bit key strength is recommended to be obsolete at 2010 by the National Institute of Standard and Technology (further read: csrc.nist.gov/CSRC/media/Projects/Key-Management/documents/transitions/Transitioning_CryptoAlgos_070209.pdf)
RSA 512-bit can be broken by a normal 2GHz PC in about 73 days, requiring 5 GB of diskspace and 2 GB of RAM.
NIST determine the obsoletion of a key strength by calculating the speed and computational power needed for a key to be broken.
And also, English is not my first language, so if your question is not answered yet, perhaps you can rephrase it.
Stumble into this, by accident. Wow, what a good teacher you are. Definitely brilliant explanation.
If I took your class I would pay SUCH close attention because you are amazing at explaining things!
Tell those students to shutup!
Did he mean a common factor with 2 and 7? How are 8 / 10 / 12 a common factor of 14?
He means to share a common factor of 14 from my understanding. Because 2 is a factor of 14 and it also is a factor of 8, 10 and 12. Therefore they share a common factor. :-)
Thanks a lot mate!
I also did not understand what he meant to say. Perhaps, +Eddie Woo can make it clear.
He mainly meant common factor with 2; all even numbers (here, because we are dealing with 14 = even) will share at least common factor, i.e., the number 2. Therefore, they're all eliminated.
Aparna Mahalingam where does q=7 came from couldnt follow it.
Thank you for the video. My teacher at CIT just read a PowerPoint slide with no explanation. Now I can understand the whole procedure.
Eddie, as a current student at university I cannot thank you enough for your clear and simple explanation. No one in the world can explain something so complex in such an easy to understand way. Cheers Pal :)
Thank you for much for explaining this. I have been wondering why prime numbers are important for RSA but couldn't find anyone using an example like this! Your students are lucky to have you!!!!
Great work Mr. Woo! I too am doing a MSc exam! Elegant explination! Very subtle behaviour management skills aswell. I hope your students recognise the fantastic teacher they have!
This (and part 1 as well) are maybe the best vids I have seen on TH-cam!
This is hands-down the best explanation of RSA in existence. Amazing.
you can clearly see, that he himself is passionate about the things he teaches. This helps alot in bringing the point across. Have seen so many videos where they only explain the theory or explain it with an example that has very large numbers and are hard to follow. This is the best explenation of the RSA algorythm i could find on YT and i have watched a lot of videos. Great teacher. He is not getting the attention he deserves for his genious.
Eddie, I love the passion you bring to your classroom [and your videos]! I ran into an issue with your explanation: if the modulus < number of characters in the set of possible characters being encoded, the decryption will not return the original character since the modulus 'repeats'. So if you're encoding the upper alphabet (A - Z), the modulus would have to be 31. Also, if the modulus results in a zero or one remainder, your resulting encryption/decryption will be either a zero or a one (raise zero and one to a power and the result is zero or one, respectively). Try encrypting/decrypting 'hello'; the decrypt comes as 'hella' since the letter 'o' is the 15th letter. The public key (5,14) encrypt produces a remainder of 1. The decrypt of 1 is also 1.
Mate, I've been using RSA for my entire career and never bothered to learn the maths behind it, thinking it'll be a waste of time. Thanks to your video, now I know it's not impossible to comprehend. Thanks!
Got this video recommended to me and I managed to finally get the hang of it you're an amazing teacher
my doctor explains this in a 3 hours lecture and i can't see the big picture of the algorithm or where these numbers are exactly come from, you are amazing thank you 😄
Most enthusiastic teacher i ever seen!! Awesome Explanation.
Simply amazing. What a teacher he is. The energy and the explanation. uff.
Best tutorial on the process of RSA. THANKS Mr Eddie Woo!
This is incredibly useful. I'm a grade 9 student who needed to get a refresher on RSA for a school thing, and this vide was simple enough that I could easily understand it.
The procedure is better explained than in my university handouts. Thank you, this short video helped me a lot!
Excellent, interesting and rather fun explanation. Very clear - Thank you so much for posting. I'm glad I found your channel Professor Woo
Thanks very much. Excellent. Your vid answered fundamental questions about PGP that other vids did not provide.
Oh man! The way you handled yourself is awesome and the lecture was so clear and perfect one i have ever seen!
Hi Mr. Thadeus, i'm Enoch. I'm not good at English but i really like Cryptography, i found these videos are highly helpful so i watched these by reading the English subtitles and translate to my language where necessary. Unfortunately there're not subtitles, so could you please help me to add subtitles on this video? Thanks
Big respect to this Teacher. Excellent explanation. Thanks, Sir for sharing such a great explanation with us.
I was sleepy... but now I am not. They way he delivered such a complex topic in an interesting and exciting way, AWESOME !
Ive never been taught by such a passionate teacher/professor as you!
Seriously the best explanation of RSA I've seen.
If you can't explain it simply, you don't understand it well enough....Albert Einstein
Clearly, you nailed the topic as this is the simplest, most intuitive and most elegant explanation I have seen so far.
Defenitely he is the best instructor, I'm here because of my java communication encryption homework for MSc CSE. Greetings from Hungary! :) Keep it up!
One of the greatest lessons which I have watched. Good luck!!! I could easily understand the main concept of this algorithm. Thank you so much for your brilliant explanation absolutely free !!!