Public Key Cryptography: RSA Encryption Algorithm

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...

[@thabg007]

my brain is running at 100% CPU usage watching this video

[@matthewpeters6448]

Mine's overclocked ;)

[@ArtOfTheProblem]

thabg007 editing this video almost killed me...

[@masawafighter7172]

My mind blew up whole watching this, I don't have a brain anymore

[@alexandermedina4950]

+thabg007 You could hear the fans going full speed in mine.

[@YesYou123333]

+thabg007 Maybe it needs a Windows update.

[@karjedav]

Possibly the best explanation of anything on the Internet.

[@ArtOfTheProblem]

Thanks Aalap, I hope to try and match this video with the upcoming one on P vs. NP

[@silbersmurber]

agree

[@ccg8803]

by sure

[@yassinesafraoui]

Yes, it explains such a complex topic very easily, hands up 🙌

[@TheSleyths]

God the people that came up with this thing are surely geniuses, can't but feel idiotic after watching this.

[@Youda00008]

TheSleyths i feel like that all the time during my studies

[@a1988ditya]

+TheSleyths +1

[@ezekielchoke2580]

Constantly feeling like that since I started digging into computer science.

[@MikhailFederov]

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.

[@barrykendrick3146]

+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?!

[@pixelbogpixxelbog2090]

10 years old? Wow better quality than most videos today. Well done :)

[@ashokbanerjee8843]

Admirable how simply you worked through explaining it all. Beautifully done, both the delivery and the accompanying graphics and animation

[@TheResonating]

+Art of the Problem question, at 13:43, which component is the chosen color, and which one is the "complement" color?

[@arfcommer15]

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!

[@AkashdeepSingh-qq5fw]

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?

[@Artaxerxes.]

@@arfcommer15 The "math way" is clearer than this. This video glosses over many important details

[@arrelite]

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.

[@dapdizzy]

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!

[@morgankuphal3417]

Right! I paid $15,000 a semester and I learned more in 16 minutes and 30 seconds than I did in 13 weeks.

[@punditgi]

Best explanation anywhere! Bravo, signore!

[@iselapuga1856]

@@dapdizzy lol oki

[@fries6402]

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

[@ArtOfTheProblem]

that's SO cool to hear, love this story, thanks for sharing...i remember when I made this video it feels like another era

[@ArtOfTheProblem]

New video is up on Evolution of Intelligence kzbin.info/www/bejne/a3bGgmR_mKqAfLM

[@guitarinos]

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.

[@petrprokop63]

Striked me too. Glad to find your comment here, otherwise I'd be in doubts...

[@whatever-ko8qx]

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.

[@ArtOfTheProblem]

awesome that was the goal!

[@SawSkooh]

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.

[@TheDJay72]

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.

[@doyoungjung9332]

yes, it's right. d is a multiplicative inverse of e mod phi(n)

[@nathankagoro9969]

can someone please explain in simple terms how we get k, I need it for a project

[@Sheeplie33]

(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).

[@robneff7084]

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: kzbin.info/www/bejne/pYDGhYmKpbqmhrM

[@charlesgerard5721]

Heck of a video, I've watched around 5 times now.

[@ArtOfTheProblem]

glad it was helpful for you - stay tuned for more!

[@HundredMillionViews]

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.

[@michaelyang6168]

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.

[@aprendiendoC]

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

[@icy14]

16:05 That was me with the rock after watching this video

[@MaxRoth]

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!

[@RegnerVE]

Max Roth but how to find k if you don't have the 'd'?

[@MaxRoth]

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

[@RegnerVE]

I will check it out tomorow thx for the fast respons buddy!

[@AnuragSawarkar]

Hi, I would just like to ask you, where exactly does the d=e^-1 mod phi (n) originate from?

[@yanivmms]

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.... ????

[@davidlawrence8085]

This is absolutely the best exposition of public key, for me at this point.

[@ArtOfTheProblem]

glad you found it

[@Nemanja29100]

Such a nice explanation,thank you very much

[@robneff7084]

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).

[@2sourcerer]

I'm stuck. Which other videos?

[@cottondai]

Wow what a great way to convey such a difficult subject of cryptography in such a comprehensive yet understandable way.

[@lukaborec1671]

Both the way in which this is explained and the style of the video are beyond amazing. Thank you!

[@matthewsnow6317]

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.

[@Vojtos3]

This is gold. I can’t image how much work it must have involved. I appreciate your work greatly

[@ArtOfTheProblem]

it was an epic video to great, I put everything I had into it :)

[@davidr.flores2043]

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

[@davidr.flores2043]

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!!!

[@ArtOfTheProblem]

thanks david, happy to have you around. love to see it aged well

[@anusha5788]

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.

[@jatinsw1128]

One of the finest videos to explain the beauty of cryptology and hence prove the magic of prime numbers

[@annablendermann]

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

[@skim2958]

This video is by far the most elegant and easy to understand explanation of RSA encryption I've seen. Thank you.

[@CalebJones]

Fantastic video for figuring out how public key/private key work.

[@zekininadresi]

This is just one of the greatest crypto related videos out on web (with an excellent timing of bg theme changes :))

[@Lik3wise]

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.

[@theeggmancometh]

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.

[@sujitkumarsingh3200]

In engineering, I have learnt encryption and deception in details, but this video explains those concepts in great details.

[@ArtOfTheProblem]

made this for people like you

[@amaridissou65]

Incredibly well explained, it was magical. Thank you!

[@mihiguy]

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 :)

[@guilhermedantas5067]

I've never seen a video so well done to explain a very technically complex (and intriguing) topic! Amazing!

[@ArtOfTheProblem]

thanks for the feedback

[@redrodlrowon]

The producers of this video are, without question, didactic geniuses.

[@ArtOfTheProblem]

thanks so much, made this video almost a decade ago and worked really hard on it

[@omkarium]

Watching videos as such, makes me believe in KZbin Gods.

[@martinziet7157]

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.

[@22Tech]

this was so high quality and explained this concept super well! I can't thank you enough

[@Wownerd1265]

So many other videos, this one finally includes formulas and examples, exactly what I was looking for.

[@AjithChanaka]

You explained it clearly. Thank you very much.

[@SongwriterTaco]

At 14:20 where did that k = 2 come from in d = (2*3016 + 1)/3 ????

[@Demorgorgon]

So I pick k = 1 and end up with a non-integer number. What happens then?

[@tywald]

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 :)

[@ats1995]

tywald Thanks for writing it out! Helped a lot for a lazy mobile user.

[@samirdayalsingh7721]

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.

[@ZonkoKongo]

thanks, made even the last bit clear

[@yangpiao3071]

The best video about explaining the RSA. Not only the procedure of performing encryption and decryption, but also clarify mathmathic knowledge behind that.

[@ArtOfTheProblem]

thanks, so cool people still find this

[@ArtOfTheProblem]

Hey I have a new video out: kzbin.info/www/bejne/a3bGgmR_mKqAfLM would love if you could help me share it

[@jihochoi_cs]

This video has by far the best explanation of public/private key!

[@peschebichsu]

Very nice, especially the example at the end! Just how you get the number 2 at 14:22 is not really understandable

[@Kelkworth]

11:06 don't forget that this only holds when A and B are both prime

[@bayremgharssellaoui238]

One of the best explanations on the internet, plus the lock analogy is amazing

[@BudgiePanic]

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

[@kristofkallo]

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.

[@bartoszkowalski885]

i still dont understand why we need K

[@duartemortagua5782]

@@bartoszkowalski885 you dont

[@Loxodromius]

OK I understand your point, but how do we calculate k?

[@duartemortagua5782]

@@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.

[@michaelfung680]

@@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

[@reservoirman]

This was an excellent video, despite the glossing over of k.

[@MatthewLiuCube]

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.

[@brandone7273]

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!

[@ArtOfTheProblem]

thrilled to hear it

[@dneirfenoz1961]

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

[@xXxBladeStormxXx]

That intense industrial background music just makes this video even better.

[@ArtOfTheProblem]

glad you like it, I get a lot of flack about my music sometimes :)

[@xXxBladeStormxXx]

@@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?

[@opinionsarenotmyown8818]

Holy shit, my brain is overheating. Was running at 100% capacity since 9:55

[@guanine369]

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?

[@obtron]

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.

[@MsAmedina1]

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.

[@ArtOfTheProblem]

thanks it was a labour of love :)

[@philippdolomit4830]

Greatest Video I have found so far about Public Key Cryptography. Thanks a lot for summarizing and simplifying this topic.

[@mayabielecki7438]

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)?

[@poincareseifert1673]

@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).

[@wemingle]

This video is dope. Thanks bruh.

[@ArtOfTheProblem]

welcome to the family, once you in, you ain't leavin'

[@MohamedAnsari_H]

Aameen

[@gambleroflife]

I have been researching on public key cryptography for 3 weeks. This is the best explanation. Thanks

[@ArtOfTheProblem]

thrilled to hear people find this

[@Mynamegeoph]

I have a cybersecurity test tomorrow and this video is just amazing and extremely helpful, awesome job

[@AbbyChau]

