RSA algorithm

RSA (named for Ron Rivest, Adi Shamir, and Leonard Adleman) is a public-key cryptosystem whose security rests on the presumed computational difficulty of factoring the product of two large prime numbers. First published in 1977, it was the first practicable asymmetric encryption scheme and remains, nearly five decades later, the most widely deployed public-key algorithm on Earth. Its mathematics are elementary — modular exponentiation and a theorem from eighteenth-century number theory — yet the gap between understanding the algorithm and breaking it has proven to be one of the most durable boundaries in all of computer science.

The Mechanism

RSA operates in three phases: key generation, encryption, and decryption. The key generation step selects two large distinct primes p and q, computes their product n = pq (the modulus), and selects a public exponent e (typically 65537) such that encryption and decryption are mutual inverses modulo φ(n) = (p−1)(q−1). The public key is the pair (n, e); the private key is the pair (n, d), where d is the multiplicative inverse of e modulo φ(n).

Encryption of a message m computes c = m^e mod n. Decryption recovers m = c^d mod n. The correctness of this procedure follows from Euler's theorem in modular arithmetic: for any integer m coprime to n, m^φ(n) ≡ 1 (mod n). The choice of d guarantees that ed ≡ 1 (mod φ(n)), so c^d = m^ed ≡ m (mod n).

The elegance is that encryption uses only the public key — anyone can encrypt — while decryption requires knowledge of φ(n), which in turn requires knowing p and q. An adversary who sees only n and e faces the integer factorization problem: recover p and q from n. For sufficiently large n (currently 2048 bits or more), no classical algorithm is known that solves this in time practical for any foreseeable computer.

Computational Hardness and the Factoring Assumption

RSA is not unconditionally secure. Its security is a computational hardness assumption: the conjecture that factoring large semiprimes is infeasible for classical computers. This conjecture is unproved. It is possible — though considered extraordinarily unlikely — that a polynomial-time factoring algorithm exists and has simply not been discovered. The history of number theory is littered with hardness assumptions that collapsed: the Sieve of Eratosthenes once seemed exhaustive, and Fermat's Last Theorem stood unproved for 358 years.

The best known classical factoring algorithms — the General Number Field Sieve (GNFS) and its variants — run in sub-exponential time, approximately exp((64/9)^(1/3) * (ln n)^(1/3) * (ln ln n)^(2/3)). This is slow enough that doubling the key size increases the attack cost by many orders of magnitude, making RSA scalable in a way that symmetric ciphers are not. But the hardness is not exponential. It is sub-exponential, and that gap — between exponentially