基于復(fù)合域SM4 密碼算法S 盒的量子電路實(shí)現(xiàn)

羅慶斌，李曉瑜，楊國(guó)武，牛偉納，李 強(qiáng)

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

自從Shor 算法[1]提出以來，利用量子技術(shù)對(duì)現(xiàn)代密碼算法的分析便受到研究者們的關(guān)注。在對(duì)稱密碼算法的分析中，文獻(xiàn)[2]首先分析了量子技術(shù)對(duì)對(duì)稱密碼算法的影響，如Grover 算法[3]可以平方加速密鑰搜索速度，建議把密鑰長(zhǎng)度至少增加一倍以達(dá)到非量子環(huán)境下的安全強(qiáng)度。文獻(xiàn)[4]利用Simon 算法[5]可以快速尋找碰撞周期的特性分析對(duì)稱密碼系統(tǒng)的安全性，大幅提升了查詢效率。隨后，結(jié)合Grover 算法和Simon 算法對(duì)具有不同結(jié)構(gòu)或不同加密方式的對(duì)稱密碼算法分析方案被提出[6-8]。

這些安全分析大多需要對(duì)對(duì)稱密碼算法量子電路實(shí)現(xiàn)的資源進(jìn)行評(píng)估，因此對(duì)稱密碼算法的量子電路實(shí)現(xiàn)近幾年也得到了大量關(guān)注。此外，量子邏輯門都是可逆的，使用量子電路實(shí)現(xiàn)的密碼算法在執(zhí)行過程中不會(huì)有能量的耗散，因此可以抵抗各種和能量分析相關(guān)的側(cè)信道分析攻擊[9]，這是對(duì)稱密碼算法量子電路實(shí)現(xiàn)受到關(guān)注的另一原因。

在現(xiàn)有的對(duì)稱密碼算法量子電路實(shí)現(xiàn)方案中，S 盒作為密碼組件的非線性結(jié)構(gòu)，一直是研究的重點(diǎn)。 文獻(xiàn)[10]首先對(duì)AES 密碼算法中綜合S 盒所需的量子電路資源用兩種方案進(jìn)行了評(píng)估：方案一主要采用Itoh-Tsujii 算法[11]進(jìn)行評(píng)估，一共需要使用40 個(gè)量子比特，3 584 個(gè)T 門和4 569個(gè)Clifford 門；方案二主要使用穩(wěn)定子鏈技術(shù)[12]進(jìn)行評(píng)估，一共使用9 個(gè)量子比特，不超過9 695個(gè)T 門和12 631 個(gè)Clifford 門。但這兩種方案中只評(píng)估了實(shí)現(xiàn)S 盒時(shí)所需的量子資源，并沒有給出具體的量子線路。文獻(xiàn)[13]主要使用Itoh-Tsujii 算法[11]具體實(shí)現(xiàn)了AES 密碼算法S 盒的量子電路，一共使用了56 個(gè)量子比特，448 個(gè)Toffoli 門，494 個(gè)CNOT 門和4 個(gè)NOT 門。通過優(yōu)化AES 密碼算法S 盒中每個(gè)輸出的布爾表達(dá)式，文獻(xiàn)[14]給出的量子電路一共使用了32 個(gè)量子比特，55 個(gè)Toffoli 門，314 個(gè)CNOT 門和4 個(gè)NOT 門。通過對(duì)S 盒中輸出布爾表達(dá)式的進(jìn)一步優(yōu)化，文獻(xiàn)[15]設(shè)計(jì)的AES 密碼算法S 盒的量子電路一共使用26 個(gè)量子比特，46 個(gè)Toffoli 門，304 個(gè)CNOT 門和4 個(gè)NOT 門。

本文主要研究SM4 密碼算法S 盒的量子電路實(shí)現(xiàn)。SM4 密碼算法是用于WAPI 的分組密碼算法，2006 年由我國(guó)國(guó)家密碼管理局公開發(fā)布[16]，2021 年6 月發(fā)布成為國(guó)際標(biāo)準(zhǔn)[17](標(biāo)準(zhǔn)號(hào)為 ISO/IEC 18033-3：2010/AMD1：2021)。目前對(duì)于SM4密碼算法量子電路實(shí)現(xiàn)的研究較少。文獻(xiàn)[18]實(shí)現(xiàn)了SM4 密碼算法的S 盒，一共使用了48 個(gè)量子比特，592 個(gè)量子門，電路深度為289。文獻(xiàn)[19]實(shí)現(xiàn)的SM4 密碼算法的S 盒中添加了14 個(gè)輔助量子比特，加上輸入和輸出的量子比特，一共需要30 個(gè)量子比特，82 個(gè)Toffoli 門，510 個(gè)CNOT 門和87 個(gè)X 門。X 門和NOT 門是等價(jià)的，所以本文中不區(qū)分X 門和NOT 門。 本文主要通過把GF(28)中 的運(yùn)算同構(gòu)到 GF((24)2)中，使用NOT 門、CNOT 門和Toffoli 門構(gòu)建實(shí)現(xiàn)S 盒的量子電路。所使用的量子比特，量子門的數(shù)量，量子電路的深度等量子資源相比于文獻(xiàn)[19]都有較大的減少。

