楊濤瑞

（重慶育才中學(xué)，重慶 400050）

1 引言

偽隨機(jī)序列是一種具有類(lèi)似白噪聲性質(zhì)的序列，在信息安全領(lǐng)域和擴(kuò)頻通信領(lǐng)域中都起著非常重要的作用。從某種意義上講，偽隨機(jī)序列的安全性確定了整個(gè)密碼體系的安全性。因此如何得到高質(zhì)量的偽隨機(jī)序列成為信息安全熱點(diǎn)研究問(wèn)題[1，2，4]。

如果一個(gè)序列是偽隨機(jī)的，它至少應(yīng)具有如下性質(zhì)[1，2，4]：

（1）看起來(lái)是隨機(jī)的，即能通過(guò)已知的所有正確的隨機(jī)性檢驗(yàn)。

（2）是不可預(yù)測(cè)的，也就是說(shuō)，即使給出產(chǎn)生序列的算法或者硬件設(shè)計(jì)和以前產(chǎn)生序列的所有知識(shí)，也不可能通過(guò)計(jì)算來(lái)預(yù)測(cè)下一個(gè)隨機(jī)位是什么值。

在本文，一種新的基于混沌迭代映射的偽隨機(jī)序列生成算法被提出來(lái)了。在該方法中，通過(guò)對(duì)迭代函數(shù)輸出值和該輸出值所在的區(qū)間下標(biāo)進(jìn)行異或運(yùn)算，從而得到一個(gè)長(zhǎng)度為n比特的偽隨機(jī)序列。

本文其余部分是按如下方式組織的：第2節(jié)描述了偽隨機(jī)序列的生成算法，第3節(jié)利用NIST提供的隨機(jī)性檢驗(yàn)方法對(duì)生成的偽隨機(jī)序列進(jìn)行了隨機(jī)性檢驗(yàn)；最后在第4節(jié)對(duì)算法進(jìn)行了總結(jié)。

2 偽隨機(jī)序列的生成

2.1 混沌迭代函數(shù)的選擇

分段線性混沌迭代函數(shù)具有良好隨機(jī)統(tǒng)計(jì)特性，其定義如下：

p是控制參數(shù)，且p∈（0，1/2）。該混沌映射在區(qū)間[0，1]上具有較好的統(tǒng)計(jì)特性：輸出值滿足遍歷各態(tài)性、混和性和確定性。

2.2 定義新運(yùn)算“異和”

2.3 偽隨機(jī)序列的生成

本文設(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）就得到了。

3 偽隨機(jī)序列的隨機(jī)性測(cè)試

建立在假設(shè)檢驗(yàn)基礎(chǔ)上的隨機(jī)性測(cè)試是一種重要的測(cè)試方法，假設(shè)檢驗(yàn)是一類(lèi)重要的統(tǒng)計(jì)推斷問(wèn)題，它依據(jù)小概率原理，即如果一個(gè)事件在現(xiàn)有假設(shè)下發(fā)生的概率很小，那么一旦這一事件發(fā)生，則認(rèn)為該假設(shè)成立，則我們接受這種假設(shè)。

美國(guó)國(guó)家技術(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)通過(guò)率大于等于98.056%時(shí)則認(rèn)為通過(guò)了該項(xiàng)隨機(jī)性檢驗(yàn)。

實(shí)驗(yàn)過(guò)程中，我們生成了1000組長(zhǎng)度為1，000，000比特的位序列。用STS工具軟件檢測(cè)，實(shí)驗(yàn)結(jié)果如下（表1）。表中的實(shí)驗(yàn)數(shù)據(jù)每一測(cè)試項(xiàng)的通過(guò)率均大于98.056%，表明算法產(chǎn)生的偽隨機(jī)序列通過(guò)了所有的隨機(jī)性測(cè)試，即可以認(rèn)為算法所產(chǎn)生的偽隨機(jī)序列有較好的隨機(jī)性。

表1 隨機(jī)性測(cè)試

重疊塊匹配測(cè)試 0.98789 98.57 通過(guò)全局通用統(tǒng)計(jì)測(cè)試 0.67624 98.84 通過(guò)線性復(fù)雜度測(cè)試 0.49344 99.17 通過(guò)串行測(cè)試 0.68725 99.20 通過(guò)近似熵測(cè)試 0.02507 99.09 通過(guò)累積和測(cè)試 0.80439 99.27 通過(guò)隨機(jī)游程測(cè)試 0.46983 99.13 通過(guò)隨機(jī)游程變體測(cè)試 0.38332 98.46 通過(guò)

4 結(jié)束語(yǔ)

本文提出了一種新的偽隨機(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í)間效率問(wèn)題。

[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 著.馮登國(guó)譯.密碼學(xué)原理與實(shí)踐[M].北京：電子工業(yè)出版社，2003.