從密碼學的隨機性探討區塊鏈與隨機數

隨機數的核心是數的隨機性。隨機性是信息安全領域，尤其是密碼學領域一個很關鍵的研究問題。在密碼學中，對一個序列的隨機性是這樣定義的：「看起來是隨機的，即能通過我們所能找到的所有正確的隨機性檢驗。」

1.背景介紹

隨機數雖然看起來不起眼，但它卻是信息安全的基礎之一。在區塊鏈中，隨機數有很多的應用場景，例如抽獎活動、驗證碼、Token、密碼應用場景等。

隨機數的核心要義

隨機數的核心是數的隨機性。隨機性是信息安全領域，尤其是密碼學領域一個很關鍵的研究問題。在密碼學中，對一個序列的隨機性是這樣定義的：「看起來是隨機的，即能通過我們所能找到的所有正確的隨機性檢驗。」

這個序列是不可預測的，即使給出產生序列的演算法或者硬體設計和以前產生序列的所有知識，也不可能通過計算來預測下一個比特是什麼或者計算代價很大幾乎不可實現。

隨機性在密碼學中佔有重要的地位，幾乎所有的密碼演算法和協議都要用到一些對攻擊者來說必須是秘密的數據。比如對一個密碼演算法來說，如果將秘密寓於密鑰之中，那麼密鑰就是秘密，包括對稱密碼演算法（DES、AES、IDEA 等）的密鑰和非對稱密碼演算法（RSA、DSA、Diffie-Hellman 等）的私鑰等，而這些密鑰必須是隨機數。對於唯一已經證明了絕對安全性的一次一密系統來說，其安全性就依賴於隨機的密鑰。

隨機數的核心要義是不可預測性，這也是對隨機數最基本的底線要求。一旦隨機數被人預測到，則基於隨機性的安全體系將立刻崩塌。

隨機數發生器

既然隨機數如此重要，那麼隨機數生成器的地位也就不言而喻了。隨機數生成器用來產生一個位序列，這個位序列的隨機性就很重要。如何才能生成均勻的隨機位序列呢？

擲骰子被認為是產生隨機數的典型示例。統計學家 Francis Galton 在 1890 年的《自然》雜誌中提出「在所有的產生隨機數的事物中，我認為沒有什麼能夠超越骰子了。」 在搖骰子的過程中，骰子在容器中不斷地翻滾、互相撞擊，以各種形式和角度與容器壁發生碰撞，在容器中的位置和形態在外界看來都是不可預知的，各種偶發因素一起參與搖骰子的過程中，比如容器哪怕只發生一次晃動，外界都不可能知道裡面到底是什麼形態。

迄今為止發現最早的骰子（4 個面）來自中東的一座公元前 24 世紀的墳墓里。公元前 1100 年的中國，一些「先知」利用火燒龜殼產生的隨機龜裂對未來做預測。又過了幾個世紀，在中國誕生了易經占卜法，利用 49 蓍草法進行占卜，其操作的分裂過程很類似於拋硬幣。

真偽隨機生成器

隨機數生成器有真隨機和偽隨機之分。

只滿足「隨機數的核心要義」中所講的隨機性要求的其實是偽隨機數生成器。偽隨機數生成器是一個確定性演算法，用一個長度為 k 的二進位序列作為輸入，演算法就能產生長度為 m（m>>k）的隨機數序列，偽隨機生成器的輸入稱為生成器的種子。

實際上，偽隨機數生成器產生的隨機數並不是真的隨機。偽隨機數生成器具有周期性，其產生的隨機數序列總會產生重複，不過如果生成器的周期足夠長（至少要遠遠大於可能採集的隨機數的長度），那麼這個隨機數生成器產生的局部的隨機序列也就和真隨機序列看起來沒有什麼區別了。

真隨機數生成器在滿足「數的隨機性」以及「序列不可預測」這兩個要求之外，還要滿足第三個要求：

這個序列不能重複產生，即使在完全相同的操作條件下用完全相同的輸入對序列發生器操作兩次，也將得到兩個完全不同的、毫不相關的位序列。

滿足了這三個要求的隨機數生成器，其產生的隨機數是不可重現的，即使是你自己也無法再次產生同樣的隨機數。

偽隨機數生成器 PRNG(Pseudo Random Number Generator)

偽隨機數生成器是由馮諾依曼在 1946 年創造的。他的基本思想是從一個隨機數種子開始，對其平方，然後取中間值。接下來重複對得到的數取平方並取中間值的過程，就會得到一個具有統計意義屬性的隨機數序列了。這也就是廣為人知的平方取中法。

然而，馮諾依曼的方法並沒有經得住時間的考驗，因為不論從什麼隨機種子開始，序列最終都會落入某個短循環序列，比如：8100,6100,4100，8100，6100,4100……。序列中的數字是依賴於前一個數字的這種生成函數，上面的重複循環問題是不可避免的。但是如果說這個循環間隔非常非常大，對實際應用並不會產生影響，那會怎樣呢？

1949 年，數學家 D.H.Lehmer 利用線性同餘生成器（LCG）實現了這一思路。這種隨機生成器發明之初非常流行。一個開發者 Paul Houle 說道：「它在很多情況下已經很好用了，但是不能使用它來做保密使用」。

目前看到的大部分庫的默認實現都是線性同餘。至於線性同餘的弱點也是很明顯的，既然是同餘那麼就在一個周期後，你產生的隨機數又會重複出現了。這有什麼影響嗎？

如果僅僅是做個測試好玩，沒啥影響，但如果你是根據數字生產卡號、密碼，那麼影響就大了。當年一些電話卡被破解就是這樣來的。這個就涉及偽隨機的演算法循環長度。什麼叫循環長度？就是如果第一次產生數字 55，第二個產生數字 107，那麼循環多少次後，會繼續產生，55，107……這樣的序列。目前大部分簡單演算法的循環長度都是 2^32 左右。

那麼有沒有更好的演算法。更好的循環長度讓人無法破解呢？當然有，就是上面演算法中的其他。數學界畢竟人才濟濟。推薦一個數學家提出的 MT 隨機數演算法，全稱是 Mersenne Twister 梅森旋轉演算法。

這個演算法是日本科學家 Makoto Matsumoto（松本真）和 Takuji Nishimura（西村拓士）在 1997 年開發的，而且還是目前可以看到最好隨機數演算法。該演算法基於有限二進位欄位上的矩陣線性遞歸 field F_{2}，可以快速產生高質量的偽隨機數，修正了古典隨機數發生演算法的很多缺陷。MT 演算法的循環長度能到多少？一個常用的實現是產生 32 位數字，循環長度 2^19937。一般來說只要你不搞天文運算。都可以輕鬆應對了。更主要的是，該演算法的實現性能還非常高。MT 演算法的普通實現不比我們常用的函數庫的 rand 慢多少，大約只慢 10%，如果針對特定的處理器進行優化，還有非常大的進步空間。

大部分程序和語言中的隨機數，確實都只是偽隨機。是由可確定的函數，通過一個種子（常用時鐘）產生的。這意味著：如果知道了種子，或者已經產生的隨機數，都可能獲得接下來隨機數序列的信息（可預測性）。

不正確地使用偽隨機數生成器會導致驚人的安全性問題。眾所周知，早前 Netscape Navigator 的大量安全漏洞直接就是來自於不適當的隨機數生成器。另一個比較典型的例子是 Reliable Software Technology 的網際網路賭博揭秘事件，這個揭秘允許欺騙性的玩家可以實時計算每人手中確切的牌。它的缺陷存在於用來生成每副牌的洗牌演算法中。在這段代碼中，調用 randomize()在每副牌生成前生成一副隨機牌。隨機數生成器的種子是按照系統時鐘，用午夜後的毫秒數選取的。這意味著隨機數生成器的輸出是容易預測的。

