Bitcoin uses an elliptic curve algorithm to generate public and private keys, with the secP256K1 curve chosen. ECC (Elliptic Curves Cryptography) is a public-key algorithm, just like RSA (the name of Ron Rivest, Adi Shamir, Len Adleman).

First, start with parallel lines

Parallel lines never meet. No one doubts that 🙂 but in modern times this conclusion has been questioned. Could parallel lines meet far, far away? In fact, no one has. So “parallel lines never meet” is just an assumption (think of the parallel axiom in junior high school, there is no proof). Since we can assume that parallel lines never meet, we can also assume that parallel lines meet far, far away. So parallel lines intersect at infinity P infinity. (Close your eyes and imagine that infinity P infinity, P infinity is not real, but mathematics exercises your imagination more than abstraction.) Here’s a graph to help you understand:

The nice thing about having P infinity on a line is that all the lines intersect, and only one point. This unifies the parallelism and intersection of the line. To distinguish it from infinity we call points on the original plane ordinary points.

Here are some properties of infinity.

▲ There can be only one infinity on line L. A group of parallel lines on a plane have common infinity points. Any two intersecting lines L1 and L2 on a plane have different points of infinity. (Otherwise L1 and L2 have A common infinity P, then L1 and L2 have two intersecting points A and P, so the assumption is incorrect.) ▲ All the infinity points on the plane form an infinity line. ▲ All the infinity points and all the ordinary points on the plane form the projective plane.

Projective plane coordinate system

The projective plane coordinate system is an extension of the normal cartesian plane cartesian coordinate system that we learned in junior high school. We know that the normal plane cartesian coordinate system does not have coordinates for infinity, cannot represent infinity. To represent infinity, projective plane coordinates were created, and of course projective plane coordinates also represent old ordinary points very well (mathematics is also “downward compatible”).

We modify the coordinates (x,y) of point A on the normal plane cartesian coordinate system as follows: let x= x /Z,y = y /Z (Z≠0); Then point A can be expressed as (X:Y:Z). It becomes a coordinate point with three parameters, and that establishes a new coordinate system for the points on the plane.

Example 2.1: find the coordinates of point (1,2) in the new coordinate system. ∴X /Z=1, ∴ Y/Z=2 (Z≠0) X=Z, ∴ Y=2 (Z:2Z:Z), ∴ Z≠0. That is, coordinates of (1:2:1) (2:4:2) (1.2:2.4:1.2), such as (Z:2Z:Z) and Z≠0, are all coordinates of (1,2) under the new coordinate system.

We can also get the equation aX+bY+cZ=0. Tip: The general equation of a line in an ordinary plane cartesian coordinate system is Ax +by+c=0. Can the new coordinate system represent infinity? So let’s think about where infinity is. So from what we learned in the last video, we know that infinity is the intersection of two parallel lines. So, how do we find the coordinates of the intersection of two lines? This is the knowledge in junior high school, which is to solve the corresponding equations of two lines simultaneously. The equation of parallel lines is aX+bY+c1Z =0; AX + bY + c2Z = 0 (c1 indicates c2); B: Why? Tip: consider the slope, because parallel lines have the same slope);

Combine the two equations and solve them. ∴ x =0 (∴ x + x =0), ∴ x =0 (∴ x + x =0), ∴ x =0 (∴ x + x =0); So the point at infinity is going to be X: Y: 0. Notice that Z does not equal 0, and Z equals 0 at infinity, so the equation for the line at infinity is Z equals 0.

Example 2.2: Find the infinity where parallel lines L1: X+2Y+3Z=0 intersect L2: X+2Y+Z=0. Solution: 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) coordinates of the same form as (-2y :Y:0), Y≠0, all represent this infinity point.

It appears that this new coordinate system can represent all points on the projective plane, and we will call this coordinate system capable of representing all points on the projective plane projective plane.

Elliptic curve

In the last video, we set up the projective plane coordinate system, and in this video we’re going to set up the elliptic curve equation in this coordinate system. Because we know that curves in coordinates can be expressed in terms of equations (for example, the unit circle equation x2+y2=1). Elliptic curves are curves, and natural elliptic curves also have equations.

Definition of an elliptic curve: An elliptic curve is the set of all points on the projective plane satisfying the equation Y2Z+a1XYZ+a3YZ2=X3+a2X2Z+a4XZ2+a6Z3 —————-[3-1], and every point on the curve is nonsingular (or smooth).

Definition:

▲ Y2Z+a1XYZ+a3YZ2 = X3+a2X2Z+a4XZ2+a6Z3 (Weierstrass, Karl Theodor Wilhelm Weierstrass,1815-1897) is a homogeneous equation.

The shape of an elliptic curve is not elliptical. It’s just that the describing equation for an elliptic curve is similar to the equation for calculating the circumference of an ellipse. Who knows this equation, please tell me ah ^_^), hence the name.

So let’s see what an elliptic curve looks like.

▲ The so-called “non-singular” or “smooth”, in mathematics means that the partial derivatives of any point on the curve Fx(x,y,z), Fy(x,y,z), Fz(x,y,z) cannot be 0 at the same time. If you haven’t taken advanced mathematics, the way to think about it is that any point that satisfies an equation has a tangent line.

Neither of the following equations is an elliptic curve, although they are the form of equation [3-1].

Because they don’t have a tangent line at the point 0:0:1.

▲ There is an infinite point O∞ (0:1:0) on the elliptic curve because this point satisfies the equation [3-1].

We know infinity on an elliptic curve. We can put an elliptic curve in a normal plane rectangular coordinate system. Because ordinary plane cartesian coordinates are only infinitely less than projective plane coordinates. If we solve the equation of the curve composed of all ordinary points on an elliptic curve in an ordinary plane cartesian coordinate system, then we add the infinite point O∞ (0:1:0) to the elliptic curve.

We set x = x/Z, y = y/Z [3-1] get into equation: y2 + a1xy + a3y = x3 + a2x2 + a4x + a6 — — — — — — — — — — — — — — — — — — — — — — — — – [3-2]

In other words, the smooth curve satisfying the equation [3-2] plus an infinite point O infinity forms an elliptic curve. In order to facilitate operation, expression, and understanding, elliptic curves will be mainly discussed in the form of [3-2].

The definition of an elliptic curve tells us that an elliptic curve is smooth, so ordinary points on an elliptic curve have tangent lines. And the most important parameter of the tangent line is the slope k.

Example 3.1: Find the slope k of the tangent line to the ordinary point A(x,y) on the elliptic curve equation y2+a1xy+a3y=x3+a2x2+a4x+a6. F(x,y)= y2+a1xy+a3y-x3-a2x2-a4x-a6; F(x,y)= y2+a1xy+a3y-x3-a2x2-a4x-a6; ‘f (x) = – Fx (x, y)/Fy (x, y) = – (a1y – 3 x2 – a2x 2 – a4)/(2 + a1x + a3) y = (3 x2 + 2 a2x + a4 – a1y)/(y + a1x + 2 a3) so k = (3 x2 + 2 a2x + a4 – a1y) /(2y+a1x +a3) ————————[3-3]

It doesn’t matter if you can’t understand the process of solving the problem, just remember the conclusion [3-3].

Addition on elliptic curves

In the last section, we saw a picture of an elliptic curve, but there didn’t seem to be any connection between the points. Can we set up an algorithm similar to addition on the real number line? The ingenious mathematician found the algorithm.

Since the concept of group, ring and field was introduced into algebra in the last century, algebraic operation has reached a high degree of unity. For example, mathematicians summarize the main characteristics of ordinary addition and propose the addition group (also called Abelian group, or Abelian group), in the eyes of the addition group. The addition of real numbers is no different from the addition of elliptic curves. This may be a mathematical abstraction :).

Operation rule: arbitrarily take two points P and Q on the elliptic curve (if P and Q coincide, make the tangent line of point P) make a straight line crossing at another point R ‘on the elliptic curve, and make the parallel line crossing at R across R’ on the Y-axis. Let’s say P plus Q is equal to R. (as shown in figure)

The + here is not the ordinary addition of real numbers, but the addition abstracted from the ordinary addition, he has some properties of ordinary addition, but the specific operation rules are obviously different from ordinary addition.

▲ According to this rule, it can be known that the line at infinity of the elliptic curve O∞ intersects P ‘with the line at a point P on the elliptic curve, and the parallel line of the Y-axis intersects P through P’, so the point at infinity O∞+ P = P. In this way, infinity O∞ acts as zero in ordinary addition (0+2=2), and we call infinity O∞ a zero element. And we call P ‘the negative member of P (minus P; I’ll call that minus P. (See below)

▲ According to this rule, it can be concluded that if the three points A, B, and C on an elliptic curve lie on the same line, their sum is equal to the zero element, i.e. A+B+C= O∞

▲ Add k identical points P, we call it kP. P+P+P = 2P+P = 3P.

Next, we use the coordinates of P and Q (x1,y1), (x2,y2), to find the coordinates of R=P+Q (x4,y4).

Example 4.1: Find the coordinates of P(x1,y1), Q(x2,y2) and R(x4,y4) on the elliptic curve equation y2+a1xy+a3y=x3+a2x2+a4x+a6. Solution :(1) find the point -r (x3,y3). Since P,Q and -r are collinear, let the collinear equation be y=kx+b.

Where, if P≠Q(P,Q two points do not coincide), the slope of the line k=(y1-y2)/(x1-x2). If P=Q(P,Q two points coincide), the line is the tangent of the elliptic curve.

Therefore, according to Example 3.1,

k=(3×2+2a2x+a4 -a1y) /(2y+a1x+a3)

So P, Q, – the coordinates of the three R’s equations: y2 + a1xy + a3y = x3 + a2x2 + a4x + a6 — — — — — — — — — — — — — — — — – [1] y = (kx + b) — — — — — — — — — — — — — — — — — [2].

Will [2], in [1] (kx + b) 2 + a1x (kx + b) + a3 (kx + b) = x3 + a2x2 + a4x + a6 — — — — — — — – [3] to [3] into a general equation, and according to the cubic equation root and coefficient of relationship (when the three coefficients is 1; Minus x1x2x3 is equal to the constant term, x1x2 plus x2x3 plus x3x1 is equal to the first term, minus x1 plus x2 plus x3 is equal to the second term. So – (x1 + x2 + x3) = a2 – ka1 – k2 x3 = k2 + ka1 + a2 + x1 + x2. — — — — — — — — — — — — — — — — — — — — – the abscissa of point – R Because k = (y1, y3)/(x1 – x3) so the y3 = y1 – k (x1 – x3); ——————————- find the y-coordinate of the point -r

(2) x4=x3= k2+ka1+a2+x1+x2; ———— find the x-coordinate of point R and y3 y4 is x=x4. The solution of the equation y2+a1xy+a3y=x3+a2x2+a4x+a6 becomes the general equation y2+(a1x+ A3)y-(x3+a2x2+a4x+a6)=0, According to the quadratic equation root and coefficient of relationship: – (a1x + a3) = y3 + y4 so y4 = – y3 – (a1x + a3) = k (x1 x4) – y1 – (a1x4 + a3); ————— to find the ordinate of point R namely: x4=k2+ka1+a2+x1+x2; y4=k(x1-x4)-y1-a1x4-a3;

At the end of this section, I want to draw your attention to the fact that the images provided may give you the illusion that the elliptic curve is symmetric with respect to the X-axis. In fact, elliptic curves are not necessarily symmetric about the x axis. Y2 minus xy is equal to x3 plus 1

Elliptic curves in cryptography

We now have basically a rudimentary understanding of elliptic curves, and that’s something to be happy about. But please note that the elliptic curves we learned earlier are continuous and not suitable for encryption; So, we have to turn elliptic curves into discrete points.

So let’s think about why why are elliptic curves continuous? Because the coordinates of the points on the elliptic curve are real numbers, the real numbers are continuous, which leads to the continuity of the curve. Therefore, we define an elliptic curve over a finite field (as the name implies, a field consisting of only a finite number of elements).

The concept of a field is abstracted from our operations on rational and real numbers, and for a strict definition refer to numbers in modern algebra. Simply speaking, the elements in the domain, like rational numbers, have their own addition, multiplication, division, identity element (1), zero element (0), and meet the exchange rate, distribution rate.

Next, we give a finite field Fp, which has a finite number of elements. Fp has only p (p is prime) elements 0,1,2… P – 2, p – 1; The addition (a+b) rule for Fp is a+b≡c (mod P); That is, the remainder of (a+ C)÷p is the same as that of C ÷p. The multiplication (a×b) rule for Fp is a×b≡c (mod P); The division of Fp (A ÷b) is a/ B ≡c (mod P); A × B-1 ≡ C (mod P); (B-1 is also an integer between 0 and p-1, but satisfies b× B-1 ≡1 (mod p); Please refer to elementary number theory, or another article of mine. The identity element of Fp is 1, and the zero element is 0.

Also, not all elliptic curves are suitable for encryption. Y2 =x3+ax+b is the simplest kind of elliptic curve that can be used to encrypt. Let’s define the curve y2=x3+ax+b as Fp:

An elliptic curve is formed by selecting two non-negative integers a and b less than p(p is prime) 4A3 + 27B2 ≠0(mod p), then all points (x,y) satisfying the following equation, plus the infinity point O∞. Y2 =x3+ax+b (mod p) where x and y are integers from 0 to p-1, and this elliptic curve is called Ep(a,b).

Let’s look at the graph of y2=x3+x+1 (mod 23)

Is that weird? How did the elliptic curve turn out to be like this, a discrete point?

An elliptic curve may look different in different number domains, but it is still an elliptic curve in nature. To take an inapt example, water, at room temperature, is liquid; Below zero, water becomes ice and solid; When the temperature rises to 100 degrees, the water turns back into steam. But it’s still H2O.

The elliptic curve on Fp also has addition, but it can no longer be explained geometrically. However, the addition rule and the real number field is similar, please compare yourself.

1. O up at infinity is zero, there are up up up + O = O, O O up + P = P (2) P (x, y) negative yuan is (x, y), has a P + (-) P = O up 3. P (x1, y1), Q (x2, y2) and R (x3, y3) has the following relationship: X3 ≡ k2 – x1 – x2 (mod p) y3 ≡ k (x1 – x3) – y1 (mod p) among them if p = Q k = (3 x2 + a) / 2 if y1 p indicates a Q, the k = (y2 – y1)/(x2 – x1)

Example 5.1 given P(3,10), Q(9,7) on E23(1,1), find 1) -p, 2)P+Q, 3) 2P. Solution 1) — P is (3,-10) 2) k=(7-10)/(9-3)=-1/2, 2’s multiplicative inverse is 12 because 2*12≡1 (mod 23) k≡-1*12 (mod 23) so k=11. X = 112-3-9 = 109, 23 (mod) ≡; Y = 11 [3 – (6)] – 10 = 89 ≡ 20 (23) mod so the coordinates of the P + Q (17, 20) 3) k = [3 (32) + 1)/(2 * 10) = 6 1/4 ≡ 23 (mod) x = 62-3-3 = 30 ≡ 20 (23) mod Y =6(3-7)-10=-34≡12 (mod 23) so the coordinates of 2P are (7,12) and finally, let’s talk about the order of the points on the elliptic curve. If the smallest positive integer n exists at a point P on the elliptic curve such that the number times nP=O infinity, then n is called the order of P. If n does not exist, we say that P is of infinite order. In fact, all points of order N on an elliptic curve defined over a finite field exist (for proof, refer to recent algebra books).

Simple encryption/decryption on elliptic curves

Public-key algorithms are always based on a mathematical puzzle. RSA, for example, relies on the fact that given two prime numbers P and q are easy to multiply to produce n, whereas factoring n is relatively difficult. So what’s the problem with elliptic curves?

Consider the following equation: K=kG [where K,G is a point on Ep(a,b) and K is an integer less than n (n is the order of point G)] It is not difficult to see that given K and G, it is easy to calculate K according to the rule of addition; But given K and G, it’s harder to find K. This is the problem of elliptic curve encryption algorithm. Word-wrap: break-word;” > < p style=”word-wrap: break-word; >

Now we describe a process for encrypted communication using elliptic curves:

1. User A selects an elliptic curve, Ep(A, B), and takes A point on the elliptic curve as base point G. 2. User A selects A private key k and generates A public key k =kG. 3. User A sends Ep(A, B) and points K and G to user B. 4. After receiving the message, user B will encode the plaintext to Ep(a, B) point M (there are many encoding methods, which will not be discussed here), and generate a random integer r (r 5, user B’s calculation point C1=M+rK; C2 = rG. 6. User B sends C1 and C2 to user A. 7. After receiving the message, user A calculates C1-kC2, resulting in point M. Because C1-kc2 =M+ Rk-K (rG)=M+ rk-R (kG)=M and then decode the point M to get the plaintext.

In this encrypted communication, if there is a voyeur H, he can only see Ep(a, B), K, G, C1, C2 and finding K through K and G or r through C2 and G is relatively difficult. Therefore, H cannot obtain the plaintext information transmitted between A and B.

In cryptography, six parameters are used to describe an elliptic curve on Fp: T=(p,a,b,G,n,h). (P, A, and b are used to determine an elliptic curve, where G is the base point, n is the order of point G, and h is the integral part of all points on the elliptic curve divided by m and n)

The selection of these parameters directly affects the security of encryption. Parameter values generally meet the following conditions:

1. Of course, the bigger p is, the safer it will be. However, the larger p is, the slower the calculation speed will be. 2, p indicates n * h; 3, Pt ≠1 (mod n), 1≤t<20; 4, 4A3 + 27B2 ≠0 (mod p); 5. N is prime; 6, h 4 or less.

The application of elliptic curve in software registration protection

We know that the advantage of using the public key algorithm as the software registration algorithm is that Cracker is difficult to get the registration machine by tracking the authentication algorithm. Below, a software registration method using Fp(a,b) elliptic curve is introduced.

The software author makes the registration machine (also known as the signing process) as follows

1. Select an elliptic curve, Ep(a,b), and base point G; 2. Select the private key k (k

Generate a random integer r (r4, take the username and the coordinate value x and y of point r as parameters, calculate the Secure Hash Algorithm (SHA) value, that is, Hash=SHA(username,x,y). Compute SN ≡ r-hash * k (mod n) 6. Use SN and Hash as the sequence number of the username username

The software verification process is as follows :(there are elliptic curve Ep(a,b), base point G and public key K in the software)

1. Extract the SN and Hash from the serial number entered by the user. 2, computing point R≡sn*G+Hash*K (mod P),

If sn and Hash are correct, their values are equal to the coordinates of point R(x,y) during the software author’s signature.

Because SN ≡ r-hash *k (mod n) so SN *G+Hash*K =(R-hash *k)*G+Hash* k = rg-hash *kG+Hash* k = rg-hash *k +Hash* k =rG= r; H=SHA(username,x,y) H=SHA(username,x,y); 4. If H=Hash, the registration is successful. If H≠Hash, the registration fails (why? Note the correlation between point R and Hash.

Briefly compare the two processes: author signature used: elliptic curve Ep(a, B), base point G, private key K, and random number R. Software verification used: elliptic curve Ep(a, B), base point G, public key K. Cracker can only use Ep(a,b) in the software, click G, public key K, and use K=kG to obtain K. And k is hard to find.