ch03.asciidoc

Elliptic Curve Cryptography

The previous two chapters covered some fundamental math. We learned how finite fields work and what an elliptic curve is. In this chapter, we’re going to combine the two concepts to learn elliptic curve cryptography. Specifically, we’re going to build the primitives needed to sign and verify messages, which is at the heart of what Bitcoin does.

Elliptic Curves over Reals

We discussed in [chapter_elliptic_curves] what an elliptic curve looks like visually because we were plotting the curve over real numbers. Specifically, it’s not just integers or even rational numbers, but all real numbers. Pi, sqrt(2), e+7th root of 19, and the like are all real numbers.

This worked because real numbers are also a field. Unlike a finite field, there are an infinite number of real numbers, but otherwise the same properties hold:

1. If a and b are in the set, a + b and a ⋅ b are in the set.

2. 0 exists and has the property a + 0 = a.

3. 1 exists and has the property a ⋅ 1 = a.

4. If a is in the set, –a is in the set, which is defined as the value that makes a + (–a) = 0.

5. If a is in the set and is not 0, a^–1 is in the set, which is defined as the value that makes a ⋅ a^–1 = 1.

Clearly, all of these are true: normal addition and multiplication apply for the first part, the additive and multiplicative identities 0 and 1 exist, –x is the additive inverse, and 1/x is the multiplicative inverse.

Real numbers are easy to plot on a graph. For example, y² = x³ + 7 can be plotted like secp256k1 over real numbers.

Figure 1. secp256k1 over real numbers

It turns out we can use the point addition equations over any field, including the finite fields we learned about in [chapter_finite_fields]. The only difference is that we have to use the addition/subtraction/multiplication/division as defined in [chapter_finite_fields], not the "normal" versions that the real numbers use.

Elliptic Curves over Finite Fields

So what does an elliptic curve over a finite field look like? Let’s look at the equation y² = x³ + 7 over F₁₀₃. We can verify that the point (17,64) is on the curve by calculating both sides of the equation:

• y² = 64² % 103 = 79
• x³ + 7 = (17³+7) % 103 = 79

We’ve verified that the point is on the curve using finite field math.

Because we’re evaluating the equation over a finite field, the plot of the equation looks vastly different (Elliptic curve over a finite field).

Figure 2. Elliptic curve over a finite field

As you can see, it’s very much a scattershot of points and there’s no smooth curve here. This is not surprising since the points are discrete. About the only pattern is that the curve is symmetric right around the middle, because of the y² term. The graph is not symmetric over the x-axis as in the curve over reals, but about halfway up the y-axis due to there not being negative numbers in a finite field.

What’s amazing is that we can use the same point addition equations with the addition, subtraction, multiplication, division, and exponentiation as we defined them for finite fields, and everything still works. This may seem surprising, but abstract math has regularities like this despite being different from the traditional modes of calculation you may be familiar with.

code-ch03/answers.py

Coding Elliptic Curves over Finite Fields

Because we defined an elliptic curve point and defined the +, - ,* and / operators for finite fields, we can combine the two classes to create elliptic curve points over a finite field:

link:code-ch03/examples.py[role=include]

When initializing Point, we will run through this part of the code:

link:code-ch03/ecc.py[role=include]

The addition (+), multiplication (), exponentiation (*), and not equals (!=) operators here use the add, mul, pow, and ne methods from FiniteField, respectively, and not the integer equivalents. Being able to do the same equation but with different definitions for the basic arithmetic operators is how we construct an elliptic curve cryptography library.

We’ve already coded the two classes that we need to implement elliptic curve points over a finite field. However, to check our work, it will be useful to create a test suite. We will do this using the results of Exercise 1:

link:code-ch03/ecc.py[role=include]

1. We pass in FieldElement objects to the Point class for initialization. This will, in turn, use all the overloaded math operations in FieldElement.

We can now run this test like so:

