在“确定”中产生“不确定”

上一篇讲了对随机数的检验，这一篇我们来讲讲如何用计算机生成随机数。通常，计算机里的随机数生成算法被叫作“伪随机数生成算法”，又叫“决定式随机位生成器”（DRBG），意思就是它能随机生成1位二进位，以50%的概率生成“0”或者“1”。

为什么这种算法都是二进位的生成器？原因在于，平时我们使用均匀分布随机数的场合是最多的，有了均匀分布的随机数，转换成其他分布也是比较简单的。而计算机内部信息又都是用二进位存储的，如果一个计算机内部浮点数是小数点后32位，那就可以批量产生32位的随机二进位，作为一种随机数“资源”，供用户使用。

那它为什么又叫“伪随机数生成算法”？为什么加一个“伪”字？那是因为它达不到上一篇讲过的“真随机数”的要求。在目前计算机架构下，永远不可能有“真”随机数生成算法，原因在于目前计算机所执行的程序都是确定性的，按事先输入的指令运行，不存在任何不确定的成分。

但在实际运用中，通常对随机数没有非常高的要求。一般来说，只要保证：

根据相当长的历史随机数，无法用当代主流的计算能力，在相当长的时间内，对之后随机数的猜测的成功或失败概率，与0.5之间产生不“可忽略的”的区别，那么这种随机数就是合格可用的。

从以上定义中，你会发现，一个合格的伪随机数生成算法的条件是动态的，是可以演变的。一个算法可能随着技术和算力发展，从合格变为不合格。

从后面具体的算法例子中，你也会看到所有伪随机数生成算法，它们都是有“周期”的。这个算法在输出了非常多的随机数之后，又会返回之前的输出模式，开始重复自己的输出了。这是它们被称为“伪随机”的又一个原因。只是这个周期是非常长的，我们不太可能在一个软件的运行寿命内观察到这种周期的发生。

但也是因为有周期，我们不能让算法总是从固定的初始状态产生随机位，否则每次随机数重新产生时，都是从同样的数字开始输出，这是不行的。所以就需要一个“种子数”，英文叫“seed”，去决定从周期中的哪个位置开始产生随机数。这一点对会编程的读者来说再熟悉不过了，第一次编程使用随机数生成函数的人都会发现，如果没有初始化“种子”，系统的随机函数总是返回同样的数。

所以这里出现了一个小尴尬，即为了产生随机数，我们先需要一个随机数作为“种子”。对不严格的场合，我们经常会使用当前系统时间的毫秒数作为种子数，但在一些对安全性要求很高的场合，人们还会使用更复杂的方法产生种子数。

让人吃惊的是，在计算机发明后的很长一段时间里，人们所使用的随机数生成算法是很粗糙的。比如，计算机刚发明的20世纪40年代，冯·诺依曼就想了一个“平方取中”法，来产生随机数。

取一个四位数作为种子，如1234，算出它的平方是1522756。然后在左边填充1个0，变01522756，然后把中间4个数字输出作为随机数，就是5227。然后对5227再求平方，取中间四个数字，如此重复操作下去。

这个算法你一看就有问题啊，当看到上一个数字就非常容易知道下一个输出是多少，都不用管种子数，怎么能叫随机数呢？但是，冯·诺依曼觉得，这种随机数已经符合他的需求了，速度快，需要的资源也少，而且有可重复性，便于排错。如果使用其他硬件设备产生随机数，如打孔纸带机，那速度就太慢了，消耗的资源也太大。同时，冯·诺依曼指出，如果用过于复杂的数学方法来产生“随机数”，那隐藏的错误可能比其能解决的问题还多。

冯·诺依曼这种算法显然是不能满足很多场合的随机数需要的。从20世纪60年代开始，人们普遍采用一种名为“线性同余法”（简称LCG）的算法来产生随机数。这个算法非常简单。我们考虑这么一个函数：

把余数作为随机数，然后下一个随机数就是把上一个余数作为 ，迭代计算下一个余数。甚至其中的 可以取0，那么就是用 除以 ，求余数就可以了。比如，取 ， ，种子数为1，迭代计算 除以17的余数，前10个余数如下：

2，4，8，16，15，13，9，1，2，4

这些数看上去是不是已经很像随机数了？实际使用时，可以把每个余数都转化成二进制数，依次输出。但是，它很快就进入重复周期，其主要原因在于c取值太小了。

对标准LCG算法的递推公式：

其中一个推荐参数是：

（它是一个梅森素数，且在32位二进制以内，因此比较好用）， ，种子数可以取20210531，或者你喜欢的任何日期。请按上述公式写个程序，将结果迭代输出若干（二进制输出效果更佳），看看够不够“随机”。

