RSA Mechanics

RSA (1977–78) was the first practical public-key cryptosystem and is still holding up a large share of the world's TLS certificates and code signatures. Its security rests on the presumed hardness of factoring a large semiprime. The mechanics fit on one page — which is why every course teaches it — but essentially every real-world RSA break has come not from factoring but from the gap between those clean equations and a safe implementation.

Why asymmetric crypto exists at all #

With symmetric ciphers, every pair of communicating parties needs its own shared key: $M$ users require $\binom{M}{2} \approx M^2/2$ keys, all distributed out of band, and one compromised machine exposes every conversation it participated in. Public-key crypto makes it linear — $2M$ keys, one keypair per user, public halves published freely.

The trade is speed. RSA is orders of magnitude slower than AES, so nobody encrypts bulk data with it: you encrypt a random session key with the recipient's public key, ship that alongside the AES-encrypted payload, and that hybrid pattern is what TLS, PGP, S/MIME and age all do.

Key generation and the algorithm #

1. Pick two large random primes $p, q$ of equal bit length. Compute $n = pq$.
2. Compute $\varphi(n) = (p-1)(q-1)$.
3. Choose a public exponent $e$ with $\gcd(e, \varphi(n)) = 1$.
4. Compute $d = e^{-1} \bmod \varphi(n)$ with the extended Euclidean algorithm.
5. Public key is $(e, n)$; private key is $d$. Discard $p$ and $q$ — but never disclose them.

$$c = m^e \bmod n, \qquad m = c^d \bmod n$$

Correctness follows from Euler's theorem: since $ed \equiv 1 \pmod{\varphi(n)}$, write $ed = k\varphi(n) + 1$, so

$$c^d = m^{ed} = m^{k\varphi(n)+1} = \left(m^{\varphi(n)}\right)^k \cdot m \equiv 1^k \cdot m = m \pmod n$$

Textbook RSA is broken — padding is not optional #

The bare equation $c = m^e \bmod n$ fails as an encryption scheme on multiple counts:

• Deterministic. Same plaintext → same ciphertext. An attacker with a guessable message space (a yes/no vote, a credit card number, a session ID) just encrypts every candidate under the public key and matches. Semantic security requires randomness in every encryption.
• Malleable. $(m_1 m_2)^e = m_1^e \cdot m_2^e \bmod n$ — multiply a ciphertext by $r^e$ and the plaintext gets multiplied by $r$, without the private key. This homomorphism is a feature in other contexts and a disaster here.
• Small message + small exponent. If $m^e < n$ (e.g. $e = 3$ and a short message), no modular reduction happens and $m = \sqrt[e]{c}$ over the integers. Håstad's broadcast attack generalizes it: the same message sent to $e$ recipients under $e$ different moduli is recoverable by CRT.

The fixes are the padding schemes in RFC 8017:

Failure modes that aren't factoring #

Nobody has factored a 2048-bit RSA modulus. The public record of RSA compromise is almost entirely about implementation:

• Bad randomness in key generation. Heninger et al. (2012) scanned the internet and computed the private keys of 0.50% of TLS hosts — roughly 64,000 — because their moduli shared a prime factor with another host's. The cause was embedded devices generating keys at first boot from an unseeded entropy pool. Any two moduli sharing a factor are both broken by a single GCD, which costs nothing against a corpus you already have. This makes entropy a load-bearing dependency of RSA, not a detail.
• Side channels. Timing and power analysis of modular exponentiation, and the CRT fault attack — a single bit-flip during one CRT half lets $\gcd(m - s^e, n)$ reveal $p$. Constant-time implementations and signature verification-after-signing are mandatory countermeasures.
• Shared or reused moduli, structurally weak primes from a flawed generator — ROCA (CVE-2017-15361, 2017), an Infineon key-generation defect that made 1024- and 2048-bit keys factorable from the public key alone, forcing Estonia to suspend and re-issue certificates for 760,000 national ID cards and affecting Infineon TPMs, Gemalto smartcards and YubiKeys besides.

Source claims audit #

Seeded from a university lab manual (RSA lab, following Applied Cryptography). Status of its load-bearing claims: