楕円曲線演算処理装置、楕円曲線演算処理プログラム及び方法
【課題】 攻撃に対する安全性を向上させることができる楕円曲線演算処理装置、楕円曲線演算処理プログラム、楕円曲線演算処理方法を提供する。
【解決手段】 楕円曲線上の点の演算を行う楕円曲線演算処理装置であって、前記楕円曲線上の所定の点Aを前記楕円曲線上の点の演算に対する入力とし、ECDBL演算及びECADD演算によりスカラー値dによる点Aのd倍点を算出する算出部と、前記算出部による点Aのd倍点の算出において、前記ECDBL演算または前記ECADD演算の入力値または出力値が無限遠点であるかどうかを判断する判断部と、前記判断部により前記入力値または前記出力値が無限遠点であると判断された場合、前記算出部による点Aのd倍点の算出を停止する停止部とを備えた。
【解決手段】 楕円曲線上の点の演算を行う楕円曲線演算処理装置であって、前記楕円曲線上の所定の点Aを前記楕円曲線上の点の演算に対する入力とし、ECDBL演算及びECADD演算によりスカラー値dによる点Aのd倍点を算出する算出部と、前記算出部による点Aのd倍点の算出において、前記ECDBL演算または前記ECADD演算の入力値または出力値が無限遠点であるかどうかを判断する判断部と、前記判断部により前記入力値または前記出力値が無限遠点であると判断された場合、前記算出部による点Aのd倍点の算出を停止する停止部とを備えた。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報セキュリティ技術に関する。
【背景技術】
【０００２】
情報化社会の発展に伴い、電子決済、住民基本台帳ネットワークなどの情報ネットワークを利用したサービスが普及することが予想される。このようなサービスを安全に運用するためには情報セキュリティ技術が必須である。また、この情報セキュリティの基盤技術として、公開鍵暗号方式が用いられる。公開鍵暗号方式として、RSA、楕円曲線暗号（以下、ECC: Elliptic Curve Cryptosystem）が主要な方式として知られている。これらの暗号を用いることによって、情報の暗号化、デジタル署名、認証機能を実現することができ、個人情報に対する第三者による不正なアクセスを防ぐことができる。
【０００３】
また、上述したようなサービスにおけるエンドユーザ側のデバイスとして、スマートカードが知られている。このスマートカードは、ICチップを搭載したカードであり、ICチップ内部のメモリ領域にユーザの秘密情報を格納している。また、スマートカードのICチップは、暗号化機能、デジタル署名機能、認証機能を搭載しており、これらの機能の処理において、ユーザの秘密情報が鍵として用いられる。この秘密情報は、カード内部のメモリ領域に格納されるため、第三者からの不正な覗き見に対する安全性、つまり耐タンパ性は、磁気記録型のカードに比べて高い。
【０００４】
しかし、このようなスマートカードに対する解析として、電力解析攻撃（Power Analysis, 以下PA）が知られている（例えば、非特許文献１参照）。以下、PAの概要に関して、図面を用いて説明する。図１５は、PAの概要を示す図である。
【０００５】
このPAは、図１５に示すように、ユーザの秘密情報Kを鍵とする暗号機能による処理（以下、暗号処理）の最中のスマートカードの消費電力を測定し、測定したデータを用いることで秘密情報Ｋを推定、解析する方法である。このPAは、電力の観察により解析を行う攻撃であるため、攻撃対象はスマートカードに限定されない。例えば、PDAデバイスに対して、電力消費時に発生する電磁波を測定するPAも知られている（例えば、非特許文献２参照）。つまり、PAは、電力を消費する組み込み機器全般を攻撃対象とする。
【０００６】
次に、RSA, ECCを用いる組み込み機器に対するPAについて詳述する。なお、このPAは、RSA, ECCの演算の仕組みを利用した攻撃であるため、まず、これらの演算について説明する。図１６は、RSA, ECCの演算の対応関係を示す図である。
【０００７】
RSA, ECCの演算には対応関係があり、この対応関係は図１６に示す通りである。以下、この対応関係を踏まえ、RSA, ECCの演算についてそれぞれ説明する。
【０００８】
まず、RSAの演算について説明する。RSAでは、べき乗剰余演算を用いた処理が行われる。このべき乗剰余演算は、基数a、指数x、法nに対して、z = ax(mod n)を計算する演算である。RSAにおいて、このべき乗剰余演算により、ｘを秘密情報とした処理が行われる。例えば、RSA暗号の復号処理は、暗号文をc、個人鍵をdとした場合、m=cd(mod n)を満たすmを求める処理である。また、RSAによる電子署名においては、署名対象データc、個人鍵d、法nに対して、上述した計算を行うことにより、電子署名mが得られる。いずれの処理においても、個人鍵dを知らない第三者は、正しい復号処理結果、電子署名処理結果を得ることができない。
【０００９】
次に、ECCの演算について説明する。ECCにおいて、以下に示すx, yの関係式を楕円曲線と呼ぶ。この楕円曲線は、主に素体（prime field）と2べき（binary field）の2種類からなる。また、楕円曲線を一意に決定するためのパラメータa, bを楕円曲線パラメータと呼ぶ。楕円曲線（素体）は、pを素数とした場合、y2 = x3 + ax + b(mod p)として表される。なお、この式において、pは素数であり、0 ≦ a, b ＜ ｐである。また、楕円曲線（2べき）は、y2 + xy = x3 + ax2 + b(mod f(x))として表される。なお、この式において、fはGF（2m）の多項式であり、a, b ⊆ GF(2m)である。また、上述した楕円曲線（素体）、楕円曲線（2べき）を表す関係式を満たす(x, y)を楕円曲線上の点（elliptic point）と呼ぶ。
【００１０】
ECCでは、点のスカラー倍算（Elliptic Scalar Multiplication）を用いた処理が行われる。この点のスカラー倍算は、楕円曲線上の点A、スカラー値と呼ばれる整数sに対して、V = sAを満たす楕円曲線上の点Vを計算する演算である。例えば、ECCにおけるECDH鍵交換は、通信相手の公開鍵となる楕円曲線上の点をA、個人鍵をdとすると、V = dAを満たす楕円曲線上の点Vを計算することで、安全な鍵共有を実現する。個人鍵dの値を知らない第三者は、正しい共有鍵の値を算出することができない。
【００１１】
上述したRSA暗号、RSAによる電子署名、ECC暗号において、個人鍵dは、暗号に対する攻撃を行う第三者（以下、攻撃者と呼称する）に漏洩してはならない値である。つまり、RSA, ECCにおいて、dの値の保護が重要な耐タンパ機能となる。数学的には、d以外の値が攻撃者に知られていたとしても、これらの値からdの値を計算するための計算量が大きすぎるため、現実的な時間内にdの値を求めることが困難であることが知られている。例えば、RSA暗号の復号処理において、nが1024bit以上の値である場合、攻撃者はc, n, mの値を知っていたとしてもdの値を求めることが困難であることが知られている。また、ECCの復号処理において、楕円曲線パラメータが160bit以上である場合、攻撃者はA, Vの値を知っていたとしてもdの値を求めることが困難であることが知られている。
【００１２】
上述したように、RSA，ECCにおいて個人鍵dの値は数学的に求めることが困難であるが、PAを用いることにより容易に解読することが知られている。このPAの基本メカニズムは、RSAにおけるべき乗剰余演算、ECCにおける点のスカラー倍算と大きな関連がある。よって、これらの演算手順について説明したうえで、RSAに対するPA、ECCに対するPAについてそれぞれ説明する。
【００１３】
まず、RSAにおけるべき乗剰余演算の演算手順と、RSAに対するPAについて説明する。図１７は、バイナリ法によるべき乗剰余演算のアルゴリズムを示す図である。また、図１８は、バイナリ法によるべき乗剰余演算の概要を示す図である。また、図１９は、バイナリ法によるべき乗剰余演算に対するPAの概要を示す図である。
【００１４】
RSA（RSA暗号、RSAによる電子署名）におけるべき乗剰余演算において、n, c,dの全てがそれぞれ1024bit以上の長さを持つ場合、べき乗剰余演算を数式通りに計算した場合、(mod n)を用いた掛け算をd回必要とする。この演算は21024以上の計算量を必要とするため現実的ではない。そこで、この計算量をlog2dに削減するための演算方法としてバイナリ法が知られている。以下、べき乗剰余におけるバイナリ法について説明する。このバイナリ法では、図１７に示すように、u-bitの個人鍵dをd = du-1||…||d1||d0（ただし、diは1-bit値）と表したとき、diのビット値が上位ビットから下位ビットの順（即ち、i = u - 1からi = 0の順）にスキャンされる。そして、diのビット値に応じて演算が行われる。di == 1の場合、2乗算（図１７におけるv := v × v(mod n)）の後に乗算（図１７におけるv := v × a(mod n)）が実行される。一方、di == 0の場合、2乗算のみが実行される。即ち、図１８に示す2乗算及び乗算の演算シーケンスが、そのままdiのビット値と連動しており、RSAに対するPAは、この性質を利用してdを解読する。
【００１５】
RSAに対するPAは、図１９に示すように、上述したバイナリ法の処理を実行するデバイスにおける消費電力を測定し、乗算処理と2乗算処理との電力波形の違いを区別することにより個人鍵dを解読する。2乗算のあとに乗算を実行している場合はdのビット値は1と解読され、2乗算のみを実行しているならばdのビット値は0と解読される。この解読がdの全ビットに対して行われることで、RSAに対するPAが成功する。
【００１６】
次に、ECCにおける点のスカラー倍算の演算手順と、ECCに対するPAについて説明する。図２０は、バイナリ法による点のスカラー倍算のアルゴリズムを示す図である。また、図２１は、バイナリ法による点のスカラー倍算の概要を示す図である。また、図２２は、バイナリ法による点のスカラー倍算に対するPAの概要を示す図である。
【００１７】
RSAにおけるべき乗剰余演算と同様に、点のスカラー倍算についても、その演算量を削減するための演算方法としてバイナリ法が知られている。以下、スカラー倍算におけるバイナリ法について説明する。このバイナリ法では、図２０に示すように、u-bitの個人鍵dをd = du-1||…||d1||d0（ただし、diは1-bit値）と表したとき、diのビット値が上位ビットから下位ビットの順（即ち、i = u - 1からi = 0の順）にスキャンされる。そして、diのビット値に応じて演算が行われる。di == 1の場合、点の2倍算（図２０におけるV := 2V。以下、ECDBL: Elliptic Curve Doubling）の後に点の加算（図２０におけるV := V + A。以下、ECADD: Elliptic Curve Addition）が実行される。一方、di == 0の場合、ECDBLのみが実行される。即ち、図２１に示すECDBL及びECADDの演算シーケンスが、そのままdiのビット値と連動しており、ECCに対するPAは、この性質を利用してdを解読する。
【００１８】
ECCに対するPAは、図２２に示すように、上述したバイナリ法の処理を実行するデバイスにおける消費電力を測定し、ECDBLとECADDとの処理による電力波形の違いを区別することにより個人鍵dを解読する。ECDBLのあとにECADDを実行している場合はdのビット値は1と解読され、ECDBLのみを実行しているならばdのビット値は0と解読される。この解読がdの全ビットに対して行われることで、ECCに対するPAが成功する。
【００１９】
上述したRSAに対するPA及びECCに対するPAは、dのビット値を決定する処理の種類を、処理を実行するデバイスの消費電力の電力波形に基づいて特定することにより個人鍵dを解読する。なお、これらのPAに対する対策法として、Add-and-double-allways法（以下、A&D法）が知られている（例えば、非特許文献３参照）。以下、A&D法によるRSAに対するPAへの対策法、A&D法によるECCに対するPAへの対策法についてそれぞれ説明する。
【００２０】
まず、A&D法によるRSAに対するPAへの対策法について説明する。図２３は、A&D法を用いたバイナリ法によるべき乗剰余演算のアルゴリズムを示す図である。また、図２４は、A&D法を用いたバイナリ法によるべき乗剰余演算に対するPAの概要を示す図である。
【００２１】
図２３に示すように、A&D法を用いたべき乗剰余演算は、常にv[0]に計算結果を格納しながら実行される。また、1206の処理において、dのビット値diが0の場合でも乗算が実行される。この乗算の結果は、1208の処理において、di = 1の場合、v[0]に格納され、次のループで使用される。一方、di = 0の場合、1206の処理における乗算の結果は、v[0]に格納されず、代わりに1024の処理における2乗算結果がv[0]に格納され次のループで使用される。つまり、1206の処理における乗算は、diの値に関係なく実行されるが、その演算結果が次のループにおける計算に用いられるのは、di = 1の場合のみである。このような処理によれば、図２４に示すように、diの値にかかわらず、バイナリ法によるべき乗剰余演算を実行するデバイスの消費電力の電力波形は一定となる。これにより、乗算処理と２乗算処理との電力波形の違いを利用したPAを防ぐことができる。また、di = 1の場合にのみ、乗算結果が次のループで用いられることにより、べき乗剰余演算の整合性が保たれる。
【００２２】
次に、A&D法によるECCに対するPAへの対策法について説明する。図２５は、A&D法を用いたバイナリ法による点のスカラー倍算のアルゴリズムを示す図である。また、図２６は、A&D法を用いたバイナリ法による点のスカラー倍算に対するPAの概要を示す図である。
【００２３】
図２５に示すように、A&D法を用いたバイナリ法による点のスカラー倍算は、常にV[0]に計算結果を格納しながら実行される。また、1406の処理において、dのビット値diが0の場合でもECADDが実行される。また、1408のdiの値に応じたV[0]へのコピー処理において、di = 0の場合は1404の処理によるECDBL結果がV[0]に格納される。また、di = 1の場合は1406の処理によるECADD結果がV[0]に格納される。このように演算結果が格納されたV[0]が次のループにおける計算に用いられる。このような処理によれば、図２６に示すように、diの値にかかわらず、バイナリ法による点のスカラー倍算を実行するデバイスの消費電力の電力波形は一定となる。これにより、点の2乗算処理とECADD処理との電力波形の違いを利用するPAを防ぐことができる。
【００２４】
しかし、上述したA&D法によるPAへの対策法に対するさらに高度な攻撃法として、メッセージ選択型PAが知られている（例えば、非特許文献４参照）。以下、RSAに対するメッセージ選択型PA、ECCに対するメッセージ選択型PAについてそれぞれ説明する。
【００２５】
まず、RSAに対するメッセージ選択型PAについて説明する。図２７は、RSAに対するメッセージ選択型PAの概要を示す図である。
【００２６】
上述したRSAに対するPAは、べき乗剰余ad(mod n)を計算する際、ランダムなaを入力し、その処理における消費電力波形を観測することで個人鍵dを解読する攻撃法である。これに対し、RSAに対するメッセージ選択型PAは、aとして特殊な値を選択して入力する点が異なる。この方法によれば、A&D法が用いられたRSAに対しても攻撃を成功させることができる。具体的には、a = -1(mod n)を入力することで、図２７に示すように、diの値によって電力波形の違いが生じ、この電力波形の違いに基づいてdiの値を識別することで、個人鍵dを解読することが可能となる。なお、ループ変数iにおける２乗算（図２３における1204の処理）の種類と、diの値との対応関係は、２乗算が1×1の場合di+1 = 0であり、２乗算が(-1)×(-1)の場合di+1 = 1である。なお、この対応関係は、図２３に示したアルゴリズムに起因する。di = 0の場合、1204の処理による２乗算結果（(-1)×（-1） = 1）が1208の処理によりv[0]にコピーされるため、次のループにおいて計算される２乗算は1×1となる。一方、di = 1の場合、1204の処理による２乗算結果（1×(-1) = -1）が1208の処理によりv[0]にコピーされるため、次のループにおいて計算される２乗算は(-1)×(-1)となる。このように、メッセージ選択型PAによれば、A&D法を用いたRSAにおける個人鍵dの解読が可能となる。
【００２７】
次に、ECCに対するメッセージ選択型PAについて説明する。この上述したメッセージ選択型PAをECCに適用した攻撃法について説明するため、まず、ECCにおける点の加算、点の2倍算の演算手順における無限遠点について説明する。なお、以降に示すECCは、A&D法を用いたECCである。図２８は、素体楕円曲線パラメータの点の加算演算のアルゴリズムを示す図である。また、図２９は、素体楕円曲線パラメータの点の2倍算処理のアルゴリズムを示す図である。また、図３０は、2べき楕円曲線パラメータの点の加算演算のアルゴリズムを示す図である。また、図３１は、2べき楕円曲線パラメータの点の2倍算処理のアルゴリズムを示す図である。
【００２８】
図２８〜図３１に示す点の加算演算、または点の2倍算処理のアルゴリズムにおいて、点の座標は3次元形式（X, Y, Z）により表現される。また、無限遠点は、Z座標が0の点、つまりZ = 0として表現され、この無限遠点をOとすると、任意の点Aに対して、A + O = O + A = Aが満たされるような点である。図２８〜３１に示すアルゴリズムは、いずれも無限遠点に関連した処理を含んでいる。この処理は、入力値、または出力値が無限遠点である場合の処理である例外処理を含む。この例外処理は、図２８の800, 817の処理、図２９の904の処理、図３０の1000, 1018の処理、図３１の1105の処理である。以下、例外処理が実行される場合の分岐を特殊分岐として説明する。
【００２９】
図２８の800の処理、図３０の1000の処理は、A + B（B = ECDBL(V)）の計算において、点Aが無限遠点である場合(Az == 0)、点Bを計算結果として出力し、点Bが無限遠点である場合(Bz == 0)、つまり、点Aまたは点Bが無限遠点である場合（特殊分岐１）、無限遠点ではない方の点を計算結果として出力する。
【００３０】
また、A + Bの計算において、A == Bである場合（特殊分岐２）、A + Bの計算処理から2Aの計算処理（ECDBL(A)）を実行する。特殊分岐２として、図２８の817の処理においてT4 == 0かつT5 == 0である場合、もしくは図３０の1018においてT1 == 0かつT2 == 0である場合が挙げられる。
【００３１】
また、A + Bの計算において、計算結果が無限遠点である場合（特殊分岐３）、無限遠点である座標(1, 1, 0)を計算結果として出力する。特殊分岐３として、図２８の817の処理においてT4 == 0かつT5 ( 0である場合、もしくは図３０の1018においてT1 == 0かつT2 ( 0である場合が挙げられる。
【００３２】
また、2Aの計算において、入力データとしての点Aが無限遠点である場合、もしくは、出力データとしての2Aが無限遠点である場合（特殊分岐４）、無限遠点である座標(1, 1, 0)を計算結果として出力する。特殊分岐４のうち、入力データとしての点Aが無限遠点である場合は、図２９の904または図３１の1105の処理においてT3 == 0である場合に相当する。また、出力データとしての2Aが無限遠点である場合は、図２９の904の処理においてT2 == 0である場合、図３１の1105の処理においてT1 == 0である場合に相当する。
【００３３】
以上のことを踏まえた上で、ECCに対するメッセージ選択型PAについて説明する。上述したメッセ−ジ選択型PAにおける特殊な値a = -1に対応する楕円曲線上の点は、2A = OかつA ( Oを満たす点Ａであることが知られている。これは、a = -1を満たすaはa2 = 1かつa ( 1を満たす値であり、この値を楕円曲線の演算に対応させると2A = OかつA ( Oを満たすＡとなることに起因する。また、ECCに対するメッセージ選択型PAにおいて、A = Pが点のスカラー倍算の入力として用いられる。ここでこのPは点Aと異なる点であり、2P = OかつP ( Oを満たし、楕円曲線パラメータが素体の場合にY座標が0となり、楕円曲線パラメータが２べきである場合にX座標が0となるような点の値とする。
【００３４】
A = Pを点のスカラー倍算の入力とすると、図２５に示した1404の処理におけるECDBL演算によって2P = Oとなり、Pの偶数倍点は常に無限遠点Oとなる。よって、V[0]に格納される値は常に無限遠点Oとなる。1404の処理におけるECDBL演算が図２９（演算曲線パラメータが素体の場合）、もしくは図３１（楕円曲線パラメータが２べきの場合）に示したアルゴリズムにより実行された場合、いずれも特殊分岐４により無限遠点である座標(1, 1, 0)が計算結果として出力されECDBL演算処理が終了する。つまり、A = Pを点のスカラー倍算の入力とすると、特殊分岐が発生することによりECDBL演算処理が終了し、メイン演算がなされない。よって、特殊分岐が発生するECDBL演算における電力波形は、特殊分岐が発生しないECDBL演算における電力波形と異なる。
【００３５】
図３２は、特殊分岐が発生するECDBL演算における電力波形と、特殊分岐が発生しないECDBL演算における電力波形とを示す図である。上述したように、特殊分岐が発生することにより途中でECDBL演算処理が中断されるため、図３２に示すように、特殊分岐が発生しないECDBL演算処理に比べて、その電力波形が短くなる。
【００３６】
また、A = Pを点のスカラー倍算の入力とすると、図２５に示した1404の処理におけるECDBL演算の結果としてV[0]に無限遠点が与えられる。このため、図２５に示した1406の処理において、常にECADD(O, P)の演算が実行される。ECADD演算の入力の片方が無限遠点の場合、特殊分岐１によりメイン演算がなされずにECADD演算処理が終了する。具体的には、図３０に示した1000の処理における特殊分岐、または図２８に示した800の処理における特殊分岐によりECADD演算処理が終了する。よって、特殊分岐が発生するECADD演算における電力波形は、特殊分岐が発生しないECADD演算における電力波形と異なる。
【００３７】
図３３は、特殊分岐が発生するECADD演算における電力波形と、特殊分岐が発生しないECADD演算における電力波形とを示す図である。上述したように、特殊分岐が発生することにより途中でECDBL演算処理が中断されるため、図３３に示すように、特殊分岐が発生しないECDBL演算処理に比べて、その電力波形が短くなる。
【００３８】
上述したように、A = Pを点のスカラー倍算の入力とすることで、ECDBL演算及びECADD演算において特殊分岐が発生する。以下、特殊分岐が発生した場合の点のスカラー倍算処理全体の電力波形について説明する。図３４は、特殊分岐が発生した場合の点のスカラー倍算処理全体の電力波形を示す図である。
【００３９】
図３４に示すように、点のスカラー倍算に対する入力をA = Pとした場合、点のスカラー倍算処理全体の電力波形は、ECADD演算及びECADD演算における特殊分岐による電力波形が交互に現れる波形となる。A&D法を用いたECCに対するメッセージ選択型PAにおいては、上述したA&D法を用いたRSAに対するメッセージ選択型PAにおける1×1，(-1)×（-1）に対応する処理が実行されない。よって、スカラー値dのビット値を識別するためのパターンが電力波形に現れず、結果として個人鍵の解読は失敗する。
【００４０】
しかし、上述したメッセージ選択型PAとは異なるメッセージ選択型PA（以下、特殊分岐PA）によりA&D法を用いたECCにおける個人鍵の解読が可能となる。この特殊分岐PAは、本発明者独自の分析によるものである。以下、特殊分岐PAについて説明する。
【００４１】
特殊分岐PAは、A = Qを点のスカラー倍算の入力とする。ここでQは、4Q = Oかつ2Q ( Oを満たす点である。図２５に示したA&D法を用いた点のスカラー倍算にA = Qが入力されると、ループ変数iにおけるECDBL演算の処理は、di+1の値に応じて実行される。di+1 == 0である場合、所定の整数kに関して、ECDBL((2k)Q)の演算が行われる。つまり、Qの偶数倍点に対するECDBL演算が実行されることにより演算結果が(4k)Q = Oとなり、特殊分岐が発生しECDBL演算が終了し、V[0] = Oとなる。一方、di+1 == 1である場合、所定の整数kに関して、ECDBL((2k + 1)Q)の演算が行われる。つまり、Qの奇数倍点に対するECDBLが実行されることにより演算結果が(4k + 2)Q ( Oとなり、特殊分岐は発生せずECDBL演算における全ての演算が実行されて終了し、V[0] = (4k + 2)Q = 2Qとなる。
【００４２】
また、上述したECDBL演算と同様に、ループ変数iにおけるECADD演算の処理もまた、di+1の値に応じて実行される。di+1 == 0である場合、ECDBL演算の結果がV[0]=Oであるため、ECADD(O, Q)の演算が行われる。この演算において、ECADDの片方の入力が無限遠点であるため、特殊分岐が発生し、処理が終了する。一方、di+1 == １である場合、ECDBL演算の結果がV[0] = 2Qであるため、ECADD(2Q, Q)の演算が行われる。この演算において、ECADD演算の両方の入力とも無限遠点ではないため、特殊分岐が発生せず、ECADD演算における全ての演算が実行されて処理が終了する。
【００４３】
以上のことから、ECDBL演算処理内容とdi+1のビット値の相関関係が正しければ、ECDBL演算処理結果に基づくECADD演算処理内容とdi+1のビット値の相関関係も正しくなることは自明である。以下、ECDBL演算処理内容とdi+1のビット値の相関関係について説明する。
【００４４】
ループ変数iのとき、図２５に示した1408のコピー処理（V[0] = V[di];）により、V[0]にコピーされる値はdiの値に応じて変化する。di == 0である場合、1404のV[0]のECDBL演算結果はQの偶数倍点であり、V[0]にコピーされる値は、2kQとなる。一方、di == 1である場合、1406のV[1]のECADD演算結果はQの偶数倍点+Qであり、V[0]にコピーされる値は(2k + 1)Qとなる。このように、di == 0である場合、またはdi == 1である場合それぞれにおけるV[0]の値が、次のループ、すなわちループ変数がi - 1となる時点におけるECDBL(V[0])演算の入力となる。よって、上述したECDBL演算処理内容とdi+1のビット値の相関関係が導出される。
【００４５】
以上の相関関係から、A = Qを点のスカラー倍算の入力とすることで、di+1 == 0である場合、ECDBL演算、ECADD演算ともに特殊分岐により処理が終了するという相関があることがわかる。また、di+1 == 1である場合、ECDBL演算、ECADD演算ともに全ての演算が実行されて処理が終了するという相関があることがわかる。つまり、この相関関係に基づいて、diの値を電力波形から推定することができる。図３５は、A&D法を用いたECCに対する特殊分岐PAを示す図である。
【００４６】
図３５に示すように、diの値と次のループにおけるECDBL演算、及びECADD演算の電力波形に相関関係があるため、A = Qを入力とする点のスカラー倍算処理を実行するデバイスの電力波形から個人鍵dを解読することができる。
【００４７】
しかし、上述した特殊分岐PAによる個人鍵の解読を防ぐ技術として、公開鍵確認（以下、PKV: Public Key Validation）が知られている（例えば、非特許文献５参照）。PKV及びA&D法を用いたECC（以下、PKV方式）によれば、4Q = Oかつ2Q ( Oを満たす点Qを、点のスカラー倍算の入力として用いられることが防がれる。図３６は、PKV処理のアルゴリズムを示す図である。
【００４８】
PKVは、スカラー倍算する点Aが、暗号演算に用いるために正しい値であるかどうかを、数学的関係に基づいて判定するアルゴリズムである。具体的には図３６に示すようにPKVを用いた判定処理が事前処理として用いられ、この判定処理において真である（valid）と判定された点Aのみが点のスカラー倍算に入力される。PKVによって真であると判定された点Aに対してd倍算処理による点のスカラー倍算処理がなされた場合、位数をrとすると、d < rが満たされる限りは、ECADD演算処理及びECDBL演算処理において常に全ての演算が実行されることが知られている。つまり、暗号処理におけるスカラー値dが常にd < rを満たすことにより、点のスカラー倍算において特殊分岐は発生しない。その結果として、PKV方式に対する特殊分岐PAが不可能となる。
【先行技術文献】
【非特許文献】
【００４９】
【非特許文献１】P.Kocher, J,Jaffe and B.Jun "Differential Power Anaysis", Crypto'99, LNCS 1666, pp.388-397, Springer-Verlag, 1999.
【非特許文献２】Catherine H. Gebotys, Simon Ho, and C.C. Tiu, "EM Analysis of Rijndael and ECC on a Wireless Java-Based PDA", Cryptographic Hardware and Embedded System, CHES 2005, pp.250-264, LNCS 3659.
【非特許文献３】Jean-Sebastien Coron, "Resistance against Differential Power Analysis for Elliptic Curve Cryptosystems", Cryptographic Hardware and Embedded System, CHES 1999, pp.292-302, LNCS 1717.
【非特許文献４】Sung-Ming Yen, Wei-Chih Lien, SangJae Moon, and JaeCheol Ha, "Power Analysis by Exploiting Chosen Message and Internal Collisions - Vulnerability of Checking Mechanism for RSA-Decryption", Mycrypt 2005. pp. 183-195, LNCS 3715.
【非特許文献５】STANDARDS FOR EFFICIENT CRYPTOGRAPHY, SEC 1: Elliptic Curve Cryptography, http://www.secg.org/download/aid-385/sec1＿final.pdf
【発明の概要】
【発明が解決しようとする課題】
【００５０】
しかしながら、上述したPKV方式に対して、Fault攻撃と呼ばれる攻撃手法を用いることで個人鍵を解読することができるという問題がある。ここで、Fault攻撃について説明する。図３７は、Fault攻撃の概要を示す図である。
【００５１】
図３７に示すように、このFault攻撃において、スマートカード等の組み込み機器に搭載された暗号回路は、様々なストレス（異常クロック、過電圧、高温度）が与えられる。このストレスによって暗号回路の内部データに異常値が発生し、この異常値に基づいて、暗号回路内の秘密情報が読み取られる。以下、PKV方式に対するFault攻撃について説明する。図３８は、PKV方式に対するFault攻撃の概要を示す図である。また、図３９は、PKV方式に対するFault攻撃において選択される点Aの一例を示す図である。また、図４０は、攻撃に対するリアルタイム性を示す図である。
【００５２】
PKV方式に対するFault攻撃は、図３８に示すように、上述した判定処理において真であると判定された点Aを、暗号回路に異常値を発生させることによって、A' = Q（4Q = O, 2Q ( O）を満たし、点Aとは異なる点A'に改ざんする。この改ざんによって、上述した特殊分岐PAが可能となる。なお、Fault攻撃の失敗率は、改ざんするビット数に比例するが、入力値の選択により改ざんするビット数を低減させることが可能である。以下、PKV方式に対するFault攻撃の具体例を示す。まず、攻撃者は、攻撃対象とする暗号回路に対し、affine座標で値を入力する場合、判定処理により真であると判定される点のうち、図３９に示すaffine座標において、Q = (Qx, Qy)に最も近い点A = (Ax, Ay)が入力される。入力した点Aが判定処理により真であると判定されると、攻撃者は、暗号回路にストレスを与え、点Aの座標データ(Ax, Ay)を(Qx, Qy)に改ざんする。これらの点は、affine座標において互いに近い場所にあることから、数ビットの変更により改ざんが可能である。また、同様の改ざんは、Jacobianなどの他の座標表現においても可能である。このように、PKV方式は、判定処理後の入力値の改ざんに対しては安全ではない。つまり、図４０に示すように、不正なデータの検出にリアルタイム性がない方式は、検出後に攻撃を行うことにより回避が可能となるため、リアルタイム性がある方式に比べて、攻撃に対する安全性が低い。
【００５３】
本発明は上述した問題点を解決するためになされたものであり、攻撃に対する安全性を向上させることができる楕円曲線演算処理装置、楕円曲線演算処理プログラム、楕円曲線演算処理方法を提供することを目的とする。
【課題を解決するための手段】
【００５４】
楕円曲線演算処理装置は、楕円曲線上の点の演算を行う装置であって、前記楕円曲線上の所定の点Aを前記楕円曲線演算処理装置に対する入力とし、ECDBL演算及びECADD演算によりスカラー値dのA倍点を算出する算出部と、前記算出部によるdのA倍点の算出において、前記ECDBL演算または前記ECADD演算の入力値または出力値が無限遠点であるかどうかを判断する判断部と、前記判断部により前記入力値または前記出力値が無限遠点であると判断された場合、前記算出部によるdのA倍点の算出を停止する停止部とを備える。
【００５５】
また、楕円曲線演算処理プログラムは、楕円曲線上の点の演算を行うプログラムであって、前記楕円曲線上の所定の点Aを前記楕円曲線演算処理プログラムに対する入力とし、ECDBL演算及びECADD演算によりスカラー値dのA倍点を算出する算出ステップと、前記算出ステップによるdのA倍点の算出において、前記ECDBL演算または前記ECADD演算の入力値または出力値が無限遠点であるかどうかを判断する判断ステップと、前記判断ステップにより前記入力値または前記出力値が無限遠点であると判断された場合、前記算出ステップによるdのA倍点の算出を停止する停止ステップとをコンピュータに実行させる。
【００５６】
また、楕円曲線演算処理方法は、楕円曲線上の点の演算を行う方法であって、前記楕円曲線上の所定の点Aを前記楕円曲線の点の演算に対する入力とし、ECDBL演算及びECADD演算によりスカラー値dのA倍点を算出する算出ステップと、前記算出ステップによるdのA倍点の算出において、前記ECDBL演算または前記ECADD演算の入力値または出力値が無限遠点であるかどうかを判断する判断ステップと、前記判断ステップにより前記入力値または前記出力値が無限遠点であると判断された場合、前記算出ステップによるdのA倍点の算出を停止する停止ステップとを備える。
【発明の効果】
【００５７】
攻撃に対する安全性を向上させることができる楕円曲線演算処理装置、楕円曲線演算処理プログラム、楕円曲線演算処理方法を提供することができる。
【図面の簡単な説明】
【００５８】
【図１】実施の形態１に係る楕円曲線暗号の装置のハードウェア構成を示す図である。
【図２】実施の形態１に係る楕円曲線演算処理装置の機能構成を示すブロック図である。
【図３】実施の形態１における点のスカラー倍算処理を示すフローチャートである。
【図４】素体楕円曲線パラメータによる点のスカラー倍算のアルゴリズムを示す図である。
【図５】ECDBL演算処理の動作を示すフローチャートである。
【図６】素体楕円曲線パラメータによるECDBL演算のアルゴリズムを示す図である。
【図７】ECADD演算処理の動作を示すフローチャーである。
【図８】素体楕円曲線パラメータによるECADD演算のアルゴリズムを示す図である。
【図９】2べき楕円曲線パラメータによるECDBL演算のアルゴリズムを示す図である。
【図１０】2べき楕円曲線パラメータによるECADD演算のアルゴリズムを示す図である。
【図１１】従来方式による効果と本発明による効果との比較を示す図である。
【図１２】実施の形態２における点のスカラー倍算のアルゴリズムを示す図である。
【図１３】実施の形態２におけるECADDDBL演算のアルゴリズムを示す図である。
【図１４】実施の形態３における点のスカラー倍算のアルゴリズムを示す図である。
【図１５】PAの概要を示す図である。
【図１６】RSA, ECCの演算の対応関係を示す図である。
【図１７】バイナリ法によるべき乗剰余演算のアルゴリズムを示す図である。
【図１８】バイナリ法によるべき乗剰余演算の概要を示す図である。
【図１９】バイナリ法によるべき乗剰余演算に対するPAの概要を示す図である。
【図２０】バイナリ法による点のスカラー倍算のアルゴリズムを示す図である。
【図２１】バイナリ法による点のスカラー倍算の概要を示す図である。
【図２２】バイナリ法による点のスカラー倍算に対するPAの概要を示す図である。
【図２３】A&D法を用いたバイナリ法によるべき乗剰余演算のアルゴリズムを示す図である。
【図２４】A&D法を用いたバイナリ法によるべき乗剰余演算に対するPAの概要を示す図である。
【図２５】A&D法を用いたバイナリ法による点のスカラー倍算のアルゴリズムを示す図である。
【図２６】A&D法を用いたバイナリ法による点のスカラー倍算に対するPAの概要を示す図である。
【図２７】RSAに対するメッセージ選択型PAの概要を示す図である。
【図２８】素体楕円曲線パラメータの点の加算演算のアルゴリズムを示す図である。
【図２９】素体楕円曲線パラメータの点の2倍算処理のアルゴリズムを示す図である。
【図３０】2べき楕円曲線パラメータの点の加算演算のアルゴリズムを示す図である。
【図３１】2べき楕円曲線パラメータの点の2倍算処理のアルゴリズムを示す図である。
【図３２】特殊分岐が発生するECDBL演算における電力波形と、特殊分岐が発生しないECDBL演算における電力波形とを示す図である。
【図３３】特殊分岐が発生するECADD演算における電力波形と、特殊分岐が発生しないECADD演算における電力波形とを示す図である。
【図３４】特殊分岐が発生した場合の点のスカラー倍算処理全体の電力波形を示す図である。
【図３５】A&D法を用いたECCに対する特殊分岐PAを示す図である。
【図３６】PKV処理のアルゴリズムを示す図である。
【図３７】Fault攻撃の概要を示す図である。
【図３８】PKV方式に対するFault攻撃の概要を示す図である。
【図３９】PKV方式に対するFault攻撃において選択される点Aの一例を示す図である。
【図４０】攻撃に対するリアルタイム性を示す図である。
【発明を実施するための形態】
【００５９】
以下、本発明の実施の形態について図面を参照しつつ説明する。
【００６０】
実施の形態１．
まず、本実施の形態に係る楕円曲線演算処理装置のハードウェア構成について説明する。図１は、本実施の形態に係る楕円曲線演算処理装置のハードウェア構成を示す図である。
【００６１】
図１に示すように、本実施の形態に係る楕円曲線演算処理装置10は、ECC（Elliptic Curve Cryptosystem）プロセッサ101、CPU（Central Processing Unit）102、ROM（Read-Only Memory）103、I/F104、EEROM（Electrically Erasable ROM）105、RAM（Random Access Memory）106と、これらを接続するデータバス107を備える。また、この楕円曲線演算処理装置10は、PAを行うために、消費電力を測定するオシロスコープ20がVcc及びGNDに接続されているものとする。ECCプロセッサ101は、暗号処理または電子署名処理に係る楕円曲線演算を行う。また、CPU102は、楕円曲線演算処理装置10を制御する。また、ROM103は、ECCプロセッサ101、CPU102により実行されるプログラムを格納する。また、I/F104は、楕円曲線演算処理装置10に対するデータの入出力を仲介する。また、EEROM105は、電気的にデータを消去可能なROMであり、ECCにおける個人鍵dを格納する。また、RAM106は、ECCプロセッサ101、CPU102により実行されるプログラムを一時的に格納する。
【００６２】
次に、本実施の形態に係る楕円曲線演算処理装置の機能構成について説明する。図２は、本実施の形態に係る楕円曲線演算処理装置の機能構成を示すブロック図である。
【００６３】
図２に示すように、本実施の形態に係る楕円曲線演算処理装置10は、判断部301、演算部302（算出部）、停止部303を機能として有する。演算部302は、ECCに係る演算を実行する。また、判断部301は、演算部302による演算に係る判断を行う。また、停止部303は、判断部301による判断に基づいて、演算部302による演算を停止させる。なお、これら各部は、ECCプロセッサ101、CPU102により実現される機能である。
【００６４】
本実施の形態に係る楕円曲線演算処理装置10は、楕円曲線上の点のスカラー倍算において、入力値または出力結果が無限遠点である場合、これを攻撃とみなし演算処理を停止する。以下、本実施の形態に係る楕円曲線演算処理装置10の動作について説明する。まず、楕円曲線演算処理装置10の全体動作について説明する。図３は、本実施の形態における点のスカラー倍算処理を示すフローチャートである。また、図４は、素体楕円曲線パラメータによる点のスカラー倍算のアルゴリズムを示す図である。なお、以降の説明において、Aは楕円曲線演算処理装置10に対する入力（楕円曲線上の所定の点）、dはスカラー値（個人鍵）、iはdのビット位置（初期値は最上位ビット位置でありuビットである場合i = u - ２）、diはi番目のビット値、かつdu-1=1、Oは無限遠点を示す。また、V[0]は入力値及び演算結果（出力値）を格納する配列変数、V[1]はECADD演算の演算結果を格納する配列変数とする。また、楕円曲線上の点はjacobian座標により表現されるものとする。
【００６５】
図３に示すように、まず、演算部302は、V[0]の初期値として、AをV[0]に代入する（S101）。これは、上述したように、点のスカラー倍算において、入力値が無限遠点である場合、演算処理が停止されることに起因する。つまり、無限遠点OではなくAをV[0]の初期値とすることにより、初期値Oによる演算処理の停止を防ぐことができる。
【００６６】
次に、演算部302は、dのi番目のビット(di)を選択し（S102）、V[0]を入力とするECDBL演算を実行してその結果をV[0]に代入する（S103, 算出ステップ）。次に、判断部301は、ECDBL演算による戻り値がERRORであるかどうかを判断する（S104, 判断ステップ）。
【００６７】
ECDBL演算による戻り値がERRORではない場合(S104, NO)、演算部302は、Aとv[0]とを入力とするECADD演算を実行してその結果をV[1]に代入する（S105, 算出ステップ）。次に、判断部301は、ECADD演算による戻り値がERRORであるかどうかを判断する（S106, 判断ステップ）。なお、ECDBL演算及びECADD演算については、ECDBL演算処理、ECADD演算処理として後述する。
【００６８】
ECADD演算による戻り値がERRORではない場合（S106, NO）、演算部302は、V[0]にV[di]を代入する（S107, 算出ステップ）。つまり、ビット値に応じて、V[0]に代入される値が決定する。次に、演算部302は、iから1を減算し（S108, 算出ステップ）、iが0以上かどうかを判断する（S109, 算出ステップ）。
【００６９】
iが0未満である場合（S109, NO）、演算部302は、V[0]を出力する（S110, 算出ステップ）。
【００７０】
一方、iが0以上である場合（S109, YES）、演算部302は、再度、dのi番目のビット(di)を選択する（S102）。
【００７１】
また、ステップS106において、ECADD演算による戻り値がERRORである場合（S106, YES）、停止部303は、スカラー倍算処理を停止する（S111, 停止ステップ）。
【００７２】
また、ステップS104において、ECBDL演算による戻り値がERRORである場合（S104, YES）、停止部303は、スカラー倍算処理を停止する（S111, 停止ステップ）。
【００７３】
これらの処理は、具体的には図４に示すアルゴリズムに相当する。このアルゴリズムにおいて、上述した点のスカラー倍算処理同様に、V[0] := Oによる初期化は行われず、代わりに3401の処理において、V[0] := Aによる初期化が行われる。また、V[0] := Aによる初期化を行いながら演算の整合性を保つための処理が、3402-3404において実行される。この処理は、di == 1を満たすiの最大値を求め、そのiに対して1を減算する処理である。これにより、dのビット値のうち、ビット値が1となる最上位ビットの1つ下位のビットからループ処理が開始される。また、3402-3404のループ処理において、ECDBL演算、ECADD演算の戻り値がERRORである場合、点のスカラー倍算処理が停止される。
【００７４】
次に、ECDBL演算処理について説明する。このECDBL演算処理は、図３におけるステップS103の処理に相当する。図５は、ECDBL演算処理の動作を示すフローチャーである。また、図６は、素体楕円曲線パラメータによるECDBL演算のアルゴリズムを示す図である。
【００７５】
図５に示すように、まず、演算部302は、V[0] = Oまたは2V[0] == Oであるかどうかを判断する（S201）。
【００７６】
V[0] = O、2V[0] == Oのいずれでもない場合（S201, NO）、つまりECDBL演算処理における入力値が無限遠点ではない場合、演算部302は、V[0]を入力とする点の2倍算演算を実行し（S202）、演算結果をV[0]へ代入する（S203）。
【００７７】
一方、V[0] == Oまたは2V[0] == Oである場合（S201, YES）、演算部302は、ERRORを戻り値として返す（S204）。
【００７８】
つまり、演算部302は、ECBDL演算処理における入力値または出力値が無限遠点である場合、ERRORを戻り値として出力する。
【００７９】
これらの処理は、具体的には図６に示すアルゴリズムに相当する。このアルゴリズムにおいて、3004の処理はステップS201, S204の処理に相当する。また、この3004の処理において、T2 == 0 or T3 == 0である場合は上述した特殊分岐4に相当し、then return ERROR;は特殊分岐4の発生による例外処理に相当する。
【００８０】
次に、ECADD演算処理について説明する。このECADD演算処理は、図３におけるステップS104の処理に相当する。図７は、ECADD演算処理の動作を示すフローチャーである。また、図８は、素体楕円曲線パラメータによるECADD演算のアルゴリズムを示す図である。
【００８１】
図７に示すように、まず、演算部302は、A == Oであるかどうかを判断する（S301）
【００８２】
A == Oではない場合（S301, NO）、演算部302は、V[0] == Oであるかどうかを判断する（S302）。
【００８３】
V[0] == Oではない場合（S302, NO）、演算部302は、点の加算演算1（図８における2901から2916の処理に相当）を実行し（S303）、A + V[0] == Oであるかどうかを判断する（S304）。
【００８４】
A + V[0] == Oではない場合（S304, NO）、演算部302は、点の加算演算2（図８における2918から2935の処理に相当）を実行し（S305）、演算結果をV[1]に代入する（S306）。
【００８５】
一方、A + V[0] == Oである場合（S304, YES）、演算部302は、ERRORを戻り値として出力する（S307）。これにより、ECADD演算処理における入力値または出力値が無限遠点である場合、点のスカラー倍算処理が停止される。
【００８６】
また、ステップS302において、V[0] == Oである場合（S302, YES）、演算部302は、ERRORを戻り値として出力する（S307）。
【００８７】
また、ステップS301において、A == Oである場合（S301, YES）、演算部302は、ERRORを戻り値として出力する（S307）。
【００８８】
つまり、演算部302は、ECADD演算処理における入力値または出力値が無限遠点である場合、ERRORを戻り値として出力する。
【００８９】
これらの処理は、具体的には図８に示すアルゴリズムに相当する。このアルゴリズムにおいて、2900の処理はステップS301, S302, S307の処理に相当する。また、この2900の処理において、Az == 0である場合、Bz == 0である場合は上述した特殊分岐1に相当し、then return ERROR;は特殊分岐1の発生による例外処理に相当する。また、2917の処理において、T1 == 0かつT2 == 0である場合は上述した特殊分岐3に相当し、else return ERROR;は特殊分岐3の発生による例外処理に相当する。
【００９０】
なお、図６及び図８に示したアルゴリズムは、素体楕円曲線パラメータによる点のスカラー倍算であるが、上述した処理は、2べき楕円曲線パラメータによる点のスカラー倍算にも適用可能である。以下、2べき楕円曲線パラメータを用いた場合のアルゴリズムについて説明する。図９は、2べき楕円曲線パラメータによるECDBL演算のアルゴリズムを示す図である。また、図１０は、2べき楕円曲線パラメータによるECADD演算のアルゴリズムを示す図である。
【００９１】
図５に示した処理は、2べき楕円曲線パラメータを用いた場合、具体的には図９に示すアルゴリズムに相当する。このアルゴリズムにおいて、3205の処理はステップS201, S204の処理に相当する。また、この3205の処理において、T1 == 0 or T3 == 0である場合は上述した特殊分岐4に相当し、then return ERROR;は特殊分岐4の発生による例外処理に相当する。
【００９２】
また、図７に示した処理は、2べき楕円曲線パラメータを用いた場合、具体的には図１０に示すアルゴリズムに相当する。このアルゴリズムにおいて、3100の処理はステップS301, S302, S307に相当する。また、この3100の処理において、Az == 0である場合、Bz == 0である場合は上述した特殊分岐1に相当し、then return ERROR;は特殊分岐1の発生による例外処理に相当する。また、3118の処理において、T1 == 0かつT2 == 0である場合は上述した特殊分岐3に相当し、else return ERROR;は特殊分岐3の発生による例外処理に相当する。
【００９３】
上述したように、特殊分岐（特殊分岐1,3,4）が発生した場合、つまり、ECBDL演算、ECADD演算のいずれかの演算において、入力値または出力値が無限遠点である場合、ERRORが出力される。またERRORが出力されることにより、EDBDL演算の処理だけでなく、その上位処理である点のスカラー倍算の処理全体が停止される。その結果として、楕円曲線演算処理装置10の消費電力の測定において、短い電力波形と長い電力波形が混在せず、長い電力波形のみが測定される。よって、これらの電力波形の違いを利用した特殊分岐PAによる攻撃を防ぐことができる。また、攻撃検知の判断は、従来のECDBL演算、ECADD演算において行われている判断と同様であることにより、攻撃の検知に必要な処理時間のオーバーヘッドをゼロにすることができる。さらに、点のスカラー倍算処理において高い頻度で繰り返されるECDBL演算、ECADD演算が実行されるたびに攻撃が検知されることにより、攻撃検知のリアルタイム性を向上させることができる。また、リアルタイム性が向上することにより、Fault攻撃のような所定のタイミングでデータの改ざんする攻撃を防ぐことができる。
【００９４】
以上のことから、本発明は従来方式に比べ、セキュリティ、処理時間、攻撃検知のリアルタイム性において優れている。図１１は、従来方式による効果と本発明による効果との比較を示す図である。
【００９５】
図１１に示すように、A&D法を用いたECCは、処理時間は高速であるが、上述したように、Qの入力による攻撃法に対しては脆弱であり、攻撃検知のリアルタイム性がない。また、PKV方式は、Qの入力による攻撃法に対しては安全であるが、処理時間は低速であり、攻撃検知のリアルタイム性がない。これに対して、本発明は、Qの入力による攻撃法に対して安全であり、処理時間が高速であり、攻撃検知のリアルタイム性がある。つまり、本発明によれば、Qの入力による攻撃法への脆弱性、処理時間、攻撃検知のリアルタイム性という従来のECCにおける課題を全て解決することができる。
【００９６】
実施の形態２．
本実施の形態に係る楕円曲線演算処理装置10は、そのハードウェア構成は実施の形態１と同様であるが、点のスカラー倍算において、ECDBL演算とECADD演算とが同時になされる手法（ECADDDBL演算）が用いられる点が、実施の形態１とは異なる。なお、このECADDDBL演算には素体楕円曲線パラメータ、jacobian座標が用いられる。以下、実施の形態１とは異なる動作について説明する。図１２は、本実施の形態における点のスカラー倍算のアルゴリズムを示す図である。また、図１３は、本実施の形態におけるECADDDBL演算のアルゴリズムを示す図である。
【００９７】
図１２に示すように、本実施の形態における点のスカラー倍算は、3501のV[0] := A;とともに、3502のV[1] := 2A;を初期化として実行する点が実施の形態１とは異なる。これは、ECDBL演算とECADD演算とが同時になされることに起因する。また、3507においてECADDDBL演算を実行し、このECADDDBL演算によりERRORが戻り値として返された場合に点のスカラー倍算全体の処理を停止する点が、実施の形態１とは異なる。
【００９８】
また、ECADDDBL演算は、図１３に示すように、y座標を計算せずにECDBL演算及びECADD演算を行うため、出力結果のy座標値Ry, Syに対する計算は行わない。また、点のスカラー倍算アルゴリズムは、Montgomery-Ladderと呼ばれる方法である。また、ECADDDBL演算の入力として、スカラー倍する対象の点のx座標Ixを用いる。
【００９９】
また、図１３に示すアルゴリズムにおける3305の処理において、T2 == O or T4 == Oである場合は、上述した特殊分岐1に相当し、then return ERROR;は特殊分岐1の発生による例外処理に相当する。また、3311の処理において、T3 == Oである場合は、上述した特殊分岐3に相当し、then return ERROR;は特殊分岐3の発生による例外処理に相当する。また、3334の処理において、T1 == Oである場合は、上述した特殊分岐4に相当し、then return ERROR;は特殊分岐4の発生による例外処理に相当する。
【０１００】
上述したように、本実施の形態に係る楕円曲線演算処理装置10において、実施の形態１と同様に、ECADDDBL演算により戻り値としてERRORが返されると、その上位処理である点のスカラー倍算処理において、処理全体が停止される。点のスカラー倍算処理において、ECDBL演算処理及びECADD演算処理の代わりにECADDDBL演算処理を実行することにより、テーブルメモリ領域と計算量を小さくすることができる。
【０１０１】
実施の形態３．
実施の形態１における点のスカラー倍算は、ECDBL演算1回ごとにECADD演算を1回実行していたが、本実施の形態における点のスカラー倍算は、window法を用いることにより、ECDBL演算をk回実行するごとにECADD演算を1回実行する。なお、本実施の形態におけるECDBL演算と、実施の形態1におけるECDBL演算との実行回数は同じである。つまり、window法を適用することにより、ECADD演算の実行頻度が低減する。以下、実施の形態１とは異なる動作について説明する。図１４は、本実施の形態における点のスカラー倍算のアルゴリズムを示す図である。
【０１０２】
図１４に示すように、window法を用いた点のスカラー倍算は、ECADD演算の頻度を下げるため、事前計算テーブルデータを作成する。この事前計算テーブルデータは、3601-3602の処理において作成され、W[x] = xA(0 < x < 2k)として与えられる。また、window法を用いた点のスカラー倍算において、(dik+k-1, …, dik)i ( 0を満たすiの最大値を求め、V:=W[(dik+k-1, …, dik)](無限遠点以外の点)による初期化処理が、3603-3605の処理により行われる。また、3606-3611のループ処理は、基本的には従来のwindow法と同じであるが、ECADD演算、ECDBL演算の戻り値がERRORである場合にスカラー倍算の処理を停止する点において異なる。
【０１０３】
上述したように、実施の形態１における点のスカラー倍算にwindow法を適用することによって、ECADD演算の実行回数が少なくなり、結果として、点のスカラー倍算に係る計算量を減らすことができる。
【０１０４】
なお、jacobian座標によるECDBL演算、ECADD演算について説明をしたが、これらの演算における特殊分岐の発生により点のスカラー倍算処理を停止するという処理は、投影座標、またはaffine座標によるECDBL演算、ECADD演算についても適用可能である。また、上述の実施の形態において、ECDBL演算、ECADD演算による戻り値がERRORである場合に点のスカラー倍算処理を停止したが、処理の停止の代わりにハードウェアリセットを行っても良い。さらに、楕円曲線演算処理装置10の不揮発性メモリ（例えばEEROM105）に攻撃検知を示すフラグを設けても良い。このフラグを設けることにより、ECDBL演算、ECADD演算による戻り値がERRORの場合にフラグをONにし、ハードウェアリセットによる再起動時にフラグがONである場合、装置自体が利用できないような処理を行うようにしても良い。また、上述した点のスカラー倍算のアルゴリズムは一例であり、無限遠点による初期化処理を行わない点のスカラー倍算のアルゴリズムに対し、本発明は適用可能である。つまり、初期化処理は無限遠点以外の任意の点によるものであれば良い。
【０１０５】
更に、本実施の形態における楕円曲線演算処理装置をコンピュータとして提供することができる。また、楕円曲線演算処理装置を構成するコンピュータにおいて上述した各ステップを実行させるプログラムを、楕円曲線演算処理プログラムとして提供することができる。上述したプログラムは、コンピュータにより読取り可能な記録媒体に記憶させることによって、楕円曲線演算処理装置を構成するコンピュータに実行させることが可能となる。ここで、上記コンピュータにより読取り可能な記録媒体としては、ＲＯＭやＲＡＭ等のコンピュータに内部実装される内部記憶装置、ＣＤ−ＲＯＭやフレキシブルディスク、ＤＶＤディスク、光磁気ディスク、ＩＣカード等の可搬型記憶媒体や、コンピュータプログラムを保持するデータベース、或いは、他のコンピュータ並びにそのデータベースや、更に回線上の伝送媒体をも含むものである。
【０１０６】
以上、本実施の形態によれば、以下の付記で示す技術的思想が開示されている。
（付記１） 楕円曲線上の点の演算を行う楕円曲線演算処理装置であって、
前記楕円曲線上の所定の点Aを前記楕円曲線上の点の演算に対する入力とし、ECDBL演算及びECADD演算によりスカラー値dのA倍点を算出する算出部と、
前記算出部によるdのA倍点の算出において、前記ECDBL演算または前記ECADD演算の入力値または出力値が無限遠点であるかどうかを判断する判断部と、
前記判断部により前記入力値または前記出力値が無限遠点であると判断された場合、前記算出部によるdのA倍点の算出を停止する停止部と
を備える楕円曲線演算処理装置。
（付記２） 付記１に記載の楕円曲線演算処理装置において、
点Aは、無限遠点ではない前記楕円曲線上の所定の点であることを特徴とする楕円曲線演算処理装置。
（付記３） 付記１または付記２に記載の楕円曲線演算処理装置において、
前記算出部は、前記ECDBL演算及び前記ECADD演算において、前記入力値または前記出力値が無限遠点である場合、ERRORを戻り値として出力することを特徴とし、
前記判断部は、前記戻り値がERRORである場合、前記入力値または前記出力値が無限遠点であると判断することを特徴とする楕円曲線演算処理装置。
（付記４） 付記１乃至付記３のいずれかに記載の楕円曲線演算処理装置において、
前記算出部は、A&D法を用いて、dのA倍点を算出することを特徴とする楕円曲線演算処理装置。
（付記５） 付記１乃至付記４のいずれかに記載の楕円曲線演算処理装置において、
前記算出部は、ECADDDBL演算を用いて、dのA倍点を算出することを特徴とする楕円曲線演算処理装置。
（付記６） 付記１乃至付記５のいずれかに記載の楕円曲線演算処理装置において、
前記算出部は、window法を用いて、dのA倍点を算出することを特徴とする楕円曲線演算処理装置。
（付記７） 楕円曲線上の点の演算を行う楕円曲線演算処理プログラムであって、
前記楕円曲線上の所定の点Aを前記楕円曲線上の点の演算に対する入力とし、ECDBL演算及びECADD演算によりスカラー値dによる点Aのd倍点を算出する算出ステップと、
前記算出ステップによる点Aのd倍点の算出において、前記ECDBL演算または前記ECADD演算の入力値または出力値が無限遠点であるかどうかを判断する判断ステップと、
前記判断ステップにより前記入力値または前記出力値が無限遠点であると判断された場合、前記算出ステップによる点Aのd倍点の算出を停止する停止ステップと
をコンピュータに実行させる楕円曲線演算処理プログラム。
（付記８） 付記７に記載の楕円曲線演算処理プログラムにおいて、
点Aは、無限遠点ではない前記楕円曲線上の所定の点であることを特徴とする楕円曲線演算処理プログラム。
（付記９） 付記７または付記８に記載の楕円曲線演算処理プログラムにおいて、
前記算出ステップは、前記ECDBL演算及び前記ECADD演算において、前記入力値または前記出力値が無限遠点である場合、ERRORを戻り値として出力することを特徴とし、
前記判断ステップは、前記戻り値がERRORである場合、前記入力値または前記出力値が無限遠点であると判断することを特徴とする楕円曲線演算処理プログラム。
（付記１０） 付記７乃至付記９のいずれかに記載の楕円曲線演算処理プログラムにおいて、
前記算出ステップは、A&D法を用いて、点Aのd倍点を算出することを特徴とする楕円曲線演算処理プログラム。
（付記１１） 付記７乃至付記１０のいずれかに記載の楕円曲線演算処理プログラムにおいて、
前記算出ステップは、ECADDDBL演算を用いて、点Aのd倍点を算出することを特徴とする楕円曲線演算処理プログラム。
（付記１２） 付記７乃至付記１１のいずれかに記載の楕円曲線演算処理プログラムにおいて、
前記算出ステップは、window法を用いて、点Aのd倍点を算出することを特徴とする楕円曲線演算処理プログラム。
（付記１３） 楕円曲線上の点の演算を行う楕円曲線演算処理方法であって、
前記楕円曲線上の所定の点Aを前記楕円曲線の点の演算に対する入力とし、ECDBL演算及びECADD演算によりスカラー値dによる点Aのd倍点を算出する算出ステップと、
前記算出ステップによる点Aのd倍点の算出において、前記ECDBL演算または前記ECADD演算の入力値または出力値が無限遠点であるかどうかを判断する判断ステップと、
前記判断ステップにより前記入力値または前記出力値が無限遠点であると判断された場合、前記算出ステップによる点Aのd倍点の算出を停止する停止ステップと
を備える楕円曲線演算処理方法。
（付記１４） 付記１３に記載の楕円曲線演算処理方法において、
点Aは、無限遠点ではない前記楕円曲線上の所定の点であることを特徴とする楕円曲線演算処理方法。
（付記１５） 付記１３または付記１４に記載の楕円曲線演算処理方法において、
前記算出ステップは、前記ECDBL演算及び前記ECADD演算において、前記入力値または前記出力値が無限遠点である場合、ERRORを戻り値として出力することを特徴とし、
前記判断ステップは、前記戻り値がERRORである場合、前記入力値または前記出力値が無限遠点であると判断することを特徴とする楕円曲線演算処理方法。
（付記１６） 付記１３乃至付記１５のいずれかに記載の楕円曲線演算処理方法において、
前記算出ステップは、A&D法を用いて、点Aのd倍点を算出することを特徴とする楕円曲線演算処理方法。
（付記１７） 付記１３乃至付記１６のいずれかに記載の楕円曲線演算処理方法において、
前記算出ステップは、ECADDDBL演算を用いて、点Aのd倍点を算出することを特徴とする楕円曲線演算処理方法。
（付記１８） 付記１３乃至付記１８のいずれかに記載の楕円曲線演算処理方法において、
前記算出ステップは、window法を用いて、点Aのd倍点を算出することを特徴とする楕円曲線演算処理方法。
【符号の説明】
【０１０７】
10 楕円曲線演算処理装置、20 オシロスコープ、101 ECCプロセッサ、102 CPU、103 ROM、104 I/F、105 EEROM、106 RAM、301 判断部、302 演算部、303 停止部。
【技術分野】
【０００１】
本発明は、情報セキュリティ技術に関する。
【背景技術】
【０００２】
情報化社会の発展に伴い、電子決済、住民基本台帳ネットワークなどの情報ネットワークを利用したサービスが普及することが予想される。このようなサービスを安全に運用するためには情報セキュリティ技術が必須である。また、この情報セキュリティの基盤技術として、公開鍵暗号方式が用いられる。公開鍵暗号方式として、RSA、楕円曲線暗号（以下、ECC: Elliptic Curve Cryptosystem）が主要な方式として知られている。これらの暗号を用いることによって、情報の暗号化、デジタル署名、認証機能を実現することができ、個人情報に対する第三者による不正なアクセスを防ぐことができる。
【０００３】
また、上述したようなサービスにおけるエンドユーザ側のデバイスとして、スマートカードが知られている。このスマートカードは、ICチップを搭載したカードであり、ICチップ内部のメモリ領域にユーザの秘密情報を格納している。また、スマートカードのICチップは、暗号化機能、デジタル署名機能、認証機能を搭載しており、これらの機能の処理において、ユーザの秘密情報が鍵として用いられる。この秘密情報は、カード内部のメモリ領域に格納されるため、第三者からの不正な覗き見に対する安全性、つまり耐タンパ性は、磁気記録型のカードに比べて高い。
【０００４】
しかし、このようなスマートカードに対する解析として、電力解析攻撃（Power Analysis, 以下PA）が知られている（例えば、非特許文献１参照）。以下、PAの概要に関して、図面を用いて説明する。図１５は、PAの概要を示す図である。
【０００５】
このPAは、図１５に示すように、ユーザの秘密情報Kを鍵とする暗号機能による処理（以下、暗号処理）の最中のスマートカードの消費電力を測定し、測定したデータを用いることで秘密情報Ｋを推定、解析する方法である。このPAは、電力の観察により解析を行う攻撃であるため、攻撃対象はスマートカードに限定されない。例えば、PDAデバイスに対して、電力消費時に発生する電磁波を測定するPAも知られている（例えば、非特許文献２参照）。つまり、PAは、電力を消費する組み込み機器全般を攻撃対象とする。
【０００６】
次に、RSA, ECCを用いる組み込み機器に対するPAについて詳述する。なお、このPAは、RSA, ECCの演算の仕組みを利用した攻撃であるため、まず、これらの演算について説明する。図１６は、RSA, ECCの演算の対応関係を示す図である。
【０００７】
RSA, ECCの演算には対応関係があり、この対応関係は図１６に示す通りである。以下、この対応関係を踏まえ、RSA, ECCの演算についてそれぞれ説明する。
【０００８】
まず、RSAの演算について説明する。RSAでは、べき乗剰余演算を用いた処理が行われる。このべき乗剰余演算は、基数a、指数x、法nに対して、z = ax(mod n)を計算する演算である。RSAにおいて、このべき乗剰余演算により、ｘを秘密情報とした処理が行われる。例えば、RSA暗号の復号処理は、暗号文をc、個人鍵をdとした場合、m=cd(mod n)を満たすmを求める処理である。また、RSAによる電子署名においては、署名対象データc、個人鍵d、法nに対して、上述した計算を行うことにより、電子署名mが得られる。いずれの処理においても、個人鍵dを知らない第三者は、正しい復号処理結果、電子署名処理結果を得ることができない。
【０００９】
次に、ECCの演算について説明する。ECCにおいて、以下に示すx, yの関係式を楕円曲線と呼ぶ。この楕円曲線は、主に素体（prime field）と2べき（binary field）の2種類からなる。また、楕円曲線を一意に決定するためのパラメータa, bを楕円曲線パラメータと呼ぶ。楕円曲線（素体）は、pを素数とした場合、y2 = x3 + ax + b(mod p)として表される。なお、この式において、pは素数であり、0 ≦ a, b ＜ ｐである。また、楕円曲線（2べき）は、y2 + xy = x3 + ax2 + b(mod f(x))として表される。なお、この式において、fはGF（2m）の多項式であり、a, b ⊆ GF(2m)である。また、上述した楕円曲線（素体）、楕円曲線（2べき）を表す関係式を満たす(x, y)を楕円曲線上の点（elliptic point）と呼ぶ。
【００１０】
ECCでは、点のスカラー倍算（Elliptic Scalar Multiplication）を用いた処理が行われる。この点のスカラー倍算は、楕円曲線上の点A、スカラー値と呼ばれる整数sに対して、V = sAを満たす楕円曲線上の点Vを計算する演算である。例えば、ECCにおけるECDH鍵交換は、通信相手の公開鍵となる楕円曲線上の点をA、個人鍵をdとすると、V = dAを満たす楕円曲線上の点Vを計算することで、安全な鍵共有を実現する。個人鍵dの値を知らない第三者は、正しい共有鍵の値を算出することができない。
【００１１】
上述したRSA暗号、RSAによる電子署名、ECC暗号において、個人鍵dは、暗号に対する攻撃を行う第三者（以下、攻撃者と呼称する）に漏洩してはならない値である。つまり、RSA, ECCにおいて、dの値の保護が重要な耐タンパ機能となる。数学的には、d以外の値が攻撃者に知られていたとしても、これらの値からdの値を計算するための計算量が大きすぎるため、現実的な時間内にdの値を求めることが困難であることが知られている。例えば、RSA暗号の復号処理において、nが1024bit以上の値である場合、攻撃者はc, n, mの値を知っていたとしてもdの値を求めることが困難であることが知られている。また、ECCの復号処理において、楕円曲線パラメータが160bit以上である場合、攻撃者はA, Vの値を知っていたとしてもdの値を求めることが困難であることが知られている。
【００１２】
上述したように、RSA，ECCにおいて個人鍵dの値は数学的に求めることが困難であるが、PAを用いることにより容易に解読することが知られている。このPAの基本メカニズムは、RSAにおけるべき乗剰余演算、ECCにおける点のスカラー倍算と大きな関連がある。よって、これらの演算手順について説明したうえで、RSAに対するPA、ECCに対するPAについてそれぞれ説明する。
【００１３】
まず、RSAにおけるべき乗剰余演算の演算手順と、RSAに対するPAについて説明する。図１７は、バイナリ法によるべき乗剰余演算のアルゴリズムを示す図である。また、図１８は、バイナリ法によるべき乗剰余演算の概要を示す図である。また、図１９は、バイナリ法によるべき乗剰余演算に対するPAの概要を示す図である。
【００１４】
RSA（RSA暗号、RSAによる電子署名）におけるべき乗剰余演算において、n, c,dの全てがそれぞれ1024bit以上の長さを持つ場合、べき乗剰余演算を数式通りに計算した場合、(mod n)を用いた掛け算をd回必要とする。この演算は21024以上の計算量を必要とするため現実的ではない。そこで、この計算量をlog2dに削減するための演算方法としてバイナリ法が知られている。以下、べき乗剰余におけるバイナリ法について説明する。このバイナリ法では、図１７に示すように、u-bitの個人鍵dをd = du-1||…||d1||d0（ただし、diは1-bit値）と表したとき、diのビット値が上位ビットから下位ビットの順（即ち、i = u - 1からi = 0の順）にスキャンされる。そして、diのビット値に応じて演算が行われる。di == 1の場合、2乗算（図１７におけるv := v × v(mod n)）の後に乗算（図１７におけるv := v × a(mod n)）が実行される。一方、di == 0の場合、2乗算のみが実行される。即ち、図１８に示す2乗算及び乗算の演算シーケンスが、そのままdiのビット値と連動しており、RSAに対するPAは、この性質を利用してdを解読する。
【００１５】
RSAに対するPAは、図１９に示すように、上述したバイナリ法の処理を実行するデバイスにおける消費電力を測定し、乗算処理と2乗算処理との電力波形の違いを区別することにより個人鍵dを解読する。2乗算のあとに乗算を実行している場合はdのビット値は1と解読され、2乗算のみを実行しているならばdのビット値は0と解読される。この解読がdの全ビットに対して行われることで、RSAに対するPAが成功する。
【００１６】
次に、ECCにおける点のスカラー倍算の演算手順と、ECCに対するPAについて説明する。図２０は、バイナリ法による点のスカラー倍算のアルゴリズムを示す図である。また、図２１は、バイナリ法による点のスカラー倍算の概要を示す図である。また、図２２は、バイナリ法による点のスカラー倍算に対するPAの概要を示す図である。
【００１７】
RSAにおけるべき乗剰余演算と同様に、点のスカラー倍算についても、その演算量を削減するための演算方法としてバイナリ法が知られている。以下、スカラー倍算におけるバイナリ法について説明する。このバイナリ法では、図２０に示すように、u-bitの個人鍵dをd = du-1||…||d1||d0（ただし、diは1-bit値）と表したとき、diのビット値が上位ビットから下位ビットの順（即ち、i = u - 1からi = 0の順）にスキャンされる。そして、diのビット値に応じて演算が行われる。di == 1の場合、点の2倍算（図２０におけるV := 2V。以下、ECDBL: Elliptic Curve Doubling）の後に点の加算（図２０におけるV := V + A。以下、ECADD: Elliptic Curve Addition）が実行される。一方、di == 0の場合、ECDBLのみが実行される。即ち、図２１に示すECDBL及びECADDの演算シーケンスが、そのままdiのビット値と連動しており、ECCに対するPAは、この性質を利用してdを解読する。
【００１８】
ECCに対するPAは、図２２に示すように、上述したバイナリ法の処理を実行するデバイスにおける消費電力を測定し、ECDBLとECADDとの処理による電力波形の違いを区別することにより個人鍵dを解読する。ECDBLのあとにECADDを実行している場合はdのビット値は1と解読され、ECDBLのみを実行しているならばdのビット値は0と解読される。この解読がdの全ビットに対して行われることで、ECCに対するPAが成功する。
【００１９】
上述したRSAに対するPA及びECCに対するPAは、dのビット値を決定する処理の種類を、処理を実行するデバイスの消費電力の電力波形に基づいて特定することにより個人鍵dを解読する。なお、これらのPAに対する対策法として、Add-and-double-allways法（以下、A&D法）が知られている（例えば、非特許文献３参照）。以下、A&D法によるRSAに対するPAへの対策法、A&D法によるECCに対するPAへの対策法についてそれぞれ説明する。
【００２０】
まず、A&D法によるRSAに対するPAへの対策法について説明する。図２３は、A&D法を用いたバイナリ法によるべき乗剰余演算のアルゴリズムを示す図である。また、図２４は、A&D法を用いたバイナリ法によるべき乗剰余演算に対するPAの概要を示す図である。
【００２１】
図２３に示すように、A&D法を用いたべき乗剰余演算は、常にv[0]に計算結果を格納しながら実行される。また、1206の処理において、dのビット値diが0の場合でも乗算が実行される。この乗算の結果は、1208の処理において、di = 1の場合、v[0]に格納され、次のループで使用される。一方、di = 0の場合、1206の処理における乗算の結果は、v[0]に格納されず、代わりに1024の処理における2乗算結果がv[0]に格納され次のループで使用される。つまり、1206の処理における乗算は、diの値に関係なく実行されるが、その演算結果が次のループにおける計算に用いられるのは、di = 1の場合のみである。このような処理によれば、図２４に示すように、diの値にかかわらず、バイナリ法によるべき乗剰余演算を実行するデバイスの消費電力の電力波形は一定となる。これにより、乗算処理と２乗算処理との電力波形の違いを利用したPAを防ぐことができる。また、di = 1の場合にのみ、乗算結果が次のループで用いられることにより、べき乗剰余演算の整合性が保たれる。
【００２２】
次に、A&D法によるECCに対するPAへの対策法について説明する。図２５は、A&D法を用いたバイナリ法による点のスカラー倍算のアルゴリズムを示す図である。また、図２６は、A&D法を用いたバイナリ法による点のスカラー倍算に対するPAの概要を示す図である。
【００２３】
図２５に示すように、A&D法を用いたバイナリ法による点のスカラー倍算は、常にV[0]に計算結果を格納しながら実行される。また、1406の処理において、dのビット値diが0の場合でもECADDが実行される。また、1408のdiの値に応じたV[0]へのコピー処理において、di = 0の場合は1404の処理によるECDBL結果がV[0]に格納される。また、di = 1の場合は1406の処理によるECADD結果がV[0]に格納される。このように演算結果が格納されたV[0]が次のループにおける計算に用いられる。このような処理によれば、図２６に示すように、diの値にかかわらず、バイナリ法による点のスカラー倍算を実行するデバイスの消費電力の電力波形は一定となる。これにより、点の2乗算処理とECADD処理との電力波形の違いを利用するPAを防ぐことができる。
【００２４】
しかし、上述したA&D法によるPAへの対策法に対するさらに高度な攻撃法として、メッセージ選択型PAが知られている（例えば、非特許文献４参照）。以下、RSAに対するメッセージ選択型PA、ECCに対するメッセージ選択型PAについてそれぞれ説明する。
【００２５】
まず、RSAに対するメッセージ選択型PAについて説明する。図２７は、RSAに対するメッセージ選択型PAの概要を示す図である。
【００２６】
上述したRSAに対するPAは、べき乗剰余ad(mod n)を計算する際、ランダムなaを入力し、その処理における消費電力波形を観測することで個人鍵dを解読する攻撃法である。これに対し、RSAに対するメッセージ選択型PAは、aとして特殊な値を選択して入力する点が異なる。この方法によれば、A&D法が用いられたRSAに対しても攻撃を成功させることができる。具体的には、a = -1(mod n)を入力することで、図２７に示すように、diの値によって電力波形の違いが生じ、この電力波形の違いに基づいてdiの値を識別することで、個人鍵dを解読することが可能となる。なお、ループ変数iにおける２乗算（図２３における1204の処理）の種類と、diの値との対応関係は、２乗算が1×1の場合di+1 = 0であり、２乗算が(-1)×(-1)の場合di+1 = 1である。なお、この対応関係は、図２３に示したアルゴリズムに起因する。di = 0の場合、1204の処理による２乗算結果（(-1)×（-1） = 1）が1208の処理によりv[0]にコピーされるため、次のループにおいて計算される２乗算は1×1となる。一方、di = 1の場合、1204の処理による２乗算結果（1×(-1) = -1）が1208の処理によりv[0]にコピーされるため、次のループにおいて計算される２乗算は(-1)×(-1)となる。このように、メッセージ選択型PAによれば、A&D法を用いたRSAにおける個人鍵dの解読が可能となる。
【００２７】
次に、ECCに対するメッセージ選択型PAについて説明する。この上述したメッセージ選択型PAをECCに適用した攻撃法について説明するため、まず、ECCにおける点の加算、点の2倍算の演算手順における無限遠点について説明する。なお、以降に示すECCは、A&D法を用いたECCである。図２８は、素体楕円曲線パラメータの点の加算演算のアルゴリズムを示す図である。また、図２９は、素体楕円曲線パラメータの点の2倍算処理のアルゴリズムを示す図である。また、図３０は、2べき楕円曲線パラメータの点の加算演算のアルゴリズムを示す図である。また、図３１は、2べき楕円曲線パラメータの点の2倍算処理のアルゴリズムを示す図である。
【００２８】
図２８〜図３１に示す点の加算演算、または点の2倍算処理のアルゴリズムにおいて、点の座標は3次元形式（X, Y, Z）により表現される。また、無限遠点は、Z座標が0の点、つまりZ = 0として表現され、この無限遠点をOとすると、任意の点Aに対して、A + O = O + A = Aが満たされるような点である。図２８〜３１に示すアルゴリズムは、いずれも無限遠点に関連した処理を含んでいる。この処理は、入力値、または出力値が無限遠点である場合の処理である例外処理を含む。この例外処理は、図２８の800, 817の処理、図２９の904の処理、図３０の1000, 1018の処理、図３１の1105の処理である。以下、例外処理が実行される場合の分岐を特殊分岐として説明する。
【００２９】
図２８の800の処理、図３０の1000の処理は、A + B（B = ECDBL(V)）の計算において、点Aが無限遠点である場合(Az == 0)、点Bを計算結果として出力し、点Bが無限遠点である場合(Bz == 0)、つまり、点Aまたは点Bが無限遠点である場合（特殊分岐１）、無限遠点ではない方の点を計算結果として出力する。
【００３０】
また、A + Bの計算において、A == Bである場合（特殊分岐２）、A + Bの計算処理から2Aの計算処理（ECDBL(A)）を実行する。特殊分岐２として、図２８の817の処理においてT4 == 0かつT5 == 0である場合、もしくは図３０の1018においてT1 == 0かつT2 == 0である場合が挙げられる。
【００３１】
また、A + Bの計算において、計算結果が無限遠点である場合（特殊分岐３）、無限遠点である座標(1, 1, 0)を計算結果として出力する。特殊分岐３として、図２８の817の処理においてT4 == 0かつT5 ( 0である場合、もしくは図３０の1018においてT1 == 0かつT2 ( 0である場合が挙げられる。
【００３２】
また、2Aの計算において、入力データとしての点Aが無限遠点である場合、もしくは、出力データとしての2Aが無限遠点である場合（特殊分岐４）、無限遠点である座標(1, 1, 0)を計算結果として出力する。特殊分岐４のうち、入力データとしての点Aが無限遠点である場合は、図２９の904または図３１の1105の処理においてT3 == 0である場合に相当する。また、出力データとしての2Aが無限遠点である場合は、図２９の904の処理においてT2 == 0である場合、図３１の1105の処理においてT1 == 0である場合に相当する。
【００３３】
以上のことを踏まえた上で、ECCに対するメッセージ選択型PAについて説明する。上述したメッセ−ジ選択型PAにおける特殊な値a = -1に対応する楕円曲線上の点は、2A = OかつA ( Oを満たす点Ａであることが知られている。これは、a = -1を満たすaはa2 = 1かつa ( 1を満たす値であり、この値を楕円曲線の演算に対応させると2A = OかつA ( Oを満たすＡとなることに起因する。また、ECCに対するメッセージ選択型PAにおいて、A = Pが点のスカラー倍算の入力として用いられる。ここでこのPは点Aと異なる点であり、2P = OかつP ( Oを満たし、楕円曲線パラメータが素体の場合にY座標が0となり、楕円曲線パラメータが２べきである場合にX座標が0となるような点の値とする。
【００３４】
A = Pを点のスカラー倍算の入力とすると、図２５に示した1404の処理におけるECDBL演算によって2P = Oとなり、Pの偶数倍点は常に無限遠点Oとなる。よって、V[0]に格納される値は常に無限遠点Oとなる。1404の処理におけるECDBL演算が図２９（演算曲線パラメータが素体の場合）、もしくは図３１（楕円曲線パラメータが２べきの場合）に示したアルゴリズムにより実行された場合、いずれも特殊分岐４により無限遠点である座標(1, 1, 0)が計算結果として出力されECDBL演算処理が終了する。つまり、A = Pを点のスカラー倍算の入力とすると、特殊分岐が発生することによりECDBL演算処理が終了し、メイン演算がなされない。よって、特殊分岐が発生するECDBL演算における電力波形は、特殊分岐が発生しないECDBL演算における電力波形と異なる。
【００３５】
図３２は、特殊分岐が発生するECDBL演算における電力波形と、特殊分岐が発生しないECDBL演算における電力波形とを示す図である。上述したように、特殊分岐が発生することにより途中でECDBL演算処理が中断されるため、図３２に示すように、特殊分岐が発生しないECDBL演算処理に比べて、その電力波形が短くなる。
【００３６】
また、A = Pを点のスカラー倍算の入力とすると、図２５に示した1404の処理におけるECDBL演算の結果としてV[0]に無限遠点が与えられる。このため、図２５に示した1406の処理において、常にECADD(O, P)の演算が実行される。ECADD演算の入力の片方が無限遠点の場合、特殊分岐１によりメイン演算がなされずにECADD演算処理が終了する。具体的には、図３０に示した1000の処理における特殊分岐、または図２８に示した800の処理における特殊分岐によりECADD演算処理が終了する。よって、特殊分岐が発生するECADD演算における電力波形は、特殊分岐が発生しないECADD演算における電力波形と異なる。
【００３７】
図３３は、特殊分岐が発生するECADD演算における電力波形と、特殊分岐が発生しないECADD演算における電力波形とを示す図である。上述したように、特殊分岐が発生することにより途中でECDBL演算処理が中断されるため、図３３に示すように、特殊分岐が発生しないECDBL演算処理に比べて、その電力波形が短くなる。
【００３８】
上述したように、A = Pを点のスカラー倍算の入力とすることで、ECDBL演算及びECADD演算において特殊分岐が発生する。以下、特殊分岐が発生した場合の点のスカラー倍算処理全体の電力波形について説明する。図３４は、特殊分岐が発生した場合の点のスカラー倍算処理全体の電力波形を示す図である。
【００３９】
図３４に示すように、点のスカラー倍算に対する入力をA = Pとした場合、点のスカラー倍算処理全体の電力波形は、ECADD演算及びECADD演算における特殊分岐による電力波形が交互に現れる波形となる。A&D法を用いたECCに対するメッセージ選択型PAにおいては、上述したA&D法を用いたRSAに対するメッセージ選択型PAにおける1×1，(-1)×（-1）に対応する処理が実行されない。よって、スカラー値dのビット値を識別するためのパターンが電力波形に現れず、結果として個人鍵の解読は失敗する。
【００４０】
しかし、上述したメッセージ選択型PAとは異なるメッセージ選択型PA（以下、特殊分岐PA）によりA&D法を用いたECCにおける個人鍵の解読が可能となる。この特殊分岐PAは、本発明者独自の分析によるものである。以下、特殊分岐PAについて説明する。
【００４１】
特殊分岐PAは、A = Qを点のスカラー倍算の入力とする。ここでQは、4Q = Oかつ2Q ( Oを満たす点である。図２５に示したA&D法を用いた点のスカラー倍算にA = Qが入力されると、ループ変数iにおけるECDBL演算の処理は、di+1の値に応じて実行される。di+1 == 0である場合、所定の整数kに関して、ECDBL((2k)Q)の演算が行われる。つまり、Qの偶数倍点に対するECDBL演算が実行されることにより演算結果が(4k)Q = Oとなり、特殊分岐が発生しECDBL演算が終了し、V[0] = Oとなる。一方、di+1 == 1である場合、所定の整数kに関して、ECDBL((2k + 1)Q)の演算が行われる。つまり、Qの奇数倍点に対するECDBLが実行されることにより演算結果が(4k + 2)Q ( Oとなり、特殊分岐は発生せずECDBL演算における全ての演算が実行されて終了し、V[0] = (4k + 2)Q = 2Qとなる。
【００４２】
また、上述したECDBL演算と同様に、ループ変数iにおけるECADD演算の処理もまた、di+1の値に応じて実行される。di+1 == 0である場合、ECDBL演算の結果がV[0]=Oであるため、ECADD(O, Q)の演算が行われる。この演算において、ECADDの片方の入力が無限遠点であるため、特殊分岐が発生し、処理が終了する。一方、di+1 == １である場合、ECDBL演算の結果がV[0] = 2Qであるため、ECADD(2Q, Q)の演算が行われる。この演算において、ECADD演算の両方の入力とも無限遠点ではないため、特殊分岐が発生せず、ECADD演算における全ての演算が実行されて処理が終了する。
【００４３】
以上のことから、ECDBL演算処理内容とdi+1のビット値の相関関係が正しければ、ECDBL演算処理結果に基づくECADD演算処理内容とdi+1のビット値の相関関係も正しくなることは自明である。以下、ECDBL演算処理内容とdi+1のビット値の相関関係について説明する。
【００４４】
ループ変数iのとき、図２５に示した1408のコピー処理（V[0] = V[di];）により、V[0]にコピーされる値はdiの値に応じて変化する。di == 0である場合、1404のV[0]のECDBL演算結果はQの偶数倍点であり、V[0]にコピーされる値は、2kQとなる。一方、di == 1である場合、1406のV[1]のECADD演算結果はQの偶数倍点+Qであり、V[0]にコピーされる値は(2k + 1)Qとなる。このように、di == 0である場合、またはdi == 1である場合それぞれにおけるV[0]の値が、次のループ、すなわちループ変数がi - 1となる時点におけるECDBL(V[0])演算の入力となる。よって、上述したECDBL演算処理内容とdi+1のビット値の相関関係が導出される。
【００４５】
以上の相関関係から、A = Qを点のスカラー倍算の入力とすることで、di+1 == 0である場合、ECDBL演算、ECADD演算ともに特殊分岐により処理が終了するという相関があることがわかる。また、di+1 == 1である場合、ECDBL演算、ECADD演算ともに全ての演算が実行されて処理が終了するという相関があることがわかる。つまり、この相関関係に基づいて、diの値を電力波形から推定することができる。図３５は、A&D法を用いたECCに対する特殊分岐PAを示す図である。
【００４６】
図３５に示すように、diの値と次のループにおけるECDBL演算、及びECADD演算の電力波形に相関関係があるため、A = Qを入力とする点のスカラー倍算処理を実行するデバイスの電力波形から個人鍵dを解読することができる。
【００４７】
しかし、上述した特殊分岐PAによる個人鍵の解読を防ぐ技術として、公開鍵確認（以下、PKV: Public Key Validation）が知られている（例えば、非特許文献５参照）。PKV及びA&D法を用いたECC（以下、PKV方式）によれば、4Q = Oかつ2Q ( Oを満たす点Qを、点のスカラー倍算の入力として用いられることが防がれる。図３６は、PKV処理のアルゴリズムを示す図である。
【００４８】
PKVは、スカラー倍算する点Aが、暗号演算に用いるために正しい値であるかどうかを、数学的関係に基づいて判定するアルゴリズムである。具体的には図３６に示すようにPKVを用いた判定処理が事前処理として用いられ、この判定処理において真である（valid）と判定された点Aのみが点のスカラー倍算に入力される。PKVによって真であると判定された点Aに対してd倍算処理による点のスカラー倍算処理がなされた場合、位数をrとすると、d < rが満たされる限りは、ECADD演算処理及びECDBL演算処理において常に全ての演算が実行されることが知られている。つまり、暗号処理におけるスカラー値dが常にd < rを満たすことにより、点のスカラー倍算において特殊分岐は発生しない。その結果として、PKV方式に対する特殊分岐PAが不可能となる。
【先行技術文献】
【非特許文献】
【００４９】
【非特許文献１】P.Kocher, J,Jaffe and B.Jun "Differential Power Anaysis", Crypto'99, LNCS 1666, pp.388-397, Springer-Verlag, 1999.
【非特許文献２】Catherine H. Gebotys, Simon Ho, and C.C. Tiu, "EM Analysis of Rijndael and ECC on a Wireless Java-Based PDA", Cryptographic Hardware and Embedded System, CHES 2005, pp.250-264, LNCS 3659.
【非特許文献３】Jean-Sebastien Coron, "Resistance against Differential Power Analysis for Elliptic Curve Cryptosystems", Cryptographic Hardware and Embedded System, CHES 1999, pp.292-302, LNCS 1717.
【非特許文献４】Sung-Ming Yen, Wei-Chih Lien, SangJae Moon, and JaeCheol Ha, "Power Analysis by Exploiting Chosen Message and Internal Collisions - Vulnerability of Checking Mechanism for RSA-Decryption", Mycrypt 2005. pp. 183-195, LNCS 3715.
【非特許文献５】STANDARDS FOR EFFICIENT CRYPTOGRAPHY, SEC 1: Elliptic Curve Cryptography, http://www.secg.org/download/aid-385/sec1＿final.pdf
【発明の概要】
【発明が解決しようとする課題】
【００５０】
しかしながら、上述したPKV方式に対して、Fault攻撃と呼ばれる攻撃手法を用いることで個人鍵を解読することができるという問題がある。ここで、Fault攻撃について説明する。図３７は、Fault攻撃の概要を示す図である。
【００５１】
図３７に示すように、このFault攻撃において、スマートカード等の組み込み機器に搭載された暗号回路は、様々なストレス（異常クロック、過電圧、高温度）が与えられる。このストレスによって暗号回路の内部データに異常値が発生し、この異常値に基づいて、暗号回路内の秘密情報が読み取られる。以下、PKV方式に対するFault攻撃について説明する。図３８は、PKV方式に対するFault攻撃の概要を示す図である。また、図３９は、PKV方式に対するFault攻撃において選択される点Aの一例を示す図である。また、図４０は、攻撃に対するリアルタイム性を示す図である。
【００５２】
PKV方式に対するFault攻撃は、図３８に示すように、上述した判定処理において真であると判定された点Aを、暗号回路に異常値を発生させることによって、A' = Q（4Q = O, 2Q ( O）を満たし、点Aとは異なる点A'に改ざんする。この改ざんによって、上述した特殊分岐PAが可能となる。なお、Fault攻撃の失敗率は、改ざんするビット数に比例するが、入力値の選択により改ざんするビット数を低減させることが可能である。以下、PKV方式に対するFault攻撃の具体例を示す。まず、攻撃者は、攻撃対象とする暗号回路に対し、affine座標で値を入力する場合、判定処理により真であると判定される点のうち、図３９に示すaffine座標において、Q = (Qx, Qy)に最も近い点A = (Ax, Ay)が入力される。入力した点Aが判定処理により真であると判定されると、攻撃者は、暗号回路にストレスを与え、点Aの座標データ(Ax, Ay)を(Qx, Qy)に改ざんする。これらの点は、affine座標において互いに近い場所にあることから、数ビットの変更により改ざんが可能である。また、同様の改ざんは、Jacobianなどの他の座標表現においても可能である。このように、PKV方式は、判定処理後の入力値の改ざんに対しては安全ではない。つまり、図４０に示すように、不正なデータの検出にリアルタイム性がない方式は、検出後に攻撃を行うことにより回避が可能となるため、リアルタイム性がある方式に比べて、攻撃に対する安全性が低い。
【００５３】
本発明は上述した問題点を解決するためになされたものであり、攻撃に対する安全性を向上させることができる楕円曲線演算処理装置、楕円曲線演算処理プログラム、楕円曲線演算処理方法を提供することを目的とする。
【課題を解決するための手段】
【００５４】
楕円曲線演算処理装置は、楕円曲線上の点の演算を行う装置であって、前記楕円曲線上の所定の点Aを前記楕円曲線演算処理装置に対する入力とし、ECDBL演算及びECADD演算によりスカラー値dのA倍点を算出する算出部と、前記算出部によるdのA倍点の算出において、前記ECDBL演算または前記ECADD演算の入力値または出力値が無限遠点であるかどうかを判断する判断部と、前記判断部により前記入力値または前記出力値が無限遠点であると判断された場合、前記算出部によるdのA倍点の算出を停止する停止部とを備える。
【００５５】
また、楕円曲線演算処理プログラムは、楕円曲線上の点の演算を行うプログラムであって、前記楕円曲線上の所定の点Aを前記楕円曲線演算処理プログラムに対する入力とし、ECDBL演算及びECADD演算によりスカラー値dのA倍点を算出する算出ステップと、前記算出ステップによるdのA倍点の算出において、前記ECDBL演算または前記ECADD演算の入力値または出力値が無限遠点であるかどうかを判断する判断ステップと、前記判断ステップにより前記入力値または前記出力値が無限遠点であると判断された場合、前記算出ステップによるdのA倍点の算出を停止する停止ステップとをコンピュータに実行させる。
【００５６】
また、楕円曲線演算処理方法は、楕円曲線上の点の演算を行う方法であって、前記楕円曲線上の所定の点Aを前記楕円曲線の点の演算に対する入力とし、ECDBL演算及びECADD演算によりスカラー値dのA倍点を算出する算出ステップと、前記算出ステップによるdのA倍点の算出において、前記ECDBL演算または前記ECADD演算の入力値または出力値が無限遠点であるかどうかを判断する判断ステップと、前記判断ステップにより前記入力値または前記出力値が無限遠点であると判断された場合、前記算出ステップによるdのA倍点の算出を停止する停止ステップとを備える。
【発明の効果】
【００５７】
攻撃に対する安全性を向上させることができる楕円曲線演算処理装置、楕円曲線演算処理プログラム、楕円曲線演算処理方法を提供することができる。
【図面の簡単な説明】
【００５８】
【図１】実施の形態１に係る楕円曲線暗号の装置のハードウェア構成を示す図である。
【図２】実施の形態１に係る楕円曲線演算処理装置の機能構成を示すブロック図である。
【図３】実施の形態１における点のスカラー倍算処理を示すフローチャートである。
【図４】素体楕円曲線パラメータによる点のスカラー倍算のアルゴリズムを示す図である。
【図５】ECDBL演算処理の動作を示すフローチャートである。
【図６】素体楕円曲線パラメータによるECDBL演算のアルゴリズムを示す図である。
【図７】ECADD演算処理の動作を示すフローチャーである。
【図８】素体楕円曲線パラメータによるECADD演算のアルゴリズムを示す図である。
【図９】2べき楕円曲線パラメータによるECDBL演算のアルゴリズムを示す図である。
【図１０】2べき楕円曲線パラメータによるECADD演算のアルゴリズムを示す図である。
【図１１】従来方式による効果と本発明による効果との比較を示す図である。
【図１２】実施の形態２における点のスカラー倍算のアルゴリズムを示す図である。
【図１３】実施の形態２におけるECADDDBL演算のアルゴリズムを示す図である。
【図１４】実施の形態３における点のスカラー倍算のアルゴリズムを示す図である。
【図１５】PAの概要を示す図である。
【図１６】RSA, ECCの演算の対応関係を示す図である。
【図１７】バイナリ法によるべき乗剰余演算のアルゴリズムを示す図である。
【図１８】バイナリ法によるべき乗剰余演算の概要を示す図である。
【図１９】バイナリ法によるべき乗剰余演算に対するPAの概要を示す図である。
【図２０】バイナリ法による点のスカラー倍算のアルゴリズムを示す図である。
【図２１】バイナリ法による点のスカラー倍算の概要を示す図である。
【図２２】バイナリ法による点のスカラー倍算に対するPAの概要を示す図である。
【図２３】A&D法を用いたバイナリ法によるべき乗剰余演算のアルゴリズムを示す図である。
【図２４】A&D法を用いたバイナリ法によるべき乗剰余演算に対するPAの概要を示す図である。
【図２５】A&D法を用いたバイナリ法による点のスカラー倍算のアルゴリズムを示す図である。
【図２６】A&D法を用いたバイナリ法による点のスカラー倍算に対するPAの概要を示す図である。
【図２７】RSAに対するメッセージ選択型PAの概要を示す図である。
【図２８】素体楕円曲線パラメータの点の加算演算のアルゴリズムを示す図である。
【図２９】素体楕円曲線パラメータの点の2倍算処理のアルゴリズムを示す図である。
【図３０】2べき楕円曲線パラメータの点の加算演算のアルゴリズムを示す図である。
【図３１】2べき楕円曲線パラメータの点の2倍算処理のアルゴリズムを示す図である。
【図３２】特殊分岐が発生するECDBL演算における電力波形と、特殊分岐が発生しないECDBL演算における電力波形とを示す図である。
【図３３】特殊分岐が発生するECADD演算における電力波形と、特殊分岐が発生しないECADD演算における電力波形とを示す図である。
【図３４】特殊分岐が発生した場合の点のスカラー倍算処理全体の電力波形を示す図である。
【図３５】A&D法を用いたECCに対する特殊分岐PAを示す図である。
【図３６】PKV処理のアルゴリズムを示す図である。
【図３７】Fault攻撃の概要を示す図である。
【図３８】PKV方式に対するFault攻撃の概要を示す図である。
【図３９】PKV方式に対するFault攻撃において選択される点Aの一例を示す図である。
【図４０】攻撃に対するリアルタイム性を示す図である。
【発明を実施するための形態】
【００５９】
以下、本発明の実施の形態について図面を参照しつつ説明する。
【００６０】
実施の形態１．
まず、本実施の形態に係る楕円曲線演算処理装置のハードウェア構成について説明する。図１は、本実施の形態に係る楕円曲線演算処理装置のハードウェア構成を示す図である。
【００６１】
図１に示すように、本実施の形態に係る楕円曲線演算処理装置10は、ECC（Elliptic Curve Cryptosystem）プロセッサ101、CPU（Central Processing Unit）102、ROM（Read-Only Memory）103、I/F104、EEROM（Electrically Erasable ROM）105、RAM（Random Access Memory）106と、これらを接続するデータバス107を備える。また、この楕円曲線演算処理装置10は、PAを行うために、消費電力を測定するオシロスコープ20がVcc及びGNDに接続されているものとする。ECCプロセッサ101は、暗号処理または電子署名処理に係る楕円曲線演算を行う。また、CPU102は、楕円曲線演算処理装置10を制御する。また、ROM103は、ECCプロセッサ101、CPU102により実行されるプログラムを格納する。また、I/F104は、楕円曲線演算処理装置10に対するデータの入出力を仲介する。また、EEROM105は、電気的にデータを消去可能なROMであり、ECCにおける個人鍵dを格納する。また、RAM106は、ECCプロセッサ101、CPU102により実行されるプログラムを一時的に格納する。
【００６２】
次に、本実施の形態に係る楕円曲線演算処理装置の機能構成について説明する。図２は、本実施の形態に係る楕円曲線演算処理装置の機能構成を示すブロック図である。
【００６３】
図２に示すように、本実施の形態に係る楕円曲線演算処理装置10は、判断部301、演算部302（算出部）、停止部303を機能として有する。演算部302は、ECCに係る演算を実行する。また、判断部301は、演算部302による演算に係る判断を行う。また、停止部303は、判断部301による判断に基づいて、演算部302による演算を停止させる。なお、これら各部は、ECCプロセッサ101、CPU102により実現される機能である。
【００６４】
本実施の形態に係る楕円曲線演算処理装置10は、楕円曲線上の点のスカラー倍算において、入力値または出力結果が無限遠点である場合、これを攻撃とみなし演算処理を停止する。以下、本実施の形態に係る楕円曲線演算処理装置10の動作について説明する。まず、楕円曲線演算処理装置10の全体動作について説明する。図３は、本実施の形態における点のスカラー倍算処理を示すフローチャートである。また、図４は、素体楕円曲線パラメータによる点のスカラー倍算のアルゴリズムを示す図である。なお、以降の説明において、Aは楕円曲線演算処理装置10に対する入力（楕円曲線上の所定の点）、dはスカラー値（個人鍵）、iはdのビット位置（初期値は最上位ビット位置でありuビットである場合i = u - ２）、diはi番目のビット値、かつdu-1=1、Oは無限遠点を示す。また、V[0]は入力値及び演算結果（出力値）を格納する配列変数、V[1]はECADD演算の演算結果を格納する配列変数とする。また、楕円曲線上の点はjacobian座標により表現されるものとする。
【００６５】
図３に示すように、まず、演算部302は、V[0]の初期値として、AをV[0]に代入する（S101）。これは、上述したように、点のスカラー倍算において、入力値が無限遠点である場合、演算処理が停止されることに起因する。つまり、無限遠点OではなくAをV[0]の初期値とすることにより、初期値Oによる演算処理の停止を防ぐことができる。
【００６６】
次に、演算部302は、dのi番目のビット(di)を選択し（S102）、V[0]を入力とするECDBL演算を実行してその結果をV[0]に代入する（S103, 算出ステップ）。次に、判断部301は、ECDBL演算による戻り値がERRORであるかどうかを判断する（S104, 判断ステップ）。
【００６７】
ECDBL演算による戻り値がERRORではない場合(S104, NO)、演算部302は、Aとv[0]とを入力とするECADD演算を実行してその結果をV[1]に代入する（S105, 算出ステップ）。次に、判断部301は、ECADD演算による戻り値がERRORであるかどうかを判断する（S106, 判断ステップ）。なお、ECDBL演算及びECADD演算については、ECDBL演算処理、ECADD演算処理として後述する。
【００６８】
ECADD演算による戻り値がERRORではない場合（S106, NO）、演算部302は、V[0]にV[di]を代入する（S107, 算出ステップ）。つまり、ビット値に応じて、V[0]に代入される値が決定する。次に、演算部302は、iから1を減算し（S108, 算出ステップ）、iが0以上かどうかを判断する（S109, 算出ステップ）。
【００６９】
iが0未満である場合（S109, NO）、演算部302は、V[0]を出力する（S110, 算出ステップ）。
【００７０】
一方、iが0以上である場合（S109, YES）、演算部302は、再度、dのi番目のビット(di)を選択する（S102）。
【００７１】
また、ステップS106において、ECADD演算による戻り値がERRORである場合（S106, YES）、停止部303は、スカラー倍算処理を停止する（S111, 停止ステップ）。
【００７２】
また、ステップS104において、ECBDL演算による戻り値がERRORである場合（S104, YES）、停止部303は、スカラー倍算処理を停止する（S111, 停止ステップ）。
【００７３】
これらの処理は、具体的には図４に示すアルゴリズムに相当する。このアルゴリズムにおいて、上述した点のスカラー倍算処理同様に、V[0] := Oによる初期化は行われず、代わりに3401の処理において、V[0] := Aによる初期化が行われる。また、V[0] := Aによる初期化を行いながら演算の整合性を保つための処理が、3402-3404において実行される。この処理は、di == 1を満たすiの最大値を求め、そのiに対して1を減算する処理である。これにより、dのビット値のうち、ビット値が1となる最上位ビットの1つ下位のビットからループ処理が開始される。また、3402-3404のループ処理において、ECDBL演算、ECADD演算の戻り値がERRORである場合、点のスカラー倍算処理が停止される。
【００７４】
次に、ECDBL演算処理について説明する。このECDBL演算処理は、図３におけるステップS103の処理に相当する。図５は、ECDBL演算処理の動作を示すフローチャーである。また、図６は、素体楕円曲線パラメータによるECDBL演算のアルゴリズムを示す図である。
【００７５】
図５に示すように、まず、演算部302は、V[0] = Oまたは2V[0] == Oであるかどうかを判断する（S201）。
【００７６】
V[0] = O、2V[0] == Oのいずれでもない場合（S201, NO）、つまりECDBL演算処理における入力値が無限遠点ではない場合、演算部302は、V[0]を入力とする点の2倍算演算を実行し（S202）、演算結果をV[0]へ代入する（S203）。
【００７７】
一方、V[0] == Oまたは2V[0] == Oである場合（S201, YES）、演算部302は、ERRORを戻り値として返す（S204）。
【００７８】
つまり、演算部302は、ECBDL演算処理における入力値または出力値が無限遠点である場合、ERRORを戻り値として出力する。
【００７９】
これらの処理は、具体的には図６に示すアルゴリズムに相当する。このアルゴリズムにおいて、3004の処理はステップS201, S204の処理に相当する。また、この3004の処理において、T2 == 0 or T3 == 0である場合は上述した特殊分岐4に相当し、then return ERROR;は特殊分岐4の発生による例外処理に相当する。
【００８０】
次に、ECADD演算処理について説明する。このECADD演算処理は、図３におけるステップS104の処理に相当する。図７は、ECADD演算処理の動作を示すフローチャーである。また、図８は、素体楕円曲線パラメータによるECADD演算のアルゴリズムを示す図である。
【００８１】
図７に示すように、まず、演算部302は、A == Oであるかどうかを判断する（S301）
【００８２】
A == Oではない場合（S301, NO）、演算部302は、V[0] == Oであるかどうかを判断する（S302）。
【００８３】
V[0] == Oではない場合（S302, NO）、演算部302は、点の加算演算1（図８における2901から2916の処理に相当）を実行し（S303）、A + V[0] == Oであるかどうかを判断する（S304）。
【００８４】
A + V[0] == Oではない場合（S304, NO）、演算部302は、点の加算演算2（図８における2918から2935の処理に相当）を実行し（S305）、演算結果をV[1]に代入する（S306）。
【００８５】
一方、A + V[0] == Oである場合（S304, YES）、演算部302は、ERRORを戻り値として出力する（S307）。これにより、ECADD演算処理における入力値または出力値が無限遠点である場合、点のスカラー倍算処理が停止される。
【００８６】
また、ステップS302において、V[0] == Oである場合（S302, YES）、演算部302は、ERRORを戻り値として出力する（S307）。
【００８７】
また、ステップS301において、A == Oである場合（S301, YES）、演算部302は、ERRORを戻り値として出力する（S307）。
【００８８】
つまり、演算部302は、ECADD演算処理における入力値または出力値が無限遠点である場合、ERRORを戻り値として出力する。
【００８９】
これらの処理は、具体的には図８に示すアルゴリズムに相当する。このアルゴリズムにおいて、2900の処理はステップS301, S302, S307の処理に相当する。また、この2900の処理において、Az == 0である場合、Bz == 0である場合は上述した特殊分岐1に相当し、then return ERROR;は特殊分岐1の発生による例外処理に相当する。また、2917の処理において、T1 == 0かつT2 == 0である場合は上述した特殊分岐3に相当し、else return ERROR;は特殊分岐3の発生による例外処理に相当する。
【００９０】
なお、図６及び図８に示したアルゴリズムは、素体楕円曲線パラメータによる点のスカラー倍算であるが、上述した処理は、2べき楕円曲線パラメータによる点のスカラー倍算にも適用可能である。以下、2べき楕円曲線パラメータを用いた場合のアルゴリズムについて説明する。図９は、2べき楕円曲線パラメータによるECDBL演算のアルゴリズムを示す図である。また、図１０は、2べき楕円曲線パラメータによるECADD演算のアルゴリズムを示す図である。
【００９１】
図５に示した処理は、2べき楕円曲線パラメータを用いた場合、具体的には図９に示すアルゴリズムに相当する。このアルゴリズムにおいて、3205の処理はステップS201, S204の処理に相当する。また、この3205の処理において、T1 == 0 or T3 == 0である場合は上述した特殊分岐4に相当し、then return ERROR;は特殊分岐4の発生による例外処理に相当する。
【００９２】
また、図７に示した処理は、2べき楕円曲線パラメータを用いた場合、具体的には図１０に示すアルゴリズムに相当する。このアルゴリズムにおいて、3100の処理はステップS301, S302, S307に相当する。また、この3100の処理において、Az == 0である場合、Bz == 0である場合は上述した特殊分岐1に相当し、then return ERROR;は特殊分岐1の発生による例外処理に相当する。また、3118の処理において、T1 == 0かつT2 == 0である場合は上述した特殊分岐3に相当し、else return ERROR;は特殊分岐3の発生による例外処理に相当する。
【００９３】
上述したように、特殊分岐（特殊分岐1,3,4）が発生した場合、つまり、ECBDL演算、ECADD演算のいずれかの演算において、入力値または出力値が無限遠点である場合、ERRORが出力される。またERRORが出力されることにより、EDBDL演算の処理だけでなく、その上位処理である点のスカラー倍算の処理全体が停止される。その結果として、楕円曲線演算処理装置10の消費電力の測定において、短い電力波形と長い電力波形が混在せず、長い電力波形のみが測定される。よって、これらの電力波形の違いを利用した特殊分岐PAによる攻撃を防ぐことができる。また、攻撃検知の判断は、従来のECDBL演算、ECADD演算において行われている判断と同様であることにより、攻撃の検知に必要な処理時間のオーバーヘッドをゼロにすることができる。さらに、点のスカラー倍算処理において高い頻度で繰り返されるECDBL演算、ECADD演算が実行されるたびに攻撃が検知されることにより、攻撃検知のリアルタイム性を向上させることができる。また、リアルタイム性が向上することにより、Fault攻撃のような所定のタイミングでデータの改ざんする攻撃を防ぐことができる。
【００９４】
以上のことから、本発明は従来方式に比べ、セキュリティ、処理時間、攻撃検知のリアルタイム性において優れている。図１１は、従来方式による効果と本発明による効果との比較を示す図である。
【００９５】
図１１に示すように、A&D法を用いたECCは、処理時間は高速であるが、上述したように、Qの入力による攻撃法に対しては脆弱であり、攻撃検知のリアルタイム性がない。また、PKV方式は、Qの入力による攻撃法に対しては安全であるが、処理時間は低速であり、攻撃検知のリアルタイム性がない。これに対して、本発明は、Qの入力による攻撃法に対して安全であり、処理時間が高速であり、攻撃検知のリアルタイム性がある。つまり、本発明によれば、Qの入力による攻撃法への脆弱性、処理時間、攻撃検知のリアルタイム性という従来のECCにおける課題を全て解決することができる。
【００９６】
実施の形態２．
本実施の形態に係る楕円曲線演算処理装置10は、そのハードウェア構成は実施の形態１と同様であるが、点のスカラー倍算において、ECDBL演算とECADD演算とが同時になされる手法（ECADDDBL演算）が用いられる点が、実施の形態１とは異なる。なお、このECADDDBL演算には素体楕円曲線パラメータ、jacobian座標が用いられる。以下、実施の形態１とは異なる動作について説明する。図１２は、本実施の形態における点のスカラー倍算のアルゴリズムを示す図である。また、図１３は、本実施の形態におけるECADDDBL演算のアルゴリズムを示す図である。
【００９７】
図１２に示すように、本実施の形態における点のスカラー倍算は、3501のV[0] := A;とともに、3502のV[1] := 2A;を初期化として実行する点が実施の形態１とは異なる。これは、ECDBL演算とECADD演算とが同時になされることに起因する。また、3507においてECADDDBL演算を実行し、このECADDDBL演算によりERRORが戻り値として返された場合に点のスカラー倍算全体の処理を停止する点が、実施の形態１とは異なる。
【００９８】
また、ECADDDBL演算は、図１３に示すように、y座標を計算せずにECDBL演算及びECADD演算を行うため、出力結果のy座標値Ry, Syに対する計算は行わない。また、点のスカラー倍算アルゴリズムは、Montgomery-Ladderと呼ばれる方法である。また、ECADDDBL演算の入力として、スカラー倍する対象の点のx座標Ixを用いる。
【００９９】
また、図１３に示すアルゴリズムにおける3305の処理において、T2 == O or T4 == Oである場合は、上述した特殊分岐1に相当し、then return ERROR;は特殊分岐1の発生による例外処理に相当する。また、3311の処理において、T3 == Oである場合は、上述した特殊分岐3に相当し、then return ERROR;は特殊分岐3の発生による例外処理に相当する。また、3334の処理において、T1 == Oである場合は、上述した特殊分岐4に相当し、then return ERROR;は特殊分岐4の発生による例外処理に相当する。
【０１００】
上述したように、本実施の形態に係る楕円曲線演算処理装置10において、実施の形態１と同様に、ECADDDBL演算により戻り値としてERRORが返されると、その上位処理である点のスカラー倍算処理において、処理全体が停止される。点のスカラー倍算処理において、ECDBL演算処理及びECADD演算処理の代わりにECADDDBL演算処理を実行することにより、テーブルメモリ領域と計算量を小さくすることができる。
【０１０１】
実施の形態３．
実施の形態１における点のスカラー倍算は、ECDBL演算1回ごとにECADD演算を1回実行していたが、本実施の形態における点のスカラー倍算は、window法を用いることにより、ECDBL演算をk回実行するごとにECADD演算を1回実行する。なお、本実施の形態におけるECDBL演算と、実施の形態1におけるECDBL演算との実行回数は同じである。つまり、window法を適用することにより、ECADD演算の実行頻度が低減する。以下、実施の形態１とは異なる動作について説明する。図１４は、本実施の形態における点のスカラー倍算のアルゴリズムを示す図である。
【０１０２】
図１４に示すように、window法を用いた点のスカラー倍算は、ECADD演算の頻度を下げるため、事前計算テーブルデータを作成する。この事前計算テーブルデータは、3601-3602の処理において作成され、W[x] = xA(0 < x < 2k)として与えられる。また、window法を用いた点のスカラー倍算において、(dik+k-1, …, dik)i ( 0を満たすiの最大値を求め、V:=W[(dik+k-1, …, dik)](無限遠点以外の点)による初期化処理が、3603-3605の処理により行われる。また、3606-3611のループ処理は、基本的には従来のwindow法と同じであるが、ECADD演算、ECDBL演算の戻り値がERRORである場合にスカラー倍算の処理を停止する点において異なる。
【０１０３】
上述したように、実施の形態１における点のスカラー倍算にwindow法を適用することによって、ECADD演算の実行回数が少なくなり、結果として、点のスカラー倍算に係る計算量を減らすことができる。
【０１０４】
なお、jacobian座標によるECDBL演算、ECADD演算について説明をしたが、これらの演算における特殊分岐の発生により点のスカラー倍算処理を停止するという処理は、投影座標、またはaffine座標によるECDBL演算、ECADD演算についても適用可能である。また、上述の実施の形態において、ECDBL演算、ECADD演算による戻り値がERRORである場合に点のスカラー倍算処理を停止したが、処理の停止の代わりにハードウェアリセットを行っても良い。さらに、楕円曲線演算処理装置10の不揮発性メモリ（例えばEEROM105）に攻撃検知を示すフラグを設けても良い。このフラグを設けることにより、ECDBL演算、ECADD演算による戻り値がERRORの場合にフラグをONにし、ハードウェアリセットによる再起動時にフラグがONである場合、装置自体が利用できないような処理を行うようにしても良い。また、上述した点のスカラー倍算のアルゴリズムは一例であり、無限遠点による初期化処理を行わない点のスカラー倍算のアルゴリズムに対し、本発明は適用可能である。つまり、初期化処理は無限遠点以外の任意の点によるものであれば良い。
【０１０５】
更に、本実施の形態における楕円曲線演算処理装置をコンピュータとして提供することができる。また、楕円曲線演算処理装置を構成するコンピュータにおいて上述した各ステップを実行させるプログラムを、楕円曲線演算処理プログラムとして提供することができる。上述したプログラムは、コンピュータにより読取り可能な記録媒体に記憶させることによって、楕円曲線演算処理装置を構成するコンピュータに実行させることが可能となる。ここで、上記コンピュータにより読取り可能な記録媒体としては、ＲＯＭやＲＡＭ等のコンピュータに内部実装される内部記憶装置、ＣＤ−ＲＯＭやフレキシブルディスク、ＤＶＤディスク、光磁気ディスク、ＩＣカード等の可搬型記憶媒体や、コンピュータプログラムを保持するデータベース、或いは、他のコンピュータ並びにそのデータベースや、更に回線上の伝送媒体をも含むものである。
【０１０６】
以上、本実施の形態によれば、以下の付記で示す技術的思想が開示されている。
（付記１） 楕円曲線上の点の演算を行う楕円曲線演算処理装置であって、
前記楕円曲線上の所定の点Aを前記楕円曲線上の点の演算に対する入力とし、ECDBL演算及びECADD演算によりスカラー値dのA倍点を算出する算出部と、
前記算出部によるdのA倍点の算出において、前記ECDBL演算または前記ECADD演算の入力値または出力値が無限遠点であるかどうかを判断する判断部と、
前記判断部により前記入力値または前記出力値が無限遠点であると判断された場合、前記算出部によるdのA倍点の算出を停止する停止部と
を備える楕円曲線演算処理装置。
（付記２） 付記１に記載の楕円曲線演算処理装置において、
点Aは、無限遠点ではない前記楕円曲線上の所定の点であることを特徴とする楕円曲線演算処理装置。
（付記３） 付記１または付記２に記載の楕円曲線演算処理装置において、
前記算出部は、前記ECDBL演算及び前記ECADD演算において、前記入力値または前記出力値が無限遠点である場合、ERRORを戻り値として出力することを特徴とし、
前記判断部は、前記戻り値がERRORである場合、前記入力値または前記出力値が無限遠点であると判断することを特徴とする楕円曲線演算処理装置。
（付記４） 付記１乃至付記３のいずれかに記載の楕円曲線演算処理装置において、
前記算出部は、A&D法を用いて、dのA倍点を算出することを特徴とする楕円曲線演算処理装置。
（付記５） 付記１乃至付記４のいずれかに記載の楕円曲線演算処理装置において、
前記算出部は、ECADDDBL演算を用いて、dのA倍点を算出することを特徴とする楕円曲線演算処理装置。
（付記６） 付記１乃至付記５のいずれかに記載の楕円曲線演算処理装置において、
前記算出部は、window法を用いて、dのA倍点を算出することを特徴とする楕円曲線演算処理装置。
（付記７） 楕円曲線上の点の演算を行う楕円曲線演算処理プログラムであって、
前記楕円曲線上の所定の点Aを前記楕円曲線上の点の演算に対する入力とし、ECDBL演算及びECADD演算によりスカラー値dによる点Aのd倍点を算出する算出ステップと、
前記算出ステップによる点Aのd倍点の算出において、前記ECDBL演算または前記ECADD演算の入力値または出力値が無限遠点であるかどうかを判断する判断ステップと、
前記判断ステップにより前記入力値または前記出力値が無限遠点であると判断された場合、前記算出ステップによる点Aのd倍点の算出を停止する停止ステップと
をコンピュータに実行させる楕円曲線演算処理プログラム。
（付記８） 付記７に記載の楕円曲線演算処理プログラムにおいて、
点Aは、無限遠点ではない前記楕円曲線上の所定の点であることを特徴とする楕円曲線演算処理プログラム。
（付記９） 付記７または付記８に記載の楕円曲線演算処理プログラムにおいて、
前記算出ステップは、前記ECDBL演算及び前記ECADD演算において、前記入力値または前記出力値が無限遠点である場合、ERRORを戻り値として出力することを特徴とし、
前記判断ステップは、前記戻り値がERRORである場合、前記入力値または前記出力値が無限遠点であると判断することを特徴とする楕円曲線演算処理プログラム。
（付記１０） 付記７乃至付記９のいずれかに記載の楕円曲線演算処理プログラムにおいて、
前記算出ステップは、A&D法を用いて、点Aのd倍点を算出することを特徴とする楕円曲線演算処理プログラム。
（付記１１） 付記７乃至付記１０のいずれかに記載の楕円曲線演算処理プログラムにおいて、
前記算出ステップは、ECADDDBL演算を用いて、点Aのd倍点を算出することを特徴とする楕円曲線演算処理プログラム。
（付記１２） 付記７乃至付記１１のいずれかに記載の楕円曲線演算処理プログラムにおいて、
前記算出ステップは、window法を用いて、点Aのd倍点を算出することを特徴とする楕円曲線演算処理プログラム。
（付記１３） 楕円曲線上の点の演算を行う楕円曲線演算処理方法であって、
前記楕円曲線上の所定の点Aを前記楕円曲線の点の演算に対する入力とし、ECDBL演算及びECADD演算によりスカラー値dによる点Aのd倍点を算出する算出ステップと、
前記算出ステップによる点Aのd倍点の算出において、前記ECDBL演算または前記ECADD演算の入力値または出力値が無限遠点であるかどうかを判断する判断ステップと、
前記判断ステップにより前記入力値または前記出力値が無限遠点であると判断された場合、前記算出ステップによる点Aのd倍点の算出を停止する停止ステップと
を備える楕円曲線演算処理方法。
（付記１４） 付記１３に記載の楕円曲線演算処理方法において、
点Aは、無限遠点ではない前記楕円曲線上の所定の点であることを特徴とする楕円曲線演算処理方法。
（付記１５） 付記１３または付記１４に記載の楕円曲線演算処理方法において、
前記算出ステップは、前記ECDBL演算及び前記ECADD演算において、前記入力値または前記出力値が無限遠点である場合、ERRORを戻り値として出力することを特徴とし、
前記判断ステップは、前記戻り値がERRORである場合、前記入力値または前記出力値が無限遠点であると判断することを特徴とする楕円曲線演算処理方法。
（付記１６） 付記１３乃至付記１５のいずれかに記載の楕円曲線演算処理方法において、
前記算出ステップは、A&D法を用いて、点Aのd倍点を算出することを特徴とする楕円曲線演算処理方法。
（付記１７） 付記１３乃至付記１６のいずれかに記載の楕円曲線演算処理方法において、
前記算出ステップは、ECADDDBL演算を用いて、点Aのd倍点を算出することを特徴とする楕円曲線演算処理方法。
（付記１８） 付記１３乃至付記１８のいずれかに記載の楕円曲線演算処理方法において、
前記算出ステップは、window法を用いて、点Aのd倍点を算出することを特徴とする楕円曲線演算処理方法。
【符号の説明】
【０１０７】
10 楕円曲線演算処理装置、20 オシロスコープ、101 ECCプロセッサ、102 CPU、103 ROM、104 I/F、105 EEROM、106 RAM、301 判断部、302 演算部、303 停止部。
【特許請求の範囲】
【請求項１】
楕円曲線上の点の演算を行う楕円曲線演算処理装置であって、
前記楕円曲線上の所定の点Aを前記楕円曲線上の点の演算に対する入力とし、ECDBL演算及びECADD演算によりスカラー値dによる点Aのd倍点を算出する算出部と、
前記算出部による点Aのd倍点の算出において、前記ECDBL演算または前記ECADD演算の入力値または出力値が無限遠点であるかどうかを判断する判断部と、
前記判断部により前記入力値または前記出力値が無限遠点であると判断された場合、前記算出部による点Aのd倍点の算出を停止する停止部と
を備える楕円曲線演算処理装置。
【請求項２】
請求項１に記載の楕円曲線演算処理装置において、
点Aは、無限遠点ではない前記楕円曲線上の所定の点であることを特徴とする楕円曲線演算処理装置。
【請求項３】
請求項１または請求項２に記載の楕円曲線演算処理装置において、
前記算出部は、前記ECDBL演算及び前記ECADD演算において、前記入力値または前記出力値が無限遠点である場合、ERRORを戻り値として出力することを特徴とし、
前記判断部は、前記戻り値がERRORである場合、前記入力値または前記出力値が無限遠点であると判断することを特徴とする楕円曲線演算処理装置。
【請求項４】
請求項１乃至請求項３のいずれかに記載の楕円曲線演算処理装置において、
前記算出部は、A&D法を用いて、点Aのd倍点を算出することを特徴とする楕円曲線演算処理装置。
【請求項５】
請求項１乃至請求項４のいずれかに記載の楕円曲線演算処理装置において、
前記算出部は、ECADDDBL演算を用いて、点Aのd倍点を算出することを特徴とする楕円曲線演算処理装置。
【請求項６】
楕円曲線上の点の演算を行う楕円曲線演算処理プログラムであって、
前記楕円曲線上の所定の点Aを前記楕円曲線上の点の演算に対する入力とし、ECDBL演算及びECADD演算によりスカラー値dによる点Aのd倍点を算出する算出ステップと、
前記算出ステップによる点Aのd倍点の算出において、前記ECDBL演算または前記ECADD演算の入力値または出力値が無限遠点であるかどうかを判断する判断ステップと、
前記判断ステップにより前記入力値または前記出力値が無限遠点であると判断された場合、前記算出ステップによる点Aのd倍点の算出を停止する停止ステップと
をコンピュータに実行させる楕円曲線演算処理プログラム。
【請求項７】
楕円曲線上の点の演算を行う楕円曲線演算処理方法であって、
前記楕円曲線上の所定の点Aを前記楕円曲線の点の演算に対する入力とし、ECDBL演算及びECADD演算によりスカラー値dによる点Aのd倍点を算出する算出ステップと、
前記算出ステップによる点Aのd倍点の算出において、前記ECDBL演算または前記ECADD演算の入力値または出力値が無限遠点であるかどうかを判断する判断ステップと、
前記判断ステップにより前記入力値または前記出力値が無限遠点であると判断された場合、前記算出ステップによる点Aのd倍点の算出を停止する停止ステップと
を備える楕円曲線演算処理方法。
【請求項１】
楕円曲線上の点の演算を行う楕円曲線演算処理装置であって、
前記楕円曲線上の所定の点Aを前記楕円曲線上の点の演算に対する入力とし、ECDBL演算及びECADD演算によりスカラー値dによる点Aのd倍点を算出する算出部と、
前記算出部による点Aのd倍点の算出において、前記ECDBL演算または前記ECADD演算の入力値または出力値が無限遠点であるかどうかを判断する判断部と、
前記判断部により前記入力値または前記出力値が無限遠点であると判断された場合、前記算出部による点Aのd倍点の算出を停止する停止部と
を備える楕円曲線演算処理装置。
【請求項２】
請求項１に記載の楕円曲線演算処理装置において、
点Aは、無限遠点ではない前記楕円曲線上の所定の点であることを特徴とする楕円曲線演算処理装置。
【請求項３】
請求項１または請求項２に記載の楕円曲線演算処理装置において、
前記算出部は、前記ECDBL演算及び前記ECADD演算において、前記入力値または前記出力値が無限遠点である場合、ERRORを戻り値として出力することを特徴とし、
前記判断部は、前記戻り値がERRORである場合、前記入力値または前記出力値が無限遠点であると判断することを特徴とする楕円曲線演算処理装置。
【請求項４】
請求項１乃至請求項３のいずれかに記載の楕円曲線演算処理装置において、
前記算出部は、A&D法を用いて、点Aのd倍点を算出することを特徴とする楕円曲線演算処理装置。
【請求項５】
請求項１乃至請求項４のいずれかに記載の楕円曲線演算処理装置において、
前記算出部は、ECADDDBL演算を用いて、点Aのd倍点を算出することを特徴とする楕円曲線演算処理装置。
【請求項６】
楕円曲線上の点の演算を行う楕円曲線演算処理プログラムであって、
前記楕円曲線上の所定の点Aを前記楕円曲線上の点の演算に対する入力とし、ECDBL演算及びECADD演算によりスカラー値dによる点Aのd倍点を算出する算出ステップと、
前記算出ステップによる点Aのd倍点の算出において、前記ECDBL演算または前記ECADD演算の入力値または出力値が無限遠点であるかどうかを判断する判断ステップと、
前記判断ステップにより前記入力値または前記出力値が無限遠点であると判断された場合、前記算出ステップによる点Aのd倍点の算出を停止する停止ステップと
をコンピュータに実行させる楕円曲線演算処理プログラム。
【請求項７】
楕円曲線上の点の演算を行う楕円曲線演算処理方法であって、
前記楕円曲線上の所定の点Aを前記楕円曲線の点の演算に対する入力とし、ECDBL演算及びECADD演算によりスカラー値dによる点Aのd倍点を算出する算出ステップと、
前記算出ステップによる点Aのd倍点の算出において、前記ECDBL演算または前記ECADD演算の入力値または出力値が無限遠点であるかどうかを判断する判断ステップと、
前記判断ステップにより前記入力値または前記出力値が無限遠点であると判断された場合、前記算出ステップによる点Aのd倍点の算出を停止する停止ステップと
を備える楕円曲線演算処理方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【図２７】
【図２８】
【図２９】
【図３０】
【図３１】
【図３２】
【図３３】
【図３４】
【図３５】
【図３６】
【図３７】
【図３８】
【図３９】
【図４０】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【図２７】
【図２８】
【図２９】
【図３０】
【図３１】
【図３２】
【図３３】
【図３４】
【図３５】
【図３６】
【図３７】
【図３８】
【図３９】
【図４０】
【公開番号】特開２０１０−１６４９０４（Ｐ２０１０−１６４９０４Ａ）
【公開日】平成２２年７月２９日（２０１０．７．２９）
【国際特許分類】
【出願番号】特願２００９−９０９１（Ｐ２００９−９０９１）
【出願日】平成２１年１月１９日（２００９．１．１９）
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【Ｆターム（参考）】
【公開日】平成２２年７月２９日（２０１０．７．２９）
【国際特許分類】
【出願日】平成２１年１月１９日（２００９．１．１９）
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【Ｆターム（参考）】
[ Back to top ]