The equations around 5:30 are misusing the congruent sign, it should be equal.

[@tejaslodaya1]

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

[@user-nc3sl5mn8p]

i am 26 years old that has just got to learn about this whole cryptography in 2023 thanks.

[@ArtOfTheProblem]

Nice! love to see it live on

[@davidedwardsjr4350]

truly amazing! I think it is possible to understand this this extraordinarily complex solution

[@a1988ditya]

how is k determined ?? why is 2 here ??

[@mariahclery1157]

we got the keys here.

[@parksunjoo7717]

what do you mean ?

[@mariahclery1157]

i mean Mr benjamin woods his my trader he has done me so well in trading

[@parksunjoo7717]

ho i get you

[@stephanielawrence9106]

wow you know Mr Benjamin woods too? he is my manager where are you from mariah ?

[@jessicawitherford9441]

never seeing a better trader like Mr benjamin woods

[@samirghoudrani3659]

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)

[@fireflies15]

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

[@ArtOfTheProblem]

excellent so clear to hear it

[@valentinsarmagal]

The eavesdropper name is EVE! EVE the EAVESDROPPER. Thank you.

[@Urahara12]

Around 12:30, isn't the mod n supposed to be on the left of the equation? The remainder is always 1, right?

[@donelygunn6002]

This confused me also and its convergence notation not an equation. www.whitman.edu/mathematics/higher_math_online/section03.01.html

[@Celdorsc2]

This bit also confused me but I was not familiar with Congruents.

[@TheISNetworldConsultant]

The best explanation of cryptography that I have seen on the internet.

[@waiitwhaat]

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.

[@kshow666]

What is the value of k? I understand how it fits in the equation but I don't understand why it was necessary.

[@akithered]

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.

[@Serob42]

14:14 Why the private key is multiplied by '2' ??? What does this '2' mean???

[@BilalMellah]

he picked K from nowhere x)

[@ImGuti]

PFM!

[@MatthewLiuCube]

It's so that when you divide by 3, you get a whole number

[@chatterb]

Ten year late but glad to arrive here. This explanation, wow what a great journey.

[@Pkroc138]

Thanks for create this video, I can imagine all the work that take to you do this.

[@DJTimeLock]

My brain hurts. xD

[@snehanshuphukon728]

mine too

[@ongy3]

Why do you multiply the function by k?

[@Filip_Phreriks]

Fascinating. I had to pause a few times to think about it but the video is really clear. Thanks!

[@ratl0ver3]

This was so wonderfully done.

[@christosbinos8467]

I cannot understand the position of K in the equation.

[@KRCPrice]

+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.

[@christopherburgess4486]

+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.

[@francescopham]

+CH Black But why you should raise the base to any value k

[@ericz6515]

+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".

[@Ali009Ahmed]

+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?

[@ones9638]

15:03 what calculator are you using? every time i try to calculate c*d i get an overflow error. help?

[@petrospaulos7736]

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.

[@MedhaviN]

This was awesome.. I liked it how he explained the whole thing along with bits of mathematical history..

[@apreasher]

I'm sorry but the equation at 15:02 is incorrect. It should be (1394 ^ 2011) mod 3127 = 89

[@JeaneAdix]

Thanks for that. Was following then got super confused. I mean how can you know the message (89) prior to running it.

[@LarryRuane]

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.

[@strohtaler4698]

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)

[@najgauner]

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.

[@helena8918]

Did you try it? if you did, you would be understanding that smth is off, cause that wouldn't give you 89 at all.

[@tropicalpenguin9119]

where the 2 came out ?? how can you get kkkk

[@gavindeulufount2043]

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!

[@ethanparker876]

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

[@FRANCOBELLONI85]

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.

[@supernovaw39]

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

[@alicewonderland9151]

13:06: This is the breakthrough. Me: What? what breakthrough?

[@kaoutermarref9915]

I started loosing it around that time

[@dropagemonem]

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.

[@ArtOfTheProblem]

wow that's amazing to hear, I'm curious what clicked?

[@rbettsx]

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.

[@NoahAndABadger]

Take all my money

[@JohnSmith-bx4gf]

Who the fuck is Alice and Bob?

[@ericdonofrio6946]

This is an EXCELLENT explanation of RSA!

[@ayoubmokeddem8706]

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.

[@ArtOfTheProblem]

thrilled to hear it

[@johnstaf]

Wonderful explanation! Thank you for explaining the important details.

[@cecilhenry9908]

This was a great video. Showed the math yet made the application understandable too. Thanks

[@oliverdowning1543]

Thank you this was a great explanation and included the maths that so many other videos lack

[@krylite5541]

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).