密码学的随机性与区块链随机数

背景介绍

随机数虽然看起来不起眼，但它却是信息安全的基础之一。在区块链中，随机数有很多的应用场景，例如抽奖活动、验证码、Token、密码应用场景等。

随机数的核心要义

随机数的核心是数的随机性。随机性是信息安全领域，尤其是密码学领域一个很关键的研究问题。在密码学中，对一个序列的随机性是这样定义的：“看起来是随机的，即能通过我们所能找到的所有正确的随机性检验。”

这个序列是不可预测的，即使给出产生序列的算法或者硬件设计和以前产生序列的所有知识，也不可能通过计算来预测下一个比特是什么或者计算代价很大几乎不可实现。

随机性在密码学中占有重要的地位，几乎所有的密码算法和协议都要用到一些对攻击者来说必须是秘密的数据。比如对一个密码算法来说，如果将秘密寓于密钥之中，那么密钥就是秘密，包括对称密码算法（DES、AES、IDEA 等）的密钥和非对称密码算法（RSA、DSA、Diffie-Hellman 等）的私钥等，而这些密钥必须是随机数。对于唯一已经证明了绝对安全性的一次一密系统来说，其安全性就依赖于随机的密钥。

随机数的核心要义是不可预测性，这也是对随机数最基本的底线要求。一旦随机数被人预测到，则基于随机性的安全体系将立刻崩塌。

随机数发生器

既然随机数如此重要，那么随机数生成器的地位也就不言而喻了。随机数生成器用来产生一个位序列，这个位序列的随机性就很重要。如何才能生成均匀的随机位序列呢？

掷骰子被认为是产生随机数的典型示例。统计学家 Francis Galton 在 1890 年的《自然》杂志中提出“在所有的产生随机数的事物中，我认为没有什么能够超越骰子了。” 在摇骰子的过程中，骰子在容器中不断地翻滚、互相撞击，以各种形式和角度与容器壁发生碰撞，在容器中的位置和形态在外界看来都是不可预知的，各种偶发因素一起参与摇骰子的过程中，比如容器哪怕只发生一次晃动，外界都不可能知道里面到底是什么形态。

迄今为止发现最早的骰子（4 个面）来自中东的一座公元前 24 世纪的坟墓里。公元前 1100 年的中国，一些“先知”利用火烧龟壳产生的随机龟裂对未来做预测。又过了几个世纪，在中国诞生了易经占卜法，利用 49 蓍草法进行占卜，其操作的分裂过程很类似于抛硬币。

真伪随机生成器

随机数生成器有真随机和伪随机之分。

只满足“随机数的核心要义”中所讲的随机性要求的其实是伪随机数生成器。伪随机数生成器是一个确定性算法，用一个长度为 k 的二进制序列作为输入，算法就能产生长度为 m（m>>k）的随机数序列，伪随机生成器的输入称为生成器的种子。

实际上，伪随机数生成器产生的随机数并不是真的随机。伪随机数生成器具有周期性，其产生的随机数序列总会产生重复，不过如果生成器的周期足够长（至少要远远大于可能采集的随机数的长度），那么这个随机数生成器产生的局部的随机序列也就和真随机序列看起来没有什么区别了。

真随机数生成器在满足“数的随机性”以及“序列不可预测”这两个要求之外，还要满足第三个要求：

这个序列不能重复产生，即使在完全相同的操作条件下用完全相同的输入对序列发生器操作两次，也将得到两个完全不同的、毫不相关的位序列。

满足了这三个要求的随机数生成器，其产生的随机数是不可重现的，即使是你自己也无法再次产生同样的随机数。

伪随机数生成器 PRNG(Pseudo Random Number Generator)

伪随机数生成器是由冯诺依曼在 1946 年创造的。他的基本思想是从一个随机数种子开始，对其平方，然后取中间值。接下来重复对得到的数取平方并取中间值的过程，就会得到一个具有统计意义属性的随机数序列了。这也就是广为人知的平方取中法。

然而，冯诺依曼的方法并没有经得住时间的考验，因为不论从什么随机种子开始，序列最终都会落入某个短循环序列，比如：8100,6100,4100，8100，6100,4100……。序列中的数字是依赖于前一个数字的这种生成函数，上面的重复循环问题是不可避免的。但是如果说这个循环间隔非常非常大，对实际应用并不会产生影响，那会怎样呢？

