(57)【要約】【課題】出力された擬似ランダムビット列から、 当該擬似ランダムビット列の生成に利用された初期の写像値、 パラメータ列等のシード関連値の推測を困難とする。【解決手段】パラメータ列と写像値とに基づき前段写像演算を行う前段写像計算手段２０１と、前記前段写像計算手段２０１による計算結果に基づき前段写像演算と異なる写像演算を行い、演算結果を前記前段写像計算手段２０１へ戻す後段写像計算手段２０３とを備え、前記前段写像計算手段２０１と前記後段写像計算手段３０１とのループによる写像演算を所定回繰り返す擬似乱数生成装置であって、前記前段写像計算手段２０１から得られる計算結果に基づき出力ランダムビット列８０２により構成される擬似乱数を生成する。【選択図】図３
2018097438.tif 000002
【特許請求の範囲】
【請求項１】
パラメータ列と写像値とに基づき前段写像演算を行う前段写像計算手段と、
前記前段写像計算手段による計算結果に基づき前段写像演算と異なる写像演算を行い、演算結果を前記前段写像計算手段へ戻す後段写像計算手段とを備え、
前記前段写像計算手段と前記後段写像計算手段とのループによる写像演算を所定回繰り返す擬似乱数生成装置であって、
前記前段写像計算手段から得られる計算結果に基づき出力ランダムビット列により構成される擬似乱数を生成することを特徴とする擬似乱数生成装置。
【請求項２】
前記前段写像計算手段による計算結果に基づき出力ランダムビット列の一部となる元データを抽出する抽出手段と、
前記元データに基づき所定処理を選択実行して出力ランダムビット列の一部を算出するビット算出手段と
を具備し、
前記抽出手段は、前記ビット算出手段が実行する所定処理の選択の際に参照する参照データを抽出することを特徴とする請求項１に記載の擬似乱数生成装置。
【請求項３】
ビット算出手段は、前記元データの一部を選択する選択手段を有し、前記参照データに基づき前記選択手段による選択を実行するか否かを判定し、前記選択手段による選択を実行する場合には、前記参照データに基づき前記元データのいずれのビットを選択するか判定することを特徴とする請求項２に記載の擬似乱数生成装置。
【請求項４】
ビット算出手段は、前記選択手段により選択されたビットに関する転置演算を行う転置手段を備え、前記参照データに基づき前記転置手段による転置を行うか否かの判定を行うことを特徴とする請求項３に記載の擬似乱数生成装置。
【請求項５】
前記転置手段は、複数の転置演算部を有し、前記参照データに基づき前記複数の転置演算部のいずれを用いて転置を行うかの判定を行うことを特徴とする請求項４に記載の擬似乱数生成装置。
【請求項６】
前記転置手段による転置結果のビット列を一時保持する保持手段を有し、該保持手段に所定長のビット列が保持されたときに、この保持手段に保持されたビット列を出力ランダムビット列として出力することを特徴とする請求項４または５に記載の擬似乱数生成装置。
【請求項７】
前記後段写像計算手段には、複数の写像計算部が備えられ、前記参照データに基づき前記複数の写像計算部のいずれを用いて写像を行うかの判定を行うことを特徴とする請求項２乃至６のいずれか１項に記載の擬似乱数生成装置。
【請求項８】
前記後段写像計算手段の計算結果を受けて、前記前段写像計算手段が用いるパラメータを変動させる内部状態変動手段を備え、
前記内部状態変動手段は、前記参照データに基づき前記前段写像計算手段が用いるパラメータを変動させるか否かの判定を行うことを特徴とする請求項２乃至７のいずれか１項に記載の擬似乱数生成装置。
【請求項９】
前記後段写像計算手段は、それぞれ異なる写像計算を行う複数の写像演算部が縦続接続されていることを特徴とする請求項１乃至８のいずれか１項に記載の擬似乱数生成装置。
【請求項１０】
前記後段写像計算手段は、前記前段写像計算手段による写像結果を整数化演算することを特徴とする請求項１乃至９のいずれか１項に記載の擬似乱数生成装置。
【請求項１１】
処理の開始時において、前段写像計算手段に与えるべき初期の写像値と初期のパラメータ列とを少なくとも含む初期の値を生成するための前処理部を具備することを特徴とする請求項１乃至１０のいずれか１項に記載の擬似乱数生成装置。
【請求項１２】
擬似乱数生成を行うコンピュータを、
パラメータ列と写像値とに基づき前段写像演算を行う前段写像計算手段、
前記前段写像計算手段による計算結果に基づき前段写像演算と異なる写像演算を行い、演算結果を前記前段写像計算手段へ戻す後段写像計算手段、
として機能させ、
前記コンピュータが前記前段写像計算手段と前記後段写像計算手段としてループ処理し、写像演算を所定回繰り返すように機能させ、
前記コンピュータを更に、前記前段写像計算手段から得られる計算結果に基づき出力ランダムビット列により構成される擬似乱数を生成するように機能させることを特徴とする擬似乱数生成プログラム。
【請求項１３】
前記コンピュータを更に、前記前段写像計算手段による計算結果に基づき出力ランダムビット列の一部となる元データを抽出する抽出手段、
前記元データに基づき所定処理を選択実行して出力ランダムビット列の一部を算出するビット算出手段として機能させ、
前記抽出手段は、前記ビット算出手段が実行する所定処理の選択の際に参照する参照データを抽出することを特徴とする請求項１２に記載の擬似乱数生成プログラム。
【請求項１４】
ビット算出手段では、前記コンピュータを、前記元データの一部を選択する選択手段として機能させ、前記参照データに基づき前記選択手段による選択を実行するか否かを判定し、
前記選択手段による選択を実行する場合には、前記参照データに基づき前記元データのいずれのビットを選択するか判定することを特徴とする請求項１３に記載の擬似乱数生成プログラム。
【請求項１５】
ビット算出手段では、前記コンピュータを、前記選択手段により選択されたビットに関する転置演算を行う転置手段として機能させ、
前記参照データに基づき前記転置手段による転置を行うか否かの判定を行うことを特徴とする請求項１４に記載の擬似乱数生成プログラム。
【請求項１６】
前記転置手段では、前記コンピュータを、複数の転置演算部として機能させ、
前記参照データに基づき前記複数の転置演算部のいずれを用いて転置を行うかの判定を行うことを特徴とする請求項１５に記載の擬似乱数生成プログラム。
【請求項１７】
前記転置手段による転置結果のビット列を一時保持する保持手段を有し、該保持手段に所定長のビット列が保持されたときに、この保持手段に保持されたビット列を出力ランダムビット列として出力することを特徴とする請求項１５または１６に記載の擬似乱数生成プログラム。
【請求項１８】
前記後段写像計算手段では、前記コンピュータを、複数の写像計算部として機能させ、
前記参照データに基づき前記複数の写像計算部のいずれを用いて写像を行うかの判定を行うことを特徴とする請求項１３乃至１７のいずれか１項に記載の擬似乱数生成プログラム。
【請求項１９】
前記コンピュータを、前記後段写像計算手段の計算結果を受けて、前記前段写像計算手段が用いるパラメータを変動させる内部状態変動手段として機能させ、
前記内部状態変動手段は、前記参照データに基づき前記前段写像計算手段が用いるパラメータを変動させるか否かの判定を行うことを特徴とする請求項１３乃至１８のいずれか１項に記載の擬似乱数生成プログラム。
【請求項２０】
前記後段写像計算手段では、前記コンピュータを、それぞれ異なる写像計算を行う複数の写像演算部が縦続接続されているように機能させることを特徴とする請求項１２乃至１９のいずれか１項に記載の擬似乱数生成プログラム。
【請求項２１】
前記後段写像計算手段は、前記前段写像計算手段による写像結果を整数化演算することを特徴とする請求項１２乃至２０のいずれか１項に記載の擬似乱数生成プログラム。
【請求項２２】
コンピュータを更に、
処理の開始時において、前段写像計算手段に与えるべき初期の写像値と初期のパラメータ列とを少なくとも含む初期の値を生成するための前処理部として機能させることを特徴とする請求項１２乃至２０のいずれか１項に記載の擬似乱数生成プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、生成された擬似乱数から初期の写像値やパラメータ列などのシード情報を推定することが困難な擬似乱数生成装置及び擬似乱数生成プログラムに関するものである。本発明は、カオス写像の反復によって得られる乱雑データを利用して乱数を得る擬似乱数生成方式に属する。
【背景技術】
【０００２】
従来より、カオス写像に基づく擬似乱数生成法や暗号化手法が数多く提案されている。この擬似乱数生成法や暗号化手法としては、カオスの特徴をどのように応用するかという着眼／発想の違いにより様々な実現手法が存在する。
【０００３】
上記のカオス写像に基づく擬似乱数生成法は、今日一般的に利用されている擬似乱数生成法や暗号化手法に比べ歴史が浅い。本発明の発明者らは、カオス写像を有限精度の計算機（デジタルコンピュータ）に実装する際に生じる課題を解決して、例えば、NIST （National Institute of Standards and Technology ／米国標準技術研究所）が定める乱数検定法（A. Rukhin. and et al, “A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications," NIST, Special Publication 800-22 Revision1A, April 2010.（文献１））に合格する等の「統計的評価」の側面において、良質な乱数を得ることを初期目標とした。
【０００４】
統計的側面において良好な評価結果を得られる擬似乱数生成方式としては、例えば文献特許文献１、特許文献２、特許文献３、特許文献４、特許文献５、特許文献６、特許文献６、特許文献７、特許文献８、非特許文献１、非特許文献２に記載のものを挙げることができる。また、構造がやや異なるが、同じくカオス写像の反復を利用する擬似乱数生成手法としては非特許文献３、４、５、６、７に記載のものを挙げることができる。
【０００５】
カオス写像に基づく擬似乱数生成に属する方式のうち最もシンプルな構成をもつ初歩的な方式（以下、初歩方式と称す）を図１に示す。この初歩方式では、初期化部Ｓ１１においてシードｓと所望のランダムビット列長ｎを入力し、初期値ｘ０を上記シードｓから求め、また、パラメータ値ａを上記シードｓから求め、カウンタ値ｉを０とする。次のカウントアップ部Ｓ１２において、カウンタ値ｉを１インクリメントする。
【０００６】
更に、次の写像計算部Ｓ１３において、パラメータ値ａの写像ｆａを用いて写像値ｘｉを更新し（自らを自らに写像する／反復写像）、次のランダムビット抽出部Ｓ１４において写像毎にｘｉの任意の所定箇所のビットを抽出して擬似ランダムビット列ｂ＝｛ｂ１，ｂ２，・・・，ｂｎ｝を得る。
【０００７】
更に、終了判定部Ｓ１５においてカウンタ値ｉがｎとなったかを判定し、ｉ＜ｎであれば、カウントアップ部Ｓ１２に戻って処理を続ける。一方、終了判定部Ｓ１５においてカウンタ値ｉがｎとなった場合には、エンドとなり処理を終了する。
【０００８】
次に、特許文献１〜８、非特許文献１、２に開示された方式における「擬似乱数生成部」に関する特徴を説明する。
【０００９】
初歩方式のランダムビット抽出部が写像値ｘｉから特定のビットを１ビット抽出する構成を有するのに対し、文献２には、複数の閾値を設け写像値ｘｉから複数のビット（ビット列）を得て、これらを最終的に結合（排他的論理和）する手法が示されている（特許文献１図９）。特許文献１においては、これにより乱数性の向上を図っている。
【００１０】
特許文献２には、複数のカオス写像（初歩方式や特許文献１に示される方式）の出力を結合（排他的論理和）する手法等が示されている（特許文献２図１６）。特許文献２においては、これにより乱数性の向上を図ることができる。
【００１１】
特許文献３には、初歩方式の写像計算部に相応する部分において、高次数の数値が格納されるレジスタサイズを、低次数の数値が格納されるレジスタサイズよりも多く確保することが開示されている。例えば、ある数値ｘの二乗ｘ２が格納されるメモリ空間を多く確保することが開示されている。更に、特許文献３においては、上記に対応した演算法が示されている（特許文献３図１）。特許文献３においては、これにより、有限精度のデジタルコンピュータなどの計算機にてカオス写像を実装する際の根本的な課題（例えば、桁丸めにより生じる隣接軌道の縮退が短周期化を招くという問題）を所定レベルで回避することができ、乱数の長周期化を図ることができる。
【００１２】
特許文献４には、初歩方式のランダムビット抽出部に相応する部分の出力に対して、更に、一方向性関数を作用させる手段が追加されものが開示されている（特許文献４図１）。これにより、特許文献４においては、乱数性の向上を図っている。
【００１３】
特許文献５、６、非特許文献１、２には、初歩方式に対して、内部状態を変動させる手段が追加されたものが開示されている。即ち、図２に示すように、図１に示した初歩方式のフローチャートにおいて、ランダムビット抽出部Ｓ１４と終了判定部Ｓ１５との間で内部状態変動部Ｓ２１を実行する。この内部状態変動部Ｓ２１では、一例として、パラメータ値ａを元のパラメータ値ａとシードｓにより更新し、写像値ｘｉを元の写像値ｘｉとシードｓにより更新する。これによって、前述同様の短周期性問題が解消されると共に、一般的に使用されるパラメータ値以外の値も利用することが可能（扱える状態空間が飛躍的に広がる）となる。更に、特許文献５、６、非特許文献１、２に記載のものによれば、良質な乱数を得ることができることが、「岩野隆, 金田学, 奥富秀俊, “一次元写像を用いた擬似乱数生成におけるパラメータ変動の効果について," 2007 年暗号と情報セキュリティシンポジウム(SCIS2007), 3E2-5, January 2007」（文献２）、「岩野隆, 金田学, 奥富秀俊, “一次元写像を用いた擬似乱数生成におけるパラメータ可変の効果について," 信学技報Vol.106, No.596, ISEC2006-123, pp.47-51, March 2007」（文献３）、「岩野隆, 金田学, 奥富秀俊, “テント型写像を用いた擬似乱数生成における内部状態変動の効果について," 2008 年暗号と情報セキュリティシンポジウム(SCIS2008), 2A2-4, January 2008」（文献４）に示されている。
【００１４】
上記の「一般的に使用されるパラメータ」とは、テント写像ではコントロールパラメータ２、ロジスティック写像ではコントロールパラメータ４、が利用されることを意味する。これ以外のパラメータを利用すると、写像値の分布に偏りが生じることが判っている。
【００１５】
特許文献７には、複数の写像値（その初期値）を用意してベクトルとし、また、複数の写像を用意して行列とし、ベクトル演算（行列演算）により写像を実施した後、写像後のベクトルに回転変換を施す手法を用いた擬似乱数生成手法が示されている（特許文献７図１）。この手法は、すなわち、複数の初歩方式を用意し、写像後に各写像値を入れ替えることに等しいものである。特許文献７においては、これにより乱数性の向上を図っている。
【００１６】
初歩方式のランダムビット抽出部が写像値ｘｉから特定のビットを１ビット抽出するのに対し、特許文献８には、コントロールパラメータが４の場合のロジスティック写像を用いる場合に限定されるが、写像値ｘｉ（Ｎビットとする）の計算の中間段階、すなわち、ｘｉ＝４ｘｉ−１（１−ｘｉ−１）の右辺に相当する部分が一時的に２Ｎビットになるため、その段階において上位と下位のＮビットを排他的論理和演算し、効率的に乱数を得る手法が開示されている。
【００１７】
しかしながら、上記の初歩方式を限られた演算精度で実装する場合には、「S. Araki, T. Miyazaki, and S. Uehara, “Analysis for Pseudorandom Number Generators Using Logistic Map", Proc. of 2006 International Symposium on Information Theory and its Applications,2006.」（文献５））、「S. Araki, T. Miyazaki, S. Uehara and K. Kakizaki, “A Study on Precision of Pseudorandom Number Generators Using the Logistic Map," Proc. of 2012 International Symposium on Information Theory and its Applications, 2012, pp. 740-744, 2012.」（文献６）、「 荒木俊輔, 宮崎武, 上原聡, 硴崎賢一, “整数上のテント写像を用いた擬似乱数生成器に関する一考察," 2013 年暗号と情報セキュリティシンポジウム(SCIS2013), 2F3-4, January 2013.」（文献７）に示されている通り、統計的側面において十分に良質な擬似ランダムビット列を得ることができない。ロジスティック写像を用いた場合は、文献５、６に示されているように、少なくとも５３ビット以上が必要であり、テント写像を用いた場合は少なくとも今日の計算機を遥かに超える演算精度が必要となる「奥富秀俊, 中村勝洋, “テント型写像から得られる擬似ランダムビット列の初期値推測法について," 電子情報通信学会論文誌VOL.J92-A, No.7, pp.487-497, July 2009.」（文献８）。
【００１８】
特許文献１〜８、非特許文献１〜７に示される従来手法に共通することは、カオス写像の反復計算によって得られる系列を利用することである。中でも、写像毎に写像値の最上位ビットを抽出して擬似ランダムビット列を構成する手法は、当該擬似ランダムビット列の生成に使われたシード情報の一部が推測可能であることが知られている「大熊健司, 櫻井幸一, “一次元写像に基づくカオス擬似乱数列の暗号論的安全性について," 1999 年暗号と情報セキュリティシンポジウム(SCIS'99), A-7-1, 1999.」（文献９）、「E.Alvarez, H.Montoya, M.Romera, G.pastor, “Gray codes and 1D quadratic maps," Electronics Letters 34(1998) 1304-1306.」（文献１０）、「Cusick TW, “Gray codes and the symbolic dynamics of quadratic maps," Electronics Letters 35(1999) 468-469.」（文献１１）、「E.Alvarez, H.Montoya, M.Romera, G.pastor, “Cryptanalysis of a chaotic encryption system," Physics Letters A276(2000) 191-196.」（文献１２）、「E.Alvarez, H.Montoya, M.Romera, G.pastor, “Cryptanalysis of an ergodic haotic cypher," Physics Letters A311(2003) 172-179.」（文献１３）、「Xiaogang Wu, Hanping Hu, Baoliang Zhag, “Parameter estimation only from the symbolic sequences generated by chaos system," Chaos, Solitons and Fractals 22(2004) 359-366.」（文献１４）、「奥富秀俊, 岩野隆, 中村勝洋, “１次の非線形写像から得られた擬似ランダムビット列の初期値推測法について," 第30 回情報理論とその応用シンポジウム(SITA2007), 2.3, November 2007.」（文献１５）、「奥富秀俊, 岩野隆, 中村勝洋, “テント型写像から得られるランダムビット列の初期値推測法について," 2008 年暗号と情報セキュリティシンポジウム(SCIS2008), 2A2-1, January 2008.」（文献１６）、「奥富秀俊, 中村勝洋, “テント写像から得られた擬似ランダムビット列のパラメータ推測法に関する考察," 2010 年暗号と情報セキュリティシンポジウム(SCIS2010), 2D1-2, January 2010.」（文献１７）。
【００１９】
また、初歩方式に関しては、上記文献８〜１７に示されている攻撃法を用いて、擬似ランダムビット列ｂ＝｛ｂ１，ｂ２，・・・，ｂｎ｝の生成に利用された初期値ｘ０やパラメータ値ａの一部また全部を総当たり攻撃するよりも効率的に得ることができる。
【００２０】
上記の攻撃とは、擬似乱数生成法から生成された擬似乱数列を既知情報としたときに、当該乱数列の生成に使われたシード情報を得ようとする行為をいい、また、攻撃法は、それを達成するための手段（ここでは数学的手段や計算アルゴリズム）をいう。
【００２１】
前述の従来手法は、統計的側面において良質な擬似乱数列を得ることを主たる目的としている。しかしながら、計算機シミュレーション分野でこれら従来手法を利用する限りにおいては問題ないが、情報セキュリティ分野での利用を検討するには、統計的に良質な乱数を提供するだけでなく、少なくとも既知攻撃法に対して対策を興じる必要が生じる。
【先行技術文献】
【特許文献】
【００２２】
【特許文献１】特開平９−１１６５３３号公報
【特許文献２】特開平９−２８８５６５号公報
【特許文献３】特開平９−２９２９７８号公報
【特許文献４】特開平１０−２０７８号公報
【特許文献５】特開２００１−２８５２７７号公報
【特許文献６】特開２００４−２６６４９５号公報
【特許文献７】特開２００７−２６４４７号公報
【特許文献８】特開２００９−１２９４３２号公報
【００２３】
【非特許文献】
【００２４】
【非特許文献１】奥富秀俊, 中村勝洋, “整数演算をベースにしたパラメータ可変の非線形写像を用いた擬似乱数生成法とその評価," SITA2003, 8.1, November 2003.
【非特許文献２】Hidetoshi OKUTOMI, Katsuhiro NAKAMURA, “Pseudo Random Number Generation Method based on Nonlinear Integer Mapping with Parameters Variable and its Randomness Evaluation," 2004 International Symposium on Information Theory and its Applications (ISITA2004), paper #358, October 2004.
【非特許文献３】S. Phatak, and S. Rao, “Logistic map: A possible random number generator," Phys. Rev. E, Vol.51, No. 4, pp.3670-3678, 1995.
【非特許文献４】M.S.Baptista, “Cryptography with chaos," Physics Letters A240 (1998) 50-54.
【非特許文献５】E.Alvarez, A,Fernandez, P.Garcia, J.Jimenez, A.Marcano, “New approach to chaotic encryption," Physics Letters A263 (1999) 373-375.
【非特許文献６】Wai-kit Wong, Lap-piu Lee, Kwok-wo Wong, “A modi_ed chaotic cryptographic method," Computer Physics Communications 138 (2001) 234{236.
【非特許文献７】G.Jakimov, L.Kocarev, “Chaos and Cryptography : Block Encryption Cipher Based on Chaotic Maps," IEEE Transactions on Circuits and Systems - I:Fundamental Theory and Applications,Vol.49, No.2, February 2001.
【発明の概要】
【発明が解決しようとする課題】
【００２５】
本発明は以上のような擬似乱数生成における現状に鑑みてなされたもので、その目的は、 従来から提案されているカオス写像に基づく擬似乱数生成法と同等の統計的に良質な擬似乱数（擬似ランダムビット列）が生成可能である擬似乱数生成装置及び擬似乱数生成プログラムを提供することである。また、これと共に、出力された擬似ランダムビット列から、 当該擬似ランダムビット列の生成に利用された初期の写像値、 パラメータ列等のシード関連値の推測を困難とする手段を備えた擬似乱数生成装置及び擬似乱数生成プログラムを提供することを目的とする。
【課題を解決するための手段】
【００２６】
本発明に係る擬似乱数生成装置は、パラメータ列と写像値とに基づき前段写像演算を行う前段写像計算手段と、前記前段写像計算手段による計算結果に基づき前段写像演算と異なる写像演算を行い、演算結果を前記前段写像計算手段へ戻す後段写像計算手段とを備え、前記前段写像計算手段と前記後段写像計算手段とのループによる写像演算を所定回繰り返す擬似乱数生成装置であって、前記前段写像計算手段から得られる計算結果に基づき出力ランダムビット列により構成される擬似乱数を生成することを特徴とする。
【００２７】
本発明に係る擬似乱数生成装置では、前記前段写像計算手段による計算結果に基づき出力ランダムビット列の一部となる元データを抽出する抽出手段と、前記元データに基づき所定処理を選択実行して出力ランダムビット列の一部を算出するビット算出手段とを具備し、前記抽出手段は、前記ビット算出手段が実行する所定処理の選択の際に参照する参照データを抽出することを特徴とする。
【００２８】
本発明に係る擬似乱数生成装置では、ビット算出手段は、前記元データの一部を選択する選択手段を有し、前記参照データに基づき前記選択手段による選択を実行するか否かを判定し、前記選択手段による選択を実行する場合には、前記参照データに基づき前記元データのいずれのビットを選択するか判定することを特徴とする。
【００２９】
本発明に係る擬似乱数生成装置では、ビット算出手段は、前記選択手段により選択されたビットに関する転置演算を行う転置手段を備え、前記参照データに基づき前記転置手段による転置を行うか否かの判定を行うことを特徴とする。
【００３０】
本発明に係る擬似乱数生成装置では、前記転置手段は、複数の転置演算部を有し、前記参照データに基づき前記複数の転置演算部のいずれを用いて転置を行うかの判定を行うことを特徴とする。
【００３１】
本発明に係る擬似乱数生成装置では、前記転置手段による転置結果のビット列を一時保持する保持手段を有し、該保持手段に所定長のビット列が保持されたときに、この保持手段に保持されたビット列を出力ランダムビット列として出力することを特徴とする。
【００３２】
本発明に係る擬似乱数生成装置では、前記後段写像計算手段には、複数の写像計算部が備えられ、前記参照データに基づき前記複数の写像計算部のいずれを用いて写像を行うかの判定を行うことを特徴とする。
【００３３】
本発明に係る擬似乱数生成装置では、前記後段写像計算手段の計算結果を受けて、前記前段写像計算手段が用いるパラメータを変動させる内部状態変動手段を備え、前記内部状態変動手段は、前記参照データに基づき前記前段写像計算手段が用いるパラメータを変動させるか否かの判定を行うことを特徴とする。
【００３４】
本発明に係る擬似乱数生成装置では、前記前段写像計算手段は、それぞれ異なる写像計算を行う複数の写像演算部が縦続接続されていることを特徴とする。
【００３５】
本発明に係る擬似乱数生成装置では、前記後段写像計算手段は、前記前段写像計算手段による写像結果を整数化演算することを特徴とする。
【００３６】
本発明に係る擬似乱数生成装置では、処理の開始時において、前段写像計算手段に与えるべき初期の写像値と初期のパラメータ列とを少なくとも含む初期の値を生成するための前処理部を具備することを特徴とする。
【００３７】
本発明に係る擬似乱数生成プログラムは、擬似乱数生成を行うコンピュータを、パラメータ列と写像値とに基づき前段写像演算を行う前段写像計算手段、前記前段写像計算手段による計算結果に基づき前段写像演算と異なる写像演算を行い、演算結果を前記前段写像計算手段へ戻す後段写像計算手段、として機能させ、前記コンピュータが前記前段写像計算手段と前記後段写像計算手段としてループ処理し、写像演算を所定回繰り返すように機能させ、前記コンピュータを更に、前記前段写像計算手段から得られる計算結果に基づき出力ランダムビット列により構成される擬似乱数を生成するように機能させることを特徴とする。
【００３８】
本発明に係る擬似乱数生成プログラムでは、前記コンピュータを更に、前記前段写像計算手段による計算結果に基づき出力ランダムビット列の一部となる元データを抽出する抽出手段、前記元データに基づき所定処理を選択実行して出力ランダムビット列の一部を算出するビット算出手段として機能させ、前記抽出手段は、前記ビット算出手段が実行する所定処理の選択の際に参照する参照データを抽出することを特徴とする。
【００３９】
本発明に係る擬似乱数生成プログラムは、ビット算出手段では、前記コンピュータを、前記元データの一部を選択する選択手段として機能させ、前記参照データに基づき前記選択手段による選択を実行するか否かを判定し、前記選択手段による選択を実行する場合には、前記参照データに基づき前記元データのいずれのビットを選択するか判定することを特徴とする。
【００４０】
本発明に係る擬似乱数生成プログラムは、ビット算出手段では、前記コンピュータを、前記選択手段により選択されたビットに関する転置演算を行う転置手段として機能させ、
前記参照データに基づき前記転置手段による転置を行うか否かの判定を行うことを特徴とする。
【００４１】
本発明に係る擬似乱数生成プログラムは、前記転置手段では、前記コンピュータを、複数の転置演算部として機能させ、前記参照データに基づき前記複数の転置演算部のいずれを用いて転置を行うかの判定を行うことを特徴とする。
【００４２】
本発明に係る擬似乱数生成プログラムでは、前記転置手段による転置結果のビット列を一時保持する保持手段を有し、該保持手段に所定長のビット列が保持されたときに、この保持手段に保持されたビット列を出力ランダムビット列として出力することを特徴とする。
【００４３】
本発明に係る擬似乱数生成プログラムは、前記後段写像計算手段では、前記コンピュータを、複数の写像計算部として機能させ、前記参照データに基づき前記複数の写像計算部のいずれを用いて写像を行うかの判定を行うことを特徴とする。
【００４４】
本発明に係る擬似乱数生成プログラムでは、前記コンピュータを、前記後段写像計算手段の計算結果を受けて、前記前段写像計算手段が用いるパラメータを変動させる内部状態変動手段として機能させ、前記内部状態変動手段は、前記参照データに基づき前記前段写像計算手段が用いるパラメータを変動させるか否かの判定を行うことを特徴とする。
【００４５】
本発明に係る擬似乱数生成プログラムは、前記前段写像計算手段では、前記コンピュータを、それぞれ異なる写像計算を行う複数の写像演算部が縦続接続されているように機能させることを特徴とする。
【００４６】
本発明に係る擬似乱数生成プログラムでは、前記後段写像計算手段は、前記前段写像計算手段による写像結果を整数化演算することを特徴とする。
【００４７】
本発明に係る擬似乱数生成プログラムでは、コンピュータを更に、処理の開始時において、前段写像計算手段に与えるべき初期の写像値と初期のパラメータ列とを少なくとも含む初期の値を生成するための前処理部として機能させることを特徴とする。
【発明の効果】
【００４８】
本発明に係る擬似乱数生成装置及び擬似乱数生成プログラムによれば、統計的に良質な擬似乱数（擬似ランダムビット列）が生成可能である。
【００４９】
また、本発明に係る擬似乱数生成装置及び擬似乱数生成プログラムによれば、出力された擬似ランダムビット列から、 当該擬似ランダムビット列の生成に利用された初期の写像値、 パラメータ列等のシード関連値の推測を困難とすることができる。
【図面の簡単な説明】
【００５０】
【図１】従来の擬似乱数生成のアルゴリズムを示すフローチャート。
【図２】図１に示した従来例を改良した、従来の擬似乱数生成のアルゴリズムを示すフローチャート。
【図３】本発明の実施形態に係る擬似乱数生成装置及び擬似乱数生成プログラムの、擬似乱数生成のアルゴリズムを示すフローチャート。
【図４】本発明の実施形態に係る擬似乱数生成装置及び擬似乱数生成プログラムの要部アルゴリズムを示すフローチャート。
【発明を実施するための形態】
【００５１】
以下、添付図面を参照して本発明の実施形態に係る擬似乱数生成装置及び擬似乱数生成プログラムを説明する。各図において、同一の構成要素には同一の符号を付して重複する説明を省略する。図３に、本発明の実施形態に係る擬似乱数生成装置の構成図を示す。この図３は、本発明の実施形態に係る擬似乱数生成プログラムによる動作のフローチャートでもある。
【００５２】
この擬似乱数生成装置は、前段写像計算手段２０１、後段写像計算手段２０３を備える。前段写像計算手段２０１は、パラメータ列と写像値とに基づき前段写像演算を行うものである。前段写像計算手段２０１は、カオス写像の計算を乗算、加算、左ビットシフト演算等の写像値の拡大に関する演算で構成される写像演算を行うものとすることができる。最初の前段写像演算に用いる初期のパラメータ列と初期の写像値は、前段写像計算手段２０１が保持している構成もあり得るが、本実施形態では、後に説明する前処理部１０１が生成する。
【００５３】
後段写像計算手段２０３は、上記前段写像計算手段２０１による計算結果に基づき前段写像演算と異なる写像演算を行い、演算結果を前記前段写像計算手段２０１へ戻すものである。後段写像計算手段２０３は、除算（除算の商を得る演算）、剰余算（除算の剰余を得る演算）、右ビットシフト演算等の写像値の縮小に関する演算で構成される写像演算を行うものとすることができる。
【００５４】
この擬似乱数生成装置は、上記前段写像計算手段２０１と上記後段写像計算手段２０３とのループによる写像演算を所定回繰り返す構成を採用する。本擬似乱数生成装置は、上記前段写像計算手段２０１から得られる計算結果に基づき出力ランダムビット列８０２により構成される擬似乱数を生成するものとすることができる。
【００５５】
更に擬似乱数生成装置は、抽出手段３０１とビット算出手段４００を備える。抽出手段３０１は、上記前段写像計算手段２０１による計算結果に基づき出力ランダムビット列８０２の一部となる元データ３０３を抽出する。ビット算出手段４００は、上記元データ３０３に基づき所定処理を選択実行して出力ランダムビット列８０２の一部を算出する。また、前記抽出手段３０１は、上記ビット算出手段４００が実行する所定処理の選択の際に参照する参照データ３０２を抽出する。
【００５６】
ビット算出手段４００は、上記元データ３０３の一部を選択する選択手段４０２を有し、上記参照データ３０２に基づき上記選択手段４０２による選択を実行するか否かを選択判定部４０１において判定し、上記選択手段４０２による選択を実行する場合には、上記参照データ３０２に基づき上記元データ３０３のいずれのビットを選択するか判定する。
【００５７】
ビット算出手段４００は、上記選択手段４０２により選択されたビット列に関する転置演算を行う転置手段５０２を備え、ランダムビット長カウンタ４０４の値に基づき転置判定部５０１が上記転置手段５０２による転置を行うか否かの判定を行う。
【００５８】
上記転置手段５０２は、図４に示すように、複数の転置演算部５０２−１〜５０２−ｕを有し、上記参照データ３０２に基づき決定部５００が上記複数の転置演算部５０２−１〜５０２−ｕのいずれを用いて転置を行うかの判定を行う。
【００５９】
前記転置手段５０２による転置結果のビット列を一時保持する保持手段５０３を有し、該保持手段５０３に所定長のビット列が保持されたときに、この保持手段５０３に保持されたビット列を出力ランダムビット列８０２として出力する。
【００６０】
本装置では、参照データ３０２と元データ３０３とを独立したデータとして扱い、参照データ３０２の一部または全部を元データ３０３の一部または全部に転用することはせず、また、元データ３０３の一部または全部を参照データ３０２の一部または全部に転用することはしない。
【００６１】
上記後段写像計算手段２０３には、それぞれ異なる端数処理を行う複数の写像計算部２０３−０〜２０３−（ｍ−１）が備えられ、後段写像選択部２０２が上記参照データ３０２に基づき上記複数の写像計算部２０３−０〜２０３−（ｍ−１）のいずれを用いて写像を行うかの判定を行う。上記後段写像計算手段２０３は、上記前段写像計算手段２０１による写像結果を整数化演算する構成とすることができる。
【００６２】
本装置は、更に内部状態変動手段６０２を備える。この内部状態変動手段６０２は、上記後段写像計算手段２０３の計算結果を受けて、上記前段写像計算手段２０１が用いるパラメータ列を変動させるものである。上記内部状態変動手段６０２は、上記参照データ３０２に基づき変動判定部６０１において上記前段写像計算手段２０１が用いるパラメータ列を変動させるか否かの判定を行う。これによって、ランダムなタイミングにて上記内部状態変動（写像関数形変化）を達成することが可能である。
【００６３】
尚、図３においては上記前段写像計算手段２０１を一種類としたが、これに限定されない。即ち、前段写像計算手段２０１は、それぞれ異なる写像計算を行う複数の写像演算部が縦続接続され、順送りで写像計算を行う構成としても良い。
【００６４】
次に図３、図４に示した擬似乱数生成装置の動作を説明する。本擬似乱数生成装置においては、処理の開始時において、前段写像計算手段２０１等に与えるべき初期の値を生成するための前処理部１０１を有している。この前処理部１０１は、この実施形態における擬似乱数生成装置／擬似乱数生成プログラムに与えられる入力情報８０１としてのシードｓｅｅｄ、擬似ランダムビット列長ｎを得て、
初期の写像値：Ｘ０
初期のパラメータ列：ａ［１］〜ａ［ｎａ］
シード固有パラメータ列：ｋａ［１］〜ｋａ［ｎａ］
パラメータ変化量列１０２：ｐａ［１］〜ｐａ［ｎａ］
により構成される初期の値を生成する。
ここで、ｎａは、初期のパラメータ列ａ［  ］、シード固有パラメータ列ｋａ［  ］、パラメータ変化量列ｐａ［  ］の要素数を意味するシステム固定値であり、後述する具体的実施形態１、２では、ｎａ＝３２としている。前処理部１０１は、上記において生成した初期の写像値Ｘ０を写像値レジスタ１０３にセットし、初期のパラメータ列ａ［１］〜ａ［ｎａ］をパラメータ列レジスタ１０４にセットする。
【００６５】
更に、前処理部１０１は、
パラメータの最小値Ａｍｉｎ
パラメータの最大値Ａｍａｘ
パラメータの状態総数ΔＡ
パラメータ変量の最小値ＢＡ
を所定値（定数／固定値）としてセットする。
また、
初期のループカウンタｉ＝０，
初期のパラメータ番号ｊ＝１，
をセットする。
【００６６】
上記において、シードｓｅｅｄは乱数の種である。ランダムビット列長ｎはこれから生成するランダムビット列の長さである。パラメータ変化量列１０２は、シードｓｅｅｄに固有の情報であり、本実施形態の内部状態変動手段６０２で用いられる。より具体的には、パラメータ変化量列１０２は、内部状態変動手段６０２において、パラメータ列に変化を与えるための参照値として利用される。初期の写像値Ｘ０は、前段写像計算手段２０１と、後段写像計算手段２０３における写像計算に関する「写像値の初期値」を意味する。写像値は、後段写像計算手段２０３で更新され、ループ毎に更新される。また、パラメータ列は、前段写像計算手段２０１、後段写像計算手段２０３での写像計算で用いられる写像関数のコントロールパラメータの列である。パラメータ列は、変動判定部６０１においてＹｅｓとなるときに、内部状態変動手段６０２において、シード固有の情報であるパラメータ変化量列１０２と参照データ３０２を参照しながら更新される（写像値と異なり、ループ毎に更新されるわけではない）。パラメータ変化量列１０２は、シード固有の情報であり、内部状態変動手段６０２においてパラメータ列を変動させる場合に、その変化量の一部を与える。
【００６７】
前処理部１０１により初期の値の生成がなされた後に、パラメータ列レジスタ１０４にセットされた初期のパラメータ列及び写像値レジスタ１０３にセットされた初期の写像値Ｘ０は、前段写像計算手段２０１へ与えられる。そこで、前段写像計算手段２０１は、初期パラメータ列と初期の写像値Ｘ０とに基づき前述の演算により構成される前段写像演算を行う。前段写像演算の結果は、抽出手段３０１へ与えられる。抽出手段３０１は、前段写像計算手段２０１によって計算された値の所定位置のビット列を参照データ３０２として抽出し、また、別の位置のビット列を元データ３０３として抽出し、２つに分けて記憶する。ビット抽出を行う際の所定位置については、統計的に良質なランダムビット列の抽出が可能である位置が望ましく、例えば、「荒木俊輔, 宮崎武, 上原聡, “擬似乱数生成器に用いる整域におけるロジスティック写像に関する一考察," 第30 回情報理論とその応用シンポジウム予稿集(SITA2007), 2.1, November 2007.」(文献１８)、「荒木俊輔, 宮崎武, 上原聡, “擬似乱数生成器に用いる整数上のロジスティック写像に関する一考察," 2008年暗号と情報セキュリティシンポジウム予稿集(SCIS2008), 2A2-5, January 2008.」(文献１９)、「Shunsuke Araki, Takeru Miyazaki, and Satoshi Uehara, “A Study on Occurrence Rates per Bit for Outputs of the Logistic Map over Integers," Proc. of 2008 International Symposium on Information Theory and its Applications, pp.1316-1320, 2008.」(文献２０)、「荒木俊輔, 宮崎武, 上原聡, “整数上のロジスティック写像におけるビット毎の出現頻度に関する考察," 2009 年暗号と情報セキュリティシンポジウム予稿集(SCIS2009) , 2F1-3, January 2009.」(文献２１)、「荒木俊輔, 宮崎武, 上原聡, 硴崎賢一, “整数上のロジスティック写像におけるビットごとの出現率に関する考察, " 日本応用数理学会論文誌, Vol.25, No.3, pp.191-206, 2015.」(文献２２)などに記載の手法を採用することができる。
【００６８】
上記参照データ３０２は、図３から明らかな通り、選択判定部４０１、選択手段４０２、転置手段５０２、後段写像選択部２０２、変動判定部６０１、内部状態変動手段６０２において、選択や判定をランダムに行う際に用いられる。
【００６９】
また、参照データ３０２は、内部状態変動手段６０２などにおいて擬似乱数生成アルゴリズムにおける内部状態の遷移をランダムに与えることのみに用いられ、既述のように元データ３０３のランダムビット列として流用しない。これにより、本実施形態における擬似乱数生成装置の最終出力である出力ランダムビット列８０２が既知となった場合でも、内部状態の推測や同期が困難になり、出力ランダムビット列８０２を生成するために必須の入力情報８０１としてのシードや擬似ランダムビット列長ｎの推測が困難になる。
【００７０】
抽出手段３０１による処理が終了すると、選択判定部４０１が起動される。選択判定部４０１は、現ループにおいて抽出した元データ３０３をビット算出手段４００の処理において採用するか破棄するかを判定する。判定に当たっては、写像回数カウンタ６０３のカウント値及び参照データ３０２に基づき判定する。選択判定部４０１における判定がＹｅｓ（採用）の場合には、選択手段４０２へ移行する一方、判定がＮｏ（破棄）の場合には、ビット算出手段４００中の実質的な演算を行う選択手段４０２及び転置手段５０２の処理はスキップする。
【００７１】
選択判定部４０１における判定がＹｅｓとなり、選択手段４０２へ進んだ場合には、元データ３０３中の本実施形態に係る擬似乱数生成の当該ループにおいて出力とすべきランダムビット（ランダムビット列）を選択／抽出する。この選択／抽出に当たっては、参照データ３０２の情報を基に「採用するビット位置」を求め、元データ３０３中の「採用するビット位置」のビット（ビット列）を選択抽出し、転置前ランダムビット列４０３としてレジスタに加えて記憶する。
【００７２】
選択手段４０２により選択されたビット列は、ランダムビット長カウンタ４０４へ送られる。ランダムビット長カウンタ４０４は、送られてきたビット列のビット数をカウントアップする。この結果、ランダムビット長カウンタ４０４の値は、転置前ランダムビット列４０３のビット数だけカウントアップされる。
【００７３】
ランダムビット長カウンタ４０４のカウントアップが終了すると、転置判定部５０１が起動される。転置判定部５０１は、ランダムビット長カウンタ４０４の値に基づき、転置前ランダムビット列４０３のビット数（系列長）が転置処理を行うサイズに達したか否かを判定する。転置処理を行う場合のサイズ（ビット長）は予め決められており、例えば、入力情報８０１により設定されるものとする。転置判定部５０１による判定結果がＹｅｓ（所定サイズに達した）ことが検出された場合には、転置手段５０２の処理へ移行する一方、判定結果がＮｏ（所定サイズに達していない）ことが検出された場合には、転置手段５０２の処理をスキップする。
【００７４】
転置手段５０２へ進むと、転置前ランダムビット列４０３の内の転置処理を行うサイズ（ビット長）分を抽出したデータに対して転置処理を施す。転置処理にあたっては、参照データ３０２の情報を基に図４に示す決定部５００が上記複数の転置演算部５０２−１〜５０２−ｕのいずれを用いて転置を行うかの判定を行う。或いは、決定部５００が「転置ルール」を求め、当該転置ルールにより転置前ランダムビット列４０３のデータに所定転置処理を実行し、転置結果のビット列を一時保持する保持手段５０３に保持させる。
【００７５】
転置手段５０２の処理が終了すると、出力部５０４が起動される。出力部５０４は、例えば、入力情報８０１により設定され予め決められた出力すべき出力規定ビット長に基づき、保持手段５０３に保持されている転置後ランダムビット列が出力規定ビット長に達したかを判定し、達していれば出力命令を出力し保持手段５０３に保持されている転置後ランダムビット列を出力ランダムビット列８０２として出力する。かくして、保持手段５０３に保持された転置処理後のビット列は、所定のタイミングで出力ランダムビット列８０２として出力される。
【００７６】
転置手段５０２の処理が修了した場合は、出力部５０４の処理が実施されるか否かに関係せず、ランダムビット長カウンタ４０４をクリアするランダムビット長カウンタクリア５０５が実施される。
【００７７】
前記ランダムビット長カウンタクリア５０５が実施された場合、または、選択判定部４０１でＮｏが選択された場合、または、転置判定部５０１でＮｏが選択された場合、には、続いて、後段写像選択部２０２が起動される。後段写像選択部２０２は、上記参照データ３０２に基づき上記複数の写像計算部２０３−０〜２０３−（ｍ−１）のいずれを用いて写像を行うかの判定を行う。
【００７８】
後段写像選択部２０２による選択に続いて、後段写像計算手段２０３としての写像計算部２０３−０〜２０３−（ｍ−１）の中の選択された写像計算部２０３−ｉにおいて、所定の端数処理が実施される。端数処理関数については、下記の式０に示すものとすることができる。また、端数処理関数については、「宮崎武, 荒木俊輔, 上原聡, “端数処理の異なる整数上のロジスティック写像による系列の性質について," 2010 年暗号と情報セキュリティシンポジウム予稿集(SCIS2010), 3D3-1, January 2010.」（文献２３）、「Takeru Miyazaki, Shunsuke Araki, Satoshi Uehara, “Rounding Logistic Maps over Integers and the Properties of the Generated Sequences," Proc. of the Fifth International Workshop on Signal Design and its Application in Communications, pp. 21-24, 2011.」（文献２４）に記載のものを用いることができ、同文献にはその効果に関しても記載されている。
【００７９】
【数１】
2018097438.tif 000003
【００８０】
後段写像計算手段２０３が行われた後には、後段写像計算の結果である写像値が、既に写像値レジスタ１０３に記憶されている写像値に代えて記憶され、内部状態変動手段６０２が起動される。内部状態変動手段６０２は、上記参照データ３０２とパラメータ変化量列１０２に基づき変動判定部６０１において上記前段写像計算手段２０１が用いるパラメータ列を変動させるか否かの判定を行う。ここで、判定結果がＹｅｓ（変動させる）となった場合には、内部状態変動手段６０２の処理へ移行する一方、判定結果がＮｏ（変動させない）となった場合には、内部状態変動手段６０２の処理をスキップする。
【００８１】
内部状態変動手段６０２では、パラメータ列の変動がなされ、結果である新たなパラメータ列が、既にパラメータ列レジスタ１０４に記憶されているパラメータ列に代えて記憶される。このようにして、カオス写像の写像関数形を決定するパラメータ列を変動させる（変位を加え更新する）。変動手法（変位の与え方）としては、現在のループで使われている写像関数のパラメータ列（パラメータ列レジスタ１０４内のパラメータ列）、写像値レジスタ１０３内の写像値、パラメータ変化量列１０２及び参照データ３０２を基に計算することができる。この後、写像回数カウンタ６０３のカウント値をインクリメントして、終了判定部７０１へ進む。
【００８２】
終了判定部７０１では、生成された擬似ランダムビット列が所定長に達したか否かを判定する。判定に当たっては、ランダムビット列８０２のビット長が入力情報８０１の擬似ランダムビット長ｎに達したか否かを比較する。ここで、Ｙｅｓ（ｎに達した／終了）であることが検出された場合には、後処理部７０２へ移行する一方、Ｎｏ（ｎに達していない／継続）であることが検出された場合は、前段写像計算手段２０１に戻り、一連の処理を継続する。
【００８３】
後処理部７０２へ進んだ場合には、例えば各レジスタや各部のリセットなどの後処理が行われ処理が終了（エンド）となる。
【００８４】
既に示した文献９〜１７に示した攻撃法及び、これらと数理的、技術的に同等の攻撃法、を利用して最も簡易に（最も少ない計算量で）攻撃が達成できるケースは以下である。（Ａ）擬似乱数生成開始から終了まで同一の写像関数を利用する（内部状態を変動させない）。（Ｂ）写像毎に出力用のランダムビットを抽出する。（Ｃ）出力のランダムビットの順が写像の順と一致する。以上のケースと比較して、本実施形態に係る擬似乱数生成装置は、先行事例と同等の統計的側面における高い乱数性能を有しながら、上記の攻撃法を利用した攻撃（内部状態の推測、シードの推測）を困難にさせる効果を有する。
【００８５】
本実施形態に係る擬似乱数生成装置は、変動判定部６０１、内部状態変動手段６０２を有し、内部状態変動手段６０２は、参照データ３０２と、シード固有の情報であるパラメータ変化量列１０２とを参照して、シード情報の固有性を保ちながら、ランダムな変化量にて内部状態を変動させる（写像関数形を変化させる）と共に、変動判定部６０１は、参照データ３０２を参照して、ランダムなタイミングにて上記内部状態変動（写像関数形変化）を達成する構成を有している。即ち、攻撃者による内部状態の同期を困難なものとし、特に上記ケース（Ａ）による攻撃法の適用を困難にする効果（効果１）を有している。
【００８６】
本実施形態に係る擬似乱数生成装置は、選択判定部４０１と選択手段４０２とを有し、これらはそれぞれ参照データ３０２を参照し「採用するビット位置」を求め、元データ３０３中の「採用するビット位置」のビット（ビット列）を選択抽出し、転置前ランダムビット列４０３を得る構成を有している。即ち、写像毎に抽出されたランダムビット列の全てが、そのまま最終出力として利用される訳ではないため、特に上記ケースＢによる攻撃法の適用を困難にする効果（効果２）を有している。
【００８７】
本実施形態に係る擬似乱数生成装置は、転置手段５０２を有し、転置手段５０２では、参照データ３０２を参照し、「転置ルール」を求め、当該転置ルールにより転置前ランダムビット列４０３のデータに所定転置処理を実行し、転置結果のビット列を一時保持する保持手段５０３に保持させる構成を有している。即ち、写像毎に抽出されたランダムビット列が写像の順番で（ランダムビット列を抽出した順番で）出力される訳ではないため、特に上記ケースＣによる攻撃法の適用を困難にする効果（効果３）を有している。
【００８８】
本実施形態に係る擬似乱数生成装置によって生成されるランダムビット列は、前段写像計算手段２０１による演算後の値から抽出され、各種選択部における選択をランダム化させ、また、最終出力に到る前にランダムな転置を受ける等の処理が、参照データ３０２に基づき行われる一方、実施形態に係る擬似乱数生成装置の最終出力の候補は上記参照データ３０２とは明確に区分分離された元データ３０３に対する演算によって得るという、独立した２系統のランダムビット列によるという構成を有している。
【００８９】
参照データ３０２は、変動判定部６０１、内部状態変動手段６０２、選択判定部４０１、選択手段４０２、転置手段５０２、後段写像選択部２０２において参照され、必要とされるランダム性の提供源としての機能を有するものであり、特に上記効果１〜３に寄与する。この参照データ３０２は、本実施形態に係る擬似乱数生成装置の最終出力である出力ランダムビット列８０２の元データとして流用しないため、本実施形態に係る擬似乱数生成装置の最終出力情報からは、上記ランダム変化のタイミングに関する情報としての参照データ３０２が推定や予測されることはない。これにより、上記効果１〜３と併せて、各種攻撃法の適用を困難にする効果を有する。
【００９０】
また、出力ランダムビット列８０２は、前段写像計算手段２０１により拡大された写像値から得られる元データ３０３を用いてビット算出手段４００の演算により得られる。更に、ループにより次のステップに用いられる写像計算の入力（次ステップにおいて写像計算の元となる写像値）は、上記ビット算出手段４００の演算により得られる値を、後段写像計算手段２０３としての写像計算部２０３−０〜２０３−（ｍ−１）で演算して（例えば、除算における剰余、或いは、右ビットシフトで切り捨てられるビット列として）得られる。これにより、次のステップの前段写像計算の入力（次ステップにおいて写像計算の元となる写像値）は、本実施形態に係る擬似乱数生成装置の最終出力である出力ランダムビット列８０２の情報を一切含まないため、上記効果１〜３と併せて、各種攻撃法の適用を困難にする効果を有する。
【００９１】
本実施形態に係る擬似乱数生成装置は、後段写像選択部２０２、後段写像計算手段２０３としての写像計算部２０３−０〜２０３−（ｍ−１）を有する。後段写像選択部２０２は、参照データ３０２を参照し、複数の写像計算部２０３−０〜２０３−（ｍ−１）のいずれか一つをランダムに選択する構成を採用している。これにより、軌道のバリエーションを増やし、ランダムビット列のパターン数の増加に寄与すると共に、各種攻撃法の適用を困難にする効果を有する。
【００９２】
具体的実施形態１
次に具体的実施形態１を説明する。この具体的実施形態１は、テント写像を利用した場合の例である。本実施形態１では、シード長が５１２ビットのシード（あるいは鍵）ｓｅｅｄ、ランダムビット列長ｎを入力情報８０１として、ｎビットのランダムビット列（０，１の２値系列）｛ｂｎ｝を得るものである。具体的実施形態１において、演算精度は６４ビット、写像値Ｘのビット幅はｔ＝３２ビットとする。具体的実施形態１では整数演算化された以下のテント写像を用いる。
【００９３】
【数２】
2018097438.tif 000004
【００９４】
有限精度の計算機実装を与えるため、写像は、テント写像ＦＴ，Ａと端数処理関数Ｇξ（ξ＝０，１，・・・，７）を併せて達成される。即ち、次の式２に示す通りである。
【００９５】
【数３】
2018097438.tif 000005
【００９６】
尚、本具体的実施形態１では、式２による写像の計算を、以下に示す前段写像Ｆ′Ｔ，Ａと後段写像Ｇ′ξに分割して考える。
【００９７】
【数４】
2018097438.tif 000006
【００９８】
上記の写像（後段）Ｇ′ξ（Ｘ）は、ＸをＭで割ったあとに端数処理をする関数を示す。特にＭが２の冪乗である場合、すなわち Ｍ＝２ｓの場合は、ＸをＭで割る操作はＸのｓビット右シフトと同じ処理である。このとき、Ｘの下位ｓビットが切り捨てられる。つまり、ＸをＭで割る前（Ｘのｓビット右シフト以前）に、切り捨てられる位置は確定しており、Ｘの下位ｓビットが「切り捨てられるビット列」に相当する。
【００９９】
なお、Ｍが２の冪乗でない場合は、ＸをＭで割る操作によって切り捨てられる部分は、ＸをＭで割った余りの部分（剰余部）（ＸＭｏｄＭ，Ｍｏｄ（Ｘ，Ｍ），Ｘ％Ｍなどと記される）であり、これもＸをＭで割る操作と同じく、既知である。以上から、元データ３０３は、前段写像計算手段２０１により拡大された写像値のうち、後段写像計算手段２０３としての写像計算部２０３−０〜２０３−（ｍ−１）の除算における剰余、或いは、右ビットシフトで切り捨てられるビット列から抽出されるものであると結論することができる。
【０１００】
本具体的実施形態１の以降の説明においては、下記の定数を用いる。
【０１０１】
【数５】
2018097438.tif 000007
【０１０２】
以下に、図３に示した構成によって、この具体的実施形態１が実現されるものとして、動作を説明する。
【０１０３】
前処理部１０１では、５１２ビットのシード（あるいは鍵）ｓｅｅｄ、ランダムビット列長ｎ∈Ｚの入力を受け、所定関数により、初期の写像値、初期のパラメータ列、シード固有パラメータ列、パラメータ変化量列１０２を下記の通りに生成する。
【０１０４】
【数６】
2018097438.tif 000008
【０１０５】
シード固有パラメータ列ｋａ［１］〜ｋａ［３２］は、５１２ビットのシードｓｅｅｄを１６ビット単位に分割して、計３２ブロックに格納したものである（１６×３２＝５１２）。即ち、次の式１４に示す通りである。
【０１０６】
【数７】
2018097438.tif 000009
【０１０７】
パラメータ列ａ［１］〜ａ［３２］は、パラメータ列レジスタ１０４に格納され、前段写像計算手段２０１における写像計算で利用される。本具体的実施形態１では、次の式１５の通りである。
【０１０８】
【数８】
2018097438.tif 000010
【０１０９】
パラメータ変化量列１０２（ｐａ［１］〜ｐａ［３２］）は、内部状態変動手段６０２において、パラメータ列ａ［  ］に変化を与えるための参照値として利用される。本具体的実施形態１では、次の式１６の通りである。
【０１１０】
【数９】
2018097438.tif 000011
【０１１１】
前処理部１０１による処理の次に前段写像計算手段２０１による計算が行われる。この前段写像計算手段２０１では、式３に示した前段写像の計算を実施して写像中間値Ｙを得る。擬似乱数生成アルゴリズム開始時点では、前処理部１０１により生成され写像値レジスタ１０３に格納された初期の写像値Ｘ０を用いた写像計算がなされる。ここで、写像回数ｉ、パラメータ列ａ［ｊ］が選ばれているとすると、写像中間値Ｙは、次の式１７の通りである。
【０１１２】
【数１０】
2018097438.tif 000012
【０１１３】
前段写像計算手段２０１で使われるパラメータ列ａ［  ］について説明する。本具体的実施形態１では、擬似乱数生成アルゴリズム開始時点で、前処理部１０１にてａ［１］〜ａ［３２］の計３２個のパラメータが生成されている。第１回目の写像では、ｊ＝１番目のパラメータ、すなわちａ［１］が利用される。いまｊ番目（ｊ＝１，２，・・・，３２）のパラメータが選ばれているとする。後述の変動判定部６０１においてＮｏ（変動させない）と判定された場合は、次回の写像でも再び同じパラメータが用いられる。Ｙｅｓ（変動させる）と判定された場合は、後述の手法にてａ［ｊ］の値が更新されると共に、ｊのインクリメント（ｊ＝ｊ＋１）が実行され、次回の写像では、次の番号のパラメータが使われる。ただしｊ＞３２の場合はｊ＝１に戻る。
【０１１４】
前段写像計算手段２０１に次いで抽出手段３０１による処理が行われる。抽出手段３０１では前段写像計算手段２０１による計算後に得た写像中間値Ｙの所定位置のビットを抽出して、参照データ３０２として、ｒｉ［ｋ］、（ｒｉ［ｋ］∈｛０，１｝、ｋ＝１，２，・・・，１７）、および、元データ３０３として、ｒｏ［ｋ］、（ｒｏ［ｋ］∈｛０，１｝，ｋ＝１，２，・・・，８）を得る。本具体的実施形態１では、Ｙは６４ビットである。Ｙを２進数表記した以下の式１８に示す配列を考える。これにより、ｒｉ［ｋ］とｒｏ［ｋ］は式１９、式２０となる。
【０１１５】
【数１１】
2018097438.tif 000013
【０１１６】
具体的実施形態１においては、参照データ３０２として、ｒｉ［ｋ］、（ｒｉ［ｋ］∈｛０，１｝，ｋ＝１，２，・・・，１７）により示されるランダムビット列は、選択判定部４０１、選択手段４０２、後段写像選択部２０２、転置手段５０２、変動判定部６０１、内部状態変動手段６０２の計６箇所において参照されるランダムデータとして利用される。参照データ３０２としてのｒｉが参照される範囲はアルゴリズムの内部処理に限られており、外部出力用のランダムビット列としては利用されない。
【０１１７】
なお、元データ３０３であるｒｏ［ｋ］（ｒｏ［ｋ］∈｛０，１｝，ｋ＝１，２，・・・，８）は、具体的実施形態１の出力となるランダムビット列の「候補」である。即ち、元データ３０３であるｒｏの全てが採用される訳ではない。
【０１１８】
抽出手段３０１による処理に続いて選択判定部４０１が処理を行う。選択判定部４０１は、参照データ３０２であるｒｉのデータを参照して、擬似乱数を選択する選択手段４０２の処理へ移行するか否かを判定する。参照データ３０２であるｒｉ［ｋ］（ｋ＝１，２，・・・，１７）のうち、ｒｉ［１］＝１（Ｙｅｓ）ならば、選択手段４０２の処理へ移行する。一方、ｒｉ［１］＝０（Ｎｏ）ならば後段写像選択部２０２に移行する。
【０１１９】
前述の選択判定部４０１がＹｅｓと判定した場合に、選択手段４０２は次の処理を行う。選択手段４０２は、参照データ３０２であるｒｉのデータを参照して、元データ３０３であるｒｏのデータ中から外部に出力するランダムビット（列）を選択する。本実施形態では、参照データ３０２のうちｒｉ［２］〜ｒｉ［９］の８ビットを参照し、ｒｉ［ｋ］＝１（ｋ＝２，３，４，・・・，９）（Ｙｅｓ）ならばｒｏ［ｋ−１］を有効なビット列である転置前ランダムビット列４０３として、レジスタｔｍｐ［  ］に格納する。一方、ｒｉ［ｋ］＝０（ｋ＝２，３，４，・・・，９）（Ｎｏ）ならば、ｒｏ［ｋ−１］は如何なる用途にも使用されず破棄される。
【０１２０】
選択手段４０２による処理の後にランダムビット長カウンタ４０４では、選択手段４０２にて選ばれた外部に出力されるランダムビット列の長さをカウントする。
【０１２１】
ランダムビット長カウンタ４０４のカウントを受けて転置判定部５０１が動作する。転置判定部５０１では、レジスタｔｍｐ［  ］に格納された転置前ランダムビット列４０３のデータサイズを参照して、転置手段５０２の処理へ移行するか否かを判定する。本実施形態では、レジスタｔｍｐ［  ］に格納された転置前ランダムビット列４０３の長さが８ビットに達している（Ｙｅｓ）ならば転置手段５０２による処理へ移行する。一方、転置前ランダムビット列４０３の長さが８ビット未満（Ｎｏ）ならば、後段写像選択部２０２へ移行する。尚、転置手段５０２による処理へ移行する場合は、レジスタｔｍｐ［  ］の先頭から８ビットがレジスタｒｅｆ［  ］に移されると共に、レジスタｔｍｐ［  ］の先頭８ビットは消去される。また、レジスタｔｍｐ［  ］の９ビット目以降のデータが繰り上がるようになっている。
【０１２２】
転置判定部５０１による処理の次には、転置手段５０２による処理が行われる。転置手段５０２では、転置判定部５０１による判定がＹｅｓのときに限り、上述のレジスタｒｅｆ［  ］に生成された８ビットのデータの順序を並び替える処理を行う。本実施形態では、予めＰ０〜Ｐ１５の１６方式の転置ルールが用意されている。参照データ３０２のうちｒｉ［１０］〜ｒｉ［１３］の計４ビットを、１０進展開した値ξ＝｛０，１，２，・・・，１５｝に対応する転置ルールＰξが選択される。転置後のデータは、保持手段５０３であるレジスタＯＵＴ［  ］に格納される。
【０１２３】
本実施形態において用いる、上記１６方式の転置ルールとは、レジスタｒｅｆ［  ］のｉ番目に写す写像ｔ：Ｉ→Ｉ，（ｉ∈Ｉ，ｔ（ｉ）∈Ｉ，Ｉ＝｛１，２，・・・，８｝，ｔは全単射)として与えられる。写像ｔは、全部で８！（８の階乗）通りある。本実施形態では、上記の８の階乗通り中の１６通りを選択したものである。以下に、第ξ（ξ＝０，１，２，・・・，１５）番目の写像ｔを意味するビット転置表Ｐξを、表１（Ｐ０〜Ｐ７）と表２（Ｐ８〜Ｐ１５）に示す。
【０１２４】
【表１】
2018097438.tif 000014
【０１２５】
【表２】
2018097438.tif 000015
【０１２６】
転置手段５０２の処理が終了すると、出力部５０４が起動される。保持手段５０３であるレジスタＯＵＴ［  ］に転置後のデータが格納されると、所定のタイミングにおいて、出力部５０４により出力命令が出力されて上記保持手段５０３であるレジスタＯＵＴ［  ］に保持されたビット列を出力ランダムビット列８０２として出力する。既述の通り、出力部５０４は、保持手段５０３に保持されている転置後ランダムビット列が出力規定ビット長に達したかを判定し、達していれば出力命令を出力する。
【０１２７】
転置手段５０２の処理が修了した場合は、出力部５０４の処理が実施されるか否かに関係せず、ランダムビット長カウンタ４０４をクリアするランダムビット長カウンタクリア５０５が実施される。前記ランダムビット長カウンタクリア５０５が実施された場合、または、選択判定部４０１でＮｏが選択された場合、または、転置判定部５０１でＮｏが選択された場合は、続いて、後段写像選択部２０２が起動される。
【０１２８】
後段写像選択部２０２では、予め用意してあるｍ個の端数処理関数Ｇ０〜Ｇｍ−１に対応する後段写像関数Ｇ′０〜Ｇ′ｍ−１のうち、参照データ３０２の所定位置データを参照して選択する。本実施形態では、ｍ＝８として、予めＧ′０〜Ｇ′７の８方式の後段写像関数が用意されている。参照データ３０２のうちｒｉ［１４］〜ｒｉ［１６］の計３ビットを、１０進展開した値ξ∈｛０，１，２，・・・，７｝に対応する後段写像関数Ｇ′ξが選択される。ここで、後段写像関数Ｇ′ξ（Ｘ）（ξ＝０，１，２，・・・，７）の例を、以下の式（Ａ）に示す。
【０１２９】
【数１２】
2018097438.tif 000016
【０１３０】
後段写像選択部２０２の処理に次いで、後段写像計算手段２０３の処理が行われる。後段写像計算手段２０３としての写像計算部２０３−０〜２０３−（ｍ−１）の中の選択された写像計算部２０３−ｉにおいて、前段写像計算手段２０１において得られた写像中間値Ｙに基づき、後段写像選択部２０２で選択された番号ξに対応する後段写像関数Ｇ′ξの計算を実施して写像値を更新する。現在の写像回数がｉであるならば、更新された写像値は次の式２１に示されるようである。
【０１３１】
【数１３】
2018097438.tif 000017
【０１３２】
更新された写像値は、写像値レジスタ１０３の写像値に上書きされる。後段写像計算手段２０３の処理の後には、変動判定部６０１による処理が行われる。変動判定部６０１では、参照データ３０２の所定位置データを参照して、擬似乱数生成アルゴリズムの内部状態に変動を与えるか否かを決定する。本実施形態では、参照データ３０２であるｒｉ［ｋ］（ｋ＝１，２，・・・，１７）のうち、ｒｉ［１７］＝１である（Ｙｅｓ／変動を与える）ならば、内部状態変動手段６０２による処理に移動し、ｒｉ［１７］＝０である（Ｎｏ／変動しない）ならば、写像回数カウンタ６０３の処理へ移行する。
【０１３３】
上記においてｒｉ［１７］＝１であり、内部状態変動手段６０２による処理に移行すると、内部状態変動手段６０２では、パラメータ変化量列１０２及び参照データ３０２を参照してパラメータａ［  ］に変動を与える。いま、ｊ（１，２，・・・，３２）番目のパラメータａ［ｊ］が選ばれているとする。本実施形態では、次の式２２による変動が行われる。
【０１３４】
【数１４】
2018097438.tif 000018
【０１３５】
上記内部状態変動手段６０２では、上記の式２２による変動を行った場合には、パラメータ列レジスタ１０４のパラメータ列に対し上記変動に係るパラメータ列を上書きして更新する。この処理の後に、或いは変動判定部６０１においてＮｏとなったときには、写像回数カウンタｊ＝ｊ＋１が計算され、次回の写像では、次の番号のパラメータが使われる。ただしｊ＞３２の場合はｊ＝１に戻る。この後、写像回数カウンタ６０３のカウント値をインクリメントして、終了判定部７０１へ進む。
【０１３６】
終了判定部７０１では、擬似ランダムビット列が所定長に達したか否かを判定する。Ｙｅｓ（終了）ならば、後処理部７０２へ移行し、Ｎｏ（終了ではない）ならば、前段写像計算手段２０１に戻り、一連の処理を継続する。
【０１３７】
後処理部７０２へ進んだ場合には、例えば各レジスタや各部のリセットなどの後処理が行われ処理（アルゴリズム）が終了される。
【０１３８】
具体的実施形態２
次に具体的実施形態２を説明する。この具体的実施形態２は、ロジスティック写像を利用した場合の例である。システムパラメータとして
写像値Ｘのビット幅：ｔ＝６４ビット
演算精度：１９２ビット
を利用する。
【０１３９】
ユーザは、
ｓｅｅｄ：  ６４ビットの乱数種
ｎ：  出力ランダムビット列のビット数
を擬似乱数生成装置に入力する。
これにより、擬似乱数生成装置は次のランダムビット列を出力する。
｛ｂ１，ｂ２，・・・，ｂｎ｝：ｎビットの出力ランダムビット列
ただし、ｂｉは０または１とする。
【０１４０】
具体的実施形態２では、次の通りの整数演算化されたロジスティック写像を用いる。
【０１４１】
【数１５】
2018097438.tif 000019
【０１４２】
ここに、有限精度の計算機実装を与えるため、写像は、ロジスティック写像ＦＬ，ＡＬと端数処理関数Ｇξ（ξ＝０，１，・・・，７）を併せて達成される。即ち、以下の式２４により表される。
【０１４３】
【数１６】
2018097438.tif 000020
【０１４４】
尚、本具体的実施形態２では、式（２４）による写像の計算を、以下に示す前段写像Ｆ´Ｌ，ＡＬと後段写像Ｇ′′ξに分割して実行する。
【０１４５】
【数１７】
2018097438.tif 000021
【０１４６】
本具体的実施形態２の以降の説明においては、下記の定数を用いる。
【０１４７】
【数１８】
2018097438.tif 000022
【０１４８】
以下に、図３に示した構成によってこの具体的実施形態２が実現されるものとして、動作を説明する。
【０１４９】
前処理部１０１では、ｔ（＝６４）ビットのシード（あるいは鍵）ｓｅｅｄ、ランダムビット列長ｎ∈Ｚの入力を受け、所定関数により、初期の写像値、初期のパラメータ列、シード固有パラメータ列、パラメータ変化量列１０２を下記の通りに生成する。
【０１５０】
【数１９】
2018097438.tif 000023
【０１５１】
前処理部１０１では、初期の写像値Ｘ０をｓｅｅｄ情報を基に算出し，Ｘｉ＋１＝ＦＬ，ＡＬ，ｍａｘ（Ｘｉ）を計算する。その過程で、シード固有パラメータ列の要素として、ｋａ［ｊ］＝Ｘ５ｊ＋１００とする６４ビットの整数を得る。即ち、次の式３６に示されるようになる。
【０１５２】
【数２０】
2018097438.tif 000024
【０１５３】
パラメータ列ａ［１］〜ａ［３２］は、パラメータ列レジスタ１０４に格納され、前段写像計算手段２０１における写像計算で利用される。本具体的実施形態２では、次の式３７の通りである。
【０１５４】
【数２１】
2018097438.tif 000025
【０１５５】
パラメータ変化量列ｐａ［１］〜ｐａ［３２］は、内部状態変動手段６０２において、パラメータ列ａ［  ］に変化を与えるための参照値として利用される。本具体的実施形態２では、次の式３８の通りである。
【０１５６】
【数２２】
2018097438.tif 000026
【０１５７】
前処理部１０１の次に前段写像計算手段２０１による計算が行われる。この前段写像計算手段２０１では、式２５に示した前段写像の計算を実施して写像中間値Ｙを得る。擬似乱数生成アルゴリズム開始時点では、前処理部１０１により生成され写像値レジスタ１０３に格納された初期の写像値Ｘ０を用いた写像計算がなされる。ここで、写像回数ｉ、パラメータ列ａ［ｊ］が選ばれているとすると、写像中間値Ｙは、次の式３９の通りである。
【０１５８】
【数２３】
2018097438.tif 000027
【０１５９】
前段写像計算手段２０１で使われるパラメータ列ａ［  ］について説明する。本具体的実施形態２では、擬似乱数生成アルゴリズム開始時点で、前処理部１０１にてａ［１］〜ａ［３２］の計３２個のパラメータが生成されている。第１回目の写像では、ｊ＝１番目のパラメータ、すなわちａ［１］が利用される。いまｊ番目（ｊ＝１，２，・・・，３２）のパラメータが選ばれているとする。後述の変動判定部６０１においてＮｏ（変動させない）と判定された場合は、次回の写像でも再び同じパラメータが用いられる。Ｙｅｓ（変動させる）と判定された場合は、後述の手法にてａ［ｊ］の値が更新されると共に、ｊのインクリメント（ｊ＝ｊ＋１）が実行され、次回の写像では、次の番号のパラメータが使われる。ただしｊ＞３２の場合はｊ＝１に戻る。
【０１６０】
前段写像計算手段２０１に次いで抽出手段３０１による処理が行われる。抽出手段３０１では前段写像計算手段２０１による計算後に得た写像中間値Ｙの所定位置のビット列を抽出して、参照データ３０２として、ｒｉ［ｋ］、（ｒｉ［ｋ］∈｛０，１｝、ｋ＝１，２，・・・，６１）、および、元データ３０３として、ｒｏ［ｋ］、（ｒｏ［ｋ］∈｛０，１｝，ｋ＝１，２，・・・，４８）を得る。本具体的実施形態２では、Ｙは１９２ビットである。参照データ３０２はＹの４９ビット目から６１ビット目までの１３ビット分と１１３ビット目から１６０ビット目までの４８ビット分の計６１ビット分と、元データ３０３はＹの６５ビット目から１１２ビット目までの４８ビット分、合計で１０９ビット分をランダムビット列として抽出する。具体的に、Ｙを２進表記した配列Ｙを２進数表記した以下の式４０に示す配列を考える。これにより、ｒｉ［ｋ］とｒｏ［ｋ］は式４１、式４２となる。
【０１６１】
【数２４】
2018097438.tif 000028
【０１６２】
具体的実施形態２においては、参照データ３０２として、ｒｉ［ｋ］、（ｒｉ［ｋ］∈｛０，１｝，ｋ＝１，２，・・・，１７）により示されるランダムビット列は、選択判定部４０１、選択手段４０２、後段写像選択部２０２、転置手段５０２、変動判定部６０１、内部状態変動手段６０２の計６箇所において参照されるランダムデータとして利用される。参照データ３０２としてのｒｉが参照される範囲はアルゴリズムの内部処理に限られており、外部出力用のランダムビット列としては利用されない。
【０１６３】
なお、元データ３０３であるｒｏ［ｋ］（ｒｏ［ｋ］∈｛０，１｝，ｋ＝１，２，・・・，４８）は、具体的実施形態２の出力となるランダムビット列の「候補」である。即ち、元データ３０３であるｒｏの全てが採用される訳ではない。
【０１６４】
抽出手段３０１による処理に続いて選択判定部４０１が処理を行う。選択判定部４０１は、参照データ３０２であるｒｉのデータを参照して、擬似乱数を選択する選択手段４０２の処理へ移行するか否かを判定する。参照データ３０２であるｒｉ［ｋ］（ｋ＝１，２，・・・，６１）のうち、ｒｉ［１］＝１（Ｙｅｓ／選択する）ならば、選択手段４０２の処理へ移行する。一方、ｒｉ［１］＝０（Ｎｏ／選択しない）ならば後段写像選択部２０２に移行する。
【０１６５】
前述の選択判定部４０１がＹｅｓと判定した場合に、選択手段４０２は次の処理を行う。選択手段４０２は、参照データ３０２であるｒｉのデータを参照して、元データ３０３であるｒｏのデータ中から外部に出力するランダムビット（列）を選択する。本実施形態では、参照データ３０２のうちｒｉ［１４］〜ｒｉ［６１］の４８ビットを参照し、ｒｉ［ｋ］＝１（ｋ＝１４，１５，・・・，６１）（Ｙｅｓ）ならばｒｏ［ｋ−１３］を有効なビット列である転置前ランダムビット列４０３として、レジスタｔｍｐ［  ］に格納する。一方、ｒｉ［ｋ］＝０（ｋ＝１４，１５，・・・，６１）（Ｎｏ）ならば、ｒｏ［ｋ−１３］は如何なる用途にも使用されず破棄される。
【０１６６】
選択手段４０２による処理の後にランダムビット長カウンタ４０４では、選択手段４０２にて選ばれた外部に出力されるランダムビット列の長さをカウントする。
【０１６７】
ランダムビット長カウンタ４０４のカウントを受けて転置判定部５０１が動作する。転置判定部５０１では、レジスタｔｍｐ［  ］に格納された転置前ランダムビット列４０３のデータサイズを参照して、転置手段５０２の処理へ移行するか否かを判定する。本実施形態では、レジスタｔｍｐ［  ］に格納された転置前ランダムビット列４０３の長さが６４ビットに達している（Ｙｅｓ）ならば転置手段５０２による処理へ移行する。一方、転置前ランダムビット列４０３の長さが６４ビット未満（Ｎｏ）ならば、後段写像選択部２０２へ移行する。尚、転置手段５０２による処理へ移行する場合は、レジスタｔｍｐ［  ］の先頭から６４ビットがレジスタｒｅｆ［  ］に移されると共に、レジスタｔｍｐ［  ］の先頭６４ビットは消去される。また、レジスタｔｍｐ［  ］の６５ビット目以降のデータが繰り上がるようになっている。
【０１６８】
転置判定部５０１による処理の次には、転置手段５０２による処理が行われる。転置手段５０２では、転置判定部５０１による判定がＹｅｓのときに限り、上述のレジスタｒｅｆ［  ］に生成された６４ビットのデータの順序を並び替える処理を行う。本実施形態では、予めＰ０〜Ｐ２５５の２５６方式の転置ルールが用意されている。参照データ３０２のうちｒｉ［２］〜ｒｉ［９］の計８ビットを、１０進展開した値ξ＝｛０，１，２，・・・，２５５｝に対応する転置ルールＰξが選択される。転置後のデータは、保持手段５０３であるレジスタＯＵＴ［  ］に格納される。
【０１６９】
本実施形態において用いる、上記２５６方式の転置ルールとは、レジスタｒｅｆ［  ］のｉ番目に写す写像ｔ：Ｉ→Ｉ，（ｉ∈Ｉ，ｔ（ｉ）∈Ｉ，Ｉ＝｛１，２，・・・，６４｝，ｔは全単射)として与えられる。写像ｔは、全部で６４！（６４の階乗）通りある。本実施形態では、上記の６４の階乗通り中の２５６通りを選択したものである。８ビット転置の場合の具体例を、既に表１と表２に示した。６４ビット転置の場合も，写像前と写像後で全単射の関係が保たれるように同様に作成すればよいため、６４ビット転置の具体例は省略する。
【０１７０】
転置手段５０２の処理が終了すると、出力部５０４が起動される。保持手段５０３であるレジスタＯＵＴ［  ］に転置後のデータが格納されると、所定のタイミングにおいて、出力部５０４により出力命令が出力されて上記保持手段５０３であるレジスタＯＵＴ［  ］に保持されたビット列を出力ランダムビット列８０２として出力する。既述の通り、出力部５０４は、保持手段５０３に保持されている転置後ランダムビット列が出力規定ビット長に達したかを判定し、達していれば出力命令を出力する。
【０１７１】
出力部５０４の処理が終了すると、ランダムビット長カウンタ４０４をクリアする処理ランダムビット長カウンタクリア５０５が行われ、続いて後段写像選択部２０２が起動される。後段写像選択部２０２では、予め用意してあるｍ個の端数処理関数Ｇ０〜Ｇｍ−１に対応する後段写像関数Ｇ′′０〜Ｇ′′ｍ−１のうち、参照データ３０２の所定位置データを参照して選択する。本実施形態では、ｍ＝８として、予めＧ′′０〜Ｇ′′７の８方式の後段写像関数が用意されている。参照データ３０２のうちｒｉ［１０］〜ｒｉ［１２］の計３ビットを、１０進展開した値ξ∈｛０，１，２，・・・，７｝に対応する後段写像関数Ｇ′′ξが選択される。ここで、後段写像関数Ｇ′′ξ（Ｘ）（ξ＝０，１，２，・・・，７）の例を、以下の式（Ｂ）に示す。
【０１７２】
【数２５】
2018097438.tif 000029
【０１７３】
後段写像選択部２０２の処理に次いで、後段写像計算手段２０３の処理が行われる。後段写像計算手段２０３としての写像計算部２０３−０〜２０３−（ｍ−１）の中の選択された写像計算部２０３−ｉにおいて、前段写像計算手段２０１において得られた写像中間値Ｙに基づき、後段写像選択部２０２で選択された番号ξに対応する後段写像関数Ｇ′′ξの計算を実施して写像値を更新する。現在の写像回数がｉであるならば、更新された写像値は次の式４３に示されるようである。
【０１７４】
【数２６】
2018097438.tif 000030
【０１７５】
更新された写像値は、写像値レジスタ１０３の写像値に上書きされる。後段写像計算手段２０３の処理の後には、変動判定部６０１による処理が行われる。変動判定部６０１では、参照データ３０２の所定位置データを参照して、擬似乱数生成アルゴリズムの内部状態に変動を与えるか否かを決定する。本実施形態では、参照データ３０２であるｒｉ［ｋ］（ｋ＝１，２，・・・，６１）のうち、ｒｉ［１３］＝１である（Ｙｅｓ／変動を与える）ならば、内部状態変動手段６０２による処理に移動し、ｒｉ［１３］＝０である（Ｎｏ／変動しない）ならば、写像回数カウンタ６０３の処理へ移行する。
【０１７６】
上記においてｒｉ［１３］＝１であり、内部状態変動手段６０２による処理に移行すると、内部状態変動手段６０２では、パラメータ変化量列１０２及び参照データ３０２を参照してパラメータａ［  ］に変動を与える。いま、ｊ（１，２，・・・，３２）番目のパラメータａ［ｊ］が選ばれているとする。本実施形態では、次の式４４による変動が行われる。
【０１７７】
【数２７】
2018097438.tif 000031
【０１７８】
上記内部状態変動手段６０２では、同時に、ｊ＝ｊ＋１が計算され、次回の写像では、次の番号のパラメータが使われる。ただしｊ＞３２の場合はｊ＝１に戻る。この後、写像回数カウンタ６０３のカウント値をインクリメントして、終了判定部７０１へ進む。
【０１７９】
終了判定部７０１では、擬似ランダムビット列が所定長に達したか否かを判定する。Ｙｅｓ（終了）ならば、後処理部７０２へ移行し、Ｎｏ（終了ではない）ならば、前段写像計算手段２０１に戻り、一連の処理を継続する。
【０１８０】
後処理部７０２へ進んだ場合には、例えば各レジスタや各部のリセットなどの後処理が行われ処理（アルゴリズム）が終了される。
【０１８１】
以上説明した具体的実施形態１、２は、構成がシンプルなため、実装の容易性と処理の高速性が特徴である。また、当擬似乱数生成法はストリーム暗号の擬似乱数生成部として転用することが考えられる。
本発明に係る擬似乱数生成装置とプログラムは、安全な擬似乱数が必要とされるアプリケーション、ツール、 ライブラリおよび情報システム、 電子デバイスに適用すると好適である。ここに安全とは、擬似乱数生成法から生成された擬似乱数列を既知情報としたときに、 当該乱数列の生成に使われたシード情報を解析的に得ることが困難であることを意味する。
【０１８２】
より具体的には、本発明に係る擬似乱数生成装置とプログラムは、情報セキュリティ分野全般、例えば公開鍵認証システム（ＰＫＩ）における安全な鍵ペア（秘密鍵、公開鍵）の生成、共通鍵暗号における安全な共通鍵の生成、暗号化通信における安全なセッション鍵の生成、無線通信における鍵の生成、その他ランダムパスワード、 ランダム鍵類の生成などに用いることができる。
【符号の説明】
【０１８３】
１０１  前処理部
１０２  パラメータ変化量列
１０３  写像値レジスタ
１０４  パラメータ列レジスタ
２０１  前段写像計算手段
２０２  後段写像選択部
２０３  後段写像計算手段
２０３−０〜２０３−（ｍ−１）  写像計算部
３０１  抽出手段
３０２  参照データ
３０３  元データ
４００  ビット算出手段
４０１  選択判定部
４０２  選択手段
４０３  転置前ランダムビット列
４０４  ランダムビット長カウンタ
５００  決定部
５０１  転置判定部
５０２  転置手段
５０２−１〜５０２−ｕ  転置演算部
５０２  転置手段
５０３  保持手段
５０４  出力部
５０５  ランダムビット長カウンタクリア
６０１  変動判定部
６０２  内部状態変動手段
６０３  写像回数カウンタ
７０１  終了判定部
７０２  後処理部
８０１  入力情報
８０２  出力ランダムビット列
【図１】
2018097438.tif 000032
【図２】
2018097438.tif 000033
【図３】
2018097438.tif 000034
【図４】
2018097438.tif 000035