(57)【要約】暗号装置（図１５）は秘密鍵を用いて楕円曲線暗号処理を行う。その暗号装置は、楕円曲線上の点のスカラー倍の演算手段（ＥＣＤＢＬ、ＥＣＡＤＤ）と、複数のデータ格納領域を有する格納手段（Ｔ［０］〜Ｔ［２］）と、或る値（ｄ）のビット・シーケンスと乱数（ＲＮＧ）とに従って、スカラー倍の演算ごとにその演算手段に結合すべきその複数のデータ格納領域の中の１つのアドレスを決定するアドレス決定手段（ＳＥＬ）と、を具える。
2004055756.tif 000002
【特許請求の範囲】
【請求項１】
秘密鍵を用いて楕円曲線暗号処理を行う暗号装置であって、
楕円曲線上の点のスカラー倍の演算手段と、
複数のデータ格納領域を有する格納手段と、
或る値ｄのビット・シーケンスと乱数とに従って、スカラー倍の演算ごとに前記演算手段に結合すべき前記複数のデータ格納領域の中の１つのアドレスを決定するアドレス決定手段と、
を具える、暗号装置。
【請求項２】
前記アドレス決定手段は、前記或る値ｄのビット・シーケンスと前記乱数の排他的論理和に従って、前記アドレスを決定するものである、請求項１に記載の暗号装置。
【請求項３】
前記アドレス決定手段は、前記或る値ｄのビット・シーケンスと前記乱数の和に従って、前記アドレスを決定するものである、請求項１に記載の暗号装置。
【請求項４】
前記演算手段は、アド・アンド・ダブル・オールウェイズを用いたバイナリ・メソッドで前記スカラー倍算を行うものである、請求項１に記載の暗号装置。
【請求項５】
前記演算手段は、モンゴメリ・ラダー法で前記スカラー倍算を行うものである、請求項１に記載の暗号装置。
【請求項６】
前記演算手段は、ウィンドウ・メソッドで前記スカラー倍算を行うものである、請求項１に記載の暗号装置。
【請求項７】
前記演算手段は、ＲＰＣ法による変換を含む演算を行うものである、請求項１に記載の暗号装置。
【請求項８】
前記演算手段は、ＲＣ法による変換を含む演算を行うものである、請求項１に記載の暗号装置。
【請求項９】
情報処理装置において使用するための、秘密鍵を用いて楕円曲線暗号処理を行う記憶媒体に格納されたプログラムであって、
楕円曲線上の点のスカラー倍を求めるステップと、
或る値ｄのビット・シーケンスと乱数とに従って、スカラー倍の演算ごとに使用される複数のデータ格納領域の中の１つのアドレスを決定するステップと、
を実行させるよう動作可能なプログラム。
【請求項１０】
前記点のスカラー倍を求めるステップは、前記或る値ｄのビット・シーケンスと前記乱数の排他的論理和に従って、前記アドレスを決定することを含むものである、請求項９に記載のプログラム。
【請求項１１】
前記アドレスを決定するステップは、前記或る値ｄのビット・シーケンスと前記乱数の和に従って、前記アドレスを決定することを含むものである、請求項９に記載のプログラム。
【請求項１２】
前記点のスカラー倍を求めるステップは、アド・アンド・ダブル・オールウェイズを用いたバイナリ・メソッドで前記スカラー倍算を行うものである、請求項９に記載のプログラム。
【請求項１３】
前記点のスカラー倍を求めるステップは、モンゴメリ・ラダー法で前記スカラー倍算を行うものである、請求項９に記載のプログラム。
【請求項１４】
前記点のスカラー倍を求めるステップは、ウィンドウ・メソッドで前記スカラー倍算を行うものである、請求項９に記載のプログラム。
【請求項１５】
前記点のスカラー倍を求めるステップは、ＲＰＣ法による変換を含む演算を行うものである、請求項９に記載のプログラム。
【請求項１６】
前記点のスカラー倍を求めるステップは、ＲＣ法による変換を含む演算を行うものである、請求項９に記截のプログラム。
【請求項１７】
情報処理装置において、秘密鍵を用いて楕円曲線暗号処理を行う方法であって、
楕円曲線上の点のスカラー倍を求めるステップと、
或る値ｄのビット・シーケンスと乱数とに従って、スカラー倍の演算ごとに使用される複数のデータ格納領域の中の１つのアドレスを決定するステップと、
を含む方法。
【請求項１８】
前記点のスカラー倍を求めるステップは、前記或る値ｄのビット・シーケンスと前記乱数の排他的論理和に従って、前記アドレスを決定することを含むものである、請求項１７に記載の方法。
【請求項１９】
前記アドレスを決定するステップは、前記或る値ｄのビット・シーケンスと前記乱数の和に従って、前記アドレスを決定することを含むものである、請求項１７に記載の方法。
【請求項２０】
前記点のスカラー倍を求めるステップは、アド・アンド・ダブル・オールウェイズを用いたバイナリ・メソッドで前記スカラー倍算を行うものである、請求項１７に記載の方法。
【請求項２１】
前記点のスカラー倍を求めるステップは、モンゴメリ・ラダー法で前記スカラー倍算を行うものである、請求項９に記載の方法。
【請求項２２】
前記点のスカラー倍を求めるステップは、ウィンドウ・メソッドで前記スカラー倍算を行うものである、請求項９に記載の方法。
【請求項２３】
前記点のスカラー倍を求めるステップは、ＲＰＣ法による変換を含む演算を行うものである、請求項９に記載の方法。
【請求項２４】
前記点のスカラー倍を求めるステップは、ＲＣ法による変換を含む演算を行うものである、請求項９に記載の方法。
【発明の詳細な説明】
発明の分野
本発明は、暗号処理の分野に関し、特に、楕円曲線暗号のためのプロセッサにおけるＳＰＡおよびＤＰＡのような電力解析攻撃を防止する耐タンパ（ｔａｍｐｅｒ−ｐｒｏｏｆ）暗号化／復号に関する。
発明の背景
暗号方式には一般的に公開鍵暗号方式と共通鍵暗号方式が含まれる。公開鍵暗号方式は、暗号化と復号に異なる鍵（キー）を用いる。典型的には、公開鍵を用いて平文（ｐｌａｉｎｔｅｘｔ）が暗号化され、秘密鍵を用いて暗号文（ｃｉｐｈｅｒｔｅｘｔ）が復号され、それによって暗号文が安全に送信できる。または、秘密鍵を用いて平文が暗号化され、公開鍵を用いて暗号文が復号され、それによって平文を暗号化したユーザが識別される。図１は、スマートカードのような暗号デバイスにおける秘密鍵を用いた暗号化／復号の構成の例を示している。図１において、暗号デバイスは、その内部の暗号化／復号ユニットにおいて周知の形態で秘密鍵を用いて入力平文／暗号文メッセージを処理して出力暗号文／平文メッセージを供給する。
公開鍵暗号の１つのタイプである楕円曲線暗号（Ｅｌｌｉｐｔｉｃ  Ｃｕｒｖｅ  Ｃｒｙｐｔｏｇｒａｐｈｙ）のためのプロセッサにおいては、スカラー倍算が行われる。点のスカラー倍算は、スカラー値ｄ、および楕円曲線上の点Ａに対して、Ｖ＝ｄＡを満たす点Ｒを求める。例えば、楕円曲線暗号におけるＤｉｆｆｅ−Ｈｅｌｌｍａｎ（ディッフィー・ヘルマン）鍵配送において、Ｖ＝ｄＡで表される点が秘密鍵ｄを用いてスカラー倍算で生成される。
バイナリ・メソッド（ｂｉｎａｒｙ  ｍｅｔｈｏｄ）を用いた点のスカラー倍算は、２進値ｄについて、ＭＳＢ（最上位ビット）からＬＳＢ（最下位ビット）まで順に点の２倍算と点の加算を実行することによって、Ｖを求める。例えばｄ＝２１＝２４＋２２＋２０＝（１０１０１）２についてＶを求めるとき、最初のＭＳＢ“１”に対して初期値Ｖ＝Ｏ（無限遠点）にＡの加算を実行してＶ＝Ａを生成し、次のビット“０”に対してそのＶに２倍算を実行してＶ＝Ａ×２を生成し、次のビット“１”に対してそのＶに２倍算とＡの加算を実行してＶ＝（Ａ×２）×２＋Ａを生成し、次のビット“０”に対してそのＶに２倍算を実行してＶ＝（（Ａ×２）×２＋Ａ）×２を生成し、ＬＳＢ“１”に対してそのＶに２倍算とＡの加算を実行して、Ｖ＝（（（Ａ×２）×２＋Ａ）×２）×２＋Ａ＝（２４＋２２＋２０）Ａを生成する。
効率的な指数剰余演算のためのウィンドウ法（ｗｉｎｄｏｗ  ｍｅｔｈｏｄ）が知られている。ウィンドウ法は、Ａｌｆｒｅｄ  Ｊ．Ｍｅｎｅｚｅｓ他の“ＨＡＮＤＢＯＯＫ  ＯＦ  ＡＰＰＬＩＥＤＣＲＹＰＴＯＧＲＡＰＨＹ”（ＣＲＣ  ｐｒｅｓｓ），ｐｐ．６１５，Ａｌｇｏｒｉｔｈｍ１４．８２に記載されている。
図２は、ウィンドウ法を用いて楕円曲線暗号における点のスカラー倍算Ｖ＝ｄＡを求めるためのアルゴリズムを示している。ここで、ｄは２進表現でｄ＝（ｄｕ−１，ｄｕ−２，．．．ｄ０）２と表記される。そのアルゴリズムはＣ言語で記述されている。
図２のアルゴリズムを説明する。まず、０＜ｘ＜２ｋの全ての整数ｘに対して、Ｗ［ｘ］＝ｘＡを満たす値ＷのテーブルＷを作成する。テーブルＷの作成後、ｕビットの値ｄ＝（ｄｕ−１，ｄｕ−２，．．．ｄ０）２を分割してｍ個のｋビット・シーケンスｂｉ＝（ｄｉｋ＋ｋ−１，．．．ｄｉｋ）２（ｉ＝０，１，２，．．．）を生成する。ここで、ｍ＝ｃｅｉｌｉｎｇ（ｕ／ｋ）。そのｂｉに対する値Ｗ［ｂｉ］（＝ｂｉＡ）をテーブルＷでルックアップすることによる加算Ｖ＝Ｖ＋Ｗ［ｂｉ］と、Ｖ＝２ｋＶで表される２ｋ倍算とを、上位シーケンスｂｍ−１から下位シーケンスｂ０へ順に実行することによって、Ｖ＝ｄＡを求める。
暗号解読（分析）またはタンパ（ｔａｍｐｅｒ）は、暗号文のような入手可能な情報から秘密鍵を含めた秘密情報を推定する。暗号解読の１つである電力解析攻撃が、１９９８年にＰａｕｌ  Ｋｏｃｈｅｒ（ポール  コーチャ）によって考案された。この電力解析攻撃は、スマートカードのような暗号デバイスに含まれる暗号プロセッサに相異なる入力データを与え、例えば図１に示されているようにオシロスコープ等を用いてその処理中における時間に対する消費電力の変化を測定し、統計的に充分な数の消費電力変化の曲線を収集しそれを解析し、それによって暗号プロセッサ内部の鍵情報を推定する。これは、共通鍵暗号と公開鍵暗号の双方に適用できる。
電力解析攻撃には、単純電力解析（以下、ＳＰＡという）（Ｓｉｍｐｌｅ  Ｐｏｗｅｒ  Ａｎａｌｙｓｉｓ）および電力差分攻撃（以下、ＤＰＡという）（Ｄｉｆｆｅｒｅｎｔｉａｌ  Ｐｏｗｅｒ  Ａｎａｌｙｓｉｓ）が含まれる。ＳＰＡは暗号プロセッサにおける１つの消費電力変化曲線の特徴から秘密鍵の推定を行う。ＤＰＡは相異なる多数の消費電力変化曲線の差分（以下、電力差分曲線という）を用いて解析することによって秘密鍵の推定を行う。一般的にはＤＰＡの方が強力である。
例えばＤＥＳ（Ｄａｔａ  Ｅｎｃｒｙｐｔｉｏｎ  Ｓｔａｎｄａｒｄ）およびＡＥＳ（Ａｄｖａｎｃｅｄ  Ｅｎｃｒｙｐｔｉｏｎ  Ｓｔａｎｄａｒｄ）等の共通鍵暗号に対するＳＰＡおよびＤＰＡが、Ｐａｕｌ  Ｋｏｃｈｅｒ，Ｊｏｓｈｕａ  Ｊａｆｆｅ，ａｎｄ  Ｂｅｎｊａｍｉｎ  Ｊｕｎ，“Ｄｉｆｆｅｒｅｎｔｉａｌ  Ｐｏｗｅｒ  Ａｎａｌｙｓｉｓ”ｉｎ  ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  Ａｄｖａｎｃｅｓ  ｉｎ  Ｃｒｙｐｔｏｌｏｇｙ−ＣＲＹＰＴＯ’９９，Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ，ｖｏｌ．１６６６，Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，１９９９，ｐｐ．３８８−３９７に記載されている。
例えばＲＳＡ暗号および楕円曲線暗号等の公開鍵暗号に対するＳＰＡおよびＤＰＡが、例えば、Ｔｈｏｍａｓ  Ｓ．Ｍｅｓｓｅｒｇｅｓ，Ｅｚｚｙ  Ａ．Ｄａｂｂｉｓｈ  ａｎｄ  Ｒｏｂｅｒｔ  Ｈ．Ｓｌｏａｎ“Ｐｏｗｅｒ  Ａｎａｌｙｓｉｓ  Ａｔｔａｃｋｓ  ｏｆ  Ｍｏｄｕｌａｒ  Ｅｘｐｏｎｅｎｔｉａｔｉｏｎ  ｉｎ  Ｓｍａｒｔｃａｒｄｓ”Ｃｒｙｐｔｏｇｒａｐｈｉｃ  Ｈａｒｄｗａｒｅ  ａｎｄ  Ｅｍｂｅｄｄｅｄ  Ｓｙｓｔｅｍｓ（ＣＨＥＳ’９９），Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｅｉｅｎｃｅ  Ｖｏｌ．１７１７，Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，ｐｐ．１４４−１５７（以下、Ｍｅｓｓｅｒｇｅｓ９９という）、およびＪｅａｎ−Ｓｅｂａｓｔｅｉｎ  Ｃｏｒｏｎ“Ｒｅｓｉｓｔａｎｃｅ  ａｇａｉｎｓｔ  Ｄｉｆｆｅｒｅｎｔｉａｌ  Ｐｏｗｅｒ  Ａｎａｌｙｓｉｓ  ｆｏｒ  Ｅｌｌｉｐｔｉｃ  Ｃｕｒｖｅ  Ｃｒｙｔｏｓｙｓｔｅｍｓ”Ｃｒｙｔｇｏｔｒａｐｈｉｃ  Ｈａｒｄｗａｒｅ  ａｎｄ  Ｅｍｂｅｄｄｅｄ  Ｓｙｓｔｅｍｓ（ＣＨＥＳ’９９），Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ  Ｖｏｌ．１７１７，Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，ｐｐ．２９２−３０２，１９９９（以下、Ｃｏｒｏｎ９９という）に記載されている。
楕円曲線暗号法は、楕円曲線の離散対数問題に基づくもので，Ｎ．Ｋｏｂｌｉｔｚ（“Ｅｌｌｉｐｔｉｃ  Ｃｕｒｖｅ  Ｃｒｙｐｔｏｓｙｓｔｅｍｓ”，Ｍａｔｈｅｍａｔｉｃｓ  ｏｆ  Ｃｏｍｐｕｔｅｒｓ，Ｖｏｌ．４８，ｐｐ．２０３−２０９，１９８７．）とＶ．Ｍｉｌｌｅｒ（“Ｕｓｅ  ｏｆ  ｅｌｌｉｐｔｉｃ  ｃｕｒｖｅｓ  ｉｎ  ｃｒｙｐｔｏｇｒａｐｈｙ”，Ａｄｖａｎｃｅｓ  ｉｎ  Ｃｒｙｐｔｏｌｏｇｙ−Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  Ｃｒｙｐｔｏ’８５，Ｌｅｃｕｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ，２１８（１９８６），Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，ｐｐ  ４１７−４２６）により提案された。
楕円曲線暗号は、楕円曲線上の点のスカラー倍算に基づく演算である。例えば、公開鍵点Ｐは、公開されたベースポイントと呼ばれる楕円曲線上の点Ｇに対して、スカラー値である秘密鍵ｄを用いた楕円曲線上の点のスカラー倍算Ｐ＝ｄＧで計算された楕円曲線上の点である。また、楕円曲線上のＤｉｆｆｉｅ−Ｈｅｌｍａｎ鍵共有を用いたＡとＢの間での鍵共有では、Ａの秘密鍵と公開鍵の対をｄＡ，ＰＡとし、Ｂの秘密鍵と公開鍵の対をｄＢ，ＰＢとして、Ｘ＝ｄＡＰＢ＝ｄＢＰＡの関係を利用する。楕円曲線上における点のスカラー倍算は、「点の加算（ＥＣＡＤＤ）」と「点の２倍算（ＥＣＤＢＬ）」の繰り返しからなる。スカラー倍算Ｒ＝ｄＱの最も単純な実現法に次の基本的アルゴリズムＡｌｇｏｒｉｔｈｍ１およびＡｌｇｏｒｉｔｈｍ２にそれぞれ示されたバイナリ・メソッド（ＭＳＢ）およびバイナリ・メソッド（ＬＳＢ）がある。以下の記載において、特に断らない限り、小文字（ｄ等）をスカラー値とし、大文字（Ｒ、Ｑ等）を楕円曲線上の点を表すものとする。
2004055756.tif 000003
ここで、Ｔは一時的変数、ｄはｎビットのスカラー値で、ｄｉはｄのｉ番目のＬＳＢ（最下位ビット）（下位ｉ番目のビット）の値である。
2004055756.tif 000004
2004055756.tif 000005
ここで、レジスタＴ［０］およびＴ［１］は一時的変数であり、ｄはｎビットのスカラー値であり、ｄｉはｄのｉ番目のＬＳＢの値である。
点のスカラー倍算にＡｌｇｏｒｉｔｈｍ１およびＡｌｇｏｒｉｔｈｍ２を使用したとき、＊で示された演算はｄ中のビット値に応じて実行されたりされなかったりする。ＳＰＡは、この性質を利用して秘密鍵ｄを解析する。多くの実験からＥＣＤＢＬ演算とＥＣＡＤＤ演算の電力波形は、特徴的で容易に区別可能であることが知られている。従って、ブロセッサにおけるＡｌｇｏｒｉｔｈｍ１およびＡｌｇｏｒｉｔｈｍ２の演算において発生する電力波形を測定することによって、その波形からＥＣＤＢＬとＥＣＡＤＤの演算の順序と回数が変化するので、秘密鍵ｄを解析して求めることができる。
このＳＰＡへの対策として、アド・アンド・ダブル・オールウェイズ（ａｄｄ−ａｎｄ−ｄｏｕｂｌｅ−ａｌｗａｙｓ、常に加算と２倍算を行う）と呼ばれる方法がＣｏｒｏｎ９９で提案されている。この方法は、常にＥＣＡＤＤ演算とＥＣＤＢＬ演算が交互に行われるので、ＳＰＡに対して安全である。次に、Ａｌｇｏｒｉｔｈｍ１およびＡｌｇｏｒｉｔｈｍ２に対してアド・アンド・ダブル・オールウェイズを施したものをＡｌｇｏｒｉｔｈｍ３およびＡｌｇｏｒｉｔｈｍ４として示す。
2004055756.tif 000006
ここで、レジスタＴ［０］およびＴ［１］は一時的変数であり、ｄはｎビットのスカラー値であり、ｄｉはｄのｉ番目のＬＳＢの値である。
2004055756.tif 000007
ここで、レジスタＴ［０］、Ｔ［１］およびＴ［２］は一時的変数であり、ｄはｎビットのスカラー値であり、ｄｉはｄのｉ番目のＬＳＢの値である。
Ａｌｇｏｒｉｔｈｍ３およびＡｌｇｏｒｉｔｈｍ４を用いてＳＰＡを防止することができる。しかし、Ｃｏｒｏｎ９９には、これらのアルゴリズムに対するＤＰＡについても述べられており、Ａｌｇｏｒｉｔｈｍ３およびＡｌｇｏｒｉｔｈｍ４ではＤＰＡで秘密鍵を解析して求めることができることが示されている。さらに、Ｃｏｒｏｎ９９には、ランダム化射影座標Ｒａｎｄｏｍｉｚｅｄ  Ｐｒｏｊｅｃｔｉｖｅ  Ｃｏｏｒｄｉｎａｔｅｓ（ＲＰＣ）と呼ばれる、乱数を使用した楕円曲線上の点の表現を導入することによって、Ａｌｇｏｒｉｔｈｍ３およびＡｌｇｏｒｉｔｈｍ４に対するＤＰＡへの対策が提案されている。Ａｌｇｏｒｉｔｈｍ３およびＡｌｇｏｒｉｔｈｍ４に対してＲＰＣを施したものをＡｌｇｏｒｉｔｈｍ５およびＡｌｇｏｒｉｔｈｍ６として示す。ＲＰＣで表現された楕円曲線上の点はダッシュ（ｐｒｉｍｅ）（’）付きの変数で示されている。
2004055756.tif 000008
2004055756.tif 000009
ここで、Ｔ’［０］、Ｔ’［１］およびＴ’［２］は一時的変数であり、ｄはｎビットのスカラー値であり、ｄｉはｄ中のｉ番目のＬＳＢである。“←”はＲＰＣ表現からの逆変換を示している。
図３は、図１に示されているような暗号化／復号ユニットまたはプロセッサによって実行されるＡｌｇｏｒｉｔｈｍ５のフロー図を示している。図４は、Ａｌｇｏｒｉｔｈｍ５を実装したブロック図を示している。
図３を参照すると、ステップ３０２において、プロセッサはＲＰＣ変換した点Ｑの座標の値をレジスタＴ［２］に代入する。ステップ３０４において、プロセッサはレジスタＴ［２］の値をレジスタＴ［０］に代入する。ステップ３０６は変数ｉ＝（ｎ−１），（ｎ−２），．．．０に対するループ処理である。ステップ３０６中のステップ３０８において、プロセッサはレジスタＴ［０］の値をＥＣＤＢＬ演算（点の２倍算）してその２倍値をレジスタＴ［０］に代入する。ステップ３１０において、プロセッサはレジスタＴ［０］とレジスタＴ［２］の値をＥＣＡＤＤ演算（点の加算）してその加算値をレジスタＴ［１］に代入する。ステップ３１２において、プロセッサは鍵のｉ番目のビットの値ｄｉの値に従ってレジスタＴ［ｄｉ］の値をレジスタＴ［０］に代入する。ステップ３１２はアドレス・ビットＤＰＡの標的になる。ステップ３１４において、プロセッサはｉ＝ｉ−１とセットする。その後、手順はステップ３０８に戻る。ｉ＝（ｎ−１），（ｎ−２），．．．０についてステップ３０６を実行した後、ステップ３１６において、プロセッサはレジスタＴ［０］の値をＲＰＣ逆変換して出力する。
2004055756.tif 000010
2004055756.tif 000011
ここで、Ｔ’［０］、Ｔ’［１］およびＴ’［２］は一時的変数であり、ｄはｎビットのスカラー値であり、ｄｉはｄ中のｉ番目のＬＳＢである。“←”はＲＰＣ表現からの逆変換を表している。
図５は、図１に示されているような暗号化／復号ユニットまたはプロセッサによって実行されるＡｌｇｏｒｉｔｈｍ６のフロー図を示している。図６は、Ａｌｇｏｒｉｔｈｍ６を実装したブロック図を示している。
図５を参照すると、ステップ５０２において、プロセッサは０点の座標の値をレジスタＴ［０］に代入する。ステップ５０４において、プロセッサはＲＰＣ変換した点Ｑ座標値をレジスタＴ［２］に代入する。ステップ５０６は変数ｉ＝０，１，．．．（ｎ−１）に対するループ処理である。ステップ５０６中のステップ５０８において、プロセッサはレジスタＴ［０］とＴ［２］の値をＥＣＡＤＤ演算してその加算値をレジスタＴ［１］に代入する。ステップ５１０において、プロセッサはレジスタＴ［２］の値をＥＣＤＢＬ演算してその２倍値をレジスタＴ［２］に代入する。ステップ５１２において、プロセッサは鍵のｉ番目のＬＳＢの値ｄｉの値に従ってレジスタＴ［ｄｉ］の値をレジスタＴ［０］に代入する。ステップ５１２はアドレス・ビットＤＰＡの標的になる。ステップ５１４において、プロセッサはｉ＝ｉ＋１とセットする。その後、手順はステップ５０８に戻る。ｉ＝０，１，．．．（ｎ−１）についてステップ５０６を実行した後、ステップ５１６において、プロセッサはレジスタＴ［０］の値をＲＰＣ逆変換して出力する。
Ａｌｇｏｒｉｔｈｍ５およびＡｌｇｏｒｉｔｈｍ６を用いて、ＳＰＡおよびＤＰＡを防止することができることが、Ｃｏｒｏｎ９９に述べられている。同様の効果をもつ方式としては、ＳＰＡを防止するモンゴメリ・ラダー（Ｍｏｎｔｇｏｍｅｒｙ−Ｌａｄｄｅｒ）とＲＰＣの双方を用いる方法が、Ｔ．Ｉｚｕ，ａｎｄ  Ｔ．Ｔａｋａｇｉ，“Ａ  Ｆａｓｔ  Ｐａｒａｌｌｅｌ  Ｅｌｉｐｔｉｃ  Ｃｕｒｖｅ  Ｍｕｌｔｉｐｌｉｃａｔｉｏｎ  Ｒｅｓｉｓｔａｎｔ  ａｇａｉｎｓｔ  Ｓｉｄｅ  Ｃｈａｎｎｅｌ  Ａｔｔａｃｋｓ”，ＰＫＣ  ２００２，ＬＮＣＳ  ２２７４，ｐｐ．２８０−２９６，Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，２００２．（Ｉｚｕ−Ｔｒａｋａｉ）において提案されている。これは、アド・アンド・ダブル・オールウェイズを用いたバイナリ・メソッド（Ａｌｇｏｒｉｔｈｍ３およびＡｌｇｏｒｉｔｈｍ４）の代わりにＳＰＡ対策を施したモンゴメリ・ラダーと呼ばれるスカラー倍算を用いるのが特徴である。モンゴメリ・ラダーでは、スカラー倍算Ｒ＝ｄＱにおいて、常にＥＣＡＤＤ演算とＥＣＤＢＬ演算を行うことにより、差が１Ｑとなるような２点の計算を行う。ＳＰＡ対策を施したモンゴメリ・ラダーとＲＰＣを使用したスカラー倍算をＡｌｇｏｒｉｔｈｍ７として示す。
2004055756.tif 000012
ここで、Ｔ’［０］、Ｔ’［１］およびＴ’［２］は一時的変数であり、ｄはｎビットのスカラー値であり、ｄｉはｄ中のｉ番目のＬＳＢである。“←”はＲＰＣ表現からの逆変換を示している。
図７は、図１に示されているような暗号化／復号ユニットまたはプロセッサによって実行されるＡｌｇｏｒｉｔｈｍ７のフロー図を示している。図８は、Ａｌｇｏｒｉｔｈｍ７を実装したブロック図を示している。
図７を参照すると、ステップ７０２において、プロセッサはＲＰＣ変換した点Ｑの座標の値をレジスタＴ［０］に代入する。ステップ７０４において、プロセッサは、レジスタＴ［０］の値をＥＣＤＢＬ演算してその２倍値をレジスタＴ［１］に代入する。ステップ７０６は変数ｉ＝（ｎ−２），（ｎ−１）．．．０に対するループ処理である。ステップ７０６中のステップ７０８において、プロセッサは鍵のｉ番目のＬＳＢの値ｄｉに従ってレジスタＴ［ｄｉ］の値をＥＣＤＢＬ演算してその加算値をレジスタＴ［２］に代入する。ステップ７１０において、プロセッサはレジスタＴ［０］とＴ［１］の値をＥＣＡＤＤ演算してレジスタＴ［１］に代入する。ステップ７１２において、プロセッサは鍵のｉ番目のＬＳＢの値ｄｉに従ってレジスタＴ［２−ｄｉ］の値をレジスタＴ［０］に代入する。ステップ７１４において、プロセッサは鍵のｉ番目のＬＳＢの値ｄｉに従ってレジスタＴ［１＋ｄｉ］の値をレジスタＴ［１］に代入する。ステップ７０８、７１２および７１４はアドレス・ビットＤＰＡの標的になる。ステップ７１６において、プロセッサはｉ＝ｉ−１とセットする。その後、手順はステップ７０８に戻る。ｉ＝（ｎ−２），（ｎ−１）．．．０についてステップ７０６を実行した後、ステップ７１８において、プロセッサはレジスタＴ［０］の値をＲＰＣ逆変換して出力する。
ＲＰＣと同様の効果を持つ方式としてＭ．Ｊｏｙｅ，ａｎｄ  Ｃ．Ｔｙｍｅｎ，“Ｐｒｏｔｅｃｔｉｏｎｓ  ａｇａｉｎｓｔ  ｄｉｆｆｅｒｅｎｔｉａｌ  ａｎａｌｙｓｉｓ  ｆｏｒ  ｅｌｌｉｐｔｉｃ  ｃｕｒｖｅ  ｃｒｙｐｔｏｇｒａｐｈｙ”，ＣＨＥＳ  ２００１，ＬＮＣＳ  ２１６２，ｐｐ．３７７−３９０，Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，２００１．（ＪＴ０１）において提案されたランダム化曲線Ｒａｎｄｏｍｉｚｅｄ  Ｃｕｒｖｅ（ＲＣ）法がある。ＲＣは、ＲＰＣと同様に乱数を用いた点の表現を用いることによるＤＰＡ対策である。ＲＣの適用方法はＲＰＣと同じである。アルゴリズムＡｌｇｏｒｉｔｈｍ５〜Ａｌｇｏｒｉｔｈｍ７についてＲＰＣの代わりにＲＣを用いたものを、“’”を付加してＡｌｇｏｒｉｔｈｍ５’〜Ａｌｇｏｒｉｔｈｍ７’として示す。なお、ＲＣで表現された楕円曲線上の点は（”）付の変数で表す。
2004055756.tif 000013
ここで、Ｔ”［０］、Ｔ”［１］およびＴ”［２］は一時的変数であり、ｄはｎビットのスカラー値であり、ｄｉはｄ中のｉ番目のＬＳＢである。“←”はＲＰＣ表現からの逆変換を表している。
図４は、Ａｌｇｏｒｉｔｈｍ５’のブロック図をも示している。
2004055756.tif 000014
ここで、Ｔ”［０］、Ｔ”［１］およびＴ”［２］は一時的変数であり、ｄはｎビットのスカラー値であり、ｄｉはｄ中のｉ番目のＬＳＢである。“←”はＲＣ表現からの逆変換を示している。
図６は、Ａｌｇｏｒｉｔｈｍ６’を実装したブロック図をも示している。
2004055756.tif 000015
ここで、Ｔ”［０］、Ｔ”［１］およびＴ”［２］は一時的変数であり、ｄはｎビットのスカラー値であり、ｄｉはｄ中のｉ番目のＬＳＢである。“←”はＲＣ表現からの逆変換を示している。
図８は、Ａｌｇｏｒｉｔｈｍ７’を実装したブロック図をも示している。
前述のように、スカラー倍算Ｒ＝ｄＱの実現法にはＡｌｇｏｒｉｔｈｍ１およびＡｌｇｏｒｉｔｈｍ２以外にウィンドウ・メソッドと呼ばれる方法も存在する。例えば４ビットのウィンドウ・メソッドは、初期処理としてＱの０〜１５倍を計算し、その結果をテーブルとして持っておき、秘密鍵を４ビット・ウィンドウ単位で処理する。次のＡｌｇｏｒｉｔｈｍ８は４ビットのウィンドウ・メソッドの最も基本的なアルゴリズムである。
2004055756.tif 000016
ここで、ｄはｎビットのスカラー値であり、説明を簡単にするために、ｎは４の倍数と仮定する。また、ｄｉ，ｉ−３は、ｄ中のｉビット目から（ｉ−３）ビット目までの４ビットの値とする。Ｗ［ｉ］はウィンドウ・メソッドで使用されるテーブルである。
点のスカラー倍算にＡｌｇｏｒｉｔｈｍ８が使用される場合、ｄのビット値に応じて行われたり行われなかったりするような演算は無い。従って、ウィンドウ・メソッドは、バイナリ・メソッドとは異なり、一般にＳＰＡに対して安全であるといわれている。しかし、ウィンドウ・メソッドは、バイナリ・メソッドと同様にＤＰＡに対して安全でなく、Ｃｏｒｏｎ９９の手法で解析可能であるが、バイナリ・メソッドと同様にウィンドウ・メソッドのＤＰＡ対策もＲＰＣやＲＣが有効であることが知られている。次のＡｌｇｏｒｉｔｈｍ９およびＡｌｇｏｒｉｔｈｍ９’は、Ａｌｇｏｒｉｔｈｍ８に対してＲＰＣおよびＲＣを施したものである。
2004055756.tif 000017
ここで、ｄはｎビットのスカラー値であり、説明を簡単にするために、ｎは４の倍数と仮定する。また、ｄｉ，ｉ−３は、ｄ中のｉビット目から（ｉ−３）ビット目までの４ビットの値とする。Ｒ’、Ｑ’、Ｔ’［０］およびＴ’［１］は一時的変数であり、Ｗ’［ｉ］はウィンドウ・メソッドで使用されるテーブルであり、“←”はＲＰＣ表現からの逆変換を示している。
2004055756.tif 000018
2004055756.tif 000019
ここで、ｄはｎビットのスカラー値であり、説明を簡単にするために、ｎは４の倍数と仮定する。また、ｄｉ，ｉ−３は、ｄ中のｉビット目から（ｉ−３）ビット目までの４ビットの値とする。Ｒ”、Ｑ”、Ｔ”［０］およびＴ［１］は一時的変数であり、Ｗ”［ｉ］はウィンドウ・メソッドで使用されるテーブルであり、“←”はＲＣ表現からの逆変換を示している。
図９および１０は、図１に示されているような暗号化／復号ユニットまたはプロセッサによって実行されるＡｌｇｏｒｉｔｈｍ９およびＡｌｇｏｒｉｔｈｍ９’のフロー図を示している。図１１および１２は、Ａｌｇｏｒｉｔｈｍ９およびＡｌｇｏｒｉｔｈｍ９’を実装したブロック図を示している。
図９および１０を参照すると、ステップ９０２において、プロセッサは０点の座標値をテーブルＷ［０］に代入する。ステップ９０４において、プロセッサはＲＰＣ変換した点Ｑの座標値をテーブルＷ［１］に代入する。ステップ９０６において、プロセッサはテーブルＷ［１］の値をＥＣＤＢＬ演算してテーブルＷ［２］に代入する。ステップ９０８は変数ｉ＝３，４，．．．１５に対するループ処理である。ステップ９１０において、プロセッサはテーブルＷ［ｉ−１］とＷ［１］の値をＥＣＡＤＤ演算してＷ［ｉ］に代入する。ステップ９１２において、プロセッサはｉ＝ｉ＋１とセットする。ステップ９１４において、プロセッサは、鍵のｎ−１，ｎ−２，．．．ｎ−４ビット目の値ｄｎ−１，ｎ−４に従ってテーブルＷ［ｄｎ−１，ｎ−４］の値をＲに代入する。
ステップ９１６は変数ｉ＝（ｎ−５），（ｎ−６），．．．０に対するループ処理である。ステップ９１６中のステップ９１８は４回反復ループ処理である。ステップ９２０において、プロセッサはレジスタＲの値をＥＣＤＢＬ演算してＲに代入する。ステップ９２０は４回繰り返される。ステップ９２２において、プロセッサは鍵のｉ〜（ｉ−３）ビット目の値ｄｉ，ｉ−３に従ってテーブルＷ［ｄｉ，ｉ−３］の値とレジスタＲの値をＥＣＡＤＤ演算してその加算値をレジスタＲに代入する。ステップ９２２はアドレス・ビットＤＰＡの標的になる。ステップ９２４において、プロセッサはｉ＝ｉ−４とセットする。その後、手順はステップ９１８に戻る。ｉ＝（ｎ−５），（ｎ−６），．．．０についてステップ９２４を実行した後、ステップ９２６において、プロセッサはレジスタＲの値をＲＰＣ逆変換して出力する。
従来、Ａｌｇｏｒｉｔｈｍ５〜Ａｌｇｏｒｉｔｈｍ７およびＡｌｇｏｒｉｔｈｍ５’〜Ａｌｇｏｒｉｔｈｍ７’、Ａｌｇｏｒｉｔｈｍ９およびＡｌｇｏｒｉｔｈｍ９’を用いれば、ＳＰＡおよびＤＰＡに対して安全であると考えられていた。しかし、Ｋ．Ｉｔｏｈ，Ｔ．Ｉｚｕ，ａｎｄ  Ｍ．Ｔａｋｅｎａｋａ“Ａｄｄｒｅｓｓ−ｂｉｔ  Ｄｉｆｆｅｒｅｎｔｉａｌ  Ｐｏｗｅｒ  Ａｎａｌｙｓｉｓ  ｏｆ  Ｃｒｙｐｔｏｇｒａｐｈｉｃ  Ｓｃｈｅｍｅｓ  ＯＫ−ＥＣＤＨ  ａｎｄ  ＯＫ−ＥＣＤＳＡ”，Ｃｒｙｐｔｏｇｒａｐｈｉｃ  Ｈａｒｄｗａｒｅ  ａｎｄ  Ｅｍｂｅｄｄｅｄ  Ｓｙｓｔｅｍｓ（ＣＨＥＳ２００２），Ｐｒｅ−ｐｒｏｃｅｅｄｉｎｇ，ｐｐ．１２９−１４３（以下、ＩＩＴ０２という）でＡｌｇｏｒｉｔｈｍ７を解析して求める手法が発表された。通常のＤＰＡ（データビットＤＰＡ（ｄａｔａ−ｂｉｔ  ＤＰＡ））は、データの変化がもたらす消費電力に注目するのに対して、このアドレス・ビットＤＰＡ（ａｄｄｒｅｓｓ−ｂｉｔ  ＤＰＡ）は、アドレスの変化がもたらす消費電力に注目した解析手法である。
例えば、Ａｌｇｏｒｉｔｈｍ７において、＊の演算ｄでは、ｄｉの値に応じて、Ｔ’［０］が使用されるかまたはＴ’［１］が使用されるかが決定される。従って、ＥＣＤＢＬ演算で使用されるデータが格納されているアドレスはｄｉと相関関係を有する。同様のことが＃で示された演算においても生じている。アドレス・ビットＤＰＡでは、その関係を利用して秘密鍵情報ｄを解析可能としている。
文献ＩＩＴ０２では、モンゴメリ・ラダー（Ａｌｇｏｒｉｔｈｍ７）に対して、アドレス・ビットＤＰＡを行っているが、同様の解析は、Ａｌｇｏｒｉｔｈｍ５、Ａｌｇｏｒｉｔｈｍ６およびＡｌｇｏｒｉｔｈｍ５’〜Ａｌｇｏｒｉｔｈｍ７’に対しても適用可能である。Ａｌｇｏｒｉｔｈｍ９およびＡｌｇｏｒｉｔｈｍ９’でも＊で示された演算において、秘密鍵情報ｄの値と使用するテーブルとが強い相関関係を有するので、同様の攻撃が可能であると考えられる。そのためアドレス・ビットＤＰＡを用いれば，Ａｌｇｏｒｉｔｈｍ５〜７およびＡｌｇｏｒｉｔｈｍ５’〜Ａｌｇｏｒｉｔｈｍ７’、Ａｌｇｏｒｉｔｈｍ９〜Ａｌｇｏｒｉｔｈｍ９’はＤＰＡに対して安全であるとはいえない。
ＩＩＴ０２には、アドレス・ビットＤＰＡへの対策について述べられている。ＩＩＴ０２で述べられているのは、Ａｌｇｏｒｉｔｈｍ５〜Ａｌｇｏｒｉｔｈｍ７に対してＣｏｒｏｎ９９やＭｅｓｓａｇｅｓ９９で提案されているエクスポーネント・ブラインディング（ｅｘｐｏｎｅｎｔ−ｂｌｉｎｄｉｎｇ）、Ｃ．Ｃｌａｖｉｅｒ，ａｎｄ  Ｍ．Ｊｏｙｅ，“Ｕｎｉｖｅｒｓａｌ  ｅｘｐｏｎｅｎｔｉａｔｉｏｎ  ａｌｇｏｒｉｔｈｍ−Ａ  ｆｉｒｓｔ  ｓｔｅｐ  ｔｏｗａｒｄｓ  ｐｒｏｖａｂｌｅ  ＳＰＡ−ｒｅｓｉｓｔａｎｃｅ−”，Ｃｒｙｐｔｏｇｒａｐｈｉｃ  Ｈａｒｄｗａｒｅ  ａｎｄ  Ｅｍｂｅｄｄｅｄ  Ｓｙｓｔｅｍｓ（ＣＨＥＳ２００１），Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ  ｖｏｌ．２１６２，Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，ｐｐ．３００−３０８（以下、ＣＪ０１という）において提案されているエクスポーネント・スプリッティング（ｅｘｐｏｎｅｎｔ−ｓｐｌｉｔｔｉｎｇ）、Ｊ．Ｙａｊｉｍａ，Ｋ．Ｉｔｏｈ，Ｍ．Ｔａｋｅｎａｋａ，ａｎｄ  Ｎ，Ｔｏｒｉｉ“ＤＰＡ  ｃｏｎｔｅｒｍｅａｓｕｒｅ  ｂｙ  ｉｍｐｒｏｖｉｎｇ  ｔｈｅ  ｗｉｎｄｏｗ  ｍｅｔｈｏｄ”，Ｃｒｙｐｔｏｇｒａｐｈｉｃ  Ｈａｒｄｗａｒｅ  ａｎｄ  Ｅｍｂｅｄｄｅｄ  Ｓｙｓｔｅｍｓ（ＣＨＥＳ２００２），Ｐｒｅ−ｐｒｏｃｅｅｄｉｎｇ，ｐｐ．３０４−３１９（以下、ＹＩＴＴ０２という）において提案されているオーバラップ・ウィンドウ法（ｏｖｅｒｌａｐｐｅｄ  ｗｉｎｄｏｗ  ｍｅｔｈｏｄ）等のスカラー値をランダムに変化させる手法を適用することである。
しかし、これらの手法は、その手法単独でＳＰＡ対策、データ・ビットＤＰＡ対策およびアドレス・ビットＤＰＡ対策であるので、既にＳＰＡ対策とデータ・ビットＤＰＡ対策済みのＡｌｇｏｒｉｔｈｍ５〜Ａｌｇｏｒｉｔｈｍ７に適用するには無駄が多い。特にこれらの手法を適用すると、楕円曲線上の点の加算および２倍算を、適用前と比較して余分に処理しなければならず、処理オーバーヘッドが大きくなる欠点がある。
発明者たちは、アドレス・ビットＤＰＡに対して安全な耐タンパ性の点のスカラー倍算を実現することの必要性（ニーズ）を認識した。
本発明の１つの目的は、秘密鍵の推定を困難にし、暗号処理の安全性を高めることである。
本発明の別の目的は、効率的な耐タンパ性の点のスカラー倍算を実現することである。
本発明のさらに別の目的は、アドレス・ビットＤＰＡに対して効率的で安全な耐タンパ性の点のスカラー倍算を実現することである。
発明の概要
本発明の特徴によれば、暗号装置（は秘密鍵を用いて楕円曲線暗号処理を行う。その暗号装置は、楕円曲線上の点のスカラー倍の演算手段と、複数のデータ格納領域を有する格納手段と、或る値のビット・シーケンスと乱数とに従って、スカラー倍の演算ごとにその演算手段に結合すべきその複数のデータ格納領域の中の１つのアドレスを決定するアドレス決定手段と、を具えている。
本発明の別の特徴によれば、情報処理装置において使用するための、秘密鍵を用いて楕円曲線暗号処理を行うプログラム（これは記憶媒体に格納されていてもよい）は、楕円曲線上の点のスカラー倍を求めるステップと、或る値ｄのビット・シーケンスと乱数とに従って、スカラー倍の演算ごとに使用される複数のデータ格納領域の中の１つのアドレスを決定するステップと、を実行させるよう動作可能である。
本発明のさらに別の特徴によれば、情報処理装置において、秘密鍵を用いて楕円曲線暗号処理を行う方法は、楕円曲線上の点のスカラー倍を求めるステップと、或る値ｄのビット・シーケンスと乱数とに従って、スカラー倍の演算ごとに使用される複数のデータ格納領域の中の１つのアドレスを決定するステップと、を含んでいる。
本発明によれば、秘密鍵の推定を困難にし、暗号処理の安全性を高めることができ、効率的な耐タンパ性の点のスカラー倍算を実現できる。
全ての図面を通して、同じ参照番号は同じ要素を示している。
【図面の簡単な説明】  図１は、暗号デバイスにおける秘密鍵を用いた暗号処理を例示している。
図２は、ウィンドウ法を用いた点のスカラー倍算Ｖ＝ｄＡのアルゴリズムを示している。
図３は、暗号化／復号ユニットまたはプロセッサによって実行されるＡｌｇｏｒｉｔｈｍ５のフロー図を示している。
図４は、Ａｌｇｏｒｉｔｈｍ５を実装したブロック図を示している。
図５は、暗号化／復号ユニットまたはプロセッサによって実行されるＡｌｇｏｒｉｔｈｍ６のフロー図を示している。
図６は、Ａｌｇｏｒｉｔｈｍ６を実装したブロック図を示している。
図７は、暗号化／復号ユニットまたはプロセッサによって実行されるＡｌｇｏｒｉｔｈｍ７のフロー図を示している。
図８は、Ａｌｇｏｒｉｔｈｍ７を実装したブロック図を示している。
図９および１０は、暗号化／復号ユニットまたはプロセッサによって実行されるＡｌｇｏｒｉｔｈｍ９およびＡｌｇｏｒｉｔｈｍ９’のフロー図を示している。
図１１および１２は、Ａｌｇｏｒｉｔｈｍ９およびＡｌｇｏｒｉｔｈｍ９’を実装したブロック図を示している。
図１３ＡおよびＢは、本発明の原理を説明するのに役立つ。
図１４は、暗号化／復号ユニットまたはプロセッサによって実行されるＡｌｇｏｒｉｔｈｍ１０およびＡｌｇｏｒｉｔｈｍ１０’のフロー図を示している。
図１５は、Ａｌｇｏｒｉｔｈｍ１０およびＡｌｇｏｒｉｔｈｍ１０’を実装したブロック図を示している。
図１６は、暗号化／復号ユニットまたはプロセッサによって実行されるＡｌｇｏｒｉｔｈｍ１１およびＡｌｇｏｒｉｔｈｍ１１’のフロー図を示している。
図１７は、Ａｌｇｏｒｉｔｈｍ１１およびＡｌｇｏｒｉｔｈｍ１１’を実装したブロック図を示している。
図１８は、暗号化／復号ユニットまたはプロセッサによって実行されるＡｌｇｏｒｉｔｈｍ１２およびＡｌｇｏｒｉｔｈｍ１２’のフロー図を示している。
図１９は、Ａｌｇｏｒｉｔｈｍ１２およびＡｌｇｏｒｉｔｈｍ１２’を実装したブロック図を示している。
図２０および２１は、暗号化／復号ユニットまたはプロセッサによって実行されるＡｌｇｏｒｉｔｈｍ１３およびＡｌｇｏｒｉｔｈｍ１３’のフロー図を示している。
図２２および２３は、Ａｌｇｏｒｉｔｈｍ１３およびＡｌｇｏｒｉｔｈｍ１３’を実装したブロック図を示している。
図２４は、各アルゴリズムの関係を示している。
好ましい実施形態の説明
前述のＡｌｇｏｒｉｔｈｍ７において＊で示された演算では、変数レジスタＴ’［ｘ］の格納アドレスが秘密鍵ｄｉに依存して変化することが問題である。即ち、ｄｉ＝０に対してレジスタＴ’［０］が、ｄｉ＝１に対してレジスタＴ’［１］がそれぞれ使用されるので、アドレス・ビットＤＰＡで鍵を解析して求めることができる。従って、ｄｉの値と使用される変数Ｔ’［０］およびＴ’［１］がランダムに変化すればアドレス・ビットＤＰＡで解析できなくなる。＃で示された演算についても、同様である。
図１３ＡおよびＢは、本発明の原理を説明するのに役立つ。入力値が、鍵のビット・シーケンスに従って制御されるスイッチを介して２つのレジスタ１および２に供給されて格納される。図１３Ａに示されているように、通常は、鍵のビット・シーケンスに従って、値を格納すべきレジスタの順序が入れ替わったり、使用するレジスタが決定されるのを防止するために、本発明によれば、図１３Ｂに示されているように、演算すべき値を格納するレジスタを鍵の値だけで決定せずに、鍵と乱数のＸＯＲ（排他的論理和）をとることによってアドレス・ビットＤＰＡに対して高い耐性を有する暗号処理を実現する。
次に、本発明の実施形態による、Ａｌｇｏｒｉｔｈｍ７とＡｌｇｏｒｉｔｈｍ７’において＊と＃で示された演算に乱数を導入したアルゴリズムを次のＡｌｇｏｒｉｔｈｍ１０およびＡｌｇｏｒｉｔｈｍ１０’として示す。本発明による変数をランダムに決定する方法を、ランダマイズド・アドレシング（Ｒａｎｄｏｍｉｚｅｄ  Ａｄｄｒｅｓｓｉｎｇ（ＲＡ）、乱数アドレス制御）と呼ぶ。
2004055756.tif 000020
2004055756.tif 000021
ここで、Ｔ’［０］、Ｔ’［１］およびＴ’［２］は一時的変数、ｄはｎビットのスカラー値で、ｄｉはｄのｉ番目のＬＳＢの値を表す。ｒはｎビットの乱数を表し、ｒｉはｒのｉ番目のＬＳＢの値である。“←”はＲＰＣ表現からの逆変換を示している。
2004055756.tif 000022
ここで、Ｔ”［０］、Ｔ”［１］およびＴ”［２］は一時的変数であり、ｄはｎビットのスカラー値であり、ｄｉはｄのｉ番目のＬＳＢ（最下位ビット）の値である。ｒはｎビットの乱数で、ｒｉはｒのｉ番目のＬＳＢの値とする。また、“←”はＲＣ表現からの逆変換を表す。
Ａｌｇｏｒｉｔｈｍ１０およびＡｌｇｏｒｉｔｈｍ１０’において、＊の部分はインデックスが秘密鍵ｄと乱数ｒのＸＯＲなので、変数レジスタＴ’［０］とＴ’［１］のどちらが使用されるかは秘密鍵ｄに無関係に決定される。同様に、＃で示された演算は、インデックスそのものが秘密鍵ｄと無関係である。従って、Ａｌｇｏｒｉｔｈｍ１０およびＡｌｇｏｒｉｔｈｍ１０’はアドレス・ビットＤＰＡに対して安全である。オーバヘッドについて、Ａｌｇｏｒｉｔｈｍ１０およびＡｌｇｏｒｉｔｈｍ１０’における楕円曲線上の点の演算（ＥＣＤＢＬとＥＣＡＤＤ）の数は、Ａｌｇｏｒｉｔｈｍ７およびＡｌｇｏｒｉｔｈｍ７’の場合と等しく、増加した部分は＊で示された演算におけるインデックスだけである。従って、Ａｌｇｏｒｉｔｈｍ１０およびＡｌｇｏｒｉｔｈｍ１０’におけるオーバヘッドは僅かである。
図１４は、図１に示されているような暗号化／復号ユニットまたはプロセッサによって実行されるＡｌｇｏｒｉｔｈｍ１０およびＡｌｇｏｒｉｔｈｍ１０’のフロー図を示している。Ａｌｇｏｒｉｔｈｍ１０およびＡｌｇｏｒｉｔｈｍ１０’の違いはＲＰＣとＲＣのうちのいずれを使用するかだけである。
図１４を参照すると、ステップ１４０２において、プロセッサは、乱数ｒのｎ−１番目のビットの値ｒｎ−１に従って、ＲＰＣまたはＲＣ変換した点Ｑの座標値をレジスタＴ［ｒｎ−１］に代入する。ステップ１４０４において、プロセッサは、乱数ｒのｎ−１番目のＬＳＢの値ｒｎ−１に従って、レジスタＴ［１−ｒｎ−１］の値をＥＣＤＢＬ演算してその２倍値をレジスタＴ［ｒｎ−１］に代入する。ステップ１４０２および１４０４は初期化のための処理である。
ステップ１４０６は、ステップ１４０８〜１４１６を含んでおり、変数ｉ＝ｎ−２，．．．０に対するループ処理である。
ステップ１４０８において、プロセッサは、乱数ｒのｉ＋１番目のＬＳＢの値ｒｉ＋１と鍵のｉ番目のＬＳＢの値ｄｉに従って、レジスタＴ［ｄｉ］の値をＥＣＤＢＬ演算してレジスタＴ［２］に代入する。ステップ１４１０において、プロセッサは、レジスタＴ［０］およびＴ［１］の値をＥＣＡＤＤ演算してその加算値をレジスタＴ［１］に代入する。ステップ１４１２において、プロセッサは、乱数ｒのｉ番目のＬＳＢの値ｒｉと鍵のｉ番目のＬＳＢの値ｄｉに従ってレジス
2004055756.tif 000023
［０］に代入する。ステップ１４１４において、プロセッサは、乱数ｒのｉ番目のＬＳＢの値ｒｉと鍵のｉ番目のＬＳＢの値ｄｉの値に従って、レジスタＴ［１
2004055756.tif 000024
いてｉ＝ｉ−１とセットする。ｉ＝ｎ−２，．．．０についてステップ１４０６のループ処理が終了したとき、手順はステップ１４１８に進む。
ステップ１４１８において、プロセッサは、レジスタＴ［０］の値をＲＰＣまたはＲＣ逆変換して出力する。
図１５は、Ａｌｇｏｒｉｔｈｍ１０およびＡｌｇｏｒｉｔｈｍ１０’を実装したブロック図を示している。図１５、および後で説明する図１７、１９、２２および２３において、“Ｔ［ｘ］”は一時的変数格納レジスタを表し、“Ｗ［ｘ］”はテーブル変数格納レジスタを表し、“ｘ”は格納レジスタのアドレスであり、“ｄ”および“ｄ’”は秘密情報を格納するレジスタであり、“ｒ”は乱数ｒを格納するレジスタを表し、“Ｒ”は出力値を格納するレジスタを表し、ＥＣＤＢＬ演算は楕円曲線上の点の２倍算演算処理ブロックを表し、“ＥＣＡＤＤ”は楕円曲線上の点の加算演算処理ブロックを表し、“ＳＥＬ”は複数の入力のうち１つを選択し出力するセレクタを表し、“Ｄ”は１つの入力を複数の出力先のうちどれかを選択して出
2004055756.tif 000025
はビット毎のＸＯＲ演算を表し、“＞＞１”は１ビット右シフト演算を表し、“△”はＮＯＴ演算を表す。
暗号化装置は、さらに、プロセッサ６２と、ＲＯＭのようなプログラム・メモリ６４とを含んでいる。プロセッサ６２は、メモリ６４に格納されているプログラムに従って図１５に示された諸要素を制御する。代替構成として、プロセッサ６２は、その諸要素に対応する機能を実現するメモリ６４中のプログラムを実行することによってその諸要素を実現してもよい。
図１５のブロック図のフローを次に示す。
2004055756.tif 000026
2004055756.tif 000027
Ａｌｇｏｒｉｔｈｍ１０およびＡｌｇｏｒｉｔｈｍ１０’とこのフローの相違は以下の通りである。
−  初期化処理において、Ａｌｇｏｒｉｔｈｍ１０およびＡｌｇｏｒｉｔｈｍ１０’ではＱとＥＣＤＢＬ（Ｑ）を代入するレジスタＴ［０］およびＴ［１］を、ｒｎ−１によって直接指定したが、このフローでは、いったんレジスタＴ［０］およびＴ［１］の両方にＱを代入し、ＥＣＤＢＬを計算してレジスタＴ［２］に格納して、次いでレジスタＴ［２］の値をコピーして格納するべきレジスタをｒｎ−１によって決定するという、３つのステップで構成している。
−  Ａｌｇｏｒｉｔｈｍ１０およびＡｌｇｏｒｉｔｈｍ１０’ではループ処理内で秘密鍵ｄと乱数ｒの演算を行っているが、このフローでは、ループ処理の前の秘密鍵のランダム化とループ処理後の逆変換において秘密鍵ｄと乱数ｒのＸＯＲ演算を行う。これに伴って、点の２倍算とデータのコピーにおけるインデックスが変更される。Ａｌｇｏｒｉｔｈｍ１０およびＡｌｇｏｒｉｔｈｍ１０’とこのフローの処理は等価であり、同系変換可能である。
−  図１５では、このフローにおけるインデックスの計算をセレクタで構成している。これはハードウェアで表現するためであり、共に効果は同じである。
図８のＡｌｇｏｒｉｔｈｍ７およびＡｌｇｏｒｉｔｈｍ７’のブロック図と比較すると、図１５のＡｌｇｏｒｉｔｈｍ１０およびＡｌｇｏｒｉｔｈｍ１０’のブロック図では、秘密鍵のランダム化処理が増加するのみで、楕円曲線上の点の加算と２倍算の回数は変わらない。
次のＡｌｇｏｒｉｔｈｍ１１およびＡｌｇｏｒｉｔｈｍ１１’は、それぞれＡｌｇｏｒｉｔｈｍ５およびＡｌｇｏｒｉｔｈｍ５’に対して同様のアドレス・ビットＤＰＡ対策を施したものである。
2004055756.tif 000028
2004055756.tif 000029
ここで、Ｔ”［０］、Ｔ”［１］およびＴ”［２］は一時的変数であり、ｄはｎビットのスカラー値であり、ｄｉはｄのｉ番目のＬＳＢの値である。ｒはｎビットの乱数であり、ｒｉはｒのｉ番目のＬＳＢの値とする。また、“←”はＲＰＣ表現からの逆変換を表す。
2004055756.tif 000030
ここで、Ｔ”［０］、Ｔ”［１］およびＴ”［２］は一時的変数であり、ｄはｎビットのスカラー値であり、ｄｉはｄのｉ番目のＬＳＢの値である。ｒはｎビットの乱数であり、ｒｉはｒのｉ番目のＬＳＢの値とする。また、“←”はＲＣ表現からの逆変換を表す。
図１６は、図１に示されているような暗号化／復号ユニットまたはプロセッサによって実行されるＡｌｇｏｒｉｔｈｍ１１およびＡｌｇｏｒｉｔｈｍ１１’のフロー図を示している。
ステップ１５０２において、プロセッサは、ＲＰＣまたはＲＣ変換した点Ｑの座標値をレジスタＴ［２］に代入する。ステップ１５０４において、プロセッサは、乱数ｒのｎ−１番目のＬＳＢの値ｒｎ−１に従ってレジスタＴ［２］の値をＥＣＤＢＬ演算してその２倍値をレジスタＴ［ｒｎ−１］に代入する。ステップ１５０２および１５０４は初期化のための処理である。
ステップ１５０６は、ステップ１５０８〜１５１４を含んでおり、変数ｉ＝ｎ−２，．．．０に対するループ処理である。
ステップ１５０８において、プロセッサは、乱数ｒのｉ＋１番目のＬＳＢの値ｒｉ＋１に従ってレジスタＴ［ｒｉ＋１］の値をＥＣＤＢＬ演算してその２倍値をレジスタＴ［ｒｉ＋１］に代入する。ステップ１５１０において、プロセッサは、乱数ｒのｉ＋１番目のＬＳＢの値ｒｉ＋１に従ってレジスタＴ［ｒｉ＋１］とＴ［２］の値をＥＣＤＢＬ演算してその２倍値をレジスタＴ［１−ｒｉ＋１］に代入する。ステップ１５１２において、プロセッサは、乱数ｒのｉ＋１番目およびｉ番目のＬＳＢの値ｒｉおよびｒｉ＋１と鍵のｉ番目のＬＳＢの値ｄｉに従って、レジスタ
2004055756.tif 000031
代入する。ｉ＝ｎ−２，．．．０についてステップ１５１６のループ処理が終了したとき、手順はステップ１５１６に進む。
ステップ１５１６において、プロセッサは乱数ｒの０番目のＬＳＢの値ｒ０に従って、レジスタＴ［ｒ０］の値をＲＰＣまたはＲＣ逆変換して出力する。
図１７は、Ａｌｇｏｒｉｔｈｍ１１およびＡｌｇｏｒｉｔｈｍ１１’を実装したブロック図を示している。
暗号化装置は、さらに、プロセッサ６２と、ＲＯＭのようなプログラム・メモリ６４とを含んでいる。プロセッサ６２は、メモリ６４に格納されているプログラムに従って図１７に示された諸要素を制御する。代替構成として、プロセッサ６２は、その諸要素に対応する機能を実現するメモリ６４中のプログラムを実行することによってその諸要素を実現してもよい。
図１７のブロック図のフローを次に示す。
2004055756.tif 000032
2004055756.tif 000033
このフローはＡｌｇｏｒｉｔｈｍ１１およびＡｌｇｏｒｉｔｈｍ１１’のどちらにも適応可能である。Ａｌｇｏｒｉｔｈｍ１１およびＡｌｇｏｒｉｔｈｍ１１’とこのフローの相違は以下の通りである。
−  Ａｌｇｏｒｉｔｈｍ１１およびＡｌｇｏｒｉｔｈｍ１１’では、初期化処理においてｒｎ−１によって指定されるレジスタＴ［０］およびＴ［１］のどちらかをＱで初期化するが、このフローでは、レジスタＴ［０］およびＴ［１］の両方をＱで初期化する。
−  Ａｌｇｏｒｉｔｈｍ１１およびＡｌｇｏｒｉｔｈｍ１１’では、コピーにおいて秘密鍵ｄと乱数ｒの演算を行うが、このフローではループ処理の前の秘密鍵のランダム化処理とループ処理後の逆変換処理において秘密鍵ｄと乱数ｒのＸＯＲ演算を行う。これに伴って、データのコピーにおけるインデックスが変更される。Ａｌｇｏｒｉｔｈｍ１１およびＡｌｇｏｒｉｔｈｍ１１’とこのフローの処理は等価であり、同系変換可能である。
−  図１７では、このフローにおけるインデックス計算をセレクタとデマルチプレクサで実現している。これはハードウェアで表現するためであり、共に効果は同じである。
図４のＡｌｇｏｒｉｔｈｍ５およびＡｌｇｏｒｉｔｈｍ５’のブロック図と比較すると、図１７のＡｌｇｏｒｉｔｈｍ１１およびＡｌｇｏｒｉｔｈｍ１１’のブロック図では、秘密鍵のランダム化処理、データの出力先を選択するセレクタ、およびデマルチプレクサが増加するのみで、楕円曲線上の点の加算と２倍算の回数は変わらない。
次のＡｌｇｏｒｉｔｈｍ１２およびＡｌｇｏｒｉｔｈｍ１２’は、それぞれＡｌｇｏｒｉｔｈｍ６およびＡｌｇｏｒｉｔｈｍ６’に対して同様のアドレス・ビットＤＰＡ対策を施したものである。
2004055756.tif 000034
2004055756.tif 000035
ここで、Ｔ”［０］、Ｔ”［１］およびＴ”［２］は一時的変数であり、ｄはｎビットのスカラー値であり、ｄｉはｄのｉ番目のＬＳＢの値である。ｒは（ｎ＋１）ビットの乱数であり、ｒｉはｒのｉ番目のＬＳＢの値とする。また、“←”はＲＰＣ表現からの逆変換を表す。
2004055756.tif 000036
ここで、Ｔ”［０］、Ｔ”［１］およびＴ”［２］は一時的変数であり、ｄはｎビットのスカラー値であり、ｄｉはｄのｉ番目のＬＳＢの値である。ｒは（ｎ＋１）ビットの乱数であり、ｒｉはｒのｉ番目のＬＳＢの値とする。また、“←”はＲＣ表現からの逆変換を表す。
図１８は、図１に示されているような暗号化／復号ユニットまたはプロセッサによって実行されるＡｌｇｏｒｉｔｈｍ１２およびＡｌｇｏｒｉｔｈｍ１２’のフロー図を示している。
ステップ１６０２において、プロセッサは、乱数ｒの０番目のＬＳＢの値ｒ０に従って０（ゼロ）点の座標をレジスタＴ［ｒ０］に代入する。ステップ１６０４において、プロセッサは、ＲＰＣまたはＲＣ変換した点Ｑの座標値をレジスタＴ［２］に代入する。ステップ１６０２および１６０４は初期化のための処理である。
ステップ１６０６は、ステップ１６０８〜１６１６を含んでおり、変数ｉ＝０，．．．ｎ−１に対するループ処理である。
ステップ１６０８において、プロセッサは、乱数ｒのｉ番目のＬＳＢの値ｒｉに従ってレジスタＴ［ｒｉ］およびＴ［２］の値をＥＣＤＢＬ演算してレジスタＴ［１−ｒｉ］に代入する。ステップ１６１０において、プロセッサは、レジスタＴ［２］の値をＥＣＤＢＬ演算してレジスタＴ［２］に代入する。ステップ１６１２において、プロセッサは、乱数ｒのｉおよびｉ＋１番目のＬＳＢの値ｒｉ
2004055756.tif 000037
］の値をレジスタＴ［ｒｊ＋１］に代入する。ステップ１６１４において、プロセッサは、ｉ＝ｉ＋１とセットする。ｉ＝０，．．．ｎ−１についてステップ１６０６のループ処理が終了したとき、手順はステップ１６１６に進む。
ステップ１６１６において、プロセッサは、乱数ｒのｎ番目のＬＳＢの値ｒｎに従って、レジスタＴ［ｒｎ］の値をＲＰＣまたはＲＣ逆変換して出力する。
図１９は、Ａｌｇｏｒｉｔｈｍ１２およびＡｌｇｏｒｉｔｈｍ１２’を実装したブロック図を示している。
暗号化装置は、さらに、プロセッサ６２と、ＲＯＭのようなプログラム・メモリ６４とを含んでいる。プロセッサ６２は、メモリ６４に格納されているプログラムに従って図１９に示された諸要素を制御する。代替構成として、プロセッサ６２は、その諸要素に対応する機能を実現するメモリ６４中のプログラムを実行することによってその諸要素を実現してもよい。
図１９のブロック図のフローを次に示す。
2004055756.tif 000038
このフローはＡｌｇｏｒｉｔｈｍ１２およびＡｌｇｏｒｉｔｈｍ１２’のどちらにも適応可能である。Ａｌｇｏｒｉｔｈｍ１２およびＡｌｇｏｒｉｔｈｍ１２’とこのフローの相違は以下の通りである。
−  Ａｌｇｏｒｉｔｈｍ１２およびＡｌｇｏｒｉｔｈｍ１２’では、初期化処理においてｒｎ−１によって指定されるレジスタＴ［０］およびＴ［１］のどちらかを０に初期化しているが、このフローでは、レジスタＴ［０］およびＴ［１］の両方を０に初期化する。
−  Ａｌｇｏｒｉｔｈｍ１２およびＡｌｇｏｒｉｔｈｍ１２’では、コピー処理において秘密鍵ｄと乱数ｒの演算を行うが、このフローではループ処理の前の秘密鍵のランダム化とループ処理後の逆変換において秘密鍵ｄと乱数ｒのＸＯＲ演算を行う。これに伴って、データのコピーにおけるインデックスが変更される。Ａｌｇｏｒｉｔｈｍ１２およびＡｌｇｏｒｉｔｈｍ１２’とこのフローの処理は等価であり、同系変換可能である。
−  図１９においては、このフローにおけるインデックス計算をセレクタとデマルチプレクサで構成している。これはハードウェアで表現するためであり、共に効果は同じである。
図６のＡｌｇｏｒｉｔｈｍ６およびＡｌｇｏｒｉｔｈｍ６’のブロック図と比較すると、図１９のＡｌｇｏｒｉｔｈｍ１２およびＡｌｇｏｒｉｔｈｍ１２’のブロック図では、秘密鍵のランダム化とデータの出力先を選択するセレクタ、およびデマルチプレクサが増加するのみで、楕円曲線上の点の加算と２倍算の回数は変わらない。
次のＡｌｇｏｒｉｔｈｍ１３およびＡｌｇｏｒｉｔｈｍ１３’は、それぞれＡｌｇｏｒｉｔｈｍ９およびＡｌｇｏｒｉｔｈｍ９’に対して同様のアドレス・ビットＤＰＡ対策を施したものである。
2004055756.tif 000039
2004055756.tif 000040
ここで、ｄはｎビットのスカラー値であり、説明を簡単にするために、ｎは４の倍数と仮定する。また、ｄｉ，ｉ−３は、ｄのｉビット目のからｉ−３ビット目のまでの４ビットの値とする。Ｒ’、Ｑ’、Ｔ’［０］およびＴ’［１］は一時的変数であり、Ｗ’［ｉ］はウィンドウ・メソッドで使用されるテーブルを表し、ｒは４ビットの乱数であり、”←”はＲＰＣ表現からの逆変換を表す。
2004055756.tif 000041
ここで、ｄはｎビットのスカラー値であり、説明を簡単にするために、ｎは４の倍数と仮定する。また、ｄｉ，ｉ−３は、ｄ中のｉビット目から（ｉ−３）ビット目までの４ビットの値とする。Ｒ”、Ｑ”、Ｔ”およびＴ”［１］は一時的変数であり、Ｗ”［ｉ］はウィンドウ・メソッドで使用されるテーブルを表し、ｒは４ビットの乱数である。“←”はＲＣ表現からの逆変換を表す。
図２０および２１は、図１に示されているような暗号化／復号ユニットまたはプロセッサによって実行されるＡｌｇｏｒｉｔｈｍ１３およびＡｌｇｏｒｉｔｈｍ１３’のフロー図を示している。
ステップ１７０２において、プロセッサは、乱数値に従って０点の座標値をテーブルＷ［ｒ］に代入する。ステップ１７０４において、プロセッサは、乱数値
2004055756.tif 000042
ステップ１７０８は、ステップ１７１０〜１７１２を含んでおり、変数ｉ＝３，．．．１５に対するループ処理である。
ステップ１７１０において、プロセッサは、乱数値ｒに従ってＷ［（ｉ−１）
2004055756.tif 000043
ップ１７１２において、プロセッサは、ｉ＝ｉ＋１とセットする。ステップ１７０２〜１７１２は、テーブル作成のための処理である。ｉ＝３，．．．１５についてステップ１７０８のループ処理が終了したとき、手順はステップ１７１４に進む。
ステップ１７１４において、プロセッサは、乱数値ｒと鍵ｎ−１，．．．ｎ−
2004055756.tif 000044
。ステップ１７１４は、初期化のための処理である。
ステップ１７１６は、ステップ１７１８〜１７２４を含んでおり、変数ｉ＝ｎ−５，．．．０に対するループ処理である。
ステップ１７１８は４回繰り返されるループ処理である。ステップ１７２０において、プロセッサはレジスタＲの値をＥＣＤＢＬ演算してＲに代入する。ステップ１７２２において、乱数値ｒと鍵のｉ，．．．ｉ−３番目のビットの値に従
2004055756.tif 000045
ップ１７２４において、プロセッサはｉ＝ｉ−４とセットする。ｉ＝ｎ−５，．．．０についてステップ１７１６の処理が終了したとき、手順はステップ１７２６に進む。
ステップ１７２６において、プロセッサは、レジスタＲの値をＲＰＣまたはＲＣ逆変換して出力する。。
図２２および２３は、Ａｌｇｏｒｉｔｈｍ１３およびＡｌｇｏｒｉｔｈｍ１３’を実装したブロック図を示している。
暗号化装置は、さらに、プロセッサ６２と、ＲＯＭのようなプログラム・メモリ６４とを含んでいる。プロセッサ６２は、メモリ６４に格納されているプログラムに従って図２２および２３に示された諸要素を制御する。代替構成として、プロセッサ６２は、その諸要素に対応する機能を実現するメモリ６４中のプログラムを実行することによってその諸要素を実現してもよい。
図２２および２３のブロック図のフローを次に表す。
2004055756.tif 000046
2004055756.tif 000047
このフローはＡｌｇｏｒｉｔｈｍ１３およびＡｌｇｏｒｉｔｈｍ１３’のどちらにも適応可能である。Ａｌｇｏｒｉｔｈｍ１３およびＡｌｇｏｒｉｔｈｍ１３’とこのフローの相違は以下の通りである。
−  図２０および２１においては、このフローにおけるインデックス計算をセレクタとデマルチプレクサで構成している。これはハードウェアで表現するためであり、共に効果は同じである。
図１１のＡｌｇｏｒｉｔｈｍ９およびＡｌｇｏｒｉｔｈｍ９’のブロック図と比較すると、図２２および２３のブロック図では、インデックスとランダム値のＸＯＲが増加するのみで、楕円曲線上の点の加算と２倍算の回数は変わらない。
本発明によるＡｌｇｏｒｉｔｈｍ１１、Ａｌｇｏｒｉｔｈｍ１１’、Ａｌｇｏｒｉｔｈｍ１２およびＡｌｇｏｒｉｔｈｍ１２’、Ａｌｇｏｒｉｔｈｍ１３およびＡｌｇｏｒｉｔｈｍ１３’は、Ａｌｇｏｒｉｔｈｍ１０およびＡｌｇｏｒｉｔｈｍ１０’と同様に、アドレス・ビットＤＰＡに対して安全である。オーバヘッドについても、Ａｌｇｏｒｉｔｈｍ１１、Ａｌｇｏｒｉｔｈｍ１２およびＡｌｇｏｒｉｔｈｍ１０’〜Ａｌｇｏｒｉｔｈｍ１２’、Ａｌｇｏｒｉｔｈ１３、およびＡｌｇｏｒｉｔｈｍ１３’は、Ａｌｇｏｒｉｔｈｍ５、Ａｌｇｏｒｉｔｈｍ６およびＡｌｇｏｒｉｔｈｍ５’〜Ａｌｇｏｒｉｔｈｍ７’、Ａｌｇｏｒｉｔｈｍ９、およびＡｌｇｏｒｉｔｈｍ９’と比較すると、楕円曲線上の点の演算（ＥＣＤＢＬとＥＣＡＤＤ）の数は等しく、増加したのはインデックスの計算だけである。そのため、Ａｌｇｏｒｉｔｈｍ８と同様、本対策による、オーバヘッドはほぼ無視できるものである。
図２４は、各アルゴリズムの関係を示している。
以上説明した本発明の実施形態の手法を用いることによりＡｌｇｏｒｉｔｈｍ５−Ａｌｇｏｒｉｔｈｍ７およびＡｌｇｏｒｉｔｈｍ５’−Ａｌｇｏｒｉｔｈｍ７’、Ａｌｇｏｒｉｔｈｍ９およびＡｌｇｏｒｉｔｈｍ９’に対してアドレス・ビットＤＰＡ対策を施すことができる。その場合のオーバヘッドは、スカラー値の計算（シフトとＸＯＲ）のみで、楕円曲線上の点の演算は生じない。楕円曲線暗号の処理の場合、点の演算以外の処理量はほぼ無視できるので、本手法を用いた場合のオーバヘッドは無視できる。Ｃｏｒｏｎ９９、Ｍｅｓｓｅｒｇｅｓ９９、ＣＪ０１およびＹＩＴＴ０２の方法を使用された場合、楕円曲線上の点の演算は５％〜１５％程度だけ増加するので、本発明の手法は速度低下を起こすことなくアドレス・ビットＤＰＡ対策を実現でき、ＳＰＡ、データ・ビットＤＰＡおよびアドレス・ビットＤＰＡに対して安全な楕円曲線暗号実装方法を提供できる。
以上説明した実施形態は典型例として挙げたに過ぎず、その変形およびバリエーションは当業者にとって明らかであり、当業者であれば本発明の原理および請求の範囲に記載した発明の範囲を逸脱することなく上述の実施形態の種々の変形を行えることは明らかである。
【図１】
2004055756.tif 000048
【図２】
2004055756.tif 000049
【図３】
2004055756.tif 000050
【図４】
2004055756.tif 000051
【図５】
2004055756.tif 000052
【図６】
2004055756.tif 000053
【図７】
2004055756.tif 000054
【図８】
2004055756.tif 000055
【図９】
2004055756.tif 000056
【図１０】
2004055756.tif 000057
【図１１】
2004055756.tif 000058
【図１２】
2004055756.tif 000059
2004055756.tif 000060
【図１４】
2004055756.tif 000061
【図１５】
2004055756.tif 000062
【図１６】
2004055756.tif 000063
【図１７】
2004055756.tif 000064
【図１８】
2004055756.tif 000065
【図１９】
2004055756.tif 000066
【図２０】
2004055756.tif 000067
【図２１】
2004055756.tif 000068
【図２２】
2004055756.tif 000069
【図２３】
2004055756.tif 000070
【図２４】
2004055756.tif 000071
【手続補正書】
【提出日】平成16年11月16日(2004.11.16)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
秘密鍵を用いて楕円曲線暗号処理を行う暗号装置であって、
楕円曲線上の点のスカラー倍の演算手段と、
複数のデータ格納領域を有する格納手段と、
或る値ｄのビット・シーケンスと乱数とに従って、スカラー倍の演算ごとに前記演算手段に結合すべき前記複数のデータ格納領域の中の１つのアドレスを決定するアドレス決定手段と、
を具える、暗号装置。
【請求項２】
前記アドレス決定手段は、前記或る値ｄのビット・シーケンスと前記乱数の排他的論理和に従って、前記アドレスを決定するものである、請求項１に記載の暗号装置。
【請求項３】
前記アドレス決定手段は、前記或る値ｄのビット・シーケンスと前記乱数の和に従って、前記アドレスを決定するものである、請求項１に記載の暗号装置。
【請求項４】
前記演算手段は、アド・アンド・ダブル・オールウェイズを用いたバイナリ・メソッドで前記スカラー倍算を行うものである、請求項１に記載の暗号装置。
【請求項５】
前記演算手段は、モンゴメリ・ラダー法で前記スカラー倍算を行うものである、請求項１に記載の暗号装置。
【請求項６】
前記演算手段は、ウィンドウ・メソッドで前記スカラー倍算を行うものである、請求項１に記載の暗号装置。
【請求項７】
前記演算手段は、ＲＰＣ法による変換を含む演算を行うものである、請求項１に記載の暗号装置。
【請求項８】
前記演算手段は、ＲＣ法による変換を含む演算を行うものである、請求項１に記載の暗号装置。
【請求項９】
情報処理装置において使用するための、秘密鍵を用いて楕円曲線暗号処理を行う記憶媒体に格納されたプログラムであって、
楕円曲線上の点のスカラー倍を求めるステップと、
或る値ｄのビット・シーケンスと乱数とに従って、スカラー倍の演算ごとに使用される複数のデータ格納領域の中の１つのアドレスを決定するステップと、
を実行させるよう動作可能なプログラム。
【請求項１０】
前記点のスカラー倍を求めるステップは、前記或る値ｄのビット・シーケンスと前記乱数の排他的論理和に従って、前記アドレスを決定することを含むものである、請求項９に記載のプログラム。
【請求項１１】
前記アドレスを決定するステップは、前記或る値ｄのビット・シーケンスと前記乱数の和に従って、前記アドレスを決定することを含むものである、請求項９に記載のプログラム。
【請求項１２】
前記点のスカラー倍を求めるステップは、アド・アンド・ダブル・オールウェイズを用いたバイナリ・メソッドで前記スカラー倍算を行うものである、請求項９に記載のプログラム。
【請求項１３】
前記点のスカラー倍を求めるステップは、モンゴメリ・ラダー法で前記スカラー倍算を行うものである、請求項９に記載のプログラム。
【請求項１４】
前記点のスカラー倍を求めるステップは、ウィンドウ・メソッドで前記スカラー倍算を行うものである、請求項９に記載のプログラム。
【請求項１５】
前記点のスカラー倍を求めるステップは、ＲＰＣ法による変換を含む演算を行うものである、請求項９に記載のプログラム。
【請求項１６】
前記点のスカラー倍を求めるステップは、ＲＣ法による変換を含む演算を行うものである、請求項９に記載のプログラム。
【請求項１７】
情報処理装置において、秘密鍵を用いて楕円曲線暗号処理を行う方法であって、
楕円曲線上の点のスカラー倍を求めるステップと、
或る値ｄのビット・シーケンスと乱数とに従って、スカラー倍の演算ごとに使用される複数のデータ格納領域の中の１つのアドレスを決定するステップと、
を含む方法。
【請求項１８】
前記点のスカラー倍を求めるステップは、前記或る値ｄのビット・シーケンスと前記乱数の排他的論理和に従って、前記アドレスを決定することを含むものである、請求項１７に記載の方法。
【請求項１９】
前記アドレスを決定するステップは、前記或る値ｄのビット・シーケンスと前記乱数の和に従って、前記アドレスを決定することを含むものである、請求項１７に記載の方法。
【請求項２０】
前記点のスカラー倍を求めるステップは、アド・アンド・ダブル・オールウェイズを用いたバイナリ・メソッドで前記スカラー倍算を行うものである、請求項１７に記載の方法。
【請求項２１】
前記点のスカラー倍を求めるステップは、モンゴメリ・ラダー法で前記スカラー倍算を行うものである、請求項１７に記載の方法。
【請求項２２】
前記点のスカラー倍を求めるステップは、ウィンドウ・メソッドで前記スカラー倍算を行うものである、請求項１７に記載の方法。
【請求項２３】
前記点のスカラー倍を求めるステップは、ＲＰＣ法による変換を含む演算を行うものである、請求項１７に記載の方法。
【請求項２４】
前記点のスカラー倍を求めるステップは、ＲＣ法による変換を含む演算を行うものである、請求項１７に記載の方法。
【手続補正書】
【提出日】平成17年1月20日(2005.1.20)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
秘密鍵を用いて楕円曲線暗号処理を行う暗号装置であって、
楕円曲線上の点のスカラー倍の演算手段と、
複数のデータ格納領域を有する格納手段と、
或る値ｄのビット・シーケンスと乱数とに従って、スカラー倍の演算ごとに前記演算手段に結合すべき前記複数のデータ格納領域の中の１つのアドレスを決定するアドレス決定手段と、
を具える、暗号装置。
【請求項２】
前記アドレス決定手段は、前記或る値ｄのビット・シーケンスと前記乱数の排他的論理和に従って、前記アドレスを決定するものである、請求項１に記載の暗号装置。
【請求項３】
前記アドレス決定手段は、前記或る値ｄのビット・シーケンスと前記乱数の和に従って、前記アドレスを決定するものである、請求項１に記載の暗号装置。
【請求項４】
前記演算手段は、アド・アンド・ダブル・オールウェイズを用いたバイナリ・メソッドで前記スカラー倍算を行うものである、請求項１に記載の暗号装置。
【請求項５】
前記演算手段は、モンゴメリ・ラダー法で前記スカラー倍算を行うものである、請求項１に記載の暗号装置。
【請求項６】
前記演算手段は、ウィンドウ・メソッドで前記スカラー倍算を行うものである、請求項１に記載の暗号装置。
【請求項７】
前記演算手段は、ＲＰＣ法による変換を含む演算を行うものである、請求項１に記載の暗号装置。
【請求項８】
前記演算手段は、ＲＣ法による変換を含む演算を行うものである、請求項１に記載の暗号装置。
【請求項９】
情報処理装置において使用するための、秘密鍵を用いて楕円曲線暗号処理を行う記憶媒体に格納されたプログラムであって、
楕円曲線上の点のスカラー倍を求めるステップと、
或る値ｄのビット・シーケンスと乱数とに従って、スカラー倍の演算ごとに使用される複数のデータ格納領域の中の１つのアドレスを決定するステップと、
を実行させるよう動作可能なプログラム。
【請求項１０】
前記アドレスを決定するステップは、前記或る値ｄのビット・シーケンスと前記乱数の排他的論理和に従って、前記アドレスを決定することを含むものである、請求項９に記載のプログラム。
【請求項１１】
前記アドレスを決定するステップは、前記或る値ｄのビット・シーケンスと前記乱数の和に従って、前記アドレスを決定することを含むものである、請求項９に記載のプログラム。
【請求項１２】
前記点のスカラー倍を求めるステップは、アド・アンド・ダブル・オールウェイズを用いたバイナリ・メソッドで前記スカラー倍算を行うものである、請求項９に記載のプログラム。
【請求項１３】
前記点のスカラー倍を求めるステップは、モンゴメリ・ラダー法で前記スカラー倍算を行うものである、請求項９に記載のプログラム。
【請求項１４】
前記点のスカラー倍を求めるステップは、ウィンドウ・メソッドで前記スカラー倍算を行うものである、請求項９に記載のプログラム。
【請求項１５】
前記点のスカラー倍を求めるステップは、ＲＰＣ法による変換を含む演算を行うものである、請求項９に記載のプログラム。
【請求項１６】
前記点のスカラー倍を求めるステップは、ＲＣ法による変換を含む演算を行うものである、請求項９に記載のプログラム。
【請求項１７】
情報処理装置において、秘密鍵を用いて楕円曲線暗号処理を行う方法であって、
楕円曲線上の点のスカラー倍を求めるステップと、
或る値ｄのビット・シーケンスと乱数とに従って、スカラー倍の演算ごとに使用される複数のデータ格納領域の中の１つのアドレスを決定するステップと、
を含む方法。
【請求項１８】
前記アドレスを決定するステップは、前記或る値ｄのビット・シーケンスと前記乱数の排他的論理和に従って、前記アドレスを決定することを含むものである、請求項１７に記載の方法。
【請求項１９】
前記アドレスを決定するステップは、前記或る値ｄのビット・シーケンスと前記乱数の和に従って、前記アドレスを決定することを含むものである、請求項１７に記載の方法。
【請求項２０】
前記点のスカラー倍を求めるステップは、アド・アンド・ダブル・オールウェイズを用いたバイナリ・メソッドで前記スカラー倍算を行うものである、請求項１７に記載の方法。
【請求項２１】
前記点のスカラー倍を求めるステップは、モンゴメリ・ラダー法で前記スカラー倍算を行うものである、請求項１７に記載の方法。
【請求項２２】
前記点のスカラー倍を求めるステップは、ウィンドウ・メソッドで前記スカラー倍算を行うものである、請求項１７に記載の方法。
【請求項２３】
前記点のスカラー倍を求めるステップは、ＲＰＣ法による変換を含む演算を行うものである、請求項１７に記載の方法。
【請求項２４】
前記点のスカラー倍を求めるステップは、ＲＣ法による変換を含む演算を行うものである、請求項１７に記載の方法。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】発明の詳細な説明
【補正方法】変更
【補正の内容】
【発明の詳細な説明】
（１）明細書第９頁第２９行に記載の「加算」を「２倍」と補正する。
（２）明細書第１０頁第２９行に記載の「Ｐ」を削除する。
（３）明細書第１３頁第２６行に記載の「Ｐ」を削除する。
（４）明細書第１７頁第７行に記載の「（」を削除する。
（５）明細書第２３頁第１３行に記載の「系」を「型」と補正する。
（６）明細書第２５頁第４行に記載の「ＤＢＬ演算してその２倍」を「ＡＤＤ演算してその加算」と補正する。
（７）明細書第２５頁第８行に記載の「１６」を「０６」と補正する。
（８）明細書第２６頁第１２行に記載の「系」を「型」と補正する。
（９）明細書第２８頁第１行に記載の「ＤＢＬ」を「ＡＤＤ」と補正する。
（１０）明細書第２９頁第１２行に記載の「系」を「型」と補正する。
（１１）明細書第２９頁第１８行に記載の「と」と「データ」の間に「、」を挿入する。
（１２）明細書第２９頁第１８行に記載の「、」を削除する。
（１３）明細書第３３頁第２９行に記載の「を」を「に」と補正する。
【国際調査報告】
2004055756.tif 000072
2004055756.tif 000073
2004055756.tif 000074
2004055756.tif 000075