@@sharonomonua1747 Mod or modulo only returns the remainder of a division operation. For instance, if you divide 5 into 5, the result is 1. But if you divide 5 into 3, the remainder is 2. Therefore, we write 5 modulo 3 = 2. These videos might help: 1 - th-cam.com/video/6dZLq77gSGU/w-d-xo.html 2 - th-cam.com/video/4zahvcJ9glg/w-d-xo.html
I was trying to understand the Wikipedia page on this topic with some difficulty. Your video did an excellent job of explaining it simply. Thanks a lot.
Nice simple introduction and the slow transitioning of deeper and technical understanding with step by step interactivity in processing the RSA algorithm. Finally, ending with a real life example using Amazon's cart totally amazed me how it all works together. I'm sharing this with one of my Math Faculty members who teaches math for teachers, she'll be impressed to see how cryptography applies in real life and that most people don't know it. Thank you for taking the time out and scripting this too, good job, and an A+!
I just wanted to say that the way you showed the extended Euclidean algorithm was not something I had seen before and it made my work SO much easier. You've more-than earned my like.
extended euclidean algorithm is far easier than this technique and less time consuming. whereever you go there's just a matter of time and if you are slower then no one cares :)
As Edward Snowdon said recently and as Gordon Welchman said 70 years ago, a computer generated algorithm thats creates a cypher can always be decrypted. The only true unbreakable encryption is a non computer generated one time pad. Its still used today. There is a guy in Switzerland who has a barrel with 50,000 dice and it spits out five dice in a row it then grabs them back and the next turn does the same. He will manually create one time pads for you at a cost of $500, good for 10,000 characters. No machine, not even a simple typewriter is used. They are written out by hand and you get both copies. He keeps no records of who buys them. Swiss banks now use them to protect their clients transactions after the US got a court order for computer records of US Taxpayers. Now not even the banks know.
There is an encryption program out there named Vial 7 - Only way to get a copy is if you know the person. Each copy is made to order and it will only work on the users computer. He hard codes the key into the program and puts the location of the file somewhere on the computer at the request of the client. When you try to use the program it looks for the key and if it's not found it will close the program, so everyone that wants to communicate with that program they have to have a custom made version to work on their computer. The encryption math is said to make RSA look like 1+1. If you are not government USA, you will never own it. After it locates the key to use it then the real encryption begins and if you use the same password every time, the encryption out put will always be different, that means there is no standard algorithm with the exception of unlocking the program for use. Estimated bit strength - Unknown because the more text there is the higher the bit strength gets.
This video was such a gem that it explained almost everything of the concept clearly in just a couple of minites Thanks mate, you made me very happy today
Amazing video. TO ANYONE CONFUSED: LEARN ABOUT THE EUCLIDEAN ALGORITHM AND THEN STUDY THE EXTENDED EUCLIDEAN ALGORITHM INDEPENDENT OF RSA. That might help.
OMG! so I am being taught Maths in uni and its basically everything in this getting me ready for next year. I find it hard to follow the lecturer sometimes and this is amazing! I need to also program a crypto algorithm and this gives me a good base! THANK YOU!
Good explanation, but is important to point that e must be coprime with phi and N. With small numbers, it's relatively easy to pick a value for e, but if p and q have 30 digits each...
Thanks for the video. It helped that I already understood the process, but this is still useful. It would perhaps have been informative to explain to people why we use phi = (p-1)(q-1), but hopefully they will search the Internet to see why that is so.
Thank you very much for this video! It is of excellent quality and I could understand it easily despite I'm only at secondary school. It is the best explanation I've come across both in print and on the internet. Many thanks!
This is actually super useful for what I am currently working on. I'm attempting to generate rsa keys using a seeded rng which uses bitcoin's bip39 seed or "mnemonic phrase".
A simple trick to get the d as well: d = e-1 mod φ(n). Let's take the example in the video: e = 7 φ(n) = 40 7^-1 mod 40 = 23 and that's how you can get it without going through the steps of the Extended Euclidean Algorithm
to find d : (k*PHI(N) + 1)/e. increment k by 1 until the answer is a round number. EX: ((1x1872) + 1 )/7 = 267.571... (not working, not a round number) ---> increment k by 1---> ((2x1872) + 1)/7 = 535 .... so d = 535 in that case. now you can build a simple program to find d , using this concept and loops
Minor mistake at 6:28, you said the result is two thousand five hundred seven, and we can see it is 2557. Cheers though, this is the best RSA tutorial I've found to date.
Dude, this has helped amounts that you can't even imagine - thank you so much! 'Liked' the video too. I'm trying to write a bit of code to replicate RSA's encryption method, but was struggling to work out how to calculate 'd', and this worked wonders. Thank you again. Just a quick query though, how did you get -34 MOD 40 to equal 6? Mathematically, doesn't this equal -34? When I get a negative number, should I be adding the value of phi (until the value becomes positive) instead of MOD'ing the value by phi?
39 MOD 40 = 39 100 MOD 40 = 20 because there's 20 LEFT! after subtracting 40 two times. so, you don't try to see how much less -34 is than 0, you try to find out how much MORE -34 is than -40. Which is 6.
I wish you have explained 1) how does one generate 2048 bit primes p and q and 2) how computationally expensive it is to raise large m to the power large d mod large n when decrypting? How do you compute 5634644664688854133766886678^7754467997556567 mod 344346456654567776554345667885677777779 for example? Apart from that the explanation is clear, thanks for the video!
Use built-in pow() function in Python3.8 (takes milli-seconds to answer for huge numbers) >>> pow(5634644664688854133766886678, 7754467997556567, 344346456654567776554345667885677777779) 216531167112280961897015422503817866282
u made my day & saved my time & I love you not rly but great video & u explained everything so well & simply that even I could follow & now I wrote a working python script & I'm happy ^^
Hello, very nice explanation. Now, I read somewhere that if I want to have a 8bits key, my 'n' needs to be less than 2^(8), but I saw many resolutions where they use a 'n' that is > 2^(key lenght that they want). Could someone light me up?
There's a significant disadvantage to your swift method of finding d. Not many people do it this way, which means if a student doesn't understand your method, he's hosed if he searches elsewhere. Also, when you mentioned the Euclidean and Extended Euclidean, you only assured we'll be getting to that later. But you never actually pointed out that we have gotten there once we started up on finding d. I happen to recognize where the EucAlgorithms came in but only because I've spent the last three weeks or so studying the damn stupid formula and falling FURTHER behind in my class as a result. I would remedy this if I were you. That said, however, this is a very good tutorial. At last, at fucking LAST I understand what all these formulas are for in RSA. Even with all the TH-cam videos available, up until this point, I had been bashing my head against the wall, trying to figure out, "Euler! Phi! Totient! GCD! Extended GCD! Euclidean! Extended Euclidean! What in the fuck am I studying this shit for?!?!" So thank you for clearing this up.
Hey ++Anthony The only confusion I'm getting is that d value is not the greatest common divisor. Check with these values p=5 q=7, e=5, n=35. The value of 'd' I get is 5. But in another solution it is 29.
Hi! I love your video and it is helping me a lot with my Internal Assessment from IB Maths HL. I really need to do something original with RSA encryption (or look at it at a different way), so I was wondering if you (or anyone reading this comment) could have any idea about an original idea or a further step to RSA encryption. Thanks ;)
I would make a big distinction in RSA between asymmetric encryption and public-key encryption. If you use a well-known and small 'e', you have public key, but can't support 'asymmetric' key encryption. With 'asymmetric' key encryption, 'e' and 'd' have the same properties; and are equally secret. I use it to make digitally signed tokens such that you don't know the plaintext until you produce a witness that you performed verify to extract a secret to decrypt the signed claims. That way, the signer distribute the verify key to those who are allowed to VERIFY. It's not totally public, because it's (n,e), but signer has (n,d,e). This allows tokens to be passed around so that man-in-the middle can't decode the claims, and the verifier can only extract verified claims. ie: the current way of checking signatures (plaintext,Sign(H(plaintexty))=sig) has security problems. The main one being that you allow people to not verify the signatures; something that is very common in the hands of web developers. And the other is in leaking the tokens to intermediate proxies.
A little python3 to calculate 'd': Note that using big primes will take a while and you will need to increase the range by a good amount. e = 17 # part of public key p = 61 # prime, keep secret q = 53 # prime, keep secret n = p * q # part of public key phi = ((p - 1) * (q - 1)) # phi of n d = [] # private key for num in range(3, 5000, 2): # if no answer is found, increase range (the 5000) poss_d = (e * num) % phi if poss_d == 1: d.append(num) else: pass for each in d: print(each)
This is the best RSA explanation I've seen
me too
Better explained than my professor in college ... for which i pay hefty tuition fee each semester. lol
@@fnamelname2445the only thing i don't understand is mod how is it used and like what is it
@@sharonomonua1747 Mod or modulo only returns the remainder of a division operation. For instance, if you divide 5 into 5, the result is 1. But if you divide 5 into 3, the remainder is 2. Therefore, we write 5 modulo 3 = 2.
These videos might help:
1 - th-cam.com/video/6dZLq77gSGU/w-d-xo.html
2 - th-cam.com/video/4zahvcJ9glg/w-d-xo.html
Cleanly explained without messy hand written scribbles many TH-cam publishers practice
You spent your time to save our time, double likes from me
I was trying to understand the Wikipedia page on this topic with some difficulty. Your video did an excellent job of explaining it simply. Thanks a lot.
The Extended Euclidean Algorithm method you've shown here was absolutely stellar. It made my job very easy. Thanks a ton, mate.
Nice simple introduction and the slow transitioning of deeper and technical understanding with step by step interactivity in processing the RSA algorithm. Finally, ending with a real life example using Amazon's cart totally amazed me how it all works together. I'm sharing this with one of my Math Faculty members who teaches math for teachers, she'll be impressed to see how cryptography applies in real life and that most people don't know it. Thank you for taking the time out and scripting this too, good job, and an A+!
I just wanted to say that the way you showed the extended Euclidean algorithm was not something I had seen before and it made my work SO much easier. You've more-than earned my like.
extended euclidean algorithm is far easier than this technique and less time consuming. whereever you go there's just a matter of time and if you are slower then no one cares :)
As Edward Snowdon said recently and as Gordon Welchman said 70 years ago, a computer generated algorithm thats creates a cypher can always be decrypted. The only true unbreakable encryption is a non computer generated one time pad. Its still used today. There is a guy in Switzerland who has a barrel with 50,000 dice and it spits out five dice in a row it then grabs them back and the next turn does the same. He will manually create one time pads for you at a cost of $500, good for 10,000 characters. No machine, not even a simple typewriter is used. They are written out by hand and you get both copies. He keeps no records of who buys them. Swiss banks now use them to protect their clients transactions after the US got a court order for computer records of US Taxpayers. Now not even the banks know.
Sure it can be decrypted, it just takes 1000 years
I'm very interested to learn more! Do you know what the non-computer generated method is called? I'm having trouble finding it.
There is an encryption program out there named Vial 7 - Only way to get a copy is if you know the person. Each copy is made to order and it will only work on the users computer. He hard codes the key into the program and puts the location of the file somewhere on the computer at the request of the client. When you try to use the program it looks for the key and if it's not found it will close the program, so everyone that wants to communicate with that program they have to have a custom made version to work on their computer. The encryption math is said to make RSA look like 1+1. If you are not government USA, you will never own it. After it locates the key to use it then the real encryption begins and if you use the same password every time, the encryption out put will always be different, that means there is no standard algorithm with the exception of unlocking the program for use. Estimated bit strength - Unknown because the more text there is the higher the bit strength gets.
They can use cryptographic random number generators
I spent my life searching for this video. I am eternally grateful.
This video was such a gem that it explained almost everything of the concept clearly in just a couple of minites
Thanks mate, you made me very happy today
You have the best explanation from all the video's ive seen regarding RSA. Thanks so much!
Very good explanation of the RSA algorithm, one of the best I've seen on TH-cam.
Thank you for making this easy to understand! I am no good with math but I like to be able to use it from time to time! 😀
I really have to say that was top notch, clear, simple, articulate. Thank You!
Amazing video.
TO ANYONE CONFUSED: LEARN ABOUT THE EUCLIDEAN ALGORITHM AND THEN STUDY THE EXTENDED EUCLIDEAN ALGORITHM INDEPENDENT OF RSA.
That might help.
more importantly the eulers theorem
Dude... you are a time saver, thank you very much for this great and clear video
Excellent explanation! You reveal the magic behind the RSA encryption-decryption algorithm!
OMG! so I am being taught Maths in uni and its basically everything in this getting me ready for next year. I find it hard to follow the lecturer sometimes and this is amazing! I need to also program a crypto algorithm and this gives me a good base! THANK YOU!
This has to be one of the best if not the very best explanation of the RSA algorithm that i've come across, Thank you!
Best video on RSA mathematics..so far and finally i am able to get maths behind RSA
Fantastic Job. Like others said , "By far the best Explanation of RSA Algorithm" after scraping the entire TH-cam
Good explanation, but is important to point that e must be coprime with phi and N. With small numbers, it's relatively easy to pick a value for e, but if p and q have 30 digits each...
no need to coprime with N, just coprime to phi
@@nafiz1938 whatever, same problem because of big numbers.
@@marciocastro7101 Ever heard of Fermat primes? It shouldn't take you longer than a fraction of a millisecond to find a suitable e.
This is great explanation. Helped me to solve d for (e,N)=(53,299) and encode(m)=171. Thanks a lot.
Thank you so much. I have confused about RSA for a while , I just watched your video and now I clearly understand about RSA Algorithm. Thanks so much.
Thanks for the video. It helped that I already understood the process, but this is still useful. It would perhaps have been informative to explain to people why we use phi = (p-1)(q-1), but hopefully they will search the Internet to see why that is so.
Thank you very much for this video! It is of excellent quality and I could understand it easily despite I'm only at secondary school. It is the best explanation I've come across both in print and on the internet. Many thanks!
what other reads have you found in print that's this intuitive? (just curious)
@@freewheelburning8834 There was a section about this in Marcus du Sautoy's book, The Music of Primes. I recommend it, a fascinating read!:)
thanks,
the way to find 'd' using a short-cut version of the EEA is a life saver :)
Very well explained, it helped me a lot. Good, simple graphics and good, timed voice. THANKS!
This video makes it much easier to understand. Thanks a lot!
Anthony, great work sir. I appreciate your effort, very well done and you know the topic inside-out. Kudos to you man!
Terrific video Anthony, I used it to teach the mathematics of RSA and to write an example Java program for encryption and decryption.
This is actually super useful for what I am currently working on. I'm attempting to generate rsa keys using a seeded rng which uses bitcoin's bip39 seed or "mnemonic phrase".
thank you very much . i was confuse before about how to get d bt i am now satisfied with explanation.
Thank you, I got stuck implementing the RSA in Python at "d". your calculation path was easy to implement.
Use d = pow( e, -1, (p-1)*(q-1) ) in Python3.8 built in function (not math.pow).
Best explanation I could find on TH-cam. Thanks!
the best course I've ever seen about rsa !!!!
This is awesome Tony! Thanks for creating and sharing! Hope to see more like it :)
One of the best explanations that i found on the topic. thankx a lot
Finally got it, now I can complete my math's paper. Hallelujah & thank you
wow awesome video...i finally found short and clear cut explanation of algorithm to find d.
thank u so much for this awesome video
Its very good description of RSA .I am became fan.................
A simple trick to get the d as well: d = e-1 mod φ(n). Let's take the example in the video:
e = 7
φ(n) = 40
7^-1 mod 40 = 23
and that's how you can get it without going through the steps of the Extended Euclidean Algorithm
Nice, this is a very nice and clear explanation.
Well done (y)
to find d : (k*PHI(N) + 1)/e. increment k by 1 until the answer is a round number. EX:
((1x1872) + 1 )/7 = 267.571... (not working, not a round number) ---> increment k by 1--->
((2x1872) + 1)/7 = 535 .... so d = 535 in that case.
now you can build a simple program to find d , using this concept and loops
wouldnt this take very long if ur numbers are huge?
thank u, it helped...
Use Python3.8 built-in function d = pow(e, -1, phi) for mod inverse calculations if you don't want to implement on your own.
My mind is blown, the shortcut method. Nice 👍
This is hands down the best RSA video out there. Too bad it took me so long to find it >.
That was Excellent, Anthony !
Great Work !
Minor mistake at 6:28, you said the result is two thousand five hundred seven, and we can see it is 2557. Cheers though, this is the best RSA tutorial I've found to date.
Thank you very much! It was awesome. Nice and clear explanation.
Useful ^ 4096 = A better word to be used at the end of the video. Thanks for sharing.
Thanks for this terrific explanation.
Dude, this has helped amounts that you can't even imagine - thank you so much! 'Liked' the video too. I'm trying to write a bit of code to replicate RSA's encryption method, but was struggling to work out how to calculate 'd', and this worked wonders. Thank you again.
Just a quick query though, how did you get -34 MOD 40 to equal 6? Mathematically, doesn't this equal -34? When I get a negative number, should I be adding the value of phi (until the value becomes positive) instead of MOD'ing the value by phi?
39 MOD 40 = 39
100 MOD 40 = 20 because there's 20 LEFT! after subtracting 40 two times.
so, you don't try to see how much less -34 is than 0, you try to find out how much MORE -34 is than -40. Which is 6.
+Jim Vekemans ah, this makes complete sense. So you simply just take the absolute value - thank you for your help!
Very descriptive of the mathematics. Awesome.
Great work Anthony. Thank you kindly.
I wish you have explained 1) how does one generate 2048 bit primes p and q and 2) how computationally expensive it is to raise large m to the power large d mod large n when decrypting? How do you compute 5634644664688854133766886678^7754467997556567 mod 344346456654567776554345667885677777779 for example? Apart from that the explanation is clear, thanks for the video!
Use built-in pow() function in Python3.8 (takes milli-seconds to answer for huge numbers)
>>> pow(5634644664688854133766886678, 7754467997556567, 344346456654567776554345667885677777779)
216531167112280961897015422503817866282
u made my day & saved my time & I love you
not rly but great video & u explained everything so well & simply that even I could follow & now I wrote a working python script & I'm happy ^^
Thanks a ton. Immensely helpful explanation.
So clear and crisp
Thank you for this awesome and clear tutorial.
In the last example, if you calculate 3 * 6219 mod 2328 = 33 not 1
Hello, very nice explanation. Now, I read somewhere that if I want to have a 8bits key, my 'n' needs to be less than 2^(8), but I saw many resolutions where they use a 'n' that is > 2^(key lenght that they want). Could someone light me up?
this is a great explanation of rsa. thanks a lot.
Thank you, that was clear and to the point.
Thank the lords for this video!
I really liked your explanation
Best explanation 👍
Thanx bro......it help me a lot
thank you, your explanation was just great.
There's a significant disadvantage to your swift method of finding d. Not many people do it this way, which means if a student doesn't understand your method, he's hosed if he searches elsewhere. Also, when you mentioned the Euclidean and Extended Euclidean, you only assured we'll be getting to that later. But you never actually pointed out that we have gotten there once we started up on finding d. I happen to recognize where the EucAlgorithms came in but only because I've spent the last three weeks or so studying the damn stupid formula and falling FURTHER behind in my class as a result. I would remedy this if I were you.
That said, however, this is a very good tutorial. At last, at fucking LAST I understand what all these formulas are for in RSA. Even with all the TH-cam videos available, up until this point, I had been bashing my head against the wall, trying to figure out, "Euler! Phi! Totient! GCD! Extended GCD! Euclidean! Extended Euclidean! What in the fuck am I studying this shit for?!?!"
So thank you for clearing this up.
Use pow() the built-in function in Python3.8 - e.g. d = pow(e, -1, (p-1)*(q-1) )
Thank you this was very helpful
this video is PERFECTION
Excellente video and explication, GREAT JOB!!!!
Very well explained
Hey ++Anthony The only confusion I'm getting is that d value is not the greatest common divisor. Check with these values
p=5 q=7, e=5, n=35. The value of 'd' I get is 5. But in another solution it is 29.
phi = (p-1)x(q-1) = 4x6=24. So, d = 5 (mod 24) = [5, 29, 53, 77, 101, 125, 149, 173, 197, 221, ...]. Hence infinite solutions > 24.
Best explanation ever.. Thank you.
Can I get the video for Elliptic Curve Cryptography, from you, please?
Good work Anthony...
You are the best brohh big thanks
THANKSS A LOT
its working with all
except p=11 q=3
gives d=2 and the right answer is d=3 :)
for p=11 and q=3, then n=33 and Phi=20, if e=3 then d=7.
you may not choose e=2 as it has co-factor with Phi=20.
Thank you ... this helped me a lot. :-)
Hi! I love your video and it is helping me a lot with my Internal Assessment from IB Maths HL. I really need to do something original with RSA encryption (or look at it at a different way), so I was wondering if you (or anyone reading this comment) could have any idea about an original idea or a further step to RSA encryption.
Thanks ;)
Super Explanation!!!!! Great Thank you
Love you man! Thanks for the video.
you are amazing!!! good work, you got a new sub
I will decompose the RSA of any complexity into multipliers. Fast and not expensive.
Excellent video!
I would make a big distinction in RSA between asymmetric encryption and public-key encryption. If you use a well-known and small 'e', you have public key, but can't support 'asymmetric' key encryption. With 'asymmetric' key encryption, 'e' and 'd' have the same properties; and are equally secret.
I use it to make digitally signed tokens such that you don't know the plaintext until you produce a witness that you performed verify to extract a secret to decrypt the signed claims. That way, the signer distribute the verify key to those who are allowed to VERIFY. It's not totally public, because it's (n,e), but signer has (n,d,e). This allows tokens to be passed around so that man-in-the middle can't decode the claims, and the verifier can only extract verified claims. ie: the current way of checking signatures (plaintext,Sign(H(plaintexty))=sig) has security problems. The main one being that you allow people to not verify the signatures; something that is very common in the hands of web developers. And the other is in leaking the tokens to intermediate proxies.
thank you very much...Very useful nd very clear
@Anthony Vance Thank you very much for such a useful video.
Thanks,......
you are a life saver
You sir, just got yourself a sub!
A little python3 to calculate 'd':
Note that using big primes will take a while and you will need to increase the range by a good amount.
e = 17 # part of public key
p = 61 # prime, keep secret
q = 53 # prime, keep secret
n = p * q # part of public key
phi = ((p - 1) * (q - 1)) # phi of n
d = [] # private key
for num in range(3, 5000, 2): # if no answer is found, increase range (the 5000)
poss_d = (e * num) % phi
if poss_d == 1:
d.append(num)
else:
pass
for each in d:
print(each)
Use pow() the built-in function in Python3.8 - e.g. d = pow(e, -1, (p-1)*(q-1) ) = pow(17, -1, 60*52) = 2753.
Very very very nice. Thank you so much
Fantastic!! Good job!
Great video! Thanks!
Thanks a lot, I have a question "Can I used same the way to generate the key to steganography for embedding data in an image?"
clear and concise!
at 4:55 it would take trillions of trillions of years to crack an rsa like that
Great work
great video. many thanks.
Thanks for this.
thanks this really helped me