安全性

第5章 認証キーの生成・管理のための「多次元インデックス法」の提案 ト数を知っていれば，それを使って，式(2.19)を計算して内部状態X₀を求ま る．求められたX₀から式(2.4)を計算し，高い確率で，その2値系列のすべて のビットを再生できる．

ただし，式(2.4)が生成する2値系列の下位ビットから上位ビットを求めるこ とができない（節5.4.1①）．この性質は後に多次元乱数生成システムを構成す る際，生成したN ビットの乱数列の間，互いに推測できないことにする操作の 中に利用される．

③2値系列の最大連

補題3.1（p.26）より，式(2.4)は開区間(0,2^N−1)において単調増加である．

従って，計算精度Nビットのときの0の最大連はX₀ = 1のときにえられる．す なわちX₀ = 1から式(2.4)を計算して，X_l ≥2^N−1のとき，0の最大連lが得ら れる．計算精度N を変え，数値計算を行った結果，l ≤N/2であった．式(2.4) から生成される2値系列が有する0の可能な最大連は，N/2以下であることを 意味する．N = 64,128のときの例を付録Bに示す．

この性質は，式(2.4)から生成される2値系列が持つ組合せの可能性を制限し ている同時に，この2値系列からNビットを切り出し，新たな初期値にする場 合，その初期値が不動点になる値（0,2^N−2,2^N−1,3×2^N−2）にならないことを 保証している．

なお，`_Nにおいての不動点に落ち入る可能な初期値の検出方法は3.3節で示 した．したがって，それらを除外することも可能である．

5.4.2 ^{安全のための実装}

整数ロジスティック写像を「多次元インデックス法」に適用する安全な方法 を示す．計算精度は管理用Rと同じ，N ビットとする．

①管理情報を乱数生成パラメータへ変換

先ず，管理用N ビットのRを式(2.4)の初期値X₀とする．Rは不動点に落 ち入る値を除外する．

次に，多次元インデックス情報iを次元数Kの次元座標i₁, i₂, . . . , i_k, . . . , i_K

5.4. 安全性 に変換する．

初期状態k = 0にして，多次元座標値i_kに従う新たな初期値の繰り返し生成 を行う．

②多次元座標に基づく写像の計算

k =k+1にし，X₀を初期値として，式(2.4)をN i_k回写像し，そして写像しな がら，NビットのBkを生成する．Bkの各ビットの構成は上位からbk,0bk,1. . . bk,N−1

であり，式(3.20)にしたがってbk,0 =YN i_k, bk,1 =YN i_k+1, . . . , bk,N−1 =YN i_k+N−1

のように計算される．k = 1のときの例を図5.3に示す．

図 5.3: 安全のための実装例（k = 1）

③出力乱数間の推測可能性を断ち切る

節5.4.2②のように生成されたBkは上位座標（ビット）による下位座標への

推測が可能である．その推測可能性を断ち切るために次の計算を加わる．即ち，

第5章 認証キーの生成・管理のための「多次元インデックス法」の提案 出力R_iは常にB_kとの間にNビットの間隔を持つようにする．こうすることに より，捨てられたNビットの情報を遡ってB_kを推測することができなくなる．

B_k を式(2.4)の初期値X₀ とする．X₀ を初期値として，式(2.4)をN 回写 像し，そして写像しながら，N ビットのR_{i1,i2,... ,ik}を生成する．R_{i1,i2,... ,ik} の各 ビットの構成は上位からr_k,0r_k,1. . . r_k,N−1であり，r_k,0 = Y_N, r_k,1 = Y_N+1, . . . , rk,N−1 =Y2N−1として計算される．k= 1のときの例を図5.3に示す

ここに，N ビットのR_{i1,i2,... ,ik} はk = 1のとき，R_i1 であり，k = 2のとき，

R_i1,i2 であり，. . .，k =Kのとき，R_{i1,i2,... ,iK} である．

④繰り返し作業による多次元乱数生成

NビットのR_{i1,i2,... ,ik}に対し，k < Kであれば，同じように，R_{i1,i2,... ,ik}を式 (2.4)の初期値X₀とし，節5.4.2②からの計算手続きを繰り返す．k =Kであれ ば，R_{i1,i2,... ,iK} を多（K）次元キーR_iとして出力する．

5.4.3 ^{安全性について}

節5.4.1から，図5.2に示す二次元に配置されているままで構成される「多次

元インデックス法」は安全ではない．これに対し，節5.4.2②，節5.4.2③の処理 により，提案法は計算量的に安全であることがわかる．下位状態からmステッ プ上位にある状態を得るには，2^m個ある可能な状態を式(3.19)で計算して確認 する必要がある．提案法（節5.4.2③）はR_i を出力する前に，N 回写像した．

それは，m=N としたことである．

従って，R_iとiから式(3.19)を用いてRを計算するよりも，Rを推測してR とiを用いてR_iを計算し，一致するR_iを見つけ出すことが容易である．即ち，

Rのあらゆる可能な値に対する総当りの手法である．

それは計算機の計算能力に応じたRのビット長（キーの長さ）を選ぶことに より，提案法を計算量的に安全なシステムにすることができることを意味する．

また，節5.4.1③に述べた式(2.4)から生成される2値系列（Y_t）の特性は初 期値の繰り返す生成が特徴である多次元インデックス法において，初期値を除 けば，0,2^N−2,2^N−1,3×2^N−1となるキーを生成することはない．