1、隨機(jī)性與偽隨機(jī)數(shù)生成器,主講人：趙永哲 e_mail: yongzhe 電話安全的密鑰,加密算法的安全性是以密鑰的安全性為基礎(chǔ)的。 安全的密鑰指的是這個(gè)密鑰必須是隨機(jī)數(shù)。 如果它們不隨機(jī)，或如果在產(chǎn)生隨機(jī)數(shù)過(guò)程中有一點(diǎn)偏差，破譯者就能利用這個(gè)偏差對(duì)保密信息進(jìn)行破譯,隨機(jī)性,偽隨機(jī)序列 密碼學(xué)意義上的偽隨機(jī)序列 真隨機(jī)序列,偽隨機(jī)序列,均勻分布數(shù)列中每個(gè)數(shù)出現(xiàn)的頻率應(yīng)相等或近似相等。 應(yīng)該有大約相同的0和1 長(zhǎng)度為1的游程大約占一半 長(zhǎng)度為2的游程大約占1/4 長(zhǎng)度為3的游程大約占1/8,密碼學(xué)意義上的偽隨機(jī)序列,不可預(yù)測(cè)的 即使給出產(chǎn)生序列的算法或硬件和所有以前產(chǎn)生的

2、位序列，也不能預(yù)測(cè)下一個(gè)隨機(jī)位是什么,真隨機(jī)序列,不能重復(fù)產(chǎn)生 即使在完全相同的操作條件下用完全相同的輸入對(duì)序列發(fā)生器操作兩次，也將得到兩個(gè)完全不同的、毫不相關(guān)的位序列。 獨(dú)立性數(shù)列中任意一數(shù)都不能由其他數(shù)推出,密鑰的分類和對(duì)隨機(jī)性的要求,主密鑰（Master Key） 真隨機(jī)序列 會(huì)話密鑰（Session Key） 偽隨機(jī)序列,真隨機(jī)數(shù)生成器,RNG Random Number Generators Random Number Generators are generating numbers in a sequence in such away that the next number h

3、as no relation with the previous numbers,Good RNGs,Turing Award winner in 2000 Andrew Chi-Chih Yao 姚期智 Contributions 貢獻(xiàn) Theory of computation Complexity Theory of RNGs 隨機(jī)數(shù)理論,1946 -,If there is no practical way to predict the next bit of an RNG with more than 50% chance, the RNG will pass all statist

4、ical tests.,ORIONs Random Number Generator,ORIONs Random Number Generator consists of two independent analogue Zener diode based noise sources. Both signals are converted into random bit streams, combined and subsequently transmitted in the form of bytes to the RS-232 port of your computer. The baud

5、 rate is 9600. So the device is capable of supplying you with about 960random bytes or 7600 random bits per second 580,Quantum Random Bit Generator,http:/random.irb.hr/ QRBG121 is a fast non-deterministic random bit (number) generator whose randomness relies on intrinsic randomness of the quantum ph

6、ysical process of photonic emission in semiconductors and subsequent detection by photoelectric effect. In this process photons are detected at random, one by one independently of each other. Timing information of detected photons is used to generate random binary digits - bits.,偽隨機(jī)數(shù)生成器,PRNG Pseudo

7、Random Number Generators 偽隨機(jī)數(shù)生成器是一個(gè)確定性算法，用一個(gè)長(zhǎng)度為k的二進(jìn)制序列作為愉入，算法就能產(chǎn)生長(zhǎng)度為m (mk)的隨機(jī)數(shù)序列。 偽隨機(jī)生成器的輸入稱為產(chǎn)生器的種子。,線性同余算法的PRNG,Xn+1=(aXn+c) mod m 模數(shù)m(m0)， 乘數(shù)a(0am)， 增量c(0cm)， 初值即種子X(jué)0(0X0m)； 如果m、a、c、X0都為整數(shù)，則產(chǎn)生的隨機(jī)數(shù)數(shù)列Xn也都是整數(shù)，且0Xnm。,線性同余算法的PRNG,Simple, fastest For 32-bit words, the period can reach 232 Insecure, the

8、formula can be worked out from output Fails in many tests Sufficiently random for many applications,ANSI X 9.17的偽隨機(jī)數(shù)產(chǎn)生器,其中加密EK(X)表示用密鑰對(duì)X進(jìn)行三重DES加密。K是密鑰。 V0是秘密的64位種子。T是時(shí)間標(biāo)記。Ri是預(yù)產(chǎn)生的隨機(jī)密鑰。,BBS偽隨機(jī)數(shù)產(chǎn)生器,Blum-Blum-Shub (BSS) generators, 1986 m=pq, p and q are distinct primes (質(zhì)數(shù)) of the form 4z+3 m has 1024

9、to 4096 bits Output the last bit of Xn+1 Well distributed: pass all tests in theory 可以通過(guò)所有檢驗(yàn) Secure but very slow The period depends on the seed and can only be worked out using an algorithm.,使用偽隨機(jī)數(shù)產(chǎn)生器應(yīng)注意的問(wèn)題,基于 歷 史 先例，PRNG的種子通常是參照系統(tǒng)時(shí)鐘生成的。這個(gè)想法是使用系統(tǒng)時(shí)間的某一點(diǎn)來(lái)作為種子。這意味著如果能算出生成器什么時(shí)間發(fā)生，那么就可以知道由生成器生成的每一個(gè)值?？梢?jiàn)，

10、用時(shí)鐘播種的偽隨機(jī)數(shù)，所有結(jié)果不是不可預(yù)測(cè)的。如果想要安全性，必須為數(shù)字生成器播種一個(gè)真正的隨機(jī)數(shù)。,在線賭博中欺騙,Reliable Software Technologies (RST)的軟件安全性組最近在 Texas Hold em Poker（由 ASF 軟件公司發(fā)行）的實(shí)現(xiàn)中發(fā)現(xiàn)了一系列缺陷。這個(gè)揭秘允許欺騙性的玩家可以實(shí)時(shí)計(jì)算每人手中確切的牌。這意味著，使用這個(gè)揭秘的玩家可以知道每個(gè)對(duì)家手中的牌和將要發(fā)出的牌。 調(diào)用 randomize() 來(lái)在每副牌生成前生成一副隨機(jī)牌。這個(gè)實(shí)現(xiàn)是用 Delphi 4 （一種 Pascal IDE）構(gòu)建的，隨機(jī)數(shù)生成器的種子是按照系統(tǒng)時(shí)鐘，用午夜后的毫秒數(shù)選取的。這意味著隨機(jī)數(shù)生成器的輸出是容易預(yù)測(cè)的。,Texas Hold em Poker的一系列缺陷,在實(shí)際的紙牌中，有 52!（大約是 2 226）種可能的、不同的洗牌順序。 32 位的隨機(jī)數(shù)生成器的種子必須是 32 位數(shù)字，這意味者只有剛剛超過(guò) 40 億個(gè)的可能的種子。遠(yuǎn)遠(yuǎn)少于 52!。 基于午夜后的毫秒數(shù)挑選種子。一天之內(nèi)只有 86,400,000 個(gè)毫秒。86,400,000 遠(yuǎn)遠(yuǎn)少于 40 億。 將攻擊程序與生成偽隨機(jī)數(shù)的服務(wù)器上的系統(tǒng)時(shí)鐘同步