Bitcoin

A peer-to-peer electronic cash payment system.

Created by Satoshi Nakamoto in 2008.

Zebpay(INDIA) – easy to use bitcoin wallet cum exchange

Get bitcoins worth ₹100 free on your first bitcoin buy/sell with referral code 'REF22116769'

Download the app now!

Secp256k1

From Bitcoin Wiki:

secp256k1 refers to the parameters of the ECDSA curve used in Bitcoin, and is defined in Standards for Efficient Cryptography (SEC) (Certicom Research, http://www.secg.org/sec2-v2.pdf).

As excerpted from Standards:

The elliptic curve domain parameters over Fp associated with a Koblitz curve secp256k1 are specified by the sextuple T = (p,a,b,G,n,h) where the finite field Fp is defined by:

  • p = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F
  • = 2256 - 232 - 29 - 28 - 27 - 26 - 24 - 1

The curve E: y2 = x3+ax+b over Fp is defined by:

  • a = 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
  • b = 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000007

The base point G in compressed form is:

  • G = 02 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798

and in uncompressed form is:

  • G = 04 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8

Finally the order n of G and the cofactor are:

  • n = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141
  • h = 01

The above article might be too technical for an average Joe. So, here's a recap cum simplified version:

Let's take a note of the constants first, then we'll look at the equations-

(Finite field Fp) lets call it p

p = FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F

a = 0

b = 7

G is the generator or base point. It's like a start line and has two components(co-ordinates) x and y. We'll call the x component G.x and y component G.y

G.x = 79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798

G.y = 483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8

n = FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141

Now let's try to understand what these are.

Basically, G is first point on the curve "secp256k1" defined by the parameters(p,a,b,G,n,h) and the equation y2 = x3+ax+b. As this is the first point, it corresponds to the private key "1".

p is the prime field which allows the numbers to wrap around itself when using modulus function. We will be using it to derive the public key from a given private key.

The curve equation is: y2 = x3+ax+b where, a = 0 and b = 7. Therefore, the equation can be simplified to: y2 = x3+7

Calculating public key for any private key(1 to (n-1)) requires combination of two processes: point addition and point doubling.

This is how addition of points in an elliptic curve is done: P + Q = R

Where:

P = (Px, Py); Q = (Qx, Qy); R = (Rx, Ry)

1. Point addition - when P != Q

Let slope be "m".

m = (Qy - Py) / (Qx - Px)

Rx = m2 - Px - Qx

Ry = m (Px - Rx) - Py

2. Point doubling - when P == Q

Let slope be "m".

m = (3Px2) + a / 2Py

But since, a = 0:

m = 3Px2 / 2Py

Rx = m2 - Px - Qx

Ry = m (Px - Rx) - Py

NOTE: Rx and Ry equations are same for both, point addition and doubling. Only "m" (slope) value changes.

Let's actually try to calculate the public key pair of private key 2 and 3.

We know that the public key of 1 is G

So, Public key of 2 will be G(P) + G(Q) = 2G(R). You can see that the points are in 2nd form (P == Q).

m = 3Gx2 / 2Gy NOTE: it's not regular division expression so we can't divide it like 6/2 = 3.

It can be rewritten as:

m = 3Gx2 * (1 / 2Gy) where, (1 / 2Gy) = modular multiplicative inverse of (2Gy, p)

Which means we have to find:

(1 / 2Gy) such that : (1 / 2Gy) is less than p & ((1 / 2Gy) * 2Gy) % p = 1

Here's an example from geeksforgeeks where, a => 2Gy; m => p; Output(x) => (1 / 2Gy)

  Input:  a = 3, m = 11
  Output: 4
  Since (4*3) mod 11 = 1, 4 is modulo inverse of 3
  One might think, 15 also as a valid output as "(15*3) mod 11" 
  is also 1, but 15 is not in ring {0, 1, 2, ... 10}, so not 
  valid.

  Input:  a = 10, m = 17
  Output: 12
  Since (10*12 = 120) mod 17(17x7 = 119) = 1, 12 is modulo inverse of 10

We can also get the same x by using am-2 % m

A simple method to calculate it is by using pow(a, m-2, m) function of python, which calculates (am-2 % m) efficiently since p is a very large number

Actual calculations:

For R = public key pair of private key "2"

m = 3Gx2 * ((2Gy)p-2 % p)
Rx = m2 - Gx - Gx (mod p)
Ry = m (Gx - Rx) - Gy (mod p)

For S = public key pair of private key "3"

m = (Ry - Gy) * ((Rx - Gx)p-2 % p)
Sx = m2 - Gx - Rx (mod p)
Sy = m (Gx - Sx) - Gy (mod p)

This is what a python code would look like:

#create a point class to store co-ordinates
from collections import namedtuple
Point = namedtuple("Point", "x y")
O = 'Origin'

#assign values to the variables
p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
n = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
a = 0
b = 7
G = Point(0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798, 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8)

#calculate R
m = (3 * G.x**2) * pow((2 * G.y), p-2, p)
x = ((m**2) - G.x - G.x) % p
y = (m * (G.x - x) - G.y) % p
R = Point(x, y)

#calculate S
m = (R.y - G.y) * pow((R.x - G.x), p-2, p)
x = ((m**2) - G.x - R.x) % p
y = (m * (G.x - x) - G.y) % p
S = Point(x, y)
Output:
>>> hex(R.x)
'0xc6047f9441ed7d6d3045406e95c07cd85c778e4b8cef3ca7abac09b95c709ee5'
>>> hex(R.y)
'0x1ae168fea63dc339a3c58419466ceaeef7f632653266d0e1236431a950cfe52a'
>>> hex(S.x)
'0xf9308a019258c31049344f85f89d5229b531c845836f99b08601f113bce036f9'
>>> hex(S.y)
'0x388f7b0f632de8140fe337e62a37f3566500a99934c2231b6cb9fd7584b8e672'

Zebpay(INDIA) – easy to use bitcoin wallet cum exchange

Get bitcoins worth ₹100 free on your first bitcoin buy/sell with referral code 'REF22116769'

Download the app now!