标准编号:	GB/T 32918.1-2016
中文名称:	信息安全技术 SM2椭圆曲线公钥密码算法 第1部分：总则
英文名称:	Information security techniques - Elliptic Curve public - key cryptography - Part 1: General
中标分类:	L80    数据加密
行业分类:	GB    国家标准
ICS分类:	35.040 35.040    字符集和信息编码 35.040
发布机构:	中华人民共和国国家质量监督检验检疫总局 中国国家标准化管理委员会
发布日期:	2016-08-29
实施日期:	2017-3-1
标准状态:	现行
翻译语言:	英文
文件格式:	PDF
中文字符数:	45000 字
翻译价格(元):	550.00 元
交付时间:	付款后 1 个工作日

GB/T 32918 Information security technology- Public key cryptographic algorithm SM2 based on elliptic curves consists of 5 parts:



—Part 1: General;



—Part 2: Digital signature algorithm;



—Part 3: Key exchange protocol;



—Part 4: Public key encryption algorithm;



—Part 5: Parameter definition.



This part is Part 1 of GB/T 32918.



This part is developed in accordance with the rules given in GB/T 1.1-2009.



This part was proposed by the State Cryptography Administration of the People’s Republic of China.



This part is under the jurisdiction of SAC/TC 260 (National Technical Committee 260 on Information Technology Security of Standardization Administration of China).



Drafting organizations of this part: Beijing Huada Infosec Technology Co., Ltd., The PLA Information Engineering University and DCS Center of Chinese Academy of Sciences.



Chief drafters of this part: Chen Jianhua, Zhu Yuefei, Ye Dingfeng, Hu Lei, Pei Dingyi, Peng Guohua, Zhang Yajuan and Zhang Zhenfeng. 

Introduction



N.Koblitz and V.Miller proposed the application of elliptic curves to public key cryptography respectively in 1985. The nature of the curve on which the public key cryptography of elliptic curve is based is as follows:



— The elliptic curve on the finite field constitutes a finite exchange group under the point addition, and its order is similar to the base field size;



— Similar to the power operation in the finite field multiplicative group, the elliptic curve multi-point operation constitutes a one-way function.



In the multi-point operation, the multiple points and the base point are known, and the problem of solving the multiple is called the discrete logarithm of elliptic curve. 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 problems and the discrete logarithm problems on the finite field, the discrete logarithm problem of elliptic curve is much more difficult to solve. Therefore, elliptic curve ciphers are much smaller than other public key ciphers at the same level of security.



SM2 is an elliptic curve cryptographic algorithm standard developed and proposed by the State Cryptography Administration. The main objectives of GB/T 32918 are as follows:



— GB/T 32918.1 defines and describes the relevant concepts and mathematical basics of the SM2 elliptic curve cryptographic algorithm, and summarizes the relationship between this part and other parts.



— GB/T 32918.2 describes a signature algorithm based on elliptic curve, i.e. SM2 signature algorithm.



— GB/T 32918.3 describes a key exchange protocol based on elliptic curve that is SM2 key exchange protocol.



— GB/T 32918.4 describes a public key encryption algorithm based on elliptic curve that is SM2 encryption algorithm, with the SM3 cryptographic hash algorithm defined in GB/T 32905-2016 adopted.



— GB/T 32918.5 defines the elliptic curve parameters used by the SM2 algorithm, and the sample results of the SM2 operation with the elliptic curve parameters.



As Part 1 of GB/T 32918, this part describes the necessary mathematical basics and general techniques to help implement the cryptographic mechanisms specified in other parts.

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 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 this part, the following symbols and abbreviations apply.



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: 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 (): 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 modulus polynomial f(x). If f(x) is a polynomial on a binary field, then all coefficients perform modulo-2 operation.



mod n: modulo-n operation. For example, 23 mod 7-2:



n: the order of the base point G (n is the prime factor 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 .



a,b: elements in Fq, which define a elliptic curve E on 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.



x-1 mod n: the only integer y making 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.

: modulo-n of x and y is congruence. That is, x mod n = y mod n.

yP: the y coordinate of the point P.

: the point compression representation of yP.



Zp : the remaining class ring of the integer modulus p.



: a cyclic group generated by the base point G.



[k]P: k multi-point of the point P on the elliptic curve, i.e:

, where k is a positive integer.



[x, y]: a set of integers greater than or equal to x and less than or equal to y.



: top function, the smallest integer greater than or equal to x. For example , .



: bottom function, the largest integer less than or equal to x. For example , .



#E (Fq): the number of points on E (Fq), called the order of the elliptic curve E (Fq).



㊉: two bit strings with equal length are subjected to bit XOR.



3 Field and elliptic curve



3.1 Finite field



3.1.1 General



This subclause gives a description of the finite field Fq and a representation of its element; q is an odd prime or a power of 2. Where q is an odd prime number p, p > 2191 is required; when q is a power of 2, 2m, m > 192 is required and m is a prime number.



3.1.2 Prime field Fp



Where q is an odd prime number p, the elements in the prime field Fp are represented by integers 0, 1, 2, …, p-1.The features of the prime field is as follows:



a) The addition unit element is integer 0;



b) The multiplication unit element is integer 1;



c) The addition of the field element is modulo p addition of integers, i.e. if a, b∈Fp, then a + b = (a + b) mod p;



d) The multiplication of the field elements is modulo p multiplication of integers, i.e., if a, b ∈Fp, then a•b = (a • b) mod p.



3.1.3 Binary extension field



Where q is a power of 2, 2m, the binary field can be seen as an F2 - dimensional vector space, whose elements can be represented by a bit string with length m.



There are many ways to represent elements in , where the two most commonly used methods are the polynomial basis (PB) representation (see Subclause A.2.1.1) and the normal basis (NB) representation (see Subclause A.2.1.3). Selection principle of base is to make the calculation efficiency of as high as possible. This standard does not specify the choice of the base. The following is a polynomial base representation as an example to illustrate the binary extension field .



Let the m power irreducible polynomial f(x) = xm + fm-1 xm-1 +...+ f2 x2 + f1x + f0 (where fi∈F2, i=0, 1, ..., m-1) on F2 be a reduced polynomial of a binary extension field . consists of all polynomials in the power of F2 less than m. The set of polynomials {xm-1, xm-2, ..., x, 1} is a set of bases of on F2 and called a polynomial basis. The coefficient of any one of the elements a(x) = am-1xm-1 + am-2xm-2 +...+ a1x + a0 in on F2 constitutes a bit string of length m, is expressed with a = (am-1, am-2, ..., a1, a0).The field features of polynomials are as follows:



a) Zero element 0 is represented by an all-zero bit string;



b) Multiplication unit 1 is represented by a bit string 00...001;



c) The addition of two field elements is subjected to bit XOR of bit strings.



d) The multiplication of the field elements a and b is defined as follows: let the polynomial of F2 corresponding to a and b be a(x) and b (x), then a•b is defined as the bit string corresponding to the polynomial (a (x) b (x)) mod f (x).



3.2 Elliptic curve on finite field



The elliptic curve on a finite field Fq is a set of points. In the affine coordinate system, the coordinates of the point P (non-infinity point) on the elliptic curve are expressed as P = (xP, yP), where xP, yP are field elements satisfying certain equations, and called respectively the x and y coordinates of the point P. In this standard, Fq is called a base field.



For more background knowledge on elliptic curves, see Subclauses A.1 and A.2 in Annex A.



In this standard, the points on the elliptic curve are represented by affine coordinates unless otherwise specified.



3.2.1 Elliptic curve on Fp



The elliptic curve equation defined on Fp (p is a prime number greater than 3) is:



y2 = x3 + ax + b, a, b ∈ Fp, and (4a3 + 27b2) mod p ≠ 0 (1)



The elliptic curve E (Fp) is defined as, as detailed in Subclause C.2:



E (Fp) = {(x,y)|x,y ∈ Fp, and they satisfy the equation (1)}∪{O}, where O is an infinity point.



The number of points on the elliptic curve E (Fp) is represented by #E (Fp), and called the order of the elliptic curve E (Fp).



3.2.2 Elliptic curve on



The elliptic curve equation defined on is:

y2 + xy = x3 + ax2 + b, a, b∈ , and b ≠ 0 (2)



Elliptic curve is defined as, as detailed in Subclause C.3:



, and meets the equation (2)}∪{O} where O is the infinity point.



The number of points on the elliptic curve is expressed with # , and called the order of elliptic curve .



3.2.3 Elliptic curve group



