GM/T 0044.12016 PDF in English
GM/T 0044.12016 (GM/T0044.12016, GMT 0044.12016, GMT0044.12016)
Standard ID  Contents [version]  USD  STEP2  [PDF] delivered in  Name of Chinese Standard  Status 
GM/T 00442016  English  RFQ 
ASK

3 days

See GM/T 0044.12016...GM/T 0044.52016 (SM9 identification cryptographic algorithm)
 Obsolete 
GM/T 0044.12016  English  370 
Add to Cart

09 seconds. Autodelivery.

Identitybased cryptographic algorithms SM9  Part 1: General
 Valid 
Standards related to (historical): GM/T 0044.12016
PDF Preview
GM/T 0044.12016: PDF in English (GMT 0044.12016) GM/T 0044.12016
GM
CRYPTOGRAPHY INDUSTRY STANDARD
OF THE PEOPLE’S REPUBLIC OF CHINA
ICS 35.040
L 80
File No.. 556182016
Identitybased cryptographic algorithms SM9 
Part 1. General
ISSUED ON. MARCH 28, 2016
IMPLEMENTED ON. MARCH 28, 2016
Issued by. State Cryptography Administration
Table of Contents
Foreword . 3
Introduction .. 4
1 Scope .. 5
2 Terms and definitions .. 5
3 Symbols and abbreviations . 6
4 Finite fields and elliptic curves .. 8
4.1 Finite fields . 8
4.2 Elliptic curves on finite fields .. 10
4.3 Elliptic curve groups .. 11
4.4 Multipoint operation of elliptic curves .. 12
4.5 Verification of points on elliptic curve subgroups.. 12
4.6 Discrete logarithm problems. 12
5 Bilinear pairings and safety curves .. 13
5.1 Bilinear pairings .. 13
5.2 Security . 13
5.3 Number of embedding and safety curves. 14
6 Data types and their conversion . 15
6.1 Data types .. 15
6.2 Data type conversion .. 15
7 System parameters and their verification . 21
7.1 System parameters .. 21
7.2 Verification of system parameters . 22
Annex A (informative) Background knowledge about elliptic curves .. 24
Annex B (informative) Calculation of bilinear pairings on elliptic curves .. 36
Annex C (informative) Number theory algorithm .. 49
Bibliography .. 58
Identitybased cryptographic algorithms SM9 
Part 1. General
1 Scope
This Part of GM/T 0044 describes the necessary basic knowledge of
mathematics and related cryptographic technology, to help implement the
cryptographic mechanisms specified in other parts of GM/T 0044.
This Part is applicable to the implementation, application and testing of
identification cryptography in commercial cryptographic algorithms.
This Part specifies and uses Fp (primenumber p > 2191) elliptic curves.
2 Terms and definitions
For the purpose of this document, the following terms and definitions apply.
2.1
identity
Information that uniquely identifies an entity. The identity shall be composed of
information that the entity cannot deny, such as identifiable name, email
address, ID number, phone number, street address, etc. of the entity.
2.2
signature master key
A key at the top of the key hierarchical structure of identitybased cryptography,
including master private key and master public key, where the master public
key is public and the master private key is kept secret by KGC. KGC uses
master private key and user identity to generate the user’s private key. In the
identitybased cryptography, master private key is generally generated by KGC
by a random number generator, and master public key is generated by master
private key in combination with system parameters.
In this Part, the signature system's master key is different from the encryption
system's master key. The digital signature algorithm belongs to the signature
system, and its master key is the signature master key; the key exchange
where K is the finite field (including Fq and Fqk).
< P>. cyclic group generated by element P.
[u]P. u times element P in addition group G1, G2.
[x, y]. a set of integers not less than x and not more than y.
ڿݔۀ. ceiling function, the minimum integer not less than x. For example, ڿ7ۀ =
7, ڿ8.3ۀ = 9.
ہݔۂ. floor function, the maximum integer not greater than x. For example, ہ7ۂ =
7, ہ8.3ۂ = 8.
β. twist curve parameter.
ψ. homomorphic map from G2 to G1, which satisfies P1 = ψ(P2).
⊕. modulo 2 addition operation, in bits, of two bitstrings of equal length.
4 Finite fields and elliptic curves
4.1 Finite fields
4.1.1 General
A filed consists of a nonempty set F and two kinds of operations. These two
kinds of operations are addition (represented by “+”) and multiplication
(represented by “•”), which satisfy the following arithmetic characteristics.
a) (F, +), for addition operation, forms an addition exchange group; the unit
element is represented by 0.
b) (F\{0}, •), for multiplication operation, forms a multiplicative exchange
group; the unit element is represented by 1.
c) The distribution law is true. for all a, b, c ∈ F, there is (a + b) • c = a • c + b
• c.
If the set F is a finite set, the filed is called a finite field. The number of elements
in a finite field is called the order of the finite field.
4.1.2 Prime field Fp
The finite field of which the order is prime is the prime filed.
Let p be a prime, then the set {0, 1, 2, ., p  1} of the all remainders of the
g in ܨ* that makes , g is called a generator. The
order of the elements a in ܨ is the smallest positive integer t that satisfies at
= 1. The order of the group ܨ* is qm  1, therefore t I qm  1.
Let the generator of the multiplicative cyclic group ܨ* be g, y ∈ ܨ*. The
discrete logarithm problem on finite fields refers to the determination of integer
x ∈ [0, qm  2] that makes y = gx true on ܨ*.
4.6.2 Elliptic curve discrete logarithm problem (ECDLP)
With known elliptic curve E(ܨ) (m ≥ 1), points P ∈ E(ܨ) and Q ∈ < P> with
the order of n, the elliptic curve discrete logarithm problem refers to the
determination of integer J ∈ [0, n  1] that makes Q = [l]P true.
5 Bilinear pairings and safety curves
5.1 Bilinear pairings
Let (G1, +), (G2, +) and (GT, •) be three cyclic groups, the order of G1, G2 and
GT be prime N, P1 be the generator of G1, and P2 be the generator of G2. There
is a homomorphism map ψ of G2 to G1 such that ψ(P2) = P1.
The bilinear pairing e is a map of G1 × G2 → GT and satisfies the following
conditions.
a) Bilinearity. For any P ∈ G1, Q ∈ G2, a, b ∈ ZN, there is e([a]P, [b]Q) = e(P,
Q)ab;
b) Nondegeneracy. ;
c) Computability. For any P ∈ G1, Q ∈ G2, there is an effective algorithm for
calculating e(P, Q).
The bilinear pairings used in this Part are defined on elliptic curve groups, which
mainly include Weil pairings, Tate pairings, Ate pairings and Rate pairings.
5.2 Security
The security of bilinear pairings is mainly based on the intractability of the
following problems.
Problem 1 (bilinear inverse DH (BIDH)). for a, b ∈ [1, N  1], with given ([a]P1,
[b]P2), it is difficult to calculate e(P1, P2)b/a.
Problem 2 (decisive bilinear inverse DH (DBIDH)). for a, b, r ∈ [1, N  1], it is
c) N  1 contains a prime factor greater than 2190;
d) N + 1 contains a prime factor greater than 2120.
6 Data types and their conversion
6.1 Data types
In this Part, data types include bit strings, byte strings, field elements, points on
elliptic curves and integers.
Bit strings. ordered sequences of 0 and 1.
Byte strings. ordered sequences of bytes, where 8 bits are 1 byte and the
leftmost bit is the most significant bit.
Field elements. elements on the finite field ܨ (m ≥ 1).
Points on elliptic curves. point P on the elliptic curve E(ܨ) (m ≥ 1) or infinity
point O, or a pair of filed elements (xP, yP) where the field elements xP and yP
satisfy the ellipse curve equation.
There are several representation forms of the byte string of points, which are
identified by one byte, PC. The representation form of the byte string of infinity
point O is a single zerobyte, PC = 00. Noninfinity point, P = (xP, yP), has the
following 3 representation forms of byte string.
a) compressed representation form, PC = 02 or 03;
b) uncompressed representation form, PC = 04;
c) mixed representation form, PC = 06 or 07.
NOTE. The mixed representation form includes both compressed and uncompressed
representation forms. In the implementation, it is allowed to be converted to the
compressed representation form or the uncompressed representation form. The
compressed representation form and the mixed representation form of points on elliptic
curves are specified as optional in this Part. For the compression form of points on
elliptic curves, see Annex A.4.
6.2 Data type conversion
6.2.1 Data type conversion relationship
Figure 1 shows the conversion relationship between various data types. The
mark on the line is the subclause where the corresponding data conversion
method is located.
6.2.7 Conversion from byte strings to field elements
Case 1. Converting to elements in the base field
Input. Field Fq, q = p; byte string S with length of l, l = ڿ݈݃ଶݍ/8ۀ.
Output. Element a in Fq.
If q = p, then convert S to integer a, according to the details of 6.2.3, if a ∉ [0, q
 1], an error is reported;
