Arduino 中的真随机数生成器（在这种情况下是 AVR ATmega）

问题

我曾在一个项目中需要为通信总线上的每个基于微控制器的设备初始化唯一的地址。由于地址必须是唯一的，而设备是相同的，因此诀窍在于使用随机化来让具有相同控制器、代码和 PCB 的控制器产生不同的行为。这样，当我们要求同一地址的两个设备通过抛硬币的方式切换到新地址时，只有一个设备跳转的概率是 50%，这意味着在很短的时间内，我们可以为所有先前具有相同地址的设备分配唯一的地址。

我们使用了标准的随机化器，甚至使用了 ADC 来包含现实世界的非线性，但这个系统被证明是完全线性的。无论花费多长时间，由于所有设备同时通电并且拥有完全相同的代码，因此在被请求时它们总是会倾向于跳转地址。还记得电影《马达加斯加》里的 Marty 吗？

我们找到的唯一方法是使用可调电位分压器等硬件元件，使每个电路至少拥有一些独特的东西可以感知。即使是这种技术也失败了，因为它在电路中增加了额外的元件，而且制造工艺加上拥有唯一种子（seed）的概率只有 1/1024（因为传感器，即 ADC，只有 10 位宽度）。我们需要一个具有真正随机种子的更好的随机化器。

我必须在此提及另一篇文章，它介绍了另外两种随机数生成方法。我无法使用其中任何一种，因为其中一种依赖于专用硬件，而另一种则占用大量内存。本文介绍的方法非常轻量，实际上可以节省 300 字节的闪存以替换现有的 Arduino rand() 函数。另一篇文章仍然可以在 此处找到。

一点背景知识

ADC 已经被用于在微控制器中生成真随机数。当由于某种原因我们无法为该随机化过程分配任何模拟输入引脚，或者 ADC 在附近 EMF 和 ESF 的存在下饱和时，就会出现一些限制。我使用了 Atmega328p 来演示一种克服这些限制的方法。我们没有尝试读取浮动的（并被认为是随机的）输入信号，而是创建了一个内部信号，并利用硬件无法精确合成预期信号的限制。这为随机化某些位提供了机会。

所以 ATMega 的 ADC（其他 AVR 和大多数具有内部 ADC 的控制器）使用一个可编程多路复用器将不同的引脚路由到主转换器。除了连接到控制器的输入引脚外，它还可以连接到一些内部预定义的电压，对于 Atmega328p 来说，这些是 0V 和 1.1V 带隙电压。参考电压也可以改变，但在此方法中我们不使用改变参考电压的效果。使用这两个电压，我们在 ADC 上合成一个幅度为 1.1V 的脉动方波。ADC 应该为低脉冲读取“0”，为高脉冲读取“1023”，但这只有在我们假设的方波是真实的情况下才是正确的，而实际并非如此。由于控制器电路的内部电容，电压电平的改变需要一些时间，幸运的是，这个时间恰好是 ADC 每次转换所需的时间范围。因此，在一个完全线性的微控制器电路中，我们形成了一个高度非线性的子系统，这是由多个因素造成的，例如电源电压、温度，最重要的是，当我们处于其他组件的固有频率范围内时，振荡会利用系统非常有趣的动态。

现在测量到的值是随机的，但可能包含某种模式，因为它们来自非混沌的物理现象。为了减少这种影响，我们使用了一些编码技术。例如，使用“种子”（seed），进行位移，以及随机改变合成信号的频率。第一个是通过使用前一次转换的结果作为起点（就像我们在伪随机数中做的那样）；位移是使用处理器标准的移位指令完成的；最后一个是通过在每次转换后改变 ADC 的时钟频率来完成的。

Using the Code

下面是一个生成 8 位随机数的示例代码。可以通过增加位深度或使用多个随机化器来获得更宽的数字。

    int N = 20; 
    // 20 works really fine for uint8, can be increased to reduce patterns. 
    // Each cicle takes around 80us on 16Mhz main clock 
    // which give a random number almost every 1.5ms.
    for (int i = 0; i < N; i++)
    {
      // Synthesize a voltage on the input
      if (i % 2 == 0)
        ADMUX = 0b01001110; // [A] // High (1.1V). // See Datasheet Table 23-3 and 23-4 
                                   // for Atmega328p 
      else
        ADMUX = 0b01001111; // [A] //  Low (0V)
      ADCSRA |= 1 << ADSC;  // Start a conversion. See Datasheet for Atmega328p Page 207
      uint8_t low, high;
      // ADSC is cleared when the conversion finishes
      while ((ADCSRA >> ADSC) % 2); // wait for the conversion to complete
      low  = ADCL;          // do not swap this sequence. Low has to be fetched first.
      high = ADCH;          // the value is always between 0-3
      V ^= low; 
      V ^= high;

      // Let's shift rotate the number;

      uint8_t last = V % 2;
      V >>= 1;
      V |= last << 7;        // "7" will need to change to K-1 to use a K bits wide datatype
      // Disable the ADC
      ADCSRA = 0;

      // Enable the ADC with a randomly selected clock Prescaler between 2 and 128. 
      // Since each conversion takes 13 ADC cycles, at 16Mhz system clock, 
      // the ADC will now take something in between 1.6us and 104us 
      // for each conversion (75us on the average).
      ADCSRA = 0b10000000 | ((V % 4) << 1); // See Datasheet Table 23-5 for Atmega328p 
    } 

N = 20 时的示例输出

N = 50 时的示例输出

改进余地

• 在测量信号时，我们还可以通过更改参考电压来增加非线性。这需要在上述代码的 [A] 点嵌入。
• 最终数字可以通过添加一个以真实数字为种子的伪随机数生成器来补充。
• 为了使 ADC 读数更加随机，我们可以让信号更加不稳定（例如，使用可变时钟速率），或者让信号移动得非常快。当读取非常快速的信号时，ADC 的不确定性会增加。这可以通过将振荡系统更多地移向共振点来实现。这意味着只有 ADC 时钟的可能频率之一会产生信号的最大上升和下降时间，从而导致更不稳定的 ADC 读数。
• 随机数的位宽度可以增加。

应用

• 安全
• 沟通

历史

• 2021 年 8 月 23 日：初始版本