13

我听说有人使用光传感器、盖革计数器和其他物理传感器来生成随机数，但我对此表示怀疑。真的有办法通过测量物理世界（使用 Arduino 或任何其他微控制器）来生成随机数吗？如果是这样，这些数字真的会是随机的吗？

澄清一下：问题是关于使用微控制器收集的数据生成随机数的可行性，这些随机数可以很好地应用于密码学——一种依赖设备熵的替代方案。

4

4 回答 4

22

进行模拟“真实世界”测量通常是熵的良好来源（又名真实随机数据）。模拟源总是会叠加一些不可预测的噪声，这些噪声可以被“捕获”。然而，如前所述，测量数据很少是无偏的。

模拟电气测量也可能或多或少容易受到无法控制的影响或什至来自外部的攻击，例如通过导致传感器饱和。EMI 也可能会干扰测量；在通话期间将普通手机放置在合理靠近电路的位置很可能会对任何模拟信号造成严重破坏。

偏见

无偏的、均匀分布的高熵数通常是人们想要的，因为它们的属性（而不是值）在某种程度上被归一化，因此可以更可靠地预测。

当以 10 位分辨率测量模拟输入时，理想情况下，从测量中收集的数字范围将涵盖从 0 到 1024 的所有值，并且每个值将以与该范围内的任何其他值相同的频率（或概率）出现。

实际上，这些值通常（或多或少）正态分布（高斯分布）围绕具有一些特征标准偏差的某个平均值，例如每个样本大约 500 @ 10 位。

去偏

因此，为了生成具有所需属性的随机值（见上文），需要进行一些去偏操作：需要某种随机提取器。

使用加密函数，如（单向）哈希函数或密码算法，通常也很容易产生所需的结果；但是这是有代价的：这些功能的“混合”在设计上非常强大，这使得在转换后无法确定源数据的质量（=随机性）。即使是最简单的确定性值序列（例如 {1,2,3,4,5...}全部。

在 µC 上生成熵

定时

在微控制器环境中，很少想到的一个很好的熵来源是事件的时间。使用高速计时器，可以通过读取计时器值以响应某些异步事件来收集真正的熵。这种与运行定时器无关的事件可能是用户按下按钮、另一个（子）系统或 IC 启动的通信开始，或者基本上任何其他未由 µC 触发的事件（或任何同步子系统）本身。

事实上，熵甚至可以从两个独立的时钟源中获取。例如，通过另一个时钟对一个时钟的计时周期进行计时。这为 Atmel AVR µC（在 Arduino 中使用）打开了几个非常有趣的可能性，具体取决于 µC 的功能：

  • 大多数 AVR 都有内部 EEPROM 存储器。对此存储器的写操作由独立于主系统时钟的专用定时器定时（-据报道有一些芯片（不是类型！）测量表明情况可能并非如此）（编辑：请注意，在某些 AVR , 以ATTiny25/45/85为例，EEPROM时序来源于内部RC振荡器，因此当该振荡器也被选为系统时钟源时，不会采集熵）；这可能取决于主时钟源（内部 R/C 与外部晶体/谐振器）。因此，相对于主系统时钟，在写入 EEPROM 所需的时间内，预计会有一些（真正随机的）抖动，这又可以通过高速定时器/计数器来测量。

  • 较新的 AVR 能够让看门狗定时器产生软件中断而不是硬件复位。看门狗定时器设计为由其自己的独立时钟源控制，从而产生可以测量的相对抖动。

  • 许多 AVR 能够使用外部 32kHz 晶振为专用定时器/计数器提供时钟，以提高实时测量的准确性。这个外部晶体是与主时钟不相关的另一个事件源。（否则一开始多出来的水晶就没用了……）

后者似乎很有希望，因为它具有相对较高带宽的潜力：当使用运行速度明显更快的系统定时器对每个 32kHz 时钟周期进行计时时（在当前的 AVR @ 20 MHz 上可以实现 600+ 的因子！）并且保守地假设只有 1 位每次测量的熵，这会导致每秒 32000+ 位的熵——远远超过一个 µC 本身消耗的量。

编辑：同时，我对 32kHz 定时器方法进行了一些简单的测试，短期结果似乎质量很低。每个样本生成的熵的上限似乎非常低，而我什至没有测试样本是否存在源自或多或少规则相移的非明显模式。这个结果可能是由于我的 DUT 的主时钟由外部晶体驱动，当在有限的时间范围内观察时，可以预期（在测量精度范围内）与 32kHz 石英的频率一样稳定。延长两个样本之间的时间（分钟？）可能会返回良好的熵，但带宽非常低。（注：

编辑#2：我的 DUT（ATmega1284）的内部 RC 振荡器似乎产生了显着的频率抖动（几 kHz/s）；当由外部 32kHz 晶体定时时，在这个振荡器上运行确实似乎产生了相当多的熵 (kBits/s)。

在一个小实验中，我最近研究了前两种方法。在我的 DUT 上，EEPROM 时序通常比 WDT 更有利：

对 EEPROM 写入进行计时，每次写入操作产生约 4.82 位的熵，而看门狗定时器在频率方面似乎更稳定，每次看门狗超时产生约 3.92 位。此外，EEPROM 的写入时间看起来更加平滑高斯分布，而 WDT 的分布似乎有些不对称并且有很多像差。

注意：为单个熵测量聚合多个“随机”事件实际上可能会降低获得的熵：源中快速的随机波动可能会部分地相互补偿，从而产生与平均值偏差较小的结果值。因此，例如，在同一时间进行 32k 次定时（晶体的每个周期一个），可以预期一个实时秒（RTC 晶体的 32k 周期）会产生更多的熵，而不是定时。

未初始化的内存

Avr-gcc 编译的应用程序通常在执行用户代码之前将整个片上 RAM 清除为 0x00，即main(). 将代码放入早期.init部分可以在原始未初始化 RAM 内容被 gcc 的初始化例程覆盖之前访问它。

由于 RAM 的物理存储单元（位）的微小差异以及取决于一些真正的随机热噪声（和其他影响），当电源（重新）应用于芯片时，并非每个单元都会将自身初始化为相同的已知状态。在上电后立即将芯片 RAM 的内容与某些功能相结合可以产生大量的熵以供以后使用。- 这样做的缺点是它只能在电源关闭一段时间然后再次打开时才能可靠地工作。正常的芯片复位，通过硬件、软件或外部信号，将保留 RAM 以前的内容，因此不是（总是）一个好的熵源。但是，由于在相当复杂的应用程序中很难预测重置时整个系统 (RAM) 的状态，因此无论如何可能在重置后立即收集一些熵。

带宽要求

熵源的质量必须与其带宽和应用程序使用熵的带宽有关。一些熵收集方法在几秒钟内可能不会产生超过一位的熵，而其他方法（不是真的在 µCs 上......）可能会产生 100 kbit/s 或更多。

必须注意的是，不能通过算法从现有熵中“创建”新熵！- 一位熵不能通过计算转换为两位熵。

因此，一个人（平均而言）每个时间单位消耗的（实际）熵不能比同时从熵源收集的熵多。

提议

当需要强随机数时，将一个或多个真实熵源与强PRNG结合起来并不少见，每次新熵可用时，使用收集到的熵来（重新）播种 PRNG。

PRNG 可用于生成比熵源在同一时间实际提供的更多基本不可预测的数据。

作为一种特殊的 PRNG，可以使用加密密码函数，其中熵用于初始化和更新密码的密钥。

Linux/dev/urandom通常以这种方式实现。

结论

如上所述，在普通微控制器上生成真正的随机数是非常可行的。对于所有其他熵源，需要分析熵源提供的原始数字，了解它们包含的真实熵量以及每个时间单位产生的熵量，以确定该源是否适合用例与否。

真正的熵源和强 PRNG 的组合是通常实现的方法，也应该在微控制器上使用。

编辑：

PRNG 方法可能不是加密密钥生成的最佳选择。为此，应该只使用真正的随机位来生成安全密钥。收集这么多的熵可能需要一些时间（可能是几秒钟），但由于在 µC 上通常不会非常频繁地执行密钥生成，因此这很可能是可以接受的。（在每秒有数百或更多 SSL (HTTPS) 连接的重负载服务器上，这将是另一个问题......）

为了产生适合密钥生成的高质量高熵比特流，应该使用上面提到的随机提取器。

（另一方面，如果可以测量或估计源输出中的熵量，则可以简单地将密钥长度按因子缩放(bitlength of key)/(entropy per bit sampled)，然后直接使用来自熵源的原始低熵数据来生成这个更长的密钥，然后它将具有与原始长度的完全随机密钥相同的整体熵。但是，如果这确实有效，则取决于密码如何处理不同长度的密钥。）

于 2012-06-03T14:18:56.057 回答
3

取决于传感器的范围、采样频率和灵敏度。您可以将传感器测量值视为位串或浮点数，这并不重要。关键是，最高有效位/前导小数不是很随机，它们甚至可能几乎不会改变。同样，最低有效位是不可靠的随机源，因为由于传感器灵敏度有限，它们可能会显示阶跃效应，并且取决于传感器，它们可能在时间上具有很强的相关性（例如，温度或电压将具有逐渐变化的趋势）。然而，中间位/数字很可能是真正随机值的来源。

假设您有一个传感器输出 0 到 200 范围内的值，精度为 0.01。假设它是一个压力计，也许是一个分贝计。您需要对此进行广泛测试并查看特定传感器和环境的值分布，但我认为 10^0 和 10^-1 位置的数字很可能均匀分布且没有可辨别的顺序。

最适合的是可以进行非常精确的测量但无论如何都必须处理高水平噪声的传感器。这可能会造成问题，因为大多数传感器并非旨在提供不必要/不可靠的精度水平。此外，当然首选始终和各处（噪声除外）大致相同的测量值。宇宙背景辐射就是一个很好的例子。

于 2012-06-02T18:14:11.340 回答
1

我一直在尝试使用硬件资源来生成随机数，到目前为止，它们似乎提供了一个不可预测的资源。如果使用白化技术，则会减少/消除任何潜在的偏差，以允许它们产生均匀的随机整数序列。

如果您想尝试和实验，我已经实现了一个 Arduino 兼容库，它使用与看门狗定时器相关的抖动来生成随机数。初步结果表明它正在产生适合加密目的的结果。

可以在Code.google 库中找到

于 2012-06-08T21:58:22.480 回答
-4

谷歌：真随机数生成器

这就是你的做法，你制造噪音并对其进行采样。您无法从软件算法之类的确定性事物中创建真正随机的事物。

于 2012-06-03T17:58:35.943 回答