☰

你能解釋一下 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 打交道時，正確掌握一些基本理念非常重要。

相關內容