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?
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
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?!
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 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!
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.
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: ua-cam.com/video/oOcTVTpUsPQ/v-deo.html
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'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
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.
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.... ????
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
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.
The best video about explaining the RSA. Not only the procedure of performing encryption and decryption, but also clarify mathmathic knowledge behind that.
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.
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 :)
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!
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.
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".
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 :)
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
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
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?
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
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
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
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!
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.
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.
+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?
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).
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)
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.
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
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.
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.
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.
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 🙌
@@yassine-saI don’t know. There’s things harder
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.
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 :)
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 ua-cam.com/video/5EcQ1IcEMFQ/v-deo.html
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?!
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!
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
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
Wow what a great way to convey such a difficult subject of cryptography in such a comprehensive yet understandable way.
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.
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 :)
One of the finest videos to explain the beauty of cryptology and hence prove the magic of prime numbers
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.
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: ua-cam.com/video/oOcTVTpUsPQ/v-deo.html
This video is by far the most elegant and easy to understand explanation of RSA encryption I've seen. Thank you.
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?
Thanks for this beautiful explanation of encryption 😍And hats off to RSA for making this "public", people like them bring back the trust in Humanity 🙏
Heck of a video, I've watched around 5 times now.
glad it was helpful for you - stay tuned for more!
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
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.
I have been researching on public key cryptography for 3 weeks. This is the best explanation. Thanks
thrilled to hear people find this
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.... ????
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
This is just one of the greatest crypto related videos out on web (with an excellent timing of bg theme changes :))
This is absolutely the best exposition of public key, for me at this point.
glad you found it
Such a nice explanation,thank you very much
I've never seen a video so well done to explain a very technically complex (and intriguing) topic! Amazing!
thanks for the feedback
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.
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: ua-cam.com/video/5EcQ1IcEMFQ/v-deo.html would love if you could help me share it
Incredibly well explained, it was magical. Thank you!
Greatest Video I have found so far about Public Key Cryptography.
Thanks a lot for summarizing and simplifying this topic.
16:05 That was me with the rock after watching this video
This video has by far the best explanation of public/private key!
Fantastic video for figuring out how public key/private key work.
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 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 :)
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
Watching videos as such, makes me believe in UA-cam Gods.
The best explanation of cryptography that I have seen on the internet.
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...
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".
I know the feeling. Or, "using complex mathematics"...
Art of the Problem absolutely
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
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
Very nice, especially the example at the end! Just how you get the number 2 at 14:22 is not really understandable
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
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.
So many other videos, this one finally includes formulas and examples, exactly what I was looking for.
Holy shit, my brain is overheating. Was running at 100% capacity since 9:55
One of the best explanations on the internet, plus the lock analogy is amazing
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
Both the way in which this is explained and the style of the video are beyond amazing. Thank you!
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
This became one of my favorite youtube videos.
Great explanation, Great editing!
Congrats!
happy people are still finding this channel, stay tuned for more!
You explained it clearly. Thank you very much.
I have a cybersecurity test tomorrow and this video is just amazing and extremely helpful, awesome job
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.
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
11:06 don't forget that this only holds when A and B are both prime
This is the best video I have ever watched.
:)
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.
you have the best 101 explaination so far i have seen
stick around for more!
The equations around 5:30 are misusing the congruent sign, it should be equal.
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
how is k determined ?? why is 2 here ??
Truly an excellent explanation. Much more informative than the one provided by the Computerphile channel.
appreciate the feedback. I try to fill the gaps that other videos miss
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
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!
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.
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.
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?
Ten year late but glad to arrive here. This explanation, wow what a great journey.
My brain hurts. xD
mine too
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?
Glad you did. Not my game
This video is dope. Thanks bruh.
welcome to the family, once you in, you ain't leavin'
Aameen
this was so high quality and explained this concept super well! I can't thank you enough
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).
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)
Why do you multiply the function by k?
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.
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 ?
@arron mason you van connect mr benjamin via mail benjaminwoods112@gmail . com
HOW are you this good at teaching? It is absolutely mindblowing. THANK YOU SIR.
appreciate the kind words
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
This is art and this is the most beautiful explanation. My brain needs one daily.
subscribe more to come!
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.
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.
The eavesdropper name is EVE! EVE the EAVESDROPPER. Thank you.
Wow... So well explained... Till now best video which explains relationship between public key and private key
15:03 what calculator are you using? every time i try to calculate c*d i get an overflow error. help?
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 :)
where the 2 came out ??
how can you get kkkk
Holy shit my brain is melting at how clever this is, but beautifully explained and really good graphics.
13:06: This is the breakthrough.
Me: What? what breakthrough?
I started loosing it around that time
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
Who the fuck is Alice and Bob?
Fascinating. I had to pause a few times to think about it but the video is really clear. Thanks!
Take all my money
OMG! brilliantly and clearly explained. Best vid I've seen in a while
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.
This has been the best explanation I've found so far, thank you :)