SM4 密碼算法S 盒的量子電路實現

羅慶斌，李曉瑜，楊國武

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

量子計算極大地改變了現代密碼系統的安全性。對于非對稱密碼系統，Shor 算法[1]能快速破解基于大整數分解的密碼算法[2]和基于離散對數的密碼算法[3]。量子計算對于對稱密碼系統的影響雖然沒有像非對稱密碼系統那樣顯著，但最近也得到大量關注。文獻[4]首先分析了Grover 算法[5]對對稱密碼系統的量子威脅，建議把原來的密鑰長度至少增加一倍。文獻[6]利用Simon 算法[7]尋找碰撞周期以攻擊對稱密碼系統，一些在經典環境中需要Ω(2n/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 盒的量子電路。

1 SM4 密碼算法

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

1.1 加密算法

加密算法采用32 輪迭代結構，每輪使用一個輪密鑰。

設輸入明文為 (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是輪函數，變換T:GF(232)→GF(232)由非線性變換τ 和線性變換L構成，即：

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

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

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

式中，＜ ＜＜i表 示把32 位字循環左移i位。

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

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

1.2 密鑰擴展算法

2 S 盒的代數結構

在SM4 密碼算法中，S 盒是唯一的非線性變換，是保證安全的關鍵組件。S 盒通常由256 個元素構成的查詢表描述。文獻[21]研究了S 盒的代數結構，并給出了如下的具體表達式：

GF(28)

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

3 S 盒的量子電路

3.1 實現思路分析

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

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

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

3.2 量子電路實現

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

圖2 實現式（13）仿射變換的量子電路圖

圖3 實現式（17）平方計算的量子電路圖

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

1）(a)2=a2

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

圖4 實現式（18）乘法計算的量子電路圖

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

3.3 量子電路復雜度分析

這里的量子電路是利用NCT 門庫實現，即采用NOT 門、CNOT 門和Toffoli 門實現。通過這些量子電路所用量子比特的數量、量子門的數量和量子電路的深度描述構建的量子電路的復雜度如表1 所示。

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

由圖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 盒的量子電路還是比較高效的。

4 結 束 語

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