一種組合式偽隨機數(shù)發(fā)生器的構(gòu)造

韓露露，楊 波，來齊齊，曹艷艷

(陜西師范大學(xué) 計算機科學(xué)學(xué)院，西安 710119) (中國科學(xué)院信息工程研究所 信息安全國家重點實驗室，北京 100093)

1 引 言

隨機數(shù)發(fā)生器分為真隨機數(shù)發(fā)生器和偽隨機數(shù)發(fā)生器，它們均可采用軟件和硬件來實現(xiàn).然而，真隨機數(shù)發(fā)生器[1]由于多采用價格高昂的硬件才可以實現(xiàn)且存在對熵源的要求高和產(chǎn)生隨機數(shù)的效率低等缺點，因此偽隨機數(shù)發(fā)生器一直以來是研究的熱點.

偽隨機序列(Pseudorandom Sequence)在計算機仿真學(xué)、信息加密、會話密鑰的產(chǎn)生、協(xié)議認證等諸多領(lǐng)域都有廣泛的應(yīng)用.尤其是在密碼學(xué)領(lǐng)域，要求偽隨機數(shù)發(fā)生器能夠產(chǎn)生與真隨機序列在計算上不可區(qū)分的序列[2]，偽隨機數(shù)發(fā)生器是實現(xiàn)對稱加密、非對稱加密、數(shù)字簽名、數(shù)據(jù)完整性等的技術(shù)基礎(chǔ).

偽隨機數(shù)發(fā)生器的構(gòu)造方法有很多.例如，可以基于分組密碼、序列密碼、混沌、數(shù)論等方法構(gòu)造偽隨機數(shù)發(fā)生器[3].然而，基于組合式的偽隨機數(shù)發(fā)生器具備構(gòu)造簡單和對已有的偽隨機數(shù)發(fā)生器統(tǒng)計特性改善明顯的特點.文獻[4]通過對組合法的深入研究得出結(jié)論：幾個獨立且近似均勻的隨機序列能線性組合成一個接近U(0,1)分布的隨機序列.文獻[5]對組合的線性同余發(fā)生器的不可預(yù)測性進行了研究.

LCG[6]算法和RC4[7]算法因其高效性，近年來人們不斷地對其進行研究和改進.Chefranov[8]在06年提出一種改善RC4算法周期的方法.Shen[9]在09年通過對線性同余發(fā)生器作位操作來達到改善隨機序列統(tǒng)計品質(zhì)的目的.Rivest[10]通過對RC4算法的深入分析在14年設(shè)計了一種類似RC算法的流密碼Spritz.然而，關(guān)于RC4算法的安全性一直以來都備受爭議[11,12].2015年IETF(Internet Engineering Task Force)聲稱RC4算法已經(jīng)不再安全[13].

鑒于RC4算法高效的特點和專門設(shè)計一款偽隨機數(shù)發(fā)生器的困難性.本文采用組合法以LCG算法和RC4算法為數(shù)據(jù)的生成源，以安全的密碼學(xué)Hash函數(shù)[14,15]為數(shù)據(jù)處理算法設(shè)計了一個具備一定密碼學(xué)強度的組合式偽隨機數(shù)發(fā)生器.該組合式偽隨機數(shù)發(fā)生器每產(chǎn)生一個512比特的隨機數(shù)后，就會對RC4算法當(dāng)前的內(nèi)部狀態(tài)進行置換.這種頻繁更新RC4內(nèi)部狀態(tài)的做法可提高其抗密碼分析能力.同時，密碼學(xué)Hash函數(shù)的單向性保證了該偽隨機數(shù)發(fā)生器產(chǎn)生的序列具備不可預(yù)測性[16,17].

2 預(yù)備知識

2.1 基本概念

至今，隨機數(shù)都沒有一個統(tǒng)一的定義，數(shù)學(xué)上的定義和概率論相關(guān)，計算復(fù)雜性理論則用描述該序列的程序長度來定義.在密碼學(xué)中，則結(jié)合統(tǒng)計特性和密碼攻擊來描述隨機數(shù)，按照性質(zhì)隨機數(shù)可以分為隨機性、不可預(yù)測性和不可重現(xiàn)性.

2.1.1 隨機性

常用以下兩個準(zhǔn)則描述序列的隨機性(Randomness)：

1)均勻分布：序列中每一個數(shù)列出現(xiàn)的頻率應(yīng)該相等或近似相等.

