In today's world there are a lot of disputes about the transition to a new, modernized elliptic curve encryption system. But is it necessary? And do we need to be afraid of the fact that if we do not change all our algorithms immediately - all the computers of the world would be hacked? After all, we have used the same RSA for many years and nothing bad happened. In this matter, I decided to find out and tell you about the working scheme of the elliptic curve cryptography!
This post is continuation of the previous one where I introduced readers to the basics of cryptography.
Let’s start with the theory and realize what all of these curves are like and how to use them.
Elliptic curve - a set of points, described by the Weierstrass equation:
Typical variants of elliptic curves graphs (all curves are smooth except one - with arguments (0,0) – it is singular):
Elliptic curves are smooth, if the following inequality:
At the same time, this condition is not satisfied for singular curves.
Remember: You can’t use the singular curve in such an algorithm.
Arithmetic operations in elliptic curve cryptography are made with the points over the curve. The basic operation is "addition".
Addition of two points could be easily represented graphically:
As it can be seen from the figure, for the addition of points p1 and p2, it is necessary to draw a straight line between them, which crosses the curve in a third point p3. Let’s reflect p3 point relative to the horizontal axis and we’ll get the required point p4 (p1 + p2).
All curves discussed above relate to the elliptic curves over the real numbers. And that brings us to the issue of rounding. Using the curves over the real numbers, we will not get a bijection between the original text and encrypted data. In order not to bother with rounding only curves over finite fields are used in cryptography.
In cryptography, there are two types of elliptic curves: over finite fields - the ring of residues modulo a prime number and over a binary finite field.
Elliptic curves over the field have got one important advantage - elements of the field can be easily represented in the form of n-bit code words, it allows you to increase the speed of the hardware implementation of elliptic algorithms.
Curves of such form used over the binary finite field in order to avoid singularity:
And now let’s go to the algorithm of the digital signature:
Creating of keys:
- Select an elliptic curve Ep (a, b). The number of points on it must be divisible by a large integer n.
- Choose a point.
- Select a random number.
- Calculate Q = d x P.
- The private key is d, the public key - (E, P, n, Q).
Formation of signatures
To generate a digital signature a large number d is used – it is a permanent secret key of the scheme; it should be known only by the signer.
To calculate the signature of message M there should be done the following steps:
- Calculate hash of message M: H = h (M), using the hash function of Stribog;
- Calculate the integer α, which binary representation is H;
- Define e = α mod n, if e = 0, e = 1;
- Generate a random number k, satisfying 0 <k <n;
- Calculate a point of an elliptic curve C = k * G;
- Define r = xC mod n, where xC - x-coordinate of the point C. If r = 0, then go back to step 4;
- Calculate the value s = (rd + ke) mod n. If s = 0, then return to Step 4;
- Return r || s value as a digital signature.
Signature verification
To verify the signature Q point is used, which satisfies the equation Q = d * G. The point Q is a public-key of the scheme and can be known by any reviewer.
The signature verification process is done according to the following algorithm:
- According to the received signatures restore the number r and s. If you do not have the inequalities 0 <r <n and 0 <s <n, then return "the signature is not valid";
- Calculate hash of message M: H = h (M);
- Calculate the integer α, which binary representation is H;
- Define e = α mod n, if e = 0, e = 1;
- Calculate v = e-1 mod n;
- Calculate the value z1 = s * v mod n and z2 = -r * v mod n;
- Calculate a point of an elliptic curve C = z1 * G + z2 * Q;
- Define R = xc mod n, where xc - x-coordinate of the point C;
- If R = r, then the signature is valid. Otherwise, a signature is not accepted.
Encryption / decryption using the elliptic curve
Let’s look at the simplest approach to encryption / decryption using the elliptic curve. The aim is to encrypt the message M, which may be represented as a point on an elliptic curve Pm (x, y).
In the encryption / decryption elliptic curve system Ep (a, b) and a point G on it are considered as parameters. User B selects the private key nB and calculates the public key PB = nB x G. To encrypt a message Pm the public key of the recipient B PB is used. User A selects a random positive integer k and computes an encrypted message Cm, which is a point on an elliptic curve.
Cm = {k x G, Pm + k x PB}
To decrypt a message, a participant B multiplies the first coordinate of a point on his own private key and subtracts the result from the second coordinate:
Pm + k x PB - nB x (k x G) = Pm + k x (nB x G) - nB x (k x G) = Pm
A participant encrypted message Pm by adding kxPB to it. No one knows the value of k, and so, even the PB is a public key, no one knows k x PB. The enemy would have to calculate k to restore the message. It will not be easy.
The recipient also doesn’t know the k, but k x G is sent to him as a hint. Multiplying k x G to a private key, the recipient receives the value that was added by the sender to the unencrypted message. Thus, the recipient, not knowing the k, but having his private key can recover the unencrypted message.
Based on all said above, I want to name the main advantages and disadvantages of elliptic curve cryptography:
The main advantages:
- Much smaller length of the key that the "classical" asymmetric cryptography has got.
- The speed of the elliptic algorithms is much higher than the classic methods have.
- Due to the small length of a key and of high-speed asymmetric cryptographic algorithms based on elliptic curve can be used in smart cards and other devices with limited computing resources.
The main disadvantages of elliptic curve cryptography:
- All advantages of elliptic curve cryptography are derived from one particular fact: there are no subexponential algorithms for solving the discrete logarithm problem based on the elliptic curve. This reduces the length of the key increases productivity. However, if there will be such algorithms, it will mean the collapse of the elliptic curve cryptography.
- Elliptic curve cryptography - is very difficult – it has got a huge number of subtleties that must be taken into account. From the selection of the elliptic curve and ending with key generation. When there will be a mass transition to elliptic curve cryptography there will be a lot of errors and vulnerabilities that have already been coped with in the more conventional methods.
Follow me, if you are a geek or want to learn more about technologies and scientific/educational topics
