Bitcoin blog

The essence of Bitcoin is innovation that be related to remittance, asset holding rights, liberation, and freedom.

Public key

Overview
Public key indicate to destination of funds.
The public key is private key encrypted with elliptic curve cryptography.

Public key example
0458e0d3f7cd6d54347a25523dee480199e59541d849abcd4223538397ded94
e30f4f10af03bb48a1af2051c529f4ff1a84042f59a266ba028916c54570766162b

※x04 (prefix)+ 64 digits(x-coordinate) + 64 digits(y-coordinate)

Jacobi coordinates
To present elliptic curves,use to projective coordinates system instead of the affine coordinate system.
By using projective coordinate system, division operation becomes unnecessary.
Also, use the jacobian coordinate system instead of the projective coordinate system (suitab for multiplication operating)

secp256k1 parameter
"secp256k1" is parameters of the ECDSA curve used in Bitcoin.

P = 2**256 - 2**32 - 977
A = 0
B = 7
Gx = 55066263022277343669578718895168534326250603453777594175500187360389116729240
Gy = 32670510020758816978083085130507043184471273380659243275938904335757337482424
G = (Gx, Gy)


Modular multiplicative inverse
Division of modular arithmetic calculate to use modular reciprocal.

def inv(a, n):
    if a == 0:
        return 0
    lm, hm = 1, 0
    low, high = a % n, n
    while low > 1:
        r = high//low
        nm, new = hm-lm*r, high-low*r
        lm, low, hm, high = nm, new, lm, low
    return lm % n 


Jacobian coordinate
Define x, y, z as follows in elliptic curve of jacobian coordinate.

def to_jacobian(p):
    o = (p[0], p[1], 1)
    return o


Multiplication formula
In jacobian coordinate system,scalar multiplication formula in multiplication point R(X3, Y3, Z3) of point P(X1, Y1, Z1) and point Q(X2, Y2, Z2) is as follows.

s = 4*X1*Y1^2
m = 3*X1^a*Z1^4
T = -2*s + m^2

X3 = T
Y3 = -8*Y1^4 + m(s - T)
Z3 = 2*Y1*Z1

def jacobian_double(p):
    if not p[1]:
        return (0, 0, 0)
    ysq = (p[1] ** 2) % P
    S = (4 * p[0] * ysq) % P
    M = (3 * p[0] ** 2 + A * p[2] ** 4) % P
    nx = (M**2 - 2 * S) % P
    ny = (M * (S - nx) - 8 * ysq ** 2) % P
    nz = (2 * p[1] * p[2]) % P
    return (nx, ny, nz)


Addition formula
In jacobian coordinate system,addition formula in addition point R(X3, Y3, Z3) of point P(X1, Y1, Z1) and point Q(X2, Y2, Z2) is as follows.

U1 = X1*Z2^2
U2 = X2*Z1^2
S1 = Y1*Z2^3
S2 = Y2*Z1^3
H = U2 - U1
r = S2 - S1

X3 = -H^3 - 2*U1*H^2 + r^2
Y3 = -S1*H^3 + r*(U1*H^2 - X3)
Z3 = Z1*Z2*H

def jacobian_add(p, q):
    if not p[1]:
        return q
    if not q[1]:
        return p
    U1 = (p[0] * q[2] ** 2) % P
    U2 = (q[0] * p[2] ** 2) % P
    S1 = (p[1] * q[2] ** 3) % P
    S2 = (q[1] * p[2] ** 3) % P
    if U1 == U2:
        if S1 != S2:
            return (0, 0, 1)
        return jacobian_double(p)
    H = U2 - U1
    R = S2 - S1
    H2 = (H * H) % P
    H3 = (H * H2) % P
    U1H2 = (U1 * H2) % P
    nx = (R ** 2 - H3 - 2 * U1H2) % P
    ny = (R * (U1H2 - nx) - S1 * H3) % P
    nz = (H * p[2] * q[2]) % P
    return (nx, ny, nz)

Double-and-add
About multiplication of elliptic curve,the most simple way to calculation method is repeated addition.
But this calculation method not realistic,because calculation amount increase exponential.
So use to "Double-and-add" method.

