# SIDH toy example¶

## Public parameters¶

In :
p = 2^8*3^5 - 1
p.is_prime()

Out:
True
In :
_.<I> = GF(p)[]
K.<i> = GF(p^2, modulus=I^2+1)
K

Out:
Finite Field in i of size 62207^2
In :
E = EllipticCurve(K, [1, 0])
E

Out:
Elliptic Curve defined by y^2 = x^3 + x over Finite Field in i of size 62207^2

## $2^8$-torsion generators¶

In :
Pa = E(0)
while (2^7)*Pa == 0:
Pa = 3^5 * E.random_point()
Pa

Out:
(37327*i + 60077 : 49881*i + 40582 : 1)
In :
Qa = Pa
while Pa.weil_pairing(Qa, 2^8)^(2^7) == 1:
Qa = 3^5 * E.random_point()
Qa

Out:
(24108*i + 33045 : 19684*i + 10186 : 1)

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

In :
Pa.order(), Qa.order(), Pa.weil_pairing(Qa, 2^8).multiplicative_order()

Out:
(256, 256, 256)

## $3^5$-torsion generators¶

In :
Pb = E(0)
while (3^4)*Pb == 0:
Pb = 2^8 * E.random_point()
Pb

Out:
(16480*i + 42988 : 39515*i + 26185 : 1)
In :
Qb = Pb
while Pb.weil_pairing(Qb, 3^5)^(3^4) == 1:
Qb = 2^8 * E.random_point()
Qb

Out:
(32542*i + 48178 : 49490*i + 54700 : 1)

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

In :
Pb.order(), Qb.order(), Pb.weil_pairing(Qb, 3^5).multiplicative_order()

Out:
(243, 243, 243)

## Alice¶

In :
Sa = randint(0, 2^8-1)
R = Pa + Sa * Qa
R

Out:
(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 :
phi = E.isogeny(R)
phi

Out:
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 :
Ea, phiPb, phiQb = phi.codomain(), phi(Pb), phi(Qb)
Ea, phiPb, phiQb

Out:
(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 :
Sb = randint(0, 3^5-1)
R = Pb + Sb * Qb
R

Out:
(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 :
psi = E.isogeny(R)
psi

Out:
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 :
Eb, psiPa, psiQa = psi.codomain(), psi(Pa), psi(Qa)
Eb, psiPa, psiQa

Out:
(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 :
Eb.isogeny(psiPa + Sa*psiQa).codomain().j_invariant()

Out:
61541*i + 35145
In :
Ea.isogeny(phiPb + Sb*phiQb).codomain().j_invariant()

Out:
61541*i + 35145

## Your turn, now: implement a real world example using¶

In :
p = 2^250 * 3^159 - 1
p.is_prime()

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