☰

random.c で使用されるエントロピー推定について説明していただけますか?

tag-icon • tag-icon linux kernel random
random.c で使用されるエントロピー推定について説明していただけますか?

/dev/randomカーネル割り込みのタイミングを使用してエントロピー プールに追加します。プール内のエントロピーの量は、 という変数で追跡されますentropy_count。

以下は からの関連するコード スニペットですrandom.c。これは、変数 の最後の 2 つの割り込み間の時間 (jiffy 単位だと思います)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;

追加されたエントロピーの推定値は、本質的にはデルタの底 2 の対数の下限値 (ループ前の初期ビットシフトのため上限値ではない) のようです。これは直感的には理解できますが、これを正式に正しくするためにどのような仮定が必要なのかはわかりません。

最初の質問は「この見積りの根拠は何ですか？」

2 つ目の質問は についてですdelta = MIN(delta, delta2) ...。これは何をするのでしょうか? このデルタと最後のデルタの最小値を取るのはなぜでしょうか? これが何を達成するのかはわかりません。おそらく推定値を向上させるか、より保守的になるだけかもしれません。

編集：私は見つけた見積りを明記した書類しかし、それについて論理的な議論は実際には示されていません (ただし、推定量が満たすべき非公式の条件については概説しています)。

コメントで取り上げられた他のリソース:

答え1

delta2前のではなくdelta、違いの 2 つの連続する値の間delta。これは一種の導関数です。 がdelta速度を測定する場合、delta2は加速度です。

この推定値の背後にある直感的な考え方は、割り込みは物理世界からの予測不可能なイベント (キーストロークやネットワーク パケットの到着など) によって決まり、多かれ少なかれランダムな間隔で発生するというものです。遅延が長くなるほど、予測不可能なイベントが多くなります。ただし、固定レートで割り込みを発生させる物理システムもあります。このdelta2測定は、そのような発生を検出する保護メカニズムです (割り込みが固定間隔で発生する場合、つまり確実に予測可能な場合は、すべてdelta同じ値になり、delta2ゼロになります)。

「直感的」と言いましたが、それ以上言うことはありません。実際、「ランダムな物理的イベント」モデルでは、ビットを数えることは間違いです。ハードウェアイベントが確率的に発生する場合、p各時間単位ごとに、遅延が表現されますんビットの場合、エントロピーの寄与は次のように計算される。2/2 倍ビットではなくんビット。しかし、現実には物理的な出来事がまったくランダムな瞬間に起こるわけではないことはわかっています。delta2メカニズムはそれを認めています。

実際には、「エントロピー推定」とはまさに次のようになります。見積もりそのセキュリティ上の価値は、十分に根拠のある、数学的に正確な正当化から来るものではなく、通常のセキュリティの源泉から来ています。つまり、誰もそれを悪用する方法を見つけていないようです (まだ)。

このページとそのエントロピー推定器に関する神話にうんざりした人が書いたもの/dev/randomで、十分な詳細とともに物事をうまく説明していると思います。RNG を扱うときは、いくつかの基本的な考え方を正しく理解することが重要です。

関連情報