亂數的核心是數的隨機性。隨機性是資訊安全領域，尤其是密碼學領域一個很關鍵的研究問題。在密碼學中，對一個序列的隨機性是這樣定義的：“看起來是隨機的，即能通過我們所能找到的所有正確的隨機性檢驗。”
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 個位元/位），無論您使用的是哪種演算法，永遠要保證熵的品質，永遠都不要降低熵。
最后說一句，位元幣本身是安全的，不安全的是錯誤的解決方案和有問題的熵。
uj5u.com熱心網友回復：
第一次發現這個神奇的地方。。。。。好像挺好玩的轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/19968.html
標籤：區塊鏈技術