转眼年关切近，很多业务都会考虑做一些抽奖活动，而各大公司在年底也会考虑开办年会。年会中，一般会安排抽奖环节。抽奖程序一般接收一个抽奖人员列表，通过算法产生一个随机数，再通过某种对应关系，将列表中的某个人与这个随机数匹配。这个匹配的人就是中奖的幸运儿了。
不出意外的话，年底这一个多月，通常是一年中随机函数被调用最频繁的一段时间。
笔者工作后参加过大大小小的年会无数，获得最多的就是阳光普照的安慰奖，这一般是给抽奖程序不垂青的人的一个人性关怀。无数和笔者一样在阳光普照、甚至都没普照到的可怜的人，不禁把矛头对准了抽奖程序。而抽奖程序的撰写者，往往更加无辜，除了把程序给大家review，甚至为了避嫌还经常把自己从抽奖名单中剔除，注定不能中奖，是不是很郁闷？
一般的抽奖程序，无外乎两个关键点：一是名单重组与对应关系，比如进入奖池顺序和从奖池剔除的逻辑以及奖池与随机数的对应关系；一是随机数产生的算法。
前者，我们可以在抽奖程序中不断迭代，以获得最佳的成果；后者，往往要看随机数的生成算法。
这里我们来着重探讨随机数生成算法。
一般地，我们希望随机数在值域范围内均匀分布，是完全杂乱的数列；其结果具有不可预测性；除非将数列本身保存下来，否则不能重现相同的数列。以上三个特性分别对应于随机数三个特征：随机性、不可预测性以及不可重复性。在密码技术上使用到的随机数至少要达到不可预测性这一等级，即至少是强伪随机数，最好是真随机数。
除了抽奖的业务场景之外，我们在生成密码的场景之内，也会大量使用随机数。了解了密码学的知识后，我们知道，随机数分为真随机数和伪随机数。真随机数一般借助物理特性的值产生，CPU中往往会内置真随机数生成器（TRNG），借助计算机电路的一些特定的“随机”物理特性，来生成随机数。不过这种生成随机数的方法代价较大，且物理世界是否真正遵循“随机”还没有定论。往往地，计算机系统会通过特定的算法，又称伪随机数生成器（PRNG）来生成伪随机数。伪随机数生成器一般需要一个随机种子，由伪随机函数生成的一组数列。按照随机数生成随机序列的特点，又可以分为强伪随机数和弱伪随机数。对于强伪随机数，其生成器又称密码学伪随机数生成器（CSPRNG）。
CSPRNG是PRNG的一个子集。产生高强度的随机数，有两个重要的因素：种子和算法。
算法一般是公开的，我们需要一个数字来作为种子，并且要保护好这个种子，以防止泄密。尴尬的是，这个数字一般也要求为随机数。使用系统时间作为种子的做法，是不安全的。常见的生成思路就是收集计算机的各种信息、键盘输入时间、内存使用状态、硬盘空闲空间、IO延时、进程数量、线程数量等信息、CPU时钟、来得到一个近似随机的种子，主要是达到不可预测性，同时提高了破解需要的成本。还有的软件为了安全性，规定产生若干个随机数后要重新产生一个种子，就是重置一次，比如Linux的随机数生成器/dev/random。当破解的成本足够高，以至于高于内容的价值，那么这次密码的保护就是成功的。
常见的生成算法如：线性同余法、单向散列函数法、ANSI X9.17等等。各种算法有公开的也有需要付费的。同时各种算法也在和破解者不断攻防中进行迭代。
我们通过列表来对比一下三类随机数生成器：
| 随机性 | 不可预测性 | 不可重现性 | 生成器 | |
|---|---|---|---|---|
| 弱伪随机数 | Y | N | N | 伪随机数生成器 PRNG, 不可用于密码技术 |
| 强伪随机数 | Y | Y | N | 伪随机数生成器 CSPRNG, 可用于密码技术 |
| 真随机数 | Y | Y | Y | 真随机数生成器 TRNG, 可用于密码技术 |
回到我们比较熟悉的ECMAScript，我们常用Math.random生成随机数。Math.random并没有指定实现的方法，只是给出了算法行为：
Math.random返回一个具有正值的数字值，大于或等于0但小于1，使用一个依赖于实现的算法或策略随机或伪随机地选择，在该范围上具有近似均匀分布。此函数不接受参数。
不同的引擎实现方式是不一样的。事实上，越来越多的浏览器开始采用xorshift128+算法来最终实现生成随机数。
这里是V8引擎的最新的实现。它首先用散列murmurhash3算法，将系统时间散列散列成两个状态值，然后使用xorshift128+最终生成随机数。
这种算法效率很高，但它不是密码学意义上的安全伪随机数生成器。由于它是周期性函数，当获取了足够多的历史数列，就预测未来的状态，不具备不可预测性，不能将它用于密码技术。当然，同样作为弱伪随机数生成器，周期越长，同时效率越高的算法，则被认为是更加优秀的算法。特别地，V8当前的Math.random实现，周期为：2^128-1。
同时，V8官方的实现上也表明，当同样的随机数种子进入随机算法，则产生的伪随机数数列是相同的。如果多个线程同时请求随机数，此时均以同样的系统时间作为种子，则会产生相同的随机数列，因此，这种算法是非线程安全的。所幸，JavaScript绝大多数情况是单线程运行的，因此这一特性产生的后果并不严重。
ECMAScript标准中也告诉我们，Math.random不应该在需要密码学安全的场景下使用。这种时候，你可以使用Crypto.getRandomValues。
blink中Crypto.getRandomValues方法，最初使用RC4算法生成随机数，不过自2015年开始，RC4算法被证明可以通过某种有穷列举的方式，达到破解的目的，因此被认为不再是安全的加密算法，因此被抛弃，转而直接调用操作系统提供的随机数生成法。当然，天下没有免费的午餐，这个方法的相对安全，换来的是执行效率相对低于Math.random。
现在回到我们最初的问题，对于抽奖的业务场景，Math.random是否够用。我们看到，Math.random在执行效率上占有一定的优势。但是，结果有一定的可预见性，在抽奖这种环节，特别是牵涉人员较多、奖项较敏感时候，使用是值得商榷的。更保险的方法是使用Crypto.getRandomValues，那么，如何使用呢？我们给出一段代码：
(function() {
var rng = window.crypto || window.msCrypto;
if (rng === undefined){
return
}
window.randomSafe = function() {
return rng.getRandomValues(new Uint32Array(1))[0] / 0xFFFFFFFF;
}
})()
这里可以采用randomSafe代替Math.random来进行随机数的选取。
由此，我们再延展一层。很多浏览器如Chrome在window.crypto实现了Web Crypto的API。但是和最终的API实现有一定的差异。最新的浏览器已经将这些方法移除，并在Crypto.subtle属性中参照https://www.w3.org/TR/WebCryptoAPI/重新实现了这些API，开发这可以自己指定加密算法、文摘算法、key值等。感兴趣的读者可以参考相关的说明。
对于随机算法，比较公认的是参考nist的随机算法评测程序https://csrc.nist.gov/projects/random-bit-generation/documentation-and-software和Big Crush。可以通过程序的方法对随机算法进行比较客观的评价。
看到这里，我们不禁长出一口气。看来中奖不中奖，阳光普照还是不普照，不光是RPWT，还有一些锅，可以交给算法。
预祝大家在年会中被随机算法选中！
Comments