Discrete Logarithm & Diffie-Hellman
Discrete Logarithm & Diffie-Hellman
The discrete logarithm problem (DLP) — finding \(x\) such that \(g^x\equiv h\pmod{p}\) — is believed hard for large primes, forming the basis of Diffie-Hellman key exchange and the DSA signature scheme.
Definition
Discrete logarithm: given \(g, h, p\), find \(x\) with \(g^x\equiv h\pmod{p}\). Best known algorithm — General Number Field Sieve — is sub-exponential, faster than factoring, so DH parameters must be larger than RSA keys.
Key Result
Diffie-Hellman key exchange: Alice sends \(A = g^a\bmod p\), Bob sends \(B = g^b\bmod p\). Shared secret: \(K = A^b = B^a = g^{ab}\bmod p\). Eve sees only \(A,B,g,p\) and must solve the Computational Diffie-Hellman problem.
Example 1
Example: \(p=23,g=5\). Alice: \(a=6,A=5^6\bmod 23=8\). Bob: \(b=15,B=5^{15}\bmod 23=19\). Shared: \(8^{15}\bmod 23 = 19^6\bmod 23 = 2\).
Example 2
Man-in-the-middle attack: without authentication, Mallory can intercept and establish separate shared secrets with Alice and Bob. Solution: authenticated Diffie-Hellman (e.g., Station-to-Station protocol with signatures).
Loading diffie-hellman-viz...
Practice
- Explain the decisional Diffie-Hellman (DDH) assumption.
- Why are safe primes \(p = 2q+1\) recommended for DH?
- What is the index calculus algorithm for the discrete logarithm?
- Compare Diffie-Hellman over \(\mathbb{Z}_p^*\) with elliptic curve DH.
Show Answer Key
1. DDH assumption: given $(g, g^a, g^b, Z)$ in group $G$, it is computationally infeasible to distinguish whether $Z = g^{ab}$ or $Z$ is random. This is stronger than the computational DH (CDH) assumption (computing $g^{ab}$ from $g^a,g^b$ is hard). DDH implies CDH implies DLP (discrete log problem). DDH is the basis for semantic security of ElGamal encryption.
2. Safe prime $p=2q+1$ ($q$ prime): the subgroup of quadratic residues has order $q$ (prime). This prevents Pohlig-Hellman attacks, which exploit smooth (many small factors) group order. With $|\langle g\rangle| = q$ prime, the only subgroups are trivial and the full group. Also prevents small-subgroup attacks. Not strictly necessary with proper validation, but simplifies security analysis.
3. Index calculus: (1) Choose a factor base $B$ of small primes. (2) Find relations: compute $g^k\bmod p$ and check if it is $B$-smooth (factors entirely over $B$). Collect enough relations to form a linear system. (3) Solve the system modulo $q$ to find $\log_g b$ for each $b\in B$. (4) To find $\log_g h$: compute $hg^k$ until $B$-smooth, then $\log_g h = \sum\log_g b_i - k$. Complexity: subexponential $L_p(1/3)$.
4. DH over $\mathbb{Z}_p^*$: requires large primes ($\geq 2048$ bits) for security against index calculus. ECDH: no subexponential algorithm known for ECDLP → 256-bit EC keys give ~128-bit security (comparable to 3072-bit DH). ECDH advantages: much smaller keys, faster computation, lower bandwidth. ECDH is preferred for modern protocols (TLS 1.3, Signal).