Search tools and guides ⌘K

VI · Cryptographic foundations

Discrete log

What it is

Given g and gˣ mod p, find x. Believed hard for primes ~2048-bit; very hard for elliptic curves at 256-bit.

Where it lives

Diffie-Hellman key exchange, ECDSA, Ed25519. The math behind TLS's key exchange.

The key insight

Elliptic curves give 128-bit security at 256-bit keys; classical DH needs ~3072-bit primes for the same strength.

More in Cryptographic foundations

One-way functions f(x) is easy to compute, f⁻¹(y) is computationally infeasible. The con… Birthday attack Finding any collision in an n-bit hash takes ~2^(n/2) operations, not … AEAD Authenticated Encryption with Associated Data. One operation provides …

Across the foundations

VII NP-completeness Computational complexity VII Approximation algorithms Computational complexity VII Reductions Computational complexity VIII Central Limit Theorem Statistics & inference VIII Hypothesis testing & p-values Statistics & inference VIII Confidence intervals Statistics & inference VIII Power & sample size Statistics & inference IX Eigenvalues & eigenvectors Linear algebra

← All foundations