GB/T 32918.1-2016 PDF in English
GB/T 32918.1-2016 (GB/T32918.1-2016, GBT 32918.1-2016, GBT32918.1-2016)
| Standard ID | Contents [version] | USD | STEP2 | [PDF] delivered in | Name of Chinese Standard | Status |
| GB/T 32918.1-2016 | English | 365 |
Add to Cart
|
0-9 seconds. Auto-delivery.
|
Information security technology -- Public key cryptographic algorithm SM2 based on elliptic curves -- Part 1: General
| Valid |
Standards related to: GB/T 32918.1-2016
PDF Preview
GB/T 32918.1-2016: PDF in English (GBT 32918.1-2016) GB/T 32918.1-2016
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 extension-field ... 29
A.3 Elliptic curve’s multiple-point-multiplication 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) Quasi-random generation and verification of
parameters of elliptic curve equation ... 71
D.1 Quasi-random 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 non-zero 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 extension-field
When q is a power 2m 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) = xm + fm -1 x m - 1 + ... + f2x2 + f1x + f0 (where
fi∈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 {xm - 1, xm - 2, ..., x, 1} is a set of bases of on F2, which is called the
polynomial-base. The coefficient of any element a (x) = am-1xm-1 + am-2xm-2 + ...
+ 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 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 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
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
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 extension-field
Operation
Coordinate system
Affine coordinates standard projective coordinates
Jacobian weighted projective
coordinates
General addition (α≠0) 1I + 2M + 1S 15M + 1S 15M + 5S
Point-multiplication 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 multiple-point-multiplication 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 point-doubling and (W - 1)-times
point; algorithm 2 requires addition operation of l times elliptic curve’s point-
doubling and l/3-times point; algorithm 3 is divided into two parts. pre-
computation requires addition operation of a point-doubling operation and (2r - 1
- 1)-times point addition operation, the main loop part needs addition operation
of (l - 1) times of point-doubling operation and [l/(r + 1) - 1]-times point, totally,
it requires l times point-doubling operation and [2r - 1 + l/(r + 1) - 2]-times point
addition operation. Generally, there is W≈l/2, then the complexity of the
multiple-point-multiplication operation is as follows (when the base field is a
binary extension-field, 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 extension-field.
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;
• MOV-method. the ESPLP of super-singular elliptic curves and curves with
similar properties is reduced to the discrete logarithm problem on the small
extension-field of Fq (sub-exponential 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];
• GHS-method. Use the Weil descent technique to solve the discrete
logarithm problem of the elliptic curve on the binary extension-field 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 sub-exponential 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 sub-exponential level computational complexity are found.
For the discrete algorithm problems of some special curves, it exists the
polynomial level computational complexity or sub-exponential 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 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 > 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 = erer-1...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 non-zero element on the field Fq, then the inverse element g-1 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 g-1 is an integer c, 1 ≤ c ≤ q - 1, and g·c
≡1 (mod q).
Input. Field Fq, non-zero element g in Fq.
Output. Inverse element g-1.
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 2-2T. 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 lmax-smooth. 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 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 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. Fp-192 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. Fp-256 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)
Quasi-random generation and verification of parameters of elliptic curve
equation
D.1 Quasi-random generation of parameters of elliptic curve
equation
D.1.1 Quasi-random 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.1-1999 Information technology - Security technology - Entity
identification - Part 1. Overview
[2] GB/T 25069-2010 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
public-key cryptosystem. Journal of Cryptology, (3). 63~79
[5] ANSI X9.62-1999 Public Key Cryptography For The Financial Services
Industry. The Elliptic Curve Digital Signature Algorithm (ECDSA). American
National Standards Institute
[6] ANSIX 9.63-2001 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 Cryptology-EUROCRYPT’92. LNCS 658. Berlin.
Springer-Verlag. 200~207
[8] Blake I, Serussi G, Smart N. 1999. Elliptic Curves in Cryptography.
Cambridge. Cambridge University Press
[9] ISO/IEC 15946-1.2002 Information technology - Security techniques -
Cryptographic techniques based on elliptic curves - Part 1. General
[10] ISO/IEC 15946-2.2002 Information technology - Security techniques -
Cryptographic techniques based on elliptic curves - Part 2. Digital signatures
[11] ISO/IEC 15946-3.2002 Information technology - Security techniques -
Cryptographic techniques based on elliptic curves - Part 3. Key establishment
[12] ISO/IEC 15946-4.2003 Information technology - Security techniques -
Cryptographic techniques based on elliptic curves - Part 4. Digital signatures
giving message recovery
[13] ITU-T Recommendation X.680 Information Technology -Abstract Syntax
Notation One (ASN.1). Specification of Basic Notation (eqv ISO/IEC 8824-1)
[14] ITU-T Recommendation X.681 Information Technology -Abstract Syntax
Notation One (ASN.1). Information Object Specification (eqv ISO/IEC 8824-2)
......
Source: Above contents are excerpted from the PDF -- translated/reviewed by: www.chinesestandard.net / Wayne Zheng et al.
|