随机数常见算法优劣剖析

这是一篇介绍随机数的文章。本文的主要目的在于展示一个起点，帮助开发和测试人员了解随机数及其原理，并介绍了几种常见随机数算法以及其各自的优劣。

1、随机数的概念

随机数是许多计算机应用中必不可少的要素。对于游戏软件，开发者经常利用随机数来模拟自然环境中的许多不确定性行为。但是在大多数计算领域中所使用到的随机数并不是真正“随机”的，而是由为伪随机生成器(PRNG)生成的。为随机数生成器都是通过确定的算法，并且不需要使用外接熵（如不确定的用户输入、时间、热噪声）来生成随机数的算法。

随机性在游戏中的应用：  

●AI算法（遗传算法、自动化模拟玩家）

●随机游戏内容、关卡场景

●模拟复杂现象 如天气、火焰等

●数学方法 如蒙特卡罗积分

●加解密算法。如RSA算法就使用随机数来生成p与q

●气候模拟、统计物理测试

●最优化算法

在计算复杂度理论里，有一个"BPP"的概念，它描述了一种问题的集合，即"Bounded-error"，"Probabilistic"，"Polynomial time"。就是指在多项式时间内以概率图灵机（非决定性图灵机）解出的问题的集合, 并且对所有的输入，输出结果有错误的概率为0到1/2的范围内的一个任意值（但不包含0与1/2）。举例来说，如果一个问题属于BPP所描述的问题集合，则必然存在一个算法，此算法允许转硬币作随机的决定，并在多项式时间内结束。 对这个算法的任何输入，他都要在(0,1/2)的错误概率内给出正确判断，不论这一个问题的答案是"正确"或者"错误"）。

另一个概念"P" ，是指在复杂度类问题中决定性图灵机在多项式时间内求解的决定性问题的集合。

一个问题如果属于"P"，并且假设存在某种条件达成BPP=P时，我们说这个问题是一个开放式问题。对于开放式问题，含有随机性选择要素的算法，比任何已有的、不含有随机选择要素的算法表现得更好。如果允许随机性的存在，去寻找一个解决特定问题的算法就要容易得多。

然而，设计一个好的随机数生成算法非常困难，最好由专家完成。（曾经有一篇经典的文章就叫做“随机数生成对我们太重要了，我们不能让它随机生成”）就像密码学一样，随机数生成的历史充满着各种失败的算法以及其所带来的恶劣后果。

2、生成随机数

一个算法是无法生成“真正”随机数的，所以人们设计了很多硬件随机数生成器。大部分以一些量子力学上无法被预测的事件作为随机性来源，如原子衰减、电路中的量子力学噪音（或称为散粒噪音）、穿过一个部分反射面的光子流、由高能X射线产生的粒子旋转等。然后通过分析来决定这个来源中有多少熵，以及能从中抽取多少个高质量的随机位。

而在纯软件实现上，PRNG都是通过一个内部状态来进行运算，生成一个“看似随机”的数列。这个初始的状态被称为种子。为一个特定的算法选一个好的种子是非常困难的，通常算法会使用自身返回的随机值作为内部状态。因为这个内部状态是有限的（即使周期很长），PRNG会在一些状态下重复。一个随机数生成器的周期就是在它开始重复之前所能返回的随机数个数。一个使用n位内部状态值的伪随机数算法最多只有的周期。用相同的种子开始一个伪随机数生成器，必将得到相同的随机数序列。所以当PRNG需要一个种子的时候，通常会传递一个来自系统或者外部硬件的熵来源。

考虑到计算需要、内存需要、安全需要以及随机数质量的不同要求，人们设计了许多不同的随机数生成算法。没有一个是所谓“通用安全”的算法，就像没有一个排序算法在所有情况下表现都最优一样。许多人默认使用C/C++的rand函数（LCG/TLCG算法）或者马特赛纳旋转(Mersenne Twister)，稍后都有详细介绍。

大多数的PRNG都返回一个[0,m]之间均匀选择的整数。C/C++的rand中m定义为RAND_MAX，通常是15位整数32767。srand(seed)函数用来设置初始种子，通常使用当前的时间作为熵来源，如srand(time(NULL))。大多数C/C++的rand实现都是LCG/TLCG算法。线性同余生成器在加密方面是相当糟糕的选择，它们生成质量很低的随机数序列，表现出多种偏向性。

在游戏中经常使用的是均匀分布。均匀分布需要从[a,b]中等同随机地挑选出一个整数。一个典型的常见错误用法是：(rand()%(b-a+1))+a。这错误的用法导致不是所有的值都以等同概率出现！只有当(b-a+1)可以整除RAND_MAX+1时，上面的用法才没有问题。举例来说，假设RAND_MAX是32767，试生成一个[0,32767]之间的随机数，使用上面的代码会导致0出现的概率是其他值的2倍！

以下摘自网络文章的内容展示了一些典型的病态使用范例：

一个可行（但是更慢）的解决方法是将随机输出缩放至[0,1]区间，再放大到[a,b]区间,如：

double v = (static_cast<double>(rand() ) ) //RAND_MAX

return static_cast<long>( v *(b -a+1)+a);

其次比较常用的分布是高斯分布。高斯分布可由一个均匀分布生成。首先用randf()返回[0,1]之间均匀分布的随机数，再调用Box-Muller变换。它的极坐标形式将每次产生两个高斯值，y1与y2。如：

float x1,x2,w,y1,y2;

do{

       x1 = 2.0 * randf() -1.0;

       x2 = 2.0 * randf() -1.0;

       w = x1 * x1 + x2 * x2;

}while(w >= 1.0)

w = sqrt( (-2.0 * log( w ) ) /w);

y1 =  x1 * w;

y2 =  x2 * w;

Boost库的文档从均匀分布开始介绍了生成其他分布的技术。

在生成出随机序列之后，通常要对其进行检验。而要检验是否随机，必须首先定义什么是随机，但是随机性又是很难精确定义的。在实践中，许多测试被设计来评测随机数生成器的质量，通用方法是检测有没有不像随机数列的一连串表现。

其中最著名的随机性测试测试集是DIEHARD集，它由12个测试组成。后来被扩展为开源的测试几DIEHARDER，除了DIEHARD外，还包括了许多随机数生成器以及一套框架，使添加新的生成器非常容易。第三套测试框架是TestU01。通过使用这些测试框架将保证通过测试的随机数生成器列不至于有明显的问题。

许多随机源的位（bit)上都会存在一些偏向性或者相关性。通常PRNG会使用一些漂白算法(whitening)来去除相关性。常见的有：John von Neumann算法、隔位翻转法、Blum Blum Shub算法、哈希加密算法 等。但是需注意的是，即便是经过漂白过的数据流，不经过进一步的处理仍然不能被视为安全的随机源。

3、PRNG算法实现

常见的PRNG算法分为加密和不加密两类。不加密算法一般比加密算法更快，但是不能在需要安全的情况下使用。下面将分开进行介绍。

(一）不加密随机数生成算法

1、平方取中法

这个算法比较古老了，是由约翰·冯·诺依曼在1946年提出的，取一个10位数作为种子，取平方，返回中间的10位作为下一个数和种子。这个算法在ENIAC（第一台计算机）中使用，是一个有缺陷的算法，已经不再使用。

2、线性同余法（LCG)

这是一个广泛使用的常见算法，但是逐渐被一些新算法所取代。它产生一个 = ( a * + b ) mod m 的数列，其中a,b是常数。模数m通常会使用2的乘方作为高效掩码。a与b要小心挑选来保证最大周期，并且避免其他一些问题。该算法有多种缺陷其中最典型的一个就是：3个一组作为空间中的点坐标，在空间中描绘这些点之后，将发现它们都在一些平面上。这个缺陷是由于连续点线性相关。使用2的乘方作为模数 的LCG表现最差。尤其是最低的几个有效位。举例来说，《C的数学库》中推荐使用a=1664525,b=1013904223,,这样产生的随机数最低几位几乎不变。

LCG的优点在于速度快，并且使用了一个相对较小的状态，因此使用广泛。包括在很多嵌入式程序中。如果模数不是2的乘方，取模运算通常非常耗时。

一些常见的LCG(m,a,b):                                            

3、截断性线性同余法（TLCG)

这个算法保存一个内部状态Si,Si使用LCG得到，然后依次生成输出Xi。公式为：，。这种算法允许使用一个快速模数m =2n，同时避免了LCG中低位缺陷。如果K也是2的乘方，除法操作也会很快。TLCG算法在微软系产品中被广泛使用（可能是微软产品使用自身VC++编译器的缘故），VC++中rand()也使用了TLCG。其实现如下：

static unsigned long seed;

