周期為2n的二元序列譜免疫度的算法

楊 波，劉能飛，佘 冰，李壽貴

（1.武漢科技大學冶金工業過程系統科學湖北省重點實驗室，湖北武漢，430065；2.武漢科技大學理學院，湖北武漢，430065）

周期為2n的二元序列譜免疫度的算法

楊 波1，劉能飛2，佘 冰2，李壽貴1

（1.武漢科技大學冶金工業過程系統科學湖北省重點實驗室，湖北武漢，430065；2.武漢科技大學理學院，湖北武漢，430065）

通過對周期序列譜免疫度的研究，提出了序列的0限制k錯線性復雜度的概念。以Mark Stamp所提出的計算周期為2n的二元序列k錯線性復雜度的算法為基礎，設計了求周期為2n的二元序列0限制k錯線性復雜度的算法1，并利用算法1提出了確定該二元序列譜免疫度的快速算法，該算法具有較高的計算效率，時間復雜度為O（n）。

流密碼；線性復雜度；k錯線性復雜度；二元序列；譜攻擊；譜免疫度；快速算法

流密碼安全的一個重要指標是序列的線性復雜度。線性復雜度是指產生一個給定序列的線性反饋移位寄存器的最小級數r。利用著名的Berlekamp-Massey算法［1］，一個敵手竊取序列的2r個連續比特就可以得到該序列的聯接多項式，即完全確定了產生該序列的線性反饋移位寄存器。因此，密碼學中一個強的序列必須具有高的線性復雜度。

設序列的周期為l，Berlekamp-Massey算法可能需要至少輸入l個連續比特才能使輸出穩定于正確的聯接多項式和線性復雜度，因此當線性復雜度較高且周期較長時，Berlekamp-Massey算法的計算量非常大。為了解決這一問題，Games等［2］研究發現，當序列的周期為2n時，通過n步計算就可以求出其線性復雜度和聯接多項式，進而提出了Games-Chan算法。……