代數(shù)攻擊及其應(yīng)用研究.pdf

1、代數(shù)攻擊是近年出現(xiàn)的重要密碼分析方法，目前已被成功應(yīng)用于對稱和非對稱密碼領(lǐng)域中多種密碼算法的分析之中。該技術(shù)借助于代數(shù)方程的思想，首先將若干加密算法實(shí)例轉(zhuǎn)化為已知的明密文和未知密鑰比特間的多變元代數(shù)方程組，然后通過求解該方程組還原未知密鑰比特。
　　本文研究了代數(shù)攻擊的技術(shù)原理及其應(yīng)用，并探討了主要技術(shù)環(huán)節(jié)的軟件實(shí)現(xiàn)問題，全文主要內(nèi)容如下：
　　1、首先討論了代數(shù)攻擊方法，重點(diǎn)歸納了求解二元域上代數(shù)方程組的算法。這類算法主要

2、分三類:第一類是基于Gr(o)bner基的方法，這是理論完備，應(yīng)用廣泛的經(jīng)典求解方法;第二類來自于密碼分析領(lǐng)域，如線性化Linearization，重線性化Relinearization以及擴(kuò)展線性化方法XL等；第三類方法的代表是將解方程問題轉(zhuǎn)化為可滿足性問題，再利用可滿足性求解器求解的方法，這是當(dāng)前最有效的解方程手段。
　　2、對AES算法的簡單變體—單輪加密函數(shù)進(jìn)行了代數(shù)攻擊。首先在假設(shè)部分比特密鑰未知條件下，利用中途相遇方法

3、列出表征加密過程的代數(shù)方程組，再采用猜測和求解相結(jié)合的策略，通過Gr(o)bner基方法和CryptoMiniSat求解器兩種方法解方程求未知密鑰比特；單機(jī)測試結(jié)果表明，用Gr(o)bner基方法至多可求解出40比特密鑰，而用CryptoMiniSat可求解出96比特密鑰信息。因此，CryptoMiniSat求解器更適合于求解此類方程組。
　　3、對Trivium算法的初始化過程與密鑰流生成過程做了深入分析。主要研究了兩大類問題：

4、一是首次分析了Trivium算法及其變體的初始化過程的擴(kuò)散性；二基于已知部分密鑰信息條件，對Trivium算法及其變體算法進(jìn)行了代數(shù)攻擊，給出了最新的密碼分析結(jié)果。結(jié)果表明，對此類方程組，CryptoMiniSat求解器性能與Gr(o)bner基方法相當(dāng)。
　　4、研制了“代數(shù)攻擊測試平臺”軟件，基于Windows XP操作系統(tǒng)下的VC++6.0集成開發(fā)環(huán)境，實(shí)現(xiàn)了針對兩種算法列方程的功能與兩種典型的方程求解算法,本文的所有測試數(shù)