January 19, 2021

Bitcoin Math: Practice

In the previous article, we looked at the theoretical foundations of elliptic cryptography and understood how it works in principle. Now all that remains is to apply this knowledge in practice: let's see how it is used in the Bitcoin protocol.

Private keys and public keys

So we now understand how discrete elliptic curve math works, and we know that Bitcoin uses a variant of elliptic cryptography secp256k1. Now we can figure out whereprivate and public keys are taken and how they are generally related to each other and to bitcoin addresses. In short, in ECDSA, a secret key is just a random number between 1 and an order value. The public key is obtained from the secret one using scalar multiplication of the base point by the value of the secret key. As an equation:

Public key = secret key * base point

This shows that the maximum possible number of secret keys (and therefore bitcoin addresses) is sure, and is equal to the order. So it may not be enough for all of them ?! Not quite so: remember that order is really big number - it is unimaginably greater than the total number of elementary particles in the entire universe.

How does this equation work in reality? The computation of the public key is broken down into a series of point doubling and point addition operations, starting at a base point.

Recall that we work with discrete mathematics of elliptic curves, where the addition of the points p + q to find their sum r is defined componentwise as follows:

c = (qy - py) / (qx - px)
rx = c2 - px - qx
ry = c (px — rx) — py

And the operation of "doubling" the point p looks like this:

c = (3px2 + a) / 2py
rx = c2 - 2px
ry = c (px — rx) — py

The amount of computation for a real example would beunrealistically complex, but we can try with an example with small numbers to see how it works. So, let's take the equation of the curve of Bitcoin, but instead of the unrealistically huge values ​​of order, modulus and base point that are used in Bitcoin, we will use small numbers.

A real-life example from toy cryptography

So, for convenience, let's create our own mini-bitcoin cryptography, for example, this:

Curve equation: y2 = x3 + 7
Module: 67
Base point: (2, 22)
Order: 79

To show that we are not bastard, we will choose a "completely random" secret key (out of 79 possible). Well, let it be 2.

Let's find a public key for it. Since we chose the simplest "secret" key with value = 2, we only need one operation of doubling the base point for this. Very comfortably. The calculation looks like this:

c = (3 * 22 + 0) / (2 * 22) mod 67
c = (3 * 4) / (44) mod 67
c = 12/44 mod 67

Here we have to do a little trick thatnot previously explained. How do we perform a division operation in the context of a finite field, where the result must be an integer? To do this, we must multiply 12 by the reciprocal of 44. Finding the reciprocal in the context of finite fields is not so easy (if you want to study this question in more detail, see here), so for now you have to take my word for it that:

44-1 = 32

The following is pretty simple:

c = 12 * 32 mod 67
c = 384 mod 67
c = 49

rx = (492 - 2 * 2) mod 67
rx = (2401 - 4) mod 67
rx = 2397 mod 67
rx = 52

ry = (49 * (2 - 52) - 22) mod 67
ry = (49 * (-50) - 22) mod 67
ry = (-2450 - 22) mod 67
ry = -2472 mod 67
ry = 7

So, we have determined that for private key 2, the public key will be dot (52, 7). Finally! So many calculations, and all for the sake of such and such a simple "discovery".

And with all that, this operation is a transition fromthe secret to the public key is nothing in complexity compared to trying to work in the opposite direction: derive the secret from the public key. If, for our "toy" example, we can still do it after pushing our efforts, in the case of real cryptography we will have a bummer. While getting the private key from the public in theory and perhaps it is computationally impossible due to the huge parameter numbers used in real elliptic cryptography.

So it's safe to say that going from a private key to a public key is a one-way journey.

Like the private key, the public key is also likeusually represented as a hexadecimal number. Wait, you say - we just learned that this key is a point, not a scalar? How can it be represented as a single number? In uncompressed format, a public key is simply two 256-bit numbers written in a row, which are its x and y coordinates. We can also take advantage of the symmetry property of the elliptic curve to obtain a compressed public key - in this format, it contains only the value of the x coordinate and information about whether the point is on the bottom or on the top half of the curve. From this information, we can recover both coordinates by substituting a curve into the equation.

We sign the data with a secret key

Now that we have our own private / public key pair (albeit in the toy micro-space of elliptic cryptography), let's finally sign some data!

This data can be of any length. Usually the first step is to hash the data to get a unique number containing the same number of bits (256) as the order of the curve. Here, for the sake of simplicity, we'll skip the hashing step and pretend we just need to sign the dataset z. Let G denote the base point, n the order, and d the private key. The signature creation algorithm is as follows:

  1. Choose some integer k in the range from 1 to n-1.
  2. Calculate point (x, y) = k * G using scalar multiplication.
  3. Find r q x mod n. If r q 0, go back to step 1.
  4. Find s q (z q r q d) / k mod n.If the S is 0, go back to step 1.
  5. Couple (r, s) is our signature

Recall, in step 4, if you have to resort to division (which in real life almost always happens), the numerator shouldAnd in the initial step 1 it is important that k is not repeated in different signatures, and that it could not be guessed by a third party.That is, K must be either random or created by a deterministic process that is kept secret fromOtherwise, you could calculate the secret key starting with step 4, as s, z, r, k and n are all known.

Let's pick the number 17 as our data and sign it with our super-secret key 2.So:

z q 17 (data)
n q 79 (order)
G (2, 22) (base point)
d q 2 (secret key)

1. Choose a random number:

k = rand(1, n — 1)
k = rand(1, 79 — 1)
k q 3 (what, it's really a random number!? Okay, okay, let's just say it's also a "toy" rand!)

2. Let's calculate the point.

This is done in the same way as before when calculating the public key - for brevity Omit the detailed arithmetic of addition and doubling.

(x, y) = 3G
(x, y) = G 2G
(x, y) = (2, 22) (52, 7)
(x, y) = (62, 63)
x = 62
y = 63

3. Find r :

r = x mod n
r = 62 mod 79
r = 62

4. Find s :

s = (z r * d) / k mod n
s = (17 62 * 2) / 3 mod 79
s = (17 124) / 3 mod 79
s = 141 / 3 mod 79
s = 47 mod 79
s = 47

Note that the above we were able to divide by 3, as the resultIn real life, you'll have to look for the opposite, etc.it's a heavy computing routine.

5. Received the signature:

Our signature is a couple (r, s) = (62, 47).

As with secret and public keys, this signature is also usually presented as a hexath line.

Checking signature with a public key

Well, the signature is something we got that now?

Now we have the data and our signature of this data.A third party who knows the public key can get our data and signature and make sure we are the senders.Let's see how it works.

By designating our open key, the steps to verify the signature will beFollowing:

  1. Make sure r and s are in the range of 1 to n-1.
  2. Calculate w = s-1 mod n
  3. Calculate u = z * w mod n
  4. Calculate v = r * w mod n
  5. Calculate point (x, y) = uG + vQ
  6. Make sure that if you don't, the signature is invalid.

Why do these steps work?Let's just run the algorithm manually and see what happens.

z q 17 (data)
(r, s) (62, 47) (signature)
n q 79 (order)
G (2, 22) (base point)
(52, 7) (public key)

1.Make sure that r and s are in the range of1 to n-1.

r: 1 <= 62 < 79
s: 1 <= 47 < 79

Yes right.

2. Let's calculate w:

w = s-1 mod n
w = 47-1 mod 79
w = 37

3. Calculate u:

u = zw mod n
u = 17 * 37 mod 79
u = 629 mod 79
u = 76

4. Calculate v:

v = rw mod n
v = 62 * 37 mod 79
v = 2294 mod 79
v = 3

5. Calculate the point (x, y):

(x, y) = uG vQ

This is the most fun part.

uG = 76G
uG = 2(38G)
uG = 2( 2(19G) )
uG = 2( 2(G 18G) )
uG = 2( 2(G 2(9G) ) )
uG = 2( 2(G 2(G 8G) ) )
uG = 2( 2(G 2(G 2(4G) ) ) )
uG = 2( 2(G 2(G 2( 2(2G) ) ) ) )

Check out: with the help of a deft grouping, we reduce 75 consecutive addition operations to just six doubling operations and two additions.And we also work on "toy" examples - imagine the number of operations in "real" cryptography.Or better not even imagine - it is possible that just go crazy.

Continue our exciting performance:

uG = 2( 2(G 2(G 2( 2( 2(2, 22) ) ) ) ) )
uG = 2( 2(G 2(G 2( 2(52, 7) ) ) ) )
uG = 2( 2(G 2(G 2(25, 17) ) ) )
uG = 2( 2(G 2( (2, 22) (21, 42) ) ) )
uG = 2( 2(G 2(13, 44) ) )
uG = 2( 2( (2, 22) (66, 26) ) )
uG = 2( 2(38, 26) )
uG = 2(27, 40)
uG = (62, 4)

And now, all the same for vQ:

vQ = 3Q
vQ = Q + 2Q
vQ = Q + 2 (52, 7)
vQ = (52, 7) + (25, 17)
vQ = (11, 20)

Having counted, we add them together:

(x, y) = uG vQ
(x, y) = (62, 4) + (11, 20)
(x, y) = (62, 63)

Uff, it seems finished. I hope they were not wrong anywhere. It is immediately clear that most of the work is done in step 5. There is just nonsense left.

6. Finally, make sure that r = x mod n

r = x mod n
62 = 62 mod 79
62 = 62

Hooray, our signature is valid!

Conclusion

For those of you who got scared by all these terrible equations in the text and quickly scrolled to the end of the article, what did we just learn?

We have developed some intuition regardingthe relationships that exist between public and private keys. We've seen how even with the simplest, toy-like examples, the mathematics of creating and verifying elliptical signatures quickly becomes complicated. We can now appreciate the enormous computational complexity that occurs when the parameters are huge 256-bit numbers. We have seen how clever use of simple mathematical procedures creates the “one-way” functions needed to maintain information asymmetry. It is this asymmetry that allows us to prove ownership of bitcoins without revealing our private keys.

If you have gone through this hands-on exercise, you have gained some confidence in the reliability of the system - provided that knowledge of our private keys is reliably protected from outsiders.

At the very least, you can now understand why it is so often repeated that bitcoin ownership is "guaranteed by mathematics."

If you have studied these examples well, then theyshould give you enough confidence to take the next step and try to do similar calculations yourself (as for modular arithmetic, this calculator makes life a lot easier). We've found that going through the manual signing and verification steps provides a deeper understanding of the kind of cryptography that makes Bitcoin a unique form of ownership unlike anything that came before it.

: Coindesk

Author: Eric Rykwalder