SIDH toy example

Public parameters

In [1]:
p = 2^8*3^5 - 1
p.is_prime()
Out[1]:
True
In [2]:
_.<I> = GF(p)[]
K.<i> = GF(p^2, modulus=I^2+1)
K
Out[2]:
Finite Field in i of size 62207^2
In [3]:
E = EllipticCurve(K, [1, 0])
E
Out[3]:
Elliptic Curve defined by y^2 = x^3 + x over Finite Field in i of size 62207^2

$2^8$-torsion generators

In [4]:
Pa = E(0)
while (2^7)*Pa == 0:
    Pa = 3^5 * E.random_point()
Pa
Out[4]:
(37327*i + 60077 : 49881*i + 40582 : 1)
In [5]:
Qa = Pa
while Pa.weil_pairing(Qa, 2^8)^(2^7) == 1:
    Qa = 3^5 * E.random_point()
Qa
Out[5]:
(24108*i + 33045 : 19684*i + 10186 : 1)

Just for checking (Sage would be too slow on real world parameters)

In [6]:
Pa.order(), Qa.order(), Pa.weil_pairing(Qa, 2^8).multiplicative_order()
Out[6]:
(256, 256, 256)

$3^5$-torsion generators

In [7]:
Pb = E(0)
while (3^4)*Pb == 0:
    Pb = 2^8 * E.random_point()
Pb
Out[7]:
(16480*i + 42988 : 39515*i + 26185 : 1)
In [8]:
Qb = Pb
while Pb.weil_pairing(Qb, 3^5)^(3^4) == 1:
    Qb = 2^8 * E.random_point()
Qb
Out[8]:
(32542*i + 48178 : 49490*i + 54700 : 1)

Just for checking (Sage would be too slow on real world parameters)

In [9]:
Pb.order(), Qb.order(), Pb.weil_pairing(Qb, 3^5).multiplicative_order()
Out[9]:
(243, 243, 243)

Alice

In [10]:
Sa = randint(0, 2^8-1)
R = Pa + Sa * Qa
R
Out[10]:
(37006*i + 60295 : 4768*i + 15927 : 1)

Warning: This computation does not use the isogeny walk algorithm, will not scale to real size parameters

In [11]:
phi = E.isogeny(R)
phi
Out[11]:
Isogeny of degree 256 from Elliptic Curve defined by y^2 = x^3 + x over Finite Field in i of size 62207^2 to Elliptic Curve defined by y^2 = x^3 + (29575*i+59258)*x + (19728*i+31732) over Finite Field in i of size 62207^2

Public data sent to Bob

In [12]:
Ea, phiPb, phiQb = phi.codomain(), phi(Pb), phi(Qb)
Ea, phiPb, phiQb
Out[12]:
(Elliptic Curve defined by y^2 = x^3 + (29575*i+59258)*x + (19728*i+31732) over Finite Field in i of size 62207^2,
 (15528*i + 37501 : 56036*i + 43649 : 1),
 (6586*i + 11442 : 54633*i + 12189 : 1))

Bob

In [13]:
Sb = randint(0, 3^5-1)
R = Pb + Sb * Qb
R
Out[13]:
(59278*i + 50914 : 1762*i + 14361 : 1)

Warning: This computation does not use the isogeny walk algorithm, will not scale to real size parameters

In [14]:
psi = E.isogeny(R)
psi
Out[14]:
Isogeny of degree 243 from Elliptic Curve defined by y^2 = x^3 + x over Finite Field in i of size 62207^2 to Elliptic Curve defined by y^2 = x^3 + (39774*i+22381)*x + (45349*i+47679) over Finite Field in i of size 62207^2

Public data sent to Alice

In [15]:
Eb, psiPa, psiQa = psi.codomain(), psi(Pa), psi(Qa)
Eb, psiPa, psiQa
Out[15]:
(Elliptic Curve defined by y^2 = x^3 + (39774*i+22381)*x + (45349*i+47679) over Finite Field in i of size 62207^2,
 (51173*i + 16345 : 1400*i + 43995 : 1),
 (54448*i + 54474 : 58859*i + 25975 : 1))

Key establishment

In [16]:
Eb.isogeny(psiPa + Sa*psiQa).codomain().j_invariant()
Out[16]:
61541*i + 35145
In [17]:
Ea.isogeny(phiPb + Sb*phiQb).codomain().j_invariant()
Out[17]:
61541*i + 35145

Your turn, now: implement a real world example using

In [18]:
p = 2^250 * 3^159 - 1
p.is_prime()
Out[18]:
True

1. Write functions to generate torsion bases

Alternatively, you can take the official basis points from the spec.

In [ ]:
 

2. Write an isogeny walk algorithm

You can either use a simple quadratic strategy using a for loop, or an advanced optimized strategy. See the spec for both.

In [ ]:
 

3. Write the key exchange functions for Alice and Bob

Do not forget to check that $j$-invariants match in the end.

In [ ]:
 

4. Optional: optimize things

  • Replace Sage's elliptic curve class with your own implementation of Montgomery curves.
  • Replace Sage's implementation of GF(p²) with your own implementation on top of Zmod(p).

Do not forget to benchmarks things to see how much you gain!

In [ ]: