RSA Part 3: Your Correct Implementation Still Leaks the Key

Your RSA implementation passes every test. Key generation works. Encryption and decryption round-trip. The math is provably right.

A motivated attacker can still recover your private key.

Not by breaking the math. Not by factoring the modulus with a sieve. By watching how long your code takes to run.

In 1996 Paul Kocher showed that timing measurements of RSA operations could recover private keys. In 2003 David Brumley and Dan Boneh extended it to OpenSSL running on real hardware — over a campus network, between buildings, with three routers and multiple switches in the path. The timing differences were microseconds. The key came out anyway.

Part 1 built the math. Part 2 made it handle real data. This part is about the gap between an implementation that is correct and one that is safe, which are unrelated properties.

The Leak, Measured

Go back to modpow from Part 1:

def modpow(b, e, n):
    tst = 1
    siz = 0
    while e >= tst:
        tst <<= 1
        siz += 1
    siz -= 1
    r = 1
    for i in range(siz, -1, -1):
        r = (r * r) % n        # Square: always happens
        if (e >> i) & 1:
            r = (r * b) % n    # Multiply: only when the bit is 1
    return r

Every iteration squares. Only 1-bits also multiply. So the total work is a direct function of the Hamming weight of the exponent — and during decryption, that exponent is the private key.

That is measurable. Two exponents of identical bit length, one with 2 bits set and one with 1024, against a 2048-bit modulus:

  modpow   : low-weight   10.94 ms | high-weight   11.85 ms | ratio 1.084x

Eight percent. Small, consistent, and in the direction the algorithm predicts. That is the entire foothold.

Be precise about what an attacker does with 8%, because "timing attack" gets used loosely. Nobody reads a key from one measurement. The attack collects thousands of decryptions and, for each bit position, correlates observed time against the time the operation would take if that bit were set. Noise averages out. Signal doesn't. The key emerges bit by bit.

What Brumley and Boneh Actually Did

Worth correcting a description that circulates widely, including in earlier versions of this article.

The attack did not extract the bits of d one at a time. From the paper: OpenSSL generates moduli N = pq where q < p, and "In each case we target the smaller factor, q. Once q is known, the RSA modulus is factored."

They recovered a prime factor, not the private exponent. The mechanism is a binary search on q: guess a value g sharing the top i-1 bits, measure decryption time for g and a neighbour, and the difference between those two times reveals whether the next bit is 0 or 1. It exploits extra Montgomery reductions and multiplication-routine switches in OpenSSL, not the square-and-multiply branch.

Once you have q, you have p = N/q, and from there d follows directly. Same outcome, different route — and knowing which is which matters if you ever read the literature, because the defenses differ.

One detail from the paper worth keeping: "The number of samples required to reach a stable decryption time is surprisingly small, requiring only 5 samples." Five, per measurement point. The cost is in the number of points, not the sampling depth.

Defense One: The Montgomery Ladder

The fix for a data-dependent branch is to remove the dependence. The Montgomery Ladder keeps two running values and updates both every iteration, so the work is identical whether the bit is 0 or 1.

def modpow_ct(b, e, n):
    """
    Constant-time modular exponentiation: the Montgomery Ladder.
    One multiply and one square per bit, regardless of the bit's value.
    """
    r0 = 1       # r0 = b^0
    r1 = b       # r1 = b^1
 
    for i in range(e.bit_length() - 1, -1, -1):
        if (e >> i) & 1 == 0:
            r1 = (r0 * r1) % n
            r0 = (r0 * r0) % n
        else:
            r0 = (r0 * r1) % n
            r1 = (r1 * r1) % n
    return r0

The branch still exists, but both arms do exactly one multiplication and one squaring. What changes is which variable is updated, not how much work happens.

Does it work? Same test as above:

  modpow   : low-weight   10.94 ms | high-weight   11.85 ms | ratio 1.084x
  modpow_ct: low-weight   24.50 ms | high-weight   23.71 ms | ratio 0.968x

The leak is gone. 1.084× becomes 0.968× — the residual is below the noise floor, and it points the wrong way, which is what "no signal" looks like.

The Cost Nobody Quotes

Look at the absolute numbers in that table, because this is the part usually left out: the ladder is roughly twice as slow. 24.5ms against 10.94ms in that run.

That is the trade. You are doing a multiplication on every bit instead of on half the bits, on average, so you should expect to pay for it. Measured on a smaller key with a realistic decryption workload:

  plain modpow          5.84 ms   (1.00x)
  modpow_ct             7.85 ms   (1.34x)
  blinded + modpow_ct   8.55 ms   (1.47x)

Between 1.3× and 2× depending on key size and exponent weight. For a service doing RSA on every request that is a real capacity decision, and it is the correct one to make — but make it knowingly rather than discovering it in a load test.

The Python Caveat

The ladder removes the algorithmic timing signal. It does not make Python constant-time.

Python's integers are arbitrary-precision with variable-length internal representation, so a 2047-bit value and a 2048-bit value occupy different numbers of machine words and take different time to process. The garbage collector introduces pauses. The interpreter has its own variable overhead.

For a genuine constant-time guarantee you need fixed-width integers and control over memory layout — C written carefully, or Rust with something like subtle. In Python the ladder is a large improvement over modpow and not a complete answer, and the section on the Marvin Attack below shows exactly how far short it falls.

Defense Two: Blinding

Blinding attacks the problem from the other side. Instead of making decryption take constant time, it makes the input random, so timing measurements describe a value the attacker doesn't know.

1. Choose random r with gcd(r, n) = 1
2. Blind: c_blind = c * r^e mod n
3. Decrypt: m_blind = c_blind^d = c^d * r^(ed) = m * r (mod n)
4. Unblind: m = m_blind * r^(-1) mod n
   Step 3 works because (r^e)^d = r^(ed) = r — the same relationship that makes RSA work at all.

def decrypt_blinded(c, priv, pub):
    d, n = priv
    e, _ = pub
 
    while True:
        r = secrets.randbelow(n - 2) + 2
        if math.gcd(r, n) == 1:
            break
 
    c_blind = (c * modpow(r, e, n)) % n     # r^e uses the PUBLIC exponent
    m_blind = modpow_ct(c_blind, d, n)      # constant-time on blinded input
    return (m_blind * pow(r, -1, n)) % n    # unblind

Verified against eight random messages on a freshly generated key:

  blinded decryption correct for all 8 messages: True

Note that r^e uses the public exponent, so that operation leaks nothing — anyone can compute it.

Why blinding beats constant-time alone. The ladder removes one specific signal. Blinding removes the attacker's ability to use any timing signal, because whatever the timing depends on, it now also depends on an r that changes every call and that they cannot observe. Correlating measurements against a chosen ciphertext stops working, because the ciphertext being decrypted is not the one they chose.

OpenSSL added blinding in 2003, in direct response to Brumley–Boneh. Real implementations use both defenses, and the measured cost of doing so is the 1.47× in the table above.

These Defenses Are Not Sufficient

Everything above is the textbook answer, and for two decades it was the whole answer.

It isn't any more. In 2023 the Marvin Attack broke implementations that had been patched and declared immune — including pyca/cryptography, the library this article recommends — and the flaw was not in the exponentiation these defenses harden. It was in the integer arithmetic underneath, which means it affects every padding mode including OAEP.

Two operations survive both defenses: the unblinding multiply and the integer-to-bytes conversion, both of which touch real plaintext after blinding has stopped protecting anything. Measured on Python's own integers:

  int.to_bytes(256): small   284.7 ns | large   314.2 ns | ratio 1.104x
  modular multiply : small  1638.4 ns | large  1943.4 ns | ratio 1.186x

Neither figure involves the exponent. The ladder removes the exponent signal, blinding removes the ciphertext signal, and the plaintext-size signal survives both.

Part 4 covers the attack, the three-year disclosure timeline, and what actually fixes it.

Three Things This Series Got Wrong, Carried Forward

Part 3 inherits code from Parts 1 and 2, including their bugs. If you are assembling the full implementation, three fixes travel with it.

The block size is off by one. Part 2's encrypt_bytes reads 256-byte plaintext blocks against a 2048-bit modulus:

  largest 256-byte value fits under a 2048-bit modulus? False
  largest 255-byte value fits under a 2048-bit modulus? True

