SM4 算法的量子實(shí)現(xiàn)*

林 達(dá), 向澤軍, 張若琳, 張莎莎, 曾祥勇

湖北大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)學(xué)院應(yīng)用數(shù)學(xué)湖北省重點(diǎn)實(shí)驗(yàn)室, 武漢 430062

1 引言

隨著量子信息科學(xué)的快速發(fā)展, 量子技術(shù)特別是量子計(jì)算機(jī)的研究取得了突破性進(jìn)展. 量子計(jì)算機(jī)具有并行處理信息的能力, 這種特性使得一些經(jīng)典計(jì)算機(jī)中的困難問題在量子場(chǎng)景下很容易被解決, 從而給公鑰密碼的安全性帶來嚴(yán)重威脅. 特別是Shor 算法[1]的提出, 這一開創(chuàng)性工作可以有效地用來進(jìn)行大整數(shù)因子分解和求解離散對(duì)數(shù), 使得目前基于上述困難性問題的經(jīng)典密碼安全性受到嚴(yán)重挑戰(zhàn). 目前大規(guī)模通用量子計(jì)算機(jī)遠(yuǎn)未普及, 而且量子計(jì)算機(jī)的性能及相關(guān)技術(shù)的發(fā)展也具有一定的不確定性, 因此, 完成由現(xiàn)有的經(jīng)典密碼算法向后量子密碼算法的過渡仍有許多問題亟待解決. 美國(guó)國(guó)家標(biāo)準(zhǔn)與技術(shù)研究院(National Institute of Standards and Technology, NIST) 于2016 年啟動(dòng)了后量子密碼算法標(biāo)準(zhǔn)的征集工作[2]. 不同于經(jīng)典密碼算法安全強(qiáng)度的定義方式, 針對(duì)量子密碼算法, NIST 根據(jù)AES[3]和SHA-3[4]提供的安全強(qiáng)度定義了一系列廣泛的安全強(qiáng)度類別, 分別與窮舉攻擊上述經(jīng)典密碼所需量子資源有關(guān). 由于Grover 算法[5]在遍歷一個(gè)無序集合時(shí)能夠?qū)崿F(xiàn)二次加速, 研究經(jīng)典密碼算法利用Grover 算法窮舉密鑰的量子實(shí)現(xiàn)開銷是當(dāng)前量子密碼領(lǐng)域的研究熱點(diǎn).

與經(jīng)典電路不同, 量子電路具有可逆性特點(diǎn). 在量子電路中實(shí)現(xiàn)經(jīng)典電路邏輯門時(shí), 可以分別使用Toffoli 門和CNOT 門模擬經(jīng)典電路中的與運(yùn)算和異或運(yùn)算, 因此經(jīng)典電路的功能都可以使用量子電路實(shí)現(xiàn). 考慮到量子計(jì)算機(jī)的不確定性, 以節(jié)約量子比特為前提設(shè)計(jì)高效的量子電路是研究經(jīng)典密碼算法量子優(yōu)化實(shí)現(xiàn)的一個(gè)主要關(guān)注點(diǎn). 此外,由于Toffoli 門的實(shí)現(xiàn)代價(jià)遠(yuǎn)大于CNOT 門、Hadamard 門等Clifford門集中的通用邏輯門, 量子電路中消耗的Toffoli 門數(shù)量以及電路Toffoli 深度是評(píng)估量子電路實(shí)現(xiàn)代價(jià)的一個(gè)主要參考指標(biāo). 目前, 對(duì)對(duì)稱密碼算法量子優(yōu)化實(shí)現(xiàn)的探索主要以AES 算法為研究對(duì)象[6–10]. 2016年, Grassl 等人[6]首次系統(tǒng)地提出了一種利用Grover 算法窮舉搜索AES 密鑰的量子實(shí)現(xiàn)方案, 并從量子電路大小、量子比特?cái)?shù)量、量子電路深度等方面全面分析了該窮舉攻擊的量子資源開銷, 其中量子電路的大小與整體電路消耗的通用量子邏輯門數(shù)量有關(guān). 隨后, Almazrooie 等人[7]針對(duì)AES-128 設(shè)計(jì)了一種可逆量子電路, 該電路采用Grassl 等人設(shè)計(jì)的zig-zag 結(jié)構(gòu)[6]以節(jié)約量子比特. 不同于文獻(xiàn)[6] 和文獻(xiàn)[7] 基于有限域上的乘法以及求逆運(yùn)算構(gòu)造AES 算法S 盒的優(yōu)化實(shí)現(xiàn), Langenberg 等人[8]利用基于塔域分解生成的AES 算法S 盒的經(jīng)典實(shí)現(xiàn)[11], 設(shè)計(jì)了一組全新的AES 量子優(yōu)化實(shí)現(xiàn)電路并評(píng)估了利用Grover 算法進(jìn)行窮舉攻擊的量子資源開銷.

在統(tǒng)計(jì)電路的量子資源開銷時(shí), 上述研究主要關(guān)注量子比特以及量子邏輯門的使用數(shù)量. 近年來, 考慮到量子糾錯(cuò)碼的應(yīng)用, 越來越多的研究同時(shí)關(guān)注了量子電路的另一個(gè)評(píng)價(jià)指標(biāo): depth-times-width 值,即量子電路中量子比特?cái)?shù)與電路深度之積[9,10]. 2020 年, Jaques 等人[9]以AES 和LowMC[12]為例研究了在電路深度受限情形下進(jìn)行量子密鑰搜索攻擊的代價(jià). 在ASIACRYPT 2020 上, Zou 等人[10]提出了一種改進(jìn)的zig-zag 結(jié)構(gòu), 該結(jié)構(gòu)基于對(duì)S 盒代數(shù)結(jié)構(gòu)及其經(jīng)典實(shí)現(xiàn)的進(jìn)一步研究, 優(yōu)化了AES 算法量子實(shí)現(xiàn)電路消耗的量子比特?cái)?shù)目以及電路的depth-times-width 值.

SM4 算法[13]是我國(guó)商用密碼算法標(biāo)準(zhǔn), 并于2021 年正式成為ISO/IEC 國(guó)際標(biāo)準(zhǔn). SM4 算法采用了與AES 算法類似的S 盒設(shè)計(jì)方法, 鑒于基于塔域結(jié)構(gòu)構(gòu)造AES 類算法S 盒的實(shí)現(xiàn)是目前較為高效的方法, 通過研究SM4 算法S 盒的代數(shù)結(jié)構(gòu)設(shè)計(jì)其優(yōu)化實(shí)現(xiàn)被廣泛關(guān)注[14–17]. Bai 等人[14]采用Paar 提出構(gòu)造同構(gòu)映射的方法[18], 利用多項(xiàng)式基將F28表示成F24的二次擴(kuò)域, 由此將F28上的元素分解為系數(shù)屬于F24的線性多項(xiàng)式, 最終通過將F24上的運(yùn)算進(jìn)一步分解為一系列F22上的操作實(shí)現(xiàn)有限域上的求逆運(yùn)算. 利用組合邏輯電路, Abbasi 等人[15]研究了SM4 算法S 盒適用于如智能卡等面積受限環(huán)境的緊湊實(shí)現(xiàn), 并基于正交基的塔域表示F28→((F22)2)2提出了一種SM4 算法S 盒的新型組合結(jié)構(gòu). 2015年, 一種基于(F24)2上的復(fù)合域設(shè)計(jì)的SM4 算法S 盒新型結(jié)構(gòu)被提出[16], 與之前的實(shí)現(xiàn)相比, 利用該結(jié)構(gòu)能有效減少硬件實(shí)現(xiàn)所需異或門數(shù)量. 通過有限域上乘法逆及其仿射等價(jià)類的面積優(yōu)化實(shí)現(xiàn), Wei 等人[17]研究了基于正規(guī)基F28上逆的塔域表示, 同時(shí)利用既有簡(jiǎn)化組合邏輯電路的技術(shù), 全面研究了所有可能正交基下F28上求逆運(yùn)算的塔域表示, 并給出了SM4 算法S 盒更緊湊的硬件實(shí)現(xiàn).

