基于復合域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 量子比特?，F在計算量子門的數量，仿射變換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 門。和現有方法相比，所使用的量子資源進一步減少，效率進一步提高。