Blockchain implementations such as bitcoin and Ethereum use elliptic curves to generate public and private key pairs. Elliptic curve was invented by Neal Koblitz and Victor Miller in 1985.
A 256 ECC(Elliptic curve cryptography) public key provides comparable security to a 3072-bit RSA public key.Hence, the primary advantage of using ECC is reduced key size and speed. .
Elliptic curves has nothing to do with ellipses, Ellipses are formed by quadratic curves, (X2) while elliptic c urves are formed by cubic equations (X3) .The Standard for Efficient Cryptography Group (SECG) is an international consortium to develop commercial standards for efficient and interoperable cryptography based on ECC. .
The SECG Website is https://www.secg.org .
The SECG has published a document with a recommended set of elliptic curve domain parameters, referred by the letters , {p, a, b, G, n, h}, they are collectively referred to as Elliptic curve domain parameters.
Creating digital signatures based on the math of elliptic curves is called the Elliptic Curve Digital Signing Algorithm, short ECDSA.
An elliptic curve is the set of points that satisfy a specific mathematical equation. The equation for an elliptic curve looks something like this:
y2 = x3 + ax + b
From the curve above, the elliptic curve has some interesting characteristics;
We have a curve defined by the math function
y2 = (x3 + a * x + b) mod p
a and b are constant values, and can be real numbers, integers or rational numbers. The modulo is a prime number and makes sure that all the values are within our range of 160 bits and it allows the use of “modular square root” and “modular multiplicative inverse” mathematics which make calculating stuff easier (I think). Since we have a modulo (p) , it means that the possible values of y2 are between 0 and p-1, which gives us p total possible values. However, since we are dealing with integers, only a smaller subset of those values will be a “perfect square” (the square value of two integers), which gives us N possible points on the curve where N < p (N being the number of perfect squares between 0 and p). Since each x will yield two points (positive and negative values of the square-root of y2 ), this means that there are N/2 possible ‘x‘ coordinates that are valid and that give a point on the curve. So this elliptic curve has a finite number of points on it, and it’s all because of the integer calculations and the modulus.
Assume, we want to add two points on the line, say P1(x1,y1) and P2(x2,y2)
The first step is to find the point-slope form of the line.
Then we can define the slope as
λ = ( y2 - y1)/( x2 - x1)
y- y1 = λ ( x - x1)
The slope intercept form of the line is:
y = λx - λx1 + y1
Let, µ = y1 - λx1
y = λx + µ
Then to find the coordinates of the third point (x3,y3)
Replace y in the Original equation of the curve.
y2 = x3 + ax + b
where a and b are constants
( λx + µ)2 = x3 + ax + b
After distributing and rearranging, we get the polynomial
0 = x3 - λ2x2 - 2 λx µ - µ2 + ax + b
The polynomial has 3 roots. x1, x2, x3,
And since it is a polynomial, The coefficient of x2 is the opposite sum of the roots.
x1 + x2 + x3 = λ2
x3 = λ2 - x1 - x2
We fix x3 in to our original equation and reflect it
y3 = y1 - y3 – y1
y3 = λ(x1 - x3) – y1
Algebraically,
for P + P = R = 2P
slope S = (3x2p) + a / ( 2yp)
for the x-cordinate
xr = s2 - 2xp
for the y-cordinate
yr = s(xp - xr) - yp
Why do we reflect ?
When we try to add infinity to a point. i.e adding points on a vertical line,
The third point is usually infinity.
Then find the third point of intersection
Reflect it and the result is the original point
P + ∞ = P , therefore, infinity is the identity for point addition
Inverses
Adding a point with its reflection is ∞, since they are in a straight line
P + P’ = ∞
Therefore, the reflection of a point is its inverse.
So, if we have to add a point and its reflection
P = (x, y) and -P(x, -y)
Then we can say, a point minus itself is infinity
P – P = ∞
The elliptic curve performs two major function;The addition Law, states to add two points on the curve, say A and B, we first find the line between the two points , then we find the third point of intersection X, then we reflect it to get C.
Then, a second case,The multiplication is when we want to add a point to itself, say A.
We find the tangent line, to the point
And then find the second point of intersection, then we reflect it to get 2A.
In ECC adding two vertical points, is an undefined procedure, this results to what is know as elliptic identity and commonly denoted as infinity X + C = ∞. This is because , to add two vertical points, the line does not make a third interception as explained above.
So to calculate 3A, we perform point doubling three times, so we add A to itself 3 times so we draw a line between 2A and A and where the line cuts the curve, we draw a vertical line across the x-axis and this new point is 3A. so, to perform few computations involves a lot of jumping around the curve , this is where ECC gets its strength since it is infeasible to divide the multiplication and find the specific point you multiplied to get there , unlike regular algebras. And this is known as the Elliptic Law Discrete Logarithm.
To recap, if you have a point say,
R = k*P, k(No of times P was added) . where you know R(The result of adding P , K times),
and P(The starting point of addittion). there is no way to find out what the value of ‘K‘ is. Since there is no point subtraction or point division,
you cannot just resolve k = R/P. Also, since you could be doing millions of point additions, you will just end up on another point on the curve,
and you’d have no way of knowing “how” you got there. You can’t reverse this operation, and you can’t find the value ‘k‘ which was multiplied with
your point P to give you the resulting point R.
We will discuss the part of ECC that is related to Diffie -hellman, Bitcoin Cryptography and digital signatures in the next chapter.
