ISSN 
下载:
-
自从Shor算法[1]提出以来，利用量子技术对现代密码算法的分析便受到研究者们的关注。在对称密码算法的分析中，文献[2]首先分析了量子技术对对称密码算法的影响，如Grover算法[3]可以平方加速密钥搜索速度，建议把密钥长度至少增加一倍以达到非量子环境下的安全强度。文献[4]利用Simon算法[5]可以快速寻找碰撞周期的特性分析对称密码系统的安全性，大幅提升了查询效率。随后，结合Grover算法和Simon算法对具有不同结构或不同加密方式的对称密码算法分析方案被提出[6-8]。
这些安全分析大多需要对对称密码算法量子电路实现的资源进行评估，因此对称密码算法的量子电路实现近几年也得到了大量关注。此外，量子逻辑门都是可逆的，使用量子电路实现的密码算法在执行过程中不会有能量的耗散，因此可以抵抗各种和能量分析相关的侧信道分析攻击[9]，这是对称密码算法量子电路实现受到关注的另一原因。
在现有的对称密码算法量子电路实现方案中，S盒作为密码组件的非线性结构，一直是研究的重点。 文献[10]首先对AES密码算法中综合S盒所需的量子电路资源用两种方案进行了评估：方案一主要采用Itoh-Tsujii算法[11]进行评估，一共需要使用40个量子比特，3584个T门和4569个Clifford门；方案二主要使用稳定子链技术[12]进行评估，一共使用9个量子比特，不超过9695个T门和12631个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门。 本文主要通过把
${\rm{GF}}({2^8})$ 中的运算同构到${\rm{ GF}}({({2^4})^2})$ 中，使用NOT门、CNOT门和Toffoli门构建实现S盒的量子电路。所使用的量子比特，量子门的数量，量子电路的深度等量子资源相比于文献[19]都有较大的减少。 -
SM4密码算法的加解密过程可以参看文献[20]，这里不再赘述。S盒是SM4密码算法中唯一的非线性变换，是保证算法安全性的关键组件，通常由256个元素构成的查询表进行描述。文献[21]研究了S盒的代数结构，并给出了具体表达式：
$$ S({\boldsymbol{\alpha }}) = {A_2} \cdot I \cdot {A_1}\left( {\boldsymbol{\alpha}} \right)\;\;\;\;\forall {\boldsymbol{\alpha}} \in {\rm{GF}}({2^8}) $$ (1) 式中，
$ I $ 是${\rm{GF}}({2^8})$ 上的乘法逆元，所用到的不可约多项式为：$$ f(x) = {x^8} + {x^7} + {x^6} + {x^5} + {x^4} + {x^2} + 1{\text{ }} $$ (2) $ {A_1} $ 和$ {A_2} $ 是如下的仿射变换：$$ {A_1} = {A_2} = {\boldsymbol{\alpha}} \cdot {\boldsymbol{F}} + {\boldsymbol{\nu}} $$ (3) 式中，
${\boldsymbol{F }}$ 是${\rm{GF}}(2)$ 上$ 8 \times 8 $ 的矩阵，具体值如下：$$ {\boldsymbol{F}} = \left( {\begin{array}{*{20}{c}} {\begin{array}{*{20}{c}} 1&1 \\ 1&1\\ \end{array}}&{\begin{array}{*{20}{c}} 1&0 \\ 1&1 \end{array}}&{\begin{array}{*{20}{c}} 0&1 \\ 0&0 \end{array}}&{\begin{array}{*{20}{c}} 0&1 \\ 1&0 \end{array}} \\ {\begin{array}{*{20}{c}} 0&1 \\ 1&0\\ \end{array}}&{\begin{array}{*{20}{c}} 1&1 \\ 1&1 \end{array}}&{\begin{array}{*{20}{c}} 1&0 \\ 1&1 \end{array}}&{\begin{array}{*{20}{c}} 0&1 \\ 0&0 \end{array}} \\ {\begin{array}{*{20}{c}} 0&1 \\ 0&0 \end{array}}&{\begin{array}{*{20}{c}} 0&1 \\ 1&0 \end{array}}&{\begin{array}{*{20}{c}} 1&1 \\ 1&1 \\ \end{array}}&{\begin{array}{*{20}{c}} 1&0 \\ 1&1 \end{array}} \\ {\begin{array}{*{20}{c}} 1&0 \\ 1&1 \end{array}}&{\begin{array}{*{20}{c}} 0&1 \\ 0&0 \end{array}}&{\begin{array}{*{20}{c}} 0&1 \\ 1&0 \end{array}}&{\begin{array}{*{20}{c}} 1&1 \\ 1&1 \end{array}} \end{array}} \right){\text{ }} $$ (4) $ {\boldsymbol{\nu}} $ 是${\rm{GF}}(2)$ 上的向量，${\boldsymbol{v}}{\text{ = }}\left( {1,1,0,0,1,0,1,1} \right)$ 。 -
S盒事实上是一个8量子比特的逻辑函数，8量子比特的逻辑函数一共有
$ {2}^{8}！ $ 个。对于任意给定的8量子比特的逻辑函数，目前还没有有效的算法对其综合。在式(1)中，仿射变换式(3)可以通过高斯消元法先综合出矩阵${\boldsymbol{F}}$ ，再通过在对应位置添加NOT门的方式综合出${\boldsymbol{\nu}}$ 的方式完成。接下来主要是综合出${\rm{GF}}({2^8})$ 上的乘法逆元运算${\boldsymbol{I}}$ ，虽然它可以看成是由对换构成的置换，但依然没有有效的综合算法。本文策略是将${\rm{ GF}}({2^8})$ 上的求逆运算同构到${\rm{GF}}({({2^4})^2})$ 上的运算。当然，对于${\rm{GF}}({2^4})$ 上的运算可以进一步同构到${\rm{GF}}({({2^2})^2})$ 中的运算，从而将${\rm{GF}}({2^8})$ 中的求逆运算同构到${\rm{GF}}({({({2^2})^2})^2})$ 中的运算。但在${\rm{GF}}({({2^2})^2})$ 上实现${\rm{GF}}({2^4})$ 上的求逆等运算时不得不添加更多的辅助量子比特。另外，对于大多数4量子比特逻辑函数，可以采用双向综合[22]等方法实现。因此，只需将${\rm{GF}}({2^8})$ 上的求逆运算同构到${\rm{ GF}}({({2^4})^2})$ 上的运算。实现S盒的整体框架如图1所示。
图 1 SM4密码算法S盒复合域实现框架图
-
由文献[21]可知，SM4密码算法求逆运算用到的不可约多项式为式(2)中的
$ f(x) $ ，即运算中用到的有限域${{{{\rm{GF}}}}}({2^8}) \cong {\rm{GF}}(2)[x]/(f(x))$ 。因为同构关系，所以当给定$ n $ 次不可约多项式$ g(x) $ 时，文中不再区分${\rm{ GF}}({2^n})$ 和${\rm{GF}}(2)[x]/(g(x))$ 。设$ X $ 为$ f(x) $ 的一个根，对于$\forall {\boldsymbol{\alpha}} \in {\rm{GF}}({2^8})$ 有：$$ {\boldsymbol{\alpha}} = \sum\limits_{i = 0}^7 {{\alpha _i}{X^i}} \;\;\;\;{\alpha _i} \in {\rm{GF}}(2) $$ (5) 同理，取不可约多项式
$ p(y) = {y^2} + \mu y + \lambda $ ，其中$\mu ,\lambda \in {\rm{GF}}({2^4})$ ，设$Y$ 是$ p(y) $ 的一个根，则对于$\forall {\boldsymbol{r}} \in {\rm{GF}}({({2^4})^2})$ 有：$$ {\boldsymbol{r}} = {r_1}Y + {r_0} {\text{ }}{r_1},{r_0} \in {\rm{GF}}({2^4}) $$ (6) 对于任意元素
${\boldsymbol{ r }}\in{\rm{ GF}}({({2^4})^2})$ ，求得其逆元为：$$ \begin{split} {{\boldsymbol{r}}^{ - 1}} =&{r_1}{(r_0^2 + {r_0}{r_1}\mu + r_1^2\lambda )^{ - 1}}Y+ \\& ({r_0} + \mu {r_1}){(r_0^2 + {r_0}{r_1}\mu + r_1^2\lambda )^{ - 1}} \\ \end{split} $$ (7) 为了计算简便，取
$ \mu {\text{ = }}1 $ ，则不可约多项式$ p(y) = {y^2} + y + \lambda $ ，式(7)变为：$$ \begin{split} {{\boldsymbol{r}}^{ - 1}} = &{r_1}{(r_0^2 + {r_0}{r_1} + r_1^2\lambda )^{ - 1}}Y+ \\& ({r_0} + {r_1}){(r_0^2 + {r_0}{r_1} + r_1^2\lambda )^{ - 1}} \\ \end{split} $$ (8) 从式(8)可知，为了求
${{\boldsymbol{r}}^{ - 1}}$ ，需要在${\rm{GF}}({2^4})$ 中进行运算，因此需要在${\rm{GF}}({2^4})$ 中选取一个不可约多项式。考虑到这些运算的执行效率，在3个4次不可约多项式中选取$ q(z) = {z^4} + z + 1 $ 。设$ Z $ 是$ q(z) $ 的一个根，则对于$\forall {\boldsymbol{a}} \in {\rm{GF}}({2^4})$ 有：$$ {\boldsymbol{a}} = \sum\limits_{i = 0}^3 {{a_i}{Z^i}} \;\;\;\;{a_i} \in {\rm{GF}}(2) $$ (9) -
由图1所示，为了实现SM4密码算法的S盒，需要分别实现
${\rm{GF}}({({2^4})^2})$ 中的求逆运算，同构映射$ \delta $ 和同构映射$ {\delta ^{ - 1}} $ ，以及仿射变换$ {A_1} $ 和$ {A_2} $ 。下面分别描述它们的量子电路，文中的量子电路主要使用python语言并利用qiskit软件包实现。 -
从式(8)可知，为了求
${{\boldsymbol{r}}^{ - 1}}$ ，需要在${\rm{GF}}({2^4})$ 做加法、平方、乘法和求逆运算。加法运算可以直接通过在对应位置添加CNOT门完成，这里不再讨论。下面先讨论平方运算。因为有限域${\rm{GF}}({2^4})$ 的特征为2，所以，对于任意元素${\boldsymbol{a}} =\displaystyle{ \sum\limits_{i{\text{ = }}0}^3} {{a_i}{Z^i}} \in {\rm{GF}}({2^4})$ 有：$$ {{\boldsymbol{a}}^2}{\text{ = }}{\left( {\sum\limits_{i = 0}^3 {{a_i}{x^i}} } \right)^2}{\text{ = }}\sum\limits_{i = 0}^3 {{a_i}{x^{2i}}} $$ (10) 因此，对于
$\forall {\boldsymbol{a}} \in {\rm{GF}}({2^4})$ ，可以找到如下的矩阵${\boldsymbol{S}}$ 使得${{\boldsymbol{a}}^2} = {\boldsymbol{S }}\cdot {\boldsymbol{a}}$ ，其中，$$ {\boldsymbol{S}} = \left( {\begin{array}{*{20}{c}} 1&0&1&0 \\ 0&0&1&0 \\ 0&1&0&1 \\ 0&0&0&1 \end{array}} \right) $$ (11) 利用高斯消元法，可以实现其量子电路如图2所示。
图 2 实现式(10)平方计算的量子电路图
对于乘法计算，由文献[23]定理1可以得出：对于
$\forall {\boldsymbol{a}},{\boldsymbol{b}}{\boldsymbol{}} \in {\rm{GF}}({2^4})$ ，记${\boldsymbol{c}} = {\boldsymbol{a}} \cdot {\boldsymbol{b}}$ ，有：$$ {\boldsymbol{c}} = {\boldsymbol{d}} + {{\boldsymbol{Q}}^{\rm{T}}} \cdot {\boldsymbol{e}} $$ (12) 其中，
$$ {\boldsymbol{d}} = \left( {\begin{array}{*{20}{c}} {{d_0}} \\ {{d_1}} \\ {{d_2}} \\ {{d_3}} \end{array}} \right) = {\boldsymbol{L}} \cdot {\boldsymbol{b}} = \left( {\begin{array}{*{20}{c}} {{a_0}}&0&0&0 \\ {{a_1}}&{{a_0}}&0&0 \\ {{a_2}}&{{a_1}}&{{a_0}}&0 \\ {{a_3}}&{{a_2}}&{{a_1}}&{{a_0}} \end{array}} \right) \cdot \left( {\begin{array}{*{20}{c}} {{b_0}} \\ {{b_1}} \\ {{b_2}} \\ {{b_3}} \end{array}} \right) $$ (13) $$ {\boldsymbol{e}} = \left( {\begin{array}{*{20}{c}} {{e_0}} \\ {{e_1}} \\ {{e_2}} \\ {{e_3}} \end{array}} \right) = {\boldsymbol{U}} \cdot {\boldsymbol{b}} = \left( {\begin{array}{*{20}{c}} 0&{{a_3}}&{\begin{array}{*{20}{c}} {{a_2}}&{{a_1}} \end{array}} \\ 0&0&{\begin{array}{*{20}{c}} {{a_3}}&{{a_2}} \end{array}} \\ 0&0&{\begin{array}{*{20}{c}} 0&{{a_3}} \end{array}} \end{array}} \right) \cdot \left( {\begin{array}{*{20}{c}} {{b_0}} \\ {{b_1}} \\ {{b_2}} \\ {{b_3}} \end{array}} \right) $$ (14) 式中，
$ {a_i} $ 和$ {b_i} $ 分别是${\boldsymbol{ a}}$ 和${\boldsymbol{ b}}$ 和对应位置上的元素，可以计算出：$$ {{\boldsymbol{Q}}^{\rm{T}}} = \left( {\begin{array}{*{20}{c}} 1&0&0&0 \\ 1&1&0&0 \\ 0&1&1&0 \\ 0&0&1&0 \end{array}} \right) $$ (15) 于是，可以实现
${\boldsymbol{a}}$ 和${\boldsymbol{b}}$ 乘积的量子电路如图3所示。
图 3 式(12)中乘法计算的量子电路图
对于乘法求逆运算，首先将其表示成如下置换：
$$ (2,9)(3,14)(4,13)(5,11)(6,7)(8,15)(10,12) $$ (16) 显然，这是由7个对换构成的奇置换。但4量子比特中的NOT门，CNOT门和Toffoli门全都是偶置换，这意味着仅使用NCT库中的逻辑门综合出的4量子比特量子电路不能实现
${\rm{GF}}({2^4})$ 中的求逆运算。本文策略是添加一个辅助量子比特，先综合出一个奇置换。这里先用两个Toffoli门，借助辅助量子比特综合出置换$ (14,15) $ ，然后使用文献[22]中的双向综合算法实现出求逆运算的量子电路如图4所示。图中$ {a_4} $ 是辅助量子比特。
图 4 实现乘法求逆运算的量子电路图
有了这些基本量子电路图，便可以非常容易地实现式(8)中
${\rm{GF}}({({2^4})^2})$ 内的求逆运算。 -
在讨论同构映射
$ \delta $ 和$ {\delta ^{ - 1}} $ 的量子电路之前，先讨论它们的构造。事实上，${\rm{ GF}}({2^8})$ 中含有与${\rm{ GF}}({2^4})$ 同构的子域，也含有${\rm{GF}}({({2^4})^2})$ 同构的子域，可以把$ Y $ 和$ Z $ 用${\rm{GF}}({2^8})$ 中的元素表示，则${\rm{GF}}({({2^4})^2})$ 的基也可以用${\rm{ GF}}({2^8})$ 中的元素表示，于是有：$$ {\delta ^{ - 1}}{\text{ = }}[1,Z,{Z^2},{Z^3},Y,YZ,Y{Z^2},Y{Z^3}] $$ (17) 由
$ {({\delta ^{ - 1}})^{ - 1}} = \delta $ 可以求出同构映射$ \delta $ 。接下来，讨论同构映射的选取。
${\rm{GF}}({({2^4})^2})$ 中，形如$ p(y) = {y^2} + y + \lambda $ 的不可约多项式共有8个，每个多项式都有2个根。$ q(z) $ 共有4个根。因此，一共有64组同构映射。为了在实现同构映射时尽可能少地使用量子门，选取元素“1”的个数最少的一组。经计算，这64组中$ \delta $ 和$ {\delta ^{ - 1}} $ 最少共有44个“1”。此时，$ Y{\text{ = 0xC5}} $ ，$ {\text{Z = 0x50}} $ ，$ \lambda {\text{ = 0xF}} $ 。同构映射为：$$ \delta = \left( {\begin{array}{*{20}{c}} {\begin{array}{*{20}{c}} 1&0 \\ 0&1 \\ \end{array}}&{\begin{array}{*{20}{c}} 1&0 \\ 0&0 \end{array}}&{\begin{array}{*{20}{c}} 0&0 \\ 1&0 \end{array}}&{\begin{array}{*{20}{c}} 0&0 \\ 0&0 \end{array}} \\ {\begin{array}{*{20}{c}} 0&0 \\ 0&0 \\ \end{array}}&{\begin{array}{*{20}{c}} 1&0 \\ 0&0 \end{array}}&{\begin{array}{*{20}{c}} 0&0 \\ 1&1 \end{array}}&{\begin{array}{*{20}{c}} 0&1 \\ 1&1 \end{array}} \\ {\begin{array}{*{20}{c}} 0&0 \\ 0&1 \\ \end{array}}&{\begin{array}{*{20}{c}} 0&0 \\ 0&0 \end{array}}&{\begin{array}{*{20}{c}} 0&0 \\ 0&1 \end{array}}&{\begin{array}{*{20}{c}} 0&1 \\ 0&0 \end{array}} \\ {\begin{array}{*{20}{c}} 0&0 \\ 0&1 \end{array}}&{\begin{array}{*{20}{c}} 0&0 \\ 1&1 \end{array}}&{\begin{array}{*{20}{c}} 1&0 \\ 1&0 \end{array}}&{\begin{array}{*{20}{c}} 1&1 \\ 1&0 \end{array}} \end{array}} \right){\text{ }} $$ (18) $$ {\delta ^{ - 1}} = \left( {\begin{array}{*{20}{c}} {\begin{array}{*{20}{c}} 1&0 \\ 0&0 \end{array}}&{\begin{array}{*{20}{c}} 1&0 \\ 0&1 \end{array}}&{\begin{array}{*{20}{c}} 1&0 \\ 0&1 \\ \end{array}}&{\begin{array}{*{20}{c}} 0&0 \\ 1&0 \end{array}} \\ {\begin{array}{*{20}{c}} 0&0 \\ 0&0 \end{array}}&{\begin{array}{*{20}{c}} 1&0 \\ 1&1 \end{array}}&{\begin{array}{*{20}{c}} 1&0 \\ 0&1 \\ \end{array}}&{\begin{array}{*{20}{c}} 0&0 \\ 0&1 \end{array}} \\ {\begin{array}{*{20}{c}} 0&1 \\ 0&0 \end{array}}&{\begin{array}{*{20}{c}} 0&1 \\ 0&1 \end{array}}&{\begin{array}{*{20}{c}} 0&1 \\ 0&0 \\ \end{array}}&{\begin{array}{*{20}{c}} 1&0 \\ 1&0 \end{array}} \\ {\begin{array}{*{20}{c}} 0&1 \\ 0&0 \end{array}}&{\begin{array}{*{20}{c}} 0&1 \\ 0&0 \end{array}}&{\begin{array}{*{20}{c}} 1&1 \\ 1&0 \end{array}}&{\begin{array}{*{20}{c}} 0&0 \\ 0&0 \end{array}} \end{array}} \right){\text{ }} $$ (19) 利用高斯消元法可以综合出
$ \delta $ 和$ {\delta ^{ - 1}} $ 的量子电路分别如图5和图6所示。
图 5 同构映射
$ \delta $ 的量子电路图
图 6 同构映射
$ {\delta ^{ - 1}} $ 的量子电路图当
$ \lambda {\text{ = 0xF}} $ 时，对于$\forall {\boldsymbol{a}} \in {\rm{GF}}({2^4})$ ，计算$\lambda \cdot {\boldsymbol{a}}$ 的值等价于计算矩阵${\boldsymbol{\lambda}}$ 乘以${\boldsymbol{ a}}$ 的值，其中，$$ {\boldsymbol{\lambda }} = \left( {\begin{array}{*{20}{c}} 1&1&1&1 \\ 1&0&0&0 \\ 1&1&0&0 \\ 1&1&1&0 \end{array}} \right) $$ (20) 其量子电路如图7所示。
图 7 乘以常数
$ \lambda $ 的量子电路 -
仿射变换式(3)中
${\boldsymbol{ F}}$ 和${\boldsymbol{\nu}}$ 的值都已经给出，所以可以综合出其量子电路如图8所示。
图 8 式(3)中仿射变换的量子电路图
-
为了描述方便，记
$ S $ 为图2中实现平方计算的电路图，图3中实现乘法计算量子电路的乘数分别记为两个实心圆点，结果记为$ M $ 。$ I $ 为图4中求逆运算的量子电路图，图5和图6中实现同构映射的电路图分别记为$ \delta $ 和$ {\delta ^{ - 1}} $ ，图7中的量子电路记为$ \lambda $ ，$ {A_1} $ 和$ {A_2} $ 为图8中仿射变换的量子电路图。此外，为了尽可能少地使用辅助量子比特，需要把一些寄存器还原，此时只需逆序添加原来的量子电路即可，图2的逆电路记为$ {S^{ - 1}} $ ，图7的逆电路记为$ {\lambda ^{ - 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每一位上的值都为$ \left| 0 \right\rangle $ 。经过该电路图运算后，寄存器c输出S盒输出的低4位，d输出S盒输出的高4位。通过IBM量子平台的Aer模拟器验证，该量子电路图是完全正确的。
图 9 S盒的量子电路示意图
图 10 SM4密码算法S盒的具体量子电路图
-
文中的量子电路是通过NOT门、CNOT门和Toffoli门实现的。通过计算S盒量子电路的比特数和所使用的量子门的数量刻画电路的复杂度。在S盒实现的量子电路中，a,b,c,d都是4量子比特寄存器，e是5量子比特寄存器，所有一共使用了21量子比特。现在计算量子门的数量，仿射变换
$ {A_1} $ 和$ {A_2} $ 其实是一样的，它们的电路图都使用了35个CNOT门，和5个NOT门；同构映射$ \delta $ 的电路图共使用了23个CNOT门；$ {\delta ^{ - 1}} $ 的电路图共使用19个CNOT门；平方计算$ S $ 的电路图和它的逆电路图都使用了5个CNOT门，它们在S盒的量子电路图中都使用了2次；乘以常数$ \lambda $ 的量子电路和它的逆电路都使用了9个CNOT门；乘法计算的量子电路共使用了16个Toffoli门和3个CNOT门，S盒的量子电路图中共使用了3次乘法计算；乘法逆运算的电路图共使用了7个Toffoli门和5个CNOT门；此外还使用了3组共12个CNOT门做量子比特的复制。最终本文实现整个S盒所使用的量子资源，和文献[19]使用量子资源的对比情况如表1所示。由表1可以看出，实现SM4密码算法S盒文献[19]需要使用30个量子比特，82个Toffoli门，510个CNOT门和87个NOT门。采用本文提出的方法只需要使用21个量子比特，55个Toffoli门，176个CNOT门和10个NOT门。此外，还计算出本文中实现的SM4算法S盒量子电路的深度为151。由此可以看出：本文实现的方法的效率在文献[19]的基础上有显著提高。
-
本文采用NOT门、CNOT门和Toffoli门实现SM4密码算法S盒的量子电路图。根据S盒的代数结构，首先将
${\rm{GF}}({2^8})$ 中的求逆运算同构到${\rm{ GF}} ({({2^4})^2})$ 求逆，其次根据${\rm{GF}}({({2^4})^2})$ 中求逆运算的表达式分别给出了${\rm{ GF}}({2^4})$ 中平方计算、乘法计算和求逆运算的量子电路，再次根据最小化基转换矩阵中“1”元素个数的原则求出了基转化矩阵的量子电路，然后利用高斯消元法给出了仿射变换的量子电路，最后综合出SM4密码算法S盒的量子电路。整个量子电路一共使用了21个量子比特，55个Toffoli门，176个CNOT门和10个NOT门。和现有方法相比，所使用的量子资源进一步减少，效率进一步提高。
Quantum Circuit Implementation of S-box for SM4 Cryptographic Algorithm Based on Composite Field Arithmetic
-
摘要: S盒是SM4分组密码算法中重要的非线性组件。使用Toffoli门、CNOT门和NOT门构建S盒的量子电路。首先，基于S盒的代数表达式，通过同构映射矩阵，将有限域
${\rm{GF}}({2^8})$ 中的求逆运算转化到有限域${\rm{ GF}}({({2^4})^2})$ 中的运算；其次，在${\rm{ GF}}({2^4})$ 中分别给出了平方计算、乘法计算和求逆运算的量子电路；再次，通过最小化同构矩阵中“1”元素的个数，求出最优的同构映射矩阵，并给出相应的量子电路；然后，通过高斯消元法给出S盒表达式中仿射变换的量子电路；最后，综合出SM4密码算法S盒的量子电路。该量子电路的正确性通过IBM量子平台的Aer模拟器进行了验证。复杂度分析表明：所给出S盒的量子电路一共使用了21个量子比特，55个Toffoli门、176个CNOT门和10个NOT门，电路深度为151。相比于已有结果，所使用的量子资源进一步减少，效率进一步提高。Abstract: The S-box is an important nonlinear component in SM4 block cipher algorithm. In this paper, Toffoli gates, CNOT gates and NOT gates are used to construct the quantum circuit of the S-box. Based on the algebraic expression of the S-box, the inverse operation in finite field${\rm{GF}}({2^8})$ is transformed into operations in finite field${\rm{GF}}({({2^4})^2})$ through isomorphic mapping matrices. The quantum circuits of square calculation, multiplication calculation and inversion operation in${\rm{ GF}}({2^4})$ are given respectively. By minimizing the number of "1" elements in the isomorphic matrices, the optimal isomorphic mapping matrices are obtained, and the corresponding quantum circuits are given. Then, the quantum circuit of affine transformation in S-box expression is given by Gaussian elimination method; Finally, the quantum circuit of S-box in SM4 cryptographic algorithm is synthesized. The correctness of the quantum circuit is verified by the Aer simulator of IBM quantum platform. The complexity analysis shows that the given quantum circuit of the S-box uses 21 qubits, 55 Toffoli gates, 176 CNOT gates and 10 NOT gates, and the circuit depth is 151. Compared with the existing results, the quantum resources used are further reduced and the efficiency is further improved.-
Key words:
- algebraic operation /
- composite field /
- quantum circuit /
- S box /
- SM4
-
[1] PETER W. Shor polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer[J]. SIAM J Comput, 1997, 26(5): 1484-1509. doi: 10.1137/S0097539795293172 [2] YAMAMURA A, ISHIZUKA H. Quantum cryptanalysis of block ciphers (Algebraic systems, formal languages and computations)[J]. RIMS Kokyuroku, 2000(1166): 235-243. [3] GROVER L K. A fast quantum mechanical algorithm for database search[C]//Proc of the 28th Annual ACM Symposium on Theory of Computing (STOC). [S.l.]: ACM, 1996: 212-219. [4] KAPLAN M, LEURENT G, LEVERRIER A, et al. Breaking symmetric cryptosystems using quantum period finding[C]//Annual International Cryptology Conference. Berlin, Heidelberg: Springer, 2016: 207-237. [5] SIMON D. On the power of quantum computation[C]//Proceedings of the 35th IEEE Symposium on the Foundations of Computer Science (FOCS). [S.l.]: IEEE, 1994: 116-123. [6] LEANDER G, MAY A. Grover meets Simon-quantumly attacking the FX-construction[C]//International Conference on the Theory and Application of Cryptology and Information Security. Cham: Springer, 2017: 161-178. [7] DONG X Y, WANG X Y. Quantum key-recovery attack on feistel structures[J]. Science China Information Sciences, 2018, 61(10): 1-7. [8] SAMIR H, LARS R K. A quantum distinguisher for 7/8-round SMS4 block cipher[J]. Quantum Information Processing, 2020, 19(11): 1-22. [9] SARAVANAN P, KALPANA P. Novel reversible design of advanced encryption standard cryptographic algorithm for wireless sensor networks[J]. Wireless Personal Communications, 2018, 100(4): 1427-1458. doi: 10.1007/s11277-018-5647-z [10] GRASSL M. LANGENBERG B. ROETTELER M. et al. Applying grover’s algorithm to AES: Quantum resource estimates[EB/OL]. (2015-12-15). https://arxiv.org/abs/1512.04965. [11] ITOH T, TSUJII S. A fast algorithm for computing multiplicative inverses in GF (2m) using normal bases[J]. Information and Computation, 1988, 78(3): 171-177. doi: 10.1016/0890-5401(88)90024-7 [12] EGNER S, PUSCHEL M. Solving puzzles related to permutations groups[C]//Proc International Symposium on Symbolic and Algebraic Computation (ISSAC’98). [S.l.]: ACM, 1998: 186-193. [13] ALMAZROOIE M, SAMSUDIN A, ABDULLAH R, et al. Quantum reversible circuit of AES-128[J]. Quantum Information Processing, 2018, 17(5): 1-30. [14] LANGENBERG B, PHAM H, STEINWANDT R. Reducing the cost of implementing the advanced encryption standard as a quantum circuit[J]. IEEE Transactions on Quantum Engineering, 2020(1): 1-12. [15] ZOU J, LIU Y, DONG C. et al. Observations on the quantum circuit of the SBox of AES[EB/OL]. (2019-10-24).https://eprint.iacr.org/2019/1245. [16] 国家密码管理局. 国家密码管理局关于发布无线局域网产品密码事宜公告[EB/OL]. (2006-01-06). https//sca. gov. cn/sca/xwdt/2006-01/06/content_1002355. shtml. State Cryptography Administration. Announcement of the state cryptography administration on issuing ciphers for WLAN products[EB/OL]. (2006-01-06). https//sca. gov. cn/sca/xwdt/2006-01/06/content_1002355. shtml. [17] 国家密码管理局. 我国SM4分组密码算法正式成为ISO/IEC国际标准[EB/OL]. (2021-07-08). https//www.oscca.gov.cn/sca/xwdt/2021-07/08/content_1060866.shtml. State Cryptography Administration. China's SM4 block cipher algorithm has officially become an ISO/IEC international standard[EB/OL]. (2021-07-08). https//www.oscca.gov.cn/sca/xwdt/2021-07/08/content_1060866.shtml. [18] 罗庆斌, 李晓瑜, 杨国武. SM4密码算法S盒的量子电路实现[J]. 电子科技大学学报, 2021, 50(6): 820-826. LUO Q B, LI X Y, YANG G W. Quantum circuit implementation of S-box for SM4 cryptographic algorithm[J]. Journal of University of Electronic Science and Technology of China, 2021, 50(6): 820-826. [19] 林达, 向泽军, 张若琳, 等. SM4算法的量子实现[J]. 密码学报, 2021, 8(6): 999-1018. doi: 10.13868/j.cnki.jcr.000493 LIN D, XIANG Z J, ZHANG R L, et al. Quantum implementation of SM4[J]. Journal of Cryptologic Research, 2021, 8(6): 999-1018. doi: 10.13868/j.cnki.jcr.000493 [20] 中国标准化委员会. GB/T 32907-2016 信息安全技术SM4分组密码算法[S]. 北京: 中国质检出版社, 2016. China Standardization Commission. GB/T 32907-2016 information security technology: SM4 block cipher algorithm[S]. Beijing: China Quality Inspection Press, 2016. [21] LIU F, JI W, HU L, et al. Analysis of the SMS4 block cipher[C]//Information Security and Privacy. Berlin, Heidelberg: Springer, 2007: 158-170. [22] YANG G, SONG X, HUNG W, et al. Bi-directional synthesis of 4-bit reversible circuits[J]. The Computer Journal, 2008, 51(2): 207-215. [23] REYHANI-MASOLEH A, HASAN M A. Low complexity bit parallel architectures for polynomial basis multiplication over GF (2m)[J]. IEEE Transactions on Computers, 2004, 53(8): 945-959. doi: 10.1109/TC.2004.47 -
点击查看大图
图(10) / 表(1)
计量
- 文章访问数: 5071
- HTML全文浏览量: 1457
- PDF下载量: 102
- 被引次数: 0
