多輪EM結(jié)構(gòu)的量子差分碰撞密鑰恢復(fù)攻擊

張中亞 吳文玲 鄒 劍

1(中國(guó)科學(xué)院軟件研究所可信計(jì)算與信息保障實(shí)驗(yàn)室 北京 100190) 2(中國(guó)科學(xué)院大學(xué) 北京 100049) 3(洛陽師范學(xué)院 河南洛陽 471934) 4(福州大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院 福州 350108)

量子計(jì)算機(jī)的發(fā)展及量子算法的應(yīng)用對(duì)密碼算法的設(shè)計(jì)和分析產(chǎn)生了巨大而深遠(yuǎn)的影響[1]，在量子環(huán)境下對(duì)對(duì)稱密碼的安全性評(píng)估已成為密碼學(xué)研究中的一個(gè)熱點(diǎn)問題.已有的量子算法中針對(duì)對(duì)稱密碼的分析方法主要有Grover量子算法[2]、Simon量子算法[3]以及Grover和Simon量子算法相結(jié)合的量子攻擊[4]等.已有的公開文獻(xiàn)中基于上述量子算法的加速優(yōu)勢(shì)，對(duì)各類對(duì)稱密碼結(jié)構(gòu)進(jìn)行了基于不同模型、不同條件下的量子分析.

Kuwakado等人[5]對(duì)3輪Feistel結(jié)構(gòu)進(jìn)行了量子條件下的區(qū)分攻擊，3輪Feistel結(jié)構(gòu)與隨機(jī)置換可以在多項(xiàng)式時(shí)間內(nèi)區(qū)分，而在經(jīng)典條件下，已證明3輪Feistel結(jié)構(gòu)與隨機(jī)置換不能在多項(xiàng)式時(shí)間內(nèi)區(qū)分.Kuwakado等人[6]對(duì)EM(Even，Mansour)結(jié)構(gòu)[7]進(jìn)行了基于Simon量子算法的量子分析，在量子條件下，單輪EM結(jié)構(gòu)是不安全的，量子敵手可以在多項(xiàng)式時(shí)間內(nèi)找到密鑰.Kaplan等人[8]利用Simon量子算法在多項(xiàng)式時(shí)間內(nèi)破解了一系列廣泛使用的基于分組密碼的認(rèn)證和認(rèn)證加密工作模式.Kaplan等人[9]基于Grover量子算法提出了量子差分和線性分析.

Leander等人[4]利用Grover量子算法和Simon量子算法的結(jié)合，對(duì)分組密碼DESX(extension of DES)所采用的FX(extension of block cipher F)結(jié)構(gòu)[10-11]進(jìn)行了量子攻擊，F(xiàn)X結(jié)構(gòu)的安全強(qiáng)度和其底層分組密碼的安全強(qiáng)度一致，前后白化密鑰沒有提高算法的安全強(qiáng)度.此后，結(jié)合Grover和Simon量子算法，基于不同的量子設(shè)置條件，更多的密碼結(jié)構(gòu)(Feistel結(jié)構(gòu)，Type-1型、Type-2型、Type-3型廣義Feistel結(jié)構(gòu))被分析研究，經(jīng)典條件下已證明多個(gè)在多項(xiàng)式時(shí)間內(nèi)不可區(qū)分的結(jié)構(gòu)在量子條件下可以區(qū)分[12-19].

基于Grover量子算法和Simon量子算法的密碼結(jié)構(gòu)安全性評(píng)估的文獻(xiàn)較為常見，但作為生日碰撞攻擊量子化的BHT(Brassard，H?yer，Tapp)量子算法[20]，還沒有公開文獻(xiàn)研究其針對(duì)對(duì)稱密碼的安全性評(píng)估，僅有對(duì)算法本身的研究[21-23].由于經(jīng)典條件下，生日碰撞攻擊在對(duì)密碼算法安全性評(píng)估中的廣泛應(yīng)用，研究量子條件下碰撞算法對(duì)密碼算法的安全性評(píng)估和BHT量子算法在密碼算法上的具體應(yīng)用具有重要的意義.

