GB/T 32918.1-2016Information security technology - Public key cryptographic algorithm SM2 based on elliptic curves - Part 1: General (English PDF)

3.1.3 Binary extension-field

When q is a power 2 m of 2, the binary extension can be regarded as an m-dimensional vector space on F2 , its elements can be represented by a bit string of length m.

The elements in have multiple representations, the two most common of which are polynomial-based (PB) representations (see A.2.1.1) and normal basis (NB) representations (see A.2.1.3). The selection principle of the base is to make the operation efficiency in as high as possible. This part does not specify the choice of the base. The binary extension-field will be described below by taking a polynomial-based representation as an example.

Let m irreducible polynomial f (x) = x m

+ f m -1 x m - 1

+ ... + f 2 x

2

+ f 1 x + f 0 (where f i in F2 , i = 0, 1, ..., m - 1) is the reduced polynomial of the binary extension-field

. consists of all polynomials on F2 that are less than m. The polynomial set {x m - 1 , x m - 2 , ..., x, 1} is a set of bases of on F2 , which is called the polynomial-base. The coefficient of any element a (x) = a m-1 x m-1

+ a m-2 x m-2

+ ...

+ a1 x + a0 in constitutes a bit string of length m on F2 , which is indicated by a = (am - 1 , am - 2 , ..., a1 , a0 ). The polynomial field characteristics are as follows:

a) Zero 0 is represented by an all-zero bit string;

b) Multiplication unit element 1 is represented by bit string 00...001;

c) The addition of two field elements is a bitwise XOR operation of the bit string;

d) The multiplication of the field elements a and b is defined as follows: Let the polynomials of F2 corresponding to a and b be a (x) and b (x), then a

· b is defined as the bit string corresponding to polynomial (a (x) b (x)) mod f (x).

3.2 Elliptic curve over a finite field

An elliptic curve on a finite field F q is a collection of points. In the affine […]

3.2.6 Weak elliptic curve

If an elliptic curve has an attack method that is better than the calculation complexity of n

1/2 level (n is the order of the base point), the curve is called a weak elliptic curve. Weak elliptic curves are prohibited in this part.

The hypersingular curve on F q [feature divisibility q +1- # E (F q ) of finite field F q ] and the anomalous curve [# E (Fp ) = p] on Fp are weak elliptic curves.

4.1 Data types

In this part, data types include bit strings, byte strings, field elements, points on elliptic curves, and integers.

Bit string: An ordered sequence of 0's and 1's.

Byte string: An ordered sequence of bytes, in which 8 bits form 1 byte.

Field element: An element in the finite field Fq .

Point on elliptic curve: point P in E (Fq ) on an elliptic curve, or a pair of field elements (xP , yP ), where the field elements xP and y P satisfy the elliptic curve equation, or the infinity point O.

The byte string representation of a point has multiple forms, it is identified by a one-byte PC. The byte string representation of the infinity point O is a single zero byte PC = 00. The non-infinity point P = (xP , yP ) has the following three byte string representations:

a) Compressed representation, PC = 02 or 03;

b) Uncompressed representation, PC = 04;

c) Mixed representation, PC = 06 or 07.

Note: Mixed representations contain both compressed and uncompressed […]

5.1 General requirements

Elliptic curve's system parameters are publicly available, the security of the system does not depend on the confidentiality of these parameters. This part does not specify the method for generating elliptic curve's system parameters, but specifies the verification method for system parameters. The calculation of the elliptic curve order and the selection method of the base point can be found in B.3 of Appendix B, the method of generating the curve parameters can be found in Appendix D.

The elliptic curve's system parameters can be divided into two cases in accordance with the different base fields:

- When the base field is Fp (p is a prime number greater than 3), the elliptic curve's system parameters on F p ;

- When the base field is , the elliptic curve's system parameters on .

5.2 Elliptic curve's system parameters on Fp and its verification

5.2.1 Elliptic curve's system parameters on F p

The elliptic curve's system parameters on Fp include:

a) The size of the field q = p, p is a prime number greater than 3;

b) (Optional) a bit string SEED of length at least 192 (if an elliptic curve is generated as described in Appendix D);

c) Two elements a and b in F p , which define the equation of elliptic curve E:

y

2

= x3 + ax + b;

d) Base point G = (xG, yG) in E (Fp ), G!=O;

e) The order n of the base point G (requirement: n > 2

191 and n > 4p

1/2

);

f) (Optional) cofactor h = # E (Fp ) / n.

5.2.2 Verification of elliptic curve's system parameters on Fp

The generator of the elliptic curve's system parameters shall verify the following conditions. The user of the elliptic curve's system parameters can choose to verify these conditions.

6.1 Key pair generation

Input: A set of valid elliptic curve's system parameters over a valid Fq (q = p and p is a prime number greater than 3, or q = 2 m

).

Output: A key pair (d, P) associated with the elliptic curve's system parameters.

a) Use a random number generator to generate an integer d in [1, n - 2];

b) G is the base point, calculate the point P = (xP , yP ) = [d] G (see A.3.2 in

Appendix A);

c) The key pair is (d, P), where d is the private key and P is the public key.

6.2 Verification of the public key

6.2.1 Verification of elliptic curve's public key on Fp

