羅慶斌，李曉瑜，楊國武

（1. 湖北民族大學(xué)信息工程學(xué)院 湖北 恩施 445000；2. 電子科技大學(xué)信息與軟件工程學(xué)院 成都 610054；3. 電子科技大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院 成都 611731）

量子計(jì)算極大地改變了現(xiàn)代密碼系統(tǒng)的安全性。對于非對稱密碼系統(tǒng)，Shor 算法[1]能快速破解基于大整數(shù)分解的密碼算法[2]和基于離散對數(shù)的密碼算法[3]。量子計(jì)算對于對稱密碼系統(tǒng)的影響雖然沒有像非對稱密碼系統(tǒng)那樣顯著，但最近也得到大量關(guān)注。文獻(xiàn)[4]首先分析了Grover 算法[5]對對稱密碼系統(tǒng)的量子威脅，建議把原來的密鑰長度至少增加一倍。文獻(xiàn)[6]利用Simon 算法[7]尋找碰撞周期以攻擊對稱密碼系統(tǒng)，一些在經(jīng)典環(huán)境中需要Ω(2n/2)次查詢的密碼算法在該量子環(huán)境下只需要O(n)次查詢。文獻(xiàn)[8]結(jié)合Grover 算法和Simon 算法對具有FX 結(jié)構(gòu)的對稱密碼在量子環(huán)境下的安全性進(jìn)行了分析。文獻(xiàn)[9]結(jié)合Grover 算法和Simon算法對具有Feistel 結(jié)構(gòu)的對稱密碼算法提出了量子密鑰恢復(fù)攻擊。文獻(xiàn)[10]通過在量子環(huán)境下利用Demirci-Sel?uk 中間人攻擊和提高解S 盒差分方程的效率分析了AES 密碼算法在量子環(huán)境下的安全性。文獻(xiàn)[11]利用Grover 算法和Simon 算法為SM4 密碼算法構(gòu)造了一個(gè)8 輪的量子區(qū)分器。

這些對稱密碼在量子環(huán)境下的安全性分析基本是建立在它們已經(jīng)可以用量子電路實(shí)現(xiàn)的假設(shè)上的。但是目前針對對稱密碼算法的量子電路實(shí)現(xiàn)研究較少，且基本是對AES 密碼算法的量子電路實(shí)現(xiàn)[12-13]，其他對稱密碼算法量子電路實(shí)現(xiàn)的研究幾乎沒有。

SM4 算法是用于WAPI 的分組密碼算法，2006年由我國國家密碼管理局公開發(fā)布[14]，2012 年3 月發(fā)布成為國家密碼行業(yè)標(biāo)準(zhǔn)[15]（標(biāo)準(zhǔn)號為 GM/T 0002-2012），2016 年8 月發(fā)布成為國家標(biāo)準(zhǔn)[16]（標(biāo)準(zhǔn)號為 GB/T 32907-2016），2021 年6 月發(fā)布成為國際標(biāo)準(zhǔn)[17]（標(biāo)準(zhǔn)號為 ISO/IEC 18033-3：2010/AMD1：2021）。SM4 算法的安全性自發(fā)布以來，得到了廣泛的關(guān)注。在這些安全性分析中，SM4 算法中唯一的非線性變換S 盒起著關(guān)鍵性的作用。文獻(xiàn)[18]分析了SM4 算法中最小活躍S 盒個(gè)數(shù)與抵抗差分攻擊輪數(shù)之間的關(guān)系。文獻(xiàn)[19-20]分別提出了基于掩碼的S 盒實(shí)現(xiàn)方案和基于門限理論的S 盒的實(shí)現(xiàn)方案，以提高SM4 密碼算法的安全性。

本文主要通過SM4 密碼算法S 盒的代數(shù)結(jié)構(gòu)，使用NOT 門、CNOT 門和Toffoli 門構(gòu)建實(shí)現(xiàn)S 盒的量子電路。

1 SM4 密碼算法

SM4 算法是分組密碼算法，其數(shù)據(jù)分組長度和密鑰分組長度都為128 bit。加密算法與解密算法都以字節(jié)（8 位）和字（32 位）為單位進(jìn)行數(shù)據(jù)處理。

1.1 加密算法

加密算法采用32 輪迭代結(jié)構(gòu)，每輪使用一個(gè)輪密鑰。

設(shè)輸入明文為 (X0,X1,X2,X3)∈(GF(232))4，輸出的 密 文 為 (Y0,Y1,Y2,Y3)∈(GF(232))4，rki∈GF(232)(i=0,1,2,···,31)為輪密鑰。加密算法可描述如下：

式中，i=0,1,2,···,31，則有：

式中，F(xiàn)是輪函數(shù)，變換T:GF(232)→GF(232)由非線性變換τ 和線性變換L構(gòu)成，即：

變換 τ由4 個(gè)8 bit 的非線性變換S 盒并行構(gòu)成。設(shè)A=(α0,α1,α2,α3)∈(GF(28))4是非線性變換τ的輸入，B=(β0,β1,β2,β3)∈(GF(28))4是輸出，則變換τ 定義如下：

式中， S box(·)為以字節(jié)為單位的非線性替換。S 盒的替換表可以參考文獻(xiàn)[18]，將在第2 章介紹它的代數(shù)結(jié)構(gòu)。

變換 τ 的 輸出B將作為線性變換L的輸入。設(shè)C∈GF(232)是L的輸出。則線性變換L定義為：

式中，＜ ＜＜i表 示把32 位字循環(huán)左移i位。

SM4 密碼算法的加密過程如圖1 所示。由于解密算法和加密算法采用相同的變換結(jié)構(gòu)和過程，只是反序使用輪密鑰，這里不再贅述。

圖1 SM4 分組密碼算法加密過程

1.2 密鑰擴(kuò)展算法

2 S 盒的代數(shù)結(jié)構(gòu)

在SM4 密碼算法中，S 盒是唯一的非線性變換，是保證安全的關(guān)鍵組件。S 盒通常由256 個(gè)元素構(gòu)成的查詢表描述。文獻(xiàn)[21]研究了S 盒的代數(shù)結(jié)構(gòu)，并給出了如下的具體表達(dá)式：

GF(28)

式中，I是 上的乘法逆元，這里的不可約多項(xiàng)式為：

3 S 盒的量子電路

3.1 實(shí)現(xiàn)思路分析

用量子電路實(shí)現(xiàn)S 盒，實(shí)際上就是實(shí)現(xiàn)式（11）。在式（11）中仿射變換的表達(dá)式已經(jīng)由式（13）給出，可以用類似高斯消元的方式實(shí)現(xiàn)矩陣FT，即通過行變換把矩陣FT化成單位陣，每做一次行變換便在對應(yīng)量子電路中添加一個(gè)CNOT門，反序排列這些CNOT 門，便構(gòu)造出了矩陣FT的量子電路。對于列向量v，在出現(xiàn)“1”的對應(yīng)位置添加NOT 門便可實(shí)現(xiàn)。

乘法逆元I會相對復(fù)雜。文獻(xiàn)[22]證明了GF(2n) 上 的任一非零元素a的逆元可以表示成(a)-1=(a)2n-2。因此需要計(jì)算：

因 此，可 以 得 出： ?a∈GF(2)[x]/(f(x))，有a2=Sq·a，其中：

3.2 量子電路實(shí)現(xiàn)

本文使用Python 語言并利用qiskit 軟件包實(shí)現(xiàn)所求的量子電路。對于式（13）中仿射變換的表達(dá)式，使用高斯消元法實(shí)現(xiàn)矩陣FT，并通過在對應(yīng)位置添加NOT 的方法實(shí)現(xiàn)向量v，最終式（13）中仿射變換的量子電路如圖2 所示。 G F(28)上的平方計(jì)算可以通過式（17）的線性變換表示，利用高斯消元法實(shí)現(xiàn)平方計(jì)算的量子電路如圖3 所示。式（19）和式（20）中的d和e可以通過Toffoli 門實(shí)現(xiàn)，式（22）中的矩陣QT可以通過高斯消元法實(shí)現(xiàn)，因此式（18）便可以實(shí)現(xiàn)，量子電路如圖4 所示。

