If you’ve been around blockchain, you’ve probably heard of elliptic curve signature algorithms. This algorithm is the cornerstone of blockchain technology. However, this algorithm is very abstract and difficult to understand. This article will introduce this algorithm in a simple and easy way, and try not to involve a large number of formulas. Many of the mathematical proofs will be directly ignored, and we will directly use the results of the proofs.
1. Symmetric encryption and asymmetric encryption
Symmetric encryption and asymmetric encryption are two main encryption algorithms. Symmetric encryption, for example, the AES encryption algorithm, is relatively efficient because both parties need to know the same key and use the same key for encryption and decryption.
But there is a problem with symmetric encryption. Key transfer is a big problem. If someone intercepts the key transferred over the network, the encrypted data is not secure.
To solve this problem, we need to use asymmetric encryption algorithms. Asymmetric encryption is divided into public key and private key. The public key can be released, and anyone can get your public key and use it to encrypt the encrypted data. Only the private key in your hand can decrypt the encrypted data. So everyone can just release their public key, and someone else can send you data securely.
And there is also a problem of asymmetric encryption than symmetric encryption, efficiency will be much lower, if the asymmetric encryption is used for network traffic environment, has a great influence on performance, so in the course of practical use, are often used in combination, these two kinds of algorithm such as HTTPS connection is established by asymmetric encryption, transmission of the symmetric encryption key, Subsequent data transfers use symmetric encryption algorithms.
And asymmetric encryption algorithms also have a nice use for signatures. If a piece of data is signed with a private key, someone can use the public key to quickly check whether the signature is valid, which is one of the foundations of blockchain technology.
Note here: using a public key is called encrypting data, and using a private key is called signing.
RSA and Elliptic Curve Cryptography (ECC) are two well-known asymmetric encryption algorithms. RSA uses the principle of prime number decomposition to achieve security. However, RSA has increasingly high requirements on the key length, which also causes a large amount of calculation, while ECC uses a much shorter key length with stronger security.
The Elliptic Curve Digital Signature Algorithm (ECDSA) described in this paper is a Signature Algorithm based on ECC, which is widely used in asymmetric encryption scenarios such as blockchain and HTTPS.
2. Elliptic curve algorithm
2.1 Representation of elliptic curves
An elliptic curve is actually a mathematical equation, usually expressed by the following equation:
If a and B take different values, then the corresponding curve shape will be different:
The above curves correspond to b=1b =1b =1 and aaa ranges from 2 to -3.
In the above equation, XXX must be an integer, not a floating-point number. In addition to the modular operation based on PPP, the value of y2y^2y2 is between 0 and ppP-1. Since XXX can only be an integer, the number of points that can be obtained is also limited, denoted as NNN.
That’s all we know about elliptic curves.
2.2 Operation of elliptic curve
A sign algorithm using a multi to sign an elliptic curve can be used if the algorithm is to run properly. If it is to sign an elliptic curve then it needs to run two operations, Point Addition and Point Multiplication.
So let’s say I have an elliptic curve that looks like this. Draw a line that intersects the curve at three points: P,Q,RP, Q,RP,Q,R. According to the definition of point addition, P+Q+R=0P +Q+R=0P +Q+R=0, then P+Q=−RP +Q= -rp +Q=−R, − R-r −R is defined as a point obtained with respect to the axis symmetry of XXX, as shown in the figure above, which is the definition of point addition.
If we move this line so that P,QP,QP,Q coincide:
$$PPP point and nPnPnP point can be connected, 3P,4P… 3P,4P… 3P,4P… (n + 1) P (n + 1) P (n + 1) point P. The dot product is defined as k×Pk \times Pk×P, which means the sum of KKK PPP points.
2.3 One-way trap door function
The definition and operation of elliptic curve are described above. Finally, the security of elliptic curve is discussed. For asymmetric encryption, the key point is that you cannot infer the private key from the encrypted data and the public key.
So above we have the definition of the dot product, that any point RRR can be computed by the dot product formula R=k×PR =k \times PR=k×P. The point here is that even if we know PPP and RRR, we can’t compute KKK, there’s no subtraction or division in the elliptic curve algorithm. This is the basis of the security of the elliptic curve algorithm, which is also called the one-way trap gate function.
This integer KKK is usually the private key in the algorithm, and R corresponds to the public key.
3. Elliptic curve signature algorithm
The characteristics of elliptic curves have been introduced above. Now let’s look at how the elliptic curve signature algorithm uses the characteristics of elliptic curves to complete signature generation and signature verification.
Before using the signature algorithm, we need to determine an elliptic curve. According to the above, if the parameters are chosen differently, the equation of the elliptic curve will be different. Where GGG is a selected initial point from which all subsequent operations will start.
Then define a pair of public and private keys. According to the above definition, P= K ×GP =k \times GP= K ×G, where KKK is a random integer corresponding to the private key K0K0K0, PPP represents a point on the elliptic curve corresponding to the public key P0P0P0.
3.1 Generating Signatures
After producing the public and private keys, you can use the following steps to generate the signature:
- Generate a random number k1k1k1. Note that this random number is not the private key generated above
- Calculate point P1P1P1 using P=k1×GP =k1 \times GP=k1×G. Note that this is not the public key above
- The x coordinate of p1, p1, p1 is RRR
- Computes HHH for the data to be signed
- Calculate S=k1−1(H+k0×R)modpS =k1 ^{-1}(H +k0 \times R)\quad mod \quad pS=k1−1(H+k0×R)modp
Generally, the length of a signature is 40 bytes. The first 20 bytes are R, and the last 20 bytes are S. When R and S are combined, the final DCSDA signature is created.
3.2 Verifying signatures
Verifying the signature is easier by using the following formula:
P0P0P0 is a public key, and PPP can be easily calculated by using this formula. After PPP is obtained, if PPP’s XXX coordinate is equal to RRR, then the verification succeeds. In the verification process, no private key is required.
In the above algorithm, it can be found that, in addition to the private key K0K0K0 in the signer’s hand, a random number K1k1K1 will be generated during the signing process. This random number is very important. If this number is not random enough, or a fixed number is used, So the k1k1k1 can be calculated from the HHH and H’H ‘h ‘HSS and S’s’.
If K1K1K1 knows, it can use the formula above to generate SSS to calculate the private key K0K0K0. In this way, the private key is leaked. In 2010, a random number k1k1K1 always returned a fixed number, resulting in a security hole on SONY’s PS3.
4. Summary
Compared with RSA algorithm, elliptic curve signature algorithm is more secure and uses shorter key bits. It has been used in many fields, HTTPS, blockchain. The security of this algorithm comes from the one-way trap door function, ** can not reverse the calculation of the private key, which is the most ingenious part of this algorithm.
The text/Rayjun
[1] en.wikipedia.org/wiki/Ellipt…
[2] www.instructables.com/Understandi…
[3] Andrea. Corbellini. Name / 2015/05/17 /…