一種軟件生成真隨機(jī)數(shù)算法的設(shè)計(jì)和實(shí)現(xiàn)

一種軟件生成真隨機(jī)數(shù)算法的設(shè)計(jì)和實(shí)現(xiàn)

摘要本文提出了一種在軟件上實(shí)現(xiàn)真隨機(jī)數(shù)的方法，該方法根據(jù)計(jì)算機(jī)上的一些隨機(jī)性事件，來(lái)生成一個(gè)由0和1組成的隨機(jī)序列，然后對(duì)01序列進(jìn)行進(jìn)一步的隨機(jī)處理，以進(jìn)一步增強(qiáng)其隨機(jī)性；根據(jù)這個(gè)01序列來(lái)生成所需要的隨機(jī)數(shù)。基于這種設(shè)計(jì)方法，本文根據(jù)鼠標(biāo)在計(jì)算機(jī)屏幕上的隨機(jī)曲線來(lái)生成01序列，然后使用線性同余法對(duì)其進(jìn)行進(jìn)一步處理。

關(guān)鍵詞真隨機(jī)數(shù)；偽隨機(jī)數(shù)；線性同余法；二元序列1引言

隨機(jī)數(shù)在信息安全領(lǐng)域有著廣泛的應(yīng)用，比如各種安全認(rèn)證協(xié)議，一次安全通信中使用到的會(huì)晤密鑰，甚至軟件產(chǎn)生RSA密鑰對(duì)等，這些應(yīng)用都會(huì)使用到隨機(jī)數(shù)。特別是一些安全級(jí)別要求比較高的應(yīng)用，對(duì)于隨機(jī)數(shù)的質(zhì)量提出了很高的要求。隨機(jī)數(shù)的生成一般有兩種方式，一種是硬件方式，一種是軟件方式。一般情況下，硬件方式生成的隨機(jī)數(shù)質(zhì)量要好于軟件方式生成的隨機(jī)數(shù)。但是對(duì)于一般的用戶來(lái)說(shuō)，需要每位用戶都配備一種硬件設(shè)備來(lái)生成隨機(jī)數(shù)，這種方式可能不太現(xiàn)實(shí)。因此，通過(guò)軟件方式來(lái)尋找高質(zhì)量的隨機(jī)數(shù)，這是一個(gè)很重要而且必要的課題。2基礎(chǔ)知識(shí)

在密碼學(xué)中，對(duì)于一個(gè)隨機(jī)序列的定義如下：

(1)看起來(lái)是隨機(jī)的。

(2)這個(gè)序列是不可預(yù)測(cè)的。

(3)這個(gè)序列是不能重復(fù)產(chǎn)生的。

隨機(jī)數(shù)生成器有真隨機(jī)和偽隨機(jī)之分。真隨機(jī)數(shù)生成器滿足以上所有的三點(diǎn)要求，偽隨機(jī)數(shù)生成器只能滿足以上的前兩點(diǎn)要求。

軟件生成隨機(jī)數(shù)的一般方式如下：

(1)確定一個(gè)數(shù)學(xué)模型或者算法。

(2)設(shè)置一些參數(shù)的值。

(3)按照規(guī)定的步驟和算法來(lái)生成第一個(gè)隨機(jī)數(shù)。

(4)然后在第一個(gè)隨機(jī)數(shù)的基礎(chǔ)上，來(lái)生成第二個(gè)隨機(jī)數(shù)。重復(fù)同樣的步驟，從而得到一個(gè)隨機(jī)數(shù)序列。

