GB/T 32918.1-2016 信息安全技术 sm2椭圆曲线公钥密码算法 第1部分：总则 GB/T32918.1-2016 标准压缩包解压密码：www.bzxz.net

ICS35.040
中华人民共和国国家标准
GB/T32918.1-—2016
信息安全技术
SM2椭圆曲线公钥密码算法
第1部分：总则
Information security technology-Public key cryptographic algorithm SM2 based on elliptic curves-Part1:General
2016-08-29发布
中华人民共和国国家质量监督检验检疫总局中国国家标准化管理委员会
2017-03-01实施
GB/T32918.1—2016
1范围
2符号和缩略语.
3域和椭圆曲线·
3.1有限域
3.2有限域上的椭圆曲线
4数据类型及其转换
4.1数据类型
4.2数据类型转换
5椭圆曲线系统参数及其验证
一般要求
F，上椭圆曲线系统参数及其验证·5.2
5.3F2上圆曲线系统参数及其验证：6密钥对的生成与公钥的验证
6.1密钥对的生成
公钥的验证：
附录A（资料性附录）关于圆曲线的背景知识素域F，
二元扩域F.
A.3椭圆曲线多倍点运算
A.4求解椭圆曲线离散对数问题的方法A.5椭圆曲线上点的压缩
附录B（资料性附录）
数论算法
有限域和模运算
有限域上的多项式Www.bzxZ.net
B.3椭圆曲线算法
附录C（资料性附录）曲线示例*C.1一般要求..
C.2F，上椭圆曲线
C.3F2上椭圆曲线
附录D（资料性附录）椭圆曲线方程参数的拟随机生成及验证D.1
椭圆曲线方程参数的拟随机生成D.2椭圆曲线方程参数的验证.·参考文献
GB/T32918《信息安全技术
第1部分：总则；
GB/T32918.1—2016
SM2圆曲线公钥密码算法》分为以下5个部分：第2部分：数字签名算法；
第3部分：密钥交换协议；
一第4部分：公钥加密算法；
第5部分：参数定义。
本部分为GB/T32918的第1部分。本部分按照GB/T1.1一2009给出的规则起草。本部分由国家密码管理局提出。本部分由全国信息安全标准化技术委员会（SAC/TC260)归口。本部分起草单位：北京华大信安科技有限公司、中国人民解放军信息工程大学、中国科学院数据与通信保护研究教育中心。
本部分主要起草人：陈建华、祝跃飞、叶顶峰、胡磊、裴定一、彭国华、张亚娟、张振峰。I
HiiKAoNhiKAca
GB/T32918.1—2016
N.Koblitz和V.Miller在1985年各自独立地提出将椭圆曲线应用于公钥密码系统。椭圆曲线公钥密码所基于的曲线性质如下：有限域上椭圆曲线在点加运算下构成有限交换群，且其阶与基域规模相近：类似于有限域乘法群中的乘幂运算，椭圆曲线多倍点运算构成一个单向函数。在多倍点运算中，已知多倍点与基点，求解倍数的问题称为椭圆曲线离散对数问题。对于一般椭圆曲线的离散对数问题，目前只存在指数级计算复杂度的求解方法。与大数分解问题及有限域上离散对数问题相比，椭圆曲线离散对数问题的求解难度要大得多。因此，在相同安全程度要求下，椭圆曲线密码较其他公钥密码所需的密钥规模要小得多。SM2是国家密码管理局组织制定并提出的椭圆曲线密码算法标准。GB/T32918的主要目标如下：GB/T32918.1定义和描述了SM2椭圆曲线密码算法的相关概念及数学基础知识，并概述了该部分同其他部分的关系。
一一GB/T32918.2描述了一种基于椭圆曲线的签名算法，即SM2签名算法。一GB/T32918.3描述了一种基于椭圆曲线的密钥交换协议，即SM2密钥交换协议。GB/T32918.4描述了一种基于椭圆曲线的公钥加密算法，即SM2加密算法，该算法需使用GB/T32905一2016定义的SM3密码杂凑算法。GB/T32918.5给出了SM2算法使用的圆曲线参数，以及使用圆曲线参数进行SM2运算的示例结果。
本部分为GB/T32918的第1部分，描述了必要的数学基础知识与一般技术，以帮助实现其他各部分所规定的密码机制。
HiKAoNniKAca
1范围
信息安全技术
SM2椭圆曲线公钥密码算法
第1部分：总则
GB/T32918.1—2016
GB/T32918的本部分规定了SM2椭圆曲线公钥密码算法涉及的必要数学基础知识与相关密码技术，以帮助实现其他各部分所规定的密码机制。本部分适用于基域为素域和二元扩域的圆曲线公钥密码算法的设计、开发、使用。2符号和缩略语
下列符号和缩略语适用于本文件。B
deg(f)
gcd(ty)
LeftRotate)
modf(a)
MOV阈。正数B，使得求取F，上的离散对数至少与求取F。上的圆曲线离散对数一样困难。
多项式f(工）的次数。
有限域上由α和b定义的一条椭圆曲线。F。上椭圆曲线E的所有有理点（包括无穷远点O)组成的集合。椭圆曲线离散对数问题。
包含力个元素的素域。
包含9个元素的有限域。
由F。中所有非零元构成的乘法群。包含2″个元素的二元扩域。
椭圆曲线的一个基点，其阶为素数。工和y的最大公因子。
余因子，h=#E（F，)/n，其中n是基点G的阶。循环左移运算。
余因子h的最大素因子的上界。
二元扩域F2关于F，的扩张次数。模多项式f（z）的运算。若（工）是二元域上的多项式，则所有系数执行模2运算。
模n运算。例如，23mod7=2。
基点G的阶[n是#E(F)的素因子]。椭圆曲线上的一个特殊点，称为无穷远点或零点，是椭圆曲线加法群的单位元。P=（pyp）是椭圆曲线上除O之外的一个点，其坐标工pVp满足椭圆曲线方程。
椭圆曲线E上两个点P,与P2的和。大于3的素数。
有限域F。中元素的数目。
HiiKAoNhiKAca
GB/T32918.1—2016
α-1 mod n
=y(modn)
#E(F。)
3域和椭圆曲线
3.1有限域
3.1.1概述
F，中的元素，它们定义F。上的一条椭圆曲线E。基点G的阶n的下界。
迹函数。
点P的工坐标。
使得r·y=1l（modn）成立的唯一整数y，lyp的点压缩表示。
整数模力的剩余类环。
基点G生成的循环群。
椭圆曲线上点P的k倍点，即：L]P=P十P十+P，其中k是正整数。西十
大于或等于工且小于或等于y的整数的集合。顶函数，大于或等于工的最小整数。例如，7=7，「8.3=9。底函数，小于或等于工的最大整数。例如，L7」=7，L8.3」=8。E（F。)上点的数目，称为椭圆曲线E(F。)的阶。长度相等的两个比特串按比特的异或运算。本条给出有限域F，的描述及其元素的表示，q是一个奇素数或者是2的方幂。当q是奇素数P时，要求p>2191，当q是2的方幕2\时，要求m>192且为素数。3.1.2素域F。
当g是奇素数p时，素域F，中的元素用整数0，1,2，，p一1表示。素域特性如下：a）加法单位元是整数0；
b）乘法单位元是整数1；
c）域元素的加法是整数的模p加法，即若a，bEF，，则a十b=（a十b)modp；d）域元素的乘法是整数的模p乘法，即若a，bEF，，则a·b=(a·b)modp。3.1.3二元扩域F2
当q是2的方幕2\时，二元扩域F2可以看成F2上的m维向量空间，其元素可用长度为m的比特串表示。
F2中的元素有多种表示方法，其中最常用的两种方法是多项式基（PB)表示（参见A.2.1.1）和正规基（NB)表示（参见A.2.1.3）。基的选择原则是使得F2中的运算效率尽可能高。本部分并不规定基的选择。下面以多项式基表示为例说明二元扩域F2。设F上m次不可约多项式f（）=r\+fm-1-1十.十f2+fi十f。（其中f.EF2，i=0,lm一1)是二元扩域F2的约化多项式。Fz由F2上所有次数低于m的多项式构成。多项式集合(工\-1，工-2，，工，1是F2在F2上的一组基，称为多项式基。F2中的任意一个元素a（）=2
HKAoNhiKAca
GB/T32918.1—2016
am-12\-1+am-2zm-2++a1+a在F.上的系数恰好构成了长度为m的比特串，用a=（am-1，am-2，,a1a）表示。多项式域特性如下：a）零元0用全0比特串表示；
b）乘法单位元1用比特串00001表示c）两个域元素的加法为比特串的按比特异或运算；d）域元素a和b的乘法定义如下：设a和b对应的F.上多项式为a（）和b(）,则a·b定义为多项式(a(r）b(r）)modf(a）对应的比特串。3.2有限域上的椭圆曲线
有限域F。上的椭圆曲线是由点组成的集合。在仿射坐标系下，椭圆曲线上点P（非无穷远点）的坐标表示为P=（工p，yp），其中工p，yp为满足一定方程的域元索，分别称为点P的坐标和y坐标。在本部分中，称F。为基域。
关于椭圆曲线更多的背景知识，参见附录A中A.1和A.2。在本部分中，如果不做特别说明，椭圆曲线上的点均采用仿射坐标表示。3.2.1F，上的椭圆曲线
定义在F，（p是大于3的素数）上的椭圆曲线方程为：y2=a+ar+ba，bEF且(4a+276)modp+0。椭圆曲线E(F，)定义为，参见C.2：E（F）=（（工y），yEF，且满足方程（1))U(O)，其中O是无穷远点。椭圆曲线E（F）上的点的数目用#E（F，）表示，称为椭圆曲线E（F，）的阶。3.2.2F2-上的椭圆曲线
定义在F2上的椭圆曲线方程为：y+ry=+ar+b，abEF，且b0。
椭圆曲线E（F2）定义为，参见C.3：E（F2）=（（，y）)zyEF2，且满足方程（2))U(O)，其中O是无穷远点。椭圆曲线E（F2）上的点的数目用#E（F2）表示，称为椭圆曲线E（F2）的阶。3.2.3椭圆曲线群
3.2.3.1F，上的椭圆曲线群
椭圆曲线E（F，）上的点按照下面的加法运算规则，构成一个交换群：a0+0=0;
b)VP=()EE(F,(O),P+O=O+P=P;
VP=（y)EEF(O),P的逆元素-P=（α，-y),P+（-P)=Oe
d）两个非互逆的不同点相加的规则：设P,=（)EE(F(O)P=(2)EE(FO)且2）设P，=(aya)=Pi+P2，则
式中：
ya(-)-y,
HiKAoNhi KAca
GB/T32918.1—2016
倍点规则：
设P,=(iy)EE(F)O)且i0P=(sy)=P+P则
[2—21
式中：
2F2上的椭圆曲线群
椭圆曲线E（F2）上的点按照下面的加法运算规则，构成一个交换群：a)0+0=0;
b）VP=(,y)EE(F2)(O),P+O=O+P=P;c）VP=(y)EE(F)(O),P的逆元素-P=（，r+y),P+（-P)=O两个非互逆的不同点相加的规则：d)
设P=（)EE(F(O)P=（)EE(FO)且2设P=（）=P+P2则
[r=+a+++a，
y=(+)+a+y1
式中：
e）倍点规则：
设P=（)(F2(O)且0P=()=P+P则
Jr=^\+aa，
lys=i+(+1)s,
式中：
3.2.4椭圆曲线多倍点运算
椭圆曲线上同一个点的多次加称为该点的多倍点运算。设是一个正整数，P是椭圆曲线上的点，称点P的次加为点P的倍点运算，记为Q=[]P=P+P++P。因为[]P=[k一1]P+P，所以倍点可以递归求得。
多倍点运算的输出有可能是无穷远点0。多倍点运算也可以通过一些技巧更有效地实现，参见附录A中A.3。3.2.5椭圆曲线离散对数问题（ECDLP）已知椭圆曲线E（F。）、阶为n的点GEE（F）及QE《G），椭圆曲线离散对数问题是指确定整数lE[o，n]，使得Q=[G成立。
椭圆曲线离散对数问题关系到椭圆曲线密码系统的安全，因此应选择安全的椭圆曲线。关于如何选择安全椭圆曲线，参见附录A中A.4。4
HiKAoNhi KAca
3.2.6弱椭圆曲线
GB/T32918.12016
若某椭圆曲线存在优于nl/级（n是基点的阶）计算复杂度的攻击方法，则称此曲线为弱椭圆曲线。在本部分中禁止使用弱椭圆曲线。F。上的超奇异曲线[有限域F，的特征整除g十1一#E（F）和F，上的异常（Anomalous）曲线［#E（F，）=P都是弱椭圆曲线。4数据类型及其转换
4.1数据类型
在本部分中，数据类型包括比特串、字节串、域元素椭圆曲线上的点和整数。比特串：有序的0和1的序列。
字节串：有序的字节序列，其中8比特为1个字节。域元素：有限域F。中的元素。
椭圆曲线上的点：椭圆曲线上的点PEE（F。），或者是一对域元素（，yp），其中域元素p和yp满足椭圆曲线方程，或者是无穷远点○。点的字节串表示有多种形式，用一个字节PC加以标识。无穷远点O的字节串表示是单一的零字节PC=00。非无穷远点P=（ap，yp)有如下三种字节串表示形式：a）压缩表示形式，PC=02或03；b）未压缩表示形式，PC=04；
c）混合表示形式，PC=06或07。注：混合表示形式既包含压缩表示形式又包含未压缩表示形式。在实现中，它允许转换到压缩表示形式或者未压缩表示形式。
对于椭圆曲线上点的压缩表示形式和混合表示形式，本部分中定为可选形式。椭圆曲线上点的压缩表示形式参见附录A中A.5。
4.2数据类型转换
4.2.1数据类型转换关系
图1提供了各种数据类型之间的转换关系，线上的标志是相应数据转换方法所在的条。域元素
比特串
字节申
图1数据类型和转换约定
HiKAoNhiKAca
GB/T32918.1—2016
4.2.2整数到字节串的转换
输人：非负整数工，以及字节串的目标长度（其中满足2>）。输出：长度为k的字节串M。
a）设M-1,M-2，，M。是M的从最左边到最右边的字节b）M的字节满足：
4.2.3字节串到整数的转换
输人：长度为k的字节串M。
输出：整数工。
a）设M-1,M-2，，M。是M的从最左边到最右边的字节；b）将M转换为整数：
4.2.4比特串到字节串的转换
输人：长度为m的比特串s。
输出：长度为的字节串M，其中k=「m/8]。设5m-1.Sm-2，*，5。是从最左边到最右边的比特；ai
b）设M.-1,M-2，M。是M从最左边到最右边的字节，则M,=s8i+7s8+ssi+1ss其中0输人：长度为的字节串M。
输出：长度为m的比特串s其中m=8k。a）设M-1.M-2，***,M是M从最左边到最右边的字节；设sm-1Sm-2，，5。是s从最左边到最右边的比特，则s是M,右起第i一8j十1比特，其中j=b)i
Li/8]。
4.2.6域元素到字节串的转换
输人：F。中的元素α。
输出：长度[=「t/8的字节串S，其中t=log2]。若9为奇素数，则α必为区间[0，9一1]中的整数，按4.2.2的方法把α转换成长度为1的字节a）
串S；
b）若g=2\，则α必为长度为m的比特串，按4.2.4的方法把α转换成长度为l的字节串S。4.2.7字节串到域元索的转换
输人：基域F，的类型，长度为=「t/8的字节串S，其中t=[log29。输出：F。中的元素α。
a】若q是奇素数，则按4.2.3的方法将S转换为整数α，若α[0.q一1]，则报错；b）若g=2，则按4.2.5的方法将S转换为长度为m的比特串α。6
4.2.8域元素到整数的转换
输人：域F。中的元素α。
输出：整数工。
a）若g为奇素数，则工=α（不需要转换）；GB/T32918.1—2016
b）若g=2”，则α必为长度为m的比特申，设sm-1，5m-2，\，S是α的从最左边到最右边的比特，将α转化为整数工：
4.2.9点到字节串的转换
输人：椭圆曲线上的点P=（工p，yp），且P≠O。输出：字节串S。若选用未压缩表示形式或混合表示形式，则输出字节串长度为21十1，若选用压缩表示形式，则输出字节串长度为1十1（1=[（log29）/8）。a）按4.2.6中的方法把域元素工p转换成长度为的字节串X，b）若选用压缩表示形式，则：
1）计算比特p（参见附录A中A.5）：2）若p=0，则令PC=02；若p=1，则令PC=03；3）字节串S=PCX
c）若选用未压缩表示形式，则：1）按4.2.6的方法把域元素yp转换成长度为1的字节串Y12）令PC=04：
3）字节串S=PCX,Yi#
d）若选用混合表示形式，则：
1）按4.2.6的方法把域元素yp转换成长度为1的字节串Y1；2）计算比特5p（参见附录A中A.5）3）若5p=0，则令PC=06；若5p=1，则令PC=07；4）字节串S=PCX，Yi。
4.2.10字节串到点的转换
输人定义F上椭圆曲线的域元素a，6，字节串S。若选用未压缩表示形式或混合表示形式，则字节串S长度为21+1：若选用压缩表示形式，则字节串PO长度为l+1(l=[（log2q）/8)。输出：椭圆曲线上的点P=（p，yp），且P≠O。a）若选用压缩表示形式，则S=PCX；若选用未压缩表示形式或混合表示形式，则S=PClX，Yi，其中PC是单一字节，X，和Y,都是长度为的字节串：b）按4.2.7的方法把字节串X，转换成域元素p；c）若选用压缩表示形式，则：
1）检验PC=02或者是PC=03，若不是这种情形，则报错；2）若PC=02，则令p=0；若PC=03.则令p=13）将（工e，p）转换为椭圆曲线上的一个点（p.yp）（参见附录A中A.5)；d）若选用未压缩表示形式，则：1）检验PC=04，若不是这种情形，则报错；7
GB/T32918.1—2016
2）按4.2.7的方法把字节串Y转换成域元素yp：e）若选用混合表示形式，则：
1）检验PC=06或者PC=07,若不是这种情形，则报错；2）执行步骤如下：
-按4.2.7的细节把字节串Y转换成域元素yp；若PC=06，则令p=0，否则令p=1：3）将（pp）转换为椭圆曲线上的一个点（p，yp)（参见附录A中A5)；f）若q为奇素数，则验证y=yi十atp十b（modg），若不是这种情形，则报错；若q=2\，则在F2中验证y十pyp=+ar+b，若不是这种情形，则报错；g)P=(tp.yp)。
5椭圆曲线系统参数及其验证
5.1一般要求
圆曲线系统参数是可以公开的，系统的安全性不依赖于对这些参数的保密。本部分不规定椭圆曲线系统参数的生成方法，但规定了系统参数的验证方法。精圆曲线阶的计算和基点的选取方法可参见附录B中B.3，曲线参数的生成方法可参见附录D。椭圆曲线系统参数按照基域的不同可以分为两种情形：一当基域是F（p为大于3的素数）时，F，上的椭圆曲线系统参数：—当基域是F2时，F上的椭圆曲线系统参数。5.2F，上椭圆曲线系统参数及其验证5.2.1F，上椭圆曲线系统参数
F，上椭圆曲线系统参数包括：
a）域的规模q=p，p是大于3的素数；b）（选项）一个长度至少为192的比特串SEED（若按照附录D描述的方法产生椭圆曲线）；c）F，中的两个元素a和b，它们定义椭圆曲线E的方程：y2=z\+ar+b；d）基点G=（GYG)EE(F,),GO;
基点G的阶n（要求：n>2191且n>4p1/2）e)
f）（选项）余因子h=#E（F）/n。5.2.2F，上椭圆曲线系统参数的验证椭圆曲线系统参数的生成者应验证下面的条件。椭圆曲线系统参数的用户可选择验证这些条件。输人：F，上椭圆曲线系统参数的集合。输出：若椭圆曲线系统参数是有效的，则输出有效”，否则输出“无效”。a）验证q=P是奇素数（参见附录B中B.1.10)；b）验证a，b，c和yc是区间[o，p一1]中的整数；若按照附录D描述的方法拟随机产生椭圆曲线，验证SEED是长度至少为192的比特串，且a，b由SEED派生得到：
d）验证（4a+276\）modp≠0；验证yc=r+az+b（modp)；
验证n是素数，n>2191且n>4p1/2（参见附录B中B.1.10）：8
小提示：此标准内容仅展示完整标准里的部分截取内容，若需要完整标准请到上方自行免费下载完整标准文档。