(57)【要約】【課題】全ての欠陥を検出する、ＲＳＡにおける欠陥攻撃に対する対抗手段を提供する。【解決手段】ＲＳＡキーのパブリック指数ｅは、この指数を欠くＲＳＡキー・オブジェクトに埋め込まれる。指数計算の間、パブリック指数ｅは取り出されて、累乗の結果が正しいことを確認するために使用されてよい。結果は、それが正しい場合にのみ出力される。本発明は、欠陥攻撃に対抗する。また、装置（１００）及びコンピュータプログラムプロダクト（１４０）も提供される。【選択図】図１
2010193447.tif 000002
【特許請求の範囲】
【請求項１】
累乗を計算する方法であって、欠陥攻撃に対して耐性を備え、装置において、
マッチング・パブリック指数に関連するＲＳＡプライベートキー・オブジェクトを得るステップと、
前記ＲＳＡプライベートキー・オブジェクトを用いて累乗の結果を得るステップと、
前記マッチング・パブリック指数を用いて、前記累乗の結果が正しいことを確認するステップと
を有する方法において、
標準モードで、
前記ＲＳＡプライベートキー・オブジェクトはＲＳＡ法Ｎを有し、前記マッチング・パブリック指数ｅは前記ＲＳＡ法Ｎから得られ、
ＣＲＴモードで、
前記ＲＳＡプライベートキー・オブジェクトは前記ＲＳＡ法Ｎの因数を有し、前記マッチング・パブリック指数ｅは前記ＲＳＡ法Ｎの前記因数のうち少なくとも１つから得られる
ことを特徴とする方法。
【請求項２】
前記マッチング・パブリック指数ｅは、前記ＲＳＡ法Ｎの２進数表現の先頭ビットに含まれる、請求項１記載の方法。
【請求項３】
ＣＲＴモードで、前記ＲＳＡ法Ｎは、その因数の乗算によって得られる、請求項２記載の方法。
【請求項４】
累乗を計算する装置であって、欠陥攻撃に対して耐性を備え、
マッチング・パブリック指数に関連するＲＳＡプライベートキー・オブジェクトを得る手段と、
前記ＲＳＡプライベートキー・オブジェクトを用いて累乗の結果を得る手段と、
前記マッチング・パブリック指数を用いて、前記累乗の結果が正しいことを確認する手段と
を有する装置において、
標準モードでは、前記ＲＳＡプライベートキー・オブジェクトに含まれるＲＳＡ法Ｎから、ＣＲＴモードでは、前記ＲＳＡプライベートキー・オブジェクトに含まれる前記ＲＳＡ法Ｎの因数のうち少なくとも１つから、前記マッチング・パブリック指数ｅを得る手段を有することを特徴とする装置。
【請求項５】
前記ＲＳＡプライベートキー・オブジェクトを得る手段、前記ＲＳＡプライベートキー・オブジェクトを用いて累乗の結果を得る手段、前記マッチング・パブリック指数を用いて、前記累乗の結果が正しいことを確認する手段、及び前記マッチング・パブリック指数ｅを得る手段は、少なくとも１つのプロセッサに実装される、請求項４記載の装置。
【請求項６】
プロセッサに、請求項１乃至３のうちいずれか一項記載の方法を実行する命令を実行させるコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、概して、暗号化に関し、具体的に、ＲＳＡのための欠陥攻撃（fault  attack）対抗手段に関する。
【背景技術】
【０００２】
本項目は、以下本明細書中に記載され、あるいは、特許請求の範囲で請求される本発明の様々な態様に関連する当該技術の様々な側面を紹介することを目的とする。ここでの記載は、本発明の様々な態様のより良い理解を助けるべく、背景情報を読み手に与えるのに役立つと信じられる。然るに、当然ながら、かかる記載は、先行技術の承認としてではなく、この観点から読まれるべきである。
【０００３】
欠陥攻撃（fault  attack）は、誤った出力から極秘データを推論するために、セキュリティ機器の期待される動作を妨げ、機器に異常動作をさせる。このような攻撃は、「On  the  Importance  of  Checking  Cryptographic  Protocols  for  Faults」、D.Boneh、R.A.DeMillo、及びR.J.Lipton著、W.Fumy編，Advances  in  Cryptology  −  EUROCRYPT  ’97、Computer  Science講義ノート第１２３３巻、３７〜５１頁、シュプリンガー・フェルラーグ版で紹介されている。
【０００４】
欠陥攻撃は、非常に強力でありうる。例えば、単一のランダムな欠陥を伴い且つ中国剰余定理（ＣＲＴ（Chinese  remaindering））を用いて求められる、欠陥のあるＲＳＡ署名は、攻撃者がその欠陥のある署名から全ての秘密キーを回復すること、を可能にすることがある。従って、対抗手段が取られるべきことは明らかである。
【０００５】
ＲＳＡは、大きな素数の積を因数分解することは困難である、という事実に基づく。Ｎ＝ｐｑは、２つの大きな素数の積であるとする。ｅ及びｄは、マッチング・パブリック指数及びマッチング・プライベート指数の対を表し、ｅｄ≡１（ｍｏｄλ（Ｎ））を満たし、更に、ｇｃｄ（ｅ，λ（Ｎ））＝１であり且つλはカーマイケル関数（オイラー関数）であるとする。Ｎ＝ｐｑである場合に、λ（Ｎ）＝ｌｃｍ（ｐ−１，ｑ−１）が成立する。ｘ＜Ｎを仮定すると、パブリック演算（例えば、メッセージ暗号化又は署名照合）は、Ｎを法とするｘのｅ乗を計算すること、すなわち、ｙ＝ｘｅｍｏｄＮを計算することにある。次いで、ｙを仮定すると、対応するプライベート演算（例えば、暗号文の解読又は署名生成）は、Ｎを法とするｙｄを計算することにある。ｅ及びｄの定義から、ｙｄ≡ｘ（ｍｏｄＮ）が得られる。プライベート演算は、中国剰余定理（ＣＲＴ（Chinese  remaindering））により、もっと高速に行われ得る。計算は、ｐ及びｑを法として独立して行われて、再結合される。この場合に、プライベート・パラメータは、ｄｐ＝ｄｍｏｄ（ｐ−１）、ｄｑ＝ｄｍｏｄ（ｑ−１）、及びｉｑ＝ｑ−１ｍｏｄｐを有して｛ｐ，ｑ，ｄｐ，ｄｑ，ｉｑ｝である。次いで、ＣＲＴ（ｘｐ，ｘｑ）＝Ｘｑ＋ｑ［ｉｑ（ｘｐ−ｘｑ）ｍｏｄｐ］としてｙｄｍｏｄＮが得られる。この場合に、ｘｐ＝ｙｄｐｍｏｄｐ且つｘｑ＝ｙｄｑｍｏｄｑである。
【０００６】
当然、幾つかのこのような対抗手段が提案されている。シャミア（Shamir）による最初の対抗手段は、EUROCRYPT  ‘97のRump  Sessionで最初にプレゼンテーションが行われたＵＳ５９９１４１５に開示されている。幾分簡単にされて、この方法は、ランダム値ｊを導入し、（ｍｏｄｐ）の代わりに（ｍｏｄｊ＊ｐ）を用いて計算を行い、期待される値が達せされることを確認する。すなわち、所与の例として、ｊが３２ビット長である場合に、欠陥後の２値マッチングの機会は２−３２＝１／４，２９４，９６７，２９６であるから、リスクはほんの僅かである。より具体的に、ｘ’ｐ＝ｙｄｍｏｄｊ＊ｐ及びｘｊ＝ｙｄｍｏｄｊの値は、最初に計算される。ｘ’ｐ≡ｘｊ（ｍｏｄｊ）であることが確認され、それが成立する場合は、計算はエラーのないものと考えられる。次いで、ｐを法とする累乗の結果は、ｘｐ＝ｘ’ｐｍｏｄｐによって与えられる。これは、ｑを法としても同じように行われる。対抗手段の正確さは、あらゆる正の整数ｊについてｘｍｏｄｐ＝（ｘｍｏｄｊ＊ｐ）ｍｏｄｐという観察に依存する。
【０００７】
Kaliski及びRobshawによってftp://ftp.rsasecurity.com/pub/pdfs/bulletn5.pdfに記述されている他の方法は、ｘ＝ｙｄｍｏｄＮを得るよう通常の方法で指数計算を行うが、ｘを与える前に、それが正しいことを、ｘｅがＮを法とするｙと等しいことを確かめることによって、確かめることにある。
【０００８】
全てのその後の方法は、基本的に、シャミアによって提案されている方法に依存する。これらの方法には：
−  M.Joye、P.Paillier、及びS-M.Yen著、Secure  Evaluation  of  Modular  Functions、R.J.  Hwang及びC.K.Wu編、2001  International  Workshop  of  Cryptology  and  Network  Security、２２７〜２２９頁、台湾国台北、２００１年
−  C.Aumuler、P.Bier、W.Fischer、P.Hofreiter、及びJ-P.Seifert著、Fault  Attack  on  RSA  with  CRT：Concrete  Results  and  Practical  Countermeasures、B.S.Kaliski  Jr.、C.K.Koc  及びC.Paar編、Cryptographic  Hardware  and  Embedded  Systems−CHES2002、Computer  Science講義ノート第２５２３巻、２６０〜２７５頁、シュプリンガー版、２００２年
−  J.Blomer、M.Otto、及びJ-P.Seifert著、A  New  CRT-RSA  Algorithm  Secure  Against  Bellcore  Attack、10th  ACM  Conference  on  Computer  and  Communication  Security（CCS2003）、３１１〜３２０頁、AMC  Press、２００３年
−  M.Ciet及びM.Joye著、Practical  Fault  Countermeasures  for  Chinese  Remaindering  Based  RSA、2nd  Workshop  Fault  Diagnosis  and  Tolerance  in  Cryptography（FDTC2005）、１２４〜１３２頁、２００５年
−  C.H.Kim及びJ.-J.Quisquater著、How  Can  We  Overcome  Both  Side  Channel  Analysis  and  Fault  Attacks  on  RSA-CRT?、4th  Workshop  on  Fault  Diagnosis  and  Tolerance  in  Cryptography（FDTC2007）、２１〜２９頁、IEEE  Computer  Society  Press、２００７年
が含まれる。
【０００９】
当然、Blomer等及びCiet等の方法は完全な不正使用防止を提供しないことが示されている。更に、これらの方法のいずれも、１００％の欠陥検出を保証せず、それらは全て、性能（実行時間及びメモリ要求）、更には、場合によりパーソナライズ処理に影響を及ぼす。
【先行技術文献】
【特許文献】
【００１０】
【特許文献１】米国特許出願公開第２００８／１４４８１４（Ａ１）号明細書
【特許文献２】米国特許出願公開第２００５／０８４０９６（Ａ１）号明細書
【非特許文献】
【００１１】
【非特許文献１】Yen  S-N等著、「HARDWARE  FAULT  ATTACK  ON  RSA  WITH  CRT  REVISITED」、COMPUTER  SCIENCE講義ノート、シュプリンガー・フェルラーグ版、独国ベルリン、第２５８７巻、２００２年１１月２８日、３７４〜３８８頁
【発明の概要】
【発明が解決しようとする課題】
【００１２】
従って、当然のことながら、全ての欠陥を検出する、ＲＳＡにおける欠陥攻撃に対する対抗手段が必要とされる。本発明は、かかる解決法を提供する。
【課題を解決するための手段】
【００１３】
第１の態様で、本発明は、累乗を計算する方法を対象とする。方法は、欠陥攻撃に対して耐性を備えている。マッチング・パブリック指数と関連付けられるＲＳＡプライベートキー・オブジェクトが得られる。そのＲＳＡプライベートキー・オブジェクトを用いて、累乗の結果が得られる。マッチング・パブリック指数を用いて、累乗の結果が正しいことが確認される。標準モードで、ＲＳＡプライベートキー・オブジェクトはＲＳＡ法Ｎを有し、マッチング・パブリック指数ｅはこのＲＳＡ法Ｎから得られる。ＣＲＴモードで、ＲＳＡプライベートキー・オブジェクトはＲＳＡ法Ｎの因数を有し、マッチング・パブリック指数ｅは、ＲＳＡ法Ｎの因数のうち少なくとも１つの因数から得られる。
【００１４】
第１の好ましい実施形態で、マッチング・パブリック指数ｅは、ＲＳＡ法Ｎの２進数表現の先頭ビットに含まれる。
【００１５】
第２の好ましい実施形態で、ＣＲＴモードで、マッチング・パブリック指数ｅは、ＲＳＡ法Ｎの２進数表現の先頭ビットに含まれ、ＲＳＡ法Ｎはその因数の乗算によって得られる。
【００１６】
第２の態様で、本発明は、累乗を計算する装置であって、欠陥攻撃に対して耐性を備えるものを対象とする。装置は、マッチング・パブリック指数に関連するＲＳＡプライベートキー・オブジェクトを得る手段と、そのＲＳＡプライベートキー・オブジェクトを用いて累乗の結果を得る手段と、マッチング・パブリック指数を用いて、累乗の結果が正しいことを確認する手段とを有する。装置は、更に、標準モードでは、ＲＳＡプライベートキー・オブジェクトに含まれるＲＳＡ法Ｎから、ＣＲＴモードでは、ＲＳＡプライベートキー・オブジェクトに含まれるＲＳＡ法Ｎの因数のうち少なくとも１つの因数から、マッチング・パブリック指数ｅを得る手段を有する。
【００１７】
第１の好ましい実施形態で、ＲＳＡプライベートキー・オブジェクトを得る手段、ＲＳＡプライベートキー・オブジェクトを用いて累乗の結果を得る手段、マッチング・パブリック指数を用いて、累乗の結果が正しいことを確認する手段、及びマッチング・パブリック指数ｅを得る手段は、少なくとも１つのプロセッサに実装される。
【００１８】
第３の態様で、本発明は、プロセッサに第１の態様に係る方法を実行する命令を実行させるコンピュータプログラムを対象とする。
【発明の効果】
【００１９】
本発明の実施形態によれば、全ての欠陥を検出する、ＲＳＡにおける欠陥攻撃に対する対抗手段を提供することが可能となる。
【図面の簡単な説明】
【００２０】
【図１】本発明の好ましい実施形態に従う装置を表す。
【発明を実施するための形態】
【００２１】
以下、本発明の好ましい特徴は、添付の図面を参照して、限定されない例によって、記載される。
【００２２】
ＲＳＡでは「キー」と「キー・オブジェクト」との間には相違がある。キーは、例えば、パブリック・キー（Ｎ，ｅ）又はプライベート・キー（Ｎ，ｄ）（夫々、ＣＲＴモードで（ｐ，ｑ，ｄｐ，ｄｑ，ｉｑ））等の、暗号計算に用いられ得るエンティティである。一方、キー・オブジェクトは、キーを表すものであると考えられている。
【００２３】
例えば、Ｊａｖａ（登録商標）Ｃａｒｄによって提供されるような、既存のアプリケーション・プログラミング・インターフェース（ＡＰＩ）では、ＲＳＡプライベートキー・オブジェクトは、ＣＲＴモードでは｛ｐ，ｑ，ｄｐ，ｄｑ，ｉｑ｝から、標準モードでは｛Ｎ，ｄ｝から初期化される。
【００２４】
注目すべきは、対応するパブリック指数（public  exponent）ｅは利用可能でない点である。このため、前述の多数の提案されている対抗手段は、計算ｙ：＝ｘｄｍｏｄＮにエラーがないかどうかを確かめる。しかし、ｅの値が利用可能であったならば、標準モードではｙｅ≡ｘ（ｍｏｄＮ）であるかどうかを、あるいは、ＣＲＴモードではｙｅ≡ｘ（ｍｏｄ｛ｐ，ｄ｝）であるかどうかを確認することによって、ｙの正確さを確かめることは容易である。これは特に、ｅの値がほぼ常に小さく選択される場合に当てはまる（一般的に、３又は２１６＋１）。
【００２５】
これを可能にするために、好ましい実施形態で、ｅの値は、その値をＲＳＡプライベートキー・オブジェクトに埋め込むことによって、利用可能にされる。
【００２６】
先行技術の解決法に反して、これは全てのエラーの検出を可能にすることができる。
【００２７】
このように、主な発明概念は、パブリックＲＳＡ指数ｅを表すものをＲＳＡキーに埋め込むことである。「表すもの」とは、値を一義的に表す手段を意味する。例えば、一般的に用いられているパブリックＲＳＡ指数は３及び２１６＋１である。これらの値を表すものの例は、それらの２進値、それらの値が後に続くバイト長、又は、前もって同意されているならば、実際には、３については“１”及び２１６＋１については“２”である。
【００２８】
記載されるように、このようなキー・オブジェクトは、ＣＲＴモードでは｛ｐ，ｑ，ｄｐ，ｄｑ，ｉｑ｝から、標準モードでは｛Ｎ，ｄ｝から得られる。ｙ＝ｘｄｍｏｄＮを計算しているときに、パブリック指数ｅはＲＳＡキーを表すものに埋め込まれているかどうかが確かめられる。パブリック指数ｅが埋め込まれている場合は、パブリック指数ｅは回復される。次いで、標準モードではｙｅ≡ｘ（ｍｏｄＮ）であるかどうか、あるいは、ＣＲＴモードではｙｅ≡ｘ（ｍｏｄ｛ｐ，ｄ｝）であるかどうかが確認される。確認結果が真である場合にのみ、ｙは返される。
【００２９】
当業者には明らかなように、ＲＳＡ法（modulus）はランダムなビット列として現れる。従って、アプリケーションが、通例のＲＳＡ法、すなわち、パブリック指数ｅを埋め込まれていない法と、本発明に従う法とを区別することを可能にすることが望ましい。これを行うよう、例えば６４ビットのインジケータＳ（例えば、“５Ａ５Ａ５Ａ５Ａ５Ａ５Ａ５Ａ５Ａ”）をパブリック指数ｅの前（又は実際には後）に挿入することが望ましい。インジケータＳは、望ましくは、Ｌ｜Ｖ（長さ−値）フォーマットで挿入される。Ｌは、パブリック指数ｅの値Ｖの（例えば、ワード又はビットにおける）長さを表す。
【００３０】
パブリック指数ｅ及び長さＩを考えると、ＩビットのＲＳＡ法Ｎ＝ｐｄは、Ｓ、Ｌ及びＶを含む所定部分により生成されてよい。かかる法は、例えば、M.Joye著、RSA  Moduli  With  a  Predetermined  Portion：Techniques  and  Applications、Information  Security  Practice  and  Experience（ISPEC2008）、Computer  Science講義ノート第４９９１巻、１１６〜１３０頁、シュプリンガー版、２００８年や、A.Lenstra著、Generating  RSA  Moduli  With  a  Predetermined  Portion、Advances  in  Cryptology−ASIACRYPT  ‘98、Computer  Science講義ノート第１５１４巻、１〜１０頁、シュプリンガー版、１９９８年に記載されるもの等、何らかの適切な方法によって生成されてよい。
【００３１】
かかる法Ｎから、パブリック指数ｅの値を回復することは容易である。相応して、ＣＲＴモードでは、パブリック指数ｅの値は積ｐｄから回復される。ｐ及びｑはＮのプライベート因数（private  factors）を表す。
【００３２】
言い換えると、累乗を計算するために、ＲＳＡプライベートキー・オブジェクトは、例えば、１又はそれ以上の記憶されているデータフィールドからプライベートキー・オブジェクトを取り出すことによって、１又はそれ以上の記憶されているデータフィールドにある値から計算によって、あるいは、それらの組合せによって、得られる。ＲＳＡプライベートキー・オブジェクトはマッチング・パブリック指数ｅと関連付けられる。これより、例えば、累乗及び署名の確認のために使用され得る、対応するパブリック指数が存在すると言える。累乗の結果（例えば、ｙ：＝ｘｄｍｏｄＮ）は、ＲＳＡプライベートキー・オブジェクトを用いて、例えば、計算によって、又は更なる装置からそれを受け取ることによって、得られる。次いで、マッチング・パブリック指数ｅを用いて、累乗の結果が正しいことが、例えば、ｙｅ≡ｘ（ｍｏｄＮ）であることを確かめることによって、確認される。実施に依存して、マッチング・パブリック指数ｅは様々な方法で得られる。標準モードでは、それはＲＳＡ法Ｎから得られ、ＣＲＴモードでは、それはＲＳＡ法Ｎの因数のうち少なくとも１つの因数から得られる。「得られる」とは、更なるエンティティに埋め込まれているパブリック指数ｅを取り出すことを意味する。例えば、標準モードで、パブリック指数ｅは、Ｎの２進数表現で２進数の連続を形成されてよい。また、ＣＲＴモードで、パブリック指数ｅは、ｐ若しくはｑの２進数表現で、又はｐ及びｑの積で、２進数の連続を形成されてよい。後者の場合に、積は、ｅが取り出され得る前に計算されるべきである。
【００３３】
図１は、本発明の好ましい実施形態に従う装置を表す。装置１００は、他の装置（図示せず。）と通信を行うよう構成される少なくとも１つのインターフェースユニット（Ｉ／Ｏ）１１０と、少なくとも１つのプロセッサ（ＣＰＵ）１２０と、データ（例えば、中間計算結果）を記憶するよう構成される少なくとも１つのメモリ１３０とを有する。プロセッサ１２０は、上述されたように、埋め込まれているパブリック指数ｅをＲＳＡプライベートキー・オブジェクトから取り出し、累乗を計算し、パブリック指数ｅを用いて結果を確認するよう構成される。例えばＣＤ−ＲＯＭ又はＤＶＤ等の、コンピュータプログラムプロダクト１４０は、本発明の実施形態のいずれかに従う方法を実行する命令をプロセッサ１２０に実行させるコンピュータプログラムを記憶している。
【００３４】
当然のことながら、本発明は、全ての欠陥又はエラーの検出を可能にする。また、当然のことながら、本発明は既存の実施と十分に互換性があるので、ＡＰＩを変更する必要はない。最後に、更なる利点は、本発明の方法が極めて有効である点である。すなわち、通常、それは、２、３の更なるモジュール増加しか必要としないので、典型的な２０４８ビット・アプリケーションのための確認ステップは、全体の計算のうち約０．０９％から０．５％にしか当たらない。
【００３５】
本明細書並びに（必要に応じて）特許請求の範囲及び図面に開示されている夫々の特徴は、独立して、又は何らかの適切な組合せで、提供されてよい。
【００３６】
ハードウェアで実施されるよう記載される特徴は、また、ソフトウェアで実施されてもよく、逆もまた同様である。接続は、適用可能な場合に、無線接続又は有線（必ずしも直接ではない。）若しくは専用の接続として実施されてよい。
【００３７】
特許請求の範囲中に現れる参照符号は、単なる実例としてであり、特許請求の範囲の適用範囲に対する限定効果を有さない。
【符号の説明】
【００３８】
１００  装置
１１０  インターフェース
１２０  プロセッサ
１３０  メモリ
１４０  コンピュータプログラムプロダクト
ｅ  パブリック指数
Ｎ  法
【図１】
2010193447.tif 000003
【外国語明細書】
2010193447000001.pdf