elliptic curve cryptography is a type of public key or asymmetric cryptography based on the discrete logarithm problem expressed by addition and multiplication at points on an elliptic curve.
Figure 4-2 is an example of an elliptic curve, similar to the one used by bitcoin.
Reading: Access bitcoin wallet
bitcoin uses a specific elliptic curve and set of mathematical constants, as defined in a standard called secp256k1, set by the national institute of standards and technology (nist). the secp256k1 curve is defined by the following function, which produces an elliptic curve:
the mod p (prime number modulus p) indicates that this curve is over a finite field of prime order p, also written as , where p = 2256 – 232 – 29 – 28 – 27 – 26 – 24 – 1, a very large prime number.
Because this curve is defined over a finite field of prime order rather than over the real numbers, it looks like a pattern of scattered dots in two dimensions, making it difficult to visualize. however, the math is identical to that of an elliptic curve over real numbers. As an example, Figure 4-3 shows the same elliptic curve over a much smaller finite field of first order 17, showing a pattern of points on a grid. bitcoin secp256k1’s elliptic curve can be thought of as a much more complex pattern of points on an unfathomable grid.
then, for example, the following is a point p with coordinates (x,y) which is a point on the curve secp256k1. you can verify this yourself using python:
In the mathematics of elliptic curves, there is a point called the “point at infinity”, which roughly corresponds to the role of 0 plus. on computers, it is sometimes represented by x = y = 0 (which does not satisfy the elliptic curve equation, but is an easy separate case that can be verified).
There is also an operator +, called “addition”, which has some properties similar to the traditional addition of real numbers that children learn in elementary school. given two points p1 and p2 on the elliptic curve, there is a third point p3 = p1 + p2, also on the elliptic curve.
Geometrically, this third point p3 is calculated by drawing a line between p1 and p2. this line will intersect the elliptic curve at exactly one additional place. let us call this point p3′ = (x, y). then reflect in the x-axis to get p3 = (x, -y).
There are a couple of special cases that explain the need for the “point at infinity”.
if p1 and p2 are the same point, the line “between” p1 and p2 must be extended to be the tangent on the curve at this point p1. this tangent will intersect the curve exactly at a new point. you can use calculus techniques to determine the slope of the tangent line. these techniques oddly enough work, even though we are restricting our interest to points on the curve with two integer coordinates!
in some cases (ie, if p1 and p2 have the same x-values but different y-values), the tangent line will be exactly vertical, in which case p3 = “point at infinity”.
if p1 is the “point at infinity”, then the sum p1 + p2 = p2. Similarly, if p2 is the point at infinity, then p1 + p2 = p1. this shows how the point at infinity plays the role of 0.
It turns out that + is associative, which means that (a+b)c = a(b+c). that means we can write a+b+c without parentheses without any ambiguity.
Now that we have defined addition, we can define multiplication in the standard way that extends addition. for a point p on the elliptic curve, if k is an integer, then kp = p + p + p + … + p (k times). note that k is sometimes confusingly called the “exponent” in this case.