1.1 本文貢獻(xiàn)

根據(jù)對(duì)塔域分解技術(shù)生成的S 盒經(jīng)典實(shí)現(xiàn)的研究, 本文介紹了一種結(jié)合即有啟發(fā)式算法設(shè)計(jì)SM4 算法S 盒的量子實(shí)現(xiàn)新方法, 該方法為構(gòu)造高效的S 盒量子實(shí)現(xiàn)提供了新思路. 利用該方法, 本文設(shè)計(jì)了一種對(duì)S 盒輸出量子比特初始值無任何要求的SM4 算法S 盒的量子優(yōu)化實(shí)現(xiàn)方案; 進(jìn)一步, 基于對(duì)SM4算法合成置換不同實(shí)現(xiàn)方法的探索, 本文提出了一種通過將線性變換前移以改進(jìn)置換T和T′的量子實(shí)現(xiàn)優(yōu)化技術(shù). 利用該技術(shù), 本文分別為SM4 算法的密鑰擴(kuò)展算法和輪函數(shù)設(shè)計(jì)了一種量子優(yōu)化實(shí)現(xiàn)方案, 基于此, 本文針對(duì)SM4 算法, 結(jié)合其加密輪函數(shù)將合成置換輸出異或到其中一個(gè)分支的特性, 提出了一套能有效節(jié)約量子比特的量子實(shí)現(xiàn)整體結(jié)構(gòu); 此外, 通過系統(tǒng)地研究電路并行處理的S 盒數(shù)量對(duì)SM4 算法不同實(shí)現(xiàn)方案的量子比特?cái)?shù)以及depth-times-width 值等指標(biāo)的影響, 本文對(duì)比了基于zig-zag 結(jié)構(gòu)實(shí)現(xiàn)的AES-128 算法量子電路, 并提出了一種在上述指標(biāo)上均優(yōu)于AES-128 的SM4 算法量子實(shí)現(xiàn)方案; 最后,本文首次提出了結(jié)合Grover 算法對(duì)SM4 算法進(jìn)行量子密鑰窮搜的量子電路, 并分析了SM4 算法抗量子窮舉攻擊的安全強(qiáng)度. 本文的研究結(jié)果表明, 在考慮量子比特開銷和depth-times-width 值等指標(biāo)的情形下, SM4 算法抵抗量子窮舉攻擊的安全性要弱于AES-128 算法.

1.2 本文組織結(jié)構(gòu)

第2 節(jié)引入本文所使用的符號(hào), 并簡(jiǎn)要介紹Grover 算法和SM4 算法等預(yù)備知識(shí). 第3 節(jié)給出SM4算法不同子部件的量子實(shí)現(xiàn)方案. 第4 節(jié)針對(duì)SM4 算法的密鑰擴(kuò)展算法和輪函數(shù)設(shè)計(jì)了相應(yīng)的量子電路.第5 節(jié)介紹利用本文設(shè)計(jì)的SM4 量子實(shí)現(xiàn)方案進(jìn)行量子密鑰窮舉的量子電路, 并評(píng)估該攻擊的量子資源開銷. 第6 節(jié)對(duì)本文的工作進(jìn)行總結(jié).

2 預(yù)備知識(shí)

本章介紹本文使用的符號(hào)、Grover 搜索算法以及SM4 算法及其S 盒的經(jīng)典實(shí)現(xiàn)等背景知識(shí).

2.1 符號(hào)說明

2.2 Grover 算法

Grover 算法的具體流程如圖1 所示, 其中H為Hadamard 門.

圖1 Grover 算法Figure 1 Grover algorithm

由文獻(xiàn)[19] 式6.6 可知, 上式可以寫為:

利用Grover 算法遍歷無序集合的具體步驟如下:

(a) 將Uf作用于輸入量子態(tài).

(b) 應(yīng)用H?n.

(c) 相位翻轉(zhuǎn).

(d) 應(yīng)用H?n.

(3) 測(cè)量電路前n個(gè)量子比特位.

2.3 SM4 算法

SM4 算法分組長(zhǎng)度與密鑰長(zhǎng)度均為128 比特, 采用32 輪非線性迭代結(jié)構(gòu), 其整體結(jié)構(gòu)如圖2 所示.

圖2 SM4 算法流程圖Figure 2 Procedure of SM4

2.3.1 輪函數(shù)

2.3.2 密鑰擴(kuò)展算法

記SM4 算法加密密鑰為MK=(MK0,MK1,MK2,MK3)∈(F322)4, 則第i輪輪密鑰的生成方式為:

其中CKi為給定常數(shù),i= 0,1,··· ,31. (K0,K1,K2,K3) 初始化為(MK0⊕FK0,MK1⊕FK1,MK2⊕FK2,MK3⊕FK3), FKj(j= 0,1,2,3) 為系統(tǒng)參數(shù). 變換T′由非線性變換τ和線性變換L′復(fù)合而成,與算法輪函數(shù)中T變換類似, 記變換τ的輸出為B, 則L′的輸出C為

2.3.3 SM4 算法S 盒的經(jīng)典實(shí)現(xiàn)

SM4 算法S 盒的硬件實(shí)現(xiàn)被廣泛研究[14–17], 表1 列出了各參考文獻(xiàn)提出的SM4 算法S 盒實(shí)現(xiàn)方案中不同邏輯門電路的消耗數(shù)量.

表1 SM4 算法S 盒的硬件實(shí)現(xiàn)開銷Table 1 Hardware cost to implement S-box of SM4

文獻(xiàn)[17] 利用塔域分解技術(shù)以節(jié)約硬件面積為出發(fā)點(diǎn)研究了AES 類算法S 盒的優(yōu)化實(shí)現(xiàn), 并給出了SM4 算法S 盒的硬件實(shí)現(xiàn)方案(見文獻(xiàn)[17] 附錄C). 該方法將SM4 算法S 盒的實(shí)現(xiàn)分解為5 個(gè)部分,分別由以下5 個(gè)函數(shù)表示.

函數(shù)Input() 為SM4 算法S 盒實(shí)現(xiàn)中的第一層線性部分. 函數(shù)Input() 的輸入為S 盒的輸入, 記為(x0,x1,··· ,x7), 其輸出為(y0,y1,··· ,y17), 且輸出可如下計(jì)算:

函數(shù)Top() 為SM4 算法S 盒實(shí)現(xiàn)中的第一層非線性部分, 其輸入為函數(shù)Input() 的輸出, 即(y0,y1,··· ,y17), 其輸出(p0,p1,p2,p3) 可如下計(jì)算:

函數(shù)Middle() 為SM4 算法S 盒實(shí)現(xiàn)中的第二層非線性部分, 其輸入為函數(shù)Top() 的輸出, 即(p0,p1,p2,p3). 記函數(shù)Middle() 的輸出為(l0,l1,l2,l3), (l0,l1,l2,l3) 可如下計(jì)算:

函數(shù)Bottom() 為SM4 算法S 盒實(shí)現(xiàn)中的第三層非線性部分, 函數(shù)Input() 的輸出(y0,y1,··· ,y17)以及函數(shù)Middle() 的輸出(l0,l1,l2,l3) 作為其輸入, 其輸出(e0,e1,··· ,e17) 可如下計(jì)算:

函數(shù)Output() 為SM4 算法S 盒實(shí)現(xiàn)中的第二層線性部分, 其輸入為函數(shù)Bottom() 的輸出, 即(e0,e1,··· ,e17), 其輸出即為S 盒的輸出(s0,s1,··· ,s7).

3 SM4 算法子部件的量子實(shí)現(xiàn)

本節(jié)給出SM4 算法子部件的量子實(shí)現(xiàn)構(gòu)造方案.

3.1 SM4 算法線性變換的量子實(shí)現(xiàn)

SM4 算法狀態(tài)位為128 比特, 分為4 個(gè)32 比特長(zhǎng)的字進(jìn)行處理. 算法輪函數(shù)(式(2)) 和密鑰擴(kuò)展算法(式(3)) 包含32 比特的異或, 均可由32 個(gè)CNOT 門并行實(shí)現(xiàn).

合成置換T中的線性變換L可以表示成F2上32×32 的可逆矩陣, 具體如下:

其中,B1,B2,B3分別為:

同理, 密鑰擴(kuò)展算法中的L′變換可以由F2上32×32 的可逆矩陣表示, 具體如下:

其中,E為F2上8×8 的單位矩陣,分別為:

利用LUP 分解實(shí)現(xiàn)算法線性層是目前研究AES 算法量子優(yōu)化實(shí)現(xiàn)時(shí)普遍采用的方法. 然而, 該方法生成的實(shí)現(xiàn)所需異或運(yùn)算較多、電路異或深度較大. 2020 年, Xiang 等人[20]基于矩陣分解理論提出了一套搜索矩陣優(yōu)化實(shí)現(xiàn)的啟發(fā)式算法, 該算法同樣能在不額外引入新變量的前提下搜索F2上二元矩陣的優(yōu)化實(shí)現(xiàn). 上述兩種實(shí)現(xiàn)方法均生成矩陣的in-place 實(shí)現(xiàn), 從而可借助CNOT 門模擬異或操作將利用上述方法得到的經(jīng)典實(shí)現(xiàn)轉(zhuǎn)換為量子實(shí)現(xiàn). 與LUP 分解給出的實(shí)現(xiàn)相比, 通過文獻(xiàn)[20] 中的算法獲得的實(shí)現(xiàn)在異或門電路數(shù)以及電路深度方面具有一定優(yōu)勢(shì). 因此, 本文采用文獻(xiàn)[20] 中提出的算法實(shí)現(xiàn)SM4 算法的線性子部件(包括線性變換L和L′), 其中線性變換L對(duì)應(yīng)矩陣的實(shí)現(xiàn)消耗83 個(gè)異或門電路, 電路深度為6, 線性變換L′對(duì)應(yīng)矩陣的實(shí)現(xiàn)消耗78 個(gè)異或門電路, 電路深度為7. 線性變換L和L′的具體實(shí)現(xiàn)見附錄中表4 和表5.

3.2 SM4 算法S 盒的量子實(shí)現(xiàn)

本節(jié)給出SM4 算法S 盒的量子實(shí)現(xiàn)方案:|x〉|b〉|0a-8〉 →|x〉|b ⊕S(x)〉|0a-8〉, 其中x,b,S(x)∈F28.

由本文第2.3.3 節(jié)所示SM4 算法S 盒的經(jīng)典實(shí)現(xiàn)可知, 不同函數(shù)的輸入輸出之間存在一定的聯(lián)系, 如函數(shù)Output() 建立了算法S 盒的輸出(s0,s1,··· ,s7) 與變量y0,y1,··· ,y17以及變量l0,l1,l2,l3之間的關(guān)系. 上述變量分別是函數(shù)Input() 和函數(shù)Middle() 的輸出. 函數(shù)Middle() 通過函數(shù)Top() 建立了變量y0,y1,··· ,y17與其輸出l0,l1,l2,l3之間的聯(lián)系. 因此, 本節(jié)將根據(jù)第2.3.3 節(jié)所示經(jīng)典實(shí)現(xiàn)中函數(shù)之間的關(guān)系探討SM4 算法S 盒的量子優(yōu)化實(shí)現(xiàn).

首先, 對(duì)于S 盒實(shí)現(xiàn)中的第一層線性部分, 即函數(shù)Input(), 注意到, 其輸出y0,y1,··· ,y17同時(shí)為S 盒的第一層非線性部分(函數(shù)Top()) 和第三層非線性部分(函數(shù)Bottom()) 的輸入. 并且,yi(i ∈{0,1,··· ,17}) 在上述兩個(gè)函數(shù)中以一定的順序被調(diào)用. 從節(jié)約量子邏輯門數(shù)量的角度考慮, 借助18 個(gè)量子輔助比特存儲(chǔ)y0,y1,··· ,y17有利于減少量子電路中CNOT 門的數(shù)量. 然而, 這種實(shí)現(xiàn)方式會(huì)增加量子電路中量子比特的開銷. 因此, 本文采用一種鏈?zhǔn)降姆绞接?jì)算兩個(gè)非線性函數(shù)所需的y0,y1,··· ,y17,將函數(shù)Input() 的實(shí)現(xiàn)內(nèi)嵌于函數(shù)Top() 和函數(shù)Bottom() 的實(shí)現(xiàn)之中. 具體思路為, 按照函數(shù)Top()和函數(shù)Bottom() 調(diào)用yi的順序, 以S 盒的輸入(x0,x1,··· ,x7) 為目標(biāo)比特, 依次計(jì)算yi的自更新實(shí)現(xiàn), 其中i ∈{0,1,··· ,17}. 需要注意的是, 計(jì)算函數(shù)Top() 中調(diào)用的yi時(shí),xj的初值為S 盒的輸入,其中i ∈{0,1,··· ,17},j ∈{0,1,··· ,7}. 而在計(jì)算函數(shù)Bottom() 中調(diào)用的yi(i ∈{0,1,··· ,17}) 時(shí),xj(j ∈{0,1,··· ,7}) 的初值已不再為S 盒的輸入, 而是等于經(jīng)過函數(shù)Top() 后被更新的值.

