GF（q）上新型自缩序列模型及研究
|
摘要
自缩序列是一类重要的伪随机序列,而周期和线性复杂度是序列伪随机性的经典量度.如何构造自缩序列的新模型,使生成序列具有大的周期和高的线性复杂度是一个重要问题.本文构造了GF(3)上一种新型的自缩序列模型,利用有限域理论,研究了生成序列的周期和线性复杂度,得到了如下结论:周期上界为3~n,下界为3~(?);线性复杂度上界为3~n,下界为3~(?);并讨论了基于GF(3)上本原三项式和四项式的自缩序列的周期和线性复杂度.且进一步把此模型推广到了任意的有限域GF(q),得到的生成序列的周期上界为(?),下界为q~(?);线性复杂度上界为(?),下界为q~(?).且当q=2时,恰是文献[1]中的结果.
Self-shrinking sequence is an important kind of pseudo-random sequences. Period and linear complexity are classic measures of pseudo-random sequences. So, it becomes an important issue to construct new models of Self-shrinking sequence that could generate sequences with great period and high linear complexity. In view of this question, a new model of Self-shrinking sequence over is constructed. After the study of the period and linear complexity of the generated sequence using the theory of finite fields, there are some main conclusions :The upper bound of the period is 3~n, the lower bound is 3~(2(?)n/3(?)) ;The upper bound of linear complexity is 3~n, the lower bound is 3~(2(?)n/3(?)-1) ; Moreover, the period and linear complexity of the generated sequence based on primitive trinomials and quarternomials of degree n over are discussed. And the model is extended to arbitrary finite field GF(q). Obtain these conclusions :the upper bound of the period of the generated sequences is (q~n(q-1))/2 the lower bound is q~((q-1)(?)n/q(?)); The upper bound of linear complexity of the generated sequences is (q~n(q-1))/2 , the lower bound is q~((q-1)(?)n/q(?)-1)
Self-shrinking sequence is an important kind of pseudo-random sequences. Period and linear complexity are classic measures of pseudo-random sequences. So, it becomes an important issue to construct new models of Self-shrinking sequence that could generate sequences with great period and high linear complexity. In view of this question, a new model of Self-shrinking sequence over is constructed. After the study of the period and linear complexity of the generated sequence using the theory of finite fields, there are some main conclusions :The upper bound of the period is 3~n, the lower bound is 3~(2(?)n/3(?)) ;The upper bound of linear complexity is 3~n, the lower bound is 3~(2(?)n/3(?)-1) ; Moreover, the period and linear complexity of the generated sequence based on primitive trinomials and quarternomials of degree n over are discussed. And the model is extended to arbitrary finite field GF(q). Obtain these conclusions :the upper bound of the period of the generated sequences is (q~n(q-1))/2 the lower bound is q~((q-1)(?)n/q(?)); The upper bound of linear complexity of the generated sequences is (q~n(q-1))/2 , the lower bound is q~((q-1)(?)n/q(?)-1)
引文
[1]W. Meier, O. Staffelbach. The Self-shrinking Generator [A] .Advances in Cryptology Eurocrypt'94,LNCS, Vol 950[C].Berlin:Spring-verlag,1995,pp:205-214.
[2]S. R. Blackburn. The Linear Complexity of the Self-shrinking Generator[J].IEEE Transactions of Information Theory,1999,45(6),pp:2073-2077.
[3]王锦玲.多位Self-shrinking序列模型与研究[J].郑州大学学报,1998,19(2),PP:119-122.
[4]D. Coppersmith, H. Krawczyk. Y. Mansour. The Shrinking Generator[A].Advance in Cryptology Eurocrypt'93,LNCS,Vol773[C].Berlin:Spring-Verlag,1993,pp:22-39.
[5]白恩健,董庆宽,肖国镇.自缩控生成器[J].西安电子科技大学学报(自然科学版),2004,31(2),pp:264-268.
[6]张楠,戚文峰.基于三项和五项本原多项式的Self-shrinking序列[J].信息工程大学学报,2004,5(2),pp:4-8.
[7]胡予濮,张玉清,肖国镇.对称密码[M].北京:机械工业出版社,2002,pp:64-76.
[8]R.Lidl,H.Niederreiter.Finite Fields[M].Addison-Wesley Publishing Company, 1983.
[9]柯召,孙琦.数论讲义[M].北京:高等教育出版社,2003
[10]王锦玲,王娟,陈忠宝.GF(3)上多位自收缩序列的模型与研究[A].密码学进展-China Crypt'2007,ISBN[C].西南交通大学出版社,2007,pp:299-300.
[11]王娟.GF(3)上多位自缩序列的模型与研究[D].2008年5月郑州大学硕士学位论文.
[12]万哲先.代数与编码[M].北京:科学出版社,1985
[13]丁存生,肖国镇.流密码及其应用[M].北京:国防工业出版社,1994.
[14]Lidl R and Niederreiter H.Intorduction to Finite Fields and Their Aplications[M].Combridge University Press, 1986.
[15]肖国镇,梁传甲,王育民.伪随机序列及其应用[M].北京:国防工业出版社,1985.
[16]Douglas R Stinson著,冯登国译.密码学原理与实践[M].北京:电子工业出版社,2003.
[17]Rainer A.Rueppel.When Shift Registers Clock Themselves [A].Advances In Cryptology Procrrding of Eurocrypt' 87,Springer-Verlag,1987,pp:53-64.
[18]Smeet B.A Note on Sequence Generated by Clock Controlled Shift Register[J].Advances in Cryptology,LNCS,Springer-Verlag,1986,PP:142-148.
[19]王锦玲.一类钟控序列线性复杂度的界[J].通信保密,1994,60(4),pp:44-48.
[20]王锦玲,毕文斌.三元树上的线性递归序列[J].郑州大学学报(工学版),2006,27(2),PP:110-112.
[21]王锦玲,雷玉印,杨娜,王静.Jennings复合序列的一些补注[J].郑州大学学报(工学版),2007,28(2),PP:110-113.
[22]Gong G,Jiang SQ.The Editing Generator and Tts Cryptanalysis[J].[EB/OL].http:www.cacr.Math.Uwaterloo.ca,2002,pp:12-28.
[23]王锦玲,陈建梅,苏江.一种新的Shrinking序列周期及线性复杂度[J].通信保密,1999,80(4),pp:48-51.
[2]S. R. Blackburn. The Linear Complexity of the Self-shrinking Generator[J].IEEE Transactions of Information Theory,1999,45(6),pp:2073-2077.
[3]王锦玲.多位Self-shrinking序列模型与研究[J].郑州大学学报,1998,19(2),PP:119-122.
[4]D. Coppersmith, H. Krawczyk. Y. Mansour. The Shrinking Generator[A].Advance in Cryptology Eurocrypt'93,LNCS,Vol773[C].Berlin:Spring-Verlag,1993,pp:22-39.
[5]白恩健,董庆宽,肖国镇.自缩控生成器[J].西安电子科技大学学报(自然科学版),2004,31(2),pp:264-268.
[6]张楠,戚文峰.基于三项和五项本原多项式的Self-shrinking序列[J].信息工程大学学报,2004,5(2),pp:4-8.
[7]胡予濮,张玉清,肖国镇.对称密码[M].北京:机械工业出版社,2002,pp:64-76.
[8]R.Lidl,H.Niederreiter.Finite Fields[M].Addison-Wesley Publishing Company, 1983.
[9]柯召,孙琦.数论讲义[M].北京:高等教育出版社,2003
[10]王锦玲,王娟,陈忠宝.GF(3)上多位自收缩序列的模型与研究[A].密码学进展-China Crypt'2007,ISBN[C].西南交通大学出版社,2007,pp:299-300.
[11]王娟.GF(3)上多位自缩序列的模型与研究[D].2008年5月郑州大学硕士学位论文.
[12]万哲先.代数与编码[M].北京:科学出版社,1985
[13]丁存生,肖国镇.流密码及其应用[M].北京:国防工业出版社,1994.
[14]Lidl R and Niederreiter H.Intorduction to Finite Fields and Their Aplications[M].Combridge University Press, 1986.
[15]肖国镇,梁传甲,王育民.伪随机序列及其应用[M].北京:国防工业出版社,1985.
[16]Douglas R Stinson著,冯登国译.密码学原理与实践[M].北京:电子工业出版社,2003.
[17]Rainer A.Rueppel.When Shift Registers Clock Themselves [A].Advances In Cryptology Procrrding of Eurocrypt' 87,Springer-Verlag,1987,pp:53-64.
[18]Smeet B.A Note on Sequence Generated by Clock Controlled Shift Register[J].Advances in Cryptology,LNCS,Springer-Verlag,1986,PP:142-148.
[19]王锦玲.一类钟控序列线性复杂度的界[J].通信保密,1994,60(4),pp:44-48.
[20]王锦玲,毕文斌.三元树上的线性递归序列[J].郑州大学学报(工学版),2006,27(2),PP:110-112.
[21]王锦玲,雷玉印,杨娜,王静.Jennings复合序列的一些补注[J].郑州大学学报(工学版),2007,28(2),PP:110-113.
[22]Gong G,Jiang SQ.The Editing Generator and Tts Cryptanalysis[J].[EB/OL].http:www.cacr.Math.Uwaterloo.ca,2002,pp:12-28.
[23]王锦玲,陈建梅,苏江.一种新的Shrinking序列周期及线性复杂度[J].通信保密,1999,80(4),pp:48-51.