Bitcoin blog

Essence of Bitcoin is innovation that may be related to remittance and asset holding rights and liberation and freedom

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.