Public-Key Cryptography

Public-key cryptography is the single most consequential application of elementary number theory in the history of human communication. Before 1976, secret communication required both parties to share a secret key in advance — meaning either a courier or a leaked tape would lose the war. Diffie and Hellman, then Rivest, Shamir, and Adleman, showed that you can publish your public key in a newspaper and still receive secret messages from anyone, without ever exchanging a private secret in advance. Every HTTPS handshake, every signed software update, every encrypted message you send today is built on this trick — and the math underneath is exactly Euler’s theorem from the previous section.

The RSA cryptosystem

RSA, named for Rivest, Shamir, Adleman (1977), turns Euler’s theorem into a working encryption scheme. The recipient generates a key pair:

• Pick two large distinct primes $p, q$ (each typically $1024$ bits in production).
• Compute the modulus $n = pq$ and the totient $\phi(n) = (p - 1)(q - 1)$.
• Pick a public exponent $e$ with $1 < e < \phi(n)$ and $\gcd(e, \phi(n)) = 1$. (In practice, $e = 65537$.)
• Compute the private exponent $d \equiv e^{-1} \pmod{\phi(n)}$ via the extended Euclidean algorithm.

The public key is $(n, e)$ — published openly. The private key is $d$ — kept secret.

Encryption and decryption

To encrypt a message $m$ with $0 \leq m < n$: compute $c = m^e \bmod n$. To decrypt: compute $m = c^d \bmod n$.

Why decryption recovers $m$. Because $ed \equiv 1 \pmod{\phi(n)}$, write $ed = 1 + k\phi(n)$ for some integer $k \geq 0$. Then, when $\gcd(m, n) = 1$, Euler’s theorem gives:

The remaining case $\gcd(m, n) > 1$ (meaning $p \mid m$ or $q \mid m$) is handled separately using the Chinese Remainder Theorem and Fermat’s little theorem; the answer is still $m$.

Worked example

Take $p = 5, q = 11$, so $n = 55$ and $\phi(n) = 4 \cdot 10 = 40$. Pick $e = 3$ (coprime to $40$). Compute $d$: $3d \equiv 1 \pmod{40}$, so $d = 27$ (verify: $3 \cdot 27 = 81 = 2 \cdot 40 + 1$). Public key $(55, 3)$, private key $27$. Encrypt $m = 2$: $c = 2^3 \bmod 55 = 8$. Decrypt $c = 8$: $m = 8^{27} \bmod 55$. Using repeated squaring inside $\mathbb{Z}/55\mathbb{Z}$, this reduces to $m = 2$.

Why RSA is secure

An attacker who sees $(n, e)$ wants the private $d$. To compute $d$ they need $\phi(n) = (p - 1)(q - 1)$. To compute $\phi(n)$ they need the factorisation $n = pq$. Factoring a 2048-bit semiprime is believed to take longer than the age of the universe on any classical computer. Multiplying two primes is fast (polynomial time); factoring their product is, as far as anyone knows, hard. This one-way trapdoor — easy forward, hard backward — is the foundation of every public-key system that descends from RSA.

Pause and think: What would go wrong if Alice published her public key $(n, e)$ but accidentally also leaked $\phi(n)$? Show that an attacker who knows $n$ and $\phi(n) = (p - 1)(q - 1)$ can recover $p$ and $q$ (and hence $d$) by solving a quadratic equation. The leak is total.

Try it

• Set up a toy RSA system with $p = 3, q = 11$. Compute $n$, $\phi(n)$, and find a valid $(e, d)$ pair. Encrypt $m = 4$ and verify the ciphertext.
• Predict before computing: with $n = 55, e = 3$, what is the ciphertext of $m = 10$? (Hint: $10^3 = 1000$; reduce mod $55$.)
• Explain in your own words why $e$ must be coprime to $\phi(n)$. (Hint: otherwise no $d$ inverts $e$ mod $\phi(n)$.)
• Two-step puzzle: an attacker intercepts the same plaintext $m$ encrypted with two different public moduli $(n_1, e), (n_2, e)$ using a small exponent like $e = 3$. Look up the “Hastad broadcast attack” and explain why small $e$ plus low padding is dangerous.

A trap to watch for

Textbook RSA — encrypting $m^e \bmod n$ with no further processing — is dangerous in practice. Reasons: (1) encrypting the same $m$ twice produces the same ciphertext, so an attacker can match repeated messages; (2) small messages with small exponents ($m^3 < n$) can be recovered by taking ordinary integer cube roots, no factoring needed; (3) homomorphic structure ($c_1 \cdot c_2 \equiv (m_1 m_2)^e$) lets an attacker manipulate ciphertexts. Production RSA always uses a padding scheme like OAEP that randomises the encoded message before exponentiation. The number-theoretic core in this section is correct — but real deployments wrap it carefully.

What you now know

You can generate an RSA key pair, encrypt and decrypt by hand on small primes, justify correctness via Euler’s theorem, and articulate the factoring-hardness assumption that protects the private exponent. You have now traversed the entire arc from $\gcd$ (§7.1) to a working encryption scheme — the journey is short, the destination is the modern internet. Velleman’s Chapter 8 turns to infinite sets and cardinality, where similar number-theoretic intuition will guide your first encounters with $\aleph_0$ versus $\mathfrak{c}$.

References

• Rivest, R. L., Shamir, A., Adleman, L. (1978). “A Method for Obtaining Digital Signatures and Public-Key Cryptosystems.” Communications of the ACM, 21(2), 120–126.
• Diffie, W., Hellman, M. E. (1976). “New Directions in Cryptography.” IEEE Transactions on Information Theory, 22(6), 644–654.
• Velleman, D. J. (2019). How to Prove It: A Structured Approach (3rd ed.). Cambridge University Press, §7.5.
• Stinson, D. R., Paterson, M. B. (2018). Cryptography: Theory and Practice (4th ed.). CRC Press, ch. 5–6.
• Koblitz, N. (1994). A Course in Number Theory and Cryptography (2nd ed.). Springer, ch. 4.