王 寧，顧 聰

（中原工學(xué)院理學(xué)院，河南鄭州450007）

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

王 寧，顧 聰

（中原工學(xué)院理學(xué)院，河南鄭州450007）

根據(jù)計(jì)算二元2n周期序列的線性復(fù)雜度的算法，給出了一個(gè)能夠快速計(jì)算二元2n周期序列的譜免疫度的新算法，該算法與Games-Chan算法有相同的復(fù)雜度，能夠同時(shí)求出對應(yīng)的零化序列，并且舉例說明了該算法的優(yōu)越性。

二元序列；線性復(fù)雜度；譜免疫度；零化序列

近些年，代數(shù)攻擊和快速代數(shù)攻擊已經(jīng)被一些密碼系統(tǒng)廣泛關(guān)注，它們對密碼體制特別是對基于線性反饋移位寄存器（LFSR）的序列密碼［1-2］的攻擊給密碼系統(tǒng)的安全帶來了嚴(yán)重的威脅。攻擊方法認(rèn)為，如果能求解一個(gè)超定的多變元非線性方程系統(tǒng)，就將威脅到密碼算法的安全性。因此，為了解決代數(shù)攻擊的問題，人們在設(shè)計(jì)布爾函數(shù)時(shí)增加了一個(gè)新的標(biāo)準(zhǔn)——代數(shù)免疫度［3］。密碼系統(tǒng)中，布爾函數(shù)如果具有足夠高的代數(shù)免疫度，就能夠有效地抵抗代數(shù)攻擊。

以代數(shù)攻擊的思想為依據(jù)，針對序列密碼，Gong等［4］提出了快速離散傅里葉譜攻擊（簡稱快速譜攻擊）。代數(shù)攻擊和快速代數(shù)攻擊利用的是布爾函數(shù)低代數(shù)次數(shù)關(guān)系，而快速譜攻擊則通過尋找密鑰流序列的低傅里葉譜重量（即線性復(fù)雜度）關(guān)系進(jìn)行攻擊。特別地，當(dāng)?shù)途€性復(fù)雜度的零化序列出現(xiàn)在密鑰流序列中時(shí)，就能進(jìn)行有效的譜攻擊。針對于此，Gong等［4］提出了譜免疫度的概念，即密鑰流序列或其補(bǔ)序列的（非零）零化序列的最低線性復(fù)雜度。對于過濾生成模型，Helleseth等［5］指出過濾函數(shù)的代數(shù)免疫度和密鑰流序列的譜免疫度之間存在著相互的制約關(guān)系：若密鑰流序列的譜免疫度較高，則其過濾函數(shù)的代數(shù)免疫度也較高，反之則不一定成立。說明在理論上，與代數(shù)攻擊相比較，譜攻擊具有更大的優(yōu)勢。

本文主要研究二元序列的譜免疫度計(jì)算問題。由于目前還無有效的關(guān)于譜免疫度的快速算法，因此只能根據(jù)定義來計(jì)算。對于2n周期的二元序列，根據(jù)Games-Chan算法［6］，筆者給出了一個(gè)新算法，該算法不僅可以快速計(jì)算對應(yīng)序列的譜免疫度，而且可以驗(yàn)證它與Games-Chan算法具有相同的復(fù)雜度。

1 預(yù)備知識(shí)

本文主要考慮二元序列s=s0，s1，s2，…，其中分量取值于二元域F2={0，1}。序列s具有周期N：存在一個(gè)正整數(shù)N滿足si+N=si對所有非負(fù)整數(shù)i都成立。設(shè)定s=（s0，s1，s2，…，sN-1）。序列s的線性復(fù)雜度LC（s）定義為滿足下面方程的最小正整數(shù)L

對所有大于等于L的j都成立；系數(shù)d1，…，dL屬于F2；這里的加是模2加。如果s為零序列，則LC（s）= 0；否則LC（s）=生成該序列的線性移位寄存器的最小長度［7］。如果存在一個(gè)二元序列a=（a0，a1，…，aN-1）滿足

則稱序列a為序列s的一個(gè)零化序列。序列s的譜免疫度定義為序列s和s的補(bǔ)序列s+1的所有非零零化序列的線性復(fù)雜度的最小值。我們的主要任務(wù)就是找出可以快速計(jì)算序列譜免疫度的算法。

對于2n周期的二元序列s，它的零化序列a一定滿足：如果si=1，i=0，1，…，2n-1，則一定有ai=0；而其他位置上的值可以任意取0或1。為了求出序列s的譜免疫度，分別計(jì)算序列s與s+1的零化序列的線性復(fù)雜度的最小值，然后從中選取最小值。為了計(jì)算序列s的零化序列的線性復(fù)雜度的最小值，采用文獻(xiàn)［8］中的思想，用一個(gè)新的變量符號*來表示未定值。這樣，s的零化序列a的通式可以表示為：對于i=0，1，…，2n-1

