(57)【要約】【課題】周期の下限を保証しつつ複雑な疑似乱数を高速に生成する。【解決手段】カオス結合系、すなわちロジスティック写像及びテント写像の結合系を用いている。本発明はvn, εn, 及びxnの各初期値v0, ε0, 及びx0を設定し、xn+1=ε・4xn(1-xn)+(1-ε)・min{2xn,2(1- xn)}の値nを増加させることによって、疑似乱数列xnを生成し、εnとvnとを用いて、εnの値を更新することによって課題を解決する。【選択図】図３
2017142697.tif 000002
【特許請求の範囲】
【請求項１】
以下の数式による疑似乱数列{zn|zn=f4(xn)}を用いた疑似乱数生成器であって、
vn+1=f1(vn)、
εn+1=f2(vi(n),εn)、
xn+1=f3(εn,xn)、
それぞれの写像は、
f1：Ｚｐｄ→Ｚｐｄ、
f2：Ｚｐ×[[0,1]]→[[0,1]]、
f3：[[0,1]]×[[0,1]]→[[0,1]],f3(ε,x)=ε・4x(1-x)+(1-ε)・min{2x,2(1-x)}、及び
f4：[[0,1]]→
【数１】
2017142697.tif 000006
によって定義され、
上記数式において、
[[0,1]]は、システムの表現できる区間[0,1]の実数であって、[x]は、xを超えない最大の整数であり、
Ｚｐは、位数が素数ｐの剰余体であり、
φＡ(x)は、行列Ａの固有多項式であり、
Ｍｄ(Ｚｐ)は、サイズがdxdのＺｐ上の正方行列であり、
f1の表現行列はＡ∈Ｍｄ(Ｚｐ)であって、φＡ(x)を原始多項式とし、
i(n)=[n/C]であって、C∈Ｚはεの更新頻度を決めるパラメータである、疑似乱数生成器。
【請求項２】
表現行列Ａがコンパニオン行列である、請求項1に記載の疑似乱数生成器。
【請求項３】
前記f4が特に、f4(x)=[252・x]mod 232であり、[252・x]が252・xを超えない最大の整数である、請求項1又は2に記載の疑似乱数生成器。
【請求項４】
前記f2が特に、値nがf1の周期であるpd-1の整数倍の値に等しい場合、εnとvi(n)とを用いてεn+1の値を更新する、請求項1〜3のいずれか一項に記載の疑似乱数生成器。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、疑似乱数生成器及びプログラムに関する。
【背景技術】
【０００２】
カオス理論を用いた疑似乱数生成方法として、ロジスティック写像又はテント写像の関数を用いた疑似乱数生成方法が使用されている。これらの疑似乱数生成方法は、高い一様性を有する疑似乱数を生成することができるが、例えばメルセンヌツイスターのような疑似乱数生成方法と比較すると、それらによって生成される疑似乱数には劣る。また、カオス理論を用いた疑似乱数生成は、周期の下限を保証することが困難である。
【発明の概要】
【発明が解決しようとする課題】
【０００３】
現在、カオス理論を用いた疑似乱数生成手法は、生成された疑似乱数の周期性を保証できない等の理由により、広くは実用されていない。本願は、カオス写像の結合した関数を用いることにより、より高い一様性を有する疑似乱数を生成するとともに、上記周期性の問題を解消する。すなわち、本願は周期の下限を保証しつつ複雑な疑似乱数を高速に生成することを課題とする。
【課題を解決するための手段】
【０００４】
上記の課題を解決するために、本発明は、複雑性、すなわち疑似乱数の一様性が十分でないが周期を見積もることができる線形写像の特徴と、周期を見積もることができないが十分な複雑性を有するカオス写像の結合系の特徴とを組み合わせている。以下に、本発明の態様について説明する。
【０００５】
一態様において提供される疑似乱数生成器は、以下の数式による疑似乱数列{zn|zn=f4(xn)}を用いた疑似乱数生成器であって、
vn+1=f1(vn)、
εn+1=f2(vi(n),εn)、
xn+1=f3(εn,xn)、
それぞれの写像は、
f1：Ｚｐｄ→Ｚｐｄ、
f2：Ｚｐ×[[0,1]]→[[0,1]]、
f3：[[0,1]]×[[0,1]]→[[0,1]],f3(ε,x)=ε・4x(1-x)+(1-ε)・min{2x,2(1-x)}、及び
f4：[[0,1]]→
【数１】
2017142697.tif 000003
によって定義され、
上記数式において、
[[0,1]]は、システムの表現できる区間[0,1]の実数であって、[x]は、xを超えない最大の整数であり、
Ｚｐは、位数が素数ｐの剰余体であり、
φＡ(x)は、行列Ａの固有多項式であり、
Ｍｄ(Ｚｐ)は、サイズがdxdのＺｐ上の正方行列であり、
f1の表現行列はＡ∈Ｍｄ(Ｚｐ)であって、φＡ(x)を原始多項式とし、
i(n)=[n/C]であって、C∈Ｚはεの更新頻度を決めるパラメータである。
【０００６】
上記態様において、表現行列Ａがコンパニオン行列であってもよい。
【０００７】
上記態様において、前記f4が特に、f4(x)=[252・x]mod 232であり、[252・x]が252・xを超えない最大の整数であってもよい。
【０００８】
上記態様において、前記f2が特に、値nがf1の周期であるpd-1の整数倍の値に等しい場合、εnとvi(n)とを用いてεn+1の値を更新してもよい。
【図面の簡単な説明】
【０００９】
本発明の実施形態及び従来技術における技術的解決策をより明瞭に説明するために、以下に、実施形態を説明するために必要な添付図面を簡単に説明する。以下の説明における添付図面は本発明のいくつかの態様を示しているに過ぎず、かつ、当業者が創造的努力なしにこれらの添付図面から他の図面を導き出すことができることは明らかである。
【００１０】
【図１】ロジスティック写像及びテント写像を結合した関数による分岐図である。
【図２】実施形態における疑似乱数生成器のブロック図である。
【図３】実施形態における疑似乱数生成方法のフローチャートである。
【図４】実施形態における暗号化装置のブロック図である。
【図５】実施形態における暗号化装置を含むシステムの概略図である。
【発明を実施するための形態】
【００１１】
本発明の実施形態における添付図面を参照して、以下に本発明の実施形態の技術的解決策を明瞭かつ十分に説明する。説明される実施形態は、本発明の実施形態の全てというよりはむしろ単なる一部に過ぎないことは明らかである。当業者によって創造的努力なしに本発明の実施形態に基づいて取得される全ての他の実施形態は、本発明の保護範囲内であるとする。
【００１２】
図1は、ロジスティック写像(Fa(x)=4ax(1-x), 0≦a≦1)のa=1の場合の関数とテント写像(Gμ(x)=2min{μx, μ(1-x)}, 0≦μ≦1)のμ=1の場合の関数とを結合した関数(Hε(x)=ε4x(1-x)+(1-ε)2min{x,(1-x)}, 0≦ε≦1)(以下,LT写像と称す)の分岐図を示している。ロジスティック写像及びテント写像の分岐図の詳細については、非特許文献１：大矢雅則、佐藤圭子、井上啓、「情報数理入門」サイエンス社、等を参照されたい。
【００１３】
以下、本発明の実施形態について説明する。
【００１４】
以下は、本発明の実施形態の説明において使用される記号である。
●Ｚｐ：位数が素数ｐの剰余体
●Ｍｄ(Ｚｐ)：サイズがdxdのＺｐ上の正方行列
●[[0,1]]：システムの表現できる区間[0,1]の実数
●[x]：xを超えない最大の整数
●φＡ(x)：行列Ａの固有多項式
【００１５】
以下は、本発明の実施形態において使用される写像とパラメータである。
●f1：Ｚｐｄ→Ｚｐｄ線形写像
●f2：Ｚｐ×[[0,1]]→[[0,1]]LT写像のパラメータを決めるための写像
●f3：[[0,1]]×[[0,1]]→[[0,1]],f3(ε,x)=ε・4x(1-x)+(1-ε)・min{2x,2(1-x)}LT写像
●f4：[[0,1]]→
【数２】
2017142697.tif 000004
●Ｃ∈Ｚ：εの更新頻度を決めるパラメータ
【００１６】
本発明の実施形態における疑似乱数生成器は、(d,n,C,f1,f2,f3,f4)で構成され、時刻iに依存する状態
(vi,εi,xi)∈Ｆｐｄ×[[0,1]]×[[0,1]]
を有する。初期状態(v0,ε0,x0)はシードとして与える。
【００１７】
本発明の実施形態における疑似乱数生成アルゴリズムについて説明する。
i(n)=[n/C]とする。疑似乱数{zn|zn=f4(xn)}は次の関係に従って生成される。
●vn+1=f1(vn)
●εn+1=f2(vi(n),εn)
●xn+1=f3(εn,xn)
【００１８】
一実施形態において、写像f1の表現行列をＡ∈Ｍｄ(Ｚｐ)としたとき、φＡ(x)が原始多項式となるf1を選択することで、f1を生成するベクトルの周期はpd-1となる。表現行列Ａがコンパニオン行列の形をとるものを選択することで、高速な計算が実現できる。また、この実施形態において、f2,f4は以下のように設定される。
●f2(v,ε)=2-33・(<v>+ε)
●f4(x)=[232・CUT20(x)]
【００１９】
図2は、実施形態における疑似乱数生成方法のフローチャートである。該疑似乱数生成方法は、以下の数式による疑似乱数列{zn|zn=f4(xn)}を用いた疑似乱数生成方法である。
vn+1=f1(vn)、
εn+1=f2(vi(n),εn)、
xn+1=f3(εn,xn)、
それぞれの写像は、
f1：Ｚｐｄ→Ｚｐｄ、
f2：Ｚｐ×[[0,1]]→[[0,1]]、
f3：[[0,1]]×[[0,1]]→[[0,1]],f3(ε,x)=ε・4x(1-x)+(1-ε)・min{2x,2(1-x)}、及び
f4：[[0,1]]→
【数３】
2017142697.tif 000005
によって定義され、
上記数式において、
[[0,1]]は、システムの表現できる区間[0,1]の実数であって、[x]は、xを超えない最大の整数であり、
Ｚｐは、位数が素数ｐの剰余体であり、
φＡ(x)は、行列Ａの固有多項式であり、
Ｍｄ(Ｚｐ)は、サイズがdxdのＺｐ上の正方行列であり、
f1の表現行列はＡ∈Ｍｄ(Ｚｐ)であって、φＡ(x)を原始多項式とし、
i(n)=[n/C]であって、C∈Ｚはεの更新頻度を決めるパラメータである。
具体的には、上記の疑似乱数生成方法は、概略的に以下のステップによって説明することもできる。
【００２０】
ステップ210: vn, εn, 及びxnの各初期値v0, ε0, 及びx0を設定する。
【００２１】
ステップ220: xn+1=ε・4xn(1-xn)+(1-ε)・min{2xn,2(1- xn)}の値nを増加させることによって、疑似乱数列xnを生成する。
【００２２】
ステップ230: εnとvnとを用いて、εnの値を更新する。
【００２３】
なお、ステップ330においてεnの値を更新した後にステップ320に戻って、継続的に疑似乱数列を生成してもよい。
【００２４】
また、一実施形態において、表現行列Ａはコンパニオン行列であってもよく、これによって、高速な計算が実現できる。
【００２５】
また、一実施形態において、f4が特に、f4(x)=[252・x]mod 232であり、[252・x]が252・xを超えない最大の整数であり、この場合、生成される疑似乱数列は、2進表現で表された[252・xn]の上位20ビットを除いたビット列で表されるので、より高い一様性を有する疑似乱数列を生成することができる。
【００２６】
また、一実施形態において、f2が特に、値nがf1の周期であるpd-1の整数倍の値に等しい場合、εnとvi(n)とを用いてεn+1の値を更新してもよい。これによって、周期の下限を保証しつつ、さらに複雑な疑似乱数を生成することができる。
【００２７】
また、一実施形態において、上記疑似乱数生成方法(疑似乱数生成方法1と称す)に上記初期値v0, ε0, 及びx0とは異なる初期値v0’, ε0’, 及び x0’を有する別の疑似乱数生成方法(疑似乱数生成方法2と称す)を同時に実行し、疑似乱数生成方法1によって生成された数列と、疑似乱数生成方法2によって生成された数列との排他的論理和を計算することによって、疑似乱数を生成してもよい。これによって、さらに高い一様性を有する疑似乱数列を生成することができる。
【００２８】
図3は、実施形態における疑似乱数生成器のブロック図である。
【００２９】
図3に示されるように、疑似乱数生成器300は、設定モジュール310と、生成モジュール320と、更新モジュール330とを備える。設定モジュール310は図2におけるステップ210を実装し、生成モジュール320は図2におけるステップ220を実装し、更新モジュール330は図2におけるステップ230を実装するように構成されてもよい。
【００３０】
図3に示されるように、設定モジュールは、生成モジュール及び更新モジュールにそれぞれ計算に必要となる初期値v0, ε0, 及びx0を送信している。また、生成モジュールは、εnの値を更新するときに、更新モジュールにvnの値を送信し、次いで更新モジュールは、εnの値を更新し、次いで更新モジュールは更新されたεの値を生成モジュールに送信する。
【００３１】
図4は、実施形態における暗号化装置400のブロック図である。
【００３２】
図4に示されるように、暗号化装置400は、データ入出力ユニット410と、疑似乱数生成器300と、暗号化ユニット420とを備える。
【００３３】
前記データ入出力ユニット410は、例えばユーザ端末のようなデータを暗号化装置400に対して出力するデバイス（ユーザ端末と称す）からデータを受け取る。前記データ入出力ユニットは、例えば初期値v0, ε0, 及びx0を有するデータを疑似乱数生成器300に入力し、かつ例えば平文等の暗号化したいデータを暗号化ユニット420に入力する。さらに、疑似乱数生成器300は、初期値v0, ε0, 及びx0により生成した疑似乱数列を暗号化ユニット420に入力する。次いで、暗号化ユニット420は前記暗号化したいデータを暗号化し、生成されたデータ（暗号文と称す）をデータ入出力ユニット410に入力し、前記データ入出力ユニット410は、データをユーザ端末に送信する。この実施形態におけるデータの形式については、ここでは限定しない。
【００３４】
この実施形態において、暗号化ユニットは、暗号文の復号化のために使用されてもよく、すなわち、暗号化装置は復号化装置と称されてもよい。
【００３５】
図5は、実施形態における暗号化装置を含むシステムの概略図である。
【００３６】
図5に示されるように、システム500は、ネットワーク網510と、暗号化装置520と、ユーザ端末530及び540と、復号化装置550とを含む。
【００３７】
なお、前記復号化装置550は、図4において説明したように、暗号化装置520と同一の構成要素によって構成されてもよい。
【００３８】
ユーザ端末530は、暗号化したいデータを暗号化装置において暗号化し、生成された暗号文をネットワーク網510を介してユーザ端末540に送信する。このとき、ユーザ端末540は、暗号文を受信してから復号化装置550を使用して暗号文を復号化してもよく、又は暗号文を受信する前に復号化装置550を介して復号化されたデータを受信してもよい。
【００３９】
なお、前述の実施形態に説明されたデータ処理を実装するための様々な装置は、別のシステムの一部として存在してもよい。
【００４０】
当業者は、本願明細書に記載された実施形態において説明された実施例を組み合わせて、モジュール、ユニット及びステップが、電子ハードウェア、コンピュータソフトウェア又はそれらの組み合わせによって実装可能であると認識することができる。ハードウェア及びソフトウェアの互換性を明確に説明するために、前述では、機能に基づく各実施例の構成要素及びステップが概略的に説明されている。前記機能がハードウェア又はソフトウェアによって実行されるか否かは、技術的解決策の特定の用途及び設計制約条件に依存する。当業者は、各特定用途のために説明された機能を実装するための異なる方法を使用してもよいが、その実装は、本発明の実施形態の範囲外であると考えられるべきではない。
【００４１】
本願明細書に記載された複数の実施形態を組み合わせて、方法又はステップが、ハードウェア、プロセッサによって実行されるソフトウェアモジュール、又はその組み合わせによって実装されてもよい。
【００４２】
記載された実施形態の前述の説明は、当業者が本発明の実施形態を実装又は使用することを可能にする。前記実施形態に様々な修正を行うことは、当業者には容易であり、かつ、本願明細書における一般的な原理は、本発明の実施形態の思想又は範囲から逸脱しない他の実施形態において実施されることが可能である。従って、本発明の実施形態は、本願明細書に説明された実施形態に限定されず、本願明細書に記載された原理に従う最大範囲にまで及ぶ。
【００４３】
前述の説明は、本発明の単なる例示的な実施形態であり、本発明の実施形態を限定することを意図していない。本発明の実施形態の思想および原理から逸脱しないで行われる任意の修正、均等置換および改良は、本発明の実施形態の保護範囲内であるものとする。
【符号の説明】
【００４４】
３００  疑似乱数生成器
３１０  設定モジュール
３２０  生成モジュール
３３０  更新モジュール
４００  暗号化装置
４１０  データ入出力ユニット
４２０  暗号化ユニット
５００  システム
５１０  ネットワーク網
５２０  暗号化装置
５３０  ユーザ端末
５４０  ユーザ端末
５５０  復号化装置
【図１】
2017142697.tif 000007
【図２】
2017142697.tif 000008
【図３】
2017142697.tif 000009
【図４】
2017142697.tif 000010
【図５】
2017142697.tif 000011