Elliptic cryptography is a section of cryptography that studies asymmetric cryptosystems based on elliptic curves over finite fields . The main advantage of elliptic cryptography is that today it is not known that there are subexponential algorithms for solving the discrete logarithm problem.
The use of elliptic curves to create cryptosystems was independently proposed by Neil Koblitz and Victor Miller in in 1985 [1]
Introduction
In 1985, independently, Neil Koblitz and Victor Miller proposed using the algebraic properties of elliptic curves in cryptography. From this moment began a rapid development of a new direction of cryptography, for which the term "cryptography on elliptic curves" is used. The role of the main cryptographic operation is performed by the operation of scalar multiplication of a point on an elliptic curve by a given integer, determined through the addition and doubling of the points of the elliptic curve. The latter, in turn, are performed on the basis of addition, multiplication and inversion operations in the final field, over which the curve is considered. Of particular interest in the cryptography of elliptic curves is due to the advantages that its application in wireless communications provides - high speed and short key length [2] Asymmetric cryptography is based on the complexity of solving some mathematical problems. Early public-key cryptosystems, such as the RSA algorithm , are cryptographic-proof due to the fact that it is difficult to factor the composite into prime factors. When using algorithms on elliptic curves, it is assumed that there are no subexponential algorithms for solving the discrete logarithm problem in groups of their points. The order of the group of points of the elliptic curve determines the complexity of the problem. It is believed that to achieve the same level of cryptographic strength as in RSA, smaller orders are required, which reduces the cost of storing and transmitting information. For example, at the RSA 2005 conference, the National Security Agency announced the creation of “Suite B”, which uses exclusively elliptic cryptography algorithms, and only 384-bit keys are used to protect information classified before “Top Secret”.
Elliptic Curves Above Finite Fields
An elliptic curve is called a set of points. satisfying the equation:
This equation can be considered over arbitrary fields and, in particular, over finite fields of particular interest for cryptography.
In cryptography, elliptic curves are considered over two types of finite fields : simple fields of odd characteristic ( where Is a prime number) and fields of characteristic 2 ( )
Elliptic Curves Above Odd Characteristic Fields
Over the field specifications the equation of the elliptic curve E can be reduced to the form:
Where Are constants satisfying .
The group of points of an elliptic curve E over a field called a lot of pairs lying on E , combined with the zero element :
It should be noted that in each nonzero element has either two square roots or none, so the points of the elliptic curve are divided into pairs of the form and .
Example
Consider an elliptic curve over the field . On this curve, in particular, lies the point , because .
Hasse Theorem
Hasse's elliptic curve theorem states that the number of points on an elliptic curve is close to the size of the final field:
which implies:
Elliptic curves over characteristic 2 fields
Over the field of characteristic 2, two types of elliptic curves are considered:
- Supersingular curve
- Nonsupersingular curve
A particular convenience of supersingular elliptic curves is that it is easy to calculate the order for them, while calculating the order of non-supersingular curves is difficult. Supersingular curves are especially convenient for creating a homemade ECC cryptosystem. To use them, you can do without the time-consuming procedure of calculating the order.
Projective coordinates
To calculate the sum of a pair of points on an elliptic curve requires not only several operations of addition and multiplication in , but also an inversion operation, i.e. for a given finding such , what which is one to two orders of magnitude slower than multiplication. Fortunately, points on an elliptic curve can be represented in various coordinate systems that do not require the use of inversion when adding points:
- in the projective coordinate system, every point represented by three coordinates which satisfy the relations:
- , .
- in the Jacobi coordinate system, the point is also represented by three coordinates with ratios: , .
- in the Lopez-Dahab coordinate system (洛佩斯 · 達哈卜 Chinese / Lopez-Dahab lat.), the following relation holds: , .
- 4 coordinates are used in the modified Jacobi coordinate system with the same ratios.
- 5 coordinates are used in the Chudnovsky-Jacobi coordinate system .
It is important to note that there may be various naming conventions - for example, IEEE P1363-2000 calls projective coordinates what are usually called Jacobi coordinates.
Elliptic Encryption / Decryption
The first task in this system is the encryption of the plaintext message to be forwarded as value (How?) For a point . Here is the point will represent encrypted text and will subsequently be decrypted. Please note that it is not possible to encode a message simply by coordinate or points, since not all such coordinates are in .
As in the case of a key exchange system, in the encryption, decryption system, the point is also considered and elliptic group . User selects a private key and generates a public key . To encrypt and send a message the user user selects a random positive integer and calculates ciphertext consisting of a pair of points
- . Wherein, - a pair of points.
Note that the side uses side public key : . To decrypt this ciphertext, multiplies the first point in a pair by a secret key and subtracts the result from the second point:
User disguised message by adding to it . No one except this user knows the value therefore therefore and is a public key, no one can remove the mask . However, the user includes in the message and a "hint", which will be enough to remove the mask to someone who has a private key . An adversary will have to figure out a message to recover according to and , which seems to be a difficult task [3] .
Arithmetic operations with points on an elliptic curve are not equivalent to these arithmetic operations with their coordinates.
The points of an elliptic curve over a finite field represent a group [4] . Multiplication is reduced to multiple doubling and summing.
For example, G + G ≠ 2G (these are different operations), 2G + 2 ^ 115G = 2 ^ 115G + 2G (summation is commutative);
2G = 2 * G; 4G = 2 * 2G; 8G = 2 * 4G; 16G = 2 * 8G, etc. (for two identical points, only the doubling operation);
25 * G; 25 = 11001 (in binary); 25 = 1 * 2 ^ 0 + 0 * 2 ^ 1 + 0 * 2 ^ 2 + 1 * 2 ^ 3 + 1 * 2 ^ 4 = 1 + 8 + 16; 25G = 16G + 8G + G = 1 * (2 ^ 4) G + 2 * (2 ^ 3) G + 1 * G (summation operation).
24G / 3G = 24G * (3G ^ -1 mod P); 5G - 3G = 5G + (3G ^ -1 mod P); where 3G ^ -1 mod P is modular multiplicative inverse.
Example
Consider the case , that corresponds to the curve
- and .
Suppose user going to send to user elliptic encoded message , and that user selects a random number . Public key is an . We have:
-
- .
User thus should send ciphertext .
Encryption Implementation
Specific implementations of encryption algorithms on an elliptic curve are described below. Here we consider the general principles of elliptical cryptography.
Parameter Set
To use elliptic cryptography, all participants must agree on all parameters defining the elliptic curve, i.e. cryptographic protocol parameter set. The elliptic curve is determined by the constants and from equation (2). The Abelian subgroup of points is cyclic and is defined by one generating point G. In this case, the cofactor , where n is the order of the point G , should be small ( preferably even )
So, for the field of characteristic 2, a set of parameters: , and for the final field where parameter set: .
There are several recommended parameter sets:
- NIST [5]
- SECG [6]
To create your own set of parameters, do the following.
- Select a set of parameters.
- Find an elliptic curve satisfying this set of parameters.
Two methods are used to find the curve for a given set of parameters.
- Select a random curve, then use the point counting algorithm [7] [8] .
- Select points, and then build a curve at these points using the technique of multiplication.
There are several classes of cryptographically “weak” curves that should be avoided:
- Curves over where Is not a prime number. The encryption on these curves is subject to Weil attacks .
- Curves with vulnerable to an attack that maps the points of a given curve to an additive field group .
Fast Reduction (NIST Curves)
The division modulo p (which is necessary for addition and multiplication) can be performed faster if p is a prime close to the power of 2. In particular, the prime Mersenne can be p . For example, a good choice is or . The National Institute of Standards and Technology (NIST) recommends using such prime numbers as p .
Another advantage of NIST recommended curves is the choice of value , which speeds up the addition operation in Jacobi coordinates.
NIST Recommended Elliptic Curves
NIST recommends 15 elliptic curves, many of which were obtained by Jerry Solinas (NSA) based on the findings of Neil Koblitz [9] . In particular, FIPS 186-3 [10] recommends 10 end fields. Some of them:
- fields where prime p has a length of 192, 224, 256, 384 or 521 [11] bits ,
- fields where m = 163, 233, 283, 409 or 571.
Moreover, for each final field, one elliptic curve is recommended. These end fields and elliptic curves are chosen, as is often mistakenly thought to be due to the high level of security. According to NIST, their choice was justified by the effectiveness of software implementation [12] . There are doubts about the safety of at least a few of them [13] [14] [15] .
Key Size
The fastest algorithms that solve the discrete logarithm problem on elliptic curves, such as the Shanks algorithm and the Pollard ρ-method , need operations. Therefore, the size of the field should be at least twice the size of the key. For example, for a 128-bit key, it is recommended to use an elliptical curve above the field where p has a length of 256 bits.
The most complex elliptic curve schemes that have been publicly hacked to date contain a 112-bit key for a finite simple field and a 109-bit key for a finite field of characteristic 2 . In July 2009, a cluster of more than two hundred Sony Playstation 3 found a 109-bit key in 3.5 months. The key over feature field 2 was found in April 2004, using 2,600 computers, for 17 months .
Diffie-Hellman Algorithm for Key Exchange
Suppose that subscribers A and B want to agree on a key that they will subsequently use in some classic cryptosystem. First of all, they openly choose a finite field and some elliptic curve over it. Their key is built at a random point on this elliptical curve. If they have a random point then, for example, her - coordinate gives a random element which can then be converted to -bit integer in -ary number system (where ), and this number can serve as a key in their classical cryptosystem. They have to pick a point. so that all their messages to each other are open and yet no one but the two of them would know anything about .
Subscribers (users) A and B first of all openly choose a point ∈ as a "basis"; plays the same role as forming in the Diffie-Hellman system for finite fields. However, we do not require that was a forming element in the group of curve points . This group may not be cyclic. Even if it is cyclic, we will not waste time checking that - a generating element (or even finding the total number N of points that we will not need in the future). We would like the subgroup B generated to be large, preferably of the same order of magnitude as . Assume for now that - taken open point on very large order (equal to either or a large divisor )
To form a key, randomly selects an integer at first comparable in order of magnitude with (which is close to ); he keeps this number a secret. He calculates ∈ and passes this point openly. Subscriber B does the same: he randomly chooses and openly conveys ∈ . Then the secret key they use is ∈ . Both users can calculate this key. For example, knows (the point was transmitted openly) and its own secret . However, any third party knows only and . In addition to solving the discrete logarithm problem - finding a by and (or finding by and ) there seems to be no way to find knowing only and [16] .
Diffie-Hellman Key Exchange Example
Take as an example
- , ,
which corresponds to the curve
- and .
It can be calculated that . User A's private key is , therefore, public key A will be
- .
User B's private key is , so member B’s public key will be
- .
The shared secret is
- .
Cryptography Security Using Elliptic Curves
- The security provided by the cryptographic approach based on elliptic curves depends on how difficult it is to solve the problem of determining according to and . This problem is usually called the logarithm problem on an elliptic curve. The fastest elliptic curve logarithm method known today is the so-called method of Pollard. The table (see below) compares the effectiveness of this method and the method of factorization using a sieve in the field of numbers of a general form. It can be seen that, compared to RSA, in the case of using cryptography methods on elliptic curves, approximately the same level of protection is achieved with significantly smaller key lengths.
Moreover, with equal key lengths, the computational effort required when using RSA and cryptography based on elliptic curves does not differ much. Thus, in comparison with RSA with equal protection levels, a clear computational advantage belongs to cryptography based on elliptic curves with a shorter key length [17] .
Table: Computational efforts required for cryptanalysis using elliptic curves and RSA
- Logarithm on an elliptic curve with Pollard method.
Key size | MIPS years |
---|---|
150 | 3.8 * 10 ^ 10 |
205 | 7.1 * 10 ^ 18 |
234 | 1.6 * 10 ^ 28 |
- Factorization in integers using the sieve method in a field of numbers of a general form.
Key size | MIPS years |
---|---|
512 | 3 * 10 ^ 4 |
768 | 3 * 10 ^ 2 |
1024 | 3 * 10 ^ 11 |
1280 | 3 * 10 ^ 14 |
1536 | 3 * 10 ^ 16 |
2048 | 3 * 10 ^ 20 |
Building an electronic digital signature using elliptic curves
ECDSA (Elliptic Curve Digital Signature Algorithm) has been adopted as ANSI X9F1 and IEEE P1363 .
Key Creation
- An elliptical curve is selected . The number of points on it should be divided by a large prime number n.
- Base point selected of order .
- Random number selected .
- Calculated .
- The private key is d, the public key is the tuple <a, b, G, n, Q>.
Signature Creation
- Random number selected .
- Calculated and .
- Condition checked , since otherwise the signature will not depend on the private key. Если r = 0, то выбирается другое случайное число k.
- Вычисляется .
- Вычисляется .
- Проверяется условие , так как в этом случае необходимого для проверки подписи числа не существует. Если s = 0, то выбирается другое случайное число k .
Подписью для сообщения М является пара чисел (r, s).
Проверка подписи
- Проверим, что числа r и s принадлежат диапазону чисел (1, n). В противном случае результат проверки отрицательный, и подпись отвергается.
- Вычислить и H(M).
- Вычислить and .
- Вычислить .
- Подпись верна в том и только том случае, когда v = r [18] .
Приложения
Большинство криптосистем современной криптографии естественным образом можно «переложить» на эллиптические кривые. Основная идея заключается в том, что известный алгоритм, используемый для конкретных конечных групп, переписывается для использования групп рациональных точек эллиптических кривых:
- алгоритм ECDSA основывающийся на ЭЦП ,
- алгоритм ECDH , основывающийся на алгоритме Диффи — Хеллмана ,
- алгоритм ECMQV , основывающийся на MQV , протоколе распределения ключей Менезеса-Кью-Венстоуна,
- ГОСТ Р 34.10-2012 ,
- факторизация Ленстры с помощью эллиптических кривых ,
- dual EC DRBG .
Необходимо отметить, что безопасность таких систем цифровой подписи опирается не только на криптостойкость алгоритмов шифрования, но и на криптостойкость используемых криптографических хеш-функций и генераторов случайных чисел .
По обзору 2013 года чаще всего используются кривые nistp256, nistp384, nistp521, secp256k1, secp384r1, secp521r1 [19] .
Notes
- ↑ Jeffrey Hoffstein, Jill Pipher, Joseph H. Silverman. An introduction to mathematical cryptography . — Springer, 2008. — 524 с. — (Undergraduate Texts in Mathematics). — ISBN 9780387779942 .
- ↑ Болотов А.А., Гашков С.Б., Фролов А.Б., Часовских А.А . Элементарное введение в эллиптическую криптографию. 11 с.
- ↑ Жданов О.Н., Золотарев В.В. Методы и средства криптографической защиты информации. 167 с.
- ↑ Эллиптическая криптография: теория . Дата обращения 13 октября 2016.
- ↑ Recommended Elliptic Curves for Government Use
- ↑ SEC 2: Recommended Elliptic Curve Domain Parameters
- ↑ Schoof's algorithm (inaccessible link)
- ↑ Schoof – Elkies – Atkin algorithm
- ↑ Neal Koblitz. Random Curves: Journeys of a Mathematician . - Springer, 2009 .-- S. 312-313. - 402 s. - ISBN 9783540740780 .
- ↑ FIPS 186-3 Archived on October 7, 2013. // NIST, 2009; deprecated in 2013 with the release of FIPS 186-4
- ↑ It may seem that a mistake has been made in this sequence. However, the last value is exactly 521, not 512 bits.
- ↑ Daniel J. Bernstein , Tanja Lange, Security dangers of the NIST curves // 2013.09.16: "Why did NIST choose these curves? * Most people we have asked: security * Actual NIST design document: eficiency" ( [1] )
- ↑ Daniel J. Bernstein and Tanja Lange. SafeCurves: choosing safe curves for elliptic-curve cryptography. (eng.) . safecurves.cr.yp.to (2013.11.18). Date of treatment December 20, 2013.
- ↑ Evgeny Zolotov . Snowden and the elliptical crypto: Bitcoin and TOR are beyond suspicion, but what about other projects? , Computerra (September 16, 2013). Date of treatment December 20, 2013.
- ↑ Dr Michael Scott, Backdoors in NIST elliptic curves Archived December 20, 2013 to Wayback Machine , Oct 24, 2013: "The curves themselves were suggested by Jerry Solinas who worked at the NSA."
- ↑ Chalkin T.A. Zhdanov O.N. The use of elliptic curves in cryptography.
- ↑ Zhdanov O.N., Zolotarev V.V. Methods and means of cryptographic information protection. 186 p.
- ↑ Ishmukhametov Sh.T. Methods of factorization of natural numbers. 99 p.
- ↑ Bos et al, Elliptic Curve Cryptography in Practice // MSR-TR-2013-119, November 2013
Links
- Bolotov A.A., Gashkov S.B., Frolov A.B., Chasovskikh A.A. Algorithmic basis of elliptic cryptography . - Moscow: MPEI, 2000 .-- 100 p.
- Bolotov A.A., Gashkov S.B., Frolov A.B., Chasovskikh A.A. An elementary introduction to elliptical cryptography. Algebraic and algorithmic foundations .. - Moscow: KomKniga, 2006. - 328 p.
- Zhdanov O.N., Zolotarev V.V. Methods and means of cryptographic information protection. - Krasnoyarsk: “The City”, 2007. - 217 p.
- Ishmukhametov Sh.T. Methods of factorization of natural numbers. - Kazan: KFU, 2011 .-- 190 p.
- Koblitz NA Course in number theory and cryptography .. - USA: Springer-Verlag, 1994 .-- 235 p.