熊家琪 劉 昂 黃雅婷

北京電子科技學院，北京市 100070

引言

在量子計算機的出現預期下，量子算法應運而生。 量子算法基于量子態(tài)的相干性和疊加性可實現并行計算，量子計算機使得量子算法實現強大的并行計算能力成為可能，這種強大的計算能力可以解決以往經典計算機很難解決或不能解決的問題。 由此催生了新的密碼分析方法，量子算法開始進入現代密碼分析領域[1]。

對當前密碼學領域影響較大的量子算法主要有Shor，Simon，Grover 算法及其優(yōu)化和衍生算法。 Shor 算法對公鑰密碼體制影響深遠，而Simon 和Grover 算法則主要影響對稱密碼體制。

1994 年，Shor 提出了以其本人姓名命名的量子算法--Shor 算法[2]。 Shor 算法可在多項式時間內求解因子分解問題和離散對數問題。 它攻破了RSA 和Diffie-Hellman 公鑰密碼系統，這一發(fā)現震撼了公鑰密碼領域，后量子密碼研究也隨之產生，NIST 于2016 年開始公開征集后量子公鑰算法。 近年來，后量子密碼成為密碼學的熱點研究問題。

同年，Simon 也提出一個量子算法--Simon量子算法[3]，主要用于解決特定函數的周期求解問題。 與經典算法相比，在查詢復雜度上，Simon 算法可以實現指數加速，可將求解函數周期的復雜度由O(nn/2) 次經典查詢降低至O(n)次量子查詢。 它對包括Feistel 結構在內的分組密碼構成威脅[1]。

1996 年，Grover 提出了Grover 量子算法[4]。Grover 算法具有加速暴力搜索的特性，從n 個無序數據中搜索1 個特定目標條目，將查詢復雜度從經典的O(n) 降到O(n1/2)， 實現平方加速。研究發(fā)現，使用Grover 算法進行密鑰窮舉攻擊時，其效果相當于將分組密碼的密鑰長度減少一半。 只要將分組密碼的密鑰長度增加一倍，就可獲得同樣的安全強度。

這些量子算法的提出對現代密碼體制的安全性構成嚴重威脅，吸引了全世界眾多的密碼學者加入到后量子密碼學的研究中來。 本文將重點研究Simon 量子算法在對稱密碼分析中的應用。

1 Simon 算法簡介

1.1 Simon 問題

給定周期函數f:{ 0 ，1}n→ { 0 ，1}n，假設存在唯一的周期s ∈ { 0 ，1}n＼ { 0}n使得f ( x) =f ( x ⊕s) ，x ∈ { 0 ，1}n，求解s。

注意:此處周期不同于常規(guī)周期原像的加法運算的關系，而是異或運算的關系。 因異或關系滿足x，x ⊕s，x ⊕s ⊕s=x，x ⊕s ⊕s ⊕s=x ⊕s，…，故此處一個函數值f(x) 僅對應兩個原像x和x ⊕s，值域是定義域的一半。

1.2 Simon 算法

給定一個布爾函數， f: { 0 ，1}n→ { 0 ，1}n，可以求出一個長度為n 比特的異或周期s，使得這個函數在周期s 下保持不變。 換句話說，存在一個s ∈ { 0 ，1}n， 使 得f ( x) = f ( y) x ⊕y ∈{0n，s} 成立。

在經典計算中，求解s 所需的計算復雜度為O(n1/2)，然而，Simon 提出的Simon 量子算法提供指數加速，在量子計算模型下只需要O(n) 次量子查詢就可以找到s。 Simon 算法的量子電路如圖1 所示。

圖1 Simon 量子算法

其中⊕表示按位的模2 加。

Simon 量子算法工作步驟如下:

a) 將兩個n 位量子寄存器狀態(tài)初始化為| 0〉?n| 0〉?n。 然后將Hadamard 變換應用于第一個寄存器，用以下方式獲得一個相等的疊加:

b) 將對函數f 的量子查詢映射到:

c) 測量第二個寄存器時，觀察第一個寄存器坍縮到以下狀態(tài):

d) 將Hadamard 變換應用于第一個寄存器，得到:

e) 若向量y 滿足y.s=1，則| y〉 對應的振幅為零。 因此，測量該狀態(tài)得到的向量y 必滿足y.s = 0。

執(zhí)行一次Simon 算法，可測得一個y1與s 正交。 再執(zhí)行一次，可測得另一個y2與s 正交。 滿足該情況的y 有很多，重復O(n) 次，我們可以得到(n - 1) 相互獨立且正交于s 的向量y，通過求解如下線性方程組可得到唯一非零解s。

因此對于Simon 問題，Simon 算法的查詢復雜度為O(n)，即可在多項式時間內用Simon 算法找到上述函數的周期s。

1.3 周期函數的構造

經典密碼中存在各種周期函數的構造。 在利用Simon 算法對一個分組密碼結構Ek:{0 ，1}n→ { 0 ，1}n進行攻擊時，由Ek可以構造一個周期為s 的函數f，攻擊者對該函數進行量子疊加態(tài)查詢，并求出s 從而破解該加密結構。 目前基于Ek構造周期函數有以下兩種形式:

圖2 LRW 結構

以Liskov，Rivest 和Wagner 提出的LRW 結構(見圖2)為例，由該結構可得加密函數:

其中t 為參數，與密鑰h 有關。 接著構造周期函數:

由f ( x) = f ( x ⊕s) ，我們可以得出周期s =h ( t0) ⊕h ( t1) 。

2 對稱密碼的Simon 量子攻擊分析

Simon 算法在對稱密碼分析中的應用研究思路主要是:利用Simon 算法可以尋找出函數周期且時間復雜度為多項式級別的這一特性，針對對稱密碼算法構造一系列的攻擊方式。 首先針對某一對稱密碼的算法結構、加密模式以及認證加密結構等設計特點，構造相應的周期函數，再利用Simon 算法求解周期，進一步構造區(qū)分攻擊、偽造攻擊、密鑰恢復攻擊或滑動攻擊，實現針對對稱密碼算法的有效密碼分析[1]。

當前關于Simon 算法在對稱密碼攻擊的研究，主要分為以下四種形式:

(1) 量子區(qū)分器，需要確定一個oracle 可訪問的函數是一個具有特定結構的函數還是一個隨機函數。

(2) 密鑰恢復，恢復一些可通過oracle 訪問的函數所使用的秘密信息。

(3) 滑動攻擊，需要函數能夠有效識別明密文對中的一個“滑動”對，從而有效地提取函數中密鑰。

(4) 量子偽造攻擊，攻擊者需要在不知道密鑰的情況下為任意消息偽造標簽，將消息身份驗證碼破壞。

本節(jié)將主要從上述四個方面淺析Simon 算法在對稱密碼分析中的應用。

規(guī)劃對臨時避險以上級別的綠地全部在控規(guī)層面的圖紙上進行了四至控制，并對每個防災避險公園綠地的設施配置和建設要求有了詳細的建設指引。既符合上位規(guī)劃對城市的要求，也能具體指導城市如何建設防災避險綠地，并達到全覆蓋。

2.1 Simon 算法的區(qū)分攻擊

使用Simon 算法可加速周期函數f 中周期s的搜索過程，因此可應用于密碼分析中的區(qū)分攻擊，用以評估密碼的偽隨機性。 任意給定一個黑盒，它包含以下兩種結構中的一種:a.有一定規(guī)律的加密結構；b.是隨機置換。 對黑盒進行訪問，判斷其結構。 若黑盒為加密結構，當該加密結構可以構造出周期函數時，即可利用Simon 算法加速區(qū)分攻擊。

