随机性、熵与随机数生成器:解析伪随机数生成器(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

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/461996.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

从零开始点亮一个LED灯 —— keil下载、新建工程、版本烧录、面包板使用、实例代码

一、keil下载 参考视频:Keil5安装教程视频 (全套资料51和32皆可用Keil5编译设置)_哔哩哔哩_bilibili 视频内容包括下载链接、安装教程、库导入,非常详细! 二、新建工程 2.1.使用stm32CubeMX新建工程 10. 使用STM32CubeMX新建工程 — [野…

嵌入式硬件电子电路设计(三)电源电路之负电源

引言:在对信号线性度放大要求非常高的应用需要使用双电源运放,比如高精度测量仪器、仪表等;那么就需要给双电源运放提供正负电源。 目录 负电源电路原理 负电源的作用 如何产生负电源 负电源能作功吗? 地的理解 负电压产生电路 BUCK电…

互斥量的使用

官方的描述 互斥量主要是对于共享资源的保护 其中参数要注意 osMutexRecursive://递归互斥量 互斥锁嵌套属性,同一个线程可以在不锁定自身的情况下多次使用互斥锁。每当拥有互斥锁的线程获得互斥锁时,锁计数就会增加。互斥锁也必须被释放多次…

商务英语学习柯桥学外语到泓畅-老外说“go easy on me”是什么意思?

在口语中“go easy on sb ”这个短语是很常见的 01 go easy on me 怎么理解? 在口语中,“go easy on me”是一个非常常见的表达,通常表示请求对方在某方面对自己宽容一些,不要对自己太过苛刻或严厉。 短语(go&#xff…

vscode在cmake config中不知道怎么选一个工具包?select a kit

vscode在cmake config中不知道怎么选一个工具包,或者发现一直在用VS的工具包想换成自己的工具包。select a kit vscode在cmake config中不知道怎么选一个工具包,或者发现一直在用VS的工具包想换成自己的工具包。select a kit 1.在VSCode中 按ctrlshift…

SpringBoot【实用篇】- 热部署

文章目录 目标:1.手动启动热部署2.自动启动热部署4.禁用热部署 目标: 手动启动热部署自动启动热部署热部署范围配置关闭热部署 1.手动启动热部署 当我们没有热部署的时候,我们必须在代码修改完后再重启程序,程序才会同步你修改的信息。如果我们想快速查…

AI 原生时代,更要上云:百度智能云云原生创新实践

本文整理自百度云智峰会 2024 —— 云原生论坛的同名演讲。 我今天分享的主题,是谈谈在云计算和 AI 技术快速发展和深入落地的背景下,百度智能云在云原生的基础设施产品和技术层面做的一些创新实践。 毋庸置疑,过去十几年云计算和 AI 技术是…

Java项目实战II基于Java+Spring Boot+MySQL的植物健康系统(开发文档+数据库+源码)

目录 一、前言 二、技术介绍 三、系统实现 四、文档参考 五、核心代码 六、源码获取 全栈码农以及毕业设计实战开发,CSDN平台Java领域新星创作者,专注于大学生项目实战开发、讲解和毕业答疑辅导。获取源码联系方式请查看文末 一、前言 基于Java、…

BGP路径属性与路由反射器

前言 IBGP水平分割规则用于防止AS内部产生环路,在很大程度上杜绝了IBGP路由产生环路的可能性,但是同时也带来了新的问题:BGP路由在AS内部只能传递一跳,如果建立IBGP对等体全互联模型又会加重设备的负担。 BGP 路径属性 AS_Path …

uniapp学习(010-2 实现抖音小程序上线)

零基础入门uniapp Vue3组合式API版本到咸虾米壁纸项目实战,开发打包微信小程序、抖音小程序、H5、安卓APP客户端等 总时长 23:40:00 共116P 此文章包含第113p的内容 文章目录 抖音小程序下载抖音开发者工具先去开发者工具里进行测试 抖音开放平台配置开始打包上传…

无线基础配置

配置图 各部分配置 AC1 vlan b [AC6605]vlan batch 10 20 100 Info: This operation may take a few seconds. Please wait for a moment...done. [AC6605]int [AC6605]interface g [AC6605]interface GigabitEthernet 0/0/2 [AC6605-GigabitEthernet0/0/2]port …

影刀RPA实战:识别简单计算验证码

1.官方计算验证码 基于影刀AI引擎的验证码识别指令,该指令不是长期免费,有一定的免费额度,用完之后需要我们到影刀官方充值。 上图使我们要识别的计算验证码 影刀指令代码: 配置我们选择计算题,文件路径本次指定本地…

HarmonyOS:UIAbility组件概述

一、概述 UIAbility组件是一种包含UI的应用组件,主要用于和用户交互。 UIAbility的设计理念: 原生支持应用组件级的跨端迁移和多端协同。支持多设备和多窗口形态。 UIAbility划分原则与建议: UIAbility组件是系统调度的基本单元&#xff0c…

单链表的基本操作实现

定义 链表节点长这个样子,数据域data指针域next指向下一个结点 typedef struct lnode {int data;struct lnode *next; }lnode ,*linklist; 初始化 /*初始化*/ linklist f1(){linklist l(linklist)malloc(sizeof(lnode));l->nextNULL;return l; }int main(){l…

C++ 优先算法——复写零(双指针)

目录 题目:复写零 1. 题目解析 2. 算法原理 一. 先找到最后一个“复写”数 处理边界情况 二. 复写操作 3. 代码实现 题目:复写零 1. 题目解析 题目截图: 该题目要求的与移动零相似,都要在一个数组上进行操作,…

使用linuxdeployqt打包Qt程序问题及解决方法

dpkg: 处理归档 libmysqlclient18_5.6.25-0ubuntu1_amd64.deb (--install)时出错: 预依赖问题 - 将不安装libmysqlclient18:amd64 在处理时有错误发生: libmysqlclient18_5.6.25-0ubuntu1_amd64.deb下载libmysqlclient18/5.6.25 libmysqlclient18/5.6…

配置BGP与IGP交互和路由自动聚合示例

组网需求 如图所示,用户将网络划分为AS65008和AS65009,在AS65009内,使用IGP协议来计算路由(该例使用OSPF做为IGP协议)。要求实现两个AS之间的互相通信。 配置思路 采用如下的思路配置BGP与IGP交互: 在AR…

基于SpringBoot的健身房系统的设计与实现(源码+定制+开发)

博主介绍: ✌我是阿龙,一名专注于Java技术领域的程序员,全网拥有10W粉丝。作为CSDN特邀作者、博客专家、新星计划导师,我在计算机毕业设计开发方面积累了丰富的经验。同时,我也是掘金、华为云、阿里云、InfoQ等平台…

flex 布局比较容易犯的错误 出现边界超出的预想的情况

flex 布局比较容易犯的错误 出现边界超出的预想的情况 如图 当使用flex布局时,设置flex:1 或者是flex:x 时 如果没有多层嵌套的flex布局,内容超出flex:1规定的后,仍然会撑大融器 在flex:1 处设置 overflow:hidden 即可超出后不显…

vscode | 开发神器vscode快捷键删除和恢复

目录 快捷键不好使了删除快捷键恢复删除的快捷键 在vscode使用的过程中,随着我们自身需求的不断变化,安装的插件将会持续增长,那么随之而来的就会带来一个问题:插件的快捷键重复。快捷键重复导致的问题就是快捷键不好使了&#xf…