计算机工程

• 安全技术 • 上一篇    下一篇

基于de Bruijn图的M序列递归升级构造方法

郭辉1,2,柏森1,2,阳溢1,2,宋斌1,2,李淑云3   

  1. (1.重庆通信学院信息工程系,重庆 400035; 2.应急通信重庆市重点实验室,重庆 400035; 3.解放军66019部队,北京 100093)
  • 收稿日期:2014-07-25 出版日期:2015-08-15 发布日期:2015-08-15
  • 作者简介:郭辉(1982-),男,工程师、硕士研究生,主研方向:信息安全,图论M序列;柏森,教授、博士;阳溢,助教、硕士;宋斌,硕士研究生;李淑云,讲师、硕士。
  • 基金项目:
    国家自然科学基金资助项目(61272043);重庆市基础与前沿研究计划基金资助项目(cstc2013jjB40009);重庆高校创新团队建设计划基金资助项目(KJTD201343);重庆通信学院基础理论研究基金资助项目“基于雾气模型的图像视频加雾隐藏技术研究”。

Recursive Upgrade Construction Method of M Sequence Based on de Bruijn Graph

GUO Hui 1,2,BAI Sen 1,2,YANG Yi 1,2,SONG Bin 1,2 ,LI Shuyun 3   

  1. (1.Department of Information Engineering,Chongqing Communication Institute,Chongqing 400035,China; 2.Chongqing Key Laboratory of Emergency Communication,Chongqing 400035,China; 3.Unit 66019 of PLA,Beijing 100093,China)
  • Received:2014-07-25 Online:2015-08-15 Published:2015-08-15

摘要: 高级M序列具有良好的伪随机特性和安全特性,广泛应用于信息安全领域,如何快速有效生成高级M序列一直是研究的热点。在图论知识的基础上,给出一种新的M序列递归升级构造方法,根据n级de Bruijn图中的一条Hanilton回路构成n级M序列、Euler回路构成n+1级M序列的 原理,在已知一条二元n级M序列的条件下,将M序列转换为de Bruijn图中一条Hamilton回路,求出该Hamilton回路的补路,得到一条Euler回路,从而构成n+1级M序列,据此依次递归生成一条更高级的M序列。利用NIST SP 800-22随机数测试标准对生成的高级M序列进行测试,结果表明,该方法生成的高级M序列测试值都大于0.01,满足随机性要求。

关键词: 信息安全, M序列, de Bruijn图, NIST SP800-22随机数测试, Hamilton回路, Euler回路

Abstract: Because of good pseudo-randomness and security features of the high order M sequence,it is applied to the field of information security,therefore,how to generate advanced M sequence quickly and efficiently is a research focus.A new M sequence recursive upgrade construction method based on de Bruijn graph is presented.This method,under the condition of a known Hamiltonian cycle of the binary nth order de Bruijn graph,according to the theory that a Hamiltonian cycle of an nth order de Bruijn graph can construct nth order M sequence,and an Euler cycle can construct a higher order M sequence,converts the M sequence to a Hamiltonian cycle in this de Bruijn graph and determines the complementary cycles of this Hamiltonian cycle.Circles and loopbacks of diverse length constitute the complementary cycles,it obtains a Euler cycle that can construct(n+1)th order M sequence,from which a higher order M sequence is generated by successive recursive method.The generated high order M sequence is tested by NIST SP 800-22 random number test suit.Results show that advanced order M sequence has rather good randomness.

Key words: information security, M sequence, de Bruijn graph, NIST SP800-22 random number test, Hamilton cycle, Euler cycle

中图分类号: