(57)【要約】本発明の実施形態は、ＧＦ（２２ｓ）をＧＦ（（２ｓ）２）表現に変換し（１０２）、ＧＦ（（２ｓ）２）表現においてＧＦ（２２ｓ）の場合と等価な演算を実行する（１０４）ことによって、ＧＦ（２２ｓ）表現で与えられるデータを操作するための、例えば、ＧＦ（２２ｓ）表現で与えられるデータに対して少なくともいくつかのＡＥＳ暗号化および／または復号化演算を実行するための方法および装置を提供する。
2005534973.tif 000002
【特許請求の範囲】
【請求項１】
ＧＦ（２２ｓ）表現のデータを、前記ＧＦ（２２ｓ）表現のデータに所定の変換に関連する変換演算子を作用させることによって、対応するＧＦ（（２ｓ）２）表現のデータに変換するステップを含むデータ操作方法。
【請求項２】
前記変換演算子が、前記変換に対応する表現変換行列に関連する、請求項１に記載の方法。
【請求項３】
前記変換演算子が、前記表現変換行列の逆行列である、請求項２に記載の方法。
【請求項４】
前記変換演算子が、線形変換と前記表現変換行列の組み合わせを含む、請求項２に記載の方法。
【請求項５】
前記変換演算子が、前記表現変換行列とＡＥＳ  Ｓボックスパラメータ行列の行列積の逆行列を含む、請求項４に記載の方法。
【請求項６】
前記ＧＦ（（２ｓ）２）表現が、ＧＦ（２ｓ）上の既約簡約多項式とＧＦ（２ｓ）上の拡大多項式とによって定義される、請求項１から５のいずれかに記載の方法。
【請求項７】
ＧＦ（２ｓ）上の前記拡大多項式が、ＧＦ（２ｓ）上の２次既約多項式を含む、請求項６に記載の方法。
【請求項８】
前記表現変換行列が、所定の基準に照らして可能な表現変換行列の集合から選択される、請求項２から７のいずれかに記載の方法。
【請求項９】
前記行列の集合の各行列が、前記ＧＦ（２２ｓ）表現上の既約多項式の根と前記ＧＦ（（２ｓ）２）表現の体生成元とによって定義される、請求項８に記載の方法。
【請求項１０】
前記ＧＦ（（２ｓ）２）表現のデータを、前記ＧＦ（２２ｓ）表現での少なくとも１つの所望の演算と等価な少なくとも１つの演算を実行することによって処理して、処理されたＧＦ（（２ｓ）２）データを取得するステップを含む、請求項１から９のいずれかに記載の方法。
【請求項１１】
前記ＧＦ（２２ｓ）表現のデータが、２以上のデータブロックを含み、前記方法が、前記ＧＦ（（２ｓ）２）表現のデータを、前記ＧＦ（２２ｓ）表現での少なくとも１つの所望の演算と等価な前記ＧＦ（（２ｓ）２）表現での少なくとも１つの演算を前記２以上のデータブロックに対して実行することによって処理して、処理されたＧＦ（（２ｓ）２）データを取得するステップを含む、請求項１から９のいずれかに記載の方法。
【請求項１２】
前記処理されたＧＦ（（２ｓ）２）データを、前記処理されたＧＦ（（２ｓ）２）データに前記所定の変換に関連する逆変換演算子を作用させることによって、前記ＧＦ（２２ｓ）表現に変換し直すステップを含む、請求項１０または１１に記載の方法。
【請求項１３】
ｓが４に等しい、請求項１から１２のいずれかに記載の方法。
【請求項１４】
ＡＥＳ  Ｓボックスを実施するのに適した安全なメモリ記憶装置であって、
ＧＦ（２２ｓ）表現のデータを対応するＧＦ（（２ｓ）２）表現のデータに変換する入力変換モジュールと、
前記ＧＦ（２２ｓ）表現での少なくとも１つの所望の演算と等価な少なくとも１つの演算を実行して、処理されたＧＦ（（２ｓ）２）データを取得する演算モジュールと、
前記処理されたＧＦ（（２ｓ）２）データを前記ＧＦ（２２ｓ）表現に変換し直す出力変換モジュールとを含む装置。
【請求項１５】
前記入力変換モジュールが、前記ＧＦ（２２ｓ）データの線形変換に表現変換行列に関連する行列を乗じるための乗算器を含む、請求項１４に記載の装置。
【請求項１６】
前記少なくとも１つの所望の演算が、逆演算を含む、請求項１４または１５に記載の装置。
【請求項１７】
前記出力変換モジュールが、前記処理されたＧＦ（（２ｓ）２）データの線形変換に表現変換行列に関連する行列を乗じるための乗算器を含む、請求項１４から１６のいずれかに記載の装置。
【請求項１８】
ｓが４に等しい、請求項１４から１７のいずれかに記載の方法。
【請求項１９】
表現変換を決定するための方法であって、
ＧＦ（２２ｓ）表現からＧＦ（（２ｓ）２）表現への複数の表現変換にそれぞれ対応する複数の回路を合成するステップと、
少なくとも１つの最適化基準に照らして前記複数の表現変換から１つを選択するステップとを含む方法。
【請求項２０】
前記複数の回路を合成するステップが、前記複数の回路を組み立てるステップを含む、請求項１９に記載の方法。
【請求項２１】
前記複数の回路を合成するステップが、前記複数の回路をシミュレートするステップを含む、請求項１９または２０に記載の方法。
【請求項２２】
ｓが４に等しい、請求項１９から２１のいずれかに記載の方法。
【請求項２３】
前記複数の表現行列が、１９２個の行列を含む、請求項１９から２２のいずれかに記載の方法。
【請求項２４】
前記少なくとも１つの基準が、回路面積を含む、請求項１９から２３のいずれかに記載の方法。
【請求項２５】
前記少なくとも１つの基準が、電力消費を含む、請求項１９から２３のいずれかに記載の方法。
【請求項２６】
ＧＦ（２２ｓ）表現のデータを、前記ＧＦ（２２ｓ）表現のデータに所定の変換に関連する復号変換演算子を作用させることによって、対応するＧＦ（（２ｓ）２）表現のデータに変換するステップと、
前記ＧＦ（（２ｓ）２）表現のデータを、前記ＧＦ（２２ｓ）表現での所望の復号化演算と等価な少なくとも１つの演算を実行することによって処理して、処理されたＧＦ（（２ｓ）２）データを取得するステップと、
前記処理されたＧＦ（（２ｓ）２）データを前記ＧＦ（２２ｓ）表現に変換し直すステップとを含むデータを復号化するための方法。
【請求項２７】
ＧＦ（２２ｓ）表現のデータを、前記ＧＦ（２２ｓ）表現のデータに所定の変換を作用させることによって、対応するＧＦ（（２ｓ）２）表現のデータに変換するステップと、
前記ＧＦ（（２ｓ）２）表現のデータを、前記ＧＦ（２２ｓ）表現での所望の暗号化演算と等価な少なくとも１つの演算を実行することによって処理して、処理されたＧＦ（（２ｓ）２）データを取得するステップと、
前記処理されたＧＦ（（２ｓ）２）データを、前記処理されたＧＦ（（２ｓ）２）データに前記所定の変換に関連する暗号変換演算子を作用させることによって、前記ＧＦ（２２ｓ）表現に変換し直すステップとを含むデータを暗号化するための方法。
【請求項２８】
前記変換演算子を作用させるステップが、１つまたは複数の中間変換演算子を作用させて、前記ＧＦ（２２ｓ）表現のデータを前記ＧＦ（（２ｓ）２）表現のデータに再帰的に変換するステップを含む、請求項１から１３のいずれかに記載の方法。
【請求項２９】
復号変換回路と暗号変換回路とを含み、ＧＦ（２２ｓ）表現のデータをＧＦ（（２ｓ）２）表現の対応するデータに変換する入力変換モジュールと、
前記ＧＦ（２２ｓ）表現での所望の暗号化／復号化演算と等価な少なくとも１つの演算を実行して、処理されたＧＦ（（２ｓ）２）データを取得する演算モジュールと、
復号逆変換回路と暗号逆変換回路とを含み、前記処理されたＧＦ（（２ｓ）２）データを前記ＧＦ（２２ｓ）表現に変換し直す出力変換モジュールとを含む暗号化／復号化装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、有限体内での計算、および有限体の表現間の変換に関する。
【背景技術】
【０００２】
高度暗号標準（ＡＥＳ）は、ラインダール（Ｒｉｊｎｄａｅｌ）ブロック暗号アルゴリズム（「ラインダールアルゴリズム」）を提供し、このアルゴリズムは、入力バイトｘに関するバイトサブ（ＢｙｔｅＳｕｂ）ビットレベルの演算を含む。バイトサブ演算は、暗号化モードと復号化モードを含む。暗号化モードは、逆演算とアフィン変換の組み合わせを含み、例えば、Ａおよびｂを所定のパラメータとした場合、ｘは、Ａｘ−１＋ｂに変換される。復号化モードは、アフィン変換とそれに続く逆演算の組み合わせを含み、例えば、ｘは、（Ａ−１（ｘ＋ｂ））−１に変換される。ＡＥＳによれば、逆変換は、ガロア体ＧＦ（２８）上で前もって形成される。体は、簡約多項式ｐ（ｔ）＝ｔ８＋ｔ４＋ｔ３＋ｔ＋１を使用して、多項式で表現される。
【０００３】
他にも、ＧＦ（２８）において逆演算を実行する周知のブロック暗号アルゴリズムが存在する。それらのアルゴリズムには、例えば、Ｋ．Ａｏｋｉ他により「Ｓｐｅｃｉｆｉｃａｔｉｏｎ  ｏｆ  Ｃａｍｅｌｌｉａ−ａ  １２８−ｂｉｔ  Ｂｌｏｃｋ  Ｃｉｐｈｅｒ」、ｈｔｔｐ：／／ｉｎｆｏ．ｉｓｌ．ｎｔｔ．ｃｏ．ｊｐ／ｃａｍｅｌｌｉａ／で説明されている、カメリア（Ｃａｍｅｌｌｉａ）暗号アルゴリズムや、Ｈ．Ｌｅｅにより「Ｚｏｄｉａｃ  Ｂｌｏｃｋ  Ｃｉｐｈｅｒ  Ｐｒｏｐｏｓａｌ」、ｈｔｔｐ：／／ｗｗｗ．ｓａｆｅｄｉｇｍ．ｃｏｍ／ｐｒｏｄｕｃｔｐｄｓ／ｄｏｗｎｌｏａｄ／Ｓａｆｅｄｉｇｍ＿Ｚｏｄｉａｃ．ｐｄｆで説明されている、ゾディアック（Ｚｏｄｉａｃ）暗号アルゴリズムが含まれる。
【発明の開示】
【発明が解決しようとする課題】
【０００４】
ＡＥＳの一方法は、Ｓボックス（Ｓ−Ｂｏｘ）と呼ばれる、２つの参照用テーブルを実装し、ＧＦ（２８）を使用する場合、各テーブルは、ｘが取り得る２５６個の値に相当する２５６個の値を含む。暗号用Ｓボックスは、Ａｘ−１＋ｂの２５６個の値を含み、復号用Ｓボックスは、（Ａ−１（ｘ＋ｂ））−１の２５６個の値を含む。ＡＥＳの別の方法は、ｘの逆元、すなわち、ｘ−１の２５６個の値を含む、Ｆ（ｘ）で示される１つのテーブルを実装する。この方法は、２５６個の値を含むテーブルを１つ格納する必要があるだけでなく、ｘにＡまたはＡ−１を乗算し、ｂを加算することによって、暗号化／復号化アフィン変換を実行するための追加の回路も必要とする。したがって、ラインダールアルゴリズムによって定義される１組の計算を伴う、ＡＥＳ  Ｓボックスの従来の実装は、全体として十分に効率的とはいえない。
【０００５】
ＡＥＳの従来のハードウェアによる実施では、複数個の、例えば、１６個のＳボックスを必要とするので、より効率的なＳボックスを設計すれば、ＡＥＳ実施の複雑さを著しく緩和することができるであろう。
【０００６】
Ｖ．Ｒｉｊｍｅｎによる「Ｅｆｆｉｃｉｅｎｔ  ｉｍｐｌｅｍｅｎｔａｔｉｏｎ  ｏｆ  ｔｈｅ  Ｒｉｊｎｄａｅｌ  Ｓ−Ｂｏｘ」、ｈｔｔｐ：／／ｗｗｗ．ｅｓａｔ．ｋｕｌｅｕｖｅｎ．ａｃ．ｂｅ／〜ｒｉｊｍｅｎ／ｒｉｊｎｄａｅｌ／ｓｂｏｘ．ｐｄｆ（「ライメン文献」）に、ＧＦ（２４）の拡大としてのＧＦ（２８）の表現に基づく１組の計算を使用することによって、ＡＥＳ  Ｓボックスの効率を改善できることが示唆されている。しかし、ライメン文献では、どのようにすればそのような表現を実現できるかについて、開示も、示唆も、または暗示もされていない。さらに、ライメン文献では、拡大ＧＦ（２４）に基づくＡＥＳ  Ｓボックスが実装できたとしても、優れたＶＨＤＬコンパイラが使用されるなら、そのような実装は実用的には用をなさないと結論づけられている。したがって、ライメン文献は、拡大ＧＦ（２４）に基づいてＡＥＳ  Ｓボックスを実装する方法の探求については教示していない。
【課題を解決するための手段】
【０００７】
本発明の実施形態は、ＧＦ（２２ｓ）データをＧＦ（（２ｓ）２）表現に変換し、ＧＦ（（２ｓ）２）表現においてＧＦ（２２ｓ）の場合と等価な演算を実行することによって、ＧＦ（２２ｓ）表現で与えられるデータを効率的に操作するための、例えば、ＧＦ（２２ｓ）表現で与えられるデータに関して少なくともいくつかのＡＥＳ暗号化および／または復号化演算を実行するための方法および装置を提供する。
【０００８】
本発明の例示的な実施形態は、拡大ＧＦ（２４）に基づいてＡＥＳ  Ｓボックスを実装する際の根本的な問題、例えば、変換および演算の全体的手順が従来の実装よりも効率的になるように、ＧＦ（２８）表現のデータをＧＦ（（２４）２）表現に効率的に変換しようとする際に特有の問題を解決することができる。
【０００９】
本発明の実施形態によるデータを操作する方法は、ＧＦ（２２ｓ）データをＧＦ（（２ｓ）２）表現の対応するデータに変換するステップを含むことができる。これは、ＧＦ（２２ｓ）データに、ＧＦ（２２ｓ）表現からＧＦ（（２ｓ）２）表現への所定の表現変換に関連する変換演算子を作用させることによって達成することができる。例えば、変換演算子は、線形変換と所定の表現変換の組み合わせを含むことができる。いくつかの実施形態では、変換演算子は、表現変換だけに関連することができる。変換演算子は、所望の変換に対応する表現変換行列を含むことができる。表現変換行列は、例えば、回路実装面積の最小化など、所望の基準に照らして可能性のある表現変換行列の集合から選択することができる。この行列の集合に属する各行列は、２つの体生成元、すなわち、ＧＦ（２２ｓ）表現上の既約多項式の根と、ＧＦ（（２ｓ）２）表現の体生成元によって定義することができる。ＧＦ（（２ｓ）２）表現は、ＧＦ（２ｓ）上の既約簡約多項式と、ＧＦ（２ｓ）上の拡大多項式、例えば、ＧＦ（２ｓ）上の２次の既約多項式とによって定義することができる。
【００１０】
いくつかの実施形態によれば、上記の方法はまた、ＧＦ（（２ｓ）２）データ上で、ＧＦ（２２ｓ）表現での少なくとも１つの所望の演算と等価な少なくとも１つの演算を実行して、処理されたＧＦ（（２ｓ）２）データを取得するステップも含む。この方法はまた、処理されたＧＦ（（２ｓ）２）データを、ＧＦ（２２ｓ）表現に変換し直すステップも含む。これは、処理されたＧＦ（（２ｓ）２）データに、所定の表現変換に関連する逆変換演算子を作用させることによって達成することができる。例えば、逆変換演算子は、線形変換と所定の表現変換の逆変換の組み合わせを含むことができる。
【００１１】
本発明のいくつかの実施形態によれば、表現変換行列を決定するための方法が提供される。この方法は、組み立ておよび／またはシミュレートによって、複数の回路を合成するステップを含むことができ、各回路は、ＧＦ（２２ｓ）表現からＧＦ（（２ｓ）２）表現への表現変換行列、および／またはその表現変換行列の逆行列に対応する。上記の方法はまた、例えば、最小回路面積など、所定の最適化基準に照らして、行列の集合の中から１つを選択するステップも含む。
【００１２】
本発明のいくつかの例示的な実施形態によれば、少なくともいくつかのＡＥＳ  Ｓボックス暗号化演算および／または復号化演算を実行するための方法、システム、および装置が提供される。本発明のいくつかの例示的な実施形態によれば、ＡＥＳ装置によって暗号化および／または復号化されるＧＦ（２８）入力データは、ＧＦ（２８）表現からＧＦ（（２４）２）表現のデータに変換することができる。いくつかの実施形態によれば、変換は、線形変換、および／またはＧＦ（２８）表現からＧＦ（（２４）２）表現への所定の表現変換を含むことができる。ＧＦ（２８）ＡＥＳ暗号化演算および／または復号化演算と等価のＧＦ（２４）演算をＧＦ（（２４）２）上で実行して、処理されたＧＦ（（２４）２）データを取得することができる。処理されたＧＦ（（２４）２）データは、後でＧＦ（２８）表現に変換し直すことができる。これらの実施形態によれば、例えば、データをＧＦ（（２４）２）表現に変換し、等価な暗号化演算／復号化演算を実行し、処理されたデータをＧＦ（２８）表現に変換し直すといった、処理全体のハードウェアによる実施を、ＡＥＳ  Ｓボックスの従来のハードウェア実施よりも著しく効率的にすることができる。
【００１３】
本発明のさらなる例示的な実施形態によれば、ＡＥＳ  Ｓボックスを実施するのに適した安全なメモリ記憶装置が提供される。記憶装置は、記憶されたＧＦ（２８）データをＧＦ（（２４）２）表現に変換するように適合される入力変換モジュールを含むことができる。入力変換モジュールは、復号変換回路と暗号変換回路を含むことができる。記憶装置はさらに、ＧＦ（（２４）２）データ上で演算を実行し、処理されたＧＦ（（２４）２）データを提供するように適合される演算モジュールを含むことができる。演算モジュールによって実行される演算は、ＧＦ（２８）ＡＥＳ暗号化演算／復号化演算と等価なものとすることができる。記憶装置はさらに、処理されたＧＦ（（２４）２）データをＧＦ（２８）表現に変換し直すように適合される出力逆変換モジュールを含むことができる。出力逆変換モジュールは、復号逆変換回路と暗号逆変換回路を含むことができる。
【００１４】
本発明と見なされる主題は、本明細書の結びの部分において詳細に指摘され、明確に特許請求される。しかし、本発明は、その構造および演算方法に関して、さらにその目的、特徴、および利点に関して、以下の詳細な説明を添付の図面と併せて読むことによって、最もよく理解することができるであろう。
【発明を実施するための最良の形態】
【００１５】
簡潔かつ明瞭に図示するため、図に示された要素は、必ずしも正確にまたは実寸比で描かれてはいないことを理解されたい。例えば、明瞭にするため、いくつかの要素の大きさが、その他の要素、または１つの要素に含まれる複数の物理的構成要素に比べて誇張されることがある。さらに、適当と考えられる場合には、同じ参照番号を複数の図で重複して使用して、対応する要素または類似する要素であることを示す。これらの図は、本発明の実施形態の例を提示するものであって、本発明の範囲を限定することを意図したものではないことを理解されたい。
【００１６】
以下の詳細な説明では、本発明を完全に理解できるように、多くの特定の細部について説明する。しかし、それらの特定の細部がなくても本発明を実施できる場合があることは、当業者であれば理解されるであろう。また、本発明が際立たなくなることがないように、よく知られている方法、手順、構成要素については詳しく説明しない。
【００１７】
以下の詳細な説明では、ＧＦ（２２ｓ）という表記は、ｐ（ｔ）を法とするＧＦ（２）上の複数の多項式からなる、ＧＦ（２）の拡大体である位数２２ｓのガロア体（ＧＦ）の表現とする。ただし、ｐ（ｔ）は、ＧＦ（２）上の次数２ｓの既約多項式である。ＧＦ（２２ｓ）表現の多項式は、２ｓ個のビットの列によって表すことができる。ＧＦ（２２ｓ）表現の要素ｘは、２ｓ桁の２進数ｘ＝［ｘ２ｓ−ｌｘ２ｓ−２．．．ｘ１ｘ０］によって定義することができる。ただし、ｘｉは、対応する多項式、例えば、ｘ２ｓ−１ｔ２ｓ−１＋ｘ２ｓ−２ｔ２ｓ−２＋．．．＋ｘ１ｔ＋ｘ０におけるｔｉの係数である。
【００１８】
ＧＦ（（２ｓ）２）という表記は、ｒ（ｔ）を法とするＧＦ（２ｓ）上の複数の多項式からなる、ＧＦ（２ｓ）の拡大体である位数２２ｓのＧＦの表現とする。ただし、ｒ（ｔ）は、ＧＦ（２ｓ）上の次数２の既約多項式であり、すなわち、αとβをＧＦ（２ｓ）の要素とした場合、ｒ（ｔ）＝ｔ２＋αｔ＋βとなる。ＧＦ（２ｓ）は、ｑ（ｔ）を法とするＧＦ（２）上の複数の多項式からなる、ＧＦ（２）の拡大体として表現される。ただし、ｑ（ｔ）は、ＧＦ（２）上の次数ｓの既約多項式である。ＧＦ（（２ｓ）２）表現の要素ｚは、線形多項式ｚ＜ｍ＞ｔ＋ｚ＜ｌ＞を表す、２ｓ桁の２進数ｚ＝［ｚ２ｓ−ｌｚ２ｓ−２．．．ｚ１ｚ０］によって定義することができ、ｚ＜ｍ＞＝［ｚ２ｓ−ｌ．．．ｚｓ＋１ｚｓ］およびｚ＜ｌ＞＝［ｚｓ−ｌ．．．ｚ１ｚ０］は、ｑ（ｔ）を法とする多項式によって表されるＧＦ（２ｓ）の要素である。
【００１９】
本発明の実施形態による、データを操作する方法のフローチャートを概略的に示した図１を参照する。
ブロック１０２に示すように、この方法は、以下で詳しく説明するように、ＧＦ（２２ｓ）データに変換演算子を作用させることによって、ＧＦ（２２ｓ）表現のデータを、ＧＦ（２２ｓ）の拡大に相当するＧＦ（（２ｓ）２）表現の対応するデータに変換するステップを含む。
【００２０】
ブロック１０４に示すように、この方法はまた、以下で詳しく説明するように、ＧＦ（（２ｓ）２）データ上で、ＧＦ（２２ｓ）表現での少なくとも１つの所望の演算と等価な少なくとも１つの演算を実行して、処理されたＧＦ（（２ｓ）２）データを取得するステップを含む。
【００２１】
ブロック１０６に示すように、この方法はさらに、以下で詳しく説明するように、処理されたＧＦ（（２ｓ）２）データを、ＧＦ（２２ｓ）表現に変換し直すステップを含む。
本発明のいくつかの実施形態によれば、ＧＦ（２２ｓ）データは、２以上のデータブロックを含むことができる。これらの実施形態によれば、上記の方法は、２以上のデータブロックで、ＧＦ（２２ｓ）表現での少なくとも１つの所望の演算と等価なＧＦ（（２ｓ）２）表現での少なくとも１つの演算を実行するように実施することができる。
【００２２】
本発明のいくつかの例示的な実施形態によれば、上記の方法は、以下で説明するように、例えば、少なくともいくつかのＡＥＳ  Ｓボックス暗号化演算／復号化演算を実行することによって、入力データの暗号化および／または復号化の一部として使用することができる。
【００２３】
本発明の範囲は上記の点に関して限定されるものではないが、説明を分かりやすくするため、本発明のいくつかの実施形態の説明の一部として、データを暗号化する装置および／または方法に言及することがある。さらに、本発明の実施形態は、データを復号化する装置および／または方法に関しても説明される。しかし、以下で説明される装置および／または方法を、暗号化と復号化の両方、またはそれらの組み合わせ向けにどのように変更できるかは、別段の説明がない限り、当業者には明らかであろう。
【００２４】
本発明のいくつかの例示的な実施形態によれば、ｓは４に等しい。これらの実施形態は、ＧＦ（２８）表現のデータを、ＧＦ（（２４）２）表現の対応するデータに変換するのに役立つ。
【００２５】
本発明の範囲は上記の点に関して限定されるものではないが、説明を分かりやすくするため、本発明のいくつかの例示的な実施形態の説明は、ｓが４に等しい、すなわち、ＧＦ（２８）表現のデータをＧＦ（（２４）２）表現に変換するための方法および／または装置に関する。しかし、ｓがその他の適切な値の場合に、それに合わせて、以下で説明される方法および／または装置をどのように変更したらよいかは、当業者には明らかであろう。本発明のいくつかの実施形態によれば、ｓがある値の場合、ＧＦ（２２ｓ）表現からＧＦ（（２ｓ）２）表現への変換は、以下で説明するように、１つまたは複数の中間変換演算子を利用することによって、段階的にまたは再帰的に実行することができる。
【００２６】
本発明のいくつかの例示的な実施形態によれば、上記の方法は、ｓが４に等しい、少なくともいくつかのＡＥＳ  Ｓボックス暗号化演算を実行するのに使用することができる。これらの実施形態では、暗号化される入力データは、以下で説明するように、拡大ＧＦ表現、例えば、ＧＦ（２８）から、新しい表現、例えば、ＧＦ（２４）の拡大に相当するＧＦ（（２４）２）に変換することができる。これらの実施形態によれば、ＧＦ（２８）での対応するＡＥＳ演算と実質上等価とすることができるＧＦ（２４）演算を、ＧＦ（（２４）２）データ上で実行して、計算の複雑さのレベルを著しく低下させることができる。処理されたデータは、以下で説明するように、後でＡＥＳ  ＧＦ（２８）表現に変換し直すことができる。
【００２７】
本発明のいくつかの実施形態のいくつかの説明は、入力データｘを、ＧＦ（２２ｓ）表現からＧＦ（（２ｓ）２）表現に変換するための、例えば、特定の電気回路を使用する、変換演算子の実装について行われるが、本発明はこの点に関して限定されるものではないことを理解されたい。むしろ、本発明のいくつかの実施形態の一部として、以下で説明される変換演算子、その他の演算、および処理は、例えば、適切なハードウェアおよび／またはソフトウェア実装など、現在知られている実装または将来考案されるであろう実装を含む、その他の様々な実装によっても実施することができる。
【００２８】
本発明のいくつかの実施形態の一部として、上記の方法は、様々な組み合わせおよび適合によって実施することができる。本発明の例示的な実施形態によれば、暗号化を実行する暗号化ブロックおよび／または復号化を実行する復号化ブロックは、例えば、スマートカードで使用できるようなタイプの組み込み電気回路によって実装することができる。データをＡＥＳ  ＧＦ（２８）表現からＧＦ（（２４）２）表現に変換するのに、またその逆に変換するのに使用できる変換演算子は、スマートカードに事前にプログラムしておくことができる。追加的または代替的に、その他の構成を使用することもできる。
【００２９】
本発明のいくつかの例示的な実施形態によれば、変換演算子は、ＧＦ（２２ｓ）表現からＧＦ（（２ｓ）２）表現への表現変換に関するものとすることができる。変換演算子は、表現変換に対応する表現変換行列に関するものとすることができる。表現変換行列は、以下で説明するように、回路実装面積の最小化など、所望の基準に照らして可能性のある表現変換行列の集合から選択することができる。この行列の集合に属する各行列は、ＧＦ（２８）などＧＦ（２２ｓ）表現上の既約多項式の根と、ＧＦ（（２４）２）などＧＦ（（２ｓ）２）表現の体拡大の生成元によって定義することができる。
【００３０】
ＧＦ（２）上のＧＦ（２４）の多項式表現は、ＧＦ（２４）上の３つの既約簡約多項式、例えば、１＋ｔ＋ｔ４、１＋ｔ３＋ｔ４、１＋ｔ＋ｔ２＋ｔ３＋ｔ４の各々によって定義することができる。
【００３１】
本発明の実施形態によれば、ＧＦ（２８）における、ＧＦ（２４）の１つまたは複数の多項式表現の体拡大は、以下で説明するように、既約拡大多項式、例えば、βとαをＧＦ（２４）の要素とした場合、ｔ２＋αｔ＋βがＧＦ（２４）上で既約となるような、ｔ２＋αｔ＋βタイプの多項式を使用して計算することができる。
【００３２】
本発明のいくつかの例示的な実施形態によれば、ｔ２＋αｔ＋β形式の１２０個の可能な既約拡大多項式を与える、１５個の異なるβと、８個の異なるαが存在し得る。３個の異なる簡約多項式と１２０個の既約拡大多項式とから、ＧＦ（２）の拡大であるＧＦ（２８）の３６０個のＧＦ（（２４）２）表現が得られる。
【００３３】
本発明のいくつかの例示的な実施形態によれば、ｔ２＋αｔ＋βタイプの既約拡大多項式の数を削減することができる。この削減は、以下で説明するように、例えば、α＝１であるようなｔ２＋αｔ＋βタイプの既約拡大多項式だけを使用することによって実現することができる。したがって、関連するＧＦ（（２４）２）表現の総数を、３６０個から２４個に削減することができる。しかし、本発明はこの点に関して限定されるものではないことに留意されたい。さらに、本発明のいくつかの実施形態の説明は、α＝１であるようなｔ２＋αｔ＋βタイプの既約拡大多項式を使用するコンテキストに限定されるが、ｔ２＋αｔ＋βタイプの任意の拡大多項式を使用する場合に、そのような方法をどのように適合させたらよいかは当業者には明らかであろう。
【００３４】
したがって、本発明のいくつかの例示的な実施形態の一部として、標準ＡＥＳ表現のデータをＧＦ（（２４）２）表現に変換するために、全部で２４個のＧＦ（（２４）２）表現を計算することができる。２４個のＧＦ（（２４）２）表現は各々、ＧＦ（２４）上の簡約多項式の１つと、例えば、α＝１であるようなｔ２＋αｔ＋βタイプの拡大多項式の１つによって定義することができる。
【００３５】
当技術分野で知られているように、同じサイズの任意の２つの有限体は同型であるので、それぞれＲｅｐ１、Ｒｅｐ２と表記される２つのＧＦ（２ｎ）表現（ｎ＝２ｓ）の間には、同型写像が存在することができる。２つの表現は各々、ＧＦ（２）上のｎ次元線形空間とすることができ、各同型写像は、表現間での線形変換とすることができる。したがって、本発明のいくつかの実施形態の一部として、例えば、行列の乗算によって、Ｒｅｐ１の要素を対応するＲｅｐ２の要素に変換するために、ｎ×ｎ型の２進表現変換行列Ｍを計算することができる。２つの体表現の間の変換は逆変換も可能なので、表現変換毎に逆表現変換行列Ｍ−１が存在することができる。ｎ個の根をもつ既約多項式ｐ０で、Ｒｅｐ１を表すことができる。ｐ０の各根は、ＧＦ（２ｎ）の生成元であり、体の同型写像の下で不変である。したがって、体拡大毎にｎ個の対応する表現変換行列が存在する。ＧＦ（２ｎ）の乗法群は巡回的であるので、表現Ｒｅｐ１とＲｅｐ２の対応する生成元の対は、Ｒｅｐ１とＲｅｐ２の間の同型写像を一意に決定することができる。したがって、Ｒｅｐ１の生成元をｒ１とし、Ｒｅｐ２の生成元をｒ２とした場合、対応する表現変換行列Ｍは、Ｍｒ１＝ｒ２を満たさなければならない。２つの体表現は同型であり、ｒ１とｒ２はＧＦ（２ｎ）の生成元であるので、任意のｋ（ｋ＝１．．．２ｎ）について、以下の連立式がＭによって満たされなければならない。
【００３６】
Ｍ（ｒ１）ｋ＝（ｒ２）ｋ    （１）
ただし、（ｒｉ）ｋは、表現Ｒｅｐｉの要素（ｒ１）ｋを生成するために、表現Ｒｅｐｉにおいてｋ乗された体生成元ｒｉを示し、表現Ｒｅｐ１の体要素（ｒ１）ｋは、ＧＦ（２）上のｎ次元線形空間のベクトルとして扱うことができ、表現変換行列Ｍを乗じて、Ｍ（ｒ１）ｋを得ることができる。
【００３７】
連立式１は、２ｎ個の線形式を含み、それらを解くことによって、生成元ｒ１とｒ２の対に対応する表現変換行列Ｍを決定することができる。連立式１は、冗長な式を含ことがあり、それらを除外することによって、計算の回数を減らすことができる。例えば、１つの表現変換行列を得るのに、最初のｎ個の式だけを使用することができる。別の表現変換行列は、生成元ｒ１とｒ２の異なる対を使用して連立式１を解くことによって得ることができる。したがって、ｒ１の像であるＲｅｐ２のｎ個の異なる生成元に対応し、Ｒｅｐ１からＲｅｐ２へのｎ個の異なる表現変換行列を与える、ｎ組の異なる連立式が存在することができる。
【００３８】
本発明の例示的な実施形態では、ＧＦ（２８）上の既約多項式、例えば、ｐ（ｔ）＝ｔ８＋ｔ４＋ｔ３＋ｔ＋１の各根は、ＧＦ（２８）体の生成元となることができる。したがって、既約多項式の８個の根に対応する８個の可能な表現変換行列を、ＧＦ（２８）の体拡大毎にそれぞれ計算することができる。したがって、これらの例示的な実施形態によれば、α＝１である場合、２４個の体拡大に対応する１９２個の可能な表現変換行列からなる集合が存在することができる。本発明のいくつかの実施形態によれば、可能な表現変換行列の各々は、標準ＡＥＳ表現から、ＧＦ（２４）の異なる拡大に対応する、ＧＦ（２８）の異なるＧＦ（（２４）２）表現への変換を可能にすることができる。
【００３９】
これらの例示的な実施形態によれば、ＡＥＳ表現の入力データｘは、表現変換、例えば、表現変換行列Ｍを作用させることによって、ＧＦ（（２４）２）表現に変換することができる。Ｔ（ｘ）で表される、ＧＦ（（２４）２）表現での演算ｘ＞ｘ−１は、変換データ、例えば、Ｍ  ｘ上で実行することができる。ＧＦ（２８）への変換Ｆ（ｘ）は、表現変換の逆変換、例えば、Ｍ−１を行うことによって得ることができる。したがって、本発明の例示的な実施形態によれば、Ｆ（ｘ）およびＴ（Ｍ  ｘ）は、以下の非線形式によって与えることができる。
【００４０】
Ｆ（ｘ）＝Ｍ−１  Ｔ（Ｍ  ｘ）    （２）
式２は、次のように書き換えることができる。
Ｍ  Ｔ（ｘ）＝Ｆ（Ｍ  ｘ）    （３）
これらの実施形態によれば、式３は、２つの表現、例えば、ＡＥＳ  ＧＦ（２８）表現と対応するＧＦ（（２４）２）表現の間の８個の可能な同型写像を表す、８個の解をもつことができる。２つの表現の間の同型写像は、以下で説明するように、一方の表現から、他方の表現の特定の生成元に写像される生成元を選択することによって決定することができる。
【００４１】
以下に、１６進形式で示された、１９２（２４×８）個の可能な表現変換行列に対応する行列ストリング（ｍａｔｒｉｘ  ｓｔｒｉｎｇ）の例示的なリストを示す。これらは、上で説明したようにして計算することができる。
簡約多項式：ｔ４＋ｔ＋１
（ａ）拡大多項式：ｔ２＋ｔ＋８
０１  ｅ１  ５ｃ  ０ｃ  ａｆ  １ｂ  ｅ３  ８５，  ０１  ｅ１  ５ｃ  ０ｃ  ａｅ  ｆａ  ｂｆ  ８９，  ０１  ５ｃ  ｅ０  ５０  ａ２  ０２  ｂ８  ｄｂ，  ０１  ５ｃ  ｅ０  ５０  ａ３  ５ｅ  ５８  ８ｂ，  ０１  ｅ０  ５ｄ  ｂ０  ｆ２  ０４  ａｄ  ６ｆ，  ０１  ｅ０  ５ｄ  ｂ０  ｆ３  ｅ４  ｆ０  ｄｆ，  ０１  ５ｄ  ｅ１  ｅｄ  ４２  １０  ａ７  ９２，  ０１  ５ｄ  ｅ１  ｅｄ  ４３  ４ｄ  ４６  ７ｆ
（ｂ）拡大多項式：ｔ２＋ｔ＋９
０１  ｅ１  ５ｃ  ０ｃ  １２  ４ｂ  ０ｆ  ｄ８，  ０１  ｅ１  ５ｃ  ０ｃ  １３  ａａ  ５３  ｄ４，  ０１  ５ｃ  ｅ０  ５０  １ｅ  ｂ２  ｂ５  ３ａ，  ０１  ５ｃ  ｅ０  ５０  １ｆ  ｅｅ  ５５  ６ａ，  ０１  ｅ０  ５ｄ  ｂ０  ４ｅ  ０９  ａ１  ８３，  ０１  ｅ０  ５ｄ  ｂ０  ４ｆ  ｅ９  ｆｃ  ３３，  ０１  ５ｄ  ｅ１  ｅｄ  ｆｅ  １ｃ  １６  ７２，  ０１  ５ｄ  ｅ１  ｅｄ  ｆｆ  ４１  ｆ７  ９ｆ
（ｃ）拡大多項式：ｔ２＋ｔ＋１０
０１  ｅ１  ５ｃ  ０ｃ  ４３  ４６  ０ｅ  ３９，  ０１  ｅ１  ５ｃ  ０ｃ  ４２  ａ７  ５２  ３５，  ０１  ５ｃ  ｅ０  ５０  ａｅ  ｂｆ  ５４  ３６，  ０１  ５ｃ  ｅ０  ５０  ａｆ  ｅ３  ｂ４  ６６，  ０１  ｅ０  ５ｄ  ｂ０  ａ３  ５８  ｆｄ  ｄ３，  ０１  ｅ０  ５ｄ  ｂ０  ａ２  ｂ８  ａ０  ６３，  ０１  ５ｄ  ｅ１  ｅｄ  ｆ２  ａｄ  ｆ６  ｃ２，  ０１  ５ｄ  ｅ１  ｅｄ  ｆ３  ｆ０  １７  ２ｆ
（ｄ）拡大多項式：ｔ２＋ｔ＋１１
０１  ｅ１  ５ｃ  ０ｃ  ｆｅ  １６  ｅ２  ６４，  ０１  ｅ１  ５ｃ  ０ｃ  ｆｆ  ｆ７  ｂｅ  ６８，  ０１  ５ｃ  ｅ０  ５０  １２  ０ｆ  ５９  ｄ７，  ０１  ５ｃ  ｅ０  ５０  １３  ５３  ｂ９  ８７，  ０１  ｅ０  ５ｄ  ｂ０  １ｆ  ５５  ｆ１  ３ｆ，  ０１  ｅ０  ５ｄ  ｂ０  １ｅ  ｂ５  ａｃ  ８ｆ，  ０１  ５ｄ  ｅ１  ｅｄ  ４ｅ  ａ１  ４７  ２２，  ０１  ５ｄ  ｅ１  ｅｄ  ４ｆ  ｆｃ  ａ６  ｃｆ
（ｅ）拡大多項式：ｔ２＋ｔ＋１２
０１  ｅ１  ５ｃ  ０ｃ  ａ２  １ａ  ０２  ｄ９，  ０１  ｅ１  ５ｃ  ０ｃ  ａ３  ｆｂ  ５ｅ  ｄ５，  ０１  ５ｃ  ｅ０  ５０  ｆ３  ０３  ｅ４  ３ｂ，  ０１  ５ｃ  ｅ０  ５０  ｆ２  ５ｆ  ０４  ６ｂ，  ０１  ｅ０  ５ｄ  ｂ０  ４３  ０５  ４ｄ  ３２，  ０１  ｅ０  ５ｄ  ｂ０  ４２  ｅ５  １０  ８２，  ０１  ５ｄ  ｅ１  ｅｄ  ａｅ  １１  ｆａ  ７３，  ０１  ５ｄ  ｅ１  ｅｄ  ａｆ  ４ｃ  １ｂ  ９ｅ
（ｆ）拡大多項式：ｔ２＋ｔ＋１３
０１  ｅ１  ５ｃ  ０ｃ  １ｆ  ４ａ  ｅｅ  ８４，  ０１  ｅ１  ５ｃ  ０ｃ  １ｅ  ａｂ  ｂ２  ８８，  ０１  ５ｃ  ｅ０  ５０  ４ｆ  ｂ３  ｅ９  ｄａ，  ０１  ５ｃ  ｅ０  ５０  ４ｅ  ｅｆ  ０９  ８ａ，  ０１  ｅ０  ５ｄ  ｂ０  ｆｆ  ０８  ４１  ｄｅ，  ０１  ｅ０  ５ｄ  ｂ０  ｆｅ  ｅ８  １ｃ  ６ｅ，  ０１  ５ｄ  ｅ１  ｅｄ  １２  １ｄ  ４ｂ  ９３，  ０１  ５ｄ  ｅ１  ｅｄ  １３  ４０  ａａ  ７ｅ
（ｇ）拡大多項式：ｔ２＋ｔ＋１４
０１  ｅ１  ５ｃ  ０ｃ  ４ｅ  ４７  ｅｆ  ６５，  ０１  ｅ１  ５ｃ  ０ｃ  ４ｆ  ａ６  ｂ３  ６９，  ０１  ５ｃ  ｅ０  ５０  ｆｆ  ｂｅ  ０８  ｄ６，  ０１  ５ｃ  ｅ０  ５０  ｆｅ  ｅ２  ｅ８  ８６，  ０１  ｅ０  ５ｄ  ｂ０  １２  ５９  １ｄ  ８ｅ，  ０１  ｅ０  ５ｄ  ｂ０  １３  ｂ９  ４０  ３ｅ，  ０１  ５ｄ  ｅ１  ｅｄ  １ｅ  ａｃ  ａｂ  ２３，  ０１  ５ｄ  ｅ１  ｅｄ  １ｆ  ｆ１  ４ａ  ｃｅ
（ｈ）拡大多項式：ｔ２＋ｔ＋１５
０１  ｅ１  ５ｃ  ０ｃ  ｆ３  １７  ０３  ３８，  ０１  ｅ１  ５ｃ  ０ｃ  ｆ２  ｆ６  ５ｆ  ３４，  ０１  ５ｃ  ｅ０  ５０  ４３  ０ｅ  ０５  ３７，  ０１  ５ｃ  ｅ０  ５０  ４２  ５２  ｅ５  ６７，  ０１  ｅ０  ５ｄ  ｂ０  ａｅ  ５４  １１  ６２，  ０１  ｅ０  ５ｄ  ｂ０  ａｆ  ｂ４  ４ｃ  ｄ２，  ０１  ５ｄ  ｅ１  ｅｄ  ａ２  ａ０  １ａ  ｃ３，  ０１  ５ｄ  ｅ１  ｅｄ  ａ３  ｆｄ  ｆｂ  ２ｅ
簡約多項式：ｔ４＋ｔ３＋１
（ａ）拡大多項式：ｔ２＋ｔ＋２
０１  ｂ１  ｅｃ  ０ｃ  ４ｆ  ７ｃ  ８０  ６９，  ０１  ｂ１  ｅｃ  ０ｃ  ４ｅ  ｃｄ  ６ｃ  ６５，  ０１  ｅｃ  ０ｄ  ５０  ｆｆ  ６０  ９７  ｄ６，  ０１  ｅｃ  ０ｄ  ５０  ｆｅ  ８ｃ  ９ａ  ８６，  ０１  ０ｄ  ５１  ｂ０  １３  ｃ７  ９４  ３ｅ，  ０１  ０ｄ  ５１  ｂ０  １２  ｃａ  ｃ５  ８ｅ，  ０１  ５１  ｂ１  ｅｄ  １ｅ  ２４  ９１  ２３，  ０１  ５１  ｂ１  ｅｄ  １ｆ  ７５  ２０  ｃｅ
（ｂ）拡大多項式：ｔ２＋ｔ＋３
０１  ｂ１  ｅｃ  ０ｃ  ｆ３  ２ｃ  ｄｃ  ３８，  ０１  ｂ１  ｅｃ  ０ｃ  ｆ２  ９ｄ  ３０  ３４，  ０１  ｅｃ  ０ｄ  ５０  ４３  ３ｃ  ７ａ  ３７，  ０１  ｅｃ  ０ｄ  ５０  ４２  ｄ０  ７７  ６７，  ０１  ０ｄ  ５１  ｂ０  ａｅ  ２７  ９８  ６２，  ０１  ０ｄ  ５１  ｂ０  ａｆ  ２ａ  ｃ９  ｄ２，  ０１  ５１  ｂ１  ｅｄ  ａ３  ２８  ７０  ２ｅ，  ０１  ５１  ｂ１  ｅｄ  ａ２  ７９  ｃ１  ｃ３
（ｃ）拡大多項式：ｔ２＋ｔ＋４
０１  ｂ１  ｅｃ  ０ｃ  ｆｆ  ２１  ６０  ６８，  ０１  ｂ１  ｅｃ  ０ｃ  ｆｅ  ９０  ８ｃ  ６４，  ０１  ｅｃ  ０ｄ  ５０  １３  ６ｄ  ｃ７  ８７，  ０１  ｅｃ  ０ｄ  ５０  １２  ８１  ｃａ  ｄ７，  ０１  ０ｄ  ５１  ｂ０  １ｅ  ９６  ２４  ８ｆ，  ０１  ０ｄ  ５１  ｂ０  １ｆ  ９ｂ  ７５  ３ｆ，  ０１  ５１  ｂ１  ｅｄ  ４ｆ  ９５  ７ｃ  ｃｆ，  ０１  ５１  ｂ１  ｅｄ  ４ｅ  ｃ４  ｃｄ  ２２
（ｄ）拡大多項式：ｔ２＋ｔ＋５
０１  ｂ１  ｅｃ  ０ｃ  ４３  ７１  ３ｃ  ３９，  ０１  ｂ１  ｅｃ  ０ｃ  ４２  ｃ０  ｄ０  ３５，  ０１  ｅｃ  ０ｄ  ５０  ａｆ  ３１  ２ａ  ６６，  ０１  ｅｃ  ０ｄ  ５０  ａｅ  ｄｄ  ２７  ３６，  ０１  ０ｄ  ５１  ｂ０  ａ３  ７６  ２８  ｄ３，  ０１  ０ｄ  ５１  ｂ０  ａ２  ７ｂ  ７９  ６３，  ０１  ５１  ｂ１  ｅｄ  ｆ２  ９９  ９ｄ  ｃ２，  ０１  ５１  ｂ１  ｅｄ  ｆ３  ｃ８  ２ｃ  ２ｆ
（ｅ）拡大多項式：ｔ２＋ｔ＋８
０１  ｂ１  ｅｃ  ０ｃ  ａｆ  ７ｄ  ３１  ８５，  ０１  ｂ１  ｅｃ  ０ｃ  ａｅ  ｃｃ  ｄｄ  ８９，  ０１  ｅｃ  ０ｄ  ５０  ａ２  ６１  ７ｂ  ｄｂ，  ０１  ｅｃ  ０ｄ  ５０  ａ３  ８ｄ  ７６  ８ｂ，  ０１  ０ｄ  ５１  ｂ０  ｆ２  ｃ６  ９９  ６ｆ，  ０１  ０ｄ  ５１  ｂ０  ｆ３  ｃｂ  ｃ８  ｄｆ，  ０１  ５１  ｂ１  ｅｄ  ４２  ２５  ｃ０  ９２，  ０１  ５１  ｂ１  ｅｄ  ４３  ７４  ７１  ７ｆ
（ｆ）拡大多項式：ｔ２＋ｔ＋９
０１  ｂ１  ｅｃ  ０ｃ  １３  ２ｄ  ６ｄ  ｄ４，  ０１  ｂ１  ｅｃ  ０ｃ  １２  ９ｃ  ８１  ｄ８，  ０１  ｅｃ  ０ｄ  ５０  １ｅ  ３ｄ  ９６  ３ａ，  ０１  ｅｃ  ０ｄ  ５０  １ｆ  ｄ１  ９ｂ  ６ａ，  ０１  ０ｄ  ５１  ｂ０  ４ｆ  ２６  ９５  ３３，  ０１  ０ｄ  ５１  ｂ０  ４ｅ  ２ｂ  ｃ４  ８３，  ０１  ５１  ｂ１  ｅｄ  ｆｆ  ２９  ２１  ９ｆ，  ０１  ５１  ｂ１  ｅｄ  ｆｅ  ７８  ９０  ７２
（ｇ）拡大多項式：ｔ２＋ｔ＋１４
０１  ｂ１  ｅｃ  ０ｃ  １ｆ  ２０  ｄ１  ８４，  ０１  ｂ１  ｅｃ  ０ｃ  １ｅ  ９１  ３ｄ  ８８，  ０１  ｅｃ  ０ｄ  ５０  ４ｅ  ６ｃ  ２ｂ  ８ａ，  ０１  ｅｃ  ０ｄ  ５０  ４ｆ  ８０  ２６  ｄａ，  ０１  ０ｄ  ５１  ｂ０  ｆｆ  ９７  ２９  ｄｅ，  ０１  ０ｄ  ５１  ｂ０  ｆｅ  ９ａ  ７８  ６ｅ，  ０１  ５１  ｂ１  ｅｄ  １３  ９４  ２ｄ  ７ｅ，  ０１  ５１  ｂ１  ｅｄ  １２  ｃ５  ９ｃ  ９３
（ｈ）拡大多項式：ｔ２＋ｔ＋１５
０１  ｂ１  ｅｃ  ０ｃ  ａ３  ７０  ８ｄ  ｄ５，  ０１  ｂ１  ｅｃ  ０ｃ  ａ２  ｃ１  ６１  ｄ９，  ０１  ｅｃ  ０ｄ  ５０  ｆ２  ３０  ｃ６  ６ｂ，  ０１  ｅｃ  ０ｄ  ５０  ｆ３  ｄｃ  ｃｂ  ３ｂ，  ０１  ０ｄ  ５１  ｂ０  ４２  ７７  ２５  ８２，  ０１  ０ｄ  ５１  ｂ０  ４３  ７ａ  ７４  ３２，  ０１  ５１  ｂ１  ｅｄ  ａｅ  ９８  ｃｃ  ７３，  ０１  ５１  ｂ１  ｅｄ  ａｆ  ｃ９  ７ｄ  ９ｅ
簡約多項式：ｔ４＋ｔ３＋ｔ２＋ｔ＋１
（ａ）拡大多項式：ｔ２＋ｔ＋２
０１  ５０  ｂ０  ０ｃ  ａ３  ８ｂ  ｄ３  ｄ５，  ０１  ５０  ｂ０  ０ｃ  ａ２  ｄｂ  ６３  ｄ９，  ０１  ｂ０  ｅｄ  ５０  ｆ２  ６ｆ  ｃ２  ６ｂ，  ０１  ｂ０  ｅｄ  ５０  ｆ３  ｄｆ  ２ｆ  ３ｂ，  ０１  ｅｄ  ０ｃ  ｂ０  ４３  ７ｆ  ３９  ３２，  ０１  ｅｄ  ０ｃ  ｂ０  ４２  ９２  ３５  ８２，  ０１  ０ｃ  ５０  ｅｄ  ａｆ  ８５  ６６  ９ｅ，  ０１  ０ｃ  ５０  ｅｄ  ａｅ  ８９  ３６  ７３
（ｂ）拡大多項式：ｔ２＋ｔ＋３
０１  ５０  ｂ０  ０ｃ  １ｅ  ３ａ  ８ｆ  ８８，  ０１  ５０  ｂ０  ０ｃ  １ｆ  ６ａ  ３ｆ  ８４，  ０１  ｂ０  ｅｄ  ５０  ４ｆ  ３３  ｃｆ  ｄａ，  ０１  ｂ０  ｅｄ  ５０  ４ｅ  ８３  ２２  ８ａ，  ０１  ｅｄ  ０ｃ  ｂ０  ｆｅ  ７２  ６４  ６ｅ，  ０１  ｅｄ  ０ｃ  ｂ０  ｆｆ  ９ｆ  ６８  ｄｅ，  ０１  ０ｃ  ５０  ｅｄ  １３  ｄ４  ８７  ７ｅ，  ０１  ０ｃ  ５０  ｅｄ  １２  ｄ８  ｄ７  ９３
（ｃ）拡大多項式：ｔ２＋ｔ＋４
０１  ５０  ｂ０  ０ｃ  ｆ３  ３ｂ  ｄｆ  ３８，  ０１  ５０  ｂ０  ０ｃ  ｆ２  ６ｂ  ６ｆ  ３４，  ０１  ｂ０  ｅｄ  ５０  ４３  ３２  ７ｆ  ３７，  ０１  ｂ０  ｅｄ  ５０  ４２  ８２  ９２  ６７，  ０１  ｅｄ  ０ｃ  ｂ０  ａｅ  ７３  ８９  ６２，  ０１  ｅｄ  ０ｃ  ｂ０  ａｆ  ９ｅ  ８５  ｄ２，  ０１  ０ｃ  ５０  ｅｄ  ａ３  ｄ５  ８ｂ  ２ｅ，  ０１  ０ｃ  ５０  ｅｄ  ａ２  ｄ９  ｄｂ  ｃ３
（ｄ）拡大多項式：ｔ２＋ｔ＋５
０１  ５０  ｂ０  ０ｃ  ４ｅ  ８ａ  ８３  ６５，  ０１  ５０  ｂ０  ０ｃ  ４ｆ  ｄａ  ３３  ６９，  ０１  ｂ０  ｅｄ  ５０  ｆｅ  ６ｅ  ７２  ８６，  ０１  ｂ０  ｅｄ  ５０  ｆｆ  ｄｅ  ９ｆ  ｄ６，  ０１  ｅｄ  ０ｃ  ｂ０  １３  ７ｅ  ｄ４  ３ｅ，  ０１  ｅｄ  ０ｃ  ｂ０  １２  ９３  ｄ８  ８ｅ，  ０１  ０ｃ  ５０  ｅｄ  １ｆ  ８４  ６ａ  ｃｅ，  ０１  ０ｃ  ５０  ｅｄ  １ｅ  ８８  ３ａ  ２３
（ｅ）拡大多項式：ｔ２＋ｔ＋８
０１  ５０  ｂ０  ０ｃ  ａｅ  ３６  ６２  ８９，  ０１  ５０  ｂ０  ０ｃ  ａｆ  ６６  ｄ２  ８５，  ０１  ｂ０  ｅｄ  ５０  ａ２  ６３  ｃ３  ｄｂ，  ０１  ｂ０  ｅｄ  ５０  ａ３  ｄ３  ２ｅ  ８ｂ，  ０１  ｅｄ  ０ｃ  ｂ０  ｆ３  ２ｆ  ３８  ｄｆ，  ０１  ｅｄ  ０ｃ  ｂ０  ｆ２  ｃ２  ３４  ６ｆ，  ０１  ０ｃ  ５０  ｅｄ  ４２  ３５  ６７  ９２，  ０１  ０ｃ  ５０  ｅｄ  ４３  ３９  ３７  ７ｆ
（ｆ）拡大多項式：ｔ２＋ｔ＋９
０１  ５０  ｂ０  ０ｃ  １３  ８７  ３ｅ  ｄ４，  ０１  ５０  ｂ０  ０ｃ  １２  ｄ７  ８ｅ  ｄ８，  ０１  ｂ０  ｅｄ  ５０  １ｆ  ３ｆ  ｃｅ  ６ａ，  ０１  ｂ０  ｅｄ  ５０  １ｅ  ８ｆ  ２３  ３ａ，  ０１  ｅｄ  ０ｃ  ｂ０  ４ｅ  ２２  ６５  ８３，  ０１  ｅｄ  ０ｃ  ｂ０  ４ｆ  ｃｆ  ６９  ３３，  ０１  ０ｃ  ５０  ｅｄ  ｆｅ  ６４  ８６  ７２，  ０１  ０ｃ  ５０  ｅｄ  ｆｆ  ６８  ｄ６  ９ｆ
（ｇ）拡大多項式：ｔ２＋ｔ＋１４
０１  ５０  ｂ０  ０ｃ  ｆｅ  ８６  ６ｅ  ６４，  ０１  ５０  ｂ０  ０ｃ  ｆｆ  ｄ６  ｄｅ  ６８，  ０１  ｂ０  ｅｄ  ５０  １３  ３ｅ  ７ｅ  ８７，  ０１  ｂ０  ｅｄ  ５０  １２  ８ｅ  ９３  ｄ７，  ０１  ｅｄ  ０ｃ  ｂ０  １ｅ  ２３  ８８  ８ｆ，  ０１  ｅｄ  ０ｃ  ｂ０  １ｆ  ｃｅ  ８４  ３ｆ，  ０１  ０ｃ  ５０  ｅｄ  ４ｅ  ６５  ８ａ  ２２，  ０１  ０ｃ  ５０  ｅｄ  ４ｆ  ６９  ｄａ  ｃｆ
（ｈ）拡大多項式：ｔ２＋ｔ＋１５
０１  ５０  ｂ０  ０ｃ  ４３  ３７  ３２  ３９，  ０１  ５０  ｂ０  ０ｃ  ４２  ６７  ８２  ３５，  ０１  ｂ０  ｅｄ  ５０  ａｅ  ６２  ７３  ３６，  ０１  ｂ０  ｅｄ  ５０  ａｆ  ｄ２  ９ｅ  ６６，  ０１  ｅｄ  ０ｃ  ｂ０  ａ３  ２ｅ  ｄ５  ｄ３，  ０１  ｅｄ  ０ｃ  ｂ０  ａ２  ｃ３  ｄ９  ６３，  ０１  ０ｃ  ５０  ｅｄ  ｆ２  ３４  ６ｂ  ｃ２，  ０１  ０ｃ  ５０  ｅｄ  ｆ３  ３８  ３ｂ  ２ｆ
上記のリストは、８個の行列ストリング値からなる各グループが、上で説明したように、ｔ２＋αｔ＋βタイプの拡大多項式の１つと、ＧＦ（２４）上の３つの既約簡約多項式の１つとに関連づけられるように構成される。行列ストリング値は、１６進形式の８対の値の形で列挙され、８×８型の２進行列を表す。ｉ番目（１≦ｉ≦１９２）の表現変換行列Ｍに対応する値をリスト中から見つけるため、以下の連立式を解くことができる。
【００４２】
ｉ−１＝Ｑ１×６４＋Ｒ１    （４）
Ｒ１＝Ｑ２×８＋Ｒ２
ただし、
０≦Ｒ１≦６４    （５）
０≦Ｒ２＜８
連立式（５）の境界条件をもつ連立式（４）から、所望のｉ番目の表現変換行列に対応する値Ｑ１、Ｑ２、Ｒ１、Ｒ２の組を得ることができる。所望の表現変換行列、例えば、ｉ番目の行列の上記のリスト中の位置は、Ｑ１＋１番目の簡約多項式の中の、Ｑ２＋１番目の拡大多項式の中の、Ｒ２＋１番目の行列ストリングとして求めることができる。行列ストリング値は、行列ストリングを１６進形式の数の対に分割することによって、変換行列表現に変換することができる。その場合、変換行列の各列は、対応する１６進対の２進表現、例えば、８桁の２進数を使用して表すことができる。
【００４３】
本発明のいくつかの実施形態は、ＡＥＳ互換Ｓボックスを含む。ＡＥＳ互換Ｓボックスは、ＡＥＳ  Ｓボックスと等価な演算、例えば、ＧＦ（（２ｓ）２）上の暗号化演算および／または復号化演算を実行するように構成することができる。ＡＥＳ互換Ｓボックスは、上で説明したように、例えば、標準ＡＥＳ  Ｓボックス上の表現からＧＦ（（２ｓ）２）表現へのデータ変換を可能にする変換回路を含むことができる。ＡＥＳ互換Ｓボックスはまた、演算モジュールを含むことができ、演算モジュールは、例えば、変換データ上でＡＥＳ等価な演算を実行するなど、変換データを処理するための演算回路および／またはソフトウェアを含むことができる。ＡＥＳ互換Ｓボックスはまた、処理されたデータをＡＥＳ表現に変換し直すための逆変換回路を含むことができる。
【００４４】
従来のＡＥＳ  Ｓボックスは、以下の式に基づいたアフィン変換を実行することができる。
【００４５】
【数１】
2005534973.tif 000003
【００４６】
ただし、Ａおよびｂは、当技術分野で知られているＡＥＳ  Ｓボックスパラメータ行列である。
【００４７】
したがって、本発明の実施形態によれば、式３を式６および７にそれぞれ代入することによって、ｘをＧＦ（（２ｓ）２）表現に変換し、ＧＦ（（２ｓ）２）表現で演算を実行し、その結果のデータをＡＥＳ表現の対応するデータに変換し直すための以下の式を得ることができる。
【００４８】
【数２】
2005534973.tif 000004
【００４９】
本発明のいくつかの実施形態によれば、変換回路またはソフトウェアは、表現変換行列Ｍを実装する回路を含むことができる。これらの実施形態のいくつかによれば、表現変換行列Ｍを実装する回路またはソフトウェアは、例えば、ＡなどのＡＥＳ  Ｓボックスパラメータなど、線形変換を実行する回路またはソフトウェアと合成することができる。本発明のさらなる実施形態によれば、変換回路またはソフトウェアは、例えば、以下で説明するような、Ｍ、ＡＭ、Ｍ−１、（ＡＭ−１）によるそれぞれの乗算用に４つの乗算モジュールを含むことができる。したがって、変換回路は、線形変換と所定の表現変換を組み合わせて用いることによって構成することができる。例えば、変換回路は、ＡＥＳ  Ｓボックスパラメータｂの加算を、例えば、ＸＯＲ回路によって実行して、和ｘ＋ｂを得ることができ、それにさらにＡＭの逆行列を乗じることができる。変換回路は、例えば、本明細書で説明する特定の実装など、線形変換と表現変換行列のその他の組み合わせを実装することもできる。そのような演算モジュールを使用することによって変換回路の効率を高めることができる。
【００５０】
行列の乗算のハードウェアによる実施は、当技術分野で知られている行列の乗算のどのようなハードウェアによる実施でも含むことができる。例えば、ｉ＝１．．．８とし、Ｄを固定の８×８型の２進行列とした場合、ｙ＝Ｄｘで定義されるブロックｙの値ｙｉは、以下の式を使用して計算することができる。
【００５１】
【数３】
2005534973.tif 000005
【００５２】
したがって、ｙの値は、式１０を使用して計算することができる。これは、行Ｄｉ，ｊのどの要素が非０であるかを決定し、ｘｊの対応する値とＸＯＲ演算を実行することによって達成することができる。
【００５３】
本発明の例示的な実施形態によれば、以下で説明するように、ＡＥＳ演算と等価な、例えば、逆演算、加算、および／または乗算などの演算を、新しい表現において定義することができる。
【００５４】
ＧＦ（２８）の要素ｘは、８桁の２進数ｘ＝［ｘ７ｘ６ｘ５ｘ４ｘ３ｘ２ｘ１ｘ０］によって定義することができ、ＧＦ（２４）の要素ｚは、４桁の２進数ｚ＝［ｚ３ｚ２ｚ１ｚ０］によって定義することができる。
【００５５】
当技術分野で知られているように、ＧＦ（２４）は、ＧＦ（２）上の簡約多項式によって定義される多項式表現をもち、例えば、ｚ＝［ｚ３ｚ２ｚ１ｚ０］は、多項式ｚ０＋ｚ１ｔ＋ｚ２ｔ２＋ｚ３ｔ３によって表すことができる。ＧＦの要素の乗算は、要素を表す多項式を掛け合わせ、その結果を簡約多項式を法として簡約することによって定義することができる。以下の説明では、ＡＥＳ  ＧＦ（２８）でのｘの逆演算ｘ−１をＦ＝Ｆ（ｘ）と表記し、新しい表現でのｚの逆演算ｚ−１をＴ＝Ｔ（ｚ）と表記することができる。
【００５６】
本発明の実施形態によれば、ＧＦ（２８）のビットオクテットｚ＝［ｚ７ｚ６ｚ５ｚ４ｚ３ｚ２ｚ１ｚ０］は、ｚ＜ｍ＞＝［ｚ７ｚ６ｚ５ｚ４］およびｚ＜ｌ＞＝［ｚ３ｚ２ｚ１ｚ０］をＧＦ（２４）の要素とした場合、線形多項式ｚ＜ｍ＞ｔ＋ｚ＜ｌ＞と類似することができる。したがって、新しい表現は、ＧＦ（２４）の要素ｚ＜ｍ＞とｚ＜ｌ＞を含むことができる。
【００５７】
本発明のいくつかの実施形態の一部として、新しい表現での乗算および加算は、ＧＦ（２４）上の演算によって定義することができる。以下に、新しい表現での乗算および加算のＧＦ（２４）上の演算による１つの可能な定義を提供する。本発明のいくつかの実施形態の一部として、その他の定義も使用できることは理解されよう。
【００５８】
２つの要素、例えば、ａ，ｄ∈ＧＦ（２８）の新しい表現での加算および減算は、当技術分野で知られているように、２つの要素のビット毎のＸＯＲとして定義することができる。２つの要素ａとｄの積は、（ｔ２＋αｔ＋β）を法とする多項式の積（ａ＜ｍ＞ｔ＋ａ＜ｌ＞）×（ｄ＜ｍ＞ｔ＋ｄ＜ｌ＞）によって定義することができる。ただし、多項式の係数の乗算および加算は、与えられた表現を使用するＧＦ（２４）上の演算によって定義することができる。したがって、要素ａとｄの積は、以下の式を使用して計算することができる。
【００５９】
【数４】
2005534973.tif 000006
【００６０】
ただし、
【００６１】
【数５】
2005534973.tif 000007
【００６２】
したがって、ＡＥＳ  ＧＦ（２８）の要素ａとｄの積は、ｒ＝［ｒ７ｒ６ｒ５ｒ４ｒ３ｒ２ｒ１ｒ０］として定義することができる。
【００６３】
データ要素ｘ＝（ａ＜ｍ＞ｔ＋ａ＜ｌ＞）の逆元ｘ−１＝（ｃ＜ｍ＞ｔ＋ｃ＜ｌ＞）を決定するには、（ｘ＜ｍ＞ｘ＋ｘ＜ｌ＞）が以下の式を満たす必要がある。
【００６４】
【数６】
2005534973.tif 000008
【００６５】
式１３は、ＧＦ（２）上の以下の連立線形式に変換することができる。
【００６６】
【数７】
2005534973.tif 000009
【００６７】
したがって、データ要素ｘの逆元ｘ−１を計算するには、上で説明したように、Ｃ＜ｍ＞およびＣ＜ｌ＞を計算すればよい。
【００６８】
本発明の実施形態によれば、連立式１４を直接計算するには、２つの平方計算、例えば、ａ２＜ｍ＞およびａ２＜ｌ＞、５つの乗算、１つの逆演算、および３つの加算を、すべてＧＦ（２４）上で行う必要がある。しかし、本発明のいくつかの実施形態の一部として、これらの計算の回数は、以下で説明するように、減らすことができる。
【００６９】
本発明の実施形態によれば、ＧＦ（２４）上の加算は、当技術分野で知られているように、ＸＯＲ回路として実装することができる。本発明の他の実施形態によれば、ＧＦ（２４）上の乗算は、以下で説明するように、複数のＧＦ（２４）乗算器を定義し、場合毎に適切な乗算器を選択することによって、より効率的に実行することができる。
【００７０】
これらの例示的な実施形態によれば、ＧＦ（２４）の２つの要素、例えば、ａ＝［ａ３，ａ２，ａ１，ａ０］とｄ＝［ｄ３，ｄ２，ｄ１，ｄ０］の、ＧＦ（２４）上の乗算ａ×ｄ＝［ａ３，ａ２，ａ１，ａ０］×［ｄ３，ｄ２，ｄ１，ｄ０］は、例えば、上で説明したように、与えられた簡約多項式別に、例えば、加算（ＸＯＲ）および乗算（ＡＮＤ）など、一連のビット毎の演算として定義することができる。したがって、２つの要素の乗算の計算法は、以下のようになる。
簡約多項式：ｔ４＋ｔ＋１
［ａ３，ａ２，ａ１，ａ０］×［ｄ３，ｄ２，ｄ１，ｄ０］＝
［ａ１ｄ２＋ａ３ｄ３＋ａ３ｄ０＋ａ２ｄ１＋ａ０ｄ３，ａ２ｄ３＋ａ０ｄ２＋ａ３ｄ３＋ａ２ｄ０＋ａ１ｄ１＋ｄ２ａ３，ａ１ｄ３＋ｄ２ａ３＋ａ０ｄ１＋ａ２ｄ２＋ａ２ｄ３＋ａ１ｄ０＋ａ３ｄ１，ａ０ｄ０＋ａ１ｄ３＋ａ２ｄ２＋ａ３ｄ１］
簡約多項式：ｔ４＋ｔ３＋１
［ａ３，ａ２，ａ１，ａ０］×［ｄ３，ｄ２，ｄ１，ｄ０］＝
［ａ０ｄ３＋ａ１ｄ３＋ａ３ｄ２＋ａ２ｄ３＋ａ３ｄ１＋ａ２ｄ１＋ａ１ｄ２＋ａ３ｄ３＋ａ３ｄ０＋ａ２ｄ２，ａ０ｄ２＋ａ３ｄ３＋ａ１ｄ１＋ａ２ｄ０，ａ０ｄ１＋ａ３ｄ２＋ａ３ｄ３＋ａ１ｄ０＋ａ２ｄ３，ａ１ｄ３＋ａ０ｄ０＋ａ２ｄ３＋ａ３ｄ２＋ａ２ｄ２＋ａ３ｄ１＋ａ３ｄ３］
簡約多項式：ｔ４＋ｔ３＋ｔ２＋ｔ＋１
［ａ３，ａ２，ａ１，ａ０］×［ｄ３，ｄ２，ｄ１，ｄ０］＝
［ａ２ｄ１＋ａ３ｄ０＋ａ３ｄ１＋ａ１ｄ２＋ａ１ｄ３＋ａ２ｄ２＋ａ０ｄ３，ａ３ｄ１＋ａ２ｄ２＋ａ１ｄ１＋ａ２ｄ０＋ａ０ｄ２＋ａ１ｄ３，ａ０ｄ１＋ａ１ｄ３＋ａ１ｄ０＋ａ３ｄ１＋ａ３ｄ３＋ａ２ｄ２，ａ３ｄ２＋ａ１ｄ３＋ａ０ｄ０＋ａ２ｄ３＋ａ２ｄ２＋ａ３ｄ１］
上記の各計算法において、要素の乗算の一部は、２以上の出力ビットで同じであることに留意されたい。例えば、ａ１ｄ３＋ａ２ｄ２＋ａ３ｄ１という式は、上に挙げた計算法の中で２回出現しているので、例えば、ＸＯＲゲートとＡＮＤゲートを使用するハードウェア要件を最小化するため、１回だけ計算すればよい。上で説明した３つの２次簡約多項式の各々を使用するＧＦ（２４）の２つの要素の乗算の計算法を利用して、各々の２次簡約多項式用のＧＦ（２４）乗算器を構成できることは、当業者であれば理解されよう。そのような乗算器は、当技術分野で知られているように、ハードウェアおよび／またはソフトウェアで実施することができる。与えられた表現変換行列用に、適切なＧＦ（２４）乗算器を構成することができる。各表現変換行列は、上で説明したように、ＧＦ（２４）上の３つの既約簡約多項式の１つと、拡大多項式とを組み合わせて定義することができるので、ＧＦ（２４）乗算器は、事前に決定することができる。本発明の例示的な実施形態によれば、ＧＦ（２４）乗算器のその他の適切な実施を、追加的または代替的に使用することもできることは、当業者であれば理解されよう。
【００７１】
ＧＦ（２４）でのＩＮＶと表記される逆演算、およびＳＱＲと表記される平方演算は、サイズがそれぞれ８バイト、すなわち、１６ニブルの２つの別個の比較的小さな参照用テーブル（ＬＵＴ）によって実施することができる。本発明のいくつかの実施形態によれば、係数βは事前に決定することができる。したがって、要素ｇ∈ＧＦ（２４）に対応する値β×ｇ２（βＳＱＲと表記）も、８バイトのＬＵＴに記憶しておくことができ、そのため、連立式１４を計算するのに必要な１組の計算から乗算を１つ取り除くことができる。代替の実施形態によれば、ＧＦ（２４）でのＳＱＲ、ＩＮＶ、および／またはβＳＱＲは、当技術分野で知られている任意の適切な回路によって実施することができる。例えば、ＳＱＲ回路は、上で説明したような２つの要素の乗算のための計算法において、ａ＝ｄと置くことによって実施することができる。したがって、ＳＱＲ回路は、以下の計算法によって実施することができる。
簡約多項式：ｔ４＋ｔ＋１
［ａ３，ａ２，ａ１，ａ０］２＝［ａ３，ａ３＋ａ１，ａ２，ａ０＋ａ２］
簡約多項式：ｔ４＋ｔ３＋１
［ａ３，ａ２，ａ１，ａ０］２＝［ａ２＋ａ３，ａ１＋ａ３，ａ３，ａ０＋ａ２＋ａ３］
簡約多項式：ｔ４＋ｔ３＋ｔ２＋ｔ＋１
［ａ３，ａ２，ａ１，ａ０］２＝［ａ２，ａ１＋ａ２，ａ２＋ａ３，ａ０＋ａ２］
本発明の実施形態の回路実装は、対応するＬＵＴ実装よりもコンパクトにすることができることに留意されたい。しかし、いくつかのＳボックス実装では、ＬＵＴのほうがより効率的なデータ処理を行うことができる。
【００７２】
本発明の例示的な実施形態によれば、１２９番目の表現変換行列、すなわち、１６進表記でＭ＝０１，５０，ｂ０，０ｃ，ａ３，８ｂ，ｄ３，ｄ５と表される行列は、上に挙げた１９２個の表現変換行列から選択することができる。したがって、対応する拡大簡約多項式は、ｐ（ｔ）＝ｔ４＋ｔ３＋ｔ２＋ｔ＋１、ｒ（ｔ）＝ｔ２＋ｔ＋２、すなわち、β＝２である。この例示的な実施形態によれば、乗算回路は、［ａ３，ａ２，ａ１，ａ０］×［ｄ３，ｄ２，ｄ１，ｄ０］＝［ａ２ｄ１＋ａ３ｄ０＋ａ３ｄ１＋ａ１ｄ２＋ａ１ｄ３＋ａ２ｄ２＋ａ０ｄ３，ａ３ｄ１＋ａ２ｄ２＋ａ１ｄ１＋ａ２ｄ０＋ａ０ｄ２＋ａ１ｄ３，ａ０ｄ１＋ａ１ｄ３＋ａ１ｄ０＋ａ３ｄ１＋ａ３ｄ３＋ａ２ｄ２，ａ３ｄ２＋ａ１ｄ３＋ａ０ｄ０＋ａ２ｄ３＋ａ２ｄ２＋ａ３ｄ１］となる。
【００７３】
本発明のこの例示的な実施形態によれば、１６進表記で示された以下のＬＵＴを使用して、０以上１５以下の入力された数ｌに対応するＳＱＲ、βＳＱＲ、および／またはＩＮＶの個々の値を計算することができる。
ＳＱＲ＝０，１，４，５，ｆ，ｅ，ｂ，ａ，２，３，６，７，ｄ，ｃ，９，８
βＳＱＲ＝０，２，８，ａ，１，３，９，ｂ，４，６，ｃ，ｅ，５，７，ｄ，ｆ
ＩＮＶ＝０，１，ｆ，ａ，８，６，５，９，４，７，３，ｅ，ｄ，ｃ，ｂ，２
ただし、各テーブルの出力は、テーブルのｌ番目のエントリとすることができる。代替として、ＳＱＲ、βＳＱＲ、および／またはＩＮＶは、上で説明したように、回路実装を使用して計算することもでき、例えば、ＳＱＲ回路は、［ａ３，ａ２，ａ１，ａ０］２＝［ａ２，ａ１＋ａ２，ａ２＋ａ３，ａ０＋ａ２］によって与えられる。
【００７４】
図２を参照すると、本発明のいくつかの例示的な実施形態による、データを暗号化／復号化するためのＡＥＳ互換Ｓボックス２００の回路実装が示されている。
Ｓボックス２００は、以下で説明するように、式８および９に基づいて、ブロックデータｘに対応する出力ｓｂｏｘ［ｘ］またはｓｂｏｘ−１［ｘ］を提供するように実施することができる。
【００７５】
Ｓボックス２００は、ＡＥＳ表現の入力データｘ、例えば、ｘ＝［ｘ７ｘ６ｘ５ｘ４ｘ３ｘ２ｘ１ｘ０］（ｘ∈ＧＦ（２８））と表記される８ビットデータなどを受信し、上で説明したように、変換演算子を用いて、このデータをＧＦ（（２４）２）表現のデータに変換する、入力変換モジュール２２１を含むことができる。復号化モードの演算の場合、変換モジュール２２１はまた、以下で説明するように、ｘに復号化アフィン変換を施すことができる。Ｓボックス２００は、以下で説明するように、例えば、ＧＦ（２８）等価の暗号化演算／復号化演算を実行することによって、変換されたデータを処理し、処理されたＧＦ（（２４）２）データを提供する、演算モジュール２３０も含むことができる。Ｓボックス２００は、以下で説明するように、処理されたデータをＡＥＳ表現に変換し直す、出力逆変換モジュール２２３も含むことができる。モジュール２２３はまた、以下で説明するように、モジュール２３０の出力に暗号化アフィン変換を施すことができる。
【００７６】
これらの例示的な実施形態によれば、モジュール２２１は、暗号化モードの演算に対応する、すなわち、上で説明したような変換ｓｂｏｘ［ｘ］を実行する、第１のデータ入力パス２０２を含むことができる。モジュール２２１は、復号化モードの演算に対応する、すなわち、変換ｓｂｏｘ−１［ｘ］を実行する、第２のデータ入力パス２０４も含むことができる。
【００７７】
本発明の例示的な実施形態によれば、モジュール２２１は、暗号変換回路２１４と、復号変換回路２１０を含むことができる。回路２１４は、ｘに変換演算子を作用させるように、例えば、ｘにＭ−１を乗じる乗算を実行するように適合されるＭ−１乗算器を含むことができる。回路２１０は、ｘに変換演算子を作用させるように適合させることができ、例えば、回路２１０は、ｘとｂとのＸＯＲ演算を実行するためのＸＯＲモジュール２１６と、モジュール２１６の出力に（ＡＭ）−１を乗じる乗算を実行する（ＡＭ）−１乗算器とを含むことができる。したがって、回路２１４の出力は、式８の括弧内の式に対応するＭ−１ｘとなることができる。回路２１０の出力は、式９の括弧内の式に対応する
【００７８】
【数８】
2005534973.tif 000010
【００７９】
となることができる。
本発明の例示的な実施形態によれば、モジュール２２１は、マルチプレクサ２２０も含み、マルチプレクサは、回路２１４および２１０の出力にそれぞれ関連づけられた２つの入力を有することができる。マルチプレクサ２２０は、これらの２つの入力を選択するのに使用することができ、マルチプレクサ２２０の出力が、選択された入力に対応する変換データ２３１の１つの出力を含むようにすることができる。マルチプレクサ２２０は、２つの入力を選択するための、当技術分野で知られている任意の適切な回路を含むことができる。例えば、マルチプレクサ２２０は、制御レジスタ（図示せず）を含むことができる。制御レジスタは、要求された演算モードを指示するための指示ビットを格納することができ、例えば、暗号化演算モードの場合は指示ビットを０に、復号化演算モードの場合は指示ビットを１に等しくすることができる。マルチプレクサ２２０の出力は、当技術分野で知られているように、指示ビットの値に基づいて選択することができる。指示ビットの値は、複数のデータブロックに対して暗号化演算または復号化演算を実行する前に設定することができる。変換ＧＦ（（２４）２）データ２３１は、当技術分野で知られているように、例えば、８ビット並列電線（図示せず）によって受け渡される８ビットを含むことができる。８本の電線は、それぞれ４本ずつの電線からなる２つの組に分割することができる。したがって、変換データ２３１の８ビットは、上で説明したように、変換データ２３１の８ビット値に対応する２つの４ビットデータ値、すなわち、２３５で示されるｚ＜ｍ＞＝［ｚ７ｚ６ｚ５ｚ４］と、２３１で示されるｚ＜ｌ＞＝［ｚ３ｚ２ｚ１ｚ０］（ｚ＜ｍ＞，ｚ＜ｌ＞∈ＧＦ（（２４）２））に分割することができる。
【００８０】
モジュール２３０は、以下で説明するように、データ値ｚ＜ｍ＞とｚ＜ｌ＞を処理し、上で説明したＴ（ｘ）＝ｃ＜ｍ＞ｔ＋ｃ＜ｌ＞によって表される処理されたデータを提供する回路を含むことができる。ｃ＜ｍ＞およびｃ＜ｌ＞の値は、連立式１４で与えることができるが、その場合、ａ＜ｍ＞およびａ＜ｌ＞は、ｚ＜ｍ＞およびｚ＜ｌ＞で置き換えられ、α＝１とする。
【００８１】
本発明の例示的な実施形態によれば、演算モジュール２３０は、上で説明したように、変換データ２３１に対してＡＥＳ等価な演算を実行するための演算回路を含むことができる。演算回路は、第１の８ビットのビット単位ＸＯＲボックス２３２と、第２の８ビットのビット単位ＸＯＲボックス２３４を含むことができる。演算回路は、上で説明したような、３つの同じＧＦ（２４）乗算器２３６、２３８、２４０も含むことができる。演算回路は、上で説明したような、ＩＮＶ２４２、ＳＱＲ２４４、βＳＱＲ２４６をそれぞれ実行する、３つの回路／８バイトテーブルを含むことができる。回路／テーブル２４２、２４４、２４６および乗算器２３６、２３８、２４０は、上で説明したように、選択された簡約多項式に基づいて、事前に決定することができる。したがって、乗算器２４０の出力ｃ＜ｌ＞および乗算器２３８の出力ｃ＜ｍ＞はそれぞれ、（ｚ＜ｌ＞＋ｚ＜ｍ＞）（ｚ２＜ｍ＞β＋ｚ２＜ｌ＞＋ｚ＜ｌ＞ｚ＜ｍ＞）−１、ｚ＜ｍ＞（ｚ２＜ｍ＞β＋ｚ２＜ｌ＞＋ｚ＜ｌ＞ｚ＜ｍ＞）−１に等しくなることができる。
【００８２】
乗算器２４０の４ビット出力と乗算器２３８の４ビット出力は、出力２３０で再合成されて、変換データ２３１に対して実行された演算Ｔに対応する１つの８ビットデータ出力を形成することができる。したがって、暗号化モードの演算の場合、モジュール２３０の出力は、式８に基づく値Ｔ［Ｍ−１×ｘ］を含むことができる。復号化モードの演算の場合、モジュール２３０の出力は、式９に基づく値
【００８３】
【数９】
2005534973.tif 000011
【００８４】
を含むことができる。モジュール２３０の出力は、モジュール２２３によって受信されることができる。
【００８５】
モジュール２２３は、暗号化モードの演算に対応する第１のデータパス２７２と、復号化モードの演算に対応する第２のデータパス２７４を含むことができる。モジュール２２３は、暗号逆変換回路２８５と、復号逆変換回路２８２を含むことができる。回路２８２は、パス２７２に関連づけられたＭ乗算器を含むことができる。回路２８２は、復号化モードにおいて、処理されたＧＦ（（２４）２）データをＡＥＳ表現に変換し直すため、例えば、式９に基づく
【００８６】
【数１０】
2005534973.tif 000012
【００８７】
を得るために使用することができる。回路２８５は、パス２７４に関連づけられたＡＭ乗算器２８４と、乗算器２８４の出力に関連づけられたＸＯＲブロック２８６を含むことができる。乗算器２８４は、演算の暗号化モードにおいて、ＸＯＲブロック２８６と組み合わせて、処理されたＧＦ（（２４）２）データをＡＥＳ表現に変換し直すため、例えば、式８に基づく
【００８８】
【数１１】
2005534973.tif 000013
【００８９】
を得るために使用することができる。本発明の例示的な実施形態によれば、モジュール２２３は、マルチプレクサ２９０も含み、マルチプレクサは、ＸＯＲブロック２８６および乗算器２８２の出力にそれぞれ関連づけられた２つの入力を有することができる。マルチプレクサ２９０は、これらの２つの入力を選択するのに使用することができ、マルチプレクサ２９０の出力が、演算モードに対応する１つの出力を含むようにすることができる。マルチプレクサ２９０は、２つの入力を選択するための、当技術分野で知られている任意の適切な回路を含むことができる。例えば、マルチプレクサ２９０は、上で説明したようなマルチプレクサ２２０の回路と同様の回路を含むことができる。
【００９０】
Ｓボックス２００の演算の例を以下に提示する。第１の例は、本発明の実施形態による、ＡＥＳ互換Ｓボックスを使用してデータを暗号化するステップを具体的に示している。第２の例は、別の実施形態によるデータの復号化を具体的に示している。提示される例では、上に列挙した行列の集合のうちの１２９番目の表現変換行列が使用され、入力データｘには値６７をもつデータが選択されている。これらの例における表現変換行列および入力データは、例示のためだけに無作為に選択されたものであり、本発明の範囲を特定の選択された表現変換行列または特定の入力データ値に限定する意図はないことに留意されたい。
【００９１】
最初に、この例示的な実施形態では１６進値６７（Ｔ１）で表される入力データが、入力パス２０２を介してロードされる。入力データは、乗算器２１４でＭ−１を乗じられ、２ｅ（Ｔ３）が算出される。次に、Ｔ３が、暗号化モードに設定されたマルチプレクサ２２０に入力される。したがって、Ｔ３は、２つの４ビット値、すなわち、Ｔ７＝２とＴ６＝ｅに分割される。次に、ＸＯＲボックス２３２で、２つの４ビット値のＸＯＲが計算され、
【００９２】
【数１２】
2005534973.tif 000014
【００９３】
が算出される。Ｔ７は、βＳＱＲ回路／テーブル２４６に入力され、Ｔ１０＝２・２２＝８が算出される。上で説明した乗算器によって、Ｔ９＝Ｔ７・Ｔ６＝２・ｅ＝３を生成するため、乗算器２３６が使用される。Ｔ６は、ＳＱＲ回路／テーブル２４４に入力され、Ｔ８＝ｅ２＝９が算出される。ＸＯＲボックス２３４で、値Ｔ８、Ｔ９、Ｔ１０のＸＯＲが計算され、
【００９４】
【数１３】
2005534973.tif 000015
【００９５】
が生成される。次に、Ｔ１２は、ＩＮＶ回路／テーブル２４２に入力され、Ｔ１３＝Ｔ１２−１＝ｆが算出される。乗算器２３８は、入力Ｔ１１およびＴ１３を受信し、Ｔ１４＝Ｔ１１・Ｔ１３＝６が算出され、乗算器２４０は、入力Ｔ７およびＴ１３を受信し、Ｔ１５＝Ｔ７・Ｔ１３＝１が算出される。次に、Ｔ１５とＴ１４が合成されて、単一の８ビットデータ値、すなわち、Ｔ１６＝１６が生成される。単一の８ビットデータ値は、乗算器２８４に入力され、Ｔ１８＝（ＡＭ）・１６＝ｅ６が算出される。最後に、ＸＯＲボックス２８６で、Ｔ１８とｂのＸＯＲが計算され、
【００９６】
【数１４】
2005534973.tif 000016
【００９７】
が生成される。マルチプレクサ２５８は、Ｔ２０＝Ｔ１９＝８５を出力として選択する。したがって、Ｓボックスの出力ｓｂｏｘ［ｘ］は８５である。
【００９８】
上記の例で説明したＳボックスの（暗号化）出力を復号化するため、Ｓボックスを利用する例を以下に提示する。Ｓボックスには最初、データ値Ｔ１＝８５が入力される。ボックス２１６で、Ｔ１とｂのＸＯＲが計算され、
【００９９】
【数１５】
2005534973.tif 000017
【０１００】
が算出される。Ｔ２は、乗算器２１８で（ＡＭ）−１を乗じられ、Ｔ４＝（ＡＭ）−１・ｅ６＝１６が算出される。次に、Ｔ４は、（復号化モードに設定された）マルチプレクサ２２０によって選択され、Ｔ５が得られる。Ｔ５は、Ｔ６＝６とＴ７＝１に分割される。次に、ボックス２３２で、２つの４ビット値のＸＯＲが計算され、
【０１０１】
【数１６】
2005534973.tif 000018
【０１０２】
が算出される。次に、回路／テーブルβＳＱＲ２４６、ＳＱＲ２４４、および乗算器２３６を使用して、値Ｔ１０＝β・Ｔ７２＝２、Ｔ９＝Ｔ６・Ｔ７＝６、およびＴ８＝Ｔ６２＝ｂが計算される。ボックス２３４で、出力Ｔ１０、Ｔ９、Ｔ８のＸＯＲが計算され、
【０１０３】
【数１７】
2005534973.tif 000019
【０１０４】
が算出される。次に、Ｔ１２は、ＩＮＶテーブル２４２に入力され、Ｔ１３＝Ｔ１２−１＝２が算出される。乗算器２３８は、入力Ｔ１１およびＴ１３を受け取り、乗算器２４０は、入力Ｔ７およびＴ１３を受け取る。乗算器２４０および乗算器２３８の出力結果はそれぞれ、Ｔ１４＝Ｔ１１・Ｔ１３＝ｅ、Ｔ１５＝Ｔ７・Ｔ１３＝２となる。次に、Ｔ１５とＴ１４が合成されて、単一の８ビットデータ値Ｔ１６＝２ｅが生成される。Ｔ１６は、乗算器５８２で、Ｍを乗じられ、Ｔ１７＝Ｍ・２ｅ＝６７が生成される。最後に、マルチプレクサ２９０は、Ｔ２０＝Ｔ１７＝６７を出力として選択する。
【０１０５】
図３を参照すると、本発明のさらなる例示的な実施形態による、演算モジュール３３０が概略的に示されている。
本発明のいくつかの例示的な実施形態によれば、Ｓボックス（図２）のモジュール２３０（図２）は、α≠１とするＡＥＳ等価な演算を実行できるように、モジュール３３０で置き換えることができる。モジュール３３０は、値２３５にαを乗じるためのアルファ乗算器３３２を含むことができる。乗算器３３２の出力は、ＸＯＲブロック２３２および乗算器２３６の入力にそれぞれ供給することができる。したがって、乗算器２３８の出力ｃ＜ｍ＞および乗算器２４０の出力ｃ＜ｌ＞は、上で説明したように、連立式１４に基づいて提供することができる。
【０１０６】
本発明のいくつかの実施形態によれば、表現変換の組から表現変換行列を決定するための方法が提供される。この方法は、組み立ておよび／またはシミュレートによって、複数の回路を合成するステップを含むことができ、各回路は、上で説明したように、ＧＦ（２２ｓ）表現からＧＦ（（２ｓ）２）表現への表現変換行列に対応する。上記の方法はまた、以下で説明するように、例えば、最小回路面積など、所定の最適化基準に照らして、行列の集合の中から１つを選択するステップも含む。
【０１０７】
本発明の例示的な実施形態によれば、可能な表現変換行列、例えば、上で説明した１９２個の表現変換行列の集合の各表現変換行列Ｍは、上で説明したように、ＡＥＳ表現からＧＦ（（２４）２）表現への変換を可能とするように実装することができる。各表現変換行列は、例えば、上で説明したような適切な電気回路、および／または適切なソフトウェアによって実装することができ、以下で説明するように、異なる性能特性をもつことができる。したがって、本発明の実施形態によれば、表現変換行列は、以下で説明するように、何らかの所望の基準に照らして、行列の集合から選択することができる。
【０１０８】
本発明の実施形態によれば、回路試験の条件となる動作パラメータは、回路の関連する結果に影響を及ぼすことができる。したがって、回路またはプロセスの最適性は、以下で説明するように、使用する動作パラメータに依存することができる。さらに、回路またはプロセスが最適であるかどうかの判断は、回路／プロセスを評価するのに使用される基準によって変ることができる。したがって、動作パラメータおよび／または基準が異なれば、異なる回路／プロセスが、最適であると決定されることがある。
【０１０９】
本発明のいくつかの例示的な実施形態によれば、比較基準には、サンプルデータを変換し、上で説明したようなＡＥＳ等価な演算を実行するため、回路／プロセスの各々が必要とするゲート数および／または消費電力が含まれることができる。本発明のその他の実施形態によれば、その他の任意の所望の最適化基準を利用することができる。
【０１１０】
本発明の例示的な実施形態によれば、回路の組、例えば、１９２個の可能な変換行列にそれぞれ対応する１９２個の回路は、例えば、上で説明したＳボックス２００（図２）に対応するように作成することができる。これらの例示的な実施形態によれば、個々の回路は、Ｓｙｎｏｐｓｉｓ社が販売するＤＣ  Ｓｈｅｌｌ  ２００１．０８−ｓｐ１（ＤＣ  Ｅｘｐｅｒｔ）を使用して合成することができる。目標ライブラリＴＳＭＣ  ０．１８μ（ＳＡＡＧ−Ｘ  Ａｒｔｉｓａｎｅ）を使用することができる。合成は、様々なタイミング、例えば、伝播遅延時間が、例えば、１２ナノ秒から６ナノ秒の範囲のいずれかの時間となるように実行することができる。これらのパラメータは、マージン、例えば、３ナノ秒のマージンを追加することによって、例えば、６６．７ＭＨｚから１１１ＭＨｚの範囲の異なる別個の周波数を使用できるようにすることができる。これらの例示的な実施形態によれば、上で説明した方法の結果を、以下の表によって要約することができる。
【０１１１】
【表１】
2005534973.tif 000020
【０１１２】
ただし、括弧内の数字は、その数字をインデックス番号とする上で説明したような表現変換行列に対応する回路を表す。したがって、例えば、タイミング＝１２の場合、Ｎｏ．８２の行列を使用したとき、最小面積の回路が得られ、Ｎｏ．４５の行列を使用したとき、最大面積の回路が得られる。
【０１１３】
表１から分かるように、実装に必要な最小面積および他の基準に関して、および／またはある動作パラメータの下で、いくつかの回路は、その他の回路よりも望ましいようである。さらに分かるように、各回路の性能は、回路の動作パラメータに依存することができる。ある動作パラメータを変更することで、個々の回路にほぼ同様の方法で影響を及ぼすことができる。しかし、いくつかの回路は、ある動作パラメータの下で動作したときに最適な結果を生みだすことができ、動作パラメータが変化すると、最適とは掛け離れた結果が生じることがあることを理解されたい。例えば、回路面積は、選択された表現変換行列に関係なく、周波数とともに大きくなることができるが、異なる周波数では、異なる回路が、最適な結果、例えば、回路を実装するのに必要な異なる最適面積を提供することができる。性能の違いは、少なくとも部分的に、ＡＥＳ  Ｓボックス等価なＬＵＴが、複雑さのレベルを異にする原因となり、またＧＦ（２８）のＧＦ（（２４）２）表現での計算が、異なる回路および様々な動作パラメータで異なる原因となることができる。
【０１１４】
本発明のいくつかの実施形態によれば、回路のいくつかは、周波数の変化にあまり影響を受けず、様々な動作パラメータの下で動作したときに、ほぼ一定の良好な結果を示すことができる。例えば、上で説明したような等価な表現変換行列に別々に対応する回路８２、１０５、１２４、１２８は、様々な動作パラメータの下で望ましい結果を示すことができる。様々な回路の性能の違い、および非常に多くのケースでのいくつかの回路の望ましさは、上で説明したような、それぞれ代替を有するＩＮＶ回路／テーブル、ＳＱＲ回路／テーブル、およびＧＦ（２４）乗算器の３つの使い分けに関係することができる。さらに、異なる回路は、異なるβＳＱＲ回路／テーブルを必要とすることができ、Ｍ、ＡＭ、Ｍ−１、（ＡＭ）−１による乗算は、上で説明したように、異なることができる。
【０１１５】
本発明のさらなる例示的な実施形態によれば、ＧＦ（２２ｓ）表現からＧＦ（（２ｓ）２）表現への変換は、１つまたは複数の中間変換演算子を利用することによって、段階的または再帰的に実行することができる。例えば、ｓ＝２ｕの場合、ＧＦ（２ｓ）表現での演算は、ＧＦ（２２ｕ）での演算に類似することができる。ＧＦ（２２ｕ）での演算は、ＧＦ（（２ｕ）２）表現で実行することができる。したがって、中間変換演算子を利用して、ＧＦ（（２ｓ）２）表現のデータをＧＦ（（２ｕ）２）表現の対応するデータに変換することができる。必要に応じて、第２の中間変換演算子を利用して、ＧＦ（２ｕ）表現のデータをＧＦ（（２ｖ）２）表現（ｕ＝２ｖ）の対応するデータに変換するなど、このような操作をさらに続けることができる。したがって、
【０１１６】
【数１８】
2005534973.tif 000021
【０１１７】
表現（ｑは奇数）での演算は、ＧＦ（２ｑ）表現での演算を使用することによって、ＧＦ（（．．（（（２ｑ）２）２）．．）２）表現での演算を使用して実行することができる。ＧＦ表現から、例えば、サイズが半分の別のＧＦ表現への変換は、例えば、回路効率および／または電力効率など、特定の実施の効率性基準に照らして設計することができる。
【０１１８】
本発明が、本明細書で提示され、添付の図面を参照しながら説明された本発明の例示的な実施形態に限定されるものではないことは、当業者であれば理解されよう。本発明のいくつかの特徴を例示し、説明してきたが、当業者であれば、多くの修正、置換、変更、および均等物を思い浮かべることができるであろう。したがって、添付の特許請求の範囲は、本発明の真の主旨に包含されるそのようなすべての修正および変更を含むことを意図したものであることを理解されたい。
【図面の簡単な説明】
【０１１９】
【図１】本発明の実施形態による、データを操作する方法のフローチャートである。
【図２】本発明のいくつかの例示的な実施形態による、データを暗号化および／または復号化するためのＡＥＳ  Ｓボックスを実施する回路の概略図である。
【図３】本発明のさらなる例示的な実施形態による、演算モジュールの概略図である。
【図１】
2005534973.tif 000022
【図２】
2005534973.tif 000023
【図３】
2005534973.tif 000024
【手続補正書】
【提出日】平成17年4月8日(2005.4.8)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
ＧＦ（２２ｓ）表現のデータを処理する方法であって、ＧＦ（２２ｓ）表現のデータを、前記ＧＦ（２２ｓ）表現のデータに所定の変換に関連する変換演算子を作用させることによって、対応するＧＦ（（２ｓ）２）表現のデータに変換するステップを含む方法。
【請求項２】
前記変換演算子が、前記変換に対応する表現変換行列に関連する、請求項１に記載の方法。
【請求項３】
前記変換演算子が、前記表現変換行列の逆行列である、請求項２に記載の方法。
【請求項４】
前記変換演算子が、線形変換と前記表現変換行列の組み合わせを含む、請求項２に記載の方法。
【請求項５】
前記変換演算子が、前記表現変換行列とパラメータ行列の行列積の逆行列を含む、請求項４に記載の方法。
【請求項６】
前記ＧＦ（（２ｓ）２）表現が、ＧＦ（２ｓ）上の既約簡約多項式とＧＦ（２ｓ）上の拡大多項式とによって定義される、請求項１から５のいずれか一項に記載の方法。
【請求項７】
ＧＦ（２ｓ）上の前記拡大多項式が、ＧＦ（２ｓ）上の２次既約多項式を含む、請求項６に記載の方法。
【請求項８】
前記表現変換行列が、所定の基準に照らして可能な表現変換行列の集合から選択される、請求項２から７のいずれか一項に記載の方法。
【請求項９】
前記行列の集合の各行列が、前記ＧＦ（２２ｓ）表現上の既約多項式の根と前記ＧＦ（（２ｓ）２）表現の体生成元とによって定義される、請求項８に記載の方法。
【請求項１０】
前記ＧＦ（（２ｓ）２）表現のデータを、前記ＧＦ（２２ｓ）表現での少なくとも１つの所望の演算と等価な少なくとも１つの演算を実行することによって処理して、処理されたＧＦ（（２ｓ）２）データを取得するステップを含む、請求項１から９のいずれか一項に記載の方法。
【請求項１１】
前記ＧＦ（２２ｓ）表現のデータが、２以上のデータブロックを含み、前記方法が、前記ＧＦ（（２ｓ）２）表現のデータを、前記ＧＦ（２２ｓ）表現での少なくとも１つの所望の演算と等価な前記ＧＦ（（２ｓ）２）表現での少なくとも１つの演算を前記２以上のデータブロックに対して実行することによって処理して、処理されたＧＦ（（２ｓ）２）データを取得するステップを含む、請求項１から９のいずれかに記載の方法。
【請求項１２】
前記少なくとも１つの所望の演算が、前記ＧＦ（２２ｓ）表現での逆演算を含む、請求項１０または１１に記載の方法。
【請求項１３】
前記ＧＦ（（２ｓ）２）表現での前記少なくとも１つの演算が、前記ＧＦ（（２ｓ）２）表現での平方演算、前記ＧＦ（（２ｓ）２）表現での乗算、前記ＧＦ（（２ｓ）２）表現でのＸＯＲ演算、および前記ＧＦ（（２ｓ）２）表現での逆演算からなる前記群から選択される少なくとも１つの演算を含む、請求項１０から１２のいずれか一項に記載の方法。
【請求項１４】
前記処理されたＧＦ（（２ｓ）２）データを、前記処理されたＧＦ（（２ｓ）２）データに前記所定の変換に関連する逆変換演算子を作用させることによって、前記ＧＦ（２２ｓ）表現に変換し直すステップを含む、請求項１０から１３のいずれか一項に記載の方法。
【請求項１５】
前記変換演算子が、復号変換演算子を含み、前記ＧＦ（２２ｓ）表現での前記少なくとも１つの所望の演算が、前記ＧＦ（２２ｓ）表現での少なくとも１つの復号化演算を含む、請求項１４に記載の方法。
【請求項１６】
前記ＧＦ（２２ｓ）表現での前記少なくとも１つの所望の演算が、前記ＧＦ（２２ｓ）表現での少なくとも１つの暗号化演算を含み、前記逆変換演算子が、暗号逆変換演算子を含む、請求項１４に記載の方法。
【請求項１７】
ｓが４に等しい、請求項１から１６のいずれかに記載の方法。
【請求項１８】
前記変換演算子を作用させるステップが、１つまたは複数の中間変換演算子を作用させて、前記ＧＦ（２２ｓ）表現のデータを前記ＧＦ（（２ｓ）２）表現のデータに再帰的に変換するステップを含む、請求項１から１７のいずれかに記載の方法。
【請求項１９】
ＧＦ（２２ｓ）表現のデータを処理するための装置であって、
ＧＦ（２２ｓ）表現のデータを対応するＧＦ（（２ｓ）２）表現のデータに変換する入力変換モジュールと、
前記ＧＦ（２２ｓ）表現での少なくとも１つの所望の演算と等価なＧＦ（（２ｓ）２）表現での少なくとも１つの演算を実行して、処理されたＧＦ（（２ｓ）２）データを取得する演算モジュールと、
前記処理されたＧＦ（（２ｓ）２）データを前記ＧＦ（２２ｓ）表現に変換し直す出力変換モジュールとを含む装置。
【請求項２０】
前記入力変換モジュールが、前記ＧＦ（２２ｓ）データに前記変換に、対応する表現変換行列に関連する行列を乗じるための乗算器を含む、請求項１９に記載の装置。
【請求項２１】
前記入力変換モジュールが、前記ＧＦ（２２ｓ）データの線形変換に、前記変換に対応する表現変換行列に関連する行列を乗じるための乗算器を含む、請求項１９または２０に記載の装置。
【請求項２２】
前記少なくとも１つの所望の演算が、前記ＧＦ（２２ｓ）表現での逆演算を含む、請求項１９から２１のいずれか一項に記載の装置。
【請求項２３】
前記ＧＦ（（２ｓ）２）表現での前記少なくとも１つの演算が、前記ＧＦ（（２ｓ）２）表現での平方演算、前記ＧＦ（（２ｓ）２）表現での乗算、前記ＧＦ（（２ｓ）２）表現でのＸＯＲ演算、および前記ＧＦ（（２ｓ）２）表現での逆演算からなる前記群から選択される少なくとも１つの演算を含む、請求項１９から２２のいずれか一項に記載の装置。
【請求項２４】
前記出力変換モジュールが、前記処理されたＧＦ（（２ｓ）２）データに、前記変換に対応する表現変換行列に関連する行列を乗じるための乗算器を含む、請求項１９から２３のいずれか一項に記載の装置。
【請求項２５】
前記出力変換モジュールが、前記処理されたＧＦ（（２ｓ）２）データの線形変換に、前記変換に対応する表現変換行列に関連する行列を乗じるための乗算器を含む、請求項１９から２４のいずれかに記載の装置。
【請求項２６】
前記ＧＦ（（２ｓ）２）表現が、ＧＦ（２ｓ）上の既約簡約多項式とＧＦ（２ｓ）上の拡大多項式によって定義される、請求項１９から２５のいずれか一項に記載の装置。
【請求項２７】
ＧＦ（２ｓ）上の前記拡大多項式が、ＧＦ（２ｓ）上の２次既約多項式を含む、請求項２６に記載の装置。
【請求項２８】
前記ＧＦ（２２ｓ）表現での前記少なくとも１つの所望の演算が、前記ＧＦ（２２ｓ）表現での復号化演算および前記ＧＦ（２２ｓ）表現での暗号化演算からなる前記群から選択される少なくとも１つの演算を含む、請求項１９から２７のいずれか一項に記載の装置。
【請求項２９】
ｓが４に等しい、請求項１９から２８のいずれか一項に記載の装置。
【請求項３０】
表現変換を決定するための方法であって、
ＧＦ（２２ｓ）表現からＧＦ（（２ｓ）２）表現への複数の表現変換にそれぞれ対応する複数の回路を合成するステップと、
少なくとも１つの最適化基準に照らして前記複数の表現変換から１つを選択するステップとを含む方法。
【請求項３１】
前記複数の回路を合成するステップが、前記複数の回路を組み立てるステップを含む、請求項３０に記載の方法。
【請求項３２】
前記複数の回路を合成するステップが、前記複数の回路をシミュレートするステップを含む、請求項３０または３１に記載の方法。
【請求項３３】
ｓが４に等しい、請求項３０から３２のいずれか一項に記載の方法。
【請求項３４】
前記少なくとも１つの基準が、回路面積および電力消費からなる前記群から選択される基準を含む、請求項３０から３３のいずれか一項に記載の方法。
【請求項３５】
ＧＦ（２２ｓ）表現のデータを暗号化／復号化するための暗号化／復号化装置であって、
復号変換回路と暗号変換回路とを含み、ＧＦ（２２ｓ）表現のデータをＧＦ（（２ｓ）２）表現の対応するデータに変換する入力変換モジュールと、
前記ＧＦ（２２ｓ）表現での所望の暗号化／復号化演算と等価な少なくとも１つの演算を前記入力変換モジュールの出力に対して実行して、処理されたＧＦ（（２ｓ）２）データを取得する演算モジュールと、
復号逆変換回路と暗号逆変換回路とを含み、前記処理されたＧＦ（（２ｓ）２）データを前記ＧＦ（２２ｓ）表現に変換し直す出力変換モジュールとを含む装置。
【請求項３６】
前記暗号変換回路が、前記ＧＦ（２２ｓ）データに、所定の変換に関連する対応する表現変換行列の逆行列を乗じるための乗算器を含む、請求項３５に記載の装置。
【請求項３７】
前記復号変換回路が、
暗号パラメータベクトルを前記ＧＦ（２２ｓ）データに加算するための加算器と、
前記加算器の出力に、暗号パラメータ行列と所定の変換に対応する表現変換行列との行列積の逆行列を乗じるための乗算器を含む、請求項３５または３６に記載の装置。
【請求項３８】
前記少なくとも１つの所望の演算が、前記ＧＦ（２２ｓ）表現での逆演算を含む、請求項３５から３７のいずれか一項に記載の装置。
【請求項３９】
前記ＧＦ（（２ｓ）２）表現での前記少なくとも１つの演算が、前記ＧＦ（（２ｓ）２）表現での平方演算、前記ＧＦ（（２ｓ）２）表現での乗算、前記ＧＦ（（２ｓ）２）表現でのＸＯＲ演算、および前記ＧＦ（（２ｓ）２）表現での逆演算からなる前記群から選択される少なくとも１つの演算を含む、請求項３５から３８のいずれか一項に記載の装置。
【請求項４０】
前記復号逆変換回路が、前記処理されたＧＦ（（２ｓ）２）データに、所定の変換に対応する表現変換行列に関連する行列を乗じるための乗算器を含む、請求項３５から３９のいずれか一項に記載の装置。
【請求項４１】
前記暗号逆変換回路が、
前記処理されたＧＦ（（２ｓ）２）データに、暗号パラメータ行列と所定の変換に対応する表現変換行列との行列積の逆行列を乗じるための乗算器と、
暗号パラメータベクトルを前記乗算器の出力に加算するための加算器とを含む、請求項３５から４０のいずれか一項に記載の装置。
【国際調査報告】
2005534973.tif 000025
2005534973.tif 000026