從演化密碼到量子人工智能密碼綜述

王寶楠 胡 風(fēng) 張煥國(guó) 王 潮,3

1(特種光纖與光接入網(wǎng)重點(diǎn)實(shí)驗(yàn)室，特種光纖與先進(jìn)通信國(guó)際合作聯(lián)合實(shí)驗(yàn)室，上海先進(jìn)通信與數(shù)據(jù)科學(xué)研究院，上海大學(xué) 上海 200444) 2(密碼科學(xué)技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室 北京 100878) 3(鵬城實(shí)驗(yàn)室量子計(jì)算中心 廣東深圳 518000) 4(武漢大學(xué)國(guó)家網(wǎng)絡(luò)安全學(xué)院 武漢 430079)

Fig. 1 Relationship between cryptosystem, cryptographic components, and mathematical problem圖1 密碼系統(tǒng)、密碼部件和數(shù)學(xué)問題的關(guān)系

演化算法是一種模擬生物演化過程與機(jī)制求解優(yōu)化問題的一類自組織、自適應(yīng)的隨機(jī)搜索算法[1-2].這類算法具有比數(shù)學(xué)規(guī)劃方法更大的優(yōu)越性，它已經(jīng)成為人工智能領(lǐng)域的研究熱點(diǎn)，在解決組合優(yōu)化和搜索問題方面，如城市旅行商問題[3]、裝箱問題[4]、背包問題[5]等取得了較大的成果.

演化算法的引入并非重新設(shè)計(jì)甚至替代已有密碼系統(tǒng)，其本質(zhì)是在解決無(wú)法基于數(shù)學(xué)理論構(gòu)建的科學(xué)問題求解，而且結(jié)合已有的先驗(yàn)知識(shí)處理難題，相比傳統(tǒng)設(shè)計(jì)方法更具優(yōu)勢(shì)，演化算法已在優(yōu)化設(shè)計(jì)、學(xué)習(xí)和博弈等多個(gè)領(lǐng)域取得成功[2].

與國(guó)外學(xué)者僅考慮演化算法在加解密算法的密碼部件應(yīng)用不同，中國(guó)學(xué)者將密碼學(xué)與演化計(jì)算結(jié)合起來，借鑒生物進(jìn)化的思想，獨(dú)立提出演化密碼的概念和用演化計(jì)算設(shè)計(jì)密碼的方法，采用演化計(jì)算解決密碼設(shè)計(jì)與分析中的搜索和優(yōu)化問題，得到可變漸強(qiáng)的密碼，有望成為已有密碼分析和設(shè)計(jì)方法的一種增強(qiáng)手段.

如圖1所示，一個(gè)密碼系統(tǒng)通常由多個(gè)密碼部件構(gòu)成的，每個(gè)密碼部件包含解某個(gè)數(shù)學(xué)問題的算法.倘若解決某個(gè)密碼部件的數(shù)學(xué)問題屬于組合優(yōu)化或搜索范疇，那么該密碼部件就可以嘗試引入演化算法，提高該密碼部件的實(shí)現(xiàn)效率.

國(guó)內(nèi)外的研究進(jìn)展表明，演化密碼已經(jīng)在對(duì)稱密碼和非對(duì)稱密碼領(lǐng)域均取得了實(shí)際成果，涉及密碼分析和設(shè)計(jì)的諸多領(lǐng)域，從加解密算法的密碼部件設(shè)計(jì)拓展到了密碼協(xié)議的設(shè)計(jì)分析.

從演化思想的隨機(jī)性探索角度出發(fā)，量子人工智能提供了一種新的、不同于傳統(tǒng)的量子計(jì)算模式.典型的量子人工智能算法D-Wave量子計(jì)算機(jī)原理的量子退火算法，其獨(dú)特的量子隧穿效應(yīng)可克服傳統(tǒng)搜索算法易陷入局部極值點(diǎn)的缺陷，在密碼設(shè)計(jì)和分析領(lǐng)域?qū)崿F(xiàn)對(duì)演化密碼的進(jìn)一步拓展.

1 演化計(jì)算的概念

演化算法和演化計(jì)算的概念是什么？1999年Millan給出了演化計(jì)算的一種定義——演化計(jì)算就是模擬生物演化過程或社會(huì)性行為建立模型來解決問題的方法[6].他從生物學(xué)和社會(huì)行為學(xué)角度提煉出演化計(jì)算的概念，指明了演化算法是一種模型.但我們認(rèn)為這一定義還不夠全面，因?yàn)槌Ｒ姷哪M退火算法與生物體或社會(huì)行為并沒有什么關(guān)系，但通常人們?cè)敢鈱⑵渥鳛檠莼惴ǖ囊环N.

2002年武漢大學(xué)的張煥國(guó)教授等人[1]給出了一個(gè)比較全面和概括性的定義——演化計(jì)算就是基于自然界發(fā)展規(guī)律而提出的一種通用的問題求解方法.與Millan的定義相比，他將出發(fā)點(diǎn)擴(kuò)大到了自然界，涵蓋了生物學(xué)和社會(huì)行為學(xué)，也涵蓋了模擬退火算法所在的物理學(xué).

我們認(rèn)為：演化算法不是一種具體的算法，而是一種通用模型，符合并具有演化特征的算法，都可以設(shè)計(jì)成演化算法，如常見的蟻群算法、遺傳算法、模擬退火算法、以及量子人工智能算法如量子退火算法等，它們所獲得的結(jié)果總是在不斷地迭代中趨向最優(yōu).演化算法和仿生算法、人工智能算法在局部概念上具有相似性，容易使人混淆它們之間的關(guān)系.與仿生算法、人工智能算法相比，演化算法的概念出現(xiàn)較晚，它實(shí)際上是對(duì)已知人工智能算法的一種分類，它與人工智能算法之間是包括與被包括的關(guān)系.另外，大部分仿生算法，如遺傳算法、蟻群算法、細(xì)胞自動(dòng)機(jī)等，都具有演化的特征，并且大部分仿生算法的設(shè)計(jì)目的是為了解決搜索和組合優(yōu)化問題，這一點(diǎn)與演化計(jì)算的目標(biāo)很相似.因此，大多數(shù)仿生算法本身屬于演化算法或能夠改造成為演化算法，演化算法和仿生算法之間是繼承和被繼承的關(guān)系.

這里我們給演化計(jì)算下的定義是——演化計(jì)算就是模擬自然界發(fā)展規(guī)律建立模型來解決問題的一種通用方法.即表明：任何具有演化特征的“自然界”算法都屬于或者能夠設(shè)計(jì)成演化算法，任何能夠歸結(jié)為搜索或組合優(yōu)化問題的問題，都可以嘗試用演化算法這一通用的“模型”來解決.

演化算法具有2個(gè)基本特征——迭代尋優(yōu)過程和評(píng)估函數(shù)，具有這2個(gè)特征的自然界算法都可以稱為演化算法.迭代是演化計(jì)算的尋優(yōu)手段，在評(píng)估函數(shù)的指引下，根據(jù)既定的算法搜索目標(biāo)空間，尋找合適的解.這個(gè)合適的解可以是最優(yōu)解，也可以是次優(yōu)解.演化算法中的評(píng)估函數(shù)是必不可少的，為了判定某個(gè)解的優(yōu)劣，我們需要評(píng)估函數(shù)給每個(gè)解“打分”，使得任意2個(gè)解能夠進(jìn)行比較，選出其中較優(yōu)的解.我們給出演化算法設(shè)計(jì)的一般模型：

1) 初始化群體；

2) 尋優(yōu)過程.

這是演化算法的核心內(nèi)容，不同的演化算法尋優(yōu)過程不同，但完成的作用是類似的，即通過不斷的迭代，利用評(píng)估函數(shù)對(duì)每個(gè)解進(jìn)行評(píng)估，排除評(píng)估值較低的解.

評(píng)估函數(shù)設(shè)計(jì)：評(píng)估函數(shù)是演化計(jì)算中不可缺少的組成部分，它用于評(píng)估當(dāng)前解的優(yōu)越性，給出精確的適應(yīng)值，使得任意2個(gè)解能夠進(jìn)行比較.通常我們尋找的目標(biāo)要滿足多個(gè)指標(biāo)要求，因此我們?cè)O(shè)計(jì)的評(píng)估函數(shù)需要能夠同時(shí)體現(xiàn)多個(gè)指標(biāo)的能力.評(píng)估函數(shù)通常定義為

f(x)=α1×β1×x+α2×β2×x+α3×β3×x…,

(1)

其中，x表示個(gè)體，α1,α2,α3表示加權(quán)系數(shù)，β1,β2,β3表示不同的指標(biāo).

3) 得到當(dāng)前最優(yōu)的解.

2 密碼學(xué)演化計(jì)算的發(fā)展過程

傳統(tǒng)密碼都遵循一種加解密算法固定而密鑰隨機(jī)可變的模式.如果能夠使加密過程中加密算法也在不斷地變化，則稱加密算法是可變的密碼，即演化密碼.

設(shè)E-τ為初始加密算法，演化過程從E-τ開始，最后變?yōu)镋0.因?yàn)镋0的安全強(qiáng)度達(dá)到了實(shí)際使用的要求，所以可以應(yīng)用于實(shí)際.

設(shè)S(E)為加密算法E的強(qiáng)度函數(shù)，則演化過程可以表示為

E-τ→E-τ+1→E-τ+2→…→E-1→E0,

(2)

S(E-τ)S(E-1)

(3)

演化密碼的使用能夠帶來2個(gè)好處：1)增強(qiáng)密碼強(qiáng)度.由于加密算法在加密過程中因受到密鑰控制而不斷變化，從而極大提高了密碼的強(qiáng)度.若能使加密算法朝著越來越好的方向發(fā)展變化，那么這種密碼就是一種自發(fā)的、漸強(qiáng)的密碼；2)提高自動(dòng)化程度.密碼系統(tǒng)的復(fù)雜性和困難性是長(zhǎng)期困擾人們分析和使用的難題.演化密碼的設(shè)計(jì)理念是基于自然界生物的進(jìn)化過程，其演化過程中不需要人為操控，符合人們長(zhǎng)期追求密碼設(shè)計(jì)自動(dòng)化的目的.它的出現(xiàn)是人們?cè)诿艽a學(xué)領(lǐng)域的研究中邁出的重要一步.2013年武漢大學(xué)的張煥國(guó)等人證明了攻擊演化密碼的數(shù)據(jù)復(fù)雜度大于攻擊固定算法密碼的數(shù)據(jù)復(fù)雜度，從而表明演化密碼對(duì)抗傳統(tǒng)差分攻擊的能力高于固定算法密碼.體現(xiàn)出演化密碼所具有的優(yōu)勢(shì)，能夠大大提高密碼強(qiáng)度[7].

目前，演化算法已經(jīng)在密碼學(xué)的各個(gè)領(lǐng)域得到了應(yīng)用，但關(guān)于演化算法何時(shí)開始在密碼學(xué)中使用還沒有一個(gè)準(zhǔn)確的定論，因?yàn)閿?shù)學(xué)和密碼學(xué)有著千絲萬(wàn)縷的聯(lián)系，就像進(jìn)化論本身一樣，演化計(jì)算從單純解決數(shù)學(xué)問題，演變到解決密碼學(xué)問題也是一個(gè)漸變的過程.根據(jù)收集的參考文獻(xiàn)，我們可以大致知道密碼學(xué)演化計(jì)算開始的時(shí)間和發(fā)展過程，我們將這個(gè)發(fā)展過程分為4個(gè)階段：

