The Discrete Log Problem

Given a generator g and a value y in F_p, find x such that g^x ≡ y (mod p).

In normal arithmetic this is easy: log_2(8) = 3. Done.

In modular arithmetic, it's hard. To find x in 2^x ≡ 14 (mod 23), you essentially try every x. With p ≈ 2^256, brute force is impossible.

Diffie-Hellman key exchange uses this:

• Public: large prime p, generator g.
• Alice picks secret a. Sends A = g^a mod p.
• Bob picks secret b. Sends B = g^b mod p.
• Both compute s = g^(ab) mod p (Alice does B^a; Bob does A^b).
• Eve sees A, B but can't recover a or b without solving DLP.

DLP attacks:

• Baby-step giant-step: O(√p) time and space.
• Pollard's rho: O(√p) time, O(1) memory.
• Index calculus (subexp for special groups): hours-days for 1024-bit p with serious compute.

For ECDSA: we use EC Discrete Log Problem in elliptic curve groups, which has NO known subexponential attack. So 256-bit EC keys ≈ 3072-bit RSA in security.

This security gap is why modern crypto moved to ECDSA/Ed25519: same security, smaller keys, faster operations.