正如所討論的，隨機數生成器的可預測性是一個很嚴重的安全性問題。由此產生了密碼安全偽隨機數生成器（Cryptographically Secure Pseudo-Random Number Generator，簡稱 CSPRNG）。顧名思義，該隨機數發生器可以產生在密碼學意義上安全的隨機數。不言而喻，CSPRNG 是一個強需求。梅森旋轉隨機數生成器並不是一種 CSPRNG，因為如果可以給定大量的先前序列樣本，後面的數字是可以預測出來的。

硬體隨機數生成器 HRNG(Hardware Random Number Generator )

通過對偽隨機數生成器的分析，我們知道偽隨機數通常會產生很嚴重的安全後果。原因是確定性的機器很難實現隨機。真隨機數生成器必須是非確定的，作為旁觀者即使知道設備使用的演算法也永遠無法以任何一致性猜測到設備的輸出。例如，如果設備輸出一系列 0 和 1，0 和 1 在任何特定輸出中出現的機會應該相等。即使掌握了設備內部工作的全部知識，任何猜中的可能性也只有 50% 左右。

構建真隨機數生成器的最佳辦法就是使用好的物理度量來生成隨機數。許多自然現象就具備這種條件。其訣竅就是它們必須有一些可測量的特性，而且行為至少要儘可能隨機。

某硬體隨機數生成器生成的隨機數據

一個典型的例子是 Unix 內核中的隨機數發生器（/dev/random），理論上它能產生真隨機。即這個隨機數的生成，獨立於生成函數，這時我們說這個隨機數發生器是非確定的。具體來講，Unix 維護了一個熵池，不斷收集非確定性的設備事件，即機器運行環境中產生的硬體噪音，來作為種子。比如說，時鐘，IO 請求的響應時間，特定硬體中斷的時間間隔，鍵盤敲擊速度，滑鼠位置變化，甚至周圍的電磁波等等。直觀地講，你每按一次鍵盤，動一下滑鼠，鄰居家 wifi 信號強度變化，磁碟寫入速度等等信號，都可能被用來生成隨機數。Windows 中也有相對的隨機數生成器，基本的思想是一致的。如果要求更高的話，也有專用的設備，可收集附近的電磁場等環境噪音來產生隨機數。20 世紀 90 年代中期的 CPU 是沒有內置隨機數生成指令的，這使得那時候好的隨機種子特別難得。

到了 1997 年，計算機科學家們厭倦了生成隨機數所受限的條件，來自 SGI 的一個團隊發明了 LavaRand，它是用一個網路攝像頭來對著熔岩燈拍照。從攝像頭中過來的圖片數據是一個真實的熵源，可以以 165kb/s 的速率生成隨機數。測量放射性衰變也是隨機數的一個比較好的來源。它根本不易產生偏差，只會帶來相對較小的自然偏差。每當電子 Geiger 計數器檢測到放射性衰變時，它就會生成一個脈衝。衰變之間的時間是一個實足的、純粹的隨機部分。尤其是，沒有人可以預測到下一次衰變的時間大於還是小於自上次衰變以來的時間，那就產生了一位隨機信息。

在 1999 年， Intel 在其 i810 晶元組上集成了晶元級的隨機數生成器。這樣使得新的伺服器都自帶熱雜訊的本地源隨機數生成能力。

我們知道溫度高於絕對零度的原子都存在熱運動，在集成電路里這些原子的熱運動會在電路里產生雜訊，雜訊會使得電路中的電壓存在微小的起伏，Intel 的 TRNG 就是通過放大這些微小的起伏來產生隨機數。2012 年，Intel 為 TRNG 增加了 RDRAND 和 RDSEED 指令，具有 500MB/s 的生產效率。但是 RDRAND 的完整性一直被質疑，裡面是不是有某些缺陷？或者是為美國國家安全局內置了什麼東西？沒人確切地知道這個問題的答案。

