随机数生成器，免费

计算机随机性简史

计算机是确定性的机器,这让"随机"成了一件让它们去产出的奇怪事。计算机上伪随机数生成器(PRNG)的历史始于 John von Neumann 1946 年的中方法:把上一个数平方,取中间几位作为新值,重复。von Neumann 自己说过,如果你不充分理解,使用任何随机数生成器都是"罪恶的状态",因为中方法有明显的失败模式(回到零的循环、短周期)。Lehmer 的线性同余生成器(LCG,1951),x_(n+1) = (a × x_n + c) mod m,是第一个具有合理统计性质的 PRNG 家族;C 标准库的 rand() 通常仍然使用一种 LCG 变体。Mersenne Twister(Matsumoto 与 Nishimura,1997-1998)给了我们一个周期为 2¹⁹⁹³⁷−1(没错,一个 6,000 位的数字)且统计性质优秀的生成器;它在 Python、R、MATLAB、PHP 等众多语言中成为默认。Marsaglia 的 xorshift 家族(2003)更快,且小到能塞进一个硬件寄存器;现代 V8(Chrome 的 JavaScript 引擎)对 Math.random() 使用 xorshift128+ 的变体。Melissa O'Neill 的 PCG(Permuted Congruential Generator)(2014)是当前非密码学 PRNG 的统计前沿,把 LCG 风格的状态推进与输出置换组合起来,以低成本得到出色的统计性质。

密码学安全的 PRNG(CSPRNG)是另一回事。定义性的属性:即便攻击者知道生成器产出的每一个输出,他也无法以可观的优势预测下一个输出。Linux 的 getrandom() 系统调用(2014 年 10 月加入内核 3.17)与底层的 /dev/urandom 使用基于 ChaCha20 的生成器,由硬件熵源(RDRAND、中断时序、音频噪声)播种。Windows 的 BCryptGenRandom 使用 AES-CTR-DRBG 构造(NIST SP 800-90A),由多个熵源播种。macOS / iOS 使用源自 Fortuna 的 CSPRNG。PRNG 与 CSPRNG 的差别影响巨大:PRNG 适合游戏随机、A/B 测试分桶或仿真;对任何攻击者可能尝试预测的东西(会话令牌、密码生成、安全 ID),只有 CSPRNG 才安全。

JavaScript 的两个随机 API

Math.random() 是更老、更简单的 API,返回近似在 [0, 1) 内均匀分布的浮点数。ECMAScript 规范刻意没有指明底层算法("approximately uniform distribution between 0 and 1, exclusive"),引擎多年来对所用算法做过切换。V8(Chrome)在 2015 年之前用 Park-Miller LCG,之后切到 xorshift128+ 以获得更好的统计性质。SpiderMonkey(Firefox)与 JavaScriptCore(Safari)使用类似的快速非密码学生成器。Math.random() 对游戏机制、仿真,以及任何不把不可预测性当作安全要求的应用,速度足够快、足够均匀。它不是密码学安全的,周期由实现决定,从少量输出可以恢复状态,序列对密码生成或安全敏感场景并不安全。crypto.getRandomValues() 是 Web Crypto API 的 CSPRNG。它把一个类型化数组填充为来自操作系统 CSPRNG 的密码学安全随机字节(与 TLS 用来获取会话密钥的源相同)。所有现代浏览器从大约 2014 年起均可用;单次调用的最大缓冲区是 65,536 字节。任何"重要"的随机数都该用它,令牌生成、安全 ID、密码生成,以及任何攻击者可能尝试预测的内容。

模偏置陷阱

从 CSPRNG 在指定范围内生成均匀整数,比看上去要难。朴素做法,例如骰子用 crypto.getRandomValues(new Uint8Array(1))[0] % 6,会得到带偏置的分布,因为 256 不能被 6 整除。在 0-255 范围内,值 0-3 各出现 43 次,值 4-5 各出现 42 次。偏置在小范围里很小,但是真实存在,长程跑统计能查出来。标准修法是拒绝采样:生成一个随机字节,看它是否落在范围最大可整除倍数之内(此处 252 = 42 × 6),落入则使用,落不入则丢弃重试。丢弃率受 (范围 / 下一个 2 的幂) 限制,所以"1-6"大约浪费 1.5% 的字节;"1-1000000"配 32 位随机整数大约浪费 0.02%。任何认真的随机库都实现了拒绝采样;基于 Math.random() 的 Math.floor(Math.random() * (max - min + 1)) + min 能避开偏置,因为 Math.random() 的精度足够高(53 位尾数),让任何合理范围下的偏置都低于人类可察觉的水平。本生成器使用 CSPRNG 输出加拒绝采样,任何整数范围的输出都是均匀的。

用途与每种用途所需的随机性级别

• 抽奖与抽签。对于非货币性抽签(办公室换位、黑客松组队、教室排座),Math.random() 够用。对货币抽奖或任何受监管的场景,使用 CSPRNG,并最好公开种子以便核验。
• 游戏机制。掷骰、洗牌、掉宝、过程化生成。Math.random() 是标准选择,快、足够均匀、足够不可预测,玩家不会察觉模式。CSPRNG 留给在线纸牌游戏,服务端必须防作弊的场合。
• A/B 测试分桶。用稳定的密钥对用户 ID 做哈希,把每个用户确定地放进一个桶,使用 Math.random() 会让用户在两次页面加载之间落到不同桶里,实验就废了。基于哈希的分配才是正确模式;随机性只在选择实验种子时用一次。
• 问卷的随机抽样。从总体中抽取一个有代表性的子集。Math.random() 够用;统计学问题是你的样本是否够大,而不是随机源是否密码学级。
• 测试数据生成。Faker、模拟数据、合成数据库 fixture。Math.random() 加一个固定种子(以便可复现)是正确的选择。
• 密码学密钥、会话令牌、密码生成。仅 CSPRNG,浏览器里的 crypto.getRandomValues()、Python 的 secrets 模块、Go 的 crypto/rand,绝不要用语言默认的随机。这一层的 bug 会让一切依赖它的东西崩塌;后果从"每个人的会话都可被劫持"到"加密密钥可被恢复"。

RANDOM.ORG 与真随机的区分

RANDOM.ORG 由 Mads Haahr 1998 年在都柏林圣三一学院启动,至今仍是网络上"真随机"的金标准。每个 CSPRNG 最终都从硬件播种状态的算法变换中得到比特(确定性的过程,即便对攻击者不可预测),而 RANDOM.ORG 测量来自无线电接收器的大气噪声,把模拟噪声直接变换成比特。这让它成为真随机数生成器(TRNG)而非伪随机数生成器:比特来源于一个真正非确定性的物理过程,而不是来自确定性算法。RANDOM.ORG 被彩票运营商、做双盲研究的学术研究者,以及讲究随机可验证的游戏所使用。代价是:每次请求一次网络往返、免费档每天有配额,以及一个哲学问题,即你是否更信任 RANDOM.ORG 声称的熵源,而非你本地的 CSPRNG。对绝大多数用途,本地 CSPRNG 已足够;对需要第三方独立核验随机性的场景,RANDOM.ORG 提供付费的随机性签名证书。

无放回抽样:Fisher-Yates 洗牌

当你需要在一个范围里取 N 个不重复的数,例如从 1-49 抽 6 个用于彩票、从 1000 名报名者中选 10 名中奖者,朴素的"生成,如果重复就丢掉"对小 N 还行,但当 N 接近范围大小时会迅速恶化(池子缩小,抽到新数的概率随之下降)。标准算法是 Fisher-Yates 洗牌,源自 Fisher 与 Yates 1938 年的统计表,Donald Knuth 1969 年把它整理成现代计算机科学形式(有时也叫 Knuth shuffle)。算法极其简单:把数字 1 到 N 写入一个数组;对从 N-1 到 1 的 i,把元素 i 与 0 到 i(包含)之间的一个随机元素交换;数组现在被均匀地洗过了。取前 K 个元素就得到 K 个不重复的随机数。关键细节:随机下标必须落在 [0, i],包含 i,使用 [0, i-1] 会引入一个微妙的偏置,密码学社区花了多年才把它刻画清楚(Sattolo 变体,有时被错误地当作真正的 Fisher-Yates 来用)。对范围非常大、把所有 N 个值放入数组不实际的情况(例如从 1-10⁹ 中挑 100 个不重复的值),水库抽样(Vitter,1985)能在有限内存下用一遍处理流式或无界输入。

掷骰约定

随机数生成器是化了装的骰子。D6(六面骰)是桌游的通用默认,范围 1-6。D20(二十面骰)是 Dungeons & Dragons 的标志性骰子,用于属性检定、攻击掷与豁免掷,D&D 的修正符体系意味着一次 D20 加一个属性加成就决定了大多数行为的结果。D100(百分骰,1-100)用于《克苏鲁的呼唤》、Warhammer Roleplay 等许多暴击概率系统的百分掷。记号 NdM 表示"投 N 个 M 面骰再求和";NdM+B 加一个奖励。3d6 投三个六面骰求和(范围 3-18,经典 D&D 属性值范围,以三角分布在 10-11 居中)。在公平模拟里,对每个骰子在 [1, M] 内生成均匀整数再求和,与掷物理骰子完全等价,底层 CSPRNG 的分布比你能买到的任何物理骰子都更均匀。赌场和受监管的博彩使用通过统计电池(TestU01 的 BigCrush、NIST SP 800-22)测试的认证 RNG,以向博彩监管机构证明均匀性;同样的标准也适用于彩票 RNG。

种子与可复现

PRNG 一个微妙却重要的属性:给定种子,它们是确定性的。把种子设为已知值,"随机"数序列就完全可复现。这对测试无价(用随机数据的单元测试应固定种子,使失败可复现),对可核验的抽奖也无价(在抽签前发布种子,然后任何人都能验证结果)。Python 的 random 模块为此提供 random.seed(value);Java 的 Random 在构造器接受种子。JavaScript 的 Math.random() 故意不暴露播种 API,引擎把种子视为内部状态,但若干纯 JS 库(seedrandom、pcg-random)提供带种子的 PRNG。CSPRNG 在设计上不同:它们不暴露种子,因为整套体系的意义就在于不可预测。需要可复现就用带显式种子的 PRNG;需要安全就用 CSPRNG,并接受你之后无法重现这个序列。

隐私:为何随机数也要纯浏览器

随机数本身很少含有敏感信息,那纯浏览器架构为什么重要?两个原因。第一,当一个随机数被用作会话令牌、幂等键、认证挑战或任何其他类似秘密的值时,在第三方服务器上生成意味着该服务器在你使用之前先看到了那个值,虽小但确实存在的暴露。第二,服务器端那些声称提供"密码学随机性"的生成器无法被用户验证;一个有 bug 或恶意的服务器可能返回看似随机的非随机或带偏置的值,而你不进行大量采样就无法察觉偏置。纯浏览器生成器走的是和你应用本应在服务器端调用的同一个 crypto.getRandomValues();熵来自同一个操作系统源(Linux getrandom()、Windows BCryptGenRandom、macOS);没有第三方看到输出。你可以在点击"生成"时打开 DevTools 的 Network 标签自行验证,没有任何对外请求。页面加载完后切到飞行模式,生成器仍可工作。

常见问题