(57)【要約】ラッチの準安定挙動を使用して乱数を発生する方法及び装置が記載されている。ラッチが、準安定になるたびに、発振の結果は、発振停止の後に到達する論理値に対してランダムである。ラッチの出力が、前記ラッチの正しい動作の間に到達していた値と異なる場合（即ち、「誤り」）、準安定事象が検出されることができる。２つ以上のほぼ同一のラッチは、並列に動作し、誤りは、前記ラッチの少なくとも２つが、異なる出力を有する場合に検出される。誤りの検出は、ランダムビットの発生を起動するのために使用されることができる。本発明は、複数のラッチを並列に動作させ、同一のバイナリ値を、各ラッチの各入力に供給する。ラッチが、準安定状態に入った場合、該ラッチの該出力は、ロジックロー又はロジックハイのいずれかのランダム出力値に安定する前に、ランダムにシフトする。２つのラッチが、異なる値に安定する場合、誤りが、これによって、識別されることができ、ランダムビットの発生を起動する。
2005530270.tif 000002
【特許請求の範囲】
【請求項１】
ラッチを使用して乱数を発生する方法であって、
―  前記ラッチの準安定状態を検出するステップ、
―  前記準安定状態の出現に基づいて、ランダムビットを発生するステップ、
を有する方法。
【請求項２】
前記検出するステップが、複数のラッチを、並列に動作させ、２つ以上の前記ラッチにおける異なる出力を検出するステップを更に有する、請求項１に記載の方法。
【請求項３】
２つ以上の前記ラッチにおける異なる出力を検出する前記ステップが、排他的論理和（ＸＯＲ）ゲートを使用して実行される、請求項２に記載の方法。
【請求項４】
マーキング信号とノイズとの相関を低下させるステップを更に有する、請求項１に記載の方法。
【請求項５】
前記相関を低下させるステップが、少なくとも１つの線形帰還シフトレジスタによって実行される、請求項４に記載の方法。
【請求項６】
前記発生するステップが、第１ラッチの出力が、第２ラッチの出力と整合しない場合、誤り信号を発生するステップを更に有する、請求項１に記載の方法。
【請求項７】
前記誤り信号が、ランダムビットを、前記マーキング入力に基づいて取得されるようにする、請求項６に記載の方法。
【請求項８】
前記ラッチの出力を、ローカルクロックソースと同期させるステップを更に有する、請求項１に記載の方法。
【請求項９】
複数の前記ランダムビットを収集し、乱数を発生するステップを更に有する、請求項１に記載の方法。
【請求項１０】
シフトレジスタから、収集されたビットを解放し、前記ランダムビットを発生するステップを更に有する、請求項１に記載の方法。
【請求項１１】
前記検出するステップが、所定の出力の収集の１つが検出された場合に、前記所定の出力の収集における複数の前記ラッチの出力を、比較し、ランダムビットを発生するステップを更に有する、請求項１に記載の方法。
【請求項１２】
前記検出するステップが、複数の前記ラッチを並列に動作させるステップを更に有し、前記方法が、前記複数のラッチの反転された及び非反転された出力を選択し、結合する複数の組み合わせを評価し、適切な組み合わせを発見するステップを更に有する、請求項１に記載の方法。
【請求項１３】
前準安定状態において動作され、前記準安定状態の出現に基づいて、ランダムビットを発生するラッチを有する、乱数発生器。
【請求項１４】
前記準安定状態の前記出現が、複数のラッチを並列に動作させ、２つ以上の前記ラッチの異なる出力を検出することによって、検出される、請求項１３に記載の乱数発生器。
【請求項１５】
前記ラッチの出力が、ローカルクロックソースと同期させられる、請求項１３に記載の乱数発生器。
【請求項１６】
複数の前記ランダムビットが収集されて、乱数を発生する、請求項１３に記載の乱数発生器。
【請求項１７】
シフトレジスタからの収集されたビットが、解放され、前記ランダムビットを発生する、請求項１３に記載の乱数発生器。
【請求項１８】
前記準安定状態の前記出現が、所定の出力の収集の１つが検出された場合に、前記所定の出力の収集における出力を比較し、ランダムビットを発生することによって検出される、請求項１３に記載の乱数発生器。
【請求項１９】
少なくとも２つの前記ラッチが、異なる出力を発生し、ランダムビットを発生するように、並列に動作される複数のラッチを有する、乱数発生器。
【請求項２０】
前記少なくとも２つの前記ラッチによる異なる出力を検出する排他的論理和（ＸＯＲ）ゲートを更に有する、請求項１９に記載の乱数発生器。
【請求項２１】
複数の前記ランダムビットが収集され、乱数を生じる、請求項１９に記載の乱数発生器。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、「フリップフロップ準安定性を使用して乱数を発生する方法及び装置」という名称で、２０００年３月６日に出願された米国特許出願第０９／５１９，５４９号明細書、及び「擬似ランダム系列を使用して乱数発生器の相関を低下させる（decorrelating）方法及び装置」という名称で、２００１年７月２５日に出願された米国特許出願第０９／９１２，６８５号明細書に関し、それぞれは本発明の譲受人に譲渡されたものであり、参考により本明細書に組み込まれる。
【０００２】
本発明は、乱数発生に関し、更に詳細には、ラッチの準安定挙動を使用して乱数を発生する方法及び装置に関する。
【背景技術】
【０００３】
ラッチ及びフリップフロップは、サンプリング、カウント及び記憶素子として、コンピュータ及び他の電子デバイスにおいて、広く使用されている。従来型Ｒ−Ｓラッチ１００が、図１に示されている。図１にあるように、Ｒ−Ｓラッチ１００は、２つのＮＯＲゲート１１０及び１２０によって構成されている。２つのＮＯＲゲート１１０、１２０の出力は、反対側のＮＯＲゲートの各入力に交差接続されている。従って、ＮＯＲゲート１１０は、ＮＯＲゲート１２０の出力とリセット信号Ｒとを、入力として受け取る。同様に、ＮＯＲゲート１２０は、ＮＯＲゲート１１０の出力とセット信号Ｓとを、入力として受け取る。種々の入力の組み合わせに対するＲ−Ｓラッチ１００の出力は、図２における表２００に示されている。
【０００４】
従って、図１に示されているラッチ１００は、ラッチ１００への入力の両方が、高い論理値（「１１」）に設定されている場合、準安定性に影響されやすく、次いで、両方の入力が低い値（「００」）である状態に遷移する。この遷移は、時折、ラッチ出力を、統計的に既知である態様で、予測不可能的に発振させる。準安定性についての詳細な議論に関しては、例えば、以下で参照のために示す、アプリケーションノート「準安定性入門書、ＡＮ２１９、フィリップスセミコンダクタ（１９８９年１１月１５日）」を参照していただきたい。理論的には、ラッチ１００は、無期限に発振することが可能である。しかしながら、実際には、ラッチ１００は、ロジックハイ又はローのいずれかのランダム出力値に、ランダムに到達する。典型的には、これらの準安定値は、次いで、所与のアプリケーションにおける他の回路によって検出され、異なる論理レベル状態であると解釈され得る、又は他の論理ゲートによって誤解され得る中間状態を呈する。
【０００５】
ポーカー、ルーレット及びスロットマシンのような確率のゲームを含む、多くのアプリケーション及び電子デバイスが、乱数を要する。特に、多数の暗号アルゴリズム及びプロトコルは、非予測可能な乱数のソースに基づき、暗号化電子通信及び類似のものを実施する。乱数発生器は、指定された数の範囲内で、起こり得る全ての順列を発生するべきである。これに加えて、前記乱数発生器は、偏っていてはならず、任意の数を、その他の数と同様の確率で発生するべきである。更に、前記乱数発生器は、予測されることができない乱数を、事前の結果の収集の大きさに関係なく、発生するべきである。従って、前記乱数は、完全に予測不可能であって、外部の影響を受けないものであるべきである。
【０００６】
「フリップフロップ準安定性を使用して乱数を発生する方法及び装置」という名称で、２０００年３月６日に出願された米国特許出願第０９／５１９，５４９号明細書は、フリップフロップの準安定挙動を使用して乱数を発生する方法及び装置を記載している。フリップフロップは、準安定挙動を確実にするために、フリップフロップのセットアップ又はホールド時間（又は両方）を故意に妨害する入力によってクロックされる。ビットは、エラーがあるたびに、収集される。所与の分類のフリップフロップに関して、準安定性が、一方のバイナリ値（０又は１のいずれか）の頻度が高い状態で出現する場合、前記０の半分を「１」、前記０の他の半分を「０」と「マークする」ことによって、一様な乱数分布が得られる。更に、前記１の半分は「１」、他の半分は「０」とマークされる。
【０００７】
準安定性の期間及び出現は、ノイズによる影響され得ることが分かっている。従って、ノイズを、乱数発生器の出力に影響を及ぼすのに使用することができる。「擬似ランダム系列を使用して乱数発生器の相関を低下させる方法及び装置」という名称で、２００１年７月２５日に出願された米国特許出願第０９／９１２，６８５号明細書は、準安定性に基づく乱数発生器を記載しており、該乱数発生器は、相関関係の確率を低下させ、出力におけるいかなる偏りも低減するために、線形帰還シフトレジスタ（ＬＦＳＲ）を使用している。
【発明の開示】
【発明が解決しようとする課題】
【０００８】
フリップフロップの準安定挙動に基づく前記のような乱数発生器は、デジタル技術のみを使用して乱数を発生する効果的な仕組みを提供している一方で、これらのそれぞれは、単一のフリップフロップを使用しており、従って、出力がどのようにあるべきであったかの理解を推定しなくてはならない。デジタル技術のみを使用し、前記出力について、いかなる推定も必要としない乱数発生器が、望ましい。
【課題を解決するための手段】
【０００９】
全体的に、ラッチの準安定挙動を使用して乱数を発生する方法及び装置が、記載される。ラッチが準安定になるたびに、発振の結果は、該発振の停止の後に到達する結果又は論理値に対して、ランダムである。ラッチの出力が、該ラッチの正しい動作の間に得られるべきであった値と異なる場合（即ち「誤り（mistake）」）、準安定事象が検出されることができる。２つ以上の、ほとんど同一であるラッチが、並列に動作する場合、誤りは、少なくとも２つの前記ラッチが、異なる出力を得る場合に検出されることができる。前記誤りの検出は、本発明によるランダムビットの発生を起動するために使用されることができる。
【００１０】
上述したように、ラッチは、該ラッチへの両方の入力が、高い論理値（「１１」）に設定されている場合に、準安定性の影響を受けやすく、次いで、両方の入力が低い値（「００」）である状態に、遷移する。本発明は、複数のラッチを並列に動作させ、各ラッチの各入力に、同一のバイナリ値を供給する。従って、「００」の値が、各ラッチに供給された場合、該ラッチは、自身の事前の状態を持続すると期待される。しかしながら、「１１」の値に、両方の入力が各ラッチに対する低い値（「００」）にある状態が続く場合、該ラッチの状態は不確定であり得て、ロジックロー又はロジックハイのいずれかのランダム出力値に安定する前に、ランダムシフトを生じる。従って、２つのラッチが、異なる値に安定する場合、誤りは、これによって識別されることができ、本発明によるランダムビットの発生を起動する。
【発明を実施するための最良の形態】
【００１１】
本発明、並びに本発明の更なるフィーチャ及び利点に関する、より完全な理解は、以下の詳細な記載及び添付図面を参照することによって得られるであろう。
【００１２】
図３Ａ及び３Ｂは、本発明による乱数発生器３００を、総合的に示している。図３に示されているように、模範的な乱数発生器３００は、対のラッチ３２０-１、３２０-２を含んでおり、これらは、準安定領域へ駆動される。以下でより完全に記載するように、ラッチ３２０-１、３２０-２の出力は、準安定性を取り除き、出力を比較する回路によって、取り込まれる。ほとんど同一のラッチ回路の前記２つの出力が、異なる場合、「誤り」が検出され、ランダムビットが発生される。従って、ラッチ３２０−１、３２０-２のいずれかの準安定動作は、乱数を発生する仕組みを提供する。
【００１３】
図３Ａに示されているように、「クロック」信号は、クロック発振器３０５によって発生される。該クロック信号は、自身のＱｂａｒ出力が、自身のＤ入力に帰還されている対のＤ型フリップフロップ３１０-１、３１０-２の入力に、供給されている。Ｄ型フリップフロップ３１０は、二分割仕組みを提供する。フリップフロップ３１０−１のクロック入力が、インバータ３０８によって変換される。従って、フリップフロップ３１０−１によって発生される刺激信号は、フリップフロップ３１０−２によって発生される取得信号より、位相が１８０度遅れている。前記取得信号は、進行し、ＬＦＳＲ３８０は、統計的に、半分０、半分１であるビットストリームを発生する。図４に示されている種々の波形は、図３Ａ及び３Ｂにおける対応する符号を付けられたサンプリング点において、得られたものであることに留意されたい。
【００１４】
図３Ａ及び４に示されているように、ラッチ３２０-１、３２０-２は、フリップフロップ３０１によって発生される取得信号によって駆動される。上述したように、図３Ａに示したラッチ３２０-１、３２０-２のようなラッチは、ラッチ３１０の両方の入力が、低い論理値（「００」）に設定されている場合、準安定性の影響を受けやすく、次いで、両方の入力が高い値（「１１」）である状態に遷移する。図３Ａにおけるラッチ３２０-１、３２０-２は、ＮＡＮＤゲートによって構成されており、図１のＮＯＲゲートラッチ１００とは異なる働きをすることに注意されたい。従って、図４に示したように、「ラッチ０」及び「ラッチ１」と付けられたラッチ３２０-１、３２０-２の出力は、それぞれ、取得信号が高いたびに、潜在的に不確定である。当業者にとって明らかであるように、各ラッチ３２０-１、３２０-２においてＮＡＮＤゲートの一方の出力が、該ラッチ３２０-１、３２０-２の出力として指定されているが、いずれのＮＡＮＤゲートの出力も（これらは、ほぼ同一であるので）、選択されることができる。ラッチ３２０のそれぞれにおける不均一な遅延の結果として、及び準安定挙動からの不均一な遅延の結果として、潜在的に不確定な信号が発生されることができる。従って、乱数発生器３００を、同期アプリケーションに適するようにするために、具体的な仕組みが、図３Ｂにおいて提供されており、該仕組みは、波形ラッチ０及びラッチ１を互いに同期させる。図３Ａ及び３Ｂの回路は、同様の文字の丸印を接続することによって、連結される。
【００１５】
図３Ｂに示されている同期回路は、各ラッチ３２０に関連する複数の直列フリップフロップ３３２−ｎ、３３４−ｎ、３３６−ｎを含んでいる。直列フリップフロップ３３２、３３４及び３３６は、準安定状態に容易に入らないように選択されている。これに加えて、これらのフリップフロップ３３２、３３４及び３３６の１つが、準安定になった場合、クロック信号の周期は、前記準安定フリップフロップの出力が、該信号が隣のフリップフロップ３３２、３３４及び３３６においてサンプリングされるような場合に、準安定フリップフロップの出力が、固定された論理値（０又は１のいずれか）に落ち着くように、十分長いものであるべきである。このように、各フリップフロップ３３２、３３４及び３３６は、ラッチ０又はラッチ１の出力と互いとを同期させる確率を改善すると同時に、いかなる不確定な論理状態も取り除く。実際に、このような回路の間違った挙動の確率は、１０年以内に測定されるであろう。
【００１６】
排他的論理和ゲート（「ＸＯＲ」）３５０は、波形ラッチ０及びラッチ１の同期バージョンを比較する。前記２つの出力が異なる場合及び場合のみ、ＸＯＲゲート３５０の出力は高いので、波形ラッチ０が、波形ラッチ１と整合しない場合、ＸＯＲゲート３５０の出力（「誤り」）は、高い。前記誤りは、（ｉ）一方のラッチ３２０が準安定になり、他方のラッチ３２０が安定のままである場合；（ｉｉ）両方のラッチ３２０が準安定になるが、異なる最終状態に到達する場合；又は（ｉｉｉ）フリップフロップ３３２、３３４、３３６を準安定状態に駆動する場合によって、生じ得る。どの場合においても、誤りは、比較的まれな事象であるはずであって、例えば、実施技術及び回路配置に依存する。代替的実施例においては、誤りは、互いに整合する波形ラッチ０及びラッチ１であると定義され得ることに留意されたい。
【００１７】
ＸＯＲゲート３５０の出力は（「誤り」）は、シフトレジスタ３６０のシフト入力（Ｓｈｉｆｔ＿ｉｎ）に供給され、シフトレジスタ３６０は、誤りがあるたびに、ＬＦＳＲ信号（後述）からビットをシフトさせる。シフトレジスタ３６０は、取得信号によってクロックされる。従って、本発明の第１実施例は、エラー（誤り）があるたびに、ビットを収集する。シフトレジスタ３６０の出力は、コンピュータインターフェース３７０に供給される。
【００１８】
図４に示されているように、誤りは、時間ｔ０において、ＸＯＲゲート３５０によって検出され、ビットを、（ＬＦＳＲ信号に基づく）取得されるべき１に等しくする。同様に、誤りは、時間ｔ１において、ＸＯＲゲート３５０によって検出され、ビットを、（ＬＦＳＲ信号に基づく）取得されるべき０に等しくする。
【００１９】
前述のように、入力ビットを、図３Ａ及び３Ｂの結合において上述した方式でマークし、取得信号を発生することは、ランダム出力ビットの一様な分布を供給する。しかしながら、準安定の期間及び出現が、ノイズによる影響を受け得ることが分かっている。従って、ノイズが、取得信号に相関している場合、乱数発生器の出力はランダムではなくなる。
【００２０】
従って、本発明の実施例によれば、（０及び１の頻度に関して）ほぼ不偏の信号ソースが、マーキング信号として使用される。前記マーキング信号は、当該システムにおけるいかなるノイズに対する高い確率と、相関していないものである。本発明は、オプションとして、線形帰還シフトレジスタ（ＬＦＳＲ）３８０であって、前記相関関係の確率を低下させ、該ＬＦＳＲの出力におけるいかなる偏りも減少するのに十分な長さを有するＬＦＳＲ３８０を使用する。適切であるＬＦＳＲは、例えば、「Bruce Schneier, Applied Cryptography, pages 369-388 (Wiley, １９９４年)」に記載されている。線形帰還シフトレジスタの動作の更に詳細な議論に関しては、以下で参考のために示す、２００１年７月２５日に出願された米国特許出願第０９／９１２，６８５号明細書を参照していただきたい。線形帰還シフトレジスタ３８０は、図４に示されているようにＬＦＳＲマーク信号を発生し、該ＬＦＳＲマーク信号は、自身の出力のやや半分以上を、波形における０として作成する。このようにして、ＬＦＳＲマーク信号は、いかなるノイズに対する高い確率とも、無相関である。
【００２１】
線形帰還シフトレジスタ３８０は、相関関係の確率を低下させ、該ＬＦＳＲの出力におけるいかなる偏りも低減するために、十分な数のビットを供給するべきである。ｎ個のフリップフロップで構成される線形帰還シフトレジスタ３８０に関しては、数字が繰り返しを開始する前に、２ｎ−１個のバイナリ数がある。
【００２２】
従って、線形帰還シフトレジスタ３８０におけるフリップフロップの数が増加するので、前記２ｎ−１バイナリ数表示の該−１は、あまり重要でなくなる。いかなる事象においても、前記−１の項に起因するいかなる偏りの検出も、既知であるので、前記偏りは、取り除かれる又は適切な回路によって訂正される。
【００２３】
従って、線形帰還シフトレジスタ３８０は、マーキング出力、即ち擬ランダムであるＬＦＳＲマークを出力し、ここで、出力ビットのほぼ半分は０であり、該出力ビットの他の半分は１である。
【００２４】
線形帰還シフトレジスタ３８０が、不安定である場合、前記出力の一部（ランダム部でさえも）は、線形帰還シフトレジスタの３８０の状態が知られることを可能にすることが、観測されている。このようにして、乱数発生器３００の出力を予測することが可能になるであろう。
【００２５】
従って、識別可能である統計を全く有さない線形帰還シフトレジスタ３８０が、利用されるべきであり、この結果、該線形帰還シフトレジスタ３８０の状態情報を、無用にする。更なる変型においては、付加的な安全は、シフトレジスタ３６０からの収集されたビットを解放し、該収集したビットの一部が、各収集間隔ごとに消滅させられることを可能にすることによって、達成される。
【００２６】
シフトレジスタ３６０は、誤りがあるたびに、ＬＦＳＲマーク信号からのビットをシフトさせる。このようにして、前記誤りの到着時間は認識されず、線形帰還シフトレジスタ３８０のどのビットが選択されるのかを、予測することができなくなる。
【００２７】
図５は、本発明の代替的な実施例を示している。図５は、少なくとも３個のラッチがある場合に「事象」（例えば、誤り）が生じているときを決定する選択回路５００を示している。模範的な選択回路５００は、ＡＮＤゲートを使用して実施されている。ｎ個のラッチのそれぞれの出力が、該選択回路５００の入力において受信され、ゾーンｎとラベルを付けられている。この模範的な実施例においては、ｎは８に等しい。各ゾーン入力及び、これらの反転されたバージョンは、それぞれ、対応する多重化装置５１０−ｎに供給される。各多重化装置５１０は、制御信号（Ｃｏｎｔｒｏｌ＿Ｍ）によって制御され、これは、ゾーン入力又はこれらの対応する反転されたバージョンを選択する。
【００２８】
選択回路５００は、ＡＮＤゲート５２０-１ないし５２０−ｎ−１の配列を含み、ここで、ｎ個のＡＮＤゲートのそれぞれは、図５に示されているように、２及びｎの間の入力を受け取る。各ＡＮＤゲート５２０は、供給された入力パターンが有効である場合、１のバイナリ値を発生する。例えば、ＡＮＤゲート回路５２０−ｎ−１は、（ゾーン０及びゾーン１からの）両方の入力が、高い（ほぼ同一のラッチに関して、期待される条件）である場合にのみ、１を発生する。
【００２９】
しかしながら（又は、逆もまた同様に）、Ｃｏｎｔｒｏｌ＿Ｍ信号の適切な選択によって、ゾーン０における反転された入力と、ゾーン１における前記反転された入力とを選択することによって、ＡＮＤゲート回路５２０−ｎ−１は、ゾーン０が１の値を有する、及びゾーン１が０の値を有する（即ち、これらは異なっており、このことは、ほぼ同一のラッチに関して見込まれない条件である）たびに、１を発生する。前記ラッチ（図５には示されていない）が、ほぼ対称であるので、非反転出力が、所与のラッチの出力として、任意に指定され得ることは、同様に起こり得ることに、再度、留意されたい。従って、多重化装置５１０は、正しい配置が選択されることを可能にし、ここで、前記ラッチは、準安定条件の下にのみ、一致しない。例えば、時折のみ準安定挙動を示す組み合わせが識別されるまで（準安定挙動をいつも示す又は決して示さない組み合わせは、望まれていないため）、様々な組み合わせが評価されることができる。
【００３０】
しかしながら、ＡＮＤゲート５２０−ｎ−１は、ゾーン０が０の値を有し、ゾーン１が１の値を有する（ＸＯＲ実施に関して、ある程度の効率の損失につながる）場合、１を発生しない。同様に、ＡＮＤゲート５２０−ｎ−１は、ゾーン０及びゾーン１の両方が、０又は１（これらが一致する）値を有する場合、１を発生しない。模範的な選択回路５００は、８個までのラッチが、様々な方式で結合され、ランダムビットの発生を起動する「事象」を作成することを可能にする。
【００３１】
上述の実施例及び変型は、本発明の本質を単に示しているのであって、様々な変更が、当業者によって、添付請求項の範囲から逸脱することなしに、実施されることができることに留意されたい。
【図面の簡単な説明】
【００３２】
【図１】図１は、従来型Ｒ−Ｓラッチを示している。
【図２】図２は、各入力の組み合わせに対する、図１のＲ−Ｓラッチの種々の出力値を示している表である。
【図３Ａ】図３Ａは、本発明による乱数発生器を、総合的に示している。
【図３Ｂ】図３Ｂは、本発明による乱数発生器を、総合的に示している。
【図４】図４は、図３Ａ及び３Ｂの回路によって生じる波形の集合を示している。
【図５】図５は、本発明の１つの実施例において使用されることができる選択回路を示しており、該選択回路は、複数のラッチが使用される場合に、準安定事象を検出する。
【図１】
2005530270.tif 000003
【図２】
2005530270.tif 000004
2005530270.tif 000005
2005530270.tif 000006
【図４】
2005530270.tif 000007
【図５】
2005530270.tif 000008
【国際調査報告】
2005530270.tif 000009
2005530270.tif 000010
2005530270.tif 000011