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

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

作　　者：郭辉[1,2] 柏森[1,2] 阳溢[1,2] 宋斌[1,2] 李淑云 

机构地区：[1]重庆通信学院信息工程系 [2]应急通信重庆市重点实验室 [3]解放军66019部队

出　　处：《计算机工程》2015年第8期144-149,161,共7页Computer Engineering

基　　金：国家自然科学基金资助项目(61272043);重庆市基础与前沿研究计划基金资助项目(cstc2013jj B40009);重庆高校创新团队建设计划基金资助项目(KJTD201343);重庆通信学院基础理论研究基金资助项目"基于雾气模型的图像视频加雾隐藏技术研究"

摘　　要：高级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,满足随机性要求。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.

关 键 词：信息安全 M序列 DE BRUIJN图 NIST SP800-22随机数测试 HAMILTON回路 Euler回路 

分 类 号：TP309[自动化与计算机技术—计算机系统结构]