GB/T 32918.12016_English: PDF (GBT32918.12016)
Standard ID  Contents [version]  USD  STEP2  [PDF] delivered in  Standard Title (Description)  Related Standard  Status  PDF 
GB/T 32918.12016  English  365 
Add to Cart

09 seconds. Autodelivery

Information security technology  Public key cryptographic algorithm SM2 based on elliptic curves  Part 1: General

GB/T 32918.12016
 Valid 
GB/T 32918.12016

Standard ID  GB/T 32918.12016 (GB/T32918.12016)  Description (Translated English)  Information security technology  Public key cryptographic algorithm SM2 based on elliptic curves  Part 1: General  Sector / Industry  National Standard (Recommended)  Classification of Chinese Standard  L80  Word Count Estimation  46,487  Date of Issue  20160829  Date of Implementation  20170301  Drafting Organization  Beijing Huada Xinan Technology Co., Ltd., China People's Liberation Army Information Engineering University, Chinese Academy of Sciences data and communication protection research and education center  Administrative Organization  National Information Security Standardization Technical Committee (SAC/TC 260)  Regulation (derived from)  National Standard Announcement 2016 No.14  Proposing organization  National Password Authority  Issuing agency(ies)  General Administration of Quality Supervision, Inspection and Quarantine of the People's Republic of China, China National Standardization Administration Committee 
GB/T 32918.12016
GB
NATIONAL STANDARD OF THE
PEOPLE’S REPUBLIC OF CHINA
ICS 35.040
L 80
Information security technology  Public key
cryptographic algorithm SM2 based
on elliptic curves  Part 1. General
ISSUED ON. AUGUST 29, 2016
IMPLEMENTED ON. MARCH 01, 2017
Issued by. General Administration of Quality Supervision Inspection and
Quarantine of PRC;
Standardization Administration of PRC.
Table of Contents
Foreword ... 4
Introduction ... 5
1 Scope ... 7
2 Symbols and abbreviations ... 7
3 Field and elliptic curve ... 9
3.1 Finite field ... 9
3.2 Elliptic curve over a finite field ... 10
4 Data types and their conversion ... 14
4.1 Data types ... 14
4.2 Data type conversion... 15
5 Elliptic curve system parameters and their verification ... 19
5.1 General requirements... 20
5.2 Elliptic curve system parameters on Fp and its verification ... 20
5.3 Elliptic curve system parameters on and its verification ... 21
6 Key pair generation and public key verification ... 23
6.1 Key pair generation ... 23
6.2 Verification of the public key ... 23
Appendix A (Informative) Background knowledge about elliptic curves ... 25
A.1 Prime field Fp ... 25
A.2 Binary extensionfield ... 29
A.3 Elliptic curve’s multiplepointmultiplication operation ... 46
A.4 Method for solving discrete logarithm problem of elliptic curve ... 50
A.5 Compression of points on elliptic curves ... 53
Appendix B (Informative) Number theory algorithm ... 55
B.1 Finite field and modulo operations ... 55
B.2 Polynomials over a finite field ... 62
B.3 Elliptic curve algorithm ... 66
Appendix C (Informative) Curve example ... 68
C.1 General requirements ... 68
C.2 Elliptic curve on Fp ... 68
C.3 Elliptic curve on ... 69
Appendix D (Informative) Quasirandom generation and verification of
parameters of elliptic curve equation ... 71
D.1 Quasirandom generation of parameters of elliptic curve equation ... 71
D.2 Verification of parameters of elliptic curve equation ... 72
References ... 74
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 cryptography techniques which are involved in the SM2 elliptic curve’s
public key cryptography algorithm, to help implement the cryptographic
mechanisms as specified in other parts.
This part is applicable to the design, development and use of elliptic curve’s
public key cryptography algorithms of which the base field is prime field and
binary field. [Translator note. In Chinese, there is only single word
corresponding to mathematic “domain” and “field” (identical in Chinese).
Therefore, in this translation, “field” and “domain” can be replaced each other
where applicable (exchangeable); likewise, limited domain finite field]
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 from
is obtained at least same difficult as obtaining the elliptic curve from Fq.
deg(f). The number of times the polynomial f (x).
E. An elliptic curve which is 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’s discrete logarithm problem.
Fp. A prime field which contains p elements.
Fq. A finite field which contains q elements.
Fq*. A multiplicative group which is constituted by all nonzero elements in Fq.
a) The addition unit element is an integer 0;
b) The multiplication unit element is an integer 1;
c) The addition of the field element is a modulo p addition of integers, that is,
if a, b ∈ Fp, then a + b = (a + b) mod p;
d) The multiplication of the field element is a modulo p multiplication of integer,
that is, if a, b ∈ Fp, then a·b = (a·b) mod p.
3.1.3 Binary extensionfield
When q is a power 2m of 2, the binary extension can be regarded as an
mdimensional 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 polynomialbased (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 extensionfield will be described
below by taking a polynomialbased representation as an example.
Let m irreducible polynomial f (x) = xm + fm 1 x m  1 + ... + f2x2 + f1x + f0 (where
fi∈F2, i = 0, 1, ..., m  1) is the reduced polynomial of the binary extensionfield
. consists of all polynomials on F2 that are less than m. The polynomial
set {xm  1, xm  2, ..., x, 1} is a set of bases of on F2, which is called the
polynomialbase. The coefficient of any element a (x) = am1xm1 + am2xm2 + ...
+ a1x + 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 allzero 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 Fq is a collection of points. In the affine
The elliptic curve E (Fq), the point G∈E (Fq) and Q∈< G> of the order n are known.
The elliptic curve’s discrete logarithm problem is to determine the integer l∈[0,
n  1], such that Q = [l] G is established.
The elliptic curve’s discrete logarithm problem is related to the security of the
elliptic curve cryptosystem, so it shall select a secure elliptic curve. See A.4 in
Appendix A for how to select a secure elliptic curve.
3.2.6 Weak elliptic curve
If an elliptic curve has an attack method that is better than the calculation
complexity of 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 part.
The hypersingular curve on Fq [feature divisibility q +1 # E (Fq) of finite field Fq]
and the anomalous curve [# E (Fp) = p] on Fp are weak elliptic curves.
4 Data types and their conversion
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∈E (Fq) 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 point has multiple forms, it is identified by a
onebyte PC. The byte string representation of the infinity point O is a single
zero byte PC = 00. The noninfinity 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
verification
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 Fp;
 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 Fp
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 Fp, which define the equation of elliptic curve E.
y2 = x3 + ax + b;
d) Base point G = (xG, yG)∈E (Fp), G≠O;
e) The order n of the base point G (requirement. n > 2191 and n > 4p1/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.
j) If any of the above verifications fail, the output is “invalid”; otherwise, the
output is “valid”.
6 Key pair generation and public key verification
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 = 2m).
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∈[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 Fp (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 yP 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 yP2 ≡ xP3 + 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.
Table A.7  Elliptic curve’s addition complexity on binary extensionfield
Operation
Coordinate system
Affine coordinates standard projective coordinates
Jacobian weighted projective
coordinates
General addition (α≠0) 1I + 2M + 1S 15M + 1S 15M + 5S
Pointmultiplication 1I + 2M + 2S 8M + 3S 5M + 5S
Note. I, M, and S in the table represent the inversion, multiplication, and square
operations in the finite field, respectively.
Calculate the multiplepointmultiplication Q = [k] P, let the number of bits of k
be l, the Hamming weight of k be W, then the algorithm 1 requires addition
operation of the (l  1) times elliptic curve’s pointdoubling and (W  1)times
point; algorithm 2 requires addition operation of l times elliptic curve’s point
doubling and l/3times point; algorithm 3 is divided into two parts. pre
computation requires addition operation of a pointdoubling operation and (2r  1
 1)times point addition operation, the main loop part needs addition operation
of (l  1) times of pointdoubling operation and [l/(r + 1)  1]times point, totally,
it requires l times pointdoubling operation and [2r  1 + l/(r + 1)  2]times point
addition operation. Generally, there is W≈l/2, then the complexity of the
multiplepointmultiplication operation is as follows (when the base field is a
binary extensionfield, it assumes α≠0; when α = 0, minus 1 multiplication
operation).
Algorithm 1.
The base field is the prime field.
Complexity under affine coordinates. 1.5lI + 3lM + 2.5lS
Complexity under standard projective coordinates. 14.5lM + 6lS
Complexity under Jacobian weighted projective coordinates. 10lM + 8lS
The base field is a binary extensionfield.
Complexity under affine coordinates. 1.5lI + 3lM + 2.5lS
Complexity under standard projective coordinates. 15.5lM + 3.5lS
Complexity under Jacobian weighted projective coordinates. 12.5lM + 7.5lS
Algorithm 2.
The base field is the prime field.
Complexity under affine coordinates. 1.33lI + 2.67lM + 2.33lS
• BSGS method. time complexity and space complexity are both (πn/2)1/2;
• Pollard method. the algorithm complexity is (πn/2)1/2;
• Parallel Pollard method. Let r be the number of parallel processors, the
algorithm complexity is reduced to (πn /2)1/2/r;
• MOVmethod. the ESPLP of supersingular elliptic curves and curves with
similar properties is reduced to the discrete logarithm problem on the small
extensionfield of Fq (subexponential computational complexity algorithm);
• Abnormal curve’s discrete logarithm solving method. effective attack
method (polynomial level computational complexity algorithm) for the
abnormal curve [# E (Fp) = p curve];
• GHSmethod. Use the Weil descent technique to solve the discrete
logarithm problem of the elliptic curve on the binary extensionfield with the
extension number as the composite number, convert the ECDLP into a
discrete logarithm problem of the hyperelliptic curve, whilst solving the
hyperelliptic curve’s discrete logarithm has a subexponential level
computational complexity algorithm.
For the discrete logarithm problem of general curves, the current solution
methods are exponential level computational complexity, no general attack
methods for effective subexponential level computational complexity are found.
For the discrete algorithm problems of some special curves, it exists the
polynomial level computational complexity or subexponential level
computational complexity algorithm.
When choosing a curve, it shall avoid using a weakly elliptical curve in the
cryptographic sense that is vulnerable to the above methods.
A.4.2 Conditions to meet for secure elliptic curve
A.4.2.1 AntiMOV 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. AntiMOV attack
conditions ensure that an elliptic curve is not vulnerable to this reduction method.
The elliptic curve on most Fq does meet the antiMOV attack conditions.
Before verifying the antiMOV 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 > 2191, B ≥ 27 is required. The selection of B ≥ 27 also
Appendix B
(Informative)
Number theory algorithm
B.1 Finite field and modulo operations
B.1.1 Exponential operations in finite fields
Let α be a positive integer, g be the element on the field Fq, the exponential
operation is the operation of calculating gα. The exponential operation can be
performed efficiently by the binary method outlined below.
Input. positive integer α, field Fq, field element g.
Output. gα.
a) Set e = a mod (q  1), if e = 0, then it outputs 1;
b) Let the binary representation of e be e = erer1...e1e0, 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 = x2;
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 nonzero element on the field Fq, then the inverse element g1 is the
field element c that makes g • c = 1. Since c = gq  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 g1 is an integer c, 1 ≤ c ≤ q  1, and g·c
≡1 (mod q).
Input. Field Fq, nonzero element g in Fq.
Output. Inverse element g1.
a) Calculate c = gq  2 (see B.1.1);
Output. If there is a square root of g, it outputs a square root mod p, otherwise,
it outputs “no square root exists”.
Algorithm 1. For p≡3 (mod 4), i.e., there is a positive integer u, such that p =
4u + 3.
a) Calculate y = gu + 1 mod p (see B.1.1);
b) Calculate z = y2 mod p;
c) If z = g, it outputs y; otherwise, it outputs “no square root exists”.
Algorithm 2. For p≡5 (mod 8), i.e., there is a positive integer u, such that p =
8u + 5.
a) Calculate z = g2u + 1 mod p (see B.1.1);
b) If z≡1 (mod p), calculate y = gu + 1 mod p, it outputs y and terminates the
algorithm;
c) If z≡1 (mod p), calculate y = (2g • (4g)u) mod p, it outputs y and terminates
the algorithm;
d) It outputs “no square root exists”.
Algorithm 3. For p≡1 (mod 8), i.e., there is a positive integer u, such that p =
8u + 1.
a) Set Y = g;
b) Generate a random number X, 0 < X < p;
c) Calculate the Lucas sequence element (see B.1.3). U = U4u + 1 mod p, V =
V4u + 1 mod p;
d) If V2≡4Y (mod p), it outputs y = (V/2) mod p and terminates;
e) If U mod p≠1 and U mod p≠p  1, it outputs “no square root exists” and
terminates;
f) Return to step b).
B.1.5 Trace function and half trace function
Let α be an element in , and the trace of α is.
The trace of half of the elements in is 0, the trace of half of the elements
Input. A large odd number u and a large positive integer T.
Output. “Probability prime number” or “composite number”.
a) Calculate v and odd number w, such that u  1 = 2v • w;
b) Execute j from 1 to T.
1) Select random number α in the interval [2, u  1];
2) Set b = aw mod u;
3) If b = 1 or u  1, go to step 6);
4) Execute i from 1 to v  1.
 Set b = b2 mod u;
 If b = u  1, go to step 6);
 If b = 1, it outputs “composite number” and terminates;
 Next i;
5) It outputs “composite number” and terminates;
6) Next j;
c) It outputs “probabilistic prime number”.
If the algorithm outputs “composite number”, then u is a composite number. If
the algorithm outputs “probabilistic prime number”, the probability that u is a
composite number is less than 22T. Thus, by choosing a sufficiently large T, the
error can be ignored.
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 lmaxsmooth. Given a positive integer
rmin, if there is a prime number v ≥ rmin such that a positive integer u = h • v, and
the integer h is lmaxsmooth, then u is called an approximate prime number. The
following algorithm checks the approximate primality of u.
Input. Positive integers u, lmax and rmin.
Output. It outputs h and v if u is an approximate prime, otherwise, it outputs “not
approximate prime”.
a) Set v = u, h = 1;
Appendix C
(Informative)
Curve example
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. y2 = x3 + ax + b
Example 1. Fp192 curve
Prime number p. BDB6F4FE 3E8B1D9E 0DA8C0D4 6F4C318C EFE4AFE3
B6B8551F
Coefficient α. 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. Fp256 curve
Prime number p. 8542D69E 4C044F18 E8B92435 BF6FF7DE 45728391
5C45517D 722EDB8B 08F1DFC3
Coefficient α. 787968B4 FA32C3FD 2417842E 73BBFEFF 2F3C848B
6831D7E0 EC65228B 3937E498
Coefficient b. 63E4C6D3 B23B0C84 9CF84241 484BFE48 F61D59A5
B16BA06E 6E12D1DA 27C5249A
Appendix D
(Informative)
Quasirandom generation and verification of parameters of elliptic curve
equation
D.1 Quasirandom generation of parameters of elliptic curve
equation
D.1.1 Quasirandom generation of parameters of elliptic curve equations
on Fp
Method 1.
Input. The size of the prime field p.
Output. Elements a, b in the bit string SEED and Fp.
a) Randomly select a bit string SEED which has a length of at least 192;
b) Calculate H = H256 (SEED) and record H = (h255, h254, ..., h0);
c) Set ;
d) Set r = R mod p;
e) Randomly select the elements a and b in Fp, so that r • b2≡a3 (mod p);
f) If (4a3 + 27b2) mod p = 0, then go to step a);
g) The elliptic curve on the selected Fp is E. y2 = x3 + ax + b;
h) Output (SEED, a, b).
Method 2.
Input. The size of the prime field p.
Output. Elements a, b in the bit string SEED and Fp.
a) Randomly select a bit string SEED which has a length of at least 192;
b) Calculate H = H256 (SEED) and record H = (h255, h254, ..., h0);
References
[1] GB/T 15843.11999 Information technology  Security technology  Entity
identification  Part 1. Overview
[2] GB/T 250692010 Information security technology  Terminology
[3] Agnew G, Beth T, Mullin R, et al. 1993. Arithmetic operations in GF(2m).
Journal of Cryptology, (6). 3~13
[4] Agnew G, Mullin R, Onyszchuk I, et al. 1991. An implementation for a fast
publickey cryptosystem. Journal of Cryptology, (3). 63~79
[5] ANSI X9.621999 Public Key Cryptography For The Financial Services
Industry. The Elliptic Curve Digital Signature Algorithm (ECDSA). American
National Standards Institute
[6] ANSIX 9.632001 Public Key Cryptography for the Financial Services
Industry. Key Agreement and key Transport Using Elliptic Curve Cryptography.
American Nation Standard Institute
[7] Brickell E, Gordon D, McCurley K, et al. 1993. Fast Exponentiation with
precomputation. Advances in CryptologyEUROCRYPT’92. LNCS 658. Berlin.
SpringerVerlag. 200~207
[8] Blake I, Serussi G, Smart N. 1999. Elliptic Curves in Cryptography.
Cambridge. Cambridge University Press
[9] ISO/IEC 159461.2002 Information technology  Security techniques 
Cryptographic techniques based on elliptic curves  Part 1. General
[10] ISO/IEC 159462.2002 Information technology  Security techniques 
Cryptographic techniques based on elliptic curves  Part 2. Digital signatures
[11] ISO/IEC 159463.2002 Information technology  Security techniques 
Cryptographic techniques based on elliptic curves  Part 3. Key establishment
[12] ISO/IEC 159464.2003 Information technology  Security techniques 
Cryptographic techniques based on elliptic curves  Part 4. Digital signatures
giving message recovery
[13] ITUT Recommendation X.680 Information Technology Abstract Syntax
Notation One (ASN.1). Specification of Basic Notation (eqv ISO/IEC 88241)
[14] ITUT Recommendation X.681 Information Technology Abstract Syntax
Notation One (ASN.1). Information Object Specification (eqv ISO/IEC 88242)
