机性与伪随机数生成器.ppt

随机性与伪随机数生成器 主讲人：赵永哲 e_mail: yongzhe @ 电话 安全的密钥 加密算法的安全性是以密钥的安全性为基础的。 安全的密钥指的是这个密钥必须是随机数。 如果它们不随机，或如果在产生随机数过程中有一点偏差，破译者就能利用这个偏差对保密信息进行破译 随机性 伪随机序列 密码学意义上的伪随机序列 真随机序列 伪随机序列 均匀分布数列中每个数出现的频率应相等或近似相等。 应该有大约相同的0和1 长度为1的游程大约占一半 长度为2的游程大约占1/4 长度为3的游程大约占1/8 密码学意义上的伪随机序列 不可预测的 即使给出产生序列的算法或硬件和所有以前产生的位序列，也不能预测下一个随机位是什么 真随机序列 不能重复产生 即使在完全相同的操作条件下用完全相同的输入对序列发生器操作两次，也将得到两个完全不同的、毫不相关的位序列。 独立性数列中任意一数都不能由其他数推出 密钥的分类和对随机性的要求 主密钥（Master Key） 真随机序列 会话密钥（Session Key） 伪随机序列 真随机数生成器 RNG – Random Number Generators Random Number Generators are generating numbers in a sequence in such away that the next number has no relation with the previous numbers 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(0≤am)， 增量c(0≤cm)， 初值即种子X0(0≤X0m)； 如果m、a、c、X0都为整数，则产生的随机数数列{Xn}也都是整数，且0≤Xnm。 线性同余算法的PRNG Simple, fastest For 32-bit words, the period can reach 232 Insecure, the formula can be worked out from output Fails in many tests Sufficiently random for man