First of all, an elliptic curve is not an ellipse. The elliptic equation is as follows:

The curve equation of the elliptic curve that we usually discuss is a 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 curve25519 are not discussed in this paper):

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

elliptic curve encryption algorithm involves group theory, finite fields and other contents in mathematics. This section briefly introduces the related mathematical theories. You can also skip section 3 and look it up again 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. Therefore, the natural number set is derived from the addition and subtraction operation, and the integer set can be derived from the multiplication and division, and then the real number set is derived from the irrational number, and the negative number is introduced into the complex number set. A group is a set and a binary operation.

If the commutative law is satisfied again, the group is called an Abelian group.

according to the definition of group, the addition operation of integers is a group, and it is also 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 are all valid. The unit element in integer addition operation is . All integers n have additive inverses-n.

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

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

Therefore, the elements in a field only need to form an addition group and a multiplication group and satisfy the distribution law, because all the elements in the group have inverse elements, and subtraction/division can be converted into the inverse elements of addition/multiplication elements. The set of real numbers is a field, the unit element in the addition group is , each real number has an addition inverse element, and the unit element in the multiplication group is , and each non-zero real number has a multiplication inverse element. The set of integers is not a domain, because most elements have no multiplicative inverse and cannot form a multiplicative group.

in cryptography, we are usually only interested in the domain of finite elements, which is called a Finite Field. We often use prime number fields in finite fields, and 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, which can be written as. Arithmetic operation in prime number field needs to abide by the rules of integer ring, that is, addition is modular P addition and multiplication is modular P multiplication.

For example:

After a special addition operation, the points on the elliptic curve can form a group in the real number field.

infinity point: define an infinity 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 that the straight lines perpendicular to the X axis are parallel lines. Why can they be defined as all passing points? Because in non-Euclidean geometry, it can be thought that parallel lines will meet at one point at infinity.

elliptic curve point addition: the intersection of a straight line passing through two points and the elliptic curve is recorded, and according to the definition, there are and. Then, the point addition of elliptic curve is defined: that is, the addition result is another intersection point between 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 an Abel group in the addition operation of the elliptic curve. After adding the unit element, the elliptic curve equation is changed to:

It is known by definition, so the final addition only needs to calculate the inverse element of the intersection point. Explanation of several special cases:

The point addition in the geometric sense of elliptic curve is defined in the previous section, which needs to be converted into algebraic addition to facilitate calculation. It should be noted that this is not a simple addition of the coordinates of two points.

suppose the slope of the straight line PQ, and then substitute the straight line equation into the curve to get:, and convert it into a standard formula, which can be obtained according to the vieta theorem. For details of the derivation process, please refer to [cubic-equations].

Two cases need to be distinguished in slope calculation. When P=Q, just 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 Reference 1. It is easy to verify and consistent with the calculation results of algebraic addition formula.

In special cases, if there is a tangent point, for example, the calculation method is unchanged and easy to obtain. 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 achieve 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 itself. That is, the initial straight line becomes the tangent of the elliptic curve, as follows:

We define that nP is obtained by adding a point p n times, which is called scalar multiplication. As in that previou example.

However, when n is large, it takes time to add n times, and there is a problem with efficiency. Because the addition of elliptic curve points constitutes Abel group in real number domain, which satisfies the commutative law and associative law, it can be optimized by [Double-and-add] algorithm. For example, its binary representation is that through optimization, only 7 times of multiplication and 4 times of addition are needed, and the time complexity is reduced. This is a good one-way function, the forward calculation is easy, but the backward and brute force calculation is 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 problem is more difficult. However, because the curve is continuous in the real number field, it may be easier to find some laws to crack. Moreover, there is no limit on the numerical size in the real number domain, floating point number and other problems lead to the calculation efficiency problem. In practical application, the elliptic curve is often limited to a limited domain, and the curve is turned into discrete points, which not only facilitates the calculation, but also increases the difficulty of cracking.

As mentioned earlier, 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 point is a prime number). Then the crack will become a discrete logarithm problem, which is much more difficult than the logarithm problem on a continuous curve. The definition of elliptic curve in prime number field is as follows:

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

The addition of elliptic curve points on the definition is 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 cases:

The point addition of elliptic curve on prime number field still constitutes Abel group. The unit element is still an infinite point, and the inverse element of the element becomes. The commutative law, associative law and closeness can be proved by modular addition and modular multiplication on prime fields. The definition of elliptic curve point addition in real number field has clear geometric significance, which is well proved from geometry. However, the elliptic curve has no obvious geometric significance, and it can be found that three points are satisfied, and the proof of the group law is too cumbersome and omitted (in fact, a simple proof has not been found).

taking the previous curve as an example, there is, and both and are on the elliptic curve. Graphically, in a straight line.

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

for an elliptic curve, there are elements in the prime number field, and the order is 24(23 points in the prime number field+1 point at infinity). If p is large, it is very difficult to calculate the order by brute force. Fortunately, the order of a group can be calculated in polynomial time by using [Schoof algorithm]. To calculate the number of points of an elliptic curve on a finite field, please refer to [counting points on elliptic curves].

Schoof algorithm uses Hasses theorem. Hasses theorem gives the range of the order of the 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, a point p is selected, and then nP is calculated as the public key. Let's take it as an example, and we use a new calculation 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 subgroup is 8), and the point p is called the base point or generator of the subgroup. Cyclic subgroup is the basis of elliptic curve cryptosystem. We expect that the more elements in the subgroup, the better. How to find a suitable subgroup is particularly important.

the first problem to be solved is how to find the order of the subgroup generated after the multiplication operation of p when the point p on the elliptic curve is known. According to Lagrange's group theory theorem, the order of a subgroup is the divisor of the order of a parent group. The following methods can be used to solve the order of subgroups generated by points p on the curve:

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

in the encryption algorithm, we expect to find a subgroup with high order. However, it is usually not to find a base point first, and then calculate the order of subgroups, because it is too uncertain and difficult to realize in algorithm. On the contrary, it is much easier to choose a large subgroup first, and then find a base point to generate the subgroup.

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

A prime number is usually chosen as the order of subgroups, that is, n is a prime number. It can be found that the point generates a subgroup of order n (except because this subgroup has order 1), and the point that is not equal 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 the calculated base point G may be a divisor of n instead of n, which does not meet the requirements. Taking the curve as an example, if we choose, then we randomly select a point and calculate it, which just meets the requirements.

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

For example, the domain parameters of elliptic curve [secp256k1] used in digital signature by Bitcoin are as follows: