基于Simon量子算法的密鑰認(rèn)證分析研究

陳 璇

(天津天獅學(xué)院，天津 300000)

0 引言

隨著近幾年移動(dòng)互聯(lián)信息技術(shù)的飛速發(fā)展，數(shù)據(jù)安全逐漸成為人們廣泛關(guān)注的問題，如何保障信息安全問題已成為行業(yè)關(guān)注的焦點(diǎn)[1-2].在威脅信息安全的諸多因素中，量子計(jì)算引中的Shor算法[3]，可以實(shí)現(xiàn)在多項(xiàng)式時(shí)間內(nèi)尋找有限群里一個(gè)元素的階，被重點(diǎn)應(yīng)用于大整數(shù)分解和離散對(duì)數(shù)計(jì)算領(lǐng)域，Simon量子算法和Grover量子算法也均對(duì)現(xiàn)有密碼算法的安全構(gòu)成了挑戰(zhàn).Simon算法能夠以O(shè)(n)次查詢實(shí)現(xiàn)特殊函數(shù)周期的獲取，并在一定程度上啟發(fā)了Shor算法的發(fā)現(xiàn)[4].

在物聯(lián)網(wǎng)數(shù)據(jù)安全方面，許多方式都會(huì)干擾加密，造成加密過程出現(xiàn)錯(cuò)誤，泄露狀態(tài)信息，而利用這些狀態(tài)信息獲取密鑰的攻擊方式被稱為“故障分析”.因此針對(duì)“故障分析”的密鑰認(rèn)證就成為了安全通信的重要環(huán)節(jié).密鑰認(rèn)證可在通信節(jié)點(diǎn)之間建立共享會(huì)話密鑰，實(shí)現(xiàn)安全通信.已有學(xué)者在此方面做出了相關(guān)研究，其中，王彩芬等[5]提出了一種改進(jìn)的三因素相互認(rèn)證與密鑰協(xié)商方案，采用增強(qiáng)存儲(chǔ)在智能卡中的相關(guān)參數(shù)的安全性，使用混沌映射計(jì)算迪菲一赫爾曼問題，修復(fù)了內(nèi)部特權(quán)攻擊的安全漏洞，保護(hù)了公共信道上敏感醫(yī)療記錄信息數(shù)據(jù).該方法能夠抵抗各類安全攻擊，且效率較高，但該方法存在的局限之一就是在使用混沌映射時(shí)，計(jì)算方式較冗長，易導(dǎo)致數(shù)據(jù)冗余造成認(rèn)證準(zhǔn)確率較低的現(xiàn)象；王偉松等[6]提出一個(gè)新的多因子認(rèn)證協(xié)議來修復(fù)身份認(rèn)證協(xié)議易遭受用戶冒充攻擊的安全漏洞.使用擴(kuò)展混沌映射，采用動(dòng)態(tài)身份保護(hù)用戶匿名性，并利用三次握手技術(shù)實(shí)現(xiàn)了異步認(rèn)證.該方法可以抵抗冒充攻擊，拒絕服務(wù)攻擊，能夠保護(hù)用戶匿名性和身份唯一性.在實(shí)際網(wǎng)絡(luò)環(huán)境中，攻擊手段是多樣的，但該方法僅針對(duì)于一種攻擊手段進(jìn)行了研究，存在一定局限性.

在此基礎(chǔ)上，本文提出一種基于Simon量子算法的密鑰認(rèn)證分析研究，在對(duì)Simon量子算法的運(yùn)算方式及密鑰設(shè)計(jì)進(jìn)行原理進(jìn)行分析的基礎(chǔ)上，結(jié)合Hadamard變換，運(yùn)用Simon量子算法對(duì)密鑰周期進(jìn)行計(jì)算，實(shí)現(xiàn)提升密鑰認(rèn)證分析過程中詢問程序安全性的目的，實(shí)驗(yàn)結(jié)果表明所提方法在準(zhǔn)確認(rèn)證概率、認(rèn)證耗時(shí)和抗攻擊性方面均有良好表現(xiàn)，具有一定的研究價(jià)值.

1 Simon量子算法

近年來，隨著量子計(jì)算的不斷進(jìn)步，量子技術(shù)被廣泛應(yīng)用到密碼算法的安全性分析中，運(yùn)用量子技術(shù)對(duì)密碼算法進(jìn)行分析更是成為了一個(gè)熱門的研究方向[7].Simon算法有多種不同的加密方案，不同的分組長度、密鑰長度、值長度以及輪數(shù)，使其可以適應(yīng)不同的應(yīng)用環(huán)境.現(xiàn)有常見的加密方案如表1所示，其中，定義該算法的分組長度為2a比特，密鑰長度為ab比特.

表1 Simon量子算法分組方式

Simon量子算法的第x輪迭代結(jié)構(gòu)如圖1所示.

圖1 Simon量子算法迭代流程圖

從圖1中可知，其中Zx和Yx分別表示對(duì)應(yīng)的左右分支，kx則表示第x輪的密鑰，那么Zx+1和Yx+1分別表示x+1對(duì)應(yīng)的左右分支，Sx表示循環(huán)移位.那么由此推斷，可以將輪函數(shù)表示為：

f(Zx)=(Zx<<<1)&(Zx<<<8)⊕(Zx<<<2)

(1)

其中，<<<表示循環(huán)位移，&表示比特與運(yùn)算，⊕表示比特異或運(yùn)算，根據(jù)公式(1)，第x輪到加密函數(shù)可以表示為：

(2)

密鑰設(shè)計(jì)：在對(duì)明文進(jìn)行加密計(jì)算時(shí)，密鑰的組成是由每一輪的子密鑰組成的，這里我們假設(shè)主密鑰為{K0，K1，…，Kx-1}，那么每一輪的密鑰就可以表示為{k0，k1，…，kx-1}，根據(jù)上文對(duì)Simon量子算法分組方式的分析可得，不同密鑰長度ab，對(duì)應(yīng)的密鑰設(shè)計(jì)方法也不同，

當(dāng)x=0，1，…，a-1時(shí)，kx=Kx；

當(dāng)x=a，a+1，…，x-1時(shí)，根據(jù)a值的不同，可以分為以下幾種情況：

(3)

其中，λ=2a-4，pi表示固定的常數(shù)序列.以此為基礎(chǔ)，對(duì)不同輪數(shù)密鑰按照輪密鑰和主密鑰進(jìn)行分級(jí)認(rèn)證.

2 基于Simon量子算法的密鑰認(rèn)證分析

2.1 密鑰周期求解

在得到Simon量子算法對(duì)密鑰的設(shè)計(jì)組成及基本原則的基礎(chǔ)上，利用Simon最密鑰周期進(jìn)行求解實(shí)際上是指在假定周期T{0，1}內(nèi)，對(duì)于密鑰函數(shù)求解任意x∈{0，1}a，使其都存在f(x)=f(x+T)，在此條件下，求解周期T.

Simon量子算法對(duì)密鑰周期的計(jì)算主要可以總結(jié)為以下5個(gè)步驟：

首先將2a個(gè)量子布特量子態(tài)初始化，并利用Hadamard變換，將其應(yīng)用至第一個(gè)密鑰寄存器中：

(4)

對(duì)第二個(gè)密鑰寄存器進(jìn)行量子Oracle訪問：

(5)

完成對(duì)第二個(gè)密鑰寄存器測量后，第一個(gè)密鑰寄存器即出現(xiàn)坍塌，坍塌結(jié)果為：

(6)

對(duì)坍塌后的第一個(gè)密鑰寄存器進(jìn)行Hadmard變換，變化后可得：

(7)

能夠?qū)崿F(xiàn)YT=1時(shí)，Y的幅度為0，那么就可以得出，此時(shí)可以滿足YT=0.

當(dāng)重復(fù)上述過程，最終基本可以得到(a-1)個(gè)不相關(guān)但均與T相交的向量，此時(shí)就可以通過對(duì)線性方程進(jìn)行求解，得出T的值.這樣的計(jì)算方式與傳統(tǒng)方法相比，可以在計(jì)算復(fù)雜度上實(shí)現(xiàn)大幅降低，為密鑰認(rèn)證分析過程節(jié)省時(shí)間.

另外一個(gè)需要注意的問題是，在對(duì)密鑰進(jìn)行認(rèn)證分析過程中，往往很難得到完全滿足Simon量子算法的解[8-9]，也就是說，Simon量子算法求解需要滿足基本的二對(duì)一的條件，即同一個(gè)函數(shù)對(duì)應(yīng)兩個(gè)原像，而兩個(gè)原像滿足其中間存在固定周期T，而在引用Simon量子算法進(jìn)行密鑰認(rèn)證分析時(shí)，會(huì)出現(xiàn)存在其他干擾t的現(xiàn)象，這時(shí)會(huì)有f(x)=f(x?t)，其中t≠T且t≠0，這種情況下稱t為布爾函數(shù)的碰撞[10].因此t存在的概率也對(duì)Simon量子算法能否計(jì)算出密鑰的周期有很大影響.

在此基礎(chǔ)上，實(shí)現(xiàn)了對(duì)密鑰周期的計(jì)算，這在降低密鑰認(rèn)證計(jì)算時(shí)間的同時(shí)，也將降低其在密鑰認(rèn)證詢問階段的對(duì)話時(shí)間.

2.2 密鑰認(rèn)證分析

上文對(duì)基于Simon量子算法密鑰周期計(jì)算方法進(jìn)行了闡述，對(duì)于密鑰認(rèn)證分析主要是針對(duì)攻擊進(jìn)行準(zhǔn)確識(shí)別，在認(rèn)證階段對(duì)輸入密鑰的正確性進(jìn)行判斷.在上述基礎(chǔ)上，本節(jié)以6輪密鑰為例，對(duì)6輪Feistel結(jié)構(gòu)密鑰認(rèn)證分析方法進(jìn)行研究.

在對(duì)6輪密鑰進(jìn)行認(rèn)證時(shí)，假設(shè)Zn，Yn分別為每一輪的輸入，f為輪函數(shù)，kn為輪密鑰，任取3個(gè)非零常數(shù)c0，c1，d0∈{0，1}0.5a，將(c0，d0)和(c1，d0)分別作為輸入值.

對(duì)密鑰進(jìn)行認(rèn)證的過程包括兩個(gè)階段，即初始化階段和密鑰認(rèn)證.在初始化階段首先將第三方的輸入值(c0，d0)和(c1，d0)生成對(duì)應(yīng)的映射e：c0×c1→cT.之后，將隨機(jī)選擇Zn，Yn∈c1和s∈Zn，Yn.將s作為主密鑰.并令s1{0，1}→c0、s2{0，1}→{0，1}、s3{0，1}→c0、s4{0，1}→{0，1}、s5{0，1}→c0、s6{0，1}→{0，1}.

當(dāng)一個(gè)輸入密鑰申請(qǐng)認(rèn)證的用戶U，ID∈{0，1}加入時(shí)，安全信道將接受參與者發(fā)送給的密鑰信息.

在接收到密鑰信息后，進(jìn)入到密鑰認(rèn)證階段，在該階會(huì)形成一個(gè)會(huì)話密鑰，并將量子布特量子態(tài)初化，用戶參與者首先進(jìn)入詢問階段.在這個(gè)階段，要完成對(duì)密鑰認(rèn)證申請(qǐng)者U隨機(jī)詢問，按照如下方式進(jìn)行問答.

ID信息詢問.收到該詢問后，認(rèn)證機(jī)制首先在已有的密鑰列表中進(jìn)行查找，如果用戶輸入的密鑰及ID信息在列表里，則返回認(rèn)證結(jié)束階段，認(rèn)為密鑰符合認(rèn)證要求，否則，系統(tǒng)返回會(huì)話密鑰階段，并將用戶輸入的密鑰信息進(jìn)行儲(chǔ)存.

Execute詢問.收到Execute詢問后，認(rèn)證機(jī)制按照其自有協(xié)議規(guī)則生成相應(yīng)的結(jié)果，并將結(jié)果返回至密鑰認(rèn)證申請(qǐng)用戶U，并保存至第一個(gè)密鑰寄存器.

Send詢問.在收到Send后，認(rèn)證機(jī)制按照協(xié)議規(guī)則生成相應(yīng)的結(jié)果，并返回給密鑰認(rèn)證申請(qǐng)用戶U，并保存至第二個(gè)密鑰寄存器，并計(jì)算YnT=1時(shí)，T不為0的值.

Corrupt詢問.收到Corrupt(U)后，返回參與者U的私鑰，并保存至Hadmard變換后的第一個(gè)密鑰寄存器.

Reveal詢問.收到Reveal后，查找Execute詢問或Send詢問所對(duì)應(yīng)的語句，并返回由其生成的對(duì)應(yīng)于該語句的密鑰設(shè)置信息，完成對(duì)6輪kn的認(rèn)證分析.

挑戰(zhàn)請(qǐng)求(Challenge request)階段：假設(shè)密鑰認(rèn)證申請(qǐng)用戶U匿名性發(fā)起認(rèn)證挑戰(zhàn)，認(rèn)證機(jī)制將做如下回應(yīng).

挑戰(zhàn)詢問階段：在這個(gè)階段，密鑰認(rèn)證申請(qǐng)用戶U隨機(jī)進(jìn)行詢問，系統(tǒng)根據(jù)一般詢問階段的應(yīng)答方式逐一進(jìn)行回應(yīng).假設(shè)密鑰認(rèn)證申請(qǐng)用戶U從未對(duì)認(rèn)證系統(tǒng)進(jìn)行Corrupt詢問，且密鑰認(rèn)證申請(qǐng)用戶U輸出的密鑰猜測值sa.如果s=sa，則表明密鑰認(rèn)證申請(qǐng)用戶U的猜測是正確的.而如果密鑰認(rèn)證申請(qǐng)用戶U可以猜出sa，則認(rèn)證系統(tǒng)即可解決DBDH(Decisional Bilinear Diffie-Hellman)問題，而這在實(shí)際上是無法實(shí)現(xiàn)的，因此密鑰認(rèn)證的安全性得以保障.

至此，密鑰認(rèn)證結(jié)束.

3 實(shí)驗(yàn)測試

3.1 實(shí)驗(yàn)條件

為了驗(yàn)證基于Simon量子算法的密鑰認(rèn)證的有效性，采用MATLAB軟件搭建了一個(gè)密鑰認(rèn)證仿真測試環(huán)境.實(shí)驗(yàn)所用系統(tǒng)CPU Inter Core i7-9700 K，6.0 GHz，內(nèi)存為16 GB，采用文獻(xiàn)[5]和文獻(xiàn)[6]中所提方法作為對(duì)比.實(shí)驗(yàn)數(shù)據(jù)Simon 64/128輪數(shù)為44，主密鑰設(shè)置為ABCDEF010203040506070809ABCDEF.密鑰管理一般分為衛(wèi)星密鑰管理、臨近空間密鑰管理以及地面網(wǎng)絡(luò)密鑰管理，如圖2所示.

圖2 密鑰管理

在圖2密鑰管理環(huán)境中，選取地面網(wǎng)絡(luò)密鑰管理中心的100組密鑰進(jìn)行認(rèn)證，其中故障個(gè)數(shù)分別設(shè)置為20，40，60，80，100個(gè).通過不同故障的密鑰分別進(jìn)行20次測試，實(shí)驗(yàn)結(jié)果取平均值，分別記錄三種方法準(zhǔn)確認(rèn)證密鑰的次數(shù)以及耗費(fèi)時(shí)間.

3.2 實(shí)驗(yàn)結(jié)果與分析

3.2.1 認(rèn)證準(zhǔn)確性測試

圖3為三種方法對(duì)密鑰進(jìn)行認(rèn)證的情況.密鑰認(rèn)證的準(zhǔn)確率是信息的發(fā)送方和接收方，用一個(gè)密鑰去加密和解密數(shù)據(jù)的準(zhǔn)確程度，其通過公式(8)計(jì)算可得：

圖3 不同方法密鑰認(rèn)證準(zhǔn)確情況

(8)

其中，M為密鑰認(rèn)證的準(zhǔn)確率，a為故障數(shù)量，m為密鑰總數(shù).密鑰認(rèn)證的準(zhǔn)確率越高，證明該方法的密鑰認(rèn)證效果越好.

從圖3中可以看出，三種方法密鑰認(rèn)證的準(zhǔn)確率均隨著故障數(shù)量的增加而逐漸降低，但對(duì)比文獻(xiàn)[5]和文獻(xiàn)[6]方法，本文方法下降趨勢較為平緩，且始終保持在90%以上的識(shí)別準(zhǔn)確率，這主要是因?yàn)楸疚姆椒ú捎肧imon算法對(duì)密鑰寄存器進(jìn)行轉(zhuǎn)換，提高了對(duì)每一輪密鑰的認(rèn)證效果.

3.2.2 認(rèn)證耗時(shí)測試

圖4為不同方法準(zhǔn)確認(rèn)證密鑰所需要消耗的時(shí)間.認(rèn)證密鑰所需要的消耗時(shí)間N與單個(gè)密鑰時(shí)間認(rèn)證時(shí)長與密鑰總數(shù)m有關(guān).其計(jì)算公式為：

圖4 不同方法密鑰認(rèn)證耗時(shí)情況

N=mt

(9)

其中，t為單個(gè)密鑰時(shí)間認(rèn)證時(shí)長.

從圖4中可知，隨著故障數(shù)量的增加，三種方法的計(jì)算耗時(shí)均呈現(xiàn)出逐漸上升的趨勢，在故障數(shù)量為40個(gè)以內(nèi)時(shí)，時(shí)間的增量相對(duì)較為平緩，但當(dāng)故障數(shù)量增加至40個(gè)以上后，文獻(xiàn)[5]和文獻(xiàn)[6]方法的耗時(shí)均出現(xiàn)劇烈上升，而本文所提方法的上升趨勢雖然較比自身也有上升趨勢，但對(duì)比另外兩種方法仍有較大優(yōu)勢，且全程耗時(shí)始終穩(wěn)定在10 s以內(nèi).這主要是因?yàn)閷?duì)密鑰周期的計(jì)算降低對(duì)申請(qǐng)認(rèn)證的密鑰信息的核查時(shí)間，減少了大量冗余計(jì)算，且應(yīng)用Simon量子算法后的詢問程序?qū)崿F(xiàn)了對(duì)無效密鑰的快速認(rèn)證.

3.2.3 認(rèn)證安全性測試

為了對(duì)所提方法的安全性進(jìn)行測試，對(duì)密鑰認(rèn)證進(jìn)行不同攻擊，此次實(shí)驗(yàn)選用在密鑰認(rèn)證過程中常見的立方攻擊、線性分析攻擊、不可能差分分析攻擊、差分分析攻擊4種攻擊方式，分別攻擊6、12、14、16輪，在此條件下分析密鑰認(rèn)證情況，具體結(jié)果如表2所示.其中立方攻擊是基于高階差分理論的新型代數(shù)攻擊方法，該方法適用于輸出比特能夠表示成關(guān)于明文變置和密鑰變量的低次多元方程；線性分析攻擊是常用密碼分析手段之一，屬于已知明文攻擊方法，它通過尋找明文和密文之間的一個(gè)“有效”的線性逼近表達(dá)式，將分組密碼與隨機(jī)置換區(qū)分開，并在此基礎(chǔ)上進(jìn)行密鑰恢復(fù)攻擊；不可能差分分析攻擊是指利用兩個(gè)明文的差對(duì)應(yīng)的輸出差不可能是某些值的特點(diǎn)求解密鑰的攻擊方法.差分分析攻擊是指通過比較分析有特定區(qū)別的明文在通過加密后的變化傳播情況來攻擊密碼算法的.

表2 面對(duì)不同攻擊時(shí)所提方法的安全性

從表2中可以看出，當(dāng)分別采用不同時(shí)間和空間復(fù)雜度的立方攻擊、線性分析攻擊、不可能差分分析攻擊、差分分析攻擊對(duì)密鑰認(rèn)證的不同輪數(shù)進(jìn)行干擾時(shí)，所提方法準(zhǔn)確實(shí)現(xiàn)密鑰認(rèn)證的概率始終保持在80%以上，這表明在面臨攻擊時(shí)，所提方法具有較高的安全性，可以在一定程度上實(shí)現(xiàn)信息的安全性.

4 結(jié)論

提出基于Simon量子算法的密鑰認(rèn)證分析研究，通過對(duì)Simon量子算法對(duì)密鑰的設(shè)計(jì)以及分類情況，結(jié)合多輪密鑰對(duì)應(yīng)的不同子密鑰在寄存器上的轉(zhuǎn)換，完成對(duì)密鑰周期的計(jì)算，在此基礎(chǔ)上，將其計(jì)算結(jié)果引入對(duì)待認(rèn)證密鑰的詢問程序中，一方面提高密鑰認(rèn)證的安全性，另一方面也可以實(shí)現(xiàn)減少密鑰認(rèn)證計(jì)算時(shí)間的目的.實(shí)驗(yàn)結(jié)果表明，文中方法的密鑰準(zhǔn)確認(rèn)證概率保持在90%以上，整體運(yùn)算耗時(shí)保持在10 s以內(nèi)，在不同類型的攻擊手段下仍能保持80%以上的密鑰認(rèn)證準(zhǔn)確率，具有較好的安全保障性能.由于條件限制，研究尚有不足，可在之后的研究中進(jìn)一步探索：

1)密鑰認(rèn)證實(shí)驗(yàn)部分僅以Simon 64/128版本的密鑰為例進(jìn)行實(shí)驗(yàn)，存在較大局限性，可以從更多密碼種類進(jìn)行測試，發(fā)現(xiàn)其可以存在的問題；

2)對(duì)于Simon量子算法的應(yīng)用是從對(duì)密鑰進(jìn)行認(rèn)證的角度進(jìn)行利用的，在之后的研究中，可從對(duì)密鑰進(jìn)行攻擊的角度，反向?qū)γ荑€認(rèn)證分析方法進(jìn)行研究.