サイドチャネル攻撃からの保護
本発明は、暗号化機構に関し、かかる暗号化機構を組み込んだ暗号化装置に関する。暗号化機構は、新しいタイプのマスキング機構を組み込むことによって、知られている暗号化機構よりも、サイドチャネル攻撃に対してよりよい抵抗を提供する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、サイドチャネル攻撃から暗号化装置を保護するための方法に関し、かかる方法を埋め込む暗号化装置に関する。
【背景技術】
【０００２】
当技術分野で知られているように、暗号化装置は、暗号化機構を実施する装置である。暗号化装置の例は、スマートカード、ＵＳＢキー、ドングル、携帯端末装置（別名、ＰＤＡ）、移動体電話、パーソナルコンピュータ（別名、ＰＣ）などを含む。かかる暗号化装置は、特に、ユーザの電子商取引を保護するために使用される。表現「電子商取引」は、その最も広い意味で解釈されるべきである。すなわち、電子商取引は、金融取引に限定されず、任意のインターネット取引、電気通信ネットワークなどを介して発生する任意の取引なども含む。電子商取引を保護することは、デジタル署名された電子文書、復号電子文書、第三者および／または認証ユーザとの折衝セッションキーの暗号化機構を含み得る。上の４つの暗号化機構は、当技術分野でよく知られている。これらは限定的ではなく（その他の暗号化機構が存在する）、必須ではない（例えば、暗号化装置はデジタル署名機構内に埋め込まれているとは限らない）。
【発明の開示】
【発明が解決しようとする課題】
【０００３】
暗号化機構は入力と出力とを有する。例えば、暗号化機構は、平文からなる入力と、暗号文からなる出力とを有する場合がある。初めて暗号化装置が設計された際、人々は、かれらの暗号化機構に唯一可能な攻撃は、入力および出力の攻撃であると思った。しかし、暗号化装置は、いわゆる「サイドチャネル攻撃」も可能であることが判明した。サイドチャネル攻撃は、暗号化装置が、正規の入出力手段以外の入出力手段を有するという事実に依存する。例えば、不正規の入力手段の使用は、暗号化装置を加熱することによって、そのクロックを修正すること（例えば、推奨される限度より上に加速すること）によって、紫外線、Ｘ線、または超音波の下に置くことによって、振動させること、またはそうでない場合、機械的に影響を与えることなどによって、暗号操作を変更することを含み得る。かかる変更は、入念に設計されることが可能であり（例えば、カウンタが減少されようとするまさにそのときにグリッチ（ｇｌｉｔｃｈ）が導入され得る）または無作為であってもよい（例えば、目的は単に無作為の障害を引き起こし、機密情報を漏らす可能性がある障害の結果を分析することであり得る）。不正規の出力手段の使用は、暗号化装置の電力消費量を分析すること（例えば、電子部品は、「２乗だけ」などの簡単な演算よりも、「２乗および乗算」などの複雑な演算を実行するためにより多くの電力を要求する）、暗号化装置によって生み出された電磁場を分析すること、暗号化装置によって放たれた音を分析することなどを含み得る。よく知られているサイドチャネル攻撃は、単純電力解析（Ｓｉｍｐｌｅ Ｐｏｗｅｒ Ａｎａｌｙｓｉｓ）（ＳＰＡ）、電力差分解析（Ｄｉｆｆｅｒｅｎｔｉａｌ Ｐｏｗｅｒ Ａｎａｌｙｓｉｓ）（ＤＰＡ）、故障差分解析（Ｄｉｆｆｅｒｅｎｔｉａｌ Ｆａｕｌｔ Ａｎａｌｙｓｉｓ）（ＤＦＡ）を含む。
【課題を解決するための手段】
【０００４】
暗号化機構は、暗号化装置内に安全に記憶されると想定される少なくとも１つの秘密Ｄを必要とする機構からなる。Ｄはいかなる攻撃を介しても暗号化装置の外に漏れるべきではない。当技術分野で知られている方法において、Ｄはｎ桁の２進数の形（ｄ０、ｄ１、．．．ｄｎ−１）２で表されることが可能であり、ｄｉは（０からｎ−１の間の各整数ｉに関する）ビットである。本明細書の残りの部分で、欧州特許条約に従って請求項内で括弧の中に置かれた参照符号によりあいまいさをもたらさないために、数学における常として、指数Ｄは（ｄ０、ｄ１、．．．ｄｎ−１）２の代わりに｛ｄ０、ｄ１、．．．ｄｎ−１｝２と示されることになる。
【０００５】
数学の一部門である抽象代数学では、モノイド（Ｍ、⊥）は、代数的集合として定義され、集合は結合的２項演算（ａｓｓｏｃｉａｔｉｖｅ ｂｉｎａｒｙ ｏｐｅｒａｔｉｏｎ）⊥の下で閉じられ（ｃｌｏｓｅｄ ｕｎｄｅｒ）ており、集合は単位元を有する。グループと反対に、モノイドでは、すべての要素が逆元を有するとは限らない。演算⊥はまた、その他の記号を用いて表されることも可能である。例えば、演算⊥は加法演算（記号＋）として、乗法演算（記号＊）などとして表されることが可能である。この表現は、単に名目的であり、モノイドの属性に影響を与えない。本明細書の残りの部分で、モノイドは乗法演算＊を用いて表されることになり、欧州特許条約に従って請求項内で括弧の中に置かれた参照符号によりあいまいさをもたらさないために、（Ｍ、＊）の代わりに｛Ｍ、＊｝と示されることになる。
【０００６】
モノイドは暗号化において広く行きわたっている。暗号化分野で最も行きわたったモノイドは、多くの逆元（例えば、２８０の逆元）を有する大きなモノイドである。例えば、ＲＳＡアルゴリズムの場合、ほとんどすべての要素は可逆である（例外は、特に、ｐおよびｑの倍数である）。Ｍ＊は、モノイド｛Ｍ、＊｝の集合Ｍのすべての可逆元を含む集合を示す。
【０００７】
本明細書の残りの部分で、すべてのモノイドは、すべての要素が交換可能なモノイドである可換モノイド（ａｂｅｌｉａｎ ｍｏｎｏｉｄｓ）である。
【０００８】
特にサイドチャネル攻撃に敏感な暗号化機構は、一定の値ｖに等しい（すなわち、ｖ＝０またはｖ＝１）各ｄｉに関して、Ｘ２およびＹ＊Ｚを計算し（Ｘ、ＹおよびＺはモノイド｛Ｍ、＊｝の３要素である）、その他の値に等しい各ｄｊ（ｄｊ＝１−ｖ）に関して、はＴ２を計算する（Ｔはモノイド｛Ｍ、＊｝の要素である）機構を含む。かかる機構の例は、ＲＳＡ冪剰余（ｍｏｄｕｌａｒ ｅｘｐｏｎｅｎｔｉａｔｉｏｎ）を含む。
【０００９】
Ｘ２は２乗演算と呼ばれ、Ｘ＊Ｘを意味する。
【００１０】
ＸｎはＸ＊Ｘ＊．．．＊Ｘを意味し、Ｘはｎ回現れる。
【００１１】
注記：加法的記法を用いたモノイドでは、Ｘ２は２Ｘと書かれることになり、Ｘ＋Ｘを意味することになる。同様に、ＸｎはｎＸと書かれることになり、Ｘ＋Ｘ＋．．．＋Ｘを意味することになり、Ｘはｎ回現れる。
【００１２】
Ｙ＊Ｚは乗法演算と呼ばれる。
【００１３】
本発明は、サイドチャネル攻撃に対して上述の特に敏感な暗号化機構の抵抗を改善する。かかる機構の例は、楕円曲線小数点乗算（ｅｌｌｉｐｔｉｃ ｃｕｒｖｅ ｐｏｉｎｔ ｍｕｌｔｉｐｌｉｃａｔｉｏｎｓ）、およびＲＳＡ演算またはＤｉｆｆｉｅ Ｈｅｌｌｍａｎ鍵確立（ｋｅｙ ｅｓｔａｂｌｉｓｈｍｅｎｔ）を実行する場合に使用される冪剰余を含む。本発明はまた、暗号化機構を保護するために要求される処理量も制限する。本発明は、特定のタイプのマスキング機構（別名、目隠し機構（ｂｌｉｎｄｉｎｇ ｍｅｃｈａｎｉｓｍ））を導入することによってこれを行う。
【００１４】
本発明およびその利点は、添付の図面を参照して、以下の明細書内でより詳細に説明される。
【発明を実施するための最良の形態】
【００１５】
図１は、冪剰余からなる暗号化機構の例を説明する。この種の冪剰余は、特に、ＲＳＡアルゴリズムおよびＤｉｆｆｉｅ Ｈｅｌｌｍａｎアルゴリズムを用いて実施される。
【００１６】
ステップ２から分かるように、指数Ｄの各ビットｄｉに関して、係数２乗（ｍｏｄｕｌａｒ ｓｑｕａｒｉｎｇ）が実行される（サブステップ２．ｉ）。ｄｉが１に等しい場合、剰余乗算（ｍｏｄｕｌａｒ ｍｕｌｔｉｐｌｉｃａｔｉｏｎ）が実行される（サブステップ２．ｉｉ）。
【００１７】
Ｄは、通常、乱数から算出される。一般に、Ｄのハミング重み（ｈａｍｍｉｎｇ ｗｅｉｇｈｔ）はおよそｎ／２である。したがって、一般に、図１の方法は、ｎ回の係数２乗演算と、約ｎ／２回の剰余乗算とを必要とする。
【００１８】
当技術分野で知られているように、このタイプの暗号化機構は、ＳＰＡなど、最も単純なサイドチャネル攻撃に対してさえ非常に敏感である。実際に、乗法演算の実行および２乗演算の実行の間、電力消費量は同じではない。したがって、暗号機構を実施する暗号化装置上にプローブを置き、電力消費量を測定し、電力追跡内で乗算と２乗を区別し、それにより、すべてのビットｄｉの値を識別することが可能である。指数Ｄは、その場合、攻撃者によって回復される。
【００１９】
図２は「平衡冪剰余アルゴリズム」として当技術分野で知られている、サイドチャネル攻撃からの第１のレベルの保護を含む暗号化機構の例を説明する。
【００２０】
この方法は、ｄｉが０に等しい場合、擬似乗算が実行される第３のステップｉｉｉが加えられる点を除いて、図１の方法に類似する。この第３のステップの結果、ビットが０に等しいにせよ、１に等しいにせよ、電力消費量は非常に近接する。
【００２１】
ｎ回の乗法演算とｎ回の２乗演算とが存在するため、この方法の複雑さは増大される。しかし、上で示されたように、基本的なサイドチャネル攻撃に対するその抵抗も同様に改善される。
【００２２】
残念ながら、この方法は、ＳＥ攻撃（セーフエラー攻撃（ｓａｆｅ ｅｒｒｏｒ ａｔｔａｃｋ））として知られている、もう１つのサイドチャネル攻撃に依然として非常に敏感である。実際に、擬似乗算の間、暗号化機構が妨害される場合、乗算は失敗するが、擬似乗算は最終結果に使用されないため、最終結果は依然として影響を受けない。したがって、攻撃者は、この例では、０に等しいビットである擬似ビットを見つけ、すべてのその他のビットが１に等しいことを推測することが可能であり、その結果、秘密の値Ｄは回復されている。
【００２３】
図３は、「Ｊｏｙｅ ＆ Ａｌ．冪剰余アルゴリズム」として当技術分野で知られ、ＪｏｙｅおよびＹｅｎによってＣＨＥＳ２００２で開示された、サイドチャネル攻撃からの第２のレベルの保護を含む、知られている暗号化機構の例を説明する。これはＭｏｎｔｇｏｍｅｒｙラダーアルゴリズム（Ｌａｄｄｅｒ ａｌｇｏｒｉｔｈｍ）に基づく。
【００２４】
図３の暗号化機構は、図２の暗号化機構の制限を克服することを目指す。
【００２５】
このため、もはや擬似演算は存在しない。代わりに、（最後のラウンドを除いて）すべての乗算の結果が最終結果において使用される。したがって、機構を妨害することは、常に誤った出力につながる。
【００２６】
この暗号化機構の複雑さは、図２の複雑さと同じである（ｎ回の乗法演算、ｎ回の２乗演算）。
【００２７】
しかし、この暗号化機構は、依然としてＤＰＡ攻撃に敏感である。当技術分野で知られているように、ＤＰＡ攻撃では、攻撃者が入力Ｘの値を設定することができる場合、攻撃者は、ｄｉの値について推測し、選択されたサンプル数全体にわたって電力消費量内の相関関係を調査することによりその値を検証することによって、ステップｉおよびｉｉの次の中間値の値を予測することが可能である。
【００２８】
図３の暗号化機構など、知られている技術を改善することが本発明の目的である。
【００２９】
図４に示されるように、図３の教示をマスキング機構と組み合わせることは可能であろう。マスキングは入力要素を乱数で乗算することであり得、それにより、ＤＰＡ攻撃の予測ステップを不可能にする。残念ながら、図４に示される技術は、およそ４＊ｎ回の演算を要求し、当該技術をこれまでの技術よりも２倍遅いものにする。図４に示される技術はまた、冪剰余も２回実行する。最初は、マスキングされた入力に関して、もう１つの時期は、マスキングに使用されるマスクに関する。この二重冪剰余により、秘密指数Ｄは２度使用され、これは機構を潜在的に弱める。
【００３０】
本発明による暗号化機構は、ｎ桁の２進数｛ｄ０、ｄ１、．．．ｄｎ−１｝２として表され得る秘密Ｄを必要とする。暗号化機構は、ＸＤに等しい出力要素ＯＵＴを計算するように構成され、Ｘはモノイド｛Ｍ、＊｝の要素である。機構は、第１の変数ＶＡＲ０と第２の変数ＶＡＲ１とを含む。暗号化機構は、各ステップＭＵＬｉの間、暗号化装置がＶＡＲ１−ｄｉ＊ＶＡＲｄｉを計算するようにｎ個のステップ｛ＭＵＬｉ｝ｉ＝ｎ−１．．０と、各ステップＳＱｉの間、暗号化装置がＶＡＲｄｉ＊ＶＡＲｄｉを計算するようにｎ個の別のステップ｛ＳＱｉ｝ｉ＝ｎ−１．．０とを含む。各ステップＳＱｉは、０からｎ−１の間の任意のｉに関してステップＭＵＬｉの後で実行され、各ステップＭＵＬｉ−１は、１からｎ−１の間の任意のｉに関してステップＭＵＬｉの後で実行される。機構は、
ａ．ランダム要素ＭＳＫ＿ＩＮＰＵＴを生成するステップと、
ｂ．要素Ｘとランダム要素ＭＳＫ＿ＩＮＰＵＴとを使用することによってマスキングされた要素ＭＡＳＫＥＤ＿Ｘを作成するステップと、
ｃ．マスキングされた要素ＭＡＳＫＥＤ＿Ｘを使用して、上述のステップ｛ＭＵＬｉ｝ｉ＝ｎ−１．．０と｛ＳＱｉ｝ｉ＝ｎ−１．．０とを必要とする、マスキングされた出力要素ＭＡＳＫＥＤ＿ＯＵＴを計算するステップと、
ｄ．秘密Ｄを必要とせずに、ランダム要素ＭＳＫ＿ＩＮＰＵＴから出力マスクＭＳＫ＿ＯＵＴＰＵＴを計算するステップと、
ｅ．マスキングされた出力要素ＭＡＳＫＥＤ＿ＯＵＴと出力マスクＭＳＫ＿ＯＵＴＰＵＴとを使用して、出力要素ＯＵＴを計算するステップと
を含むことを特徴とし、
ステップｄはステップａとステップｅの間の任意のときに発生し、ステップａ、ｂ、ｃ、ｅは連続的である。
【００３１】
図５から分かるように、出力マスクの計算は、マスキングされた出力要素の計算と共に実行することが可能である。図６から分かるように、この計算は（図のステップ４に示されるように、後に、または前に）連続的に実行することも可能である。この計算を並行して、例えば、図７に示されるように、２つの異なるスレッド内で、実行することも可能である（ステップ３ａおよび３ｂを参照）。
【００３２】
マスキング演算の結果、攻撃者はマスクを知らず、中間結果に関して推定する可能性を有さないため、ＤＰＡ攻撃はもはや適用可能ではない。
【００３３】
要素Ｘは、もう１つの機構によって暗号化機構に供給された入力要素であり得、または暗号化機構内で生成されることも可能である。例えば、タイムスタンプ機構からなる暗号化機構では、現在の時間は、機構内で安全に決定され、次いで、機構内でデジタル署名されることが可能である。
【００３４】
同様に、出力要素ＯＵＴは、暗号化機構によってもう１つの機構に通信されることが可能であり、出力要素ＯＵＴは、暗号化機構内部に維持されることが可能であり、または暗号化機構内で後処理されて、後処理された形でもう１つの機構に送られることが可能である。
【００３５】
好ましい実施形態では、本発明による暗号化機構は、ランダム要素ＭＳＫ＿ＩＮＰＵＴがＭ＊（上から分かるように、Ｍの逆元の集合）に属すようなものである。ＭＳＫ＿ＩＮＰＵＴが値Ｒに等しい場合、Ｒ−１によって、モノイド｛Ｍ、＊｝の演算＊に関するＲの逆元を示す。関数ｆ：ＭＡＳＫＥＤ＿Ｘ→ＭＡＳＫＥＤ＿ＯＵＴが、ｆ（Ｒ＊Ｘ）＝ｇ（Ｒ）＊ｆ（Ｘ）であるように関数ｇが存在するようなものである暗号化機構の場合、ＸおよびＲを乗算することによって要素ＸにマスクＭＳＫ＿ＩＮＰＵＴを適用して、出力要素を取得する目的でマスキングされた出力に適用するために出力マスク（ｇ（Ｒ））−１を計算することが可能である。いくつかの事例では、（ｇ（Ｒ））−１は、ｇ（Ｒ−１）に等しい場合がある。かかる実施形態では、逆元Ｒ−１は、したがって、出力マスクＭＳＫ＿ＯＵＰＵＴを計算するために使用され得る。
【００３６】
本発明による好ましい暗号化機構は、出力マスクＭＳＫ＿ＯＵＴＰＵＴの計算が、各ステップＲ＿ＳＱｉの間、暗号化装置がＭＳＫｉ＊ＭＳＫｉを計算するように、ｎ個のステップ｛Ｒ＿ＳＱｉ｝ｉ＝ｎ−１．．０を含むことが可能であり、ＭＳＫｉはモノイド｛Ｍ、＊｝の要素であり、初期値ＭＳＫｎは乱数Ｒの逆元から取得されており、最終値ＭＳＫ０は、マスキングされた出力ＭＡＳＫＥＤ＿ＯＵＴの値からマスキングを取る（ｕｎｍａｓｋ）ために使用される出力マスクＭＳＫ＿ＯＵＴＰＵＴである。これは、関数ｇの計算がステップＲ＿ＳＱｉを必要とすることによって実行され得るように、関数ｇに関連する機構に関して特に有利である。
【００３７】
より詳細には、本発明による好ましい実施形態では、ＭＳＫｉは、ｎ−１から０までに等しいｉに関して、ＭＳＫｉ＋１＊ＭＳＫｉ＋１に等しい可能性がある。これは、関数ｇ：ＭＳＫｎ→ＭＳＫ０に関連する機構に関して特に有利であり、ｎ−１から０までに等しいｉに関して、ＭＳＫｉ＝ＭＳＫｉ＋１＊ＭＳＫｉ＋１である。
【００３８】
好ましい暗号化機構では、マスキングされた要素ＭＡＳＫＥＤ＿ＸはＸ＊Ｒに等しく、出力要素ＯＵＴはＭＡＳＫＥＤ＿ＯＵＴ＊ＭＳＫ０に等しく、ＭＳＫｎはＲ−１に等しく、第１の変数ＶＡＲ０の初期値はランダム要素の値Ｒに設定されており、第２の変数ＶＡＲ１の初期値はマスキングされた要素ＭＡＳＫＥＤ＿Ｘの値に設定されており、各ステップＭＵＬｉは、ＶＡＲ１−ｄｉ＊ＶＡＲｄｉを計算して、結果をＶＡＲ１−ｄｉ内に記憶することであり、各ステップＳＱｉは、ＶＡＲｄｉ＊ＶＡＲｄｉを計算して、結果をＶＡＲｄｉ内に記憶することである。
【００３９】
図５は、
１．乱数が生成される第１のステップ。これは、例えば、暗号化機構を実施する暗号化装置内に埋め込まれたハードウェア乱数生成器（ｈａｒｄｗａｒｅ ｒａｎｄｏｍ ｎｕｍｂｅｒ ｇｅｎｅｒａｔｏｒ）によって行われることが可能である。実際に、乱数は、可能な限り予測不可能であることが好ましく、これは、当技術分野で知られているようなハードウェア手段を用いて最もよく達成される。
２．変数ＶＡＲ０、ＶＡＲ１およびＭＳＫｎが初期化される第２のステップ、
３．マスキングされた出力（ループの最終ラウンドの後のＶＡＲ０値）がマスキングされた要素から計算され、出力マスクＭＳＫ０が計算される、第３のステップ、
４．出力マスクＭＳＫ０を用いてマスキングされた出力からマスキングが取られ、暗号化機構を起動した実体に戻される、第４のステップ
を含む、本発明の好ましい実施形態の例を説明する。
【００４０】
暗号化機構は、入力として要素Ｘと秘密Ｄとを使用する。好ましい実施形態では、秘密Ｄは安全に記憶され、したがって、暗号化機構が起動されるたびに暗号化機構に引きわたされなくてよい。要素Ｘは、一般に、入力パラメータとして暗号化機構に引きわたされるが、（例えば、暗号化機構内で利用可能なクロックに基づくタイムスタンプを伴う上の説明から分かるように）暗号化機構自体によって決定されることも可能である。
【００４１】
本発明は、上で説明されたように、秘密Ｄを記憶して、暗号化機構を実施する暗号化装置にも関する。本発明は、より詳細には、スマートカードタイプの暗号化装置に関する。
【００４２】
本発明は、最新技術の暗号化機構と比較して追加要件がほとんどないため、スマートカードなどの埋め込みシステムに関して特に有利である。本発明はＲＳＡアルゴリズムに大変適している。実際に、本発明は、伝統的な暗号化機構と比較して鍵素材に関する追加情報を要求しない。特に、本発明は、暗号化機構に利用可能にされるＲＳＡ鍵ペアの公開指数を要求しない。
【００４３】
本発明は、任意の追加のパラメータを要求せず、したがって、静的モードでセッション鍵を確立するために特に非常に便利であるため、Ｄｉｆｆｉｅ Ｈｅｌｌｍａｎアルゴリズムに関して同様に有利である。
【００４４】
本発明は、より強力なプロセッサ（または、暗号化アルゴリズムが部分的にもしくは完全にハードウェア内で実施される場合、暗号プロセッサ）を要求することになる、指数に関する、または要素Ｘに関する追加マスクを要求しないという点で、上の両方のアルゴリズムに関しても有利である。
【００４５】
図５の好ましい実施形態の複雑さは、およそ２＊ｎ回の２乗演算およびｎ回の乗算、すなわち、最も近い方法（図３のＭｏｎｔｇｏｍｅｒｙラダー）よりも５０％だけ多い、約３＊ｎ回のＣＰＵ集中演算を必要とし、さらに多くのＲＡＭを要求しない（最高で５０％）。
【００４６】
入力マスクとして使用されるいくつかのランダム要素に関して、ステップＳＱ＿ＲＤｉは（指数ｉの一定の値ｉ＿ｗｅａｋに関して）ＭＳＫｉ＿ｗｅａｋ＝１をもたらす可能性があり、その場合、すべての後続の値（ＭＡＳＫｉ＿ｗｅａｋ−１、ＭＳＫｉ＿ｗｅａｋ−２、など）は同様に１に等しくなる点に留意されたい。この状況は出力マスクを有さないことに相当する（マスキングされた出力と出力とは等しい）ため、この状況は弱い出力マスクに対応する。しかし、この脆弱性は利用するのが困難であり、発生する可能性は非常に少ない。弱いマスクにつながるランダム要素の可能性は非常に低い。例えば、ＲＳＡ２０４８の場合、弱いランダム要素を選ぶ可能性は多くて１．９＊１０−７であることが推定される。可能性は、ＲＳＡ鍵の値に依存し、実際には、多くの場合、上の値よりさらに低い。可能性は、いくつかのランダム逆元を選び、それらを一緒に乗算することによって任意に小さくされ得る（すべての要素が弱い場合だけ、要素の積は弱くなることになる）。
【図面の簡単な説明】
【００４７】
【図１】サイドチャネル攻撃からのいかなる保護も伴わない典型的な暗号化機構を表す図である。
【図２】「平衡冪剰余アルゴリズム（ｂａｌａｎｃｅｄ ｍｏｄｕｌａｒ ｅｘｐｏｎｅｎｔｉａｔｉｏｎ ａｌｇｏｒｉｔｈｍ）」として当技術分野で知られている、サイドチャネル攻撃からの第１のレベルの保護を用いた暗号化機構を表す図である。
【図３】「Ｊｏｙｅ ＆ Ａｌ．冪剰余アルゴリズム」として当技術分野で知られている、サイドチャネル攻撃から第２のレベルの保護を用いた暗号化機構を表す図である。
【図４】冪剰余のための可能なマスキング機構を表す図である。
【図５】サイドチャネル攻撃からのより高いレベルの保護を提供する、本発明による好ましい暗号化機構を表す図である。
【図６】図５の機構の改変形態を示す図である。
【図７】図５の機構の改変形態を示す図である。
【技術分野】
【０００１】
本発明は、サイドチャネル攻撃から暗号化装置を保護するための方法に関し、かかる方法を埋め込む暗号化装置に関する。
【背景技術】
【０００２】
当技術分野で知られているように、暗号化装置は、暗号化機構を実施する装置である。暗号化装置の例は、スマートカード、ＵＳＢキー、ドングル、携帯端末装置（別名、ＰＤＡ）、移動体電話、パーソナルコンピュータ（別名、ＰＣ）などを含む。かかる暗号化装置は、特に、ユーザの電子商取引を保護するために使用される。表現「電子商取引」は、その最も広い意味で解釈されるべきである。すなわち、電子商取引は、金融取引に限定されず、任意のインターネット取引、電気通信ネットワークなどを介して発生する任意の取引なども含む。電子商取引を保護することは、デジタル署名された電子文書、復号電子文書、第三者および／または認証ユーザとの折衝セッションキーの暗号化機構を含み得る。上の４つの暗号化機構は、当技術分野でよく知られている。これらは限定的ではなく（その他の暗号化機構が存在する）、必須ではない（例えば、暗号化装置はデジタル署名機構内に埋め込まれているとは限らない）。
【発明の開示】
【発明が解決しようとする課題】
【０００３】
暗号化機構は入力と出力とを有する。例えば、暗号化機構は、平文からなる入力と、暗号文からなる出力とを有する場合がある。初めて暗号化装置が設計された際、人々は、かれらの暗号化機構に唯一可能な攻撃は、入力および出力の攻撃であると思った。しかし、暗号化装置は、いわゆる「サイドチャネル攻撃」も可能であることが判明した。サイドチャネル攻撃は、暗号化装置が、正規の入出力手段以外の入出力手段を有するという事実に依存する。例えば、不正規の入力手段の使用は、暗号化装置を加熱することによって、そのクロックを修正すること（例えば、推奨される限度より上に加速すること）によって、紫外線、Ｘ線、または超音波の下に置くことによって、振動させること、またはそうでない場合、機械的に影響を与えることなどによって、暗号操作を変更することを含み得る。かかる変更は、入念に設計されることが可能であり（例えば、カウンタが減少されようとするまさにそのときにグリッチ（ｇｌｉｔｃｈ）が導入され得る）または無作為であってもよい（例えば、目的は単に無作為の障害を引き起こし、機密情報を漏らす可能性がある障害の結果を分析することであり得る）。不正規の出力手段の使用は、暗号化装置の電力消費量を分析すること（例えば、電子部品は、「２乗だけ」などの簡単な演算よりも、「２乗および乗算」などの複雑な演算を実行するためにより多くの電力を要求する）、暗号化装置によって生み出された電磁場を分析すること、暗号化装置によって放たれた音を分析することなどを含み得る。よく知られているサイドチャネル攻撃は、単純電力解析（Ｓｉｍｐｌｅ Ｐｏｗｅｒ Ａｎａｌｙｓｉｓ）（ＳＰＡ）、電力差分解析（Ｄｉｆｆｅｒｅｎｔｉａｌ Ｐｏｗｅｒ Ａｎａｌｙｓｉｓ）（ＤＰＡ）、故障差分解析（Ｄｉｆｆｅｒｅｎｔｉａｌ Ｆａｕｌｔ Ａｎａｌｙｓｉｓ）（ＤＦＡ）を含む。
【課題を解決するための手段】
【０００４】
暗号化機構は、暗号化装置内に安全に記憶されると想定される少なくとも１つの秘密Ｄを必要とする機構からなる。Ｄはいかなる攻撃を介しても暗号化装置の外に漏れるべきではない。当技術分野で知られている方法において、Ｄはｎ桁の２進数の形（ｄ０、ｄ１、．．．ｄｎ−１）２で表されることが可能であり、ｄｉは（０からｎ−１の間の各整数ｉに関する）ビットである。本明細書の残りの部分で、欧州特許条約に従って請求項内で括弧の中に置かれた参照符号によりあいまいさをもたらさないために、数学における常として、指数Ｄは（ｄ０、ｄ１、．．．ｄｎ−１）２の代わりに｛ｄ０、ｄ１、．．．ｄｎ−１｝２と示されることになる。
【０００５】
数学の一部門である抽象代数学では、モノイド（Ｍ、⊥）は、代数的集合として定義され、集合は結合的２項演算（ａｓｓｏｃｉａｔｉｖｅ ｂｉｎａｒｙ ｏｐｅｒａｔｉｏｎ）⊥の下で閉じられ（ｃｌｏｓｅｄ ｕｎｄｅｒ）ており、集合は単位元を有する。グループと反対に、モノイドでは、すべての要素が逆元を有するとは限らない。演算⊥はまた、その他の記号を用いて表されることも可能である。例えば、演算⊥は加法演算（記号＋）として、乗法演算（記号＊）などとして表されることが可能である。この表現は、単に名目的であり、モノイドの属性に影響を与えない。本明細書の残りの部分で、モノイドは乗法演算＊を用いて表されることになり、欧州特許条約に従って請求項内で括弧の中に置かれた参照符号によりあいまいさをもたらさないために、（Ｍ、＊）の代わりに｛Ｍ、＊｝と示されることになる。
【０００６】
モノイドは暗号化において広く行きわたっている。暗号化分野で最も行きわたったモノイドは、多くの逆元（例えば、２８０の逆元）を有する大きなモノイドである。例えば、ＲＳＡアルゴリズムの場合、ほとんどすべての要素は可逆である（例外は、特に、ｐおよびｑの倍数である）。Ｍ＊は、モノイド｛Ｍ、＊｝の集合Ｍのすべての可逆元を含む集合を示す。
【０００７】
本明細書の残りの部分で、すべてのモノイドは、すべての要素が交換可能なモノイドである可換モノイド（ａｂｅｌｉａｎ ｍｏｎｏｉｄｓ）である。
【０００８】
特にサイドチャネル攻撃に敏感な暗号化機構は、一定の値ｖに等しい（すなわち、ｖ＝０またはｖ＝１）各ｄｉに関して、Ｘ２およびＹ＊Ｚを計算し（Ｘ、ＹおよびＺはモノイド｛Ｍ、＊｝の３要素である）、その他の値に等しい各ｄｊ（ｄｊ＝１−ｖ）に関して、はＴ２を計算する（Ｔはモノイド｛Ｍ、＊｝の要素である）機構を含む。かかる機構の例は、ＲＳＡ冪剰余（ｍｏｄｕｌａｒ ｅｘｐｏｎｅｎｔｉａｔｉｏｎ）を含む。
【０００９】
Ｘ２は２乗演算と呼ばれ、Ｘ＊Ｘを意味する。
【００１０】
ＸｎはＸ＊Ｘ＊．．．＊Ｘを意味し、Ｘはｎ回現れる。
【００１１】
注記：加法的記法を用いたモノイドでは、Ｘ２は２Ｘと書かれることになり、Ｘ＋Ｘを意味することになる。同様に、ＸｎはｎＸと書かれることになり、Ｘ＋Ｘ＋．．．＋Ｘを意味することになり、Ｘはｎ回現れる。
【００１２】
Ｙ＊Ｚは乗法演算と呼ばれる。
【００１３】
本発明は、サイドチャネル攻撃に対して上述の特に敏感な暗号化機構の抵抗を改善する。かかる機構の例は、楕円曲線小数点乗算（ｅｌｌｉｐｔｉｃ ｃｕｒｖｅ ｐｏｉｎｔ ｍｕｌｔｉｐｌｉｃａｔｉｏｎｓ）、およびＲＳＡ演算またはＤｉｆｆｉｅ Ｈｅｌｌｍａｎ鍵確立（ｋｅｙ ｅｓｔａｂｌｉｓｈｍｅｎｔ）を実行する場合に使用される冪剰余を含む。本発明はまた、暗号化機構を保護するために要求される処理量も制限する。本発明は、特定のタイプのマスキング機構（別名、目隠し機構（ｂｌｉｎｄｉｎｇ ｍｅｃｈａｎｉｓｍ））を導入することによってこれを行う。
【００１４】
本発明およびその利点は、添付の図面を参照して、以下の明細書内でより詳細に説明される。
【発明を実施するための最良の形態】
【００１５】
図１は、冪剰余からなる暗号化機構の例を説明する。この種の冪剰余は、特に、ＲＳＡアルゴリズムおよびＤｉｆｆｉｅ Ｈｅｌｌｍａｎアルゴリズムを用いて実施される。
【００１６】
ステップ２から分かるように、指数Ｄの各ビットｄｉに関して、係数２乗（ｍｏｄｕｌａｒ ｓｑｕａｒｉｎｇ）が実行される（サブステップ２．ｉ）。ｄｉが１に等しい場合、剰余乗算（ｍｏｄｕｌａｒ ｍｕｌｔｉｐｌｉｃａｔｉｏｎ）が実行される（サブステップ２．ｉｉ）。
【００１７】
Ｄは、通常、乱数から算出される。一般に、Ｄのハミング重み（ｈａｍｍｉｎｇ ｗｅｉｇｈｔ）はおよそｎ／２である。したがって、一般に、図１の方法は、ｎ回の係数２乗演算と、約ｎ／２回の剰余乗算とを必要とする。
【００１８】
当技術分野で知られているように、このタイプの暗号化機構は、ＳＰＡなど、最も単純なサイドチャネル攻撃に対してさえ非常に敏感である。実際に、乗法演算の実行および２乗演算の実行の間、電力消費量は同じではない。したがって、暗号機構を実施する暗号化装置上にプローブを置き、電力消費量を測定し、電力追跡内で乗算と２乗を区別し、それにより、すべてのビットｄｉの値を識別することが可能である。指数Ｄは、その場合、攻撃者によって回復される。
【００１９】
図２は「平衡冪剰余アルゴリズム」として当技術分野で知られている、サイドチャネル攻撃からの第１のレベルの保護を含む暗号化機構の例を説明する。
【００２０】
この方法は、ｄｉが０に等しい場合、擬似乗算が実行される第３のステップｉｉｉが加えられる点を除いて、図１の方法に類似する。この第３のステップの結果、ビットが０に等しいにせよ、１に等しいにせよ、電力消費量は非常に近接する。
【００２１】
ｎ回の乗法演算とｎ回の２乗演算とが存在するため、この方法の複雑さは増大される。しかし、上で示されたように、基本的なサイドチャネル攻撃に対するその抵抗も同様に改善される。
【００２２】
残念ながら、この方法は、ＳＥ攻撃（セーフエラー攻撃（ｓａｆｅ ｅｒｒｏｒ ａｔｔａｃｋ））として知られている、もう１つのサイドチャネル攻撃に依然として非常に敏感である。実際に、擬似乗算の間、暗号化機構が妨害される場合、乗算は失敗するが、擬似乗算は最終結果に使用されないため、最終結果は依然として影響を受けない。したがって、攻撃者は、この例では、０に等しいビットである擬似ビットを見つけ、すべてのその他のビットが１に等しいことを推測することが可能であり、その結果、秘密の値Ｄは回復されている。
【００２３】
図３は、「Ｊｏｙｅ ＆ Ａｌ．冪剰余アルゴリズム」として当技術分野で知られ、ＪｏｙｅおよびＹｅｎによってＣＨＥＳ２００２で開示された、サイドチャネル攻撃からの第２のレベルの保護を含む、知られている暗号化機構の例を説明する。これはＭｏｎｔｇｏｍｅｒｙラダーアルゴリズム（Ｌａｄｄｅｒ ａｌｇｏｒｉｔｈｍ）に基づく。
【００２４】
図３の暗号化機構は、図２の暗号化機構の制限を克服することを目指す。
【００２５】
このため、もはや擬似演算は存在しない。代わりに、（最後のラウンドを除いて）すべての乗算の結果が最終結果において使用される。したがって、機構を妨害することは、常に誤った出力につながる。
【００２６】
この暗号化機構の複雑さは、図２の複雑さと同じである（ｎ回の乗法演算、ｎ回の２乗演算）。
【００２７】
しかし、この暗号化機構は、依然としてＤＰＡ攻撃に敏感である。当技術分野で知られているように、ＤＰＡ攻撃では、攻撃者が入力Ｘの値を設定することができる場合、攻撃者は、ｄｉの値について推測し、選択されたサンプル数全体にわたって電力消費量内の相関関係を調査することによりその値を検証することによって、ステップｉおよびｉｉの次の中間値の値を予測することが可能である。
【００２８】
図３の暗号化機構など、知られている技術を改善することが本発明の目的である。
【００２９】
図４に示されるように、図３の教示をマスキング機構と組み合わせることは可能であろう。マスキングは入力要素を乱数で乗算することであり得、それにより、ＤＰＡ攻撃の予測ステップを不可能にする。残念ながら、図４に示される技術は、およそ４＊ｎ回の演算を要求し、当該技術をこれまでの技術よりも２倍遅いものにする。図４に示される技術はまた、冪剰余も２回実行する。最初は、マスキングされた入力に関して、もう１つの時期は、マスキングに使用されるマスクに関する。この二重冪剰余により、秘密指数Ｄは２度使用され、これは機構を潜在的に弱める。
【００３０】
本発明による暗号化機構は、ｎ桁の２進数｛ｄ０、ｄ１、．．．ｄｎ−１｝２として表され得る秘密Ｄを必要とする。暗号化機構は、ＸＤに等しい出力要素ＯＵＴを計算するように構成され、Ｘはモノイド｛Ｍ、＊｝の要素である。機構は、第１の変数ＶＡＲ０と第２の変数ＶＡＲ１とを含む。暗号化機構は、各ステップＭＵＬｉの間、暗号化装置がＶＡＲ１−ｄｉ＊ＶＡＲｄｉを計算するようにｎ個のステップ｛ＭＵＬｉ｝ｉ＝ｎ−１．．０と、各ステップＳＱｉの間、暗号化装置がＶＡＲｄｉ＊ＶＡＲｄｉを計算するようにｎ個の別のステップ｛ＳＱｉ｝ｉ＝ｎ−１．．０とを含む。各ステップＳＱｉは、０からｎ−１の間の任意のｉに関してステップＭＵＬｉの後で実行され、各ステップＭＵＬｉ−１は、１からｎ−１の間の任意のｉに関してステップＭＵＬｉの後で実行される。機構は、
ａ．ランダム要素ＭＳＫ＿ＩＮＰＵＴを生成するステップと、
ｂ．要素Ｘとランダム要素ＭＳＫ＿ＩＮＰＵＴとを使用することによってマスキングされた要素ＭＡＳＫＥＤ＿Ｘを作成するステップと、
ｃ．マスキングされた要素ＭＡＳＫＥＤ＿Ｘを使用して、上述のステップ｛ＭＵＬｉ｝ｉ＝ｎ−１．．０と｛ＳＱｉ｝ｉ＝ｎ−１．．０とを必要とする、マスキングされた出力要素ＭＡＳＫＥＤ＿ＯＵＴを計算するステップと、
ｄ．秘密Ｄを必要とせずに、ランダム要素ＭＳＫ＿ＩＮＰＵＴから出力マスクＭＳＫ＿ＯＵＴＰＵＴを計算するステップと、
ｅ．マスキングされた出力要素ＭＡＳＫＥＤ＿ＯＵＴと出力マスクＭＳＫ＿ＯＵＴＰＵＴとを使用して、出力要素ＯＵＴを計算するステップと
を含むことを特徴とし、
ステップｄはステップａとステップｅの間の任意のときに発生し、ステップａ、ｂ、ｃ、ｅは連続的である。
【００３１】
図５から分かるように、出力マスクの計算は、マスキングされた出力要素の計算と共に実行することが可能である。図６から分かるように、この計算は（図のステップ４に示されるように、後に、または前に）連続的に実行することも可能である。この計算を並行して、例えば、図７に示されるように、２つの異なるスレッド内で、実行することも可能である（ステップ３ａおよび３ｂを参照）。
【００３２】
マスキング演算の結果、攻撃者はマスクを知らず、中間結果に関して推定する可能性を有さないため、ＤＰＡ攻撃はもはや適用可能ではない。
【００３３】
要素Ｘは、もう１つの機構によって暗号化機構に供給された入力要素であり得、または暗号化機構内で生成されることも可能である。例えば、タイムスタンプ機構からなる暗号化機構では、現在の時間は、機構内で安全に決定され、次いで、機構内でデジタル署名されることが可能である。
【００３４】
同様に、出力要素ＯＵＴは、暗号化機構によってもう１つの機構に通信されることが可能であり、出力要素ＯＵＴは、暗号化機構内部に維持されることが可能であり、または暗号化機構内で後処理されて、後処理された形でもう１つの機構に送られることが可能である。
【００３５】
好ましい実施形態では、本発明による暗号化機構は、ランダム要素ＭＳＫ＿ＩＮＰＵＴがＭ＊（上から分かるように、Ｍの逆元の集合）に属すようなものである。ＭＳＫ＿ＩＮＰＵＴが値Ｒに等しい場合、Ｒ−１によって、モノイド｛Ｍ、＊｝の演算＊に関するＲの逆元を示す。関数ｆ：ＭＡＳＫＥＤ＿Ｘ→ＭＡＳＫＥＤ＿ＯＵＴが、ｆ（Ｒ＊Ｘ）＝ｇ（Ｒ）＊ｆ（Ｘ）であるように関数ｇが存在するようなものである暗号化機構の場合、ＸおよびＲを乗算することによって要素ＸにマスクＭＳＫ＿ＩＮＰＵＴを適用して、出力要素を取得する目的でマスキングされた出力に適用するために出力マスク（ｇ（Ｒ））−１を計算することが可能である。いくつかの事例では、（ｇ（Ｒ））−１は、ｇ（Ｒ−１）に等しい場合がある。かかる実施形態では、逆元Ｒ−１は、したがって、出力マスクＭＳＫ＿ＯＵＰＵＴを計算するために使用され得る。
【００３６】
本発明による好ましい暗号化機構は、出力マスクＭＳＫ＿ＯＵＴＰＵＴの計算が、各ステップＲ＿ＳＱｉの間、暗号化装置がＭＳＫｉ＊ＭＳＫｉを計算するように、ｎ個のステップ｛Ｒ＿ＳＱｉ｝ｉ＝ｎ−１．．０を含むことが可能であり、ＭＳＫｉはモノイド｛Ｍ、＊｝の要素であり、初期値ＭＳＫｎは乱数Ｒの逆元から取得されており、最終値ＭＳＫ０は、マスキングされた出力ＭＡＳＫＥＤ＿ＯＵＴの値からマスキングを取る（ｕｎｍａｓｋ）ために使用される出力マスクＭＳＫ＿ＯＵＴＰＵＴである。これは、関数ｇの計算がステップＲ＿ＳＱｉを必要とすることによって実行され得るように、関数ｇに関連する機構に関して特に有利である。
【００３７】
より詳細には、本発明による好ましい実施形態では、ＭＳＫｉは、ｎ−１から０までに等しいｉに関して、ＭＳＫｉ＋１＊ＭＳＫｉ＋１に等しい可能性がある。これは、関数ｇ：ＭＳＫｎ→ＭＳＫ０に関連する機構に関して特に有利であり、ｎ−１から０までに等しいｉに関して、ＭＳＫｉ＝ＭＳＫｉ＋１＊ＭＳＫｉ＋１である。
【００３８】
好ましい暗号化機構では、マスキングされた要素ＭＡＳＫＥＤ＿ＸはＸ＊Ｒに等しく、出力要素ＯＵＴはＭＡＳＫＥＤ＿ＯＵＴ＊ＭＳＫ０に等しく、ＭＳＫｎはＲ−１に等しく、第１の変数ＶＡＲ０の初期値はランダム要素の値Ｒに設定されており、第２の変数ＶＡＲ１の初期値はマスキングされた要素ＭＡＳＫＥＤ＿Ｘの値に設定されており、各ステップＭＵＬｉは、ＶＡＲ１−ｄｉ＊ＶＡＲｄｉを計算して、結果をＶＡＲ１−ｄｉ内に記憶することであり、各ステップＳＱｉは、ＶＡＲｄｉ＊ＶＡＲｄｉを計算して、結果をＶＡＲｄｉ内に記憶することである。
【００３９】
図５は、
１．乱数が生成される第１のステップ。これは、例えば、暗号化機構を実施する暗号化装置内に埋め込まれたハードウェア乱数生成器（ｈａｒｄｗａｒｅ ｒａｎｄｏｍ ｎｕｍｂｅｒ ｇｅｎｅｒａｔｏｒ）によって行われることが可能である。実際に、乱数は、可能な限り予測不可能であることが好ましく、これは、当技術分野で知られているようなハードウェア手段を用いて最もよく達成される。
２．変数ＶＡＲ０、ＶＡＲ１およびＭＳＫｎが初期化される第２のステップ、
３．マスキングされた出力（ループの最終ラウンドの後のＶＡＲ０値）がマスキングされた要素から計算され、出力マスクＭＳＫ０が計算される、第３のステップ、
４．出力マスクＭＳＫ０を用いてマスキングされた出力からマスキングが取られ、暗号化機構を起動した実体に戻される、第４のステップ
を含む、本発明の好ましい実施形態の例を説明する。
【００４０】
暗号化機構は、入力として要素Ｘと秘密Ｄとを使用する。好ましい実施形態では、秘密Ｄは安全に記憶され、したがって、暗号化機構が起動されるたびに暗号化機構に引きわたされなくてよい。要素Ｘは、一般に、入力パラメータとして暗号化機構に引きわたされるが、（例えば、暗号化機構内で利用可能なクロックに基づくタイムスタンプを伴う上の説明から分かるように）暗号化機構自体によって決定されることも可能である。
【００４１】
本発明は、上で説明されたように、秘密Ｄを記憶して、暗号化機構を実施する暗号化装置にも関する。本発明は、より詳細には、スマートカードタイプの暗号化装置に関する。
【００４２】
本発明は、最新技術の暗号化機構と比較して追加要件がほとんどないため、スマートカードなどの埋め込みシステムに関して特に有利である。本発明はＲＳＡアルゴリズムに大変適している。実際に、本発明は、伝統的な暗号化機構と比較して鍵素材に関する追加情報を要求しない。特に、本発明は、暗号化機構に利用可能にされるＲＳＡ鍵ペアの公開指数を要求しない。
【００４３】
本発明は、任意の追加のパラメータを要求せず、したがって、静的モードでセッション鍵を確立するために特に非常に便利であるため、Ｄｉｆｆｉｅ Ｈｅｌｌｍａｎアルゴリズムに関して同様に有利である。
【００４４】
本発明は、より強力なプロセッサ（または、暗号化アルゴリズムが部分的にもしくは完全にハードウェア内で実施される場合、暗号プロセッサ）を要求することになる、指数に関する、または要素Ｘに関する追加マスクを要求しないという点で、上の両方のアルゴリズムに関しても有利である。
【００４５】
図５の好ましい実施形態の複雑さは、およそ２＊ｎ回の２乗演算およびｎ回の乗算、すなわち、最も近い方法（図３のＭｏｎｔｇｏｍｅｒｙラダー）よりも５０％だけ多い、約３＊ｎ回のＣＰＵ集中演算を必要とし、さらに多くのＲＡＭを要求しない（最高で５０％）。
【００４６】
入力マスクとして使用されるいくつかのランダム要素に関して、ステップＳＱ＿ＲＤｉは（指数ｉの一定の値ｉ＿ｗｅａｋに関して）ＭＳＫｉ＿ｗｅａｋ＝１をもたらす可能性があり、その場合、すべての後続の値（ＭＡＳＫｉ＿ｗｅａｋ−１、ＭＳＫｉ＿ｗｅａｋ−２、など）は同様に１に等しくなる点に留意されたい。この状況は出力マスクを有さないことに相当する（マスキングされた出力と出力とは等しい）ため、この状況は弱い出力マスクに対応する。しかし、この脆弱性は利用するのが困難であり、発生する可能性は非常に少ない。弱いマスクにつながるランダム要素の可能性は非常に低い。例えば、ＲＳＡ２０４８の場合、弱いランダム要素を選ぶ可能性は多くて１．９＊１０−７であることが推定される。可能性は、ＲＳＡ鍵の値に依存し、実際には、多くの場合、上の値よりさらに低い。可能性は、いくつかのランダム逆元を選び、それらを一緒に乗算することによって任意に小さくされ得る（すべての要素が弱い場合だけ、要素の積は弱くなることになる）。
【図面の簡単な説明】
【００４７】
【図１】サイドチャネル攻撃からのいかなる保護も伴わない典型的な暗号化機構を表す図である。
【図２】「平衡冪剰余アルゴリズム（ｂａｌａｎｃｅｄ ｍｏｄｕｌａｒ ｅｘｐｏｎｅｎｔｉａｔｉｏｎ ａｌｇｏｒｉｔｈｍ）」として当技術分野で知られている、サイドチャネル攻撃からの第１のレベルの保護を用いた暗号化機構を表す図である。
【図３】「Ｊｏｙｅ ＆ Ａｌ．冪剰余アルゴリズム」として当技術分野で知られている、サイドチャネル攻撃から第２のレベルの保護を用いた暗号化機構を表す図である。
【図４】冪剰余のための可能なマスキング機構を表す図である。
【図５】サイドチャネル攻撃からのより高いレベルの保護を提供する、本発明による好ましい暗号化機構を表す図である。
【図６】図５の機構の改変形態を示す図である。
【図７】図５の機構の改変形態を示す図である。
【特許請求の範囲】
【請求項１】
ｎ桁の２進数｛ｄ０、ｄ１、．．．ｄｎ−１｝２として表され得る秘密Ｄを必要とし、ＸＤに等しい出力要素ＯＵＴを計算するように構成されている暗号化機構にして、Ｘがモノイド｛Ｍ、＊｝の要素であり、当該機構が、第１の変数ＶＡＲ０と第２の変数ＶＡＲ１とを含み、各ステップＭＵＬｉの間、暗号化装置がＶＡＲ１−ｄｉ＊ＶＡＲｄｉを計算するように、当該暗号化機構がｎ個のステップ｛ＭＵＬｉ｝ｉ＝ｎ−１．．０を含み、各ステップＳＱｉの間、暗号化装置がＶＡＲｄｉ＊ＶＡＲｄｉを計算するように、当該暗号化機構がｎ個のその他のステップ｛ＳＱｉ｝ｉ＝ｎ−１．．０を含み、各ステップＳＱｉが、０とｎ−１の間の任意のｉに関してステップＭＵＬｉの後で実行されており、各ステップＭＵＬｉ−１が、１とｎ−１の間の任意のｉに関してステップＭＵＬｉの後で実行されている、暗号化機構であって、
ａ．ランダム要素ＭＳＫ＿ＩＮＰＵＴ（Ｒ）を生成するステップと、
ｂ．要素Ｘとランダム要素ＭＳＫ＿ＩＮＰＵＴとを使用することによってマスキングされた要素ＭＡＳＫＥＤ＿Ｘ（ＶＡＲ１）を作成するステップと、
ｃ．マスキングされた要素ＭＡＳＫＥＤ＿Ｘを使用して、上述のステップ｛ＭＵＬｉ｝ｉ＝ｎ−１．．０と｛ＳＱｉ｝ｉ＝ｎ−１．．０とを必要とする、マスキングされた出力要素ＭＡＳＫＥＤ＿ＯＵＴ（ＶＡＲ０）を計算するステップと、
ｄ．秘密Ｄを必要とせずに、ランダム要素ＭＳＫ＿ＩＮＰＵＴから出力マスクＭＳＫ＿ＯＵＴＰＵＴ（ＭＳＫ０）を計算するステップと、
ｅ．マスキングされた出力要素ＭＡＳＫＥＤ＿ＯＵＴと出力マスクＭＳＫ＿ＯＵＴＰＵＴとを使用して、出力要素ＯＵＴを計算するステップと
を含むことを特徴とし、
ステップｄがステップａとステップｅの間の任意のときに発生し、ステップａ、ｂ、ｃ、ｅが連続的である、暗号化機構。
【請求項２】
ランダム要素ＭＳＫ＿ＩＮＰＵＴ（Ｒ）がモノイド｛Ｍ、＊｝の演算＊に関する逆元（Ｒ−１）を有し、逆元が出力マスクＭＳＫ＿ＯＵＴＰＵＴを計算するために使用可能である、請求項１に記載の暗号化機構。
【請求項３】
出力マスクＭＳＫ＿ＯＵＴＰＵＴの計算が、各ステップＲ＿ＳＱｉの間、暗号化装置がＭＳＫｉ＊ＭＳＫｉを計算するように、ｎ個のステップ｛Ｒ＿ＳＱｉ｝ｉ＝ｎ−１．．０を含み、ＭＳＫｉがモノイド｛Ｍ、＊｝の要素であり、初期値ＭＳＫｎがランダム要素ＭＳＫ＿ＩＮＰＵＴの逆元（Ｒ−１）から取得されており、最終値ＭＳＫ０がマスキングされた出力ＭＡＳＫＥＤ＿ＯＵＴの値からマスキングを取るために使用される出力マスクＭＳＫ＿ＯＵＴＰＵＴである、請求項１に記載の暗号化機構。
【請求項４】
ＭＳＫｉが、ｎ−１から０までに等しいｉに関して、ＭＳＫｉ＋１＊ＭＳＫｉ＋１に等しい、請求項３に記載の暗号化機構。
【請求項５】
マスキングされた要素ＭＡＳＫＥＤ＿ＸがＸ＊Ｒに等しく、出力要素ＯＵＴがＭＡＳＫＥＤ＿ＯＵＴ＊ＭＳＫ０に等しく、ＭＳＫｎがＲの逆元に等しく、第１の変数ＶＡＲ０の初期値がランダム要素の値（Ｒ）に設定されており、第２の変数ＶＡＲ１の初期値がマスキングされた要素ＭＡＳＫＥＤ＿Ｘの値に設定されており、各ステップＭＵＬｉがＶＡＲ１−ｄｉ＊ＶＡＲｄｉを計算して、結果をＶＡＲ１−ｄｉ内に記憶することであり、各ステップＳＱｉがＶＡＲｄｉ＊ＶＡＲｄｉを計算して、結果をＶＡＲｄｉ内に記憶することである、請求項４に記載の暗号化機構。
【請求項６】
請求項１から５のいずれかに記載の暗号化機構を実施することを特徴とする、秘密Ｄを記憶する暗号化装置。
【請求項７】
請求項１から５のいずれかの請求項に記載の暗号化機構を実施することを特徴とする、秘密Ｄを記憶するスマートカード。
【請求項１】
ｎ桁の２進数｛ｄ０、ｄ１、．．．ｄｎ−１｝２として表され得る秘密Ｄを必要とし、ＸＤに等しい出力要素ＯＵＴを計算するように構成されている暗号化機構にして、Ｘがモノイド｛Ｍ、＊｝の要素であり、当該機構が、第１の変数ＶＡＲ０と第２の変数ＶＡＲ１とを含み、各ステップＭＵＬｉの間、暗号化装置がＶＡＲ１−ｄｉ＊ＶＡＲｄｉを計算するように、当該暗号化機構がｎ個のステップ｛ＭＵＬｉ｝ｉ＝ｎ−１．．０を含み、各ステップＳＱｉの間、暗号化装置がＶＡＲｄｉ＊ＶＡＲｄｉを計算するように、当該暗号化機構がｎ個のその他のステップ｛ＳＱｉ｝ｉ＝ｎ−１．．０を含み、各ステップＳＱｉが、０とｎ−１の間の任意のｉに関してステップＭＵＬｉの後で実行されており、各ステップＭＵＬｉ−１が、１とｎ−１の間の任意のｉに関してステップＭＵＬｉの後で実行されている、暗号化機構であって、
ａ．ランダム要素ＭＳＫ＿ＩＮＰＵＴ（Ｒ）を生成するステップと、
ｂ．要素Ｘとランダム要素ＭＳＫ＿ＩＮＰＵＴとを使用することによってマスキングされた要素ＭＡＳＫＥＤ＿Ｘ（ＶＡＲ１）を作成するステップと、
ｃ．マスキングされた要素ＭＡＳＫＥＤ＿Ｘを使用して、上述のステップ｛ＭＵＬｉ｝ｉ＝ｎ−１．．０と｛ＳＱｉ｝ｉ＝ｎ−１．．０とを必要とする、マスキングされた出力要素ＭＡＳＫＥＤ＿ＯＵＴ（ＶＡＲ０）を計算するステップと、
ｄ．秘密Ｄを必要とせずに、ランダム要素ＭＳＫ＿ＩＮＰＵＴから出力マスクＭＳＫ＿ＯＵＴＰＵＴ（ＭＳＫ０）を計算するステップと、
ｅ．マスキングされた出力要素ＭＡＳＫＥＤ＿ＯＵＴと出力マスクＭＳＫ＿ＯＵＴＰＵＴとを使用して、出力要素ＯＵＴを計算するステップと
を含むことを特徴とし、
ステップｄがステップａとステップｅの間の任意のときに発生し、ステップａ、ｂ、ｃ、ｅが連続的である、暗号化機構。
【請求項２】
ランダム要素ＭＳＫ＿ＩＮＰＵＴ（Ｒ）がモノイド｛Ｍ、＊｝の演算＊に関する逆元（Ｒ−１）を有し、逆元が出力マスクＭＳＫ＿ＯＵＴＰＵＴを計算するために使用可能である、請求項１に記載の暗号化機構。
【請求項３】
出力マスクＭＳＫ＿ＯＵＴＰＵＴの計算が、各ステップＲ＿ＳＱｉの間、暗号化装置がＭＳＫｉ＊ＭＳＫｉを計算するように、ｎ個のステップ｛Ｒ＿ＳＱｉ｝ｉ＝ｎ−１．．０を含み、ＭＳＫｉがモノイド｛Ｍ、＊｝の要素であり、初期値ＭＳＫｎがランダム要素ＭＳＫ＿ＩＮＰＵＴの逆元（Ｒ−１）から取得されており、最終値ＭＳＫ０がマスキングされた出力ＭＡＳＫＥＤ＿ＯＵＴの値からマスキングを取るために使用される出力マスクＭＳＫ＿ＯＵＴＰＵＴである、請求項１に記載の暗号化機構。
【請求項４】
ＭＳＫｉが、ｎ−１から０までに等しいｉに関して、ＭＳＫｉ＋１＊ＭＳＫｉ＋１に等しい、請求項３に記載の暗号化機構。
【請求項５】
マスキングされた要素ＭＡＳＫＥＤ＿ＸがＸ＊Ｒに等しく、出力要素ＯＵＴがＭＡＳＫＥＤ＿ＯＵＴ＊ＭＳＫ０に等しく、ＭＳＫｎがＲの逆元に等しく、第１の変数ＶＡＲ０の初期値がランダム要素の値（Ｒ）に設定されており、第２の変数ＶＡＲ１の初期値がマスキングされた要素ＭＡＳＫＥＤ＿Ｘの値に設定されており、各ステップＭＵＬｉがＶＡＲ１−ｄｉ＊ＶＡＲｄｉを計算して、結果をＶＡＲ１−ｄｉ内に記憶することであり、各ステップＳＱｉがＶＡＲｄｉ＊ＶＡＲｄｉを計算して、結果をＶＡＲｄｉ内に記憶することである、請求項４に記載の暗号化機構。
【請求項６】
請求項１から５のいずれかに記載の暗号化機構を実施することを特徴とする、秘密Ｄを記憶する暗号化装置。
【請求項７】
請求項１から５のいずれかの請求項に記載の暗号化機構を実施することを特徴とする、秘密Ｄを記憶するスマートカード。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【公表番号】特表２００９−５３７０２５（Ｐ２００９−５３７０２５Ａ）
【公表日】平成２１年１０月２２日（２００９．１０．２２）
【国際特許分類】
【出願番号】特願２００９−５０２２３７（Ｐ２００９−５０２２３７）
【出願日】平成１９年３月２３日（２００７．３．２３）
【国際出願番号】ＰＣＴ／ＩＢ２００７／０００７２８
【国際公開番号】ＷＯ２００７／１１６２６２
【国際公開日】平成１９年１０月１８日（２００７．１０．１８）
【出願人】（５０４３２６５７２）アクサルト・エス・アー (31)
【Ｆターム（参考）】
【公表日】平成２１年１０月２２日（２００９．１０．２２）
【国際特許分類】
【出願日】平成１９年３月２３日（２００７．３．２３）
【国際出願番号】ＰＣＴ／ＩＢ２００７／０００７２８
【国際公開番号】ＷＯ２００７／１１６２６２
【国際公開日】平成１９年１０月１８日（２００７．１０．１８）
【出願人】（５０４３２６５７２）アクサルト・エス・アー (31)
【Ｆターム（参考）】
[ Back to top ]