Summary of a.

Because international algorithms such as RSA and AES face the risk of high-intensity algorithm prohibition and backdoor deployment, China has developed a set of security algorithms SM2/SM3/SM4/SM9 based on ECC elliptic curves. According to the overall strategy of the country, the replacement of the state secret algorithm will be gradually realized in finance and important fields. In addition, according to the overall plan of the People’s Bank of China, the state secret algorithm will be fully applied in the financial industry in 2022.

In the FireFly mobile finance development platform, the encryption and decryption algorithm package supporting the national secret algorithm is provided. In order to better use and promote the state secret algorithm, the encryption principle of ECC elliptic curve is analyzed below.


2. Principle of elliptic curve algorithm

Elliptic Curve Cryptography is a public key Cryptography technology based on Elliptic Curve theory. The encryption, decryption and digital signature are realized by using the discrete logarithmic difficulty of Abelian groups formed by points of elliptic curves over finite fields. The addition operation in elliptic curve corresponds to the modular multiplication operation in discrete logarithm, and the corresponding cryptosystem based on elliptic curve can be established.



Three. Elliptic curve algorithm advantage



1. More suitable for mobile Internet

With the same encryption security, the ECC key length is 163 bits, while the RSA key length is 1024 bits. The ECC encryption algorithm has a short key length, which means less storage space, lower CPU overhead and less bandwidth. As more and more users use mobile devices to complete various online activities, ECC encryption algorithms provide better customer experience for mobile Internet security.


2. Better security

ECC encryption algorithm provides stronger protection than other encryption algorithms can better prevent attacks, make your website and infrastructure more secure than using traditional encryption methods, provide better guarantee for mobile Internet security.


3. Better performance

ECC encryption algorithms require shorter key lengths to provide better security.



Theoretical basis of elliptic curve

Definition 1.

An elliptic curve satisfies an equation on the projective plane

Y2Z + a1XYZ + a3Yz2 = X3+ a2X2Z + a4XZ2 + a5Z3

The set of all points, and every point on the curve is nonsingular (or smooth).


  • The Weierstrass equation is a homogeneous equation.

  • The shape of an elliptic curve is not elliptical. It’s just that the descriptive equation for an elliptic curve is similar to the equation for calculating the circumference of an ellipse, hence the name. Here is the shape of an elliptic curve:


  • The definition of an elliptic curve tells us that an elliptic curve is smooth, so ordinary points on an elliptic curve have tangent lines.


2. Addition on elliptic curves

① Algorithm

Arbitrarily take two points P and Q on the elliptic curve (if P and Q coincide, make the tangent line of point P) and make a straight line crossing at another point R ‘on the elliptic curve, and make a parallel line crossing the Y-axis through R’ crossing at R. Let’s say P plus Q is equal to R. (as shown in figure)


② Detailed explanation of the algorithm

  • Here + is the addition abstracted from ordinary addition, which has some properties of ordinary addition, but the specific operation rules are obviously different from ordinary addition.


  • The sum of k identical points P, let’s call it kP. The figure is as follows: P+P+P = 2P+P = 3P, where 3P is three times the point P.


3. Elliptic curves over finite fields

(1) finite field

The elliptic curve mentioned above is defined in the field of real numbers. Real numbers are continuous, which leads to the continuity of elliptic curves, but it is not suitable for encryption. Therefore, elliptic curves must be transformed into discrete points, and elliptic curves must be defined over a finite field (as the name implies, a field consisting of only a finite number of elements).

Next, we give a finite field Fp, which has a finite number of elements.

Fp has only p (p is prime) elements 0,1,2… P – 2, p – 1;

The addition (a+b) rule for Fp is a+b≡c (mod P); That is, the remainder of (a+b)÷p is the same as that of C ÷p.

The multiplication (a×b) rule for Fp is a×b≡c (mod P);

