Elliptic curve cryptography

Elliptic Curve Cryptography (sometimes called ECC for short) is the study of elliptic curve equations and the arithmetic operations that apply to them. Normally, an elliptic curve involves two variables x and y which correspond to the X- and Y- coordinates of a point respectively. Curves have special operations for adding, subtracting, and multiplying two points, and the way these operations work is very different from their scalar counterparts.

All curve points have a generator point G which can produce all the other points on the curve by means of multiplication by a scalar number. G also happens to be the multiplicative identity, while the additive identity is a special point called the point at infinity and it's represented as 0 or uppercase O. It can be thought of as a limit to both ends of the curve.

Each curve has a characteristic number which stands for the number of times the generator point can be added to itself before you end up back at G. The x and y coordinates must not be larger or equal to this scalar number. Each curve also has a curve order. All private keys (which themselves are represented as numbers) must be smaller than the group order.

Operations

Point Addition

Point addition for two unequal points (x3,y3) = (x1,y1) + (x2,y2) can be performed in simple scalar arithmetic with the following pseudocode. Note that all arithmetic operation involving x or y coordinates are modulus of the characteristic (mod p) applied after it. All occurrences of the modulus are omitted from the pseudocode for brevity. Also displayed here is point doubling which is the case where both points are the same and the traditional point addition algorithm would otherwise not work on them.

   if (x1,y1) == O
       result = (x2,y2)
   else if (x2,y2) == O
       result = (x1,y1)
   else if (x2,y2) == (x1,y1)**(-1)
       result = O
   
   if (x2,y2) == (x1,y1):
        # Point doubling: 2P
        lambda = (3 * x1**2) * (2*y1)**-1
   else:
        # Point addition: P+Q
        lambda = (y2 - y1)*(x2 - x1)**-1
   x3 = lambda**2 - x1 - x2
   y3 = lambda*(x1 - x3) - y1

It follows that (x1,y1) and (x2,y2) are the input points, The lambda variable is an expression made out of the x1,y1 and x2,y2 coordinates that refers to the slope of the name made by drawing a line between point A and point B. The result of the point addition is will always be the intersection between the curve, and the line formed by x1,y1 and x2,y2. It follows that since there are three intersection points between a line formed by point addition and the curve, two of them are the operands, and the third one is the negative of the sum of the two points. The exception is when you add the point-at-infinity (0, sometimes written as uppercase O) to any point or you add the negative of a point to itself, in which case there will only be two intersection points but the result of those operations is well-defined as the original point and 0 respectively.

The reason why the third point is negative is because the three points on the line are collinear. This has the side effect that the third point cancels out the value of the other two points to satisfy the relation. As a side effect, all of the points sum to 0.

So graphically, once the point that lies on the same line as the two points being adding is found, by drawing a line that crosses these two points, it is mirrored over the X axis to get the final resulting point. The reason is because the point on the line is actually the negative of the result, and it's necessary that this point be negative to satisfy the relation P + Q - R = 0, so the R on the line is negative and it cancels out the P and Q.

It's also the reason why adding a point to its negative, like -R to R, will give you zero, because the line formed becomes vertical, indicating there is no such point on the curve to satisfy the relation (the point "0" means "no such point on the curve". It is also sometimes called "point at infinity"). This also explains why adding the point "0" to a point gives you the same point. Any line formed from "0" to another point will only include two points, and thus the result is taken as the non-null point. In this way "0" acts as an identity operator.

Point Doubling

Point doubling is when a point P is added to itself. The normal point addition method cannot be used, because it only works when the two points are different. However, the two operators refer to the same point so a different method is needed.

It is done by taking the tangent line of the point, and finding the other point on the curve this line intersects, and then "flipping" that point across the x-axis (this is possible because elliptic curves are symmetrical across the x-axis). This new point is P + P, or 2P.

This procedure can be used to repeatedly produce the doubles of these points such as 4G, 8G, 16G and so on. In each case you take the result of the previous doubling and inset it as operands of the next doubling operation.

Point Negation

When you "flip" a point, you are changing its sign. Flipping the point a second time changes its sign back just like in conventional arithmetic. This can be used to implement point subtraction, by negating the second point before adding them.

The commutative property holds because it doesn't matter which way you add Q + P or P + Q; the line is the same. And the associative property also holds because it doesn't matter which points you add first before others, you will ultimately arrive at the same point.

Point Multiplication

It's possible to combine the two processes of point addition and point doubling to multiply arbitrary numbers, otherwise known as point multiplication. You can implement point multiplication as a series of point doubles and point additions or by using the Montgomery ladder method for computing point multiplications.

Modular Multiplicative Inverse

The modular multiplicative inverse of a point P^-1 is the problem of finding a factor x such that xP ≅ 1 (mod p), where p is the curve group order. This is a congruence relation, for which there are some algorithms to this problem listed at. Modular Multiplicate Inverse can be combined with point multiplication to implement point division, by inverting the second operand.