基于复合域SM4 密码算法S 盒的量子电路实现

罗庆斌，李晓瑜，杨国武，牛伟纳，李 强

(1. 湖北民族大学智能科学与工程学院 湖北 恩施 445000；2. 电子科技大学信息与软件工程学院 成都 610054；3. 电子科技大学计算机科学与工程学院 成都 611731)

自从Shor 算法[1]提出以来，利用量子技术对现代密码算法的分析便受到研究者们的关注。在对称密码算法的分析中，文献[2]首先分析了量子技术对对称密码算法的影响，如Grover 算法[3]可以平方加速密钥搜索速度，建议把密钥长度至少增加一倍以达到非量子环境下的安全强度。文献[4]利用Simon 算法[5]可以快速寻找碰撞周期的特性分析对称密码系统的安全性，大幅提升了查询效率。随后，结合Grover 算法和Simon 算法对具有不同结构或不同加密方式的对称密码算法分析方案被提出[6-8]。

这些安全分析大多需要对对称密码算法量子电路实现的资源进行评估，因此对称密码算法的量子电路实现近几年也得到了大量关注。此外，量子逻辑门都是可逆的，使用量子电路实现的密码算法在执行过程中不会有能量的耗散，因此可以抵抗各种和能量分析相关的侧信道分析攻击[9]，这是对称密码算法量子电路实现受到关注的另一原因。

在现有的对称密码算法量子电路实现方案中，S 盒作为密码组件的非线性结构，一直是研究的重点。 文献[10]首先对AES 密码算法中综合S 盒所需的量子电路资源用两种方案进行了评估：方案一主要采用Itoh-Tsujii 算法[11]进行评估，一共需要使用40 个量子比特，3 584 个T 门和4 569个Clifford 门；方案二主要使用稳定子链技术[12]进行评估，一共使用9 个量子比特，不超过9 695个T 门和12 631 个Clifford 门。但这两种方案中只评估了实现S 盒时所需的量子资源，并没有给出具体的量子线路。文献[13]主要使用Itoh-Tsujii 算法[11]具体实现了AES 密码算法S 盒的量子电路，一共使用了56 个量子比特，448 个Toffoli 门，494 个CNOT 门和4 个NOT 门。通过优化AES 密码算法S 盒中每个输出的布尔表达式，文献[14]给出的量子电路一共使用了32 个量子比特，55 个Toffoli 门，314 个CNOT 门和4 个NOT 门。通过对S 盒中输出布尔表达式的进一步优化，文献[15]设计的AES 密码算法S 盒的量子电路一共使用26 个量子比特，46 个Toffoli 门，304 个CNOT 门和4 个NOT 门。

本文主要研究SM4 密码算法S 盒的量子电路实现。SM4 密码算法是用于WAPI 的分组密码算法，2006 年由我国国家密码管理局公开发布[16]，2021 年6 月发布成为国际标准[17](标准号为 ISO/IEC 18033-3：2010/AMD1：2021)。目前对于SM4密码算法量子电路实现的研究较少。文献[18]实现了SM4 密码算法的S 盒，一共使用了48 个量子比特，592 个量子门，电路深度为289。文献[19]实现的SM4 密码算法的S 盒中添加了14 个辅助量子比特，加上输入和输出的量子比特，一共需要30 个量子比特，82 个Toffoli 门，510 个CNOT 门和87 个X 门。X 门和NOT 门是等价的，所以本文中不区分X 门和NOT 门。 本文主要通过把GF(28)中 的运算同构到 GF((24)2)中，使用NOT 门、CNOT 门和Toffoli 门构建实现S 盒的量子电路。所使用的量子比特，量子门的数量，量子电路的深度等量子资源相比于文献[19]都有较大的减少。

1 SM4 密码算法的S 盒

1.1 S 盒的代数结构

SM4 密码算法的加解密过程可以参看文献[20]，这里不再赘述。S 盒是SM4 密码算法中唯一的非线性变换，是保证算法安全性的关键组件，通常由256 个元素构成的查询表进行描述。文献[21]研究了S 盒的代数结构，并给出了具体表达式：

ν是 G F(2)上 的向量，v= (1,1,0,0,1,0,1,1)。

1.2 S 盒的分解

S 盒事实上是一个8 量子比特的逻辑函数，8 量子比特的逻辑函数一共有 28！个。对于任意给定的8 量子比特的逻辑函数，目前还没有有效的算法对其综合。在式(1)中，仿射变换式(3)可以通过高斯消元法先综合出矩阵F，再通过在对应位置添加NOT 门的方式综合出ν 的方式完成。接下来主要是综合出 GF(28) 上 的乘法逆元运算I，虽然它可以看成是由对换构成的置换，但依然没有有效的综合算法。本文策略是将 GF(28)上的求逆运算同构到GF((24)2)上 的运算。当然，对于 GF(24)上的运算可以进一步同构到 GF((22)2)中的运算，从而将GF(28)中 的求逆运算同构到 GF(((22)2)2)中的运算。但在 GF((22)2)上 实现 GF(24)上的求逆等运算时不得不添加更多的辅助量子比特。另外，对于大多数4 量子比特逻辑函数，可以采用双向综合[22]等方法实现。因此，只需将 GF(28)上的求逆运算同构到GF((24)2)上的运算。实现S 盒的整体框架如图1所示。

图1 SM4 密码算法S 盒复合域实现框架图

2 复合域中的运算

由文献[21]可知，SM4 密码算法求逆运算用到的不可约多项式为式(2)中的f(x)，即运算中用到的有限域 GF(28)≅GF(2)[x]/(f(x))。因为同构关系，所以当给定n次不可约多项式g(x)时，文中不再区 分 GF(2n) 和 GF(2)[x]/(g(x)) 。 设X为f(x)的 一 个根，对于∀ α ∈GF(28)有：

同理，取不可约多项式p(y)=y2+µy+λ，其中µ,λ ∈GF(24) ， 设Y是p(y)的 一 个 根，则 对 于∀r∈GF((24)2)有：

为了计算简便，取 µ=1，则不可约多项式p(y)=y2+y+λ，式(7)变为：

从式(8)可知，为了求r-1， 需要在 G F(24)中进行运算，因此需要在 G F(24)中选取一个不可约多项式。考虑到这些运算的执行效率，在3 个4 次不可约多项式中选取q(z)=z4+z+1。 设Z是q(z)的一个根，则对于∀a∈GF(24)有：

3 基本组件的量子电路

由图1 所示，为了实现SM4 密码算法的S 盒，需要分别实现 GF((24)2)中的求逆运算，同构映射δ和同构映射 δ-1， 以及仿射变换A1和A2。下面分别描述它们的量子电路，文中的量子电路主要使用python 语言并利用qiskit 软件包实现。

3.1 G F((24)2)求逆的基本量子电路

因此，对于 ∀a∈GF(24)，可以找到如下的矩阵S使得a2=S·a，其中，

利用高斯消元法，可以实现其量子电路如图2所示。

图2 实现式(10)平方计算的量子电路图

式中，ai和bi分 别是a和b和对应位置上的元素，可以计算出：

于是，可以实现a和b乘积的量子电路如图3所示。

图3 式(12)中乘法计算的量子电路图

对于乘法求逆运算，首先将其表示成如下置换：

显然，这是由7 个对换构成的奇置换。但4 量子比特中的NOT 门，CNOT 门和Toffoli 门全都是偶置换，这意味着仅使用NCT 库中的逻辑门综合出的4 量子比特量子电路不能实现 G F(24)中的求逆运算。本文策略是添加一个辅助量子比特，先综合出一个奇置换。这里先用两个Toffoli 门，借助辅助量子比特综合出置换 (14,15)，然后使用文献[22]中的双向综合算法实现出求逆运算的量子电路如图4 所示。图中a4是辅助量子比特。

有了这些基本量子电路图，便可以非常容易地实现式(8)中G F((24)2)内的求逆运算。

3.2 同构映射的量子电路图

在讨论同构映射 δ和 δ-1的量子电路之前，先讨论它们的构造。事实上， GF(28) 中 含有与 GF(24)同构的子域，也含有 GF((24)2)同构的子域，可以把Y和Z用 G F(28) 中 的元素表示，则 G F((24)2)的基也可以用G F(28)中的元素表示，于是有：

由(δ-1)-1=δ 可 以求出同构映射δ。

接下来，讨论同构映射的选取。 GF((24)2)中，形如p(y)=y2+y+λ的不可约多项式共有8 个，每个多项式都有2 个根。q(z)共有4 个根。因此，一共有64 组同构映射。为了在实现同构映射时尽可能少地使用量子门，选取元素“1”的个数最少的一组。经计算，这64 组中 δ和 δ-1最少共有44 个“1”。此时，Y=0xC5， Z=0x50 ， λ=0xF。同构映射为：

利用高斯消元法可以综合出 δ 和 δ-1的量子电路分别如图5 和图6 所示。

图5 同构映射δ 的量子电路图

图6 同构映射 δ-1的量子电路图

当 λ=0xF时 ，对于 ∀a∈GF(24) ， 计算 λ·a的值等价于计算矩阵λ 乘以a的值，其中，

其量子电路如图7 所示。

图7 乘以常数λ 的量子电路

3.3 仿射变换的量子电路图

仿射变换式(3)中F和ν 的值都已经给出，所以可以综合出其量子电路如图8 所示。

图8 式(3)中仿射变换的量子电路图

4 S 盒的量子电路图

4.1 量子电路图

为了描述方便，记S为图2 中实现平方计算的电路图，图3 中实现乘法计算量子电路的乘数分别记为两个实心圆点，结果记为M。I为图4 中求逆运算的量子电路图，图5 和图6 中实现同构映射的电 路图分别记 为 δ 和 δ-1，图7 中的量子 电 路 记为λ，A1和A2为图8 中仿射变换的量子电路图。此外，为了尽可能少地使用辅助量子比特，需要把一些寄存器还原，此时只需逆序添加原来的量子电路即可，图2 的逆电路记为S-1，图7 的逆电路记为λ-1。根据图1 和式(8)可以得出SM4 密码算法的量子电路逻辑图如图9 所示，具体的量子电路图如图10 所示。图9 中a,b,c,d都是4 量子比特寄存器，e是5 量子比特寄存器。除了求逆操作需要用到寄存器e的第5 位外，其他操作都只用到前面的4 位。初始化时，寄存器a的值为S 盒输入的低4 位，b为S 盒输入的高4 位，c,d,e每一位上的值都为 |0〉。经过该电路图运算后，寄存器c输出S 盒输出的低4 位，d输出S 盒输出的高4 位。通过IBM 量子平台的Aer 模拟器验证，该量子电路图是完全正确的。

图9 S 盒的量子电路示意图

图10 SM4 密码算法S 盒的具体量子电路图

4.2 量子电路复杂度分析

文中的量子电路是通过NOT 门、CNOT 门和Toffoli 门实现的。通过计算S 盒量子电路的比特数和所使用的量子门的数量刻画电路的复杂度。在S 盒实现的量子电路中，a,b,c,d都是4 量子比特寄存器，e是5 量子比特寄存器，所有一共使用了21 量子比特。现在计算量子门的数量，仿射变换A1和A2其实是一样的，它们的电路图都使用了35 个CNOT 门，和5 个NOT 门；同构映射 δ的电路图共使用了23 个CNOT 门； δ-1的电路图共使用19 个CNOT 门；平方计算S的电路图和它的逆电路图都使用了5 个CNOT 门，它们在S 盒的量子电路图中都使用了2 次；乘以常数 λ的量子电路和它的逆电路都使用了9 个CNOT 门；乘法计算的量子电路共使用了16 个Toffoli 门和3 个CNOT门，S 盒的量子电路图中共使用了3 次乘法计算；乘法逆运算的电路图共使用了7 个Toffoli 门和5个CNOT 门；此外还使用了3 组共12 个CNOT 门做量子比特的复制。最终本文实现整个S 盒所使用的量子资源，和文献[19]使用量子资源的对比情况如表1 所示。

表1 文献[19]与本文综合S 盒所用量子资源对比表 个

由表1 可以看出，实现SM4 密码算法S 盒文献[19]需要使用30 个量子比特，82 个Toffoli门，510 个CNOT 门和87 个NOT 门。采用本文提出的方法只需要使用21 个量子比特，55 个Toffoli 门，176 个CNOT 门和10 个NOT 门。此外，还计算出本文中实现的SM4 算法S 盒量子电路的深度为151。由此可以看出：本文实现的方法的效率在文献[19]的基础上有显著提高。

5 结 束 语

本文采用NOT 门、CNOT 门和Toffoli 门实现SM4 密码算法S 盒的量子电路图。根据S 盒的代数结构，首先将 GF(28) 中 的求逆运算同构到GF((24)2)求 逆，其次根据 GF((24)2)中求逆运算的表达式分别给出了 G F(24)中平方计算、乘法计算和求逆运算的量子电路，再次根据最小化基转换矩阵中“1”元素个数的原则求出了基转化矩阵的量子电路，然后利用高斯消元法给出了仿射变换的量子电路，最后综合出SM4 密码算法S 盒的量子电路。整个量子电路一共使用了21 个量子比特，55 个Toffoli 门，176 个CNOT 门和10 个NOT 门。和现有方法相比，所使用的量子资源进一步减少，效率进一步提高。