(57)【要約】      （修正有）【課題】入力xおよび秘密の指数dを使って故障耐性のある冪乗を実行する方法を提供する。【解決手段】事前に選択された整数rおよび選ばれたランダムな要素a∈{0,…,r−1}を使って、拡張されたベース＾x≡x(mod  N)、＾x≡1＋a・r(mod  r2)が形成される。一般化では、法Nと互いに素な、事前に選択された整数t＝br2（bは整数）について、プロセッサは、法のもとでの逆元iN＝N-1mod  tを有している。プロセッサは、＾x＝x＋N・[iN(1＋ar−x)mod  t]を計算することによって拡張されたベースを生成しS2、次いで、拡張された法＾N＝Ntを計算しS3、Sr＝＾xdmod＾Nを計算しS4、Sr≡1＋dar(mod  r2)であるかどうかを検証しS5、そうである場合にかつその場合にのみ、結果S=Srmod  Nをインターフェースを介して返すＳ６。【選択図】図２
2014174556.tif 000002
【特許請求の範囲】
【請求項１】
入力x、秘密の指数dおよび法Nを使って法のもとでの冪乗を実行して結果Sを得る方法であって、前記冪乗は故障利用攻撃に対して耐性があり、当該方法は、装置の、あらかじめ決定された値rを有するプロセッサにおける少なくとも下記の段階、すなわち：
・入力xを受領する段階と；
・前記秘密の指数d、拡張されたベース＾xおよび拡張された法＾Nに関わる、法のもとでの冪乗を使って、中間的な結果Srを計算する段階であって、前記拡張されたベース＾xは前記入力xおよびランダムな値aを使って計算され、前記拡張された法＾Nは前記法Nおよび前記あらかじめ決定された値rを使って計算され、前記ランダムな値aとは独立である、段階と；
・Srが前記あらかじめ決定された値rの倍数を法として計算された前記ランダムな値aを含む式を満たすことを検証する段階と；
・前記検証が成功である場合にかつその場合にのみS＝Sr  mod  Nを返す段階とを含む、
方法。
【請求項２】
前記ランダムな要素aを選ぶ段階をさらに含む、請求項１記載の方法。
【請求項３】
前記ランダムな値がa∈Z/rZを満たす、請求項１記載の方法。
【請求項４】
拡張されたベース
【数９】
2014174556.tif 000011
を計算する段階をさらに含んでおり、iN＝N-1  mod  tは法のもとでの逆元であり、tは前記法Nとは互いに素であり、t＝br2であり、rおよびbは整数である、請求項１記載の方法。
【請求項５】
前記拡張された法＾N＝Ntを計算する段階をさらに含む、請求項４記載の方法。
【請求項６】
前記中間的な値Srが
【数１０】
2014174556.tif 000012
として計算される、請求項１記載の方法。
【請求項７】
前記中間的な値Srが満たすべき前記式はSr≡1＋dar  (mod  r2)である、請求項１記載の方法。
【請求項８】
入力x、秘密の指数dおよび法Nを使った冪乗を実行して結果Sを得る装置であって、前記冪乗は故障利用攻撃に対して耐性があり、当該装置は：
・前記入力xを受領して前記結果Sを出力するよう構成されたインターフェースと；
・プロセッサとを有しており、前記プロセッサは：
・前記秘密の指数d、拡張されたベース＾xおよび拡張された法＾Nに関わる、法のもとでの冪乗を使って中間的な結果Srを計算する段階であって、前記拡張されたベース＾xは前記入力xおよびランダムな値aを使って計算され、前記拡張された法＾Nは前記法Nおよびあらかじめ決定された値rを使って計算され、前記ランダムな値aとは独立であり、前記プロセッサは、複数の冪乗について前記あらかじめ決定された値rを使うよう構成されている、段階を行ない；
・Srが前記あらかじめ決定された値rの倍数を法として計算された前記ランダムな値aを含む式を満たすことを検証し；
・前記検証が成功である場合にかつその場合にのみ結果S＝Sr  mod  Nを前記インターフェースに送るよう構成されている、
装置。
【請求項９】
前記プロセッサがさらに、前記ランダムな要素aを選ぶよう構成されている、請求項８記載の装置。
【請求項１０】
前記ランダムな値がa∈Z/rZを満たす、請求項８記載の装置。
【請求項１１】
前記プロセッサがさらに、拡張されたベース
【数１１】
2014174556.tif 000013
を計算するよう構成されており、iN＝N-1  mod  tは法のもとでの逆元であり、tは前記法Nとは互いに素であり、t＝br2であり、rおよびbは整数である、
請求項８記載の装置。
【請求項１２】
前記プロセッサがさらに、前記拡張された法＾N＝Ntを計算するよう構成されている、請求項１１記載の装置。
【請求項１３】
前記プロセッサが、前記中間的な値Srを
【数１２】
2014174556.tif 000014
として計算するよう構成されている、請求項８記載の装置。
【請求項１４】
前記中間的な値Srが満たすべき前記式はSr≡1＋dar  (mod  r2)である、請求項８記載の装置。
【請求項１５】
プロセッサによって実行されたときに請求項１ないし７のうちいずれか一項記載の方法を実行する命令を記憶している非一時的なコンピュータ媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は概括的には暗号に、より詳細にはRSAベースまたは離散対数ベースの暗号における故障利用攻撃に対する対策に関する。
【背景技術】
【０００２】
本節は、下記で記述および／または特許請求される本発明の様々な側面に関係しうる技術のさまざまな側面を読者に紹介することを意図したものである。この議論は読者に、本発明のさまざまな側面についてのよりよい理解を容易にするための背景情報を与える助けとなるものと思われる。よって、これらの陳述は従来技術の自認としてではなくそのような観点で読まれるべきであることは理解しておくべきである。
【０００３】
本願を通じて、RSA暗号システムが例示的な限定しない例として使われるが、課題およびその解決策は、たとえばディフィー・ヘルマン鍵交換およびエルガマル暗号化方式のような離散対数に基づく暗号システムにも容易に拡張できることは理解されるであろう。
【０００４】
RSA暗号システムは、特に中国剰余定理を使って実装されるときは、故障利用攻撃に敏感であることがよく知られている。これは単純なRSAについても成り立つが、証明可能安全性をもつパディングを使った諸バージョンについても成り立つ。
【０００５】
故障利用攻撃を排除する効率的な方法がヴィジラントによって提案された（非特許文献１参照）。
【０００６】
ヴィジラントの方法は、次のように機能する。入力xおよびdに対して、S＝xd  mod  N（あるいはCRTモードではxd  mod{p,q}）を計算する必要がある。ここで、法Nは二つの選ばれた素数pとqの積である。
１．Nと互いに素なランダムな整数rを選ぶ；
２．β＝N(N-1  mod  r2)およびα＝1−β  mod  Nr2を計算する；
３．
【数１】
2014174556.tif 000003
を計算する；
４．
【数２】
2014174556.tif 000004
を計算する；
５．Sr≡1＋dr  (mod  r2)であれば、S＝Sr  mod  Nを返す；そうでなければエラー・メッセージを返す。
【０００７】
ヴィジラントの対策はある程度はよく機能するが、欠点もある。法のもとでの逆元計算に関わり（ステップ２）、法をランダムな仕方で拡張する（これは不可避）。法の逆元および法の拡張が乱数に依存するので、ある冪乗と次の冪乗で異なる。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】米国特許第5,166,978号
【非特許文献】
【０００９】
【非特許文献１】Vigilant,  RSA  with  CRT:  A  new  cost-effective  solution  to  thwart  fault  attacks,  Oswald  and  P.  Rohatgi  (ed.),  Cryptographic  Hardware  and  Embedded  Systems  -  CHES  2008,  vol.5154  of  Lecture  Notes  in  Computer  Science,  pp.130-145,  Springer,  2008
【非特許文献２】M.  Joye,  "On  Quisquater's  multiplication  algorithm",  D.  Naccache  (ed.),  Cryptography  and  Security:  From  Theory  to  Applications,  vol.6805  of  Lecture  Notes  in  Computer  Science,  pp.3-7,  Springer,  2012
【発明の概要】
【発明が解決しようとする課題】
【００１０】
このように、ヴィジラントのような法のもとでの逆元計算を含まない対策をもつことが望まれることが理解されるであろう。本発明は、ヴィジラントの対策の欠点の少なくともいくつかを克服する対策を提供する。
【課題を解決するための手段】
【００１１】
第一の側面では、本発明は、入力x、秘密の指数dおよび法Nを使った故障耐性のある冪乗を実行して結果Sを得る方法に向けられる。あらかじめ決定された値rを有するプロセッサが入力xを受領し；前記秘密の指数d、拡張されたベース＾x〔＾付きのx〕および拡張された法＾N〔＾付きのN〕に関わる、法のもとでの冪乗を使って中間的な結果Srを計算し；拡張されたベース＾xは入力xおよびランダムな値aを使って計算され、ここで、拡張された法＾Nは法Nおよび前記あらかじめ決定された値rを使って計算され、前記ランダムな値aとは独立であり；Srが前記あらかじめ決定された値rの倍数を法として計算された前記ランダムな値aを含む式を満たすことを検証し、前記検証が成功である場合にかつその場合にのみ結果S＝Sr  mod  Nを返す。
【００１２】
第一の実施形態では、前記プロセッサはさらに、前記ランダムな要素aを選ぶ。
【００１３】
第二の実施形態では、前記ランダムな値はa∈Z/rZを満たす。
【００１４】
第三の実施形態では、前記プロセッサはさらに、拡張されたベース
【数３】
2014174556.tif 000005
を計算する。ここで、iN＝N-1  mod  tは法のもとでの逆元であり、tは前記法Nとは互いに素であり、t＝br2であり、rおよびbは整数である。前記プロセッサがさらに拡張された法＾N＝Ntを計算することが有利である。
【００１５】
第四の実施形態では、中間的な値Srは
【数４】
2014174556.tif 000006
として計算される。
【００１６】
第五の実施形態では、中間的な値Srが満たすべき前記式はSr≡1＋dar  (mod  r2)である。
【００１７】
第二の側面では、本発明は、入力x、秘密の指数dおよび法Nを使った冪乗を実行して結果Sを得る装置に向けられる。前記冪乗は故障利用攻撃に対して耐性がある。前記装置は、入力xを受領して結果Sを出力するよう構成されたインターフェースと；プロセッサとを有する。前記プロセッサは：前記秘密の指数d、拡張されたベース＾x〔＾付きのx〕および拡張された法＾N〔＾付きのN〕に関わる、法のもとでの冪乗を使って中間的な結果Srを計算し；拡張されたベース＾xは入力xおよびランダムな値aを使って計算され、ここで、拡張された法＾Nは法Nおよびあらかじめ決定された値rを使って計算され、前記ランダムな値aとは独立であり、前記プロセッサは、複数の冪乗について前記あらかじめ決定された値rを使うよう構成されており；Srは前記あらかじめ決定された値rの倍数を法として計算された前記ランダムな値aを含む式を満たすことを検証し、前記検証が成功である場合にかつその場合にのみ結果S＝Sr  mod  Nを前記インターフェース（１１０）に送るよう構成されている。
【００１８】
第一の実施形態では、前記プロセッサはさらに、前記ランダムな要素aを選ぶよう構成されている。
【００１９】
第二の実施形態では、前記ランダムな値はa∈Z/rZを満たす。
【００２０】
第三の実施形態では、前記プロセッサはさらに、拡張されたベース
【数５】
2014174556.tif 000007
を計算するよう構成されている。ここで、iN＝N-1  mod  tは法の逆元であり、tは法Nとは互いに素であり、t＝br2であり、rおよびbは整数である。前記プロセッサがさらに拡張された法＾N＝Ntを計算するよう構成されていることが有利である。
【００２１】
第四の実施形態では、前記プロセッサは、前記中間的な値Srを
【数６】
2014174556.tif 000008
として計算するよう構成されている。
【００２２】
第五の実施形態では、中間的な値Srが満たすべき前記式はSr≡1＋dar  (mod  r2)である。
【００２３】
第三の側面では、本発明は、プロセッサによって実行されたときに前記第一の側面の方法を実行する命令を記憶している非一時的なコンピュータ媒体に向けられる。
【図面の簡単な説明】
【００２４】
本発明の好ましい特徴について、これから、限定しない例として、付属の図面を参照しつつ述べる。
【図１】本発明のある好ましい実施形態に基づいて故障利用攻撃に対する対策を備える暗号装置を示す図である。
【図２】本発明のある好ましい実施形態に基づく故障耐性のある冪乗の方法を示す図である。
【発明を実施するための形態】
【００２５】
ランダムな整数rを与えられたとき、ヴィジラントの対策は入力ベースを、
【数７】
2014174556.tif 000009
となるように拡張されたベース＾xに変換することが理解されるであろう。
【００２６】
すでに述べたように、ステップ２における法の逆元計算を別として、さらなる欠点は、拡張された法Nr2がランダムに構築されるということである。これはその効率的な使用を無にしかねない。実際、いくつかの冪乗アルゴリズムは法に対する条件を課す。結果として、拡張された法は通例、これらの条件に準拠するようさらに拡大されなければならない。
【００２７】
そこで、本発明の主たる発想は、固定した要素r（よって固定した拡張された法＾N）について、r2を法として「ランダム」な要素を構築するというものである。換言すれば、拡張された法は今や、選ばれた固定されたrについてあらかじめ決定されている。このようにして、法のもとでの逆元計算が回避できるとともに（一度だけ計算すればよい）、拡張された法は法に対して課される条件に準拠するよう選択されることができる。ヴィジラントの方法では、ランダム性はrの選択によって導入される。本発明では、rは固定されているため、別のところでランダム性が必要とされることを注意しておく。ヴィジラントの方法とは異なりr2を法とした拡張されたベース（すなわち、＾x  mod  r2）がランダムな要素として選ばれるのはこのためである。実際、ヴィジラントの方法においてrが固定されていたとしたら、＾x  mod  r2も固定されることになる、つまり＾x≡1＋r  (mod  r2)。
【００２８】
図１は、本発明のある好ましい実施形態に基づく、故障利用攻撃に対する対策を備えた暗号学的装置１００を示している。装置１００は、通信のために構成された少なくとも一つのインターフェース・ユニット１１０と、少なくとも一つの処理器（「プロセッサ」）１２０と、アキュムレータおよび仲介計算結果のようなデータを記憶するよう構成された少なくとも一つのメモリ１３０とを有する。図は、CD-ROMまたはDVDのような第一のコンピュータ・プログラム・プロダクト（非一時的な記憶媒体）１４０が記憶された命令を有しており、該命令はプロセッサ１２０によって実行されたときに本発明に基づいて冪乗計算を実行することを示している。
【００２９】
冪乗アルゴリズム（あらためて指摘するが、これは非限定的な例としてRSAに適合するアルゴリズム）については、(1＋r)が部分群G1＝{x∈Z/r2Z|  x≡1  (mod  r)}を生成することを注意しておくべきである。これは容易に検証される。G1の要素は、a∈{0,…,r−1}として、1＋a・rである。
【００３０】
すでに述べたように、好ましい実施形態は、事前に選択された整数rを使う。前記対策を提供するために、ランダムな要素a∈{0,…,r−1}が選ばれ、
【数８】
2014174556.tif 000010
となるように拡張されたベース＾xが形成される。
【００３１】
これは、事前に選択された整数t＝br2に簡単に一般化できる（ここで、bは整数＞0であり、1以外の平方数を因数として含まないものであっても（squarefree）なくてもよい）。
【００３２】
Nと互いに素な事前に選択された整数t＝br2について、プロセッサ１１０は法の逆元iN＝N-1  mod  tを取得または計算する。
【００３３】
これで装置１００は、故障利用攻撃に耐性のある、法のもとでの冪乗を実行する用意ができた。それは、インターフェース１１０を介して受領される入力xと、（秘密の）指数dとを使って、下記のように、そして図２に示されるように、行なわれる。
S1.  ランダムな要素a∈Z/rZを選ぶ；
S2.  ＾x＝x＋N・[iN(1＋ar−x)  mod  t]を計算する；
S3.  ＾N＝Ntを計算する；
S4.  Sr＝＾xd  mod  ＾Nを計算する；
S5.  Sr≡1＋dar  (mod  r2)であるかどうかを検証する；
S6.  上記が満たされる場合にかつその場合にのみ、インターフェース１１０を介してS=Sr  mod  Nを返し；それ以外の場合にはエラー・メッセージを返す。
【００３４】
tが固定されているので、iNの値が事前計算できることは注目に値する。したがって、＾xの評価のためには法のもとでの逆元計算は必要とされない。
【００３５】
示されるように、本発明の方法は、既存の諸実装とうまく組み合わされる。たとえば、キスケーターのアルゴリズム（特許文献１、「マイクロコントローラによる、いわゆるRSA法に基づくエンコード・システムおよびこのシステムを実装する構成」、参照）――すべてのフィリップス（現NXP）のコプロセッサで使われている――はその上位c個のビットが1に等しい法を要求する。これは、何らかの適切に選ばれた因子δを法Nに乗算することによって達成できる（非特許文献２参照）。
【００３６】
提案される方法に適用されると、たとえばt＝δと設定することが可能である。この個別的な事例では、本対策が事実上無償で得られることは注目に値する（追加的な作業メモリが必要なく、全体的なコストが非常に低いので）。
【００３７】
このように、本発明は、（事前計算できるものを別として）ヴィジラントの対策の主たるボトルネックであった逆元計算を必要としない対策を提供できることが理解されるであろう。これは、同じプロセッサおよびまともな実装が使われるとすれば、本願の方法がスピードの点でのよりよいパフォーマンスおよび作業メモリの要求低減を達成できることを意味する。さらに、提案される対策は、すでに法を拡張するある種の法乗算アルゴリズムとうまく組み合わせられる。
【００３８】
本稿および（適切な場合には）請求項および図面において開示される各特徴は、独立に提供されてもよいし、あるいは任意の適切な組み合わせにおいて提供されてもよい。ハードウェアにおいて実装されるとして記載されている特徴がソフトウェアで実装されてもよく、逆にソフトウェアにおいて実装されるとして記載されている特徴がハードウェアで実装されてもよい。請求項に参照符号があったとしても、それは単に例としてであって、請求項の範囲に対して限定する効果はもたない。
【符号の説明】
【００３９】
１００  暗号装置
１１０  I/O
１３０  メモリ
１２０  CPU
１４０  記憶媒体
S1  ランダムな要素a∈Z/rZを選ぶ；
S2  ＾x＝x＋N・[iN(1＋ar−x)  mod  t]を計算する
S3  ＾N＝Ntを計算する
S4  Sr＝＾xd  mod  ＾Nを計算する
S5  Sr≡1＋dar  (mod  r2)であるかどうかを検証する
S6  上記が満たされれば、S=Sr  mod  Nを返し；そうでなければエラー・メッセージを返す
【図１】
2014174556.tif 000015
【図２】
2014174556.tif 000016
【外国語明細書】
2014174556000001.pdf