摘要
在信息化的今天,随着信息技术和网络技术快速的发展和广泛的应用,越来越多的信息通过网络进行传输。与此同时,计算机网络所具有的开放性和共享性使得信息的安全性也逐渐成为人们日益关注的问题。密码学的理论与技术也渐渐成为信息科学与技术中的一个非常重要的研究领域。可以说,社会的信息化程度越高,商业越发达,信息安全就显得越来越重要,密码学的应用就越来越广泛。流密码是现代密码学中的一个重要分支,并且随着反馈移位寄存器理论的快速发展,加上有效的数学工具作为辅助,使得流密码理论得到了前所未有过的发展。因此,作为密码安全强度重要指标的线性复杂度与k-错复杂度,受到越来越多的关注。它的核心思想就是研究如何利用最少级数的反馈移位寄存器,生成所需要的密钥序列或生成与所需要的密钥序列非常近似的序列。本文主要研究流密码强度的重要度量指标—周期、线性复杂度、k-错线性复杂度和m-紧错线性复杂度等,得到如下主要结果:
1.提出m-紧错线性复杂度的概念。它综合了线性复杂度,k-错线性复杂度,k-错线性复杂度曲线和最小错误(?)ninerror(S)的概念。m-紧错线性复杂度是一个二元组(k_m, LC_m)。序列S的k-错线性复杂度曲线的第m个跃变点对应的k_m值和对应k_m错线性复杂度LC_m称为m-紧错线性复杂度。
2.在现有的周期为2n的二元序列的k-错线性复杂度的算法基础上求出它的紧错线性复杂度的快速算法,其基本思想是从0错线性复杂度开始计算,并在每次求k-错线性复杂度的同时,计算使序列线性复杂度再次下降最少需要改变原始序列的元素个数Tmin并通过改变k的值来降低序列的线性复杂度。
3.在GG(pm)上周期为pn序列的k-错线性复杂度的算法基础上求出它的紧错线性复杂度,其基本思想同上。
4.在周期为2npm二元序列的线性复杂度的快速算法的基础上求出周期为2npm用二元序列的紧错线性复杂度。由于魏-肖-陈算法不能像Games-Chan算法一样,扩展成为求k-错线性复杂度的算法,所以其基本思想和2、3中的思路不同。它的主要思路是:在求线性复杂度的算法每次增加线性复杂度之前,计算取消这次增加线性复杂度所需改变原始序列的最小比特数Tmin。对Tmin中间较小的值,由小到大依次改变原始序列的Tmin个比特(即叠加一个非零元素个数为Tmin的误差向量),可得1紧错线性复杂度。对于m>1,取Tmin中间较小且非零的一个或多个值,由小到大依次改变原始序列,使得相应位置线性复杂度没有增加,从而得m-紧错线性复杂度。
With the rapid development and wide application of information and network, more and more information has been transmitted through the network. Meanwhile, because of the openness and sharing of computer networks, information security has gained more and more concerns. The theory and technology of cryptography has become one of the most important research fields of information science and technology. It should be said that, the more information and its advanced commercialization, the more important information security and the more extensive application of cryptography. The stream cipher is one of the important branches of modern cryptography. The development of feedback shift register theory, together with the effective mathematical tools, has brought great progress of stream cipher theory. Therefore, as the important indexes of stream ciphers, linear complexity and k-error linear complexity have drawn more and more attention. The core idea of stream ciphers is how to use the shortest series of feedback shift register, to generate the needed key sequences or generate the approximate sequences of the needed key sequences. This dissertation mainly studies important measure indexes of stream ciphers which are based on feedback shift register, such as linear complexity, k-error linear complexity and m-tight error linear complexity. The main results are the following several respects:
1. Based on the earlier notions of linear complexity, k-error linear complexity, k-error linear complexity profile and minerror, the concept of m-tight error linear complexity is presented to study the stability of the linear complexity of sequences. The m-tight error linear complexity of sequence S is defined as a two tuple (km, LCm), which is the mth jump point of the k-error linear complexity profile of sequence S.
2. Based on the algorithm for determining the k-error linear complexity of a binary sequence with period 2n, the algorithm for determing the tight error linear complexity of it is presented. The main idea is calculating 0 error linear complexity at the beganing, and demanding k-error linear complexity at the same time, computing the smallest bits of original sequence Tmin when cancel this addition of linear complexity before every addition of linear complexity for the algorithm of linear complexity, and reduce the linear complexity of sequences through change the value of k.
3. Based on the algorithm for determining the k-error linear complexity of a binary sequence with period pn, the algorithm for determing the tight error linear complexity of it is presented. And the main idea is like 2.
4. Based on the algorithm for determining the linear complexity of a binary sequence with period 2npm, the algorithm for determing the tight error linear complexity of it is presented. Since that Wei-Xiao-Chen algorithm can not be generalized to the algorithm of k-error linear compliexity like Games-Chan algorithm, so the main idea is different from above.The main idea is:before every addition of linear complexity for the algorithm of linear complexity, computing the smallest bits of original sequence Tmin that can cancel this addition of linear complexity. To the value of smaller and nonzero among Tmin, change Tmin bits from small to big of original sequences (that is stack a nonzero element with Tmin vectors), then l-error linear complexity may obtained. For m>1, we take one or more values of the smaller and nonzero values among Tmin, change the original sequence from small to big to cancel addition of corresponding positions of linear complexity, then we get m-tight error linear complexity. IV
引文
[1]Ding C, Xiao G and Shan W. The stability theory of stream ciphers[M]. LNCS 561. Berlin: Springer-Verlag,1991:85-88.
[2]Blackburn S R. Fast rational interpolation, Reed-Solomon decoding and the linear complexity profiles of sequences[J]. IEEE Transactions on Information Theory,1997,43:537-548.
[3]Massey J L. Shift Register Synthesis and BCH Decoding[J]. IEEE Transactions on Information Theory,1969,15(1):122-127.
[4]Games R A and Chan AH. A fast algorithm for determining the complexity of a binary sequence with period 2n[J]. IEEE Transactions on Information Theory,1983,29(1): 144-146.
[5]Stamp M and Martin C F. An algorithm for the k-error linear complexity of binary sequences with period 2n[J]. IEEE Transactions on Information Theory,1993,39(4):1398-1401.
[6]Kaida T, Uehara S, Imamura K. An algorithm for the k-error linear complexity of sequences over GF(pm) with period pn, p a prime[J]. Information and Computation,1999,151(1): 134-147.
[7]Kolokotronis N, Rizomiliotis P and Kalouptsidis N. Minimum linear span approximation of binary sequences [J]. IEEE Transactions on Information Theory,2002,48:2758-2764.
[8]Meidl W. How many bits have to be changed to decrease the linear complexity?[J]. Des. Codes Cryptogr.,2004,33:109-122.
[9]Meidl W, Niederreiter H. On the expected value of the linear complexity and k-error linear complexity of periodic sequences[J]. IEEE Transactions on Information Theory,2002, 48(11):2817-2825.
[10]丁存生,肖国镇.流密码学及其应用[M].北京:国防工业出版社,1994:5-32.
[11]魏仕民.流密码及其复杂度分析[D].西安:西安电子科技大学博士论文,2001:8-18.
[12]朱莉艳.流密码复杂性研究[D].扬州:扬州大学硕士论文,2008:8-11.
[13]Golomb S W. Shift Register Sequences[M]. Revised edition:Laguna Hills, CA:Aegean Park, 1982:9-24.
[14]Massey J L. Shift register synthesis and BCH decoding[J]. IEEE Transactions on Information Theory,1969,15(1):122-127.
[15]Massey J L. An introduction to cryptography[C]. Proceed. of IEEE, May 1988:533-549.
[16]Massey J L, Serconek S. Linear complexity of periodic sequences:a general theory[C]. Advances in Cryptology-CRYPTO'96, LNCS 1109. Berlin:Springer-Verlag,1996:358-371.
[17]Rueppel R A. Analysis and design of stream ciphers[M]. Berlin:Springer-Verlag,1986: 21-30.
[18]Rueppel R A. Stream Ciphers [M]. Contemporary Cryptology-The Science of Information-Integrity. New York:IEEE Press,1992:65-134.
[19]Schneier B. Applied Cryptography:Protocols, Algorithms, and Source Code in C[M]. New York:Wiley John&Sons,1996:34-40.
[20]Stinson D R. Cryptography theory and practice[M]. Boca Raton:CRC Press,1995:50-69.
[21]李晖,李丽香,邵帅.对称密码学及其应用[M].北京:北京邮电大学出版社,2009:10-39.
[22]祝跃飞,王磊.密码学与通信安全基础[M].武汉:华中科技大学出版社,2008:40-67.
[23]牛志华.周期序列线性复杂度及其稳定性分析[D].西安:西安电子科技大学博士论文,2005:12-23.
[24]冯登国.密码分析学[M].北京:清华大学出版社,2000年:10-45.
[25]赖溪松,韩亮,张真诚(著),张玉清,肖国镇(改编).计算机密码学以其应用[M].北京:国防工业出版社,2001:32-38.
[26]Wenbo Mao. Modern Cryptography Theory and Practice[M]. Prentice Hall PTR, August, 2003:9-21.
[27]王育民,刘建伟.通信网的安全一理论与技术[M].西安:西安电子科技大学出版社,1998:18-23.
[28]吴文玲,冯登国,张文涛.分组密码的设计与分析[M].北京:清华大学出版社,2009:2-6.
[29]张红旗,王鲁.信息安全技术[M].北京:高等教育出版社,2008:31-33.
[30]Diffe W, Hellman M E. New directions in cryptography[J]. IEEE Transactions on Information Theory,1976,22(6):644-654.
[31]胡予濮,张玉清,肖国镇.对称密码学[M].北京:机械工业出版社,2002:56-70.
[32]王菊香.周期序列的k-错线性复杂度分析和研究[D].合肥:合肥工业大学,2009:21-27.
[33]杨义先,钮心忻.应用密码学[M].北京:北京邮电大学出版社,2005:96-103.
[34]覃中平,张焕国等.信息安全数学基础[M].北京:清华大学出版社,2006:18-31.
[35]Wei S, Xiao G, Chen Z. A fast algorithm for determining the minimal polynomial of a sequence with period 2p" over GF(q)[J]. IEEE Transactions on Information Theory,2002, 48(10):2754-2757.
[36]Xiao G, Wei S, Lam K Y, and Imamura K. A fast algorithm for determining the linear complexity of a sequence with period pn over GF(q)[J]. IEEE Transactions on Information Theory,2000,46(6):2203-2206.
[37]戴小平,周建钦.求周期为2pm二元序列k错线性复杂度的快速算法[J].兰州大学学报(自然科学版),2008,44(1):65-70.
[38]白恩健,谭示崇,肖国镇.确定周期为pn的q元序列k-错复杂度曲线的一个快速算法[J].西安电子科技大学学报,2004,31(3):388-393.
[39]Zhou J. An algorithm for the k-error linear complexity of a sequence with period 2pn over GF(q)[C]. IWSDA'07, IEEE Computer Society,2007:104-108.
[40]Chen H. Reducing the computation of linear complexities of periodic sequences over GF(pm)[J]. IEEE Transactions on Information Theory,2006,52(12):5537-5539.
[41]Niu Z, Xiao G. Analysis of the linear complexity and its stability for 2p"-periodic binary sequences[J]. IEICE Trans Fundamentals,2005, E88-A(9):2412-2418.
[42]牛志华,白恩健,肖国镇.pmgn周期q元序列线性复杂度与k错复杂度的关系[J].通信学报,2004,25(11):84-89.
[43]谭林,戚文峰.2mpn周期二元序列的线性复杂度和k错线性复杂度[J].通信学报,2008,29(7):44-49.
[44]周建钦.求周期序列线性复杂度的快速算法[J].华中科技大学学报(自然科学版),2007,35(2):43-46.
[45]Zhou J, Zheng Q. A fast algorithm for determining the linear complexity of periodic sequences over GF(3)[C]. CANS 2006, LNCS 4301,2006:213-223.
[46]Zhou J. Fast algorithms for determining the minimal polynomial of sequences with period kn over GF(pm)[J]. International Journal of Network Security,2008,7(1):38-41.
[47]王磊,张玉清,肖国镇.确定周期为pn的二元序列的k错线性复杂度的一个算法[J].通信学报,2001,22(4):91-95.
[48]魏仕民,董庆宽,肖国镇.确定周期序列k-错线性复杂度的一个快速算法[J].西安电子科技大学学报,2001,28(4):421-424.
[49]Lauder A and Paterson K. Computing the error linear complexity spectrum of a binary sequence with period 2n[J]. IEEE Transactions on Information Theory,2003,49(1): 273-280.
[50]Salagean A. On the computation of the linear complexity and the k-error linear complexity of binary sequences with period a power of two[J]. IEEE Transactions on Inform. Theory, 2005,51(3):1145-1150.
[51]魏仕民.确定周期序列k-错线性复杂度的一个快速算法[J].电子学报,2004,32(5):705-708.
[52]Zhou J, Xiong W, Zhao Z, You L. The Tight Error Linear Complexity of Periodic Sequences[C]. International Conference on Computational Intelligence and Security,2009: 197-201.
[53]魏仕民,肖国镇,陈钟.确定周期为2npm二元序列线性复杂度的快速算法[J].中国科学(E辑),2002,32(3):401-408.
[54]白恩健,刘晓娟,肖国镇.确定周期为pn的二元序列k-错复杂度曲线的快速算法[J].通信学报,2004,25(10):17-23.