RSA encryption and decryption is built upon Fermat's theoremEuler's theorem which says: that $a^{\phi(n)} = 1 \mod(n)$$a^{\phi(n)} \equiv 1 \pmod n$, and since $p$ and $q$ are primes:, $\phi(p*q) = (p-1)*(q-1)$$\phi(pq) = (p-1)(q-1)$.
If we have message $M$ and, modulus $n$, private keyexponent $d$ and public pairexponent $e$…, RSA encryption works like this:
Encryption: $C = M^e (\mod n)$
Decryption: $C^d \mod(n)$ which most be the same as $M$
- Encryption: $C = (M^e \bmod n)$
- Decryption: $M' = (C^d \bmod n)$, which must be the same as $M$ for the decryption to be correct.
Now, combining the above, we get $C^d = (M^e)^d = M^{(ed)} \mod(n)$.$$M' \equiv C^d \equiv (M^e)^d = M^{ed} \pmod n.$$ Since $ed = 1 \mod \phi(n)$$ed \equiv 1 \mod{\phi(n)}$, we may write $K*\phi(n) = ed - 1$$k\cdot\phi(n) = ed - 1$ for some integer $k$ which renders itand rearrange this to $ed = k*\phi(n) + 1$$ed = k\cdot\phi(n) + 1$.
NowTherefore $M^{(ed)} = M^{(\phi(n) + 1 )} = M*M^{(phi(n))} \mod(n)$,$$M' \equiv M^{ed} = M^{k\phi(n) + 1} = M \cdot M^{k\phi(n)} \pmod n,$$ and since $M^{(\phi(n))} = 1 \mod(n)$$$M^{k\phi(n)} = (M^{\phi(n)})^k \equiv 1^k = 1 \pmod n,$$ the decryption result becomes $M$$M' \equiv M \cdot M^{k\phi(n)} \equiv M \cdot 1 = M \pmod n$ equals the original message again.
So, withoutAll this depends crucially on the fact that $ed=1 \mod(\phi(n))$$ed=1 \mod{\phi(n)}$, so without it, we wontwon't get $M$ back when we decrypt.