1949 年，数学家 D.H.Lehmer 利用线性同余生成器（LCG）实现了这一思路。这种随机生成器发明之初非常流行。一个开发者 Paul Houle 说道：“它在很多情况下已经很好用了，但是不能使用它来做保密使用”。

目前看到的大部分库的默认实现都是线性同余。至于线性同余的弱点也是很明显的，既然是同余那么就在一个周期后，你产生的随机数又会重复出现了。这有什么影响吗？

如果仅仅是做个测试好玩，没啥影响，但如果你是根据数字生产卡号、密码，那么影响就大了。当年一些电话卡被破解就是这样来的。这个就涉及伪随机的算法循环长度。什么叫循环长度？就是如果第一次产生数字 55，第二个产生数字 107，那么循环多少次后，会继续产生，55，107……这样的序列。目前大部分简单算法的循环长度都是 2^32 左右。

那么有没有更好的算法。更好的循环长度让人无法破解呢？当然有，就是上面算法中的其他。数学界毕竟人才济济。推荐一个数学家提出的 MT 随机数算法，全称是 Mersenne Twister 梅森旋转算法。

这个算法是日本科学家 Makoto Matsumoto（松本真）和 Takuji Nishimura（西村拓士）在 1997 年开发的，而且还是目前可以看到最好随机数算法。该算法基于有限二进制字段上的矩阵线性递归 field F_{2}，可以快速产生高质量的伪随机数，修正了古典随机数发生算法的很多缺陷。MT 算法的循环长度能到多少？一个常用的实现是产生 32 位数字，循环长度 2^19937。一般来说只要你不搞天文运算。都可以轻松应对了。更主要的是，该算法的实现性能还非常高。MT 算法的普通实现不比我们常用的函数库的 rand 慢多少，大约只慢 10%，如果针对特定的处理器进行优化，还有非常大的进步空间。

大部分程序和语言中的随机数，确实都只是伪随机。是由可确定的函数，通过一个种子（常用时钟）产生的。这意味着：如果知道了种子，或者已经产生的随机数，都可能获得接下来随机数序列的信息（可预测性）。

不正确地使用伪随机数生成器会导致惊人的安全性问题。众所周知，早前 Netscape Navigator 的大量安全漏洞直接就是来自于不适当的随机数生成器。另一个比较典型的例子是 Reliable Software Technology 的因特网赌博揭秘事件，这个揭秘允许欺骗性的玩家可以实时计算每人手中确切的牌。它的缺陷存在于用来生成每副牌的洗牌算法中。在这段代码中，调用 randomize()在每副牌生成前生成一副随机牌。随机数生成器的种子是按照系统时钟，用午夜后的毫秒数选取的。这意味着随机数生成器的输出是容易预测的。

正如所讨论的，随机数生成器的可预测性是一个很严重的安全性问题。由此产生了密码安全伪随机数生成器（Cryptographically Secure Pseudo-Random Number Generator，简称 CSPRNG）。顾名思义，该随机数发生器可以产生在密码学意义上安全的随机数。不言而喻，CSPRNG 是一个强需求。梅森旋转随机数生成器并不是一种 CSPRNG，因为如果可以给定大量的先前序列样本，后面的数字是可以预测出来的。

硬件随机数生成器 HRNG(Hardware Random Number Generator )

通过对伪随机数生成器的分析，我们知道伪随机数通常会产生很严重的安全后果。原因是确定性的机器很难实现随机。真随机数生成器必须是非确定的，作为旁观者即使知道设备使用的算法也永远无法以任何一致性猜测到设备的输出。例如，如果设备输出一系列 0 和 1，0 和 1 在任何特定输出中出现的机会应该相等。即使掌握了设备内部工作的全部知识，任何猜中的可能性也只有 50% 左右。

构建真随机数生成器的最佳办法就是使用好的物理度量来生成随机数。许多自然现象就具备这种条件。其诀窍就是它们必须有一些可测量的特性，而且行为至少要尽可能随机。

某硬件随机数生成器生成的随机数据

一个典型的例子是 Unix 内核中的随机数发生器（/dev/random），理论上它能产生真随机。即这个随机数的生成，独立于生成函数，这时我们说这个随机数发生器是非确定的。具体来讲，Unix 维护了一个熵池，不断收集非确定性的设备事件，即机器运行环境中产生的硬件噪音，来作为种子。比如说，时钟，IO 请求的响应时间，特定硬件中断的时间间隔，键盘敲击速度，鼠标位置变化，甚至周围的电磁波等等。直观地讲，你每按一次键盘，动一下鼠标，邻居家 wifi 信号强度变化，磁盘写入速度等等信号，都可能被用来生成随机数。Windows 中也有相对的随机数生成器，基本的思想是一致的。如果要求更高的话，也有专用的设备，可收集附近的电磁场等环境噪音来产生随机数。20 世纪 90 年代中期的 CPU 是没有内置随机数生成指令的，这使得那时候好的随机种子特别难得。

