(57)【特許請求の範囲】
【請求項１】
個人鍵を用いて楕円曲線暗号処理を行う暗号化処理装置において、
乱数に基づいて生成された楕円曲線上の点Ｒを初期点にセットするランダム化手段と、
ｎを整数として、点Ｒをスカラー倍算した値「２＾ｎ×Ｒ」である点Ｒ’を設定する設定手段と、
この初期点、楕円曲線暗号のためのあるスカラー値ｄ、楕円曲線上のある点Ｐを用いてスカラー倍演算を演算し、点Ｒ’について２倍算を演算する手段と、
その演算によって得られた点Ｑから点Ｒに関係する、２倍算された点Ｒ’を用いてＱ−Ｒ’を実行するランダム化解除手段と、
その結果を出力する手段と、
を備えることを特徴とする暗号化処理装置。
【請求項２】
個人鍵を用いてＲＳＡ暗号処理を行う暗号化処理装置において、
乱数に基づいて生成された整数ｒを初期値にセットするランダム化手段と、
ｎを整数として、点ｒをべき乗剰余演算子した値ｒ＾（２＾ｎ）である点ｒ’を設定する設定手段と、
この初期値、ＲＳＡ暗号のためのあるべき指数ｄ、ある整数ｐを用いてべき乗剰余演算を演算し、値ｒ’について２乗剰余算を演算する手段と、
その演算によって得られた整数ｑからｒに関係する、２乗剰余算された値ｒ’を用いて乗算剰余演算ｑ＊ｒ’＾（−１）を実行するランダム化解除手段と、
その結果を出力する手段と、
を備えることを特徴とする暗号化処理装置。
【請求項３】
個人鍵を用いて楕円曲線暗号化処理を行う暗号化処理装置において、
乱数に基づいた、暗号化処理に使う楕円曲線上のランダムな点の座標値を表す整数値を生成するランダム値生成手段と、
ｎを整数として、前記ランダムな点の座標値の楕円体上の２＾ｎ倍算の値を設定する設定手段と、
暗号化するためのアルゴリズムである楕円体上の２倍算と加算を組み合わせたスカラー倍算を実行する際において、前記ランダムな点の座標値を演算の初期値として設定し、該ランダム点の座標値を、本来演算すべき値のスカラー倍算に含めて演算し、該ランダムな点の座標値の楕円体上の２＾ｎ倍算の値を２倍算する暗号化演算手段と、
該暗号化演算の実行後、本来演算すべき値のスカラー倍算から得られた値から、前記ランダムな点の座標値の楕円体上の２＾ｎ倍算の値の２倍算した値を減算するランダム化解除手段と、
を備えることを特徴とする暗号化処理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号化処理装置に関し、特に、ＲＳＡ暗号および楕円曲線暗号処理を行うプロセッサにおける電力解析攻撃を防止する耐タンパ暗号処理装置に関する。
【背景技術】
【０００２】
電子決済、住民基本台帳ネットワークなどのようにネットワークの利用を前提としたサービスが普及しつつある。これらのサービスにおいては、ユーザが正規のユーザであることを証明するために、ユーザの秘密情報を格納したＩＣチップを含むスマートカード（ＩＣカード）が利用されることがある。スマートカードは、暗号、ディジタル署名、認証などの機能を有し、ユーザの秘密情報を鍵として用いる。スマートカードでは、秘密情報はＩＣチップやメモリに格納されるため、第三者による不正なアクセスに対する安全性または耐タンパ性が磁気カードに比べて非常に高い。
【０００３】
スマートカードのような暗号デバイスが使用する暗号方式には、公開鍵暗号方式と共通鍵暗号方式が含まれる。公開鍵暗号方式は、暗号化と復号化とで異なる鍵（キー）を用いる方式である。典型的には、暗号化を行うための鍵（公開鍵）はあらかじめ公開されていて、送信者はこの公開鍵を用いて平文を暗号化して受信者に送信する。暗号文を復号化するための鍵（秘密鍵）は受信者のみが知る秘密情報として保持されており、受信者がこの秘密鍵を用いて暗号文を復号化することにより平文を得ることができる。公開鍵暗号方式にはＲＳＡ暗号方式及び楕円曲線暗号方式が含まれる。
【０００４】
ＲＳＡ暗号方式の処理を行う場合に必要とされる主たる演算機能にべき乗剰余計算機能がある。ここでべき乗計算とはａ＾ｄ（ｍｏｄ ｎ）＝ａ×ａ×…×ａ（ｄ回）（ｍｏｄ ｎ）という形の演算である。ここで＾はべき乗を表し、ａ、ｄ、ｎはある整数を表す。また“ｍｏｄ ｎ”はｎで割った余りを表す。ＲＳＡ暗号方式に基づく暗号機能には、暗号化・復号化・署名生成・署名検証が含まれる。復号化および署名生成では、ｄはユーザの秘密情報に関連した値を用いる。
【０００５】
楕円曲線暗号方式の処理を行う場合に必要とされる主たる演算機能にスカラー倍算がある。ここでスカラー倍算とは、ｄ×Ｐ＝Ｐ＋Ｐ＋…＋Ｐ（ｄ回）という形の演算である。またｄはある整数、Ｐはある楕円曲線上の点とする。楕円曲線暗号方式に基づく暗号機能には、暗号化・復号化・署名生成・署名検証・鍵共有が含まれる。復号化、署名生成および鍵共有では、ｄはユーザの秘密情報に関連した値を用いる。ＲＳＡ暗号におけるべき乗剰余演算と、楕円曲線暗号におけるスカラー倍算演算は、べき乗演算と呼ばれる演算の例である。
【０００６】
暗号分野における技術の一つに、解読技術（タンパ技術）と呼ばれるものがある。解読技術とは暗号文等入手可能な情報から秘密鍵等の秘密情報を推定する技術のことであり、様々な手法が知られている。その中で最近注目されている技術に、サイドチャネル攻撃と呼ばれる手法がある。
【０００７】
サイドチャネル攻撃は、１９９６年に P. Kocher, “Timing attacks on implementation of Diffie-Hellman, RSA, DSA and other systems”, CRYPTO’96, Lecture Notes in Computer Science Vol. 1109, pp. 104-113, Springer-Verlag, 1996 (文献[Koc96]) によって考案された解析手法で、スマートカード等に搭載された暗号プロセッサに様々な入力データを与えた時のサイドチャネル情報（消費電力データ・消費時間データ・電磁波データ等）を収集・解析することにより、暗号プロセッサ内部の鍵情報を推定する手法である。サイドチャネル攻撃を用いると、公開鍵暗号、共通鍵暗号共に暗号プロセッサから秘密鍵を推定できる可能性があることが指摘されている。
【０００８】
このサイドチャネル攻撃の中で、消費電力データを用いる攻撃である電力解析攻撃は強力な攻撃法である。この電力解析攻撃の中に、単純電力解析（ＳＰＡ；Single Power Analysis）と、 P. Kocher, J. Jaffe, B. Jun, “Differential Power Analysys”, Crypto’99, Lecture Notes in Computer Science Vol. 1666, pp. 388-397, Springer-Verlag, 1999 (文献[KJJ99]) によって提案された差分電力解析（ＤＰＡ；Differential Power Analysis）が含まれる。ＳＰＡは暗号プロセッサにおける電力消費データの特徴から秘密鍵の推定を行う方式であり、ＤＰＡは多数の電力消費データの差分を解析することで秘密鍵の推定を行なう方式である。また楕円曲線暗号方式を主たる攻撃対象とした L. Goubin, “A Refined Power-analysis Attacks on Elliptic Curve Cryptosystems”, PKC 2003, Lecture Notes in Computer Science Vol. 2567, pp. 199-210, Springer-Verlag, 2003 (文献[Gou03]) によって提案された改良電力解析（ＲＰＡ；Refined Power Analysis）や、T. Akishita, T. Takagi, “Zero-value Point Attacks on Elliptic Curve Cryptosystems”, ISC 2003, Lecture Notes in Computer Science Vol. 2851, pp. 218-233, Springer-Verlag, 2003 (文献[AT03]) によって提案されたゼロ値電力解析(ＺＶＡ；Zero Value Power Analysis)も電力解析攻撃に含まれる。
【０００９】
このような電力解析攻撃の脅威に対し、各種国際標準において防止技術の必要性が指摘されている。例えば、セキュリティの国際標準ＩＳＯ１５４０８によるスマートカード用プロテクション・プロファイル（ＰＰ）では、電力解析攻撃への対策は必須とされている。また、暗号モジュールに関する米国標準ＦＩＰＳ１４０−２では、現在は電力解析攻撃対策の必要性に対するコメントのみが記載されているが、将来的には必須になると考えられている。
【００１０】
ＲＳＡ暗号方式や楕円曲線暗号方式の暗号において、処理の中心となるのはべき乗演算部分である。また、電力解析攻撃の攻撃対象となるのもべき乗演算部分である。以下、楕円曲線暗号方式におけるスカラー倍算ｄ×Ｐの実現方法について述べる。
【００１１】
バイナリ法（Binary method）はスカラー倍算の演算方法である。バイナリ法には、最下位ビット（Least Significant Bit；ＭＳＢ）から計算する方法（バイナリ法（ＬＳＢ））、最上位ビット（Most Significant Bit；ＭＳＢ）から計算する方法（バイナリ法（ＭＳＢ））とが知られており、特にバイナリ法（ＭＳＢ）の変形としてモンゴメリ鎖を用いた方法（モンゴメリ法）がある。
【００１２】
ここで、バイナリ法（ＬＳＢ）のアルゴリズム例を（１）アルゴリズム１に、又、バイナリ法（ＭＳＢ）のアルゴリズム例を（２）アルゴリズム２に、さらに、モンゴメリ法によるアルゴリズム例を（３）アルゴリズム３に示す。なお、以下、特に断りの無い限り、小文字（d等）はスカラー値を表わし、大文字（Ｐ等）は楕円曲線上の点を表わすものとする。又、符号“＾”はべき乗算を表わすものとし、“（”と“）２”とによって囲まれた数列は２進数で表現された数字を表わす。又、“S1：”等のように、Ｓを付した数字はアルゴリズムを表わすプログラム例におけるステップ数を示すものとする。更に、以下では、楕円曲線上の四則演算は“「”と“」”で囲うものとする。
（１）アルゴリズム１［バイナリ法（ＬＳＢ）］
S1:  T[0] ← 0,  T[1] ← P
S2:  for i = 0 upto n-1 {
S3:      if ( d[i] == 1 ) {
S4:          T[0] ← 「T[0] + T[1]」   ← ※
S5:      }
S6:      T[1] ← 「2*T[1]」
S7:  }
S8:  return T[0]
ここで、 T[0], T[1], T[2] は一時変数、ｄはｎビットのスカラー値で、d[i] はｄの下位ｉ番目のビットの値である。
【００１３】
例えば、５ビットの整数 d=21=2^4+2^2+2^0=(10101)2 についてスカラー倍算「ｄ×Ｐ」を計算する場合を考える。ステップS1においては変数 T[0] に点 O が、また、変数 T[1] に点 P が設定される。次のステップS2〜S7において i = 0, 1, 2, 3, 4 に対応する各処理が行なわれる。
【００１４】
i = 0のときには d[i] = d[0] = 1 なので、ステップS4では変数 T[0] に 「T[0] + T[1]」 が設定され、処理後の変数 T[0] の値は P となる。ステップS6では変数T[1] に 「2*T[1]」 が設定され、処理後の変数 T[1] の値は 「2×P」 となる。
【００１５】
i = 1 のときには d[i] = d[1] = 0 なので、ステップS3〜S5はスキップされる。ステップS6では変数 T[1] に 「2*T[1]」 が設定され、処理後の変数 T[1] の値は 「4×P」 となる。
【００１６】
i = 2 のときには d[i] = d[2] = 1 なので、ステップS4では変数 T[0] に「T[0] + T[1]」 が設定され、処理後の変数 T[0] の値は「5×P」となる。ステップS6では変数 T[1] に 「2*T[1]」 が設定され、処理後の変数 T[1] の値は 「8×P」 となる。
【００１７】
i = 3 のときには d[i] = d[3] = 0なので、ステップS3〜S5はスキップされる。ステップS6では変数 T[1] に 「2*T[1]」 が設定され、処理後の変数 T[1] の値は 「16×P」 となる。
【００１８】
i = 4のときには d[i] = d[0] = 1 なので、ステップS4では変数 T[0] に「T[0] +  T[1]」 が設定され、処理後の変数 T[0] の値は 「21×P」 となる。ステップS6では変数 T[1] に 「2*T[1]」 が設定され、処理後の変数 T[1] の値は 「32×P」 となる。
【００１９】
以上でステップS2〜S7の処理が終了し、最後のステップS8において変数 T[0] の値 「21×P」 が出力される。
（２）アルゴリズム２［バイナリ法（ＭＳＢ）］
S1:  T[0] ← P
S2:  for i = n-2 downto 0 {
S3:      T[0] ← 「2*T[0]」
S4:      if ( d[i] == 1 ) {
S5:          T[0] ← 「T[0] + P」   ← ※
S6:      }
S7:  }
S8:  return T[0]
ここで T[0] は一時変数、ｄはｎビットのスカラー値で、 d[i] はｄの下位ｉ番目のビットの値である。
【００２０】
例えば、５ビットの整数 d=21=2^4+2^2+2^0=(10101)2 についてスカラー倍算「ｄ×Ｐ」を計算する場合を考える。ステップS1においては変数 T[0] に点 P が設定され、その次のステップS2〜S7において i = 3, 2, 1, 0 に対応する処理が行なわれる。
【００２１】
i = 3 のとき、ステップS3では変数 T[0] に 「2*T[0]」 が設定され、処理後の変数 T[0] の値は 「2×P」 となる。また i = 3 のときには d[i] = d[3] = ０ なので、ステップS4〜S6はスキップされる。
【００２２】
i = 2 のとき、ステップS3では変数 T[0] に 「2*T[0]」 が設定され、処理後の変数 T[0] の値は 「4×P」 となる。また i = 2 のときには d[i] = d[2] = １なので、ステップS5では変数 T[0] に 「T[0] + P」 が設定され、処理後の変数 T[0] の値は 「5×P」 となる。
【００２３】
i = 1 のとき、ステップS3では変数 T[0] に 「2*T[0]」 が設定され、処理後の変数 T[0] の値は 「10×P」 となる。また i = 1 のときには d[i] = d[1] = 0なので、ステップS4〜S6はスキップされる。
【００２４】
i = 0 とき、ステップS3では変数 T[0] に 「2*T[0]」 が設定され、処理後の変数 T[0] の値は 「20×P」 となる。また i = 0 のときには d[i] = d[0] = 1なので、ステップS5では変数 T[0] に 「T[0] + P」 が設定され、処理後の変数 T[0] の値は 「21×P」 となる。
【００２５】
以上でステップS2〜S7の処理が終了し、最後のステップS8で変数 T[0] の値「21×P」 が出力される。
（３）アルゴリズム３［モンゴメリ法］
S1:  T[0] ← P,  T[1] ← 「2*P」
S2:  for i = n-2 downto 0 {
S3:      T[2] ← 「2*T[d[i]]」
S4:      T[1] ← 「T[0] + T[1]」
S5:      T[0] ← T[2-d[i]]
S6:      T[1] ← T[1+d[i]]
S7:  }
S8:  return T[0]
ここで T[0], T[1], T[2] は一時変数、ｄはｎビットのスカラー値で、 d[i] はｄの下位ｉ番目のビットの値である。
【００２６】
例えば、５ビットの整数 d=21=2^4+2^2+2^0=(10101)2 についてスカラー倍算「ｄ×Ｐ」を計算する場合を考える。ステップS1においては変数 T[0] に点 P が、また、変数 T[1] に点 「2×P」 が設定され、その次のステップS2〜S7において i = 3, 2, 1, 0 に対応する処理が行なわれる。
【００２７】
i = 3 のとき d[i] = d[3] = 0 である。ステップS3では変数 T[2] に 「2*T[0]」 が設定され、処理後の変数 T[2] の値は 「2×P」 となる。ステップS4では変数 T[1]  に 「T[0] + T[1]」 が設定され、処理後の変数 T[1] の値は 「3×P」 となる。ステップS5では変数 T[0] に T[2] が設定され、処理後の変数 T[0] の値は 「2×P」 となる。ステップS6では変数 T[1] に T[1] が設定され、処理後の変数 T[1] は 「3×P」 となる。
【００２８】
i = 2 のとき d[i] = d[2] = 1 である。ステップS3では変数 T[2] に 「2*T[1]」 が設定され、処理後の変数 T[2] の値は 「4×P」 となる。ステップS4では変数 T[1]  に 「T[0] + T[1]」 が設定され、処理後の変数 T[1] の値は 「6×P」 となる。ステップS5では変数 T[0] に T[1] が設定され、処理後の変数 T[0] の値は 「6×P」 となる。ステップS6では変数 T[1] に T[2] が設定され、処理後の変数 T[1] は 「6×P」 となる。
【００２９】
i = 1 のとき d[i] = d[1] = 0 である。ステップS3では変数 T[2] に 「2*T[0]」 が設定され、処理後の変数 T[2] の値は 「10×P」 となる。ステップS4では変数 T[1]  に 「T[0] + T[1]」 が設定され、処理後の変数 T[1] の値は 「11×P」 となる。ステップS5では変数 T[0] に T[2] が設定され、処理後の変数 T[0] の値は 「10×P」 となる。ステップS6では変数 T[1] に T[1] が設定され、処理後の変数 T[1] は 「11×P」 となる。
【００３０】
i = 0 のとき d[i] = d[0] = 0 である。ステップS3では変数 T[2] に 「2*T[1]」 が設定され、処理後の変数 T[2] の値は 「22×P」 となる。ステップS4では変数 T[1]  に 「T[0] + T[1]」 が設定され、処理後の変数 T[1] の値は 「21×P」 となる。ステップS5では変数 T[0] に T[1] が設定され、処理後の変数 T[0] の値は 「21×P」 となる。ステップS6では変数 T[1] に T[2] が設定され、処理後の変数 T[1] は 「22×P」 となる。
【００３１】
以上でステップS2〜S7の処理が終了し、最後のステップS8で変数 T[0] の値「21×P」 が出力される。
またスカラー倍算「ｄ×Ｐ」の実現手法としては、前述したバイナリ法（アルゴリズム１、アルゴリズム２）やモンゴメリ法（アルゴリズム３）の他に、ウィンドウ法（window method）と呼ばれる方法もある。例えば、幅４ビットのウィンドウ法は、初期処理としてＰの０〜１５倍を計算し、その結果をテーブルとして保持し、次にスカラー値を４ビット単位（ウィンド）に分割することにより、スカラー倍算を処理する。以下に、アルゴリズム４としてウィンドウ法（幅４ビット）のアルゴリズム例を示す。
（４）アルゴリズム４［ウィンドウ法（幅４ビット）］
S01:  W[0] ← O,  W[1] ← P
S02:  for i = 2 upto 15 {
S03:      W[i] = 「W[i-1] + P」
S04:  }
S05:  T[0] ← W[d[n-1,n-4]]
S06:  for i = n-5 downto 3 step -4 {
S07:      T[0] ← 「16*T[0]」
S08:      T[0] ← 「T[0] + W[d[i,i-3]]」
S09:  }
S10:  return T[0]
ここで、ｄはｎビットのスカラー値で、ｎは４の倍数と仮定する。また d[i,i-3]はｄの下位ｉビット目から（ｉ−３）ビットまでの４ビット値とする。 W[i] はウィンドウ法で使用するテーブルである。
【００３２】
例えば、５ビットの整数 d=21=2^4+2^2+2^0=(10101)2=(0001 0101)2 に対するスカラー倍算を考える。このときｄのビット長５は４の倍数ではないので、便宜上、その上位３ビットに０を挿入して８ビットとみなす。つまりｎ＝８である。まず、初期値としてステップS01において W[0] = 0 と W[1] = P が設定される。次に i = 2, 3, ..., 15に対し、ステップS02〜S04が実行される。各ｉに対し、ステップS03でW[i] = 「W[i-1] + P」 が設定される。このとき W[i] に設定されている値は 「i×P」 となる。ステップS02〜S04の処理の終了後、ステップS05で変数 T[0] にW[d[n-1,n-4]] = W[d[7,4]] = W[0001] = 「1×P」 が設定される。
【００３３】
次に i = 3 に対してステップS06〜S09が処理される。ステップS07ではT[0] ← 「16*T[0]」 が処理され、変数 T[0] には 「16×Ｐ」 が登録される。ステップS08では T[0] ← 「T[0] + W[d[i,i-3]]」 = 「T[0] + W[0101]」 = 「「16×P」 + 「5×P」」 = 「21×P」 が処理され、変数 T[0] に 「21×P」 が登録される。
【００３４】
以上でステップS06〜S09の処理が終了する。最後にステップS10において変数 T[0] の値 「21×P」 が出力される。このようにウィンドウ法では、あらかじめ作成したテーブルを用いてスカラー倍算「ｄ×Ｐ」を計算する。
【００３５】
上述したアルゴリズム１・アルゴリズム２を使用してスカラー倍算を計算した場合、いずれも※印を付したステップの処理は、dのビット値 d[i] に応じて実行されたりされなかったりする。単純消費電力解析（ＳＰＡ）はこの性質を利用して秘密鍵dを解析する。多くの実験から、楕円曲線上の点の加算（楕円加算）と２倍算（楕円２倍算）の消費電力波形は容易に区別可能であることが知られている。従って、プロセッサにおけるアルゴリズム１およびアルゴリズム２の演算において発生する電力波形を測定することによって、その波形から楕円加算と楕円２倍算の演算の順序と回数がわかるため、結局は秘密鍵ｄを求めることが可能となる。なおアルゴリズム３とアルゴリズム４はビット値 d[i] に依存した条件分岐を持たないため、ＳＰＡに対する耐性を有している。
【００３６】
アルゴリズム１・アルゴリズム２に対するＳＰＡへの対策として、アド・アンド・ダブル・オールウェイズ（add-and-double-always）と呼ばれる、加算と２倍算とをアルゴリズムの実行中常に行なう方法が J. Coron, “Resistance against Differencial Power Analysis”, Cryptographic Hardware and Embedded Systems 1999 (CHES 1999), Lecture Notes in Computer Science Vol. 1717, pp. 292-302, Springer-Verlag, 1999 (文献 [Coron99]) で提案されている。この方法では、常に楕円加算と楕円２倍算とが交互に計算されるため、ＳＰＡに対して安全性を持つとされている。前述したアルゴリズム１およびアルゴリズム２に対し、アド・アンド・ダブル・オールウェイズを施したアルゴリズム例を（５）アルゴリズム１’および（６）アルゴリズム２’として示す。
（５）アルゴリズム１’［バイナリ法 (ＬＳＢ，アド・アンド・ダブル・オールウェイズ)］
S1:  T[0] ← 0,  T[2] ← P
S2:  for i = 0 upto n-1 {
S3:      T[1] ← 「T[0] + T[2]」
S4:      T[2] ← 「2*T[2]」
S5:      T[0] ← T[d[i]]
S6:  }
S7:  return T[0]
ここで T[0], T[1], T[2] はいずれも一時変数、ｄはｎビットのスカラー値で、d[i] はｄの下位ｉビット目の値である。
（６）アルゴリズム２’［バイナリ法 (ＭＳＢ，アド・アンド・ダブル・オールウェイズ)］
S1:  T[0] ← 0,  T[2] ← P
S2:  for i = n-1 downto 0 {
S3:      T[0] ← 「2*T[0]」
S4:      T[1] ← 「T[0] + T[2]」
S5:      T[0] ← T[d[i]]
S6:  }
S7:  return T[0]
ここで T[0], T[1], T[2] はいずれも一時変数、ｄはｎビットのスカラー値で、d[i]はｄの下位ｉビット目の値である。
【００３７】
上述したアルゴリズム１’、アルゴリズム２’、アルゴリズム３、アルゴリズム４などを用いることによりＳＰＡを防止することができるが、文献 [Coron99] には、これらのアルゴリズムに対するＤＰＡについても述べられており、これらアルゴリズムを用いたとしても、ＤＰＡによって秘密鍵を解析できることが示されている。またＲＰＡやＺＶＡによる解析法も提案されている。
【００３８】
ＳＰＡ・ＤＰＡ・ＲＰＡ・ＺＶＡに対しては、バイナリ法やモンゴメリ法は安全でない。これら電力解析法に対する対策として C. Clavier, M. Joye, "Universal Exponentiation Algorithm -- A First Step towards Provable SPA-resistance--", Cryptographic Hardware and Embedded Systems 2001 (CHES 2001), Lecture Notes in Computer Science Vol. 2162, pp.300-308, Springer-Verlag, 2001 (文献 [Clavier-Joye01]) にて提案されている指数分割法（Exponent Splitting method；ＥＳ）がある。このＥＳはスカラー値をランダムに変化させる手法であって、乱数ｒによって、スカラーｄをｄ＝ｒ＋（ｄ−ｒ）に分割し、２つのスカラー倍算「ｒ×Ｐ」と「（ｄ−ｒ）×Ｐ」とを別々に計算し、
「「ｒ×Ｐ」＋「（ｄ−ｒ）×Ｐ」」＝「ｄ×Ｐ」
が成り立つという性質を利用して、２つのスカラー倍算の結果を足しあわせることで「ｄ×Ｐ」を計算するものである。
【００３９】
ここで、２つのスカラー倍算「ｒ×Ｐ」および「（ｄ−ｒ）×Ｐ」には、他のＳＰＡ／ＤＰＡに耐性を有するアルゴリズムを用いる。
（７）アルゴリズム５［指数分割法］
S1:  r ← random()
S2:  T[1] ← scalar( r, P )
S3:  T[2] ← scalar( d-r, P )
S4:  T[0] ← 「T[1] + T[2]」
S5:  return T[0]
ここで random() は乱数を生成する関数である。又、scalar( d, P ) はスカラー倍算「ｄ×Ｐ」を計算する関数であって、具体的には、前述したアルゴリズム１’、アルゴリズム２’、アルゴリズム３、アルゴリズム４等を用いて計算される。また、変数 r, T[0], T[1], T[2] はいずれも一時変数である。
【００４０】
ＥＳはＳＰＡ・ＤＰＡ・ＲＰＡ・ＺＶＡの全てに対して安全といえるが、計算効率上、オーバーヘッドが大きくなる欠点がある。
特許文献１には、楕円加算と楕円２倍算を１つの演算として定義し、その演算の中で同じ種類の演算を並列に実行することで、サイドチャネル攻撃に対する耐性を持ち、かつ、スカラー倍算を高速で計算できる演算手法が記載されている。
【特許文献１】特開2004-53814号公報
【発明の開示】
【００４１】
本発明の課題は、ＳＰＡ・ＤＰＡ・ＲＰＡ・ＺＶＡに対して秘密情報の推定を困難にし、暗号処理の安全性を高めることが可能な暗号化処理装置を提供することである。
本発明の第１の暗号化処理装置は、個人鍵を用いて暗号化処理を行う暗号化処理装置において、乱数に基づいたランダムな整数値を生成するランダム値生成手段と、暗号化するためのアルゴリズムを実行する際において、該ランダムな整数値を本来演算すべき値に含めて暗号化演算を行う暗号化演算手段と、該暗号化演算の実行後、得られた値から、該ランダムな整数値を演算に含めた効果を相殺するランダム化解除手段とを備えることを特徴とする。
【００４２】
本発明の第２の暗号化処理装置は、個人鍵を用いて楕円曲線暗号処理を行う暗号化処理装置において、乱数に基づいて生成された楕円曲線上の点Ｒを初期点にセットするランダム化手段と、この初期点、楕円曲線暗号のためのあるスカラー値ｄ、楕円曲線上のある点Ｐを用いてスカラー倍演算を演算する手段と、その演算によって得られた点Ｑから点Ｒに関係する点Ｒ’を用いてＱ−Ｒ’を実行するランダム化解除手段と、その結果を出力する手段とを備えることを特徴とする。
【００４３】
本発明の第３の暗号化処理装置は、個人鍵を用いてＲＳＡ暗号処理を行う暗号化処理装置において、乱数に基づいて生成された整数ｒを初期値にセットするランダム化手段と、この初期値、ＲＳＡ暗号のためのあるべき指数ｄ、ある整数ｐを用いてべき乗剰余演算を演算する手段と、その演算によって得られた整数ｑからｒに関係する値ｒ’を用いて乗算剰余演算ｑ／ｒ’を実行するランダム化解除手段と、その結果を出力する手段とを備えることを特徴とする。
【００４４】
本発明によれば、アルゴリズムを実行して演算するたびに新たに生成されるランダムな整数値（楕円曲線上の点の座標値、あるいは、有限体上の整数値）を含めて演算するので、電力解析攻撃に遭っても、攻撃者が得る情報が毎回ランダムに異なる情報となるので、秘密情報を推定することを難しくし、暗号処理の安全性を高めることができる。
【発明を実施するための最良の形態】
【００４５】
本発明の実施形態によれば、個人鍵を用いて楕円曲線暗号処理を行う暗号装置は、乱数に基づいて生成された楕円曲線上の点Ｒを初期点にセットするランダム化手段と、この初期点、楕円曲線暗号のためのあるスカラー値ｄ、楕円曲線上のある点Ｐを用いてスカラー倍演算を演算する手段と、その演算によって得られた点Ｑから点Ｒに関係する点Ｒ’を用いてＱ−Ｒ’を実行するランダム化解除手段と、その結果を出力する手段とを備える。
【００４６】
あるいは、本発明の実施形態をＲＳＡ暗号処理に適用した場合は、個人鍵を用いてＲＳＡ暗号処理を行う暗号装置は、乱数に基づいて生成された整数ｒを初期値にセットするランダム化手段と、この初期値、ＲＳＡ暗号のためのあるべき指数ｄ、ある整数ｐを用いてべき乗剰余演算を演算する手段と、その演算によって得られた整数ｑからｒに関係する値ｒ’を用いてｑ／ｒ’を実行するランダム化解除手段と、その結果を出力する手段とを備える。
【００４７】
本発明の実施形態によれば、楕円曲線暗号におけるスカラー倍算の処理量が少なく、かつ、ＳＰＡ、ＤＰＡ、ＲＰＡ、ＺＶＡに対して安全な処理法を実現できる。
また、本発明の実施形態のＲＳＡ暗号処理への適用においては、ＳＰＡ、ＤＰＡ、ＲＰＡ、ＺＶＡに対して安全な処理方法を提供できる。
（ａ）基本説明
本発明の一実施形態としての楕円曲線暗号装置は、例えば、楕円曲線暗号の専用の情報処理装置，パーソナルコンピュータ，ＩＣカード（スマートカード）等に内蔵されたＩＣチップ，携帯電話機，携帯情報端末装置（ＰＤＡ（Personal Data Assistant）等），ＤＶＤプレーヤ等として実現されるものであり、演算を行うプロセッサを有して構成されるものである。
【００４８】
以下の説明では、本発明の実施形態にかかる楕円曲線暗号演算方法を、ｐを素数、ｍを１以上の整数とし、要素数ｐ＾ｍの有限体ＧＦ（ｐ＾ｍ）上の楕円曲線に適用した場合について説明する。なお、以下、特に断りの無い限り、小文字（d等）はスカラー値を表わし、大文字（Ｐ，Ｔ等）は楕円曲線上の点を表わすものとする。又、符号“＾”はべき乗算を表わすものとし、“（”と“）２”とによって囲まれた数列は２進数で表現された数字を表わす。又、“S01：”等のように、Ｓを付した数字はアルゴリズムを表わすプログラム例におけるステップ数を示すものとする。更に、楕円曲線上の四則演算を“「”と“」”で囲んで示す。
【００４９】
ＧＦ（ｐ＾ｍ）上の楕円曲線Ｅは、以下の方程式を満たす点（ｘ，ｙ）の集合に、無限遠点（以下、ゼロ点という場合もある）と呼ばれる点∞を加えた集合である。無限遠点∞を０と表わすこともある。
E：ｙ＾２＋ａ１×ｘ×ｙ＋ａ３×ｙ＝ｘ＾３＋ａ２×ｘ＾２＋ａ４×ｘ＋ａ６
ここでａ１，ａ２，ａ３，ａ４，ａ６，ｘ，ｙはそれぞれＧＦ（ｐ＾ｍ）の要素である。楕円曲線上の点は（ｘ，ｙ）のような座標形式で表現できるが、無限遠点∞は（ｘ，ｙ）のような座標形式で表現することができない唯一の点である。
【００５０】
ＰをＧＦ（ｐ＾ｍ）上の楕円曲線Ｅ上の点とし、以下のようにＰの逆元「−Ｐ」を定義する。
（１）Ｐ＝∞ならば、「−Ｐ」＝∞
（２）Ｐ≠∞ならば、Ｐ＝（ｘ，ｙ）としたときに、
「−Ｐ」＝（ｘ，−ｙ−ａ１×ｘ−ａ３）
また、Ｐ１，Ｐ２をＧＦ（ｐ＾ｍ）上の楕円曲線Ｅ上の２点とし、以下に示すようにＰ１とＰ２との和Ｐ３＝「Ｐ１＋Ｐ２」を定義する。
（１）Ｐ１＝∞ならば、Ｐ３＝Ｐ２
（２）Ｐ２＝∞ならば、Ｐ３＝Ｐ１
（３）Ｐ１＝「−Ｐ２」ならば、Ｐ３＝∞
（４）Ｐ１≠「−Ｐ２」ならばＰ１＝（ｘ１，ｙ１），Ｐ２＝（ｘ２，ｙ２），Ｐ３＝（ｘ３，ｙ３）としたときに、
ｘ３＝λ＾２＋ａ１×λ−ａ２−ｘ１−ｘ２，
ｙ３＝−（λ＋ａ１）×ｘ３−ν−ａ３，
ただし、
Ｐ１≠Ｐ２のとき
λ＝（ｙ２−ｙ１）／（ｘ２−ｘ１）
ν＝（ｙ１×ｘ２−ｙ２×ｘ１）／（ｘ２−ｘ１）
Ｐ１＝Ｐ２のとき
λ＝（３×ｘ１＾２＋２×ａ２×ｘ＋ａ４−ａ１×ｙ１）／（２×ｙ１＋ａ１×ｘ１＋ａ３）
ν＝（−ｘ１＾３＋ａ４×ｘ１＋２×ａ６−ａ３×ｙ１）／（２×ｙ１＋ａ１×ｘ１＋ａ３）
と定める。
【００５１】
Ｐ１≠Ｐ２のときに、「Ｐ１＋Ｐ２」を計算することを楕円加算、Ｐ１＝Ｐ２のときに「Ｐ１＋Ｐ２」＝「２×Ｐ１」を計算することを楕円２倍算という。楕円加算・楕円２倍算は、有限体ＧＦ（ｐ＾ｍ）での加減算・乗算・平方算・逆元計算の組み合わせによって計算される。
【００５２】
ｐを素数とするとき、有限体ＧＦ（ｐ）を素体という。特に、ｐが５以上の素数の場合には、素体ＧＦ（ｐ）上の楕円曲線Ｅは、方程式
E：ｙ＾２＝ｘ＾３＋ａ×ｘ＋ｂ
を満たす点（ｘ，ｙ）の集合上に、無限遠点と呼ばれる点∞を加えた集合である。無限遠点∞を０と表わすこともある。又、ａ，ｂ，ｘ，ｙはそれぞれＧＦ（ｐ）の要素である。楕円曲線上の点は（ｘ，ｙ）のような座標形式で表現できるが、無限遠点∞は（ｘ，ｙ）のような座標形式で表現することができない唯一の点である。
【００５３】
ＰをＧＦ（ｐ）上の楕円曲線Ｅ上の点とし、以下に示すようにＰの逆元「−Ｐ」を定義する。
（１）Ｐ＝∞ならば、「−Ｐ」＝∞
（２）Ｐ≠∞ならば、Ｐ＝（ｘ，ｙ）としたときに、「−Ｐ」＝（ｘ，−ｙ）
また、Ｐ１，Ｐ２をＧＦ（ｐ）上の楕円曲線Ｅ上の２点とし、以下に示すようにしてＰ１とＰ２との和Ｐ３＝「Ｐ１＋Ｐ２」を定義する。
（１）Ｐ１＝∞ならば、Ｐ３＝Ｐ２
（２）Ｐ２＝∞ならば、Ｐ３＝Ｐ１
（３）Ｐ１＝「−Ｐ２」ならば、Ｐ３＝∞
（４）Ｐ１≠−Ｐ２ならば、Ｐ１＝（ｘ１，ｙ１），Ｐ２＝（ｘ２，ｙ２），Ｐ３＝（ｘ３，ｙ３）としたときに、
ｘ３＝λ＾２−ｘ１−ｘ２
ｙ３＝−λ×ｘ３−ν，
ただし
Ｐ１≠Ｐ２のとき
λ＝（ｙ２−ｙ１）／（ｘ２−ｘ１）
ν＝（ｙ１×ｘ２−ｙ２×ｘ１）／（ｘ２−ｘ１） 
Ｐ１＝Ｐ２のとき
λ＝（３×ｘ１＾２＋ａ）／（２×ｙ１）
ν＝（−ｘ１＾３＋ａ×ｘ１＋２×ｂ）／（２×ｙ１）
と定める。
【００５４】
Ｐ１≠Ｐ２のときに、「Ｐ１＋Ｐ２」を計算することを楕円加算、Ｐ１＝Ｐ２のときに「Ｐ１＋Ｐ２」＝「２×Ｐ１」を計算することを楕円２倍算という。楕円加算・楕円２倍算は、有限体ＧＦ（ｐ）での加減算・乗算・平方算・逆元計算の組み合わせによって計算される。
【００５５】
図１は楕円加算を説明するための図、図２は楕円２倍算を説明するための図である。
楕円加算は、図１に示すように、楕円曲線上の点Ｐ１＝（ｘ１，ｙ１）とＰ２＝（ｘ２，ｙ２）とを結ぶ直線と楕円曲線との交点を、ｘ軸で折り返した点Ｐ３＝「Ｐ１＋Ｐ２」＝（ｘ３，ｙ３）として定義される。図１では、素体上の楕円曲線として、式ｙ＾２＝ｘ＾３−ｘで表される曲線が示され、ｘ３＝（（ｙ１−ｙ２）／（ｘ１−ｘ２））２−ｘ１−ｘ２、ｙ３＝（（ｙ１−ｙ２）／（ｘ１−ｘ２））（ｘ１−ｘ３）−ｙ１で定義されている。
【００５６】
楕円２倍算は、図２に示されるように、楕円曲線上の点Ｐ１＝（ｘ１，ｙ１）の接線と楕円曲線との交点を、ｘ軸で折り返した点Ｐ４＝「Ｐ１＋Ｐ１」＝「２×Ｐ１」＝（ｘ４，ｙ４）として定義される。図２では、素体上の楕円曲線として、ｙ＾２＝ｘ＾３−ｘが示され、ｘ４＝（（３ｘ１＾２−１）／（２ｙ１））２−２ｘ１、ｙ４＝（（３ｘ１＾２−１）／（２ｙ１））（ｘ１−ｘ４）−ｙ１で定義されている。
【００５７】
有限体上の楕円曲線Ｅと、ベースポイントと呼ばれる曲線上の点Ｐと、スカラーと呼ばれる整数ｄとに対して、点「ｄ×Ｐ」＝「Ｐ＋Ｐ＋…＋Ｐ」（ｄ個の和）を計算することをスカラー倍算という。スカラー倍算は、楕円加算、楕円２倍算の組み合わせによって実現される。
【００５８】
楕円加算、楕円２倍算、スカラー倍算の計算時間は、有限体における乗算、平方算、逆元計算の計算時間の和によって見積もられることが多い。これは実際の楕円加算、楕円２倍算、スカラー倍算の計算が、有限体における加減算・乗算・平方算・逆元計算の組み合わせで計算され、多くの場合、加減算の計算時間はその他の計算時間に比べて無視できるほど短いからである。
【００５９】
一般に有限体ＧＦ（ｐ＾ｍ）での逆元計算の計算時間は、乗算・平方算の計算時間に比べて非常に大きくなることが多い。このため、楕円曲線の点を表現する上で射影座標が使用されることがある。
【００６０】
射影座標では、ＧＦ（ｐ＾ｍ）上の楕円曲線の点は（Ｘ：Ｙ：Ｚ）のような３つの要素の組み合わせで表される。ただし（Ｘ：Ｙ：Ｚ）とｒ≠０であるＧＦ（ｐ＾ｍ）の要素ｒに対し（ｒ×Ｘ：ｒ×Ｙ：ｒ×Ｚ）は同じ点と考える。射影座標における楕円曲線の方程式は、元の方程式にｘ＝Ｘ／Ｚ，ｙ＝Ｙ／Ｚを代入して、
Ｅ：Ｙ＾２×Ｚ＝Ｘ＾３＋ａ×Ｘ×Ｚ＾２＋ｂ×Ｚ＾３
と表される。射影座標を用いると、楕円曲線上の全ての点は（Ｘ：Ｙ：Ｚ）のような座標形式で表現することができる。無限遠点は∞＝（０：１：０）となる。
【００６１】
H. Cohen, A. Miyaji, and T. Ono, “Efficient Elliptic Curve Exponentiation Using Mixed Coordinates”, Asiacrypt 1998, Lecture Notes in Computer Science vol. 1514, pp.51-65, Springer-Verlag, 1998 (文献 [CMO98]) によると、素体上の射影座標における楕円加算の計算時間は１２Ｍ＋２Ｓ、楕円２倍算の計算時間は７Ｍ＋５Ｓになることが報告されている。ここで１Ｍ、１Ｓは、素体上で乗算・平方算を１回計算するのに必要な計算時間を表す。
【００６２】
射影座標の一種に、ヤコビアン座標がある。ヤコビアン座標では、ＧＦ（ｐ＾ｍ）上の楕円曲線の点は（Ｘ：Ｙ：Ｚ）のような３つの要素の組み合わせで表される。ただし（Ｘ：Ｙ：Ｚ）とｒ≠０であるＧＦ（ｐ＾ｍ）の要素ｒに対し（ｒ２×Ｘ：ｒ３×Ｙ：ｒ×Ｚ）は同じ点と考える。ヤコビアン座標における楕円曲線の方程式は、元の方程式にｘ＝Ｘ／Ｚ２，ｙ＝Ｙ／Ｚ３を代入して、
Ｅ：Ｙ＾２×Ｚ＝Ｘ＾３＋ａ×Ｘ×Ｚ＾４＋ｂ×Ｚ＾６
と表される。ヤコビアン座標を用いると、楕円曲線上の全ての点は（Ｘ：Ｙ：Ｚ）のような座標形式で表現することができる。無限遠点は∞＝（０：１：０）となる。
【００６３】
文献 [CMO98] によると、素体上のヤコビアン座標における楕円加算の計算時間は１２Ｍ＋４Ｓ、楕円２倍算の計算時間は４Ｍ＋６Ｓになることが報告されている。ここで１Ｍ、１Ｓは、素体上で乗算・平方算を１回計算するのに必要な計算時間を表す。
（ｂ）実施形態の実現例
以下、本発明の実施形態に係る楕円曲線暗号演算方法を、ｐを５以上の素数とし、要素数ｐの有限体ＧＦ（ｐ）上の楕円曲線に適用した場合について説明する。
【００６４】
ＧＦ（ｐ）上の楕円曲線Ｅは、以下の式で表わすことができる。
Ｅ：ｙ＾２＝ｘ＾３＋ａ×ｘ＋ｂ
ここでａ，ｂ，ｘ，ｙはＧＦ（ｐ）の要素で、４×ａ＾３＋２７×ｂ＾２≠０を満たす。
【００６５】
図３は、本発明に係る楕円曲線暗号装置１１の要部の構成を示す図である。
本楕円曲線暗号装置１１は、図３に示すように、演算部（プロセッサ）１２と記憶部１６とをそなえて構成されている。記憶部１６は、後述する楕円曲線暗号の楕円加算，楕円２倍算等の演算プログラムを記憶するものである。
【００６６】
演算部１２は、演算器１３，レジスタ群１４および演算結果出力レジスタ群１５をそなえて構成されている。演算器１３は、記憶部１６に格納された楕円曲線暗号プログラムをレジスタ群１４を用いて実行するものであって、その演算結果を演算結果出力レジスタ群１５に出力するようになっている。
【００６７】
レジスタ群１４および演算結果出力レジスタ群１５は、いずれも複数のレジスタからなり、これらのレジスタに、演算を行なうための数値や、演算実行後の結果，現在実行しているコードのメモリアドレス、ＣＰＵの状態などを格納するものであり、演算結果出力レジスタ群１５には、特に演算器１３による演算結果が格納されるようになっている。
【００６８】
図４は、本発明の一実施形態としての楕円曲線暗号装置１１の機能構成を示すブロック図である。
本楕円曲線暗号装置１１は、図４に示すように、乱数生成部２１、スカラー倍算処理部２２、及び、randompoint()関す処理部２３をそなえて構成されている。本楕円曲線暗号装置１１は、ベースポイントＰとベースポイントに乗算するスカラーｄを入力し、スカラー倍した楕円曲線上の点「ｄ×Ｐ」を出力する。乱数生成部２１は、スカラー倍算処理部２２が演算に使う数値をランダム化するために使用する乱数を生成する。randompoint()関数処理部２３は、乱数生成部２１の生成した乱数に基づいて楕円曲線上のランダムな点の座標値を生成する処理部である。
【００６９】
楕円曲線暗号に対して、前述したアルゴリズム１’、アルゴリズム２’、アルゴリズム３、アルゴリズム４において、本発明の実施形態の方法を適用した実現例について説明する。以下では発明の実施形態の方法をＲＩＰと記す。
【００７０】
まず、バイナリ法（ＬＳＢ）と組み合わせた実現例を示す。（アルゴリズム６）
（８）アルゴリズム６（ＲＩＰ（ＬＳＢ，０））
S1:  R ← randompoint()
S2:  T[0] ← R,  T[2] ← P
S3:  for i = 0 upto n-1 {
S4:      T[1] ← 「T[0] + T[2]」
S5:      T[2] ← 「2*T[2]」
S6:      T[0] ← T[d[i]]
S7:  }
S8:  return 「T[0] - R」
ここで R, T[0], T[1], T[2] はいずれも一時変数、ｄはｎビットのスカラー値で、d[i] はｄの下位ｉビット目の値である。また関数 randompoint() は、楕円曲線上のランダムな点を生成する関数である。ここで、アルゴリズムの動作の仕方は、前述のバイナリ法（ＬＳＢ）と同様であるが、演算する数値にランダムな値が加えられていることが分かる。このランダムな値は演算毎に関数randompoint()によって生成されるために、アルゴリズムが同じ楕円曲線上の点の演算をしていても、電力解析攻撃によって電力値から分かるハミング重みが毎回違って観測される。したがって、電力解析攻撃によって重要な情報が盗まれる可能性を低くすることができる。なお、ステップＳ７終了時点で、T[0]の値は、「「ｄ×Ｐ」＋Ｒ」となっている。
【００７１】
次にアルゴリズム６における関数 randompoint() の実現方法を述べる。
・方法１：ｘ座標値をランダムに生成。点Ｒを生成する際に、ｘ座標をランダムに発生させ、対応するｙ座標値が存在するかどうかをチェックする。具体的には、例えば標数が５以上の有限体上の楕円曲線の方程式
ｙ＾２＝ｘ＾３＋ａ×ｘ＋ｂ
が与えられているとき、ｘ座標用のランダム値ｒを発生させる。このとき右辺にｘ＝ｒを代入した値ｒ＾３＋ａ×ｒ＋ｂを求め、この値が平方根を持つかどうかをチェックする。平方根を持つ場合にはその平方根をｙ座標として求め、ｒとこの平方根の値の組を出力する。平方根が存在しない場合には、ランダム値ｒを求めるところからやり直す。
・方法２：テーブルの利用。あらかじめＲの候補となるランダムな点の集合をテーブルとして保持し、関数の呼び出しごとに、テーブルの中からランダムにＲを選んで出力する。
・方法３：固定点の乱数倍。ある固定点Ｑを保持し、関数の呼び出しごとにランダムな値ｒを生成し、スカラー倍算「ｒ×Ｑ」を計算し、Ｒとして「ｒ×Ｑ」を出力する。
・方法４：固定点の利用。ある固定点Ｑを射影座標表現を（Ｘ：Ｙ：Ｚ）として保持し、関数の呼び出しごとにランダムな値ｒを生成し、各座標値をｒ倍ずつした結果（ｒ×Ｘ：ｒ×Ｙ：ｒ×Ｚ）をＲとして出力する。ヤコビアン座標を用いても同様の効果を得ることができる。
・方法５：ある固定点Ｒを保持し、関数の呼び出しに対してＲを出力し、呼び出し後にＲ←「２×Ｒ」として更新する。
【００７２】
次にバイナリ法（ＭＳＢ）と組み合わせた実現例を示す。（アルゴリズム７）
（９）アルゴリズム７（ＲＩＰ（ＭＳＢ，０））
S1:  R ← randompoint()
S2:  T[0] ← R,  T[2] ← P
S3:  for i = n-1 downto 0 {
S4:      T[0] ← 「2*T[0]」
S5:      T[1] ← 「T[0] + T[2]」
S6:      T[0] ← T[d[i]]
S7:      R ← 「2*R」
S8:  }
S9:  return 「T[0] - R」
ここで R, T[0], T[1], T[2] はいずれも一時変数、ｄはｎビットのスカラー値で、d[i] はｄの下位ｉビット目の値である。また関数 randompoint() は、楕円曲線上のランダムな点を生成する関数であり、実現方法については前述の方法１〜方法５などが考えられる。アルゴリズム７において、アルゴリズムの動作の仕方は、前述のバイナリ法（ＭＳＢ）と同じであるが、ランダムな点が計算に含まれているところが異なっている。
【００７３】
この場合も前述同様、ランダムな点Ｒを演算の中に組み込むことにより、電力攻撃に対する耐性を得る。ステップＳ８の終了時点でT[0]の値は、「ｄ×Ｐ＋Ｒ」となる。
バイナリ法（ＭＳＢ）と組み合わせた別の実施例を示す。（アルゴリズム７’）
（１０）アルゴリズム７’（ＲＩＰ（ＭＳＢ，０）’）
S1:  (R, R’) ← randompoint()
S2:  T[0] ← R,  T[2] ← P
S3:  for i = n-1 downto 0 {
S4:      T[0] ← 「2*T[0]」
S5:      T[1] ← 「T[0] + T[2]」
S6:      T[0] ← T[d[i]]
S7:  }
S8:  return 「T[0] - R’」
ここで R, R’, T[0], T[1], T[2] はいずれも一時変数、ｄはｎビットのスカラー値で、d[i] はｄの下位ｉビット目の値である。また関数 randompoint() は、楕円曲線上のランダムな点とそれに関連する点の２点を生成する関数であり、実現方法は後述する。このアルゴリズムは、基本的にバイナリ法（ＭＳＢ）と同様に動作するが、ランダム点の用い方が異なる。関数randompoint()は、耐タンパ性を獲得するためのＲの値のほかに、ステップＳ７の終了時点で演算結果に余分に楕円加算されている値を取り除くためのＲ’を生成する。上記アルゴリズムでは、ステップＳ７の終了時点で、T[0]の値は、「ｄ×Ｐ＋２＾ｎ×Ｒ」となっている。
【００７４】
Ｒ’を得る方法としては、以下のような方法が考えられる。
・方法１’〜方法５’：関数呼び出しごとに、方法１〜方法５のそれぞれの方法によって点Ｒを求め、この点Ｒをもとに点Ｒ’＝「２＾ｎ×Ｒ」を計算し、点のペアＲとＲ’を出力する
・方法６’：ある固定点Ｒと、Ｒ’＝「２＾ｎ×Ｒ」である固定点Ｒ’を保持し、関数の呼び出しに対して点のペア（Ｒ，Ｒ’）を出力する。呼び出し後にＲ←「２×Ｒ」、Ｒ’←「２×Ｒ’」として更新する。
【００７５】
次にモンゴメリ法と組み合わせた実現例を示す。（アルゴリズム８）
（１１）アルゴリズム８（ＲＩＰ（Ｍｏｎ，０＋１））
S1:  (R,R’) ← randompoint()
S2:  T[0] ← 「P + R」,  T[1] ← 「「2*P」 + R」
S3:  for i = n-2 downto 0 {
S4:      T[2] ← 「2*T[d[i]]」
S5:      T[1] ← 「T[0] + T[1]」
S6:      T[0] ← T[2-d[i]]
S7:      T[1] ← T[1+d[i]]
S8:  }
S9:  return 「T[0] - R’」
ここで R, R’, T[0], T[1], T[2] は一時変数、ｄはｎビットのスカラー値で、 d[i] はｄの下位ｉ番目のビットの値である。また関数 randompoint() は、楕円曲線上のランダムな点Ｒとそれに関連する点Ｒ’の２点を生成する関数であり、以下のような実現方法が考えられる。このアルゴリズムは、前述のモンゴメリ法と同様に動作するが、ランダム点が使用されている。この場合もアルゴリズム７と同様に、耐タンパ性を獲得するためのＲと演算後に正しい値を得るためのＲ’をrandompoint()が生成する。ステップＳ８の終了時点でT[0]の値は、「ｄ×Ｐ＋２＾（ｎ−１）×Ｒ」となっている。
【００７６】
Ｒ’を生成する方法として、以下のような方法が考えられる。
・  方法１’’〜方法５’’：関数呼び出しごとに、方法１〜方法５のそれぞれの方法によって点Ｒを求め、この点Ｒをもとに点Ｒ’＝「２＾（ｎ−１）×Ｒ」を計算し、点のペアＲとＲ’を出力する。
・  方法６’’：ある固定点Ｒと、Ｒ’＝「２＾（ｎ―１）×Ｒ」である固定点Ｒ’を保持し、関数の呼び出しに対して点のペア（Ｒ，Ｒ’）を出力する。呼び出し後にＲ←「２×Ｒ」、Ｒ’←「２×Ｒ’」として更新する。
【００７７】
次にウィンドウ法（ビット幅４）と組み合わせた実現例を示す。（アルゴリズム９）
（１２）アルゴリズム９［ＲＩＰ（Ｗ）（幅４ビット）］
S1:  R ← randompoint()
S2:  W[0] ← 0,  W[1] ← P
S3:  for i = 2 upto 15 {
S4:      W[i] = 「W[i-1] + P」
S5:  }
S6:  T[0] ← 「R + W[d[n-1,n-4]]」
S7:  for i = n-5 downto 3 step -4 {
S8:      T[0] ← 「16*T[0]」
S9:      T[0] ← 「T[0] + W[d[i,i-3]]」
S10:  }
S11:  return 「T[0] - R」
ここで、ｄはｎビットのスカラー値で、ｎは４の倍数と仮定する。また d[i,i-3]はｄの下位ｉビット目から（ｉ−３）ビットまでの４ビット値とする。 W[i] はウィンドウ法で使用するテーブルである。また関数 randompoint() は、楕円曲線上のランダムな点を生成する関数であり、実現方法については前述の方法１〜方法５などが考えられる。
【００７８】
このアルゴリズムは、前述のウィンドウ法と同様に動作するが、ランダム点が用いられている。この場合には、ステップＳ１０の終了時点で、T[0]の値が「「ｄ×Ｐ」＋Ｒ」となっているので、ステップＳ１１において、T[0]からＲを消去している。
【００７９】
また、上述した各実施形態においては、ｐを５以上の素数とし、要素数ｐの有限体ＧＦ（ｐ）上の楕円曲線に適用した場合について説明しているが、これに限定されるものではなく、本発明の趣旨を逸脱しない範囲で種々変形して実施することができる。
【００８０】
さらに、上述した各実施形態においては、本発明内容を楕円曲線暗号に適用した場合について説明しているが、ＲＳＡ暗号に対しても、本発明の趣旨を逸脱しない範囲で種々変形して実施することができる。ここで、変形においては、以下のような楕円曲線暗号演算からＲＳＡ暗号演算（有限体上の剰余演算）への置き換えを用いる：
楕円加算「Ｐ＋Ｑ」 → 乗算剰余演算 p*q (mod n)
楕円２倍算「２×Ｐ」→ ２乗剰余演算 p^2 (mod n)
スカラー倍算「ｄ×Ｐ」 → べき乗剰余演算 p^d (mod n)
逆元「−Ｐ」 → p*q=1 (mod n)となるq。このqをp^(-1)と記載する。
【００８１】
なお、本発明の各実施形態が開示されていれば、本発明の楕円曲線暗号装置，楕円曲線暗号方法，楕円曲線暗号プログラムおよび同プログラムを記録したコンピュータ読取可能な記録媒体を当業者によって実施・製造することが可能である。
【００８２】
図５は、本発明の実施形態の暗号化処理装置のハードウェア環境図である。
外部記憶装置３３に格納された本発明の実施形態を実現するプログラムは、バス３９を介してメモリ３２にコピーされ、ＣＰＵ３１によって実行される。ユーザからの入力は、入力装置３６から入力される。入力装置３６は、キーボード、マウス、テンプレート等からなる。ユーザへの情報の提示は、出力装置３７によって行われる。出力装置３７は、ディスプレイ等からなる。また、当該プログラムは、ディスケットやＣＤ−ＲＯＭ、ＤＶＤ等の可搬記録媒体３５に格納することも可能であり、媒体駆動装置３４を使って、これをメモリ３２に読み込み、ＣＰＵ３１が実行することも可能である。あるいは、可搬記録媒体３５として、前述した、スマートカードなどを使用し、媒体駆動装置３４で可搬記録媒体３５の情報を読み込み、暗号解読処理を施して、ユーザの認証を行うことも可能である。ネットワーク接続装置３８は、ネットワークと暗号化処理装置を接続するものであり、ネットワークを介して、暗号化すべきデータや解読すべきデータを受け取って、暗号化処理装置が処理することも可能である。あるいは、当該プログラムをネットワークを介して、外部記憶装置３３にダウンロードし、暗号化処理装置にインストールすることによって、本発明の実施形態の処理を実現することも可能である。
【００８３】
H. Mamiya, A. Miyaji, H. Morimoto, “Efficient Countermeasures against RPA, DPA and SPA”, CHES 2004, Lecture Notes in Computer Science Vol. 3156, pp. 343-356, Springer-Verlag, 2004 (文献 [MMM04]) によると、素体上の楕円曲線を用いた場合、ＳＰＡ・ＤＰＡ・ＲＰＡ・ＺＶＡに耐性を持つスカラー倍演算アルゴリズムとして指数分割法を用いた場合の１ビットあたりの計算時間は１６Ｍ＋１０Ｓと見積もられている。ここで１Ｍ、１Ｓは、素体上で乗算・平方算を１回計算するのに必要な計算時間を表す。
【００８４】
上で説明した実施形態はいずれもＳＰＡ・ＤＰＡ・ＲＰＡ・ＺＶＡに対して耐性を持つ。また素体上の楕円曲線を用いて、モンゴメリ法による実現例を使用した場合の１ビットあたりの計算時間は１３Ｍ＋４Ｓとなる。ここで１Ｍ、１Ｓは、素体上で乗算・平方算を１回計算するのに必要な計算時間を表す。１Ｍと１Ｓの比率は計算環境によって異なるが、文献 [MMM04] で仮定されている１Ｓ＝０．８Ｓという換算値を用いた場合、既存技術の計算時間は２４Ｍ、本発明の計算時間は１６．２Ｓとなり、約３０％の高速化が可能となる。
【００８５】
以上のように、本発明の暗号化処理装置は、楕円曲線暗号処理やＲＳＡ暗号処理を行なうのに有用であり、特にサイドチャネル攻撃に対して有効である。
【図面の簡単な説明】
【００８６】
【図１】楕円加算を説明するための図である。
【図２】楕円２倍算を説明するための図である。
【図３】本発明に係る楕円曲線暗号装置の要部の構成を示す図である。
【図４】本発明の一実施形態としての楕円曲線暗号装置の機能構成を示すブロック図である。
【図５】本発明の実施形態の暗号化処理装置のハードウェア環境図である。
【図１】
0004668931.tif 000002
【図２】
0004668931.tif 000003
【図３】
0004668931.tif 000004
【図４】
0004668931.tif 000005
【図５】
0004668931.tif 000006