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?!
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?
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!
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
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.
(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: ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-oOcTVTpUsPQ.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.
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.
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).
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 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.
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!
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
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.... ????
The best video about explaining the RSA. Not only the procedure of performing encryption and decryption, but also clarify mathmathic knowledge behind that.
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 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!
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 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.
@@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
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
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.
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.
It's gratifying that the work and discoveries of Ellis, Cocks, and Williamson are finally being acknowledged. Cocks has been remarkably sanguine about the concealment of his achievements for 20 years after the publication of RSA.
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 :)
THIS IS PURE AWESOMENESS. I've been looking for an explanetion of RSA public and private key encryption for ages, and this is the only one I've found that doesn't say that the math behind it is "beyond the scope of the video".
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).
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.
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?
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
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!
Awesome. I think the best part are: 1, if you got c/n/e, you get many many m values, because it's mod. So you don't know which m is right. 2, you will spend super long time to guess p1 and p2, in order to know d. This algo is awesome.
something that helped me understand the phi function is that the phi function calculates the amount of co-prime numbers of any number n. Co-prime means that the number shares no common factors with another number (in this case, n).
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
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
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
Absolutely amazing video. I wish in movies they explained that some secret organization can get any info in the world because they developed a method to prime factorize efficiently. It would be complex enough that the normal audience wouldnt question it and still authenticly impossible thing for us. It's like a win win for everyone.
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
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.
@@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?
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.
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.
+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.
+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?
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)
Great explanation, super clear! There is also Bezout theoreme involved in the existence of k to make d integer (this is why e needs to share no divider with phi n)
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.
Funny... I actually had come up with the same analogy of public lock(s) which were accessible to all and private key known only to the owner. But the analogy of the colored lights and mixing was even better. Superb video! Thanks!
