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

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

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

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

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

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

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