How can I implement MOV attack in sage?

Question

So I am using the following parameters that define an elliptic curve on a finite field modulo p:

p = 1331169830894825846283645180581
a = -35
b = 98
E = EllipticCurve(GF(p), [a,b])
G = E(479691812266187139164535778017, 568535594075310466177352868412)

I have the following public keys:

A = E(1110072782478160369250829345256, 800079550745409318906383650948)
B = E(1290982289093010194550717223760, 762857612860564354370535420319)

where A=a*G

I am trying to implement the MOV attack in sage using the weil_pairing() function, in order to retrieve the private key a. The sage docs saying that the element returned is a n'th root of unity on the base field of the curve (i.e. in the finite field modulo p). I dont really get why, because the result should be on the finite field modulo p^k based on the MOV attack(k is 2 in this curve).

The curve has another generator with the same order as G, lets name it Q. At first, I tried the following:

u = G.weil_pairing(Q, G.order())
v = A.weil_pairing(Q, G.order())

u; # 1224261643478288645398412515033
v; # 639110128106018561182432834399

v = int(v)
u = int(u)

1 == pow(u,Gk.order(),p) #True, False if modulus is p**k
1 == pow(v,Gk.order(),p) #True, False if modulus is p**k

u = Integers(p)(u)
v = Integers(p)(v)

na = discrete_log(v,u,operation="*")
na = int(na)
na; # 6458797

v = int(v)
u = int(u)

v == pow(u,na,p); #v = u^na mod p, True, False if modulus is p**k
A == na*G; #False

I tried to extend the base field to the finite field modulo p^k with the following commands:

Ek = E.base_extend(GF(p**k))

Gk = Ek(G)
Ak = Ek(A)
Qk = Ek(Q)

and then I used Gk, Ak and Qk instead, but this gave the same results.

I think this is not working because:

1. Q must be a point on the finite field modulo p^k which is not included in the finite field modulo p based on this: https://risencrypto.github.io/WeilMOV/
2. weil_pairing() function returns an element on the finite field modulo p instead of the finite field modulo p^k

Furthermore, I tried to find a point Q with the same order as G in the finite field modulo p^k but the only algorithm I could find is the following, which is not giving any results(running forever):

E2 = EllipticCurve(GF(p**k), [a,b])

P = E2(0)
while P.order() != G.order():
    R = E2.random_point()
    if(R.order() == G.order()):
        P = R
        break
    P = (E2.order()/G.order())*R

Lastly, I tried to use a different approach(frey ruck attack) based on the code here: https://github.com/jvdsn/crypto-attacks/blob/master/attacks/ecc/frey_ruck_attack.py but yet again, I dont get any results neither.

So my questions are:

1. Why sage function weil_pairing() returns the n'th root on finite field modulo p instead of p^k?
2. Is there a way to compute points of a specific order faster?
3. How is it possible to solve this if these algorithms are taking so long?

Answer 1

We have three separated, more or less related question, pointing to the same target of attacking a weak elliptic curve, i am trying to address each in separate sections.

---

$(1)$

This question does not depend on the complexity of the given elliptic curve, we only want to check a parent. So let us consider some easy sample case, and check the parent of the result of calling theweil_pairing $$ w $$ (in notation) for the chosen toy situation. The following sample lives over the field $F=\Bbb F_3[u]$ with nine elements, generated by the algebraic element satisfying $u^2-u-1=0$. I picked then an elliptic curve $$ E\text{ over }F=\Bbb F_3[u]\cong \Bbb F_9 \qquad :\qquad y^2=x^3 +x+1\ , $$ with order (of the rational points over $F$) equal to $16$, and two generators, $P,Q$. Note that it is pointless to have a cyclic $E(F)$, generated by one point $P$, say, since then the pairing $w$ on some points $aP$, $bP$ is equal to $w(aP,bP)=w(P,P)^{ab}=1^{ab}=1$. So we need in the example two generators, we have them below The generators have both order $4$, so $$ \begin{aligned} E(F) &=\{\ aP+bQ\ :\ a,b\in \Bbb Z\ \} \\ &=\{\ aP+bQ\ :\ a,b\in \Bbb Z/4\ \} \\ &=\{\ (a, b)\ :\ a,b\in \Bbb Z/4\ \} \\ &\cong (\Bbb Z/4)\times (\Bbb Z/4)$. \end{aligned} $$ Code for a first inspection:

