商密算法性能优化研究与实践
摘 要:商用密码算法的高性能实现是影响网络安全建设与密码泛在化应用的重要环节。聚焦SM2、SM3、SM4 算法,体系化、层次化研究不同商密算法的高性能软件实现优化技术,从理论分析、测试验证等维度对比分析优化技术并形成应用建议,以应用实践的方式介绍高性能商密算法的典型场景,为高质量商用密码发展提供支撑。
内容目录:
1 商用密码算法简介
2 商密算法性能优化技术研究
2.1 SM2 算法性能优化
2.2 SM3 算法性能优化
2.3 SM4 算法性能优化
3 商密算法性能优化分析评估
3.1 SM2 算法性能优化分析评估
3.2 SM3 算法性能优化分析评估
3.3 SM4 算法性能优化分析评估
3.4 评估分析总结
4 商密算法性能优化应用实践
4.1 面向政务云的高速率 SM2 签名服务应用
4.2 基于高性能商密算法的隐私计算应用
5 结 语
密码是网络空间安全的根本性核心技术。我国将密码分为核心密码、普通密码、商用密码。商用密码用于保护不属于国家秘密的信息,被广泛应用于政务、金融、能源、交通、水利、通信等行业领域以及大众消费场景,与关键信息基础设施安全、社会稳定以及经济发展等息息相关。
我国高度重视商用密码的发展与应用,先后提出了多项商用密码算法 ,并以标准牵引、顶层推广等方式,有效促进商用密码在各行业、各领域、各场景的深化应用。一直以来,高效率密码运算是密码技术及密码产品的核心。学术界、工业界均对商用密码进行性能优化研究与实践,提升核心竞争能力,保障高质量密码供给。
本文关注商用密码算法的高性能软件实现技术,以体系化技术分析的视角,深入研究 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.1 SM2 算法性能优化
SM2 算法是基于椭圆曲线的公钥密码算法,算法依赖于椭圆曲线上的点运算,包括点加、倍点、点乘(标量乘)运算,以及有限域上大整数的算术运算,包括有限域上的加法、减法、乘法、乘法逆等。这些运算使得 SM2 具有层次结构,自上而下可以将其分为 4 层,如图 1 所示。在算法优化中首先关注椭圆曲线点运算,其次是有限域中大数运算,这些算法的计算量大、结构复杂,存在算法效率不高、资源消耗较多等问题,因此国内外众多学者对椭圆曲线算法、大整数基本运算进行了大量的研究。本节就 SM2 算法的主要优化方法进行了研究总结,总体而言优化方法可以分为椭圆曲线运算优化、大整数运算优化两大类。
图 1 SM2 算法层次结构
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 展 开 法。非 相 邻 型 表 示(Non Adjacent Form,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.2 SM3 算法性能优化
如图 2 所示,SM3 杂凑算法采用 M-D 结构的构造方式,对长度为比特的消息 m 通过填充分组、消息拓展、迭代压缩的方式生成 256比特的杂凑值。
图 2 SM3 M-D 结构
文献 [13] 利用 Intel VTune Amplifier XE 分析了普通实现 SM3 算法的热点,压缩函数和消息拓展是最耗时的部分,其耗时分别占总耗时的 65.9% 和24.3%。因此,SM3 算法中的压缩函数和消息拓展是实现 SM3 算法性能优化的重要方法。此外,随着硬件技术的发展,X86、ARM 等主流硬件平台均推出了 SIMD 指令,可以在上述环节嵌套并行指令以进一步提升性能。
2.2.1 消息拓展和压缩函数优化
SM3 算法性能优化主要是从消息拓展和压缩函数两方面展开。消息拓展是将 512 比特的消息分组扩展到 132 个消息字。在优化实现中,将拓展的132 个消息字计算调整到压缩函数中执行,以减少数据加载和存储。压缩函数的优化实现可以通过调整结构和流程、常数计算等方面着手,可归纳为减少压缩函数循环移位导致的赋值运算次数;对压缩函数的中间变量生成流程进行优化,去除不必要的赋值,减少中间变量个数;利用预计算和存储常数,以进一步优化常数运算。
2.2.2 SIMD 并行指令优化
上述技术方案未考虑硬件指令加速的情况。事实上,SIMD 指令可以加速消息拓展的部分实现 ,图 3 较为清晰地展示出了如何利用 SIMD 优化 SM3。
图 3 SIMD 优化的 SM3
每一个是 32 bit 的字,4 个 可以填满 1个 SIMD 寄存器。图 3 右侧就是把消息放进 SIMD寄存器,然后再做消息扩展。和图 3 左侧 1 次计算出一个字相比,右侧一次可以计算出 3 个字之所以不是一次计算出 4 个字是因为计算需要用到(灰色部分),但是扩展出来的,也就是说,需要的时候 还不存在。在具体的实现中,可以先等计算完成,再用图 3 左侧的方法计算
2.3 SM4 算法性能优化
SM4 是一个分组密码算法,分组长度和主密钥长度均为 128 bit。128 bit 主密钥经过密钥拓展算法拓展为 32 个 32 bit 轮子密钥,加 / 解密变换均为 32轮轮函数 F 的迭代。轮函数涉及比特操作以及合成置换 T。T 是由非线性变换 τ 和线性变换 L 构成。上述流程中最为耗时的部分是非线性变换 τ,其核心涉及 S 盒查表操作。目前针对 SM4 算法性能优化的方法也主要集中于 S 盒操作的优化,包括直接查表优化、SIMD 优化 、复合域 及比特切片等。
2.3.1 查表优化
查表优化实现是 SM4 算法优化实现方法中最早出现、最常见的方法,其核心思想是将密码算法轮函数中尽可能多的变换操作通过预计算制成表,即通常所说的“查大表”。
2.3.2 SIMD 并行指令优化
并行分为细粒度并行和粗粒度并行 2 种。由于 SM4 算法不适合使用细粒度并行,因此选取粗粒度并行策略实现 SM4。粗粒度是多组消息的并行处理,分组密码通常是在某种工作模式下加 / 解密大量数据,在特定的工作模式,如在电码本模式(Electronic Codebook Book,ECB)、 计 算 器 模式(Counter,CTR)、Galois 计 数 器 模 式(Galois/Counter Mode,GCM)、密码分组链接模式(Cipher Block Chaining,CBC)(解密方向)下,分组密码可并行处理多组消息。下述为 128 bit 寄存器下的SIMD 并行操作:
(1)查表指令:首先使用 1 ~ 4 个 128 bit 的向量寄存器构成查找表,其次使用另一个 128 bit 寄存器作为索引,将结果存入 128 bit 寄存器中。
(2)SM4 并 行 查 表:SM4 的 S 盒 一 共 有256×8 bit,即需要消耗 16 个向量寄存器存储查找表,每次查表最多能使用 4 个向量寄存器作为查找表,进行 4 轮的查表。
(3)SM4 数据加载:在一轮 SM4 迭代过程中,需要查表的数据为 32 bit,为了尽可能利用好 128bit 的向量寄存器,将 4 组消息的 32 bit 集中于同一个向量寄存器中。
2.3.3 复合域及比特切片
与传统基于查找表法的方式相比,该方法采用代数运算的方式,计算较为简单。S 盒的运算由两部分构成:线性的仿射变换和非线性的有限域求逆。仿射变换容易实现,因此主要计算难度在于的求逆问题。根据有限域性质,通过同构变换,将的有限域运算变到复合域上进行。在实际流程中,通过比特切片技术,编排待处理数据的存储结构,然后使用仿射变换与有限域上的求逆来代替 S 盒查表,通过复合域大大降低域运算的复杂度。
3
商密算法性能优化分析评估
本节对前述商密算法优化技术进行理论分析与仿真评估,给出不同优化方法的对比分析结果,最后从实践的角度给出应用建议。
3.1 SM2 算法性能优化分析评估
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.2 SM3 算法性能优化分析评估
本文对 2.2 节提出的两项 SM3 性能优化技术方案进行测试验证。方案 1 为 C 语言实现,采用消息拓展和压缩函数。方案 2 为汇编实现,采用消息拓展压缩函数以及 SIMD 指令。对比基线为原始未优化算法。经试验测得,方法 1 和方法 2 加速效果相当,相比于原始算法性能均能提高 1 倍左右。不同之处在于方案 1 的性能与平台差异较小,方案 2 的性能与平台关系较大,若平台对汇编指令支持不够友好,则可以用于并行加速的部分甚少,加上汇编语言会增加代码的复杂度,整体性能会有所下滑。在具体项目应用中,建议在兼容性较好的硬件平台采用方案 2,在硬件环境比较特殊的场景下采用方案 1。
3.3 SM4 算法性能优化分析评估
本文 2.3 节研究了 3 项 SM4 性能优化技术方案。本节针对查表优化(方案 1)、SIMD 并行指令优化(方案 2)两项技术方案进行了对比测试,对比基线为原始未优化算法。采用 SM4 ECB 模式。经试验测得,方案 1 相比于基线方案性能提高至 2.7 倍,方案 2相比于基线方案性能提高至 5 倍。整体来说,方案2 的性能优于方案 1,但方案 2 与平台相关,加速效果不尽相同,方案 1 跨平台,可以广泛使用。此外,比特切片及复合域等创新技术往往是在 SIMD 基础上进行的再度优化,性能高于方案 1 和方案 2,但该方法也存在硬件平台的差异,推荐在硬件支持的情况下使用。
3.4 评估分析总结
基于上述分析,总结商密算法性能优化方法的性能情况、应用场景并给出推荐指数建议,见表 3。针对 SM2、SM3、SM4 算法,本文总结的相关方法大部分可以配合使用,以达到性能叠加的效果。同时部分优化技术与硬件平台强关联,比如 CPU 指令集是否支持、CPU 位宽情况、硬件存储资源是否受限等,在具体应用时,应结合硬件资源情况,进行方法的组合和筛选,在满足实际需求的同时最大限度地提升性能。
4
商密算法性能优化应用实践
随着“等保”“密评”“国密改造”等工作的推进,商用密码应用呈现泛在化发展趋势,越来越多的信息系统纷纷采用商用密码技术进行安全保护。本文选取云计算、隐私计算两大创新场景,以新技术融合应用的视角,介绍高性能商密算法应用实践。
4.1 面向政务云的高速率 SM2 签名服务应用
政务云承载了大量的政务数据与应用,具备大规模集中计算、高效率业务保障、统一身份认证等需求。在政务云中构建密码资源池,采用云签名验签服务器提供高效率的 SM2 签名服务,同时考虑系统的可扩展性,在密码资源池中基于虚拟化服务器,部署高性能 SM2 软算法,配套提供 SM2 软算法签名服务,通过软、硬两套方案协同,针对不同等级用户、不同应用对象按需提供密码运算功能,确保服务的可用性。相关应用场景见图 4。
表 3 商密算法性能优化评估总结
图 4 面向政务云的高速率 SM2 签名服务场景
4.2 基于高性能商密算法的隐私计算应用
隐私计算是数据要素化发展的关键技术,密码是其安全基石。隐私计算包含大量的对称加密、消息杂凑、非对称运算等密码算法。可基于高性能商密算法,打造安全、合规的隐私计算协议。图 5 为融合高性能商密算法的隐私计算应用场景,系统采用三方外包计算的模式,计算方在执行隐私计算协议时,将优化后的 SM4 算法应用于混淆电路场景中,优化后的 SM2 椭圆曲线算法应用于 PSI 场景中,优化后的 SM3 消息杂凑算法应用于特征工程等算法协议中,系统在实现密码算法的国密改造的同时,也极大程度地提升了性能,促进新技术的融合应用发展。
图 5 基于高性能商密算法的隐私计算应用场景
5
结 语
本文立足于 SM2、SM3、SM4 算法,分层次、成体系地梳理研究了商密软算法的高性能优化实现方法,给出了不同优化技术的理论分析与仿真评估结果,得出了相关优化技术的应用建议,并以应用实践的方式探讨了高性能商密算法的应用场景,为高质量密码能力建设提供了参考路径。下一步,将深入应用场景及平台环境,细化细分领域的算法优化技术方案,以进一步支撑高性能商密算法应用落地。