Post-quantum reincarnation of the Diffie-Hellman algorithm: past and present

As you know, the last revolution in cryptography occurred in 1976 due to the article “New Directions in Cryptography” by American scientists Whitfield Diffie and Martin Hellman. This work was for the subsequent development of cryptography as the “Big Bang” - the birth of a new universe of asymmetric cryptography took place. Until that moment (at least in the open press) there was only symmetric cryptography. Young and then unknown scientists were the first to propose a scheme in which, in order to develop a common secret, the subscribers initially did not need to exchange any secret keys. In addition to its primordial nature, this algorithm is interesting in that despite the fact that the “complex” tasks that underlie its security may become obsolete, they can be successfully replaced with new ones. Initially, this was a discrete logarithm task in a multiplicative group of a finite field (Discrete Logarithm Problem, abbr. - DLP), now in practice the discrete logarithm problem in a group of points of an elliptic curve (Elliptic Curve DLP - ECDLP) is widely used. In the future (not so distant), it is supposed to use other “complex” problems that will have exponential complexity not only on a classical, but also on a quantum computer. They are called post-quantum. One of these problems is the problem of finding isogeny between elliptic curves, which I want to talk about in this article. Now in practice, the discrete logarithm problem is widely used in the group of points of an elliptic curve (Elliptic Curve DLP - ECDLP). In the future (not so distant), it is supposed to use other “complex” problems that will have exponential complexity not only on a classical, but also on a quantum computer. They are called post-quantum. One of these problems is the problem of finding isogeny between elliptic curves, which I want to talk about in this article. Now in practice, the discrete logarithm problem is widely used in the group of points of an elliptic curve (Elliptic Curve DLP - ECDLP). In the future (not so distant), it is supposed to use other “complex” problems that will have exponential complexity not only on a classical, but also on a quantum computer. They are called post-quantum. One of these problems is the problem of finding isogeny between elliptic curves, which I want to talk about in this article.

Since the purpose of the article is to simply explain the new mathematical “engine” for the Diffie-Hellman protocol (Diffie-Hellman or DH for short), some attacks are not considered: we assume that the attacker can only read messages in the channel, but cannot interfere with the channel’s work in order to intercept subscriber messages and send their own (that is, the attacker is not “Man in the Middle”). In practice (for example, in the TLS protocol), a DH public key can be signed and there is already a Man in the Middle who cannot replace a DH key: from a server a DH public key comes as a certificate, from a client to a server - a temporary (ephemeral) key signed on a permanent closed key EDS client. In general, in harsh reality, DHI is saved by replacing PKI with public key technology based on the trust of both parties to one CA. But, Again, in order not to distract the reader from the main thing - mathematics, I do not write anything about PKI in this article. And again: since there are cases when systems were implemented and implemented in which the parties exchanged temporary (ephemeral) public keys that the parties did not check in any way (apparently those who designed them considered themselves too busy to learn the basics of cryptography, or at least turn to specialists), then please do not forget that in real life this is necessary. The Man in the Middle (aka Mediator, aka Man-in-the-middle) is not a Bigfoot and he exists. which the parties did not check in any way (apparently those who designed them considered themselves too busy to learn the basics of cryptography or at least turn to specialists), please do not forget that this is necessary in real life. The Man in the Middle (aka Mediator, aka Man-in-the-middle) is not a Bigfoot and he exists. which the parties did not check in any way (apparently those who designed them considered themselves too busy to learn the basics of cryptography or at least turn to specialists), please do not forget that this is necessary in real life. The Man in the Middle (aka Mediator, aka Man-in-the-middle) is not a Bigfoot and he exists.

The Past: Classic Diffie Hellman

Alice and Bob initially choose domain parameters: the multiplicative group of a finite field and g is the generator of its subgroup. There is nothing wrong with the word generator. This is just one of the elements of the group with the following property: if we take its degrees from 1 to the number of elements in the group, we get the whole group. A subgroup is a subset of a group, which in itself is also a group (if we multiply its elements in any combinations, we get only elements of this very subset).

Example:$$ Is the multiplicative group of a finite field.

Group Elements:

numbers from 1 to p - 1, where p is a prime number.

Group operation a * b mod p: multiply the elements of the group a and b, then a * b divide by p. The remainder of dividing a * b by p is the result of the operation a * b mod p.

For example, let p be equal to 11. Most often denoted as $$. Consists of 11 - 1 = 10 elements: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

The number of elements in a group is called the group order. Order$$ equal to 10.

Now let's play a little with operations:

5 * 6 mod 11 = 8,
1 * 10 mod 11 = 10.

1 for this group is a neutral element. Neutral - because it “does not interact” with any other elements and the result of the operation with it is always equal to the second element of the operation. In this case, 1 * 10 mod 11 is 10.

6 * 2 mod 11 = 1.

