Textbook RSA: Key Generation, Encryption/Decryption, and Why Real Systems Don't Use It That Way
Key Generation, Encryption, and Decryption
RSA is one of the first widely-deployed public-key cryptosystems. Its security rests on a single computational assumption: factoring a large composite number n = p × q into its prime factors is hard. This asymmetry — easy to compute forward (multiply two primes), hard to reverse (factor the product) — is what makes “public key cryptography” possible at all.
The public key can be shared openly. The private key must stay secret. What does that actually mean in practice? We’ll walk through key generation, encryption and decryption by hand, then see where textbook RSA breaks down and how real systems work around it.
Key Generation
At the heart of RSA is a trapdoor function: easy to evaluate with one piece of information (the public exponent e), hard to invert without another piece (the private exponent d).
The key pair starts with two random primes p and q. Their product n is the modulus shared by both keys. Euler’s totient φ(n) = (p-1)(q-1) is kept secret — revealing it lets you compute d from e instantly.
Given p and q, we choose e = 65537 (a Fermat prime with only two bits set, which makes encryption fast). The private exponent d satisfies e × d ≡ 1 (mod φ(n)), found via the extended Euclidean algorithm.
The code above generates a ~512-bit key pair from scratch — no libraries, just arithmetic:
- p and q each have 256 digits (~256 bits)
- n = p × q has 154 decimal digits (511 bits total)
- e is fixed at 65537
With these keys, a message becomes an integer m < n, encryption computes c = m^e mod n, and decryption recovers m = c^d mod n.
The output above shows it in action: message 42 encrypts to a large integer (which looks like random noise), and decrypting that ciphertext returns exactly 42. This works because of Euler’s theorem — the reason RSA was invented in the first place.
Why “Textbook” RSA Is Not Safe
The name “textbook RSA” signals something important: it’s mathematically correct but practically broken. Two fatal flaws show up immediately once you try to use it.
Determinism. Encrypt the same message twice and get the same ciphertext every time. An attacker observing encrypted traffic can spot repeated keys or messages by comparing ciphertexts — no decryption needed.
The output above confirms this: encrypting 42 twice produces identical ciphertexts. In a protocol where session IDs, handshakes, or passwords follow predictable patterns, this is a data leak.
Malleability. An attacker who intercepts a ciphertext can modify it to decrypt to a related value, without knowing any key. Multiplying the ciphertext by 2^e mod n produces a new valid ciphertext that decrypts to twice the original message.
The second demo above takes c = encrypt(100), multiplies it by 2^e mod n, and the result decrypts to exactly 200. This is how a “padding oracle” attack works in real protocols: an attacker crafts malicious ciphertexts and watches whether the server accepts or rejects them.
OAEP fixes both problems. It introduces random padding before encryption, turning deterministic RSA into probabilistic encryption — every encryption of the same message produces a different ciphertext. OAEP also embeds hash checks that tie the ciphertext to a specific structure; any tampering is caught during decryption.
The third section above demonstrates this with PyCryptodome’s PKCS1_OAEP: encrypting “Hello, RSA!” twice yields completely different ciphertexts (different hex starts), both decrypt correctly, and flipping a single bit in the ciphertext is rejected outright. The randomization is the critical difference between a mathematical curiosity and a usable protocol.
RSA’s Practical Limits
RSA has real-world costs that don’t show up in textbook examples.
Key generation scales badly. A 512-bit key took about 36ms to generate (finding two ~256-bit primes). A 1024-bit key took 617ms. Production keys at 2048 or 3072 bits would take minutes with this naive approach — real implementations use far more sophisticated prime-finding and Miller-Rabin rounds.
Operation speed depends on key size. With a tiny 128-bit key, encryption was 0.0019 ms and decryption 0.0194 ms (a 10× difference because the private exponent d is roughly as large as n itself). The public exponent e = 65537 is chosen specifically to be a small number with few bits set, making encryption fast for anyone who needs to do it.
Symmetric ciphers dwarf RSA in throughput. AES-256-GCM encrypted 128 bytes in 0.023ms and 4096 bytes in just 0.044ms — linear scaling with near-zero overhead per byte. RSA’s bottleneck isn’t the modular exponentiation alone; it’s that each operation requires O(key_bits^2) or worse arithmetic on large integers.
The performance table shows equivalent security levels across algorithm families (from NIST SP 800-57). A 128-bit symmetric key (AES-128) is roughly equivalent to a 3072-bit RSA key — meaning RSA’s key is about 24× larger. That matters for storage, transmission, and computation on constrained devices.
The quantum threat. Shor’s algorithm factors integers in polynomial time O((log n)^3). Once fault-tolerant quantum computers are available, the factoring assumption collapses entirely. NIST standardized post-quantum alternatives (CRYSTALS-Kyber for key agreement, CRYSTALS-Dilithium for signatures) in 2024. RSA’s deprecation is a matter of when, not whether — and systems with long-lived data need to plan around that timeline now.
Hybrid Encryption: How Real Systems Do It
The natural conclusion from all the above: use RSA for one thing (key agreement or transport) and symmetric encryption for everything else.
This is exactly what TLS, PGP, S/MIME, and most public-key protocols do. The pattern is:
- Generate a random AES session key (32 bytes for AES-256)
- Encrypt that session key with RSA-OAEP (~256 bytes for a 2048-bit key)
- Encrypt the actual data with AES-GCM using the session key
The fourth demo above shows this in action. A 2250-byte message gets encrypted by wrapping a random 32-byte AES key with RSA-OAEP, then encrypting the full message payload with AES-256-GCM. The total overhead is one RSA operation (256 bytes for the key) plus the symmetric ciphertext — no chunking, no repeated exponentiation.
Try doing it with RSA alone: a 2048-bit key with OAEP can encrypt at most 245 bytes per block. That same 2250-byte message requires 10 separate RSA operations, each with its own random padding and full modular exponentiation. Multiply that by the latency of a public-key operation vs. symmetric — the performance gap is dramatic.
Takeaway
RSA’s trapdoor function (modular exponentiation where encryption is easy but factoring the key to invert it is hard) makes public-key cryptography possible in principle; real systems only use RSA for the thin layer of key transport, pairing it with fast symmetric ciphers for everything that matters.