暗号論的擬似乱数生成器

暗号論的擬似乱数生成器 (CSPRNG) について

暗号論的擬似乱数生成器（CSPRNG）とは、暗号技術における様々な用途に適した特性を持つ擬似乱数生成器のことです。暗号の分野では、鍵の生成、Nonce（使い捨ての数）、Saltなど、多くの場面で乱数が必要となります。

これらの乱数にはそれぞれ異なる性質が求められます。例えば、Nonceは一意性のみが重要ですが、鍵生成には高いランダム性が不可欠です。ワンタイムパッドのように、情報理論的に安全な暗号には、CSPRNGではなく、高いエントロピーを持つ真の乱数源が要求されます。

エントロピーとCSPRNG

理想的には、暗号プロトコルで使用する乱数は、量子乱数生成器や予測不可能な物理現象など、高品質なエントロピー源から生成されるべきです。情報理論的に、ある系の出力できるエントロピーは、入力のエントロピーを超えることはありません。しかし、実用システムでは、利用可能なエントロピー量よりも多くの乱数が必要になる場合があります。エントロピーを抽出するプロセスには時間がかかるため、CSPRNGが利用されます。CSPRNGは、限られたエントロピーをより多くのビット数に拡張する役割を果たします。

CSPRNGの要件

通常の擬似乱数生成器（PRNG）の要件はCSPRNGでも満たされますが、逆は必ずしも真ではありません。CSPRNGには、以下の2つの主要な要件があります。

1. 統計的無作為性: 生成される乱数列が、統計的な無作為性テストに合格する必要があります。
2. 攻撃耐性: 初期状態や途中の状態が攻撃者に漏洩した場合でも、過去の乱数を再現できない、また、将来の乱数を予測できないという耐性が求められます。

Next-bit test

すべてのCSPRNGは「next-bit test」に合格する必要があります。これは、乱数列の最初のkビットが与えられた際に、k+1番目のビットを多項式時間で1/2を超える確率で予測するアルゴリズムが存在しないことを保証するテストです。このテストに合格する生成器は、他の無作為性に関する統計テストにも合格することが証明されています。

State compromise extensions

また、CSPRNGは「state compromise extensions」に耐える必要があります。つまり、内部状態の一部または全部が明らかになったとしても、その情報から過去に生成された乱数列を再現できない必要があります。さらに、実行中にエントロピー入力があった場合、その入力を知っていても将来の状態を予測することはできません。

通常のPRNGとの違い

多くのPRNGはCSPRNGの要件を満たしていません。PRNGの出力は統計的には無作為に見えても、リバースエンジニアリングに対して耐性がなく、アルゴリズムを解析することで真の乱数ではないことが判明することがあります。また、状態が明らかになった場合、過去の乱数を再現できるため、暗号が解読されてしまう可能性があります。CSPRNGは、このような攻撃に対抗できるように設計されています。

背景

SanthaとVaziraniは、弱い無作為性を持つビット列を組み合わせることで、高品質な擬似乱数列を生成できることを示しました。また、フォン・ノイマンは、ビット列のバイアスを除去するアルゴリズムを考案しました。これらの研究に基づいて、CSPRNGでは入力ビット列にエントロピー抽出処理を適用することが重要です。

CSPRNGの設計

CSPRNGの設計は、主に次の3つのカテゴリに分類されます。

1. 暗号プリミティブに基づく設計: ブロック暗号や暗号学的ハッシュ関数などの暗号プリミティブを利用します。
2. 数論的な設計: 数学的に解くのが難しい問題（素因数分解など）に基づいた設計です。
3. 特殊な設計: 実用的なCSPRNGを目的とした個別の設計です。

暗号プリミティブに基づく設計

ブロック暗号

安全なブロック暗号は、CTRモードで動作させることでCSPRNGとして使用できます。これは、ランダムな鍵で0、1、2と暗号化していく方法です。ただし、鍵と初期値が漏洩すると安全ではなくなり、出力が長くなると、誕生日のパラドックスにより真の乱数との区別がつきやすくなります。

暗号学的ハッシュ関数

暗号学的ハッシュ関数もCSPRNGとして利用できます。カウンタ値のハッシュ値を計算する方法が一般的です。ただし、この方法には安全性の問題があるとの指摘もあります。

ストリーム暗号

ストリーム暗号は、平文を擬似乱数列と組み合わせて暗号文を生成します。カウンタを平文として暗号文を生成すると、より長い周期の擬似乱数列が生成できる可能性があります。この方法は、内部の擬似乱数列がCSPRNGである場合にのみ安全です。

ANSI X9.17

ANSI X9.17では、DESを用いた擬似乱数の生成法が定義されており、FIPSにも採用されています。この方法では、現在日時情報とシードを用いて乱数を生成します。

数論的設計

Blum-Blum-Shub

Blum-Blum-Shubは、素因数分解の難しさを基にしたCSPRNGであり、条件付きで安全性が証明されています。ただし、実装時の性能は他の方法よりも劣ります。

その他

Micali–Schnorr generatorやNaor-Reingold pseudorandom functionなどがあります。

特殊な設計

Yarrow algorithm と Fortuna

Yarrow algorithmは入力エントロピーの品質を評価しますが、Fortunaはしません。

Microsoft CryptGenRandom

マイクロソフトのCAPIにある関数です。

ISAAC

RC4から派生したCSPRNGです。

標準規格

CSPRNGに関する標準規格には、以下のようなものがあります。

FIPS 186-2
NIST SP 800-90
ANSI X9.17-1985
ANSI X9.31-1998
ANSI X9.62-1998

また、CSPRNGの統計的テストに関する標準もあります。

NIST Special Publication 800-22


CSPRNGは、暗号技術の根幹をなす重要な要素であり、その設計と実装は高度なセキュリティ基準を満たす必要があります。

もう一度検索