RSA Cryptosystem
The RSA cryptosystem is an asymmetric public-key encryption and digital signature algorithm introduced in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman whose mathematical security relies on the computational hardness of the integer factorization problem and the RSA problem.
RSA Cryptosystem is an asymmetric public-key encryption and digital signature algorithm in computation and algorithms that enables secure data transmission across untrusted communication channels. Formally published in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman at the Massachusetts Institute of Technology (and independently discovered in classified work by British mathematician Clifford Cocks at GCHQ in 1973), the cryptosystem introduced a practical implementation of the public-key paradigm conceived by Whitfield Diffie and Martin Hellman in DiffieโHellman key exchange.
Within computational complexity theory, the security of the RSA cryptosystem rests on the asymmetry between multiplication and prime factorization. While multiplying two large prime numbers requires polynomial time O((log n)2) bit operations using standard multiplication or O(log n log log n) via the Karatsuba or HarveyโHoeven algorithms, recovering those prime factors from their product n remains computationally intractable for classical computers, requiring sub-exponential time under the general number field sieve.
Mathematical Architecture and Key Generation
The algebraic framework of RSA operates in the ring of integers modulo a composite number n, denoted โค/nโค, and its multiplicative group of units (โค/nโค)ร. The key generation protocol proceeds through four foundational arithmetic stages:
- Prime Selection: Two distinct, large prime integers p and q are generated uniformly at random from a uniform distribution of odd integers and certified prime using probabilistic tests such as the MillerโRabin primality test. In modern implementations, p and q are typically chosen to possess equivalent bit lengths, yielding a composite modulus n of 2,048, 3,072, or 4,096 bits.
- Modulus and Totient Computation: The public modulus is computed as n = pq. The order of the multiplicative group of units is given by Euler's totient function:
phi(n) = (p โ 1)(q โ 1)
Alternatively, the Carmichael totient lambda(n) = lcm(p โ 1, q โ 1) can be employed, representing the smallest positive integer such that alambda(n) โก 1 (mod n) for all a coprime to n.
- Public Exponent Selection: An integer e is selected such that 1 < e < phi(n) and gcd(e, phi(n)) = 1. The most prevalent choice in standardized implementations is the fourth Fermat prime, e = 65,537 (216 + 1), which possesses a Hamming weight of two (binary 10000000000000001), enabling modular exponentiation in seventeen multiplications.
- Private Exponent Derivation: Using the extended Euclidean algorithm, the private decryption exponent d is computed as the unique modular multiplicative inverse of e modulo phi(n):
e ยท d โก 1 (mod phi(n))
The public key is the ordered pair (n, e), while the corresponding private key is the tuple (d, p, q, dp, dq, qinv), where dp = d mod (p โ 1), dq = d mod (q โ 1), and qinv = qโ1 mod p are precomputed parameters for optimization via the Chinese Remainder Theorem.
Encryption, Decryption, and Homomorphic Structure
To transmit a secret message m, the sender encodes the plaintext into an integer in the interval 0 โค m < n such that gcd(m, n) = 1. The encryption operation evaluates a single modular exponentiation:
c โก me (mod n)
Upon receiving the ciphertext c, the recipient recovers the original plaintext m by evaluating modular exponentiation with the private exponent d:
m โก cd โก (me)d โก med (mod n)
The mathematical correctness of this inversion follows from Euler's totient theorem. Because ed โก 1 (mod phi(n)), there exists an integer k such that ed = 1 + k ยท phi(n). If gcd(m, n) = 1:
med = m1 + k ยท phi(n) = m ยท (mphi(n))k โก m ยท 1k โก m (mod n)
If gcd(m, n) > 1, the result holds via the Chinese Remainder Theorem modulo p and modulo q separately, because Fermat's Little Theorem guarantees that med โก m (mod p) and med โก m (mod q).
Raw textbook RSA exhibits a multiplicative homomorphic property. Given two plaintexts m1 and m2 with ciphertexts c1 โก m1e (mod n) and c2 โก m2e (mod n):
c1 ยท c2 โก m1e ยท m2e โก (m1 ยท m2)e (mod n)
While foundational in theoretical protocols, unpadded textbook RSA is completely insecure against chosen-ciphertext attacks, malleability manipulations, and small-exponent stereotyping.
Padding Paradigms and Optimal Asymmetric Encryption Padding
To guarantee semantic security (indistinguishability under adaptive chosen-ciphertext attack, IND-CCA2), practical RSA implementations mandate randomized padding before exponentiation:
- PKCS #1 v1.5 Padding: An early standard that prepends a deterministic block, pseudo-random non-zero padding bytes, and a delimiter to the message. In 1998, Daniel Bleichenbacher demonstrated a devastating million-query chosen-ciphertext attack against SSL servers using PKCS #1 v1.5 padding: an attacker submitting modified ciphertexts can determine whether the decrypted plaintext conforms to the padding standard based on server error responses (a padding oracle), reconstructing the complete plaintext.
- Optimal Asymmetric Encryption Padding (OAEP): Formulated by Mihir Bellare and Phillip Rogaway, OAEP employs a two-round asymmetric Feistel network parametrized by two cryptographic hash functions to inject randomness and achieve IND-CCA2 security in the random oracle model. By diffusing the message bits across the entire modulus, OAEP thwarts algebraic structural attacks and padding oracle exploitation.
Algorithmic Optimizations and Side-Channel Vulnerabilities
Evaluating cd mod n directly requires O(log d) multiplications of 2,048-bit integers. High-performance software libraries implement the Chinese Remainder Theorem (CRT) optimization. By splitting the computation into two half-sized moduli p and q:
mp = cdp mod p, and mq = cdq mod q
The final plaintext is recombined as m = mq + q ยท ((mp โ mq) ยท qinv mod p). Because modular multiplication complexity scales quadratically with operand length, evaluating two 1,024-bit exponentiations is approximately four times faster than a single 2,048-bit exponentiation.
However, CRT acceleration exposes the implementation to physical side-channel vulnerabilities. In 1996, Dan Boneh, Richard DeMillo, and Richard Lipton discovered that inducing a computational hardware fault during one of the CRT branch operations (such as mp) causes the calculated result m' to satisfy gcd(m'e โ c, n) = q, instantly factoring the public modulus and leaking the private key. Modern implementations counteract this Bellcore fault attack by verifying that me โก c (mod n) before returning any decrypted output or signature.
Comparison of Asymmetric Public-Key Primitives
| Cryptographic Primitive | Underlying Hard Problem | Typical Key Size (128-bit Security) | Dominant Operation | Primary Practical Advantage |
|---|---|---|---|---|
| RSA Cryptosystem | Integer Factorization / RSA Problem | 3,072 bits | Modular Exponentiation | Fast verification with small e = 65,537 |
| DiffieโHellman | Discrete Logarithm Problem (DLP) | 3,072 bits | Modular Exponentiation | Elegant ephemeral key agreement |
| ECDSA / Ed25519 | Elliptic Curve Discrete Logarithm (ECDLP) | 256 bits | Elliptic Curve Point Multiplication | Ultra-compact keys and signatures |
| ML-KEM (Kyber) | Module Learning With Errors (M-LWE) | 800โ1,568 bytes | Polynomial Ring Arithmetic | Post-quantum lattice resistance |
References
- Rivest, R. L., Shamir, A., & Adleman, L. (1978). A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 21(2), 120-126.
- Bellare, M., & Rogaway, P. (1994). Optimal Asymmetric Encryption โ How to encrypt with RSA. Advances in Cryptology โ EUROCRYPT '94, 92-111.
- Boneh, D. (1999). Twenty years of attacks on the RSA cryptosystem. Notices of the American Mathematical Society, 46(2), 203-213.
- Bleichenbacher, D. (1998). Chosen ciphertext attacks against protocols based on the RSA encryption standard PKCS #1. Advances in Cryptology โ CRYPTO '98, 1-12.