F.<u> = GF(3^2)
E = EllipticCurve(F, [1, 1])
print(f'E is:\n{E}\nE(F) has order {E.order()}')
P, Q = E.gens()
nP, nQ = P.order(), Q.order()
print(f'The generators P, Q of E(F) have orders {nP}, {nQ}.')
n = lcm(nP, nQ)

This gives so far the information:

E is:
Elliptic Curve defined by y^2 = x^3 + x + 1 over Finite Field in u of size 3^2
E(F) has order 16
The generators P, Q of E(F) have orders 4, 4.

Which are the results of the weil_pairing, where do they live in?

sage: P.weil_pairing(Q, n)
2*u + 2
sage: P.weil_pairing(Q, n).parent()
Finite Field in u of size 3^2
sage: P.weil_pairing(Q, n).multiplicative_order()
4
sage: P.weil_pairing(P, nP)
1
sage: P.weil_pairing(P, nP).parent()
Finite Field in u of size 3^2

So even in the case of a result equal to one, the parent domain is in the sage implementation the field $F$ with $p=3^2$ elements. We have in this example $w(P,Q)=2u+2$, so in general $w(aP,bQ)=(2u+2)^{ab}$.

---

$(2)$

The question about producing in a quick manner "some points" of a given order is not directly relevant to the attack implementation. I will say some few words. Our given curve has order computed as follows:

p = 1331169830894825846283645180581
E = EllipticCurve(GF(p), [-35, 98])

G = E(479691812266187139164535778017, 568535594075310466177352868412)

A = E(1110072782478160369250829345256, 800079550745409318906383650948)
B = E(1290982289093010194550717223760, 762857612860564354370535420319)

E.order().factor()

And the last line gives in the interpreter:

sage: E.order().factor()
2^2 * 7 * 271^2 * 23687^2 * 1153763334005213

however this does not elucidate the structure of the group $E(F)$. Which is either cyclic, so it would be the integers modulo the above number, one generator, or has two cyclic components, $E(F)\cong \Bbb Z/d_1\oplus \Bbb Z/d_2$ with $d_1$ dividing $d_2$ and with product the above number. (The theorem of invariant factors would also allow further components for an arbitrary finite / torsion abelian group = $\Bbb Z$-module, but either structure theorems for elliptic curves over finite fields, or the fact that we see at most power two tells us that we have at most two cyclic pieces.)

We can even ask for the structure by associating the corresponding finite abelian group:

sage: E.abelian_group()
Additive abelian group isomorphic to Z/103686954799254136375814 + Z/12838354
    embedded in Abelian group of points on Elliptic Curve defined by
    y^2 = x^3 + 1331169830894825846283645180546*x + 98
    over Finite Field of size 1331169830894825846283645180581

(Manually rearranged.) So the two invariant factors are $d_1=12838354=2 \cdot 271 \cdot 23687$, and $d_2 = 2 \cdot 7 \cdot 271 \cdot 23687 \cdot 1153763334005213$. Back to the question of finding points of a given order. Any point $S$ in $E(F)$ is a linear combination of $P,Q$, $$ S=aP+bQ\ , $$ and the order of $S$ divides $d_2$. Its order is the lcm of the orders for $aP$ and $bQ$. Given one such order, arrange for corresponding orders for $aP$ and $bQ$, make such a choice, then arrange for $a,b$ to realize the choice.

So there are for instance in $E(Q)$ only the points of order $1153763334005213$ which are of the shape $2 \cdot 7 \cdot 271 \cdot 23687 \cdot b'Q$, where $b'$ should be prime to $1153763334005213$, there are $1153763334005213-1$ choices for such a $b'$.

If we want to count points of order $271$, note that we have an injection $$ \Bbb Z/271\oplus\Bbb Z/271 \cong 2 \cdot 271 \cdot 23687\Bbb Z/d_1\oplus 2 \cdot 7 \cdot 23687 \cdot 1153763334005213\Bbb Z/d_2 \to \Bbb Z/d_1\oplus \Bbb Z/d_2\ , $$ and all points but one in the first group have order $271$. I hope it is clear now how to produce points of a given order starting from the generators $P,Q$...

