Usually, the curve equation of elliptic curve we discuss is binary cubic equation, which has many forms. In the elliptic curve cryptosystem, the most commonly used is the following Weierstrass general formula (other types of elliptic curves such as curve255 19 are not discussed in this paper):

Because the curve equation is similar to the integral formula for finding the arc length of ellipse, it is named elliptic curve. From the curve equation and the image, it is easy to know that the elliptic curve is symmetrical about x, and the reason why the judgment formula is not equal to zero is because there are no singular points on the elliptic curve, that is, it is smooth and derivable everywhere, so that the addition operation can be carried out on the elliptic curve. Here are some elliptic curves suitable for encryption.

Elliptic curve encryption algorithm involves group theory and finite field in mathematics. This part briefly introduces the relevant mathematical theories. You can also skip section 3 and look it up when you meet relevant nouns.

Before discussing groups, let's talk about sets. Set is simply to put a bunch of things together, such as the set of natural numbers. Of course, it is not enough to have a bunch of things, and the interaction between things can better describe the world. So natural number set is derived from addition and subtraction, integer set can be derived from multiplication and division, then real set is derived from irrational number, and negative number is introduced into complex set. A group is a set and a binary operation.

If the commutative law is satisfied again, the group is called Abel group.

According to the definition of group, the addition of integers is both a group and an Abelian group. The addition of natural numbers is not a group. Integer addition constitutes a group because it satisfies the definition of a group: the closure, associative law and commutative law of integer addition all hold. The unit element in integer addition operation is 0. All integers have addition inverses.

In cryptography, a finite group is generally needed, which is defined as follows:

In order for a structure to support four kinds of basic arithmetic at the same time (that is, addition, subtraction, multiplication and division), we need a set containing addition and multiplication groups, which is a field. When a set is a domain, we can perform basic arithmetic operations in it.

Therefore, as long as the elements in a domain form an addition group and a multiplication group and satisfy the distribution law, subtraction/division can be transformed into the inverse elements of addition/multiplication elements because all the elements in the group have inverse elements. The set of real numbers is a field, the unit element in the addition group is 0, each real number has an addition inverse element, the unit element in the multiplication group is 0, and each nonzero real number has a multiplication inverse element. The set of integers is not a domain, because most elements have no multiplicative inverses and cannot form a multiplicative group.

In cryptography, we are usually only interested in the domain of finite elements, which is called finite domain. We often use prime number fields in finite fields. The so-called prime number fields are finite fields with prime numbers. For example, when p is a prime number, the integer ring is a prime number field and can be written as. Arithmetic operation in prime number field needs to follow the rules of integer ring, that is, addition is modular P addition and multiplication is modular P multiplication.

For example, for those who:

The points on the elliptic curve can form a group in the real number field through a specific addition operation.

Infinite point: define an infinite point, that is, all straight lines perpendicular to the X axis passing through any point on the ellipse pass through this point. Some people may wonder, is the straight line perpendicular to the X axis a parallel line? Why can it be defined as all through points? Because in non-Euclidean geometry, it can be thought that parallel lines will intersect at a point at infinity.

Elliptic curve point addition: record the intersection of a straight line passing through two points and the elliptic curve. According to the definition, there is sum. Then the point addition of elliptic curve is defined: that is, the addition result is the other intersection of a straight line passing through a point and perpendicular to the X axis and the elliptic curve. Simply put, it is the symmetrical point of the intersection point about the X axis.

Elliptic curve group: defined as the point set and point addition of elliptic curves in real number field.

Therefore, the points on the elliptic curve form the Abel group in the addition operation of the elliptic curve. After adding unit elements, the elliptic curve equation becomes:

As we can see from the definition, therefore, the final addition only needs to calculate the inverse element of the intersection. Description of several special cases:

In the previous section, the geometric point addition of elliptic curve is defined, which needs to be converted into algebraic addition to facilitate calculation. It should be noted that this is not a simple two-point coordinate addition.

Assuming the slope of the straight line PQ, and then substituting the straight line equation into the curve, we can get:, which can be obtained by converting it into the standard formula according to Vieta's theorem. For the detailed derivation process, please refer to Cubic Equation.

Slope calculation needs to distinguish between two situations. When P=Q, it is enough to find the tangent slope (derivative) of the elliptic curve at point p:

It can be verified simply, for example, the elliptic curve can be obtained through the [visualization tool] in the reference 1. It is easy to verify and is consistent with the calculation result of algebraic addition formula.

For one of the special cases is the tangent point, for example, the calculation method is unchanged, which is easy to get. For special cases, the tangent slope can also verify the correctness of the formula.

In the actual encryption algorithm, we usually need to add elliptic curves several times to realize one encryption, as shown in the following figure:

The process of dot in the figure is:

In the actual encryption algorithm, we often use a point to superimpose ourselves, that is, the initial straight line becomes the tangent of the elliptic curve, as follows:

We define nP by adding a point p to n times, which is called scalar multiplication. As shown in the previous example.

However, when n is large, it takes time to perform n times of addition, and the efficiency is problematic. Because the addition of elliptic curve points constitutes Abel group in real number field, which satisfies the commutative law and associative law, it can be optimized by [double addition] algorithm. For example, its binary representation is optimized, which only needs 7 multiplications and 4 additions, and the time complexity is reduced. This is a good one-way function, and the forward calculation is easy, but the backward and brute force calculation is more complicated.

Order, then q is the public key and n is the private key. If you want to crack the key, the question is "Q = nP, if P and Q are known, how to solve N"? This question is more difficult. But because the curve is continuous in the real number domain, it may be easier to find some laws to crack. Moreover, there is no limit to the numerical size in the real number domain, and floating-point numbers and other problems lead to computational efficiency problems. In practical application, the elliptic curve is often limited in a limited area, and the curve is turned into discrete points, which not only facilitates the calculation, but also increases the difficulty of cracking.

As mentioned above, in order to be safe and easy to realize, it is necessary to limit the elliptic curve to a finite field, and the prime number field is usually used (that is, the points are prime numbers). Then the crack will become a discrete logarithm problem, which is much more difficult than the logarithm problem on the continuous curve. The elliptic curve in the prime number field is defined as follows:

Below is the image of the curve sum. It can be found that the elliptic curve becomes a discrete point and is symmetrical.

The addition of points on an elliptic curve is defined as follows. Compared with the real number field, the formula only has more modular operations.

The calculation of slope m is also divided into two situations:

The point addition of elliptic curves on prime number field still constitutes Abel group. The unit element is still an infinite point, and the inverse element of the element becomes. Commutative law, associative law and closure can be proved by modular addition and modular multiplication over prime number fields. The definition of elliptic curve point addition in real number field has clear geometric significance and is well proved from geometry. However, the elliptic curve has no obvious geometric meaning, and it can be found that the proof of group law is too complicated and omitted (in fact, no simple proof has been found).

Take the previous curve as an example, then, you, and are all on the elliptic curve. Graphically, it is a straight line.

In finite field, the elements of elliptic curve plus group are finite, and the number of elements is the order of group.

For example, an elliptic curve has elements in the prime number field, and its order is 24 (points in the 23 prime number fields+1 infinity points). If p is large, it is very difficult to calculate the order with brute force. Fortunately, the order of a group can be calculated in polynomial time by using [Schoof algorithm]. To calculate the points of an elliptic curve over a finite field, please refer to Points on an Elliptic Curve.

Schoof algorithm uses Hasses theorem. Haas theorem gives the range of the order of elliptic curve, and it can be seen that when p is large, the order is close to the value of p.

Just like the real number field, in the prime number field, choose a point p and then calculate nP as the public key. Let's take an example. We use a new formula in the prime number field.

It can be found that the point set obtained by scalar multiplication of p is a subset of the original elliptic curve group, so it is a subgroup of the original elliptic curve group and a cyclic subgroup. The number of elements in a subgroup is called the order of the subgroup (the order of the example group is 8), and the point p is called the base point or generator of the subgroup. Cyclic subgroups are the basis of elliptic curve cryptosystem. We expect the more elements in the subgroup, the better. How to find a suitable subgroup is particularly important.

First of all, we need to solve a problem, that is, how to find the order of the subgroup generated after the multiplication of P when the point P on the elliptic curve is known? According to Lagrange's group theory theorem, the order of subgroups is the divisor of the order of mother groups. The order of subgroups generated by point P on the curve can be solved by the following method:

Taking the example curve as an example, if the order of the parent group is, then the order of the subgroup generated by the points on the curve can only be. For a point, the order of its generated subgroup is 8, and the order of its generated subgroup is exactly equal to the order of its parent group 24.

In the encryption algorithm, we expect to find high-order subgroups. However, it is usually not to find a basic point first, and then calculate the order of subgroups, because the algorithm is too uncertain to be realized. On the contrary, it is much easier to choose a large subgroup first and then find a basic point to generate subgroups.

As mentioned earlier, the order n of subgroup is the divisor of the order n of mother group, that is, H is an integer, which we call the cofactor of subgroup. Because, so there are:

Usually a prime number is chosen as the order of subgroups, that is, n is a prime number. It can be found that this point generates a subgroup of order n (except this subgroup of order 1), and the unequal point is the base point we are looking for. The specific steps are as follows:

It should be noted that n in the above algorithm must be a prime number, otherwise the order of the subgroup generated by calculating the base point g may be a divisor of n instead of n, which does not meet the requirements. Take the curve as an example, if we choose, then we randomly select a point to calculate, which just meets the requirements.

As mentioned above, the elliptic curve encryption algorithm works in the elliptic curve cyclic subgroup of the prime number domain, and the required domain parameters include:

For example, the domain parameters of the elliptic curve [secp256k 1] used in bitcoin digital signature are as follows: