周期為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算法。然而有些序列的線性復雜度雖然很高，但改變少量比特后其線性復雜度降為0，穩定性極差，很容易被破解，為此Stamp等［3］提出了k錯線性復雜度概念。k錯線性復雜度是指改變原始序列每個周期中小于等于k個相應比特所得到的序列的線性復雜度最小值。Stamp等在文獻［3］中還設計了一個計算周期為2n的二元序列k錯線性復雜度的高效算法。此后，國內外學者對線性復雜度和k錯線性復雜度算法進行了一系列研究［4-10］，得到了一些適用于不同周期或不同有限域上的序列的線性復雜度或k錯線性復雜度快速算法。

序列具有高的線性復雜度和k錯線性復雜度只是流密碼安全性強的必要條件。2011年Gong等［11］提出了針對流密碼的快速選擇性離散傅里葉譜攻擊。在一般情況下，譜攻擊比代數攻擊更有效、更靈活［12-13］。為了使序列能夠抵抗快速選擇性離散傅里葉譜攻擊，Gong等在文獻［11］中同時給出了譜免疫度的概念，即序列或其補序列的非零零化序列的最小線性復雜度，并在文獻［14］中算法1的基礎上設計了一個計算周期為l（l|2n-1）的序列的譜免疫度算法。

本文通過研究譜免疫度和k錯線性復雜度之間的聯系，提出0限制k錯線性復雜度的概念，然后在文獻［3］中求周期為2n的二元序列k錯線性復雜度算法的基礎上，設計一個計算2n周期二元序列0限制k錯線性復雜度的算法，并進一步提出一個計算該二元序列譜免疫度的算法，采用這一算法可以在2n步內得到計算結果。

1　預備知識

令s∞=（s0，s1，…，si，…）是周期為l的二元序列，向量s=（s0，s1，…，sl-1）表示s∞中的一個周期，向量s的漢明重量其中表示整數加法（下同）。設a和b均為l維向量，定義兩向量的乘積a·b=c，其中ci=ai·bi、“·”為GF（2）上的乘法運算；定義兩向量的和a+b=c，其中ci=ai+bi、“+”為GF（2）上的加法運算。記，其中表示周期序列s∞的線性復雜度，l維向量a和b的漢明距離記作

定義1（k錯線性復雜度［15］）周期序列s∞的k錯線性復雜度記作ck（s），

定義2（譜免疫度［11］）設s∞是一個具有周期l的二元序列，稱

為序列s∞的譜免疫度。

定義3（0限制k錯線性復雜度）周期序列s∞的0限制k錯線性復雜度記作c0k（s），

根據譜免疫度定義和上述分析即得定理1。

定理1 周期為l的二元序列s∞的譜免疫度等于的0限制錯線性復雜度和s∞的0限制w（s）-1錯線性復雜度的最小值，即

2　快速算法

首先在文獻［3］中求周期為2n的二元序列k錯線性復雜度算法的基礎上，給出一個求周期為2n的二元序列0限制k錯線性復雜度的算法，然后基于定理1，給出一個求周期為2n的二元序列譜免疫度的快速算法。

2.1算法1：0限制k錯線性復雜度算法

輸入:周期為2n的二元非零序列s∞中的一個周期（這里要求k≤ w（s）-1）。

輸出:序列s∞的0限制k錯線性復雜度c。

算法程序偽代碼:

下面用一個算例來進一步說明算法1。

例1 設序列s∞的周期為64，其一個周期序列為s=100010100010000011001000000110100000 0100100111001010010000001111，利用算法1可求出序列s∞的0限制k=21錯線性復雜度是28。具體計算過程如下。

初始值:l=64，k=21，a=s，c=0，m=0

第一步:l=32，k=21，t=20w（b）=16

第二步:l=16，k=5，t=21w（b）=6

第三步:l=8，k=5，t=21w（b）=6

第四步:l=4，k=5，t=21w（b）=2

第五步:l=2，k=3，t=22w（b）=4

第六步:l=1，k=3，t=22w（b）=4

2.2算法1正確性的證明

設S2（2n）表示周期為2n的所有二元序列的集合，若s∞∈S2（2n），算法1僅需考慮s∞的一個周期s。設si表示s的第i比特；L（s）表示s的左半部分的長度為2n-1；R（s）表示s的右半部分，的長度為2n-1；符號aj（1≤j≤n）表示算法1中第j步循環所得到的向量a；a0表示初始向量s，即第一步循環前的向量a；符號bj（1≤j≤n）表示算法1中第j步循環所得到的向量b；符號表示將bj的第i比特由 1改為0時所對應的初始向量s中可能修改的比特的集合。算法1中的m表示在循環過程中向量b改為0的次數。

