選択された統計的アーティファクトを有する混合基数数生成器
【課題】数列を生成するのに使用される処理をマスクする方法を提供すること。
【解決手段】この方法は、ガロア体ＧＦ［Ｍ］に含まれる第１数列を生成することを含む。この方法は、第１数列内の第１の数に対して第１変更を実行することをも含む。第１変更は、第１の数に先行する第１数列の第２の数に対して実行されるＰを法とする剰余演算の結果と第１の数とを合計することを含む。Ｍは、Ｐに関して相対的に素である。この方法は、さらに、第１乱数に対して第２変更を実行することを含む。第２変更は、Ｐを法とする剰余演算からなる。この第２変更は、第１変更の後に実行される。この方法は、第２の数列を生成するために、第１数列を含む複数の数について第１および第２変更を繰り返すことを含む。
【解決手段】この方法は、ガロア体ＧＦ［Ｍ］に含まれる第１数列を生成することを含む。この方法は、第１数列内の第１の数に対して第１変更を実行することをも含む。第１変更は、第１の数に先行する第１数列の第２の数に対して実行されるＰを法とする剰余演算の結果と第１の数とを合計することを含む。Ｍは、Ｐに関して相対的に素である。この方法は、さらに、第１乱数に対して第２変更を実行することを含む。第２変更は、Ｐを法とする剰余演算からなる。この第２変更は、第１変更の後に実行される。この方法は、第２の数列を生成するために、第１数列を含む複数の数について第１および第２変更を繰り返すことを含む。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明配置は、混合基数変換を使用する通信システムに関する。より具体的には、本発明配置は、選択されたガロア体ＧＦ［Ｐ］のすべての同値類上で選択された統計的特性を有する乱数列を作るために混合基数リングの生成および変換を実行する方法およびシステムに関する。
【背景技術】
【０００２】
通信システムは、多数の応用例でリング生成器を含むことができる。リング生成器は、繰り返される写像を介して可能な出力を網羅的に作る有限体上の単純な構造である。この写像は、加法的写像および乗法的写像のある組合せであり、既約多項式はイデアルである。たとえば、リング生成器は、１１個の要素を含む有限ガロア体ＧＦ［１１］での既約多項式ｆ（ｘ）＝３ｘ3＋３ｘ2＋ｘの繰り返される計算を含む。有限体またはガロア体ＧＦ［Ｐ］は、有限な個数の要素｛０，１，２，…，Ｐ−１｝だけを含む体である。有限体またはガロア体ＧＦ［Ｐ］は、ガロア標数Ｐによって定義される有限体サイズを有し、Ｐは、しばしば、整数論的結果に基づいて素数になるように選択される。この計算は、通常、ルックアップテーブル動作、フィードバックループ、または乗算器構造としてディジタルハードウェアで実施される。
【０００３】
そのようなリング生成器の利益にかかわらず、リング生成器は、ある短所をこうむる。たとえば、リング生成器のガロア標数Ｐが、素数（２と等しくない）になるように選択される場合に、計算は、通常、ディジタル（２進）領域で非効率的である。また、有限体またはガロア体ＧＦ［Ｐ］で実行されるルックアップテーブル動作は、ガロア標数Ｐが大きい場合に、メモリ集中型である。さらに、リング生成器の出力値は、非常に決定的である。したがって、写像および現在の有限体条件の知識は、出力数列の完全な知識を与える。
【０００４】
リング生成器の出力数列を意図されない再構築からマスクする１つの方法は、より大きい有効領域への全単写像を実行するアルゴリズムを介して複数のリング生成器を組み合わせることである。この組合せの例は、個々のリング生成器のガロア標数が互いに素である時の中国の剰余定理（ＣＲＴ）を介するものである。もう１つの方法は、領域ＧＦ［Ｐ］から２進領域ＧＦ［２k］への混合基数変換を実行することによってリング生成器出力値を単純に切り詰めることである。これらのマスキング法の両方が、オリジナル数列を部分的にマスクするが、それでも、これらは、まだ、数列値を再エンジニアリングするのに使用できる統計的アーティファクトを提示する。暗号学では、そのような試みを、しばしば、周期攻撃（ｆｒｅｑｕｅｎｃｙ ａｔｔａｃｋ）と呼び、これによって、個人が、統計的分析を介して擬似ランダム数列の写像および状態特性の部分的情報を得ることができる。この処理の通常の門外漢の例が、ある文字を別の文字と交換するワードパズルである。英語の知識は、ＥがＺより優勢であるという部分的知識を与える。実際には、検索は、ブルートフォースからより論理的な検索に限定される。
【特許文献１】日本国特許出願公開第２００２−２９７０３３Ａ号
【特許文献２】米国特許第７０６９４９２号
【特許文献３】米国特許第７０７９６５１号
【特許文献４】日本国特許出願公開第２００３−５３３７５２Ａ号
【発明の開示】
【発明が解決しようとする課題】
【０００５】
前述に鑑みて、ディジタル（２進）領域で計算的に効率的であり、著しい統計的アーティファクトを全く有しない、混合基数変換法の必要が残っている。また、従来のリング生成器実施態様よりハードウェア集中的ではない実施態様を有し、選択された統計的特性を有する擬似乱数列を作る、リング生成器の必要がある。さらに、非決定的に見える軌道を有するリング生成器の必要がある。
【課題を解決するための手段】
【０００６】
本発明は、数列を生成するのに使用される処理をマスクする方法に関する。この方法は、生成するステップ、第１変更ステップ、および第２変更ステップを含む。生成するステップは、ガロア体ＧＦ［Ｍ］内に含まれる第１数列を生成することを含む。第１変更ステップは、第１数列内の第１の数に対して第１変更を実行することを含む。第１変更は、第１の数に先行する第１数列の第２の数に対して実行されるＰを法（ｍｏｄｕｌｏ）とする剰余演算の結果と第１の数とを合計することによって達成される。Ｍは、Ｐに関して相対的に素である。第２変更ステップは、第１の数に対して第２変更を実行することを含む。第２変更は、Ｐを法とする剰余演算からなる。第２変更は、第１変更の後に実行される。この方法は、さらに、第２数列を生成するために、第１数列を含む１つまたは複数の数について第１および第２の変更を繰り返すことを含む。
【０００７】
本発明の態様によれば、この方法は、第２数列を用いてディジタルデータストリームを変更することを含む。生成するステップは、生成するステップに関する選択された統計的アーティファクトを含む擬似乱数列を生成することをも含む。統計的アーティファクトは、通常、第１および第２の変更ステップによってＧＦ［Ｐ］上の乱数の一様に分布する数列を作成するように選択される。本明細書で使用される時に、「乱数の一様に分布する数列」は、数列内の各数値が完全一様分布からのランダム選択を近似し、保護空間内のすべての要素が、選択される同等の見込みを有する数列である。生成するステップは、さらに、周期的に繰り返される写像を使用することによって第１数列を網羅的に作ることを含む。この写像は、加法的写像および乗法的写像の組合せを含むように選択される。加法的写像および乗法的写像は、ガロア体ＧＦ［Ｍ］上の既約多項式の繰り返される計算を含めるために組み合わせて選択される。
【０００８】
本発明のもう１つの態様によれば、この方法は、Ｐより大きいＭの値を選択することを含む。この方法は、Ｐおよびｐ1，ｐ2，ｐ3，…ｐkを含むＰの複数の素因数のすべてと互いに素であるＭの値を選択することをも含む。この方法は、第２数列に対して第３変更ステップを実行することをさらに含む。第３変更ステップは、第２数列から１つまたは複数の出力数列を生成することを含む。第３変更ステップは、出力数列を生成するために第２数列内の各数に対して実行されるｐを法とする剰余演算をも含む。ｐは、ｐ1，ｐ2，ｐ3，…ｐkを含む群から選択される複数の値を含む。
【０００９】
本発明のもう１つの実施形態によれば、第２の数は、第１の数に直接に先行する。第２の数は、ｎ位置だけ第１の数に先行する。ｎは１より大きい。第２数列は、ガロア体ＧＦ［Ｐ］の複数の同値類にまたがって均等に分布する統計的アーティファクトを有する。同値類は、整数０、１、…、Ｐ−１ごとに１つの同値類を含む。
【００１０】
混合基数数生成器（ｍｉｘｅｄ ｒａｄｉｘ ｎｕｍｂｅｒ ｇｅｎｅｒａｔｏｒ）も提供される。混合基数数生成器は、数生成器と混合基数アキュムレータとを含む。数生成器は、ガロア体ＧＦ［Ｍ］内に含まれる第１数列を生成するように構成される。混合基数アキュムレータは、第１数列内の第１の数に対して第１変更を実行するように構成される。第１変更は、第１の数に先行する第１数列の第２の数に対して実行されるＰを法とする剰余演算の結果と第１の数とを合計することによって達成される。Ｍは、Ｐに関して相対的に素である。混合基数アキュムレータは、第１の数に対して第２変更を実行するようにも構成される。第２変更は、Ｐを法とする剰余演算からなる。第２変更は、第１変更の後に実行される。混合基数アキュムレータは、第２数列を生成するために、第１数列を含む複数の数について第１および第２の変更を繰り返すようにさらに構成される。
【００１１】
本発明の一態様によれば、混合基数数生成器は、ディジタルデータストリームを変更するのに第２数列を使用するように構成された手段を含む。数生成器は、擬似乱数生成器からなる。擬似乱数生成器は、第１数列の生成に関する統計的アーティファクトを含む擬似乱数列を生成する。統計的アーティファクトは、混合基数アキュムレータによって除去される。数生成器は、周期的に繰り返される写像を使用することによって第１数列を網羅的に作るようにも構成される。この写像は、加法的写像および乗法的写像の組合せを含む。組み合わされた加法的写像および乗法的写像は、ガロア体ＧＦ［Ｍ］上の既約多項式の繰り返される計算を含む。ＭはＰより大きい。Ｍの値は、Ｐおよびｐ1，ｐ2，ｐ3，…ｐkを含むＰの複数の素因数のすべての値に関して互いに素である。
【００１２】
本発明のもう１つの態様によれば、混合基数数生成器は、１つまたは複数の算術演算子ユニットからなる。算術演算子ユニットのそれぞれは、第２数列に対して第３変更を実行するように構成される。算術演算子ユニットは、第２数列から１つまたは複数の出力数列を生成するように構成される。第３変更は、出力数列を生成するために第２数列内の各数に対して実行されるｐを法とする剰余演算を含む。ｐは、ｐ1，ｐ2，ｐ3，…ｐkを含む群から選択される複数の値を含む。
【００１３】
第２の数は、ｎ位置だけ第１の数に先行する。ｎは１より大きい。第１数列は、ガロア体ＧＦ［Ｍ］によって定義される有限の個数の要素Ｍに制限される。本発明のもう１つの態様によれば、第２の数は、１位置だけ第１の数に先行する。第２の数列は、ガロア体ＧＦ［Ｐ］の複数の同値類にまたがって均等に分布する統計的アーティファクトを有する。同値類は、整数０、１、…、Ｐ−１ごとに１つの同値類を含む。
【００１４】
本発明のもう１つの態様によれば、第１数列は、その計算が等しいサイズのガロア体の中で第２数列に対して実行されるフィルタ構造によって操作される。このフィルタの結果は、第１数列の後続の値と組み合わせるために提示される。本明細書で使用される時に、「フィルタ」は、入力の以前の連続の時間加重和である出力を有する数学的構造を意味する。
【００１５】
実施形態を、図面を参照して説明するが、図面では、類似する符号が、複数の図面を通じて類似する要素を表す。
【発明を実施するための最良の形態】
【００１６】
ここで図１を参照すると、本発明を理解するのに有用な、従来の混合基数変換アルゴリズムの概念図が示されている。通信システムでは、さまざまなアルゴリズムが、数列をデータストリームと組み合わせるのに使用される。この組合せ処理は、通信リンクを介する伝送の前にデータストリームを暗号化するかマスクするために実行することができる。そのようなアルゴリズムには、ガロア体ＧＦ［Ｍ］基数で数列の各数を表す剰余数系（ＲＮＳ）演算を含めることができる。有限体またはガロア体ＧＦ［Ｍ］は、ガロア標数Ｍによって定義される有限体サイズを有する。ガロア体ＧＦ［Ｍ］は、有限の個数の要素｛０，１，２，…，Ｍ−１｝だけを含む体である。したがって、有限体またはガロア体で実行されるすべての算術演算は、その体に含まれる要素をもたらす。したがって、ガロア体ＧＦ［Ｍ］演算の結果の数列は、（Ｍ＋１）番目の要素おきに繰り返す可能性がある。これらのＲＮＳ演算は、当業者に周知であり、したがって、本明細書では詳細には説明しない。しかし、これらのＲＮＳ演算が、混合基数変換を必要とする可能性があることを理解されたい。用語「混合基数変換」は、本明細書で使用される時に、第１基数（または基）から第２基数（または基）への数列の変換を指す。たとえば、ガロア体ＧＦ［７］基数で表された数列は、図１に示されているようにガロア体ＧＦ［３］基数で表された数列に変換される。通常、混合基数変換は、宛先基が開始基より小さく、開始基を均等に分割しない時に、必ず、統計的アーティファクトを生じる。
【００１７】
混合基数変換アルゴリズムには、中国の剰余定理に基づく計算を含めることができる。中国の剰余定理は、当業者に周知であり、したがって、本明細書では詳細には説明しない。しかし、これらの計算が、複数の小さい基数（または基）で表された数を一意に組み合わせるために実行されることを理解されたい。この組合せは、しばしば、写像演算を介して達成される。中国の剰余定理の写像演算は、小さい基数（または基）で表された数のそれぞれを大きい基数で表された数に写像することを伴う。
【００１８】
特筆すべきことに、第１のガロア体ＧＦ［Ｍ1］基数から第２のガロア体ＧＦ［Ｍ2］基数への数列変換から生じる統計分布には、２つの基数が均等に分割可能でない時に、統計的非一様性がある。たとえば、ガロア体ＧＦ［７］基数で表された乱数列が、ガロア体ＧＦ［３］基数で表された数列に写像される。ガロア体ＧＦ［７］基数で表された乱数列は、要素｛０，１，２，…，６｝の集合によって定義される。同様に、ガロア体ＧＦ［３］基数で表された数列は、要素｛０，１，２｝の集合によって定義される。ガロア体ＧＦ［７］基数で表された数列のガロア体ＧＦ［３］基数で表された数列への写像は、一般に、各要素｛０，１，２，…，６｝をそれに対応する同値類の３を法とする剰余によって分割することを伴う。ガロア体ＧＦ［３］は、有限の個数の要素｛０，１，２｝だけを含む有限体なので、整数０、１、および２の対応する同値類がある。
【００１９】
ガロア体ＧＦ［７］からの要素のガロア体ＧＦ［３］の要素への写像演算を、次の表（１）にリストする。
【００２０】
【表１】
表１に示されているように、写像演算は、ガロア体ＧＦ［３］での要素の非一様分布をもたらす。具体的に言うと、写像演算の結果の数列は、｛０ １ ２ ０ １ ２ ０｝と定義される。整数０に関する、同値類のガロア体ＧＦ［７］からの３つの要素｛０，３，６｝がある。整数１に関する、同値類のガロア体ＧＦ［７］からの２つの要素｛１，４｝がある。整数２に関する、同値類のガロア体ＧＦ［７］からの２つの要素｛２，５｝がある。
【００２１】
統計分析を利用することによって、外部当事者が、従来の混合基数変換アルゴリズム（上で図１に関して説明した）を実施するシステムから部分的情報を得ることができ、写像演算の結果の数列によって変更されたデータストリームからオリジナル数列をより簡単に識別することができる。たとえば、２つの基数のサイズがわかれば、攻撃者は、さまざまな同値類の要素の統計的比率を使用して、変更されたデータストリームからオリジナル数列をより簡単に識別することができる。さらに、データメッセージフォーマットの知識は、統計的に有意な形で、乱数列の統計的アーティファクトと一致する。実際には、より多くの情報が、データメッセージ内容で提供される。本明細書で使用される時に、用語「統計的に有意」は、ある情報の有効性の数学的な確実さを指す。したがって、混合基数変換アルゴリズムによって導出される結果から統計的アーティファクトを除去し、その結果、変更されたデータストリームからのオリジナル数列の識別が相対的にむずかしくなるようにすることが、望ましい。
【００２２】
したがって、本発明のいくつかの実施形態は、混合基数変換における望まれない統計的アーティファクトを除去する方法を提供する。１つの方法は、一般に、統計的アーティファクトをガロア体ＧＦ［Ｐ］のすべての同値類にまたがって均等に拡散することを含む。この統計的アーティファクトの均等な分布は、混合基数リング生成器処理を使用することによって達成することができる。この処理は、（１）ガロア体ＧＦ［Ｍ］によって定義されるリングを利用して第１乱数列を生成することと、（２）Ｐを法とする剰余演算を介して以前に計算された剰余を加算することによって第１乱数列の各乱数を変更することと、（３）変更された乱数を利用して第２乱数列を生成することとを含む。第２乱数列は、Ｐを法とする剰余演算を利用しても生成される。第２乱数列は、ガロア体ＧＦ［Ｐ］のすべての同値類にまたがって均等に分布する統計的アーティファクトを含む。
【００２３】
そのような混合基数数生成器処理が、所望の統計的特性の無条件の厳守ではなく、所望の統計的特性の確率的厳守を提供することを理解されたい。用語「確率的厳守」は、イデアルに収束する挙動を指す。用語「無条件の厳守」は、数学的証明によって提供される保証のレベルを指す。そのような混合基数数生成器処理を、さまざまな通信システムアプリケーションで使用できることをも理解されたい。たとえば、そのような混合基数数生成器処理を、データストリームを変更するために暗号系で実施することができる。そのようなシナリオでは、混合基数数生成器処理は、高められたセキュリティ特徴を暗号系に提供する。この混合基数数生成器処理が、性質において非常に非決定的に見える乱数列を作ることに留意されたい。剰余換算（ｍｏｄｕｌｏ ｒｅｄｕｃｔｉｏｎ）を実行する際に、オリジナル数列からの情報は、意図的に破壊される。効果的に、意図されない再構築が、よりむずかしくなる。
【００２４】
これから、本発明を、添付図面を参照して以下でより十分に説明するが、添付図面には、本発明の例示的実施形態が示されている。しかし、本発明を、多数の異なる形で実施することができ、本明細書に示された実施形態に限定されると解釈してはならない。たとえば、本発明を、方法、データ処理システム、またはコンピュータプログラム製品として実施することができる。したがって、本発明は、完全にハードウェアの実施形態、完全にソフトウェアの実施形態、またはハードウェア／ソフトウェア実施形態としての形をとることができる。
【００２５】
ここで図２を参照すると、統計的アーティファクトをガロア体ＧＦ［Ｐ］のすべての同値類にまたがって均等に拡散するのに有用な混合基数数生成器構造の概念図が示されている。図２に示されているように、混合基数リング生成器処理は、乱数生成器２０２での乱数列の生成から開始される。この乱数列は、標数Ｍのガロア体で生成される擬似乱数列または擬似無秩序数列とすることができるが、これらに限定はされない。そのような数列は、最も簡単に、ガロア体ＧＦ［Ｍ］から選択されるランダム要素の数列とみなすことができる。ガロア体ＧＦ［Ｍ］から標数Ｐの所望のガロア体へ要素を写像するために、ガロア体標数Ｍは、ガロア体標数Ｐに対して相対的に素になるように選択される。用語「相対的に素」は、本明細書で使用される時に、１の最大公約数を有する数の集合を指す。
【００２６】
乱数列が、加算器２０４に通信される。上で説明した（図１に関して）統計的異常を打ち消すために、Ｐを法とする剰余演算の以前の出力を、フィードバック構造を介してガロア体ＧＦ［Ｍ］からの次の入力に加算する。このフィードバック構造は、遅延ユニット２０５を含む。次に、この加算演算からの結果を、Ｐを法とする剰余演算子２０６に通信する。Ｐを法とする剰余演算子２０６は、加算演算からの結果に対してＰを法とする演算を実行して、出力値を生成する。その後、Ｐを法とする剰余演算子の出力は、次の加算入力として使用され、効果的にＧＦ［Ｍ］のリング構造全体を回転する。実際に、累積的統計偏差は、回転が定常状態値に収束するので、大幅に目立たなくなる。ガロア体ＧＦ［Ｐ］から多数のそのようなサンプルを取ることが、統計的異常をすべての同値類にまたがって均等に分布させ、出力分布を一様分布の分布に戻すことを統計的に示すことは、簡単である。追加のオプションは、収束における固定点がないことを保証するために、フィードバック経路の回転に加えて定数回転（理想的には、Ｐより小さく｛Ｍ，Ｐ｝と互いに素である値）を誘導することである。数学的語法では、「固定点」とは、数学演算子の入力と出力との両方で同一のままであり、その演算子の繰り返される適用が固定値をもたらすようにする点である。たとえば、０は、伝統的な乗算演算子の固定点である。というのは、どの数に０をかけても０になるからである。
【００２７】
少数の数値の例が、この収束がどのように働くかを知るのを助ける可能性がある。
【００２８】
例１
Ｍ＝５×７＝３５、ｐ＝３であり、ユニット遅延の初期条件値が０であるものとする。ユニット遅延の初期条件（初期出力値）を、その代わりに０、１、または２のうちのいずれにもすることができることに留意されたい。上で説明したフィードバック機構がない場合に、Ｐを法とする剰余演算の出力が、ガロア体ＧＦ［Ｐ］内の統計的アーティファクトを有する値のストリームであることに留意されたい。乱数生成の出力の分布が、真に一様である場合に、ガロア体ＧＦ［Ｐ］の最初の２つの同値類は、第３の同値類より１要素だけ大きい。これは、３５ ｍｏｄｕｌｏ ３＝（３×１１＋２） ｍｏｄｕｌｏ ３＝２ ｍｏｄｕｌｏ ３の計算から簡単にわかる。図２のフィードバック（すなわち、遅延）は、同値類の３つすべてに関するガロア体ＧＦ［Ｐ］内のこの統計的非一様性を拡散する。
【００２９】
最初の乱数生成の出力が、｛２３ ８ １９ ３１ ０ ６ １３ ２１ ２１ …｝と定義されるストリームである場合に、フィードバックなしの３を法とする剰余演算の対応する出力は、［２ ２ １ １ ０ ０ １ ０ ０ …］になる。この事例での複数の入力が、同一の出力に写像され、これが、逆写像をよりむずかしくすることに留意されたい。図２に示されたユニット遅延フィードバックを有する、３を法とする剰余演算の出力は、｛２ １ ２ ０ ０ ０ １ １ １ …｝である。この小さいスケールでの数の相違は、無視できるように見えるが、それでも、フィードバックは、ＧＦ［Ｐ］の同値類に関する混合基数変換の非一様性を拡散している。
【００３０】
より従来のシステムと共に存在できる非一様性と、図２で説明した配置を用いて得られる改善とを十分に了解するために、図２の乱数生成器２０２が、ＧＦ［Ｍ］の１００００００個のランダムに選択された出力を生成するシナリオを検討されたい。ガロア体ＧＦ［Ｐ］は、ガロア体ＧＦ［３］になるように選択される。第１の乱数列は、ガロア体ＧＦ［Ｍ］からランダムに選ばれた１００万（１００００００）個の要素からなる。従来の混合基数変換アルゴリズム（上で図１に関して説明した）が使用される場合に、写像演算は、ガロア体ＧＦ［３］にまたがる要素の非一様分布をもたらす。ＭＡＴＬＡＢ（登録商標）シミュレーションから得られたこれらの写像演算の結果を示すグラフを、図３Ａに示す。ＭＡＴＬＡＢ（登録商標）は、一般的な数値シミュレーションおよび分析ツールである。このグラフは、要素０および１が、値２と比較してより頻繁に出力に現れることを示す。混合基数数生成器処理（上で図２に関して説明した）が、１の固定回転オフセットと共に使用される場合に、統計的アーティファクトは、ガロア体ＧＦ［３］のすべての同値類にまたがってほぼ均等に拡散される。ＭＡＴＬＡＢ（登録商標）シミュレーションから得られた図２の混合基数数生成器処理の結果を示すグラフを、図３Ｂに示す。図３Ｂのグラフは、出力数列での要素０、１、および２の一様分布を示す。
【００３１】
混合基数数生成器法
ここで図４を参照すると、統計的アーティファクトをガロア体ＧＦ［Ｐ］のすべての同値類にまたがって均等に拡散する混合基数数生成器法４００の流れ図が示されている。この流れ図は、図２に示された概念の代替表現である。図４に示されているように、方法４００は、ステップ４０２で開始され、ステップ４０４に継続する。ステップ４０４では、比較的大きい第１ガロア体ＧＦ［Ｍ］を選択する。ＭおよびＰの相対サイズは、任意の値をとることができ、本願で説明される統計的特性を保持する。Ｍの値は、通常、Ｐより数桁大きくなるように選択されるが、これは、実施形態が正しく機能するための要件ではない。ステップ４０４は、第１ガロア体ＧＦ［Ｍ］より小さい第２ガロア体ＧＦ［Ｐ］を選択することをも含む。ステップ４０４は、さらに、ガロア体標数Ｐに関して互いに素になるようにガロア体標数Ｍを選択することを含む。用語「互いに素」は、本明細書で使用される時に、１を除く整数の公約数を有しない複数の整数を指す。
【００３２】
ステップ４０４の後に、方法４００はステップ４０６に継続する。ステップ４０６では、相対的に大きいガロア体ＧＦ［Ｍ］によって定義されるリング構造を利用して、第１乱数列を生成する。それでも、本発明は、これに関して限定されない。たとえば、第１乱数列を、穴をあけられたガロア体ＧＦ’［Ｍ］によって定義されるリング構造を利用して生成することもできる。本明細書で使用される時に、用語「穴をあけられた」は、所望の標数の整数倍数を超える少なくとも１つの要素がガロア体ＧＦ［Ｍ］内で破棄されていることを意味する。
【００３３】
もう一度図４を参照すると、第１乱数列は、乱数ＲＮ1，ＲＮ2，…，ＲＮNを含む。この乱数列は、擬似乱数列または擬似無秩序数列とすることができる。これに関して、乱数生成器（ＲＮＧ）を、相対的に大きいガロア体ＧＦ［Ｍ］または穴をあけられたガロア体ＧＦ’［Ｍ］上で乱数列を生成するのに使用できることを理解されたい。ＲＮＧは、当業者に周知であり、したがって、本明細書では詳細には説明しない。しかし、当技術分野で既知のどのＲＮＧでも、制限なしに使用できることを理解されたい。
【００３４】
その後、方法４００は、ステップ４０８に継続する。ステップ４０８および後続のステップ４１０（下で説明する）は、集合的に、混合基数変換の望まれない統計的アーティファクトを除去する手段を提供する。また、ステップ４０８および後続のステップ４１０（下で説明する）は、集合的に、統計的アーティファクトをガロア体ＧＦ［Ｐ］のすべての同値類にまたがって均等に拡散する手段を提供する。この統計的アーティファクトの均等な分布は、所望の統計的特性すなわちガロア体ＧＦ［Ｐ］にまたがるガロア体ＧＦ［Ｍ］からの要素の一様分布の確率的厳守を提供する。さらに、ステップ４０８および後続のステップ４１０（下で説明する）は、集合的に、ガロア体ＧＦ［Ｐ］の同値類にまたがって選択された統計的アーティファクトを誘導する手段をも提供する。
【００３５】
ステップ４０８で、算術演算を実行して、第１乱数列の各乱数ＲＮ1，ＲＮ2，…，ＲＮNを、Ｐを法とする剰余演算の結果と組み合わせる。Ｐは、ガロア体ＧＦ［Ｐ］のガロア体標数である。Ｐを法とする剰余演算は、第１乱数列の先行する乱数ＲＮ1，ＲＮ2，…，ＲＮNを利用する。算術演算は、一般に、数式（１）から（４）によって定義することができる。
ＲＮ1’＝ＲＮ1＋０ （１）
ＲＮ2’＝ＲＮ2＋ＲＮ1’ ｍｏｄｕｌｏ Ｐ （２）
ＲＮ3’＝ＲＮ3＋ＲＮ2’ ｍｏｄｕｌｏ Ｐ （３）
……
ＲＮN’＝ＲＮN＋ＲＮN-1’ ｍｏｄｕｌｏ Ｐ （４）
ここで、ＲＮ1’は、１番目の算術演算から導出された変更された１番目の乱数である。ＲＮ2’は、２番目の算術演算から導出された変更された２番目の乱数である。ＲＮ3’は、３番目の算術演算から導出された変更された３番目の乱数である。ＲＮN’は、Ｎ番目の算術演算から導出された変更されたＮ番目の乱数である。ＲＮN-1’は、最後から２番目の算術演算から導出された最後から２番目の変更された乱数である。ＲＮ1は、第１乱数列の１番目の乱数である。ＲＮ2は、第１乱数列の２番目の乱数である。ＲＮ3は、第１乱数列の３番目の乱数である。ＲＮNは、第１乱数列の最後の乱数である。Ｐは、ガロア体ＧＦ［Ｐ］の有限体サイズを定義する正の整数になるように選択された値を有する係数である。
【００３６】
ステップ４０８の代替実施形態は、第１乱数列の各乱数ＲＮ1，ＲＮ2，…，ＲＮNを、Ｐを法とする剰余演算の結果に固定オフセットを加えたものと組み合わせることである。Ｐは、ガロア体ＧＦ［Ｐ］のガロア体標数である。Ｐを法とする剰余演算は、第１乱数列の先行する乱数ＲＮ1，ＲＮ2，…，ＲＮNを利用する。この算術演算は、一般に、数式（５）から（８）によって定義することができる。
ＲＮ1’＝ＲＮ1＋Ｃ （５）
ＲＮ2’＝ＲＮ2＋ＲＮ1’＋Ｃ ｍｏｄｕｌｏ Ｐ （６）
ＲＮ3’＝ＲＮ3＋ＲＮ2’＋Ｃ ｍｏｄｕｌｏ Ｐ （７）
……
ＲＮN’＝ＲＮN＋ＲＮN-1’＋Ｃ ｍｏｄｕｌｏ Ｐ （８）
ここで、ＲＮ1’は、１番目の算術演算から導出された変更された１番目の乱数である。ＲＮ2’は、２番目の算術演算から導出された変更された２番目の乱数である。ＲＮ3’は、３番目の算術演算から導出された変更された３番目の乱数である。ＲＮN’は、Ｎ番目の算術演算から導出された変更されたＮ番目の乱数である。ＲＮN-1’は、最後から２番目の算術演算から導出された最後から２番目の変更された乱数である。ＲＮ1は、第１乱数列の１番目の乱数である。ＲＮ2は、第１乱数列の２番目の乱数である。ＲＮ3は、第１乱数列の３番目の乱数である。ＲＮNは、第１乱数列の最後の乱数である。Ｐは、ガロア体ＧＦ［Ｐ］の有限体サイズを定義する正の整数になるように選択された値を有する係数である。Ｃは、すべての固定点を除去する形で有効出力を回転するように選択される任意の定数である。
【００３７】
ステップ４０８の後に、方法４００はステップ４１０に継続する。ステップ４１０が、第２乱数列を生成するために実行されることを理解されたい。この第２乱数列は、第２ガロア体ＧＦ［Ｐ］のすべての同値類にまたがって均等に分布する統計的アーティファクトを有する。ステップ４１０は、ステップ４０８で実行された算術演算から導出された変更された乱数ＲＮ1’，ＲＮ2’，ＲＮ3’，…，ＲＮN’を利用して算術演算を実行することを含む。
【００３８】
これらの算術演算は、数式（９）から（１２）によって定義することができる。
Ｒ1＝ＲＮ1’ ｍｏｄｕｌｏ Ｐ （９）
Ｒ2＝ＲＮ2’ ｍｏｄｕｌｏ Ｐ （１０）
Ｒ3＝ＲＮ3’ ｍｏｄｕｌｏ Ｐ （１１）
……
ＲN＝ＲＮN-1’ ｍｏｄｕｌｏ Ｐ （１２）
ここで、Ｒ1は、１番目の算術演算から導出された結果である。Ｒ2は、２番目の算術演算から導出された結果である。Ｒ3は、３番目の算術演算から導出された結果である。ＲNは、最後の算術演算から導出された結果である。ＲＮ1’は、ステップ４０８で実行された１番目の算術演算から導出された変更された１番目の乱数である。ＲＮ2’は、ステップ４０８で実行された２番目の算術演算から導出された変更された２番目の乱数である。ＲＮ3’は、ステップ４０８で実行された３番目の算術演算から導出された変更された３番目の乱数である。ＲＮN’は、ステップ４０８で実行されたＮ番目の算術演算から導出された変更されたＮ番目の乱数である。Ｐは、ガロア体ＧＦ［Ｐ］の有限体サイズを定義する正の整数になるように選択された値を有する係数である。結果Ｒ1，Ｒ2，…，ＲNのそれぞれが、ガロア体ＧＦ［Ｐ］からの要素｛０，１，２，…，Ｐ−１｝であることを理解されたい。第２乱数列が、乱数の集合すなわちＲ1，Ｒ2，…，ＲNによって定義されることを理解されたい。
【００３９】
図４をもう一度参照すると、方法４００は、ステップ４１２に継続する。ステップ４１２で、方法４００が終了する。方法４００が、従来の混合基数変換の望まれない統計的アーティファクト除去する１つの方法であることを理解されたい。しかし、本発明は、これに関して限定されず、統計的アーティファクトをガロア体ＧＦ［Ｐ］のすべての同値類にまたがって均等に拡散するように構成された任意の他の混合基数数生成器法を、制限なしに使用することができる。
【００４０】
データストリームを変更する方法
ここで図５を参照すると、本発明を理解するのに有用な、データストリームを変更する従来の方法５００の流れ図が示されている。図５に示されているように、方法５００は、ステップ５０２で開始され、ステップ５０４に継続する。ステップ５０４で、乱数列を生成する。この乱数の数列が、比較的大きいガロア体ＧＦ［Ｍ］内に含まれることを理解されたい。乱数列を生成した後に、ステップ５０６が実行され、ここで、乱数列の一部を選択する。
【００４１】
ステップ５０６の後に、方法５００は、ステップ５０８に継続する。ステップ５０８では、乱数列の一部を入力データストリームと組み合わせ、これによって入力データストリームを変更する。これに関して、乱数列の一部が、入力データストリームのサイズ以上のサイズを有すること、すなわち、これらが同一の基数（または基）で表される場合である、を理解されたい。したがって、方法５００を、それ相応に変更することができる。たとえば、方法５００に、ステップ５０８の前に変換ステップを含めることができる。この変換ステップは、入力データストリームがサイズＧＦ［ｎ］またはＧＦ［ｎ／ｄ］である場合に、乱数列の一部をサイズＧＦ［Ｍ］からサイズｎに変換することを含むことができ、ここで、ｄは、ｎの偶数の約数である。その後、ステップ５１０が実行され、ここで方法５００が終了する。
【００４２】
理解されるとおり、比較的大きいガロア体ＧＦ［Ｍ］は、変換方法５００にある度合のセキュリティを提供する。これに関して、ガロア体ＧＦ［Ｍ］が、有限の個数の要素｛０，１，２，…，Ｍ−１｝だけを含む体であることを了解されたい。ガロア体ＧＦ［Ｍ］は、ガロア標数Ｍによって定義される有限体サイズを有する。したがって、出力数列が、Ｍ番目の要素おきに繰り返す可能性がある。この繰返し挙動は、相関を生じる可能性があり、これによって、Ｍが小さい場合に、変更されたデータストリームの復号が比較的簡単になる。その結果、比較的大きいガロア体ＧＦ［Ｍ］を選択することが望ましい。
【００４３】
乱数列の一部を選択することも、変換方法５００にある度合のセキュリティを提供することをも了解されたい。たとえば、ある乱数列が、ガロア体ＧＦ［Ｍ］上で生成される。この例では、この乱数列が、５００ビットを含むと仮定する。乱数列の一部が、５００ビットのうちの１６ビットだけを含むように選択される。データストリームを変更するのに、この乱数列のうちの１６ビットだけを使用することによって、この乱数列を生成するのに使用されたガロア体ＧＦ［Ｍ］を判定することが、よりむずかしくなる。それでも、この方法のセキュリティをさらに高めることが望ましい。
【００４４】
ここで図６を参照すると、通信システムのセキュリティを高める方法６００が示されている。図６に示されているように、方法６００は、ステップ６０２で開始され、ステップ６０４に継続する。ステップ６０４で、比較的大きいガロア体ＧＦ［Ｍ］を選択する。理解されるとおり、大きいガロア体は、通信システムの攻撃者が、オリジナル乱数列の生成に使用されたガロア体ＧＦ［Ｍ］を、変更されたデータストリームから判定できる可能性を最小にすることができる。実際には、大きいガロア体ＧＦ［Ｍ］は、方法６００を実施する通信システムに、ある度合のセキュリティを提供することができる。別の形で言えば、乱数列のセキュリティは、主に、出力値のダイナミックレンジ（ビット数または桁数）およびみかけのランダムさによって定義される。
【００４５】
その後、ステップ６０６が実行され、ここで、第１乱数列を、ガロア体ＧＦ［Ｍ］によって定義されるリング構造を利用して生成する。それでも、本発明は、これに関して限定されない。たとえば、第１乱数列を、穴をあけられたガロア体ＧＦ’［Ｍ］によって定義されるリング構造を利用して生成することもできる。この数列の各乱数は、ガロア体ＧＦ［Ｍ］または穴をあけられたガロア体ＧＦ’［Ｍ］の要素によって定義される。ステップ６０８で、第１乱数列の一部を選択する。このステップは、方法６００を実施する通信システムに、高い度合のセキュリティを提供する。これに関して、乱数列の一部だけが入力データストリームを変更するのに使用される場合に、ガロア体ＧＦ［Ｍ］を判定することが、よりむずかしくなることを了解されたい。
【００４６】
ステップ６１０も、第２乱数列を生成するために算術演算を実行することを含む。この第２乱数列は、第２ガロア体ＧＦ［Ｐ］のすべての同値類にまたがって均等に分布する統計的アーティファクトを有する。本発明の好ましい実施形態によれば、これらの算術演算は、上で図２に関して説明した混合基数数生成器処理とすることができる。それでも、本発明がこれに関して限定されないことを了解されたい。任意の他の適切な技法を、この目的に使用することができる。
【００４７】
もう一度図６を参照すると、方法６００は、ステップ６１２に継続する。ステップ６１２では、第２乱数列を、乗算器などのデバイスに通信する。第２乱数列を入力データストリームと組み合わせて、変更されたデータストリームを形成する。入力データストリームは、サイズＧＦ（ｎ）またはＧＦ（ｎ／ｄ）を有し、ここで、ｄは、ｎの偶数の約数である。これに関して、第２乱数列および入力データストリームが、同一のサイズを有する、すなわち、これらが、同一の基数（または基）で表され、同一の桁数を含むことを理解されたい。その後、ステップ６１６が実行され、ここで方法６００が終了する。
【００４８】
当業者は、方法６００が、通信システムのセキュリティを高める１つの方法であることを了解するであろう。しかし、本発明は、これに関して限定されず、本発明を実施する任意の他の方法を、制限なしに使用することができる。
【００４９】
ハードウェア実施態様
従来の混合基数変換アルゴリズムの望まれない統計的アーティファクトを除去する方法４００（上で図４に関して説明した）を実施するさまざまな形がある。たとえば、混合基数数生成器方法４００を、図２に示されたものに似た混合基数アキュムレータ配置を利用して実施することができる。混合基数数生成器を、データストリームを変更するために通信システムおよび／または暗号系内に配備することができる。そのようなシナリオでは、混合基数数生成器は、高められたセキュリティ特徴を通信システムおよび／または暗号系に提供することができる。そのような混合基数数生成器を、以下で図７に関して説明する。
【００５０】
ここで図７を参照すると、混合基数数生成器７００のブロック図が示されている。混合基数数生成器７００は、乱数生成器７０２、混合基数アキュムレータ７５０、および外部デバイス７１０からなる。乱数生成器７０２は、リング生成器、穴をあけられたリング生成器、またはカオス生成器（ｃｈａｏｓ ｇｅｎｅｒａｔｏｒ）とすることができるが、これらに限定はされない。乱数生成器７０２がリング生成器である場合に、乱数生成器７０２は、ガロア体ＧＦ［Ｍ］によって定義されるリング構造を利用して乱数列を生成するように構成されたハードウェアおよび／またはソフトウェアからなる。乱数生成器が穴をあけられたリング生成器である場合に、乱数生成器７０２は、穴をあけられたガロア体ＧＦ’［Ｍ］によって定義されるリング構造を利用して乱数列を生成するように構成されたハードウェアおよび／またはソフトウェアからなる。したがって、乱数生成器７０２の出力を、ガロア体ＧＦ［Ｍ］からのランダム要素または穴をあけられたガロア体ＧＦ’［Ｍ］からのランダム要素とすることができる。ガロア体ＧＦ［Ｍ］または穴をあけられたガロア体ＧＦ’［Ｍ］から所望のガロア体標数Ｐに要素を写像するために、ガロア体標数Ｍは、ガロア体標数Ｐに対して相対的に素になるように選択される。また、ガロア体標数Ｍは、ガロア体標数Ｐより大きくなるように選択される。
【００５１】
また、乱数生成器７０２は、乱数列の乱数を混合基数アキュムレータ７５０に通信するように構成されたハードウェアおよび／またはソフトウェアからなる。混合基数アキュムレータ７５０は、第２乱数を生成するために算術演算を実行するように構成される。この算術演算は、乱数生成器７０２から受け取られた乱数を利用して剰余値を計算することを含む。したがって、混合基数アキュムレータ７５０は、加算器７０４、算術演算子７０６、および遅延７０８からなる。
【００５２】
加算器７０４は、乱数生成器７０２から乱数を受け取り、遅延７０８（以下で説明する）から時間遅延された剰余を受け取るように構成されたハードウェアおよび／またはソフトウェアからなる。また、加算器７０４は、乱数生成器７０２から受け取られた乱数および遅延７０８（以下で説明する）から受け取られた時間遅延された剰余を使用して加算演算を実行するように構成されたハードウェアおよび／またはソフトウェアからなる。また、加算器７０４は、この加算演算の和を算術演算子７０６に通信するように構成されたハードウェアおよび／またはソフトウェアからなる。
【００５３】
算術演算子７０６は、算術演算を実行するように構成されたハードウェアおよび／またはソフトウェアからなる。この算術演算には、モジュロ演算を実行することを含めることができる。モジュロ演算は、当業者に周知であり、したがって、本明細書では詳細には説明しない。しかし、モジュロ演算を、一般に、数式Ｒ＝Ｓ ｍｏｄｕｌｏ Ｐによって定義できることを了解されたい。ここで、Ｒは、モジュロ演算から導出される剰余である。Ｓは、算術演算子７０６に入力される乱数である。Ｐは、ガロア体ＧＦ［Ｐ］の有限体サイズを定義する正の整数になるように選択される値を有する係数である。剰余Ｒが、ガロア体ＧＦ［Ｐ］からの要素であることを理解されたい。
【００５４】
算術演算子７０６は、さらに、剰余Ｒを外部デバイス７１０および遅延７０８に通信するように構成されたハードウェアおよび／またはソフトウェアからなる。外部デバイス７１０は、剰余を入力データまたはディジタルデータストリームと組み合わせるように構成されたコンバイナとすることができる。たとえば、外部デバイスは、本発明の一実施形態で乗算器である。遅延７０８は、算術演算子７０６から受け取られた剰余Ｒをｚ-NクロックサイクルまたはＮクロックサイクルだけ遅延させるように構成されたハードウェアおよびソフトウェアからなり、ここで、ｚ-1は、１サンプルクロック周期遅延または単位遅延であり、Ｎは、正の整数値である。ｚ-Nは、Ｎクロック周期遅延である。たとえば、遅延７０８は、剰余Ｒを１クロックサイクルだけ遅延させるように構成される。それでも、本発明はこれに関して限定されない。
【００５５】
当業者は、混合基数数生成器７００が、本発明を実施する混合基数数生成器の１つのアーキテクチャであることを了解するであろう。しかし、本発明はこれに関して限定されず、本発明を実施する任意の他の混合基数数生成器アーキテクチャを、制限なしに使用することができる。
【００５６】
図１〜７に関して説明した混合基数数生成器の方法およびシステムが、数Ｐのサイズまたは構成に関して限定されないことを理解されたい。たとえば、Ｐは、Ｐがｐ1・ｐ2・，…，・ｐkの積と等しくなるように選択することができ、ここで、ｋ個の係数のすべてが、Ｍおよび互いに関して互いに素である。この系の標数は、ｋ個の個々の出力を提供する、ある種の代替実施形態を容易にすることができ、このｋ個の個々の出力のそれぞれは、上で図１〜７に関して説明した系と比較して、類似する統計的挙動を提供することができる。そのような混合基数数生成器を、図８に示す。
【００５７】
複数の出力を有する混合基数アキュムレータ
ここで図８を参照すると、複数の出力を供給する混合基数数生成器８００の代替実施形態のブロック図が示されている。混合基数数生成器８００は、乱数生成器８０２および混合基数アキュムレータ８５０からなる。乱数生成器８０２は、リング生成器、穴をあけられたリング生成器、またはカオス生成器とすることができるが、これらに限定はされない。乱数生成器８０２がリング生成器である場合に、乱数生成器８０２は、ガロア体ＧＦ［Ｍ］によって定義されるリング構造を利用して乱数列を生成するように構成されたハードウェアおよび／またはソフトウェアからなる。乱数生成器が穴をあけられたリング生成器である場合に、乱数生成器８０２は、穴をあけられたガロア体ＧＦ’［Ｍ］によって定義されるリング構造を利用して乱数列を生成するように構成されたハードウェアおよび／またはソフトウェアからなる。したがって、乱数生成器８０２の出力を、ガロア体ＧＦ［Ｍ］からのランダム要素または穴をあけられたガロア体ＧＦ’［Ｍ］からのランダム要素とすることができる。
【００５８】
ガロア体ＧＦ［Ｍ］または穴をあけられたガロア体ＧＦ’［Ｍ］から所望のガロア体標数Ｐに要素を写像するために、ガロア体標数Ｍは、ガロア体標数Ｐに対して相対的に素になるように選択され、Ｐは、ｐ1・ｐ2・，…，・ｐkの積と等しい。また、ガロア体標数Ｍは、ガロア体標数Ｐの係数ｐ1・ｐ2・，…，・ｐkと互いに素になるように選択される。ガロア体標数Ｍは、さらに、ガロア体標数Ｐより大きくなるように選択される。
【００５９】
また、乱数生成器８０２は、乱数列の乱数を混合基数アキュムレータ８５０に通信するように構成されたハードウェアおよび／またはソフトウェアからなる。混合基数アキュムレータ８５０は、混合基数アキュムレータ７５０に類似し、類似する機能を実行する構成を有利に有する。これに関して、この混合基数アキュムレータは、第２乱数を生成するために算術演算を実行するように構成される。この算術演算は、乱数生成器８０２から受け取られた乱数を利用して剰余値を計算することを含む。したがって、混合基数アキュムレータ８５０は、加算器８０４および遅延８０８からもなる。
【００６０】
乱数生成器８０２は、複数の算術演算子８１０1、８１０2、…８１０kをも含む。算術演算子８１０1、８１０2、…８１０kのそれぞれは、算術演算を実行するように構成されたハードウェアおよび／またはソフトウェアからなる。この算術演算には、モジュロ演算を実行することを含めることができる。好ましい実施形態によれば、モジュロ演算は、数式Ｒ＝ｍｏｄｕｌｏ ｐによって定義され、Ｒは、算術演算子８０６によって実行されたモジュロ演算から導出される剰余であり、ｐは、ガロア体標数Ｐの係数ｐ1，ｐ2，…，・ｐkのうちの１つである。また、算術演算子８１０1、８１０2、…８１０kのそれぞれは、ｋ個の出力のうちの１つを作るように構成されたハードウェアおよび／またはソフトウェアからなる。算術演算子８１０1、８１０2、…８１０kのそれぞれは、ガロア体ＧＦ［ｐ1-k］の要素を出力として供給し、この出力は、外部デバイス（図示せず）に転送することができる。外部デバイスは、剰余を入力データと組み合わせるように構成された任意のデバイスとすることができる。たとえば、一実施形態で、外部デバイスは、乗算器である。より重要なことに、算術演算子８１０1、８１０2、…８１０kからのｋ個の出力のうちの１つとして供給される各数列は、望まれない統計的アーティファクトがない、一様に分布する出力を有する。
【００６１】
当業者は、混合基数数生成器８００が、本発明を実施する混合基数数生成器の１つのアーキテクチャであることを了解するであろう。しかし、本発明はこれに関して限定されず、本発明を実施する任意の他の混合基数数生成器アーキテクチャを、制限なしに使用することができる。１つのそのような実施形態によれば、遅延８０８を有限インパルス応答（ＦＩＲ）フィルタまたは無限インパルス応答（ＩＩＲ）フィルタに置換することができ、この場合に、すべての演算が、変更されたＧＦ算術を使用して実行される。
【００６２】
混合基数数生成器の複数レート実施態様
ここで図９を参照すると、本発明の第２の代替実施形態が示されている。第２の代替実施形態は、混合基数数生成器９００の複数レート実施態様である。複数レート実施態様は、乱数生成器からの出力を周期的にサンプリングすること、または所望の出力の集合と比較してより高いレートでそのような出力をサンプリングすることのいずれかを含むことができる。やはり、これは、観察者が簡単には再構築できない値の累積につながる。
【００６３】
図９に示されているように、混合基数数生成器９００は、乱数生成器９０２および混合基数アキュムレータ９５０からなる。乱数生成器９０２および混合基数アキュムレータ９５０は、上で図８に関して説明した対応する構造８０２、８５０に類似する。したがって、混合基数アキュムレータ９５０も、加算器９０８および遅延９１８からなるものとすることができる。算術演算子ユニット９１２1、９１２2、…９１２kの組を、図８の算術演算子ユニット８１０1、８１０2、…８１０kに類似する演算を実行するために設けることもできる。複数レート処理は、当業者に周知であり、したがって、本明細書では詳細には説明しない。
【００６４】
混合基数数生成器９００は、加算器９０４および遅延９０６をも含む。加算器９０４は、乱数生成器９０２から乱数を受け取り、遅延９０６（以下で説明する）から時間遅延された出力を受け取るように構成されたハードウェアおよび／またはソフトウェアからなる。また、加算器９０４は、乱数生成器９０２受け取られた乱数および遅延９０６から受け取られた時間遅延された出力を使用して加算演算を実行するように構成されたハードウェアおよび／またはソフトウェアからなる。また、加算器９０４は、加算演算の和を遅延９０６に通信するように構成されたハードウェアおよび／またはソフトウェアからなる。
【００６５】
遅延９０６は、加算器９０４から受け取られた和をＮクロックサイクルだけ遅延させるように構成されたハードウェアおよびソフトウェアからなる。それでも、本発明はこれに関して限定されない。また、遅延９０６は、時間遅延された出力（すなわち、時間遅延された和）を加算器９０４、９０８に通信するように構成されたハードウェアおよびソフトウェアからなる。
【００６６】
当業者は、混合基数数生成器９００が、本発明を実施する混合基数数生成器の１つのアーキテクチャであることを了解するであろう。しかし、本発明はこれに関して限定されず、本発明を実施する任意の他の混合基数数生成器アーキテクチャを、制限なしに使用することができる。
【００６７】
本発明の前述の説明に鑑みて、本発明をハードウェア、ソフトウェア、またはハードウェアおよびソフトウェアの組合せで実現できることを認められたい。本発明によるビットの任意の置換順序を生成する方法は、１つの処理システム内で集中化された形で、または異なる要素が複数の相互接続された処理システムにまたがって拡散される分散された形で、実現することができる。本明細書で説明した方法を実行するように適合されたすべての種類のコンピュータシステムまたは他の装置が、適する。ハードウェアおよびソフトウェアの通常の組合せは、ロードされ実行された時に本明細書で説明した方法を実行するようにコンピュータプロセッサを制御するコンピュータプログラムを伴う、汎用コンピュータプロセッサとすることができる。もちろん、特定用途向け集積回路（ＡＳＩＣ）および／またはＦＰＧＡを使用して、類似する結果を達成することもできる。
【００６８】
本発明を、本明細書で説明した方法の実施を可能にするすべての特徴を含み、コンピュータシステムにロードされた時にこれらの方法を実行することができる、コンピュータプログラム製品で実施することもできる。現在の文脈でのコンピュータプログラムまたはアプリケーションは、ａ）別の言語、コード、もしくは表記への変換、またはｂ）異なる材料形態での再作成のいずれかまたは両方の後にあるいは直接にのいずれかで特定の機能を実行する情報処理能力をシステムが有するようにすることを意図された命令の組の、任意の言語、コード、または表記でのすべての表現を意味する。さらに、上の説明は、例のみとして意図されており、添付の特許請求の範囲で示されるものを除いて、いかなる形でも本発明を限定することは意図されていない。
【図面の簡単な説明】
【００６９】
【図１】本発明を理解するのに有用な、従来の混合基数変換アルゴリズムを示す概念図である。
【図２】統計的アーティファクトをガロア体ＧＦ［Ｐ］のすべての同値類にまたがって均等に拡散する混合基数リング生成器を示す概念図である。
【図３Ａ】本発明を理解するのに有用な、従来の混合基数変換アルゴリズムの統計シミュレーションを示すグラフを示す図である。
【図３Ｂ】本発明を理解するのに有用な、混合基数数生成器法の統計シミュレーションを示すグラフを示す図である。
【図４】統計的アーティファクトをガロア体ＧＦ［Ｐ］のすべての同値類にまたがって均等に拡散する混合基数数生成器法を示す流れ図である。
【図５】本発明を理解するのに有用な、データストリームを変更する従来の方法を示す流れ図である。
【図６】本発明を理解するのに有用な、通信システムのセキュリティを高める方法を示す流れ図である。
【図７】本発明を理解するのに有用な、生成器出力をデータストリームと組み合わせる機構に接続された混合基数数生成器を示すブロック図である。
【図８】本発明を理解するのに有用な、混合基数数生成器を示すブロック図である。
【図９】本発明を理解するのに有用な、混合基数数生成器を示すブロック図である。
【符号の説明】
【００７０】
２０２、７０２、８０２、９０２ 乱数生成器
２０４、７０４、８０４、９０４、９０８ 加算器
２０５ 遅延ユニット
２０６ Ｐを法とする剰余演算子
７００、８００、９００ 混合基数数生成器
７０６、８０６、８１０、９１０、９１２ 算術演算子
７０８、８０８、９０６、９１８ 遅延
７１０ 外部デバイス
７５０、８５０、９５０ 混合基数アキュムレータ
【技術分野】
【０００１】
本発明配置は、混合基数変換を使用する通信システムに関する。より具体的には、本発明配置は、選択されたガロア体ＧＦ［Ｐ］のすべての同値類上で選択された統計的特性を有する乱数列を作るために混合基数リングの生成および変換を実行する方法およびシステムに関する。
【背景技術】
【０００２】
通信システムは、多数の応用例でリング生成器を含むことができる。リング生成器は、繰り返される写像を介して可能な出力を網羅的に作る有限体上の単純な構造である。この写像は、加法的写像および乗法的写像のある組合せであり、既約多項式はイデアルである。たとえば、リング生成器は、１１個の要素を含む有限ガロア体ＧＦ［１１］での既約多項式ｆ（ｘ）＝３ｘ3＋３ｘ2＋ｘの繰り返される計算を含む。有限体またはガロア体ＧＦ［Ｐ］は、有限な個数の要素｛０，１，２，…，Ｐ−１｝だけを含む体である。有限体またはガロア体ＧＦ［Ｐ］は、ガロア標数Ｐによって定義される有限体サイズを有し、Ｐは、しばしば、整数論的結果に基づいて素数になるように選択される。この計算は、通常、ルックアップテーブル動作、フィードバックループ、または乗算器構造としてディジタルハードウェアで実施される。
【０００３】
そのようなリング生成器の利益にかかわらず、リング生成器は、ある短所をこうむる。たとえば、リング生成器のガロア標数Ｐが、素数（２と等しくない）になるように選択される場合に、計算は、通常、ディジタル（２進）領域で非効率的である。また、有限体またはガロア体ＧＦ［Ｐ］で実行されるルックアップテーブル動作は、ガロア標数Ｐが大きい場合に、メモリ集中型である。さらに、リング生成器の出力値は、非常に決定的である。したがって、写像および現在の有限体条件の知識は、出力数列の完全な知識を与える。
【０００４】
リング生成器の出力数列を意図されない再構築からマスクする１つの方法は、より大きい有効領域への全単写像を実行するアルゴリズムを介して複数のリング生成器を組み合わせることである。この組合せの例は、個々のリング生成器のガロア標数が互いに素である時の中国の剰余定理（ＣＲＴ）を介するものである。もう１つの方法は、領域ＧＦ［Ｐ］から２進領域ＧＦ［２k］への混合基数変換を実行することによってリング生成器出力値を単純に切り詰めることである。これらのマスキング法の両方が、オリジナル数列を部分的にマスクするが、それでも、これらは、まだ、数列値を再エンジニアリングするのに使用できる統計的アーティファクトを提示する。暗号学では、そのような試みを、しばしば、周期攻撃（ｆｒｅｑｕｅｎｃｙ ａｔｔａｃｋ）と呼び、これによって、個人が、統計的分析を介して擬似ランダム数列の写像および状態特性の部分的情報を得ることができる。この処理の通常の門外漢の例が、ある文字を別の文字と交換するワードパズルである。英語の知識は、ＥがＺより優勢であるという部分的知識を与える。実際には、検索は、ブルートフォースからより論理的な検索に限定される。
【特許文献１】日本国特許出願公開第２００２−２９７０３３Ａ号
【特許文献２】米国特許第７０６９４９２号
【特許文献３】米国特許第７０７９６５１号
【特許文献４】日本国特許出願公開第２００３−５３３７５２Ａ号
【発明の開示】
【発明が解決しようとする課題】
【０００５】
前述に鑑みて、ディジタル（２進）領域で計算的に効率的であり、著しい統計的アーティファクトを全く有しない、混合基数変換法の必要が残っている。また、従来のリング生成器実施態様よりハードウェア集中的ではない実施態様を有し、選択された統計的特性を有する擬似乱数列を作る、リング生成器の必要がある。さらに、非決定的に見える軌道を有するリング生成器の必要がある。
【課題を解決するための手段】
【０００６】
本発明は、数列を生成するのに使用される処理をマスクする方法に関する。この方法は、生成するステップ、第１変更ステップ、および第２変更ステップを含む。生成するステップは、ガロア体ＧＦ［Ｍ］内に含まれる第１数列を生成することを含む。第１変更ステップは、第１数列内の第１の数に対して第１変更を実行することを含む。第１変更は、第１の数に先行する第１数列の第２の数に対して実行されるＰを法（ｍｏｄｕｌｏ）とする剰余演算の結果と第１の数とを合計することによって達成される。Ｍは、Ｐに関して相対的に素である。第２変更ステップは、第１の数に対して第２変更を実行することを含む。第２変更は、Ｐを法とする剰余演算からなる。第２変更は、第１変更の後に実行される。この方法は、さらに、第２数列を生成するために、第１数列を含む１つまたは複数の数について第１および第２の変更を繰り返すことを含む。
【０００７】
本発明の態様によれば、この方法は、第２数列を用いてディジタルデータストリームを変更することを含む。生成するステップは、生成するステップに関する選択された統計的アーティファクトを含む擬似乱数列を生成することをも含む。統計的アーティファクトは、通常、第１および第２の変更ステップによってＧＦ［Ｐ］上の乱数の一様に分布する数列を作成するように選択される。本明細書で使用される時に、「乱数の一様に分布する数列」は、数列内の各数値が完全一様分布からのランダム選択を近似し、保護空間内のすべての要素が、選択される同等の見込みを有する数列である。生成するステップは、さらに、周期的に繰り返される写像を使用することによって第１数列を網羅的に作ることを含む。この写像は、加法的写像および乗法的写像の組合せを含むように選択される。加法的写像および乗法的写像は、ガロア体ＧＦ［Ｍ］上の既約多項式の繰り返される計算を含めるために組み合わせて選択される。
【０００８】
本発明のもう１つの態様によれば、この方法は、Ｐより大きいＭの値を選択することを含む。この方法は、Ｐおよびｐ1，ｐ2，ｐ3，…ｐkを含むＰの複数の素因数のすべてと互いに素であるＭの値を選択することをも含む。この方法は、第２数列に対して第３変更ステップを実行することをさらに含む。第３変更ステップは、第２数列から１つまたは複数の出力数列を生成することを含む。第３変更ステップは、出力数列を生成するために第２数列内の各数に対して実行されるｐを法とする剰余演算をも含む。ｐは、ｐ1，ｐ2，ｐ3，…ｐkを含む群から選択される複数の値を含む。
【０００９】
本発明のもう１つの実施形態によれば、第２の数は、第１の数に直接に先行する。第２の数は、ｎ位置だけ第１の数に先行する。ｎは１より大きい。第２数列は、ガロア体ＧＦ［Ｐ］の複数の同値類にまたがって均等に分布する統計的アーティファクトを有する。同値類は、整数０、１、…、Ｐ−１ごとに１つの同値類を含む。
【００１０】
混合基数数生成器（ｍｉｘｅｄ ｒａｄｉｘ ｎｕｍｂｅｒ ｇｅｎｅｒａｔｏｒ）も提供される。混合基数数生成器は、数生成器と混合基数アキュムレータとを含む。数生成器は、ガロア体ＧＦ［Ｍ］内に含まれる第１数列を生成するように構成される。混合基数アキュムレータは、第１数列内の第１の数に対して第１変更を実行するように構成される。第１変更は、第１の数に先行する第１数列の第２の数に対して実行されるＰを法とする剰余演算の結果と第１の数とを合計することによって達成される。Ｍは、Ｐに関して相対的に素である。混合基数アキュムレータは、第１の数に対して第２変更を実行するようにも構成される。第２変更は、Ｐを法とする剰余演算からなる。第２変更は、第１変更の後に実行される。混合基数アキュムレータは、第２数列を生成するために、第１数列を含む複数の数について第１および第２の変更を繰り返すようにさらに構成される。
【００１１】
本発明の一態様によれば、混合基数数生成器は、ディジタルデータストリームを変更するのに第２数列を使用するように構成された手段を含む。数生成器は、擬似乱数生成器からなる。擬似乱数生成器は、第１数列の生成に関する統計的アーティファクトを含む擬似乱数列を生成する。統計的アーティファクトは、混合基数アキュムレータによって除去される。数生成器は、周期的に繰り返される写像を使用することによって第１数列を網羅的に作るようにも構成される。この写像は、加法的写像および乗法的写像の組合せを含む。組み合わされた加法的写像および乗法的写像は、ガロア体ＧＦ［Ｍ］上の既約多項式の繰り返される計算を含む。ＭはＰより大きい。Ｍの値は、Ｐおよびｐ1，ｐ2，ｐ3，…ｐkを含むＰの複数の素因数のすべての値に関して互いに素である。
【００１２】
本発明のもう１つの態様によれば、混合基数数生成器は、１つまたは複数の算術演算子ユニットからなる。算術演算子ユニットのそれぞれは、第２数列に対して第３変更を実行するように構成される。算術演算子ユニットは、第２数列から１つまたは複数の出力数列を生成するように構成される。第３変更は、出力数列を生成するために第２数列内の各数に対して実行されるｐを法とする剰余演算を含む。ｐは、ｐ1，ｐ2，ｐ3，…ｐkを含む群から選択される複数の値を含む。
【００１３】
第２の数は、ｎ位置だけ第１の数に先行する。ｎは１より大きい。第１数列は、ガロア体ＧＦ［Ｍ］によって定義される有限の個数の要素Ｍに制限される。本発明のもう１つの態様によれば、第２の数は、１位置だけ第１の数に先行する。第２の数列は、ガロア体ＧＦ［Ｐ］の複数の同値類にまたがって均等に分布する統計的アーティファクトを有する。同値類は、整数０、１、…、Ｐ−１ごとに１つの同値類を含む。
【００１４】
本発明のもう１つの態様によれば、第１数列は、その計算が等しいサイズのガロア体の中で第２数列に対して実行されるフィルタ構造によって操作される。このフィルタの結果は、第１数列の後続の値と組み合わせるために提示される。本明細書で使用される時に、「フィルタ」は、入力の以前の連続の時間加重和である出力を有する数学的構造を意味する。
【００１５】
実施形態を、図面を参照して説明するが、図面では、類似する符号が、複数の図面を通じて類似する要素を表す。
【発明を実施するための最良の形態】
【００１６】
ここで図１を参照すると、本発明を理解するのに有用な、従来の混合基数変換アルゴリズムの概念図が示されている。通信システムでは、さまざまなアルゴリズムが、数列をデータストリームと組み合わせるのに使用される。この組合せ処理は、通信リンクを介する伝送の前にデータストリームを暗号化するかマスクするために実行することができる。そのようなアルゴリズムには、ガロア体ＧＦ［Ｍ］基数で数列の各数を表す剰余数系（ＲＮＳ）演算を含めることができる。有限体またはガロア体ＧＦ［Ｍ］は、ガロア標数Ｍによって定義される有限体サイズを有する。ガロア体ＧＦ［Ｍ］は、有限の個数の要素｛０，１，２，…，Ｍ−１｝だけを含む体である。したがって、有限体またはガロア体で実行されるすべての算術演算は、その体に含まれる要素をもたらす。したがって、ガロア体ＧＦ［Ｍ］演算の結果の数列は、（Ｍ＋１）番目の要素おきに繰り返す可能性がある。これらのＲＮＳ演算は、当業者に周知であり、したがって、本明細書では詳細には説明しない。しかし、これらのＲＮＳ演算が、混合基数変換を必要とする可能性があることを理解されたい。用語「混合基数変換」は、本明細書で使用される時に、第１基数（または基）から第２基数（または基）への数列の変換を指す。たとえば、ガロア体ＧＦ［７］基数で表された数列は、図１に示されているようにガロア体ＧＦ［３］基数で表された数列に変換される。通常、混合基数変換は、宛先基が開始基より小さく、開始基を均等に分割しない時に、必ず、統計的アーティファクトを生じる。
【００１７】
混合基数変換アルゴリズムには、中国の剰余定理に基づく計算を含めることができる。中国の剰余定理は、当業者に周知であり、したがって、本明細書では詳細には説明しない。しかし、これらの計算が、複数の小さい基数（または基）で表された数を一意に組み合わせるために実行されることを理解されたい。この組合せは、しばしば、写像演算を介して達成される。中国の剰余定理の写像演算は、小さい基数（または基）で表された数のそれぞれを大きい基数で表された数に写像することを伴う。
【００１８】
特筆すべきことに、第１のガロア体ＧＦ［Ｍ1］基数から第２のガロア体ＧＦ［Ｍ2］基数への数列変換から生じる統計分布には、２つの基数が均等に分割可能でない時に、統計的非一様性がある。たとえば、ガロア体ＧＦ［７］基数で表された乱数列が、ガロア体ＧＦ［３］基数で表された数列に写像される。ガロア体ＧＦ［７］基数で表された乱数列は、要素｛０，１，２，…，６｝の集合によって定義される。同様に、ガロア体ＧＦ［３］基数で表された数列は、要素｛０，１，２｝の集合によって定義される。ガロア体ＧＦ［７］基数で表された数列のガロア体ＧＦ［３］基数で表された数列への写像は、一般に、各要素｛０，１，２，…，６｝をそれに対応する同値類の３を法とする剰余によって分割することを伴う。ガロア体ＧＦ［３］は、有限の個数の要素｛０，１，２｝だけを含む有限体なので、整数０、１、および２の対応する同値類がある。
【００１９】
ガロア体ＧＦ［７］からの要素のガロア体ＧＦ［３］の要素への写像演算を、次の表（１）にリストする。
【００２０】
【表１】
表１に示されているように、写像演算は、ガロア体ＧＦ［３］での要素の非一様分布をもたらす。具体的に言うと、写像演算の結果の数列は、｛０ １ ２ ０ １ ２ ０｝と定義される。整数０に関する、同値類のガロア体ＧＦ［７］からの３つの要素｛０，３，６｝がある。整数１に関する、同値類のガロア体ＧＦ［７］からの２つの要素｛１，４｝がある。整数２に関する、同値類のガロア体ＧＦ［７］からの２つの要素｛２，５｝がある。
【００２１】
統計分析を利用することによって、外部当事者が、従来の混合基数変換アルゴリズム（上で図１に関して説明した）を実施するシステムから部分的情報を得ることができ、写像演算の結果の数列によって変更されたデータストリームからオリジナル数列をより簡単に識別することができる。たとえば、２つの基数のサイズがわかれば、攻撃者は、さまざまな同値類の要素の統計的比率を使用して、変更されたデータストリームからオリジナル数列をより簡単に識別することができる。さらに、データメッセージフォーマットの知識は、統計的に有意な形で、乱数列の統計的アーティファクトと一致する。実際には、より多くの情報が、データメッセージ内容で提供される。本明細書で使用される時に、用語「統計的に有意」は、ある情報の有効性の数学的な確実さを指す。したがって、混合基数変換アルゴリズムによって導出される結果から統計的アーティファクトを除去し、その結果、変更されたデータストリームからのオリジナル数列の識別が相対的にむずかしくなるようにすることが、望ましい。
【００２２】
したがって、本発明のいくつかの実施形態は、混合基数変換における望まれない統計的アーティファクトを除去する方法を提供する。１つの方法は、一般に、統計的アーティファクトをガロア体ＧＦ［Ｐ］のすべての同値類にまたがって均等に拡散することを含む。この統計的アーティファクトの均等な分布は、混合基数リング生成器処理を使用することによって達成することができる。この処理は、（１）ガロア体ＧＦ［Ｍ］によって定義されるリングを利用して第１乱数列を生成することと、（２）Ｐを法とする剰余演算を介して以前に計算された剰余を加算することによって第１乱数列の各乱数を変更することと、（３）変更された乱数を利用して第２乱数列を生成することとを含む。第２乱数列は、Ｐを法とする剰余演算を利用しても生成される。第２乱数列は、ガロア体ＧＦ［Ｐ］のすべての同値類にまたがって均等に分布する統計的アーティファクトを含む。
【００２３】
そのような混合基数数生成器処理が、所望の統計的特性の無条件の厳守ではなく、所望の統計的特性の確率的厳守を提供することを理解されたい。用語「確率的厳守」は、イデアルに収束する挙動を指す。用語「無条件の厳守」は、数学的証明によって提供される保証のレベルを指す。そのような混合基数数生成器処理を、さまざまな通信システムアプリケーションで使用できることをも理解されたい。たとえば、そのような混合基数数生成器処理を、データストリームを変更するために暗号系で実施することができる。そのようなシナリオでは、混合基数数生成器処理は、高められたセキュリティ特徴を暗号系に提供する。この混合基数数生成器処理が、性質において非常に非決定的に見える乱数列を作ることに留意されたい。剰余換算（ｍｏｄｕｌｏ ｒｅｄｕｃｔｉｏｎ）を実行する際に、オリジナル数列からの情報は、意図的に破壊される。効果的に、意図されない再構築が、よりむずかしくなる。
【００２４】
これから、本発明を、添付図面を参照して以下でより十分に説明するが、添付図面には、本発明の例示的実施形態が示されている。しかし、本発明を、多数の異なる形で実施することができ、本明細書に示された実施形態に限定されると解釈してはならない。たとえば、本発明を、方法、データ処理システム、またはコンピュータプログラム製品として実施することができる。したがって、本発明は、完全にハードウェアの実施形態、完全にソフトウェアの実施形態、またはハードウェア／ソフトウェア実施形態としての形をとることができる。
【００２５】
ここで図２を参照すると、統計的アーティファクトをガロア体ＧＦ［Ｐ］のすべての同値類にまたがって均等に拡散するのに有用な混合基数数生成器構造の概念図が示されている。図２に示されているように、混合基数リング生成器処理は、乱数生成器２０２での乱数列の生成から開始される。この乱数列は、標数Ｍのガロア体で生成される擬似乱数列または擬似無秩序数列とすることができるが、これらに限定はされない。そのような数列は、最も簡単に、ガロア体ＧＦ［Ｍ］から選択されるランダム要素の数列とみなすことができる。ガロア体ＧＦ［Ｍ］から標数Ｐの所望のガロア体へ要素を写像するために、ガロア体標数Ｍは、ガロア体標数Ｐに対して相対的に素になるように選択される。用語「相対的に素」は、本明細書で使用される時に、１の最大公約数を有する数の集合を指す。
【００２６】
乱数列が、加算器２０４に通信される。上で説明した（図１に関して）統計的異常を打ち消すために、Ｐを法とする剰余演算の以前の出力を、フィードバック構造を介してガロア体ＧＦ［Ｍ］からの次の入力に加算する。このフィードバック構造は、遅延ユニット２０５を含む。次に、この加算演算からの結果を、Ｐを法とする剰余演算子２０６に通信する。Ｐを法とする剰余演算子２０６は、加算演算からの結果に対してＰを法とする演算を実行して、出力値を生成する。その後、Ｐを法とする剰余演算子の出力は、次の加算入力として使用され、効果的にＧＦ［Ｍ］のリング構造全体を回転する。実際に、累積的統計偏差は、回転が定常状態値に収束するので、大幅に目立たなくなる。ガロア体ＧＦ［Ｐ］から多数のそのようなサンプルを取ることが、統計的異常をすべての同値類にまたがって均等に分布させ、出力分布を一様分布の分布に戻すことを統計的に示すことは、簡単である。追加のオプションは、収束における固定点がないことを保証するために、フィードバック経路の回転に加えて定数回転（理想的には、Ｐより小さく｛Ｍ，Ｐ｝と互いに素である値）を誘導することである。数学的語法では、「固定点」とは、数学演算子の入力と出力との両方で同一のままであり、その演算子の繰り返される適用が固定値をもたらすようにする点である。たとえば、０は、伝統的な乗算演算子の固定点である。というのは、どの数に０をかけても０になるからである。
【００２７】
少数の数値の例が、この収束がどのように働くかを知るのを助ける可能性がある。
【００２８】
例１
Ｍ＝５×７＝３５、ｐ＝３であり、ユニット遅延の初期条件値が０であるものとする。ユニット遅延の初期条件（初期出力値）を、その代わりに０、１、または２のうちのいずれにもすることができることに留意されたい。上で説明したフィードバック機構がない場合に、Ｐを法とする剰余演算の出力が、ガロア体ＧＦ［Ｐ］内の統計的アーティファクトを有する値のストリームであることに留意されたい。乱数生成の出力の分布が、真に一様である場合に、ガロア体ＧＦ［Ｐ］の最初の２つの同値類は、第３の同値類より１要素だけ大きい。これは、３５ ｍｏｄｕｌｏ ３＝（３×１１＋２） ｍｏｄｕｌｏ ３＝２ ｍｏｄｕｌｏ ３の計算から簡単にわかる。図２のフィードバック（すなわち、遅延）は、同値類の３つすべてに関するガロア体ＧＦ［Ｐ］内のこの統計的非一様性を拡散する。
【００２９】
最初の乱数生成の出力が、｛２３ ８ １９ ３１ ０ ６ １３ ２１ ２１ …｝と定義されるストリームである場合に、フィードバックなしの３を法とする剰余演算の対応する出力は、［２ ２ １ １ ０ ０ １ ０ ０ …］になる。この事例での複数の入力が、同一の出力に写像され、これが、逆写像をよりむずかしくすることに留意されたい。図２に示されたユニット遅延フィードバックを有する、３を法とする剰余演算の出力は、｛２ １ ２ ０ ０ ０ １ １ １ …｝である。この小さいスケールでの数の相違は、無視できるように見えるが、それでも、フィードバックは、ＧＦ［Ｐ］の同値類に関する混合基数変換の非一様性を拡散している。
【００３０】
より従来のシステムと共に存在できる非一様性と、図２で説明した配置を用いて得られる改善とを十分に了解するために、図２の乱数生成器２０２が、ＧＦ［Ｍ］の１００００００個のランダムに選択された出力を生成するシナリオを検討されたい。ガロア体ＧＦ［Ｐ］は、ガロア体ＧＦ［３］になるように選択される。第１の乱数列は、ガロア体ＧＦ［Ｍ］からランダムに選ばれた１００万（１００００００）個の要素からなる。従来の混合基数変換アルゴリズム（上で図１に関して説明した）が使用される場合に、写像演算は、ガロア体ＧＦ［３］にまたがる要素の非一様分布をもたらす。ＭＡＴＬＡＢ（登録商標）シミュレーションから得られたこれらの写像演算の結果を示すグラフを、図３Ａに示す。ＭＡＴＬＡＢ（登録商標）は、一般的な数値シミュレーションおよび分析ツールである。このグラフは、要素０および１が、値２と比較してより頻繁に出力に現れることを示す。混合基数数生成器処理（上で図２に関して説明した）が、１の固定回転オフセットと共に使用される場合に、統計的アーティファクトは、ガロア体ＧＦ［３］のすべての同値類にまたがってほぼ均等に拡散される。ＭＡＴＬＡＢ（登録商標）シミュレーションから得られた図２の混合基数数生成器処理の結果を示すグラフを、図３Ｂに示す。図３Ｂのグラフは、出力数列での要素０、１、および２の一様分布を示す。
【００３１】
混合基数数生成器法
ここで図４を参照すると、統計的アーティファクトをガロア体ＧＦ［Ｐ］のすべての同値類にまたがって均等に拡散する混合基数数生成器法４００の流れ図が示されている。この流れ図は、図２に示された概念の代替表現である。図４に示されているように、方法４００は、ステップ４０２で開始され、ステップ４０４に継続する。ステップ４０４では、比較的大きい第１ガロア体ＧＦ［Ｍ］を選択する。ＭおよびＰの相対サイズは、任意の値をとることができ、本願で説明される統計的特性を保持する。Ｍの値は、通常、Ｐより数桁大きくなるように選択されるが、これは、実施形態が正しく機能するための要件ではない。ステップ４０４は、第１ガロア体ＧＦ［Ｍ］より小さい第２ガロア体ＧＦ［Ｐ］を選択することをも含む。ステップ４０４は、さらに、ガロア体標数Ｐに関して互いに素になるようにガロア体標数Ｍを選択することを含む。用語「互いに素」は、本明細書で使用される時に、１を除く整数の公約数を有しない複数の整数を指す。
【００３２】
ステップ４０４の後に、方法４００はステップ４０６に継続する。ステップ４０６では、相対的に大きいガロア体ＧＦ［Ｍ］によって定義されるリング構造を利用して、第１乱数列を生成する。それでも、本発明は、これに関して限定されない。たとえば、第１乱数列を、穴をあけられたガロア体ＧＦ’［Ｍ］によって定義されるリング構造を利用して生成することもできる。本明細書で使用される時に、用語「穴をあけられた」は、所望の標数の整数倍数を超える少なくとも１つの要素がガロア体ＧＦ［Ｍ］内で破棄されていることを意味する。
【００３３】
もう一度図４を参照すると、第１乱数列は、乱数ＲＮ1，ＲＮ2，…，ＲＮNを含む。この乱数列は、擬似乱数列または擬似無秩序数列とすることができる。これに関して、乱数生成器（ＲＮＧ）を、相対的に大きいガロア体ＧＦ［Ｍ］または穴をあけられたガロア体ＧＦ’［Ｍ］上で乱数列を生成するのに使用できることを理解されたい。ＲＮＧは、当業者に周知であり、したがって、本明細書では詳細には説明しない。しかし、当技術分野で既知のどのＲＮＧでも、制限なしに使用できることを理解されたい。
【００３４】
その後、方法４００は、ステップ４０８に継続する。ステップ４０８および後続のステップ４１０（下で説明する）は、集合的に、混合基数変換の望まれない統計的アーティファクトを除去する手段を提供する。また、ステップ４０８および後続のステップ４１０（下で説明する）は、集合的に、統計的アーティファクトをガロア体ＧＦ［Ｐ］のすべての同値類にまたがって均等に拡散する手段を提供する。この統計的アーティファクトの均等な分布は、所望の統計的特性すなわちガロア体ＧＦ［Ｐ］にまたがるガロア体ＧＦ［Ｍ］からの要素の一様分布の確率的厳守を提供する。さらに、ステップ４０８および後続のステップ４１０（下で説明する）は、集合的に、ガロア体ＧＦ［Ｐ］の同値類にまたがって選択された統計的アーティファクトを誘導する手段をも提供する。
【００３５】
ステップ４０８で、算術演算を実行して、第１乱数列の各乱数ＲＮ1，ＲＮ2，…，ＲＮNを、Ｐを法とする剰余演算の結果と組み合わせる。Ｐは、ガロア体ＧＦ［Ｐ］のガロア体標数である。Ｐを法とする剰余演算は、第１乱数列の先行する乱数ＲＮ1，ＲＮ2，…，ＲＮNを利用する。算術演算は、一般に、数式（１）から（４）によって定義することができる。
ＲＮ1’＝ＲＮ1＋０ （１）
ＲＮ2’＝ＲＮ2＋ＲＮ1’ ｍｏｄｕｌｏ Ｐ （２）
ＲＮ3’＝ＲＮ3＋ＲＮ2’ ｍｏｄｕｌｏ Ｐ （３）
……
ＲＮN’＝ＲＮN＋ＲＮN-1’ ｍｏｄｕｌｏ Ｐ （４）
ここで、ＲＮ1’は、１番目の算術演算から導出された変更された１番目の乱数である。ＲＮ2’は、２番目の算術演算から導出された変更された２番目の乱数である。ＲＮ3’は、３番目の算術演算から導出された変更された３番目の乱数である。ＲＮN’は、Ｎ番目の算術演算から導出された変更されたＮ番目の乱数である。ＲＮN-1’は、最後から２番目の算術演算から導出された最後から２番目の変更された乱数である。ＲＮ1は、第１乱数列の１番目の乱数である。ＲＮ2は、第１乱数列の２番目の乱数である。ＲＮ3は、第１乱数列の３番目の乱数である。ＲＮNは、第１乱数列の最後の乱数である。Ｐは、ガロア体ＧＦ［Ｐ］の有限体サイズを定義する正の整数になるように選択された値を有する係数である。
【００３６】
ステップ４０８の代替実施形態は、第１乱数列の各乱数ＲＮ1，ＲＮ2，…，ＲＮNを、Ｐを法とする剰余演算の結果に固定オフセットを加えたものと組み合わせることである。Ｐは、ガロア体ＧＦ［Ｐ］のガロア体標数である。Ｐを法とする剰余演算は、第１乱数列の先行する乱数ＲＮ1，ＲＮ2，…，ＲＮNを利用する。この算術演算は、一般に、数式（５）から（８）によって定義することができる。
ＲＮ1’＝ＲＮ1＋Ｃ （５）
ＲＮ2’＝ＲＮ2＋ＲＮ1’＋Ｃ ｍｏｄｕｌｏ Ｐ （６）
ＲＮ3’＝ＲＮ3＋ＲＮ2’＋Ｃ ｍｏｄｕｌｏ Ｐ （７）
……
ＲＮN’＝ＲＮN＋ＲＮN-1’＋Ｃ ｍｏｄｕｌｏ Ｐ （８）
ここで、ＲＮ1’は、１番目の算術演算から導出された変更された１番目の乱数である。ＲＮ2’は、２番目の算術演算から導出された変更された２番目の乱数である。ＲＮ3’は、３番目の算術演算から導出された変更された３番目の乱数である。ＲＮN’は、Ｎ番目の算術演算から導出された変更されたＮ番目の乱数である。ＲＮN-1’は、最後から２番目の算術演算から導出された最後から２番目の変更された乱数である。ＲＮ1は、第１乱数列の１番目の乱数である。ＲＮ2は、第１乱数列の２番目の乱数である。ＲＮ3は、第１乱数列の３番目の乱数である。ＲＮNは、第１乱数列の最後の乱数である。Ｐは、ガロア体ＧＦ［Ｐ］の有限体サイズを定義する正の整数になるように選択された値を有する係数である。Ｃは、すべての固定点を除去する形で有効出力を回転するように選択される任意の定数である。
【００３７】
ステップ４０８の後に、方法４００はステップ４１０に継続する。ステップ４１０が、第２乱数列を生成するために実行されることを理解されたい。この第２乱数列は、第２ガロア体ＧＦ［Ｐ］のすべての同値類にまたがって均等に分布する統計的アーティファクトを有する。ステップ４１０は、ステップ４０８で実行された算術演算から導出された変更された乱数ＲＮ1’，ＲＮ2’，ＲＮ3’，…，ＲＮN’を利用して算術演算を実行することを含む。
【００３８】
これらの算術演算は、数式（９）から（１２）によって定義することができる。
Ｒ1＝ＲＮ1’ ｍｏｄｕｌｏ Ｐ （９）
Ｒ2＝ＲＮ2’ ｍｏｄｕｌｏ Ｐ （１０）
Ｒ3＝ＲＮ3’ ｍｏｄｕｌｏ Ｐ （１１）
……
ＲN＝ＲＮN-1’ ｍｏｄｕｌｏ Ｐ （１２）
ここで、Ｒ1は、１番目の算術演算から導出された結果である。Ｒ2は、２番目の算術演算から導出された結果である。Ｒ3は、３番目の算術演算から導出された結果である。ＲNは、最後の算術演算から導出された結果である。ＲＮ1’は、ステップ４０８で実行された１番目の算術演算から導出された変更された１番目の乱数である。ＲＮ2’は、ステップ４０８で実行された２番目の算術演算から導出された変更された２番目の乱数である。ＲＮ3’は、ステップ４０８で実行された３番目の算術演算から導出された変更された３番目の乱数である。ＲＮN’は、ステップ４０８で実行されたＮ番目の算術演算から導出された変更されたＮ番目の乱数である。Ｐは、ガロア体ＧＦ［Ｐ］の有限体サイズを定義する正の整数になるように選択された値を有する係数である。結果Ｒ1，Ｒ2，…，ＲNのそれぞれが、ガロア体ＧＦ［Ｐ］からの要素｛０，１，２，…，Ｐ−１｝であることを理解されたい。第２乱数列が、乱数の集合すなわちＲ1，Ｒ2，…，ＲNによって定義されることを理解されたい。
【００３９】
図４をもう一度参照すると、方法４００は、ステップ４１２に継続する。ステップ４１２で、方法４００が終了する。方法４００が、従来の混合基数変換の望まれない統計的アーティファクト除去する１つの方法であることを理解されたい。しかし、本発明は、これに関して限定されず、統計的アーティファクトをガロア体ＧＦ［Ｐ］のすべての同値類にまたがって均等に拡散するように構成された任意の他の混合基数数生成器法を、制限なしに使用することができる。
【００４０】
データストリームを変更する方法
ここで図５を参照すると、本発明を理解するのに有用な、データストリームを変更する従来の方法５００の流れ図が示されている。図５に示されているように、方法５００は、ステップ５０２で開始され、ステップ５０４に継続する。ステップ５０４で、乱数列を生成する。この乱数の数列が、比較的大きいガロア体ＧＦ［Ｍ］内に含まれることを理解されたい。乱数列を生成した後に、ステップ５０６が実行され、ここで、乱数列の一部を選択する。
【００４１】
ステップ５０６の後に、方法５００は、ステップ５０８に継続する。ステップ５０８では、乱数列の一部を入力データストリームと組み合わせ、これによって入力データストリームを変更する。これに関して、乱数列の一部が、入力データストリームのサイズ以上のサイズを有すること、すなわち、これらが同一の基数（または基）で表される場合である、を理解されたい。したがって、方法５００を、それ相応に変更することができる。たとえば、方法５００に、ステップ５０８の前に変換ステップを含めることができる。この変換ステップは、入力データストリームがサイズＧＦ［ｎ］またはＧＦ［ｎ／ｄ］である場合に、乱数列の一部をサイズＧＦ［Ｍ］からサイズｎに変換することを含むことができ、ここで、ｄは、ｎの偶数の約数である。その後、ステップ５１０が実行され、ここで方法５００が終了する。
【００４２】
理解されるとおり、比較的大きいガロア体ＧＦ［Ｍ］は、変換方法５００にある度合のセキュリティを提供する。これに関して、ガロア体ＧＦ［Ｍ］が、有限の個数の要素｛０，１，２，…，Ｍ−１｝だけを含む体であることを了解されたい。ガロア体ＧＦ［Ｍ］は、ガロア標数Ｍによって定義される有限体サイズを有する。したがって、出力数列が、Ｍ番目の要素おきに繰り返す可能性がある。この繰返し挙動は、相関を生じる可能性があり、これによって、Ｍが小さい場合に、変更されたデータストリームの復号が比較的簡単になる。その結果、比較的大きいガロア体ＧＦ［Ｍ］を選択することが望ましい。
【００４３】
乱数列の一部を選択することも、変換方法５００にある度合のセキュリティを提供することをも了解されたい。たとえば、ある乱数列が、ガロア体ＧＦ［Ｍ］上で生成される。この例では、この乱数列が、５００ビットを含むと仮定する。乱数列の一部が、５００ビットのうちの１６ビットだけを含むように選択される。データストリームを変更するのに、この乱数列のうちの１６ビットだけを使用することによって、この乱数列を生成するのに使用されたガロア体ＧＦ［Ｍ］を判定することが、よりむずかしくなる。それでも、この方法のセキュリティをさらに高めることが望ましい。
【００４４】
ここで図６を参照すると、通信システムのセキュリティを高める方法６００が示されている。図６に示されているように、方法６００は、ステップ６０２で開始され、ステップ６０４に継続する。ステップ６０４で、比較的大きいガロア体ＧＦ［Ｍ］を選択する。理解されるとおり、大きいガロア体は、通信システムの攻撃者が、オリジナル乱数列の生成に使用されたガロア体ＧＦ［Ｍ］を、変更されたデータストリームから判定できる可能性を最小にすることができる。実際には、大きいガロア体ＧＦ［Ｍ］は、方法６００を実施する通信システムに、ある度合のセキュリティを提供することができる。別の形で言えば、乱数列のセキュリティは、主に、出力値のダイナミックレンジ（ビット数または桁数）およびみかけのランダムさによって定義される。
【００４５】
その後、ステップ６０６が実行され、ここで、第１乱数列を、ガロア体ＧＦ［Ｍ］によって定義されるリング構造を利用して生成する。それでも、本発明は、これに関して限定されない。たとえば、第１乱数列を、穴をあけられたガロア体ＧＦ’［Ｍ］によって定義されるリング構造を利用して生成することもできる。この数列の各乱数は、ガロア体ＧＦ［Ｍ］または穴をあけられたガロア体ＧＦ’［Ｍ］の要素によって定義される。ステップ６０８で、第１乱数列の一部を選択する。このステップは、方法６００を実施する通信システムに、高い度合のセキュリティを提供する。これに関して、乱数列の一部だけが入力データストリームを変更するのに使用される場合に、ガロア体ＧＦ［Ｍ］を判定することが、よりむずかしくなることを了解されたい。
【００４６】
ステップ６１０も、第２乱数列を生成するために算術演算を実行することを含む。この第２乱数列は、第２ガロア体ＧＦ［Ｐ］のすべての同値類にまたがって均等に分布する統計的アーティファクトを有する。本発明の好ましい実施形態によれば、これらの算術演算は、上で図２に関して説明した混合基数数生成器処理とすることができる。それでも、本発明がこれに関して限定されないことを了解されたい。任意の他の適切な技法を、この目的に使用することができる。
【００４７】
もう一度図６を参照すると、方法６００は、ステップ６１２に継続する。ステップ６１２では、第２乱数列を、乗算器などのデバイスに通信する。第２乱数列を入力データストリームと組み合わせて、変更されたデータストリームを形成する。入力データストリームは、サイズＧＦ（ｎ）またはＧＦ（ｎ／ｄ）を有し、ここで、ｄは、ｎの偶数の約数である。これに関して、第２乱数列および入力データストリームが、同一のサイズを有する、すなわち、これらが、同一の基数（または基）で表され、同一の桁数を含むことを理解されたい。その後、ステップ６１６が実行され、ここで方法６００が終了する。
【００４８】
当業者は、方法６００が、通信システムのセキュリティを高める１つの方法であることを了解するであろう。しかし、本発明は、これに関して限定されず、本発明を実施する任意の他の方法を、制限なしに使用することができる。
【００４９】
ハードウェア実施態様
従来の混合基数変換アルゴリズムの望まれない統計的アーティファクトを除去する方法４００（上で図４に関して説明した）を実施するさまざまな形がある。たとえば、混合基数数生成器方法４００を、図２に示されたものに似た混合基数アキュムレータ配置を利用して実施することができる。混合基数数生成器を、データストリームを変更するために通信システムおよび／または暗号系内に配備することができる。そのようなシナリオでは、混合基数数生成器は、高められたセキュリティ特徴を通信システムおよび／または暗号系に提供することができる。そのような混合基数数生成器を、以下で図７に関して説明する。
【００５０】
ここで図７を参照すると、混合基数数生成器７００のブロック図が示されている。混合基数数生成器７００は、乱数生成器７０２、混合基数アキュムレータ７５０、および外部デバイス７１０からなる。乱数生成器７０２は、リング生成器、穴をあけられたリング生成器、またはカオス生成器（ｃｈａｏｓ ｇｅｎｅｒａｔｏｒ）とすることができるが、これらに限定はされない。乱数生成器７０２がリング生成器である場合に、乱数生成器７０２は、ガロア体ＧＦ［Ｍ］によって定義されるリング構造を利用して乱数列を生成するように構成されたハードウェアおよび／またはソフトウェアからなる。乱数生成器が穴をあけられたリング生成器である場合に、乱数生成器７０２は、穴をあけられたガロア体ＧＦ’［Ｍ］によって定義されるリング構造を利用して乱数列を生成するように構成されたハードウェアおよび／またはソフトウェアからなる。したがって、乱数生成器７０２の出力を、ガロア体ＧＦ［Ｍ］からのランダム要素または穴をあけられたガロア体ＧＦ’［Ｍ］からのランダム要素とすることができる。ガロア体ＧＦ［Ｍ］または穴をあけられたガロア体ＧＦ’［Ｍ］から所望のガロア体標数Ｐに要素を写像するために、ガロア体標数Ｍは、ガロア体標数Ｐに対して相対的に素になるように選択される。また、ガロア体標数Ｍは、ガロア体標数Ｐより大きくなるように選択される。
【００５１】
また、乱数生成器７０２は、乱数列の乱数を混合基数アキュムレータ７５０に通信するように構成されたハードウェアおよび／またはソフトウェアからなる。混合基数アキュムレータ７５０は、第２乱数を生成するために算術演算を実行するように構成される。この算術演算は、乱数生成器７０２から受け取られた乱数を利用して剰余値を計算することを含む。したがって、混合基数アキュムレータ７５０は、加算器７０４、算術演算子７０６、および遅延７０８からなる。
【００５２】
加算器７０４は、乱数生成器７０２から乱数を受け取り、遅延７０８（以下で説明する）から時間遅延された剰余を受け取るように構成されたハードウェアおよび／またはソフトウェアからなる。また、加算器７０４は、乱数生成器７０２から受け取られた乱数および遅延７０８（以下で説明する）から受け取られた時間遅延された剰余を使用して加算演算を実行するように構成されたハードウェアおよび／またはソフトウェアからなる。また、加算器７０４は、この加算演算の和を算術演算子７０６に通信するように構成されたハードウェアおよび／またはソフトウェアからなる。
【００５３】
算術演算子７０６は、算術演算を実行するように構成されたハードウェアおよび／またはソフトウェアからなる。この算術演算には、モジュロ演算を実行することを含めることができる。モジュロ演算は、当業者に周知であり、したがって、本明細書では詳細には説明しない。しかし、モジュロ演算を、一般に、数式Ｒ＝Ｓ ｍｏｄｕｌｏ Ｐによって定義できることを了解されたい。ここで、Ｒは、モジュロ演算から導出される剰余である。Ｓは、算術演算子７０６に入力される乱数である。Ｐは、ガロア体ＧＦ［Ｐ］の有限体サイズを定義する正の整数になるように選択される値を有する係数である。剰余Ｒが、ガロア体ＧＦ［Ｐ］からの要素であることを理解されたい。
【００５４】
算術演算子７０６は、さらに、剰余Ｒを外部デバイス７１０および遅延７０８に通信するように構成されたハードウェアおよび／またはソフトウェアからなる。外部デバイス７１０は、剰余を入力データまたはディジタルデータストリームと組み合わせるように構成されたコンバイナとすることができる。たとえば、外部デバイスは、本発明の一実施形態で乗算器である。遅延７０８は、算術演算子７０６から受け取られた剰余Ｒをｚ-NクロックサイクルまたはＮクロックサイクルだけ遅延させるように構成されたハードウェアおよびソフトウェアからなり、ここで、ｚ-1は、１サンプルクロック周期遅延または単位遅延であり、Ｎは、正の整数値である。ｚ-Nは、Ｎクロック周期遅延である。たとえば、遅延７０８は、剰余Ｒを１クロックサイクルだけ遅延させるように構成される。それでも、本発明はこれに関して限定されない。
【００５５】
当業者は、混合基数数生成器７００が、本発明を実施する混合基数数生成器の１つのアーキテクチャであることを了解するであろう。しかし、本発明はこれに関して限定されず、本発明を実施する任意の他の混合基数数生成器アーキテクチャを、制限なしに使用することができる。
【００５６】
図１〜７に関して説明した混合基数数生成器の方法およびシステムが、数Ｐのサイズまたは構成に関して限定されないことを理解されたい。たとえば、Ｐは、Ｐがｐ1・ｐ2・，…，・ｐkの積と等しくなるように選択することができ、ここで、ｋ個の係数のすべてが、Ｍおよび互いに関して互いに素である。この系の標数は、ｋ個の個々の出力を提供する、ある種の代替実施形態を容易にすることができ、このｋ個の個々の出力のそれぞれは、上で図１〜７に関して説明した系と比較して、類似する統計的挙動を提供することができる。そのような混合基数数生成器を、図８に示す。
【００５７】
複数の出力を有する混合基数アキュムレータ
ここで図８を参照すると、複数の出力を供給する混合基数数生成器８００の代替実施形態のブロック図が示されている。混合基数数生成器８００は、乱数生成器８０２および混合基数アキュムレータ８５０からなる。乱数生成器８０２は、リング生成器、穴をあけられたリング生成器、またはカオス生成器とすることができるが、これらに限定はされない。乱数生成器８０２がリング生成器である場合に、乱数生成器８０２は、ガロア体ＧＦ［Ｍ］によって定義されるリング構造を利用して乱数列を生成するように構成されたハードウェアおよび／またはソフトウェアからなる。乱数生成器が穴をあけられたリング生成器である場合に、乱数生成器８０２は、穴をあけられたガロア体ＧＦ’［Ｍ］によって定義されるリング構造を利用して乱数列を生成するように構成されたハードウェアおよび／またはソフトウェアからなる。したがって、乱数生成器８０２の出力を、ガロア体ＧＦ［Ｍ］からのランダム要素または穴をあけられたガロア体ＧＦ’［Ｍ］からのランダム要素とすることができる。
【００５８】
ガロア体ＧＦ［Ｍ］または穴をあけられたガロア体ＧＦ’［Ｍ］から所望のガロア体標数Ｐに要素を写像するために、ガロア体標数Ｍは、ガロア体標数Ｐに対して相対的に素になるように選択され、Ｐは、ｐ1・ｐ2・，…，・ｐkの積と等しい。また、ガロア体標数Ｍは、ガロア体標数Ｐの係数ｐ1・ｐ2・，…，・ｐkと互いに素になるように選択される。ガロア体標数Ｍは、さらに、ガロア体標数Ｐより大きくなるように選択される。
【００５９】
また、乱数生成器８０２は、乱数列の乱数を混合基数アキュムレータ８５０に通信するように構成されたハードウェアおよび／またはソフトウェアからなる。混合基数アキュムレータ８５０は、混合基数アキュムレータ７５０に類似し、類似する機能を実行する構成を有利に有する。これに関して、この混合基数アキュムレータは、第２乱数を生成するために算術演算を実行するように構成される。この算術演算は、乱数生成器８０２から受け取られた乱数を利用して剰余値を計算することを含む。したがって、混合基数アキュムレータ８５０は、加算器８０４および遅延８０８からもなる。
【００６０】
乱数生成器８０２は、複数の算術演算子８１０1、８１０2、…８１０kをも含む。算術演算子８１０1、８１０2、…８１０kのそれぞれは、算術演算を実行するように構成されたハードウェアおよび／またはソフトウェアからなる。この算術演算には、モジュロ演算を実行することを含めることができる。好ましい実施形態によれば、モジュロ演算は、数式Ｒ＝ｍｏｄｕｌｏ ｐによって定義され、Ｒは、算術演算子８０６によって実行されたモジュロ演算から導出される剰余であり、ｐは、ガロア体標数Ｐの係数ｐ1，ｐ2，…，・ｐkのうちの１つである。また、算術演算子８１０1、８１０2、…８１０kのそれぞれは、ｋ個の出力のうちの１つを作るように構成されたハードウェアおよび／またはソフトウェアからなる。算術演算子８１０1、８１０2、…８１０kのそれぞれは、ガロア体ＧＦ［ｐ1-k］の要素を出力として供給し、この出力は、外部デバイス（図示せず）に転送することができる。外部デバイスは、剰余を入力データと組み合わせるように構成された任意のデバイスとすることができる。たとえば、一実施形態で、外部デバイスは、乗算器である。より重要なことに、算術演算子８１０1、８１０2、…８１０kからのｋ個の出力のうちの１つとして供給される各数列は、望まれない統計的アーティファクトがない、一様に分布する出力を有する。
【００６１】
当業者は、混合基数数生成器８００が、本発明を実施する混合基数数生成器の１つのアーキテクチャであることを了解するであろう。しかし、本発明はこれに関して限定されず、本発明を実施する任意の他の混合基数数生成器アーキテクチャを、制限なしに使用することができる。１つのそのような実施形態によれば、遅延８０８を有限インパルス応答（ＦＩＲ）フィルタまたは無限インパルス応答（ＩＩＲ）フィルタに置換することができ、この場合に、すべての演算が、変更されたＧＦ算術を使用して実行される。
【００６２】
混合基数数生成器の複数レート実施態様
ここで図９を参照すると、本発明の第２の代替実施形態が示されている。第２の代替実施形態は、混合基数数生成器９００の複数レート実施態様である。複数レート実施態様は、乱数生成器からの出力を周期的にサンプリングすること、または所望の出力の集合と比較してより高いレートでそのような出力をサンプリングすることのいずれかを含むことができる。やはり、これは、観察者が簡単には再構築できない値の累積につながる。
【００６３】
図９に示されているように、混合基数数生成器９００は、乱数生成器９０２および混合基数アキュムレータ９５０からなる。乱数生成器９０２および混合基数アキュムレータ９５０は、上で図８に関して説明した対応する構造８０２、８５０に類似する。したがって、混合基数アキュムレータ９５０も、加算器９０８および遅延９１８からなるものとすることができる。算術演算子ユニット９１２1、９１２2、…９１２kの組を、図８の算術演算子ユニット８１０1、８１０2、…８１０kに類似する演算を実行するために設けることもできる。複数レート処理は、当業者に周知であり、したがって、本明細書では詳細には説明しない。
【００６４】
混合基数数生成器９００は、加算器９０４および遅延９０６をも含む。加算器９０４は、乱数生成器９０２から乱数を受け取り、遅延９０６（以下で説明する）から時間遅延された出力を受け取るように構成されたハードウェアおよび／またはソフトウェアからなる。また、加算器９０４は、乱数生成器９０２受け取られた乱数および遅延９０６から受け取られた時間遅延された出力を使用して加算演算を実行するように構成されたハードウェアおよび／またはソフトウェアからなる。また、加算器９０４は、加算演算の和を遅延９０６に通信するように構成されたハードウェアおよび／またはソフトウェアからなる。
【００６５】
遅延９０６は、加算器９０４から受け取られた和をＮクロックサイクルだけ遅延させるように構成されたハードウェアおよびソフトウェアからなる。それでも、本発明はこれに関して限定されない。また、遅延９０６は、時間遅延された出力（すなわち、時間遅延された和）を加算器９０４、９０８に通信するように構成されたハードウェアおよびソフトウェアからなる。
【００６６】
当業者は、混合基数数生成器９００が、本発明を実施する混合基数数生成器の１つのアーキテクチャであることを了解するであろう。しかし、本発明はこれに関して限定されず、本発明を実施する任意の他の混合基数数生成器アーキテクチャを、制限なしに使用することができる。
【００６７】
本発明の前述の説明に鑑みて、本発明をハードウェア、ソフトウェア、またはハードウェアおよびソフトウェアの組合せで実現できることを認められたい。本発明によるビットの任意の置換順序を生成する方法は、１つの処理システム内で集中化された形で、または異なる要素が複数の相互接続された処理システムにまたがって拡散される分散された形で、実現することができる。本明細書で説明した方法を実行するように適合されたすべての種類のコンピュータシステムまたは他の装置が、適する。ハードウェアおよびソフトウェアの通常の組合せは、ロードされ実行された時に本明細書で説明した方法を実行するようにコンピュータプロセッサを制御するコンピュータプログラムを伴う、汎用コンピュータプロセッサとすることができる。もちろん、特定用途向け集積回路（ＡＳＩＣ）および／またはＦＰＧＡを使用して、類似する結果を達成することもできる。
【００６８】
本発明を、本明細書で説明した方法の実施を可能にするすべての特徴を含み、コンピュータシステムにロードされた時にこれらの方法を実行することができる、コンピュータプログラム製品で実施することもできる。現在の文脈でのコンピュータプログラムまたはアプリケーションは、ａ）別の言語、コード、もしくは表記への変換、またはｂ）異なる材料形態での再作成のいずれかまたは両方の後にあるいは直接にのいずれかで特定の機能を実行する情報処理能力をシステムが有するようにすることを意図された命令の組の、任意の言語、コード、または表記でのすべての表現を意味する。さらに、上の説明は、例のみとして意図されており、添付の特許請求の範囲で示されるものを除いて、いかなる形でも本発明を限定することは意図されていない。
【図面の簡単な説明】
【００６９】
【図１】本発明を理解するのに有用な、従来の混合基数変換アルゴリズムを示す概念図である。
【図２】統計的アーティファクトをガロア体ＧＦ［Ｐ］のすべての同値類にまたがって均等に拡散する混合基数リング生成器を示す概念図である。
【図３Ａ】本発明を理解するのに有用な、従来の混合基数変換アルゴリズムの統計シミュレーションを示すグラフを示す図である。
【図３Ｂ】本発明を理解するのに有用な、混合基数数生成器法の統計シミュレーションを示すグラフを示す図である。
【図４】統計的アーティファクトをガロア体ＧＦ［Ｐ］のすべての同値類にまたがって均等に拡散する混合基数数生成器法を示す流れ図である。
【図５】本発明を理解するのに有用な、データストリームを変更する従来の方法を示す流れ図である。
【図６】本発明を理解するのに有用な、通信システムのセキュリティを高める方法を示す流れ図である。
【図７】本発明を理解するのに有用な、生成器出力をデータストリームと組み合わせる機構に接続された混合基数数生成器を示すブロック図である。
【図８】本発明を理解するのに有用な、混合基数数生成器を示すブロック図である。
【図９】本発明を理解するのに有用な、混合基数数生成器を示すブロック図である。
【符号の説明】
【００７０】
２０２、７０２、８０２、９０２ 乱数生成器
２０４、７０４、８０４、９０４、９０８ 加算器
２０５ 遅延ユニット
２０６ Ｐを法とする剰余演算子
７００、８００、９００ 混合基数数生成器
７０６、８０６、８１０、９１０、９１２ 算術演算子
７０８、８０８、９０６、９１８ 遅延
７１０ 外部デバイス
７５０、８５０、９５０ 混合基数アキュムレータ
【特許請求の範囲】
【請求項１】
ガロア体ＧＦ［Ｍ］内に含まれる第１数列を生成することと、
前記第１数列内の第１の数に先行する前記第１数列の第２の数に対して実行されるＰを法とする剰余演算の結果と前記第１の数とを合計することを含む、前記第１の数に対して第１変更を実行することであって、ＭがＰに関して相対的に素であるものを実行することと、
前記第１変更の後に、Ｐを法とする剰余演算を含む、前記第１の数に対して第２変更を実行することと、
第２数列を生成するために、前記第１数列を含む複数の数について前記第１および第２の変更を繰り返すことと
を含む、数列を生成するのに使用される処理をマスクする方法。
【請求項２】
前記第２数列を用いてディジタルデータストリームを変更することをさらに含む、請求項１に記載の方法。
【請求項３】
前記生成するステップが、さらに、前記生成するステップに関する選択された統計的アーティファクトを含む擬似乱数列を生成することを含み、前記統計的アーティファクトが、前記第１および第２の変更ステップによってＧＦ［Ｐ］上の乱数の一様に分布する数列を作成するように選択される、請求項１に記載の方法。
【請求項４】
Ｐおよびｐ1，ｐ2，ｐ3，…ｐkを含むＰの複数の素因数のすべてと互いに素であるＭの値を選択することをさらに含む、請求項１に記載の方法。
【請求項５】
前記第２数列に対して第３変更ステップを実行することをさらに含み、前記第３変更ステップが、前記第２数列から複数の出力数列を生成することを含む、請求項４に記載の方法。
【請求項６】
前記第３変更ステップが、前記複数の出力数列を生成するために前記第２数列内の各数に対して実行されるｐを法とする剰余演算を含み、ｐが、ｐ1，ｐ2，ｐ3，…ｐkを含む群から選択される複数の値を含む、請求項５に記載の方法。
【請求項７】
前記第２数列が、前記ガロア体ＧＦ［Ｐ］の複数の同値類にまたがって均等に分布する統計的アーティファクトを有し、前記複数の同値類が、整数０，１，…，Ｐ−１ごとに１つの同値類を含む、請求項１に記載の方法。
【請求項８】
ガロア体ＧＦ［Ｍ］内に含まれる第１数列を生成するように構成された数生成器と、
（１）前記第１数列内の第１の数に先行する前記第１数列の第２の数に対して実行されるＰを法とする剰余演算の結果と前記第１の数とを合計することを含む、前記第１の数に対して第１変更を実行することであって、ＭがＰに関して相対的に素であるものを実行することと、（２）前記第１変更の後に、Ｐを法とする剰余演算を含む、前記第１の数に対して第２変更を実行することと、（３）第２数列を生成するために、前記第１数列を含む複数の数について前記第１および第２の変更を繰り返すこととを行うように構成された混合基数アキュムレータと
を含む混合基数数生成器。
【請求項９】
ディジタルデータストリームを変更するのに前記第２数列を使用するように構成された手段をさらに含む、請求項８に記載のシステム。
【請求項１０】
前記数生成器が、前記第１数列の前記生成に関する統計的アーティファクトを含む擬似乱数列を生成する擬似乱数生成器を含み、前記統計的アーティファクトが、前記混合基数アキュムレータによって除去される、請求項８に記載のシステム。
【請求項１】
ガロア体ＧＦ［Ｍ］内に含まれる第１数列を生成することと、
前記第１数列内の第１の数に先行する前記第１数列の第２の数に対して実行されるＰを法とする剰余演算の結果と前記第１の数とを合計することを含む、前記第１の数に対して第１変更を実行することであって、ＭがＰに関して相対的に素であるものを実行することと、
前記第１変更の後に、Ｐを法とする剰余演算を含む、前記第１の数に対して第２変更を実行することと、
第２数列を生成するために、前記第１数列を含む複数の数について前記第１および第２の変更を繰り返すことと
を含む、数列を生成するのに使用される処理をマスクする方法。
【請求項２】
前記第２数列を用いてディジタルデータストリームを変更することをさらに含む、請求項１に記載の方法。
【請求項３】
前記生成するステップが、さらに、前記生成するステップに関する選択された統計的アーティファクトを含む擬似乱数列を生成することを含み、前記統計的アーティファクトが、前記第１および第２の変更ステップによってＧＦ［Ｐ］上の乱数の一様に分布する数列を作成するように選択される、請求項１に記載の方法。
【請求項４】
Ｐおよびｐ1，ｐ2，ｐ3，…ｐkを含むＰの複数の素因数のすべてと互いに素であるＭの値を選択することをさらに含む、請求項１に記載の方法。
【請求項５】
前記第２数列に対して第３変更ステップを実行することをさらに含み、前記第３変更ステップが、前記第２数列から複数の出力数列を生成することを含む、請求項４に記載の方法。
【請求項６】
前記第３変更ステップが、前記複数の出力数列を生成するために前記第２数列内の各数に対して実行されるｐを法とする剰余演算を含み、ｐが、ｐ1，ｐ2，ｐ3，…ｐkを含む群から選択される複数の値を含む、請求項５に記載の方法。
【請求項７】
前記第２数列が、前記ガロア体ＧＦ［Ｐ］の複数の同値類にまたがって均等に分布する統計的アーティファクトを有し、前記複数の同値類が、整数０，１，…，Ｐ−１ごとに１つの同値類を含む、請求項１に記載の方法。
【請求項８】
ガロア体ＧＦ［Ｍ］内に含まれる第１数列を生成するように構成された数生成器と、
（１）前記第１数列内の第１の数に先行する前記第１数列の第２の数に対して実行されるＰを法とする剰余演算の結果と前記第１の数とを合計することを含む、前記第１の数に対して第１変更を実行することであって、ＭがＰに関して相対的に素であるものを実行することと、（２）前記第１変更の後に、Ｐを法とする剰余演算を含む、前記第１の数に対して第２変更を実行することと、（３）第２数列を生成するために、前記第１数列を含む複数の数について前記第１および第２の変更を繰り返すこととを行うように構成された混合基数アキュムレータと
を含む混合基数数生成器。
【請求項９】
ディジタルデータストリームを変更するのに前記第２数列を使用するように構成された手段をさらに含む、請求項８に記載のシステム。
【請求項１０】
前記数生成器が、前記第１数列の前記生成に関する統計的アーティファクトを含む擬似乱数列を生成する擬似乱数生成器を含み、前記統計的アーティファクトが、前記混合基数アキュムレータによって除去される、請求項８に記載のシステム。
【図１】
【図２】
【図３Ａ】
【図３Ｂ】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図２】
【図３Ａ】
【図３Ｂ】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【公開番号】特開２００８−３０４９１４（Ｐ２００８−３０４９１４Ａ）
【公開日】平成２０年１２月１８日（２００８．１２．１８）
【国際特許分類】
【外国語出願】
【出願番号】特願２００８−１４０６７７（Ｐ２００８−１４０６７７）
【出願日】平成２０年５月２９日（２００８．５．２９）
【出願人】（５９１２６８３４６）ハリス・コーポレーション (25)
【氏名又は名称原語表記】ＨＡＲＲＩＳ ＣＯＲＰＯＲＡＴＩＯＮ
【Ｆターム（参考）】
【公開日】平成２０年１２月１８日（２００８．１２．１８）
【国際特許分類】
【出願番号】特願２００８−１４０６７７（Ｐ２００８−１４０６７７）
【出願日】平成２０年５月２９日（２００８．５．２９）
【出願人】（５９１２６８３４６）ハリス・コーポレーション (25)
【氏名又は名称原語表記】ＨＡＲＲＩＳ ＣＯＲＰＯＲＡＴＩＯＮ
【Ｆターム（参考）】
[ Back to top ]