47.06.02 · theoretical-cs / 06-cryptographic-foundations

Public-Key Cryptography: RSA and the Discrete Logarithm

shipped3 tiersLean: none

Anchor (Master): Arora and Barak 2009 Computational Complexity: A Modern Approach (Cambridge) Ch. 10; Rivest, Shamir and Adleman 1978 A Method for Obtaining Digital Signatures and Public-Key Cryptosystems (CACM); Shor 1997 Polynomial-Time Algorithm for Prime Factorization and Discrete Logarithms (SIAM J. Comput.)

Intuition Beginner

Symmetric cryptography uses the same key to encrypt and decrypt. The problem: how do two people agree on a shared key without meeting? Public-key cryptography solves this elegantly. Everyone has two keys: a public key (shared with the world) and a private key (kept secret). Anyone can encrypt a message using your public key, but only you can decrypt it using your private key.

The trick relies on mathematical asymmetry. RSA uses the fact that multiplying two large primes is easy, but factoring their product is hard. Diffie-Hellman uses the fact that computing $g^{a} mod p$ is easy, but recovering $a$ from $g^{a} mod p$ (the discrete logarithm problem) is hard.

RSA works as follows. You pick two large primes $p$ and $q$ , multiply them to get $N = pq$ , and publish $N$ along with an encryption exponent $e$ . To send you a message $m$ , someone computes $m^{e} mod N$ . You decrypt by computing $(m^{e})^{d} mod N = m$ using a secret decryption exponent $d$ . The relationship between $e$ and $d$ involves Euler's totient function, and computing $d$ from $N$ and $e$ requires factoring $N$ , which is believed to be hard.

The beauty of public-key cryptography is that it transforms the key-distribution problem into a computational-hardness problem. Security is not absolute but conditional: if factoring is hard (or discrete log is hard), then the system is secure.

Visual Beginner

RSA key generation:
  1. Pick primes p = 61, q = 53
  2. Compute N = 61 * 53 = 3233
  3. Compute phi(N) = (61-1)(53-1) = 3120
  4. Choose e = 17 (coprime to 3120)
  5. Compute d = e^(-1) mod 3120 = 2753
  6. Public key: (N=3233, e=17)
     Private key: d=2753

Encryption of m = 65:
  c = 65^17 mod 3233 = 2790

Decryption:
  m = 2790^2753 mod 3233 = 65

Diffie-Hellman key exchange:
  Public: p = 23, g = 5
  Alice picks a = 6, sends A = 5^6 mod 23 = 8
  Bob picks b = 15, sends B = 5^15 mod 23 = 19
  Shared secret: Alice computes 19^6 mod 23 = 2
                Bob computes 8^15 mod 23 = 2

