28-06 — Elliptic Curve Cryptography

Phase: 28 — Cryptography Mathematics Subject: 28-06 Prerequisites: 28-04 (Asymmetric Encryption), 28-01 (Modular Arithmetic), basic abstract algebra Next subject: 29-01 — Direct Proof and Contrapositive

Learning Objectives

By the end of this subject, you will be able to:

1. Define elliptic curves over finite fields and understand the group law
2. Explain the Elliptic Curve Discrete Logarithm Problem (ECDLP) and why it's hard
3. Describe Elliptic Curve Diffie-Hellman (ECDH) key exchange
4. Understand Elliptic Curve Digital Signature Algorithm (ECDSA)
5. Compare ECC security with RSA for equivalent key lengths

Core Content

1. Elliptic Curves Over Finite Fields

An elliptic curve over a finite field $\mathbb{F}_p$ (prime field) is defined by:

$$y^2 = x^3 + ax + b \pmod{p}$$

with the condition $4a^3 + 27b^2 \not\equiv 0 \pmod{p}$ (non-singular).

Example: Curve secp256k1 (used by Bitcoin): $y^2 = x^3 + 7 \pmod{p}$ where $p = 2^{256} - 2^{32} - 977$.

2. The Group Law

Points on an elliptic curve form an abelian group under a geometric addition operation:

• Identity: The point at infinity $\mathcal{O}$ (analogous to 0)
• Addition: Given $P$ and $Q$, draw a line through them. It intersects the curve at a third point $-R$. Then $P + Q = R$ (reflect over x-axis).
• Doubling: $P + P = 2P$ found using the tangent line at $P$.

Algebraic formulas (for $P = (x_1, y_1)$, $Q = (x_2, y_2)$, $P \neq Q$):

$$\lambda = \frac{y_2 - y_1}{x_2 - x_1} \pmod{p}$$

$$x_3 = \lambda^2 - x_1 - x_2 \pmod{p}$$ $$y_3 = \lambda(x_1 - x_3) - y_1 \pmod{p}$$

3. Elliptic Curve Discrete Logarithm Problem (ECDLP)

Given $P$ and $Q = kP$ (point $P$ added to itself $k$ times), find $k$.

Why it's hard: No known sub-exponential algorithm exists for ECDLP on general curves (unlike the integer DLP, which has the Number Field Sieve). The best known algorithm is Pollard's Rho with $O(\sqrt{n})$ complexity.

Security implication: A 256-bit ECC key provides roughly the same security as a 3072-bit RSA key.

4. Elliptic Curve Diffie-Hellman (ECDH)

ECDH enables two parties to establish a shared secret over an insecure channel:

1. Alice picks private key $a$, computes public key $A = aG$
2. Bob picks private key $b$, computes public key $B = bG$
3. Alice computes shared secret $S = aB = abG$
4. Bob computes shared secret $S = bA = baG$
5. Both have $S$ without ever transmitting it

Security relies on ECDLP: an eavesdropper sees $A$ and $B$ but cannot compute $abG$ without solving ECDLP.

5. Elliptic Curve Digital Signature Algorithm (ECDSA)

ECDSA provides digital signatures:

Key generation: - Pick private key $d \in [1, n-1]$ where $n$ is the curve order - Public key: $Q = dG$

Signing message $m$: 1. $z = \text{hash}(m)$ (truncated to curve order bits) 2. Pick random $k \in [1, n-1]$ 3. $R = kG = (x_1, y_1)$; $r = x_1 \mod n$ (if $r = 0$, retry) 4. $s = k^{-1}(z + rd) \mod n$ (if $s = 0$, retry) 5. Signature: $(r, s)$

Verification: 1. $w = s^{-1} \mod n$ 2. $u_1 = zw \mod n$, $u_2 = rw \mod n$ 3. $X = u_1 G + u_2 Q$ 4. If $X = \mathcal{O}$, reject. Otherwise $v = x_1 \mod n$. 5. Accept if $v = r$.

Worked Examples

Example 1: Point Addition on a Small Curve

Problem: On the curve $y^2 = x^3 + 2$ over $\mathbb{F}_{11}$ with $a = 0$, compute $P + Q$ where $P = (2, 4)$ and $Q = (5, 3)$.

Solution:

$$\lambda = \frac{3 - 4}{5 - 2} = \frac{-1}{3} \pmod{11}$$

Inverse of 3 mod 11: $3 \cdot 4 = 12 \equiv 1$, so $3^{-1} = 4$.

$$\lambda = -1 \cdot 4 = -4 \equiv 7 \pmod{11}$$

$$x_3 = 7^2 - 2 - 5 = 49 - 7 = 42 \equiv 9 \pmod{11}$$ $$y_3 = 7(2 - 9) - 4 = 7(-7) - 4 = -49 - 4 = -53 \equiv 1 \pmod{11}$$

Answer: $P + Q = (9, 1)$.

Example 2: ECDH Key Exchange

Problem: On a small curve with generator $G = (3, 2)$ over $\mathbb{F}_{17}$, Alice has $a = 4$ and Bob has $b = 3$. Compute their shared secret.

Solution:

