RSA, in depth: key generation with lambda(n), a correct proof, OAEP and PSS, real attacks, key sizes and the post-quantum deadline

The trapdoor idea

A public-key system needs a function that anyone can compute but only the key holder can invert. RSA uses exponentiation modulo a composite n = p*q. Raising to the power e is easy for anyone who knows n and e. Undoing it requires a matching exponent d, and computing d from e is easy if you know p and q and, as far as anyone knows, hard otherwise. Recovering d is provably as hard as factoring n. Inverting the function for a single ciphertext without d is called the RSA problem; it is not known to be equivalent to factoring, but no faster general method is known. The best classical factoring algorithm, the general number field sieve, is sub-exponential, which is why RSA keys are thousands of bits long.

Key generation, step by step

FIPS 186-5 and PKCS #1 describe key generation. In outline:

1. Choose the public exponent e. Almost everyone uses 65537 = 2^16 + 1: it is prime, and its two set bits make the public operation cost 17 modular multiplications. FIPS requires an odd e with 2^16 < e < 2^256, which rules out e = 3.
2. Generate random primes p and q of half the modulus length each, from a properly seeded cryptographic generator, testing candidates with Miller-Rabin and rejecting any where gcd(e, p-1) != 1. FIPS also requires |p - q| to be large, so that n cannot be factored by searching near its square root.
3. Compute n = p*q and lambda(n) = lcm(p-1, q-1), the Carmichael function. Many textbooks use Euler's phi(n) = (p-1)(q-1) instead; both give working keys, and lambda gives the smallest valid d.
4. Compute d = e^-1 mod lambda(n) with the extended Euclidean algorithm. FIPS requires d > 2^(nlen/2), which guards against small-d attacks.
5. Precompute the CRT values dP = d mod (p-1), dQ = d mod (q-1) and qInv = q^-1 mod p. The public key is (n, e); everything else is private.

import math, secrets