到了 1997 年，计算机科学家们厌倦了生成随机数所受限的条件，来自 SGI 的一个团队发明了 LavaRand，它是用一个网络摄像头来对着熔岩灯拍照。从摄像头中过来的图片数据是一个真实的熵源，可以以 165kb/s 的速率生成随机数。测量放射性衰变也是随机数的一个比较好的来源。它根本不易产生偏差，只会带来相对较小的自然偏差。每当电子 Geiger 计数器检测到放射性衰变时，它就会生成一个脉冲。衰变之间的时间是一个实足的、纯粹的随机部分。尤其是，没有人可以预测到下一次衰变的时间大于还是小于自上次衰变以来的时间，那就产生了一位随机信息。

在 1999 年， Intel 在其 i810 芯片组上集成了芯片级的随机数生成器。这样使得新的服务器都自带热噪声的本地源随机数生成能力。

我们知道温度高于绝对零度的原子都存在热运动，在集成电路里这些原子的热运动会在电路里产生噪声，噪声会使得电路中的电压存在微小的起伏，Intel 的 TRNG 就是通过放大这些微小的起伏来产生随机数。2012 年，Intel 为 TRNG 增加了 RDRAND 和 RDSEED 指令，具有 500MB/s 的生产效率。但是 RDRAND 的完整性一直被质疑，里面是不是有某些缺陷？或者是为美国国家安全局内置了什么东西？没人确切地知道这个问题的答案。

硬件随机数生成器也有不少缺点。首先就是产生随机数的速度很低，其次是电路系统里有很多不同的噪声，但并不是所有噪声都是随机的，比如电源噪声中很大一部分就是和系统时钟强相关的。而硬件随机数生成器是一个放大极小信号的电路，它对外界干扰是极其敏感的，为了避免外界非随机信号的干扰必须要耗费不少功率和面积在屏蔽上。所以加密软件依旧不得不依赖于伪随机数生成器（PRNG）。

量子随机数生成器

事实上，任何基于经典物理过程所产生的随机数本质上都不是真随机的， 包括抛硬币、上面讲到的硬件随机数生成器。经典系统中的随机性都是“表面随机性”，即事件表面上看似具有随机性，而本质上并不是随机的，只是确定性事件的概率组合。它之所以表现出随机性，是因为观察者对系统整体运作机制的不完全了解。由表面随机性所产生的随机数并不是真正随机的。

现代物理学的发展让人们把目光转向量子领域。“量子”是一个不可分割的基本个体，是构成现实事物的微小能量和物质，如光子、原子、电子都是“量子”的组成微粒。量子力学是研究微观世界力学规律的理论，其正确性已经逐步得到证实。研究表明，微观粒子的状态具有“内禀随机性”。也就是说，其随机性不是因为缺乏对系统的了解而造成的，而是微观粒子固有的特性。利用这种内禀随机性，可以产生真正的随机数，即“真随机数”(或称为“内禀随机数”)。

根据经典力学制造的硬件随机数生成器设备要确保实现公平的不可预测性很困难。假设一个随机数生成器的供应商在制造设备时可能采取了某些策略按自己的利益影响着它的输出结果，甚至是事先预设一些(看起来随机的)比特串存储在设备中，使得输出的序列对于供应商来说是部分已知的甚至是完全已知的，即输出结果对供应商来说不满足不可预测性。

因此，密码系统中必须要保证所产生的随机数与其它外部变量完全无关，即包括设备供应商在内的其他任何人都不能获知该随机数的任何信息。这一点在经典世界中是难以实现甚至无法想象的。量子密码的发展有可能实现设备无关量子随机数扩展方法，可以保证所产生的随机数与外部变量无关。

区块链与随机数

随机数对于区块链技术来说很关键。本质上，分布式账本的核心问题就是随机选择出块人的问题，这个随机性要能被全网确认，并且不能被操控，也不能被预测，否则恶意节点通过操控这个随机数就可以操控长链，从而实现双花攻击。

