暗号論的擬似乱数生成器とは? わかりやすく解説

Weblio 辞書 > 辞書・百科事典 > ウィキペディア小見出し辞書 > 暗号論的擬似乱数生成器の意味・解説 

暗号論的擬似乱数生成器

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2024/01/07 04:54 UTC 版)

暗号論的擬似乱数生成器CSPRNG、英語: cryptographically secure pseudo random number generator、暗号論的にセキュアな疑似乱数生成器)とは、暗号技術での利用に適した特性を持つ擬似乱数生成器 (PRNG) である。

暗号の応用では様々な場面で乱数を必要とする。例えば、以下のようなものがある。

  • 生成
  • Nonce (プロトコル上1度だけ使われる数、number used once)
  • Salt (ECDSA、RSASSA-PSS などの署名スキーマで使われる)
  • ワンタイムパッド

その際に必要な乱数の性質は様々である。例えば、何らかの暗号プロトコルで Nonce を生成する際に求められるのは一意性だけである。一方、の生成には高い無作為性が求められる。ワンタイムパッドには暗号論的擬似乱数も不適で、高いエントロピーを持つ真の無作為情報源が必要であり、それにより情報理論的安全性を得る。

理想的には、暗号プロトコル等に使用する乱数生成には高品質の情報源から得られるエントロピーを利用すべきである。それは、例えば量子論的な乱数生成器や予測不可能な何らかの系のプロセスである。情報理論的観点では、無作為性の程度とはエントロピーであり、ある系の入力のエントロピー以上のエントロピーは出力できないからである。しかし、実用システムでは、利用可能なエントロピー以上の乱数を必要とすることがある。無作為性を引き出すプロセスには時間が掛かるためである。そのような場合に CSPRNG を使うことがある。CSPRNG は利用可能なエントロピーをより多くのビット数に拡張する。

要求仕様

通常のPRNGの要求仕様は、CSPRNG でも満足される。しかし、逆は真ではない。CSPRNG の要求仕様は2つに分類される。第一に、その統計的特性がよいこと(統計的無作為性の試験に合格すること)、第二に、激しい攻撃にも耐えること(初期状態や途中の状態が攻撃者に明らかになっても破られないこと)である。

  • 全てのCSPRNGは "next-bit test" に合格する。next-bit test とは、乱数列の最初の k ビットを与えられたとき、k+1 番目のビットの値を多項式時間で2分の1をこえる確率で予測するアルゴリズムが存在しないことを確認する試験である。アンドリュー・チーチー・ヤオ1982年、next-bit test に合格した生成器は、無作為性に関する他の多項式時間統計試験にも合格することを証明した。
  • 全てのCSPRNGは "state compromise extensions" に耐える。その状態の一部または全部が明らかになっても(あるいは正しく推測されても)、明らかにされた状態より以前に生成された乱数列は再現できない。さらに、実行中にエントロピーの入力がある場合、その入力を知っていてもCSPRNGの将来の状態を予測できない。
例: 円周率の数列から出力を生成するCSPRNGがあり、2進数化した数列のどこからを使うのか不明であるとする。これはnext-bit testを満足するが暗号論的に安全ではない。なぜなら、アルゴリズムの状態にあたる「円周率のどの部分が現在使われているか」を攻撃者が突き止めた場合、その攻撃者は先行するビットをすべて計算できるからである。

多くのPRNGはCSPRNGとしては不適であり、上記の2つを満足しない。第一にPRNGの出力は統計的に無作為に見えるが、リバースエンジニアリングには耐性がない。従って、アルゴリズムを解析することで特別な統計的試験を設計でき、PRNG の出力が真の乱数ではないことを示すことができる。第二に状態が明らかであれば、過去の乱数列を再現でき、攻撃者が全ての過去のメッセージを読むことが可能となる。当然、将来の暗号も解読可能となる。

CSPRNGは、このような暗号解読に対抗するものとして設計される。

背景

Santha と Vazirani は、無作為性の弱いビット列を複数組み合わせることで高品質な擬似乱数列を生成できることを証明した[1]。それ以前にジョン・フォン・ノイマンはビット列からバイアスの大部分を除去できる簡単なアルゴリズムがあることを証明し[2]、Santha-Vazirani の設計に基づいたCSPRNGでフォン・ノイマンのアルゴリズムを入力ビット列に適用する必要がある。これを entropy extraction(エントロピー抽出)と呼び、研究が盛んな領域である。

設計

ここでは、CSPRNGの設計を

  1. ブロック暗号や暗号学的ハッシュ関数などの暗号プリミティブに基づく設計
  2. 数学的に解くのが難しい問題に基づく設計
  3. 特殊な設計

に分けて解説する。

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

  • 安全なブロック暗号は、CTRモードで動作させることでCSPRNGとして使うことができる。これは、ランダムな鍵を選んで0を暗号化し、次に1を暗号化し、さらに2を暗号化し、というように行う。カウンタを0以外の任意の値から開始することもできる。明らかに、その周期は n-ビットブロック暗号では 2n であり、鍵と平文の初期値が攻撃者に知られてしまうと、全く安全でなくなる。また、誕生日のパラドックスから2n/2の出力で真の乱数と1/2の確率で識別可能である。
  • 暗号学的ハッシュ関数もCSPRNGとして利用可能である。カウンタ値のハッシュ値を次々に計算すればよい。しかし、これについて安全ではないとする主張もある[3]
  • ストリーム暗号は、平文を擬似乱数列と(通常 XOR で)結合することで暗号文を生成する。カウンタを平文として暗号文を生成すれば、新たな擬似乱数列が生成され、おそらく内部の疑似乱数列より周期を長くできる。この生成法は、内部で生成する擬似乱数列がCSPRNGであるときだけ安全であるが、一般にそうでないことが多い(RC4参照)。
  • ANSI X9.17 標準(Financial Institution Key Management (wholesale)[4]では、ブロック暗号であるDESを用いた疑似乱数の生成法を挙げており、FIPSにも採用されている。この生成法では、64ビットのシード s とDESの鍵 kを用いて、次のように64ビット乱数を生成する。まず現在日時情報 D (可能な限り詳しい値)を使って、中間値 カテゴリ

暗号論的擬似乱数生成器

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2022/05/01 15:29 UTC 版)

ストリーム暗号」の記事における「暗号論的擬似乱数生成器」の解説

一般的な暗号論的擬似乱数生成器を使うこともある(一般的には計算量の点で利点が無いが、他の部分により重い計算があるなど、それが問題にならない場合例えen:BlumGoldwasser cryptosystem の内部に、Blum-Blum-Shub利用するストリーム暗号、という構造含まれている)。

※この「暗号論的擬似乱数生成器」の解説は、「ストリーム暗号」の解説の一部です。
「暗号論的擬似乱数生成器」を含む「ストリーム暗号」の記事については、「ストリーム暗号」の概要を参照ください。

ウィキペディア小見出し辞書の「暗号論的擬似乱数生成器」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。 お問い合わせ


英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「暗号論的擬似乱数生成器」の関連用語










10
90% |||||

暗号論的擬似乱数生成器のお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



暗号論的擬似乱数生成器のページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアの暗号論的擬似乱数生成器 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。
ウィキペディアウィキペディア
Text is available under GNU Free Documentation License (GFDL).
Weblio辞書に掲載されている「ウィキペディア小見出し辞書」の記事は、Wikipediaのストリーム暗号 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。

©2025 GRAS Group, Inc.RSS