钟控密钥流生成器及其密码性能.doc

第28卷第7期 通信学报 Vol.28No.7
2007年7月 JournalonCommunications July2007
钟控密钥流生成器及其密码性能
马卫局1,冯登国1,2
(1.中国科学院研究生院信息安全国家重点实验室,北京100049；2.中国科学院软件研究所,北京100080)

摘要：提出了一种新的钟控密钥流生成器，由3个移位寄存器组成:两个被钟控的线性反馈移位寄存器A和B，一个提供钟控信息的非线性反馈移位寄存器C。设A、B和C的长度分别为l1、l2和l3。移位寄存器A和B的钟控信息由从移位寄存器C选取的两个比特串提供，移位的次数分别是两个比特串的汉明重量。研究了该生成器的周期、线性复杂度和k错线性复杂度，分析了这种密钥流生成器的安全性。
关键词：密码学；密钥流生成器；钟控；安全性
中图分类号：TN918.1 文献标识码：A 文章编号：1000-436X(2007)07-0042-06
Onaclock-controlledkeystreamgeneratoranditscryptographicproperties
MAWei-ju1,FENGDeng-guo1,2
(1.StateKeyLabofInformationSecurity,GraduatedSchooloftheChineseAcademyofSciences,Beijing100049,China;
2.InstituteofSoftware,theChineseAcademyofSciences,Beijing100080,China)

Abstract:Anewclock-controlledkeystreamgeneratorwasproposed,whichwascomposedofthreeshiftregisters:twoclock-controlledlinearfeedbackshiftregistersA,B,andoneclock-controllingnonlinearfeedbackshiftregisterC.Letl1,l2andl3denotethelengthofA,BandC,respectively.Theclock-controlinformationisfromtwobitstringsoffeedbackshiftregisterC,andthetimesAandBshiftareaccordingtotheHammingweightsofthetwostrings,respectively.Theperiod,thelinearcomplexityandthekerrorlinearcomplexityofthekeystreamgeneratorarestudied,anditssecuritywasanalyzed.
Keywords:cryptography;keystreamgenerator;clock-control;security

·· 通信学报 第28卷
第7期 马卫局等：钟控密钥流生成器及其密码性能 ··

1引言收稿日期：2006-06-08；修回日期：2007-05-30

线性反馈移位寄存器（LFSR）生成的序列伪随机性好且容易实现，所以被广泛应用于构造密钥流生成器。但由于LFSR仅具有线性结构，不能抵抗B-M算法等序列综合算法的攻击，不可以直接用作密钥流生成器。引入非线性因素的方法有两种:一是通过非线性函数对LFSR序列进行组合，一是通过对LFSR进行不规则钟控。因为受到快速相关攻击[1]和代数攻击[2]的威胁，基于LFSR的非线性组合生成器和非线性滤波生成器逐渐被淘汰，所以不规则钟控的LFSR近期受到了一定的关注。到目前为止，已有很多种钟控密钥流生成器被提出和研究，例如停走生成器[3]、交错停走生成器[4]、级联钟控生成器[5]和自收缩生成器[6]等。
交错停走生成器由3个移位寄存器A、B和C组成。设它们的长度分别为l1、l2和l3。A和B被C钟控。当C的输出为1时，钟控A一次，B不变；当C的输出为0时，钟控B一次，A不变。不规则钟控的A和B的输出模2加作为密钥流比特。虽然交错停走生成器线性复杂度、周期和统计特性都比较理想，但它的安全性却并不理想。Gunther在文献[4]中指出当且仅当钟控移位寄存器C的状态猜测正确的情况下，从密钥流序列的导出序列可以得到规则钟控的移位寄存器A和B的导出序列，从而可以求出A和B的初态，这个算法的计算复杂度为。Golic和Menicocci在文献[7]中提出了一种基于编辑距离的快速相关攻击算法，如果对移位寄存器A和B的初态猜测是正确的，则编辑距离为零，如果猜测是错误的，则编辑距离为零的概率非常小，是输出串长度幂指数分之一