常祖領, 　王　寧

(1.鄭州大學 數(shù)學與統(tǒng)計學院　河南 鄭州 450001; 2.福建師范大學 福建省網(wǎng)絡安全與密碼技術重點實驗室　福建 福州 350007; 3.中原工學院 理學院　河南 鄭州 450007)

?

二元序列的錯誤線性復雜度性質

常祖領1,2, 王寧3

(1.鄭州大學 數(shù)學與統(tǒng)計學院河南 鄭州 450001; 2.福建師范大學 福建省網(wǎng)絡安全與密碼技術重點實驗室福建 福州 350007; 3.中原工學院 理學院河南 鄭州 450007)

摘要：詳細研究了二元2的冪次周期序列的錯誤線性復雜度的性質.利用Games-Chan算法作為基本工具，詳細分析了2的冪次周期并且嚴格點少的二元序列的密碼學性質.給出了具有兩個嚴格點的序列的詳細性質以及具有三個嚴格點的序列的結構.

關鍵詞：二元序列； Games-Chan算法； 錯誤線性復雜度； 嚴格點

0引言

具有良好偽隨機性的二元序列廣泛應用于信息安全領域中[1—2].現(xiàn)在已經有很多用來度量序列的密碼學性質的準則，二元序列S的線性復雜度，即能夠生成該序列的線性移位寄存器的最小長度是最重要的準則之一[2].序列應具有較大的線性復雜度來抵抗根據(jù)Berlekamp-Massey算法[3]形成的攻擊.對于周期為2n，n>0的二元序列，存在一個Games-Chan算法可以快速地計算出序列的線性復雜度[4]，并且這個算法的復雜度為O(N).

一個好的二元密碼序列不僅要有較大的線性復雜度，當改變一些分量的值時，它的線性復雜度也不能降低太多.這就令研究者們引入了一個新的準則來衡量序列的密碼學性質，即序列的k-錯線性復雜度[5]，而序列的所有k-錯線性復雜度以及對應的k組成的集合被稱為序列的錯誤線性復雜度譜[6].文獻[5]給出了一個對于任意k>0，可以快速計算二元2n周期序列的k-錯線性復雜度的Stamp-Martin算法.文獻[6]推廣了Stamp-Martin算法能夠快速計算出序列的所有k-錯線性復雜度，從而求出錯誤線性復雜度譜.文獻[7]給出了一個新的Stamp-Martin算法可以快速計算出為了使得序列的線性復雜度小于某個常數(shù)，必須改變原序列的分量值的個數(shù)k以及對應的位置.文獻[8]中給出了只有兩個嚴格點的二元2n周期序列的準確分類以及計數(shù).文獻[9]給出了二元2n周期序列的k-錯線性復雜度嚴格小于線性復雜度時最小的k的確切值.

本文將研究二元2n周期序列的錯誤線性復雜度譜，特別是譜中某些特別的嚴格點的性質.對于具有兩個嚴格點的二元序列，將給出這些序列的嚴格計數(shù)結果以及這些序列之間的關系.對于具有3個嚴格點的序列，將研究這些序列的結構，并說明這些序列其實是2個具有2個嚴格點的序列的模2和.本文還將給出一些錯誤線性復雜度譜的性質.

1基本概念

令S=s0,s1,s2,…表示一個二元序列，其中分量si取值于二元域F2={0,1}.如果存在一個正整數(shù)N滿足si+N=si對所有非負整數(shù)i都成立，則稱序列S具有周期N.這時設定S=(s0,s1,s2,…,sN-1).序列S的線性復雜度LC(S)定義為滿足下面方程的最小正整數(shù)L,sj⊕d1sj-1⊕…⊕dLsj-L=0，對所有大于等于L的j都成立，其中系數(shù)d1,…,dL屬于F2，并且⊕表示模2加.如果S為全零序列則線性復雜度為0，否則LC(S)就是能夠生成該序列的線性移位反饋寄存器的最小長度[2].

Games-Chan算法[4]可以快速地計算二元2n周期序列的線性復雜度.

Games-Chan算法：

輸入：S=SN=(s0,s1,s2,…,sN-1), N=2n, n>0;

輸出：LC, S的線性復雜度.

LC=0; l=2n; i=0

whilel>1do

l=l/2; Si=(s0,s1,s2,…,s2l-1)

L=(s0,s1,…,sl-1), R=(sl,sl+1,…,s2l-1); Bi=L⊕R;