硬體隨機數生成器也有不少缺點。首先就是產生隨機數的速度很低，其次是電路系統里有很多不同的雜訊，但並不是所有雜訊都是隨機的，比如電源雜訊中很大一部分就是和系統時鐘強相關的。而硬體隨機數生成器是一個放大極小信號的電路，它對外界干擾是極其敏感的，為了避免外界非隨機信號的干擾必須要耗費不少功率和面積在屏蔽上。所以加密軟體依舊不得不依賴於偽隨機數生成器（PRNG）。

量子隨機數生成器

事實上，任何基於經典物理過程所產生的隨機數本質上都不是真隨機的， 包括拋硬幣、上面講到的硬體隨機數生成器。經典系統中的隨機性都是「表面隨機性」，即事件表面上看似具有隨機性，而本質上並不是隨機的，只是確定性事件的概率組合。它之所以表現出隨機性，是因為觀察者對系統整體運作機制的不完全了解。由表面隨機性所產生的隨機數並不是真正隨機的。

現代物理學的發展讓人們把目光轉向量子領域。「量子」是一個不可分割的基本個體，是構成現實事物的微小能量和物質，如光子、原子、電子都是「量子」的組成微粒。量子力學是研究微觀世界力學規律的理論，其正確性已經逐步得到證實。研究表明，微觀粒子的狀態具有「內稟隨機性」。也就是說，其隨機性不是因為缺乏對系統的了解而造成的，而是微觀粒子固有的特性。利用這種內稟隨機性，可以產生真正的隨機數，即「真隨機數」(或稱為「內稟隨機數」)。

根據經典力學製造的硬體隨機數生成器設備要確保實現公平的不可預測性很困難。假設一個隨機數生成器的供應商在製造設備時可能採取了某些策略按自己的利益影響著它的輸出結果，甚至是事先預設一些(看起來隨機的)比特串存儲在設備中，使得輸出的序列對於供應商來說是部分已知的甚至是完全已知的，即輸出結果對供應商來說不滿足不可預測性。

因此，密碼系統中必須要保證所產生的隨機數與其它外部變數完全無關，即包括設備供應商在內的其他任何人都不能獲知該隨機數的任何信息。這一點在經典世界中是難以實現甚至無法想像的。量子密碼的發展有可能實現設備無關量子隨機數擴展方法，可以保證所產生的隨機數與外部變數無關。

區塊鏈與隨機數

隨機數對於區塊鏈技術來說很關鍵。本質上，分散式賬本的核心問題就是隨機選擇出塊人的問題，這個隨機性要能被全網確認，並且不能被操控，也不能被預測，否則惡意節點通過操控這個隨機數就可以操控長鏈，從而實現雙花攻擊。

PoW 的方案是讓大家進行算力競賽，設置一個計算哈希的難題，誰先算出來誰贏，算力高的贏的概率高，算力低的贏的概率低，以這樣的方式保證勝出者是隨機的。投入的算力能夠體現在哈希值上，這樣全網能夠驗證，並選擇包含最多算力的那條鏈。惡意節點只能通過提升自己的算力來增加攻擊成功的概率。

PoS 的方案是選舉，大家不用浪費電力去進行算力競賽，而是文明一點，隨機選舉一個節點來出塊，並且被選中的概率和它擁有的份額相關。如果「隨機」這一步沒有問題的話，惡意節點只能通過增加自己的份額，增加自己被選中的概率，從而增加雙花攻擊的成功概率。這裡有一點比 PoW 的方案要好就是，要實現攻擊，先得成為持幣大戶，如果攻擊成功幣價大跌，攻擊者也會承受最大的損失。而 PoW 方案中雖然算力要花錢，但是如果攻擊者沒有持幣，那麼他的利益和幣價不一定是正相關的，不能排除仍然存在攻擊的動力。

那麼接下來的核心問題就是，這個不能被操控不能被預測的隨機數從哪來。

傳統地 PoS 方案嘗試從鏈上現有的數據入手，比如使用上一個區塊的哈希值，上一個區塊的時間戳等等來作為隨機數的來源，但這些會帶來額外的安全風險。因為區塊本身的信息就是節點寫進去的，然後又要根據裡面的信息來選舉後續的出塊者，存在循環論證的嫌疑，安全性不會太好。這也是傳統地認為 PoS 方案不如 PoW 可靠的部分原因。

從資訊理論的角度談區塊鏈中的隨機問題

熵（Entropy）在物理學中用於度量一個熱力學系統的無序或混亂程度（參考熱力學第二定律），當它被引入到資訊理論（計算機科學）時，則被用來衡量信息的不確定性（不可預測性），簡單的說也就是「隨機性」。

假設有一枚「理想」的硬幣（拋出正面和反面的幾率相等），每一次拋硬幣都是獨立的、不可預測的，其結果不是正面、就是反面（0 和 1），那麼這個拋硬幣事件的熵就是 1 個比特/位，拋 256 次的熵就是 256 個比特/位。

暫時拋開那些複雜的定義、公式，「熵」其實就是那麼簡單，從科普的角度，我們只需要了解一個對於密碼學來說的重要定律：任何演算法（包括那些符合密碼學規範的偽隨機數演算法）只能是「維持」熵、甚至有可能會「降低」熵，但一定不能「增加」熵！記住這一點至關重要，歷史上發生過的無數次隨機數問題基本上都源於對這一點的忽視，我們暫且命名為「演算法不增熵」定理。

以曾經發生的 http://blockchain.info 的隨機數問題為例，http://blockchain.info 使用的 RC4 演算法（http://en.wikipedia.org/wiki/RC4，因版權問題通常也被稱為 ARC4）是一個廣泛使用的密碼學演算法，通常被用來生成偽隨機數的信息流。ARC4 演算法有一個非常「好」的特性，即：只需要一個種子（哪怕這個種子只有兩位，0 和 1），就能生成「無限多」的隨機數，你只需要反覆的對結果進行 ARC4 運算即可。比如說，使用 0 或者 1 初始化 ARC4 數組，然後反覆的進行 ARC4 運算，您都可以得到任意長度的數列，數列中的每一個元素都是 0-255（8 位）的數字，出於篇幅限制，我們在這裡只運行了 256 次的 ARC4next 方法。

0:

[222,24,137,65,163,55,93,58,138,6,30,103,87,110,146,109,199,26,127,163,240,204,235,151,69,43,77,50,39,150,95,158,168,204,117,7,109,159,185,197,65,122,165,203,48,252,34,25,139,52,152,45,187,98,158,192,75,79,139,5,160,113,8,80,146,160,195,88,74,72,228,163,10,57,123,138,205,29,0,158,200,125,104,17,242,44,244,156,163,229,147,84,185,69,21,53,162,24,122,134,66,108,202,125,94,130,62,186,0,68,18,103,18,87,184,216,96,174,76,189,76,73,6,187,197,53,239,225,88,127,8,219,51,149,92,219,203,173,155,16,245,63,196,229,44,89,21,101,81,132,135,254,8,77,14,63,3,222,188,201,218,28,233,13,8,92,45,138,25,216,55,48,134,22,54,146,20,43,216,252,93,122,115,73,106,142,89,238,126,207,107,148,6,99,244,166,190,230,91,210,200,92,70,152,108,27,239,52,144,211,123,56,218,133,211,46,151,57,203,35,74,43,231,64,235,8,137,54,33,153,175,204,50,131,85,153,13,79,137,251,99,195,228,81,116,172,100,77,71,2,71,63,151,209,157,98]

