购买
下载掌阅APP,畅读海量书库
立即打开
畅读海量书库
扫码下载掌阅APP

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

上一篇讲了对随机数的检验,这一篇我们来讲讲如何用计算机生成随机数。通常,计算机里的随机数生成算法被叫作“伪随机数生成算法”,又叫“决定式随机位生成器”(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位。高位的数字,循环周期会短,只输出低位可以更好地通过统计学测试。

Java语言中的LCG随机数生成函数源代码

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证书,所以这不是纸上谈兵。

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

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

彩票开奖装置就是一个硬件随机数生产器

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

思考题

如果你有一枚均匀的硬币,如何用这枚硬币,让3个人玩猜硬币游戏?

如果你有一枚不均匀的硬币,如何想出用这枚硬币公平地玩二人猜硬币游戏? e5d3CFSwcpq4Z3tlgM82zue7BUy/3ShSxZ3W4+fqp7nYtTbnfJ2nm4EPmq33YOSL

点击中间区域
呼出菜单
上一章
目录
下一章
×