In the previous post, we’ve mention the math behind addition law for elliptic curves over Galois Field GF(p) – prime field. Now, math behind elliptic curves over Galois Field GF(2n) – binary field would be mentioned. In literature, elliptic curves over GF(2n) are more common than GF(p) because of their adaptability into the computer hardware implementations. These type of curves are also called as Koblitz curves.
Elliptic Curves over GF(2n)
🙋♂️ You may consider to enroll my top-rated cryptography course on Udemy
Algebraically, an elliptic curve over binary field is represented as the following form:
y2 + xy = x3 + ax2 + b, (b≠0)
Negative Point
Suppose that P(x, y) is a point on the curve. The negative of the point P(x, y) is -P(x, -(x+y)), and -P is still on the curve.
Put P(m, t) and Q(m,n) into the equation y2 + xy = x3 + ax2 + b
t2 + mt = m3 + am2 + b
n2 + mn = m3 + am2 + b
Extract 2nd equation from 1st equation
t2 – n2 + mt – mn = 0
t2 + mt – n2 -mn = 0
t2 + mt – n(n + m) = 0
According to the sum and product of the roots rule, the equation could be written as:
(t – n).(t + n + m) = 0
t1 = n
t2 = – n – m = – (n+m)
We’ve already know t1=n is on the curve at the point Q(m,n). So, t2= -(n+m) is still on the curve. That’s the proof of the negative point for elliptic curves over (2n).
Proven of Addition Law
The red line would satify the equation y = ß.x + µ . Slope formula could help to calculate ß.
ß = (y1-y2)/(x1-x2) [Eq. 1]
Let’s merge the curve function (y2 + xy = x3 + ax2 + b) and linear function (y = ß.x + µ).
(ß.x + µ)2 + x.(ß.x + µ) = x3 + ax2 + b
ß2.x2 +µ2 +2ßµx + ßx2 + µx = x3 + ax2 + b
x3 + (a – ß2 – ß).x2 + (2ßµ – µ).x + (b – µ2) = 0
As mentinoned on previous post, 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 (a – ß2 – ß)2.
-(a – ß2 – ß) = x1 + x2 + x3
x3 = ß2 + ß – x1 – x2 – a [Eq. 2]
We’ve already known that P(x1, y1) is on the linear line.
y1 = ß.x1 + µ
µ = y1 – ß.x1
Also, the point -R(x3, -(x3+y3)) has to be located on the linear line y = ß.x + µ.
-(x3+y3) = ß.x3 + µ
Put the obtained µ the equation above
-(x3+y3) = ß.x3 + y1 – ß.x1
-x3 – y3 = ß.x3 + y1 – ß.x1
y3 = ß.x1 -x3 – ß.x3 – y1
y3 = ß(x1 – x3) – x3 – y1 [Eq. 3]
To sum up, addition of two point P(x1, y1) and Q(x2, y2) on the elliptic curve form y2 + xy = x3 + ax2 + b is another point on the curve which is labeled R(x3, y2) and could be computed by the following formulas.
P(x1, y1) + Q(x2, y2) = R(x3, y3)
ß = (y1-y2)/(x1-x2)
x3 = ß2 + ß – x1 – x2 – a
y3 = ß(x1 – x3) – x3 – y1
Doubling a point
Similarly, doubling a point on an elliptic curve is implemented by following principles.
The red line is tangential to the elliptic curve at the point labeled P(x1, y1). The slope of the tangent line is equal to the derivative of the elliptic curve function at the point labeled P(x1, y1).
(y2 + xy)’ = (x3 + ax2 + b)’
2y.dy + y.dx + x.dy = 3x2.dx + 2.a.x.dx
2y.dy + x.dy = 3x2.dx + 2.a.x.dx – y.dx
dy(2y + x) = dx(3x2 + 2.a.x – y)
ß = dy/dx = (3x2 + 2.a.x – y)/(2y + x)
We’ve known x1, y1 pairs are on the line. Let’s put the pairs into the slope formula.
ß = (3.(x1)2 + 2.a.x1 – y1)/(2y1 + x1)
Doubling a point on an elliptic curve over GF(2n) could be computed by the following formulas.
P(x1, y1) + P(x1, y1) = 2P(x2, y2)
ß = (3.(x1)2 + 2.a.x1 – y1)/(2y1 + x1)
x2 = ß2 + ß – 2.x1 – a
y2 = ß(x1 – x2) – x2 – y1
As metioned before, this type of elliptic curves are mostly used in cryptographic hardware implementations because of their speed and adaptability.
Python
Each elliptic curve form has its own method for constructing addition formulas. In the Weierstrass and Koblitz forms, addition involves drawing a line that intersects two points, and the reflection of the third intersection point across the x-axis gives the sum. Doubling a point requires drawing a tangent line at that point. The Edwards form, however, does not have a graphical representation for addition; instead, it relies solely on a mathematical formula that can be proven.
LightECC is a lightweight elliptic curve cryptography library for Python that simplifies ECC arithmetic. It abstracts the complexities of different curve forms, allowing users to define an elliptic curve and perform addition, subtraction, multiplication, and division of points using standard operators without needing to understand the underlying principles.
from lightecc import LightECC
# build an elliptic curve
ec = LightECC(
form_name = "koblitz", # or edwards, weierstrass.
curve_name = "k163",
)
# get the base point
G = ec.G
# addition
_2G = G + G
_3G = _2G + G
_5G = _3G + _2G
_10G = _5G + _5G
# subtraction
_9G = _10G - G
# multiplication
_20G = 20 * G
_50G = 50 * G
# division
_25G = _50G / G
You can also check out LightDSA to use digital signatures with ECDSA and EdDSA.
Support this blog if you do like!
