羅馬12毫米骰子，PAS(一個(gè)英國(guó)政府管理下的保護(hù)文物志愿者組織)/大英博物館董事(CC BY-SA 2.0)

統(tǒng)計(jì)學(xué)家弗朗西斯 · 加爾頓于1890 年《自然》雜志上寫(xiě)道：“作為一個(gè)選擇隨機(jī)的工具，我發(fā)現(xiàn)沒(méi)有什么優(yōu)于骰子。把它們?nèi)舆M(jìn)裝骰子的盒子中搖動(dòng)，它們彼此相互沖撞，并與盒壁碰彈，不停的滾動(dòng)，即使在一次搖骰子中，骰子的最初朝向也無(wú)法為其最終的朝向提供任何有用的線(xiàn)索。”

我們?nèi)绾尾拍苌梢粋€(gè)均勻的隨機(jī)數(shù)序列?大自然中產(chǎn)生的如此美麗和豐富的隨機(jī)性并不總可以被輕松的提取和量化。最古老的骰子是在公元前24世紀(jì)中東的一個(gè)墳?zāi)怪斜话l(fā)現(xiàn)的。大約在公元前1100年，在中國(guó)，龜卜中火熱龜殼直到其隨機(jī)破裂，然后占卜者對(duì)龜殼裂縫進(jìn)行解釋。幾個(gè)世紀(jì)之后，易經(jīng)卜卦中將49條蓍草莖放在桌子上，按一定規(guī)則切分幾次，其結(jié)果類(lèi)似于執(zhí)行硬幣投擲。

摘自《A Million Random Digits with 100,000 Normal Deviates》

但是到了二十世紀(jì)40年代中期，現(xiàn)代世界需要更多的隨機(jī)數(shù)，遠(yuǎn)超過(guò)骰子和蓍草莖可提供的范圍。蘭德公司研發(fā)了一種機(jī)器可以使用隨機(jī)脈沖發(fā)生器產(chǎn)生隨機(jī)數(shù)。他們運(yùn)行了一段時(shí)間，并收集到一本書(shū)中《A Million Random Digits with 100,000 Normal Deviates》?，F(xiàn)在看來(lái)，這似乎是一個(gè)好笑的藝術(shù)項(xiàng)目，但在當(dāng)時(shí)卻是一大突破，這是第一次為公眾提供了一個(gè)高質(zhì)量的長(zhǎng)隨機(jī)數(shù)序列。蘭德公司在2001重印了該書(shū)，現(xiàn)在在亞馬遜上可以購(gòu)買(mǎi)。

另外還有一個(gè)類(lèi)似的機(jī)器：搖獎(jiǎng)機(jī)，是有當(dāng)時(shí)著名的Bletchley Park WWII 破譯小組于上世紀(jì)40年代設(shè)計(jì)的，用來(lái)為英國(guó)的保險(xiǎn)債券彩票產(chǎn)生隨機(jī)數(shù)。為了減輕對(duì)ERNIE公正性和準(zhǔn)確性的擔(dān)憂(yōu)，公司做了一個(gè)偉大的紀(jì)錄片，稱(chēng)為“E.R.N.I.E.的重要性”，非常值得一看：The Importance of Being E.R.N.I.E. 。

1951年，隨機(jī)數(shù)生成終于被正式地內(nèi)嵌到一臺(tái)真正的計(jì)算機(jī)中：Ferranti Mark 1 ,它帶有一個(gè)內(nèi)置的隨機(jī)數(shù)指令，可以使用電氣噪聲一次生產(chǎn)20個(gè)隨機(jī)比特。這個(gè)功能由阿蘭·圖靈設(shè)計(jì)，Christopher Strachey 通過(guò)利用它編寫(xiě)一個(gè)隨機(jī)的情書(shū)發(fā)生器。下面是一個(gè)情書(shū)的例子，來(lái)自David Link該項(xiàng)目的2009 復(fù)合計(jì)劃。

但是圖靈的隨機(jī)數(shù)字指令讓當(dāng)時(shí)的程序員感到非常困惑,因?yàn)樗谝粋€(gè)已經(jīng)如此不可預(yù)測(cè)的環(huán)境中造成了太多的不確定性。人們期望軟件的一致性，但使用該指令的程序永遠(yuǎn)無(wú)法以一種一致性的可重復(fù)方式運(yùn)行，這使得測(cè)試幾乎不可能。

如果一個(gè)隨機(jī)數(shù)發(fā)生器可以表示為確定性函數(shù)呢?如果可以重復(fù)調(diào)用一個(gè)隨機(jī)數(shù)序列，但在相同的初始化條件下，它總是會(huì)產(chǎn)生相同的序列呢?這就是偽隨機(jī)數(shù)發(fā)生器(PRNG)。

馮·諾依曼在1946年左右開(kāi)發(fā)了一個(gè)PRNG，他的想法是從一個(gè)初始的隨機(jī)種子值開(kāi)始對(duì)其平方，然后截取平方結(jié)果的中間若干位，得到一個(gè)新的數(shù)字，接下來(lái)重復(fù)對(duì)得到的數(shù)取平方并截取中間若干位的過(guò)程，就會(huì)得到一個(gè)具有統(tǒng)計(jì)意義屬性的隨機(jī)數(shù)序列了，這也就是廣為人知的平方取中法。

馮·諾依曼的方法沒(méi)有經(jīng)受住時(shí)間的考驗(yàn)，因?yàn)闊o(wú)論使用什么樣的種子值，序列最終會(huì)陷入一系列短重復(fù)周期的數(shù)字，如8100，6100，4100，8100，6100，4100……

當(dāng)使用確定性函數(shù)生成隨機(jī)數(shù)序列時(shí)，如果后續(xù)值基于先前值，避免循環(huán)是不可能的。但是如果周期足夠長(zhǎng)，使之對(duì)隨機(jī)序列實(shí)際上影響不大呢?

依照這一想法，數(shù)學(xué)家D.H.Lehmer在1949年提出了線(xiàn)性同余生成器(LCG)。這里介紹一個(gè)簡(jiǎn)單的PRNG，叫做中央隨機(jī)數(shù)生成器，便是基于Lehmer的方法，于1995年采用JavaScript編寫(xiě)實(shí)現(xiàn)如下：

注意這里的所有幻數(shù)，選擇這些數(shù)字(通常是素?cái)?shù))用來(lái)最大化周期：在rand()生成序列之前迭代次數(shù)將自我重復(fù)。該P(yáng)RNG使用當(dāng)前時(shí)間作為種子值，其周期值約為2的31次方。

中央隨機(jī)生成器指針變得流行是因?yàn)镴avaScript 1.0沒(méi)有內(nèi)置的Math.random()函數(shù)，每個(gè)人都希望他們的Web 1.0橫幅廣告隨機(jī)旋轉(zhuǎn)。開(kāi)發(fā)者Paul Houle寫(xiě)道：“我不會(huì)用它來(lái)保密，但它對(duì)許多用途都是有好處的。”

然而互聯(lián)網(wǎng)確實(shí)需要保密。 SSL誕生于1995年左右，其加密方案要求高質(zhì)量的PRNG，這種發(fā)展可能導(dǎo)致了一段RNGs 迅猛創(chuàng)新的時(shí)期。如果查看所有的隨機(jī)數(shù)生成器的專(zhuān)利，可能會(huì)感覺(jué)就像現(xiàn)代版的第一次制造飛機(jī)的浪潮一樣。

20世紀(jì)90年代中期最常見(jiàn)的CPU沒(méi)有生產(chǎn)隨機(jī)數(shù)的指令，所以好的隨機(jī)種子很難在當(dāng)時(shí)得到。當(dāng)Phillip Hallam-Baker發(fā)現(xiàn)Netscape的SSL網(wǎng)絡(luò)服務(wù)器(當(dāng)時(shí)市場(chǎng)上最大的一個(gè))使用當(dāng)前時(shí)間和幾個(gè)進(jìn)程ID的組合作為其隨機(jī)數(shù)生成器的種子時(shí)，才意識(shí)這將成為一個(gè)真正的安全問(wèn)題。哈拉姆·貝克(Hallam-Baker)表示，攻擊者可以很容易地猜到種子值，并采用各種手段解密服務(wù)器的流量。 猜測(cè)種子值是一種常見(jiàn)的攻擊，盡管它已經(jīng)變得越來(lái)越復(fù)雜了。這是 2009年在 Hacker News 上的一段非常經(jīng)典的攻擊演練。

到1997年，計(jì)算機(jī)科學(xué)家們對(duì)生成隨機(jī)數(shù)的有限選項(xiàng)感到厭倦，所以SGI的一個(gè)團(tuán)隊(duì)創(chuàng)建了LavaRand，這是一個(gè)網(wǎng)絡(luò)攝像頭，指向桌面上的幾個(gè)熔巖燈。相機(jī)的圖像數(shù)據(jù)是一個(gè)很好的熵源：就像圖靈的真正隨機(jī)數(shù)生成器(TRNG)，并且它可以以165Kb / s的速率生成隨機(jī)數(shù)據(jù)。在當(dāng)時(shí)的硅谷時(shí)代，熔巖燈平臺(tái)迅速獲得專(zhuān)利。

Autodesk的創(chuàng)始人約翰·沃克(John Walker)意圖在世界各地推廣他的 HotBits，一個(gè)隨機(jī)數(shù)字生成服務(wù)應(yīng)用程序，由一個(gè)保證真正量子隨機(jī)性的蓋革計(jì)數(shù)器支持。 Random.org創(chuàng)建于1998，為互聯(lián)網(wǎng)提供免費(fèi)的隨機(jī)數(shù)，他們現(xiàn)在提供的手機(jī)應(yīng)用程序可以實(shí)現(xiàn)真正的隨機(jī)拋硬幣，扔骰子，撲克洗牌等。

