Elliptic-Curve Cryptography: What Elliptic Curves Are, Their Advantages and Drawbacks

Elliptic Curves

Elliptic curve cryptography is a cryptographic method based on the mathematical properties of elliptic curves. This approach to cryptography provides a high level of security with shorter keys than those used in classical cryptography.

An elliptic curve is a set of points (x, y) satisfying the equation:

where a and b are the coefficients of the curve. It has several properties that make it useful in cryptography:

1. Point addition: for two points on an elliptic curve one can define an addition operation that finds a third point on the curve lying on the line passing through the two given points. This provides the basis for encryption and digital-signature operations.

2. Discrete logarithm: in elliptic curve cryptography, security rests on the difficulty of computing the discrete logarithm. This means that even if an attacker knows the public key (a point on the elliptic curve), it is hard for them to compute the value of the private key (an integer) used for encryption or signing.

An elliptic curve — a set of points described by the Weierstrass equation:

You can see typical elliptic curve graphs under the spoiler:

The elliptic curves shown in the first 4 figures are called smooth. Whereas the two lower curves belong to the so-called singular elliptic curves.
For smooth elliptic curves the following inequality holds:

Whereas for singular curves this condition, surprise, does not hold.
If you are going to develop a cryptographic product supporting “elliptics” on your own, it is very important to remember the following fact:
Singular curves must not be used in digital-signature schemes. We will cover this topic in detail later; for now we will just say that using singular curves risks significantly reducing the strength of the digital-signature scheme.
Arithmetic operations in elliptic curve cryptography are performed on points of the curve. The main operation is “addition”.
Adding two points is easy to represent graphically:

As the figure shows, to add points P and Q you need to draw a straight line through them, which will necessarily intersect the curve at some third point R. Reflect point R across the horizontal axis and we get the desired point P+Q.

Algebraic Representation of “Addition”

Let us write the addition of two points as a formula:

Let the coordinates of point P be (xp, yp), and the coordinates of point Q be (xq, yq) respectively. Let us compute

and then the coordinates of point P+Q will be equal to:

Elliptic Curves in Cryptography

Only one more detail remains to clarify. All the curves considered above are elliptic curves over the real numbers. And this leads us to the rounding problem. That is, using curves over the real numbers, we cannot obtain a bijection between the plaintext and the encrypted data. To avoid dealing with rounding, cryptography uses only curves over finite fields. This means that an elliptic curve is understood to be a set of points whose coordinates belong to a finite field.

Cryptography considers two kinds of elliptic curves: over the finite field — the ring of residues modulo a prime number. And over the field — the binary finite field.
Elliptic curves over the field have one important advantage: elements of the field can easily be represented as n-bit code words, which makes it possible to increase the speed of hardware implementations of elliptic-curve algorithms.

All mathematical operations on elliptic curves over a finite field are performed according to the laws of the finite field over which the elliptic curve is built. That is, to compute, for example, the sum of two points of curve E over the ring of residues , all operations are performed modulo the number p.

However, there are pitfalls here. If we add two identical elements from a binary finite field, we get 0 as a result, since addition is performed modulo 2. This means that the characteristic of such a field is 2. But an elliptic curve of the form

described over a field of characteristic 2 or 3 becomes singular, and as already noted above, it is a bad idea to use singular curves in cryptography.

Therefore, over a binary finite field, curves of the following form are used:


Another important concept in elliptic curve cryptography is the order of the elliptic curve, which shows the number of points of the curve over the finite field.
Hasse's theorem states that if N — is the number of points of a curve defined over the field Zq with q elements, then the following equality holds:


Since the binary finite field consists of 2n elements, we can say that the order of the curve is equal to , where .

The following definition is associated with the number t:
an elliptic curve over a binary finite field is called supersingular if t divides the characteristic of the field (in the case of a binary field, the characteristic equals 2) without remainder.
Of course, the point of all this is that supersingular curves must not be used in digital-signature schemes. The strict recommendation not to use singular and supersingular curves for digital signatures has one very good reason, but more on that later.

Cryptography on Elliptic Curves

The points of an elliptic curve over a finite field form a group. And as we noted above, an addition operation is defined for this group.
Accordingly, we can represent multiplying the number k by the point G as G+G+..+G with k summands.

Now suppose we have a message M represented as an integer. We can encrypt it using the expression
C=M*G.
The question is how difficult it is to recover M knowing the curve parameters E(a,b), the ciphertext C, and the point G.
This problem is called the discrete logarithm problem on an elliptic curve and has no fast solution. Moreover, it is believed that the discrete logarithm problem on an elliptic curve is harder to solve than the discrete logarithm problem in finite fields.

