具有第二下降點6錯線性復雜度的2n周期序列*

王喜鳳，張　偉，周建欽安徽工業大學 計算機科學與技術學院，安徽 馬鞍山 243002

?

具有第二下降點6錯線性復雜度的2n周期序列*

王喜鳳，張偉+，周建欽
安徽工業大學 計算機科學與技術學院，安徽 馬鞍山 243002

WANG Xifeng,ZHANG Wei,ZHOU Jianqin.2n-periodic binary sequences with 6-error linear complexity as the second descent point.Journal of Frontiers of Computer Science and Technology,2016,10(6):838-846.

摘要：線性復雜度和k錯線性復雜度是衡量流密碼強度的重要指標，通常這兩個指標越大就越能抗擊明文攻擊。為了更進一步地研究密鑰流序列，利用構造方法和方體理論分析了具有第二下降點6錯線性復雜度的2n周期序列，得到了所有可能6錯線性復雜度的取值形式。分析并推導了具有2錯線性復雜度為第一次下降點且6錯線性復雜度為第二次下降點的2n周期序列的計數公式。使用這種方法也可以推導出其他具有第二次下降點或者第三次下降點的k錯線性復雜度序列的相關性質。

關鍵詞：周期序列；線性復雜度；k錯線性復雜度；方體理論

ISSN 1673-9418CODEN JKYTA8

Journal of Frontiers of Computer Science and Technology

1673-9418/2016/10(06)-0838-09

E-mail:fcst@vip.163.com

http://www.ceaj.org

Tel:+86-10-89056056

1　引言

將能夠產生序列s的最短的線性反饋移位寄存器（linear feedback shifting register，LFSR）的級數稱為序列s的線性復雜度，記為L(s)。線性復雜度L(s)及其穩定性在衡量流密碼的強度時具有重要作用。通常線性復雜度足夠大就越能抗擊明文攻擊，但是有些序列的線性復雜度不穩定，改變一個周期內的若干個元素就能使序列的線性復雜度產生極大的變化。為了更好地衡量流密碼的強度，我國學者Ding等人[1]率先提出了重量復雜度和球體復雜度。隨后，國外學者Stamp等人[2]又提出了k錯線性復雜度的概念。k錯線性復雜度Lk(s)反映了序列線性復雜度的穩定性[3-6]。

為了研究一個序列s的k錯線性復雜度在哪些點下降。Etzion等人[7]最早提出了關鍵線性復雜度分布（critical error linear complexity spectrum，CELCS）的概念，CELCS由一系列關鍵錯誤點(k,Lk(s))構成，滿足k

本文以Games-Chan算法[14]為基礎，利用方體理論，研究了具有2錯線性復雜度為第一次下降點且6錯線性復雜度為第二次下降點的周期序列的性質；分析了兩次線性復雜度下降的關系，給出了6錯線性復雜度的取值形式，并且給出了滿足這種情況的序列的計數公式。

2　預備知識與引理

首先介紹幾個重要的引理和定義，然后介紹基于Games-Chan算法的方體理論，以及如何用篩選法確定關鍵錯誤線性復雜度分布。

設有限域GF（2）上的兩個向量分別為：α=(x1,x2, …,xn)和 β=(y1,y2,…,yn)，則定義 α+β=(x1+y1,x2+ y2,…,xn+yn)，本文討論的序列都是在有限域GF（2）中的序列，其中“+”和“⊕”運算都為模2運算。

2.1相關定義和引理

文獻[15-20]具體介紹了方體理論及相關性質，這里只給出下文將要用到的相關定義。

引理1[15]設周期N=2N的二元序列s，其線性復雜度L(s)=2n，當且僅當該序列的一個周期中漢明重量為奇數。

引理2[16]設周期N=2N的二元序列s1和s2，若L(s1)=L(s2)，則L(s1+s2)

則映射具有以下性質：

注：WH(s(n))意為序列s(n)的漢明重量。