3.2.3.1 Elliptic curve group on Fp



The points on the elliptic curve E (Fp) constitute an exchange group according to the following addition rules:



a) O + O = O;



b) ∀P = (x,y)∈E(Fp)\{O}, P+O = O+P = P;



c) ∀P = (x, y)∈E(Fp)\{O}, the inverse element of P, -P = (x, -y), P + (-P) = O;



d) Addition rules for two different points that are not reciprocal:



Let P1 = (x1, y1)∈E(Fp)\{O}, P2 = (x2, y2)∈E(Fp)\{O}, and x1 ≠ x2,



Let P3 = (x3, y3) = P1 + P2, then







Where





e) Multi-point rules:



Let P1 = (x1, y1)∈E(Fp)\{O}, and y1 ≠ 0, P3 = (x3, y3) = P1 +P1,



Then







Where,



.



3.2.3.2 Elliptic curve group on



The points on the elliptic curve constitute an exchange group according to the following addition rules



a) O + O = O;



b) ∀P = (x, y)∈ \{O}, P + O= O + P = P;



c) ∀P = (x, y)∈ \{O}, the inverse element of P, - P = (x, x+y), P + (-P) = O;



d) Addition rules for two different points that are not reciprocal:



Let P1 = (x1, y1)∈ \{O}, P2 = (x2, y2)∈ \{O}, and x1 ≠ x2,



Let P3 = (x3, y3) = P1 + P2, then







Where







e) Multi-point rules:



Let P1 = (x1, y1)∈ \{O}, and x1 ≠ 0, P3 = (x3, y3) = P1 + P1, then







Where



.



3.2.4 Calculation of multi-points on elliptic curve



Multiple additions of the same point on an elliptic curve are called multi-point operations of that point. Let k be a positive integer, P be a point on the elliptic curve, and call k times’ addition as k multi-point operation of point P, denote it as . Because [k] P = [k-1] P + P, the multi-points can be recursively obtained.



The output of a multi- point operation may be at infinity point O.



The calculation of multi-point may also be fulfilled more effectively via some skills, as detailed in Subclause A.3 in Annex A.



3.2.5 Elliptic curve discrete logarithm problem (ECDLP)



Known elliptic curve E (Fq) at point of G∈E (Fq) and Q∈ with n order, the elliptic curve discrete logarithm problem is to determine the integer l∈[0, n-1], so that Q = [l] G is established.



The elliptic curve discrete logarithm problem is related to the security of elliptic curve cryptosystems, so a safe elliptic curve must be chosen. See Sublcause A.4 in Annex A for information on how to choose a safe elliptic curve.



3.2.6 Weak elliptic curve



If an elliptic curve has an attack method superior to order n1/2 (n is the order of the base point) to calculate the complexity, the curve is called a weak elliptic curve. Weak elliptic curves are prohibited in this standard.