LCG算法的优点很明显，就是简单、高效。只要公式中的 足够大，就可以使输出周期非常长，而且能通过上篇讲过的几乎所有统计学测试。所以该算法一出现就被广泛使用，至今Java语言标准库里的Random函数仍然用的是LCG算法，其中的被除数 是 ，因为计算机除以2幂次的计算是最快的，只要移位就可以了。 是一个奇怪的数字：25214903917， 。每次迭代时，余数度并没有都输出，而是被转化为二进位，再顺序倒转，然后输出第47位到第16位。高位的数字，循环周期会短，只输出低位可以更好地通过统计学测试。

LCG算法从20世纪60年代用到现在，足见其优越性，但必然也有些缺点。 3个参数必须小心选择，选得不好，就会出问题。一个著名的例子是，20世纪60年代IBM使用的一个LCG算法，叫RANDU。它使用 ，看上去这几个数字没啥不好，输出看上去也很“随机”。

1963年，有人通过简单运算，发现它连续迭代的3项余数之间有一个简单的减法关系：

这使这个算法在统计学上完全失败了。IBM在后来的机器中修正了参数，但很多人要么不知情，要么不在意，继续使用这一算法。后果就是，20世纪70年代，很多使用这个算法产生的研究结果都被认为是不可靠的。据推测，RANDU算法要到20世纪90年代早期才真正被废弃。RANDU算法就是历史上著名的一个貌似能产生随机数，但其实很不靠谱的例子。这也告诉我们，一个随机数算法能不能用，不是靠眼睛看看就可以过关的，你需要使用上一篇所讲的很专业的方法和软件对其进行测试。

另外需要注意的是，在需要严格加密的场合下，是不能使用LCG算法的，因为如果有人愿意，还是可以从LCG的历史输出里，去反推你的种子数。这相当于一道算术题：已知 和 除以 的余数，请计算一下 。对这个问题，是可以用一个多项式算法去求解的。所以，在需要加密的场合，不能使用LCG产生随机数，而要使用后面会提到的“密码学安全”算法。

1997年，两位日本研究者发明了一个名为“梅森旋转算法”的随机数生成方法。这里的“梅森”，是“梅森素数”的意思，因为它的周期就是一个很大的梅森素数。这个算法相比LCG算法的优点在于周期非常长，统计学指标上的质量比LCG更优。所以，它现在被广泛应用于主流的一些操作系统和编程语言，包括GNU库、php、Python和Ruby等。但要注意，它不是密码学安全的，只要有人拿到足够的输出，还是可以计算出所使用的种子数。

再说说“密码学安全”的随机数生成算法，首先，我们得定义什么是“密码学安全”？之前介绍的算法之所以“不安全”，在于我们可以通过观察历史数据，来推测出所使用的种子数，最终达到预测之后所产生的随机数的目的。

那反过来就是，一个“密码学安全”的随机数算法，要做到：给你相当多的历史数据，你也有非常强大的计算机，我仍然可以确保，你不能在充分的时间内，如1年，对我将来产生的随机数的猜测，产生任何“不可忽略”的提高。

这里的“相当多”“非常强大”“充分”“不可忽略”都是一些变量，我们不需要对这些变量有精确的数字定义，只要知道这些变量是可以用来衡量最终算法质量的。在有不同的安全性要求的场合，我们根据需求，可以给这些变量规定一些值。如果算法能达到我们定义的这些值，那么这个算法就可以被用在对应的场合。

数学家用的一个高招就是，把破解算法的难度与破解一个数学难题等价起来，即如果你能破解这个随机数算法，就等于破解了一个非常难的数学问题。既然能破解这个数学问题，你就能当数学家，那么大概你也用不着去破解算法了吧？

当然，也可能有人能破解这些算法，但是秘而不宣，利用这一能力谋取利益，或者达到一些自己的目的。比如，《达·芬奇密码》的作者丹·布朗写过另一部小说《数字城堡》。其背景就是美国政府秘密研究出一台超级计算机和一种秘密算法，使得他们可以解密目前网上主流加密算法加密过的信息，以此监控很多网上的秘密通信。当然，这只是小说的设定，目前没有什么证据证明有人掌握了某种破解随机数的超级算法。

对密码学安全随机数生成算法，我举一个例子。有一个算法以三位发明者名字的首字母命名——“B.B.S.算法”。这个算法的安全性就是依靠数学中的“二次剩余”问题：

求 除某个数后的余数。

在B.B.S算法中，这个被除数是两个很大素数相乘所得的。计算 除一个大数的余数很简单，但是它的逆运算就困难很多了：找到一个完全平方数，使它除以某个很大的数正好是某个余数。算法还有些其他细节，但总体上就是依靠二次剩余问题的难度来确保算法的安全性。

密码学安全算法虽然“安全”，但完全不必在任何场合都用这类算法，因为它要比前面的LCG和梅森旋转算法慢许多，而且消耗更多内存资源。所以一般应用中完全不需要用密码学安全算法。

另外，当你需要密码学安全算法时，也需要很小心地挑选。2013年，微软的两位研究员发表了一篇文章，指出美国国家安全局（简称“NSA”）推荐的一个“密码学安全”随机数算法中（Dual_EC_DRBG），所使用的参数是有弱点的。

