☰

你能解释一下 random.c 中使用的熵估计吗

tag-icon • tag-icon linux kernel random
你能解释一下 random.c 中使用的熵估计吗

/dev/random使用内核中断的计时来添加到熵池。池中的熵量在名为 的变量中进行跟踪entropy_count。

这是来自 的相关代码片段random.c。它表示变量中最后两次中断之间的时间（我认为以 jiffies 为单位）delta和 delta 的差异delta2。

delta = time - state->last_time;
state->last_time = time;

delta2 = delta - state->last_delta;
state->last_delta = delta;

if (delta < 0) delta = -delta;
if (delta2 < 0) delta2 = -delta2;
delta = MIN(delta, delta2) >> 1;
for (nbits = 0; delta; nbits++)
  delta >>= 1;

r->entropy_count += nbits;

/* Prevent overflow */
if (r->entropy_count > POOLBITS)
  r->entropy_count = POOLBITS;

看起来添加的熵的估计本质上是 delta 的以 2 为底的对数的下限（不是 ceil，因为循环之前的初始位移）。这具有一定的直观意义，尽管我不确定需要什么假设才能使其正式正确。

所以，我的第一个问题是“这个估计背后的理由是什么？”

我的第二个问题是关于delta = MIN(delta, delta2) ....这是做什么的？为什么要取这个增量和最后一个增量的最小值？我不知道这应该达到什么目的——也许它会让估计更好，也许只是更保守。

编辑：我找到了一个指定估计值的文件，但它并没有真正给出合理的论证（尽管它确实概述了估计器应该满足的一些非正式条件）。

评论中出现的其他资源：

答案1

delta2不是前一个delta，而是不同之处的两个连续值之间delta。它是一种导数：如果delta测量速度，delta2就是加速度。

该估计背后的直观想法是，中断以或多或少的随机间隔发生，由物理世界中不可预测的事件（例如击键或网络数据包的到达）决定。延迟的时间越长，涉及的不可预测的事件就越多。然而，有些物理系统会以固定的速率触发中断；该delta2措施是一种检测此类事件发生的保护机制（如果中断以固定间隔发生，因此可以明确预测，则所有中断delta都将具有相同的值，因此delta2将为零）。

我说“直观”，没什么可说的。事实上，在“随机物理事件”模型中，对比特进行计数是错误的；如果硬件事件有概率发生p对于每个时间单位，你会得到一个表示为n位，那么熵贡献应计算为n/2位，不n位。但我们知道，在现实中，物理事件并不是完全随机发生的；而是随机发生的。该delta2机制也承认这一点。

所以在实践中，“熵估计”正是：估计。它的安全价值并不是来自于一个合理的、数学上精确的理由，而是来自通常的安全来源：似乎没有人找到滥用它的方法（到目前为止）。

这一页是由一个厌倦了关于/dev/random熵估计器的神话的人写的，我认为它很好地解释了事情，有足够的细节。在与 RNG 打交道时，正确掌握一些基本理念非常重要。

相关内容