☰

Random.cで使用されるエントロピー推定を説明できますか？

tag-icon • tag-icon linux kernel random
Random.cで使用されるエントロピー推定を説明できますか？

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

以下は関連コードの一部ですrandom.c。これは、変数の最後の2つの中断の間の時間（私の意見ではjifies単位）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;

追加されたエントロピーの推定値は、基本的にデルタの下が2の対数の下限であるように見えます（ループ前の初期変位のため天井ではありません）。正式に正しいものにするためにどの仮定が必要かはわかりませんが、これはある程度直感的な意味があります。

だから私の最初の質問は「この見積もりの​​根拠は何ですか？」

2番目の質問は、delta = MIN(delta, delta2) ...これが何をしているのかということです。この増分と最後の増分の最小値を取るのはなぜですか？これが何を達成することになっているのかはわかりません。おそらく、見積もりをより良くするか、より保守的にすることができます。

編集する：私が一つ見つけた見積もりを指定するファイルしかし、これは実際には健全な主張を提供しません（たとえ推定者が満たす必要があるいくつかの非公式条件を簡単に説明しますが）。

コメントに含まれるその他のリソース：

ベストアンサー1

delta2以前ではないがdelta、違い2つの連続した値の間delta。これは微分です。delta速度を測定するとdelta2加速度です。

この推定の裏側の直感的なアイデアは、中断が物理的な世界で予測できないイベント（キー入力やネットワークパケットの到着など）によって決定されるややランダムな間隔で発生することです。遅延時間が長くなるにつれて、予測できないイベントが発生します。ただし、一部の物理システムは一定の速度で割り込みをトリガします。このdelta2アクションは、これらのイベントの発生を検出するための保護メカニズムです（割り込みが一定の間隔で発生し、明確に予測可能な場合、すべての割り込みはdelta同じ値を持つためdelta2ゼロになります）。 ）。

「直感的」と言えばあまり言うことはありません。実際、「任意の物理イベント」モデルでは、ハードウェアイベントが確率的に発生した場合、ビット計算は誤りです。血各時間単位について、次のように表示される値が得られます。Nビットの場合、エントロピー寄与は次のように計算する必要があります。n/2少し、いいえN少し。しかし、我々は実際には物理的事象が完全にランダムに発生しないことを知っています。メカニズムdelta2もこれを認識します。

したがって、実際には「エントロピー推定」はまさに次のようになります。推定。セキュリティ価値は、健全で数学的に正確な理由ではなく、一般的なセキュリティソースに由来します。これまで誰もこれを乱用する方法が見つからなかったようです。

このページエントロピー推定器に対する迷信に疲れた誰かが書いたこの/dev/random本は内容を十分に詳しく説明していると思います。 RNGを扱うときは、いくつかの基本概念を正しく理解することが重要です。

おすすめ記事