RSA Part 2: Real Primes, Real Text, and a Bug That Eats Your Data

Part 1 built a working RSA implementation. Keys generate, integers encrypt, decryption returns what you put in. The math is correct and the implementation is complete for what it does.

What it does is very limited.

The primes were p = 31337 and q = 31357 — 15 bits each, giving a 30-bit modulus. Factoring that is not a challenge:

trial division of n=982634309 found p=31337 in 1.87 ms

Under two milliseconds with the most naive method there is. That encryption isn't weak, it's theatre.

Two problems make Part 1 unfit for real use: toy primes and integer-only encryption. This fixes both — a prime generator producing cryptographically sized candidates, the Fibonacci machinery needed to validate them, and byte-level block encryption for actual messages.

And then it shows you the bug that comes free with the standard approach to the second one.

Generating Cryptographically Secure Primes

The approach is straightforward: generate a large random odd number, test whether it's prime, repeat. Three questions decide whether it's any good.

How large. For 2048-bit RSA you need two primes of roughly 1024 bits each. NIST deprecated 1024-bit keys in 2010 and prohibits them in federal systems — but that's the modulus, not the primes. Two 1024-bit primes give a 2048-bit modulus, which is the current minimum.

How random. This one is not a style choice:

import secrets, random
 
# random -- predictable from seed, wrong for cryptography
bad_candidate = random.getrandbits(1024)
 
# secrets -- OS CSPRNG, appropriate for key material
good_candidate = secrets.randbits(1024)

random is a Mersenne Twister: statistically excellent, completely deterministic given the seed, and recoverable from a few hundred observed outputs. secrets draws from /dev/urandom on Linux and macOS, BCryptGenRandom on Windows. If a number will become key material, it comes from secrets.

What test. Trial division is hopeless at 1024 bits. Two probabilistic approaches exist.

Miller-Rabin is the modern standard: given a candidate and k random witnesses, the probability a composite passes all of them is at most 4^(-k). Twenty witnesses puts that below 10^(-12).

The Lucas-Fibonacci condition is what this implementation uses, combined with a Fermat test. That pairing is the basis of the Baillie–PSW test — named for Baillie, Pomerance, Selfridge and Wagstaff. Worth getting right, because "PWS" and "Selfridge's conjure" both circulate and neither will find you the literature. It's Selfridge's conjecture: that no composite passes both conditions. None has ever been found, and there's a standing cash prize for one.

Fibonacci Numbers, Fast

The Lucas condition needs the (p+1)-th Fibonacci number modulo p, where p is 1024 bits. Stepping there one addition at a time is not an option.

The recurrence is a matrix:

[ F(n+1) ]   [ 0 1 ]^n   [ 1 ]
[ F(n)   ] = [ 1 1 ]   * [ 1 ]

Matrix multiplication is associative, so the binary exponentiation from Part 1 applies directly — O(log n) matrix multiplications instead of n additions.

def sqmatrixmul(m1, m2, w, mod):
    """Multiply two w x w matrices modulo mod."""
    mr = [[0 for j in range(w)] for i in range(w)]
    for i in range(w):
        for j in range(w):
            for k in range(w):
                mr[i][j] = (mr[i][j] + m1[i][k] * m2[k][j]) % mod
    return mr
 
def fib(x, mod):
    """x-th Fibonacci number mod `mod`, via matrix exponentiation."""
    if x < 3:
        return 1
    x -= 2
 
    tst = 1
    siz = 0
    while x >= tst:
        tst <<= 1
        siz += 1
    siz -= 1
 
    fm = [[0, 1], [1, 1]]   # function matrix
    rm = [[1, 0], [0, 1]]   # result matrix (identity)
 
    for i in range(siz, -1, -1):
        rm = sqmatrixmul(rm, rm, 2, mod)
        if (x >> i) & 1:
            rm = sqmatrixmul(rm, fm, 2, mod)
    return (rm[1][0] + rm[1][1]) % mod

Check it against the actual sequence before trusting it with anything:

fib(1..12) : [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144]
expected   : [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144]
MATCH: True

The Generator

Candidates are restricted to 3 (mod 10) or 7 (mod 10) — equivalently, odd and ±2 (mod 5). Both are necessary conditions for primality above 5, and filtering to them discards obvious composites before the expensive tests run.

import secrets
 
def genprime(siz):
    while True:
        num = (1 << (siz - 1)) + secrets.randbits(siz - 1) - 10
        num -= num % 10
        num += 3                                    # 3 (mod 10)
        if modpow(2, num - 1, num) == 1 and fib(num + 1, num) == 0:
            return num
        num += 4                                    # 3 + 4 = 7 (mod 10)
        if modpow(2, num - 1, num) == 1 and fib(num + 1, num) == 0:
            return num

