最好的计算机能产生的是伪随机序列产生器,什么意思呢?许多人试图形式化的方式定义它,但我不赞成,随机数序列是看起来是随机的序列,序列的周期应足够长,使得实际应用中相当长的有限序列都不是周期性的。就是说如果你需要十亿个随机数据,就不要选择仅在一万六千比特后就重复的序列产生器。这些相对短的非周期性的子序列应该尽可能和随机序列没有多少区别。
如果一序列产生器是伪随机的,它应该有下面的性质:
(1)看起来是随机的
这表明它通过了我们所能找到的所有随机性统计检验。
人们在计算机上已经做了许多努力来产生好的伪随机序列,学术文献中有很多讨论伪随机序列产生器和各种随机性检验的,但所有这些产生器是周期的,都不可能例外。然而周期大于2256比特的随机数序列,能够大量得到应用。
这里的关键问题还是那些奇妙的相关性和奇怪的结果。如果你以某种方式使用它们,则每个随机数序列产生器都将产生这些相同的结果。这正是为什么密码分析者用它来对系统进行攻击的原因。
密码学意义上安全的伪随机序列
密码的应用比其他大多数应用对伪随机序列的要求更严格。密码学的随机性并不仅仅意味着统计的随机性,虽然它也是其中的一部分。密码学意义上安全的伪随机数,还必须具有下面的性质
(2)它是不可预测的
即使给出产生序列的算法或硬件和所有以前产生的比特流的全部知识,也不可能通过计算来预测下个随机比特应是什么。
密码学意义上安全的伪随机序列应该是不可压缩的…,…除非你知道密钥。密钥通常是用来设置产生器的初始状态的种子。
像任何密码算法一样,密码学意义上安全的伪随机序列产生器也会受到攻击,就好像加密算法有可能被破译一样,破译密码学意义上安全的伪随机序列产生器也是可能的。密码学讲的都是关于如何使产生器抵抗攻击。