他们发现这个算法本身没问题，但是，NSA推荐的初始化参数是精心挑选过的，使这个算法有了弱点。如果使用NSA推荐的这些参数，那其产生的随机数就可能被NSA推算出来。这很像小说《数字城堡》中的情节，但现实中确实发生了，实在是很惊人的一幕。

以上说了那么多随机数生成算法，其实还遗漏了一个随机数算法中的要点，就是“种子”数如何产生的问题。前面说过，种子数决定了算法从其周期哪个位置开始产生随机序列。如果算法两次输出的种子数一样，或者太接近，那么输出很快就会发生重复，这是我们不希望的。所以，需要一个随机数来“启动”一个随机数算法，这就是“种子”。但这个种子就不能再依靠伪随机数算法来产生了，否则就是死循环。

如前所述，在很多情况下，可以用系统时间的毫秒数作为种子数。但有些场合，这还不够随机，重复概率太大。那就需要搜集计算机能搜集到的像“随机”情况的数值，或者叫“熵”。常见的方法有：让用户随便敲几下键盘，移动几下鼠标，检测一下最近两次敲键盘的时间间隔、鼠标移动的距离、CPU的温度、麦克风传进来的噪声等。如果程序在手机上运行的话，还可以检查手机摆放的角度。总之，采集各种可以搜集到的噪声数据，然后用算法混合起来，以便种子数看上去最为“随机”，最难预测。

有的软件为了安全，规定产生若干随机位后要重新产生一个种子，重置一次。Linux操作系统就自带两个随机数生成器：/dev/random和/dev/urandom。其中/dev/random需要不断重置种子，如果它搜集到的噪声不够多，就会停下来，受到阻塞，直到搜集到足够多的噪声（也就是“熵”）之后才能继续。幸好，在绝大多数场合下，另一个不会受到阻塞的随机数生成器已经足够好用了。

最后，向大家介绍一个看上去有点夸张，但的确在使用中的一个“物理性”的种子数生成器，叫“岩浆灯”（Lava Lamp）。岩浆灯确实是一盏灯，它的外形有点像沙漏，但里面并不是岩浆，而是两种不同颜色的液体，这两种液体的比重差不多，但不会互相溶解。所以这种岩浆灯里的液体就不停地发生变动，比如一种颜色液体翻滚到上面，或者分裂成两团，或者沉下去。这种变化看上去是完全随机的，物理老师会告诉我们这叫“布朗运动”。

这种岩浆灯最早是20世纪90年代SGI公司发明的，还注册了专利。1997—2001年，有家公司短暂用这种岩浆灯产生种子数，但商业化并不成功，很快就放弃了。2009年成立的，位于旧金山的一家叫Cloundflare的公司重新使用了这种岩浆灯。在他们的业务中，一个重要的部分就是向客户提供网站需要的SSL证书。现在我们访问网站时，浏览器会时常提醒你这个网站有问题，证书不被信任等，其实就是SSL证书在起作用。而要生成SSL证书，就需要产生随机数。要产生随机数，就要用到种子数，Cloundflare公司就用岩浆灯来生成种子数。

他们的方法是：用数十盏岩浆灯铺满一堵墙，然后用一个摄像头持续拍摄这面墙。因为岩浆灯不停地变化，所以摄像头拍到的画面肯定也是不停地变化，再加上摄像头拍摄本身也有噪点，温度、湿度变化对拍摄也有影响。这些噪声结合在一起，用二进制来存储摄像头拍出的画面，其结果确实是很难预测的。而且，他们还在世界不同地方的3个办公室设置了这种岩浆灯，需要3个办公室产生的随机数结合在一起，混淆后，作为最后使用的种子数。

为了产生一个随机数，如此兴师动众，是不是有点夸张？但这种岩浆灯确实在提供服务。而且，在当前的互联网上，约10%的流量都在使用该公司产生的SSL证书，所以这不是纸上谈兵。

有关软件随机数生成算法就讲到这里了，我最大的感想是，生成安全可靠的随机数出人意料地难，而且几乎到了无所不用其极的地步。

那么有没有硬件随机数生成器呢？当然有，比如福利彩票开奖用的吹乒乓球的机器，就是一个硬件随机数生成器，前面说过的岩浆灯也是。如果计算机中能内置一个掷硬币的装置，那也是一个硬件随机数生成器。使用硬件的优越性在于可以更多利用环境噪声，历史上确实有过各种计算机可以用的硬件随机数生成器。它的缺点在于效率低，并且无法验证随机数的可靠性。

目前有人在研究利用各种量子的随机属性来产生随机数，如电路的瞬间噪声、粒子的衰变时间、光子穿过半透玻璃的概率等。这些量子行为是目前人们认为的最为接近“真随机”的自然现象了。如果能有使用量子的随机性产生的随机数，那应该是最为安全和接近“真”随机数的随机数。