ISSN 
下载:
-
量子计算极大地改变了现代密码系统的安全性。对于非对称密码系统，Shor算法[1]能快速破解基于大整数分解的密码算法[2]和基于离散对数的密码算法[3]。量子计算对于对称密码系统的影响虽然没有像非对称密码系统那样显著，但最近也得到大量关注。文献[4]首先分析了Grover算法[5]对对称密码系统的量子威胁，建议把原来的密钥长度至少增加一倍。文献[6]利用Simon算法[7]寻找碰撞周期以攻击对称密码系统，一些在经典环境中需要
${{\Omega}} ({2^{n/2}})$ 次查询的密码算法在该量子环境下只需要$ O(n) $ 次查询。文献[8]结合Grover算法和Simon算法对具有FX结构的对称密码在量子环境下的安全性进行了分析。文献[9]结合Grover算法和Simon算法对具有Feistel结构的对称密码算法提出了量子密钥恢复攻击。文献[10]通过在量子环境下利用Demirci-Selçuk中间人攻击和提高解S盒差分方程的效率分析了AES密码算法在量子环境下的安全性。文献[11]利用Grover算法和Simon算法为SM4密码算法构造了一个8轮的量子区分器。这些对称密码在量子环境下的安全性分析基本是建立在它们已经可以用量子电路实现的假设上的。但是目前针对对称密码算法的量子电路实现研究较少，且基本是对AES密码算法的量子电路实现[12-13]，其他对称密码算法量子电路实现的研究几乎没有。
SM4算法是用于WAPI的分组密码算法，2006年由我国国家密码管理局公开发布[14]，2012年3月发布成为国家密码行业标准[15](标准号为 GM/T 0002-2012)，2016年8月发布成为国家标准[16](标准号为 GB/T 32907-2016)，2021年6月发布成为国际标准[17](标准号为 ISO/IEC 18033-3：2010/AMD1：2021)。SM4算法的安全性自发布以来，得到了广泛的关注。在这些安全性分析中，SM4算法中唯一的非线性变换S盒起着关键性的作用。文献[18]分析了SM4算法中最小活跃S盒个数与抵抗差分攻击轮数之间的关系。文献[19-20]分别提出了基于掩码的S盒实现方案和基于门限理论的S盒的实现方案，以提高SM4密码算法的安全性。
本文主要通过SM4密码算法S盒的代数结构，使用NOT门、CNOT门和Toffoli门构建实现S盒的量子电路。
-
SM4算法是分组密码算法，其数据分组长度和密钥分组长度都为128 bit。加密算法与解密算法都以字节(8位)和字(32位)为单位进行数据处理。
-
加密算法采用32轮迭代结构，每轮使用一个轮密钥。
设输入明文为
$\left( {{\boldsymbol{X}_0},{\boldsymbol{X}_1},{\boldsymbol{X}_2},{\boldsymbol{X}_3}} \right) \in {( {{\rm{GF}}( {{2^{32}}} )} )^4}$ ，输出的密文为$( {{\boldsymbol{Y}_0},{\boldsymbol{Y}_1},{\boldsymbol{Y}_2},{\boldsymbol{Y}_3}} ) \in {( {{\rm{GF}}( {{2^{32}}} )} )^4}$ ，${\bf{r}}{{\bf{k}}_i} \in {\rm{GF}}( {{2^{32}}} ) $ $ (i = 0,1,2, \cdots ,31)$ 为轮密钥。加密算法可描述如下：$$\begin{split}& \;\;{\boldsymbol{X}_{i + 4}} = F({\boldsymbol{X}_i},{\boldsymbol{X}_{i + 1}},{\boldsymbol{X}_{i + 2}},{\boldsymbol{X}_{i + 3}},{\bf{r}}{{\bf{k}}_i})=\\ &\;\;\;\; {\boldsymbol{X}_i} \oplus T({\boldsymbol{X}_{i + 1}} \oplus {\boldsymbol{X}_{i + 2}} \oplus {\boldsymbol{X}_{i + 3}} \oplus {\bf{r}}{{\bf{k}}_i}) \end{split}$$ (1) 式中，
$i = 0,1,2, \cdots ,31$ ，则有：$$\begin{split}& ({\boldsymbol{Y}_0}{\rm{, }}{\boldsymbol{Y}_1}{\rm{, }}{\boldsymbol{Y}_2}{\rm{, }}{\boldsymbol{Y}_3}) = ({\boldsymbol{X}_{35}}{\rm{, }}{\boldsymbol{X}_{34}}{\rm{, }}{\boldsymbol{X}_{33}}{\rm{, }}{\boldsymbol{X}_{32}})= \\ & \;\;\;\;\;\;\;\;\;\;\;\;\;R({\boldsymbol{X}_{32}}{\rm{, }}{\boldsymbol{X}_{33}}{\rm{, }}{\boldsymbol{X}_{34}}{\rm{, }}{\boldsymbol{X}_{35}}) \end{split}$$ (2) 式中，F是轮函数，变换
$T:{\rm{GF}}( {{2^{32}}} ) \to {\rm{GF}}( {{2^{32}}})$ 由非线性变换$ \tau $ 和线性变换L构成，即：$$ T( \cdot ) = L(\tau ( \cdot )) $$ (3) 变换
$ \tau $ 由4个8 bit的非线性变换S盒并行构成。设$\boldsymbol{A} = \left( {{\boldsymbol{\alpha }_0},{\boldsymbol{\alpha}_1},{\boldsymbol{\alpha}_2},{\boldsymbol{\alpha}_3}} \right) \in {( {{\rm{GF}}( {{2^8}} )} )^4}$ 是非线性变换$ \tau $ 的输入，$\boldsymbol{B} = \left( {{\boldsymbol{\beta }_0},{\boldsymbol{\beta}_1},{\boldsymbol{\beta}_2},{\boldsymbol{\beta}_3}} \right) \in {( {{\rm{GF}}( {{2^8}} )} )^4}$ 是输出，则变换$ \tau $ 定义如下：$$\begin{split}& \;\;\;\;\;\;\;\;\;\;\;\boldsymbol{B} = ({\boldsymbol{\beta}_0},{\boldsymbol{\beta}_1},{\boldsymbol{\beta}_2},{\boldsymbol{\beta}_3}) = \tau (\boldsymbol{A})=\\ & ({\rm{Sbox}}({\boldsymbol{\alpha}_0}),{\rm{Sbox}}({\boldsymbol{\alpha}_1}),{\rm{Sbox}}({\boldsymbol{\alpha}_2}),{\rm{Sbox}}({\boldsymbol{\alpha}_3})) \end{split}$$ (4) 式中，
$ {\rm{Sbox}}( \cdot ) $ 为以字节为单位的非线性替换。S盒的替换表可以参考文献[18]，将在第2章介绍它的代数结构。变换
$ \tau $ 的输出$ \boldsymbol{B} $ 将作为线性变换L的输入。设$\boldsymbol{C} \in {\rm{GF}}( {{2^{32}}} )$ 是$ L $ 的输出。则线性变换L定义为：$$\begin{split}& \boldsymbol{C} = L(\boldsymbol{B}) = \boldsymbol{B} \oplus (\boldsymbol{B} < < < 2) \oplus (\boldsymbol{B} < < < 10)\oplus\\ &\;\;\;\;\;\;\;\;\;\; (\boldsymbol{B} < < < 18) \oplus (\boldsymbol{B} < < < 24) \end{split}$$ (5) 式中，
$ < < < i $ 表示把32位字循环左移$ i $ 位。SM4密码算法的加密过程如图1所示。由于解密算法和加密算法采用相同的变换结构和过程，只是反序使用轮密钥，这里不再赘述。
图 1 SM4分组密码算法加密过程
-
轮密钥由128 bit密钥通过密钥扩展算法生成。设
${\bf{MK}} = \left( {{\bf{M}}{{\bf{K}}_0},{\bf{M}}{{\bf{K}}_1},{\bf{M}}{{\bf{K}}_2},{\bf{M}}{{\bf{K}}_3}} \right) \in {( {{\rm{GF}}( {{2^{32}}} )} )^4}$ 为输入密钥，${\bf{r}}{{\bf{k}}_i} \in {\rm{GF}}( {{2^{32}}} )(i = 0,1,2, \cdots ,31)$ 为输出的轮密钥，${\boldsymbol{K}_i} \in {\rm{GF}}( {{2^{32}}} )(i = 0,1,2, \cdots ,35)$ 为中间数据，密钥扩展算法描述如下：$$\begin{split}& ({\boldsymbol{K}_0},{\boldsymbol{K}_1},{\boldsymbol{K}_2},{\boldsymbol{K}_3}) = ({\bf{M}}{{\bf{K}}_0} \oplus {\bf{F}}{{\bf{K}}_{0{\rm{ }}}},{\rm{ }}{\bf{M}}{{\bf{K}}_1} \oplus {\bf{F}}{{\bf{K}}_1},{\rm{ }}\\ &\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;{\bf{M}}{{\bf{K}}_2} \oplus {\bf{F}}{{\bf{K}}_2},{\rm{ }}{\bf{M}}{{\bf{K}}_3} \oplus {\bf{F}}{{\bf{K}}_3}) \end{split}$$ (6) 以及
$$\begin{split}& \;\;\;\;\; \;\;\;\;\;\;\;\;\;\;\;\;\; {\bf{r}}{{\bf{k}}_i} = {\boldsymbol{K}_{i + 4}}= \\ & {\boldsymbol{K}_i} \oplus T'({\boldsymbol{K}_{i + 1}} \oplus {\boldsymbol{K}_{i + 2}} \oplus {\boldsymbol{K}_{i + 3}} \oplus {\bf{C}}{{\bf{K}}_i}) \end{split}$$ (7) 式中，
${\bf{F}}{{\bf{K}}_i}(i = 0,1,2,3)$ 是系统参数；${\bf{C}}{{\bf{K}}_i}(i = 0,1,2, \cdots ,31)$ 是固定参数；$ T'( \cdot ) $ 是和加密算法中变换$ T( \cdot ) $ 非常类似的变换。变换
$T' $ 和变换 T 唯一不同的地方是把 T 中的线性变换 L 替换成如下的线性变换$L' $ ：$$L'(\boldsymbol{B}) = \boldsymbol{B} \oplus (\boldsymbol{B} < < < 13) \oplus (\boldsymbol{B} < < < 23)$$ (8) 系统参数
${\bf{F}}{{\bf{K}}_i}$ 的十六进制表示如下所示：$$\begin{split}& {\bf{F}}{{\bf{K}}_0} = {\rm{0xA3B1BAC6}}\\ &{\bf{F}}{{\bf{K}}_1} = {\rm{0x56AA3350}}\\ &{\bf{F}}{{\bf{K}}_2} = {\rm{0x677D9197}}\\ &{\bf{F}}{{\bf{K}}_3} = {\rm{0xB27022DC}} \end{split}$$ (9) 固定参数
${\bf{C}}{{\bf{K}}_i} = \left( {{\rm{c}}{{\rm{k}}_{i,0}},{\rm{c}}{{\rm{k}}_{i,1}},{\rm{c}}{{\rm{k}}_{i,2}},{\rm{c}}{{\rm{k}}_{i,3}}} \right) \in {( {{\rm{GF}}( {{2^8}} )} )^4}$ 采用如下的方式计算：$${\rm{c}}{{\rm{k}}_{i,j}} = (4 i + j) \times 7({\rm{mod}} \,256)$$ (10) 式中，
$i = 0,1,2, \cdots ,31$ ；$ j = 0,1,2,3 $ 。 -
在SM4密码算法中，S盒是唯一的非线性变换，是保证安全的关键组件。S盒通常由256个元素构成的查询表描述。文献[21]研究了S盒的代数结构，并给出了如下的具体表达式：
$${\rm{Sbox}}({\boldsymbol{a}}) = A_2 \cdot I \cdot A_1(\boldsymbol{a})\;\;\forall \boldsymbol{a} \in {\rm{GF}}({2^8})$$ (11) 式中， I 是
$ {\rm{GF}}({2^8}) $ 上的乘法逆元，这里的不可约多项式为：$$ f(x) = {x^8} + {x^7} + {x^6} + {x^5} + {x^4} + {x^2} + 1{\text{ }} $$ (12) A1和A2是如下的仿射变换：
$$A_1(\boldsymbol{a}) =A_2(\boldsymbol{a})= {\boldsymbol{F}^{\rm{T}}} \cdot \boldsymbol{a} \oplus \boldsymbol{v}$$ (13) 式中，
$$ \boldsymbol{F} = \left( {\begin{array}{*{20}{c}} {\begin{array}{*{20}{c}} 1&1&1&0&0&1&0&1 \\ 1&1&1&1&0&0&1&0\\ 0&1&1&1&1&0&0&1\\ 1&0&1&1&1&1&0&0\\ 0&1&0&1&1&1&1&0\\ 0&0&1&0&1&1&1&1\\ 1&0&0&1&0&1&0&1\\ 1&1&0&0&1&0&1&1 \end{array}} \end{array}} \right){\text{ }} $$ (14) 是
${\rm{GF}}(2)$ 上$ 8 \times 8 $ 的矩阵；$\boldsymbol{v} = {\left( {1,1,0,0,1,0,1,1} \right)^{\rm{T}}}$ 是常数列向量。 -
用量子电路实现S盒，实际上就是实现式(11)。在式(11)中仿射变换的表达式已经由式(13)给出，可以用类似高斯消元的方式实现矩阵FT，即通过行变换把矩阵FT化成单位阵，每做一次行变换便在对应量子电路中添加一个CNOT门，反序排列这些CNOT门，便构造出了矩阵FT的量子电路。对于列向量
$ \boldsymbol{v} $ ，在出现“1”的对应位置添加NOT门便可实现。乘法逆元I会相对复杂。文献[22]证明了
$ {\rm{GF}}({2^n}) $ 上的任一非零元素${\boldsymbol{a }}$ 的逆元可以表示成${(\boldsymbol{a})^{ - 1}}{\rm{ = (}}\boldsymbol{a}{{\rm{)}}^{{2^n} - 2}}$ 。因此需要计算：$$I(\boldsymbol{a}) = {\boldsymbol{a}^{254}}$$ (15) 为了快速计算式(15)，需要分别实现
$ {\rm{GF}}(2)[x]/ $ $ (f(x)) $ 上的平方计算和乘法计算。$ {\rm{GF}}(2)[x] $ 上的平方计算具有线性的性质，即对元素$\boldsymbol{a}{\rm{ = }}\displaystyle\sum\limits_{i = 0}^{n - 1} {{a_i}{x^i}}$ 有：$${\boldsymbol{a}^2}{\rm{ = }}{\left( {\sum\limits_{i = 0}^{n - 1} {{a_i}{x^i}} } \right)^2}{\rm{ = }}\sum\limits_{i = 0}^{n - 1} {{a_i}{x^{2i}}} $$ (16) 因此，可以得出：
$\forall \boldsymbol{a} \in {\rm{GF}}(2)[x]/(f(x))$ ，有${\boldsymbol{a}^2} = {\bf{Sq}} \cdot \boldsymbol{a}$ ，其中：$$ {\bf{Sq}} = \left( {\begin{array}{*{20}{c}} 1&0&0&0&1&0&0&0 \\ 0&0&0&0&0&1&0&1\\ 0&1&0&0&1&1&0&0\\ 0&0&0&0&0&1&1&1\\ 0&0&1&0&1&1&1&0\\ 0&0&0&0&1&1&1&0\\ 0&0&0&1&1&0&1&0\\ 0&0&0&0&1&0&1&0 \end{array}} \right){\text{ }} $$ (17) 对于乘法计算，文献[23]得出如下结论：
$\forall \boldsymbol{a},\boldsymbol{b} \in {\rm{GF}}(2)[x]/(f(x))$ ，记$\boldsymbol{c} = \boldsymbol{a} \cdot \boldsymbol{b}$ ，有：$$\boldsymbol{c} = \boldsymbol{d} + {\boldsymbol{Q}^{\rm{T}}} \cdot \boldsymbol{e}$$ (18) 其中，
$$ \boldsymbol{d} = \left( {\begin{array}{*{20}{c}} {{d_0}} \\ {{d_1}} \\ \vdots \\ {{d_{n - 1}}} \end{array}} \right) = \boldsymbol{L} \cdot \boldsymbol{b} = \left( {\begin{array}{*{20}{c}} {{a_0}}&0& \cdots &0 \\ {{a_1}}&{{a_0}}& \cdots &0 \\ \vdots & \vdots & \ddots & \vdots \\ {{a_{n - 1}}}&{{a_{n - 2}}}& \cdots &{{a_0}} \end{array}} \right) \cdot \left( {\begin{array}{*{20}{c}} {{b_0}} \\ {{b_1}} \\ \vdots \\ {{b_{n - 1}}} \end{array}} \right) $$ (19) $$\begin{split}& \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\boldsymbol{e} = \left( {\begin{array}{*{20}{c}} {{e_0}} \\ {{e_1}} \\ \vdots \\ {{e_{n - 1}}} \end{array}} \right) = \boldsymbol{U} \cdot \boldsymbol{b} = \\ &\left( {\begin{array}{*{20}{c}} 0&{{a_{n - 1}}}&{{a_{n - 2}}}& \cdots &{{a_1}} \\ 0&0&{{a_{n - 1}}}& \cdots &{{a_2}} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0&0&0& \cdots &{{a_{n - 1}}} \end{array}} \right) \cdot \left( {\begin{array}{*{20}{c}} {{b_0}} \\ {{b_1}} \\ \vdots \\ {{b_{n - 1}}} \end{array}} \right) \end{split}$$ (20) 式中，
$ {a_i} $ 是$ \boldsymbol{a} $ 对应位置上的元素；$ {\boldsymbol{Q}^{\text{T}}} $ 表示矩阵$ \boldsymbol{Q} $ 的转置，其中$ \boldsymbol{Q} $ 是使得$$ \left( {\begin{array}{*{20}{c}} {{x^n}} \\ {{x^{n + 1}}} \\ \vdots \\ {{x^{2n - 2}}} \end{array}} \right) \equiv \boldsymbol{Q} \cdot \left( {\begin{array}{*{20}{c}} 1 \\ x \\ \vdots \\ {{x^{n - 1}}} \end{array}} \right)({\rm{mod}}\;f(x)) $$ (21) 成立的二元矩阵，于是可以计算出：
$$ {\boldsymbol{Q}^{\text{T}}} = \left( {\begin{array}{*{20}{c}} 1&1&0&0&0&1&0 \\ 0&1&1&0&0&0&1 \\ 1&1&1&1&0&1&0 \\ 0&1&1&1&1&0&1 \\ 1&1&1&1&1&0&0 \\ 1&0&1&1&1&0&0 \\ 1&0&0&1&1&0&0 \\ 1&0&0&0&1&0&0 \end{array}} \right) $$ (22) -
本文使用Python语言并利用qiskit软件包实现所求的量子电路。对于式(13)中仿射变换的表达式，使用高斯消元法实现矩阵FT，并通过在对应位置添加NOT的方法实现向量
$ \boldsymbol{v} $ ，最终式(13)中仿射变换的量子电路如图2所示。$ {\rm{GF}}({2^8}) $ 上的平方计算可以通过式(17)的线性变换表示，利用高斯消元法实现平方计算的量子电路如图3所示。式(19)和式(20)中的$ \boldsymbol{d} $ 和$ \boldsymbol{e} $ 可以通过Toffoli门实现，式(22)中的矩阵$ {\boldsymbol{Q}^{\text{T}}} $ 可以通过高斯消元法实现，因此式(18)便可以实现，量子电路如图4所示。
图 2 实现式(13)仿射变换的量子电路图
图 3 实现式(17)平方计算的量子电路图
为了更快速地计算
$I(\boldsymbol{a}) = {\boldsymbol{a}^{254}}$ ，本文采用Itoh-Tsujii算法[24]，但为了尽可能少地使用辅助量子比特，把计算顺序调整如下：1)
$ {(\boldsymbol{a})^2} = {\boldsymbol{a}^2} $ 2)
$ \boldsymbol{a} \cdot {\boldsymbol{a}^2} = {\boldsymbol{a}^3} $ 3)
$ {({\boldsymbol{a}^3})^{{2^2}}} = {\boldsymbol{a}^{12}} $ 4)
$ {\boldsymbol{a}^2} \cdot {\boldsymbol{a}^{12}} = {\boldsymbol{a}^{14}} $ 5)
${\boldsymbol{a}} \cdot {\boldsymbol{a}^{14}} = {\boldsymbol{a}^{15}}$ 6)
$ {({\boldsymbol{a}^{15}})^{{2^4}}} = {\boldsymbol{a}^{240}} $ 7)
$ {\boldsymbol{a}^{14}} \cdot {\boldsymbol{a}^{240}} = {\boldsymbol{a}^{254}} $ 由于仿射变换和平方计算的量子电路都为8量子比特，乘法计算量子电路为24量子比特，为了更加方便地表示S盒的量子电路，本文以8量子比特为单位描述S盒的量子电路。记A1和A2为图2中实现仿射变换的量子电路；Sq为图3中实现平方计算的量子电路；图4中实现乘法计算量子电路的乘数输入分别记为两个实心圆点，乘积结果记为M。主要根据计算
$ {\boldsymbol{a}^{254}} $ 的步骤，可以得出S盒的量子电路如图5所示。
图 4 实现式(18)乘法计算的量子电路图
图 5 S盒的量子电路示意图
-
这里的量子电路是利用NCT门库实现，即采用NOT门、CNOT门和Toffoli门实现。通过这些量子电路所用量子比特的数量、量子门的数量和量子电路的深度描述构建的量子电路的复杂度如表1所示。
表 1 量子电路所用量子资源情况表
变换方式 量子比特数 量子门数 电路深度 仿射变换 8 39 23 平方计算 8 22 16 乘法计算 24 88 39 S盒 48 592 289 由图5可知，最终S盒的实现电路中需要2次调用仿射变换的量子电路，每个仿射变换的量子电路由34个CNOT门和5个NOT门构成，电路深度为23；需要7次调用平方计算的量子电路，每个平方计算的量子电路由22个CNOT门构成，电路深度为16；需要4次调用乘法计算的量子电路，每个乘法计算的量子电路由64个Toffoli门和24个CNOT门构成，电路深度为39；此外还需要用1组(8个)CNOT门对量子比特进行复制。整个S盒的量子电路中一共使用了48个量子比特，592个量子门，电路深度为289。由于本文是首次实现SM4密码算法S盒的量子电路，不能通过对比的方式来分析该电路的复杂度。但文献[12]实现了AES密码算法S盒的量子电路，在该量子电路中，共使用了3组(24个)CNOT门对量子比特进行复制，使用的量子比特数为56。由此可以看出，本文实现的SM4算法S盒的量子电路还是比较高效的。
-
本文首次给出了SM4密码算法S盒的量子电路。根据S盒的代数结构，首先给出S盒代数表达式中仿射变换的量子电路，然后把代数表达式中求
${\rm{GF}}({2^8})$ 下元素的逆元转换为求该元素的254次方，为此，分别构建了$ {\rm{GF}}({2^8}) $ 中平方计算的量子电路和乘法计算的量子电路，再通过改进的Itoh-Tsujii算法给出S盒的量子电路。所构建的S盒的量子电路共使用了48个量子比特，592个量子门，电路深度为289。本文的研究将对量子环境下SM4密码算法的研究产生积极影响。
Quantum Circuit Implementation of S-box for SM4 Cryptographic Algorithm
-
摘要: SM4密码算法是我国国家密码管理局2006年公开发布的用于WAPI的分组密码算法，2021年6月成为国际标准。S盒作为唯一的非线性组件，其安全性直接影响到SM4算法的安全性。该文首次给出SM4密码算法S盒的量子电路实现。根据S盒的代数表达式，首先利用高斯消元法给出表达式中仿射变换的量子电路，然后把求逆元运算转换为求该元素的254次方，再分别给出对应的平方计算和乘法计算的量子电路，最后通过改进的Itoh-Tsujii算法给出S盒的量子电路。量子电路的复杂度分析表明：所给出的S盒的量子电路共用48个量子比特，592个量子门，电路深度为289，具有较高的效率。该研究将会对量子环境下SM4密码算法的安全性分析奠定基础。Abstract: SM4 cryptographic algorithm is a block cipher algorithm for WAPI published by China's state cryptography administration in 2006. It was published as an international standard in June 2021. As the only nonlinear component, the security of S-box directly affects the security of SM4 algorithm. In this paper, the quantum circuit implementation of S-box for SM4 cryptographic algorithm is given for the first time. According to the algebraic expression of S-box, firstly, the affine transformation quantum circuit is given by Gaussian elimination method, then the inverse element operation is converted to the 254 power of the corresponding element, and then the corresponding quantum circuits for square calculation and multiplication calculation are given respectively. Finally, the quantum circuit of S-box is given by using improved Itoh-Tsujii algorithm. The complexity analysis shows that the given S-box quantum circuit uses 48 qubits, 592 quantum gates and the circuit depth is 289, which has high efficiency. The research of this paper will lay a foundation for the security analysis of SM4 cryptographic algorithm in quantum environment.
-
Key words:
- algebraic operation /
- 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] RIVEST R L, SHAMIR A, ADLEMAN L. A method for obtaining digital signatures and public-key cryptosystems[J]. Commun ACM, 1978, 21(2): 120-126. doi: 10.1145/359340.359342 [3] ELGAMAL T. A public-key cryptosystem and a signature scheme based on discrete logarithms[J]. IEEE Trans Inf Theory, 1985, 31(4): 469-472. doi: 10.1109/TIT.1985.1057074 [4] YAMAMURA A, ISHIZUKA H. Quantum cryptanalysis of block ciphers (Algebraic systems, formal languages and computations)[J]. RIMS Kokyuroku, 2000(1166): 235-243. [5] 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. [6] 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. [7] 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. [8] 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. [9] DONG X Y, WANG X Y. Quantum key-recovery attack on feistel structures[J]. Science China Information Sciences, 2018, 61(10): 1-7. [10] BONNETAIN X, NAYA-PLASENCIA M, SCHROTTENLOHER A. Quantum security analysis of AES[J]. IACR Transactions on Symmetric Cryptology, 2019(2): 55-93. [11] SAMIR H, LARS R K. A quantum distinguisher for 7/8-round SMS4 block cipher[J]. Quantum Information Processing, 2020, 19(11): 1-22. [12] ALMAZROOIE M, SAMSUDIN A, ABDULLAH R, et al. Quantum reversible circuit of AES-128[J]. Quantum Information Processing, 2018, 17(5): 1-30. [13] ZOU J, WEI Z, SUN S, et al. Quantum circuit implementations of AES with fewer qubits[C]//International Conference on the Theory and Application of Cryptology and Information Security. Cham: Springer, 2020: 697-726. [14] 国家密码管理局. 国家密码管理局关于发布无线局域网产品密码事宜公告[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. [15] 国家密码管理局. GM/T 0002-2012 SM4分组密码算法[S]. 北京: 中国标准出版社, 2012. State Cryptography Administration. GM/T 0002-2012 SM4 block cipher algorithm[S]. Beijing: Standards Press of China, 2012. [16] 中国标准化委员会. 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. [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分组密码算法综述[J]. 信息安全研究, 2016, 2(11): 995-1007. LYU S W, SU B Z, WANG P, et al. Overview on SM4 algorithm[J]. Journal of Information Security Research, 2016, 2(11): 995-1007. [19] LIANG H, WU L, ZHANG X, et al. Design of a masked S-Box for SM4 based on composite field[C]//2014 Tenth International Conference on Computational Intelligence and Security. Kunming: IEEE, 2014: 387-391. [20] 李新超, 钟卫东, 张帅伟, 等. 一种SM4算法S盒的门限实现方案[J]. 密码学报, 2018, 5(6): 641-650. LI X C, ZHONG W D, ZHANG S W, et al. A new threshold implementation of the S-box in SM4[J]. Journal of Cryptologic Research, 2018, 5(6): 641-650 [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] WANG C C, TRUONG T K, SHAO H M, et al. VLSI architectures for computing multiplications and inverses in GF(2m)[J]. IEEE Transactions on Computers, 1985, 100(8): 709-717. [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 [24] 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 -
点击查看大图
图(5) / 表(1)
计量
- 文章访问数: 6237
- HTML全文浏览量: 1923
- PDF下载量: 109
- 被引次数: 0
