ISE Cryptography — Reference
Elliptic Curves for Cryptography
From \(\mathbb{Z}_p^*\) to Curves
Why cryptographers moved to a new kind of group.
The Problem with \(\mathbb{Z}_p^*\)
- Diffie-Hellman and DSA originally worked in \(\mathbb{Z}_p^*\) (integers mod a prime)
- The discrete log problem in \(\mathbb{Z}_p^*\) can be attacked by the number field sieve
- Sub-exponential: runs in roughly \(e^{c \cdot (\log p)^{1/3} (\log \log p)^{2/3}}\)
- NOT \(O(\sqrt{p})\)… faster than brute force for large \(p\)
- Consequence: huge keys for moderate security
| Security level | Symmetric key | RSA / DH key | Elliptic curve key |
|---|---|---|---|
| 80-bit | 80 bits | 1024 bits | 160 bits |
| 128-bit | 128 bits | 3072 bits | 256 bits |
| 192-bit | 192 bits | 7680 bits | 384 bits |
| 256-bit | 256 bits | 15360 bits | 512 bits |
- Elliptic curves give the same security with much smaller keys
What is an Elliptic Curve?
- An elliptic curve over a field \(\mathbb{F}\) is the set of points \((x, y)\) satisfying:
- \(y^2 = x^3 + ax + b\) (short Weierstrass form)
- plus a special point at infinity \(\mathcal{O}\) (the identity element)
- The curve must be non-singular: \(4a^3 + 27b^2 \neq 0\)
- Over the reals, this is a smooth curve. Over a finite field \(\mathbb{F}_p\), it’s a scatter of discrete points.
Over a Finite Field
- In cryptography, we work over \(\mathbb{F}_p\) for a large prime \(p\)
- The curve equation \(y^2 \equiv x^3 + ax + b \pmod{p}\)
- Points are pairs \((x, y)\) with \(x, y \in \{0, \ldots, p-1\}\) satisfying the equation
- For each \(x\), either 0 or 2 values of \(y\) satisfy \(y^2 \equiv x^3 + ax + b\)
- (Plus the point at infinity \(\mathcal{O}\))
- The total number of points is approximately \(p\) (Hasse’s theorem: within \(2\sqrt{p}\) of \(p + 1\))
- Example: \(y^2 = x^3 + 2x + 3\) over \(\mathbb{F}_7\) has the points:
- \((0, 4), (0, 3), (2, 3), (2, 4), (4, 1), (4, 6), (5, 1), (5, 6)\), plus \(\mathcal{O}\)
- 9 points total (close to \(p + 1 = 8\), within Hasse bound)
The Group Law
Addition on a curve, not a number line.
Point Addition (Geometric Intuition)
- To add two points \(P\) and \(Q\) on the curve:
- Draw a line through \(P\) and \(Q\)
- The line intersects the curve at a third point \(R'\)
- Reflect \(R'\) across the \(x\)-axis to get \(R = P + Q\)
- This geometric rule translates into algebraic formulas that work over any field
Point Doubling
- To compute \(P + P = 2P\) (when \(P = Q\)):
- Draw the tangent to the curve at \(P\)
- Find where it intersects the curve at \(R'\)
- Reflect to get \(2P = -R'\)
- Special cases:
- \(P + \mathcal{O} = P\) (the point at infinity is the identity)
- \(P + (-P) = \mathcal{O}\) (a point plus its reflection gives infinity)
- \((-P)\) is just \((x, -y)\): same \(x\), negated \(y\)
- Over \(\mathbb{F}_p\): “negated \(y\)” means \(p - y \bmod p\)
Why Points Form a Group
- The set of points on an elliptic curve, with point addition, is a group:
- Closure: adding two points gives another point on the curve (or \(\mathcal{O}\))
- Associativity: \((P + Q) + R = P + (Q + R)\) (hard to prove, but true)
- Identity: the point at infinity \(\mathcal{O}\) satisfies \(P + \mathcal{O} = P\)
- Inverses: \(-P = (x, -y)\) satisfies \(P + (-P) = \mathcal{O}\)
- This is the same structure as \((\mathbb{Z}_p^*, \times)\) from the Modular Arithmetic reference
- But the operation is “point addition”, not “integer multiplication”
- The group law is “geometric”, not “arithmetic”
- We call this group \(E(\mathbb{F}_p)\), and it has \(\approx p\) elements
Scalar Multiplication
- Scalar multiplication: \(nP = P + P + \ldots + P\) (\(n\) times)
- This is the elliptic curve analogue of modular exponentiation \(g^n \bmod p\)
- Computing \(nP\) from \(n\) and \(P\) is fast: double-and-add
- Same algorithm as square-and-multiply, just with different operation names
- Write \(n\) in binary, scan left to right: double at each step, add \(P\) if bit is 1
- \(O(\log n)\) point additions instead of \(O(n)\)
- The elliptic curve discrete log problem (ECDLP):
- Given \(P\) and \(Q = nP\), find \(n\)
- Computing \(nP\) from \(n\) is easy (double-and-add). Recovering \(n\) from \(Q\) is hard.
- This is the foundation of ECDH, ECDSA, and all EC-based crypto
| Operation | Integer group (\(\mathbb{Z}_p^*\)) | Elliptic curve (\(E(\mathbb{F}_p)\)) |
|---|---|---|
| Group operation | \(a \cdot b \bmod p\) | \(P + Q\) |
| Repeated operation | \(g^n \bmod p\) | \(nP\) |
| Fast algorithm | Square-and-multiply | Double-and-add |
| Hard problem | Discrete log (DLP) | EC discrete log (ECDLP) |
Why EC Keys Are Small
The best attacks are worse, so keys can be shorter.
Best Attacks on ECDLP
- The best generic algorithm for ECDLP: Pollard’s rho
- Runs in \(O(\sqrt{q})\) where \(q\) is the group order
- For a 256-bit curve: \(\approx 2^{128}\) operations
- Unlike \(\mathbb{Z}_p^*\), there is no sub-exponential algorithm for ECDLP on well-chosen curves
- The number field sieve does not apply to elliptic curves
- This is the whole reason EC crypto exists: same security, way smaller keys
- Consequence: a 256-bit EC key provides 128-bit security
- Same security as a 3072-bit RSA key or DH group
- But 12\(\times\) smaller keys, faster operations, less bandwidth
- This is why modern protocols (TLS 1.3, Signal, WireGuard) all use elliptic curves
Post-Quantum Caveat
- Shor’s quantum algorithm solves ECDLP in polynomial time
- Both RSA and EC are broken by a sufficiently large quantum computer
- They are equally vulnerable to quantum attacks
- Post-quantum cryptography (lattice-based schemes like ML-KEM) replaces both
- But until quantum computers exist at scale, EC remains the best classical choice
- Current best practice: hybrid schemes combining EC + post-quantum
Curve25519 and X25519
The specific curve used in modern protocols.
Why Curve25519?
- Curve25519 (designed by Daniel J. Bernstein, 2006):
- Montgomery form: \(y^2 = x^3 + 486662x^2 + x\) over \(\mathbb{F}_p\), \(p = 2^{255} - 19\)
- Group order: \(\approx 2^{252}\) (provides \(\approx 126\)-bit security)
- Design goals:
- Constant-time by construction: no branches depending on secret data
- Fast: the prime \(2^{255} - 19\) enables efficient modular reduction
- Safe: no special structure that could enable future attacks
- Simple: the x-coordinate-only Montgomery ladder avoids complex point operations
- Used in TLS 1.3, SSH, Signal, WireGuard, age, and many more
X25519: The DH Function
- X25519 is Diffie-Hellman key exchange using Curve25519
- Secret key: 32 random bytes (clamped so the scalar lands in the right range)
- Public key: 32 bytes (the \(x\)-coordinate of \(n \cdot G\), where \(G\) is the base point)
- Shared secret: 32 bytes (the \(x\)-coordinate of \(n \cdot Q\))
\[ \begin{array}{lcl} \textbf{Alice} & & \textbf{Bob} \\ \alpha \xleftarrow{R} \{0,1\}^{256} & & \beta \xleftarrow{R} \{0,1\}^{256} \\ u \leftarrow \alpha \cdot G & \xrightarrow{\;u\;} & \\ & \xleftarrow{\;v\;} & v \leftarrow \beta \cdot G \\ w \leftarrow \alpha \cdot v & & w \leftarrow \beta \cdot u \end{array} \]
- Same structure as finite-field DH, but \(\cdot\) is scalar multiplication on the curve
- Both parties compute \(w = \alpha \cdot \beta \cdot G\) (the shared point)
Safe Curves
- Not all elliptic curves are created equal
- NIST P-256: widely deployed, but parameters were generated by NSA with unexplained seeds
- Curve25519: fully transparent, rigid parameter choices, independently verifiable
- The SafeCurves project evaluates curves on:
- Twist security (is the “wrong” curve also secure?)
- Constant-time ladder availability
- Rigidity (can the parameters be verified as non-manipulated?)
- Completeness (do the formulas work for all inputs?)
- Curve25519 and Curve448 pass all SafeCurves criteria
- P-256 fails several (non-rigid, incomplete addition formulas)
ECDH and ECDSA
How the group law becomes real crypto.
ECDH Key Exchange
- Elliptic Curve Diffie-Hellman follows the same pattern as finite-field DH:
- Public parameters: curve \(E\) over \(\mathbb{F}_p\), base point \(G\) of order \(q\)
- Alice picks secret \(\alpha\), publishes \(A = \alpha \cdot G\)
- Bob picks secret \(\beta\), publishes \(B = \beta \cdot G\)
- Shared secret: \(\alpha \cdot B = \beta \cdot A = \alpha \beta \cdot G\)
- Security relies on the CDH assumption for elliptic curves:
- Given \(G\), \(\alpha \cdot G\), \(\beta \cdot G\), computing \(\alpha \beta \cdot G\) is hard
- In HPKE (Lecture 08), this becomes DHKEM:
- Encapsulate: pick ephemeral \(\alpha\), send \(\alpha \cdot G\), derive key from \(\alpha \cdot B\)
- Decapsulate: use secret \(\beta\) to compute \(\beta \cdot A\), derive same key
ECDSA Signatures (Sketch)
- Elliptic Curve Digital Signature Algorithm:
- Key pair: secret \(\alpha \in \mathbb{Z}_q\), public \(A = \alpha \cdot G\)
- Sign message \(m\): pick random nonce \(k\), compute \(R = k \cdot G\), derive signature \((r, s)\) from \(R\), \(m\), \(\alpha\), \(k\)
- Verify: check that \((r, s)\) is consistent with \(A\), \(m\), and \(G\)
- The nonce \(k\) is critical: it must be unique and secret
- Reusing \(k\) leaks the secret key (Sony PS3 hack, 2010)
- Fix: deterministic nonces via RFC 6979 (\(k\) derived from secret key + message hash)
- Ed25519 (EdDSA on Curve25519) uses deterministic nonces by design
- No random nonces needed, so you can’t screw up the randomness
Notation Summary
| Notation | Meaning | Used in |
|---|---|---|
| \(E(\mathbb{F}_p)\) | Elliptic curve group over \(\mathbb{F}_p\) | Public Key Crypto |
| \(G\) | Base point (generator) of the curve group | ECDH, ECDSA |
| \(nP\) | Scalar multiplication: \(P + P + \ldots + P\) (\(n\) times) | All EC crypto |
| ECDLP | Given \(P\) and \(nP\), find \(n\) | Security assumption |
| X25519 | ECDH on Curve25519 (\(p = 2^{255} - 19\)) | TLS 1.3, Signal, HPKE |
| Ed25519 | EdDSA signatures on Curve25519 | SSH, Signal |
| CDH | Given \(\alpha G\), \(\beta G\), compute \(\alpha \beta G\) | ECDH security |