CN111736902B - 基于simd指令的sm4的并行计算方法及装置、可读存储介质 - Google Patents

Abstract

本发明提供了一种基于SIMD指令的SM4的并行计算方法及装置、可读存储介质，其包括：对输入的多个SM4分组消息进行编排得到编排后的分组消息；对编排后的分组消息执行优化过的SM4加密或者解密运算过程；对加密或者解密运算过程中的Sbox运算用复合域技术替代查表法完成计算；对复合域技术利用基于SIMD指令的GF(2^4)中的快速乘法运算完成GF(2^8)中的求逆运算；对加密或者解密运算过程进行反编排计算得到分组消息对应的密文或者明文消息。其利用复合域技术进行SM4算法非线性运算等价变换的过程,利用运算顺序调整和融合多个线性变换进行SM4算法线性运算等价变换过程以及基于SIMD指令的GF(2^4)中的快速乘法运算，提高了SM4加解密过程的执行速度。

Description

基于SIMD指令的SM4的并行计算方法及装置、可读存储介质

技术领域

本发明涉及计算机安全技术领域，特别涉及一种基于SIMD指令的SM4的并行计算方法、并行计算装置、计算机可读存储介质。

背景技术

数据加密技术是网络安全和隐私保护的基石，通常是指通过对敏感信息进行加密使得只有具备适当访问权限的人才能够进行解密并且读取敏感信息的一般过程.为了保证数据加密操作的安全性，世界各国都推出了相应的标准算法，例如美国的AES算法，日本的CLEFIA和Camellia算法以及中国的SM4、之前也称作SMS4算法。

SM4密码算法是基于4分支的广义Feistel结构构造的，明文密文和密钥都是128比特，包含加密算法，解密算法和密钥编排算法.密钥编排算法从128比特主密钥生成32个32比特的轮密钥.加密算法和解密算法都包含相同的32轮非线性轮函数以及1次反序变换R，二者的不同是32个轮密钥的使用顺序.用4 个32比特的变量

表示128比特的明文输入，则加密算法运算过程为：

1.执行32次迭代运算，RK_i为轮密钥：

T由非线性变换τ和线性变换L两部分组成T(U)＝L(τ(U))，用

表示

的4个字节，则非线性变换表示为：

V＝(v₀，v₁，v₂，v₃)＝τ(U)＝(Sbox(u₀)，Sbox(u₁)，Sbox(u₂)，Sbox(u₃))

而线性变换L表示为：

2.对最后一轮数据进行反序变换R得到密文：

(Y₀，Y₁，Y₂，Y₃)＝R(X₃₂，X₃₃，X₃₄，X₃₅)＝(X₃₅，X₃₄，X₃₃，X₃₂)

国内网络安全法，密码法的实施促进了SM4算法的普及，但是由于加解密引入的计算机信息系统事务处理速度的下降成为SM4算法普及的一个障碍.如何提高SM4算法的执行效率成为国密行业的研究热点.目前的技术手段大致分为硬件实现和软件实现两类。

硬件实现通过不断优化实现SM4算法所需的门电路个数来提高SM4算法的加解密效率，其中关键的技术是通过复合域技术，将SM4算法的Sbox在GF(2⁸) 内的非线性求逆运算等价变换成GF(2⁴)²中的求逆运算，并进一步应用复合域技术直到将运算转换成可以门电路表示的GF(2)中的运算。

软件实现目前则有4种主要的技术手段，包括GPU、SM4硬件指令、AESNI 和比特切片(Bitslice)：

1、GPU：利用GPU的并行能力提升SM4加解密效率；

2、SM4硬件指令：通过在CPU中构建支持SM4加解密算法的硬件指令；

3、AESNI：基于AES算法的Sbox和SM4算法的Sbox的代数同构特性，利用AESNI指令AESENCLAST完成SM4的Sbox运算；将SM4算法整个从SM4的代数结构中变换到AES的代数结构中；

4、Bitslice：利用Bitslice技术和AVX2指令的256比特寄存器同时处理 256个数据分组；

上述各方案的技术缺陷为：GPU和SM4硬件指令不属于通用的解决方案， AESNI则依赖于AESNI硬件指令的存在并且目前仅有支持128比特寄存器的 AESNI指令，跟256比特寄存器SIMD指令适配时，与AESNI指令相关的操作需要做串行化处理，而Bitslice需要同时处理256个数据分组(也即4096字节) 适用范围受限，Bitslice技术涉及到的数据编排步骤以及GF(2⁴)上的乘法运算都较为复杂。

发明内容

本发明针对上述现有技术中的缺陷，提出了基于SIMD指令的SM4的并行计算方法，对输入的多个分组消息进行编排得到编排后的分组消息；对所述编排后的分组消息基于SIMD指令使用GF(2^4)替代GF(2^8)完成SM4的Sbox代换计算以实现对轮函数的求逆运算，并获取求逆运算的结果；对所述求逆运算的结果进行反编排计算得到所述分组消息对应的密文消息，克服上述传统方法的种种缺点。

本发明的具体方案如下：

一种基于SIMD指令的SM4并行计算方法，其包括以下步骤：

步骤S1：对输入的多个分组消息进行编排得到编排后的分组消息；

步骤S2：对所述编排后的分组消息基于SIMD指令，使用GF(2⁴)替代GF(2⁸) 完成SM4的Sbox代换计算，以实现对轮函数的求逆运算，并获取求逆运算的结果；

所述基于SIMD指令使用GF(2⁴)替代GF(2⁸)完成SM4的Sbox代换计算过程如下：

所述Sbox代换计算过程根据256字节的代换表将8比特的输入替换为8比特的输出Sbox(u)：

Sbox(u)＝A(A·u+C)^-1+C

其中，A为8x8的矩阵，C为8x1的矩阵，u表示8bit数，矩阵A和C中的每个元素为GF(2)中的元素：

定义SM4的Sbox的数学结构为：GF(2⁸)，f(x)＝1+x²+x⁴+x⁵+x⁶+ x⁷+x⁸；

定义有限域为：GF(2⁴)，g(x)＝1+x+x⁴；

定义Sbox的数学结构与有限域的二次代数扩张同构为：

定义同构映射矩阵M和逆同构映射矩阵M^-1的值为：

因此，将v∈GF(2⁸)写成v＝a₀+a₁y，其中a₀，a₁∈GF(2⁴)，由于v^-1∈ GF(2⁸)，将v^-1表示成v^-1＝b₀+b₁y，b₀，b₁∈GF(2⁴)，则根据(a₀+a₁y)(b₀+ b₁y)＝1有：

即GF(2⁸)内的求逆运算可以在GF(2⁴)²中完成，计算过程为：

对u∈GF(2⁸)进行仿射变换得到

对

同构映射得到

对

进行复合域求逆运算得到

对

进行同构映射得到

对

进行仿射变换得到

其中，u是GF(2⁸)中的元素，u经过仿射变换得到GF(2⁸)中的元素v，对v 进行同构映射得到GF(2⁴)²中的元素w，之后对w进行复合域求逆运算得到 GF(2⁴)²中的元素w^-1，再对w^-1进行同构映射得到GF(2⁸)中的元素s，最后对s进行仿射变换，得到GF(2⁸)中的元素t，w^-1＝Inv(w)表示在GF(2⁴)²中的求逆运算；

步骤S3：对所述求逆运算的结果进行反编排计算得到所述分组消息对应的密文消息。

更进一步地，对于GF(2⁴)²中的求逆运算中的GF(2⁴)乘法运算过程为：用 GF(2⁴)^*表示GF(2⁴)的乘法子群，而g＝0x02∈GF(2⁴)^*为GF(2⁴)^*的生成元，也即所有的e∈GF(2⁴)^*，都存在1≤i≤15，使得e＝gⁱ，为了计算c＝a· b，a，b，c∈GF(2⁴)，先计算log_gc＝log_ga+log_gb，然后计算

其中，log_ga，log_gb可以通过查找包含16个元素的LOG查找表完成。

更进一步地，利用线性变换L的特性以及SIMD指令集的特性对轮函数中的线性变换L的计算过程进行调整，其计算过程为：

轮函数中的线性变换L定义为：

将线性变换L等价变换为：

其计算只需要4次比特异或，3次shuffle，1次左移，1次右移，1次比特或共计10个SIMD指令。

更进一步地，将SM4中的将反序变换R计算融入消息反编排计算过程。

