期刊文献+

基于编织法的de Bruijn序列差异性研究

On Difference of de Bruijn Sequences Based on Interleaving Construction
下载PDF
导出
摘要 由于de Bruijn序列具有周期最大、元素分布均衡、线性复杂度较高等良好的伪随机性质,因此在序列密码的研究领域中占有重要位置,其中de Bruijn序列的构造问题一直是研究的热点问题之一.目前已有多种构造de Bruijn序列的方法,而对于构造所得de Bruijn序列的差异性则相对研究较少,本文主要讨论基于编织法得到的de Bruijn序列的差异性.基于编织法,高杨等人给出了一种由一条n级de Bruijn序列来构造四条2n级de Bruijn序列的方法.由于这四条2n级de Bruijn序列由两条编织序列I1和I2唯一决定,因此de Bruijn序列的差异性可由这两条编织序列的差异性来刻画,而这两条编织序列的差异性又可以转化为两个指定映射的差异性.映射的差异性问题进一步可归结为对n长状态(e0e2…e2n-2)来源序列的研究,最终本文得到两个映射出现差异的充要条件,进而得到这两个映射的差异数和差异率2(2^n-1+1)^-1.据此可知,由编织法构造的编织序列的差异率随着级数的增大而减少. De Bruijn sequences have good pseudo-random properties,such as the maximum period,uniform element distribution and the higher linear complexity,hence they play a very important role in stream cipher,and their construction has always been one of hot research topics.Many methods of constructing de Bruijn sequences have been presented,however,few discussions are about the differences of the constructed de Bruijn sequences.This paper studies the differences of de Bruijn sequences generated by interleaving construction.Based on interleaving construction,four de Bruijn sequences of 2n-stage can be constructed from one de Bruijn sequence of n-stage by Gao et al.Since these de Bruijn sequences are uniquely determined by two interleaved sequences I1and I2,the difference of the former can be described by the difference of these two interleaved sequences,which can be transformed into the difference between two given mappings f(x)and g(x).Furthermore,the difference between these two mappings turns into the discussions of the source of the n-tuple state(e0e2···e2n-2).Finally,this paper gives a necessary and sufficient condition for x so that f(x)≠g(x)holds,the number of such x has been enumerated,and the difference rate 2(2^n-1+1)^-1can be drawn.It can be seen that the difference rate of interleaved sequences decreases with the increase of n.
作者 王向宇 王中孝 WANG Xiang-Yu;WANG Zhong-Xiao(Strategic Support Force Information Engineering University,Zhengzhou 450001,China)
出处 《密码学报》 CSCD 2020年第2期169-178,共10页 Journal of Cryptologic Research
基金 国家自然科学基金(61502524)。
关键词 de Bruijn序列 编织法 编织序列 差异性 de Bruijn sequence interleaving construction method interleaved sequences difference
  • 引文网络
  • 相关文献

参考文献2

二级参考文献13

  • 1朱士信,孙琳.k元de Bruijn序列的反馈函数的一个升级算法[J].电子学报,2006,34(6):1066-1068. 被引量:13
  • 2Games RA,Chan AH.A fast algorithm for determining the complexity of a binary sequence with period 2n. IEEE Transactions on Information Theory . 1983
  • 3Willi Meier,Othmar Staffelbach.Fast correlation attacks on certain stream ciphers[J]. Journal of Cryptology . 1989 (3)
  • 4T. Etzion,A. Lempel.Algorithms for the generation of full-length shift- register sequences. IEEE Transactions on Information Theory . 1984
  • 5Man-Keung Siu,Po Tong.Generation of some de Bruijn sequences. Discrete Mathematics . 1980
  • 6Golomb SW.Shift Register Sequences. . 1967
  • 7Green, D.H.,Dimond, K.R.Nonlinear product-feedback shift registers. Electrical Engineers, Proceedings of the Institution of . 1970
  • 8Courtois N T,Meier W.Algebraic attacks on stream ciphers with linear feedback. Advances in Cryptology-Eurocrypt 2003 . 2003
  • 9Annexstein,F.S.Generating De Bruijn sequences: an efficient implementation. IEEE Transactions on Computers . 1997
  • 10Fredricksen H.A survey of full length nonlinear shift-register cycle algorithms. SIAM Review . 1982

共引文献3

;
使用帮助 返回顶部