1 SM4 密碼算法的S 盒

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

SM4 密碼算法的加解密過程可以參看文獻(xiàn)[20]，這里不再贅述。S 盒是SM4 密碼算法中唯一的非線性變換，是保證算法安全性的關(guān)鍵組件，通常由256 個(gè)元素構(gòu)成的查詢表進(jìn)行描述。文獻(xiàn)[21]研究了S 盒的代數(shù)結(jié)構(gòu)，并給出了具體表達(dá)式：

ν是 G F(2)上 的向量，v= (1,1,0,0,1,0,1,1)。

1.2 S 盒的分解

S 盒事實(shí)上是一個(gè)8 量子比特的邏輯函數(shù)，8 量子比特的邏輯函數(shù)一共有 28！個(gè)。對(duì)于任意給定的8 量子比特的邏輯函數(shù)，目前還沒有有效的算法對(duì)其綜合。在式(1)中，仿射變換式(3)可以通過高斯消元法先綜合出矩陣F，再通過在對(duì)應(yīng)位置添加NOT 門的方式綜合出ν 的方式完成。接下來主要是綜合出 GF(28) 上 的乘法逆元運(yùn)算I，雖然它可以看成是由對(duì)換構(gòu)成的置換，但依然沒有有效的綜合算法。本文策略是將 GF(28)上的求逆運(yùn)算同構(gòu)到GF((24)2)上 的運(yùn)算。當(dāng)然，對(duì)于 GF(24)上的運(yùn)算可以進(jìn)一步同構(gòu)到 GF((22)2)中的運(yùn)算，從而將GF(28)中 的求逆運(yùn)算同構(gòu)到 GF(((22)2)2)中的運(yùn)算。但在 GF((22)2)上 實(shí)現(xiàn) GF(24)上的求逆等運(yùn)算時(shí)不得不添加更多的輔助量子比特。另外，對(duì)于大多數(shù)4 量子比特邏輯函數(shù)，可以采用雙向綜合[22]等方法實(shí)現(xiàn)。因此，只需將 GF(28)上的求逆運(yùn)算同構(gòu)到GF((24)2)上的運(yùn)算。實(shí)現(xiàn)S 盒的整體框架如圖1所示。

圖1 SM4 密碼算法S 盒復(fù)合域?qū)崿F(xiàn)框架圖

2 復(fù)合域中的運(yùn)算

由文獻(xiàn)[21]可知，SM4 密碼算法求逆運(yùn)算用到的不可約多項(xiàng)式為式(2)中的f(x)，即運(yùn)算中用到的有限域 GF(28)?GF(2)[x]/(f(x))。因?yàn)橥瑯?gòu)關(guān)系，所以當(dāng)給定n次不可約多項(xiàng)式g(x)時(shí)，文中不再區(qū) 分 GF(2n) 和 GF(2)[x]/(g(x)) 。 設(shè)X為f(x)的 一 個(gè)根，對(duì)于? α ∈GF(28)有：

同理，取不可約多項(xiàng)式p(y)=y2+μy+λ，其中μ,λ ∈GF(24) ， 設(shè)Y是p(y)的 一 個(gè) 根，則 對(duì) 于?r∈GF((24)2)有：

為了計(jì)算簡(jiǎn)便，取 μ=1，則不可約多項(xiàng)式p(y)=y2+y+λ，式(7)變?yōu)椋?/p>

從式(8)可知，為了求r-1， 需要在 G F(24)中進(jìn)行運(yùn)算，因此需要在 G F(24)中選取一個(gè)不可約多項(xiàng)式?？紤]到這些運(yùn)算的執(zhí)行效率，在3 個(gè)4 次不可約多項(xiàng)式中選取q(z)=z4+z+1。 設(shè)Z是q(z)的一個(gè)根，則對(duì)于?a∈GF(24)有：

3 基本組件的量子電路

由圖1 所示，為了實(shí)現(xiàn)SM4 密碼算法的S 盒，需要分別實(shí)現(xiàn) GF((24)2)中的求逆運(yùn)算，同構(gòu)映射δ和同構(gòu)映射 δ-1， 以及仿射變換A1和A2。下面分別描述它們的量子電路，文中的量子電路主要使用python 語(yǔ)言并利用qiskit 軟件包實(shí)現(xiàn)。

3.1 G F((24)2)求逆的基本量子電路

因此，對(duì)于 ?a∈GF(24)，可以找到如下的矩陣S使得a2=S·a，其中，

利用高斯消元法，可以實(shí)現(xiàn)其量子電路如圖2所示。

圖2 實(shí)現(xiàn)式(10)平方計(jì)算的量子電路圖

式中，ai和bi分 別是a和b和對(duì)應(yīng)位置上的元素，可以計(jì)算出：

于是，可以實(shí)現(xiàn)a和b乘積的量子電路如圖3所示。

圖3 式(12)中乘法計(jì)算的量子電路圖

對(duì)于乘法求逆運(yùn)算，首先將其表示成如下置換：

顯然，這是由7 個(gè)對(duì)換構(gòu)成的奇置換。但4 量子比特中的NOT 門，CNOT 門和Toffoli 門全都是偶置換，這意味著僅使用NCT 庫(kù)中的邏輯門綜合出的4 量子比特量子電路不能實(shí)現(xiàn) G F(24)中的求逆運(yùn)算。本文策略是添加一個(gè)輔助量子比特，先綜合出一個(gè)奇置換。這里先用兩個(gè)Toffoli 門，借助輔助量子比特綜合出置換 (14,15)，然后使用文獻(xiàn)[22]中的雙向綜合算法實(shí)現(xiàn)出求逆運(yùn)算的量子電路如圖4 所示。圖中a4是輔助量子比特。

有了這些基本量子電路圖，便可以非常容易地實(shí)現(xiàn)式(8)中G F((24)2)內(nèi)的求逆運(yùn)算。

3.2 同構(gòu)映射的量子電路圖

在討論同構(gòu)映射 δ和 δ-1的量子電路之前，先討論它們的構(gòu)造。事實(shí)上， GF(28) 中 含有與 GF(24)同構(gòu)的子域，也含有 GF((24)2)同構(gòu)的子域，可以把Y和Z用 G F(28) 中 的元素表示，則 G F((24)2)的基也可以用G F(28)中的元素表示，于是有：

由(δ-1)-1=δ 可 以求出同構(gòu)映射δ。

接下來，討論同構(gòu)映射的選取。 GF((24)2)中，形如p(y)=y2+y+λ的不可約多項(xiàng)式共有8 個(gè)，每個(gè)多項(xiàng)式都有2 個(gè)根。q(z)共有4 個(gè)根。因此，一共有64 組同構(gòu)映射。為了在實(shí)現(xiàn)同構(gòu)映射時(shí)盡可能少地使用量子門，選取元素“1”的個(gè)數(shù)最少的一組。經(jīng)計(jì)算，這64 組中 δ和 δ-1最少共有44 個(gè)“1”。此時(shí)，Y=0xC5， Z=0x50 ， λ=0xF。同構(gòu)映射為：

利用高斯消元法可以綜合出 δ 和 δ-1的量子電路分別如圖5 和圖6 所示。

圖5 同構(gòu)映射δ 的量子電路圖

圖6 同構(gòu)映射 δ-1的量子電路圖

當(dāng) λ=0xF時(shí) ，對(duì)于 ?a∈GF(24) ， 計(jì)算 λ·a的值等價(jià)于計(jì)算矩陣λ 乘以a的值，其中，

其量子電路如圖7 所示。

圖7 乘以常數(shù)λ 的量子電路

3.3 仿射變換的量子電路圖

仿射變換式(3)中F和ν 的值都已經(jīng)給出，所以可以綜合出其量子電路如圖8 所示。

圖8 式(3)中仿射變換的量子電路圖

4 S 盒的量子電路圖

4.1 量子電路圖

