(57)【要約】      （修正有）【課題】秘密鍵の推定を困難にし、暗号処理の安全性を高める。【解決手段】暗号装置は秘密鍵を用いて楕円曲線暗号処理を行う。その暗号装置は、楕円曲線上の点のスカラー倍の演算手段（ＥＣＤＢＬ、ＥＣＡＤＤ）と、複数のデータ格納領域を有する格納手段（Ｔ［０］〜Ｔ［２］）と、或る値（ｄ）のビット・シーケンスと乱数（ＲＮＧ）とに従って、スカラー倍の演算ごとにその演算手段に結合すべきその複数のデータ格納領域の中の１つのアドレスを決定するアドレス決定手段（ＳＥＬ）と、を具える。【選択図】図１５
2008217033.tif 000002
【特許請求の範囲】
【請求項１】
秘密鍵を用いて楕円曲線暗号処理を行う暗号装置であって、
楕円曲線上の点のスカラー倍の演算手段と、
複数のデータ格納領域を有する格納手段と、
或る値ｄのビット・シーケンスと乱数とに従って、スカラー倍の演算ごとに前記演算手段に結合すべき前記複数のデータ格納領域の中の１つのアドレスを決定するアドレス決定手段と、
を具える、暗号装置。
【請求項２】
前記アドレス決定手段は、前記或る値ｄのビット・シーケンスと前記乱数の排他的論理和に従って、前記アドレスを決定するものである、請求項１に記載の暗号装置。
【請求項３】
前記アドレス決定手段は、前記或る値ｄのビット・シーケンスと前記乱数の和に従って、前記アドレスを決定するものである、請求項１に記載の暗号装置。
【請求項４】
前記演算手段は、アド・アンド・ダブル・オールウェイズを用いたバイナリ・メソッドで前記スカラー倍算を行うものである、請求項１に記載の暗号装置。
【請求項５】
前記演算手段は、モンゴメリ・ラダー法で前記スカラー倍算を行うものである、請求項１に記載の暗号装置。
【請求項６】
前記演算手段は、ウィンドウ・メソッドで前記スカラー倍算を行うものである、請求項１に記載の暗号装置。
【請求項７】
前記演算手段は、ＲＰＣ法による変換を含む演算を行うものである、請求項１に記載の暗号装置。
【請求項８】
前記演算手段は、ＲＣ法による変換を含む演算を行うものである、請求項１に記載の暗号装置。
【請求項９】
プロセッサおよびデータ格納手段を具える暗号処理を行う装置において使用するための、秘密鍵を用いて楕円曲線暗号処理を行うプログラムであって、
楕円曲線上の点のスカラー倍を求めるステップと、
或る値ｄのビット・シーケンスと乱数とに従って、スカラー倍の演算ごとに使用される前記データ格納手段の複数のデータ格納領域の中の１つのアドレスを決定するステップと、
を前記プロセッサに実行させるよう動作可能なプログラム。
【請求項１０】
前記アドレスを決定するステップは、前記或る値ｄのビット・シーケンスと前記乱数の排他的論理和に従って、前記アドレスを決定することを含むものである、請求項９に記載のプログラム。
【請求項１１】
前記アドレスを決定するステップは、前記或る値ｄのビット・シーケンスと前記乱数の和に従って、前記アドレスを決定することを含むものである、請求項９に記載のプログラム。
【請求項１２】
前記点のスカラー倍を求めるステップは、アド・アンド・ダブル・オールウェイズを用いたバイナリ・メソッドで前記スカラー倍算を行うものである、請求項９に記載のプログラム。
【請求項１３】
前記点のスカラー倍を求めるステップは、モンゴメリ・ラダー法で前記スカラー倍算を行うものである、請求項９に記載のプログラム。
【請求項１４】
前記点のスカラー倍を求めるステップは、ウィンドウ・メソッドで前記スカラー倍算を行うものである、請求項９に記載のプログラム。
【請求項１５】
前記点のスカラー倍を求めるステップは、ＲＰＣ法による変換を含む演算を行うものである、請求項９に記載のプログラム。
【請求項１６】
前記点のスカラー倍を求めるステップは、ＲＣ法による変換を含む演算を行うものである、請求項９に記載のプログラム。
【請求項１７】
演算手段、アドレス決定手段およびデータ格納手段を具える暗号処理を行う装置において、秘密鍵を用いて楕円曲線暗号処理を行う方法であって、
前記演算手段を用いて、楕円曲線上の点のスカラー倍を求めるステップと、
前記アドレス決定手段を用いて、或る値ｄのビット・シーケンスと乱数とに従って、スカラー倍の演算ごとに使用される前記データ格納手段の複数のデータ格納領域の中の１つのアドレスを決定するステップと、
を含む方法。
【請求項１８】
前記アドレスを決定するステップは、前記或る値ｄのビット・シーケンスと前記乱数の排他的論理和に従って、前記アドレスを決定することを含むものである、請求項１７に記載の方法。
【請求項１９】
前記アドレスを決定するステップは、前記或る値ｄのビット・シーケンスと前記乱数の和に従って、前記アドレスを決定することを含むものである、請求項１７に記載の方法。
【請求項２０】
前記点のスカラー倍を求めるステップは、アド・アンド・ダブル・オールウェイズを用いたバイナリ・メソッドで前記スカラー倍算を行うものである、請求項１７に記載の方法。
【請求項２１】
前記点のスカラー倍を求めるステップは、モンゴメリ・ラダー法で前記スカラー倍算を行うものである、請求項１７に記載の方法。
【請求項２２】
前記点のスカラー倍を求めるステップは、ウィンドウ・メソッドで前記スカラー倍算を行うものである、請求項１７に記載の方法。
【請求項２３】
前記点のスカラー倍を求めるステップは、ＲＰＣ法による変換を含む演算を行うものである、請求項１７に記載の方法。
【請求項２４】
前記点のスカラー倍を求めるステップは、ＲＣ法による変換を含む演算を行うものである、請求項１７に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
発明の分野
本発明は、暗号処理の分野に関し、特に、楕円曲線暗号のためのプロセッサにおけるＳＰＡおよびＤＰＡのような電力解析攻撃を防止する耐タンパ（tamper-proof）暗号化／復号に関する。 
【背景技術】
【０００２】
発明の背景
暗号方式には一般的に公開鍵暗号方式と共通鍵暗号方式が含まれる。公開鍵暗号方式は、暗号化と復号に異なる鍵（キー）を用いる。典型的には、公開鍵を用いて平文（plaintext）が暗号化され、秘密鍵を用いて暗号文（ciphertext）が復号され、それによって暗号文が安全に送信できる。または、秘密鍵を用いて平文が暗号化され、公開鍵を用いて暗号文が復号され、それによって平文を暗号化したユーザが識別される。図１は、スマートカードのような暗号デバイスにおける秘密鍵を用いた暗号化／復号の構成の例を示している。図１において、暗号デバイスは、その内部の暗号化／復号ユニットにおいて周知の形態で秘密鍵を用いて入力平文／暗号文メッセージを処理して出力暗号文／平文メッセージを供給する。
【０００３】
公開鍵暗号の１つのタイプである楕円曲線暗号(Elliptic Curve Cryptography)のためのプロセッサにおいては、スカラー倍算が行われる。点のスカラー倍算は、スカラー値ｄ、および楕円曲線上の点Ａに対して、Ｖ＝ｄＡを満たす点Ｒを求める。例えば、楕円曲線暗号におけるDiffe-Hellman（ディッフィー・ヘルマン）鍵配送において、Ｖ＝ｄＡで表される点が秘密鍵ｄを用いてスカラー倍算で生成される。
【０００４】
バイナリ・メソッド（binary method）を用いた点のスカラー倍算は、２進値ｄについて、ＭＳＢ（最上位ビット）からＬＳＢ（最下位ビット）まで順に点の２倍算と点の加算を実行することによって、Ｖを求める。例えばｄ＝２１＝２４＋２２＋２０＝（１０１０１）２についてＶを求めるとき、最初のＭＳＢ“１”に対して初期値Ｖ＝Ｏ（無限遠点）にＡの加算を実行してＶ＝Ａを生成し、次のビット“０”に対してそのＶに２倍算を実行してＶ＝Ａ×２を生成し、次のビット“１”に対してそのＶに２倍算とＡの加算を実行してＶ＝（Ａ×２）×２＋Ａを生成し、次のビット“０”に対してそのＶに２倍算を実行してＶ＝（（Ａ×２）×２＋Ａ）×２を生成し、ＬＳＢ“１”に対してそのＶに２倍算とＡの加算を実行して、Ｖ＝（（（Ａ×２）×２＋Ａ）×２）×２＋Ａ＝（２４＋２２＋２０）Ａを生成する。
【０００５】
効率的な指数剰余演算のためのウィンドウ法（window method）が知られている。ウィンドウ法は、Alfred J. Menezes他の“HANDBOOK OF APPLIED CRYPTOGRAPHY”（CRC press）,  pp. 615, Algorithm 14.82に記載されている。
【非特許文献１】Alfred J. Menezes et al.“HANDBOOK OF APPLIED CRYPTOGRAPHY”（CRC press）,  pp. 615, Algorithm 14.82
【０００６】
図２は、ウィンドウ法を用いて楕円曲線暗号における点のスカラー倍算Ｖ＝ｄＡを求めるためのアルゴリズムを示している。ここで、ｄは２進表現でｄ＝（ｄｕ−１，ｄｕ−２，．．．ｄ０）２と表記される。そのアルゴリズムはＣ言語で記述されている。
【０００７】
図２のアルゴリズムを説明する。まず、０＜ｘ＜２ｋの全ての整数ｘに対して、Ｗ［ｘ］＝ｘＡを満たす値ＷのテーブルＷを作成する。テーブルＷの作成後、ｕビットの値ｄ＝（ｄｕ−１，ｄｕ−２，．．．ｄ０）２を分割してｍ個のｋビット・シーケンスｂｉ＝（ｄｉｋ＋ｋ−１，．．．ｄｉｋ）２（ｉ＝０，１，２，．．．）を生成する。ここで、ｍ＝ｃｅｉｌｉｎｇ（ｕ／ｋ）。そのｂｉに対する値Ｗ［ｂｉ］（＝ｂｉＡ）をテーブルＷでルックアップすることによる加算Ｖ＝Ｖ＋Ｗ［ｂｉ］と、Ｖ＝２ｋＶで表される２ｋ倍算とを、上位シーケンスｂｍ−１から下位シーケンスｂ０へ順に実行することによって、Ｖ＝ｄＡを求める。
【０００８】
暗号解読（分析）またはタンパ（tamper）は、暗号文のような入手可能な情報から秘密鍵を含めた秘密情報を推定する。暗号解読の１つである電力解析攻撃が、１９９８年にPaul Kocher（ポール  コーチャ）によって考案された。この電力解析攻撃は、スマートカードのような暗号デバイスに含まれる暗号プロセッサに相異なる入力データを与え、例えば図１に示されているようにオシロスコープ等を用いてその処理中における時間に対する消費電力の変化を測定し、統計的に充分な数の消費電力変化の曲線を収集しそれを解析し、それによって暗号プロセッサ内部の鍵情報を推定する。これは、共通鍵暗号と公開鍵暗号の双方に適用できる。
【０００９】
電力解析攻撃には、単純電力解析（以下、ＳＰＡという）（Simple Power Analysis）および電力差分攻撃（以下、ＤＰＡという）（Differential Power Analysis）が含まれる。ＳＰＡは暗号プロセッサにおける１つの消費電力変化曲線の特徴から秘密鍵の推定を行う。ＤＰＡは相異なる多数の消費電力変化曲線の差分（以下、電力差分曲線という）を用いて解析することによって秘密鍵の推定を行う。一般的にはＤＰＡの方が強力である。
【００１０】
例えばＤＥＳ（Data Encryption Standard）およびＡＥＳ（Advanced Encryption Standard）等の共通鍵暗号に対するＳＰＡおよびＤＰＡが、Paul Ｋocher, Joshua Jaffe, and Benjamin Jun，“Differential Power Analysis”in proceedings of Advances in Cryptology-CRYPTO’99，Lecture Notes in Computer Science, vol. 1666, Springer-Verlag, 1999, pp. 388-397に記載されている。
【非特許文献２】Paul Ｋocher, Joshua Jaffe, and Benjamin Jun，“Differential Power Analysis”in proceedings of Advances in Cryptology-CRYPTO’99，Lecture Notes in Computer Science, vol. 1666, Springer-Verlag, 1999, pp. 388-397
【００１１】
例えばＲＳＡ暗号および楕円曲線暗号等の公開鍵暗号に対するＳＰＡおよびＤＰＡが、例えば、Thomas S. Messerges, Ezzy A. Dabbish and Robert H. Sloan“Power Analysis Attacks of Modular Exponentiation in Smartcards”Cryptographic Hardware and Embedded Systems（CHES’99），Lecture Notes in Computer Science Vol. 1717，Springer-Verlag，pp. 144-157（以下、Messerges 99という）、およびJean-Sebastein Coron“Resistance against Differential Power Analysis for Elliptic Curve Crytosystems”Cryptographic Hardware and Embedded Systems（CHES ’99），Lecture Notes in Computer Science Vol.1717, Springer-Verlag, pp. 292-302, 1999（以下、Coron 99という）に記載されている。
【非特許文献３】Thomas S. Messerges, Ezzy A. Dabbish and Robert H. Sloan“Power Analysis Attacks of Modular Exponentiation in Smartcards”Cryptographic Hardware and Embedded Systems（CHES’99），Lecture Notes in Computer Science Vol. 1717，Springer-Verlag，pp. 144-157
【非特許文献４】Jean-Sebastein Coron“Resistance against Differential Power Analysis for Elliptic Curve Crytosystems”Cryptographic Hardware and Embedded Systems（CHES ’99），Lecture Notes in Computer Science Vol.1717, Springer-Verlag, pp. 292-302, 1999
【００１２】
楕円曲線暗号法は、楕円曲線の離散対数問題に基づくもので、N. Koblitz （“Elliptic Curve Cryptosystems”,  Mathematics of Computers, Vol. 48, pp. 203-209, 1987.)と V. Miller（“Use of elliptic curves in cryptography”, Advances in Cryptology-Proceedings of Crypto'85, Lecture Notes in Computer Science, 218 (1986), Springer-Verlag, pp 417-426）により提案された。
【非特許文献５】N. Koblitz （“Elliptic Curve Cryptosystems”,  Mathematics of Computers, Vol. 48, pp. 203-209, 1987.)
【非特許文献６】V. Miller（“Use of elliptic curves in cryptography”, Advances in Cryptology-Proceedings of Crypto'85, Lecture Notes in Computer Science, 218 (1986), Springer-Verlag, pp 417-426）
【００１３】
楕円曲線暗号は、楕円曲線上の点のスカラー倍算に基づく演算である。例えば、公開鍵点Ｐは、公開されたベースポイントと呼ばれる楕円曲線上の点Ｇに対して、スカラー値である秘密鍵ｄを用いた楕円曲線上の点のスカラー倍算Ｐ＝ｄＧで計算された楕円曲線上の点である。また、楕円曲線上のDiffie-Helman鍵共有を用いたＡとＢの間での鍵共有では、Ａの秘密鍵と公開鍵の対をｄＡ，ＰＡとし、Ｂの秘密鍵と公開鍵の対をｄＢ，ＰＢとして、Ｘ＝ｄＡＰＢ＝ｄＢＰＡの関係を利用する。楕円曲線上における点のスカラー倍算は、「点の加算（ＥＣＡＤＤ）」と「点の２倍算（ＥＣＤＢＬ）」の繰り返しからなる。スカラー倍算Ｒ＝ｄＱの最も単純な実現法に次の基本的アルゴリズムAlgorithm 1およびAlgorithm 2にそれぞれ示されたバイナリ・メソッド（ＭＳＢ）およびバイナリ・メソッド（ＬＳＢ）がある。以下の記載において、特に断らない限り、小文字（ｄ等）をスカラー値とし、大文字（Ｒ、Ｑ等）を楕円曲線上の点を表すものとする。
【００１４】
〈Algorithm1: Binary Method (MSB)〉
【数１】
2008217033.tif 000003
【００１５】
ここで、Ｔは一時的変数、ｄはｎビットのスカラー値で、ｄｉはｄのｉ番目のＬＳＢ（最下位ビット）（下位ｉ番目のビット）の値である。
【００１６】
〈Algorithm2: Binary Method (LSB)〉
【数２】
2008217033.tif 000004
【００１７】
ここで、レジスタＴ［０］およびＴ［１］は一時的変数であり、ｄはｎビットのスカラー値であり、ｄｉはｄのｉ番目のＬＳＢの値である。
【００１８】
点のスカラー倍算にAlgorithm 1およびAlgorithm 2を使用したとき、＊で示された演算はｄ中のビット値に応じて実行されたりされなかったりする。ＳＰＡは、この性質を利用して秘密鍵ｄを解析する。多くの実験からＥＣＤＢＬ演算とＥＣＡＤＤ演算の電力波形は、特徴的で容易に区別可能であることが知られている。従って、プロセッサにおけるAlgorithm 1およびAlgorithm 2の演算において発生する電力波形を測定することによって、その波形からＥＣＤＢＬとＥＣＡＤＤの演算の順序と回数が変化するので、秘密鍵ｄを解析して求めることができる。
【００１９】
このＳＰＡへの対策として、アド・アンド・ダブル・オールウェイズ（add-and-double-always、常に加算と２倍算を行う）と呼ばれる方法がCoron 99で提案されている。この方法は、常にＥＣＡＤＤ演算とＥＣＤＢＬ演算が交互に行われるので、ＳＰＡに対して安全である。次に、Algorithm 1およびAlgorithm 2に対してアド・アンド・ダブル・オールウェイズを施したものをAlgorithm 3およびAlgorithm 4として示す。
【００２０】
〈Algorithm3: Binary Method (MSB, add-and-double-always)〉
【数３】
2008217033.tif 000005
【００２１】
ここで、レジスタＴ［０］およびＴ［１］は一時的変数であり、ｄはｎビットのスカラー値であり、ｄｉはｄのｉ番目のＬＳＢの値である。
【００２２】
〈Algorithm4: Binary Method (LSB, add-and-double-always)〉
【数４】
2008217033.tif 000006
【００２３】
ここで、レジスタＴ［０］、Ｔ［１］およびＴ［２］は一時的変数であり、ｄはｎビットのスカラー値であり、ｄｉはdのｉ番目のＬＳＢの値である。
【００２４】
Algorithm 3およびAlgorithm 4を用いてＳＰＡを防止することができる。しかし、Coron 99には、これらのアルゴリズムに対するＤＰＡについても述べられており、Algorithm 3およびAlgorithm 4ではＤＰＡで秘密鍵を解析して求めることができることが示されている。さらに、Coron 99には、ランダム化射影座標Randomized Projective Coordinates（ＲＰＣ）と呼ばれる、乱数を使用した楕円曲線上の点の表現を導入することによって、Algorithm 3およびAlgorithm 4に対するＤＰＡへの対策が提案されている。Algorithm 3およびAlgorithm 4に対してＲＰＣを施したものをAlgorithm 5およびAlgorithm 6として示す。ＲＰＣで表現された楕円曲線上の点はダッシュ（prime）（'）付きの変数で示されている。
【００２５】
〈Algorithm5: Binary Method (MSB, add-and-double-always, RPC)〉
【数５】
2008217033.tif 000007
【００２６】
ここで、Ｔ’［０］、Ｔ’［１］およびＴ’［２］は一時的変数であり、ｄはｎビットのスカラー値であり、ｄｉはｄ中のｉ番目のＬＳＢである。“←”はＲＰＣ表現からの逆変換を示している。
【００２７】
図３は、図１に示されているような暗号化／復号ユニットまたはプロセッサによって実行されるAlgorithm 5のフロー図を示している。図４は、Algorithm 5を実装したブロック図を示している。
【００２８】
図３を参照すると、ステップ３０２において、プロセッサはＲＰＣ変換した点Ｑの座標の値をレジスタＴ［２］に代入する。ステップ３０４において、プロセッサはレジスタＴ［２］の値をレジスタＴ［０］に代入する。ステップ３０６は変数ｉ＝（ｎ−１），（ｎ−２），．．．０に対するループ処理である。ステップ３０６中のステップ３０８において、プロセッサはレジスタＴ［０］の値をＥＣＤＢＬ演算（点の２倍算）してその２倍値をレジスタＴ［０］に代入する。ステップ３１０において、プロセッサはレジスタＴ［０］とレジスタＴ［２］の値をＥＣＡＤＤ演算（点の加算）してその加算値をレジスタＴ［１］に代入する。ステップ３１２において、プロセッサは鍵のｉ番目のビットの値ｄｉの値に従ってレジスタＴ［ｄｉ］の値をレジスタＴ［０］に代入する。ステップ３１２はアドレス・ビットＤＰＡの標的になる。ステップ３１４において、プロセッサはｉ＝ｉ−１とセットする。その後、手順はステップ３０８に戻る。ｉ＝（ｎ−１），（ｎ−２），．．．０についてステップ３０６を実行した後、ステップ３１６において、プロセッサはレジスタＴ［０］の値をＲＰＣ逆変換して出力する。
【００２９】
〈Algorithm6: Binary Method (LSB, add-and-double-always, RPC)〉
【数６】
2008217033.tif 000008
【００３０】
ここで、Ｔ’［０］、Ｔ’［１］およびＴ’［２］は一時的変数であり、ｄはｎビットのスカラー値であり、ｄｉはｄ中のｉ番目のＬＳＢである。“←”はＲＰＣ表現からの逆変換を表している。
【００３１】
図５は、図１に示されているような暗号化／復号ユニットまたはプロセッサによって実行されるAlgorithm 6のフロー図を示している。図６は、Algorithm 6を実装したブロック図を示している。
【００３２】
図５を参照すると、ステップ５０２において、プロセッサは０点の座標の値をレジスタＴ［０］に代入する。ステップ５０４において、プロセッサはＲＰＣ変換した点Ｑ座標値をレジスタＴ［２］に代入する。ステップ５０６は変数ｉ＝０，１，．．．（ｎ−１）に対するループ処理である。ステップ５０６中のステップ５０８において、プロセッサはレジスタＴ［０］とＴ［２］の値をＥＣＡＤＤ演算してその加算値をレジスタＴ［１］に代入する。ステップ５１０において、プロセッサはレジスタＴ［２］の値をＥＣＤＢＬ演算してその２倍値をレジスタＴ［２］に代入する。ステップ５１２において、プロセッサは鍵のｉ番目のＬＳＢの値ｄｉの値に従ってレジスタＴ［ｄｉ］の値をレジスタＴ［０］に代入する。ステップ５１２はアドレス・ビットＤＰＡの標的になる。ステップ５１４において、プロセッサはｉ＝ｉ＋１とセットする。その後、手順はステップ５０８に戻る。ｉ＝０，１，．．．（ｎ−１）についてステップ５０６を実行した後、ステップ５１６において、プロセッサはレジスタＴ［０］の値をＲＰＣ逆変換して出力する。
【００３３】
Algorithm 5およびAlgorithm 6を用いて、ＳＰＡおよびＤＰＡを防止することができることが、Coron 99に述べられている。同様の効果をもつ方式としては、ＳＰＡを防止するモンゴメリ・ラダー（Montgomery-Ladder）とＲＰＣの双方を用いる方法が、T. Izu, and T. Takagi, "A Fast Parallel Elliptic Curve Multiplication Resistant against Side Channel Attacks'', PKC 2002, LNCS 2274, pp.280-296, Springer-Verlag, 2002. (Izu-Takagi)において提案されている。これは、アド・アンド・ダブル・オールウェイズを用いたバイナリ・メソッド（Algorithm 3およびAlgorithm 4）の代わりにＳＰＡ対策を施したモンゴメリ・ラダーと呼ばれるスカラー倍算を用いるのが特徴である。モンゴメリ・ラダーでは、スカラー倍算Ｒ＝ｄＱにおいて、常にＥＣＡＤＤ演算とＥＣＤＢＬ演算を行うことにより、差が１Ｑとなるような２点の計算を行う。ＳＰＡ対策を施したモンゴメリ・ラダーとＲＰＣを使用したスカラー倍算をAlgorithm7として示す。
【非特許文献７】Izu, and T. Takagi, "A Fast Parallel Elliptic Curve Multiplication Resistant against Side Channel Attacks'', PKC 2002, LNCS 2274, pp.280-296, Springer-Verlag, 2002
【００３４】
〈Algorithm7: Montgomery-Ladder (SPA-countermeasure, RPC)〉
【数７】
2008217033.tif 000009
【００３５】
ここで、Ｔ’［０］、Ｔ’［１］およびＴ’［２］は一時的変数であり、ｄはｎビットのスカラー値であり、ｄｉはｄ中のｉ番目のＬＳＢである。“←”はＲＰＣ表現からの逆変換を示している。
【００３６】
図７は、図１に示されているような暗号化／復号ユニットまたはプロセッサによって実行されるAlgorithm 7のフロー図を示している。図８は、Algorithm 7を実装したブロック図を示している。
【００３７】
図７を参照すると、ステップ７０２において、プロセッサはＲＰＣ変換した点Ｑの座標の値をレジスタＴ［０］に代入する。ステップ７０４において、プロセッサは、レジスタＴ［０］の値をＥＣＤＢＬ演算してその２倍値をレジスタＴ［１］に代入する。ステップ７０６は変数ｉ＝（ｎ−２），（ｎ−１）．．．０に対するループ処理である。ステップ７０６中のステップ７０８において、プロセッサは鍵のｉ番目のＬＳＢの値ｄｉに従ってレジスタＴ［ｄｉ］の値をＥＣＤＢＬ演算してその２倍値をレジスタＴ［２］に代入する。ステップ７１０において、プロセッサはレジスタＴ［０］とＴ［１］の値をＥＣＡＤＤ演算してレジスタＴ［１］に代入する。ステップ７１２において、プロセッサは鍵のｉ番目のＬＳＢの値ｄｉに従ってレジスタＴ［２−ｄｉ］の値をレジスタＴ［０］に代入する。ステップ７１４において、プロセッサは鍵のｉ番目のＬＳＢの値ｄｉに従ってレジスタＴ［１＋ｄｉ］の値をレジスタＴ［１］に代入する。ステップ７０８、７１２および７１４はアドレス・ビットＤＰＡの標的になる。ステップ７１６において、プロセッサはｉ＝ｉ−１とセットする。その後、手順はステップ７０８に戻る。ｉ＝（ｎ−２），（ｎ−１）．．．０についてステップ７０６を実行した後、ステップ７１８において、プロセッサはレジスタＴ［０］の値をＲＰＣ逆変換して出力する。
【００３８】
ＲＰＣと同様の効果を持つ方式としてM. Joye, and C. Tymen, “Protections against differential analysis for elliptic curve cryptography”, CHES 2001, LNCS 2162, pp. 377-390, Springer-Verlag, 2001.（ＪＴ０１）において提案されたランダム化曲線Randomized Curve（ＲＣ）法がある。ＲＣは、ＲＰＣと同様に乱数を用いた点の表現を用いることによるＤＰＡ対策である。ＲＣの適用方法はＲＰＣと同じである。アルゴリズムAlgorithm 5〜Algorithm 7についてＲＰＣの代わりにＲＣを用いたものを、“’”を付加してAlgorithm 5’〜Algorithm 7’として示す。なお、ＲＣで表現された楕円曲線上の点は（”）付の変数で表す。
【非特許文献８】M. Joye, and C. Tymen, “Protections against differential analysis for elliptic curve cryptography”, CHES 2001, LNCS 2162, pp. 377-390, Springer-Verlag, 2001.
【００３９】
〈Algorithm5’: Binary Method (MSB, add-and-double-always, RC)〉
【数８】
2008217033.tif 000010
【００４０】
ここで、Ｔ”［０］、Ｔ”［１］およびＴ”［２］は一時的変数であり、ｄはｎビットのスカラー値であり、ｄｉはｄ中のｉ番目のＬＳＢである。“←”はＲＣ表現からの逆変換を表している。
【００４１】
図４は、Algorithm 5’のブロック図をも示している。
【００４２】
〈Algorithm6’: Binary Method (LSB, add-and-double-always, RC)〉
【数９】
2008217033.tif 000011
【００４３】
ここで、Ｔ”［０］、Ｔ”［１］およびＴ”［２］は一時的変数であり、ｄはｎビットのスカラー値であり、ｄｉはｄ中のｉ番目のＬＳＢである。"←"はＲＣ表現からの逆変換を示している。
【００４４】
図６は、Algorithm 6’を実装したブロック図をも示している。
【００４５】
〈Algorithm7’: Montgomery-Ladder (SPA-countermeasure, RC)〉
【数１０】
2008217033.tif 000012
【００４６】
ここで、Ｔ”［０］、Ｔ”［１］およびＴ”［２］は一時的変数であり、ｄはｎビットのスカラー値であり、ｄｉはｄ中のｉ番目のＬＳＢである。“←”はＲＣ表現からの逆変換を示している。
【００４７】
図８は、Algorithm 7’を実装したブロック図をも示している。
【００４８】
前述のように、スカラー倍算Ｒ＝ｄＱの実現法にはAlgorithm 1およびAlgorithm 2以外にウィンドウ・メソッドと呼ばれる方法も存在する。例えば４ビットのウィンドウ・メソッドは、初期処理としてＱの０〜１５倍を計算し、その結果をテーブルとして持っておき、秘密鍵を４ビット・ウィンドウ単位で処理する。次のAlgorithm 8は４ビットのウィンドウ・メソッドの最も基本的なアルゴリズムである。
【００４９】
〈Algorithm8: Window Method (4-bits)〉
【数１１】
2008217033.tif 000013
【００５０】
ここで、ｄはｎビットのスカラー値であり、説明を簡単にするために、nは４の倍数と仮定する。また、ｄｉ，ｉ−３は、ｄ中のｉビット目から（ｉ−３）ビット目までの４ビットの値とする。Ｗ［ｉ］はウィンドウ・メソッドで使用されるテーブルである。
【００５１】
点のスカラー倍算にAlgorithm 8が使用される場合、ｄのビット値に応じて行われたり行われなかったりするような演算は無い。従って、ウィンドウ・メソッドは、バイナリ・メソッドとは異なり、一般にＳＰＡに対して安全であるといわれている。しかし、ウィンドウ・メソッドは、バイナリ・メソッドと同様にＤＰＡに対して安全でなく、Coron 99の手法で解析可能であるが、バイナリ・メソッドと同様にウィンドウ・メソッドのＤＰＡ対策もＲＰＣやＲＣが有効であることが知られている。次のAlgorithm 9およびAlgorithm 9'は、Algorithm 8に対してＲＰＣおよびＲＣを施したものである。
【００５２】
〈Algorithm9: Window Method (4-bit, RPC)〉
【数１２】
2008217033.tif 000014
【００５３】
ここで、ｄはｎビットのスカラー値であり、説明を簡単にするために、ｎは４の倍数と仮定する。また、ｄｉ，ｉ−３は、ｄ中のｉビット目から（ｉ−３）ビット目までの４ビットの値とする。Ｒ’、Ｑ’、Ｔ’［０］およびＴ’［１］は一時的変数であり、Ｗ’［ｉ］はウィンドウ・メソッドで使用されるテーブルであり、"←"はＲＰＣ表現からの逆変換を示している。
【００５４】
〈Algorithm9': Window Method (4-bit, RC)〉
【数１３】
2008217033.tif 000015
【００５５】
ここで、ｄはｎビットのスカラー値であり、説明を簡単にするために、ｎは４の倍数と仮定する。また、ｄｉ，ｉ−３は、ｄ中のｉビット目から（ｉ−３）ビット目までの４ビットの値とする。Ｒ”、Ｑ”、Ｔ”［０］およびＴ［１］は一時的変数であり、Ｗ”［ｉ］はウィンドウ・メソッドで使用されるテーブルであり、“←”はＲＣ表現からの逆変換を示している。
【００５６】
図９および１０は、図１に示されているような暗号化／復号ユニットまたはプロセッサによって実行されるAlgorithm 9およびAlgorithm 9’のフロー図を示している。図１１および１２は、Algorithm 9およびAlgorithm 9’を実装したブロック図を示している。
【００５７】
図９および１０を参照すると、ステップ９０２において、プロセッサは０点の座標値をテーブルＷ［０］に代入する。ステップ９０４において、プロセッサはＲＰＣ変換した点Ｑの座標値をテーブルＷ［１］に代入する。ステップ９０６において、プロセッサはテーブルＷ［１］の値をＥＣＤＢＬ演算してテーブルＷ［２］に代入する。ステップ９０８は変数ｉ＝３，４，．．．１５に対するループ処理である。ステップ９１０において、プロセッサはテーブルＷ［ｉ−１］とＷ［１］の値をＥＣＡＤＤ演算してＷ［ｉ］に代入する。ステップ９１２において、プロセッサはｉ＝ｉ＋１とセットする。ステップ９１４において、プロセッサは、鍵のｎ−１，ｎ−２，．．．ｎ−４ビット目の値ｄｎ−１，ｎ−４に従ってテーブルＷ［ｄｎ−１，ｎ−４］の値をＲに代入する。
【００５８】
ステップ９１６は変数ｉ＝（ｎ−５），（ｎ−６），．．．０に対するループ処理である。ステップ９１６中のステップ９１８は４回反復ループ処理である。ステップ９２０において、プロセッサはレジスタＲの値をＥＣＤＢＬ演算してＲに代入する。ステップ９２０は４回繰り返される。ステップ９２２において、プロセッサは鍵のｉ〜（ｉ−３）ビット目の値ｄｉ，ｉ−３に従ってテーブルＷ［ｄｉ，ｉ−３］の値とレジスタＲの値をＥＣＡＤＤ演算してその加算値をレジスタＲに代入する。ステップ９２２はアドレス・ビットＤＰＡの標的になる。ステップ９２４において、プロセッサはｉ＝ｉ−４とセットする。その後、手順はステップ９１８に戻る。ｉ＝（ｎ−５），（ｎ−６），．．．０についてステップ９２４を実行した後、ステップ９２６において、プロセッサはレジスタＲの値をＲＰＣ逆変換して出力する。
【００５９】
従来、Algorithm 5〜Algorithm 7およびAlgorithm 5’〜Algorithm 7’、 Algorithm 9およびAlgorithm 9'を用いれば、ＳＰＡおよびＤＰＡに対して安全であると考えられていた。しかし、K. Itoh, T. Izu, and M. Takenaka “Address-bit Differential Power Analysis of Cryptographic Schemes OK-ECDH and OK-ECDSA”, Cryptographic Hardware and Embedded Systems (CHES2002), Pre-proceeding, pp.129-143 (以下、ＩＩＴ０２という) でAlgorithm 7を解析して求める手法が発表された。通常のＤＰＡ（データビットＤＰＡ(data-bit DPA)）は、データの変化がもたらす消費電力に注目するのに対して、このアドレス・ビットＤＰＡ（address-bit DPA）は、アドレスの変化がもたらす消費電力に注目した解析手法である。
【非特許文献９】K. Itoh, T. Izu, and M. Takenaka “Address-bit Differential Power Analysis of Cryptographic Schemes OK-ECDH and OK-ECDSA”, Cryptographic Hardware and Embedded Systems (CHES2002), Pre-proceeding, pp.129-143
【００６０】
例えば、Algorithm7において、＊の演算ｄでは、ｄｉの値に応じて、Ｔ’［０］が使用されるかまたはＴ’［１］が使用されるかが決定される。従って、ＥＣＤＢＬ演算で使用されるデータが格納されているアドレスはｄｉと相関関係を有する。同様のことが＃で示された演算においても生じている。アドレス・ビットＤＰＡでは、その関係を利用して秘密鍵情報ｄを解析可能としている。
【００６１】
文献ＩＩＴ０２では、モンゴメリ・ラダー（Algorithm7）に対して、アドレス・ビットＤＰＡを行っているが、同様の解析は、Algorithm 5、 Algorithm 6およびAlgorithm 5’〜Algorithm 7’に対しても適用可能である。Algorithm 9および Algorithm 9' でも＊で示された演算において、秘密鍵情報ｄの値と使用するテーブルとが強い相関関係を有するので、同様の攻撃が可能であると考えられる。そのためアドレス・ビットＤＰＡを用いれば、Algorithm 5〜7およびAlgorithm 5’〜Algorithm 7’、Algorithm 9〜Algorithm 9'はＤＰＡに対して安全であるとはいえない。
【００６２】
ＩＩＴ０２には、アドレス・ビットＤＰＡへの対策について述べられている。ＩＩＴ０２で述べられているのは、Algorithm 5〜Algorithm 7に対してCoron 99やMessages 99で提案されているエクスポーネント・ブラインディング（exponent-blinding）、C. Clavier, and M. Joye, "Universal exponentiation algorithm - A first step towards provable SPA-resistance -", Cryptographic Hardware and Embedded Systems (CHES 2001), Lecture Notes in Computer Science vol. 2162, Springer-Verlag, pp.300-308（以下、ＣＪ０１という）において提案されているエクスポーネント・スプリッティング（exponent-splitting）、.J. Yajima, K. Itoh, M. Takenaka, and N, Torii “DPA countermeasure by improving the window method”, Cryptographic Hardware and Embedded Systems (CHES2002), Pre-proceeding, pp.304-319 (以下、ＹＩＴＴ０２という）において提案されているオーバラップ・ウィンドウ法（overlapped window method）等のスカラー値をランダムに変化させる手法を適用することである。
【非特許文献１０】C. Clavier, and M. Joye, "Universal exponentiation algorithm - A first step towards provable SPA-resistance -", Cryptographic Hardware and Embedded Systems (CHES 2001), Lecture Notes in Computer Science vol. 2162, Springer-Verlag, pp.300-308
【非特許文献１１】J. Yajima, K. Itoh, M. Takenaka, and N, Torii “DPA countermeasure by improving the window method”, Cryptographic Hardware and Embedded Systems (CHES 2002), Pre-proceeding, pp.304-319
【発明の開示】
【００６３】
しかし、これらの手法は、その手法単独でＳＰＡ対策、データ・ビットＤＰＡ対策およびアドレス・ビットＤＰＡ対策であるので、既にＳＰＡ対策とデータ・ビットＤＰＡ対策済みのAlgorithm 5〜Algorithm 7に適用するには無駄が多い。特にこれらの手法を適用すると、楕円曲線上の点の加算および２倍算を、適用前と比較して余分に処理しなければならず、処理オーバーヘッドが大きくなる欠点がある。
【００６４】
発明者たちは、アドレス・ビットＤＰＡに対して安全な耐タンパ性の点のスカラー倍算を実現することの必要性（ニーズ）を認識した。
【００６５】
本発明の１つの目的は、秘密鍵の推定を困難にし、暗号処理の安全性を高めることである。
【００６６】
本発明の別の目的は、効率的な耐タンパ性の点のスカラー倍算を実現することである。
【００６７】
本発明のさらに別の目的は、アドレス・ビットＤＰＡに対して効率的で安全な耐タンパ性の点のスカラー倍算を実現することである。
【００６８】
発明の概要
本発明の特徴によれば、暗号装置は秘密鍵を用いて楕円曲線暗号処理を行う。その暗号装置は、楕円曲線上の点のスカラー倍の演算手段と、複数のデータ格納領域を有する格納手段と、或る値のビット・シーケンスと乱数とに従って、スカラー倍の演算ごとにその演算手段に結合すべきその複数のデータ格納領域の中の１つのアドレスを決定するアドレス決定手段と、を具えている。
【００６９】
本発明の別の特徴によれば、プロセッサおよびデータ格納手段を具える暗号処理を行う装置において使用するための、秘密鍵を用いて楕円曲線暗号処理を行うプログラム（これは記憶媒体に格納されていてもよい）は、楕円曲線上の点のスカラー倍を求めるステップと、或る値ｄのビット・シーケンスと乱数とに従って、スカラー倍の演算ごとに使用される前記データ格納手段の複数のデータ格納領域の中の１つのアドレスを決定するステップと、を前記プロセッサに実行させるよう動作可能である。
【００７０】
本発明のさらに別の特徴によれば、演算手段、アドレス決定手段およびデータ格納手段を具える暗号処理を行う装置において、秘密鍵を用いて楕円曲線暗号処理を行う方法は、前記演算手段を用いて、楕円曲線上の点のスカラー倍を求めるステップと、前記アドレス決定手段を用いて、或る値ｄのビット・シーケンスと乱数とに従って、スカラー倍の演算ごとに使用される前記データ格納手段の複数のデータ格納領域の中の１つのアドレスを決定するステップと、を含んでいる。
【００７１】
本発明によれば、秘密鍵の推定を困難にし、暗号処理の安全性を高めることができ、効率的な耐タンパ性の点のスカラー倍算を実現できる。
【００７２】
全ての図面を通して、同じ参照番号は同じ要素を示している。
【発明を実施するための最良の形態】
【００７３】
前述のAlgorithm 7において＊で示された演算では、変数レジスタＴ’［ｘ］の格納アドレスが秘密鍵ｄｉに依存して変化することが問題である。即ち、ｄｉ＝０に対してレジスタＴ’［０］が、ｄｉ＝１に対してレジスタＴ’［１］がそれぞれ使用されるので、アドレス・ビットＤＰＡで鍵を解析して求めることができる。従って、ｄｉの値と使用される変数Ｔ’［０］およびＴ’［１］がランダムに変化すればアドレス・ビットＤＰＡで解析できなくなる。＃で示された演算についても、同様である。
【００７４】
図１３Ａおよび１３Ｂは、本発明の原理を説明するのに役立つ。入力値が、鍵のビット・シーケンスに従って制御されるスイッチを介して２つのレジスタ１および２に供給されて格納される。図１３Ａに示されているように、通常は、鍵のビット・シーケンスに従って、値を格納すべきレジスタの順序が入れ替わったり、使用するレジスタが決定されるのを防止するために、本発明によれば、図１３Ｂに示されているように、演算すべき値を格納するレジスタを鍵の値だけで決定せずに、鍵と乱数のＸＯＲ（排他的論理和）をとることによってアドレス・ビットＤＰＡに対して高い耐性を有する暗号処理を実現する。
【００７５】
次に、本発明の実施形態による、Algorithm 7 とAlgorithm 7’において＊と＃で示された演算に乱数を導入したアルゴリズムを次のAlgorithm 10 およびAlgorithm 10’として示す。本発明による変数をランダムに決定する方法を、ランダマイズド・アドレシング（Randomized Addressing（ＲＡ）、乱数アドレス制御）と呼ぶ。
【００７６】
〈Algorithm10: Montgomery-Ladder (SPA-countermeasure, RPC, RA)〉
【数１４】
2008217033.tif 000016
【００７７】
ここで、Ｔ’［０］、Ｔ’［１］およびＴ’［２］は一時的変数、ｄはｎビットのスカラー値で、ｄｉはｄのｉ番目のＬＳＢの値を表す。ｒはｎビットの乱数を表し、ｒｉはｒのｉ番目のＬＳＢの値である。“←”はＲＰＣ表現からの逆変換を示している。
【００７８】
〈Algorithm10’: Montgomery-Ladder (SPA-countermeasure, RC, RA)〉
【数１５】
2008217033.tif 000017
【００７９】
ここで、Ｔ”［０］、Ｔ ”［１］およびＴ”［２］は一時的変数であり、ｄはｎビットのスカラー値であり、ｄｉはｄのｉ番目のＬＳＢ（最下位ビット）の値である。ｒはｎビットの乱数で、ｒｉはｒのｉ番目のＬＳＢの値とする。また、“←”はＲＣ表現からの逆変換を表す。
【００８０】
Algorithm 10およびAlgorithm 10’において、＊の部分はインデックスが秘密鍵ｄと乱数ｒのＸＯＲなので、変数レジスタＴ’［０］とＴ’［１］のどちらが使用されるかは秘密鍵ｄに無関係に決定される。同様に、＃で示された演算は、インデックスそのものが秘密鍵ｄと無関係である。従って、Algorithm10およびAlgorithm 10’はアドレス・ビットＤＰＡに対して安全である。オーバヘッドについて、Algorithm10およびAlgorithm 10’における楕円曲線上の点の演算（ＥＣＤＢＬとＥＣＡＤＤ）の数は、Algorithm7およびAlgorithm 7’の場合と等しく、増加した部分は＊で示された演算におけるインデックスだけである。従って、Algorithm10およびAlgorithm 10’におけるオーバヘッドは僅かである。
【００８１】
図１４は、図１に示されているような暗号化／復号ユニットまたはプロセッサによって実行されるAlgorithm 10およびAlgorithm 10’のフロー図を示している。Algorithm 10およびAlgorithm 10'の違いはＲＰＣとＲＣのうちのいずれを使用するかだけである。
【００８２】
図１４を参照すると、ステップ１４０２において、プロセッサは、乱数ｒのｎ−１番目のビットの値ｒｎ−１に従って、ＲＰＣまたはＲＣ変換した点Ｑの座標値をレジスタＴ［ｒｎ−１］に代入する。ステップ１４０４において、プロセッサは、乱数ｒのｎ−１番目のＬＳＢの値ｒｎ−１に従って、レジスタＴ［１−ｒｎ−１］の値をＥＣＤＢＬ演算してその２倍値をレジスタＴ［ｒｎ−１］に代入する。ステップ１４０２および１４０４は初期化のための処理である。
【００８３】
ステップ１４０６は、ステップ１４０８〜１４１６を含んでおり、変数ｉ＝ｎ−２，．．．０に対するループ処理である。
【００８４】
ステップ１４０８において、プロセッサは、乱数ｒのｉ＋１番目のＬＳＢの値ｒｉ＋１と鍵のｉ番目のＬＳＢの値ｄｉに従って、レジスタＴ［ｄｉ］の値をＥＣＤＢＬ演算してレジスタＴ［２］に代入する。ステップ１４１０において、プロセッサは、レジスタＴ［０］およびＴ［１］の値をＥＣＡＤＤ演算してその加算値をレジスタＴ［１］に代入する。ステップ１４１２において、プロセッサは、乱数ｒのｉ番目のＬＳＢの値ｒｉと鍵のｉ番目のＬＳＢの値ｄｉに従ってレジスタ
【数１６】
2008217033.tif 000018
の値をＥＣＤＢＬ演算してその２倍値をレジスタＴ［０］に代入する。ステップ１４１４において、プロセッサは、乱数ｒのｉ番目のＬＳＢの値ｒｉと鍵のｉ番目のＬＳＢの値ｄｉの値に従って、レジスタ
【数１７】
2008217033.tif 000019
の値をレジスタＴ［１］に代入する。ステップ１４１６においてｉ＝ｉ−１とセットする。ｉ＝ｎ−２，．．．０についてステップ１４０６のループ処理が終了したとき、手順はステップ１４１８に進む。
【００８５】
ステップ１４１８において、プロセッサは、レジスタＴ［０］の値をＲＰＣまたはＲＣ逆変換して出力する。
【００８６】
図１５は、Algorithm 10およびAlgorithm 10’を実装したブロック図を示している。図１５、および後で説明する図１７、１９、２２および２３において、“Ｔ［ｘ］”は一時的変数格納レジスタを表し、“W[ｘ]”はテーブル変数格納レジスタを表し、“ｘ”は格納レジスタのアドレスであり、“ｄ”および“ｄ’”は秘密情報を格納するレジスタであり、“ｒ”は乱数ｒを格納するレジスタを表し、“Ｒ”は出力値を格納するレジスタを表し、ＥＣＤＢＬ演算は楕円曲線上の点の２倍算演算処理ブロックを表し、“ＥＣＡＤＤ”は楕円曲線上の点の加算演算処理ブロックを表し、“ＳＥＬ”は複数の入力のうち1つを選択し出力するセレクタを表し、“Ｄ”は１つの入力を複数の出力先のうちどれかを選択して出力するデマルチプレクサを表し、“ＲＮＧ”は乱数生成ブロックを表し、
【数１８】
2008217033.tif 000020
はビット毎のＸＯＲ演算を表し、“＞＞１”は１ビット右シフト演算を表し、“△”はＮＯＴ演算を表す。
【００８７】
暗号化装置は、さらに、プロセッサ６２と、ＲＯＭのようなプログラム・メモリ６４とを含んでいる。プロセッサ６２は、メモリ６４に格納されているプログラムに従って図１５に示された諸要素を制御する。代替構成として、プロセッサ６２は、その諸要素に対応する機能を実現するメモリ６４中のプログラムを実行することによってその諸要素を実現してもよい。
【００８８】
図１５のブロック図のフローを次に示す。
【００８９】
【数１９】
2008217033.tif 000021
【００９０】
Algorithm 10およびAlgorithm 10'とこのフローの相違は以下の通りである。
−  初期化処理において、Algorithm 10およびAlgorithm 10'ではＱとＥＣＤＢＬ（Ｑ）を代入するレジスタＴ［０］およびＴ［１］を、ｒｎ−１によって直接指定したが、このフローでは、いったんレジスタＴ［０］およびＴ［１］の両方にＱを代入し、ＥＣＤＢＬを計算してレジスタＴ［２］に格納して、次いでレジスタＴ［２］の値をコピーして格納するべきレジスタをｒｎ−１によって決定するという、３つのステップで構成している。
−  Algorithm 10およびAlgorithm 10'ではループ処理内で秘密鍵ｄと乱数ｒの演算を行っているが、このフローでは、ループ処理の前の秘密鍵のランダム化とループ処理後の逆変換において秘密鍵ｄと乱数ｒのＸＯＲ演算を行う。これに伴って、点の２倍算とデータのコピーにおけるインデックスが変更される。Algorithm 10およびAlgorithm 10'とこのフローの処理は等価であり、同型変換可能である。
−  図１５では、このフローにおけるインデックスの計算をセレクタで構成している。これはハードウェアで表現するためであり、共に効果は同じである。
【００９１】
図８のAlgorithm 7およびAlgorithm 7’のブロック図と比較すると、図１５のAlgorithm 10およびAlgorithm 10’のブロック図では、秘密鍵のランダム化処理が増加するのみで、楕円曲線上の点の加算と２倍算の回数は変わらない。
【００９２】
次のAlgorithm 11およびAlgorithm 11’は、それぞれAlgorithm 5およびAlgorithm 5’に対して同様のアドレス・ビットＤＰＡ対策を施したものである。
【００９３】
〈Algorithm11: Binary Method (MSB, add-and-double-always, RPC, RA)〉
【数２０】
2008217033.tif 000022
【００９４】
ここで、Ｔ”［０］、Ｔ ”［１］およびＴ”［２］は一時的変数であり、ｄはｎビットのスカラー値であり、ｄｉはｄのｉ番目のＬＳＢの値である。ｒはｎビットの乱数であり、ｒｉはｒのｉ番目のＬＳＢの値とする。また、“←”はＲＰＣ表現からの逆変換を表す。
【００９５】
〈Algorithm11’: Binary Method (MSB, add-and-double-always, RC, RA)〉
【数２１】
2008217033.tif 000023
【００９６】
ここで、Ｔ”［０］、Ｔ ”［１］およびＴ”［２］は一時的変数であり、ｄはｎビットのスカラー値であり、ｄｉはｄのｉ番目のＬＳＢの値である。ｒはｎビットの乱数であり、ｒｉはｒのｉ番目のＬＳＢの値とする。また、“←”はＲＣ表現からの逆変換を表す。
【００９７】
図１６は、図１に示されているような暗号化／復号ユニットまたはプロセッサによって実行されるAlgorithm 11およびAlgorithm 11’のフロー図を示している。
【００９８】
ステップ１５０２において、プロセッサは、ＲＰＣまたはＲＣ変換した点Ｑの座標値をレジスタＴ［２］に代入する。ステップ１５０４において、プロセッサは、乱数ｒのｎ−１番目のＬＳＢの値ｒｎ−１に従ってレジスタＴ［２］の値をＥＣＤＢＬ演算してその２倍値をレジスタＴ［ｒｎ−１］に代入する。ステップ１５０２および１５０４は初期化のための処理である。
【００９９】
ステップ１５０６は、ステップ１５０８〜１５１４を含んでおり、変数ｉ＝ｎ−２，．．．０に対するループ処理である。
【０１００】
ステップ１５０８において、プロセッサは、乱数ｒのｉ＋１番目のＬＳＢの値ｒｉ＋１に従ってレジスタＴ［ｒｉ＋１］の値をＥＣＤＢＬ演算してその２倍値をレジスタＴ［ｒｉ＋１］に代入する。ステップ１５１０において、プロセッサは、乱数ｒのｉ＋１番目のＬＳＢの値ｒｉ＋１に従ってレジスタＴ［ｒｉ＋１］とＴ［２］の値をＡＤＤ演算してその加算値をレジスタＴ［１−ｒｉ＋１］に代入する。ステップ１５０２において、プロセッサは、乱数ｒのｉ＋１番目およびｉ番目のＬＳＢの値ｒｉおよびｒｉ＋１と鍵のｉ番目のＬＳＢの値ｄｉに従って、レジスタ
【数２２】
2008217033.tif 000024
の値をＥＣＤＢＬ演算してその２倍値をレジスタＴ［０］に代入する。ｉ＝ｎ−２，．．．０についてステップ１５０６のループ処理が終了したとき、手順はステップ１５１６に進む。
【０１０１】
ステップ１５１６において、プロセッサは乱数ｒの０番目のＬＳＢの値ｒ０に従って、レジスタＴ［ｒ０］の値をＲＰＣまたはＲＣ逆変換して出力する。
【０１０２】
図１７は、Algorithm 11およびAlgorithm 11’を実装したブロック図を示している。
【０１０３】
暗号化装置は、さらに、プロセッサ６２と、ＲＯＭのようなプログラム・メモリ６４とを含んでいる。プロセッサ６２は、メモリ６４に格納されているプログラムに従って図１７に示された諸要素を制御する。代替構成として、プロセッサ６２は、その諸要素に対応する機能を実現するメモリ６４中のプログラムを実行することによってその諸要素を実現してもよい。
【０１０４】
図１７のブロック図のフローを次に示す。
【０１０５】
〈実施例２のフロー:Algorithm11、11'の実施例フロー〉
【数２３】
2008217033.tif 000025
【０１０６】
このフローはAlgorithm 11およびAlgorithm 11'のどちらにも適応可能である。Algorithm 11およびAlgorithm 11'とこのフローの相違は以下の通りである。
−  Algorithm 11およびAlgorithm 11'では、初期化処理においてｒｎ−１によって指定されるレジスタＴ［０］およびＴ［１］のどちらかをＱで初期化するが、このフローでは、レジスタＴ［０］およびＴ［１］の両方をＱで初期化する。
−  Algorithm 11およびAlgorithm 11'では、コピーにおいて秘密鍵ｄと乱数ｒの演算を行うが、このフローではループ処理の前の秘密鍵のランダム化処理とループ処理後の逆変換処理において秘密鍵ｄと乱数ｒのＸＯＲ演算を行う。これに伴って、データのコピーにおけるインデックスが変更される。Algorithm 11およびAlgorithm 11'とこのフローの処理は等価であり、同型変換可能である。
−  図１７では、このフローにおけるインデックス計算をセレクタとデマルチプレクサで実現している。これはハードウェアで表現するためであり、共に効果は同じである。
【０１０７】
図４のAlgorithm 5およびAlgorithm 5’のブロック図と比較すると、図１７のAlgorithm 11およびAlgorithm 11'のブロック図では、秘密鍵のランダム化処理、データの出力先を選択するセレクタ、およびデマルチプレクサが増加するのみで、楕円曲線上の点の加算と2倍算の回数は変わらない。
【０１０８】
次のAlgorithm 12およびAlgorithm 12’は、それぞれAlgorithm 6およびAlgorithm 6’に対して同様のアドレス・ビットＤＰＡ対策を施したものである。
【０１０９】
〈Algorithm12: Binary Method (LSB, add-and-double-always, RPC, RA)〉
【数２４】
2008217033.tif 000026
【０１１０】
ここで、Ｔ”［０］、Ｔ ”［１］およびＴ”［２］は一時的変数であり、ｄはｎビットのスカラー値であり、ｄｉはｄのｉ番目のＬＳＢの値である。ｒは（ｎ＋１）ビットの乱数であり、ｒｉはｒのｉ番目のＬＳＢの値とする。また、“←”はＲＰＣ表現からの逆変換を表す。
【０１１１】
〈Algorithm12’: Binary Method (LSB, add-and-double-always, RC, RA)〉
【数２５】
2008217033.tif 000027
【０１１２】
ここで、Ｔ”［０］、Ｔ ”［１］およびＴ”［２］は一時的変数であり、ｄはｎビットのスカラー値であり、ｄｉはｄのｉ番目のＬＳＢの値である。ｒは（ｎ＋１）ビットの乱数であり、ｒｉはｒのｉ番目のＬＳＢの値とする。また、“←”はＲＣ表現からの逆変換を表す。
【０１１３】
図１８は、図１に示されているような暗号化／復号ユニットまたはプロセッサによって実行されるAlgorithm 12およびAlgorithm 12’のフロー図を示している。
【０１１４】
ステップ１６０２において、プロセッサは、乱数ｒの０番目のＬＳＢの値ｒ０に従って０（ゼロ）点の座標をレジスタＴ［ｒ０］に代入する。ステップ１６０４において、プロセッサは、ＲＰＣまたはＲＣ変換した点Ｑの座標値をレジスタＴ［２］に代入する。ステップ１６０２および１６０４は初期化のための処理である。
【０１１５】
ステップ１６０６は、ステップ１６０８〜１６１６を含んでおり、変数ｉ＝０，．．．ｎ−１に対するループ処理である。
【０１１６】
ステップ１６０８において、プロセッサは、乱数ｒのｉ番目のＬＳＢの値ｒｉに従ってレジスタＴ［ｒｉ］およびＴ［２］の値をＥＣＡＤＤ演算してレジスタＴ［１−ｒｉ］に代入する。ステップ１６１０において、プロセッサは、レジスタＴ［２］の値をＥＣＤＢＬ演算してレジスタＴ［２］に代入する。ステップ１６１２において、プロセッサは、乱数ｒのｉおよびｉ＋１番目のＬＳＢの値ｒｉおよびｒｉ＋１と鍵のｉ番目のＬＳＢの値ｄｉに従ってレジスタ
【数２６】
2008217033.tif 000028
の値をレジスタＴ［ｒｊ＋１］に代入する。ステップ１６１４において、プロセッサは、ｉ＝ｉ＋１とセットする。ｉ＝０，．．．ｎ−１についてステップ１６０６のループ処理が終了したとき、手順はステップ１６１６に進む。
【０１１７】
ステップ１６１６において、プロセッサは、乱数ｒのｎ番目のＬＳＢの値ｒｎに従って、レジスタＴ［ｒｎ］の値をＲＰＣまたはＲＣ逆変換して出力する。
【０１１８】
図１９は、Algorithm 12およびAlgorithm 12’を実装したブロック図を示している。
【０１１９】
暗号化装置は、さらに、プロセッサ６２と、ＲＯＭのようなプログラム・メモリ６４とを含んでいる。プロセッサ６２は、メモリ６４に格納されているプログラムに従って図１９に示された諸要素を制御する。代替構成として、プロセッサ６２は、その諸要素に対応する機能を実現するメモリ６４中のプログラムを実行することによってその諸要素を実現してもよい。
【０１２０】
図１９のブロック図のフローを次に示す。
【０１２１】
【数２７】
2008217033.tif 000029
【０１２２】
このフローはAlgorithm 12およびAlgorithm 12'のどちらにも適応可能である。Algorithm 12およびAlgorithm 12'とこのフローの相違は以下の通りである。
−  Algorithm 12およびAlgorithm 12'では、初期化処理においてｒｎ−１によって指定されるレジスタＴ［０］およびＴ［１］のどちらかを０に初期化しているが、このフローでは、レジスタＴ［０］およびＴ［１］の両方を０に初期化する。
−  Algorithm 12およびAlgorithm 12'では、コピー処理において秘密鍵ｄと乱数ｒの演算を行うが、このフローではループ処理の前の秘密鍵のランダム化とループ処理後の逆変換において秘密鍵ｄと乱数ｒのＸＯＲ演算を行う。これに伴って、データのコピーにおけるインデックスが変更される。Algorithm 12およびAlgorithm 12'とこのフローの処理は等価であり、同型変換可能である。
−  図１９においては、このフローにおけるインデックス計算をセレクタとデマルチプレクサで構成している。これはハードウェアで表現するためであり、共に効果は同じである。
【０１２３】
図６のAlgorithm 6およびAlgorithm 6’のブロック図と比較すると、図１９のAlgorithm 12およびAlgorithm 12'のブロック図では、秘密鍵のランダム化と、データの出力先を選択するセレクタおよびデマルチプレクサが増加するのみで、楕円曲線上の点の加算と２倍算の回数は変わらない。
【０１２４】
次のAlgorithm 13およびAlgorithm 13’は、それぞれAlgorithm 9およびAlgorithm 9’に対して同様のアドレス・ビットＤＰＡ対策を施したものである。
【０１２５】
〈Algorithm13: Window Method (4-bit, RPC, RA)〉
【数２８】
2008217033.tif 000030
【０１２６】
ここで、ｄはｎビットのスカラー値であり、説明を簡単にするために、nは４の倍数と仮定する。また、ｄｉ，ｉ−３は、ｄのｉビット目のからｉ−３ビット目のまでの４ビットの値とする。Ｒ’、Ｑ’、Ｔ’［０］およびＴ’［１］は一時的変数であり、Ｗ’［ｉ］はウィンドウ・メソッドで使用されるテーブルを表し、rは４ビットの乱数であり、"←"はＲＰＣ表現からの逆変換を表す。
【０１２７】
〈Algorithm13': Window Method (4-bit, RC, RA)〉
【数２９】
2008217033.tif 000031
【０１２８】
ここで、ｄはｎビットのスカラー値であり、説明を簡単にするために、ｎは４の倍数と仮定する。また、ｄｉ，ｉ−３は、ｄ中のｉビット目から（ｉ−３）ビット目までの４ビットの値とする。Ｒ”、Ｑ”、Ｔ”およびＴ”［１］は一時的変数であり、Ｗ”［ｉ］はウィンドウ・メソッドで使用されるテーブルを表し、ｒは４ビットの乱数である。“←”はＲＣ表現からの逆変換を表す。
【０１２９】
図２０および２１は、図１に示されているような暗号化／復号ユニットまたはプロセッサによって実行されるAlgorithm 13およびAlgorithm 13’のフロー図を示している。
【０１３０】
ステップ１７０２において、プロセッサは、乱数値に従って０点の座標値をテーブルＷ［ｒ］に代入する。ステップ１７０４において、プロセッサは、乱数値ｒに従いＲＰＣまたはＲＣ変換した点Ｑの座標値を
【数３０】
2008217033.tif 000032
に代入する。ステップ１７０６において、乱数値ｒに従って
【数３１】
2008217033.tif 000033
の値をＥＣＤＢＬ演算し
【数３２】
2008217033.tif 000034
に代入する。
【０１３１】
ステップ１７０８は、ステップ１７１０〜１７１２を含んでおり、変数ｉ＝３，．．．１５に対するループ処理である。
【０１３２】
ステップ１７１０において、プロセッサは、乱数値ｒに従って
【数３３】
2008217033.tif 000035
の値をＥＣＡＤＤ演算してＷ［ｉ］に代入する。ステップ１７１２において、プロセッサは、ｉ＝ｉ＋１とセットする。ステップ１７０２〜１７１２は、テーブル作成のための処理である。ｉ＝３，．．．１５についてステップ１７０８のループ処理が終了したとき、手順はステップ１７１４に進む。
【０１３３】
ステップ１７１４において、プロセッサは、乱数値ｒと鍵ｎ−１，．．．ｎ−４番目の値ｄｎ−１，ｎ−４の値に従って、
【数３４】
2008217033.tif 000036
の値をＲに代入する。ステップ１７１４は、初期化のための処理である。
【０１３４】
ステップ１７１６は、ステップ１７１８〜１７２４を含んでおり、変数ｉ＝ｎ−５，．．．０に対するループ処理である。
【０１３５】
ステップ１７１８は４回繰り返されるループ処理である。ステップ１７２０において、プロセッサはレジスタＲの値をＥＣＤＢＬ演算してＲに代入する。ステップ１７２２において、乱数値ｒと鍵のｉ，．．．ｉ−３番目のビットの値に従って
【数３５】
2008217033.tif 000037
の値とＲの値をＥＣＡＤＤ演算してＲに代入する。ステップ１７２４において、プロセッサはｉ＝ｉ−４とセットする。ｉ＝ｎ−５，．．．０についてステップ１７１６の処理が終了したとき、手順はステップ１７２６に進む。
【０１３６】
ステップ１７２６において、プロセッサは、レジスタＲの値をＲＰＣまたはＲＣ逆変換して出力する。
【０１３７】
図２２および２３は、Algorithm 13およびAlgorithm 13'を実装したブロック図を示している。
【０１３８】
暗号化装置は、さらに、プロセッサ６２と、ＲＯＭのようなプログラム・メモリ６４とを含んでいる。プロセッサ６２は、メモリ６４に格納されているプログラムに従って図２２および２３に示された諸要素を制御する。代替構成として、プロセッサ６２は、その諸要素に対応する機能を実現するメモリ６４中のプログラムを実行することによってその諸要素を実現してもよい。
【０１３９】
図２２および２３のブロック図のフローを次に表す。
【０１４０】
【数３６】
2008217033.tif 000038
【０１４１】
このフローはAlgorithm 13およびAlgorithm 13'のどちらにも適応可能である。Algorithm 13およびAlgorithm 13'とこのフローの相違は以下の通りである。
−  図２０および２１においては、このフローにおけるインデックス計算をセレクタとデマルチプレクサで構成している。これはハードウェアで表現するためであり、共に効果は同じである。
【０１４２】
図１１のAlgorithm 9およびAlgorithm 9’のブロック図と比較すると、図２２および２３のブロック図では、インデックスとランダム値のＸＯＲが増加するのみで、楕円曲線上の点の加算と２倍算の回数は変わらない。
【０１４３】
本発明によるAlgorithm11、Algorithm11’、Algorithm 12およびAlgorithm 12’、Algorithm 13およびAlgorithm 13'は、Algorithm 10およびAlgorithm10’と同様に、アドレス・ビットＤＰＡに対して安全である。オーバヘッドについても、Algorithm 11、Algorithm 12およびAlgorithm10’〜Algorithm 12’、Algorith13、およびAlgorithm 13'は、Algorithm5、Algorithm 6およびAlgorithm 5’〜Algorithm 7’、Algorithm 9、およびAlgorithm 9'と比較すると、楕円曲線上の点の演算（ＥＣＤＢＬとＥＣＡＤＤ）の数は等しく、増加したのはインデックスの計算だけである。そのため、Algorithm 8と同様、本対策による、オーバヘッドはほぼ無視できるものである。
【０１４４】
図２４は、各アルゴリズムの関係を示している。
【０１４５】
以上説明した本発明の実施形態の手法を用いることによりAlgorithm 5- Algorithm 7およびAlgorithm 5’- Algorithm 7’、 Algorithm 9およびAlgorithm 9'に対してアドレス・ビットＤＰＡ対策を施すことができる。その場合のオーバヘッドは、スカラー値の計算（シフトとＸＯＲ）のみで、楕円曲線上の点の演算は生じない。楕円曲線暗号の処理の場合、点の演算以外の処理量はほぼ無視できるので、本手法を用いた場合のオーバヘッドは無視できる。Coron 99、Messerges 99、 ＣＪ０１およびＹＩＴＴ０２の方法に使用された場合、楕円曲線上の点の演算は５％〜１５％程度だけ増加するので、本発明の手法は速度低下を起こすことなくアドレス・ビットＤＰＡ対策を実現でき、ＳＰＡ、データ・ビットＤＰＡおよびアドレス・ビットＤＰＡに対して安全な楕円曲線暗号実装方法を提供できる。
【０１４６】
以上説明した実施形態は典型例として挙げたに過ぎず、その変形およびバリエーションは当業者にとって明らかであり、当業者であれば本発明の原理および請求の範囲に記載した発明の範囲を逸脱することなく上述の実施形態の種々の変形を行えることは明らかである。
【図面の簡単な説明】
【０１４７】
【図１】図１は、暗号デバイスにおける秘密鍵を用いた暗号処理を例示している。
【図２】図２は、ウィンドウ法を用いた点のスカラー倍算Ｖ＝ｄＡのアルゴリズムを示している。
【図３】図３は、暗号化／復号ユニットまたはプロセッサによって実行されるAlgorithm 5のフロー図を示している。
【図４】図４は、Algorithm 5を実装したブロック図を示している。
【図５】図５は、暗号化／復号ユニットまたはプロセッサによって実行されるAlgorithm 6のフロー図を示している。
【図６】図６は、Algorithm 6を実装したブロック図を示している。
【図７】図７は、暗号化／復号ユニットまたはプロセッサによって実行されるAlgorithm 7のフロー図を示している。
【図８】図８は、Algorithm 7を実装したブロック図を示している。
【図９】図９および１０は、暗号化／復号ユニットまたはプロセッサによって実行されるAlgorithm 9およびAlgorithm 9’のフロー図を示している。
【図１０】(図10は図9で説明)
【図１１】図１１および１２は、Algorithm 9およびAlgorithm 9’を実装したブロック図を示している。
【図１２】(図12は図9で説明)
【図１３】図１３Ａおよび１３Ｂは、本発明の原理を説明するのに役立つ。
【図１４】図１４は、暗号化／復号ユニットまたはプロセッサによって実行されるAlgorithm 10およびAlgorithm 10’のフロー図を示している。
【図１５】図１５は、Algorithm 10およびAlgorithm 10’を実装したブロック図を示している。
【図１６】図１６は、暗号化／復号ユニットまたはプロセッサによって実行されるAlgorithm 11およびAlgorithm 11’のフロー図を示している。
【図１７】図１７は、Algorithm 11およびAlgorithm 11’を実装したブロック図を示している。
【図１８】図１８は、暗号化／復号ユニットまたはプロセッサによって実行されるAlgorithm 12およびAlgorithm 12’のフロー図を示している。
【図１９】図１９は、Algorithm 12およびAlgorithm 12’を実装したブロック図を示している。
【図２０】図２０および２１は、暗号化／復号ユニットまたはプロセッサによって実行されるAlgorithm 13およびAlgorithm 13’のフロー図を示している。
【図２１】(図21は図9で説明)
【図２２】図２２および２３は、Algorithm 13およびAlgorithm 13'を実装したブロック図を示している。
【図２３】(図23は図9で説明)
【図２４】図２４は、各アルゴリズムの関係を示している。
【図１】
2008217033.tif 000039
【図２】
2008217033.tif 000040
【図３】
2008217033.tif 000041
【図４】
2008217033.tif 000042
【図５】
2008217033.tif 000043
【図６】
2008217033.tif 000044
【図７】
2008217033.tif 000045
【図８】
2008217033.tif 000046
【図９】
2008217033.tif 000047
【図１０】
2008217033.tif 000048
【図１１】
2008217033.tif 000049
【図１２】
2008217033.tif 000050
【図１３】
2008217033.tif 000051
【図１４】
2008217033.tif 000052
【図１５】
2008217033.tif 000053
【図１６】
2008217033.tif 000054
【図１７】
2008217033.tif 000055
【図１８】
2008217033.tif 000056
【図１９】
2008217033.tif 000057
【図２０】
2008217033.tif 000058
【図２１】
2008217033.tif 000059
【図２２】
2008217033.tif 000060
【図２３】
2008217033.tif 000061
【図２４】
2008217033.tif 000062