ifBi≠0/*這里0表示零序列

LC=LC+l; Si+1= Bi;

else

Si+1= L;

i=i+1;

endwhile

ifSn≠(0)thenLC=LC+1.

這個算法的某一次循環(huán)中，如果Bi≠0，一定有wt(Si-1)≥wt(Si)，這里wt(·)表示序列的漢明重量，即序列一個周期中1的個數(shù).如果Bi=0，一定有wt(Si-1)=2wt(Si).如果序列S是非零序列，則在Games-Chan算法的最后一步中，一定有Sn≠(0)，所以線性復雜度一定會加1.這種情況下序列的線性復雜度可以表示為

LC(S)=a02n-1+a12n-2+…+an-221+an-120+1,ai∈F2,i=0,1,…,n-1,

其中ai=1當且僅當Bi≠0，序列的線性復雜度可以由ai的取值唯一確定.對于上面序列的線性復雜度的表示中，把向量(a0,a1,…,an-1)記為GC(LC(S))，稱其為序列S的GC表示[10—11]，就是LC(S)-1的二進制表示.通過序列的線性復雜度LC(S)的GC表示，能很清楚地知道序列的Games-Chan算法的過程.序列的GC表示在本論文中會經常用到.

引理1[9]對于兩個二元2n周期序列S1和S2，如果LC(S1)≠LC(S2)，則LC(S1⊕S2)=max{LC(S1), LC(S2)}；如果LC(S1)=LC(S2)，則LC(S1⊕S2)< LC(S1).

在文獻[5]中Stamp和Martin定義了N周期二元序列SN=(s0,s1,s2,…,sN-1)的k-錯線性復雜度LCk(S)等于在改變最多不超過k個S的分量的情況下能夠獲得的線性復雜度的最小值，即對于所有的滿足0≤wt(EN) ≤k的N周期二元序列E，LCk(S)=minLC(S⊕E).如果一個序列E具有最小重量并且滿足LCk(S)=minLC(S⊕E)，就稱E為嚴格錯誤序列.

k=0時，LC0(S)=LC(S)，記為(0,LC(S)).隨著k的增加，序列k-錯線性復雜度會逐步降低.對一個可能的錯誤線性復雜度，取對應的最小的k構成二元組(k,LCk(S)).最后一個二元組應是(wt(S),0).把這些二元組構成的集合稱為S的錯誤線性復雜度譜，而每個二元組稱為序列S的錯誤線性復雜度譜的一個嚴格點[6].注意(0,LC(S))一定是序列的第1個嚴格點，而(wt(S),0)一定是最后一個嚴格點.本文主要研究具有2個或3個嚴格點的二元2n周期序列，記序列的第二個嚴格點為(c,LCc(S))，c表示序列的線性復雜度第一次降低時需要改變的分量的最小個數(shù).

2只有兩個嚴格點的序列的性質和計數(shù)

一個二元向量a=(a1,…,an), ai∈F2, 定義

對于序列的線性復雜度第一次降低時需要改變的分量的最小個數(shù)c，文獻[9]和文獻[10]給出了下面結果.

推論1令S為二元2n周期序列且LC(S)≠0，則S的每個周期的重量滿足

當且僅當S只有兩個嚴格點等號成立.如果序列S的周期重量等于c，即序列S具有線性復雜度LC(S)且具有最小重量，則S僅有兩個嚴格點(0,LC(S))和(c,0).令序列的線性復雜度的GC表示為GC(LC(S))= (a0,a1,…,an-1)，則在序列進行Games-Chan算法中一定會有

wt(Si)=21-aiwt(Si+1),i=0,1,…,n-1.

可以看出只有兩個嚴格點的二元2n周期序列每個周期的重量就等于2b，其中b就是GC(LC(S))中0的個數(shù)，根據(jù)引理1，就可以直接推出定理1.

下面給出只有兩個嚴格點的二元2n周期序列的個數(shù)的精確計數(shù).

定理2只有兩個嚴格點的線性復雜度為LC(S)并且GC(LC(S))=(a0,a1,…,an-1)的二元2n周期序列的個數(shù)等于

證明在對序列S進行Games-Chan算法時，考慮其中的結果：S0=S,S1, …,Sn=(1).如果an-1=1，則Sn-1有兩種可能結果(01)和(10)；而如果an-1=0，則Sn-1只有一種可能(11).對于一般情況，當i從n-2到0時，如果ai=0，則Si左右兩半相同且都是Si+1，所以wt(Si)=2wt(Si+1)，Si的可能個數(shù)與Si+1的可能個數(shù)相等,如果ai=1，則Si左右兩半的和等于Si+1，所以wt(Si)=wt(Si+1)，而它們之間的個數(shù)關系為

其中N(·)表示序列的個數(shù).根據(jù)上面的遞歸關系，可以證明這個定理.

只有兩個嚴格點的二元2n周期序列具有很重要的應用.這樣的序列一定是某個序列的嚴格錯誤序列.對于兩個向量(或序列)a=(a1,…,an), b=(b1,…,bn),ai,bi∈F2，它們的交為

a∩b=(a1b1,…,anbn).

定理3令S1和S2為兩個只有兩個嚴格點的二元2n周期序列，則它們的交序列的周期重量滿足

并且上界可達.

證明令這兩個序列的線性復雜度的GC表示分別為:

GC(LC(S1))= (a0,…,an-1)，GC(LC(S2))= (b0,…,bn-1).

注意這兩個序列都是具有對應線性復雜度的重量最小的序列.對它們分別進行Games-Chan算法，分別得到(S1)0=S1, (S1)1,…, (S1)n; (S2)0=S2, (S2)1,…, (S2)n.顯然有(S1)n=(S2)n=(1).如果an-1=bn-1=0，則有(S1)n-1=(S2)n-1=(11)并且有

而如果an-1≠0或者bn-1≠0，則顯然有

注意上式中等號是可以達到的.綜上，無論何種情況，都有

把這個分析推廣到一般情形，則對i從n-1到0，當ai=bi=0時有

而當ai≠0或者bi≠0時有

并且式中等號是可以達到的.根據(jù)上面的分析可得

并且上界可達.

下面的推論說明任意二元2n周期序列，如果有必要的話，可以通過刪除一些序列中的1,而使得最終序列具有同樣的線性復雜度并且具有最小重量，即只具有兩個嚴格點.

推論2令S為二元2n周期序列且LC(S)≠0，則存在一個具有同樣的線性復雜度并且具有最小重量二元2n周期序列S′滿足

S∩S′=S′.

3只有3個嚴格點的序列的結構

令序列的3個嚴格點分別是(0,LC(S))，(c,LCc(S))和(wt(S),0)，其中c等于定理1中的結果.下面定理說明這種序列都是2個只有2個嚴格點的二元2n周期序列的模2和.

定理4令S為二元2n周期序列且只有3個嚴格點(0,LC(S))，(c,LCc(S))和(wt(S),0)，其中c等于定理1中的結果.則S是兩個二元2n周期，線性復雜度分別是LC(S)和LCc(S)的具有最小重量的序列的和，也就是說，這兩個對應的序列只有兩個嚴格點.另外，S的周期重量等于

證明根據(jù)S的3個嚴格點和引理1及定理1，存在二元2n周期序列S1只有兩個嚴格點(并且是同線性復雜度情況下重量最小的序列)滿足LC(S1)=LC(S)以及LC(S⊕S1)= LCc(S)，此時序列S可以記做S=S1⊕(S⊕S1)=S1⊕S2，若S2不是只有2個嚴格點，則根據(jù)推論2，存在只有兩個嚴格點的二元2n周期序列S′滿足與S2有相同的線性復雜度，S2∩S′=S′并且S2≠S′.根據(jù)引理1，

LC(S2⊕S′)

所以S2⊕S′≠S1，從而

wt(S1⊕(S2⊕S′))>0，

由此可推出

wt(S1⊕S′)

并且

0≠LC(S⊕(S1⊕S′))< LCc(S).

從而推出序列S的嚴格點多于3個，引發(fā)矛盾.所以S2只有2個嚴格點.由此推出序列S是2個二元2n周期，線性復雜度分別是LC(S)和LCc(S)的具有最小重量的序列的和.

令S=S1⊕S2.如果

根據(jù)定理3，存在一個只有2個嚴格點線性復雜度等于LC(S2)的二元2n周期序列S′，使得

這樣根據(jù)公式

wt(S1⊕S2)=wt(S1)+wt(S2)-2wt(S1∩S2),

可推出

wt(S1⊕S′)

再根據(jù)引理1

0≠LC(S⊕(S1⊕S′))

這也說明序列S的嚴格點多于3個，引發(fā)矛盾.綜合上面分析即可推出S=S1⊕S2的周期重量等于

定理得證.

根據(jù)定理4的證明過程可以看出，并不是任意2個只有2個嚴格點的序列的和就是一個具有3個嚴格點的序列，還必須要求這2個序列的交的重量達到定理3中的上界才行.另外對于具有3個嚴格點的序列的3個嚴格點(0,LC(S)), (c,LCc(S))和(wt(S),0)中的LCc(S)也不是可以任意給定的.如果

根據(jù)定理4能夠容易地推出如下推論.

推論3 令S是二元2n周期序列且至少有3個嚴格點(0,LC(S))，(c,LCc(S)), (d,LCd(S)), …, 則有

4結論

本文研究了具有較少嚴格點的二元2n周期序列的一些密碼學性質，而Games-Chan算法是我們的主要工具.對于只有2個嚴格點的序列，推導出一些有意義的性質，包括它們的計數(shù)和交等性質.對于只有3個嚴格點的序列，本文研究了它們的結構，說明這些序列都是2個只有2個嚴格點序列的和的形式，并由此推出一些有意義的結果,這些結果在研究二元2n周期序列的密碼學性質中有很好的應用價值.

參考文獻：

[1]MENEZESAJ,OORSCGOTPC,VANSTONESA.Handbookofappliedcryptography[M].BocaRatonFL:CRCPress, 1996: 176—233.

[2]RUPPELRA.Analysisanddesignofstreamciphers[M].NewYork:Springer-Verlag, 1986: 133—200.

[3]MASSEYJL.ShiftregistersynthesisandBCHdecoding[J].IEEEtransactionsoninformationtheory, 1969, 15(1): 122—127.

[4]GAMESRA,CHANAH.Afastalgorithmfordeterminingthecomplexityofapseudo-randomsequencewithperiod2n[J].IEEEtransactionsoninformationtheory, 1983, 29(1): 144—146.

[5]STAMPM,MARTINCF.Analgorithmforthek-errorlinearcomplexityofbinarysequenceswithperiod2n[J].IEEEtransactionsoninformationtheory, 1993, 39(4): 1398—1401.

[6]LAUDERA,PATERSONK.Computingtheerrorlinearcomplexityspectrumofabinarysequenceofperiod2n[J].IEEEtransactionsoninformationtheory, 2003, 49(1): 273—280.

[7]SALAGEANA.Onthecomputationofthelinearcomplexityandthek-errorlinearcomplexityofbinarysequenceswithperiodapoweroftwo[J].IEEEtransactionsoninformationtheory, 2005, 51(3): 1145—1150.

[8]ETZIONT,KALOUPTSIDISTN,KOLOKOTRONISN,etal.Propertiesoftheerrorlinearcomplexityspectrum[J].IEEEtransactionsoninformationtheory, 2009, 55(10): 4681—4686.

[9]KUROSAWAK,SATOF,KISHIMOTOW.Arelationbetweenlinearcomplexityandk-errorlinearcomplexity[J].IEEEtransactionsoninformationtheory, 2000, 46(2): 694—698.

[10]CHANGZ,WENQ.Onthecryptographicpropertiesofbinary2n-periodicsequences[J].Chinesejournalofelectronics, 2011, 20(2): 307—311.

[11]CHANGZ,WANGX.Onthefirstandseconderrorlinearcomplexityofbinary2n-periodicsequences[J].Chinesejournalofelectronics, 2013, 22(1): 1—6.

(責任編輯：方惠敏)

Properties of Error Linear Complexity of Binary Sequences

CHANG Zuling1,2, WANG Ning3

(1.SchoolofMathematicsandStatistics,ZhengzhouUniversity,Zhengzhou450001,China;2.FujianProvincialKeyLaboratoryofNetworkSecurityandCryptology,FujianNormalUniversity,Fuzhou350007,China;3.CollegeofScience,ZhongyuanUniversityofTechnology,Zhengzhou450007,China)

Abstract:The properties of error linear complexity of binary sequences with period power of 2 were studied. With Games-chan algorithm as the main tool, the cryptographic properties of binary sequences with period power of 2 and few critical points were considered. The properties of sequences with two critical points and the structure of sequences with three critical points were provided.

Key words:Binary sequence; Games-Chan algorithm; error linear complexity; critical point

收稿日期:2015-09-17

基金項目:國家自然科學基金聯(lián)合基金資助項目(u1301604)；河南省教育廳科學技術研究重點項目(14A110022);福建省網(wǎng)絡安全與密碼技術重點實驗室(福建師范大學)開放課題(15005).

作者簡介:常祖領(1976—), 男, 河南新鄉(xiāng)人,副教授,博士, 主要從事密碼學、編碼理論以及序列的研究，E-mail: zuling_chang@zzu.edu.cn.

中圖分類號：TN918.1

文獻標志碼：A

文章編號：1671-6841(2016)01-0032-05

DOI:10.3969/j.issn.1671-6841.201509016

引用文本: 常祖領, 王寧. 二元序列的錯誤線性復雜度性質[J]. 鄭州大學學報(理學版)，2016，48(1)：32—36.