Elliptical cryptography: theory

Hi% username%!
Recently, a very controversial article titled “Experts call for preparation for crypto apocalypse” was published on Habré . Honestly, I do not agree with the conclusions of the authors that the “holtecco danger”, everyone will soon crack and buckwheat will rise in price. However, I do not want to talk about it.
In the comments to the article, I expressed the opinion that in some ways the speakers are right and it is high time to switch to elliptical cryptography. Well, in fact, has anyone seen an ECDSA certificate on the Internet? Although the standard is almost 13 years old, we continue to use the good old RSA in the old manner. In general, I said this, and as it often happens, I wondered if it is necessary to switch to an “elliptic”? And what kind of animal is this elliptical cryptography? Which has pros, cons, subtleties. In a word, let's understand.

Elliptic curves

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

Typical options for graphs of elliptic curves you can see under the spoiler:

Elliptic curves presented in the first 4 figures are called smooth. While the two lower curves refer 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 independently develop a cryptographic product that supports the "elliptic" it is very important to remember the following fact:
It is impossible to use singular curves in EDS schemes. We will touch on this topic in detail, but now just say that using singular curves you risk significantly reducing the durability of the EDS scheme.
Arithmetic operations in elliptical cryptography are performed on points of a curve. The main operation is “addition”.
Adding two points is easy to imagine graphically:

As can be seen from the figure, to add the points P and Q, it is necessary to draw a straight line between them, which will necessarily cross the curve at any third point R. Reflect the point R relative to the horizontal coordinate axis and obtain the desired point P + Q.

Algebraic representation of "addition"

We write the addition of two points as a formula:

Let the coordinates of the point P be (x _p , y _p ), and the coordinates of the point Q, respectively, (x _q , y _q ). Calculate

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


')

Elliptic curves in cryptography

It remains to clarify only one detail. All the curves considered above refer to elliptic curves over real numbers. And that brings us to the rounding problem. That is, using curves over real numbers, we will not be able to get a bijection between the source text and the encrypted data. In order not to bother with rounding in cryptography, only curves above finite fields are used. This means that an elliptic curve is a set of points whose coordinates belong to a finite field.

In cryptography, two types of elliptic curves are considered: over a finite field - residue ring modulo a prime number. And over the field - binary finite field.
Do elliptic curves over a field there is one important advantage, the elements of the field can be easily represented in the form of n-bit code words, this allows you to increase the speed of the hardware implementation of elliptic algorithms.

All mathematical operations on elliptic curves over a finite field are performed according to the laws of a finite field over which an elliptic curve is constructed. Those. to calculate, for example, the sum of two points of the curve E over the residue ring all operations are performed modulo the number p.

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

described above a field of characteristic 2 or 3 becomes singular, and as noted above, this is an unfortunate idea to use singular curves in cryptography.

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


Another important concept of elliptic cryptography is the order of an elliptic curve , which shows the number of points of a curve over a finite field.
The Hasse theorem states that if N is the number of points of a curve defined over a field Zq with q elements, then the equality is true:


Since binary finite field consists of 2 ⁿ elements we can say that the order of the curve equals where .

The following definition is related to number t:
an elliptic curve over a binary finite field is called super-singular if t is divided by the characteristic field (in the case of a binary field, the characteristic is 2) without a remainder.
Of course, all this I mean, that it is impossible to use super singular curves in EDS schemes . The strict recommendation not to use singular and super singular 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 are a group. And as we noted above, the operation of addition is defined for this group.
Accordingly, we can represent the multiplication of the number k by the point G as G + G + .. + G with k terms.

