(57)【要約】本発明は、実質的に真正な乱数を生成する乱数生成装置が、故障や不正操作等によって真正な乱数を生成し得なくなったときに迅速にそのことを検出することができる乱数検定方法及び乱数検定装置を提供する。乱数検定１に係る乱数検定方法は、ｎ種類の値がランダムに生成される乱数を検定する場合には、ｍ個の値を取り出す乱数取得工程と、ｐ回（０≦ｐ＜ｍ）出現する値がｎ種類のうち何個あるかを数える計数工程と、計数工程で得られた個数を、予め決めてある第一の閾値と比較する比較工程と、比較工程の結果、第一の閾値を越えたときは、前記乱数に問題があると判定する判定工程とを含んでいる。
2004081786.tif 000002
【特許請求の範囲】
【請求項１】
ｎ種類の値がランダムに生成される乱数を検定する乱数検定方法であって、
ｍ個の値を取り出す乱数取得工程と、
ｐ回（０≦ｐ＜ｍ）出現する値がｎ種類のうち何個あるかを数える計数工程と、
計数工程で得られた個数を、予め決めてある第一の閾値と比較する比較工程と、
比較工程の結果、第一の閾値を越えたときは、前記乱数に問題があると判定する判定工程と、
を含んでなることを特徴とする乱数検定方法。
【請求項２】
ｎ種類の値がランダムに生成される乱数を検定する乱数検定方法であって、
ｍ個の値を取り出す乱数取得工程と、
ｐ回（０≦ｐ＜ｍ）出現する値がｎ種類のうち何個あるかを数える計数工程と、
計数工程で得られた個数を、予め決めてある第二の閾値と比較する比較工程と、
比較工程の結果、第二の閾値を下回ったときは、前記乱数に問題があると判定する判定工程と、
を含んでなることを特徴とする乱数検定方法。
【請求項３】
ｎ種類の値をランダムに生成する乱数生成装置のための乱数検定装置であって、
ｍ個の値を取り出す乱数取得部と、
ｍ個の値をｎ種類の値に分類し、各値ごとにその値が何個出現したかをカウントする個別値カウント部と、
前記個別カウント部のカウント結果に基づいて、ｐ回（０≦ｐ＜ｍ）出現する値がｎ種類の値のうち何個あるかを数える特定回数出現値カウント部と、
特定回数出現値カウント部で得られた個数を予め決められた第一の閾値と比較し、当該第一の閾値を越えたときは前記乱数生成装置に問題があると判定する判定部と、
を含んでなることを特徴とする乱数検定装置。
【請求項４】
ｎ種類の値をランダムに生成する乱数生成装置のための乱数検定装置であって、
ｍ個の値を取り出す乱数取得部と、
ｍ個の値をｎ種類の値に分類し、各値ごとにその値が何個出現したかをカウントする個別値カウント部と、
前記個別カウント部のカウント結果に基づいて、ｐ回（０≦ｐ＜ｍ）出現する値がｎ種類の値のうち何個あるかを数える特定回数出現値カウント部と、
特定回数出現値カウント部で得られた個数を予め決められた第二の閾値と比較し、当該第二の閾値を下回ったときは前記乱数生成装置に問題があると判定する判定部と、
を含んでなることを特徴とする乱数検定装置。
【請求項５】
前記乱数生成装置は２進数ｑビット（２ｑ＝ｎ）のｎ種類の値を生成するものであり、
前記乱数取得部は、前記乱数生成装置からのｑビットの信号として得られた２進数をｎ種類にデコードするデコーダからなり、
前記個別値カウント部は、前記デコーダによってデコードされたデコード信号をカウントするｎ個のカウンタからなり、
前記特定回数出現値カウント部はｎビットシフトレジスタと、当該ｎビットシフトレジスタの出力信号に接続されたカウンタとを含んで構成され、
前記判定部は、前記第一又は第二の閾値が格納されたレジスタと、前記特定回数出現カウント部のカウンタ出力と前記閾値とを比較するコンパレータを含んでなる請求項３又は４に記載の乱数検定装置。
【請求項６】
ｎ種類の値がランダムに生成される乱数を検定する乱数検定方法であって、所定数の値の取り出しを１ラウンドとし、１ラウンド当たりに同じ値が何回出現するかという出現回数ごとに、１ラウンドにおいて発生する個数の確からしい分布を予め用意しておき、実際に前記所定数のサンプリングを行ったときに、前記分布からはずれていたときは前記乱数に問題があると判定することを特徴とする乱数検定方法。
【請求項７】
前記分布のうち予め特定の出現回数に着目し、その出現回数について１ラウンドにおいて発生する値の個数が、前記分布に基づいて定めた第一の閾値を越えたか、又は第２の閾値を下回ったかに基づいて、前記分布から外れたと判定するものである請求項６に記載の乱数検定方法。
【請求項８】
ｎ種類の値をランダムに生成する乱数生成装置のための乱数検定装置であって、
ｍ個の値を取り出す乱数取得部と、
ｍ個の値をｎ種類の値に分類し、各値ごとにその値の出現回数をカウントする個別値カウント部と、
前記個別値カウント部における各値の出現回数を、予め決められた閾値と比較し、当該閾値を上回ったときは、前記乱数生成装置に問題があると判定する判定部と、
を含んでなることを特徴とする乱数検定装置。
【請求項９】
前記乱数生成装置は２進数ｑビット（２ｑ＝ｎ）のｎ種類の値を生成するものであり、
前記乱数取得部は、前記乱数生成装置からのｑビットの信号として得られた２進数をｎ種類にデコードするデコーダからなり、
前記個別値カウント部は、前記デコーダによってデコードされたデコード信号をカウントするｎ個のカウンタからなり、
前記判定部は、前記個別値カウント部のｎ個のカウンタの出力値と前記閾値とを比較するコンパレータを含んでなる請求項８に記載の乱数検定装置。
【請求項１０】
一定時間内に生成する乱数値の個数が既知である乱数生成装置のための乱数検定方法であって、前記個数の前後における適切な個数を上限値及び下限値として設定し、前記乱数生成装置が前記一定時間に生成する乱数値の個数をモニターし、その個数が設定した上限値又は下限値を超えたときに乱数生成装置に問題が生じたと判定することを特徴とする乱数検定方法。
【請求項１１】
一定時間内に生成する乱数値の個数が既知である乱数生成装置のための乱数検定装置であって、
前記乱数生成装置から生成される乱数値をカウントするカウント部と、
前記カウント部がカウント動作を行う前記一定時間を生成する計時部と、
前記計時部よって生成される前記一定時間内に前記カウント手段がカウントした前記乱数生成装置から生成される乱数値の個数を予め設定されている上限値及び下限値と比較し、当該上限値又は下限値を超えたときにその旨の信号を出力する判定部と、
を含んでなることを特徴とする乱数検定装置。
【発明の詳細な説明】
【技術分野】  本発明は、乱数生成装置から生成された値に基づいて、当該乱数生成装置の故障又は当該乱数生成装置に対する不正操作の可能性を検出する乱数検定方法及び乱数検定装置に関する。
【背景技術】  乱数を生成する方法としては、例えばコンピュータを利用してソフトウェア的に乱数を発生させたり、カウンタ等を利用して擬似的に乱数を生成させるという方法が従来から知られている。したがって、このような方法で生成された乱数は真性な乱数とはいえず、このようにして生成されたものがどの程度真の乱数に近いかを評価することができるだけであった。このような評価方法として、大型のコンピュータを利用して乱数として出力される多数の値を取得し、取得したそれぞれの値の出現分布を調べ、それに基づいて各値がどの程度均一に出現しているかを調べるという方法が知られている。しかしながら、このような評価方法を実行するためには、膨大な数の値を取得してその出現分布を調べなければならないため、評価結果が得られるまでに長時間を要する。
一方、各種のシミュレーション、例えば金融派生商品（デリバティブ）分野、建造物の強度シミュレーション分野、天気予報の分野、シミュレーションを利用した高度な遊技機などの分野において、乱数が広く利用され始めており、そして、これらの分野に利用される乱数生成装置には、極めて真性度の高い乱数を高速に発生することが要求される。このような要求を満たす乱数生成装置として、ランダムな自然現象を利用した乱数生成方法が提案された。
近年、このような自然現象を利用して乱数を生成する方法を実現する手段として、抵抗体、導体、半導体などの内部で起こる熱雑音に基づいて乱数を生成する乱数生成装置が知られるようになった。このような乱数生成装置は回路構成が比較的簡単なため、実質的に真性な乱数を種々の分野において簡便に利用できるようになることが期待されている。
ところで、このような乱数生成装置を工場で生産して出荷する場合には、出荷前にその装置が正常に動作しているかどうかを何らかの方法で検査する必要がある。また、このような乱数装置が種々の装置に搭載されたり、或いはＩＣチップ化されてＩＣカード等に組み込まれる場合には、出荷された後に故障が生じた場合、あるいは特定の値の出現頻度を意図的に上げたり下げたりという不正操作が行われた場合に、そのことを迅速に検出する方法あるいは手段が必要となる。しかしながら、生成される乱数が実質的に真性なものである場合に、故障や不正操作等の問題が起こったことを簡易かつ確実に検出する方法はこれまでのところ確立されていない。
本発明は、このような技術的背景のもとでなされたものであり、その目的は、実質的に真正な乱数を生成する乱数生成装置が、故障や不正操作等によって真正な乱数を生成し得なくなったときに、迅速かつ確実にそのことを検出することができる乱数検定方法及び乱数検定装置を提供することである。
【発明の開示】
乱数検定１では、ｎ種類の値がランダムに生成される乱数を検定する場合において、まず、乱数生成装置等からｍ個の値を取り出し、このｍ個の値から、ｐ回（０≦ｐ＜ｍ）出現する値がｎ種類のうち何個あるかを数え、その結果得られた個数を、予め決めてある第一の閾値又は第二の閾値と比較し、この比較の結果第一の閾値を越えたとき又は第二の閾値を下回ったときに前記乱数に問題があると判定する。
乱数検定２では、ｎ種類の値がランダムに生成される乱数を検定する場合において、所定数の値の取り出しを１ラウンドとし、１ラウンド当たりに同じ値が何回出現するかという出現回数ごとに、１ラウンドにおいて発生する個数の確からしい分布を予め用意しておき、実際に前記所定数のサンプリングを行ったときに、前記分布からはずれていたときは前記乱数に問題があると判定する。
乱数検定３では、一定時間内に生成する乱数値の個数が既知である乱数生成装置において、前記個数の前後における適切な個数を上限値及び下限値として設定し、前記乱数生成装置が前記一定時間に生成する乱数値の個数をモニターし、その個数が設定した上限値又は下限値を超えたときに乱数生成装置に問題が生じたと判定する。
【図面の簡単な説明】  図１（ａ）〜（ｄ）は、乱数生成装置が実際に生成した８ビットの値（１０進数では０から２５５までの２５６種類の値）を１０２４個連続してサンプリングして横軸に示した各値の出現回数をカウントし、そのカウント結果（出現回数）を縦軸にとって示したグラフであり、図１（ｅ）は、乱数生成装置に対する１ラウンドのサンプリングを１０００回実行して各値の出現回数を累積しその累積結果を１０００で割って得られた、各値の１ラウンド当たりの平均出現回数である。
図２は、図１のグラフにおいて縦軸にとった出現回数を横軸にとり、その横軸のそれぞれの出現回数に対応する値の個数（２５６個のうち何個あるかという個数）を縦軸にとったグラフである。
図３は、１ラウンドのサンプリング（１０２４回のサンプリング）を１０万回実行して、２５６種類の値のうちで１回も出現しない値の数（横軸）が１０万ラウンドのうち何ラウンドだったか（縦軸）を示した分布である。
図４は、図３のグラフを、横軸のある値からそれよりも大きな値についてすべてを横軸方向に足し合わせて得られるグラフである。
図５は、「乱数検定１」に基づく乱数検定装置の主要部を示した回路図である。
図６は、「乱数検定１」に基づく乱数検定方法を、コンピュータにソフトウェア的に実行させるためのフローチャートの一例である。
図７は、１ラウンド１０２４回のサンプリングのうちで、２５６種類の値のうちのいずれかについて、同じ値が横軸に該当する回数だけ出現するラウンドが１０万ラウンドについて何ラウンド（縦軸）あるかを示した分布である。
図８は、「乱数検定２」に基づく乱数検定装置の主要部を示した回路図である。
図９は、「乱数検定２」に基づく乱数検定方法を、コンピュータにソフトウェア的に実行させるための考え方を示したフローチャートの一例である。
図１０は、「乱数検定３」を実現するための回路を示した回路図である。
【発明を実施するための最良の形態】  以下に、本発明に係る乱数検定方法及び乱数検定装置の実施の形態について説明する。本出願人は、２００３年２月４日に日本国特許庁に提出した国際出願ＰＣＴ／ＪＰ０３／０１１００において、簡易な回路構成で実質的に真正な乱数を生成することができる乱数生成装置を提案した。このように実質的に真正な乱数を生成する乱数生成装置は、本発明に係る乱数検定方法及び乱数検定装置によって乱数検定を行う対象として好適である。ただし、本発明の方法及び装置の検定対象となる乱数生成装置は上記出願に記載されたものには限定されない。
つづいて本実施形態に係る乱数検定方法について説明する。以下では、２進数８ビットの値（１０進数では０から２５５までの２５６種類の値）をランダムに生成する乱数生成装置に本発明を適用する場合について説明する。ただし、これはあくまでも一例であり、任意のビット数の値を生成する乱数生成装置について適用できることは言うまでもない。
図１（ａ）〜（ｄ）の各グラフは、乱数生成装置が実際に生成した８ビットの値（１０進数では０から２５５までの２５６種類の値）を１０２４個連続してサンプリングして横軸に示した各値の出現回数をカウントし、そのカウント結果（出現回数）を縦軸にとって示したグラフである。１０２４は２５６の４倍であるから、乱数生成装置の出力が正確な乱数であれば、０〜２５５の各値は平均４回出現するであろうことは直ちに分かる。以下では、乱数生成装置からこのように１０２４個の値を連続してサンプリングすることを「１ラウンド」とする。
図１（ｅ）は、乱数生成装置に対する１ラウンドのサンプリングを１０００回実行して各値の出現回数を累積しその累積結果を１０００で割って得られた、各値の１ラウンド当たりの平均出現回数である。なお、実際には、１０００回のサンプリング動作及び累積動作は、コンピュータに自動的に行わせている。
図１（ｅ）の結果を見ると明らかなように、各値は１ラウンドあたり平均してほぼ４回出現していることが確かめられる。換言すると、平均の出現回数がこのように極めて４に近いことより、ここでサンプリングした乱数生成装置の出力が正確な乱数であるということができる。
［乱数検定１］
図２は、図１のグラフにおいて縦軸にとった出現回数を横軸にとり、その横軸のそれぞれの出現回数に対応する値の個数（２５６個のうち何個あるかという個数）を縦軸にとったグラフである（なお、縦軸に対数目盛りを用いている点に注意を要する）。言い換えると、図１（ａ）〜（ｄ）のようなグラフにおいて、縦軸上の各値を横軸方向に加算していったときの結果を示している。すなわち、一回も出なかった値が何個か（図１の縦軸がゼロ、すなわち横軸上の黒丸の数が何個か）、１回出現した値が何個か、２回出現した値が何個か、３回出現した値が何個か、…、を数えて得られた分布である。ただし、実際には、１ラウンドのサンプリングを１０万回繰り返して実行し（実際にはコンピュータに自動的にサンプリング動作を実行させる）、それらを累積し、それを１０万で割って平均した値に基づいてプロットしている。
図２のグラフを具体的に見ると、例えば横軸が「０」のところでは、その縦軸の値は約「４．９」である。これは、一回も出現しない値の数が１ラウンドにつき平均して約４．９個であることを示している。実際に図１（ａ）〜（ｄ）の各ラウンドについて一度も出現しない値の数を数えると、（ａ）では５個、（ｂ）では６個、（ｃ）では７個、（ｄ）では４個となっており、これらを平均すると、一回も出現しない値の数は５．５個である。母集団が（ａ）〜（ｄ）の四つと少ないにもかかわらず、この値は上記の「４．９」に非常に近い。
また、例えば曲線がピークとなる横軸「４」のところを見ると、その縦軸は約「５０」である。これは、２５６種類の値のうち４回出現する値の数が１ラウンドにつき平均して約５０個であることを示している。横軸「４」のところがピークであるという事実は、図１（ｅ）の平均値が「４」であることに対応する。また、横軸が「１０」のところを見ると、その縦軸の値は約１．４である。これは、１０回出現する値の数が１ラウンドにつき平均して約１．４個であることを示している。一方、図２の横軸の各値についてその縦軸の値をすべて足し合わせると２５６となる。これは乱数として出力される値の種類が２５６種類であることに対応する。
図２に示した結果は、乱数生成装置が正確に乱数を出力しているときの分布である。乱数生成装置が故障したり、誰かが乱数生成装置に対して不正操作を行うなどして特定の値が出やすくなったり、出現頻度に偏りが生じるなどの問題が発生すると、その乱数生成装置の出力は図２に示した分布から外れる。すなわち、ある１ラウンドにおいて、２５６種類の値のうちのある特定の値の出現頻度だけが突出して高くなると、他の値の出現頻度は低くなる。したがって、特定の値に着目して図２の分布から外れたかどうかを監視することによって、乱数生成装置が適正に動作しているかどうかの検査、いわゆる乱数検定を行うことができる。これが、「乱数検定１」の基本原理である。
次に、この乱数検定についてより詳しく説明する。ここでは一例として、図２の横軸の値が「０」の場合に着目する。横軸が「０」とは、１ラウンド当たりのある値の出現回数がゼロ回ということであり、そのときの縦軸は、出現回数がゼロ回である値の最も確からしい個数（約４．９個）を表している。仮に、乱数生成装置に問題が生じ、特定の値の出現頻度が突出して高くなったとすると、出現回数がゼロ回である値の個数は、この４．９個を越えて大幅に増えるはずである。そこで、例えば１ラウンドのサンプリングを行って、一度も出現しない値の数を数え、それが「４．９」よりも大きい予め定めた値と比較し、これを越えていれば、その乱数生成装置に問題が発生したと判定することができる。
その一方で、乱数はいろいろな値がランダムに発生するものであるから、統計的なばらつきは常に存在し、乱数生成装置が正常に動作していても、ある特定の１ラウンドだけをみた時に、一度も出現しない値の数が４．９よりも大きくなることは当然にありうる。そのような場合に、４．９からあまり大きくない値を設定してしまうと、一度も出現しない値の数がこれを越えたからといって問題があると判定したとすると、正常に動作しているものまで問題ありと判定してしまう可能性が高くなる。
そこで、どのくらい大きくなったときに不都合が生じたと判定するかを決める理論的な指針について説明する。図３は、１ラウンドのサンプリング（１０２４回のサンプリング）を１０万回実行して、２５６種類の値のうちで１回も出現しない値の数（横軸）が１０万ラウンドのうち何ラウンドだったか（縦軸）を示した分布である。たとえば、横軸の値が「４」のところをみると、縦軸の値は約１９０００であるが、これは、１回も出現しない値の数が４個である場合の頻度が１０万回につき約１９０００回であることを示している。この分布のピークは、横軸がほぼ４．９のところにあり、この事実は図２の横軸がゼロのときの縦軸の値が約４．９であることに対応する。これは、前述のように、図３のグラフが図２のグラフにおいて、横軸が「０」、すなわち図２のグラフの縦軸のところに着目しているためである。
なお、図２のグラフにおいて横軸が「０」でないところに着目しても、図３と同様のグラフを描くことができ、その場合であっても以下の議論が当てはまる点に注意すべきである。例えば、図２のグラフの横軸が「１０」、すなわち「１０回」のところに着目して図３のようなグラフを描いたとすると、そのグラフは、２５６種類の値のうちで１０回出現する値の数の出現頻度分布となる。その分布を示すグラフの形は、図２のグラフから予想することができ、横軸が約「１．５」のあたりがピークとなる曲線になる。
さらに、図２のグラフの横軸「８」に着目すると、８回出願する値の数の出現頻度分布が得られ、そのグラフは横軸が「７．５」のあたりがピークとなる曲線となる。ちなみに、図１（ａ）のグラフでは、８回出現する値の数は９個、（ｂ）のグラフでは６個、（ｃ）のグラフでは９個、（ｄ）のグラフでは５個となっている。このことからも、平均が７．５個くらいという事実の妥当性が直感的に理解できる。
図４は、図３のグラフを、横軸のある値からそれよりも大きな値についてすべてを横軸方向に足し合わせて得られるグラフである。すなわち、このグラフは、１０万ラウンドのうちで、２５６種類の値のうち１サンプルも出現しなかった値の数が横軸の個数以上となるラウンドの数を示している。
例えば、横軸が「０」のところをみると、その縦軸は１０万である。これは、すべてのラウンドにおいて１サンプルも出現しなかった値の数は０個以上であるという当然の結果を示している。また、横軸が「５」のところをみると、その縦軸は約「５００００」である。これは、１サンプルも出現しなかった値の数が２５６種類の値のうち５個以上であるラウンドが、１０万ラウンド中約「５００００」ラウンドの割合であることを示している。さらに、図４の横軸が「１５」のところをみると、その縦軸は「２」である。これは、１サンプルも出現しなかった値の数が２５６種類の値のうち１５個以上であるラウンドが、１０万ラウンド中「２」ラウンドの割合であることを示している。
このことは、検定の結果１サンプルも出現しなかった値の数が２５６種類の値のうち例えば１５個以上だったのでその乱数生成装置に問題があると判定した場合に、その乱数生成装置には実際には問題が発生していない場合の確率が１０万分の２であることを意味する。すなわち、乱数生成装置の製造工場において乱数生成装置（例えばＩＣ化された乱数生成装置）を１０万個製造し、ひとつひとつについて１ラウンド分の値（１０２４個）をサンプリングして、２５６種類の値のうち１サンプルも出現しなかった値の数が「１５」以上の場合にそれを不良品と判定することにした場合には、実際には良品であるものを不良品と判定する危険率が１０万分の２となる。これは、このように小さい値であるから、１サンプルも出なかった値の数が１５個以上出たからそれを不良品とすることは極めて妥当であることを示しているとも言える。
この場合に、もし、不良品検出についてより高い精度を必要とする場合には、不良品と判定する閾値を「１５」よりも小さくし、例えば「１０」とすれば、良品を多少犠牲にする確率は高まるが、不良品を出荷する危険性をより低くすることができる。このように、本実施形態によれば、不良品とする閾値をどのくらいの値とするのが適切であるかを理論的に決定することができる。
さらに、上述の検定方法を同じ乱数生成ＩＣに対して例えば２回続けて行ったとすると、その２回について、１サンプルも出なかった値の数が「１５」個以上となる確率は１０万分の２のさらに２乗という極めてゼロに近い確率となり、現実にはほとんどあり得ない。したがって、１サンプルも出現しなかった値の数が「１５」個以上だったものについてもう一度同じ検定を行い、やはり同じく１５個以上だったとすれば、それはほぼ間違いなく問題ありと言うことができ、判定の確実性をより高めることができる。
また、上記では、一度も出現しなかった値の個数に着目した場合について説明したが、乱数検定１はこのような場合には限られず、任意の回数（例えばｐ回）出現する値の個数に着目し、その個数について適切な閾値を設定し、これを越えた場合、あるいはこれを下回った場合に乱数に問題があると判定するという構成とすることも可能である。
この乱数検定１は、真正な乱数の基本的性質に着目した点を特徴とする。したがって、この検定方法は、前述の国際出願ＰＣＴ／ＪＰ０３／０１１００に記載されているような、実質的に真正な乱数を生成することのできる乱数生成装置に適用することで、より有益な結果が得られる。
図５は、上で述べた「乱数検定１」の考え方に基づいて、ハードウェア的に構成した乱数検定装置の主要部を示した回路図である。図５において、乱数発生器１０はここでの乱数検定の対象となるもので、ここでは２進数８ビットの乱数を出力するものとする。
乱数発生器１０は、８ビットの乱数を出力するとともに、一つの乱数を発生するたびにストローブ信号を出力する。このストローブ信号はカウンタ３０へ供給され、これをインクリメントする。カウンタ３０は１ラウンド分の１０２４回のサンプリング動作をカウントするためのもので、１０２４カウントまでインクリメントされると、次に入来するストローブ信号によってリセットされ、それと同時にキャリィ号を出力する。
乱数発生器１０から出力された８ビットのランダムな２進数はデコーダ１１に供給され、ここで２５６種類の整数値（０から２５５まで）のうちのいずれかにデコードされる。デコーダ１１の２５６個の出力ラインは、同じく２５６個設けられている８ビットのカウンタ１２０〜１２２５５のうち対応するものの入力に接続されている。デコーダ１１においてデコードされた値は、その値に対応する出力ラインから論理値「１」として出力され、対応するカウンタへ供給されて当該カウンタをインクリメントする。
各カウンタ１２０〜１２２５５からの８ビット出力は、対応する８入力論理和回路（ＯＲ回路）１３０〜１３２５５に供給される。この８入力論理和回路１３０〜１３２５５は、その８ビットすべてが論理値「０」の場合のみ、その出力が論理値「０」となり、それ以外の場合、すなわち８ビットの入力のうち１つでも論理値「１」がある場合は、その出力が論理値「１」となる。その結果、２５６種類のうちで一度も出現しなかった値に対応する８入力論理和回路の出力のみが、論理値「０」となる。８入力論理和回路１３０〜１３２５５の論理出力は、対応するインバータ１４０〜１４２５５によって反転され、２５６ビットシフトレジスタに供給される。したがって、２５６ビットシフトレジスタの２５６個の入力のうち、一度も出現しなかった値に対応した入力だけに論理値「１」が立つ。この論理値「１」が立った入力の数は、１ラウンド１０２４回のサンプリングのうち一度も出現しなかった値の数に対応する。
１ラウンド分のサンプリングが終了して前述のキャリィ信号が発せられると、この信号はデータロード信号としてシフトレジスタ１５に供給される。この信号に同期して、シフトレジスタ１５はそのときのすべての入力の値を取り込む。
なお、このキャリィ信号は、遅延回路１６を経てカウンタリセット信号となり、各カウンタ１２０〜１２２５５へも供給される。これにより、これらのカウンタはカウント値ゼロにリセットされる。遅延回路１６を設けたのは、シフトレジスタ１５がカウンタ１２０〜１２２５５のカウント値を取り込む前にリセットされるのを防ぐためである。
続いて、シフトレジスタ１５のシフト動作を実行する。このシフト動作は、前述のキャリィ信号が遅延回路１６を経てスタート信号となり、これがカウンタのスタート／ストップ回路１８に供給されることによって開始される。すなわち、スタート信号がスタート／ストップ回路１８に供給されると、２５６カウントのカウンタ２１が、クロック１９から供給されるクロック信号をカウントする。
シフトレジスタ１５は、クロック１９からのクロック信号がインバータ２０によって反転されたシフトクロックが入来するたびに、保持している２５６ビットのデータを１ビットずつ右側にシフトさせるとともに、最も右側のデータ（最初はインバータ１４２５５の論理値）をシフトレジスタ出力から論理積回路２３の一方の入力へ供給する。論理積回路２３のもう一方の入力には、クロック１９からのクロック信号（論理値「１」）が供給される。したがって、論理積回路２３の出力には、シフトレジスタ１５の出力がそのまま現れる。カウンタ２４は、この論理積回路２３の出力が論理値「１」となったときにインクリメントされる。２５６回のシフト動作が終了した時点におけるカウンタ２４のカウント値は、前述のデータロード信号がシフトレジスタ１５に供給された時点で取り込まれた２５６ビットのデータの中に含まれる論理値「１」の数に対応し、これは１ラウンド１０２４回のサンプリングのうちで、一度も出現しなかった値の個数を表している。
カウンタ２１は、クロック１９からのクロック信号を２５６までカウントするとキャリィ信号を出力する。このキャリィ信号は、カウンタスタート／ストップ回路１８に供給されるとともに、遅延回路２２を介してカウンタ２４に供給される。カウンタスタート／ストップ回路１８は、このキャリィ信号を受け取るとストップ信号を出力する。このストップ信号がカウンタ２１に供給されると、カウンタ２１はカウント動作を停止する。また、遅延回路２２を経たキャリィ信号がカウンタ２４に供給されると、カウンタ２４はリセットされる。これより、一度も出現しなかった値の数のカウント動作は終了する。
閾値レジスタ２５には、一例として「１５」という閾値が設定されている。コンパレータ２６は、カウンタ２４のカウント値を閾値レジスタ２５に設定されている値と比較しており、カウント値がこの設定値「１５」に達すると、その時点で、ウォーニング（警告）信号を発する。
このウォーニングを常時モニターし、ウォーニング信号が発せられたときは、これを検出することによって乱数発生器１０に何らかの問題が生じた可能性が極めて高いことを知ることができる。図５に示した回路は、以上説明した動作を繰り返し実行し、乱数生成器１０から出力される乱数を常時検定している。
図６は、上で述べた「乱数検定１」の方法をコンピュータにソフトウェア的に実行させるためのフローチャートの一例である。ここでも、検定の対象となる乱数生成装置は、８ビットの乱数を生成するものとして説明するが、これはあくまでも一例であることは言うまでもない。
まず、予め用意されているカウンタをリセットする（ステップ１０）。続いて、乱数として出力される８ビットの値を取得し（ステップ１１）、０から２５５までの２５６種類の値に対応して設けられた２５６個のカウンタのうち、取得した乱数値に対応するカウンタをインクリメントする（ステップ１２）。このような動作を１ラウンド１０２４サンプル分実行する（ステップ１３、１４）。そして、この時点で２５６個のカウンタのうちで、カウント値が「０」であるものの個数を、別のカウンタをインクリメントしながら数える（ステップ１５）。そして、最終的なこのカウンタのカウント値を「１５」と比較し（ステップ１６）、１５よりも小さければ乱数生成装置は問題なしと判定し、１５以上であれば、乱数生成装置に何らかの問題があると判定して、ＮＧ信号（警告信号）を発する（ステップ１７）。
［乱数検定２］
次に、乱数検定２について説明する。図７は、１ラウンド１０２４回のサンプリングのうちで、２５６種類の値のうちのいずれかについて、同じ値が横軸に該当する回数だけ出現するラウンドが１０万ラウンドについて何ラウンド（縦軸）あるかを示した分布である。ただし、横軸が１０以上の部分のみを示してある。例えば、図７で横軸が「１０」のところ（すなわち縦軸上）を見ると、そのときの縦軸の値は約「７５０００」となっている。これは、１ラウンド１０２４回のサンプリングのうちで同じ値が１０回出現するラウンドが、１０万ラウンド当たり約７５０００ラウンド現れることを示している。ちなみに、図１（ａ）〜（ｄ）に示した４ラウンドを見ると、（ａ）では１０サンプルが同じ値となる値が３個あり、（ｂ）ではゼロ個であり、（ｃ）では１個あり、（ｄ）では１個ある。したがって、同じ値が１０回出現するラウンドは、４ラウンド中３ラウンドである。
これは言い換えると、１ラウンドだけを見たときに、そのラウンドで同じ値が１０回出現する確率が約４分の３であることを示している。
また、図７で横軸が「１１」のところを見ると、そのときの縦軸の値は約「４００００」となっている。これは、同じ値が１１回出現するラウンドが、１０万ラウンド当たり約４００００ラウンド現れることを示している。したがって、１ラウンドでは同じ値が１１回出現する確率は約５分の２である。ちなみに、図１（ａ）〜（ｄ）の４ラウンドでは、（ａ）では１１サンプルが同じ値となる値がゼロ個であり、（ｂ）では１個あり、（ｃ）ではゼロ個であり、（ｄ）では３個あり、１１サンプルが同じ値となる場合のあるラウンドは、４ラウンド中２ラウンドであった。
更に、図７で横軸が「１９」のところを見ると、そのときの縦軸の値は「２」となっている。これは、同じ値が１９回出現するラウンドが、１０万ラウンド当たり２ラウンド現れることを示している。言い換えると、１ラウンドについて同じ値が１９回出現する確率は１０万分の２、すなわち０．００２％と非常に少ない。ちなみに、図１（ａ）〜（ｄ）に示した４ラウンドを見ると、同じ値が１９回出現するラウンドは一つもない。
以上のことから、１ラウンド中に同じ値が出現する確率は、その出現回数が多くなるに従って急激に低下することが分かる。このため、例えば１ラウンド分のサンプリングを行った結果、特定の値の出現回数が突出して多かったとすれば、乱数生成装置に不正操作或いは故障等による何らかの問題が生じた可能性が高いと言えるので、このことを利用して乱数検定を行うことができる。すなわち、予め回数についてある閾値を設定しておき、２５６種類のうちのいずれかの値がこの閾値を越える回数出現したら、その乱数生成装置に問題が生じていると判定する。
ただし、乱数生成装置が正常に動作していても、統計的なばらつきがあるため、ある特定の１ラウンドだけをみた時に特定の値が多数回出現することも可能性としてありうる。したがって、この閾値が低すぎると、問題のある乱数生成装置を排除する確実性は高まるが、問題のない乱数生成装置まで排除してしまう可能性が高くなる。一方、この閾値が高すぎると、問題のない乱数生成装置を排除する可能性は低くなるが、問題のある乱数生成装置を排除する確実性は低下する。このため、その乱数生成装置の用途などを考慮し、問題のある乱数生成装置をどの程度の確実性で排除したいかによって、設定すべき閾値を決める必要がある。
一例として、「１９回」（図７の横軸「１９」のところ）を閾値として設定したとすると、乱数が正常に生成されている場合に１ラウンド中に同じ値が１９サンプル以上出現する確率は、前述のように１０万分の２である。これは、この判定方法を用いて乱数生成装置の検定を行ったときに、乱数生成装置１０万個当たりにつき２個の割合で、問題のない乱数生成装置を問題ありと判定する可能性があることを意味する。
この場合、この検定方法を同じ乱数生成装置に対して例えば２回続けて行ったとすれば、続けて同じ数が１９回出る確率は１０万分の２の２乗という極めてゼロに近い値であり、現実にはこのようなことはあり得ないと考えることができる。したがって、いずれかの値が１９回以上出現したものについて、もう一度同じ検定を行って、やっぱりいずれかの値が１９回以上出現したとすれば、それは問題が生じていると判定することができる。
この判定方法は、乱数生成装置の工場出荷時における検定（工場検定）に適用することができる他、この乱数検定の方法をソフトウェア的又はハードウェア的に実現した回路を乱数生成装置に付加し、その乱数生成装置を動作させているときに常に乱数検定を実行するという用途に適用することができる。
この乱数検定２も、真正な乱数の基本的性質に着目した点を特徴としている。したがって、前述の国際出願ＰＣＴ／ＪＰ０３／０１１００に記載されているような、実質的に真正な乱数を生成することのできる乱数生成装置に適用することで、より有益な結果が得られる。
図８は、上で述べた「乱数検定２」の考え方に基づいて、ハードウェア的に構成した乱数検定装置の主要部を示した回路図である。図８において、乱数発生器４０はここでの乱数検定の対象となるもので、ここでも図５の乱数発生器１０と同様に２進数８ビットの乱数を出力するものとする。
乱数発生器４０は、８ビットの乱数を出力するとともに、一つの乱数を発生するたびにストローブ信号を出力する。このストローブ信号はカウンタ５０へ供給され、これをインクリメントする。カウンタ５０は１ラウンド分の１０２４サンプルをカウントするためのもので、１０２４カウントまでインクリメントされると、次に入来するストローブ信号によってリセットされ、それと同時にキャリィ信号を出力する。
乱数発生器４０から出力された８ビットのランダムな２進数はデコーダ４１に供給され、ここで２５６種類の整数値（０から２５５まで）のうちのいずれかにデコードされる。デコーダ４１の２５６個の出力ラインは、同じく２５６個設けられている８ビットのカウンタ４２０〜４２２５５のうちで対応するものの入力に接続されている。デコーダ４１においてデコードされた値は、その値に対応する出力から論理値「１」として出力され、対応するカウンタへ供給されて当該カウンタをインクリメントする。したがって、１ラウンドのサンプル動作が終了した時点におけるこれらのカウンタのカウント値は、０から２５５までのうち対応する値が何回出現したか示している。
各カウンタ４２０〜４２２５５からの８ビットの出力は、コンパレータ４３０〜４３２５５のうち対応するものに供給される。各コンパレータ４３０〜４３２５５は、対応するカウンタから供給された値を、レジスタ４４に予め設定されている閾値と比較する。ここでは、レジスタ４４には予め閾値「１９」が設定されているとする。この閾値は、前述のように、ランダムに生成される２５６種類の値のうちのいずれかがこれ以上の回数出現したときに検査対象の乱数生成装置に問題が生じたと判定するためのものである。
コンパレータ４２０〜４２２５５の出力は通常は論理値「０」であるが、対応するカウンタから出力される値がレジスタ４４に設定されている「１９」以上のときに「１」となる。コンパレータ４２０〜４２２５５の出力は２５６入力の論理和回路４５の対応する入力に供給される。したがって、２５６個のコンパレータのうち論理値が「１」となるものが一つでもあれば、論理和回路４５の出力は論理値「１」となり、これをウォーニング（警告）信号とする。
前述のウォーニング信号を常時モニターし、ウォーニング信号が発せられたときは、これを検出することによって乱数発生器４０に何らかの問題が生じた可能性が高いことを知ることができる。図８に示した回路は、以上説明した動作を繰り返し実行し、乱数生成器１０から出力される乱数を常時検定している。なお、１ラウンド分のサンプリングが終了して前述のキャリィ信号が発せられると、この信号は各カウンタ４２０〜４２２５５へ供給される。これにより、これらのカウンタはカウント値ゼロにリセットされる。
図９は、上で述べた「乱数検定２」の方法をソフトウェア的に実現するための考え方を示したフローチャートである。ここでも、検定の対象となる乱数生成装置は、８ビットの乱数を生成するものとして説明するが、これはあくまでも一例である。
まず、予め用意されているカウンタをリセットする（ステップ２０）。続いて、乱数として出力される８ビットの値を取得し（ステップ２１）、０から２５５までの２５６種類の値に対応して設けられた２５６個のカウンタのうち、取得した乱数値に対応するカウンタをインクリメントする（ステップ２２）。このような動作を１ラウンド１０２４サンプル分実行する（ステップ２３、２４）。そして、この時点で２５６個のカウンタのカウント値のうちで最大のものをサーチし（ステップ２５）、その最大カウント値を予め設定してある値「１９」と比較し（ステップ２６）、この最大カウント値が「１９」よりも小さければ乱数生成装置は問題なしと判定し、「１９」以上であれば、乱数生成装置に何らかの問題があると判定して、ＮＧ信号（警告信号）を発する（ステップ２７）。
［乱数検定３］
次に乱数検定３について説明する。乱数生成装置、その中でも特に熱雑音素子からの熱雑音に基づいて乱数を生成する乱数生成装置は、その回路定数や、波形成形回路の閾値の設定の仕方によって、単位時間当たりに生成する乱数値の個数は、平均値を中心として一定の分散値を持ったガウス分布を示す。すなわち、一定時間当たりに生成される乱数値の個数は必ずしも一定ではないが、大体において一定の幅の中に収まることが分かっている。
しかしながら、もしも乱数生成装置に対して不正操作が行われたり、或いは故障等が発生するといった何らかの問題が生じたとすると、単位時間当たりに生成される乱数値の個数が大きく変動する可能性が高い。例えば、１秒間に生成する乱数値が平均１万個で、かつ、どのような場合でも１秒間に１００００±１０００個の範囲にほとんど収まることが分かっている乱数生成装置において、１秒間に２００００個の乱数値が生成されたり、あるいは５０００個しか生成されなかったりすれば、その乱数生成装置に何らかの問題が生じた可能性が極めて高い。
そこで、予め正常な乱数生成装置が一定時間（例えば１秒間）に生成する乱数値の個数を調べておき、その前後における適切な個数を上限値及び下限値として設定し、その乱数生成装置が上記一定時間に生成する乱数値の個数を常時モニターし、その個数が設定した上限値又は下限値を超えた場合に乱数生成装置に何らかの問題が生じたと判定することができる。これが「乱数検定３」の基本原理である。
図１０は、この乱数検定３を実現するための回路を示した回路図である。乱数発生器６０は、８ビットの乱数値を出力するとともに、一つの乱数値を発生するたびにストローブ信号を出力する。このストローブ信号はカウンタ６１へ供給され、カウンタ６１のカウント値をインクリメントする。カウンタ６１に接続されているタイマ６２は、クロック信号をカウントして一定の時間間隔を生成し、この時間間隔ごとにカウンタ６１に対して信号を送出する。この信号がタイマ６２からカウンタ６１に送出されると、カウンタ６１のその時点でのカウント値がカウンタ値転送レジスタ６３に転送され、格納される。
一方、上限値レジスタ６４及び下限値レジスタ６５には、予め、乱数生成器６０の特性を考慮し決められた上限値及び下限値が設定してある。これらのうち上限値はコンパレータ６６１の一方の入力に供給され、下限値はコンパレータ６６２の一方の入力に供給される。また、カウンタ値転送レジスタ６３に格納されたカウント値は、コンパレータ６６１及び６６２にそれぞれに入力される。コンパレータ６６１は、入力されたカウント値が上限値を上回ったときに論理値「１」を出力し、コンパレータ６６２はカウント値が下限値を下回ったときに論理値「１」を出力する。各コンパレータの出力はそれぞれが２入力論理和回路６７の入力となって、その出力はウォーニング（警告）信号となる。したがって、二つのコンパレータ６６１、６６２の何れかの出力が「１」となったときにウォーニングが発せられ、これより、乱数生成器に問題が生じた可能性が高いことを知ることができる。
以上、乱数検定１、２、３について説明したが、これらを個別に乱数生成装置に適用できることは勿論、これらのうちの二つ又は三つを組み合わせて乱数生成装置に適用することも可能である。
【産業上の利用可能性】  本発明に係る乱数検定方法によれば、実質的に真正な乱数を生成する乱数生成装置が故障や不正操作等によって真正な乱数を生成し得なくなったときに、迅速かつ確実にそのことを検出することができる。また、この方法に基づいた本発明に係る乱数検定装置は、比較的簡易な回路構成で実現することができる。このため、本発明に係る乱数検定方法及び乱数検定装置を、乱数生成装置を製造する工場における出荷時の検査等に適用できるほか、例えば集積回路化された乱数生成装置に本発明に係る乱数検定装置を付随させ、あるいはこれに組み込んでおき、乱数生成装置を出荷したあと実際に稼働させる際に、常時乱数検定を実行するといった利用も可能となる。このため、これまでにない広い範囲で乱数検定を実行することが可能となる。
【図１】
2004081786.tif 000003
【図２】
2004081786.tif 000004
【図３】
2004081786.tif 000005
【図４】
2004081786.tif 000006
【図５】
2004081786.tif 000007
【図６】
2004081786.tif 000008
【図７】
2004081786.tif 000009
【図８】
2004081786.tif 000010
【図９】
2004081786.tif 000011
【図１０】
2004081786.tif 000012
【国際調査報告】
2004081786.tif 000013
2004081786.tif 000014
2004081786.tif 000015
2004081786.tif 000016
2004081786.tif 000017
2004081786.tif 000018