在序列a所有的*中，必須至少有一個(gè)*最終取1來保證a為非零序列。通過對序列a中的*進(jìn)行不同的賦值來求出最小的線性復(fù)雜度。

2 新的算法

筆者根據(jù)Games-Chan算法給出一個(gè)計(jì)算譜免疫度的新算法。其實(shí)新算法是分別計(jì)算序列s和s的補(bǔ)序列s+1的零化序列的最小線性復(fù)雜度，從而可以求出譜免疫度。

易見這個(gè)算法的復(fù)雜度與Games-Chan算法的復(fù)雜度是一樣的，都為O（2n）。下面的定理證明了新算法的合理性。

定理1 上面算法是正確的。

證明 首先需注意，在序列a所有的*中，必須至少有一個(gè)*最終取1來保證a為非零序列。再根據(jù)Games-Chan算法，為了使得序列的線性復(fù)雜度盡量小，不得不盡量使得序列的左右兩部分相同。所以我們的主要目標(biāo)是對上述算法中序列的左右兩部分的*賦值（且不能全為0）使得左右兩部分相同。在第j步中，當(dāng)存在0≤i＜l，ai=ai+l=*時(shí)，把其他ai與ai+l只有一個(gè)為*的*都賦值為0，ai=ai+l=*時(shí)的*的賦值放到下一步再定（這兩個(gè)*的值將會(huì)是一樣的），這樣就能保證序列左右兩部分相同，并且*的值不會(huì)全為0。此時(shí)線性復(fù)雜度不會(huì)增加。當(dāng)不存在ai與ai+l同時(shí)為*時(shí)，則無論對*賦何值，都不能使得序列左右兩邊相同，所以線性復(fù)雜度將增加l。當(dāng)ai與ai+l中有一個(gè)為*時(shí)，令下一步要考慮的序列Aj+1的第i個(gè)值為*，來保證*的值根據(jù)以后的情形再確定。最后對所有非零的零化序列，一定有An≠0，根據(jù)Games-Chan算法，此時(shí)線性復(fù)雜度增加1。上面算法運(yùn)行到最后，LC就是s的非零零化序列的最小線性復(fù)雜度。

3 結(jié)語

本文詳細(xì)討論了二元2n周期序列的譜免疫度的新算法。根據(jù)著名的Games-Chan算法及引入的新的變量*，給出了一個(gè)可以快速計(jì)算譜免疫度的新算法，同時(shí)還能求出對應(yīng)的零化序列，并且該算法與Games-Chan算法有相同的復(fù)雜度。本文的結(jié)果具有很好的應(yīng)用價(jià)值。

參考文獻(xiàn)：

［1］COURTOISNT,PIEPRZYK J.Cryptanalysisofblock cipherswith overdefined systemsofequations［C］//Advancesin Cryptology -ASIACRYPT 2002.Berlin:Springer,2002:267-287.

［2］COURTOISN,MEIERW.Algebraic attackson stream cipherswith linear feedback［C］//Advances in Cryptology-EUROCRYPT 2003.Berlin:Springer,2003:345-359.

［3］MEIERW,PASALICE,CARLETC.Algebraic attacks and decomposition of Boolean functions［C］//Advances in Cryptology-EUROCRYPT 2003.Berlin:Springer,2004:474-491.

［4］GONGG,RONJOM S,HELLESETH T,etal.Fastdiscrete Fourier spectraattackson stream ciphers［J］.IEEETransactionson Information Theory,2011,57（8）:5555-5565.

［5］HELLESETH T,RONJOM S.Simplifying algebraic attackswith univariate analysis［C］//Information Theory and Applications Workshop.New York:IEEE,2011:1-7.

［6］GAMESR,CHAN A.A fastalgorithm for determining the complexity ofa pseudo-random sequencewith period 2n［J］.IEEE Transactionson Information Theory,1983,29（1）:144-146.

［7］RUPPELR.Analysisand Design ofStream Ciphers［M］.New York:Springer-Verlag,1986.

［8］CHANG Z,WANGX.On the firstand second error linear complexity ofbinary 2n-periodic sequences［J］.Chinese Journalof Electronics,2013,22（1）:1-6.

【責(zé)任編輯：王桂珍 foshanwgzh@163.com】

A fastalgorithm for spectral immunity of binary 2n-periodic sequences

WANG Ning,GU Cong
（College of Science,Zhongyuan University of Technology,Zhengzhou 450007,China）

According to the algorithm for computing the linear complexity of binary 2n-periodic sequences,one new algorithm for fast computing the spectral immunity ofbinary 2nperiodic sequences is provided in this paper which can find the corresponding annihilator simultaneously,and an example is provided to show the efficiency of thisnew algorithm.

binary sequences;linear complexity;spectral immunity;annihilator

TP301.6

A

2017-03-16

河南省教育廳科研項(xiàng)目（13A110117）

王 寧（1976-），女，河南周口人，中原工學(xué)院講師。

1008-0171（2017）04-0023-05