WO2005008955A1

WO2005008955A1 - 個人鍵を用いた耐タンパ暗号処理

Info

Publication number: WO2005008955A1
Application number: PCT/JP2003/009284
Authority: WO
Inventors: Kouichi Itoh; Tetsuya Izu; Masahiko Takenaka; Naoya Torii
Original assignee: Fujitsu Ltd
Current assignee: Fujitsu Ltd
Priority date: 2003-07-22
Filing date: 2003-07-22
Publication date: 2005-01-27
Anticipated expiration: 2006-01-22
Also published as: JPWO2005008955A1; US20070177721A1; EP1648111A1; EP1648111A4; JP4632950B2; AU2003304629A1; EP1648111B1

Abstract

個人鍵を用いて楕円曲線暗号処理を行う暗号装置（１０）は、乱数に基づいて生成された楕円曲線上の点Ｒを初期点Ｖ０にセットするランダム化手段（１６）と、その楕円曲線暗号のための或るスカラー値ｄのビット・シーケンスに従って、その初期点Ｖ０と楕円曲線上の或る入力点Ａのスカラー倍との和Ｖ１＝Ｖ０＋ｄＡの演算を実行する演算手段（２０）と、その演算によって得られた和Ｖ１からその初期点Ｖ０を減算する演算Ｖ＝Ｖ１−Ｖ０を実行するランダム化解除手段（２２）と、そのランダム化解除手段によって得られた点Ｖを出力として供給する手段（２４）と、を具えている。

Description

明細誊個人鍵を用いた耐タンパ暗号処理

発明の分野

本発明は、暗号処理の分野に関し、特に、 R S Aおよび楕円曲線暗号のような公開鍵暗号のためのプロセッサにおける S P A、 D P Aおよび R P Aのような電力解析攻擊を防止する耐タンパ (tamper-proof) 暗号化ノ復号に関する。

発明の背景

例えば電子決済および日本の住民基本台帳ネットワークのようなネットワークを利用したサービスが普及しつつある。これらのサービスには情報セキュリティのために暗号が用いられる。

上述のサービスにおけるユーザ側のデバイスとして、ユーザの秘密情報を格納した I Cチップを含むスマ一トカードが広く普及すると予想される。スマート力ードは、暗号、ディジタル署名おょぴ認証の機能を有し、その秘密情報を鍵として用いる。スマートカードでは、秘密情報は I Cチップ' メモリに格納されるので、第三者による不正なアクセスに対する安全性または耐タンパ性が磁気カー- に比べて非常に高い。

図 1は、スマートカードのような暗号デバイスにおける秘密鍵を用いた暗号ィヒノ復号の構成の例を示している。図 1において、暗号デバイスは、その内部の暗化/復号ュニットにおいて周知の形態で個人鐽を用いて入力平文/暗号文メッセージを処理して出力暗号文 _/ /平文メッセージを供給する。暗号方式には一般的に公開鍵暗号方式と共通鍵暗号方式が含まれる。

公開鍵喑晉方式は、暗号化と復号に異なる鍵（キー）を用いる。典型的には、公開鍵を用いて平文 (plaintext) が暗号化され、個人または秘密鍵を用いて暗号文 (ciphertext) が復号され、それによつて暗号文が安全に送信できる。または、個人鍵を用いて平文が暗号化され、公開鍵を用いて暗号文が復号され、それによって平文を暗号化したユーザが識別される。公開鍵暗号は、送受信者間で秘密鐽を共有する必要がないが、計算量が共通鍵暗号と比べて非常に大きい。公開鍵暗号には R S Aおよび楕円曲線暗号が含まれる。 RSA暗号は、 z = a ^x (mo d n) で表される冪（べき）乗剰余演算（ modular exponentiation) に基づくものである。 RS A暗号に基づく暗号機能は、暗号化、復号、署名生成および署名確認に関係する。復号および署名生成ではユーザの秘密情報を個人鍵として用いる。べき乗剰余演算は、 v = a ^d (mo d n) を満たすは出力データ vを生成する。ここで、 aは入力データを表し、 nは剰余の法を表し、 dは個人鍵を表す。

楕円曲線暗号は、点のスカラー倍算に基づくものである。点のスカラー倍算は、スカラー値 d、および楕円曲線上の点 Aに対して、 - を満たす点を求める。楕円曲線暗号に基づく暗号機能は、 ECES暗号化 /復号、 ECDSA 署名生成 Z署名確認および ECDH秘密鍵共有に関係する。 ECES復号、 EC D S A署名生成および E C D H秘密鍵共有のための処理は、ユーザの秘密情報を個人鍵として用いる。例えば、 ECDH秘密鍵共有処理は、秘密共有値を表す点 Vを計算するために V= d Aで表される点のスカラー倍算を行う。ここで、 Aは秘密鍵を共有する公開鍵の点を表し、 dは個人鍵のスカラー値を表す。

RSA暗号における乗算剰余 c = a Xb (mo d n) 、 2乗剰余 c = a ²およびべき乗剰余 c = a^x (mo d n) は、楕円曲線暗号における点の加算 C = A + B、点の 2倍算 C = 2 Aおよび点のスカラ一倍算 C = X Aにそれぞれ対応する。

暗号解読 (分析) またはタンパ（tamper) は、暗号文のような入手可能な情報から個人鍵を含めた秘密情報を推定する。暗号解読の 1つである電力解析攻撃が、 1998年に PaulKocher (ポーノレコーチャ) によって考案された。

電力解析攻撃は、文献、 R Kocher, J. Jaffe and B. Jun "Differential Power Anaysis", Crypto'99, LNCS 1666, pp.388- 397, Springer-Verlag, 1999に記載されている。

この電力解析攻擊は、スマートカードのような暗号デバイスに含まれる暗号プロセクサに相異なる入力データを与え、例えば図 1に示されているようにオシ口スコープ等を用いてその処理中における時間に対する消費電力の変化を測定し、統計的に充分な数の消費電力変化の曲線を収集しそれを解析し、それによつて暗号プロセッサ内部の鍵情報を推定する。これは、共通鍵暗号と公開鍵暗号の双方に適用できる。

電力解析攻撃には、単純電力解析 (Simple Power Analysis) (以下、 S P A という）および電力差分攻撃（Differential Power Analysis) (以下、 D P Aという）が含まれる。 S P Aは暗号プロセッサにおける 1つの消費電力変化曲線の特徴から秘密鍵または個人鍵の推定を行う。 D P Aは相異なる多数の消費電力変化曲線の差分（以下、電力差分曲線という）を用いて解析することによって秘密鍵の推定を行う。一般的には D P Aの方が強力である。

電力解析攻撃を防止する必要性が各種国際標準に記載されている。例えば、セキユリティの国際標準 I S O I 5 4 0 8によるスマート力一ド用プロテクション 'プロファイル（p p ) では電力解析攻撃への対策が必須である。また、暗号モジュールに関する米国標準 F I P S 1 4 0 - 2には、現在は電力 ^^攻撃対策の必要性に関するコメントがあるだけであるが、将来的に電力解析攻撃対策が必須になるであろう。

R S Aと楕円曲線暗号に対する電力解析攻撃 S P Aおよび D P Aを防止するための様々な対策が開発された。しかし、 2 0 0 3年に、改善された電力解析攻撃 (Refined Power Analysis) ( R P A) 力、、 L. Goubin, "A Renned Power- Analysis Attack on Elliptic Curve Crypto-systems", PKC 2003, LNCS 2567, Springer-Verlag, 2003 によって発表された。この攻撃は、楕円曲線暗号に対する電力解析攻撃を防止する公開鍵暗号の中の一部の暗号を攻撃するのに有効である。

次に、楕円曲線暗号に用いられる用語を説明する。詳細は文献 IEEE P1363/D13 (Draft Version 13, November 12, 1999) main document, Standard Specifications for Public Key Cryptography, Mtp '·// rouper.ieee .org/ roup s/ 1363/Pl363/draft.htmlの標準を参照されたい。

次の式で表される変数 Xおよび yの関数で表される曲線が楕円曲線と呼ばれる楕円曲線（素体）： y ² - x ³ + a x + b (m o d p )

ここで、 pは素数を表し、 aおよび bは楕円曲線パラメータ（0≤a， b < p ) を表す。楕円曲線（2べき）： y²+x y = x³+a x²+b (mo d f (x) ) ここで、 f は GF (2^m) の多項式を表し、 aおよび bは楕円曲線パラメータ（ a, b, CGF (2^m) ) を表す。

