実数 シフ ト乱数生成法のメッセージダイジェス ト性 について
谷 ロ ネL 偉 *
The Message-Digest Property of the Shift-Real Randorn Nurnber Generator
Hirotake Ya,cucnr
最近考案 された非代数的非再帰的擬似乱数生成法である実数 シフ ト法のアルゴリズムを利用 して、新 しくメッ セージダイジェス ト関数が作成可能であることを、関数出力の統計的検証を通 じて示す。
S R 法 によ るメ ッセー ジダ イ ス トの概要
メッセージダイジェス ト関数 (MD関 数)は 、任意長の入カ メ ッセー ジに対 し、 その要約 を出力す る関数である。一般 に、その出力 は固定長であ り、二様乱数性を要求 されることが多 い。 ここで一様乱 数性 とは、一連の MD関 数の出力値を並べてい くと、 どの値 もまった くでた らめにかつ同程度 に現れ るということである。 また、情報セキュ リティの観点か らは、出力するデータ長を長 く取 って (128あ るいは 160ビ ッ ト以上)、同 じ出力値を もつ異 なる入カ メッセージが見つけに くい、 とい う性質 も要求 されている。 これ らのことを考慮す ると、MD関 数を、1つ の入カ メッセージに対 して 1も の乱数値 を 出力する擬似乱数発生器 として とらえることができる。MD関 数 はハ ッシュ関数 ともいわれ、 著名 な
ものとして MD5,SHA̲1,RIPEMD̲160な どがある([4])。
我々は、 [1,2,3]で 非再帰 的 0非 代数的な擬似乱数生成法 と して、実数 シフ ト法 (thc Shi■―Rcal method,SR法 )を 提唱 した。本論文の目的は、 この SR法 のアルゴリズムを利用 して、新たにメッセー
ジダイジェス ト関数が作成可能であることを示す ことである。
実数 シフ ト法 は、次の単純実数 シフ ト計算 (the simplincd shift̲rcal computation,SSR計算)が 基本 である:
g ( * ) : t c ' r i . ' x ' . . ' x . x , x e [ 1 , 2 )
24πλ: = π た̲ 1 × χ, た = 1 , 2 , 24,
ヵを 1回 計算するごとに、πたを表す倍精度変数の
i)仮 数部 の全 ての ビッ ト値 を 1ビ ッ ト左 に シフ トし、
ii)指数部 は … 0×20と な るよ うに設定す る。
﹄日
要
を
2 0 1 = 1
と倍精度計算 し、
十二重大学教育学部数学教室
一‑59‑―
谷 ロ ネL偉
また、実際の乱数値 としては、κを変化 させ、対応す る計算結果 24から、上位 3桁 を棄 て続 く4桁 を 取 り出す ものであ った。我 々は、 この実数 シフ ト計算中の (i)の左 シフ トを行 った結果生 じる右端 ビッ トの空白に注 目す る。すなわち、上述の ssR計 算ではこの右端 ビッ トに 0を 入 れているが、我 々は経 験上 ここに何を入れて も乱数特性があまり変わ らないことを知 っている。 よって シフ トのたびごとに生 じるこの空いた ビッ トに、予め与え られている入カ メッセージを構成するバイ ト列の ビットを順次埋め 込んでいくことを繰 り返せば、入カ メッセージの情報が埋め込 まれた形の倍精度変数値 πが得 られる。
この2を 新たにκと考えて改めて SSR計 算を行えば、入カ メ ッセージの情報が含 まれた乱数値が得 ら れることになる。 このように して倍精度変数を使 った SSR計 算で一様乱数が得 られることが分かれば、
同様のアルゴ リズムを、多倍長の整数計算で行 うことにより、例えば 160ビ ットの出力を持つメッセー ジダイジェス ト関数を実現することも可能である。本論文では、 この意味で、出カ ビットは少ないもの の、今までの我々が使用 した乱数検定 プログラムがそのまま使える SSR計 算 に基づいた MD関 数 に対 象を絞 って、一様乱数性の検定を中心 に考察を進めてい くことにす る。
メ ッセー ジダイ ジ ェス トの アル ゴ リズム
SR法 のアルゴリズムに基づいた MD関 数作成のアイデアは上述のとお りであるが、実際の計算 にお いては、1ビ ットずつ扱 うのでは能率が悪いので、一度 に 1バ イ トの入カデータ情報を埋め込 むなどの 工夫を行 うことになる。 また、埋め込み過程で使われる乗数 χを固定 したままでは特性が偏 るので、定 期的にχの値を変える必要がある。SR法 のアルゴリズムを用いた MD関 数の具体的なアルゴ リズムは 以下のとお りである。
変数
SSR計 算のκに相当する倍精度変数を Xと す る。
この Xに は、 [3]に述べ られている関数 nextxOに より、値が順次セ ットされてい く。
SSR計 算の 2に 相当す る倍精度変数を Uと する。
この Uに 、入カ メ ッセージの情報が埋め込 まれてい くことになる。
変数の初期化
Xを SRIni(0。0); X=nextXO;に より初期化す る ([3]参照)。
Uに は 1.2718281828459 を入れてお く。
入カ メッセージの埋 め込み
(1)Uの 仮数部を 8ビ ット左 シフ トす る。
(2)入カ メッセージの 1バ イ トを読み、 Uの 仮数部の b25〜b32とXORを とる。
(3)X*Uを 作 り、Uに 保存す る。
(4)Uの 指数部を ×20に す る。
埋め込みプロセスの繰 り返 し
上述 (1)〜 (4)を 、入カデータが無 くなるまで繰 り返す。ただ し、Xを 8回 使 うごとに (=入 力 データを 8バ イ ト処理す るごとに)、nextXOに よりXを 更新する。
‑60‑
メ ッセージダイ ジェス トの作成
最終的 に得 た Uを 、SSR計 算 の Xと して K改 良 SSR計 算 を行 う。 ただ し繰 り返 し回数 は 64回 とす る。得 た値 の最初 の 5桁 を棄 て続 く8桁 を メ ッセ ー ジダイ ジェス トと して採 用 し、 SSR̲MD 値 とい うことにす る。
メ ッセー ジダイ ジェス ト値の一様乱数性 の検証
乱数の特性を検証するには、多量の乱数が必要である。 このため、整数 πを4バ イ トで表 し、 これを
1つ の 入 カ メ ッセ ー ジ Ms(bと す る。 MSGπ に 対 して 、 10進 8桁 の SSR̲MD値 ″1あ 魂 残 J5魂 ′7ご8を
求め、 この乱数特性を [3]で使われた方法で検定す る。具体的には、8桁 MD値 を上位 4桁 ごl J2ご3ご4、
下位 4桁 グ5魂J7′3の 2つ に分割 し、それぞれについて 20000個の乱数値 に対する次の 7種 類計 10の検 定を危険率 0。05で 行 う (詳細 は [3]を参照のこと):
[検定 Ⅱ]文 字 0〜9の 出現頻度のχ2検定、
[検定 Ⅲ]文 字 0の 出現間隔のχ2検定、
[検定Ⅳ]乱 数値の KolmogOrOv̲Smirnov検定 +お よびκ )、
[検定 V]単 純上昇連および下降連 テス ト、
[検定 Ⅵ ]4枚 の 0〜 9カ ー ドによる古典 ポーカーテス ト、
[検定Ⅶ ]遅 れ 1お よび 2の 系列相関テス ト、
[検定ⅥⅡ]衝 突 テス ト。
そ して仮説が棄却 された回数 ε(0<ι <10)を 数える。 この操作を 1000回繰 り返す。各検定が危険 率 0.05で独立 に行われると仮定すれば (註:この仮定 は厳密 には正 しくない),θの分布 は二項分布 Bづπ (10,0.05)になるので、実際に得 られたεの分布 と対照 して χ2検定値 (CHITEST)を 求 める。
結果 は、以下のようになる。
ιの値 ⇒ 0
607 602 598。7
1 3 0 7 3 0 5 3 1 5 。1
2 76 84 74,6
> 3 10 9
CHITEST
上位 4桁 下位 4桁
0。908899 0.559416
B i n ( 1 0 , 0 . 0 5 )
11.5危険率 0 . 0 5 に比 して C H I T E S T の 値 はかな り良い結果 となっている。 また、各検定 の棄却 回数 は次 の とお りである:
検定 ⇒ 上位 4桁 下位 4桁
(Ⅱ ) (Ⅲ ) (Ⅳ )
60 51 42 48 51 42
47 48 56 49 54 58
(Ⅳ ) (V) (V) (Ⅵ) (WⅡ ) (ヽ Ⅱ)(MII) 計
55 45 40 47 491 59 52 41 46 500
危険率 0。05の検定を 1000回行 った結果であるか ら、各検定 とも妥当な値を示 しているといえよう。
上述の検定では、入カ メッセージがすべて 4バ イ トであ ったが、MD関 数 の実際の入カ メ ッセー はいろいろな長 さを持 っている。我々の身近 にある多量のメッセージ源 としてはコンピュータのファイ ルがあるので、我々が使用 しているパ ソコン (Winodows Mc)の全 ファイルを入カメッセージとして、
SSR―MD値 の特性を調べてみた。入カ メッセージ数 (全ファイル数)は 30320であ り、 この うち入力
‑ 6 1 ‑
谷 ロ ネL偉
メ ッセー ジ長が同 じで、対応す る SSR̲MD値 も同 じになる (重な る)フ ァイル数 は 3974で あ った。 こ れ らは、同一 ファイルが別 のデ ィレク トリにあ った り、名前 を変 えて保存 されてい る もの と思 われ る。
これ らを除 いた 26346個 の フ ァイルにつ いて、入カ メ ッセージ長 が異 な るが、SSR…MD値 が重なるファ イル数 は 5で あ った (重な りの度合 いはすべて 2)。 これ らは偶然 に SSR¨MD値 が同 じにな った もの と 思 われ る。 この重 な り数が妥 当な ものであ るか どうかの見 当をつ けるために、衝突 回数 の理論確率お よ び Borlandの フ リー版 Cコ ンパ イ ラー bcc32で 8桁 の乱数 (4桁 舌L数を 2つ 結合 した もの)を 26346個 作成 し、 その衝突回数 (乱数 の重 な り回数)を 調べ ることを 1000回繰 り返 した ときの、 衝突 回数 の分 布 を見てみ ると次 のよ うにな る。
衝突 回数 0 b c c 害1合 .030 理論確率 .031
2 3 186 .209 187 .217
5 6 7 以 上 134 .080 .057
131 .075 .063 11 1 1 1 0 8
4 193 188
これか ら見 ると5と いう値 は、やや多いが特に問題 とする値ではない。
[検定 Ⅱ]〜 [検定 VIII]の 7種 類 10検定を、先 ほど得た 26346個の 10進 8桁 SSR̲MD値 の うちの 最初の 20000個に対 して適用す ると以下のようになる。
検定 ⇒
上位 4桁 下位 4桁
(Ⅱ )
(>0.05)
0。7652 0。2642
(Ⅲ ) (>0.05)
0.2939 0.996
(Ⅳ ) (Ⅳ )
(<1.2239)
0。7354 0。 891 1.718 A O。 3394
検定 ⇒ (V) (V) (Ⅵ ) (>0,05) (>0.05)
上位 4桁 0.0588 0.8069 0.1541 下位 4桁 0.933 0.639 0.02599△
検定 ⇒ (ヽ彊)
( [ ‑ 0 . 0 1 4 1 9 , 0.009878
‑0.001655
(ヽ狂) 0.01409])
(MII) (<62) 60 47 上位 4桁
下位 4桁
‑0.001954 0.0000635
(検定番号の下 の ()内 の数値 は、危険率を 0.05と した場合の仮説が棄却 されない範囲で あ る。)各 検定を 1回行 っただけの結果であることを考えると、妥当な ものといえよう。
ま とめ
実数 シフ ト法のアルゴリズムを利用 した上述のメッセージダイジェス ト関数 は、検定結果を見る限 り、
一連の入カメッセージに対 して一様乱数を生成 しているものと判断される。 したがって、今後、アルゴ リズム中に使われている不動小数点演算をすべて多倍長の整数演算 に置 きかえることにより、十分な出 カデータ長を もつメッセージダイジェス ト関数が作成可能であると考え られる。同時に、情報 セキュ リ
ティの観点か ら、 このメ ッセージダイジェス ト関数の安全性 について も理論的な考察を高めてお くこと が必要である。
―‑62‑―
参考 文 献
[1]Yaguchi,H.:Randomness of Horner's rule and a new method Of generating random numbers.M MethOds and Appl.,V01。 6(2000),61‑76.
[2]Yaguchi, H.: Construction of a 10ng― period nOnalgebraic and nonrecursive pseudOrandOm number ヽ4 o n t e C a r l o N 〔e t h o d s a n d A p p l . , V o l . 8 ( 2 0 0 2 ) , 2 0 3 ‑ 2 1 3 .
[3 ]谷 口礼偉:数値計算誤差 と乱数生成。神戸大学理学部数学教室、2001.
[4 ]暗号技術検討会:2 0 01年度報告書. 経 済産業省 ・総務省、2002.
―‑63‑
