GB/T 32918.1-2016 in English

《GB/T 32918.1-2016信息安全技术 SM2椭圆曲线公钥密码算法 第1部分：总则》由TC260（全国网络安全标准化技术委员会）归口，主管部门为国家标准化管理委员会。

GB/T 32918 Information security technology- Public key cryptographic algorithm SM2 based on elliptic curves consists of 5 parts:

—Part 1: General;

—Part 2: Digital signature algorithm;

—Part 3: Key exchange protocol;

—Part 4: Public key encryption algorithm;

—Part 5: Parameter definition.

This part is Part 1 of GB/T 32918.

This part is developed in accordance with the rules given in GB/T 1.1-2009.

This part was proposed by the State Cryptography Administration of the People’s Republic of China.

This part is under the jurisdiction of SAC/TC 260 (National Technical Committee 260 on Information Technology Security of Standardization Administration of China).

Drafting organizations of this part: Beijing Huada Infosec Technology Co., Ltd., The PLA Information Engineering University and DCS Center of Chinese Academy of Sciences.

Chief drafters of this part: Chen Jianhua, Zhu Yuefei, Ye Dingfeng, Hu Lei, Pei Dingyi, Peng Guohua, Zhang Yajuan and Zhang Zhenfeng. 
Introduction

N.Koblitz and V.Miller proposed the application of elliptic curves to public key cryptography respectively in 1985. The nature of the curve on which the public key cryptography of elliptic curve is based is as follows:

— The elliptic curve on the finite field constitutes a finite exchange group under the point addition, and its order is similar to the base field size;

— Similar to the power operation in the finite field multiplicative group, the elliptic curve multi-point operation constitutes a one-way function.

In the multi-point operation, the multiple points and the base point are known, and the problem of solving the multiple is called the discrete logarithm of elliptic curve. For the discrete logarithm problem of general elliptic curves, there is only a solution method for exponential computational complexity. Compared with the large number decomposition problems and the discrete logarithm problems on the finite field, the discrete logarithm problem of elliptic curve is much more difficult to solve. Therefore, elliptic curve ciphers are much smaller than other public key ciphers at the same level of security.

SM2 is an elliptic curve cryptographic algorithm standard developed and proposed by the State Cryptography Administration. The main objectives of GB/T 32918 are as follows:

— GB/T 32918.1 defines and describes the relevant concepts and mathematical basics of the SM2 elliptic curve cryptographic algorithm, and summarizes the relationship between this part and other parts.

— GB/T 32918.2 describes a signature algorithm based on elliptic curve, i.e. SM2 signature algorithm.

— GB/T 32918.3 describes a key exchange protocol based on elliptic curve that is SM2 key exchange protocol.

— GB/T 32918.4 describes a public key encryption algorithm based on elliptic curve that is SM2 encryption algorithm, with the SM3 cryptographic hash algorithm defined in GB/T 32905-2016 adopted.

— GB/T 32918.5 defines the elliptic curve parameters used by the SM2 algorithm, and the sample results of the SM2 operation with the elliptic curve parameters.

As Part 1 of GB/T 32918, this part describes the necessary mathematical basics and general techniques to help implement the cryptographic mechanisms specified in other parts.
Information security technology—
Public key cryptographic algorithm SM2 based on elliptic curves—
Part 1: General

1 Scope

This part of GB/T 32918 specifies the necessary mathematical basics and related cryptographic techniques involved in public key cryptographic algorithm SM2 based on elliptic curves to help implement the cryptographic mechanisms specified in other parts.

This part applies to the elliptic curve public key cryptography algorithm with the base field being the prime field and the binary extension field.

2 Symbols and abbreviations

For this part, the following symbols and abbreviations apply.

B: MOV threshold. Positive B, so that the obtaining the discrete logarithm of the number on is at least as difficult as obtaining the discrete logarithm of elliptic curve on Fq.

deg (f): the power of the polynomial f(x).

E: an elliptic curve defined by a and b on the finite field.

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

ECDLP: elliptic curve discrete logarithm problem.

Fp: a prime field containing p elements.

Fq: a finite field containing q elements.

: a multiplicative group consisting of all non-zero elements in Fq.

: a binary extension containing 2m elements.

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

gcd (x,y): the greatest common factor of x and y.

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

LeftRotate (): looped left shift operation.

lmax: the upper bound of the largest prime factor of the cofactor h.

m: the number of extensions of binary extension regarding F2 .

mod f(x): the operation of modulus polynomial f(x). If f(x) is a polynomial on a binary field, then all coefficients perform modulo-2 operation.

mod n: modulo-n operation. For example, 23 mod 7-2:

