September 17, 2018

Arithmetic on a very small elliptic curve

This document gives a detailed illustration of discrete elliptic curve mathematics. After reading this document, one should be able to carry out calculations on elliptic curves by hand. The document is broken down as follows:

  1. Introduction to a small curve and a discussion of points at infinity”
  2. Examples of adding points on elliptic curves over finite fields
  3. Demonstration of how to use sage to do basic computations on elliptic curves

For those lacking background on elliptic curves, Andrea Corbellini’s gentle introduction to elliptic curve cryptography should be read first.

Elliptic curves

In a cryptographic setting–we’ll avoid abstract mathematics for now–an elliptic curve is any polynomial equation of the form

y2=x3+Ax+B y^2 = x^3 + Ax + B y2=x3+Ax+B

Where A,BF A, B FA,BF where F F F is some field.

Bitcoin’s curve

Satoshi chose a curve called secp256k1 for Bitcoin’s elliptic curve public key cryptography. The curve has the form

y2=x3+7 y^2 = x^3 + 7 y2=x3+7

where all coefficients and arithmetic operations are over the finite field Fp,p=22564294968273Fp,p=22564294968273 (i.e. the field whose elements are the integers modulo p p p).

Same curve, different field

The field used in secp256k1 is too big for manual calculations so we’ll consider a curve over the smaller field of integers modulo 13. Any solution (x,y)(x,y) to the polynomial equation y2=x3+7 y^2 = x^3 + 7 y2=x3+7 (mod 13) are points on the elliptic curve defined by this equation. This small elliptic curve has order 7 and these are the 7 points on the curve:

{,(7,5),(7,8),(8,5),(8,8),(11,5),(11,8)} {, (7, 5), (7, 8), (8, 5), (8, 8), (11, 5), (11, 8)} {,(7,5),(7,8),(8,5),(8,8),(11,5),(11,8)}

The points of the curve form a cyclic group which implies that all points, excluding , the identity, are generators of the curve, i.e. if any of these points are repeatedly added to themselves, all points of the curve will eventually be generated. The points of the standard curve secp256k1 are also generators, again excluding .

Point at infinity

In homogeneous coordinates for projective space, the equation of our small elliptic curve becomes

y2z=x3+7z3 y^2z = x^3 + 7z^3 y2z=x3+7z3

In homogeneous coordinates, points, including points at infinity, can be represented using only finite coordinates. Absolute magnitudes do not matter; only ratios of magnitudes matter. Without loss of generality, we can normalize the last nonzero entry of coordintes (x:y:z) (x : y : z) (x:y:z) to 1. By setting z=1 z = 1 z=1 in the equation above, we get our original equation of the curve. Due to normalization, the only other option is to consider the case where z=0 z = 0 z=0.

y20=x3+70 y^2 0 = x^3 + 7 0 y20=x3+70

For this expression to hold, y y y can be any value while x x x must equal 0. Normally, we consider only a single point at infinity” with coordinates (0:1:0) (0:1:0) (0:1:0). Why these coordinates in particular? As we explained above, if z z z is nonzero, it can be normalized to 1, but when we take z=0z=0, we must have x=0 x = 0 x=0 while y can be an arbitrary integer; again, we choose to normalize y y y to 1. If we consider z z z to be in the denominator of a ratio, than the convention of division by zero producing infinity, x/0= x / 0 = x/0=, gives some intuition about why the point is considered to be at infinity”. We work in affine coordinates for the rest of this document so we’re forced to represent the point at infinity as .

Point addition on an elliptic curve over a finite field

Let P=(7,5) P = (7, 5) P=(7,5) and Q=(8,8) Q = (8, 8) Q=(8,8).

Root trick

We use the following observation in the two calculations below. Notice that when a cubic polynomial is factored each of the roots appear in the three factors. If the polynomial is expanded.

y2=(xa)(xb)(xc)=(x2(a+b)x+ab)(xc)=x3(a+b)x2+abx+cx2+c(a+b)xabc=x3(a+b+c)x2+(ab+ac+bc)xabcy2=(xa)(xb)(xc)=(x2(a+b)x+ab)(xc)=x3(a+b)x2+abx+cx2+c(a+b)xabc=x3(a+b+c)x2+(ab+ac+bc)xabc

So the coefficient of x2 x^2 x2 is the sum of the three roots of the elliptic curve.

