Programming ECC - Overview

Overview

Minimal pairing-based cryptography requires:

Arithmetic in $ℤ_{p}$ : I built mine on top of the GMP library, which conveniently provides number theoretic functions such as inversion modulo a prime and the Jacobi symbol.
Elliptic curve groups: mostly routines for solving $y^{2} = x^{3} + a x + b$ over $ℤ_{p}$ , point addition and multiplication.
Bilinear pairing: Miller’s algorithm.

The above suffices for what I call Type A and B (and A1) pairings: very fast, but elements take a lot of space to represent.

Field extensions must be implemented for other pairing types.

Finding certain pairing-friendly curves requires more work. The the MNT curve construction method requires routines for finding roots modulo a given prime, testing polynomial irreducibility, computing Hilbert polynomials. These in turn depend on 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$ .