Public Key Cryptography: RSA Encryption Algorithm
HTML-код
- Опубликовано: 9 июн 2024
- RSA Public Key Encryption Algorithm (cryptography). How & why it works. Introduces Euler's Theorem, Euler's Phi function, prime factorization, modular exponentiation & time complexity.
Link to factoring graph: www.khanacademy.org/labs/explo...
my brain is running at 100% CPU usage watching this video
Mine's overclocked ;)
thabg007 editing this video almost killed me...
My mind blew up whole watching this, I don't have a brain anymore
+thabg007 You could hear the fans going full speed in mine.
+thabg007 Maybe it needs a Windows update.
Possibly the best explanation of anything on the Internet.
Thanks Aalap, I hope to try and match this video with the upcoming one on P vs. NP
agree
by sure
Yes, it explains such a complex topic very easily, hands up 🙌
God the people that came up with this thing are surely geniuses, can't but feel idiotic after watching this.
TheSleyths i feel like that all the time during my studies
+TheSleyths +1
Constantly feeling like that since I started digging into computer science.
No kidding. The R in RSA is the same R in CLRS, the most widely-referenced algorithms textbook in existence, which almost all top computer science universities use in their algorithms curriculum.
+The Sleyths Perhaps... & perhaps not.
Recall that during WW2 scientists did a test on the atomic bomb underneath Wrigley Field. They dropped a cylinder of radioactive material through more such, with a hole in it. The test was successful: the temperature in the room immediately rose ~20 degrees as predicted, since for a brief period the uranium had reached critical mass. They were "smart."
Factoring is tough, but let me tell you something: every math problem was unsolved through the very day before it was solved.
The US Government has made it clear they do not like having public codes which they are not privy to. What do you think would happen if they discovered an easy factoring technique: would they announce it to the World? Or keep it secret so that they could read everyone's messages?!
Admirable how simply you worked through explaining it all. Beautifully done, both the delivery and the accompanying graphics and animation
+Art of the Problem question, at 13:43, which component is the chosen color, and which one is the "complement" color?
This is an amazingly well laid out video that is far easier to digest than learning it the math way. I wish it was around 20 years ago! I've never seen it's equal that shows the multiple ways - color mixing, private, secret, pre-shared, AND the underlying various encryption schemes/history in such an understandable manner! Well Done!
at 14:14 did you put the value of k randomly. so if i put k=1 or k=5 i will have different values of d(decription key), will i get the same value of m(message)when using the decription key d?
@@arfcommer15 The "math way" is clearer than this. This video glosses over many important details
10 years old? Wow better quality than most videos today. Well done :)
should be some law stating that any and all education must be presented in a manner equal to or greater than the quality of this video.
This is mind bogglingly powerfully simple! I’m impressed! I’m working on integration with a DSS system right now and also reading a book Introduction to Algoryhms third edition by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein.
I’m currently reading about Ferma theorem and coming up to the internals of RSA. This video is mighty and impressive! One of the masterpieces of explanation of very complex algorithms is a clear and approachable way. Thank you for it!
Right! I paid $15,000 a semester and I learned more in 16 minutes and 30 seconds than I did in 13 weeks.
Best explanation anywhere! Bravo, signore!
@@dapdizzy lol oki
remember watching these on khan academy when i was in elementary school and am now taking cryptography as an upper level math class in university. these videos were ahead of their time and the explanation is still at a gold standard
that's SO cool to hear, love this story, thanks for sharing...i remember when I made this video it feels like another era
New video is up on Evolution of Intelligence ruclips.net/video/5EcQ1IcEMFQ/видео.html
I might be late to the party but thanks a bunch for this awesome explanation! These 17 minutes were more effective than 2 hours of lecture at my university.
awesome that was the goal!
Outstanding explanation with one frustrating defect: throwing 'k' in with absolutely no mention of how to obtain it. Getting the right k is essential for calculating d.
calculation of k is not entirely necessary. we can take the bezout relation of e and phi(n) as our d value, or use the extended euclidean algorithms to calculate it.
yes, it's right. d is a multiplicative inverse of e mod phi(n)
can someone please explain in simple terms how we get k, I need it for a project
(ed - 1) = k*phi(N) for some integer k, we don't really need to know what k is since we just obtain that cluster by doing (ed - 1). (According to a book on this subject).
Agreed. That was glossed over. As I understand it, because of the repeating nature of the mod function, k can be anything you want, just to add a bit of randomness into the key.
Hopefully I can post a link to another video here, as choosing d and e is better explained here, IMO: ruclips.net/video/oOcTVTpUsPQ/видео.html
Heck of a video, I've watched around 5 times now.
glad it was helpful for you - stay tuned for more!
Wow what a great way to convey such a difficult subject of cryptography in such a comprehensive yet understandable way.
Such a nice explanation,thank you very much
16:05 That was me with the rock after watching this video
One of the finest videos to explain the beauty of cryptology and hence prove the magic of prime numbers
This is absolutely the best exposition of public key, for me at this point.
glad you found it
This is gold. I can’t image how much work it must have involved. I appreciate your work greatly
it was an epic video to great, I put everything I had into it :)
This was just what I was looking for, and very good up until 12:00. Then I had to watch it a couple times, and fill in a couple intermediate math steps that were glossed over, but now I got it. It also helps to know the rules for picking d and e, which are better covered in other videos (explains why k is there and why he could magically replace it with 2, for instance).
I'm stuck. Which other videos?
This is the 'n' time I've come back for this explanation, and every time I watch it I am nothing short of amazed. Kudos to Art of the Problem!!!
thanks david, happy to have you around. love to see it aged well
This is by far the best explanation of RSA Encryption I've ever seen. I really like how you actually explained the algorithms and how it was derived.
I saw a few people asked about where the k=2 comes from around 14:22. I spent a while trying to figure this out myself so I thought I would share. Rather than guess a k, the better way to solve for d is to find the modular inverse d= e^-1 mod phi(n). I found a python script that could do this quickly and allowed me to solve for d easily. It also allows you to make sure that the gcd of e and phi n are is one. That is necessary. en.wikipedia.org/wiki/Multiplicative_modular_inverse
Oh and I also should say that is an awesome video and I am very grateful that you took the time to make this. It really is an amazing piece of work. Thanks!
Max Roth but how to find k if you don't have the 'd'?
Ruben Verbrugghe That is exactly what I mentioned in the comment. It is the Multiplicative Modular Inverse. d= e^-1 mod phi(n). Here is where I found a python script to find this. It is algorithmic which means it is not easy to solve by hand.
en.wikibooks.org/wiki/Algorithm_Implementation/Mathematics/Extended_Euclidean_algorithm
I will check it out tomorow thx for the fast respons buddy!
Hi, I would just like to ask you, where exactly does the d=e^-1 mod phi (n) originate from?
Brother help me out please! There's a mistake in his calculation in the last example and this is driving me INSANE, I really hope I'm missing something here, but listen:
if....
c=1394
n=3127
d=2011
now plug them in the equation: c^d mod n=m and it's supposed to come out to 89.
However, using a calculator: 1394^2011 mod 3127 = 1506
Click on this link to see the calculation:
calculatorpi.com/c?a=mod%281394**2011%2C+3127%29&submit=+++Calculate+++&b=#here
What is going on.... ????
Watching videos as such, makes me believe in RUclips Gods.
This is probably the best explanation I've seen yet as to how this works - it's always boggled my mind when I start thinking about numbers that large, and I'm no slouch at math.
I'd like to take the opportunity to thank those who kindly put the time and effort to do this MAGNIFICENT video. EVERYTHING is extremely well thought, done and said. Kudos to you "Art of the Problem". Cheers
Fantastic video for figuring out how public key/private key work.
This video is really an Art- You really have the Art of Teaching with conceptual depth!
I have a video suggestion: Please do a video on Elliptic Curve Cryptography.
This video is by far the most elegant and easy to understand explanation of RSA encryption I've seen. Thank you.
Both the way in which this is explained and the style of the video are beyond amazing. Thank you!
Incredibly well explained, it was magical. Thank you!
This is just one of the greatest crypto related videos out on web (with an excellent timing of bg theme changes :))
The best explanation of cryptography that I have seen on the internet.
mind = BLOWN
even though I couldnt catch up with every single point and calculation, at the end when all the pieces came together my mind was blown. thank you so much for this brilliant video, my network security final is in 4 days hehehe
excellent so clear to hear it
In engineering, I have learnt encryption and deception in details, but this video explains those concepts in great details.
made this for people like you
@@ArtOfTheProblem thanks a lot! i hope u get what u expect sharing such useful informations
This is so beautiful, pure consciousness at work. Its implications will soon be felt by everyone, as cryptography is the way out of all tyranny, oppression and unaccountable government's overreach.
Nice description. In fact, Phi function is only multiplicative for factors that are coprime (don't share any common prime factor), but that is not a problem since our two factors are two different prime numbers and therefore coprime by definition :)
This video has by far the best explanation of public/private key!
I've never seen a video so well done to explain a very technically complex (and intriguing) topic! Amazing!
thanks for the feedback
At 11:02 one has to be careful. The Euler's Phi Function is multiplicative (i.e ϕ(a*b)=ϕ(a)*ϕ(b)) only if the greatest common divisor satisfies gcd(a,b)=1. Otherwise we would have 4=ϕ(8)=ϕ(2*4)=ϕ(2)*ϕ(4)=1*2=2. In our case, we're always taking two different primes and the condition holds.
Striked me too. Glad to find your comment here, otherwise I'd be in doubts...
You explained it clearly. Thank you very much.
One of the best explanations on the internet, plus the lock analogy is amazing
Simply put, your video was amazing to watch. You cleared up everything (most of it) in a really easy to understand way. Thank you. You succeeded, where many other people failed.
Very nice, especially the example at the end! Just how you get the number 2 at 14:22 is not really understandable
11:06 don't forget that this only holds when A and B are both prime
Nice. This really helped me understand the details of the RSA algorithm, and how the decryption is actually discovered by the sender of the original message
Greatest Video I have found so far about Public Key Cryptography.
Thanks a lot for summarizing and simplifying this topic.
At 14:20 where did that k = 2 come from in d = (2*3016 + 1)/3 ????
So I pick k = 1 and end up with a non-integer number. What happens then?
Then you try k = 2, if it's still non-integer then you try k = 3. etc. In my exam we worked with these numbers, going to use the same variable names as in the video.
p1 = 31
p2 = 23
m = 42
n = 31*23 = 713
φ(n) = 30*22 = 660
Choosing e, starting with e = 3 => 660/3 = 220 //Not good
Testing e = 5 => 660/5 = 132 //Still not good
Testing e = 7 => 660/7 = 94.28571429 //Good, doesn't share factor with φ(n).
Choosting d, starting with k = 1:
d = (1*660+1)/7 = 94.42857143 //Not good, non-integer.
Try k = 2:
d = (2*660+1)/7 = 188.7142857 //Not good, non-integer.
Try k=3:
d = (3*660+1)/7 = 283 //Good
Encryption:
c = m^e mod n = 42^7 mod 713 = 199
Decryption:
m = c^d mod n = 199^283 mod 713 = 42
Hope this helps :)
tywald Thanks for writing it out! Helped a lot for a lazy mobile user.
my book kept confusing me as it didnt clear the trials that u showed. and with the video, i was goin crazy. thanks for putting it up.
thanks, made even the last bit clear
Holy shit, my brain is overheating. Was running at 100% capacity since 9:55
Ten year late but glad to arrive here. This explanation, wow what a great journey.
this was so high quality and explained this concept super well! I can't thank you enough
quick question, around 14:21 we see that the equation as 2 as the K value, why is that, because when I try to replicate this equation, I can't seem to get a resulting whole number, so why is it 2 in this case, what do you have to do to put in the value for K?
iterate k from 1 until (k*phi(n))+1) is divisible by e to give an integer, if the result is in fraction then increment k n try again.
I would like to share some ideas I learned about the topic. Many of you asked about how k came on. Let me approach this from a different angle. We would like to choose d so that e · d = k · ϕ(N) + 1 is true for some k. In other words, we need to fulfill the following congruence: e ⋅ d ≡ 1 (mod ϕ(N)). Since we have already found an e so that e and ϕ(N) don't share a common factor, or in other words, gcd(e, ϕ(N)) = 1, this congruence is a linear congruence for the variable d, which has a solution, because of the fact that gcd(e,ϕ(N)) = 1, and can be solved using Euklides' algorithm. Therefore, the main point is not to find a k by guessing, but to find d directly, using the method mentioned above. I hope this helped some of you.
i still dont understand why we need K
@@bartoszkowalski885 you dont
OK I understand your point, but how do we calculate k?
@@Loxodromius you use the euclidean extended algorithm, which gives you d and k at once. You can Aldo get d with the Chinese Remainder theorem, if you know p and q, which is more efficient.
@@bartoszkowalski885 I thought the usage of k is to find an integer d,
say at 14:20 (3016+1)/3=1005.667 but (2*3016+1)/3=2011, which is a 4-digit number
So many other videos, this one finally includes formulas and examples, exactly what I was looking for.
The producers of this video are, without question, didactic geniuses.
thanks so much, made this video almost a decade ago and worked really hard on it
how is k determined ?? why is 2 here ??
Thank you so much for this video. It explained everything so well and helped me finally understand! Just one question. Since this all relies on Euler's Theorem, for which you mention that m and n must share no factors, what if the message m happens to share a factor with n (i.e. it is divisible by either p1 or p2)?
@Maya Bielecki
Although Euler's theorem itself - in the form m^{φ(n)}≡1 (mod n) - is indeed only valid for an m relatively prime to the modulus n (relatively prime means that they share no non-trivial factors or equivalently that their greatest common divisor is 1), the actual relation justifying the validity of the encryption method is a bit more general, as follows: given a square-free natural number n (this condition means that n is not divisible by the square of any k≧2 or equivalently that all the prime divisors of n have multiplicity 1 in n; do remark that this is in particular the case for N=p_1*p_2, in the video presentation) and a natural number r congruent to 1 modulo φ(n), it is necessarily the case that m^r≡m (mod n).
This video was amazing. I've been racking my brain trying to conceptualize public and private keys. I couldn't figure out why input couldn't just be fed into the public key over and over to crack the private key, but your video finally made it click. Thank you for posting!
thrilled to hear it
Yes same here. It's incredible that there is a mathematical equations to make a scramble rubics cube almost impossible to return it back to same position as it was scrambled
I have been researching on public key cryptography for 3 weeks. This is the best explanation. Thanks
thrilled to hear people find this
This was an excellent video, despite the glossing over of k.
The k was multiplied to make sure that (k*phi(n) + 1)/3 was a whole number. If k was 1, then it wouldn't give a whole number.
This video is dope. Thanks bruh.
welcome to the family, once you in, you ain't leavin'
Aameen
i am cryptographer and i believe i grasped concept of rsa the way i have never before. that's how on point your interpretation is. respect.
wow that's amazing to hear, I'm curious what clicked?
I have a cybersecurity test tomorrow and this video is just amazing and extremely helpful, awesome job
The equations around 5:30 are misusing the congruent sign, it should be equal.
What is the key length?? And what does k signify in the equation of d,i.e
d=(k*phi(n)+1)/e)?? Please reply quickly
thabg007 Art of the Problem RenanzinhoSP
This is an EXCELLENT explanation of RSA!
The best video about explaining the RSA. Not only the procedure of performing encryption and decryption, but also clarify mathmathic knowledge behind that.
thanks, so cool people still find this
Hey I have a new video out: ruclips.net/video/5EcQ1IcEMFQ/видео.html would love if you could help me share it
Why do you multiply the function by k?
My brain hurts. xD
mine too
I have never been interested in cryptography .. I played this video by accident .. but man what an excellent explanation and content you got for the entire 16 minutes.
thrilled to hear it
Nice work man, this helped a lot. And yeah, the distribution of the primes is one of the most beautiful things I've learned about. You have to wonder how in the hell there is so much structure in a sequence that is just adding 'one' to the next!
14:14 Why the private key is multiplied by '2' ??? What does this '2' mean???
he picked K from nowhere x)
PFM!
It's so that when you divide by 3, you get a whole number
The eavesdropper name is EVE! EVE the EAVESDROPPER. Thank you.
2023: still the greatest video on the topic. Many people are asking about k=2. In this case modular inverse would be heplful: the modular inverse of 3 mod 3016 is 2011.
ive watched this so many times and its just so perfect
What is the value of k? I understand how it fits in the equation but I don't understand why it was necessary.
It is necessary to make the division return a whole number. K should be chosen to be a the smallest number so that D is integer. Without K, one cannot guarantee that that division returns an integer number. I think.
we got the keys here.
what do you mean ?
i mean Mr benjamin woods his my trader he has done me so well in trading
ho i get you
wow you know Mr Benjamin woods too? he is my manager where are you from mariah ?
never seeing a better trader like Mr benjamin woods
That intense industrial background music just makes this video even better.
glad you like it, I get a lot of flack about my music sometimes :)
@@ArtOfTheProblem No problem and thanks so much for the awesome video! I only had one part that I didn't quite understand. Where does the `k` come from in the `k * Phi + 1`? Is that arbitrary and left up to us to choose? Also, why is it even necessary? Wouldn't `d = (Phi + 1) / e` also work?
Fascinating. I had to pause a few times to think about it but the video is really clear. Thanks!
Around 12:30, isn't the mod n supposed to be on the left of the equation? The remainder is always 1, right?
This confused me also and its convergence notation not an equation. www.whitman.edu/mathematics/higher_math_online/section03.01.html
This bit also confused me but I was not familiar with Congruents.
I'm sorry but the equation at 15:02 is incorrect.
It should be (1394 ^ 2011) mod 3127 = 89
Thanks for that. Was following then got super confused. I mean how can you know the message (89) prior to running it.
What is shown at 15:02 is a congruence, not an equation. If someone writes "a (congruent) b mod n" (where congruent is usually written as the triple-line equals), that means "a mod n = b mod n" (this time actually equals, an equation). The first way is just a slightly simpler way to write it.
Larry Ruane - I still do not have `b` by that formula... and he clearly spoke "(c ^ d) mod n" and not the written formula (with congruent)
you read the symbols wrongly... he didnt say 1394^2011=89 mod 3127
he stated: 1394^2011 is congruent to 89 modulo 3127( the three lines symbol denotes congruence and not equality) - this means 1394^2011 mod 3127 = 89 mod 3127 or simply 89. In case 1394^2011 mod 3127= 89 than its true... i dont have an algorithm to verify this bet it should be true.
Did you try it? if you did, you would be understanding that smth is off, cause that wouldn't give you 89 at all.
This became one of my favorite youtube videos.
Great explanation, Great editing!
Congrats!
happy people are still finding this channel, stay tuned for more!
This has been the best explanation I've found so far, thank you :)
Thanks for all your videos, beautifully done, I'm using them to study for my exam. In min 15:04 it's written c^d ≡ 89 mod 3127. there should be c^d mod 3127 = 89? Sorry for my English.
In modular arithmetic, that's equivalent. If at the end you have mod N, you can think of parts before and after the ≡ as all having that mod N.
E.g. c^d ≡ 89 mod 3127 is the same as c^d mod 3127 = 89 mod 3127
I cannot understand the position of K in the equation.
+Panth Mantheon Nor can I, we learnt that to find d we have to solve the following congurence: e*d congurent 1 mod phi(n)
However when we decode it, we do use that x^(phi(n)*k)=1, because x^(e*d)=x^(k*phi(n)+1)=x*x^(k*phi(n))=x*1=x.
Edit:My guess is that he didn't want to explain how to solve a linear
congurence, so he just came up with k, or I'm just too dumb to
understand it.
+KRCPrice since taking the base to the power of phi alone is congruent to 1, the overall value achieved from raising this base to phi can be raised to any value k and still be 1, since 1^k is 1.
+CH Black But why you should raise the base to any value k
+francesco pham It is for the convenience of breaking the whole key into a public key (e) and a private key (d). Take a look at 13:14. We want to find an "e" and a "d" such that e*d=k*phi(n)+1. If we can find any such pair of "e" and "d", then we can publish "e" as part of the public key, and use "d" as a private key to cancel the effect of "e". However, not all values of "k" gives a nice split of k*phi(n)+1. For example if n=8, then phi(n)=4, and if we choose k=1, then k*phi(n)+1=5, which means either "e" or "d" must be 1, which is too trivial to server as a key. To avoid such bad choices, we randomly pick a non-trivial "e" that has no common factors with phi(n), and find a "k" such that phi(n)+1 is divisible by "e", giving d=(phi(n)+1)/e. In his final example at 14:23, he randomly picked e=3, and chose k=2 because 2*3016+1 is divisible by 3. Of course k=5 will work as well, it will just give a larger d (public key). The point is that any "k" will make the formula work, and we just pick one that gives a convenient and non-trivial split of k*phi(n)+1 into "e" and "d".
+Peng Zhao That helped a lot, thanks. Also, why shouldn't our "e" share a prime factorization with phi(n)? I could imagine this is not to give any hints to Eve, but is there any other reason to that restriction?
Thank you for this video. The breakdown is amazing and it is so easy to understand. Way better than any text that I have come across on RSA.
thanks it was a labour of love :)
Phi(A*B)=Phi(A)*Phi(B) iff gcd(A,B)=1
This is an extremely important distinction to make! Hope you can update the video with this.
Thx, I was thinking if simply Phi(A*B)=Phi(A)*Phi(B), there would be a paradox. For example Phi(8)=Phi(2)*Phi(2)*Phi(2)=1, which is actually 4.
He actually states in the video that e and d are chosen to be coprimes, so in the context of this video that expression holds
15:03 what calculator are you using? every time i try to calculate c*d i get an overflow error. help?
where the 2 came out ??
how can you get kkkk
Best video that explains RSA hands down
Best explanation of RSA on the internet !thank u
Take all my money
13:06: This is the breakthrough.
Me: What? what breakthrough?
I started loosing it around that time
Thanks for create this video, I can imagine all the work that take to you do this.
Excellent video thanks very much, I was trying to get my head around RSA for a school assessment and this clarified everything for me. Even allowed me to make a worked example using my own prime numbers and explained it to the class
Who the fuck is Alice and Bob?
truly amazing! I think it is possible to understand this this extraordinarily complex solution
this made it so much easier to understand, even though now my mind is blown and i have a severe headache from thinking so dang hard. this concept is so dope
I agree with many other comments: the ones who came up with this are geniuses, but you are just as much a genius for being able to explain this so thoroughly!! Thank you so much!
really appreciate it
I don't know if u still post but I subscribed after watching this masterpiece of an explanation.
thanks for the feedback, it was a huge video to make. I will post again but have been distracted with a new project I'm working on www.storyxperiential.com (I hope to make these across many disciplines)
Sooo useful. Saving my life so much as a student. Thank you
This was a great video. Showed the math yet made the application understandable too. Thanks
Thank you this was a great explanation and included the maths that so many other videos lack