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`

.