That += 4 is worth pausing on, because += 5 appears in a lot of copies of this function and looks equally plausible. Three plus five is eight. An even number, never prime, so the second test could never succeed and every failed iteration would waste a full Fibonacci computation. Four is correct, and you can confirm the generator reaches both classes:

residues from genprime: [3, 7]

The (1 << (siz - 1)) sets the high bit so the result is genuinely siz bits — without it a 1024-bit request could return a 200-bit number and a catastrophically weak key. The - 10 leaves room for the adjustment arithmetic without overflowing that bit length.

Generation is faster than you'd expect. Median of three runs:

genprime(1024): ['1.12s', '0.53s', '0.15s']  median 0.53s
produced a 1024-bit prime, 309 decimal digits

Around half a second, with real variance because it's a random search — one run took over a second, another took 0.15. "A few seconds" overstates it, and either way key generation is a once-per-certificate cost.

Worth checking that what comes out is actually prime. Sixty candidates from genprime, each independently verified with 40 rounds of Miller-Rabin:

60/60 primes from genprime() confirmed by Miller-Rabin (40 rounds)
false positives: 0

Which is what you'd hope, given no composite has ever been found that passes both conditions — but the test is cheap and the alternative is trusting a heuristic on faith.

It's also worth seeing why the pairing works, because either condition alone is weak. The Fermat test to base 2 has famous failures — the base-2 pseudoprimes — and they are exactly what the Fibonacci condition catches:

  composite  341: fermat-base-2 passes=True, fibonacci passes=False, BOTH=False
  composite  561: fermat-base-2 passes=True, fibonacci passes=False, BOTH=False
  composite  645: fermat-base-2 passes=True, fibonacci passes=False, BOTH=False
  composite 1105: fermat-base-2 passes=True, fibonacci passes=False, BOTH=False

Every one of those is composite. Every one passes the Fermat test — 561 is a Carmichael number, which fools Fermat for every base coprime to it. And every one fails the Fibonacci condition.

That is the whole design of Baillie–PSW: two tests whose failure modes don't overlap. The composites that fool one are precisely the ones the other rejects, which is why the combination has held for forty years with no counterexample despite a standing prize.

And the index matters. The condition is on F(p+1), not F(p) or F(p-1):

  p    p%10  F(p+1) mod p
    7   7        0
   13   3        0
   17   7        0
  ...
  16 of those satisfied the condition

Sixteen for sixteen across primes in both residue classes. An off-by-one in that index would still return numbers, still look like it worked on small tests, and quietly accept composites.

On the density question, the Prime Number Theorem gives real numbers here:

ln(2^1024) = 709.8
density of primes near 2^1024: 1 in 710
odd numbers only -> 1 in 355
restricted to 3,7 mod 10 -> 1 in 142

So roughly one in 710 numbers that size is prime, one in 355 odd ones — and with the residue filter you're testing about one in 142. That filtering is why this is seconds rather than minutes.

For scale: a 1024-bit prime is a 309-digit decimal number, and the resulting modulus is 617 digits.

The Exponent You Inherited Isn't Standard

Part 1 used e = 35537 and said why: small enough to trace by hand. Part 2 keeps the same keysgen and now feeds it real 1024-bit primes — which quietly promotes a teaching shortcut into a production parameter.

Three problems come with it.

It's below the FIPS floor.

  e used in keysgen : 35537
  FIPS 186-5 floor  : 2^16 = 65536
  is 35537 > 2^16?  False   <-- FIPS requires 2^16 < e < 2^256

FIPS 186-5 requires e to be an odd integer with 2^16 < e < 2^256. 65537 is 2^16 + 1, the smallest legal value. 35537 is smaller than 65536, so a key generated this way is outside the standard before it encrypts anything.

It's slower, despite being a smaller number. Modular exponentiation costs one squaring per bit plus one multiplication per set bit:

  35537 in binary: 0b1000101011010001  (7 bits set)
  65537 in binary: 0b10000000000000001  (2 bits set)
 
  encrypt with e=35537:  0.291 ms
  encrypt with e=65537:  0.218 ms

A third slower. 65537 is a Fermat prime — one, fourteen zeros, one — so it costs 16 squarings and a single multiply. 35537 has seven bits set and costs six extra multiplications on every encryption and every signature verification, forever. The "smaller number is faster" intuition is exactly backwards here.

And keysgen fails silently when e shares a factor with λ(n). Rare — roughly one key in eighteen thousand — but there is no error path:

    p-1 = 71074 = 2 * 35537
    gcd(35537, lambda_n) = 35537
    keysgen returned d = 1  (no error raised)
    e*d mod lambda_n = 35537   <- must be 1 for RSA to work
    round-trip 12345 -> 1986409050   OK=False

d = 1, returned cheerfully, and every message decrypts to garbage. The extended Euclidean algorithm returned a gcd rather than an inverse, and nothing checked which it was.

Real key generation loops on this: verify gcd(e, λ(n)) == 1, and if not, discard both primes and start over. Go's FIPS 140 module does exactly that, and notes the failure probability is around 2⁻¹⁵ so the retry costs nothing.

For Part 2, switch to the standard value and add the check:

def keysgen(p, q):
    n = p * q
    lambda_n = (p - 1) * (q - 1)
    e = 65537                                  # FIPS-compliant, 2 bits set
    if math.gcd(e, lambda_n) != 1:
        raise ValueError("e shares a factor with lambda(n); regenerate primes")
    d = eucalg(e, lambda_n)[0]
    if d < 0:
        d += lambda_n
    return {'priv': (d, n), 'pub': (e, n)}

Raising is the minimum. Regenerating is what production does.

Encrypting Real Data, and the Bug That Eats It

Everything is computed modulo n, so a message must be smaller than n. Real data isn't, which means splitting it into blocks.

The reasoning everyone reaches, including earlier versions of this article: n is 2048 bits, a byte is 8 bits, so blocks are 2048 ÷ 8 = 256 bytes. It gets stated as a fact — the 256-byte limit is a fundamental property of 2048-bit RSA, not an implementation choice.

It is an implementation choice, and it is wrong.

A 256-byte block is a 2048-bit number. A 2048-bit modulus is also a 2048-bit number. Whether m < n holds then depends on the value, not the length:

largest 256-byte m : 2048 bits
smallest 2048-bit n: 2048 bits
256-byte block can exceed n? True
255-byte block can exceed n? False

Here is that running against a freshly generated 2048-bit key, using the article's own encrypt_with_length and decrypt_with_length:

  the article's own test message (67 bytes):
    round-trip OK: True   <- the article tests THIS and it passes
 
  a 256-byte block of high-valued bytes:
    round-trip OK: False
    m is 2048 bits, n is 2048 bits, m>=n: True
    recovered == m mod n: True

Read those two results together. The implementation's own test — a 67-byte ASCII string — passes. Feed it 256 bytes of 0xFF and the data is gone. No exception, no warning: modpow reduces modulo n on the way in, so what comes back is m mod n, decrypted flawlessly into the wrong bytes.

That is the worst class of cryptographic bug. Correct-looking code, no error path, corruption only on high-valued blocks. ASCII text mostly survives because leading bytes stay small. A compressed archive, an image, an encrypted payload — anything with high-entropy bytes — does not.

The fix is one byte:

255-byte block: m >= n ? False
round-trip ok?  True