def is_probable_prime(n, rounds=40):
    if n < 4:
        return n in (2, 3)
    small = (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37)
    if any(n % s == 0 for s in small):
        return n in small
    d, r = n - 1, 0
    while d % 2 == 0:
        d //= 2; r += 1
    for _ in range(rounds):
        x = pow(secrets.randbelow(n - 3) + 2, d, n)
        if x in (1, n - 1):
            continue
        for _ in range(r - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False
    return True

def gen_prime(bits, e):
    while True:
        c = secrets.randbits(bits) | (0b11 << (bits - 2)) | 1   # top two bits set, odd
        if math.gcd(e, c - 1) == 1 and is_probable_prime(c):
            return c

def keygen(bits=2048, e=65537):         # teaching code: use a vetted library in production
    while True:
        p, q = gen_prime(bits // 2, e), gen_prime(bits // 2, e)
        if abs(p - q) < 2 ** (bits // 2 - 100):
            continue
        lam = math.lcm(p - 1, q - 1)
        d = pow(e, -1, lam)
        if d > 2 ** (bits // 2):
            return (p * q, e), (p, q, d, d % (p - 1), d % (q - 1), pow(q, -1, p))

Setting the top two bits of each prime guarantees that n has exactly the requested length. Real keys should come from a vetted library, an HSM or a cloud KMS, where the entropy source and side-channel behaviour have been reviewed.

Why decryption works

Encryption is c = m^e mod n and decryption is m = c^d mod n. We need m^(ed) = m mod n for every m in [0, n). The common proof writes ed = 1 + k*phi(n) and applies Euler's theorem, but Euler's theorem needs gcd(m, n) = 1, so it skips messages that share a factor with n. The full proof works one prime at a time.

Because ed = 1 mod lambda(n) and p-1 divides lambda(n), we can write ed = 1 + j(p-1). If p does not divide m, Fermat's little theorem gives m^(p-1) = 1 mod p, so m^(ed) = m * (m^(p-1))^j = m mod p. If p divides m, both sides are 0 mod p. Either way m^(ed) = m mod p. The same argument gives the result mod q, and since p and q are distinct primes, the Chinese remainder theorem gives m^(ed) = m mod n. The same proof explains why the CRT shortcut is valid: the private operation can be done mod p and mod q separately and recombined.

Worked example with small primes

Take p = 61 and q = 53. Then n = 3233, phi(n) = 3120 and lambda(n) = lcm(60, 52) = 780. Choose e = 17 (fine for a toy). Extended Euclid on 780 and 17: 780 = 45*17 + 15, 17 = 1*15 + 2, 15 = 7*2 + 1. Back-substituting gives 1 = 8*780 - 367*17, so d = -367 mod 780 = 413. Check: 17*413 = 7021 = 9*780 + 1. The textbook value from phi would be d = 2753, and indeed 2753 mod 780 = 413: both work, lambda just gives the smaller one.

n, e, d = 3233, 17, 413
m = 65
c = pow(m, e, n)          # 2790
assert pow(c, d, n) == m  # decrypts back to 65

s = pow(m, d, n)          # textbook signature of 65: 588
assert pow(s, e, n) == m  # anyone with (n, e) can verify

Signing swaps the roles: raise to d to sign and to e to verify. Real systems never sign or encrypt m directly, for the reasons below.

Why textbook RSA is broken

• Deterministic. The same message always gives the same ciphertext, so an attacker can encrypt guesses ("yes", "no", a salary figure) with the public key and compare.
• Malleable. (m1^e)(m2^e) = (m1*m2)^e mod n. Given c, an attacker can submit c * s^e to a decryption service and divide the result by s to recover m. Unpadded signatures can be forged the same way by multiplying two signed values.
• Small messages with small e. With e = 3 and m^3 < n, there is no modular reduction, and an integer cube root recovers m. If the same m is sent to three recipients with e = 3, the CRT recovers m^3 over the integers (Hastad's broadcast attack).
• Common modulus. Two users sharing n with different e can each derive the other's private key, and one message encrypted to both leaks without any key.

OAEP and hybrid encryption

Optimal Asymmetric Encryption Padding (OAEP) fixes the encryption problems by randomizing and structuring the message before exponentiation. A fresh random seed masks the data block through MGF1, a hash-based mask generator, and the masked data block in turn masks the seed. Decryption reverses the masks and checks the label hash and the 0x01 separator; any mismatch is a single generic error.

The capacity is k - 2*hLen - 2 bytes, so a 2048-bit key (256 bytes) with SHA-256 can carry at most 190 bytes. That is why RSA encryption is used only to wrap a random symmetric key, and the data itself is encrypted with AES-GCM or ChaCha20-Poly1305. The older PKCS #1 v1.5 encryption padding is the source of Bleichenbacher's 1998 attack: a server that reveals, through an error message or timing, whether a ciphertext decrypted to correctly formatted padding acts as an oracle, and about a million queries can decrypt a ciphertext. The attack returned in 2017 as ROBOT against TLS servers. TLS 1.3 removed RSA key transport entirely; its handshake signatures with RSA must use PSS.

from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.primitives.asymmetric import rsa, padding

key = rsa.generate_private_key(public_exponent=65537, key_size=3072)
pub = key.public_key()

oaep = padding.OAEP(mgf=padding.MGF1(algorithm=hashes.SHA256()),
                    algorithm=hashes.SHA256(), label=None)
wrapped = pub.encrypt(b"32-byte AES key goes here.......", oaep)
assert key.decrypt(wrapped, oaep).startswith(b"32-byte")

pss = padding.PSS(mgf=padding.MGF1(hashes.SHA256()), salt_length=padding.PSS.MAX_LENGTH)
sig = key.sign(b"release-1.4.2.tar.gz digest", pss, hashes.SHA256())
pub.verify(sig, b"release-1.4.2.tar.gz digest", pss, hashes.SHA256())  # raises InvalidSignature on failure

Signatures: PSS and strict verification

Signatures always hash first and pad the hash. PSS (Probabilistic Signature Scheme) adds a random salt and has a security proof tied to the RSA problem; it is the recommended choice for new designs. PKCS #1 v1.5 signatures are deterministic and remain widely deployed in certificates and are not known to be broken, but their verifiers must parse strictly. In 2006 Bleichenbacher showed that verifiers which did not check that the hash filled the rest of the block could be fooled with forged signatures when e = 3; variants recurred in libraries for years afterwards. The defence is to re-encode the expected block and compare it byte for byte, never to parse the decrypted block loosely. Use separate keys for signing and encryption, since a decryption oracle is also a signing oracle for the same key.

Attacks that broke real systems

Factoring a well-generated 2048-bit modulus is out of reach of classical computers. The breaks that matter in practice attack how keys are made and used:

The CRT fault attack is short enough to demonstrate. If the half computed mod q is corrupted but the half mod p is correct, then the faulty s still satisfies s^e = m mod p, so gcd(s^e - m, n) = p, and one bad signature factors the key:

import math
p, q, e, d = 61, 53, 17, 413
n, m = p * q, 65
sp = pow(m, d % (p - 1), p)
sq = (pow(m, d % (q - 1), q) + 1) % q          # simulated fault in the q half
h = (pow(q, -1, p) * (sp - sq)) % p
s_bad = sq + q * h                             # Garner recombination
assert math.gcd(pow(s_bad, e, n) - m, n) == p  # factor recovered from one faulty signature

Key sizes and the quantum deadline

NIST SP 800-57 maps RSA modulus sizes to symmetric-equivalent strength: 2048 bits is about 112 bits of security, 3072 about 128, 7680 about 192 and 15360 about 256. Cost grows roughly with the cube of the modulus size for private operations, so doubling the key makes signing several times slower; measure your own hardware with openssl speed rsa2048 rsa3072 rather than trusting published figures.

The longer-term limit is quantum. Shor's algorithm would factor RSA moduli in polynomial time on a large fault-tolerant quantum computer, which does not exist today. NIST's draft IR 8547, published in November 2024 and still a draft at the time of writing, proposes deprecating 112-bit-strength RSA after 2030 and disallowing RSA, along with elliptic-curve schemes, after 2035. The replacements are ML-KEM (FIPS 203) for key establishment and ML-DSA (FIPS 204) for signatures. Encryption is the urgent case, because recorded ciphertext can be decrypted later; signatures only need to be replaced before a capable machine exists, but long-lived roots of trust and firmware keys take years to rotate.

Operational guidance

• Generate and hold private keys in an HSM or cloud KMS; never in source control or container images.
• Use 3072-bit keys for anything that must stay secure past 2030, and keep an inventory of every RSA key with its owner, size and purpose.
• Use OAEP with SHA-256 for encryption, PSS for new signatures, and strict re-encode-and-compare verification.
• Verify CRT signatures before release and keep blinding enabled; mature libraries do both by default.
• Never roll your own padding or parsing.

What to do next

• Run the toy example and the fault demonstration above, then change the fault to the p half and confirm gcd returns q.
• Grep your codebase for unpadded RSA, PKCS #1 v1.5 encryption and NoPadding modes, and replace them with OAEP or a KEM.
• List every RSA key you operate, with size, purpose and rotation date; flag 2048-bit keys that outlive 2030.
• Check that each service uses separate keys for signing and encryption.
• Prototype a hybrid ML-KEM key exchange in a non-critical service to learn the size and latency cost.
• Read modular exponentiation for the constant-time implementation details and number theory algorithms for the supporting maths.