n: the order of the base point G (n is the prime factor of #E (Fq)).

O: a special point on the elliptic curve, called the infinity point or zero point, is the unit element of the elliptic curve addition group.

P: P = (xP, yP) is a point on the elliptic curve other than O, and its coordinates xP and yP satisfy the elliptic curve equation.

P1 + P2: the sum of two points P1 and P2 on the elliptic curve E.

p: a prime number greater than 3.

q: the number of elements in the finite field Fq .

a,b: elements in Fq, which define a elliptic curve E on Fq.

rmin: the lower bound of the order n of the base point G.

Tr (): trace function.

xP: the x coordinate of the point P.

x-1 mod n: the only integer y making with 1 ≤ y ≤ n - 1, gcd (x,n) = 1.

x ‖ y: the splicing of x and y, where x and y are bit strings or byte strings.
: modulo-n of x and y is congruence. That is, x mod n = y mod n.
yP: the y coordinate of the point P.
: the point compression representation of yP.

Zp : the remaining class ring of the integer modulus p.

: a cyclic group generated by the base point G.

[k]P: k multi-point of the point P on the elliptic curve, i.e:
, where k is a positive integer.

[x, y]: a set of integers greater than or equal to x and less than or equal to y.

: top function, the smallest integer greater than or equal to x. For example , .

: bottom function, the largest integer less than or equal to x. For example , .

#E (Fq): the number of points on E (Fq), called the order of the elliptic curve E (Fq).

㊉: two bit strings with equal length are subjected to bit XOR.

3 Field and elliptic curve

3.1 Finite field

3.1.1 General

This subclause gives a description of the finite field Fq and a representation of its element; q is an odd prime or a power of 2. Where q is an odd prime number p, p > 2191 is required; when q is a power of 2, 2m, m > 192 is required and m is a prime number.

3.1.2 Prime field Fp

Where q is an odd prime number p, the elements in the prime field Fp are represented by integers 0, 1, 2, …, p-1.The features of the prime field is as follows:

a) The addition unit element is integer 0;

b) The multiplication unit element is integer 1;

c) The addition of the field element is modulo p addition of integers, i.e. if a, b∈Fp, then a + b = (a + b) mod p;

d) The multiplication of the field elements is modulo p multiplication of integers, i.e., if a, b ∈Fp, then a•b = (a • b) mod p.

3.1.3 Binary extension field

Where q is a power of 2, 2m, the binary field can be seen as an F2 - dimensional vector space, whose elements can be represented by a bit string with length m.

There are many ways to represent elements in , where the two most commonly used methods are the polynomial basis (PB) representation (see Subclause A.2.1.1) and the normal basis (NB) representation (see Subclause A.2.1.3). Selection principle of base is to make the calculation efficiency of as high as possible. This standard does not specify the choice of the base. The following is a polynomial base representation as an example to illustrate the binary extension field .

Let the m power irreducible polynomial f(x) = xm + fm-1 xm-1 +...+ f2 x2 + f1x + f0 (where fi∈F2, i=0, 1, ..., m-1) on F2 be a reduced polynomial of a binary extension field . consists of all polynomials in the power of F2 less than m. The set of polynomials {xm-1, xm-2, ..., x, 1} is a set of bases of on F2 and called a polynomial basis. The coefficient of any one of the elements a(x) = am-1xm-1 + am-2xm-2 +...+ a1x + a0 in on F2 constitutes a bit string of length m, is expressed with a = (am-1, am-2, ..., a1, a0).The field features of polynomials are as follows:

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

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

c) The addition of two field elements is subjected to bit XOR of bit strings.

d) The multiplication of the field elements a and b is defined as follows: let the polynomial of F2 corresponding to a and b be a(x) and b (x), then a•b is defined as the bit string corresponding to the polynomial (a (x) b (x)) mod f (x).

3.2 Elliptic curve on finite field

The elliptic curve on a finite field Fq is a set of points. In the affine coordinate system, the coordinates of the point P (non-infinity point) on the elliptic curve are expressed as P = (xP, yP), where xP, yP are field elements satisfying certain equations, and called respectively the x and y coordinates of the point P. In this standard, Fq is called a base field.

For more background knowledge on elliptic curves, see Subclauses A.1 and A.2 in Annex A.

In this standard, the points on the elliptic curve are represented by affine coordinates unless otherwise specified.

3.2.1 Elliptic curve on Fp

The elliptic curve equation defined on Fp (p is a prime number greater than 3) is:

y2 = x3 + ax + b, a, b ∈ Fp, and (4a3 + 27b2) mod p ≠ 0 (1)

The elliptic curve E (Fp) is defined as, as detailed in Subclause C.2:

E (Fp) = {(x,y)|x,y ∈ Fp, and they satisfy the equation (1)}∪{O}, where O is an infinity point.

The number of points on the elliptic curve E (Fp) is represented by #E (Fp), and called the order of the elliptic curve E (Fp).

3.2.2 Elliptic curve on

The elliptic curve equation defined on is:
y2 + xy = x3 + ax2 + b, a, b∈ , and b ≠ 0 (2)

Elliptic curve is defined as, as detailed in Subclause C.3:

, and meets the equation (2)}∪{O} where O is the infinity point.

The number of points on the elliptic curve is expressed with # , and called the order of elliptic curve .

3.2.3 Elliptic curve group

3.2.3.1 Elliptic curve group on Fp

The points on the elliptic curve E (Fp) constitute an exchange group according to the following addition rules:

a) O + O = O;

b) ∀P = (x,y)∈E(Fp)\{O}, P+O = O+P = P;

c) ∀P = (x, y)∈E(Fp)\{O}, the inverse element of P, -P = (x, -y), P + (-P) = O;

d) Addition rules for two different points that are not reciprocal:

Let P1 = (x1, y1)∈E(Fp)\{O}, P2 = (x2, y2)∈E(Fp)\{O}, and x1 ≠ x2,

Let P3 = (x3, y3) = P1 + P2, then



Where


e) Multi-point rules:

Let P1 = (x1, y1)∈E(Fp)\{O}, and y1 ≠ 0, P3 = (x3, y3) = P1 +P1,

Then



Where,

.

3.2.3.2 Elliptic curve group on

The points on the elliptic curve constitute an exchange group according to the following addition rules

a) O + O = O;

b) ∀P = (x, y)∈ \{O}, P + O= O + P = P;

c) ∀P = (x, y)∈ \{O}, the inverse element of P, - P = (x, x+y), P + (-P) = O;

d) Addition rules for two different points that are not reciprocal:

Let P1 = (x1, y1)∈ \{O}, P2 = (x2, y2)∈ \{O}, and x1 ≠ x2,

Let P3 = (x3, y3) = P1 + P2, then



Where



e) Multi-point rules:

Let P1 = (x1, y1)∈ \{O}, and x1 ≠ 0, P3 = (x3, y3) = P1 + P1, then



Where

.

3.2.4 Calculation of multi-points on elliptic curve

Multiple additions of the same point on an elliptic curve are called multi-point operations of that point. Let k be a positive integer, P be a point on the elliptic curve, and call k times’ addition as k multi-point operation of point P, denote it as . Because [k] P = [k-1] P + P, the multi-points can be recursively obtained.

The output of a multi- point operation may be at infinity point O.

The calculation of multi-point may also be fulfilled more effectively via some skills, as detailed in Subclause A.3 in Annex A.

3.2.5 Elliptic curve discrete logarithm problem (ECDLP)

Known elliptic curve E (Fq) at point of G∈E (Fq) and Q∈ with n order, the elliptic curve discrete logarithm problem is to determine the integer l∈[0, n-1], so that Q = [l] G is established.

The elliptic curve discrete logarithm problem is related to the security of elliptic curve cryptosystems, so a safe elliptic curve must be chosen. See Sublcause A.4 in Annex A for information on how to choose a safe elliptic curve.

3.2.6 Weak elliptic curve

If an elliptic curve has an attack method superior to order n1/2 (n is the order of the base point) to calculate the complexity, the curve is called a weak elliptic curve. Weak elliptic curves are prohibited in this standard.

Hyper-singular curve over Fq (where the characteristic exact division q + 1 - # E (Fq) in finite field Fq) and Anomalous curve (# E (Fq) = p) on the curve Fq are weak elliptical curves.

4 Data types and their conversion

4.1 Data type

In this standard, 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 where 8 bits are 1 byte.

Field elements: the elements in the finite field Fq.

A point on an elliptic curve: a point on an elliptic curve or a pair of field elements (xP, yP) where the field elements xP and yP satisfy the elliptic curve equation or the infinity point O.

The byte string representation of a dot has many forms and 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 representations. In an implementation, it allows conversion to a compressed representation or an uncompressed representation.

For compressed representations and mixed representations of points on elliptic curves, this standard is defined as an alternative form. See Subclause A.5 of Annex A for a compressed representation of the point on the elliptic curve.

Foreword i
Introduction ii
1 Scope
2 Symbols and abbreviations
3 Field and elliptic curve
3.1 Limited field
3.2 Elliptic curve on definite field
4 Data types and their conversion
4.1 Data type
4.2 Data type conversion
5 Elliptic curve system parameters and their verification
5.1 General requirements
5.2 System parameters of elliptic curves on Fp and their verification
5.3 System parameter of elliptic curves on and their verification
6 Key pair generation and public key verification
6.1 Key pair generation
6.2 Public key verification
Annex A (Informative) Background knowledge about elliptic curves
A.1 Prime field Fp
A.2 Binary extension field
A.3 Calculation of elliptic curve multiplication points
A.4 Solution to discrete logarithm problem of elliptic curve
A.5 Compression of points on elliptic curves
Annex B (Informative) Number-theoretic algorithm
B.1 Finite field and modulo operation
B.2 Polynomials over a finite field
B.3 Elliptic curve algorithm
Annex C (Informative) Curve example
C.1 General requirements
C.2 Elliptic curve over Fp
C.3 Elliptic curve over
Annex D (Informative) Quasi-random generation and verification of elliptic curve equation parameters
D.1 Quasi-random generation of elliptic curve equation parameters
D.2 Verification of elliptic curve equation parameters
Bibliography