引理4[18]設滿足線性復雜度為L,0≤L≤2n的二元周期序列的個數N(L)為：

定義1[19]設存在正整數x和y，若二進制周期序列s中兩個元素位置差為(2x+1)×2y，則稱這兩個元素的距離為2y。

定義2[19]設周期為2n的二元序列s中有2m個非零元素，其中0≤i1

引理5[20]設s為周期為2n的二元序列且為m方體，若m方體的邊長分別為2i1,2i2,…,2im且0≤i1< i2<…

2.2篩選法

設c為二元序列s的k錯線性復雜度，e是漢明重量為k的誤差序列，那么設s=t+e，L(t)=c。若有如下框架：設T={t|L(t)=c}，E={e|WH(e)=k}，TE={t+e| t∈T,e∈E}，其中e是WH(e)=k的序列，t是線性復雜度為c的序列。使用篩選法，目的是從TE中篩選出Lk(t+e)=c的序列t+e。

對于給定線性復雜度c，求滿足Lk(t+e)=c的序列t+e，需要排除一些不滿足條件的序列。此時不滿足條件的序列有兩類：一類是 t+u∈TE，但Lk(t+u)

對于Lk(t+u)

對于 Lk(x+u)=Lk(y+v)=c，但 x+u=y+v的情況。由x+u=y+v可知x+y=u+v；又因為L(x)=L(y)= c,根據引理2知L(x+y)

3　具有第二下降點6錯線性復雜度的周期序列計數

首先使用方體理論來分析k錯線性復雜度的第一次和第二次下降的關系，并給出所有可能的取值形式。然后給定序列線性復雜度的第一次下降點和第二次下降點，求出滿足條件的所有可能序列的計數。

定理1 設周期二元序列 s(n)，若 L6(s(n))

證明 利用反證法進行證明，假設i0?{i,j,k}。

存在2n周期二元序列s(n)，序列s(n)改變兩個元素得到序列u={1111 0000 1111 0000}。此時序列u的線性復雜度L(u)=L2(s(n))=2n-(20+21+23)，可知i=0, j=1,k=3。若存在i0?{i,j,k}，那么i0=2或i0=4。

當i0=2時，因為序列 s(n)的線性復雜度 L(s(n))= 2n-2i0，所以存在序列v={1000 1000 0000 0000}使得u+v={0111 1000 1111 0000}，并且序列s(n)的線性復雜度L(s(n))=L(u+v)=2n-22。此時序列s(n)改變兩個元素后線性復雜度出現第一次下降且L(u)=L2(s(n))= 2n-(20+21+23)=5，根據序列性質知第二次下降點Lk(s(n))

式中“…”代表L(u+v+t)，并且

可以看出，只有當k=8時，即WH(t)=8時，序列線性復雜度才出現第二次下降，此時與條件矛盾。

當i0=4時，序列s(n)的線性復雜度L(s(n))=2n-24，因為n=i0=4，根據方體理論的性質，當i0=4時，兩個非零元素的距離為24=16。因為序列的長度為16，所以兩個非零元素的最長距離為8。從而不存在i0=4這種情況。

綜上所述，只有當k=8時，即WH(t)=8時，序列線性復雜度才出現第二次下降，此時與條件矛盾。因此假設不成立，則i0∈{i,j,k}。

定理2已知周期為2n的二元序列 s(n)，且L(s(n))<2n，則：

（1）L6(s(n))L(c2)>…，其中c1是1方體，c2是3方體，且c1、c2的非零元素均不重合，或有一個重合，或有兩個重合這3種情況。其中有兩個重合這種情況等價于c1是1方體，c2是2方體，且c1、c2的非零元素均不重合。

（2）L6(s(n))

證明（1）①必要性：由Kurosawa[4]知，一個周期為s(n)的二元序列s，線性復雜度為：

存在kmin=2m使得序列s的k錯線性復雜度小于L(s(n))。因c1是1方體，c2是3方體，則L5(s(n))=L4(s(n))=L2(s(n))。