1) 探索階段(1980～1993)

現(xiàn)實(shí)生活中，人們經(jīng)常需要破譯一些簡(jiǎn)單的替代密碼，通常人們根據(jù)語(yǔ)法習(xí)慣和統(tǒng)計(jì)分析的方法來破譯.但使用人工統(tǒng)計(jì)的方法，既耗費(fèi)人力、增加成本，且破譯時(shí)間也不短.為了“偷懶”，人們開始研究如何將這一繁瑣的過程自動(dòng)化.從1980年左右開始，有少數(shù)密碼學(xué)者創(chuàng)新性地使用具有“自動(dòng)”效果的方法來替代繁瑣的人工統(tǒng)計(jì)工作[8-10].這一時(shí)期并沒有演化計(jì)算的概念，人們主要采用傳統(tǒng)的、簡(jiǎn)單的人工智能算法實(shí)現(xiàn)自動(dòng)化.

1979年P(guān)eleg等人使用松弛算法(relaxation algorithm)通過不斷的迭代和更新實(shí)現(xiàn)了對(duì)替代密碼的破譯[11]，這應(yīng)該是人工智能在密碼學(xué)中最早的應(yīng)用.而后，模擬退火等組合優(yōu)化算法也被應(yīng)用到替代密碼的研究中[12].這些經(jīng)典的組合優(yōu)化算法原理都比較簡(jiǎn)單，應(yīng)用也不復(fù)雜，但能夠達(dá)到的破譯效果有限，這反映了當(dāng)時(shí)人們?cè)诮鉀Q密碼問題的“智能化”方面還處于一個(gè)比較朦朧的階段.

于此同時(shí)，在實(shí)際生活應(yīng)用中，出現(xiàn)了使用人工智能語(yǔ)言(如lisp,prolog,smalltalk等)編寫的專家系統(tǒng)，通過分析單個(gè)字母或字符串的出現(xiàn)頻率，該系統(tǒng)能夠破譯簡(jiǎn)單的替代密碼[8].

1993年Spillman等人首次提出利用遺傳算法的隨機(jī)定向搜索特性破譯替代密碼的新方法[13].這標(biāo)志著作為演化算法中最早出現(xiàn)和最為經(jīng)典的遺傳算法開始在傳統(tǒng)密碼的分析中得到應(yīng)用，也標(biāo)志著演化計(jì)算開始真正進(jìn)入密碼學(xué)領(lǐng)域.同年，Mathews的研究表明遺傳算法能夠有效地搜索巨大的密鑰空間，可以作為破譯密碼系統(tǒng)強(qiáng)有力的分析工具[14].此后有關(guān)遺傳算法分析替代密碼的文獻(xiàn)大量涌現(xiàn)，盡管演化計(jì)算的概念還沒出現(xiàn)，但人們對(duì)如何使用演化算法解決密碼學(xué)問題有了新的提高.

這一時(shí)期的研究對(duì)象可以分成2類：1)明文破譯自動(dòng)化;2)密鑰搜索.分別對(duì)應(yīng)了組合優(yōu)化問題和搜索問題.研究中，人們發(fā)現(xiàn)定義一個(gè)評(píng)估函數(shù)(cost function)是很有必要的，評(píng)估函數(shù)代表了評(píng)判準(zhǔn)則，能有效地指引尋優(yōu)或搜索方向，這樣的結(jié)構(gòu)初步具備了演化計(jì)算的條件.由于人工智能算法的使用，替代密碼等傳統(tǒng)經(jīng)典加密方法已不再具有安全性.

2) 初級(jí)階段(1993～2000)

這一階段的典型代表是澳大利亞昆士蘭大學(xué)的Millan教授和他的研究小組——Clark等人，和同一時(shí)期的其他研究者不同，他們的研究工作主要集中在Boolean函數(shù)設(shè)計(jì)[15-19]和S盒設(shè)計(jì)[6]上，統(tǒng)稱為演化密碼部件設(shè)計(jì).

1999年在總結(jié)先前工作的基礎(chǔ)上，Millan首次在密碼學(xué)中提出生物演化搜索的概念[6]，即模擬生物演化過程或社會(huì)性行為建立模型來解決密碼學(xué)問題.他指出評(píng)估函數(shù)是演化算法中最重要的組成部分，任何演化計(jì)算都需要利用這個(gè)評(píng)估函數(shù)來評(píng)估當(dāng)前解的優(yōu)越性，給出精確的適應(yīng)值，使得任意2個(gè)解能夠進(jìn)行比較，選出其中較優(yōu)的解.文獻(xiàn)[6]中Millan使用了遺傳算法結(jié)合爬山法來設(shè)計(jì)高安全性的S盒.當(dāng)然，不單單是遺傳算法，包括后來出現(xiàn)的蟻群算法、粒子群算法等仿生算法都屬于這一演化計(jì)算的范疇，它們是解決密碼學(xué)問題的新的、強(qiáng)有力的工具.

Millan小組的研究很有意義，他們?yōu)檠莼艽a的研究開辟了一個(gè)新的領(lǐng)域，為后續(xù)密碼學(xué)者的研究指引了新的方向.所謂密碼部件，就是解決某個(gè)數(shù)學(xué)問題的算法.倘若這個(gè)數(shù)學(xué)問題屬于組合優(yōu)化或搜索范疇，那么該密碼部件就可以嘗試引入演化算法來提高該密碼部件的實(shí)現(xiàn)效率.

另外，在密碼分析領(lǐng)域，演化算法也有了新的應(yīng)用.除了常見的替代密碼分析外，還出現(xiàn)了對(duì)置換密碼(transposition cipher)[20]、背包密碼(knapsack cipher)[21-24]的演化分析，分析方法還是以遺傳算法為主.

3) 成熟階段多元化(2000～2005)

這一階段的典型代表是英國(guó)約克大學(xué)的Clark和他的研究小組成員——Jacob，Stepney等人.作為Millan的后繼者，他們?cè)谔剿髅艽a學(xué)演化計(jì)算方面所花費(fèi)的努力功不可沒.Clark在2001年發(fā)表的博士論文被公認(rèn)是介紹密碼學(xué)演化計(jì)算的最經(jīng)典文獻(xiàn)[25].他指出啟發(fā)式搜索算法的能力被極大地低估了，通過使用啟發(fā)式搜索方法，一定范圍的當(dāng)代密碼學(xué)問題可以被成功地破譯.他們的研究對(duì)象主要包括Boolean函數(shù)演化設(shè)計(jì)[26-28]、S盒演化設(shè)計(jì)[29-30]和安全協(xié)議演化設(shè)計(jì)[31-32].其中，安全協(xié)議演化設(shè)計(jì)是他在2000年提出的一個(gè)新的研究方向.在研究方法上，他們開始嘗試新的演化算法——蟻群算法，并在置換密碼分析中取得成功[33-34].

除了Clark等人取得的成就外，其他的學(xué)者在密碼學(xué)演化計(jì)算的研究中也取得了一些進(jìn)展，尤其是在密碼系統(tǒng)分析(破譯)領(lǐng)域.2002年西班牙學(xué)者Hernández等人采用遺傳算法替代窮舉方法搜索合適的掩碼，首次成功破譯了經(jīng)過1輪加密的TEA密碼(tiny encryption algorithm)[35].2004年Ali等人在對(duì)RSA公鑰密碼分析時(shí)，通過結(jié)合遺傳算法來增強(qiáng)傳統(tǒng)時(shí)序攻擊的能力，并指出增強(qiáng)后的時(shí)序攻擊同樣適用于對(duì)DSS和DSA的分析[36]，這是演化計(jì)算首次出現(xiàn)在公鑰密碼系統(tǒng)的分析中.

隨著密碼學(xué)演化計(jì)算的深入發(fā)展，我們國(guó)內(nèi)的一些密碼學(xué)者也開始接觸這一新興的研究方法.2002年武漢大學(xué)的張煥國(guó)教授等人首次在國(guó)內(nèi)提出演化密碼的概念和密碼算法的演化設(shè)計(jì)方法[37]，利用演化算法來加強(qiáng)DES分組密碼核心部件——S盒的抗差分性能，并分別以這些S盒組構(gòu)造DES，得到演化設(shè)計(jì)的DES密碼體制.以這篇文獻(xiàn)為指引，他們又利用模擬退火算法和局部爬山法對(duì)Bent函數(shù)進(jìn)行演化設(shè)計(jì)，能夠得到幾乎所有的6元Bent函數(shù)和部分的8元Bent函數(shù).他們的研究工作對(duì)國(guó)內(nèi)密碼學(xué)發(fā)展具有十分重要的意義，越來越多的國(guó)內(nèi)學(xué)者開始關(guān)注演化計(jì)算在密碼學(xué)中的應(yīng)用.

2004年國(guó)家信息安全重點(diǎn)實(shí)驗(yàn)室的陳華和馮登國(guó)設(shè)計(jì)了一種包含評(píng)估函數(shù)、貪婪策略和Hill Climbing的演化遺傳算法，利用該算法能夠得到高非線性度、低差分一致性的8×8雙射S盒，但在擴(kuò)散性和抗雪崩方面的效果不理想[38].

2005年陳華等人在Millan爬山法設(shè)計(jì)的高非線性S盒基礎(chǔ)上，研究如何同時(shí)改變S盒的3個(gè)輸出向量的位置來提高S盒的非線性度，提出了MHC算法，在爬山法的基礎(chǔ)上進(jìn)一步提高非線性度[39].

由于剛剛起步，這一時(shí)期國(guó)內(nèi)學(xué)者所做的研究工作更多地是學(xué)習(xí)和參照先前國(guó)外的研究成果.研究?jī)?nèi)容主要集中在Boolean函數(shù)設(shè)計(jì)、S盒設(shè)計(jì)和DES分析上.

4) 多樣化階段成熟，系統(tǒng)化學(xué)說化(2005～現(xiàn)在)

隨著密碼學(xué)演化計(jì)算的不斷發(fā)展，越來越多的密碼學(xué)者開始接受并認(rèn)可演化計(jì)算，并投身密碼學(xué)演化計(jì)算的研究中，極大地推動(dòng)了密碼學(xué)的發(fā)展.如印度管理技術(shù)研究所的Poonam從2005年開始接觸密碼學(xué)演化計(jì)算，他們的研究方向集中在簡(jiǎn)化的數(shù)據(jù)加密標(biāo)準(zhǔn)算法(SDES)中，并首次在密碼分析中使用文化基因算法[40].還有希臘帕特雷大學(xué)的Laskari等人，他們主要研究粒子群演化算法在Feistel等分組密碼分析中的應(yīng)用[41-43].他們的研究表明：密碼問題的公式形式或表達(dá)樣式是決定發(fā)揮智能算法性能的關(guān)鍵因素，可以歸結(jié)為離散組合優(yōu)化問題的密碼學(xué)問題才適用于智能算法解決.現(xiàn)有的密碼系統(tǒng)很少會(huì)泄露任何形式的密文信息或密文內(nèi)部結(jié)構(gòu)，通常情況下智能算法是分析密文的首選方法.

