The constraints for e is just {2 < e < r; gcd(e, r) = 1}, and it has to follow those constraints so that the encryption is one-to-one rather than many-to-one, where in the latter case it would not be reversible. More recent versions of RSA use the Carmichael's function, in this case λ(n), (which simplifies to lcm(p - 1, q - 1)) in those constraints rather than r (which is just the Eurler's totient function of n). It achieves the same results but has the benefit of faster decryption.
Extended euclidean algorithm to find an inverse. I'll walk you through it. This is in text but I'll do my best to explain it in English, simply. e^(-1) mod (r) implies that e multiplied by something results in a number, when taken mod r, is 1. Writing that out, e(x) = 1 mod r Extended euclidean algorithm can get us x. r = 20, e = 3. Putting this fancy algorithm into plain english, here's how it goes: A bigger number = the smaller number (times something) + remainder the smaller number = remainder (times something) + a new remainder our first remainder = the second remainder ( times something) + a new remainder and it just loops until the final remainder is 1 20 = 3(s) + r; s = 6, r = 2; 20 = 3(6) + 2 3 = 2(1) + 1 Now above, where there was a '=', rewrite with a '-', and where there was a '+', rewrite with an 11. 20 = 3(6) + 2 turns into 20 - 3(6) = 2 3 = 2(1) + 1 turns into 3 - 2(1) = 1 Let me just isolate those two lines for clear reference: 20-3(6) = 2 3 - 2(1) = 1 So from here, we walk it back upwards. Trying to figure out what number that our original (x) was. Start with the =1 line. 3 - 2(1) = 1 We also know that 20-3(6)=2, so we can sub in 20-3(6) for 2 We get 3 - 1(20 - 3(6)), but for simplicity in text, I'm going to rewrite this as: 3- (20-6(3)) = 1 Now combining like terms 3 - 20 + 6(3) = 1 7(3) - 20 = 1 Take modulos of 20 and it just becomes 7(3) = 1 Well guess what? We wanted to find 3 (times something) = 1 Our (times something) is 7!
You can find d by using the equation d*e=1mod(r). You want to find the smallest value of d which, when multiplied by e, results in 1 mod(r). For example d*3=1mod(20). The value d in this case is 7 since 7*3=21 and 21mod(20) is equal to 1.
@@SirArghPirate 1/3 mod 20 means: 3 * x = 1 mod 20. you can use the advanced euclidean algorithm to find x or if its easy to see like in this case: x = 7. try it: 3*7 = 21 mod 20 = 1
your d formula is different to what i have in my course material. what i have is d = e^-1 mod( λ(n) ) now λ(n) = lcm(p-1, q-1) the way you do the d also gets the right answer but answer must be divided by 1 but in your example i get 3 not 7. i think the right d formula is d = 1 / e^-1 mod(r) -------------new addition--------- ok so i found out a shortcut. to find d just try this formula first because if numbers are small enough you can just get the d directly. e * d ≡ 1 mod(r) so here e = 3 and r = 20 so 3 * d ≡ 1 mod(20) if you know how to mod words we can see by putting d=7 we get 21 ≡ 1 mod(20) if you dont know how mod words then it just means 21 remove as many 20 as you can until you have remaining 1. ya when i first learned mod the notation was going above my head but trick is not to look at is a equality. its triple bar not equal sign. so 21 ≡ 1 mod(20) this expression would be same even if i wrote it as 41 ≡ 1 mod(20) because that just means if i did 41 - 20 - 20 i would have 1 remaining. r = (p-1)(q-1)
@@guilhermejose4126 please write it down less understandable. O wait, not possible. That's why notation is important. The video also completely fails on that note
I thought this was a lifesaver... until you said "everyone will let you use a calculator". I have to do this on an exam tomorrow and my professors not letting us use a calculator 💀
value of d is such that if we multiply d with e with mod r , the answer or remainder is 1 that's eculidian idk why he couldn't go for 10 seconds on this but regardless pretty helpful video. He multiplied e with 7 i.e 3*7 which is 21. 21mod20 is 1(where r=20). de mod(r) since 1 came because of 7 we take it for d
@@bashaier44 That is because the explanation is actually not very good for people who are trying to understand this perhaps for the first time. It is because: e=3 and r= 20 in the example so since 3*7=21 and 21= 20 + 1 that means 7 is the inverse of 3 in arithmetic modulo 20 (3*7 is a number that gives a remainder of 1 when divided by 20 that is what it means that 7 and 3 are multiplicative inverses modulo 20). d=7 is just the multiplicative inverse of e=3 modulo r=20 (the numbers used in the example) You can find the multiplicative inverse of any e modulo any r by using the Euclidean Algorithm, which always succeeds; but in simple examples like this with a little practice you can just "eyeball" it (which is what the author of the video did here)
I don't understand r. r = (p-1)(q-1) right? but why? Would the encryption and decryption work the same if you set r := (p+3)(q+3)? Would you change d = e^3 mod r in this scenario? Is this -1 just an arbitrary practice used in RSA? practically speaking, this doesn't really matter, but I need to understand it for it to click
r is the result of Euler's phi/totient function applied to n: r = phi(n) Sorry I can't answer why this function is used, but it's essentially the amount of numbers 1 to n that's coprime with n.
2:28 yes public e and n. thats fun when bit size is sasmall. we can brute force p and q get n calculate d. i have complete11 rsa challenges too bad they not offer money. and p q value was under 1000000 on couple python can do it 150minute. if they would be bout half what they could be could take year LOL and anyway we not need these after welearned how do it. we then just use tools what they made
The constraints for e is just {2 < e < r; gcd(e, r) = 1}, and it has to follow those constraints so that the encryption is one-to-one rather than many-to-one, where in the latter case it would not be reversible. More recent versions of RSA use the Carmichael's function, in this case λ(n), (which simplifies to lcm(p - 1, q - 1)) in those constraints rather than r (which is just the Eurler's totient function of n). It achieves the same results but has the benefit of faster decryption.
this dude just saved my finals, awesome video thank lord i found it
Thank you so much for this tutorial! I could not wrap my head around turning the concepts behind encryption into code before this.
Why doesn't this have more views??? Thank you so much !!
I love it! I'm looking forward to learn programming with python with your video.
Holy shit this was actually huge for an assignment, made it so much easier and less stressful
flawlessly explained bro! thank you
Really nice video....definitely simple and yet makes a lot of sense!
congrats on 200 subs!
How does D = 7? I don't understand that part. Is 7 just a random number that you are using as the message to send?
D is the result of the multiplicative inverse after the extended Euclidean algorithm
i don't get it either
this video is terrible, just find a new one lol
Extended euclidean algorithm to find an inverse.
I'll walk you through it. This is in text but I'll do my best to explain it in English, simply.
e^(-1) mod (r) implies that e multiplied by something results in a number, when taken mod r, is 1.
Writing that out, e(x) = 1 mod r
Extended euclidean algorithm can get us x.
r = 20, e = 3.
Putting this fancy algorithm into plain english, here's how it goes:
A bigger number = the smaller number (times something) + remainder
the smaller number = remainder (times something) + a new remainder
our first remainder = the second remainder ( times something) + a new remainder
and it just loops until the final remainder is 1
20 = 3(s) + r; s = 6, r = 2; 20 = 3(6) + 2
3 = 2(1) + 1
Now above, where there was a '=', rewrite with a '-', and where there was a '+', rewrite with an 11.
20 = 3(6) + 2 turns into 20 - 3(6) = 2
3 = 2(1) + 1 turns into 3 - 2(1) = 1
Let me just isolate those two lines for clear reference:
20-3(6) = 2
3 - 2(1) = 1
So from here, we walk it back upwards. Trying to figure out what number that our original (x) was. Start with the =1 line.
3 - 2(1) = 1
We also know that 20-3(6)=2, so we can sub in 20-3(6) for 2
We get 3 - 1(20 - 3(6)), but for simplicity in text, I'm going to rewrite this as: 3- (20-6(3)) = 1
Now combining like terms
3 - 20 + 6(3) = 1
7(3) - 20 = 1
Take modulos of 20 and it just becomes 7(3) = 1
Well guess what?
We wanted to find 3 (times something) = 1
Our (times something) is 7!
You can find d by using the equation d*e=1mod(r). You want to find the smallest value of d which, when multiplied by e, results in 1 mod(r). For example d*3=1mod(20). The value d in this case is 7 since 7*3=21 and 21mod(20) is equal to 1.
Simple AF, come back with more stuff dude!
So helpful and informational !!!
Thank you so much! The best explanation!!!
I don't get it; how does 3^(-1) % 20 equal 7 and not 0.33..
because its 1/3 mod(20) = 7
@@hammozeen but how? I type it into google and the answer is 0.33
@@SirArghPirate 1/3 mod 20 means: 3 * x = 1 mod 20. you can use the advanced euclidean algorithm to find x or if its easy to see like in this case: x = 7. try it: 3*7 = 21 mod 20 = 1
This is a different type of division called modular division. X^(-1) % Y means , find a number Z so that X * Z = 1 mod Y.
it’s not equal it’s congruence, google and ur calculator won’t do it right because it’s not exactly the literal inverted of 3
your d formula is different to what i have in my course material. what i have is d = e^-1 mod( λ(n) )
now λ(n) = lcm(p-1, q-1)
the way you do the d also gets the right answer but answer must be divided by 1 but in your example i get 3 not 7.
i think the right d formula is d = 1 / e^-1 mod(r)
-------------new addition---------
ok so i found out a shortcut. to find d just try this formula first because if numbers are small enough you can just get the d directly. e * d ≡ 1 mod(r)
so here e = 3 and r = 20
so 3 * d ≡ 1 mod(20)
if you know how to mod words we can see by putting d=7 we get 21 ≡ 1 mod(20)
if you dont know how mod words then it just means 21 remove as many 20 as you can until you have remaining 1. ya when i first learned mod the notation was going above my head but trick is not to look at is a equality. its triple bar not equal sign. so 21 ≡ 1 mod(20) this expression would be same even if i wrote it as 41 ≡ 1 mod(20) because that just means if i did 41 - 20 - 20 i would have 1 remaining.
r = (p-1)(q-1)
*patiently waits for the python program implementation*
Awesome!! well-explained thank you so much
how did he get d = 7? A normal mod calculation wont get you that
@@JulianGonzalez-ej2fi e = 3
r = 20
d * e 1(mod r)
d * 3 1(mod 20)
if d = 7, d * 3 = 21
21/20 rest 1
@@guilhermejose4126 please write it down less understandable. O wait, not possible. That's why notation is important. The video also completely fails on that note
I thought this was a lifesaver... until you said "everyone will let you use a calculator". I have to do this on an exam tomorrow and my professors not letting us use a calculator 💀
MAT246 Soheil
the whole modulo stuff is not possible, because when calculating d, the first mod value is always smaller than the second, which gives a syntax error
5:02 oh yes we have cipher text 13 so lets do
13^3 mod 33 =19
19^3 mod 33 = 28
28^3 mod 33 = 7 thats your private key
0:38 its not fix
e must be prime less than r and NOT factor of the r.
e mod r != 0
should be no problem if p and q is 100bit LOL
Dude how come you only made 1 video
value of d is such that if we multiply d with e with mod r , the answer or remainder is 1 that's eculidian idk why he couldn't go for 10 seconds on this but regardless pretty helpful video.
He multiplied e with 7 i.e 3*7 which is 21. 21mod20 is 1(where r=20).
de mod(r)
since 1 came because of 7 we take it for d
where did he get the 7 from the first place!
Hey I dont think there's a gaurentee that e can always be 3. If totient n is 72 then 3 is not relatively prime and does not fit the. requirements
Understood in minutes! Thanks
e = 19, to be more secure while keeping it less than r
At the end of both encryption and decryption we're doing mod n making it within the range of n
Meaning our initial messsage CANT be higher than n?
I don't understand how we find d=7 ??
same, i tried doing it but it is either wrong or I am not doing it right
@@bashaier44 That is because the explanation is actually not very good for people who are trying to understand this perhaps for the first time. It is because:
e=3 and r= 20 in the example so
since 3*7=21 and 21= 20 + 1
that means 7 is the inverse of 3 in arithmetic modulo 20 (3*7 is a number that gives a remainder of 1 when divided by 20 that is what it means that 7 and 3 are multiplicative inverses modulo 20).
d=7 is just the multiplicative inverse of e=3 modulo r=20 (the numbers used in the example)
You can find the multiplicative inverse of any e modulo any r by using the Euclidean Algorithm, which always succeeds; but in simple examples like this with a little practice you can just "eyeball" it (which is what the author of the video did here)
@@brunilda yo bro you mind me asking how do you revise for computer science A level
can we also have the xgcd video? thx
I am here at the comment section for the rsa python video, are you still there😂
Great video I love it hope you are doing well by the way
I don't understand r. r = (p-1)(q-1) right? but why? Would the encryption and decryption work the same if you set r := (p+3)(q+3)? Would you change d = e^3 mod r in this scenario? Is this -1 just an arbitrary practice used in RSA?
practically speaking, this doesn't really matter, but I need to understand it for it to click
r is the result of Euler's phi/totient function applied to n:
r = phi(n)
Sorry I can't answer why this function is used, but it's essentially the amount of numbers 1 to n that's coprime with n.
2:53 yes that easy. who send you message can also try crack your private key, but no need. he know what message is. he send it! LOL
2:28 yes public e and n. thats fun when bit size is sasmall. we can brute force p and q get n calculate d.
i have complete11 rsa challenges too bad they not offer money. and p q value was under 1000000 on couple python can do it 150minute.
if they would be bout half what they could be could take year LOL
and anyway we not need these after welearned how do it. we then just use tools what they made
Very Good Thank You!!
Return Connor.
Pls make a tutorial for aes
"Spanning tree" has a pretty good video on it
It would have been nice if you explained how you got d, since it is the hardest number to find in the exercise.
Where is the rsa with python😢
Where's that python tut
that was legitness
nice stuff
Hermiston Wall
i would love the teacher be like you, he make things harder, talking in mathematical way and so on, boring...
Schaefer Valleys
Noah Rue
Jaclyn Plaza
Herzog Islands
Carli Forges
Morissette Ramp
Benny Rue
Daugherty Point
thanks good work
Leonor Walk
thanks bro😚
Rosenbaum Walk
Fritsch Springs
Dagmar Estates
Marks Union
Green Ports
my calculator is literally useless lol
bro i love you
Thank you!
Lopez Gary Hall Cynthia Williams Melissa
Weimann Falls
Isai Highway
Donnelly Flat
Bailee Fork
legend
Jannie Pike
Elna Isle
Legend
Neoma Park
Chase Via
thanks!
Kelsie Neck
Brown Paul Martin Kimberly Rodriguez Laura
lemme give u a kiss
Irma Shore
Anahi Via
wag1 bruv.
lol video
worst vid ever wont recommend
Terrible video just because of not explaining well d
your video is as bad at explaining how to get to d like my professor's slides... waste of time
Dual_EC_DRBG
Legend