Elliptical cryptography

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. $(x,y)$ ${\ displaystyle (x, y)}$ $(x,y)$ satisfying the equation:

y^{2}+a_{1}xy+a_{3}y=x^{3}+a_{2}x^{2}+a_{4}x+a_{6}

{\ displaystyle y ^ {2} + a_ {1} xy + a_ {3} y = x ^ {3} + a_ {2} x ^ {2} + a_ {4} x + a_ {6}}

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 ( $\mathbb {Z} _{p}$ ${\ displaystyle \ mathbb {Z} _ {p}}$ where $p>3$ ${\ displaystyle p> 3}$ Is a prime number) and fields of characteristic 2 ( $GF(2^{m})$ ${\ displaystyle GF (2 ^ {m})}$ )

Elliptic Curves Above Odd Characteristic Fields

Over the field $\mathbb {Z} _{p}$ ${\ displaystyle \ mathbb {Z} _ {p}}$ specifications $p>3$ ${\ displaystyle p> 3}$ the equation of the elliptic curve E can be reduced to the form:

E:\quad y^{2}=x^{3}+Ax+B{\pmod {p}},

{\ displaystyle E: \ quad y ^ {2} = x ^ {3} + Ax + B {\ pmod {p}},}

Where $A,B\in \mathbb {Z} _{p}$ ${\ displaystyle A, B \ in \ mathbb {Z} _ {p}}$ Are constants satisfying $4A^{3}+27B^{2}\not \equiv 0{\pmod {p}}$ ${\ displaystyle 4A ^ {3} + 27B ^ {2} \ not \ equiv 0 {\ pmod {p}}}$ .

The group of points of an elliptic curve E over a field $\mathbb {Z} _{p}$ ${\ displaystyle \ mathbb {Z} _ {p}}$ called a lot of pairs $(x,y)$ ${\ displaystyle (x, y)}$ lying on E , combined with the zero element ${\mathcal {O}}$ ${\ displaystyle {\ mathcal {O}}}$ :

E(\mathbb {Z} _{p})={\mathcal {O}}\cup \left\{(x,y)\in \mathbb {Z} _{p}\times \mathbb {Z} _{p}|y^{2}\equiv x^{3}+Ax+B{\pmod {p}}\right\}.

{\ displaystyle E (\ mathbb {Z} _ {p}) = {\ mathcal {O}} \ cup \ left \ {(x, y) \ in \ mathbb {Z} _ {p} \ times \ mathbb { Z} _ {p} | y ^ {2} \ equiv x ^ {3} + Ax + B {\ pmod {p}} \ right \}.}

It should be noted that in $\mathbb {Z} _{p}$ ${\ displaystyle \ mathbb {Z} _ {p}}$ each nonzero element has either two square roots or none, so the points of the elliptic curve are divided into pairs of the form $(x,y)$ ${\ displaystyle (x, y)}$ and $(x,-y)$ ${\ displaystyle (x, -y)}$ .

Example

Consider an elliptic curve $y^{2}=x^{3}+3x+2$ ${\ displaystyle y ^ {2} = x ^ {3} + 3x + 2}$ over the field $\mathbb {Z} _{5}$ ${\ displaystyle \ mathbb {Z} _ {5}}$ . On this curve, in particular, lies the point $(1,1)$ ${\ displaystyle (1,1)}$ , because $1^{2}\equiv 1^{3}+3\cdot 1+2{\pmod {5}}$ ${\ displaystyle 1 ^ {2} \ equiv 1 ^ {3} +3 \ cdot 1 + 2 {\ pmod {5}}}$ .

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:

({\sqrt {p}}-1)^{2}\leqslant |E(\mathbb {Z} _{p})|\leqslant ({\sqrt {p}}+1)^{2},

{\ displaystyle ({\ sqrt {p}} - 1) ^ {2} \ leqslant | E (\ mathbb {Z} _ {p}) | \ leqslant ({\ sqrt {p}} + 1) ^ {2 },}

which implies:

\left||E(\mathbb {Z} _{p})|-p\right|<2{\sqrt {p}}+1.

{\ displaystyle \ left || E (\ mathbb {Z} _ {p}) | -p \ right | <2 {\ sqrt {p}} + 1.}

Elliptic curves over characteristic 2 fields

Over the field of characteristic 2, two types of elliptic curves are considered:

Supersingular curve
$y^{2}+ay=x^{3}+bx+c$ ${\ displaystyle y ^ {2} + ay = x ^ {3} + bx + c}$
Nonsupersingular curve
$y^{2}+axy=x^{3}+bx^{2}+c$ ${\ displaystyle y ^ {2} + axy = x ^ {3} + bx ^ {2} + c}$

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 $\mathbb {F} _{q}$ ${\ displaystyle \ mathbb {F} _ {q}}$ , but also an inversion operation, i.e. for a given $x\in \mathbb {F} _{q}$ ${\ displaystyle x \ in \ mathbb {F} _ {q}}$ finding such $y\in \mathbb {F} _{q}$ ${\ displaystyle y \ in \ mathbb {F} _ {q}}$ , what $xy=1$ ${\ displaystyle xy = 1}$ 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 $(x,y)$ ${\ displaystyle (x, y)}$ represented by three coordinates $(X,Y,Z)$ ${\ displaystyle (X, Y, Z)}$ which satisfy the relations:
$x={\frac {X}{Z}}$ ${\ displaystyle x = {\ frac {X} {Z}}}$ , $y={\frac {Y}{Z}}$ ${\ displaystyle y = {\ frac {Y} {Z}}}$ .
in the Jacobi coordinate system, the point is also represented by three coordinates $(X,Y,Z)$ ${\ displaystyle (X, Y, Z)}$ with ratios: $x={\frac {X}{Z^{2}}}$ ${\ displaystyle x = {\ frac {X} {Z ^ {2}}}}$ , $y={\frac {Y}{Z^{3}}}$ ${\ displaystyle y = {\ frac {Y} {Z ^ {3}}}}$ .
in the Lopez-Dahab coordinate system (洛佩斯 · 達哈卜 Chinese / Lopez-Dahab lat.), the following relation holds: $x={\frac {X}{Z}}$ ${\ displaystyle x = {\ frac {X} {Z}}}$ , $y={\frac {Y}{Z^{2}}}$ ${\ displaystyle y = {\ frac {Y} {Z ^ {2}}}}$ .
4 coordinates are used in the modified Jacobi coordinate system $(X,Y,Z,aZ^{4})$ ${\ displaystyle (X, Y, Z, aZ ^ {4})}$ with the same ratios.
5 coordinates are used in the Chudnovsky-Jacobi coordinate system $(X,Y,Z,Z^{2},Z^{3})$ ${\ displaystyle (X, Y, Z, Z ^ {2}, Z ^ {3})}$ .

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 $m$ ${\ displaystyle m}$ to be forwarded as value $x-y$ ${\ displaystyle xy}$ (How?) For a point $P_{m}$ ${\ displaystyle P_ {m}}$ . Here is the point $P_{m}$ ${\ displaystyle P_ {m}}$ will represent encrypted text and will subsequently be decrypted. Please note that it is not possible to encode a message simply by coordinate $x$ ${\ displaystyle x}$ or $y$ ${\ displaystyle y}$ points, since not all such coordinates are in $E_{p}(a,b)$ ${\ displaystyle E_ {p} (a, b)}$ .
As in the case of a key exchange system, in the encryption, decryption system, the point is also considered $G$ ${\ displaystyle G}$ and elliptic group $E_{p}(a,b)$ ${\ displaystyle E_ {p} (a, b)}$ . User $A$ ${\ displaystyle A}$ selects a private key $n_{A}$ ${\ displaystyle n_ {A}}$ and generates a public key $P_{A}=n_{A}G$ ${\ displaystyle P_ {A} = n_ {A} G}$ . To encrypt and send a message $P_{m}$ ${\ displaystyle P_ {m}}$ the user $B$ ${\ displaystyle B}$ user $A$ ${\ displaystyle A}$ selects a random positive integer $k$ ${\ displaystyle k}$ and calculates ciphertext $G_{m}$ ${\ displaystyle G_ {m}}$ consisting of a pair of points

G_{m}=(kG,P_{m}+kP_{B})

{\ displaystyle G_ {m} = (kG, P_ {m} + kP_ {B})}

. Wherein,

G_{m}\neq P_{m},G_{m}

{\ displaystyle G_ {m} \ neq P_ {m}, G_ {m}}

- a pair of points.

Note that the side $A$ ${\ displaystyle A}$ uses side public key $B$ ${\ displaystyle B}$ : $P_{B}$ ${\ displaystyle P_ {B}}$ . To decrypt this ciphertext, $B$ ${\ displaystyle B}$ multiplies the first point in a pair by a secret key $n_{B}$ ${\ displaystyle n_ {B}}$ and subtracts the result from the second point:
$(P_{m}+kP_{B})-n_{B}(kG)=P_{m}+k(n_{B}G)-n_{B}(kG)=P_{m}+{\cancel {kn_{B}(G)}}-{\cancel {kn_{B}(G)}}=P_{m}$ ${\ displaystyle (P_ {m} + kP_ {B}) - n_ {B} (kG) = P_ {m} + k (n_ {B} G) -n_ {B} (kG) = P_ {m} + {\ cancel {kn_ {B} (G)}} - {\ cancel {kn_ {B} (G)}} = P_ {m}}$

User $A$ ${\ displaystyle A}$ disguised message $P_{m}$ ${\ displaystyle P_ {m}}$ by adding to it $kP_{B}$ ${\ displaystyle kP_ {B}}$ . No one except this user knows the value $k$ ${\ displaystyle k}$ therefore therefore $P_{B}$ ${\ displaystyle P_ {B}}$ and is a public key, no one can remove the mask $kP_{B}$ ${\ displaystyle kP_ {B}}$ . However, the user $A$ ${\ displaystyle A}$ includes in the message and a "hint", which will be enough to remove the mask to someone who has a private key $n_{B}$ ${\ displaystyle n_ {B}}$ . An adversary will have to figure out a message to recover $k$ ${\ displaystyle k}$ according to $G$ ${\ displaystyle G}$ and $k G$ ${\ displaystyle kG}$ , 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 $p=751$ ${\ displaystyle p = 751}$ , $E_{p}(-1,188)$ ${\ displaystyle E_ {p} (- 1,188)}$ that corresponds to the curve

y^{2}=x^{3}-x+188

{\ displaystyle y ^ {2} = x ^ {3} -x + 188}

and

G=(0,376)

{\ displaystyle G = (0,376)}

.

Suppose user $A$ ${\ displaystyle A}$ going to send to user $B$ ${\ displaystyle B}$ elliptic encoded message $P_{m}=(562,201)$ ${\ displaystyle P_ {m} = (562,201)}$ , and that user $A$ ${\ displaystyle A}$ selects a random number $k=386$ ${\ displaystyle k = 386}$ . Public key $B$ ${\ displaystyle B}$ is an $P_{B}=(201,5)$ ${\ displaystyle P_ {B} = (201.5)}$ . We have:

386(0,376)=(676,558)

{\ displaystyle 386 (0,376) = (676,558)}

(562,201)+386(201,5)=(385,328)

{\ displaystyle (562,201) +386 (201,5) = (385,328)}

.

User thus $A$ ${\ displaystyle A}$ should send ciphertext $(676,558),(385,328)$ ${\ displaystyle (676,558), (385,328)}$ .

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 $a$ ${\ displaystyle a}$ and $b$ ${\ displaystyle b}$ from equation (2). The Abelian subgroup of points is cyclic and is defined by one generating point G. In this case, the cofactor $h={\frac {|E|}{n}}$ ${\ displaystyle h = {\ frac {| E |} {n}}}$ , where n is the order of the point G , should be small ( $h\leq 4$ ${\ displaystyle h \ leq 4}$ preferably even $h=1$ ${\ displaystyle h = 1}$ )

So, for the field of characteristic 2, a set of parameters: $(m,f,a,b,G,n,h)$ ${\ displaystyle (m, f, a, b, G, n, h)}$ , and for the final field $\mathbb {Z} _{p}$ ${\ displaystyle \ mathbb {Z} _ {p}}$ where $p>3$ ${\ displaystyle p> 3}$ parameter set: $(p,a,b,G,n,h)$ ${\ displaystyle (p, a, b, G, n, h)}$ .

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 $\mathbb {F} _{2^{m}}$ ${\ displaystyle \ mathbb {F} _ {2 ^ {m}}}$ where $m$ ${\ displaystyle m}$ Is not a prime number. The encryption on these curves is subject to Weil attacks .
Curves with $|E(\mathbb {F} _{q})|=q$ ${\ displaystyle | E (\ mathbb {F} _ {q}) | = q}$ vulnerable to an attack that maps the points of a given curve to an additive field group $\mathbb {F} _{q}$ ${\ displaystyle \ mathbb {F} _ {q}}$ .

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 $p=2^{251}-1$ ${\ displaystyle p = 2 ^ {251} -1}$ or $p=2^{256}-2^{32}-2^{9}-2^{8}-2^{7}-2^{6}-2^{4}-1$ ${\ displaystyle p = 2 ^ {256} -2 ^ {32} -2 ^ {9} -2 ^ {8} -2 ^ {7} -2 ^ {6} -2 ^ {4} -1}$ . 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 $a=-3$ ${\ displaystyle a = -3}$ , 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 $\mathbb {F} _{p}$ ${\ displaystyle \ mathbb {F} _ {p}}$ where prime p has a length of 192, 224, 256, 384 or 521 ^[11] bits ,
fields $\mathbb {F} _{2^{m}}$ ${\ displaystyle \ mathbb {F} _ {2 ^ {m}}}$ 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 $O({\sqrt {n}})$ ${\ displaystyle O ({\ sqrt {n}})}$ 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 $\mathbb {F} _{p}$ ${\ displaystyle \ mathbb {F} _ {p}}$ 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 $F_{q}$ ${\ displaystyle F_ {q}}$ and some elliptic curve $E$ ${\ displaystyle E}$ over it. Their key is built at a random point $P$ ${\ displaystyle P}$ on this elliptical curve. If they have a random point $P$ ${\ displaystyle P}$ then, for example, her $x$ ${\ displaystyle x}$ - coordinate gives a random element $F_{q}$ ${\ displaystyle F_ {q}}$ which can then be converted to $r$ ${\ displaystyle r}$ -bit integer in $p$ ${\ displaystyle p}$ -ary number system (where $rq=p$ ${\ displaystyle rq = p}$ ), and this number can serve as a key in their classical cryptosystem. They have to pick a point. $P$ ${\ displaystyle P}$ so that all their messages to each other are open and yet no one but the two of them would know anything about $P$ ${\ displaystyle P}$ .

Subscribers (users) A and B first of all openly choose a point $B$ ${\ displaystyle B}$ ∈ $E$ ${\ displaystyle E}$ as a "basis"; $B$ ${\ displaystyle B}$ plays the same role as forming $q$ ${\ displaystyle q}$ in the Diffie-Hellman system for finite fields. However, we do not require that $B$ ${\ displaystyle B}$ was a forming element in the group of curve points $E$ ${\ displaystyle E}$ . This group may not be cyclic. Even if it is cyclic, we will not waste time checking that $B$ ${\ displaystyle B}$ - 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 $E$ ${\ displaystyle E}$ . Assume for now that $B$ ${\ displaystyle B}$ - taken open point on $E$ ${\ displaystyle E}$ very large order (equal to either $N$ ${\ displaystyle N}$ or a large divisor $N$ ${\ displaystyle N}$ )

