p = 2^8*3^5 - 1
p.is_prime()
True
_.<I> = GF(p)[]
K.<i> = GF(p^2, modulus=I^2+1)
K
Finite Field in i of size 62207^2
E = EllipticCurve(K, [1, 0])
E
Elliptic Curve defined by y^2 = x^3 + x over Finite Field in i of size 62207^2
Pa = E(0)
while (2^7)*Pa == 0:
Pa = 3^5 * E.random_point()
Pa
(37327*i + 60077 : 49881*i + 40582 : 1)
Qa = Pa
while Pa.weil_pairing(Qa, 2^8)^(2^7) == 1:
Qa = 3^5 * E.random_point()
Qa
(24108*i + 33045 : 19684*i + 10186 : 1)
Just for checking (Sage would be too slow on real world parameters)
Pa.order(), Qa.order(), Pa.weil_pairing(Qa, 2^8).multiplicative_order()
(256, 256, 256)
Pb = E(0)
while (3^4)*Pb == 0:
Pb = 2^8 * E.random_point()
Pb
(16480*i + 42988 : 39515*i + 26185 : 1)
Qb = Pb
while Pb.weil_pairing(Qb, 3^5)^(3^4) == 1:
Qb = 2^8 * E.random_point()
Qb
(32542*i + 48178 : 49490*i + 54700 : 1)
Just for checking (Sage would be too slow on real world parameters)
Pb.order(), Qb.order(), Pb.weil_pairing(Qb, 3^5).multiplicative_order()
(243, 243, 243)
Sa = randint(0, 2^8-1)
R = Pa + Sa * Qa
R
(37006*i + 60295 : 4768*i + 15927 : 1)
Warning: This computation does not use the isogeny walk algorithm, will not scale to real size parameters
phi = E.isogeny(R)
phi
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
Ea, phiPb, phiQb = phi.codomain(), phi(Pb), phi(Qb)
Ea, phiPb, phiQb
(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))
Sb = randint(0, 3^5-1)
R = Pb + Sb * Qb
R
(59278*i + 50914 : 1762*i + 14361 : 1)
Warning: This computation does not use the isogeny walk algorithm, will not scale to real size parameters
psi = E.isogeny(R)
psi
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
Eb, psiPa, psiQa = psi.codomain(), psi(Pa), psi(Qa)
Eb, psiPa, psiQa
(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))
Eb.isogeny(psiPa + Sa*psiQa).codomain().j_invariant()
61541*i + 35145
Ea.isogeny(phiPb + Sb*phiQb).codomain().j_invariant()
61541*i + 35145
p = 2^250 * 3^159 - 1
p.is_prime()
True
Alternatively, you can take the official basis points from the spec.
Do not forget to check that $j$-invariants match in the end.
Zmod(p)
.Do not forget to benchmarks things to see how much you gain!