RSA & Modular Arithmetic theory

Symmetric cryptography uses the exact same secret key for both encryption and decryption (e.g. AES). In an open network with N participants, pairwise communication requires sharing and storing N(N-1)/2 keys, creating a massive key distribution bottleneck. Asymmetric cryptography (Diffie-Hellman, RSA) uses a mathematically linked key pair: a public key (openly distributed) for encryption and a private key (kept secret) for decryption. Anyone can encrypt a message using the recipient's public key, but only the recipient holding the corresponding private key can decrypt it, solving the key distribution problem completely.

RSA chooses two large primes p and q, computing modulus n = pq and Euler's totient φ(n) = (p-1)(q-1). A public exponent e is chosen coprime to φ(n), and the private exponent d is computed as the modular inverse: ed ≡ 1 (mod φ(n)). Encryption evaluates C = M^e mod n; decryption evaluates M' = C^d mod n. According to Euler's Totient Theorem, if gcd(M, n) = 1, then M^φ(n) ≡ 1 (mod n). Because ed = k·φ(n) + 1, we have C^d ≡ (M^e)^d = M^(k·φ(n)+1) = (M^φ(n))^k · M ≡ (1)^k · M ≡ M (mod n), guaranteeing flawless mathematical decryption.

The condition ed ≡ 1 (mod φ(n)) can be rewritten as the linear Diophantine equation e·d + φ(n)·y = gcd(e, φ(n)) = 1. The Extended Euclidean Algorithm evaluates the sequence of quotients and remainders from the standard Euclidean algorithm backwards to determine the integer Bézout coefficients x and y satisfying a·x + b·y = gcd(a, b). For inputs e and φ(n), the resulting coefficient x represents the exact modular multiplicative inverse d = e^(-1) mod φ(n), computed in strictly logarithmic O(log(min(e, φ(n)))) operations.

Evaluating a^b mod n naively by multiplying a by itself b times requires b multiplications. For a 2048-bit exponent b, b ≈ 10^616, which would take billions of years. The Square-and-Multiply algorithm scans the binary bits of b from left to right. At each bit position, it squares the current accumulator (acc = acc² mod n); if the bit is 1, it additionally multiplies by the base (acc = acc·a mod n). For a B-bit exponent, this evaluates exactly B squarings and an average of B/2 multiplications (assuming 50% ones in the binary key), completing in strictly M(B) = 1.5 B modular operations (a few thousand operations for a 2048-bit key, executing in milliseconds).

The Miller-Rabin test is a randomized polynomial-time algorithm based on Fermat's Little Theorem and the property that 1 has only two square roots modulo a prime: 1 and -1. For odd candidate n, it factors n-1 = 2^s · d. For a random witness base a, it evaluates x = a^d mod n. If x = 1 or x = n-1, n passes. Otherwise, it squares x repeatedly up to s-1 times: if x becomes n-1, it passes; if the loop terminates without seeing n-1, n is proven composite. If n is composite, at least 75% of all bases are witnesses. By running k = 40 independent rounds with random bases, the probability of falsely accepting a composite as prime is bounded by (1/4)^40 = 2^(-80) < 10^(-24).

The security of RSA relies on the computational difficulty of factoring the composite modulus n into primes p and q. The fastest known classical factoring algorithm is the General Number Field Sieve (GNFS), which runs in sub-exponential time L_n[1/3, c] = exp((c + o(1)) (ln n)^(1/3) (ln ln n)^(2/3)). While 512-bit RSA was factored in 1999 and 768-bit in 2009, 2048-bit RSA has a modulus with 617 decimal digits. Factoring a 2048-bit modulus using GNFS would require an estimated 10^9 to 10^11 core-years of continuous computing, far exceeding global computational capabilities.

In 1994, Peter Shor demonstrated that a sufficiently large fault-tolerant quantum computer can factor composite integers in polynomial time O((log n)³). Shor's algorithm reduces factoring to finding the period r of the modular exponential function f(x) = a^x mod n, which can be computed in polynomial time using the Quantum Fourier Transform (QFT). Once the period r is found, gcd(a^(r/2) ± 1, n) yields the non-trivial prime factors of n with high probability. A quantum computer with approximately 4,000 logical qubits could break 2048-bit RSA in hours, driving the transition to post-quantum cryptography (PQC).