本文通過對(duì)多輪EM結(jié)構(gòu)進(jìn)行分析，研究了經(jīng)典條件和量子條件下的碰撞算法與差分密鑰恢復(fù)攻擊的結(jié)合，從BHT量子算法的角度對(duì)差分密鑰恢復(fù)攻擊進(jìn)行量子化.本文的主要貢獻(xiàn)有2個(gè)方面：

1)研究了經(jīng)典條件下多輪EM結(jié)構(gòu)的差分碰撞密鑰恢復(fù)攻擊.針對(duì)多輪EM分組密碼結(jié)構(gòu)，結(jié)合經(jīng)典條件下的生日碰撞，我們對(duì)其進(jìn)行了差分碰撞密鑰恢復(fù)攻擊，當(dāng)差分傳遞概率2-p≥2-n /2時(shí)，r輪EM結(jié)構(gòu)的密鑰恢復(fù)時(shí)間復(fù)雜度為O(2p+n /2)，比窮舉最后輪密鑰的時(shí)間復(fù)雜度O(2p+n)快了2n /2倍.

2)基于BHT量子算法對(duì)多輪EM結(jié)構(gòu)的差分碰撞密鑰恢復(fù)攻擊進(jìn)行量子化.通過研究BHT量子算法和差分密鑰恢復(fù)攻擊的結(jié)合，對(duì)多輪EM結(jié)構(gòu)的差分碰撞密鑰恢復(fù)攻擊進(jìn)行量子化，當(dāng)差分傳遞概率2-p>2-n /3時(shí)，結(jié)合BHT量子算法的量子差分碰撞密鑰恢復(fù)時(shí)間復(fù)雜度要優(yōu)于Grover搜索的直接二次加速，顯示了BHT量子算法在密碼分析中的有效性.

1 量子算法與量子分析模型

本文主要研究生日碰撞和BHT量子算法與差分密鑰恢復(fù)攻擊的結(jié)合，從而對(duì)經(jīng)典密碼分析方法進(jìn)行量子化，本文的關(guān)注重點(diǎn)是差分密碼分析的密鑰恢復(fù)階段，不從差分鏈的選取進(jìn)行研究.

1.1 Grover量子算法

Grover量子算法[2]由Grover在1996年提出，對(duì)于1個(gè)擁有N個(gè)數(shù)據(jù)的無序數(shù)據(jù)庫，用Grover量子算法只需搜索O(N1/2)次，而經(jīng)典算法需要O(N)次.Grover量子算法加快了對(duì)經(jīng)典條件下密鑰的搜索，對(duì)經(jīng)典安全通信構(gòu)成了威脅.

Grover量子算法使用1個(gè)n量子比特寄存器Oracle，包括可能需要的附加工作量子比特，算法的目的是用最少的Oracle應(yīng)用次數(shù)求出搜索問題的1個(gè)解.

算法從n量子比特初態(tài)|0?n開始，用Hadamard變換使計(jì)算機(jī)處于疊加態(tài)量子搜索算法由反復(fù)應(yīng)用Grover迭代的量子子程序組成.通過進(jìn)行次Grover迭代，就能以概率O(1)得到搜索問題的1個(gè)解(M為解的個(gè)數(shù))，這是在量子條件下對(duì)經(jīng)典算法要求的O(N/M)次Oracle調(diào)用的二次加速.

1.2 BHT量子算法

BHT量子算法[20]由Brassard，H?yer，Tapp在1998年提出，BHT量子算法被設(shè)計(jì)為針對(duì)2-to-1目標(biāo)函數(shù)F求解碰撞，即對(duì)于函數(shù)：

F:X→Y，

其中,|X|=2|Y|，|Y|=2n.

BHT量子算法以Grover量子算法為基礎(chǔ)，以O(shè)(2n /3)的量子查詢復(fù)雜度、量子時(shí)間復(fù)雜度、量子存儲(chǔ)復(fù)雜度找到函數(shù)F的1個(gè)碰撞，算法過程為：

Step1.從集合X中隨機(jī)挑選2n /3個(gè)元素，放入集合X′.

Step2.詢問函數(shù)F，構(gòu)造列表L={(x,F(x))}，其中x∈X′，|L|=2n /3，并將列表L存于量子存儲(chǔ)單元中.

Step3.檢查L(zhǎng)中是否存在碰撞.

Step3.1.若L中存在碰撞，即有(x,F(x)),(y,F(y))∈L，滿足x≠y且F(x)=F(y)，則輸出碰撞.

Step3.2.若L中不存在碰撞，構(gòu)造分類函數(shù)：

應(yīng)用Grover量子算法對(duì)F1(x)求解.

BHT量子算法的量子查詢復(fù)雜度、量子時(shí)間復(fù)雜度、量子存儲(chǔ)復(fù)雜度均為O(2n /3).

1.3 量子分析模型

依據(jù)Zhandry[24]給出的量子設(shè)置中偽隨機(jī)函數(shù)(pseudo-random function, PRF)和偽隨機(jī)置換(pseudo-random permutation，PRP)安全性的概念，Kaplan等人[9]根據(jù)收集數(shù)據(jù)方式的不同，在對(duì)密碼進(jìn)行量子分析時(shí)，提出標(biāo)準(zhǔn)安全和量子安全2種不同的量子分析模型.

如果沒有有效的量子算法能夠通過只進(jìn)行經(jīng)典查詢區(qū)分分組密碼與PRP(或PRF)，那么分組密碼就是針對(duì)量子分析的標(biāo)準(zhǔn)安全，簡(jiǎn)稱Q1模型，該模型中，分析者用經(jīng)典方式收集數(shù)據(jù)，用量子計(jì)算處理數(shù)據(jù)；如果即使能進(jìn)行量子查詢，也沒有有效的量子算法能夠區(qū)分分組密碼與PRP(或PRF)，則分組密碼對(duì)量子分析是量子安全，簡(jiǎn)稱Q2模型，該模型中，分析者可以直接用經(jīng)典輸入的量子疊加來查詢密碼oracle，并接收相應(yīng)輸出的疊加.

由于Q2模型的強(qiáng)大的量子查詢能力，現(xiàn)有公開的量子密碼分析文獻(xiàn)中大都采用Q2模型.Q2模型中，對(duì)手的攻擊能力非常強(qiáng)，但有可能設(shè)計(jì)安全的協(xié)議來抵抗這種攻擊.很多在經(jīng)典模型中安全的消息鑒別碼(message authentication codes, MAC)和認(rèn)證加密算法(authenticated encryption, AE)被Q2攻擊[8]破解.另一方面，在量子模型中，假設(shè)標(biāo)準(zhǔn)安全PRF或量子安全PRF，常見的加密模式已經(jīng)被證明是安全的[25].

2 差分碰撞密鑰恢復(fù)攻擊

EM密碼結(jié)構(gòu)是Even和Mansour[6]提出的分組密碼結(jié)構(gòu)，可認(rèn)為是高級(jí)加密標(biāo)準(zhǔn)(Advanced Encryption Standard, AES)的簡(jiǎn)約形式.已經(jīng)證明，任何經(jīng)典算法都需要密鑰長(zhǎng)度的子指數(shù)時(shí)間來破譯EM密碼，在這個(gè)意義上，EM密碼結(jié)構(gòu)對(duì)任何經(jīng)典對(duì)手都是安全的.

Fig.1 One round EM structure

單輪EM結(jié)構(gòu)如圖1所示，P是{0,1}n上的公開隨機(jī)置換，密鑰k=k1‖k2長(zhǎng)度為2n(單位為b)，其中k1,k2∈{0,1}n.加密算法為c=Ek(m)=P(k1⊕m)⊕k2，其中m,c∈{0,1}n分別是明文及其密文，解密以m=Dk(c)=P-1(k2⊕c)⊕k1進(jìn)行.

通過迭代置換P并在其中插入密鑰k1,k2,…,kr+1的方式，可以獲得r輪EM結(jié)構(gòu)：

EMk1,k2,…,kr+1(m)=

P(P(P(m⊕k1)⊕k2)⊕…)⊕kr+1，

其中，r+1個(gè)輪子密鑰可以相互獨(dú)立，也可以由主密鑰一并生成，本文假設(shè)r+1個(gè)輪子密鑰k1,k2,…,kr+1相互獨(dú)立.

根據(jù)差分密碼分析的概念，多輪EM密碼一般意義上的差分密碼分析如圖2所示：

Fig.2 Differential cryptanalysis of r-round EM structure

本文不考慮差分鏈的搜尋，關(guān)注的重點(diǎn)是恢復(fù)密鑰kr+1階段的復(fù)雜度.

P(y⊕β)⊕kr+1=c′，

DK(c)=m，

DK(c′)=m⊕α,

成立.

在經(jīng)典條件中，一般利用

P-1(c⊕kr+1)⊕P-1(c′⊕kr+1)=β

對(duì)密鑰kr+1進(jìn)行測(cè)試，直接窮舉或通過分析具體算法先求出部分值，再通過窮舉剩余密鑰的方式求解密鑰kr+1，計(jì)算復(fù)雜度為O(2p+n)，密鑰恢復(fù)過程如圖3所示:

Fig.3 Key recovery of differential cryptanalysis

將c′表示為以c和β為輸入的函數(shù)：

c′=EK(m⊕α)=P(P-1(c⊕kr+1)⊕β)⊕kr+1.

P和β的值已知，可以構(gòu)造函數(shù)c″：

c″=P(P-1(c)⊕β).

如圖4所示，進(jìn)而構(gòu)造f函數(shù)：

f=c′⊕c″=

P(P-1(c⊕kr+1)⊕β)⊕P(P-1(c)⊕β)⊕kr+1=

EK(m⊕α)⊕P(P-1(c)⊕β)=

EK(DK(c)⊕α)⊕P(P-1(c)⊕β).

Fig.4 Construction of f=c′⊕ c″ function

也即，當(dāng)差分傳遞鏈成立時(shí)，f函數(shù)可以寫為

f=P(P-1(c⊕kr+1)⊕β)⊕P(P-1(c)⊕β)⊕kr+1.

對(duì)于f函數(shù)，當(dāng)差分傳遞概率不同時(shí)，有2種情況：

1)差分傳遞概率為1

即無論變量c如何變化，β總是以概率1出現(xiàn)，也即f函數(shù)以概率1成立.

當(dāng)f函數(shù)輸入為c和c⊕kr+1時(shí)，有

f(c)=P(P-1(c⊕kr+1)⊕β)⊕P(P-1(c)⊕β)⊕kr+1，

f(c⊕kr+1)=P(P-1(c⊕kr+1⊕kr+1)⊕β)⊕

P(P-1(c⊕kr+1)⊕β)⊕kr+1=

P(P-1(c)⊕β)⊕P(P-1(c⊕kr+1)⊕β)⊕

kr+1=f(c)，

即函數(shù)值保持不變，函數(shù)f(c)存在周期s=kr+1.

在經(jīng)典條件下，由生日碰撞攻擊可知，當(dāng)任意選取2n /2個(gè)輸入c時(shí)，可以高概率求出1對(duì)碰撞(c,c⊕kr+1)，使得f(c)=f(c⊕kr+1)，從而輕易求出密鑰kr+1，時(shí)間復(fù)雜度和數(shù)據(jù)復(fù)雜度為O(2n /2).

2)差分傳遞概率2-p<1

當(dāng)輸入2p個(gè)差為α的對(duì)時(shí)，存在1個(gè)輸入對(duì)的輸出差為β，出現(xiàn)2n /2個(gè)符合輸出差的輸入對(duì)時(shí)，根據(jù)生日攻擊，即可以高概率求出1對(duì)碰撞(c,c⊕kr+1)，使得f(c)=f(c⊕kr+1)，也即可高概率求出密鑰kr+1.那么在計(jì)算2n /2×2p個(gè)輸入c的函數(shù)值f(c)后，存在1對(duì)碰撞(c,c⊕kr+1)，時(shí)間復(fù)雜度和數(shù)據(jù)復(fù)雜度為

O(2n /2×2p)=O(2n /2+p).

由于對(duì)輸入c的形式不做限制，可以在選擇明文攻擊的條件下對(duì)多輪EM結(jié)構(gòu)進(jìn)行差分密鑰恢復(fù)攻擊.

算法1.基于生日碰撞的多輪EM結(jié)構(gòu)差分密鑰恢復(fù)攻擊.

輸入：明文m集合M(|M|=2n /2+p)；

輸出：密鑰kr+1.

Step1. 任選1個(gè)包含2n /2+p個(gè)m元素的集合M.

Step2. 對(duì)于每一個(gè)m，分別計(jì)算：

c=EK(m)，

c′=EK(m⊕α)，

c″=P(P-1(c)⊕β)，

g(m)=c′⊕c″=

EK(m⊕α)⊕P(P-1(EK(m))⊕β).

Step3. 檢查是否存在不同的m值(m0,m1)，使得g(m0)=g(m1)成立.

Step4. 對(duì)于每1對(duì)碰撞，計(jì)算：

kr+1=EK(m0)⊕EK(m1).

Step5. 將m0或m1對(duì)應(yīng)的c和c′，以及kr+1代入式：

P-1(c⊕kr+1)⊕P-1(c′⊕kr+1)=β，

驗(yàn)證該式是否成立，如果成立則輸出密鑰kr+1.

復(fù)雜度分析：

EM結(jié)構(gòu)分組和密鑰長(zhǎng)度以及隨機(jī)置換P的輸入均為n位，生日碰撞攻擊下，對(duì)于g(m)函數(shù)，2n /2+p個(gè)輸入值約有2p個(gè)碰撞出現(xiàn)，共得到2p個(gè)候選密鑰.在隨機(jī)假設(shè)的條件下，錯(cuò)誤密鑰通過公式P-1(c⊕kr+1)⊕P-1(c′⊕kr+1)=β測(cè)試的概率為2-n，則通過測(cè)試的錯(cuò)誤密鑰數(shù)為2p-n.

1)p>n/2時(shí)，集合M中元素個(gè)數(shù)2n /2+p>2n，超過數(shù)據(jù)總長(zhǎng)度，攻擊失敗.

2)p≤n/2時(shí)，集合M中元素個(gè)數(shù)2n /2+p≤2n，通過測(cè)試的錯(cuò)誤密鑰數(shù)為2p-n≤2-n /2<1.2n /2+p個(gè)明文中共有2n /2個(gè)明文及其構(gòu)成的差為α的明文對(duì)，r-1輪后輸出差為β.即在生日碰撞攻擊下，有2n /2個(gè)輸入值符合f函數(shù)，則可以高概率求出1對(duì)所需碰撞，進(jìn)而求出正確密鑰，時(shí)間復(fù)雜度和數(shù)據(jù)復(fù)雜度均為

O(2n /2×2p)=O(2n /2+p).

當(dāng)p≤n/2時(shí)，對(duì)比經(jīng)典條件下的r輪EM結(jié)構(gòu)的差分密鑰恢復(fù)的時(shí)間復(fù)雜度O(2p+n)，我們對(duì)r輪EM結(jié)構(gòu)的差分碰撞密鑰恢復(fù)攻擊速度提高了2n /2倍，時(shí)間復(fù)雜度明顯降低.

3 量子差分碰撞密鑰恢復(fù)攻擊

本節(jié)基于BHT量子算法對(duì)多輪EM結(jié)構(gòu)差分密鑰恢復(fù)攻擊進(jìn)行量子化.由第2節(jié)分析可知，g(m)函數(shù)成立的概率為前r-1輪輸入輸出差(α,β)的差分傳遞概率2-p，當(dāng)1對(duì)m值(m0,m1)同時(shí)滿足g(m)函數(shù)時(shí)，概率為2-p×2-p=2-2p，那么g(m)函數(shù)為2-to-1函數(shù)的概率也為2-2p，此時(shí)g(m)函數(shù)以概率2-2p符合BHT量子算法的適應(yīng)條件.

可以在量子Q2模型下，以量子選擇明文的攻擊條件，通過BHT量子算法對(duì)多輪EM結(jié)構(gòu)差分碰撞密鑰恢復(fù)攻擊進(jìn)行量子化.

算法2.基于BHT量子算法的多輪EM結(jié)構(gòu)差分密鑰恢復(fù)攻擊.

輸入：明文m集合M′(|M′|=l)；

輸出：密鑰kr+1.

Step1.從明文m集合中隨機(jī)挑選l個(gè)元素，放入集合M′.

Step2.詢問函數(shù)g(m)，構(gòu)造列表L={(m,g(m))}，其中m∈M′，|L|=l，將列表L存于量子存儲(chǔ)單元中.

Step3.檢查L(zhǎng)中是否存在不同的m值(m0,m1)，使得g(m0)=g(m1)成立.

Step3.1.對(duì)于每1對(duì)碰撞，計(jì)算：

kr+1=EK(m0)⊕EK(m1).

Step3.2.將m0或m1對(duì)應(yīng)的c和c′，以及kr+1代入式：

P-1(c⊕kr+1)⊕P-1(c′⊕kr+1)=β.

驗(yàn)證該式是否成立，如果成立則輸出密鑰kr+1.

Step4.若L中不存在碰撞或無法解出正確密鑰kr+1，構(gòu)造分類函數(shù)：

Step5.應(yīng)用Grover量子算法對(duì)g1(m)求解，計(jì)算并輸出kr+1=EK(m0)⊕EK(m).

復(fù)雜度分析：

Step3前需要計(jì)算g(m)函數(shù)的l個(gè)輸出值，并都存在量子存儲(chǔ)空間中，此步驟需要l的量子存儲(chǔ)復(fù)雜度、量子查詢復(fù)雜度與量子時(shí)間復(fù)雜度.

已知g(m)函數(shù)成立的概率為前r-1輪的差分傳遞概率2-p，出現(xiàn)(m0,m1)同時(shí)符合g(m)函數(shù)的概率為2-2p，由于列表L中的元素個(gè)數(shù)為l，因此在Step4中調(diào)用Grover量子算法對(duì)g1(m)求解時(shí)對(duì)應(yīng)解的個(gè)數(shù)是l×2-2p.

L中所有數(shù)據(jù)都存在量子空間中，因此Grover量子算法每次查詢都能以量子疊加態(tài)訪問所有l(wèi)個(gè)數(shù)據(jù)，依據(jù)Grover量子算法，有

則設(shè)量子時(shí)間復(fù)雜度:

其中，TO為以量子疊加態(tài)訪問Oracle的時(shí)間，T|ψ為Hadamard變換的時(shí)間.算法將L的元素都存在量子寄存器里，依據(jù)量子時(shí)間復(fù)雜度約定，若能以量子疊加態(tài)訪問Oracle，則只需要O(1)的時(shí)間，即TO=O(1).

由于Step3前需要計(jì)算函數(shù)g(m)的l個(gè)輸出值，總的量子時(shí)間復(fù)雜度為

max{l,2n /2+p×l-1/2}.

當(dāng)l=2n /2+p×l-1/2，即l=2n /3+2p/3時(shí)，可得max{l,2n /2+p×l-1/2}最小值為O(2n /3+2p/3).

另外，當(dāng)l×2-2p≥1，即l≥22p時(shí)Grover搜索才能有解，即上述復(fù)雜度成立的條件為

l=2n /3+2p/3≥22p，即p≤n/4.

當(dāng)p≤n/4時(shí)，有最小復(fù)雜度O(2n /3+2p/3)，否則，量子時(shí)間復(fù)雜度為max{l,2n /2+p×l-1/2}，其中l(wèi)≥22p，考慮2個(gè)可變參數(shù)l和p.

1)參數(shù)l

① 當(dāng)l=2n /3+2p/3時(shí)，有最小值2n /3+2p/3；

② 當(dāng)l<2n /3+2p/3時(shí)，max{l,2n /2+p×l-1/2}=2n /2+p×l-1/2；

③ 當(dāng)l>2n /3+2p/3時(shí)，max{l,2n /2+p×l-1/2}=l.

2)參數(shù)p

①p≤n/4時(shí)，取l=2n /3+2p/3≥22p，max{l,2n /2+p×l-1/2}有最小值2n /3+2p/3；

②n/42n /3+2p/3，max{l,2n /2+p×l-1/2}=l，且需l≥22p，取l=22p，則有max{l,2n /2+p×l-1/2}=l=22p；

③p>n/2時(shí)，由于l×2-2p<2n×2-2p<1，Grover搜索無解，量子碰撞算法不能對(duì)該差分分析量子化，此時(shí)，和經(jīng)典生日攻擊一致，p>n/2時(shí)，2n /2+p>2n，所需數(shù)據(jù)量超過所有明密文對(duì)個(gè)數(shù)，無法求出正確密鑰.

有關(guān)文獻(xiàn)中的量子差分攻擊只用Grover搜索進(jìn)行量子化，當(dāng)只用Grover量子搜索對(duì)本文所述差分分析進(jìn)行量子化時(shí)，其分類函數(shù)為

該分類函數(shù)取1的概率為2-n-p，根據(jù)Grover量子算法，找到密鑰kr+1的時(shí)間復(fù)雜度為O(2n /2+p/2).

1)p≤n/4時(shí)，有

O(2n /3+2p/3)

2)n/4

max{l,2n /2+p×l-1/2}=l=22p<2n /2+p/2，

也即有:

O(22p)

上述2種情況下，基于BHT量子算法的差分密鑰恢復(fù)結(jié)果優(yōu)于直接利用Grover搜索.

3)n/3≤p

max{l,2n /2+p×l-1/2}=l=22p≥2n /2+p/2，

也即有

O(22p)≥O(2n /2+p/2).

此種情況下，Grover搜索結(jié)果更優(yōu).

經(jīng)典條件和量子條件下的對(duì)比結(jié)果匯總在表1中，結(jié)果顯示，當(dāng)p2-n /3時(shí)，基于BHT碰撞搜索算法的量子差分碰撞密鑰恢復(fù)攻擊要優(yōu)于基于Grover搜索的量子差分的直接二次加速.

Table 1 Time Complexity of Key Recovery Under Classical and Quantum Conditions

4 總 結(jié)

本文通過對(duì)多輪EM分組密碼結(jié)構(gòu)進(jìn)行分析，研究了經(jīng)典條件生日碰撞、BHT量子算法和差分密鑰恢復(fù)攻擊的結(jié)合方法，對(duì)多輪EM結(jié)構(gòu)進(jìn)行了差分碰撞密鑰恢復(fù)攻擊，并從量子碰撞算法的角度對(duì)其進(jìn)行量子化.

研究結(jié)果表明：經(jīng)典條件下，當(dāng)差分傳遞概率2-p≥2-n /2時(shí)，r輪EM結(jié)構(gòu)的差分碰撞密鑰恢復(fù)攻擊快了2n /2倍；量子條件下，當(dāng)2-p>2-n /3時(shí)，基于BHT碰撞搜索算法的量子差分碰撞密鑰恢復(fù)攻擊時(shí)間復(fù)雜度要優(yōu)于基于Grover搜索的差分攻擊.結(jié)果同時(shí)表明，當(dāng)2-p≤2-n /3時(shí)，基于Grover搜索的差分密鑰恢復(fù)攻擊的二次加速仍然是最優(yōu)選擇.