Saltar al contenido

Elliptic Curve in Bitcoin

Tiempo de lectura aprox: 7 minutos, 45 segundos

Recently, I was helping a friend to set up his new watch-only wallet. As expected, a common concern came up when he was using it:

«If you always tell me to keep my private keys as secret as possible, why can I enter my public key1 into the wallet without putting my funds at risk?»

That’s when I took the opportunity to explain to him the concept of one-way cryptographic functions. More precisely, the function that allows the derivation of the public key: The Elliptic Curve.

After talking about this topic for a while, a realization struck me: I remembered that when I had to understand how the Elliptic Curve works it took me many hours, because most of the sources that can be consulted have the documentation poorly formulated and, in some cases, there are parts missing.

In addition, my friend was able to understand how the Elliptic Curve works after my explanation in less than 30 minutes.

That’s why, based on the approach I used to explain the amazing concept of Elliptic Curve to him, I wrote the article you are reading. I hope that, after reading this, you will never again have doubts about how it works, and feel free to always come back to solve them. Let’s begin.

Delving into Elliptic Curve Cryptography

Elliptic Curve Cryptography (ECC) is one of the most interesting – and important – concepts in the intersection between Mathematics and Technology. Its capabilities are far superior to other methods with the same purpose, and it has been extensively tested to prove its security.

Broadly speaking, ECC is a type of one-way cryptographic function, that is, it allows turning an input into an output in such a way that it is impossible to obtain the original input data from the output.

With this concept in mind and applying it to Bitcoin, ECC is essential in a crucial step: deriving the Public Key from the Private Key. Without a one-way function like ECC, our private key will be exposed every time we share our Public Key and therefore, an attacker could obtain our funds. That’s the reason why we need a one-way function like ECC.

Within ECC there are many variants of elliptic curves, each one with different parameters. For the case of Bitcoin, Satoshi Nakamoto chose the elliptic curve called «secp256k1», a variant used both to derive public keys and to sign Bitcoin transactions.

Why did Satoshi choose ECC?

There are multiple cryptographic functions that achieve the one-way result. So, what is the reason behind Satoshi choosing precisely the Elliptic Curve, and not other functions like RSA2?

If we seek a high level of security when employing a one-way function, an optimal degree would be 128 bits of equivalent security3—equivalent to the security provided by a 128-bit symmetric key encryption.

For this security level, with ECC we need 256-bit keys (that can be generated with the curve “secp256k1”), while with RSA we would need to generate 3072-bit keys. It is evident that ECC is much more efficient.

This happens because when RSA was designed back in 1977, the mathematical problem behind it (factorization of very high prime numbers) created a big challenge for the computers of that time. However, with the exponential increase in computing power, nowadays that mathematical problem is currently much easier to solve. The advantage of ECC over RSA is so massive, that a 256-bit RSA key, the same size as those of ECC, can now be cracked in just 50 seconds with a common laptop.

The very marked difference in efficiency between these two systems is inherent to the mathematical problem involved. In RSA the complexity level is much lower than in ECC, which leads to a requirement of longer keys to achieve the same degree of security against brute force attacks. It is observable that the difference increases exponentially as the needed key length grows.

In contrast, ECC is based on mathematical operations that are computationally infeasible to solve even with current supercomputers. This allows ECC to achieve high levels of security with very short keys compared to RSA. Moreover, if in the near future Quantum computers start being used, ECC will only need a few adjustments to keep up with the increased computing power.

Therefore, in order to make more efficient the space that a key occupies within bitcoin, thus having a greater equilibrium between security and size, it makes sense that Satoshi chose ECC over RSA.

General Elliptic Curve equation and secp256k1 parameters

The Elliptic Curve is a mathematical function defined by the following formula:

Where a and b are parameters that specify each curve. Every combination of different values for a and b, generates a new elliptic curve with unique properties.

In the Elliptic Curve used in Bitcoin, “secp256k1”, a takes the value of 0 and b takes the value of 7. Consequently, the equation is as follows:

Graphically, the secp256k1 elliptic curve displays symmetry to the x axis. This means that, for a given value of x, the y-coordinate can take two values: positive or negative.

This duality of values originates from solving the equation defining secp256k1 (y^2 = x^3 + 7), which involves calculating square roots. Specifically, solving for y results in y = ±square root(x^3 + 7):

Taking x = 2 as an example, two symmetric points are obtained: (2, +3.87) and (2, -3.87). Each x value thus generates two options for y, one positive and one negative.

The duality of values for the same x is a critical characteristic when calculating the Public Key.

Deriving the Public Key

The Public Key is obtained from the Private Key and a constant G known as the Generator Point, which is static and defined in the secp256k1 curve parameters, through the following operation:

K (Public Key) = k (Private Key) x G (Generator Point)

This operation is performed on the coordinates of the Elliptic Curve, instead of real numbers. So, in this particular case, multiplying is best interpreted as adding the Generator Point as many times as indicated by the private key value.

If the Private Key were «5», to obtain the Public Key you would have to add G+G+G+G+G = 5G.

As we have said before, the Generator Point (G) is a constant already determined in the initial parameters of the secp256k1 elliptic curve:

04 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8

The upper number dictates the x and y coordinates where the Generator Point (G) is located within the secp256k1 elliptic curve.

Let’s take a more visual look of this operation:

Imagine we have to add the points «A» and «B» on the Elliptic Curve. To do this, we will draw a line that passes through both, and the point where it crosses the curve again will be the sum of both points in negative «-C». Now we reflect that same point across the x-axis, obtaining point «C», which is finally the sum of A and B.

Now consider adding a point to itself, that is, if we have point «P» we want to obtain «2P». For this we will draw a tangent to the point we want to double. Where the tangent crosses, it will be -2P. We reflect -2P across the x axis, and we get 2P.

Now, we could use both methods to get 3P from P, that is, 2P + P.

Clearly, we can take any point and start adding and duplicating it until we get the desired multiple.

Let’s apply these procedures to the Generator Point (G). Imagine it is positioned at the coordinates (1, 2.82) and our goal is to get 5G, assuming 5 is the Private Key value. One way to do it will be to duplicating G, duplicating it again, and finally adding the original G. The coordinates of the resulting 5G point will be those of the Public Key:

5G = (2(2G)) + G

Having said that, if we start from a point K, which represents the coordinates of a public key, also knowing the position of the Generator Point (G), what would be the Private Key value used to obtain K?

It’s hard to determine, right?

This is the key point of the elliptic curve, what gives reason for its existence. The only method to find the multiplier (the Private Key) starting from the Generator Point and the Public Key would be through brute force, that is, trying every number from all possible ones until finding the one that multiplied by the Generator Point returns us the Public Key (and all this being operations on the Elliptic Curve, which require more processing).

In the context of Bitcoin, the Private Key is not a single digit number, but a number represented with 256 bits, that is, it can be between 0 and 115792089237316195423570985008687907853269984665640564039457584007913129639936.

If we had access to one million supercomputers like the MareNostrum4 (Spain’s most powerful computer), we would need no less than 24478287087205351645436112169940788908514621232681 years to have probabilities of guessing a specific key that would meet the requirements of the Elliptic Curve, or the same as 1773788919362706640973631316662376007863 ages of the universe (13.8 billion years).

Unachievable, right? And we are not even taking into account the cost of each supercomputer and the electricity needed to power all up.

This is the magic of Cryptography using Elliptic Curves, it is very easy to go in one direction (derive the Public Key) and technically impossible to go the other way, ensuring the robustness of the system.

Format Efficiency

Once we have obtained the Public Key from the Private Key, we have a number like this:

04 becf1cf6ef54423889aca53644398f14fd6e9531bd01980a38e6c7b2ca3fb426 6efd97cb9392ed186761526d2063032759b122e179be6fb8bf3575ece29d3621

With «04» being a prefix denoting the type of Public Key format, in blue the x-coordinate and in red the y-coordinate. It’s fair to say that it is a very long number, which when transmitted over the network, takes up a lot of space.

What if we could reduce the space it occupies by half? Remember, the Elliptic Curve is defined by the function:

Therefore, we can obtain the value of y by just knowing x. That is, we can compress the length of the Public Key, eliminating the y part, leaving only the x part. When a computer needs the real value of the Public Key, it solves the previous equation, thus obtaining both coordinates.

Very easy, right? Well there’s still one detail:

When the Public Key is stored with only the x-coordinate, it is called «Compressed». To identify it, the prefix «02» is placed if the y-coordinate is positive, or «03» if it is negative.

The use of one prefix for each positive or negative y is necessary to properly resolve the secp256k1 elliptic curve equation. This is due to the fact that it involves solving a square root, therefore, for each valid x there will be two possible points on the curve, (x, +y) or (x, -y), symmetric with respect to the x axis. Consequently, indicating the sign of y, allows the computer to identify the real point on the curve that represents the corresponding public key to a given private key.

For example, this is the Public Key from a few lines above, already compressed, with the 03 prefix indicating its y-coordinate is negative. Check that the x-coordinate, the one that remains, has the same value as before.

03 becf1cf6ef54423889aca53644398f14fd6e9531bd01980a38e6c7b2ca3fb426

In this way, the size representation of the public key is reduced by half compared to storing both coordinates, without losing necessary information to verify transactions. This optimizes storage and transmission when making a transaction, resulting in lower fee costs.


Wrap-up

When building the ownership system that rules Bitcoin, Satoshi wisely chose the secp256k1 Elliptic Curve: its unique characteristics ensure our Private Key and therefore our funds.

Thanks to ECC we can share our Public Key with a watch-only wallet without fearing an attacker could obtain the Private Key, because it is simply impossible.

However, if we share our Public Key, they can see the transactions we make, affecting our privacy, although I’ll leave that topic for another day.

Thanks for reading this so far. Below I leave an additional note for the geekiest (like me) and a list of the main sources used to prepare this article.


Cloud of points

At a more technical level, the secp256k1 elliptic curve is not defined on the Cartesian plane as I had previously shown in order to simplify, but rather on a Field Fp with p equal to (2^256 – 2^32 – 2^9 – 2^8 – 2^7 – 2^6 – 2^4 – 1), a very large prime number.

The Elliptic Curve on Field Fp looks like this:

This Field Fp is built by points obtained as the remainder of dividing a number (the x and y coordinate of each point on the curve in the Cartesian plane) by p. By performing this operation, when the new points are plotted, they go from being a continuous line to a cloud of points. Despite this conversion, the Elliptic Curve maintains the properties we were explaining earlier: There is symmetry with respect to the x axis, as well as a line can be drawn between two points to add them.

For illustrative purposes, in the graph I have used the p value of 43.5 so that the cloud of points can be clearly seen. You can try modifying the P value, as well as the range of x values and the type of Elliptic Curve on your own, by changing the «parameters» variable values in the Python code that I have prepared «elliptic-curve-field-p-chart.py»:

https://github.com/SalvaZaraes/bitcoin


Notes

  1. Extended Public Key
  2. RSA (Rivest–Shamir–Adleman) is an asymmetric encryption algorithm developed in 1977 and used for data security. It relies on the difficulty of factoring large composite numbers into their two prime factors. It is being replaced by ECC (Elliptic Curve Cryptography).
  3. Bits of Equivalent Security: This concept refers to the number of bits of cryptographic strength achieved with asymmetric encryption algorithms like Elliptic Curve Cryptography (ECC), compared to symmetric encryption. For instance, when we say that ECC with the secp256k1 curve provides 128 bits of equivalent security, it means it offers a level of protection similar to what would be obtained with a symmetric encryption algorithm with a key length of 128 bits, such as AES-128.

Sources

  • Antonopoulos, A. M. (2014). Mastering Bitcoin: Unlocking Digital Crypto-currencies. Oreilly & Associates Incorporated.
  • Code used to calculate the value of the Uncompressed Public Key: https://bitcointalk.org/index.php?topic=644919.msg7205689#msg7205689
  • SECP256K1 – Bitcoin Wiki. (n.d.-b). https://en.bitcoin.it/wiki/Secp256k1
  • Standards for Efficient Cryptography 2 (SEC 2) (2010). https://www.secg.org/sec2-v2.pdf
  • ‌RSA key decryption in 50 seconds:   https://formtek.com/blog/encryption-256-bit-rsa-cracked-by-a-laptop-in-50-sec/
  • All images are self-created using the matplotlib library in Python and subsequently edited.