具有第二下降點12錯線性復雜度的周期序列

陶　陶，呂家偉

(安徽工業大學計算機科學與技術學院，安徽馬鞍山 243002)

?

具有第二下降點12錯線性復雜度的周期序列

陶陶，呂家偉

(安徽工業大學計算機科學與技術學院，安徽馬鞍山 243002)

[摘要]流密碼序列的線性復雜度和k-錯線性復雜度是度量密鑰流安全性的重要指標。一般情況下，線性復雜度的高低與密鑰流的安全性成正比，但會存在序列線性復雜度不穩定的情況。因此在密碼學上的研究具有高線性復雜度和k-錯線性復雜度的序列成為熱門的研究課題。為了進一步研究序列流的穩定性與安全性問題，本文在結合了關鍵錯誤線性復雜度分布等理論的基礎上，研究在4錯時發生第一下降并在12錯時發生第二下降的周期序列的相關性質。

[關鍵詞]周期序列；線性復雜度；篩選；方體；k-錯線性復雜度

將能夠產生序列s的最短的線性反饋移位寄存器(LinearFeedbackShiftingRegister，LFSR)的級數稱為序列s的線性復雜度[1]，記為L(s).為了研究一個序列s的k-錯線性復雜度在哪些點下降，Etzion等[2]提出了關鍵線性復雜度分布(CriticalErrorLinearComplexitySpectrum，CELCS)的概念.在已知第一次下降點k的序列中，嘗試再次改變k′個元素后，且k

本文根據Etzion提出的關鍵錯誤線性復雜度分布等相關理論，研究在k=4時，第一次發生下降的序列，且在這些序列上進一步探討k′=12時，即序列發生第二次下降的情況.推算出滿足上述條件的周期序列的相關性質.

1預備知識與引理

本文研究的序列都是在有限域GF(2)域中的序列，以下引入幾個重要的引理和定義并介紹方體理論等相關概念.

1.1相關定義和引理

下面介紹方體理論及其相關性質.

引理1[3]設有周期N=2n的兩個二元序列s1和s2，當L(s1)=L(s2)時，可得L(s1+s2)

引理2[4]設周期N=2n的二元序列s，當且僅當序列的一個周期中Hamming重量為奇數時，此時存在線性復雜度L(s)=N.

1.2方體理論的相關性質

定義1[6]設周期為2n的二元序列s，若s中兩個非零元素對應的下標的差可表示成(2x+1)×2y(x,y∈Z+)的樣式，則認為這兩個非零元素之間的距離為2y，且可以形成長度為2y的邊.

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

引理5[7]設s是周期為2n的二元序列，且s為一個m-cube.若m-cube的邊長分別為2i1,2i2,…，2im其中0≤i1

引理6[8]設s為2n周期的二元序列，線性復雜度L(s)=2n-(2i1+2i2+…+2im).設k為使得序列s線性復雜度發生下降為最小值時的取值，即有Lk(s)

1.3關于篩選法的相關概念

通過使用篩選法和Games-Chan算法可研究在周期為2n的二元序列上的k-錯線性復雜度，構造方式是基于如下框架：

對于周期為2n的二元序列s，Lk(s)=c，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)

2具有第二下降點12錯的周期序列的相關性質

首先分析k-線性復雜度的第一下降點和第二下降點的關系，推導出其滿足下降點序列的相關定理并加以證明.

定理1設以2n為周期的二元序列s(n)，若有L(s(n))=L2(s(n))>L4(s(n))=L10(s(n))>L12(s(n)),L(s(n))=2n-(2i1+2i2)，且L4(s(n))=2n-(2j1+2j2+2i3+2j4)，那么{i1,i2}{j1,j2,j3，j4}.

證明利用反證法，設(1)i1?{j1，j2，j3，j4}或i2?{j1,j2,j3,j4};(2){i1,i2}{j1,j2,j3,j4}.

