Random Number Generator

来自osdev
跳到导航 跳到搜索

随机数生成器（RNG）可以用很多不同的方式实现。 本文解释了其中一些方式。


熵（Entropy）

计算机是确定性设备。 如果程序相同且所有输入相同，则每次计算的结果都相同。 那么，计算机如何生成随机数呢？ 计算机不可以是随机的，但它周围的物理世界可以。 许多物理事件在某种程度上是随机的，或者更严格地说，具有某种程度的熵。 即使在地球上最好的屏蔽录音室里，录音也会包含一定程度的噪音。 人类在键盘上输入的时间不一致，并且输入准随机文本，比如你正在阅读的文章。 甚至其他计算机也可以提供熵：虽然大多数网络流量完全是机器生成的，但最终网络数据包的确切相对时间来自按下电源按钮的那一刻，这是另一种人类行为。 因此，输入事件的时间和性质可以为我们提供一些熵。

随机数生成器的类型

有多种方法可以划分随机数生成器；一种是通过数字的生成方式，另一种是通过数字的使用方式。 这些是重要的区别：前者可能会影响操作系统的设计，后者可能会影响系统的安全性。

随机数的来源

有两种随机数：“真”随机数和伪随机数。

对于“真”随机数生成，系统持续测量预期为随机的特定事件集。 这可以是宇宙辐射和原子衰变，也可以是用户输入的时间和时钟抖动。 测量是去偏（de-biased）的，并“搅拌”到一个熵池中，从中可以提取随机数。

伪随机数由一种算法（PRNG）生成，该算法转换一些内部状态，并根据请求计算输出值。 可以设置初始种子，但在此之后，下一个状态仅取决于前一个状态。 有许多不同的PRNG，下面讨论其中一些。

可以使用一些“真”随机数来为伪随机生成器的状态设定种子，但这并不能使PRNG“真随机”。 根据具体的算法，预测所有下一个输出可能与预测前一个输出一样简单。 正如下一节所讨论的，这可能会产生严重的影响。

随机数的应用

大致有两种应用：密码学和其他方面。

为了理解以下部分，我们首先应该回顾一下关于随机数生成器的加密安全意味着什么。 密码学家将安全分为两类：信息论安全和计算安全。 前者是更有力的主张。 如果密码系统在理论上是安全的，那么攻击者在不拥有密钥的情况下，就不能得出任何关于加密消息的信息。 这种密码系统很少见。 由于攻击者不能得出“任何东西”，因此必须隐藏所有内容，包括模式、时间甚至长度。 一个人怎么能隐藏信息的长度呢？ 唯一的选择是根本不发送消息，这违背了密码系统的目的，或者发送无限长的消息。 所以一旦你开始发送，你就永远不会停止。

这就是为什么计算安全性较弱，但更实用的一种：密文必须很难找到，“给定一些合理的计算能力”。 选择这一限制的目的是希望在未来几十年内不会达到。 这还允许用户“泄露”有关密文的一些信息（例如，长度），只要找到原始输入仍然困难。 这些系统通常使用一些很难反转的操作，除非已知密钥，例如大素数分解。 很明显，密钥不能是可预测的：如果对手知道下一个输出是什么，他们很容易猜测密钥，直到找到正确的密钥。

“真”随机数是加密安全随机性的最佳来源，但是很难建立一个大的、快速补充的熵池，其中每个源都是完全无偏的，并且不受其他源的影响。 要以难以逆转的方式“拉伸”熵，可以使用加密安全随机数生成器（CSPRNG）。 CSPRNGs保证，在看到之前的结果后，在计算上很难猜测下一个输出，如果生成器的状态已知，哪些值在已知输出之前。

真随机数生成器

真正的随机数生成器使用物理设备或现象生成随机数，其不可预测性可以追溯到量子力学定律。

x86 RDSEED指令

较新的x86和x86-64处理器具有用于生成随机数的指令RDSEED。 要使用RDSEED，首先需要检查指令是否可用。 

mov eax, 7     ; set EAX to request function 7
mov ecx, 0     ; set ECX to request subfunction 0
cpuid
shr ebx, 18    ; the result we want is in EBX...
and ebx, 1     ; ...test for the flag of interest...

如果EBX设置为1（或ZF未设置），则该指令可用。 然后可以使用它生成16/32/64位随机数（取决于用作参数的寄存器大小）。 如果生成了随机数，则设置进位标志。 

mov ecx, 100   ; number of retries
.retry:
    rdseed eax
    jc .done      ; carry flag is set on success
    loop .retry