For any element of any group, there is an inverse element that “turns” it into a neutral one. For this group, 6 and 2 are inverse to each other.

When a group operation is called multiplication (as is the case $$), then we use such notation for the converse to $$ item: $$ Those. $$*$$= 1 What else can be said about this group? It is commutative (or abelian):

$$ mod p = $$ mod p: from a permutation of a and b, the result does not change.

Group generators are its elements, all degrees of which are all elements of the group. Groups in which there is at least one such element are called cyclic. How to understand that x is a generator? The most primitive method: build a table of degrees x:

What about degrees 2?

2 * 2 mod 11 = 4
4 * 2 mod 11 = 8
8 * 2 mod 11 = 5
5 * 2 mod 11 = 10
10 * 2 mod 11 = 9
9 * 2 mod 11 = 7
7 * 2 mod 11 = 3
3 * 2 mod 11 = 6
6 * 2 mod 11 = 1 - we see that the cycle is closed. Degrees 2 generate the whole group$$.

Total: 2 - generator $$.

The order of the element is the minimum degree to which it must be raised to get neutral. Order 2 in$$ equal to 10.

Now consider the degrees 3:

3 * 3 mod 11 = 9
9 * 3 mod 11 = 5
5 * 3 mod 11 = 4
4 * 3 mod 11 = 1

Order 3 is 5. It does not “run through” all values $$because we see that looping occurs to the fifth degree: if we continue the multiplication, then again we get 3, 9, 5, 4, 1.

What else can be said about 3?

This is also a generator. But not for$$, and for its subgroup consisting of five elements {3, 9, 5, 4, 1}.

Easy to see that this is a subset $$ -subgroup: there is a neutral element 1. Closure: the result of any a * b mod p for these numbers does not go beyond this set, because the result will be one of the set {3, 9, 5, 4, 1}.

Each element has the opposite: 3 * 4 mod 11 = 1, 9 * 5 mod 11 = 1, 1 * 1 mod 11 = 1. What other subgroups are there in $$?

There is still a group of order 2: {1, 10}

And of course, the trivial subgroups {1} and {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} (since formally the group is a subgroup of itself)

How to optimize generator search for $$?

Here it is necessary to use the foundation of group theory - the Lagrange theorem: “The order of a subgroup divides the order of the group”.

The element x is either a generator of a group or a generator of one of its subgroups. Consequently, raising x to the power of orders of subgroups and comparing the result with 1 can confirm or refute this.

Back to $$. Thanks to the Lagrange theorem, we can quite confidently say that there are nontrivial subgroups of only orders 2 and 5, since the order$$is equal to 10.

Thus, we could reduce the calculations for 2, raising it only to the power of 2 and 5!

$$ mod 11 = 4 ≠ 1
$$ mod 11 = $$*$$*$$ mod 11 = $$ mod 11 = 10 ≠ 1 Now these calculations are enough to prove that 2 is a generator $$
Similarly for 4:
4 * 4 mod 11 = 5 ≠ 1 ok, the next step is the fifth power for 4:
$$ mod 11 = $$*$$* 4 mod 11 = 5 * 5 * 4 mod 11 = 100 mod 11 = 1 -> 4 - this is not a generator $$What if the structure is a little more complicated? Consider$$:
Order 18 = 3 * 3 * 2. Divisors 18: 2, 3, 6, 9 Choose a random element, for example 3:
Raise 3 to the power of r1 = 18/3 = 6:
$$mod 19 = 7 ≠ 1
Raise 3 to the power of r2 = 18/2 = 9:
$$mod 19 = 18 ≠ 1

It is absolutely not necessary to raise the element under study to the power of all subgroups i.e. 2, 3, 6, 9, because if an element turns out to be a generator of a subgroup of a subgroup, then raising the power of the order of the subgroup to any degree will yield 1.

For example, if we chose not 3, but 11, we would stop at the first step:

$$mod 19 = 1.
since 11 is of order 3
$$ mod 19 = $$ mod 19 = $$mod 19
3 in$$generates a subgroup {1, 7, 11}

Nontrivial subgroups$$: {1, 18}, {1, 7, 11}, {1, 7, 8, 11, 12, 18}, {1, 4, 5, 6, 7, 9, 11, 16, 17}

But let's go back to DH. In practice, this is the choice of parameters for it - this is the choice of large (~$$, i.e., length 3072 bits) of the prime number p and the generator $$order $$ which (i.e. the minimum degree that yields 1: $$ mod p = 1) is also a large prime number (~$$) The basic operation that is performed in the algorithm is raising to a power x modulo:$$ mod p.

Note: Alice and Bob need to check the keys coming from outside for belonging to their “working” subgroup of large simple order q:

Alice is checking $$mod p = 1? If not, the protocol is aborted.

Bob does the same: he checks the key that came from Alice: $$ mod p = 1?