自2002年首次提出密碼學(xué)演化計(jì)算以來，國(guó)內(nèi)密碼學(xué)界的許多專家，如張煥國(guó)、馮登國(guó)、吳文玲、楊義先等研究團(tuán)隊(duì)，通過不斷的模仿和改進(jìn)，掌握了許多演化密碼設(shè)計(jì)的方法和技巧，在傳統(tǒng)的Boolean函數(shù)設(shè)計(jì)[44]、S盒設(shè)計(jì)[40]、DES分析[45]上取得了一定的研究成果，同時(shí)他們堅(jiān)持大膽創(chuàng)新，提出了許多新的研究方向和研究方法，如序列密碼分析[46-47]、NTRU分析[48]、ECC安全曲線選擇等，并在某些方面達(dá)到或超過了國(guó)外同行的研究水平.

現(xiàn)階段的密碼學(xué)演化計(jì)算的研究呈現(xiàn)出多樣化的發(fā)展趨勢(shì).在研究方法上，研究者不再單一地使用爬山法、模擬退火和遺傳算法，蟻群算法[49-50]、粒子群算法[51-52]、文化基因算法[40]等新興演化算法也開始得到廣泛應(yīng)用.另外，為了彌補(bǔ)應(yīng)用某種演化算法帶來的缺點(diǎn)，學(xué)者們通常會(huì)結(jié)合使用其他的優(yōu)化算法，達(dá)到優(yōu)勢(shì)互補(bǔ)的效果.目前已被提出和應(yīng)用的混合算法有：混沌模擬退火算法[53]、遺傳蟻群算法[54]、量子激勵(lì)的遺傳算法[55]等.在研究對(duì)象上，除了傳統(tǒng)的研究方向外，研究者開始嘗試更多的未知領(lǐng)域，如DES分析、SDES分析、ECC安全曲線構(gòu)造等.

2011年西北師范大學(xué)的馬宇紅、張杰針對(duì)單一演化算法的缺點(diǎn)而提出了一種新的蟻群爬山算法，并將其用于求解連續(xù)全局優(yōu)化問題，其精度和效率優(yōu)于蟻群算法[56].

2011年黃岡師范學(xué)院的Zhang和Hu設(shè)計(jì)可以用于遺傳算法的適應(yīng)度函數(shù)、交叉和變異策略，然后根據(jù)策略設(shè)計(jì)出產(chǎn)生大素?cái)?shù)的算法[57].

2014年四川師范大學(xué)的張凱通過對(duì)S盒初始種群的遺傳迭代演化，篩選出滿足特定密碼學(xué)性質(zhì)的S盒，同時(shí)分析了通過適應(yīng)函數(shù)與合適的種群規(guī)模，交叉變異算子的選擇，能夠提升遺傳算法構(gòu)建S盒的效率[54].

2017年深圳大學(xué)的王熙照和河北地質(zhì)大學(xué)的賀毅朝[5]對(duì)近10余年來利用演化算法(evolu-tionary algorithms, EAs)求解背包問題(knapsack problem, KP)的研究情況進(jìn)行了較為詳細(xì)的總結(jié)，為今后EAs求解KP提供可行的研究思路.

2018年湖北工業(yè)大學(xué)徐光輝等人[58]提出一種用于新的信號(hào)加密工程應(yīng)用的混沌系統(tǒng)，該系統(tǒng)成功的實(shí)現(xiàn)和制造是通過一個(gè)隨機(jī)數(shù)發(fā)生器的真實(shí)電路來實(shí)現(xiàn)的，應(yīng)用了2種最新的有效優(yōu)化方法:鯨魚優(yōu)化算法(whale optimization algorithm, WOA)和多維優(yōu)化算法(multi-verse optimizer algorithms, MVO)來優(yōu)化成本函數(shù).

3 國(guó)內(nèi)外研究現(xiàn)狀

目前，演化計(jì)算已經(jīng)進(jìn)入了密碼學(xué)的各個(gè)領(lǐng)域，但不同領(lǐng)域的發(fā)展情況各不相同，有些領(lǐng)域的演化設(shè)計(jì)水平已經(jīng)十分成熟，而有些領(lǐng)域的演化設(shè)計(jì)才剛剛開始.

3.1 Boolean函數(shù)設(shè)計(jì)

3.1.1 研究背景

布爾函數(shù)在密碼學(xué)、糾錯(cuò)編碼和擴(kuò)頻通信等領(lǐng)域有著廣泛的應(yīng)用.密碼學(xué)中經(jīng)常需要使用性能較好的布爾函數(shù)來設(shè)計(jì)密碼系統(tǒng)，而高非線性和低自相關(guān)性是構(gòu)造較好布爾函數(shù)所需要滿足的2個(gè)基本條件.滿足這2個(gè)條件的布爾函數(shù)能夠抵抗線性密碼分析和差分密碼分析，使密碼系統(tǒng)具有較高的安全性.因此，如何構(gòu)造具有高非線性且低自相關(guān)性的布爾函數(shù)是密碼學(xué)家長(zhǎng)期關(guān)注的問題.

3.1.2 布爾函數(shù)演化設(shè)計(jì)

1997年Millan等人提出利用爬山法(Hill Climbing)修改布爾函數(shù)真值表，通過不斷優(yōu)化真值表得到最優(yōu)的布爾函數(shù).與傳統(tǒng)的概率分布式隨機(jī)產(chǎn)生布爾函數(shù)相比，利用爬山法生成的最優(yōu)布爾函數(shù)在平衡性和非線性方面都有了提高.

同年，Millan等人又在以上爬山法的基礎(chǔ)上，增加使用了遺傳算法，提出利用遺傳學(xué)算法結(jié)合爬山法設(shè)計(jì)具有貪婪定向搜索功能的算法[15].遺傳算法的使用能夠快速地產(chǎn)生高非線性度的布爾函數(shù)，爬山法的結(jié)合同樣能夠加速這一過程，并且使得產(chǎn)生的布爾函數(shù)滿足平衡性和相關(guān)免疫性的條件.

2002年Clark[25]在Millan的研究基礎(chǔ)之上，首次提出利用模擬退火算法(simulated annealing, SA)設(shè)計(jì)滿足多種特性要求的布爾函數(shù)，其設(shè)計(jì)的布爾函數(shù)在綜合性能方面達(dá)到了新的高度.

2011年復(fù)旦大學(xué)Chunlin等人提出了使用基于遺傳算法構(gòu)造布爾函數(shù)的方法，使得到的布爾函數(shù)具有良好的加密外觀[59].

2011年Goyal等人[60]采用非支配排序遺傳算法II(NSGA-II)結(jié)合多目標(biāo)演化方法設(shè)計(jì)多指標(biāo)均衡的平衡布爾函數(shù)，實(shí)現(xiàn)了4元和5元布爾函數(shù)的設(shè)計(jì).

2012年印度理工學(xué)院的Goyal等人針對(duì)保密性強(qiáng)的布爾函數(shù)的許多理想特性中找到最佳的平衡這個(gè)難題，通過專注于非線性、自相關(guān)性和彈性這些特性，找到了一個(gè)進(jìn)化方法來構(gòu)建擁有最佳權(quán)衡4-5個(gè)變量的平衡布爾函數(shù)[61].

2013年Clark等人在低差分均勻性的情況下，使用模擬退火、文化基因算法和蟻群優(yōu)化進(jìn)行了分組密碼中的矢量布爾函數(shù)的創(chuàng)建[62].

2014年印度的Asthana等人提出了一種新的基于遺傳算法來產(chǎn)生強(qiáng)布爾函數(shù).該布爾函數(shù)擁有滿足平衡性、相關(guān)免疫性、代數(shù)次數(shù)和非線性特征的期望值[63].

2014年荷蘭內(nèi)梅亨大學(xué)的Picek等人，針對(duì)布爾函數(shù)在應(yīng)用中的一個(gè)主要的問題是要找到布爾函數(shù)的特定屬性，理論上應(yīng)該找到一個(gè)8 b輸入和非線性為118的平衡的布爾函數(shù)這個(gè)現(xiàn)象，專注于研究特定種類的布爾函數(shù)，并分析了通過整合代數(shù)和進(jìn)化計(jì)算為基礎(chǔ)方法尋找期望值，所獲得結(jié)果的形式應(yīng)比較靠近理論值[64].

2015年克羅地亞薩格勒布大學(xué)的Picek等人對(duì)遺傳編程(GP)和笛卡爾遺傳編程(CGP)分別在密碼分析中進(jìn)行構(gòu)建布爾函數(shù)進(jìn)行比較，這也是首次使用笛卡爾遺傳編程(CGP)對(duì)布爾函數(shù)進(jìn)行構(gòu)建，結(jié)果當(dāng)目標(biāo)獲得了盡可能高的非線性時(shí)，CGP比GP更好[65].

2016年P(guān)icek等人使用演化算法對(duì)密碼中的布爾函數(shù)進(jìn)行優(yōu)化[66]；同年，克羅地亞的Picek等人使用演化算法設(shè)計(jì)布爾函數(shù)，使布爾函數(shù)的非線性度得到了提升，并對(duì)不同演化算法設(shè)計(jì)布爾函數(shù)的有效性進(jìn)行了比較[67].

3.2 S盒設(shè)計(jì)與DES設(shè)計(jì)

3.2.1 研究背景

S盒是大多數(shù)分組密碼算法中唯一的非線性結(jié)構(gòu)，它的密碼強(qiáng)度決定了密碼算法的好壞，如何設(shè)計(jì)出良好的S盒是一個(gè)重要的研究問題.

1998年澳大利亞昆士蘭科技大學(xué)的Millan[68]提出一種通過對(duì)換S-盒輸出的2個(gè)值來提高S -盒的非線性度，實(shí)驗(yàn)表明通過隨機(jī)生成的方式難以獲得高非線性度的S-盒.

1999年Millan等人[69]提出基于遺傳算法獲得高非線性度S-盒的方法.實(shí)驗(yàn)表明，該方法獲得高非線性度的S-盒比窮舉搜索方法更具優(yōu)勢(shì).

2001年美國(guó)史蒂文斯理工學(xué)院的Jakimoski等人[70]第一次將混沌系統(tǒng)應(yīng)用到S-盒的構(gòu)造中，提出混沌映射構(gòu)造S -盒的方法，證明這些映射構(gòu)造的S-盒具有可以接受的非線性度和差分均勻度.

2005年重慶大學(xué)的Tang等人[71]提出使用混沌映射獲得S -盒的方法，詳細(xì)分析獲得的S -盒的雙射、非線性度、嚴(yán)格雪崩準(zhǔn)則和比特獨(dú)立準(zhǔn)則等密碼特性，結(jié)果表明所獲得的S-盒還可抵抗差分攻擊.

2005年英國(guó)謝菲爾德大學(xué)的Clark等人[72]展示如何尋找一個(gè)優(yōu)秀的單輸出布爾函數(shù)的成本函數(shù)，以便對(duì)小型S -盒提供改進(jìn).

2005年澳大利亞昆士蘭科技大學(xué)的Fuller等人[73]綜述了構(gòu)造雙射S -盒的啟發(fā)式方法，證明了通過冪映射可以進(jìn)化(僅通過迭代變異算子)來生成雙射S -盒.