2)獨立性：序列中任意一個數(shù)列都不能由其他數(shù)推出.

2.1.2 不可預(yù)測性

已知一個序列的任意前綴序列，如果沒有有效的算法能以不可忽略的優(yōu)勢猜測到下一個數(shù)，則稱該序列具備不可預(yù)測性[18](Unpredictability).

2.1.3 不可重現(xiàn)性

如果除了將隨機數(shù)列本身保存下來以外，沒有其他方法能夠重現(xiàn)數(shù)列，則稱該隨機數(shù)列具備不可重現(xiàn)性.

2.1.4 偽隨機數(shù)發(fā)生器

偽隨機數(shù)發(fā)生器是一種確定性算法，給它一個短的真隨機輸入，產(chǎn)生一個更長的、和真隨機序列非常接近的隨機序列.稱其輸入為種子(Seed)，輸出為偽隨機序列[3].

2.2 組合式隨機數(shù)發(fā)生器理論

組合法是指將兩個或者兩個以上獨立的偽隨機數(shù)發(fā)生器按照某種方式組合起來構(gòu)成一個新的偽隨機數(shù)發(fā)生器，以期望產(chǎn)生周期更長、統(tǒng)計性能更優(yōu)的偽隨機序列.這種發(fā)生器的組合方式很多，大體可以分為兩類.

第一類是1965年由Maclaren和Marsaglia共同提出的，先用一個偽隨機數(shù)發(fā)生器生成一組偽隨機序列，然后通過使用第二個偽隨機數(shù)發(fā)生器產(chǎn)生的隨機數(shù)對第一個偽隨機序列進行擾亂并重新排序，進而得到一個新的序列，其具體算法操作步驟為：

1)首先，用第一個發(fā)生器產(chǎn)生k個隨機數(shù)，并將這k個數(shù)順序地存放在矢量T={t1,t2,…,tk}中，同時置i=1;

2)用第2個發(fā)生器產(chǎn)生一個隨機整數(shù)j，j必須滿足j∈[1,k]；

3)令Xi=tj，然后再用第一個發(fā)生器生成下一個隨機數(shù)y，令tj=y，并置i=i+1；

4)重復(fù)2)-3)，即可得到組合的發(fā)生器生成的一個新的隨機數(shù)序列{Xi} .

第二類是首先每個偽隨機數(shù)發(fā)生器分別產(chǎn)生一個隨機序列，然后以此為基礎(chǔ)對兩個序列的元素進行運算(主要包括"+"、"-"以及"XOR"運算組合)，從而產(chǎn)生新的隨機序列.

3 本方案的設(shè)計說明

3.1 方案的整體描述

3.1.1 流程圖主要模塊的功能說明

下面對圖1中各模塊的主要功能進行說明：

1)RC4模塊(如圖1中①所標(biāo)識)：該模塊從外部獲得一個種子后，每對其調(diào)用一次就會產(chǎn)生一個字節(jié)的數(shù)據(jù).

圖1 方案的整體描述Fig.1 Overall description of the scheme

2)SHA-3 512模塊(如圖1中②所標(biāo)識)：該模塊把RC4算法產(chǎn)生的字節(jié)流當(dāng)做SHA-3 512的輸入，并將其產(chǎn)生的散列值作為輸出.這個過程每被執(zhí)行一次可以產(chǎn)生64個字節(jié)的數(shù)據(jù)，則對其執(zhí)行C次總共可以產(chǎn)生C×64字節(jié)的數(shù)據(jù).

3)LCG模塊(如圖1中③所標(biāo)識)：該模塊以RC4算法產(chǎn)生的字節(jié)流為參數(shù)對LCG算法的參數(shù)進行更新(在本方案中，更新參數(shù)的目的是使得模256的LCG算法達到滿周期[19])，參數(shù)更新后的LCG算法每被調(diào)用一次會產(chǎn)生一個字節(jié)的數(shù)據(jù)，對其連續(xù)調(diào)用64次以產(chǎn)生64個字節(jié)的數(shù)據(jù).這個過程被執(zhí)行C次，總共可以產(chǎn)生C×64字節(jié)的數(shù)據(jù).

3.1.2 流程圖的執(zhí)行過程說明

該PRNG輸入輸出規(guī)格說明：

1)輸入：種子的輸入長度范圍32(字節(jié))～256(字節(jié)).

2)輸出：該算法每被調(diào)用一次可產(chǎn)生64字節(jié)的隨機數(shù).

流程圖1的執(zhí)行過程：