而對(duì)于S 盒實(shí)現(xiàn)中的第二層線性部分, 即函數(shù)Output(), 其輸入為函數(shù)Bottom() 的輸出. 如本文第2.3.3 節(jié)所示, 函數(shù)Bottom() 的各輸出之間并無相互影響, 且函數(shù)Bottom() 對(duì)其輸出ei(i ∈{0,1,··· ,17}) 的計(jì)算順序沒有要求, 這意味著在函數(shù)Output() 初次調(diào)用具體的ei(i ∈{0,1,··· ,17})時(shí), 函數(shù)Bottom() 能及時(shí)提供該參數(shù)即可確保函數(shù)Output() 正確計(jì)算S 盒的輸出. 而函數(shù)Output()作為線性函數(shù), 可由F2上的二元矩陣表示, 一旦獲得該矩陣的自更新實(shí)現(xiàn), 即可根據(jù)該實(shí)現(xiàn)中最初調(diào)用ei的順序利用函數(shù)Bottom() 計(jì)算ei, 將函數(shù)Bottom() 與函數(shù)Output() 同步實(shí)現(xiàn), 最終生成S 盒的輸出, 其中i ∈{0,1,··· ,17}. 因此, 本文首先設(shè)計(jì)函數(shù)Output() 的優(yōu)化實(shí)現(xiàn), 接著在此基礎(chǔ)之上實(shí)現(xiàn)函數(shù)Bottom(), 以此將后者的實(shí)現(xiàn)內(nèi)嵌于前者的實(shí)現(xiàn)之中.

根據(jù)上述分析, 本節(jié)分三步探討SM4 算法S 盒的量子實(shí)現(xiàn)方案: 首先設(shè)計(jì)計(jì)算p0,p1,p2,p3的量子電路, 接著研究生成l0,l1,l2,l3的量子電路, 最后基于上述實(shí)現(xiàn)設(shè)計(jì)S 盒的量子實(shí)現(xiàn)方案.

算法1 給出了利用本文第2.3.3 節(jié)所示函數(shù)Top() 計(jì)算p0,p1,p2,p3的量子實(shí)現(xiàn)方案, 該方案包含了函數(shù)Input() 的實(shí)現(xiàn). 算法1 對(duì)應(yīng)的量子實(shí)現(xiàn)資源消耗為: 13 個(gè)Toffoli 門, 136 個(gè)CNOT 門以及23 個(gè)X 門, Toffoli 深度為10.

算法1 共使用5 個(gè)輔助比特, 其中4 個(gè)用于存儲(chǔ)其輸出, 即p0,p1,p2,p3(分別存儲(chǔ)于T0,T1,T2,T3).由經(jīng)典實(shí)現(xiàn)可知, 利用算法1 的輸出基于函數(shù)Middle() 可以計(jì)算l0,l1,l2,l3, 算法2 給出了該計(jì)算過程的具體實(shí)現(xiàn)方案, 其對(duì)應(yīng)量子實(shí)現(xiàn)的資源消耗為: 11 個(gè)Toffoli 門, 25 個(gè)CNOT 門以及10 個(gè)X 門, Toffoli深度為8.

算法2 共消耗9 個(gè)輔助比特, 其輸出l0,l1,l2,l3分別存儲(chǔ)于p3,T8,T6,p0, 其中T6和T8為輔助比特,p0和p3為算法1 的輸出比特. 需要注意的是, 經(jīng)過算法2 第9 步, 輔助比特T2被初始化為零, 在后面的實(shí)現(xiàn)中, 該比特可以繼續(xù)作為輔助比特使用.

在生成算法2 的輸出后, 即可利用經(jīng)典實(shí)現(xiàn)中的函數(shù)Bottom() 和函數(shù)Output() 計(jì)算SM4 算法S盒的輸出. 由本節(jié)的分析可知, 實(shí)現(xiàn)函數(shù)Bottom() 和函數(shù)Output() 的關(guān)鍵在于找到函數(shù)Output() 對(duì)應(yīng)矩陣的自更新實(shí)現(xiàn), 該矩陣如下所示:上述矩陣為行滿秩矩陣, 這意味著通過添加單位向量即可將其擴(kuò)展為可逆方陣, 接著利用基于矩陣分解理論的啟發(fā)式算法[20]搜索其自更新實(shí)現(xiàn), 繼而設(shè)計(jì)函數(shù)Bottom() 的優(yōu)化實(shí)現(xiàn)并最終實(shí)現(xiàn)算法S 盒.

算法1 利用5 個(gè)輔助比特計(jì)算p0,p1,p2,p3 Input: S 盒的輸入(x0,x1,··· ,x7); 量子輔助比特Ti = 0,i = 0,1,··· ,4.Output: T0 = p0,T1 = p1,T2 = p2,T3 = p3, T4 待重置; xi = xi,i ∈{0,1,··· ,7}.1 x4 = x4 ⊕x2 ⊕x7;2 x6 = x6 ⊕x2 ⊕x7;3 x7 =x7;x2 ⊕x6;31 x3 = x3 ⊕x0 ⊕x6 ⊕x7;32 x1 = x1 ⊕x5 ⊕x6;33 x5 =30 x2 =T0 ⊕(x4 ·x7);5 x7 =x7;4 T0 =6 x2 = x2 ⊕x0 ⊕x3;7 T3 =x5 ⊕x3 ⊕x4;34 T2 = T2 ⊕(x2 ·x3);35 x2 =T3 ⊕(x2 ·x6);8 x2 = x2 ⊕x0 ⊕x3;9 x6 = x6 ⊕x2 ⊕x7;10 x3 =x2 ⊕x6;36 T0 = T0 ⊕T1 ⊕T3 ⊕T4;37 T1 = T1 ⊕(x1 ·x5)⊕x1 ⊕x5;38 x5 =x3 ⊕x4 ⊕x5 ⊕x7;11 x4 = x4 ⊕x6;12 T1 =x5 ⊕x3 ⊕x4;39 x3 = x3 ⊕x0 ⊕x6 ⊕x7;40 x2 =T1 ⊕(x3 ·x4);13 x3 = x3 ⊕x0 ⊕x2 ⊕x4 ⊕x7;14 x1 =x1 ⊕x3;15 T2 = T2 ⊕(x1 ·x3);16 x1 =x1 ⊕x3;17 x3 =x2 ⊕x0 ⊕x6;41 x1 = x1 ⊕x6;42 T1 = T1 ⊕(x1 ·x2);43 x1 = x1 ⊕x5;44 x2 = x2 ⊕x0;45 T1 =x3 ⊕x0 ⊕x2 ⊕x5 ⊕x6;18 x4 = x4 ⊕x2 ⊕x6 ⊕x7;19 x0 = x0 ⊕x4 ⊕x6;20 x5 = x5 ⊕x0 ⊕x1 ⊕x3 ⊕x6 ⊕x7;21 T4 =T1 ⊕T2 ⊕T3 ⊕x3 ⊕x5 ⊕x6 ⊕x7;46 T3 = T3 ⊕T2 ⊕T4;47 x7 = x7 ⊕x0 ⊕x3 ⊕x6;48 T2 = T2 ⊕(x2 ·x7);49 x2 =T4 ⊕(x0 ·x5)⊕x0 ⊕x5;22 x5 = x5 ⊕x0 ⊕x1 ⊕x2 ⊕x4 ⊕x6;23 T0 = T0 ⊕(x5 ·x6)⊕x5 ⊕x6;24 x6 =x2 ⊕x6;50 x0 = x0 ⊕x4 ⊕x6;51 x7 = x7 ⊕x0 ⊕x2 ⊕x5;52 x2 =x6 ⊕x0 ⊕x2 ⊕x5;25 x7 =x7 ⊕x0 ⊕x1 ⊕x3 ⊕x4 ⊕x6;26 T0 = T0 ⊕(x6 ·x7);27 x7 =x7 ⊕x0 ⊕x1 ⊕x3 ⊕x4 ⊕x6;28 x6 =x6 ⊕x0 ⊕x2 ⊕x5;29 x5 = x5 ⊕x2 ⊕x3 ⊕x4 ⊕x7;x2 ⊕x0 ⊕x4 ⊕x7;53 x5 = x5 ⊕x1 ⊕x6;54 T4 = T4 ⊕T0 ⊕x1 ⊕(x2 ·x5);55 T2 = T2 ⊕T4 ⊕(x6 ·x7)⊕x6 ⊕x7;56 x5 = x5 ⊕x1 ⊕x6;57 x2 =x2 ⊕x0 ⊕x4 ⊕x7;58 x7 = x7 ⊕x2 ⊕x3 ⊕x4 ⊕x5;

?算法2 利用9 個(gè)輔助比特計(jì)算l0,l1,l2,l3 Input: 算法1 的輸出p0,p1,p2,p3; 量子輔助比特Ti = 0,i = 0,1,··· ,8.Output: Ti 待重置, 其中i = 0,1,3,4,5,7; T2 = 0,p3 = l0,T8 = l1,T6 = l2,p0 = l3.1 T0 =T0 ⊕(p0 ·p3);2 T1 =T4 ⊕(p2 ·T2);9 T2 =8 T4 =T1 ⊕(T0 ·p1)⊕T0 ⊕p1;3 T0 = T0 ⊕T1 ⊕p1;4 T2 =T2 ⊕p2 ⊕(p1 ·p3);5 T5 =T2 ⊕p2 ⊕(p1 ·p3);10 T3 = T3 ⊕T5;11 T6 =T5 ⊕(p0 ·T2)⊕p0 ⊕T2;6 T7 =T6 ⊕(T0 ·T3);12 p0 =T7 ⊕(T1 ·T5)⊕T1 ⊕T5;7 T3 = T3 ⊕(p1 ·T2)⊕p1 ⊕T2;p0 ⊕T3;13 T8 =T8 ⊕(T4 ·T7);14 p3 = p3 ⊕(T7 ·p2);

接下來介紹S 盒的實(shí)現(xiàn)方案|x〉|b〉|014〉 →|x〉|b ⊕S(x)〉|014〉. 為了減少量子比特開銷, 本節(jié)采用文獻(xiàn)[10] 中的方法, 將兩個(gè)量子比特經(jīng)過Toffoli 門后的狀態(tài)保存于新引入的量子比特Z中, 并將之借助CNOT 門異或到所有需要Z中存儲(chǔ)值的S 盒相應(yīng)比特之中, 接著將Z的值置零用于保存下一組中間值,具體實(shí)現(xiàn)如算法3 所示.

算法3 需調(diào)用兩次算法1 和算法2, 并且算法3 需額外借助1 個(gè)輔助比特Z. 通過初始化算法2 中的輔助比特T2(對(duì)應(yīng)算法2 中第9 步) 并將之作為Z輸入算法3 即可計(jì)算S 盒的輸出. 該實(shí)現(xiàn)方案共使用14個(gè)量子輔助比特, 消耗510 個(gè)CNOT 門, 82 個(gè)Toffoli 門, 87 個(gè)X 門, Toffoli 深度為68.

4 SM4 算法的量子實(shí)現(xiàn)

本節(jié)介紹本文針對(duì)SM4 算法密鑰擴(kuò)展算法和輪函數(shù)設(shè)計(jì)的優(yōu)化實(shí)現(xiàn)方案.

4.1 SM4 算法密鑰擴(kuò)展算法的量子實(shí)現(xiàn)

根據(jù)公式(3)可知, SM4 算法輪子密鑰具體由下列方式生成:

根據(jù)密鑰擴(kuò)展算法的更新方式, 圖3 所示電路a 給出了生成輪子密鑰rki的量子實(shí)現(xiàn)方案. 在經(jīng)過τ變換時(shí), 該實(shí)現(xiàn)方案對(duì)于每一個(gè)S 盒均需引入8 個(gè)量子比特存儲(chǔ)其輸出. 因此, 假設(shè)并行處理4 個(gè)S 盒,圖3 所示電路a 需使用14×4+32×5=216 個(gè)量子比特計(jì)算rki. 值得注意的是, 為了節(jié)約量子比特, 在生成當(dāng)前輪輪子密鑰rki后, 32 個(gè)量子輔助比特需重置, 即對(duì)L′變換后的狀態(tài)經(jīng)過逆T′變換, 這使得電路消耗的Toffoli 門數(shù)量和Toffoli 深度翻倍.

對(duì)公式(4)的進(jìn)一步研究我們可以發(fā)現(xiàn), 當(dāng)前輪子密鑰只與緊隨其后的四輪輪子密鑰的生成有關(guān). 以K4為例,K5,K6,K7,K8的生成均與K4有關(guān). 從K9開始, 輪子密鑰的生成便與K4無關(guān), 這意味著可以將保存K4的量子比特用于生成或保存其他輪子密鑰. 同時(shí), 由K8的生成方式可知, 置換T′的輸出值直接異或到K4用于生成第5 輪輪子密鑰. 因此, SM4 算法所有輪子密鑰均可以不借助其他存儲(chǔ)比特在保存種子密鑰的128 個(gè)量子比特上進(jìn)行更新獲得.