為了描述方便，記S為圖2 中實(shí)現(xiàn)平方計(jì)算的電路圖，圖3 中實(shí)現(xiàn)乘法計(jì)算量子電路的乘數(shù)分別記為兩個(gè)實(shí)心圓點(diǎn)，結(jié)果記為M。I為圖4 中求逆運(yùn)算的量子電路圖，圖5 和圖6 中實(shí)現(xiàn)同構(gòu)映射的電 路圖分別記 為 δ 和 δ-1，圖7 中的量子 電 路 記為λ，A1和A2為圖8 中仿射變換的量子電路圖。此外，為了盡可能少地使用輔助量子比特，需要把一些寄存器還原，此時(shí)只需逆序添加原來的量子電路即可，圖2 的逆電路記為S-1，圖7 的逆電路記為λ-1。根據(jù)圖1 和式(8)可以得出SM4 密碼算法的量子電路邏輯圖如圖9 所示，具體的量子電路圖如圖10 所示。圖9 中a,b,c,d都是4 量子比特寄存器，e是5 量子比特寄存器。除了求逆操作需要用到寄存器e的第5 位外，其他操作都只用到前面的4 位。初始化時(shí)，寄存器a的值為S 盒輸入的低4 位，b為S 盒輸入的高4 位，c,d,e每一位上的值都為 |0〉。經(jīng)過該電路圖運(yùn)算后，寄存器c輸出S 盒輸出的低4 位，d輸出S 盒輸出的高4 位。通過IBM 量子平臺(tái)的Aer 模擬器驗(yàn)證，該量子電路圖是完全正確的。

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

圖10 SM4 密碼算法S 盒的具體量子電路圖

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

文中的量子電路是通過NOT 門、CNOT 門和Toffoli 門實(shí)現(xiàn)的。通過計(jì)算S 盒量子電路的比特?cái)?shù)和所使用的量子門的數(shù)量刻畫電路的復(fù)雜度。在S 盒實(shí)現(xiàn)的量子電路中，a,b,c,d都是4 量子比特寄存器，e是5 量子比特寄存器，所有一共使用了21 量子比特?，F(xiàn)在計(jì)算量子門的數(shù)量，仿射變換A1和A2其實(shí)是一樣的，它們的電路圖都使用了35 個(gè)CNOT 門，和5 個(gè)NOT 門；同構(gòu)映射 δ的電路圖共使用了23 個(gè)CNOT 門； δ-1的電路圖共使用19 個(gè)CNOT 門；平方計(jì)算S的電路圖和它的逆電路圖都使用了5 個(gè)CNOT 門，它們?cè)赟 盒的量子電路圖中都使用了2 次；乘以常數(shù) λ的量子電路和它的逆電路都使用了9 個(gè)CNOT 門；乘法計(jì)算的量子電路共使用了16 個(gè)Toffoli 門和3 個(gè)CNOT門，S 盒的量子電路圖中共使用了3 次乘法計(jì)算；乘法逆運(yùn)算的電路圖共使用了7 個(gè)Toffoli 門和5個(gè)CNOT 門；此外還使用了3 組共12 個(gè)CNOT 門做量子比特的復(fù)制。最終本文實(shí)現(xiàn)整個(gè)S 盒所使用的量子資源，和文獻(xiàn)[19]使用量子資源的對(duì)比情況如表1 所示。

表1 文獻(xiàn)[19]與本文綜合S 盒所用量子資源對(duì)比表 個(gè)

由表1 可以看出，實(shí)現(xiàn)SM4 密碼算法S 盒文獻(xiàn)[19]需要使用30 個(gè)量子比特，82 個(gè)Toffoli門，510 個(gè)CNOT 門和87 個(gè)NOT 門。采用本文提出的方法只需要使用21 個(gè)量子比特，55 個(gè)Toffoli 門，176 個(gè)CNOT 門和10 個(gè)NOT 門。此外，還計(jì)算出本文中實(shí)現(xiàn)的SM4 算法S 盒量子電路的深度為151。由此可以看出：本文實(shí)現(xiàn)的方法的效率在文獻(xiàn)[19]的基礎(chǔ)上有顯著提高。

5 結(jié) 束 語(yǔ)

本文采用NOT 門、CNOT 門和Toffoli 門實(shí)現(xiàn)SM4 密碼算法S 盒的量子電路圖。根據(jù)S 盒的代數(shù)結(jié)構(gòu)，首先將 GF(28) 中 的求逆運(yùn)算同構(gòu)到GF((24)2)求 逆，其次根據(jù) GF((24)2)中求逆運(yùn)算的表達(dá)式分別給出了 G F(24)中平方計(jì)算、乘法計(jì)算和求逆運(yùn)算的量子電路，再次根據(jù)最小化基轉(zhuǎn)換矩陣中“1”元素個(gè)數(shù)的原則求出了基轉(zhuǎn)化矩陣的量子電路，然后利用高斯消元法給出了仿射變換的量子電路，最后綜合出SM4 密碼算法S 盒的量子電路。整個(gè)量子電路一共使用了21 個(gè)量子比特，55 個(gè)Toffoli 門，176 個(gè)CNOT 門和10 個(gè)NOT 門。和現(xiàn)有方法相比，所使用的量子資源進(jìn)一步減少，效率進(jìn)一步提高。