線性復(fù)雜度為2n2m的2n周期序列的k錯(cuò)線性復(fù)雜度

摘 要:線性復(fù)雜度和k錯(cuò)線性復(fù)雜度是衡量密鑰序列隨機(jī)性的兩個(gè)重要標(biāo)準(zhǔn)，運(yùn)用ChanGames算法，得到線性復(fù)雜度為2n2m的2n周期二元序列的k錯(cuò)線性復(fù)雜度的所有可能的值，LCk(s)=0或2n-2m-2r+1+c，2n-2r+1+c。這一結(jié)果對(duì)于進(jìn)一步探討流密碼密鑰序列的安全性有重要的應(yīng)用價(jià)值。

關(guān)鍵詞:密鑰序列; 線性復(fù)雜度;k錯(cuò)線性復(fù)雜度;ChanGames算法;二元周期序列

中圖分類號(hào):TN918.4文獻(xiàn)標(biāo)志碼:A

文章編號(hào):1001-3695(2010)06-2299-02

doi:10.3969/j.issn.10013695.2010.06.087

kerror linear complexity of 2nperiodic sequences with linear complexity 2n2m

YANG Minghui， ZHU Shixin

(School of Mathematics， Hefei University of Technology， Hefei 230009， China)

Abstract:Linear complexity and kerror linear complexity are two important standards to scale the randomicity of key sequences. For a 2nperiodic binary sequence with linear complexity 2n2m. This paper obtained all the possible values of the kerror linear complexity using ChanGames algorithm， LCk(s)=0 or 2n-2m-2r+1+c，2n-2r+1+c. The result presented of stream cipher is so important that it can be used to analyze the safety of periodic key sequences more deeply.

Key words:key sequence; linear complexity; kerror linear complexity; ChanGames algorithm; periodic binary sequences

對(duì)于有限域F2上2n周期二元序列，文獻(xiàn)[1，2]分別給出了快速計(jì)算2n周期序列的線性復(fù)雜度和k錯(cuò)線性復(fù)雜度的算法。文獻(xiàn)[3]中給出了線性復(fù)雜度等于l(0≤l≤2n，l是整數(shù))的序列的個(gè)數(shù)，且計(jì)算了這類序列的線性復(fù)雜度的期望。文獻(xiàn)[4]討論了任意2n周期序列的k錯(cuò)線性復(fù)雜度小于線性復(fù)雜度的最小的k的表達(dá)式。Meidl在文獻(xiàn)[5]中對(duì)于線性復(fù)雜度為2n的序列給出了1錯(cuò)線性復(fù)雜度的具體形式及期望，并討論了k錯(cuò)(k≥2)線性復(fù)雜度的期望的界，而文獻(xiàn)[6]對(duì)線性復(fù)雜度為2n-1的序列給出了2錯(cuò)線性復(fù)雜度的具體形式及期望。對(duì)于線性復(fù)雜度為2n-2m的序列，文獻(xiàn)[7]研究了其2錯(cuò)線性復(fù)雜度的具體形式及2錯(cuò)誤序列個(gè)數(shù)可能的值。本文通過(guò)應(yīng)用ChanGames算法，給出了線性復(fù)雜度為2n-2m的2n周期二元序列k錯(cuò)(k為正整數(shù))線性復(fù)雜度的具體形式。

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

設(shè)s=(s0，s1，…，sN-1)∞是有限域F2上N周期序列，定義s的Hamming重量為s的一個(gè)周期中非零元素個(gè)數(shù)，記為W(s)。類似地，定義向量sN的Hamming重量為sN中非零元素的個(gè)數(shù)，記為W(sN)。顯然，對(duì)于周期序列s，若sN是其一個(gè)周期，則W(s)=W(sN)。定義F2上周期序列s=(s0，s1，…，sN-1)∞所對(duì)應(yīng)的多項(xiàng)式sN(x)=s0+s1x+…+sN-1xN-1。另外，若N=2n，簡(jiǎn)記s(n)=s2n。

定義s的線性復(fù)雜度LC(s)為能生成該序列的最短線性反饋移位寄存器的長(zhǎng)度。特別地，當(dāng)s為0序列時(shí)，令LC(s)=0。為敘述方便，設(shè)向量sN=(s0，s1，…，sN-1)的線性復(fù)雜度是以sN為一個(gè)周期的序列s=(s0，s1，…，sN-1)∞的線性復(fù)雜度，即LC(s)=LC(sN)。s的k錯(cuò)線性復(fù)雜度[1]是指s(N)中改變至多k個(gè)si，所得到的新周期序列的最小的線性復(fù)雜度，記為L(zhǎng)Ck(s)，即LCk(s)=minw(e)≤kLC(s+e)。其中:e=(e0，e1，…，eN-1)∞，W(e)表示序列e的一個(gè)周期中“1”的個(gè)數(shù)。

給定F2上2n周期二元序列，其線性復(fù)雜度可以由ChanGames算法[2]計(jì)算出來(lái)，該算法是本文的重要工具。下面簡(jiǎn)要介紹ChanGames算法:

