前一阵子我去参加了 OpenResty Con 2017, 来自 KONG 的 Thibault Charbonnier 分享了他们在 OpenResty 上关于随机数应用的一些 Tips. 这才知道 LuaJIT 使用的随机算法和原生 Lua 的算法是不同的。我在自己的项目中也常常有使用随机数，但基本上只是直接使用，没有探寻背后的一些原理。刚好利用这个机会来好好补充下这方面的知识。
引言
许多应用中都需要用到随机数，如物理仿真、统计采样、密码学、博彩等。随机数一般可以通过两种方法得到。一种是基于物理现象由硬件产生。由此得到的随机数，在产生之前是不可预知的，因此，是真正的随机数。比如在
「真随机」也有不同的含义，若想要「真正的真随机」目测只能靠量子力学了。一般的所谓真随机不是指这个，而是指统计意义上的随机，也就是具备不确定性，可以被安全的用于金融等领域，下面说的也是这种。另外，计算机系统可以产生统计意义上的真随机数。
一个典型的例子就是 UNIX 内核中的随机数发生器（/dev/random），它在理论上能产生真随机。即这个随机数的生成，独立于生成函数，这时我们说这个产生器是非确定的。具体来讲，UNIX 维护了一个熵池，不断收集非确定性的设备事件，即机器运行环境中产生的硬件噪音来作为种子。比如说：时钟，IO 请求的响应时间，特定硬件中断的时间间隔，键盘敲击速度，鼠标位置变化，甚至周围的电磁波等等……直观地说，你每按一次键盘，动一下鼠标，邻居家 wifi 信号强度变化，磁盘写入速度，等等信号，都可能被用来生成随机数。
伪随机数要比真正的随机数更容易获取，而且在大多数情况下都能满足应用的要求。我们这里只讨论伪随机数的生成算法，即随机数生成器（Random Number Generator, RNG）。以下除特别指出外，我们提到的随机数都是指伪随机数。
下面的这段引用自维基百科：
随机数生成器（Random number generator）是通过一些算法、物理讯号、环境噪音等来产生看起来似乎没有关联性的数列的方法或装置。丢硬币、丢骰子、洗牌就是生活上常见的随机数产生方式。
大部分计算机上的伪随机数，并不是真正的随机数，只是重复的周期比较大的数列，是按一定的算法和种子值生成的。
大部分程序和语言中的随机数（比如 C 中的），确实都只是伪随机。是由可确定的函数（常用线性同余），通过一个种子（常用时钟），产生的伪随机数。这意味着：如果知道了种子，或者已经产生的随机数，都可能获得接下来随机数序列的信息（可预测性）。这也是北京车牌摇号背后的原理(只摇出六位种子)，即：用相同的种子开始一个伪随机数生成器，必将得到相同的随机数序列。
经常地，随机数在统计上需要满足特定的分布，如均匀分布、正态分布、指数分布等等。一个好的随机数生成器应该都够高效地生成满足待定分布的随机数序列。而产生的随机数序列有多「随机」又在多大程度上符合特定分布，则需要严格的理论证明和统计分析。但这里，首先要记住一点，随机序列的周期越长越好，虽然周期并不是评价随机数算法的唯一重要标准。
当然，设计一个好的随机数生成算法非常困难，最好由专家完成。
背景
Dual_EC_DRBG，全称为Dual Elliptic Curve Deterministic Random Bit Generation，是基于椭圆曲线的确定性随机数生成器。2007，两名微软的研究人员 Dan Shumow 和 Niels Ferguson 就发现，Dual_EC_DRBG 算法可以被植入后门。他们提到，如果算法中使用的常数经过特殊选择，并且用来选择这些常数所使用的数据被算法设计者保存下来，那么该算法设计者在知道该算法生成随机序列的前32个字节的情况下，可以预知未来所有生成的“随机”序列。目前最新的进展是，斯诺登披露的文件证明了，美国国家安全局（NSA）通过贿赂RSA公司，使其在BSafe安全软件中采用Dual_EC_DRBG算法。而Dual_EC_DRBG则是NSA精心设计的留有后门的算法（当然NSA可能没有告诉RSA公司这一点）。
由此，我们可以看出评价随机数的两个标准：
-
随机性
-
分布均匀性
分布均匀性指的是 0 和 1 出现的概率大致相等
-
独立性
独立性指的是序列中任何子序列不能由其他子序列推导出
遗憾的是，没有可靠的方法表明一个序列的独立性好，只能证明一个序列不具有独立性。因此只好多测测，来回多次仍然表现不错的话，就姑且当它独立性不错。
-
-
不可预测性
不可预测性是指每个数都统计独立于其他数，因而不可预测。但是真正的随机数序列很少用，一般看上去随机的随机数序列都是由算法产生的。因此需要注意不能让攻击者从先前的随机数推导出后面的随机数。
接下来我将介绍符合均匀分布的随机数生成的相关算法。（由于相关算法非常多，因此，这里先介绍常用的若干种，有机会再逐渐补充。）
PRNG
考虑到计算需要、内存需要、安全需要以及随机数质量的不同要求，人们设计了许多不同的随机数生成算法。没有一个是所谓“通用安全”的算法，就像没有一个排序算法在所有情况下表现都最优一样。许多人默认使用 C/C++ 的rand 函数（LCG/TLCG 算法）或者马特赛纳旋转(Mersenne Twister)，稍后都有详细介绍。
常见的 PRNG 算法分为加密和不加密两类。不加密算法一般比加密算法更快，但是不能在需要安全的情况下使用。下面将分开进行介绍。
不加密
-
线性同余法(Linear Congruential Generator, LCG)
最为常见的一种随机数生成算法，许多语言的标准库中的随机函数都是采用这种方法实现的。
LCG 非常容易实现，生成速度快，只需要很小的内存来维护状态（通常仅需要4个或8个字节）。因而对于一般性的应用，LCG 是首选。但 LCG 随机数的周期短（32位的随机数，周期最多仅为2^32^），随性机一般。
-
截断性线性同余法(TLCG)
TLCG 算法在微软系产品中被广泛使用（可能是微软产品使用自身 VC++ 编译器的缘故）
-
线性反馈移位寄存器法(LFSR)
同 LCG 相比，LFSR 法也只需要占用很少的内存，但却能产生质量更高的随机数。
-
马特塞特旋转法(Mersenne Twister, MT)
Python、Ruby、R、PHP(mt_rand)、MATLAB 中随机函数的默认算法都是 MT。
优点是循环长度达到 2^19937^。19937的周期应该能运算到远比整个宇宙的生命还要更长的时间。缺点是启动慢，占用内存较大。
加密
-
ISAAC、ISAAC+
该算法是基于 RC4 密码变体的 CSPRNG。ISAAC 没有小于240的周期，预期的周期为28295。
-
/dev/random
虽然不是一个特定的算法，但是 Linux 和很多 Unix 的衍生品都在 /dev/random 命令下实现了一个随机源，它返回一个基于系统熵的随机数，因此可以被视为真随机数生成器。但是 /dev/random 是阻塞的，意味着在搜集到足够的熵之前是不会返回的。因此很多程序都使用不阻塞的 /dev/unrandom。但是这样得到的随机数就不是那么安全，并且 /dev/unrandom 会耗尽系统熵，稍差的实现很容易被攻击。该实现没有特定的算法，有些实现使用了 Yarrow。
-
CryptGenRandom
微软的 CryptoAPI 函数库中的 CryptGenRandom 可以生成密码安全的随机字节来填充一个 buffer。和 /dev/random 类似，它也可以被视作真随机数生成器。虽然没有开放源文件，但是它通过了 FIPS 认证，所以被认为是安全的。在 Windows 上，这是个不错的 CSPRNG
-
Yarrow
一种免费的开源 PRNG，Mac OS 和 Free BSD 都用该算法来实现了 /dev/random。原作者已经不再对它进行支持，开发了一个改进的 Fortuna 算法。
结语
对于一般性的任务，一个设计良好的 LCG 算法可能已经足够“随机”了，并且 LCG 非常高效，不会占用太多的内存空间。对于随机性要求高的应用，MT 一般是首要考虑的方法，但需要占用相对较多的内存空间可能是它的一个不足(大多数情况下，这似乎根本不是个问题 :-)。其他的算法或者更适合于特定的应用，或者更便于在特定的硬件上实现。总之，当我们在使用随机数的时候，我们最好知道自己在做什么。
最后是一个的笑话：某个游戏的 getRandomNumber 函数的实现：
参考资料
- Pseudorandom number generators
- 随机数常见算法优劣剖析
- 伪随机数的产生
- 随机数生成（一）：均匀分布
- 攻破随机数产生器(一)
- 攻破随机数产生器(二)
- 电脑取随机数是什么原理，是真正的随机数吗？
