Bitcoin Math: Practice

In the previous article, we looked at the theoretical foundations of elliptic cryptography and understood how itworks 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 the discrete mathematics of elliptic curves works, and we know that Bitcoin uses a variant of elliptic cryptographysecp256k1.Now we can figure out where it came fromwhat are the private and public keys and how are they generally related to each other and to Bitcoin addresses. In short, the ECDSA secret key — it is simply a random number between 1 and the order value. The public key is obtained from the secret key using the operation of scalar multiplication of the base point by the value of the secret key. In equation form:

Public key = secret key * base point

This shows that the maximum possible number of secret keys (and therefore Bitcoin addresses) —sure, and equal to the order. So, it means there may not be enough for all of them?! Not quite so: remember that the order — Thisreally bignumber — it is unimaginably greater than the total number of elementary particles in the entire Universe.

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

Recall that we are working with the discrete mathematics of elliptic curves, where the addition of points p + q to find their sum r is defined component-wise as follows:

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

A «doubling» operation 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 example from a «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 blind, we will choose a «absolutely random» secret key (out of 79 possible). Well, let it be 2.

Let's find the 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 bedot(52, 7). Finally! So many calculations, and all for the sake of such and such a simple «discovery».

And with all that, this operation — transitionfrom private to public key — the complexity is simply nothing compared to trying to work in the opposite direction: deducing the private key from the public key. If for our «toy» For example, we can still do this with some effort; in the case of real cryptography, a bummer awaits us. Although you can get the private key from the public keyin theoryand perhaps this 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 likeTypically represented as a hexadecimal number. Wait a minute, you say — we just found out that this key — point, not a scalar? How can it be represented as a single number? In uncompressed format, the public key — these are simply two 256-bit numbers written in a row, which are its x and y coordinates. We can also take advantage of the elliptic curve symmetry property to obtain a compressed public key — in this format it contains only the x coordinate value and information about which half of the curve the point — on the bottom or on the top. From this information we can reconstruct both coordinates by substituting curves 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.Typically the first step is to hash the data to produce a unique number containing the same number of bits (256) as the order of the curve. Here, for simplicity, we will skip the hashing step and pretend that we just need to sign the z data set. Let us denote the base point by G, and by n — order, and d — private key. The algorithm for creating a signature is as follows:

1. Choose some integer k in the range from 1 to n-1.
2. Calculate the point (x, y) = k * G using scalar multiplication.
3. Find r = x mod n. If r = 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 that in step 4, if you have to resort todivision (which almost always happens in real life), the numerator should be multiplied by the reciprocal of the denominator. And at the initial step 1, it is important that k is not repeated in different signatures, and that it cannot be guessed by a third party. That is, k must be either random or created by a deterministic process that is kept secret from third parties. Otherwise, it would be possible to calculate the secret key starting from step 4, since s, z, r, k and n are known to everyone.

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

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

1. Choose a random number:

k = rand(1, n — 1)
k = rand(1, 79 — 1)
k = 3 (is this really a random number!? Well, okay, okay, let's say that this is also a «toy» random!)

2. Let's calculate the point.

This is done in the same way as previously when calculating the public key — For brevity, we will 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. Findr:

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

4. Finds:

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 above we were able to divide by 3 because the result was an integer. In real life you will have to look for the inverse value, etc. – heavy computing routine.

5. Received the signature:

Our signature is the pair (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 between 1 and 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 = 79 (order)
G = (2, 22) (base point)
Q = (52, 7) (public key)

1. Let's make sure that r and s are in the range from 1 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 fun part. Let's look at the operations of doubling and addition in uG and vQ separately.

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 it out:with the help of clever grouping, we reduce 75 consecutive addition operations to just six doubling operations and two — addition. And we also work on «toy» examples — imagine the number of operations in the «present» cryptography Or better yet, don’t even imagine — It’s possible that you’ll 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, it's all the same forvQ:

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 regardingrelationships that exist between public and private keys. We saw how even on the simplest, «toy» examples, the mathematics of creating and verifying elliptic signatures quickly becomes complex. Now we can appreciate the enormous computational complexity that arises when the parameters are huge 256-bit numbers. We saw how clever applications of simple mathematical procedures create «one-sided» functions necessary to maintain information asymmetry. It is this asymmetry that allows us to prove ownership of bitcoins without revealing our private keys.

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

At the very least, we can now understand why it is so often repeated that ownership of bitcoins is “guaranteed by mathematics.”

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

: Coindesk

Author:Eric Rykwalder