>>> import ecc
>>> from helper import run  # (1)
>>> run(ecc.ECCTest('test_on_curve'))
.
----------------------------------------------------------------------
Ran 1 test in 0.001s

OK

1. helper is a module with some very useful utility functions, including the ability to run unit tests individually.

Point Addition over Finite Fields

We can use all the same equations over finite fields, including the linear equation:

• y = mx + b

It turns out that a "line" in a finite field is not quite what you’d expect (Line over a finite field).

Figure 3. Line over a finite field

The equation nevertheless works, and we can calculate what y should be for a given x.

Remarkably, point addition works over finite fields as well. This is because elliptic curve point addition works over all fields! The same exact formulas we used to calculate point addition over reals work over finite fields. Specifically, when x₁ ≠ x₂:

• P₁ = (x₁,y₁), P₂ = (x₂,y₂), P₃ = (x₃,y₃)
• P₁ + P₂ = P₃
• s = (y₂ – y₁)/(x₂ – x₁)
• x₃ = s² – x₁ – x₂
• y₃ = s(x₁ – x₃) – y₁

And when P₁ = P₂:

• P₁ = (x₁,y₁), P₃ = (x₃,y₃)
• P₁ + P₁ = P₃
• s = (3x₁² + a)/(2y₁)
• x₃ = s² – 2x₁
• y₃ = s(x₁ – x₃) – y₁

All of the equations for elliptic curves work over finite fields, which sets us up to create some cryptographic primitives.

Coding Point Addition over Finite Fields

Because we coded FieldElement in such a way as to define add, sub, mul, truediv, pow, eq, and ne, we can simply initialize Point with FieldElement objects and point addition will work:

link:code-ch03/examples.py[role=include]

code-ch03/answers.py

code-ch03/answers.py

Scalar Multiplication for Elliptic Curves

Because we can add a point to itself, we can introduce some new notation:

• (170,142) + (170,142) = 2 ⋅ (170,142)

Similarly, because we have associativity, we can actually add the point again:

• 2 ⋅ (170,142) + (170,142) = 3 ⋅ (170, 142)

We can do this as many times as we want. This is what we call scalar multiplication. That is, we have a scalar number in front of the point. We can do this because we have defined point addition and point addition is associative.

One property of scalar multiplication is that it’s really hard to predict without calculating (see Scalar multiplication results for y² = x³ + 7 over F₂₂₃ for point (170,142)).

Figure 4. Scalar multiplication results for y² = x³ + 7 over F₂₂₃ for point (170,142)

Each point is labeled by how many times we’ve added the point. You can see that this is a complete scattershot. This is because point addition is nonlinear and not easy to calculate. Performing scalar multiplication is straightforward, but doing the opposite, point division, is not.

This is called the discrete log problem and is the basis of elliptic curve cryptography.

Another property of scalar multiplication is that at a certain multiple, we get to the point at infinity (remember, the point at infinity is the additive identity or 0). If we imagine a point G and scalar-multiply until we get the point at infinity, we end up with a set:

• { G, 2G, 3G, 4G, ... nG } where nG = 0

It turns out that this set is called a group, and because n is finite, we have a finite group (or more specifically, a finite cyclic group). Groups are interesting mathematically because they behave well with respect to addition:

• G + 4G = 5G or aG + bG = (a + b)G

When we combine the fact that scalar multiplication is easy to do in one direction but hard in the other and the mathematical properties of a group, we have exactly what we need for elliptic curve cryptography.

Why Is This Called the Discrete Log Problem?

You may be wondering why the problem of reversing scalar multiplication is referred to as the discrete log problem.

We called the operation between the points "addition," but we could easily have called it a point "operation." Typically, a new operation that you define in math is denoted with the dot operator (⋅). The dot operator is also used for multiplication, and it sometimes helps to think that way:

• P₁ ⋅ P₂ = P₃

When you do lots of multiplying, that’s the same as exponentiation. Scalar multiplication when we called it "point addition" becomes scalar exponentiation when thinking "point multiplication":