Now imagine that we have the 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 parameters of the curve E (a, b), the ciphertext C and the point G.
This problem is called the discrete logarithm on an elliptic curve and does not have a quick solution. Moreover, it is believed that the discrete logarithm problem on an elliptic curve is more difficult 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.
So for solving the discrete logarithm there are sufficiently fast algorithms having complexity , where c and d are some constants, and p is the size of the field. Such algorithms are called subexponential and make it relatively easy to open the discrete logarithm in a finite field if the field size is not chosen very large, on the order of 2 ¹⁰²⁴ .
At the same time, the fastest methods for solving the discrete logarithm on an elliptic curve have the complexity where q is the number of points of the elliptic curve.
Thus, to ensure a level of stability of 2 ⁸⁰ operations, it is necessary that q = 2 ¹⁶⁰ . Let me remind you that in order to obtain a similar level of complexity in calculating a discrete logarithm in a finite field, a field of order q = 2 ^{1024 is} necessary.

However, it should be noted that since the power of computing technology is constantly increasing, the value of q will constantly increase. But since the graphics functions and differ sharply from each other, in the group of points of the elliptic curve q will grow much slower than in an arbitrary finite field.

Attack options

1. Polig-Hellman algorithm . Algorithm for solving discrete logarithm. Suppose that n is the number of points of an elliptic curve. Let number n be decomposed into primes p ₁ , p ₂ , .., p _n . The essence of the method is to find discrete logarithms modulo the number p _i , and then obtain a general solution using the Chinese theorem on residuals . The attack reduces the problem of a discrete logarithm in a large field n to the same problem, but with a much smaller field p. In order to resist the attack, you just need to choose the curves, the number of points of which is divided by a very large prime number q≈n.
2. The Shanks algorithm , better known as baby steps / giant steps. A typical example of time memory trade off. For a group of size n, tables of size n ^{1/2 are} calculated, then the desired element is searched for by this table. Algorithm complexity .
3. Vulnerability of singular and supersingular curves . I have already mentioned that there are no subexponential methods for solving the discrete logarithm problem. In fact, there is one reservation: there are such methods, but only for a certain kind of curves: singular and super-singular. The special properties of such curves allow us to reduce the problem of a discrete logarithm on an elliptic curve to the problem of a discrete logarithm in a finite field. Accordingly, for such a class of curves, standard keys of 160-320 bits will be fatally vulnerable, which will allow attackers to unlock 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 calculated by the formula
   n = q + 1-t , where q is the size of the source field. And that a curve is called super singular if t is divisible by 2.
   Therefore, at first glance it may seem like a good idea to use curves in which the number of points is q, i.e. t = 1.
   However, such curves are called anomalous, and solving the discrete logarithm on anomalous elliptic curves is even simpler than for super-singular and singular curves.

Summarize

Based on the foregoing, we write out the main advantages and disadvantages of elliptical cryptography:
So, the main advantages:

1. The key length is much shorter compared to the “classical” asymmetric cryptography.
2. The speed of the elliptic algorithms is much higher than that of the classical ones. This is explained both by the size of the field and the use of a binary finite field structure that is closer to computers.
3. Due to the short key length and high speed, asymmetric cryptography algorithms on elliptic curves can be used in smart cards and other devices with limited computing resources.

The main disadvantages of elliptical cryptography:

1. All the advantages of elliptical cryptography stem from one specific fact:
   For the discrete logarithm problem on elliptic curves, there are no subexponential solution algorithms. This allows you to reduce the length of the key and increase productivity. However, if such algorithms appear, it will mean the collapse of elliptical cryptography.
2. Elliptical cryptography is very difficult. Not that I considered ordinary asymmetric cryptography to be a very simple thing. But "elliptic" is a huge amount of subtleties that need to be taken into account. Starting with the choice of an elliptic curve and ending with the generation of keys. When a mass transition to an elliptic is likely to be sure to be a large number of errors and vulnerabilities that have already been worked out for more familiar methods.

Based on the foregoing, I concluded for myself that the ubiquitous transition to an "elliptic" is not a necessity. In the end, while the usual RSA, DSA peacefully coexist on the one hand, and GOST 34.10, ECDSA on the other, there is a false but soothing sense of alternative that we can lose by chasing the most modern cryptographic methods.

Used Books

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 Elliptical Cryptography.
3. Lawrence Washington - Number theory and Number theory and Cryptography.