Case 2. Converting to elements in the extension field
Input. Field ܨ (m ≥ 2), q = p; byte string S with length of l, where l =
ڿ݈݃ଶݍ/8ۀ × m.
Output. Element a in ܨ.
a) Divide the byte string S into m segments, the length of each segment is
l/m, denoted as S = (Sm1, Sm2, ., S1, S0);
b) Execute i from m  1 to 0.
Convert Si to integer ai according to the details of 6.2.3, if ai ∉ [0, q  1],
an error is reported;
c) If q = p, output a = (am1, am2, ., a1, a0).
6.2.8 Conversion from points to byte strings
The conversion from points to byte strings is divided into two cases. one is that,
in the calculation process, the elliptic curve point can be used as the input of a
certain function (such as hash function) only after being converted to a byte
string; in this case it only needs to convert points directly to byte strings. One is
that, when transmitting or storing elliptic curve points, the compressed or mix
compressed representation form may be used to reduce the amount of
transmission or storage space; in this case, the onebyte identifier PC needs to
be added to indicate the representation form of points. The detailed conversion
process is described in two cases.
Case 1. Direct conversion
Input. Point P = (xP, yP) on the elliptic curve ܨ (m ≥ 1) and P ≠ 0.
Output. Byte string X1 ll Y1 with length of 2l. (When m=1, l = ڿ݈݃ଶݍ/8ۀ; when
m > 1, l = ڿ݈݃ଶݍ/8ۀ × m)...
...... Source: Above contents are excerpted from the PDF  translated/reviewed by: www.chinesestandard.net / Wayne Zheng et al.