對于(1)，此處設i2?{j1,j2,j3,j4}，存在25周期二元序列s(5)，序列s(5)改變4個元素后得到序列u={1111 0000 1111 0000 1111 0000 1111 0000},此時序列u的線性復雜度L(u)=L4(s(5))=25-(20+21+23+24)，即得j1=0,j2=1,j3=3,j4=4.則i1,i2有以下兩種可能：①i1=0,i2=2;②i1=1,i2=2.

當i1=0,i2=2時，因為序列s(n)的線性復雜度L(s(5))=2n-(2i1+2i2)，所以存在序列v={1100 1100 0000 0000 0000 0000 0000 0000}.

使得u+v={0011 1100 1111 0000 1111 0000 1111 0000}，并且序列s(5)的線性復雜度L(s(5))=L(u+v)=25-(20+21).此時序列s(5)改變4個元素且其線性復雜度出現第一次下降，且L(u)=L4(s(n))=25-(20+21+23+24)=5，根據序列的性質易知第二次下降點Lk(s(5))

其中，

t1={0011 1100 1111 0000 1111 0000 1111 0000}，

t2={1100 0011 0000 1111 1111 0000 1111 0000}，

t3={1001 0110 0101 1010 1111 0000 1111 0000}，

t4={1111 0000 0011 1100 1111 0000 1111 0000}，

t5={1011 0100 0111 1000 1111 0000 1111 0000}.

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

當i1=1,i2=2時，存在序列v={1010 1010 0000 0000 0000 0000 0000 0000}，使得u+v={0101 1010 1111 0000 1111 0000 1111 0000}，此時與上述情況類似，予以省略.

當i1?{j1,j2,j3,j4}時，有①i1=2,i2=3;②i1=2,i2=4，情況與i2?{j1,j2,j3,j4}類似，予以省略.

對于②i1=2,i2=5時，序列s(5)的線性復雜度L(s(5))=25-(22+25)，因為n=i2=5.根據方體理論，當i2=5時兩個非零元素的距離為25=32.因為序列的長度為32，所以兩個非零元素的最大距離為16，所以不存在i2=5這種情況.

綜上所述可知，假設不成立，則{i1,i2}∈{j1,j2,j3,j4}.

定理2設以2n為周期的二元序列s(n)，線性復雜度L(s(n))<2n，那么

(1)L(s(n))=L2(s(n))>L4(s(n)),L4(s(n))=L10(s(n))>L12(s(n))且僅當序列s(n)可以分解為若干方體c1，c2，c3,...,L(c1)>L(c2)>L(c3)>…>L(cn),其中c1是2方體，c2是4方體，且c1和c2中的非零元素存在重合4個、或重合3個、或重合2個、或重合1個、或不重合等5種情況.

(2)L(s(n))=L3(s(n))>L4(s(n)),L4(s(n))=L11(s(n))>L12(s(n))，當且僅當L(s(n))=2n-(2i1+2i2)，L4(s(n))=2n-(2j1+2j2+2j3+2j4)，0

證明(1)(必要性)假設序列s(n)是周期為2n的二元序列，且L(s(n))=2n-(2i1+2i2+…+2im).根據引理6可知，使得Lk(s(n))L4(s(n)).

當重合4個非零元素時，相當于序列s(n)由一個2方體c1和一個3方體c2構成，且c1和c2中的非零元素均不重合，顯然L(s(n))=L(c1).加入一個線性復雜度與c1相等的2方體(與s(n)中的非零元素無重合)，該2方體和c1構成一個3方體c1′，且c1′與c2構成一個4方體，序列s(n)發生第一次下降，L(s(n))=L(c1)>L4(s(n)).將c1，c2去除，此時序列發生第二次下降.

當重合3個非零元素時，c1剩余的一個非零元素記為x，將重合位置處的3個元素變為1，同時將x變為0，此時發生第一次下降，線性復雜度L(s(n))>L(c2)=L4(s(n)).設L(c2)=2n-(2j1+2j2+2j3+2j4)，向s(n)中加入3個非零元素，與x組成一個線性復雜度L(c1′)=2n-(2j3+2j4)的2方體，然后將c2余下的非零元素中的9個元素變為0，得到L(c2′)=2n-(2j3+2j4)，c1′與c2′組成一個線性復雜度為L12(s(n))=2n-(2j3+2j4+2j5))

當重復2個和1個非零元素時，情況與重合3個非零元素時類似，發生第二次下降時，對于重合2個非零元素的序列，此時加入6個非零元素與c1的非零元素組成3方體c1′，然后將c2中的6個非零元素變為0(共改變12個元素)，此時c1′與c2′組成4方體，但由于方體之間的距離更大，所以此時發生第二次下降.對于重合1個非零元素的情況，加入9個非零元素，并將c2中的3個非零元素變為0，情況與上述類似，此處不再詳細列出.

當c1，c2的非零元素不重合時，去除c1的四個非零元素后序列s(n)的線性復雜發生第一次下降，L(s(n))>L4(s(n))=L(c2).向序列s(n)中加入12個1，與c1構成一個4方體，記為c1′，c1′與c2構成一個5方體c2′，且有L(c2′)L12(s(n)).

(充分性)假設c1為2方體，c2為1方體，且非零元素不重合.此時去掉c1時，序列s(n)線性復雜度發生下降.同時去掉c1和c2，此時線性復雜度再次發生下降，即L6(s(n))

假設c1為2方體，c2為2方體，此種情況與上述類似，予以省略.

假設c1為2方體，c2為3方體.c1和c2的非零元素存在不重合，或重合1個，或重合2個等情況.當c1與c2的非零元素不重合時，如{0000 0000 0000 0000 0000 1111 1111 1111}，此時等價于c1為2方體，c2為4方體，且c1和c2的非零元素有4個重合.當c1和c2的非零元素有1個重合的時候，分別去掉c1和c1+c2的非零元素，則線性復雜度下降，即L10(s(n))

假設c1為2方體，c2為5方體.雖然c1和c2的非零元素存在不重合、或重合1個、或重合2個、或重合3個、或重合4個等情況.但是由于c2是5方體，所以發生第二次下降至少要改變28個非零元素才會發生第二次下降，即L28(s(n))

綜上所述，可以得到c1為2方體，c2為4方體時滿足上述要求.

定理3設s(n)是以2n為周期的二元序列，若L(s(n))>L4(s(n))>L12(s(n))，且有L(s(n))=2n-(2i1+2i2)，L4(s(n))=2n-(2j1+2j2+2j3+2j4)，0

證明下面的證明基于框架:T={t|L(t)=L}，E={e|WH(e)=12}，TE={t+e|t∈T,e∈E},其中t是線性復雜度為L(t)=L12(s(n))的序列，e是WH(e)=12的序列，且L4(s(n))=2n-(2j1+2j2+2j3+2j4).使用篩選法，從TE中篩選出L12(t+e)=L的序列t+e.

當L12(s(n))=2n-(2k1+2k2+…+2km)時，s(n)的12錯線性復雜度序列有2m=32個非零元素.關于Lk(t+u)

當L12(s(n))=2n-(2k1+2k2+2k3+2k4)時，下面用反證法，用實例證明{k1,k2,k3,k4}一定不包含{i1,i2}.令s(n)是25周期二元序列，L(s(n))=25-(20+21),則L12(s(n))≠25-(20+21+23+24).設L12(s(n))=25-(20+21+23+24)，根據框架TE={t+e|t∈T,e∈E}.其中T={t|L(t)=25-(20+21+23+24)}，E={e|WH(e)=12}，TE={t+e|t∈T,e∈E}，其中t是線性復雜度為25-(20+21+23+24)的序列，e是WH(e)=12的序列.通過篩選方法，從TE中篩選出L12(s(n))=25-(20+21+23+24)的序列t+e.現在研究t+u∈TE，且L12(s(n))<25-(20+21+23+24)的情況.此情況可等價轉化為檢查是否存在v∈E，使得L(u+v)=25-(20+21+23+24).

對任意u∈E，使得L4(u)=25-(20+21+22+23)，當u(5)={0000 0000 0000 0000 0000 1111 1111 1111}，v(5)={0000 1111 0000 1111 0000 0000 1111 0000}時,L(u+v)=25-(20+21+23+24)，故L12(s(n))<25-(20+21+23+24).因此{i1,i2}{k1,k2,k3,k4}.

當L12(s(n))=2n-(2k1+2k2+2k3)<2n-(2j1+2j2+2j3+2j4)時，使用反證法證明i1?{k1,k2,k3}.

L12(s(n))≠2n-(2k1+2k2+2k3)，其中i1?{k1,k2,k3}.

3結語

錯誤線性復雜度是度量一個序列穩定性的重要指標之一，關于錯誤線性復雜度從該思想提出后就受到了密碼學界的關注.本文結合k-錯線性復雜度、最小錯誤理論以及k-錯線性復雜度曲線等理論，研究周期為2n存在第二個下降點二進制序列s(n)的若干性質，其中序列s(n)在4錯時發生第一下降且12錯時發生第二次下降.經研究得出的性質，可以用于推導12錯線性復雜度的計數方法和結果，同時也能用于對于其它具有第二次下降點k-錯線性復雜度序列的研究.

[參考文獻]

[1]田金兵.偽隨機序列的相關特性和線性復雜度的研究[D].武漢:湖北大學,2007.

[2]T.Etzion,N.Kalouptsidis,N.Kolokotronis,et al.Properties of the error linear complexity spectrum[J].IEEE Trans.on Inform.Theory,2009,55(10):4681-4686.

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

[4]Rueppel R A.Analysis and Design of Stream Ciphers[M].Berlin:Spring-Verlag,1986.

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

[6]周建欽,上官成,趙澤茂.若干二元周期序列的緊錯線性復雜度[J].計算機工程與應用,2011,47(10):49-53.

[7]Zhou Jianqin.A counter example concerning the 3-error linear complexity of 2n-periodic binary sequences[J]. Designs codes and Cryptography,2012,64(3):285-286.

[8]Zhu, F X,Qi,W F.The 2-error linear complexity of 2n-periodic binary sequences with linear complexity 2n-1[J]. Journal of Electronics(China),2007,24(3):390-395.

[9]牛志華.周期序列線性復雜度及其穩定性分析[D].西安:西安電子科技大學,2005.

[10]Shannon C E.A mathematical Theory of Communication[J].Bell System Technical Journal,1948,27(7):637-657.

[11]Kenneth H.Rosen.初等數論及其應用[M].5版.夏鴻剛,譯,北京:機械工業出版社,2009:35-160.

[12]陳魯生,沈世鎰.現代密碼學[M].2版.北京:科學出版社,2008:133-549.

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

[14]張仕斌,萬武南,張金全,等.應用密碼學[M].西安:西安電子科技大學出版社,2009:43-136.

Periodic Binary Sequences with 12-error Linear Complexity As the Second Descent Point

TAO Tao, LV Jia-wei

(Computer Science and Technology School,Anhui University of Technology,Ma’anshan Anhui 243002,China)

Abstract:The linear complexity and the k-error linear complexity of the stream cipher are important indicators to measure the security of the key stream .In general, the linear complexity is proportional to the security of the key stream, but there is a situation of instability in the sequence of linear complexity. Therefore, the research on cryptography is a hot research topic with high linear complexity and k-error linear complexity. In order to research the sequence of stream cipher, based on the theory of critical error linear complexity spectrum, we derive the correlation property of periodic sequences with the given first descent point 4-error linear complexity and second descent point 12-error linear complexity.

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

[收稿日期]2016-03-02

[基金項目]國家自然科學基金“不可靠無線傳感器網絡中自適應稀疏壓縮采樣關鍵技術研究”(61402009)；賽爾網絡下一代互聯網技術創新項目“基于IPv6的校園路燈節能系統的研究”(NGII20150617)。

[作者簡介]陶陶(1977- )，男，副教授，碩士，從事物聯網技術、無線傳感網絡研究。

[通訊作者]呂家偉(1990- )，男，碩士研究生，從事密碼學與理論計算機科學研究。

[中圖分類號]TN918.1

[文獻標識碼]A

[文章編號]2095-7602(2016)06-0001-05