Public-Key Cryptography

Why This Matters

Before 1976, all cryptography required both parties to share a secret key in advance. Public-key cryptography solved this: two parties who have never communicated can establish a shared secret over a public channel. The mathematical mechanism relies on problems that are easy to set up but hard to reverse: multiplying large primes is fast, factoring their product is (believed to be) hard.

RSA and Diffie-Hellman are the two foundational constructions. RSA provides encryption and digital signatures. Diffie-Hellman provides key exchange. Both rely on number-theoretic hardness assumptions that have withstood decades of attack by the best mathematicians and computer scientists. Understanding the precise mathematical structure of these systems is necessary for reasoning about their security guarantees and failure modes.

Number-Theoretic Foundations

Definition

Modular Arithmetic

For integers $a$, $b$, and positive integer $n$, we write $a \equiv b \pmod{n}$ if $n$ divides $a - b$. The set $\mathbb{Z}/n\mathbb{Z} = \{0, 1, \ldots, n-1\}$ forms a ring under addition and multiplication modulo $n$.

Definition

Euler Totient Function

For a positive integer $n$, Euler's totient function $\phi(n)$ counts the number of integers in $\{1, \ldots, n\}$ that are coprime to $n$. Key properties:

• If $p$ is prime: $\phi(p) = p - 1$
• If $p, q$ are distinct primes: $\phi(pq) = (p-1)(q-1)$
• The group of units $(\mathbb{Z}/n\mathbb{Z})^\times$ has order $\phi(n)$

Definition

Trapdoor One-Way Function

A function $f$ is a one-way function if it is easy to compute $f(x)$ from $x$ but computationally infeasible to find $x$ from $f(x)$. A trapdoor one-way function additionally has a secret (the trapdoor) that makes inversion efficient. Without the trapdoor, inversion is hard. With it, inversion is easy. Public-key cryptography requires trapdoor one-way functions: the public key defines the easy direction, and the private key is the trapdoor.

Euler's Theorem

Theorem

Euler's Theorem

Statement

If $\gcd(a, n) = 1$, then:

$a^{\phi(n)} \equiv 1 \pmod{n}$

When $n = p$ is prime, this reduces to Fermat's little theorem: $a^{p-1} \equiv 1 \pmod{p}$ for $a \not\equiv 0 \pmod{p}$.

Intuition

The integers coprime to $n$ form a multiplicative group $(\mathbb{Z}/n\mathbb{Z})^\times$ of order $\phi(n)$. By Lagrange's theorem from group theory, the order of every element divides the group order. So $a^{\phi(n)} = 1$ in this group.

Proof Sketch

Let $\{r_1, \ldots, r_{\phi(n)}\}$ be the elements of $(\mathbb{Z}/n\mathbb{Z})^\times$. Since $\gcd(a, n) = 1$, multiplication by $a$ permutes these elements: $\{ar_1, \ldots, ar_{\phi(n)}\}$ is the same set modulo $n$. Therefore $\prod_i (ar_i) \equiv \prod_i r_i \pmod{n}$, giving $a^{\phi(n)} \prod_i r_i \equiv \prod_i r_i \pmod{n}$. Since each $r_i$ is coprime to $n$, cancel $\prod r_i$ to get $a^{\phi(n)} \equiv 1 \pmod{n}$.

Why It Matters

Euler's theorem is the engine behind RSA. The correctness of RSA decryption follows directly from the fact that $a^{k\phi(n) + 1} \equiv a \pmod{n}$ when $\gcd(a, n) = 1$.

Failure Mode

The theorem requires $\gcd(a, n) = 1$. If $a$ shares a factor with $n$, the conclusion fails. In RSA, where $n = pq$, the message $m$ must satisfy $\gcd(m, n) = 1$. If $m$ is a multiple of $p$ or $q$, RSA still works by the Chinese Remainder Theorem, but the proof path changes.

RSA Cryptosystem

Key Generation

1. Choose two large distinct primes $p$ and $q$ (typically 1024+ bits each)
2. Compute $n = pq$ and $\phi(n) = (p-1)(q-1)$
3. Choose $e$ with $1 < e < \phi(n)$ and $\gcd(e, \phi(n)) = 1$ (common choice: $e = 65537$)
4. Compute $d \equiv e^{-1} \pmod{\phi(n)}$ using the extended Euclidean algorithm
5. Public key: $(n, e)$. Private key: $(n, d)$. Discard $p$, $q$, and $\phi(n)$.

Encryption and Decryption

• Encrypt: Given plaintext $m \in \{0, \ldots, n-1\}$, compute ciphertext $c \equiv m^e \pmod{n}$
• Decrypt: Given ciphertext $c$, compute $m \equiv c^d \pmod{n}$

Theorem

RSA Correctness

Statement

For any message $m \in \{0, \ldots, n-1\}$:

$m^{ed} \equiv m \pmod{n}$

That is, decryption recovers the original message: $(m^e)^d \equiv m \pmod{n}$.

Intuition

Since $ed \equiv 1 \pmod{\phi(n)}$, write $ed = 1 + k\phi(n)$ for some integer $k$. Then $m^{ed} = m \cdot (m^{\phi(n)})^k$. By Euler's theorem, $m^{\phi(n)} \equiv 1 \pmod{n}$ when $\gcd(m, n) = 1$, so $m^{ed} \equiv m \pmod{n}$.

Proof Sketch

Write $ed = 1 + k(p-1)(q-1)$.

Case 1: $\gcd(m, n) = 1$. By Euler's theorem, $m^{\phi(n)} \equiv 1 \pmod{n}$, so $m^{ed} = m \cdot (m^{\phi(n)})^k \equiv m \pmod{n}$.

Case 2: $p | m$ but $q \nmid m$ (i.e., $\gcd(m, n) = p$). Work modulo $p$ and $q$ separately. Modulo $p$: $m \equiv 0$, so $m^{ed} \equiv 0 \equiv m \pmod{p}$. Modulo $q$: $\gcd(m, q) = 1$, so $m^{q-1} \equiv 1 \pmod{q}$ by Fermat's little theorem, hence $m^{ed} = m \cdot (m^{(p-1)(q-1)})^k \equiv m \pmod{q}$. By the Chinese Remainder Theorem, $m^{ed} \equiv m \pmod{n}$.

Case 3: $n | m$. Then $m \equiv 0 \pmod{n}$ and $m^{ed} \equiv 0 \equiv m \pmod{n}$.

Why It Matters

This theorem guarantees that RSA decryption always works. The proof covers all cases, including the edge case where $m$ shares a factor with $n$. Without this completeness, RSA would be unreliable.

Failure Mode

RSA correctness holds regardless of the choice of $m$. However, RSA security requires additional conditions: $p$ and $q$ must be large, random, and of similar size. If $p$ and $q$ are close together, Fermat factorization finds them quickly. If either is small, trial division succeeds. Textbook RSA (without padding) is also vulnerable to chosen-ciphertext attacks and lacks semantic security. In practice, RSA must be used with proper padding schemes like OAEP.

Example

Small RSA computation

Let $p = 61$, $q = 53$. Then $n = 3233$ and $\phi(n) = 60 \times 52 = 3120$.

Choose $e = 17$ (coprime to 3120). Compute $d \equiv 17^{-1} \pmod{3120}$. Using the extended Euclidean algorithm: $d = 2753$ (since $17 \times 2753 = 46801 = 15 \times 3120 + 1$).

Encrypt $m = 65$: $c = 65^{17} \bmod 3233 = 2790$.

Decrypt: $m = 2790^{2753} \bmod 3233 = 65$. The original message is recovered.

Diffie-Hellman Key Exchange

Definition

Diffie-Hellman Protocol

Let $p$ be a large prime and $g$ a generator of $(\mathbb{Z}/p\mathbb{Z})^\times$.

1. Alice chooses random $a \in \{2, \ldots, p-2\}$, sends $A = g^a \bmod p$ to Bob
2. Bob chooses random $b \in \{2, \ldots, p-2\}$, sends $B = g^b \bmod p$ to Alice
3. Shared secret: Alice computes $B^a = g^{ab} \bmod p$. Bob computes $A^b = g^{ab} \bmod p$. Both obtain the same value $K = g^{ab} \bmod p$.

An eavesdropper sees $g$, $p$, $g^a$, and $g^b$, but must compute $g^{ab}$ from these values. This is the Computational Diffie-Hellman (CDH) problem.

Definition

Discrete Logarithm Problem (DLP)

Given a prime $p$, a generator $g$ of $(\mathbb{Z}/p\mathbb{Z})^\times$, and a value $h = g^x \bmod p$, the discrete logarithm problem asks: find $x$. The best known classical algorithms (general number field sieve for DLP, Pollard's rho) run in subexponential time $L_p[1/3, c]$ for appropriate constants. No polynomial-time classical algorithm is known.

Security Assumptions

The security of RSA and Diffie-Hellman rests on computational hardness assumptions, not proven lower bounds.

Integer Factorization Assumption: Given $n = pq$ for random primes $p, q$ of equal bit-length, no polynomial-time algorithm can find $p$ and $q$ with non-negligible probability.

Decisional Diffie-Hellman (DDH) Assumption: In a group $G$ of prime order $q$ with generator $g$, the tuples $(g^a, g^b, g^{ab})$ and $(g^a, g^b, g^c)$ are computationally indistinguishable for random $a, b, c$.

Both assumptions are believed to be true but unproven. Breaking either would not immediately resolve P vs NP, since factoring and DLP might be in NP $\cap$ co-NP (and thus unlikely to be NP-complete). However, both problems fall to Shor's algorithm on a quantum computer, running in polynomial time.

Post-Quantum Concerns

Shor's algorithm factors $n$-bit integers in $O(n^3)$ time on a quantum computer and solves the discrete logarithm problem in comparable time. If large-scale quantum computers become practical, RSA and Diffie-Hellman are broken.

Post-quantum alternatives rely on different hardness assumptions:

• Lattice-based: Learning With Errors (LWE), Ring-LWE
• Code-based: McEliece cryptosystem
• Hash-based: SPHINCS+ for signatures

NIST standardized lattice-based schemes (ML-KEM, ML-DSA) in 2024 as replacements.

Common Confusions

Watch Out

Public key does not always mean encryption key

In RSA, the public key can encrypt and the private key decrypts. But RSA also supports digital signatures, where the private key signs (encrypts the hash) and the public key verifies. In Diffie-Hellman, neither party has an "encryption key" at all: the protocol produces a shared secret, which is then used as a symmetric key. "Public key = encryption key" is an oversimplification that breaks down outside basic RSA encryption.

Watch Out

RSA security is not equivalent to factoring

Breaking RSA (recovering $m$ from $c = m^e \bmod n$) is not known to be equivalent to factoring $n$. It is possible in principle that one could decrypt without factoring. What is known: factoring $n$ breaks RSA (since knowing $p$ and $q$ lets you compute $d$). The converse is open. In practice, all known attacks on RSA either factor $n$ or exploit implementation flaws (timing, padding oracles).

Watch Out

Large key size does not mean large security margin

RSA key sizes (2048 or 4096 bits) are much larger than symmetric key sizes (128 or 256 bits) because the best attacks on RSA (number field sieve) are subexponential, not exponential. A 2048-bit RSA key provides roughly 112 bits of security, comparable to a 112-bit symmetric key. The numbers are not directly comparable.

Exercises

ExerciseCore

Problem

In RSA with $p = 11$ and $q = 13$, compute the public and private keys using $e = 7$. Then encrypt the message $m = 9$ and verify that decryption recovers it.

Hint

Reveal Solution

ExerciseCore

Problem

In Diffie-Hellman with $p = 23$ and $g = 5$, Alice chooses $a = 6$ and Bob chooses $b = 15$. Compute the public values each sends and the shared secret.

Hint

Reveal Solution

ExerciseAdvanced

Problem

Prove that if you can compute $\phi(n)$ from $n = pq$ (where $p, q$ are unknown primes), you can factor $n$. That is, show that knowing $\phi(n)$ is equivalent to knowing the factorization.

Hint

Reveal Solution

ExerciseAdvanced

Problem

Why is textbook RSA (without padding) not semantically secure? Construct a concrete attack.

Hint

Reveal Solution

References

Canonical:

• Katz & Lindell, Introduction to Modern Cryptography (2020), Chapters 8-13 for public-key encryption, digital signatures, and number-theoretic constructions
• Shoup, A Computational Introduction to Number Theory and Algebra (2009), Chapters 10-12 for the mathematical foundations

Foundational papers:

• Diffie & Hellman, "New Directions in Cryptography" (1976)
• Rivest, Shamir, Adleman, "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems" (1978)

Current:

• Boneh & Shoup, A Graduate Course in Applied Cryptography (2023), Chapters 10-11, freely available online
• NIST, "Post-Quantum Cryptography Standards" (2024), for ML-KEM and ML-DSA specifications

Next Topics

• Zero-knowledge proofs: prove knowledge of a secret without revealing it, building on the hardness assumptions introduced here