PoW 的方案是让大家进行算力竞赛，设置一个计算哈希的难题，谁先算出来谁赢，算力高的赢的概率高，算力低的赢的概率低，以这样的方式保证胜出者是随机的。投入的算力能够体现在哈希值上，这样全网能够验证，并选择包含最多算力的那条链。恶意节点只能通过提升自己的算力来增加攻击成功的概率。

PoS 的方案是选举，大家不用浪费电力去进行算力竞赛，而是文明一点，随机选举一个节点来出块，并且被选中的概率和它拥有的份额相关。如果“随机”这一步没有问题的话，恶意节点只能通过增加自己的份额，增加自己被选中的概率，从而增加双花攻击的成功概率。这里有一点比 PoW 的方案要好就是，要实现攻击，先得成为持币大户，如果攻击成功币价大跌，攻击者也会承受最大的损失。而 PoW 方案中虽然算力要花钱，但是如果攻击者没有持币，那么他的利益和币价不一定是正相关的，不能排除仍然存在攻击的动力。

那么接下来的核心问题就是，这个不能被操控不能被预测的随机数从哪来。

传统地 PoS 方案尝试从链上现有的数据入手，比如使用上一个区块的哈希值，上一个区块的时间戳等等来作为随机数的来源，但这些会带来额外的安全风险。因为区块本身的信息就是节点写进去的，然后又要根据里面的信息来选举后续的出块者，存在循环论证的嫌疑，安全性不会太好。这也是传统地认为 PoS 方案不如 PoW 可靠的部分原因。

从信息论的角度谈区块链中的随机问题

熵（Entropy）在物理学中用于度量一个热力学系统的无序或混乱程度（参考热力学第二定律），当它被引入到信息论（计算机科学）时，则被用来衡量信息的不确定性（不可预测性），简单的说也就是“随机性”。

假设有一枚“理想”的硬币（抛出正面和反面的几率相等），每一次抛硬币都是独立的、不可预测的，其结果不是正面、就是反面（0 和 1），那么这个抛硬币事件的熵就是 1 个比特/位，抛 256 次的熵就是 256 个比特/位。

暂时抛开那些复杂的定义、公式，“熵”其实就是那么简单，从科普的角度，我们只需要了解一个对于密码学来说的重要定律：任何算法（包括那些符合密码学规范的伪随机数算法）只能是“维持”熵、甚至有可能会“降低”熵，但一定不能“增加”熵！记住这一点至关重要，历史上发生过的无数次随机数问题基本上都源于对这一点的忽视，我们暂且命名为“算法不增熵”定理。

以曾经发生的http://blockchain.info的随机数问题为例，http://blockchain.info使用的 RC4 算法（http://en.wikipedia.org/wiki/RC4，因版权问题通常也被称为 ARC4）是一个广泛使用的密码学算法，通常被用来生成伪随机数的信息流。ARC4 算法有一个非常“好”的特性，即：只需要一个种子（哪怕这个种子只有两位，0 和 1），就能生成“无限多”的随机数，你只需要反复的对结果进行 ARC4 运算即可。比如说，使用 0 或者 1 初始化 ARC4 数组，然后反复的进行 ARC4 运算，您都可以得到任意长度的数列，数列中的每一个元素都是 0-255（8 位）的数字，出于篇幅限制，我们在这里只运行了 256 次的 ARC4next 方法。

0:

[222,24,137,65,163,55,93,58,138,6,30,103,87,110,146,109,199,26,127,163,240,204,235,151,69,43,77,50,39,150,95,158,168,204,117,7,109,159,185,197,65,122,165,203,48,252,34,25,139,52,152,45,187,98,158,192,75,79,139,5,160,113,8,80,146,160,195,88,74,72,228,163,10,57,123,138,205,29,0,158,200,125,104,17,242,44,244,156,163,229,147,84,185,69,21,53,162,24,122,134,66,108,202,125,94,130,62,186,0,68,18,103,18,87,184,216,96,174,76,189,76,73,6,187,197,53,239,225,88,127,8,219,51,149,92,219,203,173,155,16,245,63,196,229,44,89,21,101,81,132,135,254,8,77,14,63,3,222,188,201,218,28,233,13,8,92,45,138,25,216,55,48,134,22,54,146,20,43,216,252,93,122,115,73,106,142,89,238,126,207,107,148,6,99,244,166,190,230,91,210,200,92,70,152,108,27,239,52,144,211,123,56,218,133,211,46,151,57,203,35,74,43,231,64,235,8,137,54,33,153,175,204,50,131,85,153,13,79,137,251,99,195,228,81,116,172,100,77,71,2,71,63,151,209,157,98]

