陶　陶，呂家偉

(安徽工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，安徽馬鞍山 243002)

?

具有第二下降點(diǎn)12錯線性復(fù)雜度的周期序列

陶陶，呂家偉

(安徽工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，安徽馬鞍山 243002)

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

[關(guān)鍵詞]周期序列；線性復(fù)雜度；篩選；方體；k-錯線性復(fù)雜度

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

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

1預(yù)備知識與引理

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

1.1相關(guān)定義和引理

下面介紹方體理論及其相關(guān)性質(zhì).

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

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

1.2方體理論的相關(guān)性質(zhì)

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

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

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

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

1.3關(guān)于篩選法的相關(guān)概念

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

對于周期為2n的二元序列s，Lk(s)=c，e是漢明重量為k的序列，假設(shè)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是線性復(fù)雜度為c的序列.使用篩選法，目標(biāo)是從TE中篩選出Lk(t+e)=c的序列t+e.

對于給定線性復(fù)雜度c，求滿足Lk(t+e)=c的序列t+e，存在兩種情況：一種是t+u∈TE，但Lk(t+u)

2具有第二下降點(diǎn)12錯的周期序列的相關(guān)性質(zhì)

首先分析k-線性復(fù)雜度的第一下降點(diǎn)和第二下降點(diǎn)的關(guān)系，推導(dǎo)出其滿足下降點(diǎn)序列的相關(guān)定理并加以證明.

定理1設(shè)以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}.

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

對于(1)，此處設(shè)i2?{j1,j2,j3,j4}，存在25周期二元序列s(5)，序列s(5)改變4個元素后得到序列u={1111 0000 1111 0000 1111 0000 1111 0000},此時序列u的線性復(fù)雜度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.

當(dāng)i1=0,i2=2時，因?yàn)樾蛄衧(n)的線性復(fù)雜度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)的線性復(fù)雜度L(s(5))=L(u+v)=25-(20+21).此時序列s(5)改變4個元素且其線性復(fù)雜度出現(xiàn)第一次下降，且L(u)=L4(s(n))=25-(20+21+23+24)=5，根據(jù)序列的性質(zhì)易知第二次下降點(diǎn)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}.

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

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

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

對于②i1=2,i2=5時，序列s(5)的線性復(fù)雜度L(s(5))=25-(22+25)，因?yàn)閚=i2=5.根據(jù)方體理論，當(dāng)i2=5時兩個非零元素的距離為25=32.因?yàn)樾蛄械拈L度為32，所以兩個非零元素的最大距離為16，所以不存在i2=5這種情況.

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

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

(1)L(s(n))=L2(s(n))>L4(s(n)),L4(s(n))=L10(s(n))>L12(s(n))且僅當(dāng)序列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))，當(dāng)且僅當(dāng)L(s(n))=2n-(2i1+2i2)，L4(s(n))=2n-(2j1+2j2+2j3+2j4)，0

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

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

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

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

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

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

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

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

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

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

定理3設(shè)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是線性復(fù)雜度為L(t)=L12(s(n))的序列，e是WH(e)=12的序列，且L4(s(n))=2n-(2j1+2j2+2j3+2j4).使用篩選法，從TE中篩選出L12(t+e)=L的序列t+e.

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

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

對任意u∈E，使得L4(u)=25-(20+21+22+23)，當(dāng)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).因此{(lán)i1,i2}{k1,k2,k3,k4}.

當(dāng)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結(jié)語

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

[參考文獻(xiàn)]

[1]田金兵.偽隨機(jī)序列的相關(guān)特性和線性復(fù)雜度的研究[D].武漢:湖北大學(xué),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]周建欽,戴小平,王小軍.具有穩(wěn)定k錯線性復(fù)雜度的周期序列[J].通信學(xué)報(bào),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]周建欽,上官成,趙澤茂.若干二元周期序列的緊錯線性復(fù)雜度[J].計(jì)算機(jī)工程與應(yīng)用,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]牛志華.周期序列線性復(fù)雜度及其穩(wěn)定性分析[D].西安:西安電子科技大學(xué),2005.

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

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

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

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

[14]張仕斌,萬武南,張金全,等.應(yīng)用密碼學(xué)[M].西安:西安電子科技大學(xué)出版社,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

[基金項(xiàng)目]國家自然科學(xué)基金“不可靠無線傳感器網(wǎng)絡(luò)中自適應(yīng)稀疏壓縮采樣關(guān)鍵技術(shù)研究”(61402009)；賽爾網(wǎng)絡(luò)下一代互聯(lián)網(wǎng)技術(shù)創(chuàng)新項(xiàng)目“基于IPv6的校園路燈節(jié)能系統(tǒng)的研究”(NGII20150617)。

[作者簡介]陶陶(1977- )，男，副教授，碩士，從事物聯(lián)網(wǎng)技術(shù)、無線傳感網(wǎng)絡(luò)研究。

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

[中圖分類號]TN918.1

[文獻(xiàn)標(biāo)識碼]A

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