密碼學的骰子——隨機數

做開發的工程師們應該或多或少都接觸過隨機數，可能認為它就是一個隨機生成的數字嘛，使用時也很簡單，只要呼叫開發語言提供的函式即可。但實際上隨機數後面還是有著比較複雜但也有趣的知識點的。

根據一般定義，隨機數應該具有以下三個性質：隨機性，不存在統計學偏差，是完全雜亂的數列，即分佈均勻性和獨立性；不可預測性，不能從過去的隨機數數列推測出下一個出現的數；不可重現性，不能重現相同的數列。

我們在平時程式設計開發裡用到的隨機數，一般都只滿足第一個條件，這種只滿足隨機性分佈的隨機數，就叫做

偽隨機數

或弱偽隨機數

。這是因為程式語言提供的隨機數生成方法（學名叫偽隨機數生成器）是靠軟體演算法實現的，既然是演算法，那就必定遵循了一定的規律，也就有被預測的可能。像常用到的C語言的rand庫和Java的java。util。Random類，就是採用了線性同餘演算法生成隨機數。雖然名字好像不好聽，但偽隨機數已經滿足大多數應用場景的需求了。

但對於密碼學來講，偽隨機數就遠遠不夠了。除了隨機性，密碼學要求的隨機數還要具備不可預測性。我們把具有這兩個性質的隨機數叫做

密碼學安全的偽隨機數或強偽隨機數

。在密碼學中隨機數的用途很廣，主要有以下幾個方面：

生成金鑰：無論是對稱金鑰還是公私鑰對，生成過程中都有隨機因子參與其中，以增加金鑰被破解的難度；

生成Nonce：Nonce是Number used once或Number once的縮寫，意思是隻用一次的數字。透過在資料里加入Nonce，哪怕是對同樣的明文加密或簽名，都可以保證每一次的加密或簽名結果都不相同，以防止重放攻擊，這一點對於身份驗證系統尤其有意義。所謂重放攻擊就是指攻擊者截獲了你提交的驗證資訊，然後將資訊原封不動的提交給驗證系統，冒充你進行身份驗證。

加鹽：加鹽都是Nonce的拓展應用，基本原理也是在加密時嚮明文摻入隨機數因子，以增加加密結果的不可預測性。在密碼學裡，有這樣一個基本原則：加密結果儘量不要保留原資料的規律。舉個例子：對稱加密都是採用分組加密模式，也就是將原文資料分成組，對每一組進行加密，最後將得到的多組密文合併起來。下圖中最左邊是原圖，中間就是用對稱分組加密的方式生成的密文。可以看出，雖然作為分組的原圖中每一塊區域的都加密了，但顏色一致的區域加密後的資料也是一樣的，組合成的密文影象還是帶有原圖的規律，我們依然可以看出原圖的大體內容。針對這個問題，可以在分組資料中加入隨機數，使得即使是同樣的資料，加密後的結果也不一樣。最右邊就是經過上述處理後加密的結果，可以看出加密後圖像已完全沒有任何規律可循了。對稱加解密的初始化向量或非對稱加解密中的Padding都屬於這種加鹽應用。

加一點鹽，味道更好

Blinding：與加鹽的原理類似，只不過是針對密文。話說有一種RSA攻擊方式叫做時序攻擊，基本方法就是攻擊者根據解密所花費的時間確定私鑰，比如這一位私鑰為0時，解密花1ms，私鑰為1時，解密要花10ms，攻擊者透過構造不同密文，統計解密花費的時間，理論上可以推算出私鑰。針對這種攻擊，可以先將密文與隨機數進行合併，再送給私鑰解密，這樣就無法透過時間推算出私鑰了。這種方法叫Blinding。

綜上所述，密碼學就是利用了隨機數的隨機性和不可預測性，提高金鑰和加解密過程的複雜性和不可預測性，以增加被攻破的難度。

那麼，密碼學安全的偽隨機數或強偽隨機數如何生成呢？前面分析過了，靠軟體演算法生成是不靠譜的。科學已經證明，如果要實現不可預測性的隨機數，需要藉助物理規律、人品或者老天爺，比如擲錢幣、骰子、滑動滑鼠的軌跡、電子元件噪聲、核裂變、量子理論、大氣輻射等等。以它們為隨機源生成的隨機數，是滿足密碼學安全要求的。實際應用中一般是採用基於電子元件的噪聲原理的隨機數發生器晶片。而普通計算機使用的CPU或主機板基本是沒有這種隨機數發生器功能的，因此，在密碼學的應用中，隨機數發生器晶片成了USBKey的標配，安全的運算，不能沒有它的參與。你看，又一次迴歸到了“私鑰永遠不出KEY”的金科玉律。

所謂“有一利必有一弊”，強隨機數雖然安全，但缺點就是運算速度太慢。我們做過一個實測，在同一臺PC主機和生成程式的情況下，採用USBKey生成1000組，每組128KB的隨機數，共計耗時約12個小時；採用軟體函式庫生成同樣數量的隨機數，只用了不到一分鐘。

最後聊聊真隨機數，

真隨機數

就是除了隨機性和不可預測性外，還需具有不可重複性，也就是產生的隨機數列，不可能再次出現。但是在給定邊界條件下，是不存在真隨機數的，因為隨機數範圍有邊界，那計算出的隨機數列必然有重複。不過如果邊界條件十分複雜且難以捕捉，我們也可以認為它是真隨機數。很多偽隨機數列從區域性看，都展現了完美的隨機性，但如果你把這個隨機數列拉長，就會發現它的分佈也是有規律的。而真隨機數，就是把數列拉的無限長，也是沒有任何規律所循。這也就是測試一個隨機數發生器質量時，樣本資料量要足夠大的原因。

其實說到這，不可避免地出現了一個根本問題：世界上到底有沒有真正的隨機數？前面說過，隨機數的產生有賴於物理現象的隨機性，但我們現在認為隨機的物理現象，是不是隻是因為人類認識不夠，還沒有發現其真正規律？也就是說，這個世界真的是充滿了不可預知的各種混沌，還是有一隻我們看不見的手在操縱著（愛因斯坦老先生說過：上帝不擲骰子）？幸虧我們討論的是密碼學，不是哲學，這個問題頂多想想就好了。雖然真正的隨機數可能不存在，但是有密碼學能夠用的隨機數就已經很好了。