隨機數生成器漫談(二)

隨機數在我們生活工作中無處不在,一組真正的隨機數列呢,應該具有哪些特性呢?

隨機數生成器漫談(二)

等機率性

在隨機序列中,每個數字出現的機率應該相等,對應於二進位制,也就是

0和1的出現機率應該相等

。顯然這個樸素的,可以使用反證法。如果0和1出現的機率不一樣,比如1的機率為51,0點機率為49,則我們可以以51%的機率預測下一個數字為1,超過一半的機率了,顯然已經不隨機了。

滿足這個條件就一定是隨機數序列了嗎?顯然也不對。類似0101010101……這樣的迴圈序列顯然也不是隨機的。所以還需要下面的條件

獨立性

根據前面的已知資訊,無法以

大於1/2的機率推測出下一個數字為0或者為1

。就像彩票,知道了前面那麼多期的結果,可是還是中不了大獎。

如果給了一個電腦,如何編寫程式構造隨機序列呢?現在使用的方法主要有下面二種思路。

獲取物理資訊,轉換成隨機數。

Linux中專門提供了兩個隨機數生成裝置(也就是檔案,對於linux來說,一切皆是檔案),分別是

/dev/urandom和dev/random

。他們是利用

系統的熵

來生成隨機數。學過物理和資訊理論或者相關學科應該知道,熵是一種刻畫系統混亂程度的度量,隨著時間的流逝,封閉系統的熵會越來越大。對於計算機,有個熵池,專門收集記憶體、檔案、CPU、程序等的資訊來表徵熵。如果當前系統很穩定,比如剛開機的時候,或者待機的時候,熵增加的就慢,隨機性就不好。

對於 /dev/urandom和/dev/random來說,random依賴於系統中斷,當系統中斷數不足時,裝置會禁止訪問,其他程序會阻塞,直到根據熵池產生新的隨機位元組之後才返回。對於urandom,則不會(ublock),但是產生的隨機數效果就不太好了。

隨機數生成器漫談(二)

使用指令

rdrand

或者

rdseed

Inter對CPU提供了

rdrand

rdseed

指令,專門用來提供隨機數。具體的差別可以參考文件 The Difference Between RDRAND and RDSEED。Inter的建議如下:

如果您希望播種另一個偽隨機數生成器(PRNG),請使用RDSEED

出於所有其他目的,請使用RDRAND

隨機數生成器漫談(二)

上面的程式碼,透過rdrand讀取隨機數,放入暫存器r1、r2、r3、r4中。

使用偽隨機數生成器

使用random()或者rand()

C語言自帶的,對隨機性和安全性要求不高的,可以選擇使用。

使用密碼演算法生成偽隨機數

密碼演算法(加密演算法,雜湊演算法)等都有很好的偽隨機性。具體來說,給定輸入,不能預測輸出,即使知道很多對輸入和輸出。常見的一個應用場景就是網上銀行的u盾,會不斷的生成一串數字。這些演算法都是

偽隨機

的,在執行足夠長的時間後,將會變成迴圈序列,只不過迴圈的週期很長很長。很多的密碼庫和數學庫都提供有此類庫,比如openssl等。