Simon 算法可對Feistel 結構進行區(qū)分攻擊。在2010 年的ISIT 會議上，Kuwakado 和Morii 第一個提出Simon 算法在密碼分析中的應用[5]，我們知道，沒有多項式經典算法能夠區(qū)分具有內部置換的3 輪Feistel 密碼和隨機置換(圖3 為3 輪Feistel 結構圖)。 這意味著具有內部置換的3 輪Feistel 密碼可以抵抗經典計算機上的任何選擇明文攻擊。 然而Kuwakado 和Morii 證明了量子算法可以區(qū)分具有內部置換的3 輪Feistel 密碼和隨機置換，并提出了針對3 輪Feistel 結構(內部輪函數為置換)的多項式時間內的量子區(qū)分器。 因此，具有內部置換的3 輪Feistel 密碼在量子計算機上的選擇明文攻擊下可能是不安全的。

圖3 3 輪Feistel 結構圖

2017 年， Santoli 和Schaffner[6]將上述Kuwakado 和Morii 的結論進行了拓展，將內部輪函數由置換變更為偽隨機函數，結論依然成立，即利用Simon 算法可有效區(qū)分內部輪函數為偽隨機函數的3 輪Feistel 結構與隨機置換。

2017 年，Hosoyamada 和Sasaki[7]表明量子計算機可以顯著加速Demiric-Seluck 中間相遇攻擊，可將6 輪Feistel 結構的區(qū)分攻擊的復雜度由經典計算的 O(23n/4) 降到量子計算的O(2n/2)。

2019 年Ito 等人[8]同樣使用Simon 算法，將Kuwakado 和Morii 的結果擴展了一輪，提出了一個針對4 輪Feistel 結構的量子CCA(選擇密文)區(qū)分器。

對于廣義Feistel 結構，2019 年Dong 等人[9]提出了關于d 分支Type-1 型GFS(廣義Feistel結構)的2d - 1 輪的量子區(qū)分器，以及2d 分支Type-2 型GFS 的2d + 1 輪的量子區(qū)分器。

2019 年羅宜元、閆海倫等人[10]根據MISTY劃分的左右結構，求解3 輪MISTY-L 和MISTYR 結構對應的周期函數，從而構造了相應的Simon 量子算法攻擊。 另外他們還論證了3 輪Lai-Massey 結構在選擇明文攻擊下，量子攻擊者無法構造碰撞函數的周期函數，所以在抵抗Simon 量子算法攻擊方面，Lai-Massey 結構與相同輪數的Feistel 結構相比，具有更強的安全性。

2.2 Simon 算法的密鑰恢復攻擊

EM 密碼是Even 和Mansour 提出的一種經典密碼[11]，可以看作是AES 的簡化版本，如圖4。 2012 年Kuwakado 和Morii 在文獻[12]中，基于Simon 算法對Even-Mansour 類型的分組密碼結構進行量子密鑰恢復攻擊，給出了1 輪的密鑰恢復攻擊，證明了在量子計算機上實現的Even-Mansour 密碼結構是不安全的。 2017 年Hosoyamada 和Aoki[13]在多項式時間內恢復2 輪Even-Mansour 密碼結構的所有密鑰，其量子相關密鑰攻擊是Kaplan 等人[14]的量子滑動攻擊的擴展。

圖4 EM 密碼和AES 模型

在2017 年的Asiacrypt 大會上，Leander 和May[15]結合Grover 和Simon 量子算法來破解基于FX 的分組密碼(圖5 為FX 結構)，其中使用Simon 算法作為內部判定函數，使用Grover 算法作為外部搜索算法。 結果表明在FX 結構中使用白化密鑰并不會提高量子CPA 模型的安全性。

2017 年Bonnetain[16]延續(xù)Kaplan 等人[14]對AEZ 的分析，提出一個用于發(fā)現量子周期的Simon 算法的擴展，對認證加密算法AEZv4 和AEZv5 構造了密鑰恢復攻擊。

圖5 FX 結構，k1，k2 為白化密鑰

2018 年，Dong 和Wang[17]首次對Feistel 結構使用量子密鑰恢復攻擊，結合Simon 和Grover算法，系統研究了針對r 輪Feistel 結構的量子密鑰恢復攻擊，給出了不同場景下具體的時間復雜度和內存消耗，結果顯示該量子攻擊的時間復雜度上優(yōu)于量子暴力搜索算法，同時與最好的經典攻擊相比，即Dinur 等人在CRYPTO 2015 的攻擊，不僅在時間復雜度上占據優(yōu)勢，還不產生任何額外的內存開銷。

2019 年，Ito 等人[8]將他們提出的針對4 輪Feistel 密碼的量子區(qū)分器擴展到對Feistel-KF 和Feistel-FK 結構進行密鑰恢復攻擊。

2019 年Dong 等人[11]利用他們提出的Type-1 型GFS 和Type-2 型GFS 的量子區(qū)分器，以及Leander 和May 提出的Simon 和Grover 算法結合的方法對Type-1 型、Type-2 型GFS 進行了量子密鑰恢復攻擊。

2020 年，彭信行等人[18]對6 輪的Feistel 結構進行了密鑰恢復攻擊，通過對第2 輪和第4 輪的加解密過程構造區(qū)分器，得到了4 輪密鑰，并給出了該攻擊的時間復雜度為2n/2。

2020 年， Dong 等人[19]結合Simon 算法， 對全輪的GOST 算法(類似于DES 的分組密碼算法)提出了一種新的量子密鑰恢復攻擊。

2.3 Simon 算法的滑動攻擊

在CRYPTO 2016 上，Kaplan 等人[14]通過滑動攻擊和Simon 算法相結合，將迭代Even-Mansour 密碼的滑動攻擊轉換為量子攻擊。 證明了Simon 算法可以應用于滑動攻擊，攻擊復雜度從O(2n/2) 降到O(n)，是量子模型中經典對稱密碼分析技術首次實現指數級別的加速。

在2020 年， Dong 等人[19]結合Simon 算法對滑動攻擊進行了改進， 在多項式時間內破解Feistel 的一些變體，即2K-/4K-Feistel 分組密碼以及2K-/4K-DES 分組密碼。

2.4 Simon 算法的量子偽造攻擊

在密碼學中，消息認證碼MAC 是經過某特定算法(如hash 函數等)后產生的小段信息，它可以被用來檢查信息在傳遞的過程中是否被篡改。 消息偽造攻擊就是在篡改明文信息的同時保證篡改后的消息認證碼與原來的一致，從而不被發(fā)現。 Simon 算法攻擊MAC，其本質是找到MAC 函數的周期。

2016 年Kaplan 等人[14]利用Simon 算法對分組密碼工作模式進行了量子攻擊，有CBCMAC、PMAC、GMAC 工作模式，但是無法攻擊CCM 工作模式。 對于CBC-MAC 構造周期函數為:

由f ( b，x) = f ( b′，x′) x ⊕ Ek(b) = x′ ⊕Ek(b′) ，求得周期s=1|| Ek(0) ⊕Ek(1) 。 同理可以求得PMAC、GMAC 工作模式的MAC 函數的周期。 另外Kaplan 等人[14]還提出Simon 算法可以對GCM、OCM 模式(當輸入消息為空時)以及對凱撒密碼的候選算法，如CLOC、AEZ、COPA、OTR、POET、OMD、Minalpher 等進行攻擊，復雜度僅為O(n)， 其中n 是塊的大小。 他們證明了一些認證和認證加密方案在量子環(huán)境下是不安全的。

2017 年，Santoli 和Schaffner[6]提出了針對消息認證方案CBC-MAC (固定長度消息)加密模式的量子偽造攻擊。 其攻擊也適用于將基本CBC-MAC 擴展到任意長度的消息，方法是在消息長度之前加上前綴。

