GB/T32918.1-2016
信息安全技术SM2椭圆曲线公钥密码算法第1部分：总则
Informationsecuritytechnology—PublickeycryptographicalgorithmSM2basedonellipticcurves—Part1:General
- 中国标准分类号（CCS）L80
- 国际标准分类号（ICS）35.040
- 实施日期2017-03-01
- 文件格式PDF
- 文本页数46页
- 文件大小769.49KB
以图片形式预览信息安全技术SM2椭圆曲线公钥密码算法第1部分：总则
信息安全技术SM2椭圆曲线公钥密码算法第1部分：总则
国家标准 GB/T32918.1一2016 信息安全技术 SM2椭圆曲线公钥密码算法 第1部分:总则 nformationsecurityteehnology PublickeyeryptographiealgorithmSM2basedon eliptie curves Part1:General 2016-08-29发布 2017-03-01实施 国家质量监督检验检疫总局 发布 国家标准化管理委员会国家标准
GB/T32918.1一2016 前 言 GB/T32918《信息安全技术SM2椭圆曲线公钥密码算法》分为以下5个部分 -第1部分:总则; 第2部分;数字签名算法; 第3部分:密钥交换协议 第4部分;公钥加密算法; 第5部分;参数定义
本部分为GB/T32918的第1部分
本部分按照GB/T1.1-2009给出的规则起草 本部分由国家密码管理局提出
本部分由全国信息安全标准化技术委员会(SAc/Tc280)归口
本部分起草单位;北京华大信安科技有限公司、人民解放军信息工程大学、科学院数据与 通信保护研究教育中心 本部分主要起草人;陈建华、祝跃飞、,叶顶峰、胡磊、裴定一、彭国华、张亚娟、张振峰
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.描述了一种基于椭圆曲线的公钥加密算法,即sM2加密算法,该算法需使用 (GB/T32905-2016定义的sM3密码杂凑算法
GB/T32918.5给出了SM2算法使用的椭圆曲线参数,以及使用椭圆曲线参数进行sM2运算 的示例结果
本部分为GB/T32918的第1部分,描述了必要的数学基础知识与一般技术,以帮助实现其他各部 分所规定的密码机制
GB/T32918.1一2016 信息安全技术 SM2椭圆曲线公钥密码算法 第1部分:总则 范围 GB/T32918的本部分规定了SM2椭圆曲线公钥密码算法涉及的必要数学基础知识与相关密码 技术,以帮助实现其他各部分所规定的密码机制
本部分适用于基域为素域和二元扩域的椭圆曲线公钥密码算法的设计,开发,使用
符号和缩略语 下列符号和缩略语适用于本文件 MOV阂
正数B,使得求取F
上的离散对数至少与求取F，上的椭圆曲线离 B 散对数一样困难
多项式(r)的次数 deg( 有限域上由a和b定义的一条椭圆曲线
E E(F, F，上椭圆曲线E的所有有理点(包括无穷远点O)组成的集合
ECDLP 椭圆曲线离散对数问题
包含个元素的素域
F 包含个元素的有限域 f 由F,中所有非零元构成的乘法群 F F” 包含2"个元素的二元扩域
G 椭圆曲线的一个基点,其阶为素数
gcd(.r,y r和y的最大公因子
余因子,h=#E(F,/n,其中n是基点G的阶
LeftRotate(O 循环左移运算
余因子h的最大素因子的上界
二元扩域F关于F,的扩张次数 1 模多项式(.r)的运算
若(.r)是二元域上的多项式,则所有系数执行模2 modf(r 运算
模n运算
例如,23mod7=2 modn 基点G的阶[n是#E(F,)的素因子]
2 椭圆曲线上的一个特殊点,称为无穷远点或零点,是椭圆曲线加法群的单位元
g ,)是椭圆曲线上除o之外的一个点,其坐标" 满足椭圆曲线 (.Zpp Zpy 方程
椭圆曲线E上两个点P与P,的和 PP 大于3的素数
有限域F,中元素的数目
GB/T32918.1一2016 F
中的元素,它们定义F
上的一条椭圆曲线E a.b 基点G的阶n的下界
rnmin Tr(O 迹函数
点P的
坐标
r" 使得ry=1modn)成立的唯一整数y,1
GB/T32918.1一2016 十air十a在F上的系数恰好构成了长度为m的比特串,用a=(a- C )表示
多项式域特性如下 ,a 零元0用全0比特串表示; b)乘法单位元1用比特串00001表示; c)两个域元素的加法为比特串的按比特异或运算 d域元素a和的乘法定义如下;设a和对应的F,上多项式为a(.r)和b(.r),则ab定义为 多项式(a(a)(r))modf(r)对应的比特串
3.2有限域上的椭圆曲线 有限域F
上的椭圆曲线是由点组成的集合
在仿射坐标系下,椭圆曲线上点P(非无穷远点)的坐 标表示为P=(r声,yp),其中工p,y,为满足一定方程的域元素,分别称为点尸的r坐标和y坐标
在 本部分中,称F
为基域
关于椭圆曲线更多的背景知识,参见附录A中A.1和A.2 在本部分中,如果不做特别说明,椭圆曲线上的点均采用仿射坐标表示
3.2.1r，上的椭圆曲线 定义在F,户是大于3的素数)上的椭圆曲线方程为 y'=r十a.rb,,bEF,,且(4a=+27b)modp0. 椭圆曲线E(F,)定义为,参见c.2 E(F,)=((r,y|.r,yEF,且满足方程(1U(o),其中o是无穷远点
椭圆曲线E(F,)上的点的数目用井E(F,)表示,称为椭圆曲线E(F,)的阶
3.2.2F上的椭圆曲线 定义在F上的椭圆曲线方程为: (2 =r十a=十b.a.hEF-.且去0. y"十ry 椭圆曲线E(F)定义为,参见C.3 E(F)=(r,y)|lx,yE下,且满足方程(2)U(o),其中0是无穷远点
椭圆曲线E(F)上的点的数目用#E(F)表示,称为椭圆曲线E(F)的阶
3.2.3椭圆曲线群 3.2.3.1F，上的椭圆曲线群 椭圆曲线E(F,上的点按照下面的加法运算规则,构成一个交换群 aO十0=(O; VP=(r,y)EE(F,八o.P+0=O+P=P; b VP=(r,y)EF,八o,尸的逆元素一P=(.r,一y),P+(一P)=O; d)两个非互逆的不同点相加的规则 设P=(.r1,y1))EE(F,\O,P,=(.r?,y)EE(F,八o),且.ri夭r 设P=(.r,y)=P十P,则 r;=入 ly;=入(ri一r)-y. 式中: y2 .r？ .Z
GB/T32918.1一2016 倍点规则 设P=(.r1,yi)E(F,\O),且y0,P,=(.ri,y,)=尸十尸" 则 Z3=入"一2.r1" ly;=入(.r1一.r.)一y1 式中 3.r十a 2y 3.2.3.2F上的椭圆曲线群 椭圆曲线E(F上的点按照下面的加法运算规则,构成一个交换群 O十O=O a VP=(r,y)EE(F\oO},P+O=O+P=P; P= =(r,y)EE(F八O),尸的逆元素一P=(r,r十y),P+(一P)=O; 两个非互逆的不同点相加的规则: 设P=(.ri,yi)EE(F\o),P=(.r?,y:)EE(F\O),且r1夭r 设P,=(r,y,)=P十P,则 .r;=入2
=十入十上i十上十a =入(.? ly3 .r1十r十.r3十y1 式中: y1十y" 入= .r1十r 倍点规则 e 设P=(r1,y1)EE(F八O),且.Ei0,P=(r,y.)=P十P,则 .r=入2十入十a， y;=ri+(a十1)ra 式中: 入=.Z1十 ,Z1 3.2.4椭圆曲线多倍点运算 椭圆曲线上同一个点的多次加称为该点的多倍点运算
设是一个正整数,P是椭圆曲线上的 点,称点P的人次加为点尸的人倍点运算,记为Q=[k]尸=P十P十十P
因为[]P=[人-1]P十 P,所以倍点可以递归求得
多倍点运算的输出有可能是无穷远点o 多倍点运算也可以通过一些技巧更有效地实现,参见附录A中A.3， 3.2.5椭圆曲线离散对数问题(ECDLP 已知椭圆曲线E(F,)阶为"的点GE(F,)及QE(G),椭圆曲线离散对数同题是指确定整数 e[O,n一1],使得Q=[]G成立
椭圆曲线离散对数问题关系到椭圆曲线密码系统的安全,因此应选择安全的椭圆曲线
关于如何 选择安全椭圆曲线,参见附录A中A.4
GB/T32918.1一2016 3.2.6弱椭圆曲线 若某椭圆曲线存在优于n'"级(n是基点的阶)计算复杂度的攻击方法,则称此曲线为弱椭圆曲线
在本部分中禁止使用弱椭圆曲线
r尸,上的超奇异曲线[有限域尸,的特征整除q十1一#E(F,)]和r,上的异常(Amlo)曲线 [井E(F,)=]都是弱椭圆曲线
数据类型及其转换 数据类型 在本部分中,数据类型包括比特串,字节串,域元素、椭圆曲线上的点和整数 比特串;有序的0和l的序列
字节串;有序的字节序列,其中8比特为1个字节
域元素;有限域F,中的元素 精圆曲线上的点;椭圆曲线上的点rEE(F,),或者是一对域元素(cpy,),其中域元素工，和》 满足椭圆曲线方程,或者是无穷远点O 点的字节串表示有多种形式,用一个字节PC加以标识
无穷远点O的字节串表示是单一的零字 节PC=00
非无穷远点P=(rp,y ,)有如下三种字节串表示形式 压缩表示形式,PC=02或03; a b未压缩表示形式,PC=04; c)混合表示形式,PC=06或07
注:混合表示形式既包含压缩表示形式又包含未压缩表示形式
在实现中,它允许转换到压缩表示形式或者未压 缩表示形式
对于椭圆曲线上点的压缩表示形式和混合表示形式,本部分中定为可选形式
椭圆曲线上点的压 缩表示形式参见附录A中A.5
4.2数据类型转换 4.2.1数据类型转换关系 图1提供了各种数据类型之间的转换关系,线上的标志是相应数据转换方法所在的条
4.2.8 域元素 4.2.6 4.2.7 4.2.5 4.2.2 整数 比特串 字节串 4.2.3 4.2.4 4.2.10 4.2.9 点 图1数据类型和转换约定
GB/T32918.1一2016 4.2.2整数到字节串的转换 输人:非负整数.r,以及字节串的目标长度k(其中卜满足2">r). 输出:长度为的字节串M
a 设M-1,NM-2,,M是M的从最左边到最右边的字节; bM的字节满足: 2M
4.2.3字节串到整数的转换 输人:长度为的字节串M
输出:整数工
设M-1,NM-2,,M是M的从最左边到最右边的字节; a b将M转换为整数r 2M 4.2.4比特串到字节串的转换 输人:长度为m的比特串、
输出:长度为的字节串M,其中k=「m/8]
a)设s ,s是、从最左边到最右边的比特; 1S朋一2 b设M-,M-g,,M是M从最左边到最右边的字节,则 s;s,其中0<1i
GB/T32918.1一2016 4.2.8域元素到整数的转换 输人;域F中的元素a
输出:整数r
a)若q为奇素数,则r=a(不需要转换); b若q=2",则a必为长度为m的比特串,设s前- -,,.s是a的从最左边到最右边的比特 ,Sm-2" 将a转化为整数r: 4.2.9点到字节串的转换 输人;椭圆曲线上的点尸=(fpyp),且尸-O. 输出字节串S
若选用未压缩表示形式或混合表示形式,则输出字节串长度为2l;若选用压 缩表示形式,则输出字节串长度为l十1(l=[og:)/8]
a)按4.2.6中的方法把域元素了,转换成长度为l的字节串X; b若选用压缩表示形式,则 计算比特y(参见附录A中A.5) 1 若y=0,则令PC=02;若y声=1,则令PC=03; 2) 3) 字节串s=Pc|Xi; 若选用未压缩表示形式,则 按4.2.的方法把域元素y,转换成长度为的字节串Y 1 令 2 PC=04; 3字节串s=Pc1XIY; 若选用混合表示形式,则 按4.2.的方法把域元素y,转换成长度为的字节串 2)计算比特y(参见附录A中A.5); 若y,=0,则令Pc=06;若y,=1,则令Pc=07. 3 4 字节串S=PC|XY 4.2.10字节串到点的转换 输人:定义F,上椭圆曲线的域元素a、b,字节串S
若选用未压缩表示形式或混合表示形式,则字 节串s长度为2十1;若选用压缩表示形式,则字节串Po长度为十1(/=[(log;q)/8]
输出;椭圆曲线上的点P=(rp,yp),且PO. 若选用压缩表示形式,则s=PCX1;若选用未压缩表示形式或混合表示形式,则S= a PCX，lY1,其中PC是单一字节.X和Y都是长度为1的字节串; b 按4.2.7的方法把字节串X转换成域元素rp; 若选用压缩表示形式,则 检验PC=02或者是PC=03,若不是这种情形,则报错 若PC=02,则令声=0;若PC=03,则令yp=1 2 3)将(rp,yp)转换为椭圆曲线上的一个点(.rp,yp参见附录A中A.5); 若选用未压缩表示形式,则: 检验PC=04,若不是这种情形,则报错;
GB/T32918.1一2016 2)按4.2.7的方法把字节串Y转换成域元素yp; 若选用混合表示形式,则 检验PC=06或者PC=07,若不是这种情形,则报错 2)执行步骤如下 按4.2.7的细节把字节串Y转换成域元素yp; 若PC=06,则令y;=0,否则令y，=1 了,)转换为椭圆曲线上的一 小yw)(参见附录A中A.5) 3)将(.r 个点(.r p 若9为奇素数,则验证=;十么r十(aadl),若不是这种情形,则报错 ，=r十ar十b,若不是这种情形,则报错; 若《=2",则在F中验证y十士py, P=(.r g .ryp
椭圆曲线系统参数及其验证 一般要求 5.1 椭圆曲线系统参数是可以公开的,系统的安全性不依赖于对这些参数的保密
本部分不规定椭圆 曲线系统参数的生成方法,但规定了系统参数的验证方法
椭圆曲线阶的计算和基点的选取方法可参 见附录B中B.3,曲线参数的生成方法可参见附录D. 椭圆曲线系统参数按照基域的不同可以分为两种情形 -当基域是F,(p为大于3的素数)时.F,上的椭圆曲线系统参数; 当基域是F时,F上的椭圆曲线系统参数
5.2F，上椭圆曲线系统参数及其验证 5.2.1！，上椭圆曲线系统参数 F，上椭圆曲线系统参数包括 a)域的规模q=是大于3的素数; b) 选项)一个长度至少为192的比特串SEED(若按照附录D描述的方法产生椭圆曲线 e F,中的两个元素
和b它们定义椭圆曲线E的方程:y=r'十ar十 d)基点G=(ra,ye)EE(F,),GO; b1/2); e)基点G的阶n(要求;n>2且n>4 (选项)余因子h=井E(F,/n
5.2.2！，上椭圆曲线系统参数的验证 椭圆曲线系统参数的生成者应验证下面的条件
椭圆曲线系统参数的用户可选择验证这些条件
输人;F上椭圆曲线系统参数的集合
输出;若椭圆曲线系统参数是有效的,则输出“有效”;否则输出“无效”
验证g=户是奇素数(参见附录B中B.1.10); 骑证 a,b,r
和y是区间[O,户-1]中的整数; 若按照附录D描述的方法拟随机产生椭圆曲线,验证SEED是长度至少为192的比特串,且 由SEED派生得到; b0; 验证4a十2762)1 )modp Eya"=r,十4ra十(modp); n>4p1"(参见附录B中B.1.10); 验证n是素数,n>2"且
GB/T32918.1一2016 g验证[nG=0(参见附录A中A.3); h)选项)计算h'=[p'a十1/n」,并验证h=h'; 验证抗MOV攻击条件和抗异常曲线攻击条件成立(参见附录A中A.4.2.1和A.4.2.2) iD 若以上任何一个验证失败,则输出“无效”;否则,输出“有效” 5.3F上椭圆曲线系统参数及其验证 5.3.1F上椭圆曲线系统参数 上的椭圆曲线系统参数包括 F" a)域的规模q=2",对F中元素表示法(三项式基TPB,五项式基PPB或高斯正规基GNB)的 标识，一个F,上的m次约化多项式(若所用的基是TPB或PPB); 选项)一个长度至少为192的比特串SEED(若按照附录D描述的方法拟随机产生椭圆 曲线); -'十ar=十 中的两个元素a和b,它们定义椭圆曲线E的方程;y=十ry- F" d)基点G=(.ra,y.)E(F),GO e)基点G的阶n(要求:n>21且n>2?十m/2). 选项)余因子h=井E(F)/n 5.3.2F上椭圆曲线系统参数的验证 下面的条件椭圆曲线系统参数的生成者应加以验证
这些条件椭圆曲线系统参数的用户可选择 验证 输人:;F上椭圆曲线系统参数的集合
输出:若椭圆曲线系统参数是有效的,则输出“有效”;否则输出“无效” 对某个m,验证q=2";若所用的是TPB,则验证约化多项式是F上的不可约三项式(参见 表A.3);若所用的是PPB,则验证不存在m次不可约三项式,且约化多项式是F
上的不可约 直项式(参见表A.4);若所用的是(GNB,则验证朋不能被8整除，
和y
是长度为"的比特串 b 验证a,b 若按照附录D描述的方法拟随机产生椭圆曲线,验证sEED是长度至少为192的比特串,且 a,b由SEED派生得到; D 验证b0; -中验证y 在F 十royG=rn十axro'十; 'e" (参见附录B中B.1.10); 2十m/2 -个素数,n>2" 验证n是一 】且n>2？" 验证[n]G=o(参见附录A.3.2). g h 选项)计算h'-l(2"胜十1'/n」.验证h一h' 验证抗MOV攻击条件成立(参见附录A中A.4.2.1); 若以上任何一个验证失败,则输出“无效”;否则输出“有效” 密钥对的生成与公钥的验证 6.1 密钥对的生成 输人;一个有效的F,(q=且卢为大于8的素数,或q=2")上椭圆曲线系统参数的集合
输出;与椭圆曲线系统参数相关的一个密钥对(d,P) 用随机数发生器产生整数dE[1,n-2]
GB/T32918.1一2016 bG为基点,计算点P=(工p,yp)=[d]G(参见附录A中A.3.2); 密钥对是(d,P),其中d为私钥,P为公钥
6.2 公钥的验证 6.2.1F，上椭圆曲线公钥的验证 输人;一个有效的F,p>3且p为素数)上椭圆曲线系统参数集合及一个相关的公钥P 输出;对于给定的椭圆曲线系统参数,若公钥P是有效的,则输出“有效”;否则输出“无效” 验证尸不是无穷远点O; b)验证公钥P的坐标r,和y,是域F,中的元素即验证r,和y,是区间[O,p-1]中的整数); 验证y,=上中十ar,十 mod); d验证E["]P=O 若通过了所有验证,则输出“有效”;否则输出“无效” 6.2.2F上椭圆曲线公钥的验证 输人:一个有效的F"上椭圆曲线系统参数集合及一个相关的公钥P 输出;对于给定的椭圆曲线系统参数,若公钥P是有效的,则输出“有效”;否则输出“无效” 验证P不是无穷远点O; a b验证公钥尸的坐标r,和y,是域F中的元素即验证r,和y,是长度为m的比特串); e)在F中验证y十ry,=r十ar十b， d)验证E[n]P=O; e)若通过了所有验证,则输出“有效”;否则输出“无效” 注:公钥的验证是可选项 10o
GB/T32918.1一2016 附 录A 资料性附录 关于椭圆曲线的背景知识 A.1素域！， 素域F，的定义 A.1.1 设是一个素数,F,由(0,1,2,,力一1)中个元素构成,称F,为素域
加法单位元是整数0,乘 法单位元是整数1,F,的元素满足如下运算法则 加法设a.beF,,则a十力一r,其中尸=(a十b)modp,E[O.p一1]
-乘法;设a.heF, b)modp,.sE[0,力一1]
,则a6=s,其中s=(a 记F;是由F,中所有非零元构成的乘法群,由于F;是循环群,所以在F,中至少存在一个元素g" 使得F,中任一非零元都可以由的一个方幕表示,称片为F，的生成元(或本原元),即F;={g|0< i<力-2)
设a=只'EF,其中0
GB/T32918.1一2016 标准射影坐标系下,E(F,)上点的加法运算定义如下: O十o=O: a b Vp=(.r,y,)EE(F,八o),P+O=O+p=P; P= (r,y,=)EE(F,八O),P的逆元素一P=(ur,一uy,uc),uEF,且u0,P+(一P)=O; dD 设点尸=(.riyi,)EE(F,\o},P=.r!,y!您)E(F八\o},P=尸十P，一 )O. r8y3,义 若P夭P,则 y2之1,入，=入一入s,入;=入1十入2,入
=1义2 '1之2人 Z2之1,人 1之2,人" =入3入11,y3=入(入g入1一入1)一入入10之=入1n入s; 若P ,则 =y=,入，=入;r1艾1,入;=入
”,A着=入i3一8A 2y113 A4入 2入s入a,您=入2入s
人2人6,y A.1.2.3.2,Jacobian加重射影坐标系 F,上椭圆曲线方程在Jacobian加重射影坐标系下可以简化为y=r=十a.r'十b
其中a,b F ,且4a276=夭0 modp
椭圆曲线上的点集记为E(F,)=(ry,2)lr,y,EF,且满足曲线方程 了十a.r之 十h-')
对于(rl,y,1)和(2?,y,2),若存在某个4eF,且u夭0,使得r=以' ,则称这两个三元组等价.表示同一个点
l”2,之1(之2 若=0,记X=r/e',Y=y/,则可从Jacobian加重射影坐标表示转化为仿射坐标表示;Y'- 十aX十b 文=0,(1,1,0)对应的仿射坐标系下的点即无穷远点o. 若 Jacobian加重射影坐标系下,E(F,上点的加法运算定义如下 O十O=O; a b VP=(.r,ys)EE(F,\O),P十0=O十P=尸; P=(r， y':)EE(F,\O),P的逆元素一P=(ur，一 ,u:),ueF,且u0,P十(一P)=O wy . 设点P =(c1y=)EE(F,\o),P=(ry=)EE(F,\(o),尸=尸十P- ,您O .Z -y3 若P关Pg,则 入e,入=y文',入;=y您 ,An=入一As,;=入i十入2, ,人， r1 =rs=,;=A 入
=入十入r 入;入”y=入,(a入
-入入3,义=1义2入3; 若P=P,则: 入1=3.r'十a心',A2=4.r1yi”,入，=8y',r=入12一2入2,y;=入入2一.r)一入3,您=2y1您1
A.1.3F，上椭圆曲线的阶 F,p为大于3的素数)上一条椭圆曲线的阶是指点集E(F,)中元素的个数,记为井E(F,)
由 几 Hwse定理知;/十1一p'<并E(r,)GB/T32918.1一2016 的向量空间,也就是说在F中存在m个元素a0,ai, n am一1,使得VaF,a可以唯一表示为 a=aa十aiai十十d那-a用-1,其中4EF
,称'a,ai,,a那-1}为F在F，上的一组基
给定这样 -组基,就可以由向量(ao,ai,,dm-1)来表示域元素a
F在F
上的基有多种选择,域元素的加法 在不同的基下的运算规则是一致的,都可以通过向量按分量异或运算得到;域元素的乘法在不同的基下 有不同的运算规则(如用多项式基表示和用正规基表示时其运算规则就不一致). A.2.1.1多项式基 设F上次不可约多项式f(r)=r"十fn-1r"一1十十fa.r"十fir十f.(其中fEFa,i=0,1. ,m一1)是二元扩域F的约化多项式
F由F上所有次数低于m的多项式构成,即 F=a朋-1.工 r十ala,EF2,i=0,l,,m一1}
---十1 ,r,1}是F作为向量空间在F,上的一组基,称为多项式基
多项式集合.r" 域元素a 相对多项式基可以由长度为川的比特串(d朋-1am一 a1.2 十a -十a1.T十ao a1a t0)来表示,所以 F朋=(a -1. (a-dm-;aid)la,EF,i=0,l,"" 乘法单位元1由(0001)表示,零元由(0000)表示
域元素的加法和乘法定义如下 加法运算 va ,bb.= .(6
-b
-=bb.)eF
,则(d
-d
-=d,d) a)+(w.b 2
a1a0， -1m ,其中c;=ab 1,亦即,加法运算按分位异或运算执行
.c1cn .i=0.l， c 1 乘法运算 ，则(a
bb= ，a a1a， b.h
Tdn (4n -1mr 是 -grir),其中多项式(" +d
十br十b,)在F上mod/(r)的余式
a1r十aob丽-14 注意,F恰包含2" 是由F中所有非零元构成的乘法群,F”是循环群,在 F中至少存在一个元素,使得F 非零元都可以由区的一个方幕表示,称区为下”的生成元 或本原元),即:F 2)
设a=g'EF”,其中0i2”一2,则a的乘法逆元为: 一g“" 示例4;二元扩域F;的多项式基表示 取F上的一个不可约多项式(x)=r'十？ =十1,则F中的元素是 (00000),(00001),(00010),(0001l),(00100),(00101),(00110), 0011),(o1000),(o1001),(o1o10),(o1o11),(o1100),(o1101). 01110),(01111),(10000),(10001),(10010),(10011),(10100)， (1o1o1),(10110),(1o111),(11000),(11001),(11o1o),(11011) 1ll00),(1l101),(1ll10),(1lll1 加法;(11011)+(I011)=(o1000) 乘法:(1101l)1001l)=(00100 .r十r了十r十1.r十r十1=r》十r了十r十r了十r十1 (r十.r十1)十r 十.r十1)除以/(.r)的余式
即.r"是(.r'十.r 乘法单位元是(00001) ),a=
是F”的一个生成元,则a的方幕为 a" =(00001),a'=(00010),a==(00100).a=(01000).a'=(10000),a'=(00101). =).a"wo)a"=( e" 01010).a了=(10100).a" 01101.e》 a口=(01110),a=(11100),a=(11101),a'=(11111),a“=(11011),a=(10011. al=(00011).al"=(o0110).a”=(o1100),a1=(11000).a=(10101).a=(o1111). 14
GB/T32918.1一2016 e? =(11110),a苔=(11001),a孩=(10111),a=(01011),a=(10110),a”=(01001). =(00001 a"=(10010)a= A.2.1.2三项式和五项式基 A.2.1.2.1概述 三项式基(TPB)和五项式基(PPB)是特殊的多项式基
A.2.1.2.2 三项式基 F上的三项式是形如.工"十r‘十1的多项式,其中1
GB/T32918.1一2016 vaEF,则a=aw8”"十a19" ,其中aFg,(i=0,l,,m一 -1),并记为a=(aaa1a" -1),域元素a由长度为m的比特串表示
所以F=(anaiaga
-a 1laEFg,0
GB/T32918.1一2016 利用域元素a和b乘积的第一项c,的公式,计算域元素a和b的乘积 对u= =(uauu
-1),v=(tuu-),设F(u,u)是以c,=F(a,b)导出的表达式 输人;大于1的整数m.正整数T(其中在F-上存在类型丁的高斯正规基B)及在高斯正规基 B表示下的两个域元素a、b
输出:积(ecc)=(aaa
)×(b.bb
置(u
a) =(ana l1"一 1**m-1; b) 置(们u-)=(b,b
-); 对人从0到m一1执行 c N 计算c=F(u,u); 2 置u=leftRotate(u),并置=LeftRotate(w),其中leftRotate()表示循环左移1位 运算,即L.edftRotate(a)=L.efRotate(w.,ud
-u-)=(wn u
-1u0); d)输出c=(ccic那- 在示例4中,用多项式乘法和带余除法描述了Fg,下面的示例5用高斯正规基表示F 示例5;二元扩域F的高斯正规基表示 F;域元素为比特五位组 (00000),(00001),(00010),(0001l),(00100),(00101),(00110),(001l1. l100),(o11o1),(o110),(oIl1) (o1000),(01001),(o1o10),(01011),(G 1 10000),(10001),(10010),(1001l),(10100),(10101),(10110),(1011l1)， 11000),(11001),(11010),(11011),(11100).(11101).(11110),(11111
+(,bb;b,b))=(eicrce:cici),其中ci,=a田b,,0
GB/T32918.1一2016 bP=(a",al),计算[2]P=(.r,ya): 入=.xr 2十1=a 十一-7 :十(a”十1)a=a'” 示例7:用型最优正规基表示F的椭圆曲线 取生成元a=(11000) )是其乘法单位元,则F”可由a生成， 01l00 11000). ll00) =(101l1)，a"=(01l10) 00001) a=(10010)，a口=(10100). (10000 11001 =(01111. 9=(00010 =(00101) (01001 10101 (00100)，a孩=(o1010) a=(o1011). 1011o). =(o11o1)，a=a"=(11l11
=(01000)， 十1,其中a=0,h=1
此方程可以表示如下 取一非超奇异曲线,方程为:y十ry 11111)y'十(11111).ry 11111).p'+(11111 这是因为乘法单位元为(1111 F上此曲线的点为: 0a ，Y 0 Y .a12 all) e3 包括无穷远点o),且E(Fa)是循环群 则E(F)有44 a',a'),按加法运算规则,有 [1]P .O [5]P [8]P []P [13]P [16] [17]P [20]1 [21]" F22 [25]P ,以" [32]P [29]" ,al 30r a0.0 35 [33P [34们P [36P [37]P [38]P [39P [40]P a C们]P” 42 43P [44]P=o ,a a,a21 A.2.2.3射影坐标表示 A.2.2.3.1标准射影坐标系 F"上非超奇异椭圆曲线方程在标准射影坐标系下可以简化为y'十zry=x》十a.r'十b',其中 a.hEF-,且b=0
E(F-)=((r.y,=)lr,y=EF-且满足曲线方程y=十ry这='十ar 2十 A" 对于(r ,,y,s1)和(a ?,,y,c),若存在某个uEF且u0,使得:;ri=从r!,yi=4y,s1=4c" b8 则称这两个三元组等价,表示同一个点
若==0记x一工/EY一y/s,则可从标准射影坐标表示转化为仿射坐标表示.Y'+XY一X+ aX2十b; 若茫=0,则0,l,0)对应的仿射坐标系下的点即无穷远点O 22
GB/T32918.1一2016 标准射影坐标系下,E(F)上点的加法运算定义如下 椭圆曲线E(Fm)上的点按照下面的加法运算规则,构成一个交换群 O十(O a b vP )EE(F\O),则PO=O十P=P .ry,您 EE(F\o,P的逆元素 =(ur,u(r十y),u:),uF且u0， p P 设点 r1y1怎1)EEF\o},P 怎2)EE(F\{O),P=PP= =.Z2y2" r2芯1,A》=入十入,入，=y1忽2,A;=y2芯1,A，=入十入
,入;=1您！,=入
" 真.A.a;一入,A,(G,十)十Aw十aa.,,,一入,Any,一A.(a,A十Am)+工 十 若 ,则 =入入
, =r,入,=入a十y1z1入，=入',A=A.(aj十入)+a1r 11 =入?入十s入
十ra,您=入A
A.2.2.3.2Jaeobia加重射影坐标系 F"上非超奇异椭圆曲线方程在Jacobian加重射影坐标系下可以简化为y'十.zy2=r'十4.r"、" b",其中a.hEF-,且6-0
E(F-)-((y.=)lr,y.=EF-且满足曲线方程十ys=！ ar==十b"y
对于(r1,y,s1)和(.r?,ye,s;),若存在某个uEF且u0,使得:r=u'r,y=uy ,则称这两个三元组等价,表示同一个点
之1=这》, 若交0,记X=r/e y/e=,则可从Jacobian加重射影坐标表示转化为仿射坐标表示Y”"十 xY-x'十4x'十; 若=0,则(1,l,0)对应的仿射坐标系下的点即无穷远点O
Jacobian加重射影坐标系下,E(F)上点的加法运算定义如下 椭圆曲线E(F)上的点按照下面的加法运算规则,构成一个交换群 P (.r,y,:)E(F八O,则P+O=O十P=P b r,y.)EE(F-\o).的逆元素一尸-(u=r,u'工十u'y.ue).uEF-且“0 设点 ,s1)EE(F)\O,P=(.r,yg,怎)EE(F八\o),P=P十P= .Z1，y1 ,则 r=，;=A,十A.,=yi二,;=y=,
=A,十入.A;==ia =a
十入n入，十入,y=入n.r十入s入了2; r1十b8,入=，十r2
+十yi=iy;=r's,十入r 11 A.2.3F上椭圆曲线的阶 F上的一条椭圆曲线E的阶是指点集E(F)中元素的个数,记为井E(F. 由Hasse定理知;2"十1一21十"儿<井E(F)<2"十12l十m" A.3椭圆曲线多倍点运算 A.3.1概述 设尸是椭圆曲线E上阶为N的点,k为正整数,尸的倍点为Q,即 23
GB/T32918.1一2016 Q=[]P=P十P十十P A.3.2椭圆曲线多倍点运算的实现 椭圆曲线多倍点运算的实现有多种方法,这里给出三种方法,以下都假设1<
GB/T32918.1一2016 -Q=[2i一十1]Q+P; 置j=！ l 输出Q A.3.3椭圆曲线多倍点运算复杂度估计 不同坐标系下椭圆曲线点加运算和倍点运算的复杂度如表A.6和表A.7
表A.6素域上椭圆曲线加法运算复杂度 标 坐 系 运 算 仿射坐标 标准射影坐标 加重射影坐标 Jacobian -般加法 1l+2M+1s 13M十2S 12M十4S 僧 点 1I十2M十2S 8M5S 4M十6S 表A.7二元扩域上椭圆曲线加法运算复杂度 坐 系 标 运 算 仿射坐标 标准射影坐标 Jacobian加重射影坐标 -般加法(a07 1I十2M十1s 15M+1s 15M十5S 倍 点 lI十2M2S 8M+3S 5M十5S 注:表中I、M和S分别表示有限域中的求逆运算、乘法运算和平方运算
计算多倍点Q=[]P,设人的比特数为l,k的Hamming重量为w,则算法一需要1一1次椭圆曲 线2倍点和w一1次点加运算;算法二需要1次椭圆曲线2倍点和l/3次点加运算;算法三分两部分 预计算时需要一次2倍点运算和2-1一1次点加运算,主循环部分需要1-1次2倍点运算和/(r十1)-1 次点加运算,共需要1次2倍点运算和2-1十1/(r十1)一2次点加运算
一般有w~1/2,则多倍点运 算的复杂度如下(基域为二元扩域时,假设40,当4=0时,少一次乘法运算) 算法一: 基域为素域 仿射坐标下的复杂度 1.5I十3M十2.5/s 标准射影坐标下的复杂度 14.5M十6s Jacobian加重射影坐标下的复杂度:10M+8s 基域为二元扩域 仿射坐标下的复杂度 1.51+3M2.5s 标准射影坐标下的复杂度: 15.5/M十3.5/S Jacobian加重射影坐标下的复杂度:12.5/M+7.5/s 算法二 基域为素域 仿射坐标下的复杂度 1.33/I2.67M十2.33/S 12.33M十5.671S 标准射影坐标下的复杂度: Jacobian加重射影坐标下的复杂度: 8/M十7.33S 基域为二元扩域 1.33I十2.67M十2.33S 仿射坐标下的复杂度 25
GB/T32918.1一2016 标准射影坐标下的复杂度 13M十3.33S Jacobian加重射影坐标下的复杂度:10M+6.67IS 算法三: 基域为素域 仿射坐标下的复杂度 /十1/(r十1)十2-'一2)(2M+I+S)十1s l/(r十1十2"-1一2)(13M十2S)十l(8M十5S) 标准射影坐标下的复杂度 /(r十1十2r-1一2)(12M十4S)十l(4M十6S Jacobian加重射影坐标下的复杂度 基域为二元扩域 仿射坐标下的复杂度 /十1/(r十1)十2r-'一2)(2MIS)十1s l/(r十1十2-1一2)(15M十1S)十l(8M十3S 标准射影坐标下的复杂度: l/(r十1十2-一2)(15M5S)十l(5M十5S Jacobian加重射影坐标下的复杂度: A.4求解椭圆曲线离散对数问题的方法 A.4.1椭圆曲线离散对数求解方法 已知椭圆曲线E(F,),阶为》的点PEE(F,)及Q《P>,椭圆曲线离散对数问题是指确定整数 k[O,-1],使得Q=[]P成立
EECDLP现有攻击方法有 Pohlig-Hellman方法:设1是n的最大素因子,则算法复杂度为o('3):; BBsGS方法;时间复杂度与空间复杂度均为(Tn/2 Polard方法:算法复杂度为(Tn/2)1 并行Pollard方法;设r为并行处理器个数,算法复杂度降至(Tn/2)'2/r; MOV-方法;把超奇异椭圆曲线及具有相似性质的曲线的ECDLP降到F,的小扩域上的离散对 数问题亚指数级计算复杂度算法) 异常曲线离散对数求解方法;对异常曲线[井E(F,)=的曲线]的有效攻击方法(多项式级计 算复杂度算法) GHs方法;利用wedil下降技术求解扩张次数为合数的二元扩域上椭圆曲线离散对数问题,将 ECDLP转化为超椭圆曲线离散对数问题,而求解高亏格的超椭圆曲线离散对数存在亚指数级 计算复杂度算法
-般曲线的离散对数问题,目前的求解方法都为指数级计算复杂度,未发现有效的亚指数级计 对于一 算复杂度的一般攻击方法;而对于某些特殊曲线的离散对数问题,存在多项式级计算复杂度或者亚指数 级计算复杂度算法
选择曲线时,应避免使用易受上述方法攻击的密码学意义上的弱椭圆曲线
A.4.2安全椭圆曲线满足的条件 A.4.2.1抗o攻击条件 A.Menezes、T.Okamoto,s.Vanstone,G,.Frey和H.Ruek的约化攻击将有限域F,上的椭圆曲线离 散对数问题约化为F,(B>)上的离散对数问题
这个攻击方法只有在且较小时是实用的大多数懒 圆曲线不符合这种情说
抗Mov攻击条件确保一条椭圆曲线不易受此约化方法攻击
多数r,上的 椭圆曲线确实满足抗MoV攻击条件
在验证抗MoV攻击条件之前,应选择一个Mo阔,它是使得求取F,和上的离散对数问题至少与 求取！P,上的悄圆曲线离散对数问题同样难的 一个正整数B
对于4>2"的标准,要求8>27
选择 26
信息安全技术SM2椭圆曲线公钥密码算法第1部分：总则GB/T32918.1-2016
1. SM2椭圆曲线公钥密码算法简介
SM2是一种基于椭圆曲线的公钥密码算法，由中国密码学专家设计。它使用的是一个特定的椭圆曲线参数集，称为SM2曲线。与RSA和DSA等传统的公钥算法相比，SM2具有更短的密钥长度、更高的安全性和更快的加解密速度。
2. GB/T32918.1-2016标准概述
GB/T32918.1-2016是我国颁布的《信息技术 安全技术SM2椭圆曲线公钥密码算法 第1部分：总则》标准，规定了SM2椭圆曲线公钥密码算法的基本概念、标准规范和术语定义。
该标准适用于在数字证书管理、电子认证、电子邮件安全等信息安全领域中应用SM2椭圆曲线公钥密码算法的相关工作。它主要包括以下内容：
- 标准名称和编号
- 标准化工作原则
- 术语和定义
- 符号和约定
- 标准结构
- 标准修订
3. SM2椭圆曲线公钥密码算法在GB/T32918.1-2016标准中的应用
作为我国信息安全技术的重要组成部分，SM2椭圆曲线公钥密码算法在GB/T32918.1-2016标准中得到了广泛应用。该标准对于SM2算法的定义和规范，使得其在数字证书管理、电子认证、电子邮件安全等方面得到了更加稳妥和有效的应用。
例如，在数字证书管理中，使用SM2算法可以有效地防止私钥被盗取或泄露，并确保数字证书的真实性和完整性。在电子认证中，使用SM2算法可以确保身份认证的准确性和安全性。在电子邮件安全中，使用SM2算法可以防止邮件被篡改、伪造或窃取。
4. 总结
GB/T32918.1-2016标准明确了SM2椭圆曲线公钥密码算法的基本概念和术语定义，并规范了其在数字证书管理、电子认证、电子邮件安全等领域中的应用。SM2算法以其高效、安全的特点，成为我国信息安全技术中重要的一部分。
