一种基于“编织法”的de Bruijn序列构造算法

doi:10.3969/j.issn.0372-2112.2018.01.007

电子学报 ›› 2018, Vol. 46 ›› Issue (1): 48-54.DOI: 10.3969/j.issn.0372-2112.2018.01.007

一种基于“编织法”的de Bruijn序列构造算法

高杨, 刘松华, 王中孝

洛阳外国语学院, 河南洛阳 471003

收稿日期:2016-07-13 修回日期:2017-01-08 出版日期:2018-01-25
- 通讯作者:
- 高杨
- 作者简介:
- 刘松华,男,1979年生于吉林安图,现为洛阳外国语学院研究生,主要研究方向为密码学.E-mail:liusonghua0519@163.com
- 基金资助:
- 国家自然科学基金 (No.61502524）

A de Bruijn Sequence Construction Algorithm Based on ‘Interleaving’ Construction Method

GAO Yang, LIU Song-hua, WANG Zhong-xiao

Luoyang University of Foreign Languages, Luoyang, Henan 471003, China

Received:2016-07-13 Revised:2017-01-08 Online:2018-01-25 Published:2018-01-25

摘要/Abstract

摘要： 文章首先给出n级de Bruijn序列通过"编织法"所产生序列的周期，并证明其中所有2n长状态两两不同.之后，论证出平移等价意义下一条n级de Bruijn序列仅能编织出两条序列.最后针对每一条序列，补全其缺失的四个2n长状态即可构造出2n级de Bruijn序列.由于增添比特的方式有两种，因此由一条n级de Bruijn序列可构造出四条2n级de Bruijn序列.

关键词: 序列密码, de Bruijn序列, 编织法, 平移等价

Abstract: Firstly, this paper determines the period of ‘Interleaving’ sequences from de Bruijn sequences of n-stage and proves all 2n-tuple states are different from each other. Secondly, in the view of shift equivalence, the paper demonstrates that one can only construct two sequences from de Bruijn sequences of n-stage. For each one, the completion of its missing four 2n-tuple states can construct de Bruijn sequences of 2n-stage. Since there are two different ways to complete the missing bits, we can finally get four de Bruijn sequences of 2n-stage from one de Bruijn sequence of n-stage.

Key words: stream cipher, de Bruijn sequence, interleaving method, shift equivalence

中图分类号:

TN918.2

高杨, 刘松华, 王中孝. 一种基于“编织法”的de Bruijn序列构造算法[J]. 电子学报, 2018, 46(1): 48-54.

GAO Yang, LIU Song-hua, WANG Zhong-xiao. A de Bruijn Sequence Construction Algorithm Based on ‘Interleaving’ Construction Method[J]. Acta Electronica Sinica, 2018, 46(1): 48-54.

参考文献

[1] 王中孝,戚文峰.非线性反馈移位寄存器串联分解唯一性探讨[J].电子与信息学报,2014,36(7):1656-1660. Wang Zhong-xiao,Qi Wen-feng.On the uniqueness of decomposition of a NFSR into a cascade connection of smaller NFSRs[J].Journal of Electronics & Information Technology,2014,36(7):1656-1660.(in Chinese)
[2] Meier W,Staffelbach O.Fast correlation attacks on certain stream ciphers[J].Journal of Cryptology,1989,1(3):159-176.
[3] Courtois N T.Higher order correlation attacks,XL algorithm and cryptanalysis of toyocrypt[A].Proceedings of Information Security and Cryptology-ICISC 2002,Lecture Notes in Computer Science 2587[C].Berlin:Springer-Verlag,2003.182-199.
[4] Courtois N T,Meier W.Algebraic attacks on stream ciphers with linear feedback[A].Advances in Cryptology EUROCRYPT 2003[C].Warsaw,Poland,2003.346-359.
[5] Meier W,Pasalic E,Carlet C.Algebraic attacks and decomposition of boolean functions[A].Proceedings of Advances in Cryptology EUROCRYPT 2004,Lecture Notes in Computer Science 3027[C].Berlin:Springer-Verlag,2004.474-491.
[6] Turan M S.On the nonlinearity of maximum-length NFSR feedbacks[J].Cryptography and Communications,2012,4(3/4):233-243.
[7] Zhong J,Lin D.Driven stability of nonlinear feedback shift registers with inputs[J].IEEE Transactions on Communications,2016,64(6):2274-2284.
[8] Martin H,Thomas J,Willi M.New Stream Cipher Designs:The eSTREAM Finalists[M].Berlin:Springer,2008.179-190.
[9] 朱士信,孙琳.K元de Bruijn序列的反馈函数的一个升级算法[J].电子学报,2006,34(6):1066-1068. ZHU Shi-xin,SUN Lin.An algorithm for generating feedback functions of k-ary de Bruijn sequences by raising stage[J].Acta Electronica Sinica,2006,34(6):1066-1068.(in Chinese)
[10] Lempel A.On a homomorphism of the de Brujin graph and its application to design of feedback shift registers[J].IEEE Transactions on Computers,1970,19(12):1204-1209.
[11] Mandal K,Gong G.Crytographically strong de Bruijn sequences with large periods[A].Proceedings of Selected Area in Crytography,Lecture Notes in Computer Science 7707[C].Berlin:Springer-Verlag,2013.104-118.
[12] Abbas A,Mufutau A.A recursive construction of nonbinary de Bruijn sequences[J].Designs Codes and Cryptography,2011,60(2):155-169.
[13] Mitchell C J,Etzion T,Paterson K G.A method for constructing decodable de Brujin sequences[J].IEEE Transactions on Information Theory,1996,42(5):1472-1478.
[14] 丁存生,肖国镇.流密码学及其应用[M].北京:国防工业出版社,1994.
[15] Golomb S W.Shift Register Sequences[M].San Francisco:Aegean Park Press,1967.
[16] Dubrova E.Generation of full cycles by a composition of NLFSRs[J].Designs,Codes and Cryptography,2014,73(2):469-486.
[17] Gong G.Theory and applications of q-ary interleaved sequences[J].IEEE Transactions on Information Theory,1995,41(2):400-411.
[18] Li N,Tang X,Helleseth T.New M-ary sequences with low autocorrelation from interleaved technique[J].Designs Codes and Cryptography,2014,73(1):237-249.

一种基于“编织法”的de Bruijn序列构造算法

A de Bruijn Sequence Construction Algorithm Based on ‘Interleaving’ Construction Method

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 8

编辑推荐

Metrics

[1]	李俊志, 关杰. 非线性反馈移存器型序列密码的完全性通用算法[J]. 电子学报, 2018, 46(9): 2075-2080.
[2]	皮飞;戚文峰;. 二元周期序列的4-错线性复杂度[J]. 电子学报, 2011, 39(12): 2914-2920.
[3]	赵和平;赵聆波. 一种基于物理噪声源的复合加密算法[J]. 电子学报, 2009, 37(10): 2193-2198.
[4]	朱士信;孙琳. k元de Bruijn序列的反馈函数的一个升级算法[J]. 电子学报, 2006, 34(6): 1066-1068.
[5]	丁群, 彭喜元, 杨自恒. 基于神经网络算法的组合序列密码芯片[J]. 电子学报, 2006, 34(3): 409-412.
[6]	赵耀东, 戚文峰. 二元周期序列的k错误线性复杂度[J]. 电子学报, 2005, 33(1): 12-16.
[7]	金晨辉;高海英. 对两个基于混沌的序列密码算法的分析[J]. 电子学报, 2004, 32(7): 1066-1070.
[8]	李红达;冯登国. 复合离散混沌动力系统与序列密码体系[J]. 电子学报, 2003, 31(8): 1209-1212.