@@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 - ua-cam.com/video/6dZLq77gSGU/v-deo.html 2 - ua-cam.com/video/4zahvcJ9glg/v-deo.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 :)
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
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!
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.
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!
Amazing video. TO ANYONE CONFUSED: LEARN ABOUT THE EUCLIDEAN ALGORITHM AND THEN STUDY THE EXTENDED EUCLIDEAN ALGORITHM INDEPENDENT OF RSA. That might help.
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...
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
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 ^^
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
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.
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?
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.
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.
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 UA-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.
The initial 8-bit LFSR 10101010 and the feedback tabs polynomial is x5+x3+x1+1. Use Excel to generate a keystream of a sufficient length to encrypt your name “space”, showing all the steps?
Excellent video, I've read some resources about RSA but there is still something that confuses me: what do you all mean to "choose" e, can I choose any value for e? Which usually is 3 or 65537 on modern applications. I mean, is "3" always going to be coprime with any phi? Like in the example in 10:15 how did you found that e=7 ?
e can be any Prime, since primes are co-primes with any PHI. Should be large with very few 1 bits - so 0x10001 = 65537 is one of the best choice for fast encryption (during key exchange) and signature verification.
Hi, I have a few quires... What would be the maximum message length would it go up to.?... How would you perform (X power Y) certainly I cant define it as Integer or float when I perform a small C program?...How can I perform division same problem as before.... Overall the processor available is either 32 bit or 64 bit processor how will it compute such a big algorithm...?....
+Heramban S There are libraries which handle big integers for most languages (called BigInt or similar). These generally include a function called something like PowerMod, for performing raising a number to a large exponent, mod x. In PHP 5 there is a library called BCMath which performs math operations on any number expressed as a string of any length, hundreds or thousands of digits long. Once you've realised that this is possible, you can easily write your own functions for arbitrary size number math.
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.
I've knocked together a primitive Python implementation of this and I've got two problems so far. One is that the algorithm to derive d occasionally results in a divide-by-zero error, which I've solved simply by scrapping it and starting over with a new value of e. It's still quick but there must be a more elegant solution to avoid the error in the first place? The second problem is that, for anything more than three-digit values for p and q, the actual encryption and decryption is incredibly slow. For four-digit values it clocks in at almost a minute and a half. Why is it so slow when this process happens routinely for much larger primes than anything I'm using?
My guess is that you may need to watch ua-cam.com/video/EHUgNLN8F1Y/v-deo.html (Modular Exponentiation video, much faster method) Also, encrypt data in chunks that will not exceed n in value if not done that way already. I'm pretty much doing the same thing that you are doing, writing in python.
It does lose information I think - as I understand it, the limit of RSA is that the message can't be larger than N. In a real example, N is so huge that the message would have to be very long indeed for that to be a problem.
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 had a problem when applying the extended euclids theorom to my example. One one occasion i was left with such a high minus number, that when mod it with my Phi number, it returned another -minus number, therefore i could not continue the algorithm, as yours provided in the xample returned a positive after
+michael 0184 did you try putting the mod calculation into that wolfram site? Also the answer i got from modulus at the end of the calculation was negative also, but if you mod it again or a few times depending on the number your modding by, eventually you get the positive, which explains the answer i got from the wolfram site. For the record my final inputs for the Euclid algorithm to find d was -617 mod 360. which would give me - 257, but if you mod it again it gives 103, which matches the answer wolframAlpha gives :)
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 - ua-cam.com/video/6dZLq77gSGU/v-deo.html
2 - ua-cam.com/video/4zahvcJ9glg/v-deo.html
Cleanly explained without messy hand written scribbles many UA-cam publishers practice
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.
You spent your time to save our time, double likes from me
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 spent my life searching for this video. I am eternally grateful.
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 :)
Very good explanation of the RSA algorithm, one of the best I've seen on UA-cam.
The Extended Euclidean Algorithm method you've shown here was absolutely stellar. It made my job very easy. Thanks a ton, mate.
You have the best explanation from all the video's ive seen regarding RSA. Thanks so much!
This is great explanation. Helped me to solve d for (e,N)=(53,299) and encode(m)=171. Thanks a lot.
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!
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
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!
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
But it's never truly random, that's why it has to he done manually
Best video on RSA mathematics..so far and finally i am able to get maths behind RSA
I really have to say that was top notch, clear, simple, articulate. Thank You!
Fantastic Job. Like others said , "By far the best Explanation of RSA Algorithm" after scraping the entire UA-cam
Excellent explanation! You reveal the magic behind the RSA encryption-decryption algorithm!
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! 😀
thanks,
the way to find 'd' using a short-cut version of the EEA is a life saver :)
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.
Dude... you are a time saver, thank you very much for this great and clear video
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!:)
thank you very much . i was confuse before about how to get d bt i am now satisfied with explanation.
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
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).
Terrific video Anthony, I used it to teach the mathematics of RSA and to write an example Java program for encryption and decryption.
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.
Very well explained, it helped me a lot. Good, simple graphics and good, timed voice. 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".
Its very good description of RSA .I am became fan.................
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!
Best explanation I could find on UA-cam. Thanks!
the best course I've ever seen about rsa !!!!
Finally got it, now I can complete my math's paper. Hallelujah & thank you
This is hands down the best RSA video out there. Too bad it took me so long to find it >.
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
My mind is blown, the shortcut method. Nice 👍
wow awesome video...i finally found short and clear cut explanation of algorithm to find d.
thank u so much for this awesome video
One of the best explanations that i found on the topic. thankx a lot
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 for this terrific explanation.
This is awesome Tony! Thanks for creating and sharing! Hope to see more like it :)
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
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.
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.
Very descriptive of the mathematics. Awesome.
Nice, this is a very nice and clear explanation.
Well done (y)
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?
Useful ^ 4096 = A better word to be used at the end of the video. Thanks for sharing.
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.
That was Excellent, Anthony !
Great Work !
this video is PERFECTION
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!
Great work Anthony. Thank you kindly.
Thanks a ton. Immensely helpful explanation.
I really liked your explanation
Best explanation 👍
Thank you for this awesome and clear tutorial.
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.
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 UA-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) )
You are the best brohh big thanks
this is a great explanation of rsa. thanks a lot.
Thank you this was very helpful
So clear and crisp
Very well explained
Excellente video and explication, GREAT JOB!!!!
In the last example, if you calculate 3 * 6219 mod 2328 = 33 not 1
thank you very much...Very useful nd very clear
I will decompose the RSA of any complexity into multipliers. Fast and not expensive.
Thank you, that was clear and to the point.
Best explanation ever.. Thank you.
Can I get the video for Elliptic Curve Cryptography, from you, please?
The initial 8-bit LFSR 10101010 and the feedback tabs polynomial is x5+x3+x1+1. Use Excel to generate a keystream of a sufficient length to encrypt your name “space”, showing all the steps?
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?"
Excellent video, I've read some resources about RSA but there is still something that confuses me: what do you all mean to "choose" e, can I choose any value for e? Which usually is 3 or 65537 on modern applications. I mean, is "3" always going to be coprime with any phi? Like in the example in 10:15 how did you found that e=7 ?
e can be any Prime, since primes are co-primes with any PHI. Should be large with very few 1 bits - so 0x10001 = 65537 is one of the best choice for fast encryption (during key exchange) and signature verification.
Love you man! Thanks for the video.
you are amazing!!! good work, you got a new sub
Hi, I have a few quires... What would be the maximum message length would it go up to.?... How would you perform (X power Y) certainly I cant define it as Integer or float when I perform a small C program?...How can I perform division same problem as before.... Overall the processor available is either 32 bit or 64 bit processor how will it compute such a big algorithm...?....
+Heramban S There are libraries which handle big integers for most languages (called BigInt or similar). These generally include a function called something like PowerMod, for performing raising a number to a large exponent, mod x. In PHP 5 there is a library called BCMath which performs math operations on any number expressed as a string of any length, hundreds or thousands of digits long. Once you've realised that this is possible, you can easily write your own functions for arbitrary size number math.
Thank the lords for this video!
Good work Anthony...
Thanks,......
you are a life saver
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.
How to choose e, just a small prime that doesn't share a factor with φ(n) ?
Super Explanation!!!!! Great Thank you
How did you find your own rsa public number? Which as result of both of your private prime numbers multiplication?
Very very very nice. Thank you so much
I've knocked together a primitive Python implementation of this and I've got two problems so far. One is that the algorithm to derive d occasionally results in a divide-by-zero error, which I've solved simply by scrapping it and starting over with a new value of e. It's still quick but there must be a more elegant solution to avoid the error in the first place?
The second problem is that, for anything more than three-digit values for p and q, the actual encryption and decryption is incredibly slow. For four-digit values it clocks in at almost a minute and a half. Why is it so slow when this process happens routinely for much larger primes than anything I'm using?
My guess is that you may need to watch ua-cam.com/video/EHUgNLN8F1Y/v-deo.html
(Modular Exponentiation video, much faster method)
Also, encrypt data in chunks that will not exceed n in value if not done that way already. I'm pretty much doing the same thing that you are doing, writing in python.
Use python3.8 built in functions like d == pow( e, -1, (p-1)*(q-1) ) and they are pretty fast even with 2048 bit RSA keys.
Can somebody please explain to me how the message doesn't lose information when you calculate modulo n? As modulo is not an injective function?
It does lose information I think - as I understand it, the limit of RSA is that the message can't be larger than N. In a real example, N is so huge that the message would have to be very long indeed for that to be a problem.
I guess I'm getting something wrong but 5:27 - you want to calculate x^2753 ?
You're the best!
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 ;)
great video. many thanks.
I had a problem when applying the extended euclids theorom to my example. One one occasion i was left with such a high minus number, that when mod it with my Phi number, it returned another -minus number, therefore i could not continue the algorithm, as yours provided in the xample returned a positive after
+michael 0184 did you try putting the mod calculation into that wolfram site? Also the answer i got from modulus at the end of the calculation was negative also, but if you mod it again or a few times depending on the number your modding by, eventually you get the positive, which explains the answer i got from the wolfram site. For the record my final inputs for the Euclid algorithm to find d was -617 mod 360. which would give me - 257, but if you mod it again it gives 103, which matches the answer wolframAlpha gives :)
When you calculate d, what happens if you get 0 instead of 1? e.g. p=11 q=13. Thanks.
I think you picked e=3 which is wrong because GCD 120, 3 != 1 e.o.w 120 and 3 are not co-prime
the first e you can choose with 11,13 to use is 7
You sir, just got yourself a sub!