The use of elliptic curves in cryptography was independently proposed by Neal Koblitz and Victor Miller in 1985.
in general, an elliptic curve can be expressed by the following equation, where a, b, c and d are coefficients.
For example, when a = 1, b = , c =-2 and d = 4, the obtained elliptic curve is:
The image of the elliptic curve E is shown in Figure X-1, and it can be seen that it is not an ellipse at all.
Draw a straight line from two points A and B on the curve, and find the intersection point between the straight line and the elliptic curve. The point of the intersection point about the axis symmetry position of X is defined as A+B, which is the addition. As shown in the following figure: A+B = C
The above method cannot explain A+A, that is, the situation where two points coincide. Therefore, in this case, the tangent of the elliptic curve at point A, the intersection point with the elliptic curve, and the point where the intersection point is symmetrical with respect to X are defined as A+A, that is, 2A, which is the double operation.
the point where a is symmetrical about x axis is defined as -A, that is, the negative and positive operation of elliptic curve. As shown in the following figure:
If a and -A are added, and the straight line passing through a and -A is parallel to the Y axis, it can be considered that the straight line intersects the elliptic curve at infinity.
to sum up, the operations of A+B and 2A are defined, so given a certain point g of an elliptic curve, 2G, 3G (G+2G), 4G ... That is, when the G point is given and X is known, it is not difficult to find xG point. On the contrary, it is very difficult to find x when xG point is known. This is the mathematical principle behind elliptic curve encryption algorithm.
to form a smooth curve, an elliptic curve requires that the values of x and y are both real numbers, that is, an elliptic curve in the real number field. However, the elliptic curve encryption algorithm uses finite fields instead of real fields. According to the definition of number theory, finite field GF(p) refers to the operations of addition, subtraction, multiplication and division defined in an integer set consisting of , 1, 2 ... p-1 * * * p elements given a certain prime number p.
suppose the elliptic curve is y? = x? +x+1, when it is over the finite field GF(23), write: y? ≡ x? +x+1 (mod 23)
At this time, the elliptic curve is no longer a smooth curve, but some discontinuous points, as shown in the following figure. Take point (1,7) as an example, 7? ≡ 1? + 1 + 1 ≡ 3 (mod 23)。 So there are the following points:
(,1) (,22) (1,7) (1,16) (3,1) (3,13) (4,) (5,4) (5,19) (6,4) (6,19.
in addition, if P(x,y) is a point on the elliptic curve, then -P means (x,-y) is also a point on the elliptic curve. For example, point P(,1),-p = (,1) = (,22) is also a point on the elliptic curve.
the related formula is as follows: elliptic curve y on finite field GF(p)? = x? +ax+b, if P(Xp, Yp), Q(Xq, Yq), and P≠-Q, then R(Xr,Yr) = P+Q is determined by the following rules:
Xr = (λ? -XP-xq) mod pyr = (λ (XP-xr)-yp) mod p where λ = (Yq-Yp)/(Xq-Xp) mod p (if P≠Q), λ = (3Xp? +a)/2Yp mod p (if P=Q)
Therefore, the elliptic curve y over the finite field GF(23)? ≡ x? +x+1 (mod 23), assuming (,1) as the G point, calculate 2G, 3G, 4G...xG, etc., as follows:
Calculate 2g: λ = (3x? + 1)/2x1 mod 23 = (1/2) mod 23 = 12 Xr = (12? --) mod23 = 6yr = (12 (-6)-1) mod23 = 19, that is, 2G is the point (6,19)
Calculate 3g: 3g = g+2g, that is, (,1)+(6,19) λ = (19-. --6) mod 23 = 3yr = (3 (-3)-1) mod 23 = 13, that is, 3G is the point (3, 13)
To establish an encryption mechanism based on elliptic curves, it is necessary to find such problems as RSA prime factorization or other discrete logarithm. It is very difficult to find x from the known g and xG on the elliptic curve, which is the discrete logarithm problem on the elliptic curve. Here x is the private key and xG is the public key.
The principle of elliptic curve encryption algorithm is as follows:
Let the private key and public key be k and k respectively, that is, K = kG, where g is the G point.
public key encryption: select a random number r to generate a ciphertext c from the message m, which is a point pair, that is, C = {rG, M+rK}, where k is the public key
private key decryption: M+rK-k(rG) = M+r(kG)-k(rG) = M where k and k are respectively.
elliptic curve signature algorithm, namely ECDSA. Let the private key and public key be k and k respectively, that is, K = kG, where g is the G point.
private key signature: 1. select random number r and calculate point rG(x, y). 2. According to the random number R, the hash H of the message M and the private key K, calculate S = (h+kx)/R. 3. Send the message m and the signature {rG, s} to the receiver.
signature of public key verification: 1. The receiver receives the message M and the signature {rG=(x,y), s}. 2. Find the hash h according to the message. 3. Use the sender's public key K to calculate: hG/s+xK/s, and compare it with rG. If it is equal, the verification is successful.
the principle is as follows: Hg/s+xk/s = Hg/s+x (kg)/s = (h+xk) g/s = r (h+xk) g/(h+kx) = rg
suppose the message to be signed is a string: "Hello World!" . The first step of DSA signature is to generate a message digest for the message to be signed. Different signature algorithms use different message digest algorithms. And ECDSA256 uses SHA256 to generate a 256-bit digest.
after the abstract is generated, the abstract is signed by using a signature algorithm:
a random number k is generated
two large numbers r and s are calculated by using the random number k. Putting r and s together constitutes the signature of the message digest.
it should be noted here that because of the existence of random number k, for the same message, the signatures generated by using the same algorithm are different. From the function point of view, signature function will produce different outputs for the same input. Because random values will be mixed into the signature process inside the function.
regarding the verification process, we will not discuss its algorithm details here. From a macro point of view, the receiver of the message separates R and S from the signature, and then calculates R by using the public key information and S. If the calculated r is the same as the received r value, the verification is successful. Otherwise, it means that the verification failed.