随机性、熵与随机数生成器:解析伪随机数生成器（PRNG）和真随机数生成器（TRNG）

本文4000字，建议阅读8分钟
本文介绍伪随机数生成器(PRNG)和真随机数生成器。

随机性的定义

随机性是指一系列事件或结果中不存在任何可预测模式或顺序。真正的随机性难以实现,特别是在计算机这样的确定性系统中,因为它们遵循特定的指令运行。在数学和计算领域,随机性对于实现无偏采样、密码安全以及确保模拟和随机化算法等过程的不可预测性至关重要。

随机性可分为以下两类：

• 确定性随机性:由已知过程(如算法)生成,但呈现出随机特征。

• 非确定性随机性:由自然界中不可预测的过程(如放射性衰变或大气噪声)产生。

熵的理解

熵衡量了系统中的不可预测性或随机性程度。在信息论中,熵量化了一个序列所包含的信息量,通常与无序程度相关。熵值越高,意味着不可预测性越强。

熵的关键概念:

香农熵:度量随机变量可能取值的平均不可预测性。其计算公式为:

其中p(x_i)表示每个可能结果x_i的概率。

熵源:物理过程(如放射性衰变、热噪声)和计算方法(如哈希函数、系统状态)可作为熵源,在生成密码密钥时尤其重要。

对于安全性和不可预测性要求极高的应用,如密码学,高熵至关重要。低熵可能会暴露某些模式,使系统容易受到攻击。

随机数生成器(RNG)概述

随机数生成器(RNG)是能够生成无特定模式数字序列的算法或硬件系统。主要有两类RNG:

• 伪随机数生成器(PRNG):通过算法方法生成看似随机但实际上具有确定性的数字序列。

• 真随机数生成器(TRNG):利用物理现象,通过硬件方法产生真正不可预测的随机数序列。

伪随机数生成器(PRNG)

PRNG采用数学算法生成看似随机但实为确定性的数字序列。PRNG由一个"种子"值初始化,如果给定相同的种子,它们总是产生相同的序列。

PRNG的特点:

• 确定性:对于相同的种子值,PRNG将始终生成相同的序列。

• 高效性:PRNG能够快速生成大量随机值。 

• 周期性:PRNG序列最终会在一定周期后重复,不过现代PRNG算法的周期非常长。

除上述特点外,PRNG还具有以下优点:

• 可重现性:由于PRNG的确定性,可以方便地重现特定的随机数序列,这在某些应用中非常有用,如调试、测试和科学模拟等。

• 可并行化:PRNG算法通常易于并行化,可以在多核处理器或分布式系统上高效运行,从而进一步提高生成速度。

• 灵活性:PRNG算法的参数(如种子值、算法系数等)可以根据需要进行调整,以满足不同应用对随机性质量的要求。 

尽管PRNG具有诸多优点,但其确定性使其不适用于对不可预测性要求极高的场合,如密码密钥生成等。在这些领域,TRNG通常是更合适的选择。

常见的PRNG算法:

1、线性同余生成器(LCG):作为最古老、最简单的PRNG之一,LCG采用以下公式生成随机数序列:

其中:

• X_n表示当前随机值,

• a,c和m为常数参数,分别称为乘数、增量和模数。

LCG的优点在于实现简单、计算速度快,但其统计性质较差,不适合密码应用。

2、梅森旋转算法(Mersenne Twister):以其超长周期(约为2^19937−1)著称,MT算法被广泛应用于对随机数质量要求较高的领域。MT采用了一种基于矩阵线性递归的构造方法,具有良好的统计特性和高维均匀分布。

梅森旋转算法(Mersenne Twister)有一套复杂的数学公式。它基于矩阵线性递归,利用了有限二进制字段上的线性变换。但是在实现MT算法时,通常按照标准的描述来编程,无需从头推导这些公式，所以我们这里就不详细介绍了。

MT算法的突出优点在于其超长周期和高维均匀分布,这得益于其巧妙的数学构造。同时,MT也具有较高的生成速度和良好的统计学性质,因此被广泛应用于各种需要高质量随机数的领域。

3、Xorshift生成器:这类PRNG利用异或(XOR)和位移等位运算产生随机数序列。其优点是计算简洁高效,速度远超许多其他PRNG。Xorshift生成器的缺点是统计性质略逊于MT,但仍可满足一般应用需求。以下是Xorshift算法的通用公式:

Xorshift算法的优点在于其简洁、高效,仅需要很少的状态存储和计算操作就能生成质量尚可的伪随机数序列。但它的统计性质略逊于梅森旋转等更复杂的算法。在对随机性要求较高的场合,通常会选用Xorshift*或其他改进版本。

4、密码学PRNG(CSPRNG):密码学伪随机数生成器(Cryptographically Secure Pseudo-Random Number Generator, CSPRNG)是一类特殊的伪随机数生成器,旨在生成具有很高安全性和不可预测性的随机数序列,使其能够安全地用于密码学应用。与一般的PRNG相比,CSPRNG必须满足更严格的安全性要求。

CSPRNG的主要特点包括:

1. 不可区分性:CSPRNG生成的随机数序列应当与真随机数序列在统计学上不可区分。即使攻击者获得了部分随机输出,也无法有效预测后续的随机数。

2. 不可预测性:攻击者即使知道CSPRNG的算法和部分状态信息,也无法以优于暴力搜索的效率预测后续输出。这是通过引入足够的熵(随机性)来实现的。

3. 备用安全性:即使CSPRNG的部分状态泄露或算法存在一定缺陷,仍能保证生成随机数的安全性。这通常通过积累熵池、重新密钥化等机制来实现。

为满足上述要求,CSPRNG通常基于安全的密码学原语构建,如:

• 分组密码:如AES、ChaCha20等,可用于构建伪随机函数(PRF)或伪随机置换(PRP)。

• 哈希函数:如SHA-2、SHA-3等,可用于熵萃取、密钥派生等。

• 消息认证码(MAC):如HMAC、CMAC等,可用于完整性验证和密钥生成。

常见的CSPRNG算法包括:

1. Fortuna:由Bruce Schneier等人设计,使用多个熵源来积累随机种子,并周期性地对种子进行重新密钥化。Fortuna广泛应用于开源操作系统和密码库中。

2. Yarrow:Fortuna的前身,也是一种积累熵的CSPRNG算法。Yarrow在MacOS、iOS等系统中使用。

3. CTR_DRBG:基于分组密码(如AES)的确定性随机比特生成器(Deterministic Random Bit Generator, DRBG),由NIST标准化。CTR_DRBG在Linux内核、OpenSSL等中使用。

4. HASH_DRBG和HMAC_DRBG:分别基于哈希函数和消息认证码的DRBG,也由NIST标准化。

5. ChaCha20:基于ChaCha20流密码的CSPRNG,可用于快速生成随机数。ChaCha20已被IETF标准化,并用于TLS协议等。

CSPRNG算法各自都有其独特的结构和流程,难以用一个通用公式来描述。CSPRNG与一般的PRNG相比,在种子管理、安全性分析等方面有更严格的要求,因此其算法结构往往也更为复杂。在实际应用中,应当选用经过充分安全性评估的标准CSPRNG算法,而非自行设计。

PRNG的应用场景:

• 模拟仿真:如蒙特卡罗方法、随机采样等。

• 游戏娱乐:游戏内事件和元素的随机生成。

• 统计抽样:随机选取数据样本进行分析。

尽管PRNG在诸多领域有着广泛应用,但其确定性的特点限制了它在安全关键场合(如密钥生成)中的使用。 

真随机数生成器(TRNG)

TRNG,即硬件随机数生成器,通过利用不可预测的物理过程产生真正随机的数字序列。与PRNG不同,TRNG无需种子,其生成的随机数完全独立于之前的输出值。

TRNG中的真随机性来源:

1. 放射性衰变:放射性物质以随机方式发射粒子,是可靠的熵源。

2. 热噪声:电子元件中普遍存在的热噪声可作为随机源。

3. 光子过程:光子在光学系统中的量子行为(如通过分束器)可用于提取随机性。

4. 大气噪声:由无线电或传感器采集的大气噪声变化是一种天然的不可预测随机源。

除上述物理过程外,TRNG还可利用其他量子效应,如光子纠缠、电子自旋等,进一步提高随机数的质量。

TRNG的特点:

• 非确定性:即使在相同初始条件下,TRNG生成的随机序列也不可重复。

• 生成速度限制:受物理过程的制约,TRNG的生成速率通常低于PRNG。

