テント型写像から得られる擬似ランダムビット列の初期値推測法について(情報セキュリティ基礎)

概要

論文の詳細を見る
傾き1<a≤2のテント型写像の反復のたびに最上位ビットを抽出して得られた擬似ランダムビット列が与えられたときに,傾きaを既知として,当該系列を生成し得る初期値範囲の推測法について述べる.従来では,写像のたびに,写像の前後関係を厳密に調べ上げることによって初期値範囲を絞り込んでいく手法が示されていたが,逐次計算処理的な手法であるがために,解が数理的に整理されていなかった.また,グレイコードを利用した解析法が示されていたが,厳密な初期値範囲を得ることができない場合があった.本論文で示す推測法は,観測ビット列からn回反復写像の多項式関数形f^n_a(x_0)=x_nを決定し,最終値x_nの存在条件を用いて,初期値x_0の範囲を当該多項式関数の解として求めるものである.なお,本推測法では,最終値x_nの厳密な存在範囲を知ることが重要であり,これは一般的には困難であるが,テント型写像とビット抽出ルールの特性を考慮して分割された区間の推移を状態遷移図として整理したことによって,観測ビット列からx_i(0<i≤n)の厳密な存在範囲を簡単に求めることができる旨を示した.ただし,傾き1<a<2の場合では,観測ビット列中に1に続く0の連の理論上の最大値(この値は傾きaに依存する)が含まれる場合は,系列を前後に分割して,分割した系列単位で絞り込んでいくことで達成される.これより,厳密な初期値範囲が数理的に整理された形で得ることができるようになった.
社団法人電子情報通信学会の論文
2009-07-01

テント型写像から得られる擬似ランダムビット列の初期値推測法について(情報セキュリティ基礎)

スポンサーリンク

概要

著者

関連論文

スポンサーリンク