我理解标准随机数生成器如何工作.但是当使用crytpography时,随机数确实必须是随机的.
我知道有些仪器可以读取宇宙白噪声以帮助产生安全的哈希值,但是你的标准PC没有这个.
加密安全随机数生成器如何在没有可重复模式的情况下获取其值？
正如您可能用于生成加密密钥的加密安全数字随机生成器一样,通过从其他人无法观察到的源收集熵(即不可预测的输入)来工作.
例如,Linux上的/ dev/random(4)从硬件中断的时序变化中收集信息,例如硬盘返回数据,按键和传入网络数据包.这种方法是安全的,只要内核不会高估它收集了多少熵.几年前,来自各种不同来源的熵估计都减少了,使得它们更加保守.以下是Linux估算熵的解释.
以上都不是特别高的吞吐量./ dev/random(4)可能是安全的,但是一旦无法确定数据是否安全随机,它就会通过拒绝提供数据来维护安全性.例如,如果您想生成大量加密密钥和随机数,那么您可能需要使用硬件随机数生成器.
硬件RNG通常设计为从一对振荡器之间的差异中采样,这对振荡器以接近相同的速度运行,但其速率根据热噪声稍微变化.如果我没记错的话,用于英国优质债券彩票的随机数发生器ERNIE就是这样做的.
替代方案包括对CCD上的噪声进行采样(参见lavaRND),放射性衰变(参见hotbits)或大气噪声(请参阅random.org,或者只是将调谐到某个地方以外的AM收音机插入声卡).或者你可以直接让电脑的用户敲打他们的键盘就像一只疯狂的黑猩猩一会儿,不管你的船是什么漂浮.
正如andras指出的那样,我只想谈谈一些最常见的熵收集方案.Thomas Pornin的回答和JohannesRössel的答案都做了很好的工作,解释了人们如何能够修复聚集的熵,以便再次提出一些问题.
出于加密目的,需要的是流应"在计算上与均匀随机比特无法区分"."计算"意味着它不需要是真正随机的,只有在没有访问上帝自己的计算机的情况下才会出现.
实际上,这意味着系统必须首先收集n个真正随机位的序列.n应足够大以阻止穷举搜索,即尝试n位的所有2 ^ n组合是不可行的.就今天的技术而言,只要n大于90左右,就可以实现这一点,但密码学家只喜欢2的幂,所以习惯上使用n = 128.
这些n个随机比特是通过收集"物理事件"获得的,就物理学而言,这些事件应该是不可预测的.通常,使用时序:CPU有一个周期计数器,每秒更新数十亿次,有些事件发生不可避免的抖动量(传入网络数据包,鼠标移动,击键......).系统对这些事件进行编码,然后通过应用加密安全散列函数(例如SHA-256)来"压缩"它们(然后截断输出以产生我们的n位).这里重要的是物理事件的编码具有足够的熵:粗略地说,所述事件可以共同假设至少2 ^ n个组合.根据其定义,散列函数应该很好地将该熵集中到n位字符串中.
一旦我们有n位,我们使用PRNG(伪随机数发生器)根据需要产生多少位.如果PRNG假设它在足够宽的未知n位密钥上操作,则其输出在计算上与均匀随机位无法区分,则称其为加密安全的.在90年代,一个流行的选择是RC4,它实现起来非常简单,速度非常快.然而,事实证明它具有可测量的偏差,即它并不像最初所希望的那样难以区分.该eSTREAM项目包括在收集新的设计为PRNG(实际上流密码,因为大多数流密码组成的PRNG,其输出与数据异或加密),记录它们,并通过密码破译促进分析.eSTREAM产品组合包含七个PRNG设计,这些设计被认为足够安全(即他们拒绝分析,密码学家倾向于很好地理解他们抵抗的原因).其中,四个是"针对软件进行优化".好消息是虽然这些新的PRNG似乎比RC4更安全,但它们也明显更快(我们这里谈论的是每秒数百兆字节).其中三个"免费使用",并提供源代码.
从设计的角度来看,PRNG重用了分组密码的大部分元素.使用相同的雪崩和比特扩散到宽内部状态的概念.或者,可以从分组密码构建一个不错的PRNG:简单地使用n位序列作为密钥进入分组密码,并加密计数器的连续值(如果分组密码使用m,则表示为m位序列-位块).这产生了伪随机比特流,只要分组密码是安全的,并且产生的流不长于m*2 ^(m/2)比特(对于m = 128,这,这在计算上无法与随机区分)意味着大约300亿千兆字节,这对于大多数用途来说足够大了).这种用法称为计数器模式(CTR).
通常,CTR模式下的分组密码不如专用流密码快(流密码的点是,通过丧失分组密码的灵活性,预期会有更好的性能).但是,如果您碰巧拥有来自英特尔的最新CPU之一的AES-NI指令(基本上是硬件中的AES实现,集成在CPU中),那么具有CTR模式的AES将产生无与伦比的速度(几千兆字节/第二).
首先,加密安全PRNG的要点不是产生完全不可预测的序列.正如您所指出的那样,缺少产生大量(或多或少)真实随机性的东西1使得这是不可能的.
所以你选择的东西很难预测."硬"在这里意味着,无论如何,无论何时需要它都会花费不可思议的长时间.有许多数学算法可以参与其中 - 如果您采用一些着名的CSPRNG并查看它们的工作原理,您可以一瞥.
构建此类PRNG的最常见变体是:
使用流密码,其已经输出(假定安全的)伪随机比特流.
在计数器模式下使用分组密码
有时也使用计数器上的哈希函数.维基百科对此有更多了解.
一般要求只是从发生器的比特流确定原始初始化向量并且不能容易地预测下一个比特是不可行的.
至于初始化,大多数CSPRNG使用系统上可用的各种源,范围从线路噪声,中断或系统中的其他事件等真正随机的事物到某些存储器位置等其他事物.初始化矢量最好是随机的,不依赖于数学算法.在Debian的OpenSSL实现中,这种初始化被破坏了一段时间,这导致了严重的安全问题.
1哪个也存在问题,必须小心消除偏差,因为热噪声等因素根据温度而有不同的特性 - 你几乎总是有偏见并需要消除它.这本身并不是一项微不足道的任务.
为了使随机数发生器被认为是加密安全的,需要确保防止知道该算法的对手和(大量)先前生成的比特的攻击.这意味着拥有该信息的人无法重建任何隐藏的生成器内部状态,并预测下一个生成的内容将具有超过50%的准确度.
普通的伪随机数发生器通常不是加密安全的,因为从先前输出的比特重建内部状态通常是微不足道的(通常,整个内部状态只是直接产生的最后N个比特).任何没有良好统计特性的随机数发生器也不具有加密安全性,因为即使不知道内部状态,其输出至少也是可预测的.
因此,关于它们如何工作,任何好的加密系统都可以用作加密安全的随机数发生器 - 使用加密系统来加密"正常"随机数发生器的输出.由于攻击者无法重建普通随机数发生器的明文输出,因此无法直接攻击它.这是一个有点循环的定义,这引出了如何密钥加密系统以保证其安全的问题,这是另一个问题.
每个生成器都将使用自己的种子策略,但这里有一些来自CryptGenRandom上的Windows API文档
使用Microsoft CSP,CryptGenRandom使用其他安全组件使用的相同随机数生成器.这允许许多过程对系统范围的种子做出贡献.CryptoAPI为每个用户存储一个中间随机种子.为了形成随机数生成器的种子,调用应用程序提供它可能具有的位 - 例如,鼠标或键盘定时输入 - 然后将其与存储的种子和各种系统数据以及用户数据(例如进程ID和线程ID,系统时钟,系统时间,系统计数器,内存状态,可用磁盘集群,散列用户环境块.该结果用于对伪随机数发生器(PRNG)进行种子处理.
在带有Service Pack 1(SP1)及更高版本的Windows Vista中,使用NIST特殊出版物800-90中指定的基于AES计数器模式的PRNG的实现.在Windows Vista,Windows Storage Server 2003和Windows XP中,使用联邦信息处理标准(FIPS)186-2中指定的PRNG.如果应用程序可以访问一个好的随机源,它可以在调用CryptGenRandom之前用一些随机数据填充pbBuffer缓冲区.然后,CSP使用此数据进一步随机化其内部种子.在调用CryptGenRandom之前省略初始化pbBuffer缓冲区的步骤是可以接受的.
京公网安备 11010802040832号 | 京ICP备19059560号-6 