Public Key Cryptography: RSA Encryption Algorithm

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

[@yassine-sa]

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

[@brendawilliams8062]

@@yassine-saI don’t know. There’s things harder

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

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

[@pixelbogpixxelbog2090]

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

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

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

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

[@AnimeshSharma1977]

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 🙏

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

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

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

[@cottondai]

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

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

[@charlesgerard5721]

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

[@ArtOfTheProblem]

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

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

[@nathankagoro]

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

[@skim2958]

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

[@jatinsw1128]

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

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

[@Nemanja29100]

Such a nice explanation,thank you very much

[@davidlawrence8085]

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

[@ArtOfTheProblem]

glad you found it

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

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

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

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

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

[@ngocvo9058]

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!

[@ArtOfTheProblem]

really appreciate it

[@zekininadresi]

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

[@TheISNetworldConsultant]

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

[@CalebJones]

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

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

[@amaridissou65]

Incredibly well explained, it was magical. Thank you!

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

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

[@tongleo1055]

you have the best 101 explaination so far i have seen

[@ArtOfTheProblem]

stick around for more!

[@icy14]

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

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

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

[@jihochoi_cs]

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

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

[@masterflamaster6377]

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

[@ArtOfTheProblem]

I know the feeling. Or, "using complex mathematics"...

[@masterflamaster6377]

Art of the Problem absolutely

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

[@samirdayalsingh0]

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

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

[@omkarium]

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

[@philippdolomit4830]

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

[@peschebichsu]

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

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

[@brendawilliams8062]

Glad you did. Not my game

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

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

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

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

[@mr.pineapple7688]

@@ArtOfTheProblem thanks a lot! i hope u get what u expect sharing such useful informations

[@AjithChanaka]

You explained it clearly. Thank you very much.

[@stefanvasilev8948]

This is the best video I have ever watched.

[@ArtOfTheProblem]

:)

[@AbbyChau]

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

[@bayremgharssellaoui238]

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

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

[@juancortez9654]

Truly an excellent explanation. Much more informative than the one provided by the Computerphile channel.

[@ArtOfTheProblem]

appreciate the feedback. I try to fill the gaps that other videos miss

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

[@fnln5541]

Wow... So well explained... Till now best video which explains relationship between public key and private key

[@Kelkworth]

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

[@Mynamegeoph]

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

[@opinionsarenotmyown8818]

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

[@dhruv01dubey]

I don't know if u still post but I subscribed after watching this masterpiece of an explanation.

[@ArtOfTheProblem]

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)

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

[@deMojo1]

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

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

[@IreshDissanayakaM]

This is art and this is the most beautiful explanation. My brain needs one daily.

[@ArtOfTheProblem]

subscribe more to come!

[@ones9638]

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

[@lukaborec1671]

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

[@wemingle]

This video is dope. Thanks bruh.

[@ArtOfTheProblem]

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

[@MohamedAnsari_H]

Aameen

[@chatterb]

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

[@a1988ditya]

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

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

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

[@MaryamSeyedi22]

HOW are you this good at teaching? It is absolutely mindblowing. THANK YOU SIR.

[@ArtOfTheProblem]

appreciate the kind words

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

[@JustSkillGG]

This became one of my favorite youtube videos. Great explanation, Great editing! Congrats!

[@ArtOfTheProblem]

happy people are still finding this channel, stay tuned for more!

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

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

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

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

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

[@Wownerd1265]

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

[@ongy3]

Why do you multiply the function by k?

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

[@valentinsarmagal]

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

[@mohamedelaminboukerfa7127]

Best explanation of RSA on the internet !thank u

[@tropicalpenguin9119]

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

[@nabeel250575]

haven't seen any videos better than these on cryptography. Good work thanks.

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

[@beckymilton2029]

@arron mason you van connect mr benjamin via mail benjaminwoods112@gmail . com

[@bd189a55]

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.

[@alicewonderland9151]

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

[@kaoutermarref9915]

I started loosing it around that time

[@RazorCallahan2424]

Best video that explains RSA hands down

[@DJTimeLock]

My brain hurts. xD

[@snehanshuphukon728]

mine too

[@mbharatm]

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!

[@ArtOfTheProblem]

thanks for feedback, I remember the joy of working on that analogy....

[@mbharatm]

LOL... I just noticed that this video was done in 2012! Talk about lasting value! :)

[@JohnSmith-bx4gf]

Who the fuck is Alice and Bob?

[@hellocrappy]

This is an EXCELLENT explanation of RSA!

[@NoahAndABadger]

Take all my money

[@cafafans]

The best explanation of RSA Encryption Algorithm in the entire internet. You are great, thank you so much.

[@manchupuvvu]

Excellent video. A fine example of how KZbin can be used constructively. Thank you.

[@ohad219]

Holy shit my brain is melting at how clever this is, but beautifully explained and really good graphics.