Foreword
Like RSA (Ron Rivest, ADI Shamir, Len Adleman's name), ECC (Elliptic Curves Cryptography, Elliptic Code Coding) also belongs to the public key algorithm. At present, there are not many public literatures of ECC in China (anyway I have not found anyway). There are some introductions, and it is also a general, still understanding the essence of ECC after reading (maybe I understand too much). A few days ago I found some materials from the foreign website. After reading it, I seem to understand it. So I want to put me aware of ECC, share it with you. Of course, the ECC is profound, my understanding is still very beautiful, there is a lot of mistakes in the article, welcome all the masters to criticize, the younger brother, I am listening, and correct it in time. The article will use a serial way, I will write it a little bit. This paper mainly focuses on theory, and the code implementation is not involved. This requires you have a little mathematical skill. It is best to understand the RSA algorithm and have a understanding of the public key algorithm. The book "of the" Number of Recent Basics "" primary diameter ", it is best to turn it first, this is helpful to understand this article. Don't be afraid, I try to pay the language, I hope this article can be a knocking brick that learns ECC.
First, talk from the parallel line.
Parallel lines, never intersect. No one is suspected of :) But it is doubtful to this conclusion. Will parallelism will intersect a very far away? In fact, no one has seen it. Therefore, "parallel lines, never intersect" is just hypothesis (everyone thinks about the parallel axioms of junior high school, is not proven). Since you can assume that the parallel line will never intersect, you can assume that the parallel line intersects far away. That is, the parallel line intersects the infinite far point p∞ (please close your eyes, imagine that the infinite far point p∞, P∞ is very unusual, in fact, the abstract ability of mathematics exercise, it is better to do it is exercise Imagination). Give a picture to help understand:
There is a P∞ point on the line, and the benefits of bringing all the lines intersect, and there is only one intersection. This is unified with the parallelism of the line. To distinguish between the original plane, it is called a normal point.
The following is a few nature of infinity.
▲ The infinite far point on the line L can only have one.
(From definition, you can directly
▲ A set of parallel straight lines on the plane have a public infinity.
(From definition, you can directly
▲ The two straight lines L1, L2 on the plane have different infinite points.
(Otherwise, L1 and L2 have public infinity far podp, then L1 and L2 have two intersections A, P, so it is assumed that the error is assumed.)
▲ All the whole infinity in the plane constitutes a
Infinitely straight. (I imagine this straight line)
▲ All infinite points on the plane and all the usual points
The shooting plane.
Second, the shooting coordinate system
The shooting coordinate system is an extension of the ordinary plane right angle coordinate system (which is the Cartesian Cartia Cutting Cartes "of our junior high school. We know that the ordinary plane right angle coordinate system does not design coordinates for infinity and distinction, can't express infinity. In order to express an infinite point, a shooting planar coordinate system is generated. Of course, the shooting plane coordinate system can also represent the old topic point (mathematics is also "downward").
Our coordinates (X, Y) on the point A on the normal plane right angle coordinate system are modified:
Let X = X / Z, Y = Y / Z (z ≠ 0); then A point can be represented as (x: Y: Z).
It turns into a coordinate point with three parameters, which has established a new coordinate system on the plane.
Example 2.1: See the coordinates of the spot (1, 2) in the new coordinate system. Solution: ∵X / z = 1, y / z = 2 (z ≠ 0) ∴x = z, y = 2Z ∴ coordinate is (Z: 2Z: Z), z ≠ 0. That is (1: 2: 2) (2: 4: 2) (1.2: 2.4: 1.2) is like (Z: 2Z: Z), Z ≠ 0 coordinates, all (1, 2) in new coordinates Coordinates under the system. We can also get the straight line equation AX by CZ = 0 (thinking about why? Tip: The normal planned straight-line coordinate system is AX BY C = 0). Can a new coordinate system indicate infinite perspectives? Then let us think about where the endless is. According to the knowledge of the previous section, we know that the infinite point is the intersection of two parallel straight lines. So how do you ask two straight intersection coordinates? This is the knowledge of junior high school, which is associated with the equation corresponding to the two straight lines. The equation of parallel straight lines is:
AX by C
1Z = 0; AX by C
2z = 0 (C
1 ≠ C
2);
(Why? Tip: Can be considered from slopes because the parallel line slope is the same;
Connect the second equation, solve. C
2z = C
1Z = - (AX by), ∵C
1 ≠ C
2 ∴Z = 0 ∴AX by = 0;
So infinity is the form of this form (x: y: 0). Note that the usual point z ≠ 0, infinity far point z = 0, so the equation corresponding to the infinity straight line is z = 0.
Example 2.2: An infinite point of the parallel line L1: x 2y 3z = 0 and L2: X 2Y Z = 0 intersects. Solution: Because of L1∥L2, there is z = 0, X 2Y = 0; so the coordinate is (-2y: Y: 0), y ≠ 0. That is (-2: 1: 0) (- 4: 2: 0) (- 2.4: 1.2: 0), such as (-2y: Y: 0), Y ≠ 0 coordinates, all indicate this infinite point.
It seems that this new coordinate system can represent all points on the shooting plane, we will show this coordinate system that can represent all points on the shooting plane.
Overy and shadow flat coordinate system.
Exercise: 1, seeking point A (2, 4) coordinates under the plane of the shooting plane. 2, the viewing of the surgical shadow plane is below the point (4.5: 3: 0.5), the coordinates under the normal flat right angle coordinate system. 3, ask the line X Y Z = 0 on the coordinates of the infinite point. 4, judgment: the endless point and infinity straight line and straight line AX by = 0 in the line AX by CZ = 0 are the same point?
Third, elliptical curve
In the previous section, we established a shooting coordinate system, which we will establish an elliptic curve equation under this coordinate system. Because we know, the curve in the coordinates can be represented by equations (such as: unit circle equation is x
2 Y
2 = 1). The elliptic curve is a curve, and the natural elliptical curve also has an equation. Definition of an elliptic curve:
A elliptic curve is satisfying equation Y2Z A1XYZ A3YZ2 = X3 A2X2Z A4XZ2 A6Z3 ---------------- [3-1]
All points are set, and each point on the curve is non-singular (or gloss).
Detailed explanation:
▲ Y
2Z a
1XYZ A
3yz
2 = X
3 a
2X
2Z a
4XZ
2 a
6z
3 is a WeierStrass equation (Wellstras, Karl Thetor Wilhelm Weierstrass, 1815-1897), is a homogeneous equation.
▲ The shape of the elliptic curve is not ellipse. Just because the elliptic curve is described, it is similar to calculating an elliptical circumference (calculating the elliptical circumference of the equation, I have not seen it, and the elliptical line points (setting density is 1) are not coming. Who knows this Equation, please tell me ^ _ ^), so you have name.
Let's take a look at what the elliptic curve is like.
▲ The so-called "unspeakable" or "smooth", in mathematics, any point of deflection forth in the curve
X (x, y, z), f
Y (x, y, z), f
Z (x, y, z) cannot be 0 at the same time. If you don't have to learn higher mathematics, you can understand this word like this, that is, there is a tangent in any point of the equation.
The following two equations are not an elliptical curve, although they are equation [3-1].
Because they are in (0: 0: 1) points (ie the origin) without tangent.
▲ There is an infinite far point O∞ (0: 1: 0) on the elliptic curve, because this point meets the equation [3-1].
I know the infinity of the elliptic curve. We can put the elliptic curve on the normal flat right angle coordinate system. Because the normal plane right angle coordinate system is only less infinite than the shooting coordinate system. In the normal flat right angle coordinate system, we find the curve equations consisting of all the usual points on the elliptic curve, plus infinite far point O∞ (0: 1: 0), does not constitute an ellipse curve?
We set X = X / Z, Y = Y / Z to get into equation [3-1] obtained:
Y2 a1xy a3y = x3 a2x2 a4x A6 ------------------------- [3-2]
That is to say, the smooth curve of the equation [3-2] plus an infinite far point O∞, which constitutes an elliptic curve. In order to facilitate operation, expression, and understanding, the elliptic curve will mainly use [3-2] in the future.
At the end of this section, we talked about the tangent slope problem of the elliptic curve.
The definition of an elliptic curve can be known that the elliptic curve is smooth, so the usual points on the elliptic curve have tangent. The most important parameter of the cutting line is the slope K.
Example 3.1: Q2 A1XY A3Y = X3 A2X2 A4X A6, the slope of the tangent of the usual point A (X, Y). Solution: Let F (x, y) = Y2 A1XY A3Y-X3-A2X2-A4X-A6 Severe Drafting FX (X, Y) = A1Y-3X2-2A2X-A4 fy (x, y) = 2Y A1X A3 derivatives are: f '(x) = - fx (x, y) / fy (x, y) = - (A1Y-3X2-2A2X-A4) / (2y A1X A3) = (3x2 2A2X A4-A1Y) / (2Y A1X A3) so K = (3x2 2A2X A4-A1Y) / (2Y A1X A3) ----------------- ------- [3-3] It doesn't matter if you don't understand the problem. Remember to conclusion [3-3].
Exercise: 1, the elliptic curve equation of the legend will be given to the equation on the normal plane right angle coordinate system.
Fourth, addition on the elliptic curve
In the previous section, we have seen the image of the elliptic curve, but there is no connection between the point and the point. Can we build an algorithm similar to the algorithmic algorithm? Genius's mathematician found this operational algorithm
☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆ Introducing the concept of group, ring, and domain in the near century, so that algebraic operations It has reached a high degree of unity. For example, mathematicians summarize the main features of ordinary additives, propose adding groups (also called exchange groups, or Abel (Abel), in the eyes of the group. There is no difference between the addition of the addition and the elliptic curve. This may be mathematical abstraction :). For the specific concepts of groups and plus group, please refer to mathematics books in the near generation. ☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆
Operating algorithm: Two points P, Q (if p, Q two points coincide, do two points of P, and do two points of P, and do the P-point cutting line) to do the parallel line of the Y-axis of the Elliptic curve. Hand in R. We specify P Q = R. (As shown)
Specks detailed:
▲ The is not a normal addition in the real number, but from the abstract addition of ordinary add, he has some nature of ordinary addition, but the specific algorithm is clearly different from ordinary additive.
▲ According to this rule, you can know that the elliptic curve infinite point O∞ is connected to P 'on the elliptic curve, and the parallel line of the Y-axis is parallel to P, so there is an endless point O∞ P. = P. In this way, the role of infinity far point O∞ is quite equivalent to ordinary plus (0 2 = 2), we call infinity o∞ o∞
Zero element. At the same time, we call P 'to P.
Negative elements (referred to as, negative P; record, -p). (See the figure below)
▲ According to this rule, you can get the following conclusions: If three points A, B, C on the elliptic curve are on the same line, then they are equal to zero, namely A B C = O∞
▲ K is added, we remember KP. As shown below: P P P = 2P P = 3p.
Below, we use the coordinates of P, Q points (X
1, y
1), (x2, y
2), ask the coordinate of R = P Q (X
4, y
4).
Example 4.1: Entering the Elliptical Curve Equation Y2 A1XY A3Y = X3 A2X2 A4X A6, the coordinates of the usual point P (x1, y1), q (x2, y2) and R (X4, Y4). Solution: (1) Prevention point -R (x3, y3) because of P, Q, -R three-point common line, set the common line equation is Y = kx b, where P ≠ Q (P, Q is two points Unsweight), the line slope K = (Y1-Y2) / (x1-x2) If P = Q (p, Q two points coincides), the straight line is the tangent of the elliptic curve, so it is known from Example 3.1: k = (3x2 2A2X A4 -A1Y) / (2Y A1X A3) Therefore, the coordinate value of P, Q, -R is equation: Y2 A1xy A3Y = X3 A2x2 A4X A6 ------- ---------- [1] y = (kx b) ----------------- [2]. [2], substitute [1] (kx b) 2 A1X (KX B) A3 (KX B) = x3 A2x2 A4X A6 -------- [3] [3] The chemical formation is the general equation, according to the three equation roots and coefficients (when the three-term coefficient is 1; -x1x2x3 is equal to the constant term coefficient, X1X2 X2x3 X3X1 is equal to one-time coefficient, - (x1 x2 x3) equal Secondary merges.) So - (x1 x2 x3) = A2-KA1-K2 X3 = K2 KA1 A2 X1 X2; ----------------- ---- Ask the horizontal coordinates of the point -R because K = (Y1-Y3) / (x1-x3) is Y3 = Y1-K (x1-x3); ------------ ------------------ As the ordinate (2) of the point -R (2) Using -R to obviously have X4 = x3 = k2 ka1 A2 X1 X2 ; ---------- The horizontal coordinates of the point R and Y3 Y4 are X = X4 Equations Y2 A1XY A3Y = X3 A2X2 A4X A6 to decrease into general equation Y2 ( A1X A3) Y- (x3 A2X2 A4X A6) = 0, according to the secondary equation root and coefficient Relation: - (A1X A3) = Y3 Y4, Y4 = -y3- (A1X A3) = K (X1-X4) -y1- (A1X4 A3); ----------------------------------------------------------------------------------------------------------------------------------------------------------------- ; Y4 = k (x1-x4) -Y1-A1X4-A3;
At the end of this section, reminding everyone that the previously provided images may give you an illusion, that is, the elliptical curve is about the X-axis symmetrical. In fact, the elliptical curve is not necessarily regarding the X axis. Y
2-xy = x
3 1
V. Elliptic curve in password
We now basically have a preliminary understanding of the elliptic curve, which is a great time. But please note that the elliptic curve learned in front is continuous and is not suitable for encryption; so we must turn the elliptic curve into discrete points. Let us think about it, why is the elliptical curve continuous? It is because the coordinates of the elliptic curve are real (that is, the elliptic curve mentioned earlier is defined on the real domain), the real number is continuous, resulting in continuous curve. Therefore, we have to define the elliptic curve on a limited domain (as the name suggestions, limited domains are only domains composed of limited elements).
☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆ ☆ ☆ ☆ ☆ The concept of domain is abstract from our constant, real-time operation, strict Please refer to the number of recent generation numbers. Simply put, the elements in the domain are the same as a ratio, with their own addition, multiplication, division, unit (1), zero (0), and satisfy the exchange rate, allocation rate. ☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆
Below, we give a limited domain F
P, this domain has only limited elements.
Only P (p) is only p (p) element 0, 1, 2 ... p-2, p-1; FP is added (MOD P); ie, (a b); C) ÷ p The remainder of P and the remainder of C ÷ P. FP multiplication (A × B) rule is A × B≡C (MOD P); FP division (A ÷ B) rule is A / B≡C (MOD P); ie A × B-1≡C (MOD) p); (B-1 is also an integer between 0 to P-1, but satisfying B × B-1≡1 (MOD P); specific cases can refer to the primary alienism, or another one
article
). The unit element of FP is 1, and the zero element is 0.
At the same time, not all elliptic curves are suitable for encryption. y
2 = x
3 AX B is a class of elliptical curves that can be used to encrypt, and is also a simple type. Let's take Y
2 = x
3 AX B This curve is defined in f
P:
Select two non-negative integers A, B 4A3 27B2 ≠ 0 (MOD P) satisfying the following conditions to meet all points (x, y) of the following equations, plus infinite far point O ∞, constitute an elliptic curve. Y2 = x3 ax b (mod p) where X, Y belongs to an integer between 0 to P-1, and the elliptical curve is recorded as EP (A, B).
Let's take a look y.
2 = x
Image of 3 x 1 (MOD 23)
Is it impossible to think? The elliptical curve, how to become this like, become a discrete point?
The elliptic curve will appear different from different numbers, but its essence is still an elliptical curve. To give a less appropriate example, it is water, under normal temperature, is a liquid; to zero, the water turns into ice, which has a solid; and the temperature rises to one hundred degrees, the water has become water vapor. But its essence is still H
2O.
Fly
The elliptic curve on the P is also added, but it is no longer explained to the geometric meaning. However, the addition of the addition and the real domain, please compare the readers themselves.
1 infinite far point O∞ is zero element, there is O∞ O∞ = O∞, O∞ P = P = p 2 p (x, y) negative elevation is (x, -y), P (- P) = O∞ 3 p (x1, y1), Q (x2, y2) and R (x3, y3) have the following relationship: X3ZK2-X1-X2 (MOD P) Y3≡K (X1-X3) -y1 (MOD P) where P = Q is k = (3x2 a) / 2y1 if p ≠ q, then k = (Y2-Y1) / (x2-x1) Example 5.1 is known E23 (1, 1) Point P (3, 10), Q (9, 7), seek 1) -P, 2) P Q, 3) 2P. Solution 1) -p value is (3, -10) 2) k = (7-10) / (9-3) = - 1/2, 2 multiplication is 12 because 2 * 12≡1 (MOD 23) K≡-1 * 12 (MOD 23), K = 11. X = 112-3-9 = 109≡17 (MOD 23); y = 11 [3 - (- 6)] - 10 = 89≡20 (MOD 23), the coordinate of P Q is (17, 20) 3 K = [3 (32) 1] / (2 * 10) = 1 / 4≡6 (MOD 23) x = 62-3-3 = 30≡20 (MOD 23) Y = 6 (3-7) -10 = -34≡12 (MOD 23), 2P coordinates (7, 12)
Finally, we talked about the order on the elliptic curve.
If there is a little P in the elliptic curve, there is a minimum positive integer n, so that the number is multiplied by NP = O∞, then n is called P as P.
Order, if the N does not exist, we say that P is unlimited.
In fact, all points of all points on the elliptic curve defined on a limited domain (prove, please refer to the books in the near generation)
Exercise: 1 See all points on E11 (1, 6). 2 Known of E11 (1, 6), g (2, 7), and find all values for all values for 2g to 13 g.
Sixth, simple encryption / decryption on the elliptic curve
The public key algorithm always is based on a mathematical problem. For example, RSA is based on: given two prime numbers p, Q is easy to multiplied by n, and the dual decomposition of N is relatively difficult. What is the problem with the ellipse curve?
Consider the following equation:
K = kg [where K, G is the point on EP (A, B), k is an integer of less than N (n is the order of point G)]
It is difficult to find that K and G are given according to the addition of the addition, the calculation K is easy; but given K and G, seeking K is relatively difficult.
This is the problem used by the elliptic curve encryption algorithm. We refer to the base point, k (k Now we describe a process of encrypting communication with an elliptic curve: 1. User A selects an elliptic curve EP (A, B), and takes a little on the elliptical curve, as the base point G. 2. User A Select a private key K and generates a public key K = kg. 3. User A will pass EP (A, B) and Point K, and G to the user B. 4. After the user b receives the information, the plain text to be transmitted to the EP (A, B) is a point m (there are many coding methods, not discussive here), and generate a random integer R (r 1 = m rk; c 2 = rg. 6, user B will c 1, c 2 Pass the user A. 7. After the user A receives the information, calculates C. 1-kc 2, the result is point M. because C 1-kc 2 = m rk-k (rg) = m rk-r (kg) = m It is possible to decode the point m. In this encrypted communication, if there is a voyager H, he can only see EP (A, B), K, G, C 1, c 2 and pass K, g to K or through C 2, g seeking R is relatively difficult. Therefore, H cannot obtain the plaintext information transmitted between A and B. In the password, an elliptic curve on a FP is described, and six parameters are often used: T = (p, a, b, g, n, h). (P, a, b is used to determine an elliptic curve, G is the base point, n is the order of point G, H is an integer portion of all points m and N to be each other on the elliptic curve) The choice of these participating values directly affects encryption. The parameter value is generally required to meet the following conditions: 1, the larger, but the larger, the larger, the calculation speed will be slow, and the general safety requirements can be satisfied. 2, p ≠ n × h; 3, Pt ≠ 1 (MOD N), 1 ≤ T <20 4, 4A3 27B2 ≠ 0 (MOD P); 5, N is the number of prime; 6, h ≤ 4. 7. Application of elliptic curve in software registration protection We know that the benefit of the public key algorithm as a software registration algorithm is that Cracker is difficult to obtain a registration machine by tracking the verification algorithm. Next, a method of software registration using the FP (A, B) elliptic curve will be introduced. The software author makes a registration machine as follows (also known as signature process) 1. Select an elliptic curve EP (A, B), and the base point g; 2. Select the private key K (the step of k 3, generate a random integer R (R 4. As a parameter, the coordinate value x, y of the username and point R, calculate the SHA (Secure Hash Algorithm Security Rate Algorithm, similar to the MD5) value, ie Hash = SHA (UserName, X, Y); 5, calculate Sn≡r - Hash * K (MOD N) 6, use SN and Hash as the serial number of the user name Username The software verification process is as follows: (there is an elliptic curve EP (A, B), and the base point G, the public key K) 1. In the serial number input from the user, extract SN and Hash; 2, calculate the point R≡SN * G HASH * K (MOD P), if SN, Hash is correct, its value is equal to the coordinates of point r (x, y) during the software author signature, because Sn≡r-Hash * K (MOD N) and so SN * G HASH * K = (R-Hash * K) * G Hash * K = RG-HASH * KG HASH * K = RG- Hash * K HASH * K = rg = r; 3. As the argument of the coordinate value x, y of the username and point R, calculate H = SHA (Username, X, Y); 4, if h = hash is registered successfully. If h ≠ hash, the registration failed (why? Prompt points R and HASH correlation). Simple comparison two processes: The author's signature is used: Elliptic curve EP (A, B), base point G, private key K, and random number R. Software verification is used: elliptic curve EP (A, B), base point G, public key K. Cracker wants to make a registration machine, can only be obtained by using EP (A, B), point g, public key K, and uses K = kg to obtain K. And K is very difficult. Exercise: The following is also a registration algorithm that is often protected. Please read it carefully, and try the answer to the signature process and the verification process to use the parameters. Cracker wants to make a registration machine, how to do it. The software author makes a registration machine (also known as signature process) as follows, selects an elliptical curve EP (A, B), and the base point G; 2, select the private key K (K Eight, conclusion This is finally noted for a paragraph of several months of intermittent writing. For this article, I checked a lot of information, but in order to make the article more easy to understand, I try to avoid the terminology, F The elliptical curve on the 2N domain is not involved. However, some noun descriptions may not be too accurate, I hope that readers have a lot of criticisms for the article. I also only used this article as a first draft, I will constantly revise him. Finally, thank you for seeing snow, sunbird, ccg, and see all members of the Forum on me, thank you people who have helped me, there is no encouragement, this article I have no motivation, thank you, thank you! 2003-5-3 preliminary draft, in seeing the snow forum 2004-7-11 second sheet, correct a picture "Full text" Main references Zhang Ho Rui, "Near World", Higher Education Press, 1978 鹤 严 士 健, "First Number", Higher Education Press, 1982 Duan Yun, "Network Information Security" third, Peking University Computer system Michael Rosing, chapter5 "Implementing Elliptic Curve Cryptography", softbound, 1998 "SEC 1: Elliptic Curve Cryptography", Certicom Corp., 2000 "IEEE P1363a / D9", 2001 original source: http: //blog.9cbs.net/mfkplus/archive/ 2005/01/02 / 237748.ASPX
