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

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.

@mcieno : and what about the case where the elliptic curve is binary curve ? In my case, I’ve $x=(0, 0, 16260673061341949275257563295988632869519996389676903622179081103440260644990, 0, 0, 0, 0, 0, 11559732032986387107991004021392285783925812861821192530917403151452391805634, 0, 0, 0)$ and $y=(0, 0, 0, 15530828784031078730107954109694902500959150953518636601196686752670329677317, 0, 0, 0, 0, 0, 4082367875863433681332203403145435568316851327593401208105741076214120093531, 0, 0)$

so obviously, as a result of the underlying finite field being a prime power, I can’t do something like point = E(integer,integer)