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.
🙋♂️ You may consider to enroll my top-rated cryptography course on Udemy
Elliptic Curves over GF(2n)
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.
Like this blog? Support me on Patreon
