Skip to content

Instantly share code, notes, and snippets.

@asanso
Last active December 19, 2022 15:39
Show Gist options
  • Save asanso/e08430be25456023e152f28c216a68bf to your computer and use it in GitHub Desktop.
Save asanso/e08430be25456023e152f28c216a68bf to your computer and use it in GitHub Desktop.
p = 0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaaab
r = 0x73eda753299d7d483339d80809a1d80553bda402fffe5bfeffffffff00000001
# assert p.is_prime()
# assert r.is_prime()
proof.arithmetic(False)
Fp = GF(p)
Fpx.<x> = Fp[]
Fp2.<i> = GF(p**2, modulus = x^2+1)
Ep = EllipticCurve(Fp, [0,4])
EpOrder = Ep.order()
assert EpOrder%r == 0
# A point for G1
cof1 = EpOrder//r
P1 = cof1 * Ep.random_point()
while P1.is_zero():
P1 = cof1 * Ep.random_point()
assert (r*P1).is_zero()
Et2 = EllipticCurve(Fp2, [0,4*(1+i)])
Et2Order = Et2.order()
assert Et2Order%r == 0
'''
The twisted curve is defined over Fp2, and the twist map is defined using a 6-th root of 1+i, say u
(x,y) --> (u²x, u³y)
We need to define Fp12 = Fp2(u)
'''
Fp2y.<y> = Fp2[]
Fp12.<u> = Fp2.extension(y**6 - (1+i))
E12 = Ep.change_ring(Fp12)
# we take a point of order r on G2 (over the twist)
coft2 = Et2Order//r
Pt2 = coft2 * Et2.random_point()
while Pt2.is_zero():
Pt2 = coft2 * Et2.random_point()
assert (r*Pt2).is_zero()
def untwist(P):
return E12(P[0] / u**2, P[1] / u**3)
def twist(P):
return Et2((P[0] * u**2)[0], (P[1] * u**3)[0])
# we map it into E12
P2 = untwist(Pt2)
assert twist(P2) == Pt2
assert (r*P2).is_zero()
P1 = E12(P1)
assert (r*P1).is_zero()
#works only in sage 9.5
#assert P1.weil_pairing(2*P2, r) == P1.weil_pairing(P2, r)**2
eps = i+1
def endom(P):
return Et2([eps^((-p+1)/3)*P[0]^p, eps^((-p+1)/2)*P[1]^p])
def endomM(P):
P = untwist(P)
P = E12(P[0]^p, P[1]^p)
return twist(P)
GPt2 = endom(Pt2)
assert GPt2 == p * Pt2
assert endom(Pt2) == endomM(Pt2)
# used in the G1 endom
beta = 793479390729215512621379701633421447060886740281060493010456487427281649075476305620758731620350
def endomG1(P):
return Ep([P[0]*beta, P[1]])
betam = 4002409555221667392624310435006688643935503118305586438271171395842971157480381377015405980053539358417135540939436
def endomG1m(P):
return Ep([P[0]*betam, P[1]])
Pb = cof1 * Ep.random_point()
while Pb.is_zero():
Pb = cof1 * Ep.random_point()
assert (r*Pb).is_zero()
P2 = untwist(GPt2)
P1 = E12(Pb)
Pe = endomG1m(Pb)
P1e = E12(-Pe)
P2u = untwist(Pt2)
P1.weil_pairing(P2,r) == P1e.weil_pairing(P2u,r)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment