具有第二下降点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