国密算法Python工具包的性能优化方法

谢振杰 付 伟 罗 芳

1(海军工程大学信息安全系 武汉 430033)2(中国人民解放军78156部队 重庆 400039)

中国商用密码标准算法是指国家密码管理局认定的一系列国产商用密码算法,即国密算法.其中SM2是我国自主设计的基于椭圆曲线密码(elliptic curve cryptosystem, ECC)的公钥密码算法(以下简称“SM2”)[1-5],包含数字签名、密钥交换和公钥加密,对应RSA,ECDSA,DH,ECDH等国际算法.SM3是我国自主设计的密码杂凑算法(以下简称“SM3”)[6],对应MD5,SHA-1,SHA-2等国际算法.SM4是我国自主设计的分组密码算法(以下简称“SM4”)[7],用于数据加解密运算以保证机密性,对应DES,AES等国际算法.祖冲之密码是我国自主设计的序列密码算法(以下简称“ZUC”)[8],是我国首个成为国际标准的密码算法,在5G通信领域至关重要.国密算法作为国家网信自主安全的重要基础设施,具备高安全性且自主可控[9],正在各领域加速推广,其在各平台的实现性能同样是一个不容忽视的问题.

Python作为一种解释型程序设计语言,其代码简洁易学、第三方资源丰富的特性极大提升了编程效率.但Python的运行效率(指单位时间处理的数据量)相比编译型语言(如C语言)有明显短板,在运算量大、实时性高的场景下,Python程序可能成为性能瓶颈.随着国密算法逐步推广应用,国内Python程序员(特别是信息安全软件开发者)对便捷、稳定、高效的国密算法Python工具包有迫切需求.对于国密算法的软件实现及优化,近年来国内已有一些研究成果,如:文献[10]研究了SM4算法快速软件实现方法;文献[11-12]研究了ZUC算法快速软件实现方法;文献[13]从椭圆曲线计算、有限域上的大整数计算以及处理器平台等层面研究了SM2算法的性能优化;文献[14]介绍将国密算法集成到OpenSSL的工作.上述均采用C语言或汇编语言.文献[15]实现了国密算法JavaScript通用密码库.对于在Python环境下高效实现国密算法,尚未见系统的、效果足够好的研究成果或开源代码.

当前,采用Python语言编写的国密算法第三方库主要是gmssl[16]和snowland-smx(pysmx)[17],二者实现了SM2,SM3,SM4等国密算法.然而,相较于更为成熟的国际密码算法库PyCryptodome[18],gmssl或pysmx中同类密码运算的运行效率低1～3个数量级.究其原因,gmssl和pysmx使用纯Python语言编写,由Python解释器逐行解释执行,而PyCryptodome库的核心算法使用C语言编写,编译成链接库后供Python调用,编译后的机器代码在执行效率上有显著优势.此外,gmssl和pysmx尚有诸多细节值得改进.因此,当系统对密码运算性能有较高要求时,现有的国密算法Python库可能难以满足需要,这在一定程度上阻碍了国密算法在Python环境下的推广应用.

针对上述问题,本文开发了高效的国密算法Python工具包,可支持SM2,SM3,SM4,ZUC这4种国密算法,相较于现有的国密算法Python库gmssl和pysmx,性能有大幅提升,基本与国外成熟的PyCryptodome库的同类密码算法性能相当.开发过程参考了gmssl,pysmx,PyCryptodome的代码以及相应的国家标准[1-8].

1 性能优化

相较于gmssl和pysmx对国密算法的Python实现,本工具包采用的性能优化方法如下(按照性能提升幅度由高至低排序).

1.1 Numba加速

Numba是一个第三方Python库[19],用于把Python代码先编译成机器代码再执行,对数值计算和循环的加速效果尤其明显,可极大提升代码运行效率.由于在Python中“一切皆为对象”,变量采用弱类型,而编译成机器代码需要明确指定类型,所以使用Numba加速的代码要牺牲一部分Python语言特性,代码风格介于Python和C之间.Numba只支持部分Python内置库和函数,但对数值计算常用的第三方库Numpy[20]有很好的支持.通过cProfile(Python内置的性能分析工具)对密码算法运行过程进行分析,发现耗时主要来自循环执行的数值计算,而这正是Numba擅长的部分.参考Numba规范重写SM3,SM4,ZUC的核心代码后,运行效率可提升100倍以上.

1.2 调用PyCryptodome库的椭圆曲线运算

SM2的主要耗时来自椭圆曲线点乘,涉及大整数运算,自主实现大整数运算并用Numba加速后,运行效率反而不及Python内置的大整数运算.而PyCryptodome库实现的椭圆曲线运算与SM2是一致的,采用编译好的C链接库,且允许自定义椭圆曲线参数.因此,调用PyCryptodome库的椭圆曲线运算链接库,装载SM2椭圆曲线参数,运行效率比纯Python实现的SM2椭圆曲线运算高5～10倍.

1.3 采用预计算加速SM2基点点乘

