(57)【要約】フリップフロップの準安定作用を用いて乱数を生成するための方法および装置が開示される。フリップフロップは、準安定作用を確実にするためにフロップフロップのセットアップまたはホールド時間（または両方）を故意に乱す入力によってクロックされる。準安定事象が検出されたとき、出力ビットは、ランダムビットとして提供される。前記フリップフロップに対するゼロ入力の半数を「１」として、且つ前記ゼロのその他の半数を「ゼロ」として「マークする」ことによって、一様な乱数分布が得られる。加えて、前記１の半数は、「１」としてマークされ、且つ前記１のその他の半数は「ゼロ」としてマークされる。マーキング信号は、リニアフィードバックシフトレジスタを使用していかなるノイズに対しても高い確率で無相関である。
2004537119.tif 000002
【特許請求の範囲】
【請求項１】
乱数を発生するための方法であって、
マーキング信号を用いてフリップフロップへの入力信号をマーキングするステップであり、前記入力信号は、第１のバイナリ値および第２のバイナリ値を有し、前記マーキング信号は、前記第１のバイナリ値のほぼ半数を前記第１のバイナリ値としてマークし且つ前記第１のバイナリ値のほぼ半数は前記第２のバイナリ値としてマークされるステップと、
前記マーキング信号をノイズに対して非相関とするステップと、
前記フリップフロップを準安定状態にて動作させるステップと、
前記準安定状態の生起に基づいて前記マーキング信号から乱数ビットを生成するステップと、を有する、方法。
【請求項２】
前記非相関とするステップは、少なくとも一つのリニアフィードバックシフトレジスタによって実行される、請求項１に記載の方法。
【請求項３】
前記リニアフィードバックシフトレジスタは、相関の機会を減少させるために充分なビットの数を提供する、請求項２に記載の方法。
【請求項４】
前記リニアフィードバックシフトレジスタ（ＬＦＳＲ）は、該ＬＦＳＲ出力におけるいかなる偏りも減少させるために充分なビットの数を提供する、請求項２に記載の方法。
【請求項５】
前記リニアフィードバックシフトレジスタは、生成された乱数ビットから偏りを除去する補償回路を有する、請求項２に記載の方法。
【請求項６】
前記非相関とするステップは、リニアフィードバックシフトレジスタの収集によって実行される、請求項１に記載の方法。
【請求項７】
前記フリップフロップは、該フリップフロップのセットアップ時間を乱すことによって前記準安定状態に置かれる、請求項１に記載の方法。
【請求項８】
前記フリップフロップは、該フリップフロップのホールド時間を乱すことによって前記準安定状態に置かれる、請求項１に記載の方法。
【請求項９】
前記生成するステップは、もし印加された入力に前記フリップフロップの出力が適合しなければ、誤り信号を生成するステップをさらに有する、請求項１に記載の方法。
【請求項１０】
前記誤り信号は、前記マーキング入力に基づいて収集されるべき乱数ビットを生じさせる、請求項９に記載の方法。
【請求項１１】
前記フリップフロップの出力を、ローカルクロック源に同期させるステップをさらに有する、請求項１に記載の方法。
【請求項１２】
乱数を作り出すために複数の前記乱数ビットを収集するステップをさらに有する、請求項１に記載の方法。
【請求項１３】
前記第１のバイナリ値はゼロであり、且つ前記第２のバイナリ値は１である、請求項１に記載の方法。
【請求項１４】
前記第１のバイナリ値は１であり、且つ前記第２のバイナリ値はゼロである、請求項１に記載の方法。
【請求項１５】
前記乱数ビットを生成するために、収集されたビットをシフトレジスタから解放するステップをさらに有する、請求項１に記載の方法。
【請求項１６】
乱数を発生するための方法であって、
ゼロの半数はゼロとマークされ、ゼロの半数は１とマークされ、１の半数はゼロとマークされ、そして１の半数は１とマークされるようにフリップフロップへの入力信号にマーキングするステップと、
前記マーキング信号をノイズに対して非相関とするステップと、
前記フリップフロップを準安定状態にて動作させるステップと、
前記準安定状態の生起に基づいて前記マーキング信号から乱数ビットを生成するステップと、を有する、方法。
【請求項１７】
前記非相関とするステップは、リニアフィードバックシフトレジスタによって実行される、請求項１６に記載の方法。
【請求項１８】
前記リニアフィードバックシフトレジスタは、相関の機会を減少させるために充分なビットの数を提供する、請求項１７に記載の方法。
【請求項１９】
前記リニアフィードバックシフトレジスタ（ＬＦＳＲ）は、該ＬＦＳＲ出力におけるいかなる偏りも減少させるために充分なビットの数を提供する、請求項１７に記載の方法。
【請求項２０】
前記リニアフィードバックシフトレジスタは、生成された乱数から偏りを除去する補償回路を有する、請求項１７に記載の方法。
【請求項２１】
前記非相関とするステップは、リニアフィードバックシフトレジスタの収集によって実行される、請求項１６に記載の方法。
【請求項２２】
前記生成するステップは、もし印加された入力に前記フリップフロップの出力が適合しなければ、誤り信号を生成するステップをさらに有する、請求項１６に記載の方法。
【請求項２３】
乱数を作り出すために複数の前記乱数ビットを収集するステップをさらに有する、請求項１６に記載の方法。
【請求項２４】
準安定状態で作動されるフリップフロップと、
マーキング信号を用いて前記フリップフロップに対する入力信号をマーキングするためのマーキング回路であって、前記入力信号は、第１のバイナリ値および第２のバイナリ値を有し、前記マーキング信号は、前記第１のバイナリ値のほぼ半数を前記第１のバイナリ値としてマークし且つ前記第１のバイナリ値のほぼ半数は前記第２のバイナリ値としてマークされるマーキング回路と、
前記マーキング信号をノイズに対して非相関とする少なくとも一つのリニアフィードバックシフトレジスタと、
前記準安定状態の生起に基づいて前記マーキング信号から乱数ビットを生成するための手段と
を具備する、乱数発生器。
【請求項２５】
前記第１のバイナリ値はゼロであり、且つ前記第２のバイナリ値は１である、請求項２４に記載の乱数発生器。
【請求項２６】
前記第１のバイナリ値は１であり、且つ前記第２のバイナリ値はゼロである、請求項２４に記載の乱数発生器。
【請求項２７】
前記一つまたはそれより多くのリニアフィードバックシフトレジスタは、相関の機会を減少させるために充分なビットの数を提供する、請求項２４に記載の乱数発生器。
【請求項２８】
前記一つまたはそれより多くのリニアフィードバックシフトレジスタ（ＬＦＳＲ）は、該ＬＦＳＲ出力におけるいかなる偏りも減少させるために充分なビットの数を提供する、請求項２４に記載の乱数発生器。
【請求項２９】
前記一つまたはそれより多くのリニアフィードバックシフトレジスタは、生成された乱数から偏りを除去する補償回路を有する、請求項２４に記載の乱数発生器。
【請求項３０】
準安定状態で作動されるフリップフロップと、
ゼロの半数はゼロとマークされ、ゼロの半数は１とマークされ、１の半数はゼロとマークされ、そして１の半数は１とマークされるように、前記フリップフロップに対する入力信号をマーキングするためのマーキング回路と、
前記マーキング信号をノイズに対して非相関とする一つまたはそれより多くのリニアフィードバックシフトレジスタと、
前記準安定状態の生起に基づいて前記マーキング信号から乱数ビットを生成するための手段と、を具備する、乱数発生器。
【請求項３１】
前記一つまたはそれより多くのリニアフィードバックシフトレジスタは、相関の機会を減少させるために充分なビットの数を提供する、請求項３０に記載の乱数発生器。
【請求項３２】
前記一つまたはそれより多くのリニアフィードバックシフトレジスタ（ＬＦＳＲ）は、該ＬＦＳＲ出力におけるいかなる偏りも減少させるために充分な数のビットを提供する、請求項３０に記載の乱数発生器。
【請求項３３】
前記一つまたはそれより多くのリニアフィードバックシフトレジスタは、生成された乱数から偏りを除去する補償回路を有する、請求項３０に記載の乱数発生器。
【発明の詳細な説明】
【技術分野】
【０００１】
（関連出願に対するクロスレファレンス）
本発明は、本発明の譲受人に譲渡され、「フリップフロップ準安定性を用いて乱数を生成するための方法および装置」（Method and Apparatus for Generating Random Numbers Using Flip-Flop Meta-Stability）と題されて、２０００年３月６日に出願され、引用により本明細書組み込まれた、米国特許出願第０９／５１９，５４９号に関連している。
【０００２】
本発明は、乱数の生成に、そしてより詳細には、フリップフロップ準安定性を用いて乱数を生成するための方法および装置に関する。
【背景技術】
【０００３】
フリップフロップおよびラッチは、コンピューターおよび他の電子デバイス、例えばサンプリング、カウントおよび格納要素として広く使用されている。Ｄ型フリップフロップ（「データ」）、Ｒ−Ｓラッチ（「リセットおよびセット」）、Ｊ−Ｋフリップフロップ（ＪおよびＫ入力を有する）、そしてＴフリップフロップ（ただ一つの入力を有する）のような、多数のフリップフロップタイプが開発されている。例えば、Ｄ型フリップフロップは、その出力が１クロックパルスだけ遅延されるクロック動作フリップフロップである。
【０００４】
在来のＲ−Ｓラッチ１００が、図１Ａに示されている。図１Ａにおけるように、Ｒ−Ｓラッチ１００は、２つのＮＯＲゲート１１０および１２０から構成されている。２つのＮＯＲゲート１１０、１２０の出力は、反対側のＮＯＲゲートのそれぞれの入力に交差接続されている。すなわち、ＮＯＲゲート１１０は、ＮＯＲゲート１２０の出力およびリセット信号Ｒを、入力として受ける。同様に、ＮＯＲゲート１２０は、ＮＯＲゲート１１０の出力およびセット信号Ｓを入力として受ける。
【０００５】
より最近では、図１Ａに示される単純なラッチは、Ｄ型フリップフロップ１５０が図１Ｂに示されるように、エッジトリガーされるフリップフロップに置き換えられている。そのようなＤ型フリップフロップは、クロック信号に関して予想できないタイミングを有する非同期ディジタル信号の論理状態を検出するためにしばしば使用されている。立ち上がり信号が、フリップフロップ１５０のクロック入力ＣＬＫに印加されると同時に、検出されるべき非同期信号のディジタル論理レベルは、Ｄ入力に向けられる。検出された信号は、それからＱ出力ライン上に取り出される。前記クロックが再度立ち上がらない限り、出力Ｑは、変化しない。その後は、フリップフロップ１５０は、（リセット信号が、恒久的にグラウンドに結合されている限りは）ＣＬＫ信号が立ち上がるたびに状態をＤ入力上の値に単純に変化させる。
【０００６】
図１Ａに示されるラッチ１００は、準安定になり易い。準安定性の詳細な議論については、例えば引用により本明細書組み込まれた、「アプリケーションノート、準安定性入門」（Application Note, A Meta-Stability Primer）,AN219,Philips Semiconductors（１９８９年１１月１５日）、を参照されたい。概して、準安定性は、ラッチ１００に対する両入力が、高論理値（「１１」）にセットされ、そしてそれから低論理値（「００」）にリセットされたときに、起こり得る。これらの状況のもとで、ラッチ出力は、統計的に既知の方法で予測できないように発振し得る。理論上においては、ラッチ１００は、無期限に発振し得る。しかしながら、実際には、ラッチ１００は、ランダムに転移し且つ論理低または高のいずれかのランダムな出力値に行き着く。典型的には、これらの準安定値は、続いて、所与のアプリケーションにおける他の回路構成によって検出され、そして異なる論理レベル状態として解釈され得るか、または、他の論理ゲートによって誤って解釈され得る中間状態と想定されてしまう。
【０００７】
加えて、図１Ｂに示されるエッジトリガーされるフリップフロップ１５０は、該フリップフロップのセットアップまたはホールド時間が乱されてしまったときに、準安定となり得る。エッジトリガーされるフリップフロップ１５０は、あらゆるエッジトリガーされるフリップフロップ１５０の内部において、エッジ検出回路構成によって提供されるラッチ１００が存在するので、準安定になりがちである。もしセットアップまたはホールド時間が乱されると、そのときは、内部ラッチ１００は、準安定状態をトリガーし得る入力を監視することになる。
【０００８】
ポーカー、ルーレットおよびスロットマシーンのような運のゲームを含む、多くのアプリケーションおよび電子的デバイスは、乱数を必要とする。特に、非常に多くの暗号のアルゴリズムおよびプロトコルは、安全な電子的通信およびそれに類似したものを実行するために乱数の非予測性に依存している。乱数発生器は、数値の指定された範囲内においてあらゆる可能性のある順列を生成すべきである。加えて、乱数発生器は、偏るべきではなく、そしていかなる所与の数も、いかなる他の数と同様の確率で生成すべきである。さらに、乱数発生器は、以前の結果の収集の量にかかわらず、予測され得ない乱数を発生すべきである。それ故、乱数は、完全に予測不可能で且つ外部の影響を受け得ないものとすべきである。
【０００９】
「フリップフロップ準安定性を用いて乱数を生成するための方法および装置」（Method and Apparatus for Generating Random Numbers Using Flip-Flop Meta-Stability）と題されて、２０００年３月６日に出願された、米国特許出願第０９／５１９，５４９号は、フリップフロップの準安定作用を用いて乱数を生成するための方法および装置を開示している。フリップフロップは、準安定作用を確実にするためにフリップフロップのセットアップまたはホールド時間（または両方）を故意に乱す入力によってクロックされる。ビットは、エラーがあるときはいつでも収集される。もし、所与の種類のフリップフロップについて、一つのバイナリ値（ゼロまたは１）について、準安定性がもっと頻繁に起こるならば、ゼロの半数を「１」とし且つゼロの他の半数を「０」として「マーキング」することによって、一様な乱数分布が得られる。加えて、１の半数が「１」と、他の半数が「ゼロ」とマークされる。
【００１０】
このやり方で入力ビットをマークすることは、理論的には、乱数出力ビットの均一な分布を提供する。準安定性がランダムベースで起きているのに、準安定性の期間および生起がノイズにより影響されることがわかっている。それ故、もしノイズが、マーキング信号に相関されていれば、そのときは乱数発生器の出力は、ランダムではないであろう。それ故に、ノイズまたは他の外力によって影響されない準安定性を用いて乱数を生成するための方法および装置の必要性が存在する。当該システムにおけるいかなるノイズに対しても高い確率で非相関であるマーキング信号を用いる準安定性を用いて乱数を生成するための方法および装置のさらなる必要性が存在する。
【発明の開示】
【発明が解決しようとする課題】
【００１１】
概して、フリップフロップの準安定作用を用いて乱数を生成するための方法および装置が開示される。フリップフロップは、準安定作用を確実にするためにフリップフロップのセットアップまたはホールド時間（あるいは両方）を故意に乱す入力によってクロックされる。フリップフロップの準安定作用は乱数を生成するためのメカニズムを提供する。
【課題を解決するための手段】
【００１２】
フリップフロップが準安定になる都度の、発振の結果は、発振が止まった後に達成される結果すなわち論理値に従ってランダムである。もし、正常な動作の間に達成されたであろう値と結果が異なっていたら（「誤り」）、そのときは準安定事象が検出され得る。もし、ゼロおよび１の繰り返しシーケンスが、フリップフロップに対する入力として用いられれば、ゼロまたは１のいずれかについて「誤り」を生じさせる機会が存在するであろう。
【００１３】
１またはゼロの均一な分布が、（ｉ）ゼロの半数を「１」とし、且つゼロの他の半数を「ゼロ」とする；（ｉｉ）１の半数を「１」とし、且つ他の半数を「ゼロ」とする；あるいは（ｉｉｉ）それらの両方とする「マーキング」によって得られる。それ故、ゼロ状態または１状態においてなされる誤りの割合にかかわらず、乱数出力ビットの分布は、均一にとどまる。
【００１４】
本発明は、いかなるシステムノイズに対してもマーキング信号を高い確率で非相関とする。それ故、（ゼロおよび１の頻度に関して）偏らない信号源が、マーキング信号として使用される。リニアフィードバックシフトレジスタ（ＬＦＳＲ）が、マーキング信号を非相関とするために採用される。リニアフィードバックシフトレジスタは、相関の機会を減少させ且つＬＦＳＲ出力におけるいかなる偏りも低減するのに充分な長さを持つべきである。より長いシフトレジスタは、より長いシーケンスを有し且つ従ってノイズ源と整合されない非常に高い確率を有する。
【００１５】
本発明のさらなる特徴や利点ばかりでなく、本発明のより完全な理解が、以下の詳細な説明および図面に対する参照によって得られる。
【発明を実施するための最良の形態】
【００１６】
図２Ａは、「フリップフロップ準安定性を用いて乱数を生成するための方法および装置」（Method and Apparatus for Generating Random Numbers Using Flip-Flop Meta-Stability）と題されて、２０００年３月６日に出願された、米国特許出願第０９／５１９，５４９号の教示に従った乱数発生器２００を示している。乱数発生器２００は、ゼロの半数を「１」とし、且つゼロの他の半数を「ゼロ」として「マーキング」することによって乱数出力ビットの一様な分布を提供する。加えて、１の半数が「１」としてマークされ、他の半数が「ゼロ」としてマークされる。
【００１７】
図２Ａに示されるように、乱数発生器２００は、フリップフロップ２１０、ディレイ２１５、２２０、Ｄ型フリップフロップ２２５、２３２、およびクロック発振器２３０を含んでいる。フリップフロップ２１０は、準安定作用を確実にするためにフリップフロップ２１０のセットアップまたはホールド時間（あるいは両方）を故意に乱す入力によってクロックされる。セットアップまたはホールド時間は、例えばディレイ２１５、２２０を用いて乱され得る。フリップフロップ２１０は、例えばＤ、ＴまたはＪＫタイプのフリップフロップとして具体化され得る。加えて、フリップフロップ２１０は、当該技術における通常の技術を有するものには明らかであろうように、単純なラッチ１００および若干異なった回路として具体化され得る。
【００１８】
クロック源は、クロック発振器２３０およびそのＱバー（Qbar)出力がそのＤ入力(input_D）にフィードバックされているＤ型フリップフロップ２２５によって生成される。この方法で、Ｄ型フリップフロップ２２５は、２で割り算するメカニズムを提供すべく、Ｔ型フリップフロップ（トグル化出力）と同様の方法で動作する。このように、フリップフロップ２１０のＤ入力は、１およびゼロに交互に切換えられることによって駆動される。２で割り算フリップフロップ２３２は、図２Ｃに示される、入力波形におけるゼロの半数を「１」とし、ゼロの他の半数を「ゼロ」としてマークする、マーク信号（Mark）を生成する。
【００１９】
図２Ａおよび図２Ｃにおいて最も明確に見られるように、クロック発振器２３０によって作られるクロック波形は、図２Ａにおいて「クロック」（Clock)とマークされたサンプル点において得られる。２で割り算フリップフロップ２２５によって作られる入力波形は、図２Ａにおいて「入力」(Input）とマークされたサンプル点において得られる、ディレイ２１５によって作られる入力Ｄ波形およびディレイ２２０によって作られる入力クロック波形（Input_clock）は、図２Ａにおける対応するサンプリング点において得られる。２で割り算フリップフロップ２３２によって作られるマーク波形は、図２Ａにおいて「マーク」（Mark）とマークされたサンプル点で得られる。
【００２０】
図２Ｃに示される通り、ディレイ２１５、２２０によるセットアップまたはホールド時間（あるいは両方）の乱れは、準安定出力（META-STABLE OUT）波形によって明示されるように、フリップフロップ２１０が準安定作用を示すであろうことを確実にする。以下においてさらに議論されるように、フリップフロップ２１０の準安定動作は、乱数を生成するためのメカニズムを提供する。
【００２１】
ディレイ２１５、２２０による遅延、フリップフロップ２１０それ自体における本来の遅延、および最も重要な点で準安定作用による不均一遅延からの結果として、準安定出力（META-STABLE OUT）波形は、クロック波形に同期していない。それ故、図２Ａの乱数発生器２００を同期アプリケーションに適するようにさせるために、実例となるメカニズムは、準安定出力（META-STABLE OUT）波形をクロック波形と同期させるべく図２Ｂにおいて提供されている。図２Ａおよび図２Ｂの回路構成は同様の文字の吹き出し（バブル）を結合することによって接続されることに留意されたい。
【００２２】
図２Ｂに示される同期回路構成２３５は、準安定状態に容易に入ることがないように選択された、いくつかの直列フリップフロップ２４０から２４２を含んでいる。加えて、もしこれらのフリップフロップ２４０から２４２の一つが準安定となると、クロック信号の期間は、準安定フリップフロップの出力が固定された論理値（０または１）に落ち着くであろうように、充分に長くなるはずであり、そのため信号が次のフリップフロップ２４０から２４２においてサンプリングされたときに、該フリップフロップは安定となる。このようなやり方において、各フリップフロップ２４０から２４２は、準安定出力（META-STABLE OUT）波形をクロック波形に同期させる機会を改善し、同時にいかなる準安定性も除去する。実際、そのような回路についての不適正な作用の機会は、数十年のうちに測定されるであろう。
【００２３】
排他的論理和ゲート（「ＸＯＲ」）２５０は、同期バージョンの準安定出力（META-STABLE OUT）波形を（２分周フリップフロップ２２５の出力においてサンプリングされた）入力波形と比較する。ＸＯＲゲート２５０の出力は、もし２つの入力が異なっている場合および、もし２つの入力が異なっている場合にのみ、高いであろうから、ＸＯＲゲート２５０の出力（「誤り」）は、もし安定出力（Stable-out）波形が入力信号と適合しなければ、高いであろう。ＸＯＲゲート２５０の出力「誤り」（Mistake）が、シフトレジスタ２６０のシフト入力（シフト入力波形、Shift_in）に印加され、そしてシフトレジスタ２６０は、誤りが存在するたびにその都度マーク信号から１ビットシフトするであろう。それ故、本発明の第１の実施の形態は、エラー（誤り）が存在するときはいつでもビットを集める。
【００２４】
シフトレジスタ２６０の入力ラインは、マーク信号に接続されている。このようにして、誤りがあるときはその都度、シフトレジスタ２６０がマーク信号からのビットにおいてシフトするであろう。それ故、図２Ｃに示されるように、誤りゼロについては、（マーク信号に基づいて）１に等しいビットが、収集されるであろう。同様に、誤り１つについては、（マーク信号に基づいて）ゼロに等しいビットが、収集されるであろう。
【００２５】
乱数発生器２００は、「１」または「ゼロ」のいずれかのマークによって、フリップフロップ２１０に１の入力をマークする。したがって、もし入力についての１つの値に誤りが生じたら、乱数ビットの均一な分布も、前記１の値で作られた誤りに起因して収集されるであろう。それ故、この回路は、１またはゼロの入力値に生じるエラーの間の偏りには反応しない。
【００２６】
先に記載された通り、図２Ａから図２Ｃに関連して上述で議論されたやり方で入力ビットをマークすることは、乱数出力ビットの均一な分布を提供する。しかしながら、準安定性の期間および生起はノイズによって影響され得ることが解っている。このようにして、もしノイズがマーキング信号に相関されていれば、そのときは該乱数発生器の出力は、ランダムではないであろう。
【００２７】
本発明の一つの特徴によれば、（ゼロおよび１の頻度について）偏っていない信号源が、マーキング信号として使用される。該マーキング信号は、システムにおけるいかなるノイズに対しても高い確率で非相関である。本発明は、相関の機会を減少させ且つ当該ＬＦＳＲ出力におけるいかなる偏りも低減するのに充分な長さを有するリニアフィードバックシフトレジスタ（ＬＦＳＲ）を採用している。適切なＬＦＳＲは、例えばBruce Schneier、「応用暗号作成法」（Applied Cryptography）、369-388ページ（Wiley,1994年）に記述されている。
【００２８】
図３は、本発明に従った乱数発生器３００を示している。図３に示されるように、乱数発生器３００は、フリップフロップ２１０、ディレイ２１５、２２０、Ｄ型フリップフロップ２２５、および図２Ａに関連して上述されたのと同様の方法で動作するクロック発振器２３０を含んでいる。加えて、乱数発生器３００は、入力波形におけるゼロの半数より若干多くを、「１」とし、且つゼロのほとんど半数を「ゼロ」としてマークする、図４に示される、ＬＦＳＲマーク信号を生成する、リニアフィードバックシフトレジスタ３１０を含んでおり、該マーク信号は、本発明に関するいかなるノイズとも高い確率で非相関である。前記信号は、ｎビットのＬＦＳＲについて２ｎ−１パターンしかないので（全てゼロのパターンが生じることはない）、常に若干の偏りを有している。この偏りは、もしｎが大きければとるに重大ではないものとなる。
【００２９】
したがって、図３の乱数発生器３００は、図２Ａのマーキングフリップフロップ２３２をリニアフィードバックシフトレジスタ３１０で置き換えている。リニアフィードバックシフトレジスタ３１０は、Bruce Schneier、「応用暗号作成法」（Applied Cryptography）、369-388ページ（Wiley,1994年）に記述されたように実施され得る。図３の乱数発生器３００は、クロック源に乱数発生器３００の出力を同期させるために、図２Ｂの同期回路２３５と共に利用され得る。
【００３０】
先に記載された通り、リニアフィードバックシフトレジスタ３１０は、相関の機会を減少させ且つＬＦＳＲ出力におけるいかなる偏りをも低減するために充分に多数のビットを提供すべきである。ｎ個のフリップフロップを含むリニアフィードバックシフトレジスタ３１０について、数が繰り返し始める前に２ｎ−１のバイナリ数が存在するであろう。そのように、リニアフィードバックシフトレジスタ３１０におけるフリップフロップの数が増大するにつれて、２ｎ−１のバイナリ表現における−１は、より重要でなくなる。少なくとも、前記−１項に対して帰属し得るいかなる偏りの方向も既知であるから、図５に関連して以下に議論されるように、この偏りは適切な回路によって除去または補正され得る。
【００３１】
それ故、リニアフィードバックシフトレジスタ３１０は、疑似ランダムである、マーキング出力ＬＦＳＲマークを、出力ビットの半数をゼロとし、且つ出力ビットの他の半数を１として提供する。
【００３２】
もしリニアフィードバックシフトレジスタ３１０が不安定であれば、出力の部分（ランダム部分でさえも）が、リニアフィードバックシフトレジスタ３１０の状態を知られるようにすることを許容し得る。このようにして、乱数発生器３００の出力を予想することが可能となるかもしれない。それ故、識別できる統計量を持たないリニアフィードバックシフトレジスタ３１０が利用されるべきであり、それによってリニアフィードバックシフトレジスタ３１０の状態情報を無用にする。さらなるバリエーションにおいて、付加的な安全が、シフトレジスタ２６０から収集されたビットを解放することによって、そして各収集間隔において収集ビットのいくつかを失うことを許容することによって達成される。
【００３３】
シフトレジスタ２６０は、誤りが存在するたびにその都度マーク信号から１ビット全体にシフトさせる。この方法において、誤りの到着時間は、識別されず、そして誰かが、リニアフィードバックシフトレジスタ３１０のどのビットが選択されるであろうかを予想することはできない。
【００３４】
図５は、本発明の代わりの実施の形態を示している。先に記載された通り、いかなる最大の長さのＬＦＳＲについても、１とゼロとの間の比率には若干の偏りが存在するであろう。この条件は、全てがゼロの状態が生じることがなく、さもなければＬＦＳＲが変化を停止してしまうという要求から生じている。言い換えれば、もしＬＦＳＲの状態が全てゼロであれば、そのときは、タップの数またはシフトの数にかかわらず、ＸＯＲの組合せは１にならない。それ故、全て１の状態を除く全ての状態は、二重の状態を有する。例えば、３ビットＬＦＳＲが与えられると、状態１０１は、二重状態の０１０と共に生じるであろう。しかしながら、全て１の状態（１１１）については、このことは正しくはない。もし最下位ビット（またはそのことについての他のいずれかのビット）が出力として使用されるならば、そのときは、ＬＦＳＲは、４つの１（１１１１）および３つのゼロ（０００）の出力と共に７つの固有の状態を持つであろう。
【００３５】
この偏りを補正するために、我々は、全て１の状態が生じたときにのみ変化し且つ使用されるだけのＬＦＳＲ状態フリップフロップ５１０を追加することができる。このフリップフロップ５１０の初期状態は、関連性がない。我々は、ＮビットＡＮＤゲート５２０によって全て１の状態を最初に検出する。このゲート５２０の出力は、全て１の状態が生じたときにのみ真となるであろう。我々は、このＡＮＤゲート５２０を一対の２対１マルチプレクサー５３０、５４０に接続する。第１の２対１マルチプレクサー５３０は、ＬＦＳＲ５０５に全て１の状態が生じ、ＡＮＤゲート５２０の出力を真とさせるときにのみ、ＬＦＳＲ状態フリップフロップ５１０の状態を変化させるために使用される。さもなければ、状態フリップフロップ５１０に対して同一の状態が再循環され、そしてその状態が変化しない。第２の２対１マルチプレクサー５４０は、通常は、ＬＦＳＲ５０５からの形式的な出力ビットを受ける。ＬＦＳＲ５０５に全て１の状態が生じたときは、この第２の２対１マルチプレクサー５４０は、ＬＦＳＲ状態フリップフロップ５１０からのビットを受ける。全て１状態が生じると毎回ＬＦＳＲ状態が変化する。それ故、ＬＦＳＲ５０５の状態が全て１となるときに、時間の半分は、補正されたＬＦＳＲについての出力ビットが１となり、そしてＬＦＳＲ５０５の状態が全て１であるときに、時間の半分は、補正されたＬＦＳＲ５０５についての出力ビットがゼロとなるであろう。それ故、２サイクル毎に、ＬＦＳＲ５０５の全ての状態を通して、フリップフロップ５５０で受信される累積出力は、完全に偏りがなく、すなわち、補正された出力ビットストリームにおける１およびゼロの数は、均一となるであろう。
【００３６】
ＬＦＳＲについて、全シーケンスが使用されない場合、この回路は、局部的な偏りに関する他の論点がより重要となるであろうから、不要となる。
【００３７】
本明細書に示され且つ説明された実施の形態および変形例は、単に本発明の原理の例証となるものであり、本発明の範囲および精神から逸脱することなく、当業者によって種々の修正が施されるであろうことが、理解されるべきである。
【図面の簡単な説明】
【００３８】
【図１Ａ】在来のＲ−Ｓラッチを示す図である。
【図１Ｂ】在来のＤ型フリップフロップを示す図である。
【図２Ａ】「フリップフロップ準安定性を用いて乱数を生成するための方法および装置」（Method and Apparatus for Generating Random Numbers Using Flip-Flop Meta-Stability）と題されて、２０００年３月６日に出願された、米国特許出願第09/519,549号の教示に従った乱数発生器を示す図である。
【図２Ｂ】図２Ａの乱数発生器の出力をクロック源に同期させるために利用され得る同期回路を示す図である。
【図２Ｃ】図２Ａおよび図２Ｂの回路によって作られる１セットの波形を示す図である。
【図３】本発明に従った改善された乱数発生器を示す図である。
【図４】図３および図２Ｂの回路によって作られる１セットの波形を示す図である。
【図５】偏らないリニアフィードバックシフトレジスタを用いる本発明の代替の実施の形態を示す図である。
【図１Ａ】
2004537119.tif 000003
【図１Ｂ】
2004537119.tif 000004
【図２Ａ】
2004537119.tif 000005
【図２Ｂ】
2004537119.tif 000006
【図２Ｃ】
2004537119.tif 000007
【図３】
2004537119.tif 000008
【図４】
2004537119.tif 000009
【図５】
2004537119.tif 000010
【国際公開パンフレット】
2004537119.tif 000011
2004537119.tif 000012
2004537119.tif 000013
2004537119.tif 000014
2004537119.tif 000015
2004537119.tif 000016
2004537119.tif 000017
2004537119.tif 000018
2004537119.tif 000019
2004537119.tif 000020
2004537119.tif 000021
2004537119.tif 000022
2004537119.tif 000023
2004537119.tif 000024
2004537119.tif 000025
2004537119.tif 000026
2004537119.tif 000027
2004537119.tif 000028
2004537119.tif 000029
2004537119.tif 000030
2004537119.tif 000031
【国際調査報告】
2004537119.tif 000032
2004537119.tif 000033
2004537119.tif 000034