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

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

2、4算法)的冗余版本。
　　本文首先研究了代數(shù)免疫最優(yōu)布爾函數(shù)的遞歸構(gòu)造，提出了代數(shù)免疫最優(yōu)布爾函數(shù)的二階遞歸構(gòu)造法和一階遞歸構(gòu)造法；其次討論了兩類對(duì)稱布爾函數(shù)，對(duì)其代數(shù)免疫性，代數(shù)次數(shù)和非線性度做了深入研究并得到完整結(jié)果；最后研究了Grobner基的快速計(jì)算。具體結(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)，而且是完全平衡的。這是首個(gè)代數(shù)免疫最優(yōu)布爾函數(shù)的一階遞歸構(gòu)造法。最后，基于布爾函數(shù)的變換，對(duì)上述兩類遞歸構(gòu)造法進(jìn)行了推廣。
　　2)分析了兩類對(duì)稱布爾函數(shù)。證明了這兩類布爾函數(shù)代數(shù)免疫最優(yōu)的充要條件，并進(jìn)一步解決了其中代數(shù)免疫最優(yōu)部分函數(shù)的計(jì)數(shù)問題。同時(shí)，詳細(xì)討論了這兩類函數(shù)的其

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