In real work and life, we use signature to express our approval of a document. Your signature can be recognized by others and cannot be forged. Digital signature is an electronic realization of display signature, which can not only fully realize the characteristics of real signature, but even do better.

Commonly used digital signature algorithms are RSA (Rivest-Shamir-Adleman Scheme) and DSS (Digital Signature Standard). Bitcoin uses ECDSA to generate the public and private keys of accounts and verify transactions and blocks.

1. Alice (In cryptography, people's names start from A to Z and are often used instead of A, B, C, D, etc. , and the lower the letter, the lower the frequency) to generate a pair of keys, one is sk (signature key), which is not public; The other is vk (Authentication Key), which is public.

This pair of keys is generated at the same time and related to each other mathematically. At the same time, it is impossible to infer any information about sk from vk.

2. The digital signature algorithm receives two outputs: information m and sk, and generates a digital signature Sm.

3. The verification function receives information M, Sm and vk as input, and the return result is yes orNo. The purpose of this step is to verify that the digital signature of the information M you see is indeed signed by Alice's sk to confirm whether the information matches the signature.

Different from handwritten signature, handwritten signature is basically similar, but digital signature is greatly influenced by input. A slight change to the input will produce a completely different digital signature. In general, the information is not directly digitally signed, but the hash value of the information is signed. According to the collision-free nature of the encrypted hash function, it is as secure as signing the original information.

Mathematically, a curve formed by any point satisfying the following formula is called a random elliptic curve: A and B can be arbitrary values. Here are some examples of random elliptic functions:

Before we know how to generate public and private keys based on secp256k 1 elliptic curves with ECDSA algorithm, we need to know how to add points to random elliptic curves.

Firstly, the addition of points on elliptic curves is defined. Suppose there are two points A and B on the elliptic curve, then the straight line that makes these two points intersects the curve at the third point (point C), and then point D is obtained symmetrically about X, then D is the sum of these two points, and it is marked as D = A+BD = A+B. Obviously, point D is also on this curve. So the sum of two points on an elliptic curve is also a point on the curve.

Special circumstances:

1. If two points coincide, make the tangent of the point, and the symmetrical point with the intersection point of the curve is sum, that is, a+a+a = c c.

As shown in the figure:

With addition, multiplication is nothing more than multiple addition operations. With the reference point p, we can multiply it and finally get another point on the curve.

Let PPP be a point on the elliptic curve, then the result of multiplying the positive integer kkk by the point PPP is defined by the following formula. Note that the addition in the formula is the addition of points on the above elliptic curve:

The operation of points satisfies the associative law:

Obviously, it is a stupid method to calculate by accumulation, and its time complexity is linear. As mentioned above, the addition of points on the elliptic curve satisfies the law of association, that is, if we extend it, there will be

So there is such a Sao operation, such as calculation, we can calculate first; Then calculate; Recalculate; Final calculation. Here we reduce the addition of 15 times to 4 times.

Of course, the value of k cannot always be a power of 2. In fact, the above operation can be extended to the case where k is an arbitrary positive integer. For example, calculate 23P, calculate first, and then

Because so Total * * * only needs seven additions.

Analysis, for any positive integer k, we can use this method to calculate k? P The number of addition calculations required is reduced to

In other words, this algorithm is a good one from the point of view of time complexity.

This method is called fast power algorithm, which was originally used to quickly calculate the power of a certain number. This is extended to the fast calculation of point multiplication of elliptic curves.

Why does a fast power algorithm suddenly appear after introducing point multiplication on elliptic curves? What is the significance of fast power algorithm for elliptic curve encryption? Because mathematicians/cryptographers find that the time complexity of fast power algorithm is logarithmic, but there is no algorithm much faster than the value of each attempt on the premise of knowing the sum. So the mathematical problem of elliptic curve encryption dependence was born.

If we change the notation and record the addition of points on the elliptic curve as multiplication, the original multiplication becomes a power operation, then the form of the above problem should be consistent with the discrete logarithm problem. Namely:

So this problem is called discrete logarithm problem on elliptic curve.

Although the form is the same, it is not equivalent. In fact, this problem is much more difficult than that of factorization of large integers (RSA) and discrete logarithm (DH). At present, there is no sub-exponential time complexity algorithm (whether large integer factorization or discrete logarithm problem), which makes the key of elliptic curve encryption much shorter than RSA and DH with the same security strength, which is a big advantage of elliptic curve encryption.

Assuming that a value x is randomly selected for calculation, the final result will definitely fall at a point on the curve. The key point of the hypothesis is, can the initial random value be deduced under the condition of open and specific curve equation?

Proof: the search process can only be calculated violently, and the possible value is one of ~. On average, it takes several calculations to find a value. So the question is, how long does it take to run a calculation?

Suppose we use a supercomputer with a main frequency (one trillion operations per second) to calculate from the moment the universe was born, and now we have done it twice. The probability of finding a value is. This probability is close to the probability that the earth will be destroyed by a giant meteorite in the next second. Now that we have seen this, it means that this has not happened.

In the above example, it is a random number of ~ bits, which can be used as the private key. Is a point on the random elliptic curve, that is, the public key generated by the private key, so the advantage can be proved by 1

However, in cryptography, the elliptic curve in the real number field introduced above cannot be used. because

So we need to introduce elliptic curves over finite fields.

In order to prove advantage 2, we need to make some modifications to the random elliptic curve: in order to ensure that the sum of the coordinate values of the points finally calculated is 5 12 bits, secp256k 1 introduces the modular mechanism of prime numbers. Specifically, the random elliptic curve is derived from

It becomes the largest prime number less than.

The random elliptic curve function diagram at this time is as follows:

Specifically, it is to prove to others any information I know but don't expose. (Some are similar to zero knowledge proof)

Proof: The associative law was introduced earlier: adding a hash function, simple modification can lead to: make, then it can be called. At this time, the equation is: for simplicity, we remember sum. At this point, the equation is simplified to: What does the above equation mean?

It can be assumed that if a sum satisfies the above equation, it can be proved that a person has. This assumption has a premise that if a person does not know X, then he cannot provide and satisfy the above equation.

Discuss this premise in detail: if a person doesn't know X and wants to calculate the sum, can he do it? The conclusion is no, first of all, we can't calculate (in a limited time).

One more question: Can you calculate any information about the given sum?

According to the formula: solve it.

If you want to calculate X, you need to know R, but if R is not public, is there any way to calculate R? We know that r = r * p；; But according to this formula, R (the mathematical problem just introduced) cannot be reversed, so X is also safe.

At this point, the second advantage of the algorithm can be proved.