隨機數(shù)

???———— 不可預(yù)測的源泉

使用隨機數(shù)的密碼技術(shù)

?隨機數(shù)的使用場景，比如:

• 生成密鑰
  ?用于對稱密碼和消息的認證碼
• 生成密鑰對
  ?用于公鑰密碼和數(shù)字簽名
• 生成初始化向量
  ?用于分組密碼的CBC、CFB、OFB模式
• 生成nonce
  ?用于防御重放攻擊以及分組密碼的CTR模式等
• 生成鹽
  ?用于基于口令的密碼等；
  為了不讓攻擊者看穿而使用隨機數(shù)，因為“無法看穿”，即不可預(yù)測。

隨機數(shù)性質(zhì)

對隨機數(shù)的性質(zhì)進行分類

• 隨機性 —— 不存在統(tǒng)計學(xué)偏差，是完全雜亂的數(shù)列
• 不可預(yù)測性—— 不能從過去的數(shù)列推測出下一個出現(xiàn)的數(shù)

• 不可重現(xiàn)性—— 除非將數(shù)列本身保存下來，否則不能重現(xiàn)相同的數(shù)列
  上述三個性質(zhì)按順序分別命名為“弱偽隨機數(shù)”、“強偽隨機數(shù)”和“真?zhèn)坞S機數(shù)”

  
  
  隨機數(shù)的性質(zhì).png

隨機性

?所謂隨機性，簡單來說，就是看上去雜亂無章的性質(zhì)。我們可以用偽隨機數(shù)生成器大量的生成0到9范圍內(nèi)的整數(shù)，然后看一看所生成的數(shù)列。如果數(shù)列是像0、1、2、3、4、5、6、7、8、9、0、1、2....這樣循環(huán)不斷，那肯定不是雜亂無章的?；蛘哒σ豢词请s亂無章的，但實際上在數(shù)列中0一次都沒出現(xiàn)過，或者整個數(shù)列一半都是6，這樣的數(shù)列也能算是雜亂無章的。
?如果偽隨機數(shù)列中不存在統(tǒng)計學(xué)偏差，則我們可以認為這個偽隨機數(shù)列是隨機的。判斷一個偽隨機數(shù)是否隨機的方法稱為隨機數(shù)測試，隨機數(shù)測試的方法有很多種。
?一半在電腦游戲中使用的隨機數(shù)只要具備隨機性就可以了。此外，在計算機模擬軟件中使用的隨機數(shù)雖然需要根據(jù)目的來進行隨機數(shù)測試，但也是只要具備隨機性就可以了。然而，密碼技術(shù)中所使用的隨機數(shù)，僅僅具備隨機性是不夠的。
?由于隨機數(shù)會被用來生成密鑰，因此密鑰不能被攻擊者看穿。但是，雜亂無章并不代表不會被看穿，因此，將只具備隨機性的偽隨機數(shù)數(shù)稱為 “弱為隨機數(shù)”。

不可預(yù)測性

?密碼中所使用的隨機數(shù)僅僅具備隨機性是不夠的，還需要具備避免攻擊者看穿的不可預(yù)測性。不可預(yù)測性（unpredictability）。
?所謂不可預(yù)測性，是指攻擊者在制定過去生成偽隨機數(shù)列的前提下，依然無法預(yù)測出下一個生成出來的偽隨機數(shù)的性質(zhì)。其中，“在制定過去生成的偽隨機數(shù)列的前提下.....”是非常重要的一點。
?不可預(yù)測性是通過使用其他的密碼技術(shù)來實現(xiàn)的。例如，可以通過單向散列函數(shù)的單向性和密碼的機密性來保證偽隨機數(shù)生成器的不可預(yù)測性。我們將具備不可預(yù)測性的偽隨機數(shù)稱為強偽隨機數(shù)。

不可重新性

