张剑强
平台开发处
徐林亮
平台开发处
随机数在计算机科学，尤其是信息安全领域有着广泛应用。生成密钥、创建盐值(salt)、构造token等操作都离不开随机数。生成随机数很容易，很多“从娃娃抓起”学习计算机的小学生，也会使用rand()函数，但在安全领域使用随机数，并不简单。
C语言提供的rand()函数是使用最广泛的随机数产生器(RNG，Random Number Generator)，很多编程语言调用它作为自己的随机函数实现。rand() 使用迭代算法计算随机数，它利用一个“随机种子”作为RNG的内部变量设置初值，在每次被调用的时候，输出一个随机数，同时更新内部变量的值，为下一次调用做好准备。这样生成的随机数并不适合安全用途——对于给定的种子，生成的随机数是一个固定序列，只能称之为伪随机。
使用高分辨率时间值、键盘击键间隔等外部熵源设置随机种子，可以在一定程度上改善rand()的随机性，但依然非常不够——攻击者收集足够多的历史输出序列，就可以预测rand()的下一个输出值。以广泛使用的GNU C 库中的rand为例，其每次输出的数值有如下规律：
从上述公式中显然可见，利用历史序列预测下一个输出值，是比较简单的，这样的随机数无法用于安全场景。
# 那什么样的随机数可以用于安全场合？
随机数发生器可以抽象成持续输出01序列的随机比特生成器(Random Bit Generator)，就像可以不停丢出正反面的硬币。一枚总偏好正面的硬币显然不是合适的硬币，一个好的RBG，其输出的序列必须有良好的统计特性，安全领域使用的随机数尤其如此。
我国密码管理局《GM/T 0005 随机性检测规范》和美国标准研究院(NIST)《SP800-22r1a, A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications》是对随机数进行检测的相关标准。二者均从统计角度出发，提出15个检测项，对RBG生成的01序列进行进行测试，分析其中0、1的分布比例、游程长度(连续的0或1的序列长度)等特征是否偏离正常值，甚至利用傅里叶变换等手段，试图探测随机序列中的“规律”，而任何可见的规律的存在，也意味着“随机性”的不足。
伴随SP800-22r1a 标准，NIST甚至发布了测试程序，github上也有相关的项目，可以对生成好的bit流进行随机性统计测试。
# 如何产生适用的随机数？
我们所熟悉的、抽象概念上的“计算机”，作为确定有限状态自动机，是没有能力输出真正的随机数的——对于确定的初始状态和输入序列，它总是给出确定的输出序列。
在这样的“计算机”中利用逻辑算法生成的“随机数”，其实是一个看似随机的固定序列，只能称为伪随机数。这样的随机数发生能器也称为伪随机数发生器PRNG(Pseudo Random Number Generator)。
回到真实的物理世界，“随机”无处不在——模拟电视机在没有信号的时候，满屏黑白雪花、喇叭刺啦作响——噪声中就充斥着随机性。利用物理现象可以产生真正的随机数：对电路噪声进行采样、对外部事件进行高精度计时、对未初始化的内存空间进行取样，近年来，还出现了利用量子效应的随机数发生器产品。这些能产生真正的随机数的器件，称为真随机数发生器TRNG(True Random Number Generator)。
密码学领域所用的随机数，既要求不可预测，也要求良好的统计品质，还要求很高的生产速率。PRNG作为可预测序列显然难以满足要求，而TRNG的生产速度受物理设备限制，其统计品质也无从保障——比起物理现象和物理器件，密码学家们还是更信任老朋友——已经验证的哈希函数和密码算法。经典安全hash函数和对称算法的输出值有良好的统计特性(这正是它们的设计目标之一)。利用这些算法构造自动机，可以输出具有良好统计特征的伪随机数序列，而使用合适的熵源为这些自动机设置种子，就能产生满足安全用途的随机数序列，这样的随机数生成器称为密码学安全随机数发生器(CSPRNG，Cryptographically Secure Pseudo Random Number Generator)。
NIST标准SP800-90A 和 NIST SP800-90B 分别给出了构造CSPRNG的推荐方案和对熵源的要求，对自行构建CSPRNG有一定帮助。
# 程序员：“我太难了”——需要这么难吗？
对于绝大多数程序员而言，并不需要自行设计实现CSPRNG，底层资源已经提供了良好的支持。
Intel CPU 在 Ivy Bridge(2012年)架构中，已经用硬件实现了CSPRNG，并在指令集中增加了RDRAND指令，用于获取随机数；此后还增加了RDSEED指令，供用户在实现“软”CSPRNG时，获取随机种子。这两个指令都能产生满足NIST标准的随机数和随机种子，AMD也在2015年之后，支持了这两条指令。
Linux操作系统提供了两个随机数发生器： /dev/random 和 /dev/urandom。这两个随机数发生器基于同一个CSPRNG，前者在收集够一定的熵(外部随机性)后，才从CSPRNG提取数，而后者不受此限。一般性地说，前者有更好的不可预测性，但对熵源的依赖性较高、读取时有可能会因没有可用的熵而阻塞；后者不会阻塞，但随机性略差。Linux系统还提供了硬件随机数发生器的访问接口 /dev/hwrng。在Kernel 3.16以后，硬件随机数发生器的数据被引入到了随机数产生过程中，而2020年发布的5.6之后，/dev/random 也不再阻塞、 random和urandom基本可以认为是等效的。虽然有过争议，但现在基本可以认为，/dev/urandom 是能够用于安全应用的。
高级编程语言可用的资源就更丰富了，PHP 7.0.0引入了CSPRNG，Java语言可以用SecureRandom。C语言？C语言您可以读取/dev/urandom，也可以内联汇编用RDRAND指令自己编一个去吧。
小小随机数，随机不随意。
参考资料：
＋
GNU C GLIBC 随机数算法分析：
https://www.mscs.dal.ca/~selinger/random/
＋
NIST SP800-22r1a 密码学安全随机数发生器检测
https://github.com/dj-on-github/sp800_22_tests
＋
NIST SP800-90A 随机数发生器推荐方案
https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-90Ar1.pdf
＋
NIST SP800-90B 随机数发生器熵源推荐
https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-90B.pdf
＋
RDRAND与RDSEED
https://software.intel.com/content/www/cn/zh/develop/blogs/the-difference-between-rdrand-and-rdseed.html?wapkw=rdrand