Engineering / Mathematics — Probabilistic Algorithms
The RSA Cryptosystem
RSA key generation, encryption, decryption and correctness, together with the assumptions its security depends on.
Executive summary
RSA is the archetypal public-key cryptosystem. Its correctness is Euler's theorem and its security rests on the difficulty of factoring, though the two are not known to be equivalent.
The textbook description is a mathematical core that is not by itself a secure encryption scheme, and the gap between the two is where most real failures occur.
Learning objectives
- State the key generation, encryption and decryption procedures.
- Prove correctness from Euler's theorem.
- Distinguish textbook RSA from a deployable scheme.
01The scheme
Key generation
Choose distinct primes p and q of the target size; set n = pq and compute φ(n) = (p−1)(q−1). Choose e coprime to φ(n) and compute d with ed ≡ 1 mod φ(n).
Public key
The pair (n, e), published freely.
Private key
The exponent d, together with p and q for the Chinese remainder speedup.
Encrypt
c = m^e mod n.
Decrypt
m = c^d mod n.
Correctness
(m^e)^d = m^{ed} = m^{1 + kφ(n)} = m · (m^{φ(n)})^k ≡ m (mod n) by Euler's theorem when gcd(m, n) = 1.
The identity also holds when m shares a factor with n, verified separately modulo p and q and combined by the Chinese remainder theorem.
02What the security rests on
| Quantity | Consequence if recoverable |
|---|---|
| The factorisation of n | φ(n) follows, then d; complete break |
| φ(n) | Yields the factorisation via a quadratic; complete break |
| d | Yields the factorisation by a randomised algorithm; complete break |
| A single plaintext | That message only; no key compromise |
The first three are computationally equivalent, so knowing any one of them is as good as knowing all. What is not established is the converse direction: breaking RSA encryption for a single ciphertext has never been proved to require factoring, and the RSA problem could in principle be easier.
03Textbook RSA is not an encryption scheme
- Deterministic. No semantic security. Small message spaces are exhaustively searchable.
- Malleable. Multiplying a ciphertext by
r^emultiplies the plaintext by r, permitting meaningful modification without the key. - Small exponent weakness. With small e and a short unpadded message,
m^emay be below n, so the plaintext is recovered by an integer root with no modular arithmetic at all. - Fault sensitivity. With the Chinese remainder speedup, a computational fault in one half exposes a factor of the modulus by a single gcd.
Deployable schemes use randomised padding — OAEP for encryption, PSS for signatures — which removes determinism and malleability and carries a security proof relative to the underlying assumption. Every one of the weaknesses above has appeared in a deployed system.
04Frequently asked questions
Why is e = 65537 the usual choice?
It is prime, so the coprimality check against φ(n) rarely fails, and its binary form has only two set bits, making encryption fast. It is also large enough to avoid the small-exponent attacks that afflict e = 3 with inadequate padding.
Can the same modulus serve several users?
No. Any holder of a valid private exponent for that modulus can factor it and derive everyone else's private key. Each user needs an independently generated modulus.
Is RSA obsolete?
Not yet, but it is being displaced. Elliptic curve systems give equivalent security at far smaller key sizes, and both fall to a sufficiently large quantum computer, which is what motivates post-quantum schemes.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 174-179.
This page carries the durable method layer only: definitions, constructions, algorithms, complexity results and selection criteria, authored originally for KEVOS. No text is transcribed or paraphrased from the source, and no numeric tables or benchmark data are reproduced — these are routed to live authoritative sources instead.
Author: Kevin Jogin. Last reviewed 2026-08-07.