Bitcoin elliptic curve calculations

Menu: crack demo curve calculator curve demo bitcoin transaction unittest
Author: Willem Hengeveld, itsme@xs4all.nl, Source: on github.

Several example calculations with the bitcoin parameters. In these calculations the following parameters are used:

p - the curve base prime field, this is used for calculations involving coordinates.
G - the fixed generator point
n - the curve group order, this is the total number of points.
x - the secret key, a value between 0 and the group order
k - the signing secret, a value between 0 and the group order
px, py - the coordinates of the public key point, values between 0 and the coordinate order
r - the first part of the signature, a value between 0 and the coordinate order
s - the first part of the signature, a value between 0 and the group order
m - the message, a value between 0 and the group order
Y - the public key

Note that in bitcoin calculations the message is the hash of the prepared transaction.
Also note that in bitcoin the s value is required to be between 0 and half the group order, you have to take the negative when it is larger.

Example, cracking a key using secret-reuse

When a signing secret was used to sign two different messages, you can recover the signing secret with this calculation:

 k = (m1-m2)/(s1-s2)

And then calculate x in the same way as in the next example.

r:

m1: s1:

m2: s2:

k: x:

Example, cracking a key using known secret

When you have cracked or otherwise guessed a signing secret for a signature, the private key is calculated like this:

x = (s*k-m)/r

k:
s:	m:
x:

Example, calculate a public key

Given the private key, you can calculate the public key like this:

Y = G * x

x:
px:	py:

Example, sign a message with a secret key

A ecdsa signature is calculated like this:

r = xcoord(G*k),  s = (m+x*r)/k

x:	k:
m:
r:	s:

Example, verify a message signature.

A ECDSA signature is verified using this calculation:

G*m+Y*r==R*s

px:	py:
r:	s:
m:
result:

Example, find pubkey.

Given a signature and messagehash, you can calculate the public key:

Y = (R*s-G*m)/r

r:	s:
m:
px:	py:
px:	py:

Example, find signing secret.

given a privatekey, message and signature, you can calculate the signing secret which was used:

k = (m+x*r)/s

r:	s:
x:
m:
k:

Example, add points.

x:	y:
x:	y:

x:	y:

Example, multiply point by a number.

x:	y:
a:
x:	y:

Example, divide point by a number.

multiply by the modular inverse in GFn

x:	y:
a:
x:	y:

Decompress a point

 y = sqrt(x^3+a*x+b)

x:
even	y:
odd	y:

You can decompress from `y` as well.

 x = cuberoot(y^2-7)

This works, because for the secp256k1 curve, 'a' is zero.

	y:
first	x:
second	x:
third	x:

Validate point.

checks that:

y² == x³+a*x+b

	result:
x:	y: