(57)【特許請求の範囲】
【請求項１】
wビットの乱数の列を生成する乱数列生成装置であって、整数n，m (1≦n≦m-1)に対して、
wビットの整数の列s1,s2,…,sn,…,smを種として受け付ける種受付部、
当該受け付けられた整数の列s1,s2,…,sn,…,smを、整数列x1,x2,…,xn,…,xmとして与える初期化部、
当該与えられた整数列x1,x2,…,xn,…,xmのそれぞれに対して所定の変換を施してwビットの整数の列y1,y2,…,yn,…,ymを得る変換部、
当該整数の列yn+1,…,ymから回転ビット数を得て、当該整数の列y1,y2,…,yn,…,ymをwmビットのビット列と見て、これ、もしくは、これの一部に対して当該得られた回転ビット数の回転演算を行って、得られたwmビットのビット列からwビットの整数の列z1,z2,…,zn,…,zmを得る回転部、
当該整数の列z1,z2,…,zn,…,zmを整数列x1,x2,…,xn,…,xmとして前記変換部に与える更新部、
前記変換部における変換ならびに前記回転部における回転が、所定の回数繰り返された場合、最後に得られたz1,z2,…,znを、乱数列r1,r2,…,rnとして出力する出力部、
を備えることを特徴とする乱数列生成装置。
【請求項２】
請求項１に記載の乱数列生成装置であって、
前記変換部は、写像g(・,・)を用いて、整数i (1≦i≦m-1)についての漸化式
y1  = g(xm,x1)；
yi+1 = g(xi,xi+1)
により変換を行う
ことを特徴とする乱数列生成装置。
【請求項３】
請求項１に記載の乱数列生成装置であって、
前記変換部は、所定の整数cと、写像g(・,・)と、を用いて、整数i (1≦i≦m-1)についての漸化式
y1  = g(c,x1)；
yi+1 = g(yi,xi+1)
により変換を行う
ことを特徴とする乱数列生成装置。
【請求項４】
請求項１に記載の乱数列生成装置であって、
前記変換部は、写像g(・,・)を用いて、整数i (1≦i≦m-1)についての漸化式
y1  = g(c,x1)；
yi+1 = g(xi,xi+1)
により変換を行う
ことを特徴とする乱数列生成装置。
【請求項５】
請求項２から４のいずれか１項に記載の乱数列生成装置であって、
当該写像g(・,・)は、所定の写像h(・)と所定の整数q (0≦q≦2w-1)により
g(a,b) = 2b2 + h(a)b + q (mod 2w)
と定義される
ことを特徴とする乱数列生成装置。
【請求項６】
請求項５に記載の乱数列生成装置であって、
当該写像h(・)は、
h(a) = a
と定義される
ことを特徴とする乱数列生成装置。
【請求項７】
請求項５に記載の乱数列生成装置であって、
当該写像h(・)は、与えられた値の数値表現の所定のビットをクリアする演算により定義される
ことを特徴とする乱数列生成装置。
【請求項８】
請求項５に記載の乱数列生成装置であって、
当該写像h(・)は、与えられた値の数値表現の所定のビットを反転する演算により定義される
ことを特徴とする乱数列生成装置。
【請求項９】
請求項５に記載の乱数列生成装置であって、
当該写像h(・)は、与えられた値の数値表現の最下位２ビットを０１に置換する演算により定義される
ことを特徴とする乱数列生成装置。
【請求項１０】
請求項１から９のいずれか１項に記載の乱数列生成装置であって、
前記回転部は、当該整数の列yn+1,…,ymをw(m-n+1)ビットのビット列と見て、これから所定の位置のビットを１個以上抽出して並べたビット列を整数と見たときの整数値を、回転ビット数として得る
ことを特徴とする乱数列生成装置。
【請求項１１】
請求項１０に記載の乱数列生成装置であって、
前記回転部は、当該整数の列yn+1,…,ymをw(m-n+1)ビットのビット列と見て、これから所定の位置のビットの値により、回転する方向を決める
ことを特徴とする乱数列生成装置。
【請求項１２】
請求項１から１１のいずれか１項に記載の乱数生成装置であって、
前記回転部は、当該整数の列yn+1,…,ymから回転ビット数を得て、当該整数の列y1,y2,…,ynをwnビットのビット列と見て、これに対して当該得られた回転ビット数の回転演算を行って、得られたwnビットのビット列からwビットの整数の列z1,z2,…,znを得て、整数の列yn+1,…,ymをw(m-n)ビットのビット列と見て、これに対して当該得られた回転ビット数の回転演算を行って、得られたw(m-n)ビットのビット列からwビットの整数の列zn+1,…,zmを得る
ことを特徴とする乱数列生成装置。
【請求項１３】
乱数生成部と、メッセージ受付部と、暗号化復号化部と、を備える暗号化復号化装置であって、
前記乱数生成部は、請求項１から１２のいずれか１項に記載の乱数生成装置により、乱数列r1,r2,…,rnを生成し、
前記メッセージ受付部は、wビットの整数の整数列p1,p2,…,をメッセージとして受け付け、
前記暗号化復号化部は、wビットの整数の列p1 xor r1,p2 xor r2,…,pi xor r((i+n-1) mod n) + 1,…を暗号化もしくは復号化の結果として出力する
ことを特徴とする暗号化復号化装置。
【請求項１４】
種受付部と、初期化部と、変換部と、回転部と、更新部と、出力部と、を備える乱数列生成装置にて実行され、wビットの乱数の列を生成する乱数列生成方法であって、整数n，m (1≦n≦m-1)に対して、
前記種受付部が、wビットの整数の列s1,s2,…,sn,…,smを種として受け付ける種受付工程、
前記初期化部が、当該受け付けられた整数の列s1,s2,…,sn,…,smを、整数列x1,x2,…,xn,…,xmとして与える初期化工程、
前記変換部が、当該与えられた整数列x1,x2,…,xn,…,xmのそれぞれに対して所定の変換を施してwビットの整数の列y1,y2,…,yn,…,ymを得る変換工程、
前記回転部が、当該整数の列yn+1,…,ymから回転ビット数を得て、当該整数の列y1,y2,…,yn,…,ymをwmビットのビット列と見て、これ、もしくは、これの一部に対して当該得られた回転ビット数の回転演算を行って、得られたwmビットのビット列からwビットの整数の列z1,z2,…,zn,…,zmを得る回転工程、
前記更新部が、当該整数の列z1,z2,…,zn,…,zmを整数列x1,x2,…,xn,…,xmとして前記変換工程に与える更新工程、
前記出力部が、前記変換工程における変換ならびに前記回転工程における回転が、所定の回数繰り返された場合、最後に得られたz1,z2,…,znを、乱数列r1,r2,…,rnとして出力する出力工程
を備えることを特徴とする乱数列生成方法。
【請求項１５】
請求項１４に記載の乱数列生成方法であって、
前記変換工程では、写像g(・,・)を用いて、整数i (1≦i≦m-1)についての漸化式
y1  = g(xm,x1)；
yi+1 = g(xi,xi+1)
により変換を行う
ことを特徴とする乱数列生成方法。
【請求項１６】
請求項１４に記載の乱数列生成方法であって、
前記変換工程では、所定の整数cと、写像g(・,・)と、を用いて、整数i (1≦i≦m-1)についての漸化式
y1  = g(c,x1)；
yi+1 = g(yi,xi+1)
により変換を行う
ことを特徴とする乱数列生成方法。
【請求項１７】
請求項１４に記載の乱数列生成方法であって、
前記変換工程では、写像g(・,・)を用いて、整数i (1≦i≦m-1)についての漸化式
y1  = g(c,x1)；
yi+1 = g(xi,xi+1)
により変換を行う
ことを特徴とする乱数列生成方法。
【請求項１８】
請求項１５から１７のいずれか１項に記載の乱数列生成方法であって、
当該写像g(・,・)は、所定の写像h(・)と所定の整数q (0≦q≦2w-1)により
g(a,b) = 2b2 + h(a)b + q (mod 2w)
と定義される
ことを特徴とする乱数列生成方法。
【請求項１９】
請求項１８に記載の乱数列生成方法であって、
当該写像h(・)は、
h(a) = a
と定義される
ことを特徴とする乱数列生成方法。
【請求項２０】
請求項１８に記載の乱数列生成方法であって、
当該写像h(・)は、与えられた値の数値表現の所定のビットをクリアする演算により定義される
ことを特徴とする乱数列生成方法。
【請求項２１】
請求項１８に記載の乱数列生成方法であって、
当該写像h(・)は、与えられた値の数値表現の所定のビットを反転する演算により定義される
ことを特徴とする乱数列生成方法。
【請求項２２】
請求項１８に記載の乱数列生成方法であって、
当該写像h(・)は、与えられた値の数値表現の最下位２ビットを０１に置換する演算により定義される
ことを特徴とする乱数列生成方法。
【請求項２３】
請求項１４から２２のいずれか１項に記載の乱数列生成方法であって、
前記回転工程では、当該整数の列yn+1,…,ymをw(m-n+1)ビットのビット列と見て、これから所定の位置のビットを１個以上抽出して並べたビット列を整数と見たときの整数値を、回転ビット数として得る
ことを特徴とする乱数列生成方法。
【請求項２４】
請求項２３に記載の乱数列生成方法であって、
前記回転工程では、当該整数の列yn+1,…,ymをw(m-n+1)ビットのビット列と見て、これから所定の位置のビットの値により、回転する方向を決める
ことを特徴とする乱数列生成方法。
【請求項２５】
請求項１４から２４のいずれか１項に記載の乱数生成方法であって、
前記回転工程では、当該整数の列yn+1,…,ymから回転ビット数を得て、当該整数の列y1,y2,…,ynをwnビットのビット列と見て、これに対して当該得られた回転ビット数の回転演算を行って、得られたwnビットのビット列からwビットの整数の列z1,z2,…,znを得て、整数の列yn+1,…,ymをw(m-n)ビットのビット列と見て、これに対して当該得られた回転ビット数の回転演算を行って、得られたw(m-n)ビットのビット列からwビットの整数の列zn+1,…,zmを得る
ことを特徴とする乱数列生成方法。
【請求項２６】
乱数生成部、メッセージ受付部、暗号化復号化部を有する暗号化復号化装置にて実行される暗号化復号化方法であって、
前記乱数生成部が、請求項１３から２３のいずれか１項に記載の乱数生成方法により、乱数列r1,r2,…,rnを生成する乱数生成工程、
前記メッセージ受付部が、wビットの整数の整数列p1,p2,…,をメッセージとして受け付けるメッセージ受付工程、
前記暗号化復号化部が、wビットの整数の列p1 xor r1,p2 xor r2,…,pi xor r((i+n-1) mod n) + 1,…を暗号化もしくは復号化の結果として出力する暗号化復号化工程
を備えることを特徴とする暗号化復号化方法。
【請求項２７】
コンピュータを、請求項１から１２のいずれか１項に記載の乱数列生成装置として機能させることを特徴とするプログラム。
【請求項２８】
コンピュータを、請求項１３に記載の暗号化復号化装置として機能させることを特徴とするプログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、乱数列生成装置、暗号化復号化装置、乱数列生成方法、暗号化復号化方法、ならびに、プログラムに関する。
【０００２】
【従来の技術】
従来から、種々の乱数列生成のための技術が提案されている。これらの技術によって得られた乱数は、たとえば、モンテカルロ法による各種の物理現象、化学現象などの模擬実験や、秘密通信のブロック暗号システムにおいて用いられる。
【０００３】
【発明が解決しようとする課題】
さて、このような乱数列の生成技術においては、得られた乱数列に含まれる数値の分布ができるだけ一様であることや、当該数値のコンピュータにおける数値表現の所定のビットのみを見た場合に、当該ビットの「０」と「１」の出現頻度にできるだけ偏りがないことや、乱数列の周期ができるだけ長いことなど、種々の性質を満たすことが望ましい。
【０００４】
本発明は、生成される乱数列が乱数列として好ましい性質を有するような乱数列生成装置、乱数列生成方法、ならびに、これらを用いた暗号化復号化装置、暗号化復号化方法、ならびに、これらをコンピュータによって実現するためのプログラムを提供することを目的とする。
【０００５】
【課題を解決するための手段】
以上の目的を達成するため、本発明の原理にしたがって、下記の発明を開示する。
【０００６】
本発明の第１の観点に係る乱数列生成装置は、wビットの乱数の列を生成し、種受付部と、初期化部と、変換部と、回転部と、更新部と、出力部と、を備え、整数n，m (1≦n≦m-1)に対して、以下のように構成する。
【０００７】
すなわち、種受付部は、wビットの整数の列s1,s2,…,sn,…,smを種として受け付ける。
【０００８】
一方、初期化部は、当該受け付けられた整数の列s1,s2,…,sn,…,smを、整数列x1,x2,…,xn,…,xmとして変換部に与える。
【０００９】
さらに、変換部は、当該与えられた整数列x1,x2,…,xn,…,xmのそれぞれに対して所定の変換を施してwビットの整数の列y1,y2,…,yn,…,ymを得る。
【００１０】
そして、回転部は、当該整数の列yn+1,…,ymから回転ビット数を得て、当該整数の列y1,y2,…,yn,…,ymをwmビットのビット列と見て、これ、もしくは、これの一部に対して当該得られた回転ビット数の回転演算を行って、得られたwmビットのビット列からwビットの整数の列z1,z2,…,zn,…,zmを得る。
【００１１】
一方、更新部は、当該整数の列z1,z2,…,zn,…,zmを整数列x1,x2,…,xn,…,xmとして変換部に与える。
【００１２】
さらに、出力部は、変換部における変換ならびに回転部における回転が、所定の回数繰り返された場合、最後に得られたz1,z2,…,znを、乱数列r1,r2,…,rnとして出力する。
【００１３】
また、本発明の乱数列生成装置において、変換部は、写像g(・,・)を用いて、整数i (1≦i≦m-1)についての漸化式
y1  = g(xm,x1)；
yi+1 = g(xi,xi+1)
により変換を行うように構成することができる。
【００１４】
また、本発明の乱数列生成装置において、変換部は、所定の整数cと、写像g(・,・)と、を用いて、整数i (1≦i≦m-1)についての漸化式
y1  = g(c,x1)；
yi+1 = g(yi,xi+1)
により変換を行うように構成することができる。
【００１５】
また、本発明の乱数列生成装置において、変換部は、写像g(・,・)を用いて、整数i (1≦i≦m-1)についての漸化式
y1  = g(c,x1)；
yi+1 = g(xi,xi+1)
により変換を行うように構成することができる。
【００１６】
また、本発明の乱数列生成装置において、当該写像g(・,・)は、所定の写像h(・)と所定の整数q (0≦q≦2w-1)により
g(a,b) = 2b2 + h(a)b + q (mod 2w)
と定義されるように構成することができる。
【００１７】
また、本発明の乱数列生成装置において、当該写像h(・)は、
h(a) = a
と定義されるように構成することができる。
【００１８】
また、本発明の乱数列生成装置において、当該写像h(・)は、与えられた値の数値表現の所定のビットをクリアする演算により定義されるように構成することができる。
【００１９】
また、本発明の乱数列生成装置において、当該写像h(・)は、与えられた値の数値表現の所定のビットを反転する演算により定義されるように構成することができる。
【００２０】
また、本発明の乱数列生成装置において、当該写像h(・)は、与えられた値の数値表現の最下位２ビットを０１に置換する演算により定義されるように構成することができる。
【００２１】
また、本発明の乱数列生成装置において、回転部は、当該整数の列yn+1,…,ymをw(m-n+1)ビットのビット列と見て、これから所定の位置のビットを１個以上抽出して並べたビット列を整数と見たときの整数値を、回転ビット数として得るように構成することができる。
【００２２】
また、本発明の乱数列生成装置において、回転部は、当該整数の列yn+1,…,ymをw(m-n+1)ビットのビット列と見て、これから所定の位置のビットの値により、回転する方向を決めるように構成することができる。
【００２３】
また、本発明の乱数列生成装置において、回転部は、当該整数の列yn+1,…,ymから回転ビット数を得て、当該整数の列y1,y2,…,ynをwnビットのビット列と見て、これに対して当該得られた回転ビット数の回転演算を行って、得られたwnビットのビット列からwビットの整数の列z1,z2,…,znを得て、整数の列yn+1,…,ymをw(m-n)ビットのビット列と見て、これに対して当該得られた回転ビット数の回転演算を行って、得られたw(m-n)ビットのビット列からwビットの整数の列zn+1,…,zmを得るように構成することができる。すなわち、ziは、uiを所定の回転ビット数だけ回転演算したものである。
【００２４】
本発明の他の観点に係る暗号化復号化装置は、乱数生成部と、メッセージ受付部と、暗号化復号化部と、を備え、以下のように構成する。
【００２５】
すなわち、乱数生成部は、上記の乱数生成装置により、乱数列r1,r2,…,rnを生成する。
【００２６】
一方、メッセージ受付部は、wビットの整数の整数列p1,p2,…,をメッセージとして受け付ける。
【００２７】
さらに、暗号化復号化部は、wビットの整数の列p1 xor r1,p2 xor r2,…,pi xor r((i+n-1) mod n) + 1,…を暗号化もしくは復号化の結果として出力する。
【００２８】
本発明の他の観点に係る乱数列生成方法は、wビットの乱数の列を生成し、種受付工程と、初期化工程と、変換工程と、回転工程と、更新工程と、出力工程と、を備え、整数n，m (1≦n≦m-1)に対して、以下のように構成する。
【００２９】
すなわち、種受付工程では、wビットの整数の列s1,s2,…,sn,…,smを種として受け付ける。
【００３０】
一方、初期化工程では、当該受け付けられた整数の列s1,s2,…,sn,…,smを、整数列x1,x2,…,xn,…,xmとして変換工程に与える。
【００３１】
さらに、変換工程では、当該与えられた整数列x1,x2,…,xn,…,xmのそれぞれに対して所定の変換を施してwビットの整数の列y1,y2,…,yn,…,ymを得る。
【００３２】
そして、回転工程では、当該整数の列yn+1,…,ymから回転ビット数を得て、当該整数の列y1,y2,…,yn,…,ymをwmビットのビット列と見て、これ、もしくは、これの一部に対して当該得られた回転ビット数の回転演算を行って、得られたwmビットのビット列からwビットの整数の列z1,z2,…,zn,…,zmを得る。
【００３３】
一方、更新工程では、当該整数の列z1,z2,…,zn,…,zmを整数列x1,x2,…,xn,…,xmとして変換工程に与える。
【００３４】
さらに、出力工程では、変換工程における変換ならびに回転工程における回転が、所定の回数繰り返された場合、最後に得られたz1,z2,…,znを、乱数列r1,r2,…,rnとして出力する。
【００３５】
また、本発明の乱数列生成方法において、変換工程では、写像g(・,・)を用いて、整数i (1≦i≦m-1)についての漸化式
y1  = g(xm,x1)；
yi+1 = g(xi,xi+1)
により変換を行うように構成することができる。
【００３６】
また、本発明の乱数列生成方法において、変換工程では、所定の整数cと、写像g(・,・)と、を用いて、整数i (1≦i≦m-1)についての漸化式
y1  = g(c,x1)；
yi+1 = g(yi,xi+1)
により変換を行うように構成することができる。
【００３７】
また、本発明の乱数列生成方法において、変換工程では、写像g(・,・)を用いて、整数i (1≦i≦m-1)についての漸化式
y1  = g(c,x1)；
yi+1 = g(xi,xi+1)
により変換を行うように構成することができる。
【００３８】
また、本発明の乱数列生成方法において、当該写像g(・,・)は、所定の写像h(・)と所定の整数q (0≦q≦2w-1)により
g(a,b) = 2b2 + h(a)b + q (mod 2w)
と定義されるように構成することができる。
【００３９】
また、本発明の乱数列生成方法において、当該写像h(・)は、
h(a) = a
と定義されるように構成することができる。
【００４０】
また、本発明の乱数列生成方法において、当該写像h(・)は、与えられた値の数値表現の所定のビットをクリアする演算により定義されるように構成することができる。
【００４１】
また、本発明の乱数列生成方法において、当該写像h(・)は、与えられた値の数値表現の所定のビットを反転する演算により定義されるように構成することができる。
【００４２】
また、本発明の乱数列生成方法において、当該写像h(・)は、与えられた値の数値表現の最下位２ビットを０１に置換する演算により定義されるように構成することができる。
【００４３】
また、本発明の乱数列生成方法において、回転工程では、当該整数の列yn+1,…,ymをw(m-n+1)ビットのビット列と見て、これから所定の位置のビットを１個以上抽出して並べたビット列を整数と見たときの整数値を、回転ビット数として得るように構成することができる。
【００４４】
また、本発明の乱数列生成方法において、回転工程では、当該整数の列yn+1,…,ymをw(m-n+1)ビットのビット列と見て、これから所定の位置のビットの値により、回転する方向を決めるように構成することができる。
【００４５】
また、本発明の乱数列生成方法において、回転工程では、当該整数の列yn+1,…,ymから回転ビット数を得て、当該整数の列y1,y2,…,ynをwnビットのビット列と見て、これに対して当該得られた回転ビット数の回転演算を行って、得られたwnビットのビット列からwビットの整数の列z1,z2,…,znを得て、整数の列yn+1,…,ymをw(m-n)ビットのビット列と見て、これに対して当該得られた回転ビット数の回転演算を行って、得られたw(m-n)ビットのビット列からwビットの整数の列zn+1,…,zmを得るように構成することができる。すなわち、ziは、uiを所定の回転ビット数だけ回転演算したものである。
【００４６】
本発明の他の観点に係る暗号化復号化方法は、乱数生成工程と、メッセージ受付工程と、暗号化復号化工程と、を備え、以下のように構成する。
【００４７】
すなわち、乱数生成工程では、上記の乱数生成方法により、乱数列r1,r2,…,rnを生成する。
【００４８】
一方、メッセージ受付工程では、wビットの整数の整数列p1,p2,…,をメッセージとして受け付ける。
【００４９】
さらに、暗号化復号化工程では、wビットの整数の列p1 xor r1,p2 xor r2,…,pi xor r((i+n-1) mod n) + 1,…を暗号化もしくは復号化の結果として出力する。
【００５０】
本発明の他の観点に係るプログラムは、コンピュータを、上記の乱数列生成装置もしくは暗号化復号化装置として機能させ、もしくは、コンピュータに、上記の乱数列生成方法もしくは暗号化復号化方法を実行させるように構成する。
【００５１】
これらのプログラムは、コンパクトディスク、フレキシブルディスク、ハードディスク、光磁気ディスク、ディジタルビデオディスク、磁気テープ、半導体メモリ等のコンピュータ読取可能な情報記録媒体に記録することができる。
【００５２】
上記プログラムは、当該プログラムが実行されるコンピュータとは独立して、コンピュータ通信網を介して配布・販売することができる。また、上記情報記録媒体は、当該コンピュータとは独立して配布・販売することができる。
【００５３】
【発明の実施の形態】
以下に本発明の実施形態を説明する。なお、以下に説明する実施形態は説明のためのものであり、本願発明の範囲を制限するものではない。したがって、当業者であればこれらの各要素もしくは全要素をこれと均等なものに置換した実施形態を採用することが可能であるが、これらの実施形態も本願発明の範囲に含まれる。
【００５４】
（発明の実施の形態）
以下で説明する本発明の実施形態においては、「wビットの数値表現による乱数」の列を生成するために、有限体上の非線型変換として、所定の写像h(・)と所定の整数q (0≦q≦2w-1)とを用いて
g(a,b) = 2b2 + h(a)b + q (mod 2w)
により定義される写像g(・,・)を用いる。
【００５５】
写像h(・)としては、恒等写像
h(a) = a
を用いることができる。
【００５６】
また、所定のマスク値MASKを利用することにより、与えられた値aの数値表現の所定のビットをクリアする演算
h(a) = a and MASK
や、所定のビットを反転する演算
h(a) = a xor MASK
を採用してもよい。
【００５７】
さらに、最下位の２ビットを値０１に変換する演算
h(a) = (a and (not 3)) or 1
などを採用することができる。
【００５８】
ここで、各演算子は値aの数値表現（整数表現）に対するもので、andはビット積（ビットアンド）、xorはビット排他的和（ビットエクスクルーシブオア）、notはビット反転（ビットノット）、orはビット和（ビットオア）にそれぞれ相当するものである。
【００５９】
したがって、これらの演算は、コンピュータにおいては桁上がりや桁下がりなどをとりたてて考慮せずに、wビットの整数演算として用意されているものをそのまま適用して実現することができる。
【００６０】
またwの値は、当該コンピュータのＣＰＵ（Central Processing Unit）に用意されている機械語のビット幅、もしくは、これよりも小さい幅に対応させることが望ましい。
【００６１】
現在のところ、世界最高速のブロック暗号技術といわれているＲＣ６は、有限体上の非線型変換
f(x) = 2x2 + x (mod 2w)
を用いることによって実現されており、これによって、ある種から生成される乱数列は、これとは異なる種から生成される乱数列とは常に異なるものであり（１対１性）、生成される乱数列の最長周期が2w-1となっている。
【００６２】
本実施形態において採用される写像g(・,・)は、ＲＣ６における有限体上の非線型変換をさらに一般化したものであり、
h(a) = 1；
q = 0
としたg(・,・)を採用した場合には、ＲＣ６と同等の乱数列の生成能力を有する。なお、本発明においては、上記のＲＣ６同等の写像の以外の写像を選択できるため、さまざまなバリエーションの乱数を得ることができる。
【００６３】
また、これ以外の演算や値を選択した場合にも、良好な乱数列が得られることが、実験により実証されている。
【００６４】
図１は、本実施形態に係る乱数生成装置の概要構成を示す模式図である。図２は、本実施形態に係る乱数生成装置において実行させる処理の制御の流れを示すフローチャートである。以下、これらの図を参照して、本実施形態について、詳細に説明する。
【００６５】
乱数列生成装置１０１は、wビットの乱数の列を生成し、種受付部１０２と、初期化部１０３と、変換部１０４と、回転部１０５と、更新部１０６と、出力部１０７と、を備える。
【００６６】
まず、乱数列生成装置１０１の種受付部１０２は、wビットの整数の列s1,s2,…,sn,…,smを種として受け付ける（ステップＳ２０１）。ただし、1≦n≦m-1である。
【００６７】
典型的には、s1,s2,…,sn,…,smは、乱数列生成装置が有するＲＡＭ（Random Access Memory）等のメモリに格納されるが、ＣＰＵが有するキャッシュに格納してもよいし、ハードディスク等の読み書き可能な外部記録媒体に一時的に記憶してもよい。
【００６８】
ついで、初期化部１０３は、当該受け付けられたs1,s2,…,sn,…,smを、整数列x1,x2,…,xn,…,xmとして変換部１０４に与える（ステップＳ２０２）。
【００６９】
ここで、x1,x2,…,xn,…,xmも同様に、ＲＡＭ等のメモリに格納される。この場合、初期化部１０３が実行する処理は、s1,s2,…,sn,…,smに対応するメモリからx1,x2,…,xn,…,xmに対応するメモリへの値の転送によって実現することができる。
【００７０】
さらに、変換部１０４は、当該与えられた整数列x1,x2,…,xn,…,xmのそれぞれに対して上記の非線型変換g(・,・)により定義される変換を施してwビットの整数の列y1,y2,…,yn,…,ymを得る（ステップＳ２０３）。
【００７１】
当該変換としては以下のような漸化式により定義されるものを採用することができる。
【００７２】
（１）整数i (1≦i≦m-1)についての漸化式
y1  = g(xm,x1)；
yi+1 = g(xi,xi+1)
により変換を行う。
【００７３】
（２）所定の整数cを用いて、整数i (1≦i≦m-1)についての漸化式
y1  = g(c,x1)；
yi+1 = g(yi,xi+1)
により変換を行う。
【００７４】
（３）整数i (1≦i≦m-1)についての漸化式
y1  = g(c,x1)；
yi+1 = g(xi,xi+1)
により変換を行う。
【００７５】
これらの計算は、ＣＰＵが有するＡＬＵ（Arithmetic Logic Unit）を用いて実現することができる。y1,y2,…,yn,…,ymもまた、メモリ等に格納される。
【００７６】
そして、回転部１０５は、当該整数の列yn+1，…,ymから回転ビット数を得る（ステップＳ２０４）。回転ビット数を得る手法としては、以下のようなものが考えられる。
【００７７】
すなわち、yn+1，…,ymをビット列と見て、あらかじめ定めたビット位置のビットを順に並べ、再度これを整数値と見る。図３に、w=4，m-n=2の場合に、所定のビット位置の値から整数値を得る様子を示す。本図の例では、8ビットのビット列から3ビット分を抽出している。
【００７８】
3ビットから得られる整数値は、符号無し整数と見れば、0〜7の８通りである。この場合は、回転方向として「あらかじめ定めた方向（右もしくは左）」を採用し、得られる整数値をそのまま回転ビット数とする。
【００７９】
一方、１ビットを符号（正または負に対応付ける）とし、他の２ビットから回転量を得ることとして、この場合は、正の場合は左方向へ、負の場合は右方向へ、それぞれ絶対値分のビット数だけ回転するとしても良い。
【００８０】
ついで、回転部１０５は、当該y1,y2,…,yn,…,ymをwmビットのビット列と見て、これ、もしくは、これの一部に対して所定の回転演算を行って、得られたwmビットのビット列からwビットの整数の列z1,z2,…,zn,…,zmを得る（ステップＳ２０５）。
【００８１】
所定の回転演算としては、以下のようなものを採用することができる。
【００８２】
（１）wnビットのビット列を、得られた回転ビット数だけ巡回シフトするもの。図４に、この巡回シフトとして、w=4，n=4であって、y1,y2,…,y4をビッグエンディアンに配列して、１ビット左にシフトする場合の概要構成を示した。これは、wmビットのビット列の一部を回転する回転演算である。
【００８３】
（２）wmビットのビット列全体を、得られた回転ビット数だけ巡回シフトするもの。図４におけるwnビットのビット列の回転と同様に、wmビットのビット列全体を巡回させれば良い。
【００８４】
（３）y1，…，ynのwnビットのビット列を、得られた回転ビット数だけ巡回シフトするほか、これとは別に、yn+1，…，ymのw(m-n)ビットのビット列を、得られた回転ビット数だけ巡回シフトするもの。
【００８５】
これらの手法は、メモリ等に格納されたy1,y2,…,yn,…,ymの全体もしくは一部を、を、ＣＰＵにとって自然なビット幅単位で、桁上がり・桁下がりを考慮しつつ、順次巡回シフトすることによって実現することができる。この場合、得られるz1,z2,…,zn,…,zmは、y1,y2,…,yn,…,ymが格納されていたメモリ内の領域に新たな値として格納されることとなる。
【００８６】
さらに、出力部１０７は、変換部１０４における変換ならびに回転部１０５における回転が、所定の回数繰り返されたか否かを判定する（ステップＳ２０６）。
【００８７】
たとえば、ステップＳ２０１の前において、メモリ内に用意されたカウンタ変数に「所定の回数の値」を代入し、ステップＳ２０４とステップＳ２０６の間において当該カウンタ変数の値を１減じ、ステップＳ２０６においては、当該カウンタ変数の値が０になったか否かを判定することによって、実現することができる。
【００８８】
所定の回数繰り返された場合（ステップＳ２０６；Ｙｅｓ）最後に得られたz1,z2,…,znを、乱数列r1,r2,…,rnとして出力して（ステップＳ２０７）、乱数列の生成を終了する。
【００８９】
一方、所定の回数繰り返されていない場合（ステップＳ２０６；Ｎｏ）、更新部１０６は、当該z1,z2,…,zn,…,zmを整数列x1,x2,…,xn,…,xmとして変換部１０４に与えて（ステップＳ２０８）、ステップＳ２０３に戻り、変換（ステップＳ２０３）、回転（ステップＳ２０４、Ｓ２０５）の処理を繰り返す。
【００９０】
これは、z1,z2,…,zn,…,zmが格納されているメモリ等内の値を、x1,x2,…,xn,…,xmが格納されているメモリ等へ転送することによって実現できる。
【００９１】
乱数列生成装置１０１においては、図示しない記憶部が存在し、その記憶部は、s1,s2,…,sn,…,sm、x1,x2,…,xn,…,xm、y1,y2,…,yn,…,ym、z1,z2,…,zn,…,zm、r1,r2,…,rn,…,rmなどを異なる領域に、もしくは、値の利用の依存関係を分析することにより、同じ領域に記憶する（たとえば、y1,y2,…,yn,…,ymとz1,z2,…,zn,…,zm等。）ような構成をとることができる。また、各部は、上記の共有メモリを用いて互いに計算した値をやりとりするのである。
【００９２】
図５は、本実施形態の乱数列生成装置１０１が実現されるコンピュータの典型的な概要構成を示す模式図である。以下、本図を参照して説明する。
【００９３】
コンピュータ３０１は、ＣＰＵ  ３０２によって制御される。コンピュータ３０１に電源が投入されると、ＣＰＵ  ３０２は、ＲＯＭ（Read Only Memory）３０３に用意されたＩＰＬ（Initial Program Loader）を実行する。
【００９４】
そして、ＩＰＬの実行により、フレキシブルディスクドライブ３０４に装着されたフレキシブルディスクやハードディスク３０５等に記録されたＯＳ（Operating System）がロードされ、ユーザからの各種の指示入力を受け付けることができるようになる。
【００９５】
ユーザは、キーボード３０６やマウス３０７を操作して、コンピュータ３０１に対して各種の指示入力を与える。
【００９６】
これに応じて、ＯＳは、ハードディスク３０５やＣＤ−ＲＯＭ（Compact Disk ROM）ドライブ３０８に装着されたＣＤ−ＲＯＭに記録されたプログラムや各種のデータをＣＰＵ  ３０２に実行させ、実行の過程やその結果をディスプレイ３０９に表示する。
【００９７】
また、ＣＰＵ  ３０２は、一時的な記憶域として、ＲＡＭ  ３１１を利用する。ＲＡＭ  ３１１は、上記のように、計算の途中で利用される各種の数列を記憶するために用いられる。
【００９８】
さらに、ＣＰＵ  ３０２は、プログラムの実行の過程において、ハードディスク３０５に、生成された乱数列などの処理の結果や途中経過などの情報を保存することができる。
【００９９】
なお、本実施形態における演算は、上記のように、きわめて単純なビット演算に還元することができる。したがって、専用の電子回路（加算器、減算器、シフタ、ラッチ等）を組み合わせて乱数列生成装置１０１を構成することができるほか、ＡＳＩＣ（Application Specific Integrated Circuit）、ＤＳＰ（Digital Signal Processor）やＦＰＧＡ（Field Programmable Gate Array）などのような電子回路の構成状態を可変に変更できる電子素子を利用して、乱数列生成装置１０１を構成することができ、これらの態様も本発明の範囲に含まれる。
【０１００】
（実験の結果）
上記実施形態に係る乱数列生成装置１０１を用いて、以下の諸元で乱数列を生成させた。
W = 32,
n = 32,
g(a,b) = 2b2 + h(a)b
【０１０１】
ただし、写像h(・)は、与えられた値の数値表現の最下位２ビットを０１に置換する演算により定義される。
【０１０２】
また、変換および回転は、それぞれ１ラウンドごとに１回とした。すなわち、「所定の回数の繰り返し」は１回である。
【０１０３】
出力されるのは、全部でwn = 1024ビットの乱数列r1,r2,…,r1024である。
【０１０４】
これに対して２００００×８９９９９種類の種を与え、２００００×８９９９９ラウンドだけ乱数列r1,r2,…,r1024を出力させた。
【０１０５】
そして、これに対して乱数列のランダム性を検査する標準的なテストであるＦＩＰＳ  １４０−１ならびにＦＩＰＳ  １４０−２のうち、標準セキュリティ規格にあるランダム性検査テストを、１０２４ビットの乱数列の中の各ビット位置毎に適用して、本実施形態の乱数列の性質を検査した。
【０１０６】
これらのテストにおいては、各ビット位置から２００００ビットのビット列を取り出し、その２００００ビットのビット列に対して、以下が行われる。
モノビットテスト（monobit test）。所定の位置のビットの値の出現頻度に偏りがないか否かを調べるもの。
ポーカーテスト（poker test）。２００００ビットを５０００個の４ビットパターンに分割し、その４ビットパターンの出現頻度に偏りがないか否かを調べるもの。
ランズテスト（runs test）。乱数列から所定の長さの連を切り出した場合に、当該長さの連の出現頻度に偏りがないか否かを調べるもの。長さとしては１〜６を用いる。
ロングランズテスト（long runs teset）。ランズテストと同様であるが、ＦＩＰＳ  １４０−１の場合は３４以上の連が存在する場合ランダム性が否定され、ＦＩＰＳ  １４０−１の場合は２６以上の連が存在する場合ランダム性が否定される。
【０１０７】
実験の結果、ＦＩＰＳ  １４０−１においては、生成された１０２４ビット×８９９９９サンプルの２００００ビット列は、すべて、定められた基準をクリアした。
【０１０８】
また、ＦＩＰＳ  １４０−２においては、生成された１０２４ビット×８９９９９サンプルの２００００ビット列の内、９９.９２パーセントのサンプルが、定められた基準をクリアした。
【０１０９】
さらに、上記の乱数テストよりも厳しい乱数テストであるＮＩＳＴ  ８００−２２に本発明を適用して調べた結果、回転の手法（３）を利用すると、極めて良好な乱数を得られることが判明している。
【０１１０】
また、本技術をＸＩＬＩＮＸ（登録商標）社のVertex xcv1000（システムゲート数は１００万）のＦＰＧＡに実装したところ、本アルゴリズムの並列性から、25.62Gビット/secのスピードで乱数列を生成させることができた。すなわち、本技術をＦＰＧＡ等のハードウェアに実装すると、高速性の上で多大なメリットを得ることができる。
【０１１１】
このようにして、本実施形態によって生成された乱数列は極めて性質が良いものであり、秘密通信の暗号化の分野や物理現象、化学現象などの模擬実験の分野で有用であり、ハードウェア上で高速に良好なランダム性を持つ乱数列を出力するのに極めて有用であることが示された。
【０１１２】
（暗号化復号化装置）
上記の乱数生成装置を利用すれば、暗号化や復号化を実現することができる。図６は、このような暗号化や復号化を行う暗号化装置および復号化装置の概要構成を示す模式図である。
【０１１３】
暗号化装置６０１と、復号化装置６５１と、は、s1,…,sn,…,smを共通鍵とする。そして、それぞれが備える生成部６０２、６５２は、いずれも、同じ構成（計算手法）による乱数発生装置２０１を有し、この共通鍵s1,…,sn,…,smを入力として受け付ける。すると、同じ乱数r1,…,rnが出力されることとなる。
【０１１４】
この乱数を用いて、暗号化装置６０１においては、メッセージ受付部６０３が受け付けた伝送メッセージの整数列p1,p2,…,pi,…を、ＸＯＲ部６０４が、p1 xor r1,p2 xor r2,…,pi xor r((i+n-1) mod n) + 1,…のように変換して、これを暗号化済メッセージの整数列e1,e2,…,ei,…として出力する。
【０１１５】
ここで、xorは上述したように排他的論理和演算を意味し、a mod nはaをnで割った余りを意味する。
【０１１６】
一方、復号化装置６５１のメッセージ受付部６５３は、暗号化済メッセージの整数列e1,e2,…,ei,…を受け付け、ＸＯＲ部６５４がe1 xor r1,e2 xor r2,…,ei xor r((i+n-1) mod n) + 1,…のように変換して、これを復号化済メッセージの整数列f1,f2,…,fi,…として出力する。
【０１１７】
ここで、
0003735670.tif 000002
であるから、復号化済メッセージの整数列ともとの伝送メッセージの整数列とは同じものであり、暗号化ならびに復号化ができることが示された。
【０１１８】
なお、処理の対象となるメッセージの長さは、n以下とすることもできる。その場合には、上記の((i+n-1) mod n) + 1はiに置き換えることができる。このようにすれば、同じ乱数列を繰り返し利用するよりも、さらに秘匿性を高めることができる。
【０１１９】
上記のように、暗号化装置６０１と復号化装置６５１とは全く同じ構成であるので、１つの装置をある場合は暗号化装置６０１として、ある場合は復号化装置６５１として、それぞれ利用することができる。
【０１２０】
【発明の効果】
以上説明したように、本発明によれば、生成される乱数列が乱数列として好ましい性質を有するような乱数列生成装置、乱数列生成方法、これらを用いた暗号化復号化装置、暗号化復号化方法、ならびに、これらをコンピュータによって実現するためのプログラムを提供することができる。
【図面の簡単な説明】
【図１】  本発明の実施形態に係る乱数列生成装置の概要構成を示す模式図である。
【図２】  本実施形態の乱数列生成装置において実行される乱数列生成処理の制御の流れを示すフローチャートである。
【図３】  本実施形態の乱数列生成装置の回転部において実行される回転ビット数の取得の様子を示す説明図である。
【図４】  本実施形態の乱数列生成装置の回転部において実行される回転演算の様子を示す説明図である。
【図５】  本実施形態の乱数列生成装置が実現される典型的なコンピュータの概要構成を示す模式図である。
【図６】  暗号化装置と復号化装置の実施形態の概要構成を示す模式図である。
【符号の説明】
１０１  乱数列生成装置
１０２  種受付部
１０３  初期化部
１０４  変換部
１０５  回転部
１０６  更新部
１０７  出力部
３０１  コンピュータ
３０２  ＣＰＵ
３０３  ＲＯＭ
３０４  フレキシブルディスクドライブ
３０５  ハードディスク
３０６  キーボード
３０７  マウス
３０８  ＣＤ−ＲＯＭドライブ
３０９  ディスプレイ
３１１  ＲＡＭ
６０１  暗号化装置
６０２  乱数生成部
６０３  メッセージ受付部
６０４  ＸＯＲ部
６５１  復号化装置
６５２  乱数生成部
６５３  メッセージ受付部
６５４  ＸＯＲ部
【図１】
0003735670.tif 000003
【図２】
0003735670.tif 000004
【図３】
0003735670.tif 000005
【図４】
0003735670.tif 000006
【図５】
0003735670.tif 000007
【図６】
0003735670.tif 000008