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

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

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

Fig. 1 Relationship between cryptosystem, cryptographic components, and mathematical problem圖1 密碼系統、密碼部件和數學問題的關系

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

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

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

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

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

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

1 演化計算的概念

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

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

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

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

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

1) 初始化群體；

2) 尋優過程.

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

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

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

(1)

其中，x表示個體，α1,α2,α3表示加權系數，β1,β2,β3表示不同的指標.

3) 得到當前最優的解.

2 密碼學演化計算的發展過程

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

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

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

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

(2)

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

(3)

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

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

1) 探索階段(1980～1993)

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

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

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

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

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

2) 初級階段(1993～2000)

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

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

Millan小組的研究很有意義，他們為演化密碼的研究開辟了一個新的領域，為后續密碼學者的研究指引了新的方向.所謂密碼部件，就是解決某個數學問題的算法.倘若這個數學問題屬于組合優化或搜索范疇，那么該密碼部件就可以嘗試引入演化算法來提高該密碼部件的實現效率.

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

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

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

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

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

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

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

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

4) 多樣化階段成熟，系統化學說化(2005～現在)

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

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

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

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

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

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

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

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

3 國內外研究現狀

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

3.1 Boolean函數設計

3.1.1 研究背景

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

3.1.2 布爾函數演化設計

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

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

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

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

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

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

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

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

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

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

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

3.2 S盒設計與DES設計

3.2.1 研究背景

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2016年Picek等人[85]基于目前最先進的適應度函數進行實驗分析，提出了一個能提供更高速度以及更優結果的新的適應度函數.

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

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

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

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

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

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

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

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

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

3.2.2 DES的演化設計

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

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

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

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

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

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

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

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

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

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

3.3 序列密碼設計

3.3.1 研究背景

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

3.3.2 序列密碼的演化設計

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

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

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

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

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

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

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

3.4 NTRU破譯

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

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

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

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

2016年Agrawal和Sharma在保證較低時間復雜度的情況下，使用遺傳算法(GA)、蟻群算法(ACO)和粒子群算法(PSO)對NTRU進行優化.實驗結果表明，相對于其他演化算法，使用粒子群算法進行優化時，NTRU的復雜度最高[108]，復雜度為O(Nlog(N+1)3)(N為素數)，而傳統NTRU復雜度為O(NlogN)，意味著使用粒子群算法的NTRU提供了更高的安全性.

3.5 ECC安全曲線選擇

3.5.1 研究背景

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

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

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

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

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

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

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

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

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

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

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

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

3.7 背包問題分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.8 隨機數的產生

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

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

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

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

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

4.1 量子人工智能密碼設計

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

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

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

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

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

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

4.2 基于量子退火的整數分解

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

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

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

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

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

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

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

Grover算法與側信道攻擊的結合，可以拓展Grover算法的攻擊有效性.

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

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

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

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

5.1 演化密碼學的研究方法

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

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

5.2 研究方向

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

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

5.3 研究團隊

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

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

5.4 相關會議和期刊

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

Table 1 Classifications of Relevant References on Evolutionary Computation in Cryptography表1 密碼學演化計算相關文獻分類

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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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