説明

乱数生成検定方法及びこれを用いた乱数生成検定装置

【課題】物理現象に基づいて独立に事象が発生するまでの時間間隔から得られる指数分布に従った乱数値に対する乱数検定を行うことを目的とする。
【解決手段】物理現象に基づいて独立に発生する事象について所定の条件を満たす第1の時点から、前記所定の条件を満たす第2の時点までの時間間隔を計測し(2)、前記計測された時間間隔を基にn種類の乱数を生成し、前記乱数が生成されると各乱数ごとにその頻度をカウント(8)し、前記乱数の生成レートを基に各乱数の発生頻度の範囲を理論統計的に導出し(6,7)、n種類の乱数ごとに前記カウント値と前記発生頻度の範囲とを比較して(11,12)、カウント値が範囲外にあるときは生成した乱数に問題があると判定する(13,14,15)ので、物理現象に基づいて生成された乱数が従う乱数特性そのものから直接的に乱数性の検定を行うことが可能となり、検定の適正さを向上させることができる。

【発明の詳細な説明】
【技術分野】
【0001】
本発明は、乱数発生素子から物理乱数を取り出して真の乱数を生成する物理乱数方法及び装置に関し、特に、物理乱数としての固有の特性が維持されている状態で乱数性の検定を可能にすることができる技術に係るものである。
【背景技術】
【0002】
物理現象に基づいて独立に事象が発生する場合、ある時点で発生した後の次に発生するまでの時間間隔の集合は乱数として利用するとその利益が大きい。なぜなら、例えばコンピュータを用いてソフトウェア的に発生させた乱数は厳密にみれば繰り返して現れることが避けられず、予測可能な擬似乱数の範疇でしかないからである。一方、物理現象に基づいて生成された乱数は、物理現象に基づいて独立に事象が発生していれば真正な乱数となり、近年、様々な技術分野でこの乱数生成方法を組み込んだ装置の重要性が目立ってきている。
【0003】
物理現象に基づく乱数生成方法には、例えば、抵抗、ダイオード等の半導体、あるいは導体を熱雑音発生源として用いる方法がある。これら熱雑音源から独立な事象として発生するパルスのうち所定の閾値を超えるパルスを検出していけば、その時間間隔が物理乱数(自然乱数)となることが知られている。また、独立に発生するパルス間の時間間隔は、指数分布に従うことが分かっている。つまり、サンプリングされたパルス間の時間間隔が表す値は、指数分布に従う自然乱数とみなすことができる。
【0004】
このため、パルス間の時間間隔を自然乱数として生成する乱数生成器に人為的操作を施せばパルス発生の独立性が維持されず、その結果、特定の値の出現頻度が高くなる等の指数分布に従わない不真正の乱数値が生成される。そこで、この原理を、乱数生成器が意図的に不正操作されたときの発見に利用したり、乱数生成器の故障の検出に役立てようとする試みがなされるようになってきた。
【発明の開示】
【発明が解決しようとする課題】
【0005】
ところで、どのような値が出現するのか全く予想できない自然乱数が真正であるか否かを検定する際には、等確率性と無規則性を評価する必要がある。等確率性とは等出現性と言い換えることができ、どの時点をとっても各値の出現する確率が全て等しい、即ち、特定の値が著しく偏って出現している現象になっていないという乱数の基本的性質である。また、無規則性とは無相関性又は一様性と言い換えられることができ、i番目の値とj番目の値に何の相関がないこと、即ち、所定の時間幅でみればすべての値がみな一様に平坦に出現しているというものである。無規則性の要件は、例えば、熱雑音源から発生される乱数パルス間の時間間隔を計時パルスを使ってその発生カウント数で計測しようとする場合に、有限カウンタのカウント動作を一巡させるときに必要とされる。つまり、単位時間当たりに取り出す乱数パルス数を増やすと時間的に近接したパルスを識別できなくなるが、これがカウント動作が一巡する前の小さい値の出現頻度を小さくしてしまい、乱数頻度の均一性に影響を与える場合があるためである。
【0006】
このような小さい乱数値の出現頻度の不均一さを改善するために無規則性(一様性)に着目して検定する場合、検定対象となる乱数は一様性が求められる状況下での値である必要がある。そこで、例えば、熱雑音源から発生するパルス間の時間間隔を測定して得た乱数値に対して排他的論理和の演算処理を施し、その後に乱数が真正であるか否かの検定を行ったりする。具体的には、順方向カウンタと逆方向カウンタの対応する桁同士の排他的論理和をとり、得られた値を最終的な乱数値として設定している。しかしながら、排他的論理和の演算処理によって得られる各乱数値の発生頻度は、演算処理前の乱数値に大きな偏りがあっても殆ど一様になることから、悪意のある人為的操作や乱数発生源の故障等によって乱数値の発生に偏りがある状況を的確に検出することを困難にさせてしまう恐れがある。
そこで、本発明は、物理現象に基づいて独立に事象が発生するまでの時間間隔から得られる指数分布に従った乱数値そのものに対する乱数検定を行うことを目的とする。
【課題を解決するための手段】
【0007】
本発明の乱数生成検定方法は、物理現象に基づいて独立に発生する事象について所定の条件を満たす第1の時点から、前記所定の条件を満たす第2の時点までの時間間隔を計測し、前記計測された時間間隔を基にn種類の乱数を生成し、前記乱数が生成されると各乱数ごとにその頻度をカウントし、前記乱数の生成レートを基に各乱数の発生頻度の範囲を理論統計的に導出し、n種類の乱数ごとに前記カウント値と前記発生頻度の範囲とを比較してカウント値が範囲外にあるときは生成した乱数に問題があると判定する。ここで、前記カウントは所定の時間間隔でリセットされながら行うようにしてもよいし、また所定の時間間隔で乱数の生成レートを計測することで発生頻度の範囲を再導出するようにしてもよい。更に、前記発生頻度の範囲は、乱数の生成レートから得られる乱数頻度の期待値を基準にした所定の幅にすることができる。
【0008】
本発明の乱数生成検定装置は、物理現象に基づいて独立に発生する事象について所定の条件を満たす第1の時点から、前記所定の条件を満たす第2の時点までの時間間隔を計測する計時部と、前記計測された時間間隔を基にn種類の乱数を生成する乱数生成部と、前記乱数が生成されると各乱数ごとにその頻度をカウントするカウント部と、前記乱数の生成レートを基に各乱数の発生頻度の範囲を理論統計的に導出する閾値計算部と、n種類の乱数ごとに前記カウント値と前記発生頻度の範囲とを比較してカウント値が範囲外にあるときは生成した乱数に問題があると判定する判定部とを備える。ここで、前記カウントは所定の時間間隔でリセットされながら行うようにしてもよいし、また所定の時間間隔で乱数の生成レートを計測することで発生頻度の範囲を再導出するようにしてもよい。更に、前記発生頻度の範囲は、乱数の生成レートから得られる乱数頻度の期待値を基準にした所定の幅にすることができる。
【発明の効果】
【0009】
本発明によれば、物理現象に基づいて独立に発生する事象のうち所定の条件を満たす事象間の時間間隔の計測からn種類の乱数を生成し、その発生頻度を理論統計的に得られる発生頻度と比較して判定しているので、物理現象に基づいて生成された乱数が従う乱数特性そのものから直接的に乱数性の検定を行うことが可能となり、検定の適正さを向上させることができる。
また、所定の時間間隔で乱数の生成レートを計測し、これにより発生頻度の範囲を再導出するようにしているので、乱数に人為的な操作や乱数生成部の故障が生じれば遅滞無く異常信号を出力することが可能であり、従来と比較して迅速且つ厳密な乱数検定をすることができる。
【発明を実施するための最良の形態】
【0010】
以下に図面を参照しながら、本発明の実施形態について説明する。図1は、本発明の乱数生成検定方法を実現する乱数生成検定装置のブロック図であり、図2及び図3は、乱数検定の動作手順を示すフローチャートである。
上述したように、物理現象に基づいて独立に事象が発生するまでの時間間隔は指数分布になることが知られている。本実施形態では、抵抗等による熱雑音発生源から発生するパルスを用いた場合について説明する。指数分布の一般式は以下のように表される。

なお、λは単位時間当たりの平均乱数発生回数、tは時間間隔である。
【0011】
<乱数生成部10による乱数生成>
まず、乱数をどのように生成しているかについて説明する。初期化処理後(ステップS10)、パルス検出手段(不図示)が、熱雑音発生源から発生されるパルスのうち所定の閾値より大きいもの(以下、「乱数パルス」と称する。)を検出する処理1(ステップS11)が開始されると、次の乱数パルスが検出されるまでの時間間隔を計時手段(不図示)によって計測処理2(ステップS11)が実行される。前記計時手段は、乱数パルスよりも高い周波数のクロック信号を発生するクロック信号発生手段と、前記クロック信号のクロック回数をカウントするカウント手段とを含んで構成され、乱数パルス間でカウントされたクロック数を基に乱数パルス間の時間間隔(t)を計測する。前記カウント手段は有限桁のカウンタで本実施形態では2進数の8桁とし、カウンタ値(10進数)としては0〜255までの256種類となる。そのため、前の乱数パルスが検出されてから次の乱数パルスが検出されるまでの間はクロック回数のカウンタがインクリメントされ続けるが、カウンタが255に到達するとカウンタはリセットされて再び0からのインクリメントになる。したがって、次の乱数パルスが検出されるまでの時間間隔(t)が長くなるほどカウンタリセット回数が増えることになるが、いずれにしても1つの時間間隔(t)が計測されれば0〜255のうちの何れかの1つの値を決定することができる。乱数生成部10は、この値を乱数値として取り出すことを所定のタイマ設定時間が経過するまで繰り返す(ステップS11,13,15)。なお、取り出された乱数値は真正な乱数であるか否かについて検定前の未確定な値であるので、以下では真正な乱数値と区別するために「推定乱数値」と呼ぶことにする。
【0012】
<乱数検定>
次に、生成された推定乱数値を検定する動作について説明する。本実施形態の乱数検定方法は、発生する乱数パルスから生成された推定乱数値それぞれについてその発生頻度の期待値を理論的に計算しておき、この期待値に所定の上下幅をもたせた範囲から逸脱する推定乱数値の頻度がある場合は真正な乱数が生成されていないと判断するものである。以下、その詳細な内容を示す。
【0013】
上述したように、1つの時間間隔(t)が計測されると0〜255のうちの何れかの1つの推定乱数値が決定されるので、各推定乱数値が生成される度にその頻度を記録することを繰り返す。具体的には、256個の桁を備えた発生回数カウンタ8を用意し、各推定乱数値が生成されると対応する桁の数をインクリメントしていけばよい(ステップS14)。
また、乱数検定部20は、発生回数カウンタのインクリメント処理の他に、各推定乱数値の発生頻度の期待値を得るために乱数パルス生成レート(λ)の計測3を行う(ステップS12)。乱数パルス間の時間間隔(t)が指数分布に従うので、時間間隔(t)の期待値E(t)は理論的には1/λになることが知られている。つまり、乱数パルスが単位時間あたりどのくらい生成されたかを示す乱数パルス生成レート(λ)が変動すれば、時間間隔の期待値E(t)が変化するので、その結果、各推定乱数値の発生頻度の理論期待値E(r)も変化する。本発明の乱数検定方法は、この推定乱数値の発生頻度の期待値E(r)からの逸脱度を所定時間ごとにチェックすることを特徴とするので、タイマ5によって所定の監視時間(例えば、数ミリ秒)が経過するごとにタイマ処理(ステップS16)に移行し、乱数生成・検定の全体動作を終了させるまでステップS11に戻って繰り返す。
【0014】
次に、タイマ処理(ステップS16)について図2及び図3を参照しながら説明する。タイマ5が前記所定の監視時間を経過するとタイマ処理動作に入り、乱数検定部20は、ステップS12で計測された乱数パルス生成レート(λ)から推定乱数値の発生頻度の期待値E(r)の計算4を行う(ステップS18)。次に、乱数検定部20は、期待値E(r)に対する検定区間、即ち、下限閾値の計算6と上限閾値の計算7を行う(ステップS19)。この下限閾値と上限閾値、即ち検定幅をどのように設定すべきかが問題となるが、各推定乱数値の期待値E(r)がどの程度ばらつくかは正規分布に従うとみなしてよいので、E(r)に対して±υσ(σ:ばらつきの程度)を検定幅にすればよい。これは、パルス検出手段によって検出された実際の乱数パルス間の時間間隔(t)は、当然ながら期待値E(t)を中心にして統計的な変動を含んでばらつき、それが例えば±7σから外れてしまうことは通常の稼働状態に設定された熱雑音発生源の抵抗器であれば極めて稀にしか起こり得ないことに関連する。つまり、乱数パルスの発生間隔が±7σから外れてしまうものがあれば、即ち、発生頻度が±7σから外れる推定乱数値が生じるならば、それは乱数発生において人為的な操作がなされたか、又は乱数発生器に故障が生じて正常な稼働状態になっていると考えるのが合理的となる。
そこで、推定乱数値の発生頻度の下限閾値をH-(r)、同じく上限閾値をH+(r)とすれば、以下のようになる。

υ値はばらつき許容レベルに対応し、その値が大きくなる程、検定幅が広くなることを意味する。したがって、±7σでの検定幅であれば異常値と判断されなくても、±3σの検定幅では異常値と判断されることがある。
【0015】
本実施形態では、下限閾値H-(r)〜上限閾値H+(r)の検定幅に推定乱数値が存在しているか否かの判断は、乱数検定部20における比較器11(x),12(x)(x=0,…255)が行う。上述したように、乱数生成部で生成された各推定乱数値は0〜255までの何れか1つの値に対応し、その発生頻度が発生回数カウンタでインクリメント処理し記憶されている。また、ステップS19で下限閾値H-(r)と上限閾値H+(r)が計算されているので、各推定乱数値(0〜255)の下限発生頻度を下限メモリ9に、上限発生頻度を上限メモリ10に設定することができる(ステップS20)。これにより、比較器11(x)は、発生回数カウンタ8と下限閾値メモリ9との対応する桁の値の大小関係を調べて(ステップS21)、発生カウンタ8のカウント値が下限閾値メモリ9に設定されているカウント値よりも小さいときは論理和回路13に信号「1」、そうでないときは信号「0」を出力する。同様に、比較器12(x)は、発生回数カウンタ8と上限閾値メモリ10との対応する桁の値の大小関係を調べて(ステップS21)、発生カウンタ8のカウント値が上限閾値メモリ10に設定されているカウント値よりも大きいときは論理和回路14に信号「1」、そうでないときは信号「0」を出力する。
【0016】
論理和回路13,14は、0〜255の各桁の比較から出力された信号の論理和演算をし、その結果、1つでも信号「1」が出力されているときは、定義した検定幅に推定乱数値が存在していないことを示す信号「1」を論理和回路15に出力する(ステップS23)。更に、論理和回路15は論理和回路13,14からの信号の論理和演算をして、出力信号が「1」のときは、乱数生成に何らかの問題があるとして警告(異常)信号を発する(ステップS24)。そして、発生回数カウンタ8の各桁がリセットされて(ステップS25)、ステップS16のタイマ処理を終了させる。
【0017】
特に、本実施形態は、タイマ5で設定される所定の監視時間ごとに、乱数パルスの発生レート(λ)を計測し、これにより推定乱数値の頻度期待値E(r)が更新されて上限閾値及び下限閾値を再計算して、下限閾値メモリ9及び上限閾値メモリ10に設定すべき各桁値を変更している。そして、発生回数カウンタ8でインクリメントされているカウント値も前記監視時間ごとにリセットされ、カウンタの各桁の比較処理が実行される構成である。これにより、例えば、熱雑音発生源である抵抗器の周辺環境が変わって乱数パルスの発生頻度が高くなれば上限閾値及び下限閾値の上昇修正がなされ、推定乱数値が検定幅内に存在しているか否かを前記監視時間ごとに正確にチェックすることができるという効果を有する。したがって、タイマ5での監視時間を数ミリ秒に設定すれば瞬時に検定結果を出すことが可能である。
なお、前記監視時間は、不正行為や故障を確実に検出する目的からするとできるだけ短時間であることが要求される。しかし、極端に短時間にすると計時手段によるクロック信号のクロック回数が殆ど積算されていないカウント数について上限閾値及び下限閾値との比較がなされてしまい、異常乱数値を精度よく検出することができなくなってしまう。そこで、本実施形態では、例えば数ミリ秒でタイマー設定することにしている。
【0018】
図4は、上述した本実施形態の乱数検定方法を示すイメージ図である。図3中に示した黒丸は、各推定乱数値0〜255(横軸)に対する発生回数、即ち頻度をプロットしてある。ただし、縦軸は、対数目盛りであることに留意されたい。
指数関数f(t)の傾きを得るには、指数関数f(t)=λe-λtを値tで微分して求めればよいが、上述したように発生回数が対数目盛りであるためg(t)=logf(t)として、g(t)を値tで微分して求める。
d/dt g(t)=d/dt logλe-λt=d/dt (logλ) +d/dt (loge-λt)=−λより、発生頻度を対数表示したグラフは傾き−λの直線となり、図3の実線で示す期待値E(r)の直線に対応している。また、この期待値直線を挟むようにして示された2つの破線は、期待値E(r)に対して±υσの幅を有する上限閾値線及び下限閾値線を表している。期待値直線から上限閾値線又は下限閾値線までの距離は、|υσ|となっている。グラフの横軸は各推定乱数値を表すので本実施形態では0〜255の値の何れかである。したがって、所定の監視時間内に乱数値0が何回出現したか、乱数値1が何回出現したか、…乱数値255が何回出現したかを黒丸でプロットしていることになる。
【0019】
いま、例えば、検定幅が非常に狭く設定されているとして、図4に示すように黒丸の殆どは、上限閾値直線H+(r)と下限閾値直線H-(r)との間に存在しているものの、1つの黒丸のみが検定幅内に存在していない状況が発生したとする。検定幅が狭ければ、生成された推定乱数値の中にはこの幅から逸脱してしまうものがあるかもしれない。しかし、検定幅を適切な広さに設定したのにもかかわらず逸脱するような値が生じたとすれば、これは乱数生成部10で生成された推定乱数値が理論的に求めた期待値どおりに従っておらず、真正な乱数値として不適当であると評価することが妥当となる。この場合、逸脱する黒丸の数が1つであっても、不真正な乱数生成であり、異常値として警告信号が発せられることになる。±7σなどの十分な幅に設定した検定幅であれば、各推定乱数値(0〜255)すべての出現頻度が検定幅内になければ人為的な操作が付加されるか又は乱数生成器の故障であるとみなすのが合理的だからである。したがって、本発明の乱数生成検定方法は、各推定乱数値のなかでその発生回数が検定幅を逸脱するものが1つでもあれば異常な乱数生成であるいう判断が可能であり、発生頻度を調べる対象としての推定乱数値の数が少なくても検定を行うことができるという特徴がある。
【0020】
また、本実施形態の乱数生成検定方法は、真正な自然乱数であればその乱数の発生する時間間隔(t)が指数分布に従うはずであるから、これより理論的に得られる乱数発生頻度の期待値からのばらつき、即ち、逸脱度を監視して乱数検定を行う構成である。したがって、推定乱数値に対して例えば排他的論理和演算などの任意の演算加工を一切施すことがなく、指数分布の特性からの直接的な検定方法であることから、乱数としての真正さを確実に検定することができる。
【0021】
(応用例について)
本実施形態では、カウント手段を8桁として設定したために推定乱数値として取り得る値が0〜255となり、その結果、図1の発生回数カウンタが0〜255桁、そして図3にプロットした黒丸が256個の各乱数値の発生頻度数を表すことになったのであるが、任意の桁数を設定できることはいうまでもない。
また、物理現象の事象として抵抗等の熱雑音発生源からのパルスによって説明したが特に限定する意図を含んでいるものではない。
また、上限閾値直線H+(r)と下限閾値直線H-(r)は、期待値E(r)からの±υσの幅として計算するように構成したが、物理現象の事象の特徴や特性、更には環境等から、乱数の発生頻度が期待値E(r)より上限閾値直線H+(r)のみ、又は期待値E(r)より下限閾値直線H-(r)のみで発生する場合は、これに応じて閾値計算を設定すればよい。
【図面の簡単な説明】
【0022】
【図1】本発明の乱数生成検定方法を実現する装置のブロック構成図である。
【図2】本発明の乱数生成検定方法の一本実施形態としての検定動作手順を示すフローチャートである。
【図3】本発明の乱数生成検定方法の一本実施形態としての検定動作手順を示すフローチャートであり、特に、タイマ処理に関するものである。
【図4】本発明の乱数生成検定方法を示すイメージ図である。
【符号の説明】
【0023】
1 乱数パルス検出部
2 時間間隔計測部
3 乱数パルス生成レート(λ)の計測部
4 期待値E(t)の計算部
5 タイマー
6 下限閾値計算部
7 上限閾値計算部
8 発生回数カウンタ
9 下限閾値メモリ
10 上限閾値メモリ
11、12 比較器
13、14、15 論理和演算回路

【特許請求の範囲】
【請求項1】
物理現象に基づいて独立に発生する事象について所定の条件を満たす第1の時点から、前記所定の条件を満たす第2の時点までの時間間隔を計測する計時処理と、
前記計時処理によって計測された時間間隔を基にn種類の乱数を生成する乱数生成処理と、
前記乱数生成処理によって乱数が生成されると各乱数ごとにその頻度をカウントするカウント処理と、
前記乱数生成処理によって生成される乱数の生成レートを基に、前記各乱数が発生する頻度の範囲を理論統計的に導出する閾値計算処理と、
n種類の乱数ごとに、前記カウント処理でカウントされた値と前記閾値計算処理によって導出された発生頻度の範囲とを比較し、前記カウント値が範囲外にあるときは前記乱数に問題があると判定する処理とを、含む乱数生成検定方法。
【請求項2】
所定の時間間隔で前記カウント処理におけるカウントをリセットすることを特徴とする請求項1に記載の方法。
【請求項3】
所定の時間間隔で前記乱数の生成レートを計測し、前記発生頻度の範囲を再導出することを特徴とする請求項1又は2に記載の方法。
【請求項4】
前記発生頻度の範囲は、前記乱数の生成レートから得られる乱数頻度の期待値を基準にした所定の幅であることを特徴とする請求項1〜3の何れか1項に記載の方法。
【請求項5】
物理現象に基づいて独立に発生する事象について所定の条件を満たす第1の時点から、前記所定の条件を満たす第2の時点までの時間間隔を計測する計時部と、
前記計時部によって計測された時間間隔を基にn種類の乱数を生成する乱数生成部と、
前記乱数生成部によって乱数が生成されると各乱数ごとにその頻度をカウントするカウント部と、
前記乱数生成部によって生成される乱数の生成レートを基に、前記各乱数が発生する頻度の範囲を理論統計的に導出する閾値計算部と、
n種類の乱数ごとに、前記カウント部でカウントされた値と前記閾値計算部によって導出された発生頻度の範囲とを比較し、前記カウント値が範囲外にあるときは前記乱数に問題があると判定する判定部とを、備えた乱数生成検定装置。
【請求項6】
所定の時間間隔で前記カウント部におけるカウントをリセットすることを特徴とする請求項5に記載の装置。
【請求項7】
所定の時間間隔で前記乱数の生成レートを計測し、前記発生頻度の範囲を再導出することを特徴とする請求項5又は6に記載の装置。
【請求項8】
前記発生頻度の範囲は、前記乱数の生成レートから得られる乱数頻度の期待値を基準にした所定の幅であることを特徴とする請求項5〜7の何れか1項に記載の装置。

【図1】
image rotate

【図2】
image rotate

【図3】
image rotate

【図4】
image rotate


【公開番号】特開2007−319465(P2007−319465A)
【公開日】平成19年12月13日(2007.12.13)
【国際特許分類】
【出願番号】特願2006−153537(P2006−153537)
【出願日】平成18年6月1日(2006.6.1)
【出願人】(591107481)株式会社エルイーテック (37)
【出願人】(501462686)株式会社アイ・エイ・エス総合研究所 (4)
【Fターム(参考)】