โ† Wiki Index / Computation & Algorithms / RSA Cryptosystem
๐Ÿ’ป Computation & Algorithms

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:

  1. 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.
  2. 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.

  1. 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.
  2. 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 PrimitiveUnderlying Hard ProblemTypical Key Size (128-bit Security)Dominant OperationPrimary Practical Advantage
RSA CryptosystemInteger Factorization / RSA Problem3,072 bitsModular ExponentiationFast verification with small e = 65,537
Diffieโ€“HellmanDiscrete Logarithm Problem (DLP)3,072 bitsModular ExponentiationElegant ephemeral key agreement
ECDSA / Ed25519Elliptic Curve Discrete Logarithm (ECDLP)256 bitsElliptic Curve Point MultiplicationUltra-compact keys and signatures
ML-KEM (Kyber)Module Learning With Errors (M-LWE)800โ€“1,568 bytesPolynomial Ring ArithmeticPost-quantum lattice resistance

References

  1. 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.
  2. Bellare, M., & Rogaway, P. (1994). Optimal Asymmetric Encryption โ€” How to encrypt with RSA. Advances in Cryptology โ€” EUROCRYPT '94, 92-111.
  3. Boneh, D. (1999). Twenty years of attacks on the RSA cryptosystem. Notices of the American Mathematical Society, 46(2), 203-213.
  4. Bleichenbacher, D. (1998). Chosen ciphertext attacks against protocols based on the RSA encryption standard PKCS #1. Advances in Cryptology โ€” CRYPTO '98, 1-12.
๐Ÿงฌ Support Open Science
Explore interactive science games on LowKey Games or browse scientific apparel & accessories in the CRV Science Shop.
๐Ÿ’ก Spot an inaccuracy or have primary literature to expand this article?
Submit a citation or revision note using your shared CRV Science / LowKey Games profile ID.
Suggest Revision