RSA Encryption Theory, Key Generation, Encryption, and Decryption in Python (pow, math.gcd, extended Euclidean, Miller-Rabin)

What is RSA Encryption?

RSA is a public-key cryptosystem published in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman. In a public-key cryptosystem, the key used for encryption (public key) differs from the key used for decryption (private key), and security is maintained even when the public key is widely distributed.

The security of RSA is based on the fact that factoring large composite numbers is computationally intractable. It remains widely used today for key exchange, digital signatures, and other applications.

Mathematical Foundations

To understand RSA, several mathematical concepts need to be established.

Integer Factorization Problem

Multiplying two large primes \(p\) and \(q\) to compute \(N = p \times q\) is straightforward. However, recovering the original \(p\) and \(q\) from a given \(N\) (integer factorization) is extremely difficult with current computers when \(N\) is sufficiently large. This asymmetry in computational complexity forms the basis of RSA’s security.

Euler’s Totient Function

Euler’s totient function \(\varphi(N)\) represents the count of integers from \(1\) to \(N\) that are coprime to \(N\) . When \(N = p \times q\) (where \(p\) and \(q\) are distinct primes), the following holds:

Euler’s Theorem

When \(\gcd(a, N) = 1\) (i.e., \(a\) and \(N\) are coprime), the following holds:

This theorem is the core foundation for proving the correctness of RSA.

Modular Inverse

When integers \(e\) and \(\varphi(N)\) are coprime, there exists a unique integer \(d\) satisfying:

This \(d\) is called the modular inverse of \(e\) modulo \(\varphi(N)\) , written as \(d \equiv e^{-1} \pmod{\varphi(N)}\) . It can be efficiently computed using the extended Euclidean algorithm.

RSA Algorithm

Key Generation

1. Randomly select two large primes \(p\) and \(q\)
2. Compute \(N = p \times q\)
3. Compute \(\varphi(N) = (p - 1)(q - 1)\)
4. Choose an integer \(e\) such that \(1 < e < \varphi(N)\) and \(\gcd(e, \varphi(N)) = 1\) (commonly \(e = 65537\) )
5. Compute \(d = e^{-1} \bmod \varphi(N)\) using the extended Euclidean algorithm
6. Public key: \((N, e)\) , Private key: \((N, d)\)

Encryption

Represent the plaintext as an integer \(m\) (\(0 \le m < N\) ) and encrypt using the public key \((N, e)\) :

Decryption

Decrypt the ciphertext \(c\) using the private key \((N, d)\) :

Proof of Correctness

We show that decryption correctly recovers the original plaintext. Consider the case where \(\gcd(m, N) = 1\) .

From \(e \cdot d \equiv 1 \pmod{\varphi(N)}\) , there exists an integer \(k\) such that \(e \cdot d = 1 + k \cdot \varphi(N)\) .

By Euler’s theorem (equation \(\text{(2)}\) ), \(m^{\varphi(N)} \equiv 1 \pmod{N}\) , therefore:

This proves that decryption correctly recovers the original message.

Python Implementation

[WARNING] The following program is an educational implementation to understand the principles of RSA encryption. Do NOT use it for actual cryptographic communications.

import random
import math


