What are the three main families of public-key cryptography and which "hard problem" does each rely on?
RSA → integer factorisation. Diffie-Hellman → discrete logarithm. Elliptic-Curve DH/ECDSA → discrete logarithm on elliptic curves.
| Algorithm family | Hard problem | Typical key size (for ~128-bit security) |
|---|---|---|
| RSA | Factor a big number n = p·q into its primes |
3072 bits |
| Diffie-Hellman (DH) | Given g^x mod p, recover x |
3072 bits |
| Elliptic Curve (ECDH / ECDSA) | Same as DH but in a curve group — much harder per bit | 256 bits |
Each family supports both encryption / key exchange and digital signatures:
| Use case | RSA | DH-based | EC-based |
|---|---|---|---|
| Encryption | RSA-OAEP | ElGamal | ECIES |
| Key exchange | (Rare) | DH / DHE | ECDH / ECDHE |
| Signatures | RSA-PSS | DSA / ElGamal | ECDSA / EdDSA |
Why ECC is preferred today: the discrete log on elliptic curves seems much harder per bit of key length than plain DH or RSA, so you get the same security with much shorter keys, smaller signatures, and faster operations. TLS 1.3 mandates ECDHE for key exchange.
Post-quantum note: all three families fall to Shor's algorithm on a sufficiently large quantum computer. NIST's post-quantum standards (CRYSTALS-Kyber, CRYSTALS-Dilithium, SPHINCS+, …) are based on lattices, codes, and hashes — completely different math.