• ホーム
• 情報セキュリティ
• 暗号技術

乱数について

暗号に関する研究の進展とともに，セキュリティシステムの実現に強力な暗号アルゴリズムが使われるようになってきている．しかし，このようなセキュリティシステムの多くはパスワードや暗号鍵のような秘密の情報を生成することに依存している．この秘密の情報が盗まれたり，推測されることはセキュリティシステムが破られるのと等価である．

RFC1750 ("Randomness Recommendations for Security")に，パスワードや暗号鍵のような予測の困難な乱数性を持ったデータを生成するための技術や推奨項目が記述されている（2005年6月に RFC4086 へ更新）．

ここでは，RFC1750 の記述を中心に乱数の重要性と乱数の生成方法について解説する．

乱数の利用	ハードウェアによる乱数生成	ソフトウェアによる乱数生成
乱数性の評価

乱数の利用

• 乱数の必要性
  暗号システムにおいては，セキュリティの向上のために乱数を利用することが多い．
  代表的な乱数の利用例には以下のようなものがある．
  • パスワードの生成
  • 暗号鍵の生成
    共通鍵暗号および公開鍵暗号用の鍵
  • ＩＤ情報の生成
    重複しない識別子の生成
  • ランダム要素の付加
    ディジタル署名やデータの暗号化時に乱数情報を付加し，同じ鍵でも異なる出力を得る(解読の困難性を増す)
  
  このような秘密情報の生成には，ほとんどの場合何らかの形で乱数生成プロセスが用いられる．秘密情報を生成するために疑似乱数生成プロセスを用いることは，疑似セキュリティを実現することに繋がる． 特に，簡単な疑似乱数プロセスを使用した場合，セキュリティシステムに対する攻撃者は，秘密情報を生成した環境を再現することが容易になり，秘密情報を探索するための労力を大幅に削減することができてしまうことになる． そのため，疑似乱数の生成プロセスの選択に十分な注意を払う必要がある．
  セキュリティの目的のために予測が困難な乱数データを生成することは非常に重要であるが，難しい問題でもある．
• 乱数の生成
  乱数を発生させる方法には，物理的手段で発生させる方法(真性乱数)と算術式により発生させる方法(擬似乱数)とがある．
  • 真性乱数（物理乱数）
    ランダムな物理現象や特定のハードウェアを利用するもので，発生確率が平等，無相関，周期性が無いなどの特徴がある．
  • 擬似乱数（算術乱数）
    一定の算術式を用いて発生させるもので，次の性質が要求される．
    • 統計的一様性
    • 無相関性
    • 長周期性
    • 非線形性（予測不可能性）
  乱数データを得る比較的簡単な方法は，ハードウェアを利用することである．特に，量と質はそれ程高くある必要はない．最近のシステムは既にディスクドライバや音声入力のような高品質の乱数を発生に利用できるハードウェアを持っているものもある．
  複数のデータ源や低品質であるが多量の入力を持つ単一のデータ源からの低品質の乱数性を処理し，高品質の少量の乱数データを生成するために種々の計算手法が利用できる．
  ハードウェアによる乱数源が利用できない場合，種々のユーザあるいはソフトウェアによる乱数源が注意深く利用できる．一旦，十分な量の高い品質の種(数百ビット)が得られたならば，その種から暗号学的に強力な予測が困難な乱数データ列を計算する手法が利用できる．
• 要求される乱数量
  乱数データに対して要求される量は，一般にはそれ程多くはない．共通鍵暗号の鍵に対しては現状では最大でも 256ビット程度であり，通常は 128 ビットである(これは，将来の攻撃者が利用できる計算機能力によっても変わってくる)．一連の鍵が必要な場合は，強力な乱数種から暗号学的に強力な乱数列を生成する手段を用いることができる．数百ビットの乱数ビットが一日に一回生成できれば，このような手法に対しては十分と考えられる．たとえ，乱数ビットが 1 秒に 1 ビットしか生成できなくとも高度なセキュリティシステムには 200秒待つことは許される．
• 暗号利用での乱数に対する要求条件
  • 生成した擬似乱数列から多項式時間で生成式と初期値が推定できないこと
  • 過去に生成した擬似乱数列から以後生成する擬似乱数列が予測できないこと
  • 初期値として 128ビット程度以上のアドレス空間が必要

ハードウェアによる乱数生成

熱雑音や放射線の崩壊を生み出す源，高速な自走式の発信器などは，直接的な乱数源になる．これらは，僅かなハードウェア量であリ，計算機システムの標準部品として容易に組み込めるものである．さらに，回転ディスクあるいはそれに類似した機構を持つ任意のシステムは，十分な乱数源を持つと言える．このような僅かな付加的なハードウェアとそれにアクセスするソフトウェアが必要であり，有効であるという計算機ベンダの共通認識が重要と思われる．

攪拌のための最良の入力源は，空気の乱れによるディスクドライブのタイミングや熱雑音をもった音声入力のようなハードウェアのランダム性を持ったものである． しかし，それが実現できない場合他の可能性がある．これには，システムクロック，システムまたは入出力バッファ，user/system/hardware/network のシリアル番号，アドレス，タイミングおよびユーザ入力などが含まれる．これらのどれも，限られたあるいはある環境化では予測可能な値である．

上記の乱数源の幾つかはマルチユーザシステムでは強力なものになる．システムの各ユーザ自体がランダム性の源になるからである．しかしながら，パーソナルコンピュータのような小規模な単一ユーザシステムでは，攻撃者が同様な環境を構築することが可能である．これは，攻撃者が元々用いられたものと十分に相関の高い攪拌プロセスを用いて入力を生成でき，探索に利用できることを示している．

強力な攪拌関数を用い複数の乱数源を使うことが推奨される．これにより，特定の入力の弱点を克服することができる．例えば，ランダムなユーザのキー入力のタイミングと内容は数百ビットの乱数ビットを生成する．しかし，安全側の仮定がなされなければならない．例えば，キー入力の間隔については，ほんの数ビットの乱数性のみを仮定するなどである．

入力された文字やそのタイミングを攪拌した結果は，さらにクロック値やその他の入力と結合することができる．この戦略は，対象システムにおける入力の幾つかが非常に弱いものであったとしてもセキュリティに対する良い乱数性を生成する実用的で移植性の高いコードを生成する．しかし，それでも小規模な単一ユーザシステムにおける高度な攻撃には対抗できない．特に，攻撃者が過去における生成プロセスを観測できたならば．したがって，ハードウェアによる乱数生成が望ましいと言える．

将来的には，強力でポータブルな物理的予測不可能な乱数源を持つ乱数ジェネレータが現われると予想される．
現在利用されているランダム要素には，次のようなものがある．

• キー入力のばらつきの利用
• マウスの軌跡や移動速度の利用
• サウンド，ビデオ入力（雑音入力）
• 磁気媒体へのアクセス時間のばらつき
• OS提供デバイスファイル（/dev/random）

ソフトウェアによる乱数生成

信頼すべき乱数発生用のハードウェアがない場合，乱数データを取得する最善の方法は，大容量の相関の無いデータ源からランダムに入力を得て，強力な攪拌関数でデータを結合，攪拌することである．このような攪拌関数は，結合されるデータの一部が固定的あるいは予測され易いものであったとしても，データ源の乱数性を保存する．

乱数の一様性の向上方法には，次のような方法がある．

• パリティの利用
  入力ビット列のパリティを取る．
• Transition Mappingsの利用
  入力ビット列において任意の 00 または 11 のペアは取り除き、01 を 0 と 10 を 1 と置き換える．
• FFTの利用
  入力データをフーリエ変換する．
• データ圧縮の利用
  入力データを可逆な圧縮手法により圧縮する．圧縮が可逆なため，長い入力に対して存在していたと同じ情報量が短縮された出力に対しても存在する．

ソフトウェアによる擬似乱数(算術乱数)の生成方法には，次のようなものがある．

• 伝統的擬似乱数生成法
  線形合同法，平方採中法，線形フィードバックレジスタ(LFSR)法などがある．
  多くの伝統的な乱数生成方法は，決定論的な疑似乱数源を用いるものであり，これらは，種と呼ばれる値を用いて算術演算あるいは論理演算により数字列を生成するものである． しかし，これらの乱数列はシミュレーションの用途には十分かも知れないが，セキュリティアプリケーションに対しては，明らかに不適切である． 線形合同法などでは，乱数列の観測により将来の乱数列が予測できてしまう． また，初期状態が知られれば完全に予測されてしまうからである．
  
  線形合同法(Linear congruence pseudo-random number generator)
  次のような剰余演算で $n$ 番目の値 $V_n$ から $n+1$ 番目の値 $V_{n+1}$ を計算する．

  $V_{n+1} = (V_n \times a + b) \bmod c$

  ここで，$a$, $b$, $c$ はパラメータであり定数である．
  この乱数系列は，連続した4つの値 $V_i$ からパラメータ $a$, $b$, $c$ が求められるため，以後の乱数系列が予測できてしまう．
  
  線形フィードバックシフトレジスタ(LFSR)
  線形フィードバックシフトレジスタ(LFSR) は， $L$ ビットのシフトレジスタであり，その一端に任意の選択された複数のビット位置からのビットの排他的論理和を入力するものである． LFSR により生成される系列 $\{r_i\}$ は，次の関係を満たす．

  $r_i = a_1 r_{i-1} + a_2 r_{i-2} + \cdots + a_L r_{i-L}$

  ここで，$a_i$ は LFSR の結線状態を表し，$0$ または $1$ である．また，加算は $GF(2)$ 上の演算である．
  LFSR の出力特性は，$a_i$ の値により決定されるが，特性多項式

  $a(x) = 1 + a_1 x + a_2 x^2 + \cdots + a_L x^L$

  が $L$ 次の原始多項式のときに，系列 $\{r_i\}$ はM系列となり最も長い周期 $2^L -1$ を持つ．
  M系列では，ゼロ状態を除いて他の状態が1周期の間に全て現れるため，1周期当りの等頻度性や無相関性に優れている．しかし，線形合同法と同様に過去の乱数系列から未来の乱数系列が予測可能である．
  
  メルセンヌ・ツイスタ (Mersenne twister：MT)
  メルセンヌ・ツイスタのアルゴリズムは，一般フィードバックシフトレジスタ (GFSR) をひねって (Twisted)，調律した(Tempered) ものである（略称：TTGFSR）．考案者らによる実装が BSDライセンスで公開されている．
  以下の線形漸化式によって生成される． 　

  $X_{n+p} = X_{n+q} + X_{n+1} B + X_n C$

  ここで，$p$ は $2^p - 1$ が素数 (メルセンヌ素数)となるような数でありメルセンヌ指数と呼ばれる． 通常，$p = 19937$ が使われる（MT19937）．この時は，内部に 623個の 32ビット長の状態ベクトルを持つ $(19937 = 32 x 623 + 1)$．
  
  メルセンヌ・ツイスタ (MT19937) は，以下の特徴を持つ．
  • 長い周期 $2^{19937} - 1$ を持つ．
  • 高次元（623次元）に均等分布する． すなわち，出力中の連続する値間の相関性が無視できる程度である．
  • 出力の中のすべてのビットが統計的に十分ランダムである．
  • 十分高速である．
  
  メルセンヌ・ツイスタは，線形漸化式によって生成されるため予測可能である．また，一般的な疑似乱数生成器と比較して動作に必要なメモリ量（ワーキングメモリ）が大きい．
• 攪拌関数
  暗号アルゴリズム，ハッシュ関数を利用した乱数生成方式である．
  攪拌関数は，二つ以上の入力を結合し，各出力ビットがそれぞれすべての入力ビットの異なる非線形関数になるような出力を生成する関数である． 平均的には，任意の入力ビットを変化させると，出力ビットの半分が変化する． しかし，その関係は複雑で非線形であるため，どの特定の出力ビットも任意の入力ビットが変化したときに変化することが保証されるものではない．
  共通鍵暗号は，入力(鍵とデータ)を攪拌する関数として利用できる． また，SHA, MD5などのハッシュ関数(メッセージダイジェスト関数)も攪拌関数として利用できる．
