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:
- Introduction to a small curve and a discussion of “points at infinity”
- Examples of adding points on elliptic curves over finite fields
- 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
Where A,B∈F and 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
where all coefficients and arithmetic operations are over the finite field Fp,p=2256−4294968273 (i.e. the field whose elements are the integers modulo 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) to the polynomial equation 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)}
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
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) to 1. By setting 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.
y2⋅0=x3+7⋅0
For this expression to hold, y can be any value while x must equal 0. Normally, we consider only a single “point at infinity” with coordinates (0:1:0). Why these coordinates in particular? As we explained above, if z is nonzero, it can be normalized to 1, but when we take z=0, we must have x=0 while y can be an arbitrary integer; again, we choose to normalize y to 1. If we consider z to be in the denominator of a ratio, than the convention of division by zero producing infinity, 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) and 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=(x−a)(x−b)(x−c)=(x2−(a+b)x+ab)(x−c)=x3−(a+b)x2+abx+cx2+c(a+b)x−abc=x3−(a+b+c)x2+(ab+ac+bc)x−abc
So the coefficient of 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).
First, we find the slope of the line joining the two points.
m=8−78−5=3
Then we find the equation of the line by substituting the coordinates of P into the equation of a line with the slope calculated above.
y=3(x−7)+5=3x−16≡3x−3≡3x+10
Now we substitute the equation of the line into the formula for the curve.
y2=(3x+10)2=9x2+60x+100=x3+7 ⟹0=x3−9x2−60x−93
Using the root trick, 9=7+8+x≡15+x≡2+x⟹x=7 (7 and 8 being the x-coordinates of P and Q). Then we substitute this value of x into our equation of the line.
y=3x+10=31≡5
Finally we reflect this value for y to find −y=−5≡8. Therefore P+Q=(7,5)+(8,8)=(7,8).
Adding a point to itself
To find S=P+P we first calculate the tangent line to P=(7,5) using implicit differentiation on the equation of the curve y2=x3+7.
2yy′=3x2⟹y′=2y3x2=2⋅53⋅72=10147=104=4(10−1)=4⋅4=16≡3
Then we find the equation of the line by substituting the coordinates of P into the equation of a line with the slope (y′=m) calculated above.
y=3(x−7)+5=3x−16≡3x−3≡3x+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 ⟹0=x3−9x2−60x−93
Using the root trick, 9=7+7+x≡14+x≡1+x⟹x=8. Then we substitute this value of x into our equation of the line.
y=3⋅8+10=24≡8
Finally we reflect this value for y to find −y=−8≡5. Therefore 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)