算法3 計(jì)算輸出比特初始值不受限時(shí)的S 盒Input: 經(jīng)過算法1 自更新后的xi,i = 0,1,··· ,7; 算法2 的輸出l0,l1,l2,l3; 量子輔助比特Z = 0.Output: s0,s1,s2,s3,s4,s5,s6,s7.1 x2 =x2 ⊕x3 ⊕x4 ⊕x5;2 Z =Z ⊕(x2 ·l2);3 s2 = s2 ⊕Z;4 s5 = s5 ⊕Z;5 s7 = s7 ⊕Z;6 Z =95 s4 = s4 ⊕Z;96 s6 = s6 ⊕Z;97 Z = Z ⊕(x1 ·l2);98 x1 =x1 ⊕x0;99 x0 =Z ⊕(x2 ·l2);7 x2 =x2 ⊕x3 ⊕x4 ⊕x5;8 x4 = x4 ⊕x2 ⊕x6 ⊕x7;9 Z = Z ⊕(x4 ·l2);10 s0 = s0 ⊕Z;11 s1 = s1 ⊕Z;12 s3 = s3 ⊕Z;13 s4 =48 Z = Z ⊕(x7 ·l0);49 s1 = s1 ⊕Z;50 s2 = s2 ⊕Z;51 s5 = s5 ⊕Z;52 s6 = s6 ⊕Z;53 Z = Z ⊕(x7 ·l0);54 x7 = x7 ⊕x0 ⊕x3 ⊕x4;55 x6 =s4 ⊕Z;14 s6 = s6 ⊕Z;15 s7 = s7 ⊕Z;16 Z = Z ⊕(x4 ·l2);17 x4 = x4 ⊕x2 ⊕x6 ⊕x7;18 x0 = x0⊕x1⊕x3⊕x4⊕x5⊕x7;19 Z =x6 ⊕x2;56 Z = Z ⊕(x6 ·l0);57 s1 = s1 ⊕Z;58 s3 = s3 ⊕Z;59 s6 = s6 ⊕Z;60 s7 = s7 ⊕Z;61 Z = Z ⊕(x6 ·l0);62 x6 =x6 ⊕x2;63 l0 = l0 ⊕l1;64 x0 = x0 ⊕x2 ⊕x3;65 s0 =x0⊕x2⊕x3⊕x5⊕x6;100 l2 = l2 ⊕l1 ⊕l0;101 x5 = x5 ⊕x1 ⊕x6;102 Z = Z ⊕(x5 ·l2);103 s1 = s1 ⊕Z;104 s2 = s2 ⊕Z;105 s3 = s3 ⊕Z;106 s5 = s5 ⊕Z;107 s6 = s6 ⊕Z;108 s7 = s7 ⊕Z;109 Z = Z ⊕(x5 ·l2);110 x5 = x5 ⊕x1 ⊕x6;111 x3 =Z ⊕(x0 ·l3);20 s3 = s3 ⊕Z;21 s7 = s7 ⊕Z;22 Z = Z ⊕(x0 ·l3);23 x0 = x0⊕x1⊕x3⊕x4⊕x5⊕x7;24 x6 = x6 ⊕x0 ⊕x4;25 Z = Z ⊕(x6 ·l3);26 s1 = s1 ⊕Z;27 s2 = s2 ⊕Z;28 Z = Z ⊕(x6 ·l3);29 x6 = x6 ⊕x0 ⊕x4;30 x7 =x7;x3 ⊕x0 ⊕x5 ⊕x7;112 Z = Z ⊕(x3 ·l2);113 s2 = s2 ⊕Z;114 s3 = s3 ⊕Z;115 s6 = s6 ⊕Z;116 s7 = s7 ⊕Z;117 Z = Z ⊕(x3 ·l2);118 x3 =31 Z = Z ⊕(x7 ·l1);32 s1 = s1 ⊕Z;33 s3 = s3 ⊕Z;34 s5 = s5 ⊕Z;35 s6 = s6 ⊕Z;36 Z = Z ⊕(x7 ·l1);37 x7 =x7;s0 ⊕(x0 ·l0);66 x0 = x0 ⊕x2 ⊕x3;67 x2 = x2 ⊕x6 ⊕x7;68 Z = Z ⊕(x2 ·l0);69 s5 = s5 ⊕Z;70 s7 = s7 ⊕Z;71 Z = Z ⊕(x2 ·l0);72 x2 = x2 ⊕x6 ⊕x7;73 l0 = l0 ⊕l1;74 l1 = l1 ⊕l2;75 Z = Z ⊕(x6 ·l1);76 s1 = s1 ⊕Z;77 s4 = s4 ⊕Z;78 s6 = s6 ⊕Z;79 Z = Z ⊕(x6 ·l1);80 x5 = x5 ⊕x2 ⊕x3 ⊕x4 ⊕x7;81 s1 =x3 ⊕x0 ⊕x5 ⊕x7;119 l2 = l2 ⊕l3 ⊕l1 ⊕l0;120 l3 = l3 ⊕l0;121 x1 = x1 ⊕x5;122 Z = Z ⊕(x1 ·l3);123 s2 = s2 ⊕Z;124 s3 = s3 ⊕Z;125 s4 = s4 ⊕Z;126 s5 = s5 ⊕Z;127 s7 = s7 ⊕Z;128 Z = Z ⊕(x1 ·l3);129 x1 = x1 ⊕x5;130 x0 =38 x2 = x2 ⊕x4 ⊕x7;39 Z = Z ⊕(x2 ·l1);40 s0 = s0 ⊕Z;41 s1 = s1 ⊕Z;42 s2 = s2 ⊕Z;43 s5 = s5 ⊕Z;44 s6 = s6 ⊕Z;45 Z = Z ⊕(x2 ·l1);46 x2 = x2 ⊕x4 ⊕x7;47 x7 = x7 ⊕x0 ⊕x3 ⊕x4;s1 ⊕(x5 ·l1);82 x5 = x5 ⊕x2 ⊕x3 ⊕x4 ⊕x7;83 l1 = l1 ⊕l2;84 l2 = l2 ⊕l3;85 x0 =x0 ⊕x2 ⊕x3 ⊕x5 ⊕x6;86 Z = Z ⊕(x0 ·l2);87 s1 = s1 ⊕Z;88 s5 = s5 ⊕Z;89 s7 = s7 ⊕Z;90 Z = Z ⊕(x0 ·l2);91 x1 =x0 ⊕x2 ⊕x4;131 Z = Z ⊕(x0 ·l3);132 s1 = s1 ⊕Z;133 s2 = s2 ⊕Z;134 s3 = s3 ⊕Z;135 s6 = s6 ⊕Z;136 s7 = s7 ⊕Z;137 Z =x1 ⊕x0;92 Z = Z ⊕(x1 ·l2);93 s0 = s0 ⊕Z;94 s1 = s1 ⊕Z;Z ⊕(x0 ·l3);138 x0 =x0 ⊕x2 ⊕x4;139 l3 = l3 ⊕l0;140 運(yùn)行算法1–2 重置輔助比特;

圖3 輪子密鑰rki 的生成Figure 3 Generation of subkey rki

下面介紹一種優(yōu)化的生成輪子密鑰rki的量子電路結(jié)構(gòu), 如圖3 電路b 所示實(shí)現(xiàn)方案.

其中L′-1為L(zhǎng)′的逆變換.

根據(jù)上述分析, 同時(shí)考慮到輪子密鑰的特殊性(一方面, 輪子密鑰需輸入算法輪函數(shù)用于更新狀態(tài); 另一方面, 作為計(jì)算下一輪輪子密鑰的參數(shù)其值需繼續(xù)保留.), 本節(jié)利用算法3 設(shè)計(jì)了如圖4 所示SM4 算法密鑰擴(kuò)展算法的量子實(shí)現(xiàn)方案.

值得注意的是, 圖4 并未顯示實(shí)現(xiàn)S 盒所需的量子輔助比特. 同時(shí), 將給定參數(shù)異或到狀態(tài)位中, 等價(jià)于將狀態(tài)位中與固定參數(shù)中值為1 的比特對(duì)應(yīng)的比特位取反. SM4 算法的給定參數(shù)中, 輪常量的漢明重量為503, 系統(tǒng)參數(shù)的漢明重量為64, 即使用503+64 = 567 個(gè)X 門即可完成異或輪常數(shù)和系統(tǒng)參數(shù).圖4 所示SM4 算法密鑰擴(kuò)展算法量子實(shí)現(xiàn)的資源開銷分析如下:

圖4 共消耗128 個(gè)基于32 比特的異或, 32 個(gè)τ變換, 每一個(gè)τ變換包含4 個(gè)S 盒. 此外, 該實(shí)現(xiàn)使用32 次逆線性變換, 由于量子電路要求可逆, 線性變換及其逆變換的量子實(shí)現(xiàn)代價(jià)相等. 考慮到量子比特?cái)?shù)和電路深度對(duì)指標(biāo)depth-times-width 值的影響, S 盒又是影響量子電路所需量子輔助比特和電路深度的主要組件, 因此τ變換中S 盒的實(shí)現(xiàn)方式直接關(guān)系著量子電路的整體表現(xiàn). 綜上所述, 假設(shè)一次τ變換中, 并行處理的S 盒數(shù)量為i(i ∈{1,2,4}), 圖4 所示實(shí)現(xiàn)方案共需要128+14×i個(gè)量子比特,(82×4)×32 = 10496 個(gè)Toffoli 門, (510×4)×32+128×32+78×2×32 = 74368 個(gè)CNOT 門,87×4×32+1070=12206 個(gè)X 門, Toffoli 深度為(68×(4/i))×32, 其中i ∈{1,2,4}.

圖4 SM4 算法密鑰擴(kuò)展算法的實(shí)現(xiàn)Figure 4 Implementation of key expansion of SM4

4.2 SM4 算法整體實(shí)現(xiàn)結(jié)構(gòu)

由公式(2)可知, SM4 算法輪函數(shù)的展開與其密鑰擴(kuò)展算法類似, 因此, 本文利用算法3 設(shè)計(jì)了如圖5 所示SM4 算法輪函數(shù)的實(shí)現(xiàn)方案.

圖5 SM4 算法輪函數(shù)的實(shí)現(xiàn)Figure 5 Implementation of round function of SM4

利用圖5 所示結(jié)構(gòu)更新SM4 算法輪函數(shù)的量子資源開銷分析如下:

基于圖4 的輸出, 即算法輪子密鑰已知的情形下, 圖5 共消耗基于32 比特的異或150 個(gè), 其中32 個(gè)用于異或輪子密鑰, 86 個(gè)用于更新狀態(tài), 32 個(gè)用于消除狀態(tài)位中被異或的輪子密鑰以便進(jìn)行下一輪狀態(tài)更新. 電路還消耗32 個(gè)τ變換, 每一個(gè)τ變換包含4 個(gè)S 盒. 此外, 算法反序函數(shù)共需要64 次基于比特的SWAP 操作, 可由64×3 = 192 個(gè)CNOT 門模擬. 與密鑰擴(kuò)展算法量子實(shí)現(xiàn)方案的分析類似, 假設(shè)一次τ變換中, 并行處理的S 盒數(shù)量為i(i ∈{1,2,4}), 圖5 所示實(shí)現(xiàn)方案共需要128+14×i個(gè)量子比特, (82×4)×32 = 10496 個(gè)Toffoli 門, (510×4)×32+150×32+83×2×32+192 = 75584 個(gè)CNOT 門, 87×4×32=11136 個(gè)X 門, Toffoli 深度為(68×(4/i))×32, 其中i ∈{1,2,4}.

考慮到密鑰擴(kuò)展算法與算法輪函數(shù)之間的關(guān)系, 本文結(jié)合圖4 和圖5 設(shè)計(jì)了SM4 算法量子實(shí)現(xiàn)整體結(jié)構(gòu), 如圖6 所示.

圖6 SM4 算法整體加密結(jié)構(gòu)Figure 6 Whole encrypt sctructure of SM4

圖6 中的虛線將SM4 算法的整體量子實(shí)現(xiàn)分為三個(gè)部分: 第一部分更新密鑰, 生成rk0(K4). 該部分電路僅經(jīng)過一次τ變換, 即包含4 個(gè)S 盒; 第二部分更新密鑰和輪函數(shù). 該部分電路計(jì)算算法第i輪的輸出以及算法第i+1 輪的輪子密鑰, 其中i=1,2,··· ,31. 因此, 圖6 所示電路第二部分每一次更新經(jīng)過兩個(gè)τ變換(如圖6 中虛線框所示), 即包含8 個(gè)S 盒; 第三部分生成密文. 此時(shí)電路僅經(jīng)過一次τ變換, 即包含4 個(gè)S 盒.

由表2 中的結(jié)果可知, 采用本文設(shè)計(jì)的如圖6 所示SM4 算法的量子實(shí)現(xiàn)整體結(jié)構(gòu), 隨著i的取值變大, 即電路并行處理的S 盒數(shù)量增加, 電路所需量子比特?cái)?shù)增加, 電路的depth-times-width 值減小. 與AES-128 的量子實(shí)現(xiàn)相比, 本文針對(duì)SM4 算法設(shè)計(jì)的量子實(shí)現(xiàn)整體結(jié)構(gòu)使用的量子比特?cái)?shù)明顯減少. 這是由于, 一方面, 直接將針對(duì)AES 設(shè)計(jì)的zig-zag 結(jié)構(gòu)運(yùn)用于基于Feistel 結(jié)構(gòu)的密碼算法并不一定是最優(yōu)選擇; 另一方面, 利用本文提出的算法3 對(duì)SM4 算法合成置換T和T′的改進(jìn)實(shí)現(xiàn), 進(jìn)一步減少了量子電路中量子比特的使用數(shù)量.

5 SM4 算法量子窮舉攻擊

本節(jié)基于如圖6 所示整體實(shí)現(xiàn)結(jié)構(gòu)評(píng)估利用Grover 算法搜索SM4 算法密鑰的量子資源開銷.

表2 SM4 算法與AES-128 算法實(shí)現(xiàn)開銷對(duì)比Table 2 Comparison of cost to implement SM4 and AES-128

(1) 制備均勻疊加態(tài)以及|-〉所需的Hadamard 門;

(a)Uf的開銷;

(b) 相位翻轉(zhuǎn)的開銷, 即實(shí)現(xiàn)2|0〉〈0|-1 的代價(jià);

(c) 相位翻轉(zhuǎn)前后所需的Hadamard 門.

針對(duì)分組長(zhǎng)度為128 比特的分組密碼，借助兩對(duì)明密文對(duì)即可確定128 比特密鑰的唯一值，因此，利用Grover 算法對(duì)密鑰長(zhǎng)度為128 比特的分組密碼進(jìn)行量子窮舉攻擊時(shí)所使用的量子電路Uf通常如圖7 所示, 其中Enc 為密碼算法的可逆量子電路, Enc-1為其逆電路.

圖7 函數(shù)Uf 對(duì)應(yīng)的可逆實(shí)現(xiàn)Figure 7 Reversible implementation of Uf

圖7 所示量子電路中, 兩個(gè)“Enc” 并行運(yùn)行, 兩個(gè)“Enc-1” 并行運(yùn)行, 電路Toffoli 深度翻倍. 同時(shí),文獻(xiàn)[6] 指出, 根據(jù)文獻(xiàn)[21] 的研究, 給定兩組明密文對(duì), 經(jīng)過密碼算法可逆電路之后判斷輸出值與密文是否相等需使用8·(128·2)-24 個(gè)Toffoli 門. 而對(duì)于相位翻轉(zhuǎn), 參考文獻(xiàn)[6] 指出, 實(shí)現(xiàn)2|0〉〈0|-1 的量子資源開銷為8·128-24 個(gè)Toffoli 門. 綜上, 結(jié)合圖1和圖7 所示電路對(duì)分組長(zhǎng)度和密鑰長(zhǎng)度均為128比特的分組密碼進(jìn)行量子窮舉攻擊的代價(jià)分析如下:

Toffoli 門的數(shù)量為

其中ΔToffoli為密碼算法的量子實(shí)現(xiàn)電路中消耗的Toffoli 門數(shù).

CNOT 門的數(shù)量為

其中ΔCNOT為密碼算法的量子實(shí)現(xiàn)電路中消耗的CNOT 門數(shù).