• P⁷ = Q

The discrete log problem in this context is the ability to reverse this equation, which ends up being:

• log_PQ = 7

The log equation on the left has no analytically calculable algorithm. That is, there is no known formula that you can plug in to get the answer generally. This is all a bit confusing, but it’s fair to say that we could call the problem the "discrete point division" problem instead of the discrete log problem.

code-ch03/answers.py

Scalar Multiplication Redux

Scalar multiplication is adding the same point to itself some number of times. The key to making scalar multiplication into public key cryptography is using the fact that scalar multiplication on elliptic curves is very hard to reverse. Note the previous exercise. Most likely, you calculated the point s ⋅ (47,71) in F₂₂₃ for s from 1 until 21. Here are the results:

link:code-ch03/examples.py[role=include]

If you look closely at the numbers, there’s no real discernible pattern to the scalar multiplication. The x coordinates don’t always increase or decrease, and neither do the y coordinates. About the only pattern is that between 10 and 11, the x coordinates are equal (10 and 11 have the same x, as do 9 and 12, 8 and 13, and so on). This is due to the fact that 21 ⋅ (47,71) = 0.

Scalar multiplication looks really random, and that’s what gives this equation asymmetry. An asymmetric problem is one that’s easy to calculate in one direction, but hard to reverse. For example, it’s easy enough to calculate 12 ⋅ (47,71). But if we were presented with this:

• s ⋅ (47,71) = (194,172)

would we be able to solve for s? We can look up the results shown earlier, but that’s because we have a small group. We’ll see in Defining the Curve for Bitcoin that when we have numbers that are a lot larger, discrete log becomes an intractable problem.

Mathematical Groups

The preceding math (finite fields, elliptic curves, combining the two) was really to bring us to this point. What we actually want to generate for the purposes of public key cryptography are finite cyclic groups, and it turns out that if we take a generator point from an elliptic curve over a finite field, we can generate a finite cyclic group.

Unlike fields, groups have only a single operation. In our case, point addition is the operation. Groups also have a few other properties, like closure, invertibility, commutativity, and associativity. Lastly, we need the identity.

Let’s look at each property, starting with that last one.

Identity

If you haven’t guessed by now, the identity is defined as the point at infinity, which is guaranteed to be in the group since we generate the group when we get to the point at infinity. So:

• 0 + A = A

We call 0 the point at infinity because visually, it’s the point that exists to help the math work out (Vertical line "intersects" a third time at the point at infinity).

Figure 5. Vertical line "intersects" a third time at the point at infinity

Closure

This is perhaps the easiest property to prove since we generated the group in the first place by adding G over and over. Thus, if we have two different elements that look like this:

• aG + bG

We know that the result is going to be:

• (a + b)G

How do we know if this element is in the group? If a+b < n (where n is the order of the group), then we know it’s in the group by definition. If a+b >= n, then we know a < n and b < n, so a+b < 2n, so a+b–n < n:

• (a + b – n)G = aG + bG – nG = aG + bG – 0 = aG + bG

More generally, (a + b)G = ((a + b) % n)G, where n is the order of the group.

So we know that this element is in the group, proving closure.

Invertibility

Invertibility is easy to depict (Each point is invertible by taking the reflection over the x-axis).

Figure 6. Each point is invertible by taking the reflection over the x-axis

Mathematically, we know that if aG is in the group, (n – a)G is also in the group. You can add them together to get aG + (n – a)G = (a + n – a)G = nG = 0.

Commutativity

We know from point addition that A + B = B + A (The line through the points doesn’t change).

Figure 7. The line through the points doesn’t change

This means that aG + bG = bG + aG, which proves commutativity.

Associativity

