基于不同产生机制的伪随机序列和DNA序列的随机性测量

张巍琼, 郑智捷

（1.云南大学软件学院信息安全系,云南昆明 650091;2.云南省软件工程重点实验室,云南昆明 650091）

0 引言

如今,网络安全问题已经成为国家安全问题[1]。而随机性作为香农理论[2]的一个重要思想,在密码学领域中得到了充分的体现和应用,是密码学安全性的基础。正如密码学家Bruce Schneier所言,随机序列是谈论最少的密码学问题,但没有哪个问题比这个问题更重要[3]。

对于网络通信而言,实现一个有弹性的伪随机序列生成器非常必要[4],它可以用来产生会话密钥、时间戳、认证挑战码、初始向量[5]。NIST标准发布了AES加密算法,取代当前使用的DES算法,它们都可以作为伪随机数生成器的基础算法。另外,生物学上,有些学者认为核苷酸序列具有近似的随机性[6]。

文中致力于比较不同产生机制生成序列的随机性检测结果,为网络通信安全的研究提供一定的参考。讨论的伪随机数生成器以单一的TDES和AES算法实现的伪随机数生成器为基础,并做相应修改,形成结构更加复杂的3-TDES机制和3-AES机制,用来生成伪随机序列。而DNA序列转换机制则用来形成0-1序列,方便观察碱基序列的随机性。最后选用的随机性检验方法是NIST标准[7]中的单比特频数检测方法。此外,评价方式统一采用P-value,该方式对于长序列更加方便和准确。通过观察不同伪随机序列的测量模型和可视化模型,结果就显而易见了。

1 生成伪随机序列的基本方法

理论上,要求伪随机数产生器具备以下特征:良好的统计分布特性,高效率的伪随机数产生,伪随机数产生的循环周期足够长,产生机制可移植性好和伪随机数可重复产生。其中满足良好的统计性质是最重要的。

伪随机数生成器首先实现1轮三重DES（TDES）的产生机制,如图1（a）所示,结构简单,其中TDES的加密过程为EDE模式,使用两个密钥K1和K2对数据进行加密。接着使用3个TDES作为加密机制,加入异或操作,产生一定长度的伪随机序列,其中PRNi=EK（EK（Ti）⊕Vi）,Vi+1=EK（EK（Ti）⊕PRNi）,随机种子Seedi由时间种子Ti和自定义种子Vi组成,如图1（b）所示。然后对AES算法做类似处理,分别实现1个AES的简化机制和3个AES的复杂机制。比较这些不同算法实现的伪随机数生成器的优缺点。最终将它们与DNA序列转换机制对比,以更全面评价它们的性能。基于4种不同产生机制的伪随机数生成器的逻辑结构以及DNA序列转换机制结构分别如图1所示。

图1 PRNG逻辑结构和DNA序列转换结构

伪随机数生成器的核心部件是产生器,产生器主要由3部分组成:

（1）输入:伪随机数的种子Seed,初值可为任意值,生成随机数的过程中自动更新;

（2）密钥:TDES加密算法使用一个56位的密钥对K1、K2,AES加密算法使用一个128位的密钥K,密钥保密且在产生随机数时使用;

（3）输出:一个伪随机数PRNj和一个新种子Seedi。

DNA序列按照某一碱基替换规则将AGTC逐一替换成0-1序列,与伪随机序列统一。

2 不同随机序列的测量模式

使用上述基于TDES、3-TDES、AES、3-AES的随机数生成器产生了一系列随机数。由于肉眼观察很难确定其随机性,因此,使用单频数检测方法对其进行随机性检测。它流程简单,过程清晰,用于检测二元序列中0和1的个数是否近似相等,并计算P-value,若P-Value不小于α（α一般的取值范围是[0.001,0.01]）,则待检序列通过单比特频数检测。

最后,用该方法对DNA序列进行随机性检测,并将所有的检测结果与P-value的频数分布直方图交叉比较,以便观察各个伪随机数生成器的性能以及伪随机序列与DNA序列的随机性分布特征。其测量模型和操作流程如图2所示。

图2 随机性检测

3 典型结果

3.1 测量序列

分别用4种伪随机数生成器产生3组伪随机数。另外,还选择了水稻、玉米、小麦3种植物DNA序列和马、老鼠、牛3种动物DNA序列,分别代表植物基因和动物基因。先按碱基替换规则“A～11 T～00 G～10 C～01”处理DNA序列,再用类似的方法对其进行随机性检测。其中1组伪随机数的部分检测结果以及两组DNA序列的部分检测结果如图3所示,Y/N表示是否通过单频数检测。

图3 单频数检测结果

从上述几种随机数生成器产生的随机序列的单频数检测结果得知,当序列分段足够小的时候,基于TDES的3组数据和基于3-TDES的3组数据各自有1段显示N,基于3-AES的3组数据有2段显示N,即未通过检测;基于AES的3组数据全部通过检测;而植物和动物DNA序列也有几段显示未通过检测。

3.2 测量图示

为了使检测结果更加直观,使用MATLAB绘制P-Value的可视化频数分布直方图,交叉比较基于不同产生机制的各个随机序列的分布特性。如图4所示。

观察比较图4,可以得知每个直方图中P-value都均匀分布在整个空间。很明显,图4（d）的3组数据的P-value在0～0.1区间分布最密集,（a）、（b）图以及（e）图的玉米DNA序列和（f）图的后两组序列具有类似特点,即P-value在0～0.1区间的分布相对较密集。而其他诸如（c）、（e）图的P-value分布特征相似,即在0～0.1区间的分布相对较疏散。

图4 P-value频数分布直方图

4 分析比较

观察图3和图4,1轮TDES和3轮TDES具有类似的随机特征,而对于1轮AES与3轮AES,后者随机性弱于前者。因此,尽管基于3轮AES的实现结构比1轮AES更复杂,但它所产生的随机序列并没有表现出预期的更强随机性。TDES与AES相比,基于AES的产生机制也没有表现出明显的优势。

以上伪随机数生成器大致可以分为2类,即基于TDES和基于AES。从宏观上看,两类机制生成的随机序列都呈现出令人满意的结果,一定程度上说明基于密码学的伪随机数生成器是有效的。然而,进一步的比较显示,复杂的结构或算法并不一定能增强随机性,也就是说增加复杂性不一定能换来更好的性能。

观察从生物系中挑选出的几种代表性植物和动物的DNA序列的分布特征,可以看到DNA序列经转换机制形成的0-1序列大体上都具有较好的随机性。由此可知,无论是伪随机数序列还是DNA序列,都可以为相关领域的深入研究提供参考。

5 结束语

主要通过密码学中的分组密码体制实现了基于 TDES、3-TDES、AES以及3-AES 4种不同产生机制的伪随机数生成器,并用DNA转换机制形成了0-1序列。采用单频数分段检测方法对上述所有0-1序列进行随机性检测,检测结果以直方图的形式呈现。P-value频数分布直方图从可视化角度形象而直观地展示了不同随机序列的随机性分布特征。无论是基于密码学的伪随机数生成器还是DNA序列转换机制,都具有一定的研究价值。

致谢:感谢陈冠良老师在英语翻译方面的帮助,感谢云南大学软件学院以及云南省软件工程重点实验室对信息安全研究项目的基金支持。

[1] Kemmerer R A.cybersecurity,Software Engineering[C].Proceedings.25th International Conference on,2003:705-715.

[2] Shannon C E.A mathematical theory of communication[J].Bell System Technical Journal,1948,27:379-429,623-656.

[3] Schneier B.Secretsand lies:Digital security in networked world[M].New York:Jone Wiley and Sons,2000:85-101.

[4] Zheng Z J.Novel Pseudo-random Number Generation Using variant logic Framework[C].Proceedings of the 2nd International Cyber Resilience Conference,2011:100-104.

[5] Shannon C E.Communication theory of secrecy systems[J].Bell System Technical Journal,1949,28（4）:656-715.

[6] Azbel M Y,Kantor Y,Verkh L.Statistical analysis of DNA sequences[J].I.Biopolymers,1982,21:1687-1690.

[7] The NIST SP 800-90 Deterministic Random Bit Generator Validation System（DRBGVS）,NIST SP 800-90,National Institute of Standards and Technology[S].2011.

[8] Knuth D.The Art of Computer Programming[M].Seminumerical Algorithms.Reading,MA:Addition-Wisely.1998.

[9] NIST.FIPS PUB 140-2,Security requirements for cryptographic modules[S].2001.

[10] Lucks S.Attacking Seven Rounds of Rijndael Under 192-bit and 256 bit Keys[C].In:Proceedings of the Third Advanced Encryption Standard Conference,2000:242-246.

[11] Li C Y,Chang T Y,Huang C C.A nonlinear PRNG using digitized logistic map with self-reseeding method[C]//Proceedings ofthe International Symposium on VLSI Design Automation and Test（VLSI-DAT）,2010:108-111.

[12] Wan J,Zheng Z J.Showing exhaustive number sequences of two logic variables for variant logic functional space[C].Proceedings of Asia-Pacific Youth Conference on Communication,2010:69-73.

[13] Li Q,Zheng Z J.Spacial Distributions for Measures of Random Sequences Using 2D Conjugate Maps[C].Proceedings of Asia-Pacific Youth Conference on Communication,2010:64-68.

[14] Li Q,Zheng Z J.2D Spatial Distributions for Measures of Random Sequences Using Conjugate Maps[C].Proceedings of the 11th Australian Information Warfare and Security Conference,2010:18-25.

[15] Li S,Tian X.Nonlinear study and complexity study[D].Harbin Institute of Technology Press,2006.

[16] Shi G D,Kang F,Gu H W.Research and Implementation of Randomness Tests[J].Computer Engineering,2009,35（20）:145-147.

[17] Chen Q,Deng Q N.Cloud computing and its key techniques[J].Journal of Computer Applications,2009,29（9）:2563-2567.

[18] Zhang J X,Ji Z M,Zheng C.Survey of research progress on cloud computing[J].Application Research of Computer,2010,27（2）:429-433.