GB-T 32918.1-2016 信息安全技术 SM2椭圆曲线公钥密码算法 第1部分:总则.pdf
- 文档编号:14660554
- 上传时间:2023-06-25
- 格式:PDF
- 页数:46
- 大小:1.13MB
GB-T 32918.1-2016 信息安全技术 SM2椭圆曲线公钥密码算法 第1部分:总则.pdf
《GB-T 32918.1-2016 信息安全技术 SM2椭圆曲线公钥密码算法 第1部分:总则.pdf》由会员分享,可在线阅读,更多相关《GB-T 32918.1-2016 信息安全技术 SM2椭圆曲线公钥密码算法 第1部分:总则.pdf(46页珍藏版)》请在冰点文库上搜索。
ICS35.040L80中华人民共和国国家标准GB/T32918.12016信息安全技术SM2椭圆曲线公钥密码算法第1部分:
总则InformationsecuritytechnologyPublickeycryptographicalgorithmSM2basedonellipticcurvesPart1:
General2016-08-29发布2017-03-01实施中华人民共和国国家质量监督检验检疫总局中国国家标准化管理委员会发布知识星球https:
/次前言引言1范围12符号和缩略语13域和椭圆曲线23.1有限域23.2有限域上的椭圆曲线34数据类型及其转换54.1数据类型54.2数据类型转换55椭圆曲线系统参数及其验证85.1一般要求85.2Fp上椭圆曲线系统参数及其验证85.3F2m上椭圆曲线系统参数及其验证96密钥对的生成与公钥的验证96.1密钥对的生成96.2公钥的验证10附录A(资料性附录)关于椭圆曲线的背景知识11A.1素域Fp11A.2二元扩域F2m13A.3椭圆曲线多倍点运算23A.4求解椭圆曲线离散对数问题的方法26A.5椭圆曲线上点的压缩27附录B(资料性附录)数论算法29B.1有限域和模运算29B.2有限域上的多项式33B.3椭圆曲线算法35附录C(资料性附录)曲线示例37C.1一般要求37C.2Fp上椭圆曲线37C.3F2m上椭圆曲线37附录D(资料性附录)椭圆曲线方程参数的拟随机生成及验证39D.1椭圆曲线方程参数的拟随机生成39D.2椭圆曲线方程参数的验证40参考文献41GB/T32918.12016知识星球https:
/言GB/T32918信息安全技术SM2椭圆曲线公钥密码算法分为以下5个部分:
第1部分:
总则;第2部分:
数字签名算法;第3部分:
密钥交换协议;第4部分:
公钥加密算法;第5部分:
参数定义。
本部分为GB/T32918的第1部分。
本部分按照GB/T1.12009给出的规则起草。
本部分由国家密码管理局提出。
本部分由全国信息安全标准化技术委员会(SAC/TC260)归口。
本部分起草单位:
北京华大信安科技有限公司、中国人民解放军信息工程大学、中国科学院数据与通信保护研究教育中心。
本部分主要起草人:
陈建华、祝跃飞、叶顶峰、胡磊、裴定一、彭国华、张亚娟、张振峰。
GB/T32918.12016知识星球https:
/言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/T329052016定义的SM3密码杂凑算法。
GB/T32918.5给出了SM2算法使用的椭圆曲线参数,以及使用椭圆曲线参数进行SM2运算的示例结果。
本部分为GB/T32918的第1部分,描述了必要的数学基础知识与一般技术,以帮助实现其他各部分所规定的密码机制。
GB/T32918.12016知识星球https:
/M2椭圆曲线公钥密码算法第1部分:
总则1范围GB/T32918的本部分规定了SM2椭圆曲线公钥密码算法涉及的必要数学基础知识与相关密码技术,以帮助实现其他各部分所规定的密码机制。
本部分适用于基域为素域和二元扩域的椭圆曲线公钥密码算法的设计、开发、使用。
2符号和缩略语下列符号和缩略语适用于本文件。
BMOV阈。
正数B,使得求取FqB上的离散对数至少与求取Fq上的椭圆曲线离散对数一样困难。
deg(f)多项式f(x)的次数。
E有限域上由a和b定义的一条椭圆曲线。
E(Fq)Fq上椭圆曲线E的所有有理点(包括无穷远点O)组成的集合。
ECDLP椭圆曲线离散对数问题。
Fp包含p个元素的素域。
Fq包含q个元素的有限域。
Fq*由Fq中所有非零元构成的乘法群。
F2m包含2m个元素的二元扩域。
G椭圆曲线的一个基点,其阶为素数。
gcd(x,y)x和y的最大公因子。
h余因子,h=#E(Fq)/n,其中n是基点G的阶。
LeftRotate()循环左移运算。
lmax余因子h的最大素因子的上界。
m二元扩域F2m关于F2的扩张次数。
modf(x)模多项式f(x)的运算。
若f(x)是二元域上的多项式,则所有系数执行模2运算。
modn模n运算。
例如,23mod7=2。
n基点G的阶n是#E(Fq)的素因子。
O椭圆曲线上的一个特殊点,称为无穷远点或零点,是椭圆曲线加法群的单位元。
PP=(xP,yP)是椭圆曲线上除O之外的一个点,其坐标xP,yP满足椭圆曲线方程。
P1+P2椭圆曲线E上两个点P1与P2的和。
p大于3的素数。
q有限域Fq中元素的数目。
1GB/T32918.12016知识星球https:
/in基点G的阶n的下界。
Tr()迹函数。
xP点P的x坐标。
x-1modn使得xy1(modn)成立的唯一整数y,1yn-1,gcd(x,n)=1。
xyx与y的拼接,其中x和y是比特串或字节串。
xy(modn)x与y模n同余。
亦即,xmodn=ymodn。
yP点P的y坐标。
yPyP的点压缩表示。
Zp整数模p的剩余类环。
基点G生成的循环群。
kP椭圆曲线上点P的k倍点,即:
kP=P+P+Pk个,其中k是正整数。
x,y大于或等于x且小于或等于y的整数的集合。
x顶函数,大于或等于x的最小整数。
例如,7=7,8.3=9。
x底函数,小于或等于x的最大整数。
例如,7=7,8.3=8。
#E(Fq)E(Fq)上点的数目,称为椭圆曲线E(Fq)的阶。
长度相等的两个比特串按比特的异或运算。
3域和椭圆曲线3.1有限域3.1.1概述本条给出有限域Fq的描述及其元素的表示,q是一个奇素数或者是2的方幂。
当q是奇素数p时,要求p2191;当q是2的方幂2m时,要求m192且为素数。
3.1.2素域Fp当q是奇素数p时,素域Fp中的元素用整数0,1,2,p-1表示。
素域特性如下:
a)加法单位元是整数0;b)乘法单位元是整数1;c)域元素的加法是整数的模p加法,即若a,bFp,则a+b=(a+b)modp;d)域元素的乘法是整数的模p乘法,即若a,bFp,则ab=(ab)modp。
3.1.3二元扩域F2m当q是2的方幂2m时,二元扩域F2m可以看成F2上的m维向量空间,其元素可用长度为m的比特串表示。
F2m中的元素有多种表示方法,其中最常用的两种方法是多项式基(PB)表示(参见A.2.1.1)和正规基(NB)表示(参见A.2.1.3)。
基的选择原则是使得F2m中的运算效率尽可能高。
本部分并不规定基的选择。
下面以多项式基表示为例说明二元扩域F2m。
设F2上m次不可约多项式f(x)=xm+fm-1xm-1+f2x2+f1x+f0(其中fiF2,i=0,1,m-1)是二元扩域F2m的约化多项式。
F2m由F2上所有次数低于m的多项式构成。
多项式集合xm-1,xm-2,x,1是F2m在F2上的一组基,称为多项式基。
F2m中的任意一个元素a(x)=2GB/T32918.12016知识星球https:
/0001表示;c)两个域元素的加法为比特串的按比特异或运算;d)域元素a和b的乘法定义如下:
设a和b对应的F2上多项式为a(x)和b(x),则ab定义为多项式(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.1Fp上的椭圆曲线定义在Fp(p是大于3的素数)上的椭圆曲线方程为:
y2=x3+ax+b,a,bFp,且(4a3+27b2)modp0。
(1)椭圆曲线E(Fp)定义为,参见C.2:
E(Fp)=(x,y)|x,yFp,且满足方程
(1)O,其中O是无穷远点。
椭圆曲线E(Fp)上的点的数目用#E(Fp)表示,称为椭圆曲线E(Fp)的阶。
3.2.2F2m上的椭圆曲线定义在F2m上的椭圆曲线方程为:
y2+xy=x3+ax2+b,a,bF2m,且b0。
(2)椭圆曲线E(F2m)定义为,参见C.3:
E(F2m)=(x,y)|x,yF2m,且满足方程
(2)O,其中O是无穷远点。
椭圆曲线E(F2m)上的点的数目用#E(F2m)表示,称为椭圆曲线E(F2m)的阶。
3.2.3椭圆曲线群3.2.3.1Fp上的椭圆曲线群椭圆曲线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(Fp)O,且x1x2,设P3=(x3,y3)=P1+P2,则x3=2-x1-x2,y3=(x1-x3)-y1,式中:
=y2-y1x2-x1;3GB/T32918.12016知识星球https:
/F2m上的椭圆曲线群椭圆曲线E(F2m)上的点按照下面的加法运算规则,构成一个交换群:
a)O+O=O;b)P=(x,y)E(F2m)O,P+O=O+P=P;c)P=(x,y)E(F2m)O,P的逆元素-P=(x,x+y),P+(-P)=O;d)两个非互逆的不同点相加的规则:
设P1=(x1,y1)E(F2m)O,P2=(x2,y2)E(F2m)O,且x1x2,设P3=(x3,y3)=P1+P2,则x3=2+x1+x2+a,y3=(x1+x3)+x3+y1,式中:
=y1+y2x1+x2;e)倍点规则:
设P1=(x1,y1)E(F2m)O,且x10,P3=(x3,y3)=P1+P1,则x3=2+a,y3=x21+(+1)x3,式中:
=x1+y1x1。
3.2.4椭圆曲线多倍点运算椭圆曲线上同一个点的多次加称为该点的多倍点运算。
设k是一个正整数,P是椭圆曲线上的点,称点P的k次加为点P的k倍点运算,记为Q=kP=P+P+Pk。
因为kP=k-1P+P,所以k倍点可以递归求得。
多倍点运算的输出有可能是无穷远点O。
多倍点运算也可以通过一些技巧更有效地实现,参见附录A中A.3。
3.2.5椭圆曲线离散对数问题(ECDLP)已知椭圆曲线E(Fq)、阶为n的点GE(Fq)及Q,椭圆曲线离散对数问题是指确定整数l0,n-1,使得Q=lG成立。
椭圆曲线离散对数问题关系到椭圆曲线密码系统的安全,因此应选择安全的椭圆曲线。
关于如何选择安全椭圆曲线,参见附录A中A.4。
4GB/T32918.12016知识星球https:
/弱椭圆曲线若某椭圆曲线存在优于n1/2级(n是基点的阶)计算复杂度的攻击方法,则称此曲线为弱椭圆曲线。
在本部分中禁止使用弱椭圆曲线。
Fq上的超奇异曲线有限域Fq的特征整除q+1-#E(Fq)和Fp上的异常(Anomalous)曲线#E(Fp)=p都是弱椭圆曲线。
4数据类型及其转换4.1数据类型在本部分中,数据类型包括比特串、字节串、域元素、椭圆曲线上的点和整数。
比特串:
有序的0和1的序列。
字节串:
有序的字节序列,其中8比特为1个字节。
域元素:
有限域Fq中的元素。
椭圆曲线上的点:
椭圆曲线上的点PE(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数据类型和转换约定5GB/T32918.12016知识星球https:
/整数到字节串的转换输入:
非负整数x,以及字节串的目标长度k(其中k满足28kx)。
输出:
长度为k的字节串M。
a)设Mk-1,Mk-2,M0是M的从最左边到最右边的字节;b)M的字节满足:
x=k-1i=028iMi。
4.2.3字节串到整数的转换输入:
长度为k的字节串M。
输出:
整数x。
a)设Mk-1,Mk-2,M0是M的从最左边到最右边的字节;b)将M转换为整数x:
x=k-1i=028iMi。
4.2.4比特串到字节串的转换输入:
长度为m的比特串s。
输出:
长度为k的字节串M,其中k=m/8。
a)设sm-1,sm-2,s0是s从最左边到最右边的比特;b)设Mk-1,Mk-2,M0是M从最左边到最右边的字节,则Mi=s8i+7s8i+6s8i+1s8i,其中0ik,当8i+jm,02191且n4p1/2);f)(选项)余因子h=#E(Fp)/n。
5.2.2Fp上椭圆曲线系统参数的验证椭圆曲线系统参数的生成者应验证下面的条件。
椭圆曲线系统参数的用户可选择验证这些条件。
输入:
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)modp0;e)验证yG2xG3+axG+b(modp);f)验证n是素数,n2191且n4p1/2(参见附录B中B.1.10);8GB/T32918.12016知识星球https:
/F2m上椭圆曲线系统参数及其验证5.3.1F2m上椭圆曲线系统参数F2m上的椭圆曲线系统参数包括:
a)域的规模q=2m,对F2m中元素表示法(三项式基TPB、五项式基PPB或高斯正规基GNB)的标识,一个F2上的m次约化多项式(若所用的基是TPB或PPB);b)(选项)一个长度至少为192的比特串SEED(若按照附录D描述的方法拟随机产生椭圆曲线);c)F2m中的两个元素a和b,它们定义椭圆曲线E的方程:
y2+xy=x3+ax2+b;d)基点G=(xG,yG)E(F2m),GO;e)基点G的阶n(要求:
n2191且n22+m/2);f)(选项)余因子h=#E(F2m)/n。
5.3.2F2m上椭圆曲线系统参数的验证下面的条件椭圆曲线系统参数的生成者应加以验证。
这些条件椭圆曲线系统参数的用户可选择验证。
输入:
F2m上椭圆曲线系统参数的集合。
输出:
若椭圆曲线系统参数是有效的,则输出“有效”;否则输出“无效”。
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)验证b0;e)在F2m中验证yG2+xGyG=xG3+axG2+b;f)验证n是一个素数,n2191且n22+m/2(参见附录B中B.1.10);g)验证nG=O(参见附录A.3.2);h)(选项)计算h=(2m/2+1)2/n,验证h=h;i)验证抗MOV攻击条件成立(参见附录A中A.4.2.1);j)若以上任何一个验证失败,则输出“无效”;否则输出“有效”。
6密钥对的生成与公钥的验证6.1密钥对的生成输入:
一个有效的Fq(q=p且p为大于3的素数,或q=2m)上椭圆曲线系统参数的集合。
输出:
与椭圆曲线系统参数相关的一个密钥对(d,P)。
a)用随机数发生器产生整数d1,n-2;9GB/T32918.12016知识星球https:
/公钥的验证6.2.1Fp上椭圆曲线公钥的验证输入:
一个有效的Fp(p3且p为素数)上椭圆曲线系统参数集合及一个相关的公钥P。
输出:
对于给定的椭圆曲线系统参数,若公钥P是有效的,则输出“有效”;否则输出“无效”。
a)验证P不是无穷远点O;b)验证公钥P的坐标xP和yP是域Fp中的元素(即验证xP和yP是区间0,p-1中的整数);c)验证yP2xP3+axP+b(modp);d)验证nP=O;e)若通过了所有验证,则输出“有效”;否则输出“无效”。
6.2.2F2m上椭圆曲线公钥的验证输入:
一个有效的F2m上椭圆曲线系统参数集合及一个相关的公钥P。
输出:
对于给定的椭圆曲线系统参数,若公钥P是有效的,则输出“有效”;否则输出“无效”。
a)验证P不是无穷远点O;b)验证公钥P的坐标xP和yP是域F2m中的元素(即验证xP和yP是长度为m的比特串);c)在F2m中验证y2P+xPyP=x3P+ax2P+b;d)验证nP=O;e)若通过了所有验证,则输出“有效”;否则输出“无效”。
注:
公钥的验证是可选项。
01GB/T32918.12016知识星球https:
/录A(资料性附录)关于椭圆曲线的背景知识A.1素域FpA.1.1素域Fp的定义设p是一个素数,Fp由0,1,2,p-1中p个元素构成,称Fp为素域。
加法单位元是整数0,乘法单位元是整数1,Fp的元素满足如下运算法则:
加法:
设a,bFp,则a+b=r,其中r=(a+b)modp,r0,p-1。
乘法:
设a,bFp,则ab=s,其中s=(ab)modp,s0,p-1。
记F*p是由Fp中所有非零元构成的乘法群,由于F*p是循环群,所以在Fp中至少存在一个元素g,使得Fp中任一非零元都可以由g的一个方幂表示,称g为F*p的生成元(或本原元),即F*p=gi|0ip-2。
设a=giF*p,其中0ip-2,则a的乘法逆元为:
a-1=gp-1-i。
示例1:
素域F2,F2=0,1F2的加法表如表A.1,乘法表如表A.2:
表A.1+01001110表A.201000101示例2:
素域F19,F19=0,1,2,18F19中加法的示例:
10,14F19,10+14=24,24mod19=5,则10+14=5。
F19中乘法的示例:
7,8F19,78=56,56mod19=18,则78=18。
13是F19*的一个生成元,则F19*中元素可由13的方幂表示出来:
130=1,131=13,132=17,133=12,134=4,135=14,136=11,137=10,138=16,139=18,1310=6,1311=2,1312=7,1313=15,1314=5,1315=8,1316=9,1317=3,1318=1。
A.1.2Fp上椭圆曲线的定义A.1.2.1概述Fp上椭圆曲线常用的表示形式有两种:
仿射坐标表示和射影坐标表示。
11GB/T32918.12016知识星球https:
/仿射坐标表示当p是大于3的素数时,Fp上椭圆曲线方程在仿射坐标系下可以简化为y2=x3+ax+b,其中a,bFp,且使得(4a3+27b2)modp0。
椭圆曲线上的点集记为E(Fp)=(x,y)|x,yFp且满足曲线方程y2=x3+ax+bO,其中O是椭圆曲线的无穷远点。
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(Fp)O,P3=(x3,y3)=P1+P2O,则x3=2-x1-x2,y3=(x1-x3)-y1,其中=y2-y1x2-x1,若x1x2,3x12+a2y1,若x1=x2且P2-P1。
示例3:
有限域F19上一条椭圆曲线F19上方程:
y2=x3+x+1,其中a=1,b=1。
则F19上曲线的点为:
(0,1),(0,18),(2,7),(2,12),(5,6),(5,13),(7,3),(7,16),(9,6),(9,13),(10,2),(10,17),(13,8),(13,11),(14,2),(14,17),(15,3),(15,16),(16,3),(16,16),则E(F19)有21个点(包括无穷远点O)。
a)取P1=(10,2),P2=(9,6),计算P3=P1+P2:
=y2-y1x2-x1=6-29-10=4-1=-415(mod19),x3=152-10-9=225-10-916-10-9=-316(mod19),y3=15(10-16)-2=15(-6)-23(mod19),所以P3=(16,3)。
b)取P1=(10,2),计算2P1:
=3x12+a2y1=3102+122=35+14=164=4(mod19),x3=42-10-10=-415(mod19),y3=4(10-15)-2=-2216(mod19),所以2P1=(15,16)。
A.1.2.3射影坐标表示A.1.2.3.1标准射影坐标系当p是大于3的素数时,Fp上椭圆曲线方程在标准射影坐标系下可以简化为y2
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- GB-T 32918.1-2016 信息安全技术 SM2椭圆曲线公钥密码算法 第1部分:总则 GB 32918.1 2016 信息 安全技术 SM2 椭圆 曲线 密码 算法 部分 总则
![提示](https://static.bingdoc.com/images/bang_tan.gif)
链接地址:https://www.bingdoc.com/p-14660554.html