1)首先，從外部獲得一個種子并將該種子賦給RC4算法.

2)調(diào)用RC4算法并將其產(chǎn)生的字節(jié)流分別作為LCG模塊和SHA-3 512模塊的輸入，經(jīng)過一系列的運算后，這兩個模塊分別輸出C×64字節(jié)的數(shù)據(jù)(如圖1中②和③所標(biāo)識)，接著將兩個模塊產(chǎn)生的數(shù)據(jù)按位進行異或得到C×64字節(jié)的數(shù)據(jù)(如圖1中④所標(biāo)識).

3)用SHA-3 512求上一步最終得到的C×64字節(jié)數(shù)據(jù)的散列值，并將該散列值作為本輪該PRNG算法產(chǎn)生的隨機數(shù)并輸出.

4)分別取第2步LCG模塊和SHA-3 512模塊輸出的第Q個64字節(jié)的數(shù)據(jù)，并將其轉(zhuǎn)換成大整數(shù)進行相加(如圖1中⑤所標(biāo)識)，同時將結(jié)果累加到PRNG的內(nèi)部計數(shù)器Couter(如圖1中⑥所標(biāo)識)上，然后用SHA-3 512求計數(shù)器Counter的散列值.然后，用求得的散列值對RC4算法當(dāng)前的內(nèi)部狀態(tài)進行置換.

5)重復(fù)第2步至第4步，直到得到所需數(shù)量的隨機數(shù).

3.1.3 方案用到的組合式思想說明

1)由3.1可知，LCG模塊的輸出是通過調(diào)用C個參數(shù)不同的LCG算法獲得，將這C組的輸出組合在一起可以改善單個LCG算法周期短的缺點.

2)在圖1中，將LCG模塊輸出的C×64字節(jié)的數(shù)據(jù)和SHA-3 512模塊輸出的C×64字節(jié)的數(shù)據(jù)進行異或，該操作不僅起到改善單個C×64字節(jié)統(tǒng)計特性的作用，還增加了整個PRNG的抗密碼分析能力.

3)在圖1中，該PRNG在產(chǎn)生第2個以及以后的第N個隨機數(shù)之前，首先會利用SHA-3 512求得的PRNG內(nèi)部計數(shù)器Counter的散列值，然后利用該散列值對RC4算法產(chǎn)生上一個隨機數(shù)時所處的內(nèi)部狀態(tài)進行置換.由計數(shù)器Counter的值不斷增加和SHA-3 512的抗碰撞性知，每次用于置換RC4算法內(nèi)部狀態(tài)的散列值都是不一樣的.因此，該操作可以增加RC4算法的周期.

由第2章組合式隨機數(shù)發(fā)生器的理論可以得出，本方案不僅增加了輸出序列的周期，而且還增加了RC4算法的周期，使得整個PRNG算法具備更強的抗密碼分析能力.

3.2 方案局部的詳細執(zhí)行過程

流程圖2的執(zhí)行順序及各模塊的詳細操作說明.

圖2 本方案的局部結(jié)構(gòu)圖
Fig.2 Local structure of the scheme

1)從外部獲取一個隨機的種子(Seed)并將此隨機數(shù)作為RC4算法的種子.

2)調(diào)用RC4算法(如圖2中①所標(biāo)識)產(chǎn)生一個字節(jié)的隨機數(shù)(用n表示)，并計算N=64+(nmod162).

5)調(diào)用RC4算法若干次以使本方案用到的線性同余發(fā)生器(Xn+1=(aXn+c)mod256)達到滿周期.具體的參數(shù)更新過程如下(如圖2中④所標(biāo)識)：

② 同更新參數(shù)a的值一樣.調(diào)用RC4算法產(chǎn)生一個字節(jié)的隨機數(shù)c1，判斷c1是否滿足gcd(c1,256)=1(gcd(a,b)表示a和b的最大公約數(shù))，如果滿足,則將c1作為該線性同余發(fā)生器的參數(shù)c的值(c=c1)；如果不滿足，則繼續(xù)調(diào)用RC4算法產(chǎn)生一個隨機數(shù)ci，直到ci滿足gcd(ci,256)=1，該步驟停止，并將ci作為該線性同余發(fā)生器參數(shù)c的值(c=c1).

③ 因為RC4算法產(chǎn)生的任何數(shù)都可以作為該線性同余發(fā)生器的種子，所以只需要再調(diào)用一次RC4算法產(chǎn)生一個字節(jié)的隨機數(shù)X，并將X作為該線性同余發(fā)生器的種子(Xn=X).

