The most of cryptography resources mention elliptic curve cryptography, but they often ignore the math behind elliptic curve cryptography and directly start with the addition formula. This approach could be very confusing for beginners. In this post, proven of the addition formula would be illustrated for Elliptic Curves over Galois Field GF(p) – prime field.
🙋♂️ You may consider to enroll my top-rated cryptography course on Udemy
Elliptic Curves over GF(p)
Basically, an Elliptic Curve is represented as an equation of the following form.
y2 = x3 + ax + b (Weierstrass Equation)
Pre-condition: 4a3 + 27b2 ≠ 0 (To have 3 distinct roots)
Addition of two points on an elliptic curve would be a point on the curve, too. Adding two points on an elliptic curve is demonstrated on the following illustration.
P(x1, y1) + Q(x2, y2) = R(x3, y3)
Negative Point
Suppose that R(x3, y3) is a point over a elliptic curve. Then, negative of R(x3, y3) is -R(x3, -y3). Because the curve is symetric about x-axis.
Proven of Addition Law
The red line would satify the equation y = ß.x + µ. Also, P(x1, y1), Q(x2, y2) and R(x3, -y3) are points on the line.
y1 = ß.x1 + µ
µ = y1 – ß.x1
y2 = ß.x2 + µ
-y3 = ß.x3 + µ
y3 = -(ß.x3 + µ)
Let’s put the obtained µ into the equation
y3 = -(ß.x3 + y1 – ß.x1)
y3 = ß.x1 – ß.x3 – y1
y3 = ß(x1 – x3) – y1 [Eq. 1]
ß would be calculated by the Slope formula.
ß = tanα = (y2 – y1) / (x2 – x1) [Eq.2]
We’ve already had the following two equations. Let’s merge them and obtain an merged equation.
y2 = x3 + ax + b
y = ß.x + µ
(ß.x + µ)2 = x3 + ax + b
ß2x2 + µ2 + 2ßµx = x3 + ax + b
x3 – ß2x2 +(a – 2ßµ).x + (b – µ2) = 0
According to the polynomial relation rule between coefficients and roots, the sum of the roots (x1, x2, x3) have to be equal to the negative coefficient of x2 , which is ß2. Proven is illustrated below.
(x-x1)(x-x2)(x-x3) = 0
(x2 -x.x2 – x.x1 + x1x2)(x-x3) = 0
(x3 -x3.x2 -x2.x2 +x2.x3.x -x1.x2 +x1.x3.x + x1.x2.x – x1.x2.x3) = 0
(x3 – (x1 + x2 + x3).x2+ (x1.x2 + x1.x3 + x2.x3).x – x1.x2.x3) = 0
So, we’ve had the following two equations:
x3 – ß2x2 +(a – 2ßµ).x + (b – µ2) = 0
x3 – (x1 + x2 + x3).x2+ (x1.x2 + x1.x3 + x2.x3).x – x1.x2.x3 = 0
Let’s compare the coefficient of the x2.
ß2 = x1 + x2 + x3
x3 = ß2 – x1 – x2 [Eq. 3]
To sum up, addition of two given points on an elliptic curve gives another point on the curve and the 3rd point could be calculated by the following formulas (proven of Eq.1, Eq. 2 and Eq. 3)
P(x1, y1) + Q(x2, y2) = R(x3, y3)
ß = (y2 – y1) / (x2 – x1)
x3 = ß2 – x1 – x2
y3 = ß(x1 – x3) – y1
Doubling a Point
Similarly, doubling a point an elliptic curve is handled by creating tangent line to the curve.
The red line is tangential to the elliptic curve at the point labeled P(x1, y1). Then, doubled point 2P(x3, y3) is symetric about x-axis of the 2nd intercept point of curve and line.
The slope of the tangent line is equal to the derivative of the elliptic curve function at the point labeled P(x1, y1).
(y2 )’ = (x3 + ax + b)’
dy.2y = dx.(3x2 + a)
ß = dy/dx = (3x2 + a)/2y
We’ve known x1, y1 pairs are on the line. When put the pairs into the slope formula, the following equation is obtained.
ß = (3.x12 + a)/2y1
To conclude, doubling a point on an elliptic curve could be calculated by the following formula.
P(x1, y1) + P (x1, y1) = 2P (x3, y3)
ß = (3.x12 + a) / 2.y1
x3 = ß2 -2.x1
y3 = ß(x1 – x3) – y1
Additionally, Bitcoin transactions are performed on a specific curve where a=0 and b=7 (y2 = x3 + 7). That is the curve called Secp256k1.
Support this blog if you do like!
3 Comments
Comments are closed.