ChanGames算法是一個(gè)遞歸過(guò)程，每一步將向量s(m)，1≤m≤n，分成左右兩個(gè)部分:

L(sm)=(s0，s1，…，s2m-1-1)

R(s(m))=(s2m-1，s2m-1+1，…，s2m-1)

如果L(s(m))=R(s(m))，LC(s)=LC(L(s(m)));否則，LC(s)=2m-1+LC(d)。其中d=L(s(m))+R(s(m))。要注意的是僅當(dāng)L(s(m))≠R(s(m))時(shí)，線性復(fù)雜度才能增加。

由ChanGames算法的思想，可以定義一個(gè)F22m到F22m-1的映射φm

φm(s0，s1，…，s2m-1)=(s0+s2m-1，s1+s2m-1+1，…，s2m-1-1+s2m-1)

該映射有下面三個(gè)性質(zhì):

a)W(φm(s(m)))≤W(s(m));

b)當(dāng)m≥2時(shí)，W(φm(s(m)))和W(s(m))同奇偶;

c)s(m)的原像集合

φ-1m+1(s(m))={v∈F22m+1 φm+1(v)=s(m)}

中元素的個(gè)數(shù)為22m。

2 主要結(jié)果

引理1[8] 設(shè)s是2n周期二元序列，則LC(s)=2n當(dāng)且僅當(dāng)W(s)是奇數(shù)。

引理2[5] 設(shè)s是2n周期二元序列，則當(dāng)W(s(n))>k時(shí)，序列s的k錯(cuò)線性復(fù)雜度為L(zhǎng)Ck(s)=2n-2r+1+c。其中1≤r≤n-1，1≤c≤2r-1。

引理3 設(shè)s是2n周期二元序列，若W(s(n))為偶數(shù)，則LC2g(s)=LC2g+1(s)，g為任意非負(fù)整數(shù)。

證明因?yàn)閃(s(n))為偶數(shù)，若每個(gè)周期相同位置改變恰好2g+1個(gè)比特，W(s(n))變成了奇數(shù)，由引理1，序列s的線性復(fù)雜度變成了2n，故LC2g(s)=LC2g+1(s)，g為任意非負(fù)整數(shù)。

設(shè)s是2n周期二元序列，LC(s)=2n-2m，0≤m≤n-1，則由引理1，W(s(n))為偶數(shù)，由引理3，W(s(n))為偶數(shù)時(shí)，LC2g(s)=LC2g+1(s)，g為任意非負(fù)整數(shù)，故下文只考慮k=2h(h≥1)時(shí)序列s的k錯(cuò)線性復(fù)雜度。

定理1設(shè)s是線性復(fù)雜度為2n-2m的2n周期二元序列。其中0≤m≤n-1，則LCk(s)=0或?yàn)槿缦聝煞N形式:

LCk(s)=2n-2m-2r+1+c1≤r≤m-1，1≤c≤2r-12n-2r+1+cm+1≤r≤n-1，1≤c≤2r-1

證明設(shè)s(n)=(s0，s1，…，s2n-1)是序列s的一個(gè)2n-周期所對(duì)應(yīng)的向量，s(t)=φt+1…φn(s(n))=(s(t)0，s(t)1，…，s(t)2t-1)。其中m≤t≤n-1，根據(jù)ChanGames算法，序列s必滿足

L(s(t))≠R(s(t))，m+2≤t≤nL(s(m+1))=R(s(m+1))(1)

且LC(L(s(m+1)))=2m。而s(m)=φm+1(s(m+1))，由式(1)，s(m)=0。由引理1，W(s(n))為偶數(shù)，由映射φn的性質(zhì)a)和b)，W(s(t))為偶數(shù)且W(s(t))≤W(s(n))，m≤t≤n。下面根據(jù)s(n)和s(m+1)的Hamming重量來(lái)分情況討論:

情形1 W(s)=W(s(n))≤k。

根據(jù)k錯(cuò)線性復(fù)雜度的定義，則LCk(s)=0。

情形2 W(s)=W(s(n))>k，W(s(m+1))>k。

當(dāng)j>m時(shí)，W(s(j))>k而且L(s(m+1))=R(s(m+1))，對(duì)s(m+1)改變的k比特即:對(duì)L(s(m+1))與R(s(m+1))作相同的h比特改變，則LCk(s)=2n-1+…+2m+1+f。其中f=LCh(L(s(m+1)))。因?yàn)長(zhǎng)(s(m+1))=R(s(m+1))，W(s(m+1))>k，所以W(L(s(m+1)))>h，又因?yàn)長(zhǎng)(s(m+1))為周期為2m的二元序列，由引理2知f=LCh(L(s(m+1)))=2m-2r+1+c，1≤r≤m-1，1≤c≤2r-1。根據(jù)ChanGames算法的遞歸過(guò)程知，W(s)=W(s(n))>k且W(s(m+1))>k時(shí)s(n)的k錯(cuò)線性復(fù)雜度為

2n-1+…+2m+1+2m-2r+1+c=2n-2m-2r+1+c

1≤r≤m-1，1≤c≤2r-1

情形3 W(s)=W(s(n))>k，W(s(m+1))≤k。設(shè)r是使得W(s(r))，m+1≤r≤n-1至多為k的最大整數(shù)，由W(s(m+1))≤k知這樣的r是存在的。令b=W(s(r))，設(shè)a(n)是由s(n)改變b比特得到的向量，類似s(t)，定義a(t)=(a(t)0，a(t)1，…，a(t)2t-1)，m+1≤t≤n，則向量a(t)和s(t)至多相差b比特并且對(duì)于整數(shù)j，r2n-1+2n-2+…+2r+1。如果改變s(n)中的b=W(s(r))≤k比特使得s(r)變成0，即L(a(r+1))=R(a(r+1))，則a(n)的線性復(fù)雜度形式如下:

Lr，c=2n-1+2n-2+…+2r+1+c=2n-2r+1+c，0≤c≤2r

其中c=LC(L(a(r+1)))。

如果L(a(r+1))≠R(a(r+1))，即a(r)是非零向量，此時(shí)a(n)的線性復(fù)雜度LC滿足

LC>2n-1+2n-2+…+2r+1+2r≥Lr，c

而LCk(s)是由s(n)改變b比特所得到的最小的線性復(fù)雜度，因此LCk(s)=Lr，c。其中c是s(r+1)變化后所能得到的最小的線性復(fù)雜度。不妨設(shè)a(n)就是由s(n)改變b比特得到的線性復(fù)雜度達(dá)到最小值的向量。下面證明c≠0，c≠2r。

設(shè)s(r)=(0，…，0，…，1↑u1，…1↑u2，…1↑ub，…，0)，即

s(r)u1=s(r)u2=…=s(r)ub=1，0≤u1<…

且s(r)j=0，0≤j≤2r-1，j≠u(mài)1，u2，…，ub。則由s(r)=φr+1(s(r+1))，有

s(r+1)u1+s(r+1)u1+2r=1s(r+1)ub+s(r+1)ub+2r=1 (2)

且s(r+1)j=s(r+1)j+2r，0≤j≤2r-1，j≠u(mài)1，…，ub，可以適當(dāng)改變s(r+1)u1，s(r+1)u1+2r，…，s(r+1)ub和s(r+1)ub+2r中b比特來(lái)保證W(L(s(r+1)))變成偶數(shù)，同時(shí)使式(2)中b個(gè)等式變成0，從而使s(r)變成0，由引理1，c≠2r。另外，c=0與r是使得W(s(r))至多為k的最大整數(shù)相矛盾，故1≤c≤2r-1。因此當(dāng)W(s)=W(s(n))>k且W(s(m+1))≤k時(shí)，LCk(s)=2n-2r+1+c，1≤c≤2r-1。

下面通過(guò)一個(gè)具體例子來(lái)說(shuō)明一下本文的主要結(jié)果。

例1 設(shè)n=3，m=1，求線性復(fù)雜度為2n-2m=6的2n周期二元序列s=(11101011)的4錯(cuò)線性復(fù)雜度的范圍。

由于W(s)=W(s(3))=6>4且W(s(2))=2<4，利用情形2的結(jié)論知1≤LC4(s)≤3。計(jì)算得LC4(s)=1，與情形2的結(jié)論相符合。

3 結(jié)束語(yǔ)

本文運(yùn)用ChanGames算法，計(jì)算出F2上線性復(fù)雜度為2n2m的序列s的k錯(cuò)線性復(fù)雜度，對(duì)序列s的k錯(cuò)線性復(fù)雜度的計(jì)數(shù)及期望仍是尚待研究的問(wèn)題。

參考文獻(xiàn):

[1]STAMP M， MARTIN C F. An algorithm for the kerror linear complexity of binary sequences with period 2n[J]. IEEE Trans on Information Theory， 1993，39(4):1398-1401.

[2]GAMES R A，CHAN A H. A fast algorithm for determining the linear complexity of a pseudorandom sequence with period 2n [J]. IEEE Trans on Information Theory，1983， IT29(1):144-146.

[3]RUEPPEL R A. Analysis and design of stream ciphers[M]. Berlin:SpringerVerlag，1986.

[4]KUROSAA K， SATO F， SAKATA T， et al. A relationship between linear complexity and kerror linear complexity[J]. IEEE Trans on Information Theory， 2000， 46(2):694-698.

[5]MEIDL W. On the stability of 2nperiodic binary sequences[J]. IEEE Trans on Information Theory， 2005， 51(3):1151-1155.

[6]ZHU Fengxiang，QI Wenfeng. The 2error linear complexity of 2nperiodic binary sequences with linear complexity 2n-1[J]. Journal of Electronics， 2007， 24(3):390-395.

[7]譚林，戚文峰.F2上2n周期的k錯(cuò)誤序列[J]. 電子與信息學(xué)報(bào)，2008，30(11):2592-2595.

[8]FU Fangwei，NIEDERREITER H， SU Ming. The characterization of 2nperiodic binary sequences with fixed 1error linear complexity[C]//Proc of SETA. Heidelberg:Springer， 2006:88-103.