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=}")

QK = EK.lift_x(a + 2) # Independent from PK
why add 2 to a?
I don't understand
how to choose the correct number to add with a

QK = EK.lift_x(a + 2) # Independent from PK
why add 2 to a?
I don't understand
how to choose the correct number to add with a

why add 2 to a?

It was just a randomly chosen linear independent point: QK = (a + 2 : 3*a + 7 : 1).

On different curves you may have luck after a few tries with QK = EK.random_point().

Updating the script to a more robust approach...