随机性与伪随机数生成器随机性与伪随机数生成器主讲人：赵永哲主讲人：赵永哲e_mail: yongzhe jlu.edu.cn电话：电话：13180888761安全的密钥安全的密钥 加密算法的安全性是以密钥的安全性为基础的。加密算法的安全性是以密钥的安全性为基础的。安全的密钥指的是这个密钥必须是随机数。安全的密钥指的是这个密钥必须是随机数。如果它们不随机，或如果在产生随机数过程中有一如果它们不随机，或如果在产生随机数过程中有一点偏差，破译者就能利用这个偏差对保密信息进行点偏差，破译者就能利用这个偏差对保密信息进行破译破译 随机性随机性伪随机序列伪随机序列密码学意义上的伪随机序列密码学意义上的伪随机序列真随机序列真随机序列伪随机序列伪随机序列 均匀分布数列中每个数出现的频率应相等或近似相均匀分布数列中每个数出现的频率应相等或近似相等。等。 应该有大约相同的应该有大约相同的0和和1 长度为长度为1的游程大约占一半的游程大约占一半 长度为长度为2的游程大约占的游程大约占1/4 长度为长度为3的游程大约占的游程大约占1/8密码学意义上的伪随机序列密码学意义上的伪随机序列不可预测的不可预测的 即使给出产生序列的算法或硬件和所有以前产生的即使给出产生序列的算法或硬件和所有以前产生的位序列，也不能预测下一个随机位是什么位序列，也不能预测下一个随机位是什么真随机序列真随机序列不能重复产生不能重复产生 即使在完全相同的操作条件下用完全相同的输入对即使在完全相同的操作条件下用完全相同的输入对序列发生器操作两次，也将得到两个完全不同的、序列发生器操作两次，也将得到两个完全不同的、毫不相关的位序列。毫不相关的位序列。独立性数列中任意一数都不能由其他数推出独立性数列中任意一数都不能由其他数推出密钥的分类和对随机性的要求密钥的分类和对随机性的要求主密钥（主密钥（Master Key） 真随机序列真随机序列会话密钥（会话密钥（Session Key） 伪随机序列伪随机序列真随机数生成器真随机数生成器 RNG Random Number GeneratorsRandom Number Generators are generating numbers in a sequence in such away that the next number has no relation with the previous numbers Good RNGsTuring Award winner in 2000Andrew Chi-Chih Yao 姚期智姚期智Contributions 貢献貢献Theory of computationComplexityTheory of RNGs 随机数随机数理论理论 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 statistical 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 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 physical 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. 伪随机数生成器伪随机数生成器PRNG Pseudo Random Number Generators伪随机数生成器是一个确定性算法，用一个长度为伪随机数生成器是一个确定性算法，用一个长度为k的二进制序列作为愉入，算法就能产生长度为的二进制序列作为愉入，算法就能产生长度为m (mk)的随机数序列。的随机数序列。伪随机生成器的输入称为产生器的种子。伪随机生成器的输入称为产生器的种子。 线性同余算法的线性同余算法的PRNG Xn+1=(aXn+c) mod m模数模数m(m0)，乘数乘数a(0am)，增量增量c(0cm)，初值即种子初值即种子X0(0X0m)；如果如果m、a、c、X0都为整数，则产生的随机数数列都为整数，则产生的随机数数列Xn也都是整数，且也都是整数，且0Xnm。线性同余算法的线性同余算法的PRNGSimple, fastestFor 32-bit words, the period can reach 232 Insecure, the formula can be worked out from outputFails in many testsSufficiently random for many applications ANSI X 9.17的伪随机数产生器的伪随机数产生器其中加密其中加密E EK K(X)(X)表示用密钥对表示用密钥对X X进行三重进行三重DESDES加密。加密。K K是密钥。是密钥。V V0 0是秘密的是秘密的6464位种子。位种子。T T是时间标记。是时间标记。R Ri i是预产生的随机密钥。是预产生的随机密钥。BBS伪随机数产生器伪随机数产生器Blum-Blum-Shub (BSS) generators, 1986 m=pq, p and q are distinct primes (质数质数) of the form 4z+3m has 1024 to 4096 bitsOutput the last bit of Xn+1Well distributed: pass all tests in theory 可以通过所可以通过所有有检验检验Secure but very slowThe period depends on the seed and can only be worked out using an algorithm. 使用伪随机数产生器应注意的问题使用伪随机数产生器应注意的问题基于基于 历历 史史 先例，先例，PRNG的种子通常是参照系统时钟的种子通常是参照系统时钟生成的。这个想法是使用系统时间的某一点来作为生成的。这个想法是使用系统时间的某一点来作为种子。这意味着如果能算出生成器什么时间发生，种子。这意味着如果能算出生成器什么时间发生，那么就可以知道由生成器生成的每一个值。可见，那么就可以知道由生成器生成的每一个值。可见，用时钟播种的伪随机数，所有结果不是不可预测的。用时钟播种的伪随机数，所有结果不是不可预测的。如果想要安全性，必须为数字生成器播种一个真正如果想要安全性，必须为数字生成器播种一个真正的随机数。的随机数。在线赌博中欺骗在线赌博中欺骗 Reliable Software Technologies (RST)的软件安全的软件安全性组最近在性组最近在 Texas Hold em Poker（由（由 ASF 软件软件公司发行）的实现中发现了一系列缺陷。这个揭秘公司发行）的实现中发现了一系列缺陷。这个揭秘允许欺骗性的玩家可以实时计算每人手中确切的牌。允许欺骗性的玩家可以实时计算每人手中确切的牌。这意味着，使用这个揭秘的玩家可以知道每个对家这意味着，使用这个揭秘的玩家可以知道每个对家手中的牌和将要发出的牌。手中的牌和将要发出的牌。调用调用 randomize() 来在每副牌生成前生成一副随机来在每副牌生成前生成一副随机牌。这个实现是用牌。这个实现是用 Delphi 4 （一种（一种 Pascal IDE）构）构建的，随机数生成器的种子是按照系统时钟，用午建的，随机数生成器的种子是按照系统时钟，用午夜后的毫秒数选取的。这意味着随机数生成器的输夜后的毫秒数选取的。这意味着随机数生成器的输出是容易预测的。出是容易预测的。Texas Hold em Poker的一系列缺陷的一系列缺陷在实际的纸牌中，有在实际的纸牌中，有 52!（大约是（大约是 2 226）种可能的、不同的）种可能的、不同的洗牌顺序。洗牌顺序。32 位的随机数生成器的种子必须是位的随机数生成器的种子必须是 32 位数字，这意味者只位数字，这意味者只有刚刚超过有刚刚超过 40 亿个的可能的种子。远远少于亿个的可能的种子。远远少于 52!。 基于午夜后的毫秒数挑选种子。一天之内只有基于午夜后的毫秒数挑选种子。一天之内只有 86,400,000 个个毫秒。毫秒。86,400,000 远远少于远远少于 40 亿。亿。将攻击程序与生成伪随机数的服务器上的系统时钟同步，使将攻击程序与生成伪随机数的服务器上的系统时钟同步，使得可能组合的数量减少到大约得可能组合的数量减少到大约 200,000 种可能性。种可能性。 发现这个薄弱环节的发现这个薄弱环节的 RST 开发的工具需要知道纸牌中的五张开发的工具需要知道纸牌中的五张牌。基于这五张牌，程序从几十万个可能的洗牌方法中搜索牌。基于这五张牌，程序从几十万个可能的洗牌方法中搜索并推出最优匹配。在并推出最优匹配。在 Texas Hold em Poker 情形中，这意情形中，这意味着程序将欺骗性玩家手中的两张牌作为输入，再加上三个味着程序将欺骗性玩家手中的两张牌作为输入，再加上三个玩家的第一张翻开的牌（发牌）。玩家的第一张翻开的牌（发牌）。下次课再见！下次课再见！