RSA in Python Part 2: Prime Generation and Encryption
Extend your Python RSA build with 1024-bit secure random prime generation and full plaintext encryption and decryption, with working, testable code.
Part 1 built a working RSA implementation. You can generate keys, encrypt an integer, and decrypt it back. The math is correct. The implementation is complete for what it does.
What it does is very limited.
The prime numbers we used -- p = 31337 and q = 31357 -- are 15 bits each. The modulus n = 982634309 is 30 bits. Factor a 30-bit number: Python can brute-force it by trial division in under a millisecond. The encryption we built is not just weak. It's theater. Anyone who intercepts a ciphertext can recover the message faster than you could type it.
import math
n = 982634309
for p in range(2, int(math.sqrt(n)) + 1):
if n % p == 0:
print(f"Factored: {p} * {n // p}")
break
# Factored: 31337 * 31357 -- done in microseconds
Two problems make Part 1 unfit for real use: toy primes and integer-only encryption. This article fixes both. We'll build a prime generator that produces cryptographically suitable candidates, add the Fibonacci-based primality test needed to validate them efficiently, and implement byte-level block encryption so this system can handle actual messages.
This is still educational. Part 3 covers the remaining gap – the timing attacks and side-channel vulnerabilities that make even a well-implemented RSA dangerous without countermeasures.
We recommend reading Implementing RSA, AES-GCM, and TLS from Scratch in Python to continue reading our selection of content. The 1024-bit primes you just generated are exactly what feeds a real TLS handshake, and that piece shows the full protocol this building block plugs into.
Traven
How Do You Generate Cryptographically Secure Random Primes for RSA?
Generating large primes sounds hard. The good news: there are infinitely many primes, they're distributed relatively densely among large numbers, and testing a candidate is much faster than finding one by enumeration. The standard approach is:
- Generate a large random odd number
- Test whether it's prime
- If not prime, try another candidate
- Repeat until you find one
The key questions are: how large, how random, and what primality test.
How large. For 2048-bit RSA, you need two primes p and q each approximately 1024 bits. Their product gives a 2048-bit modulus n. The exact bit length of each prime can vary slightly, but targeting 1024 bits is the standard. Smaller primes make factoring easier. NIST formally deprecated 1024-bit RSA keys in 2013.
How random. Python's random module produces statistically random numbers from a deterministic PRNG seeded by the system time. An attacker who knows your seed -- or who can narrow it down -- can reproduce your "random" primes. The secrets module uses the operating system's cryptographically secure random number generator: /dev/urandom on Linux and macOS, BCryptGenRandom on Windows. These are non-deterministic, non-reproducible, and appropriate for key material.
import secrets
import 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)
What primality test. You cannot test 1024-bit numbers for primality by trial division -- the candidate would need to be tested against all primes up to its square root, and there are roughly 2^511 such primes to check. Two efficient probabilistic approaches exist:
The Miller-Rabin test is the modern standard. It's a probabilistic algorithm that, given a candidate n and a random witness a, either proves n is composite or says n is "probably prime." Run it with k independent witnesses, and the probability of a composite number passing all tests is at most 4^(-k). With 20 witnesses, that's less than 10^(-12) -- a false positive is less likely than a cosmic ray flipping a bit in your RAM.
The Lucas test (used here) is based on properties of Fibonacci numbers modulo the candidate. Combined with a Fermat test, it forms the basis of the Baillie-PSW test, which has no known counterexamples -- no composite number has ever been found that passes it. For prime generation in practice, this combination is considered reliable.
The test we use is a specific heuristic combining a Fermat condition and a Lucas-Fibonacci condition. It's less general than Baillie-PSW but fast to implement from scratch.
How Does the Fibonacci Matrix Method Speed Up Primality Testing?
The Lucas condition requires computing the (p+1)-th Fibonacci number modulo p. Computing Fibonacci numbers naively -- stepping one by one from F(1) to F(p+1) -- is not feasible when p is a 1024-bit number.
Matrix exponentiation makes this fast. The Fibonacci recurrence F(n) = F(n-1) + F(n-2) can be expressed as matrix multiplication:
[ F(n+1) ] [ 0 1 ]^n [ 1 ]
[ F(n) ] = [ 1 1 ] * [ 1 ]
The matrix raised to the n-th power gives you F(n+1) and F(n) directly. Crucially, matrix multiplication is associative, so you can apply the same binary exponentiation trick we used for modpow. Computing M^n takes O(log n) matrix multiplications instead of n additions.
Each matrix multiplication involves four multiplications and two additions of numbers less than the modulus. With modular reduction at each step, the intermediate values stay bounded.
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):
"""
Compute the x-th Fibonacci number modulo mod.
Uses matrix exponentiation for O(log x) performance.
F(1) = F(2) = 1.
"""
if x < 3:
return 1
x -= 2 # Adjust index so we start from [1, 1]
# Find highest bit of x
tst = 1
siz = 0
while x >= tst:
tst <<= 1
siz += 1
siz -= 1
# Function matrix: one step of Fibonacci recurrence
fm = [[0, 1],
[1, 1]]
# Result matrix: identity (matrix^0 = identity)
rm = [[1, 0],
[0, 1]]
# Binary exponentiation on matrices
for i in range(siz, -1, -1):
rm = sqmatrixmul(rm, rm, 2, mod)
if (x >> i) & 1:
rm = sqmatrixmul(rm, fm, 2, mod)
# Second row of result vector is the Fibonacci number
return (rm[1][0] + rm[1][1]) % mod
Verify this computes Fibonacci numbers correctly before trusting it with primality testing:
fib_sequence = [1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
for i, expected in enumerate(fib_sequence, start=1):
result = fib(i, 10**18) # Large modulus so no reduction occurs
assert result == expected, f"F({i}): expected {expected}, got {result}"
print("Fibonacci correctness: OK")
How Do You Generate a 1024-Bit Prime in Python?
The primality test combines two conditions. Given a candidate p:
2^(p-1) ≡ 1 (mod p)-- the Fermat primality condition. All primes satisfy this by Fermat's Little Theorem. Most composites don't.F(p+1) ≡ 0 (mod p)-- the Lucas-Fibonacci condition. This catches Fermat pseudoprimes (composites that pass condition 1).
Candidates are restricted to numbers that are3 (mod 10)or7 (mod 10). This is equivalent to saying the number is odd and±2 (mod 5). Both are necessary conditions for primality for numbers greater than 5 -- any even number is composite, and any multiple of 5 is composite. Filtering to these residue classes eliminates half the candidates before running the expensive tests.
import secrets
def genprime(siz):
"""
Generate a random prime of approximately siz bits.
Uses the Selfridge/Lucas heuristic test:
- Fermat primality condition
- Fibonacci Lucas condition
Candidates restricted to 3 or 7 (mod 10).
"""
while True:
# Generate a random siz-bit number
# Set the high bit to ensure it's actually siz bits long
num = (1 << (siz - 1)) + secrets.randbits(siz - 1) - 10
# Adjust to 3 (mod 10)
num -= num % 10
num += 3
# Test the 3 (mod 10) candidate
if modpow(2, num - 1, num) == 1 and fib(num + 1, num) == 0:
return num
# Adjust to 7 (mod 10) and test
num += 4
if modpow(2, num - 1, num) == 1 and fib(num + 1, num) == 0:
return num
A few things worth understanding in this code.
The (1 << (siz - 1)) sets the most significant bit, ensuring the number is at least siz bits long. Without this, secrets.randbits(siz - 1) could produce a number far smaller than intended -- a 200-bit number instead of a 1024-bit one -- and the key would be weak.
The - 10 gives the adjustment arithmetic room to increase num without overflowing the intended bit length.
The search checks two candidates per iteration (the 3 mod 10 and 7 mod 10 variants) rather than one. This doubles throughput. The Prime Number Theorem tells us that primes near N have density approximately 1 / ln(N). For 1024-bit numbers, ln(2^1024) ≈ 710. So roughly 1 in 710 odd numbers in this range is prime, meaning you expect to test around 355 candidates per prime found. With the residue filtering, you reject more non-candidates before running the expensive Fermat and Lucas tests.
Generating a 1024-bit prime takes a few seconds on a modern CPU. For key generation, that's acceptable. You generate keys infrequently -- once per session, once per certificate -- so the cost doesn't matter in practice.
Generate two primes and create a key pair:
print("Generating primes (this takes a few seconds)...")
p = genprime(1024)
q = genprime(1024)
print(f"p is {p.bit_length()} bits")
print(f"q is {q.bit_length()} bits")
keys = keysgen(p, q)
print(f"n is {keys['pub'][1].bit_length()} bits")
For a sanity check: a 1024-bit prime looks like a 309-digit decimal number. The modulus n is approximately 2048 bits, around 617 digits. Nothing about these numbers is special or guessable -- they're drawn from a uniform distribution over a range containing roughly 2^1013 primes.
How Do You Encrypt and Decrypt Text (Not Just Integers) with RSA in Python?
Part 1's numencrypt takes an integer m and requires m < n. For a 2048-bit key, n is a 2048-bit number -- 256 bytes. You can encrypt any message that fits in 256 bytes as a single integer.
Most messages are longer than 256 bytes. The solution: slice the plaintext into 256-byte blocks, encrypt each block independently, and concatenate the ciphertexts.
There's a subtlety in the byte-to-integer conversion. A 256-byte block contains 256 * 8 = 2048 bits of data. To represent this block as a single integer, interpret the bytes as a big-endian base-256 number: the first byte occupies the most significant 8 bits, the last byte occupies the least significant 8 bits.
def bytes_to_int(block):
"""Convert a byte sequence to a big-endian integer."""
result = 0
for byte in block:
result = (result << 8) + byte
return result
def int_to_bytes(n, length):
"""Convert an integer back to a fixed-length byte sequence."""
result = bytearray(length)
for i in range(length - 1, -1, -1):
result[i] = n & 0xFF
n >>= 8
return bytes(result)
Verify the round-trip:
original = b"Hello, RSA!"
padded = original.ljust(32, b'\x00') # Pad to 32 bytes
as_int = bytes_to_int(padded)
back = int_to_bytes(as_int, 32)
assert back == padded
print("Byte/integer round-trip: OK")
The full block encryption function:
def encrypt_bytes(data, key):
"""
Encrypt arbitrary bytes with RSA key.
Data is split into 256-byte blocks.
Each block is encrypted independently.
Last block is zero-padded if needed.
Returns ciphertext as bytes.
"""
data = bytearray(data)
cdata = bytearray()
for i in range(0, len(data), 256):
# Build a 256-byte block
m = 0
for j in range(256):
if i + j < len(data):
m = (m << 8) + data[i + j]
else:
m <<= 8 # Zero-pad the last block
# Encrypt the block as an integer
c = modpow(m, key[0], key[1])
# Serialize ciphertext block as exactly 256 bytes
for j in range(255, -1, -1):
cdata.append((c >> (j * 8)) & 0xFF)
return bytes(cdata)
# Decryption is mathematically identical -- just pass the other key
decrypt_bytes = encrypt_bytes
The variable decrypt_bytes = encrypt_bytes is not laziness. RSA encryption and decryption are the same operation: raise the input to a power modulo n. The only difference is which exponent you use. Encrypt with e, decrypt with d. The underlying math is symmetric. This assignment makes that explicit.
What About the Zero-Padding Problem?
Block encryption with zero-padding introduces an ambiguity: the receiver can't tell whether trailing zeros in the last block were part of the original message or added as padding.
For ASCII text, this rarely matters -- a null byte at the end of a string is usually harmless. For binary data -- images, executables, compressed archives -- trailing zeros change the file. A 100-byte file padded to 256 bytes that decrypts back to 256 bytes will be broken.
Two fixes:
Option 1: Store the plaintext length alongside the ciphertext. Include the original byte count as a header in the ciphertext. The receiver reads it, decrypts the blocks, and trims to the correct length.
import struct
def encrypt_with_length(data, key):
"""Prepend the plaintext length as a 4-byte header."""
length_header = struct.pack('>I', len(data)) # Big-endian 32-bit int
return length_header + encrypt_bytes(data, key)
def decrypt_with_length(cdata, key):
"""Read the length header and trim the decrypted output."""
original_length = struct.unpack('>I', cdata[:4])[0]
decrypted = decrypt_bytes(cdata[4:], key)
return decrypted[:original_length]
Option 2: Use a padding scheme with an unambiguous terminator. PKCS#1 v1.5 padding adds a specific byte sequence before the message that marks its beginning, making length implicit. OAEP adds randomness in addition to length marking. Both solve the ambiguity problem properly. This is why production RSA always uses a padding scheme -- not just for semantic security, but for basic correctness with arbitrary binary data.
End-to-End Example
# Generate keys (in practice, do this once and store securely)
print("Generating 1024-bit primes...")
p = genprime(1024)
q = genprime(1024)
keys = keysgen(p, q)
pub = keys['pub']
priv = keys['priv']
# Encrypt a text message
message = b"This is a test message for RSA encryption. It can be any length."
print(f"Original ({len(message)} bytes): {message}")
ciphertext = encrypt_bytes(message, pub)
print(f"Ciphertext ({len(ciphertext)} bytes): {ciphertext[:32].hex()}...")
plaintext = decrypt_bytes(ciphertext, priv)
# Trim zero padding from last block
plaintext = plaintext[:len(message)]
print(f"Decrypted: {plaintext}")
assert plaintext == message, "Round-trip failed"
print("Round-trip: OK")
Important: Why Raw RSA Is Still Wrong for This Use Case
Even with chunked byte encryption, raw RSA (no padding) is semantically insecure. The same 256-byte plaintext block always produces the same 256-byte ciphertext block. An attacker observing two encrypted messages containing the same block learns they match, without knowing the content. For structured data -- headers, file formats, protocol messages -- this leaks significant information.
More concretely: RSA without padding is malleable. Given ciphertext c = m^e mod n, an attacker can compute (2^e * c) mod n, which decrypts to 2m. An attacker can transform ciphertexts arithmetically without knowing the key. This enables attacks on protocols that use raw RSA for anything beyond generating an AES session key.
The production pattern: use RSA to encrypt a random 256-bit AES key. Use AES-GCM for the actual message. RSA handles key exchange. AES handles bulk encryption. This is what TLS does.
Raw RSA encryption for messages is not a real use case. It's a teaching tool. The real use case is asymmetric key exchange.
What Are the Remaining Security Gaps?
After Part 2, this implementation handles real messages with real key sizes. Two major gaps remain.
Weak primality testing. The Fermat-plus-Lucas test we use has no known counterexamples -- no composite has ever been documented that passes both conditions simultaneously. But "no known counterexamples" is not a proof. The Miller-Rabin test with 20+ witnesses provides a formal probability bound: at most 4^(-20) probability of a false positive per test. Production key generation uses Miller-Rabin or the provably correct AKS test.
No timing-attack protection. The modpow function processes bits of the private key d differently depending on their values. A 1 bit causes a square-and-multiply; a 0 bit causes only a square. These two code paths take different amounts of time. An attacker with access to decryption timing measurements across thousands of requests can recover d bit by bit using statistical analysis.
Paul Kocher demonstrated this attack against real SSL implementations in 1996. Daniel Bleichenbacher demonstrated a related attack against PKCS#1 v1.5 RSA implementations in 1998. These are not theoretical attacks -- they've broken production systems. Part 3 covers constant-time implementations and RSA blinding in full.
We recommend reading RSA Is Simple. Deploying RSA Correctly Almost Never Is. to continue reading our selection of content. You've now built the encryption half correctly. That piece covers the exact production failures, padding oracles included, that still trip up teams who stop exactly where this article does.
Traven
The Complete Part 2 Implementation
Here is the full rsa2.py building on Part 1:
"""
RSA from Scratch -- Part 2
Adds: cryptographically secure prime generation,
Fibonacci-based Lucas primality test,
byte-level block encryption and decryption.
For educational use. Do not use in production.
"""
import secrets
import struct
# -- Part 1 functions (included for completeness) --
def eucalg(a, b):
swapped = False
if a < b:
a, b = b, a
swapped = True
ca = (1, 0)
cb = (0, 1)
while b != 0:
k = a // b
a, b, ca, cb = b, a - b * k, cb, (ca[0] - k * cb[0], ca[1] - k * cb[1])
if swapped:
return (ca[1], ca[0])
return ca
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
if (e >> i) & 1:
r = (r * b) % n
return r
def keysgen(p, q):
n = p * q
lambda_n = (p - 1) * (q - 1)
e = 35537
d = eucalg(e, lambda_n)[0]
if d < 0:
d += lambda_n
return {'priv': (d, n), 'pub': (e, n)}
# -- Part 2: prime generation --
def sqmatrixmul(m1, m2, w, 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):
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]]
rm = [[1, 0], [0, 1]]
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
def genprime(siz):
while True:
num = (1 << (siz - 1)) + secrets.randbits(siz - 1) - 10
num -= num % 10
num += 3
if modpow(2, num - 1, num) == 1 and fib(num + 1, num) == 0:
return num
num += 4
if modpow(2, num - 1, num) == 1 and fib(num + 1, num) == 0:
return num
# -- Part 2: byte-level encryption --
def encrypt_bytes(data, key):
data = bytearray(data)
cdata = bytearray()
for i in range(0, len(data), 256):
m = 0
for j in range(256):
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):
cdata.append((c >> (j * 8)) & 0xFF)
return bytes(cdata)
decrypt_bytes = encrypt_bytes
def encrypt_with_length(data, key):
header = struct.pack('>I', len(data))
return header + encrypt_bytes(data, key)
def decrypt_with_length(cdata, key):
original_length = struct.unpack('>I', cdata[:4])[0]
decrypted = decrypt_bytes(cdata[4:], key)
return decrypted[:original_length]
if __name__ == '__main__':
print("Generating 1024-bit primes...")
p = genprime(1024)
q = genprime(1024)
print(f"p: {p.bit_length()} bits")
print(f"q: {q.bit_length()} bits")
keys = keysgen(p, q)
pub, priv = keys['pub'], keys['priv']
print(f"n: {pub[1].bit_length()} bits")
message = b"RSA from scratch, Part 2: now with real primes and text encryption."
ct = encrypt_with_length(message, pub)
pt = decrypt_with_length(ct, priv)
assert pt == message, "Round-trip failed"
print(f"Message: {message}")
print(f"Decrypted: {pt}")
print("Round-trip: OK")
Frequently Asked Questions
Why use secrets instead of random for prime generation?
Python's random module generates statistically uniform numbers using a Mersenne Twister PRNG. Given the seed, its output is deterministic and reproducible. The secrets module uses the OS-level CSPRNG (/dev/urandom on Linux/macOS, BCryptGenRandom on Windows), which pulls from hardware entropy sources. For anything that will become a cryptographic key, use secrets.
What is the PWS (Selfridge-Lucas) primality test?
A heuristic combining two conditions: the Fermat condition 2^(p-1) ≡ 1 (mod p) and the Lucas condition F(p+1) ≡ 0 (mod p). Numbers satisfying both are prime with overwhelming probability. No composite is known to pass both simultaneously. The Baillie-PSW test formalizes this combination with additional rigor.
Why split plaintext into 256-byte blocks?
RSA can only encrypt integers smaller than the modulus n. A 2048-bit modulus means n is at most 256 bytes. Larger plaintexts require splitting into chunks, encrypting each independently, and reassembling. The 256-byte limit is a fundamental property of 2048-bit RSA, not an implementation choice.
Is this implementation safe for production use?
No. Use pycryptodome or the Python cryptography library. This implementation lacks timing-attack protection, uses a non-standard primality test, has no message padding (OAEP), and hasn't been audited.
Part 3 covers the attacks this implementation remains vulnerable to: timing-based key recovery, blinding countermeasures, and what constant-time cryptography actually means in Python.