1:[6,8,14,14,24,32,41,41,57,51,73,87,102,118,135,131,161,181,202,224,247,102,17,124,76,104,133,163,194,226,163,73,108,38,57,127,166,206,23,65,224,71,165,211,186,87,52,103,128,180,137,239,127,183,151,209,60,44,48,147,210,142,207,149,216,104,173,167,238,239,94,230,67,143,76,236,63,143,154,197,12,17,10,119,104,46,106,197,42,3,171,116,97,215,94,138,225,97,198,118,100,125,26,61,58,230,88,198,0,112,124,71,207,55,97,128,47,75,153,130,158,95,117,7,105,226,176,130,239,90,49,125,20,247,71,95,234,13,154,98,178,210,63,236,243,36,147,202,101,88,53,9,222,9,250,163,15,184,130,181,167,249,231,37,187,125,231,174,239,43,92,255,255,154,201,48,177,206,22,183,105,92,9,8,94,51,211,200,121,189,64,9,97,248,174,13,201,173,209,196,15,129,227,3,127,184,41,69,165,199,122,90,33,63,21,160,164,205,37,93,222,211,137,199,18,135,107,7,83,10,230,113,108,41,195,34,181,63,68,164,52,214,97,63,178,22,55,192,80,153,210,224,91,240,104,165]

這個數列中的任意一段（32 個元素即 256 位），都可以被用來作為比特幣私鑰或簽名時使用的 k 值，他們看起來都很「隨機」。可惜，無論我們進行了怎樣的運算，這個數列的熵都永遠小於等於 1 個比特（即 0 和 1）。也就是說，其它人，如果能覆蓋全部的熵，進行相同的運算，也能夠計算出您的全部私鑰和全部 k 值。

http://blockchain.info 出問題時的熵是 8 個比特（0-255），也就是說，您只需要使用這 256 個數字作為種子，反覆的進行 ARC4 運算，就能覆蓋出問題的時間段里 http://blockchain.info 用戶所使用的全部隨機數（考慮到瀏覽器緩存和 CDN 緩存，問題時間段的長度可能是數周）。當然，您還可以基於代碼進行一些優化，只考慮部分可能出現的情況，比如說每進行 33 次 ARC4next 生成一個隨機數，或者是間隔 256 次 ARCnext 後再用 33 次 ARCnext 來生成一個隨機數。

例如，上述種子 0 所對應的數組中，我們可以進行如下簡單的計算：

取開頭的 33 個元素：[222,24,137,65,163,55,93,58,138,6,30,103,87,110,146,109,199,26,127,163,240,204,235,151,69,43,77,50,39,150,95,158,168]；

按照 http://blockchain.info 的演算法（他們自己定義的 BigInteger 類型），將第一個元素替換為 0，最後一個元素加 1，即得到結果數組：[0,24,137,65,163,55,93,58,138,6,30,103,87,110,146,109,199,26,127,163,240,204,235,151,69,43,77,50,39,150,95,158,169]；

使用這個結果數組可以得到一個 k 值 188941a3375d3a8a061e67576e926dc71a7fa3f0cceb97452b4d3227965f9ea9；

再使用 ECDSA 演算法計算出該 k 值所對應的 r 值：0dcc0b9a668d4b7b8cbde71288bf32bb659bd7fda1b66172ce97fda6f8b0a06e；

這個 r 值在整個區塊鏈的交易簽名中一共出現過 5 次，這 5 筆交易所對應的私鑰均已暴漏；

比如說，地址：19hXXVpwhmu1frqKwF1VZdNfqtGrMvg87n，交易 hash：b2b63f29c379ff830f45a5165b0e374093207ddca3e737562617c1d526ef4c65，該筆交易簽名就是這個 r 值，利用區塊鏈上的數據，任何人都能夠很容易的計算出該地址的私鑰：5JHyRh8hwyjWjt3RR3B9X6oJt9mzJZwFe8YnF7W22XcSHdD6rxK；

搞定。看到這裡，我們可以知道，根據前面的「演算法不增熵」定理，對於比特幣所需要的隨機數來說，僅僅使用密碼學安全的偽隨機數演算法還是不夠的，您需要的是「足夠」的熵（比特幣需要的是 256 個比特/位），無論您使用的是哪種演算法，永遠要保證熵的品質，永遠都不要降低熵。

最後說一句，比特幣本身是安全的，不安全的是錯誤的解決方案和有問題的熵。