一種軟件生成真隨機數算法的設計和實現

摘要本文提出了一種在軟件上實現真隨機數的方法，該方法根據計算機上的一些隨機性事件，來生成一個由0和1組成的隨機序列，然后對01序列進行進一步的隨機處理，以進一步增強其隨機性；根據這個01序列來生成所需要的隨機數。基于這種設計方法，本文根據鼠標在計算機屏幕上的隨機曲線來生成01序列，然后使用線性同余法對其進行進一步處理。

關鍵詞真隨機數；偽隨機數；線性同余法；二元序列1引言

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

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

(1)看起來是隨機的。

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

(3)這個序列是不能重復產生的。

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

軟件生成隨機數的一般方式如下：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

數組A[j]的含義如下：數組下標j表示組合后的隨機數序列的第j個位置，數組的值A[j]表示組合后的隨機數序列第j個位置的值從原始隨機數序列Seed中A[j]位置取值。

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

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

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

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