(57)【要約】【課題】  長周期性、一様性の点で良好で、簡単な構成または処理で実現することを可能とする。  【解決手段】  （Ｘn ＝ｐＸn-12＋ｑＸn-1＋ｒ （mod ２N）  但し、ｐ＝４ｋ＋２（ｋ＝０，１，２，・・・）  ｑ，ｒ：奇数）の式によって表される非線形写像によって乱数を生成する。Ｎ＝４で（ｐ＝２，ｑ＝３，ｒ＝１）の例では、２4の周期を持つ軌道が存在する（図１Ａ）。（ｐ＝２，ｑ＝１，ｒ＝１）の例では、２3の周期を持つ軌道が２組存在している（図１Ｂ）。（ｐ＝２，ｑ＝３，ｒ＝３）の例では、２2の周期を持つ軌道が２組、周期２の周期軌道が４組，共存している（図１Ｃ）。【選択図】  図１
2005107910.tif 000002
【特許請求の範囲】
【請求項１】
式（１）で表される非線形写像によってＮビットの乱数を生成する乱数発生装置。
Ｘn ＝ａmＸn-1m＋ａm-1Ｘn-1m-1＋ａm-2Ｘn-1m-2＋・・・・
＋ａ2Ｘn-12＋ａ1Ｘn-1＋ａ0 （mod ２N）                （１）
但し、ａ2＋ａ4＋ａ6＋・・・：偶数，ａ3＋ａ5＋ａ7＋・・・：偶数
ａ1，ａ0               ：奇数である。
【請求項２】
式（２）で表される非線形写像によってＮビットの乱数を生成する乱数発生装置。
Ｘn＝ｐＸn-12＋ｑＸn-1＋ｒ  (mod２N)    （２）
但し、ｐ＝４ｋ＋２（ｋ＝０，１，２，・・・），ｑ，ｒ：奇数とする。
【請求項３】
請求項２において、
ｑ＝４ｌ＋３（ｌ＝０，１，２，・・・）に設定した乱数発生装置。
【請求項４】
請求項２において、
ｑ＝４ｌ＋１（ｌ＝０，１，２，・・・）およびｒ＝１，５，９，・・・に設定した乱数発生装置。
【請求項５】
請求項２において、
ｑ＝４ｌ＋１（ｌ＝０，１，２，・・・）およびｒ＝３，７，１１，・・・・に設定した乱数発生装置。
【請求項６】
Ｎビットのｐ（＝４ｋ＋２（ｋ＝０，１，２，・・・））と、Ｎビットの前の状態の値Ｘn-1とを乗算し、２Ｎビットの出力ｐＸn-1を生成する第１の乗算器と、
上記第１の乗算器の出力の下位Ｎビットと、Ｎビットのｑ（奇数）とを加算する第１の加算器と、
上記第１の加算器の出力の内の最上位ビットを除くＮビットと、Ｘn-1とを乗算する第
２の乗算器と、
上記第２の乗算器の出力の下位Ｎビットと、Ｎビットのｒ（奇数）とを加算する第２の加算器とを備え、
上記第２の加算器の出力の内の最上位ビットを除くＮビットをｎ番目の出力Ｘnとして
出力する乱数発生装置。
【請求項７】
式（１）で表される非線形写像によってＮビットの乱数を生成する乱数発生方法。
Ｘn ＝ａmＸn-1m＋ａm-1Ｘn-1m-1＋ａm-2Ｘn-1m-2＋・・・・
＋ａ2Ｘn-12＋ａ1Ｘn-1＋ａ0 （mod ２N）                （１）
但し、ａ2＋ａ4＋ａ6＋・・・：偶数，ａ3＋ａ5＋ａ7＋・・・：偶数
ａ1，ａ0               ：奇数である。
【請求項８】
式（２）で表される非線形写像によってＮビットの乱数を生成する乱数発生方法。
Ｘn＝ｐＸn-12＋ｑＸn-1＋ｒ  (mod２N)    （２）
但し、ｐ＝４ｋ＋２（ｋ＝０，１，２，・・・），ｑ，ｒ：奇数とする。
【請求項９】
請求項８において、
ｑ＝４ｌ＋３（ｌ＝０，１，２，・・・）に設定した乱数発生方法。
【請求項１０】
請求項８において、
ｑ＝４ｌ＋１（ｌ＝０，１，２，・・・）およびｒ＝１，５，９，・・・に設定した乱数発生方法。
【請求項１１】
請求項８において、
ｑ＝４ｌ＋１（ｌ＝０，１，２，・・・）およびｒ＝３，７，１１，・・・・に設定した乱数発生方法。
【請求項１２】
Ｎビットのｐ（＝４ｋ＋２（ｋ＝０，１，２，・・・））と、Ｎビットの前の状態の値Ｘn-1とを乗算し、２Ｎビットの出力ｐＸn-1を生成する第１の乗算ステップと、
上記第１の乗算ステップの出力の下位Ｎビットと、Ｎビットのｑ（奇数）とを加算する第１の加算ステップと、
上記第１の加算ステップの出力の内の最上位ビットＭＳＢを除くＮビットと、Ｘn-1と
を乗算する第２の乗算ステップと、
上記第２の乗算ステップの出力の下位Ｎビットと、Ｎビットのｒ（奇数）とを加算する第２の加算ステップとを備え、
上記第２の加算ステップの出力の内の最上位ビットＭＳＢを除くＮビットをｎ番目の出力Ｘnとして出力する乱数発生方法。
【請求項１３】
コンピュータに対して、式（１）で表される非線形写像によってＮビットの乱数を生成する乱数発生方法を実行させるプログラム。
Ｘn ＝ａmＸn-1m＋ａm-1Ｘn-1m-1＋ａm-2Ｘn-1m-2＋・・・・
＋ａ2Ｘn-12＋ａ1Ｘn-1＋ａ0 （mod ２N）                （１）
但し、ａ2＋ａ4＋ａ6＋・・・：偶数，ａ3＋ａ5＋ａ7＋・・・：偶数
ａ1，ａ0               ：奇数である。
【請求項１４】
コンピュータに対して、式（２）で表される非線形写像によってＮビットの乱数を生成する乱数発生方法を実行させるプログラム。
Ｘn＝ｐＸn-12＋ｑＸn-1＋ｒ  (mod２N)    （２）
但し、ｐ＝４ｋ＋２（ｋ＝０，１，２，・・・），ｑ，ｒ：奇数とする。
【請求項１５】
請求項１４において、
ｑ＝４ｌ＋３（ｌ＝０，１，２，・・・）に設定したプログラム。
【請求項１６】
請求項１４において、
ｑ＝４ｌ＋１（ｌ＝０，１，２，・・・）およびｒ＝１，５，９，・・・に設定したプログラム。
【請求項１７】
請求項１４において、
ｑ＝４ｌ＋１（ｌ＝０，１，２，・・・）およびｒ＝３，７，１１，・・・・に設定したプログラム。
【請求項１８】
Ｎビットのｐ（＝４ｋ＋２（ｋ＝０，１，２，・・・））と、Ｎビットの前の状態の値Ｘn-1とを乗算し、２Ｎビットの出力ｐＸn-1を生成する第１の乗算ステップと、
上記第１の乗算ステップの出力の下位Ｎビットと、Ｎビットのｑ（奇数）とを加算する第１の加算ステップと、
上記第１の加算ステップの出力の内の最上位ビットＭＳＢを除くＮビットと、Ｘn-1と
を乗算する第２の乗算ステップと、
上記第２の乗算ステップの出力の下位Ｎビットと、Ｎビットのｒ（奇数）とを加算する第２の加算ステップとを備え、
上記第２の加算ステップの出力の内の最上位ビットＭＳＢを除くＮビットをｎ番目の出力Ｘnとして出力する乱数発生方法をコンピュータに実行させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、例えばストリーム暗号化の暗号化に使用される乱数を発生する乱数発生装置、乱数発生方法およびプログラムに関する。
【背景技術】
【０００２】
従来、ストリーム暗号化では、平文のビット系列と乱数のビット系列との排他的論理和をとることで暗号文のビット系列を生成している。通常、乱数は、擬似乱数発生装置によって生成される。擬似乱数発生装置の一例として、ＦＳＲ(Feedback Shift Register)を
用いたものが知られている。他の擬似乱数発生装置として、下記の特許文献１に記載のようなカオス関数を用いたものも知られている。
【０００３】
【特許文献１】特許第３０３０３４１号公報
【０００４】
ハードウェアでストリーム暗号を実現する場合には、回路規模や設計の簡単さからＦＳＲを用いるものが使用されている。線形ＦＳＲは、各１ビットを記憶できるｎ段のシフトレジスタと、ｎビットのシフトレジスタから取り出したビット情報を排他的論理和で１ビットに合成する結線回路とからなり、その１ビットがシフトレジスタにフィードバック入力される構成とされる。線形ＦＳＲは、２n の状態を持ちうるが、ｎビットの全てが０であると、出力が常に０となる。この状態を除く２n −１の状態を生成する周期２n −１の系列がＭ系列(Maximum length shift register sequence)と呼ばれる。
【発明の開示】
【発明が解決しようとする課題】
【０００５】
Ｍ系列は、線形要素のみからなる線形ＦＳＲから生成されるために、次の状態が予測されやすい問題があった。暗号化の鍵生成のための擬似乱数発生器としては、長周期性、一様性といった性質が必要であり、線形ＦＳＲにより生成されるＭ系列は、長周期性、一様性については満足できるが、線形複雑度が不足する点で、十分に満足できるものではなかった。ここで、一様性とは、任意の長さにおける全乱数系列の等頻度性（０と１が等頻度で出現すること）が保たれることである。
【０００６】
したがって、この発明の目的は、簡単な構成およびアルゴリズムによって、長周期性、一様性に優れ、線形複雑度の高い擬似乱数を生成することが可能な乱数発生装置、乱数発生方法およびプログラムを提供することにある。
【課題を解決するための手段】
【０００７】
上述した課題を解決するために、この発明は、式（１）で表される非線形写像によってＮビットの乱数を生成する乱数発生装置である。
Ｘn ＝ａmＸn-1m＋ａm-1Ｘn-1m-1＋ａm-2Ｘn-1m-2＋・・・・
＋ａ2Ｘn-12＋ａ1Ｘn-1＋ａ0 （mod ２N）                （１）
但し、ａ2＋ａ4＋ａ6＋・・・：偶数，ａ3＋ａ5＋ａ7＋・・・：偶数
ａ1，ａ0               ：奇数である。
【０００８】
また、この発明は、式（２）で表される非線形写像によってＮビットの乱数を生成する乱数発生装置である。
Ｘn＝ｐＸn-12＋ｑＸn-1＋ｒ  (mod２N)    （２）
但し、ｐ＝４ｋ＋２（ｋ＝０，１，２，・・・），ｑ，ｒ：奇数とする。
【０００９】
さらに、この発明は、Ｎビットのｐ（＝４ｋ＋２（ｋ＝０，１，２，・・・））と、Ｎビットの前の状態の値Ｘn-1とを乗算し、２Ｎビットの出力ｐＸn-1を生成する第１の乗算器と、  第１の乗算器の出力の下位Ｎビットと、Ｎビットのｑ（奇数）とを加算する第１の加算器と、  第１の加算器の出力の内の最上位ビットを除くＮビットと、Ｘn-1とを乗
算する第２の乗算器と、  第２の乗算器の出力の下位Ｎビットと、Ｎビットのｒ（奇数）とを加算する第２の加算器とを備え、  第２の加算器の出力の内の最上位ビットを除くＮビットをｎ番目の出力Ｘnとして出力する乱数発生装置である。
【００１０】
この発明は、式（１）で表される非線形写像によってＮビットの乱数を生成する乱数発生方法である。
Ｘn ＝ａmＸn-1m＋ａm-1Ｘn-1m-1＋ａm-2Ｘn-1m-2＋・・・・
＋ａ2Ｘn-12＋ａ1Ｘn-1＋ａ0 （mod ２N）                （１）
但し、ａ2＋ａ4＋ａ6＋・・・：偶数，ａ3＋ａ5＋ａ7＋・・・：偶数
ａ1，ａ0               ：奇数である。
【００１１】
この発明は、式（２）で表される非線形写像によってＮビットの乱数を生成する乱数発生方法である。
Ｘn＝ｐＸn-12＋ｑＸn-1＋ｒ  (mod２N)    （２）
但し、ｐ＝４ｋ＋２（ｋ＝０，１，２，・・・），ｑ，ｒ：奇数とする。
【００１２】
さらに、この発明は、Ｎビットのｐ（＝４ｋ＋２（ｋ＝０，１，２，・・・））と、Ｎビットの前の状態の値Ｘn-1とを乗算し、２Ｎビットの出力ｐＸn-1を生成する第１の乗算ステップと、  第１の乗算ステップの出力の下位Ｎビットと、Ｎビットのｑ（奇数）とを加算する第１の加算ステップと、  第１の加算ステップの出力の内の最上位ビットＭＳＢを除くＮビットと、Ｘn-1とを乗算する第２の乗算ステップと、  第２の乗算ステップの
出力の下位Ｎビットと、Ｎビットのｒ（奇数）とを加算する第２の加算ステップとを備え、  第２の加算ステップの出力の内の最上位ビットＭＳＢを除くＮビットをｎ番目の出力Ｘnとして出力する乱数発生方法である。
【００１３】
この発明は、コンピュータに対して、式（１）で表される非線形写像によってＮビットの乱数を生成する乱数発生方法を実行させるプログラムである。
Ｘn ＝ａmＸn-1m＋ａm-1Ｘn-1m-1＋ａm-2Ｘn-1m-2＋・・・・
＋ａ2Ｘn-12＋ａ1Ｘn-1＋ａ0 （mod ２N）                （１）
但し、ａ2＋ａ4＋ａ6＋・・・：偶数，ａ3＋ａ5＋ａ7＋・・・：偶数
ａ1，ａ0               ：奇数である。
【００１４】
この発明は、コンピュータに対して、式（２）で表される非線形写像によってＮビットの乱数を生成する乱数発生方法を実行させるプログラムである。
Ｘn＝ｐＸn-12＋ｑＸn-1＋ｒ  (mod２N)    （２）
但し、ｐ＝４ｋ＋２（ｋ＝０，１，２，・・・），ｑ，ｒ：奇数とする。
【００１５】
この発明は、Ｎビットのｐ（＝４ｋ＋２（ｋ＝０，１，２，・・・））と、Ｎビットの前の状態の値Ｘn-1とを乗算し、２Ｎビットの出力ｐＸn-1を生成する第１の乗算ステップと、  第１の乗算ステップの出力の下位Ｎビットと、Ｎビットのｑ（奇数）とを加算する第１の加算ステップと、  第１の加算ステップの出力の内の最上位ビットＭＳＢを除くＮビットと、Ｘn-1とを乗算する第２の乗算ステップと、  第２の乗算ステップの出力の下
位Ｎビットと、Ｎビットのｒ（奇数）とを加算する第２の加算ステップとを備え、  第２の加算ステップの出力の内の最上位ビットＭＳＢを除くＮビットをｎ番目の出力Ｘnとし
て出力する乱数発生方法をコンピュータに実行させるプログラムである。
【発明の効果】
【００１６】
この発明は、乗算器を用いた簡便な非線形写像を用いていることから線形複雑度が高く、かつ完全な一様性・長周期性を持つ擬似乱数を発生することができる。
【００１７】
この発明は、ハードウェア上の計算に適した２のべき乗体の整数演算のみで、擬似乱数を発生させることができるので、ソフトウェアのみならず、ハードウェアによって簡単に実現することができ、高速に擬似乱数を発生させることができる。
【発明を実施するための最良の形態】
【００１８】
以下、この発明について説明する。この発明では、下記の式（１）で表されるｍ次の非線形写像によって乱数を発生する。
【００１９】
Ｘn ＝ａmＸn-1m＋ａm-1Ｘn-1m-1＋ａm-2Ｘn-1m-2＋・・・・
＋ａ2Ｘn-12＋ａ1Ｘn-1＋ａ0 （mod ２N）                （１）
但し、ａ2＋ａ4＋ａ6＋・・・：偶数，ａ3＋ａ5＋ａ7＋・・・：偶数
ａ1，ａ0               ：奇数である。
【００２０】
（ｍ＝２）次の場合では、
Ｘn ＝ｐＸn-12＋ｑＸn-1＋ｒ （mod ２N）                （２）
但し、ｐ＝４ｋ＋２（ｋ＝０，１，２，・・・）
ｑ，ｒ     ：奇数である。
【００２１】
このとき式（１）および式（２）で表される写像は、１対１の写像となる。これを式（２）の場合について証明する。背理法を使用する。Ｘn-1を単にＸと表記する。
【００２２】
Ｘ≠Ｙで、Ｘ（ｐＸ＋ｑ）＋ｒ＝Ｙ（ｐＹ＋ｑ）＋ｒ （mod ２N）と仮定する。その時、
（Ｘ−Ｙ）（ｐＸ＋ｐＹ＋ｑ）＝０ （mod ２N）
しかし、Ｘ−Ｙ≠０で、ｐＸ＋ｐＹ＋ｑが奇数なので、左辺はmod ２Nで零にはならな
い。したがって、仮定は矛盾している。よって、ｆ（Ｘ）は、１対１の写像となる。なお、１対１写像になるという証明に関する参考文献として、Ronald L.Rivest,"Permutation Polynomials Modulo 2w," Finite Fields and their Applications,vol.7,pp.287-292,2001がある。
【００２３】
式（２）によって発生した乱数は、ｐ，ｑ，ｒの値によって、以下の周期性を持つ。
【００２４】
ｑ＝４ｌ＋３  （ｌ＝０，１，２，・・・）、すなわち、ｑ＝３，７，１１，・・・の場合：
周期２N の周期軌道を持つ。
【００２５】
ｑ＝４ｌ＋１  （ｌ＝０，１，２，・・・）、すなわち、ｑ＝１，５，９，・・・の場合：
ｒ＝１，５，９，・・・の場合
周期２N-1 の周期軌道が２組存在している。
【００２６】
ｒ＝３，７，１１，・・・の場合
周期２N-2 の周期軌道が２組、周期２N-3 の周期軌道が２組，周期２N-4 の周期軌道が２組，・・・，周期２の周期軌道が４組，共存している。
【００２７】
Ｎ＝４の例を使用して、周期性についてより具体的に説明する。（ｐ＝２，ｑ＝３，ｒ＝１）とされ、Ｘn ＝２Ｘn-12＋３Ｘn-1＋１ （mod ２4）の例では、図１Ａに示すよう
に、２4の周期を持つ軌道が存在する。例えばＸn-1＝５であれば、Ｘn＝５０＋１５＋１
（mod ２4）＝２となる。
【００２８】
（ｐ＝２，ｑ＝１，ｒ＝１）とされ、Ｘn ＝２Ｘn-12＋Ｘn-1＋１ （mod ２4）の例で
は、図１Ｂに示すように、２3の周期を持つ軌道が２組存在している。
【００２９】
（ｐ＝２，ｑ＝３，ｒ＝３）とされ、Ｘn ＝２Ｘn-12＋３Ｘn-1＋３ （mod ２4）の例
では、図１Ｃに示すように、２2の周期を持つ軌道が２組、周期２の周期軌道が４組，共
存している。
【００３０】
このように、この発明では、２N の長周期を持ち、また、整数演算であるため、簡単な構成で実現でき、さらに、複数の周期が存在しうるので、次の状態が予測しにくく、暗号化を解読しにくくする乱数を発生できる。
【００３１】
上述した式（１）に示す高次の非線形写像または式（２）に示す２次の非線形写像は、コンピュータプログラムによって実現することができる。
【００３２】
図２は、式（２）に示す２次の非線形写像による乱数発生装置を実現するハードウェアの構成例を示す。なお、Ｎは、ディジタル値で表された整数（Ｘn-1，Ｘn ｐ，ｑ，ｒ）
のビット数である。また、図２の構成では、タイミングの同期をとるためのレジスタ等の構成は、簡単のために省略されている。さらに、式（２）を下記の式（３）のように変形したものと対応した構成とされている。
【００３３】
Ｘn ＝（ｐＸn-1＋ｑ）・Ｘn-1＋ｒ （mod ２N）                （３）
【００３４】
参照符号１は、乗算器を示す。乗算器１に対して、各Ｎビットのｐ（＝４ｋ＋２（ｋ＝０，１，２，・・・））と、乱数の前の状態の値Ｘn-1とが入力され、２Ｎビットの乗算
出力ｐＸn-1が生成され、レジスタ２に格納される。
【００３５】
レジスタ２の下位Ｎビットの出力が加算器３に一方の入力として供給される。下位Ｎビットを選択するのは、（mod ２N）の演算を行うからである。以下の演算処理においても
、同様の理由で下位側のＮビットが選択される。加算器３の他方の入力として、Ｎビットのｑ（奇数）が入力される。加算器３の出力として、Ｎ＋１ビットの（ｐＸn-1＋ｑ）が
得られる。加算器３の出力がレジスタ４に格納される。
【００３６】
レジスタ４の出力の内の最上位ビットＭＳＢを除くＮビットが乗算器５に供給される。ＬＳＢが最下位ビットを示す。乗算器５の他の入力としてＸn-1が入力される。乗算器５
の出力は、（ｐＸn-1＋ｑ）・Ｘn-1である。乗算器５の２Ｎビットの出力がレジスタ６に格納される。
【００３７】
レジスタ６の下位Ｎビットの出力が加算器７に一方の入力として供給される。加算器７の他方の入力として、Ｎビットのｒ（奇数）が入力される。加算器７の出力として、Ｎ＋１ビットの（ｐＸn-1＋ｑ）・Ｘn-1＋ｒが得られる。加算器７のＮ＋１ビットの出力がレジスタ８に格納される。レジスタ８の最上位ビットＭＳＢを除くＮビットの出力が乱数のｎ番目の出力Ｘnとして出力される。
【００３８】
なお、図２では、省略されているが、ｐ，ｑ，ｒの値を設定する回路構成が設けられている。
【００３９】
この発明は、上述したこの発明の一実施形態等に限定されるものでは無く、この発明の要旨を逸脱しない範囲内で様々な変形や応用が可能である。
【産業上の利用可能性】
【００４０】
この発明による乱数発生装置、乱数発生方法およびプログラムは、スペクトル拡散通信の拡散符号の生成、モンテカルロシミュレーションの擬似乱数の発生等に対しても適用できる。
【図面の簡単な説明】
【００４１】
【図１】この発明による乱数発生装置により発生された乱数の周期を説明するための略線図である。
【図２】この発明による乱数発生装置の一実施形態のブロック図である。
【符号の説明】
【００４２】
１，５  乗算器
３，７  加算器
【図１】
2005107910.tif 000003
【図２】
2005107910.tif 000004