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

Question

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

这是来自random.c. 它表示变量中最后两个中断之间的时间（我认为是 jiffies）delta和 deltas 中的差异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) .... 这有什么作用？为什么取这个 delta 和最后一个的最小值？我不知道这应该实现什么 - 也许它会使估计更好，也许只是更保守。

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

评论中出现的其他资源：

• 维基百科/dev/random和/dev/urandom
• 试图解释它的论文（我对此持怀疑态度，请参阅评论）
• 一篇关于/dev/random上面代码编写者的评论的博客文章。
• 关于/dev/random熵池的secutity.SE 答案。

Answer 1

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

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

我说的是“直观”，没有更多要说的了。事实上，在“随机物理事件”模型中，计数比特是错误的；如果每个时间单位发生硬件事件的概率为p，并且您得到的延迟表示为n位，则熵贡献应计为n/2位，而不是n位。但我们知道，在现实中，物理事件并不是完全随机发生的；该delta2机制承认同样多。

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

这个页面是由一个厌倦了关于/dev/random熵估计器的神话的人写的，我认为它很好地解释了事情，有足够的细节。在处理 RNG 时，获得一些基本的想法很重要。