Hyper-singular curve over Fq (where the characteristic exact division q + 1 - # E (Fq) in finite field Fq) and Anomalous curve (# E (Fq) = p) on the curve Fq are weak elliptical curves.



4 Data types and their conversion



4.1 Data type



In this standard, 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 where 8 bits are 1 byte.



Field elements: the elements in the finite field Fq.



A point on an elliptic curve: a point 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 dot has many forms and 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 representations. In an implementation, it allows conversion to a compressed representation or an uncompressed representation.



For compressed representations and mixed representations of points on elliptic curves, this standard is defined as an alternative form. See Subclause A.5 of Annex A for a compressed representation of the point on the elliptic curve.

Foreword i
Introduction ii
1 Scope
2 Symbols and abbreviations
3 Field and elliptic curve
3.1 Limited field
3.2 Elliptic curve on definite 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 multiplication 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 modulo 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

信息安全技术
SM2椭圆曲线公钥密码算法
第1部分：总则
1 范围
GB/T 32918的本部分规定了SM2椭圆曲线公钥密码算法涉及的必要数学基础知识与相关密码技术，以帮助实现其他各部分所规定的密码机制。
本部分适用于基域为素域和二元扩域的椭圆曲线公钥密码算法的设计、开发、使用。
2符号和缩略语
下列符号和缩略语适用于本文件。
B MOV阈。正数B，使得求取 上的离散对数至少与求取Fq上的椭圆曲线离散对数一样困难。
deg(f) 多项式f(x)的次数。
E 有限域上由a和b定义的一条椭圆曲线。
E(Fq) Fq上椭圆曲线E的所有有理点(包括无穷远点O)组成的集合。
ECDLP 椭圆曲线离散对数问题。
Fp 包含p个元素的素域。
Fq 包含q个元素的有限域。
Fq* 由Fq中所有非零元构成的乘法群。
包含2m个元素的二元扩域。
G 椭圆曲线的一个基点，其阶为素数。
gcd(x，y) x和y的最大公因子。
h 余因子，h=#E(Fq)/n，其中n是基点G的阶。
LeftRotate() 循环左移运算。
lmax 余因子h的最大素因子的上界。
m 二元扩域 关于F2的扩张次数。
modf(x) 模多项式f(x)的运算。若f(x)是二元域上的多项式，则所有系数执行模2运算。
mod n 模n运算。例如，23 mod 7=2。
n 基点G的阶[n是#E(Fq)的素因子]。
O 椭圆曲线上的一个特殊点，称为无穷远点或零点，是椭圆曲线加法群的单位元。
P P=(xp，yp)是椭圆曲线上除O之外的一个点，其坐标xP，yP满足椭圆曲线方程。
P1+P2 椭圆曲线E上两个点P1与P2的和。
p 大于3的素数。
q 有限域Fq中元素的数目。
a，b Fq中的元素，它们定义Fq上的一条椭圆曲线E。
rmin 基点G的阶n的下界。
Tr() 迹函数。
xP 点P的x坐标。
X-1 mod n 使得x·y≡1(mod n)成立的唯一整数y，1≤y≤n-1，gcd(x，n)=1。
x||y x与y的拼接，其中x和y是比特串或字节串。
x≡y(mod n) x与y模n同余。亦即，x mod n=y mod n。
yP 点P的y坐标。
yP的点压缩表示。
Zp 整数模p的剩余类环。
基点G生成的循环群。
[k]P 椭圆曲线上点P的k倍点，即： ，其中k是正整数。
[x，y] 大于或等于x且小于或等于y的整数的集合。
顶函数，大于或等于x的最小整数。例如， 。
底函数，小于或等于x的最大整数。例如， 。
#E(Fq) E(Fq)上点的数目，称为椭圆曲线E(Fq)的阶。
⊕ 长度相等的两个比特串按比特的异或运算。
3域和椭圆曲线
3.1 有限域
3.1.1 概述
本条给出有限域Fq的描述及其元素的表示，q是一个奇素数或者是2的方幂。当q是奇素数p时，要求p>2191；当q是2的方幂2m时，要求m>192且为素数。
3.1.2素域Fp
当q是奇素数p时，素域Fp中的元索用整数0，1，2，…，p-1表示。素域特性如下：
a)加法单位元是整数0；
b)乘法单位元是整数1；
c)域元素的加法是整数的模p加法，即若a，b∈Fp，则a+b=(a+b)mod p；
d)域元索的乘法是整数的模p乘法，即若a，b∈Fp，则a·b=(a·b)mod p。
3.1.3二元扩域
当q是2的方幂2m时，二元扩域 可以看成F2上的m维向量空间，其元素可用长度为m的比特串表示。
中的元素有多种表示方法，其中最常用的两种方法是多项式基(PB)表示(参见A.2.1.1)和正规基(NB)表示(参见A.2.1.3)。基的选择原则是使得 中的运算效率尽可能高。本部分并不规定基的选择。下面以多项式基表示为例说明二元扩域 。
设F2上m次不可约多项式f(x)=xm+fm-1xm-1+…+f2x2+f1x+f0(其中fi∈F2，i=0，1，…，m-1)是二元扩域 的约化多项式。 由F2上所有次数低于m的多项式构成。多项式集合{xm-1，xm-2，…，x，1}是 在F2上的一组基，称为多项式基。 中的任意一个元索a(x)=am-1xm-1+am-2xm-2+…+a1x+a0在F2上的系数恰好构成了长度为m的比特串，用a=(am-1，am-2，…，a1，a0)表示。多项式域特性如下：
a)零元0用全0比特串表示；
b)乘法单位元1用比特串00…001表示；
c) 两个域元素的加法为比特串的按比特异或运算；
d)域元素a和b的乘法定义如下：设a和b对应的F2上多项式为a(x)和b(x)，则a·b定义为多项式(a(x)b(x))modf(x)对应的比特串。
3.2有限域上的椭圆曲线
有限域Fq上的椭圆曲线是由点组成的集合。在仿射坐标系下，椭圆曲线上点P(非无穷远点)的坐标表示为P=(xP，yP)，其中xP，yP为满足一定方程的域元索，分别称为点P的x坐标和y坐标。在本部分中，称Fq为基域。
关于椭圆曲线更多的背景知识，参见附录A中A.1和A.2。
在本部分中，如果不做特别说明，椭圆曲线上的点均采用仿射坐标表示。
3.2.1 Fp上的椭回曲线
定义在Fp(p是大于3的素数)上的椭圆曲线方程为：
y2=x3+ax+b，a，b∈Fp，且(4a3+27b2)mod p≠0。 (1)
椭圆曲线E(Fp)定义为，参见C.2：
E(Fp)={(x，y)|x，y∈Fp，且满足方程(1)}∪{O}，其中O是无穷远点。
椭圆曲线E(Fp)上的点的数目用#E(Fp)表示，称为椭圆曲线E(Fp)的阶。
3.2.2 上的椭圆曲线
定义在 上的椭圆曲线方程为：
y2+xy=x3+ax2+b，a，b∈ ，且b≠0。 (2)
椭圆曲线E( )定义为，参见C.3：
E( )={(x，y)|x，y∈ ，且满足方程(2))∪{O}，其中O是无穷远点。
椭圆曲线E( )上的点的数目用#E( )表示，称为椭圆曲线E( )的阶。
3.2.3椭圆曲线群
3.2.3.1 Fp上的椭圆曲线群
椭圆曲线E(Fp)上的点按照下面的加法运算规则，构成一个交换群：
a) O+O=O；
b) P=(x，y)∈E(Fp)＼{O}，P+O=O+P=P；
c) P=(x，y)∈E(Fp)＼{O}，P的逆元索-P=(x，-y)，P+(-P)=O；
d)两个非互逆的不同点相加的规则：
设P1=(x1，y1)∈E(Fp)＼{O}，P2=(x2，y2)∈E(Ep)＼{O}，且x1≠x2，设P3=(x3，y3)=P1+P2，则

