基于不同產(chǎn)生機制的偽隨機序列和DNA序列的隨機性測量

張巍瓊, 鄭智捷

（1.云南大學軟件學院信息安全系,云南昆明 650091;2.云南省軟件工程重點實驗室,云南昆明 650091）

0 引言

如今,網(wǎng)絡(luò)安全問題已經(jīng)成為國家安全問題[1]。而隨機性作為香農(nóng)理論[2]的一個重要思想,在密碼學領(lǐng)域中得到了充分的體現(xiàn)和應(yīng)用,是密碼學安全性的基礎(chǔ)。正如密碼學家Bruce Schneier所言,隨機序列是談?wù)撟钌俚拿艽a學問題,但沒有哪個問題比這個問題更重要[3]。

對于網(wǎng)絡(luò)通信而言,實現(xiàn)一個有彈性的偽隨機序列生成器非常必要[4],它可以用來產(chǎn)生會話密鑰、時間戳、認證挑戰(zhàn)碼、初始向量[5]。NIST標準發(fā)布了AES加密算法,取代當前使用的DES算法,它們都可以作為偽隨機數(shù)生成器的基礎(chǔ)算法。另外,生物學上,有些學者認為核苷酸序列具有近似的隨機性[6]。

文中致力于比較不同產(chǎn)生機制生成序列的隨機性檢測結(jié)果,為網(wǎng)絡(luò)通信安全的研究提供一定的參考。討論的偽隨機數(shù)生成器以單一的TDES和AES算法實現(xiàn)的偽隨機數(shù)生成器為基礎(chǔ),并做相應(yīng)修改,形成結(jié)構(gòu)更加復雜的3-TDES機制和3-AES機制,用來生成偽隨機序列。而DNA序列轉(zhuǎn)換機制則用來形成0-1序列,方便觀察堿基序列的隨機性。最后選用的隨機性檢驗方法是NIST標準[7]中的單比特頻數(shù)檢測方法。此外,評價方式統(tǒng)一采用P-value,該方式對于長序列更加方便和準確。通過觀察不同偽隨機序列的測量模型和可視化模型,結(jié)果就顯而易見了。

1 生成偽隨機序列的基本方法

理論上,要求偽隨機數(shù)產(chǎn)生器具備以下特征:良好的統(tǒng)計分布特性,高效率的偽隨機數(shù)產(chǎn)生,偽隨機數(shù)產(chǎn)生的循環(huán)周期足夠長,產(chǎn)生機制可移植性好和偽隨機數(shù)可重復產(chǎn)生。其中滿足良好的統(tǒng)計性質(zhì)是最重要的。

偽隨機數(shù)生成器首先實現(xiàn)1輪三重DES（TDES）的產(chǎn)生機制,如圖1（a）所示,結(jié)構(gòu)簡單,其中TDES的加密過程為EDE模式,使用兩個密鑰K1和K2對數(shù)據(jù)進行加密。接著使用3個TDES作為加密機制,加入異或操作,產(chǎn)生一定長度的偽隨機序列,其中PRNi=EK（EK（Ti）⊕Vi）,Vi+1=EK（EK（Ti）⊕PRNi）,隨機種子Seedi由時間種子Ti和自定義種子Vi組成,如圖1（b）所示。然后對AES算法做類似處理,分別實現(xiàn)1個AES的簡化機制和3個AES的復雜機制。比較這些不同算法實現(xiàn)的偽隨機數(shù)生成器的優(yōu)缺點。最終將它們與DNA序列轉(zhuǎn)換機制對比,以更全面評價它們的性能。基于4種不同產(chǎn)生機制的偽隨機數(shù)生成器的邏輯結(jié)構(gòu)以及DNA序列轉(zhuǎn)換機制結(jié)構(gòu)分別如圖1所示。

圖1 PRNG邏輯結(jié)構(gòu)和DNA序列轉(zhuǎn)換結(jié)構(gòu)

偽隨機數(shù)生成器的核心部件是產(chǎn)生器,產(chǎn)生器主要由3部分組成:

（1）輸入:偽隨機數(shù)的種子Seed,初值可為任意值,生成隨機數(shù)的過程中自動更新;

（2）密鑰:TDES加密算法使用一個56位的密鑰對K1、K2,AES加密算法使用一個128位的密鑰K,密鑰保密且在產(chǎn)生隨機數(shù)時使用;

（3）輸出:一個偽隨機數(shù)PRNj和一個新種子Seedi。

DNA序列按照某一堿基替換規(guī)則將AGTC逐一替換成0-1序列,與偽隨機序列統(tǒng)一。

2 不同隨機序列的測量模式

