RSA in Python Part 2: Random Prime Generation and Text Encryption

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.