密码安全的随机数生成器是如何工作的?

我了解标准随机数发生器是如何工作的。 但是在使用低温摄影术时,随机数真的必须是随机的。

我知道有些仪器会读取宇宙白噪声来帮助生成安全的哈希值,但是您的标准PC没有这个function。

一个密码安全的随机数生成器如何获得其值不可重复的模式?

一个密码安全的随机数生成器,就像你可能用来生成encryption密钥一样,通过从其他人无法观察到的来源收集熵(即不可预知的input)来工作。

例如,Linux上的/ dev / random(4)从硬件返回数据,按键和传入networking数据包等硬件中断的时间变化中收集信息。 这种方法是安全的,只要内核不会高估它收集的熵。 几年前,来自各种不同来源的熵估计都减less了,使得它们更加保守。 这里是对Linux如何估计熵的解释 。

以上都不是特别高的吞吐量。 / dev / random(4)可能是安全的,但是一旦不能确定数据是否安全随机,拒绝发送数据就保证了安全。 例如,如果你想要生成大量的密钥和随机数,那么你可能会想使用硬件随机数生成器。

通常,硬件RNG是针对一对振荡器之间的差异而devise的,这些振荡器以接近相同的速度运行,但其速率根据热噪声稍微变化。 如果我没有记错的话,用于英国高级债券彩票的随机数发生器ERNIE就是这样工作的。

替代scheme包括在CCD(见lavaRND ),放射性衰减(参见hotbits )或大气噪声(参见random.org ,或者只是将调频到电台以外的某个地方插入声卡 )中的噪声采样 。 或者,你可以直接要求电脑的用户像疯狂的黑猩猩一样在键盘上敲打一分钟,无论是漂浮在你的船上。

对于内联链接缺乏抱歉,但显然我必须在我被允许发布更多内容之前,在本网站上烧尽更多。

编辑:保护。 因为有些人对这袋骨头很好,左边点击那个向上的东西,我显然可以把其余的链接放到现在。 谢谢你仁慈的人! ^ _ ^

编辑:正如安德拉斯指出的,我只想到谈一些最常见的熵收集计划。 Thomas Pornin的回答和JohannesRössel的回答都做了很好的工作,解释了如何去处理聚集的熵,以便再次处理这些熵。

为了encryption的目的,所需要的是该stream应该“在计算上与一致随机比特不可区分”。 “计算地”意味着它不需要是真正的随机的,只有在没有上帝自己的计算机的情况下才会出现。

实际上,这意味着系统必须首先收集n个真正随机位的序列。 n必须足够大以阻止穷举search,即尝试n位的所有2 ^ n个组合将是不可行的。 对于当今的技术来说,只要n大于90即可,但密码员只是两个幂,所以习惯上使用n = 128

这些n个随机位是通过收集“物理事件”来获得的,这些物理事件应该是不可预知的。 通常情况下,使用计时:CPU有一个循环计数器,每秒钟更新数十亿次,有些事件发生不可避免的抖动量(传入networking数据包,鼠标移动,击键…)。 系统对这些事件进行编码,然后通过应用诸如SHA-256的encryption安全散列函数(输出被截断以产生n位)来“压缩”它们。 这里重要的是物理事件的编码具有足够的 :粗略地说,所述事件可以共同假定至less2 ^ n个组合。 根据其定义,散列函数应该很好地把熵集中到一个n位的string中。

一旦我们有了n个比特,我们使用一个PRNG(伪随机数发生器)来根据需要发出尽可能多的比特。 如果PRNG假设它在足够宽的未知n比特密钥上操作,其输出在计算上与均匀随机比特不可区分,则称PRNG是密码安全的。 在90年代,一个stream行的select是RC4 ,这是非常简单的实施,并且相当快。 然而,结果却是有可测量的偏差,也就是说,并不像最初所希望的那样难以区分。 eSTREAM项目包括为PRNG收集更新的devise(实际上是stream密码,因为大多数stream密码都是PRNG,输出与要encryption的数据进行异或运算),logging这些密码并促进密码学家进行分析。 eSTREAM Portfolio包含7个被认为足够安全的PRNGdevise(即他们抵制分析,密码学家倾向于很好地理解他们为什么抵制)。 其中,四个是“软件优化”。 好消息是,虽然这些新的PRNG似乎比RC4更安全,但它们也明显更快(我们正在这里讨论每秒数百兆字节)。 其中三个是“免费使用”,并提供源代码。

从devise的angular度来看,PRNG重用了分组密码的许多元素。 使用雪崩和扩散比特进入宽内部状态的相同概念。 或者,可以用分组密码build立一个像样的PRNG:简单地使用n位序列作为分组密码的密钥,并且encryption计数器的连续值(表示为m位序列,如果分组密码使用m-位块)。 只要分组密码是安全的,并且产生的stream不超过m×2 ^(m / 2)位(对于m = 128 ,则这产生了一个伪随机的比特stream,其在计算上与随机不可区分意味着大约300亿千兆字节,因此对于大多数用途而言足够大)。 这种用法被称为计数器模式(CTR) 。

通常,CTR模式下的分组密码不如专用stream密码那么快(stream密码的点在于,通过丧失分组密码的灵活性,预期性能更好)。 但是,如果您恰好有英特尔最新的CPU之一的AES-NI指令(基本上是硬件上的AES实现,集成在CPU中),那么使用CTR模式的AES将产生无与伦比的速度(每个数千兆字节第二)。

首先,密码安全PRNG的重点不是产生完全不可预知的序列。 正如你所指出的,没有产生大量的(或多或less)真正的随机性1的东西使得这是不可能的。

所以你诉诸于一些难以预测的东西。 这里的“硬”意味着无论如何,需要的时间不可避免地会花费过多时间。 有一些mathalgorithm在这方面发挥作用 – 如果你拿一些知名的CSPRNG并看看它们是如何工作的,你可以看一看。

build立这样一个PRNG最常见的变种是:

  • 使用已经输出(假定是安全的)伪随机比特stream的stream密码。
  • 在计数器模式下使用分组密码

计数器上的散列函数有时也被使用。 维基百科有更多这方面的内容 。

一般要求只是从发生器的位stream中确定原始的初始化向量是不可行的,并且下一位不容易预测。

就初始化而言,大多数CSPRNG使用系统中可用的各种源,范围从真正的随机事件,例如系统噪声,中断或系统中的其他事件,到某些存储位置等其他事物。 初始化向量最好是非常随机的,不依赖于mathalgorithm。 这个初始化在Debian的OpenSSL实现中被打破了一段时间,导致了严重的安全问题。


1这也有其问题,因为热噪声等因温度不同而具有不同特性,所以必须小心消除偏差,因此几乎总是有偏差,需要消除偏差。 而这本身并不是一件微不足道的任务。

为了使随机数发生器被认为是密码安全的 ,需要防止知道该algorithm的对手的攻击和(大量的)先前产生的比特的攻击。 这意味着具有这些信息的人不能重构发生器的任何隐藏的内部状态,并且预测接下来的比特产生的精度将高于50%。

普通的伪随机数发生器通常不具有密码安全性,因为从先前的输出位重构内部状态通常是微不足道的(通常,整个内部状态只是直接产生的最后N位)。 任何没有良好统计特性的随机数发生器也不是密码安全的,因为即使不知道内部状态,其输出至less是可预测的。

所以,至于它们是如何工作的,任何好的encryption系统都可以用作密码安全的随机数生成器 – 使用encryption系统来encryption“普通”随机数生成器的输出。 由于攻击者不能重build普通随机数发生器的明文输出,所以他不能直接攻击它。 这是一个有点循环的定义,它引发了你如何密钥encryption系统来保证安全的问题,这是另外一个问题。

每个生成器将使用自己的种子策略,但是这里有一点来自CryptGenRandom的Windows API文档

使用Microsoft CSP,CryptGenRandom使用其他安全组件使用的相同的随机数生成器。 这使得许多stream程可以为全系统种子做出贡献。 CryptoAPI为每个用户存储一个中间随机种子。 为了形成随机数发生器的种子,调用应用程序提供可能具有的位(例如,鼠标或键盘定时input),然后将其与存储的种子以及各种系统数据和用户数据(例如进程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缓冲区的步骤是可以接受的。