Now we are not considering an adversary who could replace public keys along the way, but nevertheless one should always remember that in cryptography there are cases from the category of “with such friends we don’t need enemies”: the program on Alice or Bob devices may contain various errors (in the implementation of modular arithmetic, or memory may just be damaged).

If the checks went fine, then Alice and Bob count keys for symmetric algorithms in order to protect the data transmission channel with their help (for example, encrypt data and read MAC (Message Autentication Code) or just read MAC).

Reverse to$$ mod p operation is called Discrete Logarithm (DL) or, in our Discrete Logarithm: let p, g and $$. It is required to find the degree of x. This is just what is very interesting to the attacker.

Of course, cryptographers are not involved in the selection of the group, of course, but Alice or Bob personally (although a certain subset of all Alice and Bobov belongs to their set, but we do not consider this particular case). A subset of cryptographers who are deeply versed in the structure of groups and know which ones to use safely sometimes publish the results of their work in the form of specific numbers p, g and step-by-step descriptions of algorithms with test vectors. They can be found in the form of NIST or RFC standards.

Here is an example of unsafe parameters for DH: a group of “smooth” order, i.e. in which the number of elements can be represented as the product of the degrees of small primes, because it can easily calculate the discrete logarithm using the Pollig-Hellman method, which calculates the discrete logarithm in the subgroups of the group, and then using the Chinese remainder theorem obtains the logarithm for the group itself. Since the calculations by the Chinese theorem themselves are quite simple, the complexity of the entire Pollyg-Hellman algorithm can be approximately estimated as the complexity of computing DL in the largest of the subgroups of simple order.

Present: Elliptical Diffie Hellman

In 1985, Neal I. Koblitz and Victor Saul Miller independently invented how to use elliptic curves in cryptography. Their discovery helped to create elliptic versions of the Diffie-Hellman, El-Gamal, MQV, DSS, GOST R 34.10-94 algorithms, which initially used the multiplicative group of the finite field. As a result, new algorithms (with the exception of GOST) received the EC prefix: ECDH, EC ElGamal, ECMQV, ECDSS. And our Russian GOST R 34.10-94 was transformed into GOST R 34.10-2001 (and then into the more reliable 34.10-2012). Why was such a transition to elliptic curves necessary? It allowed faster calculations with the same level of security.

Alice and Bob choose domain parameters for elliptic curves.

What do the Domain parameters for elliptic curves consist of:

1. Galois field GF ($$) Consists of$$elements, where p is the
field characteristic (prime number)
(In practice, n = 1 is more often used. GF ($$) and is called
a prime field. Its elements are all numbers from 0 to p-1)

2. The Weierstrass equation of the curve over the field GF ($$) (“Above the field” means that
all the coefficients (in this case A and B) and the solutions (x and y) are the elements of the field):

$$= $$+ A$$+ B (for p> 3)

where A and B are such that 4$$+27$$≠ 0, x, y are the affine
coordinates

3. The order of the group of points (the number of all its elements) is
denoted by #E (GF ($$))
It is represented as q * k, where q (a large prime) is the order of the subgroup, and k is a small
number (not necessarily prime) is called cofactor (factor)

4. Generator of a subgroup of a group of curve points (base point): a point Q having order q. (The Pollyg-Hellman discrete logarithm algorithm is also applicable to the group of points of the elliptic curve, as well as to any other Abelian group, therefore the group of points must have a “non-smooth” order. That is, equal to the product of a large prime number by a small number. In contrast to in the classical version, the group of which always contains a p-1 element, the group of elliptic curves can also have a simple order)

Recall the most basic:

Elements of a group are points of a curve, i.e. pairs (x, y) are solutions of the Weierstrass equation. The group operation is called the addition of points:

(x1, y1) + (x2, y2) = (x3, y3)

Plus there is also the so-called Point At Infinity or zero point (but a point at infinity - it sounds more beautiful, agree) We denote it by O. This is the analogue of unity for the multiplicative group of a finite field (from the classical DH): 1 * t mod p = t * 1 mod p = t, for curves: (x, y) + O = O + (x, y) = (x, y). Her fundamental difference from the sister from the multiplicative group is that she cannot be represented in the form of any elements of the field, i.e. as an ordinary point (x, y) so that it is possible to carry out calculations with it as with the rest of the points according to the general formula.

In the first part of the article, we will consider only a simple field GF (p), therefore, all examples and formulas use the suffix mod p: The

formula for adding points (X1, Y1) and (X2, Y2):

X3 =$$- X1- X2 mod p
Y3 = µ (X1 - X3) - Y1 mod p

where µ = (Y2-Y1) / (X2-X1) mod p if X1 ≠ X2:

If X1 = X2 and Y1 = Y2 ≠ 0, then μ = (3$$+ A) / 2Y1 mod p

In the case when X1 = X2 and Y1 = - Y2 mod p, then the formulas are not applicable and the result is a point at infinity.

Fractions help to more beautifully express the inverse element in the multiplicative group: for example,$$ mod p means $$*$$ mod p where $$ - inverse to value $$

We denote the scalar product of the number n by the point Q as follows: [n] * Q.
[n] * Q = Q + Q + ... + Q + Q

n times (this is a sequential addition operation performed n times using the above formulas) An attacker knows the domain parameters: curve and point Q (subgroup generator) as well as the result of scalar multiplication n to the point Q: [n] * Q. What he wants to find: the number n (i.e. solve the ECDLP problem). In which case is it easy? Captain Evidence says that if Q belongs to a small subgroup, then the point [n] * Q will belong to the same subgroup and the attacker will iterate over all possible scalars and multiply them by Q until he receives the point [n] * Q known to him. Therefore, Q must belong to a subgroup of large prime order.

So, the main group must contain a subgroup of large simple order (in other words, the order of the whole group must be NOT smooth). Captain Evidence is back in business and reports: for a group to contain a large subgroup, the group itself must be large. The order of the group of points of the curve E over the field GF ($$) is denoted by #E (GF ($$)). Hasse's theorem gives a very useful estimate:

#E (GF ($$)) = $$ + 1 - t, where t is the Frobenius trace, which in absolute value t ≤ 2 *$$. Those. group order #E (GF ($$)):
$$ + 1 - $$ ≤ #E (GF ($$)) ≤ $$ + 1 + $$

Now we know how the number of field elements is related to the number of points: they practically do not differ in order. Can it be argued that for an attacker it is necessary to order the points of the calculation curve to obtain a scalar? For “brute force” - yes, but there is a more beautiful method that requires much less effort. Pollard’s method, which is also applicable to DLP (as well as to any other commutative group). This is a probabilistic algorithm. The number of operations that it requires is about the square root of the number of elements in the group. Thus, if we consider “combat” cryptographic curves (cq * k, where q is a large prime and k is a small number: in practice 1, 2 or 4), then their security can be conveniently estimated as the number of operations that an attacker must perform when using the most “advanced” method for these curves - the Pollard method.

Example:

The most commonly used NIST P-256 curve in the world over a plain field.
The structure of her group is this: the order is a large prime. That is, the order is q * k, where q is prime and cofactor k = 1. Its safety can be estimated as$$, since today for NIST P-256 nothing better than the Pollard method has not been invented.

In addition to curves with a smooth order, there are others that make it relatively easy to solve ECDLP: supersingular (with a Frobenius trace t such that: t mod p = 0) and anomalous (t = 1). Suppose that the Bob and Alice curve does not fall into any of these bad companies and therefore it is practically impossible to solve ECDLP for it.



Note: as in the case of classic DH, checking all (incoming and outgoing) points to belong to a group is considered a good form, but here the situation is a little more complicated. First, the coordinates are substituted into the equation - this is a check for entry into the group. Then, to check that a large subgroup of order q belongs to, we multiply the point by q. If as a result we get a point at infinity, then everything is OK, but if not, the point lies in some other subgroup and the protocol should be interrupted.

Total:

Classic DH: as a result of the key exchange, Alice and Bob have the same element in the group: its generator multiplied by itself x * y times:$$mod p

And now copypaste:

Elliptical DH: as a result of the key exchange, Alice and Bob have the same group element: its generator is the Q point, folded x * y times: [x * y] * Q

The difference in the name of the operations for these groups (addition or multiplication) is not important (because the group only has only one operation). So now we’ll try more universally:
as a result of the key exchange, Alice and Bob have the same element in the group: her generator, over which the group operation with him was performed x * y times.

Quantum Nightmare and Hate

Classical and elliptical DH, in addition to mathematical elegance, combines one unpleasant fact: the complex (for ordinary computers) ECDLP and DLP problems underlying them can be easily solved if quantum computers are created that can hold a sufficiently large number of qubits (from several hundred to several thousand). In addition, this means the end for the RSA cryptosystem: the Shore quantum algorithm allows large numbers to be decomposed into prime factors in polynomial time. Therefore, it is precisely for asymmetric algorithms that the post-quantum topic is very relevant. For symmetric ciphers, everything is not so terrible so far - they will be attacked by the Grover quantum algorithm, which has the complexity of the square root of the power of the set of keys. For example, if you used AES with a key length of 128 bits,$$operations on a quantum computer).

One of the most promising complex mathematical problems resistant to quantum computers is the isogeny of elliptic curves. Read about them in the sequel .

References:

Bruce Schneier, Niels Ferguson “Practical Cryptography”
Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone “Handbook of Applied Cryptography”
Lawrence C. Washington “Elliptic Curves: Number Theory and Cryptography, Second Edition”