The fastest methods developed for finite fields turn out to be useless in the case of elliptic curves.
For instance, to solve the discrete logarithm there exist fairly fast algorithms with complexity , where c and d — are certain constants, and p — is the size of the field. Such algorithms are called subexponential and make it comparatively easy to break the discrete logarithm in a finite field if the field size is not chosen very large, on the order of 21024.
At the same time, the fastest methods for solving the discrete logarithm on an elliptic curve have complexity , where q — is the number of points of the elliptic curve.
Thus, to ensure a security level of 280 operations, q=2160 is required. Let me remind you that to obtain a comparable level of complexity when computing the discrete logarithm in a finite field, a field of order q=21024 is required.

It should be noted, however, that since the power of computing technology keeps increasing, the value of q will keep increasing as well. But since the graphs of the functions and differ sharply from one another, in the group of points of the elliptic curve q will grow much more slowly than in an arbitrary finite field.

Types of Attacks

1. The Pohlig-Hellman algorithm. An algorithm for solving the discrete logarithm. Suppose n — is the number of points of the elliptic curve. Let the number n be factored into primes p1, p2,.., pn. The essence of the method comes down to finding discrete logarithms modulo the number pi, and then obtaining the overall solution using the Chinese remainder theorem. The attack allows the discrete logarithm problem in the large field n to be reduced to the same problem but with a much smaller field p. To withstand the attack one simply needs to choose curves whose number of points is divisible by a very large prime number q≈n.
2. Shanks' algorithm, better known as baby-step/giant-step. A typical example of a time-memory trade-off. For a group of size n, a table of size n1/2 is computed, and then the required element is looked up in this table. The complexity of the algorithm is .
3. Vulnerability of singular and supersingular curves. I already mentioned that no subexponential methods exist for solving the discrete logarithm problem. In fact, there is one caveat: such methods do exist, but only for a certain kind of curve: singular and supersingular ones. The special properties of such curves make it possible to reduce the discrete logarithm problem on an elliptic curve to the discrete logarithm problem in a finite field. Accordingly, for this class of curves, standard keys of 160-320 bits would be fatally vulnerable, allowing attackers to recover the secret key in a relatively short time.
4. Vulnerability of anomalous curves. Let me remind you that the number of points of an elliptic curve is computed by the formula
   n=q+1-t, where q — is the size of the underlying field. And recall that a curve is called supersingular if t is divisible by 2.
   Therefore, at first glance it might seem like a good idea to use curves in which the number of points equals q, i.e., t=1.
   However, such curves are called anomalous, and solving the discrete logarithm on anomalous elliptic curves is an even easier problem than for supersingular and singular curves.

Summary

Based on everything said above, let us list the main advantages and disadvantages of elliptic curve cryptography:
So, the main advantages:

1. A much shorter key length compared to “classical” asymmetric cryptography.
2. The speed of elliptic algorithms is much higher than that of classical ones. This is explained both by the field sizes and by the use of the binary finite field structure, which is closer to how computers work.
3. Because of the short key length and high speed, asymmetric elliptic curve cryptography algorithms can be used in smart cards and other devices with limited computational resources.

The main disadvantages of elliptic curve cryptography:

1. All the advantages of elliptic curve cryptography stem from one specific fact:
   no subexponential algorithms exist for solving the discrete logarithm problem on elliptic curves. This makes it possible to shorten the key length and increase performance. However, if such algorithms ever appear, it will mean the collapse of elliptic curve cryptography.
2. Elliptic curve cryptography — is very complex. Not that I consider ordinary asymmetric cryptography a completely simple thing. But “elliptics” — is a huge number of subtleties that need to be taken into account, starting with the choice of elliptic curve and ending with key generation. With a mass transition to elliptics, there will most likely inevitably be a large number of errors and vulnerabilities that have already been worked out for more familiar methods.

Based on everything said above, I concluded for myself that a universal transition to “elliptics” is not a necessity. After all, as long as ordinary RSA and DSA coexist peacefully on one side with GOST 34.10 and ECDSA on the other, there is a false but reassuring feeling of having an alternative, one we might lose by chasing after the most modern cryptographic methods.

References

1. Don Johnson, Alfred Menezes, Scott Vanstone — The Elliptic Curve Digital Signature Algorithm.
2. A. Bolotov, S. Gashkov, A. Frolov, A. Chasovskikh — An Elementary Introduction to Elliptic Curve Cryptography.
3. Lawrence Washington — Elliptic curves, Number theory and Cryptography.