引理1 設s∞∈S2（2n），則

證明:利用數學歸納法證明如下。

（1）當j=1時，即算法1執行第一步循環得到b1。由可得si=1、si+2n-1=0或si=0、si+2n-1=1，若要將由1改為0，按照0限制的要求，此時需要將si或由1改為0，所以

當j=r時，即算法1執行到第r步循環得到br。若要將由1改為0，由于則有或由于0不能改變，所以此時需要將或由1改為0，這等同于修改或由的定義和歸納假設，有

由（1）和（2），引理1得證。

引理2 如果算法1在第j步循環可以將bj改為0，那么將bj中1個值為1的比特改為0將使得初始向量s中2m個相應的值為1的比特改為0。

證明:注意到m是向量b改為0的次數，其初始值為0，m隨b的這種修改而增加。對m進行數學歸納如下。

（1）當m=0時，若在第r1步循環可以將修改為0，則av=bv=L（av-1）+R（av-1），1≤v＜ r1。因此，第r1步中和中值為1的比特對應s中的1個值為1的比特。由于與文獻［3］中的k錯線性復雜度算法不同，由0限制的原則，將中1個值為1的比特改為0將對應修改L或中1個值為1的比特，因此使得初始向量s中2m=20=1個相應的值為1的比特修改為0。

算法1在第r1步循環將修改為0后，m=1且中每個值為1的比特對應著中各1個值為1的比特，從而對應s中2m=2個值為1的比特。

（2）假設當m=u-1時，若在第r2（＞r1）步循環可以將修改為0，那么將中1個值為1的比特改為0將使得初始向量s中2u-1=2m個相應的值為1的比特改為0。

當m=u時，若在第j（＞r2）步循環可以將bj修改為0，有av=bv=L（av-1）+R（av-1），r2＜v＜j，因此，第j步循環中L（aj-1）和R（aj-1）中值為1的比特對應s中2u個值為1的比特。由于bj=L（aj-1）+R（aj-1），由0限制的原則，將bj中1個值為1的比特改為0將對應修改L（aj-1）或R（aj-1）中1個值為1的比特，因此使得初始向量s中2u=2m個相應的值為1的比特改為0。

由（1）和（2），引理2得證。

引理3 如果在算法1的第j步循環要將bj修改為0，則要修改初始向量s中相應的w（bj）× 2m個值為1的比特。

證明:由引理2，將bj中某個值為1的比特改為0，等價于將初始向量s中2m個值為1的比特改為0；由引理1，顯然i1≠i2。所以，若將bj修改為0需要修改s中 w（bj）×2m個值為1的比特。

定理2 令s∞∈S2（2n），0≤k＜w（s），算法1能在n步內求出序列s∞的0限制k錯線性復雜度。

證明:當k=0時，算法1實際上就是文獻［2］中的Games-Chan算法。如果k＞0，可以通過將s中不超過k個值為1的比特改為0，盡可能地將s的線性復雜度減到最小。

根據Games-Chan算法，當b≠0時，s的線性復雜度將增大，因此減小線性復雜度的方法是盡可能地將每一步的b改為0。具體的策略是:如果在第j步循環能將bj修改為0，必須將其修改為0。這是因為，如此修改將使線性復雜度減小2n-j，而即使第j步循環之后每步都能將b改為0，線性復雜度最多減小2n-j。由引理3，第j步若要將bj修改為0，將對應修改初始向量s中w（bj）×2m個值為1的比特，所以在第j步能否將bj修改為0，取決于是否w（bj）×2m≤k。若第j步將bj修改為0，初始向量s中可被修改的值為1的比特數將減小為k-w（bj）×2m。顯然算法1將在循環n步后結束，且值為0的比特是不可能被修改的，所以算法1能在n步內求出序列s∞的0限制k錯線性復雜度。證畢。

2.3算法2：譜免疫度算法

算法1給出了一個通用的0限制k錯線性復雜度算法，也就是k的值可以取小于w（s）的任何非負整數。依據定理1，本文在算法1的基礎上提出了算法2，具體如下。

輸入:周期為2n的二元非零序列s∞中的一個周期

輸出:序列s∞的譜免疫度P。

算法步驟:

（1）以s、序列周期l=2n、w（s）-1作為算法1的輸入，輸出s∞的0限制w（s）-1錯線性復雜度cs。

（3）計算P=min｛cs，c｝。

由算法步驟可知，算法2可以在2n步內計算出周期為2n的二元序列的譜免疫度，即算法2的時間復雜度為O（n）。

3　結語