seed = 214013L * seed + 2531011L;

return( seed>>16)&0x7fff;// return bits 16-30

这个算法其实是不安全的。实际上，对于一个加密分析工程，只需要得到该算法两个连续输出之后就可以破解它的内部状态（包括一个不需要的最高位），也就获得了之后它所有的输出。一个最简单的破解内部状态的方法是：注意该状态的最高位与之后的输出是没有关系的，所以只需要破解第31位。第一个输出会给该状态的15位，只有17位未知。再有两个输出，可以用已知的15位测试所有可能的个状态，就可以知道哪个状态产生哪两个输出。这样就已经可以得到内部状态了。两个输出是不够的，因为它们不能决定一个唯一的状态。

BC++和TurboC也都使用了TLCG，并设置a=22695477和b=1，虽然ASNI C并未强制要求实现一个rand函数，但是《C Programming Language》举出的一个例子就是使用TLCG，并设置a=113515245和b=12345,RAND_MAX最小为32767。

4、线性反馈移位寄存器法

LFSR通过将一个内部状态依次一位地移出来产生随机位。新的随机位将通过当前状态的线性函数获得并移入这个状态。LFSR流行是因为它速度很快，并且在硬件上容易实现，并且能产生大范围的数列。通过选择合理的流水序列可以使一个n位的LFSR拥有的周期。但是只需要个输出位就可以推导出LFSR的结构和反馈链接，所以LFSR并不安全。

5、逆同余法

这个算法类似LCG但是不是线性的。，其中是模m的乘法逆数，也就是因为求逆操作非常费时，所以该算法并不常用。

6、滞后斐波纳契法（LFG)

该算法使k个状态，但是很难良好运行，也很难初始化。周期取决于初始种子，而空间被分割成很难预测的循环。因为马特塞特旋转算法和新的PRNG出现，该算法已经被抛弃。(Boost库中收录了多种LFG，有兴趣可以自行研究)

7、线性递归生成器

这种算法是LFSR的一个泛化。现在大多数在二进制有限域的快速PRNG都是由它衍生而来（注意，这些算法都不能通过线性递归测试，因为它们都使用了线性函数）。

8、马特塞特旋转法

1997年，Makoto Matsumoto 和 Takuji Nishimura发表了马特塞特旋转算法。这种算法避免了之前PRNG的许多问题。当时两人展示了两个版本MT11213和MT19937，MT19937的周期应该能运算到远比整个宇宙的生命还要更长的时间。它使用624个长整数或者19968位作为内部状态，这大约符合超大周期的预期。更惊人的是，它比LCG更快！，在高达623个维度是等分布的。目前它已经成为主要的PRNG。

MT算法之所以这么快，是因为它每次产生随机数时，只更新内部状态的一小部分，通过多次调用来遍历这个状态。马特赛特旋转算法是一个旋转广义反馈移位寄存器。它不是密码学安全的：在观察624个连续输出后就可以破解出它的内部状态而预测之后的输出。该算法仍然存在一些缺陷，在下面的WELL算法会提到。

9、WELL算法

该算法于2006年推出。WELL算法所产生的随机数比MT19937拥有更好的等分布性，并且在“位混合”属性上做了改进。它更快，有多种周期，更重要的是能产生更高质量的随机数。

根据状态大小，WELL周期可以是2的n次方。n=512、521、607、800、1024、19937、21701、23209、444497。这样允许用户牺牲周期长度来换取较小状态，提升了灵活性。所有的WELL算法速度相当。一台标准PC需要1 Googol年来计算2的512次方个随机数（1 Googol = ,谷歌“google”就是来源于此）

相对于MT19937，WELL一个显著改进就是能快速跳过大量0位的内部状态。如果MT19937种子有大量的位是0，或者某种情况下进入了一个有大量位是0的状态，它接下来生成的几个随机数将有很大程度偏向于0。WELL算法表现要好很多，很快就能跳过偏向于0的状态（但是仍然有些许可能性）以下是Chris Lomont的实现，比Matsumoto官方实现快大约40%。

static unsigned long state[16];

static unsigned int index = 0;

unsigned long WELLRNG512(void)

{

       unsigned long a,b,c,d;

       a = state[index];

       c = state[(index+13)&15];

       b = a^c^(a<<16)^(c<<15);

       c = state[(index+9)&15];

       c ^= (c>>11);

       a = state[index] = b^c;

       d = a ^((a<<5)& 0xDA442D20);

       index = (index + 15)&15;

       a = state[index];

       state[index] = a^b^d^(a<<2)^(b<<18)^(c<<28);

       return state[index];

}

