(57)【要約】【課題】マスキングされたモンゴメリーのモジュラー乗算方法及び関連装置を提供する。【解決手段】本発明はマスキングされたモンゴメリーのモジュラー乗算方法及び関連装置に関する。  合同ｎにおけるモジュラー乗算は、少なくとも擬似乱数ｚを生成するステージ、及びその結果へ、ｎによる前記数との積を加算するステージを含む。本発明は特に暗号計算に専用のプロセッサの安全確保に適用される。【選択図】図２
2008304920.tif 000002
【特許請求の範囲】
【請求項１】
暗号化要素により実行される、合同ｎにおけるモンゴメリーのモジュラー乗算方法であって、該方法が二つの入力演算数Ａ＋ｋ１．ｎ及びＢ＋ｋ２．ｎを受け取り、Ａ及びＢはｎよりも小さく、ｋ１及びｋ２は整数であり、該方法が次のステージ：
−Ａ．Ｂ  ｍｏｄ  ｎに等しい中間結果Ｓを計算するステージと、
−擬似乱数ｚを生成するステージと、
−ｎにより乗算された前記数ｚの積を中間結果Ｓに加えるステージと
を含むことを特徴とする方法。
【請求項２】
次のステージ：
Ｓ←ｘ０．ｙ
０≦ｉ≦ｔｎ−１であるｉに対し、以下を行なう：
ｍｉ←Ｓ０．ｎ’ｍｏｄ  ｒ
Ｓ←ｘｉ．ｙ＋（ｍｉ．ｎ＋Ｓ）／ｒ
ｍｔｎ←Ｓ０．ｎ’ｍｏｄ  ｒ
擬似乱数ｚを決定する
Ｓ←ｚ．ｎ＋（ｍｔｎ．ｎ＋Ｓ）／ｒ
を含み、
ここで、ｒは記数法の底、ｔｎは多数の機械語におけるモジュールｎのサイズを指し、ｘ及びｙは乗算されるべき演算数、ｍｉは中間係数、Ｓは乗算結果であり、そしてｎ’の値が−ｎ−１ｍｏｄ  ｒに等しいことを特徴とする請求項１に記載の方法。
【請求項３】
モジュラー乗算が４以上の高い記数法の底において実行されることを特徴とする請求項２に記載の方法。
【請求項４】
擬似乱数ｚが乗算入力演算数ｘ＝Ａ＋ｋ１．ｎ及びｙ＝Ｂ＋ｋ２．ｎに従って計算されることを特徴とする請求項１あるいは２に記載の方法。
【請求項５】
数ｘが機械語ｘ０ｘ１．．．ｘｔｎにより形成され、そして数ｙがｙ０ｙ１．．．ｙｔｎにより形成され、擬似乱数ｚがｘ０  ｘｏｒ  ｘ１  ｘｏｒ．．．ｘｏｒ  ｘｔｎ  ｘｏｒ  ｙ０  ｘｏｒ  ｙ１  ｘｏｒ．．．ｘｏｒ  ｙｔｎに等しいことを特徴とする請求項４に記載の方法。
【請求項６】
モンゴメリーのモジュラー乗算実行装置であって、加算されそして乗算されるべき幾つかの数字を受け取る、ｐ組のパイプライン方式で実行される論理−レジスタの対を備えた乗算−加算器を含む少なくとも一つの計算セルを包含し、少なくとも二つの出力が下位と上位に対応し、加算器が乗算−加算器の二つの出力を受け取る装置において、装置が追加のｂ−１ビット＋１ビット〜ｂビットの加算器を含むことを特徴とする装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はマスキングされたモンゴメリーのモジュラー乗算方法及び関連装置に関する。それは特に暗号計算専用のプロセッサの安全保護に適用される。
【背景技術】
【０００２】
暗号法の目的の一つは、一般的に暗号化キーである秘密要素を用いて極秘データを暗号化することである。キー値は極秘データの開示を防止するために是非とも保護されなければならない。暗号法のアルゴリズムは、実際にキーが見出せないことを保証するように設計される。理論的に、キーの探求は通常、管理の及ばない計算手段を必要とし、計算時間はヒューマンスケールを超える。しかしながら、或る攻撃者はキー値を見出すために物理的測定を用いることにより、これらの数学上の困難を巧みにかいくぐった。用いられた一つの方法は従って補助チャンネルによる攻撃である。これはキーの使用中に、暗号計算ブロックの挙動を測ることに関する。実際、幾つかの計算はキー値に従って実行される。しかし物理的なサイズは計算ブロックにより実行される演算、及びこれらの演算に含まれるデータによって変化する。例えば、回路の電力消費量の測定、計算時間、又は構成要素により発生する電磁放射は、実行される一定の演算又は処理される一定のデータの識別を可能にする。使用されるキー値は、従ってこれらの測定値を解析することにより見出され得る。
【０００３】
非対称の暗号法プロセスを利用してセキュリティシステムを保護するために、このタイプの攻撃を行なうことは、少なくとも従来の暗号攻撃を行なうのと同じだけ難しいことが望ましい。既知の解決策はこれらの攻撃を軽減する有効性を可能にするが、しかしながら防止することは出来ない。これらの解決策は物理的サイズの測定が、計算ブロックにより実行される演算について、できる限る最小限の情報のみ明らかにすることを確実にするため、計算アルゴリズム及び／又は扱われるデータの変更を含み得る。幾つかのカテゴリーの保護方法が確立されている。
【０００４】
一つの第一のカテゴリーは擬似計算ブロックを加えることに関する。これらの特定のブロックは計算には含まれないが、電力消費及び／又は電磁放射を変化させる。測定の処理はこれらの擬似計算ブロックの影響が取り除かれ、従って無視されることを可能にするため、このタイプの対策は完全には有効でない。
【０００５】
第二のカテゴリーの保護方法は、アルゴリズムの実行がキー値に依存することを防止する。この方法は必要であるが十分ではない。
【０００６】
第三のカテゴリーはデータのランダムな攪乱を導入する。この保護方法は一般に「マスキング」と形容される。これは測定と既知のデータとの間の相関関係を減らすために、暗号化されていない、又は暗号化されたデータと先験的に関連を持たないデータを操作することに関する。
【０００７】
これらの保護方法の実施には幾つかの欠点が伴うことが避けられない。一方、それは計算時間及び／又はソフトウェアの実行に関するコードのサイズを増加させ、あるいはハードウェア実現のための回路面積を増加させる。他方で、暗号のアルゴリズムは一般的に層による計算システムにおいて実行される。基本的な計算ブロックは、それら自体が暗号のアルゴリズムを実行するために使用される、より高いレベルのアルゴリズムによって用いられる。基本的ブロックの変更は、従ってこの変更された基本的ブロックを用いた幾つかのより高いレベルのアルゴリズムにおいて、予期しない、又は正しくない挙動さえも生じ得る。これらのエラーを避けるため、アルゴリズム及び／又は計算システム構成のレベルにおいて、幾らかの変更が時には必要である。従って変更された基本的ブロックの組み込みは、より高いアルゴリズムの層における多くの影響のために複雑にされる。
【０００８】
例として、乗算のマスキングは、それが非対称の暗号法に関して自然に思えるため、しばしば用いられる。計算は合同ｎのモジュラーリングにおいて通常実行される。乗法のマスキングは、（ｎを法とするｘ）を操作する代わりに（ｎを法とする（ｘ・ｒ））に等しい数ｘ’の操作により、アルゴリズムの実行中に行なわれ、ここでｒは不確実性、ｎは母数である。しかしながら、乗法のマスキングは幾つかの欠点を有する。一方で、それは期待される結果を得るために追加的な分割を必要とする。ところで、そのような分割演算は計算時間及びハードウェア資源に関して高価である。他方で、不確実性ｒはアルゴリズムの実行期間全体にわたって固定され、これは攻撃者により利用され得る脆弱さを現わし得る。更に、アルゴリズムが一定の楕円曲線を用いるとき、特に攻撃者が前記曲線におけるゼロ座標の点を選択するとき、別の脆弱性が乗法のマスキングと共に現われ得る。
【０００９】
別の既知のマスキング方法は合同ｋ．ｎのモジュラーリングにおけるアルゴリズムの実行であり、ここでｋは自然の整数である。しかしながら、計算に用いられるモジュールのサイズを増やすことは実行されるソフトウェア及びハードウェア資源のより高度の再スケーリングを必要とする。
【００１０】
別のマスキングプロセスは（特許文献１）の番号の下に発行された欧州特許出願の中で開示された。これはそのうちの一つがマスキングされた二つの乗算に関する技術である。この解決策は前のものと同様に、現行のそして多層の計算システムに組み込むことは容易でない。実際、それは特に暗号法の機能によって用いられるアルゴリズムにおける変化を伴う。
【００１１】
非対称の暗号化アルゴリズムにより用いられる基本演算の一つはモジュラー乗算である。ｎを法とする二つの整数の積の計算を可能にするこの演算は、多数のアルゴリズムにより用いられる。それは従って補助チャンネルによる攻撃に対する保護を含むことが望ましい。
【００１２】
満足されるべき更なる要求事項は解法の柔軟性、すなわち多くの変化するサイズを処理するその能力である。
【００１３】
【特許文献１】欧州特許第１２３９３６４号明細書
【発明の開示】
【課題を解決するための手段】
【００１４】
本発明の目的の一つは、非常に僅かな計算時間の追加費用をもたらし、非常に少ない追加のハードウェア資源を要し、より高いレベルのアルゴリズムに対して影響しない方法によって、モジュラー乗算の演算を保護することである。このため、本発明の目的は暗号化構成要素により実行される合同ｎを有するモンゴメリーのモジュラー乗算方法を提供することであり、該方法は二つの入力演算数Ａ＋ｋ１．ｎ及びＢ＋ｋ２．ｎを受け取り、Ａ及びＢはｎよりも小さく、ｋ１及びｋ２は整数であり、該方法は少なくとも次のステージ：
−Ａ．Ｂ  ｍｏｄ  ｎに等しい中間結果Ｓを計算するステージと、
−擬似乱数ｚを生成するステージと、
−ｎにより乗算された前記数ｚの積を中間結果Ｓに加えるステージと
を含む。
【００１５】
本発明における方法は少なくとも次のステージを含み得る：
Ｓ←ｘ０．ｙ
０≦ｉ≦ｔｎ−１であるｉに対し、以下を行なう：
ｍｉ←Ｓ０．ｎ’ｍｏｄ  ｒ
Ｓ←ｘｉ．ｙ＋（ｍｉ．ｎ＋Ｓ）／ｒ
ｍｔｎ←Ｓ０．ｎ’ｍｏｄ  ｒ
擬似乱数ｚを決定する
Ｓ←ｚ．ｎ＋（ｍｔｎ．ｎ＋Ｓ）／ｒ
ここで、ｒは記数法の底、ｔｎは多数の機械語におけるモジュールｎのサイズを指し、ｘ及びｙは乗算されるべき演算数、ｍｉは中間係数、Ｓは乗算結果であり、そしてｎ’の値は−ｎ−１ｍｏｄ  ｒに等しい。
【００１６】
一つの実行方法によれば、モジュラー乗算は４以上の高い記数法の底において実行される。
【００１７】
一つの実行方法によれば、擬似乱数ｚは乗算入力演算数ｘ＝Ａ＋ｋ１．ｎ及びｙ＝Ｂ＋ｋ２．ｎに従って計算される。
【００１８】
数ｘが機械語ｘ０ｘ１．．．ｘｔｎにより形成され、そして数ｙがｙ０ｙ１．．．ｙｔｎにより形成される一つの実行方法によれば、擬似乱数ｚはｘ０  ｘｏｒ  ｘ１  ｘｏｒ．．．ｘｏｒ  ｘｔｎ  ｘｏｒ  ｙ０  ｘｏｒ  ｙ１  ｘｏｒ．．．ｘｏｒ  ｙｔｎに等しく、ｘｏｒはバイナリの「ｏｒ専用」演算を指す。
【００１９】
本発明の目的はまた、加算されそして乗算されるべき幾つかの数字を受け取る、ｐ組のパイプライン方式で実行される論理−レジスタの対を備えた乗算−加算器を含む少なくとも一つの計算セルを包含する、モンゴメリーのモジュラー乗算を実行するための装置を提供することであり、少なくとも二つの出力が下位と上位に対応し、加算器が乗算−加算器の二つの出力を受け取り、該装置は追加のｂ−１ビット＋１ビット〜ｂビットの加算器を含む。
【００２０】
他の特徴は、添付図面に対応して例として与えられる、以下の詳細な制限されない記述に含まれる。
【発明を実施するための最良の形態】
【００２１】
本発明における乗算器は、ＡＳＩＣ（特定用途の集積回路（Ａｐｐｌｉｃａｔｉｏｎ−Ｓｐｅｃｉｆｉｃ  Ｉｎｔｅｇｒａｔｅｄ  Ｃｉｒｃｕｉｔ））又は、ＦＰＧＡ（フィールド・プログラマブル・ゲート・アレイ（Ｆｉｅｌｄ  Ｐｒｏｇｒａｍｍａｂｌｅ  Ｇａｔｅ  Ａｒｒａｙ））におけるハードウェアで実行され、ｂビットのデータ・バスにおいて機能する。
【００２２】
多数のビットｂはこれ以降「機械語」の用語により形容される。該バスのサイズはしばしば２の累乗である。記数法の底ｒは２ｂに等しいと定義される。母数ｎはｔｎの機械語として保存された奇数である。そして最後に、Ｒは記数法の底の累乗として定義され、ここでＲは母数ｎよりも大きい。数ｘは底ｒにおいて次のようにｔ＋１個の数字ｘｉに分解され得る。
ｘ＝ｘ０＋ｘ１．ｒ＋ｘ２．ｒ２．．．＋ｘｔ．ｒｔ
ここで、各数字ｘｉは機械語のサイズである。
【００２３】
本発明における乗算器はｘ．ｙ．Ｒ−１  ｍｏｄ  ｎ＋ｅ．ｎを計算するために、二つの数ｘ及びｙを用い、ここでｅはｘとｙに依存する０とｒ／２の間の値である。演算ｘ．ｙ．Ｒ−１  ｍｏｄ  ｎはモンゴメリーのモジュラー乗算である。乗算器は従ってモンゴメリーのモジュラー乗算と、この乗算結果の付加的なマスキングを実行する。ｅの値はｘとｙに依存するため、入力値ｘとｙが乗算器により使用される前に、ランダムな値によって既にマスキングされている時、その結果もランダムな値により、それ自体マスキングされる。乗算器は従って入力データのマスキングを伝播する。
【００２４】
一つの実行変数によれば、ｅの値はｘとｙに無関係な確率変数に依存する。
【００２５】
乗算を実行する前に、ｎ’と称される値が予め計算される：ｎ’＝−ｎ−１  ｍｏｄ  ｒ。乗算結果はＳと称される。底ｒにおける数Ｎの数字はＮｉと称される。
【００２６】
結果の付加的なマスキングを伴うモンゴメリーのモジュラー乗算は次の方法を通じて計算される：
ｉ．Ｓ←ｘ０．ｙ
ｉｉ．０≦ｉ≦ｔｎ−１であるｉに対し、以下を行なう：
ａ．  ｍｉ←Ｓ０．ｎ’ｍｏｄ  ｒ
ｂ．  Ｓ←ｘｉ．ｙ＋（ｍｉ．ｎ＋Ｓ）／ｒ
ｉｉｉ．ｍｔｎ←Ｓ０．ｎ’ｍｏｄ  ｒ
ｉｖ．ｚ←ｘ０  ｘｏｒ  ｘ１  ｘｏｒ．．．ｘｏｒ  ｘｔｎ  ｘｏｒ  ｙ０  ｘｏｒ  ｙ１  ｘｏｒ．．．ｘｏｒ  ｙｔｎ
ｖ．Ｓ←ｚ．ｎ＋（ｍｔｎ．ｎ＋Ｓ）／ｒ
ここで、ｍｉの値は計算の中間係数である。
【００２７】
第４ステージ（ｉｖ）の役割は、ｘとｙに依存する擬似乱数値ｚを提供することである。上記の例において与えられる、この擬似乱数値ｚを計算するプロセスは、数ｘとｙとを違ったやり方で結合するために変更され得る。第５ステージ（ｖ）は乗算結果の中に、前のステージの間に生じた不確実性を導入する。加算される数（ｚ．ｎ）はｎの倍数であるため、変更された結果はそれが従来のプロセスで生み出されたであろう結果に適合する。
【００２８】
ステージ（ｉｉ．ｂ．）（Ｓ←ｘｉ．ｙ＋（ｍｉ．ｎ＋Ｓ）／ｒ）は、計算時間に関して最も費用がかかる。それは二つの乗算−加算の演算のシーケンスにより実行され得る。
第一の乗算−加算はＳ←（ｍｉ．ｎ＋Ｓ）／ｒであり、
そして第二の乗算−加算はＳ←ｘｉ．ｙ＋Ｓである。
【００２９】
各乗算−加算はループにより実行され、第一の乗算−加算はｒによる除算の分だけ第二番目と異なる。
【００３０】
一つの実行方法によれば、第二の乗算−加算により実行されるループは次の通りである：
ｃ＝０
０≦ｊ≦ｔｎであるｊに対し、以下を行なう：
Ｐ←ｐｉｑｊ＋ｖｊ＋ｃ
ｓｊ←ＬＳＢ（Ｐ）
ｃ←ＭＳＢ（Ｐ）
ｓｎ＋１＝ｃ
ここでｓは乗算−加算の結果ｐｉ．ｑ＋ｖを指し、ｃは桁繰上げの変数である。
【００３１】
モジュラー乗算ステージ（ｉｉ．ｂ．）の間、値ｐｉはｘｉにより置き換えられ、値ｑはｙにより置き換えられ、値ｖはＳにより置き換えられる。基本演算Ｐ←ｐｉｑｊ＋ｖｊ＋ｃはｐｉ，ｑｊ，ｖｊを用いて実行され、ここでｃは０〜ｒ−１に及ぶ。中間結果Ｐは従って０〜ｒ２−１の間にあり、二つの数字として表わされる。ＬＳＢ（Ｐ）の表現はＰの下位ビットを指し、ＭＳＢ（Ｐ）はＰの上位ビットを指す。
【００３２】
ｑｎが１以下である、マスキングされない数に対して演算する乗算−加算と異なり、本発明における装置により実行される乗算−加算は、（ｊ＝ｔｎのとき）ループの最後の反復において０〜ｒ／２の間の数字ｑｎに対する演算を実行する。ｓｎ＋１の値は従って２よりも大きくなり得る。
【００３３】
第一の乗算−加算、Ｓ←（ｍｉ．ｎ＋Ｓ）／ｒは第二の乗算−加算と同様に実行されるが、しかしまた結果をｂビットだけ下位ビットに向けてシフトする。このシフトはｒによる除算と等価である。シフトを伴う乗算−加算は次のように実行される：
ｃ＝０
０≦ｊ≦ｔｎであるｊに対し、以下を行なう：
Ｐ←ｐｉｑｊ＋ｖｊ＋ｃ
ｓｊ−１←ＬＳＢ（Ｐ）
ｃ←ＭＳＢ（Ｐ）
ｓｎ＝ｃ＋ｖｎ＋１
【００３４】
モジュラー乗算ステージ（ｉｉ．ｂ．）の間、値ｐｉはｍｉにより置き換えられ、値ｑはｎにより置き換えられ、値ｖはＳにより置き換えられる。従って、ｊ＝ｔｎの反復に対し、ｔｎの定義によりｎｊ＝０、従ってＰ≦２（ｒ−１）であり、これはＭＳＢ（Ｐ）≦１を意味する。
【００３５】
該ループは従って、インデックスのシフト分の差で、第二の乗算−加算に対応するループの近くにあり、これは二つのループを実行することが出来る構成要素の実現を考慮することを可能にする。乗算器はとりわけ、乗算−加算（ｐｉｑｊ＋ｖｊ）の演算をパイプライン方式で実行し、そして結果が得られるにつれて変数ｃを加算することにより、演算ｐｉｑｊ＋ｖｊ＋ｃを（ｐｉｑｊ＋ｖｊ）＋ｃへと分解することが可能である。
【００３６】
図１は本発明におけるマスキングされたモジュラー乗算の中で用いられる、乗算−加算セルの一例である。該セルは上に記述された二つの乗算−加算演算を計算する。それは性能を改善するためにパイプライン方式で実行される。パイプラインは、クリティカルパスを減らすために論理フェーズ同士の間にレジスタのバリアを加え、従って（理論的には底ｒにおける加算器の）最大動作周波数を増加させることにある。
【００３７】
基本的構成要素のパイプラインの深さは、その内部レジスタの数により定義される。出力レジスタはカウントされない。
【００３８】
図１において与えられる例は、深さｐのパイプライン方式で実行される乗算−加算器１を我々が自由に使うことを前提としている。
【００３９】
それは特に一組の論理−レジスタの対（ｌｉ，ｒｉ）を含む。これらの対の数ｐは特に、パイプライン方式で実行される乗算−加算器の最大周波数Ｆ１ｍａｘが、加算器の最大周波数Ｆ２ｍａｘ以上であって、これら二つの周波数の値が共に出来るだけ近いことを保証するように選ばれる。
【００４０】
パイプライン方式で実行される乗算−加算器の最大動作周波数が、ｐステージの内のただ一つの実行時間の逆数により与えられるのに対して、乗算−加算器の最大動作周波数は、乗算−加算演算の実行時間の逆数により与えられる。最適な演算のために、加算器の実行時間を与える加算器の最大周波数が決定され、そして乗算−加算器は、該加算器の実行時間以下ではあるが、それに出来る限り近いｐ個の横断時間のステージへと細分される。
【００４１】
乗算−加算器１の入力は三つの数字、ｐｉ，ｑｊ，及びｖｊに対応し、出力はＬＳＢ（ｐｉｑｊ＋ｖｊ）及びＭＳＢ（ｐｉｑｊ＋ｖｊ）に対応する数字の対である。該出力は二つの数字の長さである。
【００４２】
乗算−加算器の結果は、参照番号２である三入力の加算器に伝送される：数字＋数字＋桁繰上げ→数字＋桁繰上げは、周波数Ｆ２ｍａｘにおいて１サイクル（パイプライン０）にわたり動作する。
【００４３】
ｃのストレージに対応するＴｅｍｐレジスタは次の計算に必要とされる。：ｃと次のＬＳＢとの加算及び前の桁繰上げ。
【００４４】
データ（ｐ×Ｑ＋Ｖの数字）は従って、桁繰上げの伝播と同じ方向に、下位ビットを先頭にして各サイクルにおいて連続して出力される。
【００４５】
演算ｓｎ＝ｃ＋ｖｎ＋１は、ｖｎ＋１が２よりも大きい可能性があるため、従来の装置におけるような２ビット＋１ビット＝３ビットではなく、ｂ−１ビット＋１ビット＝ｂビットを用いて、図に示されない加算器により実行されることができる。
【００４６】
結果の付加的なマスキングを伴うモンゴメリーのモジュラー乗算における、別のステージは、従来のレジスタ及びマルチプレクサを用いて実行され得る。モンゴメリー法によるモジュラー乗算を実行する乗算器は、国際公開第２００６／１０３２８８号パンフレットの番号の下に発行された特許出願の中に記述されている。
【００４７】
本発明内のマスキングプロセスにおけるステージは、上述のように乗算−加算セルを含む装置において容易に実行され得る。擬似乱数は二つの入力と一つの出力を有する論理構成要素によって生成されることができ、第一の入力は乗算されるべき第一の演算数ｘを受け取り、第二の入力は乗算されるべき第二の演算数ｙを受け取り、そして出力は例えばｘ  ｘｏｒ  ｙと等しい数のような、ｘとｙの組合せを生じ、ここでｘｏｒはバイナリのＯＲ専用演算を指す。この論理構成要素から得られる擬似乱数ｚは、ｚ．ｎに等しい、ｎの複数の擬似乱数を備えるために、次に乗算器においてｎと結合されることができる。
【００４８】
図２はモジュラー乗算の演算を利用するアルゴリズムにより、本発明においてマスキングプロセスを実行する乗算器の利用の概略図である。アルゴリズム実行の間、実行される全ての乗算は、幾つかの固定された初期値から全て得られる数に対して作用する。例として、アルゴリズムにおいて用いられる他の全ての値を生成するために、ｈ、ｘ、ｄ、及びｓと称される四つの初期値が使用される。
【００４９】
最初の第一ステージ２１において、付加的なマスキングがこれらの初期値ｈ、ｘ、ｄ、及びｓに対して実行される。マスキングされた値ｈｍ、ｘｍ、ｄｍ、及びｓｍは次のように得られる：
ｈｍ＝ｈ＋ｅｈ．ｎ；  ｘｍ＝ｅｘ．ｎ；  ｄｍ＝ｅｄ．ｎ；  ｓｍ＝ｅｓ．ｎ；
ここで、ｅｈ、ｅｘ、ｅｄ、ｅｓは０〜２ｐの間のランダムな値である。実際には、付加的なマスキングを有効にするために、ｐの値は望ましくは少なくとも６３に等しくなるべきである。
【００５０】
第二ステージ２２において、アルゴリズムは必要な回数だけ本発明における乗算器を利用することにより実行される。アルゴリズムに対する変更は必要とされず、そして本発明における乗算器によって生み出される全ての結果はマスキングされ、アルゴリズムがマスキングされたデータのみを処理することを可能にする。
【００５１】
アルゴリズムが実行された後、マスキング無しで得られたであろう結果を見出すため、第三ステージ２３において「マスキング解除」操作が、マスキングされた値２３１に対して適用される。この操作は例えば、特定の入力値を選択することにより、本発明における乗算器によって実行され得る。
【００５２】
図２に例示されている装置の利用は、計算において使用される値が初期値と相互に関係しないことを示す。その結果、アルゴリズムの実行中に物理的サイズを解析している攻撃者は従って最早、入力変数の適切な選択を通じて、計算中に使用される秘密データを捜し出すことは出来ない。従来の装置においては、例えば、攻撃者は多数の「０」又は多数の「１」を含む入力変数を選択することができ、次に該入力変数と消費量との間の関係を決定するために電力消費量を解析し、及び／又はアルゴリズムにより実行された演算のタイプを推論することができる。付加的なマスキングの使用のおかげで、これらの「０」又は「１」の長い初期シーケンスは、アルゴリズムにより使用される演算数内で消去され、従って攻撃者自身により選定された任意の入力変数に関し、攻撃者が成し得たであろう任意の仮定を低下させる。
【００５３】
計算時間に関する追加費用及び、ハードウェア組み込みの場合の回路面積は、非常に小さい。
【００５４】
該乗算ブロックはハードウェアの実装を変えることなく、あらゆるサイズの数に対して実行されるべきアルゴリズムを有利に可能にする。ＦＰＧＡ又はＡＳＩＣにおいて総合され、本発明において実現された乗算器は、例えば任意のモジュールである１２８、２５６、５１２、１０２４、及び２０４８ビットのサイズに対する乗算を実行する。
【００５５】
本発明における方法の一つの利点は、構成要素の構造に関する限り、透明に存在する暗号計算要素において実行出来ることである。実際、従来のモジュラー乗算計算の演算子のみを、本発明において方法を実行する演算子に置き換えることだけで十分である。この基本的演算の置き換えは、暗号化又は認証のような安全性メカニズムにより用いられる機能が、本発明における演算子を利用するため、次に構成要素の保護を全体的に改善する。
【図面の簡単な説明】
【００５６】
【図１】本発明におけるマスキングされたモジュラー乗算において用いられる、乗算−加算セルの一例である。
【図２】モジュラー乗算の演算を利用したアルゴリズムによる、本発明におけるマスキングプロセスを実行する乗算器の利用の概略図である。
【符号の説明】
【００５７】
１  乗算−加算器
２  三入力の加算器
２１  第一ステージ
２２  第二ステージ
２３  第三ステージ
２３１  マスキングされた値
【図１】
2008304920.tif 000003
【図２】
2008304920.tif 000004
【外国語明細書】
2008304920000001.pdf