# How can I implement the elliptic curve MOV attack myself?

I understand and have implemented elliptic curve signatures in Python without the use of libraries like Sage, and would like to implement the MOV attack against certain weak types of elliptic curves.

Even though I understand the mathematical notation and terms of group theory, I'm a programmer by trade, not a mathematician or cryptographer. When I read descriptions of the MOV attack, though, I'm completely lost. The notation and terms are way beyond anything I understand, so I have no idea how to implement MOV.

I understand what $F_p$ and $F_{p^k}$ are about. I also understand that the idea is to make a function $e()$ of domain $F_p$ and range $F_{p^k}$ in such a way that sets up $x^y = z \pmod {p^k}$, where $y$ happens to be the scalar by which your generator point was point-multiplied. Then, since this is a traditional multiplication modulo a composite with known prime factorization group, you can do index calculus to get y instead of being limited to slower methods that work on elliptic curve groups.

But how the heck do I calculate this $e()$ function? I don't understand these "torsion point" and "div() function" concepts at all, especially not in a way that would allow me to write Python code to implement them.

-

It is all pairings... this is a rather complex matter. I recommend reading Ben Lynn's PhD dissertation; it is about as nice an introductory text on pairings as you can get.

The definition is rather mind-twisting:

• You first define divisors, which are rather formal objects. It is the free group of the curve points: for each curve point $P$, you define a divisor $(P)$, and then you add divisors together, so the complete form of a divisor is a linear combination: $\sum_{P\in E} a_P (P)$. This is a formal sum: all the linear combinations are deemed distinct from each other. In particular, $(P+Q)$ (the divisor associated with the point $P+Q$) is not the same as $(P)+(Q)$ (which is the sum of two elementary divisor, and is thus a divisor in its own right, but not associated with a curve point). Each $a_P$ is an integer (possibly negative).

• Then you consider rational functions over the curve (these are functions $f = R_1(x,y)/R_2(x,y)$ where $R_1$ and $R_2$ are polynomials, and $(x,y)$ are the coordinates of curve points).

• Then you establish a kind of bijection between divisors and rational functions. The function $f$ has zeros (roots of polynomial $R_1$) and poles (roots of polynomial $R_2$): you map $f$ to a divisor $\sum_{P\in E} a_P (P)$ such that:

• if $P$ is a zero of multiplicity $n$ then $a_P = n$;
• if $P$ is a pole of multiplicity $n'$ then $a_P = -n'$;
• otherwise $a_P = 0$.

It so happens that to a given divisor corresponds a unique rational function $f$, up to a multiplicative constant. This is not completely surprising: we know that a polynomial can be rebuilt (up to a multiplicative constant) from knowledge of its roots: if polynomial $T$ has root $t_1$ with multiplicity $2$ and root $t_2$ with multiplicity $3$, then $T = \alpha (X-t_1)^2(X-t_2)^3$ for some constant $\alpha$. Here, this is extended to rational functions, which contain two polynomials, hence the zeros and the poles (our $f$ functions are over two variables $x$ and $y$ instead of one, but the same principle is at work here). We denote the divisor corresponding to function $f$ by $(f)$.

• Then the really confusing part: for some reason, we begin to apply rational functions to divisors. It took me some time to understand this step. We define a new operation which takes a rational function $f$ and a divisor $D$, and computes $f(D)$. Then magic occurs: for two functions $f$ and $g$, we have $f((g)) = g((f))$ (the "Weil reciprocity").

• Then we define the Weil pairing as a quotient of two such applications of functions on divisors. The quotient makes the multiplicative constants disappear, and the result is well-defined.

Then you want to compute the pairing. Mathematically, you would need to build two huge rational functions (the polynomials would have $2^{160}$ or so coefficients, so that's not feasible) and then apply these functions to some divisors (which are equally humongous). However, since we are just interested in the final application result, we can remove a lot of needless complexity, and that's Miller's algorithm.

All of this suppose that you start with a finite field $\mathbb{F}_q$ for some $q$ (a prime or a prime power), then do all computations in some extension field $\mathbb{F}_{q^k}$ for some $k$ called the embedding degree. Theory shows that if your points of interest have order $r$ (a prime number)(points of order $r$ are called $r$-torsion points), then the pairing remains trivial (you get $1$ at the end), until $k$ is "large enough": precisely, the $k$ value at which things get interesting is the smallest $k \geq 2$ such that $r$ divides $q^k-1$ (that the Balasubramanian-Koblitz theorem).

For normal curves, the embedding degree $k$ is ludicrously high (the same order of magnitude as $q$), so you would have to do computations with numbers too large to fit in your computer, or, for that matter, in the Universe taken as a whole. However, if the curve is so that $k$ is small, then the pairing can be computed, and the MOV attack reduces the problem of discrete logarithm on the curve to the problem of discrete logarithm in $\mathbb{F}_{q^k}$, which can be substantially simpler.

In particular, when $q$ is prime and equal to $3$ modulo $4$ and the curve is $Y^2 = X^3+aX$, then $k = 2$. If $q$ is a 256-bit integer, then the MOV attack turns discrete logarithm over a 256-bit curve (infeasible) into discrete logarithm in a 512-bit field (hard but feasible).

Implementing pairings is a deep exploration into non-trivial mathematics. It is enlightening, but daunting. For practical purposes it may be simpler to rely on some existing code, e.g. Ben Lynn's PBC library).

(I am writing all of this from memory, there could be some mistakes. Feel free to fix them.)

-
thumbs up There's a reason, most cryptographers just use the properties of pairings and ignore their actual implementation: It belongs to the "higher mysteries of algebra" (for both finding and calculating pairings), and there is no "simple implementation in a few lines of code". –  tylo Mar 6 '14 at 14:55

A Torsion point is a point on an elliptic curve is a point of finite order. That is, $T\in E(\mathbb{F}_p)$ is a torsion point if there exists some $n>0$ such that $nT=0$ (where $0$ is the point at infinity).

$e(\cdot,\cdot)$ is the Weil pairing, an example of a bilinear pairing. It is a function $e:E(\mathbb{F}_p)^2\to \mathbb{F}_{p^k}$ for some $k$ such that $e(aP,bQ)=e(P,Q)^{ab}$. The reason that ECC is not completely worthless is because usually the Weil pairing maps onto $\mathbb{F}_{p^k}$ with $k$ large.

Unfortunately, explaining Millar's algorithm for calculating the Pairing is beyond me, but this appears to be the relevant paper.

-
I've been unsure whether to put this as an answer or comment, but since it at least helps with the torsion question I've put it here. –  figlesquidge Nov 21 '13 at 17:58