Subscribed unsubscribe Subscribe Subscribe

Bitcoin blog

Essence of Bitcoin is innovation that may be related to remittance and asset holding rights and 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