.fail:
    ; no random number available
.done:
    ; random number is in EAX

这取决于你和你的用户是否信任RDSEED。 因为它是在硬件中实现的，所以它实际上是一个黑匣子，可能包含各种错误，或者更糟的是，后门。

专用硬件

有专门用于生成“真”随机数的设备。 从消费者级TPMs到PCIe“加密加速器”都有。 这些是RDSEED/RDRAND的一种泛化，缺点是需要额外的驱动程序来与设备交互，用户可能没有安装这样的设备。

TPMs或Trusted Platform Module是可以安装在现代主板上的小型协处理器。 除了生成随机数，它们还提供其他可信计算服务。 值得注意的是，Windows 11要求有TPM。 它们也可以在CPU上模拟（例如英特尔PTT或AMD fTPM）。 与RDSEED一样，后门可能是一个问题。

手动采样

在一个运行的系统中，有很多进程实际上是随机的。 想想每秒钟都会出现的各种中断：精度为百万分之几的计时器、外围I/O、用户与整个系统的交互等等。

挑战在于找到（矛盾的是）可靠随机且难以从外部影响和观察的来源。 对于这些源中的每一个，必须估计它们贡献了多少熵。 测量将各自的熵量添加到池中，而读取则会降低熵。

因为你可以完全控制这种生成方法，所以还可以合并硬件生成器生成的值。 你可以自己决定这些生成器的熵是多少，甚至是0位。

当使用计时作为熵源时，读取的时间戳应尽可能精确。 TSC在这方面做得很好。 衡量从该操作中获得的熵需要了解事件发生的时间窗口和TSC的滴答率。 例如，如果一个TSC的滴答频率为3 GHz，并且一个事件有一个10毫秒的窗口要发生，那么TSC读取可以有3000万个值中的任何一个，这意味着从中获得的熵约为24.8位。 如果TSC较慢，只有1GHz，那么熵将只有约23.2位。

对抗熵

如果对手能够以某种方式观察熵池的状态，并将自己的熵贡献给熵池，那么他们提供熵的方式可能会迫使熵池进入较低的熵状态。 一个简单的例子是，熵源定期检查池中的某个位是否已设置，然后提供熵，直到它被清除。 这样，在大多数情况下，给定的位是清晰的，熵缓冲区可能处于的状态数减少了一半。 DJB的博客上描述了一种更复杂的攻击：https://blog.cr.yp.to/20140205-entropy.html

部分原因还在于，如果用户请求一个随机数，不经修改地公开熵池是不明智的。 如果对手可以访问该池（通过专用的“添加熵”接口或采样事件源），则很容易对其下毒。 用于隐藏确切状态的常用方法是使用加密安全的哈希函数（如SHA-256），结合计数器（例如熵计数器）和salt对池（部分）进行哈希运算。 因为这些散列算法很难反转，所以它的输入不容易猜测。 只有当池中还有一些熵时，才需要这样做。

加密安全的伪随机数生成器（Cryptographically secure pseudorandom number generators）

现在跟随一些CSPRNGs。 重要的是要记住，与任何加密一样，如果你打算实际使用它，最好不要自制它。 出错的方式很多，算法越复杂，出错的几率就越大。 当然，对于业余用途来说，这是完全好的；只是不要使用手工制作的TLS密钥源进行网上银行业务。

x86 RDRAND指令

