SM9中高次幂运算的快速实现方法.pdf
《SM9中高次幂运算的快速实现方法.pdf》由会员分享,可在线阅读,更多相关《SM9中高次幂运算的快速实现方法.pdf(8页珍藏版)》请在咨信网上搜索。
1、第 49卷 第 9期2023年 9月Computer Engineering 计算机工程SM9中高次幂运算的快速实现方法王江涛,樊荣,黄哲(中国船舶集团有限公司第七二二研究所,武汉 430205)摘要:国密 SM9算法是基于双线性对的标识密码算法,其运行过程需进行多次十二次扩域的高次幂运算,其计算性能对 SM9算法体制的应用至关重要。SM9签名运算中的高次幂可以预存点,在运算过程中通过查表减少运算时间。由于验签运算中高次幂的底数不确定,无法通过查表进行运算,因此分别使用 Comb固定基和 NAF算法在算法模型上降低高次幂中十二次扩域乘法运算量。为提高十二次扩域乘法的计算效率,根据 R-ate对
2、的特殊性质提出基于分圆子群的快速平方算法,降低扩域乘法所需的基域运算开销,并将其应用于高次幂的运算中。硬件架构创新性地采用基于自定义 RISC指令集的 ASIP微码控制方式实现,该架构的灵活性有利于在有限的硬件资源下实现复杂的 SM9算法逻辑,其中可修改的指令集可以更好地与底层硬件适配。在 Xilinx Artix-7系列的 FPGA 平台上的实验结果表明,在 167 MHz的时钟频率条件下,不增加额外的硬件资源开销,该方法完成一次 SM9签名的时间仅为 0.244 ms。关键词:SM9算法;高次幂;R-ate对;分圆子群;Comb固定基;NAF算法开放科学(资源服务)标志码(OSID):中文
3、引用格式:王江涛,樊荣,黄哲.SM9中高次幂运算的快速实现方法 J.计算机工程,2023,49(9):118-124,136.英文引用格式:WANG J T,FAN R,HUANG Z.Fast implementation of high power operation in SM9J.Computer Engineering,2023,49(9):118-124,136.Fast Implementation of High Power Operation in SM9WANG Jiangtao,FAN Rong,HUANG Zhe(No.722 Research Institute,Ch
4、ina State Shipbuilding Co.,Ltd.,Wuhan 430205,China)【Abstract】The SM9 algorithm is an identification cipher algorithm based on bilinear pairs.The operation process requires multiple higher power operations of twelve domain expansions,and its computing performance is crucial to the application of the
5、SM9 algorithm system.In SM9,the higher power of the signature operation can be stored in the point.The operation time is reduced by looking up the table in the operation process.The base number of the higher power in signature verification operation is uncertain and cannot be stored by looking up th
6、e table.The Comb fixed basis and NAF algorithm are used respectively to reduce the amount of multiplication of twelve times the higher power in the algorithm model.To further improve the calculation efficiency of the multiplication of the twelve degree extension field,this study proposes a fast squa
7、re algorithm based on cyclotomic subgroups according to the special properties of R-ate pairs,which reduces the overhead base field operation required by the extension field multiplication and is applied to the operation of higher powers.The hardware architecture innovatively adopts the ASIP microco
8、de control mode based on the customized RISC instruction set.The flexibility provided by the architecture is conducive to the implementation of the complex SM9 algorithm logic under limited hardware resources.The modifiable instruction set can also be adapted to the underlying hardware.The experimen
9、tal results on the FPGA platform of the Xilinx Artix-7 series show that under the condition of the 167 MHz clock frequency,without additional hardware resource overhead,the time to complete an SM9 signature is only 0.244 ms.【Key words】SM9 algorithm;higher power;R-ate pairing;cyclotomic subgroup;Comb
10、 fixed-base;NAF algorithmDOI:10.19678/j.issn.1000-3428.0065618基金项目:湖北省重点研发计划(2020BAB103)。作者简介:王江涛(1998),男,硕士研究生,主研方向为信息网络与安全;樊 荣,高级工程师,硕士;黄 哲,工程师、硕士。收稿日期:2022-08-29 修回日期:2022-11-10 Email:网络空间安全文章编号:1000-3428(2023)09-0118-07 文献标志码:A 中图分类号:TP309第 49卷 第 9期王江涛,樊荣,黄哲:SM9中高次幂运算的快速实现方法0概述 近年来,基于椭圆曲线上配对的密码体
11、制引起了人们的极大兴趣,由于双线性对独特的性质,可以构造许多其他加密算法无法完成的加密协议,因此出现了大量基于双线性对的研究成果,其中有许多新的的协议,包括一轮三方密钥交换1、基于身份的加密2、基于身份的签名3、短签名方案4等。我国国家密码管理局于 2016 年正式发布基配对的 SM9 标识密码算法5,于 2018 年被纳入国际标准,该算法以用户的身份信息作为公钥,简化了可信第三方认证中心(Certificate Authority,CA)的秘钥管理环节,从而解决了由高频认证引发的信息堵塞问题,非常适合海量用户之间的安全通信,在云计算、物联网等海量用户的新兴领域中6,SM9 密码算法具有明显的
12、优势。基于配对的密码协议只有在高安全级别上以高效 计 算 双 线 性 配 对 的 情 况 下 才 能 实 现。得 益 于MILLER 等7提出的在椭圆曲线上以除子的标量乘来计算有理函数的迭代算法,实现以线性复杂度的开销去计算双线性对,并用于计算 weil对(对称双线性对)的目的。文献 8 给出计算更简便的 Tate 对(非对称双线性对)。文献 9-11 在 Tate对的基础上通过构造特殊结构的双线性 Eta 对、Ate 对和 Atei对来优化双线性对的计算量。文献 12 定义了 R-ate对,通过两个特定线性对的比值,减少 Miller算法中的循环次数。文献 13-15 优化了 BN 曲线上
13、R-ate对的计算,主要针对其中的 Miller 循环和最终幂运算,对 Miller循环中的同构映射进行分析,将循环中的点加,倍点和线性函数的运算从十二次扩域降低为二次扩域.文献 16-17 将最终幂运算进行幂次分解,用基域的组合多项式来表示运算困难的大幂次项,并利用有限域和扩域上 Frobenius 映射进行加速,文献 18 使用 Comb 固定基19对 SM9 中签名部分的高次幂进行优化。密 码 算 法 的 底 层 运 算 有 大 量 大 数 计 算,文献20提出蒙哥马利算法,将大数的模乘改为3个大数乘法,这也使得对称加密的底层运算可以实现,文 献21针 对 R-ate 对 提 出 混 合
14、 模 乘(Hybrid Modular Multiplication,HMM),其核心思想是将基域的数表示为特征数的多项式形式,引入了多项式情况下的蒙哥马利算法,将对于大数的模乘转化到特征数上的模乘,但由于 SM9 中特征数的权重比文献中使用的权重大,所以使用该算法并不合适作为SM9的底层运算。文献 22 提出基于字的蒙哥马利乘(MWR2MM),将乘数均转化为短整数乘法,更有利于硬件实现。文献 23 提出迭代字蒙哥马利乘(IDDMM),将模也转化为短整数,在基于 MWR2MM基础上增加了基础乘法的位宽。文献 24 提出基于蒙哥马利的求逆运算,使蒙哥马利域的大数在求逆后,不用再进行两次转入域操作
15、。本文利用十二次扩域的分圆子群的性质,使用快速平方算法,该算法相较于传统平方算法需要的基域乘法数量降低了 1/2。该平方算法应用在 SM9的高次幂运算上,包括 R-ate 最终幂和签名算法中,最终幂中的高次幂采用反复平方-乘法算法和 NAF算法,签名算法中高次幂采用 Comb固定基算法。底层的大数模乘采用文献 20 中的蒙哥马利运算,相较于 IDDMM,更有利于本文架构实现,硬件使用Xilinx Artix-7 系列的 XC7A50T,架构选用基于专用指 令 集 处 理 器(Application Specific Instru-ction Set Processor,ASIP)的微码编程,在
16、控制硬件资源开销的同时降低时钟周期,从而提高性能。1基础算法 1.1BN曲线上的 R-ate对文献 25 提出一种在素域Fp上构造配对友好的常曲线的方式,BN 曲线定义了椭圆曲线26-28方程(Fq):y2=x3+b,对应嵌入度k为 12,素域的特征p、群的阶r、Frobenius迹tr由参数t定义为式(1)所示:p(t)=36t4+36t3+24t2+6t+1r(t)=36t4+36t3+18t2+6t+1tr(t)=6t2+1(1)其中:t Z是一个任意的整数,使得p及r均为素数。SM9 使用了定义在 BN 曲线上的 R-ate 对,双线性对中定义了 3个阶为N的循环群,分别是加群G1、G
17、2和乘群GT,G1的生成原是P1,G2的生成原是P2,G1表 示(Fp)r Ker(p-1),G2表 示(Fp)r Ker()p-p,(Fq)r为椭圆曲线上的r扭转点,核Ker(p-p)为P|p()P-pP=O,O定义为椭圆曲线中的无穷远点,在群G1、G2、GT中存在映射G2G1 GT满足双线性、可计算性和非退化性,对应映射关系如式(2)所示:e(QP)(f6t+2Q()P l6t+2Qp()Q()P )l6t+2Q+p()Q -2p()Q()Pp12-1 r(2)其 中:Q G2P G1;frQ为 Miller 函 数;p表 示Frobenius 映射p(xy)=(xpyp);lRQ(P)为
18、椭圆曲线上过RQ的直线方程在P点处的值。R-ate双线性对的计算可由算法 1实现。算法 1 BN曲线上的 R-ate对输入 P G1,Q G2,s=6t+2输出 e(Q,P)1.分解s为s=i=0L-1si2i()NAF,R Q,f 1。2.对于i从L-1降到 0,执行:1)计算f=f2 lR,R(P),R=2R;2)若si=1,则计算f=f lR,Q(P),R=R+Q;1192023年 9月 15日Computer Engineering 计算机工程3)若si=-1,则计算f=f lR,-Q(P),R=R-Q。3.计算Q1=p(Q),Q2=p2(Q)。4.计算f=f lR,Q1(P),R=R
19、+Q1。5.计算f=f lR,-Q2(P)。6.计算f=f()p12-1 t。7.输出f。算法 1 中的计算可以分解为图 1 中基域的加减乘和求逆运算,其中较为复杂的运算为第 2步 Miller循环和第 6 步的最终幂运算,最终可以转化为基域的加减乘和求逆运算。1.2NAF算法采用 NAF 算法对标量k进行编码,是指将使用1,0 表示二进制序列k=(sm-1,si,s1s0)bin,其中si01,变换为用 1、0 和1 表示的形式。即标量k的 NAF 编码为k=(km,ki,k1k0)NAF,其中ki-101,且首位km 0,具体表示如式(3)所示:k=i=0m-1ki2i(3)标量k的 NA
20、F编码算法描述如算法 2所示。算法 2 标量k的 NAF编码算法输入 长度为m bit的标量k输出 k=(km,ki,k1,k0)NAF1.m=0。2.对于k 0,重复执行:1)若 k为奇数,则执行km=2-(k mod 4);2)若 k为偶数,则执行km=0;3)k=k-km,m=m+1;4)k=k/2。3.返回(km,ki,k1,k0)NAF。令lNAF()k表示标量k采用 NAF 编码方法的编码长 度,则 有2m3 lNAF()k 2m+13,下 面 给 出 实 用 的NAF编码性质:1)长度最多比二进制形式编码的长度多 1;2)非零元素平均个数为m 3;3)非零元素-1,1不会相邻。在
21、反复平方-乘法运算中,可以使用性质 2)减少乘法数量。1.3Comb固定基SM9 签名运算中高次幂可以预存点,通过查找表运算高次幂gr,将幂指数通过基于 Comb固定基的方式进行查表计算。指数r可以表示成式(4)中两种形式,其中Ri=j=031Rij 2jRij01。r=i=0255ri 2i=i=07Ri 232iri01Ri0232-1(4)当指数运算时,所有Ri位置相同的比特可以同时处理,将需要预先存储的元素表示为gi=07mi 232i,其中m按位展开为m7m6m5m4m3m2m1m00255,所以共需要预存 256 个十二次扩域元素,算法实现先按照图 2对r进行比特重组,将以Ri表示
22、变为以ai表示,再使用算法 3进行计算。算法 3 基于 Comb基的高次幂运算输入 预计算表gi=07mi 232*i,g,重组后r输出 w=gr1.w=1;2.对于i从 31到 0重复执行:1)w=w2;2)在查找表中找到m=ai的预存值q;3)w=w q。3.返回w。使用 Comb算法优化前,如果预存每个比特位上的平方值,也需要预存 256个十二次扩域元素,运算开销为 128 次GT域上的乘法。优化后,在使用相同存储开销的情况下,运算开销减少为GT域上 31次乘法运算和 31次平方运算。1.4SM9签名算法密钥生成中心(Key Generate Center,KGC)产生随机数ks1N-1
23、,计算G2元素Ppub-s=ksP2并作为签名主公钥,计算G1元素dSA=t2P1作为签名密钥,t2通过哈希计算用户标识ID得到。令待签名的信息为 M,KGC 生成(Ppub-sdSA)密钥对,签名后得到数字签名为(hs),签名流程为:1)计算GT中的元素g=e(P1,Ppub-s);图 2幂指数r的比特重组Fig.2Bit recombination of power exponent r图 1R-ate算法的实现Fig.1Implementation of R-ate algorithm120第 49卷 第 9期王江涛,樊荣,黄哲:SM9中高次幂运算的快速实现方法2)产生随机数r 1N-1
24、;3)计算群GT中的元素w=gr;4)计算整数h=H2(M|wN);5)计算整数l=(r-h)mod N;6)计算群G1中的元素S=ldsA;7)消息的签名值为(hS)。在签名算法中,当 KGC 下发了Ppub-s后,由于P1也是固定变量,因此签名中g可以提前预计算并存储起来,不用每次签名都要重新计算,所以签名的效率往往是验签效率的数倍。2基于分圆子群的快速平方算法 2.1扩域平方算法SM9 中选取的是式(5)的 1-2-4-12 塔式扩张29,对应的不可约多项式分别为x2-(=-2),x2-u(u=-2),x3-v(v=-2),其计算式如下:Fp2=Fpu u2-=-2Fp4=Fp2v v2
25、-=uFp12=Fp4w w3-v v2=(5)在扩域Fq4中将a表示为a1+a0v,其中a1、a0均表示二次扩域元素。使用算法 4 计算 4 次扩域元素的平方,相较于直接用 Karatsuba 算法计算,平方算法需要将基域的乘法从 9次降低为 6次。算法 4 Fp2=Fpu u2-上的平方运算输入 A=a1v+a0(a1,a0 Fp2)输出 A2=A1v+A2(A1,A2 Fp)1.c0=a1 a02.c1=(a0+a1u)(a0+a1)3.c2=(1+u)c04.返回A1=2 c0,A0=c1-c2在扩域Fq12中表示为a+bw+cw2,其中a、b、c为扩域Fq4元素,应用塔式扩张的乘法运
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- SM9 中高 运算 快速 实现 方法
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。