(57)【要約】  本発明は、サイドチャネル攻撃に対して耐性のあるデータ暗号化法に関し、ここではモジュール（Ｍ）を用いて入力値（ａ）のモジュラ逆数が返値（ｒ）として決定される。本発明が課題としているのは、モジュラ逆数の決定において、わずかなコストだけでサイドチャネル攻撃に対する耐性が得られる同時にインプリメントにおける制限が最小になるようにすることである。このために提案されるのは、第１サブステップにおいて入力値（ａ）と乱数（ｃ）とから第１の積（ｄ）を形成し、第２サブステップにおいて上記のモジュール（Ｍ）を用いて第１の積（ｄ）のモジュラ逆数（ｅ）を決定し、第３サブステップにおいて上記の乱数（ｃ）とモジュラ逆数（ｅ）との第２の積（ｂ）を決定し、第４サブステップにおいて上記の返値（ｒ）を第２の積（ｂ）に設定することである。
2008542802.tif 000002
【特許請求の範囲】
【請求項１】
サイドチャネル攻撃に対して耐性のあるデータ暗号化および／または復号化法であって、
該方法では計算ユニットを使用し、
暗号化および／または復号化のステップにて、モジュール（Ｍ）を用いて入力値（ａ）のモジュラ逆数を返値（ｒ）として決定する形式の、データ暗号化および／または復号化法において、
−  第１サブステップにて前記入力値（ａ）と乱数（ｃ）とから第１の積（ｄ）を形成し、
−  第２サブステップにて前記のモジュール（Ｍ）によって第１の積（ｄ）のモジュラ逆数（ｅ）を決定し、
−  第３サブステップにて前記の乱数（ｃ）とモジュラ逆数（ｅ）との第２の積（ｂ）を決定し、
−  第４サブステップにて前記の返値（ｒ）を第２の積（ｂ）に設定することを特徴とする、
データ暗号化および／または復号化方法。
【請求項２】
前記の返値（ｒ）を決定した後、乱数（ｃ）、第１の積（ｄ）、第２の積（ｂ）およびモジュラ逆数（ｅ）を消去する、
請求項１または２に記載の方法。
【請求項３】
計算ユニットを有するタコグラフであって、
該計算ユニットにより、データが暗号化および／または復号化され、
また前記計算ユニットを構成して、当該の暗号化および／または復号化のステップにて当該計算ユニットのモジュール（Ｍ）によって入力値（ａ）のモジュラ逆数が返値（ｒ）として決定されるようにした形式のタコグラフにおいて、
前記計算ユニットにより、
−  第１サブステップにて入力値（ａ）と乱数（ｃ）とから第１の積（ｄ）が形成され、
−  第２サブステップにて前記のモジュール（Ｍ）によって第１の積（ｄ）のモジュラ逆数（ｅ）が決定され、
−  第３サブステップにて前記の計算ユニットにより、前記の乱数（ｃ）とモジュラ逆数（ｅ）との第２の積（ｂ）が決定され、
−  第４サブステップにて前記の計算ユニットにより、前記の返値（ｒ）が第２の積（ｂ）に設定されることを特徴とする
タコグラフ。
【請求項４】
計算ユニットを有する移動式データ担体、例えばデータカードしとして構成されたデータ担体であって、
前記計算ユニットにより、データが暗号化および／または復号化され、
また前記計算ユニットを構成して、当該の暗号化および／または復号化のステップにて当該計算ユニットのモジュール（Ｍ）によって入力値（ａ）のモジュラ逆数が返値（ｒ）として決定されるようにした形式の移動式データ担体において、
前記計算ユニットにより、
−  第１サブステップにて入力値（ａ）と乱数（ｃ）とから第１の積（ｄ）が形成され、
−  第２サブステップにて前記のモジュール（Ｍ）によって第１の積（ｄ）のモジュラ逆数（ｅ）が決定され、
−  第３サブステップにて前記の乱数（ｃ）とモジュラ逆数（ｅ）との第２の積（ｂ）が決定され、
−  第４サブステップにて前記の返値（ｒ）が第２の積（ｂ）に設定されることを特徴とする
移動式データ担体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、モジュールを用いて入力値のモジュラ逆数である返値を計算する方法であってサイドチャネル攻撃に対して耐性のある方法に関する。
【０００２】
サイドチャネル攻撃は、暗号解読法の１つのクラスである。暗号アプリケーションに対する従来の攻撃とは異なり、ここでは攻撃者は、基礎にある抽象数学的なアルゴリズムを破ろうとするのではなく、暗号方式の固有のインプリメントに攻撃する。このために攻撃者は、具体的なインプリメントの容易に入手可能な物理的測定量を使用する。この物理的測定量は、例えば、計算の実行時間、計算中のプロセッサの電流消費および電磁放射またはエラーが誘発された際のインプリメントの挙動である。個々の計算の物理的測定値は、直接解析することができ、これは、例えばＳＰＡ（Simple Power Analysys）を用いて行われるか、また攻撃者は複数の計算の測定値を記録（例えば、ストレージオシロスコープを使用して）し、引き続いて、例えばＤＰＡ（Diffential Power Analysis）を用いてこれらの測定値を統計的に評価することによって行われる。
【０００３】
サイドチャネル攻撃は、古典的な暗号解読法よりも格段に有効であることが多く、またアルゴリズムの観点からは比較的安全とみなされる方式であっても、このアルゴリズムのインプリメントがサイドチャネル攻撃に対して保護されていない場合には破ることが可能である。例えばスマートカードおよび組み込みアプリケーションついては、サイドチャネル攻撃に対する防御手段が重要である。
【０００４】
サイドチャネル攻撃はつぎの刊行物においてすでに扱われている。すなわち、
Kocher: Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other Systems, Crypto 1996, LNCS 1109, 第104-113頁, Springer；
Kocher, Jaffe, Jun: Differential power analysis, Crypto 1999, LNCS 1666, 第388- 397頁, Springer；
Messerges, Dabbish, Sloan: Power analysis attacks of modular exponentiation in smartcards, CHES 1999, LNCS 1717, 第144-157頁, Springer
においてすでに扱われている。
【０００５】
またBoneh, Demillo, Lipton: On the importance of checking cryptographic protocols for faults, Eurocrypt 1997, LNCS 1233, 第37-51頁, Springerには、エラーが誘発された際のインプリメントの動作中または計算中のプロセッサの電磁放射および電流消費から得られる情報を利用することについての示唆がすでに記載されている。
【０００６】
逆数計算のための数学的手法は、
Menezes, van Oorschot, Vanstone: Handbook of applied cryptography, CRC-Press 1996
にも記載されている。
【０００７】
暗号方式に対する、例えば、ＤＥＳおよびＡＥＳに対するマスキング法は、
Goubin, Patarin: DES and differential power analysis, CHES 1999, LNCS 1717, 第158-172頁, Springer；
Akkar, Giraud: An implementation of DES and AES, secure against some attacks, CHES 2001, LNCS 2162, 第309-318頁, Springer；
Messerges: Securing the AES finalists against power analysis attacks, FSE 2000, LNCS 1978, 第150-164頁, Springer；
Coron, Goubin: On boolean and arithmetic masking against differential power analysis, CHES2000, LNCS 1965, 第213-237頁, Springer;
Trichina, de Seta, Germani: Simplified adaptive multiplicative masking for AES and its securized implementation, CHES 2002, LNCS 2523, 第187-197頁, Springer；
Golic, Tymen: Multiplicative masking and power analysis of AES, CHES 2002, LNCS 2523, 第198- 212頁, Springer
からも公知である。
【０００８】
デジタル署名標準にしたがってデジタル署名を形成することは
FIPS 186: Digital signature Standard, Federal Information Processing Standards Publication 186, NIST 1997
にも取り上げられている。
【０００９】
本発明の目的は、殊にＳＰＡおよびＤＰＡに対してモジュラ逆数計算を保護することである。多くの暗号方式（例えば公開鍵方式）は、有限体における算術演算を使用している。ここで使用される重要な計算ステップは、有限体におけるモジュラ逆数の計算である。
【００１０】
モジュラ逆数計算のための方式は、一般に最大公約数を計算するアルゴリズム（拡張されたユークリッドアルゴリズムまたは２値で動作するSteinアルゴリズムのようなその変化形態）に基づいているか、またはフェルマーの小定理を使用して、逆数をモジュラの指数に還元している。最大公約数の計算に基づくアルゴリズムは、データに大きく依存するフローを有する。すなわち、除算の回数により、例えば、逆数を求めようとする数を推定できるのである。２値で動作するSteinアルゴリズムでは体のモジュールの計算の中間値が奇数の場合に、この中間値に１が加えられる。この加算がアルゴリズムの第ｉ番目のステップに行われた否かを攻撃者が観察できる場合、この攻撃者は、逆数を求めようとする数がビット単位でわかってしまう。したがってこのアルゴリズムでは攻撃者は、実行時間、電流消費または電磁放射から、逆数を求めようとする数を容易に推定できるのである。フェルマーの小定理に基づくアルゴリズムは確かに一様なフローを有するが、格段に遅くしたがってより一層非効率的である。
【００１１】
サイドチャネル攻撃から防御するために一般に使用されるテクニックは、保護すべき情報と、他のすべての測定可能な信号との間の信号ノイズ比を劣化させ、秘密の情報の観察を困難にしようとするか、またはランダム化テクニックを使用して、保護すべき情報と、測定される値との間の相関を取り除こうとするかのいずれかである。秘密の情報の観察を困難にする方法には、例えば、保護に値する情報に依存しデータに依存する分岐の回避、電流プロフィールがわずかにしか変動しないプログラムステップの使用、または実行時間が計算データに依存しないプログラム部分の使用、ランダムおよび／または冗長なプログラム部分の実行などが含まれる。これらの対抗手段により、一般的にＳＰＡ攻撃に対する保護が行われるが、インプリメントが不利な制限を受けてしまうという欠点を有するのである。
【００１２】
保護しようとする情報と測定値との間の相関を取り除くためのランダム化テクニックは、ＤＰＡの統計的な解析法から保護するために使用される。このような手段では、一般的に秘密の情報が乱数値でマスキングされる。ここでは新たな計算の度にマスクに対して、新しい無関係な乱数値が選択される。この場合に攻撃者は都度、この攻撃者にとってはランダムに見える計算を測定することになる。それはこの攻撃者はこのマスクを知らないため、測定される物理的な値と、入力または出力データとの間の簡単な相関を決定できないからである。
【００１３】
従来技術の問題および欠点から出発して本発明が課題としているのは、つぎのようなモジュラ逆数計算方法を提供することである。すなわち、サイドチャネル攻撃に対して耐性を有し、同時にインプリメントにおける制限およびサイドチャネル攻撃に対する保護のための付加的なコストが少なく維持される上記のような方法を提供することである。
【００１４】
このために本発明により、請求項１に記載した方法が提案される。この他に請求項３に記載したタコグラフおよび請求項４に記載したデータカードが提供される。このタコグラフおよびデータカードはそれぞれ、これらが請求項１の方法にしたがって動作するように構成されている。これらの請求項を各引用する従属請求項には有利な発展形態が記載されている。
【００１５】
本発明のテクニックによって可能になるのは、モジュラ逆数計算法の任意のインプリメント（最大公約数の計算に基づく極めて効率的なアルゴリズムも）を簡単な変換によってＳＰＡおよびＤＰＡから防御することである。本発明にしたがって算術的同型（arithmetisch homomorph）なマスキング法を使用することの利点は、例えば、マスキングを計算の入力側において行うことができ、また出力側において結果からマスキング除去を行うことができ、また同時にモジュラ逆数計算のインプリメントがＳＰＡおよびＤＰＡ攻撃から防御されるのである。暗号化または復号化法における本発明の有利な応用は、殊に本発明によるタコグラフまたは本発明による移動形データ担体における本発明の有利な応用は、例えば、デジタル署名標準ＤＳＡにしたがってデジタル署名を形成する際に必要な逆数計算である。
【００１６】
ｐを素数、ｑをｑ｜ｐ−１なる素数、０＜ｇ＜ｐなるｇを(Ｚ／ｐＺ)*における位数ｑの部分巡回群の生成元、０＜ａ＜ｑなるａを秘密鍵、Ａ＝ｇ^ａ mod pを対応する公開鍵、０≦ｍ＜ｐなるｍを署名すべきメッセージとする。メッセージｍおよび公開鍵ａに対して署名（ｒ，ｓ）を計算するため、ＤＳＡにしたがってつぎの計算ステップを計算ユニットによって実行する。すなわち、
１）  秘密のままのしておかなければならない、０＜ｋ＜ｑなる乱数ｋを選択する、
２）  ｒ = (ａ^k mod p) mod qを計算する、
３）  モジュールＭを用いてモジュラ逆数h = 1/k mod qを計算する、
４）  s = h*(m+a*r) mod qを計算する。
【００１７】
ステップ３）におけるモジュラ逆数の計算は、本発明より極めて有利にもＳＰＡから保護することができるため、秘密の乱数ｋ、いわゆる短期鍵は攻撃者に知られることがない。攻撃者がこの短期鍵を知った場合、この攻撃者はこの署名を作成した人の秘密鍵ａを算出することができることになる。
【００１８】
有限体Ｋにおけるモジュラ逆数を計算するインプリメントを有する本発明のモジュールＭは、例えば、有限体Ｋに属する元ａから、サイドチャネル攻撃に耐性を有する形でモジュラ逆数を決定することができる。ここで本発明の方法は、例えば、つぎのようなステップで動作する。すなわち、
１）  計算ユニットにより、Ｋからランダムな元ｃが選択される、
２）  計算ユニットにより、d = a * cが決定される、
３）  モジュールＭによって逆数e = M(d)が決定される、
４）  計算ユニットにより、b = e * cが決定される、
５）  計算ユニットにより、返値ｒ := bが設定される。
【００１９】
攻撃者は、ステップ３）において、ランダムに同じ分布で選択された有限体の元dの逆数だけを観察するが、この元ｄはこの計算の真の入力値ａに依存しない。この攻撃者にはランダムに選択された元cは知られていないため、この攻撃者はＳＰＡ攻撃によっても、ＤＰＡ攻撃によっても、Ｍによって実行される計算ステップから情報を得ることはできないのである。
【００２０】
本発明の方法の利点は、保護されていないインプリメントを本発明にしたがい、ステップ１），２），４）および５）だけ拡張すれば、ＳＰＡおよびＤＰＡに対する耐性が得られるという点にもある。例えば、ユークリッドアルゴリズムに基づく効率的なモジュラ逆数計算方法を変更なしに使用可能である。ここでの付加的な計算コストは、フェルマーの小定理に基づく逆数計算方法よりも格段に少ない。
【００２１】
本発明の方法の有利な発展形態では、中間結果ｃ，ｄおよびｅは各計算ステップの後、消去される。
【００２２】
以下では具体的な実施例に基づき、図面を参照して本発明を詳しく説明するが、本発明はこの実施例の説明には制限されない。ここで
図１は、本発明によるデータカードを有する本発明のタコグラフの概略透視図を示しており、
図２は、本発明による方法のフローの概略図を示している。
【００２３】
図１には本発明によるタコグラフＤＴＣＯと本発明によるデータカードＤＣとが示されている。データカードＤＣは２つの収容孔２のうちの１つを通してＤＴＣＯに挿入することができるため、これらの２つのエレメント間のデータ伝送中にはタコグラフＤＴＣＯ内のデータカードＤＣは、外部から触れることができない形で収容される。このタコグラフＤＴＣＯは、前面側３に２つの収容孔２の他に表示ユニット１および操作エレメント４を有する。データカードＤＣは、収容孔２に挿入した後、データ線路５によって中央のプロセッサＣＰＵに接続される。このプロセッサは内部の記憶装置ＭＥＭにアクセスする。同様にデータカードも詳細に示していない記憶装置および中央プロセッサを有する。
【００２４】
タコグラフＤＴＣＯとデータカードＤＣとの間のデータ伝送は、セッション鍵によって暗号化され、暗号化および解読中にタコグラフＤＴＣＯおよびデータカードＤＣの中央のプロセッサＣＰＵによって、例えば入力値Ａのモジュラ逆数が決定される。このためにプロセッサＣＰＵは、図２に示したモジュールＫＲＹを使用する。
【００２５】
モジュールＫＲＹは、暗号化のフローの一部分である。入力値ａはモジュールＫＲＹに渡され、このモジュール内でモジュールMod Invに転送される。モジュールMod Invにより、まず乱数Ｃが決定され、これと入力値ａとを乗算して積ｄが得られる。モジュールＭを用いて積ｄのモジュラ逆数ｅを決定し、引き続いて乱数ｃと乗算する。返値ｒにこの積を設定してモジュールＫＲＹに結果として返す。
【図面の簡単な説明】
【００２６】
【図１】本発明によるデータカードを有する本発明のタコグラフの概略透視図である。
【図２】本発明によるフローの概略図である。
【図１】
2008542802.tif 000003
【図２】
2008542802.tif 000004
【手続補正書】
【提出日】平成18年10月20日(2006.10.20)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
サイドチャネル攻撃に対して耐性のあるデータ暗号化および／または復号化法であって、
該方法では計算ユニットを使用し、
暗号化および／または復号化のステップにて、モジュール（Ｍ）を用いて入力値（ａ）のモジュラ逆数を返値（ｒ）として決定する形式の、データ暗号化および／または復号化法において、
−  第１サブステップにて乱数（ｃ）を選択し、
−  第２サブステップにて前記入力値（ａ）と乱数（ｃ）とから第１の積（ｄ）を形成し、
−  第３サブステップにて、前記のモジュール（Ｍ）を用い、モジュラ逆数（ｅ）を計算するアルゴリズムのインプリメントであってサイドチャネル攻撃に対して保護されていないインプリメントにより、第１の積（ｄ）のモジュラ逆数（ｅ）を決定し、
−  第４サブステップにて前記の乱数（ｃ）とモジュラ逆数（ｅ）との第２の積（ｂ）を決定し、
−  第５サブステップにて前記の返値（ｒ）を第２の積（ｂ）に設定することを特徴とする、
データ暗号化および／または復号化方法。
【請求項２】
前記の返値（ｒ）を決定した後、乱数（ｃ）、第１の積（ｄ）、第２の積（ｂ）およびモジュラ逆数（ｅ）を消去する、
請求項１に記載の方法。
【請求項３】
前記の保護されていないインプリメントは、ユークリッドアルゴリズムベースである、
請求項１または２に記載の方法。
【請求項４】
計算ユニットを有するタコグラフであって、
該計算ユニットにより、データが暗号化および／または復号化され、
また前記計算ユニットを構成して、当該の暗号化および／または復号化のステップにて当該計算ユニットのモジュール（Ｍ）によって入力値（ａ）のモジュラ逆数が返値（ｒ）として決定されるようにした形式のタコグラフにおいて、
前記計算ユニットを構成して、
−  第１サブステップにて乱数（ｃ）が選択され、
−  第２サブステップにて入力値（ａ）と乱数（ｃ）とから第１の積（ｄ）が形成され、
−  第３サブステップにて前記のモジュール（Ｍ）を用い、モジュラ逆数（ｅ）を計算するアルゴリズムのインプリメントであってサイドチャネル攻撃に対して保護されていないインプリメントにより、第１の積（ｄ）のモジュラ逆数（ｅ）が決定され、
−  第４サブステップにて前記の乱数（ｃ）とモジュラ逆数（ｅ）との第２の積（ｂ）が決定され、
−  第５サブステップにて前記の計算ユニットにより、前記の返値（ｒ）が第２の積（ｂ）に設定されるようにしたことを特徴とする
タコグラフ。
【請求項５】
計算ユニットを有する移動式データ担体、例えばデータカードとして構成されたデータ担体であって、
前記計算ユニットにより、データが暗号化および／または復号化され、
また前記計算ユニットを構成して、当該の暗号化および／または復号化のステップにて当該計算ユニットのモジュール（Ｍ）によって入力値（ａ）のモジュラ逆数が返値（ｒ）として決定されるようにした形式の移動式データ担体において、
前記計算ユニットを構成して、
−  第１サブステップにて乱数（ｃ）が選択され、
−  第２サブステップにて入力値（ａ）と乱数（ｃ）とから第１の積（ｄ）が形成され、
−  第３サブステップにて前記のモジュール（Ｍ）を用い、モジュラ逆数（ｅ）を計算するアルゴリズムのインプリメントであってサイドチャネル攻撃に対して保護されていないインプリメントにより、第１の積（ｄ）のモジュラ逆数（ｅ）が決定され、
−  第４サブステップにて前記の乱数（ｃ）とモジュラ逆数（ｅ）との第２の積（ｂ）が決定され、
−  第５サブステップにて前記の計算ユニットにより、前記の返値（ｒ）が第２の積（ｂ）に設定されるようにしたことを特徴とする
タコグラフ。
移動式データ担体。
【国際調査報告】
2008542802.tif 000005
2008542802.tif 000006
2008542802.tif 000007
2008542802.tif 000008
2008542802.tif 000009
2008542802.tif 000010