整数ロジスティック写像を用いた乱数生成法とその応用 Randam Numbers Generation Method and The Application By Integer Logistic Map

博士論文

2011

カオスの研究は，約100 年前（ポアンカレ）からとされ，1970 年代から盛んになり，多くの成果を得るようになった．「カオスの最大の応用は擬似乱数にある」と言われるほどカオスの擬似乱数生成への応用が高く期待されている．その中，カオスを生成する関数で，ほとんどのカオスの入門書に紹介されているロジスティック写像xt+1 = 4xt(1 ? xt) に対する研究成果が多く発表されている．しかし，カオスに関する理論的な研究成果が多く得られているにもかかわらず，幅広く産業技術としてのカオスの応用システムはまだ見られていないのが現状である．ほとんどのカオスに関する研究は，実数で定義，計算されるカオス時系列の性質に対するものに対し，産業技術としてのカオスの応用は多くの場合，有理数（コンピュータ）で計算されている．実数の計算で得られるカオス時系列の性質は，必ずしも有理数の計算で得られる時系列が有する性質と一致するとは限らない，むしろ，基本性質は異なっていることは一般的であろうと考えられる．有限計算精度で生成した時系列はいずれ周期に落ち入るため，原理的にはカオスにならない，擬似カオスと称される．従って，カオスを産業技術へ利用するには，まず有限計算精度の計算で得られる時系列が有する性質を解明する必要がある．カオスを産業技術として応用するとき，多くの場合に同じ入力に対し同じ安定した出力が求められる．このような再現性を持つ比較的に安価なシステムはデジタル（コンピュータ）システムである．カオスは実数で定義されている．コンピュータでの無理数の計算は近似計算で浮動小数点演算法を用いる．しかし，安価な産業用計算機（マイクロコントローラ）は浮動小数点をサポートしていない．また，浮動小数点演算はシステムの種類によって，異なる規格を採用していることがある．このことは，異なるシステム（規格）において，同じ入力で同じ出力がえられない可能性があることを意味する．従って，浮動小数点演算によるカオスの計算を含むシステムでは安価なシステムになり難い．そのため，異なるシステムでも同じ入力に対し同じ出力が得られる整数演算による擬似カオス時系列の生成が求められる．ロジスティック写像による乱数生成について，1947 年にも2 進計算機の原型を考案したフォン・ノイマンらにより提案された．しかし，ロジスティック写像を計算して得られる時系列は一様分布とはならず，Ｕ字型となっている．それを使って，一様分布の系列にするには何らかの処理が必要である．しかし，これまでの提案された方法では何れも大幅な生成速度の低下を伴っている．また，計算精度ビット長が長くすることで，生成される系列の周期長を長くすることができるが，写像速度の低下に繋がる．一方，周期長，統計的乱数性，生成速度などは乱数生成法においての重要な指標となっている．従って，計算精度拡張の高速な計算方法，乱数生成速度の低下が小さい処理方法が望まれる．本研究はロジスティック写像を擬似乱数生成へ応用することを考える．本研究は序章と終章を含み，6 章からなる．以下，2 から5 の各章の概要を述べる．2 章では，3 章以降で必要となるカオスに関する基礎的な概念・用語を準備する．とくに，本論分の主要結果であるロジスティック写像の計算機上での演算について，従来用いられてきた浮動小数点法による計算方法と比較しながら，本論文で提案する整数演算を用いた計算方法の特色について論じる．3 章では，まず，整数ロジスティック写像において，初期値敏感性を示さない場合すなわち，ホール（Hall）の存在を明らかにする．また，初期値が不動点以外の値で，有限回の繰り返し計算で不動点に入ることを回避するために，不動点を含む任意の値に落ち入る系列の存在を調べる方法を提案する．そして，数値計算により，整数ロジスティック写像が生成できる平均的な非周期状態長の推定値と計算精度N との近似的な関係を与える．4 章では，整数演算を用いて計算精度N ビットのロジスティック写像を計算し，計算過程に存在する2N ビットの内部状態を利用した撹拌方法に基づく擬似乱数生成法を提案する．また，生成した乱数列に対し，初期値敏感性をハミング距離の収束の速さで提案法とMTと比較を行い，提案法の効果を示した．そして，計算精度N = 128 ビットで生成される2 進数列に対し，統計的検定を行い，一様性を持つとの結論を得た．5 章では，大量のID・パスワード（PW）の生成だけでなく，管理にも適した擬似乱数列の生成方法を提案する．提案法は，初期値(種)R とK 次元空間座標で表す位置i を用いて2 値系列を生成する．i 番目の擬似乱数列Ri は初期値Rを用いてK = 1 回繰り返して生成される．擬似乱数生成がロジスティック写像を用いたとき，提案方式における多次元乱数生成の性能を確認し，計算量的に安全なキーの生成が可能であることを示す．その結果，本研究は整数で演算するロジスティック写像が有する基本的な性質を解明して，ロジスティック写像をセキュリティー用乱数生成へ応用するとき，初期値選びや計算精度長の決定の根拠を与え，安全な乱数生成システムの構築を可能にした（3 章）．そして，高速な乱数生成方法を提案し（4 章），これまで実現困難とされるキーの使い捨て暗号や認証を容易にした（5 章）．