• 暗号学的に強いシーケンス
  一連の乱数データ列が生成されるとき，攻撃者はその乱数データ列の値を知り得ることが予想される．一般的には，知り得た値から他の乱数データ値を予測できるべきではない．
  強い乱数種を使い暗号学的に強力な手順により乱数データ列が生成される必要がある．また，乱数ジェネレータの内部状態を明らかにしてはならない．乱数データ列の各値が以前の値から決定論的に計算されるとき，任意の値が明らかになれば将来のすべての値が決定されてしまうためである．これは例えば，各値が以前使用した値の固定的な関数であるときには，その関数が非常に強力な非可逆なメッセージダイジェスト関数であったとしても真実となる．
  強い乱数列を達成するための伝統的な方法は，乱数種を結合することによって得られた値をハッシングし，その値を攻撃者が得られるジェネレータの状態量を制限するようにマスクすることである．
  ランダムな鍵と種を持った暗号化アルゴリズムを使うことができる．暗号化出力の一部あるいはすべてを次の繰り返しに対する暗号化入力にフィードバックする．適切なフィードバック手法が暗号化アルゴリズムとともに推奨される．
  
  暗号学的に安全な疑似乱数生成器とは，
  • $n$ ビットの入力を $m$ ビット $(m \gt n)$ に拡張する決定性多項式時間アルゴリズム ：$g$
  • 長さ $m$ のビット列の集合：$U_m$
  • $g$ の出力の集合 $g： (U_n)$
  とするとき，
  • $|g(U_n)| / |U_m| \le 2^n/2^m = 1/2^{(m - n)}$
  • $g(U_n)$ と $U_m$ を多項式時間アルゴリズムにより識別不可能
  となるものである．
  
  Blum Blum Shub 乱数ジェネレータ
  現在，その強さが証明されている最も強力な乱数ジェネレータは，Blum Blum Shub ジェネレータと呼ばれるものである．大きな素数を用いべき乗剰余演算を利用するものである．単純であるが，計算量は従来の乱数ジェネレータに比べればかなり大きい．これは，セッション鍵を作るような比較的頻度の少ない用途に対しては重大な欠点にはならない．
  
  二つの大きな素数 $p$ と $q$ を選ぶ．そのどちらも $4$ で割ると $3$ 余るものとする． また，$n = pq$ とする． このとき，$n$ と互いに素なランダムな数 $x$ を選ぶ．乱数ジェネレータの初期種と乱数系列を計算する方法は次のようになる．

  $s_0 = x^2 \bmod n$

  $s_{i+1} = {s_i}^2 \bmod n$

  ここで，各 $s_i$ の下位数ビットのみを用いるようにする．最下位ビットのみを用いるのが常に安全である．
  $\log_{2} (\log_{2}(s_i))$ 個以上の下位ビットを用いないならば，この方法により生成されるビット列を予測することは $n$ を素因数分解するのと同じ困難性があることが証明されている．初期値の $x$ を秘密にする限り，$n$ を公開することもできる．
  このジェネレータの興味深い点は，任意の s の値を直接計算できることである．

  $s_i = s_0^{2^i \bmod ((p-1)(q-1))} \bmod n$

  これは，このように生成された複数の鍵を持つアプリケーションにおいて，そのすべての鍵を保存する必要がないことを意味する．各鍵はそのインデックスから初期値の $s$ と $n$ を用いて順次生成できるからである．
• /dev/random
  OS が提供するランダムデータ収集用デバイスファイルであり，一般に次のように乱数データを生成する．
  1. デバイスドライバ等が収集したランダムソースをエントロピー・プールに保管する．
  2. エントロピー・プールにデータが入力されるとデータを攪拌し，ランダム性の量を推測する．
  3. 読み取り要求があると，エントロピー・プールのデータをハッシュしてランダムデータとして出力する．エントロピー・ プールが空の場合は，周囲からノイズが集まってくるまで，呼び出しをブロックする．
  この乱数生成器は，周囲で発生するノイズをデバイスドライバや他の情報源から収集して，エントロピー・プールに収めている．/dev/random にアクセスするとエントロピー・プールにあるノイズから推定されたビット数の範囲でだけランダムな値が返される．/dev/urandom でアクセスして大きな値を要求すると，エントロピー・プールが使い果たされても値が返る．乱数を暗号化の目的で利用する場合 (例えば，鍵の生成) には，/dev/random を使うべきである．

乱数性の評価

FIPS PUB 140-2 に乱数列に対する評価基準が示されている．

20,000ビットの乱数に対して，以下を満足することを要求している．

• 乱数における $1$ の数 $x$ が，$9,725 \lt x \lt 10,275$ の範囲にある．
• 乱数を $4$ ビットずつに分けたそれぞれの値 $i$ の生起数を $f(i)$ とするとき，

  $x = (16/5000) \times (\sum_{i=0}^{15}[f(i)]^2) - 5000$

  なる $x$ が $2.16 \lt x \lt 46.17$ を満たす．
• $1$ または $0$ の連続する個数 (run) が以下に示す範囲にある ($1～6$ の run に対して)．
  
  

  Length of Run	Required Interval
  1	2,325 - 2,685
  2	1,114 - 1,386
  3	527 - 723
  4	240 - 384
  5	103 - 209
  6+	103 - 209

• $1$ または $0$ の連続する個数の最大値が $26$ 未満である．

／