?所謂不可重新性，是指無法重新和某一隨機數(shù)列完全相同的數(shù)列的性質(zhì)。如果除了將隨機數(shù)列本身本身保存下來以外，沒有其他方法能夠重新該數(shù)列，則我們就可以說該隨機數(shù)列具備了不可重現(xiàn)性。
?僅靠軟件時無法生成具備不可重現(xiàn)性的隨機數(shù)列的。軟件只能生成偽隨機數(shù)列，這是因為運行軟件的計算機本身僅具備有限的內(nèi)部狀態(tài)。而在內(nèi)部狀態(tài)相同的條件下，軟件必然只能生成相同的數(shù)，因此軟件所生成的數(shù)列在某一個時刻一定會出現(xiàn)重復(fù)的。首次出現(xiàn)重復(fù)之前的數(shù)列長度稱為周期，對于軟件所生成的數(shù)列，其周期必定是有限的。當(dāng)然，這個周期可能會很長，但總歸還是有限的。凡是具有周期的數(shù)列，都不具備不可重現(xiàn)性。
?要生成具備不可重現(xiàn)性的隨機數(shù)列，需要從不可重新性的物理現(xiàn)象中獲取信息，比如周圍的溫度和聲音的變化，用戶移動的鼠標的位置、鍵盤的輸入的時間間隔、放射線測量儀的輸出值等，根據(jù)從這些硬件中所獲取的信息而生成的數(shù)列，一般可以認為是具備不可重新性的隨機數(shù)列。
?目前，利用熱噪聲這一自然現(xiàn)象，人們已經(jīng)開發(fā)出能夠生成不可重新性的隨機數(shù)的硬件設(shè)備。例如，英特爾的新型CPU中就內(nèi)置了數(shù)字隨機數(shù)生成器，并提供了生成不可重現(xiàn)性隨機數(shù)的RDSEED指令，以及生成不可預(yù)測隨機數(shù)的RDRAND指令。
我們稱具備不可重現(xiàn)性的隨機數(shù)稱為真隨機數(shù)。

偽隨機數(shù)生成器

?隨機數(shù)可以通過硬件來生成，也可以通過軟件來生成。
?通過硬件生成的隨機數(shù)列，是根據(jù)傳感器收集的熱量、聲音變化等事實上無法預(yù)測和重現(xiàn)的自然現(xiàn)象信息來生成的。像這樣的硬件設(shè)備就稱為隨機數(shù)生成器（Random Number Generator ，RNG）。
?而可以生成隨機數(shù)的軟件則稱為偽隨機生成器*（Pseudo Random Number Generator，PRNG）。因為僅靠軟件無法生成真隨機數(shù)，因此要加上一個“偽”字。

偽隨機數(shù)生成結(jié)構(gòu)

?偽隨機數(shù)生成器具有“內(nèi)部狀態(tài)”，并根據(jù)外部輸入的“種子”來生成偽隨機數(shù)列。

偽隨機數(shù)生成器結(jié)構(gòu).png

• 偽隨機數(shù)生成器內(nèi)部狀態(tài)
  ?偽隨機數(shù)生成器的內(nèi)部狀態(tài)，是指偽隨機數(shù)生成器所管理的內(nèi)存中的數(shù)值。當(dāng)有人對偽隨機數(shù)生成器發(fā)出“給我一個偽隨機數(shù)”的請求時，偽隨機數(shù)生成器會根據(jù)內(nèi)存中的數(shù)值（內(nèi)部狀態(tài)）進行計算，并將計算的結(jié)果作為隨機數(shù)的輸出。隨后，為了響應(yīng)下一個偽隨機數(shù)請求，偽隨機數(shù)生成器會改變自己的內(nèi)部狀態(tài)。因此，將根據(jù)內(nèi)部狀態(tài)計算偽隨機數(shù)的方法和改變內(nèi)部狀態(tài)的方法組合起來，就是偽隨機數(shù)生成的算法。
  ?由于內(nèi)部狀態(tài)決定了下一個生成偽隨機數(shù)，因此內(nèi)部狀態(tài)不能被攻擊者知道。
• 偽隨機數(shù)生成器的種子
  ?為了生成偽隨機數(shù)，偽隨機數(shù)生成器需要被稱為種子（seed）的信息。偽隨機數(shù)的種子是用來對偽隨機數(shù)生成器的內(nèi)部狀態(tài)進行初始化的。
  ?偽隨機數(shù)的種子是一串隨機的比特序列，根據(jù)種子就可以生成出專屬自己的偽隨機數(shù)列。偽隨機數(shù)生成器是公開的，但種子是需要自己保密的，這就好像密碼算法是公開的，但是密鑰只能自己保密。由于種子不可以被攻擊者知道，因此不可使用容易被預(yù)測的值，例如不可以使用當(dāng)前時間作為種子。
  ?密碼的密鑰和偽隨機數(shù)的種子之間的對比：
  
  密碼的密鑰與偽隨機數(shù)的種子.png

具體偽隨機數(shù)生成器