def jacobian_multiply(a, n):
    if a[1] == 0 or n == 0:
        return (0, 0, 1)
    if n == 1:
        return a
    if n < 0 or n >= N:
        return jacobian_multiply(a, n % N)
    if (n % 2) == 0:
        return jacobian_double(jacobian_multiply(a, n//2))
    if (n % 2) == 1:
        return jacobian_add(jacobian_double(jacobian_multiply(a, n//2)), a)   

It's branch by remainder value obtained by dividing n to B,
「0」is executed "double(multiple)",「1」is execute "double" and "add".
Repeat until "n" became 0 or 1.



Elliptic curve coordinate of jacobian coordinate system
Coordinate(x,y) defined as following in jacobian coordinate.
x = X / Z^2
y = Y / Z^3

def from jacobian(p):
    z = inv(p[0], P)
    return ((p[0] * z**2) % P, (p[0] * Z**3) % P)


Get public key coordinate
Find coordinate(x, y) of public key, with argument "base point G" and "private key (decoded_private_key)".

def fast_multiply(a, n):
    return from_jacobian(jacobian_multiply(to_jacobian(a), n))
public_key = fast_multiply(G, decoded_private_key)
print(public_key)


Make public key
Add prefix"04" to coordinate(x, y) of public key,it's genuine " Public key".

def encode_pubkey(pub):
    return "04" + "%x"%public_key[0] + "%x"%public_key[1] 
hex_encoded_public_key = encode_pubkey(public_key)
print (hex_encoded_public_key)
Remove all ads

Elliptic curve cryptography

Overview
This article speaks about elliptic curve to base on Elliptic Curve Cryptography(ECC).

y^2=x^3+ax+b

When this equation solution equal "zero",the point connection become elliptic curve.
case of a=-1,b=1: y^2 = x^3 - x + 1
f:id:adrenaline2017:20170321224111p:plain



Finite field
In the ECC,use not rational number but finite field.
Finite field is finite of element count,and that set can arithmetic.

In case of element count is "12",finite field of order "12" is expressed to F(12).
F(12) {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}

Calculation in F(12)
1 + 5 = 6
8 + 9 = 5


Solution of elliptic curve on finite filed
ECC use solution of elliptic curve on finite filed.
Unlike elliptic curves on rational number field,
solutions are "discrete" in the case of finite fields as shown below.
f:id:adrenaline2017:20170314143427p:plain


Elliptic curve cryptography
ECC is based on discrete logarithm problem on elliptic curve.
It's not concrete cipher form names, that show general term of cryptography system used elliptic curve.
Cryptic algorithm implement elliptic curve on finite field.


Discrete logarithm problem
it's called ECDLP(Elliptic Curve Discrete Logarithm Problem)

In finite field ,Point Q equal add point d to point G in d times on elliptic curve.
f:id:adrenaline2017:20170314143505p:plain

It's easy to calculate point Q from point G and d,
reversal operation (calculate "d" from point G and Q) are too difficult.
Using this characteristic,In elliptic curve cryptography, define to point Q is encrypted and d is secret key.

Now,Let's see how to calculate by concrete elliptic curve cryptography, while looking at the code.


Modular multiplicative inverse
when calculate division in modular arithmetic,use to Modular multiplicative inverse.
Modular multiplicative inverse is calculated by using "extended Extended Euclidean algorithm" used in RSA cryptosystem.

f:id:adrenaline2017:20170316144244p:plain

def inv(a, m):
    if a == 0:
        return 0
    lm, hm = 1, 0
    low, high = a % m, m
    while low > 1:
        r = high//low
        nm, new = hm-lm*r, high-low*r
        lm, low, hm, high = nm, new, lm, low
    return lm % m    

Usually when "high" larger than "low" return "a" ,but when "low" bigger than "hight" return "a%m".
Calculate iteratively until the residue of "a%m" becomes 1 or less.


Addition of elliptic curve on finite field/b>
P1 + P2 = P3
A straight line passing through two points (P1, P2) on the curve always passes through the third point.
Also,P3(sum of P1 and P2) become place where y coordinate of third point is inverted.

f:id:adrenaline2017:20170314110727j:plain


When set P1(x1,y1),P2(x2, y2),P3(x3, y3),λ(Slope of straight line passing through P1 and P2),
following formula holds.

λ = (y2 - y1) / (x2 - x1)
x3 = λ^2 - x1 - x2
y3 = λ(x1 - x2) + y1

def EC_add(P, Q, Pcur = cP):
    Lamda = ((Q[1] - P[1]) * inv_mod(Q[0] - P[0])) % Pcur
    x = ((Lamda ** 2) - P[0] - Q[0]) % Pcur
    y = (Lamda * (P[0] - x) - P[1]) % Pcur
    return (x, y)

P1 + P1 = 2P1
A straight line passing through only one point (P1) existing on the curve as a tangent always passes through the second point.
Also, the multiple of P1 is the place where y coordinate of the second point is inverted.

f:id:adrenaline2017:20170314111952j:plain

When set P1(x1,y1),P3(x3, y3),λ(slope of straight line passing through P1),
following formula holds.
λ = (3 * x1^2 + a) / (2 * y1)
x3 = λ^2 - 2 * x1
y3 = λ(x1 - x2) + y1

def EC_double(P, Acur = cA, Pcur = cP):
    Lamda = ((3 * (P[0] ** 2) + Acur) * inv_mod(2 * P[1])) % Pcur
    x = (Lamda ** 2 - 2 * P[0]) % Pcur
    y = (Lamda * (P[0] - x) - P[1]) % Pcur
    return (x, y)

In each row is used "%Pcur(low)", because of finite field.
It use the modular multiplicative inverse "inv mod" function to divide of modular arithmetic.


Multiplication of elliptic curves over finite fields
The multiplication on the elliptic curve is defined as follows for point P and natural number d.

f:id:adrenaline2017:20170317150123j:plain

This is called scalar multiplication.
"d * P" same means P add d times.
Below code use "Duble-and-add".

def EC_mult(Scalar, Point = Gpt):
    if Scalar == 0 or Scalar >= cN:
        raise Exception("Invalid Scalar/Private Key")
    ScalarB = str(bin(Scalar))[2:]
    Q = Point
    for i in range (1, len(ScalarB)):
        Q = EC_double(Q)
        if ScalarB[i] == "1":
            Q = EC_add(Q, Point)
    return (Q)

cN is the total number of points made up of integers present on the plane on the finite field.
ScalarB gives the argument Scalar in binary notation.
Slicing the leading 0b (Binary number).
If the value of binary number is "0" execute "double",It is "1" execute "double" and "add ".


※This code used in this article refer the code of great teacher "Jonathan underwood".
※This code is compatible with python 2.x series.

Private key

Overview
One of the key pairs in public key cryptography is the private key.
Use the private key to control access to transaction.
f:id:adrenaline2017:20170307105205p:plain


Private key was chosen randomly integer (256 bit) from between 1 to p.
"p" is「2^256 - 2^32 - 2^9 - 2^8 - 2^7 - 2^6 - 2^4 - 1」.
This is the order p of the elliptic curve cryptography parameter(SECp 256 k 1) used in Bitcoin.

Private key exemple(hexadecimal,64 lines,256 bit)
5321ce1018296ca11aa51aef4d2ae7edd9c98bf3b563cad8ec9b0dd215accd7e


Module and parameter

import random
import time
import hashlib
import os

Put necessary module for random number generation.。


Decode

code_strings = {16: '0123456789abcdef'}

def decode_privkey(priv):   
    result = 0
    while len(string) > 0:
        result *= int(16)
        result += code_strings[int(16)].find(priv[0])
        prive = priv[1:]
    return result

Decode_privkey function is function of convert hex to decimal.
Calculate one each from the beginning of the argument.。
Convert to the corresponded value with code_strings.
Find addition of converted value and previous value,and move to next value.


Random number generation

def random_key():   
    entropy = str(os.urandom(32))+ str(random.randrange(2**256)) + str(int(time.time() * 1000000))
    binary_data = entropy if isinstance(entropy, bytes) else bytes(entropy, 'utf-8')
    bin_sha256 = hashlib.sha256(binary_data).digest()
    if isinstance(bin_sha256, str):
        return bin_sha256
    return ''.join('{:02x}'.format(y) for y in bin_sha256)

"random_key" function generate random number of high entropy.
os.urandom generate random n"time.time ()" get epoch seconds of the current time.
umber of 32 bit.
"random.randrange(2**256)" generate one random number from between 0 to 2^256.
"time.time ()" get epoch seconds of the current time.
Checks whether type of "entropy" is bytes, and convert it to bytes if not.
Get 256 bytes of data with SHA 256.


Private key generation

N = 115792089237316195423570985008687907852837564279074904382605163141518161494337

valid_private_key = False
while not valid_private_key:
    private_key = random_key()
    decoded_private_key = decode_privkey(private_key)
    valid_private_key = 0 < decoded_private_key < N

print (private_key) 

N= 2^256(to be accurate ,N = 2^256 - 2^32 - 2^9 - 2^8 - 2^7 - 2^6 - 2^4 - 1).
Random number generated by "random_key ()" and check whether it's between 0 and N.


The code used in this article is published in GitHub.

Remove all ads