(57)【要約】【課題】リソース効率のよい形で入力数列の繰返し周期を延ばすために通信システム内で複数の入力数列を組み合わせる方法を提供すること。【解決手段】この方法は、受け取るステップ、写像するステップ、および生成するステップを含む。受け取るステップは、それぞれがガロア体ＧＦ［ｐｋ］で表される第１数列および第２数列を受け取ることを含む。写像するステップは、第１数列および第２数列をガロア拡大体ＧＦ［ｐｋ＋１］に写像することを含む。生成するステップは、ガロア拡大体ＧＦ［ｐｋ＋１］でのガロア体乗算演算を利用して第１数列を第２数列と組み合わせることによって出力数列を生成することを含む。ｐは、素数である。ｋは、整数である。ｐｋ＋１は、ガロア拡大体ＧＦ［ｐｋ＋１］の有限体サイズを定義する。【選択図】図１
2008299330.tif 000002
【特許請求の範囲】
【請求項１】
リソース効率のよい形で少なくとも２つの入力数列の繰返し周期を延ばすために通信システム内で前記少なくとも２つの入力数列を組み合わせる方法であって、
それぞれがガロア体ＧＦ［ｐｋ］で表される第１数列および第２数列を受け取ることと、
前記第１数列および前記第２数列をガロア拡大体ＧＦ［ｐｋ＋１］に写像することと、
前記ガロア拡大体ＧＦ［ｐｋ＋１］でのガロア体乗算演算を利用して前記第１数列を前記第２数列と組み合わせることによって出力数列を生成することであって、ｐは、素数であり、ｋは、整数値であり、ｐｋ＋１は、前記ガロア拡大体ＧＦ［ｐｋ＋１］の有限体サイズを定義する、生成することと
を含む方法。
【請求項２】
前記ガロア体ＧＦ［ｐｋ］の有限体サイズを定義する素数になるようにｐｋを選択することをさらに含む、請求項１に記載の方法。
【請求項３】
前記受け取るステップの前に、前記第１数列および前記第２数列をｐ進記数法表現で表すことをさらに含む、請求項１に記載の方法。
【請求項４】
前記受け取るステップの前に、前記第１数列および前記第２数列を混合基数記数法表現で表すことをさらに含む、請求項１に記載の方法。
【請求項５】
加重記数法で表された少なくとも２つのデジットからなるように前記第１数列および前記第２数列のそれぞれを選択することをさらに含む、請求項１に記載の方法。
【請求項６】
前記生成するステップが、前記第１数列および前記第２数列のそれぞれからのデジットの別個の部分集合を使用する複数のガロア体乗算演算を選択的に実行することによって、前記第１数列および前記第２数列を組み合わせることをさらに含む、請求項１に記載の方法。
【請求項７】
ペイロードデータまたは乱数列になるように前記第１数列を選択することをさらに含む、請求項１に記載の方法。
【請求項８】
擬似乱数列または擬似無秩序乱数列になるように前記第２数列を選択することをさらに含む、請求項１に記載の方法。
【請求項９】
前記写像するステップが、前記第１数列および前記第２数列のアフィン変換を実行することをさらに含む、請求項１に記載の方法。
【請求項１０】
それぞれがガロア体ＧＦ［ｐｋ］で表される第１数列および第２数列を受け取るように構成された受け取り手段と、
前記第１数列および前記第２数列をガロア拡大体ＧＦ［ｐｋ＋１］に写像するように構成された写像手段と、
前記ガロア拡大体ＧＦ［ｐｋ＋１］でのガロア体乗算演算を利用して前記第１数列を前記第２数列と組み合わせることによって出力数列を生成するように構成された生成手段であって、ｐは、素数であり、ｋは、整数値であり、ｐｋ＋１は、前記ガロア拡大体ＧＦ［ｐｋ＋１］の有限体サイズを定義する、生成手段と
を含む、閉ガロア体暗号（ＣＧＦＣ）システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明配置は、信号処理、誤り訂正符号、擬似乱数生成、および暗号化システムでのガロア体乗算の効率的な実施態様に関する。より具体的には、本発明配置は、複数の入力数列を組み合わせるための効率的で可逆の閉ガロア体組合せ（ｃｌｏｓｅｄ  Ｇａｌｏｉｓ  ｆｉｅｌｄ  ｃｏｍｂｉｎａｔｉｏｎ：ＣＧＦＣ）処理に関する。
【背景技術】
【０００２】
数列生成器（ｓｅｑｕｅｎｃｅ  ｇｅｎｅｒａｔｏｒ）は、信号処理、誤り訂正符号、擬似乱数生成、および暗号化システムの範囲にわたるアプリケーションで使用される。これらのアプリケーションのそれぞれの基礎になる機構は、性質において有限な数列であり、数列の繰返し周期が短ければ短いほど、部外者がその数列の将来の値を判定し、または予測することが簡単になる。数列の繰返し周期を延ばすために、多くのアプリケーションは、生成多項式の長さを増やし、複数の直交する数列を用いるあるタイプの非線形組合せ技法を使用し、あるいは他の形で数列の長さを増やす。
【０００３】
これらの技法は、大幅に高まる実施態様の複雑さをもたらし、この複雑さは、リソース消費および処理時間の増加になる。また、数列周期ごとに、生成アルゴリズムは、通常、固定され、ガロア体上の特定の既約多項式に束縛される。また、入力数列のうちの１つまたは複数の先験的知識が、格納または伝送中に発生し得る数列の誤りを検出し、訂正する効率的な方法をもたらすようになる、組合せ技法を実施することが望ましい。
【０００４】
数列の変更の静的な例が、通信システムに存在する。そのような例の１つが、リードソロモン誤り訂正符号（Reed Solomon error correction code）およびその派生物である。リードソロモン誤り訂正符号は、原始元および固定された既約多項式を使用するガロア拡大体乗算に基づいて出力値を計算する。
【特許文献１】日本国特許出願公開第２００２−２９７０３３Ａ号
【特許文献２】米国特許第７０６９４９２号
【特許文献３】米国特許第７０７９６５１号
【非特許文献１】ｈｔｔｐ：／／ｍａｔｈｗｏｒｌｄ．ｗｏｌｆｒａｍ．ｃｏｍ／Ｂｉｊｅｃｔｉｖｅ．ｈｔｍｌ
【非特許文献２】ｈｔｔｐ：／／ｍａｔｈｗｏｒｌｄ．ｗｏｌｆｒａｍ．ｃｏｍ／Ｉｎｊｅｃｔｉｏｎ．ｈｔｍｌ
【非特許文献３】ｈｔｔｐ：／／ｍａｔｈｗｏｒｌｄ．ｗｏｌｆｒａｍ．ｃｏｍ／Ｓｕｒｊｅｃｔｉｏｎ．ｈｔｍｌ
【発明の開示】
【発明が解決しようとする課題】
【０００５】
前述に鑑みて、計算的に従来の方法より効率的である、データストリームを乱数列と組み合わせる方法が必要である。また、乱数列の繰返し周期を効率的に延ばす方法が必要である。さらに、従来の方法より誤りを被りにくい、データストリームを乱数列と組み合わせる方法が必要である。
【課題を解決するための手段】
【０００６】
本発明は、リソース効率のよい形で入力数列の繰返し周期を延ばすために通信システム内で複数の入力数列を組み合わせる方法に関する。この方法は、受け取るステップ、写像するステップ、および生成するステップを含む。受け取るステップは、第１数列および第２数列を受け取ることを含む。第１数列および第２数列は、ガロア体ＧＦ［ｐｋ］で表される。写像するステップは、第１数列および第２数列をガロア拡大体ＧＦ［ｐｋ＋１］に写像することを含む。生成するステップは、ガロア拡大体ＧＦ［ｐｋ＋１］でのガロア体乗算演算を利用して第１数列を第２数列と組み合わせることによって出力数列を生成することを含む。ｐは、素数である。ｋは、整数である。ｐｋ＋１は、ガロア拡大体ＧＦ［ｐｋ＋１］の有限体サイズを定義する。生成するステップが、第１数列および第２数列の可逆再構築を保証するために実行されることに留意されたい。
【０００７】
本発明の一態様によれば、この方法は、ガロア体ＧＦ［ｐｋ］の有限体サイズを定義する素数になるようにｐｋを選択することを含む。この方法は、受け取るステップの前に、第１数列および第２数列を、ｐ進記数法表現または混合基数記数法表現で表すことをも含む。
【０００８】
本発明のもう１つの態様によれば、第１数列および第２数列のそれぞれは、加重記数法（ｗｅｉｇｈｔｅｄ  ｎｕｍｂｅｒ  ｓｙｓｔｅｍ）で表された複数のデジットからなる。この方法は、第１数列および第２数列のそれぞれからのデジットの別個の部分集合を使用するガロア体乗算演算を選択的に実行することによって、第１数列および第２数列を組み合わせることを含む。
【０００９】
本発明のもう１つの態様によれば、この方法は、ペイロードデータまたは乱数列になるように第１数列を選択することを含む。この方法は、擬似乱数列または擬似無秩序（ｐｓｅｕｄｏ−ｃｈａｏｔｉｃ）乱数列になるように第２数列を選択することをも含む。この方法は、既知の数学的関係を有する乱数列になるように１つまたは複数の入力数列を選択することと、これを第１数列と組み合わせることとを含む。
【００１０】
本発明のもう１つの態様によれば、写像するステップは、第１数列および第２数列のアフィン変換を実行することを含む。この方法は、時間の関数になるようにアフィン変換を選択することをも含む。
【００１１】
閉ガロア体暗号（ＣＧＦＣ）システムも提供される。このＣＧＦＣシステムは、受け取り手段、写像手段、および生成手段を含む。受け取り手段は、第１数列および第２数列を受け取るように構成される。第１数列および第２数列は、ガロア体ＧＦ［ｐｋ］で表される。写像手段は、第１数列および第２数列をガロア拡大体ＧＦ［ｐｋ＋１］に写像するように構成される。生成手段は、ガロア拡大体ＧＦ［ｐｋ＋１］でのガロア体乗算演算を利用して第１数列を第２数列と組み合わせることによって出力数列を生成するように構成される。ｐは、素数である。ｋは、整数である。ｐｋ＋１は、ガロア拡大体ＧＦ［ｐｋ＋１］の有限体サイズを定義する。
【００１２】
本発明の一態様によれば、ｐｋは、ガロア体ＧＦ［ｐｋ］の有限体サイズを定義する素数である。第１数列および第２数列は、ｐ進記数法表現または混合基数記数法表現で表される。
【００１３】
本発明のもう１つの態様によれば、第１数列および第２数列のそれぞれは、加重記数法で表された複数のデジットからなる。生成手段は、第１数列および第２数列のそれぞれからのデジットの別個の部分集合を使用するガロア体乗算演算を選択的に実行することによって、第１数列および第２数列を組み合わせるようにさらに構成される。
【００１４】
本発明のもう１つの態様によれば、第１数列は、ペイロードデータまたは乱数列である。第２数列は、擬似乱数列または擬似無秩序乱数列である。生成手段は、複数の入力数列を第１数列と組み合わせるようにさらに構成される。入力数列は、既知の数学的関係を有する乱数列である。
【００１５】
本発明のもう１つの態様によれば、写像手段は、第１数列および第２数列のアフィン変換を実行するようにさらに構成される。アフィン変換は、時間の関数とすることができる。
【００１６】
実施形態を、図面を参照して説明するが、図面では、類似する符号が、複数の図面を通じて類似する要素を表す。
【発明を実施するための最良の形態】
【００１７】
本発明を、以降において、添付図面を参照してより十分に説明するが、添付図面には、本発明の例示的実施形態が示されている。しかし、本発明は、多数の異なる形で実施することができ、本明細書で示される実施形態に限定されると解釈してはならない。たとえば、本発明を、方法、データ処理システム、またはコンピュータプログラム製品として実施することができる。したがって、本発明は、完全にハードウェアの実施形態、完全にソフトウェアの実施形態、またはハードウェア／ソフトウェア実施形態としての形態をとることができる。
【００１８】
多くの通信システムアプリケーションでは、複数の数列を組み合わせる効率的手段を有することが望ましい。そのような通信システムアプリケーションは、乱数生成アプリケーション、誤り符号化アプリケーション、暗号化アプリケーション、変調アプリケーション、および類似物を含む。誤り符号化アプリケーションおよび暗号化アプリケーションでは、組合せ処理は、生成する特性の判定を拒むために、作られる数ストリームを使用するある可逆演算によって入力データストリームをマスクするために実行される。用語「可逆」は、本明細書で使用される時に、マスキング動作を元に戻す方法の存在を指す。２つの独立な線形に生成された数ストリームを組み合わせる効率的な手段を有することも望ましい。この組合せ処理は、非線形数ストリームを作ることができる。非線形に生成された数ストリームは、生成する構造を識別することを非常にむずかしくする。したがって、本発明のいくつかの実施形態は、ガロア拡大体での乗算を介して２つのデータ入力を効率的に組み合わせる方法および装置を提供する。そのような実施形態は、時間とハードウェア設計との両方での効率を満足する。そのような実施形態は、さらに、単純でほぼ対称の逆演算子を提供する。
【００１９】
本発明の他の実施形態は、意図されない復号をむずかしくすると同時に、ディジタルハードウェアでデータを効率的にマスクする方法を提供する。これに関して、そのような方法を、さまざまな通信システムアプリケーションで使用できることを了解されたい。そのような方法を、他の非線形処理技法と組み合わせて、選択された統計的特性を誘導することができる。
【００２０】
ここで図１を参照すると、２つのデータ入力を組み合わせる閉ガロア体組合せ（ＣＧＦＣ）法１００の流れ図が示されている。ＣＧＦＣ法１００を説明する前に、読者が本発明を理解するのを助けるために、ガロア体の短い議論を提供する。次の議論が、ガロア体の基礎的特性の全般的議論であることを理解されたい。説明を単純にするために、ガロア体の完全な定義または正確な定義は、提供しない。
【００２１】
理解されるとおり、ガロア体ＧＦ［ｐｋ］は、要素の離散集合｛０，１，２，…，ｐｋ−１｝上で作成される巡回有限構造である。たとえば、ガロア体ＧＦ［２３］は、要素｛０，１，２，３，４，５，６，７｝を含む巡回有限構造である。ガロア体ＧＦ［ｐｋ］は、ガロア体ＧＦ［ｐｋ］内で算術演算を実行することを可能にする、ある解析的特性を有する。そのような算術演算は、加算演算、減算演算、および乗算演算を含む。ガロア体ＧＦ［ｐｋ］は、前記算術演算の結果が同一のガロア体内の別の要素と等しいので、しばしば、閉構造と呼ばれる。これらの算術演算を、モジュラ演算と考えることができる。たとえば、ガロア体ＧＦ［ｐｋ］が、ガロア体ＧＦ［７１］として選択される場合に、選択された要素のモジュラ演算は、２−４＝−１・７＋５＝５  ｍｏｄ  ７、５＋６＝１１＝１・７＋４＝４  ｍｏｄ  ７、および５・６＝３０＝４・７＋２＝２  ｍｏｄ  ７と定義することができる。
【００２２】
ガロア体ＧＦ［ｐｋ］での除算の算術演算は、一意の逆数を定義することを必要とする。より一般的に、ガロア体ＧＦ［ｐｋ］に含まれる数による除算は、概念上、前記数の逆数による乗算と同等である。たとえば、ガロア体ＧＦ［ｐｋ］が、ガロア体ＧＦ［１１］として選択される場合に、選択された要素のモジュラ演算は、４・３＝１２＝１  ｍｏｄ  １１と定義することができる。そのようなシナリオでは、４が、ガロア体ＧＦ［１１］での３の逆数である。同様に、３は、ガロア体ＧＦ［１１］での４の逆数である。
【００２３】
理解されるとおり、ガロア体ＧＦ［ｐｋ］での除算の算術演算は、前記ガロア体ＧＦ［ｐｋ］の非ゼロ要素についてのみ有効である。たとえば、ガロア体ＧＦ［ｐｋ］が、ガロア体ＧＦ［２３］として選択される場合に、要素０とＸのモジュラ演算は、０・Ｘ＝０Ξ０  ｍｏｄ  ８と定義される。Ｘは、ガロア体ＧＦ［２３］の任意の要素である。そのようなシナリオでは、ガロア体ＧＦ［２３］に０の逆数が存在しない。したがって、要素０とガロア体ＧＦ［２３］の別の要素との乗算を逆転して、一緒に乗算される２つの要素のうちの１つを得ることはできない。特筆すべきことに、ガロア体ＧＦ［２３］には、偶数要素｛０，２，４，６｝の逆数も存在しない。より一般的に、ガロア体ＧＦ［２ｋ］には、偶数要素の逆数が存在しない。より一般的に、ガロア体ＧＦ［ｐ］では、素数標数ｐによって除算可能ではない数だけが一意の逆数を有することが、真である。
【００２４】
もう一度図１を参照すると、本発明は、ガロア体乗算の上で説明した短所を迂回するＣＧＦＣ法１００を提供する。本発明は、ガロア体ＧＦ［ｐ］の要素について逆数が存在することを保証するＣＧＦＣ法１００をも提供する。一般に、この方法は、任意の複数のｋビットデータストリームに対してアフィン変換を実行することを伴う。結果のデータストリームを、ガロア体ＧＦ［ｐｋ＋１］でのガロア体乗算によって効率的に可逆に組み合わせることができる。アフィン変換は、出力値の可変性を拡大し、これによってｋビットデータストリームのリバースエンジニアリングをよりむずかしくする、追加の自由度をもたらす。当業者が了解するであろうとおり、アフィン変換は、一般に、ディジタル語の末尾に１を付加すること、またはディジタル語の末尾から１を除去することを伴う。
【００２５】
次の実施例は、アフィン変換をさらに例示するために提供される。しかし、本発明の範囲を、いかなる形であってもこれによって限定されると考えてはならない。
【実施例１】
【００２６】
ｐが２と等しく、ｋが３と等しいものとする。ガロア体ＧＦ［８］からガロア体ＧＦ［１６］への単純なアフィン変換は、ガロア体ＧＦ［８］の数の各３ビット表現の最下位ビット（ＬＳＢ）の後ろに１を付加することによって実行される。このアフィン変換は、０→１、１→３、２→５、３→７、４→９、５→１１、６→１３、および７→１５をもたらす。拡大されたガロア体の各数は、一意の逆数を有する。明らかに、１−１  ｍｏｄ  １６Ξ１、３−１  ｍｏｄ  １６Ξ１１、５−１  ｍｏｄ  １６Ξ１３、７−１  ｍｏｄ  １６Ξ７、９−１  ｍｏｄ  １６Ξ９、１１−１  ｍｏｄ  １６Ξ３、１３−１  ｍｏｄ  １６Ξ５、および１５−１  ｍｏｄ  １６Ξ１５である。ガロア体ＧＦ［１６］からガロア体ＧＦ［８］へのアフィン変換は、（ｙ−１）／２として実行され、ここで、ｙは、ガロア体ＧＦ［１６］乗算の結果である。ガロア体ＧＦ［２ｋ］からガロア体ＧＦ［２ｋ＋１］へのアフィン変換は、必ず奇数の値を生じる。ガロア体ＧＦ［２ｋ＋１］乗算の結果ｙは、必ず奇数である。ｙ−１は、必ず偶数である。ガロア体ＧＦ［２ｋ＋１］からガロア体ＧＦ［２ｋ］へのアフィン変換は、単純に、ｙから最下位ビット（ＬＳＢ）を捨て、ｋ個の上位ビットを残すことによって達成される。
【００２７】
もう一度図１を参照すると、ＣＧＦＣ法１００は、ステップ１０２で開始され、ステップ１０４に継続する。ステップ１０４では、２つのデータ入力Ｘ１およびＸ２を閉ガロア体組合せ系で受け取る。閉ガロア体組合せ系は、図５に関して下で説明するものなどの閉ガロア体暗号化システムとすることができるが、これに限定はされない。その後、ステップ１０６を実行し、ここで、ガロア体ＧＦ［ｐｋ］の次元を値ｐだけ増やす。ステップ１０６の後に、ステップ１０８を実行し、ここで、ガロア体ＧＦ［ｐ−１］からの非ゼロ要素を、データ入力Ｘ１およびＸ２のそれぞれに加える。ステップ１０６および１０８が、集合的にオリジナル数範囲とガロア拡大体の数範囲との間のアフィン変換を提供することに留意されたい。このアフィン変換は、定数関数または時間の関数として選択することができる。アフィン変換は、当業者に周知であり、したがって、本明細書では詳細には説明しない。しかし、アフィン変換を全単写像と考えることができることを理解されたい。全単写像、単射写像、および全射写像も、当業者に周知であり（たとえば、非特許文献１〜３を参照されたい）、したがって、本明細書では詳細には説明しない。
【００２８】
ステップ１１０で、２つのデータ入力を、ガロア拡大体ＧＦ［ｐｋ＋１］でのガロア体乗算演算を介して組み合わせる。ガロア体乗算演算は、データ入力Ｘ１およびＸ２の可逆再構築を保証するために実行される。この可逆演算は望ましく、第１データ入力Ｘ１を、事前定義の数学的処理および第２データ入力Ｘ２の先験的知識を介して入手できるようになる。
【００２９】
ステップ１１０で、ＣＧＦＣ法１００は、ステップ１１２に継続する。ステップ１１２では、既知のデジットを前記ガロア体乗算演算の結果から引く。ステップ１１４で、ガロア体ＧＦ［ｐｋ＋１］の次元を値ｐだけ減らす。その後、ステップ１１６を実行し、ここでＣＧＦＣ法１００が終了する。
【００３０】
図１のステップ１１０をもう一度参照し、ガロア体での乗算の原理的説明および機構の短い議論を、読者が本発明を理解するのを助けるために提供する。本発明の範囲が、いかなる形でもこれによって限定されると考えられてはならないことに留意されたい。
【００３１】
理解されるとおり、ガロア体の２つの数の乗算は、同一のガロア体に含まれる別の数をもたらす。乗算処理は、オリジナルの数の一方の知識を与えられた場合であっても、他方の数が逆数を有しない場合があるので、可逆でない場合がある。たとえば、ガロア体ＧＦ［８］の数２および４の乗算は、数０をもたらす（２×４＝８＝０  ｍｏｄｕｌｏ  ８）。数２および４はガロア体ＧＦ［８］では逆数を有しないので、０の出力値と一方の入力値とが既知の場合に、他方の入力値を再構築することはできない。より一般的に、乗算処理は、ガロア体ＧＦ［８］のいくつかの値について可逆ではない。
【００３２】
保証された可逆乗算への解決策は、乗算される数を、所与のガロア体で逆数を有する数に制限することである。この制限は、受け入れられる数を作るか出力を受け入れられる数に写像するかのいずれかにするために、乱数生成器に追加の要件を課す。すべての要素が一意の逆数を有するようになる構造を実施する１つの方法は、オリジナルのガロア体の次元を増やし、最初の数の集合を拡大されたガロア体の別個の可逆部分集合に写像することである。増やされた次元を有するガロア体を、本明細書ではガロア拡大体と称する。オリジナルのガロア体の要素と逆数を有するガロア拡大体の要素との間に単射写像が存在することを示すことができる。この可逆性は、単射写像を介するオリジナルのガロア体の数の一意乗算を可能にし、有効な全単写像を実施する。
【実施例２】
【００３３】
一例として、ガロア体ＧＦ［３２］の要素の直接（不可逆）乗算を、ガロア拡大体ＧＦ［３３］の部分集合に射影された時の同一要素の（可逆）乗算と比較されたい。ガロア体ＧＦ［３２］の要素を、次の表１に示す。ガロア体ＧＦ［３３］の要素を、次の表２に示す。表１および２の数が、２デジット３進表現で表されていることに留意されたい。
【表１】
2008299330.tif 000003
【表２】
2008299330.tif 000004
【００３４】
表１の第１行および第１列に示された乗算結果が、必ずゼロ（００）であることに留意されたい。この結果は、これらの値が不可逆であることを意味する。さらに、２つの一様にランダムな入力数列を与えられた場合の出力数列の統計的分布は、２１／８１個の出力がゼロ（００）と等しくなるようにゆがめられ、これによって、所望の一様分布が除去される。表２は、入力も一様分布である時に、必ず、出力の完全に一様に分布する集合を示す。入力値または出力値のいずれかを与えられれば、他方の入力を一意に再構築することができる。この可逆特性は、各出力値が、表２の各行または各列に１回だけ現れるという事実から、最も簡単に知ることができる。
【００３５】
ガロア体乗算が、加重記数法での同等の乗算より計算効率がよいことに留意されたい。というのは、出力値の個数が、有限集合に制限されるからである。成句「加重記数法」は、本明細書で使用される時に、剰余数系以外の記数法を指す。
【００３６】
ガロア体ＧＦ［２ｋ］などの２進法でのガロア体乗算が、ディジタル論理の構造に起因して実際面で有用であることにも留意されたい。従来の乗算と比較した、ディジタルハードウェアでのガロア体乗算の計算節約は、５０％を超える。ガロア体乗算演算をもたらすアルゴリズムは、当業者に周知であり、したがって、本明細書では説明しない。一般に、ガロア体での乗算結果は、中間算術ステップの部分的情報だけが一意の出力値を決定するのに必要なので、より効率的に得ることができる。
【００３７】
さらに、ガロア体乗算を介して２つの数を組み合わせることは、その２つの数の知識がない時に、必ずその２つの数のマスキングをもたらすことに留意されたい。この特性は、多数の通信システムアプリケーションで望ましい。この特性は、個々の入力数列値の各デジットが、出力値の他のデジットに対するより大きい影響を有することを除いて、ビット単位ＸＯＲ（排他的論理和）論理演算を介して２つの数を組み合わせる組合せ技法にも匹敵する。ビット単位ＸＯＲ論理演算は、数がガロア拡大体ＧＦ［２２］におけるそれ自体の逆数に写像される、ガロア体ＧＦ［２１］のガロア拡大体乗算のスペシャルケースと見なすことができる。
【００３８】
ここで図２を参照すると、上で説明したＣＧＦＣ法１００は、ＣＧＦＣ算術処理２００によってさらに定義することができる。ＣＧＦＣ算術処理２００は、データ入力Ｘ１およびＸ２を用いて開始される。データ入力Ｘ１は、ペイロードデータまたは乱数列の乱数とすることができる。データ入力Ｘ２は、擬似乱数列の擬似乱数または擬似無秩序乱数列の擬似無秩序乱数とすることができる。成句「ペイロードデータ」は、本明細書で使用される時に、文字または句読点記号など、自然言語の書かれた記号と同等の数値であるデータを指す。たとえば、数３が文字Ｃと同等の数値である場合に、データ入力Ｘ１は、３の値を有する。データ入力は、事前定義の符号化処理を使用する任意のタイプのデータに関する同等の数値とすることもできる。
【００３９】
データ入力Ｘ１、Ｘ２は、次元ｐｋのガロア体ＧＦ［ｐｋ］のメンバとして表現される。ｐｋは、ガロア体ＧＦ［ｐｋ］の有限体サイズを定義する素数である。本発明の実施形態によれば、データ入力Ｘ１、Ｘ２は、２の冪（べき）の次元を有するガロア体すなわち、ガロア体ＧＦ［２ｋ］表現で表される。そのようなシナリオでは、２進算術でのガロア体ＧＦ［２ｋ］の要素の操作は、自明である。
【００４０】
データ入力Ｘ１、Ｘ２は、ｐ進記数法表現または混合基数記数法表現で表される。ｐ進記数法および混合基数記数法は、当業者に周知であり、したがって、本明細書では詳細には説明しない。しかし、ｐ進数が、所与の互いに素な数ｐによる整数の整除性に基づく自然数の体の拡大の要素であることを了解されたい。成句「自然数」は、本明細書で使用される時に、０より大きい正整数の集合を指す。実際には、ｐは、２より大きいか２と等しい（ｐ＝２）。というのは、１と等しいｐの値（ｐ＝１）が、情報を含まないからである。自然数の体の拡大は、ｐ進数列をもたらす。ｐ進数列は、剰余ｘｋ  ｍｏｄｕｌｏ  ｐのｋ個の要素（ｘ０，ｘ１，…，ｘｋ−１）からなる。
【００４１】
図２に示されているように、最初の乗算演算２０２、２０４および加算演算２０６、２０８は、データ入力Ｘ１、Ｘ２を使用して実行される。これらの演算２０２、２０４、２０６、２０８は、アフィン変換を介して有限体またはガロア体ＧＦ［ｐｋ］のサイズをｐｋからｐｋ＋１に増やすために実行される。ｐは、任意の素数になるように選択される。それでも、本発明はこれに関して限定されない。たとえば、ｐを、中国の剰余定理に似た処理を介して合成数に拡大することができる。乗算演算２０２、２０４の積を、以下ではＹ１およびＹ２と称する。積Ｙ１、Ｙ２は、数式（１〜２）によって定義される。
Ｙ１＝Ｘ１・ｐ１    （１）
Ｙ２＝Ｘ２・ｐ１    （２）
ここで、Ｙ１およびＹ２は、乗算演算２０２、２０４を介して得られる積である。
【００４２】
その後、加算演算２０６、２０８を実行して、有限体またはガロア体ＧＦ［ｐ１］からの非ゼロ定数Ｃ１、Ｃ２を各積Ｙ１、Ｙ２に加算する。非ゼロ定数Ｃ１、Ｃ２は、１、２、…、またはｐ−１の値を有する。これらの加算演算２０６、２０８によって、入力アフィン変換が完了し、データ入力Ｘ１、Ｘ２の逆数の存在が保証される。ｐ＝２であり、算術演算２０６、２０８が２進算術で実行される場合に、このアフィン変換が、データ入力Ｘ１、Ｘ２の最下位ビット（ＬＳＢ）の右側への２進１の単純な付加であり、したがって、１がガロア体ＧＦ［２］の唯一の非ゼロ要素なので、２Ｘ＋１を実施することを了解されたい。
【００４３】
加算演算２０６、２０８の結果を、以下ではＺ１およびＺ２と称する。結果Ｚ１、Ｚ２は、数式（３〜４）によって定義される。
Ｚ１＝Ｙ１＋Ｃ１＝（Ｘ１・ｐ１）＋Ｃ１    （３）
Ｚ２＝Ｙ２＋Ｃ２＝（Ｘ２・ｐ１）＋Ｃ２    （４）
ここで、Ｚ１およびＺ２は、加算演算の結果である。Ｙ１およびＹ２は、乗算演算２０２、２０４を介して得られる積である。Ｃ１およびＣ２は、有限体またはガロア体ＧＦ［ｐ］から選択される非ゼロ定数である。Ｘ１およびＸ２は、ＲＮＳ剰余値、ｐ進記数法表現、または混合基数記数法表現として表されたデータ入力である。ｐは、ガロア体ＧＦ［ｐ］の有限体サイズを定義する素数の定数である。
【００４４】
その後、ガロア体乗算２１０を、結果Ｚ１、Ｚ２を使用して実行する。このガロア体乗算２１０は、データ入力Ｘ１、Ｘ２を拡大されたガロア体ＧＦ［ｐｋ＋１］で組み合わせるために実行される。ガロア体乗算２１０の結果は、数式（５）によって定義される。
ＲＶ１＝Ｚ１・Ｚ２（ｍｏｄ  ｐｋ＋１）＝［（Ｘ１・ｐ１）＋Ｃ１］・［（Ｘ２・ｐ１）＋Ｃ２］（ｍｏｄ  ｐｋ＋１）    （５）
ここで、ＲＶ１は、ガロア体乗算２１０の結果である。ｐｋ＋１は、拡大されたガロア体ＧＦ［ｐｋ＋１］のサイズによって定義される値を有する係数である。ガロア体ＧＦ［ｐｋ＋１］からの２つの要素が乗算される時に、その積は、そのガロア体ＧＦ［ｐｋ＋１］に含まれるもう１つの要素であることを理解されたい。効果的に、乗算演算が結果Ｚ１、Ｚ２を使用して実行されている間に、有限の構造サイズが維持される。たとえば、ｐｋ＋１が、１６の値を有するように選択され、積Ｚ１・Ｚ２が、４５の値をもたらす場合に、算術演算４５  ｍｏｄｕｌｏ  １６の結果は、１３と等しい。値１３は、ガロア拡大体ＧＦ［１６］の有限に多数の可逆要素｛１，３，…，１５｝の一要素である。
【００４５】
図２に示されているように、非ゼロ定数Ｃ１、Ｃ２は、ガロア体乗算２１２を介して一緒に組み合わされる。このガロア体ＧＦ［ｐ１］乗算２１２は、非ゼロ定数Ｃ１、Ｃ２をガロア体ＧＦ［ｐ１］内で組み合わせるために実行される。ガロア体乗算２１２の結果は、数式（６）によって定義することができる。
ＲＶ２＝−Ｃ１・Ｃ２（ｍｏｄ  ｐ）    （６）
ここで、ＲＶ２は、非ゼロ定数Ｃ１、Ｃ２を表す値である。ｐは、ガロア体ＧＦ［ｐ１］の有限体サイズを定義する素数値を有する係数である。ｐが１と等しく（ｐ＝１）、Ｃ１かけるＣ２が１と等しい（Ｃ１＝Ｃ１＝Ｃ１・Ｃ２＝１）場合には、逆数が両方のデータ入力Ｘ１、Ｘ２について必ず存在するので、このガロア拡大体での乗算２１２を実行する必要はない。
【００４６】
図２に示されているように、（ＲＶ１−ＲＶ２）・ｐ−１を計算して、ガロア体ＧＦ［ｐｋ＋１］からガロア体ＧＦ［ｐｋ］へのアフィン変換２１４を実行する。アフィン変換２１４は、結果Ｑを得るためにＲＶ１からＲＶ２を引くことを含む。結果Ｑは、数式（７）によって定義することができる。
Ｑ＝ＲＶ１−ＲＶ２    （７）
【００４７】
その後、積Ｑを乗算演算２１６を介してｐ１の逆数と組み合わせて、組み合わされた出力（ＣＯ）を得る。組み合わされた出力は、数式（８）によって定義することができる。
ＣＯ＝Ｑ・ｐ−１    （８）
ここで、Ｑは、ＲＶ１からＲＶ２を引くことから得られる結果である。ｐ−１は、素数ｐの逆数である。
【００４８】
全体的なＣＧＦＣ算術処理２００は、全般的に数式（９）によって定義することができる。
【００４９】
【数１】
2008299330.tif 000005
ここで、ｐは、ガロア体ＧＦ［ｐｍ］の有限体サイズを定義する素数定数である。Ｘ１およびＸ２は、ｐ進記数法表現または混合基数記数法表現の値として表されたデータ入力である。Ｃ１およびＣ２は、ガロア体ＧＦ［ｐ］から選択された非ゼロ値である。ｐｋ＋１は、ガロア体ＧＦ［ｐｋ＋１］の有限体サイズを定義する数値である。２と等しいｐ（ｐ＝２）について、拡大ガロア体ＧＦ［２ｋ＋１］でのすべての積が、奇数であることに留意されたい。したがって、数式（８）で定義される演算は、ｍｏｄｕｌｏ  ２ｋ＋１かけるＲＶ１のｋ＋１ビット結果をｋ個の最上位ビット（ＭＳＢ）に切り詰めることによって、２進算術で単純に実行することができる。より一般的には、最下位ビット（ＬＳＢ）が、ＲＶ１からＲＶ２を引いた結果から除去される。
【００５０】
図２をもう一度参照すると、乱数列の繰返し周期を拡大する方法を、簡単に構築することができる。２つの乱数列を、互いに素な繰返し周期を有する擬似乱数生成器から来る入力Ｘ１およびＸ２として与えられれば、出力数列は、入力繰返し周期の積と等しい繰返し周期を有するもう１つの擬似乱数列を作る非線形組合せになる。この段落で説明する方法は、ガロア体の中での乗算が結合的なので、多数の乱数生成器の組合せに自明に拡張される。この文脈では、「結合的」特性は、算術処理への入力を任意の組合せで並べ変え、同一の出力をもたらす能力を指す。ＣＧＦＣ算術処理２００（図２に関して上で説明した）全体が、結合的であることに留意されたい。
【００５１】
ＣＧＦＣ算術処理２００を、符号化処理に従って変更できることを理解されたい。そのようなシナリオでは、データ入力Ｘ１を、データを表す数列からの数とすることができる。Ｘ２は、符号化数列からの数とすることができる。符号化数列は、擬似乱数列または擬似無秩序乱数列とすることができるが、これらに限定はされない。そのような変更されたＣＧＦＣ算術処理２００の例を、図３に示す。
【００５２】
ここで図３を参照すると、データを符号化するＣＧＦＣ算術処理３００のブロック図が示されている。ＣＧＦＣ算術処理３００を、他の処理と共に使用して、ストリーム暗号または他の符号化アルゴリズムを作成することができることを理解されたい。そのような構造は、フィードバックループ、スクランブリング、および混合基数演算を含むが、これらに限定はされない。
【００５３】
図３に示されているように、データ数列３０２の各値は、ガロア拡大体乗算３１４（図１および図２に関して上記説明した）を介してコード数列３０４の値と組み合わされる。データ数列３０２および／またはコード数列３０４を、既知の数学的関係を有するように選択できることに留意されたい。データ数列３０２およびコード数列３０４は、加重記数法で表された複数のデジットからなるものとすることもできる。そのようなシナリオでは、データ数列３０２およびコード数列３０４を、各数列３０２、３０４からのデジットの別個の部分集合を使用するガロア拡大体乗算３１４を選択的に実行することによって組み合わせることができる。
【００５４】
コード数列３０４値のダイナミックレンジが、データ数列３０２値のダイナミックレンジ以上であると仮定されることに留意されたい。本明細書で使用される時に、成句「ダイナミックレンジ」は、数または測定値の可能な値の個数を指す。ダイナミックレンジは、可能な入力値の集合の濃度と同等である。
【００５５】
コード数列３０４を、１つまたは複数の乱数生成器によって生成された値の切り捨てられた選択またはランダム選択から形成できることにも留意されたい。乱数生成器は、当業者に周知であり、したがって、本明細書では詳細には説明しない。符号化処理３００の符号化されたデータ出力数列３２０は、コード数列３０４値を使用する、データ数列３０２値に対する符号化または暗号化暗号のブロックを表す。
【００５６】
符号化されたデータ出力数列３２０を復号するほぼ対称の方法が存在することに、さらに留意されたい。復号処理は、組み合わされた出力符号化データ数列３２０からデータ数列３０２を得るために実行することができる。以下において、そのような逆ＣＧＦＣ算術処理を図４で説明する。
【００５７】
ここで図４を参照すると、第１の入力数列４０２は、符号化処理３００（図３に関して上記説明した）で展開された符号化されたデータ出力数列３２０である。第２の入力数列４０４は、符号化処理３００で利用されたコード数列３０４に基づく、逆数にされたコード数列である。このコード数列３０４に対する「逆数にする」演算は、組合せステップで使用されるものと同一のガロア拡大体の中のコード数列３０４値の一意の逆数を表す、オリジナルのコード数列３０４値からの単射写像を指す。この逆数にする演算は、値ごとの基礎で計算される。この逆数にする演算は、算術処理、ディジタル論理、ルックアップテーブル、またはソフトウェアの任意の組合せを使用して実施することができる。剰余数系の中で逆数を突き止める効率的な方法は、当業者に周知であり、したがって、本明細書では詳細には説明しない。しかし、ガロア体の中で逆数を求める１つの一般的な方法が、拡張ユークリッド互除法（Ｅｘｔｅｎｄｅｄ  Ｅｕｃｌｉｄｅａｎ  ａｌｇｏｒｉｔｈｍ）を介することに留意されたい。拡張ユークリッド互除法は、当業者に周知であり、したがって、本明細書では詳細には説明しない。
【００５８】
逆数にされたコード数列４０４を与えられて、復号処理４００は、ＣＧＦＣ算術処理２００（図２に関して上記説明した）と同一の組合せ技法に従う。これに関して、復号処理４００が、乗算演算４０６、４０８および加算演算４１０、４１２を含むことを了解されたい。復号処理４００は、ガロア拡大体乗算演算４１４およびガロア体乗算演算４１６をも含む。この復号処理は、さらに、加算演算４１８および乗算演算４２２を含む。復号処理４００の出力数列４２０は、図３のオリジナルのデータ数列３０２と同一である。
【００５９】
表３は、ガロア体ＧＦ［８］が図３および図４に示された流れに従う場合の、データ数列およびコード数列から可能な符号化された値および復号された値のすべてを表す。表見出し「第１データソースからのデータ数列」が、図３のデータ数列３０２の値を指すことを了解されたい。表見出し「第２データソースからのコード数列」は、図３のコード数列３０４の値を指す。表見出し「第１データソースアフィン変換」は、図３の乗算演算３０６および加算演算３１０によって作られるＺ１の値を指す。表見出し「第２データソースアフィン変換」は、図３の乗算演算３０８および加算演算３１２によって作られるＺ２の値を指す。表見出し「ＧＦ［１６］結果」は、図３の中間結果ＲＶ１を指す。表見出し「ＧＦ［８］結果」は、図３の中間結果ＣＯを指す。表見出し「ＧＦ［１６］での１／データソース２」は、図４の中間結果Ｚ４を指す。表見出し「ＧＦ［８］復号されたデータ」は、図４の復号されたデータ数列４２０を指す。この２進（ｐ＝２）例では、値のそれぞれに付加される任意の非ゼロ値が、必ず１であることに留意されたい。また、復号ステップが、数列値自体ではなく、ランダム数列の逆数による乗算を必要とすることに留意されたい。
【表３−１】
2008299330.tif 000006
【表３−２】
2008299330.tif 000007
【表３−３】
2008299330.tif 000008
【表３−４】
2008299330.tif 000009
【００６０】
閉ガロア体暗号系（ＣＧＦ暗号システム）
従来の暗号系（システム）が、通常は、ディジタルハードウェアで実施される非対称暗号化処理技法または非対称暗号化解除処理技法を必要とすることを理解されたい。成句「非対称処理」は、本明細書で使用される時に、関連する動作を実行するのに必要な時間、処理構造、または計算リソースにおける大きい差を指す。この非対称暗号化処理技法または非対称暗号化解除処理技法は、多くの暗号の機能性および応用可能性を制限する可能性がある。たとえば、ＲＳＡアルゴリズムは、データを暗号化するための公開鍵および秘密鍵の選択を伴う。この選択は、通常、所期のユーザによるメッセージの暗号化解除を、メッセンジャによる暗号化ステップよりはるかに簡単にする。ディジタルハードウェアは、通常、比較的多数のディジタル論理ゲートを含む。したがって、従来の暗号系は、比較的高い電力消費および比較的長いデータ処理時間を有する。対称処理を可能にする暗号化法は、ハードウェアの設計再利用ならびに機能および応用可能性におけるより高い柔軟性を可能にする。
【００６１】
閉ガロア体（ＣＧＦ）暗号系（システム）の実施形態（たとえば、図５に示されたもの）は、ディジタルハードウェアで実施される対称暗号化処理技法および対称暗号化解除処理技法を提供する。成句「対称処理」は、本明細書で使用される時に、非常に類似する処理構造、時間、およびリソースを使用してメッセージの暗号化と暗号化解除との両方を行う能力を指す。実際に、ＣＧＦ暗号系の実施形態は、従来の暗号系と比較して、比較的短いデータ処理時間を有する。ＣＧＦ暗号系の実施形態は、効率的な組合せ手段に起因して、従来の暗号系と比較して、比較的少ない電力消費をも有する。
【００６２】
ここで図５を参照すると、発明的配置を実施するのに使用できる閉ガロア体（ＣＧＦ）暗号系（システム）５００の一実施形態が示されている。ＣＧＦ暗号系５００は、メッセージ生成器５０２および乱数生成器（ＲＮＧ）５０４、５１０からなる。ＣＧＦ暗号系５００は、また、閉ガロア体（ＣＧＦ）暗号化システム５０６および閉ガロア体（ＣＧＦ）暗号化解除システム５０８からなる。メッセージ生成器５０２は、ペイロードデータを生成するように構成されたハードウェアおよびソフトウェアからなる。メッセージ生成器５０２は、また、ブロックフォーマットでペイロードデータを表す動作を実行するように構成されたハードウェアおよびソフトウェアからなる。メッセージ生成器５０２は、さらに、ＣＧＦ暗号化システム５０６にペイロードデータを通信するように構成されたハードウェアおよびソフトウェアからなる。
【００６３】
ＲＮＧ  ５０４は、暗号化数列を生成するように構成されたハードウェアおよびソフトウェアからなる。暗号化数列は、線形にまたは非線形に生成された擬似乱数または擬似無秩序乱数からなるものとすることができる。ＲＮＧ  ５０４は、また、ＣＧＦ暗号化システム５０６に乱数列を通信するように構成されたハードウェアおよびソフトウェアからなる。
【００６４】
ＣＧＦ暗号化システム５０６は、メッセージ生成器５０２からペイロードデータを受け取り、ＲＮＧ  ５０４から暗号化数列を受け取るように構成されたハードウェアおよびソフトウェアからなる。ＣＧＦ暗号化システム５０６は、また、乱数列を使用してペイロードデータを暗号化するためにＣＧＦＣ法１００（図１に関して上記説明した）およびＣＧＦＣ算術処理３００（図３に関して上記説明した）を実施し、実行するように構成されたハードウェアおよびソフトウェアからなる。ＣＧＦ暗号化システム５０６は、さらに、ＣＧＦ暗号化解除システム５０８に組み合わされた出力を通信するように構成されたハードウェアおよびソフトウェアからなる。
【００６５】
ＲＮＧ  ５１０は、暗号化解除数列を生成するように構成されたハードウェアおよびソフトウェアからなる。暗号化解除数列は、線形にまたは非線形に生成された擬似乱数または擬似無秩序乱数からなるものとすることができる。暗号化解除数列は、ＲＮＧ  ５０４によって生成された暗号化数列と同一とすることができる。ＲＮＧ  ５１０は、また、データブロックフォーマッティングを実行するように構成されたハードウェアおよびソフトウェアからなる。ＲＮＧ  ５１０は、さらに、ＣＧＦ暗号化解除システム５０８に暗号化解除数列を通信するように構成されたハードウェアおよびソフトウェアからなる。
【００６６】
ＣＧＦ暗号化解除システム５０８は、ＣＧＦ暗号化システム５０６から組み合わされた出力を受け取り、ＲＮＧ  ５１０から暗号化解除数列を受け取るように構成されたハードウェアおよびソフトウェアからなる。ＣＧＦ暗号化解除システム５０８は、また、ペイロードデータを暗号化解除するために逆ＣＧＦＣ算術処理４００（上で図４に関して説明した）を実施し、実行するように構成されたハードウェアおよびソフトウェアからなる。ＣＧＦ暗号化解除システム５０８は、さらに、外部デバイス（図示せず）にメッセージデータを通信するように構成されたハードウェアおよびソフトウェアからなる。
【００６７】
本発明の前述の説明に鑑みて、本発明をハードウェア、ソフトウェア、またはハードウェアおよびソフトウェアの組合せで実現できることを認められたい。本明細書で説明した方法を実行するように適合されたすべての種類のコンピュータシステムまたは他の装置が、適する。ハードウェアおよびソフトウェアの通常の組合せは、ロードされ実行された時に本明細書で説明した方法を実行するようにコンピュータプロセッサを制御するコンピュータプログラムを伴う、汎用コンピュータプロセッサとすることができる。もちろん、特定用途向け集積回路（ＡＳＩＣ）および／またはＦＰＧＡを使用して、類似する結果を達成することもできる。
【００６８】
本発明を、本明細書で説明した方法の実施を可能にするすべての特徴を含み、コンピュータシステムにロードされた時にこれらの方法を実行することができる、コンピュータプログラム製品で実施することもできる。現在の文脈でのコンピュータプログラムまたはアプリケーションは、ａ）別の言語、コード、もしくは表記への変換、またはｂ）異なる材料形態での再作成のいずれかまたは両方の後にあるいは直接に、のいずれかで特定の機能を実行する情報処理能力をシステムが有するようにすることを意図された命令の組の、任意の言語、コード、または表記でのすべての表現を意味する。さらに、上の説明は、例のみとして意図されており、添付の特許請求の範囲で示されるものを除いて、いかなる形でも本発明を限定することは意図されていない。
【図面の簡単な説明】
【００６９】
【図１】本発明を理解するのに有用な閉ガロア体組合せ（ＣＧＦＣ）法を示す流れ図である。
【図２】本発明を理解するのに有用なＣＧＦＣ算術処理を示す図である。
【図３】本発明を理解するのに有用な、データを符号化するＣＧＦＣ算術処理を示す図である。
【図４】本発明を理解するのに有用な、データを復号するＣＧＦＣ算術処理を示す図である。
【図５】本発明を理解するのに有用な、閉ガロア体暗号系を示すブロック図である。
【符号の説明】
【００７０】
５００  ＣＧＦ暗号システム
５０２  メッセージ生成器
５０４、５１０  乱数生成器
５０６  ＣＧＦ暗号化システム
５０８  ＣＧＦ暗号化解除システム
【図１】
2008299330.tif 000010
【図２】
2008299330.tif 000011
【図３】
2008299330.tif 000012
【図４】
2008299330.tif 000013
【図５】
2008299330.tif 000014
【外国語明細書】
2008299330000001.pdf