商密算法性能优化研究与实践

密码是网络空间安全的根本性核心技术。我国将密码分为核心密码、普通密码、商用密码。商用密码用于保护不属于国家秘密的信息，被广泛应用于政务、金融、能源、交通、水利、通信等行业领域以及大众消费场景，与关键信息基础设施安全、社会稳定以及经济发展等息息相关。我国高度重视商用密码的发展与应用，先后提出了多项商用密码算法，并以标准牵引、顶层推广等方式，有效促进商用密码在各行业、各领域、各场景的深化应用。一直以来，高效率密码运算是密码技术及密码产品的核心。学术界、工业界均对商用密码进行性能优化研究与实践，提升核心竞争能力，保障高质量密码供给。本文关注商用密码算法的高性能软件实现技术，以体系化技术分析的视角，深入研究SM2、SM3及SM4等算法的高性能实现方法，从理论分析与仿真评估的维度给出不同优化方法的对比分析结果，得出不同优化技术的应用建议，最后以应用实践的方式介绍高性能商密算法的典型场景，对高质量密码供给与应用能力建设有一定参考价值。1商用密码算法简介我国大力发展商用密码技术与应用，已公开的商用密码算法包括SM1、SM2、SM3、SM4、SM7、SM9及ZUC（祖冲之）算法。SM2、SM3、SM4这3项密码算法是PKI体系最常用的算法，也是使用最为广泛的商密算法，鉴于此，本文重点研究此3种算法。SM2、SM3、SM4算法均由中国国家密码管理局发布，并先后成为密码行业标准、国家标准及国际标准。SM2算法是我国采用的公钥密码算法，其安全性基于椭圆曲线离散对数困难问题，算法主要包括数字签名、密钥交换协议和公钥加密算法3个部分。在PKI体系中，基于SM2算法的数字签名技术在我国电子认证领域已广泛应用。SM3算法是我国采用的密码杂凑函数标准，消息分组长度为512位，摘要值长度为256位。SM3算法广泛应用于密码协议、数字签名、消息鉴别、完整性认证等领域。SM4算法是我国采用的分组密码算法，算法采用非平衡Feistel结构，加密算法和密钥扩展算法迭代轮数均为32轮，分组长度和密钥长度均为128比特。SM4算法主要用于数据的机密性保护，在音视频加密保护、云存储加密、数据库加密、安全通道保护、敏感信息保护等领域广泛使用。2商密算法性能优化技术研究本节针对SM2、SM3、SM4算法特点，基于工业界、学术界已有成果，结合最新技术发展趋势，分层次、体系化地梳理研究商密算法的高性能软件实现技术。2.1SM2算法性能优化SM2算法是基于椭圆曲线的公钥密码算法，算法依赖于椭圆曲线上的点运算，包括点加、倍点、点乘（标量乘）运算，以及有限域上大整数的算术运算，包括有限域上的加法、减法、乘法、乘法逆等。这些运算使得SM2具有层次结构，自上而下可以将其分为4层，如图1所示。在算法优化中首先关注椭圆曲线点运算，其次是有限域中大数运算，这些算法的计算量大、结构复杂，存在算法效率不高、资源消耗较多等问题，因此国内外众多学者对椭圆曲线算法、大整数基本运算进行了大量的研究。本节就SM2算法的主要优化方法进行了研究总结，总体而言优化方法可以分为椭圆曲线运算优化、大整数运算优化两大类。图1SM2算法层次结构2.1.1不同坐标系中点加与倍点运算椭圆曲线上点坐标的表示方法

主要用仿射坐标(x,y)和射影坐标(x,y,z)表示，这两种坐标可相互转换。射影坐标一般分为标准射影坐标、Jacobian加重射影坐标。仿射坐标中椭圆曲线的表示方程公式为：该群中点的表示方法为(x,y)。标准射影坐标(x,y,z)对应的仿射坐标为将的对应关系代入椭圆曲线中可得标准射影坐标下的方程为：Jacobian加重射影坐标(x,y,z)对应的仿射坐标为将对应关系代入曲线

得到在Jacobian加重射影坐标下的方程为上述坐标中的点加运算、倍点运算（两个相同点的点加运算）可在相应坐标方程下换算得到。2.1.2点乘运算椭圆曲线点乘为R=kP，其中k为整数，P为椭圆曲线上的任意点。点乘运算通过点加与倍点运算构成，它是椭圆曲线最核心且非常耗时的运算，其计算速度从整体上决定了椭圆曲线密码体制的效率。目前点乘运算的研究方法很多，主要为k的表达形式与预处理方式。k的表达形式是将k进行不同的表示后，在计算k的过程中融入点加与倍点运算得到点乘结果。预处理方式是P为固定值，将P的倍点进行存储，然后通过查表计算当前倍点值。以下给出了有代表性的研究方法。（1）二进制方法。二进制表示方法将k以二进制的形式展开为通过展开后的二进制串使用霍纳法则计算k。（2）NAF展开法。非相邻型表示（NonAdjacentForm，NAF）是k的一种带符号表示方法，k的NAF表示为且没有两个连续的数字是非零的，为k的展开序列。（3）窗口方法。窗口方法的思想是一次扫描w位（w为窗口宽度），使点P一次完成的计算，从而利用空间提高计算效率。有两种表现较好的窗口算法。第1种为固定窗口算法，将k用二进制表示后，用固定长度w按照一定的规则划分，即k的表示为其中表示向上取整。此方法可将分组数据重新编码为规则模式，如使用booth编码方法编码分组数据，从而防止点乘运算通过侧信道泄漏信息，提高实现安全性。第2种为滑动窗口算法w-NAF，整数NAF表达形式是将每两位至多出现一个非零值的思想，演化为每w位中至多出现一个非零值，整数k表示为其中非零时都是奇数，且称为k的w-NAF表示，记为（4）双基链方法。双基链算法是基于Dimitrov提出的一种双基数系统，将整数k用两个不同的基表示，其最多在O(logk/loglogk)的时间复杂度内表示一个数。在双基链系统中，对任意整数k可表示为将整数k的双基链表示形式记为D(k)，可通过贪心算法来编码得到双基链形式。2.1.3素数域大整数运算椭圆曲线上的点运算最终为有限域上的算术运算，有限域算术运算实现效率也影响着整数算法实现的效率。有限域上的运算包括加法、减法、乘法和模逆等基本运算，域上的加法、减法运算与代数运算方法基本相同，不同之处在于其运算结果需要求模，即约减。有限域上的约减、模乘、模逆等计算都非常复杂，耗时多，因此本节对这几种方法进行研究。（1）约减。约减是有限域中的基本运算之一，针对约减的优化主要有Barrett约减、Montgomery约减、快速约减这3类方法。Barrett约减是一种低成本的求商运算，估算出一个近似值使得其中n是一个很小的数，因此最终的结果r通过少数的减法计算得出。Montgomery约减是通过移位代替除法的一种方法，给定整数X，选取r为2的n幂，然后计算时右移n位完成取模运算。快速约减的思想是当模数为素数时通过多次加法与减法操作代替除法，从而快速求得取模结果。（2）模乘。本文称用于的运算为模乘运算，实际上就是将乘法结果取模。模乘是公钥密码体制中的基本算法之一，其运行速度对公钥密码算法起着重要的作用。很多学者对模乘算法进行优化改进，常见的方法有基于Barrett约减的模乘算法、KOA快速乘法以及Montgomery模乘算法。（3）模逆。对于素数如果存在使得则称为a模p的逆元。有限域中逆元计算量比乘法和平方耗时多。常见的素域上求逆的方法有扩展欧几里得算法、基于二进制的扩展欧几里得算法、Lehmer扩展欧几里得算法等。扩展欧几里得算法反复使用辗转相除法，通过辗转相除中的商反演计算出两个正整数的最大公约数，即可找到两个整数s、t使得若等式两边同时模p可得，则s为a模p的逆。整数除法可通过移位操作实现，根据这一思想有了基于二进制的扩展欧几里得算法。使用欧几里得算法求逆过程中需多次进行大整数除法运算求商，而大整数的除法运算非常耗时，因此如果只用两个数的高位计算商时，可提高计算效率。Lehmer扩展欧几里得算法的思想是用小整数的除法代替大整数的除法，小整数的扩展欧几里得算法替代大整数的扩展欧几里得算法，从而提高计算效率。2.2SM3算法性能优化如图2所示，SM3杂凑算法采用M-D结构的构造方式，对长度为比特的消息m通过填充分组、消息拓展、迭代压缩的方式生成256比特的杂凑值。图2SM3M-D结构文献[13]利用IntelVTuneAmplifierXE分析了普通实现SM3算法的热点，压缩函数和消息拓展是最耗时的部分，其耗时分别占总耗时的65.9%和24.3%。因此，SM3算法中的压缩函数和消息拓展是实现SM3算法性能优化的重要方法。此外，随着硬件技术的发展，X86、ARM等主流硬件平台均推出了SIMD指令，可以在上述环节嵌套并行指令以进一步提升性能。2.2.1消息拓展和压缩函数优化SM3算法性能优化主要是从消息拓展和压缩函数两方面展开。消息拓展是将512比特的消息分组扩展到132个消息字。在优化实现中，将拓展的132个消息字计算调整到压缩函数中执行，以减少数据加载和存储。压缩函数的优化实现可以通过调整结构和流程、常数计算等方面着手，可归纳为减少压缩函数循环移位导致的赋值运算次数；对压缩函数的中间变量生成流程进行优化，去除不必要的赋值，减少中间变量个数；利用预计算和存储常数，以进一步优化常数运算。2.2.2SIMD并行指令优化上述技术方案未考虑硬件指令加速的情况。事实上，SIMD指令可以加速消息拓展的部分实现，图3较为清晰地展示出了如何利用SIMD优化SM3。图3SIMD优化的SM3每一个是32bit的字，4个

可以填满1个SIMD寄存器。图3右侧就是把消息放进SIMD寄存器，然后再做消息扩展。和图3左侧1次计算出一个字相比，右侧一次可以计算出3个字之所以不是一次计算出4个字是因为计算需要用到（灰色部分），但是扩展出来的，也就是说，需要的时候

还不存在。在具体的实现中，可以先等计算完成，再用图3左侧的方法计算2.3SM4算法性能优化SM4是一个分组密码算法，分组长度和主密钥长度均为128bit。128bit主密钥经过密钥拓展算法拓展为32个32bit轮子密钥，加/解密变换均为32轮轮函数F的迭代。轮函数涉及比特操作以及合成置换T。T是由非线性变换τ和线性变换L构成。上述流程中最为耗时的部分是非线性变换τ，其核心涉及S盒查表操作。目前针对SM4算法性能优化的方法也主要集中于S盒操作的优化，包括直接查表优化、SIMD优化、复合域

及比特切片等。2.3.1查表优化查表优化实现是SM4算法优化实现方法中最早出现、最常见的方法，其核心思想是将密码算法轮函数中尽可能多的变换操作通过预计算制成表，即通常所说的“查大表”。2.3.2SIMD并行指令优化并行分为细粒度并行和粗粒度并行2种。由于SM4算法不适合使用细粒度并行，因此选取粗粒度并行策略实现SM4。粗粒度是多组消息的并行处理，分组密码通常是在某种工作模式下加/解密大量数据，在特定的工作模式，如在电码本模式（ElectronicCodebookBook，ECB）、计算器模式（Counter，CTR）、Galois计数器模式（Galois/CounterMode，GCM）、密码分组链接模式（CipherBlockChaining，CBC）（解密方向）下，分组密码可并行处理多组消息。下述为128bit寄存器下的SIMD并行操作：（1）查表指令：首先使用1～4个128bit的向量寄存器构成查找表，其次使用另一个128bit寄存器作为索引，将结果存入128bit寄存器中。（2）SM4并行查表：SM4的S盒一共有256×8bit，即需要消耗16个向量寄存器存储查找表，每次查表最多能使用4个向量寄存器作为查找表，进行4轮的查表。（3）SM4数据加载：在一轮SM4迭代过程中，需要查表的数据为32bit，为了尽可能利用好128bit的向量寄存器，将4组消息的32bit集中于同一个向量寄存器中。2.3.3复合域及比特切片与传统基于查找表法的方式相比，该方法采用代数运算的方式，计算较为简单。S盒的运算由两部分构成：线性的仿射变换和非线性的有限域求逆。仿射变换容易实现，因此主要计算难度在于的求逆问题。根据有限域性质，通过同构变换，将的有限域运算变到复合域上进行。在实际流程中，通过比特切片技术，编排待处理数据的存储结构，然后使用仿射变换与有限域上的求逆来代替S盒查表，通过复合域大大降低域运算的复杂度。3商密算法性能优化分析评估本节对前述商密算法优化技术进行理论分析与仿真评估，给出不同优化方法的对比分析结果，最后从实践的角度给出应用建议。3.1SM2算法性能优化分析评估3.1.1点加与倍点运算点加与倍点是椭圆曲线的计算基础，不同坐标系下其计算方法不同导致计算效率也不同。仿射坐标计算点运算需求模逆，计算复杂度高，耗时多，效率低，因此在实际工程实现中通常不考虑该方法。相比来说，Jacobian加重射影坐标的运算效率最高，因此在工程实现中通常采用Jacobian加重射影坐标进行点运算。为了方便使用，工程实现对外点的表示使用仿射坐标，内部计算时存在Jacobian加重射影坐标与仿射坐标的相互转换。3.1.2点乘运算本文研究了点乘运算二进制方法、NAF展开法、窗口方法以及双基链方法。二进制方法中非零符号的汉明权重未做优化，开销较大，现已很少使用。NAF展开法的性能通常会低于窗口方法。双基链方法使用贪心算法，汉明权重很难预估，运行速度不确定因素较大，工程应用较少考虑。本节将重点对比分析窗口方法中的滑动窗口算法w-NAF、booth编码与固定窗口结合方法。SM2算法素数域长为256位，在256位数据长度中对不同宽度下基于w-NAF与基于booth编码的两种点乘算法进行性能分析。本节针对两种不同点的形式（固定点乘与非固定点乘）分别进行了比较分析，结果见表1，其中，PA和PD分别代表一次点加和倍点运算，M代表一次乘法运算。表1 w-NAF与booth编码的点乘性能分析对固定点采用预计算存储方式实现点乘运算时，随着宽度增加，两种方法的计算量都在减少、存储量增加。宽度相同时基于w-NAF方法的计算开销比基于booth方法的计算开销高很多，存储开销少很多。为提高计算效率，基于booth编码的方法效率会更高。选择宽度时，如不考虑存储开销则宽度越大效率越高，但实际应用中，存储资源是有限的，应综合考虑计算与存储开销，因此选择宽度为7的基于booth编码的算法较为适用。当点不固定时，两种算法在宽度为5处计算开销都最低。当两种计算开销最低时，基于w-NAF的点乘性能稍优于基于booth编码的点乘性能。SM2算法中两种点乘方式的使用频率基本相等，综合分析SM2算法采用基于booth编码方式实现的效率会更高，并且安全性更好。3.1.3素数域大整数运算在约减运算方面，Barrett约减及Montgomery约减性能大致相当。快速约减算法不需要除法，性能是最好的，推荐使用。在模乘运算方面，由于Montgomery模乘算法通过移位避开了除法运算，其性能优于Barrett约减的模乘算法及KOA快速乘法，推荐使用。同时，Montgomery模乘算法底层使用Montgomery约减算法，因此在工业应用中可配合使用。在模逆运算方面，重点分析比较基于二进制的欧几里得求逆算法和Lehmer扩展欧几里得求逆算法。本文在Intel(R)Core(TM)i5-7500平台上，用32字节的数据测试了两种求逆方法的性能，测试结果如表2所示。测试结果表明Lehmer欧几里得算法的性能是二进制欧几里得算法的4倍左右。推荐采用Lehmer欧几里得算法。表2 两种模逆算法性能测试结果3.2SM3算法性能优化分析评估本文对2.2节提出的两项SM3性能优化技术方案进行测试验证。方案1为C语言实现，采用消息拓展和压缩函数。方案2为汇编实现，采用消息拓展压缩函数以及SIMD指令。对比基线为原始未优化算法。经试验测得，方法1和方法2加速效果相当，相比于原始算法性能均能提高1倍左右。不同之处在于方案1的性能与平台差异较小，方案2的性能与平台关系较大，若平台对汇编指令支持不够友好，则可以用于并行加速的部分甚少，加上汇编语言会增加代码的复杂度，整体性能会有所下滑。在具体项目应用中，建议在兼容性较好的硬件平台采用方案2，在硬件环境比较特殊的场景下采用方案1。3.3SM4算法性能优化分析评估本文2.3节研究了3项SM4性能优化技术方案。本节针对查表优化（方案1）、SIMD并行指令优化（方案2）两项技术方案进行了对比测试，对比基线为原始未优化算法。采用SM4ECB模式。经试验测得，方案1相比于基线方案性能提高至2.7倍，方案2相比于基线方案性能提高至5倍。整体来说，方案2的性能优于方案1，但方案2与平台相关，加速效果不尽相同，方案1跨平台，可以广泛使用。此外，比特切片及复合域等创新技术往往是在SIMD基础上进行的再度优化，性能高于方案1和方案2，但该方法也存在硬件平台的差异，推荐在硬件支持的情况下使用。3.4评估分析总结基于上述分析，总结商密算法性能优化方法的性能情况、应用场景并给出推荐指数建议，见表3。针对SM2、SM3、SM4算法，本文总结的相关方法大部分可以配合使用，以达到性能叠加的效果。同时部分优化技术与硬件平台强关联，比如CPU指令集是否支持、CPU位宽情况、硬件存储资源是否受限等，在具体应用时，应结合硬件资源情况，进行方法的组合和筛选，在满足实际需求的同时最大限度地提升性能。4商密算法性能优化应用实践随着“等保”“密评”“国