Elliptic Curve Cryptography: A Deep-Dive into its Building Blocks, Implementation, and Drawbacks

The building blocks of ECC

One of the most powerful types of cryptography being used nowadays is Elliptic Curve Cryptography (ECC). This method is used to secure, among others, the Cloudflare servers that host most of the online content nowadays.

This algorithm is in charge of securing everything from customers’ HTTPS connections to data transmissions from one data center to another. In order to trust this technology, it might be worth digging into why it is so important in the modern world and seeing how it works behind the scenes.

Going back to the history of cryptography, we can differentiate between the classical and the modern era. 1977 can be set as the turning point. That’s when both the RSA algorithm and the Diffie-Hellman key exchange algorithms were introduced.

These algorithms were revolutionary because they represented and put into practice the first viable cryptographic schemes where security was based on the theory of numbers. Its implementation turned out to be useful for even securing communications across the network and allowing 2 parties to exchange data without exchanging a shared secret.

Consequently, cryptography evolved from being about securely transporting secret codebooks around the world to being able to have secure communications between any two parties without worrying about third parties listening and waiting for the exchange of keys.

This turning point was the building block of a new concept by which that key that you use to encrypt your data can be made public while the key that you use to decrypt remains private. In fact, this is the origin of public key cryptography.

This is based on the premise that these algorithms are easy to process in one direction but extremely difficult to undo and move back in the other direction. In other words, we can think of multiplication as the easy direction, whereas factoring the product of the multiplication pairs into its two component primes would constitute the hard direction to decode.

The most studied and well-known public key cryptographic system is the RSA algorithm, whose security relies on the fact that factoring is slow whereas multiplication is a fact. In general, a public key encryption system has two components, a public key, and a private key. Encryption works by taking a message and applying a mathematical operation to it to get a random-looking number. Decryption takes the random-looking number and applies a different operation to get back to the original number.

Encryption with the public key can only be undone by decrypting with the private key. Since computers do not handle well arbitrarily large numbers, we can make sure that the numbers that we are dealing with do not get too large by choosing a maximum number and only dealing with lower numbers from that set threshold. By doing that, we would be treating numbers like the numbers on an analog clock. Any calculation that results in a number larger than the maximum would get wrapped around to a number in the valid range. For example, in RSA algorithms that maximum value is obtained by multiplying two random prime numbers.

The public and private keys are two specially chosen numbers that are greater than zero and less than the maximum value, call the pub and priv. To encrypt a number you multiply it by itself pub times, making sure to wrap around when you hit the maximum. To decrypt a message, you multiply it by itself priv times and you get back to the original number.

It sounds surprising, but it actually works. This property was a big breakthrough when it was discovered.

In order to represent a message mathematically, we have to turn the letters into numbers. A common representation of the Latin alphabet is UTF-8. Each character corresponds to a number.

If we take the example of the word CLOUD, this would lead us to numbers 67, 76, 79, 85, and 68. Each of these digits is smaller than our maximum of 91, so we can encrypt them individually.

We have to multiply it by itself 5 times to get the encrypted value.

67×67 = 4489 = 30 ;

Since 4489 is larger than the maximum, we wrap it around by dividing by 91 and taking the remainder.

4489 = 91×41 + 30

30×67 = 2010 = 8

8×67 = 536 = 81

81×67 = 5427 = 58

This means that the encrypted version of 67 is 58.

Repeating the process for each of the letters we get that the encrypted message CLOUD becomes:

58, 20, 53, 50, 87

To decrypt this scrambled message, we take each number and multiply it by itself 29 times:

58×58 = 3364 = 88 (remember, we wrap around when the number is greater than max)>

88×58 = 5104 = 8

…

9×58 = 522 = 67

Voila, we’re back to 67.

As we scale, these factoring algorithms get more efficient as the size of the numbers being factored gets larger. The gap between the difficulty of factoring large numbers and multiplying large numbers is shrinking as the number (i.e. the key’s bit length) gets larger. As the resources available to decrypt numbers increase, the size of the keys need to grow even faster, which are not the most favorable conditions for mobile and other low powered devices with more limited computational power

ECC implementation

Unlike factoring, most people are not familiar with elliptic curves. In short, an elliptic curve is the set of points that satisfy a specific mathematical equation:

y2 = x3 + ax + b

We can observe horizontal symmetry:

Taking a closer look we realize that if we take any two points on the curve and draw a line through them, it will intersect the curve at exactly one more place

It turns out that if you have two points, an initial point “dotted” with itself n times to arrive at a final point, finding out n when you only know the final point and the first point is hard.

Going back to the basics, this problem must be easy to do and hard to undo.

For example, imagine one person hitting a ball from point A towards point B, and when it hits the curve, the ball bounces either straight up or straight down to the other side of the curve.

If someone walks into the room later and sees where the ball has ended up, even if they know all the rules of the game and where the ball started, they cannot determine the number of times the ball was struck to get there without running through the whole game again until the ball gets to the same point. Easy to do, hard to undo: this is the basis for a very good Trapdoor Function.

Getting closer towards more realistic goals

The simplified game dynamics above do not explain what true cryptographic curves look like. In reality, these curves are more similar to the one below. Here’s an example of a curve (y2 = x3 — x + 1) plotted for all numbers:

Here’s the plot of the same curve with only the whole number points represented with a maximum of 97:

The same simplified explanation can be applied. You can visualize the line between two points as a line that wraps around at the borders until a certain point is hit.

With this new curve representation, you can take messages and represent them as points on the curve. You could imagine taking a message and setting it as the x coordinate, and solving for y to get a point on the curve. It is slightly more complicated than this in practice, but this is a general idea.

An elliptic curve cryptosystem can be defined by picking a prime number as a maximum, a curve equation, and a public point on the curve. A private key is a number priv, and a public key is a public point dotted with itself priv times. Computing the private key from the public key in this kind of cryptosystem is called the elliptic curve discrete logarithm function. This turns out to be the Trapdoor Function we were looking for.

Applications in the real world

• Proof of ownership
• Anonymity
• Signatures in Apple’s iMessage services
• DNSCurve encryption
• SSL/TLS authentication
• Perfect forward secrecy

Major drawback

• There is a generalized skepticism that distrust the NIST itself and the standards that it published and that were supported by the NSA. Almost all Elliptic Curves fall under this threat. Despite not existing any known attacks on special curves, these are chosen for their arithmetic efficiency and some feel that the widespread adoption of more complex curves is several years away. Until these non-traditional curves are implemented by browsers, they won’t be able to be used for securing cryptographic transport on the web.
• Another uncertainty about elliptic curve cryptography is related to patents. There are over 130 patents that cover specific uses of elliptic curves owned by BlackBerry (through their 2009 acquisition of Certicom). Many of these patents were licensed for use by private organizations and even the NSA. This has given some developers pause over whether their implementations of ECC infringe upon this patent portfolio.
• The ECDSA digital signature has a drawback compared to RSA in that it requires a good source of entropy. Without proper randomness, the private key could be revealed.

To conclude, the advantage of ECC over traditional RSA far outweigh the drawbacks. Many experts are concerned that the mathematical algorithms behind RSA could be broken, leaving ECC as the only reasonable alternative. ECC is supported by most major browsers and certification authorities.