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 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