1
/
of
12
PayPal, credit cards. Download editable-PDF and invoice in 1 second!
GM/T 0003.1-2012 English PDF (GMT0003.1-2012)
GM/T 0003.1-2012 English PDF (GMT0003.1-2012)
Regular price
$175.00 USD
Regular price
Sale price
$175.00 USD
Unit price
/
per
Shipping calculated at checkout.
Couldn't load pickup availability
Delivery: 3 seconds. Download true-PDF + Invoice.
Get QUOTATION in 1-minute: Click GM/T 0003.1-2012
Historical versions: GM/T 0003.1-2012
Preview True-PDF (Reload/Scroll if blank)
GM/T 0003.1-2012: Public key cryptographic algorithm SM2 based on elliptic curves - Part 1: General
GM/T 0003.1-2012
GM
CRYPTOGRAPHY INDUSTRY STANDARD
OF THE PEOPLE’S REPUBLIC OF CHINA
ICS 35.040
L 80
File No.. 36826-2012
Public key cryptographic algorithm SM2
based on elliptic curves - Part 1. General
ISSUED ON. MARCH 21, 2012
IMPLEMENTED ON. MARCH 21, 2012
Issued by. State Cryptography Administration
Table of Contents
Foreword ... 3
Introduction ... 4
1 Scope ... 5
2 Symbols and abbreviations ... 5
3 Field and elliptic curve ... 7
4 Data type and its conversion ... 13
5 Elliptic curve’s system parameters and verification ... 19
6 Key pair generation and public key verification ... 22
Annex A (Informative) Background knowledge about elliptic curves ... 24
Annex B (Informative) Number theory algorithm ... 57
Annex C (Informative) Curve examples ... 71
Annex D (Informative) Quasi-random generation and verification of parameters
of elliptic curve equation ... 74
Bibliography ... 77
Introduction
In 1985, N. Koblitz and V. Miller independently proposed the application of
elliptic curves to cryptographic algorithm. The nature of the curve on which the
elliptic curve’s public key cryptography is based is as follows.
- elliptic curves on a finite field form a finite exchange group under point
addition; the order is similar to the base field;
- similar to the power operation in the finite field multiplication group, the
elliptic curve multi-point-multiplication operation constitutes a one-way
function.
In the multiple-point-multiplication operation, the multiple-point-multiplication
and the base point are known, and the problem of solving the multiplication is
called the elliptic curve’s discrete logarithm problem. 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 problem and the discrete logarithm problem on the finite field,
the elliptic curve’s discrete logarithm problem is much more difficult to solve.
Therefore, elliptic curve ciphers are much smaller than other public key ciphers
required for the same level of security.
This Part describes the necessary mathematical basics and general techniques
to help implement the cryptographic mechanisms specified in the various
sections.
Public key cryptographic algorithm SM2
based on elliptic curves - Part 1. General
1 Scope
This Part of GM/T 0003 gives the necessary mathematical basics and
associated cryptography techniques for the SM2 elliptic curve’s public key
cryptographic algorithm to help implement the cryptographic mechanisms
specified in other parts.
This Part is applicable to the elliptic curve’s public key cryptographic algorithm
with the base field as the prime field and the binary extension field.
2 Symbols and abbreviations
The following symbols and abbreviations apply to this Part.
a, b. elements in Fq; they define an elliptic curve E on Fq.
B. M( )V threshold; positive number B makes it difficult to find the discrete
logarithm on at least as much as the discrete logarithm of the elliptic curve
on Fq.
deg (f). the number of polynomials f(x).
E. an elliptic curve defined by a and b over a finite field.
E(Fq). a set of all rational points of elliptic curve E on Fq (including infinity point
O).
ECDLP. elliptic curve’s discrete logarithm problem.
Fp. a prime field containing p elements.
Fq. a finite field containing q elements.
. multiplicative group consisting of all non-zero elements in Fq.
. binary extension field containing 2m elements.
b) The multiplication unit is an integer 1.
c) The addition of field elements is an integer modulo p addition, that is, if
, then a + b = (a + b) mod p.
d) The multiplication of field elements is the modulo p multiplication of
integers, that is, if , then .
3.1.3 Binary field
When q is a power of 2m, the binary extension can be regarded as an m-
dimensional vector space on F2, and its elements can be represented by a bit
string of length m.
There are many ways to represent elements in . The two most commonly
used methods are the polynomial base (PB) representation (see Annex A.2.1.1)
and the normal base (NB) representation (see Annex A.2.1.3). The principle of
base is to make the operation efficiency in as high as possible. This
Standard does not specify the choice of base. The following is a polynomial
base representation as an example to illustrate the binary extension field .
Let the irreducible polynomial
(where , i = 0, 1, ..., m-1) to the m power on F2 be a reduced polynomial
of the binary extension . 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,
called polynomial base. The coefficient of any element
in on F2 just constitutes a bit string of length
m, represented as .
a) Zero 0 is represented by an all-zero string.
b) Multiplication unit 1 is represented by bit string .
The known elliptic curve E(Fp), point with order of n and
, elliptic curve’s discrete logarithm problem refer that determining the
integer to make .
Elliptic curve’s discrete logarithm problem is related to the security of elliptic
curve’s cryptosystem, so it must choose a safe elliptic curve. For information on
how to choose a safe elliptic curve, see A.4 of Annex A.
3.2.6 Weak elliptic curve
If an elliptic curve has an attack method superior to level (n is the order of
the base point), the graph is a weak elliptic curve. It is forbidden to use weak
elliptic curve in this Standard.
The hypersingular curve on Fq (the characteristic divisible of
finite field Fq) and the Anomalous curve on Fq are weak elliptic
curves.
4 Data type and its conversion
4.1 Data type
In this Standard, data types include bit strings, byte strings, field elements,
points and integers on elliptic curves.
Bit string. ordered sequence of 0 and 1.
Byte string. an ordered sequence of bytes, where 8 bits are 1 byte.
Field element. Element in finite field Fq.
Point on elliptic curve. the point on the elliptic curve or a pair of
field elements ( ), where the field elements and satisfy the elliptic
curve equation, or the infinity point O.
The byte string representation of a point has multiple forms, which are identified
by a one-byte PC. The byte string representation of infinity point O is a single
zero byte PC=00. The non-infinity point has the following three
4.2.6 Conversion from field element to byte string
Input. element a in Fq.
Output. byte string S of length , where .
a) If q is an odd prime number, then a must be an integer in the interval [0,
q-1]. Convert a to a byte string S of length l according to the method of
4.2.2.
b) If q=2m, then a must be a bit string of length m. Convert a to a byte string
S of length l according to the method of 4.2.4.
4.2.7 Conversion from byte string to field element
Input. type of Fq, byte string S with length , where .
Output. element a in Fq.
a) If q is an odd prime number, convert S to an integer a according to the
method of 4.2.3. If , then report an error.
b) If q=2m, convert S to a bit string α of length m according to the method of
4.2.5.
4.2.8 Conversion from field element to integer
Input. element a in Fq.
Output. integer x.
a) If q is an odd prime, then x=a (no conversion required).
b) If q=2m, α must be a bit string of length m. Let sm-1, sm-2, ..., s0 be the ...
Get QUOTATION in 1-minute: Click GM/T 0003.1-2012
Historical versions: GM/T 0003.1-2012
Preview True-PDF (Reload/Scroll if blank)
GM/T 0003.1-2012: Public key cryptographic algorithm SM2 based on elliptic curves - Part 1: General
GM/T 0003.1-2012
GM
CRYPTOGRAPHY INDUSTRY STANDARD
OF THE PEOPLE’S REPUBLIC OF CHINA
ICS 35.040
L 80
File No.. 36826-2012
Public key cryptographic algorithm SM2
based on elliptic curves - Part 1. General
ISSUED ON. MARCH 21, 2012
IMPLEMENTED ON. MARCH 21, 2012
Issued by. State Cryptography Administration
Table of Contents
Foreword ... 3
Introduction ... 4
1 Scope ... 5
2 Symbols and abbreviations ... 5
3 Field and elliptic curve ... 7
4 Data type and its conversion ... 13
5 Elliptic curve’s system parameters and verification ... 19
6 Key pair generation and public key verification ... 22
Annex A (Informative) Background knowledge about elliptic curves ... 24
Annex B (Informative) Number theory algorithm ... 57
Annex C (Informative) Curve examples ... 71
Annex D (Informative) Quasi-random generation and verification of parameters
of elliptic curve equation ... 74
Bibliography ... 77
Introduction
In 1985, N. Koblitz and V. Miller independently proposed the application of
elliptic curves to cryptographic algorithm. The nature of the curve on which the
elliptic curve’s public key cryptography is based is as follows.
- elliptic curves on a finite field form a finite exchange group under point
addition; the order is similar to the base field;
- similar to the power operation in the finite field multiplication group, the
elliptic curve multi-point-multiplication operation constitutes a one-way
function.
In the multiple-point-multiplication operation, the multiple-point-multiplication
and the base point are known, and the problem of solving the multiplication is
called the elliptic curve’s discrete logarithm problem. 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 problem and the discrete logarithm problem on the finite field,
the elliptic curve’s discrete logarithm problem is much more difficult to solve.
Therefore, elliptic curve ciphers are much smaller than other public key ciphers
required for the same level of security.
This Part describes the necessary mathematical basics and general techniques
to help implement the cryptographic mechanisms specified in the various
sections.
Public key cryptographic algorithm SM2
based on elliptic curves - Part 1. General
1 Scope
This Part of GM/T 0003 gives the necessary mathematical basics and
associated cryptography techniques for the SM2 elliptic curve’s public key
cryptographic algorithm to help implement the cryptographic mechanisms
specified in other parts.
This Part is applicable to the elliptic curve’s public key cryptographic algorithm
with the base field as the prime field and the binary extension field.
2 Symbols and abbreviations
The following symbols and abbreviations apply to this Part.
a, b. elements in Fq; they define an elliptic curve E on Fq.
B. M( )V threshold; positive number B makes it difficult to find the discrete
logarithm on at least as much as the discrete logarithm of the elliptic curve
on Fq.
deg (f). the number of polynomials f(x).
E. an elliptic curve defined by a and b over a finite field.
E(Fq). a set of all rational points of elliptic curve E on Fq (including infinity point
O).
ECDLP. elliptic curve’s discrete logarithm problem.
Fp. a prime field containing p elements.
Fq. a finite field containing q elements.
. multiplicative group consisting of all non-zero elements in Fq.
. binary extension field containing 2m elements.
b) The multiplication unit is an integer 1.
c) The addition of field elements is an integer modulo p addition, that is, if
, then a + b = (a + b) mod p.
d) The multiplication of field elements is the modulo p multiplication of
integers, that is, if , then .
3.1.3 Binary field
When q is a power of 2m, the binary extension can be regarded as an m-
dimensional vector space on F2, and its elements can be represented by a bit
string of length m.
There are many ways to represent elements in . The two most commonly
used methods are the polynomial base (PB) representation (see Annex A.2.1.1)
and the normal base (NB) representation (see Annex A.2.1.3). The principle of
base is to make the operation efficiency in as high as possible. This
Standard does not specify the choice of base. The following is a polynomial
base representation as an example to illustrate the binary extension field .
Let the irreducible polynomial
(where , i = 0, 1, ..., m-1) to the m power on F2 be a reduced polynomial
of the binary extension . 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,
called polynomial base. The coefficient of any element
in on F2 just constitutes a bit string of length
m, represented as .
a) Zero 0 is represented by an all-zero string.
b) Multiplication unit 1 is represented by bit string .
The known elliptic curve E(Fp), point with order of n and
, elliptic curve’s discrete logarithm problem refer that determining the
integer to make .
Elliptic curve’s discrete logarithm problem is related to the security of elliptic
curve’s cryptosystem, so it must choose a safe elliptic curve. For information on
how to choose a safe elliptic curve, see A.4 of Annex A.
3.2.6 Weak elliptic curve
If an elliptic curve has an attack method superior to level (n is the order of
the base point), the graph is a weak elliptic curve. It is forbidden to use weak
elliptic curve in this Standard.
The hypersingular curve on Fq (the characteristic divisible of
finite field Fq) and the Anomalous curve on Fq are weak elliptic
curves.
4 Data type and its conversion
4.1 Data type
In this Standard, data types include bit strings, byte strings, field elements,
points and integers on elliptic curves.
Bit string. ordered sequence of 0 and 1.
Byte string. an ordered sequence of bytes, where 8 bits are 1 byte.
Field element. Element in finite field Fq.
Point on elliptic curve. the point on the elliptic curve or a pair of
field elements ( ), where the field elements and satisfy the elliptic
curve equation, or the infinity point O.
The byte string representation of a point has multiple forms, which are identified
by a one-byte PC. The byte string representation of infinity point O is a single
zero byte PC=00. The non-infinity point has the following three
4.2.6 Conversion from field element to byte string
Input. element a in Fq.
Output. byte string S of length , where .
a) If q is an odd prime number, then a must be an integer in the interval [0,
q-1]. Convert a to a byte string S of length l according to the method of
4.2.2.
b) If q=2m, then a must be a bit string of length m. Convert a to a byte string
S of length l according to the method of 4.2.4.
4.2.7 Conversion from byte string to field element
Input. type of Fq, byte string S with length , where .
Output. element a in Fq.
a) If q is an odd prime number, convert S to an integer a according to the
method of 4.2.3. If , then report an error.
b) If q=2m, convert S to a bit string α of length m according to the method of
4.2.5.
4.2.8 Conversion from field element to integer
Input. element a in Fq.
Output. integer x.
a) If q is an odd prime, then x=a (no conversion required).
b) If q=2m, α must be a bit string of length m. Let sm-1, sm-2, ..., s0 be the ...
Share











