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)

In [ ]:
 

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.

In [ ]:
 

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.

In [ ]:
 

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.

In [ ]: