(57)【要約】本発明は、乱数生成器によって生成される乱数をリアルタイムでテストするための方法及び装置である。この乱数生成器によって生成されたランダムビットのストリームは、所定のビットブロックに分割される。次に、これらのブロックは、ギャップ長計算の演算を受け、これにより、ギャップがどの特定の範囲に属するかについて決定される。次に、これらのギャップ長値は、指数カウント演算を適用され、種々のビットパターン及びギャップ範囲についてギャップ頻度値が得られて更新される。その後、この更新されたギャップ頻度値は、少なくとも１つの所定の許容範囲と比較され、前記ギャップ頻度値の少なくとも１つが、所定の回数よりも多く反復して前記所定の許容範囲から外れたら、前記生成されたランダムシーケンスは十分にランダムでないと決定される。
2005523511.tif 000002
【特許請求の範囲】
【請求項１】
乱数ストリームのランダム性をテストするための方法において、
−ランダムバイナリビットの連続ストリームを生成させるステップと、
−前記ランダムバイナリビットを所定のビットブロックに分割するステップと、
−前記各所定のビットブロックを指数ギャップ頻度計算（Ａ）に適用し、少なくとも２つの同一のビットブロック間のギャップ頻度値を計算して更新するステップと、
−前記指数ギャップ頻度計算の出力を所定の許容範囲と比較することによって、前記生成されたランダムビットが十分にランダムであるかどうか決定するステップと、
を有する方法。
【請求項２】
請求項１に記載の方法において、前記各所定のビットブロックについての前記指数ギャップ頻度計算（A）は、式：
Anew= α・Aold + b
によって更新され、ここで、αは０と１との間であり（０＜α＜１）、前記少なくとも２つの同一のビットブロックが発生したらｂ＝１であり、発生しなければｂ＝０である、方法。
【請求項３】
請求項１に記載の方法において、更に、前記ギャップ頻度値の少なくとも１つが、所定の回数よりも多く反復して前記所定の許容範囲から外れたら、前記生成されたランダムビットは十分にランダムでないと決定するステップを有する方法。
【請求項４】
請求項１に記載の方法において、更に、前記ギャップ頻度値の少なくとも１つが、所定の回数よりも多く反復して前記所定の許容範囲から外れたら、前記生成されたランダムビットは十分にランダムでないことを通知するステップを有する方法。
【請求項５】
請求項１に記載の方法において、更に、前記ギャップ頻度値の少なくとも１つが、所定の回数よりも多く反復して前記所定の許容範囲から外れたら、ランダムビットの新しい組を生成させるステップを有する方法。
【請求項６】
請求項１に記載の方法において、更に、前記ギャップ頻度値の少なくとも１つが、所定の回数よりも多く反復して前記所定の許容範囲から外れたら、前記生成されたランダムビットを次のアプリケーション用として拒絶するステップを有する方法。
【請求項７】
乱数生成器によって生成される乱数ストリームをテストするための方法において、
（ａ）前記ランダムバイナリビットを所定のビットブロックに分割するステップと、
（ｂ）前記分割されたランダムビットをギャップ長計算に適用するステップと、
（ｃ）前記ギャップ長計算の出力を指数平均カウントに適用し、少なくとも２つの同一のビットブロック間のギャップ頻度値を得て更新するステップと、
（ｄ）前記ギャップ頻度値を所定の許容範囲と比較するステップと、
（ｅ）前記ギャップ頻度値の少なくとも１つが、所定の回数よりも多く反復して前記所定の許容範囲から外れたかどうか決定するステップと、
を有する方法。
【請求項８】
請求項７に記載の方法において、前記各所定のビットブロックについての前記指数平均は、式：
Anew= α・Aold + b
によって更新され、ここで、αは０と１との間であり（０＜α＜１）、前記少なくとも２つの同一のビットブロックが発生したらｂ＝１であり、発生しなければｂ＝０である、方法。
【請求項９】
請求項７に記載の方法において、更に、前記ギャップ頻度値の少なくとも１つが、所定の回数よりも多く反復して前記所定の許容範囲から外れたら、前記生成されたランダムビットは十分にランダムでないと決定するステップを有する方法。
【請求項１０】
請求項７に記載の方法において、更に、前記各ギャップ頻度値が前記所定の許容範囲内に入れば、前記ギャップ頻度値の少なくとも１つが前記所定の許容範囲から外れるまで前記ステップ（ａ）〜（ｅ）を繰り返すステップを有する方法。
【請求項１１】
請求項１０に記載の方法において、更に、前記ステップ（ａ）〜（ｅ）が所定の回数よりも多く繰り返されたら、十分にランダムでない数が生成されていることを通知するステップを有する方法。
【請求項１２】
請求項１０に記載の方法において、更に、前記ステップ（ａ）〜（ｅ）が所定の回数よりも多く繰り返されたら、ランダムビットの新しい組を生成させるステップを有する方法。
【請求項１３】
ランダム性をテストするためのシステムにおいて、
−バイナリビットを有するランダムシーケンスを生成させるための乱数生成器と、
−前記生成されたランダムシーケンスが十分にランダムかどうか指数ギャップ頻度演算に基づいて検出するための検出器と、
−前記指数ギャップ頻度演算の結果に基づいて、次のアプリケーションのための前記生成されたランダムシーケンスの流れを制御するスイッチであって、前記ランダムシーケンスは、所定のビットブロックに分割され、前記指数ギャップ頻度演算を受け、これにより少なくとも２つの同一のビットブロック間のギャップ頻度値が得られて更新され、前記ギャップ頻度値の少なくとも１つが、所定の回数よりも多く反復して前記所定の許容範囲から外れたら、前記生成されたランダムシーケンスは十分にランダムでないと決定するスイッチと、
を有するシステム。
【請求項１４】
請求項１３に記載のシステムにおいて、更に、前記ギャップ頻度値の少なくとも１つが前記所定の回数よりも多く反復して前記所定の許容範囲から外れたら、前記生成されたランダムシーケンスが十分にランダムでないという警報信号を送信するための手段を有するシステム。
【請求項１５】
請求項１３に記載のシステムにおいて、更に、前記ギャップ頻度値の少なくとも１つが、所定の回数よりも多く反復して前記所定の許容範囲から外れたら、ランダムビットの新しい組を生成させる手段を有するシステム。
【請求項１６】
命令シーケンスを表すデータが記憶された機械読取り可能な媒体において、前記命令シーケンスは、プロセッサによって実行されたら当該プロセッサに、
−ランダムバイナリビットの連続ストリームを生成させるステップと、
−前記ランダムバイナリビットを所定のビットブロックに分割するステップと、
−前記各所定のビットブロックを指数ギャップ頻度計算に適用し、少なくとも２つの同一のビットブロック間のギャップ頻度値を計算して更新するステップと、
−前記指数ギャップ頻度計算の出力を所定の許容範囲と比較することによって、前記生成されたランダムビットが十分にランダムであるかどうか決定するステップと、
を実行させる、媒体。
【請求項１７】
請求項１６に記載の記憶媒体において、前記ギャップ頻度値の少なくとも１つが前記所定の許容範囲から外れたら、前記生成された乱数は十分にランダムでないと決定される、記憶媒体。
【請求項１８】
請求項１６に記載の記憶媒体において、前記プロセッサは、更に、前記ギャップ頻度値の少なくとも１つが前記所定の許容範囲から外れたら、ランダムビットの新しい組を処理するように動作可能である、記憶媒体。
【請求項１９】
請求項１６に記載の記憶媒体において、前記プロセッサは、更に、前記ギャップ頻度値の少なくとも１つが、所定の回数よりも多く反復して前記所定の許容範囲から外れたら、前記生成されたランダムビットを次のアプリケーション用として拒絶するように動作可能である、記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、乱数生成器に関し、特に、乱数生成器によって生成される乱数が十分にランダムかどうかをテストする分野に関する。
【背景技術】
【０００２】
真にランダムなシーケンスは、実際のアプリケーションで生成することは困難である。例えば、一般的に、乱数生成器が一連の１及び０を一定期間生成させていると、乱数生成器のハードウェアコンポーネントにおいて熱が発生する。一部の状況においては、１ビットを生成させることは、０ビットを生成させることよりも多くの電力を消費しうる。１ビットの長いシーケンスが発生すると、ランダム生成器の電気回路は熱くなる傾向がある。従って、回路が熱いときに１ビットを生成させると、回路は「ラッチアップ」する、その結果、回路は主に１ビットを生成させ、０ビットを滅多に生成させなくなる。セキュリティが重要であるアプリケーションに乱数が用いられる場合、上述の偏った０／１頻度のエラーは破壊的な結果を生じる。
【０００３】
従って、ランダム性テストを実行するときには、ハードウェアの改竄（hardware tampering）及び部品の故障の両方の検出が必要である。従来のランダム性テストは、生成された乱数シーケンスについての大量の統計的テスト（例えばカイ二乗テスト及びデルタテスト等）を通じて実行される。しかし、このようなテストは、大量の計算処理能力を必要とするのでリアルタイムで実行するのは非常に高価である。
【発明の開示】
【発明が解決しようとする課題】
【０００４】
本発明は、上記の問題を解決し、更に、生成された乱数が十分にランダムであることを保証するオンラインランダム性テストを提供する方法及び装置を提供することによって追加の利点を提供する。
【課題を解決するための手段】
【０００５】
本発明の１つの側面によれば、乱数ストリームのランダム性をテストするための方法は、ランダムバイナリビットの連続ストリームを生成させるステップと、前記ランダムバイナリビットを所定のビットブロックに分割するステップと、前記各所定のビットブロックを指数ギャップ頻度計算（exponential-gap-frequency calculation）（Ａ）に適用し、少なくとも２つの同一のビットブロック間のギャップ頻度値を計算して更新するステップと、前記指数ギャップ頻度計算の出力を所定の許容範囲と比較することによって、前記生成されたランダムビットが十分にランダムであるかどうか決定するステップとを有する。本方法は、更に、前記ギャップ頻度値の少なくとも１つが、所定の回数よりも多く反復して前記所定の許容範囲から外れたら、前記生成されたランダムビットは十分にランダムでないと決定するステップと、前記ギャップ頻度値の少なくとも１つが、所定の回数よりも多く反復して前記所定の許容範囲から外れたら、前記生成されたランダムビットは十分にランダムでないことを通知するステップと、前記ギャップ頻度値の少なくとも１つが、所定の回数よりも多く反復して前記所定の許容範囲から外れたら、ランダムビットの新しい組を生成させるステップとを有する。
【０００６】
本発明の他の側面によれば、乱数生成器によって生成される乱数ストリームをテストするための方法は、前記ランダムバイナリビットを所定のビットブロックに分割するステップと、前記分割されたランダムビットをギャップ長計算に適用するステップと、前記ギャップ長計算の出力を指数平均カウント（exponential averaging counting）に適用し、少なくとも２つの同一のビットブロック間のギャップ頻度値を得て更新するステップと、前記ギャップ頻度値を所定の許容範囲と比較するステップと、前記ギャップ頻度値の少なくとも１つが、所定の回数よりも多く反復して前記所定の許容範囲から外れたかどうか決定するステップとを有する。
【０００７】
本発明の他の側面によれば、ランダム性をテストするためのシステムは、バイナリビットを有するランダムシーケンスを生成させるための乱数生成器と、前記生成されたランダムシーケンスが十分にランダムかどうか指数ギャップ頻度演算に基づいて検出するための検出器と、前記指数ギャップ頻度演算の結果に基づいて、次のアプリケーションのための前記生成されたランダムシーケンスの流れを制御するスイッチであって、前記ランダムシーケンスは、所定のビットブロックに分割され、前記指数ギャップ頻度演算を受け、これにより少なくとも２つの同一のビットブロック間のギャップ頻度値が得られて更新され、前記ギャップ頻度値の少なくとも１つが、所定の回数よりも多く反復して前記所定の許容範囲から外れたら、前記生成されたランダムシーケンスは十分にランダムでないと決定するスイッチとを有する。このシステムは、更に、前記ギャップ頻度値の少なくとも１つが前記所定の回数よりも多く反復して前記所定の許容範囲から外れたら、前記生成されたランダムシーケンスが十分にランダムでないという警報信号を送信するための手段と、前記ギャップ頻度値の少なくとも１つが、所定の回数よりも多く反復して前記所定の許容範囲から外れたら、ランダムビットの新しい組を生成させる手段とを有する。
【０００８】
本発明の更に他の側面は、本発明が、特定のアプリケーションで所望されるのに応じて、ハードウェア、ソフトウェア又はハードウェアとソフトウェアとの組合せで実現されることができることである。
【０００９】
更に、本発明は、単純で、信頼性があって安価な実施態様で実現されることができる。
【発明を実施するための最良の形態】
【００１０】
これらの及び他の利点は、添付の図面と共に以下の詳細な説明を読むことによって当業者には明らかになる。
【００１１】
以下の説明においては、制限ではなく説明のために、特定のアーキテクチャ、インタフェース、技術等の具体的詳細が、本発明の完全な理解を与えるために示される。しかし、当業者には、本発明が、これらの具体的詳細からは逸脱する他の実施例においても実行されることができることは明らかである。単純性及び明快さのために、周知の装置、回路及び方法の詳細な説明は、不必要な細部により本発明の説明を不明瞭にしないために省略される。
【００１２】
図１は、本発明の１つの実施例による乱数生成システム１０の簡略ブロック図を示す。システム１０は、一連の乱数を生成させるための乱数生成器（ＲＧ）１２と、検出器１４と、スイッチ１６とを含む。この開示におけるＲＧ１２は、バイナリビットのシーケンス又はあらゆる従来の又は従来とは異なった態様で所望のランダム性を含む他のあらゆる形式のシーケンスに変換されることができる信号を作成するあらゆるデバイスを意味する。検出器１４は、生成された乱数が本当にランダムなシーケンスであるかどうかを所定の基準（後に説明される）に従って検出する。スイッチ１６は、暗号システム、オーディオ又はビデオノイズ生成器、コンピュータプログラム又は他のデバイス及び方法への入力を表してもよい。
【００１３】
動作中、乱数が乱数生成器１２によって生成されると、検出器１４は、生成された乱数が真にランダムシーケンスを形成するかどうか検出する。生成された乱数が、特定の許容範囲内で十分にランダムであると決定されれば、スイッチ１６は、生成された乱数が、あらゆる適切な次のアプリケーション、即ち、あらゆる回路、システム、プロセス、ギャンブルアプリケーション、シミュレーション、統計的サンプリング、Diffie-Hellmanキー交換、又は、ＲＧ１２によって供給される乱数を用いる同種のアプリケーション等に転送されることを許可する。従って、生成された乱数が十分にランダムでないと検出器１４によって判断されたら、スイッチ１６は生成された乱数の流れを止めることができる。別の実施例では、生成されたランダムシーケンスが十分にランダムでないと決定されたら、乱数の新しい組が乱数生成器１２によって生成されてもよい。
【００１４】
ここで、図２及び３を参照して、生成された乱数が充分にランダムであるかどうか決定することについて詳細に説明される。
【００１５】
図２を参照する。乱数ストリームがＲＧ１２によって生成されると、生成された乱数はｋビットの所定のブロックに分割される。新しいランダムビットが生成されるたびに、この新しいビットは、ｋビットが得られるまで、前のビットのシーケンスに追加される。説明の便宜上、ｋビットのユニットとして６ビットの群が説明されていることに注意されたい。しかし、本発明が、あらゆる正の整数のｋビットをサポートすることができることが理解されるべきである。従って、図面における６ビットのグループ化は、本発明の範囲に制限を課さない。
【００１６】
本実施例において、ｋビットの分割されたブロックの各々は、検出器１４によって分析され、同じｋビットブロックの前の発生からの距離（ギャップと呼ばれる）が、全ての分割されたブロックについて決定される。本発明のキーとなる原理は、同一のｋビットパターン間の特定のギャップ長が現れる平均回数が知られているということである。一連の全ての可能なギャップ長が、適当な区間に区切られれば、計算されたギャップ長が各区間に入る回数は、ほぼ同じでなければならない。可能なｋビットブロックのそれぞれ及びギャップ長区間のそれぞれのためにアキュムレータ（Ａ）が提供され、新しいｋビットブロックが生成されて同じｋビットブロックの前の発生からのギャップが計算されるたびに、ブロックのｋビットのバイナリ表示及びこのギャップの属する区間の番号がそれぞれのアキュムレータをインデックスするのに用いられる。例えば、図２に示されるように、パターン「００００００」は、第１のブロック及び第４のブロックにおいて発生するので、このパターンに対応するギャップは３である。パターン「００００１０」は、第３及び第５のブロックにおいて発生するので、このパターンに対応するギャップは２である。アキュムレータは、特定のビットブロックの特定のギャップがギャップ長の所定の区間に入る平均回数（頻度）の情報を常に得て、各ブロックについて、ギャップが所定の範囲内にある回数を分析することによって、生成された乱数が十分にランダムであるかどうかが決定される。この回数は、全ての可能なｋビットブロック及びギャップ範囲について概ね同じでなければならない。
【００１７】
本発明はランダムシーケンスをテストするのにリアルタイムで適用可能であるので、全てのアキュムレータは更新されなければならないことに注意されたい。よって、古い頻度値は、減少した影響を与える又は全く影響を与えない。即ち、ランダムシーケンスの統計的品質を評価するためのテストは連続的に実行され、従って、アキュムレータは、オーバーフローを回避するために周期的にクリアされなければならない。本発明の技術に従って実行されることができる種々のカウント方法があるが、下記のように、好適には、頻度カウント演算の間、指数平均が用いられる。
【００１８】
特定のギャップ範囲の平均発生回数即ち頻度を得るためにアキュムレータＡが用いられれば、ｋ個のランダムビットが発生するたびに、０〜１の係数αがアキュムレータ（Ａｏｌｄ）に乗算され、インジケータ値ｂが加算される。即ち、
Anew=α・Aold+b
ここで、ｋビットブロック及びギャップの属する範囲が、使用されているアキュムレータに対応すれば、ｂは１であり、そうでなければｂ＝０である。指数平均アキュムレータＡは、可能なｂｎパターンのそれぞれ（０≦ｎ＜２ｋ）、及び、可能なギャップ範囲の可能な区間のそれぞれについて最初に初期化されることに注意されたい。初期化値は、予め割り当てられた値によってオペレータによって初期化される。有用な平均化効果を得るために、αの値は、１に近くなるように選択される（α=1-1/n、n >>1）。この場合、
【数１】
2005523511.tif 000003
であり、重みが半減された平均された値の半減期は、
【数２】
2005523511.tif 000004
である。ｎステップの後、最も古い平均された値の重みは、
【数３】
2005523511.tif 000005
になる。ここで、ｅは自然対数の底（オイラー定数）であり、従って、項ｎは、平均された値の「自然寿命（natural life）」になる。全ての平均された値が１であれば、アキュムレータは、1+α+α2+…=1/(1-α)=nを含み、全ての平均された値が０であれば、アキュムレータ値は０である。指数平均の期待値が個々の値の期待値の指数平均であることに注意されたい。平均された値が均一分散されたバイナリビットであったら、指数平均の期待値は、1/2+1/2α+1/2α2+…=n/2となる。
【００１９】
上記の通りに、アキュムレータは特定の係数α（０＜α＜１）によって減少させられるので、指数平均はカウンタをクリアする役目を果たす。従って、アキュムレータは、動作モードの最中、決して大きくなり過ぎない。指数平均が各アキュムレータについて実行されると、各指数平均の値は所定の許容範囲と比較される。何れかのアキュムレータの値が指数平均カウントの最中に所定の範囲から外れたら、本発明の実施例によれば、生成された乱数は十分にランダムでないと推測される。ここで、テストが反復して失敗したらユーザに通知するための閾値がセットされてもよい。厳密な許容範囲の境界は、理想的なギャップ分布が得られる既知の良い乱数のソースでの大規模なシミュレーションから得られるデータに基づいて選択的に調整されることができる。このようなランダムシーケンスは、市販されており、例えば、「www.fourmilab.ch/hotbits」及び「lavarand.sgi.com」を含む種々のウェブソースからダウンロードされることができる。従って、生成されたランダムシーケンスが十分にランダムであるとみなされるかどうかに関する選択が異なった感度でできるように、テストにおいて用いられる実際の範囲は、オペレータによって選択的にセットされる。別の実施例では、各アキュムレータに異なった許容範囲が割り当てられることができる。
【００２０】
図３は、本発明によるランダムシーケンスの統計的品質をテストするための動作ステップを示すフローチャートである。長方形の要素は、コンピュータソフトウェア命令を示す一方、ダイヤモンド形の要素は、長方形のブロックにより表されるコンピュータソフトウェア命令の実行に影響を及ぼすコンピュータソフトウェア命令を表す。代替的に、処理及び決定ブロックは、デジタル信号プロセッサ回路又は特定用途向けＩＣ（ＡＳＩＣ）等の機能的に等価な回路によって実行されるステップを表す。ループ及び変数の初期化並びに一時的変数の使用等、多くのルーチンプログラム要素が示されないことに注意されたい。当業者には、ここで別段示されていなければ、具体的なステップのシーケンスは説明のためのみであり、本発明の精神から逸脱することなく変更がなされることが可能であることが理解される。
【００２１】
図３に示すように、ランダム性テストは、ステップ１００の乱数生成器１２によるランダムバイナリビットの連続ストリームの発生とともに開始される。ステップ１２０において、生成された乱数はブロックビットの組に分割される。次に、ブロックビットの組は、ギャップ頻度計算を受け、ここで、特定の長さの同一のビットパターン間のギャップの分布が計算される。同じビットパターン間のギャップが見つけられるたびに、ステップ１４０で、指数ギャップ頻度値の組が各アキュムレータにおいて更新される。ここで、古いギャップ頻度値が減少した効果を有するように、全ての前の指数ギャップ頻度値は、係数α（０＜α＜１）によって低減されてから、１がｋビットブロック及びギャップが属する範囲に対応するアキュムレータに加算される。指数平均演算を受けた後、ステップ１６０で、ギャップ頻度値は所定の許容範囲又は複数の所定の許容範囲のそれぞれと比較される。各アキュムレータの値の何れかが所定の許容範囲外であれば、ステップ２００において、非ランダムパターンが検出されたと決定され、カウンタが１増加される。そうでなければ、ステップ１８０でカウンタはリセットされ、乱数を処理するステップ１００に戻る。ステップ２２０において、カウンタの値が閾値より大きければ、ステップ２４０において、生成された乱数が十分にランダムでないことの通知が送信される。代替的に、スイッチ１６が停止され、次のアプリケーションのための乱数の流れを止めることができる。次に、生成された乱数は廃棄されることができ、新しい乱数を発生させるプロセス全体が開始されることができる。ステップ２２０でカウンタの値が閾値を越えなければ、乱数を発生させるプロセスは繰り返される。
【００２２】
上述の種々のステップは、これらステップをアプリケーションプログラムに組み込まれた機能にプログラムすることに実行されることができ、当分野で通常の技術を有するプログラマは、言語（例えばＣ、Ｖｉｓｕａｌ  Ｂａｓｉｃ、Ｊａｖａ、Ｐｅｒｌ、Ｃ＋＋等）の通例のプログラミング技法を用いてこれらを実現することができる。１つの実施例においては、図３において説明される方法は、次のように（Ｃプログラミング言語を用いて）構成されてもよい。説明を簡単にするため、浮動小数点演算を用いるテストが実行された。
付録：ＭＳ  Ｖｉｓｕａｌ  Ｃコード
【表１】
2005523511.tif 000006
2005523511.tif 000007
2005523511.tif 000008
【００２３】
本発明の好適な実施例が図示され説明されたが、当業者には、本発明の真の範囲から逸脱することなく種々の変形及び修正がなされることができ、その要素は等価物により置換されることができるということは理解されるであろう。加えて、本発明の中心範囲から逸脱することなく、多くの修正例が特定の状況及び本発明の教示に適合するために作られることができる。従って、本発明は、本発明を実行するために最良の形態であると考えられて開示された特定の実施例に制限されるのではなく、添付の請求項の範囲内の全ての実施例を含むことが意図される。
【図面の簡単な説明】
【００２４】
【図１】本発明の１つの実施例による乱数生成モジュールの簡略ブロック図を示す。
【図２】本発明の１つの実施例による乱数のシーケンスに実行されるランダム性テストを示す図を示す。
【図３】本発明の１つの実施例による生成された乱数の統計値をテストする動作ステップを示すフローチャートである。
【図１】
2005523511.tif 000009
【図２】
2005523511.tif 000010
【図３】
2005523511.tif 000011
【国際調査報告】
2005523511.tif 000012
2005523511.tif 000013
2005523511.tif 000014
2005523511.tif 000015
2005523511.tif 000016