暗号用演算装置、暗号用演算方法及びプログラム
【課題】（ｎ−１）入力型の選択文書型の単純電力解析に対する耐性を備え、演算効率のよい、暗号用演算装置を提供すること。
【解決手段】入力部１１は、べき乗剰余計算の底であるメッセージＭと、秘密のべき指数ｄと、法ｎとを入力する。前処理部１２は、該メッセージＭを２乗して、変換データを求める。暗号用演算部２は、上記変換データを演算対象とし、法ｎの下で、上記べき指数ｄのうち最下位ビットを除いたものに基づく右向き型演算手順により、べき乗剰余計算を行う。後処理部１３は、ｄのＬＳＢが１である場合には法ｎの下で上記演算結果とメッセージＭの乗算剰余計算を行い、ｄのＬＳＢが０である場合にはダミー計算として同一の乗算剰余計算を行う。出力部１４は、後処理部１３の演算結果（ｄのＬＳＢが１である場合）又は暗号用演算部２の演算結果（ｄのＬＳＢが０である場合）を最終的な演算結果として出力する。
【解決手段】入力部１１は、べき乗剰余計算の底であるメッセージＭと、秘密のべき指数ｄと、法ｎとを入力する。前処理部１２は、該メッセージＭを２乗して、変換データを求める。暗号用演算部２は、上記変換データを演算対象とし、法ｎの下で、上記べき指数ｄのうち最下位ビットを除いたものに基づく右向き型演算手順により、べき乗剰余計算を行う。後処理部１３は、ｄのＬＳＢが１である場合には法ｎの下で上記演算結果とメッセージＭの乗算剰余計算を行い、ｄのＬＳＢが０である場合にはダミー計算として同一の乗算剰余計算を行う。出力部１４は、後処理部１３の演算結果（ｄのＬＳＢが１である場合）又は暗号用演算部２の演算結果（ｄのＬＳＢが０である場合）を最終的な演算結果として出力する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、べき乗剰余計算や楕円曲線上のスカラー倍算などの暗号用演算を行う暗号用演算装置、暗号用演算方法及びプログラムに関する。
【背景技術】
【０００２】
ＩＣカードに代表される小規模なデバイスは、携帯可能で、情報セキュリティの核となる利用者の認証や、決済データの認証などに利用される。ＩＣカード上のＬＳＩに搭載されている暗号機能には一般に耐タンパー対策が施され、ＬＳＩ内部に記憶されている秘密鍵の漏洩が生じないように実装される。耐タンパー対策としては、ＬＳＩの消費電力の変動を観測して秘密鍵の推定を容易にする電力解析などのサイドチャネル攻撃に対しても、演算上の工夫により防御する手法が知られている。
【０００３】
ＲＳＡ暗号や楕円曲線暗号などの公開鍵暗号は、べき乗剰余演算あるいは楕円曲線上のスカラー倍算と呼ばれる基本演算を利用して構成される。これらの基本演算に対する電力解析攻撃の対策手法として、秘密鍵のパターンに依存せずに規則的に行う演算手法が、単純電力解析（ＳＰＡ(Simple Power Analysis)）と呼ばれる攻撃に有効であることが知られている。こうしたＳＰＡ攻撃に耐性のある、べき乗剰余演算（あるいはスカラー倍算）として、Add-and-Double-Always法（非特許文献１）や、モンゴメリ・ラダー法（非特許文献２）がある。
【０００４】
しかし、最近、従来のＳＰＡ耐性のあるべき乗剰余演算に対する新たな攻撃手法が見出されてきており、例えば、非特許文献３では、選択文書型のＳＰＡが示されている。特に、ＲＳＡ暗号や楕円曲線暗号におけるＳＰＡ対策として有名な、右向きバイナリ型のAdd-and-Double-Always演算手法に対し、モジュラスをｎとして、（ｎ−１）を入力に与える単純な手法で、従来のＳＰＡ対策が破られることが示されている。
【０００５】
また、発明者の検討により、モンゴメリ・ラダー法に対しても、Ｙｅｎらの（ｎ−１）入力型ＳＰＡによりＳＰＡ対策を無効化できることが判明した。
【０００６】
選択文書型のＳＰＡに対する汎用的で強力な対策に、入力メッセージに対してランダムなマスクをかけて演算を行うメッセージ・ブラインディング法の適用がある。しかし、同対策手法では、演算コストの小さくない逆元計算が必要であるという問題や、通常のべき乗計算に比べて２倍の演算コストがかかる場合があるという問題などがある。
【非特許文献１】J.S.Coron, ”Resistance against differential power analysis for elliptic curve”, CHES ’99.
【非特許文献２】M.Joye and S.-M. Yen, ”The Montgomery Powering Ladder”, CHES 2002.
【非特許文献３】S.-M. Yen et al., ”Power Analysis by Exploiting Chosen Message and Internal Collisions”, Mycrypt 2005.
【発明の開示】
【発明が解決しようとする課題】
【０００７】
ＲＳＡ暗号や楕円曲線暗号の実装モジュールにおいて、選択文書型のＳＰＡ攻撃により、従来の対策演算法が無効化されてしまうことが判明している。選択文書型の電力解析攻撃の中では、ある入力に対する暗号処理の１回の実行波形だけで秘密鍵の多くのビットパターンを推定可能とする（ｎ−１）入力型ＳＰＡや、その拡張攻撃が特に脅威となる。しかし、それら脅威に対する対策演算法は知られていない。
【０００８】
本発明は、上記事情を考慮してなされたもので、右向き型のバイナリべき乗算やモンゴメリ・ラダー算法における（ｎ−１）入力型ＳＰＡやその拡張攻撃手法に対する効率的な対策演算法を実現した暗号用演算装置、暗号用演算方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００９】
本発明は、２進数からなる秘密のパラメータの上位ビットから下位ビットに向けて計算を進める手順である右向き型演算手順を用いて、特定の暗号用演算を行う暗号用演算装置であって、前記暗号用演算の対象となるデータと、前記演算に用いる前記秘密のパラメータと、前記演算に用いる他のパラメータとを入力する入力部と、前記データに対して、特定の変換を施して、変換データを求める前処理部と、前記変換データと、前記秘密のパラメータの全部又は一部と、前記他のパラメータとを入力として、該秘密のパラメータの全部又は一部を用いた前記右向き型演算手順により、前記暗号用演算を行って、その演算結果を求める暗号用演算部と、前記暗号用演算部が求めた前記演算結果をもとにして、前記データと前記秘密のパラメータの全部と前記他のパラメータとを入力とした場合の前記暗号用演算の演算結果を求める後処理を行う後処理部と、前記暗号用演算部が求めた前記演算結果又は前記後処理部が求めた前記演算結果を、最終的な演算結果として出力する出力部とを備えたことを特徴とする。
【発明の効果】
【００１０】
本発明によれば、右向き型のバイナリべき乗算やモンゴメリ・ラダー算法における（ｎ−１）入力型ＳＰＡやその拡張攻撃手法に対する効率的な対策演算法を実現することができる。
【発明を実施するための最良の形態】
【００１１】
以下、図面を参照しながら本発明の実施形態について説明する。
【００１２】
まず、本実施形態に係る暗号用演算装置について説明するのに先立って、本実施形態において考慮する選択入力型ＳＰＡについて説明する。なお、以下で扱う暗号用演算は、べき乗剰余計算や楕円曲線上のスカラー倍算である。
【００１３】
べき乗剰余計算の計算手順として、大きく、右向き型演算手順（指数の上位ビットから下位ビットに向けて計算を進める演算手順）と、左向き型演算手順（指数の下位ビットから上位ビットに向けて計算を進める演算手順）とがある。これらのうち、本実施形態で考慮する選択入力型ＳＰＡが脅威となるのは、右向き型演算手順のべき乗剰余計算である。
【００１４】
右向き型べき乗剰余計算は、指数をｗ（複数）ビットずつまとめて処理を行うｗビットウィンドウ法に拡張できることや、演算途中の計算結果の記憶量が削減できる場合があることなどの利点があり、実装上利用される場面が多い。右向き型べき乗剰余計算法の具体例に、右向きバイナリ法とモンゴメリ・ラダー法とがある。
【００１５】
右向きバイナリ法は、そのままの実装では指数ビットによる剰余乗算の処理分岐があるため、通常のＳＰＡに弱く、ＳＰＡ対策を考慮してダミー処理を追加した手順が利用される場面が多い。以降の説明では、ＳＰＡ対策を考慮した右向きバイナリ法を例として非特許文献３で示された選択入力型ＳＰＡを説明する。
【００１６】
非特許文献３の選択入力型ＳＰＡは、１回もしくは２回のべき乗剰余計算の実行波形から、特定のビットを除くほぼ全ての指数ビットを推定可能とする、非常に脅威となる攻撃である。非特許文献３では、法ｎに対して、（ｎ−１）を入力とする（−１）入力ＳＰＡ、ｘと−ｘの１組を入力とする（ｘ，−ｘ）入力ＳＰＡの２種類が示されている。
【００１７】
まず、右向きバイナリ法に対して（−１）入力ＳＰＡを適用した場合について説明する。
【００１８】
図１４に、この場合における演算経過の一例を示す。
【００１９】
この場合、指数ビットを１ビット処理する度に２乗剰余処理と乗算剰余処理とが繰り返されるが、登場する演算パターンは、
１＊１ ｍｏｄ ｎ，
(-1)＊(-1) ｍｏｄ ｎ，
１＊(-1) ｍｏｄ ｎ
の３種類にすぎず、更に、２乗剰余処理部では、1*1 mod n又は(-1)*(-1) mod nのいずれかが実行される。
【００２０】
ここで、あるビットｄ（ｉ）における２乗剰余処理部の演算内容と、１つ前に処理したビットｄ（ｉ−１）の値との関係に着目すると、２乗剰余処理部で上記のいずれの演算が実行されるかは、１つ前に処理したビットｄ（ｉ−１）が０であるか又は１であるかに依存していることが分る。すなわち、あるビットｄ（ｉ）について２乗剰余処理部で1*1 mod n又は(-1)*(-1) mod nのいずれが実行されたかが分かれば、１つ前のビットｄ（ｉ−１）が０であるか又は１であるかが特定できることになる。
【００２１】
２乗剰余処理は規則的なタイミングで発生するため、ＳＰＡによりこの２種類の波形の区別さえできれば、指数ｄのＬＳＢを除く全てのビットパターンが判明する。
【００２２】
実際、この２種類の波形の区別が可能であることを実験により確認した結果も報告されており、（−１）入力ＳＰＡへの対策は必須となる。
【００２３】
この攻撃への対策として、入力が（−１）であるかどうかを検査し、もしそうであれば、指数のＬＳＢの０／１に応じて、べき乗剰余結果として（実際に演算を進めることなく）０／１を出力する方法で対処できる。しかし、非特許文献３では、（−１）入力ＳＰＡを拡張した（ｘ，−ｘ）入力ＳＰＡも提示されている。
【００２４】
次に、右向きバイナリ法に対して（ｘ，−ｘ）入力ＳＰＡを適用した場合について説明する。
【００２５】
図１５に、この場合の演算経過の一例を示す。
【００２６】
この場合、入力ｘでの演算経過と入力（−ｘ）での演算経過とを比較すると、乗算剰余処理部での（−ｘ）入力時の結果は、常に、ｘ入力時の演算結果に（−１）を乗じた値になっていることが分る。
【００２７】
従って、２乗剰余処理部に着目すると、ｘ入力時と（−ｘ）入力時とで全く同じ演算が行われるのは、１つ前に処理したビットｄ（ｉ−１）が０のときに限られ、この性質から、ＳＰＡで２乗剰余処理に着目して２波形を比較することにより、ＬＳＢを除く指数のビットパターンが判明することが分る。
【００２８】
次に、モンゴメリ・ラダー算法に対して（−１）入力ＳＰＡを適用した場合について説明する。
【００２９】
モンゴメリ・ラダー算法は次の通りである。
【００３０】
（１）べき指数ｄ＝[d(m-1),..,di,..,d1,d0]_2の上位ビットからｄｉまでを処理した中間結果として、（Ｌｉ，Ｒｉ）なる組が得られる。ここで、Ｄｉ＝[d/2^i]（ここで、［ｘ］はｘ以下の最大の整数を表す。）として、Ｌｉ＝M^Di (mod n)，Ｒｉ＝M^(Di+1) (mod n)である。初期値を（Ｌｍ，Ｒｍ）＝（Ｍ＾０，Ｍ＾１）＝（１，Ｍ）とする。
【００３１】
（２）着目する指数ビットｄ（ｉ−１）に応じて、図１６に示す計算を実行する。ここで、Ｌ０が最終結果を与える。
【００３２】
上記算法では、Ｌｉが本来の中間結果、Ｒｉが補助的な中間値である。指数部の差が１であることに注意して指数部に着目すると、必ず一方は奇数、他方は偶数になる。
【００３３】
（−１）を入力Ｍとして与えたとき、(-1)^(2k)=1，(-1)^(2k+1)=-1であり、ＬｉとＲｉは、指数の偶数・奇数に応じて、１か（−１）の組しかとり得ない。
【００３４】
従って、Ｌｉ，Ｒｉの計算時に登場するパターンも、
１＊１，
(-1)＊(-1)，
１＊(-1)，
(-1)＊１
の４種類のみであり、これらのパターンはＳＰＡでの判別が容易である。
【００３５】
これらのうち、(-1)*(-1)の計算が登場する場合に着目すると、Ｄ（ｉ＋１）が偶数でＤｉが奇数（すなわちd(i+1)=0かつdi=1）のケースと、Ｄ（ｉ＋１）が奇数でＤｉが偶数（すなわちd(i+1)=1かつdi=0）のケースとに限られる。このことは、べき指数の上位から順にＳＰＡで指数値を順次決定できることを表している。
【００３６】
図１７に、モンゴメリ・ラダー算法に対して（−１）入力ＳＰＡを適用した場合の演算経過の一例を示す。
【００３７】
図１７の例では、(-1)*(-1) mod nの計算は、指数ビットが下位から５番目、３番目、１番目の計算においてであり、これらのビットが一つ上位のビットと０／１が反転した関係になっていることを利用して、ＬＳＢを除く全てのビットを推定できる。
【００３８】
次に、モンゴメリ・ラダー算法に対して（ｘ，−ｘ）入力ＳＰＡを適用した場合について説明する。
【００３９】
図１８に、この場合における演算経過の一例を示す。
【００４０】
この場合、モンゴメリ・ラダー算法での中間レジスタに記憶される値の指数に着目すると、必ず一方は奇数、他方は偶数になることから、（−ｘ）入力時には、L*R mod nの計算結果は必ず-x^y mod nとなる。
【００４１】
従って、R←L*R mod nとL←L*R mod nの演算結果を、ｘ入力時の同じタイミングでの演算と比較すると、必ず符号反転した結果となる。
【００４２】
指数ビットとして０もしくは１が連続した場合には、それぞれL←L*L mod n、R←R*R mod nの計算が繰り返され、その場合に限って、ｘ入力時の演算と全く同じ演算が同じタイミングで出現することが分る。
【００４３】
この性質から、ＳＰＡでｘ入力時と（−ｘ）入力時との２波形の差分を解析することにより、指数のビットパターンが判明することが分る。
【００４４】
以上で説明したように、ＳＰＡに対して耐性があると考えられてきた右向きバイナリ型算法やモンゴメリ・ラダー算法において、（−１）入力ＳＰＡや（ｘ，−ｘ）入力ＳＰＡにより秘密指数のパターンが判明する可能性が高いことが明らかとなった。
【００４５】
以下、本実施形態では、これらの選択入力型ＳＰＡに対する耐性を備えた本実施形態に係る暗号用演算装置について説明する。
【００４６】
図１に、本実施形態の暗号用演算装置の構成例を示す。
【００４７】
図１に示されるように、本実施形態の暗号用演算装置は、攻撃無効化処理部１と暗号用演算部２とを備えている。
【００４８】
暗号用演算部２は、既存の所定の暗号用演算を行う。所定の暗号用演算は、例えば、べき乗剰余計算や楕円曲線上のスカラー倍算である。
【００４９】
攻撃無効化処理部１は、上記選択文書型ＳＰＡ攻撃に対する耐性を暗号用演算装置に付与するために、該攻撃を無効化するための処理を行う。
【００５０】
攻撃無効化処理部１は、入力部１１、前処理部１２、後処理部１３、出力部１４を備えている。
【００５１】
攻撃無効化処理部１と暗号用演算部２とをハードウェアにより構成するかソフトウェアにより構成するかについては、例えば次のようなバリエーションがある。
（１）攻撃無効化処理部１と暗号用演算部２とをすべてハードウェアにより構成する。
（２）攻撃無効化処理部１と暗号用演算部２とをすべてソフトウェアにより構成する。
（３）攻撃無効化処理部１をソフトウェア（ファームウェア）により構成し、暗号用演算部２をハードウェアにより構成する。
【００５２】
なお、暗号用演算部２は、既存のもので構わないので、既存の暗号用演算部２に、新たに攻撃無効化処理部１を追加して、本実施形態の暗号用演算装置を実現することが可能である。
【００５３】
図２に、本実施形態の暗号用演算装置の動作手順の一例を示す。
【００５４】
ステップＳ１で、入力部１１は、当該暗号用演算の対象となるデータ（べき乗剰余計算の場合のメッセージＭ、楕円曲線上のスカラー倍算の場合のＰ）、該演算に用いる秘密のパラメータｄ＝[d(m-1),..,di,..,d1,d0]_2（ただし、[]_2は２進数展開を意味する）、該演算に用いるその他のパラメータを入力する。
【００５５】
なお、所定の暗号用演算が、べき乗剰余計算である場合、ｄは、（秘密の）指数であり、その他のパラメータには、べき乗剰余計算の法ｎが該当する。また、所定の暗号用演算が、楕円曲線上のスカラー倍算である場合、ｄは、（秘密の）スカラー値であり、その他のパラメータには、楕円曲線ドメインパラメータＥが該当する。
【００５６】
なお、入力部１１は、それらデータを、どのような方法で入力するものであっても良い。例えば、入力デバイスや通信デバイスやメモリデバイスなどから入力しても良いし、他のプロセスから入力しても良い。
【００５７】
ステップＳ２で、前処理部１２は、（暗号用演算部２に対する）上記攻撃を無効化するために、演算対象となるデータに対して所定の変換を施して変換データを生成する処理を含む前処理を行う。より具体的には後述するが、演算対象となるデータの変換については、所定の暗号用演算が、べき乗剰余計算である場合に、例えば、M’←M^2 mod nなどを行い、所定の暗号用演算が、楕円曲線上のスカラー倍算である場合に、例えば、P’←2*Pなどを行う。生成された変換データ（例えば、Ｍ’やＰ’）は、暗号用演算部２に与えられる。
【００５８】
また、より具体的には後述するが、入力されたｄの全部又は一部のビット（例えば、最下位ビットを除いたｄ’＝[d(m-1),..,di,..,d1]_2）が暗号用演算部２に与えられる。また、入力された、その他のパラメータが、暗号用演算部２に与えられる。更に、それら以外の情報が暗号用演算部２に与えられる場合もある。
【００５９】
ステップＳ３で、暗号用演算部２は、与えられた、生成された変換データ（例えば、Ｍ’やＰ’）と、秘密のパラメータｄ’の全部又は一部のビットと、その他のパラメータとを入力として、当該所定の暗号用演算を行う。
【００６０】
なお、この暗号用演算部２により得られる演算結果は、求めるべき最終的な演算結果ではない（あるいは、条件に応じて、最終的な演算結果になることもある）。
【００６１】
ステップＳ４で、後処理部１３は、暗号用演算部２の計算結果をもとに、最終的な演算結果を生成する。より具体的には後述するが、所定の暗号用演算が、べき乗剰余計算である場合に、例えば、S←S*M mod n（暗号用演算部２の計算結果に更にMを乗算）などを行い、所定の暗号用演算が、楕円曲線上のスカラー倍算である場合に、例えば、Q←Q+P（暗号用演算部２の計算結果に更にPを加算）などを行う。なお、その際、より具体的には後述するが、所定の暗号用演算によっては、攻撃を無効化するために、ダミー演算を行うことがある。
【００６２】
ステップＳ５で、出力部１４は、後処理部１３により得られた計算結果（条件に応じて、暗号用演算部２により得られた計算結果）を出力する。例えば、所定の暗号用演算が、べき乗剰余計算である場合に、Ｓ＝M^ｄ mod nを出力し、所定の暗号用演算が、楕円曲線上のスカラー倍算である場合に、Q=d*Pを出力する。
【００６３】
なお、出力部１４は、最終的な計算結果を、どのような方法で出力するものであっても良い。例えば、出力デバイスや通信デバイスやメモリデバイスなどへ出力しても良いし、他のプロセスへ出力しても良い。
【００６４】
以下、暗号用演算装置のより具体的な構成例について説明する。
【００６５】
以下説明する第1〜第３の実施形態は、暗号用演算として、べき乗剰余計算を例にとったものであり、第４，５の実施形態は、暗号用演算として、楕円曲線上でのスカラー倍算を例にとったものである。
【００６６】
＜べき乗剰余演算＞
図３に、図１を「べき乗剰余計算」用に記述した構成例を示す。
【００６７】
第1〜第３の実施形態では、暗号用演算装置は「べき乗剰余計算装置」、暗号用演算部は「べき乗剰余計算部」と呼ぶ。
【００６８】
（第１の実施形態）
本発明の第１の実施形態に係るべき乗剰余演算装置について説明する。本実施形態では、べき乗剰余演算の３つの演算手順例を示す。
【００６９】
最初に、右向きバイナリ型算法によるべき乗剰余演算に対する、（−１）入力ＳＰＡ攻撃と（ｘ，−ｘ）入力ＳＰＡ攻撃を無効化できるようにした例について説明する。
【００７０】
図４に、この場合のべき乗剰余演算の演算手順の一例を示す。
【００７１】
まず、ステップＳ１０で、入力部１１は、べき乗剰余計算の底であるメッセージＭと、秘密のべき指数ｄ＝[d(m-1),..,di,..,d1,d0]_2と、法ｎとを入力する。
【００７２】
ステップＳ１１で、前処理部１２は、Ｍを２乗剰余計算（M^2 mod n）し、その計算結果をＭ’とする。
【００７３】
上記のＭ’を底、入力されたｄのうち最下位ビットを除いたｄ’（ｄ’＝[d/2]）をべき指数、入力されたｎを法として、それらが攻撃無効化処理部１からべき乗剰余計算部２へ与えられる。
【００７４】
ステップＳ１２で、べき乗剰余計算部２は、それらをもとに、（右向き型の）べき乗剰余計算（M’^d’ mod n）を行い、その計算結果Ｓを求める。
【００７５】
このＳは、べき乗剰余計算部２から攻撃無効化処理部１へ返される。
【００７６】
ステップＳ１３で、後処理部１３は、入力されたｄの最下位ビット（ＬＳＢ）ｄ０が１かどうか調べ、ｄ０が１である場合には、ステップＳ１４に進んで、後処理部１３は、上記計算結果ＳとＭを法ｎで乗算剰余計算（S*M mod n）し、この計算結果で、Ｓを更新する。この（更新後の）Ｓが、最終的なべき乗剰余演算結果（M^d mod n）になる。
【００７７】
一方、ｄ０が０である場合には、ステップＳ１５に進んで、後処理部１３は、ダミー処理として、ステップＳ１４と同じ計算（S*M mod n）を行い、その結果は、本来の出力と異なる領域Ｓ’に保存する。この場合、べき乗剰余計算部２により求められたＳが、最終的なべき乗剰余演算結果（M^d mod n）になる。
【００７８】
ステップＳ１６で、出力部１４は、べき乗剰余演算結果S=M^d mod nを出力する。
【００７９】
なお、上記演算手順例において、ステップＳ１５のダミー処理は、べき指数ｄのＬＳＢの０／１の判別をタイミング攻撃により防ぐ目的で追加しているが、暗号の演算では、べき指数のＬＳＢは１であることが、暗号アルゴリズムの性質から事前に判明している場合もある。よって、べき指数のＬＳＢの０／１の判別をサイドチャネル攻撃から防御する必要がない場合には、ステップＳ１５のダミー処理は省略しても良い。
【００８０】
また、べき乗剰余計算部２と攻撃無効化処理部１との間でＳをやり取りする方法としては、Ｓをべき乗剰余計算部２と攻撃無効化処理部１とで共有する記憶領域に記憶しても良いし、べき乗剰余計算部２と攻撃無効化処理部１との間でＳを転送しても良いし、べき乗剰余計算部２と攻撃無効化処理部１との間でＳの記憶場所を示すポインタを転送しても良い。
【００８１】
さて、この計算手順例によれば、ステップＳ１１により得られるＭ’は、ｘ入力時と−ｘ入力時で常にｘ＾２となる。従って、ステップＳ１２でのべき乗計算時には、ｘと−ｘのいずれの入力でも常に同じ演算が行われ、ステップＳ１３以降の処理で符号により異なる処理が行われる。このため、（ｘ、−ｘ）入力ＳＰＡで指数ビットが判明する可能性があるのは、指数ｄのＬＳＢのみであり、それ以外のビットは、判別することが不可能になる。また、（−１）入力ＳＰＡでも、同様の性質から、指数ｄのＬＳＢを除く指数ビットが保護できる。
【００８２】
次に、モンゴメリ・ラダー算法によるべき乗剰余演算に対する、（−１）入力ＳＰＡ攻撃と（ｘ，−ｘ）入力ＳＰＡ攻撃を無効化できるようにした例について説明する。
【００８３】
図５に、この場合のべき乗剰余演算の演算手順の一例を示す。
【００８４】
まず、ステップＳ２０で、入力部１１は、べき乗剰余計算の底であるＭと、秘密のべき指数ｄ＝[d(m-1),..,di,..,d1,d0]_2と、法ｎとを入力する。
【００８５】
ステップＳ２１で、前処理部１２は、Ｍを２乗剰余計算し、その計算結果（M^2 mod n）をＭ’とする。
【００８６】
上記のＭ’を底、入力されたｄをべき指数、入力されたｎを法として、それらが攻撃無効化処理部１からべき乗剰余計算部２へ与えられる。
【００８７】
ステップＳ２２で、べき乗剰余計算部２は、参照する指数ビットを表すインデックスｉをｍにセットし、中間レジスタＬに１をセットし、中間レジスタＲに、与えられたＭ’をセットする。
【００８８】
以降、ステップＳ２３からステップＳ２７までの処理ループで、べき乗剰余計算部２は、指数ビットｄ（ｍ−１）からｄ１までのべき指数に対応したべき乗計算を行う。
【００８９】
ステップＳ２３で、インデックスｉをデクリメントし、ステップＳ２４で、ｉが０より大きいかどうか調べる。
【００９０】
ｉが０より大きい場合には、ステップＳ２５で、指数ビットｄｉが１であるかどうか調べ、ｄｉが１ならば、ステップＳ２６に進んで、L←L*R mod nとR←R*R mod nの計算を行い、ｄｉが０ならば、ステップＳ２７に進んで、R←L*R mod nとL←L*L mod nの計算を行う。そして、ステップＳ２３に戻って、次の処理ループに移る。
【００９１】
以上の処理ループが繰り返された結果、ステップＳ２３でｉ＝０になると、ステップＳ２４で、ｉが０より大きくないので、この処理ループを抜けて、ステップＳ２８へ分岐することになる。
【００９２】
ここで、べき乗剰余計算部２による計算は終了となり、このときの（Ｒ，Ｌ）が、べき乗剰余計算部２から攻撃無効化処理部１へ返される。
【００９３】
ステップＳ２８で、後処理部１３が、入力されたｄの最下位ビット（ＬＳＢ）ｄ０が１かどうか調べ、ｄ０が１である場合には、ステップＳ２９に進んで、後処理部１３が、上記計算結果ＬとＭを法ｎで乗算剰余計算（L*M mod n）し、この計算結果で、Ｌを更新する。この（更新後の）Ｌが、最終的なべき乗剰余演算結果（M^d mod n）になる。
【００９４】
一方、ｄ０が０である場合には、ステップＳ３０に進んで、後処理部１３が、ダミー処理として、ステップＳ２９と同じ計算（L*M mod n）を行い、その結果は、本来の出力と異なる領域Ｒ（他の領域でも構わない。）に保存する。この場合、べき乗剰余計算部２により求められたLが、最終的なべき乗剰余演算結果（M^d mod n）になる。
【００９５】
ステップＳ３１で、出力部１４が、べき乗剰余演算結果L =M^d mod nを出力する。
【００９６】
なお、べき乗剰余計算部２と攻撃無効化処理部１との間でＬをやり取りする方法としては、Ｌをべき乗剰余計算部２と攻撃無効化処理部１とで共有する記憶領域に記憶しても良いし、べき乗剰余計算部２と攻撃無効化処理部１との間でＬを転送しても良いし、べき乗剰余計算部２と攻撃無効化処理部１との間でＬの記憶場所を示すポインタを転送しても良い。なお、Ｌをべき乗剰余計算部２と攻撃無効化処理部１とで共有する記憶領域に記憶する場合に、Ｒもべき乗剰余計算部２と攻撃無効化処理部１とで共有する記憶領域に記憶しても良い。
【００９７】
また、上記では、攻撃無効化処理部１からべき乗剰余計算部２へ、ｄ＝[d(m-1),..,di,..,d1,d0]_2を与えたが、その代わりに、ｄのうち最下位ビットを除いたｄ’（ｄ’＝[d/2]）を与えるようにしても良い（この場合、ステップＳ２２でｉ＝ｍ−１となり、ステップＳ２４でｉが負になったら処理ループを抜けるようになれば良い）。
【００９８】
次に、右向きバイナリ型算法によるべき乗剰余演算に対する、（−１）入力ＳＰＡ攻撃と（ｘ，−ｘ）入力ＳＰＡ攻撃を無効化できるようにした例について説明する。
【００９９】
図６に、この場合のべき乗剰余演算の演算手順の一例を示す。
【０１００】
まず、ステップＳ４０で、入力部１１は、べき乗剰余計算の底であるＭと、秘密のべき指数ｄ＝[d(m-1),..,di,..,d1,d0]_2と、法ｎとを入力する。
【０１０１】
ステップＳ４１で、前処理部１２は、Ｍを２乗剰余計算（M^2 mod n）し、その計算結果をＭ’とする。
【０１０２】
上記のＭ’を底、入力されたｄをべき指数、入力されたｎを法として、それらが攻撃無効化処理部１からべき乗剰余計算部２へ与えられる。
【０１０３】
ステップＳ４２で、べき乗剰余計算部２は、参照する指数ビットを表すインデックスｉをｍにセットし、中間レジスタＳに１をセットする。
【０１０４】
以降、ステップＳ４３からステップＳ４８までの処理ループで、べき乗剰余計算部２は、指数ビットｄ（ｍ−１）からｄ１までのべき指数に対応したべき乗計算を行う。
【０１０５】
ステップＳ４３で、インデックスｉをデクリメントし、ステップＳ４４で、ｉが０より大きいかどうか調べる。
【０１０６】
ｉが０より大きい場合には、ステップＳ４５に進んで、Ｓを２乗剰余計算（S^2 mod n）し、その計算結果でＳを更新した後に、ステップＳ４６で、指数ビットｄｉが１であるかどうか調べ、ｄｉが１ならば、ステップＳ４７に進んで、S←S*M’ mod nの計算を行い、ｄｉが０ならば、ステップＳ４８に進んで、ダミー処理として、S’←S*M’ mod nの計算を行う。ここで、Ｓ’はダミー処理の結果を保存するレジスタである。そして、ステップＳ４３に戻って、次の処理ループに移る。
【０１０７】
以上の処理ループが繰り返された結果、ステップＳ４３でｉ＝０になると、ステップＳ４４で、ｉが０より大きくないので、この処理ループを抜けて、ステップＳ４９へ分岐することになる。
【０１０８】
ここで、べき乗剰余計算部２による計算は終了となり、このときのＳが、べき乗剰余計算部２から攻撃無効化処理部１へ返される。
【０１０９】
ステップＳ４９で、後処理部１３は、入力されたｄの最下位ビット（ＬＳＢ）ｄ０が１かどうか調べ、ｄ０が１である場合には、ステップＳ５０に進んで、後処理部１３は、上記計算結果ＳとＭを法ｎで乗算剰余計算（S*M mod n）し、この計算結果で、Ｓを更新する。この（更新後の）Ｓが、最終的なべき乗剰余演算結果（M^d mod n）になる。
【０１１０】
一方、ｄ０が０である場合には、ステップＳ５１に進んで、後処理部１３は、ダミー処理として、ステップＳ５０と同じ計算（S*M mod n）を行い、その結果は、本来の出力と異なる領域Ｓ’に保存する。この場合、べき乗剰余計算部２により求められたＳが、最終的なべき乗剰余演算結果（M^d mod n）になる。
【０１１１】
ステップＳ５２で、出力部１４は、べき乗剰余演算結果S=M^d mod nを出力する。
【０１１２】
なお、べき乗剰余計算部２と攻撃無効化処理部１との間でＳをやり取りする方法としては、Ｓをべき乗剰余計算部２と攻撃無効化処理部１とで共有する記憶領域に記憶しても良いし、べき乗剰余計算部２と攻撃無効化処理部１との間でＳを転送しても良いし、べき乗剰余計算部２と攻撃無効化処理部１との間でＳの記憶場所を示すポインタを転送しても良い。なお、Ｓをべき乗剰余計算部２と攻撃無効化処理部１とで共有する記憶領域に記憶する場合に、Ｓ’もべき乗剰余計算部２と攻撃無効化処理部１とで共有する記憶領域に記憶しても良い。
【０１１３】
また、上記では、攻撃無効化処理部１からべき乗剰余計算部２へ、ｄ＝[d(m-1),..,di,..,d1,d0]_2を与えたが、その代わりに、ｄのうち最下位ビットを除いたｄ’（ｄ’＝[d/2]）を与えるようにしても良い（この場合、ステップＳ３２でｉ＝ｍ−１となり、ステップＳ３４でｉが負になったら処理ループを抜けるようになれば良い）。
【０１１４】
本発明によれば、ＲＳＡ暗号や楕円曲線暗号に対する選択入力型ＳＰＡで脅威となる（ｎ−１）攻撃を無効化することができる。また、本対策による演算手法での処理量の増加はほとんどない。さらに、（ｎ−１）攻撃の拡張として、入力ｘと−ｘの１組を与え、それぞれの電力波形の差分を解析して内部状態の差異から秘密指数を推定する攻撃も無効化することができる。
【０１１５】
（第２の実施形態）
本発明の第２の実施形態に係るべき乗剰余演算装置について説明する。
【０１１６】
ここでは、（−１）入力ＳＰＡを拡張した攻撃とその対策について説明する。
【０１１７】
（−１）は乗法に関する単位元である１の平方根（位数２）である。べき乗の右向きバイナリ計算法で、入力をＭとし、指数ｄ＝[d(m-1),..,dj,..,d1,d0]_2の最上位からｄｊまでを処理した中間値をＳｊとする。Ｄｊ＝[d(m-1),…,dj]_2とおくと、Ｓｊ＝M^Dj mod nである。従って、Ｍとして位数２の値である（−１）を入力すると、Ｄｊの最下位ビットであるｄｊの０／１に依存して、Ｓｊ＝１（dj=0のとき）、Ｓｊ＝−１（dj=1のとき）となる。この後、指数ｄ（ｊ−１）ビットの処理に移り、最初にSj^2 mod nの計算が行われ、この処理がｄｊの値に依存した２通りしかないことが、攻撃に利用されている。
【０１１８】
この原理を拡張すると、位数２＾ｔ（ｔは１以上の整数）の元を入力とする攻撃が考えられる。位数２＾ｔの元は、乗法群の位数λ（元の個数）に依存して存在する場合と存在しない場合とがある。実際に、λ mod 2^tが０となる場合には、位数２＾ｔの元が存在し、λが判明している場合には、多項式時間のアルゴリズムで求めることができる。
【０１１９】
例えば、位数２＾２＝４の元αをべき乗の右向きバイナリ計算法に入力すると、指数ｄの最上位からｄｊビットまでを処理した中間値Ｓｊ(=M^Dj mod n)は、Dj mod (2^2)の値（すなわち、ｄ（ｊ＋１）とｄｊの２ビット）に依存して決まる。すなわち、
［ｄ（ｊ＋１），ｄｊ］＝［０，０］のとき、Ｓｊ＝１、
［ｄ（ｊ＋１），ｄｊ］＝［０，１］のとき、Ｓｊ＝α、
［ｄ（ｊ＋１），ｄｊ］＝［１，０］のとき、Ｓｊ＝α＾２＝−１、
［ｄ（ｊ＋１），ｄｊ］＝［１，１］のとき、Ｓｊ＝α＾３＝−α
となる。
【０１２０】
次に、隣のｄ（ｊ−１）ビットの処理に移り、最初の２乗処理では、
［ｄ（ｊ＋１），ｄｊ］＝［０，０］の場合には、1^2 mod n=1の計算が行われ、
［ｄ（ｊ＋１），ｄｊ］＝［０，１］の場合には、α^2 mod n=-1の計算が行われ、
［ｄ（ｊ＋１），ｄｊ］＝［１，０］の場合には、(-1)^2 mod n=1の計算が行われ、
［ｄ（ｊ＋１），ｄｊ］＝［１，１］の場合には、(-α)^2=-1の計算が行われる。
【０１２１】
また、その次の乗算では、
［ｄ（ｊ＋１），ｄｊ］＝［０，０］の場合には、1×α mod nの計算が行われ、
［ｄ（ｊ＋１），ｄｊ］＝［１，０］の場合には、1×α mod nの計算が行われ、
［ｄ（ｊ＋１），ｄｊ］＝［０，１］の場合には、(-1)×α mod nの計算が行われ、
［ｄ（ｊ＋１），ｄｊ］＝［１，１］の場合には、(-1)×α mod nの計算が行われる。
【０１２２】
このように、２乗処理部では４通り、乗算処理部では２通りの計算しか現れず、これらの計算は、指数ビット[d(j+1),dj]の２ビットに依存して、パターンが分かれることから、ＳＰＡによって攻撃が容易となる可能性が高い。
【０１２３】
この位数４の元αを利用したＳＰＡは、ｗビットウィンドウ法（例えば、２ビットウィンドウ法）によるべき乗計算にも適用することができる。２ビットウィンドウ法で指数のｄｊビットまで処理した中間結果をＳｊとすると、Ｓｊの値も指数［ｄ（ｊ＋１），ｄｊ］の２ビットに依存して、上記と同じ値となる。この後、指数ｄ（ｊ−１）とｄ（ｊ−２）の２ビットの処理に移り、最初の２乗処理は、上記と同じ分岐となる。
【０１２４】
それに続く２乗処理では、
［ｄ（ｊ＋１），ｄｊ］＝［０，０］の場合には、1^2 mod nの計算が行われ、
［ｄ（ｊ＋１），ｄｊ］＝［１，０］の場合には、1^2 mod nの計算が行われ、
［ｄ（ｊ＋１），ｄｊ］＝［０，１］の場合には、(-1)^2 mod nの計算が行われ、
［ｄ（ｊ＋１），ｄｊ］＝［１，１］の場合には、(-1)^2 mod nの計算が行われる。
【０１２５】
この後、指数［ｄ（ｊ−１），ｄ（ｊ−２）］の値に依存して、
［０，０］の場合には、１×１の計算が行われ、
［０，１］の場合には、１×αの計算が行われ、
［１，０］の場合には、１×（−１）の計算が行われ、
［１，１］の場合には、１×（−α）の計算が行われる。
【０１２６】
このように、２回連続する２乗処理において、最初の２乗処理では４通り、次の２乗処理では２通りの処理が、［ｄ（ｊ＋１），ｄｊ］の値に依存して行われる。また、乗算処理では、４通りの処理が［ｄ（ｊ−１），ｄ（ｊ−２）］の値に依存して行われる。
【０１２７】
同様の攻撃は、位数２＾ｔの元を入力とした場合にも適用できる。
【０１２８】
以下、位数２＾ｔの元を入力とするＳＰＡを無効化できるようにした例について説明する。
【０１２９】
図７に、この場合のべき乗剰余演算の演算手順の一例を示す。
【０１３０】
まず、ステップＳ６０で、入力部１１は、べき乗剰余計算の底であるＭと、秘密のべき指数ｄ＝[d(m-1),..,di,..,d1,d0]_2と、法ｎとを入力する。
【０１３１】
ステップＳ６１で、前処理部１２は、Ｍに対して２乗剰余計算をｔ回繰り返し（M^(2^t) mod n）、その結果をＭ’とする。
【０１３２】
次に、上記のＭ’を底、入力されたｄのうち最下位ビットからｔビット分を除いた値（最上位ビットから最下位から（ｔ＋１）ビット目までの部分）ｄ’（ｄ’=[d/(2^t)]＝[d(m-1),..,dt]）をべき指数、入力されたｎを法として、それらが攻撃無効化処理部１からべき乗剰余計算部２へ与えられる。
【０１３３】
ステップＳ６２で、べき乗剰余計算部２は、それらをもとに、（右向き型の）べき乗剰余計算（M’^d’ mod n）を行い、その計算結果Ｓ１を求める。
【０１３４】
このＳ１は、べき乗剰余計算部２から攻撃無効化処理部１へ返される。
【０１３５】
ステップＳ６３で、後処理部１３は、入力されたＭを底、入力されたｄのうちＬＳＢからｔビット分を取り出した値（ｔビット目から最下位ビット目までの部分）ｄＬ＝[d(t-1),…,d0]をべき指数、入力されたｎを法として、べき乗剰余計算（M^dL mod n）を行い、その計算結果Ｓ２を求める。なお、このステップＳ６３のべき乗剰余計算は、右向き型でも左向き型でも任意のべき乗計算法を利用することができる。
【０１３６】
なお、ステップＳ６３のべき乗剰余計算は、べき乗剰余計算部２に実行させても良い。この場合、まず、入力されたＭを底、入力されたｄのうちＬＳＢからｔビット分を取り出した値ｄＬ＝[d(t-1),…,d0]をべき指数、入力されたｎを法として、それらが攻撃無効化処理部１からべき乗剰余計算部２へ与えられる。そして、べき乗剰余計算部２は、それらをもとに、べき乗剰余計算（M^dL mod n）を行い、その計算結果Ｓ２を求める。このＳ２は、べき乗剰余計算部２から攻撃無効化処理部１へ返される。
【０１３７】
ステップＳ６４で、後処理部１３は、Ｓ１とＳ２の２つの値を剰余乗算（Ｓ←S1×S2 mod n）して、最終結果Ｓを求める。
【０１３８】
ステップＳ６５で、出力部１４は、べき乗剰余演算結果S=M^d mod nを出力する。
【０１３９】
ここで、上記計算の正当性は、d=d’*(2^t)+dLと分解し、
S=M^d
=M^(d’*(2^t)+dL)
={(M^(2^t))^d’}×(M^dL)
=(M’^d’)×(M^dL) mod n
であることから確認できる。
【０１４０】
この計算手順では、ステップＳ６１での処理により、位数２＾ｔ’（ｔ’≦ｔ）なる入力に対してＭ’＝１となることから、このような入力を与えたとしても、ステップＳ６２の右向きべき乗計算では、処理の分岐は起こらない。このことから、位数２＾ｔ’なる入力を利用したＳＰＡを無効化することができる。
【０１４１】
なお、上記のステップＳ６２のべき乗剰余計算とステップＳ６３のべき乗剰余計算とは、上記とは逆の順番で実行しても構わない。
【０１４２】
また、ステップＳ６２，Ｓ６３のべき乗剰余計算をいずれもべき乗剰余計算部２に実行させる代わりに、例えば図８のようにべき乗剰余計算部２の他にべき乗剰余計算部３を備え、ステップＳ６２のべき乗剰余計算をべき乗剰余計算部２に実行させ、ステップＳ６３のべき乗剰余計算をべき乗剰余計算部３に実行させるようにしても良い。この場合に、ステップＳ６２のべき乗剰余計算とステップＳ６３のべき乗剰余計算とを同時に実行するようにしても良い。
【０１４３】
また、ステップＳ６２のべき乗剰余計算に必要な（Ｍ’，ｄ’，ｎ）と、ステップＳ６３のべき乗剰余計算に必要な（Ｍ，ｄＬ，ｎ）とは、攻撃無効化処理部１からべき乗剰余計算部２へ順次与えても良いし、同時に与えても良い。
【０１４４】
また、ステップＳ６２のべき乗剰余計算の結果Ｓ１と、ステップＳ６３のべき乗剰余計算の結果Ｓ２とは、べき乗剰余計算部２から攻撃無効化処理部１へ順次与えても良いし、同時に与えても良い。
【０１４５】
また、べき乗剰余計算部２と攻撃無効化処理部１との間でＳ１，Ｓ２をやり取りする方法としては、Ｓ１，Ｓ２をべき乗剰余計算部２と攻撃無効化処理部１とで共有する記憶領域に記憶しても良いし、べき乗剰余計算部２と攻撃無効化処理部１との間でＳ１，Ｓ２を転送しても良いし、べき乗剰余計算部２と攻撃無効化処理部１との間でＳ１，Ｓ２の記憶場所を示すポインタを転送しても良い。
【０１４６】
なお、本実施形態は、右向き型のバイナリ法にもモンゴメリ・ラダー法にも適用可能である。
【０１４７】
本発明によれば、（ｎ−１）の高次の根（位数２＾ｔの元）を入力として利用する攻撃も無効化することができる。
【０１４８】
（第３の実施形態）
本発明の第３の実施形態に係るべき乗剰余演算装置について説明する。
【０１４９】
ここで、対象とする選択入力型ＳＰＡは、（−１）入力と（ｘ，−ｘ）入力の２つの攻撃である。本対策演算は、入力集合を、正の数のグループＧｐと、負の数のグループＧｎとに等分して扱うことを、ポイントとする。入力ｘと−ｘは、一方がＧｐに属し、他方がＧｎに属する。また、（−１）はＧｎに属し、１はＧｐに属する。
【０１５０】
このように入力集合を分け、Ｇｐに属する入力に対しては、通常通りに、べき乗剰余計算を行い、Ｇｎに属する入力（−ｙ）に対しては、符号を反転してＧｐに属するｙを求めた上で、ｙに対してべき乗計算を行い、最後に、べき指数の奇数／偶数に応じて、符号の反転処理を行うか（奇数の場合）、あるいは、符号の反転処理を行わない（偶数の場合）。
【０１５１】
すなわち、
Ｓ=y^d
={(-1)*(-y)}^d
=(-1)^d×(-y)^d mod n
となる性質を利用する。
【０１５２】
このとき、（ｘ，−ｘ）入力ＳＰＡは、いずれの入力を与えてもべき乗部分は全く同じ計算が行われるために、無効化される。また、（−１）入力ＳＰＡも、符号反転されて１に対するべき乗が行われるために、特徴的な中間データの分岐が現れず、無効化される。
【０１５３】
図９に、この場合のべき乗剰余演算の演算手順の一例を示す。
【０１５４】
まず、ステップＳ７０で、入力部１１は、べき乗剰余計算の底であるＭと、秘密のべき指数ｄ＝[d(m-1),..,di,..,d1,d0]_2と、法ｎとを入力する。
【０１５５】
ステップＳ７１で、前処理部１２は、入力Ｍに対する符号ビットｓｇｎを求める。
【０１５６】
ここで、ｓｇｎ＝１ならば、入力Ｍは負の数のグループＧｎに属し、ｓｇｎ＝０ならば、Ｍは正の数のグループＧｐに属することを表すものとする。
【０１５７】
符号ビットの具体的な計算法としては、例えば次の２種類がある。
【０１５８】
第１の方法は、Ｇｐ＝{0,1,2,...,(n-1)/2}、Ｇｎ＝{(n+1)/2,(n+3)/2,…,n-2,n-1}とし、入力Ｍと（ｎ−１）／２との大小を比較するものである。Ｍ＞（ｎ−１）／２ならば、ｓｇｎ＝１、そうでなければ、ｓｇｎ＝０とする。
【０１５９】
第２の方法は、Ｇｐ＝｛ｘ｜ｘ＝０もしくはｘのＬＳＢ＝１｝、Ｇｎ＝｛ｘ｜ｘ≠０かつｘのＬＳＢ＝０｝と分けるものである。このグループ区分は、ｘ＝０を除いて、ｘと−ｘの両方のＬＳＢが０もしくは１に揃うことはなく、（ｎ−１）のＬＳＢ＝０である性質を利用している。この方法では、ｘ＝０の場合を除いて入力ｘのＬＳＢを反転した値を符号ｓｇｎとする。
【０１６０】
ステップＳ７２で、前処理部１２は、上記で求められた符号ｓｇｎ＝１ならば、ステップＳ７３に進んで、入力Ｍの符号を反転したＭ’の計算（M’←-M mod n）を行う。
【０１６１】
そして、上記のＭ’を底、入力されたｄをべき指数、入力されたｎを法として、それらが攻撃無効化処理部１からべき乗剰余計算部２へ与えられる。
【０１６２】
ステップＳ７４で、べき乗剰余計算部２は、それらをもとに、べき乗剰余計算（M’^d mod n）を行い、その計算結果Ｓを求める。
【０１６３】
このＳは、べき乗剰余計算部２から攻撃無効化処理部１へ返される。
【０１６４】
ステップＳ７５で、後処理部１３は、符号ビットの処理として（−１）＾ｄを求めて上記Ｓに掛ける計算（(-1)^d×S mod n）を行い、この計算結果で、Ｓを更新する。この（更新後の）Ｓが、最終的なべき乗剰余演算結果（M^d mod n）になる。
【０１６５】
一方、ステップＳ７２で、上記で求められた符号ｓｇｎ＝０ならば、前処理部１２はＭ’の計算は行わない。
【０１６６】
そして、入力されたＭを底、入力されたｄをべき指数、入力されたｎを法として、それらが攻撃無効化処理部１からべき乗剰余計算部２へ与えられる。
【０１６７】
ステップＳ７６で、べき乗剰余計算部２は、それらをもとに、べき乗剰余計算（M^d mod n）を行い、その計算結果Ｓを求める。このＳが、最終的なべき乗剰余演算結果（M^d mod n）になる。なお、符号ｓｇｎ＝０の場合、後処理部１３は、Ｓの更新演算は行わない。
【０１６８】
ステップ７７で、出力部１４は、べき乗剰余演算結果S=M^d mod nを出力する。
【０１６９】
なお、ステップＳ７３は、Ｍ’＝ｎ−Ｍの減算で計算でき、ステップＳ７５は、先に説明したようにｄが奇数の場合には、Ｓ＝ｎ−Ｓの減算を行い、そうでない場合には、何もせずにＳを出力すればよい。
【０１７０】
また、べき乗剰余計算部２と攻撃無効化処理部１との間でＳをやり取りする方法としては、Ｓをべき乗剰余計算部２と攻撃無効化処理部１とで共有する記憶領域に記憶しても良いし、べき乗剰余計算部２と攻撃無効化処理部１との間でＳを転送しても良いし、べき乗剰余計算部２と攻撃無効化処理部１との間でＳの記憶場所を示すポインタを転送しても良い。
【０１７１】
なお、本実施形態は、右向き型のバイナリ法にもモンゴメリ・ラダー法にも適用可能である。
【０１７２】
以上、第１〜第３の実施形態では、法ｎでのべき乗剰余計算を対象として計算方法を説明したが、法ｎが複数の素数の積である場合には、ｎを互いに素な因子に分解し、そのぞれの因子をモジュラスとしたべき乗剰余計算を行い、最後に複数の因子でのべき乗剰余計算結果を中国剰余定理により合成する演算が利用される場合が多い。この場合に、個々の因子でのべき乗剰余計算に各実施形態の計算手法を適用することができる。
【０１７３】
例えば、ＲＳＡ暗号における中国剰余定理を利用した復号演算に対する選択入力型ＳＰＡの対策計算法として、これらの算法を利用することができる。
【０１７４】
この場合、例えば、第１、第２又は第３の実施形態の乗剰余演算装置において、（法ｎが互いに素な複数の素数の積である場合に）法ｎを互いに素な因子に分解し、個々の因子を法として前記前処理部、前記暗号用演算部及び前記後処理部を用いてそれぞれ前記最終的な演算結果を求め、求めた複数の前記最終的な演算結果を中国剰余定理で合成する処理部を設ければ良い。
【０１７５】
＜楕円曲線上でのスカラー倍算＞
さて、ここに示した計算アルゴリズムは、楕円曲線上でのスカラー倍算にも適用できるものが多い。具体的には、第１、第２の実施形態として示した手法は、次のように利用すれば、楕円曲線上のスカラー倍算における選択入力型ＳＰＡに対して効果がある。
【０１７６】
まず、（ＲＳＡ暗号のような）有限体上のべき乗算M^d mod pと楕円曲線上のスカラー倍算dP（over E/Fq）とは、次のように対応している。すなわち、有限体（Z/pZ）上の乗法（a*b mod p）は、楕円曲線（E/Fq）上の加法（A+B over E/Fq）に対応し、有限体上の元のｄ乗は、楕円曲線上の元のｄ倍に対応する。
【０１７７】
第１の実施形態で考慮した攻撃は、有限体Ｆｑ上の楕円曲線の元が構成する有限可換群Ｅ（Ｆｑ）における位数２の元Ｐ＿２を入力とする攻撃と、元Ｙと元Ｐ＿２＋Ｙの２点を入力する攻撃に相当する。
【０１７８】
同様に、第２の実施形態で考慮した攻撃は、位数２＾ｔ（ｔ＞１）の元Ｐ＿｛２＾ｔ｝を入力とする攻撃に相当する。
【０１７９】
楕円曲線上での位数２の元Ｐ＿２は、２＊Ｐ＿２＝Ｏ（Ｏは無限遠点を表す）であり、位数２＾ｔの元Ｐ＿｛２＾ｔ｝は、（２＾ｔ）＊Ｐ＿｛２＾ｔ｝＝Ｏとなる元である。
【０１８０】
位数２の元Ｐ＿２を右向きスカラー倍算の入力点とすると、点２倍算の処理は、２＊Ｐ＿２（＝Ｏ）か２＊Ｏ（＝Ｏ）のどちらかの処理が、スカラー値のビットパターンに応じて繰り返される。位数２＾ｔの元を入力点とした場合にも、点２倍算の処理が２＾ｔ通りに限定され、それらがスカラー値の連続するｔビットの中間ビットパターンに依存して行われることから、ＳＰＡでのスカラー値の判別が容易となる。
【０１８１】
また、Ｙを任意の点として、点（Ｐ＿２＋Ｙ）を入力としてスカラー倍算を行った場合、２倍算の処理では、２＊（ｋＹ）（＝（２ｋ）＊Ｙ）もしくは２＊（ｋＹ＋Ｐ＿２）（＝（２ｋ）＊Ｙ）のどちらかが行われる。ここで、前者の計算が行われるのは、ｋが偶数のときであり、後者の計算が行われるのは、ｋが奇数のときとなる。右向き計算法の性質から、ｋは、それまでに処理したスカラー値のＭＳＢから中間ビットまでの値に相当することから、スカラー値の中間ビットの０／１に対応して、上記の２通りの計算が行われる。
【０１８２】
さらに、同じスカラー倍算においてＹを入力した場合には、２倍算において２＊（ｋＹ）の計算が行われることに着目すれば、点Ｙと点（Ｙ＋Ｐ＿２）とを入力した場合の電力波形の差分に着目すれば、スカラー値が推定できることが分る。
【０１８３】
以下、暗号用演算として楕円曲線上でのスカラー倍算が用いられた場合の暗号用演算装置の構成例について説明する。
【０１８４】
図１０に、図１を「楕円曲線上のスカラー倍算」用に記述した構成例を示す。
【０１８５】
第４，５の実施形態では、暗号用演算装置は「（楕円曲線上の）スカラー倍算装置」、暗号用演算部は「（楕円曲線上の）スカラー倍算部」と呼ぶ。
【０１８６】
（第４の実施形態）
最初に、第１の実施形態を楕円曲線暗号でのスカラー倍算に適用して攻撃を無効化できるようにした例について説明する。
【０１８７】
図１１に、この場合の楕円曲線上でのスカラー倍算の演算手順の一例を示す。
【０１８８】
この手順により、位数２の元Ｐ＿２入力ＳＰＡと（Ｙ，Ｐ＿２＋Ｙ）の２点入力ＳＰＡを無効化することができる。
【０１８９】
まず、ステップＳ８０で、入力部１１は、スカラー倍算の対象である点Ｐと、秘密のスカラー値ｄ＝[d(m-1),..,di,..,d1,d0]_2と、楕円曲線のドメインパラメータＥとを入力する。
【０１９０】
ここで、楕円曲線のドメインパラメータとは、楕円曲線の定義体や楕円曲線の係数、楕円曲線の位数やベースポイントなど、スカラー倍算を定義する楕円曲線のパラメータ群を指す。
【０１９１】
ステップＳ８１で、前処理部１２は、Ｐを２倍し（2*P）、その計算結果をＰ’とする。
【０１９２】
上記のＰ’をスカラー倍算の対象である点、入力されたｄのうち最下位ビットを除いたｄ’（ｄ’＝[d/2]）をスカラー値、入力されたＥを楕円曲線のドメインパラメータとして、それらが攻撃無効化処理部１からスカラー倍算部２へ与えられる。
【０１９３】
ステップＳ８２で、スカラー倍算部２は、それらをもとに、（右向き型の）スカラー倍算（d’*P’）を行い、その計算結果Ｑを求める。
【０１９４】
このＱは、スカラー倍算部２から攻撃無効化処理部１へ返される。
【０１９５】
ステップＳ８３で、後処理部１３は、入力されたｄの最下位ビット（ＬＳＢ）ｄ０が１かどうか調べ、ｄ０が１である場合には、ステップＳ８４に進んで、後処理部１３は、上記計算結果ＱとＰを点加算（Q+P）し、この計算結果で、Ｑを更新する。この（更新後の）Ｑが、最終的なスカラー倍算結果（d*P）になる。
【０１９６】
一方、ｄ０が０である場合には、ステップＳ８５に進んで、後処理部１３は、ダミー処理として、ステップＳ８４と同じ計算（Q+P）を行い、その結果は、本来の出力と異なる領域Ｑ’に保存する。この場合、スカラー倍算部２により求められたＱが、最終的なべき乗剰余演算結果（d*P）になる。
【０１９７】
ステップＳ８６で、出力部１４は、スカラー倍算結果Q= d*P を出力する。
【０１９８】
なお、スカラー倍算部２と攻撃無効化処理部１との間でＱをやり取りする方法としては、Ｑをスカラー倍算部２と攻撃無効化処理部１とで共有する記憶領域に記憶しても良いし、スカラー倍算部２と攻撃無効化処理部１との間でＱを転送しても良いし、スカラー倍算部２と攻撃無効化処理部１との間でＱの記憶場所を示すポインタを転送しても良い。
【０１９９】
なお、本実施形態は、右向き型のバイナリ法にもモンゴメリ・ラダー法にも適用可能である。
【０２００】
（第５の実施形態）
次に、第２の実施形態を楕円曲線暗号でのスカラー倍算に適用して攻撃を無効化できるようにした例について説明する。
【０２０１】
図１２に、この場合の楕円曲線上でのスカラー倍算の演算手順の一例を示す。
【０２０２】
まず、ステップＳ９０で、入力部１１は、スカラー倍算の対象である点Ｐと、秘密のスカラー値ｄ＝[d(m-1),..,di,..,d1,d0]_2と、楕円曲線のドメインパラメータＥとを入力する。
【０２０３】
ステップＳ９１で、前処理部１２は、点Ｐに対して点２倍算をｔ回繰り返し（(2^t)*P）、その計算結果をＰ’とする。
【０２０４】
次に、上記のＰ’をスカラー倍算の対象である点、入力されたｄの最下位ビットのうちｔビット分を除いた値（最上位ビットから最下位から（ｔ＋１）ビット目までの部分）ｄ’（ｄ’=[d/(2^t)] ＝[d(m-1),..,dt]）をスカラー値、入力されたＥを楕円曲線のドメインパラメータとして、それらが攻撃無効化処理部１からスカラー倍算部２へ与えられる。
【０２０５】
ステップＳ９２で、スカラー倍算部２は、それらをもとに、（右向き型の）スカラー倍算（d’*P’）を行い、その計算結果Ｑ１を求める。
【０２０６】
このＱ１は、スカラー倍算部２から攻撃無効化処理部１へ返される。
【０２０７】
ステップＳ９３で、後処理部１３は、入力されたＰをスカラー倍算の対象である点、入力されたｄのうちＬＳＢからｔビット分を取り出した値（ｔビット目から最下位ビット目までの部分）ｄＬ＝[d(t-1),…,d0]をスカラー値、入力されたＥを楕円曲線のドメインパラメータとして、スカラー倍算（dL*P）を行い、その計算結果Ｑ２を求める。なお、このステップＳ９３の計算は、右向き型でも左向き型でも任意のスカラー倍計算法を利用することができる。
【０２０８】
なお、ステップＳ９３のスカラー倍算は、スカラー倍算部２に実行させても良い。この場合、まず、入力されたＰをスカラー倍算の対象である点、入力されたｄのうちＬＳＢからｔビット分を取り出した値ｄＬ＝[d(t-1),…,d0]をスカラー値、入力されたＥを楕円曲線のドメインパラメータとして、それらが攻撃無効化処理部１からスカラー倍算部２へ与えられる。そして、スカラー倍算部２は、それらをもとに、（右向き型の）スカラー倍算（dL*P）を行い、その計算結果Ｑ２を求める。このＱ２は、スカラー倍算部２から攻撃無効化処理部１へ返される。
【０２０９】
ステップＳ９４で、後処理部１３は、Ｑ１とＱ２の２つの点を点加算して（Q1+Q2）、最終結果Ｑを求める。
【０２１０】
ステップＳ９５で、出力部１４は、スカラー倍算結果Q= d*P を出力する。
【０２１１】
ここで、上記計算の正当性は、d=d’*(2^t)+dLと分解し、
Ｑ=d*P
=(d’*(2^t)+dL)*P
={(d’*(2^t))*P}+(dL)*P
=d’*P’+(dL)*P
であることから確認できる。
【０２１２】
なお、上記のステップＳ９２のスカラー倍算とステップＳ９３のスカラー倍算とは、上記とは逆の順番で実行しても構わない。
【０２１３】
また、ステップＳ９２，Ｓ９３のスカラー倍算をいずれもスカラー倍算部２に実行させる代わりに、例えば図１３のようにスカラー倍算部２の他にスカラー倍算部３を備え、ステップＳ９２のスカラー倍算をスカラー倍算部２に実行させ、ステップＳ６３のスカラー倍算をスカラー倍算部３に実行させるようにしても良い。この場合に、ステップＳ９のスカラー倍算とステップＳ９３のスカラー倍算とを同時に実行するようにしても良い。
【０２１４】
また、ステップＳ９２のスカラー倍算に必要な（Ｐ’，ｄ’，Ｅ）と、ステップＳ９３のスカラー倍算に必要な（Ｐ，ｄＬ，Ｅ）とは、攻撃無効化処理部１からスカラー倍算部２へ順次与えても良いし、同時に与えても良い。
【０２１５】
また、ステップＳ９２のスカラー倍算の結果Ｑ１と、ステップＳ９３のスカラー倍算の結果Ｑ２とは、スカラー倍算部２から攻撃無効化処理部１へ順次与えても良いし、同時に与えても良い。
【０２１６】
また、スカラー倍算部２と攻撃無効化処理部１との間でＱ１，Ｑ２をやり取りする方法としては、Ｑ１，Ｑ２をスカラー倍算部２と攻撃無効化処理部１とで共有する記憶領域に記憶しても良いし、スカラー倍算部２と攻撃無効化処理部１との間でＱ１，Ｑ２を転送しても良いし、スカラー倍算部２と攻撃無効化処理部１との間でＱ１，Ｑ２の記憶場所を示すポインタを転送しても良い。
【０２１７】
なお、本実施形態は、右向き型のバイナリ法にもモンゴメリ・ラダー法にも適用可能である。
【０２１８】
なお、以上の各機能は、ソフトウェアとして記述し適当な機構をもったコンピュータに処理させても実現可能である。
また、本実施形態は、コンピュータに所定の手順を実行させるための、あるいはコンピュータを所定の手段として機能させるための、あるいはコンピュータに所定の機能を実現させるためのプログラムとして実施することもできる。加えて該プログラムを記録したコンピュータ読取り可能な記録媒体として実施することもできる。
【０２１９】
なお、本発明は上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組み合わせにより、種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。さらに、異なる実施形態にわたる構成要素を適宜組み合わせてもよい。
【図面の簡単な説明】
【０２２０】
【図１】本発明の実施形態に係る暗号用演算装置の構成例を示す図
【図２】同実施形態に係る暗号用演算装置の動作手順の一例を示すフローチャート
【図３】同実施形態に係るべき乗剰余計算を行う暗号用演算装置（べき乗剰余計算装置）の構成例を示す図
【図４】同実施形態におけるべき乗剰余計算の処理手順の第1の例を示すフローチャート
【図５】同実施形態におけるべき乗剰余計算の処理手順の第２の例を示すフローチャート
【図６】同実施形態におけるべき乗剰余計算の処理手順の第３の例を示すフローチャート
【図７】同実施形態におけるべき乗剰余計算の処理手順の第４の例を示すフローチャート
【図８】同実施形態に係るべき乗剰余計算を行う暗号用演算装置（べき乗剰余計算装置）の他の構成例を示す図
【図９】同実施形態におけるべき乗剰余計算手順の第５の例を示すフローチャート
【図１０】同実施形態に係る楕円曲線上のスカラー倍算を行う暗号用演算装置（スカラー倍算装置）の構成例を示す図
【図１１】同実施形態における楕円曲線上のスカラー倍算の処理手順の第1の例を示すフローチャート
【図１２】同実施形態における楕円曲線上のスカラー倍算の処理手順の第２の例を示すフローチャート
【図１３】同実施形態に係る楕円曲線上のスカラー倍算を行う暗号用演算装置（スカラー倍算装置）の他の構成例を示す図
【図１４】右向きバイナリ算法に対する（−１）入力ＳＰＡ攻撃について説明するための図
【図１５】右向きバイナリ算法に対する（ｘ、−ｘ）入力ＳＰＡ攻撃について説明するための図
【図１６】モンゴメリ・ラダー算法について説明するための図
【図１７】モンゴメリ・ラダー算法に対する（−１）入力ＳＰＡ攻撃について説明するための図
【図１８】モンゴメリ・ラダー算法に対する（ｘ、−ｘ）入力ＳＰＡ攻撃について説明するための図
【符号の説明】
【０２２１】
１…攻撃無効化処理部、２，３…暗号用演算部（べき乗剰余計算部、スカラー倍算部）、１１…入力部、１２…前処理部、１３…後処理部、１４…出力部
【技術分野】
【０００１】
本発明は、べき乗剰余計算や楕円曲線上のスカラー倍算などの暗号用演算を行う暗号用演算装置、暗号用演算方法及びプログラムに関する。
【背景技術】
【０００２】
ＩＣカードに代表される小規模なデバイスは、携帯可能で、情報セキュリティの核となる利用者の認証や、決済データの認証などに利用される。ＩＣカード上のＬＳＩに搭載されている暗号機能には一般に耐タンパー対策が施され、ＬＳＩ内部に記憶されている秘密鍵の漏洩が生じないように実装される。耐タンパー対策としては、ＬＳＩの消費電力の変動を観測して秘密鍵の推定を容易にする電力解析などのサイドチャネル攻撃に対しても、演算上の工夫により防御する手法が知られている。
【０００３】
ＲＳＡ暗号や楕円曲線暗号などの公開鍵暗号は、べき乗剰余演算あるいは楕円曲線上のスカラー倍算と呼ばれる基本演算を利用して構成される。これらの基本演算に対する電力解析攻撃の対策手法として、秘密鍵のパターンに依存せずに規則的に行う演算手法が、単純電力解析（ＳＰＡ(Simple Power Analysis)）と呼ばれる攻撃に有効であることが知られている。こうしたＳＰＡ攻撃に耐性のある、べき乗剰余演算（あるいはスカラー倍算）として、Add-and-Double-Always法（非特許文献１）や、モンゴメリ・ラダー法（非特許文献２）がある。
【０００４】
しかし、最近、従来のＳＰＡ耐性のあるべき乗剰余演算に対する新たな攻撃手法が見出されてきており、例えば、非特許文献３では、選択文書型のＳＰＡが示されている。特に、ＲＳＡ暗号や楕円曲線暗号におけるＳＰＡ対策として有名な、右向きバイナリ型のAdd-and-Double-Always演算手法に対し、モジュラスをｎとして、（ｎ−１）を入力に与える単純な手法で、従来のＳＰＡ対策が破られることが示されている。
【０００５】
また、発明者の検討により、モンゴメリ・ラダー法に対しても、Ｙｅｎらの（ｎ−１）入力型ＳＰＡによりＳＰＡ対策を無効化できることが判明した。
【０００６】
選択文書型のＳＰＡに対する汎用的で強力な対策に、入力メッセージに対してランダムなマスクをかけて演算を行うメッセージ・ブラインディング法の適用がある。しかし、同対策手法では、演算コストの小さくない逆元計算が必要であるという問題や、通常のべき乗計算に比べて２倍の演算コストがかかる場合があるという問題などがある。
【非特許文献１】J.S.Coron, ”Resistance against differential power analysis for elliptic curve”, CHES ’99.
【非特許文献２】M.Joye and S.-M. Yen, ”The Montgomery Powering Ladder”, CHES 2002.
【非特許文献３】S.-M. Yen et al., ”Power Analysis by Exploiting Chosen Message and Internal Collisions”, Mycrypt 2005.
【発明の開示】
【発明が解決しようとする課題】
【０００７】
ＲＳＡ暗号や楕円曲線暗号の実装モジュールにおいて、選択文書型のＳＰＡ攻撃により、従来の対策演算法が無効化されてしまうことが判明している。選択文書型の電力解析攻撃の中では、ある入力に対する暗号処理の１回の実行波形だけで秘密鍵の多くのビットパターンを推定可能とする（ｎ−１）入力型ＳＰＡや、その拡張攻撃が特に脅威となる。しかし、それら脅威に対する対策演算法は知られていない。
【０００８】
本発明は、上記事情を考慮してなされたもので、右向き型のバイナリべき乗算やモンゴメリ・ラダー算法における（ｎ−１）入力型ＳＰＡやその拡張攻撃手法に対する効率的な対策演算法を実現した暗号用演算装置、暗号用演算方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００９】
本発明は、２進数からなる秘密のパラメータの上位ビットから下位ビットに向けて計算を進める手順である右向き型演算手順を用いて、特定の暗号用演算を行う暗号用演算装置であって、前記暗号用演算の対象となるデータと、前記演算に用いる前記秘密のパラメータと、前記演算に用いる他のパラメータとを入力する入力部と、前記データに対して、特定の変換を施して、変換データを求める前処理部と、前記変換データと、前記秘密のパラメータの全部又は一部と、前記他のパラメータとを入力として、該秘密のパラメータの全部又は一部を用いた前記右向き型演算手順により、前記暗号用演算を行って、その演算結果を求める暗号用演算部と、前記暗号用演算部が求めた前記演算結果をもとにして、前記データと前記秘密のパラメータの全部と前記他のパラメータとを入力とした場合の前記暗号用演算の演算結果を求める後処理を行う後処理部と、前記暗号用演算部が求めた前記演算結果又は前記後処理部が求めた前記演算結果を、最終的な演算結果として出力する出力部とを備えたことを特徴とする。
【発明の効果】
【００１０】
本発明によれば、右向き型のバイナリべき乗算やモンゴメリ・ラダー算法における（ｎ−１）入力型ＳＰＡやその拡張攻撃手法に対する効率的な対策演算法を実現することができる。
【発明を実施するための最良の形態】
【００１１】
以下、図面を参照しながら本発明の実施形態について説明する。
【００１２】
まず、本実施形態に係る暗号用演算装置について説明するのに先立って、本実施形態において考慮する選択入力型ＳＰＡについて説明する。なお、以下で扱う暗号用演算は、べき乗剰余計算や楕円曲線上のスカラー倍算である。
【００１３】
べき乗剰余計算の計算手順として、大きく、右向き型演算手順（指数の上位ビットから下位ビットに向けて計算を進める演算手順）と、左向き型演算手順（指数の下位ビットから上位ビットに向けて計算を進める演算手順）とがある。これらのうち、本実施形態で考慮する選択入力型ＳＰＡが脅威となるのは、右向き型演算手順のべき乗剰余計算である。
【００１４】
右向き型べき乗剰余計算は、指数をｗ（複数）ビットずつまとめて処理を行うｗビットウィンドウ法に拡張できることや、演算途中の計算結果の記憶量が削減できる場合があることなどの利点があり、実装上利用される場面が多い。右向き型べき乗剰余計算法の具体例に、右向きバイナリ法とモンゴメリ・ラダー法とがある。
【００１５】
右向きバイナリ法は、そのままの実装では指数ビットによる剰余乗算の処理分岐があるため、通常のＳＰＡに弱く、ＳＰＡ対策を考慮してダミー処理を追加した手順が利用される場面が多い。以降の説明では、ＳＰＡ対策を考慮した右向きバイナリ法を例として非特許文献３で示された選択入力型ＳＰＡを説明する。
【００１６】
非特許文献３の選択入力型ＳＰＡは、１回もしくは２回のべき乗剰余計算の実行波形から、特定のビットを除くほぼ全ての指数ビットを推定可能とする、非常に脅威となる攻撃である。非特許文献３では、法ｎに対して、（ｎ−１）を入力とする（−１）入力ＳＰＡ、ｘと−ｘの１組を入力とする（ｘ，−ｘ）入力ＳＰＡの２種類が示されている。
【００１７】
まず、右向きバイナリ法に対して（−１）入力ＳＰＡを適用した場合について説明する。
【００１８】
図１４に、この場合における演算経過の一例を示す。
【００１９】
この場合、指数ビットを１ビット処理する度に２乗剰余処理と乗算剰余処理とが繰り返されるが、登場する演算パターンは、
１＊１ ｍｏｄ ｎ，
(-1)＊(-1) ｍｏｄ ｎ，
１＊(-1) ｍｏｄ ｎ
の３種類にすぎず、更に、２乗剰余処理部では、1*1 mod n又は(-1)*(-1) mod nのいずれかが実行される。
【００２０】
ここで、あるビットｄ（ｉ）における２乗剰余処理部の演算内容と、１つ前に処理したビットｄ（ｉ−１）の値との関係に着目すると、２乗剰余処理部で上記のいずれの演算が実行されるかは、１つ前に処理したビットｄ（ｉ−１）が０であるか又は１であるかに依存していることが分る。すなわち、あるビットｄ（ｉ）について２乗剰余処理部で1*1 mod n又は(-1)*(-1) mod nのいずれが実行されたかが分かれば、１つ前のビットｄ（ｉ−１）が０であるか又は１であるかが特定できることになる。
【００２１】
２乗剰余処理は規則的なタイミングで発生するため、ＳＰＡによりこの２種類の波形の区別さえできれば、指数ｄのＬＳＢを除く全てのビットパターンが判明する。
【００２２】
実際、この２種類の波形の区別が可能であることを実験により確認した結果も報告されており、（−１）入力ＳＰＡへの対策は必須となる。
【００２３】
この攻撃への対策として、入力が（−１）であるかどうかを検査し、もしそうであれば、指数のＬＳＢの０／１に応じて、べき乗剰余結果として（実際に演算を進めることなく）０／１を出力する方法で対処できる。しかし、非特許文献３では、（−１）入力ＳＰＡを拡張した（ｘ，−ｘ）入力ＳＰＡも提示されている。
【００２４】
次に、右向きバイナリ法に対して（ｘ，−ｘ）入力ＳＰＡを適用した場合について説明する。
【００２５】
図１５に、この場合の演算経過の一例を示す。
【００２６】
この場合、入力ｘでの演算経過と入力（−ｘ）での演算経過とを比較すると、乗算剰余処理部での（−ｘ）入力時の結果は、常に、ｘ入力時の演算結果に（−１）を乗じた値になっていることが分る。
【００２７】
従って、２乗剰余処理部に着目すると、ｘ入力時と（−ｘ）入力時とで全く同じ演算が行われるのは、１つ前に処理したビットｄ（ｉ−１）が０のときに限られ、この性質から、ＳＰＡで２乗剰余処理に着目して２波形を比較することにより、ＬＳＢを除く指数のビットパターンが判明することが分る。
【００２８】
次に、モンゴメリ・ラダー算法に対して（−１）入力ＳＰＡを適用した場合について説明する。
【００２９】
モンゴメリ・ラダー算法は次の通りである。
【００３０】
（１）べき指数ｄ＝[d(m-1),..,di,..,d1,d0]_2の上位ビットからｄｉまでを処理した中間結果として、（Ｌｉ，Ｒｉ）なる組が得られる。ここで、Ｄｉ＝[d/2^i]（ここで、［ｘ］はｘ以下の最大の整数を表す。）として、Ｌｉ＝M^Di (mod n)，Ｒｉ＝M^(Di+1) (mod n)である。初期値を（Ｌｍ，Ｒｍ）＝（Ｍ＾０，Ｍ＾１）＝（１，Ｍ）とする。
【００３１】
（２）着目する指数ビットｄ（ｉ−１）に応じて、図１６に示す計算を実行する。ここで、Ｌ０が最終結果を与える。
【００３２】
上記算法では、Ｌｉが本来の中間結果、Ｒｉが補助的な中間値である。指数部の差が１であることに注意して指数部に着目すると、必ず一方は奇数、他方は偶数になる。
【００３３】
（−１）を入力Ｍとして与えたとき、(-1)^(2k)=1，(-1)^(2k+1)=-1であり、ＬｉとＲｉは、指数の偶数・奇数に応じて、１か（−１）の組しかとり得ない。
【００３４】
従って、Ｌｉ，Ｒｉの計算時に登場するパターンも、
１＊１，
(-1)＊(-1)，
１＊(-1)，
(-1)＊１
の４種類のみであり、これらのパターンはＳＰＡでの判別が容易である。
【００３５】
これらのうち、(-1)*(-1)の計算が登場する場合に着目すると、Ｄ（ｉ＋１）が偶数でＤｉが奇数（すなわちd(i+1)=0かつdi=1）のケースと、Ｄ（ｉ＋１）が奇数でＤｉが偶数（すなわちd(i+1)=1かつdi=0）のケースとに限られる。このことは、べき指数の上位から順にＳＰＡで指数値を順次決定できることを表している。
【００３６】
図１７に、モンゴメリ・ラダー算法に対して（−１）入力ＳＰＡを適用した場合の演算経過の一例を示す。
【００３７】
図１７の例では、(-1)*(-1) mod nの計算は、指数ビットが下位から５番目、３番目、１番目の計算においてであり、これらのビットが一つ上位のビットと０／１が反転した関係になっていることを利用して、ＬＳＢを除く全てのビットを推定できる。
【００３８】
次に、モンゴメリ・ラダー算法に対して（ｘ，−ｘ）入力ＳＰＡを適用した場合について説明する。
【００３９】
図１８に、この場合における演算経過の一例を示す。
【００４０】
この場合、モンゴメリ・ラダー算法での中間レジスタに記憶される値の指数に着目すると、必ず一方は奇数、他方は偶数になることから、（−ｘ）入力時には、L*R mod nの計算結果は必ず-x^y mod nとなる。
【００４１】
従って、R←L*R mod nとL←L*R mod nの演算結果を、ｘ入力時の同じタイミングでの演算と比較すると、必ず符号反転した結果となる。
【００４２】
指数ビットとして０もしくは１が連続した場合には、それぞれL←L*L mod n、R←R*R mod nの計算が繰り返され、その場合に限って、ｘ入力時の演算と全く同じ演算が同じタイミングで出現することが分る。
【００４３】
この性質から、ＳＰＡでｘ入力時と（−ｘ）入力時との２波形の差分を解析することにより、指数のビットパターンが判明することが分る。
【００４４】
以上で説明したように、ＳＰＡに対して耐性があると考えられてきた右向きバイナリ型算法やモンゴメリ・ラダー算法において、（−１）入力ＳＰＡや（ｘ，−ｘ）入力ＳＰＡにより秘密指数のパターンが判明する可能性が高いことが明らかとなった。
【００４５】
以下、本実施形態では、これらの選択入力型ＳＰＡに対する耐性を備えた本実施形態に係る暗号用演算装置について説明する。
【００４６】
図１に、本実施形態の暗号用演算装置の構成例を示す。
【００４７】
図１に示されるように、本実施形態の暗号用演算装置は、攻撃無効化処理部１と暗号用演算部２とを備えている。
【００４８】
暗号用演算部２は、既存の所定の暗号用演算を行う。所定の暗号用演算は、例えば、べき乗剰余計算や楕円曲線上のスカラー倍算である。
【００４９】
攻撃無効化処理部１は、上記選択文書型ＳＰＡ攻撃に対する耐性を暗号用演算装置に付与するために、該攻撃を無効化するための処理を行う。
【００５０】
攻撃無効化処理部１は、入力部１１、前処理部１２、後処理部１３、出力部１４を備えている。
【００５１】
攻撃無効化処理部１と暗号用演算部２とをハードウェアにより構成するかソフトウェアにより構成するかについては、例えば次のようなバリエーションがある。
（１）攻撃無効化処理部１と暗号用演算部２とをすべてハードウェアにより構成する。
（２）攻撃無効化処理部１と暗号用演算部２とをすべてソフトウェアにより構成する。
（３）攻撃無効化処理部１をソフトウェア（ファームウェア）により構成し、暗号用演算部２をハードウェアにより構成する。
【００５２】
なお、暗号用演算部２は、既存のもので構わないので、既存の暗号用演算部２に、新たに攻撃無効化処理部１を追加して、本実施形態の暗号用演算装置を実現することが可能である。
【００５３】
図２に、本実施形態の暗号用演算装置の動作手順の一例を示す。
【００５４】
ステップＳ１で、入力部１１は、当該暗号用演算の対象となるデータ（べき乗剰余計算の場合のメッセージＭ、楕円曲線上のスカラー倍算の場合のＰ）、該演算に用いる秘密のパラメータｄ＝[d(m-1),..,di,..,d1,d0]_2（ただし、[]_2は２進数展開を意味する）、該演算に用いるその他のパラメータを入力する。
【００５５】
なお、所定の暗号用演算が、べき乗剰余計算である場合、ｄは、（秘密の）指数であり、その他のパラメータには、べき乗剰余計算の法ｎが該当する。また、所定の暗号用演算が、楕円曲線上のスカラー倍算である場合、ｄは、（秘密の）スカラー値であり、その他のパラメータには、楕円曲線ドメインパラメータＥが該当する。
【００５６】
なお、入力部１１は、それらデータを、どのような方法で入力するものであっても良い。例えば、入力デバイスや通信デバイスやメモリデバイスなどから入力しても良いし、他のプロセスから入力しても良い。
【００５７】
ステップＳ２で、前処理部１２は、（暗号用演算部２に対する）上記攻撃を無効化するために、演算対象となるデータに対して所定の変換を施して変換データを生成する処理を含む前処理を行う。より具体的には後述するが、演算対象となるデータの変換については、所定の暗号用演算が、べき乗剰余計算である場合に、例えば、M’←M^2 mod nなどを行い、所定の暗号用演算が、楕円曲線上のスカラー倍算である場合に、例えば、P’←2*Pなどを行う。生成された変換データ（例えば、Ｍ’やＰ’）は、暗号用演算部２に与えられる。
【００５８】
また、より具体的には後述するが、入力されたｄの全部又は一部のビット（例えば、最下位ビットを除いたｄ’＝[d(m-1),..,di,..,d1]_2）が暗号用演算部２に与えられる。また、入力された、その他のパラメータが、暗号用演算部２に与えられる。更に、それら以外の情報が暗号用演算部２に与えられる場合もある。
【００５９】
ステップＳ３で、暗号用演算部２は、与えられた、生成された変換データ（例えば、Ｍ’やＰ’）と、秘密のパラメータｄ’の全部又は一部のビットと、その他のパラメータとを入力として、当該所定の暗号用演算を行う。
【００６０】
なお、この暗号用演算部２により得られる演算結果は、求めるべき最終的な演算結果ではない（あるいは、条件に応じて、最終的な演算結果になることもある）。
【００６１】
ステップＳ４で、後処理部１３は、暗号用演算部２の計算結果をもとに、最終的な演算結果を生成する。より具体的には後述するが、所定の暗号用演算が、べき乗剰余計算である場合に、例えば、S←S*M mod n（暗号用演算部２の計算結果に更にMを乗算）などを行い、所定の暗号用演算が、楕円曲線上のスカラー倍算である場合に、例えば、Q←Q+P（暗号用演算部２の計算結果に更にPを加算）などを行う。なお、その際、より具体的には後述するが、所定の暗号用演算によっては、攻撃を無効化するために、ダミー演算を行うことがある。
【００６２】
ステップＳ５で、出力部１４は、後処理部１３により得られた計算結果（条件に応じて、暗号用演算部２により得られた計算結果）を出力する。例えば、所定の暗号用演算が、べき乗剰余計算である場合に、Ｓ＝M^ｄ mod nを出力し、所定の暗号用演算が、楕円曲線上のスカラー倍算である場合に、Q=d*Pを出力する。
【００６３】
なお、出力部１４は、最終的な計算結果を、どのような方法で出力するものであっても良い。例えば、出力デバイスや通信デバイスやメモリデバイスなどへ出力しても良いし、他のプロセスへ出力しても良い。
【００６４】
以下、暗号用演算装置のより具体的な構成例について説明する。
【００６５】
以下説明する第1〜第３の実施形態は、暗号用演算として、べき乗剰余計算を例にとったものであり、第４，５の実施形態は、暗号用演算として、楕円曲線上でのスカラー倍算を例にとったものである。
【００６６】
＜べき乗剰余演算＞
図３に、図１を「べき乗剰余計算」用に記述した構成例を示す。
【００６７】
第1〜第３の実施形態では、暗号用演算装置は「べき乗剰余計算装置」、暗号用演算部は「べき乗剰余計算部」と呼ぶ。
【００６８】
（第１の実施形態）
本発明の第１の実施形態に係るべき乗剰余演算装置について説明する。本実施形態では、べき乗剰余演算の３つの演算手順例を示す。
【００６９】
最初に、右向きバイナリ型算法によるべき乗剰余演算に対する、（−１）入力ＳＰＡ攻撃と（ｘ，−ｘ）入力ＳＰＡ攻撃を無効化できるようにした例について説明する。
【００７０】
図４に、この場合のべき乗剰余演算の演算手順の一例を示す。
【００７１】
まず、ステップＳ１０で、入力部１１は、べき乗剰余計算の底であるメッセージＭと、秘密のべき指数ｄ＝[d(m-1),..,di,..,d1,d0]_2と、法ｎとを入力する。
【００７２】
ステップＳ１１で、前処理部１２は、Ｍを２乗剰余計算（M^2 mod n）し、その計算結果をＭ’とする。
【００７３】
上記のＭ’を底、入力されたｄのうち最下位ビットを除いたｄ’（ｄ’＝[d/2]）をべき指数、入力されたｎを法として、それらが攻撃無効化処理部１からべき乗剰余計算部２へ与えられる。
【００７４】
ステップＳ１２で、べき乗剰余計算部２は、それらをもとに、（右向き型の）べき乗剰余計算（M’^d’ mod n）を行い、その計算結果Ｓを求める。
【００７５】
このＳは、べき乗剰余計算部２から攻撃無効化処理部１へ返される。
【００７６】
ステップＳ１３で、後処理部１３は、入力されたｄの最下位ビット（ＬＳＢ）ｄ０が１かどうか調べ、ｄ０が１である場合には、ステップＳ１４に進んで、後処理部１３は、上記計算結果ＳとＭを法ｎで乗算剰余計算（S*M mod n）し、この計算結果で、Ｓを更新する。この（更新後の）Ｓが、最終的なべき乗剰余演算結果（M^d mod n）になる。
【００７７】
一方、ｄ０が０である場合には、ステップＳ１５に進んで、後処理部１３は、ダミー処理として、ステップＳ１４と同じ計算（S*M mod n）を行い、その結果は、本来の出力と異なる領域Ｓ’に保存する。この場合、べき乗剰余計算部２により求められたＳが、最終的なべき乗剰余演算結果（M^d mod n）になる。
【００７８】
ステップＳ１６で、出力部１４は、べき乗剰余演算結果S=M^d mod nを出力する。
【００７９】
なお、上記演算手順例において、ステップＳ１５のダミー処理は、べき指数ｄのＬＳＢの０／１の判別をタイミング攻撃により防ぐ目的で追加しているが、暗号の演算では、べき指数のＬＳＢは１であることが、暗号アルゴリズムの性質から事前に判明している場合もある。よって、べき指数のＬＳＢの０／１の判別をサイドチャネル攻撃から防御する必要がない場合には、ステップＳ１５のダミー処理は省略しても良い。
【００８０】
また、べき乗剰余計算部２と攻撃無効化処理部１との間でＳをやり取りする方法としては、Ｓをべき乗剰余計算部２と攻撃無効化処理部１とで共有する記憶領域に記憶しても良いし、べき乗剰余計算部２と攻撃無効化処理部１との間でＳを転送しても良いし、べき乗剰余計算部２と攻撃無効化処理部１との間でＳの記憶場所を示すポインタを転送しても良い。
【００８１】
さて、この計算手順例によれば、ステップＳ１１により得られるＭ’は、ｘ入力時と−ｘ入力時で常にｘ＾２となる。従って、ステップＳ１２でのべき乗計算時には、ｘと−ｘのいずれの入力でも常に同じ演算が行われ、ステップＳ１３以降の処理で符号により異なる処理が行われる。このため、（ｘ、−ｘ）入力ＳＰＡで指数ビットが判明する可能性があるのは、指数ｄのＬＳＢのみであり、それ以外のビットは、判別することが不可能になる。また、（−１）入力ＳＰＡでも、同様の性質から、指数ｄのＬＳＢを除く指数ビットが保護できる。
【００８２】
次に、モンゴメリ・ラダー算法によるべき乗剰余演算に対する、（−１）入力ＳＰＡ攻撃と（ｘ，−ｘ）入力ＳＰＡ攻撃を無効化できるようにした例について説明する。
【００８３】
図５に、この場合のべき乗剰余演算の演算手順の一例を示す。
【００８４】
まず、ステップＳ２０で、入力部１１は、べき乗剰余計算の底であるＭと、秘密のべき指数ｄ＝[d(m-1),..,di,..,d1,d0]_2と、法ｎとを入力する。
【００８５】
ステップＳ２１で、前処理部１２は、Ｍを２乗剰余計算し、その計算結果（M^2 mod n）をＭ’とする。
【００８６】
上記のＭ’を底、入力されたｄをべき指数、入力されたｎを法として、それらが攻撃無効化処理部１からべき乗剰余計算部２へ与えられる。
【００８７】
ステップＳ２２で、べき乗剰余計算部２は、参照する指数ビットを表すインデックスｉをｍにセットし、中間レジスタＬに１をセットし、中間レジスタＲに、与えられたＭ’をセットする。
【００８８】
以降、ステップＳ２３からステップＳ２７までの処理ループで、べき乗剰余計算部２は、指数ビットｄ（ｍ−１）からｄ１までのべき指数に対応したべき乗計算を行う。
【００８９】
ステップＳ２３で、インデックスｉをデクリメントし、ステップＳ２４で、ｉが０より大きいかどうか調べる。
【００９０】
ｉが０より大きい場合には、ステップＳ２５で、指数ビットｄｉが１であるかどうか調べ、ｄｉが１ならば、ステップＳ２６に進んで、L←L*R mod nとR←R*R mod nの計算を行い、ｄｉが０ならば、ステップＳ２７に進んで、R←L*R mod nとL←L*L mod nの計算を行う。そして、ステップＳ２３に戻って、次の処理ループに移る。
【００９１】
以上の処理ループが繰り返された結果、ステップＳ２３でｉ＝０になると、ステップＳ２４で、ｉが０より大きくないので、この処理ループを抜けて、ステップＳ２８へ分岐することになる。
【００９２】
ここで、べき乗剰余計算部２による計算は終了となり、このときの（Ｒ，Ｌ）が、べき乗剰余計算部２から攻撃無効化処理部１へ返される。
【００９３】
ステップＳ２８で、後処理部１３が、入力されたｄの最下位ビット（ＬＳＢ）ｄ０が１かどうか調べ、ｄ０が１である場合には、ステップＳ２９に進んで、後処理部１３が、上記計算結果ＬとＭを法ｎで乗算剰余計算（L*M mod n）し、この計算結果で、Ｌを更新する。この（更新後の）Ｌが、最終的なべき乗剰余演算結果（M^d mod n）になる。
【００９４】
一方、ｄ０が０である場合には、ステップＳ３０に進んで、後処理部１３が、ダミー処理として、ステップＳ２９と同じ計算（L*M mod n）を行い、その結果は、本来の出力と異なる領域Ｒ（他の領域でも構わない。）に保存する。この場合、べき乗剰余計算部２により求められたLが、最終的なべき乗剰余演算結果（M^d mod n）になる。
【００９５】
ステップＳ３１で、出力部１４が、べき乗剰余演算結果L =M^d mod nを出力する。
【００９６】
なお、べき乗剰余計算部２と攻撃無効化処理部１との間でＬをやり取りする方法としては、Ｌをべき乗剰余計算部２と攻撃無効化処理部１とで共有する記憶領域に記憶しても良いし、べき乗剰余計算部２と攻撃無効化処理部１との間でＬを転送しても良いし、べき乗剰余計算部２と攻撃無効化処理部１との間でＬの記憶場所を示すポインタを転送しても良い。なお、Ｌをべき乗剰余計算部２と攻撃無効化処理部１とで共有する記憶領域に記憶する場合に、Ｒもべき乗剰余計算部２と攻撃無効化処理部１とで共有する記憶領域に記憶しても良い。
【００９７】
また、上記では、攻撃無効化処理部１からべき乗剰余計算部２へ、ｄ＝[d(m-1),..,di,..,d1,d0]_2を与えたが、その代わりに、ｄのうち最下位ビットを除いたｄ’（ｄ’＝[d/2]）を与えるようにしても良い（この場合、ステップＳ２２でｉ＝ｍ−１となり、ステップＳ２４でｉが負になったら処理ループを抜けるようになれば良い）。
【００９８】
次に、右向きバイナリ型算法によるべき乗剰余演算に対する、（−１）入力ＳＰＡ攻撃と（ｘ，−ｘ）入力ＳＰＡ攻撃を無効化できるようにした例について説明する。
【００９９】
図６に、この場合のべき乗剰余演算の演算手順の一例を示す。
【０１００】
まず、ステップＳ４０で、入力部１１は、べき乗剰余計算の底であるＭと、秘密のべき指数ｄ＝[d(m-1),..,di,..,d1,d0]_2と、法ｎとを入力する。
【０１０１】
ステップＳ４１で、前処理部１２は、Ｍを２乗剰余計算（M^2 mod n）し、その計算結果をＭ’とする。
【０１０２】
上記のＭ’を底、入力されたｄをべき指数、入力されたｎを法として、それらが攻撃無効化処理部１からべき乗剰余計算部２へ与えられる。
【０１０３】
ステップＳ４２で、べき乗剰余計算部２は、参照する指数ビットを表すインデックスｉをｍにセットし、中間レジスタＳに１をセットする。
【０１０４】
以降、ステップＳ４３からステップＳ４８までの処理ループで、べき乗剰余計算部２は、指数ビットｄ（ｍ−１）からｄ１までのべき指数に対応したべき乗計算を行う。
【０１０５】
ステップＳ４３で、インデックスｉをデクリメントし、ステップＳ４４で、ｉが０より大きいかどうか調べる。
【０１０６】
ｉが０より大きい場合には、ステップＳ４５に進んで、Ｓを２乗剰余計算（S^2 mod n）し、その計算結果でＳを更新した後に、ステップＳ４６で、指数ビットｄｉが１であるかどうか調べ、ｄｉが１ならば、ステップＳ４７に進んで、S←S*M’ mod nの計算を行い、ｄｉが０ならば、ステップＳ４８に進んで、ダミー処理として、S’←S*M’ mod nの計算を行う。ここで、Ｓ’はダミー処理の結果を保存するレジスタである。そして、ステップＳ４３に戻って、次の処理ループに移る。
【０１０７】
以上の処理ループが繰り返された結果、ステップＳ４３でｉ＝０になると、ステップＳ４４で、ｉが０より大きくないので、この処理ループを抜けて、ステップＳ４９へ分岐することになる。
【０１０８】
ここで、べき乗剰余計算部２による計算は終了となり、このときのＳが、べき乗剰余計算部２から攻撃無効化処理部１へ返される。
【０１０９】
ステップＳ４９で、後処理部１３は、入力されたｄの最下位ビット（ＬＳＢ）ｄ０が１かどうか調べ、ｄ０が１である場合には、ステップＳ５０に進んで、後処理部１３は、上記計算結果ＳとＭを法ｎで乗算剰余計算（S*M mod n）し、この計算結果で、Ｓを更新する。この（更新後の）Ｓが、最終的なべき乗剰余演算結果（M^d mod n）になる。
【０１１０】
一方、ｄ０が０である場合には、ステップＳ５１に進んで、後処理部１３は、ダミー処理として、ステップＳ５０と同じ計算（S*M mod n）を行い、その結果は、本来の出力と異なる領域Ｓ’に保存する。この場合、べき乗剰余計算部２により求められたＳが、最終的なべき乗剰余演算結果（M^d mod n）になる。
【０１１１】
ステップＳ５２で、出力部１４は、べき乗剰余演算結果S=M^d mod nを出力する。
【０１１２】
なお、べき乗剰余計算部２と攻撃無効化処理部１との間でＳをやり取りする方法としては、Ｓをべき乗剰余計算部２と攻撃無効化処理部１とで共有する記憶領域に記憶しても良いし、べき乗剰余計算部２と攻撃無効化処理部１との間でＳを転送しても良いし、べき乗剰余計算部２と攻撃無効化処理部１との間でＳの記憶場所を示すポインタを転送しても良い。なお、Ｓをべき乗剰余計算部２と攻撃無効化処理部１とで共有する記憶領域に記憶する場合に、Ｓ’もべき乗剰余計算部２と攻撃無効化処理部１とで共有する記憶領域に記憶しても良い。
【０１１３】
また、上記では、攻撃無効化処理部１からべき乗剰余計算部２へ、ｄ＝[d(m-1),..,di,..,d1,d0]_2を与えたが、その代わりに、ｄのうち最下位ビットを除いたｄ’（ｄ’＝[d/2]）を与えるようにしても良い（この場合、ステップＳ３２でｉ＝ｍ−１となり、ステップＳ３４でｉが負になったら処理ループを抜けるようになれば良い）。
【０１１４】
本発明によれば、ＲＳＡ暗号や楕円曲線暗号に対する選択入力型ＳＰＡで脅威となる（ｎ−１）攻撃を無効化することができる。また、本対策による演算手法での処理量の増加はほとんどない。さらに、（ｎ−１）攻撃の拡張として、入力ｘと−ｘの１組を与え、それぞれの電力波形の差分を解析して内部状態の差異から秘密指数を推定する攻撃も無効化することができる。
【０１１５】
（第２の実施形態）
本発明の第２の実施形態に係るべき乗剰余演算装置について説明する。
【０１１６】
ここでは、（−１）入力ＳＰＡを拡張した攻撃とその対策について説明する。
【０１１７】
（−１）は乗法に関する単位元である１の平方根（位数２）である。べき乗の右向きバイナリ計算法で、入力をＭとし、指数ｄ＝[d(m-1),..,dj,..,d1,d0]_2の最上位からｄｊまでを処理した中間値をＳｊとする。Ｄｊ＝[d(m-1),…,dj]_2とおくと、Ｓｊ＝M^Dj mod nである。従って、Ｍとして位数２の値である（−１）を入力すると、Ｄｊの最下位ビットであるｄｊの０／１に依存して、Ｓｊ＝１（dj=0のとき）、Ｓｊ＝−１（dj=1のとき）となる。この後、指数ｄ（ｊ−１）ビットの処理に移り、最初にSj^2 mod nの計算が行われ、この処理がｄｊの値に依存した２通りしかないことが、攻撃に利用されている。
【０１１８】
この原理を拡張すると、位数２＾ｔ（ｔは１以上の整数）の元を入力とする攻撃が考えられる。位数２＾ｔの元は、乗法群の位数λ（元の個数）に依存して存在する場合と存在しない場合とがある。実際に、λ mod 2^tが０となる場合には、位数２＾ｔの元が存在し、λが判明している場合には、多項式時間のアルゴリズムで求めることができる。
【０１１９】
例えば、位数２＾２＝４の元αをべき乗の右向きバイナリ計算法に入力すると、指数ｄの最上位からｄｊビットまでを処理した中間値Ｓｊ(=M^Dj mod n)は、Dj mod (2^2)の値（すなわち、ｄ（ｊ＋１）とｄｊの２ビット）に依存して決まる。すなわち、
［ｄ（ｊ＋１），ｄｊ］＝［０，０］のとき、Ｓｊ＝１、
［ｄ（ｊ＋１），ｄｊ］＝［０，１］のとき、Ｓｊ＝α、
［ｄ（ｊ＋１），ｄｊ］＝［１，０］のとき、Ｓｊ＝α＾２＝−１、
［ｄ（ｊ＋１），ｄｊ］＝［１，１］のとき、Ｓｊ＝α＾３＝−α
となる。
【０１２０】
次に、隣のｄ（ｊ−１）ビットの処理に移り、最初の２乗処理では、
［ｄ（ｊ＋１），ｄｊ］＝［０，０］の場合には、1^2 mod n=1の計算が行われ、
［ｄ（ｊ＋１），ｄｊ］＝［０，１］の場合には、α^2 mod n=-1の計算が行われ、
［ｄ（ｊ＋１），ｄｊ］＝［１，０］の場合には、(-1)^2 mod n=1の計算が行われ、
［ｄ（ｊ＋１），ｄｊ］＝［１，１］の場合には、(-α)^2=-1の計算が行われる。
【０１２１】
また、その次の乗算では、
［ｄ（ｊ＋１），ｄｊ］＝［０，０］の場合には、1×α mod nの計算が行われ、
［ｄ（ｊ＋１），ｄｊ］＝［１，０］の場合には、1×α mod nの計算が行われ、
［ｄ（ｊ＋１），ｄｊ］＝［０，１］の場合には、(-1)×α mod nの計算が行われ、
［ｄ（ｊ＋１），ｄｊ］＝［１，１］の場合には、(-1)×α mod nの計算が行われる。
【０１２２】
このように、２乗処理部では４通り、乗算処理部では２通りの計算しか現れず、これらの計算は、指数ビット[d(j+1),dj]の２ビットに依存して、パターンが分かれることから、ＳＰＡによって攻撃が容易となる可能性が高い。
【０１２３】
この位数４の元αを利用したＳＰＡは、ｗビットウィンドウ法（例えば、２ビットウィンドウ法）によるべき乗計算にも適用することができる。２ビットウィンドウ法で指数のｄｊビットまで処理した中間結果をＳｊとすると、Ｓｊの値も指数［ｄ（ｊ＋１），ｄｊ］の２ビットに依存して、上記と同じ値となる。この後、指数ｄ（ｊ−１）とｄ（ｊ−２）の２ビットの処理に移り、最初の２乗処理は、上記と同じ分岐となる。
【０１２４】
それに続く２乗処理では、
［ｄ（ｊ＋１），ｄｊ］＝［０，０］の場合には、1^2 mod nの計算が行われ、
［ｄ（ｊ＋１），ｄｊ］＝［１，０］の場合には、1^2 mod nの計算が行われ、
［ｄ（ｊ＋１），ｄｊ］＝［０，１］の場合には、(-1)^2 mod nの計算が行われ、
［ｄ（ｊ＋１），ｄｊ］＝［１，１］の場合には、(-1)^2 mod nの計算が行われる。
【０１２５】
この後、指数［ｄ（ｊ−１），ｄ（ｊ−２）］の値に依存して、
［０，０］の場合には、１×１の計算が行われ、
［０，１］の場合には、１×αの計算が行われ、
［１，０］の場合には、１×（−１）の計算が行われ、
［１，１］の場合には、１×（−α）の計算が行われる。
【０１２６】
このように、２回連続する２乗処理において、最初の２乗処理では４通り、次の２乗処理では２通りの処理が、［ｄ（ｊ＋１），ｄｊ］の値に依存して行われる。また、乗算処理では、４通りの処理が［ｄ（ｊ−１），ｄ（ｊ−２）］の値に依存して行われる。
【０１２７】
同様の攻撃は、位数２＾ｔの元を入力とした場合にも適用できる。
【０１２８】
以下、位数２＾ｔの元を入力とするＳＰＡを無効化できるようにした例について説明する。
【０１２９】
図７に、この場合のべき乗剰余演算の演算手順の一例を示す。
【０１３０】
まず、ステップＳ６０で、入力部１１は、べき乗剰余計算の底であるＭと、秘密のべき指数ｄ＝[d(m-1),..,di,..,d1,d0]_2と、法ｎとを入力する。
【０１３１】
ステップＳ６１で、前処理部１２は、Ｍに対して２乗剰余計算をｔ回繰り返し（M^(2^t) mod n）、その結果をＭ’とする。
【０１３２】
次に、上記のＭ’を底、入力されたｄのうち最下位ビットからｔビット分を除いた値（最上位ビットから最下位から（ｔ＋１）ビット目までの部分）ｄ’（ｄ’=[d/(2^t)]＝[d(m-1),..,dt]）をべき指数、入力されたｎを法として、それらが攻撃無効化処理部１からべき乗剰余計算部２へ与えられる。
【０１３３】
ステップＳ６２で、べき乗剰余計算部２は、それらをもとに、（右向き型の）べき乗剰余計算（M’^d’ mod n）を行い、その計算結果Ｓ１を求める。
【０１３４】
このＳ１は、べき乗剰余計算部２から攻撃無効化処理部１へ返される。
【０１３５】
ステップＳ６３で、後処理部１３は、入力されたＭを底、入力されたｄのうちＬＳＢからｔビット分を取り出した値（ｔビット目から最下位ビット目までの部分）ｄＬ＝[d(t-1),…,d0]をべき指数、入力されたｎを法として、べき乗剰余計算（M^dL mod n）を行い、その計算結果Ｓ２を求める。なお、このステップＳ６３のべき乗剰余計算は、右向き型でも左向き型でも任意のべき乗計算法を利用することができる。
【０１３６】
なお、ステップＳ６３のべき乗剰余計算は、べき乗剰余計算部２に実行させても良い。この場合、まず、入力されたＭを底、入力されたｄのうちＬＳＢからｔビット分を取り出した値ｄＬ＝[d(t-1),…,d0]をべき指数、入力されたｎを法として、それらが攻撃無効化処理部１からべき乗剰余計算部２へ与えられる。そして、べき乗剰余計算部２は、それらをもとに、べき乗剰余計算（M^dL mod n）を行い、その計算結果Ｓ２を求める。このＳ２は、べき乗剰余計算部２から攻撃無効化処理部１へ返される。
【０１３７】
ステップＳ６４で、後処理部１３は、Ｓ１とＳ２の２つの値を剰余乗算（Ｓ←S1×S2 mod n）して、最終結果Ｓを求める。
【０１３８】
ステップＳ６５で、出力部１４は、べき乗剰余演算結果S=M^d mod nを出力する。
【０１３９】
ここで、上記計算の正当性は、d=d’*(2^t)+dLと分解し、
S=M^d
=M^(d’*(2^t)+dL)
={(M^(2^t))^d’}×(M^dL)
=(M’^d’)×(M^dL) mod n
であることから確認できる。
【０１４０】
この計算手順では、ステップＳ６１での処理により、位数２＾ｔ’（ｔ’≦ｔ）なる入力に対してＭ’＝１となることから、このような入力を与えたとしても、ステップＳ６２の右向きべき乗計算では、処理の分岐は起こらない。このことから、位数２＾ｔ’なる入力を利用したＳＰＡを無効化することができる。
【０１４１】
なお、上記のステップＳ６２のべき乗剰余計算とステップＳ６３のべき乗剰余計算とは、上記とは逆の順番で実行しても構わない。
【０１４２】
また、ステップＳ６２，Ｓ６３のべき乗剰余計算をいずれもべき乗剰余計算部２に実行させる代わりに、例えば図８のようにべき乗剰余計算部２の他にべき乗剰余計算部３を備え、ステップＳ６２のべき乗剰余計算をべき乗剰余計算部２に実行させ、ステップＳ６３のべき乗剰余計算をべき乗剰余計算部３に実行させるようにしても良い。この場合に、ステップＳ６２のべき乗剰余計算とステップＳ６３のべき乗剰余計算とを同時に実行するようにしても良い。
【０１４３】
また、ステップＳ６２のべき乗剰余計算に必要な（Ｍ’，ｄ’，ｎ）と、ステップＳ６３のべき乗剰余計算に必要な（Ｍ，ｄＬ，ｎ）とは、攻撃無効化処理部１からべき乗剰余計算部２へ順次与えても良いし、同時に与えても良い。
【０１４４】
また、ステップＳ６２のべき乗剰余計算の結果Ｓ１と、ステップＳ６３のべき乗剰余計算の結果Ｓ２とは、べき乗剰余計算部２から攻撃無効化処理部１へ順次与えても良いし、同時に与えても良い。
【０１４５】
また、べき乗剰余計算部２と攻撃無効化処理部１との間でＳ１，Ｓ２をやり取りする方法としては、Ｓ１，Ｓ２をべき乗剰余計算部２と攻撃無効化処理部１とで共有する記憶領域に記憶しても良いし、べき乗剰余計算部２と攻撃無効化処理部１との間でＳ１，Ｓ２を転送しても良いし、べき乗剰余計算部２と攻撃無効化処理部１との間でＳ１，Ｓ２の記憶場所を示すポインタを転送しても良い。
【０１４６】
なお、本実施形態は、右向き型のバイナリ法にもモンゴメリ・ラダー法にも適用可能である。
【０１４７】
本発明によれば、（ｎ−１）の高次の根（位数２＾ｔの元）を入力として利用する攻撃も無効化することができる。
【０１４８】
（第３の実施形態）
本発明の第３の実施形態に係るべき乗剰余演算装置について説明する。
【０１４９】
ここで、対象とする選択入力型ＳＰＡは、（−１）入力と（ｘ，−ｘ）入力の２つの攻撃である。本対策演算は、入力集合を、正の数のグループＧｐと、負の数のグループＧｎとに等分して扱うことを、ポイントとする。入力ｘと−ｘは、一方がＧｐに属し、他方がＧｎに属する。また、（−１）はＧｎに属し、１はＧｐに属する。
【０１５０】
このように入力集合を分け、Ｇｐに属する入力に対しては、通常通りに、べき乗剰余計算を行い、Ｇｎに属する入力（−ｙ）に対しては、符号を反転してＧｐに属するｙを求めた上で、ｙに対してべき乗計算を行い、最後に、べき指数の奇数／偶数に応じて、符号の反転処理を行うか（奇数の場合）、あるいは、符号の反転処理を行わない（偶数の場合）。
【０１５１】
すなわち、
Ｓ=y^d
={(-1)*(-y)}^d
=(-1)^d×(-y)^d mod n
となる性質を利用する。
【０１５２】
このとき、（ｘ，−ｘ）入力ＳＰＡは、いずれの入力を与えてもべき乗部分は全く同じ計算が行われるために、無効化される。また、（−１）入力ＳＰＡも、符号反転されて１に対するべき乗が行われるために、特徴的な中間データの分岐が現れず、無効化される。
【０１５３】
図９に、この場合のべき乗剰余演算の演算手順の一例を示す。
【０１５４】
まず、ステップＳ７０で、入力部１１は、べき乗剰余計算の底であるＭと、秘密のべき指数ｄ＝[d(m-1),..,di,..,d1,d0]_2と、法ｎとを入力する。
【０１５５】
ステップＳ７１で、前処理部１２は、入力Ｍに対する符号ビットｓｇｎを求める。
【０１５６】
ここで、ｓｇｎ＝１ならば、入力Ｍは負の数のグループＧｎに属し、ｓｇｎ＝０ならば、Ｍは正の数のグループＧｐに属することを表すものとする。
【０１５７】
符号ビットの具体的な計算法としては、例えば次の２種類がある。
【０１５８】
第１の方法は、Ｇｐ＝{0,1,2,...,(n-1)/2}、Ｇｎ＝{(n+1)/2,(n+3)/2,…,n-2,n-1}とし、入力Ｍと（ｎ−１）／２との大小を比較するものである。Ｍ＞（ｎ−１）／２ならば、ｓｇｎ＝１、そうでなければ、ｓｇｎ＝０とする。
【０１５９】
第２の方法は、Ｇｐ＝｛ｘ｜ｘ＝０もしくはｘのＬＳＢ＝１｝、Ｇｎ＝｛ｘ｜ｘ≠０かつｘのＬＳＢ＝０｝と分けるものである。このグループ区分は、ｘ＝０を除いて、ｘと−ｘの両方のＬＳＢが０もしくは１に揃うことはなく、（ｎ−１）のＬＳＢ＝０である性質を利用している。この方法では、ｘ＝０の場合を除いて入力ｘのＬＳＢを反転した値を符号ｓｇｎとする。
【０１６０】
ステップＳ７２で、前処理部１２は、上記で求められた符号ｓｇｎ＝１ならば、ステップＳ７３に進んで、入力Ｍの符号を反転したＭ’の計算（M’←-M mod n）を行う。
【０１６１】
そして、上記のＭ’を底、入力されたｄをべき指数、入力されたｎを法として、それらが攻撃無効化処理部１からべき乗剰余計算部２へ与えられる。
【０１６２】
ステップＳ７４で、べき乗剰余計算部２は、それらをもとに、べき乗剰余計算（M’^d mod n）を行い、その計算結果Ｓを求める。
【０１６３】
このＳは、べき乗剰余計算部２から攻撃無効化処理部１へ返される。
【０１６４】
ステップＳ７５で、後処理部１３は、符号ビットの処理として（−１）＾ｄを求めて上記Ｓに掛ける計算（(-1)^d×S mod n）を行い、この計算結果で、Ｓを更新する。この（更新後の）Ｓが、最終的なべき乗剰余演算結果（M^d mod n）になる。
【０１６５】
一方、ステップＳ７２で、上記で求められた符号ｓｇｎ＝０ならば、前処理部１２はＭ’の計算は行わない。
【０１６６】
そして、入力されたＭを底、入力されたｄをべき指数、入力されたｎを法として、それらが攻撃無効化処理部１からべき乗剰余計算部２へ与えられる。
【０１６７】
ステップＳ７６で、べき乗剰余計算部２は、それらをもとに、べき乗剰余計算（M^d mod n）を行い、その計算結果Ｓを求める。このＳが、最終的なべき乗剰余演算結果（M^d mod n）になる。なお、符号ｓｇｎ＝０の場合、後処理部１３は、Ｓの更新演算は行わない。
【０１６８】
ステップ７７で、出力部１４は、べき乗剰余演算結果S=M^d mod nを出力する。
【０１６９】
なお、ステップＳ７３は、Ｍ’＝ｎ−Ｍの減算で計算でき、ステップＳ７５は、先に説明したようにｄが奇数の場合には、Ｓ＝ｎ−Ｓの減算を行い、そうでない場合には、何もせずにＳを出力すればよい。
【０１７０】
また、べき乗剰余計算部２と攻撃無効化処理部１との間でＳをやり取りする方法としては、Ｓをべき乗剰余計算部２と攻撃無効化処理部１とで共有する記憶領域に記憶しても良いし、べき乗剰余計算部２と攻撃無効化処理部１との間でＳを転送しても良いし、べき乗剰余計算部２と攻撃無効化処理部１との間でＳの記憶場所を示すポインタを転送しても良い。
【０１７１】
なお、本実施形態は、右向き型のバイナリ法にもモンゴメリ・ラダー法にも適用可能である。
【０１７２】
以上、第１〜第３の実施形態では、法ｎでのべき乗剰余計算を対象として計算方法を説明したが、法ｎが複数の素数の積である場合には、ｎを互いに素な因子に分解し、そのぞれの因子をモジュラスとしたべき乗剰余計算を行い、最後に複数の因子でのべき乗剰余計算結果を中国剰余定理により合成する演算が利用される場合が多い。この場合に、個々の因子でのべき乗剰余計算に各実施形態の計算手法を適用することができる。
【０１７３】
例えば、ＲＳＡ暗号における中国剰余定理を利用した復号演算に対する選択入力型ＳＰＡの対策計算法として、これらの算法を利用することができる。
【０１７４】
この場合、例えば、第１、第２又は第３の実施形態の乗剰余演算装置において、（法ｎが互いに素な複数の素数の積である場合に）法ｎを互いに素な因子に分解し、個々の因子を法として前記前処理部、前記暗号用演算部及び前記後処理部を用いてそれぞれ前記最終的な演算結果を求め、求めた複数の前記最終的な演算結果を中国剰余定理で合成する処理部を設ければ良い。
【０１７５】
＜楕円曲線上でのスカラー倍算＞
さて、ここに示した計算アルゴリズムは、楕円曲線上でのスカラー倍算にも適用できるものが多い。具体的には、第１、第２の実施形態として示した手法は、次のように利用すれば、楕円曲線上のスカラー倍算における選択入力型ＳＰＡに対して効果がある。
【０１７６】
まず、（ＲＳＡ暗号のような）有限体上のべき乗算M^d mod pと楕円曲線上のスカラー倍算dP（over E/Fq）とは、次のように対応している。すなわち、有限体（Z/pZ）上の乗法（a*b mod p）は、楕円曲線（E/Fq）上の加法（A+B over E/Fq）に対応し、有限体上の元のｄ乗は、楕円曲線上の元のｄ倍に対応する。
【０１７７】
第１の実施形態で考慮した攻撃は、有限体Ｆｑ上の楕円曲線の元が構成する有限可換群Ｅ（Ｆｑ）における位数２の元Ｐ＿２を入力とする攻撃と、元Ｙと元Ｐ＿２＋Ｙの２点を入力する攻撃に相当する。
【０１７８】
同様に、第２の実施形態で考慮した攻撃は、位数２＾ｔ（ｔ＞１）の元Ｐ＿｛２＾ｔ｝を入力とする攻撃に相当する。
【０１７９】
楕円曲線上での位数２の元Ｐ＿２は、２＊Ｐ＿２＝Ｏ（Ｏは無限遠点を表す）であり、位数２＾ｔの元Ｐ＿｛２＾ｔ｝は、（２＾ｔ）＊Ｐ＿｛２＾ｔ｝＝Ｏとなる元である。
【０１８０】
位数２の元Ｐ＿２を右向きスカラー倍算の入力点とすると、点２倍算の処理は、２＊Ｐ＿２（＝Ｏ）か２＊Ｏ（＝Ｏ）のどちらかの処理が、スカラー値のビットパターンに応じて繰り返される。位数２＾ｔの元を入力点とした場合にも、点２倍算の処理が２＾ｔ通りに限定され、それらがスカラー値の連続するｔビットの中間ビットパターンに依存して行われることから、ＳＰＡでのスカラー値の判別が容易となる。
【０１８１】
また、Ｙを任意の点として、点（Ｐ＿２＋Ｙ）を入力としてスカラー倍算を行った場合、２倍算の処理では、２＊（ｋＹ）（＝（２ｋ）＊Ｙ）もしくは２＊（ｋＹ＋Ｐ＿２）（＝（２ｋ）＊Ｙ）のどちらかが行われる。ここで、前者の計算が行われるのは、ｋが偶数のときであり、後者の計算が行われるのは、ｋが奇数のときとなる。右向き計算法の性質から、ｋは、それまでに処理したスカラー値のＭＳＢから中間ビットまでの値に相当することから、スカラー値の中間ビットの０／１に対応して、上記の２通りの計算が行われる。
【０１８２】
さらに、同じスカラー倍算においてＹを入力した場合には、２倍算において２＊（ｋＹ）の計算が行われることに着目すれば、点Ｙと点（Ｙ＋Ｐ＿２）とを入力した場合の電力波形の差分に着目すれば、スカラー値が推定できることが分る。
【０１８３】
以下、暗号用演算として楕円曲線上でのスカラー倍算が用いられた場合の暗号用演算装置の構成例について説明する。
【０１８４】
図１０に、図１を「楕円曲線上のスカラー倍算」用に記述した構成例を示す。
【０１８５】
第４，５の実施形態では、暗号用演算装置は「（楕円曲線上の）スカラー倍算装置」、暗号用演算部は「（楕円曲線上の）スカラー倍算部」と呼ぶ。
【０１８６】
（第４の実施形態）
最初に、第１の実施形態を楕円曲線暗号でのスカラー倍算に適用して攻撃を無効化できるようにした例について説明する。
【０１８７】
図１１に、この場合の楕円曲線上でのスカラー倍算の演算手順の一例を示す。
【０１８８】
この手順により、位数２の元Ｐ＿２入力ＳＰＡと（Ｙ，Ｐ＿２＋Ｙ）の２点入力ＳＰＡを無効化することができる。
【０１８９】
まず、ステップＳ８０で、入力部１１は、スカラー倍算の対象である点Ｐと、秘密のスカラー値ｄ＝[d(m-1),..,di,..,d1,d0]_2と、楕円曲線のドメインパラメータＥとを入力する。
【０１９０】
ここで、楕円曲線のドメインパラメータとは、楕円曲線の定義体や楕円曲線の係数、楕円曲線の位数やベースポイントなど、スカラー倍算を定義する楕円曲線のパラメータ群を指す。
【０１９１】
ステップＳ８１で、前処理部１２は、Ｐを２倍し（2*P）、その計算結果をＰ’とする。
【０１９２】
上記のＰ’をスカラー倍算の対象である点、入力されたｄのうち最下位ビットを除いたｄ’（ｄ’＝[d/2]）をスカラー値、入力されたＥを楕円曲線のドメインパラメータとして、それらが攻撃無効化処理部１からスカラー倍算部２へ与えられる。
【０１９３】
ステップＳ８２で、スカラー倍算部２は、それらをもとに、（右向き型の）スカラー倍算（d’*P’）を行い、その計算結果Ｑを求める。
【０１９４】
このＱは、スカラー倍算部２から攻撃無効化処理部１へ返される。
【０１９５】
ステップＳ８３で、後処理部１３は、入力されたｄの最下位ビット（ＬＳＢ）ｄ０が１かどうか調べ、ｄ０が１である場合には、ステップＳ８４に進んで、後処理部１３は、上記計算結果ＱとＰを点加算（Q+P）し、この計算結果で、Ｑを更新する。この（更新後の）Ｑが、最終的なスカラー倍算結果（d*P）になる。
【０１９６】
一方、ｄ０が０である場合には、ステップＳ８５に進んで、後処理部１３は、ダミー処理として、ステップＳ８４と同じ計算（Q+P）を行い、その結果は、本来の出力と異なる領域Ｑ’に保存する。この場合、スカラー倍算部２により求められたＱが、最終的なべき乗剰余演算結果（d*P）になる。
【０１９７】
ステップＳ８６で、出力部１４は、スカラー倍算結果Q= d*P を出力する。
【０１９８】
なお、スカラー倍算部２と攻撃無効化処理部１との間でＱをやり取りする方法としては、Ｑをスカラー倍算部２と攻撃無効化処理部１とで共有する記憶領域に記憶しても良いし、スカラー倍算部２と攻撃無効化処理部１との間でＱを転送しても良いし、スカラー倍算部２と攻撃無効化処理部１との間でＱの記憶場所を示すポインタを転送しても良い。
【０１９９】
なお、本実施形態は、右向き型のバイナリ法にもモンゴメリ・ラダー法にも適用可能である。
【０２００】
（第５の実施形態）
次に、第２の実施形態を楕円曲線暗号でのスカラー倍算に適用して攻撃を無効化できるようにした例について説明する。
【０２０１】
図１２に、この場合の楕円曲線上でのスカラー倍算の演算手順の一例を示す。
【０２０２】
まず、ステップＳ９０で、入力部１１は、スカラー倍算の対象である点Ｐと、秘密のスカラー値ｄ＝[d(m-1),..,di,..,d1,d0]_2と、楕円曲線のドメインパラメータＥとを入力する。
【０２０３】
ステップＳ９１で、前処理部１２は、点Ｐに対して点２倍算をｔ回繰り返し（(2^t)*P）、その計算結果をＰ’とする。
【０２０４】
次に、上記のＰ’をスカラー倍算の対象である点、入力されたｄの最下位ビットのうちｔビット分を除いた値（最上位ビットから最下位から（ｔ＋１）ビット目までの部分）ｄ’（ｄ’=[d/(2^t)] ＝[d(m-1),..,dt]）をスカラー値、入力されたＥを楕円曲線のドメインパラメータとして、それらが攻撃無効化処理部１からスカラー倍算部２へ与えられる。
【０２０５】
ステップＳ９２で、スカラー倍算部２は、それらをもとに、（右向き型の）スカラー倍算（d’*P’）を行い、その計算結果Ｑ１を求める。
【０２０６】
このＱ１は、スカラー倍算部２から攻撃無効化処理部１へ返される。
【０２０７】
ステップＳ９３で、後処理部１３は、入力されたＰをスカラー倍算の対象である点、入力されたｄのうちＬＳＢからｔビット分を取り出した値（ｔビット目から最下位ビット目までの部分）ｄＬ＝[d(t-1),…,d0]をスカラー値、入力されたＥを楕円曲線のドメインパラメータとして、スカラー倍算（dL*P）を行い、その計算結果Ｑ２を求める。なお、このステップＳ９３の計算は、右向き型でも左向き型でも任意のスカラー倍計算法を利用することができる。
【０２０８】
なお、ステップＳ９３のスカラー倍算は、スカラー倍算部２に実行させても良い。この場合、まず、入力されたＰをスカラー倍算の対象である点、入力されたｄのうちＬＳＢからｔビット分を取り出した値ｄＬ＝[d(t-1),…,d0]をスカラー値、入力されたＥを楕円曲線のドメインパラメータとして、それらが攻撃無効化処理部１からスカラー倍算部２へ与えられる。そして、スカラー倍算部２は、それらをもとに、（右向き型の）スカラー倍算（dL*P）を行い、その計算結果Ｑ２を求める。このＱ２は、スカラー倍算部２から攻撃無効化処理部１へ返される。
【０２０９】
ステップＳ９４で、後処理部１３は、Ｑ１とＱ２の２つの点を点加算して（Q1+Q2）、最終結果Ｑを求める。
【０２１０】
ステップＳ９５で、出力部１４は、スカラー倍算結果Q= d*P を出力する。
【０２１１】
ここで、上記計算の正当性は、d=d’*(2^t)+dLと分解し、
Ｑ=d*P
=(d’*(2^t)+dL)*P
={(d’*(2^t))*P}+(dL)*P
=d’*P’+(dL)*P
であることから確認できる。
【０２１２】
なお、上記のステップＳ９２のスカラー倍算とステップＳ９３のスカラー倍算とは、上記とは逆の順番で実行しても構わない。
【０２１３】
また、ステップＳ９２，Ｓ９３のスカラー倍算をいずれもスカラー倍算部２に実行させる代わりに、例えば図１３のようにスカラー倍算部２の他にスカラー倍算部３を備え、ステップＳ９２のスカラー倍算をスカラー倍算部２に実行させ、ステップＳ６３のスカラー倍算をスカラー倍算部３に実行させるようにしても良い。この場合に、ステップＳ９のスカラー倍算とステップＳ９３のスカラー倍算とを同時に実行するようにしても良い。
【０２１４】
また、ステップＳ９２のスカラー倍算に必要な（Ｐ’，ｄ’，Ｅ）と、ステップＳ９３のスカラー倍算に必要な（Ｐ，ｄＬ，Ｅ）とは、攻撃無効化処理部１からスカラー倍算部２へ順次与えても良いし、同時に与えても良い。
【０２１５】
また、ステップＳ９２のスカラー倍算の結果Ｑ１と、ステップＳ９３のスカラー倍算の結果Ｑ２とは、スカラー倍算部２から攻撃無効化処理部１へ順次与えても良いし、同時に与えても良い。
【０２１６】
また、スカラー倍算部２と攻撃無効化処理部１との間でＱ１，Ｑ２をやり取りする方法としては、Ｑ１，Ｑ２をスカラー倍算部２と攻撃無効化処理部１とで共有する記憶領域に記憶しても良いし、スカラー倍算部２と攻撃無効化処理部１との間でＱ１，Ｑ２を転送しても良いし、スカラー倍算部２と攻撃無効化処理部１との間でＱ１，Ｑ２の記憶場所を示すポインタを転送しても良い。
【０２１７】
なお、本実施形態は、右向き型のバイナリ法にもモンゴメリ・ラダー法にも適用可能である。
【０２１８】
なお、以上の各機能は、ソフトウェアとして記述し適当な機構をもったコンピュータに処理させても実現可能である。
また、本実施形態は、コンピュータに所定の手順を実行させるための、あるいはコンピュータを所定の手段として機能させるための、あるいはコンピュータに所定の機能を実現させるためのプログラムとして実施することもできる。加えて該プログラムを記録したコンピュータ読取り可能な記録媒体として実施することもできる。
【０２１９】
なお、本発明は上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組み合わせにより、種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。さらに、異なる実施形態にわたる構成要素を適宜組み合わせてもよい。
【図面の簡単な説明】
【０２２０】
【図１】本発明の実施形態に係る暗号用演算装置の構成例を示す図
【図２】同実施形態に係る暗号用演算装置の動作手順の一例を示すフローチャート
【図３】同実施形態に係るべき乗剰余計算を行う暗号用演算装置（べき乗剰余計算装置）の構成例を示す図
【図４】同実施形態におけるべき乗剰余計算の処理手順の第1の例を示すフローチャート
【図５】同実施形態におけるべき乗剰余計算の処理手順の第２の例を示すフローチャート
【図６】同実施形態におけるべき乗剰余計算の処理手順の第３の例を示すフローチャート
【図７】同実施形態におけるべき乗剰余計算の処理手順の第４の例を示すフローチャート
【図８】同実施形態に係るべき乗剰余計算を行う暗号用演算装置（べき乗剰余計算装置）の他の構成例を示す図
【図９】同実施形態におけるべき乗剰余計算手順の第５の例を示すフローチャート
【図１０】同実施形態に係る楕円曲線上のスカラー倍算を行う暗号用演算装置（スカラー倍算装置）の構成例を示す図
【図１１】同実施形態における楕円曲線上のスカラー倍算の処理手順の第1の例を示すフローチャート
【図１２】同実施形態における楕円曲線上のスカラー倍算の処理手順の第２の例を示すフローチャート
【図１３】同実施形態に係る楕円曲線上のスカラー倍算を行う暗号用演算装置（スカラー倍算装置）の他の構成例を示す図
【図１４】右向きバイナリ算法に対する（−１）入力ＳＰＡ攻撃について説明するための図
【図１５】右向きバイナリ算法に対する（ｘ、−ｘ）入力ＳＰＡ攻撃について説明するための図
【図１６】モンゴメリ・ラダー算法について説明するための図
【図１７】モンゴメリ・ラダー算法に対する（−１）入力ＳＰＡ攻撃について説明するための図
【図１８】モンゴメリ・ラダー算法に対する（ｘ、−ｘ）入力ＳＰＡ攻撃について説明するための図
【符号の説明】
【０２２１】
１…攻撃無効化処理部、２，３…暗号用演算部（べき乗剰余計算部、スカラー倍算部）、１１…入力部、１２…前処理部、１３…後処理部、１４…出力部
【特許請求の範囲】
【請求項１】
２進数からなる秘密のパラメータの上位ビットから下位ビットに向けて計算を進める手順である右向き型演算手順を用いて、特定の暗号用演算を行う暗号用演算装置であって、
前記暗号用演算の対象となるデータと、前記演算に用いる前記秘密のパラメータと、前記演算に用いる他のパラメータとを入力する入力部と、
前記データに対して、特定の変換を施して、変換データを求める前処理部と、
前記変換データと、前記秘密のパラメータの全部又は一部と、前記他のパラメータとを入力として、該秘密のパラメータの全部又は一部を用いた前記右向き型演算手順により、前記暗号用演算を行って、その演算結果を求める暗号用演算部と、
前記暗号用演算部が求めた前記演算結果をもとにして、前記データと前記秘密のパラメータの全部と前記他のパラメータとを入力とした場合の前記暗号用演算の演算結果を求める後処理を行う後処理部と、
前記暗号用演算部が求めた前記演算結果又は前記後処理部が求めた前記演算結果を、最終的な演算結果として出力する出力部とを備えたことを特徴とする暗号用演算装置。
【請求項２】
前記所定の暗号用演算は、べき乗剰余計算であり、
前記データは、べき乗剰余計算の底であるメッセージＭであり、
前記秘密のパラメータは、べき指数ｄであり、
前記他のパラメータは、法ｎであり、
前記最終的な演算結果は、べき乗剰余計算結果Ｍ＾ｄ ｍｏｄ ｎであることを特徴とする請求項１に記載の暗号用演算装置。
【請求項３】
前記前処理部は、法ｎの下で、前記メッセージＭを２乗して、前記変換データを求め、
前記暗号用演算部は、前記変換データを演算対象とし、法ｎの下で、前記べき指数ｄのうち最下位ビットを除いたものに基づく前記右向き型演算手順により、べき乗剰余計算を行い、
前記後処理部は、前記べき指数ｄの最下位ビットが１である場合には、法ｎの下で、前記暗号用演算部の演算結果と前記メッセージＭとの乗算剰余計算を行って、前記最終的な演算結果を求めることを特徴とする請求項２に記載の暗号用演算装置。
【請求項４】
前記後処理部は、前記べき指数ｄの最下位ビットが０である場合には、ダミー計算として、前記べき指数ｄの最下位ビットが１である場合と同一の演算を行い、
前記暗号用演算部の演算結果を、前記最終的な演算結果とすることを特徴とする請求項３に記載の暗号用演算装置。
【請求項５】
前記前処理部は、法ｎの下で、前記メッセージＭに対して２乗演算をｔ回繰り返して、前記変換データを求め、
前記暗号用演算部は、前記変換データを演算対象とし、法ｎの下で、前記べき指数ｄのうち最下位ビットからｔビット分を除いたものに基づく前記右向き型演算手順により、第１のべき乗剰余計算を行って、第１の演算結果を求め、
前記後処理部は、前記メッセージＭを演算対象とし、法ｎの下で、前記べき指数ｄのうち最下位ビットからｔビット分を取り出したものに基づく任意の演算手順により、第２のべき乗剰余計算を行って、第２の演算結果を求め、
前記後処理部は、法ｎの下で、第１の演算結果と第２の演算結果との乗算剰余計算を行って、前記最終的な演算結果を求めることを特徴とする請求項２に記載の暗号用演算装置。
【請求項６】
前記後処理部が第２のべき乗剰余計算を行って前記第２の演算結果を求める代わりに、前記暗号用演算部又は前記暗号用演算部とは別に設けられた暗号用演算部が第２のべき乗剰余計算を行って前記第２の演算結果を求めることを特徴とする請求項５に記載の暗号用演算装置。
【請求項７】
前記前処理部は、入力メッセージの空間を正のメッセージ空間と負のメッセージ空間とに２分して定義した際に、前記メッセージＭが正のメッセージ空間に属するか又は負のメッセージ空間に属するかを調べ、前記メッセージＭが負のメッセージ空間に属する場合には、法ｎの下で、前記メッセージＭの符号を反転して、前記変換データを求め、
前記暗号用演算部は、前記メッセージＭが負のメッセージ空間に属する場合には、前記変換データを演算対象とし、法ｎの下で、前記べき指数ｄに基づく前記右向き型演算手順により、べき乗剰余計算を行い、前記メッセージＭが正のメッセージ空間に属する場合には、前記メッセージＭを演算対象とし、法ｎの下で、前記べき指数ｄに基づく前記右向き型演算手順により、べき乗剰余計算を行い、
前記後処理部は、前記メッセージＭが負のメッセージ空間に属する場合には、法ｎの下で、（−１）＾ｄと前記暗号用演算部の演算結果との乗算剰余計算を行って、前記最終的な演算結果を求めることを特徴とする請求項２に記載の暗号用演算装置。
【請求項８】
前記データＭが正のメッセージ空間に属する場合には、前記暗号用演算部の演算結果を、前記最終的な演算結果とすることを特徴とする請求項２に記載の暗号用演算装置。
【請求項９】
法ｎが互いに素な複数の素数の積である場合に、法ｎを互いに素な因子に分解し、個々の因子を法として前記前処理部、前記暗号用演算部及び前記後処理部を用いてそれぞれ前記最終的な演算結果を求め、求めた複数の前記最終的な演算結果を中国剰余定理で合成する手段を更に備えたことを特徴とする請求項１ないし８のいずれか１項に記載の暗号用演算装置。
【請求項１０】
前記所定の暗号用演算は、楕円曲線上のスカラー倍算であり、
前記データは、スカラー倍算の対象である点Ｐであり、
前記秘密のパラメータは、秘密のスカラー値ｄであり、
前記他のパラメータは、楕円曲線のドメインパラメータＥであり、
前記最終的な演算結果は、楕円曲線上のスカラー倍算結果ｄ＊Ｐであることを特徴とする請求項１に記載の暗号用演算装置。
【請求項１１】
前記前処理部は、楕円曲線のドメインパラメータＥの下で、前記点Ｐを２倍して、前記変換データを求め、
前記暗号用演算部は、前記変換データを演算対象とし、楕円曲線のドメインパラメータＥの下で、前記スカラー値ｄのうち最下位ビットを除いたものに基づく前記右向き型演算手順により、楕円曲線上のスカラー倍算を行い、
前記後処理部は、前記スカラー値ｄの最下位ビットが１である場合には、楕円曲線のドメインパラメータＥの下で、前記暗号用演算部の演算結果と前記点Ｐとの点加算を行って、前記最終的な演算結果を求めることを特徴とする請求項１０に記載の暗号用演算装置。
【請求項１２】
前記後処理部は、前記スカラー値ｄの最下位ビットが０である場合には、ダミー計算として、前記スカラー値ｄの最下位ビットが１である場合と同一の演算を行い、
前記暗号用演算部の演算結果を、前記最終的な演算結果とすることを特徴とする請求項１１に記載の暗号用演算装置。
【請求項１３】
前記前処理部は、楕円曲線のドメインパラメータＥの下で、前記点Ｐに対して点２倍算をｔ回繰り返して、前記変換データを求め、
前記暗号用演算部は、前記変換データを演算対象とし、楕円曲線のドメインパラメータＥの下で、前記スカラー値ｄのうち最下位ビットからｔビット分を除いたものに基づく前記右向き型演算手順により、第１の楕円曲線上のスカラー倍算を行って、第１の演算結果を求め、
前記後処理部は、前記データを演算対象とし、楕円曲線のドメインパラメータＥの下で、前記スカラー値ｄのうち最下位ビットからｔビット分を取り出したものに基づく任意の演算手順により、第２の楕円曲線上のスカラー倍算を行って、第２の演算結果を求め、
前記後処理部は、楕円曲線のドメインパラメータＥの下で、第１の演算結果と第２の演算結果との点加算を行って、最終的なスカラー倍算結果を求めることを特徴とする請求項１０に記載の暗号用演算装置。
【請求項１４】
前記後処理部が第２の楕円曲線上のスカラー倍算を行って前記第２の演算結果を求める代わりに、前記暗号用演算部又は前記暗号用演算部とは別に設けられた暗号用演算部が第２の楕円曲線上のスカラー倍算を行って前記第２の演算結果を求めることを特徴とする請求項１３に記載の暗号用演算装置。
【請求項１５】
前記暗号用演算部は、右向き型のバイナリ法又はモンゴメリ・ラダー法により、べき乗剰余計算を行うものであることを特徴とする請求項３、４、５、６、７または８に記載の暗号用演算装置。
【請求項１６】
前記暗号用演算部は、右向き型のバイナリ法又はモンゴメリ・ラダー法により、楕円曲線上のスカラー倍算を行うものであることを特徴とする請求項１１、１２、１３または１４に記載の暗号用演算装置。
【請求項１７】
前記暗号用演算部は、右向き型のｗビットウィンドウ法により、べき乗剰余計算を行うものであることを特徴とする請求項５または６に記載の暗号用演算装置。
【請求項１８】
前記暗号用演算部は、右向き型のｗビットウィンドウ法により、楕円曲線上のスカラー倍算を行うものであることを特徴とする請求項１３または１４に記載の暗号用演算装置。
【請求項１９】
２進数からなる秘密のパラメータの上位ビットから下位ビットに向けて計算を進める手順である右向き型演算手順を用いて、特定の暗号用演算を行う暗号用演算装置であって、
前記暗号用演算装置の備える入力部が、前記暗号用演算の対象となるデータと、前記演算に用いる前記秘密のパラメータと、前記演算に用いる他のパラメータとを入力するステップと、
前記暗号用演算装置の備える前処理部が、前記データに対して、特定の変換を施して、変換データを求めるステップと、
前記暗号用演算装置の備える暗号用演算部が、前記変換データと、前記秘密のパラメータの全部又は一部と、前記他のパラメータとを入力として、該秘密のパラメータの全部又は一部を用いた前記右向き型演算手順により、前記暗号用演算を行って、その演算結果を求めるステップと、
前記暗号用演算装置の備える後処理部が、前記暗号用演算部が求めた前記演算結果をもとにして、前記データと前記秘密のパラメータの全部と前記他のパラメータとを入力とした場合の前記暗号用演算の演算結果を求める後処理を行うステップと、
前記暗号用演算装置の備える出力部が、前記暗号用演算部が求めた前記演算結果又は前記後処理部が求めた前記演算結果を、最終的な演算結果として出力するステップとを有することを特徴とする暗号用演算装置。
【請求項２０】
２進数からなる秘密のパラメータの上位ビットから下位ビットに向けて計算を進める手順である右向き型演算手順を用いて、特定の暗号用演算を行う暗号用演算装置としてコンピュータを機能させるためのプログラムであって、
前記暗号用演算装置の備える入力部が、前記暗号用演算の対象となるデータと、前記演算に用いる前記秘密のパラメータと、前記演算に用いる他のパラメータとを入力するステップと、
前記暗号用演算装置の備える前処理部が、前記データに対して、特定の変換を施して、変換データを求めるステップと、
前記暗号用演算装置の備える暗号用演算部が、前記変換データと、前記秘密のパラメータの全部又は一部と、前記他のパラメータとを入力として、該秘密のパラメータの全部又は一部を用いた前記右向き型演算手順により、前記暗号用演算を行って、その演算結果を求めるステップと、
前記暗号用演算装置の備える後処理部が、前記暗号用演算部が求めた前記演算結果をもとにして、前記データと前記秘密のパラメータの全部と前記他のパラメータとを入力とした場合の前記暗号用演算の演算結果を求める後処理を行うステップと、
前記暗号用演算装置の備える出力部が、前記暗号用演算部が求めた前記演算結果又は前記後処理部が求めた前記演算結果を、最終的な演算結果として出力するステップとをコンピュータに実行させるためのプログラム。
【請求項１】
２進数からなる秘密のパラメータの上位ビットから下位ビットに向けて計算を進める手順である右向き型演算手順を用いて、特定の暗号用演算を行う暗号用演算装置であって、
前記暗号用演算の対象となるデータと、前記演算に用いる前記秘密のパラメータと、前記演算に用いる他のパラメータとを入力する入力部と、
前記データに対して、特定の変換を施して、変換データを求める前処理部と、
前記変換データと、前記秘密のパラメータの全部又は一部と、前記他のパラメータとを入力として、該秘密のパラメータの全部又は一部を用いた前記右向き型演算手順により、前記暗号用演算を行って、その演算結果を求める暗号用演算部と、
前記暗号用演算部が求めた前記演算結果をもとにして、前記データと前記秘密のパラメータの全部と前記他のパラメータとを入力とした場合の前記暗号用演算の演算結果を求める後処理を行う後処理部と、
前記暗号用演算部が求めた前記演算結果又は前記後処理部が求めた前記演算結果を、最終的な演算結果として出力する出力部とを備えたことを特徴とする暗号用演算装置。
【請求項２】
前記所定の暗号用演算は、べき乗剰余計算であり、
前記データは、べき乗剰余計算の底であるメッセージＭであり、
前記秘密のパラメータは、べき指数ｄであり、
前記他のパラメータは、法ｎであり、
前記最終的な演算結果は、べき乗剰余計算結果Ｍ＾ｄ ｍｏｄ ｎであることを特徴とする請求項１に記載の暗号用演算装置。
【請求項３】
前記前処理部は、法ｎの下で、前記メッセージＭを２乗して、前記変換データを求め、
前記暗号用演算部は、前記変換データを演算対象とし、法ｎの下で、前記べき指数ｄのうち最下位ビットを除いたものに基づく前記右向き型演算手順により、べき乗剰余計算を行い、
前記後処理部は、前記べき指数ｄの最下位ビットが１である場合には、法ｎの下で、前記暗号用演算部の演算結果と前記メッセージＭとの乗算剰余計算を行って、前記最終的な演算結果を求めることを特徴とする請求項２に記載の暗号用演算装置。
【請求項４】
前記後処理部は、前記べき指数ｄの最下位ビットが０である場合には、ダミー計算として、前記べき指数ｄの最下位ビットが１である場合と同一の演算を行い、
前記暗号用演算部の演算結果を、前記最終的な演算結果とすることを特徴とする請求項３に記載の暗号用演算装置。
【請求項５】
前記前処理部は、法ｎの下で、前記メッセージＭに対して２乗演算をｔ回繰り返して、前記変換データを求め、
前記暗号用演算部は、前記変換データを演算対象とし、法ｎの下で、前記べき指数ｄのうち最下位ビットからｔビット分を除いたものに基づく前記右向き型演算手順により、第１のべき乗剰余計算を行って、第１の演算結果を求め、
前記後処理部は、前記メッセージＭを演算対象とし、法ｎの下で、前記べき指数ｄのうち最下位ビットからｔビット分を取り出したものに基づく任意の演算手順により、第２のべき乗剰余計算を行って、第２の演算結果を求め、
前記後処理部は、法ｎの下で、第１の演算結果と第２の演算結果との乗算剰余計算を行って、前記最終的な演算結果を求めることを特徴とする請求項２に記載の暗号用演算装置。
【請求項６】
前記後処理部が第２のべき乗剰余計算を行って前記第２の演算結果を求める代わりに、前記暗号用演算部又は前記暗号用演算部とは別に設けられた暗号用演算部が第２のべき乗剰余計算を行って前記第２の演算結果を求めることを特徴とする請求項５に記載の暗号用演算装置。
【請求項７】
前記前処理部は、入力メッセージの空間を正のメッセージ空間と負のメッセージ空間とに２分して定義した際に、前記メッセージＭが正のメッセージ空間に属するか又は負のメッセージ空間に属するかを調べ、前記メッセージＭが負のメッセージ空間に属する場合には、法ｎの下で、前記メッセージＭの符号を反転して、前記変換データを求め、
前記暗号用演算部は、前記メッセージＭが負のメッセージ空間に属する場合には、前記変換データを演算対象とし、法ｎの下で、前記べき指数ｄに基づく前記右向き型演算手順により、べき乗剰余計算を行い、前記メッセージＭが正のメッセージ空間に属する場合には、前記メッセージＭを演算対象とし、法ｎの下で、前記べき指数ｄに基づく前記右向き型演算手順により、べき乗剰余計算を行い、
前記後処理部は、前記メッセージＭが負のメッセージ空間に属する場合には、法ｎの下で、（−１）＾ｄと前記暗号用演算部の演算結果との乗算剰余計算を行って、前記最終的な演算結果を求めることを特徴とする請求項２に記載の暗号用演算装置。
【請求項８】
前記データＭが正のメッセージ空間に属する場合には、前記暗号用演算部の演算結果を、前記最終的な演算結果とすることを特徴とする請求項２に記載の暗号用演算装置。
【請求項９】
法ｎが互いに素な複数の素数の積である場合に、法ｎを互いに素な因子に分解し、個々の因子を法として前記前処理部、前記暗号用演算部及び前記後処理部を用いてそれぞれ前記最終的な演算結果を求め、求めた複数の前記最終的な演算結果を中国剰余定理で合成する手段を更に備えたことを特徴とする請求項１ないし８のいずれか１項に記載の暗号用演算装置。
【請求項１０】
前記所定の暗号用演算は、楕円曲線上のスカラー倍算であり、
前記データは、スカラー倍算の対象である点Ｐであり、
前記秘密のパラメータは、秘密のスカラー値ｄであり、
前記他のパラメータは、楕円曲線のドメインパラメータＥであり、
前記最終的な演算結果は、楕円曲線上のスカラー倍算結果ｄ＊Ｐであることを特徴とする請求項１に記載の暗号用演算装置。
【請求項１１】
前記前処理部は、楕円曲線のドメインパラメータＥの下で、前記点Ｐを２倍して、前記変換データを求め、
前記暗号用演算部は、前記変換データを演算対象とし、楕円曲線のドメインパラメータＥの下で、前記スカラー値ｄのうち最下位ビットを除いたものに基づく前記右向き型演算手順により、楕円曲線上のスカラー倍算を行い、
前記後処理部は、前記スカラー値ｄの最下位ビットが１である場合には、楕円曲線のドメインパラメータＥの下で、前記暗号用演算部の演算結果と前記点Ｐとの点加算を行って、前記最終的な演算結果を求めることを特徴とする請求項１０に記載の暗号用演算装置。
【請求項１２】
前記後処理部は、前記スカラー値ｄの最下位ビットが０である場合には、ダミー計算として、前記スカラー値ｄの最下位ビットが１である場合と同一の演算を行い、
前記暗号用演算部の演算結果を、前記最終的な演算結果とすることを特徴とする請求項１１に記載の暗号用演算装置。
【請求項１３】
前記前処理部は、楕円曲線のドメインパラメータＥの下で、前記点Ｐに対して点２倍算をｔ回繰り返して、前記変換データを求め、
前記暗号用演算部は、前記変換データを演算対象とし、楕円曲線のドメインパラメータＥの下で、前記スカラー値ｄのうち最下位ビットからｔビット分を除いたものに基づく前記右向き型演算手順により、第１の楕円曲線上のスカラー倍算を行って、第１の演算結果を求め、
前記後処理部は、前記データを演算対象とし、楕円曲線のドメインパラメータＥの下で、前記スカラー値ｄのうち最下位ビットからｔビット分を取り出したものに基づく任意の演算手順により、第２の楕円曲線上のスカラー倍算を行って、第２の演算結果を求め、
前記後処理部は、楕円曲線のドメインパラメータＥの下で、第１の演算結果と第２の演算結果との点加算を行って、最終的なスカラー倍算結果を求めることを特徴とする請求項１０に記載の暗号用演算装置。
【請求項１４】
前記後処理部が第２の楕円曲線上のスカラー倍算を行って前記第２の演算結果を求める代わりに、前記暗号用演算部又は前記暗号用演算部とは別に設けられた暗号用演算部が第２の楕円曲線上のスカラー倍算を行って前記第２の演算結果を求めることを特徴とする請求項１３に記載の暗号用演算装置。
【請求項１５】
前記暗号用演算部は、右向き型のバイナリ法又はモンゴメリ・ラダー法により、べき乗剰余計算を行うものであることを特徴とする請求項３、４、５、６、７または８に記載の暗号用演算装置。
【請求項１６】
前記暗号用演算部は、右向き型のバイナリ法又はモンゴメリ・ラダー法により、楕円曲線上のスカラー倍算を行うものであることを特徴とする請求項１１、１２、１３または１４に記載の暗号用演算装置。
【請求項１７】
前記暗号用演算部は、右向き型のｗビットウィンドウ法により、べき乗剰余計算を行うものであることを特徴とする請求項５または６に記載の暗号用演算装置。
【請求項１８】
前記暗号用演算部は、右向き型のｗビットウィンドウ法により、楕円曲線上のスカラー倍算を行うものであることを特徴とする請求項１３または１４に記載の暗号用演算装置。
【請求項１９】
２進数からなる秘密のパラメータの上位ビットから下位ビットに向けて計算を進める手順である右向き型演算手順を用いて、特定の暗号用演算を行う暗号用演算装置であって、
前記暗号用演算装置の備える入力部が、前記暗号用演算の対象となるデータと、前記演算に用いる前記秘密のパラメータと、前記演算に用いる他のパラメータとを入力するステップと、
前記暗号用演算装置の備える前処理部が、前記データに対して、特定の変換を施して、変換データを求めるステップと、
前記暗号用演算装置の備える暗号用演算部が、前記変換データと、前記秘密のパラメータの全部又は一部と、前記他のパラメータとを入力として、該秘密のパラメータの全部又は一部を用いた前記右向き型演算手順により、前記暗号用演算を行って、その演算結果を求めるステップと、
前記暗号用演算装置の備える後処理部が、前記暗号用演算部が求めた前記演算結果をもとにして、前記データと前記秘密のパラメータの全部と前記他のパラメータとを入力とした場合の前記暗号用演算の演算結果を求める後処理を行うステップと、
前記暗号用演算装置の備える出力部が、前記暗号用演算部が求めた前記演算結果又は前記後処理部が求めた前記演算結果を、最終的な演算結果として出力するステップとを有することを特徴とする暗号用演算装置。
【請求項２０】
２進数からなる秘密のパラメータの上位ビットから下位ビットに向けて計算を進める手順である右向き型演算手順を用いて、特定の暗号用演算を行う暗号用演算装置としてコンピュータを機能させるためのプログラムであって、
前記暗号用演算装置の備える入力部が、前記暗号用演算の対象となるデータと、前記演算に用いる前記秘密のパラメータと、前記演算に用いる他のパラメータとを入力するステップと、
前記暗号用演算装置の備える前処理部が、前記データに対して、特定の変換を施して、変換データを求めるステップと、
前記暗号用演算装置の備える暗号用演算部が、前記変換データと、前記秘密のパラメータの全部又は一部と、前記他のパラメータとを入力として、該秘密のパラメータの全部又は一部を用いた前記右向き型演算手順により、前記暗号用演算を行って、その演算結果を求めるステップと、
前記暗号用演算装置の備える後処理部が、前記暗号用演算部が求めた前記演算結果をもとにして、前記データと前記秘密のパラメータの全部と前記他のパラメータとを入力とした場合の前記暗号用演算の演算結果を求める後処理を行うステップと、
前記暗号用演算装置の備える出力部が、前記暗号用演算部が求めた前記演算結果又は前記後処理部が求めた前記演算結果を、最終的な演算結果として出力するステップとをコンピュータに実行させるためのプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【公開番号】特開２０１０−８８８３（Ｐ２０１０−８８８３Ａ）
【公開日】平成２２年１月１４日（２０１０．１．１４）
【国際特許分類】
【出願番号】特願２００８−１７０４３２（Ｐ２００８−１７０４３２）
【出願日】平成２０年６月３０日（２００８．６．３０）
【出願人】（０００００３０７８）株式会社東芝 (54,554)
【Ｆターム（参考）】
【公開日】平成２２年１月１４日（２０１０．１．１４）
【国際特許分類】
【出願日】平成２０年６月３０日（２００８．６．３０）
【出願人】（０００００３０７８）株式会社東芝 (54,554)
【Ｆターム（参考）】
[ Back to top ]