• 高熵输出:TRNG提供接近完全随机的高熵数据,非常适合安全关键应用。

TRNG的应用领域:

• 密码学:生成加密密钥、初始化向量、会话令牌等。 

• 科学实验:在采样或实验设置中需要高度不可预测性的场合。

• 博彩业:确保游戏结果的公平性和不可预知性。

尽管TRNG具有高安全性的优点,但其生成速度和实现成本通常高于PRNG。因此,TRNG主要用于对随机数绝对不可预测性有严格要求的应用中。

PRNG与TRNG的比较

确定性

• PRNG:具有确定性,即使用相同种子初始化时,会产生相同的随机序列。

• TRNG:非确定性,依赖于不可预测的物理过程。

速度性能

• PRNG:生成速度快,能够快速产生大量随机数。

• TRNG:受物理过程限制,生成速率通常低于PRNG。

实现复杂度

• PRNG:基于数学算法,通过软件实现。

• TRNG:依赖专用硬件,从物理源中提取熵。

周期性

• PRNG:具有固定周期,最终会重复,周期长度取决于算法。

• TRNG:无周期性,每个随机值都独立生成。

熵的质量

• PRNG:熵的质量取决于算法和种子,通常为中等水平。

• TRNG:能够提供高质量熵,生成全真随机数,适合安全关键应用。

应用场景

• PRNG:广泛应用于对效率要求较高的领域,如仿真、游戏和统计抽样等。

• TRNG:主要用于密码学和安全系统等对不可预测性要求极高的场合。

可预测性

• PRNG:当种子已知时,输出可被预测,因此不适合密码应用。

• TRNG:依赖自然熵源,输出不可预测。

需要指出的是,在实际应用中,PRNG和TRNG并非完全对立,它们常常协同使用以发挥各自的优势。例如,可用TRNG产生高熵种子,再用其初始化PRNG以提高生成速率。通过恰当结合两者,可在保证安全性的同时兼顾效率。

PRNG与TRNG的协同应用

现代随机数解决方案通常采用PRNG和TRNG相结合的混合架构,以期兼具速度和安全性。一种常见做法是利用TRNG产生高熵种子,再用其初始化密码学安全的PRNG。这样,既可从TRNG获得高质量熵,又能发挥PRNG的高速生成能力,是密码通信等安全关键应用的理想方案。

随机数生成面临的挑战与思考

1. 熵估计困难:评估TRNG产生随机数的质量可能面临挑战,需采用统计学检测以确保熵足够。

2. 潜在安全隐患:对于PRNG,不当的种子选取可能导致可预测性,从而危及密码应用安全。而TRNG硬件的缺陷则可能产生有偏差的随机数。

3. 速度与质量的权衡:TRNG提供优质随机源,但生成速率较低;PRNG具有高速优势,但可能不及TRNG般不可预测。如何平衡二者是一大挑战。

4. 严格测试与验证:无论是PRNG还是TRNG,其随机性都需经过严格的统计学检验,如NIST SP800-22随机性测试标准等,以保证随机数序列的质量。 

此外,随机数生成技术的发展还面临其他机遇与挑战:

• 后量子密码学:随着量子计算的发展,传统密码体制面临严峻挑战。后量子密码算法(如格基密码、哈希签名等)对随机数质量提出了更高要求,亟需发展更安全高效的随机源。

• 机器学习中的随机性:随机性在机器学习中扮演重要角色,如随机梯度下降、Dropout正则化等。开发适合机器学习场景的专用随机数生成器,对提升模型性能意义重大。

• 随机性的理论研究:随机性的本质一直是基础科学的研究热点。从算法复杂性到量子物理,从混沌动力学到生物学,随机性无处不在。深入探讨随机性的理论基础,有助于指导随机技术的创新发展。

随机性、熵和随机数生成器是密码学、安全系统等领域的核心概念。理解其内涵对设计和实现安全可靠的应用至关重要。PRNG凭借高效易用的特点,在仿真、游戏等领域得到广泛应用;而TRNG以其高熵、不可预测等优势,成为密码学不可或缺的随机源。在现实中,二者常常协同使用,以期在安全与效率间求得平衡。未来,随着信息安全、人工智能等领域的快速发展,随机技术必将迎来更多的机遇与挑战。