Input: A valid set of elliptic curve's system parameters over F p (p > 3 and p is prime number) and an associated public key P.

Output: For a given elliptic curve's system parameter, if the public key P is valid, the output is “valid”; otherwise, the output is “invalid”.

a) Verify that P is not infinity point O;

b) Verify that the coordinates xP and y P of the public key P are elements in the field Fp (i.e. verify that xP and yP are integers in the interval [0, p - 1]);

c) Verify yP

2

== xP

3

+ axP + b (mod p);

d) Verify [n] P = O;

e) If all verifications have passed, the output is “valid”; otherwise, the output is “invalid”.

6.2.2

Verification of elliptic curve's public key on

Input: A valid set of elliptic curve's system parameters on and an associated public key P.

A.4.2 Conditions to meet for secure elliptic curve

A.4.2.1 Anti-MOV attack conditions

A.Menezes, T.Okamoto, S.Vanstone, G.Frey, and H.Rück's reduction attacks reduce the elliptic curve's discrete logarithm problem on the finite field Fq to the discrete logarithm problem on . This attack method is practical only when B is small, most elliptic curves do not meet this condition. Anti-MOV attack conditions ensure that an elliptic curve is not vulnerable to this reduction method.

The elliptic curve on most Fq does meet the anti-MOV attack conditions.

Before verifying the anti-MOV attack conditions, it shall select a MOV threshold, which is a positive integer B that makes the discrete logarithm problem on at least as difficult as calculating the elliptic curve's discrete logarithm problem on Fq . For the standard q > 2

191 , B >= 27 is required. The selection of B >= 27 also […]

B.1 Finite field and modulo operations

B.1.1 Exponential operations in finite fields

Let alpha be a positive integer, g be the element on the field F q , the exponential operation is the operation of calculating g

alpha

. The exponential operation can be performed efficiently by the binary method outlined below.

Input: positive integer alpha, field Fq , field element g.

Output: g

alpha

.

a) Set e = a mod (q - 1), if e = 0, then it outputs 1;

b) Let the binary representation of e be e = erer-1 ...e1 e0 , of which the highest bit er is 1;

c) Set x = g;

d) For i, execute it by falling from r - 1 to 0:

1) Set x = x

2

;

2) If ei = 1, set x = g · x;

e) Output x.

Other acceleration algorithms are found in Brickell et al. 1993, Knuth 1981.

B.1.2 Inverse operations in finite fields

Let g be a non-zero element on the field F q , then the inverse element g

-1 is the field element c that makes g · c = 1. Since c = g q - 2 , the inversion can be achieved by an exponential operation. Note that if q is a prime number and g is an integer satisfying 1 <= g <= q - 1, then g

-1 is an integer c, 1 <= c <= q - 1, and g·c

==1 (mod q).

Input: Field Fq , non-zero element g in F q .

Output: Inverse element g

-1

.

a) Calculate c = g q - 2 (see B.1.1);

B.1.5 Trace function and half trace function

Let alpha be an element in , and the trace of alpha is:

.

The trace of half of the elements in is 0, the trace of half of the elements […]

B.1.11 Approximate primality testing

Given a trial division bound lmax, if each prime factor of the positive integer h does not exceed lmax, then h is said to be lmax-smooth. Given a positive integer r min , if there is a prime number v >= r min such that a positive integer u = h · v, and the integer h is lmax-smooth, then u is called an approximate prime number. The following algorithm checks the approximate primality of u.

Input: Positive integers u, lmax and r min .

Output: It outputs h and v if u is an approximate prime, otherwise, it outputs “not approximate prime”.

a) Set v = u, h = 1;

C.1 General requirements

All values in this Appendix are expressed in hexadecimal, the left side is the high order and the right side is the low order.

C.2 Elliptic curve on Fp

The elliptic curve equation is: y

2

= x

3

+ ax + b

Example 1: Fp -192 curve

Prime number p: BDB6F4FE 3E8B1D9E 0DA8C0D4 6F4C318C EFE4AFE3

B6B8551F

Coefficient alpha: BB8E5E8F BC115E13 9FE6A814 FE48AAA6 F0ADA1AA

5DF91985

Coefficient b: 1854BEBD C31B21B7 AEFC80AB 0ECD10D5 B1B3308E

6DBF11C1

The base point G = (x, y), of which the order is n.

Coordinate x: 4AD5F704 8DE709AD 51236DE6 5E4D4B48 2C836DC6

E4106640

Coordinate y: 02BB3A02 D4AAADAC AE24817A 4CA3A1B0 14B52704

32DB27D2

Order n: BDB6F4FE 3E8B1D9E 0DA8C0D4 0FC96219 5DFAE76F 56564677

Example 2: Fp -256 curve

Prime number p: 8542D69E 4C044F18 E8B92435 BF6FF7DE 45728391

5C45517D 722EDB8B 08F1DFC3

Coefficient alpha: 787968B4 FA32C3FD 2417842E 73BBFEFF 2F3C848B

6831D7E0 EC65228B 3937E498

Coefficient b: 63E4C6D3 B23B0C84 9CF84241 484BFE48 F61D59A5

B16BA06E 6E12D1DA 27C5249A […]