當c1、c2的非零元素均不重合時，去掉c1的兩個非零元素線性復雜度第一次下降。在c1上增加6個1將變成一個3方體，和c2形成一個4方體，此時線性復雜度第二次下降，即L6(s(n))

當c1的非零元素和c2的一個非零元素重合時，將c2中重合的位置加上非零元素，將c1中沒有重合的非零元素去掉，即將序列s(n)中的c1去掉，此時L2(s(n))

當c1的非零元素和c2非零元素都相交時，將c2中兩個重合的位置加上非零元素，此時3方體c2決定著此時序列的線性復雜度，故L2(s(n))

②充分性：假設c1、c2、c3均為1方體，其中3個方體的非零元素互不重合，且在c1、c2、c3中添加兩個非零元素時，不能構成一個方體。首先去掉c1時，線性復雜度下降；再同時去掉c1和c2時，線性復雜度再次下降，即L4(s(n))

假設c1為1方體，c2為2方體，c1和c2的非零元素可以不重合，可以有一個重合，也可以有兩個重合。當 c1和 c2的非零元素可以不重合時，如{1111 1100 0000 0000}，此時等價于c1為1方體，c2為3方體，且c1和c2非零元素有兩個重合。當c1和c2非零元素有兩個重合時，分別去掉c1和c2非零元素，則線性復雜度下降，即L4(s(n))

假設c1為1方體，c2為4方體，c1和c2的非零元素可以不相交，可以有一個重合，可以有兩個重合。因為c2為4方體，所以第二次下降至少需要改變14個非零元素線性復雜度才下降，即L14(s(n))

綜上所述，只有當c1為1方體，c2為3方體時滿足上述情況。

（2）由（1）易知L6(s(n))

定理3設序列s(n)為周期為2n的二元序列，如果L6(s(n))

證明 T={t|L(t)=L}，E={e|L(e)=6}，TE={t+e|t∈T,e∈E}，其中L(t)=L6(s(n))，WH(e)=6，L2(s(n))=2n-(2i+ 2j+2k)，使用篩選法，從TE中篩選出L6(t+e)=L的序列t+e。關于L6(t+e)

當i0=i時{i1,i2,i3}不包含{i,j},{i,k}。假設n=5，i01，i=0，j=1，k=3。

則存在序列

則存在序列

同理可證：當i0=j時{i1,i2,i3}不包含{i,j},{j,k}；i0= k時{i1,i2,i3}不包含{i,k},{j,k}。

同理，v={0101 0000 1100 0000 0101 0000 0000 0000}時，可證i1≠i；v={0111 0000 0100 0000 1000 0000 1000 0000}時，可證i1≠k;v={0111 1000 0100 1000 0000 0000 0000 0000}時，可證i2≠k。

定理4設s(n)是2n周期的二元序列，線性復雜度為2n。

（1）L2(s(n))=2n-(2i+2j+2k),L6(s(n))

①當i0=i時

（2）若L6(s(n))=0，則滿足上述條件的2n周期的二元序列s(n)的個數有如下3種情況：

①當i0=i時

②當i0=j時

③當i0=k時

證明 定理4的證明過程中，首先利用構造法分析出L6(s(n))=0的情況的具體個數，然后利用篩選法，篩選出符合條件的L6(s(n))≠0的序列，具體過程如下：

（1）由引理知，線性復雜度L(t)=L的2n周期二元序列t的個數是2L-1。

（2）下面推導當i0=i時序列e的個數，其中WH(e)=6且L2(e)=2n-(2i+2j+2k)。

步驟1設s(i)是周期為2i的二元序列，線性復雜度為2i且WH(s(i))=1，則s(i)的個數為2i。

步驟2設s(i+1)是周期為2i+1的二元序列，線性復雜度為2i+1-2i=2i且WH(s(i+1))=2，則s(i+1)的個數為2i。

步驟3當 j>i時，設s(j)是周期為2j的二元序列，線性復雜度為2j-2i且WH(s(j))=2，則s(j)的個數為2i×(22)j-i-1。

步驟4設s(j+1)是周期為2j+1的二元序列，線性復雜度為2j+1-(2i+2j)且WH(s(j+1))=4，則s(j+1)的個數為2i×(22)j-i-1。

步驟5當k>j時，設s(k)是周期為2k的二元序列，線性復雜度為2k-(2i+2j)且WH(s(k))=4，則s(k)的個數為2i×(22)j-i-1×(24)k-j-1。

步驟6已知序列s(k)中已經有4個非零元素分別是p1、p2、p3、p4，在序列s(k+1)上加兩個非零元素p5、p6，構成周期為2k+1的二元序列s(k+1)。因p5、p6的距離為2k-2i，使p5、p6和 p1、p2、p3、p4任意元素的距離為2k，則一共有4種方案，若p1、p2和p5、p6的距離為2k，則剩下的兩個元素p3、p4有22種選擇，則s(k+1)序列的個數為2i×(22)j-i-1×(24)k-j-1×4×22。

步驟7當s>k時，設s(n)是周期為2n的二元序列，線性復雜度為2n-(2i+2j+2k)且WH(e)=6，則序列s(n)的個數是2i×(22)j-i-1×(24)k-j-1×4×22×(26)n-k-1。

由上可知，當i0=i時，滿足e∈E，L(e)=2n-2i0，L2(e)=2n-(2i+2j+2k)，i0=i的序列e的個數為：

同理可證，當i0=j時，滿足e∈E，L(e)=2n-2i0，的序列e的個數：

當 i0=k時，滿足 e∈E，L(e)=2n-2i0，L2(e)= 2n-(2i+2j+2k)，i0=k的序列e的個數為：

由上可知，當L6(s(n))=0時，滿足條件的周期為2n的二元周期序列s(n)在i0=i,i0=j,i0=k這3種情況下的個數。

（3）因s+u,t+v∈SE，L6(s+u)=L6(t+v)=L，其中s≠t，u≠v，但s+u=t+v，檢查是否存在序列v，WH(u)=WH(v)=6，使L(u+v)=L(s+t)

①序列v的個數與參數α、β相關，其中β<α

下面討論i0=i時重復序列的具體個數：任給u∈E，存在1個序列v，使L(u+v)=2n-(2i+2α+2k)< L，此時 λi=1；存在2個序列 v，使 L(u+v)=2n-(2α+2k)

下面舉例證明，假設n=5，i0=1，i=1，j=2，k=4，α=3

則存在序列

使L(u(5)+v(5)1)=2n-(2i+2α+2k)=25-(21+23+24)<25-(20+23+24)=L，則存在

同理可得，i0=j時，任給u∈E，存在1個序列v，使L(u+v)=2n-(2j+2α+2k)

下面分別舉例說明i0=i，i0=j，i0=k的情況：

當i0=i時，假設n=5，i0=1，i=1，j=2，k=3，已知序列

則存在序列

同理可證：

綜上所述，定理4得證。

下面舉例來進一步驗證定理4，并且其正確性已用計算機程序進行了驗證。

例1n=5，i0=0，i=0，j=1，k=3，i1=1，i2=2，

例2n=5，i0=3，i=0，j=1，k=3，i1=0，i2=2，

4　結論

本文在Games-Chan算法和篩選法的基礎上，用方體理論和篩選法研究周期為2n的二進制序列s(n)的6錯線性復雜度的相關性質，其中序列s(n)的2錯線性復雜度是第一次下降，序列s(n)的6錯線性復雜度是第二次下降。給出了6錯線性復雜度的所有可能的取值形式，并且推導出了完整的計數公式。對于其他具有第二次下降點k錯線性復雜度序列，也能使用此種方法。同理可研究具有三次下降點k錯線性復雜度的序列。

References:

[1]Ding Cunsheng,Xiao Guozhen,Shan Weijuan.The stability theory of stream ciphers[M]//Lecture Notes in Computer Science 561.Berlin,Heidelberg:Springer,1991:85-88.

[2]Stamp M,Martin C.F.An algorithm for the k-error linear.co mplexity of binary sequence with period2n[J].IEEE Transactions on Information Theory,1993,39(4):1398-1401.

[3]Kurosawa K,Sato F,Sakata T,et al.A relationship between linear complexity and k-error linear complexity[J].IEEE Transactions on Information Theory,2000,46(2):694-698.

[4]Tan Lin,Qi Wenfeng.Linear complexity and k-error linear complexity for2mpn-periodic binary sequences[J].Journal on Communication,2008,29(7):44-49.

[5]Zhou Jianqin.On the 3-error linear complexity of2n-periodic binary sequences with linear complexity2n[J].Acta MathematicaeApplicatae Sinica,2013,36(3):399-413.

[6]Fu Fangwei,Niederreiter H,Su Ming.The characterization of2n-periodic binary sequences with fixed 1-error linear complexity[C]//LNCS 4086:Proceedings of the 4th International Conference on Sequences and Their Applications,Beijing,China,Sep 24-28,2006.Berlin,Heidelberg:Springer, 2006:88-103.

[7]Etzion T,Kalouptsidis N,Kolokotronis N,et al.Propertics of the error linear complexity spectrum[J].IEEE Transactions on Information Theory,2009,55(10):4681-4686.

[8]Pi Fei,Qi Wenfeng.The 4-error linear complexity of binary periodic sequences[J].Acta Electronica Sinica,2011,39 (12):2914-2920.

[9]Niu Zhihua,Guo Danfeng.New algorithm for computing minerror linear complexity ofpn-periodic binary sequences[J]. Journal of ComputerApplications,2013,33(1):12-14.

[10]Wang Hongcui,Zhou Jianqin.Original sequence counting functions ofpnperiodic sequence 3-error linear complexity[J]. Journal of Hangzhou Dianzi University,2013(6):37-40.

[11]Zhou Jianqin.On the 2-error linear complexity of2n-periodic balanced binary sequences[J].Journal of Suzhou University of Science and Technology:Natural Science Edition,2013, 30(4):1-7.

[12]Zhou Jianqin,Liu Wanquan,Wang Xifeng.Structure analysis on the k-error linear complexity for2n-periodic binary sequence[J/OL].arXiv:1312.6927v2(2014-08-09)[2015-03-11].http://arxiv.org/pdf/1312.6927.pdf.

[13]Games R A,Chan A H.A fast algorithm for determining the complexity of a binary sequence with period2n[J].IEEE Transactions on Information Theory,1983,29(1):144-146.

[14]Zhou Jianqin,Liu Wanquan.On the k-error linear complexity for2n-periodic binary sequences via cube theory[J].arXiv: 1309.1829v1(2013-09-07)[2015-03-11].http://arxiv.org/ pdf/1309.1829.pdf.

[15]Zhou Jianqin,Liu Wanquan.The k-error linear complexity distribution for2n-periodic binary sequences[J].Designs, Codes and Cryptography,2014,73(1):55-75.

[16]Meidl W.On the stablity of2n-periodic binary sequences[J]. IEEE Transactions on Information Theory,2005,51(3): 1151-1155.

[17]Rueppel R A.Analysis and design of stream ciphers[M]. Berlin:Springer-Verlag,1986.

[18]Zhou Jianqin,Dai Xiaoping.On the stable k-error linear complexity of periodic sequences[J].Journal on Communication,2011,32(11A):213-220.

[19]Zhu Fengxiang,Qi Wenfeng The 2-error linear complexity of 2n-periodic binary sequences with linear complexity2n-1[J]. Journal of Electronics,2007,24(3):390-395.

[20]Zhou Jianqin,Ouyang Kongli.On k-error linear complexity ofpn-periodic sequences overGF(q)[J].Journal of Jishou University:Natural Science Edition,2013,34(6):41-46.

附中文參考文獻：

[4]譚林,戚文峰.2mpn周期二元序列的線性復雜度和k錯線性復雜度[J].通信學報,2008,29(7):44-49.

[5]周建欽.具有2n線性復雜度的2n周期二元序列的3錯線性復雜度[J].應用數學學報,2013,36(3):399-413.

[8]皮飛,戚文峰.二元周期序列的4-錯線性復雜度[J].電子學報,2011,39(12):2914-2920.

[9]牛志華，郭丹峰.計算pn周期二元序列的最小錯線性復雜度新算法[J].計算機應用,2013,33(1):12-14．

[10]王洪翠,周建欽.pn周期序列3錯線性復雜度原序列計數公式[J].杭州電子科技大學學報,2013(6):37-40.

[11]周建欽.2n周期平衡二元序列的2錯線性復雜度[J].蘇州科技學院學報:自然科學版,2013,30(4):1-7.

[18]周建欽,戴小平.具有穩定k錯線性復雜度的周期序列[J].通信學報,2011,32(11A):213-220.

[20]周建欽,歐陽孔禮.GF(q)上pn-周期序列的k錯線性復雜度[J].吉首大學學報:自然科學版,2013,34(6):41-46.

WANG Xifeng was born in 1980.She is a lecturer at Anhui University of Technology.Her research interests include communication,information security and cryptography,etc.

王喜鳳（1980—），女，山東成武人，碩士，安徽工業大學講師，主要研究領域為通信，信息安全，密碼學等。

ZHANG Wei was born in 1989.He is an M.S.candidate at Anhui University of Technology.His research interests include information security and cryptography,etc.

張偉（1989—），男，安徽合肥人，安徽工業大學碩士研究生，主要研究領域為信息安全，密碼學等。

ZHOU Jianqin was born in 1963.He received the M.S.degree from Fudan University in 1989.Now he is a professor at Anhui University of Technology.His research interests include communication,information security and cryptography,etc.

周建欽（1963—），男，山東巨野人，1989年于復旦大學獲得碩士學位，現為安徽工業大學教授，主要研究領域為通信，信息安全，密碼學等。

*The National Natural Science Foundation of China under Grant No.61300059(國家自然科學基金);the Natural Science Foundation of Anhui Province under Grant No.1208085MF106(安徽省自然科學基金);the Natural Science Research Project of Anhui Colleges under Grant No.KJ2013Z025(安徽省教育廳自然科學研究項目);the Youth Foundation Project of Anhui University of Technology under Grant No.QZ201412(安徽工業大學青年基金項目).

Received 2015-04,Accepted 2015-09.

CNKI網絡優先出版:2015-10-14,http://www.cnki.net/kcms/detail/11.5602.TP.20151014.1722.002.html

+Corresponding author:E-mail:waynezh89@163.com

文獻標志碼：A

中圖分類號：TN918.1

doi:10.3778/j.issn.1673-9418.1504035

2n-Periodic Binary Sequences with 6-Error Linear Complexity as the Second Descent Point?

WANG Xifeng,ZHANG Wei+,ZHOU Jianqin
Computer Science and Technology School,Anhui University of Technology,Ma’anshan,Anhui 243002,China

Abstract:The linear complexity and the k-error linear complexity are important indicators to measure the strength of stream ciphers,and the higher of those two indicators could resistance the plaintext attack than others,generally. In order to research the sequence of stream cipher,this paper uses a structural approach and cube theory in investigating the 2n-periodic binary sequences with 6-error linear complexity as the second descent point,and gets all the possible value forms of 6-error linear complexity.This paper analyzes and derives the complete counting functions of 2n-periodic binary sequences with the given first descent point 2-error linear complexity and second descent point 6-error linear complexity.With the method proposed in this paper,other second or third descent point of the k-error linear complexity for 2n-periodic binary sequences can be obtained.

Key words:periodic sequence;linear complexity;k-error linear complexity;cube theory