How Does RSA Public-Key Cryptography Work? (Modular Arithmetic, Euler’s Totient & Prime Factorization)

The Key Distribution Problem and the Asymmetric Revolution

For thousands of years, cryptography relied entirely on symmetric key ciphers (such as the Caesar cipher, Vigenère cipher, and Enigma machine), where both the sender and receiver had to share the identical secret key $k$ before encrypting and decrypting messages [1,2]. Symmetric encryption suffered from a fatal logistical bottleneck: how could two parties who had never met securely establish a shared secret key across an insecure public channel without an eavesdropper intercepting it? [1,2]

In 1976, Whitfield Diffie and Martin Hellman published "New Directions in Cryptography", proposing the theoretical concept of Public-Key Cryptography based on trapdoor one-way functions—mathematical operations that are easy to compute in the forward direction but computationally intractable to reverse without a secret mathematical "trapdoor" [1,3].

In 1977 at MIT, Ron Rivest, Adi Shamir, and Leonard Adleman implemented the first practical trapdoor cryptosystem: the RSA algorithm [1,4].

"Public-key cryptography solved the ancient key-exchange problem: anyone can lock a padlock with a public key, but only the holder of the private key can open it."

Number Theoretic Foundations: Primes and Euler’s Totient

The security of RSA rests on modular arithmetic and the asymmetry between multiplication and prime factorization [1,4,5]:

1. Prime Selection: Choose two distinct, randomly generated large prime numbers $p$ and $q$ (in modern RSA-2048, each prime is 1,024 bits long).

2. Modulus Calculation: Compute the RSA modulus $n = p \cdot q$. The bit-length of $n$ determines the key strength [1,4].

3. Euler’s Totient Function $\phi(n)$: Compute the number of positive integers less than $n$ that are coprime to $n$. Because $p$ and $q$ are prime, Euler's totient simplifies to [1,4,5]:

$$\phi(n) = (p - 1)(q - 1)$$

4. Public Exponent $e$: Select an integer $e$ such that $1 < e < \phi(n)$ and $\gcd(e, \phi(n)) = 1$. The standard industry standard choice is the Fermat prime $e = 65537 = 2^{16} + 1$, chosen for rapid modular exponentiation with few set bits [1,4].

5. Private Exponent $d$: Calculate the modular multiplicative inverse of $e$ modulo $\phi(n)$ using the Extended Euclidean Algorithm [1,4,5]:

$$d \cdot e \equiv 1 \pmod{\phi(n)} \quad \implies \quad d \equiv e^{-1} \pmod{\phi(n)}$$

The Public Key is the pair $(e, n)$, while the Private Key is $d$ (with $p, q,$ and $\phi(n)$ kept secret or securely destroyed) [1,4].

Encryption, Decryption, and Euler’s Theorem Proof

To encrypt a plaintext message $m$ (represented as an integer $0 \le m < n$), the sender computes the ciphertext $c$ using the recipient's public key $(e, n)$ via modular exponentiation [1,4]:

$$c = m^e \bmod n$$

To decrypt the ciphertext $c$, the recipient uses their secret private exponent $d$ [1,4]:

$$m = c^d \bmod n$$

The mathematical proof that decryption recovers the exact original plaintext relies on Euler’s Theorem (which states that if $\gcd(m, n) = 1$, then $m^{\phi(n)} \equiv 1 \pmod n$) [1,4,5]:

$$c^d \equiv (m^e)^d \equiv m^{ed} \pmod n$$

Because $ed \equiv 1 \pmod{\phi(n)}$, there exists an integer $k$ such that $ed = 1 + k\phi(n)$. Substituting this gives [1,4,5]:

$$m^{ed} = m^{1 + k\phi(n)} = m \cdot \left(m^{\phi(n)}\right)^k \equiv m \cdot (1)^k \equiv m \pmod n$$

"Decryption works because Euler’s Theorem guarantees that raising ciphertext to the private power d cancels out the public exponent e modulo n."

Security Hardness, Padding Schemes, and Quantum Threats

An attacker possessing the public key $(e, n)$ cannot compute the private key $d$ without knowing $\phi(n) = (p-1)(q-1)$, which strictly requires factoring $n$ into its constituent primes $p$ and $q$ [1,4,6]. The fastest known classical algorithm for integer factorization, the General Number Field Sieve (GNFS), operates in sub-exponential time $\mathcal{O}\left(\exp\left(\sqrt[3]{(64/9) b (\log b)^2}\right)\right)$ where $b = \log_2 n$, making factoring 2048-bit keys impossible on classical computers for millions of years [1,6].

In practice, textbook RSA is vulnerable to mathematical attacks (such as Coppersmith's small root attacks and Wiener's small private exponent attacks). Real-world implementations mandate randomized padding schemes like Optimal Asymmetric Encryption Padding (OAEP) to achieve semantic security against chosen-ciphertext attacks [1,4,6].

Looking ahead, Peter Shor proved in 1994 that a fault-tolerant quantum computer running Shor's Algorithm can factor integers in polynomial time $\mathcal{O}((\log n)^3)$, prompting the global cryptographic migration toward NIST-standardized lattice-based Post-Quantum Cryptography (PQC, such as ML-KEM / Crystals-Kyber) [1,7].