As previously seen, the digital signature algorithms in Bitcoin are based on a pair of private and public keys that are mathematically linked. Let's explore together what this mathematical link is and how they are generated.

The private key is simply a random or pseudo-random number. In the case of Bitcoin, this number is 256 bits in size. The number of possibilities for a Bitcoin private key is therefore theoretically .

Note: A "pseudo-random number" is a number that has properties close to those of a truly random number but is generated by a deterministic algorithm.

However, in practice, there are only distinct points on our elliptic curve secp256k1, where is the order of the generator point of the curve. We will see later what this number corresponds to, but simply remember that a valid private key is an integer between and , knowing that is a number close to but slightly less than . Therefore, there are some 256-bit numbers that are not valid for becoming a private key in Bitcoin, specifically, all the numbers between and . If the generation of the random number (the private key) produces a value such that , it is considered invalid, and a new random value must be generated.

The number of possibilities for a Bitcoin private key is therefore about , which is a number close to . This number is so large that if you choose a private key at random, it is statistically almost impossible to land on another user's private key. To give you an idea of scale, the number of possible private keys in Bitcoin is of an order of magnitude close to that of the estimated atoms in the observable universe.

As we will see in the coming chapters, today, the majority of private keys used in Bitcoin are not generated randomly but are the result of deterministic derivation from a mnemonic phrase, itself pseudo-random (this is the famous phrase of 12 or 24 words). This information does not change anything for the use of signature algorithms like ECDSA, but it helps to refocus our popularization in Bitcoin.

For the rest of the explanation, the private key will be denoted by the lowercase letter .

The public key is a point on the elliptic curve, denoted by the capital letter , and is calculated from the private key . This point is represented by a pair of coordinates on the elliptic curve, each coordinate being an integer modulo , the prime number defining the finite field . In practice, an uncompressed public key is represented by 520 bits (or 65 bytes), corresponding to two 256-bit numbers ( and ) placed end-to-end, preceded by the 8-bit prefix .

However, it is also possible to represent the public key in a compressed form using only 33 bytes (264 bits) by keeping only the abscissa of our point on the curve and a byte indicating the parity of . This is what is known as a compressed public key. I will talk more about this in the last chapters of this training. But what you need to remember is that a public key is a point described by and .

To calculate the point that corresponds to our public key, we use the operation of scalar multiplication on elliptic curves, defined as a repeated addition ( times) of the generator point :

where:

The fact that this point is common to all public keys in Bitcoin allows us to be sure that the same private key will always give us the same public key :

The main characteristic of this operation is that it is a one-way function. It is easy to calculate the public key knowing the private key and the generator point , but it is practically impossible to calculate the private key knowing only the public key and the generator point . Finding from and amounts to solving the discrete logarithm problem on elliptic curves, a mathematically difficult problem for which no efficient algorithm is known. Even the most powerful current calculators are unable to solve this problem in a reasonable time.

The concept of addition on elliptic curves is defined geometrically. If we have two points and on the curve, the operation is calculated by drawing a line passing through and . This line will necessarily intersect the curve at a third point . We then take the mirror image of this point with respect to the x-axis to obtain the point , which is the result of the addition:

Graphically, this can be represented as follows:

For the doubling of a point, that is the operation , we draw the tangent to the curve at point . This tangent intersects the curve at another point . We then take the mirror image of this point with respect to the x-axis to obtain the point , which is the result of the doubling:

Graphically, this is shown as:

By using these operations of addition and doubling, we can perform the scalar multiplication of a point by an integer , denoted , by performing repeated doublings and additions.

For example, suppose we have chosen a private key . To compute the associated public key, we perform:

Graphically, this corresponds to performing a series of additions and doublings:

If we wish, for example, to calculate the point , we must first calculate the point by doubling the point , then add and . To add and , simply draw the line connecting these two points, retrieve the unique point at the intersection between this line and the elliptic curve, and then determine as the opposite of .

We will have:

Graphically, this would be represented as follows:

Thanks to these operations, we can understand why it is easy to derive a public key from a private key, but the reverse is practically impossible.

Let's go back to our simplified example. With a private key . To calculate the associated public key, we perform:

We have thus been able to easily calculate the public key by knowing and .

Now, if someone only knows the public key , they are faced with the discrete logarithm problem: finding such that . This problem is considered difficult because there is no efficient algorithm to solve it on elliptic curves. This ensures the security of the ECDSA and Schnorr algorithms.

Of course, in this simplified example with , it would be possible to find through trial and error, as the number of possibilities is low. However, in practice, is a 256-bit integer, making the number of possibilities astronomically large (about ). Therefore, it is infeasible to find by brute force.