Alice's public: $A = 4G$. Compute by repeated addition: - $2G$: tangent slope $\lambda = (3x_1^2 + a) / (2y_1) = 3 \cdot 9 / 4 = 27/4 \equiv 10 \cdot 13 = 130 \equiv 14 \pmod{17}$ - Continue to find $4G = (5, 11)$

Bob's public: $B = 3G = (4, 8)$.

Alice computes: $S = aB = 4(4, 8) = (5, 6)$. Bob computes: $S = bA = 3(5, 11) = (5, 6)$.

Answer: Shared secret is $(5, 6)$. Both parties arrived at the same point.

Example 3: ECDSA Verification

Problem: Verify ECDSA signature $(r, s) = (7, 3)$ on message hash $z = 5$ using public key $Q = 3G$ where $G = (2, 5)$ over a small curve. Assume curve order $n = 11$.

Solution:

$w = s^{-1} = 3^{-1} \mod 11 = 4$ (since $3 \cdot 4 = 12 \equiv 1$).

$u_1 = zw = 5 \cdot 4 = 20 \equiv 9 \pmod{11}$ $u_2 = rw = 7 \cdot 4 = 28 \equiv 6 \pmod{11}$

$X = u_1 G + u_2 Q = 9G + 6(3G) = 9G + 18G = 27G \equiv 5G \pmod{n}$

$5G = (x_1, y_1) = (8, 2)$, so $v = x_1 \mod n = 8$.

Answer: $v = 8$, but $r = 7$. Since $v \neq r$, the signature is invalid. (This was a deliberately bad signature to show the verification process.)

Practice Problems

Problem 1: On curve $y^2 = x^3 + x + 1$ over $\mathbb{F}_{13}$, add $P = (2, 4)$ and $Q = (2, 9)$ (note: $y$ values are negatives of each other). What is $P + Q$?

Problem 2: Explain why ECDLP is considered harder than the ordinary DLP for the same key size, citing the best known algorithms for each.

Problem 3: In ECDH, if Eve learns Alice's public key $A$ and Bob's public key $B$, what must she compute to find the shared secret?

Problem 4: Why is the random $k$ in ECDSA critical? What happens if $k$ is reused or predictable?

Problem 5: Compare the security of a 256-bit ECC key with a 3072-bit RSA key. Why does ECC achieve comparable security with much smaller keys?

Summary

1. Elliptic curves over finite fields form a group under point addition, enabling public-key cryptography
2. ECDLP (finding $k$ given $P, kP$) is believed to be hard — no sub-exponential algorithm known
3. ECDH enables key exchange: both parties compute $abG$ from $aG$ and $bG$ without revealing $a$ or $b$
4. ECDSA provides digital signatures using ECDLP hardness and a per-message random $k$
5. ECC achieves RSA-equivalent security with ~10x smaller keys, making it ideal for constrained devices

Key Terms

• ECDH (Elliptic Curve Diffie-Hellman)
• ECDLP (Elliptic Curve Discrete Logarithm Problem)
• ECDSA
• Elliptic curve
• Finite field $\mathbb{F}_p$
• Group law (point addition)
• Point at infinity $\mathcal{O}$
• Pollard's Rho
• Private/public key pair
• secp256k1

Pitfalls

Quiz

1. Treating ECC like RSA. ECC operates in a totally different algebraic structure (elliptic curve groups). Don't apply RSA intuitions (factoring) to ECC security.
2. Ignoring side-channel attacks. ECC implementations are particularly vulnerable to timing attacks on scalar multiplication. Always use constant-time algorithms in production.
3. Confusing curve parameters with domain parameters. A curve is defined by (p, a, b, G, n, h). Using a curve with the wrong parameters (e.g., wrong order n) breaks security.
4. Using weak or NIST curves with suspicion. NIST curves (P-256, P-384) have generated controversy over potential NSA backdoors via opaque parameter generation. Curve25519/Curve448 are preferred for new systems.
5. Implementing ECC from scratch. Don't roll your own ECC. Use audited libraries (libsodium, BouncyCastle, OpenSSL). A single bug in point arithmetic can completely compromise keys.
6. Forgetting the cofactor h in calculations. The cofactor h = #E(F_p) / n. Some algorithms (e.g., Elliptic Curve Diffie-Hellman) need h for correct key validation.
7. Assuming ECDSA is safe without proper randomness. ECDSA requires a fresh random k for each signature. Reusing k (like the Sony PS3 exploit in 2010) reveals the private key instantly.
8. Confusing public key compression with 'lossy' compression. Compressed public keys (x + parity bit) contain all the information needed to recover y — no data is lost.

Q1: An elliptic curve over a finite field $\mathbb{F}_p$ is defined by:

A) $y = mx + c$ B) $y^2 = x^3 + ax + b$ with $4a^3 + 27b^2 \not\equiv 0 \pmod{p}$ C) $x^2 + y^2 = r^2$ D) $y = x^2$

Correct: B)

• If you chose B: Correct. This is the Weierstrass form for elliptic curves over finite fields.
• If you chose A: That's a line, not an elliptic curve.
• If you chose C: That's a circle (or ellipse over reals), not an elliptic curve.
• If you chose D: That's a parabola.

Q2: The identity element for the elliptic curve group is:

A) The origin $(0, 0)$ B) The point at infinity $\mathcal{O}$ C) The point $(1, 1)$ D) There is no identity element

Correct: B)

• If you chose B: Correct. The point at infinity $\mathcal{O}$ is the identity. Adding any point to $\mathcal{O}$ returns that point.
• If you chose A: $(0, 0)$ is not special on most curves. The identity is the point at infinity.
• If you chose C: $(1, 1)$ is just a regular point (if it lies on the curve).
• If you chose D: The curve points do form a group, so an identity must exist.

Q3: ECDLP is considered hard because:

A) No algorithm faster than $O(2^{n/2})$ is known (Pollard's Rho), unlike the integer DLP which has sub-exponential algorithms B) It is provably impossible C) Computers are too slow D) The keys are always secret

Correct: A)

• If you chose A: Correct. ECDLP's best known algorithm is Pollard's Rho at $O(\sqrt{n})$. The integer DLP has the Number Field Sieve at sub-exponential $O(e^{(c+o(1))(\log n)^{1/3}(\log\log n)^{2/3}})$.
• If you chose B: "Provably impossible" is a very high bar in complexity theory. We believe it's hard based on decades of research, but have no proof.
• If you chose C: Even with fast computers, $O(2^{128})$ operations is infeasible.
• If you chose D: The keys are public. The hardness comes from the mathematical structure, not secrecy of keys.

Q4: In ECDH, the shared secret computed by both parties is:

A) $a + b$ B) $abG$ (the same point computed via different paths) C) $aG + bG$ D) The concatenation of public keys

Correct: B)

• If you chose B: Correct. Alice computes $a(bG) = abG$ and Bob computes $b(aG) = abG$. Both arrive at the same point.
• If you chose A: Addition is not the group operation here. The group operation is point addition, not scalar addition.
• If you chose C: $aG + bG = (a+b)G$ is NOT the same as $abG$ (unless $a+b = ab$, which is rare).
• If you chose D: Concatenation doesn't give a shared secret; it just combines public information.

Q5: ECDSA requires a fresh random $k$ per signature because:

A) Using the same $k$ twice reveals the private key B) $k$ determines the curve parameters C) Without $k$, the signature is too short D) $k$ is the public key

Correct: A)

• If you chose A: Correct. If the same $k$ is used for two messages with hashes $z_1, z_2$ and signatures $(r, s_1), (r, s_2)$, then $s_1 - s_2 = k^{-1}(z_1 - z_2)$, revealing $k$, and then the private key $d$.
• If you chose B: $k$ is a per-signature nonce, not a curve parameter.
• If you chose C: Signature length is determined by the curve order, not $k$.
• If you chose D: The public key is $Q = dG$, not $k$.

Q6: A 256-bit ECC key provides roughly equivalent security to:

A) A 256-bit RSA key B) A 1024-bit RSA key C) A 3072-bit RSA key D) A 512-bit RSA key

Correct: C)

• If you chose C: Correct. NIST estimates: 128-bit security (ECC 256) ≈ 3072-bit RSA. ECC's $O(\sqrt{n})$ attack vs RSA's sub-exponential NFS attack.
• If you chose A: 256-bit RSA is trivially breakable. ECDLP on 256 bits requires ~$2^{128}$ operations.
• If you chose B: 1024-bit RSA is considered weak. ECC 256 is far stronger.
• If you chose D: 512-bit RSA is extremely weak.

Q7: The "point at infinity" $\mathcal{O}$ in elliptic curve arithmetic serves as:

A) The generator point $G$ B) The identity element (analogous to 0 in addition) C) The maximum possible point D) An invalid point that should be avoided

Correct: B)

• If you chose B: Correct. $\mathcal{O}$ is the identity of the group: $P + \mathcal{O} = P$ for all $P$. It arises from projective geometry.
• If you chose A: The generator $G$ is a specific, publicly known point. $\mathcal{O}$ is different.
• If you chose C: There is no "maximum" point on a finite field curve — all points are equally valid.
• If you chose D: $\mathcal{O}$ is a valid group element, not an error. It appears when adding $P$ and $-P$.

Q8: Which curve does Bitcoin use for its signatures?

A) Curve25519 B) secp256k1 C) NIST P-256 D) secp224k1

Correct: B)

• If you chose B: Correct. Bitcoin uses secp256k1 ($y^2 = x^3 + 7$ over $\mathbb{F}_p$ with $p = 2^{256} - 2^{32} - 977$).
• If you chose A: Curve25519 is used in Signal, TLS 1.3, and many other applications, but not Bitcoin.
• If you chose C: NIST P-256 is a NIST standard curve used in many applications, but Bitcoin chose secp256k1.
• If you chose D: secp224k1 is a 224-bit curve, too small for Bitcoin's security requirements.

Next Steps

You have completed Phase 28 (Cryptography Mathematics). Moving to 29-01 — Direct Proof and Contrapositive to begin Phase 29 (Proof Techniques) with foundational proof methods used throughout mathematics.