To understand the ECC elliptic curve encryption algorithm, we must follow the clues and solve the following principles all the way.
So I got this curve:
The encryption and decryption process of this equation will not be explained. There are a lot of online materials and books on cryptography.
Its principle is based on the addition algorithm on the projective plane, and its forward process is simple and easy, while the reverse process of addition is more difficult. We can use the analogy of playing billiards to determine the initial position of a ball as p 1, hit p 1 n times (assuming that the strength and direction of n hits are the same), and finally get the position as p2. Given p 1 and n, it is easy to get p2, and it is enough to play the ball n times. However, if p 1 and p2 are known, it is very difficult to deduce n reversely. Everyone understands this truth. The irreversibility of the addition of elliptic curves on the projective plane is similar to the billiards game above.
The ECC curve used for encryption, decryption and signature is determined by the following parameters: (p, a, b, g, n, h). P is the integer range of a finite field, A and B determine the shape of the curve, G is the initial point selected on the curve, N is the number of times used for addition, and H is the cofactor. I don't know why it is used, so it is usually 1.
The Secp256k 1 curve parameters used by Bitcoin are as follows:
p =? 2^256 ? 2^32 ? 2^9 ? 2^8 ? 2^7 ? 2^6 ? 2^4 ? 1 =? 2^256? – 2^32? – 977
a =? 0
b = 7
This is a curve chosen by Satoshi Nakamoto, not a popular curve. Remove the modular operation and simply express it as? y^2 = x^3 + 7 .
In Secp256k 1, "sec" stands for the standard of efficient cryptography, "p" stands for the finite field parameter p, 256 stands for the number of bits of p, and "k" is of great significance.
"K" stands for Koblitz, which is the name of Koblitz, the inventor of elliptic curve encryption algorithm. Here refers to a curve, the parameters of which are deliberately selected. For example, A and B, a 0 and a 7 above are all deliberately chosen.
1 after k stands for serial number.
The one corresponding to "K" is called "R", and the so-called R refers to Random, which means random number. Everyone will understand that the parameters used in the curve are randomly selected. For example, the parameters of Secp256r 1 are as follows:
p =? 2^224(2^32 ? 1) + 2^ 192 + 2^96 ? 1
a =? 1 157920892 10356248762697446949407573530086 1434 152903 14 19553363 1308867097853948
b =? 4 1058363725 152 142 129326 129780047268409 1 1444 10 159937255548352563 1403946740 129 1
Secp256r 1 also has a name, NIST P256. NIST is the National Institute of Standards and Technology, that is, the National Committee of Standards and Technology, which belongs to the Ministry of Commerce and specializes in formulating technical standards for government agencies. So Secp256r 1 is a technology that shines with the official aura. This standard was issued by NIST on 1999.
Since the parameters P, A and B are randomly selected, it should be safer. In theory, it is, but the word "random" is not so easy. It's not that the upper lip touches the lower lip to give a random number. Random numbers in computers have always been a difficult problem. ?
The random number generation of Secp256r 1 is realized by hashing algorithm SHA 1. When a string is hashed by SHA 1 algorithm, a very random number can be generated every time. And then what? The character string of SHA 1 corresponding to P, A and B of Secp256r 1 is C49D360886E704936A 678E139D26B67819F7E90.
The suspicion of cryptography and cryptography application technology industry arises from this: why did NIST choose this string?
As we all know, NIST can't calculate the seed string of SHA 1 according to the given curve.
Therefore, people suspect that NIST may have tested countless seed strings and finally chose a weaker curve. This is a violent choice. It is said that NIST has tested 654.38+0 billion curves. 20 14 cryptographer? Daniel J. Bernstein 1 and Tung Chou published the article "How to Manipulate Curve Standards: White Paper with Black Hat" to introduce how to manipulate the formulation of ECC curve standards.
Although there is no empirical evidence that everyone is worried about, this is not the first time NIST tampered with elliptic curves. Last time there was real hammer evidence. In 2007, NIST issued a technical standard document with a page of 130: NIST Special Issue 800-90, which introduced the "deterministic random bit generator", that is, the technology of generating random numbers, which is similar to SHA 1 mentioned above. Among the technologies introduced, one is called? Dual_EC_DRBG, that is, the technology of generating random numbers by double elliptic curves. The technical principle is similar to adding elliptic curve encryption.
Compared with billiards, in order to generate random numbers, two billiard balls are placed at p 1 and p2 respectively on the huge "limited field" billiards table. Hit the first billiards at p 1 n times, where n is the secret number, and get the position p 1', which is the generated random number. After that, p2 also struck N times to obtain the position p2', and P2' was used instead of N as the secret number of the next generation random number. Finally, put p 1 and p2 back to their original positions and wait for the next time.
In principle, it is no problem for this algorithm to generate random numbers. Compared with other random number generation algorithms, the efficiency is slow. Some cryptographers put forward this problem, and the efficiency of this algorithm is an order of magnitude higher than that of other algorithms in this standard, slow three.
Strangely, Dual_EC_DRBG was recommended by NSA to NIST and received strong support. Who is NSA? As we all know, the National Security Agency (NSA) is a powerful department that has struggled with American folk cryptography for many years.
In 2007, at the awesome CRYPTO Conference, a cryptographer? Dan Shumow and Niels Ferguson pointed out that Dual_EC_DRBG is not only slow, but also has a back door. The algorithm specified by NIST may be fine, but the initial positions of P 1 and P2 are problematic: these two parameters are related and can be calculated.
This really hit NIST and the National Security Agency in the face. Of course, cryptographers have no conclusive evidence, whether it is a malicious design by NIST and the National Security Agency, or a private evil by researchers working for them.
Until the 20 13 prism door broke out, the government documents disclosed by Snowden showed that NSA deliberately implanted a back door in the encryption algorithm. Later, Reuters revealed that NSA bought RSA to implant its software? Dual_EC_DRBG, in order to crack the encryption technology, eavesdrop on Internet information. Everything is exposed. This is the ghost of cooperation between the National Security Bureau and NIST.
Secp256r 1 was abandoned in bitcoin, and Secp256k 1 was selected, while Satoshi Nakamoto developed bitcoin software before 2008. So it should be 2007? At the password conference, right? The censure of Dual_EC_DRBG aroused Satoshi Nakamoto's vigilance. At that time, the Prism Gate had not yet erupted, and there was no evidence of malicious manipulation by NSA.
Institutions do evil, people are helpless, no one blushes, and no one is responsible. Put a back door, let it go, and everyone will hide.