使用上述基于TDES、3-TDES、AES、3-AES的隨機數(shù)生成器產(chǎn)生了一系列隨機數(shù)。由于肉眼觀察很難確定其隨機性,因此,使用單頻數(shù)檢測方法對其進行隨機性檢測。它流程簡單,過程清晰,用于檢測二元序列中0和1的個數(shù)是否近似相等,并計算P-value,若P-Value不小于α（α一般的取值范圍是[0.001,0.01]）,則待檢序列通過單比特頻數(shù)檢測。

最后,用該方法對DNA序列進行隨機性檢測,并將所有的檢測結(jié)果與P-value的頻數(shù)分布直方圖交叉比較,以便觀察各個偽隨機數(shù)生成器的性能以及偽隨機序列與DNA序列的隨機性分布特征。其測量模型和操作流程如圖2所示。

圖2 隨機性檢測

3 典型結(jié)果

3.1 測量序列

分別用4種偽隨機數(shù)生成器產(chǎn)生3組偽隨機數(shù)。另外,還選擇了水稻、玉米、小麥3種植物DNA序列和馬、老鼠、牛3種動物DNA序列,分別代表植物基因和動物基因。先按堿基替換規(guī)則“A～11 T～00 G～10 C～01”處理DNA序列,再用類似的方法對其進行隨機性檢測。其中1組偽隨機數(shù)的部分檢測結(jié)果以及兩組DNA序列的部分檢測結(jié)果如圖3所示,Y/N表示是否通過單頻數(shù)檢測。

圖3 單頻數(shù)檢測結(jié)果

從上述幾種隨機數(shù)生成器產(chǎn)生的隨機序列的單頻數(shù)檢測結(jié)果得知,當序列分段足夠小的時候,基于TDES的3組數(shù)據(jù)和基于3-TDES的3組數(shù)據(jù)各自有1段顯示N,基于3-AES的3組數(shù)據(jù)有2段顯示N,即未通過檢測;基于AES的3組數(shù)據(jù)全部通過檢測;而植物和動物DNA序列也有幾段顯示未通過檢測。

3.2 測量圖示

為了使檢測結(jié)果更加直觀,使用MATLAB繪制P-Value的可視化頻數(shù)分布直方圖,交叉比較基于不同產(chǎn)生機制的各個隨機序列的分布特性。如圖4所示。

觀察比較圖4,可以得知每個直方圖中P-value都均勻分布在整個空間。很明顯,圖4（d）的3組數(shù)據(jù)的P-value在0～0.1區(qū)間分布最密集,（a）、（b）圖以及（e）圖的玉米DNA序列和（f）圖的后兩組序列具有類似特點,即P-value在0～0.1區(qū)間的分布相對較密集。而其他諸如（c）、（e）圖的P-value分布特征相似,即在0～0.1區(qū)間的分布相對較疏散。

圖4 P-value頻數(shù)分布直方圖

4 分析比較

觀察圖3和圖4,1輪TDES和3輪TDES具有類似的隨機特征,而對于1輪AES與3輪AES,后者隨機性弱于前者。因此,盡管基于3輪AES的實現(xiàn)結(jié)構(gòu)比1輪AES更復雜,但它所產(chǎn)生的隨機序列并沒有表現(xiàn)出預(yù)期的更強隨機性。TDES與AES相比,基于AES的產(chǎn)生機制也沒有表現(xiàn)出明顯的優(yōu)勢。

以上偽隨機數(shù)生成器大致可以分為2類,即基于TDES和基于AES。從宏觀上看,兩類機制生成的隨機序列都呈現(xiàn)出令人滿意的結(jié)果,一定程度上說明基于密碼學的偽隨機數(shù)生成器是有效的。然而,進一步的比較顯示,復雜的結(jié)構(gòu)或算法并不一定能增強隨機性,也就是說增加復雜性不一定能換來更好的性能。

觀察從生物系中挑選出的幾種代表性植物和動物的DNA序列的分布特征,可以看到DNA序列經(jīng)轉(zhuǎn)換機制形成的0-1序列大體上都具有較好的隨機性。由此可知,無論是偽隨機數(shù)序列還是DNA序列,都可以為相關(guān)領(lǐng)域的深入研究提供參考。

5 結(jié)束語

主要通過密碼學中的分組密碼體制實現(xiàn)了基于 TDES、3-TDES、AES以及3-AES 4種不同產(chǎn)生機制的偽隨機數(shù)生成器,并用DNA轉(zhuǎn)換機制形成了0-1序列。采用單頻數(shù)分段檢測方法對上述所有0-1序列進行隨機性檢測,檢測結(jié)果以直方圖的形式呈現(xiàn)。P-value頻數(shù)分布直方圖從可視化角度形象而直觀地展示了不同隨機序列的隨機性分布特征。無論是基于密碼學的偽隨機數(shù)生成器還是DNA序列轉(zhuǎn)換機制,都具有一定的研究價值。

致謝:感謝陳冠良老師在英語翻譯方面的幫助,感謝云南大學軟件學院以及云南省軟件工程重點實驗室對信息安全研究項目的基金支持。

[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.