周期序列线性复杂度与k-错复杂度的数学期望 - 电子与信息学报200411.pdf

《周期序列线性复杂度与k-错复杂度的数学期望 - 电子与信息学报200411.pdf》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第26卷第11期电子与信息学报Vo1.26No.112004年11月JournalofElectronics&InformationTechnologyNov.2004周期序列线性复杂度与卜错复杂度的数学期望‘牛志华白恩健肖国镇(西安电子科技大学综合业务网国家重点实验室西安710071)摘要:密码学意义上强的序列不仅应该具有足够高的线性复杂度，而且当少量比特发生改变时不会引起线性复杂度的急剧下降，即具有高的k-错复杂度.该文以多项式的因式分解为主要工具研究了任意有限域GF(q)上，周期N与p互素以及N=Pv这两种情况下，计数函数.IVN,O(e)的值，

2、并给出了线性复杂度的数学期望EN,。的值以及k-错复杂度的数学期望EN,*的一个有用的下界，这里p是有限域GF(的的特征.关健词:流密码，周期序列，线性复杂度，k-错复杂度中图分类号:TN918.4文献标识码:A文章编号:1009-5896(2004)11-1787-05OntheExpectedValueoftheLinearComplexityandthek-ErrorLinearComplexityofPeriodicSequencesNiuZhi-huaBaiEn一ianXiaoGuo-zhen(NationalKeyLabofIntegrat

3、edServiceNetworks,XidianUniv.,Xi'an710071,China)AbstractCryptographicallystrongsequencesnotonlyshouldhavealargelinearcom-plexity,butalsonoasignificantdecreaseofthelinearcomplexitywhenafewtermsarechanged.Thisrequirementleadstotheconceptofthek-errorlinearcomplexityofperiodicsequen

4、ces.Inthefollowingtwocases:(1)gcd(N,p)=1;(2)N=p0,wherepdenotesthecharacteristicofthefinitefieldGF(q),thecountingfunctionJVN,o(c),i.e.,thenumberofN-periodicsequenceswithgivenlinearcomplexityc,isshowed,theexpectedvalueofthelinearcomplexityEN,oisdetermined,andausefullowerboundonthe

5、expectedvalueofthek-errorlinearcomplexityEN,kisestablished.KeywordsStreamcipher,Periodicsequences,Linearcomplexity,k-Errorlinearcomplex-ity1引言周期序列的线性复杂度是流密码强度的一个重要度量指标，序列(S)的线性复杂度定义为生成它的最小线性反馈移位寄存器的长度，记为LC(S)，密钥序列的线性复杂度必须足够大，因为只要知道连续2LC(S)个比特，就可以通过解线性方程组或借助BM算法将整个序列完全确定.但是，有的序列虽

6、然具有很高的线性复杂度但其线性复杂度却极不稳定，即当改变这些序列周期的一位或几位时，其线性复杂度发生很大的变化，这样的序列用来作为密钥序列是不安全的.因此，序列的线性复杂度的稳定性与序列的不可测性是密切相关的.我国学者早就注意到这个问题并率先创立了流密码的稳定性理论，并引入球体复杂度，重量复杂度等流密码稳定12003-05-15收到，2003-12-02改回国家自然科学基金项目(60073051)和国家自然科学基金重大项目(90104005)资助课题1788电子与信息学报第26卷性度量指标[Ill，国外学者Stamp和Martin也注意到这个间题，在文

7、献[2]中提出了类似球体复杂度的k-错复杂度的概念.设(S)是有限域GF(q)上周期为N的序列，当改变(S)的周期中至多k(0

8、3]将Stamp-Martin算法做了推广，给出了任意有限域GF(p哟上周期为尹的序列的k-错