對對稱密碼的代數(shù)攻擊及解多元方程組算法的研究.pdf

1、近些年來，對對稱密碼體制的一種全新有效的攻擊方法-代數(shù)攻擊，在密碼學(xué)界中引起了越來越多的關(guān)注。與以前傳統(tǒng)的“統(tǒng)計(jì)”攻擊方法不同，使用代數(shù)方法對密碼體制進(jìn)行密碼分析的攻擊方法，統(tǒng)稱為代數(shù)攻擊。其主要思想是，將密碼體制內(nèi)在加密活動描述為輸入(密鑰)和輸出之間的多元方程組，并且通過求解低次超定或稀疏方程組來恢復(fù)密鑰。這樣，求解大型低次超定稀疏多元方程組計(jì)算上的困難性，就成為許多現(xiàn)代對稱密碼體制安全性的一個必要條件，人們也越來越多得關(guān)注于尋找求

2、解大型多元方程組的新的快速有效算法。 代數(shù)攻擊與其它已有的攻擊方法相比有很大的優(yōu)勢，其中最引人注意的特色之一就是代數(shù)攻擊所需要的數(shù)據(jù)量非常少，有時1個或2個已知明文就足夠了，這對攻擊者來說是非常有吸引力的。這也正是為什么現(xiàn)在代數(shù)攻擊雖然還不成熟、效率低，卻仍然是潛在得非常有破壞力的原因。代數(shù)攻擊的另一個優(yōu)勢就是，它是一種全新的分析方法，目前涉足的也許只是代數(shù)分析方法的一小部分，還有許多未知的領(lǐng)域沒有被探索和研究。因而代數(shù)攻擊的前

3、景非常廣闊，可以有很大得提高和改進(jìn)，對代數(shù)攻擊進(jìn)行研究具有很好的理論意義和應(yīng)用價值。 代數(shù)攻擊最早用于對公鑰密碼及分組密碼Rijndael和Serpent的攻擊，通過將恢復(fù)密鑰的問題轉(zhuǎn)化為求解一個多元二次方程組(MQ問題)來進(jìn)行密碼分析。雖然代數(shù)攻擊對Rijndael和Serpent還沒有可行的攻擊實(shí)例，但其S盒超定稀疏方程的存在已成為Rijndael和Serpent一種本質(zhì)的威脅。隨著解低次多元方程組有效算法-XL算法的提出和

4、改進(jìn)，對基于LFSR流密碼體制的代數(shù)攻擊成為一個熱門課題，其攻擊思想是由高階相關(guān)攻擊的思想衍變而來的，不再把輸出作為輸入的函數(shù)考慮，而是研究輸入流和輸出流之間的代數(shù)關(guān)系。研究表明代數(shù)攻擊對基于LFSR的流密碼體制非常有效，多個基于LFSR的流密碼對代數(shù)攻擊是(本質(zhì))脆弱的。近年來對分組密碼的代數(shù)攻擊又有了新的研究成果，采用將MQ問題轉(zhuǎn)化為SAT問題求解的算法可以破解6輪DES(僅使用一個已知明文)和全部輪的KeeLoq密碼體制。

5、 本文研究了對基于LFSR流密碼和分組密碼的代數(shù)攻擊；既有理論方面的研究，又有對具體密碼算法實(shí)際的攻擊方法，如Toyocrypt、LILI-128、EO、Sfinks、Rijndael、Serpent、DES、KeeLoq等。本文還研究了傳統(tǒng)的構(gòu)造Gr(o)bner基的Buchberger算法、XL算法及改進(jìn)和將MQ問題轉(zhuǎn)化為SAT問題求解等解方程組的算法。相較于前兩種算法，第三種算法非常簡單有效，而且所需已知明文的個數(shù)也相對較少，采用

6、這種算法，可以破解6輪DES和全部輪的KeeLoq，因而研究這種算法對推動代數(shù)攻擊的發(fā)展有非常積極的意義。本文重點(diǎn)探討了將低次稀疏多元方程組轉(zhuǎn)化為CNF-SAT問題的有效方法，并僅用一個已知明文，固定20個密鑰比特，采用S-盒的門電路表示方法，列出了6輪DES 3076個方程的2900元稀疏二次方程組，轉(zhuǎn)化為4203個變元、16880個子句、子句總長度為51514的SAT問題，進(jìn)而用MiniSAT 2.0求解，恢復(fù)出另外36比特密鑰。本