Moving Around on a Line

Before we start thinking about what's involved in driving around on a curve, let's use an easier scenario and imagine driving around on a line (see Figure 7-1).

If we have a straight line that passes through the origin (i.e., the point at x = 0, y = 0), we can create a new point on the line by using two points A and B to create a point C by simply adding A and B. Here is the obvious formula for adding two points:

We need to add the two x-coordinates to get a new x (simply 1 + 3 = 4) and add the two y-coordinates (also 1 + 3 = 4). Note that we can also use a simple geometric trick to generate point C without using arithmetic: Simply start at point B and then move at the same angle and amount as point A is from the origin.

Figure 7-1: Adding two points (A and B) on a line to get point C

For a line, this addition process is very simple but is not useful for cryptography (and equally not useful for creating driving instructions for our "car" that are hard to reverse engineer). But as you'll see, the process for adding points is very different with elliptical curves.

Elliptic Curve Digital Signature Algorithm (ECDSA)

Instead of integer factorization-based schemes, digital signatures in Bitcoin are based on ECC. Although integer factorization works well in principle, faster computers and better algorithms to factor integers have over time increasingly required the use of ever larger prime factors to ensure reasonable security. The recommended size of encryption keys used for RSA encryption is between 1024 and 4096 bits. In contrast, elliptic curves offer the same functionality but are not affected by advances in factoring integers; therefore, shorter keys can be used (a 256-bit key in ECC is believed to offer comparable security to a 1024-bit key in an RSA-type scheme). In short, ECC is thought to be stronger than methods based on factoring integers for the same key length.

Bitcoin uses elliptic curves to create digital signatures, specifically by using a protocol called the Elliptic Curve Digital Signature Algorithm (ECDSA). An elliptic curve is any two-dimensional curve that satisfies the equation:

A few sample curves that satisfy this equation are shown in Figure 7-2. Public/private key pairs are generated by choosing points on these elliptic curves that are mathematically related to each other.

Figure 7-2: Different elliptic curves can be generated using different parameters in our starting equation.

As with the property of a straight line, when you add the coordinates of any two points on the curve, the result is another point on the curve.

However, with elliptic curves addition has a special meaning and is defined as follows:

Clearly, this formula for adding two points is much more complex than the addition formula we used for straight lines. Figure 7-3 shows an example elliptic curve with two points A and B and the resulting point C created by following these addition rules.

Figure 7-3: Two points (A and B) on an elliptic curve are added to create point C, using our special method of addition.

In the example in Figure 7-3, points A and B are not special in any way. Choosing different A and B points would lead to a different point C (Figure 7-4), which is the whole point of using this type of addition for cryptography: In the earlier jelly donut incident, Crowley had to drive a long, circuitous route back to his house so Satoshi's home address would remain obscured. Repeatedly jumping between points on the elliptic curve using this method of addition can help you obscure your private key in a digital signature system in the same way, as you'll soon see.

Figure 7-4: When different points A and B are chosen, a different point C is created.

Similar to lines, you can use a geometric trick to calculate the sum of adding two points on elliptic curves (i.e., without needing to do the tedious arithmetic). Simply draw a line through points A and B, and find another location where the line intersects the curve. Then draw a vertical line starting at this point of intersection and see where else it crosses the elliptic curve. This second crossing is point C (Figure 7-5).

Figure 7-5: Using simple geometry, you can find point C by just drawing a line through points A and B and then moving vertically to find point C.

A fundamental property of elliptic curves is that any line that intersects at least two points must also intersect a third (except for vertical lines and lines that are tangent to a point on the curve^[1]).

Of course, if we want to "drive around" our elliptic curve, as in our conceptual example involving a car, it's somewhat awkward that we need two points to generate every new point: As with a car, it would be ideal to go from a single point to another single point so our "car" only has to be in one place at a time. Fortunately, this is possible with elliptic curves as well by using a form of multiplication to multiply a point on the curve by an integer, which is the same as adding a point to itself multiple times. It might seem like the geometric trick does not work in this case. How do you draw a straight line through two points if they are in the same place? You can probably guess by imagining what happens when you consider adding two points, A and B, that are very close together: The line that passes through A and B will resemble the tangent to the curve near those points. So when in Figure 7-6), so if a tangent line touches the curve only one more time it is still counted as "intersecting three times." we add A + A (or equivalently, multiply A by 2), we draw a tangent to the curve at point A and find where else it intersects. Then we draw a vertical line, as before, to find the resulting point, 2A (Figure 7-6).

Figure 7-6: With only one starting point, we can point multiply by 2 by using the tangent line through point A.

To calculate 3A, you first calculate 2A, as we just did, and then adding an additional A is just like adding any two no overlapping points. In elliptic curve terminology, calculating kA, where k is an arbitrary integer, is called point multiplication. Calculating kA for large values of k is computationally expensive without efficient implementations.

