How does ECDSA work in Bitcoin

ECDSA (‘Elliptical Curve Digital Signature Algorithm’) is the cryptography behind private and public keys used in Bitcoin. It consists of combining the math behind finite fields and elliptic curves to create one way equations, meaning you can choose your private key (some number) and easily calculate your public key (some other number). However, I can’t take my public key (or anybody else’s for that matter) and easily calculate their private key. In fact, for Bitcoin it would take trillions of computers trillions of years of continuous guessing of different private keys to figure out which one creates a given public key.

Let’s see how!

Finite Fields:

A finite field is exactly like it sounds, a finite set of numbers. The real numbers are an infinite set of numbers, but the set (3, 97, 205, 1,678, 17) is a finite set of numbers. A more interesting and useful set of numbers are the set of integers modulo p, where p is a prime number.

Modulo is like addition on a clock or remainder math. For example modulo 12 would be adding around a clock, so (1 + 4) modulo 12 = 5, but (1+15) modulo 12 = 4. Why? Think about a clock. 1 + 15 = 16 and 16 is 4 hours after 12. Or think about remainder math. 16 / 12 = 1 remainder 4 so the remainder is 4.

You can also follow the same logic to do subtraction and multiplication. Check this out for more examples.

Elliptic Curve:

Elliptic curves are the set of points described by the equation:

The below are examples of elliptic curves:

Elliptic curves are useful because of their various properties. Firstly, elliptic curves are groups. Groups are defined in mathematics if they have closure, associativity, an identity element, and an inverse for each element.

1. Closure: If a and b are in a group G, then a + b is in the group G
2. Associativity: (a + b) + c = a + (b + c)
3. Identity Element: a + 0 = 0 + a = a
4. For every a there exists b such that a + b = 0
5. For Abelian Groups only, commutativity: a + b = b + a

Further, elliptic curves have some of their own specific group laws.

1. The identity element is the point at infinity, 0
2. The inverse of the point P is the one symmetric about the x axis
3. Addition is defined as: given three aligned, non-zero points, P, Q, and R you have P + Q + R = 0. The order does not matter for these three points, so P + (Q+R) = 0, (P+Q) + R = 0, (P+R) + Q = 0, etc. This allows us to prove elliptic curves are both commutative, and associative.

The above equation also gives us an equation to add two points together and calculate the third point. As stated before, we know that when a line passes through two points on a curve, it will pass through a third point. And we know that

P + Q + R = 0

so,

P + Q = -R

And we know that -R is just the inverse of the point R reflected across the x-axis.

What about the case where P is tangent to the curve, such that there are only two intersecting points.

Since, P is tangent to the curve, you have P = Q and therefore, P + P = -R from the equation above. Or, 2P = -R. This is called point doubling for elliptic curves.

Finite Fields + Elliptic Curves:

When you combine finite fields and elliptic curves you get the magic of cryptography. The equation for an elliptic curve transforms to the following:

Basically, we added mod p to the end of the elliptic curve equations.

And if we plot a finite field over an elliptic curve, we get the following examples:

Note how the points are symmetric across a certain line, meaning we can still do point addition P + Q = -R where we draw a line connecting P, Q, and R and reflect R over the x axis to find -R. In a finite field, a line looks very different than an infinite field. It is similar to the game galaxy where you go off the top of the screen and you end up at the bottom of the screen. Below you can see P, Q, and R being connected through a line.

And because finite fields over elliptic curves are still in a group, we retain all of the properties for a mathematical group described above.

Scalar Multiplication and Order

Recall that a line passing through two points on an elliptic curve will pass through a third point and the equation to calculate said third point is P + Q =-R (point addition). Further, if P is tangent to elliptic curve then P = Q and P + P = -R → or 2P = -R (point doubling).

Point addition and point doubling allow us to define scalar multiplication for elliptic curves such that, xP = R where x is a scalar, P is a point tangent to the curve and R is the resulting point from adding P on to itself x times. For example:

11P = R

P + 10P = R

P + 2(5P) = R

P + 2(P + 4P) = R

P + 2(P + 2(2P)) = R

In this example, we would take point P and add point P to get new point F.

P + 2(P + (2F)) = R

Take point F and add F to it to get new point C.

P + 2(P + C) = R

Add P and C together to get point D.

P + 2(D) = R

Add point D to point D to get point E.

P + E = R

Add point P and point E to get R! So you can see how point addition and point doubling allows us to calculate scalar multiplication for xP = R.

Elliptic curves over finite fields have the same property. We can continually add P on to itself creating scalar multiplication.

Think back to the clock image we used for modulo operations. When adding P to itself over and over, it is similar to moving P around a clock. Eventually you will get back to where you started and continually cycle through the same points.

Let’s check out an example using the equation:

and if we choose the point P = (3,6), we can then cycle through the scalar multiplication of P to understand how many times we add P to itself to get back to the point (3,6).

We can see that P = (3,6) and it takes 5Ps to get back to the same point (3,6). That means P = (3,6) and so does 6P, 11P, 16P…etc. Check out this awesome calculator and visual tool from Andrea Corbellini to verify and to try other examples.

The key point to the above example is calculating the order of a subgroup generated by point P. The order of P is defined as the smallest positive integer n such that nP = 0. So in our example, the order of the subgroup based on point P is 5, meaning 5P = 0. There is no smaller positive scalar multiplier of point P that will yield the point 0.

Bringing this all together, our example defines the following:

1. Prime modulo of the finite field = 97
2. The elliptic curve described above where a = 2 and b = 3
3. A random point P = (3,6) — this is called the base point
4. The order of the subgroup (set of cyclic points based on P) = 5

ECDSA and Bitcoin

For Bitcoin, we have the following parameters:

1. Prime modulo: 2²⁵⁶ - 2³² - 2⁹ - 2⁸ - 2⁷ - 2⁶ - 2⁴ - 1 → this is a really really big number approximately equal to all of the atoms in the universe. It is also represented in hexadecimal as: FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F
2. Elliptic curve where a = 0 and b = 7
3. Base point P in hexadecimal = 04 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8
4. Order in hexadecimal = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141

These numbers were not arbitrarily chosen. There is actually a cryptography standard run by the organization, Standards for Efficient Cryptography Group (SEC) and Bitcoin follows the secp256k1 standard.

Therefore, the private key for Bitcoin is just an arbitrarily chosen number between 1 and the order above. The public key can easily be derived through scalar multiplication with the formula:

public key = private key * base point P

This is just performing scalar multiplication on base point P multiplied by your private key the same way we described scalar multiplication above with xP = R. The above example we showed how x = 11 and calculated 11P = R using point doubling and point addition. The difference between this example and Bitcoin is that Bitcoin uses extremely large numbers in hexadecimal form, but the process of using point doubling and point addition is the same.

Once you choose your private key and multiply it by the base point P, you get a new point (x,y) in the finite field/elliptic curve. This is your public key. It is computationally easy to use your private key and multiply it by the base point to get the public key, but it is computationally difficult to start with the public key and work backwards to calculate the private key. The equation is a one way street.

The private key and public key are now available to create digital signatures like we discussed in the last post.

For brevity sake, I am leaving out the mathematical proofs for digital signatures but if you are interested, check it out here.

Special thanks to:

• Andrea Corbellini and her blog posts
• This post from
  CoinDesk
• Jimmy Song
  and his videos