王寶楠 胡 風 張煥國 王 潮,3

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

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

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

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

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

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

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

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

1 演化計算的概念

演化算法和演化計算的概念是什么？1999年Millan給出了演化計算的一種定義——演化計算就是模擬生物演化過程或社會性行為建立模型來解決問題的方法[6].他從生物學和社會行為學角度提煉出演化計算的概念，指明了演化算法是一種模型.但我們認為這一定義還不夠全面，因為常見的模擬退火算法與生物體或社會行為并沒有什么關(guān)系，但通常人們愿意將其作為演化算法的一種.

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

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

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

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

1) 初始化群體；

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

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

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

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

(1)

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

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

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

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

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

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

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

(2)

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

(3)

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

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

1) 探索階段(1980～1993)

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

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

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

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

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

2) 初級階段(1993～2000)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.1 Boolean函數(shù)設計

3.1.1 研究背景

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

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

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

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

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

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

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

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

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

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

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

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

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

3.2 S盒設計與DES設計

3.2.1 研究背景

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

1998年澳大利亞昆士蘭科技大學的Millan[68]提出一種通過對換S-盒輸出的2個值來提高S -盒的非線性度，實驗表明通過隨機生成的方式難以獲得高非線性度的S-盒.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.2.2 DES的演化設計

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

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

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

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

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

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

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

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

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

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

3.3 序列密碼設計

3.3.1 研究背景

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

3.3.2 序列密碼的演化設計

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

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

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

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

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

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

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

3.4 NTRU破譯

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

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

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

2016年3月印度的Agrawal和Sharma分別使用蟻群優(yōu)化算法(ACO)和粒子群優(yōu)化算法(PSO)對NTRU進行算法的優(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在保證較低時間復雜度的情況下，使用遺傳算法(GA)、蟻群算法(ACO)和粒子群算法(PSO)對NTRU進行優(yōu)化.實驗結(jié)果表明，相對于其他演化算法，使用粒子群算法進行優(yōu)化時，NTRU的復雜度最高[108]，復雜度為O(Nlog(N+1)3)(N為素數(shù))，而傳統(tǒng)NTRU復雜度為O(NlogN)，意味著使用粒子群算法的NTRU提供了更高的安全性.

3.5 ECC安全曲線選擇

3.5.1 研究背景

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

3.5.2 ECC安全曲線選擇的演化設計

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

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

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

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

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

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

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

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

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

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

3.7 背包問題分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 量子人工智能密碼設計與分析

4.1 量子人工智能密碼設計

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

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

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

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

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

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

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

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

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

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

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

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

2018年11月ETSI會議的一些標準組織專家認為，也正是因為D -Wave最初的應用是洛克希德馬丁公司戰(zhàn)機飛控軟件測試、谷歌圖像識別等，與密碼學領(lǐng)域無關(guān)，當前對D-Wave在密碼學領(lǐng)域方面的應用遭到忽視.

4.3 Grover 量子搜索算法在ECC中的應用

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

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

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

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

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

5.1 演化密碼學的研究方法

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

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

5.2 研究方向

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

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

5.3 研究團隊

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

Fig. 4 Popular research team of evolutionary cryptography圖4 演化密碼學的主要研究團隊

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

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

Table 1 Classifications of Relevant References on Evolutionary Computation in Cryptography表1 密碼學演化計算相關(guā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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

全體作者感謝劉禮黎、賈徽徽，曹琳在他們碩士研究生學習階段對本文做出的貢獻.