Public-key cryptography relies on the existence of trapdoor one-way functions—mathematical operations that are computationally efficient to evaluate in the forward direction, but computationally infeasible to invert without specific trapdoor information. Alongside integer factorization (RSA), the Discrete Logarithm Problem (DLP) forms the theoretical and practical foundation of modern asymmetric cryptography, key establishment protocols, and digital signature standards.
┌────────────────────────────────────────────────────────┐
│ Discrete Logarithm Problem │
│ Given (g, p, y), find x in: │
│ y ≡ gˣ (mod p) │
└───────────────────────────┬────────────────────────────┘
│
┌────────────────────────┬───────────────┴───────────────┬────────────────────────┐
▼ ▼ ▼ ▼
┌──────────────┐ ┌────────────────────┐ ┌────────────────────┐ ┌─────────────────┐
│ Multiplicative│ │ Diffie-Hellman │ │ ElGamal │ │ Elliptic Curves │
│ Group ℤₚ* │ │ Key Exchange │ │ Asymmetric Scheme │ │ E(𝔽ₚ) │
│ • Order p-1 │ │ • Forward Secrecy │ │ • IND-CPA Security │ │ • Chord & Tangent│
│ • Generators │ │ • CDH / DDH Proofs │ │ • Homomorphic Mult │ │ • ECDLP Hardness│
└──────────────┘ └────────────────────┘ └────────────────────┘ └─────────────────┘
For any prime $p$, the set of integers coprime to $p$ forms a finite abelian group under modular multiplication, denoted $\mathbb{Z}_p^*$:
\[\mathbb{Z}_p^* = \{1, 2, 3, \dots, p-1\}\]| Group Order: $ | \mathbb{Z}_p^* | = \phi(p) = p - 1$. |
Given a generator $g \in \mathbb{Z}p^*$, a modulus $p$, and an element $y \in \mathbb{Z}_p^*$, find the unique integer $x \in \mathbb{Z}{p-1}$ such that:
\[y \equiv g^x \pmod p\]Introduced by Whitfield Diffie and Martin Hellman in 1976, DHKE was the first published method allowing two parties to establish a shared cryptographic secret over an unencrypted, adversarial communication channel without transmitting the secret itself.
Alice (Private: a) Bob (Private: b)
───────────────────────────── ───────────────────────────
Public Parameters: (p, g) Public Parameters: (p, g)
Computes: A = gᵃ mod p ─── Public A ───► Computes: B = gᵇ mod p
◄─── Public B ───
Computes Shared Secret: Computes Shared Secret:
K = Bᵃ mod p K = Aᵇ mod p
= (gᵇ)ᵃ = gᵃᵇ mod p = (gᵃ)ᵇ = gᵃᵇ mod p
Proposed by Taher Elgamal in 1985, this scheme extended Diffie-Hellman into full public-key encryption and digital signatures.
ElGamal Encryption
Public Key: (p, g, y = gˣ mod p) Private Key: x
Sender (Alice): Receiver (Bob):
- Choose ephemeral random k - Receives (c₁, c₂)
- Compute c₁ = gᵏ mod p - Computes shared mask: s = c₁ˣ mod p
- Compute shared mask s = yᵏ mod p - Computes s⁻¹ mod p via EEA
- Compute c₂ = m · s mod p - Recovers message: m = c₂ · s⁻¹ mod p
Ciphertext: C = (c₁, c₂)
Elliptic Curve Cryptography (ECC) transfers the discrete logarithm problem from the multiplicative group $\mathbb{Z}_p^*$ to the additive group of geometric points on an algebraic curve.
Over a prime field $\mathbb{F}_p$ ($p > 3$), an elliptic curve $E(\mathbb{F}_p)$ is defined by:
\[y^2 \equiv x^3 + ax + b \pmod p\]with non-singularity condition $\Delta = 4a^3 + 27b^2 \not\equiv 0 \pmod p$, along with the point at infinity $\mathcal{O}$ acting as the identity element.
Point Addition (P ≠ Q) Point Doubling (P = Q)
y │ . (Curve) y │ . (Curve)
│ / \ │ / \
P ┼─────/───\─── Q P ┼─────* (Tangent Line)
│ / \ │ / \
│ / \ │ / \
──┼──/─────────\────── x ──┼──/─────\────── x
│ / \ │ / \
P+Q ┼* (Reflect -R) 2P ┼* (Reflect -R)
│ │
For points $P = (x_1, y_1)$ and $Q = (x_2, y_2)$:
Given a base point $P \in E(\mathbb{F}p)$ of prime order $n$ and a public point $Q = [k]P = \underbrace{P + P + \dots + P}{k \text{ times}}$, finding the scalar integer $k \in \mathbb{Z}_n$ is the ECDLP.
The required key sizes across algorithm families diverge significantly as security levels increase. Because subexponential algorithms (GNFS and Index Calculus) exist for integer factorization and finite field discrete logarithms, their moduli must grow superlinearly. In contrast, generic square-root attacks on elliptic curves allow key sizes to scale linearly ($2 \times \text{security bits}$).
| Algorithm Family | Cryptosystems | 80-bit Security (Legacy) | 128-bit Security (Standard) | 192-bit Security (High) | 256-bit Security (Top-Secret) |
|---|---|---|---|---|---|
| Integer Factorization | RSA | 1024 bit | 3072 bit | 7680 bit | 15360 bit |
| Discrete Logarithm (Finite Field) | DH, DSA, ElGamal | 1024 bit ($q \ge 160$) | 3072 bit ($q \ge 256$) | 7680 bit ($q \ge 384$) | 15360 bit ($q \ge 512$) |
| Elliptic Curves (ECDLP) | ECDH, ECDSA, Ed25519 | 160 bit | 256 bit (e.g. P-256, Curve25519) | 384 bit (P-384) | 512–521 bit (P-521, Ed448) |
| Symmetric Key (Baseline) | AES, 3DES | 80 bit (2TDEA / 3DES) | 128 bit (AES-128) | 192 bit (AES-192) | 256 bit (AES-256) |
| Mathematical Property | Multiplicative Group $\mathbb{Z}_p^*$ | Elliptic Curve Group $E(\mathbb{F}_p)$ |
|---|---|---|
| Elements | Integers ${1, 2, \dots, p-1}$ | Points $(x, y) \in \mathbb{F}_p \times \mathbb{F}_p$ plus $\mathcal{O}$ |
| Group Operation | Modular Multiplication ($a \cdot b \bmod p$) | Point Addition ($P + Q$) via Chord-and-Tangent |
| Identity Element | $e = 1$ | Point at infinity $\mathcal{O}$ |
| Inverse | $a^{-1} \pmod p$ via Extended Euclidean | $-P = (x, -y \bmod p)$ (Reflection across x-axis) |
| Repeated Operation | Exponentiation: $g^k \bmod p$ | Scalar Multiplication: $[k]P$ |
| Discrete Logarithm | Find $x$ in $y \equiv g^x \pmod p$ | Find $k$ in $Q = [k]P$ (ECDLP) |
| Best Classical Attack | Subexponential: Index Calculus ($L_p[1/3]$) | Exponential: Pollard’s $\rho$ ($\mathcal{O}(\sqrt{n})$) |
| NIST 128-bit Security Key | 3072 bits | 256 bits (Curve25519, secp256r1) |