楕円曲線は、主に素体（prime field) と 2べき（binary field) からなる。楕円曲線は楕円曲線パラメータ aおよび bによつて一意的に決定される。

楕円曲線上の点（elliptic point) は、楕円曲線で表される式を満たす座標 (x , y) であり、素体の場合 0≤x, yく pを満たす整数 , y) の集合であり、 2べきの場合は（X, y) EGF (2^ra) を満たす要素， y) の集合である。

無限遠点（infinite point) は、 Oと表記され、任意の点 Aに対し A + 0==0 + A = Aを満たす楕円曲線上の特殊な点である。ここで、 +は点の加算を表す。ベースポイント（base point) は、楕円曲線上の 1点であり、 Gと表記される。ベースポイントは楕円曲線暗号のユーザ間で共有され、公開鍵 Z個人鐽のペアの生成、および楕円曲線暗号を用いたその他の処理に用いられる。

2次元ベクトル（x， y) を用いた点の表現は、ァファイン座標（Affine coordinates) と呼ばれる。（x, y) = (X/Z, Y/Z) を満たす 3次元べクトル（Χ， Υ, Ζ) を用いた点の表現は、投影座標（projective coordinates ) と呼ばれる。 (X , y) = (X/Z², Y/Z³) を満たす 3次元ベクトル ( X, Y， Z) を用いた点の表現は、ヤコビアン座標 (Jacobian coordinates) と呼ばれる。 3次元ベクトル表現の使用によって、点のスカラ一倍算における除算の回数を大幅に減らし、全体の演算を高速化できる。

点 Aおよび Bに対する演算 A+Bは、点の加算（elliptic point addition) と呼ばれる。 A + B = B+Aが成立する。点 Aおよび Bに対する演算 A— Bは、点の減 (elliptic point subtraction) と呼ばれ ·ο。

点の 2倍算（elliptic point doubling) は、楕円曲線上の点 Aから C = 2 Aで表される楕円曲線上の点 Cが定義される。この演算 2 Aを点の 2倍算と呼ぶ。点のスカラー倍算（elliptic scalar multiplication) は、楕円曲線上の点 Aおょぴスカラー値 dから、 V- d Aによって定義される楕円曲線上の Vを導出する演算であり、点の加算、点の減算および 2倍算の組み合わせからなる。ベースポイント Gと、個人鍵を表すスカラー値 dとに対し、公開鍵は V= dG を満たす Vにより与えられる。公開鍵は楕円曲線上の点である。個人鍵はスカラ一値である。

次に、電力解析攻撃について説明する。

べき乗剰余または点のスカラー倍算を実現するためのアルゴリズムには、例えばバイナリ法、符号付きパイナリ法およびウィンドゥ法等が含まれる。攻撃者はスマートカードにおけるべき乗剰余または点のスカラー倍算のアルゴリズムを知つているものと仮定する。

図 2は通常のバイナリ法によるべき乗剰余のアルゴリズムを示している。与えられた基数 a、指数 dおよぴ法 nに対して、べき乗剰余値 v= a ^d (mo d n ) が求められる。図 3は、通常のバイナリ法による点のスカラー倍算のアルゴリズムを示している。与えられた点 Aおよびスカラー値 dに対して、点のスカラー倍を表す点 V= d Aが求められる。ここで、 dは mビットの 2進値を表す。 2進値 d中の i番目のビット値は d [ i ] で表される（i = 0， 1 , . . . m— 1 ) 。 2進値 d中の i番目から： j番目のビット値（ i > j >0) のストリングの値は d [ i , j ] で表される。例えば、 d= 1 9 = (1 0 0 1 1 ) ₂のとき、 d [ 4] = 1、 d [3] =0、 d [2] =0、 d [1] = 1、 d [0] = 1であり、 d [0， 0] = ( 1) ₂= 1、 d [ 1， 0] = ( 1 1) ₂= 3、 d [ 2, 0] = (O i l) ₂= 3、 d [3 , 0] = (0 0 1 1) ₂= 3 , d [4， 0] = ( 1 0 O i l ) ₂= 1 9、 d [4, 1 ] = ( 1 0 0 1 ) ₂ = 9である。 EC ADDは点の加算を表し、 E CD B Lは点の 2倍算を表す。

図 2を参照すると、ステップ 1 0 2においてワーク変数 tおよび Vがそれぞれ t = aおよび v= lと初期ィ匕される。ステップ 1 0 3〜： L 0 6は、 iに対するループ処理であり、 i =0, 1， . . . m- 1について順次、 d [ i ] =0に対してステップ 1 0 5における 2乗算が実行され、 d [ i ] - 1に対してステップ 1 04における乗算とステップ 1 0 5における 2乗算が実行される。ステップ 1 0 6の後、ワーク変数 Vの値は v = a ^{d [i}' ^0] (mo d n) で表される。

図 3 を参照すると、ステップ 2 0 2においてワーク変数 Tおよび Vが T = A および V == Oと初期化される。ステップ 20 3〜 2 06は、 iに対するループ処理であり、 i=0, 1, . . . m— 1について順次、 d [i] =0に対してステップ 205における 2倍算が実行され、 d [i] =1に対してステップ 204における点の加算（EC ADD) とステップ 205における 2倍算（ECDBL) とが実行される。ステップ 206の後、ワーク変数 Vの値は V=d [i， 0] で表される。

図 2および 3のアルゴリズムと個人鍵 dの間には、次の（COR. 1) および (COR. 2) の相関関係がある。

(COR. 1) 値 dのビット値と実行される演算の間に相関関係がある。図 3 のァノレゴリズムにおいて、 dの各ビット値に従って、 ECDBL、または ECD B Lおよび EC ADDが行われる。

(COR. 2) 値 dのビット値とワーク変数の値の間に相関関係がある。図 3 のアルゴリズムにおいて、ステップ 106の後の Vの値は V- (d [i， 0] ) A = (2¹ d [i] ) A+ (d [ i一 1， 0] ) Aで表される。

SPAは相関関係（COR. 1) に基づいて個人鍵を求める。 DP Aは相関関係（COR. 2) に基づいて個人鍵を推定する。 RPAは相関関係（COR. 1 ) および（COR. 2) の任意のいずれかに基づいて個人鍵を推定する。

SPAは、単一の電力波形を測定し、スマ一トカード內部で行われている処理を推定することによつて個人鍵を推定する。

例えば、図 3のアルゴリズムを処理するスマートカードの消費電力を測定し、図 4に例示された電力波形が得られたと仮定する。図 4のように、得られた消費電力波形 Aおよび Dが E C AD Dと E C D B Lを識別できるような形状を有するとき、相関関係 (COR. 1) に従って、電力波形 Dとその後続の波形 Aの組はビット値 1に対応し、単独の波形 Dはビット値 0に対応する。このようにして、個人鍵のビット歹 IJ "00110" が求まる。

SPAに対する対策として、個人鍵 dのビット値に関係なく一定の演算手順を繰り返すァド ·アンド'ダブル ·オールウェイズ (add-and-double-always, 常に加算と 2倍算を行う）およびモンゴメリ 'ラダー（Montgomery-Ladder) 等が知られている。

アド ·アンド 'ダブル ·オールウェイズ法は、文献、 J. Coron, "Resistance against differential power analysis for elliptic curve cryptographic cryptosystme", CHES'99, LNCS 1717, pp.292- 302, Springer-Verlag, 1999に記載されている。

