(57)【要約】      （修正有）【課題】決定論的事後処理を必要としない乱数発生器および乱数発生方法を提供する。【解決手段】不均等または均等周期の発振ディジタル出力信号Ａ１、Ａ２、．．．、ＡＬが、少なくとも２つのリング発振器３２、３３、３４によって発生され、論理状態「０」、「１」を表す外部パリティ信号ＰＳが、奇数個の出力信号Ａ１、Ａ２、．．．、ＡＬが特定の論理状態「１」を取るときに発生される乱数発生方法に関する。外部パリティ信号ＰＳは、それぞれのリング発振器の外部パリティ入力３６、３７、３８へフィードバックされる。本発明において、カオス理論（パリティ信号のフィードバック）とディジタル回路における真のランダム性（熱雑音に起因するジッタ）との協力が、乱数を発生する新規な理論的原理として、効率的な実際的解決法を導いた。【選択図】図１
2006139756.tif 000002
【特許請求の範囲】
【請求項１】
均等または不均等周期の発振ディジタル出力信号（Ａ１、Ａ２、．．．、ＡＬ）が、少なくとも２つのリング発振器（３２、３３、３４、４１、４２、４３、７１、７２、７３、８１、８２、８３、８４）によって発生され、論理状態（「０」、「１」）を表す外部パリティ信号（ＰＳ）が発生され、前記外部パリティ信号が、奇数個の出力信号（Ａ１、Ａ２、．．．、ＡＬ）が論理状態「１」を示すときにのみ論理状態「１」を取り、そうでなければ論理状態「０」を取り、外部パリティ信号（ＰＳ）がそれぞれのリング発振器（３２、３３、３４、４１、４２、４３、７１、７２、７３、８１、８２、８３、８４）の外部パリティ入力（３６、３７、３８、４５、４６、４７）へフィードバックされる乱数発生方法。
【請求項２】
各々のリング発振器（３２、３３、３４、４１、４２、４３、７１、７２、７３、８１、８２、８３、８４）について、各々の場合に、それぞれのリング発振器（３２、３３、３４、４１、４２、４３、７１、７２、７３、８１、８２、８３、８４）の出力信号（Ａ１、Ａ２、．．．、ＡＬ）またはそれぞれのリング発振器（３２、３３、３４、４１、４２、４３、７１、７２、７３、８１、８２、８３、８４）の外部パリティ入力（３６、３７、３８、４５、４６、４７）へフィードバックされた信号が特定の論理状態（「１」）を取るときに、所定の論理状態（「０」、「１」）を表す内部パリティ信号（Ｐ１、Ｐ２、Ｐ３、Ｐ４、．．．、ＰＬ）が発生される、請求項１に記載の方法。
【請求項３】
論理状態（「０」、「１」）を表す更なるパリティ信号（ＰＰ）が発生され、前記更なるパリティ信号が、奇数個の内部パリティ信号（Ｐ１、Ｐ２、Ｐ３、Ｐ４、．．．、ＰＬ）が論理状態「１」を示すときにのみ論理状態「１」を取り、そうでなければ論理状態「０」を取る、請求項２に記載の方法。
【請求項４】
内部パリティ信号（Ｐ１、Ｐ２、Ｐ３、Ｐ４、．．．、Ｐｚ）の信号遷移が、パリティ信号発生の前にカウントされる、請求項３に記載の方法。
【請求項５】
少なくとも１つのリング発振器（３２、３３、３４、４１、４２、４３、７１、７２、７３、８１、８２、８３、８４）が、対応するリング発振器（３２、３３、３４、４１、４２、４３、７１、７２、７３、８１、８２、８３、８４）の対応する入力（スタート／ストップ）へ供給されたスタート信号（「１」）の助けによって発振へ励起される、請求項１から４のいずれか一項に記載の方法。
【請求項６】
全てのリング発振器（３２、３３、３４、４１、４２、４３、７１、７２、７３、８１、８２、８３、８４）が、同じスタート信号（「１」）の助けにより、好ましくは同時に発振へ励起される、請求項５に記載の方法。
【請求項７】
外部パリティ信号（ＰＳ）が、少なくとも１つの外部パリティ入力（４７）へフィードバックされる前に反転される、請求項１から６のいずれか一項に記載の方法。
【請求項８】
外部パリティ信号（ＰＳ）が、少なくとも１つの外部パリティ入力（４７）へフィードバックされる前に遅延される、請求項１から７のいずれか一項に記載の方法。
【請求項９】
外部パリティ信号（ＰＳ）が、異なった外部パリティ入力（３６、３７、３８、４５、４６、４７）へフィードバックされる前に、異なった持続時間だけ遅延される、請求項８に記載の方法。
【請求項１０】
第１のリング発振器（３２、３３、３４、４１、４２、４３、７１、７２、７３、８１、８２、８３、８４）によって発生された出力信号（Ａ１、Ａ２、．．．、ＡＬ）の周期（値において、ゲートの遅延時間の奇数倍（Ｋ１、Ｋ２、Ｋ３、．．．、ＫＬ）に等しい）と、第１のリング発振器（３２、３３、３４、４１、４２、４３、７１、７２、７３、８１、８２、８３、８４）の外部パリティ入力（３６、３７、３８、４５、４６、４７）における外部パリティ信号（ＰＳ）の遅延持続時間（値において、ゲートの遅延時間の倍数（Ｍ１、Ｍ２、Ｍ３、．．．、ＭＬ）に等しい）との合計が、ゲートの遅延時間の奇数倍（Ｋ１、Ｋ２、Ｋ３、．．．、ＫＬ）に等しく、第２のリング発振器（３２、３３、３４、４１、４２、４３、７１、７２、７３、８１、８２、８３、８４）によって発生された出力信号（Ａ１、Ａ２、．．．、ＡＬ）の周期（値において、ゲートの遅延時間の奇数倍に等しい）と、第２のリング発振器（３２、３３、３４、４１、４２、４３、７１、７２、７３、８１、８２、８３、８４）の外部パリティ入力（３６、３７、３８、４５、４６、４７）における外部パリティ信号（ＰＳ）の遅延持続時間（値において、ゲートの遅延時間の倍数（Ｍ１、Ｍ２、Ｍ３、．．．、ＭＬ）に等しい）との合計が、ゲートの遅延時間の偶数倍に等しくなるように、リング発振器（３２、３３、３４、４１、４２、４３、７１、７２、７３、８１、８２、８３、８４）の周期およびリング発振器（３２、３３、３４、４１、４２、４３、７１、７２、７３、８１、８２、８３、８４）の外部パリティ入力（３６、３７、３８、４５、４６、４７）における外部パリティ信号（ＰＳ）の遅延持続時間が選択される、請求項９に記載の方法。
【請求項１１】
外部パリティ信号（ＰＳ）がランダム・ビット（７８）を発生する特定のレート（ｖ）でサンプリングされるか、更なるパリティ信号（ＰＰ）が、ランダム・ビット（７８）を発生する特定のレート（ｖ）でサンプリングされる、請求項１から１０のいずれか一項に記載の方法。
【請求項１２】
複数の外部の、特にサンプリングされたパリティ信号（ＰＳ）が発生され、論理状態（「０」、「１」）を表すスーパー・パリティ信号（ＳＰ）が発生され、このスーパー・パリティ信号が、外部の、特にサンプリングされたパリティ信号（ＰＳ）の奇数個が論理状態「１」を示すときにのみ論理状態「１」を取り、そうでなければ論理状態「０」を取るか、複数の更なる、特にサンプリングされたパリティ信号が発生され、論理状態（「０」、「１」）を表すスーパー・パリティ信号（ＳＰ）が発生され、前記スーパー・パリティ信号が、更なる、特にサンプリングされたパリティ信号の奇数個が論理状態「１」を示すときにのみ論理状態「１」を取り、そうでなければ論理状態「０」を取る、請求項１から１１のいずれか一項に記載の方法。
【請求項１３】
外部または更なるパリティ信号（ＰＳ）が、ランダム・ビット（ＺＢ）を発生する特定のレート（ｖ）で同期的にサンプリングされるか、スーパー・パリティ信号（ＳＰ）が、ランダム・ビット（ＺＢ）を発生する特定のレート（ｖ）でサンプリングされる、請求項１２に記載の方法。
【請求項１４】
サンプリングが、ランダムな非均一サンプリング時間間隔で実行され、特に、請求項１から１２のいずれか一項に記載の方法によってランダムに発生されるランダム・ビット（ＺＢ）が所定の論理状態（「１」）を取るときにサンプリングが実行される、請求項１１から１３のいずれか一項に記載の方法。
【請求項１５】
奇数（Ｋ）個の直列接続インバータ（ｉｎｖ１，２、ｉｎｖ２，１、ｉｎｖ３，１、．．．、ｉｎｖｉ，ｊ、．．．、ｉｎｖＬ，ＫＬ）を有するフィードバック付独立自由走インバータ・チェーンから特に構成され、不均等な周期の発振ディジタル出力信号（Ａ１、Ａ２、．．．、ＡＬ）を発生する少なくとも２つのリング発振器（３２、３３、３４、４１、４２、４３、７１、７２、７３、８１、８２、８３、８４）、および所定の論理状態（「０」、「１」）を表す外部パリティ信号（ＰＳ）を発生し、前記外部パリティ信号が、奇数個の出力信号（Ａ１、Ａ２、．．．、ＡＬ）が論理状態「１」を示すときにのみ論理状態「１」を取り、そうでなければ論理状態「０」を取る第１のパリティ信号発生手段（ＸＯＲ）を有する乱数発生器であって、それぞれのリング発振器（３２、３３、３４、４１、４２、４３、７１、７２、７３、８１、８２、８３、８４）の外部パリティ入力（３６、３７、３８、４５、４６、４７）へ外部パリティ信号（ＰＳ）をフィードバックするフィードバック手段（ｘｏｒ１、ｘｏｒ２、ｘｏｒ３、ｘｏｒ４、．．．、ｘｏｒＬ）が存在する乱数発生器。
【請求項１６】
第１のパリティ信号発生手段がＸＯＲゲート（ＸＯＲ）を有し、前記ＸＯＲゲートの入力に出力信号（Ａ１、Ａ２、．．．、ＡＬ）が存在する、請求項１５に記載の乱数発生器。
【請求項１７】
各々のリング発振器（３２、３３、３４、４１、４２、４３、７１、７２、７３、８１、８２、８３、８４）について、特定の論理状態（「１」）を表す内部パリティ信号（Ｐ１、Ｐ２、Ｐ３、Ｐ４、．．．、ＰＬ）を発生する第２のパリティ信号発生手段（ｘｏｒ１、ｘｏｒ２、ｘｏｒ３、．．．、ｘｏｒＬ）が存在し、前記内部パリティ信号が、それぞれのリング発振器（３２、３３、３４、４１、４２、４３、７１、７２、７３、８１、８２、８３、８４）の出力信号またはそれぞれのリング発振器（３２、３３、３４、４１、４２、４３、７１、７２、７３、８１、８２、８３、８４）の外部パリティ入力（３６、３７、３８、４５、４６、４７）へフィードバックされた信号が特定の論理状態（「１」）を取るときにのみ論理状態「１」を取る、請求項１５または１６に記載の乱数発生器。
【請求項１８】
第２のパリティ信号発生手段がＸＯＲゲート（ｘｏｒ１、ｘｏｒ２、ｘｏｒ３、．．．、ｘｏｒＬ）を含み、前記ＸＯＲゲートの各々が外部パリティ入力および出力信号入力を有し、外部パリティ信号（ＰＳ）から引き出された信号がパリティ入力に存在し、それぞれのリング発振器（３２、３３、３４、４１、４２、４３、７１、７２、７３、８１、８２、８３、８４）のそれぞれの出力信号（Ａ１、Ａ２、．．．、ＡＬ）が出力信号入力に存在する、請求項１７に記載の乱数発生器。
【請求項１９】
論理状態（「０」、「１」）を表す更なるパリティ信号（ＷＰ）を発生する第３のパリティ信号発生手段が存在し、前記更なるパリティ信号が、奇数個の内部パリティ信号（Ｐ１、Ｐ２、Ｐ３、Ｐ４、．．．、ＰＬ）が論理状態「１」を示すときにのみ論理状態「１」を取り、そうでなければ論理状態「０」を取る、請求項１８に記載の乱数発生器。
【請求項２０】
パリティ信号発生の前に内部パリティ信号（Ｐ１、Ｐ２、Ｐ３、．．．、ＰＬ）の信号遷移をカウントするカウンティング手段（８８１、８８２、．．．、８８Ｌ）が存在する、請求項１９に記載の乱数発生器。
【請求項２１】
カウンティング手段がバイナリ・カウンタ（８８１、８８２、．．．、８８Ｌ）、特にフリップフロップ、好ましくはＪＫフリップフロップ（ＪＫ１、ＪＫ２、．．．、ＪＫＺ）を有するチェーンを含む、請求項２０に記載の乱数発生器。
【請求項２２】
スタート信号（「１」）を発生し、少なくとも１つのリング発振器（３２、３３、３４、４１、４２、４３、７１、７２、７３、８１、８２、８３、８４）の入力（スタート／ストップ）へ前記スタート信号を供給して、このリング発振器が発振へ励起されるようにするスタート手段が存在する、請求項１５から２１のいずれか一項に記載の乱数発生器。
【請求項２３】
少なくとも１つのリング発振器（３２、３３、３４、４１、４２、４３、７１、７２、７３、８１、８２、８３、８４）が、入力側のインバータ（ｉｎｖ１）の代わりにＮＡＮＤゲート（ｎａｎｄ１、ｎａｎｄ１，１、ｎａｎｄ２，１、ｎａｎｄ３，１、．．．、ｎａｎｄｉ，１、．．．、ｎａｎｄＬ，１）を含み、前記ＮＡＮＤゲートが、スタート信号（「１」）を供給する入力（スタート／ストップ）を有する、請求項２２に記載の乱数発生器。
【請求項２４】
全てのリング発振器（３２、３３、３４、４１、４２、４３、７１、７２、７３、８１、８２、８３、８４）が同じスタート信号（「１」）のを用いて、好ましくは同時に発振へ励起されるように、スタート手段が構成される、請求項２２または２３に記載の乱数発生器。
【請求項２５】
全てのリング発振器（３２、３３、３４、４１、４２、４３、７１、７２、７３、８１、８２、８３、８４）が、各々の場合に、入力側のインバータ（ｉｎｖ１）の代わりにＮＡＮＤゲート（ｎａｎｄ１、ｎａｎｄ１，１、ｎａｎｄ２，１、ｎａｎｄ３，１、．．．、ｎａｎｄｉ，１、．．．、ｎａｎｄＬ，１）を含み、前記ＮＡＮＤゲートが、各々の場合に、スタート信号（「１」）を供給するため相互に接続される入力（スタート／ストップ）を有する、請求項２４に記載の乱数発生器。
【請求項２６】
少なくとも１つの外部パリティ入力（４７）の前にインバータ（ｉｎｖ３，−１、ｉｎｖ１，−Ｍ１、．．．、ｉｎｖ１，−１、．．．、ｉｎｖＬ，−ＭＬ、．．．、ｉｎｖＬ，−１が接続され、前記インバータへ外部パリティ信号（ＰＳ）が供給される、請求項１５から２５のいずれか一項に記載の乱数発生器。
【請求項２７】
全ての外部パリティ入力の前に、不等価の個数（Ｍ１、Ｍ２、．．．、ＭＬ）のインバータ（ｉｎｖ１，−Ｍ１、ｉｎｖ１，−１、．．．、ｉｎｖＬ，−ＭＬ、ｉｎｖＬ，−１）を有するインバータ・チェーンが接続され、前記インバータ・チェーンへ外部パリティ信号（ＰＳ）が供給される、請求項２６に記載の乱数発生器。
【請求項２８】
第１のリング発振器（３２、３３、３４、４１、４２、４３、７１、７２、７３、８１、８２、８３、８４）によって発生された出力信号（Ａ１、Ａ２、．．．、ＡＬ）の周期（値において、ゲートの遅延時間の奇数倍（Ｋ１、Ｋ２、Ｋ３、．．．、ＫＬ）に等しい）と、第１のリング発振器（３２、３３、３４、４１、４２、４３、７１、７２、７３、８１、８２、８３、８４）の外部パリティ入力（３６、３７、３８、４５、４６、４７）における外部パリティ信号（ＰＳ）の遅延持続時間（値において、ゲートの遅延時間の倍数（Ｍ１、Ｍ２、Ｍ３、．．．、ＭＬ）に等しい）との合計が、ゲートの遅延時間の奇数倍に等しく、第２のリング発振器（３２、３３、３４、４１、４２、４３、７１、７２、７３、８１、８２、８３、８４）によって発生された出力信号（Ａ１、Ａ２、．．．、ＡＬ）の周期（値において、ゲートの遅延時間の奇数倍（Ｋ１、Ｋ２、Ｋ３、．．．、ＫＬ）に等しい）と、第２のリング発振器（３２、３３、３４、４１、４２、４３、７１、７２、７３、８１、８２、８３、８４）の外部パリティ入力（３６、３７、３８、４５、４６、４７）における外部パリティ信号（ＰＳ）の遅延持続時間（値において、ゲートの遅延時間の倍数（Ｍ１、Ｍ２、Ｍ３、．．．、ＭＬ）に等しい）との合計が、ゲートの遅延時間の偶数倍に等しい、請求項２７に記載の乱数発生器。
【請求項２９】
ランダム・ビット（ＺＢ）を発生する特定のレート（ｖ）で外部パリティ信号（ＰＳ）をサンプリングするサンプリング手段が存在し、および／またはランダム・ビット（ＺＢ）を発生する特定のレート（ｖ）で更なるパリティ信号（ＰＰ）をサンプリングするサンプリング手段が存在する、請求項１５から２８のいずれか一項に記載の乱数発生器。
【請求項３０】
請求項１５から２９のいずれか一項に記載の乱数発生器の複数個が存在し、これらの乱数発生器が外部の、特にサンプリングされたパリティ信号（ＰＳ）を発生し、論理状態（「０」、「１」）を表すスーパー・パリティ信号（ＳＰ）を発生するスーパー・パリティ信号発生手段が存在し、前記スーパー・パリティ信号が、外部の、特にサンプリングされたパリティ信号（ＰＳ）の奇数個が論理状態「１」を示すときにのみ論理状態「１」を取り、そうでなければ論理状態「０」をとり、および／または請求項１５から２９のいずれか一項に記載の乱数発生器の複数個が存在し、これらの乱数発生器が更なる特にサンプリングされたパリティ信号（ＰＰ）を発生し、論理状態（「０」、「１」）を表すスーパー・パリティ信号（ＳＰ）を発生するスーパー・パリティ信号発生手段が存在し、前記スーパー・パリティ信号が、更なる特にサンプリングされたパリティ信号（ＰＰ）の奇数個が論理状態「１」を示すときにのみ論理状態「１」を取り、そうでなければ論理状態「０」を取る、請求項１５から２９のいずれか一項に記載の乱数発生器。
【請求項３１】
ランダム・ビット（ＺＢ）を発生する特定のレート（ｖ）で外部パリティ信号（ＰＳ）または更なるパリティ信号（ＰＰ）を同期的にサンプリングするサンプリング手段が存在し、および／またはランダム・ビット（ＺＢ）を発生する特定のレート（ｖ）でスーパー・パリティ信号（ＳＰ）をサンプリングするサンプリング手段が存在する、請求項３０に記載の乱数発生器。
【請求項３２】
サンプリング手段が、ランダムな非均一サンプリング時間間隔でサンプリングを実行するように構成され、特に、請求項１５から３１のいずれか一項に記載の乱数発生器によってランダムに発生されたランダム・ビット（ＺＢ）が所定の論理状態（「１」）を取るときサンプリングを実行するように構成された、請求項２９から３１のいずれか一項に記載の乱数発生器。
【請求項３３】
サンプリング手段がＤフリップフロップ（８８１、８８２、．．．、８８Ｌ）を含み、前記Ｄフリップフロップが、クロック（ＣＰ）、特に非安定マルチバイブレータ（８７、８７１、８７２、．．．、８７Ｌ）からのパルスによって駆動されるか、フィードバック付リング発振器（ＲＲＯ）によって駆動される、請求項２９から３２のいずれか一項に記載の乱数発生器。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、請求項１４のプリアンブルに従った乱数発生器、および請求項１のプリアンブルに従った乱数発生方法に関する。
【背景技術】
【０００２】
乱数発生器（ＲＮＧ）は、ランダムなバイナリまたは多価の数（乱数）を自動的に発生するために使用される。乱数発生器は、多くの応用分野で必要とされる。これらの分野は、たとえば、
−  暗号化の応用
−  確率的シミュレーション
−  ソフトウェアおよびハードウェアのテスト
−  コンピュータ・ゲーム
【０００３】
以下では、乱数発生器の暗号化応用に限定して考察する。これらの応用は、たとえば次のものを含む。
−  認証
−  誰何・応答プロトコル
−  ゼロ知識証明
−  鍵共有プロトコル
−  ディフィー・ヘルマン法
−  鍵発生
−  対称暗号化法のセッション鍵
−  非対称暗号化法の鍵発生（公開鍵法）
−  バイナリ・ノイズの発生（一時パッド、マックエライス公開鍵法）
−  公開鍵法のパラメータ発生（たとえばランダム素数の発生）
−  他の暗号化応用
−  パスワード発生
−  決定論的乱数発生器（疑似乱数発生器）の初期値（シード）
−  平文テキスト・ブロックのパディング
−  記憶メディアの安全な消去（ランダム・ビット・パターンによる多数回の上書き）
【０００４】
一般的に、２つの主な種類の発生器、即ち、決定論的発生器（疑似乱数発生器またはＰＲＮＧ）および物理的乱数発生器（真乱数発生器またはＴＲＮＧ）が存在する。決定論的発生器は、ランダムに選択された初期値（ＩＶ）から、はるかに長く、ランダムに見える数のストリングを引き出すアルゴリズム手順である。当然のことながら、このストリング自体は、発生方法の決定論的性格のために、真にランダムではあり得ない。
【０００５】
したがって、実際にランダムな数のストリングを発生するためには、いわゆる物理的乱数発生器を使用することが必要である。これは、非決定論的またはカオス物理的プロセスを使用して乱数を発生する。乱数は、或るプロセス測定値（たとえば、抵抗を横切る熱雑音電圧）を測定および処理することによって発生される。
【０００６】
本発明の目的は、集積回路（ＩＣ）に埋め込むことができ、次の暗号および経済的関連品質規準を満たす物理的乱数発生器を実現することである。
−  通常の大規模集積回路（たとえば論理ゲート）の標準化されたコンポーネントの使用によってのみに実現可能である
−  最少数の可能なコンポーネントを使用して構築する（低コスト、小さな表面積、および低電力消費）
−  他のユニットの影響から保護された自立および独立したユニットとしてＩＣ上に埋め込まれる
−  ＩＣ上の他のユニットから独立してオンおよびオフできる
−  オンにした後で機能を素早く復元する（短いウォームアップ時間）
−  最高可能数のランダム・ビットが単位時間当たりに発生される（高レート）
−  環境条件（温度、電磁干渉、電源電圧の変動など）に関してロバストである
−  侵入および非侵入の操作試行（攻撃）に関してロバストである
−  受動的攻撃
−  能動的攻撃
−  双方の発生ビットのランダム性の品質を評価するために使用される統計的テストを満足させる
−  発生された乱数の決定論的事後処理ができるだけ少ない
−  動作中に機能および品質テストが可能である（オンライン・テスト）
【０００７】
以下で、暗号化乱数発生器は、ビット・ソースとして実現されるものとする。個々のビットは、用途に依存してブロックへ組み合わせられる（たとえば、データ暗号化標準またはＤＥＳの鍵については、５６ビット）。一般的に、暗号化乱数発生器によって発生されたビット・ストリング（たとえば鍵）は、暗号化システムのセキュリティを危うくしないように、秘密にする必要があると考えなければならい（前述したセクションの応用リストでは、これは誰何・応答プロトコルおよびゼロ知識証明まで、全ての方法について当てはまらない）。これらの場合、乱数発生器は、問題とする暗号化方法の秘密を発生する。この秘密によって、たとえば、平文テキストが暗号化される。もし秘密が攻撃者に知られなければ、攻撃者は、常に、全ての可能なビット・ストリングを選択してみなければならない（完全サーチ）。上記の例において、これは、未知のキーで暗号化された平文テキストを観察した攻撃者が、実際に発生された鍵を発見したと思う前に、（統計的に）平均で２５５の可能な鍵を全て試みなければならないことを意味する。この攻撃は、攻撃者の観点からは最悪の可能なケースである。システムを成功裏に攻撃するためには、攻撃者は、発生器が或る時点で発生する或るビット数を予測できなければならない。これは、発生器によって発生された他のビット・ストリングの知識なしに起こるか、未知のビット・ストリングの前または後に、発生器が発生したビット・ストリングの知識と共に起こることができる。攻撃者は、発生されたビット・ストリングを全体的に、または部分的に、推量しようと試みることができる。後者の場合、攻撃者は、完全サーチによって残りのビットを発見することができる。
【０００８】
そのような予測を行うため、攻撃者は、全ての既知の技術的および科学的ツールへのアクセスを有する。攻撃者は、攻撃に要するコストに関してのみ制限される。これらのコストは、定められたコスト限界（経済学的主題：攻撃による期待利得が攻撃コストを超過しない）よりも下でなければならないと考えることができる。
【０００９】
ビット・ソースは、コスト限界のレベルに依存して様々なセキュリティ・レベルへ分割することができる。もしビット・ソースが所与のコスト限界について全ての攻撃に耐えるならば、そのビット・ソースは、このコスト限界に対して現実的に安全なビット・ソースとして認められなければならない。
【００１０】
図１４は、物理的ビット・ソースの形態をした物理的乱数発生器ＴＲＮＧのモデルを示す。ソースの実質的なコンポーネントは、ダイナミックな予測不可能物理システム、即ち、いわゆるランダム・ソース１である。内部（時間依存）状態は、このランダム・ソース１に関連づけられる。或る時間間隔で、ランダム・ソース１の状態値は、測定および処理されて（値の獲得２）、１つまたは複数のランダム・ビットが発生される（ランダム・ビット発生３）。このようにして発生されたランダム・ビットのストリングは、内部ランダム・ビットと呼ばれる。次に、これらのランダム・ビット・ストリングは、アルゴリズム事後処理５にさらされる。数学的事後処理５は、一般的に、内部乱数の品質を改善するために実行される（ここで依然として、乱数の品質尺度が定められなければならない。詳細は、次のセクションを参照されたい）。一般的には、ランダム抽出５と呼ばれる。これは、成功裏に発生されたビット間の依存性の除去、および多くの場合に存在するバイアス（０および１の不均等分布）の除去を意味する。このようにして発生されたランダム・ビットは、更なるステップで出力され、適宜、出力メモリに記憶される（ランダム・ビット出力５）。
【００１１】
図１４で示されるように、物理的乱数発生器ＴＲＮＧは、隔離されたシステムではなく、物理的環境６に埋め込まれる。測定された状態、したがって発生されたランダム・ビットは、環境６の或る物理量に依存すると考えなければならない。これらの物理量は、たとえば、デバイスへ与えられた電源電圧、外界温度、または電磁場のような量を含む。様々な種類の発生器が、物理的システムの性質に基づいて区別される。物理的システムの２つの本質的な種類は、次のとおりである。
−  量子システム
−  古典的システム
【００１２】
量子システムとは、量子力学の法則によって記述されるシステムを意味する。現在の一般的な科学的知見によれば、（ランダム発生が基礎を置く）そのようなシステムで起こる現象が、真にランダムである。その例は、放射性物質の崩壊プロセスである。
【００１３】
対照的に、古典的システムは、（古典）物理学の決定論的法則によって記述される。このようなシステムが予測不可能であり得ることについて、様々な理由を挙げることができる。多くの自由度を有するシステムにおいて、システム内で起こる相互作用は、多くの場合、正確に予測するにはあまりに複雑である。更に、システムの初期状態は、多くの場合、正確に決定され得ない。この事実は、更に、いわゆるカオスシステムの場合にインパクトを与える。そのようなシステムでは、初期状態での小さな変化が、時間の経過によって、大きく異なった予測不可能システム状態を導く。
【００１４】
暗号化ビット・ソースを評価するためには、そのビット・ソースを、上記で定められた実際的に安全な暗号化ビット・ソースの特性と比較しなければならない。これは、発生されたビット・ストリングの統計的評価、および、いわゆるサイド・チャネル攻撃の可能性のチェックを含む。これらの攻撃は、実際に、乱数発生器が埋め込みシステム内で展開されるとき、大きな重要性を有する。サイド・チャネル攻撃は、発生器によって発生される数を予測する試み、または数の発生に影響を及ぼす試みである。この試みは、発生器の環境から測定値を決定することによって（受動的攻撃）、または環境へ故意の影響を与えることによって（能動的攻撃）、非侵入的に起こる。そのような攻撃の更に悪質なものは、侵入的サイド・チャネル攻撃である（たとえば、ＩＣに孔を空けて信号を測定する）。受動的かつ非侵入的攻撃の典型的なものは、たとえば、発生器からの電磁放射または発生器の電力消費の測定である。
【００１５】
発生器によって発生されたビット・ストリングを統計的に評価するため、様々な統計的テストを利用することができる（たとえば、非特許文献１、非特許文献２、非特許文献３、非特許文献４）。
【００１６】
原理的には、ランダム有限シーケンスの概念を定める問題は、これらの有限ビット・ストリングの評価で生じる。コルモゴロフ（非特許文献５）によれば、有限シーケンスは、もし圧縮不可能であればランダムである。これは、選択されたコンピュータ・モデルを基準とした最短アルゴリズム記述の長さが、シーケンスそれ自体の長さと同一オーダの大きさであることを意味する（これは、コンピュータ・モデルとしてチューリング機械（ドイツ語の原語は「Ｔｕｒｎｉｎｇ−Ｍａｓｃｈｉｎｅ」。−ドイツ語訳者）を使用したときの、いわゆるシーケンスのコルモゴロフ複雑性である）。ここでの基本アイデアは、圧縮可能なシーケンスが、圧縮を可能とするように規則性を示さなければならないことである。したがって、ランダム・シーケンスは、この意味での規則性を示さない。残念ながら、この概念は、ストリングのランダム性の直接テストを導かない。なぜなら、コルモゴロフ複雑性は、計算可能性理論の意味で計算可能ではないからである。
【００１７】
統計的テストは、ランダム（有限）ビット・ストリングに帰される或る特性に関してビット・ストリングをテストできるだけである。これらの特性は、多くの場合、ランダム性の一般的理解に基づく直感的観念から引き出される。実際、ビット・ストリングのランダム性が、コルモゴロフの意味でテストをパスすることを、多数のテストについて示すことができる（非特許文献６）。
【００１８】
物理的乱数発生器は、従来技術からの多数の変形が知られる。乱数発生器の開発の初期には、主として外部乱数発生器、即ち、ＩＣに埋め込まれない発生器が開発された。この目的のために、使用されるランダム・ソースをかなりの範囲で選択することができる。今日の外部乱数発生器において、多数のランダム・ソース、たとえば放射線ソース、抵抗内の電子熱雑音、または環境内のランダム・イベント（たとえばキーボードのキー押下間の時間間隔）が使用される。
【００１９】
乱数発生器が商用ＩＣに埋め込まれたのは、全く最近のことである。この場合、ランダム・ソースの種類、そのＩＣの表面サイズ、技術的実現、および微小化が重要な役割を演じる。しかし今まで、サイド・チャネル攻撃への乱数発生器の免疫性には、ほとんど注意が払われなかった。実現された埋め込み乱数発生器の例は、特許文献１、非特許文献７、非特許文献８、特許文献２、特許文献３、特許文献４、非特許文献９、特許文献５、特許文献６、特許文献７、特許文献８、特許文献９、非特許文献１０に見出される。
【００２０】
本発明は、従来技術による多様な実施形態で開示される、いわゆるインバータ・チェーン乱数発生器から始まる。例として、特許文献７を参照する。
【００２１】
これら乱数発生器の基本的コンポーネントは、いわゆるリング発振器８である。それは、奇数個Ｋのインバータｉｎｖ１、ｉｎｖ２、．．．、ｉｎｖＫ（論理ＮＯＴゲート）の直列接続を含み、最後のインバータｉｎｖＫの出力は、最初のｉｎｖ１の入力へ接続される（図１５ａを参照）。個々のインバータｉｎｖ１、ｉｎｖ２、．．．、ｉｎｖＫの遅延時間の結果として、ゲートｉｎｖ１、ｉｎｖ２、．．．、ｉｎｖＫの個数Ｋが奇数のときにのみ、周期的発振が起こる。
【００２２】
この発振をスタートおよびストップするため、最初のインバータｉｎｖ１を、制御入力スタート／ストップを有するＮＡＮＤゲートｎａｎｄ１で置換することができる（図１５ｂを参照）。もしこの制御入力スタート／ストップが論理１（「１」）にセットされるならば、リング発振器９は発振を始める。
【００２３】
図１６ａは、２つのインバータｉｎｖ２およびｉｎｖ３、および１つのＮＡＮＤゲートｎａｎｄ１を有するＫ＝３のリング発振器１０を示す。図１６ｂは、遅延時間τを有するインバータｉｎｖの入力１１および出力１２における理想化された信号トレースを示す。もし図１６ａのリング発振器１０内のゲートｎａｎｄ１、ｉｎｖ２、ｉｎｖ３が、そのように理想化された振る舞いを示すならば、図１６ｃは、経過時間Ｔの間、入力Ｓが「１」へセットされた後の点Ｓ、Ｂ、Ｃ、およびＡ＝Ａ’における図１６ａのリング発振器１０の理想化された信号トレースを示す。
【００２４】
ＣＭＯＳコンポーネント７４ＨＣＴ０４（入力ＮＡＮＤゲートを有さない。図１７ａ）を使用して、Ｋ＝３を有するリング発振器１０を技術的に実現した場合、オシロスコープで記録された点Ａ’の信号トレース１４は、図１７ｂで示される。信号トレース１４の拡大された詳細（図１７ｂ）によって暗示されるように、回路７４ＨＣＴ０４の導体内の電子の熱運動が熱雑音信号を付加する。図１７ｃは、より長い時間間隔ｔにわたって観察された雑音発振信号１４のエンベロープ１５を示す。注目されるように、信号１４の側面の雑音は、無雑音信号の場合よりも、遅かれ速かれ決定レベルの超過を導く。側面におけるこの時間的ランダム・シフトは、「ジッタ」と呼ばれる。固定された時間ｔ１（図１７ｃ）を基準として観察された最大可能側面シフト間の差は、参照文字Δで示される。この差Δの大きさは、参照時間ｔ１からの側面距離と共に増加する。この現象は「ジッタ累積」として知られる。
【００２５】
約２５ＭＨｚの周波数ｆを有し、０．２ｓの間に５１２回平均された図１７ａからのリング発振器１０の発振信号１４は、図１８に示される。この平均された信号のエンベロープ１３は、トリガ点からの様々な時間間隔について自己相関の振る舞いを示す。図１８から分かるように、信号１４は、約０．２８ｓの後になるまで、累積ジッタによって完全には非相関化されない。
【００２６】
これは、３Ｈｚ以下のサンプリング・レートｖでのみ、発生されたビットが非相関化され、したがってランダム・ビット・ソースとして使用され得ることを意味する。発生されたランダム・ビットの最大可能レートｖｍａｘを増加するため、様々な周期（即ち、様々なＫ値）を有する複数のリング発振器を組み合わせることができる。図１９は、Ｌ個のリング発振器１７、１８、１９、２０、２１、２２に基づく回路配列の２つの例示的実施形態を示す。ここで、各々の場合に、出力のパリティ・チェック（いわゆるＸＯＲ結合）が実行される。具体的には、これは、それぞれのリング発振器１７、１８、１９、２０、２１、２２の出力がＸＯＲゲートｘｏｒの入力へ接続され、奇数個の論理「１」信号がリング発振器１７、１８、１９、２０、２１、２２の出力に存在するときにのみ、「１」信号がＸＯＲゲートｘｏｒの出力に発生されることを意味する。偶数個の論理「１」値は、ＸＯＲゲートの出力に「０」信号を発生するであろう。この理由によって、ＸＯＲゲートｘｏｒの出力信号は、以下ではパリティ信号ＰＳと呼ばれる。
【００２７】
図１９ａおよび図１９ｂの２つの回路は、リング発振器１７、１８、１９、２０、２１、２２のスタート／ストップ入力の構成でのみ異なる。図１９ａの最初の実施形態において、個々のリング発振器１７、１８、１９のスタート／ストップ入力は一緒に駆動される。図１９ｂで示される２番目の可能実施形態は、入力を別々に駆動することによって、個々の発振信号の初期位相を相互に対してシフトする。
【００２８】
図２０ａは、普通のスタート／ストップ信号を有する２つのリング発振器２４、２５のパリティ・チェックを有する回路を示す。図２０ｂおよび図２０ｃで分かるように、パリティ信号ＰＳ２９の周期Ｐは一定に維持される。個々のリング発振器信号２７および２８の遅い位相シフトの結果として、パリティ信号ＰＳの信号トレース２９は、図２１ａで明瞭に分かるように、より長い時間間隔の周期Ｐ内では変化する。図２１ｂの約０．２ｓの時間では、パリティ信号ＰＳ２９のエンベロープ３０は、個々のコンポーネントの自己相関（図１８を参照）よりも小さい可変の自己相関を表示する。リング発振器のこのパリティ・チェックは、乱数発生器の多くの実現で使用される。この手法では、相関を完全には除去することができず、したがって追加のレート低減決定論的事後処理が避けられない。
【００２９】
【特許文献１】独国特許出願公開第１０１１７３６２号明細書
【特許文献２】米国特許出願公開第２００２／０１８６０８６号明細書
【特許文献３】米国特許第４，８５５，６９０号明細書
【特許文献４】独国特許第１０１０３０７１号明細書
【特許文献５】米国特許第５，７０６，２１８号明細書
【特許文献６】国際公開第０３／０８１４１７号パンフレット
【特許文献７】独国特許出願公開第１０２１３２６９号明細書
【特許文献８】米国特許出願公開第２００３／０１８５３９２号明細書
【特許文献９】欧州特許出願公開第１３４３０７３号明細書
【非特許文献１】Ｋｉｌｌｍａｎｎ，  Ｗｏｌｆｇａｎｇ，  および  Ｗｅｒｎｅｒ  Ｓｃｈｉｎｄｌｅｒ，「物理的乱数発生器の機能分類および評価手順に関する提案」（Ｅｉｎ  Ｖｏｒｓｃｈｌａｇ  ｚｕ  ：  Ｆｕｎｋｔｉｏｎａｌｉｔａｔｓｋｌａｓｓｅｎ  ｕｎｄ  Ｅｖａｌｕａｔｉｏｎｓｍｅｔｈｏｄｏｌｏｇｉｅ  ｆｕｒ  ｐｈｙｓｉｋａｌｉｓｃｈｅ  Ｚｕｆａｌｌｓｚａｈｌｅｎｇｅｎｅｒａｔｏｒｅｎ），  Ｂｕｎｄｅｓａｍｔ  ｆｕｒ  Ｓｉｃｈｅｒｈｅｉｔ  ｉｎ  ｄｅｒ  Ｉｎｆｏｒｍａｔｉｏｎｓｔｅｃｈｎｉｋ  （２００１）
【非特許文献２】Ｍａｒｓａｇｌｉａ，  Ｇ．，「Ｄｉｅｈａｒｄ：  ランダム性テスト・バッテリ」，  ＵＲＬ  ｈｔｔｐ：／／ｓｔａｔ．ｆｓｕ．ｅｄｕ／ｐｕｂ／ｄｉｅｈａｒｄ／（１９９６）
【非特許文献３】Ｒｕｈｋｉｎ，  Ａ．  Ｌ．，  Ｊ．  Ｓｏｔｏｔ，  Ｎｅｃｈｖａｔａｌ，  Ｍ．  Ｓｍｉｄ，  Ｍ．  Ｌｅｖｅｎｓｏｎ，  Ｄ．  Ｂａｎｋｓ，  Ｍ．  Ｖａｎｇｌｅ，  Ｓ．  Ｌｅｉｇｈ，  Ｓ．  Ｖｏ  および  Ｊ．  Ｄｒａｙ，「暗号化乱数発生器の有効性の統計的テスト・スイート」，  Ｎａｔｉｏｎａｌ  Ｉｎｓｔｉｔｕｔｅ  ｏｆ  Ｓｔａｎｄａｒｄｓ  ａｎｄ  Ｔｅｃｈｎｏｌｏｇｙ，  Ｇａｉｔｈｅｒｓｂｕｒｇ，  ＭＤ  （２０００）
【非特許文献４】Ｋａｌｉｓｋｉ，  Ｂｕｒｔｏｎ  Ｓ．，  Ｊｒ．，  Ｃｅｔｉｎ  ｋａｙａ  Ｋｏｃ  および  Ｃｈｒｉｓｔｏｆ  Ｐａａｒ  （Ｅｄｓ．），「暗号化ハードウェアおよび埋め込みシステム−ＣＨＥＳ  ２００２，  ４ｔｈ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｗｏｒｋｓｈｏｐ，  Ｒｅｄｗｏｏｄ  Ｓｈｏｒｅｓ，  ＣＡ，  Ｕ．Ｓ．Ａ．，  Ａｕｇｕｓｔ  １３−１５，  ２００２，  Ｒｅｖｉｓｅｄ  Ｐａｐｅｒｓ」，  Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ，  Ｖｏｌ．２５２３，  Ｓｐｒｉｎｇｅｒ  （２００３），  ＩＳＢＮ  ３−５４０−００４０９−２，  ｐｐ．  １−２  内の  Ｓｃｈｉｎｄｌｅｒ，  Ｗｅｒｎｅｒ，「暗号化応用で使用される真（物理的）乱数発生器の評価規準」
【非特許文献５】Ｋｏｌｍｏｇｏｒｏｖ，  Ａｎｄｒｅｉ  Ｎ．，「情報の量的定義への３つのアプローチ」，  ｉｎ  Ｐｒｏｂｌｅｍｓ  ｉｎ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｔｒａｎｓｍｉｓｓｉｏｎ  １  （１９６５），  Ｎｏ．  １
【非特許文献６】Ｌｉ，  Ｍｉｎｇ，  および  Ｐａｕｌ  Ｖｉｔａｎｎｙｉ，「コルモゴロフ複雑性とその応用への紹介」，  Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ  （１９９３），  ＩＳＢＮ  ０−３８７−９４０５３−７
【非特許文献７】Ｃｒｙｐｔｏｇｒａｐｈｙ  Ｒｅｓｅａｒｃｈ，  Ｉｎｃ．，「ＶＩＡ  Ｃ３ネヘミア乱数発生器の評価」，  ＵＲＬ  ｈｔｔｐ：／／ｗｗｗ．ｃｒｙｐｔｏｇｒａｐｈｙ．ｃｏｍ／ｒｅｓｏｕｒｃｅｓ／ｗｈｉｔｅｐａｐｅｒｓ／ＶＩＡ＿ｒｎｇ．ｐｄｆ
【非特許文献８】Ｃｒｙｐｔｏｇｒａｐｈｙ  Ｒｅｓｅａｒｃｈ，  Ｉｎｃ．，「インテル乱数発生器」，  ＵＲＬ  ｈｔｔｐ：／／ｗｗｗ．ｃｒｙｐｔｏｇｒａｐｈｙ．ｃｏｍ／ｒｅｓｏｕｒｃｅｓ／ｗｈｉｔｅｐａｐｅｒｓ／ＩｎｔｅｌＲＮＧ．ｐｄｆ
【非特許文献９】Ｋａｌｉｓｋｉ，  Ｂｕｒｔｏｎ  Ｓ．，  Ｊｒ．，  Ｃｅｔｉｎ  ｋａｙａ  Ｋｏｃ  および  Ｃｈｒｉｓｔｏｆ  Ｐａａｒ  （Ｅｄｓ．），「暗号化ハードウェアおよび埋め込みシステム−ＣＨＥＳ  ２００２，  ４ｔｈ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｗｏｒｋｓｈｏｐ，  Ｒｅｄｗｏｏｄ  Ｓｈｏｒｅｓ，  ＣＡ，  Ｕ．Ｓ．Ａ．，  Ａｕｇｕｓｔ  １３−１５，  ２００２，  Ｒｅｖｉｓｅｄ  Ｐａｐｅｒｓ」，  Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ，  Ｖｏｌ．  ２５２３，  Ｓｐｒｉｎｇｅｒ  （２００３），  ＩＳＢＮ  ３−５４０−００４０９−２，  ｐｐ．  ４１５−４３０  内の  Ｆｉｓｃｈｅｒ，  Ｖｉｋｔｏｒ，  および  Ｍｉｌｏｓ  Ｄｒｕｔａｒｏｖｓｋｙ，「再構成可能ハードウェアに埋め込まれた真乱数発生器」
【非特許文献１０】Ｋａｌｉｓｋｉ，  Ｂｕｒｔｏｎ  Ｓ．，  Ｊｒ．，  Ｃｅｔｉｎ  ｋａｙａ  Ｋｏｃ  および  Ｃｈｒｉｓｔｏｆ  Ｐａａｒ  （Ｅｄｓ．），「暗号化ハードウェアおよび埋め込みシステム−ＣＨＥＳ  ２００２，  ４ｔｈ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｗｏｒｋｓｈｏｐ，  Ｒｅｄｗｏｏｄ  Ｓｈｏｒｅｓ，  ＣＡ，  Ｕ．Ｓ．Ａ．，  Ａｕｇｕｓｔ  １３−１５，  ２００２，  Ｒｅｖｉｓｅｄ  Ｐａｐｅｒｓ」，  Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ，  Ｖｏｌ．  ２５２３，  Ｓｐｒｉｎｇｅｒ  （２００３），  ＩＳＢＮ  ３−５４０−００４０９−２，  ｐｐ．４５０−４５３  内の  Ｔｋａｃｉｋ，  Ｔｈｏｍａｓ  Ｅ．，「ハードウェア乱数発生器」
【発明の開示】
【発明が解決しようとする課題】
【００３０】
本発明の目的は、決定論的事後処理がもはや必要でないように、前述した種類の乱数発生器、および従来技術から知られるような乱数ストリング発生方法を構成または開発することである。
【課題を解決するための手段】
【００３１】
この目的は、請求項１４の特徴を有する乱数発生器、および請求項１の特徴を有する方法によって達成される。
【００３２】
本発明の有利な構成および展開は、従属請求項で明示される。
【００３３】
本発明は、均等または不均等周期の発振ディジタル出力信号が、少なくとも２つのリング発振器によって発生され、また論理状態、即ち論理「０」または「１」を表す外部パリティ信号が発生されるように、乱数の発生方法から始まる。外部パリティ信号は、奇数個の出力信号が論理状態「１」を有するときにのみ論理状態「１」を取り、そうでなければ論理状態「０」を取る。本発明によれば、外部パリティ信号は、それぞれのリング発振器の外部パリティ入力へフィードバックされる。従来技術から知られるように、外部パリティ信号は、それをサンプリングすることによってランダム・ビットを発生するように使用される。それぞれのリング発振器の（外部パリティ）入力へパリティ信号をフィードバックするため、パリティ信号の自己相関は、従来技術から知られるフィードバックなしの方法に対して顕著に低減される。この理由によって、発生されたランダム・ビットのレートは、本発明に従った方法において顕著に増加する。
【００３４】
本発明に従った乱数発生器は、適切な形式によれば、好ましくは奇数個の直列接続インバータを有するフィードバック付独立自由走行インバータ・チェーンから構成されて均等または不均等周期の前記発振ディジタル出力信号を発生する少なくとも２つのリング発振器、および好ましくは前述した外部パリティ信号を発生する排他的ＯＲゲートによって形成される第１のパリティ信号発生手段を含む。本発明によれば、たとえば排他的ＯＲゲートから形成されたフィードバック手段が存在する。フィードバック手段は、この外部パリティ信号を、それぞれのリング発振器（インバータ・チェーンから形成される）の外部パリティ入力へフィードバックする。
【００３５】
本発明に従った好ましい実施形態において、各々のリング発振器について、各々の場合に、それぞれのリング発振器の出力信号またはそれぞれのリング発振器の外部パリティ入力へフィードバックされた信号が特定の論理状態（たとえば「１」）を取るとき、特定の論理状態（たとえば「１」）を表す内部パリティ信号が発生される。一方では、これらの内部パリティ信号は、前述したような種類の更なるパリティ信号形成によって、更なるパリティ信号へ変換される。このパリティ信号は、それをサンプリングすることによってランダム・ビットを発生するため、前述したように使用される。この更なるパリティ形成の結果として、外部パリティ信号と比較して再び顕著に低減される自己相関を有する信号が生成される。同時に、ランダム・ビットを発生する可能サンプリング・レートは、このようにして再び顕著に低減される。
【００３６】
したがって、内部パリティ信号を発生するため、本発明に従った乱数発生器は、適切なパリティ信号発生手段を含む。これらは、好ましくは、外部パリティ入力および出力信号入力を有する排他的ＯＲゲートを含む。外部パリティ信号から引き出された信号、たとえばパリティ信号それ自体または以下で詳細に説明するように発生される信号が、外部パリティ入力に存在する。それぞれのリング発振器のそれぞれの出力信号は、出力信号入力に存在する。更なるパリティ信号を発生するため、本発明に従った乱数発生器は、更なるパリティ信号発生手段を含む。この手段は、奇数個の内部パリティ信号が、特定の論理状態（たとえば「１」）を取るとき、論理状態「０」または「１」を表す更なるパリティ信号を発生する。適切な様式で、これらの手段は、更に好ましくは、排他的ＯＲゲート（ＸＯＲゲート）を含み、その入力に内部パリティ信号が存在する。
【００３７】
前述したように、特に、インバータ・チェーンから形成されたリング発振器の場合に、スタート問題が生じる。この問題を避けるため、本発明によれば、本発明の乱数発生器の中にスタート手段が存在する。このスタート手段はスタート信号（たとえば論理「１」）を発生し、少なくとも１つのリング発振器のスタート／ストップ入力へスタート信号を供給し、このリング発振器が発振へ励起されるようにする。このために、このリング発振器は、入力側にインバータの代わりに２つの入力を有するＮＡＮＤゲートを有する。このＮＡＮＤゲートの１つの入力および出力は、除去されたインバータの入力および出力の代わりにインバータ・チェーンの残りのものへ接続される。他の入力は、前述したスタート／ストップ入力を形成し、スタート信号がそこへ供給される。
【００３８】
原理的には、全てのリング発振器は、対応するスタート／ストップ入力を介して別々にスタートすることができる。しかし、多くの場合、同じスタート信号（たとえば論理「１」）の助けにより、全てのリング発振器を好ましくは同時に発振へ励起するならば、好都合であることが分かった。このため、たとえば、入力側のインバータの代わりに、全てのリング発振器の各々がＮＡＮＤゲートを設けられる。このＮＡＮＤゲートのスタート／ストップ入力は、スタート信号（たとえば論理「１」）を供給するため相互に接続される。
【００３９】
ここで、配置に依存して他のスタート問題が生じる。このスタート問題は、少なくとも１つの外部パリティ入力の前にインバータを接続することによって除去される。外部パリティ信号は前記インバータへ供給される。第１に、このインバータは、この外部パリティ入力で信号の遅延を生じる。第２に、前にインバータを接続された外部パリティ入力の信号は、極性の反転を経験する。後者の場合、対応するリング発振器の入力で極性の反転が起こり、したがってこのリング発振器で発振が開始する。結果として、他の接続されたリング発振器も発振へ励起される。
【００４０】
或る応用の場合、もしインバータの個数が異なるインバータ・チェーンが、全ての外部パリティ入力の前に接続され、それらのインバータ・チェーンへ外部パリティ信号が供給されるならば、有利であることが証明された。その場合、もし、第１のリング発振器によって発生された出力信号の周期（値において、ゲート（インバータ（ドイツ語原文ではＩｎｖｅｎｔｅｒ。−−−ドイツ語翻訳者）、ＮＡＮＤゲート、ＸＯＲゲート）の遅延時間の奇数倍に等しい）と、第１のリング発振器の外部パリティ入力における外部パリティ信号の遅延持続時間（値において、遅延時間の倍数に等しい）との合計が、遅延時間の奇数倍に等しく、また、もし、第２のリング発振器によって発生された出力信号の周期（値において、遅延時間の奇数倍に等しい）と、第２のリング発振器の外部パリティ入力における外部パリティ信号の遅延持続時間（値において、遅延時間の倍数に等しい）との合計が、遅延時間の偶数倍に等しければ、回路配列の発振が生じる。
【００４１】
前述したように、外部パリティ信号および更なるパリティ信号の双方を、ランダム・ビットの発生に使用することができる。本発明による乱数発生器は、ランダム・ビットを発生する特定レートで外部パリティ信号をサンプリングするサンプリング手段、および／またはランダム・ビットを発生する特定レートで更なるパリティ信号をサンプリングするサンプリング手段を有する。
【００４２】
もし前述したような種類の乱数発生器の複数個を組み合わせるならば、最大サンプリング・レートを更に増加させることができる。外部の、特にサンプリングされたパリティ信号を発生し、および／または、更なる、特にサンプリングされたパリティ信号を発生する乱数発生器から始めて、これらのパリティ信号から追加または反復されたパリティ形成によって（パリティ信号形成の任意の変形が可能である）、乱数発生のために提供された（スーパー）パリティ信号の自己相関が実際に任意の程度まで低減される乱数発生器を形成することができる。
【００４３】
更なる乱数発生はサンプリングを必要とする。ここで、外部パリティ信号または更なるパリティ信号または他の低次のパリティ信号が、ランダム・ビットを発生する特定レートで同期的にサンプリングされるか、最高次の（スーパー）パリティ信号が、ランダム・ビットを発生する特定レートでサンプリングされるかは重要ではない。
【００４４】
サンプリングは、時間的に一定の間隔で起こることができるが、本発明によれば、ランダムな非均一サンプリング間隔でもサンプリングが実行される。たとえば、前述した乱数発生器の１つによってランダムに発生されたランダム・ビットが所定の論理状態（たとえば「１」）を取る時点で、もしサンプリングを実行するならば、ランダム・サンプリングを達成することができる。
【００４５】
たとえば、クロック、特に非安定マルチバイブレータからのパルスによって駆動されるか（時間的に一定のサンプリング時間間隔の場合）、前述したフィードバックを有するリング発振器によって駆動される（時間的にランダムなサンプリング時間間隔の場合）Ｄフリップフロップを使用して、サンプリングを達成することができる。
【００４６】
今から、図面を参照して本発明を詳細に説明する。
【発明を実施するための最良の形態】
【００４７】
本発明の基本的概念は、前述したように、個々のリング発振器の入力へパリティ信号をフィードバックさせることにある。
【００４８】
図１は、本発明に従った乱数発生器の第１の例示的実施形態を示す。この乱数発生器は、Ｌ個のリング発振器３２、３３、３４をもとに、それら発振器の出力は、パリティ信号ＰＳが形成されるＸＯＲゲートｘｏｒの対応入力へ供給される。
【００４９】
図１が示すように、リング発振器３２、３３、３４の個々の入力へフィードバックパリティ信号ＰＳを供給することは、多数の論理ＸＯＲゲートｘｏｒ１、ｘｏｒ２、．．．、ｘｏｒＬを介して達成される。各々の場合にパリティ信号ＰＳが存在する入力は、外部パリティ入力３６、３７、３８と呼ばれる。
【００５０】
注意すべきは、この回路の発振は、図２の例がＬ＝３、Ｋ１＝３、Ｋ２＝５、およびＫ３＝７について示すように、また以下で詳細に説明するように、パラメータＬ、Ｋ１、．．．、ＫＬの全ての値の組み合わせについては生じない。
【００５１】
オフ状態における回路の論理状態は図２ａで示される。図２ｂは、回路がオンにされた後（即ち、スタート／ストップ信号が論理「１」へセットされた後）の状態を示す。注意すべきは、回路は常に依然として静的（非発振）状態にあることである。なぜなら、ＮＡＮＤゲートｎａｎｄｉ，１（ｉ＝１、２、３）の全ての出力は変化しないからである。このスタート問題は、ＸＯＲゲートの外部パリティ入力４７の前に更なるインバータｉｎｖ３，−１を挿入することによって軽減される（図３を参照）。
【００５２】
この現在発振している回路のパリティ信号ＰＳは、図４で様々な時間間隔について示される。フィードバックは、適切な（発振）パラメータの組み合わせについて、非常に不規則な形態のパリティ信号ＰＳを導くことが明瞭に分かる。平均のパリティ信号ＰＳは、非常に低い一定の自己相関を示す（図５を参照）。図２１ｂと比較すると、これは顕著な改善であり、発生されるランダム・ビットのレートｖを実質的に増加させることができる。
【００５３】
一般的なスタート問題を解決するため、また追加ジッタ累積を導入するため、ＸＯＲゲートｘｏｒｉ（ｉ＝１，．．．，Ｌ）の前に、インバータのチェーンｉｎｖｉ，−ｊ（ｉ＝１，．．．，Ｌ，ｊ＝１，．．．，Ｍi）が導入される。個々のチェーンＭ１，．．．，ＭＬの長さは可変である。スタート／ストップ問題が生じないことを確実にするため、パラメータＭｉおよびＫiを特別に選択しなければならない。２つの合計Ｍi＋ＫiおよびＭj＋Ｋjの１つが奇数であり、他方が偶数であるように、ｉ，ｊ∈｛１，．．．，Ｌ｝×｛１，．．．，Ｌ｝の場合、少なくとも１つのペアｉ，ｊが存在する場合があるはずである。
【００５４】
図６は、パリティ信号ＰＳのフィードバックを有する一般的回路図を示す。以下の説明では、この回路はフィードバック付発振器（ＲＲＯ）と呼ばれる（略語ＲＲＯは、ｒｕｃｋｇｅｋｏｐｐｅｌｔｅｒ  Ｒｉｎｇ−Ｏｓｚｉｌｌａｔｏｒ（フィードバックを有するリング発振器）の略である。この略語は図面にもあるので、明細書中に残すことにした。−−−ドイツ語翻訳者）。ＸＯＲゲートｘｏｒ１〜ｘｏｒＬの出力Ｐ１〜ＰＬの信号は、入力信号のパリティをチェックし、したがって内部パリティ信号と呼ばれる。区別するため、ＸＯＲゲートＸＯＲの出力におけるパリティ信号ＰＳは外部パリティ信号と呼ばれる。
【００５５】
図７は、パラメータＬ＝４、Ｋ１＝１、Ｋ２＝３、Ｋ３＝４、Ｋ４＝５、Ｍ１＝３、Ｍ２＝２、Ｍ３＝１、Ｍ４＝０を有するＲＲＯのインスタンスを示す。簡潔にするため、ＲＲＯ（４；１，３，４，５；３，２，１，０）の表示が使用される。図８で示されるように、内部パリティ信号は、ＲＲＯの構成のために全く多様であり、ランダム・ビットを発生するために使用可能である。
【００５６】
内部パリティ信号Ｐ１、Ｐ２、．．．、ＰＬの更なるパリティ・チェックＰＰによって、品質が更に改善される。その場合、図９で示されるように、更なるパリティ信号ＰＰが発生され、サンプリングの後、ランダム・ビット・ストリングＺＢとして使用可能である。サンプリングは、周期的クロック信号ＣＰによって駆動されるＤフリップフロップ８５によって達成される。クロック信号ＣＰは非安定マルチバイブレータ８７によって発生されることができ、その周期（均一サンプリング間隔）はバイナリ・カウンタ８６で決定される。ランダムな非均一サンプリング間隔を得るためには、非安定マルチバイブレータ８７をＲＲＯで置換することができる。均一サンプリングのＲＲＯインスタンスＲＲＯ（４；１，３，４，５；３，２，１，０）を有する乱数発生器は、図１０で示される。この乱数発生器の統計的テストは、ほとんどバイアスを示さず、ビット７の低い相関を示した。
【００５７】
これらの効果を除去するため、更なる（スーパー）パリティ・チェックＳＰを介して複数のＲＲＯが結合された。この結合は、多様な方法で実行することができる。図１１において、均一サンプリングはパリティ・チェックＰＰの後で起こる。対照的に、図１２において、個々のＲＲＯは（スーパー）パリティ・チェックＳＰの前にサンプリングされる。これは非同期的に起こるので、スーパー・パリティ信号ＳＰは、均等持続時間のランダム・ビット７を得るため再びサンプリングされなければならない。これを避けるため、図１３で示されるように、サンプリングを同期的に実行することもできる。
【００５８】
実際には、多くの場合、小さいが依然として妨害するバイアスが現れる。したがって、十分に良好とは言えないランダム・ビット・ストリングが発生される。他の電子的に実現されたＴＲＮＧも、この欠陥を有する。この欠陥は、通常、使用される能動半導体コンポーネントの不整合動作点に起因する。これまでの実施では、この残留バイアスを中和するため、様々な決定論的事後処理、たとえば、頻繁に使用されるフォンノイマン法がサンプリングの後で実行された。全てのこれらのアルゴリズムは、実質的に、発生されるランダム・ビットのレートを低減させる。
【００５９】
しかし、フィードバック付リング発振器（ＲＲＯ）を使用すると、もし、長さＺのバイナリ・カウンタ８８１、８８２、．．．、８８Ｌ（ここでは、Ｚ個のＪＫフリップフロップＪＫ１、ＪＫ２、．．．、ＪＫＺ）がリング発振器ＲＲＯの出力Ｐ１、Ｐ２、．．．、ＰＬへ接続されるならば、サンプリング前でも、この残留バイアスを中和することができる（図９を参照）。これらのカウンタ８８１、８８２、．．．、８８Ｌの出力はＸＯＲゲートの入力へ接続され、ＸＯＲゲートは更なるパリティ信号ＰＰを引き渡す（図２２）。２つの信号状態（不均等持続時間を有する高および低）の間の信号遷移をカウントすることによって、新しい（より長い）信号状態が得られる。持続時間に関して、これらの新しい信号状態は、元の信号の信号状態よりも相互に類似する。Ｚの個数が大きくなれば、それだけ良好に信号状態の持続時間を均等化することができ、したがって残留バイアスは任意の小さな値へ抑圧される。Ｚ＝１の場合でも、良好な結果が達成される。
【図面の簡単な説明】
【００６０】
【図１】パリティ信号のフィードバックを有するリング発振器を示す図である。
【図２】フィードバックを有するリング発振器のスタート問題の例を示す図である。  （ａ）スタート前  （ｂ）スタート後
【図３】図２のスタート問題の解決を示す図である。  （ａ）スタート前  （ｂ）スタート後
【図４】次のタイムスパンにおける図３の回路のパリティ信号ＰＳの信号トレースを示す図である。  （ａ）１０ｎｓ  （ｂ）４０ｎｓ  （ｃ）２００ｎｓ  （ｄ）４００ｎｓ  （ｅ）１０００ｎｓ  （ｆ）２０００ｎｓ
【図５】図３の回路の平均パリティ信号を示す図である。
【図６】フィードバックを有するリング発振器（ＲＲＯ）の概略的な回路図である。
【図７】ＲＲＯ（４；１，３，４，５；３，２，１，０）の回路を示す図である。
【図８】図７のＲＲＯ（４；１，３，４，５；３，２，１，０）の点Ｐ１、Ｐ２、Ｐ３、およびＰ４における内部パリティ信号を示す図である。
【図９】ＲＲＯで実現されたランダム・ビット発生器を示す図である。
【図１０】ＲＲＯ（４；１，３，４，５；３，２，１，０）を有する乱数発生器の例を示す図である。
【図１１】Ｎ個のＲＲＯおよびサンプリングされたスーパー・パリティ信号を有する乱数発生器を示す図である。
【図１２】Ｎ個のサンプリングされたＲＲＯおよびサンプリングされたスーパー・パリティ信号を有する乱数発生器を示す図である。
【図１３】Ｎ個の同期およびサンプリングされたＲＲＯおよびサンプリングされたスーパー・パリティ信号を有する乱数発生器を示す図である。
【図１４】物理的乱数発生器のモデル（従来技術）を示す図である。
【図１５】従来技術に従ったリング発振器を示す図である。  （ａ）インバータ・チェーン・リング発振器  （ｂ）制御入力を有するインバータ・チェーン・リング発振器
【図１６】従来技術に従ったリング発振器の機能モードの例を示す図である。  （ａ）Ｋ＝３のリング発振器（従来技術）  （ｂ）インバータの理想化された遅延  （ｃ）発振信号のトレース
【図１７】図１６のリング発振器の実際的実現の例を示す図である。  （ａ）コンポーネント７４ＨＣＴ０４を使用したＫ＝３のリング発振器の実現  （ｂ）熱雑音を付加した発振信号のトレース  （ｃ）雑音発振信号のエンベロープ
【図１８】図１７ａのリング発振器の平均発振信号を示す図である。
【図１９】いわゆるパリティ・チェック（従来技術）のパフォーマンスの例を示す図である。  （ａ）スタート／ストップ信号が共通に駆動されるＬ個のリング発振器のパリティ・チェック回路  （ｂ）スタート／ストップ信号が別々に駆動されるＬ個のリング発振器のパリティ・チェック回路
【図２０】図１９ａのパリティ・チェックの実際のパフォーマンスの例を示す図である。  （ａ）スタート／ストップ信号が共通に駆動される２つのリング発振器のパリティ・チェック回路の例  （ｂ）個々のコンポーネントの信号およびパリティ信号のトレース  （ｃ）個々のコンポーネントの信号およびパリティ信号のトレース
【図２１】図１９ａのパリティ・チェックの実際のパフォーマンスの例を示す図である。  （ａ）個々のコンポーネントの信号およびパリティ信号のトレース  （ｂ）図２０ａの回路の平均パリティ信号
【図２２】中和された残留バイアスを有するＲＲＯを示す図である。
【符号の説明】
【００６１】
参照文字および略語のリスト
１  ランダム・ソース
２  値の獲得
３  ランダム・ビット発生
４  アルゴリズム事後処理／ランダム抽出
５  ランダム・ビット出力
６  物理環境
８  リング発振器
９  制御入力を有するリング発振器
１０  リング発振器
１１  入力信号
１２  出力信号
１３  信号エンベロープ
１４  導体の点Ａ’における信号トレース
１５  エンベロープ曲線
１７  リング発振器
１８  リング発振器
１９  リング発振器
２０  リング発振器
２１  リング発振器
２２  リング発振器
２４  リング発振器
２５  リング発振器
２７  ＸＯＲゲートの第１の入力信号
２８  ＸＯＲゲートの第２の入力信号
２９  パリティ信号
３０  平均パリティ信号のエンベロープ
３２  リング発振器
３３  リング発振器
３４  リング発振器
３６  外部パリティ入力
３７  外部パリティ入力
３８  外部パリティ入力
４１  リング発振器
４２  リング発振器
４３  リング発振器
４５  外部パリティ入力
４６  外部パリティ入力
４７  外部パリティ入力
４７°外部パリティ入力
７１  リング発振器
７２  リング発振器
７３  リング発振器
８１  リング発振器
８２  リング発振器
８３  リング発振器
８４  リング発振器
８５  Ｄフリップフロップ
８５１  Ｄフリップフロップ
８６  バイナリ・カウンタ
８６１  バイナリ・カウンタ
８７  非安定マルチバイブレータ
８７１  非安定マルチバイブレータ
８８１  バイナリ・カウンタ
Ａ  導体の点
Ｂ  導体の点
Ｃ  導体の点
Ａ’  導体の点
ＤＥＳ  データ暗号化標準
ｆ  周波数
ｉｎｖ  インバータ
ｉｎｖ１  インバータ／ＮＯＴゲート
ｉｎｖ２  インバータ／ＮＯＴゲート
ｉｎｖＫ  インバータ／ＮＯＴゲート
ＪＫ１  ＪＫフリップフロップ
ＪＫ２  ＪＫフリップフロップ
ＪＫＺ  ＪＫフリップフロップ
Ｋ  ゲートの個数
Ｋ１  ゲートの個数
Ｋ１  ゲートの個数
Ｋ２  ゲートの個数
Ｋ３  ゲートの個数
ＫＬ  ゲートの個数
Ｌ  リング発振器の個数
Ｍ  ゲートの個数
Ｍ１  ゲートの個数
Ｍ２  ゲートの個数
Ｍ３  ゲートの個数
Ｍ４  ゲートの個数
ＭＬ  ゲートの個数
Ｎ  リング発振器の個数
ｎａｎｄ１  ＮＡＮＤゲート
ｎａｎｄ２
Ｐ  周期
Ｐ１  内部パリティ信号
Ｐ２  内部パリティ信号
ＰＬ  内部パリティ信号
ＰＲＮＧ  決定論的乱数発生器
ＰＳ  外部パリティ信号
ＲＲＯ  フィードバック付リング発振器
Ｓ  導体の点
ＳＰ  スーパー・パリティ信号
スタート／ストップ  制御入力
ｔ  時間
ｔ１  時点
Ｔ  経過時間
ＴＲＮＧ  物理的乱数発生器
Ｕ  電圧
Ｕｅ  入力電圧
Ｕａ  出力電圧
ｘｏｒ  奇数個の入力が論理「１」であるとき、出力で論理「１」を有する排他的ＯＲ／ＸＯＲゲート
ｘｏｒ１  奇数個の入力が論理「１」であるとき、出力で論理「１」を有する排他的ＯＲ／ＸＯＲゲート
ｘｏｒ２  奇数個の入力が論理「１」であるとき、出力で論理「１」を有する排他的ＯＲ／ＸＯＲゲート
Ｚ  個数
ＺＢ  ランダム・ビット
Δ  差
ｖ  サンプリング・レート
ｖｍａｘ  最大サンプリング・レート
τ  遅延時間
【図１】
2006139756.tif 000003
【図２】
2006139756.tif 000004
【図３】
2006139756.tif 000005
【図４】
2006139756.tif 000006
【図５】
2006139756.tif 000007
【図６】
2006139756.tif 000008
【図７】
2006139756.tif 000009
【図８】
2006139756.tif 000010
【図９】
2006139756.tif 000011
【図１０】
2006139756.tif 000012
【図１１】
2006139756.tif 000013
【図１２】
2006139756.tif 000014
【図１３】
2006139756.tif 000015
【図１４】
2006139756.tif 000016
【図１５】
2006139756.tif 000017
【図１６】
2006139756.tif 000018
【図１７】
2006139756.tif 000019
【図１８】
2006139756.tif 000020
【図１９】
2006139756.tif 000021
【図２０】
2006139756.tif 000022
【図２１】
2006139756.tif 000023
【図２２】
2006139756.tif 000024
【外国語明細書】
2006139756000001.pdf