很明顯，這種軟件方式生成的隨機(jī)數(shù)是偽隨機(jī)數(shù)序列。只要知道了其使用的算法和參數(shù)值，我們就可以生成同樣的隨機(jī)數(shù)序列。因此，真正的隨機(jī)數(shù)是不可能通過(guò)具體的算法來(lái)生成的。真正的隨機(jī)數(shù)序列只能來(lái)源于隨機(jī)事件，那么我們可以從計(jì)算機(jī)系統(tǒng)中存在的大量的隨機(jī)事件中提取隨機(jī)事件，經(jīng)過(guò)正確的處理就有可能生成真正的隨機(jī)數(shù)序列。比如，將用戶的擊鍵次數(shù)，鼠標(biāo)的操作次數(shù)，CPU負(fù)載，網(wǎng)絡(luò)數(shù)據(jù)包到達(dá)次數(shù)等隨機(jī)信息放入到一個(gè)被稱為“熵池”的緩存區(qū)中，“熵池”被均勻地?cái)嚢?。?dāng)需要取隨機(jī)數(shù)時(shí)，我們就從“熵池”中讀取隨機(jī)數(shù)源。但是這種方式生成隨機(jī)數(shù)的速度不夠理想。3設(shè)計(jì)思想

在信息安全領(lǐng)域，我們經(jīng)常遇到這樣的情況：需要生成8個(gè)字節(jié)的隨機(jī)數(shù)序列。那么我們可以把這8個(gè)字節(jié)的隨機(jī)數(shù)序列當(dāng)成由64個(gè)bit所組成的，每個(gè)bit位的取值為0或者1。如果我們使用投擲硬幣的方式來(lái)決定每個(gè)bit位應(yīng)該取0還是1，那么我們投擲64次硬幣，就會(huì)得到一個(gè)由0或者1組成的隨機(jī)數(shù)序列。這個(gè)0和1組成的隨機(jī)數(shù)序列每8位組成一個(gè)字節(jié)，最終我們得到了要求的8個(gè)字節(jié)的隨機(jī)數(shù)序列。像這種隨機(jī)數(shù)序列的生成方式，它符合了密碼學(xué)對(duì)于隨機(jī)序列定義的3個(gè)特點(diǎn)，從而保證它是一個(gè)真正的隨機(jī)數(shù)序列。但是，顯而易見(jiàn)地，這種生成隨機(jī)數(shù)序列的方式效率太低下了。

基于這種思想，我們可以利用計(jì)算機(jī)系統(tǒng)的隨機(jī)性，提取出0和1組成的隨機(jī)數(shù)序列，然后對(duì)這個(gè)0和1組成的隨機(jī)數(shù)序列進(jìn)行組合處理，從而最終得到質(zhì)量很高的真隨機(jī)數(shù)序列。我們的算法思想可以總結(jié)為如下幾步：

(1)根據(jù)計(jì)算機(jī)系統(tǒng)中的隨機(jī)事件，得到0和1組成的原始隨機(jī)數(shù)序列。

(2)對(duì)0和1組成的原始隨機(jī)數(shù)序列進(jìn)行某種處理，獲得組合之后的由0和1組成的組合隨機(jī)數(shù)序列。

(3)繼續(xù)進(jìn)行類似于第二步的處理，進(jìn)行多次的組合處理。

(4)將最終得到的0和1隨機(jī)數(shù)序列每8個(gè)bit組成一個(gè)字節(jié)，從而得到若干字節(jié)的隨機(jī)數(shù)。在這個(gè)設(shè)計(jì)方法中，關(guān)鍵的是第一步，隨機(jī)事件的獲取。只要能保證原始隨機(jī)數(shù)序列是真正的隨機(jī)事件生成的，即使我們不進(jìn)行后續(xù)的組合處理，我們也可以得到真正的隨機(jī)數(shù)序列。就好像我們通過(guò)投擲硬幣來(lái)獲得8字節(jié)的隨機(jī)數(shù)一樣。但是，由于計(jì)算時(shí)間或者計(jì)算機(jī)系統(tǒng)的精度等各方面的限制，長(zhǎng)度很長(zhǎng)的原始隨機(jī)數(shù)序列不容易獲得。所以，需要對(duì)獲得的原始隨機(jī)數(shù)序列進(jìn)行數(shù)學(xué)上的處理，以便獲得長(zhǎng)度很長(zhǎng)的隨機(jī)數(shù)序列。

