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

第28卷第7期通信学报Vol.28 No.72007年7月Journal on CommunicationsJuly 2007钟控密钥流生成器及其密码性能马卫局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-06On a clock-controlled keystream generator and its cryptographic propertiesMA Wei-ju1, FENG Deng-guo1,2(1. State Key Lab of Information Security, Graduated School of the Chinese Academy of Sciences, Beijing 100049, China;2. Institute of Software, the Chinese Academy of Sciences, Beijing 100080, China)Abstract: A new clock-controlled keystream generator was proposed, which was composed of three shift registers: two clock-controlled linear feedback shift registers A, B, and one clock-controlling nonlinear feedback shift register C. Let l1, l2 and l3 denote the length of A, B and C, respectively. The clock-control information is from two bit strings of feedback shift register C, and the times A and B shift are according to the Hamming weights of the two strings, respectively. The period, the linear complexity and the k error linear complexity of the keystream generator are studied, and its security was analyzed.Key words: cryptography; keystream generator; clock-control; security25第7期马卫局等：钟控密钥流生成器及其密码性能471引言收稿日期：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的初态猜测是正确的，则编辑距离为零，如果猜测是错误的，则编辑距离为零的概率非常小，是输出串长度幂指数分之一，这种算法的恢复移位寄存器A和B的计算复杂度为，恢复移位寄存器C的初态的计算复杂度为。在文献8中，Golic和Menicocci对基于编辑距离的相关攻击进行了改进，可以单独把A或B的初态求出，算法的计算复杂度为，恢复移位寄存器C的初态的计算复杂度为。为了获得更高的安全性，本文第2节提出一种新的钟控密钥流生成器。在第3节中讨论了它的周期、线性复杂度和错线性复杂度。第4节对这种生成器的安全性进行了分析。第5节给出结束语。2生成器的提出对于一个长度为的移位寄存器R，设其反馈多项式为f，第i个状态为，,则其第个状态为 。交错停走生成器由三个移位寄存器组成：两个被钟控的移位寄存器A和B，一个提供钟控信息的移位寄存器C。设A、B和C的长度分别为l1、l2和l3，它们的初始状态分别为，和，反馈多项式分别为、和。交错停走生成器的密钥流产生算法如下：对于。1）钟控移位寄存器C一次，并产生；2）如果，则钟控A一次，并产生；如果，则钟控B一次，并产生； 3）令。其中，。作为密钥流输出。对于，和为互反多项式的情形，丁存生在文献9中给出了输出序列的线性复杂度和周期，并探讨了密钥流的稳定性。当C为非线性反馈移位寄存器，并产生M序列（最大长度de Bruijn序列）时，Gunther在文献4中研究了密钥流的周期、线性复杂度和统计特性。虽然交错停走生成器线性复杂度、周期和统计特性都比较理想，但它的安全性却并不理想。为了获得更高的安全性，本文提出了一种新的钟控密钥流生成器案，称之为“重量钟控模2加生成器”。这种生成器是通过对交错停走改进得到的，它仍然具有两个被钟控的移位寄存器A和B，以及一个提供钟控信息的移位寄存器C，其中A和B产生的是m序列，C产生的是M序列。它的基本结构和交错停走生成器相同，只是钟控的模式改变了。对于，设，记。简单起见，记。对于移位寄存器C的第个状态，我们从中分别选取长度为和两组比特串和其中， 。生成器的密钥流产生算法如下：对于。1）钟控移位寄存器C一次；2）钟控移位寄存器A次，并产生；钟控移位寄存器B次，并产生； 3）令。其中，。作为密钥流输出。3密钥流的周期和线性复杂度引理1在移位寄存器C的一个周期内，移位寄存器A和B被钟控的次数分别为和。证明序列和为m序列，故周期分别为和。序列是M序列，故其周期为。对于固定的，取定移位寄存器C的个位置。根据M序列的性质， 移位寄存器C的状态转移图是一个圈，所有的值都在这个圈上。这样，在一个移位寄存器C的一个周期内，的汉明重量为的移位寄存器C的状态数为。因此同样的道理，得到。证毕。密钥流序列是序列与的和序列，在考察序列的周期和线性复杂度之前，先来考察序列与的周期和线性复杂度。引理2如果，则序列的周期为。证明当移位寄存器A和C的状态分别回到初态和时，会出现重复。移位寄存器C在每时钟脉冲后会回到初态，所以当C移位了M个周期后，A就移位了次。如果有整数M和N满足，则M2k个时钟后，移位寄存器A和C都回到初态。的最小值对应着的最小周期。因为，所以有，从而的最小值为。这样就得到的周期为。证毕。引理3如果，则序列的周期为。证明证明方法和引理2相同。证毕。引理4如果，则序列的线性复杂度满足。证明从某个固定的位置开始，对进行采样，即每比特取1比特构成一个子序列，这等价于对进行采样。所有的采样序列具有相同的反馈多项式，其根为的根的次幂。这样，就等价一个由个子序列的组成序列。设这个子序列为。令，设表示序列的右移算子，那么将多项式算子作用在上得因此的一个反馈多项式为。可知线性复杂度上界为。设的极小多项式为。序列满足，其中为右移算子，(0)表示全零序列。设f1的一个根为，它是GF(2l1)上的一个本原元。当时，也是GF(2l1)一个本原元。而为的一个根，故是一个次数为的不可约多项式，且。所以的极小多项式形如，其中。假设，则。这样就有这样的周期至多为，与引理2矛盾。因此，的线性复杂度大于。证毕。引理5如果，则序列的线性复杂度满足。证明和引理4的证明方法相同，等价于一个由个子序列的组成阵列。设每个子序列具有相同的极小多项式，其中次数为，它的根为的根的次幂。的极小多项式形如，其中。因此，。证毕。定理1如果，且，则重量钟控模2加生成器的密钥流有如下性质：1)周期为。2)线性复杂度满足 。证明1）根据引理4和引理5，可知和的极小多项式分别为和，其中和为不可约多项式，。从而设和的生成函数的既约有理分式表示分别为和。密钥流的生成函数的既约有理分式表示为易知因此，的极小多项式为，的周期注意到上式中的第4个等号之所以成立，是因为。3）因为的极小多项式为，所以的线性复杂度为的次数，即。再根据引理4和引理5，可得证毕。定义1设是上周期为的序列，定义的错线性复杂度为其中表示序列的线性复杂度，表示序列的周期，表示序列的第一个周期段。引理69设和是上周期为的序列，和分别为这两个序列的既约有理分式表示。那么定理2如果，且，则重量钟控模2加生成器的密钥流的错线性复杂度证明设是GF(2)上的任意多项式，首先，证明注意到而且整除，因此可知整除。从定理1的证明过程中，可知密钥流的生成函数的既约有理分式表示为再设为序列的生成函数的既约有理分式表示，其中是上与有相同周期且满足的序列。由引理5，有由于的周期为，设，则中有一个长度至少为的零游程。因此，的线性复杂度不小于。由此可知从而由定理1可得证毕。4安全性分析一个安全的流密码应该可以抵抗各种已知明文攻击，即敌手在截取任意长的密钥流比特串的情况下仍然不能恢复密钥。在基于移位寄存器的流密码算法中，我们一般把移位寄存器的初始状态作为密钥。对于钟控密钥流生成器，最基本的攻击算法就是分别征服攻击算法，即对钟控的情况进行穷举，从而恢复被钟控移位寄存器的初态。例如对于交错停走生成器，Gunther在文献4中指出当且仅当钟控移位寄存器C的初态猜测正确的情况下，从密钥流序列的导出序列可以得到规则钟控的移位寄存器A和B的导出序列，从而可以求出A和B的初态。穷举C的初态的计算复杂度为。在已知钟控信息的情况下，用高斯算法解线性方程的方法来求出A和B的初态，计算复杂度为。所以这种算法的计算复杂度为。在重量钟控模2加生成器算法的实际应用中，钟控模式是秘密的，即提供钟控信息的两组比特串和的长度和，以及下标和是不公开的，其中，。把和gcd 的情况排除，我们来看重量钟控模2加生成器共有多少种不同的钟控模式。令， ，设共有种钟控模式，则容易验证当时，假设敌手已知3个移位寄存器的反馈多项式和任意长的密钥流比特串，未知的是钟控模式和3个移位寄存器的初始状态。如果敌手想完全知道重量钟控模2加生成器的钟控信息，他就要同时知道、以及移位寄存器C的初态。这样，穷举算法的计算复杂度为，分别征服攻击的计算复杂度为。当时，算法的计算复杂度大于穷举3个移位寄存器初态的计算复杂度。在实际应用中，我们一般选择。Golic和Menicocci文献7，8中提出了对交错停走生成器的基于编辑距离的快速相关攻击算法。该算法研究了输入序列的1次导出序列与输出序列的1次导出序列之间的关系，给出了对于给定一段输出序列的1次导出序列，规则钟控的LFSR输入序列的1次导出序列每个比特的后验概率。这些后验概率明显地与1/2不同，因此用迭代译码算法即可恢复移位寄存器A和B的初态，然后即可用很低地计算复杂度恢复C的初态。对于重量钟控模2加生成器，输入的LFSR移位的次数为一个未知的比特串的重量，不再是停走模式，因此输入序列的1次导出序列与输出序列的1次导出序列之间不存在必然联系，基于编辑距离的快速相关攻击也是无效的。因为作为输入的移位寄存器A和B是不规则钟控的，且穷举钟控信息的算法计算复杂度为。当足够大时，如，时，钟控信息无法用猜测的方法获取。这样，关于移位寄存器A和B的初态以及密钥流比特的含错线性方程或代数方程无法建立，所以如文献10中的快速相关攻击和文献2中的代数攻击也是无效的。对于时间存储权衡攻击11，必须要知道确切的加密算法。在重量钟控模2加生成器中，钟控模式决定着加密算法，穷举钟控模式的计算复杂度为。在一种钟控模式下，状态空间的范数为。设攻击者可以利用的存储空间为，则整个攻击算法的计算复杂度为。只要3个移位寄存器有一定的长度，这种攻击算法也是无效的。例如当3个移位寄存器长度都为80左右的整数时，要么攻击者所需要的存储空间过大，要么计算复杂度过大，算法无法实现。5结束语本文提出了一种钟控密钥流生成器，它由3个移位寄存器组成：两个被钟控的线性反馈移位寄存器A和B，一个提供钟控信息的非线性反馈移位寄存器C。设A，B和C的长度分别为l1，l2和l3。这种生成器是通过对交错停走生成器改进得到的。移位寄存器A和B的钟控信息由从移位寄存器C选取的两个比特串提供，移位的次数分别是两个比特串的重量。当移位寄存器A和B产生m序列且移位寄存器C产生M序列时，选取适当长度的提供钟控信息的比特串，这种密钥流生成器的周期为，线性复杂度L的范围为，错线性复杂度的下界为。分析了密钥流生成器的安全性，认为它可以抵抗现存的攻击算法。参考文献: 1MEIER W, STAFFELBACH O. Fast correlation attacks on certain stream ciphersJ. J Cryptology, 1989, 1(3):159-176.2COURTOIS N T, MEIER W. Algebraic attacks on stream ciphers with linear feedbackA. Advances in Cryptology -EUROCRYPT2003C. Berlin: Springer-Verlag, 2003. 345-359.3BEHTH T, PIPER F. The stop-and-go generatorA. Advances in Cryptology-EUROCRYPT84C. Berlin: Springer-Verlag，1985.89-92.4GUNTHER C G. Alternating step generators controlled by de Bruijn sequencesA. Advances in Cryptology- EUROCRYPT87C.Berlin: Springer-Verlag, 1988. 5-14.5VOGEL R. On the linear complexity of casecaded sequencesA. Advances in Cryptology-EUROCRYPT84C. Berlin: Springer-Verlag, 1985. 92-99.6MEIER W, STAFFELBACH O. The self-shrinking generatorA. Advances in Cryptology-EUROCRYPT94C. Berlin: Springer-Verlag, 1995. 205-214.7GOLIC J D, MENICOCCI R. Edit distance correlation attack on the alternating step generatorA. Advances in Cryptology-CRYPTO 97C. Berlin: Sprin