什么是真正的随机数?

当你在iTunes上冲浪时,为了保证你银行账户的安全,计算机需要随机数的帮助。然而,它们是否和我们一样,只擅长于思考可预测的模式呢?Mads Haahr对此毫不怀疑。他说:「生成随机数不是应该留给人类来做的任务。」你可能希望他会这么说。作为都柏林三一学院的计算机科学家,他是一个有名的在线随机数生成器(random.org)的创始人。但他有自己的看法。

[caption id="attachment_5653" align="aligncenter" width="800"]图片: Eugenia Loli 图片: Eugenia Loli[/caption]

人类的大脑擅长于发现和生成模式。这热带稀草草原上,这种技能很有用,因为它能让我们在猛兽看见我们之前就发现它们。但是,它也限制了我们用随机和不可预测的方式思考的能力。这是一个问题,因为真正的随机性是非常有用的。随机数被用在密码学、计算、设计等领域上,应用十分广泛。我们无法做到「随机」,只好把这个任务交给计算机。

但是,如果随机任务完全依赖外包,也会存在自身的问题。最初的随机数生成器莫过于用于占卜和游戏的骰子,它们是六面的骨头,来自羊的脚后跟,每面刻有不同的数字。受到骨头形状的限制,有些数字出现的几率总是大于其他数字,为那些知道个中奥秘的人提供了可乘之机。

现代的随机数生成器包括赌场的骰子、轮盘和彩票球,但是对它们的怀疑一点也没有减少。

而且它不仅仅是程序问题。你不能只给计算机特定的规则来创造随机数,那不是真正的随机。相反,你需要使用一种算法来从一个更小的、无法预测的输入中「生成」一个看起来随机的输出:例如,从诸如π(圆周率)这样的随机字符串中提取并从通过使用日期和时间来确定随机数字但是这样做的问题是,由于输入的限制,这样的「伪随机」数是有限的,并且在一定时间后再趋向于非随机,如果你看的足够多,你能够猜出它的排列方式。

另一种选择是把计算机与一些物理源、「真正的」随机性相连。20世纪50年代,英国邮政局希望有一种方法来产生大量的随机数用来挑选其高级债券彩票的获奖者。这项工作落到了破解德国纳粹恩尼格玛密码的巨像电脑设计师肩上。他们创造了ERNIE(the Electronic Random Number Indicator Equipment,电子随机数指示装置)该装置利用电子混沌运动轨迹通过霓虹灯管来产生一个随机电子脉冲时间序列从而生成随机数。

ERNIE现在已经是第四代了,它的工作原理十分简单,即依靠热噪声晶体管产生的随机性。现代许多计算应用程序使用类似的原理,用芯片上的生成器来进行收集,如英特尔公司的RdRand和Via公司的Padlock。Haahr公司的生成器则是从原本嘈杂大气过程中生成随机数。

这样仍然存在两个问题。首先,在理论上,只要有足够的计算能力,任何人都可以重建经典物理过程来创造随机数。其次,更为实际的是,通常基于物理过程的随机数生成器产生随机数的速度不够快。

许多系统,如苹果使用UNIX平台,是通过将芯片上的随机发生器的输出与「熵池」的内容(充满其他随机组合)相结合。这可能是连接到计算机的任何设备产生的随机时序,也可能是产生随机噪声的用户键盘。然后通过「哈希函数」将组件组合起来生成一个随机数。哈希函数是将油水混合的数学问题:现有方法无法得知输入的序列,也无法对输出函数进行定量。

这意味着未来会有,也仍然存在着速度问题。解决办法通常是将物理随机数生成器仅作为能产生更丰富流量的种子程序来使用。

下面我们回到了算法问题。虽然这些程序方法的精确性是独一无二的,但根据2013安全报告师的报告表明,美国国家安全局知道这样一个生成器(名为dual_ec_drbg)的内部工作原理,可能就能通过它来破解加密。如果你只是玩网络游戏,这不是个大问题,但如果是数十亿美元的金融交易,或敏感文件加密,上述怀疑就会是个巨大隐患。

这种问题导致一些研究者提出,在古典世界里,随机性不仅是内在的而且还牵扯到谁拥有信息来源的问题,一个无懈可击的的随机性的来源是不存在的。对安全加密,我们必须转向量子物理,那里物体似乎是真正随机的。不像抛硬币,你可能会问是否一个光子撞击一个半镶银的镜子穿过它,或者是反射回来。不像旋转死亡,你会给一个电子六个电路去选择通过。「作为一个数学家,我喜欢我的随机性是有依据的,并且量子随机性数量告诉我们,」 来自安娜堡密歇根大学的 Carl Miller说, 「在这方面,它是独一无二的。」

密码系统利用量子理论的变化,的确在通讯方面更加安全。但是他们的安全也并不是最后的定论。提取量子随机性总是涉及到有人做出非随机性选择的设备,或者测量仪器等等。并不那么完美的光子检测,使用一定的方法也能够提供一个后门,那样的话,非随机性也能通过滑动。

一种仍处于验证之下的方式也许它的随机性会被放大,让你觉得你能有更多的可能性破解它。在纯粹随机理论之中,可以把N个随机位转换成2N个,也能用与原槽位完全不相干的数代替。

这些基于独立设备上的量子随机数的生成是我们为真正随机性的研究的最新进展。只要有人找到了研究的方法,也许在不久的将来,真正的随机性也许会实现。对于随机性的研究,将伴随着人类的发展永远进行下去。

本文选自new scientist,机器之心编译出品,参与成员:汪汪、孟婷、salmoner、Rui

入门
暂无评论
暂无评论~