3.3 方案整體的詳細執(zhí)行過程

下面對方案的整體流程圖3的執(zhí)行過程進行說明.

1)從外部獲取一個隨機的種子(Seed)并將此隨機數(shù)作為RC4算法的種子，同時把該種子的前16個字節(jié)作為本方案所設(shè)計的PRNG內(nèi)部計數(shù)器的初值(即Counter=Seed16，該操作僅被執(zhí)行一次).

2)調(diào)用一次RC4算法產(chǎn)生一個字節(jié)的數(shù)據(jù)(用M表示)，計算C=H+(MmodP) (如圖3中①所標(biāo)識).其中C表示：本輪產(chǎn)生一個偽隨機數(shù)所用到的線性同余算法(LCG)個數(shù).其中，H表示每生成一個隨機數(shù)最少用到的LCG個數(shù)，P表示整個PRNG算法在生成隨機數(shù)的過程中使用的LCG的變化幅度，對于生成的任意一個隨機數(shù)其用到的LCG個數(shù)變化范圍為：H至(H+P-1).H和P的具體取值由實際需要的安全強度和效率決定.

圖3 方案整體的詳細描述Fig.3 Overall detailed description of the scheme

7)調(diào)用RC4算法產(chǎn)生一個字節(jié)的數(shù)據(jù)(用F表示)，計算Q=(FmodC)+1.將第3步和第4步得到的C×64字節(jié)數(shù)據(jù)的第Q個64字節(jié)的數(shù)據(jù)分別轉(zhuǎn)化成一個大的整數(shù)，分別表示為R和L，并計算Temp=L+R(如圖3中⑤所標(biāo)識).

9)重復(fù)第 2到第 8步，直到得到所需數(shù)量的隨機數(shù).

4 安全性

4.1 不可預(yù)測性

應(yīng)用于密碼學(xué)的隨機數(shù)發(fā)生器必須具備不可預(yù)測性[20,21].對于偽隨機數(shù)發(fā)生器而言，在種子未知的情況下，即使已知序列中任意多個前綴都不能夠猜測到序列中的下一個隨機數(shù)，也即已經(jīng)產(chǎn)生的隨機數(shù)和序列的下一個隨機數(shù)之間沒有明顯的關(guān)系.這個性質(zhì)稱為前向不可預(yù)測性.同時，還應(yīng)該保證從任何已經(jīng)產(chǎn)生的序列中不能推導(dǎo)出偽隨機數(shù)發(fā)生器的種子，也即已經(jīng)產(chǎn)生的隨機數(shù)和種子之間沒有明顯的關(guān)系.這個性質(zhì)叫做后向不可預(yù)測性.下面分別從前向不可預(yù)測性和后向不可預(yù)測性的角度對本文設(shè)計的偽隨機數(shù)發(fā)生器的安全性進行分析.

4.1.1 前向不可預(yù)測性

圖4 先后產(chǎn)生的隨機數(shù)的關(guān)系
Fig.4 Relation of random numbers generated one after another

從圖1可以看出，要想得到第n個隨機數(shù)和第(n+1)個隨機數(shù)的關(guān)系，需要得到產(chǎn)生下一個隨機數(shù)的Seedn(其作用是在產(chǎn)生下一個隨機數(shù)之前對RC4當(dāng)前的內(nèi)部狀態(tài)進行置換).那么就需要得到計數(shù)器Counter當(dāng)前的值，也即需要得到相應(yīng)的R和L的值.繼續(xù)向前推導(dǎo)，需要猜測到方案流程圖3本輪生成的C×64字節(jié)的數(shù)據(jù).

圖5 求逆的困難性Fig.5 Difficulty of inversion

若上述工作全部完成，接下來猜測將兩個C×64字節(jié)的數(shù)據(jù)的第幾個64字節(jié)的數(shù)據(jù)轉(zhuǎn)化成了大整數(shù).那么就可以得到Tempn.然而，Counter=Seed16+Temp1+Temp2+…+Tempn，其中Seed16表示該PRNG從外部獲得的種子的前16個字節(jié)的數(shù)據(jù).因此，需要對變長輸入的SHA-3 512成功求逆n次，對異或的結(jié)果求逆n次，還要成功猜測n次轉(zhuǎn)化成大整數(shù)R和L的數(shù)據(jù)是C×64字節(jié)數(shù)據(jù)的第幾個64字節(jié)的數(shù)據(jù)，最后，還要猜測到計數(shù)器的初始值(外部輸入的種子的前16個字節(jié)).這是不可能的.因此，本方案具備前向不可預(yù)測性.

