(57)【要約】【課題】楕円曲線E(Z/pZ)上でのQ＝kPの故障耐性計算を含む、楕円曲線E(Z/pZ)上での暗号演算の正しさを検査する手段。【解決手段】rを整数として、楕円曲線E^(Z/pr2Z)≡E(Z/pZ)×E(Z/r2Z)が中国剰余法によって与えられる。E^(Z/pr2Z)において点P^＝CRT(P(mod  p),R(mod  r2))が形成される（１２０）；P^はE(Z/pZ)においてPに帰着し、E1(Z/r2Z)においてRに帰着する。E^(Z/pr2Z)においてQ^＝kP^が計算される（１３０）。次いで、E1(Z/r2Z)においてQ^≡kR(mod  r2)かどうかが検証され、もしそうであればQ＝Q^  mod  pが出力される。一方、もしそうでない場合には「エラー」が返される。また、装置（２００）およびコンピュータ・プログラム・プロダクト（２４０）も提供される。【選択図】図１
2010217880.tif 000002
【特許請求の範囲】
【請求項１】
第一の楕円曲線E(Z/pZ)上での暗号演算の正しさを検査する方法であって、プロセッサにおける：
・rを整数として、前記第一の楕円曲線E(Z/pZ)およびある第二の楕円曲線E(Z/r2Z)から中国剰余法によって与えられる第三の楕円曲線E^(Z/pr2Z)≡E(Z/pZ)×E(Z/r2Z)を得るステップと；
・E^(Z/pr2Z)上で当該演算を実行して第一の結果を得るステップと；
・E1(Z/r2Z)上で当該演算を実行して第二の結果を得、ここで、E1(Z/r2Z)はE(Z/r2Z)内の点であってrを法とするとE(Z/rZ)上での恒等元に帰着するものの部分集合を表す、ステップと；
・前記第一の結果および前記第二の結果がE1(Z/r2Z)において等しいことを検証するステップと；
・E^(Z/pr2Z)における当該演算の前記第一の結果をpを法として還元したものを出力するステップとを有する、
方法。
【請求項２】
前記暗号演算が楕円曲線E(Z/pZ)上でのQ＝kPの故障耐性のある計算のための、E(Z/pZ)におけるスカラー倍であり、当該方法がさらに：
・E^(Z/pr2Z)において、P^がE(Z/pZ)においてはPに帰着しE1(Z/r2Z)においてはRに帰着するような点P^＝CRT(P(mod  p),R(mod  r2))を形成するステップであって、ここで、CRTは中国剰余法を表す、ステップと；
・Q^＝kP^をE^(Z/pr2Z)において計算するステップと；
・E1(Z/r2Z)においてQ^≡kR  (mod  r2)かどうかを検証し、そうである場合にのみQ＝Q^  mod  pを出力するステップとを有する、
請求項１記載の方法。
【請求項３】
前記整数rがランダムに選ばれる、請求項１または２記載の方法。
【請求項４】
前記整数rが所定の値をもつ、請求項１または２記載の方法。
【請求項５】
前記整数rが素数である、請求項３または４記載の方法。
【請求項６】
E1(Z/r2Z)内の前記点Rがランダムに選ばれる、請求項２記載の方法。
【請求項７】
前記楕円曲線がエドワーズ曲線またはヤコビ曲線として表現される、請求項１または２記載の方法。
【請求項８】
第一の楕円曲線E(Z/pZ)上での暗号演算の正しさを検査する装置であって：
・rを整数として、前記第一の楕円曲線E(Z/pZ)およびある第二の楕円曲線E(Z/r2Z)から中国剰余法によって与えられる第三の楕円曲線E^(Z/pr2Z)≡E(Z/pZ)×E(Z/r2Z)を得；
・E^(Z/pr2Z)上で当該演算を実行して第一の結果を得；
・E1(Z/r2Z)上で当該演算を実行して第二の結果を得、ここで、E1(Z/r2Z)はE(Z/r2Z)内の点であってrを法とするとE(Z/rZ)上での恒等元に帰着するものの部分集合を表し；
・前記第一の結果および前記第二の結果がE1(Z/r2Z)において等しいことを検証し；
・E^(Z/pr2Z)における当該演算の前記第一の結果をpを法として還元したものを出力する、
手段を有する、装置。
【請求項９】
前記暗号演算は楕円曲線E(Z/pZ)上でのQ＝kPの故障耐性のある計算のための、E(Z/pZ)におけるスカラー倍であって、当該装置がさらに、
・E^(Z/pr2Z)において、P^がE(Z/pZ)においてはPに帰着し、E1(Z/r2Z)においてはRに帰着するような点P^＝CRT(P(mod  p),R(mod  r2))を形成し、ここで、CRTは中国剰余法を表し；
・Q^＝kP^をE^(Z/pr2Z)において計算し；
・E1(Z/r2Z)においてQ^≡kR  (mod  r2)かどうかを検証し、そうである場合にのみQ＝Q^  mod  pを出力する、
手段を有する、装置。
【請求項１０】
プロセッサによって実行されたときに請求項１ないし７のうちいずれか一項記載の方法を実行する命令が記憶されているコンピュータ・プログラム・プロダクト。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、概括的には暗号に、詳細には故障利用攻撃に耐性のある楕円曲線暗号アルゴリズムに関する。
【背景技術】
【０００２】
このセクションは、下記で記載および／または特許請求される本発明のさまざまな側面に関係しうる当技術分野のさまざまな側面を読者に紹介することを意図している。この議論は、本発明のさまざまな側面のよりよい理解を助けるための背景情報を読者に提供する助けとなるものと思われる。よって、これらの陳述がこの観点で読まれるべきであり、従来技術の自認として読まれるべきでないことは理解しておくべきである。
【０００３】
故障利用攻撃（fault  attack）は、秘密復号鍵のような暗号上の秘密の一ないし複数ビットを取得する意図をもって暗号計算の際にエラーを導入する。故障利用攻撃をかける実際的な方法は、非特許文献１および非特許文献２で概観されている。
【０００４】
RSA（Rivest-Shamir-Adleman［リヴェスト‐シャミール‐アドルマン］）冪乗は、Z/NZにおける入力xおよび秘密の指数dに対して、xをd乗することからなる。ここで、Z/NZはNを法とする整数環であり、N＝pqは２つの大きな素数の積である。アディ・シャミールは、非特許文献３において故障利用攻撃に対するエレガントな対策を提供した。その対策は次のようなものである：
１．（小さな）ランダム整数rに対して、y′＝xd  mod  rNを計算する
２．z＝xd  mod  rを計算する
３．y′≡z  (mod  r)であるかどうかを検査し、
・もしそうであれば、y＝y′  mod  Nを出力し、
・もしそうでなければ、「エラー」を返す。
【０００５】
典型的には、rは64ビット整数である。シャミールの方法の正しさは、中国剰余定理（CRT:  Chinese  remainder  theorem）の応用である。計算が正しいとき、y′≡y  (mod  N)かつy′≡z  (mod  r)であることは明らかである。故障が存在するとき、y′≡z  (mod  r)となる確率は約1/rである。rが64ビット値であるとき、これは故障が検出されない確率はほぼ2-64であるということを意味する。rについてのより大きな値は、計算に対する要求がより高くなることを代償として、より高い検出確率を含意する。
【０００６】
シャミールの方法は、CRTモードで評価されるとき、すなわちy＝xd  mod  Nがxd  mod  pおよびxd  mod  qから評価されるときのRSA冪乗を保護するよう適応されることができる。シャミールの対策のさらなる一般化および拡張は非特許文献４で論じられている。
【０００７】
デーヴィッド・ヴィジラントは非特許文献５において代替的な解決策を提案した。この解決策は、次のようなものである：
１．（小さな）ランダム整数rに対して、X＝CRT(x(mod  N),1＋r(mod  r2))を形成する
２．y′＝Xd  mod  r2Nを計算する
３．y′≡1＋dr  (mod  r2)であるかどうかを検査し、
・もしそうであれば、y＝y′  mod  Nを出力し、
・もしそうでなければ、「エラー」を返す。
【０００８】
ステップ１において、CRTは中国剰余定理の適用を示す。つまり、そのようにして得られたXはX≡x(mod  N)およびX≡1＋r(mod  r2)を満たす。よって、計算に障害がないときは、y′＝xd  (mod  N)かつy′≡(1＋r)d  (mod  r2)である。
【０００９】
【数１】
2010217880.tif 000003
が二項係数を表すとして
【数２】
2010217880.tif 000004
である。この恒等式をr2を法として還元すると、計算に障害がないとき、(1＋r)d≡1＋dr  (mod  r2)、よってy′≡1＋dr  (mod  r2)となる。故障が検出されない確率は、約1/r2であることが期待される。結果として、ヴィジラントの方法におけるrについての32ビット値がシャミールの方法におけるrについての64ビット値と同じセキュリティ・レベルを提供するはずである。
【００１０】
ヴィジラントの方法はシャミールの方法に対していくつかの利点を呈する。特に、冪乗z＝xd  mod  rの代わりにずっと高速な乗算1＋dr  mod  r2とする。もっとも、シャミールの方法におけるzの評価はφ(r)の値が知られていることを条件としてxd  modφ(r)  mod  rとして高速化できることは理解されるであろう（ここで、φはオイラーのトーシェント関数）。さらに、ヴィジラントの方法はCRTモードのRSAに適用される。
【００１１】
シャミールおよびヴィジラントの対策をRSAへの適用について記述してきたが、楕円曲線暗号（ECC:  elliptic  curve  cryptography）がRSAに対する興味深い代替であることは理解されるであろう。それは、推定される同じセキュリティ・レベルに対して鍵がずっと短くなるからである。
【００１２】
ECCでは、楕円曲線E上の点Pおよび整数kが与えられたとき、基本演算は、スカラー倍kP、すなわちP＋P＋…＋P（k回）を計算することにある。ここで、＋はE上での群演算を表す。攻撃者のゴールは、故障を誘導することによってkの値（またはその一部）を復元することである。
【００１３】
シャミールの対策は楕円曲線スカラー倍に一般化されるが（非特許文献６参照）、ヴィジラントの方法は、二項定理の等価物がないため、楕円曲線スカラー倍への一般化に簡単に使えるものではない。
【先行技術文献】
【非特許文献】
【００１４】
【非特許文献１】Hagai  Bar-El、Hamid  Choukri、David  Naccache、Michael  Tunstall、Claire  Whelan著、「The  Sorcerer's  Apprentice  Guide  to  Fault  Attacks」、Proceedings  of  the  IEEE、94(2)、pp.370-382、2006年（より早期のバージョンはProc.  of  FDTC  2004にある）
【非特許文献２】Christophe  Giraud、Hugues  Thiebeauld著、「A  Survey  On  Fault  Attacks」、J.-J.  Quisquater、P.  Paradinas、Y.  Deswarte、A.A.  El  Kalam編『Smart  Card  Research  and  Advanced  Applications  VI』（CARDIS  2004）、pp.159-176、Kluwer、2004年
【非特許文献３】1997年5月13日にドイツのコンスタンツでのEUROCRYPT'97の残部セッション（rump  session）で呈示された「How  to  Check  Modular  Exponentiation」
【非特許文献４】Marc  Joye、Pascal  Paillier、Sung-Ming  Yen、「Secure  Evaluation  of  Modular  Functions」、R.J.  Hwang、C.K.  Wu編、2001  International  Workshop  on  Cryptology  and  Network  Security、pp.227-229、Taipei、Taiwan、2001年9月
【非特許文献５】David  Vigilant、「RSA  With  CRT:  A  New  Cost-Effective  Solution  to  Thwart  Fault  Attacks」、E.  Oswald、P.  Rohatgi編『Cryptographic  Hardware  and  Embedded  Systems--CHES2008、volume  5154、Lecture  Notes  in  Computer  Science』所収、pp.230-145、Springer、2008年
【非特許文献６】Johannes  Bl¨omer、Martin  Otto、Jean-Pierre  Seifert、「Sign  Change  Fault  Attacks  on  Elliptic  Curve  Cryptosystems」、L.  Breveglieri、I.  Koren、D.  Naccache、J.-P.  Seifert編『Fault  Diagnosis  and  Tolerance  in  Cryptography--FDTC  2006  volume  4236  of  Lecture  Notes  in  Computer  Science』所収、pp.36-52、Springer-Verlag、2006年
【非特許文献７】Sung-Ming  Yen、Seungjoo  Kim、Seongan  Lim、Sang-Jae  Moon、「RSA  Speedup  With  Chinese  Remainder  Theorem  Immune  Against  Hardware  Fault  Cryptanalysis」、IEEE  Transactions  on  Computers、52(4):461-472、2003年（より早期のバージョンはProc.  of  ICISC  2001にある）
【非特許文献８】Daniel  J.  Bernstein、Tanja  Lange、「Faster  Addition  and  Doubling  on  Elliptic  Curves」、K.  Kurosawa編、『Advances  in  Cryptology--ASIACRYPT  2008、volume  4833  of  Lecture  Notes  in  Computer  Science』所収、pp.29-50、Springer、2007年
【非特許文献９】Olivier  Billet、Marc  Joye、「The  Jacobi  Model  of  An  Elliptic  Curve  and  Side-Channel  Analysis」、M.  Fossorier、T.  Hoholdt、A.  Poli編『Applied  Algebra,  Algebraic  Algorithms  and  Error  Correcting  Codes  (AAECC-15),  volume  2643  of  Lecture  Notes  in  Computer  Science』、pp.34-42、Springer、2003年
【発明の概要】
【発明が解決しようとする課題】
【００１５】
したがって、ECC上での故障利用攻撃に対する代替的な解決策を提供する解決策が必要とされている。本発明はそのような解決策を提供する。
【課題を解決するための手段】
【００１６】
第一の側面では、本発明は、第一の楕円曲線E(Z/pZ)上での暗号演算の正しさを検査する方法に向けられる。プロセッサは、rを整数として前記第一の楕円曲線E(Z/pZ)およびある第二の楕円曲線E(Z/r2Z)から中国剰余法によって与えられる第三の楕円曲線E^(Z/pr2Z)≡E(Z/pZ)×E(Z/r2Z)を得；E^(Z/pr2Z)上で当該演算を実行して第一の結果を得；E1(Z/r2Z)上で当該演算を実行して第二の結果を得、ここで、E1(Z/r2Z)はE(Z/r2Z)内の点であってrを法とするとE(Z/rZ)上での恒等元に還元されるものの部分集合を表し；前記第一の結果および前記第二の結果がE1(Z/r2Z)において等しいかどうかを検証し；もしそうであれば、pを法として還元されたE^(Z/pr2Z)における当該演算の前記第一の結果を出力する。
【００１７】
ある第一の好ましい実施形態では、前記暗号演算は楕円曲線E(Z/pZ)上でのQ＝kPの故障耐性のある計算のための、E(Z/pZ)におけるスカラー倍である。E^(Z/pr2Z)において、P^がE(Z/pZ)においてはPに還元されE1(Z/r2Z)においてはRに還元されるよう点P^＝CRT(P(mod  p),R(mod  r2))が形成される。ここで、CRTは中国剰余法を表す。Q^＝kP^がE^(Z/pr2Z)において計算され、E1(Z/r2Z)においてQ^≡kR  (mod  r2)かどうかが検証され、そうである場合にのみQ＝Q^  mod  pが出力される。
【００１８】
ある第二の好ましい実施形態では、整数rはランダムに選ばれる。
【００１９】
ある第三の好ましい実施形態では、整数rは所定の値をもつ。
【００２０】
整数rが素数であることは有利である。
【００２１】
E1(Z/r2Z)内の点Rがランダムに選ばれることも有利である。
【００２２】
あるさらなる好ましい実施形態では、楕円曲線はエドワーズ曲線またはヤコビ曲線として表現される。
【００２３】
第二の側面では、本発明は、第一の楕円曲線E(Z/pZ)上での暗号演算の正しさを検査する装置に向けられる。本装置は、rを整数として前記第一の楕円曲線E(Z/pZ)およびある第二の楕円曲線E(Z/r2Z)から中国剰余法によって与えられる第三の楕円曲線E^(Z/pr2Z)≡E(Z/pZ)×E(Z/r2Z)を得；E^(Z/pr2Z)上で当該演算を実行して第一の結果を得；E1(Z/r2Z)上で当該演算を実行して第二の結果を得、ここで、E1(Z/r2Z)はE(Z/r2Z)内の点であってrを法とするとE(Z/rZ)上での恒等元に還元されるものの部分集合を表し；前記第一の結果および前記第二の結果がE1(Z/r2Z)において等しいかどうかを検証し；もしそうであれば、pを法として還元されたE^(Z/pr2Z)における当該演算の前記第一の結果を出力する、手段を有する。
【００２４】
ある第一の好ましい実施形態では、前記暗号演算は楕円曲線E(Z/pZ)上でのQ＝kPの故障耐性のある計算のための、E(Z/pZ)におけるスカラー倍である。本装置はさらに、E^(Z/pr2Z)において点P^＝CRT(P(mod  p),R(mod  r2))を、P^がE(Z/pZ)においてはPに還元され、E1(Z/r2Z)においてはRに還元されるように形成し、ここで、CRTは中国剰余法を表し；Q^＝kP^をE^(Z/pr2Z)において計算し；E1(Z/r2Z)においてQ^≡kR  (mod  r2)かどうかを検証し；そうである場合にのみQ＝Q^  mod  pを出力する手段を有する。
【００２５】
第三の側面では、本発明は、プロセッサによって実行されたときに前記第一の側面の実施形態のいずれかに基づく方法を実行する命令が記憶されているコンピュータ・プログラム・プロダクトに向けられる。
【００２６】
本発明の好ましい特徴についてこれから、非限定的な例として、付属の図面を参照しつつ述べる。
【図面の簡単な説明】
【００２７】
【図１】本発明のある好ましい実施形態に基づく故障耐性のある方法を示すフローチャートである。
【図２】本発明のある好ましい実施形態に基づく故障耐性のある楕円曲線暗号計算を実行するための装置を示す図である。
【発明を実施するための形態】
【００２８】
［外１］
2010217880.tif 000005
を環とし、
［外２］
2010217880.tif 000006
をR上で定義された楕円曲線
［外３］
2010217880.tif 000007
上での有理点の集合を表すものとする。r2を法として整数の環Z/r2Z上で定義された楕円曲線を考えると、
［外４］
2010217880.tif 000008
をE(Z/rZ)上での恒等元を表すとして、部分集合が
【数３】
2010217880.tif 000009
として定義される。
【００２９】
図１は、本発明のある好ましい実施形態に基づく故障耐性のある方法を例示するフローチャートである。楕円曲線E(Z/pZ)上でのQ＝kPの故障耐性計算は、次の方法を使って実行されうる：
１．rを（小さな）整数として、中国剰余法によって与えられる楕円曲線E^(Z/pr2Z)≡E(Z/pZ)×E(Z/r2Z)を考える（１１０）。
２．E^(Z/pr2Z)における点P^＝CRT(P(mod  p),R(mod  r2))を形成する（１２０）。つまり、
ａ．P^はE(Z/pZ)においてPに帰着し、
ｂ．P^はE1(Z/r2Z)においてRに帰着する、
ような点P^である。
３．E^(Z/pr2Z)においてQ^＝kP^を計算する（１３０）。
４．E1(Z/r2Z)においてQ^≡kR(mod  r2)かどうかを検査し（１４０）、
・もしそうであれば、Q＝Q^  mod  pを出力し、
・もしそうでなければ、「エラー」を返す。
【００３０】
検査するステップ（すなわち上記のステップ４）においてkRがE1(Z/r2Z)において計算できることは注目に値する。これはE(Z/r2Z)において計算するよりずっと高速である。楕円曲線の表現に依存して、これは典型的にはr2を法とした１回の乗算になる。E1(Z/r2Z)においてはkR＝(k  mod  r)Rであることは理解されるであろう。
【００３１】
上記の方法には数多くの変形がある。たとえば、整数rはランダムに選ばれてもよいし、あるいは所定の値に固定されてもよい。この整数は素数として選ばれてもよい。E1(Z/r2Z)における点Rについても同じことが言える。すなわち、ランダムに選ばれることも所定の値に固定されることもできる。
【００３２】
さらに、検査するステップ４はいくつかの仕方で実行されうる。具体的には、いわゆる伝染計算（infective  computation）を使って明示的な分岐命令を回避するよう実装できる。伝染計算は非特許文献７および非特許文献６に記載されている。
【００３３】
さらに、楕円曲線は種々の仕方で表現されうる。特に興味深いのは、いわゆる完全モデル（complete  models）である。その場合、恒等元が特別な扱いを必要としないからである。そのような曲線の例はエドワーズ曲線（非特許文献８に記載されている）およびヤコビ曲線（非特許文献９に記載されている）である。
【００３４】
図２は、本発明のある好ましい実施形態に基づく装置を示している。装置２００は、他の装置（図示せず）との通信のために適応された少なくとも一つのインターフェース・ユニット２１０と、少なくとも一つのプロセッサ２２と、アキュムレータおよび中間計算結果のようなデータを記憶するよう適応されている少なくとも一つのメモリ２３０を有する。プロセッサ２２０は、本稿で先述したように本発明の方法の実施形態の任意のものに従って冪乗を計算するよう適応されている。CD-ROMまたはDVDのようなコンピュータ・プログラム・プロダクト２４０は、プロセッサ２２０によって実行されたときに本発明の実施形態の任意のものに従う方法を実行する記憶された命令を有する。
【００３５】
本記載ならびに（該当する場合には）請求項および図面において開示された各特徴は、独立して、あるいは任意の適切な組み合わせにおいて提供されうる。ハードウェアにおいて実装されると述べられている特徴がソフトウェアにおいて実装されてもよく、逆ソフトウェアにおいて実装されると述べられている特徴がハードウェアにおいて実装されてもよい。請求項に現れる参照符号は単に例示としてであり、特許請求の範囲に対していかなる限定する効果ももたないものとする。
【符号の説明】
【００３６】
１１０  CRTを使って楕円曲線E^(Z/pr2Z)≡E(Z/pZ)×E(Z/r2Z)を生成
１２０  P^がE(Z/pZ)においてPに帰着し、E1(Z/r2Z)においてRに帰着するよう、E^(Z/pr2Z)における点P^＝CRT(P(mod  p),R(mod  r2))を形成
１３０  E^(Z/pr2Z)においてQ^＝kP^を計算
１４０  E1(Z/r2Z)においてQ^≡kR(mod  r2)かどうかを検査し、もしそうであればQ＝Q^  mod  pを出力
２００  装置
２１０  インターフェース・ユニット
２２０  プロセッサ
２３０  メモリ
２４０  コンピュータ・プログラム・プロダクト
【図１】
2010217880.tif 000010
【図２】
2010217880.tif 000011
【外国語明細書】
2010217880000001.pdf