モンゴメリ ·ラダー法は、文献、 R Montgomery, "Speeding the Pollard and elliptic curve methods for factorizations", Math of Comp, vol.48, pp.243-264, 1987に記載されている。

図 5は、通常のァド 'アンド ·ダブル ·オールウェイズのアルゴリズムを示している。この場合、演算の手順は、個人鍵 dの各ビット値に関係なく、 ECAD D, ECDBL, ECADD, E CDB L, . . . ， ECADD, ECDBLとなる。

DP Aは、複数の電力波形を測定して解析することによって個人鍵を推定する。次の手順 (DPA. 01) 〜（DPA. 03) は、図 3のアルゴリズムに対する DPAの例を示している。

(DPA. 01) k個のランダムな与えられた点 A₀, Aい A_0> . . , Aトに対して、各 A jの d倍算を行っている期間の消費電力が測定される。 Ajに対するスカラー倍算において測定された k個の消費電力データの集合が C (A』， t) で表される（j =0， 1, . . . k一 1) 。

(DPA. 02) 以下の手順に従って、 d [0] の値が推定され、その推定が正しいどうかが判定される。

- 推定値 d [0] が正しいと仮定する。この仮定に基づいて、 i =0についてステップ 203〜206が終了した時点における、スマートカード内部の変数 V の座標 Xのデータ値をそれぞれの A jについて予想する。例えば d [0] =1と仮定した場合、図 3のアルゴリズムに従って V = Ajと予想できる。予想の結果、 Vのデータ値の最下位ビットが 1であるとき、 C (A t) を Gユに分類し、 Vのデータ値の最下位ビットが 0であるとき、 C (A_s, t) を G。に分類する。分類に用いられる Vのデータ値は、 Xの代わりに yまたは zのデータ値であつてもよい。

― 上述の分類に基づいて、次の式で表される電力差分曲線を作成する。

Δ (t) = {G₁に属する C (A;, t) の平均 } ― {G₀に属する C (Aい t) の平均 }

一その電力差分曲線が図 6 Aに示すようなスパイクを有するときは、 d [0] の推定値が正しいと判定する。その電力差分曲線が図 6 Bに示すように平坦なときは、 d [0] の推定値が誤りであると判定する。

(DPA. 03) 手順 (DP A. 02) を、 d [1] ， d [2] , . . . d [ m— 1] に対して順に操り返し実行することによって個人鍵 dの値を求める。 d

[h] に対して手 j暖 (DPA. 02) を実行するとき、手順 (DPA. 02) における分類の基準となる Vのデータとして、 i = hについて終了した時点のデータが用いられる。 Vのデータ値の予想にあたっては、既に求められた d [0] 〜 d [h- 1] の値と今回推定した d [h] の値が用いられる。その理由は、 Vの値が、 V=2^hd [h] A+d [ - 1, 0] A、即ち既に求められた d [0] 〜d [h-1] と今回推定した d [h] によって決定される値だからである。

DP Aは、スマートカードの消費電力がデータ値の "1" の数に比例するという性質に基づいている。

DP Aに対する一般的な対策として乱数を用いた方法が知られている。その方法は、スマートカード内部で生成された乱数を用いて変数データを隠蔽またはランダム化することによって、 DP Aによるデータ値の推定を防止する。

例えば、ランダムィ匕座標と呼ばれる方法は、投影座標またはヤコビアン座標の点のデータ表現をランダム化する。この場合、通常の暗号処理において、ァファイン座標を表すワーク変数（X, y) に対して、ワーク変数が、投影座標 (r X x, r X y, r X z) に変換され、またはヤコビアン座標 ( r ² X x , r ³X y , r X z) に変換される。ここで、 rは乱数を表す。乱数 rによって全ての座標データがランダム化され、ワーク変数の値は予測不可能となり、 DP Aが防止できる。それによつてワーク変数の値はランダム化されるが、乱数 rの値に関係なくワーク変数の値はいずれも同一の点を表すので、 d [0] 〜d [m— 1] の計算後に、求めた座標をァファイン座標に逆変換することによって、通常の処理と同じ演算結果 d A」·が一意的に求められる。

次に、 RPAを説明する。 RPAは、個人鍵 dのビット値を推定し、その値に基づいて特定の入力点を選択してそれを暗号装 ίのスカラー倍算の入力として供給することによって、個人鍵 dを推定する。スカラー倍算の特定のタイミングにおけるワーク変数値が 0であれば、 RPAはビット値の推定が正しいと判定し、そうでない場合は推定が誤りであると判定する。ワーク変数値が 0であるか否かは、 S P Aにおける単一の電力波形を用いても、また DP Aにおける複数の電力波形の差分を用いても判定できる。

次の手順 (RPA. 01) 〜（RPA. 04) は、図 3のアルゴリズムに対する RP Aの例を示している。； P Aにおいて、攻撃者は、既に求められた d [0 ] , d [1] , · . . d [h- 1] に基づいて、次のビット値 d [h] を求める

(RPA. 01) 既知の値 d [0] , d [1] , . . . d [h-1] と、推定値 d [h] と力ら、 A= (d [ , 0] 一¹ (mo d φ ) ) Qを求める。ここで、 ^は位数（order) の値であり、 Qは Q= ( , 0) または（0, y) を満たす楕円曲線上の点、即ち座標 Xまたは yが 0となる座標である。

(RPA. 02) スマートカードに d Aを演算させて、消費電力波形 C (A, d) を測定する。

(RPA. 03) 消費電力波形 C (A, d) の曲線のうち、ステップ 203〜 206の i =h, + 1に対応する部分波形を観察して、ワーク変数 Vの座標 X が 0であるかどうかを判定する。 Vの座標 Xが 0力どうかの判定法については、前述の Goubinの文献を参照されたい。

RPAが可能な理由は、 d [h] の推定が正しいとき、ステップ 203〜20 6のループが i = hについて完了した後、ワーク変数 Vの座標 Xまたは yが 0となるからである。 Vの座標 Xまたは yが 0となると、この値が i = h + 1に対する演算に用いられるときに、例外的処理が発生し、この例外処理は電力波形によつて観察できる。

図 7 Aおよび 7 Bは、 RP Aにおける電力波形を例示している。

d [h] の推定が正しいときに i =hに対するループ処理の後に Vの座標値を表す波形が出現する理由は、手順 (RPA. 01) に従って Aが与えられるからである。このような Aを与えることによって、 d [h] の推定が正しいときに i =hに対するステップ 203〜206のループ処理の後の Vの値が Qに一致し、座標 xまたは yの値が 0となる。

従って、ワーク変数の座標値が攻撃者の意図したタイミングにおいて 0となることを回避するようアルゴリズムを作成することによって RP Aを防止することができる。

. 基本的にデータをランダム化する DP A対策によって RP Aを防止できるが、例外がある。例えば、 DP A対策の 1つであるランダム化座標は、 RPAに対して脆弱である。これは、 DP A対策なしの処理におけるワークデータをは, Y , Z) としたとき、ランダム化座標を用いた場合のワークデータは (r XX, r XY, r XZ) となるからである。即ち、 D P A対策なしの処理における座檩値が 0である場合、ランダム化座標における座標値も rの値に関係なく 0となる。

本発明者によって公表された、伊豆、他の文献、 "楕円曲線暗号向けサイドチャネル対策方式の比較評価" 、 2003年、暗号と情報セキュリティシンポジゥム（SC I S 2003) 、 8 D— 3には、楕円曲線暗号に対応する公開鍵暗号の電力解析攻撃の対策として、 S P Aおよび DP Aに対して最も安全な対策は、ランダム化座標 (Randomized Projective Coordinates) (RPC) 、ランダムィヒ曲線（Randomized Curve) (RC) 、指数分割法（Exponent Splitting) (E S) 、点の隠蔽（Point Blinding) (PB) の 4つの対策であることが記載されている。これらは、 DPA対策であるが、 SPA对策とともに用いることによつて DP Aと S PAの双方を防止できる。

表 1は、アド ·アンド'ダブル ·オールウェイズ法を併用した場合の、 SPA 、 DPAおよび RPAに対する安全性と、点のスカラー倍算に必要な処理量の比較を示している。表 1 公開鍵暗号の安全性と、点のスカラー倍算の処理時間の比較

ここで、 Sは電力解析攻撃に対して安全であること、 Vは電力解析攻撃に対して脆弱であることを表す。 Eは、図 5のアド'アンド ·ダブル ·オールウェイズ法による点のスカラー倍算の処理時間を表し、 Aは、点の加算、減算および 2倍算の処理量を表し、 Iは逆元計算の処理量を表している。

R PCおよび RCはその処理が高速であるが、 RP Aに対して弱い。 ESおよび P Bは R P Aに対し安全であるがその処理が遅レ、。

図 8 Aは、投影座標に基づく R PCのアルゴリズムを示している。図 8Bは、ヤコビアン座標に基づく R PCのアルゴリズムを示している。図 8Cは、アブァィン座標に基づく R Cのアルゴリズムを示している。

これらのアルゴリズムは、 ( i ) 入力点 Aの座標データのランダム化 (図 8 A のステップ 401〜 402 ；図 8 Bのステップ 501— 502 ；図 8 Cのステツプ 601〜602) 、（ i i ) アド 'アンド ·ダブル ·オールウェイズを用いたスカラー倍算 (図 8 Aのステップ 403〜408 ；図 8 Bのステップ 503〜 5 08 ；図 8 Cのステップ 603〜608) 、および ( i i i ) データのランダム化を解除して元に戻して（de-randomize) (逆ランダム化）、演算結果を出力する（図 8 Aのステップ 409〜410 ；図 8 Bのステップ 509〜510 ；図 8Cの 609〜610) の 3段階で構成される。

段階（ i) は DP A対策のための処理である。乱数 rを生成し、図 8 Aにおいては A' = (r X Av, r XA_Y， r X Α_ζ) 、図 8 Βにおいては Α， = ( X A_x, r ³XA_Y, r X A_z) 、図 8 Cにおいては A' = (r ²X A_x, r ³XA_Y) に従って座標データをランダム化し、それによつて、これらのデータが攻擊者によって推定されるのを防ぐ。ここで、 A_x， Α_γ, A_zはそれぞれ点 Aの座標 (Z ， Υ， Ζ) を表す。

段階（i i i) は、データのランダム化を解除して、通常の暗号処理と同じ処理値を出力するための処理である。図 8 Aにおいては V- (V [0] _X/V [0 ] _z， V [01ノ V [01 _z) 、図 8 Bにおいては V= (V [0] ノ (V [0 ] z) ) ², V [0] ノ (V [0] z) ³) 、図 8Cにおいては V= (V [0] _XZ r ², V [0] _YZr ³) が処理される。

し力し、これらの対策は RP Aには無効である。その理由は、段階（i) のランダム化において座標値と乱数 rの積を導入するからである。例えば、図 8じにおいて、ランダム化を行わない場合のワーク変数データを V= (V_x, V_Y) とすると、段階（i) ステップ 603〜608のワーク変数データは V' = (r ² XV_X, r ³XV_Y) で表される。即ち、ランダム化を行わない時の Vの座標 X， Yの値いずれかが 0のとき、 V' の座標 X， Yの値いずれかも乱数 rに関係なく

0となり、 RP Aが適用できる条件を満たす。図 8 Aおよび 8 Bに示した R PC および R PAについても同様である。

処理時間は、 RPCおよび RCにおいてァド ·アンド ·ダブル ·オールウェイズ演算が 1回、ランダム化の解除のための逆元演算が 1回必要であり、合計 E +

Iである。

図 9 Aは E Sのアルゴリズムを示している。図 9 Bは PBのァノレゴリズムを示している。

これらのアルゴリズムは、図 8 A〜 8 Cのァルゴリズムと同様に、 ( i ) 入力点 Aの座標データのランダム化 (図 9 Aのステップ 70；！〜 702 ；図 9 Bのステツプ 801-802) 、 ( i i ) アド 'アンド 'ダブル'オールウェイズを用いたスカラー倍算（図 9Aのステップ 703〜704 ；図 9Bのステップ 803 〜804) 、および（i i i) データのランダム化を解除して元に戻し、演算結果を出力する（図 9 Aのステップ 705〜706 ；図 9 Bの 805〜 806 ) の 3段階で構成される。図 9 Aにおいて、段階（i) ではスカラー値 dに対して、 d-di+dgを満たすランダムなスカラー値 (！ェおよび d₂が生成される。段階（ i では、前述の d およぴ(1₂に対して V₂= c^Aおよび V₂= d₂Aで表されるスカラー倍算を、図 5のアド 'アンド .ダブル ·オールウェイズ演算に従って行う。ランダムな d ^および d₂に対するスカラー倍算によってワーク変数をランダム化し、それによつて DP A対策が実現される。段階（i) および（i i) によって攻撃者の意図したタイミングでワーク変数の座標値が 0となることが防止されて、 R P A対策が実現される。段階（i i i) では、 V = V₁ + V₂=dA+ (d- r ) A=dAの演算によって、データのランダム化を解除して元に戻し、 dAを出力する。

図 9 Bにおいて、段階（i) では入力点 Aに対し、 A Aj + Asを満たすランダムな点および A₂を生成している。段階（i i) では前述の点およぴ A₂に対して = d および V₂= d A₂で表されるスカラー倍算を、図 5のァド ·アンド 'ダブル ·オールウェイズ演算に従つて行う o ランダムな点 A iおよび A ₂に対するス力ラー倍算によってワーク変数をランダム化し、それによつて DP A対策が実現される。段階（i) および（i によって攻擊者の意図したタイミングでワーク変数の座標値が 0となることが防止されて、 R P A対策が実現される。段階（ i i i) では、 V = V₁+V₂=d (Α, + Α^ =dAの演算によって、データのランダム化を解除して元に戻し、 dAを出力する。

E Sの場合、アド 'アンド 'ダブル 'オールウェイズ演算を 2回と、ランダム化の解除の際に点の加算を 1回を必要とするので、処理時間は合計で 2 E+Aである。 PBの場合、アド 'アンド 'ダブル ·オールウェイズ演算を 2回と、データのランダム化とその解除の際に点の加算または減算を 3回を必要とするので、処理時間は合計で 2 E + 3 Aである。

従って、点のスカラー倍算の処理量が少ない公知の公開鍵暗号処理法では R P Cに対して弱く、 R P Cに対して安全な公知の公開鍵暗号処理法ではス力ラ一倍算の処理量が多くなる。

発明者たちは、スカラ一倍算の処理量が少なく、力つ SPA、 DPAおよび R P Cに対して安全な公開鍵暗号の処理法を実現することの必要性を認識した。本発明の目的は、スカラー倍算の処理量が少なく、かつ S PA DP Aおよび RP Cに対して安全な公開鍵暗号の処理法を実現することである。

発明の概要

本発明の特徴によれば、個人鍵を用いて楕円曲線暗号処理を行う暗号装置は、乱数に基づいて生成された楕円曲線上の点 Rを初期点 V。にセットするランダム化手段と、その楕円曲線暗号のための或るスカラー値 dのビット ·シーケンスに従って、その初期点 V。と楕円曲線上の或る入力点 Aのスカラー倍との和ニ V。+ d Aの演算を実行する演算手段と、その演算によって得られた和からその初期点 V。を減算する演算 V = V 一 V。を実行するランダム化解除手段と、そのランダム化解除手段によって得られた点 Vを出力として供給する手段と、を具えている。