本发明提供一种基于SIMD指令的SM4并行计算装置，其包括处理器和存储器，所述存储器存储计算机程序，当所述计算机程序被处理器执行时实现上述任一项的方法。

本发明还提出了一种计算机可读存储介质，所述计算机可读存储介质存储计算机程序，当所述计算机程序被处理器执行时实现上述任一项的方法。

与现有技术相比较，本发明的具有以下有益效果：

本发明提供了一种基于SIMD指令的SM4的并行计算方法及其装置、计算机可读存储介质，该方法包括：对输入的多个SM4分组消息进行编排得到编排后的分组消息；对所述编排后的分组消息执行优化过的SM4加密或者解密运算过程；对所述加密或者解密运算过程中的Sbox运算用复合域技术替代查表法完成计算；对所述复合域技术利用本发明提出的基于SIMD指令的GF(2^4)中的快速乘法运算完成GF(2^8)中的求逆运算；对所述加密或者解密运算过程进行反编排计算得到所述分组消息对应的密文或者明文消息。本发明通过利用复合域技术进行SM4算法非线性运算等价变换的过程，利用运算顺序调整和融合多个线性变换进行SM4算法线性运算等价变换的过程，以及新提出的基于SIMD指令的GF(2^4)中的快速乘法运算，给出了与SIMD指令集高度有好的SM4分组密码算法的新的执行过程，可以实现对4个，8个，16个、32个或者更多个SM4 分组消息的并行加解密处理，提高了SM4加解密过程的执行速度，并且该方法不依赖具体的硬件平台，在任何支持SIMD指令的硬件上都可以实现。

与已有的基于AESNI指令加速SM4计算过程的方法相比，本发明提出的方法不依赖AESNI这一特有的指令，仅依赖更为通用的SIMD指令。与已有的基于Bitslice技术和AVX2指令的SM4计算过程的方法相比，本发明提出的方法也具有更好的通用性，并且支持4个、8个、16个、32个分组并行处理，更加贴合使用场景。与已有的基于Bitslice技术和AVX2指令的SM4计算过程要求同时处理512个SM4分组使用场景受限。另外真实环境中测试，本发明提出的SM4 计算过程随着并行处理的消息数的翻倍，处理速度也翻倍。并且当并行处理16 或者32个分组时，实测速度比AESNI和Bitslice方法的实测速度要快出20％～30％

附图说明

通过阅读参照以下附图所作的对非限制性实施例所作的详细描述，本申请的其它特征、目的和优点将会变得更明显。

图1为本发明一种基于SIMD指令的SM4的并行计算方法的流程图；

图2为本发明实施例中的编排过程示意图；

图3为求逆运算过程示意图；以及

图4为本发明实施例中的反编排过程示意图。

具体实施方式

下面结合附图和实施例对本申请作进一步的详细说明。可以理解的是，此处所描述的具体实施例仅用于解释相关发明，而非对该发明的限定。另外还需要说明的是，为了便于描述，附图中仅示出了与有关发明相关的部分。

需要说明的是，在不冲突的情况下，本申请中的实施例及实施例中的特征可以相互组合。下面将参考附图并结合实施例来详细说明本申请。

本发明旨在提供一种基于SIMD指令的SM4的并行计算方法，其包括以下步骤：

步骤S1：对输入的多个分组消息进行编排得到编排后的分组消息。

本发明的方法可以并行处理多组消息，下面以基于128比特的SIMD指令实现为例，展示并行处理4组消息为例展示消息编排过程，参见图2，其中

i＝0，1，2，3均是32比特，4组128比特的消息分别为：

(A₀，A₁，A₂，A₃)，(B₀，B₁，B₂，B₃)，(C₀，C₁，C₂，C₃)，(D₁，D₂，D₃，D₄)；

消息编排之后有4个128比特寄存器分别用来存储编排后的消息，其中4 个寄存器中存储的内容分别是：

(A₀，B₀，C₀，D₀)，(A₁，B₁，C₁，D₁)，(A₂，B₂，C₂，D₂)，(A₃，B₃，C₃，D₃)。

步骤S2：对编排后的分组消息基于SIMD指令使用GF(2⁴)替代GF(2⁸)完成 SM4的Sbox代换计算以实现对轮函数的求逆运算，并获取求逆运算的结果；

其中，基于SIMD指令使用GF(2⁴)替代GF(2⁸)完成SM4的Sbox代换计算过程如下：

Sbox代换计算过程根据256字节的代换表将8比特的输入替换为8比特的输出Sbox(u)：

Sbox(u)＝A(A·u+C)^-1+C

其中，A为8x8的矩阵，C为8x1的矩阵，u表示8bit数，矩阵A和C中的每个元素为GF(2)中的元素：

例如，对于u＝0x7b时的计算过程，u对应的矩阵形式为(1 1 0 1 1 1 1 0)^T，首先执行下面的计算得到v：

矩阵(0 1 1 0 0 1 1 1)^T对应的值为v＝0xe6，GF(2⁸)中v＝0xe6的逆为 v^-1＝0xfe，对应的矩阵形式为(0 1 1 1 1 1 1 1)^T，则Sbox(u)＝A·v^-1+C：

矩阵(1 1 1 0 0 1 1 1)^T对应的值为Sbox(u)＝0xe7，对比SM4标准中的Sbox的定义可以发现计算结果正确；这是GF(2⁴)替代GF(2⁸)数学基础。

定义SM4的Sbox的数学结构为：GF(2⁸)，f(x)＝1+x²+x⁴+x⁵+x⁶+ x⁷+x⁸；

定义有限域为：GF(2⁴)，g(x)＝1+x+x⁴；

定义Sbox的数学结构与有限域的二次代数扩张同构为：

x，y为计算数据对象；

定义同构映射矩阵M和逆同构映射矩阵M^-1的值为：

因此，将v∈GF(2⁸)写成v＝a₀+a₁y，其中，a₀，a₁∈GF(2⁴)，由于v^-1∈ GF(2⁸)，将v^-1表示成v^-1＝b₀+b₁y，b₀，b₁∈GF(2⁴)，则根据(a₀+a₁y)(b₀+ b₁y)＝1有：

即GF(2⁸)内的求逆运算可以在GF(2⁴)²中完成，计算过程为：

对u∈GF(2⁸)进行仿射变换得到

对

同构映射得到

对

进行复合域求逆运算得到

对

进行同构映射得到

对

进行仿射变换得到

其中，w^-1＝Inv(w)表示在GF(2⁴)²中的求逆运算。其中w^-1＝Inv(w)表示在GF(2⁴)²中的求逆运算，该求逆运算根据b₀，b₁的计算公式可以按照图3展示的过程进行，也即GF(2⁸)内的求逆运算转化成了GF(2⁴)上的加法、乘法、平方和求逆运算。

在一个实施例中，对于GF(2⁴)²中的求逆运算中的GF(2⁴)乘法运算过程为：用GF(2⁴)^*表示GF(2⁴)的乘法子群，而g＝0x02∈GF(2⁴)^*为GF(2⁴)^*的生成元，也即所有的e∈GF(2⁴)^*，都存在1≤i≤15，使得e＝gⁱ，为了计算c＝a· b，a，b，c∈GF(2⁴)，先计算log_gc＝log_ga+log_gb，然后计算

其中，log_ga，log_gb可以通过查找包含16个元素的LOG查找表完成。

以上是本发明的方法中关键的优化措施，其是利用SM4分组密码算法Sbox的代数结构将其上的求逆运算转移到与其同构的GF(2⁴)²的运算来完成，基于本发明提出的GF(2⁴)上的优化的乘法运算过程，可以加速SM4分组密码算法Sbox的代换过程.由于SM4分组密码算法密钥编排算法与加解密过程共用相同的Sbox的代换过程，上述的计算过程同样可以应用SM4分组密码算法的密钥编排算法，提高计算速度，这是本发明的重要发明点。

步骤S3：对求逆运算的结果进行反编排计算得到分组消息对应的密文消息；本发明中还将SM4中的反序变换R计算融入消息反编排计算过程，将反序变换R 融入消息反编排过程不会增加额外的运算，有助于提升软件执行速度。

以基于128比特的SIMD指令实现为例，并行处理4组消息为例展示消息反编排过程，参见图4，其中

i＝32,33,34,35.根据消息编排过程，在执行完32次轮函数之后，4个寄存器中存储的内容分别为：

(A₃₂，B₃₂，C₃₂，D₃₂)，(A₃₃，B₃₃，C₃₃，D₃₃)，(A₃₄，B₃₄，C₃₄，D₃₄)，(A₃₅，B₃₅，C₃₅，D₃₅)；

经过融合了注意到反序变换R的消息反编排操作之后，4个寄存器中的存储的内容分别为：

(A₃₅，A₃₄，A₃₃，A₃₂)，(B₃₅，B₃₄，B₃₃，B₃₂)，(C₃₅，C₃₄，C₃₃，C₃₂)，(D₃₅，D₃₄，D₃₃，D₃₂)；

也即对应4组明文消息的密文.注意，利用常见SIMD指令集，融合反序变换R并不会增加额外的运算指令。

GF(2⁴)上的加法运算可以通过比特异或来完成，平方运算和求逆运算可以通过构建运算表格并利用SIMD指令集中常见的shuffle指令来完成.为了实现高效的计算，需要一种快速计算GF(2⁴)上乘法的方法.本发明提出利用GF(2⁴) 上的生成元以及对数表和指数表来快速完成乘法计算的过程，利用SIMD指令集仅需7个指令就可以完成(基于128比特寄存器的SIMD指令集可以用7个指令完成GF(2⁴)上16次乘法，基于256比特寄存器的SIMD指令集可以用7个指令完成GF(2⁴)上32次乘法，基于512比特寄存器的SIMD指令集可以用7个指令完成GF(2⁴)上64次乘法)。

因此，利用线性变换L的特性以及SIMD指令集的特性对轮函数中的线性变换L的计算过程进行调整，其计算过程为：

轮函数中的线性变换L定义为：

将线性变换L等价变换为：

其计算只需要4次比特异或，3次shuffle，1次左移，1次右移，1次比特或共计10个SIMD指令。

本发明的方法中利用线性变换L的特性以及SIMD指令集的特性，调整线性变换L的运算过程，使得可以使用更少的SIMD指令来完成线性变换L，进一步地提高了运算速度，是本发明的重要发明点之一。

本发明提出一种基于SIMD指令的SM4的并行计算装置，其包括处理器和存储器，存储器存储计算机程序，当计算机程序被处理器执行时实现上述任一项的方法。

本发明还提出了一种计算机可读存储介质，计算机可读存储介质存储计算机程序，当计算机程序被处理器执行时实现上述任一项的方法。

本发明为了描述的方便，描述以上装置时以功能分为各种单元分别描述。当然，在实施本申请时可以把各单元的功能在同一个或多个软件和/或硬件中实现。

通过以上的实施方式的描述可知，本领域的技术人员可以清楚地了解到本申请可借助软件加必需的通用硬件平台的方式来实现。基于这样的理解，本申请的技术方案本质上或者说对现有技术做出贡献的部分可以以软件产品的形式体现出来，该计算机软件产品可以存储在存储介质中，如ROM/RAM、磁碟、光盘等，包括若干指令用以使得一台计算机设备，可以是个人计算机，服务器，或者网络设备等，执行本申请各个实施例或者实施例的某些部分的装置。

最后所应说明的是：以上实施例仅以说明而非限制本发明的技术方案，尽管参照上述实施例对本发明进行了详细说明，本领域的普通技术人员应当理解：依然可以对本发明进行修改或者等同替换，而不脱离本发明的精神和范围的任何修改或局部替换，其均应涵盖在本发明的权利要求范围当中。

Claims (5)

1.一种基于SIMD指令的SM4的并行计算方法，其特征在于，其包括以下步骤：

步骤S1：对输入的多个分组消息进行编排得到编排后的分组消息；

均是32比特,4组128比特的消息分别为：(A₀,A₁,A₂,A₃),(B₀,B₁,B₂,B₃),(C₀,C₁,C₂,C₃),(D₁,D₂,D₃,D₄)；

消息编排之后有4个128比特寄存器分别用来存储编排后的消息,其中4个寄存器中存储的内容分别是:

(A₀,B₀,C₀,D₀),(A₁,B₁,C₁,D₁),(A₂,B₂,C₂,D₂),(A₃,B₃,C₃,D₃)；

步骤S2：对所述编排后的分组消息基于SIMD指令使用GF(2⁴)替代GF(2⁸)完成SM4的Sbox代换计算以实现对轮函数的求逆运算，并获取求逆运算的结果；

所述基于SIMD指令使用GF(2⁴)替代GF(2⁸)完成SM4的Sbox代换计算过程如下：

所述Sbox代换计算过程根据256字节的代换表将8比特的输入替换为8比特的输出Sbox(u)：

Sbox(u)＝A(A·u+C)^-1+C

其中，A为8x8的矩阵，C为8x1的矩阵,u表示8bit数，矩阵A和C中的每个元素为GF(2)中的元素:

定义SM4的Sbox的数学结构为：GF(2⁸),f(x)＝1+x²+x⁴+x⁵+x⁶+x⁷+x⁸；

定义有限域为：GF(2⁴),g(x)＝1+x+x⁴；

定义Sbox的数学结构与有限域的二次代数扩张同构为：

h(y)＝9+y+y²；

定义同构映射矩阵M和逆同构映射矩阵M^-1的值为:

因此，将v∈GF(2⁸)写成v＝a₀+a₁y,其中a₀,a₁∈GF(2⁴),由于v^-1∈GF(2⁸),将v^-1表示成v^-1＝b₀+b₁y,b₀,b₁∈GF(2⁴),则根据(a₀+a₁y)(b₀+b₁y)＝1有:

即GF(2⁸)内的求逆运算可以在GF(2⁴)²中完成,计算过程为：

对u∈GF(2⁸)进行仿射变换得到

对

同构映射得到

对

进行复合域求逆运算得到

对

进行同构映射得到

对

进行仿射变换得到

其中，u是GF(2⁸)中的元素，u经过仿射变换得到GF(2⁸)中的元素v，对v进行同构映射得到GF(2⁴)²中的元素w，之后对w进行复合域求逆运算得到GF(2⁴)²中的元素w^-1,再对w^-1进行同构映射得到GF(2⁸)中的元素s，最后对s进行仿射变换，得到GF(2⁸)中的元素t，w^-1＝Inv(w)表示在GF(2⁴)²中的求逆运算；

对于GF(2⁴)²中的求逆运算中的GF(2⁴)乘法运算过程为：用GF(2⁴)^*表示GF(2⁴)的乘法子群,而g＝0x02∈GF(2⁴)^*为GF(2⁴)^*的生成元,也即所有的e∈GF(2⁴)^*,都存在1≤i≤15,使得e＝gⁱ，为了计算c＝a·b,a,b,c∈GF(2⁴),先计算log_g c＝log_g a+log_g b，然后计算

其中，log_g a,log_g b可以通过查找包含16个元素的LOG查找表完成；

GF(2⁴)上的加法运算通过比特异或来完成,平方运算和求逆运算可以通过构建运算表格并利用SIMD指令集中常见的shuffle指令来完成；利用GF(2⁴)上的生成元以及对数表和指数表来快速完成乘法计算的过程,利用SIMD指令集仅需7个指令就能完成；

步骤S3：对所述求逆运算的结果进行反编排计算得到所述分组消息对应的密文消息。

2.根据权利要求1所述的基于SIMD指令的SM4的并行计算方法，其特征在于，利用线性变换L的特性以及SIMD指令集的特性对轮函数中的线性变换L的计算过程进行调整，其计算过程为：

轮函数中的线性变换L定义为:

将线性变换L等价变换为:

其计算只需要4次比特异或,3次shuffle,1次左移,1次右移,1次比特或，共计10个SIMD指令。

3.根据权利要求1-2任一项所述的基于SIMD指令的SM4的并行计算方法，其特征在于，将SM4中的反序变换R计算融入消息反编排计算过程。

4.一种基于SIMD指令的SM4的并行计算方法的并行计算装置，其特征在于，其包括处理器和存储器，所述存储器存储计算机程序，当所述计算机程序被处理器执行时实现权利要求1-3任一项的方法。

5.一种计算机可读存储介质，其特征在于，所述计算机可读存储介质存储计算机程序，当所述计算机程序被处理器执行时实现权利要求1-3任一项的基于SIMD指令的SM4的并行计算方法。

Images