# 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 [ ]: