在嵌入式系统中生成随机数的典型方法是什么？

Question

在嵌入式系统中生成随机数的典型方法是什么？您能为每种方法提供优缺点,和/或某些因素可能会让您选择一种方法而不是另一种方法吗？

Answer 1

首先,你必须提出一个基本问题:你需要不可预知的随机数吗？

例如,密码学需要不可预测的随机数.也就是说,没有人必须能够猜出下一个随机数是什么.这排除了任何种子随机数生成器从常见参数(如时间)播种的方法:您需要适当的熵源.

某些应用程序可以使用非加密质量的随机数生成器.例如,如果您需要通过以太网进行通信,则需要一个随机数生成器来进行指数退避; 统计随机性足够这个¹.

不可预测的RNG

每当对手可能试图猜测你的随机数并根据猜测做一些不好的事情时,你需要一个不可预测的RNG.例如,如果您要生成加密密钥或使用许多其他类型的加密算法,则需要一个不可预测的RNG.

不可预测的RNG由两部分组成:熵源和伪随机数发生器.

一个熵源的kickstart的不可预测性.熵需要来自不可预测的来源或混合不可预测的来源.这些来源不需要完全不可预测,它们不需要完全可预测.熵量化了不可预测性的数量.估算熵很困难; 寻找安全专业人士的研究论文或评估.

生成熵有三种方法.

您的设备可能包含一些非确定性硬件.一些设备包括基于物理现象的专用硬件RNG,例如不稳定的振荡器,热噪声等.一些设备具有捕获某些不可预测值的传感器,例如光或声音传感器的低阶位.

请注意,硬件RNG通常具有精确的使用条件.上电后大多数方法需要一些时间才能使输出真正随机.通常,极端温度等环境因素会影响随机性.请仔细阅读RNG的使用说明.对于加密应用程序,通常建议对HRNG的输出进行统计测试,如果这些测试失败则拒绝操作.

切勿直接使用硬件RNG.输出很少完全不可预测 - 例如,每个比特可能具有60%的概率为1,或者两个连续比特相等的概率可能仅为48%.使用硬件RNG为PRNG播种,如下所述.
您可以在制造过程中预加载随机种子,然后再使用它.熵在使用时不会磨损²:如果你有足够的熵开始,你将在你的设备的生命周期内有足够的熵.保持熵的危险在于它必须保密:如果熵池意外泄漏,那就是吐司.
如果您的设备与可信第三方(例如您的服务器或传感器网络中的主节点)有连接,则可以从该设备(通过安全通道)下载熵.

甲PRNG,也被称为确定性随机位产生器(DRBG),是一个确定性的算法,通过将内部状态生成随机数的序列.国家必须以足够的熵播种,之后PRNG几乎可以永远运行.加密质量的PRNG算法基于加密原语; 始终使用经过审查的算法(最好是一些经过良好审核的第三方代码,如果有的话).

PRNG需要用熵播种.您可以选择在制造期间或每次启动时或周期性地或任何组合注入熵一次.

您需要注意设备在相同的RNG状态下不会启动两次:否则观察者可以在重置后重复相同的RNG呼叫序列,并且第二次知道RNG输出.这是工厂注入的熵(根据定义总是相同的)以及从传感器(需要时间累积)的熵的问题.

如果可能,将RNG状态保存到持久存储.当设备启动时,读取RNG状态,对其应用一些转换(例如,通过生成一个随机字),并保存修改后的状态.完成此操作后,您可以开始将随机数返回给应用程序和系统服务.这样,设备每次都会以不同的RNG状态启动.

如果这是不可能的,你必须非常小心.如果您的设备具有工厂注入的熵和可靠的时钟,您可以将时钟值混合到RNG状态以实现单一性; 但是,请注意,如果您的设备断电并且时钟从某个固定原点(闪烁十二点)重新启动,您将处于可重复状态.

复位后或首次启动时可预测的RNG状态是嵌入式设备(以及服务器)的常见问题.例如,对RSA公钥的研究表明,许多生成的熵不足,导致许多设备生成相同的密钥³.

如果无法实现加密质量,则可以回退到不太好的RNG.您需要注意一些应用程序(包括大量加密)是不可能的.

任何RNG都依赖于两部分结构:唯一种子(即熵源)和基于该种子的确定性算法.

如果你不能收集足够的熵,至少要尽可能多地聚集.特别是,确保没有两个设备从相同的状态开始(这通常可以通过将序列号混合到RNG种子中来实现).如果可能的话,安排种子在重置后不要重复.

不使用加密DRBG的唯一理由是您的设备没有足够的计算能力.在这种情况下,您可以回退到更快的算法,允许观察者根据RNG的过去或未来输出猜测某些数字.的梅森捻线机是一种流行的选择,但已经有自其发明的改进.

¹ _{即使这是有争议的:使用非加密质量的随机退避,另一个设备可能会通过将其重新传输时间与您的重新传输时间对齐而导致拒绝服务.但是还有其他方法可以通过更频繁的传输来实现DoS.}
² _{从技术上讲,它确实如此,但仅限于天文尺度.}
³ _{或者至少有一个共同的因素,这同样糟糕.}