We know from point addition that A + (B + C) = (A + B) + C (see Figures #a_b_c_case_one and #a_b_c_case_two).

Figure 8. (A + B) + C: A + B is computed first before C is added

Figure 9. A + (B + C): B + C is added first before adding A (note that this results in the same point as in (A + B) + C: A + B is computed first before C is added)

Thus, aG + (bG + cG) = (aG + bG) + cG, proving associativity.

code-ch03/answers.py

Coding Scalar Multiplication

What we’re trying to do with Exercise 5 is this:

link:code-ch03/examples.py[role=include]

We want to be able to scalar-multiply the point with some number. Thankfully, there’s a method in Python called rmul that can be used to override the front multiplication. A naive implementation looks something like this:

class Point:
    ...
    def __rmul__(self, coefficient):
        product = self.__class__(None, None, self.a, self.b) # (1)
        for _ in range(coefficient): # (2)
            product += self
        return product

1. We start the product at 0, which in the case of point addition is the point at infinity.

2. We loop coefficient times and add the point each time.

This is fine for small coefficients, but what if we have a very large coefficient—that is, a number that’s so large that we won’t be able to get out of this loop in a reasonable amount of time? For example, a coefficient of 1 trillion is going to take a really long time.

There’s a cool technique called binary expansion that allows us to perform multiplication in log₂(n) loops, which dramatically reduces the calculation time for large numbers. For example, 1 trillion is 40 bits in binary, so we only have to loop 40 times for a number that’s generally considered very large:

class Point:
    ...
link:code-ch03/ecc.py[role=include]

1. current represents the point that’s at the current bit. The first time through the loop it represents 1 × self; the second time it will be 2 × self, the third time 4 × self, then 8 × self, and so on. We double the point each time. In binary the coefficients are 1, 10, 100, 1000, 10000, etc.

2. We start the result at 0, or the point at infinity.

3. We are looking at whether the rightmost bit is a 1. If it is, then we add the value of the current bit.

4. We need to double the point until we’re past how big the coefficient can be.

5. We bit-shift the coefficient to the right.

This is an advanced technique. If you don’t understand bitwise operators, think of representing the coefficient in binary and only adding the point where there are 1’s.

With add and rmul, we can start defining some more complicated elliptic curves.

Defining the Curve for Bitcoin

While we’ve been using relatively small primes for the sake of examples, we are not restricted to such small numbers. Small primes mean that we can use a computer to search through the entire group. If the group has a size of 301, the computer can easily do 301 computations to reverse scalar multiplication or break discrete log.

But what if we made the prime larger? It turns out that we can choose much larger primes than we’ve been using. The security of elliptic curve cryptography depends on computers not being able to go through an appreciable fraction of the group.

An elliptic curve for public key cryptography is defined with the following parameters:

• We specify the a and b of the curve y² = x³ + ax + b.

• We specify the prime of the finite field, p.

• We specify the x and y coordinates of the generator point G.

• We specify the order of the group generated by G, n.

These numbers are known publicly and together form the cryptographic curve. There are many cryptographic curves and they have different security/convenience trade-offs, but the one we’re most interested in is the one Bitcoin uses: secp256k1. The parameters for secp256k1 are these:

• a = 0, b = 7, making the equation y² = x³ + 7

• p = 2²⁵⁶ – 2³² – 977

• G_x =
  0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798

• G_y =
  0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8

• n = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141

G_x refers to the x coordinate of the point G and G_y the y coordinate. The numbers starting with 0x are hexadecimal numbers.

There are a few things to notice about this curve. First, the equation is relatively simple. Many curves have a and b values that are much bigger.

Second, p is extremely close to 2²⁵⁶. This means that most numbers under 2²⁵⁶ are in the prime field, and thus any point on the curve has x and y coordinates that are expressible in 256 bits each. n is also very close to 2²⁵⁶. This means any scalar multiple can also be expressed in 256 bits.

Third, 2²⁵⁶ is a huge number (see sidebar). Amazingly, any number below 2²⁵⁶ can be stored in 32 bytes. This means that we can store the private key relatively easily.

How Big is 2²⁵⁶?

2²⁵⁶ doesn’t seem that big because we can express it succinctly, but in reality, it is an enormous number. To give you an idea, here are some relative scales:

2²⁵⁶ ~ 10⁷⁷

• Number of atoms in and on Earth ~ 10⁵⁰
• Number of atoms in the solar system ~ 10⁵⁷
• Number of atoms in the Milky Way ~ 10⁶⁸
• Number of atoms in the universe ~ 10⁸⁰

A trillion (10¹²) computers doing a trillion computations every trillionth (10^–12) of a second for a trillion years is still less than 10⁵⁶ computations.

Think of finding a private key this way: there are as many possible private keys in Bitcoin as there are atoms in a billion galaxies.

Working with secp256k1

Since we know all of the parameters for secp256k1, we can verify in Python whether the generator point, G, is on the curve y² = x³ + 7:

link:code-ch03/examples.py[role=include]

Furthermore, we can verify in Python whether the generator point, G, has the order n:

link:code-ch03/examples.py[role=include]

Since we know the curve we will work in, this is a good time to create a subclass in Python to work exclusively with the parameters for secp256k1. We’ll define the equivalent FieldElement and Point objects, but specific to the secp256k1 curve. Let’s start by defining the field we’ll be working in:

link:code-ch03/ecc.py[role=include]
...
link:code-ch03/ecc.py[role=include]

We’re subclassing the FieldElement class so we don’t have to pass in P all the time. We also want to display a 256-bit number consistently by filling 64 characters so we can see any leading zeros.

Similarly, we can define a point on the secp256k1 curve and call it S256Point:

link:code-ch03/ecc.py[role=include]
...
link:code-ch03/ecc.py[role=include]

1. In case we initialize with the point at infinity, we need to let x and y through directly instead of using the S256Field class.

We now have an easier way to initialize a point on the secp256k1 curve, without having to define a and b every time like we have to with the Point class.

We can also define rmul a bit more efficiently, since we know the order of the group, n. Since we’re coding Python, we’ll name this with a capital N to make it clear that N is a constant:

link:code-ch03/ecc.py[role=include]
...
class S256Point(Point):
    ...
link:code-ch03/ecc.py[role=include]

1. We can mod by n because nG = 0. That is, every n times we cycle back to zero or the point at infinity.

We can now define G directly and keep it around since we’ll be using it a lot going forward:

link:code-ch03/ecc.py[role=include]

Now checking that the order of G is n is trivial:

link:code-ch03/examples.py[role=include]

Public Key Cryptography

At last, we have the tools that we need to do public key cryptography operations. The key operation that we need is P = eG, which is an asymmetric equation. We can easily compute P when we know e and G, but we cannot easily compute e when we know P and G. This is the discrete log problem described earlier.

The difficulty of discrete log will be essential to understanding signing and verification algorithms.

Generally, we call e the private key and P the public key. Note here that the private key is a single 256-bit number and the public key is a coordinate (x,y), where x and y are each 256-bit numbers.

Signing and Verification

To set up the motivation for why signing and verification exists, imagine this scenario. You want to prove that you are a really good archer, like at the level where you can hit any target you want within 500 yards as opposed to being able to hit any particular target.

Now, if someone could observe you and interact with you, proving this would be easy. Perhaps they would position your son 400 yards away with an apple on his head and challenge you to hit that apple with an arrow. You, being a very good archer, could do this and prove your expertise. The target, if specified by the challenger, makes your archery skill easy to verify.

Unfortunately, this doesn’t scale very well. If, for example you wanted to prove this to 10 people, you would have to shoot 10 different arrows at 10 different targets from 10 different challenges. You could try to do something like have 10 people watch you shoot a single arrow, but since they can’t all choose the target, they can never be sure that you’re not just good at hitting one particular target instead of an arbitrary target. What we want is something that you can do once, that requires no interaction back and forth with the verifiers, but that still proves that you are indeed, a good archer that can hit any target.

If, for example, you simply shot an arrow into a target of your choosing, the people observing afterward wouldn’t necessarily be convinced. After all, you might have painted the target around wherever your arrow happened to land. So what can you do?

Here’s a very clever thing you can do. Inscribe the tip of the arrow with the position of the target that you’re hitting ("apple on top of my son’s head") and then hit that target with your arrow. Now anyone seeing the target can take an X-ray machine and look at the tip of the embedded arrow and see that the tip indeed says exactly where it was going to hit. The tip clearly had to be inscribed before the arrow was shot, so this can prove you are actually a good archer (provided the actual target isn’t just one that you’ve practiced hitting over and over).

This is the same technique we’re using with signing and verification, except what we’re proving isn’t that we’re good archers, but that we know a secret number. We want to prove possession of the secret without revealing the secret itself. We do this by putting the target into our calculation and hitting that target.

Ultimately this is going to be used in transactions, which will prove that the rightful owners of the secrets are spending the bitcoins.

Inscribing the Target

The inscribing of the target depends on the signature algorithm, and in our case that algorithm is called the Elliptic Curve Digital Signature Algorithm, or ECDSA for short.

The secret in our case is e satisfying the following:

• eG = P

where P is the public key and e is the private key.

The target that we’re going to aim at is a random 256-bit number, k. We then do this:

• kG = R

R is now the target that we’re aiming for. In fact, we’re only going to care about the x coordinate of R, which we’ll call r. You may have guessed already that r here stands for random.

We claim at this point that the following equation is equivalent to the discrete log problem:

• uG + vP = kG

where k was chosen randomly, u,v ≠ 0 can be chosen by the signer, and G and P are known. This is due to the fact that:

• uG + vP = kG implies vP = (k – u)G

Since v ≠ 0, we can divide by the scalar multiple v:

• P = ((k – u)/v)G

If we know e, we have:

• eG = ((k – u)/v)G or e = (k – u)/v

This means that any (u,v) combination that satisfies the preceding equation will suffice.

Now suppose we don’t know e, but we can solve uG + vP = kG with some (u,v) combination. Then e = (k–u)/v gives a solution to P = eG while knowing only P and G. In other words, we’d have broken the discrete log problem.

This means to provide a correct u and v, we either have to break the discrete log problem or know the secret e. Since we assume discrete log is hard, we can say e is assumed to be known by the one who came up with u and v.

One subtle thing that we haven’t talked about is that we have to incorporate the purpose of our shooting. This is a contract that gets fulfilled as a result of shooting at the target. William Tell, for example, was shooting so that he could save his son (shoot the target and you get to save your son). You can imagine there would be other reasons to hit the target and other "rewards" that the person hitting the target would receive. This has to be incorporated into our equations.

In signature/verification parlance, this is called the signature hash. A hash is a deterministic function that takes arbitrary data into data of fixed size. This is a fingerprint of the message containing the intent of the shooter, which anyone verifying the message already knows. We denote this with the letter z. This is incorporated into our uG + vP calculation this way:

• u = z/s, v = r/s

Since r is used in the calculation of v, we now have the tip of the arrow inscribed. We also have the intent of the shooter incorporated into u, so both the reason for shooting and the target that is being aimed at are now part of the equation.

To make the equation work, we can calculate s:

• uG + vP = R = kG
• uG + veG = kG
• u + ve = k
• z/s + re/s = k
• (z + re)/s = k
• s = (z + re)/k

This is the basis of the signature algorithm, and the two numbers in a signature are r and s.

Verification is straightforward:

• uG + vP where u,v ≠ 0
• uG + vP = (z/s)G + (re/s)G = ((z + re)/s)G = ((z + re)/((z + re)/k))G = kG = (r,y)

Warning

Why We Don’t Reveal k At this point, you might be wondering why we don’t reveal k and instead reveal the x coordinate of R, or r. If we were to reveal k, then: uG + vP = R uG + veG = kG kG – uG = veG (k – u)G = veG (k – u) = ve (k – u)/v = e means that our secret would be revealed, which would defeat the whole purpose of the signature. We can, however, reveal R. It’s worth mentioning again: make sure you’re using truly random numbers for k, as even accidentally revealing k for a known signature is the equivalent of revealing your secret and losing your funds!

Verification in Depth

Signatures sign some fixed-length value (our "contract")—in our case, something that’s 32 bytes. The fact that 32 bytes is 256 bits is not a coincidence, as the thing we’re signing will be a scalar for G.

To guarantee that the thing we’re signing is 32 bytes, we hash the document first. In Bitcoin, the hashing function is hash256, or two rounds of sha256. This guarantees the thing that we’re signing is exactly 32 bytes. We will call the result of the hash the signature hash, or z.

The signature that we are verifying has two components, (r,s). r is the x coordinate of some point R that we’ll come back to. The formula for s is as above:

• s = (z+re)/k

Keep in mind that we know e (P = eG, or what we’re proving we know in the first place), we know k (kG = R, remember?), and we know z.

We will now construct R = uG + vP by defining u and v this way:

• u = z/s
• v = r/s

Thus:

• uG + vP = (z/s)G + (r/s)P = (z/s)G + (re/s)G = ((z + re)/s)G

We know s = (z + re)/k, so:

• uG + vP = ((z + re) / ((z + re)/k))G = kG = R

We’ve successfully chosen u and v in such a way as to generate R as we intended. Furthermore, we used r in the calculation of v, proving we knew what R would be. The only way we can know the details of R beforehand is if we know e.

To wit, here are the steps:

1. We are given (r,s) as the signature, z as the hash of the thing being signed, and P as the public key (or public point) of the signer.

2. We calculate u = z/s, v = r/s.

3. We calculate uG + vP = R.

4. If R's x coordinate equals r, the signature is valid.

Note

Why Two Rounds of sha256? The calculation of z requires two rounds of sha256, or hash256. You may be wondering why there are two rounds when only one is necessary to get a 256-bit number. The reason is for security. There is a well-known hash collision attack on SHA-1 called a birthday attack that makes finding collisions much easier. Google found a SHA-1 collision using some modifications of a birthday attack and a lot of other things in 2017. Using SHA-1 twice, or double SHA-1, is the way to defeat or slow down some forms of this attack. Two rounds of sha256 don’t necessarily prevent all possible attacks, but doing two rounds is a defense against some potential weaknesses.

Verifying a Signature

We can now verify a signature using some of the primitives that we have:

link:code-ch03/examples.py[role=include]

1. Note that we use Fermat’s little theorem for 1/s, since n is prime.

2. u = z/s.

3. v = r/s.

4. uG + vP = (r,y). We need to check that the x coordinate is r.

code-ch03/answers.py

Programming Signature Verification

We already have a class S256Point, which is the public point for the private key. We create a Signature class that houses the r and s values:

link:code-ch03/ecc.py[role=include]

We will be doing more with this class in [chapter_serialization].

We can now write the verify method on S256Point based on this:

class S256Point(Point):
    ...
link:code-ch03/ecc.py[role=include]

1. s_inv (1/s) is calculated using Fermat’s little theorem on the order of the group, n, which is prime.

2. u = z/s. Note that we can mod by n as that’s the order of the group.

3. v = r/s. Note that we can mod by n as that’s the order of the group.

4. uG + vP should be R.

5. We check that the x coordinate is r.

So, given a public key that is a point on the secp256k1 curve and a signature hash, z, we can verify whether a signature is valid or not.

Signing in Depth

Given that we know how verification should work, signing is straightforward. The only missing step is figuring out what k, and thus R = kG, to use. We do this by choosing a random k.

The signing procedure is as follows:

1. We are given z and know e such that eG = P.

2. Choose a random k.

3. Calculate R = kG and r = x coordinate of R.

4. Calculate s = (z + re)/k.

5. Signature is (r,s).

Note that the public key (pubkey) P has to be transmitted to whoever wants to verify it, and z must be known by the verifier. We’ll see later that z is computed and P is sent along with the signature.

Creating a Signature

We can now create a signature.

Warning

Be Careful with Random Number Generation Note that using something like the random library from Python to do cryptography is generally not a good idea. This library is for teaching purposes only, so please don’t use any of the code explained to you here for production purposes.

We do this using some of the primitives that we have:

link:code-ch03/examples.py[role=include]

1. This is an example of a "brain wallet," which is a way to keep the private key in your head without having to memorize something too difficult. Please don’t use this for a real secret.

2. This is the signature hash, or hash of the message that we’re signing.

3. We’re going to use a fixed k here for demonstration purposes.

4. kG = (r,y), so we take the x coordinate only.

5. s = (z + re)/k. We can mod by n because we know this is a cyclical group of order n.

6. The public point needs to be known by the verifier.

code-ch03/answers.py

Programming Message Signing

To program message signing, we now create a PrivateKey class, which will house our secret:

link:code-ch03/ecc.py[role=include]

1. We keep around the public key, self.point, for convenience.

We then create the sign method:

from random import randint
...
class PrivateKey:
...
    def sign(self, z):
        k = randint(0, N)  # (1)
        r = (k*G).x.num  # (2)
        k_inv = pow(k, N-2, N)  # (3)
        s = (z + r*self.secret) * k_inv % N  # (4)
        if s > N/2:  # (5)
            s = N - s
        return Signature(r, s) # (6)

1. randint chooses a random integer from [0,__n__). Please don’t use this function in production, because the random number from this library is not nearly random enough.

2. r is the x coordinate of kG.

3. We use Fermat’s little theorem again, and n, which is prime.

4. s = (z + re)/k.

5. It turns out that using the low-s value will get nodes to relay our transactions. This is for malleability reasons.

6. We return a Signature object from the class defined earlier.

Importance of a Unique k

There’s an important rule in signatures that utilize a random component like we have here: the k needs to be unique per signature. That is, it cannot get reused. In fact, a k that’s reused will result in you revealing your secret! Why?

If our secret is e and we are reusing k to sign z₁ and z₂:

• kG = (r,y)
• s₁ = (z₁ + re) / k, s₂ = (z₂ + re) / k
• s₁/s₂ = (z₁ + re) / (z₂ + re)
• s₁(z₂ + re) = s₂(z₁ + re)
• s₁z₂ + s₁re = s₂z₁ + s₂re
• s₁re – s₂re = s₂z₁ – s₁z₂
• e = (s₂z₁ – s₁z₂) / (rs₁ – rs₂)

If anyone sees both signatures, they can use this formula and find our secret! The PlayStation 3 hack back in 2010 was due to the reuse of the k value in multiple signatures.

To combat this, there is a deterministic k generation standard that uses the secret and z to create a unique, deterministic k every time. The specification is in RFC 6979 and the code changes to look like this:

class PrivateKey:
...
link:code-ch03/ecc.py[role=include]

1. We are using the deterministic k instead of a random one. Everything else about sign remains the same.

2. This algorithm returns a candidate that’s suitable.

A deterministic k will be unique with very high probability. This is because sha256 is collision-resistant, and no collisions have been found to date.

Another benefit from a testing perspective is that the signature for a given z and the same private key will be the same every time. This makes debugging much easier and unit tests a lot easier to write. In addition, transactions that use deterministic k will create the same transaction every time, as the signature will not change. This makes transactions less malleable (more on that in [chapter_segwit]).

Conclusion

We’ve covered elliptic curve cryptography and can now prove that we know a secret by signing something. We can also verify that the person with the secret actually signed a message. Even if you don’t read another page in this book, you’ve learned to implement what was once considered "weapons-grade munitions". This is a major step in your journey and will be essential for the rest of the book!

We now turn to serializing a lot of these structures so that we can store them on disk and send them over the network.