作者：Alon Zakai

編譯：胡子大哈

翻譯原文：http://huziketang.com/blog/posts/detail?postId=58cfc3dda6d8a07e449fdd29

英文原文：A Brief History of Random Numbers

** 轉(zhuǎn)載請注明出處，保留原文鏈接以及作者信息**

（羅馬 12mm 骰子挑胸，大英博物館便攜式文物保護方案-CC BY-SA 2.0）

“在所有的產(chǎn)生隨機數(shù)的事物中艇抠，我認(rèn)為沒有什么能夠超越骰子了”寸莫，這是統(tǒng)計學(xué)家 Francis Galton 在 1890 年的《自然》雜志中寫道。它們在容器中不斷地翻滾弧呐、互相撞擊，以各種形式和角度與容器壁發(fā)生碰撞，在容器中的位置和形態(tài)在外界看來都是那么不可預(yù)知漆改，容器哪怕只發(fā)生一次晃動，外界都不可能知道里面到底是什么形態(tài)准谚。

古已有之的隨機數(shù)

到底如何才能生成均勻的隨機數(shù)列呢挫剑？自然界中隨機性大量而近乎完美的存在，人類并不能準(zhǔn)確地預(yù)知和量化這種隨機性柱衔。迄今為止發(fā)現(xiàn)最早的骰子（4 個面）是來自中東的一座公元前 24 世紀(jì)的墳?zāi)估锓啤Ｔ俳恍┑臍v史是在公元前 1100 年的中國，利用火燒龜殼產(chǎn)生的隨機龜裂現(xiàn)象唆铐，一些“先知”會根據(jù)龜裂情況來對未來做判斷哲戚。又過了幾個世紀(jì)，在中國誕生了易經(jīng)占卜法艾岂，利用 49 蓍草法進行占卜顺少，其操作的分裂過程很類似于拋硬幣。

機器生成隨機數(shù)的第一次觸碰

（摘自：“ A Million Random Digits with 100,000 Normal Deviates”）

時間到了 20 世紀(jì) 40 年代中期王浴，現(xiàn)代世界需要更多的隨機數(shù)脆炎，不再是骰子或者蓍草可以滿足的了。RAND 公司發(fā)明了一種機器氓辣，通過隨機脈沖發(fā)生器可以生成大量的隨機數(shù)秒裕。他們將這個機器運行所產(chǎn)生的數(shù)字聚合起來并發(fā)布成圖書“A Million Random Digits with 100,000 Normal Deviates”。這在現(xiàn)在看來是十分荒謬的钞啸，但是在當(dāng)時卻是一個突破几蜻。這是人類第一次產(chǎn)生如此大量的癞松、高質(zhì)量的隨機數(shù)，并且對公眾是開放的入蛆。這本書 RAND 公司一直印刷到了 2001 年响蓉，現(xiàn)在在亞馬遜上也可以看得到。

于此類似的機器：搖獎機哨毁，是由著名的 Bletchley Park WWII 破譯小組在 20 世紀(jì) 40 年代發(fā)明的枫甲，當(dāng)時被用來生成英國保險債券彩票所使用的隨機數(shù)。為了平息公眾對搖獎機的公平性和準(zhǔn)確性的質(zhì)疑和擔(dān)心扼褪，官方斥資制作了當(dāng)時的巨型紀(jì)錄片：“搖獎機的重要性（The Importance of Being E.R.N.I.E.）”想幻。下面給出視頻，很值得一看话浇。

<iframe frameborder="0" width="640" height="498" src="https://v.qq.com/iframe/player.html?vid=n0385z4te91&tiny=0&auto=0" allowfullscreen></iframe>

（The Importance of Being E.R.N.I.E.）

1951 年隨機性終于被正式規(guī)范化并且整合到了計算機 Ferranti Mark 1 號中脏毯。Ferranti Mark 1 號內(nèi)置了隨機數(shù)生成指令，利用電氣噪聲可以一次性生成 20 個隨機比特位幔崖。這一特性是由阿蘭·圖靈設(shè)計的食店。Christopher Strachey 利用這一特點，編寫了一套隨機情書生成器赏寇。下面這是情書例子吉嫩，利用這個程序生成的 David Link 的 2009 復(fù)合計劃：

JEWEL LOVE
MY LIKING HUNGERS FOR YOUR ADORABLE INFATUATION.
YOU ARE MY EROTIC ARDOUR.: MY FOND RAPTURE. MY THIRST
SIGHS FOR YOUR INFATUATION. MY HEART SEDUCTIVELY WISHES YOUR
BREATHLESS LONGING.

YOURS CURIOUSLY

M. U. C.

（由于上面文字過于漏骨，譯者嘗試引申出譯文如下）

我對你的可愛迷戀至極嗅定。

你勾起了我所有對情愛的幻想自娩。

我為你而狂熱。

你的魅力使我對你充滿了渴望渠退。

我的心隨你在而讓我無法呼吸忙迁。

你的追求者

M.U.C

但是圖靈的隨機數(shù)指令幾乎是當(dāng)時的開發(fā)人員崩潰的，因為這種隨機在本身就已經(jīng)很不穩(wěn)定的開發(fā)環(huán)境下又引入了不確定性碎乃。人們希望在軟件中得到一致性的結(jié)果姊扔，但是用這種指令的軟件永遠不可能得到可重復(fù)的一致性結(jié)果，這也使得軟件測試幾乎變的不可行荠锭。

那么如果隨機數(shù)生成器可以由一個確定性的函數(shù)來替代會怎樣呢旱眯？如果在給定一個確定的初始條件晨川，每次可以生成同樣的隨機序列會怎樣呢证九？這就是偽隨機數(shù)生成器（PRNG）。

偽隨機數(shù)生成器（PRNG）

偽隨機數(shù)生成器是由馮諾依曼在 1946 年創(chuàng)造的共虑。他的基本思想是從一個隨機數(shù)種子開始愧怜，對其平方，然后取中間值妈拌。接下來重復(fù)對得到的數(shù)取平方并取中間值的過程拥坛，就會得到一個具有統(tǒng)計意義屬性的隨機數(shù)序列了蓬蝶。這也就是廣為人知的平方取中法。

然而猜惋，馮諾依曼的方法并沒有經(jīng)得住時間的考驗丸氛，因為不論從什么隨機種子開始，序列最終都會落入某個短循環(huán)序列著摔，比如：8100,6100,4100缓窜，8100，6100,4100……谍咆。

序列中的數(shù)字是依賴于前一個數(shù)字的這種生成函數(shù)禾锤，上面的重復(fù)循環(huán)問題是不可避免的。但是如果說這個循環(huán)間隔非常非常大摹察，對實際應(yīng)用并不會產(chǎn)生影響恩掷，那會怎樣呢？

1949 年供嚎，數(shù)學(xué)家 D.H.Lehmer 利用線性同余生成器（LCG）實現(xiàn)了這一思路黄娘。下面給出的是基于 Lehmer 的方法所實現(xiàn)的一種樸素 PRNG，叫做中央隨機數(shù)生成器克滴，使用 JavaScript 在 1995 年寫的寸宏。

    // The Central Randomizer 1.3 (C) 1997 by Paul Houle (paul@honeylocust.com)
    // See:  http://www.honeylocust.com/javascript/randomizer.html
    rnd.today=new Date();
    rnd.seed=rnd.today.getTime();
    function rnd() {
      rnd.seed = (rnd.seed*9301+49297) % 233280;
      return rnd.seed/(233280.0);
    };
    
    function rand(number) {
      return Math.ceil(rnd()*number);
    };

注意代碼中的魔法數(shù)字（如 9301 等），這些數(shù)字（通常是質(zhì)數(shù)）是用來最大化重復(fù)區(qū)間的——上面所提到的自我重復(fù)的循環(huán)區(qū)間偿曙。這種 PRNG 使用當(dāng)前時間作為種子值氮凝，重復(fù)區(qū)間可以達到 2 的 31 次方。

這種中央隨機生成器發(fā)明之初非常流行望忆，因為那時的 JavaScript 1.0 還沒有內(nèi)置 Math.random() 函數(shù)罩阵，當(dāng)時的 Web 1.0 環(huán)境下，大家都想讓自己的 banner 廣告隨機旋轉(zhuǎn)启摄。一個開發(fā)者 Paul Houle 說道：“它在很多情況下已經(jīng)很好用了稿壁，但是不能使用它來做保密使用”。

對 PRNG 的更高要求

互聯(lián)網(wǎng)確實需要保密歉备。SSL 誕生在 1995 年傅是，它的加密方案需要高質(zhì)量的 PRNG。它的發(fā)展也直接導(dǎo)致了一段時間的 PRNG 野蠻創(chuàng)新時期蕾羊。如果你回頭看一下所有的隨機數(shù)生成器的專利喧笔，你可能會感受到就像現(xiàn)代版的第一次制造飛機的浪潮一樣。

20 世紀(jì) 90 年代中期的 CPU 是沒有內(nèi)置隨機數(shù)生成指令的龟再，這使得那時候好的隨機種子特別難得书闸。本來這問題也不大，不過當(dāng)飛利浦的 Hallam-Baker 發(fā)現(xiàn) Netscape（當(dāng)時市場上的巨頭）的 SSL web 服務(wù)器使用了“當(dāng)前時間 + 一組特殊 ID”組合作為種子的時候利凑，這個問題變成了一個切身體會到的安全問題了浆劲。Hallam-Baker 展示了一個攻擊者很容易猜到種子值嫌术，并且對他們所拿到的服務(wù)器流量進行解密的過程。猜種子值是一個非常常規(guī)的攻擊手段牌借，盡管這種手法現(xiàn)在變得越來越困難度气。這里給出 2009 年在 Hacker News 上的一段非常經(jīng)典的攻擊演練。

到了 1997 年膨报，計算機科學(xué)家們厭倦了生成隨機數(shù)所受限的條件蚯嫌，來自 SGI 的一個團隊發(fā)明了 LavaRand，它是用一個網(wǎng)絡(luò)攝像頭來對著熔巖燈拍照丙躏。從攝像頭中過來的圖片數(shù)據(jù)是一個真實的熵源——像圖靈那樣的真實隨機數(shù)生成器（TRNG）——可以以 165kb/s 的速率生成隨機數(shù)择示。一如當(dāng)時硅谷的風(fēng)格，熔巖燈平臺很快拿到了專利晒旅。

AutoDesk 的創(chuàng)始人 John Walker 在全世界范圍內(nèi)推廣他的 HotBits栅盲，這是一種“隨機數(shù)即服務(wù)”的應(yīng)用，背后原理是蓋革計數(shù)器來保證其量子隨機性废恋。1998 年成立的 Random.org 為互聯(lián)網(wǎng)提供真正的隨機數(shù)谈秫。他們提供的服務(wù)包括真正的拋硬幣隨機、骰子隨機和卡牌洗牌隨機等鱼鼓。

上面所提到的大多數(shù)算法后來都無人問津了拟烫，但是一個叫做梅森旋轉(zhuǎn)隨機數(shù)生成器（The Mersenne Twister）的軟件 PRNG 鶴立雞群，它是由松本真（Makoto Matsumoto）和西村 拓士（Takuji Nishimura）在 1997 年發(fā)明的迄本。它完美地平衡了性能和隨機數(shù)的質(zhì)量硕淑，并且經(jīng)受住了時間的考驗。其基本思想是基于線性反饋移位寄存器（LFSR）嘉赎，產(chǎn)生一個循環(huán)周期非常長的確定性序列置媳，循環(huán)周期能夠達到 21??3?? 1。在當(dāng)前的編程語言中公条，這種算法依舊是默認(rèn)的 PRNG拇囊。

在 1999 年，隨機數(shù)市場發(fā)生了一個巨大的變化靶橱，Intel 在其 i810 芯片組上集成了芯片級的隨機數(shù)生成器寥袭。這樣使得新的服務(wù)器都自帶熱噪聲的本地源隨機數(shù)生成能力——真正的隨機數(shù)生成器（TRNG）。這很偉大关霸，但是它始終沒有軟件 PRNG 快传黄，所以加密軟件依舊不得不依賴于偽隨機數(shù)生成器（PRNG）。

這就把我們帶到了“密碼安全 PRNG”（CSPRNG）（這些討厭的縮寫谒拴！難怪很多人認(rèn)為計算機科學(xué)很煩人）尝江。CSPRNG 對于 SSL 特別重要。那么 CSPRNG 的原理是什么呢英上？這里有一份 131 頁的論文來介紹 CSPRNG炭序。祝你在里面閱讀愉快。

不言而喻苍日，CSPRNG 是一個強需求惭聂。梅森旋轉(zhuǎn)隨機數(shù)生成器并不是一種 CSPRNG，因為如果可以給定大量的先前序列樣本相恃，后面的數(shù)字是可以預(yù)計的出來辜纲。

時間再拉近一些，2012 年拦耐，Intel 為 TRNG 增加了 RDRAND 和 RDSEED 指令耕腾，具有 500MB/s 的生產(chǎn)效率。但是 RDRAND 的完整性一直被質(zhì)疑杀糯，里面是不是有某些缺陷扫俺？或者是為美國國家安全局內(nèi)置了什么東西？沒人確切地知道這個問題的答案固翰，我猜某些地方的某些人一定知道狼纬，可是他們也一定不會公開。

開源硬件隨機數(shù)生成器

近些年開源硬件 TRNG 也逐漸顯露頭角骂际。它們廣受歡迎得益于其設(shè)計的透明化：你可以自己構(gòu)建線路疗琉，也可以用現(xiàn)有的組件搭建。完全的透明化使得對硬件隨機數(shù)生成沒有任何的擔(dān)心和疑慮歉铝。REDOUBLER和無限噪聲 TRNG是兩個開源硬件隨機數(shù)生成器盈简，鏈接中給出他們的 Github 源碼地址。

結(jié)尾

今天太示，依舊有關(guān)于對隨機數(shù)生成方法選擇的爭論送火，在操作系統(tǒng)內(nèi)核、編程語言和安全包（如 OpenSSL 或者 OpenSSH）方面均未停止先匪。有許多不同的算法聚焦于不同的特點上种吸，如速度、占用空間呀非、安全性等方面坚俗，也有一些安全專家依舊在尋找攻破已有算法的方法。但是對于我們?nèi)粘５氖褂脕碇v岸裙，在大多數(shù)的操作系統(tǒng)中你可以放心地使用 /dev/random猖败，或者編程語言中你可以隨心地使用 rand() 函數(shù)，都能給你帶來很好的使用體驗降允，并且你這么做恩闻，阿蘭·圖靈也會很開心。

歡迎大家關(guān)注我的前端大哈 - 知乎專欄剧董，定期發(fā)布高質(zhì)量前端文章幢尚。

我最近正在寫一本《React.js 小書》破停，對 React.js 感興趣的童鞋，歡迎指點尉剩。