4.1.2 后向不可預(yù)測性

圖6 PRNG產(chǎn)生的隨機數(shù)與種子之間的關(guān)系Fig.6 Relationship between random numbers generated by PRNG and seeds

5 方案實驗

5.1 實驗平臺

本方案的實驗環(huán)境主要參數(shù)如表1所示.在集成開發(fā)環(huán)境Visual studio 2012中用C/C++對本方案進行代碼實現(xiàn)，在代碼實現(xiàn)過程中用到密碼學(xué)庫CryptoPP1.

表1 實驗環(huán)境主要參數(shù)Table 1 Main parameters of experimental environment

5.2 實驗數(shù)據(jù)

實驗的主要目的是測試本方案設(shè)計的PRNG能否通過NIST的隨機性測試標(biāo)準(zhǔn).同時，測試了方案中使用的LCG個數(shù)對產(chǎn)生隨機數(shù)效率的影響.表2中列舉了該PRNG算法使用的LCG個數(shù)的變化范圍為4(個)至8(個)時，使用不同位數(shù)的種子產(chǎn)生不同數(shù)量的隨機比特并將其以二進制格式寫入磁盤中的文件花費的時間.表3列舉了該PRNG算法使用的LCG個數(shù)的變化范圍為2(個)至4(個)時，使用不同位數(shù)的種子產(chǎn)生不同數(shù)量的隨機比特并將其以二進制格式寫入磁盤中的文件花費的時間.

表2 使用的LCG個數(shù)的變化范圍為：4(個)～8(個)Table 2 Number of used LCG varies from 4 (units) to 8 (units)

表3 使用的LCG個數(shù)的變化范圍為：2(個)～4(個)
Table 3 Number of used LCG varies from 2 (units) to 4(units)

比特數(shù)量種子位數(shù) 100000000(bits)1000000000(bits)10000000000(bits)256位種子1.286(mins)12.849(mins)126.012(mins)512位種子1.291(mins)12.912(mins)132.532(mins)1024位種子1.287(mins)13.245(mins)128.418(mins)

用NIST提供的SP800-22測試包對上述實驗產(chǎn)生的數(shù)據(jù)進行統(tǒng)計測試.該測試包主要包括15個測試項，有些測試項被分成了多個子測試項，每個測試項的結(jié)果中均有p-value值和通過率Proportion兩個指標(biāo).對于P-value值，若該值大于規(guī)定的顯著水平α，則說明序列是隨機的，一般α的取值為[0.001,0.01]；對于通過率的值Proportion，若該值在置信區(qū)間內(nèi)，表示序列通過該項檢測，反之則未通過.設(shè)β是被測序列的組數(shù)，則置信區(qū)間為：

設(shè)置顯著性水平α=0.01，其他選項采用默認.用NIST隨機性測試方法對本方案設(shè)計的PRNG算法生成的β組1M bits的序列進行測試.在使用256位種子、LCG變化范圍為4(個)～8(個)情況下，分別取分組長度β=1000、β=3000、β=5000的數(shù)據(jù)進行測試，結(jié)果顯示該PRNG算法能夠很好地通過測試.表4列舉了β=1000時，各項測試結(jié)果對應(yīng)的P-value值和Proportion值.其中，帶*的測試項目表示該項含有多個子項.對于含有多個子項的項，表中分別對列出了其Proportion值最大的子項和最小的子項及相應(yīng)的P-value值.

表4 NIST SP800-22 測試結(jié)果Table 4 Test results of NIST SP800-22

5.3 實驗結(jié)論

從表2和表3的實驗結(jié)果可以得到，該PRNG在使用相同的種子產(chǎn)生100000000(bits)、1000000000(bits)、10000000000(bits)的隨機數(shù)平均花費的時間近似相等，所以可以認為方案中用到的CryptoPP中構(gòu)造的Integer類涉及的大整數(shù)轉(zhuǎn)換和加法運算都可以高效地執(zhí)行.

對比表2和表3的實驗結(jié)果可以得到，方案中使用的LCG算法個數(shù)影響著整個PRNG的效率.因此，在使用該PRNG算法時可以根據(jù)具體的安全性強度和效率要求選擇合適個數(shù)的LCG.