Elliptic Curves

Elliptic curves are very useful objects because they allow us to obtain a group structure with interesting properties. Given a field \( \mathcal{F} \), an elliptic curve is the set of points \( (x,y) \) which satisfy the following equation: \[ y^2+a_1xy+a_3y=x^3+a_2x^2+a_4x+a_6 \] This is known as the general Weierstrass equation. In many cases, this can be written in the simpler form \[ y^2=x^3+ax+b \] which is the (Weierstrass) short-form. Depending on the choice of the parameters \( a \) and \( b \) and the field, the curve can have some desired properties or not. If \( 4a^3+27b^2 \neq 0 \), the curve is non-singular.

We can define an operation which allows us to sum elements belonging to the elliptic curve and obtain a group. This is done using a geometric construction, the chord-and-tangent rule. Given two points on the curve \( P_1=(x_1,y_1) \) and \( P_2=(x_2,y_2) \), we can draw a line connecting them. That line intersects the curve on a third point \( P_3=(x_3,y_3) \). We set the sum of \( P_1 \) and \( P_2 \) as \( (x_3,-y_3) \), that is, point \( P_3 \) flipped around the \( x \)-axis. The formulae are: \( s=\frac{y_2-y_1}{x_2-x_1} \) \( x_3=s^2-x_1-x_2 \) \( y_3=s(x_1-x_3)-y_1 \)

We can easily see that we have a problem if we try to sum \( P_1=(x_1,y_1) \) and \( P_2=(x_1,-y_1) \). We need to add an additional point to the system, which we call the point at infinity \( \mathcal{O} \). This inclusion is necessary to be able to define the group structure and works as the identity element for the group operation.

Another problem appears when we want to sum \( P_1 \) and \( P_1 \) to get to \( P_3=2P_1 \). But, if we draw the tangent line to the curve on \( P_1 \), we see that it intersects the curve at another point. If we want to perform this operation, we need to find the slope of the tangent line and find the intersection: \( s=\frac{3x_1^2+a}{2y_1} \) \( x_3=s^2-2x_1 \) \( y_3=s(x_1-x_3)-y_1 \)

It takes a little bit of work, but we can prove that the elliptic curve with this operation has the properties of a group. We will use finite fields to work with these curves and the groups that we will obtain are finite cyclic groups, that is, groups which can be generated by repeteadly using the operation on a generator, \( g \): \( {g,2g,3g,4g,5g,...} \).

If we plot the collection of points onto a graph, we see that the points are distributed in a rather "random" fashion. For example, \( 2g \) could be very far from \( 3g \) which in turn are very far from \( 4g \). If we wanted to know how many times \( k \) we have to add the generator to arrive at a certain point \( P \) (that is solving the equation \( kg=P \)) we see that we don't have an easy strategy and we are forced to perform a brute search over all possible \( k \). This problem is known as the (elliptic curve) discrete logarithm (log for friends) problem (other friends prefer ECDLP).

On the other hand, if we know \( k \), we can compute in a very fast way \( P=kg \). This offers us a way to hide (in plain sight) things inside the group. Of course, if you could break the DLP, you could get \( k \), but it is rather infeasible. If we want to calculate \( 65536g \), we can do it by realizing that \( g+g=2g \), \( 2g+2g=4g \), \( 4g+4g=8g \)...until \( 32768g+32768g=65535g \), so we narrowed the operations 65536 to 16. There are many useful algorithms that allow us to speed up the operations over elliptic curves, allowing us to avoid expensive calculations such as inversions, which appear when we want to calculate the slope.

Projective coordinates

We can save ourselves from costly inversions if we move from our nice 2 dimensional space to a 3 dimensional space. This was introduced by Moebius and helps us also to represent the point at infinity properly. We can map our points from our elliptic curve \( (x,y) \) to points in projective space \( (X,Y,Z) \) as \( (x,y) \rightarrow (X=x,Y=y,Z=1) \) and \( \mathcal{O} \rightarrow (0,1,0) \). We can go back using the transformation \( (X,Y,Z) \rightarrow (x=X/Z,y=Y/Z) \), except for the point at infinity, where it is ill-defined. We can visualize this process with the following picture, where we take three points from an elliptic curve and transform them to 3-d.

We can think of this as transforming our 2-d points to lines passing through the origin in 3-d space. For example, the point \( (x_1,y_1) \) in 2-d transforms to the line \( (\mu x_1,\mu y_1, \mu) \) with \( \mu \) an element in the field. Thus, two points \( P_1=(X_1,Y_1,Z_1) \) and \( P_2=(X_2,Y_2,Z_2) \) are the same in 2-d (more precisely, are congruent) if we can find \( \eta \) such that \( (\eta X_1,\eta Y_1,\eta Z_1)=(X_2,Y_2,Z_2) \). These lines do not contain the origin \( (0,0,0) \). It is usual to write points is projective space as \( (X:Y:Z) \), instead of \( (X,Y,Z) \). In our picture, the point A (yellow) gets mapped to the point D (red above it). All the points that lie on the same straight line passing through the origin and D (pink dashed) are considered equivalent to D. Similarly, point B (blue) is mapped to point F (light blue) and all the ponts over the light green dotted line (except the origin) are equivalent to F. When we add points in this space, the components \( (X,Y,Z) \) will change, but we can go back to the point belonging to the curve by just retracing our steps to \( Z=1 \) along the line that passes through the origin. Why go all this length? We will shortly see that we avoid inversions at each addition step and do just one at the time of finding the point in 2-d (for example, when we need to find \( r=x_1 \) in ECDSA). Of course, if we have to do \( P=2g \) we didn't gain anything, but if we have to perform \( P=kg \) with \( k \) in the order of 256 bits, we saved many costly inversions.

Making the substitutions into the elliptic curve equation \[ \frac{Y^2}{Z^2} = \frac{X^3}{Z^3} + a \frac{X}{Z} + b \] We can multiply by \( Z^3 \) and get the equation \[ ZY^2=X^3+aZ^2+bZ^3 \] If we want to sum \( P \) and \( Q \) to yield \( R=P+Q \) in projective space, we can use the formulae:

\( Z_R=Z_PZ_Q(X_PZ_Q-X_QZ_P)^3 \) \( X_R=(X_PZ_Q-X_QZ_P)(Z_QZ_P(Y_PZ_Q-Y_QZ_P)^2-(X_PZ_Q-X_QZ_P)^2(X_PZ_Q+X_QZP)) \) \( Y_R=Z_PZ_Q(X_QY_P-X_PY_Q)(X_PZ_Q-X_QZ_P)^2-(Y_PZ_Q-Y_QZ_P)A \) \( A=Z_PZ_Q(Y_PZ_Q-Y_QZ_P)^2-(X_PZ_Q+X_QZ_P)(X_PZ_Q-X_QZ_P)^2 \).

This looks more complicated and difficult than the simple formulae for 2 dimensional (2-d) space. However, we do not have to calculate any inverses! To get the sum, we have to perform 12 multiplications and 2 squarings. In 2-d, we have 2 multiplications, one squaring and one inversion. Inversions can be 20 times or more expensive than multiplications, so we've saved at least 10 multiplications (some authors say inversions are about 80 times more expensive than multiplications).

Some curves can go even faster. If \( x^3+ax+b \) has a solution in \( \mathcal{F}_p \), we can work with an equivalent Jacobi quartic \( v^2=a^\prime u^4+du^2+1 \), where \( a^\prime \) and \( d \) depend on the root. We can transform the curve \( (u,v) \) to 3-d space \( (U,V,W) \) using \( u=U/W \) and \( v=V/W^2 \) and get the equation

\[ V^2=a^\prime U^4+dU^2W^2+W^4 \]

If we want to sum \( P_3=P_1+P_2 \), in these coordinates we have:

\( U_3=U_1W_1V_2+U_2W_2V_1 \) \( V_3=((W_1W_2)^2+a^\prime (U_1U_2)^2)(V_1V_2+dU_1U_2W_1W_2)+2a^\prime U_1U_2W_1W_2(U_1^2W_2^2+U_2^2W_1^2) \) \( W_3=(W_1W_2)^2-a^\prime (U_1U_2)^2 \)

These allow us to further reduce the costs for adding to 6 multiplications and 4 squarings. Other models with fast implementations are Edwards curves and Montgomery curves, which have some of the fastest implementations.

Montgomery curves satisfy the following equation \[ By^2=x^3+Ax^2+x \] where \( B(A^2-4)\neq 0 \). This expression can be cast in the Weierstrass form by making some transformation. If we take \( (x,y) \) and map it to \( (x^\prime,y^\prime) \) given by \( (x,y)\rightarrow(x/B+A/3B,y/B) \), we get \[ y^2=x^3+\left(\frac{3-A^2}{3B^2}\right)x+\frac{2A^3-9A}{27B^3} \] Transforming a Weierstrass curve into a Montgomery curve is not always possible, though. The order of the group must be divisible by \( 4 \) and \( x^3+ax+b=0 \) must have a solution.

Montgomery curves can also be related to twisted Edwards curves, which obey the following equation \[ ax^2+y^2=1+dx^2y^2 \] The parameters are related via \( A=2(a+d)/(a-d) \) and \( B=4/(a-d) \). We say these two curves are birrationally equivalent. For example, the well-known Edwards curve 25519, with \( p=2^{255}-19 \) is (birrationally) equivalent to the Montgomery curve \( t^2=u^3+486662u^2+u \). The mappings are \( (x,y)=(\sqrt{-486664}u/t,(u-1)/(u+1)) \) \( (u,t)=((1+y)/(1-y),\sqrt{-486664}(1+y)/(x(1-y))) \)

Montgomery curves have some interesting properties that lend themselves to constant time implementation. We can work in projective coordinates just using the \( x \) component, with the transformation \( x=X/Z \). Doubling a point takes the simple form: \( 4R=(X_1+Z_1)^2-(X_1-Z_1)^2 \) \( X_2=(X_1+Z_1)^2(X_1-Z_1)^2 \) \( Z_2=R((X_1-Z_1)^2+((A+2)/4)R) \)

Twisted Edwards curves have there advantages, too. The expressions for point addition and doubling are the same. Given \( P_1=(x_1,y_1) \), \( P_2=(x_2,y_2) \) we get \( x_3=\frac{x_1y_2+x_2y_1}{1+dx_1x_2y_1y_2} \) \( y_3=\frac{y_1y_2-ax_1x_2}{1-dx_1x_2y_1y_2} \) If we let \( x_1=x_2 \) and \( y_1=y_2 \) we get the expressions for point doubling. There are several alternatives to speeding up the calculations, such as projective, inverted or extended coordinates.

There are some other tricks to add and multiply points over elliptic curves, such as the technique by Gallant, Lambert and Vanstone (GLV) and generalized by Galbraith, Lin and Scott (GLS).