X門的數(shù)量為

其中ΔX為密碼算法的量子實(shí)現(xiàn)電路中消耗的X 門數(shù).

Hadamard 門的數(shù)量為

電路Toffoli 深度可參照文獻(xiàn)[6] 近似為

其中ΔDepth為密碼算法量子實(shí)現(xiàn)電路的Toffoli 深度.

電路所需量子比特?cái)?shù)為

其中Δqubit為密碼算法量子實(shí)現(xiàn)電路所需量子比特總數(shù).

SM4 算法與AES-128 均為分組長(zhǎng)度和密鑰長(zhǎng)度等于128 比特的分組密碼, 將表2 所示算法的量子實(shí)現(xiàn)開銷代入公式(6)—(11)即可計(jì)算利用Grover 算法搜索SM4 算法和AES-128 算法密鑰的量子資源開銷, 具體如表3 所示.

表3 SM4 算法與AES-128 算法的量子窮舉攻擊開銷對(duì)比Table 3 Comparison of cost to conduct quantum exhaustive key search for SM4 and AES-128

一方面, 針對(duì)密碼算法的抗量子攻擊安全強(qiáng)度, NIST 定義了五種類別, 分別與對(duì)五種經(jīng)典密碼算法進(jìn)行量子窮舉攻擊所需計(jì)算資源有關(guān)[2]. 以第一類為例, 滿足第一等級(jí)安全強(qiáng)度的密碼算法, 對(duì)其進(jìn)行任意攻擊的計(jì)算資源需與對(duì)AES-128 進(jìn)行密鑰窮搜的計(jì)算資源相當(dāng)或比之更多. 由文獻(xiàn)[2] 可知, 對(duì)密碼算法進(jìn)行量子分析所需的計(jì)算資源可以由經(jīng)典環(huán)境下基本操作的數(shù)目或量子電路的大小等指標(biāo)度量, 而量子電路的大小與該電路所需量子比特?cái)?shù)有關(guān); 另一方面, 文獻(xiàn)[9] 指出, 量子邏輯門的消耗與NIST 定義的抗量子攻擊安全類別相關(guān),但是在考慮量子糾錯(cuò)的情況下,depth-times-width 值是更加實(shí)際的評(píng)估量子資源消耗的指標(biāo). 因此, 我們可以通過利用Grover 算法進(jìn)行密鑰窮搜的電路所消耗的量子比特?cái)?shù)目和該電路的depth-times-width 值合理地比較SM4 算法與AES-128 算法抗量子窮舉攻擊的強(qiáng)度. 如表3 所示, 針對(duì)量子比特?cái)?shù)量, 無論并行S 盒的數(shù)量如何, 利用本文設(shè)計(jì)的SM4 算法量子實(shí)現(xiàn)方案構(gòu)造的量子窮舉攻擊所需量子比特均比對(duì)AES-128 進(jìn)行密鑰窮搜的量子電路所需量子比特少. 此外, 針對(duì)指標(biāo)depth-timeswidth 值, 本文提出了一種并行處理S 盒數(shù)量為8 的SM4 算法量子實(shí)現(xiàn)方案, 利用該實(shí)現(xiàn)方案構(gòu)造的量子窮舉攻擊具有比對(duì)AES-128 的量子窮舉攻擊更低的depth-times-width 值. 雖然比AES-128 更長(zhǎng)的加密輪數(shù)一定程度增加了實(shí)現(xiàn)SM4 算法所需的量子資源, 但是從量子比特?cái)?shù)目和depth-times-width 值兩個(gè)指標(biāo)出發(fā), 本文的研究表明, SM4 算法的抗量子窮舉攻擊強(qiáng)度要弱于AES-128 算法.

6 總結(jié)

本文首先研究了SM4 算法線性層的量子實(shí)現(xiàn), 不同于目前研究分組密碼的量子實(shí)現(xiàn)時(shí)普遍采用LUP分解的方法, 本文利用基于矩陣分解理論的啟發(fā)式算法生成了SM4 算法線性層異或門電路消耗更少、異或深度更小的經(jīng)典實(shí)現(xiàn), 該實(shí)現(xiàn)可通過借助CNOT 門模擬異或操作轉(zhuǎn)換為量子實(shí)現(xiàn); 其次, 從SM4 算法S 盒的經(jīng)典實(shí)現(xiàn)出發(fā), 利用基于矩陣分解理論的啟發(fā)式算法實(shí)現(xiàn)其線性部分, 并在此基礎(chǔ)上構(gòu)造了SM4算法S 盒的量子優(yōu)化實(shí)現(xiàn)方案, 該實(shí)現(xiàn)需借助14 個(gè)量子輔助比特并且對(duì)S 盒的輸出比特初值沒有任何限制條件; 借助本文設(shè)計(jì)的S 盒量子實(shí)現(xiàn)的上述性質(zhì), 同時(shí)考慮到SM4 算法的密碼結(jié)構(gòu)特性, 本文通過添加逆線性變換的方法構(gòu)造了能有效節(jié)約32 個(gè)量子比特的T和T′的量子優(yōu)化實(shí)現(xiàn)方案; 基于上述改進(jìn)實(shí)現(xiàn)方案, 根據(jù)算法輪子密鑰和狀態(tài)更新的特點(diǎn)針對(duì)密鑰擴(kuò)展算法和輪函數(shù)分別設(shè)計(jì)了一種量子優(yōu)化實(shí)現(xiàn)方案; 接著, 探索了適用于基于Feistel 結(jié)構(gòu)密碼算法的量子實(shí)現(xiàn)整體結(jié)構(gòu). 目前對(duì)稱密碼算法量子實(shí)現(xiàn)的研究主要集中在AES 算法上面, 為了減少量子比特開銷, 學(xué)者基于AES 算法SPN 結(jié)構(gòu)提出的zig-zag 結(jié)構(gòu)需要計(jì)算輪函數(shù)的逆. 本文研究表明, 針對(duì)AES 算法設(shè)計(jì)的zig-zag 結(jié)構(gòu)并不適用于實(shí)現(xiàn)基于Feistel結(jié)構(gòu)的密碼算法. 利用Feistel 結(jié)構(gòu)輪函數(shù)輸出異或到其中一個(gè)分支以及本文所設(shè)計(jì)S 盒的量子實(shí)現(xiàn), 本文提出了一種具有較高靈活性、量子比特消耗比直接采用zig-zag 結(jié)構(gòu)少、并且與zig-zag 結(jié)構(gòu)相比無需對(duì)算法整輪求逆以節(jié)約量子比特的SM4 算法量子實(shí)現(xiàn)整體結(jié)構(gòu). 綜合考慮電路所耗量子比特?cái)?shù)和電路Toffoli 深度對(duì)量子電路整體性能的影響, 研究了當(dāng)電路并行處理的S 盒數(shù)量分別為1、2、4、8 時(shí)SM4算法整體實(shí)現(xiàn)方案的量子資源開銷; 最后, 基于本文設(shè)計(jì)的SM4 算法量子實(shí)現(xiàn)整體結(jié)構(gòu), 結(jié)合Grover 算法, 研究了對(duì)SM4 算法進(jìn)行量子窮舉攻擊所需的量子資源開銷, 并且比較了SM4 算法與AES-128 算法抵抗量子窮舉攻擊的安全性強(qiáng)度.