Cryptography's Hidden Lock

Pick a number g, a prime p, and a secret exponent x. Computing h = gˣ mod p — multiply g by itself x times, wrapping around p — is quick and easy, even for huge numbers.

Now go the other way. I hand you g, p and h, and ask: what was x? Suddenly there's no shortcut. The values of gˣ bounce around the range 0…p unpredictably, giving you no hint whether you're close. This is the discrete logarithm problem, and like factoring, it's a one-way function: trivial forward, believed brutally hard backward.

That asymmetry is a gift to cryptography. It lets two strangers agree on a shared secret over an open line — the famous Diffie–Hellman key exchange — and underpins elliptic-curve cryptography, which protects much of today's secure web.

Try it. With base g and prime p fixed, choose a secret exponent — the demo computes h = gˣ mod p (the public value). Then hit Crack to brute-force x back, testing exponents one by one and counting steps.

<p class="hint">{{intro}}</p>
<div class="lock">
  <label>{{label_secret_x}} <b id="xv">6</b></label>
  <input id="x" type="range" min="1" max="22" value="6" />
  <div class="pub">{{label_public_h}} <b id="h">8</b></div>
  <div class="btns">
    <button id="crack" type="button">{{btn_crack}}</button>
    <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
  </div>
  <div id="out" class="out"></div>
</div>
<hr/>
<h4 class="h">{{dh_heading}}</h4>
<p class="hint">{{dh_intro}}</p>
<div class="dh">
  <div class="party">
    <div class="who">{{alice}}</div>
    <label>{{label_secret_a}} <input id="a" type="number" min="1" max="22" value="6" /></label>
    <div>{{alice_sends}}</div>
    <div>{{alice_computes}}</div>
  </div>
  <div class="party">
    <div class="who">{{bob}}</div>
    <label>{{label_secret_b}} <input id="b" type="number" min="1" max="22" value="15" /></label>
    <div>{{bob_sends}}</div>
    <div>{{bob_computes}}</div>
  </div>
</div>
<div id="shared" class="shared"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.lock label { font: 600 14px system-ui; color: #1d3557; }
input[type=range] { width: 100%; margin: .4rem 0; accent-color: #457b9d; }
.pub { font: 700 15px ui-monospace, monospace; color: #1d3557; margin: .3rem 0 .6rem; }
.pub b, .out b { color: #2a9d8f; }
.btns { display: flex; gap: .5rem; margin-bottom: .5rem; }
button { font: 600 14px system-ui, sans-serif; padding: .5rem 1rem; border: 1px solid #457b9d; background: #457b9d; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #457b9d; }
.out { font: 600 14px system-ui; min-height: 1.3em; line-height: 1.5; }
.out .steps { color: #c0392b; font-weight: 800; }
hr { border: none; border-top: 1px solid #e6e9ee; margin: 1.1rem 0; }
.h { font: 700 14px system-ui; color: #1d3557; margin: 0 0 .4rem; }
.dh { display: grid; grid-template-columns: 1fr 1fr; gap: .7rem; }
.party { border: 1px solid #e6e9ee; border-radius: 10px; padding: .7rem; font: 600 13px system-ui; color: #444; line-height: 1.7; }
.who { font-weight: 800; color: #457b9d; margin-bottom: .3rem; }
.party input { width: 4rem; font: 700 14px ui-monospace, monospace; padding: .2rem .4rem; border: 1px solid #bbb; border-radius: 6px; }
.key { color: #6d597a; }
.shared { margin-top: .7rem; font: 800 15px system-ui; min-height: 1.3em; }
.shared.ok { color: #0a7d33; } .shared.bad { color: #c0392b; }

// Code not found

For a tiny prime it's instant; the counter still shows the search is linear in the size of p, which becomes hopeless for the 600-digit primes used in practice. Below, watch a Diffie–Hellman handshake: Alice and Bob each keep a secret exponent, exchange only public powers, and arrive at the same shared key — which an eavesdropper can't compute without solving the discrete log.

The discrete logarithm sits almost exactly where factoring does:

• Verifying is trivial: given a candidate x, compute gˣ mod p and check it equals h.
• Brute force tries every exponent — linear in p, i.e. exponential in the number of digits.
• The best classical methods (index calculus and its relatives) are sub-exponential: far better than brute force, still far from polynomial. For well-chosen primes, no one can do it in reasonable time.
• It's in NP, not known to be NP-complete, and not known to be in P — its hardness is a widely held belief, not a theorem.
• Quantum breaks it. Shor's algorithm solves discrete log in polynomial time on a quantum computer, just as it factors. A large quantum machine would break Diffie–Hellman and classic elliptic-curve crypto alike.

So discrete log and factoring are twin pillars of public-key cryptography — and twin casualties of quantum computing, which is why the world is racing toward post-quantum schemes.

The discrete log quietly guards how secrets are shared online:

• Diffie–Hellman key exchange: two parties derive a shared key over a public channel — the foundation of secure sessions.
• Elliptic-curve cryptography (ECC): a discrete log over elliptic curves, giving strong security with small keys — used in TLS, SSH, and messaging apps.
• Digital signatures: DSA, ECDSA and EdDSA sign software, transactions and certificates.
• Cryptocurrencies: Bitcoin and Ethereum keys are elliptic-curve discrete-log pairs.
• HTTPS everywhere: the padlock's key agreement often rests on exactly this problem.

It is, with factoring, one of the two hard problems holding up the public-key internet.

The discrete logarithm is factoring's quieter twin: another easy-forward, hard-backward operation we've turned into a cornerstone of digital trust. Its one-way nature is the small miracle that lets two people who've never met agree on a secret while the whole world listens.

And like factoring, it carries the same asterisk. Its hardness is a belief, not a proof, and a sufficiently large quantum computer would dissolve it via Shor's algorithm. That's why both pillars are being shored up with post-quantum cryptography — so the locks keep holding even as the tools to pick them evolve.