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

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

（1.武漢科技大學(xué)冶金工業(yè)過(guò)程系統(tǒng)科學(xué)湖北省重點(diǎn)實(shí)驗(yàn)室，湖北武漢，430065；2.武漢科技大學(xué)理學(xué)院，湖北武漢，430065）

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

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

（1.武漢科技大學(xué)冶金工業(yè)過(guò)程系統(tǒng)科學(xué)湖北省重點(diǎn)實(shí)驗(yàn)室，湖北武漢，430065；2.武漢科技大學(xué)理學(xué)院，湖北武漢，430065）

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

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

流密碼安全的一個(gè)重要指標(biāo)是序列的線性復(fù)雜度。線性復(fù)雜度是指產(chǎn)生一個(gè)給定序列的線性反饋移位寄存器的最小級(jí)數(shù)r。利用著名的Berlekamp-Massey算法［1］，一個(gè)敵手竊取序列的2r個(gè)連續(xù)比特就可以得到該序列的聯(lián)接多項(xiàng)式，即完全確定了產(chǎn)生該序列的線性反饋移位寄存器。因此，密碼學(xué)中一個(gè)強(qiáng)的序列必須具有高的線性復(fù)雜度。

設(shè)序列的周期為l，Berlekamp-Massey算法可能需要至少輸入l個(gè)連續(xù)比特才能使輸出穩(wěn)定于正確的聯(lián)接多項(xiàng)式和線性復(fù)雜度，因此當(dāng)線性復(fù)雜度較高且周期較長(zhǎng)時(shí)，Berlekamp-Massey算法的計(jì)算量非常大。為了解決這一問(wèn)題，Games等［2］研究發(fā)現(xiàn)，當(dāng)序列的周期為2n時(shí)，通過(guò)n步計(jì)算就可以求出其線性復(fù)雜度和聯(lián)接多項(xiàng)式，進(jìn)而提出了Games-Chan算法。然而有些序列的線性復(fù)雜度雖然很高，但改變少量比特后其線性復(fù)雜度降為0，穩(wěn)定性極差，很容易被破解，為此Stamp等［3］提出了k錯(cuò)線性復(fù)雜度概念。k錯(cuò)線性復(fù)雜度是指改變?cè)夹蛄忻總€(gè)周期中小于等于k個(gè)相應(yīng)比特所得到的序列的線性復(fù)雜度最小值。Stamp等在文獻(xiàn)［3］中還設(shè)計(jì)了一個(gè)計(jì)算周期為2n的二元序列k錯(cuò)線性復(fù)雜度的高效算法。此后，國(guó)內(nèi)外學(xué)者對(duì)線性復(fù)雜度和k錯(cuò)線性復(fù)雜度算法進(jìn)行了一系列研究［4-10］，得到了一些適用于不同周期或不同有限域上的序列的線性復(fù)雜度或k錯(cuò)線性復(fù)雜度快速算法。

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

本文通過(guò)研究譜免疫度和k錯(cuò)線性復(fù)雜度之間的聯(lián)系，提出0限制k錯(cuò)線性復(fù)雜度的概念，然后在文獻(xiàn)［3］中求周期為2n的二元序列k錯(cuò)線性復(fù)雜度算法的基礎(chǔ)上，設(shè)計(jì)一個(gè)計(jì)算2n周期二元序列0限制k錯(cuò)線性復(fù)雜度的算法，并進(jìn)一步提出一個(gè)計(jì)算該二元序列譜免疫度的算法，采用這一算法可以在2n步內(nèi)得到計(jì)算結(jié)果。

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

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

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

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

為序列s∞的譜免疫度。

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

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

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

2　快速算法

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

2.1算法1：0限制k錯(cuò)線性復(fù)雜度算法

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

輸出:序列s∞的0限制k錯(cuò)線性復(fù)雜度c。

算法程序偽代碼:

下面用一個(gè)算例來(lái)進(jìn)一步說(shuō)明算法1。

例1 設(shè)序列s∞的周期為64，其一個(gè)周期序列為s=100010100010000011001000000110100000 0100100111001010010000001111，利用算法1可求出序列s∞的0限制k=21錯(cuò)線性復(fù)雜度是28。具體計(jì)算過(guò)程如下。

初始值: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正確性的證明

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

引理1 設(shè)s∞∈S2（2n），則

證明:利用數(shù)學(xué)歸納法證明如下。

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

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

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

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

證明:注意到m是向量b改為0的次數(shù)，其初始值為0，m隨b的這種修改而增加。對(duì)m進(jìn)行數(shù)學(xué)歸納如下。

（1）當(dāng)m=0時(shí)，若在第r1步循環(huán)可以將修改為0，則av=bv=L（av-1）+R（av-1），1≤v＜ r1。因此，第r1步中和中值為1的比特對(duì)應(yīng)s中的1個(gè)值為1的比特。由于與文獻(xiàn)［3］中的k錯(cuò)線性復(fù)雜度算法不同，由0限制的原則，將中1個(gè)值為1的比特改為0將對(duì)應(yīng)修改L或中1個(gè)值為1的比特，因此使得初始向量s中2m=20=1個(gè)相應(yīng)的值為1的比特修改為0。

算法1在第r1步循環(huán)將修改為0后，m=1且中每個(gè)值為1的比特對(duì)應(yīng)著中各1個(gè)值為1的比特，從而對(duì)應(yīng)s中2m=2個(gè)值為1的比特。

（2）假設(shè)當(dāng)m=u-1時(shí)，若在第r2（＞r1）步循環(huán)可以將修改為0，那么將中1個(gè)值為1的比特改為0將使得初始向量s中2u-1=2m個(gè)相應(yīng)的值為1的比特改為0。

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

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

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

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

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

證明:當(dāng)k=0時(shí)，算法1實(shí)際上就是文獻(xiàn)［2］中的Games-Chan算法。如果k＞0，可以通過(guò)將s中不超過(guò)k個(gè)值為1的比特改為0，盡可能地將s的線性復(fù)雜度減到最小。

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

2.3算法2：譜免疫度算法

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

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

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

算法步驟:

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

（3）計(jì)算P=min｛cs，c｝。

由算法步驟可知，算法2可以在2n步內(nèi)計(jì)算出周期為2n的二元序列的譜免疫度，即算法2的時(shí)間復(fù)雜度為O（n）。

3　結(jié)語(yǔ)

序列的譜免疫度是流密碼安全的一個(gè)新標(biāo)準(zhǔn)。本文討論了譜免疫度與k錯(cuò)線性復(fù)雜度的內(nèi)在聯(lián)系，提出了0限制k錯(cuò)線性復(fù)雜度的概念，并給出計(jì)算周期為2n的二元序列0限制k錯(cuò)線性復(fù)雜度的快速算法，在此基礎(chǔ)上提出了求周期為2n的二元序列譜免疫度的算法，該算法能在2n步內(nèi)得到計(jì)算結(jié)果，具有較高的計(jì)算效率。

［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］魏仕民，肖國(guó)鎮(zhèn)，陳鐘.確定周期為2npm二元序列線性復(fù)雜度的快速算法［J］.中國(guó)科學(xué):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.

［責(zé)任編輯 尚 晶］

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

湖北省自然科學(xué)基金資助項(xiàng)目（2013CFA131）；武漢科技大學(xué)冶金工業(yè)過(guò)程系統(tǒng)科學(xué)湖北省重點(diǎn)實(shí)驗(yàn)室開(kāi)放基金資助項(xiàng)目（Y201315）；武漢科技大學(xué)大學(xué)生科技創(chuàng)新基金研究項(xiàng)目（14ZZB100）.

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