第 5 章 認証キーの生成・管理のための「多次元インデックス法」の提案 70
5.3 評価
5.3 評価
節5.2.1で考案した三つの条件に適した擬似乱数生成法として，ロジスティッ
ク写像式(2.2 p.8)を用いた閾値法はよく知られている[3,14]．
式(2.2)を有限桁の計算精度で計算するとき，整数を用いた固定小数点で計算
する方法がある（2章，p.16整数ロジスティック写像）．整数ロジスティック写 像`N での計算は計算精度を容易に拡張できる．整数型の演算は計算機システム の種類が異なっても，同じ入力であれば同じ出力が得られる．
提案法では，定義2.1で定まる式(2.4)で計算されるXtに対し，定義3.6で定
まる式(3.20 p.32)にしたがって2値系列を生成する閾値法を用いる．本節では，
そのときの効果について考察する．
5.3.1 生成速度
「多次元インデックス法」が用いる擬似乱数生成法の2値系列r0r1. . . の生
成速度をS bps（ビット/秒），初期値をR，次元数K，生成・管理するNビッ
トのキーの総数をMとし，2進数列を生成する以外の作業時間（例えば，ビッ ト列を切り出す時間など）が十分に小さく，計算しないことにする場合，初期 値Rを用いた任意の位置座標iにあるN ビットのキーRiの生成に要する時間 について考察する．
計算値
節5.2.4に示したように，次元数Kの多次元インデックス法は位置座標i(i1, . . . , iK)に基づき，Nビットの初期値RからRiを生成する．従って，任意のNビッ トのRiを生成するに必要な時間TRiはTRi = (K+i1+. . .+iK)×N/Sで計算 される．
ここに，次元数K，総数M = M1 ×. . .×MKのN ビットのキーの生成に 必要の時間の最小値，最大値，平均値をそれぞれTminK , TmaxK , TaveK とするときの 値を示す．明らかに，最小値はi1, . . . , iKが全て最小値（0, . . . ,0）となるとき，
最大値はi1, . . . , iKが全て最大値（M1−1, . . . , MK −1）となるとき，平均値 は全てのRiの生成時間の和にその総数Mで割って計算される．従って，それ ぞれ以下のようになる．
第5章 認証キーの生成・管理のための「多次元インデックス法」の提案
TminK = N K/S
TmaxK = N(M1+· · ·+MK)/S TaveK = N
QK j=1Mj
MX1−1
i1=0
· · ·
MXK−1
iK=0
(K+i1+· · ·+iK)/S
= N(K+M1+· · ·+MK)/(2S)
一般に，Mのサイズは大きいほうが望ましいが，K = 1のとき，提案法即ち 従来法に相当する一次元インデックス法では，Mを大きくすることができない．
しかし，K ≥ 2の場合，提案法によって，2値系列の生成速度Sの相対的に小 さい擬似乱数生成器でも，管理するキーRiの総数Mが大きい中の任意の1つ を高速に生成（再生）することが可能になる．
実生成速度の確認
節5.3.1に2値系列の生成速度Sが与えられたときの多次元座標iに位置する
キーRiの生成に要する時間を示した．ここでは，2進数列を生成する以外の作 業時間が十分に小さいので，計算には含めていない．
表 5.1: キーの生成時間の比較(Unit: msec)
i(i1 ∼i14) t0 t
0, ...,0(Min) 0.366 0.421 4, D,4,3,2, C,4,4,3,0, A,7,7, B 2.560 2.781 F, ..., F(Max) 5.851 6.234 (Genuine Intel(R) 1.50 GHz)
このような近似的に計算された生成時間を推測時間(t0)とし，実際に汎用PC を用いて計算にかかった時間を実測時間(t)とする．実験は整数ロジスティック写 像から生成される2値系列が有する非周期状態長が十分に長く得られるように，
計算精度N = 128ビットとする．また，K = 14，M1 =M2 =. . .=MK = 16 にして，2値系列の生成速度が4.9 Mbpsの時の両者の最小値，最大値などの結 果を表5.1に示す．次元座標iの値は16進表示である．両者は近い結果である．
5.3. 評価
5.3.2 初期値敏感性の確認
方法
多次元座標iを固定にして，初期値R(X0)に微小な変化を与え，生成される2 つのRiの間のビット間ハミング距離の統計量のχ二乗値の分布を理論値と比較 することにより，2つのRiの間に無関係であることを確認し，「多次元インデッ クス法」において，整数ロジスティック写像を用いたときの初期値敏感性の存 在を確認する．
手順
N = 128, K = 14, M1 =. . .=M14= 16にする．
1)iとRをランダムに選び，Riを生成する．
2)iとR0を用いて，R0iを生成する(R0 =R+ 1)．
3)RiとR0iの間のハミング距離hを計算する．1
4)手順1)∼3)をj = 1000回繰り返し，hの頻度分布f(h)を集計する．
5)理論値に対するf(h)のχ2値νを計算する．2
6)手順4),5)を1000回繰り返し，χ二乗値νがそれぞれν <8.26,10.85,15.45, 19.34,23.83,31.41,37.57（それぞれ自由度20のときのP 値1%,5%,25%,50%, 75%,95%,99%に対応する（[21] 3.3節））に入る数を数える．
結果の確認
節5.3.2.の手順6)で計測し得たχ二乗値νの分布を表5.2に示す．比較は，4 章でのχ二乗検定と同様に，χ二乗値の経験分布が理論分布に対する乖離をあ らわすχ二乗値を求め，自由度7，有意水準0.01で行う．χ二乗値が<18.48で あれば，経験分布が理論分布にしたがっているとする．経験分布が理論分布に 対する乖離をあらわすχ二乗値が，3.32で，<18.48である．従って，RiとRi0
1整数ロジスティック写像`N において，R0iと(R0 =R+ 1)が一つのホール（3.2節を参照）
に属している場合を除いた．
2RiとR0iの生成がランダムであれば，f(h)の理論値f(H)がf(H) =j×N!/((N−H)!H!) となる(H = 0,1, . . . ,128)．尚，χ二乗値の計算においてのhのカテゴリ数は頻度数の小さい h≤54とh≥74のものをそれぞれ1つのカテゴリに統合して，≤54,55, . . . ,73,≥74の21に した．
第5章 認証キーの生成・管理のための「多次元インデックス法」の提案 の間に無関係であることと判断できる．「多次元インデックス法」において，整 数ロジスティック写像`N を用いたときの初期値敏感性の存在を確認できた．
表 5.2: ハミング距離の頻度のχ二乗分布（Ri, Ri0） ν < 8.26 10.85 15.45 19.34 23.83 31.41 37.57 理論値 10 50 250 500 750 950 990 計測値 11 50 226 496 775 956 993
5.3.3 近傍座標 i 間の R
iの無相関性
方法
節5.3.2と同じ方法である．Rを固定にし，iに微小な変化を与え，生成され
る2つのRiの間のビット間ハミング距離の統計量のχ二乗値の分布を理論値と 比較することにより，近傍座標i間のRiの無相関性を確認する．
手順
節5.3.2の手順の内容に2)，3）だけを以下のように変える：
2)i0とRを用いて，Ri0を生成する（if (i <15) then(i0K =iK+ 1) else(i0K = iK−1)）．
3)RiとRi0の間のハミング距離hを計算する．
結果の確認
計測し得たχ二乗値νの分布を表5.3に示す．比較は，4章でのχ二乗検定と 同様に，χ二乗値の経験分布が理論分布に対する乖離をあらわすχ二乗値を求 め，自由度7，有意水準0.01で行う．χ二乗値が<18.48であれば，経験分布 が理論分布にしたがっているとする．経験分布が理論分布に対する乖離をあら わすχ二乗値が，1.41で，< 18.48である．従って，RiとRi0 の間に無関係で あることは判断できる．提案法において，`Nを用いたときの近傍座標i間のRi
が線形的な相関関係が持たないことを確認できた．
5.3. 評価
表 5.3: ハミング距離の頻度のχ二乗分布（Ri, Ri0） ν < 8.26 10.85 15.45 19.34 23.83 31.41 37.57 理論値 10 50 250 500 750 950 990 計測値 9 53 264 512 745 946 992
5.3.4 非周期空間サイズ
ここに，「多次元インデックス法」が管理する総数MのNビットのキーRiの 中に，同じものが存在しないとき，そのサイズを非周期空間サイズと呼ぶ．
「多次元インデックス法」は`N を用いた時の周期性は基本的に`N が有する 周期性に依存すると考えられるが，繰り返して初期値を更新することで、`Nが 持つ複数の周期系列の複合周期になる可能性がある（3.4節を参照）．ここで，
N ビットのキーの生成可能なサイズM の多次元空間にあるキーに対する全件 検索を行う．同じキーが検出されれば，ループに入ったことと判断できる．
検索は計算精度N を40,44,48ビットの3通りにし，対応する多次元空間サ イズをM = 2N/2−4とした．それぞれの次元数Kを2通りに与え，各次元のサ イズMkを同じ値（M1 =. . .=MK）にした．各ケースに初期値を無作為に選 び，50回検索してループが検索された回数を表5.4に示す．
表 5.4: 計算精度と非周期空間サイズ
計算精度N(bit) 40 44 48
多次元座標空間サイズM 216 218 220 次元数K 8 4 9 6 10 5 各次元サイズMk 4 16 4 8 4 16
ループ検出回数 19 22 18 25 18 27
表5.4から，同じ空間サイズにおいては次元数Kの大きい(次元サイズMkの 小さい)方がループの検出数が少ないことが分かる．また，表5.4には示してい ないが，検出された同じキーの連続している数が全てMkよりも少ないことか ら，ループは次元Kで初めて入ったと判断できる．仮に次元K−1に既にルー プに入ったのであれば，次元KにはMk個の同じキーが並んで検出されるはず である．
第5章 認証キーの生成・管理のための「多次元インデックス法」の提案 検索結果に基づき，我々は計算精度N（例えば128）ビットのときの管理す るRiの総数（空間サイズ）M = 2N/2−4（例えば260）が非周期である確率は0.6 程であり，次元数を更に一次元減らしたときの空間サイズ(例えば256)は高い 確率で非周期的であることを推測できる．従って，適切な次元数の設定により，
一定の非周期空間サイズを確保することは可能となる．
5.3.5 パラメータ N, M, K(k) について
計算精度N と次元サイズM
計算精度Nのとき，ある初期値X0から生成できるキーの総数M を決める．
そのとき，とりうる値の数は2N 通りあるが，3章で議論したように，ある初期 値（種）X0から生成できる非周期状態の長さは5×2N/2−3に近いことから，一 次元インデックス法の場合，M が非周期状態である大きさは5×2N/2−3/N と 推測される．この値は節5.3.4の数値実験結果と近い．
次元数Kと次元サイズMk
Mが一定のとき，Kを大きくすれば，Mkの平均サイズが小さくなり，Riの生 成速度が速くなる．Mkは各次元の座標空間のサイズを決める(k = 1,2, ..., K)． また，Riの生成速度に影響を与える．個別のMkのサイズが極端に大きいとき，
一次元生成法で見たように，この次元においての平均生成時間は長くなり，Ri の生成速度が極端に遅くなることもある．
分類上，Mkはk番目のクラスのサイズを表しており，適切なMkのサイズは 生成速度だけでなく，分類上の便宜さと照し合せて，決める必要がある．
なお，経験的にKの設定は，Mkのサイズを4 ∼ 16にするのが適切と思わ れる．