RSA Encryption-Decryption Identity Proof via Euler's Theorem

Lightly amended from https://chatgpt.com/share/68724162-ffd8-800d-99dc-893959fbb945

Step-by-step derivation of the RSA property from Euler’s Theorem, assuming:

• $n=pq$, where $p,q$ are distinct primes
• $\varphi (n)=(p-1)(q-1)$
• $e\cdot d\equiv 1(\mathrm{mod}\varphi (n))\Rightarrow ed=1+k\varphi (n)ed=1+k\varphi (n)$ for some integer $k$
• $\gcd (m,n)=1$ (i.e. $m$ is invertible mod $n$)

We aim to prove:

$m^{ed}\equiv m(\mathrm{mod}n)$

---

🔶 Step 1: Euler’s Theorem

For any integer aa such that gcd⁡(a,n)=1\gcd(a, n) = 1,

$a^{\varphi (n)}\equiv 1(\mathrm{mod}n)$

---

🔶 Step 2: Use the key equation ed=1+kϕ(n)ed = 1 + k\phi(n)

Suppose $ed=1+k\varphi (n)ed=1+k\varphi (n)$ Then:

$m^{ed}=m^{1+k\varphi (n)}=m\cdot (m^{\varphi (n)}{)}^k$

---

🔶 Step 3: Apply Euler’s Theorem to mϕ(n)m^{\phi(n)}

Since gcd⁡(m,n)=1\gcd(m, n) = 1, Euler’s theorem applies:

$m^{\varphi (n)}\equiv 1(\mathrm{mod}n)\Rightarrow (m^{\varphi (n)}{)}^k\equiv 1^k=1(\mathrm{mod}n)$

---

🔶 Step 4: Plug back in

Now we substitute:

$m^{ed}=m\cdot (m^{\varphi (n)}{)}^k\equiv m\cdot 1=m(\mathrm{mod}n)$

✅ Therefore:

$\boxed{m^{ed}\equiv m(\mathrm{mod}n)}$

This proves the RSA encryption/decryption identity, assuming $\gcd (m,n)=1$, and that $e\cdot d\equiv 1(\mathrm{mod}\varphi (n))$.

---

🔍 Notes:

1. Why does $\gcd (m,n)=1$ matter?
   1. Because Euler’s Theorem only holds when the base is invertible mod nn.
2. What if mm is not coprime to nn?
   1. Technically, the identity can fail (e.g., if $m\equiv 0\mathrm{mod}p$). For practical deployment of RSA, padding schemes ensure this doesn’t happen.
   2. this is fixed via PKCS standards like PKCS 11 - Wikipedia!
3. Alternative view via CRT (Chinese Remainder Theorem):
   1. You can also prove this result by reducing mod p and mod q separately and applying Fermat’s Little Theorem.