The Math Behind Elliptic Curve Cryptography

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.

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)

ecc1

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.

ecc4

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.

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