def is_prime_miller_rabin(n, k=20):
    """Miller-Rabin primality test"""
    if n < 2:
        return False
    if n == 2 or n == 3:
        return True
    if n % 2 == 0:
        return False
    # Decompose n-1 as 2^r * d
    r, d = 0, n - 1
    while d % 2 == 0:
        r += 1
        d //= 2
    for _ in range(k):
        a = random.randrange(2, n - 1)
        x = pow(a, d, n)
        if x == 1 or x == n - 1:
            continue
        for _ in range(r - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False
    return True


def generate_prime(bits):
    """Generate a random prime of specified bit length"""
    while True:
        # Set MSB and LSB to 1 to ensure odd number of correct bit length
        p = random.getrandbits(bits) | (1 << (bits - 1)) | 1
        if is_prime_miller_rabin(p):
            return p


def extended_gcd(a, b):
    """Extended Euclidean algorithm: returns gcd, x, y such that ax + by = gcd"""
    if a == 0:
        return b, 0, 1
    gcd, x1, y1 = extended_gcd(b % a, a)
    return gcd, y1 - (b // a) * x1, x1


def mod_inverse(e, phi):
    """Compute modular inverse of e mod phi"""
    gcd, x, _ = extended_gcd(e % phi, phi)
    if gcd != 1:
        raise ValueError("Modular inverse does not exist")
    return x % phi


def generate_keypair(bits=512):
    """Generate RSA key pair"""
    p = generate_prime(bits)
    q = generate_prime(bits)
    n = p * q
    phi = (p - 1) * (q - 1)
    e = 65537
    d = mod_inverse(e, phi)
    return (n, e), (n, d)


def encrypt(message, public_key):
    """Encrypt a message using the public key"""
    n, e = public_key
    return pow(message, e, n)


def decrypt(ciphertext, private_key):
    """Decrypt a ciphertext using the private key"""
    n, d = private_key
    return pow(ciphertext, d, n)

Python’s built-in pow(base, exp, mod) function internally performs fast modular exponentiation equivalent to exponentiation by squaring (binary method) .

Function Explanations

1. is_prime_miller_rabin: Performs probabilistic primality testing using the Miller-Rabin algorithm. With \(k = 20\) rounds, the probability of falsely identifying a composite as prime is below \(4^{-20} \approx 10^{-12}\) .

2. generate_prime: Generates a random bit string of the specified length, sets the most significant and least significant bits to 1 (ensuring an odd number of the correct bit length), and repeats until the number passes the primality test.

3. extended_gcd: A recursive implementation of the extended Euclidean algorithm. Finds \(x\) and \(y\) satisfying \(ax + by = \gcd(a, b)\) . See our Euclidean algorithm article for a full correctness proof of this algorithm and a proof that it constructs Bezout’s identity.

4. mod_inverse: Uses the extended Euclidean algorithm to compute \(d\) satisfying \(e \cdot d \equiv 1 \pmod{\varphi(N)}\) .

5. generate_keypair: Combines the above functions to generate an RSA key pair (public key and private key). \(e = 65537\) (\(2^{16} + 1\) ) is chosen because it has only two bits set in binary, making modular exponentiation faster.

Usage Example

# --- Encrypting and decrypting a number ---
public_key, private_key = generate_keypair(bits=512)

message = 12345
ciphertext = encrypt(message, public_key)
decrypted = decrypt(ciphertext, private_key)
print(f"Original:  {message}")
print(f"Encrypted: {ciphertext}")
print(f"Decrypted: {decrypted}")
assert message == decrypted

# --- Encrypting and decrypting a string ---
text = "Hello RSA"
# Convert string to bytes, then interpret as an integer
m = int.from_bytes(text.encode(), "big")
c = encrypt(m, public_key)
d = decrypt(c, private_key)
# Convert integer back to bytes, then decode to string
result = d.to_bytes((d.bit_length() + 7) // 8, "big").decode()
print(f"Original:  {text}")
print(f"Decrypted: {result}")

Benchmark: Timing vs. Key Length

Using the implementation above, we measured key-generation and decryption (modular exponentiation) time for key lengths from 128 to 1024 bits (mean over multiple trials per length, with Miller-Rabin rounds \(k=20\) ).

import time

for bits in [128, 256, 512, 768, 1024]:
    t0 = time.perf_counter()
    public_key, private_key = generate_keypair(bits=bits)
    keygen_time = time.perf_counter() - t0

    message = 123456789
    t0 = time.perf_counter()
    ciphertext = encrypt(message, public_key)
    enc_time = time.perf_counter() - t0

    t0 = time.perf_counter()
    decrypted = decrypt(ciphertext, private_key)
    dec_time = time.perf_counter() - t0
    assert message == decrypted

    print(f"{bits}bit: keygen={keygen_time*1000:.1f}ms, "
          f"enc={enc_time*1e6:.1f}us, dec={dec_time*1e6:.1f}us")

Key-generation time grows nearly exponentially with key length: going from 128 to 1024 bits (8x the length) increases key-generation time by roughly 2,700x. This comes from two compounding effects — the cost of Miller-Rabin trial division and modular exponentiation grows with bit length, and the probability that a random odd number of a given bit length is prime falls off roughly as \(1/\ln(2^{bits})\) , so more candidates must be tried before a prime is found. For production RSA-2048, this pure-Python implementation could take minutes to tens of minutes to generate a key; production libraries (cryptography, OpenSSL, etc.) cut this to tens or hundreds of milliseconds using arbitrary-precision arithmetic libraries like GMP and optimized algorithms. Decryption (modular exponentiation) itself does not grow nearly as fast, staying around 33ms even at 1024 bits — key generation, not decryption, is the practical bottleneck.

Attacks That Arise From Mismanaging the Private Key

RSA’s security rests on the hardness of integer factorization, but mismanaging implementation or key handling opens up attacks that recover the private key or plaintext without ever factoring \(N\) . Below we derive the mathematics behind four well-known attacks — Wiener’s attack, the common modulus attack, padding-oracle attacks, and timing side channels — and then implement and verify each one.

When the Private Exponent d Is Too Small: Wiener’s Attack

It is tempting to speed up decryption (\(m = c^d \bmod N\) , equation \(\text{(5)}\) ) by fixing a small private exponent \(d\) first and deriving the public exponent \(e\) from it. Michael Wiener showed in 1990 that when \(p<q<2p\) and \(d\) is smaller than roughly \(N^{0.25}/3\) , the private key \(d\) can be efficiently recovered from the public key \((N, e)\) alone, using the continued fraction expansion of \(e/N\) .

Deriving the Attack

From the key-generation equation \(\text{(3)}\) , \(ed \equiv 1 \pmod{\varphi(N)}\) , so there exists a positive integer \(k\) with

(where \(k = (ed-1)/\varphi(N)\) ). Dividing both sides of equation \(\text{(8)}\) by \(d\varphi(N)\) gives

Note that any common divisor of \(k\) and \(d\) must divide \(1\) (from equation \(\text{(8)}\) ), so \(\gcd(k,d)=1\) — \(k/d\) is already in lowest terms, which the continued-fraction theorem we use below requires. Also, since \(e < \varphi(N)\) and \(ed = 1+k\varphi(N) > \varphi(N)\) forces \(d>1\) , we have \(k \ge 1\) .

The attacker knows \(N\) , not \(\varphi(N)\) , so we need to bound the error introduced by substituting \(e/N\) for \(e/\varphi(N)\) in equation \(\text{(9)}\) . Since \(\varphi(N) = N-p-q+1\) , \(\varphi(N) \approx N\) as long as \(p+q\) is small relative to \(N\) . Assuming the balanced prime selection \(p < q < 2p\) (common in RSA key generation), \(N = pq > p^2\) gives \(p < \sqrt{N}\) , and \(q < 2p\) gives

so \(N - \varphi(N) = p+q-1 < 3\sqrt{N}\) . Using this bound to evaluate \(e/N - k/d\) :

Applying the triangle inequality, \(e < \varphi(N)\) (so \(e/\varphi(N) < 1\) ), and equation \(\text{(10)}\) :

Since \(\varphi(N)\) has roughly the same number of digits as \(N\) , the second term \(1/(d\varphi(N))\) is negligible next to \(3/\sqrt{N}\) as long as \(d\) is at most on the order of \(N^{0.25}\) , so effectively

This is where the theorem on best rational approximations by continued fractions (Legendre’s theorem) comes in.

Theorem (best continued-fraction approximation). For a real number \(x\) and integers \(h, k\) with \(\gcd(h,k)=1\) , if \(|x - h/k| < 1/(2k^2)\) , then \(h/k\) is one of the convergents of the (simple) continued fraction expansion of \(x\) .

Comparing the bound in equation \(\text{(13)}\) to \(1/(2d^2)\) : \(3/\sqrt{N} < 1/(2d^2)\) means \(d^2 < \sqrt{N}/6\) , i.e.,

guarantees that \(k/d\) appears among the convergents of the continued fraction expansion of \(e/N\) . Because this derivation bounds the inequalities somewhat loosely, the constant is looser than the published result (Wiener’s original paper tightens the analysis to get the exact constant \(d < N^{0.25}/3 \approx 0.333\, N^{0.25}\) ), but the essential mechanism — once \(d\) falls below roughly the fourth root of \(N\) , it can be recovered from the public key alone via a continued fraction expansion — is exactly what this derivation shows.

The Attack Algorithm

Compute the convergents \(h_i/k_i\) of the continued fraction expansion \([a_0; a_1, a_2, \ldots]\) of \(e/N\) in order, and for each convergent (candidate \(k = h_i\) , candidate \(d = k_i\) ), substitute into equation \(\text{(8)}\) to check whether the candidate \(\hat\varphi = (e\hat d - 1)/\hat k\) is an integer (i.e., divides evenly). If it does, \(p+q = N - \hat\varphi + 1\) is known, so \(p, q\) can be recovered as the roots of the quadratic

(if the discriminant is a perfect square and the product of the roots equals \(N\) , the convergent was the correct \(k/d\) ).

import math


def continued_fraction(num, den):
    """Return the continued-fraction coefficients [a0, a1, ...] of num/den"""
    cf = []
    while den:
        a = num // den
        cf.append(a)
        num, den = den, num - a * den
    return cf


def convergents(cf):
    """Return the convergents (h_i, k_i) built from the continued-fraction coefficients"""
    convs = []
    h_prev2, h_prev1 = 0, 1
    k_prev2, k_prev1 = 1, 0
    for a in cf:
        h = a * h_prev1 + h_prev2
        k = a * k_prev1 + k_prev2
        convs.append((h, k))
        h_prev2, h_prev1 = h_prev1, h
        k_prev2, k_prev1 = k_prev1, k
    return convs


def wiener_attack(e, n):
    """Recover d from the public key (e, n) alone by exhausting convergents k/d"""
    cf = continued_fraction(e, n)
    for (k, d) in convergents(cf):
        if k == 0 or d == 0:
            continue
        if (e * d - 1) % k != 0:
            continue
        phi_candidate = (e * d - 1) // k  # invert equation (8)
        s = n - phi_candidate + 1  # candidate p + q (coefficient in eq. (15))
        disc = s * s - 4 * n
        if disc < 0:
            continue
        sqrt_disc = math.isqrt(disc)
        if sqrt_disc * sqrt_disc != disc:
            continue
        p = (s + sqrt_disc) // 2
        q = (s - sqrt_disc) // 2
        if p * q == n:
            return d, p, q
    return None

Verification 1: Recovering a Key With a Deliberately Small d

Using the earlier generate_prime and mod_inverse, we generated two 512-bit primes (\(N\) around 1024 bits), then deliberately chose a small \(d\) inside the \(N^{0.25}/3\) bound and derived \(e = d^{-1} \bmod \varphi(N)\) from it (a key-generation procedure that must never be used in practice).

import math
import random

random.seed(42)
bits = 512
p = generate_prime(bits)
q = generate_prime(bits)
n = p * q
phi = (p - 1) * (q - 1)

target_d_bits = int(math.log2(n) / 4) - 2  # aim for a bit length slightly below N^0.25
while True:
    d = random.getrandbits(target_d_bits) | 1
    if d > 2 and math.gcd(d, phi) == 1:
        e = mod_inverse(d, phi)
        if e > 1:
            break

result = wiener_attack(e, n)
recovered_d, rp, rq = result
message = 123456789
c = pow(message, e, n)
m2 = pow(c, recovered_d, n)
print(recovered_d == d, sorted([rp, rq]) == sorted([p, q]), m2 == message)

Running this, \(N\) came out to 1023 bits, and the chosen private exponent \(d\) was 253 bits (\(N^{0.25}\) ’s bit length is about 256 bits, so \(d\) was indeed inside the bound), well below the threshold \(N^{0.25}/3 \approx 3.060 \times 10^{76}\) . Feeding only this \((N, e)\) into wiener_attack, the recovered value matched the original \(d\) exactly, \(p\) and \(q\) were correctly recovered, and decrypting the ciphertext with the recovered \(d\) reproduced the original plaintext. The attacker never factored anything — the entire private key fell out of an \(O(\log N)\) -step continued fraction expansion.

Verification 2: Scanning the Success Rate Near the Boundary

The theoretical guarantee in equation \(\text{(14)}\) is a sufficient condition for guaranteed success; it says nothing about what happens once you cross it. So we varied the size of \(d\) as a ratio against \(N^{0.25}\) (using 256-bit primes, \(N\) around 512 bits), running 40-50 trials per ratio and measuring the attack’s success rate.

ratios = [0.33, 1, 1.5, 2, 3, 4, 6, 8, 12, 16, 24, 32, 48, 64, 100]
# For each ratio, choose d approximately equal to ratio * N**0.25,
# regenerate N via generate_prime(256), run trials_per_ratio=40-50 trials,
# and tally the fraction where wiener_attack(e, n) recovers the original d

As the figure shows, the ratios \(0.33\) and \(1\) — inside and just past the theoretical boundary (\(\text{ratio}=1/3\) ) — both succeeded 100% of the time. Just beyond that, ratios \(1.5\) and \(2\) still succeeded 74% and 78% of the time, decaying gradually as the ratio grows (20% at ratios \(6\) and \(8\) , 2% at ratio \(24\) ), reaching 0% success at ratio \(100\) . This is because the inequality in equation \(\text{(12)}\) is a worst-case sufficient condition, while in practice the error terms for a given \(p, q, e\) are often much smaller, so \(k/d\) frequently still turns up as a convergent well past the nominal boundary. The theoretical boundary is a conservative rule of thumb — in practice, even shrinking \(d\) to a small constant multiple of \(N^{0.25}\) is dangerous.

Practical Countermeasure

The recommended key-generation procedure used earlier in this article (the “Key Generation” section) fixes \(e = 65537\) first and computes \(d = e^{-1} \bmod \varphi(N)\) from it. The resulting \(d\) is a random value with roughly the same number of digits as \(\varphi(N)\) , far larger than \(N^{0.25}\) , so Wiener’s attack cannot apply in principle. What’s dangerous is choosing \(d\) small up front to speed up decryption (this is unrelated to RSA-CRT-based decryption speedups — CRT does not shrink \(d\) itself). Standards such as NIST SP 800-56B recommend checking during key generation that \(d\) is sufficiently large (a common rule of thumb is \(d > N^{0.5}\) ).

Reusing the Same Modulus N: The Common Modulus Attack

If multiple users share the same \(N\) (and hence the same \(p, q\) ) but use different public exponents \(e_1, e_2\) (with \(\gcd(e_1, e_2)=1\) ) to each encrypt the same plaintext \(m\) , the extended Euclidean algorithm alone recovers \(m\) — without ever learning \(p\) , \(q\) , or either private key \(d_1, d_2\) .

Deriving the Attack

The ciphertexts are

Since \(\gcd(e_1, e_2) = 1\) , Bezout’s identity guarantees the extended Euclidean algorithm can efficiently compute integers \(a, b\) (at least one negative) satisfying

The key observation: Wiener’s attack and this article’s proof of correctness (equations \(\text{(6)}\) -\(\text{(7)}\) ) both worked modulo \(\varphi(N)\) , but equation \(\text{(17)}\) is an exact integer equality that never touches \(\varphi(N)\) at all. Therefore

holds as an identity, with no need for Euler’s theorem at all. At least one of \(a, b\) will be a negative integer, but that is handled simply by computing \(c_1^{-|a|} \equiv (c_1^{-1})^{|a|} \pmod N\) using the modular inverse (see the “Modular Inverse” section earlier in this article).

Verification

We generated \(N\) from two 512-bit primes, encrypted the same plaintext twice under two different public exponents \(e_1, e_2\) sharing that \(N\) (having confirmed \(\gcd(e_1,e_2)=1\) ), then recovered the plaintext from the attacker’s viewpoint — knowing only \(N, e_1, e_2, c_1, c_2\) , and never touching \(p\) , \(q\) , or either private key.

message = int.from_bytes(b"COMMON MODULUS ATTACK DEMO", "big")
c1 = pow(message, e1, n)
c2 = pow(message, e2, n)

# The attacker knows only n, e1, e2, c1, c2
g, a, b = extended_gcd(e1, e2)  # same function as in the Euclidean algorithm article
assert g == 1

c1_term = pow(mod_inverse(c1, n), -a, n) if a < 0 else pow(c1, a, n)
c2_term = pow(mod_inverse(c2, n), -b, n) if b < 0 else pow(c2, b, n)
recovered = (c1_term * c2_term) % n

After confirming \(\gcd(e_1, e_2) = 1\) , the extended Euclidean algorithm returned \(a, b\) as huge integers (about the same number of digits as \(e_1, e_2\) ) that indeed satisfied \(a e_1 + b e_2 = 1\) . Computing recovered from these \(a, b\) via equation \(\text{(18)}\) matched the original message exactly, and converting it back to bytes reproduced the literal string b'COMMON MODULUS ATTACK DEMO'. Neither \(p\) , \(q\) , nor either private key \(d_1, d_2\) was used at any point.

Lessons and a Related Attack

The root cause is a mathematical fact: the moment \(N\) is shared, one party’s private key material can be used to “unlock” the other party’s ciphertext. The only fix is to always generate key pairs from an independent \(N\) (independent \(p, q\) ). A related but distinct scenario is Håstad’s broadcast attack (1988): sending the same message to multiple recipients under different \(N\) ’s but a small shared \(e\) (typically \(e=3\) ) allows the plaintext to be recovered using the Chinese Remainder Theorem instead of the extended Euclidean algorithm. The preconditions and number-theoretic tool differ, but the lesson — reusing keys or messages is fatal — is the same.

Vulnerabilities From Missing Padding: Padding-Oracle Attacks

This article’s implementation (encrypt/decrypt) is textbook RSA: it simply computes \(m^e \bmod N\) on the raw plaintext integer \(m\) . This has a structural problem. If \(m_1, m_2\) encrypt to \(c_1, c_2\) , then

holds — the product of ciphertexts is the ciphertext of the product of plaintexts — a multiplicative homomorphism (malleability) that lets an attacker tamper with ciphertexts in meaningful ways. Real-world RSA therefore always combines encryption with a padding scheme. Here we implement two historically important schemes, PKCS#1 v1.5 and OAEP, and verify their difference in security experimentally.

PKCS#1 v1.5 Padding and Bleichenbacher’s Attack

PKCS#1 v1.5 builds a \(k\) -byte encryption block (\(k\) being the byte length of \(N\) ) of the form

PS is a random non-zero byte string of at least 8 bytes; the 0x00 byte right after it marks where the message M begins. The decoder validates that the decrypted block conforms to this structure before extracting M.

In 1998, Daniel Bleichenbacher showed that this validation step could itself be abused as an oracle (a function that tells you whether a given ciphertext decrypts to validly-padded plaintext) — the so-called Million Message Attack. Given a target ciphertext \(c_0\) (encrypting an unknown plaintext \(m_0\) ), the attacker picks a known integer \(s\) and forms

This is the ciphertext of \(s \cdot m_0 \bmod N\) . Sending \(c'\) to the server and learning only “is the padding valid?” narrows down the range in which \(s \cdot m_0 \bmod N\) ’s leading bytes equal 0x00 0x02, and repeating this with adaptively chosen \(s\) eventually reconstructs \(m_0\) entirely (equation \(\text{(21)}\) exploits the exact same multiplicative homomorphism as equation \(\text{(19)}\) ; the key point is that the padding-validity check leaks exactly one bit of information from the server on every query).

Verification

We implemented PKCS#1 v1.5’s encode, decode, and oracle functions ourselves and verified the following (using a small RSA key of \(k\) bytes).

def pkcs1_v15_pad(msg, k):
    """EB = 0x00 || 0x02 || PS(random non-zero, >=8 bytes) || 0x00 || M"""
    ps_len = k - len(msg) - 3
    ps = bytes(random.randint(1, 255) for _ in range(ps_len))
    return b"\x00\x02" + ps + b"\x00" + msg


def pkcs1_v15_unpad_oracle(eb):
    """Padding oracle: returns only whether the structure (0x00 0x02 ... 0x00 ...) is valid"""
    if len(eb) < 11 or eb[0] != 0x00 or eb[1] != 0x02:
        return False
    idx = eb.find(b"\x00", 2)
    return idx != -1 and idx >= 2 + 8

First, we measured how often a random ciphertext happens to look “validly padded.” Since \(c^d \bmod N\) is nearly uniformly distributed over \(N\) when \(c\) is a uniform random integer, decrypting with the real RSA private key and bypassing decryption to sample uniform integers directly are statistically the same distribution (we cross-checked this equivalence on a small 192-bit \(N\) , running 300,000 trials each way and getting zero hits both times). Using this equivalence on a practically-sized 2048-bit RSA key, 5 million trials by direct uniform sampling produced 86 hits judged validly padded — an observed probability of \(1.72\times10^{-5}\) (about 1 in 58,140), close in order of magnitude to the theoretical baseline of \(2^{-16} \approx 1.53\times10^{-5}\) based on just the two leading bytes matching.

Next, we reproduced Bleichenbacher’s first attack step (the so-called “blinding” search — trying successive \(s\) in equation \(\text{(21)}\) until the first one produces valid padding) using only queries to the padding oracle, never the private key directly (with a small 192-bit RSA key; oracle_query internally performs a real private-key decryption on every call).

s = 2
while True:
    c_candidate = (c0 * pow(s, e, n)) % n
    if oracle_query(c_candidate):  # internally runs pow(c_candidate, d, n) and checks padding
        break
    s += 1

The result: the first valid padding turned up at \(s = 1{,}265{,}823\) , requiring 1,265,822 oracle queries — each one a genuine RSA decryption — before that. This “on the order of a million queries” scale is exactly why Bleichenbacher’s attack is called the Million Message Attack. Real attacks then continue with a binary-search-style narrowing of the interval, so depending on key size and server response time, the entire ciphertext can be decrypted without ever touching the private key, using anywhere from thousands to millions of oracle queries.

OAEP: A Solution in the Random Oracle Model

OAEP (Optimal Asymmetric Encryption Padding, Bellare–Rogaway, 1994) uses a hash function \(H\) and a mask generation function \(\text{MGF1}\) (which repeatedly applies a hash to produce a mask of arbitrary length) to thoroughly scramble the entire message with a random seed.

The decisive difference from PKCS#1 v1.5 is that validity reduces to a bit-for-bit exact match against the hash value \(H(\texttt{label})\) . PKCS#1 v1.5’s check was a loose structural test (“the leading two bytes are fixed, and a 0x00 appears somewhere”); with OAEP (using SHA-256), the entire 256-bit hash value must match, or the block is rejected. Under the random oracle model (an analytical technique that treats a hash function as an ideal random function), OAEP is proven to achieve IND-CCA2 security (indistinguishability under adaptive chosen-ciphertext attack — even an attacker holding a decryption oracle learns nothing about the plaintext) from nothing more than the assumption that RSA is a trapdoor one-way permutation.

Verification

We implemented OAEP’s encode/decode using hashlib.sha256 and a hand-written MGF1, confirmed correctness through an actual RSA encryption/decryption round trip, and verified the following (SHA-256 adds \(2 \times 32 + 2 = 66\) bytes of overhead, so we used two 300-bit primes giving \(N\) around 599 bits).

def oaep_unpad(em, k, label=b""):
    """Combine all checks into a single boolean without early returns
    (early returns that branch on the failure reason are exactly what enables Manger's attack)"""
    l_hash = hashlib.sha256(label).digest()
    y = em[0]
    masked_seed, masked_db = em[1:1+32], em[1+32:]
    seed = xor_bytes(masked_seed, mgf1(masked_db, 32))
    db = xor_bytes(masked_db, mgf1(seed, k - 33))
    l_hash_prime, rest = db[:32], db[32:]
    sep_idx = rest.find(b"\x01")
    ps_ok = sep_idx != -1 and all(b == 0 for b in rest[:sep_idx])
    valid = (y == 0) and (l_hash_prime == l_hash) and ps_ok
    return valid, (rest[sep_idx+1:] if valid else None)

For this 599-bit key, out of 50,000 random ciphertexts decrypted through real RSA private-key decryption, zero were judged validly padded (the requirement of an exact 256-bit lHash match already puts the probability on the order of \(2^{-256}\) , so an astronomical number of trials would be needed before a coincidental match could ever occur). We then took a genuinely encrypted-and-decrypted plaintext block EM, flipped a single bit in it, generated 2,000 such single-bit-flip variants, and checked whether any passed the oracle’s validity check afterward — all 2,000 were correctly rejected. Where PKCS#1 v1.5’s check only inspects the leading two bytes and the separator byte (so changes deep inside PS go unnoticed), OAEP’s \(\text{MGF1}\) -based diffusion means any single bit flipped in the ciphertext changes the entire decoded output unpredictably, almost certainly breaking the strong hash-equality check — a result this experiment confirms quantitatively.

Manger’s Attack and ROBOT: Implementation Pitfalls

OAEP’s security proof assumes the decryption oracle reveals only a single valid/invalid bit. But in 2001, James Manger showed that implementing OAEP’s checks as a series of early returns — if y != 0: raise ..., then if l_hash_prime != l_hash: raise ..., and so on — leaks whether the leading byte \(Y\) is zero through the type of error or the response timing, enabling a Bleichenbacher-style narrowing attack all over again. This is exactly why the code in the previous section computed valid = (y == 0) and (l_hash_prime == l_hash) and ps_ok as a single expression with no early return. Then in 2018, the ROBOT attack (Böck, Somorovsky, Young) demonstrated that implementations from nine or more vendors — F5, Citrix, IBM, and others — were still vulnerable to Bleichenbacher’s 20-year-old attack running directly against TLS servers. The lesson from these two attacks: a padding scheme’s security proof and the security of the code that implements it are two separate problems, and the latter is guaranteed only by implementation-level discipline — constant-time execution and uniform error handling.

A Note on Timing Side Channels: Decryption Must Run in Constant Time

Where padding-oracle attacks exploit differences in what the server’s response says, timing side-channel attacks exploit differences in how long it takes to say it. As detailed in the article on exponentiation by squaring and the Montgomery ladder , a naive binary exponentiation \(c^d \bmod N\) performs a number of multiplications that depends on the Hamming weight of the secret exponent \(d\) , so statistical differences in execution time leak information about the secret key’s bit pattern (Paul Kocher, 1996, a proof-of-concept demonstrated against RSA, DH, and DSS). That article’s measurements, under a 2048-bit-scale modulus, found that naive binary exponentiation showed up to a 121.6% timing difference between conditions, while the Montgomery ladder’s difference was only 0.1% — nearly perfectly independent of the bit pattern.

Interestingly, the “try successive values of \(s\) ” operation used in our Bleichenbacher implementation above is conventionally called “blinding” in cryptography — but it means the opposite thing here. Attacker-side blinding (as in Bleichenbacher’s attack) extracts secret information by repeatedly multiplying by a known \(s\) and querying the server, whereas defensive RSA blinding (Kocher’s proposed countermeasure against timing attacks) computes \(c' = c \cdot r^e \bmod N\) for a random value \(r\) unpredictable to the attacker, decrypts that, and then corrects the result by multiplying by \(r^{-1}\) — making execution time depend on a random value outside the attacker’s control, breaking any correlation with the secret exponent \(d\) ’s bit pattern. That the same mathematical operation (exploiting multiplicative homomorphism) is used both offensively and defensively nicely illustrates that RSA’s structural feature (equation \(\text{(19)}\) ) is a double-edged sword. In practice, production systems combine the Montgomery ladder’s uniform operation count with RSA blinding’s randomization so that execution time leaks no information about the secret key whatsoever.

RSA’s Security Today, and the Move to Post-Quantum Cryptography

Finally, let’s take stock of where RSA’s security stands today.

The largest classical factorization on record remains RSA-250 (829 bits), factored via GNFS (the General Number Field Sieve) in 2020; the practically-used RSA-2048 (2048 bits) remains unfactored. Around 2024, claims circulated that D-Wave-style quantum annealers had “factored RSA-2048,” but these used methods entirely unrelated to Shor’s algorithm and pose no threat to any practically-sized RSA key (as of 2025, the largest number ever factored by a faithful implementation of Shor’s algorithm on real quantum hardware remains around 48 bits). On the theoretical side, however, Craig Gidney published a paper in May 2025 lowering the estimated physical-qubit requirement for factoring RSA-2048 — even accounting for error-correction overhead — to under one million qubits and under one week of runtime (a major improvement over the roughly 20 million qubits estimated in 2019). Current quantum computers still have several orders of magnitude fewer physical qubits than this, so RSA-2048 is in no immediate danger, but this trajectory is exactly why proactive migration is underway worldwide.

On the standardization front, NIST finalized the lattice-based post-quantum standards FIPS 203 (ML-KEM, formerly CRYSTALS-Kyber, key encapsulation), FIPS 204 (ML-DSA, formerly CRYSTALS-Dilithium, signatures), and FIPS 205 (SLH-DSA, hash-based signatures) in August 2024, closing out a standardization process that began in 2016. The following NIST IR 8547 (a migration-plan draft, November 2024) lays out a timeline in which 112-bit-security algorithms such as RSA-2048 and ECC P-256 are to be deprecated by 2030 and disallowed by 2035. For the mechanics of why the number-theoretic problem underlying RSA (integer factorization) falls to Shor’s algorithm on a quantum computer in polynomial time, and why lattice problems (Learning With Errors) are believed to resist quantum computers, see our introduction to post-quantum cryptography , which implements the Regev cryptosystem from scratch.

Security Considerations (Summary)

This implementation is for educational purposes and should not be used in production for the following reasons:

• Lack of padding: Textbook RSA has a multiplicative homomorphism (equation \(\text{(19)}\) ) and is vulnerable to chosen-ciphertext attacks. Production systems need a provably-secure padding scheme like the OAEP verified above.
• The size of the private exponent d: Shrinking \(d\) to speed things up lets Wiener’s attack recover it from the public key alone. Following the standard procedure of deriving \(d\) from \(e=65537\) avoids this entirely.
• Reusing N: Sharing a modulus \(N\) across multiple key pairs enables the common modulus attack to recover plaintext. Key pairs must always be generated from independent \(p, q\) .
• Timing side channels: An implementation without constant-time guarantees leaks secret-key information through decryption’s execution time. Production systems need the Montgomery ladder combined with RSA blinding.
• Key size: This implementation’s default of 512 bits is no longer secure. A minimum of 2048 bits is recommended for production use, and RSA itself is slated for migration away from during the 2030s.
• Quantum computing threat: Shor’s algorithm lets a sufficiently large quantum computer factor integers in polynomial time. Migration to Post-Quantum Cryptography is underway worldwide.

Related Articles

• OAuth 2.0 and OpenID Connect: Fundamentals of Authorization and Authentication - RSA is used in JWT signature verification for OAuth 2.0/OIDC.
• Zero Trust Architecture: Principles, Components, and Implementation - RSA serves as a foundational cryptographic technology in Zero Trust.
• Post-Quantum Cryptography in Python: Learning With Errors (LWE) and Regev Encryption - Explains why this article’s factoring problem is broken by Shor’s algorithm on a quantum computer, and the LWE problem that replaces it.
• Security Certification Comparison: CISSP vs Japan’s Registered Information Security Specialist - Compares security certifications whose exam scope includes cryptographic technologies.
• Diffie-Hellman Key Exchange Protocol: Theory and Python Implementation - A protocol that achieves secure key exchange using a different approach from RSA.
• Euclidean Algorithm and Extended Euclidean Algorithm in Python - Proves the correctness, complexity, and Bezout’s-identity construction behind the modular inverse computation this article uses to generate the private key.
• Fast Modular Exponentiation Using Binary Exponentiation in Python - Explains the exponentiation by squaring algorithm used in RSA encryption and decryption.
• Elliptic Curve ElGamal Encryption: Principles and Simplified Python Implementation - A public-key cryptosystem based on a different mathematical foundation (discrete logarithm problem on elliptic curves).
• Cryptography Roadmap: Symmetric, Public-Key, Hash, and Key Exchange Hub — Places RSA in the “public-key (integer factorization)” slot and maps its relation to DH, elliptic-curve cryptography, and hash functions.
• Diffie-Hellman Key Exchange: Theory and Python Implementation (Discrete Log) — A key-exchange protocol whose security rests on the discrete logarithm problem rather than integer factorization; the contrast clarifies both.
• Elliptic Curve Cryptography (ECC) in Python — The modern mainstream: 256-bit keys matching RSA-3072 security, with point addition, ECDLP, ECDH, ECDSA, and X25519 in depth.
• AES and ChaCha20 in Python — The symmetric ciphers that carry the bulk data in hybrid encryption precisely because RSA is slow; rounds, GF(2^8), cipher modes, and AEAD in depth.
• Digital Signatures (ECDSA / EdDSA / RSA-PSS) in Python — The signature side of RSA in practice: RSA-PSS randomized padding and the hash-then-sign paradigm in depth.

Related Tools

• Hash Generator (DevToolBox) - Hash generation tool supporting MD5 and SHA

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.
• Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.