乘加型钟控组合生成器的符合率问题.doc

第3A期那键等：乘加型钟控组合生成器的符合率问题119乘加型钟控组合生成器的符合率问题那键，刘文芬（信息工程大学 信息工程学院，河南 郑州 450002）摘 要：讨论了乘加型钟控组合生成器输出序列与目标移位寄存器（LFSR3）单比特相等的概率，结果为0.5；给出了计算乘积生成器联合分布的递归算法，在此基础上，给出了快速计算乘加型钟控组合生成器的输出序列段与一条目标LFSR序列段对应比特相符合的联合概率分布的算法，并给出部分实验结果。关键词：停走生成器；组合生成器；概率模型；符合率中图分类号：TN918 文献标识码：A 文章编号：1000-436X(2008)3A-0114-05Coincidence of the multiply and xor clock controlled combinerNA Jian, LIU Wen-fen (College of Information Engineering, Information Engineering University, Zhengzhou 450002, China)Abstract: The multiplied and xored clock controlled combiner was studied. It was proved first that the coincidence between the single output bit and the single target LFSR bit is 0.5 respectively. Then a recursive and fast algorithm to compute the joint distribution of the coincidence between the output bits of the multiplied combiner was proposed. And then, a fast algorithm to compute the coincidence between a section of output bits and the respective section of target bits of the multiplied and xored combiner was given.Key words: stop and go generator; combiner; probability model; coincidence1 引言组合生成器是一类重要的密钥流生成器，传统的组合生成器，通过非线性布尔函数将多个线性移位寄存器（LFSR）产生的序列组合后再输出。对于此类生成器，进行相关攻击1和快速相关攻击2较为有效。停走生成器（stop-and-go）3是1984年由T. Beth和F. Piper在欧洲密码会上提出的，是一种基于LFSR的钟控生成器。由于这种生成器产生的伪随机序列具有较好的性质，同时在硬件上较容易实现，因而受到广泛关注。将停走生成器应用到组合生成器的设计中，使得组合生成器的输出序列具有大的周期性和高的线性复杂度4,5等较好的密码学性质。文献6指出，钟控组合生成器是最有前途的密钥流生成器之一，其输出序列与目标LFSR序列之间符合率的计算是值得研究的问题。文献7给出了由3个钟控停走生成器组成的乘加型钟控组合生成器的概率模型，其函数形式为 ，考察了输出序列分布的均匀性，有限维联合分布的马尔可夫性及大数性质。本文在文献7建立的概率模型的基础上，研究乘加型钟控组合生成器的输出序列与目标LFSR序列的符合率，给出了计算输出序列段与目标LFSR序列段对应比特相等的联合概率分布的快速算法，在一定程度上解决了文献6提出的问题。收稿日期：2008-01-10本文第2节介绍停走生成器的概率模型，第3节对生成器输出序列与目标LFSR序列的符合率的计算进行了讨论，第4节为结束语。2 停走生成器的概率模型文献7给出了钟控停走生成器的概率模型：设，是定义同一概率空间上取值为的6条独立随机变量序列，满足还假设和 ，这6条序列之间也是相互独立的。又记, ，则3个钟控停走生成器的3条输出序列； 都是均匀分布的0 ,1随机变量序列，都是严平稳和遍历的齐次马尔可夫链，易知这3条序列之间也是相互独立的。3 乘加型钟控组合生成器的符合率本节考察乘加型钟控组合生成器的符合率问题，注意，n为非负整数。实际上，此种组合生成器是乘积型生成器与停走生成器的模2加生成器。后文中，将乘加型钟控组合生成器简称为乘加型生成器。首先给出计算乘积型生成器输出序列联合分布的快速算法。引理17 若乘积生成器的输出序列为，则联合分布其中，（i为非负整数），表示停走生成器输出序列的一步转移概率； （i为非负整数），表示停走生成输出序列的一步转移概率。这里，且两条停走生成器序列的初始分布分别为，。引理1给出了的计算乘积生成器输出序列联合分布的公式，但计算复杂度较高，比如计算的复杂度约为，找到一种计算该联合分布的快速算法是必要的。引理28 设和 为2条独立的齐次马氏链，其状态空间分别为和，一步转移概率矩阵分别为和。则序列为一齐次马氏链，状态空间为，一步转移概率矩阵为，其中为矩阵的积，即。定理1 乘积生成器的输入向量序列是一条严平稳的齐次马尔可夫链，其一步转移概率矩阵为其初始分布为证明 由引理1知，（）是初始分布为均匀分布的严平稳的齐次马氏链，且一步转移概率矩阵均为再结合引理2的结论即可证明。由定理1可知，乘积生成器的输入向量构成马氏链，我们利用递推的方法计算乘积生成器输出序列的联合分布。记其中，为输入向量取值空间中的元素，即 ，。定理2 按如上定义的满足如下递推关系：1) 如果，2) 如果，则其中，f为乘积组合函数。证明 1) 如果时，则，此时必有 。2) 当时，根据 的马氏性，利用全概率公式，根据定理2给出的递推关系，并利用定理1给出的一步转移概率矩阵，就可以递归地计算乘积生成器输出序列的联合分布 。下面给出计算该联合分布的递归算法。算法1 计算联合分布 的递归算法。输入：所求联合概率分布的维数n，初始分布对，其中为示性函数，。1) 对所有的，递推计算2) 将第一步重复次。输出：联合分布 。该递归算法的使用使得计算联合分布的复杂度降低为，复杂度比引理1的方法有显著降低。在给出计算乘积生成器输出的联合分布的基础上，进一步讨论乘加型生成器的输出与目标LFSR序列的符合率。引理37 停走生成器序列与目标LFSR序列的符合率为；当， 。定理3 乘加型生成器的输出序列 与目标LFSR序列单比特的符合率为1) 当时,2) ，当时，证明 1) 当时，且时，利用，与的独立性及分布的均匀性，有：当时， 当较大时，第3个LFSR的输出序列与组合生成器的输出序列对应比特的符合率接近。上述结论说明当较大时，利用单个比特间的符合率从输出序列恢复目标LFSR序列是困难的。下面讨论输出序列段与目标LFSR序列段对应比特相等的联合分布。当时，结合引理1及引理3那么 由此式可以递推求得联合分布。算法2 计算联合分布 的递归算法。输入：所求联合概率分布的维数n，初始分布。1) 利用算法1计算联合分布2) 根据递推式计算并返回1。3) 1)、2)步重复进行次。输出：联合分布 。在表1中，给出部分mn以及an的取值表1mn以及an的取值Nmnan10.1330.50820.0570.31130.3960.18040.3890.10250.2690.05560.2520.02970.2170.01680.1870.00890.1610.004图1给出随着的变化，乘加型生成器输出序列段与目标LFSR序列段对应比特相符合的联合分布率an与平衡状态分布的变化示意图，其中横轴表示n的取值，实线表示an的取值，虚线表示平衡状态分布的取值。为更加清晰地反映出乘加型生成器的输出序列段与目标LFSR序列段对应比特相符合的联合分布率与平衡状态分布率的差异，给出图2，其中横轴表示的取值，实线表示的取值，虚线表示的取值。图1 an与平衡状态分布随n的变化图2 与随n的变化定理3说明，乘加型生成器的有较好的随机性，由已知的输出序列恢复目标LFSR的单比特比较困难，但是利用算法2计算得到的表1说明了连续输出序列段中包含了第3个目标LFSR较多的信息，即两者有较大的符合率。对生成器进行分别征服攻击，只需要穷举目标LFSR的初态，如果对应序列与生成器输出序列的符合率与算法2的计算结果相同，则我们找到了该LFSR的正确初态。4 结束语本文对乘加型钟控组合生成器的输出序列与输入序列的符合率问题进行了研究，在给出计算乘积型钟控组合生成器输出序列联合分布的快速算法的基础上，给出乘加型生成器输出序列段与目标LFSR序列段符合率的递推算法，利用该算法可以快速计算输出序列段与目标LFSR序列段的符合率，部分解决了文献6提出的问题。实验结果表明，乘加型钟控组合生成器的输出序列段包含目标LFSR较多信息，可利用这一点对乘加型生成器进行分别征服攻击。参考文献：1CANTEAUT A, TRABBIA M. Improved fast correlation attacks using parity-check equations of weight 4 and 5A. Advances in Cryptology EUROCRYPT2002, LNCS vol. 2332C. Springer-Verlag, 2002. 209-211.2JOHANSSON T, JONSSON F. Fast correlation attacks on stream ciphers via convolutional codesA. Advances in Cryptology EUROCRYPT99C. Springer-Verlag, 1999. 347-362.3BETH T, PIPER F. The stop and go generatorA. Advances in CryptologyEUROCRYPT84, LNCS vol. 209C. Springer-Verlag, 1984. 88-92.4GOLLMAN D, CHAMBERS W. Clock-controlled shift registers: A reviewA. IEEE J select Aeras CommunicationC. 1989. 525-533.5JOHANSSON T. Reduced complexity correlation property attacks on two clocked-controlled generatorsA. Advances in CryptologyAISACRYPT98, LNCS. vol. 1514C. Springer-Verlag, 1998. 342-357.6丁存生, 肖国镇. 流密码学及其应用M. 北京: 国防工业出版社, 1994: 181-202.DING C S, XIAO G Z. Stream Cipher and its ApplicationsM. Beijing: National Defense Industrial Press, 1994.189-199.7李世取, 黄晓英, 刘文芬等. 密码学中的有关概率模型M. 北京: 电子工业出版社, 2005.138-272.LI S Q, HUANG X Y, LIU W F, et al. On Some Probabilistic Model in CrptographyM. Beijing: Publishing House