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

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

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

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

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

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

(1)看起來是隨機的。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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