Number Theory

Elliptic Curves

A Bitcoin private key is a random 256-bit number k. The public key is the point kG on the curve secp256k1: y^2 = x^3 + 7. The entire security of the system rests on the fact that the discrete-logarithm problem on this curve requires 2^128 operations. Behind every crypto transaction sits algebraic geometry.

  • Bitcoin / Ethereum: ECDSA on secp256k1 protects transactions worth hundreds of billions of dollars
  • TLS 1.3: ECDH key exchange on the P-256 curve underpins HTTPS connections
  • Signal, WhatsApp: X25519 - ECDH on Curve25519 for message encryption
  • SSH: Ed25519 signatures on an elliptic curve in modern SSH clients
  • Passports and chip cards: ECDSA in EMV chip cards
  • Post-quantum cryptography: elliptic-curve isogenies - the SIKE algorithm

y^2 = x^3 + 7. That is the curve secp256k1. A Bitcoin private key is a random 256-bit number k. The public key is the point kG on this curve. The entire security of the system rests on one fact: finding k from G and kG requires 2^128 operations. The geometry of algebraic curves sits behind every transaction.

**What this lesson is really about**: the points on the curve form a group - a non-obvious fact. Algebraic geometry produces the group, number theory over finite fields produces computability, the ECDLP produces security. Three layers, one cryptosystem.

Real curves in production

ECDSA: digital signature

**Elliptic curves in modern systems** From math to production security - TLS 1.3: ECDHE for key exchange. Default: Curve25519 (X25519). Each HTTPS connection: two key pairs, ECDH, shared secret. Perfect forward secrecy: new keys per session. - Bitcoin / Ethereum: ECDSA for transactions. secp256k1. Private key = 32 bytes. Public key = 64 bytes (x, y). Address = Hash160(publicKey). ~400,000 transactions per day need ECDSA verification. - Signal / WhatsApp: X3DH plus Double Ratchet. X3DH (Extended Triple DH): 3 ECDH exchanges for forward secrecy and future secrecy. Curve25519. Double Ratchet rotates keys after each message. - SSH / GPG / JWT: Ed25519 for authentication. EdDSA (Ed25519) is faster than ECDSA, immune to k-reuse, and constant-time. GitHub keys, SSH keys, JWT tokens.

0

1

Sign In

Elliptic curves: a group built from geometry

Bitcoin uses the secp256k1 curve: y^2 = x^3 + 7 over the field Fp, with p = 2^256 - 2^32 - 977. A private key is a random number k (256 bits). The public key is the point kG on the curve, where G is a fixed base point. **Every Bitcoin transaction is a multiplication of a point on the curve by a 256-bit number.** The inverse problem (recover k from kG) is computationally infeasible.

Why does the definition of an elliptic curve require Delta = -16(4a^3 + 27b^2) != 0? What happens when Delta = 0?

Group law: chord and tangent

The group of points of an elliptic curve is an algebraic structure defined geometrically. To add P + Q: draw the line through P and Q, find the third intersection with the curve, reflect across the x-axis. The neutral element is the 'point at infinity' O. This is not an arbitrary choice: it is the definition that makes the set of points an abelian group.

**Lagrange's theorem for elliptic curves:** the order of any point P divides #E(Fp). For cryptography we want a prime n = #E (or of a subgroup): then every nontrivial point is a generator. secp256k1: #E = n is prime, around 2^256. The group is cyclic of order n.

What is the neutral element of the group E(Fp)? What is -P for the point P = (x, y) on y^2 = x^3 + ax + b?

Scalar multiplication and ECDLP

Double-and-add: compute kP in O(log k) operations - fast. Recovering k from G and kG is the **ECDLP (Elliptic Curve Discrete Logarithm Problem)** - computationally infeasible for cryptographic parameters. The best algorithm, Pohlig-Hellman-Pollard, requires about sqrt(n) operations: at n ~ 2^256 that is 2^128 - out of reach. For RSA the best algorithms are sub-exponential, which is why a 256-bit ECC key matches RSA-3072 in strength.

Why is kP computed in O(log k), while ECDLP (find k from G and kG) takes about sqrt(n) operations?

ECDH, ECDSA, and real-world curves

Signal Messenger, WhatsApp, iMessage all use X25519 (ECDH on Curve25519) for perfect forward secrecy. Bitcoin and Ethereum use secp256k1 for transaction signatures. TLS 1.3 uses ECDHE with Curve25519 or secp256r1. **Every HTTPS connection uses ECDH several times.** Together, elliptic curves protect trillions of dollars per second.

**Curve25519** (Bernstein, 2006) was designed for security: Montgomery form y^2 = x^3 + 486662 x^2 + x over F_{2^255 - 19}. Key properties: (1) every point is safe for scalar multiplication (no cofactor issues), (2) no known weak keys, (3) constant-time implementations to thwart side-channel attacks. **Ed25519** is the signature variant (EdDSA).

**secp256k1 vs secp256r1:** Bitcoin chose secp256k1 (Certicom) rather than the standard secp256r1 (NIST). The reason: suspicions that secp256r1's parameters contain an NSA backdoor (recall Dual_EC_DRBG). secp256k1 has structured parameters (a=0, b=7) that do not look arbitrary.

Describe the ECDH protocol. Why can an attacker who knows G, A = aG, and B = bG not compute the shared secret abG without knowing a or b?

CurveEquationFieldUse
secp256k1y^2 = x^3 + 7F_{2^256 - 2^32 - 977}Bitcoin, Ethereum
Curve25519y^2 = x^3 + 486662 x^2 + x (Montgomery)F_{2^255 - 19}Signal, TLS 1.3, WireGuard
Ed25519twisted Edwards curveF_{2^255 - 19}SSH, JWT, Telegram
secp256r1 (P-256)y^2 = x^3 - 3x + b (NIST)F_p (NIST)TLS, ECDSA in browsers
secp384r1similar form384-bit fieldgovernment systems

Parameters: curve E, generator G, order n, hash H Key generation: d = random.randint(1, n-1) # private Q = d*G # public Signing a message m: k = random.randint(1, n-1) # random, SECRET R = k*G = (r, _) # r = x-coordinate s = k^{-1} * (H(m) + d*r) mod n sig = (r, s) Verification (know Q, m, sig = (r, s)): u1 = H(m) * s^{-1} mod n u2 = r * s^{-1} mod n R' = u1*G + u2*Q r' = R'.x mod n Signature valid iff r' == r Security: k must be DIFFERENT for every signature! Sony PlayStation 3 was broken precisely because k was constant across signatures.

Упражнения

  1. Why does ECC with a 256-bit key give the same security as RSA with 3072 bits? — RSA: General NFS - a sub-exponential factoring algorithm; ECDLP: only Pollard's rho (~sqrt(n) = 2^128 for n ~ 2^256); 128-bit security = 2^128 operations to break; Match: 256-bit ECC = 3072-bit RSA = 128 bits of security
  2. What happens in ECDSA if you use the same k for two different signatures? — Two signatures (r, s_1) and (r, s_2) with the same r = k * G.x; s_1 - s_2 = k^{-1} (H(m_1) - H(m_2)), so k = (H(m_1) - H(m_2)) / (s_1 - s_2) mod n; Knowing k: d = (s_1 k - H(m_1)) / r mod n - the private key is exposed; Sony PS3: k was constant for all firmware signatures, broken in 1 hour

Key ideas

  • E: y^2 = x^3 + ax + b over Fp, Delta != 0; points form an abelian group with neutral element O
  • Addition P + Q: chord slope lambda = (y_2 - y_1) / (x_2 - x_1), x_3 = lambda^2 - x_1 - x_2, y_3 = lambda(x_1 - x_3) - y_1
  • Hasse's theorem: |#E(Fp) - (p+1)| <= 2 sqrt(p); for p ~ 2^256: #E ~ 2^256
  • Double-and-add: kP in O(log k) operations; ECDLP (k from G, kG): ~2^128 for 256 bits
  • ECDH: shared secret abG; ECDSA: signature (r, s); Ed25519: no k-reuse vulnerability
  • secp256k1 (Bitcoin), Curve25519 (Signal / TLS), Ed25519 (SSH) - the three main curves

Related topics

Elliptic curves bring together algebraic geometry, number theory, and cryptography

  • p-adic numbers — Curves over Qp; Hensel's lemma for finding curve points
  • Fermat's last theorem - Wiles — The Frey curve y^2 = x(x - a^n)(x + b^n) is the central object of the FLT proof
  • Quadratic residues — Checking whether y^2 is a quadratic residue mod p is the basic curve operation

Связанные уроки

  • aa-05-fields
Elliptic Curves