Lecture
Post-quantum cryptography is a part of cryptography that remains relevant even with the advent of quantum computers and quantum attacks. Since quantum computers are significantly superior to classical computer architectures in the computational speed of traditional cryptographic algorithms, modern cryptographic systems are becoming potentially vulnerable to cryptographic attacks. Most traditional cryptosystems rely on integer factorization problems or discrete logarithm problems that will be easily solvable on large enough quantum computers using the Shor algorithm. [1] [2] Many cryptographers are currently developing algorithms that are independent of quantum computing, that is, resistant to quantum attacks.
There are classic cryptosystems that rely on computationally complex problems and have a number of significant differences from the systems mentioned above, which makes them much more difficult to solve. These systems are independent of quantum computing, and, therefore, they are considered quantum-resistant (quantum-resistant), or "post-quantum" cryptosystems.
Post-quantum cryptography, in turn, differs from quantum cryptography, which deals with communication protection methods based on the principles of quantum physics.
What is cryptography and what is it for? Say, Alice and Bob want to exchange a message, so that its contents are kept secret. Obviously, each side must have its own key. And at this stage, two subspecies of cryptosystems can be distinguished.
The first of them includes symmetric cryptosystems. Here, one key can be easily calculated from another, and often they completely coincide. Significant advantages of such cryptosystems are ease of implementation and high speed of operation due to the use of simpler operations. However, if one of the keys is compromised, any attempt to protect sensitive information will lose its meaning.
This problem is elegantly solved in asymmetric cryptosystems using special algorithms. However, here we are faced with the complexity of operations, which may be inefficient for a large amount of data. In such cryptosystems, you need to try very hard to calculate the other from one key, and, while someone else's computer does not have the enormous power of the dark side, you can be relatively calm for the secrecy of the protected data.
An interesting multi-way ... Well, how is it implemented, the inquisitive% username% will ask? It's all about the so-called one-way functions. Let there be a function y = f (x). Using the well-known argument x, it is easier to calculate the value of the function y than to capture Westeros with three dragons and an army of flawless ones. However, calculating the argument x from the known value of the function y is a rather time-consuming task.
The most famous candidates for one-sided functions are the number factorization problem, which consists in decomposing the number into prime factors, and the discrete logarithm problem, which consists in finding the unknown k from the known values of y and g that satisfy: y = gk. The first, for example, is used in the well-known RSA cryptosystem, and the second can be found in the Diffie-Hellman key establishment scheme.
However, given the rapid growth of computing device performance like a dragon’s flight, there is a need to increase the key length, but this can become a critical factor for devices with limited power ... Eh, it would be so cool if such a structure appeared that would reduce the size key with the same level of durability ... And, fortunately, it exists! The name of this miracle is an elliptical curve.
RSA, elliptic curves, quantum computer, isogeny ... At first glance, these words resemble some kind of spell, but everything is much more complicated than it sounds!
The need for a transition to cryptography resistant to attack on a quantum computer has already been officially announced by NIST and NSA, from which the conclusion is pretty simple: it's time to get out of your comfort zone!
So, it is worth moving away from the good old RSA and even, probably, from the elliptic curves that many people have loved and learn new, no less interesting primitives that can protect confidential information.
To understand the intricacies of cryptography on elliptic curves, to trace the new-fangled trends of post-quantum cryptography and even touch it using the Microsoft SIDH library, welcome to cat,% username%!
Elliptical Curve - Above Field 
Is a nonsingular cubic curve on the projective plane over 
(algebraic closure of the field ) defined by an equation of degree 3 with coefficients from the field and "point at infinity."
. They call it nonsingular, because you can unambiguously draw a tangent to all its points. Well, since this is a cubic curve, then it should be given by an equation of the third degree, which in the generalized form of Weierstrass looks as follows:
y2 + a1xy + a3y = x3 + a2x2 + a4x + a6
However, in practice, such a shape of the curve can be found infrequently. There are forms of Legendre, Montgomery, Hesse, etc. The use of one form or another can increase the efficiency of operations on points of an elliptic curve. For example, in the Montgomery form, it is possible to multiply a point by a number in a fixed time thanks to the Montgomery ladder algorithm.
Surely many came across a Weierstrass form, it is called canonical for fields with characteristic charK ≠ 2,3:
E (K): y2 = x3 + ax + b
An important characteristic of an elliptic curve is its discriminant, which for the Weierstrass form is calculated as follows: Δ = 4a3 + 27b2.
The discriminant should not be equal to zero, otherwise the curve will no longer be elliptical, since there will be inflection points, as on the curve y2 = x3−3x + 2 in the figure to the right.
Surely many are familiar with the image of the elliptic curve, which can be seen in the figure on the left. Here, a curve of the form y2 = x3−3x + 5 is defined over the field of rational numbers.
However, when using rational numbers, there is a difficulty with their rounding, and, as a result, with the ambiguity of encryption and decryption operations. Therefore, in cryptography, elliptic curves are defined over a finite field, where the coordinates of the points are the elements of the field. The curve graph, of course, will lose its former attractiveness, smooth lines will be replaced by dots, but we love elliptical curves far from it!
One cannot fail to mention one more characteristic of elliptic curves, which (SPOILER!) Will still give readers its presence in the article. This is a j − invariant, a constant. Its calculation for an elliptic curve in the form of Weierstrass also does not have a terrifying effect on the body: j = 17284a34a3 + 27b2
Group Properties
An important point in cryptography on elliptic curves is that the points of an elliptic curve with an abstract infinitely remote point form an Abelian group. Take addition as a group operation, then a group is such an algebraic structure that has the following properties:
A few words about persistence
Now let's talk a little about the strength of cryptosystems based on the discrete logarithm problem. Let G be a finite cyclic group, that is, each of its elements can be represented as the degree of a single element - the generator g: = G = {1, g2, g3, ..., gq − 1}.
Depending on the choice of the group G, there are various methods for solving the discrete logarithm problem. So, to solve the discrete logarithm problem in a finite field, unfortunately, there are not only universal algorithms (the Polyg-Hellman method, the Pollard ρ-method, etc.) that have exponential complexity, but also special ones that have sub-exponential complexity (the decomposition base method , sieve method of a numerical field).
If we take the point of an elliptic curve as the generator of the group G, then the crypto-rogues will have to be content only with universal algorithms. Therefore, cryptography on elliptic curves "pamper" users with a shorter key length.
However, not all elliptic curves are capable of providing a high level of strength in cryptographic protocols. The first danger is supersingular curves. Their advantage is the ease of calculating the number of points, in contrast to non-super-singular curves. There are many factors by which a supersingular curve can be distinguished from a nonsupersingular curve, but in this article we will not focus on this point.
These curves are vulnerable to a MOV attack, which allows one to reduce the calculation of the discrete logarithm problem in the group of points of the elliptic curve over the field Fq to the discrete logarithm problem in the final field Fqk. Considering that the key length in cryptography on elliptic curves is less, and that for supersingular curves the value of k is not large, the implementation of this attack is extremely successful for an attacker.
So what's the problem? We use suitable elliptic curves and enjoy life! But it was not there…
Post-quantum cryptographic constructions can save the cryptographic world from quantum attacks. Although a quantum computer will destroy most of the traditional algorithms (RSA, DSA, ECDSA), ultrafast computations cannot completely get rid of cryptography, since post-quantum cryptography is mainly focused on five different approaches that solve the problem of quantum attacks. [2] [3] ]
A classic example is a hash tree public key Merkle signature, Ralph Charles Merkle proposed this digital signature algorithm in 1979 as an interesting alternative to RSA and DSA digital signatures. The main drawback of the Merkle scheme is that for any public key based on a hash function, there is a limit on the number of signatures that can be obtained from the corresponding set of private keys. This fact reduced the level of interest in signatures of this type until there was a need for cryptography resistant to the effects of quantum computers.
It is one of the most promising candidates for post-quantum cryptosystems. A classic example is McEliece and Niederreiter encryption schemes.
A classic example of encryption schemes is Ring-Learning with Errors or older NTRUs and GGHs.
One of the most interesting schemes is Jacques Patarin's public key signature HFE, which he proposed in 1996, as a generalization of the sentences of Matsumoto and Imai.
A vivid example is the Rijndael cipher, proposed in 1998, subsequently renamed AES (Advanced Encryption Standard).
This is an analogue of the Diffie-Hellman protocol, based on wandering in a supersingular isogenic graph, allowing two or more parties to obtain a common secret key using a communication channel that is not protected from listening.
In 1978, a document published by the developers of the RSA public key cryptographic algorithm (an abbreviation for the names Rivest, Shamir, and Adleman) mentioned Richard Schreppel’s new linear sieve algorithm, which factorized any RSA module} 
lengths 
bit using 
simple operations. Thus, in order for this algorithm to require at least 
simple operations, you must choose at least no less than 
bit. As 
means something converges to {\ displaystyle 0.5} 
at 
, then to find out the correct size {\ displaystyle n} at the final {\ displaystyle b} 
A more thorough linear sieve speed analysis is required.
In 1988, John Pollard] proposed a new factorization algorithm called the General Method of Sieve a Number Field. This algorithm factorized the RSA module. dimensions 
bit using 
simple operations. Therefore, you need to choose not less than 
bit so that the algorithm takes at least simple operations.
Since 2008, the fastest factorization algorithms for classical computer architectures use at least 
simple operations. There were some improvements in the values 
and in detail 
but it’s not hard to guess that {\ displaystyle 1/3} 
optimally and that module selection approximately equal in length 
bit, will resist all possible attacks on classic computers.
In 1994, Peter Shore proposed an algorithm that factorized any RSA module. dimensions 
(more precisely 
) qubit operations on a quantum computer of order size 
qubit (and a small number of auxiliary calculations on a classical computer). Using the Shore algorithm, you must at least select the module {\ displaystyle n} bit size no less than 
bit, which is too big a number for any of our interest {\ displaystyle b} [9].
There are very few examples of algorithms that are resistant to quantum attacks. But despite the greater level of cryptographic stability, post-quantum algorithms are unable to displace modern cryptosystems (RSA, DSA, ECDSA, etc.).
Consider attacks on a public-key cryptosystem, namely, the McEliece encryption algorithm, which uses the Goppa binary codes. Originally, Robert McAlice] introduced documents in which codes are {\ displaystyle n} long hacked for 
simple operations. Therefore, you need to choose not less than 
bit so that the algorithm takes at least simple operations. Several subsequent works reduced the number of attack operations to 
but 
significantly less 
if {\ displaystyle n} great. Therefore, improved attacks still use simple operations. As for quantum computers, their use will only lead to a decrease in the constant {\ displaystyle 0.5} , which will slightly reduce the number of operations required to crack this algorithm.
If the McEliece encryption system is so well-protected, why doesn't it replace the RSA? It's all about efficiency - in particular, the size of the key. McEliece public key uses approximately 
≈ 
bit, while the RSA public key is enough about 
bit. If bit for McEliece, there will be less 
bit for RSA but real security levels like 
, allow RSA to have a public key of several thousand bits, while for McEliece the key size is close to a million bits.
Recently, quantum computing has gained wide popularity. If in a classical computer the smallest unit of information is represented by a bit, which can take the value either 0 or 1 at one time, then in a quantum one this role is played by qubits. Their feature is that the qubit can be both in state 0 and in state 1 at the same time. This gives quantum computers their superior computing power. For example, if we consider four bits of information, then from all sorts of 16 states, we can choose only one at a time. 4 qubits can be in 16 states at the same time, that is, in superposition, and this dependence grows exponentially with each new qubit.
If in a classical computer logic elements receive bits of information at the input, and an unambiguously determined result is output, then in a quantum computer, the so-called quantum gate (quantim gate) is taken as a logical element, which manipulates the value of the whole superposition.
An important phenomenon characteristic of qubits is confusion. For example, we have two tangled qubits. Measuring the state of one of them will help to find out information about the state of his pair without the need for any verification.
It should be noted that a quantum computer is not a substitute for the familiar to us classical one, since they are faster only in performing computational operations, where it is necessary to use all kinds of superpositions. So for watching videos with cats using such a machine is completely impractical.
On the one hand, the advent of a quantum computer is cool. Really. In many areas of science, such a machine will bring many benefits (for example, in modeling), but for cryptography such a significant breakthrough will be critical. And all because in 1994, Peter Shore proposed a quantum algorithm that allows us to expand the number not in hundreds of millions of years, but in quite visible time.
Modification of this algorithm allows us to solve the discrete logarithm problem. In general, the Shore method consists in reducing a problem that is difficult on a classical computer to computing the order of a certain function. If we consider the factorization of the number, or the factorization problem, then we take f (x) = ax (modN) as the function itself, where N is the number that can be expanded, and a is a specially selected value that is coprime to N. during the algorithm, we find the period of the function w, which satisfies the relation: f (x + w) = f (x) and, as a result, aw = 1 (modN). Using the found period, one can calculate the eigen divisor of N using the Euclidean algorithm: gcd (aw2, N).
In order to solve the discrete logarithm problem, that is, to find such k from the data y = gk, it is necessary to calculate the order of another function, namely: f (x1, x2) = gx1yx2, where g is the generator of the group with the number of elements equal to q . The period of the function is represented by a pair of numbers (w1, w2): f (w1 + x1, w2 + x2) = f (x1, x2). Then the solution to the discrete logarithm problem will have the form: k = −w1w2 (modq).
Thus, in the Shore method, the quantum and classical parts can be distinguished, and the task of the quantum part of the algorithm is to find the period of the function using the superposition method.
It is not surprising that the existence of such algorithms and the tendency to develop quantum computers pushed special organizations to think. The US National Security Agency, for example, back in 2015, announced a plan for the transition to algorithms that are resistant to a quantum computer attack. And in 2016, NIST USA officially announced the launch of a call for proposals for the development of post-quantum cryptography algorithms.
Post-quantum cryptography is not limited to one primitive, in fact, several candidates are currently being considered. These may, for example, include fast cryptographic protocols on gratings, hash function schemes (for example, Merkle's signature), and cryptosystems based on non-commutative algebra (for example, on a braid group). We opted for an alternative that is closely related to elliptical curves (we love them so much!), Namely, isogeny.
Let's start with the concept: isogeny is a rational map that takes points of a single elliptic curve to points of an isogenic curve, leaving the point at infinity indefinitely stationary. Suppose we have two isogenic elliptic curves E1 and E2. They are called isogenic if they are defined over one field and have the same number of points.
So, isogeny is, in fact, a small VZHUH, which takes the point of the curve E1 to the input, and at the output it gives the point of the curve E2. The core of isogeny is the set of points on the curve E1 that go to the infinitely distant point of the curve E2.
For each isogeny, there is a single dual isogeny that performs the inverse transformation. That is, if the isogeny has the following form: 
then dual to her: 
If we multiply the isogeny and the dual to it, we get the point of the curve E2 multiplied by an integer l, which is called the degree of isogeny. Isogenies of simple degrees can define permutations on the set of j − invariants of isogenic curves. A sequential overlap of graphs of isogenic elliptic curves allows you to get just a cosmically beautiful star of isogenic curves, as in the figure below.
The possibility of using isogeny to build cryptosystems has been proposed relatively recently. In 2003, the author E. Teske published a work where isogeny was used in a scheme with the possibility of depositing keys. In 2006, A.G. Rostovtsev and A. Stolbunov, the El Gamal encryption scheme was adapted for the isogeny of elliptic curves. Also in 2006, to construct hash functions, it was proposed to use graphs of isogenic supersingular curves. An important and, one might say, turning point in the study of isogeny is the work published in 2010, which proposes a quantum algorithm that solves the problem of finding isogenies of non-super-singular curves in sub-exponential time. From this point on, studies have become more focused on supersingular curves. So, on the network you can already find public key encryption schemes, evidence with zero disclosure, a scheme of undeniable signatures and blind signatures.
Microsoft also did not stand aside and in 2016 released the open source SIDH library (Supersingular Isogeny Key Exchange). One of the advantages of this library is the ability to use elliptical curves in the shape of Montgomery, which protect against time attacks.
SIDH is implemented in C and supports the use of Microsoft Visual Studio on OC Windows and LNU GCC and clang on OC Linux. The library presents the implementation of basic arithmetic functions with the ability to support various platforms, including x64, x86 and ARM. A big plus for performance is the optimized implementation of operations on elliptic curves.
The library implements the Diffie-Hellman key separation protocol for isogeny of supersingular curves.
This scheme was proposed by Jao and DeFeo. Simplified, it can be described as follows. As parameters of the cryptosystem, the well-known supersingular curve E0 and the points PA, QA, PB, QB fixed on it are used. For convenience, the protocol can be monitored in the figure below.
Let Alice want to share with Bob, not life, but the private key. To do this, it generates random numbers mA, nA and constructs the isogeny ϕA: E0 → EA, where the kernel is specified as.
Bob performs the same actions, but only builds isogeny, where he selects as the core.
The isogeny ϕA and ϕB are secret and are not transmitted to anyone. However, both Bob and Alice can divide the points into their isogenic curves without any consequences, and besides, the curves themselves can be transferred. This is what really happens. This stage is indicated by a dashed line in the figure. Alice gives Bob the points ϕA (PB) and ϕA (QB), and the curve EA itself. Bob does the same: passes Alice points ϕB (PA) and ϕB (QA and curve EB.
Is this legal at all ?! You can be calm,% username%, knowing both isogenic curves, the attacker will not be able to calculate the isogeny itself.
So, Alice and Bob exchanged data, now we are approaching the final and incredibly beautiful stage, namely, obtaining a common key. Knowing the images of the points PA and QA on the curve EB and the random numbers mB and nB, Bob can easily construct the isogeny ϕA ′, and Alice, having the same amount of information, can construct the isogeny ϕB ′. An elegant solution is that the isogeny of ϕA ′ and ϕB ′ will lead our interlocutors to the EAB curve, and its j-invariant can be taken as a key.
Microsoft has greatly simplified life by implementing basic functions that free coding of the above steps of the algorithm. Before implementing the key separation scheme, it is necessary to initialize the structure, which contains the parameters of the cryptosystem:
CurveIsogeny = SIDH_curve_allocate (CurveIsogenyData);
if (CurveIsogeny == NULL) {
Status = CRYPTO_ERROR_NO_MEMORY;
goto cleanup;
}
Status = SIDH_curve_initialize (CurveIsogeny, & random_bytes_test, CurveIsogenyData);
if (Status! = CRYPTO_SUCCESS) {
goto cleanup;
}
The structure itself:
typedef struct {CurveIsogeny_ID CurveIsogeny; unsigned int pwordbits; unsigned int owordbits; unsigned int pbits; uint64_t prime [MAXWORDS_FIELD]; uint64_t A [MAXWORDS_FIELD]; uint64_t C [MAXWORDS_FIELD]; unsigned int oAbits; uint64_t Aorder [MAXWORDS_ORDER]; unsigned int oBbits; unsigned int eB; uint64_t Border [MAXWORDS_ORDER]; uint64_t PA [2 * MAXWORDS_FIELD]; uint64_t PB [2 * MAXWORDS_FIELD]; unsigned int BigMont_A24; uint64_t BigMont_order [BIGMONT_MAXWORDS_ORDER]; uint64_t Montgomery_R2 [MAXWORDS_FIELD]; uint64_t Montgomery_pp [MAXWORDS_FIELD]; uint64_t Montgomery_one [MAXWORDS_FIELD]; } CurveIsogenyStaticData;
In order for Alice and Bob to exchange keys, it is enough to call a couple of functions that do not oblige you to know what is happening “under the hood”. Key generation takes place using functions:
Status = KeyGeneration_A (PrivateKeyA, PublicKeyA, CurveIsogeny) ;
and
Status = KeyGeneration_B (PrivateKeyB, PublicKeyAB CurveIsogeny) ;
Alice and Bob exchange the calculated public keys and find the common key:
Status = SecretAgreement_A (PrivateKeyA, PublicKeyB, SharedSecretA, false, CurveIsogeny) ;
and
Status = SecretAgreement_B (PrivateKeyB, PublicKeyA, SharedSecretB, false, CurveIsogeny) ;
Among the functions in the library, one can distinguish basic arithmetic, which will help in the implementation of their protocols. This, for example, j_inv, calculating the j-invariant of an elliptic curve, inv_3_way, finding the value of the multiplicatively inverse, doubling the point and adding points - xDBLADD, tripling the point - xTPL, etc. You can find the full description in the publication.
Of course, it is still difficult to judge the need for post-quantum cryptography, when, in fact, there is no powerful quantum computer ... However, the fuss in the NSA and NIST cannot but lead to suspicions. We can only guess about the real motives for such a rush. In any case, it never hurts to play it safe and start exploring a new and interesting direction in cryptography, especially if it is quite feasible in practice.
Comments
To leave a comment
Information security, Cryptography and cryptanalysis, Steganography and Stegoanalysis
Terms: Information security, Cryptography and cryptanalysis, Steganography and Stegoanalysis