How Does RSA Rely on Prime Factorization Hardness?

The RSA cryptosystem secures digital communications by exploiting the asymmetry between multiplying two large prime numbers and factoring their product back into its original primes. While multiplication is computationally trivial for classical computers, prime factorization remains infeasible for sufficiently large numbers. This one-way mathematical relationship protects the private key even when the public key is openly shared.

The Mathematical Foundation of RSA

RSA key generation begins by selecting two distinct, large prime numbers, \(p\) and \(q\). These primes are multiplied together to form the modulus \(n\):

\[n = p \times q\]

The security of the system depends on keeping \(p\) and \(q\) secret while publishing \(n\) as part of the public key. Next, Euler's totient function \(\phi(n)\) is computed:

\[\phi(n) = (p - 1)(q - 1)\]

A public exponent \(e\) is chosen such that \(1 < e < \phi(n)\) and \(\gcd(e, \phi(n)) = 1\). Finally, the private exponent \(d\) is calculated as the modular multiplicative inverse of \(e\) modulo \(\phi(n)\):

\[d \equiv e^{-1} \pmod{\phi(n)}\]

The public key consists of the pair \((n, e)\), and the private key consists of \((n, d)\).

Why Factoring Protects the Private Key

An attacker who intercepts the public key \((n, e)\) knows both \(n\) and \(e\). To recover the private exponent \(d\), the attacker needs to know \(\phi(n)\). Computing \(\phi(n)\) directly from \(n\) requires knowing the prime factors \(p\) and \(q\), because:

\[\phi(n) = n - (p + q) + 1\]

Without \(p\) and \(q\), there is no known classical algorithm that can efficiently compute \(\phi(n)\) or \(d\) from \((n, e)\) alone. Conversely, if an attacker successfully factors \(n\) into \(p\) and \(q\), they can immediately compute \(\phi(n)\) and use the extended Euclidean algorithm to find \(d\), completely breaking the encryption.

Classical Computational Complexity

In classical computing, multiplying two \(k\)-bit primes takes \(O(k^2)\) operations using standard algorithms, or even faster with advanced multiplication techniques. For a 2048-bit modulus, a modern processor can perform this multiplication in microseconds.

Factoring \(n\), however, is dramatically harder. The fastest known classical algorithm for factoring general integers is the General Number Field Sieve (GNFS), which has sub-exponential time complexity:

\[O\left(\exp\left(\left(\sqrt[3]{\frac{64}{9}} + o(1)\right) (\ln n)^{1/3} (\ln \ln n)^{2/3}\right)\right)\]

Because the runtime grows super-polynomially with the bit length of \(n\), doubling the key size increases the difficulty of factoring by many orders of magnitude. For a 2048-bit or 4096-bit RSA key, factoring \(n\) with classical hardware would take longer than the age of the universe.

Encryption and Decryption Without Factoring

To encrypt a message \(m\) (represented as an integer where \(0 \le m < n\)), the sender computes the ciphertext \(c\) using the public key:

\[c \equiv m^e \pmod{n}\]

To decrypt \(c\), the recipient uses the private key:

\[m \equiv c^d \pmod{n}\]

Modular exponentiation can be performed efficiently in polynomial time using exponentiation by squaring. Thus, legitimate users can encrypt and decrypt messages quickly, while an eavesdropper attempting to invert the encryption without \(d\) faces a problem believed to be computationally equivalent to factoring \(n\).