隨機數
???———— 不可預測的源泉
使用隨機數的密碼技術
?隨機數的使用場景诀姚，比如:
- 生成密鑰
?用于對稱密碼和消息的認證碼 - 生成密鑰對
?用于公鑰密碼和數字簽名 - 生成初始化向量
?用于分組密碼的CBC雀久、CFB、OFB模式 - 生成nonce
?用于防御重放攻擊以及分組密碼的CTR模式等 - 生成鹽
?用于基于口令的密碼等桨啃；
為了不讓攻擊者看穿而使用隨機數蘸秘，因為“無法看穿”臣缀，即不可預測。
隨機數性質
對隨機數的性質進行分類
- 隨機性 —— 不存在統(tǒng)計學偏差方仿，是完全雜亂的數列
- 不可預測性—— 不能從過去的數列推測出下一個出現的數
-
不可重現性—— 除非將數列本身保存下來，否則不能重現相同的數列
上述三個性質按順序分別命名為“弱偽隨機數”统翩、“強偽隨機數”和“真?zhèn)坞S機數”
隨機數的性質.png
隨機性
?所謂隨機性仙蚜，簡單來說，就是看上去雜亂無章的性質厂汗。我們可以用偽隨機數生成器大量的生成0到9范圍內的整數委粉，然后看一看所生成的數列。如果數列是像0娶桦、1贾节、2、3衷畦、4栗涂、5、6祈争、7斤程、8、9菩混、0忿墅、1、2....這樣循環(huán)不斷沮峡，那肯定不是雜亂無章的球匕。或者咋一看是雜亂無章的帖烘，但實際上在數列中0一次都沒出現過亮曹，或者整個數列一半都是6，這樣的數列也能算是雜亂無章的秘症。
?如果偽隨機數列中不存在統(tǒng)計學偏差照卦，則我們可以認為這個偽隨機數列是隨機的。判斷一個偽隨機數是否隨機的方法稱為隨機數測試乡摹，隨機數測試的方法有很多種役耕。
?一半在電腦游戲中使用的隨機數只要具備隨機性就可以了。此外聪廉，在計算機模擬軟件中使用的隨機數雖然需要根據目的來進行隨機數測試瞬痘，但也是只要具備隨機性就可以了故慈。然而，密碼技術中所使用的隨機數框全，僅僅具備隨機性是不夠的察绷。
?由于隨機數會被用來生成密鑰，因此密鑰不能被攻擊者看穿津辩。但是拆撼，雜亂無章并不代表不會被看穿，因此喘沿，將只具備隨機性的偽隨機數數稱為 “弱為隨機數”闸度。
不可預測性
?密碼中所使用的隨機數僅僅具備隨機性是不夠的，還需要具備避免攻擊者看穿的不可預測性蚜印。不可預測性（unpredictability）莺禁。
?所謂不可預測性，是指攻擊者在制定過去生成偽隨機數列的前提下窄赋，依然無法預測出下一個生成出來的偽隨機數的性質睁宰。其中，“在制定過去生成的偽隨機數列的前提下.....”是非常重要的一點寝凌。
?不可預測性是通過使用其他的密碼技術來實現的柒傻。例如，可以通過單向散列函數的單向性和密碼的機密性來保證偽隨機數生成器的不可預測性较木。我們將具備不可預測性的偽隨機數稱為強偽隨機數红符。
不可重新性
?所謂不可重新性，是指無法重新和某一隨機數列完全相同的數列的性質伐债。如果除了將隨機數列本身本身保存下來以外预侯，沒有其他方法能夠重新該數列，則我們就可以說該隨機數列具備了不可重現性峰锁。
?僅靠軟件時無法生成具備不可重現性的隨機數列的萎馅。軟件只能生成偽隨機數列，這是因為運行軟件的計算機本身僅具備有限的內部狀態(tài)虹蒋。而在內部狀態(tài)相同的條件下糜芳，軟件必然只能生成相同的數，因此軟件所生成的數列在某一個時刻一定會出現重復的魄衅。首次出現重復之前的數列長度稱為周期峭竣，對于軟件所生成的數列，其周期必定是有限的晃虫。當然皆撩，這個周期可能會很長，但總歸還是有限的哲银。凡是具有周期的數列扛吞，都不具備不可重現性呻惕。
?要生成具備不可重現性的隨機數列，需要從不可重新性的物理現象中獲取信息滥比，比如周圍的溫度和聲音的變化亚脆，用戶移動的鼠標的位置、鍵盤的輸入的時間間隔守呜、放射線測量儀的輸出值等，根據從這些硬件中所獲取的信息而生成的數列山憨，一般可以認為是具備不可重新性的隨機數列查乒。
?目前，利用熱噪聲這一自然現象郁竟，人們已經開發(fā)出能夠生成不可重新性的隨機數的硬件設備玛迄。例如，英特爾的新型CPU中就內置了數字隨機數生成器棚亩，并提供了生成不可重現性隨機數的RDSEED指令蓖议，以及生成不可預測隨機數的RDRAND指令。
我們稱具備不可重現性的隨機數稱為真隨機數讥蟆。
偽隨機數生成器
?隨機數可以通過硬件來生成勒虾，也可以通過軟件來生成。
?通過硬件生成的隨機數列瘸彤，是根據傳感器收集的熱量修然、聲音變化等事實上無法預測和重現的自然現象信息來生成的。像這樣的硬件設備就稱為隨機數生成器（Random Number Generator 质况，RNG）愕宋。
?而可以生成隨機數的軟件則稱為偽隨機生成器*（Pseudo Random Number Generator，PRNG）结榄。因為僅靠軟件無法生成真隨機數中贝，因此要加上一個“偽”字。
偽隨機數生成結構
?偽隨機數生成器具有“內部狀態(tài)”臼朗，并根據外部輸入的“種子”來生成偽隨機數列邻寿。
- 偽隨機數生成器內部狀態(tài)
?偽隨機數生成器的內部狀態(tài)，是指偽隨機數生成器所管理的內存中的數值视哑。當有人對偽隨機數生成器發(fā)出“給我一個偽隨機數”的請求時老厌，偽隨機數生成器會根據內存中的數值（內部狀態(tài)）進行計算，并將計算的結果作為隨機數的輸出黎炉。隨后枝秤，為了響應下一個偽隨機數請求，偽隨機數生成器會改變自己的內部狀態(tài)慷嗜。因此淀弹，將根據內部狀態(tài)計算偽隨機數的方法和改變內部狀態(tài)的方法組合起來丹壕，就是偽隨機數生成的算法。
?由于內部狀態(tài)決定了下一個生成偽隨機數薇溃，因此內部狀態(tài)不能被攻擊者知道菌赖。 - 偽隨機數生成器的種子
?為了生成偽隨機數，偽隨機數生成器需要被稱為種子（seed）的信息沐序。偽隨機數的種子是用來對偽隨機數生成器的內部狀態(tài)進行初始化的琉用。
?偽隨機數的種子是一串隨機的比特序列，根據種子就可以生成出專屬自己的偽隨機數列策幼。偽隨機數生成器是公開的邑时，但種子是需要自己保密的，這就好像密碼算法是公開的特姐，但是密鑰只能自己保密晶丘。由于種子不可以被攻擊者知道，因此不可使用容易被預測的值唐含，例如不可以使用當前時間作為種子浅浮。
?密碼的密鑰和偽隨機數的種子之間的對比：
密碼的密鑰與偽隨機數的種子.png
具體偽隨機數生成器
- 雜亂的方法
? 既然要生成雜亂無章的數列，那么用雜亂無章的算法不就可以了嗎捷枯？比如說滚秩，可以使用連程序員都無法理解的混亂又復雜的算法。然而淮捆，這種做法是錯誤的叔遂。如果只是把算法搞的復雜，那么該算法是無法用于密碼技術的争剿。
?其中一個原因就是周期太短了已艰。使用復雜算法所生成的數列大多都會具有很短的周期（即短數列的不斷重復）。由于密碼技術使用的偽隨機數必須具備不可預測性蚕苇，因此周期短是不行的哩掺。
?另一個原因是，如果程序員不能夠理解算方法的詳細內容涩笤，那么就無法判斷所生成的隨機數是否具有不可預測性嚼吞。 - 線性同余法
?線性同余法（linear congruential method）是一種使用很廣泛的偽隨機數生成器算法。然而蹬碧，它并不能用于密碼技術舱禽。 -
單向散列函數法
?使用單向散列函數可以編寫出能夠生成具備不可預測性的偽隨機數列的偽隨機數生成器。
用單向散列函數實現偽隨機數生成器.png
?這種偽隨機數生成器的工作方式如下恩沽。
- 用偽隨機數的種子初始化內部狀態(tài)（計數器）誊稚。
- 用單向散列函數計算計數器的散列值
- 將散列值作為偽隨機數輸出。
- 計數器的值加1。
- 根據需要的偽隨機數數量重復2~4的步驟里伯。
?供給制要預測下一個偽隨機數城瞎，需要知道計數器的當前值。請大家注意疾瓮，這里輸出的偽隨機數實際上相當于單向散列函數的散列值脖镀。也就是說，要想知道計數器的值狼电，就需要破解單向散列函數的單向性蜒灰，這是非常困難的，因此攻擊者無法預測下一個偽隨機數肩碟∏拷眩總而言之，在這種偽隨機數生成器中腾务，單向散列函數的單向性是支撐偽隨機數生成器不可預測性的基礎毕骡。
- 密碼法
?我們可以使用密碼來編寫能夠生成強偽隨機數的偽隨機數生成器削饵。既可以使用AES等對稱密碼岩瘦，也可以使用RSA等公鑰密碼。
- 初始內部狀態(tài)（計數器）
- 用密鑰加密計算器的值
- 將密文作為偽隨機數的輸出
- 計算器的值加1
- 根據需要的偽隨機數數量重復2~4步驟
?攻擊者要預測下一個偽隨機數窿撬，需要知道計數器的當前值然而启昧，由于之前所輸出的偽隨機數相當于密碼，因此要知道計數器的值劈伴，就需要破譯密碼密末，這是非常困難的，因此攻擊者無法預測出下一個偽隨機數跛璧⊙侠铮總而言之，在這種偽隨機數生成器中追城，密碼的機密性是支撐偽隨機數生成器不可預測性的基礎刹碾。
-
ANSI X9.17
?關于用密碼實現偽隨機數生成器的具體方法，在ANSIX9.17和ANSI X9.31的附錄中進行了描述座柱，下面我們來介紹一下這種方法迷帜。這里所介紹的偽隨機數生成器，就被用于密碼軟件PGP中色洞。
用ANSI X9.17方法實現偽隨機數生成器.png
- 初始化內部狀態(tài)
- 將當前時間加密生成掩碼
- 對內部狀態(tài)與掩碼求XOR
- 將步驟3的結果進行加密
- 將步驟4的結果作為偽隨機數輸出
- 對步驟4的結果與掩碼求XOR
- 將步驟6的結果加密
- 將步驟7的結果作為新的內部狀態(tài)
- 重復步驟2~8直到得到所需數量的偽隨機數戏锹。
?在步驟2中，我們將當前時間進行加密生成了一個掩碼火诸。當前時間是可以被攻擊者預測出來的锦针，但是由于攻擊者不知道加密密鑰，因此他無法預測加密后的當前時間（即掩碼）。在之后的步驟3和步驟6中伞插，我們將使用掩碼對比特序列進行隨機翻轉割粮。
?步驟3~5的作用是輸出偽隨機數。這里輸出額偽隨機數是將內部狀態(tài)與掩碼的XOR進行加密之后的結果媚污，那么攻擊者是否能通過將偽隨機數進行反算來看穿內部狀態(tài)與掩碼的XOR呢舀瓢？不能，因為要看穿這個值耗美，攻擊者必須要破解密碼京髓。因此，根據過去輸出的偽隨機數列商架，攻擊者無法推測出偽隨機數生成器內部狀態(tài)堰怨。
?步驟6~8的作用是更新內部狀態(tài)。新的內部狀態(tài)是將上個偽隨機數與掩碼的XOR進行加密之后的結果蛇摸。那么攻擊者是否能夠從偽隨機數推測出新的內部狀態(tài)呢?不能备图，因為要算出新的內部狀態(tài)，只知道上一個偽隨機數是不夠的赶袄，還必須知道掩碼以及加密密鑰才行揽涮。
?我們可以發(fā)現，在這種偽隨機數生成器中饿肺，密碼的使用保證了無法根據輸出的偽隨機數列來推測內部狀態(tài)蒋困。換言之，偽隨機數生成器的內部狀態(tài)是通過密碼進行保護的敬辣。
- 其他算法
?除了上面介紹的算法之外雪标，還有很多其他的生成隨機數的算法。在安全相關的軟件開發(fā)中溉跃，開發(fā)者在選擇隨機數生成算法時必須確認“這個隨機數算法是否能夠用于密碼學和安全相關用途”村刨。一個隨機數算法再優(yōu)秀，如果它不具備不可預測性撰茎，那么久不能用于密碼學和安全相關用途嵌牺，。大多數情況下乾吻，隨機數算法的說明都會寫明是否可用于安全相關的用途髓梅，請大家仔細確認。
?有一個有名的偽隨機算法叫作梅森旋轉算法（Mersenne twister）绎签，但它并不能用于安全相關的用途枯饿。和線性同余一樣，只要觀察足夠長的隨機數列诡必，就能夠對之后生成的隨機數列進行預測奢方。
?Java中有一個用于生成隨機數列的類搔扁，叫java.util.Random，然而這個類也不能用于安全相關用途蟋字，如果要用于安全相關用途稿蹲，可以使用另一個名叫java.security.SecureRandom的類，不過這類的底層算法是經過封裝的鹊奖，因此實際用到的算法可能不止一種苛聘。
?和Java一樣，Ruby中也分別用Random和SecureRandom模塊忠聚，在安全相關用途中應該使用SecureRandom设哗，而不是Random。
對偽隨機數生成器的攻擊
?和密碼相比两蟀，偽隨機數生成器實在是很少被人們所注意网梢，因此我們很容易忘記偽隨機數生成器也是可以受到攻擊的。然而赂毯，由于偽隨機數生成器承擔了生成密鑰的重任战虏，因此它經常成為攻擊對象。
- 對種子進行攻擊
? 偽隨機數的種子和密碼的密鑰是同等重要的党涕。如果攻擊者知道了偽隨機數的種子烦感，那么就能夠知道這個偽隨機數生成器所生成的全部偽隨機數列。因此遣鼓，偽隨機數的種子是不可以被攻擊者知道啸盏。
?要避免種子被攻擊知道重贺，我們需要使用具備不可重現性的真隨機數作為種子骑祟。 - 對隨機數池進行攻擊
?當然，我們一般不會到了需要的時候才當場生成真隨機數气笙，而是會事先在一個名為隨機數池（random pool）的文件中積累隨機比特序列次企。當密碼軟件需要偽隨機數的種子時，可以從這個隨機數池中取出所需要的長度的隨機比特序列來使用潜圃。
?隨機數池的內容不可以被攻擊者知道缸棵，否則偽隨機數的種子就可能被預測出來。
?隨機數池本身并不存儲任何有意義的信息谭期。我們需要保護沒有任何意義的比特序列堵第，這一點優(yōu)點違背常識，但其實卻是非常重要的隧出。
該系列的主要內容來自《圖解密碼技術第三版》
我只是知識的搬運工
文章中的插圖來源于原著