The division of Fp (A ÷b) is a/ B ≡c (mod P); A × B-1 ≡ C (mod P); (B-1 is also an integer between 0 and p-1, but satisfies b× B-1 ≡1 (mod p);

The identity element of Fp is 1, and the zero element is 0.


(2) Encryptable elliptic curves

Also, not all elliptic curves are suitable for encryption. Y2 = x3 + ax + b is the simplest kind of elliptic curve that can be used to encrypt. Let’s define the curve y2 = x3 + ax + b as Fp:

Select two non-negative integers a and b less than p(p is prime) that satisfy the following conditions

4a3 + 27b2 ≠ 0 (mod p)

Then all points (x,y) satisfying the following equation, plus O infinity, form an elliptic curve.

y2 = x3 + ax + b(mod p)

Where x and y are integers between 0 and p-1, and this elliptic curve is denoted Ep(a,b).

Example: View the image of y2 = x3 + x + 1 (mod 23)


The elliptic curve, then, is a discrete point, and the elliptic curve looks different in different number domains, but it’s still essentially an elliptic curve.


③ Calculate the coordinates of points on an elliptic curve

The elliptic curve on Fp also has addition. According to the addition rule, the coordinates of points on the elliptic curve can be calculated.

Given point P(x1, y1), Q(x2,y2), calculated point R(x3, y3) :

X3 ≡ K2 — x1 — y1 (mod P)

Y3 ≡ K (x1 — x3) — y1 (mod P)

If P≠Q and PQR is collinear at three points, its slope k=(y2 — y1)/(x2 — x1).

Where, if P=Q, PR is the elliptic tangent through point P, and its slope k=(3×12+ a) / 2y1


The order of points on an elliptic curve

If the smallest positive integer n exists at a point P on the elliptic curve such that the number times nP=O infinity, then n is called the order of P. If n does not exist, we say that P is of infinite order. In fact, order N exists at all points on an elliptic curve defined over a finite field.



Five. The principle of elliptic curve encryption and decryption

1. Basis of encryption and decryption

Public-key algorithms are always based on a mathematical puzzle. RSA, for example, relies on the fact that given two prime numbers P and q are easy to multiply to produce n, whereas factoring n is relatively difficult. So what’s the problem with elliptic curves?

Consider the following equation:

K=kG [where K,G are points on Ep(a,b) and K is an integer less than n (n is the order of point G)]

Given k and G, it’s easy to calculate k by the rule of addition; But given K and G, it’s harder to find K. This is the problem of elliptic curve encryption algorithm.

We call G the base point, k (k<n, where n is the order of G) the private key, and k the public key.

K = 2, k is twice the point of G;

K = 3, k is 3 times the point of G;

K = 4, k is 4 times the point of G;

.

If K is given a multiple of G on an elliptic curve, how can we calculate how many times K is G? Intuitively, it is easy to calculate a multiple point forward, and much harder to calculate a multiple point K of G backwards. Therefore, multiple K is used as private key and public key in elliptic curve algorithm.


2. Encryption and decryption process

Now we describe a process for encrypted communication using elliptic curves:

  1. User A selects an elliptic curve, Ep(A, B), and takes A point on the elliptic curve as base point G.

  2. User A selects A private key k and generates A public key k =kG.

  3. User A passes Ep(A, B) and points K and G to user B.

  4. After receiving the message, user B encodes the plaintext to be transmitted to the point M on Ep(a, B) (there are many encoding methods, which will not be discussed here) and generates a random integer r (r<n).

  5. User B’s calculation point C1=M+rK; C2 = rG.

  6. User B sends C1 and C2 to user A.

  7. User A receives the message and computes C1-kC2, resulting in point M. because

C1-kC2=M+rK-k(rG)=M+rK-r(kG)=M

And then you decode the point M and you get the plaintext.

In this encrypted communication, if there is a voyeur H, he can only see Ep(a, B), K, G, C1, C2 and finding K through K and G or r through C2 and G is relatively difficult. Therefore, H cannot obtain the plaintext information transmitted between A and B.


3. Encryption and decryption parameters

In cryptography, six parameters are used to describe an elliptic curve on Fp:

T = (p, a, b, G, n, h).

P, A, and b are used to determine an elliptic curve,

G is the base,

N is the order of point G,

H is the number of points on an elliptic curve divided by m and n.

The selection of these parameters directly affects the encryption security. Parameter values must meet the following conditions:

  1. Of course, the larger p is, the safer it will be, but the larger p is, the slower the calculation speed will be, and about 200 bits can meet the general safety requirements;

  2. P indicates n * h;

  3. Pt ≠1 (mod n), 1≤t<20;

  4. 4A3 + 27B2 ≠ 0 (mod p);

  5. N is prime;

  6. H 4 or less.



Principles of Elliptic Curve Digital Signature (ECDSA)

1. An overview of the

Elliptic Curve Digital Signature Algorithm (ECDSA) is a simulation of digital signature algorithm (DSA) using elliptic curve cryptography (ECC).

ECDSA is the combination of ECC and DSA, and the whole signature process is similar to DSA, except that the algorithm adopted in signature is ECC, and the final value of signature is also divided into R and S.


2. Signature process

  1. Choose an elliptic curve, Ep(a,b), and base point G;

  2. Select the private key k (k<n, n is the order of G), and calculate the public key K=kG by base point G.

  3. Generate a random integer r (r<n), calculate point r =rG;

  4. Taking the original data and the coordinate values of point R x and y as parameters, compute SHA1 as a hash, that is, hash =SHA1(original data,x,y);

  5. Compute S ≡ r-hash * k (mod n);

  6. R and s are the signature values. If either r or S is 0, perform step 3 again.


3. Visa inspection process

After receiving the message (m) and signature value (r,s), the receiving party performs the following operations:

  1. Calculation: sG+H(m)P=(x1,y1), R1 ≡x1 mod P.

  2. Verify the equation: R1 ≡r mod p

  3. If the equation holds, the signature is accepted, otherwise the signature is invalid.



Application of elliptic curve algorithm

Elliptic cryptography is widely used in TLS, openPGP and SSH, as well as in Bitcoin and other cryptocurrencies. In addition, the SM2 algorithm promoted in China is also based on elliptic curve algorithm. SM2 and TLS are used as an example.

1. SM2

(1) overview

SM2 algorithm and RSA algorithm are both public key cryptography algorithms. With the development of cryptography technology and computing technology, the common 1024 bit RSA algorithm is facing serious security threats. Our national cryptography management department decided to replace RSA algorithm with SM2 elliptic curve algorithm after research. SM2 algorithm has advantages in both security and performance. See Table 1 algorithm breach time and Table 2 algorithm performance.


RSA Key Strength

Elliptic curve key strength

If breached

512

106

Has been breached

768

132

Has been breached

1024

160

2048

210

Table 1 Algorithm break time


algorithm

Signature speed (times per second)

Inspection speed (times/second)

A 1024 – bit RSA

2792

51224

A 2048 – bit RSA

455

15122

A 256 – bit SM2

4095

871

Table 2 Algorithm performance


② The relationship between SM2 and elliptic curve algorithm

The elliptic curve equation adopted by SM2 algorithm is: y2= x3+ AX + b. In SM2 algorithm standard, the only standard curve is determined by specifying a and B coefficients. At the same time, in order to map curves to encryption algorithms, other parameters are identified in the SM2 standard for use by algorithmic programs.


③ SM2 encryption and decryption process

The following symbols are used in the SM2 encryption and decryption process:

A, B Two users of the public key cryptosystem.

DB User B’s private key.

E(Fq) the set of all rational points (including O at infinity) of the elliptic curve E on Fq.

Fq is a finite field containing q elements.

G is a basis point of an elliptic curve whose order is prime.

Hash() Password Hash algorithm.

Hv() cryptographic hashing algorithm with message digest length of V bits.

KDF() key derivation function.

H cofactor, h=#E(Fq)/n, where n is the order of basis point G.

M Indicates the message to be encrypted.

M ‘Decrypts the received message.

Order n basis G (n is the prime factor of #E(Fq)).

O A special point on an elliptic curve, called infinity or zero, is the identity element of the additive group of elliptic curves.

PB Public key of user B.

Q The number of elements in the finite field Fq.

A, B, Fq, they define an elliptic curve E over Fq.

The joining together of x | | y x and y, x, y is a bit string or byte string.

[k]P K times the point P on an elliptic curve.

The number of points on E(Fq) is called the order of the elliptic curve E(Fq).

M radius t xor operation


A. Encryption algorithm flow

SM2 encryption is encrypted using a public key. The public key consists of a curvilinear coordinate point. The public key in x.509 certificate is represented as two 32-byte BigInteger starting with the 04 mark, that is, the curvilinear point P (X,y). The SM2 public key encryption algorithm is more complex than RSA. The encryption result consists of three parts. SM2 uses random numbers to encrypt the same plaintext data.

Let the message to be sent be the bit string M and klen be the bit length of M.

In order to encrypt plaintext M, user A, as the encryptor, should perform the following operations:

A1: Use random number generator to generate random number K ∈[1, n-1];

A2: Calculate the elliptic curve point C1 = [k]G=(x1, y1) according to SM2 part 1 3.2.9 and 3.2.5 of the elliptic curve public Key cryptography algorithm

To convert the data type of C1 to a bit string;

A3: Calculate the elliptic curve point S= [h]PB, if S is infinite point, then error and exit;

A4: Calculate the elliptic curve point [k]PB=(x2, y2) as given in SM2 Elliptic curve Public Key Cryptography Part 1 3.2.6 and 3.2.5

Method, convert the data type of coordinates X2 and y2 into bit string;

A5: calculate t = KDF (x2 | | y2, klen), if t 0 bit string for the whole, it returns A1;

A6: Calculate C2=M⊕t;

A7: calculate the C3 = Hash (x2 | | M | | y2);

A8: output ciphertext C = C1 | | C3 | | C2.



According to the SM2 elliptic curve public key cryptography algorithm recommended by the state secret, firstly generate random numbers to calculate curve point C1, two BigInteger numbers of 32 bytes, which is the first part of SM2 encryption result. The second part is the real ciphertext, which is the result of the encryption of the plaintext, with the same length as the plaintext. Part 3 is the hash value, which is used to validate the data. According to the recommended 256-bit elliptic curve, the plaintext encryption result is 96 bytes larger than the original length.


B. Decryption algorithm flow

SM2 decryption algorithm is the reverse operation of encryption. Firstly, we need to extract the three parts of the encrypted result from the ciphertext, then calculate the M ‘plaintext value through the private key, and finally verify the data

Let klen be the bit length of C2 in ciphertext.

To cipher C = C1 | | C3 | | C2 decrypted, user B should implement the following as the decryption operation steps:

B1: Fetch bit string C1 from C, as given in SM2 Elliptic Curve Public Key Cryptography Part 1 3.2.4 and 3.2.10,

Convert the data type of C1 to the point on the elliptic curve to verify whether C1 satisfies the elliptic curve equation. If not, an error will be reported

And exit;

B2: Calculate the elliptic curve point S= [h]C1, if S is infinite point, then error and exit;

B3: Calculate [dB]C1= (x2, y2) according to the method given in part 1 of SM2 Elliptic curve Public Key Cryptography algorithm 3.2.6 and 3.2.5

The data type of coordinates X2 and y2 is converted to bit string.

B4: calculate t = KDF (x2 | | y2, klen), if t 0 bit string for the whole, the error and exit;

B5: Remove the bit string C2 from C and calculate M ‘=C2⊕t;

B6: calculate u = Hash (x2 | | M ‘| | y2), extracted from C bit string C3, if u indicates C3, error and exit;

B7: output plaintext M ‘.


SM2 decryption can also be implemented using soft algorithms. However, it involves private key calculation. To protect the security of the private key, you are advised to run it on hardware devices, such as storage media, such as UKey, to better protect key security. Take file encryption for example, first take UKey inside the encryption certificate encryption, this part can be completed in the application system. Decryption requires the UKey corresponding to the encryption certificate. The application system invokes the UKey decryption interface to complete data decryption in the physical hardware and is protected by the device PIN code.


(4) speed and length of SM2 algorithm

In short, SM2 has fast signature speed and slow signature check speed, which is opposite to RSA algorithm. See table 2 above. In addition, encryption and decryption speed and check speed.

SM2 supports 128 GB of data, and the encryption result increases by 96 bytes.

The SM2 signature algorithm has no limit on the length of the original data, and the signature result is 64 bytes.


2. TLS

(1) overview

HTTPS provides content encryption, identity authentication, and data integrity through the TLS layer and certificate mechanism. It effectively prevents data from being monitored or tampered with and defends against MITM (Middleman) attacks. During TLS encryption, asymmetric key exchange and symmetric content encryption algorithms are needed. Symmetric content encryption strength is very high, encryption and decryption speed is also very fast, but can not safely generate and keep the key. In TLS, application data is transmitted after symmetric encryption. Symmetric keys used in transmission are exchanged through asymmetric keys during handshake.


② Key exchange algorithm in TLS

The most commonly used key exchange algorithms are RSA and ECDHE. RSA has a long history and is widely supported, but Perfect Forward Secrecy (PFS) is not supported. ECDHE uses the ECC (Elliptic Curve) diffie-Hellman (DH) algorithm, which is fast in calculation and supports PFS.


③ Key exchange algorithm based on ECC

Here are five common ECC based TLS key exchange algorithms that mimic DH_DSS, DHE_DSS, DH_RSA, DHE_RSA, and DH_anon, respectively.

​

Take ecdHE_ECdSA as an example:

The certificate contains the ECDSA-capable public key, and the ECDHE algorithm is used to negotiate and prepare the master key. The certificate must allow the key to be used for signing using the hash algorithm that will be used in the Server key exchange message; The public key must use a curve and point format that can be supported by the Client, which specifies the supported named curve with the EC_point_formats extension in the Client Hello message, as described in [TLSECC]. This is the most secure and high-performance cipher suite available in TLS 1.2.


④ Complete handshake process of ECDHE key exchange

A: The Client sends A Client Hello message to the server to inform the server of the protocol version and encryption suite supported by the Client.

B: a. After receiving the response, the Server selects a protocol and suite supported by both parties and sends Server Hello to the client. At the same time, the Server sends its Certificate to the client.

B. The server uses the private key to sign random client numbers, server numbers, and server DH parameters to generate server signatures.

C: The Server sends DH parameters and Server Key Exchange (Server Key Exchange) to the client.

D: The Client sends DH parameters (Client Key Exchange) to the server.

Then, the client verifies the server signature using the public key. The client and server generate the pre-master key using the DH parameters of the server and the DH parameters of the client respectively, and then generate the master key (session key) using the pre-master key, client random number, and server random number. Finally, the handshake is complete and all messages are encrypted with the master key. As shown in figure:



Eight. Conclusion

Elliptic curve ECC algorithm based on the theory of elliptic curve, can offer higher safety with less computing power intensity, effectively solve the “improve security intensity must increase the key length of project implementation issues, and has been widely supported and use, the reader when choosing encryption algorithm, ECC algorithm is a good choice.



Ix. Reference materials

This section describes the ECC encryption algorithm

https://www.pediy.com/kssd/pediy06/pediy6014.htm


Elliptic Curve Cryptography: a gentle introduction

https://andrea.corbellini.name/2015/05/17/elliptic-curve-cryptography-a-gentle-introduction/


National Cryptography Administration

http://www.oscca.gov.cn/


SM2 Elliptic curve public key cryptography algorithm

http://www.firstsolver.com/wordpress/?p=1938


TLS_ECC

https://tools.ietf.org/html/rfc4492




The authors introduce

Zhang Guanjun, Engineer of Firefly Mobile financial Development platform, User Experience Technology Department, Minsheng Technology Co., LTD