5.5. Using a Mixing Function to Stretch Random Bits (混合関数を使用したランダムビットの拡張)

5.5. Using a Mixing Function to Stretch Random Bits (混合関数を使用したランダムビットの拡張)

混合関数がその入力と同じまたはより少ない出力ビットを生成する必要はありませんが, ビットの混合は入力に存在するランダムな予測不可能性の量を "拡張" することはできません。したがって, それぞれに 12 ビット分の予測不可能性 (4,096 の等しく可能な値など) がある 32 ビットの 4 つの入力は, 48 ビット分を超える予測不可能な出力を生成できません。出力は, たとえば連続する整数と混合することによって数百または数千のビットに拡張できますが, 賢い敵の検索空間は依然として 2^48 の可能性です。さらに, 入力されたビットよりも少ないビットに混合すると, 出力のランダム性を強化する傾向があります。

セクション 5.1 の最後の表は, ランダムビットを定数ビットと排他的論理和で混合するとランダムビットが生成されることを示しています。これは真実ですが, 1 つのランダムビットを複数に "拡張" する方法は提供しません。たとえば, ランダムビットが 0 と混合され, 次に 1 と混合された場合, これは 2 ビットシーケンスを生成しますが, 常に 01 または 10 のいずれかになります。可能な値は 2 つしかないため, 依然として元のランダム性の 1 ビットしかありません。