Curve wars: how prime numbers safeguard our crypto

In my last post, I gave a non-technical introduction to elliptical curves which form the backbone of security for all the cryptocurrencies we love. This is the second post in the series which I will henceforth call ‘Cryptography for Everyone: A Citizen Science Journey’. It is meant for all those non-technical noobs like me out there. We often find ourselves overwhelmed by the constant bombardment of heavy jargon by those geeky cryptographers. Guess what…we’ve had enough! Let’s dive in…

To briefly TLDR my last post, elliptical curves are formed by simple equations in 2D (i.e., x and y). Using high school algebra (or geometry as I illustrated), here is what we can do:

• add two points on the curve to get a new point.
• double points on the curve or multiply them with an integer to get a new point.

More importantly, here is what we cannot: reverse the multiplication of a point with an integer. In the context of cryptography, if k is your secret key and P is a fixed point on the curve (more about P later), you can compute the public key as K = kP. But even if you know K and P, you cannot get back k since division (K/G) is not defined for elliptical curves. Furthermore, look how successive points P, 2P, 3P etc. jump around seemingly randomly on the curve (even though they are generated by a well-defined point addition rule, as I explained in my previous post):

Figure1: Point addition in elliptical curves: this is how public keys are generated

This irreversibility of the public key generation process is the crux of the security delivered by all elliptic curves. In cryptography, this is formally known as the elliptical curve problem (ECP). So far, nobody has solved it (and we hope it remains that way). But wait, this is always true right…right? Ideally, yes. [But malicious designers (read NSA/NIST) can and have been known to build in weaknesses to elliptical curve standards](https://miracl.com/blog/backdoors-in-nist-elliptic-curves/). In other words, a cunning design of the curve can put in ‘backdoors’ that enable the designer to identify the secret key even without having to solve the ECP. Think of it this way: I might not have the key to enter your house, but if I were its builder, I could have just made one of its walls weak…

So, what is a safe elliptical curve? We are in luck. In 2014, Daniel Bernstein and Tanja Lange [(the same guys who envisioned post-quantum cryptography)](https://www.nature.com/articles/nature23461) came up with a [comprehensive list of criteria for safe curves](https://safecurves.cr.yp.to/index.html). Based on these, we can find an elliptical curve that is not safe enough for use in our next rug pull shitcoin (…just kidding). Before you rush to look up the list, we need to get through a ton of cryptographic jargon so that we can understand what criteria really mean. In the end, we will see to what extent the two most used elliptical curves in our favorite coin list satisfy these criteria.

Let’s begin:

• Finite fields: The problem with numbers is that they extend to infinity. Consider the secret key k in the previous example. Obviously, it’s better when it’s bigger. But how big can you make it without breaking the math? Enter, finite fields. Finite because it’s not infinite, i.e., the numbers you can choose are limited. Let’s say that we can only choose our numbers from those listed on a clock i.e., 1,2,3,4…12. That’s it. So, your secret key k can only be any one of these two values. But hey, who is to prevent us noobs from choosing any other value for our key. Say you chose 69 because you like it. Now cryptographers are clever. So, when you choose 69, here is what they are going to do: take the remainder of 69/12, i.e., 9. Lo and behold folks, we have just defined another fundamental operation in cryptography: the modulo operation. Another freaking jargon for what we used call a ‘remainder’ in primary school. No matter what number you choose, taking its modulo (aka remainder of dividing) by 12, always gives you a number between 0 and 11. That’s it! That’s the trick of converting an insanely huge number to a ‘finite’ field of the order of 11 (i.e., 12-1). Now the question is: how do you choose the field order? In other words what should be a ‘safe’ number to divide by. Heard of prime numbers? Yeah, those are the love of life for cryptographers. Pages and pages of research have been published on how prime numbers ["have the virtue of minimizing the number of security concerns for elliptic-curve cryptography"](https://cr.yp.to/ecdh/curve25519-20060209.pdf). Without blowing our brains out by diving into their rabbit holes, let’s just take their word for it. Another jargon eliminated: prime fields.
• Base point/generator point: Remember the point P? Now how do you get that? Well, you can choose a random point. But if you choose it to follow certain criteria, you can ensure that it’s a safe choice: To begin with, the point should be on the curve. There you go…sounds as obvious as it is. Next, look into the animation from above again, if you keep going P, 2P, 3P, 4P…there will be a time when the point blows away to infinity:

Figure 2: As I explained in my last post, to add two points (in this case P + 12P), you normally draw a straight line between them and find the point Q (=P + 12P) where this line meets the curve a 3rd time. But in this case, as you can see, the line never meets the curve again…or it meets it at infinity.

This number m (in our example m = 13) is defined as the order of the base point. So, what should be a safe m? You guessed it…it must be prime. You might ask why should it be prime? Let’s consider the bitcoin curve again (y^2 = x^3 + 7). Say we have a generator point P of the order of m = 23 (which is prime). Here is how the points P, 2P, 3P, 4P…22P will likely be distributed:

Figure 3: The distribution of succesive points P, 2P, 3P...from the generator point P of the order of a prime number m is usually uniformly random on the elliptical curve

But if the order of P is 22 (which is not a prime), then the points might be distributed as:

Figure 4: The distribution of succesive points P, 2P, 3P...from the generator point P of the order of a non-prime number m usually shows some form of clustering/structure on the elliptical curve

Do you notice how they tend to cluster? Now the attacker (who is ironically the curve designer in this case) knows where to look for your secret key (which is merely one of the points through which P cycles through). NIST…you sneaky b**tard!

To summarize, now we know that safe elliptical curves have a prime field (i.e., there are a unique collection of q-1 points where q is a prime). Moreover, the generator point P (used for producing the public key from the private key) should also be of the order of a prime number m. Now the ratio of the order of the curve to the order of the base point (p/l) is known as the cofactor of the curve. Ideally the cofactor should be 1 (i.e., q = m). This means that starting from the generator, it should be possible to cycle through all points on the curve before returning back to it.

Now that we know the 3 important parameters (field size, order of the generator and the cofactor) of elliptical curves, lets look at how the two most popular curves in cryptocurrency are named:

1. Secp256k1:

• sec: Standards for Efficient Cryptography, not the SEC we all hate...
• p: prime
• 256: the prime number is of 256, it is actually 2^256 – 2^32 – 977 (yeah that’s how insanely large they are),
• k: Koblitz (the guy who designed it),
• 1: version number.

1. Ed25519:

• Ed: Twisted Edwards curve (the scientist),
• 25519: prime field is 2^255 – 19 (yeah again a ridiculous number)

Now lets have a look at which of the top 30 cryptos (by market cap as of now) uses which curve:

Figure 5: Crypto and their curves.

As you can see around 1/3rd of the coins use Ed25519 while the rest use secp256k1, although the data is biased due to the presence of a number of tokens on the Ethereum chain which itself uses secp256k1. Finally, lets have a look at how each of our curves fair with respect to the ‘safety checks’ we have defined so far:

​

Figure 6: Curve wars. Stats so far.

So far so good…but wait we are only getting started. It gets way more interesting than this. But that’s a story for another day…

That’s all folks…stay safe and only trust primes!