Run in Binder

Using elliptic curves and isogenies in Sage

Finite fields

We create finite fields by passing their cardinality

In [1]:
Fp = GF(11)
In [2]:
Fp
Out[2]:
Finite Field of size 11
In [3]:
Fq = GF(11^2)
Fq
Out[3]:
Finite Field in z2 of size 11^2

For extension fields, the generator is obtained with the .gen() function.

In [4]:
z = Fq.gen()
z
Out[4]:
z2
In [5]:
z^120
Out[5]:
1

Same thing in one go

In [6]:
K.<t> = GF(next_prime(2^128)^2)
K
Out[6]:
Finite Field in t of size 340282366920938463463374607431768211507^2

Elliptic curves

Curves over $ℚ$

In [7]:
E = EllipticCurve([-10,10])
E
Out[7]:
Elliptic Curve defined by y^2 = x^3 - 10*x + 10 over Rational Field
In [8]:
E.plot()
Out[8]:

Cuvers over other fields

In [9]:
F = EllipticCurve(GF(11), [1, 0])
F
Out[9]:
Elliptic Curve defined by y^2 = x^3 + x over Finite Field of size 11
In [10]:
F.order()
Out[10]:
12
In [11]:
F.cardinality()
Out[11]:
12
In [12]:
F.points()
Out[12]:
[(0 : 0 : 1), (0 : 1 : 0), (5 : 3 : 1), (5 : 8 : 1), (7 : 3 : 1), (7 : 8 : 1), (8 : 5 : 1), (8 : 6 : 1), (9 : 1 : 1), (9 : 10 : 1), (10 : 3 : 1), (10 : 8 : 1)]
In [13]:
P = F.random_point()
P
Out[13]:
(9 : 1 : 1)
In [14]:
P.order()
Out[14]:
6

Group structure

In [15]:
F.abelian_group()
Out[15]:
Additive abelian group isomorphic to Z/12 embedded in Abelian group of points on Elliptic Curve defined by y^2 = x^3 + x over Finite Field of size 11
In [16]:
g = F.gens()[0]
g
Out[16]:
(8 : 6 : 1)
In [17]:
g.order()
Out[17]:
12

Construct an isogeny with given kernel

In [18]:
origin = 6*g
origin
Out[18]:
(0 : 0 : 1)
In [19]:
F.point([0,0])
Out[19]:
(0 : 0 : 1)
In [20]:
I = F.isogeny(origin)
I
Out[20]:
Isogeny of degree 2 from Elliptic Curve defined by y^2 = x^3 + x over Finite Field of size 11 to Elliptic Curve defined by y^2 = x^3 + 7*x over Finite Field of size 11
In [21]:
I.rational_maps()
Out[21]:
((x^2 + 1)/x, (x^2*y - y)/x^2)
In [22]:
FF = I.codomain()
In [23]:
FF
Out[23]:
Elliptic Curve defined by y^2 = x^3 + 7*x over Finite Field of size 11
In [24]:
FF.abelian_group()
Out[24]:
Additive abelian group isomorphic to Z/6 + Z/2 embedded in Abelian group of points on Elliptic Curve defined by y^2 = x^3 + 7*x over Finite Field of size 11
In [25]:
FF.plot()
Out[25]:

The same example, over the rationals

In [26]:
E = EllipticCurve([1,0])
In [27]:
P = E.lift_x(0)
P
Out[27]:
(0 : 0 : 1)
In [28]:
P.order()
Out[28]:
2
In [29]:
J = E.isogeny(P)
EE = J.codomain()
EE
Out[29]:
Elliptic Curve defined by y^2 = x^3 - 4*x over Rational Field

In (very) limited cases, Sage can compute the isogeny given the image curve and the degree

In [30]:
JJ = E.isogeny(None, codomain=EE, degree=2)
In [31]:
J == JJ
Out[31]:
True

Your turn: exercices!

Diffie-Hellman

Implement the (naive) Diffie-Helman key exchange scheme with elliptic curves.

1. Find a curve of prime order

Choose a prime $p$. Take curves at random over $𝔽_p$ until you find one with prime order.

Suggestion: For a start, take $p$ of ~60 bits. When your code works well enough you can try 160 bits (it may take a few minutes to find a curve)

2. Implement the scheme

Write a function to sample secret keys, and a function to produce public keys. Perform the key exchnage and verify that Alice and Bob obtain the same key.

ECM Factoring method

Implement Lenstra's factoring method. See the lecture notes, Section 5.

Note: Sage has limited support for curves over $ℤ/Nℤ$, just enough to implement ECM.

Generating irreducible polynomials

Implement the Couveignes-Lercier method for generating irreducible polynomials. See the lecture notes, Section 8.

Note: Sage has limited support for curves over $ℤ/Nℤ$, just enough to implement ECM.