對(duì)于進(jìn)一步的組合處理，我們要慎重的選擇。如果選擇的好，可以進(jìn)一步的增加序列的隨機(jī)性，從而可以降低對(duì)原始隨機(jī)數(shù)序列采集的要求。但是，特別值得注意的是，如果選擇的組合算法存在缺陷，反而有可能降低原始隨機(jī)數(shù)序列的隨機(jī)性。極端的情況是，比如組合算法生成的結(jié)果都是0組成的序列。4具體實(shí)現(xiàn)

我們選擇這樣的一種隨機(jī)事件，當(dāng)用戶拿著鼠標(biāo)在計(jì)算機(jī)屏幕上隨意滑動(dòng)時(shí)，鼠標(biāo)滑動(dòng)的軌跡組成的一條曲線是隨機(jī)的。也就是說(shuō)，即使同一個(gè)用戶也不可能劃出這樣一條完全一致的曲線。這種方式很類似于我們投擲硬幣的方式。就像古希臘一位哲人所說(shuō)，人生不可能兩次踏入同一條河流。

基于上述的隨機(jī)事件的選擇，我們?cè)谝欢ǖ臅r(shí)間內(nèi)對(duì)這條曲線進(jìn)行時(shí)間的抽樣。如果要求生成Nbit的01序列，那么我們就對(duì)這段曲線進(jìn)行時(shí)間間隔為1/N的取樣。這樣，我們就會(huì)得到N個(gè)取樣點(diǎn)，每個(gè)取樣點(diǎn)用其在計(jì)算機(jī)屏幕上的坐標(biāo)來(lái)表示。接著對(duì)每個(gè)取樣點(diǎn)的橫坐標(biāo)和縱坐標(biāo)進(jìn)行相加，取不大于坐標(biāo)和的最大整數(shù)。如果得到的整數(shù)是偶數(shù)，那么這個(gè)取樣點(diǎn)就表示為0；如果得到的整數(shù)是奇數(shù)，那么這個(gè)取樣點(diǎn)就表示為1。這樣，我們最后得到了由0和1組成的隨機(jī)數(shù)序列。假設(shè)，我們得到的隨機(jī)數(shù)序列可以表示為：

Seed[i]，其中(i=0，1，…N-1)

然后，我們對(duì)得到的隨機(jī)數(shù)序列進(jìn)行進(jìn)一步的處理，組成組合隨機(jī)數(shù)生成器，從而進(jìn)一步增強(qiáng)序列的隨機(jī)性。

我們使用線性同余法對(duì)原始隨機(jī)數(shù)序列進(jìn)行進(jìn)一步處理，從而得到新的組合隨機(jī)數(shù)序列。我們使用線性同余法得到N個(gè)位于[0，N-1]之間的隨機(jī)數(shù)，它可以表示為：

A[j]，其中(j=0，1，…N-1)，(A[j]的取值在[0，N-1]).

數(shù)組A[j]的含義如下：數(shù)組下標(biāo)j表示組合后的隨機(jī)數(shù)序列的第j個(gè)位置，數(shù)組的值A(chǔ)[j]表示組合后的隨機(jī)數(shù)序列第j個(gè)位置的值從原始隨機(jī)數(shù)序列Seed中A[j]位置取值。

如果得到的隨機(jī)數(shù)序列A[j]沒(méi)有重復(fù)值，也就是滿足：A[j]=A[k]，當(dāng)且僅當(dāng)j=k。那么得到的組合隨機(jī)數(shù)序列為：

Seed[A[0]]，Seed[A[1]]，Seed[A[2]]，…Seed[A[N-1]].

如果得到的隨機(jī)數(shù)序列A[j]有重復(fù)值，比如A[6]=A[23]=N/2。

假設(shè)出現(xiàn)A[j]=A[k](j<k)，那么組合后的隨機(jī)數(shù)序列的第k個(gè)位置暫時(shí)不做處理，繼續(xù)下一個(gè)位