This is a read note of Programming Bitcoin Ch03: Elliptic Curve Cryptography.

1 Elliptic Curves over Finite Fields

Point addition works over finite fields. The linear equation y = mx + b and the formulas to calculate point addtion work over finite fields as well.

Point addition is nonlinear. Scalar multiplication adds a point specified times. Performing scalar multiplication is straightforward. But doing the opposite, reversing scalar multiplication, is called the discrete log problem and is not easy.

When we combine the fact that scalar multiplication is easy to do in one direction but hard in the other and the mathematical properties of a group, we have exactly what we need for elliptic curve cryptography.

Scalar multiplication looks really random, and that’s what gives this equation asymmetry. An asymmetric problem is one that’s easy to calculate in one direction, but hard to reverse.

2 Mathematical Groups

Another property of scalar multiplication is that at a certain multiple, we get to the point at infinity (the point at infinity is the additive identity or 0). If we imagine a point G and scalar-multiply until we get the point at infinity, we end up with a set: { G, 2G, 3G, 4G, ... nG } where nG = 0. It turns out that this set is called a group, and because n is finite, we have a finite group (or more specifically, a finite cyclic group). The group has properties of identity, closure, invertibility, communtativity, and associativity.

3 Bitcoin Curve

An elliptic curve for public key cryptography is defined with the following parameters:

  • We specify the a and b of the curve y ** 2 = x ** 3 + ax + b.
  • We specify the prime of the finite field, p.
  • We specify the x and y coordinates of the generator point G.
  • We specify the order of the group generated by G, n.

The parameters for secp256k1 are these:

  • a = 0, b = 7, making the equation y ** 2 = x ** 3 + 7
  • p = 2 ** 256 - 2 ** 32 - 977
  • Gx = 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
  • Gy = 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8
  • n = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141

Both p and n are close to 2 ** 256. This means that any scalar multiple can be expressed in 256 bits.

4 Public Key Cryptography

Public Key Cryptography (PKC) use the euqation P = eG, which is an asymmetric equation. We can easily compute P when we know e and G, but we cannot easily compute e when we know P and G. Generally, we call e the private key and P the public key. Note here that the private key is a single 256-bit number and the public key is a coordinate (x,y), where x and y are each 256-bit numbers. In PKC, the G and P are known.

5 Signing and Verification

The signature algorithm is called the Elliptic Curve Digital Signature Algoriht, or ECDSA for short. Here we use G, k, r, e and message hash z to calculate the signature s. It works as follows:

  • generate a 256-bit random number k, keep it private.
  • calculate a random point R = kG. Only use the x coordinate of R, which is r. r is public.
  • find a pair of numbers (u!=0, v!=0) such that uG + vP = kG. The equation means vP = (k-u)G => P = ((k-u)/v)G => eG = ((k - u) / v)G => e = (k - u) / v. This means to provide a correct u and v for the random number k, we either have to break the discrete log problem or know the secret e.
  • let z be the signature hash of the message to be signed. let u = z/s, v = r/s where s is the signature, then uG + vP = kG => uG + veG = kG => u + ve = k => z/s + re/s = k => s = (z + re) / k. Send (s, r) as the signature result.

To verify with z, r, s, G and P:

  • let u = z/s, v = r/s
  • calculate uG + vP, where the result, uG + vP = (z/s)G + (re/s)G = ((z + re)/s)G = ((z + re)/((z + re)/k))G = kG = (r,y), should give the correct r.