• 雜亂的方法
  ? 既然要生成雜亂無章的數(shù)列，那么用雜亂無章的算法不就可以了嗎？比如說，可以使用連程序員都無法理解的混亂又復(fù)雜的算法。然而，這種做法是錯誤的。如果只是把算法搞的復(fù)雜，那么該算法是無法用于密碼技術(shù)的。
  ?其中一個原因就是周期太短了。使用復(fù)雜算法所生成的數(shù)列大多都會具有很短的周期（即短數(shù)列的不斷重復(fù)）。由于密碼技術(shù)使用的偽隨機數(shù)必須具備不可預(yù)測性，因此周期短是不行的。
  ?另一個原因是，如果程序員不能夠理解算方法的詳細內(nèi)容，那么就無法判斷所生成的隨機數(shù)是否具有不可預(yù)測性。
• 線性同余法
  ?線性同余法（linear congruential method）是一種使用很廣泛的偽隨機數(shù)生成器算法。然而，它并不能用于密碼技術(shù)。

• 單向散列函數(shù)法
  ?使用單向散列函數(shù)可以編寫出能夠生成具備不可預(yù)測性的偽隨機數(shù)列的偽隨機數(shù)生成器。

  
  
  用單向散列函數(shù)實現(xiàn)偽隨機數(shù)生成器.png
  
  

  ?這種偽隨機數(shù)生成器的工作方式如下。

1. 用偽隨機數(shù)的種子初始化內(nèi)部狀態(tài)（計數(shù)器）。
2. 用單向散列函數(shù)計算計數(shù)器的散列值
3. 將散列值作為偽隨機數(shù)輸出。
4. 計數(shù)器的值加1。
5. 根據(jù)需要的偽隨機數(shù)數(shù)量重復(fù)2~4的步驟。
   ?供給制要預(yù)測下一個偽隨機數(shù)，需要知道計數(shù)器的當(dāng)前值。請大家注意，這里輸出的偽隨機數(shù)實際上相當(dāng)于單向散列函數(shù)的散列值。也就是說，要想知道計數(shù)器的值，就需要破解單向散列函數(shù)的單向性，這是非常困難的，因此攻擊者無法預(yù)測下一個偽隨機數(shù)?？偠灾?，在這種偽隨機數(shù)生成器中，單向散列函數(shù)的單向性是支撐偽隨機數(shù)生成器不可預(yù)測性的基礎(chǔ)。

• 密碼法
  ?我們可以使用密碼來編寫能夠生成強偽隨機數(shù)的偽隨機數(shù)生成器。既可以使用AES等對稱密碼，也可以使用RSA等公鑰密碼。

用密碼實現(xiàn)的偽隨機數(shù)生成器.png

1. 初始內(nèi)部狀態(tài)（計數(shù)器）
2. 用密鑰加密計算器的值
3. 將密文作為偽隨機數(shù)的輸出
4. 計算器的值加1
5. 根據(jù)需要的偽隨機數(shù)數(shù)量重復(fù)2~4步驟
   ?攻擊者要預(yù)測下一個偽隨機數(shù)，需要知道計數(shù)器的當(dāng)前值然而，由于之前所輸出的偽隨機數(shù)相當(dāng)于密碼，因此要知道計數(shù)器的值，就需要破譯密碼，這是非常困難的，因此攻擊者無法預(yù)測出下一個偽隨機數(shù)?？偠灾谶@種偽隨機數(shù)生成器中，密碼的機密性是支撐偽隨機數(shù)生成器不可預(yù)測性的基礎(chǔ)。

• ANSI X9.17
  ?關(guān)于用密碼實現(xiàn)偽隨機數(shù)生成器的具體方法，在ANSIX9.17和ANSI X9.31的附錄中進行了描述，下面我們來介紹一下這種方法。這里所介紹的偽隨機數(shù)生成器，就被用于密碼軟件PGP中。

  
  
  用ANSI X9.17方法實現(xiàn)偽隨機數(shù)生成器.png

1. 初始化內(nèi)部狀態(tài)
2. 將當(dāng)前時間加密生成掩碼
3. 對內(nèi)部狀態(tài)與掩碼求XOR
4. 將步驟3的結(jié)果進行加密
5. 將步驟4的結(jié)果作為偽隨機數(shù)輸出
6. 對步驟4的結(jié)果與掩碼求XOR
7. 將步驟6的結(jié)果加密
8. 將步驟7的結(jié)果作為新的內(nèi)部狀態(tài)
9. 重復(fù)步驟2~8直到得到所需數(shù)量的偽隨機數(shù)。
   ?在步驟2中，我們將當(dāng)前時間進行加密生成了一個掩碼。當(dāng)前時間是可以被攻擊者預(yù)測出來的，但是由于攻擊者不知道加密密鑰，因此他無法預(yù)測加密后的當(dāng)前時間（即掩碼）。在之后的步驟3和步驟6中，我們將使用掩碼對比特序列進行隨機翻轉(zhuǎn)。
   ?步驟3~5的作用是輸出偽隨機數(shù)。這里輸出額偽隨機數(shù)是將內(nèi)部狀態(tài)與掩碼的XOR進行加密之后的結(jié)果，那么攻擊者是否能通過將偽隨機數(shù)進行反算來看穿內(nèi)部狀態(tài)與掩碼的XOR呢？不能，因為要看穿這個值，攻擊者必須要破解密碼。因此，根據(jù)過去輸出的偽隨機數(shù)列，攻擊者無法推測出偽隨機數(shù)生成器內(nèi)部狀態(tài)。
   ?步驟6~8的作用是更新內(nèi)部狀態(tài)。新的內(nèi)部狀態(tài)是將上個偽隨機數(shù)與掩碼的XOR進行加密之后的結(jié)果。那么攻擊者是否能夠從偽隨機數(shù)推測出新的內(nèi)部狀態(tài)呢?不能，因為要算出新的內(nèi)部狀態(tài)，只知道上一個偽隨機數(shù)是不夠的，還必須知道掩碼以及加密密鑰才行。
   ?我們可以發(fā)現(xiàn)，在這種偽隨機數(shù)生成器中，密碼的使用保證了無法根據(jù)輸出的偽隨機數(shù)列來推測內(nèi)部狀態(tài)。換言之，偽隨機數(shù)生成器的內(nèi)部狀態(tài)是通過密碼進行保護的。

• 其他算法
  ?除了上面介紹的算法之外，還有很多其他的生成隨機數(shù)的算法。在安全相關(guān)的軟件開發(fā)中，開發(fā)者在選擇隨機數(shù)生成算法時必須確認“這個隨機數(shù)算法是否能夠用于密碼學(xué)和安全相關(guān)用途”。一個隨機數(shù)算法再優(yōu)秀，如果它不具備不可預(yù)測性，那么久不能用于密碼學(xué)和安全相關(guān)用途，。大多數(shù)情況下，隨機數(shù)算法的說明都會寫明是否可用于安全相關(guān)的用途，請大家仔細確認。
  ?有一個有名的偽隨機算法叫作梅森旋轉(zhuǎn)算法（Mersenne twister），但它并不能用于安全相關(guān)的用途。和線性同余一樣，只要觀察足夠長的隨機數(shù)列，就能夠?qū)χ笊傻碾S機數(shù)列進行預(yù)測。
  ?Java中有一個用于生成隨機數(shù)列的類，叫java.util.Random，然而這個類也不能用于安全相關(guān)用途，如果要用于安全相關(guān)用途，可以使用另一個名叫java.security.SecureRandom的類，不過這類的底層算法是經(jīng)過封裝的，因此實際用到的算法可能不止一種。
  ?和Java一樣，Ruby中也分別用Random和SecureRandom模塊，在安全相關(guān)用途中應(yīng)該使用SecureRandom，而不是Random。

對偽隨機數(shù)生成器的攻擊

?和密碼相比，偽隨機數(shù)生成器實在是很少被人們所注意，因此我們很容易忘記偽隨機數(shù)生成器也是可以受到攻擊的。然而，由于偽隨機數(shù)生成器承擔(dān)了生成密鑰的重任，因此它經(jīng)常成為攻擊對象。

• 對種子進行攻擊
  ? 偽隨機數(shù)的種子和密碼的密鑰是同等重要的。如果攻擊者知道了偽隨機數(shù)的種子，那么就能夠知道這個偽隨機數(shù)生成器所生成的全部偽隨機數(shù)列。因此，偽隨機數(shù)的種子是不可以被攻擊者知道。
  ?要避免種子被攻擊知道，我們需要使用具備不可重現(xiàn)性的真隨機數(shù)作為種子。
• 對隨機數(shù)池進行攻擊
  ?當(dāng)然，我們一般不會到了需要的時候才當(dāng)場生成真隨機數(shù)，而是會事先在一個名為隨機數(shù)池（random pool）的文件中積累隨機比特序列。當(dāng)密碼軟件需要偽隨機數(shù)的種子時，可以從這個隨機數(shù)池中取出所需要的長度的隨機比特序列來使用。
  ?隨機數(shù)池的內(nèi)容不可以被攻擊者知道，否則偽隨機數(shù)的種子就可能被預(yù)測出來。
  ?隨機數(shù)池本身并不存儲任何有意義的信息。我們需要保護沒有任何意義的比特序列，這一點優(yōu)點違背常識，但其實卻是非常重要的。

該系列的主要內(nèi)容來自《圖解密碼技術(shù)第三版》
我只是知識的搬運工
文章中的插圖來源于原著