Please note that Euler's Theorem is conventionally given as a^[phi(n)] mod n = 1 if gcd(a, n) is 1. Then have: M¹ ⋅ M^[phi(n)x] mod n (timestamp: 14:26) = M ⋅ (M^[phi(n)])ˣ mod n --> exponent rules = M ⋅ (M^[phi(n)] mod n)ˣ --> b/c aᵐ mod n = (a mod n)ᵐ = M ⋅ (1)ᵏ --> by Euler's Theorem = M ⋅ 1 = M Apologies for any confusion
It's absolutely shocking how difficult it is to find proofs of well known theorems that go through the actual logic for why each steps was taken. Thank you for this.
This video is a great blessing! It's very hard to find details onto why this method works, but you provided perfect explanation, which fill in all the gaps for me ❤
You can do this here because the result, M, is less than N. If you have the mod of a product of 2 numbers, a and b, you can take a or b out so long as the result is less than n. AKA (ab)modN = a * (bmodN) if a * (bmodN) < N.
@@benhayter-dalgliesh5794 that makes sense, but why is that the case for M? Sorry its been 2 years I honestly forgot a bit. Thanks for the reply tho, that clears something up
@@AlexStormDrake Because M represents the message that is being encrypted/decrypted. And it is simply a condition that the message must be smaller than N. This is because the decryption process will never yield the original message if M > N because it is mod(N)
It is also worth noting that this video is not the best to watch to understand why RSA works. It has a few flaws, for example the modular arithmetic exponentiation law at 3:20 works for all values of a, not just when a
At 7:41 7d = 1 mod 3120 might be calculated using Extended Euclidean Algorithm - might require less computation than guessing the number. Aside from that the material explains the topic very well ;)
I might be wrong here but I think Euler’s Theorem is based on the proof he presented for Fermat’s Little Theorem stating that X^p-X is a multiple of P. Eg. 4^5-4 = 1020 is equal to 204 * 5 therefore a multiple of 5.
that's not the euler's theorem. Euler's theorem states that if a and n are coprime, then a^(phi(n)) mod n = 1, there is no positive integer x that's in the exponent of a
You are proving it using Euler's theorem but, Euler's theorem only work when GCD(M, n) = 1. So in the case that GCD(M, n) > 1 then this didn't prove how RSA still works in that situation
The Euler's theorem proof of correctness can be extended to show correctness for such cases, although in a practical system, GCD(M, n) > 1 is almost never the case. So proofs like this are generally considered good enough. But RSA does still work for GCD(M, n) > 1, it just requires a little extra maths to show it.
Please note that Euler's Theorem is conventionally given as a^[phi(n)] mod n = 1 if gcd(a, n) is 1. Then have:
M¹ ⋅ M^[phi(n)x] mod n (timestamp: 14:26)
= M ⋅ (M^[phi(n)])ˣ mod n --> exponent rules
= M ⋅ (M^[phi(n)] mod n)ˣ --> b/c aᵐ mod n = (a mod n)ᵐ
= M ⋅ (1)ᵏ --> by Euler's Theorem
= M ⋅ 1
= M
Apologies for any confusion
the original formula should be {M ⋅ (M^[phi(n)])ˣ} mod n.
How we can tell that M and n are relatively prime? Please answer
@@asmap3096 their greatest common factor is 1
@@asmap3096 N equal p.q (multiplication of 2 prime numbers), of course it cannot be divisible by any random integer M
It's absolutely shocking how difficult it is to find proofs of well known theorems that go through the actual logic for why each steps was taken. Thank you for this.
But how do we know that M^e < N? If this isn't the case it wouldn't work right?
there is a restriction how big the e can be compared to N, also the N which is used in the algorithm is a huuuge number compared to e
We don't know this at all. This video is not the best explanation of RSA. We know that M
@@benhayter-dalgliesh5794 i can't catch this
@@benhayter-dalgliesh5794 pls explain is M and n are relativel prime?
Finding this video, has me feeling the same when I found $100 bill in my dirty pants. While broke. While bored. God bless you.
This video is a great blessing! It's very hard to find details onto why this method works, but you provided perfect explanation, which fill in all the gaps for me ❤
At 14:45 you somehow take the M^1 out of the mod expression, which cannot be done, thus you cannot just simplify the other part to 1
You can do this here because the result, M, is less than N. If you have the mod of a product of 2 numbers, a and b, you can take a or b out so long as the result is less than n. AKA (ab)modN = a * (bmodN) if a * (bmodN) < N.
@@benhayter-dalgliesh5794 that makes sense, but why is that the case for M? Sorry its been 2 years I honestly forgot a bit. Thanks for the reply tho, that clears something up
@@AlexStormDrake Because M represents the message that is being encrypted/decrypted. And it is simply a condition that the message must be smaller than N. This is because the decryption process will never yield the original message if M > N because it is mod(N)
@@AlexStormDrake Note the decryption equation at 1:53, for this equation to work, M simply must be less than N
It is also worth noting that this video is not the best to watch to understand why RSA works. It has a few flaws, for example the modular arithmetic exponentiation law at 3:20 works for all values of a, not just when a
Well said😍
At 7:41 7d = 1 mod 3120 might be calculated using Extended Euclidean Algorithm - might require less computation than guessing the number. Aside from that the material explains the topic very well ;)
another note is the modular exponentiation law at 3:08 works for all values of A. Showing that it works only for A
holy moly thank you SOO much ! This is GOLD !
Hi there, just one question :
There is restriction on M that M must be less than N, but M^e may or may not be less than N, then how can we use Euler?
Abhinav Kumar that restriction is not necessary
@@joefagan9335 Is there a seperate proof that shows how the modular exponential law is still true when A>N?
did you ever find an answer
This is an amazing explanation!
I might be wrong here but I think Euler’s Theorem is based on the proof he presented for Fermat’s Little Theorem stating that X^p-X is a multiple of P. Eg. 4^5-4 = 1020 is equal to 204 * 5 therefore a multiple of 5.
Aarigato Sofia kun.
Thank you so much
Thank you! It made my day.
😊 🙏 😊
thanks for sharing with us!
that's not the euler's theorem. Euler's theorem states that if a and n are coprime, then a^(phi(n)) mod n = 1, there is no positive integer x that's in the exponent of a
You are proving it using Euler's theorem but, Euler's theorem only work when GCD(M, n) = 1. So in the case that GCD(M, n) > 1 then this didn't prove how RSA still works in that situation
The Euler's theorem proof of correctness can be extended to show correctness for such cases, although in a practical system, GCD(M, n) > 1 is almost never the case. So proofs like this are generally considered good enough. But RSA does still work for GCD(M, n) > 1, it just requires a little extra maths to show it.
Best explanation on the internet
Except there are a many gaps and a few flaws. For example, the exponentiation law at 3:20 works for all integer values of A, not just for A
Ultimate
thanks
thank you so so much
Thankyou for this
Thanks :)