2017 年Bonnetain[16]，證明了AEZ 的所有版本都在量子疊加模型中被嚴重破壞，不僅對AEZv4 和AEZv5 進行了密鑰恢復攻擊，并用于對AEZ10 的偽造攻擊，其復雜度遠低于設計者所提出的。

3 對稱密碼抗Simon 算法量子攻擊的方法

能有效抵抗經典計算機攻擊，又能抵御已知量子計算攻擊的密碼算法，稱為后量子密碼(Post-Quantum Cryptography，簡稱PQC)，或稱為抗 量 子 密 碼 ( Quantum-resistant Cryptography)[20]。 2016 年美國國家標準與技術研究院NIST 啟動了全球范圍內的后量子密碼算法的征集工作。 作為未來代替RSA、Diffie-Hellman、ECDH 等現行公鑰密碼算法的密碼技術，后量子密碼正被越來越多的人所知。 后量子密碼的研究主要在公鑰體制，在對稱密碼體制研究較少，當前主流的后量子密碼體制有四種類型[21]:基于hash、基于編碼、基于格、基于多變量的密碼體制。 上節(jié)所敘述的量子算法在對稱密碼體制的研究結果表明許多經典密碼的安全證明需要從量子攻擊者的角度被重新審視，也為經典密碼學的后量子密碼安全性提供了新的思路。

結合Simon 量子算法的攻擊特點，經典對稱密碼可以考慮以下幾種方法增強自身安全性，提高抗Simon 量子算法攻擊能力。

(1) 增加密鑰長度

對于對稱密碼算法，并不急切需要新算法代替，因為可以通過調整參數解決。 正如前文所提到的，Grover 算法提高了密鑰空間的搜索效率，能夠應用于許多密碼體制的量子計算攻擊，其效果相當于將分組密碼的密鑰長度降低了一半。因此，通過增加一倍的密鑰長度，可以抵抗這種攻擊。 這種方法對密碼安全性的提升是建立在增加系統資源消耗，犧牲效率的基礎上，并非最佳策略。

(2) 采用量子網絡編碼

利用量子不可克隆原理的量子網絡編碼可有效防止信息被竊聽。 1982 年，Wootters 和Zurek[22]提出了量子不可克隆原理，即在量子力學系統中，一個未知量子態(tài)不可能被全部準確克隆。 如果用于編碼的量子態(tài)中包含非正交態(tài)，當竊聽者通過量子操作來獲得關于編碼的信息時，根據量子不可克隆原理，接收方所收到的量子態(tài)和發(fā)送方原始配置的量子態(tài)就會不同，于是導致其統計特性發(fā)生變化，從而使竊聽被通信雙方察覺[23]。

(3) 采用量子密鑰分發(fā)(QKD)

當前“利用公鑰算法分發(fā)對稱密鑰，然后基于對稱密鑰加解密信息”的混合方案在密碼系統得到了廣泛應用。 通過QKD 代替公鑰算法可保證對稱密鑰的安全分發(fā)。 QKD 利用量子力學特性保證通信安全。 其最重要也最獨特的一個特性就是通信雙方可以察覺到第三方的竊聽。并且量子力學是物理定律，可以被認為是永久有效的，這使得量子密鑰分發(fā)能夠提供長期的安全保障性。

(4) 采用一些抗量子攻擊能力強的結構，如Lai-Massey 結構

前文我們提到對于三輪Feistel 結構和MISTY 結構，Simon 算法可對其進行區(qū)分攻擊，而三輪Lai-Massey 結構在選擇明文攻擊下能夠抵抗Simon 量子算法攻擊，故在分組密碼的設計中，可優(yōu)先選用抗Simon 量子算法攻擊能力強的Lai-Massey 結構，從而增強密碼的安全性。