To form a key, $A$ ${\ displaystyle A}$ randomly selects an integer at first $a$ ${\ displaystyle a}$ comparable in order of magnitude with $q$ ${\ displaystyle q}$ (which is close to $N$ ${\ displaystyle N}$ ); he keeps this number a secret. He calculates $a B$ ${\ displaystyle aB}$ ∈ $E$ ${\ displaystyle E}$ and passes this point openly. Subscriber B does the same: he randomly chooses $b$ ${\ displaystyle b}$ and openly conveys $b B$ ${\ displaystyle bB}$ ∈ $E$ ${\ displaystyle E}$ . Then the secret key they use is $P=abB$ ${\ displaystyle P = abB}$ ∈ $E$ ${\ displaystyle E}$ . Both users can calculate this key. For example, $A$ ${\ displaystyle A}$ knows $b B$ ${\ displaystyle bB}$ (the point was transmitted openly) and its own secret $a$ ${\ displaystyle a}$ . However, any third party knows only $a B$ ${\ displaystyle aB}$ and $b B$ ${\ displaystyle bB}$ . In addition to solving the discrete logarithm problem - finding a by $B$ ${\ displaystyle B}$ and $a B$ ${\ displaystyle aB}$ (or finding $b$ ${\ displaystyle b}$ by $B$ ${\ displaystyle B}$ and $b B$ ${\ displaystyle bB}$ ) there seems to be no way to find $a b B$ ${\ displaystyle abB}$ knowing only $a B$ ${\ displaystyle aB}$ and $b B$ ${\ displaystyle bB}$ ^[16] .

Diffie-Hellman Key Exchange Example

Take as an example

p=211

{\ displaystyle p = 211}

,

E_{p}(0,-4)

{\ displaystyle E_ {p} (0, -4)}

,

which corresponds to the curve

y^{2}=x^{3}-4

{\ displaystyle y ^ {2} = x ^ {3} -4}

and

G=(2,2)

{\ displaystyle G = (2,2)}

.

It can be calculated that $241G=$ ${\ displaystyle 241G =}$ ${\mathcal {O}}$ ${\ displaystyle {\ mathcal {O}}}$ . User A's private key is $n_{A}=121$ ${\ displaystyle n_ {A} = 121}$ , therefore, public key A will be

P_{A}=121(2,2)=(115,48)

{\ displaystyle P_ {A} = 121 (2,2) = (115,48)}

.

User B's private key is $n_{B}=203$ ${\ displaystyle n_ {B} = 203}$ , so member B’s public key will be

203(2,2)=(130,203)

{\ displaystyle 203 (2,2) = (130,203)}

.

The shared secret is

121(130,203)=203(115,48)=(161,69)

{\ displaystyle 121 (130,203) = 203 (115,48) = (161,69)}

.

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 $k$ ${\ displaystyle k}$ according to $k P$ ${\ displaystyle kP}$ and $P$ ${\ displaystyle P}$ . This problem is usually called the logarithm problem on an elliptic curve. The fastest elliptic curve logarithm method known today is the so-called $p$ ${\ displaystyle p}$ 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 $p$ ${\ displaystyle p}$ 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 $E_{p}(a,b)$ ${\ displaystyle E_ {p} (a, b)}$ . The number of points on it should be divided by a large prime number n.
Base point selected $G\in E_{p}(a,b)$ ${\ displaystyle G \ in E_ {p} (a, b)}$ of order $n,n\cdot G=\infty$ ${\ displaystyle n, n \ cdot G = \ infty}$ .
Random number selected $d\in (1,n)$ ${\ displaystyle d \ in (1, n)}$ .
Calculated $Q=d\cdot G$ ${\ displaystyle Q = d \ cdot G}$ .
The private key is d, the public key is the tuple <a, b, G, n, Q>.

Signature Creation

Random number selected $k\in (1,n)$ ${\ displaystyle k \ in (1, n)}$ .
Calculated $k\cdot G=(x_{1},y_{1})$ ${\ displaystyle k \ cdot G = (x_ {1}, y_ {1})}$ and $r=x_{1}(\operatorname {mod} n)$ ${\ displaystyle r = x_ {1} (\ operatorname {mod} n)}$ .
Condition checked $r\neq 0$ ${\ displaystyle r \ neq 0}$ , since otherwise the signature will not depend on the private key. Если r = 0, то выбирается другое случайное число k.
Вычисляется $k^{-1}(\operatorname {mod} n)$ $k^{-1}(\operatorname {mod} n)$ .
Вычисляется $s=k^{-1}\cdot (H(M)+dr)(\operatorname {mod} n)$ $s=k^{-1}\cdot (H(M)+dr)(\operatorname {mod} n)$ .
Проверяется условие $s\neq 0$ $s\neq 0$ , так как в этом случае необходимого для проверки подписи числа $s^{-1}(\operatorname {mod} n)$ $s^{-1}(\operatorname {mod} n)$ не существует. Если s = 0, то выбирается другое случайное число k .

Подписью для сообщения М является пара чисел (r, s).

Проверка подписи

Проверим, что числа r и s принадлежат диапазону чисел (1, n). В противном случае результат проверки отрицательный, и подпись отвергается.
Вычислить $w=s^{-1}(\operatorname {mod} n)$ $w=s^{-1}(\operatorname {mod} n)$ и H(M).
Вычислить $u_{1}=H(M)w(\operatorname {mod} n)$ $u_{1}=H(M)w(\operatorname {mod} n)$ and $u_{2}=rw(\operatorname {mod} n)$ $u_{2}=rw(\operatorname {mod} n)$ .
Вычислить $u_{1}G+u_{2}Q=(x_{0},y_{0}),v=x_{0}(\operatorname {mod} n)$ $u_{1}G+u_{2}Q=(x_{0},y_{0}),v=x_{0}(\operatorname {mod} n)$ .
Подпись верна в том и только том случае, когда 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.

[1] Jeffrey Hoffstein, Jill Pipher, Joseph H. Silverman. An introduction to mathematical cryptography . — Springer, 2008. — 524 с. — (Undergraduate Texts in Mathematics). — ISBN 9780387779942 .

[2] Болотов А.А., Гашков С.Б., Фролов А.Б., Часовских А.А . Элементарное введение в эллиптическую криптографию. 11 с.

[3] Жданов О.Н., Золотарев В.В. Методы и средства криптографической защиты информации. 167 с.

[4] Эллиптическая криптография: теория . Дата обращения 13 октября 2016.

[5] Recommended Elliptic Curves for Government Use

[6] SEC 2: Recommended Elliptic Curve Domain Parameters

[7] Schoof's algorithm (inaccessible link)

[8] Schoof – Elkies – Atkin algorithm

[9] Neal Koblitz. Random Curves: Journeys of a Mathematician . - Springer, 2009 .-- S. 312-313. - 402 s. - ISBN 9783540740780 .

[10] FIPS 186-3 Archived on October 7, 2013. // NIST, 2009; deprecated in 2013 with the release of FIPS 186-4

[11] It may seem that a mistake has been made in this sequence. However, the last value is exactly 521, not 512 bits.

[12] 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] )

[13] 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.

[14] 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.

[15] 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."

[16] Chalkin T.A. Zhdanov O.N. The use of elliptic curves in cryptography.

[17] Zhdanov O.N., Zolotarev V.V. Methods and means of cryptographic information protection. 186 p.

[18] Ishmukhametov Sh.T. Methods of factorization of natural numbers. 99 p.

[19] Bos et al, Elliptic Curve Cryptography in Practice // MSR-TR-2013-119, November 2013

Elliptical cryptography

Introduction

Elliptic Curves Above Finite Fields

Elliptic Curves Above Odd Characteristic Fields

Example

Hasse Theorem

Elliptic curves over characteristic 2 fields

Projective coordinates

Elliptic Encryption / Decryption

Example

Encryption Implementation

Parameter Set

Fast Reduction (NIST Curves)

NIST Recommended Elliptic Curves

Key Size

Diffie-Hellman Algorithm for Key Exchange

Diffie-Hellman Key Exchange Example

Cryptography Security Using Elliptic Curves

Building an electronic digital signature using elliptic curves

Key Creation

Signature Creation

Проверка подписи

Приложения

Notes

Links

More articles: