摘要： 高级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

中图分类号: 

• TP309