Discrete Logarithm Problem
You'll learn why breaking Diffie-Hellman and ElGamal encryption is considered computationally infeasible.
What Is the Discrete Logarithm Problem?
In modular arithmetic (which you've already seen), it's easy to compute powers: given a base g, exponent x, and modulus p, calculating g^x mod p is straightforward and fast, even for huge numbers.
The Discrete Logarithm Problem (DLP) is the reverse: given g, p, and the result y = g^x mod p, find the unknown exponent x. This turns out to be extremely hard when the numbers are large enough.
Why This Matters for Cryptography
Remember Diffie-Hellman key exchange? Both parties compute public values like g^a mod p and share them. An eavesdropper sees g, p, g^a mod p, and g^b mod p, but to find the shared secret, they'd need to recover either a or b—which means solving the discrete logarithm problem.
There's no known efficient algorithm to solve DLP for properly chosen large primes. The best-known methods take exponential time, making brute-force attacks impractical (trying every possible exponent would take longer than the age of the universe for 2048-bit keys).
The Analogy
Think of mixing paint colors. Mixing blue and yellow to get green is easy (the "forward" direction). But given only green paint, figuring out the exact proportions of blue and yellow used is much harder—you can only guess and test. DLP is similar: computing forward is trivial; reversing it is not.
Key Takeaway: The Discrete Logarithm Problem—finding the exponent x given g^x mod p—is computationally hard for large primes, providing the security foundation for Diffie-Hellman and ElGamal cryptosystems.