MOV attack on elliptic curves.

MOV.sage

# Setup curve
p = 17
a, b = 1, -1

E = EllipticCurve(GF(p), [a, b])
G = E.gen(0)

# Target secret key
d = 8

# Public point
P = d * G
del d

# Find the embedding degree
# p**k - 1 === 0 (mod order)
order = E.order()
k = 1
while (p**k - 1) % order:
    k += 1
    assert k <= 6

K.<a> = GF(p**k)
EK = E.base_extend(K)
PK = EK(P)
GK = EK(G)

d = 0
while P != d * G:
    QK = EK.random_point()
    if QK.order() != E.order():
        continue

    AA = PK.tate_pairing(QK, E.order(), k)
    GG = GK.tate_pairing(QK, E.order(), k)
    d = AA.log(GG)

print(F"{d=}")

@ytrezq

Feel free to suggest improvements :)

While I know how to compute bilinear pairings and I understand the aim, I’ve absolutely no idea about what :

EK = E.base_extend(K)

does (I’m meaning the function). Looks like you’ll have to find a SageMath alternative to do this.
By the way, did you test your code to see if it works on easy samples ?

@ytrezq

Was tested on

p = 3009944491747103173592552029257669572283120430367
a, b = 1, 0

E = EllipticCurve(GF(p), [a, b])

G = E(2900641855339024752663919275085178630626065454884, 1803317565451817334919844936679231131166218238368)
P = E(10654737690719804518827220655939579230832010880, 1272308004685912947962139770717466018620937245516)

which was a VolgaCTF 2020 Qualifier challenge.