GB/T 32918.1-2016 English PDF (GBT32918.1-2016)

Delivery: 3 seconds. Download true-PDF + Invoice.
Get Quotation: Click GB/T 32918.1-2016 (Self-service in 1-minute)
Historical versions (Master-website): GB/T 32918.1-2016
Preview True-PDF (Reload/Scroll-down if blank)

GB/T 32918.1-2016: Information security technology - Public key cryptographic algorithm SM2 based on elliptic curves - Part 1: General
GB/T 32918.1-2016
Information security technology--Public key cryptographic algorithm SM2 based on elliptic curves--Part 1. General
ICS 35.040
L80
National Standards of People's Republic of China
Information security technology
SM2 elliptic curve public key cryptography algorithm
Part 1. General
Released on.2016-08-29
2017-03-01 implementation
General Administration of Quality Supervision, Inspection and Quarantine of the People's Republic of China
China National Standardization Administration issued
Content
Foreword I
Introduction II
1 range 1
2 symbols and abbreviations 1
3 domain and elliptic curve 2
3.1 Limited domain 2
3.2 Elliptic curve 3 on finite field
4 data types and their conversion 5
4.1 Data Type 5
4.2 Data Type Conversion 5
5 Elliptic curve system parameters and their verification 8
5.1 General requirements 8
5.2 Elliptic curve system parameters on Fp and its verification 8
5.3 Elliptic curve system parameters and verification on F2m 9
6 Key pair generation and public key verification 9
6.1 Key Pair Generation 9
6.2 Verification of Public Keys 10
Appendix A (informative) Background on elliptic curves 11
A.1 Prime domain Fp 11
A.2 Binary extension F2m 13
A.3 elliptic curve multi-point operation 23
A.4 Method for solving discrete logarithm problems of elliptic curves 26
A.5 Compression of points on elliptic curves 27
Appendix B (informative appendix) Number theory algorithm 29
B.1 Finite domain and modular operations 29
B.2 Polynomial on a finite field 33
B.3 Elliptic curve algorithm 35
Appendix C (informative) Curve example 37
C.1 General requirements 37
C.2 Fp upper elliptic curve 37
C.3 F2m elliptic curve 37
Appendix D (informative) Quasi-random generation and verification of elliptic curve equation parameters 39
D.1 Quasi-random generation of parameters of elliptic curve equations 39
D.2 Verification of elliptic curve equation parameters 40
Reference 41
Foreword
GB/T 32918 "Information Security Technology SM2 Elliptic Curve Public Key Cryptography Algorithm" is divided into the following five 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 the first part of GB/T 32918.
This part is drafted in accordance with the rules given in GB/T 1.1-2009.
This section is proposed by the National Cryptography Authority.
This part is under the jurisdiction of the National Information Security Standardization Technical Committee (SAC/TC260).
This section drafted by. Beijing Huada Xinan Technology Co., Ltd., People's Liberation Army Information Engineering University, Chinese Academy of Sciences data and
Communication Protection Research Education Center.
The main drafters of this section. Chen Jianhua, Zhu Yuefei, Ye Dingfeng, Hu Lei, Lu Dingyi, Peng Guohua, Zhang Yajuan, Zhang Zhenfeng.
introduction
In 1985, N. Koblitz and V. Miler independently proposed the application of elliptic curves to public key cryptosystems. Elliptical curve
The nature of the curve on which the key cipher is based is as follows.
--- The elliptic curve on the finite field forms a finite exchange group under the point addition operation, and its order is similar to the base domain size;
--- Similar to the power operation in the finite field multiplication group, the elliptic curve multi-point operation constitutes a one-way function.
In the multi-point operation, the multiple point and the base point are known, and the problem of solving the multiple is called the elliptic curve discrete logarithm problem. For general ellipse
For the discrete logarithm problem of curves, there are only solutions for exponential computational complexity. And large number decomposition problems and discrete pairs on finite fields
Compared with the numerical problem, the elliptic curve discrete logarithm problem is much more difficult to solve. Therefore, under the same level of security requirements, the elliptic curve is dense
The code requires a much smaller key size than other public key ciphers.
SM2 is an elliptic curve cryptographic algorithm standard developed and proposed by the National Cryptography Authority. The main objectives of GB/T 32918 are as follows.
---GB/T 32918.1 defines and describes the related concepts and mathematical basics of the SM2 elliptic curve cryptographic algorithm, and outlines
The relationship between this part and other parts.
--- GB/T 32918.2 describes a signature algorithm based on elliptic curve, namely SM2 signature algorithm.
--- GB/T 32918.3 describes a key exchange protocol based on elliptic curve, namely the SM2 key exchange protocol.
---GB/T 32918.4 describes a public key encryption algorithm based on elliptic curve, namely SM2 encryption algorithm, which needs to be used
The SM3 cryptographic hash algorithm defined in GB/T 32905-2016.
---GB/T 32918.5 gives the elliptic curve parameters used by the SM2 algorithm, and uses the elliptic curve parameters for SM2 operations.
Sample results.
This part is the first part of GB/T 32918, which describes the necessary mathematical basics and general techniques to help achieve other departments.
The cryptographic mechanism specified by the branch.
Information security technology
SM2 elliptic curve public key cryptography algorithm
Part 1. General
1 Scope
This part of GB/T 32918 specifies the necessary mathematical basics and related passwords involved in the SM2 elliptic curve public key cryptography algorithm.
Technology to help implement the cryptographic mechanisms specified in the various sections.
This part is applicable to the design, development and use of elliptic curve public key cryptography algorithms whose base domain is prime domain and binary domain.
2 symbols and abbreviations
The following symbols and abbreviations apply to this document.
B MOV threshold. a positive number B, such that the discrete logarithm on FqB is obtained at least from the elliptic curve on Fq
It is as difficult as the logarithm.
Deg(f) The number of times the polynomial f(x).
E An elliptic curve defined by a and b over a finite field.
E(Fq) A set of all rational points of the elliptic curve E (including the infinity point O) on Fq.
ECDLP elliptic curve discrete logarithm problem.
Fp contains the prime domain of p elements.
Fq contains a finite field of q elements.
Fq* A multiplicative group of all non-zero elements in Fq.
F2m contains a binary extension of 2m elements.
G A base point of an elliptic curve whose order is prime.
Gcd(x, y) The greatest common factor of x and y.
h residual factor, h=
xP The x coordinate of point P.
X-1 modn makes the unique integer y, where x y ≡ 1 (modn) holds, 1 ≤ y ≤ n-1, gcd (x, n) = 1.
The splicing of x‖yx and y, where x and y are bit strings or byte strings.
X≡y(modn) x is congruent with y-module n. That is, x modn=ymodn.
yP Point y coordinate of P.
The point compression representation of y~P yP.
Zp The remainder of the class of the integer modulo p.
\u003cG\u003e The cyclic group generated by the base point G.
[k]P k times the point P on the elliptic curve, ie. [k]P=PPP
, 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.
x top function, the smallest integer greater than or equal to x. For example, 7 = 7 and 8.3 = 9.
The x-bottom function, the largest integer less than or equal to x. For example, 7 = 7 and 8.3 = 8.
3.1.2 Prime domain Fp
When q is an odd prime number p, elements in the prime domain Fp are represented by integers 0, 1, 2, and p-1. The prime domain characteristics are as follows.
a) the addition unit element is an integer 0;
b) the multiplication unit is an integer 1;
c) the addition of the domain elements is the modulo p addition of integers, ie if a, b ∈ Fp, then ab = (ab) modp;
d) The multiplication of the domain elements is the modulo p multiplication of integers, ie a, b = (a · b) modp if a, b ∈ Fp.
3.1.3 Binary expansion domain F2m
When q is a power of 2 m, the binary extension F2m can be regarded as the m-dimensional vector space on F2, and the elements can be used with bits of length m.
String representation.
The elements in F2m have multiple representations, the two most common of which are polynomial basis (PB) representations (see A.2.1.1) and regular
Base (NB) representation (see A.2.1.3). The selection principle of the basis is to make the operation efficiency in F2m as high as possible. This section does not specify the basic
select. The binary expansion domain F2m will be described below by taking a polynomial base representation as an example.
Let m2 irreducible polynomial f(x)=xm fm-1xm-1 f2x2 f1x f0 (where fi∈F2,i=0,1,
, m-1) is a reduced polynomial of the binary extension F2m. F2m consists of all polynomials on F2 that are less than m. Polynomial set
{xm-1,xm-2,,x,1} is a set of bases of F2m on F2, called a polynomial basis. Any element in F2m a(x)=
Am-1xm-1 am-2xm-2 a1x a0 The coefficient on F2 constitutes a bit string of length m, with a=(am-1,
Am-2,, a1, a0) is indicated. The polynomial domain characteristics are as follows.
a) Zero 0 is represented by an all-zero string;
b) multiplication unit 1 is represented by bit string 00001;
c) the addition of two domain elements is a bitwise XOR operation of the bit string;
d) The multiplication of the domain 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
A bit string corresponding to the polynomial (a(x)b(x)) modf(x).
3.2 Elliptic curve over a finite field
An elliptic curve on a finite field Fq is a collection of points. In the affine coordinate system, the point P (non-infinity point) on the elliptic curve
The symbol is expressed as P = (xP, yP), where xP, yP are domain elements satisfying a certain equation, which are respectively called the x coordinate and the y coordinate of the point P. in
In this section, Fq is called the base domain.
For more background on elliptic curves, see A.1 and A.2 in Appendix A.
In this section, 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)modp≠0. (1)
The elliptic curve E(Fp) is defined as, see C.2.
E(Fp)={(x,y)|x, y∈Fp, and satisfy the equation (1)}∪{O}, where O is the infinity point.
The number of points on the elliptic curve E(Fp)
3.2.3 Elliptic curve group
3.2.3.1 Elliptic curve group on Fp
The points on the elliptic curve E(Fp) form an exchange group according to the following addition rules.
a) OO=O;
b) ∀P=(x,y)∈E(Fp)\\{O}, PO=OP=P;
c) ∀P=(x,y)∈E(Fp)\\{O}, the inverse element of P-P=(x,-y), P (-P)=O;
d) Two rules for adding 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
X3=λ2-x1-x2,
Y3=λ(x1-x3)-y1,{
In the formula.
λ=
Y2-y1
X2-x1
e) Double point rule.
Let P1=(x1,y1)∈E(Fp)\\{O}, and y1≠0, P3=(x3,y3)=P1 P1,
X3=λ2-2x1,
Y3=λ(x1-x3)-y1,{
In the formula.
λ=
3x21 a
2y1
3.2.3.2 Elliptic curve group on F2m
The points on the elliptic curve E(F2m) form an exchange group according to the following addition rules.
a) OO=O;
b) ∀P=(x,y)∈E(F2m)\\{O}, PO=OP=P;
c) ∀P=(x,y)∈E(F2m)\\{O}, the inverse element of P-P=(x,xy),P (-P)=O;
d) Two rules for adding different points that are not reciprocal.
Let P1=(x1,y1)∈E(F2m)\\{O}, P2=(x2,y2)∈E(F2m)\\{O}, and x1≠x2,
Let P3=(x3,y3)=P1 P2, then
X3=λ2 λ x1 x2 a,
Y3=λ(x1 x3) x3 y1,{
In the formula.
λ=
Y1 y2
X1 x2
e) Double point rule.
Let P1=(x1,y1)∈E(F2m)\\{O}, and x1≠0, P3=(x3,y3)=P1 P1, then
X3=λ2 λ a,
Y3=x21 (λ 1)x3,{
In the formula.
λ=x1
Y1
X1
3.2.4 elliptic curve multi-point operation
Multiple additions of the same point on an elliptic curve are called multi-point operations of that point. Let k be a positive integer and P be on an elliptic curve
Point, the k times of the point P is added as the k-time point operation of the point P, which is recorded as Q=[k]P=PPP
􀮩 􀮫􀮪􀪁􀪁􀪁 􀪁􀪁􀪁
. Because [k]P=[k-1]P
P, so k times can be recursively obtained.
The output of a multi-point operation may be at infinity point O.
Multi-point operations can also be implemented more efficiently with some techniques, see Appendix A, A.3.
3.2.5 Elliptic Curve Discrete Logarithm Problem (ECDLP)
It is known that the elliptic curve E(Fq), the point of order n, G∈E(Fq) and Q∈ \u003cG\u003e Elliptic curve discrete logarithm problem is to determine the integer
L∈[0,n-1], so that Q=[l]G holds.
The elliptic curve discrete logarithm problem is related to the security of the elliptic curve cryptosystem, so a safe elliptic curve should be chosen. About how
Select the safe elliptic curve, see Appendix A, A.4.
3.2.6 weak elliptic curve
If an elliptic curve has an attack method that is better than the n1/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 section.
Hypersingular curve on Fq [Characteristic divisibility of finite field Fq q 1-
4.2 Data Type Conversion
4.2.1 Data type conversion relationship
Figure 1 provides the conversion relationship between various data types, and the mark on the line is the bar where the corresponding data conversion method is located.
Figure 1 data type and conversion convention
4.2.2 Integer to byte string conversion
Input. a non-negative integer x, and the target length k of the byte string (where k satisfies 28k>x).
Output. A byte string M of length k.
a) Let Mk-1, Mk-2, and M0 be the leftmost to rightmost byte of M;
b) The byte of M satisfies.
4.2.3 Byte string to integer conversion
Input. a byte string M of length k.
Output. integer x.
a) Let Mk-1, Mk-2, and M0 be the leftmost to rightmost byte of M;
b) Convert M to an integer x.
4.2.4 Bit string to byte...