本発明の別の特徴によれば、暗号装置は、個人鍵を用いてぺき乗剰余暗号処理を行う暗号装置であって、乱数に基づいて生成された整数 rを初期値 V。にセットするランダム化手段と、そのべき乗剰余暗号のための或る値 dを表す mビット •シーケンスに従って、その初期値 V。と或る入力値 aに対するべき乗剰余演算 V^VoXlI a ~ (2 ' d [ i ] ) (mo d n) = r X a ^d (mo d n) の演算（i =0 1 . . . m— 1) を実行する演算手段と、その演算によって得られた値 V iと r (m o d n) の逆元 r— ¹ (m o d n ) との乗算剰余演算 V = V_XX r "¹ (mo d n) を実行するランダム化解除手段と、そのランダム化解除手段によって得られた値 Vを出力として供給する手段と、を具える。ここで H a；は積 a。X a , Χ. . . X a_m— を表し、 a ~ dは a ^dを表す。

本発明は、上述の暗号装置を実現するプログラムに関する。

本発明は、上述の暗号装置を実現する方法に関する。

本発明によれば、スカラー倍算の処理量が少なく、かつ S PA DPAおよぴ RPCに対して安全な公開鍵暗号の処理法を実現できる。

図面において同じ要素には同じ参照番号が付されている。

図面の簡単な説明

図 1は、ストカードのような暗号デバイスにおける秘密鍵を用いた暗晉化 /復号の構成の例を示している。図 2は、通常のバイナリ法によるべき乗剰余のアルゴリズムを示している。図 3は、通常のバイナリ法による点のスカラ一倍算のァルゴリズムを示している。

図 4は、スマートカードの消費電力を測定して得られた電力波形を示している図 5は、通常ァド ·アンド'ダブノレ ·オールウェイズのァルゴリズムを示している。

図 6 Aは、スパイクを有する、時間に対する消費電力の曲線を示している。図 6 Bは、平坦な、時間に対する電力差分曲線を示している。

図 7 Aおよび 7 Bは、 R P Aにおける電力波形を例示している。

図 8 Aは、投影座標に基づく R P Cのアルゴリズムを示している。

図 8 Bは、ヤコビアン座標に基づく R P Cのアルゴリズムを示している。図 8 Cは、ァフアイン座標に基づく R Cのァルゴリズムを示している。

図 9 Aは、 E S暗号のアルゴリズムを示している。

図 9 Bは、 P B喑号のアルゴリズムを示している。

図 1 0は、本発明による暗号処理装置の概略的構成を示している。

図 1 1は、図 1 0の暗号化装置によって実行される、本発明の電力解析攻撃対策が施された公開鍵暗号処理のためのアルゴリズムを示している。

図 1 2は、図 1 0の暗号ィ匕装置によって実行される、本発明による電力解析攻撃対策を楕円曲線暗号に適用した基本的アルゴリズムを示す。

図 1 3は、図 1 0の暗号ィ匕装置によって実行される、本発明による電力解析攻擊対策を R S A暗号に適用した基本的アルゴリズムを示す。

図 1 4〜1 6は、図 1 2におけるランダムな点 Rの生成のァルゴリズムを示している。

図 1 7は、図 1 2における投影座標における点 Rの生成のアルゴリズムを示している。

図 1 8は、図 1 2におけるヤコビアン座標における点 Rの生成のアルゴリズムを示している。

図 1 9は、図 1 2におけるワーク変数 V [ 2 ] に対する点の 2倍算の実施形態を示している。

図 20は、図 1 6、 20および 1 9のアルゴリズムを組み合わせた、図 1 2に示された本発明による基本的アルゴリズムの実施形態を示している。

好ましい実施形態の説明

図 1 0は、本発明による暗号処理装置 1 0の概略的構成を示している。暗号処理装置 1 0は、値 a、 dおよび nまたは値 Aおょぴ dを入力して供給する入力部 1 2と、乱数 Rまたは rを発生する乱数生成部 14と、乱数生成部 1 4からの乱数 Rまたは rに従ってワーク変数を V' [0] ： =R (または！:）、 V [2] -A (または a) として初期化するワーク変数初期化部 1 6と、ワーク変数 V' [0 ] 、 V [1] および V [2] を格納するメモリ 1 8と、を具えている。暗号処理装置 1 0は、さらに、値 dの各ビット値を検出しながら初期化部 1 6のワーク変数に対して公開鍵加算（PUB ADD) および公開鍵 2倍算 (PUBDBL) を繰り返し実行して、 V' [0] =cLA+Rまたは a ^dX r (mo d n) を計算するスカラー倍算処理部 20を具えている。ここで、 PUBADDは点の加算または法 nの乗算剰余を表し、 PUBDBLは点の 2倍算または法 nの 2乗剰余を表す。 PUBADDと PUBDBLの演算手順は dビット値に依存しなレヽ。喑号処理装置 1 0は、さらに、 V' [0] から V=PUB SUB (V [0] , または r ) を計算して Rまたは rの影響を取り除いた V = d Aを計算するランダム 'データ除去部を具えている。ここで、公開鍵減算 PUB SUBは点の減算または rの逆元を用いた法 nにおける乗算剰余を表す。暗号処理装置 1 0は、さらに、演算結果の値 V= d Aまたは v = a ^d (mo d n) を出力する出力部 24 を含んでいる。 Rまたは rは、暗号装置 1 0内部で生成され、外部からはァクセスできない値である。

暗号化装置 1 0は、さらに、プロセッサ 32と、 ROMのようなプログラム ' メモリ 34とを含んでいる。プロセッサ 3 2は、メモリ 34に格納されているプログラムに従ってこれらの要素 1 2〜24を制御する。代替構成として、プロセッサ 32は、要素 1 2〜 24に対応する機能を実現するメモリ 34中のプログラムを実行することによって要素 1 2〜26を実現してもよレ、。この場合、図 1 0 はフロー図として見ることができる。図 11は、図 10の暗号化装置 10によって実行される、本発明による電力解析攻撃への対策が施された公開鍵暗号処理のための基本的ァルゴリズムを示している。このァルゴリズムは楕円曲線暗号と R S A暗号の双方に適用できる。

図 11のアルゴリズムは、図 8 A〜8 Cのアルゴリズムと同様に、（i) データのランダム化 (ステップ 1004〜1006) 、 (ii) ァド ·アンド ·ダブル ♦オールウェイズを用いたスカラー倍算（ステップ 1008) 、および（iii) デ

^"タのランダム化を解除して元に戾し、演算結果 Vを出力する（ステップ 101

0) の 3段階で構成される。

図 11を参照すると、ステップ 1002において、入力部 12は、値 a、 dおよび nまたは値 Aおよび dを入力する。ステップ 1004において、生成部 14 は、ランダムなデータ Rまたは rを生成する。 Rは、楕円曲線暗号において楕円曲線上のランダムな点のデータであり、 R S Aにおいてランダムな整数値であるステップ 1006において、初期化部 16は、アド ' アンド ·ダブル ·オールウェイズ法で用いられるワーク変数を、 V， [0] =Rまたは r、 V [2] =A または aと、初期化する。

ステップ 1008において、点のスカラー倍算実行部 20は、ワーク変数 V'

[0] 、 V [0] 、 V [2] を用いてァド ·アンド 'ダブル ·オールウェイズを実行する。即ち、 i=0, 1， . . . ， m— 1に対して、楕円曲線暗号において V' [1] =ECADD (V' [0] ， V [2] ) , V [2] =ECDBL (

V [2] ) 、および V' [0] =V [d [i] ] の演算を繰り返し実行し、または R S A暗号において V， [1] =V [0] XV [2] (mo d n) 、

V [2] =V [2] ² (mo d n) 、および V' [0] =V [d [ i ] ] の演算を繰り返し実行する。個人鍵 dのビット値に関係なく、アド ·アンド ·ダブル ·オールウェイズの所定の演算パターンを繰り返すことによって S P A対策を実現する。ステップ 1004において V， [0] 二 Rまたは rとセットすることによって、ワーク変数 V' [0] および V， [1] の値がランダム化されて、 D P Aを防止できる。 V [2] の値はランダム化されない。その理由は、アド 'ァンド 'ダブル 'オールウェイズ法においては V [2] の値を利用した D P Aおよぴ SPAが不可能なので、 V [2] をランダム化する必要がないからである。 V [2] の値は、個人鍵 dのビット値と関係なく、 Aの 2倍算または 2乗算を繰り返し実行することによって求められる値なので、この値を利用して DP Aを実行することはできない。

ステップ 1010において、ランダム *データ除去部 22はランダム化されたデータを元に戻す。そのために、ステップ 1004で生成され Rに対して、楕円曲線暗号においては V = V' [0] 一 Rが計算され、； RSAにおいては V = V， [0] XR— ¹または r一¹が求められる。ステップ 1012において、出力部 2 4は演算結果 Vを出力する。

このようにして、図 1 1に示されたアルゴリズムによって S P Aおよび DP A が防止される。次に、図 11のアルゴリズムを楕円曲線暗号に適用したとき、 R P Aが防止されることを説明する。

図 12は、図 10の暗号ィ匕装置 10によって実行される、本発明による電力解析攻撃対策を楕円曲線暗号に適用した基本的アルゴリズムを示す。

図 12を参照すると、ステップ 1101において、乱数点生成部 14は楕円曲線上のランダムな点 Rを生成または選択する。初期化部 1 6は、ステップ 1 10 2において初期値として Rをワーク変数 V ' [0] にセットし、ステップ 1 10 3において初期値として Aをワーク変数 V [2] にセットする。

ステップ 1 104〜1 108を含むループは、ワーク変数 V' [0] 、 V [ 1] および V [2] に対してアド .アンド ·ダブル'オールウェイズ法による点のスカラー倍箅を実行する。このループは、図 5のステップ 303〜 307の R P A対策無しのァド 'アンド 'ダブル ·オールウェイズ法と同じ処理を行っているが、 V' [0] の初期値としてランダム点 Rがセットされることによって、 R P A対策が実現される。

そのような初期値によって、図 12のワーク変数 V' [0] および V， [1] と図 5の V [0] および V [1] の間の関係は、 V' [0] =V [0] +Rおよび V' [1] =V [1] +Rで表される。即ち、図 5で計算されるワーク変数の

V [0] および V [1] の値に対して、図 12のアルゴリズムは、 V' [0] =

V [0] +Rおよび V' [1] =V [1] +Rを求め、これらの値は Rに応じてランダムに変化する。即ち、 RPCおよび RCのように、ランダム値 Rに関係な〈V， [0] および V' [1] の座標データが 0となることはない。従って、攻擊者は意図的にワーク変数の座標データ値を 0とすることが不可能となり、 RP Aが防止される。

ステップ 1 104〜1 108のループが終了した後、ステップ 1109において出力部 24は V = V' [0] 一 Rを計算することによって、 Rによってランダム化されたデータを元に戻して、その値 Vを出力する。

このようにして、本発明によるァルゴリズムは R Ρ Αに対して安全な喑号処理を実現する。 RP A対策なしの図 5のアルゴリズムと本発明による図 12のアルゴリズムを比較すると、 RP A対策のための追加的処理はステップ 1101に示す点 Rの生成と、ステップ 1109における点 Rの減算だけである。即ち、 RP A対策に関係する速度低下は、これら 2つの処理分だけに限定されるので、図 5 の 2倍の処理時間を必要とする ESおよび PBと比較すると高速な処理が実現される。

図 13は、図 10の暗号化装置 10によって実行される、本発明による電力解析攻撃対策を R S A暗号に適用した基本的アルゴリズムを示す。

図 1 3を参照すると、ステップ 1201において、乱数生成部 14は舌し数 rを生成する。初期化部 16は、ステップ 1202において初期値として rをワーク変数 V' [0] にセットし、ステップ 1203において初期値として aをワーク変数 V [2] にセットする。

ステップ 1204〜 1208を含むループは、ワーク変数 V' [0] 、 V， [ 1] および V [2] に対してアド .アンド 'ダブル.オールウェイズ法によりべき剰余演算を実行してワーク変数を更新する。

ステップ 1204〜 1208の.ループが終了した後、ステップ 1209において出力部 24は rの逆元 r—¹ (mo d n) と V' [0] の乗算剰余を計算することによって、 rによってランダム化されたデータを元に戾して、その値 Vを出力する。

ステップ 1204〜 1209におけるアド 'アンド'ダブル ·オールウェイズ法によるループによって SPAを防ぎ、ワーク変数 V' [0] の初期値に乱数 r がセットされることによって、そのループにおけるワーク変数をランダムに変ィ匕させ DP Aを防ぐ。

処理のオーバ一^、ッドについて、図 5を RS Aに適用する場合と比較すると、 R P A対策のための追加的処理はステップ 1 201に示す追加処理は rの生成と、ステップ 1 209に示す rの逆元の乗算剰余だけである。

次に、図 1 2の楕円曲線暗号用の基本的アルゴリズムの実施形態について説明する。

図 1 2におけるステップ 1 1 0 1における点 Rの生成、ステップ 1 1 07における V [2] の 2倍算として、必要な計算量が異なる複数の実施形態が存在する図 14〜 1 8は、図 1 2におけるステップ 1 1 0 1を実現する相異なるランダムな点 Rの生成のアルゴリズムを示している。

図 14を参照すると、ステップ 1 30 1において、乱数点生成部 14は、取り得る任意の座標 Xの値をランダムに生成し、値 Xを R_xにセットする。即ち、素体の楕円曲線パラメータを用いた楕円曲線暗号の場合、 0<R_X< pを満たす整数を、 2べきの楕円曲線パラメータの場合 GF (2^m) のランダムな値を与えることによって生成する。ステップ 1 302において所与の座標 Xに対応する座標 Yを求め R_Yを生成する。ステップ 1 3 03および 1 304において、 R= (R _x, R_Y) とセットする。座標 Xから座標 Yを求めるためのアルゴリズムは、前記文献 I E EE P 1 36 3ZD 1 3に記載されている。

図 1 5を参照すると、生成部 1 4は、ステップ 140 1において乱数 sを生成し、ステップ 1402において図 5のァド'アンド 'ダブル ·オールウェイズによってベースボイント Gを s倍した s Gを Rにセットする。あるいは、図 5のァ .ルゴリズムの代わりに、図 1 2のアルゴリズムを R = 0、 d = sおよび A = Gについて実行してもよい。このように同一アルゴリズムを共用することによって、リソースの利用を効率化できる。乱数 sは任意の値であるが、それがスカラー値 dのビット長を超える場合、ステップ 1 402のスカラー倍算による計算オーバ一へッドが大きい。例えば 1 60ビットの楕円曲線暗号において s力 1 60ビットの乱数であるとき、ステップ 1 402の計算量が大きくなる。その結果、本発明によるアルゴリズム全体の計算量が図 5のアルゴリズムの概ね 2倍となつて処理速度が低下する。従って、 sは 2 0〜3 0ビットの値であることが好ましい。図 1 6は、スマートカードの初期化等において点 Rの初期値をランダムに与えた後、本発明による電力解析攻撃から保護された暗号処理が呼び出される度にその点 Rの値を更新するアルゴリズムを示している。その更新を簡単な演算で実現することによって、図 1 4および 1 5に示されたアルゴリズムと比べて、その処理時間を短くできる。

ステップ 1 5 0 1において、生成部 1 4は、通常の電力解析攻撃対策において使用される Rの値をメモリ上の特定の領域から読み込む。代替構成として、例えば図 1 4および 1 5に示した方法を用いて点 Rの初期値を与えてもよい。ステツプ 1 5 0 2において、生成部 1 4は、点 Rに対して 2倍算を行うことによってその値を更新する。ステップ 1 5 0 3において、生成部 1 4はその更新した点 Rの値を次回の処理のために格納する。

図 1 7は、図 1 2における投影座標における点 Rの生成のアルゴリズムを示している。図 1 8は、図 1 2におけるヤコビアン座標における点 Rの生成のァルゴリズムを示している。

これらのアルゴリズムにおいては、生成部 1 4は、図 1 6のアルゴリズムと同様にスマートカードが初期化されるとき等にぉレ、て点 Rの初期値をランダムに生成し、その後、本発明による暗号プログラムが呼び出される度に、生成部 1 4は点 R初期値を更新する。

図 1 6のアルゴリズムと同様に、生成部 1 4は、ステップ 1 6 0 1においてメモリ 1 8に格納されている前回の R読み込み、ステップ 1 6 0 3において更新された Rを格納する。図 1 7において、生成部 1 4は、ステップ 1 6 0 2において定数 tを座標値 R = ( _{X J} R _Y, R _z) に乗算することによって初期値 Rを更新する。図 1 8において、生成部 1 4は、ステップ 1 6 0 2において定数 t、 t ² および t ³を座標値 R ( R _x, R _Y， R _z) の各成分に乗算することによって初期値 Rを更新する。 tの値として、例えば t = 3のような小さな値を選択することによって、 Rの更新に必要な計算量を小さくできる。

図 1 9は、図 1 2におけるステップ 1 1 0 7におけるワーク変数 V [ 2 ] に対する点の 2倍算の実施形態を示している。

ステップ 1107における点の 2倍算は、同一ワーク変数 V [2] に対して繰り返し実行され、 V [2] の値はループ変数 iを用いて V [2] =2 ^{i + 1}Aと表される。ヤコビアン座標および素体の場合について、同一の点に対して繰り返し実行される 2倍算（点の 2^k倍算）によって計算を高速化する手法が、本発明者の中の 2人、武仲および伊藤によって 2000年 5月 16日付けで公開された特開 2000— 137436号公報（A) に開示されており、ここでこの文献を引用して組み込む。図 19では、その公報における図 2に示されている点の 2^k倍算の手法が用いられる。

図 1 9における iは、図 1 7におけるループ変数 iの値と同じである。このァルゴリズムは、変数 Pとしての A [2] = (X；, Yい Ζ = 2 ^; Aの入力から A [2] = (X_{i + 1}, Y_{i + 1}, Z _{i +} =2 ^{i +1} Aの出力までの演算を表している。 i =0のときは、 i f文によって i =0に対する処理に分岐することによつて、通常の素体ヤコビアン座標における 2倍算と同じ処理を行う。 i>lのときは、 i f文によって i>lに対する処理に分岐する。このとき、点の 2倍算のためのワーク変数を計算するために、 i一 1におけるワーク変数の値を再利用することによって計算量が削減される。前記文献 I EEE P 1363に記載されている標準的な点の 2倍算を用いたとき、 1回当たり 10回の乗算が必要であるが、図 19のアルゴリズムを用いたとき 1回当たり 8回の乗算のみを必要とする。即ち、図 19に示されたアルゴリズムを用いることによって、標準的な方法を用いるのと比較して点の 2倍算に必要な計算量を 2割だけ削減できる。図 20は、図 1 5 (R初期化) 、 16 (ステップ 1101、 Rの生成) および 19 (ステップ 1 106、点の 2 ^k倍算）のアルゴリズムを組み合わせた、図 1 2に示された本発明による基本的アルゴリズムの実施形態を示している。

代替構成として、図 7のステップ 1 101として図 14〜 18のいずれかと、ステップ 1 106として図 1 9および前記文献 I EEE P 1363のいずれか、の組み合わせであってもよい。

次に、図 13の R S A暗号用の基本的アルゴリズムの実施形態について説明する。 R S A暗号用の電力解析攻撃対策の場合、図 18がそのまま実施例となる。その理由は、ステップ 1201における乱数 rの生成、ステップ 1206における 2乗算の実現例には変形形態がないからである。

以上説明したように、本発明の実施形態によれば、 S PA、 DPAおよび RP Aの全ての解析に対する対策が実現でき、かつ通常安全なものとして知られていた E Sおよび P Bと比較して計算量が小さくなる。

表 2は、電力解析攻撃対策の通常の公開鍵暗号と本発明による楕円曲線暗号の比較を示している。表 3は、電力解析攻撃対策の通常の公開鍵暗号と本発明による RS A暗号の比較を示している。表 3において RPC、 RCおよび PB暗号は楕円曲線暗号に適用できないので除外されている。表 2 楕円曲線用の電力解析攻撃への対策の比較

表 3 R S A用の電力解析攻撃への対策の比較

.で、 Sは解析に対して安全であること、 Vは解析に対して脆弱であることを表す。電力解析攻擊対策なしのァド'アンド'ダブル ·オールウェイズにおいて

、スカラー算の処理時間が Eで表され、逆元計算の処理時間が Iで表され、点の加算、減算および 2倍算が Aで表されるものとする。 Aは Eに比べて無視できるほど小さい。

通常の暗号ィ匕による処理量は表 1のものである。本発明による図 20のァルゴリズムの処理量は、ステップ 1 702における点の 2倍算とステップ 171 1における点の減算以外は、図 5におけるァド 'アンド'ダブノレ 'オールウェイズと同じ演算を行うので、合計 E+ 2 Aと表される。

表 2から分かるように、 SPA、 DP Aおよび R PAの全てに対して安全な暗号は、 ES暗号、 PB暗号および本発明の暗号である。処理時間を比較すると、 Aは Eに比べて無視できるほど小さいので、本発明の暗号の処理時間は、安全な E S暗号および P B暗号の処理時間のほぼ半分である。

Aが Eと比べて無視できるほど小さいのは、アド ·アンド'ダブノレ ·オールゥエイズにおいて点の加算と 2倍算がそれぞれ m回実行され、合計 2m回実行されることから明らかである。例えば、 160ビット楕円曲線暗号において m= 16 0としたとき、 E:= 32 OAとなる。

E Sに必要な計算は、 R S Aにおける E Sの演算手順が次の通りなので、 2 E となる。

丄 = a ¹ (mod n) ,

v₂ = a^d2 (mod n) ,

v = vi V2 (mod n) = a^d (mod n)

ここで、 _{V l}および v₂の乗算剰余はべき乗剰余演算と比べて非常に小さく無視できると仮定している。本発明による図 13の処理は、ステップ 1201〜 12 08に示すァド ·アンド ·ダブノレ ·オールウェイズと、ステップ 1210における逆元 r— ¹ (mo d n) の演算で構成されるので、処理量は合計 E+ Iと表される。即ち、 E> Iに対して、本発明の方が E Sよりも高速な処理を実現できる。 Eと Iの大小関係は、処理環境によって異なるが、一般的に Eは演算ビット長の 3乗、 Iは演算ビット長の 2乗に比例するので、 E > Iという仮定は妥当である。このように、本発明は電力解析攻撃に対する安全性を損なうことなく、処理時間が小さい。

以上説明した実施形態は典型例として挙げたに過ぎず、その変形およびバリェーションは当業者にとって明らかであり、当業者であれば本発明の原理および請求の範囲に記載した発明の範囲を逸脱することなく上述の実施形態の種々の変形を行えることは明らカである。

Claims

請求の範囲

1. 個人鍵を用いて楕円曲線暗号処理を行う暗号装置であって、

乱数に基づいて生成された楕円曲線上の点 Rを初期点 V。にセットするランダム化手段と、

前記楕円曲線暗号のための或るスカラー値 dのビット ·シーケンスに従って、前記初期点 V。と楕円曲線上の或る入力点 Aのスカラー倍との和 d A の演算を実行する演算手段と、

前記演算によって得られた和 V iから前記初期点 V。を減算する演算 V = V i― V 0を実行するランダムィ匕解除手段と、

前記ランダム化解除手段によつて得られた点 Vを出力として供給する手段と、を具える、暗号装置。

2. 前記演算手段は次の演算を繰り返し実行し、

一点の加算 V [1] ： =V [0] +V [2] 、

一点の 2倍算 V [2] ： =2 V [2] 、および

一代入 V [0] ： =V [d [i] ]

ここで、 V [2] は別の変数を表し、前記入力点 Aが変数 V [2] の初期値としてセットされ、前記スカラー値 dは mビット 'シーケンスであり、 d [ i ] は、 i =0, 1, . . . m— 1について前記スカラー値 dの i番目の L SBの値を表すものである、請求項 1に記載の暗号装置。

3. 前記ランダム化手段は、前記楕円曲線上の点 Rの座標 Xを生成し、前記座標 Xに従って前記点 Rの座標 Yを生成して、前記生成された座標（X， Y) を前記点 Rとして前記初期点 V。にセットするものである、請求項 1に記載の暗号装置。

4. 前記ランダム化手段は、乱数 sを生成し、ベースポイント Gの s倍を求め、前記求められた s Gを前記点 Rとして前記初期点 V。にセットするものである、請求項 1'に記載の暗号装置。

5. 前記ランダム化手段は、前記 sGを求めるために、無限遠点 Oをワーク変数 V [0] に初期値としてセットし、前記 Gをワーク変数 V [2] に初期値としてセットし、

次の演算を繰り返し実行し、

一点の加算 V [1] ： =V [0] +V [2] 、

一点の 2倍算 V [2] ： = 2 V [2] 、および

一代入 V [0] ： =V [d [ i ] ]

ここで、前記スカラー値 dは mビット 'シーケンスであり、 d [ i] は、 i =0 ， 1, . . . m— 1について前記スカラー値 dの i番目の L S Bの値を表すものである、請求項 4に記載の暗号装置。

6. 前記ランダム化手段は、前記 s Gを求めるために、乱数 sを前記スカラー値 dにセットし、前記入力点 Aを前記ベースボイント Gにセットし、無限遠点 O を前記点 Rにセットすることによって、前記演算 V₁ = V。+ d Aを用いて s G =0+ s Gを求めるものである、請求項 4に記載の暗号装置。

7. 最初にランダムに発生された前記楕円曲線上の点 R₀が前記点 Rにセットされ、その後前記点 Rとして関数 R_n= f (R_n-₁, c) で表される前記楕円曲線上の点 R _nが用いられ、ここで R _nは n回目の楕円曲線暗号処理を表すものであり、 cは定数を表すものである、請求項 1に記載の暗号装置。

8. 前記楕円曲線上の前回の点が投影座標の点（R_x, R_Y， R_z) で表されるとき、前記楕円曲線上の今回の点 R_nが投影座標の点（c XR_x， c XR_Y ， c XR_Z) で表されるものである、請求項 7に記載の暗号装置。

