(57)【要約】【課題】乱数列の生成に使用される処理をマスクする方法を提供すること。【解決手段】この方法は、乱数列を生成することを含む。このステップは、穴をあけられているリング構造を利用して乱数列を選択的に生成することを含む。この方法は、乱数列を第１基数から第２基数へ変換するために混合基数変換を実行することをも含む。この方法は、さらに、第２基数で表された乱数列の統計的アーティファクトを除去するために少なくとも１つの要素をリング構造から除去することによってリング構造に穴をあけることを含む。第１基数および第２基数は、これらのめいめいが第１ガロア体標数および第２ガロア体標数によって定義されるようにするために選択される。【選択図】図４
2008304916.tif 000002
【特許請求の範囲】
【請求項１】
乱数列を生成するのに使用される処理をマスクする方法であって、
乱数列を生成することと、
前記乱数列を第１基数から第２基数へ変換するために混合基数変換を実行することとを含み、
前記生成するステップが、穴をあけられているリング構造を利用して前記乱数列を選択的に生成することをさらに含む、方法。
【請求項２】
データストリームを変更するのに前記乱数列を使用することをさらに含む、請求項１に記載の方法。
【請求項３】
前記第２基数で表された前記乱数列内の統計的アーティファクトを除去するために前記リング構造から少なくとも１つの要素を除去することによって、前記リング構造に穴をあけることをさらに含む、請求項１に記載の方法。
【請求項４】
前記混合基数変換ステップで選択された統計的アーティファクトを誘導するために少なくとも１つの穴をあけられる要素を選択することをさらに含む、請求項３に記載の方法。
【請求項５】
前記第１基数および前記第２基数がそれぞれ第１ガロア体標数および第２ガロア体標数によって定義されるようにするために、前記第１基数および前記第２基数を選択することをさらに含む、請求項３に記載の方法。
【請求項６】
前記第１ガロア体標数が前記第２ガロア体標数に関して互いに素になるようにするために、前記第１ガロア体標数を選択することをさらに含む、請求項５に記載の方法。
【請求項７】
第１ガロア体の有限体サイズと比較してより小さい有限体サイズになるように前記第２ガロア体標数を選択することをさらに含む、請求項５に記載の方法。
【請求項８】
前記穴をあけるステップが、さらに、前記第２基数で表された前記乱数列の少なくとも１つの統計的アーティファクトを除去するために前記リング構造からｎ個の要素を除去することをさらに含み、ｎが、前記第１ガロア体の要素数と第２ガロア体の要素数との間の数学的関係に基づいて決定される、請求項７に記載の方法。
【請求項９】
ｎが、前記第１ガロア体の前記要素数を前記第２ガロア体の前記要素数によって割った商から生じる剰余値に基づいて決定される、請求項８に記載の方法。
【請求項１０】
前記混合基数変換が、前記第２基数の複数の同値類を作り、前記リング構造から除去される前記ｎ個の要素が、各同値類が混合基数変換を実行する前記ステップの後に等しい個数の要素を有することを保証するために選択される、請求項８に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明的配置は、リング生成器を有する通信システムに関する。より具体的には、本発明的配置は、望まれない統計的アーティファクトがない混合基数変換を実行する方法およびシステムに関する。
【背景技術】
【０００２】
多数の整数論に基づく計算システムに、リング生成器を含めることができる。リング生成器は、繰り返される写像を介して可能な出力を網羅的に作る有限体上の単純な構造である。この写像は、加法的写像および乗法的写像のある組合せであり、既約多項式はイデアルである。たとえば、リング生成器は、有限ガロア体ＧＦ［１１］での既約多項式ｆ（ｘ）＝３ｘ3＋３ｘ2＋ｘの繰り返される計算を含む。有限体またはガロア体ＧＦ［Ｐ］は、有限な個数の要素｛０，１，２，…，Ｍ−１｝だけを含む体である。有限体またはガロア体ＧＦ［Ｍ］は、ガロア標数Ｍによって定義される有限体サイズを有する。Ｍは、最もしばしば、２のべきまたは奇数の素数のいずれかになるように選択される。
【０００３】
そのようなリング生成器の利益にかかわらず、リング生成器は、ある短所をこうむる。たとえば、奇数サイズのリング生成器がガロア標数Ｍに頼ることは、ディジタル（２進）領域では計算的に非効率的である。また、有限体またはガロア体ＧＦ［Ｍ］で実行されるルックアップテーブル動作は、リソース集中型である。さらに、リング生成器の軌道は、非常に決定的である。したがって、写像および現在の有限体条件の知識は、出力数列の完全な知識を与え、多くのアプリケーションでは、この情報をマスクすることが望ましい。そのようなアプリケーションは、スペクトル拡散通信アプリケーションおよび暗号アプリケーションを含むが、これらに限定はされない。
【特許文献１】日本国特許出願公開第２００２−２９７０３３Ａ号
【特許文献２】米国特許第７０６９４９２号
【特許文献３】米国特許第７０７９６５１号
【特許文献４】日本国特許出願公開第２００３−５３３７５２Ａ号
【発明の開示】
【発明が解決しようとする課題】
【０００４】
前述に鑑みて、ディジタル（２進）領域で計算的に効率のよい算術演算を実施するリング生成器の必要が残っている。また、従来のリング生成器実施態様より少なくハードウェア集中型である実施態様を有するリング生成器の必要もある。さらに、その決定的特性を隠すことにおいてより堅牢な軌道を有するリング生成器の必要がある。
【課題を解決するための手段】
【０００５】
本発明は、乱数列を生成するのに使用される処理をマスクする方法に関する。この方法は、乱数列を生成することを含む。このステップは、穴をあけられているリング構造を利用して乱数列を選択的に生成することを含む。この方法は、乱数列を第１基数から第２基数へ変換するために混合基数変換を実行することをも含む。この方法は、データストリームを変更するのに乱数列を使用することをさらに含む。用語「乱数列」は、本明細書で使用される時に、選択された統計分布からの独立の乱数をそれぞれが模倣する数値の数列を指す。
【０００６】
本発明の態様によれば、この方法は、リング構造から少なくとも１つの要素を除去することによって、リング構造に穴をあけることを含む。この穴をあけることは、第２基数で表された乱数列内の統計的アーティファクトを除去するために実行される。この方法は、混合基数変換で選択された統計的アーティファクトを誘導するために穴をあけられる要素を選択することをも含む。この方法は、第１基数および第２基数がそれぞれ第１ガロア体標数および第２ガロア体標数によって定義されるようにするために、第１基数および第２基数を選択することをさらに含む。第１ガロア体標数が第２ガロア体標数に関して互いに素になるようにするために、第１ガロア体標数を選択することができる。第２ガロア体標数は、第１ガロア体の有限体サイズより小さい有限体サイズになるように選択される。
【０００７】
本発明のもう１つの態様によれば、穴をあけるステップは、リング構造からｎ個の要素を除去することをさらに含む。この穴をあけることは、第２基数で表された乱数列の少なくとも１つの統計的アーティファクトを除去するために実行される。ｎは、第１ガロア体の要素数と第２ガロア体の要素数との間の数学的関係に基づいて決定される。より具体的には、ｎは、第１ガロア体の要素数を第２ガロア体の要素数によって割った商から生じる剰余値に基づいて決定される。
【０００８】
本発明のもう１つの態様によれば、混合基数変換は、第２基数の複数の同値類を作る。リング構造から除去されるｎ個の要素は、各同値類が混合基数変換実行の後に等しい個数の要素を有することを保証するために選択される。
【０００９】
システムも提供される。このシステムは、生成器と混合基数変換器とを含む。生成器は、穴をあけられているリング構造を利用して乱数列を選択的に生成するように構成される。混合基数変換器は、混合基数変換を実行するように構成される。混合基数変換は、乱数列を第１基数から第２基数へ変換するために実行される。穴をあけられたリング構造および混合基数変換器は、混合基数変換に関連する統計的アーティファクトが全くない、第２基数での乱数列を作るために、組み合わせて構成される。
【００１０】
本発明の態様によれば、このシステムは、さらに、乱数列を利用してデータストリームを変更する手段からなる。本発明のもう１つの態様によれば、第１基数は、第１ガロア体標数または中国の剰余定理に似た方法を介して組み合わされた互いに素な標数のガロア体の寄せ集めによって定義される。同様に、第２基数は、第２ガロア体標数または中国の剰余定理に似た方法を介して組み合わされた互いに素な標数のガロア体の寄せ集めによって定義される。第１ガロア体標数は、第２ガロア体標数に関して互いに素である。第２ガロア体標数は、第１ガロア体の有限体サイズより小さい有限体サイズになるように選択される。
【００１１】
本発明のもう１つの態様によれば、リング構造は、第２基数で表された乱数列の少なくとも１つの統計的アーティファクトを除去するためにｎ個の要素を除去される。ｎは、第１ガロア体の要素数と第２ガロア体の要素数との間の数学的関係に基づいて決定される。より具体的には、ｎは、第１ガロア体の要素数を第２ガロア体の要素数によって割った商から生じる剰余値に基づいて決定される。
【００１２】
本発明のもう１つの態様によれば、混合基数変換は、第２基数の複数の同値類を作る。リング構造から除去されるｎ個の要素は、各同値類が混合基数変換実行の後に等しい個数の要素を有することを保証するために選択される。
【００１３】
実施形態を、図面を参照して説明するが、図面では、類似する符号が、複数の図面を通じて類似する要素を表す。
【発明を実施するための最良の形態】
【００１４】
ここで図１を参照すると、本発明を理解するのに有用な、従来の混合基数変換アルゴリズムの概念図が示されている。用語「混合基数変換」は、本明細書で使用される時に、第１基数（または基）から第２基数（または基）への数列の変換を指す。たとえば、ガロア体ＧＦ［７］基数で表された数列は、図１に示されているようにガロア体ＧＦ［３］基数で表された数列に変換される。
【００１５】
通信システムでは、さまざまなアルゴリズムが、数列をデータストリームと組み合わせるのに使用される。この組合せ処理は、通信リンクを介する伝送の前にデータストリームを暗号化するかマスクするために実行することができる。そのようなアルゴリズムには、ガロア体［ｐ］基数で数列の各数を表す剰余数系（ＲＮＳ）演算を含めることができる。ガロア体ＧＦ［ｐ］は、有限の個数の要素｛０，１，２，…，ｐ−１｝だけを含む体である。したがって、有限体またはガロア体で実行されるすべての算術演算は、その体に含まれる要素をもたらす。有限体またはガロア体ＧＦ［ｐ］は、ガロア標数ｐによって定義される有限体サイズを有する。したがって、ガロア体ＧＦ［ｐ］演算の結果の数列は、ｐ番目の要素おきに繰り返す可能性がある。これらのＲＮＳ演算は、当業者に周知であり、したがって、本明細書では詳細には説明しない。
【００１６】
特筆すべきことに、第１のガロア体ＧＦ［ｐ1k1］基数から第２のガロア体ＧＦ［ｐ2k2］基数への数列変換から生じる要素分布には、２つの基数が均等に分割可能でない時に、統計的非一様性がある。たとえば、ガロア体ＧＦ［７］基数で表された数列が、ガロア体ＧＦ［３］基数で表された数列に写像される。ガロア体ＧＦ［７］基数で表された乱数列は、要素｛０，１，２，…，６｝の集合によって定義される。同様に、ガロア体ＧＦ［３］基数で表された数列は、要素｛０，１，２｝の集合によって定義される。ガロア体ＧＦ［７］基数で表された数列のガロア体ＧＦ［３］基数で表された数列への写像は、一般に、各要素｛０，１，２，…，６｝をそれに対応する同値類の３を法（ｍｏｄｕｌｏ）とする剰余によって分割することを伴う。ガロア体ＧＦ［３］は、有限の個数の要素｛０，１，２｝だけを含む有限体なので、整数０、１、および２の対応する同値類がある。
【００１７】
ガロア体ＧＦ［７］からの要素のガロア体ＧＦ［３］の要素への写像演算を、次の表（１）にリストする。
【００１８】
【表１】
2008304916.tif 000003
表１に示されているように、写像演算は、ガロア体ＧＦ［３］での要素の非一様分布をもたらす。具体的に言うと、写像演算の結果の数列は、｛０  １  ２  ０  １  ２  ０｝と定義される。整数０に関する、同値類のガロア体ＧＦ［７］からの３つの要素｛０，３，６｝がある。整数１に関する、同値類のガロア体ＧＦ［７］からの２つの要素｛１，４｝がある。整数２に関する、同値類のガロア体ＧＦ［７］からの２つの要素｛２，５｝がある。非一様性は、異なる同値類が異なる個数の要素を含むので明らかである。
【００１９】
統計分析を利用することによって、従来の混合基数変換アルゴリズム（上で図１に関して説明した）を実施する暗号系またはスペクトル拡散システムの攻撃者は、写像演算の結果の数列によって変更されたデータストリームからオリジナル数列をより簡単に識別することができる。たとえば、２つの基数のサイズがわかれば、攻撃者は、さまざまな同値類の要素の統計的比率を使用して、変更されたデータストリームからオリジナル数列を識別することができる。したがって、混合基数変換アルゴリズムによって導出される結果から統計的アーティファクトを除去し、その結果、変更されたデータストリームからのオリジナル数列の識別がよりむずかしくなるようにすることが、望ましい。
【００２０】
したがって、本発明のいくつかの実施形態は、混合基数変換における望まれない統計的アーティファクトを除去する方法を提供する。この方法は、一般に、ガロア体ＧＦ［２k］擬似リングに穴をあけることを含む。本明細書で使用される時に、用語「穴をあけること」は、所望の標数の整数倍を超えるガロア体ＧＦ［２k］の１つまたは複数の要素を破棄することを意味する。「穴をあけること」は、所望の基数にまたがる完全に一様な分布を維持するために実行される。所望の基数は、ガロア体ＧＦ［２k］基数より小さい素数基数を含むが、これに限定はされない。ガロア体ＧＦ［２k］基数は、好ましくは、所望の基数に関して互いに素である。用語「互いに素」は、本明細書で使用される時に、１を除いて公約数を有しない複数の整数を指す。この方法は、さまざまな通信システムアプリケーションで使用することができる。たとえば、そのような方法を、暗号系で実施することができる。そのようなシナリオでは、この方法を使用して、暗号系のセキュリティ機能を高めることができる。
【００２１】
これから、本発明を、添付図面を参照して以下でより十分に説明するが、添付図面には、本発明の例示的実施形態が示されている。しかし、本発明を、多数の異なる形で実施することができ、本明細書に示された実施形態に限定されると解釈してはならない。たとえば、本発明を、方法、データ処理システム、またはコンピュータプログラム製品として実施することができる。したがって、本発明は、完全にハードウェアの実施形態、完全にソフトウェアの実施形態、またはハードウェア／ソフトウェア実施形態としての形をとることができる。
【００２２】
ここで図２を参照すると、本発明を理解するのに有用な、混合基数変換の望まれない統計的アーティファクトを除去する方法の概念図が示されている。混合基数変換は、ガロア体ＧＦ［ｐk］によって定義される擬似リングから始まり、ここで、ｐkは、ガロア体ＧＦ［ｐk］の有限体サイズを定義する数である。本発明の実施形態によれば、ｐは、２以外の値を有するように有利に選択される。それでも、本発明はこれに関して限定されない。理解されるとおり、ガロア体ＧＦ［ｐk］は、有限の個数の要素｛０，１，２，…，ｐk−１｝だけを含む体である。ガロア体ＧＦ［ｑ］にまたがる一様分布を有する写像を保証するために、ガロア体ＧＦ［ｐk］の少なくとも１つの要素が破棄される。言い換えると、ガロア体ＧＦ［ｐk］は、ガロア体ＧＦ［ｑ］擬似リングの整数個数の完全なサイクルによって定義される写像を有するために、１つまたは複数の要素で穴をあけられる。破棄される要素は、連続的である必要がなく、第２ガロア体ＧＦ［ｑ］の結果の同値類を除いて、特定の順序で選択される必要がない。さらに、統計的アーティファクトを除去するのに必要な最小限より多数の要素を、変換の属性をより完全にマスクするために除去することができる。
【００２３】
これに関して、ガロア体ＧＦ［ｑ］擬似リングのサイクルの個数を、数式（１）によって定義できることを了解されたい。
ＮＯＣ＝（ｐk−ｎ）／ｑ    （１）
ここで、ＮＯＣは、穴をあけられたガロア体ＧＦ［ｐk−ｎ］擬似リングのサイクルの個数である。ｐk−ｎは、穴をあけられたガロア体ＧＦ［ｐk−ｎ］の有限体サイズを定義する正の整数である。ｑは、ガロア体ＧＦ［ｑ］の有限体サイズを定義する正の整数である。
【００２４】
ｐk、ｎ、およびｑの値を数式（１）に代入することによって、ガロア体ＧＦ［ｑ］擬似リングのＮＯＣを計算することができる。たとえば、ｐkが２７と等しく、ｑが５と等しく、穴の個数ｎが７である場合に、ガロア体ＧＦ［５］擬似リングのＮＯＣは、４と等しい。図２に示された実施形態によれば、ガロア体ＧＦ［３3］（またはガロア体ＧＦ［２７］）には、要素｛１，５，９，１７，１８，２０，２６｝で穴をあけることができる。その代わりに、同一のガロア体ＧＦ［２７］リングに、要素｛０，１，２，３，４，５，６｝で穴をあけることができる。それでも、本発明はこれに関して限定されない。
【００２５】
混合基数変換は、ｐk−ｎ個の要素を含む穴をあけられたガロア体ＧＦ’［ｐk］に対する多項式ｆ（ｘ）ｍｏｄｕｌｏ  ｐkの繰り返される計算に継続する。これらの計算の結果は、穴をあけられたガロア体ＧＦ’［ｐk］によって定義される基数の第２の基数ｑを法とする剰余で表される数である。たとえば、穴をあけられたガロア体ＧＦ’［ｐk］が、要素９で穴をあけられたガロア体ＧＦ［１０］として選択される場合に、結果の数列は、サイズＧＦ’［１０］（またはＧＦ［９］）を有することができる。したがって、結果の数列は、要素｛０，１，２，…，８｝によって定義される。この結果の数列の要素は、ガロア体ＧＦ［ｑ］の要素に写像される。
【００２６】
次の実施例は、本発明をさらに例示するために提供される。しかし、本発明の範囲は、いかなかる形でもこれによって限定されると考えられてはならない。
【実施例１】
【００２７】
ここで図３を参照すると、リング生成器が、ガロア体ＧＦ［７］上で自明な多項式ｆ（ｘ）＝ｘの繰り返される計算を含むように選択される。ガロア体ＧＦ［７］は、有限の個数の要素｛０，１，２，…，６｝だけを含む体である。ガロア体ＧＦ［７］の要素が、ガロア体ＧＦ［３］の要素に写像される。ガロア体ＧＦ［３］によって定義される擬似リングにまたがる一様分布を保証するために、６の値を有するガロア体ＧＦ［７］の要素が破棄される。言い換えると、ガロア体ＧＦ［７］は、ガロア体ＧＦ［３］の２つ（すなわち、６／３＝２）の完全なサイクルによって定義される写像を有するために、要素６で穴をあけられる。同等の穴をあける動作を、ＧＦ［７］に要素６ではなく要素０または要素３で穴をあけることを選択することによって得ることができることに留意されたい。
【００２８】
これに関して、ガロア体ＧＦ［３］擬似リングのサイクルの個数が、下記に繰り返す、前に述べた数式（１）によって定義されることを了解されたい。
ＮＯＣ＝（ｐk−ｎ）／ｑ
ここで、ＮＯＣは、ガロア体ＧＦ［３］擬似リングのサイクルの個数である。変数の値は、ｐ＝７、ｋ＝１、ｎ＝１、およびｑ＝３である。
穴をあけられたガロア体ＧＦ’［７］の要素の、ガロア体ＧＦ［３］の要素への写像を、次の表（２）にリストする。
【００２９】
【表２】
2008304916.tif 000004
表２に示されているように、この写像演算は、ガロア体ＧＦ［３］にまたがる要素の一様分布をもたらす。具体的に言うと、この写像演算の結果の数列は、｛０  １  ２  ０  １  ２｝と定義される。整数０の同値類に、ガロア体ＧＦ［７］からの２つの要素｛０，３｝がある。整数１の同値類に、ガロア体ＧＦ［７］からの２つの要素｛１，４｝がある。整数２の同値類に、ガロア体ＧＦ［７］からの２つの要素｛２，５｝がある。
【実施例２】
【００３０】
リング生成器が、ガロア体ＧＦ［２３３］上での多項式ｆ（ｘ）の繰り返される計算を含むように選択される。ガロア体ＧＦ［２３３］は、有限の個数の要素｛０，１，２，…，２３２｝だけを含む体である。ガロア体ＧＦ［２３３］の要素が、ガロア体ＧＦ［５］の要素に写像される。ガロア体ＧＦ［５］にまたがる一様分布を保証するために、ガロア体ＧＦ［２３３］の１３個の要素が破棄される。任意に選択されて、最後の１３個の要素が、穴をあけることを介して破棄される。言い換えると、ガロア体ＧＦ［２３３］擬似リングは、ガロア体ＧＦ［５］擬似リングの４４（すなわち、２２０／５＝４４）個の完全なサイクルによって定義される写像を有するために、要素２２０から要素２３２までで穴をあけられる。
【００３１】
これに関して、ガロア体ＧＦ［５］擬似リングのサイクルの個数が、数式（２）によって定義されることを了解されたい。
ＮＯＣ＝ｐ1／ｐ2    （２）
ここで、ＮＯＣは、ガロア体ＧＦ［５］擬似リングのサイクルの個数である。ｐ1は、第１のガロア体ＧＦ［２３３］の有限体サイズを定義する正の整数である。ｐ2は、第２のガロア体ＧＦ［５］の有限体サイズを定義する正の整数である。
【００３２】
ｐk、ｎ、およびｑの値を数式（１）に代入することによって、ガロア体ＧＦ［５］擬似リングのＮＯＣを、次のように計算することができる：ＮＯＣ＝（２３３1−１３）／５＝４４。したがって、ガロア体ＧＦ［５］擬似リングを介する４４個の完全なサイクルがある。
【００３３】
ガロア体ＧＦ［５］の要素への穴をあけられたガロア体ＧＦ’［２３３］の要素の写像を、次の表（３）にリストする。
【００３４】
【表３】
2008304916.tif 000005
表３に示されているように、この写像演算は、ガロア体ＧＦ［５］にまたがる要素の一様分布をもたらす。具体的に言うと、この写像演算の結果の数列は、｛０  １  ２  ３  ４  …０  １  ２  ３  ４｝と定義される。整数０、１、２、３、および４の同値類のそれぞれに、ガロア体ＧＦ［５］からの同一個数の要素がある。
【００３５】
ここで図４を参照すると、乱数列の生成に使用される処理をマスクする方法４００の流れ図が示されている。図４に示されているように、方法４００は、ステップ４０２で開始され、ステップ４０４に継続する。ステップ４０４では、第１基数および第２基数を選択する。第１基数は、第１有限体のサイズを定義する。第１有限体は、第１ガロア体ＧＦ［ｐk］または第１ガロア体ＧＦ［Ｍ］によって定義することができる。第２基数は、第２有限体のサイズを定義する。第２有限体は、第２ガロア体ＧＦ［ｑ］によって定義することができる。第１ガロア体は、第２ガロア体に関して互いに素になるように選択することができる。第２ガロア体は、第１ガロア体の有限体サイズより小さい有限体サイズを有するように選択することができる。
【００３６】
ステップ４０４の後に、方法４００は、ステップ４０６に継続する。ステップ４０６では、リング構造から少なくとも１つの要素を除去することによって、リング構造に穴をあける。このリング構造は、第１有限体または第１ガロア体によって定義される。この穴をあけることは、第２基数で表される乱数列の統計的アーティファクトを除去するために実行される。統計的アーティファクトには、混合基数変換（以下でステップ４１０に関して説明する）の統計的アーティファクトを含めることができる。このステップには、さらに、リング構造からｎ個の要素を除去することを含めることができる。ｎは、第１有限体またはガロア体の要素数と第２有限体またはガロア体の要素数との間の数学的関係に基づいて決定される。より具体的に言うと、ｎは、第１有限体またはガロア体ＧＦの要素数を第２有限体またはガロア体の要素数によって割った商から生じる剰余値に基づいて決定される。
【００３７】
その後、ステップ４０８が実行され、ここで、乱数列を生成する。このステップには、穴をあけられているリング構造を利用して乱数列を選択的に生成することを含めることができる。このステップで生成される乱数列が、第１基数で表されることを了解されたい。ステップ４１０で、乱数列を第１基数から第２基数に変換するために、混合基数変換を実行する。混合基数変換が、第２基数の複数の同等のクラスを作ることを理解されたい。リング構造から除去されるｎ個の要素は、各同値類がこのステップの実行後に等しい個数の要素を有することを保証するように選択される。その後、ステップ４１２が実行され、ここで、方法４００が終了する。
【００３８】
当業者は、方法４００が、乱数列の生成に使用される処理をマスクする１つの方法であることを了解するであろう。しかし、本発明は、これに関して限定されず、乱数列の生成に使用される処理をマスクする任意の他の方法を、制限なしに使用することができる。
【００３９】
データストリームを変更する方法
ここで図５を参照すると、本発明を理解するのに有用な、データストリームを変更する従来の方法５００の流れ図が示されている。図５に示されているように、方法５００は、ステップ５０２で開始され、ステップ５０４に継続する。ステップ５０４で、乱数列を生成する。この乱数の数列が、比較的大きいガロア体ＧＦ［Ｍ］内に含まれることを理解されたい。乱数列を生成した後に、ステップ５０６が実行され、ここで、乱数列の一部を選択する。
【００４０】
ステップ５０６の後に、方法５００は、ステップ５０８に継続する。ステップ５０８で、乱数列の一部を、組合せ方法を使用するデバイスに通信する。そのようなデバイスは、乗算器、加算器、ディジタル論理デバイス、フィードバック機構、または類似する組合せ機能デバイスを含む。その後、乱数列の一部を、データストリームに組み込むかデータストリームと組み合わせ、これによって、データストリームを変更する。これに関して、乱数列の一部およびデータストリームが、同一のサイズを有する、すなわち、これらが、同一の基数（または基）で表され、同一の桁数を含むことを理解されたい。したがって、方法５００を、それ相応に変更することができる。たとえば、方法５００に、ステップ５０８の前に変換ステップを含めることができる。この変換ステップは、データストリームがサイズＧＦ［ｎ］またはＧＦ［ｎ／ｄ］である場合に、乱数列の一部をサイズＧＦ［Ｍ］からサイズｎに変換することを含むことができ、ここで、ｄは、ｎの偶数の約数である。その後、ステップ５１２が実行され、ここで方法５００が終了する。
【００４１】
理解されるとおり、比較的大きいガロア体ＧＦ［Ｍ］は、変換方法５００にある度合のセキュリティを提供する。これに関して、ガロア体ＧＦ［Ｍ］が、有限の個数の要素｛０，１，２，…，Ｍ−１｝だけを含む体であることを了解されたい。したがって、出力数列が、Ｍ番目の要素おきに繰り返す可能性がある。この繰返し挙動は、相関を生じる可能性があり、これによって、Ｍが小さい場合に、変更されたデータストリームの復号が比較的簡単になる。その結果、比較的大きいガロア体ＧＦ［Ｍ］を選択することが望ましい。
【００４２】
乱数列の切頭部を選択することも、変換方法５００にある度合のセキュリティを提供することをも了解されたい。たとえば、ある乱数列が、ガロア体ＧＦ［Ｍ］上で生成される。この乱数列が、５００個の独立ｐ進数字を含む。乱数列の一部が、５００個の数字のうちの１６個だけを含むように選択される。データストリームを変更するのに、この乱数列のうちの１６個の数字だけを使用することによって、この乱数列を生成するのに使用された決定性規則を判定することが、よりむずかしくなる。それでも、この方法のセキュリティをさらに高めることが望ましい。
【００４３】
ここで図６を参照すると、本発明を理解するのに有用な、通信システムのセキュリティを高める方法６００が示されている。図６に示されているように、方法６００は、ステップ６０２で開始され、ステップ６０４に継続する。ステップ６０４で、比較的大きいガロア体ＧＦ［Ｍ］を選択する。理解されるとおり、大きいガロア体は、通信システムの攻撃者が、オリジナル乱数列の生成に使用されたガロア体ＧＦ［Ｍ］を、変更されたデータストリームから判定できる可能性を最小にすることができる。実際には、大きいガロア体ＧＦ［Ｍ］は、方法６００を実施する通信システムに、ある度合のセキュリティを提供することができる。
【００４４】
その後、ステップ６０６が実行され、ここで、ある種の要素が、ガロア体ＧＦ［Ｍ］から除去される。これらの要素は、ガロア体ＧＦ［Ｍ］を変更されたデータストリームから識別するのに有用な統計的アーティファクトを提供できる要素として選択される。たとえば、これらの要素は、これらの要素の混合基数変換がガロア体ＧＦ［ｑ］擬似リングの完全なサイクルの集合によって定義されるようにするために選択される。その結果、このステップは、後続の混合基数変換に、望まれない統計的アーティファクトがなくなることを保証する。実際に、このステップは、出力数列を定義する決定的ルールを、アドバタイズされない相互に素な基数に依存するようにすることによって、方法６００を実施する通信システムに、高められた度合のセキュリティを提供する。
【００４５】
その後、方法６００は、ステップ６０８に継続する。ステップ６０８では、乱数列を、穴をあけられたガロア体ＧＦ’［Ｍ］上で生成する。数列の各乱数は、穴をあけられたガロア体ＧＦ’［Ｍ］の要素によって定義される。
【００４６】
ステップ６１０で、ガロア体ＧＦ［Ｍ］からガロア体ＧＦ［ｑ］への混合基数変換を実行する。このステップは、乱数列の一部を選択することを含む。このステップは、穴をあけられたガロア体ＧＦ’［Ｍ］からの乱数列の選択された部分を、ガロア体ＧＦ［ｑ］によって表される結果の出力基数に変換することをも含む。このステップは、方法６００を実施する通信システムに、さらに高い度合のセキュリティを提供する。これに関して、データストリームを変更する前に混合基数変換が使用される場合に、ガロア体ＧＦ［Ｍ］および基礎になる乱数列を判定することが、よりむずかしくなることを了解されたい。
【００４７】
ステップ６１０の後に、ステップ６１２が実行され、ここで、ガロア体ＧＦ［ｑ］に写像された、ステップ６１０からの結果の値を、データストリームをマスクする組合せ方法を使用するデバイスに通信する。この組合せ方法は、標準的な乗算、ガロア拡大体での乗算、ｑを法とする剰余系での加算、ｑを法とする剰余系での減算、ビット単位の論理演算、または任意の他の標準的な組合せ方法とすることができる。これに関して、正しい組合せ技法が使用される場合に、ガロア体ＧＦ［ｑ］出力および入力データストリームが同一サイズを有する必要がないことを理解されたい。ステップ６１４で、ステップ６１０からの結果の値をデータストリームと組み合わせて、変更されたデータストリームを形成する。その後、ステップ６１６が実行され、ここで方法６００が終了する。
【００４８】
当業者は、方法６００が、通信システムのセキュリティを高める１つの方法であることを了解するであろう。しかし、本発明は、これに関して限定されず、本発明を実施する任意の他の方法を、制限なしに使用することができる。
【００４９】
ハードウェア実施態様
ここで図７を参照すると、本発明を理解するのに有用なシステム７００が示されている。図７からわかるように、システム７００は、穴をあけられたリング生成器７０２および混合基数変換器７０４からなる。穴をあけられたリング生成器７０２および混合基数変換器７０４が、混合基数変換に関連する統計的アーティファクトが全くない第２基数の乱数列を作るために組み合わせて構成されることを理解されたい。
【００５０】
図７に示されているように、穴をあけられたリング生成器７０２は、第１基数で表された乱数列を生成するように構成されたハードウェアおよびソフトウェアからなる。また、穴をあけられたリング生成器７０２は、穴をあけられているリング構造を利用して乱数列を選択的に生成するように構成されたハードウェアおよびソフトウェアからなる。このリング構造は、穴をあけられたガロア体ＧＦ’［Ｍ］擬似リングとすることができる。乱数のそれぞれは、それぞれ、穴をあけられたガロア体ＧＦ’［Ｍ］によって定義するか、これからの要素とすることができる。リング構造は、第２基数で表される乱数の統計的アーティファクトを除去するために、少なくとも１つの要素をそこから除去される。穴をあけられたリング生成器７０２は、さらに、乱数を混合基数変換器７０４に通信するように構成されたハードウェアおよびソフトウェアからなる。
【００５１】
混合基数変換器７０４は、混合基数変換を実行するように構成されたハードウェアおよびソフトウェアからなる。混合基数変換は、乱数Ｊを第１基数から第２基数に変換するために算術演算を実行することを含む。本発明の態様によれば、第１基数は、第１ガロア体ＧＦ［Ｍ］によって定義される。同様に、第２基数は、第２ガロア体ＧＦ［ｑ］によって定義される。第１ガロア体ＧＦ［Ｍ］は、第２ガロア体ＧＦ［ｑ］に関して互いに素とすることができる。第２ガロア体ＧＦ［ｑ］は、第１ガロア体ＧＦ［Ｍ］の有限体サイズより小さい有限体サイズを有する。
【００５２】
算術演算は、モジュロ演算を実行することを含むことができる。モジュロ演算は、当業者に周知であり、したがって、本明細書では詳細には説明しない。しかし、モジュロ演算を、一般に、数式（２）によって定義できることを了解されたい。
Ｒ＝Ｊ  ｍｏｄｕｌｏ  （ｑ）    （２）
ここで、Ｒは、モジュロ演算から導出される剰余である。Ｊは、混合基数変換器７０４に入力される乱数である。ｑは、ガロア体ＧＦ［ｑ］の有限体サイズを定義する正の整数になるように選択される値を有する係数である。Ｊの値の範囲が、｛０，１，２，…，Ｍ｝であり、Ｒの値の範囲が、｛０，１，２，…，ｑ−１｝であることに留意されたい。
【００５３】
写像演算は、ルックアップテーブル演算を用いることもできる。そのようなシナリオでは、混合基数変換器７０４は、乱数Ｊ  ｍｏｄｕｌｏ  ｑを写像するのに必要な情報についてデータストア（図示せず）に照会することができる。また、混合基数変換器７０４は、ガロア体ＧＦ［ｑ］基数で表された乱数Ｊを外部デバイス（図示せず）に通信するように構成されたハードウェアおよびソフトウェアからなる。
【００５４】
本発明の態様によれば、リング構造は、ｎ個の要素をそれから除去される。リング構造からｎ個の要素を除去することによって、少なくとも１つの統計的アーティファクトが、第２基数で表された乱数列内で除去される。ｎが、第１ガロア体の要素数と第２ガロア体の要素数との間の数学的関係に基づいて決定されることを理解されたい。より具体的に言うと、ｎは、第１ガロア体の要素数を第２ガロア体の要素数によって割った商の剰余値に基づいて決定される。
【００５５】
本発明のもう１つの態様によれば、混合基数変換は、第２基数の複数の同値類を作る。リング構造から除去されるｎ個の要素は、各同値類が混合基数変換の後に等しい個数の要素を有することを保証するように選択される。
【００５６】
当業者は、システム７００が、本発明を実施するシステムの１つのアーキテクチャであることを了解するであろう。しかし、本発明はこれに関して限定されず、本発明を実施する任意の他のシステムアーキテクチャを、制限なしに使用することができる。たとえば、このシステムは、さらに、乱数列を利用してディジタルデータストリームを変更する手段からなるものとすることができる。
【００５７】
本発明の前述の説明に鑑みて、本発明をハードウェア、ソフトウェア、またはハードウェアおよびソフトウェアの組合せで実現できることを認められたい。本発明によるビットの任意の置換順序を生成する方法は、１つの処理システム内で集中化された形で、または異なる要素が複数の相互接続された処理システムにまたがって拡散される分散された形で、実現することができる。本明細書で説明した方法を実行するように適合されたすべての種類のコンピュータシステムまたは他の装置が、適する。ハードウェアおよびソフトウェアの通常の組合せは、ロードされ実行された時に本明細書で説明した方法を実行するようにコンピュータプロセッサを制御するコンピュータプログラムを伴う、汎用コンピュータプロセッサとすることができる。もちろん、特定用途向け集積回路（ＡＳＩＣ）および／またはＦＰＧＡを使用して、類似する結果を達成することもできる。
【００５８】
本発明を、本明細書で説明した方法の実施を可能にするすべての特徴を含み、コンピュータシステムにロードされた時にこれらの方法を実行することができる、コンピュータプログラム製品で実施することもできる。現在の文脈でのコンピュータプログラムまたはアプリケーションは、ａ）別の言語、コード、もしくは表記への変換、またはｂ）異なる材料形態での再作成のいずれかまたは両方の後にあるいは直接にのいずれかで特定の機能を実行する情報処理能力をシステムが有するようにすることを意図された命令の組の、任意の言語、コード、または表記でのすべての表現を意味する。さらに、上の説明は、例のみとして意図されており、添付の特許請求の範囲で示されるものを除いて、いかなる形でも本発明を限定することは意図されていない。
【図面の簡単な説明】
【００５９】
【図１】本発明を理解するのに有用な、従来の混合基数変換アルゴリズムを示す概念図である。
【図２】本発明を理解するのに有用な、混合基数変換アルゴリズムの望まれない統計的アーティファクトを除去する方法を示す概念図である。
【図３】本発明を理解するのに有用な、ガロア体ＧＦ［７］からガロア体ＧＦ［３］への要素の混合基数変換を示す概略図である。
【図４】本発明を理解するのに有用な、乱数列の生成に使用される処理をマスクする方法を示す流れ図である。
【図５】本発明を理解するのに有用な、データストリームを変更する従来の方法を示す流れ図である。
【図６】本発明を理解するのに有用な、通信システムのセキュリティを高める方法を示す流れ図である。
【図７】本発明を理解するのに有用な、穴をあけられたリング生成器を有するシステムを示すブロック図である。
【符号の説明】
【００６０】
７００  システム
７０２  穴をあけられたリング生成器
７０４  混合基数変換器
【図１】
2008304916.tif 000006
【図２】
2008304916.tif 000007
【図３】
2008304916.tif 000008
【図４】
2008304916.tif 000009
【図５】
2008304916.tif 000010
【図６】
2008304916.tif 000011
【図７】
2008304916.tif 000012
【外国語明細書】
2008304916000001.pdf