SM2在生成密钥、签名、验证、加密运算中,以及密钥交换的双方,均需要运行1次基点点乘(k·G)运算,采用预计算技术可显著提升计算效率[13].标量k是一个256b的整数,令其二进制下1的数量占一半且最高位为1,则采用二进制展开法[1]计算k·G需要进行255+127=382次点加运算.若将k视为32B数据,对于k上的每个字节Bi,预先计算出Bi=1,2,…,255(i∈[0,31])而其他字节为全0时的k·G坐标并保存,则计算任意k·G最多仅需31次点加运算.而每个点坐标为512b即64B,预计算数据大小仅为255×32×64B=522240B=510KB.虽然理论上应提速12倍,但从1次调用点乘变为多次调用点加,频繁调用链接库使开销增大,所以采用预计算进行基点点乘的实测效率约为普通点乘的4～5倍.

1.4 并行运算

Numba支持各循环轮次的并行运算.对于SM4算法,ECB模式下的加密和解密、CBC模式下的解密可并行执行,并行运算可使效率提高1～2倍.由于单线程运算量较小,且引入多线程有额外的通信和调度开销,线程数达到4以后,设置更多的线程数也不会有明显提升.

1.5 构造双字节S盒快表

在SM4和ZUC中,S盒变换是高频操作,传统做法是用长度为256B的S盒表逐个字节转换.初始化阶段构造双字节S盒快表(大小为256×256×2B=131072B=128KB),S盒查表操作可减少一半,“移位”和“按位与”运算也大幅减少.实验表明,双字节S盒快表可使SM4和ZUC的运行效率提高10%～20%.

1.6 减少函数调用

函数调用使代码简洁,但高频的函数调用会引入额外开销.例如SM3,SM4,ZUC有大量循环移位运算,将循环移位的函数去掉,再尽可能消除“& 0xffffffff”运算(“& 0xffffffff”用于确保值大小为32b,对于64位处理器,运算中间值也可超过32b,仅在最后赋值前再进行“& 0xffffffff”运算;但同一变量连续2次循环移位之间不能将其省略,否则会引起计算错误),运行效率提高10%～16%.

1.7 避免中间类型转换

在gmssl和pysmx中,各函数间传递的数据类型在整数(int)、字节串(bytes)、16进制字符串(str)和列表(list)之间反复转换,这类冗余操作应尽可能避免.尽量用同一种数据类型完成运算和参数传递,运行效率可提高8%～15%.

1.8 针对Python的专门优化

构造双字节S盒快表、减少函数调用和避免中间类型转换对所有编程语言都适用,针对Python语言还可作以下优化:一是用类型明确的数组代替弱类型的列表;二是用生成器表达式代替列表推导;三是能在原数组上修改就不要生成新数组,等等.通过若干实现细节的优化,运行效率可提高5%左右.

2 功能扩展

相较于gmssl和pysmx,本工具包还包含以下扩展.

2.1 包含SM2密钥交换协议

gmssl和pysmx仅实现了SM2数字签名和公钥加密算法,没有实现SM2密钥交换协议,互联网上也未找到实现SM2密钥交换协议的开源Python代码,故本工具包可能是首次在互联网上开源SM2密钥交换协议的Python代码.

2.2 SM2实现更完整

gmssl和pysmx实现的SM2数字签名算法不包含国标[2]规定的Z值计算和Hash变换,gmssl库仅能输入bytes类型消息,而本工具包完整实现了SM2数字签名算法的Z值计算和Hash变换,可适配多种类型的输入(str和bytes).此外,除核心算法外,本工具包还实现了国标[1-4]描述的一些重要辅助函数(如密钥派生函数、公钥验证、椭圆曲线系统参数验证等).

2.3 区分加速版和未加速版

本工具包同时实现了SM2,SM3,SM4,ZUC这4种国密算法的加速版和未加速版,二者内部结构基本一致,功能相同,各算法的代码文件相互独立(除SM2需调用SM3),不设工具函数模块,框架清晰.加速版使用Python第三方库Numba和PyCryptodome,运行效率明显提高,便于计算机高效执行,但舍弃了部分Python语言特性,牺牲了代码可读性.未加速版采用纯Python实现,不依赖第三方库,体现了除Numba和PyCryptodome之外的所有优化,代码简洁、可读性强,适合初学者学习算法代码.

3 实验与分析

本文实验主要展示国密算法Python工具包加速版和未加速版以及现有国密算法Python库gmssl和pysmx所实现的SM2,SM3,SM4,ZUC这4种国密算法的运行效率,此外引入ECC-256,MD5,SHA-256,AES-128,RC4这5种国际密码算法(均来自国际密码算法库PyCryptodome)作为对比.

3.1 实验环境与参数

能运行Python 3代码的处理器和操作系统均可运行本工具包.经不同平台测试,其运行效率的绝对值随着CPU性能差异而有所浮动,但与其他库对比的相对值基本稳定.实验计算机的配置如表1所示:

表1 实验计算机配置

