Discrete Logarithms

Discrete Logarithms

1. What Is the Problem? (beginner!)

Forward = easy: $3⁴$ mod $7 = 4$ (multiply!). Backward = HARD: find $x$ with $3^{x}$ mod $7 = 4$ (try 0,1,2,... → $x = 4$!). With 2048-bit primes, trying all is impossible — that gap IS the security (Diffie-Hellman, ElGamal, DSA live here!).

p = 7, g = 3 (primitive root — generates all 1..6!)
powers: 3⁰=1, 3¹=3, 3²=2, 3³=6, 3⁴=4, 3⁵=5, 3⁶=1 (cycle len 6!)
discrete log: log₃(4) = 4 (which power gives 4?)
forward 1 multiply; backward up to 6 tries (tiny — real: 2²⁰⁴⁸ tries!)

Tiny numbers: $p = 23$, $g = 5$, $a = 6$, $b = 15$ → $A = 8$, $B = 19$ → shared $2$ (verify: $19⁶$ mod $23 = 8¹⁵$ mod $23 = 2$!).

4. Security Notes (exam viva!)

• Prime $p$ ≥ 2048 bits; $g$ of large PRIME order (else Pohlig-Hellman + CRT attack!).
• Safe primes $p = 2q + 1$ ($q$ prime) preferred!
• NO authentication alone (man-in-the-middle! need signatures/STS!).

5. Exam Points

• Define DLP + toy log ($3^{x}$ mod $7$) — 5 marks, very frequent.
• DH steps + tiny-number key — 7 marks, favourite numerical.
• Safe-prime + MITM caveat — 3 marks, frequent.