式中：

e) 倍点规则：
设P1=(x1，y1)∈E(Fp)＼{O}，且y1≠0，P3=(x3，y3)=P1+P1，
则

式中：

3.2.3.2 上的椭圆曲线群
椭圆曲线E( )上的点按照下面的加法运算规则，构成一个交换群：
a)O+O=O；
b) P=(x，y)∈E( )＼{O}，P+O=O+P=P；
c) P=(x，y)∈E( )＼{O}，P的逆元素-P=(x，x+y)，P+(-P)=O；
d)两个非互逆的不同点相加的规则：
设P1=(x1，y1)∈E( )＼{O}，P2=(x2，y2)∈E( )＼{O}，且x1≠x2，
设P3=(x3，y3)=P1+P2，则

式中：

e)倍点规则：
设P1=(x1，y1)∈E( )＼{O}，且x1≠0，P3=(x3，y3)=p1+P1，则

式中：

3.2.4 椭圆曲线多倍点运算
椭圆曲线上同一个点的多次加称为该点的多倍点运算。设k是一个正整数，P是椭圆曲线上的点，称点P的k次加为点P的k倍点运算，记为 ，因为[k]P=[k-1]P+P，所以k倍点可以递归求得。
多倍点运算的输出有可能是无穷远点O。
多倍点运算也可以通过一些技巧更有效地实现，参见附录A中A.3。
3.2.5 椭圆曲线离散对数问题(ECDLP)
已知椭圆曲线E(Fq)、阶为n的点G∈E(Fq)及Q∈，椭圆曲线离散对数问题是指确定整数l∈[0，n-1]，使得Q=[l]G成立。
椭圆曲线离散对数问题关系到椭圆曲线密码系统的安全，因此应选择安全的椭圆曲线。关于如何选择安全椭圆曲线，参见附录A中A.4。
3.2.6弱椭圆曲线
若某椭圆曲线存在优于n1/2级(n是基点的阶)计算复杂度的攻击方法，则称此曲线为弱椭圆曲线。在本部分中禁止使用弱椭圆曲线。
Fq上的超奇异曲线[有限域Fq的特征整除q+1-#E(Fq)]和Fp上的异常(Anomalous)曲线[#E(Fp)=p]都是弱椭圆曲线。
4数据类型及其转换
4.1数据类型
在本部分中，数据类型包括比特串、字节串、域元素、椭圆曲线上的点和整数。
比特串：有序的0和1的序列。
宇节串：有序的字节序列，其中8比特为1个字节。
域元素：有限域Fq中的元素。
椭圆曲线上的点：椭圆曲线上的点P∈E(Fq)，或者是一对域元紊(xP，yP)，其中域元素xP和yP满足椭圆曲线方程，或者是无穷远点O。
点的字节串表示有多种形式，用一个字节PC加以标识。无穷远点O的字节串表示是单一的零字节PC=00。非无穷远点P=(xP，yP)有如下三种字节串表示形式：
a)压缩表示形式，PC=02或03；
b)未压缩表示形式，PC=04；
c)混合表示形式，PC=06或07。
注：混合表示形式既包古压缩表示形式又包含未压缩表示形式。在实现中，它允许转换到压缩表示形式或者未压缩表示形式。
对于椭圆曲线上点的压缩表示形式和混合表示形式，本部分中定为可选形式.椭圆曲线上点的压缩表示形式参见附录A中A.5.
4.2数据类型转换
4.2.1数据类型转换关系
图1提供了各种数据类型之间的转换关系，线上的标志是相应数据转换方法所在的条。