RDRAND比RDSEED稍早，并提供([https://software.intel.com/content/www/us/en/develop/blogs/the-difference-between-rdrand-and-rdseed.html 英特尔声称的）CSPRNG。 它的存在由CPUID leaf，ECX位30表示： 

mov eax, 1     ; set EAX to request function 1
mov ecx, 0     ; set ECX to request subfunction 0
cpuid
shr ecx, 30    ; the result we want is in ECX...
and ecx, 1     ; ...test for the flag of interest...

如果ECX设置为1（或ZF未设置），则该指令可用。用法与RDSEED相同： 

mov ecx, 100   ; number of retries
.retry:
    rdrand eax
    jc .done      ; carry flag is set on success
    loop .retry
.fail:
    ; no random number available
.done:
    ; random number is in EAX

它由RDSEED读取的同一个熵源自动播种，不能手动播种。 因此，它与RDSEED一样需要注意。

Ciphers

通过植入一个安全Cipher（如ChaCha20和AES）并运行多个循环来构造CSPRNG是相当常见的，在这些循环中，输出与运行的计数器一起被重新加密。 每隔一段时间，就会创建一个新密钥，可能涉及另一个安全的随机源。

编写（和植入后门）一个基于CSPRNG的ChaCha20的可能是一篇关于这个主题的有趣文章，以及它如何以令人惊讶的方式出错。

伪随机数生成器

接下来是各种常规PRNG。 它们在质量、简单性和速度的各个方面都有所不同。 仔细阅读每个解释！

标准的示例

直接取自 C标准文档（第347页）： 

//以下函数定义了rand和srand的可移植实现。

static unsigned long int next = 1;  // 注：“unsigned long int”假定为32位宽

int rand(void)  // RAND_MAX假设为32767
{
    next = next * 1103515245 + 12345;
    return (unsigned int) (next / 65536) % 32768;
}

void srand(unsigned int seed)
{
    next = seed;
}

这是一个相当标准但平庸的标准 线性同余发生器（Linear Congruential Generator-LCG）。 它返回15个随机位。

它基于这个递推公式 

 Xn+1 = (aXn + c) mod m

其中，模数m是LCG能产生的最大随机值数。 对于C标准中的示例，a=1103515245、C=12345和m=232（隐式）。 LCG的质量在很大程度上取决于这些值，很难找到好的值。 维基百科给出了常见参数列表。

斐波那契随机数

斐波那契序列的特殊“重拍”可以用来生成随机数。 这是通过有4个“种子”来实现的，这些种子一开始是非常奇怪的值（例如45、80、22、32）。 seed()函数的作用是：在序列的末尾添加一个新的种子，并删除第一个种子（种子被称为A、B、C和D）。 rand（）函数只返回种子的总和，并用结果调用seed（）。 Glidix就是这种RNG实现的一个很好的例子。

线性反馈移位寄存器

线性反馈移位寄存器（LFSR）是一种简单的方法，可以在给定非零种子的情况下生成很长的随机数序列。 其思想如下：“n”位LFSR有“n”位（0或1）。 最初，寄存器用“n”位种子填充。 对于下一个要生成的值，从寄存器中“点击”某些位，并将它们异或在一起。 将结果二进制值输入最左边的位，将所有位向右移动一个位置。 从最右侧LFSR移出的位是生成的随机位。

LFSR可以产生的比特序列最终会重复，但通过仔细选择异或比特，LFSR的周期可以增加到最多2n-1比特。 这意味着在一个2n-1位的序列之后，将返回相同的序列。 然而，这是所有伪随机数生成器都具有的一个特性：在不改变种子的情况下，它们最终会重复自己。

下面是一个16位LFSR的示例，使用位11、13、14和16异或作为其输入。 该LFSR的周期为65535位，因此在序列自身重复之前，它将生成一个65535位的伪随机序列。 LFSR产生的下一个位是1（位16的值），下一个输入位是0。 

            1                                       11      13  14      16
          +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
INPUT --> | 0   1   0   0   0   1   0   0   1   1   1   1   0   0   0   1 | --> OUTPUT
          +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+

INPUT = bit 11 XOR bit 13 XOR bit 14 XOR bit 16

更大（和更小）的LFSR也是可能的。 聪明人已经推导出多项式，确保在任何非零输入的情况下，LFSR的周期尽可能大（2n-1）。 这样的多项式被写成x16+x14+x13+x11+1。 对于这个“n”=16的多项式示例，位16、14、13和11必须异或在一起，并作为输入提供，从左开始计数，从1开始。 Polynomials for other values of n can be found here on Wikipedia and on page 5 of this PDF document.

请注意，种子永远不能为零。 这也意味着，不可能所有寄存器的位值都为零，而在2个寄存器的可能组合中，不允许全零状态。 因此，2个n-1状态是可能的最大值。

Wichmann-Hill

1982年，Brian Wichmann和David Hill建议组合三个线性同余生成器，然后对结果进行归一化和求和，得到一个均匀分布在0和1之间的数。 一个常见的例子是： 

static uint16_t seed[3]; /* seed with numbers between 1 and 30000 */
float wichmann_hill(void) {
  seed[0] = (171 * seed[0]) % 30269;
  seed[1] = (172 * seed[1]) % 30307;
  seed[2] = (170 * seed[2]) % 30323;
  return fmod(seed[0] / 30269.0 + seed[1] / 30307.0 + seed[2] / 30323.0, 1.0);
}

已知该版本的周期略小于7万亿（最常见的倍数为30268、30306和30322）。

Mersenne Twister

Mersenne Twister是一款非常受欢迎的PRNG，可在大多数平台上使用；例如，它是C++11标准库所需的生成器集的一部分。 64位MT-19937版本的C实现如下：

根据维基百科实现： 

#include <stddef.h>
#include <stdint.h>
#include <assert.h>

#ifdef USE32
typedef uint32_t word_t;
#define STATE_SIZE  624
#define MIDDLE      397
#define INIT_SHIFT  30
#define INIT_FACT   1812433253
#define TWIST_MASK  0x9908b0df
#define SHIFT1      11
#define MASK1       0xffffffff
#define SHIFT2      7
#define MASK2       0x9d2c5680
#define SHIFT3      15
#define MASK3       0xefc60000
#define SHIFT4      18
#else
typedef uint64_t word_t;
#define STATE_SIZE  312
#define MIDDLE      156
#define INIT_SHIFT  62
#define TWIST_MASK  0xb5026f5aa96619e9
#define INIT_FACT   6364136223846793005
#define SHIFT1      29
#define MASK1       0x5555555555555555
#define SHIFT2      17
#define MASK2       0x71d67fffeda60000
#define SHIFT3      37
#define MASK3       0xfff7eee000000000
#define SHIFT4      43
#endif

#define LOWER_MASK  0x7fffffff
#define UPPER_MASK  (~(word_t)LOWER_MASK)
static word_t state[STATE_SIZE];
static size_t index = STATE_SIZE + 1;

static void seed(word_t s)
{
    index = STATE_SIZE;
    state[0] = s;
    for (size_t i = 1; i < STATE_SIZE; i++)
        state[i] = (INIT_FACT * (state[i - 1] ^ (state[i - 1] >> INIT_SHIFT))) + i;
}

static void twist(void)
{
    for (size_t i = 0; i < STATE_SIZE; i++)
    {
        word_t x = (state[i] & UPPER_MASK) | (state[(i + 1) % STATE_SIZE] & LOWER_MASK);
        x = (x >> 1) ^ (x & 1? TWIST_MASK : 0);
        state[i] = state[(i + MIDDLE) % STATE_SIZE] ^ x;
    }
    index = 0;
}

static word_t mt_random(void)
{
    if (index >= STATE_SIZE)
    {
        assert(index == STATE_SIZE || !"Generator never seeded");
        twist();
    }

    word_t y = state[index];
    y ^= (y >> SHIFT1) & MASK1;
    y ^= (y << SHIFT2) & MASK2;
    y ^= (y << SHIFT3) & MASK3;
    y ^= y >> SHIFT4;

    index++;
    return y;
}

有些实现会自动使用seed 5489为生成器设定种子，但这（显然）会导致每次初始化时都有相同的输出。


它的表现优于上面列出的所有PRNG，但由于其庞大的状态规模，速度相当缓慢。 它在一些统计领域也存在问题。 参考 "It is high time we let go of the Mersenne Twister"。

PCG系列

PCG系列是PRNG领域的一个相对较新的成员。 最简单的版本使用带有置换运算符的LCG对输出进行置乱。 它是为了通过尽可能多的统计测试而建造的，同时仍然保持小而快。 There is a comprehensive paper describing the generators and Apache 2.0-licensed code is available: https://www.pcg-random.org/download.html.

请注意，该网站声称，PCG的输出比其他PRNG的输出更难预测，这意味着PCG更安全。 It is possible to predict some generators after only three outputs, so it should not be considered "hard to break" and definitely not "more secure". “非”加密安全PRNG的可预测性通常不是问题。

xoshiro系列

和PCG一样，xoshiro和相关的xoroshiro家族也是相当新的PRNG。

搞一个自创的

如果你仍然不满意，你可能想建立自己的PRNG。 你可以通过编写一些看起来不错的东西，并将其置于自动化的统计测试套件（如TestU01的SmallCrush中，依次Crush，BigCrush。 这些测试非常容易运行，可以快速指出问题，例如： 

#include <unif01.h>
#include <bbattery.h>

#include <stdint.h>

static uint32_t next = 1;
unsigned int custom_rand(void) {
    // This is a terrible generator!
    next = (next * 0x4B4B9656U) ^ (next * 0x565AC3C3U) + 1;
    return next * (next - 1);
}

int main(void) {
    unif01_Gen *gen = unif01_CreateExternGenBits("custom_rand", custom_rand);
    bbattery_SmallCrush(gen);  //或者bbattery_Crush，bbattery_BigCrush
    unif01_DeleteExternGenBits(gen);
}

SmallCrush将报告该生成器在15次统计测试中有12次失败。 因此，也不需要进行其他速度慢得多的测试。

取自“http://wiki.foofun.cn//index.php?title=Random_Number_Generator&oldid=689”