14.1 介紹
很多密碼學(xué)系統(tǒng)需要使用到隨機(jī)數(shù)挤渔。目前為止诈皿，本書(shū)只是假設(shè)可以獲取到隨機(jī)數(shù)。本章將介紹密碼學(xué)中的隨機(jī)數(shù)的重要性以及一些機(jī)制欠雌。
產(chǎn)生隨機(jī)數(shù)是一件相當(dāng)復(fù)雜的過(guò)程蹄梢。和密碼學(xué)中很多其他事情一樣，它非常容易出錯(cuò)富俄，但是從表面上看卻看起來(lái)好像一切都是對(duì)的禁炒。
隨機(jī)數(shù)生成器分成3個(gè)范疇：
真正的隨機(jī)數(shù)生成器
密碼學(xué)安全的偽隨機(jī)數(shù)生成器
偽隨機(jī)數(shù)生成器
14.2 真正的隨機(jī)數(shù)生成器
任何考慮用算術(shù)手段來(lái)產(chǎn)生隨機(jī)數(shù)的人自然都是有原罪的. ——馮·諾伊曼
馮·諾伊曼,現(xiàn)代計(jì)算機(jī)之父，提出了他很明確的觀點(diǎn)霍比。不可能使用可預(yù)測(cè)的幕袱，決定性的數(shù)學(xué)來(lái)產(chǎn)生隨機(jī)數(shù)。需要一個(gè)本質(zhì)是隨機(jī)的東西而不是一個(gè)確定性規(guī)則的序列悠瞬。
真正的隨機(jī)數(shù)生成器從物理過(guò)程中獲取它們的隨機(jī)性们豌。歷史上有很多系統(tǒng)被用來(lái)生成這些數(shù)字。其中的一些至今仍在使用浅妆。然而望迎，在我們實(shí)際的密碼學(xué)系統(tǒng)中，需要大量的隨機(jī)數(shù)狂打，而真正的隨機(jī)數(shù)生成器通常太慢了以至于通常不可靠擂煞。
目前有很多更快也更可靠的隨機(jī)源。目前的硬件隨機(jī)數(shù)生成器通常使用以下物理過(guò)程來(lái)產(chǎn)生隨機(jī)數(shù)趴乡。
量子過(guò)程对省。
熱力學(xué)過(guò)程蝗拿。
振蕩器漂移。
時(shí)間事件蒿涎。
并不是所有的選項(xiàng)都需要產(chǎn)生高質(zhì)量的哀托，真實(shí)的隨機(jī)數(shù)。本章將進(jìn)一步介紹他們是如何被成功應(yīng)用的劳秋。
放射性衰變
量子物理過(guò)程應(yīng)用到產(chǎn)生隨機(jī)數(shù)的一個(gè)例子是放射衰變仓手。眾所周知，放射物質(zhì)隨著時(shí)間會(huì)慢慢衰變玻淑。無(wú)法知道下一個(gè)原子什么時(shí)候衰變嗽冒；它是完全隨機(jī)的。然而監(jiān)測(cè)衰變何時(shí)發(fā)生补履，是容易的添坊。通過(guò)監(jiān)測(cè)獨(dú)立衰變之間的時(shí)間，就可以產(chǎn)生隨機(jī)數(shù)了箫锤。
散粒噪聲
散粒噪聲是另外一個(gè)量子物理過(guò)程應(yīng)用到產(chǎn)生隨機(jī)數(shù)的例子贬蛙。散粒噪聲是基于每個(gè)獨(dú)立的粒子的運(yùn)動(dòng)引發(fā)光和電子：光的情況下是光子，電的情況下是電子谚攒。
抽樣噪聲
熱力學(xué)過(guò)程應(yīng)用到產(chǎn)生隨機(jī)數(shù)的一個(gè)例子是抽樣噪聲阳准。抽樣噪聲是發(fā)生在電荷載體（通常是電子）通過(guò)一定阻力的媒介時(shí)產(chǎn)生的噪聲。微弱的電流流過(guò)電阻（電阻的電壓會(huì)有微弱不同）馏臭。
這些共識(shí)對(duì)于沒(méi)有了解過(guò)背后物理知識(shí)的人來(lái)說(shuō)有點(diǎn)嚇人野蝇，但是不用過(guò)于擔(dān)心：并不需要真正的理解它們。如果你之前沒(méi)有聽(tīng)說(shuō)過(guò)這些位喂，可以簡(jiǎn)單地假裝這個(gè)值是平均值浪耘÷伊椋△f是帶寬塑崖，T是系統(tǒng)的開(kāi)爾文溫度，kB是玻爾茲曼常數(shù)痛倚。
從公式中可以看出规婆，抽樣早上是熱力或者是溫度獨(dú)立的。幸運(yùn)的是蝉稳，一個(gè)攻擊者通常沒(méi)有辦法打破隨機(jī)數(shù)生成器的該項(xiàng)特性抒蚜。某一個(gè)刻的溫度在系統(tǒng)使用它的時(shí)候溫度可能已經(jīng)不在那個(gè)點(diǎn)了。
通過(guò)介紹這個(gè)公式耘戚，可以看出抽樣噪聲是很小的嗡髓。在室溫情況下，合理假設(shè)（10kHz帶寬收津，1k歐電阻）饿这，抽樣噪聲在幾百納米伏特浊伙。即便是將范圍調(diào)整為微伏特（1微伏特=1000納伏特），依然是1百萬(wàn)分之一伏特长捧，而一個(gè)簡(jiǎn)單的AA電池就有1.5V
然而嚣鄙，公式涉及到了平方根，該值將會(huì)是完全隨機(jī)的分布串结。通過(guò)重復(fù)測(cè)量哑子，可以產(chǎn)生高質(zhì)量的隨機(jī)數(shù)。在多數(shù)實(shí)際產(chǎn)品中肌割，熱力學(xué)噪聲數(shù)字是高質(zhì)量低偏差的卧蜓。
14.3 密碼學(xué)安全的偽隨機(jī)數(shù)生成器
接下來(lái)幾節(jié)將要介紹一些密碼學(xué)安全的偽隨機(jī)數(shù)生成器，記住這些算法只是可以使用把敞，作為一個(gè)應(yīng)用的開(kāi)發(fā)者烦却，你不需要在它們中做選擇。如果真的需要生成隨機(jī)數(shù)先巴，你應(yīng)該使用你自己操作系統(tǒng)支持的密碼安雪的隨機(jī)數(shù)生成器其爵。在*NIX（Linux, BSDs 以及 OS X）上是/dev/urandom，在Windows上是CryptGenRandom. Python提供了使用系統(tǒng)隨機(jī)數(shù)的接口os.urandom和random.SystemRandom.
為了保證安全伸蚯，盡量避免使用用戶層級(jí)的密碼安全的隨機(jī)數(shù)生成器摩渺，比方說(shuō)OpenSSL中的隨機(jī)數(shù)。使用這些有很多可能出錯(cuò)的情況剂邮，通常與它們的內(nèi)部狀態(tài)有關(guān)：它們可能沒(méi)有做初始化摇幻，或者只是簡(jiǎn)單的初始化，或者是在不同的場(chǎng)景中重用相同的狀態(tài)挥萌。這些情況都可能會(huì)導(dǎo)致密碼系統(tǒng)徹底的崩潰绰姻。
14.4 Yarrow
Yarrow算法是密碼學(xué)安全的偽隨機(jī)數(shù)生成算法。
該算法在FreeBSD中被用作CSPRNG引瀑，并被Mac OS X系統(tǒng)繼承狂芋。在這倆種系統(tǒng)中，它都是被用來(lái)實(shí)現(xiàn)/dev/random憨栽。在Linux系統(tǒng)中/dev/urandom僅僅只是/dev/random的別名帜矾。
14.5 Blum Blum Shub
TODO：介紹該算法的優(yōu)點(diǎn)（可證明），但是為什么又不使用它（慢）屑柔。
14.6 雙橢圓曲線隨機(jī)比特生成器（Dual_EC_DRBG）
Dual_EC_DRBG是NIST的密碼學(xué)安全的偽隨機(jī)比特生成標(biāo)準(zhǔn)屡萤。該標(biāo)準(zhǔn)引發(fā)了大量的爭(zhēng)議。盡管被用來(lái)作為官方的密碼學(xué)標(biāo)準(zhǔn)掸宛，但是它很快被證明了它是不夠好死陆。
密碼學(xué)專家最終演示了該標(biāo)準(zhǔn)可以在其常量中隱藏一個(gè)后門(mén)，就會(huì)造成不特定攻擊可能會(huì)整個(gè)摧毀該隨機(jī)數(shù)生成器的潛在風(fēng)險(xiǎn)唧瘾。
一些年之后措译，一份泄漏的文檔中推薦使用后門(mén)在一個(gè)未命名的NIST標(biāo)準(zhǔn)中髓涯，而這一年正好是Dual_EC_DRBG發(fā)布的年份坦冠，使得該標(biāo)準(zhǔn)更加的可疑镜硕。這也使得官方從推薦該標(biāo)準(zhǔn)到停用該標(biāo)準(zhǔn)睦优，這個(gè)情況在當(dāng)時(shí)的環(huán)境中是前所未見(jiàn)的。
背景
很長(zhǎng)一段時(shí)間掠械，由NIST產(chǎn)生的官方標(biāo)準(zhǔn)都缺飯很好的現(xiàn)代密碼學(xué)安全的偽隨機(jī)生成數(shù)算法由缆。有一些其他的簡(jiǎn)陋的選擇，但是該選擇的標(biāo)準(zhǔn)化有幾個(gè)嚴(yán)重的問(wèn)題猾蒂。
NIST為了強(qiáng)調(diào)這個(gè)問(wèn)題發(fā)表了被稱為SP 800-90的文章均唉，其中包括一些新的密碼學(xué)安全的偽隨機(jī)數(shù)生成算法。該文章包含了很多基于各種不同的密碼學(xué)機(jī)制的算法：
密碼學(xué)函數(shù)函數(shù)
HMAC
塊加密
橢圓曲線
最后一項(xiàng)立刻就引人注目了肚菠。使用橢圓曲線來(lái)產(chǎn)生隨機(jī)數(shù)是非常少見(jiàn)的舔箭。標(biāo)準(zhǔn)希望能夠是最先進(jìn)的，并且依然是保守的蚊逢。橢圓曲線在之前的學(xué)術(shù)文章中被考慮過(guò)层扶，但是離其被推薦作為一個(gè)標(biāo)準(zhǔn)被廣泛使用還有很遙遠(yuǎn)的距離。
第二個(gè)原因是橢圓曲線看起來(lái)很奇怪烙荷。HMAC和塊加密都很明顯是對(duì)稱算法镜会。哈希函數(shù)通常在非對(duì)稱算法例如數(shù)字簽名中被應(yīng)用。但是它們自身并不是非對(duì)稱的终抽。而橢圓曲線戳表，專門(mén)被用于非對(duì)稱加密：簽名，密鑰交換昼伴，非對(duì)稱加密匾旭。
這也就是說(shuō)，這個(gè)選擇并不是完全來(lái)自于藍(lán)海圃郊。密碼學(xué)安全的隨機(jī)數(shù)生成算法的一個(gè)基于很少能聽(tīng)到的很強(qiáng)的數(shù)論基礎(chǔ)的例子：Blum Blum Shub相比其他選擇就太慢了价涝。例如在同一個(gè)標(biāo)準(zhǔn)中，Dual_EC_DRBG要比它的同輩們慢一些描沟，排在第三位飒泻。通常強(qiáng)的數(shù)學(xué)證明是值得性能上的損失的鞭光。例如吏廉，我們相信因數(shù)分解是很困難的，但是hash函數(shù)和加密就沒(méi)有那么確信惰许。RSA是1977年發(fā)明的席覆，自從那個(gè)時(shí)候開(kāi)始的測(cè)試都是非常好的。而DES兩年后被提出汹买，現(xiàn)在已經(jīng)完全被攻破佩伤。MD4和MD5在十年后被提出聊倔，現(xiàn)在也已經(jīng)被攻破了。
問(wèn)題在于生巡，這個(gè)標(biāo)準(zhǔn)并沒(méi)有真正地拿出安全性證據(jù)耙蔑。標(biāo)準(zhǔn)提出了這個(gè)生成器但是僅僅是提出它至少是和解決橢圓曲線問(wèn)題一樣的難。作為對(duì)比Blum Blum Shub就可以證明要攻破它孤荣，至少和解決二次剩余困難性問(wèn)題一樣難甸陌。目前我們最好的問(wèn)題是因數(shù)分解問(wèn)題，我們可以確定該問(wèn)題特別的難盐股。
省略證明是愚蠢的钱豁，因?yàn)槟銢](méi)有理由要使用一個(gè)和Dual_EC_DRBG一樣慢的偽隨機(jī)數(shù)生成算法除非你有證據(jù)你在犧牲性能的情況下能獲得些什么。
NIST本該在提出來(lái)的時(shí)候就進(jìn)行的工作疯汁，密碼學(xué)家后來(lái)對(duì)其進(jìn)行了證明牲尺，這些分析強(qiáng)調(diào)了一些問(wèn)題。
算法概述
該算法包括兩部分：
在橢圓曲線上生成一個(gè)偽隨機(jī)數(shù)點(diǎn)幌蚊，然后將其作為生成器的中間狀態(tài)谤碳。
將這些點(diǎn)轉(zhuǎn)化為偽隨機(jī)比特。
本節(jié)將圖形化地來(lái)詳述該過(guò)程溢豆，圖片是以Shumow和Ferguson的工作為基礎(chǔ)估蹄。兩位密碼學(xué)家強(qiáng)調(diào)了該算法的主要問(wèn)題。
整個(gè)算法中沫换，?是一個(gè)函數(shù)臭蚁，它的輸入為橢圓曲線的點(diǎn)，輸出為一個(gè)整數(shù)：算法需要兩個(gè)橢圓曲線上的點(diǎn)：P和Q讯赏。這些是固定的垮兑，在規(guī)范中定義的。算法有一個(gè)內(nèi)部狀態(tài)s漱挎。當(dāng)產(chǎn)生一個(gè)新的比特塊時(shí)系枪，算法將s轉(zhuǎn)化成一個(gè)不同的值r，使用?函數(shù)磕谅，以及和P做橢圓曲線的乘法私爷。
這個(gè)值r既會(huì)用來(lái)產(chǎn)生輸出的比特也會(huì)用來(lái)更新生成器的內(nèi)部狀態(tài)。為了產(chǎn)生輸出的比特膊夹，需要用到橢圓曲線的另一個(gè)點(diǎn)Q衬浑。輸出的比特是將r乘以Q，再將該結(jié)果竟一個(gè)一個(gè)轉(zhuǎn)化函數(shù) θ的處理：
為了更新?tīng)顟B(tài)放刨，r會(huì)再次乘以P工秩，然后將結(jié)果轉(zhuǎn)化為整數(shù)。這個(gè)整數(shù)就是新的狀態(tài)s。
問(wèn)題和問(wèn)題標(biāo)志
首先助币，?是很簡(jiǎn)單的：它僅僅是橢圓曲線點(diǎn)的x坐標(biāo)浪听，而舍棄了y坐標(biāo)。這也就意味著攻擊者如果能看到?的輸出眉菱，那么攻擊者就容易找到橢圓曲線上的這個(gè)點(diǎn)迹栓。在它自身來(lái)講，不是一個(gè)很大的問(wèn)題俭缓；但是如我們所見(jiàn)迈螟，這是后門(mén)可能性的一個(gè)因素。
另一個(gè)缺陷是點(diǎn)轉(zhuǎn)化為偽隨機(jī)比特的過(guò)程尔崔。函數(shù)θ僅僅是簡(jiǎn)單地舍棄了16比特答毫。之前的設(shè)計(jì)舍棄了更多的信息：對(duì)于256比特橢圓曲線，設(shè)計(jì)在一些場(chǎng)景中舍棄了120-175比特季春。
錯(cuò)誤地舍棄重要的比特使得生成器有了小的偏差洗搂。下一個(gè)比特的特性被違反了，攻擊者有大于50%的幾率可以猜出下一個(gè)比特的正確值载弄。雖然在一千次中僅僅有一次是大于50%的耘拇；但是這對(duì)于被認(rèn)為是最完美的密碼學(xué)安全的偽隨機(jī)數(shù)生成器來(lái)說(shuō)依然是不可接受。
舍棄僅僅16位比特還帶來(lái)另一個(gè)問(wèn)題宇攻。因?yàn)檫@16比特是被丟棄的惫叛，只需要猜測(cè)2^16種可能就可以找到得到該輸出的?(rQ)的值。這是一個(gè)很小的數(shù)字：簡(jiǎn)單地進(jìn)行枚舉就可以了逞刷。這些值是?的輸出嘉涌，也就是橢圓曲線坐標(biāo)的x。由于我們知道它是橢圓曲線上的點(diǎn)夸浅，只需要將其代入到橢圓曲線方程仑最，即可驗(yàn)證我們的猜測(cè)。
常量a帆喇，b警医，p都是由曲線決定的。只需要簡(jiǎn)單地猜測(cè)一個(gè)x的值坯钦，就只有y是未知的了预皇。我們可以有效地計(jì)算它，計(jì)算等式右邊的值然后檢查它是不是一個(gè)平方數(shù)y^2=q.如果它是,A=(x,√q)=(x,y)就是橢圓曲線上的點(diǎn)婉刀。這就給出了一個(gè)可能的點(diǎn)A吟温，也就是用來(lái)產(chǎn)生輸出的rQ。
通常情況下這并不是一個(gè)問(wèn)題路星。為了找出算法的狀態(tài)溯街，攻擊者需要找到r诱桂，這樣他們就可以得到內(nèi)部狀態(tài)s洋丐。對(duì)于已知rQ呈昔，他們依然需要去解決橢圓曲線離散對(duì)數(shù)問(wèn)題，來(lái)找到r友绝。我們假定這個(gè)問(wèn)題是非常非常難的堤尾。
記住橢圓曲線最開(kāi)始是用來(lái)做非堆成加密的。該問(wèn)題通常被認(rèn)為是很難解的迁客，但是如果我們有額外的信息呢郭宝？如果有一個(gè)秘密的e，使得eQ=P掷漱？
假設(shè)攻擊者恰恰知道e粘室。重復(fù)上面的數(shù)學(xué)公式。嘗試之前找出的A也就是rQ卜范。然后計(jì)算
最后的步驟和e衔统，P，Q有很大的關(guān)系海雪。這個(gè)就非常有趣了锦爵，因?yàn)?(rP)就是算法中計(jì)算的s，算法的新的狀態(tài)奥裸。也就是意味著如果攻擊者知道e险掀，就可以從任意輸出很容易地計(jì)算出新的狀態(tài)s，他們就可以預(yù)測(cè)生成器的所有未來(lái)的值了湾宙。
這個(gè)假設(shè)攻擊者的A就是正確的A樟氢。因?yàn)閮H僅有16比特被丟棄，也就只有16比特?cái)?shù)據(jù)需要去猜測(cè)侠鳄。也就是有216個(gè)可能的x坐標(biāo)嗡害。實(shí)驗(yàn)顯示，有一半的x坐標(biāo)可以找到橢圓曲線上對(duì)應(yīng)的點(diǎn)畦攘，也就是有215種可能的點(diǎn)A霸妹，其中一個(gè)是rQ。對(duì)于現(xiàn)代計(jì)算機(jī)來(lái)說(shuō)這是一個(gè)很小的值知押，小到完全可以去嘗試所有可能性叹螟。因此可以說(shuō)如果攻擊者知道這個(gè)秘密的e值，那么他就可以攻破生成器算法台盯。
如果有一個(gè)神奇的e罢绽，使得eQ=P，然后選擇P和Q（不用解釋P和Q是從哪里得來(lái)的）静盅，這樣你就可以破解這個(gè)生成器良价。你會(huì)怎么挑選這些值寝殴。
為了強(qiáng)調(diào)它的可能性，研究者從NIST的曲線點(diǎn)P的p值開(kāi)始明垢，然后使用他們自己的Q‘蚣常。他們只需要從P開(kāi)始，選擇一個(gè)隨機(jī)數(shù)d（保持它的私密性）痊银，然后設(shè)置Q’=dP抵蚊。這里的技巧是如果知道Q'=dP里的d，那么可以有效地計(jì)算eQ‘=P里的e溯革。這個(gè)e就是之前攻擊需要的值贞绳。當(dāng)他們嘗試找出這個(gè)值，他們實(shí)驗(yàn)了所有的情況（也就是致稀，很多的d）冈闭，能看到輸出的32個(gè)字節(jié)就可以決定內(nèi)部狀態(tài)s。
這一些抖单，當(dāng)然萎攒，都只是為了強(qiáng)調(diào)P和Q的特定值可能是一個(gè)秘密的后門(mén)。并沒(méi)有證據(jù)顯示這個(gè)實(shí)際的值存在后門(mén)臭猜。然后躺酒，這個(gè)標(biāo)準(zhǔn)里從來(lái)不解釋，他們是怎么得來(lái)這個(gè)神奇的Q的蔑歌，這就不能給人多大的信心羹应。典型地，密碼學(xué)標(biāo)準(zhǔn)使用隱藏備用的數(shù)字次屠，例如一些常量园匹，比方說(shuō)π，或者自然對(duì)數(shù)的底數(shù)e劫灶。
如果一些人知道后門(mén)裸违，后續(xù)明顯是毀滅性的。本章已經(jīng)論述了密碼學(xué)安全的偽隨機(jī)數(shù)生成器的必要性：攻破了隨機(jī)數(shù)等于其他的使用這個(gè)生成器的其他密碼系統(tǒng)也會(huì)被完全攻破本昏。
有兩種途徑來(lái)試圖糾正該算法：
讓θ更復(fù)雜一些供汛，使其難以逆運(yùn)算，而不是僅僅只舍棄16比特涌穆。這樣會(huì)使得尋找潛在的點(diǎn)很難怔昨，也就很難施行攻擊。一個(gè)顯而易見(jiàn)的方式是舍棄更多的比特宿稀。另一個(gè)方式是使用密碼學(xué)安全的hash函數(shù)趁舀，或者將兩個(gè)方法結(jié)合到一起。
每次運(yùn)行算法的時(shí)候生成一個(gè)隨機(jī)數(shù)Q祝沸，可能是選擇一個(gè)隨機(jī)d然后設(shè)置Q=dP矮烹。當(dāng)然d需要是足夠大的真正的隨機(jī)：如果θ沒(méi)有改變越庇，而d也僅僅有幾個(gè)值的話，攻擊者依然可以按照上述方法進(jìn)行攻擊奉狈。
這些都只是修復(fù)措施卤唉，更好的辦法是使用別的算法。這些建議沒(méi)有解決它很慢嘹吨，很奇怪的問(wèn)題搬味，現(xiàn)在它已經(jīng)被從標(biāo)準(zhǔn)中刪除境氢。
14.7 Mersenne Twister
Mersenne Twister是一個(gè)很通用的隨機(jī)數(shù)生成器蟀拷。它有很多優(yōu)點(diǎn)，很高的性能萍聊，很大的區(qū)間219937-1=4*106001,它也通過(guò)了所有需要隨機(jī)性的測(cè)驗(yàn)问芬。盡管它有這么多的優(yōu)點(diǎn)，但是它不是密碼學(xué)安全的寿桨。
深入了解Mersenne Twister
為了強(qiáng)調(diào)為什么Mersenne Twister不是密碼學(xué)安全的此衅，本節(jié)將深入來(lái)看一下算法的工作機(jī)制。幸運(yùn)的是亭螟，它并不是很復(fù)雜挡鞍。
標(biāo)準(zhǔn)的Mersenne Twister算法有一個(gè)內(nèi)部狀態(tài)的數(shù)組S，包含了624個(gè)無(wú)符號(hào)32位整數(shù)预烙，和一個(gè)指向當(dāng)前整數(shù)的索引i墨微。它包括三個(gè)步驟：
一個(gè)優(yōu)化的初始化函數(shù)，它將從一個(gè)初始化的隨機(jī)值（種子）來(lái)產(chǎn)生初始狀態(tài)扁掸。
一個(gè)狀態(tài)生成函數(shù)翘县，用來(lái)從舊的狀態(tài)產(chǎn)生新的狀態(tài)
一個(gè)擴(kuò)展函數(shù)，也被稱為是回火函數(shù)谴分，它會(huì)從當(dāng)前的狀態(tài)（i指向的元素）產(chǎn)生一個(gè)隨機(jī)數(shù)锈麸。
當(dāng)調(diào)用擴(kuò)展函數(shù)的時(shí)候，索引值會(huì)加一牺蹄。當(dāng)所有的狀態(tài)都被用來(lái)產(chǎn)生過(guò)隨機(jī)數(shù)之后忘伞，初始化函數(shù)再次被調(diào)用。狀態(tài)初始化函數(shù)在第一個(gè)數(shù)字被擴(kuò)展之前也需要被調(diào)用沙兰。
然后氓奈，狀態(tài)被重新生成，隨后每一個(gè)元素再次執(zhí)行擴(kuò)展函數(shù)僧凰，直到用完探颈。這個(gè)過(guò)程無(wú)限重復(fù)。
本節(jié)將對(duì)每一步進(jìn)行簡(jiǎn)單介紹训措。擴(kuò)展的工作是超出了本書(shū)的范疇伪节，但是我們僅是簡(jiǎn)單地介紹一下就足以看出為什么Mersenne Twister不是密碼學(xué)安全的隨機(jī)數(shù)生成器光羞。
初始化函數(shù)
初始化函數(shù)創(chuàng)建一個(gè)Mersenne Twister的狀態(tài)數(shù)組，以及一個(gè)很小的數(shù)（種子）作為初始化隨機(jī)數(shù)怀大。
這個(gè)數(shù)組以種子作為開(kāi)始纱兑，然后下一個(gè)元素是從一個(gè)常量，上一個(gè)元素化借，以及新元素的索引共同產(chǎn)生的潜慎。元素被逐個(gè)產(chǎn)生直到達(dá)到624個(gè)。
下面是Python的源代碼：
def uint32(n):
return 0xFFFFFFFF & n
def initialize_state(seed):
state = [seed]
for i in range(1, 624):
prev = state[-1]
elem = 0x6c078965 * (prev ^ (prev >> 30)) + i
state.append(uint32(elem))
return state
對(duì)于沒(méi)有接觸過(guò)Ptyhon或者它的位操作的人來(lái)說(shuō)：
">>"和“<<”是右移和左移
"&"是二進(jìn)制與蓖康，0&0=0&1=1&0=0&0=0铐炫，1&1=1
""是二進(jìn)制異或，"="是異或和賦值到左側(cè)蒜焊，所以x=k和x=xk是一回事倒信。
狀態(tài)重新生成函數(shù)
狀態(tài)重生成函數(shù)輸入當(dāng)前狀態(tài)，輸出一個(gè)新?tīng)顟B(tài)泳梆。在第一數(shù)字被擴(kuò)展之前被調(diào)用鳖悠，之后每624個(gè)元素被用完之后被調(diào)用。
該函數(shù)的Python的源代碼非常的簡(jiǎn)單优妙。注意它是在數(shù)組元素的位置上修改乘综，而不是產(chǎn)生一個(gè)新的數(shù)組。
def regenerate(s):
for i in range(624):
y = s[i] & 0x80000000
y += s[(i + 1) % 624] & 0x7fffffff
z = s[(i + 397) % 624]
s[i] = z ^ (y >> 1)
if y % 2:
s[i] ^= 0x9908b0df
表達(dá)式s[(i + n) % 624]中的"%"表示狀態(tài)的下一個(gè)元素套硼，當(dāng)沒(méi)有下一個(gè)元素的時(shí)候它將會(huì)從第一個(gè)元素重新開(kāi)始卡辰。
值0x80000000和0x7fffffff解析為32位數(shù)字的時(shí)候有特定的含義。0x9=80000000只有第一位是1熟菲，0x7fffffff除了第一位以外全都是1.循環(huán)的前兩行中的二進(jìn)制與操作看政，y包含了狀態(tài)元素的最高位以及下一個(gè)元素的除了最高位之后的位。
回火函數(shù)
在產(chǎn)生隨機(jī)數(shù)之前回火函數(shù)被應(yīng)用在狀態(tài)的當(dāng)前元素上抄罕。源碼如下
_TEMPER_MASK_1 = 0x9d2c5680
_TEMPER_MASK_2 = 0xefc60000
def temper(y):
y ^= uint32(y >> 11)
y ^= uint32((y << 7) & _TEMPER_MASK_1)
y ^= uint32((y << 15) & _TEMPER_MASK_2)
y ^= uint32(y >> 18)
return y
它可能不是很明顯允蚣，尤其是當(dāng)你沒(méi)有使用過(guò)二進(jìn)制的邏輯運(yùn)算，這個(gè)函數(shù)是雙射或者說(shuō)一對(duì)一的呆贿，每一個(gè)32比特的整數(shù)輸入數(shù)組映射到一個(gè)輸出嚷兔。反過(guò)來(lái)，每一個(gè)32比特的數(shù)字的輸出僅有一個(gè)32比特的數(shù)字作為輸入做入。因?yàn)樗褂昧俗笠坪陀乙频牟僮髅拔赡軙?huì)覺(jué)得它舍棄了一些數(shù)據(jù)，然后可能無(wú)法做逆運(yùn)算竟块。這些操作確實(shí)丟棄了一些比特壶运，然后這個(gè)嚴(yán)格的計(jì)算異或：這些移位只是用來(lái)和回火掩碼進(jìn)行異或。異或操作是可逆的浪秘，因?yàn)槊恳粋€(gè)獨(dú)立的操作都是可逆的蒋情，他們的組合也是埠况。
因?yàn)榛鼗鸷瘮?shù)是一對(duì)一的，它有一個(gè)逆函數(shù)：一個(gè)函數(shù)用來(lái)計(jì)算一個(gè)數(shù)的逆火數(shù)棵癣。如果對(duì)于二進(jìn)制計(jì)算不是很熟悉辕翰，這個(gè)操作可能不是那么明顯，但是沒(méi)關(guān)系狈谊，最差情況也可以暴力地計(jì)算喜命。假設(shè)嘗試了每一個(gè)32位整數(shù)，然后記錄這個(gè)對(duì)照關(guān)系在一張大表里河劝。當(dāng)需要結(jié)果的時(shí)候壁榕，查詢一下表，找到原始值丧裁。這個(gè)表會(huì)有32*2^ 32比特大小护桦，17GB含衔，很大煎娇，但是不是不可能的。
幸運(yùn)地是贪染，有簡(jiǎn)單的方法來(lái)計(jì)算回火函數(shù)的逆缓呛。下一節(jié)將介紹為什么Mersenne Twister不是密碼學(xué)安全的。對(duì)于對(duì)逆火函數(shù)感興趣的杭隙，其源碼如下：
def untemper(y):
y ^= y >> 18
y ^= ((y << 15) & _TEMPER_MASK_2)
y = _undo_shift_2(y)
y = _undo_shift_1(y)
return y
def _undo_shift_2(y):
t = y
for _ in range(5):
t <<= 7
t = y ^ (t & _TEMPER_MASK_1)
return t
def _undo_shift_1(y):
t = y
for _ in range(2):
t >>= 11
t ^= y
return t
密碼學(xué)安全
密碼學(xué)安全指的是：它不能預(yù)測(cè)到未來(lái)的輸出也不能用現(xiàn)在的輸出覆蓋過(guò)去的輸出哟绊。Mersenne Twister不具備這個(gè)特性。
偽隨機(jī)數(shù)生成器痰憎，包括這些密碼學(xué)安全的和不安全的票髓，都定義了他們的內(nèi)部狀態(tài)。畢竟它們是確定性的算法：它們只是努力地假裝它們不是铣耘。密碼學(xué)安全的和原始的隨機(jī)數(shù)生成器的本質(zhì)區(qū)別是密碼學(xué)安全洽沟，算法不能泄漏任何有關(guān)于它們內(nèi)部狀態(tài)的信息，而一般的算法則無(wú)所謂蜗细。
記住Mersenne Twister裆操，隨機(jī)數(shù)是由當(dāng)前的狀態(tài)的元素產(chǎn)生，使用回火函數(shù)炉媒，然后得到結(jié)果踪区。并且回火函數(shù)有逆函數(shù)。也就是得到了算法的輸出吊骤，然后使用逆函數(shù)缎岗，就可以得到狀態(tài)的624個(gè)元素中的一個(gè)。
假設(shè)我是唯一一個(gè)看到算法輸出的人白粉，然后你在狀態(tài)的開(kāi)始階段也就是算法的一個(gè)新的實(shí)例传泊，這也就意味著僅需要產(chǎn)生624個(gè)隨機(jī)數(shù)茅郎，我就可以克隆你的狀態(tài)。
盡管攻擊者并不能看到所有624個(gè)數(shù)字或渤，他們通常也可以重構(gòu)未來(lái)的狀態(tài)系冗，這主要是由于過(guò)去狀態(tài)與未來(lái)狀態(tài)之間簡(jiǎn)單的構(gòu)造函數(shù)。
再次薪鹦，這不是Mersenne Twister的弱點(diǎn)掌敬。它被設(shè)計(jì)的快速并且強(qiáng)隨機(jī)。它并不是用來(lái)不可預(yù)測(cè)的池磁，而這恰恰是密碼學(xué)安全的隨機(jī)數(shù)生成算法的特性奔害。