Adding two distinct points

We solve for R=P+Q=(7,5)+(8,8) R = P + Q = (7, 5) + (8, 8) R=P+Q=(7,5)+(8,8).

First, we find the slope of the line joining the two points.

m=8587=3 m = = 3 m=8785=3

Then we find the equation of the line by substituting the coordinates of PP into the equation of a line with the slope calculated above.

y=3(x7)+5=3x163x33x+10 y = 3(x-7) + 5 = 3x - 16 3x - 3 3x + 10 y=3(x7)+5=3x163x33x+10

Now we substitute the equation of the line into the formula for the curve.

y2=(3x+10)2=9x2+60x+100=x3+7 y^2 = (3x + 10)^2 = 9x^2 + 60x + 100 = x^3 + 7 y2=(3x+10)2=9x2+60x+100=x3+7 0=x39x260x93 0 = x^3 -9x^2 - 60x - 93 0=x39x260x93

Using the root trick, 9=7+8+x15+x2+xx=7 9 = 7 + 8 + x 15 + x 2 + x x = 7 9=7+8+x15+x2+xx=7 (7 and 8 being the x-coordinates of P P P and Q Q Q). Then we substitute this value of x x x into our equation of the line.

y=3x+10=315 y = 3x + 10 = 31 5 y=3x+10=315

Finally we reflect this value for y y y to find y=58 -y = -5 8 y=58. Therefore P+Q=(7,5)+(8,8)=(7,8) P + Q = (7, 5) + (8, 8) = (7, 8) P+Q=(7,5)+(8,8)=(7,8).

Adding a point to itself

To find S=P+P S = P + P S=P+P we first calculate the tangent line to P=(7,5) P = (7, 5) P=(7,5) using implicit differentiation on the equation of the curve y2=x3+7 y^2 = x^3 + 7 y2=x3+7.

2yy=3x2y=3x22y=37225=14710=410=4(101)=44=1632yy=3x2y=2y3x2=25372=10147=104=4(101)=44=163

Then we find the equation of the line by substituting the coordinates of PP into the equation of a line with the slope (y=m y’ = m y=m) calculated above.

y=3(x7)+5=3x163x33x+10 y = 3(x-7) + 5 = 3x - 16 3x - 3 3x + 10 y=3(x7)+5=3x163x33x+10

(Note: the tangent line we found has the exact same slope as the line we found above!)

Now we substitute the equation of the line into the formula for the curve.

y2=(3x+10)2=9x2+60x+100=x3+7 y^2 = (3x + 10)^2 = 9x^2 + 60x + 100 = x^3 + 7 y2=(3x+10)2=9x2+60x+100=x3+7 0=x39x260x93 0 = x^3 -9x^2 - 60x - 93 0=x39x260x93

Using the root trick, 9=7+7+x14+x1+xx=8 9 = 7 + 7 + x 14 + x 1 + x x = 8 9=7+7+x14+x1+xx=8. Then we substitute this value of x x x into our equation of the line.

y=38+10=248 y = 3 8 + 10 = 24 8 y=38+10=248

Finally we reflect this value for y y y to find y=85 -y = -8 5 y=85. Therefore P+P=(7,5)+(7,5)=(8,5) P + P = (7, 5) + (7, 5) = (8, 5) P+P=(7,5)+(7,5)=(8,5).

Verification of results in Sage

Using sage REPL to verify our results above.

sage: F = FiniteField(13); F
>>> Finite Field of size 13
sage: E = EllipticCurve(F, [ 0, 7]); E
>>> Elliptic Curve defined by y^2 = x^3 + 7 over Finite Field of size 13
sage: E.points()
>>> [(0 : 1 : 0), (7 : 5 : 1), (7 : 8 : 1), (8 : 5 : 1), (8 : 8 : 1), (11 : 5 : 1), (11 : 8 : 1)]
sage: P = E.point((7,5)); P
>>> (7 : 5 : 1)
sage: P.order()
>>> 7
sage: Q = E.point((8,8)); Q
>>> (8 : 8 : 1)
sage: Q.order()
>>> 7
sage: P + Q
>>> (7 : 8 : 1)
sage: P + P
>>> (8 : 5 : 1)

Previous post
Keccak implementation in Haskell A Haskell programmer typically relies on for hash implementations. is exhaustive and efficient; most of its cryptographic functions are