Technology Popularization|Application of state secret algorithm in Ultrain blockchain

Cryptography is the basis of blockchain, and a lot of cryptography algorithms are used in blockchain, including symmetric encryption, asymmetric encryption, one-way hash algorithm, digital signature and other technologies.

In order to realize the independent control of cryptography technology, China has also defined its own national Cryptography Standards. In the “financial distributed ledger technology security specification” issued by the central bank in 2020, it is clearly required that domestic blockchain technology must support national cryptography algorithm. Ultrain blockchain has now completed the support for the national secret algorithm, which meets all the requirements of the central bank’s security specifications.

This paper first introduces the basic concepts of symmetric encryption, asymmetric encryption and digital signature, then focuses on the elliptic curve cryptography technology in the asymmetric encryption algorithm, and finally expounds the application of the national encryption algorithm in the Ultrain blockchain. To solve the problem of poor signature verification performance of OpenSSL, Ultrain optimizes the implementation of the algorithm and achieves a performance improvement of 3–4 times. The relevant optimization code has been submitted to OpenSSL GitHub

( https://github.com/openssl/openssl/issues/11992 ）。

01 Symmetric encryption and asymmetric encryption

Symmetric cryptography is a way of using the same key when encrypting and decrypting. Symmetric key has many aliases, such as public key password, traditional password, private key password, shared key password and so on. Figure 1 and Figure 2 are symmetric cipher encryption and decryption processes respectively. Encryption and decryption use the same key, so they are called symmetric encryption.

1.2 asymmetric encryption

Asymmetric cryptography uses different keys when encrypting and decrypting, which is also called public key cryptography. They are usually a pair of keys: public key and private key. After the public key is encrypted, the private key can be decrypted; after the private key is encrypted, the public key can be decrypted. The public key is derived from the private key, and the public key is public. Asymmetric encryption solves the problem of key distribution in symmetric encryption. The general public key is used for encryption and the private key for decryption. When the private key is used for encryption, it is digital signature in essence, that is, decryption with the public key can verify that the information is indeed the result of private key encryption. At present, public key cryptography mainly includes the following:

RSA (the first letter of the surnames of Ron Rivest, ADI Shamir and Leonard Adleman). This algorithm uses the difficulty of large prime factor decomposition.

EIGamal, designed by Taher EIGamal, is different from RSA in that it is difficult to find the discrete logarithm under mod n.

Rabin, a public key algorithm designed by m.o.rabin. The difficulty of Rabin’s way to find the square root

Elliptic curve cryptography (ECC),

Today we focus on the cryptography algorithm, which is realized by special multiplication of specific points on the elliptic curve. It takes advantage of the fact that the inverse operation of this multiplication algorithm is very difficult.

Public key algorithm is slower than symmetric encryption algorithm, so symmetric encryption algorithm is used in data encryption, while public key algorithm is more used in digital signature scenarios.

1.3 digital signature

One day Alice sent an email to Bob: “Hi, Bob, give me 1000000 yuan, account number is 6214 6576 8789 8987, account name is Alice”. In real life, Bob may call Alice to confirm whether the e-mail is forged or not, and to confirm whether the content has been tampered with, so as to prevent the collection account and amount from being maliciously modified. Of course, there is another scenario, Bob calls Alice and Alice denies sending the e-mail at last.

The technology that can prevent the forgery, tampering and denial mentioned above is the digital signature mentioned above. Generally, the message is long. We only sign the hash value of the message, so the process of Alice sending the message is as follows:

1. Alice uses one-way hash function to calculate the hash value of mail content;

2. Alice encrypts the hash value with the private key, and the ciphertext obtained is Alice’s signature of the hash value. Since only Alice holds her private key, no one else can generate the same ciphertext except Alice himself, and the signed out signature Alice can’t deny;

3. Alice sends the message and signature to Bob;

4. Bob uses Alice’s public key to decrypt the received signature to the hash value;

5. Bob compares the hash value obtained in 4 with the hash value of the message sent directly by Alice. If the two are the same, the signature verification succeeds, otherwise the verification fails.

02 Detailed explanation of elliptic curve encryption algorithm

We have understood the basic concepts of symmetric encryption and asymmetric encryption. In this section, we mainly talk about the elliptic curve technology in the asymmetric encryption algorithm for digital signature.

2.1 basic concepts

2.1.1 Abelian group

In mathematics, a group is an algebraic structure, which consists of a set and a binary operation + and satisfies the following conditions:

1. Closeness. The result of binary operation of two numbers in the set is still in the set.

2. Combination. a+b+c = a+(b+c)

3. Unit: yuan. There is unit element 0, so a + 0 = 0 + a = a

4. Inverse element. For any a, there must be B to make a + B = 0

5. Exchange law. a+b+c = a+c+b

2.1.2 elliptic curve equation

In cryptography, the elliptic curve equation defined in the prime field GFP is:

E: Y2 = X3 + ax + b where a, B ∈ GFP and (4A3 + 27b2) mod p! = 0

In addition to the curves defined b y p, a and B, x, y and N are usually needed to determine an elliptic curve. So, to describe a n elliptic curve over a finite field, there are six variables: T = (P, a, B, x, y, n)

P — the number of points in the prime field, the greater P is, the more secure it is, but with the increase of computation

a. B — curve coefficient

x. X, y coordinate of Y — G point

N — is prime number, and is the order of G point. There is a minimum positive integer at a point P on the elliptic curve, so that NP = 0 ∞ (origin or infinity, the following infinity is represented by 0), then n is called the order of p; if n does not exist, we say P is infinite. In prime field, the order of all points of elliptic curve exists.

2.1.3 point operation on elliptic curve

The points on elliptic curves in prime field are also abelian groups. The unit element is zero at infinity. The inverse element of point P on an elliptic curve is its X-axis symmetric point.

P and Q are the two points of the elliptic curve on the prime field GFP respectively. Their lines intersect the elliptic curve at the third point R (see case 1 in Figure 5), and there are infinite points P + Q + r = 0. There are several special cases, 2, 3 and 4 in the figure below. In the second case, the straight line is tangent to Q, which can be seen as Q and Q are connected, intersecting the elliptic curve at P point, that is, q + Q + P = 0; in the third case, P and Q are parallel to y axis, because the two parallel lines intersect at infinity, P + Q + 0 = 0; in the fourth case, P and P are connected, intersecting at infinity.

Based on the above, we have the following conclusions:

Q + Q + P = 0, that is, q + q = — P, (Q + Q) + (Q + Q) = (- P) + (- P), that is, taking P’s symmetric point-p as the tangent, and so on, we can quickly get 2n * q points, n ∈ [0, + ∞). In elliptic curve encryption, the private key is a large integer, and the public key is the product of point G on the elliptic curve and the private key. We can quickly calculate the public key through the binary representation of the private key.

2.2 algorithm application

Elliptic curve is mainly used for digital signature. The following is the mathematical calculation process to realize digital signature and signature verification.

2.2.1 digital signature and signature verification

Digital signature mainly needs hash value (Digest) H and private key Ka of message M to generate the final result {R, s}; signature verification mainly uses public key p and message digest H. The following is the calculation process of signature generation and signature verification.

Generating signature, that is, the process of calculating R and S

The private key is a large number Ka, and the public key is the point where the private key multiplies the G point, P = kag

The random number k is generated. The product of the calculation and the base point k = kg. The x-axis coordinate KX of the k-point is r to the module KX (MOD n) of the order n of the elliptic curve, that is, r = KX (MOD n)

Calculation of k-1 (MOD n) based on the order of curve

R has been generated in step 2, s = k-1 (H + Kar) (MOD n)

Signature verification

Calculating s based on the inverse S-1 of the order n of elliptic curve

Calculate U1 = HS-1

Calculate U2 = RS-1

Calculation point q = u1g + U2 * P

Take the x-axis coordinate QX of point Q, if QX is equal to R, that is, the x-axis coordinate KX of point K in the signature process, then the verification is passed.

Why does proof have this feature in the signature verification process?

According to the signature calculation, s = k-1 (H + Kar) (MOD n), SK = (H + Kar) (MOD n) is multiplied by K on both sides.

Point q = u1g + U2 * P, P = kag, q = u1g + u2kag

Substituting U1 and U2 into q = h s-1g + rs-1kag = (H + RKA) s-1g

Substituting the formula of step 1 into step 3, q = SK * s-1g = kg, so if {R, s}, h is correct, point K and point P have the same X-axis coordinates

2.2.2 comparative advantages of elliptic curve and RSA Technology

We have talked about asymmetric RSA before. It is recommended to use elliptic curve encryption by national secret because elliptic curve has some advantages over RSA:

More secure. The elliptic curve is based on the discrete logarithm difficulty, and the computational complexity is exponential, so it is difficult to solve. However, RSA algorithm is difficult to decompose large prime factors, and the computational complexity is sub exponential.

A shorter key. Under the same security level, the key length of ECC is much smaller than that of other public key algorithms. 128bit elliptic curve algorithm has the same security level as 1024bit RSA algorithm.

2.3 common elliptic curves

In bitcoin and Ethereum networks, secp256k1 is used. P is a 256 bit prime number, and K represents Koblitz. a=0，b=7。 The curve equation is y2 = X3 + 7. Koblitz elliptic curve has some special properties, which can realize group operation more effectively.

Secp256r1. Sister curve of secp256k1. P is also a 256 bit prime number, but the value is different from secp256k1 curve, and R represents random. “Random” selection of parameters is safer, however, some suspect that random coefficients may have been chosen to provide backdoor. Therefore, bitcoin network did not choose it, but chose a more efficient secp256k1.

SM2 curve. SM2 is a standard curve recommended by China on the basis of previous studies on ECC. GB / T 35276–2017 defines the specific implementation of SM2 algorithm.

03 Application of state secret algorithm in Ultrain

In addition to SM2 elliptic curve, SM3 and SM4 are also applied in the support of ultrain blockchain to national secret algorithm.

SM3 hash algorithm generates 256bit hash value, which is mainly used to replace sha256 algorithm.

SM4 symmetric encryption algorithm, ultrain wallet public private key encryption replaced aes128 with SM4.

3.1 implementation details of national secret algorithm

We have explained the principle of elliptic curve above, and SM2 curve is also built on it, but it also has its own characteristics:

3.1.1 calculation of H value in Sm2

In secp256k1, h is the hash value of the message, while in SM2, it is more complex to calculate H value, which needs to be calculated in two steps:

1. Calculate Z value through SM3 algorithm:

Z=SM3(ENTL||ID||a||b||xG||yG||xA||yA)

ID: string of user identity flag

Entl: bit length of ID represented by two bytes

a. B: curve parameters

XG, YG: coordinate of G point x, Y axis

Xa, ya: public key coordinates x, Y axis

2. Use Z and the message to be signed to calculate the hash value H through SM3, H = SM3 (z|m)

3.2 state secret algorithm optimization

3.2.1 OpenSSL SM2 curve performance problems

We develop the implementation of SM2 based on OpenSSL, but we find that the speed of signature and verification is very slow. On MacBook Pro, we sign 22496 times every 10 seconds and check 24374 times every 10 seconds. Locate to EC_ POINT_ Mul is slow. Check the source code of OpenSSL. It does not pre cache the 2n * g, n ∈ [0, 256] (the private key is 256 bit long). For example, if the binary value of the private key is 1000 1100, it is 27 * G + 23 * G + 22 * g for the public key, while 2 * g, 22 * g, 23 * g… 2256 * g are all known, so only the + operation of three points on the elliptic curve is needed, and it does not need to be recalculated every time. In addition, some core functions need to be compiled by assembly, and the performance after optimization can be improved by 3–4 times, as shown in the following table.

3.2.2 SM2 signature and message cannot recover public key

In secp256k1, we can recover the public key according to the signature {R, s} and the message, but SM2 can’t recover the public key through the signature and the message, because in the process of calculating the H value of SM2, we use the coordinates of the public key, so we must know the public key, which is in conflict with only the signature and the message recovery public key. Because SM2 cannot pass the signature and message recover public key, we take out the public key and verify it in the process of transaction verification. However, in our system, an account can have several public keys, so it is necessary to traverse the account’s public key to verify the transaction, resulting in the lower transaction performance of multiple public key accounts. Fortunately, 99% of all accounts in the system have only one pair of public and private keys, so it will not affect the overall performance of the system in theory.

04 Conclusion

This paper first introduces the basic concepts of symmetric encryption and asymmetric encryption, then introduces the elliptic curve encryption technology in the asymmetric encryption technology in detail, and finally describes the support of ultrain blockchain to the national encryption algorithm. The understanding of the elliptic curve encryption part requires a higher mathematical basis. The decentralized trust of blockchain is based on cryptography, and cryptography technology is based on mathematics, so in math we trust.

reference:

[1]. https://encyclopedia.thefreedictionary.com/elliptic+curve