How do high school students understand bitcoin encryption algorithm

Encryption algorithm is the cornerstone of digital currency, and the public key system of Bitcoin adopts elliptic curve algorithm to ensure the security of transactions. This is because to crack the elliptic curve encryption, we have to face the problem of discrete logarithm. So far, we haven't found a solution in polynomial time. When the space used by the algorithm is large enough, it is considered safe. This paper does not involve advanced mathematics theory, and I hope all high school students can understand it.

Cryptography has a long history, and almost everyone can construct encryption and decryption methods, such as simple cyclic shift. Old or simple methods require secret encryption algorithms and keys. But judging from the long-term offensive and defensive war in history, the secrecy based on encryption is not reliable. At the same time, the transmission of key has always been a big problem, and it often faces the risk of key leakage or man-in-the-middle attack.

In 1970s, cryptography ushered in a breakthrough. Ralph C. Merkle first put forward the idea of asymmetric encryption in 1974. Two years later, Whitfield Diffie and Whitfield Diffie put forward specific ideas based on one-way function and one-way secret door function. Subsequently, a large number of researches and algorithms have emerged, among which RSA algorithm and a series of elliptic curve algorithms are the most famous.

No matter which algorithm, it is on the shoulders of predecessors, mainly based on the development of number theory, group theory and finite field theory with prime numbers as the research object. The key of content encryption no longer needs to be transmitted, but is generated by operation, so that communication is safe even in an insecure network. The decryption of ciphertext depends on the decryption of key, but the decryption of key faces a difficult problem. For RSA algorithm, this problem is a factorization of large numbers, and for elliptic curve algorithm, this problem is a quasi-discrete logarithmic solution. At present, there is no polynomial time solution for both, that is to say, when the number of digits increases, the difficulty increases exponentially.

So how do encryption and decryption work in public and private key systems? In a word, it is carried out through operation in a limited field, because encryption and decryption must be accurate. A finite field is a collection of finite elements. Encryption is mapping one element to another, while decryption is re-mapping. The composition of finite fields is related to the properties of prime numbers.

Some time ago, when Riemann conjecture (closely related to the prime number theorem) was heated up, a technical director of the blockchain project said that the elliptic curve algorithm had nothing to do with prime numbers and was not affected by Riemann conjecture, which was completely nonsense. It can be seen that the blockchain project is mixed and needs to be washed well.

The public key system adopted by Bitcoin and most blockchain projects is elliptic curve algorithm, not RSA. Before introducing the elliptic curve algorithm, it is helpful to understand the discrete logarithm problem for its security.

Let's take a look at Fermat's last theorem:

Original root definition:

Let (a, p)= 1 (a and p are coprime) and satisfy.

The lowest positive integer L of is called the order of module P of A, and the integer A whose order of module P is (maximum) p- 1 is called the primitive root of module P.

Two theorems:

Based on this, we can see that {1, 2,3, … p- 1} is a finite field, and the defined operation gi (mod p) falls within this finite field. At the same time, when I take different numbers from 0 to p-2, the operation results are also different. This is basically the same as the power operation in our high school, except for an extra layer of modular operation.

One more thing to note is that the exponent of g can be not limited to 0~p-2, but actually it can be all natural numbers, but because

Therefore, all the function values are in a finite field, and they are continuous cycles.

Discrete logarithm definition:

Let g be the primitive root of module p, (a, p) = 1,

We call I the exponent of a (for the primitive root g of module p), which is expressed as:

Here ind is the first three letters of the index.

Is this definition very similar to the definition of log? In fact, this is an extension of the logarithmic definition we learned in high school, but it is now applied to finite fields.

But this is different from logarithmic calculation in real number field, which is a continuous space. Logarithmic calculation has formulas and laws to follow, but it is often difficult to be accurate. Our encryption system needs accuracy, but it is extremely difficult to operate on a limited domain. When you know the power value a and the logarithm base g, it is difficult to find its discrete logarithm value I.

When the selected prime number p is large enough, it becomes impossible to find I in time and calculation. Therefore, we can say that I cannot be calculated, that is, I am safe and cannot be cracked.

The elliptic curve algorithm of Bitcoin adopts secp256k 1 algorithm. There are many introductions about the elliptic curve algorithm on the Internet, so I won't go into details here. As long as you know that it is actually a cubic curve (not an elliptic function), it is defined as follows:

Then parameters a and b; Different elliptic curves have different values. Of course, X and Y are defined in real number domain, which is not feasible in cryptography. When it is really used, X and Y should be defined on a finite field, both of which are natural numbers, less than a prime number p, so when defining this elliptic curve, its response is only some discrete points in the coordinate system, which is not like a curve at all. However, in the finite field of sets, its various operations are complete. That is to say, the corresponding point can be found through encryption operation, and the point before encryption can be obtained through decryption operation.

At the same time, like the discrete logarithm problem mentioned above, we hope to find a finite subgroup in the discrete lattice of this elliptic curve, which has the ergodicity and cyclicity mentioned above. This subgroup will be used in all our calculations. In this way, a finite field that we need is established. Then here we need the order of the subgroup (a prime number n) and the base point g in the subgroup (a coordinate, which can traverse the subgroup of order n through addition operation).

According to the above description, we know that the definition of elliptic curve includes a five-element ancestor (P, A, B, G, N, H); Specific definitions and concepts are as follows:

P: large prime number, which is used to define the finite field (group) of elliptic curves.

A, b: parameters of elliptic curve, defining elliptic curve function.

G: the base point in the cyclic subgroup, the basis of operation.

N: the order of cyclic subgroups (another big prime number,

H: the correlation factor of subgroups, that is, the order of a group divided by the integer part of the order of subgroups.

Well, it's time to see what the elliptic curve algorithm of Bitcoin is like. Simply put, it is an elliptic curve with the following parameters:

Elliptic curve defines addition, which means that two points are connected, and the symmetrical point where the X axis intersects the third point of the image is the sum of the two points. There is already a lot of content on the internet, so I won't go into details here.

However, careful students may have a question. The problem with discrete logarithm is that it is easy to find the power, but it is difficult to find its exponent. However, in the elliptic curve algorithm, there is no power, only product. How does this reflect the discrete logarithm problem?

In fact, this is a question of definition. At first, the elliptic curve algorithm defined this operation as sum, but as long as you defined this operation as product, the whole system would be fine. Moreover, if the product is defined, it will be found that all operations conform to the discrete logarithm problem and the principle of selecting finite fields in form. Therefore, this is essentially a discrete logarithm problem. But it is not a simple discrete logarithm problem, in fact, it is more difficult than the general discrete logarithm problem, because it is not simply to find the discrete logarithm of a number, but to find a value similar to the discrete logarithm on a user-defined calculation. This is why the elliptic curve algorithm is very secure, because it uses much fewer private key bits (256 bits) than RSA needs (usually 2048 bits).