圖2 實(shí)現(xiàn)式（13）仿射變換的量子電路圖

圖3 實(shí)現(xiàn)式（17）平方計(jì)算的量子電路圖

為了更快速地計(jì)算I(a)=a254，本文采用Itoh-Tsujii 算法[24]，但為了盡可能少地使用輔助量子比特，把計(jì)算順序調(diào)整如下：

1）(a)2=a2

由于仿射變換和平方計(jì)算的量子電路都為8 量子比特，乘法計(jì)算量子電路為24 量子比特，為了更加方便地表示S 盒的量子電路，本文以8 量子比特為單位描述S 盒的量子電路。記A1和A2為圖2 中實(shí)現(xiàn)仿射變換的量子電路；Sq 為圖3 中實(shí)現(xiàn)平方計(jì)算的量子電路；圖4 中實(shí)現(xiàn)乘法計(jì)算量子電路的乘數(shù)輸入分別記為兩個(gè)實(shí)心圓點(diǎn)，乘積結(jié)果記為M。主要根據(jù)計(jì)算a254的步驟，可以得出S 盒的量子電路如圖5所示。

圖4 實(shí)現(xiàn)式（18）乘法計(jì)算的量子電路圖

圖5 S 盒的量子電路示意圖

3.3 量子電路復(fù)雜度分析

這里的量子電路是利用NCT 門庫實(shí)現(xiàn)，即采用NOT 門、CNOT 門和Toffoli 門實(shí)現(xiàn)。通過這些量子電路所用量子比特的數(shù)量、量子門的數(shù)量和量子電路的深度描述構(gòu)建的量子電路的復(fù)雜度如表1 所示。

表1 量子電路所用量子資源情況表

由圖5 可知，最終S 盒的實(shí)現(xiàn)電路中需要2 次調(diào)用仿射變換的量子電路，每個(gè)仿射變換的量子電路由34 個(gè)CNOT 門和5 個(gè)NOT 門構(gòu)成，電路深度為23；需要7 次調(diào)用平方計(jì)算的量子電路，每個(gè)平方計(jì)算的量子電路由22 個(gè)CNOT 門構(gòu)成，電路深度為16；需要4 次調(diào)用乘法計(jì)算的量子電路，每個(gè)乘法計(jì)算的量子電路由64 個(gè)Toffoli 門和24 個(gè)CNOT 門構(gòu)成，電路深度為39；此外還需要用1 組（8 個(gè)）CNOT 門對量子比特進(jìn)行復(fù)制。整個(gè)S 盒的量子電路中一共使用了48 個(gè)量子比特，592 個(gè)量子門，電路深度為289。由于本文是首次實(shí)現(xiàn)SM4 密碼算法S 盒的量子電路，不能通過對比的方式來分析該電路的復(fù)雜度。但文獻(xiàn)[12]實(shí)現(xiàn)了AES 密碼算法S 盒的量子電路，在該量子電路中，共使用了3 組（24 個(gè)）CNOT 門對量子比特進(jìn)行復(fù)制，使用的量子比特?cái)?shù)為56。由此可以看出，本文實(shí)現(xiàn)的SM4 算法S 盒的量子電路還是比較高效的。

4 結(jié) 束 語

本文首次給出了SM4 密碼算法S 盒的量子電路。根據(jù)S 盒的代數(shù)結(jié)構(gòu)，首先給出S 盒代數(shù)表達(dá)式中仿射變換的量子電路，然后把代數(shù)表達(dá)式中求GF(28)下元素的逆元轉(zhuǎn)換為求該元素的254 次方，為此，分別構(gòu)建了 G F(28)中平方計(jì)算的量子電路和乘法計(jì)算的量子電路，再通過改進(jìn)的Itoh-Tsujii 算法給出S 盒的量子電路。所構(gòu)建的S 盒的量子電路共使用了48 個(gè)量子比特，592 個(gè)量子門，電路深度為289。本文的研究將對量子環(huán)境下SM4 密碼算法的研究產(chǎn)生積極影響。