# Supersingular Isogeny Elliptic Curve Cryptography

Before we start, let's be clear: this is an experiment to demo isogeny-based DH, it is not secure or fast (at least it wouldn't be with reasonably-sized fields)!

We pick a supersingular curve over a small prime field:

lA, lB = 2, 3 eA, eB = 6, 7 p = lA ^ eA * lB ^ eB - 1 # This is conveniently a large-ish curve for a demo (comically small for crypto, though!); this structure doesn't matter much because we do math over GF(p), not GF(p^2) assert p.is_prime() assert p % 4 == 3 # Necessary for below curve to be supersingular.
k = GF(p) # Note; not using GF(p^2) because of a limitation in Sage E = EllipticCurve(k, [1, 0]) E
 ```Elliptic Curve defined by y^2 = x^3 + x over Finite Field of size 139967```

Elliptic curves of this form with a prime congruent to 3 mod 4 will incidentally always be supersingular, but Sage will confirm that:

E.is_supersingular()
 `True`
n_points = E.count_points() n_points
 `139968`
E.j_invariant()
 `1728`

Let's pick 4 random unique points, fixed as part of the protocol:

points = [] while len(points) != 4: p = E.random_point() if p not in points: points.append(p) PA, PB, QA, QB = points PA, PB, QA, QB
 ```((52145 : 122183 : 1), (122248 : 66260 : 1), (22354 : 13937 : 1), (111386 : 102821 : 1))```

Alice computes her secret numbers, from which she computes a point RA, which defines the kernel of her isogeny:

mA, nA = 123, 525 RA = mA * PA + nA * QA print RA
 `(42052 : 45422 : 1)`

Sage has convenient tools for proving that this is an isogeny:

E.is_isogenous(EA)
 `True`

Alice sends her public key (consisting of the isogenous elliptic curve and the two base points for Bob under that curve) to Bob. I use the symbols phiA_PB and phiA_QB here to clarify that Bob just sees those values; he does not actually see the isogeny itself.

EA, phiA_PB, phiA_QB = EA, phiA(PB), phiA(QB) EA, phiA_PB, phiA_QB
 ```(Elliptic Curve defined by y^2 = x^3 + 91219*x + 72262 over Finite Field of size 139967, (107172 : 121677 : 1), (42404 : 0 : 1))```

Sage gives us convenient tools for checking our work:

phiA = E.isogeny(RA) print phiA EA = phiA.codomain() print EA
 ```Isogeny of degree 7776 from Elliptic Curve defined by y^2 = x^3 + x over Finite Field of size 139967 to Elliptic Curve defined by y^2 = x^3 + 91219*x + 72262 over Finite Field of size 139967 Elliptic Curve defined by y^2 = x^3 + 91219*x + 72262 over Finite Field of size 139967```

Bob does the same thing:

# Bob does the same thing mB, nB = 812, 580 RB = mB * PB + nB * QB print RB # phiB is a function from points on E to points on EB phiB = E.isogeny(RB) print phiB EB = phiB.codomain() print EB
 ```(112221 : 17506 : 1) Isogeny of degree 11664 from Elliptic Curve defined by y^2 = x^3 + x over Finite Field of size 139967 to Elliptic Curve defined by y^2 = x^3 + 86786*x + 16746 over Finite Field of size 139967 Elliptic Curve defined by y^2 = x^3 + 86786*x + 16746 over Finite Field of size 139967```
E.is_isogenous(EB)
 `True`
# Bob sends to Alice: EB, phiB_PA, phiB_QA = EB, phiB(PA), phiB(QA) EB, phiB_PA, phiB_QA
 ```(Elliptic Curve defined by y^2 = x^3 + 86786*x + 16746 over Finite Field of size 139967, (82090 : 7459 : 1), (70660 : 33062 : 1))```
# Alice computes the shared secret: SBA = mA * phiB_PA + nA * phiB_QA print SBA phiBA = EB.isogeny(SBA) print phiBA KA = phiBA.codomain().j_invariant()
 ```(12132 : 0 : 1) Isogeny of degree 2 from Elliptic Curve defined by y^2 = x^3 + 86786*x + 16746 over Finite Field of size 139967 to Elliptic Curve defined by y^2 = x^3 + 130855*x + 32368 over Finite Field of size 139967```
# Bob computes the shared secret: SAB = mB * phiA_PB + nB * phiA_QB print SAB phiAB = EA.isogeny(SAB) print phiAB KB = phiAB.codomain().j_invariant()
 ```(107172 : 18290 : 1) Isogeny of degree 3 from Elliptic Curve defined by y^2 = x^3 + 91219*x + 72262 over Finite Field of size 139967 to Elliptic Curve defined by y^2 = x^3 + 130855*x + 32368 over Finite Field of size 139967```
KA == KB
 `True`