大多數(shù)的這些發(fā)明都半途而廢，但是一個(gè)叫做梅森旋轉(zhuǎn)隨機(jī)數(shù)生成器(The Mersenne Twister)的PRNG 軟件被推廣，在1997 由松本眞和西村拓士發(fā)明。它完美地平衡了性能和隨機(jī)數(shù)的質(zhì)量，并且經(jīng)受住了時(shí)間的考驗(yàn)。它基于線(xiàn)性反饋移位寄存器(LFSR)的思想，產(chǎn)生一個(gè)循環(huán)周期非常長(zhǎng)的確定性序列。近期的應(yīng)用中，其循環(huán)周期可達(dá)到 2¹⁹⁹³⁷− 1。在如今的編程語(yǔ)言中，這種算法依舊是默認(rèn)的 PRNG。

終于在1999發(fā)生了一個(gè)很大的轉(zhuǎn)變。英特爾在其i810芯片組中增加了一個(gè)內(nèi)置的隨機(jī)數(shù)發(fā)生器。這使得新的服務(wù)器具備了來(lái)自熱噪聲的本地源隨機(jī)數(shù)生成能力——真正的隨機(jī)數(shù)生成器(TRNG)。這非常具有進(jìn)步意義，但速度仍不如軟件PRNGs快，所以加密軟件仍然不得不依靠一個(gè)偽隨機(jī)數(shù)發(fā)生器。

這節(jié)我們介紹安全加密的PRNG(CSPRNG)，(這些縮寫(xiě)!難怪有些人認(rèn)為計(jì)算機(jī)科學(xué)是枯燥的。)在SSL的時(shí)代CSPRNG非常重要。什么是CSPRNG?這里有一份 131 頁(yè)的論文來(lái)介紹 CSPRNG，希望你能愉快閱讀。

不言而喻，CSPRNG 具有很強(qiáng)的要求。梅森旋轉(zhuǎn)隨機(jī)數(shù)生成器并不是一種 CSPRNG，因?yàn)槿绻梢越o定大量的先前序列樣本，后面的數(shù)字可以預(yù)計(jì)出來(lái)。最近，2012年英特爾在真隨機(jī)數(shù)發(fā)生器上增加了 RDRAND 和RDSEED指令，采用片上熱噪聲發(fā)生器可提供500MB/s的吞吐量。但RDRAND 的完整性一直被質(zhì)疑。是不是存在細(xì)小的缺陷?或者是為國(guó)家安全局內(nèi)置了什么東西?沒(méi)有人知道這個(gè)問(wèn)題的答案。我猜某些地方的某些人一定知道，可是他們也一定不會(huì)公開(kāi)。

采用硬件隨機(jī)數(shù)生成器 PEDOUBLER 生成的隨機(jī)數(shù)。

開(kāi)源硬件TRNGs于最近些年出現(xiàn)，其優(yōu)點(diǎn)源自于設(shè)計(jì)的透明化：你可以檢查電路本身，也可以在家里使用現(xiàn)成的組件建立它們。完全透明的設(shè)計(jì)不會(huì)讓人懷疑這些電路優(yōu)秀的隨機(jī)性。REDOUBLER和無(wú)限噪聲 TRNG是兩個(gè)開(kāi)源硬件隨機(jī)數(shù)生成器，鏈接中給出他們的 Github 源碼地址。

今天，關(guān)于隨機(jī)數(shù)生產(chǎn)方法選擇的爭(zhēng)論仍存在于在操作系統(tǒng)內(nèi)核，編程語(yǔ)言，和安全包(如 OpenSSL 或者 OpenSSH)等方面。這些算法存在多種變形用以滿(mǎn)足不同的速度、空間和安全要求，安全專(zhuān)家總是在尋找新的方法來(lái)攻破已有算法的實(shí)現(xiàn)。但是對(duì)于日常使用，在大多數(shù)的操作系統(tǒng)中我們可以放心地使用 /dev/random，或者編程語(yǔ)言中的 rand() 函數(shù)，它們都可以快速得到一段足夠長(zhǎng)的隨機(jī)數(shù)列，并且你這么做，阿蘭·圖靈也會(huì)很開(kāi)心。

來(lái)源：https://medium.freecodecamp.com/a-brief-history-of-random-numbers-9498737f5b6c

【本文是51CTO專(zhuān)欄機(jī)構(gòu)大數(shù)據(jù)文摘的原創(chuàng)譯文，微信公眾號(hào)“大數(shù)據(jù)文摘（ id: BigDataDigest）”】

戳這里，看該作者更多好文