2008年波蘭波德拉謝大學(xué)的Szaban等人[74]提出了一個(gè)基于細(xì)胞自動(dòng)機(jī)(cellular automata)生成S -盒的方法，結(jié)果表明基于細(xì)胞自動(dòng)機(jī)的S -盒有相對(duì)于經(jīng)典S -盒更好的密碼屬性.

2008年新西蘭坎特伯雷大學(xué)的Linham等人[75]提出了一個(gè)使用啟發(fā)式方法來構(gòu)造S -盒的方法，其目標(biāo)是生成符合嚴(yán)格雪崩準(zhǔn)則(SAC)，非線性且對(duì)差分密碼分析具有高度抵抗力的S -盒.

2011年12月哈爾濱工程大學(xué)的畢曉君等人針對(duì)傳統(tǒng)方法設(shè)計(jì)S盒存在的設(shè)計(jì)時(shí)間過長(zhǎng)、易陷入局部最優(yōu)的缺點(diǎn)，提出了一種基于改變粒子群優(yōu)化算法的S盒優(yōu)化設(shè)計(jì)方法[76]，通過改變慣性權(quán)重來提高搜索速度和精度來增大算法效率，從而快速地搜索到能有效抵抗差分密碼分析和線性密碼分析的S盒，改善密碼性能.

2012年國(guó)防科技大學(xué)的李亞鵬等人對(duì)遺傳算法構(gòu)造S盒進(jìn)行優(yōu)化[77]，使得其在密碼學(xué)性能、收斂速度和適應(yīng)度值方面有很好的改善.該方法是在初始種群的生成過程中加入由先驗(yàn)知識(shí)產(chǎn)生的部分性能較優(yōu)的S盒，在一定程度上提高收斂效果和收斂速度;采用最優(yōu)個(gè)體保存法選擇策略執(zhí)行遺傳算子操作，可以大幅減少額外的計(jì)算量;采用Davis順序交叉法執(zhí)行交叉操作，引入進(jìn)化逆轉(zhuǎn)變異法執(zhí)行變異操作，補(bǔ)償群體中多樣性易損失的不足，同時(shí)能夠提高算法的搜索效率，加快收斂速度.

2012年8月重慶大學(xué)的Wang等人[78]將混沌和遺傳算法結(jié)合起來構(gòu)造更高密碼性質(zhì)的S盒的方法，比單純使用混沌的方法更好地構(gòu)造更強(qiáng)的S盒.

2013年McLaughlin等人提出了一個(gè)確定算法來尋找非線性S盒.“過濾”(filtered)非線性攻擊是目前對(duì)降低輪蛇(reduced-round Serpent)在達(dá)到任意已知明文攻擊的最低數(shù)據(jù)復(fù)雜度，并且已經(jīng)證明了錯(cuò)誤密鑰隨機(jī)假設(shè)對(duì)降低輪蛇的攻擊是不完全有效的，降低輪蛇是依賴于現(xiàn)行密碼分析或者其變體[79].

2013年McLaughlin等人利用模擬退火算法找到對(duì)于各種S盒的非線性逼近，這些S盒在現(xiàn)有的外輪攻擊中可以用于代替線性近似，并提出了11輪蛇的一個(gè)新的攻擊方法，它比任何已知明文攻擊或者選擇明文攻擊都有更好的數(shù)據(jù)復(fù)雜度，它對(duì)于256位密鑰有最佳的整體時(shí)間復(fù)雜度[80].

2014年突尼斯的斯法克斯大學(xué)的Guesmi等人提出了基于混沌函數(shù)和遺傳算法的新方法來設(shè)計(jì)強(qiáng)大的替代盒，并分析了S盒的強(qiáng)度，通過對(duì)7輪S盒的數(shù)值分析表明其較好的S盒近似，并且它們具有較高的抵抗免疫差分分析的能力[81].

2014年馬來西亞國(guó)油大學(xué)Khan等人設(shè)計(jì)了一個(gè)新的基于混沌的S盒，通過使用DDY(DDT可以有助于對(duì)S盒進(jìn)行差分分析)的系統(tǒng)優(yōu)化來進(jìn)行動(dòng)態(tài)設(shè)計(jì).該S盒與其他基于混沌的S盒設(shè)計(jì)相比，有非常低的差分概率，其差分近似概率為8256[82].

2015年清華大學(xué)的覃冠杰等人[83]提出了使用人工蜂群算法來實(shí)現(xiàn)隨機(jī)S -盒的全局優(yōu)化，實(shí)驗(yàn)結(jié)果驗(yàn)證該算法的有效性，可以同時(shí)優(yōu)化S-盒的非線性、微分特性和擴(kuò)散特性.

2015年重慶郵電大學(xué)的Wang等人[84]提出了一種結(jié)合混沌和優(yōu)化運(yùn)算構(gòu)造具有高非線性度S-盒的新方法.實(shí)驗(yàn)結(jié)果表明，該方法構(gòu)造的S-盒比僅基于混沌映射構(gòu)造的S-盒具有更高的非線性度.

2016年P(guān)icek等人[85]基于目前最先進(jìn)的適應(yīng)度函數(shù)進(jìn)行實(shí)驗(yàn)分析，提出了一個(gè)能提供更高速度以及更優(yōu)結(jié)果的新的適應(yīng)度函數(shù).

2016年Ahmad等人[86]探索了旅行商問題和分段線性混沌映射來合成有效的8×8的S盒，研究結(jié)果表明，根據(jù)預(yù)期設(shè)計(jì)的S盒將具有更好的保密特性.

2017年日本安全平臺(tái)實(shí)驗(yàn)室的Yu等人[87]在歐密會(huì)上提出一種搜索不可能差分的新工具，可以用于檢測(cè)任何輸入和輸出差分.同時(shí)，該工具也可用于8元S盒性能的檢測(cè)，也可考慮用于未來S盒的設(shè)計(jì)優(yōu)化.

建立在S盒基礎(chǔ)之上的DES也同樣面臨這個(gè)問題.目前，對(duì)DES類分組密碼的主要攻擊方法有窮舉攻擊、差分攻擊和線性分析等，而差分分析和線性分析便直接針對(duì)DES中的S盒組合密碼的迭代結(jié)構(gòu).因此，演化DES的核心就是演化S盒組，使之符合某種安全準(zhǔn)則.S盒的安全準(zhǔn)則主要有：非線性準(zhǔn)則、雪崩準(zhǔn)則和擴(kuò)散準(zhǔn)則[37].

2017年荷蘭代爾夫特理工大學(xué)的Picek等人[88]介紹了演化細(xì)胞自動(dòng)機(jī)規(guī)則的概念，該啟發(fā)式方法能夠?yàn)?×4到7×7的尺寸選擇最佳的S-盒.

2017年哈爾濱工程大學(xué)的Tian等人[89]提出了一個(gè)基于交織的邏輯映射(the intertwining logistic map)和細(xì)菌覓食優(yōu)化的混沌S-盒的方法.該S -盒可以有效抵抗多種類型的密碼分析攻擊.

2017年突尼斯埃爾馬納爾大學(xué)的Farah等人[90]提出了一個(gè)基于混沌映射和教與學(xué)優(yōu)化(teaching-learning-based optimization)算法獲取強(qiáng)S-盒的新方法，實(shí)驗(yàn)表明該方法設(shè)計(jì)的S -盒具有良好的密碼學(xué)特性，可以抗多種攻擊.

2017年巴基斯坦塔克西拉工程技術(shù)大學(xué)的Khan等人[91]提出了利用差分分布表(difference distribution table)生成混沌S -盒的構(gòu)造方法.實(shí)驗(yàn)表明，該方法獲得的S-盒顯示出非常低的差分均勻度，同時(shí)保持良好的密碼特性.

2018年印度國(guó)立伊斯蘭大學(xué)的Ahmad等人[92]提出構(gòu)建一個(gè)基于人工蜂群優(yōu)化和混沌映射的S-盒的構(gòu)造方法.該算法旨在優(yōu)化初始S-盒以滿足密碼學(xué)特性，構(gòu)造具有高強(qiáng)度的S-盒.

2019年意大利米蘭比科卡大學(xué)的Mariot等人[93]對(duì)基于細(xì)胞自動(dòng)機(jī)的S -盒的密碼特性進(jìn)行了系統(tǒng)的研究，證明了該S -盒的非線性度和差分均勻度的上界.

3.2.2 DES的演化設(shè)計(jì)

1999年Millan指出啟發(fā)式組合優(yōu)化算法非常適用于替代盒(S盒)的設(shè)計(jì)，其設(shè)計(jì)出的盒具有較高的非線性度和低自相關(guān)性[6].他在試驗(yàn)中采用了遺傳學(xué)算法，通過不斷“同化”操作，綜合前代不同S盒的優(yōu)點(diǎn)，產(chǎn)生新一代具有更優(yōu)性能的S盒，最終收斂到當(dāng)前最優(yōu)解.

2004年Clark等人利用模擬退火算法在構(gòu)造單輸出布爾函數(shù)上獲得了很好的效果[30].事實(shí)上，S盒是由若干個(gè)布爾輸入和輸出組成的，因此，S盒的設(shè)計(jì)可以仿照演化算法在布爾函數(shù)中的應(yīng)用.同年，他將該模擬退火算法推廣到S盒的設(shè)計(jì)中.

2002年武漢大學(xué)的張煥國(guó)教授等人首次在國(guó)內(nèi)提出演化密碼的概念和密碼算法的演化設(shè)計(jì)方法[37]，利用演化算法來加強(qiáng)DES分組密碼核心部件——S盒的抗差分性能，并分別以這些S盒組構(gòu)造DES，得到演化設(shè)計(jì)的DES密碼體制.

2012年印度的Jadon等人使用二進(jìn)制粒子優(yōu)化算法策略來進(jìn)行DES對(duì)稱密鑰密碼算法進(jìn)行密碼分析.該方法可以確定56 b密鑰比特中的42 b密鑰比特的位置，BPSO可以用來尋找剩下的14 b密鑰比特[94].

2013年Khan等人提出了一種新的基于螞蟻密碼攻擊的群，并將其應(yīng)用于簡(jiǎn)單數(shù)據(jù)加密(DES)的密碼分析中，該方法使用已知明文攻擊來恢復(fù)DES的密鑰，并對(duì)密鑰進(jìn)行迭代搜索，這些密鑰通過螞蟻在不同運(yùn)行路線的基礎(chǔ)上完成而得到一些候選最佳密鑰，然后這些最佳密鑰用來尋找DES加密中的56 b密鑰中的每個(gè)單獨(dú)的比特.與遺傳算法和二進(jìn)制粒子群算法相比，該方法對(duì)DES產(chǎn)生更有效的攻擊，且可以減少值的位數(shù)[95].

2012年Rajashekarappa等人提出使用禁忌搜索算法對(duì)S-DES進(jìn)行密碼分析的方法.該方法采用了唯密文攻擊和基于成本函數(shù)值的多種類最佳密鑰的產(chǎn)生，從而能夠更快的找到S-DES密鑰[96].

2014年Teytaud等人利用啟發(fā)式算法(meta-heuristics)，特別是遺傳算法對(duì)S-DES進(jìn)行密碼分析，實(shí)驗(yàn)表明遺傳算法的性能比隨機(jī)搜索差[97].

2015年Dworak等人對(duì)于S-DES(簡(jiǎn)化數(shù)據(jù)加密標(biāo)準(zhǔn))提出了一種新的密碼分析攻擊.該攻擊是對(duì)BPSO(二進(jìn)制粒子群優(yōu)化算法)進(jìn)行修改，它可以在給定的時(shí)間周期內(nèi)對(duì)獲得結(jié)果的質(zhì)量產(chǎn)生積極的影響[98].

2017年波蘭西里西亞大學(xué)的Dworak等人[99]提出了一種針對(duì)DES6加密算法的遺傳差分密碼分析方法，可以將數(shù)據(jù)加密標(biāo)準(zhǔn)(DES)的新差異攻擊減少到6輪.結(jié)果表明，該方法可以在85%的情況下破壞K6K6的有效部分.

2018年摩洛哥ChouaibDoukkali大學(xué)Grari等人[100]提出了一種新的基于蟻群優(yōu)化(ACO)的攻擊，用于簡(jiǎn)化數(shù)據(jù)標(biāo)準(zhǔn)加密(S-DES)的密碼分析.實(shí)驗(yàn)結(jié)果表明，與其他攻擊相比，該方法的攻擊速度明顯加快，并且需要少量已知的明文-密文對(duì),ACO可以作為攻擊S-DES中使用的密鑰的有力工具.

3.3 序列密碼設(shè)計(jì)

3.3.1 研究背景

序列密碼是密碼學(xué)的一個(gè)重要分支，由于人們對(duì)序列密碼的研究比較充分，再加上其具有實(shí)現(xiàn)容易、效率高等特點(diǎn)，所以序列密碼稱為許多重要應(yīng)用領(lǐng)域的主流密碼.序列密碼的基本原理就是通過明(密)文和移位寄存器產(chǎn)生的密鑰序列模2加來完成加(解)密的過程，因此序列密碼的關(guān)鍵是產(chǎn)生密鑰序列的算法.

3.3.2 序列密碼的演化設(shè)計(jì)

2008年武漢大學(xué)的陳連俊等人利用演化算法對(duì)濾波模型流密碼進(jìn)行了密碼分析.實(shí)驗(yàn)表明，該方法具有較小的演化代數(shù)和較高的成功率，能夠減少密碼分析過程中試探密鑰的次數(shù)，其分析復(fù)雜度遠(yuǎn)遠(yuǎn)低于窮舉攻擊的復(fù)雜度[46].

2010年陳連俊等人又對(duì)組合模型序列密碼中的Geefe發(fā)生器和門限發(fā)生器進(jìn)行分析.實(shí)驗(yàn)結(jié)果表明，演化計(jì)算在序列密碼相關(guān)分析中有重要作用，其中如何設(shè)計(jì)好適應(yīng)度函數(shù)和選擇、雜交、變異等演化算子是演化算法的關(guān)鍵[47].

2011年Crainicu等人提出一種基于禁忌搜索算法密碼分析攻擊，該禁忌搜索算法試圖重建RC4內(nèi)部狀態(tài)[101].

2014年7月江西理工大學(xué)的吳君欽等人針對(duì)傳統(tǒng)序列密碼算法中出現(xiàn)的生成序列密碼重碼率高和容易陷入局部最優(yōu)解等缺點(diǎn)，提出了一種基于多目標(biāo)差分演化的序列密碼算法.利用該算法產(chǎn)生的序列密碼能夠較好地通過各項(xiàng)隨機(jī)性檢驗(yàn)，使用該算法產(chǎn)生了256 b的二進(jìn)制隨機(jī)序列.統(tǒng)計(jì)分析表明，此序列具有很好的隨機(jī)性，相比傳統(tǒng)演化算法生成的序列，具有更高的隨機(jī)性和安全性[102].

2015年波蘭的西里西亞大學(xué)的Polak等人使用遺傳算法對(duì)流密碼進(jìn)行分析，來尋找線性移位反饋寄存器近似給定密鑰流的最短等效線性系統(tǒng)逼近[103].

2016年印度理工學(xué)院Kumar等人[104]討論了遺傳算法在流密碼中的應(yīng)用.密鑰生成是流密碼中最重要的因素.這里重復(fù)使用遺傳算法進(jìn)行密鑰選擇.在每次迭代中，選擇適應(yīng)度值最高的鍵，并與閾值進(jìn)行比較,所選的鍵是唯一且不重復(fù)的.因此，所選密鑰的加密由于密鑰的隨機(jī)性更強(qiáng)而具有高度加密性.結(jié)果表明，使用遺傳算法生成的密鑰是唯一的，對(duì)數(shù)據(jù)加密更加安全.

2018年印度海德拉巴大學(xué)Krishna 等人[105]在雙目標(biāo)開發(fā)改進(jìn)和聲搜索算法與差分進(jìn)化算法結(jié)合的密鑰生成算法.在單目標(biāo)優(yōu)化框架中開發(fā)第二代非支配排序遺傳算法的密鑰生成算法，然后對(duì)編碼的密鑰流以及編碼的純文本進(jìn)行加密，以生成密文.

3.4 NTRU破譯

NTRU公鑰密碼體制是目前后量子密碼的研究熱點(diǎn)之一.2005年解放軍理工大學(xué)的趙小龍等人提出利用遺傳算法對(duì)于NTRU公鑰密碼體制一種攻擊方法[48].因?yàn)镹TRU的私鑰不是唯一的，而是滿足一定條件的解集，他們將私鑰的樣本空間看作一個(gè)種群，私鑰的每一種取值都看作個(gè)體，在定義相應(yīng)的適應(yīng)度函數(shù)后，搜索密鑰就轉(zhuǎn)化為找尋適應(yīng)度最好的個(gè)體.

算法的核心部分包括3個(gè)內(nèi)容：1)編碼；2)適應(yīng)度函數(shù)設(shè)計(jì)；3)遺傳算子設(shè)計(jì).若公鑰和私鑰系數(shù)中為1的項(xiàng)數(shù)已知，那么根據(jù)上述3個(gè)內(nèi)容即可用遺傳算法搜索私鑰的樣本空間，尋找適應(yīng)度最好的樣本，其工作流程與經(jīng)典的遺傳算法類似.

2009年解放軍理工大學(xué)的唐元?jiǎng)偟热薣106]利用格理論結(jié)合遺傳算法對(duì)NTRU進(jìn)行攻擊，并對(duì)算法的循環(huán)交叉操作進(jìn)行分析，交叉概率取值為0.7～0.9之間時(shí)，對(duì)搜索結(jié)果影響較大.實(shí)驗(yàn)表明，遺傳算法與一般搜索算法相比，具有一定的有效性和穩(wěn)定性.NTRU搜索空間隨其標(biāo)準(zhǔn)格維數(shù)增大呈指數(shù)級(jí)增長(zhǎng)，所以需要構(gòu)建巨大數(shù)量的初始種群，運(yùn)算量較大.

2016年3月印度的Agrawal和Sharma分別使用蟻群優(yōu)化算法(ACO)和粒子群優(yōu)化算法(PSO)對(duì)NTRU進(jìn)行算法的優(yōu)化.模擬結(jié)果顯示，與傳統(tǒng)NTRU速度相比，使用蟻群優(yōu)化算法(ACO)和粒子群優(yōu)化算法(PSO)優(yōu)化后的NTRU平均速度增加百分比分別為34.65%和41.31%，優(yōu)化后的NTRU算法速度大大提升[107].

2016年Agrawal和Sharma在保證較低時(shí)間復(fù)雜度的情況下，使用遺傳算法(GA)、蟻群算法(ACO)和粒子群算法(PSO)對(duì)NTRU進(jìn)行優(yōu)化.實(shí)驗(yàn)結(jié)果表明，相對(duì)于其他演化算法，使用粒子群算法進(jìn)行優(yōu)化時(shí)，NTRU的復(fù)雜度最高[108]，復(fù)雜度為O(Nlog(N+1)3)(N為素?cái)?shù))，而傳統(tǒng)NTRU復(fù)雜度為O(NlogN)，意味著使用粒子群算法的NTRU提供了更高的安全性.

3.5 ECC安全曲線選擇

3.5.1 研究背景

1985年Koblitz和Miller兩位密碼學(xué)家分別獨(dú)立地提出了橢圓曲線公鑰密碼體制[1].目前，國(guó)際各個(gè)標(biāo)準(zhǔn)組織，如ANSI，NIST，SECG等，所公布的安全曲線數(shù)量一共不超過30條.由于ECC的研究在中國(guó)起步較晚，中國(guó)還沒有一條屬于自己推薦的安全曲線.國(guó)內(nèi)的工程應(yīng)用絕大多數(shù)都是使用美國(guó)NIST所推薦的15條曲線.但問題是這些標(biāo)準(zhǔn)組織之間對(duì)橢圓曲線的安全定義并不相同，表現(xiàn)在所推薦的曲線數(shù)量的不同，如SECG推薦了25條，NIST推薦了15條，而ANSI只推薦了2條.其中只有2條曲線是這3個(gè)組織都共同推薦的，其他的曲線有些推薦了，有些沒推薦.因此，我們?cè)谑褂眠@些曲線時(shí)，難免會(huì)產(chǎn)生3個(gè)疑問：1)如何判定這些曲線是真正意義上的安全？2)這些曲線是否存在某些人為或者非人為的缺陷？3)中國(guó)應(yīng)該怎樣選擇自己的安全曲線？

3.5.2 ECC安全曲線選擇的演化設(shè)計(jì)

長(zhǎng)期以來演化計(jì)算在橢圓曲線公鑰密碼中的應(yīng)用一直是一個(gè)空白.自2004年起，上海大學(xué)王潮教授與武漢大學(xué)的張煥國(guó)教授等人共同提出基于演化計(jì)算的安全橢圓曲線快速選擇算法[109].

進(jìn)一步，王潮教授等人提出了一種基于演化密碼和HMM改進(jìn)的Koblitz安全曲線產(chǎn)生新方法，利用隱Markov模型(HMM)預(yù)測(cè)跡向量解決基點(diǎn)計(jì)算難題，完成了F(22000)以內(nèi)Koblitz安全曲線的搜索實(shí)驗(yàn)，產(chǎn)生的安全曲線基域的覆蓋范圍、曲線的規(guī)模和產(chǎn)生的效率均超過美國(guó)NIST的公開報(bào)道參數(shù)，可提供的安全曲線的基域和基點(diǎn)最高超過1 900 b，遠(yuǎn)超過美國(guó)NIST公布的571 b，在NIST公布的F(2163)～F(2571)范圍之間還有新的安全曲線的發(fā)現(xiàn)，其所產(chǎn)生的安全曲線與NIST推薦的安全曲線具有相同的安全準(zhǔn)則[110-112].

2016年芬蘭圖爾庫(kù)大學(xué)的Sahebi等人針對(duì)橢圓曲線選擇這個(gè)難題，提出了一種有效的橢圓曲線選擇框架(SEECC)，即通過并行遺傳算法來選擇橢圓曲線中的一條安全有效的曲線，從而提高了橢圓曲線密碼體制的安全性和有效性[113].

2018年印度學(xué)者Sujatha等人[114]提出一種改進(jìn)的橢圓曲線密碼體制下的選民身份驗(yàn)證的方法，選民使用私鑰，公鑰用于對(duì)選民進(jìn)行身份驗(yàn)證.ECC中私鑰的選擇是通過使用布谷鳥搜索優(yōu)化技術(shù)而不是隨機(jī)選擇值，且該方法使用實(shí)時(shí)樣本數(shù)據(jù)庫(kù)進(jìn)行了增強(qiáng).

3.6 換位密碼(transposition cipher)、替換密碼

2011年電氣與電子技術(shù)學(xué)院的Omran等人對(duì)多字母替換密碼使用遺傳算法進(jìn)行密碼分析，研究了遺傳算法在搜索密鑰空間的適應(yīng)性[115].

2011年印度內(nèi)達(dá)吉蘇巴斯技術(shù)學(xué)院的Luthra等人探討了在引入了螢火蟲算法的遺傳算法中使用的變異算子和一般的交叉算子融合，來對(duì)單表替換密碼進(jìn)行密碼分析的問題[116].

2015年印度的Mishra等人使用了爬山算法、模擬退火算法和兩者的結(jié)合來攻擊唯密文攻擊模式下的換位密碼[117].

2015年印度尼西亞的Telkom大學(xué)的Wulandari等人將差分進(jìn)化用于解決整數(shù)問題置換，用差分進(jìn)化來攻擊換位密碼，從而表明了差分進(jìn)化能夠用于正確的解密有高達(dá)9的排列長(zhǎng)度，但是開始在10個(gè)排列長(zhǎng)度為10的模擬中有一半不正確答案的密文[118].

2018年土耳其薩卡里亞大學(xué)Demirci等人[119]提出了一種新的基于交換的粒子群優(yōu)化算法移動(dòng)算子.該實(shí)驗(yàn)測(cè)試了操作符的換位密碼加密，文本大小為125,250,500和750個(gè)字母，密鑰長(zhǎng)度為5,10,15.在大多數(shù)情況下，該算法可恢復(fù)70%的密鑰.

3.7 背包問題分析

2011年浙江科技大學(xué)的Shen等人使用一種基于雙種群遺傳算法的改進(jìn)方法求解0-1背包問題，克服了早熟和在迭代過程中的局部收斂的問題[120].

2011年北京工業(yè)大學(xué)的Wei等人提出了一種新的人工蜂群算法解決多維背包問題，介紹了引力的信息素并提出了一種基于吸引力信息素的過渡策略.在算法中，偵查員根據(jù)轉(zhuǎn)型策略生成食物來源，并通過與相應(yīng)的精英食物源進(jìn)行比較來替換廢棄的食物來源，采用蜜蜂和旁觀者使用食物來源鄰域確定的過渡策略來修改修復(fù)算子[121].

2011年國(guó)立卡南大學(xué)的Chou等人提出了一種新的量子進(jìn)化算法，即量子禁忌搜索(QTS)，來解決0-1背包問題，其性能優(yōu)于其他方法(如量子進(jìn)化算法QEA)，沒有過早收斂，同時(shí)具有更高的效率[122].

2012年馬來西亞多媒體大學(xué)的Lee等人提出了優(yōu)先列表的蟻群算法與突變(PACOM)算法求解多維背包問題，并應(yīng)用在MKP中[123].

2012年Taheri等人提出了在Win-Azure’s PaaS環(huán)境中使用并行遺傳算法(PGA)解決云背包問題，這是首次將遺傳算法應(yīng)用到云背包問題上[124].

2012年中原工學(xué)院的Ling等人提出了使用改進(jìn)的粒子群算法解決了小規(guī)模的背包問題，該算法克服了標(biāo)準(zhǔn)的粒子群算法的缺點(diǎn)，即容易陷入局部最優(yōu)解且具有收斂精度低.當(dāng)超過背包的承重時(shí)，適應(yīng)度將為零.當(dāng)單個(gè)粒子的最佳位置與所有粒子的最佳位置相同，則粒子的位置將被重新初始化[125].

2012年黃河科技學(xué)院的 Ma提出結(jié)合貪婪變換算法的改進(jìn)的自適應(yīng)遺傳變換算法來解決0-1背包問題，能夠收斂到全局最優(yōu)解而不至于過早收斂，且具有更快的收斂速度、更高的魯棒性和更可靠的穩(wěn)定性[126].

2013年哈爾濱工業(yè)大學(xué)的Chen等人提出了使用基于MPI的并行人工魚群算法求解多維0-1背包問題.該算法能有效地縮短處理時(shí)間，且解決了使用基本的人工魚群算法解決多維0-1問題出現(xiàn)的問題規(guī)模變大時(shí)數(shù)據(jù)維數(shù)增加，從而難以滿足實(shí)際要求的難題[127].

2013年Konggu工程學(xué)院的Tharanipriya等人提出了將多聚類遺傳算法與粗糙集理論結(jié)合的一種改進(jìn)的混合遺傳算法，解決了傳統(tǒng)聚類算法局部最優(yōu)的問題，能夠很好地應(yīng)用于0-1背包問題中[128].

2013年Jin等人對(duì)傳統(tǒng)的遺傳算法進(jìn)行了改進(jìn)，基于遺傳和免疫問題提出了一種解決0-1背包問題的新的免疫遺傳算法，它可以提高算法的收斂速度，避免遺傳算法優(yōu)化過程中的退化問題[129].

2013年印度的大學(xué)技術(shù)研究所的Samanta等人提出了螞蟻舉重算法(AWL)用來解決01背包問題，結(jié)果顯示了相對(duì)于廣泛使用的遺傳算法來說，該方法在性能和時(shí)間復(fù)雜度上有顯著提高[130].

2014年泰國(guó)Mahanakon科技大學(xué)的Anantathanavit等人提出了求解0-1背包問題和多維背包問題的算法.該算法融合了二進(jìn)制粒子群優(yōu)化算法(BPSO)和模擬退火以達(dá)到目標(biāo)利益最大，其最大的貢獻(xiàn)是通過在局部最優(yōu)上使用雜交BPSO和模擬退火的方法來擺脫局部最優(yōu)從而達(dá)到全局最優(yōu).該方法比單獨(dú)使用二進(jìn)制粒子群優(yōu)化算法或者單獨(dú)使用模擬退火算法的效果更好[131].

2014年印度的帕爾大學(xué)的Pradhan等人介紹了一種將遺傳算法和粗糙理論相結(jié)合來求解0-1背包問題的混合算法，遺傳算法提供了一種線性時(shí)間復(fù)雜度為21時(shí)解決背包問題的方法，結(jié)合了粗糙集理論的屬性約簡(jiǎn)技術(shù)，從而減少了搜索空間和保證了有效信息不會(huì)丟失，在遺傳算法中使用粗糙集理論，提高了遺傳算法的搜索效率和質(zhì)量[132].

2015年香港大學(xué)的Li等人介紹了一種基于變異矩陣的自適應(yīng)遺傳算法，用于求解擁有更高復(fù)雜度和結(jié)構(gòu)的一系列的01背包問題，對(duì)使用簡(jiǎn)單背包、平行背包和分層背包3種不同背包問題的數(shù)值結(jié)果進(jìn)行了討論，以及它們的不同效率的啟發(fā)式解釋.從而得到，自適應(yīng)變異矩陣是最好的，因此，突變的概率是隱時(shí)間依賴的[133].

2015年土耳其耶爾德茲技術(shù)大學(xué)的Uslu針對(duì)背包問題中“包的容量”或者“材料的類型數(shù)量”等問題變量增加時(shí)，問題規(guī)模的復(fù)雜度也會(huì)顯著增加這個(gè)問題，采用了遺傳算法來求解0-1背包問題[134].

2015年土耳其的Yasar大學(xué)的Tasgetiren等人首次提出了一種可變鄰域搜索的差分進(jìn)化算法來解決多維背包問題.為了提高解的質(zhì)量，還將使用變鄰域搜索的差分進(jìn)化算法與二進(jìn)制交換本地搜索算法相結(jié)合[135].

2015年阿爾及利亞的Rezoug等人提出了解決多維背包問題的文化基因算法，首先將遺傳算法與一個(gè)隨機(jī)的本地搜索結(jié)合(GA-SLS)，然后再與模擬退火算法結(jié)合[136].

2017年河北地質(zhì)大學(xué)的賀毅朝等人[137]提出一種基于動(dòng)態(tài)規(guī)劃的求解隨機(jī)時(shí)變背包問題(randomized time-varying knapsack problem, RTVKP)的精確算法.實(shí)驗(yàn)表明，該方法比已有的精確算法更適于求解背包載重較大的RTVKP問題.

2017年2月空軍工程大學(xué)的薛俊杰等人[138]通過構(gòu)建一種二進(jìn)制反向?qū)W習(xí)方法將煙花算法應(yīng)用于求解多維背包問題.實(shí)驗(yàn)表明，求解多維背包問題中，二進(jìn)制反向?qū)W習(xí)煙花算法具有較高的尋優(yōu)精度、良好的收斂效率和魯棒性.

2019年印度泰米爾納德邦VIT大學(xué)的Abdel-Basset等人[139]提出了一種改進(jìn)的鯨魚優(yōu)化算法(IWOA)，用于解決不同尺度的單維和多維0-1背包問題.實(shí)驗(yàn)結(jié)果表明，與已有文獻(xiàn)的方法相比，IWOA方法在求解0-1背包問題更有效且具魯棒性.

2019年土耳其Dokuz Eylül大學(xué)的Ozsoydan等人[140]提出了一種基于遺傳算法和粒子群優(yōu)化的簡(jiǎn)單而有效的二元群智能技術(shù).實(shí)驗(yàn)研究表明，該方法與已有文獻(xiàn)的結(jié)果相比，得到顯著的改進(jìn)，且該方法可方便地應(yīng)用于其他元啟發(fā)式算法中，提高算法的效率.

3.8 隨機(jī)數(shù)的產(chǎn)生

2013年印度得利科技大學(xué)的Jhajharia等人針對(duì)公鑰密碼系統(tǒng)偽隨機(jī)數(shù)生成器(PRNG)廣泛應(yīng)用于生成特定的密鑰和人工神經(jīng)網(wǎng)絡(luò)(ANN)中的隨機(jī)數(shù)，且ANN已發(fā)現(xiàn)有很多種可能的攻擊問題，提出了使用遺傳算法的人工神經(jīng)網(wǎng)絡(luò)(ANN)的公鑰密碼系統(tǒng)密鑰產(chǎn)生方法.該方法克服了ANN傳統(tǒng)PRNG生成隨機(jī)數(shù)的缺點(diǎn)，對(duì)于生成的公鑰和私鑰，要使用不同數(shù)量的混合輪，保證私鑰的生成不會(huì)由公鑰得到[141].

2011年西班牙的Cárdenas-Montes等人介紹了4種進(jìn)化算法在性能上對(duì)隨機(jī)數(shù)生成器的變化所產(chǎn)生的影響：粒子群優(yōu)化、差分進(jìn)化、遺傳算法和螢火蟲算法[142].

