SM4 算法的量子實現*

林 達, 向澤軍, 張若琳, 張莎莎, 曾祥勇

湖北大學數學與統計學學院應用數學湖北省重點實驗室, 武漢 430062

1 引言

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

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

在統計電路的量子資源開銷時, 上述研究主要關注量子比特以及量子邏輯門的使用數量. 近年來, 考慮到量子糾錯碼的應用, 越來越多的研究同時關注了量子電路的另一個評價指標: depth-times-width 值,即量子電路中量子比特數與電路深度之積[9,10]. 2020 年, Jaques 等人[9]以AES 和LowMC[12]為例研究了在電路深度受限情形下進行量子密鑰搜索攻擊的代價. 在ASIACRYPT 2020 上, Zou 等人[10]提出了一種改進的zig-zag 結構, 該結構基于對S 盒代數結構及其經典實現的進一步研究, 優化了AES 算法量子實現電路消耗的量子比特數目以及電路的depth-times-width 值.

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

1.1 本文貢獻

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

1.2 本文組織結構

第2 節引入本文所使用的符號, 并簡要介紹Grover 算法和SM4 算法等預備知識. 第3 節給出SM4算法不同子部件的量子實現方案. 第4 節針對SM4 算法的密鑰擴展算法和輪函數設計了相應的量子電路.第5 節介紹利用本文設計的SM4 量子實現方案進行量子密鑰窮舉的量子電路, 并評估該攻擊的量子資源開銷. 第6 節對本文的工作進行總結.

2 預備知識

本章介紹本文使用的符號、Grover 搜索算法以及SM4 算法及其S 盒的經典實現等背景知識.

2.1 符號說明

2.2 Grover 算法

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

圖1 Grover 算法Figure 1 Grover algorithm

由文獻[19] 式6.6 可知, 上式可以寫為:

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

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

(b) 應用H?n.

(c) 相位翻轉.

(d) 應用H?n.

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

2.3 SM4 算法

SM4 算法分組長度與密鑰長度均為128 比特, 采用32 輪非線性迭代結構, 其整體結構如圖2 所示.

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

2.3.1 輪函數

2.3.2 密鑰擴展算法

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

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

2.3.3 SM4 算法S 盒的經典實現

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

表1 SM4 算法S 盒的硬件實現開銷Table 1 Hardware cost to implement S-box of SM4

文獻[17] 利用塔域分解技術以節約硬件面積為出發點研究了AES 類算法S 盒的優化實現, 并給出了SM4 算法S 盒的硬件實現方案(見文獻[17] 附錄C). 該方法將SM4 算法S 盒的實現分解為5 個部分,分別由以下5 個函數表示.

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

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

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

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

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

3 SM4 算法子部件的量子實現

本節給出SM4 算法子部件的量子實現構造方案.

3.1 SM4 算法線性變換的量子實現

SM4 算法狀態位為128 比特, 分為4 個32 比特長的字進行處理. 算法輪函數(式(2)) 和密鑰擴展算法(式(3)) 包含32 比特的異或, 均可由32 個CNOT 門并行實現.

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

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

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

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

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

3.2 SM4 算法S 盒的量子實現

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

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

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

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

根據上述分析, 本節分三步探討SM4 算法S 盒的量子實現方案: 首先設計計算p0,p1,p2,p3的量子電路, 接著研究生成l0,l1,l2,l3的量子電路, 最后基于上述實現設計S 盒的量子實現方案.

算法1 給出了利用本文第2.3.3 節所示函數Top() 計算p0,p1,p2,p3的量子實現方案, 該方案包含了函數Input() 的實現. 算法1 對應的量子實現資源消耗為: 13 個Toffoli 門, 136 個CNOT 門以及23 個X 門, Toffoli 深度為10.

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

算法2 共消耗9 個輔助比特, 其輸出l0,l1,l2,l3分別存儲于p3,T8,T6,p0, 其中T6和T8為輔助比特,p0和p3為算法1 的輸出比特. 需要注意的是, 經過算法2 第9 步, 輔助比特T2被初始化為零, 在后面的實現中, 該比特可以繼續作為輔助比特使用.

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

算法1 利用5 個輔助比特計算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 個輔助比特計算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 盒的實現方案|x〉|b〉|014〉 →|x〉|b ⊕S(x)〉|014〉. 為了減少量子比特開銷, 本節采用文獻[10] 中的方法, 將兩個量子比特經過Toffoli 門后的狀態保存于新引入的量子比特Z中, 并將之借助CNOT 門異或到所有需要Z中存儲值的S 盒相應比特之中, 接著將Z的值置零用于保存下一組中間值,具體實現如算法3 所示.

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

4 SM4 算法的量子實現

本節介紹本文針對SM4 算法密鑰擴展算法和輪函數設計的優化實現方案.

4.1 SM4 算法密鑰擴展算法的量子實現

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

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

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

算法3 計算輸出比特初始值不受限時的S 盒Input: 經過算法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 運行算法1–2 重置輔助比特;

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

下面介紹一種優化的生成輪子密鑰rki的量子電路結構, 如圖3 電路b 所示實現方案.

其中L′-1為L′的逆變換.

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

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

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

圖4 SM4 算法密鑰擴展算法的實現Figure 4 Implementation of key expansion of SM4

4.2 SM4 算法整體實現結構

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

圖5 SM4 算法輪函數的實現Figure 5 Implementation of round function of SM4

利用圖5 所示結構更新SM4 算法輪函數的量子資源開銷分析如下:

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

考慮到密鑰擴展算法與算法輪函數之間的關系, 本文結合圖4 和圖5 設計了SM4 算法量子實現整體結構, 如圖6 所示.

圖6 SM4 算法整體加密結構Figure 6 Whole encrypt sctructure of SM4

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

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

5 SM4 算法量子窮舉攻擊

本節基于如圖6 所示整體實現結構評估利用Grover 算法搜索SM4 算法密鑰的量子資源開銷.

表2 SM4 算法與AES-128 算法實現開銷對比Table 2 Comparison of cost to implement SM4 and AES-128

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

(a)Uf的開銷;

(b) 相位翻轉的開銷, 即實現2|0〉〈0|-1 的代價;

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

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

圖7 函數Uf 對應的可逆實現Figure 7 Reversible implementation of Uf

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

Toffoli 門的數量為

其中ΔToffoli為密碼算法的量子實現電路中消耗的Toffoli 門數.

CNOT 門的數量為

其中ΔCNOT為密碼算法的量子實現電路中消耗的CNOT 門數.

X門的數量為

其中ΔX為密碼算法的量子實現電路中消耗的X 門數.

Hadamard 門的數量為

電路Toffoli 深度可參照文獻[6] 近似為

其中ΔDepth為密碼算法量子實現電路的Toffoli 深度.

電路所需量子比特數為

其中Δqubit為密碼算法量子實現電路所需量子比特總數.

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

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

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

6 總結

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