Programming ECC - Overview

Overview

The first step is to implement arithmetic in $ℤ_{p}$ . I built mine on top of the GMP library, which conveniently provides various number theoretic functions such as inversion modulo a prime and the Jacobi symbol.

Basic elliptic curve arithmetic is built on top, then finally a pairing can be coded. For some curves, field extensions must be implemented.

For the MNT curve construction method various operations on polynomials need to be implemented, such as finding roots modulo a given prime and irreducibility tests, along with an algorithm to compute Hilbert polynomials (which requires high precision complex floating point arithmetic) and also an algorithm to solve a Pell-type equation.

Arithmetic on Elliptic Curves

Curves over fields of characteristic greater than 3 can be written in the form $y^{2} = x^{3} + a x + b$ . For such curves, point addition and multiplication routines are straightforward. (See Blake, Seroussi and Smart.) We give the explicit formulae here.

Suppose we wish to compute $R = P + Q$ . If $P = O$ , then $R = Q$ and similarly $Q = O$ is easily handled. If $P_{x} = Q_{x}$ then either $P_{y} = - Q_{y}$ in which case $R = O$ (for we have $P = - Q$ ), or $P = Q$ in which case the point doubling algorithm is invoked. Note that the point doubling algorithm assumes the input does not have order 2, i.e. the $y$ -coordinate is nonzero. (If $P$ has order 2, the result is $O$ .)

Point addition for $P \neq Q$ :

\begin{matrix} λ & = & \frac{Q_{y} - P_{y}}{Q_{x} - P_{x}} \\ R_{x} & = & λ^{2} - P_{x} - Q_{x} \\ R_{y} & = & (P_{x} - R_{x}) λ - P_{y} \end{matrix}

Point doubling:

\begin{matrix} λ & = & \frac{3 P_{x}^{2} + a}{2 P_{y}} \\ R_{x} & = & λ^{2} - 2 P_{x} \\ R_{y} & = & (P_{x} - R_{x}) λ - P_{y} \end{matrix}

Generating Random Points

The standard method to generate a random point on an elliptic curve is to choose a random $x$ -coordinate and solve a quadratic equation for $y$ . (If no solution exists, a new $x$ -coordinate is chosen.) For odd characteristics, this can be done once one is able to find square roots of elements. In a finite field of prime order, square roots can be obtained via the Tonelli-Shanks algorithm. In general fields, see D.J. Bernstein's draft of a paper entitled "Faster square roots in annoying finite fields". At the moment I just solve $x^{2} - a$ using the Cantor-Zassenhaus method (which is referred to as Legendre's method in the aforementioned reference).

Easier ways to generate random points exist for particular cases. For example if $p$ is a prime with $p = 2 \mod 3$ then the cube root of $x \in 𝔽_{q}$ is simply $x^{(2 p - 1) / 3}$ . Thus if $a = 0$ in the equation of the elliptic curve, then it is a simple matter to pick $y$ first and then solve for $x$ .