(57)【特許請求の範囲】
【請求項１】
楕円曲線暗号において規定される楕円曲線上の２点Ｐ，Ｑ、およびスカラー値ｋ，ｌに基づくスカラー倍加算：ｋＰ＋ｌＱ、または、
超楕円曲線暗号において規定される因子Ｄ１，Ｄ２、およびスカラー値ｋ，ｌに基づくスカラー倍加算：ｋＤ１＋ｌＤ２、
いずれかのスカラー倍加算演算を実行する暗号処理装置であり、
前記スカラー値ｋ，ｌについて、すべてのビットを０，または＋１，または−１で表現し、かつ、スカラー値ｋ，ｌの対応ビット位置のビットの組み合わせ（ｋｉ，ｌｉ）、ただしｉ＝０〜ｎ、の全てを、
（ｋｉ，ｌｉ）＝（０，±１）または（±１，０）
を満足する設定としたＪＲＦ（ジョイント・レギュラーフォーム）表現スカラー値、
ｋ＝＜ｋｎ，・・・ｋ０＞、
ｌ＝＜ｌｎ，・・・ｌ０＞、
を生成するスカラー値制御部と、
前記スカラー値制御部の生成したＪＲＦ表現スカラー値を適用して、スカラー倍加算：ｋＰ＋ｌＱ、またはｋＤ１＋ｌＤ２の演算処理を実行する演算実行部と、
を有することを特徴とする暗号処理装置。
【請求項２】
前記スカラー値制御部は、
スカラー値ｋ，ｌが、両者とも偶数、または両者とも奇数である場合、いずれか一方のスカラー値の値を変更して、偶数と奇数の組み合わせに設定し、変更したスカラー値ｋ，ｌについて、対応ビット位置のビットの組み合わせ（ｋｉ，ｌｉ）が、
（ｋｉ，ｌｉ）＝（０，±１）または（±１，０）
を満足するＪＲＦ（ジョイント・レギュラーフォーム）表現スカラー値、
ｋ＝＜ｋｎ，・・・ｋ０＞、
ｌ＝＜ｌｎ，・・・ｌ０＞、
を生成する処理を実行する構成であり、
前記演算実行部は、
前記変更スカラー値に基づくスカラー倍加算：ｋＰ＋ｌＱ、またはｋＤ１＋ｌＤ２の演算処理を実行し、さらに、補正計算を実行して、変更前のスカラー値を適用したスカラー倍加算結果を算出する処理を実行する構成であることを特徴とする請求項１に記載の暗号処理装置。
【請求項３】
前記演算実行部は、
前記ＪＲＦ表現スカラー値、
ｋ＝＜ｋｎ，・・・ｋ０＞、
ｌ＝＜ｌｎ，・・・ｌ０＞、
の対応ビット（ｋｉ，ｌｉ）を選択し、スカラー倍加算：ｋＰ＋ｌＱ、またはｋＤ１＋ｌＤ２の計算に際して、ｋＰとｌＱ、またはｋＤ１とｌＤ２を同時に計算する同時計算手法を適用した演算を実行する構成であることを特徴とする請求項１に記載の暗号処理装置。
【請求項４】
前記演算実行部は、
前記ＪＲＦ表現スカラー値、
ｋ＝＜ｋｎ，・・・ｋ０＞、
ｌ＝＜ｌｎ，・・・ｌ０＞、
の対応ビット（ｋｉ，ｌｉ）のすべてについて、
Ｔ←（ｋｎＰ＋ｌｎＱ）、または、Ｔ←ｋｎＤ１＋ｌｎＤ２、
上記Ｔの算出処理を同じ計算アルゴリズムに従って実行する構成であることを特徴とする請求項３に記載の暗号処理装置。
【請求項５】
前記演算実行部は、
演算処理において、加算点：Ｐ＋Ｑ、または加算因子：Ｄ１＋Ｄ２の算出処理を実行することなく、スカラー倍加算：ｋＰ＋ｌＱ、またはｋＤ１＋ｌＤ２の演算処理を実行する構成であることを特徴とする請求項３に記載の暗号処理装置。
【請求項６】
楕円曲線暗号において規定される楕円曲線上の２点Ｐ，Ｑ、およびスカラー値ｋ，ｌに基づくスカラー倍加算：ｋＰ＋ｌＱ、または、
超楕円曲線暗号において規定される因子Ｄ１，Ｄ２、およびスカラー値ｋ，ｌに基づくスカラー倍加算：ｋＤ１＋ｌＤ２、
いずれかのスカラー倍加算演算を、暗号処理装置において実行する暗号処理方法であり、
スカラー値制御部における実行ステップであり、
前記スカラー値ｋ，ｌについて、すべてのビットを０，または＋１，または−１で表現し、かつ、スカラー値ｋ，ｌの対応ビット位置のビットの組み合わせ（ｋｉ，ｌｉ）、ただしｉ＝０〜ｎ、の全てを、
（ｋｉ，ｌｉ）＝（０，±１）または（±１，０）
を満足する設定としたＪＲＦ（ジョイント・レギュラーフォーム）表現スカラー値、
ｋ＝＜ｋｎ，・・・ｋ０＞、
ｌ＝＜ｌｎ，・・・ｌ０＞、
を生成するスカラー値制御ステップと、
演算実行部における実行ステップであり、
前記スカラー値制御部の生成したＪＲＦ表現スカラー値を適用して、スカラー倍加算：ｋＰ＋ｌＱ、またはｋＤ１＋ｌＤ２の演算処理を実行する演算実行ステップと、
を有することを特徴とする暗号処理方法。
【請求項７】
前記スカラー値制御ステップは、
スカラー値ｋ，ｌが、両者とも偶数、または両者とも奇数である場合、いずれか一方のスカラー値の値を変更して、偶数と奇数の組み合わせに設定し、変更したスカラー値ｋ，ｌについて、対応ビット位置のビットの組み合わせ（ｋｉ，ｌｉ）が、
（ｋｉ，ｌｉ）＝（０，±１）または（±１，０）
を満足するＪＲＦ（ジョイント・レギュラーフォーム）表現スカラー値、
ｋ＝＜ｋｎ，・・・ｋ０＞、
ｌ＝＜ｌｎ，・・・ｌ０＞、
を生成する処理を実行するステップであり、
前記演算実行ステップは、
前記変更スカラー値に基づくスカラー倍加算：ｋＰ＋ｌＱ、またはｋＤ１＋ｌＤ２の演算処理を実行し、さらに、補正計算を実行して、変更前のスカラー値を適用したスカラー倍加算結果を算出する処理を実行するステップであることを特徴とする請求項６に記載の暗号処理方法。
【請求項８】
前記演算実行ステップは、
前記ＪＲＦ表現スカラー値、
ｋ＝＜ｋｎ，・・・ｋ０＞、
ｌ＝＜ｌｎ，・・・ｌ０＞、
の対応ビット（ｋｉ，ｌｉ）を選択し、スカラー倍加算：ｋＰ＋ｌＱ、またはｋＤ１＋ｌＤ２の計算に際して、ｋＰとｌＱ、またはｋＤ１とｌＤ２を同時に計算する同時計算手法を適用した演算を実行するステップであることを特徴とする請求項６に記載の暗号処理方法。
【請求項９】
前記演算実行ステップは、
前記ＪＲＦ表現スカラー値、
ｋ＝＜ｋｎ，・・・ｋ０＞、
ｌ＝＜ｌｎ，・・・ｌ０＞、
の対応ビット（ｋｉ，ｌｉ）のすべてについて、
Ｔ←（ｋｎＰ＋ｌｎＱ）、または、Ｔ←ｋｎＤ１＋ｌｎＤ２、
上記Ｔの算出処理を同じ計算アルゴリズムに従って実行するステップであることを特徴とする請求項８に記載の暗号処理方法。
【請求項１０】
前記演算実行ステップは、
演算処理において、加算点：Ｐ＋Ｑ、または加算因子：Ｄ１＋Ｄ２の算出処理を実行することなく、スカラー倍加算：ｋＰ＋ｌＱ、またはｋＤ１＋ｌＤ２の演算処理を実行するステップであることを特徴とする請求項８に記載の暗号処理方法。
【請求項１１】
楕円曲線暗号において規定される楕円曲線上の２点Ｐ，Ｑ、およびスカラー値ｋ，ｌに基づくスカラー倍加算：ｋＰ＋ｌＱ、または、
超楕円曲線暗号において規定される因子Ｄ１，Ｄ２、およびスカラー値ｋ，ｌに基づくスカラー倍加算：ｋＤ１＋ｌＤ２、
いずれかのスカラー倍加算演算を、暗号処理装置において実行させるコンピュータ・プログラムであり、
スカラー値制御部において実行させるステップであり、
前記スカラー値ｋ，ｌについて、すべてのビットを０，または＋１，または−１で表現し、かつ、スカラー値ｋ，ｌの対応ビット位置のビットの組み合わせ（ｋｉ，ｌｉ）、ただしｉ＝０〜ｎ、の全てを、
（ｋｉ，ｌｉ）＝（０，±１）または（±１，０）
を満足する設定としたＪＲＦ（ジョイント・レギュラーフォーム）表現スカラー値、
ｋ＝＜ｋｎ，・・・ｋ０＞、
ｌ＝＜ｌｎ，・・・ｌ０＞、
を生成するスカラー値制御ステップと、
演算実行部において実行させるステップであり、
前記スカラー値制御部の生成したＪＲＦ表現スカラー値を適用して、スカラー倍加算：ｋＰ＋ｌＱ、またはｋＤ１＋ｌＤ２の演算処理を実行する演算実行ステップと、
を実行させることを特徴とするコンピュータ・プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号処理装置、および暗号処理方法、並びにコンピュータ・プログラムに関する。さらに詳細には、楕円曲線暗号におけるスカラー倍加算点ｋＰ＋ｌＱや超楕円曲線暗号におけるスカラー倍加算因子ｋＤ１＋ｌＤ２の算出の高速化を実現する暗号処理装置、および暗号処理方法、並びにコンピュータ・プログラムに関する。
【背景技術】
【０００２】
昨今、ネットワーク通信、電子商取引の発展に伴い、通信におけるセキュリティ確保が重要な問題となっている。セキュリティ確保の１つの方法が暗号技術であり、現在、様々な暗号化手法を用いた通信が行なわれている。
【０００３】
例えばＩＣカード等の小型の装置中に暗号処理モジュールを埋め込み、ＩＣカードと、データ読み取り書き込み装置としてのリーダライタとの間でデータ送受信を行ない、認証処理、あるいは送受信データの暗号化、復号化を行なうシステムが実用化されている。
【０００４】
暗号処理を実行する例えばＩＣカードは、例えば駅の改札などの様々なゲート、あるいはショッピングセンターなどで盛んに利用されるようになっており、小型化および処理の迅速化の要求が厳しくなってきている。
【０００５】
暗号化方式には、大別して共通鍵方式、公開鍵方式がある。共通鍵方式は、対称暗号方式ともよばれ、発信者、受信者の双方で共通の鍵を保有する。共通鍵方式の代表的な方法として、ＤＥＳ（Data Encryption Standard）がある。ＤＥＳアルゴリズムの特徴は、暗号化と復号化とをほぼ同じアルゴリズムで実行可能なことである。
【０００６】
この共通鍵暗号に対して、発信者と受信者の鍵を異なるものとした構成が公開鍵方式または非対称暗号方式である。公開鍵暗号方式では、暗号化、復号化に共通の鍵を用いる共通鍵暗号方式と異なり、秘密に保つ必要のある秘密鍵は、特定の１人が持てばよいため鍵の管理において有利である。ただし、公開鍵暗号方式は共通鍵暗号方式に比較してデータ処理速度が遅く、一般には、秘密鍵の配送、デジタル署名等のデータ量の少ない対象に多く用いられている。公開鍵暗号方式の代表的なものにはＲＳＡ（Rivest-Shamir-Adleman）暗号や、楕円曲線暗号（ＥＣＣ：Elliptic Curve Cryptography）が知られている。
【０００７】
楕円曲線暗号（Elliptic Curve Cryptography）は、楕円曲線上の離散対数問題の困難性を利用した暗号であり，１６０ｂｉｔで１０２４ｂｉｔのＲＳＡ暗号と等価の安全性をもつと言われる。一般に楕円曲線暗号は、素体上の楕円曲線：ｙ２＝ｘ３＋ａｘ＋ｂ（４ａ３＋２７ｂ２≠０）や、２の拡大体上の楕円曲線：ｙ２＋ｘｙ＝ｘ３＋ａｘ２＋ｂ（ｂ≠０）などを用いる。これらの曲線上の点に無限遠点（Ｏ）を加えた集合は、加法に関して有限群をなし、無限遠点（Ｏ）はその単位元となる。以下、この有限群上の点の加法を＋で表す。
【０００８】
この有限群上の異なる２点Ｐ，Ｑの加算Ｐ＋Ｑを「点の加算」、
点Ｐと点Ｐの加算Ｐ＋Ｐ＝２Ｐを「点の２倍算」
と呼ぶ。
また、点Ｐをｋ回加算した点Ｐ＋Ｐ＋…＋Ｐ＝ｋＰを求める演算を「点のスカラー倍算」と呼ぶ。なお、楕円曲線暗号上の演算に関しては、例えば非特許文献１に記されている。
【０００９】
また、楕円曲線上の異なる２点Ｐ，Ｑのスカラー倍点の加算点ｋＰ＋ｌＱを高速に計算する「点のスカラー倍同時計算法」が知られている。ｋ，ｌはスカラー量である。
点のスカラー倍同時計算のアルゴリズムは、スカラー量ｋ，ｌについて、それぞれ、
ｋ＝（ｋｎ・・・ｋ０）２、
ｌ＝（ｌｎ・・・ｌ０）２、
とした２進表現として、以下のようなアルゴリズムを適用して実行される。
【００１０】
［点のスカラー倍同時計算のアルゴリズム］
Ｉｎｐｕｔ：楕円曲線上の点Ｐ，Ｑ  スカラー値ｋ，ｌ
Ｏｕｔｐｕｔ:ｋＰ＋ｌＱ
１．Ｃｏｍｐｕｔｅ  Ｐ＋Ｑ
２．Ｔ←（ｋｎＰ＋ｌｎＱ）
３．Ｆｏｒ  ｉ＝ｎ−１  ｄｏｗｎｔｏ  ０  ｄｏ
Ｔ←２Ｔ
Ｉｆ  （ｋｉ，ｌｉ）≠（０，０）  ｔｈｅｎ
Ｔ←Ｔ＋（ｋｉＰ＋ｌｉＱ）
４．Ｒｅｔｕｒｎ  Ｔ
【００１１】
上記の［点のスカラー倍同時計算のアルゴリズム］では、各点Ｐ，Ｑの個々のスカラー倍としてのｋＰ，ｌＱを単独に計算するものではなく、２進表現スカラー量の対応ビット（ｋｉ，ｌｉ）の条件に基づいて、ｋＰ＋ｌＱを同時に計算する手法である。この手法は、それぞれ点Ｐ，Ｑのスカラー倍算ｋＰまたはｌＱを算出してからｋＰ＋ｌＱを点の加算処理として実行するよりも、点の２倍算の回数を約半分に減らすことができ、高速化を実現している。
【００１２】
楕円曲線上の離散対数問題の困難性の一方で、楕円曲線暗号処理中のデバイスの消費電力を測定することによりデバイス内部に格納された秘密情報を暴く電力解析攻撃と呼ばれる攻撃法が提案されている。電力解析攻撃には、主に一回の消費電力波形を利用する単純電力解析（Ｓｉｍｐｌｅ  Ｐｏｗｅｒ  Ａｎａｌｙｓｉｓ，ＳＰＡ）と複数の消費電力波形の差分を利用する差分電力解析（Ｄｉｆｆｅｒｅｎｔｉａｌ  Ｐｏｗｅｒ  Ａｎａｌｙｓｉｓ，ＤＰＡ）が存在する。楕円曲線暗号に対する電力解析攻撃については、例えば非特許文献２に示されている。一般に、楕円曲線暗号におけるＤＰＡ対策は、ＳＰＡ対策にランダム化手法を組み合わせることにより実現される。
【００１３】
しかし、上記の［点のスカラー倍同時計算アルゴリズム］は、ＳＰＡに対して安全ではない。点の２倍算と点の加算の演算は異なる処理として実行されるため、演算中の消費電力の特徴は異なる。そのため、攻撃者は消費電力波形を見ることにより点の２倍算を行なっているか点の加算を行なっているかを区別することができる。
【００１４】
上記の［点のスカラー倍同時計算アルゴリズム］におけるステップ３において、
Ｔ←２Ｔの点の２倍算は全てのｉに対して行なうのに対して、
Ｔ←Ｔ＋（ｋｉＰ＋ｌｉＱ）の点の加算は（ｋｉ，ｌｉ）≠（０，０）の場合にのみ行なう。従って、攻撃者は（ｋｉ，ｌｉ）＝（０，０）であるか否かについて、消費電力波形を見ることにより判別することができる。また、上記の［点のスカラー倍同時計算アルゴリズム］においては、ステップ１においてＰ＋Ｑの点の加算を行なうという前計算が必要となる。
【非特許文献１】D. Hankerson, J.L. Hernandez, and A. Menezes, "Software Implementation of Elliptic Curve Cryptography over Binary Fields", Cryptographic Hardware and Embedded Systems - CHES 2000, LNCS 1965, pp.1-24, Springer-Verlag, 2000.
【非特許文献２】J.-S. Coron, "Resistance against Differential Power Analysis for Elliptic Curve Cryptosystems",Cryptographic Hardware and Embedded Systems - CHES'99, LNCS 1965, pp.292-302, Springer-Verlag, 1999.
【発明の開示】
【発明が解決しようとする課題】
【００１５】
本発明は、楕円曲線暗号におけるスカラー倍加算点ｋＰ＋ｌＱや、楕円曲線暗号を一般化した方式として知られる超楕円曲線暗号におけるスカラー倍加算因子ｋＤ１＋ｌＤ２の算出の高速化を実現し、さらに、単純電力解析（Ｓｉｍｐｌｅ  Ｐｏｗｅｒ  Ａｎａｌｙｓｉｓ，ＳＰＡ）などの攻撃に対する耐性を持つスカラー倍点の加算点の計算を実現する暗号処理装置、および暗号処理方法、並びにコンピュータ・プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１６】
本発明の第１の側面は、
楕円曲線暗号において規定される楕円曲線上の２点Ｐ，Ｑ、およびスカラー値ｋ，ｌに基づくスカラー倍加算：ｋＰ＋ｌＱ、または、
超楕円曲線暗号において規定される因子Ｄ１，Ｄ２、およびスカラー値ｋ，ｌに基づくスカラー倍加算：ｋＤ１＋ｌＤ２、
いずれかのスカラー倍加算演算を実行する暗号処理装置であり、
前記スカラー値ｋ，ｌについて、すべてのビットを０，または＋１，または−１で表現し、かつ、スカラー値ｋ，ｌの対応ビット位置のビットの組み合わせ（ｋｉ，ｌｉ）、ただしｉ＝０〜ｎ、の全てを、
（ｋｉ，ｌｉ）＝（０，±１）または（±１，０）
を満足する設定としたＪＲＦ（ジョイント・レギュラーフォーム）表現スカラー値、
ｋ＝＜ｋｎ，・・・ｋ０＞、
ｌ＝＜ｌｎ，・・・ｌ０＞、
を生成するスカラー値制御部と、
前記スカラー値制御部の生成したＪＲＦ表現スカラー値を適用して、スカラー倍加算：ｋＰ＋ｌＱ、またはｋＤ１＋ｌＤ２の演算処理を実行する演算実行部と、
を有することを特徴とする暗号処理装置にある。
【００１７】
さらに、本発明の暗号処理装置の一実施態様において、前記スカラー値制御部は、スカラー値ｋ，ｌが、両者とも偶数、または両者とも奇数である場合、いずれか一方のスカラー値の値を変更して、偶数と奇数の組み合わせに設定し、変更したスカラー値ｋ，ｌについて、対応ビット位置のビットの組み合わせ（ｋｉ，ｌｉ）が、
（ｋｉ，ｌｉ）＝（０，±１）または（±１，０）
を満足するＪＲＦ（ジョイント・レギュラーフォーム）表現スカラー値、
ｋ＝＜ｋｎ，・・・ｋ０＞、
ｌ＝＜ｌｎ，・・・ｌ０＞、
を生成する処理を実行する構成であり、
前記演算実行部は、前記変更スカラー値に基づくスカラー倍加算：ｋＰ＋ｌＱ、またはｋＤ１＋ｌＤ２の演算処理を実行し、さらに、補正計算を実行して、変更前のスカラー値を適用したスカラー倍加算結果を算出する処理を実行する構成であることを特徴とする。
【００１８】
さらに、本発明の暗号処理装置の一実施態様において、前記演算実行部は、前記ＪＲＦ表現スカラー値、
ｋ＝＜ｋｎ，・・・ｋ０＞、
ｌ＝＜ｌｎ，・・・ｌ０＞、
の対応ビット（ｋｉ，ｌｉ）を選択し、スカラー倍加算：ｋＰ＋ｌＱ、またはｋＤ１＋ｌＤ２の計算に際して、ｋＰとｌＱ、またはｋＤ１とｌＤ２を同時に計算する同時計算手法を適用した演算を実行する構成であることを特徴とする。
【００１９】
さらに、本発明の暗号処理装置の一実施態様において、前記演算実行部は、前記ＪＲＦ表現スカラー値、
ｋ＝＜ｋｎ，・・・ｋ０＞、
ｌ＝＜ｌｎ，・・・ｌ０＞、
の対応ビット（ｋｉ，ｌｉ）のすべてについて、
Ｔ←（ｋｎＰ＋ｌｎＱ）、または、Ｔ←ｋｎＤ１＋ｌｎＤ２、
上記Ｔの算出処理を同じ計算アルゴリズムに従って実行する構成であることを特徴とする。
【００２０】
さらに、本発明の暗号処理装置の一実施態様において、前記演算実行部は、演算処理において、加算点：Ｐ＋Ｑ、または加算因子：Ｄ１＋Ｄ２の算出処理を実行することなく、スカラー倍加算：ｋＰ＋ｌＱ、またはｋＤ１＋ｌＤ２の演算処理を実行する構成であることを特徴とする。
【００２１】
さらに、本発明の第２の側面は、
楕円曲線暗号において規定される楕円曲線上の２点Ｐ，Ｑ、およびスカラー値ｋ，ｌに基づくスカラー倍加算：ｋＰ＋ｌＱ、または、
超楕円曲線暗号において規定される因子Ｄ１，Ｄ２、およびスカラー値ｋ，ｌに基づくスカラー倍加算：ｋＤ１＋ｌＤ２、
いずれかのスカラー倍加算演算を、暗号処理装置において実行する暗号処理方法であり、
スカラー値制御部における実行ステップであり、
前記スカラー値ｋ，ｌについて、すべてのビットを０，または＋１，または−１で表現し、かつ、スカラー値ｋ，ｌの対応ビット位置のビットの組み合わせ（ｋｉ，ｌｉ）、ただしｉ＝０〜ｎ、の全てを、
（ｋｉ，ｌｉ）＝（０，±１）または（±１，０）
を満足する設定としたＪＲＦ（ジョイント・レギュラーフォーム）表現スカラー値、
ｋ＝＜ｋｎ，・・・ｋ０＞、
ｌ＝＜ｌｎ，・・・ｌ０＞、
を生成するスカラー値制御ステップと、
演算実行部における実行ステップであり、
前記スカラー値制御部の生成したＪＲＦ表現スカラー値を適用して、スカラー倍加算：ｋＰ＋ｌＱ、またはｋＤ１＋ｌＤ２の演算処理を実行する演算実行ステップと、
を有することを特徴とする暗号処理方法にある。
【００２２】
さらに、本発明の暗号処理方法の一実施態様において、前記スカラー値制御ステップは、スカラー値ｋ，ｌが、両者とも偶数、または両者とも奇数である場合、いずれか一方のスカラー値の値を変更して、偶数と奇数の組み合わせに設定し、変更したスカラー値ｋ，ｌについて、対応ビット位置のビットの組み合わせ（ｋｉ，ｌｉ）が、
（ｋｉ，ｌｉ）＝（０，±１）または（±１，０）
を満足するＪＲＦ（ジョイント・レギュラーフォーム）表現スカラー値、
ｋ＝＜ｋｎ，・・・ｋ０＞、
ｌ＝＜ｌｎ，・・・ｌ０＞、
を生成する処理を実行するステップであり、
前記演算実行ステップは、
前記変更スカラー値に基づくスカラー倍加算：ｋＰ＋ｌＱ、またはｋＤ１＋ｌＤ２の演算処理を実行し、さらに、補正計算を実行して、変更前のスカラー値を適用したスカラー倍加算結果を算出する処理を実行するステップであることを特徴とする。
【００２３】
さらに、本発明の暗号処理方法の一実施態様において、前記演算実行ステップは、前記ＪＲＦ表現スカラー値、
ｋ＝＜ｋｎ，・・・ｋ０＞、
ｌ＝＜ｌｎ，・・・ｌ０＞、
の対応ビット（ｋｉ，ｌｉ）を選択し、スカラー倍加算：ｋＰ＋ｌＱ、またはｋＤ１＋ｌＤ２の計算に際して、ｋＰとｌＱ、またはｋＤ１とｌＤ２を同時に計算する同時計算手法を適用した演算を実行するステップであることを特徴とする。
【００２４】
さらに、本発明の暗号処理方法の一実施態様において、前記演算実行ステップは、前記ＪＲＦ表現スカラー値、
ｋ＝＜ｋｎ，・・・ｋ０＞、
ｌ＝＜ｌｎ，・・・ｌ０＞、
の対応ビット（ｋｉ，ｌｉ）のすべてについて、
Ｔ←（ｋｎＰ＋ｌｎＱ）、または、Ｔ←ｋｎＤ１＋ｌｎＤ２、
上記Ｔの算出処理を同じ計算アルゴリズムに従って実行するステップであることを特徴とする。
【００２５】
さらに、本発明の暗号処理方法の一実施態様において、前記演算実行ステップは、演算処理において、加算点：Ｐ＋Ｑ、または加算因子：Ｄ１＋Ｄ２の算出処理を実行することなく、スカラー倍加算：ｋＰ＋ｌＱ、またはｋＤ１＋ｌＤ２の演算処理を実行するステップであることを特徴とする。
【００２６】
さらに、本発明の第３の側面は、
楕円曲線暗号において規定される楕円曲線上の２点Ｐ，Ｑ、およびスカラー値ｋ，ｌに基づくスカラー倍加算：ｋＰ＋ｌＱ、または、
超楕円曲線暗号において規定される因子Ｄ１，Ｄ２、およびスカラー値ｋ，ｌに基づくスカラー倍加算：ｋＤ１＋ｌＤ２、
いずれかのスカラー倍加算演算を、暗号処理装置において実行させるコンピュータ・プログラムであり、
スカラー値制御部において実行させるステップであり、
前記スカラー値ｋ，ｌについて、すべてのビットを０，または＋１，または−１で表現し、かつ、スカラー値ｋ，ｌの対応ビット位置のビットの組み合わせ（ｋｉ，ｌｉ）、ただしｉ＝０〜ｎ、の全てを、
（ｋｉ，ｌｉ）＝（０，±１）または（±１，０）
を満足する設定としたＪＲＦ（ジョイント・レギュラーフォーム）表現スカラー値、
ｋ＝＜ｋｎ，・・・ｋ０＞、
ｌ＝＜ｌｎ，・・・ｌ０＞、
を生成するスカラー値制御ステップと、
演算実行部において実行させるステップであり、
前記スカラー値制御部の生成したＪＲＦ表現スカラー値を適用して、スカラー倍加算：ｋＰ＋ｌＱ、またはｋＤ１＋ｌＤ２の演算処理を実行する演算実行ステップと、
を実行させることを特徴とするコンピュータ・プログラムにある。
【００２７】
なお、本発明のコンピュータ・プログラムは、例えば、様々なプログラム・コードを実行可能なコンピュータ・システムに対して、コンピュータ可読な形式で提供する記憶媒体、通信媒体、例えば、ＣＤやＦＤ、ＭＯなどの記録媒体、あるいは、ネットワークなどの通信媒体によって提供可能なコンピュータ・プログラムである。このようなプログラムをコンピュータ可読な形式で提供することにより、コンピュータ・システム上でプログラムに応じた処理が実現される。
【００２８】
本発明のさらに他の目的、特徴や利点は、後述する本発明の実施例や添付する図面に基づくより詳細な説明によって明らかになるであろう。なお、本明細書においてシステムとは、複数の装置の論理的集合構成であり、各構成の装置が同一筐体内にあるものには限らない。
【発明の効果】
【００２９】
本発明の構成によれば、楕円曲線暗号において規定される楕円曲線上の２点Ｐ，Ｑ、およびスカラー値ｋ，ｌに基づくスカラー倍加算：ｋＰ＋ｌＱ、または、超楕円曲線暗号において規定される因子Ｄ１，Ｄ２、およびスカラー値ｋ，ｌに基づくスカラー倍加算：ｋＤ１＋ｌＤ２、これらの演算処理において、スカラー値ｋ，ｌについて、すべてのビットを０，または＋１，または−１で表現し、かつ、スカラー値ｋ，ｌの対応ビット位置のビットの組み合わせ（ｋｉ，ｌｉ）を、
（ｋｉ，ｌｉ）＝（０，±１）または（±１，０）
を満足する設定としたＪＲＦ（ジョイント・レギュラーフォーム）表現スカラー値、
ｋ＝＜ｋｎ，・・・ｋ０＞、
ｌ＝＜ｌｎ，・・・ｌ０＞、
を生成し、このＪＲＦ表現のスカラー値を適用してスカラー倍加算：ｋＰ＋ｌＱ、またはｋＤ１＋ｌＤ２の演算処理を実行する構成としたので、（ｋｉ，ｌｉ）のすべての組み合わせにおいて同一の演算処理シーケンスを実行可能となり、ビットの組み合わせに応じた処理の差異がなくなり電力解析に対する耐性が向上し、また、Ｐ＋ＱやＤ１＋Ｄ２の事前計算の省略が可能となり演算処理の高速化が実現される。
【発明を実施するための最良の形態】
【００３０】
以下、本発明の暗号処理装置、および暗号処理方法、並びにコンピュータ・プログラムの詳細について説明する。説明は、以下の項目に従って行なう。
（１）楕円曲線暗号、および超楕円曲線暗号の概要
（２）本発明の暗号処理装置の具体的構成および処理例
（３）暗号処理装置の構成例
【００３１】
［（１）楕円曲線暗号、および超楕円曲線暗号の概要］
本発明は、楕円曲線暗号や、楕円曲線暗号を一般化した方式として知られる超楕円曲線暗号におけるスカラー倍点の加算点ｋＰ＋ｌＱの算出の高速化を実現し、さらに、単純電力解析（Ｓｉｍｐｌｅ  Ｐｏｗｅｒ  Ａｎａｌｙｓｉｓ，ＳＰＡ）などの攻撃に対する耐性を持つスカラー倍点の加算点の計算を実現する。まず、楕円曲線暗号、および超楕円曲線暗号の概要について説明する。
【００３２】
前述したように、楕円曲線暗号（Elliptic Curve Cryptography）は、楕円曲線上の離散対数問題の困難性を利用した暗号であり，１６０ｂｉｔで１０２４ｂｉｔのＲＳＡ暗号と等価の安全性をもつと言われる。一般に楕円曲線暗号は、素体上の楕円曲線：ｙ２＝ｘ３＋ａｘ＋ｂ（４ａ３＋２７ｂ２≠０）や、２の拡大体上の楕円曲線：ｙ２＋ｘｙ＝ｘ３＋ａｘ２＋ｂ（ｂ≠０）などを用いる。
【００３３】
一方、楕円曲線暗号を一般化した超楕円曲線暗号（ＨＥＣＣ：Hyper Elliptic Curve Cryptography）は、Koblitz、Cantorによって提案された方式である。有限体をＦｑ（ただしｑ＝ｐｎ，ｐは素数）とする楕円曲線暗号（ＥＣＣ）では有限体Ｆｑ上で定義される楕円曲線上の点をＰとし、スカラー倍算した点ｋＰ（ｋ∈Ｚ）をＱとすると、Ｑからｋを求める問題は離散対数問題に帰着できる。一方、超楕円曲線暗号（ＨＥＣＣ）では点の形式的和である因子（ｄｉｖｉｓｏｒ）をＤ１とし、スカラー倍算ｋＤ１で定義される因子をＤ２とすると、Ｄ２からｋを求める問題は超楕円曲線におけるヤコビ多様体上の離散対数問題となり、その数学的解法の困難性が存在する。このように超楕円曲線暗号（ＨＥＣＣ）は、数学的な解読困難性の存在が確認されており公開鍵暗号の有効な暗号方式として期待されている。
【００３４】
超楕円曲線では曲線を特徴づける値は種数（ｇｅｎｕｓ）ｇである。このとき有限体Ｆｑ上で定義される種数ｇの超楕円曲線Ｃは以下の方程式、
ｙ２＋ｈ（ｘ）ｙ＝ｆ（ｘ）
で定義される。ここで、ｈ（ｘ），ｆ（ｘ）∈Ｆｑ［ｘ］，ｆ（ｘ）は、高々、次数ｇの多項式（ｐが奇素数の場合はｈ＝０）、ｆ（ｘ）は、次数２ｇ＋１のｍｏｎｉｃ多項式である。
【００３５】
超楕円曲線暗号の定義体の演算サイズ（ビット長）は楕円曲線暗号と同等の安全性を仮定した場合、Ｈａｓｓｅの定理より、楕円曲線の定義体の演算サイズに比べて１／ｇに小さくなることが導かれる。演算サイズが小さいことは実装上メリットがあり、超楕円曲線暗号の利点の一つして挙げられる。
【００３６】
本発明は、上述した楕円曲線暗号や、超楕円曲線暗号において、高速にかつ、単純電力解析（ＳＰＡ）などの攻撃に対する耐性を持つ演算として、楕円曲線暗号においては、楕円曲線上の点Ｐ，Ｑについてのスカラー倍点の加算点ｋＰ＋ｌＱの算出、超楕円曲線暗号においては、点の形式的和である因子（ｄｉｖｉｓｏｒ）であるＤ１，Ｄ２についてのスカラー倍因子の加算因子ｋＤ１＋ｌＤ２の算出を実現する。
【００３７】
［（２）本発明の暗号処理装置の具体的構成および処理例］
以下、本発明の暗号処理装置の具体的構成および処理例について説明する。図１を参照して、本発明の暗号処理装置における楕円曲線暗号におけるスカラー倍点の加算点ｋＰ＋ｌＱ、または超楕円曲線暗号における因子Ｄ１，Ｄ２についてのスカラー倍因子の加算因子ｋＤ１＋ｌＤ２の算出を行なう暗号処理部１００の構成例について説明する。なお、
Ｐ，Ｑは、楕円曲線上の２点、
Ｄ１，Ｄ２は、超楕円曲線における点の形式的和である因子（ｄｉｖｉｓｏｒ）、
ｋ，ｌは、スカラー量、
である。
【００３８】
図１に示すように、本発明の暗号処理装置において、楕円曲線暗号おけるスカラー倍点の加算点ｋＰ＋ｌＱ、または超楕円曲線暗号におけるスカラー倍因子の加算因子ｋＤ１＋ｌＤ２の算出を行なう暗号処理部１００は、スカラー値制御部１０１と、演算実行部１０２を有する。なお、以下では、楕円曲線暗号におけるスカラー倍点の加算点ｋＰ＋ｌＱの算出処理例を実施例として説明する。超楕円曲線暗号におけるスカラー倍因子の加算因子ｋＤ１＋ｌＤ２の算出も、ｋＰ＋ｌＱの算出処理と同様に実行可能である。
【００３９】
スカラー値制御部１０１は、スカラー倍点の加算点ｋＰ＋ｌＱの算出に適用するスカラー値ｋ，ｌを入力し、スカラー値ｋ，ｌが偶数であるか奇数であるかを判定し、スカラー値ｋ，ｌの偶奇が異なる場合に、
（ｋｉ，ｌｉ）＝（０，±１）または（±１，０）
を満たす０，１，−１の数列ｋ＝〈ｋｎ・・・ｋ０〉，ｌ＝〈ｌｎ・・・ｌ０〉で表現する。
【００４０】
先に説明した従来の「点のスカラー倍同時計算法」では、スカラー値ｋ，ｌについて、それぞれ、
ｋ＝（ｋｎ・・・ｋ０）２、
ｌ＝（ｌｎ・・・ｌ０）２、
とした２進表現として、以下のアルゴリズムを適用してｋＰ＋ｌＱの算出が実行されていた。
【００４１】
［点のスカラー倍同時計算のアルゴリズム］
Ｉｎｐｕｔ：楕円曲線上の点Ｐ，Ｑ  スカラー値ｋ，ｌ
Ｏｕｔｐｕｔ:ｋＰ＋ｌＱ
１．Ｃｏｍｐｕｔｅ  Ｐ＋Ｑ
２．Ｔ←（ｋｎＰ＋ｌｎＱ）
３．Ｆｏｒ  ｉ＝ｎ−１  ｄｏｗｎｔｏ  ０  ｄｏ
Ｔ←２Ｔ
Ｉｆ  （ｋｉ，ｌｉ）≠（０，０）  ｔｈｅｎ
Ｔ←Ｔ＋（ｋｉＰ＋ｌｉＱ）
４．Ｒｅｔｕｒｎ  Ｔ
【００４２】
すなわち、従来の構成では、スカラー値ｋ，ｌについて、それぞれ、
ｋ＝（ｋｎ・・・ｋ０）２、
ｌ＝（ｌｎ・・・ｌ０）２、
とした２進表現、すなわち、
（ｋｉ，ｌｉ）＝（０，０）または（０，１）または（１，０）または（１，１）
の２進表現を設定して、上記の［点のスカラー倍同時計算のアルゴリズム］を実行していた。
【００４３】
本発明の暗号処理においては、スカラー値制御部１０１は、スカラー倍点の加算点ｋＰ＋ｌＱの算出に適用するスカラー値ｋ，ｌを入力し、スカラー値ｋ，ｌが偶数であるか奇数であるかを判定し、スカラー値ｋ，ｌの偶奇が異なる場合に、
（ｋｉ，ｌｉ）＝（０，±１）または（±１，０）
を満たすように、スカラー値ｋおよびｌをそれぞれ０，１，−１の数列とした拡張２進表現に変換する。この拡張２進表現を、
ｋ＝〈ｋｎ・・・ｋ０〉，
ｌ＝〈ｌｎ・・・ｌ０〉
として示す。
【００４４】
スカラー値：ｋ，ｌの拡張２進表現において、対応するビット、すなわち、（ｋｉ，ｌｉ）は、
（ｋｉ，ｌｉ）＝（０，±１）または（±１，０）
の条件を満たすように設定する。
この条件を満足するｋ，ｌの表現を、以下では、ジョイント・レギュラーフォーム（ＪＲＦ：Ｊｏｉｎｔ Ｒｅｇｕｌａｒ Ｆｏｒｍ）と呼ぶ。
【００４５】
本発明の暗号処理においては、スカラー値制御部１０１は、スカラー値ｋ，ｌの偶奇を判定し、スカラー値ｋ，ｌの偶奇が異なる場合、すなわち、
（ａ）スカラー値ｋが偶数、スカラー値ｌが奇数、または、
（ｂ）スカラー値ｋが奇数、スカラー値ｌが偶数、
上記（ａ），（ｂ）いずれかの場合に、
（ｋｉ，ｌｉ）＝（０，±１）または（±１，０）
を満たす０，１，−１の数列ｋ＝〈ｋｎ・・・ｋ０〉，ｌ＝〈ｌｎ・・・ｌ０〉で表現し、これを図１に示す演算実行部１０２に入力し、演算実行部１０２は、前述の［点のスカラー倍同時計算のアルゴリズム］に従って、点のスカラー倍加算点ｋＰ＋ｌＱの算出を実行する。
【００４６】
演算実行部１０２は、以下の［点のスカラー倍同時計算のアルゴリズム］を実行する。
［点のスカラー倍同時計算のアルゴリズム］
Ｉｎｐｕｔ：楕円曲線上の点Ｐ，Ｑ  スカラー値ｋ，ｌ
Ｏｕｔｐｕｔ:ｋＰ＋ｌＱ
１．Ｃｏｍｐｕｔｅ  Ｐ＋Ｑ
２．Ｔ←（ｋｎＰ＋ｌｎＱ）
３．Ｆｏｒ  ｉ＝ｎ−１  ｄｏｗｎｔｏ  ０  ｄｏ
Ｔ←２Ｔ
Ｉｆ  （ｋｉ，ｌｉ）≠（０，０）  ｔｈｅｎ
Ｔ←Ｔ＋（ｋｉＰ＋ｌｉＱ）
４．Ｒｅｔｕｒｎ  Ｔ
【００４７】
しかし、
（ｋｉ，ｌｉ）＝（０，±１）または（±１，０）
の設定であるので、上記のアルゴリズムにおけるステップ３の処理において、
（ｋｉ，ｌｉ）＝（０，０）となることはなく、すべての（ｋｉ，ｌｉ）について、ステップ３では、
Ｔ←２Ｔ
Ｔ←Ｔ＋（ｋｉＰ＋ｌｉＱ）
これらの処理を実行することになる。すなわち、全ての（ｉ）すなわち拡張２進表現のなされたｋ，ｌの各ビットについて、すべて同一の処理が実行される。
【００４８】
この結果、電力解析を実行しても、（ｋｉ，ｌｉ）＝（０，０）であるか否かに応じて、処理が異なっていた従来シーケンスと異なり、すべての（ｋｉ，ｌｉ）の組について、同一の処理が実行され、ＳＰＡ等の電力解析による処理の判別が不可能となり、電力解析に対する耐性の高い暗号処理が実現される。
【００４９】
さらに、ステップ３で実行される処理中の、
Ｔ←Ｔ＋（ｋｉＰ＋ｌｉＱ）
この算出処理において、
（ｋｉ，ｌｉ）＝（０，±１）または（±１，０）
の設定であるので、
Ｔ←Ｔ＋（ｋｉＰ＋ｌｉＱ）
における（ｋｉＰ＋ｌｉＱ）の計算では、
（０＊Ｐ）＋（（＋１）＊Ｑ）＝Ｑ
（０＊Ｐ）＋（（−１）＊Ｑ）＝−Ｑ
（（＋１）＊Ｐ）＋（０＊Ｑ）＝Ｐ
（（−１）＊Ｐ）＋（０＊Ｑ）＝−Ｐ
上記４種類の計算のみが発生することになり、結果として、Ｐ，−Ｐ，Ｑ，−Ｑの４つの値を算出するのみでよい。
【００５０】
これは、前述の［点のスカラー倍同時計算のアルゴリズム］におけるステップ１の事前計算処理、すなわち、
１．Ｃｏｍｐｕｔｅ  Ｐ＋Ｑ
この計算処理ステップが、省略可能となることを意味する。
このステップ１の［Ｐ＋Ｑ］の算出処理は、［Ｐ＋Ｑ］の値を事前に算出することで、ステップ３において、Ｐ＋Ｑを算出する必要が発生した場合に、算出済みの値を適用可能とするための算出ステップである。従来のシーケンスでは、ステップ３における処理、すなわち、
Ｔ←Ｔ＋（ｋｉＰ＋ｌｉＱ）
この算出処理において、
（ｋｉ，ｌｉ）＝（１，１）
の組み合わせが発生することがあり、この組み合わせが発生した場合に、ステップ１での事前計算値を適用する設定としていた。
【００５１】
しかし、本処理例では、
（ｋｉ，ｌｉ）＝（０，±１）または（±１，０）
の設定であるので、
Ｔ←Ｔ＋（ｋｉＰ＋ｌｉＱ）
における（ｋｉＰ＋ｌｉＱ）の計算では、Ｐ，−Ｐ，Ｑ，−Ｑの４つの値のみが発生し、Ｐ＋Ｑを算出する処理が必要なビットの組み合わせ（ｋｉ，ｌｉ）＝（１，１）は発生しない。この結果、ステップ１での［Ｐ＋Ｑ］の事前計算処理が不要となり、処理ステップを１つ削減することが可能となり、演算の高速化が実現される。
【００５２】
このように、本発明の処理例に従って、［点のスカラー倍同時計算のアルゴリズム］を実行する場合、入力スカラー値が偶数、奇数の組み合わせである場合、
（ｋｉ，ｌｉ）＝（０，±１）または（±１，０）
のジョイント・レギュラーフォーム（ＪＲＦ：Ｊｏｉｎｔ Ｒｅｇｕｌａｒ Ｆｏｒｍ）に表現を設定して、［点のスカラー倍同時計算のアルゴリズム］を実行させることで、［点のスカラー倍同時計算のアルゴリズム］において、
（ａ）ステップ３の処理が、（ｋｉ，ｌｉ）のすべての組み合わせにおいて、すべて同一の処理として実行される。
（ｂ）ステップ１の処理が省略できる。
上記（ａ），（ｂ）が実現されることになり、電力解析に対する耐性が向上し、演算の高速化が図られることになる。
【００５３】
なお、本発明の処理例では、図１に示すスカラー値制御部１０１において、入力スカラー値が偶数、奇数の組み合わせである場合、
（ｋｉ，ｌｉ）＝（０，±１）または（±１，０）
上記のジョイント・レギュラーフォーム（ＪＲＦ：Ｊｏｉｎｔ Ｒｅｇｕｌａｒ Ｆｏｒｍ）に表現を設定して、演算実行部１０２に出力して、上述の［点のスカラー倍同時計算のアルゴリズム］を実行させる。
【００５４】
図１に示すスカラー値制御部１０１における処理、すなわち、ジョイント・レギュラーフォーム（ＪＲＦ：Ｊｏｉｎｔ Ｒｅｇｕｌａｒ Ｆｏｒｍ）の設定処理について、以下説明する。例えば、入力スカラー値ｋ，ｌが、
（ｋ，ｌ）＝（５２，３９）
である場合、ｋ，およびｌを（０，＋１，−１）の拡張２進表現に設定するともに、
（ｋｉ，ｌｉ）＝（０，±１）または（±１，０）
の関係となるジョイント・レギュラーフォーム（ＪＲＦ：Ｊｏｉｎｔ Ｒｅｇｕｌａｒ Ｆｏｒｍ）に表現を設定すると、
ｋ＝５２＝＜１，０，−１，０，１，０，０＞
ｌ＝３９＝＜０，１，０，１，０，−１，１＞
となる。
【００５５】
以下、偶奇が異なるスカラー値ｋ，ｌのジョイント・レギュラーフォーム（ＪＲＦ：Ｊｏｉｎｔ Ｒｅｇｕｌａｒ Ｆｏｒｍ）を、
（ｋ０，ｌ０），・・・，（ｋｎ，ｌｎ）と下位から生成する方法について説明する。
【００５６】
図１に示すスカラー値制御部１０１は、スカラー値ｋ，ｌを入力し、これらのスカラー値の偶奇判定を実行し、ｋ，ｌが偶数と奇数の組み合わせである場合に、ｋ，ｌの２進表現から、スカラー値ｋ，ｌのジョイント・レギュラーフォーム（ＪＲＦ：Ｊｏｉｎｔ Ｒｅｇｕｌａｒ Ｆｏｒｍ）を生成する。
【００５７】
スカラー値ｋ，ｌの２進表現を、
ｋ＝（ｋｎ・・・ｋ０）２、
ｌ＝（ｌｎ・・・ｌ０）２、
とする。スカラー値制御部１０１は、この２進表現に基づいて、スカラー値ｋ，ｌのジョイント・レギュラーフォーム（ＪＲＦ：Ｊｏｉｎｔ Ｒｅｇｕｌａｒ Ｆｏｒｍ）を生成する。
【００５８】
まず、ｋ，ｌは偶奇が異なるデータであり、必然的に、スカラー値ｋ，ｌの２進表現の最下位ビットの組み合わせ（ｋ０，ｌ０）は、
（ｋ０，ｌ０）＝（０，１）、または、
（ｋ０，ｌ０）＝（１，０）
である。
【００５９】
スカラー値制御部１０１は、まず、スカラー値ｋ，ｌの２進表現の最下位から２番目のビット、（ｋ１，ｌ１）に注目し、（ｋ１，ｌ１）の値に基づいて、変換処理を実行する。
（ｋ１，ｌ１）＝（０，１）または（１，０）の場合には変換を行なわない。すなわち、ジョイント・レギュラーフォーム（ＪＲＦ）の条件である、
（ｋｉ，ｌｉ）＝（０，±１）または（±１，０）
この条件を満足するので、２進表現の（ｋ１，ｌ１）をそのまま、ＪＲＦにおける（ｋ１，ｌ１）とする。
【００６０】
一方、２進表現の（ｋ１，ｌ１）が、
（ｋ１，ｌ１）＝（０，０）である場合は、ジョイント・レギュラーフォーム（ＪＲＦ）の条件である、
（ｋｉ，ｌｉ）＝（０，±１）または（±１，０）
この条件を満足していないので、表現を変更する。この場合、スカラー値制御部１０１は、スカラー値ｋの２進表現の最下位ビットｋ０の値に応じて、スカラー値ｋ，ｌの２進表現の最下位ビットおよび最下位から２番目のビット、［ｋ１，ｋ０］と、［ｌ１，ｌ０］を以下のように変換して、ＪＲＦにおける（ｋ１，ｌ１）および（ｋ０，ｌ０）を設定する。
【００６１】
ｋ０＝１の場合、すなわち、
（ｋ１，ｌ１）＝（０，０）、
（ｋ０，ｌ０）＝（１，０）のときは、
２進表現［ｋ１，ｋ０］＝［０，１］→ＪＲＦ表現［ｋ１，ｋ０］＝［１，−１］
２進表現［ｌ１，ｌ０］＝［０，０］→ＪＲＦ表現［ｌ１，ｌ０］＝［０，０］
とする変換処理を実行して、ｋ，ｌのＪＲＦ表現を設定する。
【００６２】
ｋ０＝０の場合、すなわち、
（ｋ１，ｌ１）＝（０，０）、
（ｋ０，ｌ０）＝（０，１）のときは、
２進表現［ｋ１，ｋ０］＝［０，０］→ＪＲＦ表現［ｋ１，ｋ０］＝［０，０］
２進表現［ｌ１，ｌ０］＝［０，１］→ＪＲＦ表現［ｌ１，ｌ０］＝［１，−１］
とする変換処理を実行して、ｋ，ｌのＪＲＦ表現を設定する。
【００６３】
また、２進表現の（ｋ１，ｌ１）が、
（ｋ１，ｌ１）＝（１，１）である場合も、ジョイント・レギュラーフォーム（ＪＲＦ）の条件である、
（ｋｉ，ｌｉ）＝（０，±１）または（±１，０）
この条件を満足していないので、表現を変更する。この場合、スカラー値制御部１０１は、スカラー値ｋの２進表現の最下位ビットｋ０の値に応じて、スカラー値ｋ，ｌの２進表現の最下位ビットおよび最下位から２番目のビット、［ｋ１，ｋ０］と、［ｌ１，ｌ０］を以下のように変換して、ＪＲＦにおける（ｋ１，ｌ１）および（ｋ０，ｌ０）を設定する。
【００６４】
ｋ０＝１の場合、すなわち、
（ｋ１，ｌ１）＝（１，１）、
（ｋ０，ｌ０）＝（１，０）のときは、
２進表現［ｋ１，ｋ０］＝［１，１］→ＪＲＦ表現［ｋ１，ｋ０］＝［０，−１］
２進表現［ｌ１，ｌ０］＝［１，０］→ＪＲＦ表現［ｌ１，ｌ０］＝［１，０］
とし、さらに、ｋの２進表現の上位ビットｋ２に（＋１）を繰り越す。この変換処理を実行して、ｋ，ｌのＪＲＦ表現を設定する。
【００６５】
ｋ０＝０の場合、すなわち、
（ｋ１，ｌ１）＝（１，１）、
（ｋ０，ｌ０）＝（０，１）のときは、
２進表現［ｋ１，ｋ０］＝［１，０］→ＪＲＦ表現［ｋ１，ｋ０］＝［１，０］
２進表現［ｌ１，ｌ０］＝［１，１］→ＪＲＦ表現［ｌ１，ｌ０］＝［０，−１］
とし、さらに、ｌの２進表現の上位ビットｌ２に（＋１）を繰り越す。この変換処理を実行して、ｋ，ｌのＪＲＦ表現を設定する。
【００６６】
以上の処理を実行することで、
（ｋ１，ｌ１）＝（０，０），（０，１），（１，０），（１，１）
これらの全ての場合に、
（ｋ０，ｌ０）＝（０，±１）または（±１，０）と、
（ｋ１，ｌ１）＝（０，１）または（１，０）
の組み合わせに設定されることになり、ジョイント・レギュラーフォーム（ＪＲＦ）の条件である、
（ｋｉ，ｌｉ）＝（０，±１）または（±１，０）
この条件を満足させることが可能となる。
【００６７】
次に，（ｋ２，ｌ２）についても、
（ｋ２，ｌ２）＝（０，０）または（１，１）の場合には、
（ｋ１，ｌ１）に応じて、上述と同様の変換を行なう。
この処理を、スカラー値ｋ，ｌの２進表現、すなわち、
ｋ＝（ｋｎ・・・ｋ０）２、
ｌ＝（ｌｎ・・・ｌ０）２、
これらの２進表現の下位から上位に向けて、順次、実行する。この処理を実行することにより、スカラー値ｋ，ｌを、
（ｋｉ，ｌｉ）＝（０，±１）または（±１，０）
を満たす０，１，−１の数列、
ｋ＝〈ｋｎ・・・ｋ０〉，
ｌ＝〈ｌｎ・・・ｌ０〉
で表現することが可能になる。
【００６８】
図２にスカラー値ｋ，ｌの２進表現からＪＲＦ表現への変換処理の態様をまとめたテーブルを示す。
スカラー値ｋ，ｌの２進表現を、
ｋ＝（ｋｎ・・・ｋ０）２、
ｌ＝（ｌｎ・・・ｌ０）２、
としたとき、
スカラー値制御部１０１は、この２進表現に基づいて、スカラー値ｋ，ｌのジョイント・レギュラーフォーム（ＪＲＦ：Ｊｏｉｎｔ Ｒｅｇｕｌａｒ Ｆｏｒｍ）を、ｋ，ｌの２進表現の下位ビットから順次、生成する。
【００６９】
スカラー値制御部１０１は、図２に示すように、ｋ，ｌの対応ビット（ｋｉ，ｌｉ）の組み合わせに応じて、以下の変換処理を行なってＪＲＦ表現に変更する。
（１）（ｋｉ，ｌｉ）＝（１，０）の場合、
（ｋｉ，ｌｉ）を、変更せず、そのまま、ＪＲＦ表現として適用
（２）（ｋｉ，ｌｉ）＝（０，１）の場合、
（ｋｉ，ｌｉ）を、変更せず、そのまま、ＪＲＦ表現として適用
【００７０】
（３）（ｋｉ，ｌｉ）＝（０，０）の場合、
（３ａ）（ｋｉ−１，ｌｉ−１）＝（１，０）の場合、
（ｋｉ，ｋｉ−１）＝［０，１］→ＪＲＦ＜１，−１＞
（ｌｉ，ｌｉ−１）＝［０，０］→ＪＲＦ＜０，０＞
これらの表現に変更して、ＪＲＦ表現を設定する。
（３ｂ）（ｋｉ−１，ｌｉ−１）＝（０，１）の場合、
（ｋｉ，ｋｉ−１）＝［０，０］→ＪＲＦ＜０，０＞
（ｌｉ，ｌｉ−１）＝［０，１］→ＪＲＦ＜１，−１＞
これらの表現に変更して、ＪＲＦ表現を設定する。
【００７１】
（４）（ｋｉ，ｌｉ）＝（１，１）の場合、
（４ａ）（ｋｉ−１，ｌｉ−１）＝（１，０）の場合、
（ｋｉ，ｋｉ−１）＝［１，１］→ＪＲＦ＜０，−１＞
（ｌｉ，ｌｉ−１）＝［１，０］→ＪＲＦ＜１，０＞
これらの表現に変更して、ＪＲＦ表現を設定する。
（４ｂ）（ｋｉ−１，ｌｉ−１）＝（０，１）の場合、
（ｋｉ，ｋｉ−１）＝［１，０］→ＪＲＦ＜１，０＞
（ｌｉ，ｌｉ−１）＝［１，１］→ＪＲＦ＜０，−１＞
これらの表現に変更して、ＪＲＦ表現を設定する。
【００７２】
スカラー値制御部１０１の実行するスカラー値ｋ，ｌのＪＲＦ表現の生成処理アルゴリズムの一例である［アルゴリズム１］について、図３に示すフローチャートを参照して説明する。
【００７３】
まず、ステップＳ１０１において、楕円曲線上の異なる２点Ｐ，Ｑのスカラー倍点の加算点ｋＰ＋ｌＱの算出に適用するスカラー値ｋ，ｌを入力する。次に、ステップＳ１０２において、スカラー値ｋ，ｌについて初期設定を行う。すなわち、
ｉ←０，ｓｉ←ｋ，ｔｉ←ｌ
の初期設定を実行する。
ｉは、ｋ，ｌの２進表現としてのビット位置を示す変数ｉ（ｉ＝０〜ｎ）に相当する。
【００７４】
次に、ステップＳ１０３において、スカラー値ｋ，ｌに相当するｓｉ，ｔｉの各々の最下位ビットｋｉ，ｌｉを算出する。ｋｉ，ｌｉは、以下の式によって算出される。
ｋｉ←ｓｉｍｏｄ２
ｌｉ←ｔｉｍｏｄ２
【００７５】
次に、ステップＳ１０４において、スカラー値ｋ，ｌの対応ビットの組み合わせ（ｋｉ，ｌｉ）についての状態判定を実行する。すなわち、まず、
（ｋｉ，ｌｉ）＝（０，０）
であるか否かを判定する。
【００７６】
ステップＳ１０４において、
（ｋｉ，ｌｉ）＝（０，０）
と判定された場合には、次に、ステップＳ１０５に進み、
ｋｉ−１＝１であるか否かを判定する。
【００７７】
ステップＳ１０５において、
ｋｉ−１＝１であると判定された場合は、ステップＳ１０６に進み、
ｋｉ←１
ｋｉ−１←−１
の設定を行う。すなわち、２進表現としてのスカラー値［ｋｉ，ｋｉ−１］をＪＲＦ表現として＜１，−１＞として設定する。この処理は、図２における（３ａ）の処理に相当する。
【００７８】
また、ステップＳ１０５において、
ｋｉ−１＝１でないと判定された場合は、ステップＳ１０７に進み、
ｌｉ←１
ｌｉ−１←−１
の設定を行う。すなわち、２進表現としてのスカラー値［ｌｉ，ｌｉ−１］をＪＲＦ表現として＜１，−１＞として設定する。この処理は、図２における（３ｂ）の処理に相当する。
【００７９】
ステップＳ１０６またはステップＳ１０７の処理の後、ステップＳ１０８に進み、スカラー値ｋ，ｌに相当するｓｉ，ｔｉの更新処理として、以下の処理を行なう。
ｓｉ＋１←ｓｉ／２
ｔｉ＋１←ｔｉ／２
これらの処理は、ＪＲＦ表現の設定された下位ビットを切り捨て、未処理の上位ビットのみを切り出す処理に相当する。
【００８０】
ステップＳ１０４において、
（ｋｉ，ｌｉ）＝（０，０）
でないと判定された場合には、次に、ステップＳ１０９に進み、
（ｋｉ，ｌｉ）＝（１，１）
であるか否かを判定する。
【００８１】
ステップＳ１０９において、
（ｋｉ，ｌｉ）＝（１，１）
であると判定された場合には、次に、ステップＳ１１０に進み、
ｋｉ−１＝１であるか否かを判定する。
【００８２】
ステップＳ１１０において、
ｋｉ−１＝１であると判定された場合は、ステップＳ１１１に進み、
ｋｉ←０
ｋｉ−１←−１
の設定を行う。すなわち、２進表現としてのスカラー値［ｋｉ，ｋｉ−１］をＪＲＦ表現として＜０，−１＞として設定する。さらに、スカラー値ｋ，ｌに相当するｓｉ，ｔｉの更新処理として、以下の処理を行なう。
ｓｉ＋１←（ｓｉ＋１）／２
ｔｉ＋１←（ｔｉ−１）／２
これらの処理は、ｋの２進表現の上位ビットｋｉ＋１に（＋１）を繰り越すとともに、ＪＲＦ表現の設定された下位ビットを切り捨て、未処理の上位ビットのみを切り出す処理に相当する。この処理は、図２における（４ａ）の処理に相当する。
【００８３】
ステップＳ１１０において、
ｋｉ−１＝１でないと判定された場合は、ステップＳ１１２に進み、
ｌｉ←０
ｌｉ−１←−１
の設定を行う。すなわち、２進表現としてのスカラー値［ｌｉ，ｌｉ−１］をＪＲＦ表現として＜０，−１＞として設定する。さらに、スカラー値ｋ，ｌに相当するｓｉ，ｔｉの更新処理として、以下の処理を行なう。
ｓｉ＋１←（ｓｉ−１）／２
ｔｉ＋１←（ｔｉ＋１）／２
これらの処理は、ｌの２進表現の上位ビットｌｉ＋１に（＋１）を繰り越すとともに、ＪＲＦ表現の設定された下位ビットを切り捨て、未処理の上位ビットのみを切り出す処理に相当する。この処理は、図２における（４ｂ）の処理に相当する。
【００８４】
ステップＳ１０９において、
（ｋｉ，ｌｉ）＝（１，１）
でないと判定された場合には、次に、ステップＳ１１３に進み、スカラー値ｋ，ｌに相当するｓｉ，ｔｉの更新処理として、以下の処理を行なう。
ｓｉ＋１←（ｓｉ−ｋｉ）／２
ｔｉ＋１←（ｔｉ−ｌｉ）／２
これらの処理は、２進表現としての（ｋｉ，ｌｉ）をそのままＪＲＦ表現として利用し、ＪＲＦ表現の設定された下位ビットを切り捨て、未処理の上位ビットのみを切り出す処理に相当する。この処理は、図２における（１），（２）の処理に相当する。
【００８５】
次に、ステップＳ１１４において、
ｓｉ＋１＞０、または、
ｔｉ＋１＞０
が成立するか否かを判定する。これは、ＪＲＦ表現への変換の済んでいない２進表現の上位ビットが存在するか否かを判定する処理である。ステップＳ１１４において、
ｓｉ＋１＞０、または、
ｔｉ＋１＞０
が成立すると判定された場合は、ＪＲＦ表現への変換の済んでいない２進表現の上位ビットが存在することを意味するので、ステップＳ１１５において、変数ｉを更新、すなわち、
ｉ←ｉ＋１
を実行して、ステップＳ１０３に戻り、同様の処理を繰り返し実行する。
【００８６】
ステップＳ１１４において、
ｓｉ＋１＞０、または、
ｔｉ＋１＞０
が成立しないと判定された場合は、ＪＲＦ表現への変換の済んでいない２進表現の上位ビットが存在しないことを意味するので、ステップＳ１１６に進み、最終的に設定された変数ｉをｎとする処理、すなわち、
ｎ←ｉ
この更新処理を実行し、ステップＳ１１７において、スカラー値ｋ，ｌのＪＲＦ表現として、
ｋ＝＜ｋｎ，・・・ｋ０＞、
ｌ＝＜ｌｎ，・・・ｌ０＞、
を出力する。
【００８７】
図１に示す暗号処理部１００のスカラー値制御部１０１は、この処理によって、
スカラー値ｋ，ｌの２進表現、すなわち、
ｋ＝（ｋｎ・・・ｋ０）２、
ｌ＝（ｌｎ・・・ｌ０）２、
これらの２進表現を、拡張２進表現、すなわち、すべてのビットを０，または＋１，または−１で表現し、かつ、ジョイント・レギュラーフォーム（ＪＲＦ：Ｊｏｉｎｔ Ｒｅｇｕｌａｒ Ｆｏｒｍ）の条件である、
（ｋｉ，ｌｉ）＝（０，±１）または（±１，０）
を満足するＪＲＦ表現としての、
ｋ＝＜ｋｎ，・・・ｋ０＞、
ｌ＝＜ｌｎ，・・・ｌ０＞、
を生成し、演算実行部１０２に出力する。演算実行部１０２では、スカラー値制御部１０１から入力するスカラー値ｋ，ｌのＪＲＦ表現としての、
ｋ＝＜ｋｎ，・・・ｋ０＞、
ｌ＝＜ｌｎ，・・・ｌ０＞、
これらのスカラー値に基づいて、先に説明した［点のスカラー倍同時計算のアルゴリズム］を実行する。この処理によって、［点のスカラー倍同時計算のアルゴリズム］において、
（ａ）（ｋｉ，ｌｉ）のすべての組み合わせにおいて、すべて同一の演算処理が実行される。
（ｂ）Ｐ＋Ｑの演算処理が省略できる。
上記（ａ），（ｂ）が実現されることになり、電力解析に対する耐性が向上し、演算の高速化が図られることになる。
【００８８】
図３を参照して説明したＪＲＦ表現の生成アルゴリズムである［アルゴリズム１］をまとめると、以下のように記述することができる。
【００８９】
［アルゴリズム１］
１．ｉ←０，ｓｉ←ｋ，ｔｉ←ｌと入力する。
２．ｓｉ，ｔｉの最下位ビットをそれぞれｋｉ，ｌｉとする。
３．（ｋｉ，ｌｉ）＝（０，０）の場合には、次のようにする。
ｋｉ−１＝１の場合には、ｋｉ←１，ｋｉ−１←−１と変換する。
ｋｉ−１＝０の場合には、ｌｉ←１，ｌｉ−１←−１と変換する。
ｓｉ＋１←ｓｉ／２，ｔｉ＋１←ｔｉ／２とする。
４．（ｋｉ，ｌｉ）＝（１，１）の場合には、次のようにする。
ｋｉ−１＝１の場合には、ｋｉ←０，ｋｉ−１←−１と変換し、
ｓｉ＋１←（ｓｉ＋１）／２，ｔｉ＋１←（ｔｉ−１）／２とする。
ｋｉ−１＝０の場合には、ｌｉ←０，ｌｉ−１←−１と変換し、
ｓｉ＋１←（ｓｉ−１）／２，ｔｉ＋１←（ｔｉ＋１）／２とする。
５．上記３，４以外の場合、つまり、
（ｋｉ，ｌｉ）＝（０，１）または（１，０）の場合は、
ｓｉ＋１←（ｓｉ−ｋｉ）／２，ｔｉ＋１←（ｔｉ−ｌｉ）／２とする。
６．ｓｉ＋１＞０またはｔｉ＋１＞０であれば、
ｉ←ｉ＋１として、２．に戻る。そうでなければ、ｎ←ｉとして、
〈ｋｎ・・・ｋ０〉，〈ｌｎ・・・ｌ０〉を出力する。
【００９０】
次に、上述のアルゴリズム１を、分岐が少なくなるように最適化した［アルゴリズム２］について、図４に示すフローチャートを参照して説明する。この［アルゴリズム２］も、スカラー値ｋ，ｌのＪＲＦ表現の生成処理アルゴリズムの一例であり、図１に示す暗号処理部１００におけるスカラー値制御部１０１において実行される。
【００９１】
ステップＳ２０１〜Ｓ２０３の処理は、図３を参照して説明した［アルゴリズム１］におけるステップＳ１０１〜Ｓ１０３と、ほぼ同様の処理である。すなわち、まず、ステップＳ２０１において、楕円曲線上の異なる２点Ｐ，Ｑのスカラー倍点の加算点ｋＰ＋ｌＱの算出に適用するスカラー値ｋ，ｌを入力する。次に、ステップＳ２０２において、スカラー値ｋ，ｌについて初期設定を行う。すなわち、
ｉ←０，ｓ←ｋ，ｔ←ｌ
の初期設定を実行する。
ｉは、ｋ，ｌの２進表現としてのビット位置を示す変数ｉ（ｉ＝０〜ｎ）に相当する。
次に、ステップＳ２０３において、スカラー値ｋ，ｌに相当するｓ，ｔの各々の最下位ビットｋｉ，ｌｉを算出する。ｋｉ，ｌｉは、以下の式によって算出される。
ｋｉ←ｓｍｏｄ２
ｌｉ←ｔｍｏｄ２
【００９２】
次に、ステップＳ２０４において、スカラー値ｋ，ｌの対応ビットの組み合わせ（ｋｉ，ｌｉ）についての状態判定を実行する。すなわち、まず、
（ｋｉ，ｌｉ）＝（０，０）
であるか否かを判定する。
【００９３】
ステップＳ２０４において、
（ｋｉ，ｌｉ）＝（０，０）
と判定された場合には、次に、ステップＳ２０５に進み、
ｋｉ←ｋｉ−１
ｋｉ−１←−ｋｉ−１
ｌｉ←ｌｉ−１
ｌｉ−１←−ｌｉ−１
これらの設定を行う。すなわち、２進表現に基づくスカラー値［ｋｉ，ｋｉ−１］を、ＪＲＦ表現として＜ｋｉ−１，−ｋｉ−１＞として設定し、［ｌｉ，ｌｉ−１］を、ＪＲＦ表現として＜ｌｉ−１，−ｌｉ−１＞として設定する。この処理は、図２における（３ａ）（３ｂ）の処理に相当する。
【００９４】
さらに、ステップＳ２０５では、スカラー値ｋ，ｌに相当するｓ，ｔの更新処理として、以下の処理を行なう。
ｓ←ｓ／２
ｔ←ｔ／２
これらの処理は、ＪＲＦ表現の設定された下位ビットを切り捨て、未処理の上位ビットのみを切り出す処理に相当する。
【００９５】
ステップＳ２０４において、
（ｋｉ，ｌｉ）＝（０，０）
でないと判定された場合には、次に、ステップＳ２０６に進み、
（ｋｉ，ｌｉ）＝（１，１）
であるか否かを判定する。
【００９６】
ステップＳ２０６において、
（ｋｉ，ｌｉ）＝（１，１）
であると判定された場合には、次に、ステップＳ２０７に進み、
ｋｉ←１−ｋｉ−１
ｋｉ−１←−ｋｉ−１
ｌｉ←１−ｌｉ−１
ｌｉ−１←−ｌｉ−１
これらの設定を行う。すなわち、２進表現に基づくスカラー値［ｋｉ，ｋｉ−１］を、ＪＲＦ表現として＜１−ｋｉ−１，−ｋｉ−１＞として設定し、［ｌｉ，ｌｉ−１］を、ＪＲＦ表現として＜１−ｌｉ−１，−ｌｉ−１＞として設定する。この処理は、図２における（４ａ）（４ｂ）の処理に相当する。
【００９７】
さらに、ステップＳ２０７では、スカラー値ｋ，ｌに相当するｓ，ｔの更新処理として、以下の処理を行なう。
ｓ←（ｓ−２ｋｉ＋１）／２
ｔ←（ｔ−ｌｉ）／２
これらの処理は、ＪＲＦ表現の設定された下位ビットを切り捨て、未処理の上位ビットのみを切り出す処理に相当する。
【００９８】
ステップＳ２０６において、
（ｋｉ，ｌｉ）＝（１，１）
でないと判定された場合には、次に、ステップＳ２０８に進み、スカラー値ｋ，ｌに相当するｓ，ｔの更新処理として、以下の処理を行なう。
ｓ←（ｓ−ｋｉ）／２
ｔ←（ｔ−ｌｉ）／２
これらの処理は、２進表現としての（ｋｉ，ｌｉ）をそのままＪＲＦ表現として利用し、ＪＲＦ表現の設定された下位ビットを切り捨て、未処理の上位ビットのみを切り出す処理に相当する。この処理は、図２における（１），（２）の処理に相当する。
【００９９】
次に、ステップＳ２０９において、
ｓ＞０、または、
ｔ＞０
が成立するか否かを判定する。これは、ＪＲＦ表現への変換の済んでいない２進表現の上位ビットが存在するか否かを判定する処理である。ステップＳ２０９において、
ｓ＞０、または、
ｔ＞０
が成立すると判定された場合は、ＪＲＦ表現への変換の済んでいない２進表現の上位ビットが存在することを意味するので、ステップＳ２１０において、変数ｉを更新、すなわち、
ｉ←ｉ＋１
を実行して、ステップＳ２０３に戻り、同様の処理を繰り返し実行する。
【０１００】
ステップＳ２０９において、
ｓ＞０、または、
ｔ＞０
が成立しないと判定された場合は、ＪＲＦ表現への変換の済んでいない２進表現の上位ビットが存在しないことを意味するので、ステップＳ２１１に進み、最終的に設定された変数ｉをｎとする処理、すなわち、
ｎ←ｉ
この更新処理を実行し、ステップＳ２１２において、スカラー値ｋ，ｌのＪＲＦ表現として、
ｋ＝＜ｋｎ，・・・ｋ０＞、
ｌ＝＜ｌｎ，・・・ｌ０＞、
を出力する。
【０１０１】
図１に示す暗号処理部１００のスカラー値制御部１０１は、この処理によって、
スカラー値ｋ，ｌの２進表現、すなわち、
ｋ＝（ｋｎ・・・ｋ０）２、
ｌ＝（ｌｎ・・・ｌ０）２、
これらの２進表現を、拡張２進表現、すなわち、すべてのビットを０，または＋１，または−１で表現し、かつ、ジョイント・レギュラーフォーム（ＪＲＦ：Ｊｏｉｎｔ Ｒｅｇｕｌａｒ Ｆｏｒｍ）の条件である、
（ｋｉ，ｌｉ）＝（０，±１）または（±１，０）
を満足するＪＲＦ表現としての、
ｋ＝＜ｋｎ，・・・ｋ０＞、
ｌ＝＜ｌｎ，・・・ｌ０＞、
を生成し、演算実行部１０２に出力する。演算実行部１０２では、スカラー値制御部１０１から入力するスカラー値ｋ，ｌのＪＲＦ表現としての、
ｋ＝＜ｋｎ，・・・ｋ０＞、
ｌ＝＜ｌｎ，・・・ｌ０＞、
これらのスカラー値に基づいて、先に説明した［点のスカラー倍同時計算のアルゴリズム］を実行する。この処理によって、［点のスカラー倍同時計算のアルゴリズム］において、
（ａ）（ｋｉ，ｌｉ）のすべての組み合わせにおいて、すべて同一の演算処理が実行される。
（ｂ）Ｐ＋Ｑの演算処理が省略できる。
上記（ａ），（ｂ）が実現されることになり、電力解析に対する耐性が向上し、演算の高速化が図られることになる。
【０１０２】
図４を参照して説明したＪＲＦ表現の生成アルゴリズムである［アルゴリズム２］をまとめると、以下のように記述することができる。
【０１０３】
［アルゴリズム２］
１．ｉ←０，ｓ←ｋ，ｔ←ｌと入力する。
２．ｓ，ｔの最下位ビットをそれぞれｋｉ，ｌｉとする。
３．（ｋｉ，ｌｉ）＝（０，０）の場合には、
ｋｉ←ｋｉ−１，ｋｉ−１←−ｋｉ−１，
ｌｉ←ｌｉ−１，ｌｉ−１←−ｌｉ−１，
ｓ←ｓ／２，
ｔ←ｔ／２
とする。
４．（ｋｉ，ｌｉ）＝（０，０）の場合には、
ｋｉ←１−ｋｉ−１，ｋｉ−１←−ｋｉ−１，
ｌｉ←１−ｌｉ−１，ｌｉ−１←−ｌｉ−１，
ｓ←（ｓ−２ｋｉ＋１）／２，
ｔ←（ｔ−２ｌｉ＋１）／２
とする。
５．上記３，４以外の場合には、
ｓ←（ｓ−ｋｉ）／２，
ｔ←（ｔ−ｌｉ）／２
とする。
６．ｓ＞０またはｔ＞０であれば、
ｉ←ｉ＋１として２．に戻る。そうでなければ、ｎ←ｉとして、
〈ｋｎ・・・ｋ０〉，〈ｌｎ・・・ｌ０〉を出力する。
【０１０４】
次に、図１に示す暗号処理部１００において実行される［点のスカラー倍同時計算のアルゴリズム］の全体処理について、すなわち、スカラー値制御部１０１と演算実行部１０２の実行する処理の全体アルゴリズムについて、［アルゴリズム３］として、図５に示すフローチャートを参照して説明する。
【０１０５】
図１に示す暗号処理部１００の演算実行部１０２は、スカラー値制御部１０１から入力するスカラー値ｋ，ｌのＪＲＦ表現としての、
ｋ＝＜ｋｎ，・・・ｋ０＞、
ｌ＝＜ｌｎ，・・・ｌ０＞、
これらのスカラー値を入力して、点のスカラー倍加算点［ｋＰ＋ｌＱ］を算出する。基本的には、先に説明した［点のスカラー倍同時計算のアルゴリズム］を実行することになるが、先に説明したように、
（ａ）（ｋｉ，ｌｉ）のすべての組み合わせにおいて、すべて同一の演算処理が実行される。
（ｂ）Ｐ＋Ｑの演算処理が省略できる。
上記（ａ），（ｂ）が実現され、従来の演算アルゴリズムと異なるアルゴリズムとなる。図５に示すフローを参照して本発明の［点のスカラー倍同時計算のアルゴリズム］について説明する。
【０１０６】
まず、ステップＳ３０１において、暗号処理部は、点のスカラー倍加算点［ｋＰ＋ｌＱ］を算出するために必要となるパラメータとして、スカラー値ｋ，ｌと、楕円曲線上の点Ｐ，Ｑを入力する。
【０１０７】
次に、ステップＳ３０２において、スカラー値ｋ，ｌをＪＲＦ表現としての、
ｋ＝＜ｋｎ，・・・ｋ０＞、
ｌ＝＜ｌｎ，・・・ｌ０＞、
に変換する。この処理は、図１に示すスカラー値制御部１０１において実行される処理であり、先に、図３を参照して説明した［アルゴリズム１］、または、図４を参照して説明した［アルゴリズム２］に従って実行される。
【０１０８】
ステップＳ３０３以下の処理は、図１に示す演算実行部１０２において実行される［点のスカラー倍同時計算処理］である。この処理は、先に説明した従来手法としての［点のスカラー倍同時計算のアルゴリズム］、すなわち、
［点のスカラー倍同時計算のアルゴリズム］
Ｉｎｐｕｔ：楕円曲線上の点Ｐ，Ｑ  スカラー値ｋ，ｌ
Ｏｕｔｐｕｔ:ｋＰ＋ｌＱ
１．Ｃｏｍｐｕｔｅ  Ｐ＋Ｑ
２．Ｔ←（ｋｎＰ＋ｌｎＱ）
３．Ｆｏｒ  ｉ＝ｎ−１  ｄｏｗｎｔｏ  ０  ｄｏ
Ｔ←２Ｔ
Ｉｆ  （ｋｉ，ｌｉ）≠（０，０）  ｔｈｅｎ
Ｔ←Ｔ＋（ｋｉＰ＋ｌｉＱ）
４．Ｒｅｔｕｒｎ  Ｔ
この処理を基本としているが、複数の変更点を有する。
【０１０９】
まず、ステップＳ３０３において、
Ｔ←（ｋｎＰ＋ｌｎＱ）
ｉ←ｎ−１
とする。この処理は、従来の［点のスカラー倍同時計算のアルゴリズム］におけるステップ２に相当する処理として実行される。ｉは、ＪＲＦ表現としての
ｋ＝＜ｋｎ，・・・ｋ０＞、
ｌ＝＜ｌｎ，・・・ｌ０＞、
のビット位置を示す変数として利用される。
【０１１０】
なお、本発明のアルゴリズムでは、従来の［点のスカラー倍同時計算のアルゴリズム］におけるステップ１の［Ｃｏｍｐｕｔｅ  Ｐ＋Ｑ］の算出処理が省略される。
【０１１１】
次にステップＳ３０４において、
ｉ≧０
が成立するか否かが判定される。ｉ≧０が成立しない場合は、ｋＰ＋ｌＱの算出処理が終了したことを意味する。
【０１１２】
ｉ≧０が成立する場合は、ｋＰ＋ｌＱの算出処理が終了していないことを意味し、ステップＳ３０５に進み、
Ｔ←２Ｔ
とし、さらに、ステップＳ３０６において、
Ｔ←Ｔ＋（ｋｉＰ＋ｌｉＱ）
とする処理を実行する。この処理は、従来の［点のスカラー倍同時計算のアルゴリズム］におけるステップ３に相当する処理として実行される。
【０１１３】
しかし、従来の［点のスカラー倍同時計算のアルゴリズム］におけるステップ３では、（ｋｉ，ｌｉ）の値に基づく選択的な処理として実行されていた処理、すなわち、
Ｉｆ  （ｋｉ，ｌｉ）≠（０，０）  ｔｈｅｎ
Ｔ←Ｔ＋（ｋｉＰ＋ｌｉＱ）
この処理が、本発明に従った処理では、全ての（ｋｉ，ｌｉ）の組み合わせにおいて実行される。この処理の結果、電力解析ビット値の解析を困難化することが可能となる。
【０１１４】
次に、ステップＳ３０７において、変数ｉの更新処理として、
ｉ←ｉ＋１
を実行し、ステップＳ３０４以下を繰り返し実行する。
最終的に、ステップＳ３０４において、
ｉ≧０
が成立しないと判定されると、ｋＰ＋ｌＱの算出処理が終了したと判定し、ステップＳ３０８において、Ｔ＝ｋＰ＋ｌＱを出力して処理を終了する。
【０１１５】
このように、本発明の点のスカラー倍同時計算アルゴリズムでは、先に説明した従来の［点のスカラー倍同時計算のアルゴリズム］におけるステップ１の［Ｃｏｍｐｕｔｅ  Ｐ＋Ｑ］の算出処理が省略され、また、ステップ３の処理が、（ｋｉ，ｌｉ）のすべての組み合わせにおいて、すべて同一の処理として実行される。この結果、電力解析に対する耐性が向上するとともに、演算の高速処理が可能となる。
【０１１６】
図５を参照して説明した本発明の点のスカラー倍同時計算アルゴリズムである［アルゴリズム３］をまとめると、以下のように記述することができる。
【０１１７】
［アルゴリズム３］
１．ｋ，ｌをＪＲＦで表現し、
〈ｋｎ・・・ｋ０〉，
〈ｌｎ・・・ｌ０〉
を出力する。
２．Ｔ←（ｋｎＰ＋ｌｎＱ），
ｉ←ｎ−１
とする。
３．ｉ≧０でなければ、Ｔを出力し終了する。
４．Ｔ←２Ｔを点の２倍算を用いて計算する。
５．Ｔ←Ｔ＋（ｋｉＰ＋ｌｉＱ）を点の加算を用いて計算する。
６．ｉ←ｎ−１とし、３．に戻る。
【０１１８】
上述の図５を参照して説明した処理フローは、ｋＰ＋ｌＱを算出する点のスカラー倍同時計算のアルゴリズムであるが、前提として、スカラー値ｋとｌが偶奇の組み合わせ、すなわち、
ｋが偶数で、ｌが奇数、または、
ｋが奇数で、ｌが偶数、
これらのいずれかの場合を前提としている処理である。これは、ジョイント・レギュラーフォーム（ＪＲＦ：Ｊｏｉｎｔ Ｒｅｇｕｌａｒ Ｆｏｒｍ）の条件である、
（ｋｉ，ｌｉ）＝（０，±１）または（±１，０）
を満足するための必須要件となるからである。
【０１１９】
しかし、図１の暗号処理部１００において算出すべき、点のスカラー倍加算点［ｋＰ＋ｌＱ］において、入力するスカラー値ｋ，ｌは、偶奇の組み合わせであるとは限らない。以下、図６に示すフローチャートを参照して、スカラー値ｋ，ｌが偶奇の組み合わせのみならず、偶数同士、奇数同士である場合にも、対応可能とし、電力解析に対する耐性の向上と演算の高速処理を実現する処理シーケンス［アルゴリズム４］について説明する。
【０１２０】
図６に示すフローに従った［アルゴリズム４］は、図１に示す暗号処理部１００において実行される。まず、ステップＳ４０１において、暗号処理部は、点のスカラー倍加算点［ｋＰ＋ｌＱ］を算出するために必要となるパラメータとして、スカラー値ｋ，ｌと、楕円曲線上の点Ｐ，Ｑを入力する。
【０１２１】
ステップＳ４０２〜Ｓ４０６の処理は、図１に示すスカラー値制御部１０１において実行される。まず、ステップＳ４０２において、スカラー値ｋ，ｌの偶奇判定を行なう。すなわち、ｋ，ｌが双方とも偶数、または奇数であるか否かが判定される。
【０１２２】
ステップＳ４０２において、ｋ，ｌが双方とも偶数、または奇数であると判定されると、入力されたｋ，ｌのままでは、ジョイント・レギュラーフォーム（ＪＲＦ：Ｊｏｉｎｔ Ｒｅｇｕｌａｒ Ｆｏｒｍ）の条件である、
（ｋｉ，ｌｉ）＝（０，±１）または（±１，０）
を満足するＪＲＦ表現が設定できない。このため、ステップＳ４０４，Ｓ４０５において、フラグの設定およびスカラー値の調整を実行する。すなわち、ステップＳ４０４において、スカラー値の調整が実行されることを示すフラグ［１］を設定する。これは、例えば暗号処理部１００のアクセス可能なメモリに、ｋＰ＋ｌＱの処理データに対応するフラグとして設定する。
【０１２３】
次に、ステップＳ４０５において、スカラー値ｋをｋ＋１に変更する処理を実行する。この処理によって、更新されたｋとｌは、偶数と奇数の組み合わせに変更され、ジョイント・レギュラーフォーム（ＪＲＦ：Ｊｏｉｎｔ Ｒｅｇｕｌａｒ Ｆｏｒｍ）の条件である、
（ｋｉ，ｌｉ）＝（０，±１）または（±１，０）
を満足するＪＲＦ表現が設定可能となる。
【０１２４】
一方、ステップＳ４０２において、ｋ，ｌが双方とも偶数、または奇数の組み合わせでなく、偶奇の組み合わせであると判定されると、入力されたｋ，ｌのままで、ジョイント・レギュラーフォーム（ＪＲＦ：Ｊｏｉｎｔ Ｒｅｇｕｌａｒ Ｆｏｒｍ）の条件である、
（ｋｉ，ｌｉ）＝（０，±１）または（±１，０）
を満足するＪＲＦ表現が設定可能であり、ステップＳ４０３において、スカラー値の調整が実行されていないことを示すフラグ［０］を設定する。
【０１２５】
ステップＳ４０３またはステップＳ４０５の処理の後、ステップＳ４０６において、スカラー値ｋ，ｌをＪＲＦ表現としての、
ｋ＝＜ｋｎ，・・・ｋ０＞、
ｌ＝＜ｌｎ，・・・ｌ０＞、
に変換する。この処理は、図１に示すスカラー値制御部１０１において実行される処理であり、先に、図３を参照して説明した［アルゴリズム１］、または、図４を参照して説明した［アルゴリズム２］に従って実行される。
【０１２６】
ステップＳ４０７以下の処理は、図１に示す演算実行部１０２において実行される［点のスカラー倍同時計算処理］である。この処理は、先に説明した従来手法としての［点のスカラー倍同時計算のアルゴリズム］を基本としているが、図５を参照して説明したと同様、複数の変更点を有する。
【０１２７】
まず、ステップＳ４０７において、
Ｔ←（ｋｎＰ＋ｌｎＱ）
ｉ←ｎ−１
とする。この処理は、従来の［点のスカラー倍同時計算のアルゴリズム］におけるステップ２に相当する処理として実行される。ｉは、ＪＲＦ表現としての
ｋ＝＜ｋｎ，・・・ｋ０＞、
ｌ＝＜ｌｎ，・・・ｌ０＞、
のビット位置を示す変数として利用される。なお、このアルゴリズムにおいても、従来の［点のスカラー倍同時計算のアルゴリズム］におけるステップ１の［Ｃｏｍｐｕｔｅ  Ｐ＋Ｑ］の算出処理が省略される。
【０１２８】
次にステップＳ４０８において、
ｉ≧０
が成立するか否かが判定される。ｉ≧０が成立しない場合は、ｋＰ＋ｌＱの算出処理が終了したことを意味する。
【０１２９】
ｉ≧０が成立する場合は、ｋＰ＋ｌＱの算出処理が終了していないことを意味し、ステップＳ４０９に進み、
Ｔ←２Ｔ
とし、さらに、ステップＳ４１０において、
Ｔ←Ｔ＋（ｋｉＰ＋ｌｉＱ）
とする処理を実行する。この処理は、従来の［点のスカラー倍同時計算のアルゴリズム］におけるステップ３に相当する処理として実行される。本処理例でも、先に図５を参照して説明したアルゴリズム３と同様、従来の［点のスカラー倍同時計算のアルゴリズム］におけるステップ３では、（ｋｉ，ｌｉ）の値に基づく選択的な処理として実行されていた処理、すなわち、
Ｉｆ  （ｋｉ，ｌｉ）≠（０，０）  ｔｈｅｎ
Ｔ←Ｔ＋（ｋｉＰ＋ｌｉＱ）
この処理が、本アルゴリズム４では、全ての（ｋｉ，ｌｉ）の組み合わせにおいて実行される。この処理の結果、電力解析ビット値の解析を困難化することが可能となる。
【０１３０】
次に、ステップＳ４１１において、変数ｉの更新処理として、
ｉ←ｉ＋１
を実行し、ステップＳ４０８以下を繰り返し実行する。
最終的に、ステップＳ４０８において、
ｉ≧０
が成立しないと判定されると、ｋＰ＋ｌＱの算出処理が終了したと判定し、ステップＳ４１２において、設定済みのフラグの判定がなされる。フラグに［１］が設定されている場合は、演算実行部において算出したＴ＝ｋＰ＋ｌＱの算出に適用したスカラー値［ｋ］は、入力されたスカラー値ではなく、ステップＳ４０５において、ｋ←ｋ＋１の処理で更新されたスカラー値であると判定し、ステップＳ４１３において、補正計算として、
Ｔ←Ｔ−Ｐ
の補正計算を実行する。この補正計算の後、ステップＳ４１４において、計算結果として、
Ｔ＝ｋＰ＋ｌＱ
を出力して処理を終了する。
【０１３１】
ステップＳ４１２において、フラグに［１］が設定されていない場合は、演算実行部において算出したＴ＝ｋＰ＋ｌＱの算出に適用したスカラー値［ｋ］は、入力されたスカラー値であり、ステップＳ４０５の補正処理は省略され、ステップＳ４１４において、計算結果として、
Ｔ＝ｋＰ＋ｌＱ
を出力して処理を終了する。
【０１３２】
このように、図６を参照して説明した［アルゴリズム４］では、入力するスカラー値ｋ，ｌが任意の組み合わせにおいて対応可能であり、入力するスカラー値ｋ，ｌが偶奇の組み合わせのみならず、偶数同士、奇数同士である場合にも、電力解析に対する耐性の向上と演算の高速処理が実現される。
【０１３３】
すなわち、先に説明した従来の［点のスカラー倍同時計算のアルゴリズム］におけるステップ１の［Ｃｏｍｐｕｔｅ  Ｐ＋Ｑ］の算出処理が省略され、また、ステップ３の処理が、（ｋｉ，ｌｉ）のすべての組み合わせにおいて、すべて同一の処理として実行される。この結果、電力解析に対する耐性が向上するとともに、演算の高速処理が可能となる。
【０１３４】
図６を参照して説明した本発明の点のスカラー倍同時計算アルゴリズムである［アルゴリズム４］をまとめると、以下のように記述することができる。
【０１３５】
［アルゴリズム４］
１．ｋ，ｌの偶奇が同じであれば、
ｋ←ｋ＋１，
ｆｌａｇ←１
とする。そうでなければ、
ｆｌａｇ←０とする。
２．ｋ，ｌをＪＲＦで表現し、
〈ｋｎ・・・ｋ０〉，
〈ｌｎ・・・ｋ０〉
を出力する。
３．Ｔ←（ｋｎＰ＋ｌｎＱ），
ｉ←ｎ−１とする。
４．ｉ≧０でなければ、８．に進む。
５．Ｔ←２Ｔを点の２倍算を用いて計算する。
６．Ｔ←Ｔ＋（ｋｉＰ＋ｌｉＱ）を点の加算を用いて計算する。
７．ｉ←ｎ−１とし、３．に戻る。
８．ｆｌａｇ＝１であれば，Ｔ←Ｔ−Ｐとする。
Ｔを出力する。
【０１３６】
本処理例によれば、任意のスカラー値ｋ，ｌに対する処理が可能であり、ｋ，ｌの偶奇以外の情報をもらさずにｋＰ＋ｌＱのスカラー倍同時計算をすることができる。なお、上述の実施例では、スカラー値ｋに対して＋１することで、入力スカラー値の変更を行なう設定としたが、入力スカラー値が偶数同士、または奇数同士である場合に、偶数と奇数の組み合わせに変更すれば、よく、スカラー値ｋ，ｌの変更態様は、上述した処理例（ｋ←ｋ＋１）に限らず、様々な変更処理が可能である。ただし、変更したスカラー値を適用した演算後において、変更を元に戻すための補正計算を行なうことが必要である。
【０１３７】
なお、図３〜図６を参照して説明した各アルゴリズムにおいては、楕円曲線暗号におけるスカラー倍点の加算点ｋＰ＋ｌＱの算出処理例を実施例として説明してきたが先にも説明したように、超楕円曲線暗号におけるスカラー倍因子の加算因子ｋＤ１＋ｌＤ２の算出も、ｋＰ＋ｌＱの算出処理と同様に実行可能である。すなわち、本発明の暗号処理装置は、楕円曲線暗号または超楕円曲線暗号に対応する暗号処理演算を実行する暗号処理装置であり、楕円曲線暗号において規定される楕円曲線上の２点Ｐ，Ｑ、およびスカラー値ｋ，ｌに基づくスカラー倍加算：ｋＰ＋ｌＱ、または、超楕円曲線暗号において規定される因子Ｄ１，Ｄ２、およびスカラー値ｋ，ｌに基づくスカラー倍加算：ｋＤ１＋ｌＤ２、これらのいずれかのスカラー倍加算演算を実行する。
【０１３８】
図１に示すスカラー値制御部１０１は、スカラー値ｋ，ｌについて、すべてのビットを０，または＋１，または−１で表現し、かつ、スカラー値ｋ，ｌの対応ビット位置のビットの組み合わせ（ｋｉ，ｌｉ）を、
（ｋｉ，ｌｉ）＝（０，±１）または（±１，０）
を満足する設定としたＪＲＦ（ジョイント・レギュラーフォーム）表現スカラー値、
ｋ＝＜ｋｎ，・・・ｋ０＞、
ｌ＝＜ｌｎ，・・・ｌ０＞、
を生成する処理を実行するスカラー値制御部であり、図１に示す演算実行部１０２は、スカラー値制御部１０１の生成したＪＲＦ表現スカラー値を適用して、スカラー倍加算：ｋＰ＋ｌＱ、またはｋＤ１＋ｌＤ２の演算処理を実行する。
【０１３９】
さらに、スカラー値制御部１０１は、スカラー値ｋ，ｌが、両者とも偶数、または両者とも奇数である場合、いずれか一方のスカラー値の値を変更して、偶数と奇数の組み合わせに設定し、変更したスカラー値ｋ，ｌについて、対応ビット位置のビットの組み合わせ（ｋｉ，ｌｉ）が、
（ｋｉ，ｌｉ）＝（０，±１）または（±１，０）
を満足するＪＲＦ（ジョイント・レギュラーフォーム）表現スカラー値、
ｋ＝＜ｋｎ，・・・ｋ０＞、
ｌ＝＜ｌｎ，・・・ｌ０＞、
を生成する処理を実行し、演算実行部１０２は、変更スカラー値に基づくスカラー倍加算：ｋＰ＋ｌＱ、またはｋＤ１＋ｌＤ２の演算処理を実行し、さらに、補正計算を実行して、変更前のスカラー値を適用したスカラー倍加算結果を算出する処理を実行する構成を持つ。
【０１４０】
また、演算実行部１０２は、ＪＲＦ表現スカラー値、
ｋ＝＜ｋｎ，・・・ｋ０＞、
ｌ＝＜ｌｎ，・・・ｌ０＞、
の対応ビット（ｋｉ，ｌｉ）を選択し、スカラー倍加算：ｋＰ＋ｌＱ、またはｋＤ１＋ｌＤ２を同時に計算する同時計算手法を適用した演算を実行する構成であり、ＪＲＦ表現スカラー値、
ｋ＝＜ｋｎ，・・・ｋ０＞、
ｌ＝＜ｌｎ，・・・ｌ０＞、
の対応ビット（ｋｉ，ｌｉ）のすべてについて、同一の計算シーケンスを適用した演算処理を実行し、また演算処理において、加算点：Ｐ＋Ｑ、または加算因子：Ｄ１＋Ｄ２の算出処理を実行することなく、スカラー倍加算：ｋＰ＋ｌＱ、またはｋＤ１＋ｌＤ２の演算処理を実行する。
【０１４１】
これらの処理構成によって、高速な演算が実現され、また、ＳＰＡ耐性に優れた安全な暗号処理が可能となる。
【０１４２】
［（３）暗号処理装置の構成例］
最後に、上述の暗号処理を実行するデバイスとしてのＩＣモジュール２００の構成例を図７に示す。上述の処理は、例えばＰＣ、ＩＣカード、リーダライタ、その他、様々な情報処理装置において実行可能であり、図７に示すＩＣモジュール２００は、これら様々な機器に構成することが可能である。
【０１４３】
図７に示すＣＰＵ(Central processing Unit)２０１は、暗号処理の開始や、終了、データの送受信の制御、各構成部間のデータ転送制御、その他の各種プログラムを実行するプロセッサである。メモリ２０２は、ＣＰＵ２０１が実行するプログラム、あるいは演算パラメータとしての固定データを格納するＲＯＭ（Read-Only-Memory）、ＣＰＵ２０１の処理において実行されるプログラム、およびプログラム処理において適宜変化するパラメータやフラグの格納エリア、ワーク領域として使用されるＲＡＭ（Random Access Memory）等からなる。
【０１４４】
なお、メモリ２０２に格納する演算実行プログラムには、上述した点のスカラー倍加算処理の実行シーケンスを含むプログラムなどが含まれる。データ等の格納領域は、耐タンパ構造を持つメモリとして構成されることが好ましい。
【０１４５】
暗号処理部２０３は、上述したスカラー倍算処理を含む暗号処理、復号処理等を実行する。なお、ここでは、暗号処理手段を個別モジュールとした例を示したが、このような独立した暗号処理モジュールを設けず、例えば暗号処理プログラムをＲＯＭに格納し、ＣＰＵ２０１がＲＯＭ格納プログラムを読み出して実行するように構成してもよい。
【０１４６】
乱数発生器２０４は、暗号処理に必要となる鍵の生成などにおいて必要となる乱数の発生処理を実行する。
【０１４７】
送受信部２０５は、外部とのデータ通信を実行するデータ通信処理部であり、例えばリーダライタ等、ＩＣモジュールとのデータ通信を実行し、ＩＣモジュール内で生成した暗号文の出力、あるいは外部のリーダライタ等の機器からのデータ入力などを実行する。
【０１４８】
以上、特定の実施例を参照しながら、本発明について詳解してきた。しかしながら、本発明の要旨を逸脱しない範囲で当業者が該実施例の修正や代用を成し得ることは自明である。すなわち、例示という形態で本発明を開示してきたのであり、限定的に解釈されるべきではない。本発明の要旨を判断するためには、特許請求の範囲の欄を参酌すべきである。
【０１４９】
なお、明細書中において説明した一連の処理はハードウェア、またはソフトウェア、あるいは両者の複合構成によって実行することが可能である。ソフトウェアによる処理を実行する場合は、処理シーケンスを記録したプログラムを、専用のハードウェアに組み込まれたコンピュータ内のメモリにインストールして実行させるか、あるいは、各種処理が実行可能な汎用コンピュータにプログラムをインストールして実行させることが可能である。
【０１５０】
例えば、プログラムは記録媒体としてのハードディスクやＲＯＭ（Read Only Memory)に予め記録しておくことができる。あるいは、プログラムはフレキシブルディスク、ＣＤ−ＲＯＭ(Compact Disc Read Only Memory)，ＭＯ(Magneto optical)ディスク，ＤＶＤ(Digital Versatile Disc)、磁気ディスク、半導体メモリなどのリムーバブル記録媒体に、一時的あるいは永続的に格納（記録）しておくことができる。このようなリムーバブル記録媒体は、いわゆるパッケージソフトウエアとして提供することができる。
【０１５１】
なお、プログラムは、上述したようなリムーバブル記録媒体からコンピュータにインストールする他、ダウンロードサイトから、コンピュータに無線転送したり、ＬＡＮ(Local Area Network)、インターネットといったネットワークを介して、コンピュータに有線で転送し、コンピュータでは、そのようにして転送されてくるプログラムを受信し、内蔵するハードディスク等の記録媒体にインストールすることができる。
【０１５２】
なお、明細書に記載された各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。また、本明細書においてシステムとは、複数の装置の論理的集合構成であり、各構成の装置が同一筐体内にあるものには限らない。
【産業上の利用可能性】
【０１５３】
本発明の構成によれば、楕円曲線暗号において規定される楕円曲線上の２点Ｐ，Ｑ、およびスカラー値ｋ，ｌに基づくスカラー倍加算：ｋＰ＋ｌＱ、または、超楕円曲線暗号において規定される因子Ｄ１，Ｄ２、およびスカラー値ｋ，ｌに基づくスカラー倍加算：ｋＤ１＋ｌＤ２、これらの演算処理において、スカラー値ｋ，ｌについて、すべてのビットを０，または＋１，または−１で表現し、かつ、スカラー値ｋ，ｌの対応ビット位置のビットの組み合わせ（ｋｉ，ｌｉ）を、
（ｋｉ，ｌｉ）＝（０，±１）または（±１，０）
を満足する設定としたＪＲＦ（ジョイント・レギュラーフォーム）表現スカラー値、
ｋ＝＜ｋｎ，・・・ｋ０＞、
ｌ＝＜ｌｎ，・・・ｌ０＞、
を生成し、このＪＲＦ表現のスカラー値を適用してスカラー倍加算：ｋＰ＋ｌＱ、またはｋＤ１＋ｌＤ２の演算処理を実行する構成としたので、（ｋｉ，ｌｉ）のすべての組み合わせにおいて同一の演算処理シーケンスを実行可能となり、ビットの組み合わせに応じた処理の差異がなくなり電力解析に対する耐性が向上し、また、Ｐ＋ＱやＤ１＋Ｄ２の事前計算の省略が可能となり演算処理の高速化が実現される。
【図面の簡単な説明】
【０１５４】
【図１】本発明の暗号処理装置における点のスカラー倍加算の算出を実行する暗号処理部構成例について説明する図である。
【図２】スカラー値ｋ，ｌの２進表現からＪＲＦ表現への変換処理の態様をまとめたテーブルを示す図である。
【図３】スカラー値制御部の実行するスカラー値ｋ，ｌのＪＲＦ表現の生成処理アルゴリズムの一例である［アルゴリズム１］について説明するフローチャートを示す図である。
【図４】スカラー値制御部の実行するスカラー値ｋ，ｌのＪＲＦ表現の生成処理アルゴリズムの一例である［アルゴリズム２］について説明するフローチャートを示す図である。
【図５】暗号処理部において実行される処理の全体アルゴリズムとしての［アルゴリズム３］について説明するフローチャートを示す図である。
【図６】暗号処理部において実行される処理の全体アルゴリズムとしての［アルゴリズム４］について説明するフローチャートを示す図である。
【図７】本発明の暗号処理演算を実行する暗号処理実行デバイス例としてのＩＣモジュールの構成例を示す図である。
【符号の説明】
【０１５５】
１００  暗号処理部
１０１  スカラー値制御部
１０２  演算実行部
２００  ＩＣモジュール
２０１  ＣＰＵ(Central Processing Unit)
２０２  メモリ
２０３  暗号処理部
２０４  乱数発生器
２０５  送受信部
【図１】
0004682852.tif 000002
【図２】
0004682852.tif 000003
【図３】
0004682852.tif 000004
【図４】
0004682852.tif 000005
【図５】
0004682852.tif 000006
【図６】
0004682852.tif 000007
【図７】
0004682852.tif 000008