Cap plaintext blocks at 255 bytes for a 2048-bit key. In general, (key_bits // 8) - 1. PKCS#1 v1.5 reserves 11 bytes and OAEP reserves more, and that overhead exists partly for exactly this reason — the padding has to guarantee m < n.

BLOCK = 255   # (2048 // 8) - 1, guarantees m < n
 
def encrypt_bytes(data, key):
    data = bytearray(data)
    cdata = bytearray()
    for i in range(0, len(data), BLOCK):
        m = 0
        for j in range(BLOCK):
            if i + j < len(data):
                m = (m << 8) + data[i + j]
            else:
                m <<= 8
        c = modpow(m, key[0], key[1])
        for j in range(255, -1, -1):        # ciphertext is still 256 bytes
            cdata.append((c >> (j * 8)) & 0xFF)
    return bytes(cdata)

Note the asymmetry: you read 255 bytes of plaintext and write 256 bytes of ciphertext, because c can be anything up to n - 1. Encryption expands.

Which makes this line, common in tutorials and previously in this one, wrong:

decrypt_bytes = encrypt_bytes   # only true when block sizes match

The mathematical operation genuinely is symmetric — Part 1 showed numencrypt and numdecrypt are the same function. But once encryption changes the block size, the framing isn't symmetric any more. Decryption has to read 256-byte blocks and emit 255, which means it needs its own implementation:

def decrypt_bytes(cdata, key):
    cdata = bytearray(cdata)
    data = bytearray()
    for i in range(0, len(cdata), 256):      # read 256-byte ciphertext blocks
        c = 0
        for j in range(256):
            c = (c << 8) + cdata[i + j]
        m = modpow(c, key[0], key[1])
        for j in range(BLOCK - 1, -1, -1):   # emit 255-byte plaintext blocks
            data.append((m >> (j * 8)) & 0xFF)
    return bytes(data)

With both halves in place, the full pipeline handles everything Part 1 couldn't:

  n=2048 bits, e=65537, BLOCK=255
  short ascii                15B ->   260B ct -> round-trip True
  exactly 255 bytes         255B ->   260B ct -> round-trip True
  600 bytes high-entropy    600B ->   772B ct -> round-trip True
  1 byte                      1B ->   260B ct -> round-trip True

Including the case that broke the 256-byte version: 255 bytes of 0xFF, and 600 bytes of cryptographically random data where every block is high-valued.

The Padding Problem This Doesn't Solve

Short blocks get zero-padded, so you cannot distinguish a message ending in 0x00 from padding. Prepending the plaintext length fixes that:

import struct
 
def encrypt_with_length(data, key):
    return struct.pack('>I', len(data)) + encrypt_bytes(data, key)
 
def decrypt_with_length(cdata, key):
    original_length = struct.unpack('>I', cdata[:4])[0]
    return decrypt_bytes(cdata[4:], key)[:original_length]

That solves the ambiguity. It introduces two things worth knowing about, neither of which is mentioned when this pattern gets recommended.

The header is a 32-bit unsigned integer, which caps the message at 4 GB and fails loudly past it:

>I is unsigned 32-bit: max length = 4,294,967,295 bytes (4.00 GB)
len(data) = 4 GB  -> error: 'I' format requires 0 <= number <= 4294967295

Fine for most uses, and something to know before you stream a disk image through it.

The header is not encrypted. It sits in front of the ciphertext in the clear:

message is 60 bytes -> header bytes 0000003c -> reads back as 60

Anyone who sees the ciphertext reads the exact plaintext length without a key. Block-based encryption already leaks length approximately, rounded up to the block size — this leaks it exactly. Whether that matters depends on what you're sending, and "it's just the length" has broken real protocols before.

And decrypt_with_length trusts that header completely. Throwing malformed input at it:

  valid                  -> returned 11 bytes: b'hello world'
  header claims 4GB      -> returned 256 bytes: b'hello world\x00\x00\x00...'
  truncated to 10 bytes  -> returned 11 bytes: b'\x00\xae\xaai,\x12\xd0\xcb\x8a\x8b\xbc'
  empty                  -> error
  header only            -> returned 0 bytes: b''

Three of five malformed inputs return data rather than raising. A truncated ciphertext yields eleven bytes of garbage that the caller has no way to distinguish from plaintext. A forged header changes how much you get back.

Compare that to an authenticated scheme, where every one of those rows is a thrown exception. This is what "no integrity protection" means concretely — not that an attacker can decrypt your data, but that your code cannot tell valid ciphertext from noise.

That solves correctness. It does not solve security, and the gap is larger than it looks.

Raw RSA is deterministic. Part 1 demonstrated this on single integers; at block level it means an attacker learns which 255-byte chunks of your file are identical. In a structured format — a header, a repeated record, a run of padding — that is often enough to reconstruct the shape of the data.

Raw RSA is also malleable, which is the sharper problem and easy to demonstrate. An attacker who never sees the private key can modify the plaintext:

  original m      = 1000
  ciphertext c    = 656884064
  attacker computes (2^e * c) mod n without the key
  victim decrypts -> 2000
  attacker doubled the plaintext: True
 
    multiply by   3: decrypts to   3000
    multiply by   7: decrypts to   7000
    multiply by 100: decrypts to 100000

Multiply the ciphertext by f^e mod n and the victim decrypts f × m. Exactly, every time, for any f. If that plaintext is a transaction amount, a permission level or a counter, an attacker with no key at all just edited it.

OAEP breaks both properties — randomness makes encryption non-deterministic, and the integrity structure makes malleation detectable. It is not optional and not something to implement yourself.

The production pattern, and what TLS actually does: use RSA to encrypt a random AES key, use AES-GCM for the message. RSA handles key exchange. AES handles bulk data. Raw RSA for messages is a teaching tool, not a use case.

What Part 2 Adds, and What Remains

The implementation now generates cryptographically sized keys from a secure random source and encrypts arbitrary bytes. That's the gap between "demonstrates the algorithm" and "runs end to end."

It is still not safe. modpow branches on the bits of the private exponent, so its running time leaks key material — Part 3 covers timing attacks, blinding, and constant-time exponentiation.

Three things worth carrying out of this part regardless.

Names matter for finding the literature. Baillie–PSW, and Selfridge's conjecture.

Test with adversarial data, not with "hello". The block-size bug survived because every test used short ASCII strings. One block of 0xFF would have caught it immediately.

Cryptographic bugs fail silently by default. No exception, no warning, no error return — just different bytes coming out than went in, on a subset of inputs you didn't think to try.