sage: EF = E.abelian_group()
sage: EF.gens()
((831960547404637732080245697552 : 277342045953693233252374308630 : 1),
 (118010095899121458286495929253 : 595183235394488229448465664053 : 1))

---

$(3)$

This is in fact the main and only question.

We have to note first that for two random points $A,G$ in $E(F)$ - with order of $A$ dividing the order of $G$ to have a necessary condition for the start - there is not always possible to realize $A$ as an integer multiple of $G$. For instance, pick $A,G$ in different components of the $\Bbb Z/271\oplus \Bbb Z/271$ that injects in $E(F)$. But for the practical purpose, we may and do assume that there is a relation $$ A=mG\ , $$ and we want to determine (one choice of) $m$ making this happen.

So let us use some suitable pairing (that should not be trivial) and let us pair both $G$ and $A=mG$ with one and the same suitable point, well the generators are enough to pair with. We work over $F$ first, no extension of degree two of it, just to get an impression.

In our case, with $A$, $B$, $G$ as in the question, we have order $d_2$ for them:

sage: A.order().factor()
2 * 7 * 271 * 23687 * 1153763334005213
sage: B.order().factor()
7 * 271 * 23687 * 1153763334005213
sage: G.order().factor()
2 * 7 * 271 * 23687 * 1153763334005213

so the usage of an antisymmetric may be not so fruitful. Since we have to pair with "the generator of the other, easier part $\cong \Bbb Z/d_1$, of much smaller order to get non-trivial results. Explicitly, written in terms of the generators $P$, $Q$, with orders $d_1$, respectively $d_2$ we have for the lifted instances (lifted from EF back to points of E)...

P, Q   = [gen.__dict__['_element'] for gen in EF.gens()]    # ugly, but the pairing design gives no easy access to the "lift"
d1, d2 = Q.order(), P.order()

and these generators have orders $d_1$ dividing $d_2$:

sage: Q.order().factor()
2 * 271 * 23687
sage: P.order().factor()
2 * 7 * 271 * 23687 * 1153763334005213

Which information can be traced back by pairing with $P$?

sage: P.weil_pairing(G, P.order())
196105629888591658454494838286
sage: P.weil_pairing(A, P.order())
501468398775454992710087089898

sage: P.weil_pairing(G, P.order()).multiplicative_order().factor()
271 * 23687
sage: P.weil_pairing(A, P.order()).multiplicative_order().factor()
271 * 23687

Which information can be traced back by pairing with $Q$?

sage: Q.weil_pairing(G, d2)
7599096454588741679433611555
sage: Q.weil_pairing(A, d2)
1173763469271310012326486522736

sage: Q.weil_pairing(G, d2).multiplicative_order().factor()
2 * 271 * 23687
sage: Q.weil_pairing(A, d2).multiplicative_order().factor()
2 * 271 * 23687

So we can extract with the weil_pairing the partial information only from solving a discrete logarithm problem in a group of order $2\cdot 271\cdot 23687$. A brute force search related to this group gives:

a = Q.weil_pairing(A, d2)
g = Q.weil_pairing(G, d2)
# from A = m.G we obtain a = g^m.

s, t, u = 2, 271, 23687
# these are the factors of the (same) multiplicative order of a, g
# we are searching for m in the form
# m = (ms * t * u) + (mt * s * u) + (mu * s * t)
# then from a^st = (g^m)^(st) = g^(mst) = g^(mu s²t²) we can isolate mu

a_s, g_s = a^(t*u), g^(t^2*u^2)
a_t, g_t = a^(s*u), g^(s^2*u^2)
a_u, g_u = a^(s*t), g^(s^2*t^2)

ms = [m for m in range(s) if g_s^m == a_s][0]
mt = [m for m in range(t) if g_t^m == a_t][0]
mu = [m for m in range(u) if g_u^m == a_u][0]

m = (ms * t * u) + (mt * s * u) + (mu * s * t) % (s*t*u)

print(f"m = {m} :: Is a == g^m? {bool(a == g^m)}")

And we obtain:

m = 19297151 :: Is a == g^m? True

