I was doing a little research on RSA algorithm and i was watching this video and around minute 5:45, the author has 2 formulas:
$ m^e\mod n = c $
and
$ c^d\mod n = m $
and then he ends up with $\text{ } m^{ed}\mod n = m $
Firstly, i don't get what property was used to pass from this $\text{ } (m^e\mod n)^d \mod n =m\text{ }$ to the formula above.
Secondly, my math may be a bit rusty but shouldn't $\text{ } (m^e\mod n)^d \mod n =m\text{ }$ be true for any positive integer m,e,d,n since i only replaced c in the equation?
Thanks for your help!
Ps: Please keep in mind i am no expert of any kind in math.
First of all, we can "collapse" modulo arithmetic in the following way:
$$ [(a \bmod n) \times b] \bmod n = ab \bmod n $$
If you apply this repeatedly, you can obtain
$$ [(m^e \bmod n)^d] \bmod n = (m^e)^d \bmod n = m^{ed} \bmod n $$
Secondly, the expressions
$$ m^e \bmod n = c $$
and
$$ c^d \bmod n = m $$
are not jointly true for all $m, n, e, d$. Given the right $n, e, d$, it is true for all $m$ such that $0 \leq m < n$—that is to say, one can encrypt any "message" less than the modulus $n$—but it is not the case that any three numbers make up a public key pair. They have to be chosen according to an algorithm that can be found here.
When that is done, one can encrypt any message $m$ by raising it to the $e$th power, and taking the result modulo $n$ to obtain the ciphertext $c$. One can then reverse this transformation by raising $c$ to the $d$th power, and take the result modulo $n$ again to recover the message $m$.