A topic in the Open Knowledge Graph — a free, open map of 15,290 topics and the order to learn them in.
RSA is a public-key cryptosystem whose security rests on the difficulty of factoring large integers. The public key (n, e) consists of a product n = pq of two large primes and an encryption exponent e. The private key d satisfies ed ≡ 1 (mod phi(n)). Encryption computes c = me mod n; decryption computes m = cd mod n. Correctness follows from Euler's theorem. The trapdoor is factorization: computing d from (n, e) is easy if p and q are known but believed hard otherwise. RSA is used for key exchange and digital signatures, though direct RSA encryption requires padding schemes (OAEP) to be secure against chosen-ciphertext attacks.
RSA, introduced by Rivest, Shamir, and Adleman in 1977, was the first practical public-key cryptosystem and remains widely deployed. Its core idea is a trapdoor permutation: a function that is easy to compute but hard to invert without a secret trapdoor. Key generation picks two large primes p and q, computes n = pq and phi(n) = (p-1)(q-1), chooses a public exponent e (commonly 65537) coprime to phi(n), and computes the private exponent d = e-1 mod phi(n). The public key is (n, e); the private key is d. Anyone can encrypt by computing c = me mod n, but only the holder of d can decrypt: m = cd mod n. Correctness follows from Euler's theorem: since ed ≡ 1 mod phi(n), we have med = m1 + k*phi(n) = m * (mphi(n))k ≡ m mod n.
The security assumption is that factoring n is computationally hard when p and q are large random primes (each at least 1024 bits, giving a 2048-bit modulus). If an attacker could factor n, they could compute phi(n) and derive d directly. The best known classical factoring algorithm, the General Number Field Sieve, runs in sub-exponential time — faster than trying all possible factors but dramatically slower than polynomial. For 2048-bit moduli, GNFS is estimated to require roughly 2112 operations, well beyond current capabilities. However, Shor's quantum algorithm factors in polynomial time, which is why RSA is considered vulnerable to future quantum computers and why post-quantum alternatives are being standardized.
A critical practical point is that textbook RSA is insecure. Encrypting as c = me mod n is deterministic (same message always gives same ciphertext), which violates semantic security. It is also multiplicatively homomorphic: E(m1) * E(m2) = E(m1 * m2) mod n, enabling algebraic attacks. Real RSA encryption uses OAEP (Optimal Asymmetric Encryption Padding), which adds randomness and structure to the message before exponentiation, achieving provable CCA-security under the RSA assumption. Similarly, RSA signatures require hashing the message first (and adding randomized padding via PSS) to prevent forgery through multiplicative manipulation.
In practice, RSA is rarely used to encrypt bulk data directly because modular exponentiation is orders of magnitude slower than AES. Instead, RSA typically encrypts a random session key (a few hundred bits), and the session key is used with a fast symmetric cipher for the actual data. This hybrid approach — asymmetric cryptography for key exchange, symmetric cryptography for data — combines the convenience of public keys with the speed of symmetric encryption. RSA also serves as the basis for digital signature schemes, where the signer applies the private key to a hash of the message and any verifier can check using the public key.