1:[6,8,14,14,24,32,41,41,57,51,73,87,102,118,135,131,161,181,202,224,247,102,17,124,76,104,133,163,194,226,163,73,108,38,57,127,166,206,23,65,224,71,165,211,186,87,52,103,128,180,137,239,127,183,151,209,60,44,48,147,210,142,207,149,216,104,173,167,238,239,94,230,67,143,76,236,63,143,154,197,12,17,10,119,104,46,106,197,42,3,171,116,97,215,94,138,225,97,198,118,100,125,26,61,58,230,88,198,0,112,124,71,207,55,97,128,47,75,153,130,158,95,117,7,105,226,176,130,239,90,49,125,20,247,71,95,234,13,154,98,178,210,63,236,243,36,147,202,101,88,53,9,222,9,250,163,15,184,130,181,167,249,231,37,187,125,231,174,239,43,92,255,255,154,201,48,177,206,22,183,105,92,9,8,94,51,211,200,121,189,64,9,97,248,174,13,201,173,209,196,15,129,227,3,127,184,41,69,165,199,122,90,33,63,21,160,164,205,37,93,222,211,137,199,18,135,107,7,83,10,230,113,108,41,195,34,181,63,68,164,52,214,97,63,178,22,55,192,80,153,210,224,91,240,104,165]

这个数列中的任意一段（32 个元素即 256 位），都可以被用来作为比特币私钥或签名时使用的 k 值，他们看起来都很“随机”。可惜，无论我们进行了怎样的运算，这个数列的熵都永远小于等于 1 个比特（即 0 和 1）。也就是说，其它人，如果能覆盖全部的熵，进行相同的运算，也能够计算出您的全部私钥和全部 k 值。

http://blockchain.info出问题时的熵是 8 个比特（0-255），也就是说，您只需要使用这 256 个数字作为种子，反复的进行 ARC4 运算，就能覆盖出问题的时间段里http://blockchain.info用户所使用的全部随机数（考虑到浏览器缓存和 CDN 缓存，问题时间段的长度可能是数周）。当然，您还可以基于代码进行一些优化，只考虑部分可能出现的情况，比如说每进行 33 次 ARC4next 生成一个随机数，或者是间隔 256 次 ARCnext 后再用 33 次 ARCnext 来生成一个随机数。

例如，上述种子 0 所对应的数组中，我们可以进行如下简单的计算：

取开头的 33 个元素：[222,24,137,65,163,55,93,58,138,6,30,103,87,110,146,109,199,26,127,163,240,204,235,151,69,43,77,50,39,150,95,158,168]；

按照http://blockchain.info的算法（他们自己定义的 BigInteger 类型），将第一个元素替换为 0，最后一个元素加 1，即得到结果数组：[0,24,137,65,163,55,93,58,138,6,30,103,87,110,146,109,199,26,127,163,240,204,235,151,69,43,77,50,39,150,95,158,169]；

使用这个结果数组可以得到一个 k 值 188941a3375d3a8a061e67576e926dc71a7fa3f0cceb97452b4d3227965f9ea9；

再使用 ECDSA 算法计算出该 k 值所对应的 r 值：0dcc0b9a668d4b7b8cbde71288bf32bb659bd7fda1b66172ce97fda6f8b0a06e；

这个 r 值在整个区块链的交易签名中一共出现过 5 次，这 5 笔交易所对应的私钥均已暴漏；

比如说，地址：19hXXVpwhmu1frqKwF1VZdNfqtGrMvg87n，交易 hash：b2b63f29c379ff830f45a5165b0e374093207ddca3e737562617c1d526ef4c65，该笔交易签名就是这个 r 值，利用区块链上的数据，任何人都能够很容易的计算出该地址的私钥：5JHyRh8hwyjWjt3RR3B9X6oJt9mzJZwFe8YnF7W22XcSHdD6rxK；

搞定。看到这里，我们可以知道，根据前面的“算法不增熵”定理，对于比特币所需要的随机数来说，仅仅使用密码学安全的伪随机数算法还是不够的，您需要的是“足够”的熵（比特币需要的是 256 个比特/位），无论您使用的是哪种算法，永远要保证熵的品质，永远都不要降低熵。

比特币本身是安全的，不安全的是错误的解决方案和有问题的熵。