9. 前記楕円曲線上の前回の点がヤコビアン座標の点（R_x, R_Y, R_z ) で表されるとき、前記楕円曲線上の今回の点 R_nがヤコビアン座標の点（c ² XR_X， c ³XR_Y, c XR₂) で表されるものである、請求項 7に記載の暗号装

1 0. 前記楕円曲線暗号処理は素体の楕円曲線パラメータに対するヤコビヤン座標を用いた演算であり、 P=V [2] = (Χ Y;, Z j =2 iAであり、 i

a Riを順に実行することによって Riを求め、

i>lについて、演算 Ri ： =R_iT_i— ₁を実行することによって Riを求め、ここで！^ は i一 1についての中間データを表し、前記求められた Riに従って、演算 Mi ：

S , ： = 4XiQい 1 : =8(3 ヽ Z _{i + 1} : =2Y_;Zい X_{i + 1} ： =M_; ²- 2 Sいおよび Y_{i +1} :

(S j—Xi) — を、この順にまたは別の順に実行して P= (X_{i + 1}, Y_{i +}い Z _{i +} = 2 ^{i + 1}Aを求め、 V [2] として出力するものである、

請求項 2に記載の暗号装置。

1 1. 個人鍵を用いてべき乗剰余暗号処理を行う暗号装置であって、

乱数に基づいて生成された整数 rを初期値 V。にセットするランダム化手段と前記べき乗剰余暗号のための或る値 dのビット ·シーケンスに従って、前記初期値 V。と或る入力値 aに対するべき乗剰余演算 Vi-VQ a ^d (mo d n) = r X a ^d (mo d n) の演算を実行する演算手段と、

前記演算によって得られた値と r (mo d n) の逆元 r一¹ (mo d n ) との乗算剰余演算 V = ViX r— ¹ (mo d n) を実行するランダム化解除手段と、

前記ランダム化解除手段によって得られた値 Vを出力として供給する手段と、を具える、暗号装置。

1 2. 前記演算手段は、次の演算を繰り返し実行するものである、

一乗算 V [1] ： =V [0] XV [2] (mo d n) 、

一 2乗算 V [2] ： =V [2] ² (mo d n) 、および

一代入 V [0] ： =V [d [i] ]

ここで、 V [2] は別の変数を表し、前記値 dは mビット 'シーケンスであり、 d [i] は、 i =0， 1， . . . m—lについて前記値 dの i番目の LSBの値を表すものである、

請求項 1 1に記載の暗号装置。

13. 情報処理装置において使用するための、個人鐽を用いて楕円曲線暗号処理を行う記憶媒体に格納されたプログラムであって、

乱数に基づレ、て生成された楕円曲線上の点 Rをランダムに発生するステップと前記点 Rを初期点 V。にセットする

前記楕円曲線暗号のための或るスカラー値 dのビット ·シーケンスに従って、前記初期点 V。と楕円曲線上の或る入力点 Aのスカラー倍との和 V = V。 + d A の演算を実行するステツプと、

前記演算によつて得られた和 V _xから前記初期点 V。を減算する演算 V = V_X -

V。を実行するステップと、

前記減算によって得られた点 Vを出力として供給するステップと、

を実行させるよう動作可能なプログラム。

14. 情報処理装置において使用するための、個人鍵を用いてべき乗剰余暗号処理を行う記憶媒体に格納されたプログラムであって、

乱数に基づいて生成された整数 rを初期値 V。にセットするステップと、前記べき乗剰余暗号のための或る値 dのビット ·シーケンスに従って、前記初期値 V。と或る入力値 aに対するべき乗剰余演算 Vi-Vo a ^d (mo d n) = r X a ^d (mo d n) の演箅を実行するステップと、

前記演算によって得られた値と r (mo d n) の逆元 r— ¹ (mo d n )

r— ¹ (mo d n) を実行するステップと、前記逆元との乗算剰余演算によって得られた値 Vを出力として供給するステツプと、

を実行させるよう動作可能なプログラム。

15. 情報処理装置において使用するための、個人鍵を用いて楕円曲線暗号処理を行う方法であって、

乱数に基づレ、て生成された楕円曲線上の点 Rをランダムに発生するステップと前記点 Rを初期点 V。にセットするステップと、

前記楕円曲線暗号のための或るスカラー値 dのビット ·シーケンスに従って、前記初期点 V。と楕円曲線上の或る入力点 Aのスカラー倍との和 V i = V。十 d A の演算を実行するステップと、

前記演算によって得られた和 V iから前記初期点 V。を減算する演算 V-Vi— V。を実行するステップと、前記減算によつて得られた点 Vを出力として供給するステツプと、

を含む方法。

1 6. 情報処理装置において使用するための、個人鍵を用いてべき乗剰余暗号処理を行う方法であって、

乱数に基づいて生成された整数 rを初期値 V。にセットするステップと、前記べき乗剰余暗号のための或る値 dのビット ·シーケンスに従って、前記初期値 V。と或る入力値 aに対するべき乗剰余演算 V Vo a ^d (mo d n) = r X a ^d (mo d n) の演算を実行するステップと、

前記演算によって得られた値ェと r (mo d n) の逆元 r— ¹ (mo d n ) との乗算剰余演算 V-VtX r— ¹ (mo d n) を実行するステップと、前記逆元との乗算剰余演算によつて得られた値 Vを出力として供給するステップと、

を含む方法。