2017年捷克學(xué)者Chlumecky等人[143]提出一種利用遺傳算法(GA)對(duì)降雨徑流模型進(jìn)行優(yōu)化的新方法.遺傳算法使用進(jìn)化原理結(jié)合隨機(jī)數(shù)生成器估計(jì)模型參數(shù).實(shí)驗(yàn)結(jié)果表明，該方法在模型的輸出質(zhì)量上呈現(xiàn)出穩(wěn)定的趨勢(shì).與以往的研究相比，該方法加速了模型的標(biāo)定，并對(duì)降雨徑流模型進(jìn)行了改進(jìn).

2019年赫瑞-瓦特大學(xué)Zanforlin等人[144]提出了一種基于2個(gè)獨(dú)立連續(xù)波激光源間采樣相位隨機(jī)化的光學(xué)量子隨機(jī)數(shù)生成器(QRNG)算法.詳細(xì)分析了基于QRNG的外差測(cè)量方法，以Kullback-Leibler散度為基準(zhǔn)，量化了設(shè)置偏差的影響，以評(píng)估安全隨機(jī)數(shù)生成的限制條件.

4 量子人工智能密碼設(shè)計(jì)與分析

4.1 量子人工智能密碼設(shè)計(jì)

量子環(huán)境下的密碼理論研究目前主要包含3類，且都是國(guó)外學(xué)者提出的：1)Shor算法等通用量子算法對(duì)公鑰密碼的攻擊；2)抗量子密碼研究，比如基于NP問題的格密碼研究；3)量子密碼研究.

上海大學(xué)王潮教授等人獨(dú)立提出第4類研究：(基于量子人工智能的)量子計(jì)算機(jī)密碼設(shè)計(jì).之前，國(guó)際上暫未發(fā)現(xiàn)通用及專用2類量子計(jì)算機(jī)用于密碼設(shè)計(jì)領(lǐng)域的公開研究及報(bào)道.

在2012年王潮教授等人[145]提出D-Wave量子計(jì)算機(jī)設(shè)計(jì)密碼的潛力和可行性，以對(duì)稱密碼體制中的關(guān)鍵密碼部件布爾函數(shù)為研究對(duì)象，于2017年率先在國(guó)際上首次完成基于真實(shí)D -Wave 2000Q系統(tǒng)的抗多種密碼攻擊的密碼函數(shù)設(shè)計(jì)實(shí)驗(yàn)[146].

通過深入分析對(duì)稱密碼體制關(guān)鍵部件布爾函數(shù)在理論設(shè)計(jì)和搜索優(yōu)化方面實(shí)現(xiàn)多指標(biāo)均衡所面臨的瓶頸，提出布爾函數(shù)三大安全指標(biāo)(非線性度、相關(guān)免疫、平衡性)的量子自旋模型及可保證實(shí)際量子退火精度的安全指標(biāo)映射量子Chimera圖的可擴(kuò)展方案，成功完成小規(guī)模Bent函數(shù)設(shè)計(jì)和具有高非線性度的4元彈性函數(shù)設(shè)計(jì).

王潮教授等人將量子計(jì)算設(shè)計(jì)密碼的研究視為一個(gè)新的量子研究領(lǐng)域，命名為量子人工智能密碼量子計(jì)算密碼，旨在利用D -Wave量子計(jì)算機(jī)量子隧穿原理量子退火這一量子人工智能算法，結(jié)合密碼函數(shù)背景，將密碼設(shè)計(jì)問題映射為D -Wave量子退火擅長(zhǎng)處理的組合優(yōu)化問題，借助量子退火相比傳統(tǒng)計(jì)算的指數(shù)級(jí)空間搜索優(yōu)勢(shì)處理，是一種不同于傳統(tǒng)密碼搜索分析和理論設(shè)計(jì)的密碼設(shè)計(jì)思路和方案

該研究獲得了國(guó)內(nèi)外著名學(xué)者的肯定評(píng)價(jià)，例如國(guó)際著名的量子物理專家、《Nature》資深評(píng)論員、ETH Zürich的Troyer教授于2015年12月對(duì)這一探索性實(shí)驗(yàn)工作給予積極肯定：“It is important to look for new applications”.2016年7月，王育民教授評(píng)價(jià)：“如何借助加拿大的D -Wave計(jì)算機(jī)，巧妙發(fā)揮量子的一些物理特性，有效地解決密碼設(shè)計(jì)中的計(jì)算困難問題是你們工作的意義所在.”

4.2 基于量子退火的整數(shù)分解

業(yè)內(nèi)長(zhǎng)期以來認(rèn)為Shor算法是唯一有效的攻擊RSA的量子計(jì)算算法，在抗量子密碼的研究方面幾乎僅考慮到Shor算法的潛在威脅.實(shí)際上根據(jù)《Nature》和《Science》報(bào)道，均認(rèn)為實(shí)現(xiàn)Shor算法破譯仍舊遙遙無(wú)期[147-149].Google首席量子計(jì)算機(jī)科學(xué)家、原加州圣巴巴拉分校的Martinis教授及國(guó)際量子專家、Microsoft量子研究組首席研究員Troyer(原蘇黎世理工聯(lián)邦理工學(xué)院教授)均表示通用量子計(jì)算機(jī)的實(shí)用化，包括采用Shor算法破譯實(shí)際RSA公鑰密碼等典型應(yīng)用，遙遙無(wú)期[147-149].

通用量子計(jì)算機(jī)的進(jìn)展緩慢，對(duì)實(shí)際運(yùn)行的公鑰密碼不能構(gòu)成安全威脅，需要尋找Shor算法之外的量子算法攻擊公鑰密碼.業(yè)內(nèi)認(rèn)為基于量子退火的專用量子計(jì)算機(jī)D -Wave對(duì)信息科學(xué)非常重要：有利于解決“有指數(shù)級(jí)可能性的答案”搜索，這也是考慮將D -Wave量子計(jì)算機(jī)用于密碼設(shè)計(jì)及密碼分析的基礎(chǔ).

上海大學(xué)王潮教授等人基于D-Wave原理量子退火，提出了可用于小量子比特實(shí)現(xiàn)整數(shù)分解以攻擊RSA公鑰密碼的通用量子計(jì)算模型.基于D -Wave量子計(jì)算軟件環(huán)境，有效實(shí)現(xiàn)20 b整數(shù)的分解[150]，獲得了目前量子計(jì)算破譯RSA公鑰密碼的最大指標(biāo)，而2019年1月8日最新推出的IBM Q System OneTM運(yùn)行Shor算法在理論上最大只能分解5～10 bit整數(shù)，也超過了洛克希德馬丁公司研究員采用量子退火破譯RSA的最大規(guī)模7781[151].

該研究于國(guó)內(nèi)首次驗(yàn)證了D -Wave破譯RSA的潛力，這是不同于Shor算法的第2種攻擊方法，也說明該方法比Shor算法更具現(xiàn)實(shí)攻擊力.要獲得同樣的攻擊效果，Shor算法至少需要40多個(gè)量子比特，所需精度及規(guī)模都遠(yuǎn)非目前通用量子計(jì)算機(jī)所能達(dá)到.目前最大規(guī)模的谷歌72量子比特Bristlecone(“狐尾松”)芯片，還不是精確的量子比特，由于量子糾錯(cuò)問題(surface code碼)等技術(shù)瓶頸無(wú)法形成密碼破譯能力，外部環(huán)境的微小干擾都可能導(dǎo)致計(jì)算錯(cuò)誤.

王新梅教授在《Science China Physics,Mechanics & Astronomy》對(duì)文獻(xiàn)[150]研究撰寫的Highlight[152]中指出：“如能用量子退火算法攻擊其他知名密碼算法也是有意義的”.更進(jìn)一步，不僅需要重視D-Wave對(duì)RSA及其他公鑰密碼體制的攻擊可行性，未來抗量子密碼研究也需要重視來自D -Wave專用型量子計(jì)算機(jī)的攻擊可行性.《Science》出版機(jī)構(gòu)——美國(guó)科學(xué)促進(jìn)會(huì)(American Association for the Advancement of Science——AAAS)在EurekAlert上對(duì)該研究成果進(jìn)行報(bào)道，截止2019年7月底點(diǎn)擊率為13 399次.同時(shí)，科學(xué)網(wǎng)、IEEE對(duì)該研究也進(jìn)行了相關(guān)報(bào)道.

2018年11月ETSI會(huì)議的一些標(biāo)準(zhǔn)組織專家認(rèn)為，也正是因?yàn)镈 -Wave最初的應(yīng)用是洛克希德馬丁公司戰(zhàn)機(jī)飛控軟件測(cè)試、谷歌圖像識(shí)別等，與密碼學(xué)領(lǐng)域無(wú)關(guān)，當(dāng)前對(duì)D-Wave在密碼學(xué)領(lǐng)域方面的應(yīng)用遭到忽視.

4.3 Grover 量子搜索算法在ECC中的應(yīng)用

Grover算法與側(cè)信道攻擊的結(jié)合，可以拓展Grover算法的攻擊有效性.

2016年賈徽徽等人[155]將Grover量子搜索算法和中間相遇攻擊相結(jié)合，提出了一種新的搜索算法—Grover量子中間相遇搜索算法，并將其應(yīng)用于糾正ECC側(cè)信道攻擊中出現(xiàn)的錯(cuò)誤密鑰位.與傳統(tǒng)搜索算法相比，計(jì)算復(fù)雜度大幅降低.實(shí)驗(yàn)結(jié)果表明，該方法能夠以成功率1糾正ECC攻擊中出現(xiàn)的錯(cuò)誤位.

2017年王潮教授等人[156]提出基于0.1π旋轉(zhuǎn)相位Grover算法的橢圓曲線密碼電壓毛刺攻擊算法.實(shí)驗(yàn)結(jié)果表明，該方法能以100%的概率攻擊NIST發(fā)布的Kob1itz安全曲線K-163，計(jì)算復(fù)雜度呈指數(shù)級(jí)下降.該方法是除Shor算法之外量子計(jì)算對(duì)公鑰密碼的一種新的有效的量子密鑰攻擊方法.

5 演化密碼學(xué)與量子人工智能密碼的總結(jié)

我們對(duì)演化密碼學(xué)與量子人工智能密碼的發(fā)展現(xiàn)狀有了初步分析.目前，我們收集了該領(lǐng)域自20世紀(jì)80年代以來的100多篇文獻(xiàn)，這些文獻(xiàn)幾乎涵蓋了當(dāng)前密碼學(xué)演化計(jì)算的所有內(nèi)容，通過分析，我們希望能夠?yàn)閲?guó)內(nèi)人工智能與密碼學(xué)結(jié)合的研究提供參考.

5.1 演化密碼學(xué)的研究方法

演化密碼學(xué)的研究方法就是指研究時(shí)所采用的演化算法.根據(jù)“演化”的定義，我們將演化算法分成2類——基于自然進(jìn)化原理的算法和模擬生物社會(huì)性行為的算法.圖2展示了國(guó)內(nèi)外在密碼學(xué)研究中已經(jīng)得到應(yīng)用的演化算法.

Fig. 2 Evolutionary Algorithm classifications in cryptography圖2 密碼學(xué)演化算法分類

5.2 研究方向

根據(jù)演化計(jì)算應(yīng)用的情況，我們將密碼學(xué)問題分為：密碼分析(破譯)、密碼部件演化設(shè)計(jì).其中，人們對(duì)密碼分析(破譯)的研究由來已久，它也是研究者關(guān)注最多的領(lǐng)域，其次是密碼部件設(shè)計(jì).

在密碼分析(破譯)中，以替代密碼為代表的傳統(tǒng)密碼體系已經(jīng)被成功破譯，現(xiàn)在的研究熱點(diǎn)主要集中在對(duì)DES,SDES分析中，對(duì)公鑰密碼RSA,ECC的分析也是未來的研究方向.在密碼部件設(shè)計(jì)領(lǐng)域，演化計(jì)算在Boolean函數(shù)設(shè)計(jì)和S盒設(shè)計(jì)中的應(yīng)用已經(jīng)十分成熟，但此后創(chuàng)新性的研究很少出現(xiàn).基于啟發(fā)式搜索的密碼安全協(xié)議設(shè)計(jì)最早由Clark提出，由于限制條件很多，目前該方向的研究者并不多.圖3顯示了當(dāng)前密碼學(xué)演化計(jì)算的主要研究方向.

5.3 研究團(tuán)隊(duì)

這里我們只列出具有代表性的研究人物和他的團(tuán)隊(duì)，包括Millan研究團(tuán)隊(duì)、Clark研究團(tuán)隊(duì)、Laskari研究團(tuán)隊(duì)和國(guó)內(nèi)的張煥國(guó)研究團(tuán)隊(duì).圖4展現(xiàn)了各個(gè)研究團(tuán)隊(duì)的主要成員以及他們之間的聯(lián)系，圖4中連線表明兩者曾一起發(fā)表過論文.

Fig. 4 Popular research team of evolutionary cryptography圖4 演化密碼學(xué)的主要研究團(tuán)隊(duì)

5.4 相關(guān)會(huì)議和期刊

演化密碼學(xué)涵蓋了密碼學(xué)和演化計(jì)算2個(gè)學(xué)科內(nèi)容，但人們更愿意將其作為人工智能應(yīng)用的成功案例.當(dāng)前，絕大多數(shù)密碼學(xué)演化計(jì)算相關(guān)文獻(xiàn)來源于各種智能計(jì)算、信息安全和演化計(jì)算的相關(guān)國(guó)際會(huì)議和期刊.而密碼學(xué)會(huì)議或期刊卻很少收錄有關(guān)演化計(jì)算的論文，代表密碼學(xué)最高級(jí)水平的三大會(huì)議——美密會(huì)、歐密會(huì)和亞密會(huì)——近10年來很少收錄有關(guān)密碼學(xué)演化計(jì)算的文章，最早的一篇還要追溯到1998年Millan在歐密會(huì)上發(fā)表的關(guān)于的Boolean函數(shù)啟發(fā)式設(shè)計(jì)的論文[18].演化密碼的發(fā)展任重而道遠(yuǎn).我們從收集的100多篇相關(guān)文獻(xiàn)中選出107篇，按照主要的出版機(jī)構(gòu)分類作了統(tǒng)計(jì)和總結(jié)，如表1所示:

Table 1 Classifications of Relevant References on Evolutionary Computation in Cryptography表1 密碼學(xué)演化計(jì)算相關(guān)文獻(xiàn)分類

Note: The numbers in brackets represent the number of papers published in the corresponding journals.

The full name of Journal：

ICCIMA—International Conference on Computational Intelligence and Multimedia Applications;S&P—Security and Privacy;CEC—Congress on Evolutionary Computation;ICHIT—International Conference on Hybrid Information Technology;ICEEC—International Conference on Electrical Electronic and Computer Engineering;ICCIS—International Conference on Computational Intelligence and Security;ICISA—International Conference on Information Science and Applications;ISA—Intelligence Systems and Applications;WiCom—Wireless Communications;GECCO—The Genetic and Evolutionary Computation Conference;IJCSNS—International Journal of Computer Science and Network Security;IJCSIS—International Journal of Computer Science and Information Security.

從出版機(jī)構(gòu)來看，將近一半的演化密碼學(xué)相關(guān)論文被收錄在IEEE和Springer中，另有一半零散地分散在各個(gè)大學(xué)的電子數(shù)據(jù)庫(kù)和其他的一些出版機(jī)構(gòu).從論文來源角度來看，早期的演化密碼學(xué)論文主要出現(xiàn)在介紹性的Workshop和某些學(xué)者的博士論文中，而后開始出現(xiàn)在一些較知名的人工智能計(jì)算相關(guān)的國(guó)際會(huì)議上，固定期刊收錄的很少.

CEC是當(dāng)前演化計(jì)算領(lǐng)域最大和最具影響力的國(guó)際會(huì)議，演化密碼學(xué)相關(guān)的論文主要發(fā)表在CEC中，并大都被IEEE下屬的Evolutionary Computing期刊收錄.受IEEE Computational Intelligence Society和Evolutionary Progamming Society資助，CEC從1999年開始每年舉行一次，會(huì)議內(nèi)容包括進(jìn)化機(jī)器人、多目標(biāo)優(yōu)化、進(jìn)化硬件、進(jìn)化計(jì)算理論等人工智能計(jì)算及應(yīng)用的多個(gè)研究領(lǐng)域，演化密碼學(xué)作為人工智能演化計(jì)算應(yīng)用的成功案例也屬于該會(huì)議的討論范疇.與之齊名的GECCO和PPSN也都是人工智能領(lǐng)域較有影響力的國(guó)際會(huì)議，但它們很少收錄密碼學(xué)相關(guān)的論文.

6 演化密碼到量子人工智能密碼的展望

演化密碼已經(jīng)發(fā)展了20多年，得到了國(guó)家自然科學(xué)基金面上項(xiàng)目和重點(diǎn)項(xiàng)目等連續(xù)支持，并已經(jīng)歷了20多年的歷程，在對(duì)稱密碼和非對(duì)稱密碼均取得了豐碩的研究成果.在演化密碼安全性分析、演化DES密碼體制、演化DES密碼芯片、密碼部件(如S盒、P置換、輪函數(shù)和安全橢圓曲線等)的設(shè)計(jì)自動(dòng)化、Bent函數(shù)等密碼函數(shù)的分析與演化設(shè)計(jì)、密碼的演化分析、協(xié)議演化設(shè)計(jì)等方面獲得實(shí)際成功.表2中，我們簡(jiǎn)單匯總了當(dāng)前演化密碼學(xué)的研究成果.

Table 2 Summary of Popular Research on Evolutionary Cryptography表2 演化密碼學(xué)研究現(xiàn)狀匯總

Note: √ represents the study of corresponding algorithms in this field.

今后的演化密碼發(fā)展可能有3個(gè)方面：

1) 針對(duì)目前已有的密碼部件設(shè)計(jì)方法，演化密碼方法不是否定傳統(tǒng)的密碼分析設(shè)計(jì)方法，有望成為已有的密碼部件設(shè)計(jì)方法的一種增強(qiáng)手段.在需要對(duì)密碼部件設(shè)計(jì)某一過程參數(shù)進(jìn)行窮舉搜索的情況下，更快地搜索出好的參數(shù)；或是在已有較好的密碼部件設(shè)計(jì)參數(shù)情況下，可以進(jìn)行局部尋優(yōu)，有較大的概率對(duì)現(xiàn)有的參數(shù)進(jìn)行進(jìn)一步優(yōu)化.

2) 演化計(jì)算可以增強(qiáng)已有的密碼分析方法自動(dòng)化，對(duì)傳統(tǒng)方法進(jìn)行增強(qiáng)，成為密碼分析的有力手段.對(duì)于現(xiàn)代高強(qiáng)度密碼，如果安全強(qiáng)度達(dá)到指數(shù)級(jí)或者亞指數(shù)級(jí)，單純依靠演化算法或許搜索量依然很大.但是演化算法的使用可以降低密鑰搜索空間的數(shù)量級(jí)，使已有攻擊方法如虎添翼，在這些攻擊方法的已有攻擊能力基礎(chǔ)上進(jìn)一步減少搜索空間量級(jí).

3) 發(fā)展量子人工智能密碼.通用量子計(jì)算機(jī)進(jìn)展緩慢，而加拿大D-Wave商用量子計(jì)算機(jī)發(fā)展迅猛，已與Martin,Google,NASA、美國(guó)國(guó)家實(shí)驗(yàn)室等眾多機(jī)構(gòu)合作，完成100多個(gè)先期應(yīng)用，有望成為量子計(jì)算商用化的突破點(diǎn).D-Wave量子計(jì)算機(jī)在密碼學(xué)領(lǐng)域的研究鮮有人關(guān)注，目前國(guó)際上暫未發(fā)現(xiàn)通用及專用2類量子計(jì)算機(jī)直接用于密碼設(shè)計(jì)領(lǐng)域的公開文獻(xiàn)報(bào)道.

演化密碼思想已經(jīng)具備人工智能密碼的主要特征，本文進(jìn)一步拓展到量子人工智能密碼，在國(guó)際上首次由中國(guó)學(xué)者提出了量子計(jì)算機(jī)密碼設(shè)計(jì)的原創(chuàng)性理論，并于2017年底在國(guó)際上首次完成真實(shí)D-Wave 2000Q量子計(jì)算機(jī)密碼設(shè)計(jì)實(shí)驗(yàn).國(guó)際量子專家Troyer教授指出了量子人工智能密碼框架應(yīng)用探索的重要性.

在密碼破譯領(lǐng)域，在國(guó)內(nèi)首次提出了提出一種完全不同于著名的Shor算法的量子攻擊方法，驗(yàn)證了D-Wave分解大數(shù)破譯RSA密碼的潛力，成功實(shí)現(xiàn)20 bit整數(shù)的分解.獲得了目前量子計(jì)算破譯RSA公鑰密碼的最大指標(biāo)，對(duì)2019年1月8日最新推出的IBM Q System OneTM運(yùn)行Shor算法破譯RSA的理論最大值形成超越.

Grover量子搜索算法在橢圓曲線側(cè)信道攻擊中的應(yīng)用，大大降低攻擊的計(jì)算復(fù)雜度，提高算法的搜索效率，同時(shí)也拓展了Grover算法的攻擊能力.

4) 演化密碼有望對(duì)一些新型的密碼體制分析和設(shè)計(jì)提供探索性研究，并發(fā)展到人工智能智能密碼.

演化密碼可以加速NTRU的并行攻擊效率，融合人工智能方法，有望應(yīng)用于后量子時(shí)代的密碼算法設(shè)計(jì)和分析.

演化密碼是演化算法和密碼學(xué)的理論應(yīng)用發(fā)展的歷史必然，是密碼智能化發(fā)展過程中的一種成功實(shí)踐.演化密碼已經(jīng)具備了智能密碼的一些特征，演化密碼是進(jìn)一步發(fā)展為智能密碼的有效途徑.

就密碼安全性理論而言，演化密碼思想融合人工智能方法，有望快速產(chǎn)生一批可以實(shí)用的亞優(yōu)解，達(dá)到一次一密碼算法的作用，類似跳頻通信，增強(qiáng)密碼系統(tǒng)安全性.

全體作者感謝劉禮黎、賈徽徽，曹琳在他們碩士研究生學(xué)習(xí)階段對(duì)本文做出的貢獻(xiàn).