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

本文涉及的产品
检索分析服务 Elasticsearch 版,2核4GB开发者规格 1个月
实时计算 Flink 版,5000CU*H 3个月
智能开放搜索 OpenSearch行业算法版,1GB 20LCU 1个月
简介: 随机性在密码学、仿真和机器学习等领域中至关重要,本文探讨了随机性、熵的概念以及伪随机数生成器(PRNG)和真随机数生成器(TRNG)的原理和应用。PRNG通过算法生成看似随机的序列,适用于高效需求;TRNG利用物理过程生成真正随机数,适用于高安全需求。文章还讨论了两者的协同应用及其面临的挑战。

随机性在诸多领域中扮演着至关重要的角色,涵盖密码学、仿真和机器学习等方面。因为随机性为无偏决策、不可预测序列和安全加密提供了基础。然而生成随机数是一项复杂的任务,理解伪随机数生成(pseudo-random number generation, PRNG)与真随机数生成(true random number generation, TRNG)之间的区别至关重要。本文将探讨随机性、熵的概念以及不同类型随机数生成器(random number generator, RNG)的原理,重点介绍伪随机数生成器(PRNG)和真随机数生成器(TRNG)。

随机性的定义

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

随机性可分为以下两类:

  • 确定性随机性:由已知过程(如算法)生成,但呈现出随机特征。
  • 非确定性随机性:由自然界中不可预测的过程(如放射性衰变或大气噪声)产生。

熵的理解

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

熵的关键概念:

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

其中

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,cm为常数参数,分别称为乘数、增量和模数。

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_DRBGHMAC_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以其高熵、不可预测等优势,成为密码学不可或缺的随机源。在现实中,二者常常协同使用,以期在安全与效率间求得平衡。未来,随着信息安全、人工智能等领域的快速发展,随机技术必将迎来更多的机遇与挑战。

https://avoid.overfit.cn/post/7aefb302eacf4c85a387eec41abdb63e

目录
相关文章
|
17天前
|
存储 弹性计算 人工智能
阿里云Alex Chen:普惠计算服务,助力企业创新
本文整理自阿里云弹性计算产品线、存储产品线产品负责人陈起鲲(Alex Chen)在2024云栖大会「弹性计算专场-普惠计算服务,助力企业创新」中的分享。在演讲中,他分享了阿里云弹性计算,如何帮助千行百业的客户在多样化的业务环境和不同的计算能力需求下,实现了成本降低和效率提升的实际案例。同时,基于全面升级的CIPU2.0技术,弹性计算全线产品的性能、稳定性等关键指标得到了全面升级。此外,他还宣布了弹性计算包括:通用计算、加速计算和容器计算的全新产品家族,旨在加速AI与云计算的融合,推动客户的业务创新。
|
24天前
|
存储 人工智能 弹性计算
产品技术能力飞跃,阿里云E-HPC荣获“CCF 产品创新奖”!
9月24日,在中国计算机学会举办的“2024 CCF 全国高性能计算学术年会”中,阿里云弹性高性能计算(E-HPC)荣获「 CCF HPC China 2024 产品创新奖」。这也是继 2022 年之后,阿里云E-HPC 再次荣获此奖项,代表着阿里云在云超算领域的持续创新结果,其产品能力和技术成果得到了业界的一致认可。
|
8天前
|
SQL 人工智能 安全
【灵码助力安全1】——利用通义灵码辅助快速代码审计的最佳实践
本文介绍了作者在数据安全比赛中遇到的一个开源框架的代码审计过程。作者使用了多种工具,特别是“通义灵码”,帮助发现了多个高危漏洞,包括路径遍历、文件上传、目录删除、SQL注入和XSS漏洞。文章详细描述了如何利用这些工具进行漏洞定位和验证,并分享了使用“通义灵码”的心得和体验。最后,作者总结了AI在代码审计中的优势和不足,并展望了未来的发展方向。
|
3天前
|
负载均衡 算法 网络安全
阿里云WoSign SSL证书申请指南_沃通SSL技术文档
阿里云平台WoSign品牌SSL证书是由阿里云合作伙伴沃通CA提供,上线阿里云平台以来,成为阿里云平台热销的国产品牌证书产品,用户在阿里云平台https://www.aliyun.com/product/cas 可直接下单购买WoSign SSL证书,快捷部署到阿里云产品中。
1843 6
阿里云WoSign SSL证书申请指南_沃通SSL技术文档
|
2天前
|
存储 安全 Oracle
【灵码助力安全3】——利用通义灵码辅助智能合约漏洞检测的尝试
本文探讨了智能合约的安全性问题,特别是重入攻击、预言机操纵、整数溢出和时间戳依赖性等常见漏洞。文章通过实例详细分析了重入攻击的原理和防范措施,展示了如何利用通义灵码辅助检测和修复这些漏洞。此外,文章还介绍了最新的研究成果,如GPTScan工具,该工具通过结合大模型和静态分析技术,提高了智能合约漏洞检测的准确性和效率。最后,文章总结了灵码在智能合约安全领域的应用前景,指出尽管存在一些局限性,但其在检测和预防逻辑漏洞方面仍展现出巨大潜力。
|
6天前
|
Web App开发 算法 安全
什么是阿里云WoSign SSL证书?_沃通SSL技术文档
WoSign品牌SSL证书由阿里云平台SSL证书合作伙伴沃通CA提供,上线阿里云平台以来,成为阿里云平台热销的国产品牌证书产品。
1778 2
|
15天前
|
编解码 Java 程序员
写代码还有专业的编程显示器?
写代码已经十个年头了, 一直都是习惯直接用一台Mac电脑写代码 偶尔接一个显示器, 但是可能因为公司配的显示器不怎么样, 还要接转接头 搞得桌面杂乱无章,分辨率也低,感觉屏幕还是Mac自带的看着舒服
|
22天前
|
存储 人工智能 缓存
AI助理直击要害,从繁复中提炼精华——使用CDN加速访问OSS存储的图片
本案例介绍如何利用AI助理快速实现OSS存储的图片接入CDN,以加速图片访问。通过AI助理提炼关键操作步骤,避免在复杂文档中寻找解决方案。主要步骤包括开通CDN、添加加速域名、配置CNAME等。实测显示,接入CDN后图片加载时间显著缩短,验证了加速效果。此方法大幅提高了操作效率,降低了学习成本。
5113 15
|
9天前
|
人工智能 关系型数据库 Serverless
1024,致开发者们——希望和你一起用技术人独有的方式,庆祝你的主场
阿里云开发者社区推出“1024·云上见”程序员节专题活动,包括云上实操、开发者测评和征文三个分会场,提供14个实操活动、3个解决方案、3 个产品方案的测评及征文比赛,旨在帮助开发者提升技能、分享经验,共筑技术梦想。
1039 147
|
17天前
|
存储 缓存 关系型数据库
MySQL事务日志-Redo Log工作原理分析
事务的隔离性和原子性分别通过锁和事务日志实现,而持久性则依赖于事务日志中的`Redo Log`。在MySQL中,`Redo Log`确保已提交事务的数据能持久保存,即使系统崩溃也能通过重做日志恢复数据。其工作原理是记录数据在内存中的更改,待事务提交时写入磁盘。此外,`Redo Log`采用简单的物理日志格式和高效的顺序IO,确保快速提交。通过不同的落盘策略,可在性能和安全性之间做出权衡。
1583 12