楊濤瑞
(重慶育才中學(xué),重慶 400050)
偽隨機(jī)序列是一種具有類似白噪聲性質(zhì)的序列,在信息安全領(lǐng)域和擴(kuò)頻通信領(lǐng)域中都起著非常重要的作用。從某種意義上講,偽隨機(jī)序列的安全性確定了整個(gè)密碼體系的安全性。因此如何得到高質(zhì)量的偽隨機(jī)序列成為信息安全熱點(diǎn)研究問題[1,2,4]。
如果一個(gè)序列是偽隨機(jī)的,它至少應(yīng)具有如下性質(zhì)[1,2,4]:
(1)看起來是隨機(jī)的,即能通過已知的所有正確的隨機(jī)性檢驗(yàn)。
(2)是不可預(yù)測(cè)的,也就是說,即使給出產(chǎn)生序列的算法或者硬件設(shè)計(jì)和以前產(chǎn)生序列的所有知識(shí),也不可能通過計(jì)算來預(yù)測(cè)下一個(gè)隨機(jī)位是什么值。
在本文,一種新的基于混沌迭代映射的偽隨機(jī)序列生成算法被提出來了。在該方法中,通過對(duì)迭代函數(shù)輸出值和該輸出值所在的區(qū)間下標(biāo)進(jìn)行異或運(yùn)算,從而得到一個(gè)長度為n比特的偽隨機(jī)序列。
本文其余部分是按如下方式組織的:第2節(jié)描述了偽隨機(jī)序列的生成算法,第3節(jié)利用NIST提供的隨機(jī)性檢驗(yàn)方法對(duì)生成的偽隨機(jī)序列進(jìn)行了隨機(jī)性檢驗(yàn);最后在第4節(jié)對(duì)算法進(jìn)行了總結(jié)。
分段線性混沌迭代函數(shù)具有良好隨機(jī)統(tǒng)計(jì)特性,其定義如下:
p是控制參數(shù),且p∈(0,1/2)。該混沌映射在區(qū)間[0,1]上具有較好的統(tǒng)計(jì)特性:輸出值滿足遍歷各態(tài)性、混和性和確定性。
本文設(shè)計(jì)一種偽隨機(jī)序列生成算法,其原理框圖如圖1所示。
步驟1:將區(qū)間[0,1]劃分為等距的256個(gè)子區(qū)間,記為Δi,i=0,1 255。每個(gè)區(qū)間的取值范圍是 [i·2-8,(i+1)·2-8]。
步驟2:根據(jù)給定的初始值x0,控制參數(shù)p和初始迭代次數(shù)N0,迭代映射F(x0,p),得到輸出xi。
步驟3:比較xi與步驟1的各個(gè)子區(qū)間,記下xi落入子區(qū)間 Δi的下標(biāo) i。
圖1 偽隨機(jī)序列生成框圖
步驟4:將十進(jìn)制數(shù)xi轉(zhuǎn)化為二進(jìn)制形式,取其小數(shù)點(diǎn)后8位并將其倒排;將步驟3得到的i也表示為8位的二進(jìn)制形式。然后將這兩個(gè)二進(jìn)制形式的8位進(jìn)行按位異或運(yùn)算,得到一個(gè)8位的輸出比特流,記為φi。
步驟5:將φi除以128得到的余數(shù)賦給N0(如果余數(shù)為0,則將128賦給N0),作為計(jì)算下一個(gè)8位輸出比特流時(shí)函數(shù)的迭代次數(shù)。
重復(fù)步驟2~步驟5若干次,一個(gè)期望的偽隨機(jī)序列(φ1,φ2, φn)就得到了。
建立在假設(shè)檢驗(yàn)基礎(chǔ)上的隨機(jī)性測(cè)試是一種重要的測(cè)試方法,假設(shè)檢驗(yàn)是一類重要的統(tǒng)計(jì)推斷問題,它依據(jù)小概率原理,即如果一個(gè)事件在現(xiàn)有假設(shè)下發(fā)生的概率很小,那么一旦這一事件發(fā)生,則認(rèn)為該假設(shè)成立,則我們接受這種假設(shè)。
美國國家技術(shù)與標(biāo)準(zhǔn)局(NIST)推出的STS(Statistical Test Suite)是當(dāng)前偽隨機(jī)性測(cè)試中最具權(quán)威的工具,其中給出了16種隨機(jī)序列測(cè)試的方法,其顯著性水平a∈[0.001,0.01]。當(dāng)每組隨機(jī)性檢測(cè)的概率值(p-value)大于a,即p-value> a則接收該假設(shè),反之則拒絕。根據(jù)NIST的建議,當(dāng)通過率大于等于98.056%時(shí)則認(rèn)為通過了該項(xiàng)隨機(jī)性檢驗(yàn)。
實(shí)驗(yàn)過程中,我們生成了1000組長度為1,000,000比特的位序列。用STS工具軟件檢測(cè),實(shí)驗(yàn)結(jié)果如下(表1)。表中的實(shí)驗(yàn)數(shù)據(jù)每一測(cè)試項(xiàng)的通過率均大于98.056%,表明算法產(chǎn)生的偽隨機(jī)序列通過了所有的隨機(jī)性測(cè)試,即可以認(rèn)為算法所產(chǎn)生的偽隨機(jī)序列有較好的隨機(jī)性。
表1 隨機(jī)性測(cè)試
重疊塊匹配測(cè)試 0.98789 98.57 通過全局通用統(tǒng)計(jì)測(cè)試 0.67624 98.84 通過線性復(fù)雜度測(cè)試 0.49344 99.17 通過串行測(cè)試 0.68725 99.20 通過近似熵測(cè)試 0.02507 99.09 通過累積和測(cè)試 0.80439 99.27 通過隨機(jī)游程測(cè)試 0.46983 99.13 通過隨機(jī)游程變體測(cè)試 0.38332 98.46 通過
本文提出了一種新的偽隨機(jī)序列生成方法,并用NIST提供的STS軟件包對(duì)所產(chǎn)生的偽隨機(jī)序列進(jìn)行了隨機(jī)性測(cè)試,實(shí)驗(yàn)表明該方法產(chǎn)生的偽隨機(jī)序列具有較好的隨機(jī)性。由于在將十進(jìn)制小數(shù)轉(zhuǎn)化為二進(jìn)制時(shí)采用了 乘二取整 的經(jīng)典算法,導(dǎo)致其時(shí)間效率很低,今后我們將繼續(xù)探究如何提高生成序列的時(shí)間效率問題。
[1] 金晨輝,鄭浩然,張少武等.密碼學(xué)[M].北京:高等教育出版社,2010.
[2] 廖曉峰,肖迪,陳勇等著.漏沖密碼學(xué)原理及其應(yīng)用[M].北京:科學(xué)出版社,2009.
[3] NIST Special Publication 800-22rev1a,http://csrc.nist.gov/groups/ST/toolkit/rng/index.html.
[4] Douglas R.Stinson 著.馮登國譯.密碼學(xué)原理與實(shí)踐[M].北京:電子工業(yè)出版社,2003.