The Math Behind Elliptic Curves over Binary Field

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.

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.

ecc_5

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

ecc_6

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.

ecc_7

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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s