流密碼代數(shù)攻擊中若干關(guān)鍵問題的研究.pdf

1、代數(shù)攻擊是近幾年來最重要的密碼分析技術(shù)之一。代數(shù)免疫度是隨著代數(shù)攻擊的出現(xiàn)而提出的關(guān)于布爾函數(shù)的一個新準則，用于衡量布爾函數(shù)抵抗標準代數(shù)攻擊的能力。為了有效抵抗代數(shù)攻擊，密碼系統(tǒng)中使用的布爾函數(shù)必須具有盡可能高的代數(shù)免疫度，甚至要求是代數(shù)免疫最優(yōu)的。求解多變元非線性方程系統(tǒng)的快速方法是支撐代數(shù)攻擊有效實施的重要步驟，而Grobner基正是求解非線性方程系統(tǒng)的一個重要方法。廣泛應(yīng)用于代數(shù)攻擊的XL算法就是Grobner基的一個快速算法(F

2、4算法)的冗余版本。
　　本文首先研究了代數(shù)免疫最優(yōu)布爾函數(shù)的遞歸構(gòu)造，提出了代數(shù)免疫最優(yōu)布爾函數(shù)的二階遞歸構(gòu)造法和一階遞歸構(gòu)造法；其次討論了兩類對稱布爾函數(shù)，對其代數(shù)免疫性，代數(shù)次數(shù)和非線性度做了深入研究并得到完整結(jié)果；最后研究了Grobner基的快速計算。具體結(jié)果如下：
　　1)研究了代數(shù)免疫最優(yōu)布爾函數(shù)的遞歸構(gòu)造。首先，給出了代數(shù)免疫最優(yōu)布爾函數(shù)的二階遞歸構(gòu)造方法。該方法構(gòu)造的布爾函數(shù)代數(shù)免疫最優(yōu)，具有優(yōu)良的代數(shù)次數(shù)和

3、非線性度，并且與之前的二階遞歸構(gòu)造法相比，它具有更加優(yōu)良的平衡性。其次，提出了代數(shù)免疫最優(yōu)布爾函數(shù)的一階遞歸構(gòu)造法。該方法構(gòu)造的布爾函數(shù)不但代數(shù)免疫最優(yōu)，而且是完全平衡的。這是首個代數(shù)免疫最優(yōu)布爾函數(shù)的一階遞歸構(gòu)造法。最后，基于布爾函數(shù)的變換，對上述兩類遞歸構(gòu)造法進行了推廣。
　　2)分析了兩類對稱布爾函數(shù)。證明了這兩類布爾函數(shù)代數(shù)免疫最優(yōu)的充要條件，并進一步解決了其中代數(shù)免疫最優(yōu)部分函數(shù)的計數(shù)問題。同時，詳細討論了這兩類函數(shù)的其

4、它密碼學性質(zhì)，特別是，完全確定了其代數(shù)次數(shù)和非線性度，從而解決了Braeken關(guān)于這兩類函數(shù)中代數(shù)免疫最優(yōu)部分函數(shù)的代數(shù)次數(shù)和非線性度的猜想。
　　3)討論了Grobner基的快速計算。提出了二元多項式理想Grobner基的一個快速算法。證明了在嚴格排序的生成集中，只需計算相鄰多項式間的S-多項式即可。基于該結(jié)論，在Grobner基的計算過程中，所需計算的S-多項式的數(shù)量從1/2r(r-1)銳減到(r-1)，其中r為當前生成元組中