基于随机序列统计特性的伪随机序列生成方法

doi:10.11 959/j.issn.2096-109x.2017.00125

网络与信息安全学报 ›› 2017, Vol. 3 ›› Issue (1): 31-38.doi: 10.11 959/j.issn.2096-109x.2017.00125

基于随机序列统计特性的伪随机序列生成方法

柏森^1,²(),周龙福¹,郭辉³,闫兵²

¹ 重庆工程学院软件学院，重庆400056
² 重庆通信学院信息工程系，重庆400035
³ 61541部队，北京 100094

修回日期:2016-12-02 出版日期:2017-01-15 发布日期:2020-03-20
作者简介:柏森（1963-），男，四川达县人，博士，重庆工程学院教授、硕士生导师，主要研究方向为信息隐藏、图像加密。|周龙福（1971-），男，江西临川人，硕士，重庆工程学院副教授，主要研究方向为软件体系结构、数据库、网络与系统安全。|郭辉（1982-），男，河南辉县人，硕士，61541部队工程师，主要研究方向信息安全。|闫兵（1993-），男，湖南常德人，重庆通信学院硕士生，主要研究方向信息安全。
基金资助:
国家自然科学基金资助项目(61272043);重庆市基础与前沿研究计划基金资助项目(cstc2013jjB40009);应急通信重庆市重点实验室能力提升基金资助项目(cstc2014pt-sy40003)

Method to generate the pseudo random sequence based on the statistical properties

Sen BAI^1,²(),Long-fu ZHOU¹,Hui GUO³,Bing YAN²

¹ School of Software, Chongqing Institute of Engineering, Chongqing 400056, China
² Information Engineering Department, Chongqing Communication Institute, Chongqing 400035, China
³ Unit 61541 of PLA, Beijing 100094, China

Revised:2016-12-02 Online:2017-01-15 Published:2020-03-20
Supported by:
The National Natural Science Foundation of China(61272043);Basic＆Frontier Project of Chongqing(cstc2013jjB40009);Capability Enhancement Foundation of Chongqing Key Laboratory of Emergency Communication(cstc2014pt-sy40003)

摘要/Abstract

摘要：

在现有生成伪随机序列的方法中，产生的伪随机序列存在均衡性、游程特性不够好的问题。根据随机序列的统计特性，在骑士巡游问题 SemiHam 求解算法的基础上，提出了基于随机序列统计特性的伪随机序列生成方法。首先，对棋盘中的格子设定不同长度的0、1游程值；然后，再用骑士巡游问题SemiHam求解算法产生的Hamilton圈对设定游程值的棋盘进行扫描；最后，取出0、1游程值，得到伪随机序列。实验结果表明，该算法产生的伪随机序列满足随机序列统计特性，且随机性较好。

关键词: 伪随机序列, 随机序列统计特性, SemiHam算法, NISTSP800-22随机性测试

Abstract:

There are some problems existing in pseudo-random sequence generating methods, such as the weaker proportionality, bad run length characteristic, etc. Hence, based on the SimiHam algorithm in Knight's tour problem, a pseudo-random sequences generating method was proposed according to the statistical properties of random se-quence. First, set runs value 0 and 1 in different length for the grids in chessboard, and then scan the chessboard with Hamilton cycles which are generated by SemiHam algorithm in Knight's tour problem, At last extract run length values of 0 and 1 and get the pseudo-random sequences. Experimental results show that the pseudo-random se-quence generated by the proposed algorithm satisfies the statistical properties of a random sequence and has better randomness.

Key words: pseudo-random sequence, statistical properties of a random sequence, SemiHam algorithm, NIST SP800-22 random test

中图分类号:

TN919.81

柏森,周龙福,郭辉,闫兵. 基于随机序列统计特性的伪随机序列生成方法[J]. 网络与信息安全学报, 2017, 3(1): 31-38.

Sen BAI,Long-fu ZHOU,Hui GUO,Bing YAN. Method to generate the pseudo random sequence based on the statistical properties[J]. Chinese Journal of Network and Information Security, 2017, 3(1): 31-38.

图/表 12

图1

图2

图3

图4

图5

表1

长度为l的游程个数占总游程比例"

游程长度/	游程占总游程的比例
l=1	$\frac{1}{2}$
l=2	$\frac{1}{4}$
l=3	$\frac{1}{8}$
l=4	$\frac{1}{16}$
l=5	$\frac{1}{32}$

表1

表2

图6

图7

表3

表4

表5

参考文献 18

[1]	吴资玉，韩庆文，通信原理[M]. 北京: 电子工业出版社， 2008: 316-317.
	WU Z Y , HAN Q W . Principles of communications[M]. Beijing: Publishing House of Electronics Industry. 2008: 316-317.
[2]	HUANG X , YE G . An image encryption algorithm based on hy-per-chaos and DNA sequence[J]. Multimedia Tools and Applica-tions, 2014, 72 (1): 57-70.
[3]	雷雄俊，刘光斌 . GPS伪随机序列的构成及应用分析[J]. 光通信研究， 2010, 21 (6): 64-67.
	LEI H J , LIU G B . Architecture and applications of GPS pseudo-random sequence[J]. Study on Optical Communications, 2010, 21 (6): 64-67.
[4]	AHMED Z , CANCES J P , MEGHDADI V . MEGHDADI V. Cryptographic spread spectrum relay communication[C]// Next Generation Mobile Appli-cations, Services and Technologies. 2008: 588-591.
[5]	张群英，方广有 . 伪随机序列编码脉冲信号在探地雷达中的应用研究[J]. 电子与信息学报， 2012, 33 (2): 424-428.
	ZHANG Q Y , FANG G Y . The study of pseudo random sequence's application to GPR[J]. Journal of Electronics＆Information Tech-nology, 2012, 33 (2): 424-428
[6]	杜小妮 . 伪随机序列的构造及其随机性分析[D]. 陕西: 西安电子科技大学， 2008.
	DU X N . The construction and randomness analysis of pseudo ran-dom sequence[D]. Shaanxi: Xidian University, 2008.
[7]	张丽姣，闵乐泉，韩双霜 . 二维新混沌系统和伪随机数生成器的设计[J]. 计算机工程与设计， 2014, 35 (4): 1178-1182.
	ZHANG L J , MIN L Q , HAN S S . Design of 2-dimensional novel chaotic system and pseudo-random number generator[J]. Computer Engineering and Design, 2014, 35 (4): 1178-1182.
[8]	孙克辉，叶正伟，贺少波 . 混沌伪随机序列发生器的FPGA设计与实现[J]. 计算机应用与软件， 2014, 6 (12): 3-7.
	SUN K H , YE Z W , HE S B , Design and implementation of chaotic pseudo-random sequence generator using FPGA[J]. Computer Ap-plications and Software, 2014, 6 (12): 3-7.
[9]	李家标，曾以成，陈仕必，等. 改进型Henon映射生成混沌伪随机序列及性能分析[J]. 物理学报， 2011, 60 (6): 126-130.
	LI J B , ZENG Y C , CHEN S B , Modified Hénon map generated chaotic pseudorandom-bit sequences and performance analysis[J]. Acta Physica Sinica, 2011, 60 (6): 126-130.
[10]	叶珍，臧鸿雁 . 基于混沌系统的量化方法及伪随机性研究[J]. 计算机应用研究， 2014, 31 (12): 3719-3721.
	YE Z , ZANG H Y . Research of quantization methods and pseudo-randomness based on chaotic systems[J]. Application Research of Computers, 2014, 31 (12): 3719-3721.
[11]	花文昭，韩文报 . 基于椭圆曲线的二元伪随机序列构造与分析[J]. 计算机工程， 2012, 38 (18): 100-102.
	HUA W Z , HAN W B . Construction and analysis of binary pseu-dorandom sequences based on elliptic curve[J]. Computer Engi-neering, 2012, 38 (18): 100-102.
[12]	JESSA M , JAWORSKI M . Producing secure pseudorandom se-quences with combined multiplicative congruential generators[C]// Systems, Signals and Image Processing (IWSSIP). 2012: 160-163.
[13]	NIVASCH G . Experimental results on hamiltonian-cycle-finding algorithms[R]. Weizman Institute, Israel, 2003.
[14]	柏森，杨晓帆 . 求马步图 Hamilton 圈的最优算法[J]. 计算机工程与科学， 2000, 22 (2): 8-11.
	BAI S , YANG X F . An optimal algorithm for searching a Hamilton cycle of the knight-tour's problem[J]. Computer Engineering＆Science, 2000, 22 (2): 8-11.
[15]	DEMAIO J . Which chessboards have a closed knight's tour within the cube[J]. Journal of Combinatorics, 2007, 14 (2): 1-9.
[16]	BAI S , LIAO X F , QU X H , et al. Generalized knight's tour prob-lem and its solutions algorithm[C]// 2006 International Conference on Computational Intelligence and Security. 2006: 570-573.
[17]	SIVAKUMAR T , VENKATESAN R . A novel approach for image encryption using dynamic scan pattern[J]. IAENG International Journal of Computer Science, 2014, 41 (2): 91-101.
[18]	RUKHIN A , SOTO J , NECHVATAL J , et al. A statistical test suite for random and pseudorandom number generators for cryptographic applications[R]. Booz-Allen and Hamilton Inc Mclean Va, 2001.

棋盘大小	0的数量/个	1的数量/个	1占的比例
20×20	397	397	50％
20×35	694	694	50％
25×55	1 369	1 368	49.98％
40×10	397	397	50％

测试项目	1组测试值	2组测试值	3组测试值	4组测试值	5组测试值
Frequency Test	1.000 0	1.000 0	1.000 0	1.000 0	1.000 0
Frequency Test within a Block	0.986 7	0.777 3	0.390 0	0.956 7	0.876 1
Runs Test	0.747 4	0.747 4	0.747 4	0.747 4	0.747 4
Test for the Longest of Ones in a Block	0.035 4	0.870 7	0.972 7	0.576 8	0.968 4
Discrete Fourier Transform Test	0.072 2	0.506 0	0.748 8	0.247 0	0.506 0
Linear Complexity Test	0.808 8	0.423 2	0.000 04	0.985 6	0.676 7
	0.709 4	0.995 3	0.499 0	0.355 3	0.865 9
Serial Test
	0.742 1	0.998 8	0.096 5	0.742 1	0.941 8
Approximate Entropy Test	0.780 4	0.232 0	0.332 8	0.555 6	0.459 7
	0.878 4	0.785 7	0.376 7	0.810 1	0.934 9
Cumulative Sums Test
	0.878 4	0.785 7	0.376 7	0.810 1	0.934 9
OverlappingTemplate	0.488 4	0.886 6	0.886 6	0.488 4	0.488 4
Rank	0.291 9	0.693 7	0.291 9	0.693 7	0.291 9

测试项目	本文算法	文献[ 10 ]算法
Frequency Test	1.000	0.712
Frequency Test within a Block	0.797	0.699
Runs Test	0.747	0.259
Test for the Longest of Ones in a
	0.685	0.284
Block
Discrete Fourier Transform Test	0.416	0.266
Linear Complexity Test	0.579	0.924
	0.685	0.584
Serial Test
	0.704	0.682
Approximate Entropy Test	0.472	0.54
	0.757	0.719
Cumulative Sums Test
	0.757	0.728

基于随机序列统计特性的伪随机序列生成方法

Method to generate the pseudo random sequence based on the statistical properties

在线阅读

pdf下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 12

参考文献 18

相关文章 0

Metrics

推荐阅读 0

棋盘大小	l=1	l=2	l=3	l=4	l=5	l=6	l=7	l=8	l=9
20×20	200	100	50	26	12	6	4	2	-
20×35	350	176	88	44	22	10	6	2	2