《演化計算在密碼分析中的套用研究》是依託武漢大學，由楊敏擔任項目負責人的青年科學基金項目。
基本介紹
- 中文名：演化計算在密碼分析中的套用研究
- 項目類別：青年科學基金項目
- 項目負責人：楊敏
- 依託單位：武漢大學
項目摘要,結題摘要,
項目摘要
密碼是信息安全的基礎，沒有密碼的安全就沒有網際網路的信息安全。研究密碼的安全性具有重要的現實意義和理論價值。本課題將用演化計算的思想來研究分組密碼和公鑰密碼的攻擊。對於分組密碼，研究如何用演化計算尋找分組密碼的最/次優差分路徑以攻擊分組密碼。對於公鑰密碼，主要研究大數分解和離散對數的計算，包括：研究群上隨機映射的枝圈結構規律，首先將問題歸約到指數所在的整數環上，利用演化計算研究該整數環上簡單函式的枝圈結構規律，以尋找短的枝圈結構，這在利用pollard的rho方法計算離散對數時有直接重要的套用；用演化計算研究數域篩法里多項式選擇的方法，以找到接近最/次優的多項式，提高數域篩法的效率。另外還將研究那些能快速降低問題規模的數學工具（如中國剩餘定理，歐幾里德算法）在大數分解和離散對數計算上的適用性。通過上述研究，攻擊一個分組密碼，獲得大數分解和離散對數計算的一種新解法或/並改進已有的攻擊方法。
結題摘要
本課題研究演化計算在大數分解，離散對數和分組密碼分析中的套用。由於離散對數問題研究可歸約於大數分解研究，且數域篩法是目前最快的分解算法，所以我們重點研究數域篩法和分組密碼。數域篩法中多項式選擇至關重要，好多項式在篩法里產生更多關係，且可以減少矩陣步驟矩陣的大小。篩法和矩陣這兩個步驟的效率決定了大數分解整體效率。在演化設計多項式過程中存在多項式空間過大的問題。首先我們利用統計和代數方法研究了多項式好壞和其係數的關係，得出重要結論：當多項式尾係數含有更多小素因子時通常多項式更好，對於一個d次多項式，當其d-2次係數為負數且足夠小時通常多項式更好。這些研究結論可用於減少多項式的有效空間。其次，我們進一步提出用幾何學觀點來選擇多項式並得出如下結論：一個好多項式對應的圖形應該靠近x軸且變化比較平緩。為了儘量靠近x軸，d-2次的係數應該為負數且足夠小，對於5次以上多項式，其d-1次和d-3次係數符號應該相反；為了使多項式圖形比較平緩，次數較高的係數應該儘量小，首係數更應該儘量小。大量實驗結果表明上述結論的有效性：我們方法獲得的結果比實際分解採用的多項式效果都好，MurphyE指標要好10%-30%。如RSA190於2010年被俄羅斯人I.Popovyan以及荷蘭人A.Timofeev分解，我們的多項式要比他們所用多項式在指標上好26%。如果進行分解比賽，其它條件相同時我們會比他們提前約26%的時間。上述結論的科學意義：研究結論回答了好多項式在哪裡分布，如何快速找到它們這些重要問題。具有重要套用價值，該研究結果發布在國際密碼學研究會網站上：http://eprint.iacr.org/2013/583。法國INRIA著名科學家Paul Zimmermann，CARAMEL項目（CADO-NFS是CARAMEL的子項目）科研負責人密切關注並將我們關於首係數的結論用於其後繼版本的大數分解國際開源項目CADO-NFS（版本a9cbbb5之後，包括最新的2.0發行版）。另外，在分組密碼分析方面，我們基於啟發式搜尋算法，給出並完善了面向字/位元組的差分路徑搜尋最佳化算法，研究了密碼算法和部件在HAIFA、Sponge、樹型結構下的安全性。並對AES進行了攻擊：我們找出了一條新的差分路徑，進一步降低了Biclique攻擊算法的複雜度。