域元素
比特串
字节串
整数
点
图1 数据类型和转换约定
4.2.2整数到字节串的转换
输入：非负整x，以及字节串的目标长度k(其中k满足28k>x)。
输出：长度为k的字节串M。
a)设Mk-1，Mk-2，…，M0是M的从最左边到最右边的字节；
b)M的字节满足：

4.2.3字节串到整数的转换
输入：长度为k的字节串M。
输出：整数x。
a)设Mk-1，Mk-2，…，M0是M的从最左边到最右边的字节；
b)将M转换为整数x：

4.2.4 比特串到字节串的转换
输入：长度为m的比特串s。
输出：长度为k的字节串M，其中k= 。
a)设sm-1，sm-2，…，s0是s从最左边到最右边的比特；
b)设Mk-1，Mk-2，…，M0是M从最左边到最右边的字节，则
Mi=s8i+7s8i+6…s8i+1s8i，其中0≤i2191且n>4p1/2)；
f) (选项)余因子h=#E(Fp)/n。
5.2.2 Fp上椭圆曲线系统参数的验证
椭圆曲线系统参数的生成者应验证下面的条件。椭圆曲线系统参数的用户可选择验证这些条件。
输入：Fp上椭圆曲线系统参数的集合。
输出：若椭圆曲线系统参数是有效的，则输出“有效”；否则输出“无效”。
a) 验证q=p是奇素数(参见附录B中B.1.10)；
b)验证a，b，xG和yG是区间[0，p-1]中的整数；
c)若按照附录D描述的方法拟随机产生椭圆曲线，验证SEED是长度至少为192的比特串，且a，b由SEED派生得到；
d)验证(4a3+27b2)modp≠0；
e) 验证yG2≡xG3+axG+b(modp)；
f) 验证n是素数，n>2191且n>4p1/2(参见附录B中B.1.10)；
g)验证[n]G=0(参见附录A中A.3)；
h)(选项)计算h′= ，并验证h=h′；
i) 验证抗MOV攻击条件和抗异常曲线攻击条件成立(参见附录A中A.4.2.1和A.4.2.2)；
j) 若以上任何一个验证失败，则输出“无效”；否则，输出“有效”。
5.3 上椭圆曲线系统参数及其验证
5.3.1 上椭圆曲线系统参数
上的椭圆曲线系统参数包括：
a) 域的规模q=2m，对 中元素表示法(三项式基TPB、五项式基PPB或高斯正规基GNB)的标识，一个F2上的m次约化多项式(若所用的基是TPB或PPB)；
b)(选项)一个长度至少为192的比特串SEED(若按照附录D描述的方法拟随机产生椭圆曲线)；
c) 中的两个元素a和b，它们定义椭圆曲线E的方程：y2+xy=x3+ax2+b；
d) 基点G=(xG，yG)∈E )，G≠O；
e)基点G的阶n(要求：n>2191且n>22+m/2)；
f) ( 项)余因子h=#E( )/n。
5.3.2 上椭圆曲线系统参数的验证
下面的条件椭圆曲线系统参数的生成者应加以验证。这些条件椭圆曲线系统参数的用户可选择验证。
输入： 上椭圆曲线系统参数的集合。
输出：若椭圆曲线系统参数是有效的，则输出“有效”；否则输出“无效”。
a)对某个m，验证q=2m；若所用的是TPB，则验证约化多项式是F2上的不可约三项式(参见表A.3)；若所用的是PPB，则验证不存在m次不可约三项式，且约化多项式是F2上的不可约五项式(参见表A.4)；若所用的是GNB，则验证m不能被8整除；
b) 验证a，b，xG和yG是长度为m的比特串；
c)若按照附录D描述的方法拟随机产生椭圆曲线，验证SEED是长度至少为192的比特串，且a，b由SEED派生得到；
d)验证b≠0；
e) 在 中验证yG+xGyG=xG3+axG2+b；
f) 验证n是一个素数，n>2191且n>22+m/2(参见附录B中B.1.10)；
g)验证[n]G=O(参见附录A.3.2)；
h)(选项)计算h′= ，验证h=h′；
i) 验证抗MOV攻击条件成立(参见附录A中A.4.2.1)；
j) 若以上任何一个验证失败.则输出“无效”；否则输出“有效”。
6 密钥对的生成与公钥的验证
6.1密钥对的生成
输入：一个有效的Fq(q=p且p为大于3的素数，或q=2m)上椭圆曲线系统参数的集合。
输出：与椭圆曲线系统参数相关的一个密钥对(d，P)。
a)用随机散发生器产生整数d∈[1，n-2]；
b)G为基点，计算点P=(xP，yP)=[d]G(参见附录A中A.3.2)；
c)密钥对是(d，P)，其中d为私钥，P为公钥。
6.2公钥的验证
6.2.1 Fp上椭圆曲线公钥的验证
输人：一个有效的F，(p>3且p为素数)上椭圆曲线系统参数集合及一个相关的公钥P。
输出：对于给定的椭圆曲线系统参数，若公钥P是有效的，则输出“有效”；否则输出“无效”。
a)验证P不是无穷远点O；
b)验证公钥P的坐标xP和yP是域F，中的元素(即验证xP和yP是区间[0，p-1]中的整数)；
c)验证yP2≡xP3+axP+b(modp)；
d)验证[n]P=O；
e)若通过了所有验证，则输出“有效”；否则输出“无效”。
6.2.2 上椭圆曲线公钥的验证
输入：一个有效的 上椭圆曲线系统参数集合及一个相关的公钥P。
输出：对于给定的椭圆曲线系统参数，若公钥P是有效的.则输出“有效”；否则输出“无效”。
a) 验证P不是无穷远点O；
b) 验证公钥P的坐标xP和yP是域 中的元素(即验证xP和yP是长度为m的比特串)；
c) 在 中验证yP2+xPyP=xP3+axP2+b；
d)验证[n]P=O；
e)若通过了所有验证，则输出“有效”；否则输出“无效”。
注：公钥的验证是可选项。
附 录A
(资料性附录)
关于椭圆曲线的背景知识
A.1 素域Fp
A.1.1 素域Fp的定义
设p是一个素数，Fp由{0，1，2，…，p-1}中p个元素构成，称Fp为素域。加法单位元是整数0，乘法单位元是整数1，Fp的元素满足如下运算法则：
——加法：设a，b∈Fp，则a+b=r，其中r=(a+b)modp，r∈[0，p-1]。
——乘法：设a，b∈Fp，则a·b=s，其中s=(a·b)modp，s∈[0，p-1]。
记Fp*是由Fp中所有非零元构成的乘法群，由于Fp*是循环群，所以在Fp中至少存在一个元素g，使得Fp中任一非零元都可以由g的一个方幂表示，称g为Fp*的生成元(或本原元)，即Fp*={gi|0≤i≤p-2}。设a=gi∈Fp*，其中0≤i≤p-2，则a的乘法逆元为：a-1=gp-1-i。
示例1：素域F2，F2={0，1}
F2的加法表如表A.1，乘法表如表A.2：