(57)【要約】本発明の実施形態は、有限体における第１表現のマスクされたデータを該有限体における第２表現の変換済みデータに変換し、該変換済みデータを操作してマスクされた操作済みデータを取得することによって、データを操作するための方法及び装置を提供する。
2006517036.tif 000002
【特許請求の範囲】
【請求項１】
データを操作する方法であって、
有限体における第１表現のマスクされた入力データを、前記有限体における第２表現の変換済みデータに変換し、
前記変換済みデータを操作して、マスクされた操作済みデータを取得する、
ステップを含むことを特徴とする方法。
【請求項２】
前記マスクされた入力データの入力マスクを、前記第２表現の更新済みマスクに変換するステップを含むことを特徴とする、請求項１に記載の方法。
【請求項３】
前記マスクされた入力データを変換するステップが、アフィン変換を行うステップを含むことを特徴とする、請求項２に記載の方法。
【請求項４】
前記アフィン変換が線形変換からなり、前記入力マスクを変換するステップが、前記線形変換を行うステップを含むことを特徴とする、請求項３に記載の方法。
【請求項５】
前記変換済みデータを操作するステップが、前記更新済みマスクを用いて該変換済みデータを操作するステップを含むことを特徴とする、請求項２から請求項４までのいずれか１つの請求項に記載の方法。
【請求項６】
前記マスクされた入力データを変換するステップにより、前記更新済みマスクによってマスクされた状態の前記変換済みデータを得ることを特徴とする、請求項２から請求項５までのいずれか１つの請求項に記載の方法。
【請求項７】
前記変換済みデータを操作するステップにより、前記更新済みマスクによってマスクされた状態の前記操作済みデータを得ることを特徴とする、請求項２から請求項６までのいずれか１つの請求項に記載の方法。
【請求項８】
前記変換済みデータを操作するステップが、
前記変換済みデータに前記更新済みマスクを乗じて第１中間データを取得し、
前記第１中間データに前記更新済みマスクの平方を加えて第２中間データを取得し、
前記第２中間データを反転して第３中間データを取得し、
前記第３中間データに単位データ・ビットを加えて第４中間データを取得し、
前記第４中間データに前記更新済みマスクを乗じて前記第２表現のマスクされた反転済みデータを取得する、
ステップを含むことを特徴とする、請求項２から請求項７までのいずれか１つの請求項に記載の方法。
【請求項９】
前記操作済みデータを逆変換して、前記第１表現のマスクされた逆変換済みデータを取得するステップを含むことを特徴とする、請求項１から請求項８までのいずれか１つの請求項に記載の方法。
【請求項１０】
前記操作済みデータを逆変換することにより、前記入力マスクの線形変換によってマスクされた状態の前記逆変換済みデータを得ることを特徴とする、請求項９に記載の方法。
【請求項１１】
前記マスクされた逆変換済みデータのマスクを取るステップを含むことを特徴とする、請求項９又は請求項１０に記載の方法。
【請求項１２】
前記更新済みマスクを逆変換するステップを含むことを特徴とする、請求項９から請求項１１までのいずれか１つの請求項に記載の方法。
【請求項１３】
前記操作済みデータを逆変換するステップが、アフィン変換を行うステップを含むことを特徴とする、請求項９から請求項１２までのいずれか１つの請求項に記載の方法。
【請求項１４】
前記更新済みマスクを逆変換するステップを含み、前記アフィン変換が線形変換からなり、該更新済みマスクを逆変換するステップが、前記線形変換を行うステップを含むことを特徴とする、請求項１３に記載の方法。
【請求項１５】
前記変換済みデータを操作するステップが、前記第１表現の少なくとも１つの所望の演算と等価の少なくとも１つの演算を行うステップを含むことを特徴とする、請求項１から請求項１４までのいずれか１つの請求項に記載の方法。
【請求項１６】
前記少なくとも１つの演算が逆演算であることを特徴とする、請求項１５に記載の方法。
【請求項１７】
前記有限体がガロア体であることを特徴とする、請求項１から請求項１６までのいずれか１つの請求項に記載の方法。
【請求項１８】
前記有限体がＧＦ（ｇh）であることを特徴とする、請求項１７に記載の方法。
【請求項１９】
ｇが２に等しいことを特徴とする、請求項１８に記載の方法。
【請求項２０】
前記第１表現がＧＦ（２2s）であり、第２表現がＧＦ（（２s）2）であることを特徴とする、請求項１９に記載の方法。
【請求項２１】
ｓが４に等しいことを特徴とする、請求項２０に記載の方法。
【請求項２２】
前記マスクされた入力データを与えるために、前記入力マスクを用いて入力データをマスクするステップを含むことを特徴とする、請求項２から請求項２１までのいずれか１つの請求項に記載の方法。
【請求項２３】
前記入力マスクを生成するステップを含むことを特徴とする、請求項２から請求項２２までのいずれか１つの請求項に記載の方法。
【請求項２４】
ｌｏｇ（ｖ）ビットの第１の組とｖ−１ビットの第２の組とを生成し、
前記ビットの第１の組に基づいて数ｗを定め、
前記入力マスクのｗ番目のビットの値を１に設定し、
前記入力マスクのｖ−１ビットを前記第２の組のｖ−１ビットとそれぞれ置き換える、
ステップを含むことを特徴とする、請求項２３に記載の方法。
【請求項２５】
前記入力マスクの少なくとも幾つかのビットが、あらかじめ設定された値を持つことを特徴とする、請求項２から請求項２４までのいずれか１つの請求項に記載の方法。
【請求項２６】
データを操作するための装置であって、
有限体における第１表現のマスクされた入力データを、前記有限体における第２表現の変換済みデータに変換する変換ブロックと、
前記変換済みデータを操作して、マスクされた操作済みデータを取得する操作ブロックと、
を含むことを特徴とする装置。
【請求項２７】
前記変換ブロックが、前記マスクされた入力データの入力マスクを前記第２表現の更新済みマスクに変換することを特徴とする、請求項２６に記載の装置。
【請求項２８】
前記変換ブロックが、
前記第１表現の前記マスクされた入力データを前記変換済みデータに変換する入力変換モジュールと、
前記入力マスクを前記更新済みマスクに変換するマスク変換モジュールと、
を含むことを特徴とする、請求項２７に記載の装置。
【請求項２９】
前記入力変換モジュールが、前記マスクされた入力データに表現変換行列を乗じる乗算器を含み、前記マスク変換モジュールが、前記入力マスクに前記表現変換行列を乗じる乗算器を含むことを特徴とする、請求項２８に記載の装置。
【請求項３０】
前記入力変換モジュールが、前記マスクされた入力データにアフィン変換を行うようになったことを特徴とする、請求項２９に記載の装置。
【請求項３１】
前記マスク変換モジュールが、前記アフィン変換に対応する線形変換を前記マスクに行うようになったことを特徴とする、請求項３０に記載の装置。
【請求項３２】
前記操作ブロックが、前記第１表現の少なくとも１つの所望の演算と等価の少なくとも１つの演算を行うことを特徴とする、請求項２６から請求項３１までのいずれか１つの請求項に記載の装置。
【請求項３３】
前記操作ブロックが、前記第２表現の前記変換済みデータを反転して、マスクされた反転済みデータを与える反転ブロックを含むことを特徴とする、請求項３２に記載の装置。
【請求項３４】
前記操作ブロックが、
前記入力変換モジュールの出力と前記マスク変換モジュールの出力とを乗算する第１乗算器と、
前記マスク変換モジュールの出力の平方を与える平方モジュールと、
前記第１乗算器の出力に前記平方モジュールの出力を加える第１加算器と、
前記第１加算器の出力がゼロでない場合にはゼロ出力値を与えるゼロ検出器と、
前記ゼロ検出器の出力と前記マスク変換モジュールの出力との論理ＡＮＤに対応する出力を与えるＡＮＤゲートと
前記ＡＮＤゲートの出力を前記第１加算器の出力に加える第２加算器と、
前記第２加算器の出力を反転する反転モジュールと、
前記反転モジュールの出力に単位値を加える第３加算器と、
前記マスク変換モジュールの出力と前記第２加算器の出力とを乗算する第２乗算器と、
前記ＡＮＤゲートの出力に前記第２乗算器の出力を加える第４加算器と、
を含むことを特徴とする、請求項２８から請求項３３までのいずれか１つの請求項に記載の装置。
【請求項３５】
前記操作ブロックが、
前記入力変換モジュールの出力と前記マスク変換モジュールの出力とを乗算する第１乗算器と、
前記マスク変換モジュールの出力の平方を与える平方モジュールと、
前記第１乗算器の出力に前記平方モジュールの出力を加える第１加算器と、
前記第１加算器の出力を反転する反転モジュールと、
前記反転モジュールの出力に単位値を加える第２加算器と、
前記マスク変換モジュールの出力と前記第２加算器の出力とを乗算する第２乗算器と、
を含むことを特徴とする、請求項２８から請求項３３までのいずれか１つの請求項に記載の装置。
【請求項３６】
前記操作済みデータを逆変換して、前記第１表現のマスクされた逆変換済みデータを取得する逆変換ブロックを含むことを特徴とする、請求項２６から請求項３５までのいずれか１つの請求項に記載の装置。
【請求項３７】
前記操作済みデータを逆変換して、前記第１表現のマスクされた逆変換済みデータを取得する逆変換ブロックを含み、前記逆変換ブロックが、
前記操作済みデータを前記第１表現に逆変換する出力逆変換モジュールと、
前記更新済みマスクを逆変換するマスク逆変換モジュールと、
を含むことを特徴とする、請求項２７から請求項３５までのいずれか１つの請求項に記載の装置。
【請求項３８】
前記出力逆変換モジュールが、前記操作済みデータにアフィン変換を行うようになったことを特徴とする、請求項３７に記載の装置。
【請求項３９】
前記マスク逆変換モジュールが、前記アフィン変換に対応する線形変換を前記更新済みマスクに行うようになったことを特徴とする、請求項３８に記載の装置。
【請求項４０】
前記マスクされた逆変換済みデータのマスクを取るマスク除去モジュールを含むことを特徴とする、請求項３６から請求項３９までのいずれか１つの請求項に記載の装置。
【請求項４１】
前記入力マスクを生成するマスク生成器を含むことを特徴とする、請求項２７から請求項４０までのいずれか１つの請求項に記載の装置。
【請求項４２】
前記マスク生成器が、ｌｏｇ（ｖ）ビットの第１の組とｖ−１ビットの第２の組とを生成し、前記ビットの第１の組に基づいて数ｗを定め、前記入力マスクのｗ番目のビットの値を１に設定し、該入力マスクのｖ−１ビットを前記第２の組のｖ−１ビットとそれぞれ置き換えることができることを特徴とする、請求項４１に記載の装置。
【請求項４３】
前記入力マスクの少なくとも幾つかのビットが、あらかじめ設定された値を持つことを特徴とする、請求項２７から請求項４２までのいずれか１つの請求項に記載の装置。
【請求項４４】
ｖビットを持つ非ゼロマスクを生成する方法であって、
ｌｏｇ（ｖ）ビットの第１の組とｖ−１ビットの第２の組とを生成し、
前記ビットの第１の組に基づいて数ｗを定め、
前記マスクのｗ番目のビットの値を１に設定し、
前記マスクのｖ−１ビットを前記第２の組のｖ−１ビットとそれぞれ置き換える、
ステップを含むことを特徴とする方法。
【請求項４５】
データを暗号化する方法であって、
有限体における第１表現のマスクされた入力データを、前記有限体における第２表現の変換済みデータに変換し、
前記マスクされた入力データの入力マスクを、前記第２表現の更新済みマスクに変換し、
前記第１表現の所望の暗号化演算と等価の少なくとも１つの演算を行うことにより、前記更新済みマスクを用いて前記変換済みデータを操作して、操作済みデータを取得し、
前記操作済みデータを逆変換して、前記第１表現の操作済みデータを取得する、
ステップを含むことを特徴とする方法。
【請求項４６】
データを復号化する方法であって、
有限体における第１表現のマスクされた入力データを、前記有限体における第２表現の変換済みデータに変換し、
前記マスクされた入力データの入力マスクを、前記第２表現の更新済みマスクに変換し、
前記第１表現の所望の復号化演算と等価の少なくとも１つの演算を行うことにより、前記更新済みマスクを用いて前記変換済みデータを操作して、操作済みデータを取得し、
前記操作済みデータを逆変換して、前記第１表現の操作済みデータを取得する、
ステップを含むことを特徴とする方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般に、有限体における計算に関し、より具体的には、有限体におけるマスクされたデータの操作に関する。
【背景技術】
【０００２】
データ操作アルゴリズムは、有限体のデータ要素に逆演算を行うことを含む場合がある。例えば、次世代暗号化標準（ＡＥＳ）は、ラインダール・ブロック暗号アルゴリズム（「ラインダール・アルゴリズム」）を提供するが、これは、例えばバイト、ｘといったベクトルを含む入力データに関するＢｙｔｅＳｕｂビット・レベル演算を含む。ＢｙｔｅＳｕｂ演算は、暗号化モード及び復号化モードを含む。暗号化モードは、逆演算及びアフィン変換を含み、例えば、Ａ及びｂを所定のパラメータとすると、ｘはＡｘ-1＋ｂに変換される。復号化モードは、アフィン変換と、それに続く逆演算とを含み、例えば、ｘは（Ａ-1（ｘ＋ｂ））-1に変換される。ＡＥＳによれば、逆演算はガロア体ＧＦ（２8）全体にわたって行われる。ガロア体は、簡約多項式ｐ（ｔ）＝ｔ8＋ｔ4＋ｔ3＋１を用いて、多項式形式で表現される。
【０００３】
ＧＦ（２8）において逆演算を実装する他の既知のブロック暗号アルゴリズムが存在する。これらのアルゴリズムは、例えば、Ｋ．Ａｏｋｉらによって「Ｓｐｅｃｉｆｉｃａｔｉｏｎ  ｏｆ  Ｃａｍｅｌｌｉａ−ａ  １２８−ｂｉｔ  Ｂｌｏｃｋ  Ｃｉｐｈｅｒ」、ｈｔｔｐ：／／ｉｎｆｏ．ｉｓｌ．ｎｔｔ．ｃｏ．ｊｐ／ｃａｍｅｌｌｉａ／において説明されるＣａｍｅｌｉａ暗号アルゴリズムと、Ｃ．Ｈ．Ｌｅｅによって「Ｚｏｄｉａｃ：  Ｂｌｏｃｋ  Ｃｉｐｈｅｒ  Ｐｒｏｐｏｓａｌ」、ｈｔｔｐ：／／ｗｗｗ．ｓａｆｅｄｉｇｍ．ｃｏｍ／ｐｒｏｄｕｃｔｐｄｓ／ｄｏｗｎｌｏａｄ／Ｓａｆｅｄｉｇｍ＿Ｚｏｄｉａｃ．ｐｄｆにおいて説明されるＺｏｄｉａｃ暗号アルゴリズムとを含む。
【０００４】
電力差分解析（ＤＰＡ）攻撃は、データ操作アルゴリズムの入力と出力との間の関係を用いて、そのアルゴリズムによって実装される秘密鍵を解明することができる。例えばＡＥＳアルゴリズムといった操作アルゴリズムをＤＰＡ攻撃から保護するために、アルゴリズムを実行する前に、Ｒで表されるランダム入力マスクを、例えばＧＦ（２）全体にわたって入力ベクトル（例えばバイト）ｘに加えて、マスクされたデータを取得することができる。ランダム・マスクは、ｘの長さと等しいビット長を有するランダム・ベクトルを含むことができる。したがって、アルゴリズムは、ｘではなく和の値ｘ＋Ｒに関して実行され、その結果、攻撃者は、アルゴリズムへの実際の入力値を知ることができない。
【０００５】
アルゴリズムのマスクされていない出力を使用できるようにするために、例えばマスクされたデータに関してアルゴリズムを実行した後で、該マスクを除去することが必要な場合がある。
【０００６】
Ｔｒｉｃｈｉｎａ，  Ｅ．らによる「Ｓｉｍｐｌｉｆｉｅｄ  Ａｄａｐｔｉｖｅ  Ｍｕｌｔｉｐｌｉｃａｔｉｖｅ  Ｍａｓｋｉｎｇ  ｆｏｒ  ＡＥＳ  ａｎｄ  ｉｔｓ  Ｓｅｃｕｒｉｚｅｄ  Ｉｍｐｌｅｍｅｎｔａｔｉｏｎ」、ＣＨＥＳ２００２、において説明される方法は、マスクされた入力ベクトルｘ＋ＲにＲを乗じてｘＲ＋Ｒ2を取得するステップと、Ｒ2をその結果に加えてＸＲを取得するステップと、ＸＲを逆数にしてＸ-1Ｒ-1を取得するステップと、１をＸ-1Ｒ-1に加えてＸ-1Ｒ-1＋１を取得するステップと、Ｒをその結果に乗じてＸ-1＋Ｒを取得するステップとを含む。
【０００７】
Ｔｒｉｃｈｉｎａ，  Ｅ．らによって説明される方法を用いてＡＥＳデータのマスクされた逆演算を行うには、ＧＦ（２8）全体にわたって、２回の乗算と、１回の平方と、２回の加算とが必要である。こうした逆演算のハードウェア実装は、相対的に複雑であり、及び／又は、電力消費が大きいものとなる場合がある。例えば、ハードウェア実装は、２５６バイトの大きさを持つ平方ルックアップテーブル（ＬＵＴ）と、ＧＦ（２8）における乗算のための２つの乗算回路とを用いることが必要な場合がある。
【発明の開示】
【０００８】
本発明の実施形態は、マスクされた入力データを第２表現に変換し、第１表現の演算と等価の演算を第２表現で実行して、マスクされた操作済みデータを取得することによって、有限体の第１表現で与えられるマスクされたデータを効率的に操作するための、例えば第１表現で与えられるマスクされた入力データの反転を実行するための方法及び装置を提供する。
【０００９】
本発明の実施形態によれば、マスクされたデータを操作する方法は、第１表現のマスクされた入力データを有限体における第２表現の変換済みデータに変換し、該変換済みデータを操作して、マスクされた操作済みデータを取得するステップを含むことができる。
【００１０】
幾つかの実施形態によれば、本方法はまた、マスクされた入力データの入力マスクを、第２表現の更新済みマスクに変換するステップを含むことができる。変換済みデータを操作するステップは、更新済みマスクを用いて該変換済みデータを操作するステップを含むことができる。
【００１１】
本発明の実施形態によれば、入力データを変換することにより、更新済みマスクによってマスクされた状態の変換済みデータを得ることができる。変換済みデータを操作することにより、更新済みマスクによってマスクされた状態の操作済みデータを得ることができる。
【００１２】
本発明の幾つかの実施形態によれば、変換済みデータを操作するステップは、第１表現の少なくとも１つの所望の演算と等価の少なくとも１つの演算を行うステップを含むことができる。
【００１３】
幾つかの例示的な実施形態によれば、変換済みデータを操作するステップは、該変換済みデータに更新済みマスクを乗じて第１中間データを取得し、該第１中間データに該更新済みマスクの平方を加えて第２中間データを取得し、該第２中間データを反転して第３中間データを取得し、該第３中間データに単位データ・ビットを加えて第４中間データを取得し、該第４中間データに該更新済みマスクを乗じて第２表現のマスクされた反転データを取得するステップを含むことができる。
【００１４】
本発明の幾つかの実施形態によれば、本方法は、操作済みデータを逆変換して、第１表現の逆変換済みデータを取得するステップを含むことができる。操作済みデータを逆変換することにより、入力マスクの線形変換によってマスクされた状態の逆変換済みデータを得ることができる。
【００１５】
本発明の幾つかの実施形態によれば、有限体はガロア体（ＧＦ）を含むことができる。
【００１６】
幾つかの例示的な実施形態によれば、第１表現はＧＦ（２2s）を含むことができ、第２表現はＧＦ（（２s）2）を含むことができる。これらの実施形態の幾つかによれば、ｓは４と等しいものとすることができ、すなわち、第１表現はＧＦ（２8）を含むことができ、第２表現はＧＦ（（２4）2）を含むことができる。
【００１７】
本発明の幾つかの実施形態によれば、マスクされた入力データを操作するための装置は、第１表現のマスクされた入力データを第２表現の変換済みデータに変換する変換ブロックを含むことができる。変換ブロックは、マスクされた入力データの入力マスクを更新済みマスクに変換することもできる。この装置はまた、第２表現の変換済みデータを操作する操作ブロックと、操作済みデータを変換して第１表現の逆変換済みデータにする逆変換ブロックとを含む。操作ブロックは、第２表現の変換済みデータを反転する反転ブロックを含むことができる。逆変換済みデータは、入力マスクのアフィン変換によってマスクすることができる。
【００１８】
本発明の例示的な実施形態によれば、変換ブロックは、第１表現のマスクされた入力データを変換して、対応する第２表現の変換済みデータにする入力変換モジュールを含むことができる。変換ブロックは、入力マスクを変換して更新済みマスクにするマスク変換モジュールを含むこともできる。幾つかの実施形態によれば、マスク変換モジュールによって行われる入力マスクの変換は、入力変換モジュールによって行われる変換と関連させることができる。
【００１９】
例示的な実施形態によれば、反転ブロックは、入力変換モジュールの出力とマスク変換モジュールの出力とを乗算する第１乗算器と、該マスク変換モジュールの出力の平方を与える平方モジュールとを含むことができる。反転ブロックはまた、平方モジュールの出力を第１乗算器の出力に加える第１加算器と、該第１加算器の出力がゼロでない場合にはゼロ出力値を与えるゼロ検出器と、該ゼロ検出器の出力とマスク変換モジュールの出力との論理ＡＮＤに対応する出力を与えるＡＮＤゲートとを含むことができる。反転ブロックはさらに、ＡＮＤゲートの出力を第１加算器の出力に加える第２加算器と、該第２加算器の出力を反転する反転モジュールと、該反転モジュールの出力に単位値を加える第３加算器と、該第２加算器の出力を用いてマスク変換モジュールの出力を乗算する第２乗算器と、該第２乗算器の出力をＡＮＤゲートの出力に加える第４加算器とを含むことができる。
【００２０】
本発明の例示的な実施形態によれば、逆変換ブロックは、第２表現の操作済みデータを逆変換して、対応する第１表現の逆変換済みデータにする出力逆変換モジュールを含むことができる。逆変換ブロックは、更新済みマスクを逆変換するマスク逆変換モジュールを含むこともできる。幾つかの実施形態によれば、マスク逆変換モジュールによって行われる更新済みマスクの逆変換は、出力逆変換モジュールによって行われる変換と関連させることができる。
【発明を実施するための最良の形態】
【００２１】
発明と考えられる対象は、特許請求の範囲において具体的に指摘され、厳密に請求される。しかしながら、本発明は、作動の機構及び方法のいずれに関しても、その目的、特徴、及び利点と併せて、添付図面と共に読んだときに以下の詳細な説明を参照することによって最も良く理解されることになる。
【００２２】
図に示される要素は、説明を簡単かつ明確にするために、必ずしも正確に又は縮尺通りに描かれていないことが分かるであろう。例えば、要素の幾つかの寸法は、明確にするために他の要素に対して強調される場合があるか、又は、幾つかの物理コンポーネントが、１つの要素に含まれる場合がある。さらに、適切であると考えられる場合には、対応する要素又は類似の要素を示すために、参照番号が図面間で繰り返されることがある。これらの図面は、本発明の実施形態の例を提示するものであり、本発明の範囲を制限することを意図していないことが分かるであろう。
【００２３】
以下の詳細な説明においては、本発明が完全に理解されるように、多くの具体的な詳細が記載される。しかしながら、当業者であれば、本発明は、それらの具体的な詳細なしに実施できることが分かるであろう。他の場合においては、本発明を分かり難くしないように、周知の方法、手順、及び要素を詳細に説明していない。
【００２４】
以下の詳細な説明においては、ＧＦ（２2s）という表記は、モジュロｐ（ｔ）を取るＧＦ（２）上の複数の多項式で構成されるＧＦ（２）の拡大体としての位数２2sのガロア体（ＧＦ）表現を指し、ここでｐ（ｔ）は、ＧＦ（２）上の２ｓ次既約多項式である。多項式は、２ｓビットの文字列によって、ＧＦ（２2s）表現で表すこともできる。ＧＦ（２2s）表現の要素ｕは、２ｓ桁の２進数ｕ＝［ｕ2s-1ｕ2s-2．．．ｕ1ｕ0］によって定めることができ、ここでｕiは、対応する多項式、例えばｕ2s-1ｔ2s-1＋ｕ2s-2ｔ2s-2＋．．．ｕ1ｔ＋ｕ0におけるｔiの係数である。
【００２５】
ＧＦ（（２s）2）という表記は、モジュロｒ（ｔ）を取るＧＦ（２s）上の複数の多項式で構成されるＧＦ（２s）の拡大体としての位数２2sのＧＦ表現を指し、ここでｒ（ｔ）は、ＧＦ（２s）上の２次既約多項式、すなわち、α及びβがＧＦ（２s）の要素である場合のｒ（ｔ）＝ｔ2＋αｔ＋βである。ＧＦ（２s）は、モジュロｑ（ｔ）を取るＧＦ（２）上の複数の多項式で構成されるＧＦ（２）の拡大体として表現され、ここでｑ（ｔ）は、ＧＦ（２）上の２次既約多項式である。ＧＦ（（２s）2）表現の要素ｚは、線形多項式ｚ<m>ｔ＋ｚ<l>を表す２ｓ桁の二進数ｚ＝［ｚ2s-1ｚ2s-2．．．ｚ1ｚ0］によって定めることができ、ここでｚ<m>＝［ｚ2s-1．．．ｚs+1ｚs］及びｚ<l>＝［ｚs-1．．．ｚ1ｚ0］は、モジュロｑ（ｔ）を取る多項式によって表されるＧＦ（２s）の要素である。
【００２６】
ここで説明される本発明の幾つかの例示的な実施形態は、データを、有限体、例えばＧＦの２元体表現、例えばＧＦ（２2s）表現で参照することができる。しかしながら、当業者であれば、本発明の実施形態は、他のいずれかの表現のデータ、例えばｇ及びｈがいずれかの所望の値を有するＧＦ（ｇh）表現のデータについて、実施できることが分かるであろう。
【００２７】
所定の有限体のベクトルｘを含む入力データをマスクすることは、該所定の有限体からランダムに選択される要素であるＲで示される入力ランダム・マスクをｘに加えること、すなわち、マスクされた入力データ、例えばｘ＋Ｒを取得することを含む。
【００２８】
本発明の幾つかの実施形態にしたがってマスクされたデータを操作する方法のフローチャートを概略的に示す図１を参照する。
【００２９】
ブロック１０２に示されるように、本方法は、例えば入力データ及び入力ランダム・マスクの組み合わせを含む、例えばＧＦといった所定の有限体における第１表現のマスクされた入力データを、例えば詳細に後述されるように該第１表現のマスクされた入力データに変換演算子を適用することによって変換し、所定の有限体における第２表現のマスクされた変換済みデータにすることを含むことができる。
【００３０】
ブロック１０４に示されるように、本方法は、第１表現の入力ランダム・マスクを、詳細に後述されるように第２表現の更新済みマスクに変換することを含むことができる。
【００３１】
ブロック１０６に示されるように、本方法はまた、例えば更新済みマスクを用いて変換済みデータを操作し、詳細に後述されるように第２表現のマスクされた操作済みデータを取得することを含むことができる。
【００３２】
ブロック１０８に示されるように、本方法はさらに、逆変換演算子を適用することによって操作済みデータを逆変換して第１表現に戻し、詳細に後述されるように第１表現のマスクされた逆変換済みデータを取得することを含むことができる。
【００３３】
ブロック１０９に示されるように、本方法はまた、例えば後述のように、マスクされた逆変換済みデータのマスクを取ることを含むことができる。
【００３４】
ブロック１０１に示されるように、本方法はまた、例えば後述のように、入力ランダム・マスクを生成することを含むことができる。
【００３５】
ブロック１０３に示されるように、本方法はまた、例えば当該技術分野で知られるように入力マスクを入力データに加えることによって、例えば入力マスクを用いて入力データをマスクし、マスクされた入力データを取得することを含むことができる。
【００３６】
本発明の幾つかの実施形態によれば、変換演算子は、第１表現のデータを対応する第２表現のデータに変換するためのいずれかの適切な演算子を含むことができる。幾つかの例示的な実施形態によれば、変換演算子は、例えば、２００３年８月６日に出願され、本発明の出願人に譲渡され、開示が引用によりここに組み入れられる「Ｍｅｔｈｏｄ  ａｎｄ  ｄｅｖｉｃｅ  ｏｆ  ｍａｎｉｐｕｌａｔｉｎｇ  ｄａｔａ  ｉｎ  Ｆｉｎｉｔｅ  Ｆｉｅｌｄ」という名称の国際特許出願ＰＣＴ／ＩＬ０３／００６４７号において説明されるように、所望の変換に対応する表現変換行列を含むことができる。本発明の幾つかの例示的な実施形態によれば、変換演算子は、後述のように、表現変換行列と、例えば復号化アフィン変換又は暗号化アフィン変換といったアフィン変換との組み合わせを含むことができる。
【００３７】
当該技術分野において知られているように、同じ大きさのいずれか２つの有限体は同型であるため、所定の有限体、例えばＧＦ（２n）の、それぞれＲｅｐ1及びＲｅｐ2と表される２つの表現の間に、同型が存在することになる。２つの表現の各々はＧＦ（２）上のｎ次元の線形空間とすることができ、各々の同型は該表現間の線形変換とすることができる。したがって、本発明の幾つかの実施形態の一部として、例えば行列乗算によりＲｅｐ1の要素をＲｅｐ2の対応する要素に変換するために、ｎ×ｎ二進表現変換行列Ｍを計算することができる。２つの体表現の間の変換は可逆的であるため、各々の表現変換について、表現変換逆行列Ｍ-1が存在することができる。根ｎを持つ既約多項式ｐ0がＲｅｐ1を表すものとすることができる。ｐ0の各々の根は、ＧＦ（２n）の生成器であり、体の同型の下でも不変である。したがって、各々の体の拡大について、ｎ個の対応する表現変換行列が存在する。ＧＦ（２n）の乗法群は巡回群であるため、表現Ｒｅｐ1及びＲｅｐ2の対応するそれぞれの生成器の組は、Ｒｅｐ1とＲｅｐ2との間の同型を独自のものとして定めることができる。したがって、Ｒｅｐ1の生成器ベクトルｒ1及びＲｅｐ2の生成器ベクトルｒ2について、対応する表現変換行列Ｍは、Ｍｒ1＝ｒ2を満足しなければならない。（ｒi）kは、表現Ｒｅｐiの要素（ｒ1）kを生成するために、表現Ｒｅｐiの体生成器ｒiをｋ乗することを示し、表現Ｒｅｐ1の体要素（ｒ1）kは、ＧＦ（２）上のｎ次元線形空間におけるベクトルとして扱うことができ、表現変換行列Ｍを乗じてＭ（ｒ1）kを与えることができるものとすると、２つの体表現が同型であり、ｒ1及びｒ2がＧＦ（２n）の生成器であるため、Ｍはあらゆるｋ（ｋ＝１．．．２n）について以下の方程式系、
Ｍ（ｒ1）k＝（ｒ2）k      （１）
を満足しなければならない。
【００３８】
方程式系１は２n線形方程式を含み、それを解いて、生成器ｒ1及びｒ2の組に対応する表現変換行列Ｍを求めることができる。方程式系１は、計算数を減らすために無視することができる冗長方程式を含むことがある。例えば、最初のｎ個の方程式のみを用いて、１つの表現変換行列を与えることができる。生成器ｒ1及びｒ2の異なる組を用いる方程式系１の解によって、別の表現変換行列を与えることができる。したがって、各々がｒ1の「像」を定めるＲｅｐ2のｎ個の異なる生成器に対応するｎ個の異なる方程式系が存在し、それによって、Ｒｅｐ1からＲｅｐ2へのｎ個の異なる表現変換行列が与えられることになる。
【００３９】
本発明の例示的な実施形態においては、ＧＦ（２8）上の既約多項式、例えばｐ（ｔ）＝ｔ8＋ｔ4＋ｔ3＋ｔ＋１の各々の根は、ＧＦ（２8）体の生成器とすることができる。したがって、既約多項式の８つの根にそれぞれ対応する８つの可能な表現変換行列を、ＧＦ（２8）の各々の拡大体について計算することができる。ＧＦ（２）上のＧＦ（２4）の多項式表現は、ＧＦ（２4）上の３つの既約簡約多項式、例えば１＋ｔ＋ｔ4、１＋ｔ3＋ｔ4、１＋ｔ＋ｔ2＋ｔ3＋ｔ4の各々によって定めることができる。ＧＦ（２8）におけるＧＦ（２4）の１つ又はそれ以上の多項式表現の体拡大は、既約拡大多項式、例えばβ及びαがＧＦ（２4）の要素でありＧＦ（２4）上で既約であるようなｔ2＋αｔ＋β型の多項式を用いて、計算することができる。本発明の例示的な実施形態によれば、ｔ2＋αｔ＋β形式の１２０個の可能な既約拡大多項式を与える１５個の異なるβ値及び８個の異なるα値が存在する。３個の異なる簡約多項式及び１２０個の既約拡大多項式によって、ＧＦ（２）の拡大体としてＧＦ（２8）の３６０個の異なるＧＦ（（２4）2）表現が得られる。したがって、これらの例示的な実施形態によれば、３６０個の体拡大に対応して、２８８０個の可能な表現変換行列が存在することになる。本発明の幾つかの実施形態によれば、可能な表現変換行列の各々は、標準的なＡＥＳ表現から、ＧＦ（２4）の異なる拡大に対応するＧＦ（２8）の異なるＧＦ（（２4）2）表現への変換を可能にする。したがって、表現変換行列Ｍは、例えば選択されたＭに対応するハードウェア実装の複雑性といったいずれかの所望の基準に従って、あらかじめ選択することができる。
【００４０】
第１表現のベクトルｘを含む入力データは、表現変換、例えば表現変換行列Ｍを適用することによって、第２表現に変換することができる。第２表現のＴ（ｘ）で表される演算ｘ＞ｘ-1を、変換済みデータ、例えばＭ・ｘに対して実行することができる。表現変換の逆数、例えばＭ-1を適用することによって、操作済みデータを第１表現に戻す逆変換Ｆ（ｘ）を取得することができる。したがって、本発明の例示的な実施形態によれば、以下の非線形方程式、
Ｆ（ｘ）＝Ｍ-1・Ｔ（Ｍ・ｘ）      （２）
によって、Ｆ（ｘ）及びＴ（Ｍ・ｘ）を与えることができる。
【００４１】
本発明の例示的な実施形態によれば、第１表現のマスクされた入力データｘ＋Ｒは、第２表現の変換済みデータＭｘ＋ＭＲに変換することができる。上述のように、第１表現と第２表現との間の変換は反転可能な変換であるため、表現変換行列Ｍは正則行列である。したがって、ＭＲは、Ｒに対応して、有限体のいずれかの非ゼロ値を取ることができる。したがってまた、変換済みデータＭｘ＋ＭＲは、マスクが更新済みマスク、例えばＭＲを含むものとした場合、マスクされた変換済みデータを含むことができる。
【００４２】
本発明の例示的な実施形態によれば、入力マスクＲは非ゼロ値を取ることができる。非ゼロのランダム・マスクを取得するために、例えば後述するようないずれかの適切な非ゼロのランダム・マスク生成器を実装することができる。
【００４３】
本発明の幾つかの例示的な実施形態によれば、変換済みデータを操作することは、例えば後述するように変換済みデータを反転することを含むことができる。変換済みデータを反転することは、例えば後述するように、更新済みマスクを用いることを含むことができる。
【００４４】
本発明の例示的な実施形態によれば、マスクされた変換済みデータを反転することは、変換済みデータ、例えばＭｘ＋ＭＲに更新済みマスクＭＲを乗じて、第１中間データ、例えばＭｘＭＲ＋（ＭＲ）2を取得することを含むことができる。マスクされた変換済みデータを反転することはまた、更新済みマスクの平方、例えば（ＭＲ）2を第１中間データに加えて、第２中間データ、例えばＭｘＭＲを取得することを含むことができる。変換済みデータを反転することはさらに、第２中間データＭｘ＋ＭＲを反転して、第３中間データ、例えば（ＭｘＭＲ）-1を取得することを含むことができる。変換済みデータを反転することはさらに、単位データ・ビットすなわち１を第３中間データに加えて、第４中間データ、例えば（ＭｘＭＲ）-1＋１を取得することを含むことができる。変換済みデータを反転することはさらに、第４中間データに更新済みマスクＭＲを乗じて、第２表現のマスクされた反転済みデータ、例えば（Ｍｘ）-1＋ＭＲを取得することを含むことができる。加算、乗算、及び／又は反転といった演算の少なくとも幾つかは、第２表現で行うことができる。第２表現の演算は、例えば後述のように、いずれかの適切な回路及び／又はルックアップテーブル（ＬＵＴ）によって実装することができる。
【００４５】
本発明の幾つかの実施形態によれば、逆変換演算子は、第２表現のデータを逆変換して、対応する第１表現のデータに戻すためのいずれかの適切な演算子を含むことができる。本発明の例示的な実施形態によれば、逆変換演算子は、上述のように、行列Ｍ-1による乗算を含むことができる。逆変換演算子を適用した結果は、方程式２、例えばＭ-1［（Ｍｘ）-1］＝ｘ-1に従って計算できることが分かるであろう。したがって、第１表現のマスクされた反転済みデータ、例えばｘ-1＋Ｒは、第２表現のマスクされた反転済みデータ、例えば（Ｍｘ）-1＋ＭＲに逆変換演算子を適用することによって取得することができる。本発明の幾つかの例示的な実施形態によれば、逆変換演算子は、行列Ｍ-1と、例えば後述のようなアフィン変換、例えば復号化アフィン変換又は暗号化アフィン変換との組み合わせを含むことができる。
【００４６】
図２を参照すると、本発明の幾つかの例示的な実施形態にしたがって、マスクされたデータを操作するための装置２００の回路実装が概略的に示される。
【００４７】
本発明の例示的な実施形態によれば、装置２００は、第１表現のマスクされた入力データを対応する第２表現のマスクされたデータに変換する変換ブロック２０２を含むことができる。ブロック２０２は、マスクＲを第２表現の更新済みマスクに変換するように構成することもできる。装置２００はまた、第２表現の変換済みデータを操作、例えば反転する操作ブロック、例えば反転ブロック２０４と、操作済みデータを逆変換して第１表現の逆変換済みデータにする逆変換ブロック２０６とを含むことができる。
【００４８】
本発明の例示的な実施形態によれば、ブロック２０２は、第１表現のマスクされた入力データｘ＋Ｒを対応する第２表現の変換済みデータに変換する入力変換モジュール２０８を含むことができる。ブロック２０２はまた、入力マスクＲを更新済みマスクに変換するマスク変換モジュール２１０を含むことができる。変換済みのマスクされたデータに関連する更新済みマスクを取得するために、モジュール２１０によって行われるマスクの変換を、例えば後述のように、モジュール２０８によって行われる変換と関連させることができる。モジュール２０８及び／又はモジュール２１０は、例えば後述のように、第１表現のデータを変換して対応する第２表現のデータにするいずれかの回路、ルックアップテーブル（ＬＵＴ）、及び／又は、いずれかの適切なハードウェア及び／又はソフトウェアを含むことができる。当業者であれば、本発明の幾つかの他の実施形態にしたがって、モジュール２０８及び２１０を、例えばマスクされた入力データ及び入力マスクを逐次的に変換する１つの複合変換モジュールの形で実装できることが分かるであろう。
【００４９】
本発明の例示的な実施形態によれば、ブロック２０４は、モジュール２０８の出力２２６及びモジュール２１０の出力２２８と関連する第１乗算器２１２を含むことができる。ブロック２０４はまた、出力２２８と関連する平方モジュール２１４と、該モジュール２１４の出力２３０及び乗算器２１２の出力２３２と関連する第１加算器２１６とを含むことができる。ブロック２０４はさらに、加算器２１６の出力２３４と関連する反転モジュール２１８と、モジュール２１８の出力２３６と関連し、単位値すなわち値１を持つ信号を受信する入力２４０を有する第２加算器２２０とを含むことができる。ブロック２０４はさらに、出力２２８及び加算器２２０の出力２４２と関連する第２乗算器２２２を含むことができる。乗算器２１２及び／又は乗算器２２２は、例えば後述のように、第２表現を用いて第１表現の２つの要素を乗じるいずれかの回路、ルックアップテーブル（ＬＵＴ）、及び／又は、いずれかの適切なハードウェア及び／又はソフトウェアを含むことができる。ユニット２１４は、例えば後述のように、第２表現を用いて第１表現の１つの要素の平方を与えるいずれかの回路、ルックアップテーブル（ＬＵＴ）、及び／又は、いずれかの適切なハードウェア及び／又はソフトウェアを含むことができる。反転モジュール２１８は、例えば後述のように、第２表現を用いて第１表現のデータを反転するいずれかの回路、ルックアップテーブル（ＬＵＴ）、及び／又は、いずれかの適切なハードウェア及び／又はソフトウェアを含むことができる。加算器２１６及び２２０は、２つの要素の加算を実施するいずれかのソフトウェア及び／又はハードウェアを含むことができる。例えば、加算器２１６及び／又は加算器２２０は、当該技術分野において知られているように、ＸＯＲゲートを含むことができる。
【００５０】
本発明の例示的な実施形態によれば、ブロック２０６は、ブロック２０４の出力２４３と関連する逆変換モジュール２２４を含むことができる。モジュール２２４は、例えば後述のように、第２表現のデータを逆変換して対応する第１表現の逆変換済みデータにするいずれかの回路、ルックアップテーブル（ＬＵＴ）、及び／又は、いずれかの適切なハードウェア及び／又はソフトウェアを含むことができる。
【００５１】
本発明の例示的な実施形態によれば、モジュール２０８、２１０、及び／又は２２４は、それぞれ、Ｍによる乗算、Ｍによる乗算、及びＭ-1による乗算を実行する、例えば後述のような乗算器を含むことができる。したがって、出力２２６はＭｘ＋ＭＲに対応する値を取ることができ、出力２２８はＭＲに対応する値を取ることができる。したがって、出力２４３は（Ｍｘ）-1＋ＭＲに対応する値を取ることができ、ブロック２０６の出力２４４は、ｘ-1＋Ｒに対応する値を取ることができる。この実施形態によれば、ブロック２０２及び２０４の出力は、更新済みマスクＭＲによってマスクすることができ、ブロック２０６の出力は、入力マスクＲによってマスクすることができる。このように、ブロック２０２、２０４、及び２０６の出力は、入力マスク又は更新済みマスクのいずれかによってマスクできることが分かるであろう。
【００５２】
例示的な実施形態によれば、装置２００は、少なくとも２つのＸＯＲゲート２１６及び２２０と、第２表現の２つの乗算回路２１２及び２２２と、第２表現の１つの平方回路又はＬＵＴ２１４と、例えば後述のように、ｎ×ｎビット行列、例えばＭにベクトルを乗じるための３つの乗算回路２０８、２１０、及び２２４とを含むことができる。
【００５３】
当業者であれば、本発明の実施形態にしたがってマスクされたデータを操作するための装置、例えば装置２００のハードウェア実装を、従来型のマスク反転装置と比べてより単純なものにし、したがってより小型にできることが分かるであろう。例えば、第１表現がＧＦ（２2s）表現を含み、第２表現がＧＦ（（２s）2）表現を含む場合には、第２表現の平方ＬＵＴは、２sｓビットを含むことができる。本発明の実施形態によれば、平方ＬＵＴのビットサイズは、第１表現の平方ＬＵＴのビットサイズ、例えば２2s+1ｓと比べて、より小さなものとすることができる。さらに、従来型のマスク反転装置は、第１表現の乗算を行う乗算回路を実装することが必要な場合がある。これらの回路は、本発明の実施形態によって実装される乗算器と比べてより複雑な場合がある。
【００５４】
幾つかの例示的な実施形態によれば、上述の方法及び／又は装置は、後述のように、例えばマスクされたＡＥＳ  Ｓ−ｂｏｘ暗号化／復号化演算を行うことによって、マスクされた入力データｘ＋Ｒを暗号化及び／又は復号化するために、実装することができる。
【００５５】
分かりやすくするために、本発明の幾つかの実施形態の説明の一部として、データを暗号化する装置及び／又は方法に対して言及する場合があるが、本発明の範囲はこの点に限定されるものではない。本発明のさらなる実施形態は、データを復号化する装置及び／又は方法を参照して説明することができる。しかしながら、当業者であれば、暗号化装置、復号化装置、及び／又は、暗号化と復号化の両方を組み合わせた装置を実装するために、ここで説明される本発明の方法及び／又は装置をどのように修正し、及び／又は、適用すべきかが明らかであろう。特に指定のない限り、ここで説明される方法及び装置の原理は、いずれかのこうした修正及び／又は適用と併せて実装されるように意図される。
【００５６】
本発明の幾つかの例示的な実施形態においては、ｓは４に等しい。これらの実施形態は、ＧＦ（２8）表現のデータをＧＦ（（２4）2）表現に変換するのに有用である。
【００５７】
分かりやすくするために、本発明の幾つかの実施形態の説明は、ｓが４に等しい、すなわちＧＦ（２8）表現のデータをＧＦ（（２4）2）表現に変換するための方法及び／又は装置に関するものであるが、本発明の範囲はこの点に限定されるものではない。しかしながら、当業者であれば、他のいずれかの適切なｓの値について、ここで説明される方法及び／又は装置をどのように適宜に修正すべきかが明らかであろう。
【００５８】
本発明の幾つかの実施形態の説明の一部として、本方法及び／又は装置は、様々な組み合わせ及び形態で実装することができる。本発明の例示的な実施形態によれば、暗号化を行う暗号化ブロック、及び／又は、復号化を行う復号化ブロックは、例えばスマートカードに用いることができるタイプの組み込み電気回路に実装することができる。ＡＥＳ  ＧＦ（２8）表現からＧＦ（（２4）2）に、及びＧＦ（（２4）2）からＧＦ（２8）に、データを変換するために用いることができる変換演算子は、例えばスマートカードに事前プログラムすることができる。付加的又は代替的に、他の構成を用いることができる。
【００５９】
従来型のＡＥＳ  Ｓ−ｂｏｘは、以下の方程式、
2006517036.tif 000003
2006517036.tif 000004
に従ってアフィン変換を行うことができ、ここで、当該技術分野において知られているように、ｓｂｏｘ［ｘ］は暗号化に関する変換を表し、ｓｂｏｘ-1［ｘ］は復号化に関する変換を表し、Ａ及びｂはＡＥＳ  Ｓ−ｂｏｘパラメータ行列である。
【００６０】
したがって、本発明の実施形態によれば、方程式２をそれぞれ方程式３及び４に代入し、両方程式においてｘを（ｘ＋Ｒ）と置き換えることによって、マスクされたデータｘ＋Ｒを第２表現に変換し、第２表現で演算を行い、得られたデータを対応する第１表現、例えばＡＥＳ表現に逆変換するための以下の修正方程式を取得することができる。
2006517036.tif 000005
2006517036.tif 000006
【００６１】
本発明の幾つかの実施形態に従って、変換回路又はソフトウェアは、表現変換行列Ｍを実装する回路を含むことができる。こうした実施形態の幾つかによれば、表現変換行列Ｍを実装する回路又はソフトウェアは、線形変換例えばＡを実装する回路又はソフトウェアと組み合わせことができる。本発明のさらなる実施形態によれば、変換回路又はソフトウェアは、それぞれＡＭ-1、ＭＡ-1、Ｍ、及びＭ-1によって乗算するための、例えば後述のような４つの乗算モジュールを含むことができる。このように、変換回路は、アフィン変換、例えばＡによる乗算及び／又はｂの加算の適用と、所定の表現変換、例えばＭによる乗算の適用との組み合わせで構成することができる。こうした演算モジュールの使用により、変換回路の効率を向上させることができる。
【００６２】
行列乗算のハードウェア実装は、当該技術分野において知られているように、いずれかの行列乗算のハードウェア実装を含むことができる。例えば、ｉ＝１．．．ｎであり、Ｄが固定されたｎ×ｎの二値行列であるとすると、ｙ＝Ｄｘによって定められるブロックｙの値ｙiは、以下の方程式、
2006517036.tif 000007
を用いて計算することができる。
【００６３】
このように、ｙの値は、方程式７を用いて計算することができる。これは、行Ｄiのどの要素が非ゼロであるかを求め、対応するｘjの値のＸＯＲ演算を行うことによって、達成することができる。
【００６４】
本発明の例示的な実施形態によれば、ＡＥＳ演算と等価の演算、例えば、逆演算、加算演算、及び／又は乗算演算は、後述のように、第２表現、例えばＧＦ（（２4）2）表現で定めることができる。
【００６５】
ＧＦ（２8）の要素ｘは、八桁の二進数ｘ＝［ｘ7ｘ6ｘ5ｘ4ｘ3ｘ2ｘ1ｘ0］によって定めることができ、ＧＦ（２4）の要素ｚは、四桁の二進数ｚ＝［ｚ3ｚ2ｚ1ｚ0］によって定めることができる。
【００６６】
当該技術分野において知られているように、ＧＦ（２4）は、ＧＦ（２）上の簡約多項式によって定められる多項式表現を持つことができ、例えばｚ＝［ｚ3ｚ2ｚ1ｚ0］は、多項式ｚ0＋ｚ1ｔ＋ｚ2ｔ2＋ｚ3ｔ3によって表すことができる。ＧＦにおける要素の乗算は、該要素を表す多項式を乗算し、その結果のモジュロを簡約多項式に約分することによって定めることができる。
【００６７】
本発明の実施形態によれば、ＧＦ（２8）のビット・オクテットｚ＝［ｚ7ｚ6ｚ5ｚ4ｚ3ｚ2ｚ1ｚ0］は、線形多項式ｚ<m>ｔ＋ｚ<l>と相似のものとすることができ、ここで、ｚ<m>＝［ｚ7ｚ6ｚ5ｚ4］及びｚ<l>＝［ｚ3ｚ2ｚ1ｚ0］はＧＦ（２4）の要素である。したがって、第２表現は、ＧＦ（２4）の要素ｚ<m>及びｚ<l>を含むことができる。
【００６８】
本発明の幾つかの実施形態の一部として、第２表現の乗算演算及び加算演算は、ＧＦ（２4）における演算に関して定めることができる。以下に与えられるのは、ＧＦ（２4）上の演算に関する、第２表現の乗算及び加算の１つの可能な定義である。本発明の幾つかの実施形態の一部として、他の定義を用いることもできることが分かるであろう。
【００６９】
第１表現の２つの要素、例えばａ，ｄ∈ＧＦ（２8）の、第２表現での加算及び減算は、当該技術分野において知られているように、該２つの要素のビット単位のＸＯＲとして定めることができる。２つの要素ａ及びｄの積は、多項式の積（ａ<m>ｔ＋ａ<l>）×（ｄ<m>ｔ＋ｄ<l>）ｍｏｄ（ｔ2＋αｔ＋β）として定めることができ、ここで多項式の係数の乗算及び加算は、所与の表現を用いるＧＦ（２4）上の演算によって定めることができる。したがって、要素ａ及びｄの積は、以下の方程式、
（ａ<m>ｔ＋ａ<l>）×（ｄ<m>ｔ＋ｄ<l>）（ｍｏｄ  ｔ2＋αｔ＋β）＝
（ａ<l>ｄ<m>−ａ<m>ｄ<m>α＋ａ<m>ｄ<l>）ｔ−ａ<m>ｄ<m>β＋ａ<l>ｄ<l>≡ｒ<m>ｔ＋ｒ<l>      （８）
を用いて計算することができ、ここで、
（ａ<l>ｄ<m>−ａ<m>ｄ<m>α＋ａ<m>ｄ<l>）≡ｒ<m>≡［ｒ7ｒ6ｒ5ｒ4］
ａ<m>ｄ<m>β＋ａ<l>ｄ<l>≡ｒ<l>≡［ｒ3ｒ2ｒ1ｒ0］      （９）
である。
【００７０】
したがって、ＡＥＳ表現すなわちＧＦ（２8）表現の要素ａ及びｄの積は、ｒ＝［ｒ7ｒ6ｒ5ｒ4ｒ3ｒ2ｒ1ｒ0］と定めることができる。このように、ＡＥＳ表現の要素ａ及びｄの積は、例えば方程式の組９に従い、ＧＦ（２4）上の一連の加算演算及び乗算演算を用いて計算することができる。当業者であれば、ＧＦ（２4）においてマイナス記号とプラス記号とは置換可能であることが分かるであろう。したがって、方程式の組９の第１式のマイナス記号は、例えば後述のように、プラス記号と置き換えることができる。
【００７１】
図３Ａを参照すると、本発明の幾つかの例示的な実施形態にしたがって、乗算器３０２の回路実装が概略的に示される。
【００７２】
乗算器３０２は、２つのＧＦ（２4）要素を乗じるための乗算ユニット３０４、３０６、及び３１６と、２つのＧＦ（２4）要素を乗じ、該２つの要素の積にβを乗じるためのβ乗算ユニット３０８とを含むことができる。ユニット３０４、３０６、３０８、及び３１６は、例えば後述のように、２つのＧＦ（２4）要素の乗算を行うためのいずれかの適切なＬＵＴ及び／又は回路を含むことができる。当該技術分野において知られているように、乗算器３０２はまた、ＸＯＲゲート３１０、３１２、及び３１４を含むことができる。
【００７３】
ＡＥＳ表現の要素ａの平方は、方程式の組９にａ＝ｄを代入することによって計算することができる。例えば上述のように方程式の組９の第１式のマイナス記号をプラス記号で置き換えた場合には、以下の方程式の組、
２ａ<l>ａ<m>＋ａ<m>2α≡ｒ<m>≡［ｒ7ｒ6ｒ5ｒ4］
ａ<m>2β＋ａ<l>2≡ｒ<l>≡［ｒ3ｒ2ｒ1ｒ0］      （１０）
を用いることができる。
【００７４】
図３Ｂを参照すると、本発明の幾つかの例示的な実施形態にしたがって、平方ユニット３２０の回路実装が概略的に示される。
【００７５】
平方ユニット３２０は、ＧＦ（２4）要素の平方に対応する値をそれぞれが含むＬＵＴ３２２及び３２４と、ＧＦ（２4）要素の平方にβを乗じたものに対応する値を含むＬＵＴ３２６とを含むことができる。ＬＵＴ３２２、３２４、及び３２６は、例えば後述のように、いずれかの適切なＬＵＴを含むことができる。平方ユニット３２０はまた、当該技術分野において知られているＸＯＲゲート３２８を含むことができる。
【００７６】
データ要素（ｘ<m>ｘ＋ｘ<l>）ｘ＝（ａ<m>ｔ＋ａ<l>）の逆数ｘ-1＝（ｃ<m>ｔ＋ｃ<l>）を求めるには、以下の方程式の組、
０ｘ＋１＝（ｃ<m>ｔ＋ｃ<l>）×（ａ<m>ｔ＋ａ<l>）＝
０ｘ＋１＝（ｃ<m>ｔ＋ｃ<l>）×（ａ<m>ｔ＋ａ<l>）ｍｏｄ（ｔ2＋αｔ＋β）＝
０ｘ＋１＝（ｃ<m>ａ<m>α＋ｃ<m>ａ<l>＋ｃ<l>ａ<m>）ｔ＋ｃ<l>ａ<l>＋ｃ<m>ａ<m>β      （１１）
を解くことが必要になる。
【００７７】
方程式の組１１は、ＧＦ（２）上の以下の線形方程式系、
ｃ<m>＝ａ<m>（ａ2<m>β＋ａ2<l>＋ａ<l>ａ<m>α）-1
ｃ<l>＝（ａ<l>＋ａ<m>α）（ａ2<m>β＋ａ2<l>＋ａ<l>ａ<m>α）-1      （１２）
に変換することができる。
【００７８】
したがって、データ要素ｘの逆数ｘ-1を計算するために、上述のように、Ｃ<m>及びＣ<l>の値を計算することができる。このように、ＡＥＳ表現の要素ｘの逆数は、方程式の組１２に従って、ＧＦ（２4）上の一連の加算演算、乗算演算、平方演算、及び逆演算を用いて計算することができる。
【００７９】
図３Ｃを参照すると、本発明の幾つかの例示的な実施形態にしたがって、反転モジュール３３０の回路実装が概略的に示される。
【００８０】
反転モジュール３３０は、例えば後述のように、２つのＧＦ（２4）要素を乗じるための乗算ユニット３３４、３４２、及び３４６を含むことができる。モジュール３３０はまた、例えば後述のように、ＧＦ（２4）要素の平方に対応する値を含む平方ＬＵＴ３３１と、ＧＦ（２4）要素の平方にβを乗じたもの対応する値を含むβ平方ＬＵＴ３３２とを含むことができる。モジュール３３０はさらに、例えば後述のように、ＧＦ（２4）要素の逆数に対応する値を含む反転ＬＵＴ３４４を含むことができる。モジュール３３０はまた、当該技術分野において知られているように、ＸＯＲゲート３４０及び３３８を含むことができる。
【００８１】
本発明の実施形態によれば、ＧＦ（２4）上の乗算は、後述のように、ＧＦ（２4）乗算器を定め、各々の場合について適切な乗算器を選択することによって、より効率的に行うことができる。
【００８２】
これらの例示的な実施形態によれば、ＧＦ（２4）の２つの要素、例えばａ＝［ａ3，ａ2，ａ1，ａ0］及びｄ＝［ｄ3，ｄ2，ｄ1，ｄ0］の、ＧＦ（２4）上の乗算ａ×ｄ＝［ａ3，ａ2，ａ1，ａ0］×［ｄ3，ｄ2，ｄ1，ｄ0］は、例えば上述のように、所与の簡約多項式について、一連のビット単位の演算、例えば加算（ＸＯＲ）及び乗算（ＡＮＤ）として定めることができる。したがって、例えば、２つの要素の乗算の解は、以下のようになる。
簡約多項式：ｔ4＋ｔ＋１
［ａ3，ａ2，ａ1，ａ0］＊［ｄ3，ｄ2，ｄ1，ｄ0］＝
［ａ1ｄ2＋ａ3ｄ3＋ａ3ｄ0＋ａ2ｄ1＋ａ0ｄ3，ａ2ｄ3＋ａ0ｄ2＋ａ3ｄ3＋ａ2ｄ0＋ａ1ｄ1＋ｄ2ａ3，ａ1ｄ3＋ｄ2ａ3＋ａ0ｄ1＋ａ2ｄ2＋ａ2ｄ3＋ａ1ｄ0＋ａ3ｄ1，ａ0ｄ0＋ａ1ｄ3＋ａ2ｄ2＋ａ3ｄ1］
簡約多項式：ｔ4＋ｔ3＋１
［ａ3，ａ2，ａ1，ａ0］＊［ｄ3，ｄ2，ｄ1，ｄ0］＝
［ａ0ｄ3＋ａ1ｄ3＋ａ3ｄ2＋ａ2ｄ3＋ａ3ｄ1＋ａ2ｄ1＋ａ1ｄ2＋ａ3ｄ3＋ａ3ｄ0＋ａ2ｄ2，ａ0ｄ2＋ａ3ｄ3＋ａ1ｄ1＋ａ2ｄ0，ａ0ｄ1＋ａ3ｄ2＋ａ3ｄ3＋ａ1ｄ0＋ａ2ｄ3，ａ1ｄ3＋ａ0ｄ0＋ａ2ｄ3＋ａ3ｄ2＋ａ2ｄ2＋ａ3ｄ1＋ａ3ｄ3］
簡約多項式：ｔ4＋ｔ3＋ｔ2＋ｔ＋１
［ａ3，ａ2，ａ1，ａ0］＊［ｄ3，ｄ2，ｄ1，ｄ0］＝
［ａ2ｄ1＋ａ3ｄ0＋ａ3ｄ1＋ａ1ｄ2＋ａ1ｄ3＋ａ2ｄ2＋ａ0ｄ3，ａ3ｄ1＋ａ2ｄ2＋ａ1ｄ1＋ａ2ｄ0＋ａ0ｄ2＋ａ1ｄ3，ａ0ｄ1＋ａ1ｄ3＋ａ1ｄ0＋ａ3ｄ1＋ａ3ｄ3＋ａ2ｄ2，ａ3ｄ2＋ａ1ｄ3＋ａ0ｄ0＋ａ2ｄ3＋ａ2ｄ2＋ａ3ｄ1］
【００８３】
解の各々における要素の乗算の幾つかは、２つ又はそれ以上の出力ビットについて類似となる場合があることに注意されたい。例えば、上に挙げた解の中に二度現れる式ａ1ｄ3＋ａ2ｄ2＋ａ3ｄ1は、ハードウェア要件を最小にするために、例えばＸＯＲゲート及びＡＮＤゲートを用いて一度だけ計算することができる。当業者であれば、上述の３つの二次簡約多項式の各々を使用する、ＧＦ（２4）における２つの要素の乗算の解を用いて、二次簡約多項式の各々についてＧＦ（２4）乗算器を構成できることが分かるであろう。こうした乗算器は、当該技術分野において知られているハードウェア及び／又はソフトウェアに実装することができる。所与の表現変換行列について、適切なＧＦ（２4）乗算器を構成することができる。上述のように、各々の表現変換行列は、拡大多項式と組み合わせて、ＧＦ（２4）上の３つの既約簡約多項式のうちの１つによって定めることができるため、ＧＦ（２4）乗算器はあらかじめ決定することができる。当業者であれば、本発明の例示的な実施形態にしたがって、付加的に又は代替的にＧＦ（２4）乗算器の他の適切な実装を使用できることが分かるであろう。
【００８４】
ＧＦ（２4）において、ＩＮＶと表示される反転と、ＳＱＲと表示される平方とは、例えば、１６ニブルといった８バイトのサイズを各々が持つ比較的小さな２つの個別のルックアップテーブル（ＬＵＴ）によって実装することができる。本発明の幾つかの実施形態によれば、係数βはあらかじめ決定することができる。したがって、要素ｇ∈ＧＦ（２4）についての値β×ｇ2を、βＳＱＲと表示することができる８バイトＬＵＴに格納し、方程式の組１２を計算するのに必要な計算の組から１つの乗算をなくすようにすることができる。代替的な実施形態によれば、ＧＦ（２4）のＳＱＲ、ＩＮＶ、及び／又はβＳＱＲは、当該技術分野において知られているように、いずれかの適切な回路によって実装することができる。例えば、上述のように、２つの要素の乗算の解にａ＝ｄを代入することによって、ＳＱＲ回路を実装することができる。したがって、例えば、ＳＱＲ回路は、α＝１について以下の解を実装することができる。
簡約多項式：ｔ4＋ｔ＋１
［ａ3，ａ2，ａ1，ａ0］2＝［ａ3，ａ1＋ａ3，ａ2，ａ0＋ａ2］
簡約多項式：ｔ4＋ｔ3＋１
［ａ3，ａ2，ａ1，ａ0］2＝［ａ2＋ａ3，ａ1＋ａ3，ａ3，ａ0＋ａ2＋ａ3］
簡約多項式：ｔ4＋ｔ3＋ｔ2＋ｔ＋１
［ａ3，ａ2，ａ1，ａ0］2＝［ａ2，ａ1＋ａ2，ａ2＋ａ3，ａ0＋ａ2］
【００８５】
本発明の実施形態の回路実装は、対応するＬＵＴ実装よりコンパクトにできることに留意されたい。しかしながら、幾つかのＳ−ｂｏｘ実装において、ＬＵＴがより効率的なデータ処理を提供することができる。
【００８６】
図４を参照すると、本発明の幾つかの例示的な実施形態にしたがって、マスクされたデータを暗号化／復号化するのためのＡＥＳ互換装置４００の回路実装を概略的に示す。
【００８７】
本発明の例示的な実施形態によれば、装置４００は、入力変換ブロック４１２と、操作ブロック、例えば反転ブロック４１４と、出力逆変換ブロック４１６とを含むことができる。装置４００は、後述のように、暗号化演算モード及び／又は復号化演算モードを持つことができる。
【００８８】
本発明の例示的な実施形態によれば、ブロック４１２は、ＧＦ（２8）表現などのＡＥＳ表現の、例えばｘ＋Ｒの３２ビット列ベクトルに対応するマスクされた入力データ信号４３８を受信し、このデータをＧＦ（（２4）2）表現のデータに変換するための入力変換モジュール４１８を含むことができる。復号化演算モードにおいては、変換モジュール４１８は、例えば上記の方程式６に従って、ｘ＋Ｒに復号化アフィン変換を適用することもできる。したがって、例えば、モジュール４１８の出力信号４４０は、ｘt＋Ｒtの値に対応する値を持つことができ、ここで、暗号化演算モードではｘt＝Ｍｘ及びＲt＝ＭＲであり、復号化演算モードではｘt＝ＭＡ-1ｘ＋ＭＡ-1ｂ及びＲt＝ＭＡ-1Ｒである。
【００８９】
ブロック４１２はまた、入力マスクＲを更新済みマスクに変換するマスク変換モジュール４２０を含むことができる。マスクされた変換済みデータに対応する更新済みマスクを取得するために、モジュール４２０によって行われるマスクの変換は、モジュール４１８によって行われる線形変換に対応する線形変換を含むことができる。例えば、暗号化演算モードにおいては、変換モジュール４２０は、ＲにＭを乗じてＭＲを取得することができる。復号化演算モードにおいては、変換モジュール４２０は、ＲにＭＡ-1を乗じてＭＡ-1Ｒを取得することができる。
【００９０】
モジュール４１８及び／又はモジュール４２０は、第１表現のデータを対応する第２表現のデータに変換し、及び／又は、例えば後述のようにアフィン変換を行うためのいずれかの回路、ルックアップテーブル（ＬＵＴ）、及び／又は、いずれかの適切なハードウェア及び／又はソフトウェアを含むことができる。
【００９１】
図５Ａを参照すると、本発明の幾つかの例示的な実施形態にしたがって、入力変換モジュール５００の回路実装が概略的に示される。
【００９２】
例示的な実施形態によれば、モジュール５００は、ｘ＋ＲとＭとの乗算を実施する乗算器５０６を含むことができる。モジュール５００はまた、ｘ＋ＲとｂとのＸＯＲ演算を実施するＸＯＲゲート５０８と、ＸＯＲゲート５０８の出力５１８とＭＡ-1との乗算を実施する乗算器５１０とを含むことができる。乗算器５０６及び／又は５１０は、例えば上述のように、ｎ×ｎ行列にベクトルを乗じるためのいずれかの適切な乗算器を含むことができる。モジュール５００はまた、例えば乗算器５０６の出力信号５１４と乗算器５１０の出力信号５１６とを選択することによって、暗号化演算モードと復号化演算モードとの間で選択を行う、当該技術分野で既知のマルチプレクサ５１２を含むことができる。
【００９３】
図５Ｂを参照すると、本発明の幾つかの例示的な実施形態にしたがって、マスク変換モジュール５３０の回路実装が概略的に示される。
【００９４】
例示的な実施形態によれば、モジュール５３０は、ＲとＭとの乗算を実施する乗算器５３２を含むことができる。モジュール５３０はまた、ＲとＭＡ-1との乗算を実施する乗算器５３４を含むことができる。乗算器５３２及び／又は５３４は、例えば上述のように、ｎ×ｎ行列にベクトルを乗じるためのいずれかの適切な乗算器を含むことができる。モジュール５３０はまた、例えば乗算器５３２の出力信号５３３と乗算器５３４の出力信号５３５とを選択することによって、暗号化演算モードと復号化演算モードとの間で選択を行う、当該技術分野で既知のマルチプレクサ５３６を含むことができる。
【００９５】
再び図４を参照すると、反転ブロック４１４は、第２表現の変換済みデータを反転するいずれかの回路及び／又はＬＵＴ、及び／又は、いずれかの適切なハードウェア及び／又はソフトウェアを含むことができる。
【００９６】
本発明の例示的な実施形態によれば、ブロック４１４は、信号４４０及び信号４４２を受信し、例えば値（ｘt＋Ｒt）Ｒtに対応する信号４７１を与えるための第１乗算器４７０を含むことができる。ブロック４１４はまた、信号４４２を受信し、例えばＲt2の値に対応する信号４７３を与える平方ユニット４７２と、信号４７１及び信号４７３を受信し、例えばｘtＲtの値に対応する信号４７５を与える第１加算器４７４とを含むことができる。ブロック４１４はさらに、信号４７５を受信して、例えば、ｘtＲt？０の場合にはゼロ値を持ち、ｘtＲt＝０の場合には非ゼロ値、例えば１を持つ信号を与えるためのゼロ検出（ＺＤ）モジュール４８０を含むことができる。ブロック４１４はまた、信号４４２及び信号４８１を受信して信号４８３を与えるための、例えば当該技術分野で既知のＡＮＤゲート４８２を含むことができる。例えば、信号４８３は、ｘtＲt？０の場合にはゼロ値を持ち、ｘtＲt＝０の場合には非ゼロ値、例えばＲtを持つことができる。ブロック４１４はさらに、信号４７５及び信号４８３を受信して、例えば、ｘtＲt？０の場合にはｘtＲtの値に対応し、ｘtＲt＝０の場合にはＲtの値に対応する信号４８５を与えるための第２加算器４７６を含むことができる。ブロック４１４はさらに、信号４８５を受信して、例えば、ｘtＲt？０の場合には（ｘtＲt）-1の値に対応し、ｘtＲt＝０の場合にはＲt-1の値に対応する信号４８７を与えるための反転モジュール４７８と、信号４８７及び単位値すなわち値１を持つ信号を受信して、例えば、ｘtＲt？０の場合は（ｘtＲt）-1＋１の値に対応し、ｘtＲt＝０の場合にはＲt-1＋１の値に対応する信号４８９を与えるための第３加算器４７９とを含むことができる。ブロック４１４はさらに、信号４４２及び信号４８９を受信し、例えば、ｘtＲt？０の場合にはｘt-1＋Ｒtの値に対応し、ｘtＲt＝０の場合には１＋Ｒtの値に対応する信号４９１を与えるための第２乗算器４８６を含むことができる。ブロック４１４はさらに、信号４９１及び４８３を受信し、例えば、ｘtＲt？０の場合にはｘt-1＋Ｒtの値に対応し、ｘtＲt＝０の場合にはＲtの値に対応する信号４４４を与えるための第４加算器４８４を含むことができる。乗算器４７０及び／又は乗算器４８６は、例えば上述のように、第２表現を用いて第１表現の２つの要素を乗じるいずれかの回路、ルックアップテーブル（ＬＵＴ）、及び／又は、いずれかの適切なハードウェア及び／又はソフトウェアを含むことができる。ユニット４７２は、例えば上述のように、第２表現を用いて第１表現の２つの要素を平方するいずれかの回路、ルックアップテーブル（ＬＵＴ）、及び／又は、いずれかの適切なハードウェア及び／又はソフトウェアを含むことができる。反転モジュール４７８は、例えば上述のように、第２表現を用いて第１表現のデータを反転するいずれかの回路、ルックアップテーブル（ＬＵＴ）、及び／又は、いずれかの適切なハードウェア及び／又はソフトウェアを含むことができる。加算器４７４、加算器４７６、加算器４７９、及び／又は加算器４８４は、２つの要素の加算を実行するいずれかのソフトウェア及び／又はハードウェアを含むことができる。例えば、加算器４７４、加算器４７６、加算器４７９、及び／又は加算器４８４は、当該技術分野で既知のＸＯＲゲートを含むことができる。モジュール４８０は、例えば、信号４８１の論理ＮＯＴと、それに続く論理ＡＮＤとを実行するいずれかの回路、ルックアップテーブル（ＬＵＴ）、及び／又は、いずれかの適切なハードウェア及び／又はソフトウェアを含むことができる。
【００９７】
これらの例示的な実施形態によれば、反転モジュール４７８への入力すなわち信号４８５は、例えばｘtＲt＝０であってもＲt？０であるため、非ゼロ値を持つ。したがって、ゼロ入力、すなわちｘt＝０は、例えば反転モジュールへの入力がゼロではないマスク値、例えばＲtを持つように、ブロック４１４によってマスクされる。
【００９８】
したがって、当業者であれば、反転ブロック４１４を実装して、ＡＥＳ装置上での、例えばゼロ入力を用いるＤＰＡ攻撃を阻止できることが分かるであろう。
【００９９】
本発明の他の実施形態によれば、ブロック４１４は、他のいずれかの適切な構成、例えば図２を参照して上述したような反転ブロック２０４の構成に類似の構成を含むことができる。
【０１００】
上述の例示的な実施形態によれば、信号４４４は、例えば、上述のように、暗号化演算モードにおける（ＭＸ）-1＋ＭＲ）に対応する値と、復号化演算モートにおける（（ＭＡ）-1（ｘ＋ｂ）-1＋ＭＡ-1Ｒ）に対応する値とを持つことができる。
【０１０１】
本発明の例示的な実施形態によれば、ブロック４１６は、第２表現、例えばＧＦ（（２4）2）表現のブロック４１４の出力、例えば信号４４４を受信し、このデータを逆変換して、例えばＧＦ（２8）といった第１表現の逆変換済みデータにするための出力逆変換モジュール４２４を含むことができる。暗号化演算モードにおいては、変換モジュール４２４は、例えば上記の方程式７に従って暗号化アフィン変換を適用することもできる。したがって、例えば、モジュール４２４の出力信号４３４はｘ’＋Ｒ’に対応する値を持つことができ、ここで、暗号化演算モードにおいてはｘ’＝Ａｘ-1＋ｂ及びＲ’＝ＡＲであり、復号化演算モードにおいてはｘ’＝Ａ-1（ｘ＋ｂ）-1及びＲ’＝Ａ-1Ｒである。これらの実施形態によれば、Ｒ’はマスクＲの標準的な線形変換に対応するものとすることができるため、Ｒ’をマスクとして用いることができる。
【０１０２】
ブロック４１６はまた、更新済みマスクを逆変換するマスク逆変換モジュール４２２を含むことができる。データの逆変換に対応して更新済みマスクを逆変換するために、モジュール４２２によって行われる逆変換は、モジュール４２０によって行われる線形変換に対応する線形変換を含むことができる。例えば、復号化演算モードにおいては、逆変換モジュール４２２は、Ａ-1ＭＲにＭ-1を乗じてＡ-1Ｒを取得することができる。暗号化演算モードにおいては、逆変換モジュール４２２は、ＭＲにＡＭ-1を乗じてＡＲを取得することができる。したがって、出力マスク信号４３２は、Ｒ’に対応する値を含むことができる。モジュール４２２及び／又は４２４は、第１表現のデータを対応する第２表現のデータに変換し、及び／又は、例えば後述のようなアフィン変換を行うための、いずれかの回路、ルックアップテーブル（ＬＵＴ）、及び／又は、いずれかの適切なハードウェア及び／又はソフトウェアを含むことができる。
【０１０３】
図６Ａを参照すると、本発明の幾つかの例示的な実施形態にしたがって、出力逆変換モジュール６００の回路実装が概略的に示される。
【０１０４】
例示的な実施形態によれば、モジュール６００は、操作済みデータ、例えば信号４４４とＭ-1との乗算を実行する乗算器６０２を含むことができる。モジュール６００はまた、操作済みデータとＡＭ-1との乗算を実行する乗算器６０４と、乗算器６０４の出力とｂとのＸＯＲ演算を実行するＸＯＲゲート６０６とを含むことができる。乗算器６０２及び／又は６０４は、例えば上述のように、ｎ×ｎ行列にベクトルを乗じるためのいずれかの適切な乗算器を含むことができる。モジュール６００はまた、例えば乗算器６０２の出力信号６１４と乗算器６０６の出力信号６１６とを選択することによって、暗号化演算モードと復号化演算モードとの間で選択を行う、当該技術分野で既知のマルチプレクサ６０８を含むことができる。
【０１０５】
図６Ｂを参照すると、本発明の幾つかの例示的な実施形態にしたがって、マスク逆変換モジュール６３０の回路実装が概略的に示される。
【０１０６】
例示的な実施形態によれば、モジュール６３０は、更新済みマスク、例えば信号４４２とＡＭ-1との乗算を実行する乗算器６３２を含むことができる。モジュール６３０はまた、更新済みマスクとＭ-1との乗算を実行する乗算器６３４を含むことができる。乗算器６３２及び／又は６３４は、例えば上述のように、ｎ×ｎ行列にベクトルを乗じるためのいずれかの適切な乗算器を含むことができる。モジュール６３０はまた、乗算器６３２の出力信号６３３と乗算器６３４の出力信号６３５とを選択することによって、暗号化演算モードと復号化演算モードとの間で選択を行う、当該技術分野で既知のマルチプレクサ６３６を含むことができる。
【０１０７】
再び図４を参照すると、装置４００はまた、信号４３４に関する列混合演算に対応する信号４５６を与える列混合モジュール４５５を含むことができる。列混合演算は、当該技術分野において知られているように、例えば３２ビット列ベクトルｘ’＋Ｒ’を含む信号４３４とラインダール列混合行列とを乗じることを含むことができる。例えば、列混合演算は、以下のように、すなわち、
2006517036.tif 000008
として計算することができ、ここで、ｘ’1＋Ｒ’1，ｘ’2＋Ｒ’2，ｘ’3＋Ｒ’3，及びｘ’4＋Ｒ’4は、列ベクトルｘ’＋Ｒ’のマスクされたデータ要素である。
【０１０８】
当業者であれば、Ｒ’1、Ｒ’2、Ｒ’3、及びＲ’4は、Ｒのそれぞれの要素、例えばＲ1、Ｒ2、Ｒ3、及びＲ4の線形変換に対応するため、ベクトル（Ｒ’1、Ｒ’2、Ｒ’3、Ｒ’4）の全ての要素は、非ゼロの値、すなわちＲ’1？０、Ｒ’2？０、Ｒ’3？０、及びＲ’4？０であることが分かるであろう。しかしながら、ベクトル（Ｒ’1、Ｒ’2、Ｒ’3、Ｒ’4）とラインダール列混合行列との積は、ゼロ値を持つこともある。このことは、後のＡＥＳラウンドのマスクを歪めるという望ましくない結果をもたらすことがある。本発明の幾つかの例示的な実施形態によれば、この潜在的な問題を防止するために、ＲのＲ1、Ｒ2、Ｒ3、及びＲ4は、あらかじめ設定された等しい値、すなわちＲ1＝Ｒ2＝Ｒ3＝Ｒ4を持つものとすることができる。当業者であれば、あらかじめ設定された等しい値Ｒ1＝Ｒ2＝Ｒ3＝Ｒ4によって、ベクトル（Ｒ’1、Ｒ’2、Ｒ’3、Ｒ’4）とラインダール列混合行列との積が常に非ゼロであることを保証できることが分かるであろう。本発明の実施形態にしたがって、あらかじめ設定された他の値を用いて、ラインダール列混合乗算の結果が非ゼロになることを保証することもできる。
【０１０９】
ＡＥＳラウンドはまた、当該技術分野において知られているように、行シフト演算の実行を含むことができる。行シフト演算は、当該技術分野において知られているように、マスクされたデータの４つの列を表す４×４データ行列の各行の要素間におけるシフトを含むことができる。データ行列は、ｋ＝１．．．１６としたときの和Ｘ’k＋Ｒ’kに各々が対応する１６個の要素を含むことができる。本発明の幾つかの例示的な実施形態によれば、Ｒの１６個の要素全ては、後に続くラウンドのマスクが歪まないことを保証するために、あらかじめ設定された等しい値、すなわちＲ1＝Ｒ2＝．．．＝Ｒ16を持つものとすることができる。本発明の実施形態にしたがって、あらかじめ設定された他の値を用いて、ラインダール行混合乗算の結果が非ゼロであることを保証することもできる。当業者であれば、上述のようにマスクＲの１６個の要素全てをあらかじめ設定しても、ＤＰＡ攻撃に必要な総当りに対して比較的軽微な影響しか与えないことが分かるであろう。
【０１１０】
当業者であれば、ベクトル（１，１，１，１）は、ラインダール列混合行列の固有ベクトルであること、すなわち、以下の式、
2006517036.tif 000009
で表されることが分かるであろう。
【０１１１】
したがって、本発明の例示的な実施形態によれば、信号４３２の値は、信号４３２に関して行われる列混合演算に応じて更新されることはない。
【０１１２】
本発明の幾つかの例示的な実施形態によれば、装置４００はさらに、例えば最終ＡＥＳラウンド後に、マスクされた逆変換済みデータのマスクを取るためのマスク除去モジュール４６０を含むことができる。例示的な実施形態によれば、モジュール４６０は、信号４５６に対応する第１入力と第２入力との和に対応する出力信号４６４を与えるＸＯＲゲート４６２を含むことができる。最終ＡＥＳラウンド後に、ゲート４６２の第２入力を信号４３２と関連させることができる。したがって、更新済みマスクの値は、最後のラウンド後に、マスクされた逆変換済みデータとＸＯＲを取ることができ、その結果、操作済みデータからマスクが除去される。
【０１１３】
本発明の幾つかの例示的な実施形態によれば、出力信号４６４はＲ’によってマスクされるため、マスクＲ’は、後述のように、後続のＡＥＳラウンドにおける入力マスクとして用いることができる。
【０１１４】
本発明の幾つかの例示的な実施形態によれば、装置４００はさらに、後述のように、後続のＡＥＳラウンドにおける新たなマスクを用いることが可能なマスク入力モジュール４５０を含むことができる。モジュールは、以前のＡＥＳラウンドの信号４６５の値、例えばｘ’’＋Ｒ’に対応する第１入力と、ランダム・マスク信号４５２の値、例えばＲに対応する第２入力との和を与える第１ＸＯＲゲート４２８を含むことができる。したがって、例えば、ＸＯＲゲート４２８の出力信号４５４は、ｘ’’＋Ｒ’＋Ｒの値に対応するものとすることができる。構成４５０はまた、信号４５４と信号４３２との和に対応する信号４３８をブロック４１２に与える第２ＸＯＲゲート４２６を含むことができる。したがって、信号４３８は、ｘ’’＋Ｒに対応する値を持つことができる。
【０１１５】
当業者であれば、構成４５０の各ＸＯＲゲートの入力及び出力は、マスク、すなわちＲ及び／又はＲ’を含むことができることが分かるであろう。
【０１１６】
本発明の例示的な実施形態によれば、装置４００によって実装される表現変換行列Ｍは、後述のように、例えば装置４００を実装するための最小回路面積といった所望の最適化基準に基づいて、あらかじめ決定することができる。
【０１１７】
本発明の例示的な実施形態によれば、１組の回路、例えばα＝１のときの１９２個の可能な変換行列に対応する１９２個の回路を作成して、装置４００を実装することができる。例えば、回路の各々は、シノプシス社から入手可能なＤＣ  Ｓｈｅｌｌ  ２００１．０８−ｓｐ１（ＤＣ  Ｅｘｐｅｒｔ）を用いて合成することができる。ターゲット・ライブラリＴＳＭＣ  ０．１８μ（ＳＡＡＧ−Ｘ  Ａｒｔｉｓａｎｅ）を用いることができる。例えば１２ｎＳｅｃから６ｎＳｅｃまでの範囲の伝搬遅延時間といった様々なタイミングについて、合成を行うことができる。これらのパラメータにより、例えば３ナノ秒のマージンといったマージンを加えることによって、例えば６６．７ＭＨｚから１１１ＭＨｚまでの範囲の、それぞれ異なる周波数を用いることが可能になる。合成の結果に応じて、表現変換行列［０１  ０ｃ  ５０  ｅｄ  ４２  ３５  ６７  ９２］が実装される場合には、従来のＡＥＳ装置の回路面積と比較して約４５％の回路面積削減を達成することができる。
【０１１８】
本発明の例示的な実施形態によれば、例えば後述のように、ランダム・ビット生成器を実装して、非ゼロのマスクＲを生成することができる。しかしながら、当業者であれば、他のいずれかの適切な装置及び／又は方法を実装して、非ゼロのマスクＲを生成できることが分かるであろう。
【０１１９】
本発明の例示的な実施形態によれば、ランダム・ビット生成器を用いて、ｖビットを有する非ゼロのマスクＲを生成することができ、ここで、ｖは２のべき乗、例えばｖ＝８である。この生成器は、ｌｏｇ（ｖ）＋ｖ−１ビットを生成することができる。初めのｌｏｇ（ｖ）ビットは、０？ｗ＜ｖである第１の数ｗを定めるのに用いることができる。残りのｖ−１ビットは、第２の数ｐを定めるのに用いることができる。ｖビット・マスクは、Ｒのｗ番目のビットの値を１に設定し、Ｒの他のｖ−１ビットをｐのｖ−１ビットと置き換えることによって、生成することができる。例えば、ｖ＝８の場合には、ランダム・ビット生成器は、ｌｏｇ８＋８−１＝１０のランダム・ビット、例えば１０１１１００１０１を生成することができる。したがって、ｗ＝１０１2＝５、ｐ＝１１００１０１、Ｒ＝１１１００１０１である。
【０１２０】
当業者であれば、マスクのｗ番目のビットにおいて１の値は常に置き換えられるため、上述の方法は非ゼロのマスクを提供できることが分かるであろう。さらに、上述の方法を実施して、可能な非ゼロｖビット・マスクのいずれか１つを提供することができる。さらに、上述の方法を実装するマスク生成器によって、等しいハミング重みを持つマスクを等しい確率で生成することができる。以前にマスクが生成された場合に特定のマスクを生成することに対応する条件付きエントロピー値は、例えば以下のように、
2006517036.tif 000010
として計算することができる。
【０１２１】
したがって、上述の方法を実施して、例えばｖ＝８の場合には約７．９０２４４といった比較的高いエントロピー値を与えることができる。
【０１２２】
当業者であれば、本発明は、添付図面を参照して本明細書で示され、説明された本発明の例示的な実施形態に限定されるものではないことが分かるであろう。本発明の幾つかの特徴が示され、説明されたが、当業者であれば、多くの修正、置換、変更、及び均等物を想定できるであろう。したがって、特許請求の範囲は、本発明の真の精神内にあるものとして、そうした修正及び変更の全てに及ぶことが意図されているものと理解すべきである。
【図面の簡単な説明】
【０１２３】
【図１】本発明の実施形態に係る、マスクされたデータを操作する方法のフローチャート図である。
【図２】本発明の幾つかの例示的な実施形態に係る、マスクされたデータを操作する装置の回路実装の概略図である。
【図３Ａ】本発明の幾つかの例示的な実施形態に係る、乗算器の回路実装の概略図である。
【図３Ｂ】本発明の幾つかの例示的な実施形態に係る、平方モジュールの回路実装の概略図である。
【図３Ｃ】本発明の幾つかの例示的な実施形態に係る、反転モジュールの回路実装の概略図である。
【図４】本発明の幾つかの例示的な実施形態に係る、マスクされたデータを暗号化／復号化するＡＥＳ互換装置の回路実装の概略図である。
【図５Ａ】本発明の幾つかの例示的な実施形態に係る、データ変換モジュールの回路実装の概略図である。
【図５Ｂ】本発明の幾つかの例示的な実施形態に係る、マスク変換モジュールの回路実装の概略図である。
【図６Ａ】本発明の幾つかの例示的な実施形態に係る、出力逆変換モジュールの回路実装の概略図である。
【図６Ｂ】本発明の幾つかの例示的な実施形態に係る、マスク逆変換モジュールの回路実装の概略図である。
【図１】
2006517036.tif 000011
【図２】
2006517036.tif 000012
【図３Ａ】
2006517036.tif 000013
【図３Ｂ】
2006517036.tif 000014
【図３Ｃ】
2006517036.tif 000015
【図４】
2006517036.tif 000016
2006517036.tif 000017
2006517036.tif 000018
【国際調査報告】
2006517036.tif 000019