This part of GM/T 0003 specifies the necessary mathematical basics and related cryptographic techniques involved in public key cryptographic algorithm SM2 based on elliptic curves to help implement the cryptographic mechanisms specified in other parts.
This part applies to the elliptic curve public key cryptography algorithm with the base field being the prime field and the binary extension field.
2 Symbols and abbreviations
For the purpose of this part, the following symbols and abbreviations apply.
a, b: the elements in Fq, which defined an elliptic curve on Fq.
B: MOV threshold. Positive B, so that the obtaining the discrete logarithm of the number on is at least as difficult as obtaining the discrete logarithm of elliptic curve on Fq.
deg (f): the power of the polynomial f(x).
E: an elliptic curve defined by a and b on the finite field.
E (Fq): a set of all rational points of the elliptic curve E on Fq (including the infinity point O).
ECDLP: an elliptic curve discrete logarithm problem.
Fp: a prime field containing p elements.
Fq: a finite field containing q elements.
: a multiplicative group consisting of all non-zero elements in Fq.
: a binary extension containing 2m elements.
G: a base point of an elliptic curve whose order is a prime.
gcd (x,y): the greatest common factor of x and y.
h: cofactor, h — #E(Fq)/n, where n is the order of the base point G.
LeftRotate(): the looped left shift operation.
lmax: the upper bound of the largest prime factor of the cofactor h.
m: the number of extensions of binary extension regarding F2.
mod f(x): the operation of mod polynomial f(x). If f(x) is a polynomial on a binary field, then all coefficients perform mod-2 operation.
mod n: mod n operation. For example, 23 mod 7—2:
n: the order of the base point G (n is the prime element of E (Fq)).
O: a special point on the elliptic curve, called the infinity point or zero point, is the unit element of the elliptic curve addition group.
P: P— (xP, yP) is a point on the elliptic curve other than O, and its coordinates xP and yP satisfy the elliptic curve equation.
P1+P2: the sum of two points P1 and P2 on the elliptic curve E.
p: a prime number greater than 3.
q: the number of elements in the finite field Fq .
rmin: the lower bound of the order n of the base point G.
Tr(): trace function.
xP: the x coordinate of the point P.
x1 mod n: the only integer y making x·y=1(mod n) with 1≤y≤n-1, gcd(x,n)-1.
x ‖ y: the splicing of x and y, where x and y are bit strings or byte strings.
x=y(mod n): mod n of x and y is congruent. That is, x mod n—y=mod n.
yP: the y coordinate of the point P.
Foreword i Introduction ii 1 Scope 2 Symbols and abbreviations 3 Field and elliptic curve 3.1 Finite field 3.2 Elliptic curve on finite field 4 Data types and their conversion 4.1 Data type 4.2 Data type conversion 5 Elliptic curve system parameters and their verification 5.1 General requirements 5.2 System parameters of elliptic curves on Fp and their verification 5.3 System parameter of elliptic curves on and their verification 6 Key pair generation and public key verification 6.1 Key pair generation 6.2 Public key verification Annex A (Informative) Background knowledge about elliptic curves A.1 Prime field Fp A.2 Binary extension field A.3 Calculation of elliptic curve multi-points A.4 Solution to discrete logarithm problem of elliptic curve A.5 Compression of points on elliptic curves Annex B (Informative) Number-theoretic algorithm B.1 Finite field and mod operation B.2 Polynomials over a finite field B.3 Elliptic curve algorithm Annex C (Informative) Curve example C.1 General requirements C.2 Elliptic curve over Fp C.3 Elliptic curve over Annex D (Informative) Quasi-random generation and verification of elliptic curve equation parameters D.1 Quasi-random generation of elliptic curve equation parameters D.2 Verification of elliptic curve equation parameters Bibliography
1 Scope
This part of GM/T 0003 specifies the necessary mathematical basics and related cryptographic techniques involved in public key cryptographic algorithm SM2 based on elliptic curves to help implement the cryptographic mechanisms specified in other parts.
This part applies to the elliptic curve public key cryptography algorithm with the base field being the prime field and the binary extension field.
2 Symbols and abbreviations
For the purpose of this part, the following symbols and abbreviations apply.
a, b: the elements in Fq, which defined an elliptic curve on Fq.
B: MOV threshold. Positive B, so that the obtaining the discrete logarithm of the number on is at least as difficult as obtaining the discrete logarithm of elliptic curve on Fq.
deg (f): the power of the polynomial f(x).
E: an elliptic curve defined by a and b on the finite field.
E (Fq): a set of all rational points of the elliptic curve E on Fq (including the infinity point O).
ECDLP: an elliptic curve discrete logarithm problem.
Fp: a prime field containing p elements.
Fq: a finite field containing q elements.
: a multiplicative group consisting of all non-zero elements in Fq.
: a binary extension containing 2m elements.
G: a base point of an elliptic curve whose order is a prime.
gcd (x,y): the greatest common factor of x and y.
h: cofactor, h — #E(Fq)/n, where n is the order of the base point G.
LeftRotate(): the looped left shift operation.
lmax: the upper bound of the largest prime factor of the cofactor h.
m: the number of extensions of binary extension regarding F2.
mod f(x): the operation of mod polynomial f(x). If f(x) is a polynomial on a binary field, then all coefficients perform mod-2 operation.
mod n: mod n operation. For example, 23 mod 7—2:
n: the order of the base point G (n is the prime element of E (Fq)).
O: a special point on the elliptic curve, called the infinity point or zero point, is the unit element of the elliptic curve addition group.
P: P— (xP, yP) is a point on the elliptic curve other than O, and its coordinates xP and yP satisfy the elliptic curve equation.
P1+P2: the sum of two points P1 and P2 on the elliptic curve E.
p: a prime number greater than 3.
q: the number of elements in the finite field Fq .
rmin: the lower bound of the order n of the base point G.
Tr(): trace function.
xP: the x coordinate of the point P.
x1 mod n: the only integer y making x·y=1(mod n) with 1≤y≤n-1, gcd(x,n)-1.
x ‖ y: the splicing of x and y, where x and y are bit strings or byte strings.
x=y(mod n): mod n of x and y is congruent. That is, x mod n—y=mod n.
yP: the y coordinate of the point P.
Contents of GM/T 0003.1-2012
Foreword i
Introduction ii
1 Scope
2 Symbols and abbreviations
3 Field and elliptic curve
3.1 Finite field
3.2 Elliptic curve on finite field
4 Data types and their conversion
4.1 Data type
4.2 Data type conversion
5 Elliptic curve system parameters and their verification
5.1 General requirements
5.2 System parameters of elliptic curves on Fp and their verification
5.3 System parameter of elliptic curves on and their verification
6 Key pair generation and public key verification
6.1 Key pair generation
6.2 Public key verification
Annex A (Informative) Background knowledge about elliptic curves
A.1 Prime field Fp
A.2 Binary extension field
A.3 Calculation of elliptic curve multi-points
A.4 Solution to discrete logarithm problem of elliptic curve
A.5 Compression of points on elliptic curves
Annex B (Informative) Number-theoretic algorithm
B.1 Finite field and mod operation
B.2 Polynomials over a finite field
B.3 Elliptic curve algorithm
Annex C (Informative) Curve example
C.1 General requirements
C.2 Elliptic curve over Fp
C.3 Elliptic curve over
Annex D (Informative) Quasi-random generation and verification of elliptic curve equation parameters
D.1 Quasi-random generation of elliptic curve equation parameters
D.2 Verification of elliptic curve equation parameters
Bibliography
