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

Citing SafeCurves:

• SEC1 requires the embedding degree to be at least $20$.
• X9.62 requires the embedding degree to be at least $20$.
• P1363 puts variable requirements upon the embedding degree, depending on the size of $p$, but never requires it to be more than $30$.
• Brainpool requires the embedding degree to be much larger, at least $\frac{\ell-1}{100}$.

Hence, $k = 12$ is not considered "too large" in general, it's just very inefficient to do arithmetics on $F_{q^{12}}$ later.
For example, BLS12-381 is a pairing-friendly curve with $k = 12$ and a "sextic twist" into $F_{q^{2}}$.

---

For fun, computing the base extension with $k = 1337$ for secp256k1 took me just a few seconds:

p = 2**256-2**32-2**9 -2**8 - 2**7 - 2**6 - 2**4 - 1
a, b = 0, 7

E = EllipticCurve(GF(p), (a, b))
G = E(0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798, 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8)
E.set_order(0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141 * 0x1)

print(E)

# Embedding degree of secp256k1 = 19298681539552699237261830834781317975472927379845817397100860523586360249056
# This is just for fun.
K.<a> = GF(p**1337)
EK = E.base_extend(K)

print(EK)

By the way, your code doesn t works on binary curves (even on isogeny 3).
It complains at line 23 that the parameter to GF isn t a prime power.

@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.