So as with our conceptual example, we'll now use point multiplication to "drive" from one point on the curve to another. In ECC, point multiplication is used to generate the public key from the private key. However, there will be one important difference between our jelly-filled donut story and how ECC really works. In our story, Satoshi's house represented a private key and Crowley's house a public key, but in ECC the starting point and destination point are both publicly known—it is only the path between them that is secret. So it is in fact the path that is the private key; the destination point is the public key (as it was before), and the starting point is simply a standard location that everyone agrees to use. In ECC it's as if Satoshi's home address were widely known to be in the center of a very complex labyrinth—everyone knows where he lives, but no one knows how to get there. Given a previously agreed-upon point on the curve, G, and a private key, d, the public key, Q, is calculated by point multiplication such that Q = dG. Note that the public key is a point on the curve but the private key is just an integer.

So far we've been depicting elliptic curves as smooth, continuous functions that extend into infinity. However, computers have limited memory, and it isn't possible to use real-valued numbers as coordinates for points on the curve without introducing rounding errors (which are unacceptable in cryptography). For practical implementations, only integer-valued points on elliptic curves are allowed, and modular arithmetic is used to keep all of the points within certain bounds (from 0 to 512, for example). This technique of using only integer-valued points is best illustrated with an example. Let's first choose the same elliptic curve that Bitcoin uses, which is called a Koblitz curve (Figure 7-7), using the parameters a = 0 and b = 7.

Figure 7-7: A Koblitz curve

We then choose a prime modulo p so that the elliptic curve satisfies this equation:

not eI In this type of math notation, the modulo operation is performed after the additions so first you calculate x2 + ax + b and then you perform mod p on the result.

256 32 9 8 7

Bitcoin uses a very large p value (specifically p = 2 - 2 - 2- 2- 2 - 26 - 24 - 1), which is important for cryptographic strength, but we can use a smaller number to illustrate how "driving around on integer-valued points on a Koblitz curve" works. Let's choose p = 67. In fact, many curves satisfy the modular equation (namely, every curve where p is added to or subtracted from the b parameter any number of times; see the left-hand chart in Figure 7-8), and from those curves we can use all of the points that have integer-valued coordinates (shown in Figure 7-8 as dots).

Figure 7-8: On the left is a standard picture of the elliptic curve in the form we're familiar with (the bold curve) with additional curves that are drawn by using other multiples of p (the thin curves.) On the right, we've taken a larger section of the coordinate plane that is an expansion of the upper-right quadrant. This is the section of the curve that is most convenient when using the integer-based variant of ECC.

Given the choice of p = 67, only 79 unique points with integer-valued coordinates exist, and 78 of them can be found in the upper-right quadrant from 0 < x < 66 and 0 < y < 66 (shown in the chart on the right in Figure 7-8; note that the left chart shows the entire range). The number of unique points, n, is called the order of the curve. The 79th point is the zero point, which is not at (0,0) as you might expect but rather is the point at y = infinity. The zero point is important because it is valid output from an addition or point multiplication operation and therefore needs to be carefully accounted for (see the sample code in "Pseudocode for Elliptic Point Summation and Point Multiplication" on page 158).

As a last step before we can generate public/private key pairs, we need to choose one of the 79 points to be a generator point, G. The generator needs to have the property that one can calculate every one of the other 78 points by multiplying G by some integer, k (i.e., so you can generate every point by calculating G, 2G, 3G, 79G). If we choose the point (5,47) as our generator point, we can check whether by successively incrementing k we can travel to every point in the set (see Figure 7-9).

Figure 7-9: On the left, starting with point G, we multiply G successively to create new points at 2G, 3G, and 4G. On the right, you see what happens when this multiplication is repeated even further.

If the order of the curve is prime (i.e., there is a prime number of points), any point except the zero point works equally well as a generator. If the order is not prime, regardless of the k value, some points will travel only to a subset of points (which can lead to a reduction in cryptographic strength). In our case, we can safely use the point (5,47) because it generates all the other 78 points (as depicted in the chart in Figure 7-9).

To return to our conceptual car example, point G in this figure could be Satoshi's house and point 4G, for example, could be Crowley's house. The points between represent the complicated drive through Cryptoville. Until you carry out the point multiplication operation, it certainly isn't obvious what the path from G to 4G is. The 4 in 4G gives away the answer, namely that the path connecting those points can be found by taking three steps from G. However, if G and 4G were instead labeled A and B, it would take a long time to guess how to get from one to the other. In other words, if you know only the start and end points (i.e., the public key), it would take a long time to guess the path (i.e., the private key). But if you know the starting point and the path, then calculating the end point is easy. In terms of Bitcoin, it means that if someone knows the Bitcoin address that contains your money (which is based on the public key), it is still impossible for that person to figure out your private key to spend the bitcoins at that address.

• [1] Exact vertical lines are considered to hit a third point at y = infinity. Points where the line is tangent to the curve count as two intersection points (even though it looks like only one