隨機性與偽隨機數(shù)生成器.ppt

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

2、位序列，也不能預(yù)測下一個隨機位是什么,真隨機序列,不能重復(fù)產(chǎn)生 即使在完全相同的操作條件下用完全相同的輸入對序列發(fā)生器操作兩次，也將得到兩個完全不同的、毫不相關(guān)的位序列。 獨立性數(shù)列中任意一數(shù)都不能由其他數(shù)推出,密鑰的分類和對隨機性的要求,主密鑰（Master Key） 真隨機序列 會話密鑰（Session Key） 偽隨機序列,真隨機數(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 隨機數(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.,偽隨機數(shù)生成器,PRNG Pseudo

7、Random Number Generators 偽隨機數(shù)生成器是一個確定性算法，用一個長度為k的二進制序列作為愉入，算法就能產(chǎn)生長度為m (mk)的隨機數(shù)序列。 偽隨機生成器的輸入稱為產(chǎn)生器的種子。,線性同余算法的PRNG,Xn+1=(aXn+c) mod m 模數(shù)m(m0)， 乘數(shù)a(0am)， 增量c(0cm)， 初值即種子X0(0X0m)； 如果m、a、c、X0都為整數(shù)，則產(chǎn)生的隨機數(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的偽隨機數(shù)產(chǎn)生器,其中加密EK(X)表示用密鑰對X進行三重DES加密。K是密鑰。 V0是秘密的64位種子。T是時間標(biāo)記。Ri是預(yù)產(chǎn)生的隨機密鑰。,BBS偽隨機數(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 可以通過所有檢驗 Secure but very slow The period depends on the seed and can only be worked out using an algorithm.,使用偽隨機數(shù)產(chǎn)生器應(yīng)注意的問題,基于 歷 史 先例，PRNG的種子通常是參照系統(tǒng)時鐘生成的。這個想法是使用系統(tǒng)時間的某一點來作為種子。這意味著如果能算出生成器什么時間發(fā)生，那么就可以知道由生成器生成的每一個值?？梢?，

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