System	Hard problem	Quantum-safe?
RSA	Factoring $N = pq$	No (Shor's algorithm)
Diffie-Hellman	Discrete logarithm in $Z_{p}^{*}$	No (Shor's algorithm)
Elliptic curve DH	Elliptic curve discrete log	No (Shor's algorithm)
Learning With Errors	Lattice problem	Yes (believed)

Worked example Beginner

We walk through RSA with toy parameters. Pick primes $p = 11$ and $q = 3$ .

Key generation. $N = 11 \times 3 = 33$ . $ϕ (N) = (11 - 1) (3 - 1) = 20$ . Choose $e = 3$ (coprime to 20). Compute $d = e^{- 1} mod 20$ . We need $3 d \equiv 1 (mod 20)$ . Testing: $3 \times 7 = 21 \equiv 1 (mod 20)$ , so $d = 7$ .

Public key: $(N, e) = (33, 3)$ . Private key: $d = 7$ .

Encryption. Message $m = 14$ . Compute $c = 1 4^{3} mod 33$ . $1 4^{2} = 196 = 5 \times 33 + 31$ , so $1 4^{2} \equiv 31 (mod 33)$ . Then $1 4^{3} \equiv 31 \times 14 = 434 = 13 \times 33 + 5$ , so $c = 5$ .

Decryption. Compute $m = 5^{7} mod 33$ . $5^{2} = 25$ , $5^{4} = 625 = 18 \times 33 + 31$ , so $5^{4} \equiv 31$ . $5^{7} = 5^{4} \times 5^{2} \times 5 = 31 \times 25 \times 5 = 3875 = 117 \times 33 + 14$ , so $m = 14$ . Correct.

Why it works. Euler's theorem says $m^{ϕ (N)} \equiv 1 (mod N)$ when $g cd (m, N) = 1$ . Since $e d = 3 \times 7 = 21 = 1 + 1 \times 20 = 1 + ϕ (N)$ , we have $m^{e d} = m^{1 + ϕ (N)} = m \cdot m^{ϕ (N)} \equiv m \cdot 1 = m (mod N)$ .

Check your understanding Beginner

Formal definition Intermediate+

Definition (RSA assumption). Given a product $N = pq$ of two random $n$ -bit primes and a public exponent $e$ coprime to $ϕ (N)$ , for every PPT algorithm $A$ :

Pr [A (N, e, m^{e} mod N) = m] \leq negl (n)

where $m$ is chosen uniformly from $Z_{N}^{*}$ .

Definition (discrete logarithm problem). Given a cyclic group $G$ of prime order $q$ , a generator $g$ , and $h = g^{a}$ for random $a \in Z_{q}$ , the discrete logarithm problem is to find $a$ .

Definition (CDH assumption). For a cyclic group $G$ with generator $g$ , given $(g, g^{a}, g^{b})$ for random $a, b$ , no PPT algorithm can compute $g^{ab}$ with non-negligible probability.

Definition (DDH assumption). For a cyclic group $G$ with generator $g$ , no PPT algorithm can distinguish $(g, g^{a}, g^{b}, g^{ab})$ from $(g, g^{a}, g^{b}, g^{c})$ for random $a, b, c$ with non-negligible advantage.

Definition (IND-CPA security). A public-key encryption scheme $(K ey G e n, E n c, D ec)$ is IND-CPA secure if no PPT adversary $A$ can win the following game with non-negligible advantage: (1) $A$ receives the public key $p k$ , (2) $A$ submits two messages $m_{0}, m_{1}$ , (3) the challenger encrypts $m_{b}$ for random $b$ , (4) $A$ outputs a guess $b^{'}$ , and $A$ wins if $b^{'} = b$ .

Counterexamples to common slips

"RSA with $e = 3$ is always insecure." RSA with small $e$ is vulnerable to specific attacks (e.g., Coppersmith's attack when $m$ is much smaller than $N$ ), but not inherently insecure when proper padding (OAEP) is used.
"Diffie-Hellman is the same as RSA." DH is based on the discrete logarithm problem in a group; RSA is based on factoring. They are different hardness assumptions, though both are broken by Shor's quantum algorithm.
"IND-CPA security means the encryption is unbreakable." IND-CPA only protects against passive eavesdroppers who see ciphertexts. It does not protect against chosen-ciphertext attacks (IND-CCA), which is the standard security requirement for real systems.

Key theorem with proof Intermediate+

Theorem (RSA correctness). Let $N = pq$ for distinct primes $p, q$ , $e$ coprime to $ϕ (N) = (p - 1) (q - 1)$ , and $d = e^{- 1} mod ϕ (N)$ . Then for all $m \in Z_{N}^{*}$ , $(m^{e})^{d} \equiv m (mod N)$ .

Proof. Since $e d \equiv 1 (mod ϕ (N))$ , we have $e d = 1 + k ϕ (N)$ for some integer $k$ . By Euler's theorem, $m^{ϕ (N)} \equiv 1 (mod N)$ for any $m$ coprime to $N$ . Therefore:

m^{e d} = m^{1 + k ϕ (N)} = m \cdot (m^{ϕ (N)})^{k} \equiv m \cdot 1^{k} = m (mod N) .

This works even when $g cd (m, N) \neq = 1$ (i.e., when $m$ is a multiple of $p$ or $q$ ), by applying the Chinese Remainder Theorem: modulo $p$ , $m^{e d} \equiv m^{1 + k (p - 1) (q - 1)} \equiv m \cdot (m^{p - 1})^{k (q - 1)} \equiv m \cdot 1 = m (mod p)$ by Fermat's little theorem (if $p ∤ m$ ; if $p ∣ m$ then both sides are 0 mod $p$ ). Similarly mod $q$ . By CRT, $m^{e d} \equiv m (mod N)$ . $□$

Bridge. The RSA construction is the foundational reason public-key cryptography works: the algebraic structure of modular arithmetic provides a function that is a permutation (so decryption is always possible) yet one-way without the trapdoor (so only the private key holder can decrypt). This builds toward the Diffie-Hellman key exchange which achieves a different goal (key agreement rather than encryption) using a different algebraic structure (group exponentiation rather than ring exponentiation). The central insight is that trapdoor one-way functions arise from the gap between computing a function and inverting it, and this is exactly the pattern that appears again in 47.06.04 where digital signatures use the same RSA function in reverse (sign with $d$ , verify with $e$ ). Putting these together with the one-way function theory of 47.06.01 shows that public-key cryptography requires structured hardness assumptions (factoring, discrete log) that go beyond the generic OWF, and this structural requirement is the reason public-key primitives cannot be constructed from generic OWFs via black-box reductions.

Exercises Intermediate+

Exercise 5 (medium, short answer).

Explain why Shor's quantum algorithm breaks both RSA and Diffie-Hellman. What is the common structure it exploits?

Answer

Both RSA and Diffie-Hellman reduce to finding the period of a function. For RSA (factoring $N = pq$ ), the function is $f (x) = a^{x} mod N$ for random $a$ coprime to $N$ . The period $r$ satisfies $a^{r} \equiv 1 (mod N)$ . If $r$ is even, then $(a^{r /2})^{2} \equiv 1 (mod N)$ , so $g cd (a^{r /2} - 1, N)$ gives a factor of $N$ with probability $\geq 1/2$ . For discrete log ( $h = g^{a} mod p$ , find $a$ ), the function is $f (x, y) = g^{x} h^{y} mod p$ with period $(a, - 1)$ in $(Z_{p})^{2}$ . Shor's algorithm uses the quantum Fourier transform to find the period in polynomial time, breaking both problems. The common structure is a periodic function over a finite abelian group, and quantum Fourier sampling extracts the period efficiently.

Exercise 6 (hard, symbolic).

Prove that RSA with $e = 2$ (Rabin encryption) is as hard to invert as factoring $N = pq$ . Specifically, show that an algorithm $A$ that computes square roots modulo $N$ can be used to factor $N$ .

Answer

Given $N = pq$ and a square-root oracle $A$ that on input $y$ returns $x$ with $x^{2} \equiv y (mod N)$ :

Pick a random $r \in Z_{N}^{*}$ . Compute $y = r^{2} mod N$ . Feed $y$ to $A$ to get $r^{'}$ with $r^{'2} \equiv r^{2} (mod N)$ . Then $(r^{'})^{2} - r^{2} \equiv 0 (mod N)$ , so $(r^{'} - r) (r^{'} + r) \equiv 0 (mod N)$ .

If $r^{'} \neq \equiv \pm r (mod N)$ , then neither $r^{'} - r$ nor $r^{'} + r$ is divisible by $N$ (since $0 < ∣ r^{'} \pm r ∣ < N$ with high probability), but their product is. This means $g cd (r^{'} - r, N)$ is a nontrivial factor of $N$ .

The probability that $r^{'} \equiv \pm r (mod N)$ is $1/2$ (since $y = r^{2}$ has four square roots modulo $N$ : $\pm r mod p$ and $\pm r mod q$ , combined via CRT into four roots, two of which are $\pm r$ ). So the algorithm succeeds with probability $1/2$ per trial, and expected $O (1)$ trials suffice. Rubric: full credit for the $g cd$ argument and the $1/2$ probability analysis.

Exercise 7 (hard, symbolic).

The ElGamal encryption scheme works as follows in a group $G$ of order $q$ with generator $g$ : key generation picks random $x \in Z_{q}$ and sets $p k = g^{x}$ , $s k = x$ ; encryption of message $m$ picks random $r$ and outputs $(g^{r}, m \cdot (p k)^{r})$ ; decryption of $(c_{1}, c_{2})$ computes $m = c_{2} / c_{1}^{x}$ . Prove that ElGamal is IND-CPA secure if and only if DDH holds in $G$ .

Answer

DDH implies IND-CPA. In the IND-CPA game, the adversary receives $p k = g^{x}$ and challenge ciphertext $(g^{r}, m_{b} \cdot g^{x r})$ . The value $g^{x r} = (g^{x})^{r} = p k^{r}$ is the Diffie-Hellman shared secret. By DDH, $(g, g^{x}, g^{r}, g^{x r})$ is indistinguishable from $(g, g^{x}, g^{r}, g^{s})$ for random $s$ . If we replace $g^{x r}$ with a random $g^{s}$ , the ciphertext becomes $(g^{r}, m_{b} \cdot g^{s})$ , and $m_{b} \cdot g^{s}$ is uniformly random (since $g^{s}$ is a uniform group element masking $m_{b}$ ). So the adversary gains no information about $b$ .

IND-CPA implies DDH. Suppose DDH does not hold: there exists a distinguisher $D$ for $(g, g^{a}, g^{b}, g^{c})$ vs. $(g, g^{a}, g^{b}, g^{ab})$ . We build an IND-CPA adversary $A$ for ElGamal: receive $p k = g^{a}$ , submit $m_{0} = 1, m_{1} = g^{c - ab}$ (computed using the DDH challenge), receive ciphertext $(g^{r}, m_{b} \cdot g^{a r}) = (g^{b}, m_{b} \cdot g^{ab})$ where we identify $r = b$ . If $c = ab$ , then $m_{1} = g^{0} = 1 = m_{0}$ and both messages are identical; if $c \neq = ab$ , then $m_{1} \neq = m_{0}$ , and $A$ can distinguish. A cleaner reduction: given a DDH challenge $(g, g^{a}, g^{b}, g^{c})$ , set $p k = g^{a}$ , encrypt the identity element to get $(g^{b}, g^{c})$ , and use $D$ to check if this is a valid ElGamal ciphertext (which requires $g^{c} = g^{ab}$ ). Rubric: full credit for both directions.

Exercise 8 (hard, short answer).

Why is the Learning With Errors (LWE) problem considered quantum-resistant, unlike RSA and discrete log?

Answer

LWE asks: given a matrix $A$ and vector $b = A s + e mod q$ for secret $s$ and small error vector $e$ , find $s$ . The best known classical and quantum algorithms for LWE require $2^{O (n)}$ time for $n$ -dimensional instances (the best algorithms are lattice reduction algorithms like BKZ, which run in $2^{O (n / l o g n)}$ time). Unlike the period-finding structure exploited by Shor's algorithm for factoring and discrete log, LWE does not reduce to finding the period of a function over a finite abelian group. The quantum Fourier transform does not directly help with lattice problems. LWE is also connected to worst-case lattice problems (GapSVP, SIVP) via the Regev reduction (2005), so solving LWE on average would solve these worst-case problems, which have resisted quantum attack for decades.

Lean formalization Intermediate+

Mathlib has the algebraic prerequisites for RSA (modular arithmetic, Euler's theorem, CRT in NumberTheory.ZMod and GroupTheory.Coset) but no formalization of cryptographic security notions or reduction proofs. A natural formalization target would be the RSA correctness proof (Proposition: $m^{e d} \equiv m (mod N)$ ) using Mathlib's existing number theory. The security reduction (factoring implies RSA assumption) would require modelling PPT adversaries and negligible functions. This unit ships without a lean_module.

Advanced results Master

Three results sharpen our understanding of public-key cryptography's foundations and limitations.

Result 1 (random oracle model and beyond). The security of RSA-OAEP (RSA with Optimal Asymmetric Encryption Padding) was proven IND-CCA secure in the random oracle model by Bellare and Rogaway (1994), assuming the RSA problem is hard. Fujisaki, Okamoto, Pointcheval and Stern (2004) proved that any IND-CPA scheme can be transformed into an IND-CCA scheme in the random oracle model. However, Canetti, Goldreich and Halevi (1998) showed that there exist schemes secure in the random oracle model that are insecure when the random oracle is instantiated with any concrete hash function ^{[Arora-Barak Ch. 10]}.

Result 2 (lattice-based cryptography and quantum resistance). Regev (2005) introduced the Learning With Errors problem and proved that solving LWE on average is as hard as solving worst-case lattice problems (GapSVP, SIVP) for quantum algorithms. This worst-case-to-average-case reduction is the foundational reason lattice-based cryptography is believed to be quantum-resistant. The NIST post-quantum standardisation process selected Kyber (key encapsulation) and Dilithium (signatures), both based on module-LWE ^{[Shor 1997]}.

Result 3 (Impagliazzo's five worlds). Impagliazzo (1995) described five possible complexity-theoretic worlds, ordered by the strength of available cryptographic primitives. In Pessiland (NP is hard on average but one-way functions do not exist), no public-key cryptography is possible. In Minicrypt (OWFs exist but not trapdoor OWFs), symmetric cryptography exists but public-key cryptography does not. In Cryptomania (trapdoor OWFs exist), full public-key cryptography is available. The question of which world we inhabit is the central open problem of cryptographic foundations ^{[Arora-Barak Ch. 10]}.

Synthesis. Public-key cryptography rests on structured hardness assumptions that go beyond generic one-way functions: factoring and discrete logarithm provide the algebraic structure needed for trapdoor operations, and this builds toward the quantum-resistance question where lattice problems replace number-theoretic problems as the hardness foundation. The central insight is that the algebraic structure enabling public-key encryption (modular exponentiation, group operations) is also the structure that quantum algorithms exploit (period finding), and this is exactly the pattern that appears again in 47.06.03 where zero-knowledge proofs require similar algebraic structure for their interaction protocols. Putting these together with the one-way function theory of 47.06.01 shows that the cryptographic landscape is stratified: generic OWFs yield symmetric cryptography, structured assumptions yield public-key cryptography, and quantum-resistant assumptions yield post-quantum cryptography, each layer requiring more specific and more structured hardness.

Full proof set Master

Proposition 1 (RSA correctness via CRT). For $N = pq$ , $e d \equiv 1 (mod ϕ (N))$ , and any $m \in Z_{N}$ : $m^{e d} \equiv m (mod N)$ .

Proof. It suffices to show $m^{e d} \equiv m (mod p)$ and $m^{e d} \equiv m (mod q)$ , then invoke CRT.

Case 1: $p ∤ m$ . By Fermat's little theorem, $m^{p - 1} \equiv 1 (mod p)$ . Since $e d = 1 + k (p - 1) (q - 1)$ : $m^{e d} = m^{1 + k (p - 1) (q - 1)} = m \cdot (m^{p - 1})^{k (q - 1)} \equiv m \cdot 1 = m (mod p)$ .

Case 2: $p ∣ m$ . Then $m \equiv 0 (mod p)$ and $m^{e d} \equiv 0 \equiv m (mod p)$ .

Similarly for $q$ . By CRT, since $m^{e d} \equiv m$ mod both $p$ and $q$ , and $g cd (p, q) = 1$ , we have $m^{e d} \equiv m (mod pq = N)$ . $□$

Proposition 2 (DDH implies IND-CPA for ElGamal). If DDH holds in $G$ , then ElGamal encryption in $G$ is IND-CPA secure.

Proof. Consider the IND-CPA game: the adversary receives $p k = g^{x}$ and challenge ciphertext $(c_{1}, c_{2}) = (g^{r}, m_{b} \cdot g^{x r})$ .

Define hybrid $H_{0}$ : the real game with $b = 0$ . Define hybrid $H_{1}$ : replace $g^{x r}$ with $g^{s}$ for random $s$ . By DDH, $(g, g^{x}, g^{r}, g^{x r})$ and $(g, g^{x}, g^{r}, g^{s})$ are indistinguishable, so $H_{0} \approx H_{1}$ .

In $H_{1}$ , the ciphertext is $(g^{r}, m_{b} \cdot g^{s})$ where $g^{s}$ is a uniform group element independent of everything else. So $m_{b} \cdot g^{s}$ is uniformly distributed in $G$ , regardless of $b$ . The adversary's advantage in $H_{1}$ is exactly 0.

Since $H_{0}$ and $H_{1}$ are indistinguishable, the adversary's advantage in $H_{0}$ is at most negligibly more than 0. $□$

Connections Master

47.06.01 — One-way functions are the generic primitive; RSA and discrete logarithm are concrete instantiations that additionally provide the trapdoor property needed for public-key cryptography.
21.01.04 — Fermat's little theorem, Euler's theorem, and the Chinese Remainder Theorem are the number-theoretic foundations of RSA correctness.
21.01.01 — The Euclidean algorithm and Bézout's identity are used to compute the private key $d = e^{- 1} mod ϕ (N)$ .
47.06.03 — Zero-knowledge proofs use the discrete logarithm setting for Schnorr protocols and other interactive proof systems.
47.06.04 — Digital signatures use the same RSA key generation in reverse: sign with the private exponent $d$ , verify with the public exponent $e$ .

Historical & philosophical context Master

Public-key cryptography was invented independently by Diffie and Hellman (1976) and by Merkle (1975, published 1978). RSA was proposed by Rivest, Shamir and Adleman in 1977. The Diffie-Hellman key exchange was the first practical method for establishing a shared secret over an insecure channel.

Shor's 1994 discovery of a polynomial-time quantum algorithm for factoring and discrete logarithm transformed the field. It demonstrated that the security of RSA and Diffie-Hellman is conditional not just on classical hardness but on the assumption that large-scale quantum computers cannot be built. This sparked the development of post-quantum cryptography, culminating in the NIST standardisation process (2017-2024).

The philosophical significance is that security in cryptography is always relative to a computational model and a set of hardness assumptions. What is secure today may not be secure tomorrow if those assumptions are broken—by classical algorithms, quantum algorithms, or new mathematics ^{[Arora-Barak Ch. 10]}.

Bibliography Master

@book{arora2009computational,
  author    = {Arora, Sanjeev and Barak, Boaz},
  title     = {Computational Complexity: A Modern Approach},
  publisher = {Cambridge University Press},
  year      = {2009},
}
@article{rivest1978method,
  author  = {Rivest, Ronald L. and Shamir, Adi and Adleman, Leonard},
  title   = {A Method for Obtaining Digital Signatures and Public-Key Cryptosystems},
  journal = {Communications of the ACM},
  volume  = {21},
  number  = {2},
  pages   = {120--126},
  year    = {1978},
}
@article{shor1997polynomial,
  author  = {Shor, Peter W.},
  title   = {Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer},
  journal = {SIAM Journal on Computing},
  volume  = {26},
  number  = {5},
  pages   = {1484--1509},
  year    = {1997},
}
@article{diffie1976new,
  author  = {Diffie, Whitfield and Hellman, Martin E.},
  title   = {New Directions in Cryptography},
  journal = {IEEE Transactions on Information Theory},
  volume  = {22},
  number  = {6},
  pages   = {644--654},
  year    = {1976},
}
@article{regev2005lattices,
  author  = {Regev, Oded},
  title   = {On Lattices, Learning with Errors, Random Linear Codes, and Cryptography},
  journal = {Journal of the ACM},
  volume  = {56},
  number  = {6},
  year    = {2009},
}

Prerequisites

47.06.01
21.01.04
21.01.01

Tier anchors

beginner: Arora and Barak 2009 Computational Complexity: A Modern Approach (Cambridge) Ch. 10 (encrypting with a public key and decrypting with a private key using number theory)
intermediate: Arora and Barak 2009 Computational Complexity: A Modern Approach (Cambridge) Ch. 10 (RSA encryption, Diffie-Hellman key exchange, discrete logarithm problem, IND-CPA security)
master: Arora and Barak 2009 Computational Complexity: A Modern Approach (Cambridge) Ch. 10; Rivest, Shamir and Adleman 1978 A Method for Obtaining Digital Signatures and Public-Key Cryptosystems (CACM); Shor 1997 Polynomial-Time Algorithm for Prime Factorization and Discrete Logarithms (SIAM J. Comput.)

References

Arora, S. and Barak, B. — Computational Complexity: A Modern Approach · Cambridge University Press (2009). Chapter 10 develops public-key cryptography, presenting the RSA cryptosystem: choose two large primes $p, q$ , compute $N = pq$ and $ϕ (N) = (p - 1) (q - 1)$ , select $e$ coprime to $ϕ (N)$ , compute $d = e^{- 1} mod ϕ (N)$ ; the public key is $(N, e)$ and the private key is $d$ ; encryption of message $m$ is $c = m^{e} mod N$ and decryption is $m = c^{d} mod N$ , with correctness following from Euler's theorem $m^{ϕ (N)} \equiv 1 (mod N)$ giving $c^{d} = m^{e d} = m^{1 + k ϕ (N)} \equiv m (mod N)$ ; the chapter also develops the Diffie-Hellman key exchange: Alice and Bob agree on a prime $p$ and generator $g$ of $Z_{p}^{*}$ , Alice sends $g^{a} mod p$ , Bob sends $g^{b} mod p$ , and both compute the shared secret $g^{ab} mod p$ , whose security relies on the Computational Diffie-Hellman assumption (CDH) and the stronger Decisional Diffie-Hellman assumption (DDH).
Shor, P. — Polynomial-Time Algorithm for Prime Factorization and Discrete Logarithms on a Quantum Computer · SIAM Journal on Computing 26(5):1484--1509 (1997). Presents a quantum algorithm that factors $N = pq$ and computes discrete logarithms in $Z_{p}^{*}$ in time $O ((lo g N)^{3})$ , breaking RSA and Diffie-Hellman; the algorithm uses quantum Fourier sampling to find the period of the function $f (x) = a^{x} mod N$ , and the period reveals the factors of $N$ or the discrete logarithm respectively.

Estimated time

beginner: 15m
intermediate: 40m
master: 90m