(二）加密随机数生成算法

密码安全的PRNG(CSPRNGS)让攻击者即使获得大量的输出，也很难推断生成器的内部状态或者预测未来输出。一些CSPRNG已经被标准化并且有了开源实现，但是这些算法都应该小心使用，以避免可能存在的陷阱。如果可能，尽量使用可靠的来源，并确认是有效的。而大部分的CSPRNG为了保证密码学强度并未开源，所以此类算法实现细节仍然不得而知。

1、Blum Blum Shub

，然后随机数由计算而来。其密码学强度基于因式分解，但是由于Shor的量子因式分解法已经可以高效分解整数，如果量子计算机投入使用，那么此算法与RSA都不再安全了。

该算法一般只在需要加密时使用，因为它比不加密的PRNG慢很多。

2、ISAAC、ISAAC+

该算法是基于RC4密码变体的CSPRNG。ISAAC没有小于240的周期，预期的周期为28295。

3、/dev/random

虽然不是一个特定的算法，但是Linux和很多Unix的衍生品都在/dev/random命令下实现了一个随机源，它返回一个基于系统熵的随机数，因此可以被视为真随机数生成器。但是/dev/random是阻塞的，意味着在搜集到足够的熵之前是不会返回的。因此很多程序都使用不阻塞的/dev/unrandom。但是这样得到的随机数就不是那么安全，并且/dev/unrandom会耗尽系统熵，稍差的实现很容易被攻击。该实现没有特定的算法，有些实现使用了Yarrow。

4、微软的CryptGenRandom

微软的CryptoAPI函数库中的CryptGenRandom可以生成密码安全的随机字节来填充一个buffer。和/dev/random类似，它也可以被视作真随机数生成器。虽然没有开放源文件，但是它通过了FIPS认证，所以被认为是安全的。在Windows上，这是个不错的CSPRNG。

5、Yarrow

一种免费的开源PRNG，Mac OS和Free BSD都用该算法来实现了/dev/random。原作者已经不再对它进行支持，开发了一个改进的Fortuna算法。

6、Fortuna

该算法基于任意良好的分组密码，并在计数模式下加密，加密后续计数器的值。它的密钥是周期性变动的，以避免一些设计缺陷。它使用了一个熵池来收集对系统有效的随机熵，因为使用了外部熵，所以被视为真随机数生成器。

4、创造随机数生成器的常见错误

创造一个好的随机数生成器非常重要，在RNG的历史上，坏的设计随处可见，并且导致了很多恶劣的后果。用户总是可以从别人的错误中学习到经验，所以让我们来看一看这个领域中的一些常见错误。

RANDU:一个曾经被广泛使用的病态PRNG。RANDU是LCG（，65539，0），初始种子必须是奇数。这些常量的选择最初是想让实现更简单快捷。像所有的LCG一样，RANDU存在线性相关的缺陷并曾经导致一系列严重问题。下图展示了10万个三维绘制的三元组，它们完全分布在15个平面上。

Netscape：Netscape的早期版本需要好似用CSPRNG,并用其结果来作为密码，但是这个CSPRNG使用的3个种子没有完全散布开（该CSPRNG使用当前时间、本进程ID、父进程ID 作为3个种子）导致了一个基于Netscape SSL协议的成功攻击。

一些民间算法：某个游戏开发者曾经在一款游戏中实现了一个自定义的快速PRNG，其基本想法是将数位从种子中移出，每当种子中移出一位时，与一个常量做XOR操作。这个算法速度很快，粗看也不错，但是经过测试后发现该算法会产生一个递减的序列，然后不断回跳，形成锯齿状的书出。这个结果直接导致了该游戏中AI系统的一个BUG（该作者从未怀疑过此BUG来自于他的PRNG，因为该PRNG已经使用多年）。

最后是一个的笑话：某个游戏的getRandomNumber函数的实现：

5、结语

本文提供了一些RNG/PRNG的基本知识，也包括了一些常用的算法。一个专业的开发者应该了解RNG/PRNG的各种类型，并且知道什么时候该用哪一种，而一个专业的测试人员则应该在了解程序所使用的RNG/PRNG算法实现的前提下发现其可能存在的问题。希望本文能提供这些基础知识并作为一个有益的参考。