A 256-byte block can exceed n, and when it does the data is silently reduced mod n — no exception, correct-looking decryption, wrong bytes. Use BLOCK = 255, generally (key_bits // 8) - 1.

The public exponent is non-compliant. keysgen uses e = 35537, carried over from Part 1 where it kept the worked examples small. FIPS 186-5 requires 2^16 < e < 2^256, and 35537 < 65536. It is also slower than 65537 despite being smaller, because it has seven bits set against 65537's two.

Key generation has no coprimality check. If gcd(e, λ(n)) != 1 there is no modular inverse, and an unguarded keysgen returns d = 1 without raising. Every message then decrypts to garbage. Add the check and regenerate the primes.

What Still Isn't Covered

The defenses above address the exponentiation. Production RSA has more layers, and each is a place to get it wrong.

CRT introduces its own attack. Real implementations decrypt modulo p and q separately and recombine. It's a large win — measured on a 2048-bit key, 3.31×, not the 4× usually quoted. But a computation fault during CRT decryption lets a chosen ciphertext reveal enough to factor n. Boneh, DeMillo and Lipton found this in 1996. The fix is validating the CRT result before returning it, and Part 1's re-encryption check is exactly that.

OAEP is not optional. Textbook RSA is deterministic and malleable — Parts 1 and 2 demonstrated both. Bleichenbacher's 1998 attack showed a PKCS#1 v1.5 implementation could be broken with an adaptive chosen-ciphertext attack against a decryption oracle, and any server returning distinguishable errors for different failures is one.

Cache timing sits below all of this. An L1 hit costs about 4 cycles; a miss to RAM costs 200+. If which cache lines you touch depends on the key, an attacker sharing your physical machine — routine in cloud environments — can measure it. Neither defense here addresses that.

And It Has an Expiry Date

One more thing a 2021 article could not have said.

Part 1 flagged it in passing: 2048-bit RSA is 112-bit security, and that exact strength has a deprecation date attached to it now.

Part 5 covers what that means, why the migration starts before a quantum computer exists, and what carries forward from everything in this series.

Use the Library

from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP
 
key = RSA.generate(2048)
cipher = PKCS1_OAEP.new(key.publickey())
ciphertext = cipher.encrypt(b"Production-safe RSA encryption")
 
plaintext = PKCS1_OAEP.new(key).decrypt(ciphertext)

Four lines. OAEP, blinding, CRT with fault validation, constant-time operations, and a correct block size — all handled, all audited.

Worth confirming rather than trusting, since the whole series has been about not trusting crypto code. Running that example, plus the two failures Parts 1 and 2 demonstrated:

  article example runs: True
  key size: 2048 bits, e = 65537
  ciphertext length: 256 bytes
 
  OAEP: same plaintext -> different ciphertext: True
  both decrypt correctly: True
  tampered ciphertext rejected: ValueError

Three things in those results close the series.

e = 65537 by default — you don't get to pick 35537 by accident.

The same plaintext produces different ciphertext. Part 1 showed raw RSA encrypting 80087 to 539186383 every single time; OAEP's randomness kills that, and both ciphertexts still decrypt correctly.

A single flipped bit is rejected with an exception. Part 2 showed raw RSA is malleable — multiply the ciphertext by f^e and the plaintext becomes f × m. Here, tampering raises ValueError instead of returning plausible garbage.

That is what the library is doing for you, stated as measurements rather than reassurance.

The cryptography library gives you the same guarantees with a more explicit API, and its private key object confirms something Part 1 explained abstractly:

  private key stores: p, q, d, dmp1, dmq1, iqmp -> True
  dmp1 bits: 1023 | d bits: 2047   <- CRT exponents are half-size

dmp1 and dmq1 are d mod (p-1) and d mod (q-1) — the CRT exponents. Half the bit length of d, which is exactly why CRT decryption measured 3.31× faster. A real private key is not one number; it's six, and five of them exist purely to make decryption fast enough to be practical.

One naming detail worth noticing: the import path is cryptography.hazmat.primitives. Hazmat. The maintainers put the word "hazardous materials" in the module path for the layer where you assemble primitives yourself, because that is the layer where this series' three bugs live.

Note PKCS1_OAEP, not PKCS1_v1_5. Both exist in the library and the second one is the padding Marvin attacks. If you find yourself reaching for v1.5 for compatibility with something old, that is the moment to fix the something old.

And the honest framing, given everything above: using a maintained library does not mean the problem is solved. It means the problem is somebody's full-time job, they publish CVEs when they find one, and you get the fix by upgrading. That is a fundamentally better position than owning the bug yourself and never hearing about it — which is what shipping the code in this series would actually buy you.

That is what this series was for. Not as an alternative to the library, but so that when you write PKCS1_OAEP.new(public_key) you know what OAEP is fixing, why PKCS#1 v1.5 wasn't enough, what blinding has to do with timing, and why the private key object stores p, q, dP, dQ and qInv rather than just d.

The three-part arc, in one line each. Part 1: the math is simple and the toy implementation factors in under two milliseconds. Part 2: making it real introduces a block-size bug that eats your data silently. Part 3: even a correct implementation broadcasts its private key through the clock, fixing that costs between 1.3× and 2× throughput, and a 2023 attack shows the fix is still incomplete in any language with variable-width integers.

Every one of those failures produced working-looking code. Not one of them threw an exception. That is the actual lesson, and it is why the last section of this series is an argument for using somebody else's.