序列的譜免疫度是流密碼安全的一個新標準。本文討論了譜免疫度與k錯線性復雜度的內在聯系，提出了0限制k錯線性復雜度的概念，并給出計算周期為2n的二元序列0限制k錯線性復雜度的快速算法，在此基礎上提出了求周期為2n的二元序列譜免疫度的算法，該算法能在2n步內得到計算結果，具有較高的計算效率。

［1］Massey J L.Shift-registers synthesis and BCH decoding［J］.IEEE Transactions on Information Theory，1969，IT-15（1）:122-127.

［2］Games R A，Chan A H.A fast algorithm for determining the complexity of a binary sequence with period 2n［J］.IEEE Transactions on Information Theory，1983，IT-29（1）:144-146.

［3］Stamp M，Martin C F.An algorithm for the k-error linear complexity of binary sequences with period 2n［J］.IEEE Transactions on Information Theory，1993，39（4）:1398-1401.

［4］Kaida T，Uehara S，Imamura K.An algorithm for the k-error linear complexity of sequences over GF（pm）with period pn，p a prime［J］.Information and Computation，1999，151:134-147.

［5］Xiao Guozhen，Wei Shimin，Lam K Y，et al.A fast algorithm for determining the linear complexity of a sequence with period pnover GF（q）［J］.IEEE Transactions on Information Theory，2000，46（6）: 2203-2206.

［6］Wei Shimin，Xiao Guozhen，Chen Zhong.A fast algorithm for determining the minimal polynomial of a sequence with period 2pnover GF（q）［J］.IEEE Transactions on Information Theory，2002，48（10）: 2754-2758.

［7］Wei Shimin，Xiao Guozhen，Chen Zhong.An efficient algorithm for k-error linear complexity［J］. Chinese Journal of Electronics，2002，11（2）:265-267.

［8］魏仕民，肖國鎮，陳鐘.確定周期為2npm二元序列線性復雜度的快速算法［J］.中國科學:E輯，2002，32（3）:401-408.

［9］Chen Hao.Fast algorithms for determining the linear complexity of sequences over GF（pm）with period 2tn［J］.IEEE Transactions on Information Theory，2005，51（5）:1854-1856.

［10］Meidl W.Reducing the calculation of the linear complexity of u2v-periodic binary sequences to Games-Chan algorithm［J］.Des Codes Cryptogr，2008，46（1）:57-65.

［11］Gong Guang，R?njom S，Helleseth T，et al.Fast discrete Fourier spectra attacks on stream ciphers［J］.IEEE Transactions on Information Theory，2011，57（8）:5555-5565.

［12］Courtois N T，Meier W.Algebraic attacks onstream ciphers with linear feedback［C］//Advances in Cryptology-EUROCRYPT 2003.Springer，2003，LNCS 2656:345-359.

［13］Helleseth T，R?njom S.Simplifying algebraic attacks with univariate analysis［C］//Information Theory and Applications Workshop，New York: IEEE，2011:1-7.

［14］Gong Guang.Sequences，DFT and resistance against fast algebraic attacks［C］//Sequences and Their Applications（SETA 2008）.Springer，2008，LNCS 5203:197-218.

［15］Niederreiter H，Shparlinski I E.Periodic sequences with maximal linear complexity and almost maximal k-error linear complexity［C］//Proceedings of Cryptography and Coding，9th IMA International Conference.Springer，2003，LNCS 2898:183-189.

［責任編輯 尚 晶］

Algorithm for spectral immunity of binary sequences with period 2n

Yang Bo1，Liu Nengfei2，She Bing2，Li Shougui1
（1.Hubei Province Key Laboratory of Systems Science in Metallurgical Process，Wuhan University of Science and Technology，Wuhan 430065，China；2.College of Science，Wuhan University of Science and Technology，Wuhan 430065，China）

The concept of 0-constrained k-error linear complexity of a sequence is firstly presented by means of studying the spectral immunity of a periodic sequence.Then an algorithm（A1）for computing the 0-constrained k-error linear complexity of a given binary sequence with period 2nis designed based on the algorithm for computing the k-error linear complexity of this kind of sequences proposed by Mark Stamp.Finally，on the basis of algorithm A1，a fast algorithm for determining the spectral immunity of binary sequences with period 2nis proposed.This algorithm is efficient and its time complexity is O（n）.

stream cipher；linear complexity；k-error linear complexity；binary sequence；spectral attack；spectral immunity；fast algorithm

TP309；TN918.1

A

1674-3644（2016）05-0382-05

2016-04-22

湖北省自然科學基金資助項目（2013CFA131）；武漢科技大學冶金工業過程系統科學湖北省重點實驗室開放基金資助項目（Y201315）；武漢科技大學大學生科技創新基金研究項目（14ZZB100）.

楊 波（1973-），男，武漢科技大學副教授，博士.E-mail:boyangcn@126.com