除SM2以外,每轮测试预先生成100MB随机数据,分别以32B,1KB,32KB,1MB这4种大小的数据块读取,测试各密码算法对不同长度消息的连续运算速率.所有实验均执行1000次,取平均值为有效数据.

3.2 SM2测试

SM2最耗时的环节是椭圆曲线点乘运算.随机生成1000个[1,n-2]范围内的大整数(n为椭圆曲线基点G的阶),由各库分别执行基点点乘运算,速率如图1所示.其中前7项的椭圆曲线参数为SM2标准参数[5],而ECC-256采用美国标准NIST P-256参数[18].未加速版实现了国标[1]描述的3个点乘算法(图1中标注为算法1、算法2和算法3),实测算法2(加减法)最快.加速版调用了PyCryptodome库的椭圆曲线运算链接库,达到ECC-256普通点乘的性能,该库还针对NIST P-256参数的数学特性进行了优化,因此ECC-256的基点点乘明显快于普通点乘.而进一步采用预计算技术的SM2基点点乘效率与ECC-256基本一致,约为普通点乘的4.4倍.

图1 椭圆曲线点乘运算测试

未加速时(指采用算法2点乘的未加速版,下同)点乘运算速率为gmssl的3.0倍、pysmx的1.6倍,预计算加速后的点乘运算速率为gmssl的49.3倍、pysmx的25.9倍、未加速时的16.4倍.

SM2公钥加解密、数字签名与验证以及密钥交换的速率如图2所示.密钥交换测试只计双方的纯数据计算,不包含网络传输等其他开销(gmssl和pysmx未实现SM2密钥交换协议,故没有相应数据).

图2 SM2算法测试

可见,各版本SM2实际运算的效率基本符合点乘运算测试结果.加速后运行效率约为gmssl的12～27倍、pysmx的7～16倍、未加速时的4～10倍.作为对比,另测试了ECC-256的签名/验证(即ECDSA算法),本实现速率分别为其6倍和1.2倍,PyCryptodome库目前仍没有实现ECC加密与解密.

3.3 SM3测试

各密码杂凑算法的运算速率如图3所示.

图3 密码杂凑算法的运算速率

加速版SM3处理短消息(指32B,下同)的速率为gmssl的73.9倍、pysmx的46.5倍、未加速版的32.6倍,达到PyCryptodome库SHA-256速率的1.3倍;处理长消息(包含1KB,32KB,1MB,下同)的速率约为gmssl的645倍、pysmx的402倍、未加速版的298倍,达到SHA-256速率的79.3%.

3.4 SM4测试

各分组密码算法在ECB和CBC这2种分组密码工作模式下的加解密运算速率分别如图4、图5所示(图中仅标注了加密运算速率的数值).

图4 分组密码算法在ECB模式下的运算速率

图5 分组密码算法在CBC模式下的运算速率

ECB模式下,加速版SM4加解密短消息的平均速率为pysmx的131倍、gmssl的45.1倍、未加速版的16.7倍,达到PyCryptodome库AES-128速率的1.2倍;加解密长消息的平均速率约为pysmx的610倍、gmssl的377倍、未加速版的137倍,达到AES-128速率的28.9%.

CBC模式下,加速版SM4加解密短消息的平均速率为pysmx的73.6倍、gmssl的30.0倍、未加速版的10.4倍,达到AES-128速率的2.7倍;加密长消息的速率约为pysmx的257倍、gmssl的167倍、未加速版的57.7倍,达到AES-128速率的48.2%;解密长消息的速率约为pysmx的467倍、gmssl的295倍、未加速版的112倍,达到AES-128速率的85.8%.

可见,与PyCryptodome的AES-128相比,本工具包SM4在ECB模式下加解密长消息、CBC模式下加密长消息的速率相对落后,而在CBC模式下加解密短消息时更快,其余情况下速率基本相当.

3.5 ZUC测试

各序列密码算法的运算速率如图6所示(序列密码算法的加密和解密是同一种运算).

图6 序列密码算法的运算速率

加速版ZUC处理短消息的速率为pysmx的42.7倍、未加速版的24.0倍;处理长消息的速率约为pysmx的106倍、未加速版的61.4倍.本工具包ZUC的运算速率慢于PyCryptodome的RC4,但ZUC的安全性高于RC4.

4 结 语

综上,采用Numba编译核心算法Python代码,调用PyCryptodome库的椭圆曲线运算并采用预计算加速基点点乘,以及运用其他优化后,Python实现的各国密算法的运行效率比现有国密算法Python库gmssl和pysmx提高1～3个数量级,基本与PyCryptodome库的同类密码算法效率相当.本工具包大幅提升了国密算法在Python环境下的数据处理能力,一定程度上解决了现有国密算法Python库性能不足的痛点.本工具包的全部代码(包含SM2,SM3,SM4,ZUC这4种国密算法的加速版和未加速版,以及上述全部测试代码)均已在码云平台开源(详见https://gitee.com/basddsa/hggm).