Course contentsShow
← Computer Science
Lesson 2412 of 2,87254. Cryptography FundamentalsFree lesson

Discrete Logarithm Problem

The hard mathematical problem underlying Diffie-Hellman and ElGamal security guarantees.

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.