1、密码学报ISSN 2095-7025 CN 10-1195/TNJournal of Cryptologic Research,2023,10(4):720736密码学报编辑部版权所有.E-mail:http:/Tel/Fax:+86-10-82789618基于 SIMD 指令集的 SM2 数字签名算法快速实现*韦 薇,罗 敏,白 野,彭 聪,何德彪武汉大学 国家网络安全学院 空天信息安全与可信计算教育部重点实验室,武汉 430072通信作者:罗敏,E-mail:摘要:SM2 数字签名算法是国家密码管理局发布的首个数字签名标准,已广泛应用于网上银行、电子政务等领域.本文提出一种基于高级矢量扩展
2、指令集(advanced vector extension 512,AVX512)的 SM2数字签名算法实现方案,有效提升了 SM2 数字签名算法的性能.结合单指令多数据集(single instructionmultiple data,SIMD)运算特性,设计了一种新的冗余基数表示形式与数据排列方式,利用 3 比特冗余空间减少进位传播的次数,构建高效的并行素域运算模块.进而提出一种可变基点标量乘法的并行优化算法,在算法分支加入虚拟操作,按需存储点加与倍点的计算结果,结合底层数据表示形式消除 8 路分支的差异性.利用 AVX512 指令与分步点加方法加速固定基点标量乘法.签名与验签算法的性能比
3、最新的 SIMD实现分别提升了 196%和 69%.关键词:SM2 数字签名算法;SIMD 指令集;AVX512;软件优化中图分类号:TP309.7文献标识码:ADOI:10.13868/ki.jcr.000622中文引用格式:韦薇,罗敏,白野,彭聪,何德彪.基于 SIMD 指令集的 SM2 数字签名算法快速实现J.密码学报,2023,10(4):720736.DOI:10.13868/ki.jcr.000622英文引用格式:WEI W,LUO M,BAI Y,PENG C,HE D B.Fast implementation of SM2 digital signa-ture algorit
4、hm using SIMD instructionsJ.Journal of Cryptologic Research,2023,10(4):720736.DOI:10.13868/ki.jcr.000622Fast Implementation of SM2 Digital Signature Algorithm UsingSIMD InstructionsWEI Wei,LUO Min,BAI Ye,PENG Cong,HE De-BiaoKey Laboratory of Aerospace Information Security and Trusted Computing,Minis
5、try of Education,School ofCyber Science and Engineering,Wuhan University,Wuhan 430072,ChinaCorresponding author:LUO Min,E-mail:Abstract:SM2 digital signature algorithm was published by the State Cryptography Administrationof China.It has been widely used in online banking,e-governance,and other fiel
6、ds.This paperproposes an implementation of SM2 digital signature algorithm based on advanced vector extension512(AVX512).Firstly,combining the characteristics of single instruction multiple data(SIMD),areduced-radix representation and data arrangement are designed,so that the 3-bit redundant space*基
7、金项目:山东省重点研发计划(2020CXGC010115);国家自然科学基金(62172307,62202339,U21A20466)Foundation:Major Scientific and Technological Innovation Project of Shandong Province(2020CXGC010115);Na-tional Natural Science Foundation of China(62172307,62202339,U21A20466)收稿日期:2022-07-05定稿日期:2022-09-30韦薇 等:基于 SIMD 指令集的 SM2 数字签名算
8、法快速实现721can be used to reduce the number of carry propagation.Based on this,an efficient parallel prime fieldarithmetic algorithm is constructed.Then,a parallel optimization algorithm for variable base pointscalar multiplication is proposed.Some dummy operations are added to the branches of the algo
9、rithmand the computation results of point addition and point double on demand are stored to eliminate thedifference of the 8-way instances.Furthermore,a fixed-base scalar multiplication is accelerated usingAVX512 instructions and a stepwise point addition.Experiments show that the proposed scheme ca
10、neffectively improve the performance of SM2 digital signature algorithm.The performance of signaturegeneration and verification is ahead 196%and 69%of the latest SIMD implementation.Key words:SM2 digital signature algorithm;SIMD instructions;AVX512;software optimization1引言数字签名是保障网络安全的重要机制之一,其通过特定的规则
11、和参数生成,允许数据的接收者确认数据的来源和完整性.SM2 椭圆曲线公钥密码算法由国家密码管理局于 2010 年首次公开发布,并于 2016年列为中国国家密码标准(标准号:GB/T32918-2016)1,2018 年正式成为 ISO/IEC 国际标准.算法由数字签名算法、密钥交换协议、公钥加密算法三部分组成.SM2 数字签名算法与传统的数字签名算法(RSA、ELGamal 等)相比,具有密钥空间小、签名速度快等优势,已在电子政务、网上银行、物联网等领域2广泛应用,提高了数据传输的安全性与可靠性.基于 SM2 数字签名的批量验签方案3与其衍生的功能型签名方案(如适配器签名4、环签名5)相继提出
12、,签名算法应用进一步推广到区块链、云计算等领域.用户数量与业务量的增加对 SM2 数字签名算法的性能提出了新的挑战,高性能实现成为密码工程的一个重要研究方向.单指令多数据集(single instruction multiple data,SIMD)是一种采用单个控制器来控制多个处理器,同时对一组数据向量中的每一个元素分别执行相同的操作从而实现空间并行的技术.相比传统的 x64指令集,在数据密集运算的场景下,SIMD 指令集的处理速度具有显著优势.以 Intel 处理器为代表,该处理器的 SIMD 指令集包括 SSE、AVX、AVX2 和 AVX512,不同版本的指令集寄存器长度与个数不同.研
13、究人员发现 SIMD 指令集可用于密码算法的高速实现.自 1996 年 Intel 推出 SIMD 指令集后,许多学者使用该指令集优化了多个对称密码算法,SM4 算法6、ZUC 算法7的并行实现方案相继提出.基于椭圆曲线的公钥密码算法的关键步骤为大整数运算与椭圆曲线运算.Bos 等人8利用 AVX2 指令集实现了 2 路低延迟蒙哥马利模乘算法,模幂的性能相比 OpenSSL 提高了 1.5 倍.Buhrow 等人9基于 AVX512 指令集,提出了 8 路与 16 路并行模乘算法,显著提升了蒙哥马利模乘的吞吐量.Hisil 等人10基于蒙哥马利阶梯算法(Montgomery ladder)11
14、,设计了适用于 Montgomery 形式椭圆曲线的 4 路 Montgomery ladder 矢量化算法,并利用 AVX2 指令集和 AVX512 指令集实现矢量算法.Nath 等人12在此基础上提出了可变基点和固定基点标量乘法的优化算法,减少了点运算中的乘法个数,并使用汇编语言和 AVX2 指令集实现了 Curve25519 和 Curve448 曲线上的 4 路 Montgomery ladder 矢量化算法,进一步缩短了 Montgomery ladder 算法的运行时间.Faz-Hernndez 等人13使用 AVX2 指令集对 Curve25519 曲线上的算术运算和点运算进行优
15、化.Cheng 等人14基于 AVX2 指令集进一步提高了 Curve25519 曲线上标量乘法的吞吐量.Huang 等人15将其推广到 SM2 椭圆曲线,基于 AVX2 指令集实现了 2 路并行大整数运算与标量乘法算法,降低了 SM2 上恒定时间标量乘法的时延.Gueron 等人16针对 NIST 中的 P-256 曲线在 x86_64 平台下实现了一个高度优化的密码库,使用SIMD 指令集优化固定基点标量乘法计算流程,且可以直接扩展到 OpenSSL 中.Bernstein 等人17针对Ed25519 曲线提出了加速固定基点标量乘法的技术,提高了 EdDSA 方案的运行速度.Faz-Her
16、nndez 等人18结合 SIMD 指令集设计了 Ed25519 曲线的预计算表,进一步优化了固定基点标量乘法性能.目前国内商用密码算法的 SIMD 优化实现主要围绕对称密码算法展开,针对 SM2 数字签名算法的快速实现研究较少.本文充分利用 SIMD 的并行计算特性,设计了更加匹配的并行策略与数据排列方式、减少了高延迟指令的使用,改进了素数域上的算术运算与点运算,实现了基于 AVX512 指令集的 SM2 数字签名算法,提高了该算法的性能.本文的主要贡献如下:722Journal of Cryptologic Research 密码学报 Vol.10,No.4,Aug.2023(1)设计了基
17、于 AVX512 指令集的 8 路素域运算模块.使用 AVX512 指令集实现模加、减、乘、逆,针对特定基数表示下的 SM2 模数设计了并行模约减算法,利用 3 比特冗余空间减少进位传播次数,采用加法链加速模逆运算,提升了素域算术运算性能.(2)提出了一种标量乘法并行优化方法.对原始 Montgomery ladder 算法进行改进,实现恒定时间点向量集交换函数,将算法迭代次数设置为固定值,保证了 8 路并行分支的一致性,同时利用AVX512 指令集与分步点加方法加速固定基点标量乘法,有效衔接底层 8 路并行算术运算.(3)设计并实现了高性能 SM2 数字签名方案.在 Intel 平台上的性能
18、测试结果表明:相比最新的AVX2 实现,本方案签名与验签的性能分别提升了 196%和 69%.本文结构如下:第2节介绍 SM2 数字签名算法、Montgomery ladder 算法与 AVX512 指令集;第3节介绍本文提出的 SM2 数字签名算法的并行优化方案,分析算法的理论复杂度与安全性;第4节评估算法性能;第5节总结全文.2预备知识2.1SM2 标准推荐椭圆曲线参数及定义SM2 椭圆曲线定义在素数域 Fp或二元扩域 F2n上,在仿射坐标系下由 Weierstrass 方程式 E:y2=x3+ax+b 确定,其中 a 与 b 满足 4a3+27b2=0,p 为大于 3 的素数,在标准中推
19、荐 p=2256 2224 296+264 119,其形式为伪梅森素数,可以利用伪梅森素数相关性质加速模约减运算20.在雅可比射影坐标下,椭圆曲线上一点(X:Y:Z),Z=0,对应的仿射坐标点为(x,y),满足 x=X/Z2,y=Y/Z3,该坐标系下的曲线方程如式(1)所示:E:Y2=X3+aXZ4+bZ6mod p.(1)椭圆曲线上同一点多次相加为多倍点运算,也称标量乘法,令 k 为正整数,P 是椭圆曲线上的点,标量乘法 kP 如式(2)所示:kP=P+P+P|zk个.(2)2.2SM2 数字签名算法SM2 数字签名算法21包括密钥生成算法、签名生成算法与签名验证算法.首先,系统根据密钥生成
20、算法生成私钥 dA和公钥 PA;然后,签名者使用私钥 dA运行签名生成算法生成消息 M 的签名对(r,s),并发送给验证者;最后,验证者收到签名对(r,s)后,使用签名者的公钥 PA运行签名验证算法验证签名是否通过.SM2 数字签名算法规定使用的杂凑算法 H256为 SM3 密码杂凑算法,G 为 SM2 椭圆曲线的基点,n 为基点 G 的阶,具体计算过程如下:密钥生成算法:输入安全参数,输出私钥 dA 1,n 2 和公钥 PA=dAG.签名生成算法:(1)计算消息 M 的杂凑值 e=H256(M);(2)生成随机数 k 1,n 1;(3)计算 kG=(x1,y1),r=(e+x1)mod n,
21、若 r=0 或 r+k=n 则返回(2);(4)计算 s=(1+dA)1(k r dA)mod n,若 s=0 则返回(2);(5)输出消息 M 对应的签名对(r,s).签名验证算法:(1)验证 r 1,n 1,s 1,n 1 是否成立,若不成立,验签失败;(2)计算收到消息 M的杂凑值 e=H256(M);韦薇 等:基于 SIMD 指令集的 SM2 数字签名算法快速实现723(3)计算 t=(r+s)mod n,若 t=0,验签失败;(4)计算(x1,y1)=sG+tPA,R=(e+x1)mod n,验证 R=r是否成立,若成立则验签通过,否则验签失败.2.3Montgomery ladde
22、r 算法算法1为椭圆曲线群上的 Montgomery ladder 算法22,每轮迭代过程保证 R0 R1始终为 P.在第 i 轮迭代结束后,有 R0=(k)iP,R1=(k)i+1P,(k)i=k/2i,当算法执行到第 8 步,返回值R0=(k)0P=kP.计算过程中 R0首先被初始化为 P,当 ki=0,计算 R0=2R0,当 ki=1,计算R0=R0+R1=2R0+P,即与经典的二进制标量乘法算法相似,但该算法同时更新 R1.由于两个不同分支下都计算一次倍点与点加,每个分支具有相同的计算流程,可以防御简单功率分析攻击.算法 1 Montgomery ladder 算法Input:P E(
23、Fp),k=(kn1,kn2,k0)2 N with kn1=1Output:Q=kP1(R0,R1)(P,2P);2for i n 2 down to 0 do3if ki=0 then4(R0,R1)(2R0,R0+R1);5else6(R0,R1)(R0+R1,2R1);7end8return R0.2.4SIMD 指令集技术概述在标量乘法软件优化实现方面,SIMD 技术的并行计算特性一直是研究的热点.一个具有 SIMD 指令集的处理器上包含一组特殊的向量寄存器和相关指令集,能并行计算向量寄存器中的数据.采用了 SIMD技术的指令集有 Intel 处理器中的 SSE、AVX2 等.AVX
24、2 指令集23中向量寄存器的长度为 256 bit,分为两个 128 bit 通道,分别是高通道和低通道,AVX2 及早期指令集不同通道不能互取数据.AVX512 指令集实现了跨通道数据互取,效率更高.2.4.1并行方式SIMD 指令的并行方式有三种:细粒度并行、粗粒度并行与混合并行.形式化表示为(ij)路 SIMD并行方式,即一组指令同时完成 i 个实例的计算,每个实例位于向量寄存器中的 j 个通道.以 256 bit 长度寄存器为例,细粒度并行方式如图1(a)所示,将一组运算数据放入向量寄存器并行处理,用于加速单个实例计算.粗粒度并行是将多组运算数据放入一组向量寄存器,实现多组消息的并行处
25、理,如图1(b)所示,通常用于加速多个实例计算.混合方式如图1(c)所示,为前两种方式的结合体.由于细粒度并行策略与混合并行策略涉及同一寄存器通道之间的数据移动,会带来很高的时延,因此本文基于 AVX512 指令集,采用(8 1)路粗粒度并行策略加速大整数运算和 SM2 数字签名算法(简称 8 路).图 1 SIMD 指令集并行策略Figure 1 Parallel strategies of SIMD Instruction Set724Journal of Cryptologic Research 密码学报 Vol.10,No.4,Aug.20232.4.2AVX512 指令集高级矢量扩展
26、指令集(advanced vector extension 512,AVX512)是 Intel 于 2013 年发布的一套扩展指令集,与前几代指令集相比,寄存器宽度和可用寄存器数量都增加了一倍,寄存器的长度达到 512 bit,可将 8 个 64 bit 整数或 16 个 32 bit 整数打包到寄存器中.AVX512 指令集主要分为以下几类:算术指令.加减指令(VPADDQ,VPSUBQ)可以同时进行 8 组 64 bit 整数的加减运算;乘法指令(VPMULUDQ)能够同时计算 8 组 32 bit 整数的乘积,并将 8 组 64 bit 乘积结果存储在 512bit 寄存器中,其中加减
27、指令均无法处理进位和借位.逻辑指令.逐比特与指令(VPANDD)对两个 512 bit 寄存器内容进行逐比特与运算;左移指令(VPSLLQ/VPSLLVQ)和右移指令(VPSRLQ/VPSRLVQ)能够对寄存器中元素逐比特移位.VPSLLQ 和 VPSRLQ 对 AVX512 寄存器中数据移动相同位数,VPSLLVQ 和 VPSRLVQ 对每个通道中的数据设置不同的移位量,为操作向量寄存器增加了灵活性.联合指令.VPBLENDMQ 指令在掩码作用下选择两个不同寄存器中的字来填充目标寄存器.置换指令.AVX512 的置换指令(VPERMQ)根据控制变量,以 64 bit 为单位置换一个寄存器中的
28、数据.AVX512 指令集中各个指令的时延和吞吐量信息参考相关说明文献 24,其中置换指令的时延是 3 个时钟周期,并且无法在流水线中执行,在方案实现过程中应尽量避免使用以降低性能损失.在 Intel 平台上,可以通过多种方式使用 AVX512 指令集,如汇编语言、C+类、编译器内联函数(Intrisincs)和自动矢量化等,本文以内联函数方式使用 AVX512 与 AVX2 指令集.方案中并行运算用到的主要 AVX512 指令见表1.表 1 实现素域运算的相关 AVX512 指令集Table 1AVX512 instructions used for implementation of pr
29、ime-field arithmetic指令助记符内联函数功能描述VADD_mm512_add_epi64()8 通道 64 bit 数据加VSUB_mm512_sub_epi64()8 通道 64 bit 数据减VMUL_mm512_mul_epu32()8 通道 32 bit 数据乘VSHL_mm512_slli_epi64()8 通道 64 bit 数据统一左移VSHR_mm512_srli_epi64()8 通道 64 bit 数据统一右移VAND_mm512_and_si512()512 bit 数据逻辑与VXOR_mm512_xor_si512()512 bit 数据逻辑异或3SM
30、2 并行优化实现3.1数据映射方式3.1.1数据的表示方式令 p 为素域的特征,m 是 p 的比特长度,w 是处理器的字长,对于素域 Fp中的任意一个元素 a,有两种表示方法.第一种是全基数表示法,此方法将 a 用一系列数字 A(w)=as1,as2,a0 表示,其中 s=m/w,满足 a=s1i=0ai2iw.这种表示方法紧凑,常用在多精度库中,但在模加减的计算过程中存在即时进位的缺点,导致数据运算过程出现依赖关系,限制了并行计算.第二种为冗余基数表示法,此方法将 a 用一系列数字 A(w)=as1,as2,a0 表示,其中 0 w w,s=m/w,满足a=s1i=0ai2iw.这种表示方法
31、允许每个数字在达到寄存器最大容量 w 之前增大几倍,由加法产生的进位可以保留在同一寄存器中,可以延迟进位的传播,在寄存器溢出之前执行多次加法,为素域运算的并行带来可行性.韦薇 等:基于 SIMD 指令集的 SM2 数字签名算法快速实现725本方案使用冗余基数表示法来表示素域大整数,w的选择是素域运算性能的关键:较小的 w会产生较大的分支数量,较大的 w会限制运算的并行性.考虑到 SM2 模数 p 的形式,AVX512 指令集不支持进位传播的性质,以及乘法器的最大输入字长为 32 bit 的限制,本方案最终设置 w为 29,冗余空间为 3bit.例如一个长度为 256 bit 的数 a 包含 2
32、56/29=9 个分支.3.1.2素域元素到 AVX512 寄存器的映射AVX512 指令集的并行计算单元为向量寄存器.在使用 AVX512 指令实现大整数运算之前,需要将素域元素映射到 512 bit 长的寄存器中.具体映射方式为:以 29 bit 为单位,将 8 个素域元素同一位置分支打包为一组存入 AVX512 寄存器,采用 8 路并行方式进行运算.向量集的结构如式(3)所示,素域中 8个独立的元素 A,B,C,D,E,F,G,H 依次放入 AVX512 寄存器,每个素域元素包含 9 个分支,共需 9 个AVX512 寄存器,一次向量运算等价于 8 个相互独立的单路大整数运算.将 8 个
33、元素整体看作一个向量集M,Mi表示 8 个整数的第 i 个分支,根据这种映射方式设计 8 路并行素域运算.M=M0 a0,b0,c0,d0,e0,f0,g0,h0M1 a1,b1,c1,d1,e1,f1,g1,h1M2 a2,b2,c2,d2,e2,f2,g2,h2M3 a3,b3,c3,d3,e3,f3,g3,h3M4 a4,b4,c4,d4,e4,f4,g4,h4M5 a5,b5,c5,d5,e5,f5,g5,h5M6 a6,b6,c6,d6,e6,f6,g6,h6M7 a7,b7,c7,d7,e7,f7,g7,h7M8 a8,b8,c8,d8,e8,f8,g8,h8.(3)向量集 A,B
34、,C,D,E,F,G,H 的结构如图2所示,其中 A,B,C,D,E,F,G,H 是不同的素域元素且互相之间没有依赖关系,这 8 个素域元素的第 i 个分支分别为位于第 i 个 AVX512 寄存器的 8 个分段,每个分段长度为 64 bit.AVX512 中的乘法指令 VMUL 仅将输入操作数的每 64 bit 分段中的低 32 bit相乘,将分支 i 存储在 64i 到 64i+29 位置上,可以同时对 8 组大整数进行算术运算.在整个计算过程中,元素的实际分支长度可以大于 29 bit,最后乘法约减的结果保持在 29 bit 内,确保在运算过程中不会产生溢出:9 (229 1)2 264
35、.图 2 向量集 A,B,C,D,E,F,G,H 结构Figure 2 Structure of vector set A,B,C,D,E,F,G,H726Journal of Cryptologic Research 密码学报 Vol.10,No.4,Aug.20233.1.3椭圆曲线点到向量寄存器的映射椭圆曲线上点的坐标一般使用结构体来存储,结构体中每个数据为一个坐标分量,长度为 256 bit,在并行算法的基础上,本文使用冗余基数来表示坐标,并映射到 AVX512 寄存器,一次运算可以同时处理 8个点.用(xi,yi)表示基数为 29 的仿射坐标点,P=(xp,yp)表示仿射坐标点向量集
36、,包含 8 个仿射点(xi,yi)的全部坐标.在雅可比射影坐标形式下,点向量集 P 的形式为 P=(XP,YP,ZP).以仿射坐标为例,8 个仿射点 A=(xA,yA),B=(xB,yB),C=(xC,yC),D=(xD,yD),E=(xE,yE),F=(xF,yF),G=(xG,yG),H=(xH,yH)映射到一组仿射坐标点向量集 P,映射过程如式(4)所示.P=A,B,C,D,E,F,G,H=(xA,yA),(xB,yB),(xC,yC),(xD,yD),(xE,yE),(xF,yF),(xG,yG),(xH,yH)=(xA,xB,xC,xD,xE,xF,xG,xH,yA,yB,yC,yD
37、,yE,yF,yG,yH)=(xp,yp)(4)3.28 路大整数并行运算素域大整数运算是椭圆曲线算法的关键性能模块,为了提高运算的性能,本文在计算过程中应用SIMD 技术,以 8 路并行方式完成素域运算.在计算前,将操作数从基为 64 的全基数表示转换为基为29 的冗余基数表示,上层协议计算完成后,将结果转换为全基数表示.3.2.1加减对于给定的两组向量集A(0),B(0),C(0),D(0),E(0),F(0),G(0),H(0)和A(1),B(1),C(1),D(1),E(1),F(1),G(1),H(1),8 路素域并行加法 A(2),B(2),C(2),D(2),E(2),F(2),
38、G(2),H(2)=A(0),B(0),C(0),D(0),E(0),F(0),G(0),H(0)+A(1),B(1),C(1),D(1),E(1),F(1),G(1),H(1)的计算过程为 a(2)i=a(0)i+a(1)i,i 0,9),由于加法的输入长度小于 63 bit,不会产生溢出.减法和加法过程相似,不同之处在于负数的处理,为了避免中间结果出现负数的情况,将 SM2 模数的倍数与中间变量相加,以保证结果恒正.8 个素域元素的并行加法共需 9 个 VADD 指令,减法为了保证结果恒正,代价相比加法较大.3.2.2模乘模乘是素域运算中最关键的步骤,其使用频率高、计算复杂,因此应更加注意
39、并行算法的设计.素域乘法计算通常分为两部分:整数乘法和模约减,对于伪梅森素数,这两个步骤可以同时进行20.SM2 中的模数为广义梅森素数,本方案采用乘法约减交叉进行的策略,需要使用额外寄存器来保存未约减的中间结果.AVX512 下的 8 路并行模乘算法如算法2所示.算法 26 步使用乘积扫描策略计算部分乘积结果,将其存储于局部寄存器变量 T.算法 914 步为第二个循环,使用乘法和进位传播交叉策略,在计算部分乘积 TR 的同时,将所得乘积结果每个分支高 29bit 的内容与下一分支(权重更高)数据相加,减少了乘积结果的长度,避免在快速约减过程中产生溢出.最后调用快速约减算法将乘积结果分支数减少
40、为 9 个,并且每个分支长度约减到 29 bit 内.可以发现,当所有分支长度为 29 bit 时,部分乘积结果分支长度为 58 bit,对应权重相加的分支最多为 62 bit,如最大分支 t8在寄存器中一个分段的内容如式(5)所示.t8=a0b8+a1b7+a2b6+a3b5+a4b4+a5b3+a6b2+a7b1+a8b0.(5)到 17 步前,中间结果存储在寄存器 T、TR 和 ACCU 中,其中 T 存储低 256 bit 数据,TR 存储高256 bit 数据,之后约减中间变量 TR.目前主流的约减算法有 Barrett 和 Montgomery 约减算法25,两者适用的模数为任意素
41、数,针对 SM2 椭圆曲线的模数,本文实现了线性复杂度的快速约减算法.在基数为 29 的冗余表示法下,我们设计了适用于 SM2 模数 p 的快速约减算法.为了将中间结果的18 个分支约减到 9 个分支,根据 SM2 模数推导出同余式:2256 2224+296 264+1 mod p,依次将乘积的 9 个高权重分支的系数表示为同余式(6),公式左侧权重大于等于 2261的分支系数可以约减到权重小韦薇 等:基于 SIMD 指令集的 SM2 数字签名算法快速实现727于 2232的分支系数.算法 2 8 路并行模乘算法Input:M=A(0),B(0),G(0),H(0),N=A(1),B(1),
42、G(1),H(1)Output:R=A(2),B(2),G(2),H(2)=A(0)A(1)mod p,H(0)H(1)mod p1M29 0 x1FFFFFFF;2for i 0 to 8 do3Ti 0,0,0,0,0,0,0,0;4for k i down to 0 do5Ti VADD(Ti,VMUL(Mik,Nk);6end7end8ACCU VSHR(T8,29);9T8 VAND(T8,M29,M29,M29,M29,M29,M29,M29,M29);10for i 9 to 16 do11for j i 8 down to 9 do12ACCU VADD(ACCU,MUL(Mj
43、,Nij);13end14TRi9 VAND(ACCU,M29,M29,M29,M29,M29,M29,M29,M29);15ACCU VSHR(ACCU,29);16end17TR8 ACCU;18R FastRed(T,TR);19return R.t92261 t9(2229+2101 269+25)mod pt102290 t10(2258+2130 298+234)mod pt112319 t11(2255+2159 295+263+231)mod pt122348 t12(2252+2188+260+228)mod pt132377 t13(2249+2217+2121+257+2
44、25)mod pt142406 t14(2247+2150+2118+254+222)mod pt152435 t15(2244+2179+2147+2116 283+251+220)mod pt162464 t16(2241+2208+2176+2145+2112 280+249+217)mod pt172493 t17(3 2237+2205+2174+2141+2109+246+214)mod p(6)算法3为并行模乘算法第 16 步调用的 FastRed 算法,在约减算法中使用同余式约减和进位传播交叉策略.通过定义 19 个寄存器变量并进行加减操作,将分支数目由 18 减为 9,由于同
45、余式约减过程中,加到t0 t8的分支长度不超过 62 bit,约减后每个分支长度不超过 63 bit:2 (262 1)263,符合 AVX512寄存器 64 位分段长度,没有产生溢出.经过同余式约减,每个分支长度最大为 63 bit,若直接将其输出作为下一次模乘的输入操作数,则会产生溢出.为了保证模乘算法输出操作数长度小于等于 29 bit,在算法3第 11 行利用进位传播 carry_PPG 将每个分支的长度减少到 29 bit 内,当冗余空间为 3 bit 时,最多两轮进位传播就可完成此约减.约减的原理是将每个分支分为两部分:hili,低 29 bit 部分 li和剩余比特部分 hi,每
46、部分都有相应的权重,将权重相同的部分相加,每个分支的长度最多不超过 29 bit.最后一个分支与上一个分支的进位相加,结果分为两种情况:第一种情况为分支长度小于等于 29 bit,符合要求,不进行额外处理;第二种情况分支长度大于 29 bit,使用同余式(6)的第一个公式约减.至此 t0 t8每个分支长度约减到安全范围内,可以作为其他素域运算的输入而不产生溢出.在模乘具体实现中,本方案未使用 AVX512 指令集中的置换指令,相比728Journal of Cryptologic Research 密码学报 Vol.10,No.4,Aug.2023Huang 的模乘算法15减少了模乘的时延,提
47、高了吞吐量.算法 3 8 路并行快速模约减算法Input:M=T17,T16,T15,T2,T1,T0Output:R=T8,T7,T1,T0=M mod p1R1 T8,T7,T6,T5,T4,T3,T2,T1,T0;R2 3T17,T16,T15,T14,T13,0,T11,T10,T925;2R3 T16,0,0,0,0,0,0,0,029;R4 T15,0,0,0,0,0,0,0,0212;3R5 T14,0,0,0,0,0,0,0,0215;R6 T13,0,0,0,0,0,0,T17,T16217;4R7 T12,0,0,0,0,0,0,T16,T15220;R8 T11,0,0,
48、0,0,0,0,0,0223;5R9 T10,T9,0,0,0,0,0,0,0226;R10 0,T13,T12,T11,T10,T9,0,0,T17214;6R11 0,T17,T16,T15,T14,0,T12,T11,022;R12 0,0,T17,T16,T15,0,0,0,0;7R13 0,0,0,0,T17,T16,0,T14,T13225;R14 0,0,0,0,0,T17,0,T15,T14222;8R15 0,0,0,0,0,0,0,T13,T12228;R16 0,0,0,0,0,T11,0,0,028;9R17 0,0,0,0,0,T10,T9,0,0211;R18 0,
49、0,0,0,0,0,T16,0,0222;10R19 0,0,0,0,0,0,T15,0,0225;11return R carry_PPG(R1+R2+R3+R4+R5+R6+R7+R8+R9+R10+R11+R12+R13+R14+R15 R16 R17 R18 R19).3.2.3模平方模平方算法是模乘的一个特例,可以看作两个操作数相同的模乘运算,通常比模乘算法快.由于中间乘积结果 aiaj,i=j 出现两次,在计算出 aiaj后,可以使用移位指令来实现 2 倍运算,减少了指令数量,其余计算过程和模乘类似.3.2.4模逆模逆运算最常使用的方法是扩展欧几里得算法,该算法非常高效,但执行流程
50、不规则且运行时间依赖于操作数,容易受到计时攻击和简单功率分析攻击3.本方案使用费马小定理实现恒定时间的模逆算法,一方面是因为 8 路模逆运算下 8 个元素的求逆流程需要保持一致;另一方面可以提高算法的安全性.对于素域中的元素 z Fp,其逆元 z1 zp2mod p,本方案使用加法链26将模逆运算转换为模乘和模平方运算,并调用并行模乘和模平方算法来提高吞吐量.3.3标量乘法并行运算在 SM2 数字签名算法中,标量乘法分为两类:固定基点标量乘法和可变基点标量乘法.本文针对这两类标量乘法分别设计了并行优化方案,其中可变基点标量乘法的点运算基于 Co-Z 雅可比射影坐标.雅可比坐标下的点运算可以避免