Now the same should be done also for the other pieces, i.e. working also against the primes $7$ and $1153763334005213$. we only need corresponding non-trivial pairing information. And of course, the last prime is somehow too big for a naive loop. So far we have only the information: $$ A = mG\qquad\text{ with $m$ of the shape $19297151+2\cdot 271\cdot 23687\cdot N$ .} $$ We can also obtain information to cover the prime $7$ by using the tate_pairing,

sage: P.tate_pairing(A, d2, 2).multiplicative_order().factor()
7 * 271 * 23687
sage: P.tate_pairing(G, d2, 2).multiplicative_order().factor()
7 * 271 * 23687
sage: P.tate_pairing(A, d2, 2)

or just by working with the points $1153763334005213\cdot A$ and $1153763334005213\cdot G$.

A1 = 1153763334005213 * A
G1 = 1153763334005213 * G

for N in range(7):
    m = 19297151 + (2 * 271 * 23687) * N
    if A1 == m * G1:
        print(f"m = {m} modulo 2 * 7 * 271 * 23687")
        break

This delivers:

m = 32135505 modulo 2 * 7 * 271 * 23687

It remains to get the information modulo the remained prime, $1153763334005213$, the only "big prime" involved. Both discrete logarithm problems, on the elliptic curve and on the multiplicative group with this number of elements, would take a long time for a naive approach.

---

$(3)$ continued...

Here are some final words regarding the computation of $m$ modulo $q = 1153763334005213$, which is a prime number. It working over a field (instead in the group of rational points of an elliptic curve), then here is the field and the associated discrete logarithm problem.

We initialize the same curve over the field $K[u]$ with $p^2$ elements.

p = 1331169830894825846283645180581
F.<u> = GF(p^2)
E = EllipticCurve(F, [-35, 98])

G = E(479691812266187139164535778017 , 568535594075310466177352868412)
A = E(1110072782478160369250829345256, 800079550745409318906383650948)

P, Q   = [gen.__dict__['_element'] for gen in E.abelian_group().gens()]    # ugly again
d1, d2 = Q.order(), P.order()

print(f"E has order {E.order().factor()}")
print(f"d1 = {d1.factor()} is the order of Q")
print(f"d2 = {d2.factor()} is the order of P")

and the results are:

E has order 2^7 * 7 * 11 * 29 * 191 * 271^2 * 457 * 919 * 1409 * 23687^2 * 1153763334005213^2
d1 = 2^3 * 271 * 23687 * 1153763334005213 is the order of Q
d2 = 2^4 * 7 * 11 * 29 * 191 * 271 * 457 * 919 * 1409 * 23687 * 1153763334005213 is the order of P

Now we also have the prime $q$ as factor in the order of using the weil_pairing,

sage: P.weil_pairing(A, d2).multiplicative_order().factor()
2 * 271 * 23687 * 1153763334005213
sage: P.weil_pairing(G, d2).multiplicative_order().factor()
2 * 271 * 23687 * 1153763334005213

so $A=mG$ implies $$ \begin{aligned} \underbrace{2 \cdot 7\cdot 271 \cdot 23687\cdot A}_{:=A_2} &= 2 \cdot 7\cdot 271 \cdot 23687\cdot mG\\ &=m\cdot\underbrace{( 2 \cdot 7\cdot 271 \cdot 23687\cdot G)}_{G_2}\ . \end{aligned} $$ applying the weil_pairing, we need to find $m$ such that:

r = 2 * 7 * 271 * 23687
A2, G2 = r*A, r*G
a2 = P.weil_pairing(A, d2)
g2 = P.weil_pairing(G, d2)

print(f"a2 = w(P, A2) is {a2}")
print(f"g2 = w(P, G2) is {g2}")

We obtain:

a2 = w(P, A2) is 573701785486394880347215076826*u + 937462886552089156533615255382
g2 = w(P, G2) is 882076139211768800810294904418*u + 458352352918379992142983892259
sage: u.minpoly()
x^2 + x + 1

We obtain: So it remains to solve for $m$ modulo $q$ in the discrete logarithm equation: $$ 573701785486394880347215076826\;u + 937462886552089156533615255382 = ( 882076139211768800810294904418\;u + 458352352918379992142983892259)^m \ . $$ (And then combine with the information for the other involved primes, $2$, $7$, $271$, $23687$.)

Good luck!