The RSA Cryptosystem
Imagine you want to send your credit card number to an online store. You have never met the store before. You share no secret with it. How can two strangers agree on private information over a public channel? Any eavesdropper can read that channel. For most of the history of cryptography this seemed impossible. Every cipher required a shared secret key exchanged in advance. In 1977 Ron Rivest, Adi Shamir, and Leonard Adleman found a way around this. They used number theory, giving the world its first practical Public-Key Cryptography system. The RSA cryptosystem lets anyone encrypt a message using a freely published public key. Only the holder of a matching private key can decrypt it. The trick rests on a single asymmetry. Multiplying two large primes is fast. But factoring their product back into those primes is believed to be extremely slow. RSA turns this asymmetry into an encryption scheme. It builds the encryption and decryption operations directly out of modular exponentiation. This uses Modular Arithmetic and Primes for Cryptography as its computational substrate. This article walks through exactly how RSA keys are generated. It shows how encryption and decryption work as inverse operations. It explains why Euler's theorem guarantees that decryption always recovers the original message. We derive the complexity of every step. We trace a complete numerical example by hand. We catalog the pitfalls that turn a textbook-correct implementation into a broken or insecure one. By the end you should be able to generate an RSA key pair. You should be able to encrypt and decrypt by hand on small numbers. You should be able to explain precisely why the math works. This sets up later discussions of RSA Security and Factoring and how RSA underlies Digital Signatures.
- RSA is a public-key cryptosystem: encryption uses a public key, decryption uses a separate private key.
- Keys come from two large random primes `p, q`; security rests on the difficulty of factoring `n = p·q`.
- Encryption is `c = mᵉ mod n`; decryption is `m = c^d mod n`, where `e·d ≡ 1 (mod φ(n))`.
- Correctness follows from Euler's theorem: `m^φ(n) ≡ 1 (mod n)` when `gcd(m, n) = 1`, extended via CRT to all `m`.
- Key generation, encryption, and decryption all run in polynomial time via fast modular exponentiation.
- Textbook (unpadded) RSA is deterministic and malleable; real systems require randomized padding schemes.
RSA encrypts with one exponent and decrypts with its multiplicative inverse modulo `φ(n)`, and Euler's theorem guarantees this round trip always returns the original message.
The idea
RSA is built from three algorithms: key generation, encryption, and decryption. Key generation produces a public key `(n, e)`, which anyone may know, and a private key `d`, known only to the recipient. The modulus `n` is the product of two large distinct primes `p` and `q`, chosen and then discarded (only their product and the derived exponents survive). The security of the whole scheme reduces informally to the claim that recovering `p` and `q` from `n` alone — integer factorization — is computationally infeasible for suitably large primes. The core mathematical object is Euler's totient function `φ(n)`, which counts the integers in `{1, ..., n}` that are coprime to `n`. For `n = p·q` with distinct primes, ``` φ(n) = (p - 1)(q - 1) ``` The public exponent `e` is chosen coprime to `φ(n)`, and the private exponent `d` is its modular inverse: `e·d ≡ 1 (mod φ(n))`. Encryption raises the message to the power `e` modulo `n`; decryption raises the ciphertext to the power `d` modulo `n`. That these two operations undo each other is not a coincidence — it is a direct consequence of Euler's theorem, which states that for any integer `m` coprime to `n`, ``` m^φ(n) ≡ 1 (mod n) ``` This single congruence is the mathematical engine that makes public-key encryption from modular exponentiation possible. It is worth being precise about terminology. "RSA" as described here is often called textbook RSA: a direct algebraic scheme without padding. It is deterministic, homomorphic under multiplication, and vulnerable to several structural attacks. Every deployed system layers a randomized padding scheme (such as OAEP) on top of the algebraic core described in this article; that core, however, is exactly what we analyze.
How it works
Key generation. The recipient (say, Bob) performs the following steps once, offline, to produce a key pair. ``` function RSA_KeyGen(bit_length): // 1. Choose two large random primes of roughly bit_length/2 bits each p ← random_prime(bit_length / 2) q ← random_prime(bit_length / 2) while p == q: q ← random_prime(bit_length / 2) n ← p q phi ← (p - 1) (q - 1) // 2. Choose public exponent e coprime to phi e ← 65537 // common fixed choice assert gcd(e, phi) == 1 // re-pick primes if this fails // 3. Compute private exponent d = e^{-1} mod phi d ← modular_inverse(e, phi) // via Extended Euclidean Algorithm public_key ← (n, e) private_key ← (n, d) // p, q, phi are then discarded (or kept securely) return (public_key, private_key) ```
Encryption. Anyone holding the public key `(n, e)` can encrypt a message `m` (represented as an integer with `0 ≤ m < n`): ``` function RSA_Encrypt(m, n, e): return ModExp(m, e, n) // c = m^e mod n ```
Decryption. Only the holder of `d` can decrypt: ``` function RSA_Decrypt(c, n, d): return ModExp(c, d, n) // m = c^d mod n ``` Both operations depend on fast modular exponentiation (square-and-multiply), which computes `x^k mod n` without ever forming the astronomically large integer `x^k`: ``` function ModExp(base, exponent, modulus): result ← 1 base ← base mod modulus while exponent > 0: if exponent is odd: result ← (result base) mod modulus exponent ← exponent >> 1 base ← (base base) mod modulus return result ```
Extended Euclidean Algorithm (used to compute `d`), which simultaneously computes `gcd(a, b)` and coefficients `x, y` such that `a·x + b·y = gcd(a, b)`: ``` function ExtGCD(a, b): if b == 0: return (a, 1, 0) (g, x1, y1) ← ExtGCD(b, a mod b) x ← y1 y ← x1 - (a / b) * y1 return (g, x, y) function ModularInverse(e, phi): (g, x, _) ← ExtGCD(e, phi) assert g == 1 // inverse exists iff gcd(e, phi) = 1 return ((x mod phi) + phi) mod phi ```
Complexity & correctness
Time complexity. Let `n` have `k` bits (so `k` is roughly the security parameter, e.g. `k = 2048`).
- Primality generation: finding a random `k/2`-bit prime requires testing `O(k)` candidates on average (by the prime number theorem, density `~1/ln(2^{k/2})`), each tested via Miller–Rabin in `O(k²)` to `O(k³)` time depending on multiplication method. Total: polynomial in `k`.
- Modular exponentiation (`ModExp`): the loop runs once per bit of the exponent, so `O(k)` iterations, each doing a multiplication and reduction modulo an `k`-bit number. Using schoolbook multiplication that costs `O(k²)` per step, giving `O(k³)` total; with fast multiplication (e.g. Karatsuba or FFT-based), this drops toward `O(k² log k)` or better.
- Extended Euclidean Algorithm: runs in `O(k)` iterations with `O(k²)`-time arithmetic per step (via a similar analysis to the classical Modular Arithmetic and Primes for Cryptography Euclidean algorithm bounds), so `O(k²)` total — cheap compared to exponentiation.
So key generation, encryption, and decryption are all polynomial-time in the bit length `k` of the modulus — this is precisely what makes RSA usable, in contrast to factoring `n`, which is not known to have a polynomial-time classical algorithm.
Space complexity. All quantities involved (`p, q, n, e, d`, intermediate products in `ModExp`) are `O(k)`-bit integers, so space usage is `O(k)` throughout — linear in the key size, since `ModExp` never stores more than a constant number of `k`-bit values at once.
Correctness proof. We must show that for any message `m` with `0 ≤ m < n`, ``` (m^e)^d ≡ m (mod n) ``` Since `e·d ≡ 1 (mod φ(n))`, there is an integer `t` such that ``` e·d = 1 + t·φ(n) ``` so it suffices to show `m^{1 + t·φ(n)} ≡ m (mod n)`. Case 1: `gcd(m, n) = 1`. By Euler's theorem, `m^{φ(n)} ≡ 1 (mod n)`. Raise both sides to the power `t` and multiply by `m`: ``` m^{1 + t·φ(n)} = m · (m^{φ(n)})^t ≡ m · 1^t = m (mod n) ``` This gives exactly the claim. Case 2: `gcd(m, n) ≠ 1`. Since `n = p·q` for distinct primes, this means `m` is a multiple of `p`, of `q`, or (only if `m = 0`) both. Suppose `p | m` (the `q` case is symmetric). Then trivially `m^{1+t·φ(n)} ≡ 0 ≡ m (mod p)`. For the modulus `q`, since `p ∤ m` is not assumed but `gcd(m, q) = 1` (as `m` is not simultaneously a multiple of both primes, unless `m ≡ 0 (mod n)` which is a degenerate but still-correct edge case), Fermat's little theorem gives `m^{q-1} ≡ 1 (mod q)`, hence `m^{φ(n)} = m^{(p-1)(q-1)} ≡ 1 (mod q)` and the same argument as Case 1 shows `m^{1+t·φ(n)} ≡ m (mod q)`. Having shown the congruence holds mod `p` and mod `q` separately, the Chinese Remainder Theorem lets us combine them into a congruence mod `n = p·q`: ``` m^{1 + t·φ(n)} ≡ m (mod n) ``` Both cases together prove decryption always recovers the original message, for every `m` in `[0, n)`, not merely those coprime to `n`. This completeness over the full message space is what makes RSA a correct total function, not merely correct almost always.
Tradeoffs. RSA's correctness is unconditional (a mathematical theorem, not a heuristic), but its security is only conjectured — it rests on the unproven hardness of factoring. Its performance is also markedly worse than symmetric ciphers of comparable security: a 2048-bit RSA operation is orders of magnitude slower than an AES block operation, which is why in practice RSA encrypts only a short symmetric key, and that key does the bulk work (hybrid encryption).
Worked example
We use deliberately small primes for hand-tracing; real RSA uses primes hundreds of digits long.
Step 1 — choose primes. ``` p = 61, q = 53 ```
Step 2 — compute modulus and totient. ``` n = p · q = 61 · 53 = 3233 φ(n) = (p-1)(q-1) = 60 · 52 = 3120 ```
Step 3 — choose public exponent `e`. We need `gcd(e, 3120) = 1`. Choose `e = 17` (a common textbook choice). Check: `3120 = 2^4 · 3 · 5 · 13`, and `17` shares no factor with any of these, so `gcd(17, 3120) = 1`. ✓
Step 4 — compute private exponent `d = 17⁻¹ mod 3120`. Run the Extended Euclidean Algorithm on `(3120, 17)`:
| step | a | b | q = a div b | r = a mod b |
|---|---|---|---|---|
| 1 | 3120 | 17 | 183 | 9 |
| 2 | 17 | 9 | 1 | 8 |
| 3 | 9 | 8 | 1 | 1 |
| 4 | 8 | 1 | 8 | 0 |
Back-substituting gives `d = 2753`, and indeed `17 · 2753 = 46801 = 15·3120 + 1`, confirming `17 · 2753 ≡ 1 (mod 3120)`.
Public key: `(n, e) = (3233, 17)`. Private key: `(n, d) = (3233, 2753)`.
Step 5 — encrypt a message. Suppose Alice wants to send `m = 65` (e.g. an ASCII code). ``` c = 65^17 mod 3233 ``` Tracing `ModExp(65, 17, 3233)` via square-and-multiply (`17 = 10001₂`):
| bit | exponent (binary, MSB→LSB) | result after multiply | base after square |
|---|---|---|---|
| 1 | 1 | 65 | 65² mod 3233 = 4225 mod 3233 = 992 |
| 0 | 0 | 65 (unchanged) | 992² mod 3233 = 984064 mod 3233 = 1041 |
| 0 | 0 | 65 (unchanged) | 1041² mod 3233 = 1083681 mod 3233 = 1541 |
| 0 | 0 | 65 (unchanged) | 1541² mod 3233 = 2374681 mod 3233 = 2140 |
| 1 | 1 | 65 · 2140 mod 3233 = 139100 mod 3233 = 2790 | (done) |
So `c = 2790`.
Step 6 — decrypt. Bob computes ``` m' = 2790^2753 mod 3233 ``` using the same `ModExp` routine (this is the standard textbook result, verified algebraically above): the computation returns `m' = 65`, matching the original plaintext exactly, as guaranteed by Euler's theorem since `gcd(65, 3233) = 1` (as `65 = 5·13` shares no factor with `3233 = 61·53`). This confirms the full round trip `m → c → m` for a concrete numeric instance, matching the general correctness proof above.
Common pitfalls & traps
| Pitfall | Why it breaks RSA |
|---|---|
| Using textbook RSA directly on messages (no padding) | Deterministic ciphertext leaks equality of plaintexts; also enables chosen-ciphertext and multiplicative-malleability attacks |
| Picking `e` not coprime to `φ(n)` | No modular inverse `d` exists — key generation must fail and retry |
| Reusing the same prime `p` or `q` across two moduli | Computing `gcd(n₁, n₂)` instantly reveals shared factor, fully breaking both keys |
| Choosing `p, q` too close together | Enables Fermat factorization: `n = a² - b²` is solvable quickly when `p ≈ q` |
| Small public exponent with small padding-free messages | If `m^e < n`, `c = m^e` with no modular wraparound, so `m` is recoverable via ordinary integer `e`-th root |
| Encrypting the same short message to several recipients with same `e` | Håstad's broadcast attack recovers `m` via CRT across ciphertexts without ever factoring `n` |
| Forgetting to discard/protect `p, q, φ(n)` after key generation | Anyone with `φ(n)` and `n` can factor `n` trivially, breaking the private key |
Pioneers & history
Origins · 1 minRonald L. Rivest and how this was discovered
Ronald Rivest, together with Adi Shamir and Leonard Adleman, published the RSA algorithm in 1978 while at MIT, building on Diffie and Hellman's 1976 conceptual proposal for public-key cryptography. Rivest went on to co-design numerous widely used cryptographic primitives, including the MD family of hash functions, and remained a central figure in both theoretical cryptography and applied election-security research throughout his career.
Where this matters
RSA underlies TLS/SSL handshakes that secure HTTPS web traffic, where it (or its close relatives) historically encrypted or signed the symmetric session keys used for the bulk of a connection. It is embedded in SSH for server and client authentication, in PGP/GPG for encrypted email, and in code-signing certificates that let operating systems verify that software has not been tampered with. Smart cards, hardware security modules, and TPM chips implement RSA key generation and signing in dedicated silicon for banking, government ID, and secure boot systems. Because RSA operations are relatively expensive, it is almost always used in a hybrid scheme: RSA encrypts a short random symmetric key, and a fast cipher like AES encrypts the actual data — a pattern that recurs across nearly every secure communication protocol in use today. Understanding this article's core mechanics is the necessary foundation for reasoning about RSA Security and Factoring, padding-oracle attacks, and how the same exponentiation trick, run in reverse, produces Digital Signatures.
Ask the tutor: How does the RSA-OAEP padding scheme fix the malleability and determinism weaknesses of textbook RSA?
Why does RSA use two primes instead of one large prime for n?
Two primes let the key generator compute `φ(n) = (p-1)(q-1)` easily and privately, which is essential for finding `d`. If `n` itself were prime, then `φ(n) = n - 1`, and anyone who knew `n` (which is public) would immediately know `φ(n)` too, letting them compute `d` from `e` exactly as the legitimate key holder does. Using the product of two secret primes hides `φ(n)` behind the hardness of factoring: without knowing `p` and `q`, an attacker cannot efficiently compute `(p-1)(q-1)`, and therefore cannot derive `d` from the public `(n, e)`. This factoring-based secrecy of `φ(n)` is the entire security foundation of RSA.
Can RSA encrypt messages longer than the modulus n?
No, not directly. A message is represented as an integer `m` satisfying `0 ≤ m < n`, since encryption computes `m^e mod n`, and reduction modulo `n` would make any larger value ambiguous with a smaller equivalent one. In practice, plaintext longer than `n` is split into blocks (an approach with its own weaknesses) or, far more commonly, RSA is used only to encrypt a short symmetric key of fixed size, while the actual long message is encrypted with a fast symmetric cipher like AES. This hybrid design sidesteps RSA's message-length limitation and its poor performance on large data entirely.
Why is e = 65537 such a common choice for the public exponent?
`65537 = 2^{16} + 1` is prime, has a very simple binary representation (`10000000000000001₂`) with only two set bits, and is large enough to avoid several small-exponent attacks that plague choices like `e = 3`. Its binary form means `ModExp` needs only 16 squarings and a single extra multiplication to compute `m^e mod n`, making encryption and signature verification fast. Because it is odd and typically coprime to `(p-1)(q-1)` for randomly chosen primes, key generation with `e = 65537` rarely needs to retry, unlike very small `e` values which fail the coprimality check more often and are more attack-prone.
What happens if p and q are chosen too close to each other?
If `p` and `q` are close in value, `n = p·q` becomes vulnerable to Fermat factorization, which searches for integers `a, b` such that `n = a² - b²= (a-b)(a+b)`. Starting from `a = ⌈√n⌉` and incrementing, this search converges extremely fast precisely when `p` and `q` are near `√n`, because then `a ≈ (p+q)/2` is found almost immediately. Proper key generation requires `p` and `q` to differ by many bits and be independently random, which is why standards mandate generating primes of specified minimum bit-length difference rather than picking two primes near a target value.
Does RSA provide both encryption and digital signatures?
The same algebraic operation — modular exponentiation with a public/private exponent pair — underlies both, but the roles of the keys reverse. For encryption, anyone uses the public key `(n, e)` to encrypt, and only the private key `d` can decrypt. For signing, the signer uses their own private key `d` to "encrypt" (sign) a message digest, and anyone can use the public key `(n, e)` to verify that only the private-key holder could have produced that signature. Both directions rely on the exact same Euler's-theorem correctness argument developed in this article, which is why RSA signatures are covered as a direct extension of RSA encryption.
Is RSA still secure today, and what threatens it?
RSA with sufficiently large keys (2048 bits or more, per current guidance) is considered secure against all known classical attacks, since no polynomial-time classical factoring algorithm is known. However, Shor's algorithm shows that a sufficiently large fault-tolerant quantum computer could factor `n` in polynomial time, breaking RSA entirely; no such machine exists at the scale required today, but this threat motivates ongoing standardization of post-quantum cryptographic alternatives. Separately, RSA's classical security also depends heavily on correct implementation — padding schemes, random prime generation, and side-channel resistance all matter as much as key size, a topic explored further under RSA security and factoring.
Why is fast modular exponentiation essential rather than computing m^e directly?
Computing `m^e` as an ordinary integer before reducing modulo `n` is infeasible: for a 2048-bit modulus and a typical exponent, `m^e` would have astronomically more digits than atoms in the observable universe. Square-and-multiply instead reduces modulo `n` after every squaring and multiplication step, keeping every intermediate value bounded to roughly the same bit-length as `n` itself. This reduces the number of arithmetic operations from exponential in the exponent's value to linear in its bit-length, which is precisely what makes RSA's polynomial-time complexity claim true in practice, not just in principle.