(57)【要約】【課題】  コブリッツ曲線上に適用可能で、サイドチャネル攻撃を防ぐことができる、かつメモリ使用量、及び、処理高速性に優れる、楕円曲線におけるスカラー倍計算の技術を提供する。【解決手段】  コンピュータＡ１０１及びコンピュータＢ１２１において、スカラー倍計算部１１５，１３５は、スカラー値及び楕円曲線上の点からスカラー倍点を計算するスカラー倍計算の処理において、スカラー値とは独立に作成した前計算テーブルを用いて、楕円曲線上のτ倍算と加算を、スカラー値とは独立に一定の順序で実行する。これにより、サイドチャネル攻撃を防ぐことができ、高速演算可能なスカラー倍計算方法が利用可能である。【選択図】  図１
2006243690.tif 000002
【特許請求の範囲】
【請求項１】
楕円曲線上の加算と前記加算とは異なる第二の演算とを有する楕円曲線において、スカラー値、及び、前記楕円曲線上の点からスカラー倍点を計算する、楕円曲線暗号におけるスカラー倍計算装置であって、
前記スカラー値を数値列にエンコードするステップと、
前記楕円曲線上の点から前記スカラー値とは独立に前計算テーブルを作成するステップと、
前記数値列及び前記前計算テーブルから、前記楕円曲線上の加算と第二の演算を、前記スカラー値とは独立に一定の順序で実行することにより、前記スカラー倍点を計算するステップとを含む処理を行うことを特徴とするスカラー倍計算装置。
【請求項２】
楕円曲線上の加算と前記加算とは異なる第二の演算とを有する楕円曲線において、スカラー値、及び、前記楕円曲線上の点からスカラー倍点を計算する、楕円曲線暗号におけるスカラー倍計算装置であって、
前記楕円曲線上の点から前記スカラー値とは独立に前計算テーブルを作成するステップと、
前記前計算テーブルから、前記楕円曲線上の加算と第二の演算を、前記スカラー値とは独立に一定の順序で実行することにより、前記スカラー倍点を計算するステップとを含む処理を行うことを特徴とするスカラー倍計算装置。
【請求項３】
楕円曲線上の加算と前記加算とは異なる第二の演算とを有する楕円曲線において、あらかじめエンコードされたスカラー値、ウィンドウ幅、及び、楕円曲線上の点からスカラー倍点を計算する、楕円曲線暗号におけるスカラー倍計算装置であって、
前記楕円曲線上の点から前記スカラー値とは独立に前計算テーブルを作成するステップと、
前記前計算テーブルから、前記楕円曲線上の加算と第二の演算を、前記スカラー値とは独立に一定の順序で前記ウィンドウ幅に応じて実行することにより、前記スカラー倍点を計算するステップとを含む処理を行うことを特徴とするスカラー倍計算装置。
【請求項４】
請求項１記載のスカラー倍計算装置において、
更に、前記スカラー値を数値列にエンコードするステップは、前記スカラー値におけるΨ関数の値を計算するステップを含み、
前記Ψ関数は、前記スカラー値であるｄに対して、
Ψｗ(ｄ)＝（ｘＲ＋ｘＴ＊ｔｗ＋１  mod ２ｗ＋１）−２ｗ
で与えられ、
前記楕円曲線はコブリッツ曲線であり、前記第二の演算はτ倍算であることを特徴とするスカラー倍計算装置。
【請求項５】
請求項１〜３のいずれか一項に記載のスカラー倍計算装置において、
前記スカラー値とは独立に一定の順序で実行することにより、前記スカラー倍点を計算するステップは、
前記楕円曲線上の第二の演算をτとするとこの第二の演算τをあらかじめ定められた回数だけ実行する第一のステップと、
前記楕円曲線上の加算を実行する第二のステップとを有し、
前記第一と第二のステップを繰り返し行うことを特徴とするスカラー倍計算装置。
【請求項６】
請求項１または２に記載のスカラー倍計算装置において、
前記前計算テーブルは、前記楕円曲線上の点であるＰとあらかじめ定めた正の整数であるｗと前記楕円曲線上の第二の演算であるτとに対して、
Ｐ±τＰ±τ２Ｐ±……±τｗ−１Ｐ
からなることを特徴とするスカラー倍計算装置。
【請求項７】
請求項２記載のスカラー倍計算装置において、
前記スカラー値とは独立に一定の順序で実行することにより、前記スカラー倍点を計算するステップは、
前記前計算テーブルから読み出した点をシフトするステップを含むことを特徴とするスカラー倍計算装置。
【請求項８】
請求項２記載のスカラー倍計算装置において、
前記スカラー値とは独立に一定の順序で実行することにより、前記スカラー倍点を計算するステップは、
前記楕円曲線上の点から中間データを導出するステップと、
前記中間データをシフトするステップとを含むことを特徴とするスカラー倍計算装置。
【請求項９】
データからディジタル署名データを生成する署名生成装置であって、
請求項１〜３のいずれか一項に記載のスカラー倍計算装置を用いてスカラー倍を計算するステップを有する署名生成処理を行うことを特徴とする署名生成装置。
【請求項１０】
データからディジタル署名データを生成する署名生成装置であって、
乱数倍計算部を有し、
前記乱数倍計算部は、
楕円曲線上の点から前計算テーブルを作成するステップと、
あらかじめ定められた個数だけビットをランダムに選択し、前記ランダムに選択したビットから整数を生成するステップと、
前記生成した整数から、楕円曲線上の加算と第二の演算を、前記整数とは独立に一定の順序で実行するステップと、
前記整数を生成するステップ、及び、前記実行するステップを繰り返し行うステップと、
前記繰り返し行うステップにより、乱数と前記楕円曲線上の点との乱数倍点を出力するステップとを有する処理を行い、
前記乱数倍計算部の処理を用いて署名生成処理を行うことを特徴とする署名生成装置。
【請求項１１】
暗号化されたデータから復号化されたデータを生成する復号化装置であって、
請求項１〜３のいずれか一項に記載のスカラー倍計算装置を用いてスカラー倍を計算するステップを有する復号化処理を行うことを特徴とする復号化装置。
【請求項１２】
データから共有データを生成するデータ生成装置であって、
請求項１〜３のいずれか一項に記載のスカラー倍計算装置を用いてスカラー倍を計算するステップを有するデータ生成処理を行うことを特徴とするデータ生成装置。
【請求項１３】
請求項１〜３のいずれか一項に記載のスカラー倍計算装置による、スカラー倍計算を含む処理を、計算機に実行させることを特徴とするプログラム。
【請求項１４】
請求項９または１０に記載の署名生成装置による署名生成処理を計算機に実行させることを特徴とするプログラム。
【請求項１５】
請求項１１記載の復号化装置による復号化処理を計算機に実行させることを特徴とするプログラム。
【請求項１６】
請求項１２記載のデータ生成装置によるデータ生成処理を計算機に実行させることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、セキュリティ技術に関し、特に、楕円曲線演算を用いたメッセージ処理の技術に関する。
【背景技術】
【０００２】
楕円曲線暗号は、N. Koblitz, V. S. Millerにより提案された公開鍵暗号の一種である。公開鍵暗号には、公開鍵（Public Key）と呼ばれる一般公開してよい情報と、秘密鍵（Private Key）と呼ばれる秘匿しなければならない秘密情報がある。与えられたメッセージの暗号化や署名の検証には公開鍵を用い、与えられたメッセージの復号化や署名の生成には秘密鍵を用いる。
【０００３】
楕円曲線暗号における秘密鍵は、スカラー値が担っている。また、楕円曲線暗号の安全性は、楕円曲線上の離散対数問題の求解が困難であることに由来している。楕円曲線上の離散対数問題とは、楕円曲線上のある点Ｐとそのスカラー倍の点ｄＰが与えられた時、スカラー値ｄを求める問題である。楕円曲線上の点とは、楕円曲線の定義方程式を満たす数の組をいい、楕円曲線上の点全体には、無限遠点という仮想的な点を単位元とした演算、すなわち楕円曲線上の加法（乃至は加算）が定義される。
【０００４】
そして、同じ点同士による楕円曲線上の加法のことを、特に楕円曲線上の２倍算という。楕円曲線上の２点の加法は、次のようにして計算される。２点を通る直線を引くとその直線は楕円曲線と他の点において交わる。その交わった点とｘ軸に関して対称な点を、加法を行った結果の点とする。例えば、コブリッツ曲線の場合には、点（ｘ１，ｙ１）と点（ｘ２，ｙ２）の加算（ｘ３，ｙ３）＝（ｘ１，ｙ１）＋（ｘ２，ｙ２）は、下記（式１）〜（式３）を計算することにより得られる。
【０００５】
ｘ３＝λ２＋λ＋ｘ１＋ｘ２＋ａ                    ・・・（式１）
ｙ３＝（ｘ１＋ｘ３）λ＋ｘ３＋ｙ１                  ・・・（式２）
λ＝（ｙ１＋ｙ２）／（ｘ１＋ｘ２）                  ・・・（式３）
ここで、コブリッツ曲線の定義方程式は、下記（式４）で与えられる。
【０００６】
ｙ２＋ｘｙ＝ｘ３＋ａｘ２＋１，（ａ＝０ or １）      ・・・（式４）
すなわち、（式４）のｘ，ｙに、各々ｘｉ，ｙｉ（ｉ＝１，２，３）を代入した場合に、（式４）の等式が成り立つ。
【０００７】
楕円曲線上の点の２倍算は次のようにして計算される。楕円曲線上の点における接線をひくと、その接線は楕円曲線上の他の一点において交わる。その交わった点とｘ座標に関して対称な点を、２倍算を行った結果の点とする。例えば、コブリッツ曲線の場合には、点（ｘ１，ｙ１）の２倍算（ｘ３，ｙ３）＝２（ｘ１，ｙ１）＝（ｘ１，ｙ１）＋（ｘ１，ｙ１）は、（式１），（式２）及び下記（式５）を計算することにより得られる。
【０００８】
λ＝（ｙ１／ｘ１）＋ｘ１                              ・・・（式５）
また、コブリッツ曲線上の点に対して、τ倍算（タウ倍算）と呼ばれる演算を行うことが可能である。点（ｘ１，ｙ１）に対するτ倍算とは、下記（式６）を計算することである。
【０００９】
（ｘ３，ｙ３）＝τ（ｘ１，ｙ１）＝（ｘ１２，ｙ１２）        ・・・（式６）
また、下記（式７），（式８）が成り立つことが知られており、（式７）の性質により、τを、下記（式９）を満たす複素数と考えることができる。
【００１０】
（ｘ４，ｘ４）＋２（ｘ，ｙ）＝μ（ｘ２，ｙ２）          ・・・（式７）
μ＝(−１)ａ                                          ・・・（式８）
τ２＋２＝μτ                                        ・・・（式９）
楕円曲線上のある点に対し、特定の回数だけ加法を行うことをスカラー倍といい、その結果をスカラー倍点、その回数のことをスカラー値という。
【００１１】
楕円曲線暗号において標準化団体が推奨する楕円曲線は、ランダムな標数２の楕円曲線、コブリッツ曲線、及び、標数が大きな素体上の楕円曲線である。
【００１２】
楕円曲線上の離散対数問題の求解の困難性が理論的に確立されてきている一方で、実際の実装においては秘密鍵などの秘密情報に関連する情報、例えば計算時間や電力消費量などが暗号処理において漏洩する場合があり、その漏洩情報をもとに秘密情報を復元するといったサイドチャネル攻撃と呼ばれる攻撃法が提案されている。
【００１３】
楕円曲線暗号に対して、標準化団体の推奨する楕円曲線については、例えば、非特許文献１に記載されている。
【００１４】
楕円曲線暗号に対するサイドチャネル攻撃について、非特許文献２に記載されている。
【００１５】
楕円曲線暗号においては、与えられたメッセージの暗号化、復号化、署名の生成、検証は、楕円曲線演算を用いて行う必要がある。特に楕円曲線上のスカラー倍の計算は、秘密情報であるスカラー値を用いた暗号処理において用いられる。
【００１６】
楕円曲線暗号に対するサイドチャネル攻撃の防御法について、非特許文献３に記載されている。
【００１７】
コブリッツ曲線におけるスカラー倍の高速計算手法について、非特許文献４に記載されている。また、正規基底については、例えば、非特許文献４に記載されている。
【非特許文献１】D. Johnson, A. Menezes, “The Elliptic Curve Digital Signature Algorithm (ECDSA)”, Technial Report CORR 99-34, Dept. of C&O, University of Waterloo, Canada.［平成１７年２月１日検索］，＜ＵＲＬ＞http://www.cacr.math.uwaterloo.ca/techreports/1999/corr99-34.pdf
【非特許文献２】J.Coron, Resistance against Differential Power Analysis for Elliptic Curve Cryptosystems, Cryptographic Hardware and Embedded Systems: Proceedings of CHES'99, LNCS 1717, Springer-Verlag, (1999), pp.292-302.
【非特許文献３】K.Okeya, T.Takagi, The Width-w NAF Method Provides Small Memory and Fast Elliptic Scalar Multiplications Secure against Side Channel Attacks, RSA conference cryptographer's track (CT-RSA 2003), LNCS 2612, Springer-Verlag, (2003), pp.328-343.
【非特許文献４】J.A.Solinas, “Efficient Arithmetic on Koblitz Curves”, Designs, Codes and Cryptography, 19, (2000), pp.195-249.
【発明の開示】
【発明が解決しようとする課題】
【００１８】
情報通信ネットワークの進展と共に電子情報に対する秘匿や認証の為の暗号技術は不可欠な要素となってきている。暗号技術に課せられる要件としては、安全性以外にも、処理速度や少ないメモリ使用量などがあるが、一般的に、安全性、処理速度、メモリ使用量の間にはトレードオフの関係があり、すべての要件を満たすことは難しい。他方、楕円曲線上の離散対数問題が非常に困難である為に、素因数分解の困難性を安全性の根拠にしている暗号と比べて、楕円曲線暗号では鍵長を比較的短くすることができる。
【００１９】
そのため、楕円曲線暗号では、計算能力、メモリ容量などのリソースが比較的少なくても暗号処理を行うことが可能である。しかしながら、スマートカード（ＩＣカード等ともいう）等においては、利用可能なリソースは少なく、限られたリソース内で暗号処理を最適化する必要がある。前記非特許文献４などに記載されているように、コブリッツ曲線では、点のスカラー倍算についてはτ倍算を用いることによって高速演算が可能であることが知られており、スマートカードで用いるのに有効である。
【００２０】
前記非特許文献３の技術は、サイドチャネル攻撃を防ぐ方法として有効であり、コブリッツ曲線に対して適用できるが、τ倍算を用いた形では適用できない。
【００２１】
また、前記非特許文献４の技術は、コブリッツ曲線での高速計算手法としては有効であるが、サイドチャネル攻撃を防ぐという点については考慮されていない。
【００２２】
本発明は以上のような問題に鑑みてなされたものであり、その目的は、コブリッツ曲線に適用可能で、サイドチャネル攻撃を防ぐことができ、かつメモリ使用量及び処理高速性に優れた、楕円曲線暗号におけるスカラー倍を計算する技術を提供することにある。
【課題を解決するための手段】
【００２３】
本願において開示される発明のうち、代表的なものの概要を簡単に説明すれば、次のとおりである。前記目的を達成するために、本発明の楕円曲線暗号におけるスカラー倍を計算する技術は、以下に示す技術的手段を備えることを特徴とする。
【００２４】
本発明のスカラー倍計算方法は、楕円曲線上の加算（第一の演算とする）と前記加算とは異なる第二の演算とを有する楕円曲線において、スカラー値と楕円曲線上の点からスカラー倍点を計算する、楕円曲線暗号におけるスカラー倍を計算する方法であって、計算機資源を用いて、前記スカラー値を数値列にエンコードするステップと、前記楕円曲線上の点から前記スカラー値とは独立に前記前計算テーブル（後段の計算で使用するために前以て計算された値が格納された情報）を作成するステップと、前記エンコードした結果の数値列と前記前計算テーブルから、前記楕円曲線上の加算と第二の演算を、前記スカラー値とは独立に一定の順序で実行することにより、前記スカラー倍点を計算するステップとを有する処理を行う。
【００２５】
また、本発明のスカラー倍計算方法は、前記エンコードするステップは、前記スカラー値におけるΨ関数の値を計算するステップを含み、前記Ψ関数は、前記スカラー値ｄ＝ｘＲ＋ｘＴτに対して、Ψｗ(ｄ)＝（ｘＲ＋ｘＴ＊ｔｗ＋１  mod ２ｗ＋１）−２ｗで与えられる。ここで、ｗは、ウィンドウ幅と呼ばれる正の整数、ｘＲ，ｘＴは、整数、ｔｗ＋１は、コブリッツ曲線上の演算τを複素数とみなしたときにｗによって定まる整数である。なお、これらの記号の詳細については非特許文献４にも記載されている。
【００２６】
また、本発明の他のスカラー倍計算方法は、楕円曲線演算において、スカラー値と楕円曲線上の点からスカラー倍点を計算する方法であって、計算機資源を用いて、前記楕円曲線上の点から前記前計算テーブルを作成するステップと、前記スカラー値及び前記前計算テーブルからスカラー倍点を計算するステップとを有する処理を行う。
【００２７】
以上のような手段により、コブリッツ曲線において適用可能で、サイドチャネル攻撃を防ぐことができる、かつメモリ使用量に優れた及び高速計算可能で処理高速性に優れた、楕円曲線暗号におけるスカラー倍計算方法を利用可能にする。また、このスカラー倍計算方法を用いた、暗号化処理、復号化処理、署名生成処理、署名検証処理、鍵交換などのデータ共有のためのデータ生成処理などを利用可能にする。また本発明は、演算装置や記憶装置などの計算機資源を備え、それら処理を行う装置、及び、それら処理を計算機に実行させるプログラムを提供する。
【００２８】
本発明の方法、装置及びプログラムは、具体的には、以下のような特徴を有する。
【００２９】
（１）楕円曲線上の加算と前記加算とは異なる第二の演算とを有する楕円曲線において、スカラー値及び前記楕円曲線上の点からスカラー倍点を計算する、楕円曲線暗号におけるスカラー倍計算方法であって、前記スカラー値を数値列にエンコードするステップと、前記楕円曲線上の点から前記スカラー値とは独立に前計算テーブルを作成するステップと、前記数値列及び前記前計算テーブルから、前記楕円曲線上の加算と第二の演算を、前記スカラー値とは独立に一定の順序で実行することにより、前記スカラー倍点を計算するステップとを含むことを特徴とするスカラー倍計算方法。
【００３０】
（２）楕円曲線上の加算と前記加算とは異なる第二の演算とを有する楕円曲線において、スカラー値及び前記楕円曲線上の点からスカラー倍点を計算する、楕円曲線暗号におけるスカラー倍計算方法であって、前記楕円曲線上の点から前記スカラー値とは独立に前計算テーブルを作成するステップと、前記前計算テーブルから、前記楕円曲線上の加算と第二の演算を、前記スカラー値とは独立に一定の順序で実行することにより、前記スカラー倍点を計算するステップとを含むことを特徴とするスカラー倍計算方法。
【００３１】
（３）楕円曲線上の加算と前記加算とは異なる第二の演算とを有する楕円曲線において、あらかじめエンコードされたスカラー値、ウィンドウ幅、及び楕円曲線上の点からスカラー倍点を計算する、楕円曲線暗号におけるスカラー倍計算方法であって、前記楕円曲線上の点から前記スカラー値とは独立に前計算テーブルを作成するステップと、前記前計算テーブルから、前記楕円曲線上の加算と第二の演算を、前記スカラー値とは独立に一定の順序で前記ウィンドウ幅に応じて実行することにより、前記スカラー倍点を計算するステップとを含むことを特徴とするスカラー倍計算方法。
【００３２】
（４）前記楕円曲線はコブリッツ曲線であることを特徴とするスカラー倍計算方法。
【００３３】
（５）前記第二の演算はτ倍算であることを特徴とするスカラー倍計算方法。
【００３４】
（６）前記スカラー値とは独立に一定の順序で実行することにより、前記スカラー倍点を計算するステップは、前記楕円曲線上の第二の演算をτとするとこの第二の演算τをあらかじめ定められた回数だけ実行する第一のステップと、前記楕円曲線上の加算を実行する第二のステップとを有し、前記第一と第二のステップを繰り返し行うことを特徴とするスカラー倍計算方法。
【００３５】
（７）更に、前記スカラー値を数値列にエンコードするステップは、前記スカラー値におけるΨ関数の値を計算するステップを含み、前記Ψ関数は、前記スカラー値であるｄに対して、Ψｗ(ｄ)＝（ｘＲ＋ｘＴ＊ｔｗ＋１  mod ２ｗ＋１）−２ｗで与えられることを特徴とするスカラー倍計算方法。
【００３６】
（８）前記前計算テーブルは、前記楕円曲線上の点であるＰとあらかじめ定めた正の整数であるｗとに対して、｛Ｐ，３Ｐ，５Ｐ，……，（２ｗ−１）Ｐ｝からなることを特徴とするスカラー倍計算方法。
【００３７】
（９）前記前計算テーブルは、前記楕円曲線上の点であるＰとあらかじめ定めた正の整数であるｗと前記楕円曲線上の第二の演算であるτとに対して、Ｐ±τＰ±τ２Ｐ±……±τｗ−１Ｐからなることを特徴とするスカラー倍計算方法。
【００３８】
（１０）前記スカラー値とは独立に一定の順序で実行することにより、前記スカラー倍点を計算するステップは、前記前計算テーブルから読み出した点をシフトするステップを含むことを特徴とするスカラー倍計算方法。
【００３９】
（１１）前記スカラー値とは独立に一定の順序で実行することにより、前記スカラー倍点を計算するステップは、前記楕円曲線上の点から中間データを導出するステップと、前記中間データをシフトするステップとを含むことを特徴とするスカラー倍計算方法。
【００４０】
（１２）前記前計算テーブルを作成するステップは、前記前計算テーブルに格納するデータを生成するステップと、前記生成したデータをランダム化するステップと、前記ランダム化したデータを前記前計算テーブルに格納するステップとを含むことを特徴とするスカラー倍計算方法。
【００４１】
（１３）前記スカラー値とは独立に一定の順序で実行することにより、前記スカラー倍点を計算するステップは、前記前計算テーブルに格納されている点を読み出すステップと、前記読み出した点をランダム化するステップと、前記ランダム化した点を前記前計算テーブルに書き込むステップとを含むことを特徴とするスカラー倍計算方法。
【００４２】
（１４）データからディジタル署名データを生成する署名生成方法であって、前記スカラー倍計算方法を用いてスカラー倍を計算するステップを有することを特徴とする署名生成方法。
【００４３】
（１５）データからディジタル署名データを生成する署名生成方法であって、乱数倍計算部による処理ステップを有し、前記乱数倍計算部による処理ステップは、楕円曲線上の点から前計算テーブルを作成するステップと、あらかじめ定められた個数だけビットをランダムに選択し、前記ランダムに選択したビットから整数を生成するステップと、前記生成した整数から、楕円曲線上の加算と第二の演算を、前記整数とは独立に一定の順序で実行するステップと、前記整数を生成するステップ、及び、前記実行するステップを繰り返し行うステップと、前記繰り返し行うステップにより、乱数と前記楕円曲線上の点との乱数倍点を出力するステップとを有することを特徴とする署名生成方法。
【００４４】
（１６）暗号化されたデータから復号化されたデータを生成する復号化方法であって、前記スカラー倍計算方法を用いてスカラー倍を計算するステップを有することを特徴とする復号化方法。
【００４５】
（１７）データから共有データを生成するデータ生成方法であって、前記スカラー倍計算方法を用いてスカラー倍を計算するステップを有することを特徴とするデータ生成方法。
【００４６】
（１８）楕円曲線上の加算と前記加算とは異なる第二の演算τとを有する楕円曲線において、スカラー値及び楕円曲線上の点からスカラー倍点を計算する、楕円曲線暗号におけるスカラー倍計算装置であって、前記スカラー値を数値列にエンコードするエンコード部と、前記楕円曲線上の点から前記スカラー値とは独立に前計算テーブルを作成する前計算部と、前記数値列及び前記前計算テーブルから、前記楕円曲線上の加算と第二の演算τを、前記スカラー値とは独立に一定の順序で実行することにより、前記スカラー倍点を計算する実計算部とを具備することを特徴とするスカラー倍計算装置。
【００４７】
（１９）楕円曲線上の加算と前記加算とは異なる第二の演算τとを有する楕円曲線において、スカラー値及び楕円曲線上の点からスカラー倍点を計算する、楕円曲線暗号におけるスカラー倍計算装置であって、前記楕円曲線上の点から前記スカラー値とは独立に前計算テーブルを作成する前計算部と、前記前計算テーブルから前記楕円曲線上の加算と第二の演算τを、前記スカラー値とは独立に一定の順序で実行することにより、前記スカラー倍点を計算する実計算部とを具備することを特徴とするスカラー倍計算装置。
【００４８】
（２０）楕円曲線上の加算と前記加算とは異なる第二の演算τとを有する楕円曲線において、あらかじめエンコードされたスカラー値、ウィンドウ幅、及び楕円曲線上の点からスカラー倍点を計算する、楕円曲線暗号におけるスカラー倍計算装置であって、前記楕円曲線上の点から前記スカラー値とは独立に前計算テーブルを作成する前計算部と、前記前計算テーブルから、前記楕円曲線上の加算と第二の演算τを、前記ウィンドウ幅に応じて前記スカラー値とは独立に一定の順序で実行することにより、前記スカラー倍点を計算する実計算部とを具備することを特徴とするスカラー倍計算装置。
【００４９】
（２１）データからディジタル署名データを生成する署名生成処理部と、前記署名生成処理部より依頼されてスカラー倍を計算するスカラー倍計算部とを有する署名生成装置であって、前記スカラー倍計算部は、前記スカラー倍計算方法を用いてスカラー倍を計算するステップを有する処理を行うことを特徴とする署名生成装置。
【００５０】
（２２）データからディジタル署名データを生成する署名生成装置であって、乱数倍計算部を有し、前記乱数倍計算部は、楕円曲線上の点から前計算テーブルを作成する前計算部と、あらかじめ定められた個数だけビットをランダムに選択し、前記ランダムに選択したビットから整数を生成するステップと、前記生成された整数から、楕円曲線上の加算と第二の演算を、前記整数とは独立に一定の順序で実行するステップと、前記整数を生成するステップ、及び、前記実行するステップを繰り返し行うステップと、前記繰り返し行うステップにより、乱数と前記楕円曲線上の点との乱数倍点を出力するステップを含む処理を行う実計算部とを有することを特徴とする署名生成装置。
【００５１】
（２３）暗号化されたデータから復号化されたデータを生成する復号化処理部と、前記復号化処理部より依頼されてスカラー倍を計算するスカラー倍計算部とを有する復号化装置であって、前記スカラー倍計算部は、前記スカラー倍計算方法を用いてスカラー倍を計算するステップを有する処理を行うことを特徴とする復号化装置。
【００５２】
（２４）データから共有データを生成するデータ生成処理部と、前記データ生成処理部より依頼されてスカラー倍を計算するスカラー倍計算部とを有するデータ生成装置であって、前記データ生成処理部は、前記スカラー倍計算方法を用いてスカラー倍を計算するステップを有する処理を行うことを特徴とするデータ生成装置。
【００５３】
（２５）前記スカラー倍計算方法による処理を計算機に実行させることを特徴とするプログラム。
【００５４】
（２６）前記署名生成方法による処理を計算機に実行させることを特徴とするプログラム。
【００５５】
（２７）前記復号化方法による処理を計算機に実行させることを特徴とするプログラム。
【００５６】
（２８）前記データ生成方法による処理を計算機に実行させることを特徴とするプログラム。
【発明の効果】
【００５７】
本願において開示される発明のうち、代表的なものによって得られる効果を簡単に説明すれば以下のとおりである。本発明によれば、コブリッツ曲線に対して適用可能で、サイドチャネル攻撃を防ぐことができ安全で、かつメモリ使用量及び処理高速性に優れた、楕円曲線演算によるメッセージ処理が可能になる。
【発明を実施するための最良の形態】
【００５８】
以下、本発明の実施の形態を図面に基づいて詳細に説明する。なお、実施の形態を説明するための全図において、同一部には原則として同一符号を付し、その繰り返しの説明は省略する。図１〜図１６は、本発明の各実施の形態を説明するための図である。
【００５９】
＜システム構成＞
図１は、本発明の一実施の形態におけるスカラー倍計算装置であるコンピュータＡ１０１及びコンピュータＢ１２１と、これを含んで構成される情報処理システムの構成を示すものである。図１に示す構成は、各実施の形態で基本的に共通となる。本発明の実施の形態におけるスカラー倍計算装置は、本発明の実施の形態におけるスカラー倍計算方法に従ったスカラー倍計算処理を含んだ処理を実行するものであり、スカラー倍計算を用いた暗号化処理などを実行する。各コンピュータ（１０１，１２１）は、本発明の実施の形態におけるプログラムを実行することにより、スカラー倍計算処理を含む処理を行う。本情報処理システムは、スカラー倍計算方法を適用したコンピュータＡ１０１とコンピュータＢ１２１とがネットワーク１４２により接続されてなりネットワーク１４２を介してデータ・情報の授受を行う暗号通信システムを示している。
【００６０】
本暗号通信システムにおけるコンピュータＡ１０１でメッセージの暗号化を行うには、Ｐｍ＋ｋ（ｄＱ）及びｋＱを計算して出力する。そして、暗号文を入力したコンピュータＢ１２１で暗号文の復号化を行うには、秘密鍵ｄと前記ｋＱより−ｄ（ｋＱ）を計算し、入力された暗号文に対して、下記（式１０）を計算して出力すればよい。
【００６１】
（Ｐｍ＋ｋ（ｄＱ））−ｄ（ｋＱ）                  ・・・（式１０）
ここで、Ｐｍはメッセージ、ｋは乱数、ｄは秘密鍵を示す定数（スカラー値に対応する）、Ｑは定点、ｄＱは公開鍵を示す点（スカラー倍点に対応する）である。コンピュータＡ１０１は、秘密鍵ｄ、定点Ｑ、公開鍵ｄＱなどの情報を保持している。コンピュータＢ１０１は、秘密鍵ｄなどの情報を保持している。
【００６２】
データ１４１は、コンピュータＡ１０１からコンピュータＢ１２１に送信される。データ１４３は、コンピュータＢ１２１からコンピュータＡ１０１に送信される。ネットワーク１４２には、データとして、前記Ｐｍ＋ｋ（ｄＱ），ｋＱのみが送信され、メッセージＰｍを復元（復号化）するためには、ｋｄＱ、すなわちｋＱのｄ倍を計算する必要がある。ところが、秘密鍵ｄはネットワーク１４２には送信されないため、秘密鍵ｄを保持しているものだけが、メッセージＰｍを復元できることになる。
【００６３】
コンピュータＡ１０１は、ＣＰＵ１１３やコプロセッサ１１４などの演算装置、ＲＡＭ１０３、ＲＯＭ１０６や外部記憶装置１０７などの記憶装置、コンピュータ外部とのデータ入出力を行う入出力インタフェース１１０を装備しており、外部にはコンピュータＡ１０１をユーザが操作するための、出力装置であるディスプレイ１０８、入力装置であるキーボード１０９、その他図示しない着脱可能な可搬型記憶媒体の読み書き装置などが接続されている。
【００６４】
更に、コンピュータＡ１０１は、ＲＡＭ１０３、ＲＯＭ１０６や外部記憶装置１０７などの記憶装置によって、記憶部１０２を実現している。ＣＰＵ１１３やコプロセッサ１１４などの演算装置が、記憶部１０２に格納された本実施の形態のプログラムを実行することにより、処理部１１１として、データ処理部１１２、スカラー倍計算部１１５とそれらに含まれる各処理部を実現する。本実施の形態のプログラムは、スカラー倍計算方法に従った処理を行わせるための命令などが記述されたものである。データ処理部１１２は、各実施の形態に応じたメッセージ処理を行うもので、例えば実施の形態１においては暗号化処理部１１２として機能し、入力されたメッセージの暗号化を行う。
【００６５】
ＣＰＵ１１３は、コンピュータＡ１０１全体の制御を行う。コプロセッサ１１４は、ＣＰＵ１１３と協調して、特に数値演算を行う。各実施の形態では、これら２つの演算装置を利用してスカラー倍計算処理を含む目的の処理すなわち暗号化処理などを行う。ハードウェア構成としてはこれに限らずに、例えば１つのプロセッサを有する構成で目的の処理を行うようにすることも勿論可能である。また、ＰＣなどの汎用コンピュータ上で本発明の実施の形態のプログラムを実行させて他の処理と共に目的の処理を行わせる構成や、目的の処理を専用に実行するコンピュータ構成などのいずれも可能である。前記目的の処理とは、スカラー倍計算処理や、スカラー倍計算処理を用いてなされる暗号化処理、復号化処理、署名生成処理、署名検証処理、及び鍵交換などのデータ共有のためのデータ生成処理などを指し、これらについては後述する実施の形態で説明される。
【００６６】
スカラー倍計算部１１５は、データ処理部１１２からの依頼に従って、スカラー倍計算処理を含む処理を行う。スカラー倍計算部１１５は、実施の形態１などでは、暗号化処理部１１２で暗号化を行うのに必要なパラメータを計算する。
【００６７】
記憶部１０２は、定数１０４、秘密情報１０５などを記憶している。定数１０４は、例えば楕円曲線の定義式や楕円曲線上の定点などである。秘密情報１０５は、秘匿しなければならない情報であり、例えば秘密鍵の情報である。
【００６８】
コンピュータＢ１２１は、コンピュータＡ１０１と同様のハードウェア構成を備える。コンピュータＢ１２１は、ＣＰＵ１３３、コプロセッサ１３４、ＲＡＭ１２３、ＲＯＭ１２６、外部記憶装置１２７、入出力インタフェース１３０などを装備しており、外部にはディスプレイ１２８、キーボード１２９などが接続されている。なお、コンピュータＢ１２１をコンピュータＡ１０１と異なる構成として情報処理システムを構成することも可能である。
【００６９】
更に、コンピュータＢ１２１は、ＲＡＭ１２３、ＲＯＭ１２６や外部記憶装置１２７などの記憶装置によって、記憶部１２２を実現している。ＣＰＵ１３３やコプロセッサ１３４などの演算装置が、記憶部１２２に格納された本実施の形態のプログラムを実行することにより、処理部１３１として、データ処理部１３２、スカラー倍計算部１３５とそれらに含まれる各処理部を実現する。データ処理部１３２は、各実施の形態に応じたメッセージ処理を行うもので、実施の形態１などにおいては復号化処理部１３２として機能し、暗号化されたメッセージである暗号文（データ１４１に対応する）の復号化を行う。
【００７０】
スカラー倍計算部１３５は、データ処理部１３２からの依頼に従って、スカラー倍計算処理を含む処理を行う。スカラー倍計算部１３５は、実施の形態１などでは、復号化処理部１３２で復号化を行うのに必要なパラメータを計算する。記憶部１２２は、定数１２４（例えば楕円曲線の定義式や楕円曲線上の定点である）、秘密情報１２５（例えば秘密鍵の情報である）などを記憶している。
【００７１】
なお、上記各プログラムは、あらかじめ、上記コンピュータ（１０１，１２１）内の記憶部（１０２，１２２）に格納されていても良いし、必要なときに、入出力インタフェース（１１０，１３０）と上記コンピュータ（１０１，１２１）が利用可能な媒体を介して、他の装置から上記記憶部（１０２，１２２）に導入されてもよい。上記利用可能な媒体とは、例えば、入出力インタフェース（１１０，１３０）に対して着脱／入出力が可能な記憶媒体、または通信媒体（すなわちネットワークまたはネットワークを伝搬する搬送波）を指す。
【００７２】
＜暗号化シーケンス＞
次に、図２は、コンピュータＡ１０１及びコンピュータＢ１２１の各処理部間での情報の受け渡しの様子を示したシーケンス図である。まず、図２を参照しながら、前記図１のコンピュータＡ１０１が、入力されたメッセージを暗号化する場合の動作について説明する。処理対象となるメッセージは、ディジタル化されたデータであればよく、テキスト、画像、映像、音などの種類は問わない。
【００７３】
コンピュータＡ１０１において、まず、データ処理部（すなわち暗号化処理部）１１２は、入出力インタフェース１１０を介して、入力メッセージ（ステップＳ２０４）に対応する平文メッセージを受け取ると、入力された平文メッセージのビット長が、あらかじめ定めたビット長か否かを判断する。所定のビット長より長い場合には、所定のビット長となるように平文メッセージを区切る。
【００７４】
以下、所定のビット長に区切られている部分メッセージ（単にメッセージともいう）について説明する。暗号化処理部１１２は、メッセージのビット列によって表される数値をｘ座標（ｘｍ）に持つ楕円曲線上の点Ｐｍのy座標の値（ｙｍ）を計算する。コブリッツ曲線は（式４）で表わされるので、これよりy座標の値を求めることができる。
【００７５】
次に、暗号化処理部１１２は、乱数ｋを生成する。そして、記憶部１０２に格納されている定数１０４から読み出した公開鍵ｄＱと点Ｑのｘ座標と（Ｓ２０５）、求めたy座標の値と生成した乱数ｋとを、スカラー倍計算部１１５へ送る（Ｓ２０６）。スカラー倍計算部１１５は、点Ｑのｘ座標、y座標の値、及び乱数ｋによるスカラー倍点（ｘｄ１，ｙｄ１）＝ｋＱと、公開鍵ｄＱのｘ座標、y座標の値、及び乱数ｋによるスカラー倍点（ｘｄ２，ｙｄ２）＝ｋ（ｄＱ）とを計算し、計算されたスカラー倍点を、暗号化処理部１１２へ送る（Ｓ２０７）。
【００７６】
暗号化処理部１１２は、スカラー倍計算部１１５から送られたスカラー倍点を用いて、暗号化処理を行う。例えば、コブリッツ曲線では、ｋＱとＰｍ＋ｋ（ｄＱ）を計算する。すなわち、下記（式１１）〜（式１３）を計算し、暗号化されたメッセージｘｅ１，ｘｅ２を得る。
【００７７】
ｘｅ１＝ｘｄ１                                  ・・・（式１１）
ｘｅ２＝λ２＋λ＋ｘ１＋ｘｄ２＋ａ                ・・・（式１２）
λ＝（ｙ１＋ｙｄ２）／（ｘ１＋ｘｄ２）            ・・・（式１３）
コンピュータＡ１０１は、暗号化処理部１１２で暗号化された１つ以上の部分メッセージから、暗号化された出力メッセージ（Ｓ２０８に対応する）を組み立てる。
【００７８】
コンピュータＡ１０１は、暗号化された出力メッセージを、前記図１のデータ１４１として入出力インタフェース１１０より出力し、ネットワーク１４２を介してコンピュータＢ１２１へ転送する。
【００７９】
なお、図２における記憶部１０２からデータ処理部１１２への情報読み出し（Ｓ２０５）のタイミングは、スカラー倍計算部１１５へ当該情報を送る前であれば、入力メッセージ（Ｓ２０４）を受け付ける前であっても良い。
【００８０】
＜復号化シーケンス＞
次に、図２を参照しながら、コンピュータＢ１２１が、暗号化されたメッセージ（データ１４１）を復号化する場合の動作について説明する。
【００８１】
コンピュータＢ１２１において、まず、復号化処理部１３２は、入出力インタフェース１３０を介して、暗号化されたデータ１４１が入力されると（Ｓ２０４）、入力された暗号化されたデータ１４１のビット長が、あらかじめ定めたビット長か否かを判断する。所定のビット長より長い場合には、所定のビット長となるように、暗号化されたデータ１４１を区切る。
【００８２】
以下、所定のビット長に区切られている部分データ（単にデータともいう）について説明する。データ１４１のビット列によって表される数値をｘ座標に持つ楕円曲線上のｙ座標の値を計算する。暗号化されたメッセージがｘｅ１，ｘｅ２のビット列であり、コブリッツ曲線ではy座標の値ｙｅ１，ｙｅ２は、下記（式１４），（式１５）から得ることができる。
【００８３】
ｙｅ１２＋ｘｅ１ｙｅ１＝ｘｅ１３＋ａｘｅ１２＋１，ａ＝０ or １      ・・・（式１４）
ｙｅ２２＋ｘｅ２ｙｅ２＝ｘｅ２３＋ａｘｅ２２＋１，ａ＝０ or １      ・・・（式１５）
復号化処理部１３２は、記憶部１２２（図２の１０２）に格納されている秘密情報１２５から読み出した秘密鍵ｄと（Ｓ２０５）、x座標、y座標の値（ｘｅ１，ｙｅ１）を、スカラー倍計算部１３５（図２の１１５）へ送る（Ｓ２０６）。スカラー倍計算部１３５は、x座標、y座標の値、秘密鍵ｄからスカラー倍点（ｘｄ３，ｙｄ３）＝ｄ（ｘｅ１，ｙｅ１）を計算する。スカラー倍計算部１３５は、計算されたスカラー倍点（ｘｄ３，ｙｄ３）を復号化処理部１３２へ送る（Ｓ２０７）。
【００８４】
復号化処理部１３２は、スカラー倍計算部１３５から送られたスカラー倍点（ｘｄ３，ｙｄ３）を用いて、復号化処理を行う。例えば、暗号化されたメッセージが、ｘｅ１，ｘｅ２のビット列であり、コブリッツ曲線では、（Ｐｍ＋ｋ（ｄＱ））−ｄ（ｋＱ）＝（ｘｅ２，ｙｅ２）−（ｘｄ３，ｙｄ３）を計算することにより達成する。すなわち、下記（式１６），（式１７）を計算し、暗号化される前の部分メッセージｘｍに相当するｘｆ１を得る。
【００８５】
ｘｆ１＝λ２＋λ＋ｘｅ２＋ｘｄ３＋ａ                ・・・（式１６）
λ＝（ｙｅ２＋ｙｄ３）／（ｘｅ２＋ｘｄ３）            ・・・（式１７）
コンピュータＢ１２１は、復号化処理部１３２で復号化された部分メッセージから平文メッセージを組み立て、出力メッセージ（Ｓ２０８）として、入出力インタフェース１３０を介して、ディスプレイ１２８などから出力する。
【００８６】
次に、コンピュータＢ１２１が復号化処理を行う場合における、スカラー倍計算部１３５の処理を、以下に示す各実施の形態において詳細に説明する。各実施の形態で、本発明の実施の形態における復号化装置として機能するコンピュータＢ１２１は、本発明の実施の形態における復号化方法に従った復号化処理を行う。
【００８７】
（実施の形態１）
本発明の実施の形態１におけるスカラー倍計算方法、スカラー倍計算装置及びプログラムについて、図１〜図６を参照しながら説明する。
【００８８】
図３は、実施の形態１で用いるスカラー倍計算部１１５の機能ブロック構成を示す。図３に示すスカラー倍計算部１１５（図１のコンピュータＢ１２１のスカラー倍計算部１３５に対応する）は、エンコード部３０２、前計算部３０３、実計算部３０４からなる。エンコード部３０２は、剰余取得部３２１、剰余変換部３２２、繰り返し判定部３２３、δ剰余変換部３２４、Ψ関数計算部３２５、格納部３２６からなる。前計算部３０３は、加算部３３１、２倍算部３３２、繰り返し判定部３３３からなる。実計算部３０４は、ビット値判定部３４１、加算部３４２、τ倍算部３４３、繰り返し判定３４４からなる。
【００８９】
実施の形態１で用いるスカラー倍計算方法として、スカラー倍計算部１１５がスカラー値ｄ及び楕円曲線上の点Ｐから、楕円曲線におけるスカラー倍点ｄＰを計算する第１の計算方法を説明する。スカラー倍計算部１１５が復号化処理部１３２からスカラー値ｄと楕円曲線上の点Ｐを受け取ると、エンコード部３０２は、入力されたスカラー値ｄを数値列ｄｗ[j]にエンコードする。
【００９０】
これは、下記（式１８）を満たす整数ｄ’に対して、下記（式１９），（式２０）を満たすｄｗ[j]に、スカラー値ｄを変換することに相当する。
【００９１】
ｄＰ＝ｄ’Ｐ                              ・・・（式１８）
ｄ’＝ｄｗ[２ｎ]τ２ｎ＋ｄｗ[２ｎ−１]τ２ｎ−１＋……＋ｄｗ[ｊ]τｊ＋……＋ｄｗ[０]        ・・・（式１９）
−２ｗ＜ｄｗ[ｊ]＜２ｗ                        ・・・（式２０）
ここで、ｎはスカラー値ｄを２進表記した場合のビット長であり、ｗはあらかじめ定めた正の整数で、ウィンドウ幅と呼ばれる。計算時間（処理速度）を優先する場合はｗを大きな値にする。メモリ使用量を小さくする場合はｗを小さな値にする。
【００９２】
前計算部３０３は、入力された楕円曲線上の点Ｐから、前計算テーブルを作成する。前計算テーブルは、｛Ｐ，３Ｐ，５Ｐ，……，（２ｗ−１）Ｐ｝により構成される。
【００９３】
実計算部３０４は、数値列ｄｗ[j]にエンコードされたスカラー値と楕円曲線上の点Ｐから、前計算テーブルを用いてスカラー倍点ｄＰを計算する。
【００９４】
次に、エンコード部３０２、前計算部３０３、実計算部３０４の行う各処理について詳細に説明する。まず、図４を用いて、エンコード部３０２がスカラー値ｄをエンコードする方法を説明する。図４は、エンコード部３０２でのエンコード処理を示すフロー図である。
【００９５】
まず、δ剰余変換部３２４は、変数ｄ’にｄ mod δを代入する（ステップＳ４０１）。ただし、δとスカラー値ｄに対してｄ mod δの計算方法については、非特許文献４に記載されている。ｄ’＝ｄ mod δは、下記（式２１）なる形で表される。ここで、ｄ０，ｄ１は共に整数である。
【００９６】
ｄ’＝ｄ０＋ｄ１τ                            ・・・（式２１）
次に、変数ｉを０で初期化する（Ｓ４０２）。繰り返し判定部３２３は、変数ｄ’に対して、｜Rpart(ｄ’)｜＜２ｗかつTpart(ｄ’)＝０であるかどうかを判定する（Ｓ４０３）。ここで、スカラー値ｄ’＝ｄ０＋ｄ１τに対して、ｄ’の実部分Rpart(ｄ’)、及びτ部分Tpart(ｄ’)は、下記（式２２），（式２３）で与えられる整数である。
【００９７】
Rpart(ｄ’)＝ｄ０                              ・・・（式２２）
Tpart(ｄ’)＝ｄ１                              ・・・（式２３）
前記ステップＳ４０３で２つの条件が共に成立すれば（TRUE）、ステップＳ４２１へ移る。上記いずれかの条件が成立しない場合（FALSE）、ステップＳ４１１へ移る。
【００９８】
前記ステップＳ４１１では、Ψ関数計算部３２５は、スカラー値ｄ’の実部分Rpart(ｄ’)の、２ｗ＋１による剰余をｘＲに、スカラー値ｄ’のτ部分Tpart(ｄ’)の、２ｗ＋１による剰余をｘＴに、それぞれ代入する。
【００９９】
Ψ関数計算部３２５は、下記（式２４）を計算し変数ｕに格納する（Ｓ４１２）。なお記号＊は乗算を表わす。
【０１００】
Ψｗ(ｄ’)＝（ｘＲ＋ｘＴ＊ｔｗ＋１  mod ２ｗ＋１）−２ｗ          ・・・（式２４）
ここで、ｔｗ＋１は、下記（式２５）で与えられる整数であり、（式２５）におけるＵｗ＋１は、下記（式２６）で定まる整数である。
【０１０１】
ｔｗ＋１＝２ＵｗＵｗ＋１−１ mod ２ｗ＋１                        ・・・（式２５）
Ｕ０＝０，Ｕ１＝１，Ｕｗ＋１＝μＵｗ−２Ｕｗ−１              ・・・（式２６）
次に、格納部３２６は、ｄｗ[i]，ｄｗ[i+1]，……，ｄｗ[i+w-1]に、それぞれ、ｕ，０，０，……，０を格納する（Ｓ４１３）。次に、Ψ関数計算部３２５は、（ｄ’−ｕ）／τｗを計算し、その結果をｄ’に格納する（Ｓ４１４）。次に、変数ｉをｗ増加させ、ステップＳ４０３へ戻る（Ｓ４１５）。
【０１０２】
一方、ステップＳ４２１では、格納部３２６は、ｄｗ[i]，ｄｗ[i+1]，……，ｄｗ[n+w+a+2]に、それぞれ、Rpart(ｄ’)，０，０，……，０を格納する。次に、エンコード部３０２は、ｄｗ[n+w+a+2]，……，ｄｗ[0]を、実計算部３０４へ出力する（Ｓ４２２）。
【０１０３】
なお、前記ステップＳ４１４で、τでの除算を行うには、次のようにすればよい。ｄ’を入力とすると、τでの除算結果ｄ’／τは、下記（式２７）で与えられる。
【０１０４】
ｄ’／τ＝Tpart(ｄ’)＋Rpart(ｄ’)（μ−τ）／２          ・・・（式２７）
また、変数ｉの上限がｎ＋ｗ＋ａ＋２となる理由は以下の通りである。スカラー値ｄ’を（式１９）のように変換した際、変数ｉがｎ＋ａ＋３以下になることが、非特許文献３に記載されている。このスカラー値ｄ’の変換後の桁数はｗの倍数になっていなければならない。そのため、ｗ個の数値列ｄｗ[i]，ｄｗ[i+1]，……，ｄｗ[i+w-1]を組にしていくと、上位の桁数がｗ個より少ない可能性があり、その一番少ない場合はｎ＋ａ＋３桁目だけが残るという可能性である。従って、スカラー値ｄ’を（式１９）のように変換した際、変数ｉの値の上限はｎ＋ｗ＋ａ＋２となることがわかる。
【０１０５】
次に、図５を用いて、前計算部３０３が楕円曲線上の点から前計算テーブルを作成する方法を説明する。図５は、前計算部３０３での前計算テーブルの作成処理を示すフロー図である。
【０１０６】
まず、２倍算部３３２は、点Ｐを２倍し、その結果を２Ｐに格納する（Ｓ５０１）。なお２倍算を関数ＥＣＤＢＬで表している。次に、変数ｊに初期値１を代入する（Ｓ５０２）。次に、繰り返し判定部３３３により、ｊが２ｗより小さいかどうかを判定する（Ｓ５０３）。ｊ＜２ｗの場合は（TRUE）、ステップＳ５０４へ移る。ｊ≧２ｗの場合は（FALSE）、ステップＳ５１１へ移る。
【０１０７】
ステップＳ５０４では、加算部３３１は、点ｊＰと点２Ｐを加算し、その結果を（ｊ＋２）Ｐに格納する。なお加算を関数ＥＣＡＤＤで表わしている。次に、変数ｊを２増加させ、ステップＳ５０３へ戻る（Ｓ５０５）。
【０１０８】
一方、ステップＳ５１１では、｛Ｐ，３Ｐ，……，（２ｗ−１）Ｐ｝を前計算テーブルとして出力する。
【０１０９】
上記処理において、加算は（式１）〜（式３）を用いて、２倍算は（式１），（式２），（式５）を用いて、それぞれ計算される。なお、加算及び２倍算の計算には、これらの式を用いる以外にも、公知技術である射影座標やヤコビアン座標における計算公式を用いることもできる。
【０１１０】
また、楕円曲線上の点Ｑ＝（ｘ，ｙ）に対して、楕円曲線上の加算に関する逆元の点−Ｑは、コブリッツ曲線の場合、−Ｑ＝（ｘ，ｘ＋ｙ）と表されるため、点Ｑの座標が与えられていれば容易に計算できる。そのため、点｛Ｐ，３Ｐ，……，（２ｗ−１）Ｐ｝のみを前計算テーブルとして格納する。その後の実計算部３０４が行う計算で必要となる点｛−Ｐ，−３Ｐ，……，−（２ｗ−１）Ｐ｝については、それら格納された点から導出すればよいので、前計算テーブルには格納する必要はない。なお、上記点｛−Ｐ，−３Ｐ，……，−（２ｗ−１）Ｐ｝の導出を省くために、それら点のｙ座標の値のみを前計算テーブルに格納しておいてもよい。
【０１１１】
なお、前計算部３０３の行う前計算テーブルの作成処理は、点｛Ｐ，３Ｐ，……，（２ｗ−１）Ｐ｝が計算されればよい。そのため、非特許文献である、Cohen, H., A course in computational algebraic number theory, GTM138, Springer -Verlag, (1993)の４８１ページに記載されているモンゴメリトリックによる逆元演算共通化方法を用いて、楕円曲線演算で必要となる逆元演算の計算の共通化を行うことにより、高速化を図ってもよい。
【０１１２】
また、点Ｐが固定点である場合、前計算部３０３の行う前計算テーブルの作成処理は、ただ一度行えばよい。そのため、一旦、点｛Ｐ，３Ｐ，……，（２ｗ−１）Ｐ｝を計算すれば、それ以降のスカラー倍計算では、点｛Ｐ，３Ｐ，……，（２ｗ−１）Ｐ｝を再計算する必要はない。
【０１１３】
最後に、図６を用いて、実計算部３０４が、エンコードされたスカラー値、楕円曲線上の点及び前計算テーブルから、楕円曲線におけるスカラー倍点を計算する方法を説明する。図６は、実計算部３０４でのスカラー倍点の計算処理を示すフロー図である。
【０１１４】
まず、実計算部３０４は、変数ｃに、初期値ｎ＋ｗ＋ａ＋２を代入する（Ｓ６０１）。次に、繰り返し判定部３４４は、ｄｗ[c]が０か非０かを判定する（Ｓ６０２）。ｄｗ[c]が０の場合はステップＳ６０３へ移る。ｄｗ[c]が０でなければステップＳ６１１へ移る。
【０１１５】
ステップＳ６０３では、変数ｃを１減少させ、ステップＳ６０２へ戻る。
【０１１６】
一方、ステップＳ６１１では、点Ｑに、ｄｗ[c]Ｐを代入する。次に、変数ｊに、初期値ｃ−１を代入する（Ｓ６１２）。次に、繰り返し判定部３４４は、ｊが０より小さいかどうかを判定する。ｊが０より小さい場合はステップＳ６２１へ移る。ｊが０以上の場合はステップＳ６１４へ移る（Ｓ６１３）。
【０１１７】
ステップＳ６１４では、τ倍算部３４３は、点Ｑをτ倍し、点Ｑに再び格納する。次に、繰り返し判定部３４４は、ｄｗ[j]が０か非０かを判定する（Ｓ６１５）。ｄｗ[j]が０の場合はステップＳ６１７へ移る。ｄｗ[j]が０でなければステップＳ６１６へ移る。
【０１１８】
ステップＳ６１６では、加算部３４２は、点Ｑとｄｗ[j]Ｐを加算する。ただし、ｄｗ[j]が負の場合は(−ｄｗ[j])Ｐのｙ座標を反転したものを用いて加算を行う。そして加算の結果を点Ｑに格納し、ステップＳ６１７へ移る。
【０１１９】
なお、ｄｗ[j]が０でない場合は、ｄｗ[j]は（式２０）を満たす奇数である。そのため、ｄｗ[j]Ｐもしくは(−ｄｗ[j])Ｐのいずれかが、前計算テーブルに必ず存在する。
【０１２０】
ステップＳ６１７では、変数ｊを１減少させ、ステップＳ６１３へと戻る。一方、ステップＳ６２１では、点Ｑを出力する。処理は以上である。
【０１２１】
以上の処理において、エンコード部３０２が行う処理により出力される数値列ｄｗ[j]は、（式１８）〜（式２０）を満たす。この理由は次の通りである。
【０１２２】
前記図４のステップＳ４０１でｄ’にｄ mod δを代入している。そのため、適当な数ｋを用いてｄ’＝ｄ＋ｋδと表わすことができる。他方、コブリッツ曲線上ではδＰは無限遠点となることが知られており、そのため（式１８）が成立する。
【０１２３】
ステップＳ４０３からステップＳ４１５のループにおいて、ｊ回目のｄ’の値をｄ’[j]、ｕの値をｕ[j]とおく。すなわち、ステップＳ４１４で、下記（式２８）が計算される。
【０１２４】
ｄ’[ｊ＋１]＝（ｄ’[ｊ]−ｕ[ｊ]）／τｗ        ・・・（式２８）
０回目のループでは、下記（式２９）となる。１回目のループでは、下記（式３０）となる。以下同様にして、ｊ回目のループでは、下記（式３１）となる。
【０１２５】
ｄ’＝ｄ’[０]                                  ・・・（式２９）
ｄ’＝ｄ’[１]τｗ＋ｕ[０]                          ・・・（式３０）
ｄ’＝（……(ｄ’[ｊ]τｗ＋ｕ[ｊ])τｗ＋……＋ｕ[１]）τｗ＋ｕ[０]        ・・・（式３１）
ｄｗ[jw]以外のｄｗ[i]には０が割り当てられていることに注意すれば、ｄ’が（式１９）を満たすことがわかる。
【０１２６】
ステップＳ４１２で計算されるｕ[j]は、下記（式３２）の範囲となることは容易にわかる。
【０１２７】
−２ｗ ＜ｕ[ｊ]＜２ｗ                          ・・・（式３２）
従って、０以外のｄｗ[i]はｕ[j]が割り当てられる。従って、（式２０）を満たす。
【０１２８】
また、エンコード部３０２が行う処理で計算されるｕ[j]はｊ＝０を除きすべて奇数となる。この理由は次の通りである。
【０１２９】
前記ステップＳ４１１で、Rpart(ｄ’[j])が奇数であれば、ｔｗ＋１は偶数であることから、ｕ[j]は奇数となる。一方、ステップＳ４１４で、ｄ’[j+1]＝（ｄ’[j]−ｕ[j]）／τｗが計算される。下記（式３３）が成り立つため、Rpart(ｄ’[j+1])は奇数となる。
【０１３０】
ｄ’[ｊ]−((ｄ’[ｊ] mod τｗ)−τｗ) mod τｗ＋１＝τｗ        ・・・（式３３）
従って、ｊ＝０を除き、ｕ[j]はすべて奇数である。
【０１３１】
なお、ｕ[0]も奇数とするためには、スカラー値ｄの実部分Rpart(ｄ)が奇数であればよい。そのためには、入力されたスカラー値ｄの実部分Rpart(ｄ)が偶数の時は、ｄ＋１をあらためてスカラー値ｎとしてエンコードする。すなわち、ｄを奇数に変換する。そして、スカラー倍点ｎＰを計算する。下記（式３４）が成り立つため、ｎＰから点Ｐを引き、その値をスカラー倍点ｄＰとして出力すればよい。
【０１３２】
ｎＰ＝（ｄ＋１）Ｐ＝ｄＰ＋Ｐ                  ・・・（式３４）
また、入力されたｄの実部分Rpart(ｄ)が奇数の時は、ｄ＋τをあらためてスカラー値ｎとしてエンコードし、下記（式３５）を利用して、スカラー倍点ｄＰを求めてもよい。この場合、ｄがいずれの場合も、行う処理が一致するという利点がある。
【０１３３】
ｎＰ＝（ｄ＋τ）Ｐ＝ｄＰ＋τＰ                ・・・（式３５）
また、実計算部３０４が出力する点Ｑはスカラー倍点ｄＰに等しい。この理由は次の通りである。
【０１３４】
前記図６のステップＳ６１３において、点Ｑが、下記（式３５）と表されるとする。ここで、ｃはｄｗ[i]≠０を満たす最大のｉである。
【０１３５】
（ｄｗ[ｃ]τｃ−ｊ−１＋ｄｗ[ｃ−１]τｃ−ｊ−２＋……＋ｄｗ[ｊ＋１]）Ｐ        ・・・（式３６）
このとき、次にステップＳ６１３に来る時も点Ｑは（式３６）を満たすことを以下で示す。点Ｑは、ステップＳ６１４でτ倍され、ｄｗ[j]が０でなければステップＳ６１６でｄｗ[j]Ｐが加算される。そのためステップＳ６１６の直後では、点Ｑの値は、下記（式３７）となる。
【０１３６】
（ｄｗ[ｃ]τｃ−ｊ＋ｄｗ[ｃ−１]τｃ−ｊ−１＋……＋ｄｗ[ｊ＋１]τ＋ｄｗ[ｊ]）Ｐ        ・・・（式３７）
従って、ｄｗ[j]＝０の時も含めて、ステップＳ６１７の直前で、点Ｑは（式３７）を満たす。ステップＳ６１７でｊが１減少するので、（式３７）のｊにｊ＋１を代入すると（式３６）になる。すなわち、次にステップＳ６１３に来る時も点Ｑは（式３６）を満たす。
【０１３７】
ｊ＞ｃに対するｄｗ[j]の値は０であるので、ステップＳ６２１で出力される点Ｑの値は、下記（式３８）に等しい。
【０１３８】
（ｄｗ[ｃ]τｃ＋ｄｗ[ｃ−１]τｃ−１＋……＋ｄｗ[１]τ＋ｄｗ[０]）Ｐ        ・・・（式３８）
実計算部３０４に入力されるスカラー値は、エンコード部３０２によりエンコードされたｄｗ[j]であるので、そのｄｗ[j]は（式２０）を満たす。従って、Ｑ＝ｄＰである。
【０１３９】
また、上記スカラー倍計算方法は、サイドチャネル攻撃に対する防御法に関しても有効である。この理由は次の通りである。
【０１４０】
エンコード部３０２によりスカラー値ｄは数値列ｄｗ[i]にエンコードされる。ｉ＝ｎ＋ｗ＋ａ＋２からｉ＝０までｄｗ[i]を左から右に並べた数値列ｄｗ[n+w+a+2]……ｄｗ[0]は、下記（式３９）のようなパターンで表わされる。
【０１４１】
｜０……０ｘ｜０……０ｘ｜……｜０……０ｘ｜        ・・・（式３９）
ここで、各ｘは各々非０の値であり、それぞれ上記ｕ[j]に対応する。記号｜はパターンにおけるブロックの区切りを示す。ブロック｜０……０ｘ｜はｗ個の値であり、“０……０”は値がｗ−１個連続することを示す。
【０１４２】
実計算部３０４がスカラー倍点を計算する際に、ステップＳ６１３〜Ｓ６１７の繰り返し処理において、ブロック｜０……０ｘ｜に対応する楕円曲線演算は、｜Ｔ……ＴＡ｜、すなわちｗ−１回のＴの後にＡとなる。ただし、Ｔはτ倍算を、ＡはＥＣＡＤＤ（楕円曲線上の加算）をそれぞれ表わす。従って、すべてのスカラー値に対して、実行する楕円曲線演算は、下記（式４０）のように固定されている。
【０１４３】
｜Ｔ……ＴＡ｜Ｔ……ＴＡ｜……｜Ｔ……ＴＡ｜        ・・・（式４０）
そのため、（式４０）のみからは、スカラー値ｄに関する情報を引き出すことができない。すなわちサイドチャネル攻撃に対する防御性を有している。
【０１４４】
なお、実施の形態１に関して、非特許文献２に記載されているランダム化射影座標を併用してスカラー倍計算を行うこと（処理１とする）、スカラー倍計算を高速に行うために、前計算テーブルのサイズを大きくしてスカラー倍計算を行うこと（処理２とする）、及び、前計算テーブルに格納されている点が読み出されるたびに、再びランダム化して、前計算テーブルに書き込むこと（処理３とする）のいずれを行ってもよい。上記ランダム化を用いる処理によって、前計算テーブルに対する格納データがランダム化される。
【０１４５】
以上の通り、上記第１の計算方法は、コブリッツ曲線に対して適用可能で、サイドチャネル攻撃に有用な情報を与えないのでサイドチャネル攻撃に対して耐性があり、メモリ使用量及び処理高速性にも優れるという特徴及び効果がある。
【０１４６】
（実施の形態２）
本発明の実施の形態２におけるスカラー倍計算方法、スカラー倍計算装置及びプログラムについて、図１〜図３，図７，図８を参照しながら説明する。実施の形態２では、前記図３で示されるスカラー倍計算部１１５の機能ブロック構成を用いる。実施の形態２におけるスカラー倍計算部１１５（図１のスカラー倍計算部１３５に対応する）は、実施の形態１と同様の処理部を有する構成である。ただし、実施の形態２では、前計算部３０３において前記２倍算部３３２ではなくτ倍算部３３２を具備するものとする。
【０１４７】
実施の形態２で用いるスカラー倍計算方法として、スカラー倍計算部１１５がスカラー値ｄ及び楕円曲線上の点Ｐから、楕円曲線におけるスカラー倍点ｄＰを計算する第２の計算方法を説明する。第２の計算方法では、２倍算を用いずに加算とτ倍算を用いて前計算テーブルを作成できるという特徴がある。そのため、前計算部３０３は、２倍算部を具備する必要がない。
【０１４８】
スカラー倍計算部１１５が復号化処理部１３２からスカラー値ｄと楕円曲線上の点Ｐを受け取ると、エンコード部７０２は、入力されたスカラー値ｄを数値列ｄｗ[j]にエンコードする。ただし、実施の形態２では、ｄｗ[j]は（式１９）ではなく、下記（式４１）を満たす。ただし（式４１）の各符号はすべての組み合わせを表わす（すなわち正負いずれをとってもよい）ものとする。
【０１４９】
ｄｗ[ｊ]＝±１±τ±τ２±……±τｗ−１                  ・・・（式４１）
前計算部３０３は、入力された楕円曲線上の点Ｐから、前計算テーブルを作成する。前計算テーブルは、Ｐ±τＰ±Ｐτ２±……±τｗ−１Ｐより構成される。
【０１５０】
実計算部３０４は、エンコードされたスカラー値と楕円曲線上の点Ｐから、前計算テーブルを用いてスカラー倍点ｄＰを計算する。
【０１５１】
次に、エンコード部３０２、前計算部３０３、実計算部３０４の行う各処理について詳細に説明する。まず、図７を用いて、エンコード部３０２がスカラー値ｄをエンコードする方法を説明する。図７は、エンコード部３０２でのエンコード処理を示すフロー図である。
【０１５２】
まず、変数ｉを０で初期化する（Ｓ７０１）。次に、δ剰余変換部３２４は、変数ｄ’にｄ mod δを代入し、変数ｃ０にRpart(ｄ’)、変数ｃ１にTpart(ｄ’)をそれぞれ代入する（Ｓ７０２）。
【０１５３】
繰り返し判定部３２３は、条件｛ｃ０２＋μｃ０ｃ１＋２ｃ１２≧４／７＊２ｗ｝であるかどうかを判定する（Ｓ７０３）。これは、数ｃ０＋ｃ１τを数τｗで割ったときに商が０かどうかを判定している。この判定で上記条件が成立するのであれば（TRUE）、ステップＳ７０４へ移る。上記条件が成立しないのであれば（FALSE）、ステップＳ７１１へ移る。
【０１５４】
ステップＳ７０４では、Ψ関数計算部３２５は、Ψｗ(ｃ０＋ｃ１τ)を計算し、その結果をｕに格納する。更にｕをｄｗ[i]に、sign(ｕ)をｓに、｜ｕ｜をｕに、それぞれ代入し、変数ｉを１増加させる。ここで、sign(ｕ)は、ｕの符号である。
【０１５５】
次に、ｃ０にｃ０−ｓ＊ｂ０[(ｕ−１)／２]を、ｃ１にｃ１−ｓ＊ｂ１[(ｕ−１)／２]を、それぞれ代入する（Ｓ７０５）。ここで、ｂ０，ｂ１は、それぞれ以下の条件を満たす整数である。各βｊ＝１＋(−１)ｊ(１)τ＋(−１)ｊ(２)τ２＋……＋(−１)ｊ(ｗ−１)τｗ−１｛ｊ＝(ｊ(ｗ−１)……ｊ(０))２，ｊ(ｉ)＝０ or １｝に対して、βｊは、適当な数ｂ０，ｊ，ｂ１，ｊを用いてβｊ＝ｂ０，ｊ＋ｂ１，ｊτと表すことができる。ｕｊ＝Ψｗ(βｊ)とおき、ｕｊ＞０であれば、ｕ＝(ｕｊ−１)／２を満たすｊが存在するので、このｊに対してｂ０＝ｂ０，ｊ，ｂ１＝ｂ１，ｊとおく。ｕｊ＜０であれば、ｕ＝(−ｕｊ−１)／２を満たすｊが存在するので、このｊに対してｂ０＝−ｂ０，ｊ，ｂ１＝−ｂ１，ｊとおく。
【０１５６】
繰り返し判定部３２３は、ｊ≦ｗかどうかを判定する（Ｓ７０６）。ｊ≦ｗであれば（TRUE）、ステップＳ７０７へ移る。ｊ＞ｗであれば（FALSE）、ステップＳ７０３へ戻る。
【０１５７】
ステップＳ７０７では、変数ｃ０にｃ１＋μｃ０／２を、変数ｃ１に−ｃ０／２を、それぞれ代入する。
【０１５８】
ステップＳ７１１では、ステップＳ７０３〜Ｓ７０７のループを繰り返し行う度にステップＳ７０４で計算されるΨｗ(ｃ０＋ｃ１τ)をｄｗ[i]に格納する。
【０１５９】
ステップＳ７１２では、エンコード部３０２は、｛ｄｗ[c]，……，ｄｗ[0]｝を出力する。ここで、ｃはｄｗ[j]≠０を満たす最大のｊである。
【０１６０】
変数ｉの値の上限がｉ＋ｗ−１となる理由は、実施の形態１と同様である。
【０１６１】
次に、図８を用いて、前計算部３０３が楕円曲線上の点から前計算テーブルを作成する方法を説明する。図８は、前計算部３０３での前計算テーブル作成処理を示すフロー図である。
【０１６２】
前計算部３０３は、まず、変数Ｒに楕円曲線上の点Ｐを代入する（Ｓ８０１）。次に、変数ｉに初期値１を代入し、また集合Ｓに空集合｛｝を代入する（Ｓ８０２）。次に、繰り返し判定部３３３は、ｉがｗより小さいかどうかを判定する（Ｓ８０３）。この条件が成立する場合は、ステップＳ８０４へ移る。条件が成立しない場合は、ステップＳ８１１へ移る。
【０１６３】
ステップＳ８０４では、Ｒのすべての点Ｑに対して加算部３３１、τ倍算部３３２によりＰ±τＱを計算し、集合Ｓと２点Ｐ±τＱを集合Ｓに代入する。次に、ＳをＲに格納する（Ｓ８０５）。次に、変数ｉを１増加させ（Ｓ８０６）、ステップＳ８０３へ戻る。
【０１６４】
一方、ステップＳ８１１では、繰り返し判定部３３３により、ステップＳ８０３でｉがｗ以上の場合、楕円曲線上の点の集合Ｒを前計算テーブルとして出力する。
【０１６５】
スカラー倍計算部１１５で行われる演算は、τ倍算と加算のみであり、比較的処理の重い２倍算を用いずに前計算テーブルを作成できる。
【０１６６】
また、点−Ｐ±τＰ±Ｐτ２±……±τｗ−１Ｐを前計算テーブルには格納する必要がない理由も実施の形態１と同様であり、点−Ｐ±τＰ±Ｐτ２±……±τｗ−１Ｐの導出を省くために、それら点のｙ座標の値のみを前計算テーブルに格納しておいてもよい。
【０１６７】
なお、前計算部３０３の行う前計算テーブルの作成処理は、点Ｐ±τＰ±Ｐτ２±……±τｗ−１Ｐが計算されればよい。そのため、モンゴメリトリックによる逆元演算共通化方法を用いて、楕円曲線演算で必要となる逆元演算の計算の共通化を行うことにより、高速化を図ってもよい。
【０１６８】
また、点Ｐが固定点である場合、点Ｐ±τＰ±Ｐτ２±……±τｗ−１Ｐを再計算する必要がない理由も実施の形態１と同様である。前計算テーブル作成処理を、モンゴメリトリックを用いて、楕円曲線演算で必要となる逆元演算の計算の共通化を行うことにより、高速化を図ってもよいことも、第１の計算方法と同様である。
【０１６９】
最後に、実計算部３０４が、エンコードされたスカラー値と楕円曲線上の点から、楕円曲線におけるスカラー倍点を計算する方法を説明する。実計算部３０４が行う処理は、実施の形態１と同様の処理である。
【０１７０】
エンコード部３０２が行う処理により出力されるｄｗ[j]は、（式１８），（式２０）,（式４１）を満たす。（式１８）が成立する理由は、実施の形態１と同様である。ステップＳ７０３〜Ｓ７０７のループにおいて、ｉ回目に出力される値をｃ０，ｉ＋ｃ１，ｉτとする。その出力された値ｃ０，ｉ＋ｃ１，ｉτに対して、下記（式４２）とおき、ステップＳ７０６〜Ｓ７０７のループにおいて、ｂ０，ｂ１の値をそれぞれｂ０，ｉ，ｂ１，ｉ、とおき、ｕ[i]＝Ψｗ(ｂ０，ｉ＋ｂ１，ｉτ)，ｓ[i]＝sign(ｕ[i])とおく。ここで、sign(ｕ[i])は、ｕ[i]の符号を表すものである。
【０１７１】
Ψｗ(ｃ０，ｉ＋ｃ１，ｉτ)＝ｄｗ[ｉ＋１]                        ・・・（式４２）
ステップＳ７０６〜Ｓ７０７のループにおいて、下記（式４３）が計算される。（式４３）を変形すると、下記（式４４）が成り立つ。
【０１７２】
ｃ０，ｉ＋１＋ｃ１，ｉ＋１τ＝｛（ｃ０，ｉ＋ｃ１，ｉτ）−ｓ[i]（（|ｕ[i]|−１）／２）＊（ｂ０，ｉ＋ｂ１，ｉτ）｝／τｗ        ・・・（式４３）
（ｃ０，ｉ＋ｃ１，ｉτ）τｗ＝（ｃ０，ｉ＋１＋ｃ１，ｉ＋１τ）−ｓ[i]（（|ｕ[i]|−１）／２）＊（ｂ０，ｉ＋ｂ１，ｉτ）        ・・・（式４４）
（式４２）と（式４４）を用いると、ｄ’が（式１８）を満たすことがわかる。
【０１７３】
ステップＳ７１１においてΨｗ(ｃ０＋ｃ１τ)をｄｗ[i]に代入しており、Ψｗ(ｃ０＋ｃ１τ)＝（ｃ０＋ｃ１＊ｔｗ＋１mod ２ｗ＋１）−２ｗは、｜ｃ０＋ｃ１＊ｔｗ＋１mod ２ｗ＋１｜＜２ｗ＋１を満たすので、ｄｗ[i]は（式４１）を満たす。
【０１７４】
実計算部３０４が出力する点Ｑはスカラー倍点ｄＰに等しい。この理由は次の通りである。実施の形態１の実計算部３０４の行う処理と同様の処理を行う。
【０１７５】
前記ステップＳ６１３において点Ｑが、下記（式４５）と表されるとする。
【０１７６】
（ｄｗ[ｃ]τｃ−ｊ−１＋ｄｗ[ｃ−１]τｃ−ｊ−２＋……＋ｄｗ[ｊ＋１]）Ｐ        ・・・（式４５）
このとき、次にステップＳ６１３に来る時も点Ｑは（式４５）を満たすことを以下で示す。点ＱはステップＳ６１４でτ倍され、ｄｗ[j]が０でなければステップＳ６１６でｄｗ[j]Ｐが加えられる。そのためステップＳ６１６の直後では、点Ｑの値は、下記（式４６）となる。
【０１７７】
（ｄｗ[ｃ]τｃ−ｊ＋ｄｗ[ｃ−１]τｃ−ｊ−１＋……＋ｄｗ[ｊ＋１]τ＋ｄｗ[ｊ]）Ｐ        ・・・（式４６）
従って、ｄｗ[j]＝０の時も含めて、ステップＳ６１７の直前で、点Ｑは（式４６）を満たす。ステップＳ６１７でｊが１減少するので、（式４６）のｊにｊ＋１を代入すると（式４５）になる。すなわち、次にステップＳ６１３に来る時も点Ｑは（式４５）を満たす。ｊ＞ｃに対するｄｗ[ｊ]の値は０であるので、ステップＳ６２１で出力される点Ｑの値は、下記（式４７）に等しい。
【０１７８】
（ｄｗ[ｃ]τｃ＋ｄｗ[ｃ−１]τｃ−ｊ＋……＋ｄｗ[１]τ＋ｄｗ[０]）Ｐ        ・・・（式４７）
実計算部３０４に入力されるスカラー値は、エンコード部３０２によりエンコードされたｄｗ[j]であるので、そのｄｗ[j]は（式４１）を満たす。従って、Ｑ＝ｄＰである。
【０１７９】
また、上記第２の計算方法は、サイドチャネル攻撃に対する防御法に関しても有効である。この理由は次の通りである。エンコード部３０２によりスカラー値ｄは数値列ｄｗ[i]にエンコードされる。この数値列ｄｗ[i]はｄｗ[i]＝±１±τ±τ２±……±τｗ−１を満たす。
【０１８０】
すると、実計算部３０４がスカラー倍点を計算する際に、前記ステップＳ６１３〜Ｓ６１７の繰り返し処理に対応する楕円曲線演算は、｜Ｔ……ＴＡ｜、すなわちｗ−１回のＴの後にＡとなる。ただし、Ｔはτ倍算を、ＡはＥＣＡＤＤをそれぞれ表わす。これはｄｗ[i]がｄｗ[j]＝±１±τ±τ２±……±τｗ−１を満たすことより従う。
【０１８１】
従って、すべてのスカラー値に対して、実行する楕円曲線演算は実施の形態１と同様に、下記（式４８）と固定されている。そのため、（式４８）のみからは、スカラー値ｄに関する情報を引き出すことができない。
【０１８２】
｜Ｔ……ＴＡ｜Ｔ……ＴＡ｜……｜Ｔ……ＴＡ｜        ・・・（式４８）
なお、実施の形態２において、前記処理１〜処理３を用いてよいことも、実施の形態１と同様である。
【０１８３】
以上の通り、上記第２の計算方法は、コブリッツ曲線に対して適用可能で、サイドチャネル攻撃に有用な情報を与えないのでサイドチャネル攻撃に対して耐性があり、メモリ使用量及び処理高速性に優れるという特徴がある。
【０１８４】
（実施の形態３）
本発明の実施の形態３におけるスカラー倍計算方法、スカラー倍計算装置及びプログラムについて、図１，図２，図９，図１０を参照しながら説明する。実施の形態３では、図９で示されるスカラー倍計算部１１５の機能ブロック構成を用いる。実施の形態３におけるスカラー倍計算部１１５（図１のスカラー倍計算部１３５に対応する）は、前計算部９０２、実計算部９０３からなる。前計算部９０２は、加算部９２１、τ倍算部９２２、繰り返し判定部９２３からなる。実計算部９０３は、剰余取得部９３１、剰余変換部９３２、繰り返し判定部９３３、δ剰余変換部９３４、Ψ関数計算部９３５、ビット値判定部９３６、加算部９３７、τ倍算部９３８からなる。
【０１８５】
実施の形態３で用いるスカラー倍計算方法として、スカラー倍計算部１１５がスカラー値ｄ及び楕円曲線上の点Ｐから、楕円曲線におけるスカラー倍点ｄＰを計算する第３の計算方法を説明する。第３の計算方法では、スカラー値をエンコードした値を格納することなく、直接、スカラー倍算を計算できるという特徴がある。楕円曲線上の点Ｐ＝（ｘ，ｙ）は、ｘ，ｙをあらかじめ正規基底を用いて表しておけば、τ倍した点τ(Ｐ)は点Ｐの線形表現を左に１ビット分だけシフトした値、τ−１倍した点τ−１(Ｐ)は点Ｐの線形表現を右に１ビット分だけシフトした値になる。
【０１８６】
これより、点τｊｗ(ｄｗ[i]Ｐ)を計算するためには、まず、前計算テーブルから点ｄｗ[i]Ｐを呼び出し、点ｄｗ[i]Ｐのｘ座標、ｙ座標の値をそれぞれ左にｉｗビット分だけシフトさせればよい。従って、点Ｑを無限遠点Ｏで初期化し、点Ｑに点τｊｗ(ｄｗ[i]Ｐ)を足して、その値を点Ｑに代入するという操作を続けることによって、前記図３の格納部３２６のような格納部に値を格納することなく、直接、スカラー倍算を計算できる。これより、スカラー値ｄ及び楕円曲線上の点Ｐから、楕円曲線におけるスカラー倍点ｄＰを計算する際に、エンコード結果を格納するメモリを節約することができる。そのため、実計算部９０３は、格納部を具備する必要がない。
【０１８７】
スカラー倍計算部１１５が復号化処理部１３２からスカラー値ｄと楕円曲線上の点Ｐを受け取ると、実計算部９０３は、数値列ｄｗ[i]を計算する。このｄｗ[i]は実施の形態２で定義したｄｗ[i]と等しい。
【０１８８】
次に、前計算部９０２、実計算部９０３の行う各処理について詳細に説明する。前計算部９０２が楕円曲線上の点から、前計算テーブルを作成する方法は、実施の形態２と同様である。
【０１８９】
次に、図１０を用いて、実計算部９０３がスカラー値と楕円曲線上の点から前計算テーブルを用いて、楕円曲線におけるスカラー倍点を計算する方法を説明する。図１０は、実計算部９０３でのスカラー倍点の計算処理を示すフロー図である。
【０１９０】
実計算部９０３は、まず、変数ｉを０で初期化し、Ｑに無限遠点Ｏを代入する（Ｓ１００１）。次に、Ψ関数計算部９３５は、変数ｄ’にｄ mod δを代入し、ｃ０にｄ’の実部分Rpart(ｄ’)を、ｃ１にｄ’のτ部分Tpart(ｄ’)をそれぞれ代入する（Ｓ１００２）。
【０１９１】
次に、繰り返し判定部９３３は、条件｛ｃ０２＋μｃ０ｃ１＋２ｃ１２≧４／７＊２ｗ｝であるかどうかを判定する。条件が成立すれば（TRUE）、ステップＳ１００４へ移る。条件が成立しない場合は（FALSE）、ステップＳ１０１１へ移る（Ｓ１００３）。
【０１９２】
ステップＳ１００４では、剰余変換部９３２は、Ψｗ(ｃ０＋ｃ１τ)をｄｗ[i]に格納する。更に加算部９３７、τ倍算部９３８は、Ｑ＋τｉｗ(ｄｗ[i]Ｐ)を計算し、その値をＱに、sign(ｄｗ[i])をｓに、｜ｄｗ[i]｜をｄｗ[i]に、それぞれ代入して、変数ｉを１増加させる。次に、（ｃ０−ｓ＊ｂ０[(ｄｗ[i]−１)／２]，ｃ１−ｓ＊ｂ１[(ｄｗ[i]−１)／２]）を、（ｃ０，ｃ１）に代入する（Ｓ１００５）。
【０１９３】
次に、繰り返し判定部９３３は、ｊ≦ｗかどうかを判定する（Ｓ１００６）。ｊ≦ｗの場合（TRUE）、ステップＳ１００７へ移る。ｊ＞ｗの場合（FALSE）、ステップＳ１００３へ移る。
【０１９４】
ステップＳ１００７では、ｃ１＋μｃ０／２，−ｃ０／２をそれぞれｃ０，ｃ１に代入し、Ｓ１００６に戻る。
【０１９５】
一方、ステップＳ１０１１では、実計算部９０３は、点Ｑ＝ｄＰを出力する。
【０１９６】
また、変数ｉの値の上限がｉ＋ｗ−１となる理由は、実施の形態１及び２と同様である。また、実計算部９０３が行う処理により計算されるｄｗ[i]が、（式１８），（式１９），（式４１）を満たす理由も実施の形態２と同様である。
【０１９７】
また、実計算部９０３が出力する点Ｑはスカラー倍点ｄＰに等しい。この理由は次の通りである。
【０１９８】
前記ステップＳ１００４において点Ｑが、下記（式４９）と表されるとする。
【０１９９】
（ｄｗ[０]τｉ＋ｄｗ[１]τｉ＋１＋……＋ｄｗ[ｉ]τ２ｉ）Ｐ        ・・・（式４９）
このとき、次にステップＳ１００４に来る時も点Ｑは（式４９）を満たすことを以下で示す。ステップＳ１００３〜Ｓ１００７のループにおいて、i回目の直後では、点Ｑは（式４９）を満たす。また、ステップＳ１００３でｉにｉ＋１が代入されている。
【０２００】
従って、ステップＳ１００４の直後で出力される点Ｑの値は、下記（式５０）であり、（式５０）を整理すると、下記（式５１）である。
【０２０１】
（ｄｗ[０]＋ｄｗ[１]τ＋……＋ｄｗ[ｉ]τｉ）Ｐ＋(ｄｗ[ｉ＋１]τｉ＋１)Ｐ        ・・・（式５０）
（ｄｗ[０]＋ｄｗ[１]τ＋……＋ｄｗ[ｉ]τｉ＋１）Ｐ        ・・・（式５１）
従って、ｉ＋１回目にステップＳ１００４に来る時も点Ｑは（式４９）を満たす。
【０２０２】
ステップＳ１００３〜Ｓ１００７のループを抜け出すときのｉの値をｃ’とする。このとき、点Ｑの値は、下記（式５２）を満たす。
【０２０３】
（ｄｗ[０]＋ｄｗ[１]τ＋……＋ｄｗ[ｉ]τｃ’）Ｐ        ・・・（式５２）
一方、前記実施の形態２におけるスカラー値のエンコードを示す図７でのステップＳ７０３〜Ｓ７０７のループは、エンコードにおいては実施の形態３のステップＳ１００３〜Ｓ１００７までの操作と同様の操作を行っている。従って、下記（式５３）が成り立つ。
【０２０４】
ｃ’＝ｃ                ・・・（式５３）
これより実施の形態３で出力される点Ｑは実施の形態２の実計算部３０４の出力する値と等しい。従って、Ｑ＝ｄＰである。
【０２０５】
また、上記第３の計算方法は、サイドチャネル攻撃に対する防御法に関しても有効である。この理由は以下の通りである。
【０２０６】
実計算部９０３により、スカラー値ｄから、数値列ｄｗ[i]を計算する。この数値列ｄｗ[i]はｄｗ[i]＝±１±τ±τ２±……±τｗ−１を満たす。また、実計算部９０３はスカラー倍点を計算する際に、ステップＳ１００３〜Ｓ１００７の繰り返し処理に対応する楕円曲線演算は、｜Ｔ……ＴＡ｜、すなわちｉｗ−１回のＴの後にＡとなる。ただし、Ｔはτ倍算を、ＡはＥＣＡＤＤをそれぞれ表わす。これはｄｗ[i]がｄｗ[i]＝±１±τ±τ２±……±τｗ−１を満たすことより従う。
【０２０７】
従って、すべてのスカラー値に対して、実行する楕円曲線演算は、実施の形態１及び２と同様に、下記（式５４）と固定されている。そのため、（式５４）のみからは、スカラー値ｄに関する情報を引き出すことができない。
【０２０８】
｜Ｔ……ＴＡ｜Ｔ……ＴＡ｜……｜Ｔ……ＴＡ｜        ・・・（式５４）
なお、実施の形態３において、前記処理１〜処理３を用いてよいことも、実施の形態１及び２と同様である。
【０２０９】
以上の通り、上記第３の計算方法は、コブリッツ曲線に対して適用可能で、サイドチャネル攻撃に有用な情報を与えないのでサイドチャネル攻撃に対して耐性があり、メモリ使用量及び処理高速性に優れるという特徴がある。
【０２１０】
（実施の形態４）
本発明の実施の形態４におけるスカラー倍計算方法、スカラー倍計算装置及びプログラムについて、図１，図２，図９，図１１を参照しながら説明する。
【０２１１】
実施の形態４では、前記図９で示されるスカラー倍計算部１１５の機能ブロックを用いる。実施の形態４におけるスカラー倍計算部１１５（図１のスカラー倍計算部１３５に対応する）の構成は、実施の形態３と同様である。
【０２１２】
実施の形態４で用いるスカラー倍計算方法として、スカラー倍計算部１１５がスカラー値ｄ及び楕円曲線上の点Ｐから、楕円曲線におけるスカラー倍点ｄＰを計算する第４の計算方法を説明する。第４の計算方法では、第３の計算方法と同様に、スカラー値をエンコードした値を格納することなく、直接、スカラー倍算を計算できるという特徴がある。点τ−ｉｗ(Ｑ)を計算するためには、点Ｑのｘ座標、ｙ座標の値をあらかじめ正規基底を用いて表しておけば、点Ｑの各座標の値を右にｗビット分だけシフトさせればよい。
【０２１３】
従って、点Ｑを無限遠点Ｏで初期化し、前計算テーブルから点ｄｗ[i]Ｐを呼び出し、点τ−ｉｗ(Ｑ)に点ｄｗ[i]Ｐを足して、その値を点Ｑに代入するという操作を続けることによって、格納部に値を格納することなく、直接、スカラー倍算を計算できる。これより、スカラー値ｄ及び楕円曲線上の点Ｐから、楕円曲線におけるスカラー倍点ｄＰを計算する際に、エンコード結果を格納するメモリを節約することができる。そのため、実計算部９０２は、格納部を具備する必要がない。
【０２１４】
実施の形態３と実施の形態４の違いは以下の通りである。実施の形態３では、前計算テーブルから読み出された点の各座標の値をｉｗビット分だけシフトするのに対し、実施の形態４では、ワークメモリにある点Ｑ（中間データに相当する）の各座標の値をｗビット分だけシフトさせればよい。これにより、シフトさせる回数を節約することができる。
【０２１５】
次に前計算部９０２、実計算部９０３の行う各処理について詳細に説明する。前計算部９０２が楕円曲線上の点から、前計算テーブルを作成する方法は、実施の形態２及び３と同様である。
【０２１６】
次に、図１１を用いて、実計算部９０３がスカラー値と楕円曲線上の点から前計算テーブルを用いて、楕円曲線におけるスカラー倍点を計算する方法を説明する。図１１は、実計算部９０３でのスカラー倍点の計算処理を示すフロー図である。
【０２１７】
実計算部９０３は、まず、変数ｉを０で初期化し、Ｑに無限遠点Ｏを代入する（Ｓ１１０１）。次に、Ψ関数計算部９３５は、変数ｄ’にｄ mod δを代入し、ｃ０にｄ’の実部分Rpart(ｄ’)を、ｃ１にｄ’のτ部分Tpart(ｄ’)をそれぞれ代入する（Ｓ１１０２）。
【０２１８】
次に、繰り返し判定部９３３により条件｛ｃ０２＋μｃ０ｃ１＋２ｃ１２≧ ４／７＊２ｗ｝であるかどうかを判定する（Ｓ１１０３）。条件が成立すれば（TRUE）、ステップＳ１１０４へ移る。条件が成立しない場合は（FALSE）、ステップＳ１１１１へ移る。
【０２１９】
ステップＳ１１０４では、Ψ関数計算部９３５は、Ψｗ(ｃ０＋ｃ１τ)をｄｗ[i]に格納する。更に加算部９３７、τ倍算部９３８は、τ−ｗ(Ｑ)＋ｄｗ[i]Ｐを計算し、その値をＱに、sign(ｄｗ[i])をｓに、｜ｄｗ[i]｜をｄｗ[i]に、それぞれ代入して、変数ｉを１増加させる。次に、（ｃ０，ｃ１）に、（ｃ０−ｓ＊ｂ０[(ｄｗ[i]−１)／２]，ｃ１−ｓ＊ｂ１[(ｄｗ[i]−１)／２]）を代入する（Ｓ１１０５）。
【０２２０】
次に、繰り返し判定部９３３は、ｊ≦ｗかどうかを判定する（Ｓ１１０６）。ｊ≦ｗの場合は（TRUE）、ステップＳ１１０７へ移る。ｊ＞ｗの場合は（FALSE）、ステップＳ１１０３へ移る。
【０２２１】
ステップＳ１１０７では、（ｃ１＋μｃ０／２，−ｃ０／２）を（ｃ０，ｃ１）に代入し、Ｓ１１０６に戻る。
【０２２２】
一方、ステップＳ１１１１では、実計算部９０３は、点Ｑ＝ｄＰを出力する。
【０２２３】
また、変数ｉの値の上限がｉ＋ｗ−１となる理由は実施の形態３と同様である。また、実計算部９０３が行う処理により出力されるｄｗ[i]が、（式１８），（式１９），（式４１）を満たす理由も、実施の形態２及び３と同様である。
【０２２４】
また、実計算部９０３が出力する点Ｑはスカラー倍点ｄＰに等しい。この理由は次の通りである。
【０２２５】
前記ステップＳ１１０４において点Ｑが、下記（式５５）と表されるとする。
【０２２６】
（τ−ｉｗ(ｄｗ[０])＋τ−(ｉ−１)ｗ(ｄｗ[１])＋……＋τ−ｗ(ｄｗ[ｉ−１])＋ｄｗ[ｉ]）Ｐ        ・・・（式５５）
このとき、次にステップＳ１１０４に来る時も点Ｑは（式５５）を満たすことを以下で示す。ステップＳ１１０３〜Ｓ１１０７のループにおいて、ｉ回目の直後では、点Ｑは（式５５）を満たす。また、ステップＳ１１０３でｉにｉ＋１が代入されている。
【０２２７】
また、ステップＳ１１０４でｉにｉ＋１が代入されている。従って、ステップＳ１１０４の直後で出力される点Ｑの値は、下記（式５６）であり、（式５６）を整理すると、下記（式５７）となる。従って、ｉ＋１回目にステップＳ１１０４に来る時も点Ｑは（式５５）を満たす。
【０２２８】
τ−ｗ(τ−ｉｗ(ｄｗ[０])＋τ−(ｉ−１)ｗ(ｄｗ[１])＋……＋τ−ｗ(ｄｗ[ｉ−１])＋ｄｗ[ｉ])Ｐ＋(ｄｗ[ｉ＋１])Ｐ        ・・・（式５６）
（τ−(ｉ＋１)ｗ(ｄｗ[０])＋τ−ｉｗ(ｄｗ[１])＋……＋τ−ｗ(ｄｗ[ｉ])＋ｄｗ[ｉ＋１]）Ｐ        ・・・（式５７）
ステップＳ１１０３〜Ｓ１１０７のループを抜け出すときのｉの値をｃ’とする。このとき、点Ｑの値は、下記（式５８）を満たす。
【０２２９】
（τ−ｃｗ(ｄｗ[０])＋τ−(ｃ−１)ｗ(ｄｗ[１])＋……＋τ−ｗ(ｄｗ[ｃ−１])＋ｄｗ[ｃ]）Ｐ        ・・・（式５８）
一方、前記実施の形態２におけるスカラー値のエンコードを示す図７でのステップＳ７０３〜Ｓ７０７のループは、エンコードにおいては実施の形態４と同様の操作を行っている。従って、下記（式５９）が成り立つ。
【０２３０】
ｃ’＝ｃ                          ・・・（式５９）
これより実施の形態４で出力される点Ｑは実施の形態２の実計算部３０４の出力する値と等しい。従って、Ｑ＝ｄＰである。
【０２３１】
また、上記第４の計算方法は、サイドチャネル攻撃に対する防御法に関しても有効である。この理由は以下の通りである。
【０２３２】
実計算部９０３により、スカラー値ｄから、数値列ｄｗ[i]を計算する。この数値列ｄｗ[i]はｄｗ[i]＝±１±τ±τ２±……±τｗ−１を満たす。また、実計算部９０３はスカラー倍点を計算する際に、ステップＳ１１０３〜Ｓ１１０７の繰り返し処理に対応する楕円曲線演算は、｜Ｔ……ＴＡ｜、すなわちｗ−１回のＴの後にＡとなる。ただし、Ｔはτ倍算を、ＡはＥＣＡＤＤをそれぞれ表わす。これはｄｗ[i]がｄｗ[i]＝±１±τ±τ２±……±τｗ−１を満たすことより従う。
【０２３３】
従って、すべてのスカラー値に対して、実行する楕円曲線演算は、実施の形態１及び２と同様に、下記（式６０）と固定されている。そのため、（式６０）のみからは、スカラー値ｄに関する情報を引き出すことができない。
【０２３４】
｜Ｔ……ＴＡ｜Ｔ……ＴＡ｜……｜Ｔ……ＴＡ｜        ・・・（式６０）
なお、実施の形態４において、前記処理１〜処理３を用いてよいことも、実施の形態１、２及び３と同様である。
【０２３５】
以上の通り、上記第４の計算方法は、コブリッツ曲線に対して適用可能で、サイドチャネル攻撃に有用な情報を与えないのでサイドチャネル攻撃に対して耐性があり、メモリ使用量及び処理高速性に優れるという特徴がある。
【０２３６】
（実施の形態５）
本発明の実施の形態５におけるスカラー倍計算方法、スカラー倍計算装置及びプログラムについて、図１〜図４を参照しながら説明する。
【０２３７】
実施の形態５では、前記図３で示されるスカラー倍計算部１１５の機能ブロックを用いる。実施の形態５におけるスカラー倍計算部１１５（図１のスカラー倍計算部１３５に対応する）の構成は、実施の形態１及び２と同様である。
【０２３８】
実施の形態５で用いるスカラー倍計算方法として、スカラー倍計算部１１５がスカラー値ｄ及び楕円曲線上の点Ｐから、楕円曲線におけるスカラー倍点ｄＰを計算する第５の計算方法を説明する。第５の計算方法では、サイドチャネル攻撃に対する防御法として有効なコブリッツ曲線以外の楕円曲線のスカラー倍計算方法を説明する。
【０２３９】
上記のような楕円曲線の例として、下記（式６１）という定義式を持つ楕円曲線を考える。
【０２４０】
ｙ２＝ｘ３−ｂ（ｂ≠０）                              ・・・（式６１）
この楕円曲線上の点に対して、フロベニウス写像τと呼ばれる演算を行うことが可能である。点（ｘ１，ｙ１）に対するフロベニウス写像τとは、下記（式６２）を計算することである。τを、下記（式６３）を満たす虚部が正である複素数と考えることができる。
【０２４１】
（ｘ３，ｙ３）＝τ（ｘ１，ｙ１）＝（ｘ１７，ｙ１７）        ・・・（式６２）
τ２−ｔτ＋７＝０                                    ・・・（式６３）
ここで、複素数ａ＋ｂｉ（ここでｉは虚数単位）の虚部とは実数ｂのことであり、ｔは楕円曲線におけるトレースと呼ばれる整数である。ただし、ｔｗ＋１は、下記（式６４）で与えられる整数であり、Ｕｗ＋１は、下記（式６５）で定まる整数である。
【０２４２】
ｔｗ＋１＝７ＵｗＵｗ＋１−１ mod ７ｗ＋１                    ・・・（式６４）
Ｕ０＝０，Ｕ１＝１，Ｕｗ＋１＝ｔＵｗ−７Ｕｗ−１            ・・・（式６５）
実施の形態１において、スカラー値ｄを数値列ｄｗ[i]にエンコードする操作は、スカラー値ｄを、余りが出るまでτｗで割り続けることに相当する。従って、スカラー値ｄがτｗで割り算を行うことができれば、コブリッツ曲線以外の楕円曲線のスカラー倍計算においてサイドチャネル攻撃に対する防御法を構成することができるということになる。
【０２４３】
スカラー倍計算部１１５が、復号化処理部１３２からスカラー値ｄと楕円曲線上の点Ｐを受け取ると、エンコード部３０２は、入力されたスカラー値ｄを数値列ｄｗ[i]にエンコードする。これは、下記（式６６）を満たす整数ｄ’に対して、下記（式６７），（式６８）を満たすｄｗ[i]に、スカラー値ｄを変換することに相当する。
【０２４４】
ｄＰ＝ｄ’Ｐ                      ・・・（式６６）
ｄ’＝ｄｗ[２ｎ]τ２ｎ＋ｄｗ[２ｎ−１]τ２ｎ−１＋……＋ｄｗ[ｉ]τｉ＋……＋ｄｗ[０]        ・・・（式６７）
−７ｗ＜ｄｗ[ｉ]＜７ｗ            ・・・（式６８）
前計算部３０３は、入力された楕円曲線上の点Ｐから、前計算テーブルを作成する。前計算テーブルは｛Ｐ，２Ｐ，……，（７ｗ−１）Ｐ｝により構成される。ただし、点ｋＰ（ｋ＝７，７２，……，７ｗ−１）は前計算テーブルには含まれていない。
【０２４５】
実計算部３０４は、エンコードされたスカラー値と楕円曲線上の点Ｐから、前計算テーブルを用いてスカラー倍点ｄＰを計算する。
【０２４６】
次に、エンコード部３０２、前計算部３０３、実計算部３０４の行う各処理について詳細に説明する。
【０２４７】
エンコード部３０２がスカラー値ｄをエンコードする方法は、実施の形態１と同様である。ただし、前記ステップＳ４０１において、δは、下記（式６９）を満たす数であり、ここでｍは、拡大次数と呼ばれる整数である。
【０２４８】
δ＝（τｍ−１）／（τ−１）                ・・・（式６９）
ｄ mod δの計算方法は以下の通りである。δは（式６９）を用いることによって、下記（式７０）と変形することができる。ここで、δ０，δ１は整数である。
【０２４９】
δ＝δ０＋δ１τ                            ・・・（式７０）
スカラー値ｄは、下記（式７１）と書くことができる。ここで、ｄ０，ｄ１は整数である。
【０２５０】
ｄ＝ｄ０＋ｄ１τ                            ・・・（式７１）
このとき、ｄmod δは、下記（式７２）を満たす数である。
【０２５１】
ｄ mod δ＝ｒ０＋ｒ１τ                      ・・・（式７２）
ただし、ｒ０，ｒ１はそれぞれ下記（式７３），（式７４）を満たす整数であり、ｑ０，ｑ１は下記（式７５），（式７６）を満たす数である。
【０２５２】
ｒ０＝ｄ０−δ０ｑ０＋７δ１ｑ１                ・・・（式７３）
ｒ１＝ｄ１−δ１ｑ０−δ０ｑ１−ｔδ１ｑ１        ・・・（式７４）
ｑ０＝ Round(λ０)                          ・・・（式７５）
ｑ１＝ Round(λ１)                          ・・・（式７６）
ここで、λ０，λ１は、λ０＝ｇ０／Ｎ，λ１＝ｇ１／Ｎを満たす数（有理数）であり、数λに対してRound(λ)は、λ＋１／２を超えない最大の整数である。また、ｇ０，ｇ１，Ｎは、それぞれ下記（式７７），（式７８），（式７９）で与えられる整数である。
【０２５３】
ｇ０＝ｄ０δ０＋ｔｄ０δ１＋７ｄ１δ１          ・・・（式７７）
ｇ１＝ｄ１δ０−ｄ０δ１                      ・・・（式７８）
Ｎ＝δ０２＋ｔδ０δ１＋７δ１２                ・・・（式７９）
また、前記ステップＳ４０３の分岐条件は、｜Rpart(ｄ’)｜＜２ｗ及びTpart(ｄ’)＝０ではなく、｜Rpart(ｄ’)｜＜７ｗ及びTpart(ｄ’)＝０である。ステップＳ４１１は、Rpart(ｄ’) mod ２ｗ＋１をｘＲに代入、及びTpart(ｄ’) mod ２ｗ＋１をｘＴに代入ではなく、Rpart(ｄ’) mod ７ｗ＋１をｘＲに代入、Tpart(ｄ’) mod ７ｗ＋１をｘＴに代入する。ステップＳ４１２では、（ｘＲ＋ｘＴ＊ｔｗ＋１mod ２ｗ＋１）−２ｗをｕに代入ではなく、（ｘＲ＋ｘＴ＊ｔｗ＋１mod ７ｗ＋１）−７ｗをｕに代入する。
【０２５４】
ここで、ｔｗ＋１は、下記（式８０）で与えられる整数であり、Ｕｗ＋１は、下記（式８１）で定まる整数である。
【０２５５】
ｔｗ＋１＝７ＵｗＵｗ＋１−１ mod ７ｗ＋１                  ・・・（式８０）
Ｕ０＝０，Ｕ１＝１，Ｕｗ＋１＝ｔＵｗ−７Ｕｗ−１        ・・・（式８１）
前計算部３０３が楕円曲線上の点から前計算テーブルを作成する方法は、実施の形態１と同様である。ただし、前記ステップＳ５０３の分岐条件は、ｊ＜２ｗではなく、ｊ＜７ｗである。
【０２５６】
また、実計算部Ｓ３０４が、エンコードされたスカラー値、楕円曲線上の点及び前計算テーブルから、楕円曲線におけるスカラー倍点を計算する方法も、実施の形態１と同様である。ただし、実施の形態５におけるτ倍算部３４３のτは、（式９）ではなく、（式６３）を満たす。エンコード部３０２が行う処理により出力されるｄｗ[i]は、（式６６），（式６７），（式６８）を満たす。（式６６），（式６７）が成立する理由は、実施の形態１と同様である。
【０２５７】
前記ステップＳ４１２で計算されるｕ[j]は、下記（式８２）の範囲となることは容易にわかる。従って、０以外のｄｗ[i]はｕ[j]が割り当てられる。従って、（式６８）を満たす。
【０２５８】
−７ｗ＜ｕ[ｊ]＜ ７ｗ                        ・・・（式８２）
エンコード部３０２が行う処理で計算されるｕ[j]は、ｊ＝０を除きすべて７の倍数となり、実計算部３０４が出力する点Ｑはスカラー倍点ｄＰに等しい。この理由も実施の形態１と同様である。また、上記第５の計算方法は、サイドチャネル攻撃に対する防御法に関しても有効である。この理由も実施の形態１と同様である。
【０２５９】
実施の形態５において、前記処理１〜処理３を用いてよいことも、実施の形態１〜４と同様である。
【０２６０】
前記（式６１）以外の楕円曲線の例を挙げる。楕円曲線Ｅを、非特許文献である、R. P. Gallant, J. L. Lambert, and S. A. Vanstone “Faster Point Multiplication on Elliptic Curves with Efficient Endomorphisms”, In J. Kilian, editor, Advances in Cryptology - Proceedings of CRYPTO 2001, volume 2139 of Lecture Notes in Computer Science, 190-200. Springer, 2001.に記載の楕円曲線とすると、点Ｐ、スカラー値ｄに対するスカラー倍算ｄＰは、下記（式８３）を計算すればよいことが知られている。
【０２６１】
ｄＰ＝ｋ１Ｐ＋ｋ２ΨＰ                          ・・・（式８３）
ここで、ｋ１，ｋ２は、０から√ｎまでの範囲にある正の整数、ΨはＥの自己準同型写像、ｎは点Ｐの位数である。整数ｋ１，ｋ２に対して（式８３）の操作を繰り返し行うことによって、スカラー値ｄを実施の形態１〜４のいずれか一つに記載の形に変換できる。このとき、すべてのスカラー値に対して、実行する楕円曲線演算は、下記（式８４）と固定されている。ただし、Ψは自己準同型演算を表わす。そのため、（式８４）のみからは、スカラー値ｄに関する情報を引き出すことができない。
【０２６２】
｜Ψ……ΨＡ｜Ψ……ΨＡ｜……｜Ψ……ΨＡ｜        ・・・（式８４）
以上の通り、上記第５の計算方法は、サイドチャネル攻撃に有用な情報を与えないのでサイドチャネル攻撃に対して耐性があり、コブリッツ曲線以外の楕円曲線に対しても適用可能であり、メモリ使用量及び処理高速性に優れるという特徴がある。
【０２６３】
（実施の形態６）
本発明の実施の形態６におけるスカラー倍計算方法、スカラー倍計算装置及びプログラムについて、図１，図２，図９，図１２を参照しながら説明する。
【０２６４】
実施の形態６では、前記図９で示されるスカラー倍計算部１１５の機能ブロックを用いる。実施の形態６におけるスカラー倍計算部１１５（図１のスカラー倍計算部１３５に対応する）の構成は、実施の形態３及び４と同様である。ただし、実施の形態６では、前記図９における前計算部９０２のτ倍算部９２２ではなく２倍算部９２２を具備するものとする。
【０２６５】
実施の形態６で用いるスカラー倍計算方法として、スカラー倍計算部１１５がスカラー値ｄ、楕円曲線上の点Ｐ、及び、ウィンドウ幅ｗから、楕円曲線におけるスカラー倍点ｄＰを計算する第６の計算方法を説明する。第６の計算方法では、スカラー値ｄはバイナリτ進表現で格納されているとする。ここで、スカラー値ｄのバイナリτ進表現とは、下記（式８５），（式８６）なる表現のことである。
【０２６６】
ｄ＝ｄｗ[ｎ＋ａ−１]τｎ＋ａ−１＋ｄｗ[ｎ＋ａ−２]τｎ＋ａ−２＋……＋ｄｗ[ｉ]τｉ＋……＋ｄｗ[０]        ・・・（式８５）
ｄｗ[ｉ]＝０またはｄｗ[ｉ]＝１        ・・・（式８６）
このとき、スカラー値ｄのバイナリ表現は、通常のバイナリ表現と同様に、メモリに格納しやすく、スカラー値ｄを他の表現に変換しやすいという特徴を持つ。また、スカラー倍点ｄＰの計算毎にウィンドウ幅ｗを変更することが可能である。
【０２６７】
処理速度とメモリ使用量の間にはトレードオフの関係があるから、状況に合わせたウィンドウ幅の選択を可能にする。
【０２６８】
また、実施の形態６における楕円曲線上のスカラー倍計算において、スカラー値ｄはバイナリτ進表現で格納されているから、最上位ビットから最下位ビットに向けて（left-to-right）処理を行うことを可能にする。
【０２６９】
次に、前計算部９０２、実計算部９０３の行う各処理について詳細に説明する。前計算部９０２が楕円曲線上の点Ｐから前計算テーブルを作成する方法は、実施の形態１及び５と同様である。
【０２７０】
図１２を用いて、実計算部９０３がバイナリτ進表現で格納されているスカラー値、楕円曲線上の点、前計算テーブル、及び、ウィンドウ幅ｗから、楕円曲線におけるスカラー倍点を計算する方法を説明する。図１２は、実計算部９０３のスカラー倍点の計算処理を示すフロー図である。
【０２７１】
まず、実計算部９０３は、点Ｑを楕円曲線Ｅの無限遠点Ｏ、変数ｉをｍ＋ａ―１で初期化する（Ｓ１２０１）。次に、繰り返し判定部９３３は、ｉ＞ｗであるかどうかを判定する（Ｓ１２０２）。ｉ＞ｗの場合は（TRUE）、ステップＳ１２０３へ移る。ｉ≦ｗの場合は（FALSE）、ステップＳ１２２１へ移る。
【０２７２】
ステップＳ１２０３では、変数ｊに初期値１を代入する。次に、繰り返し判定部９３３は、ｊ≦ｗであるかどうかを判定する（Ｓ１２０４）。ｊ≦ｗである場合は（TRUE）、ステップＳ１２０５へ移る。ｊ＞ｗの場合は（FALSE）、ステップＳ１２１１へ移る。ステップＳ１２０５では、τ倍算部９３８は、点Ｑをτ倍し、点Ｑに格納する。
【０２７３】
ステップＳ１２１１では、ｕｉに、（１＋Σｄｉ-ｗ＋ｊ（ｔｗ＋１Ｕｊ−２Ｕｊ−１））mod ２ｗ＋１ −２ｗを代入する。
【０２７４】
次に、繰り返し判定部９３３は、ｕｉ＞０であるかどうかを判定する（Ｓ１２１２）。ｕｉ＞０の場合は（TRUE）、ステップＳ１２１３へ移る。ｕｉ≦０の場合は（FALSE）、ステップＳ１２１４へ移る。
【０２７５】
ステップＳ１２１３では、加算部９３７は、点Ｑと前計算テーブル上の点ｕｉＰを加算し、点Ｑに格納する。一方、ステップＳ１２１３では、加算部９３７は、点Ｑから前計算テーブル上の点−ｕｉＰを減算し、点Ｑに格納する。次に、ステップＳ１２１５ｄで、ｉにｉ−ｗを代入する。
【０２７６】
一方、ステップＳ１２１１では、繰り返し判定部９３３は、ｊ≦ｉであるかどうかを判定する。ｊ≦ｉの場合は（TRUE）、ステップＳ１２２２へ移る。ｊ＞ｉの場合は（FALSE）、ステップＳ１２３１へ移る。ステップＳ１２２２で、τ倍算部９３８は、点Ｑをτ倍し、点Ｑに格納する。
【０２７７】
ステップＳ１２３１では、ｕ０に、（１＋Σｄｉ（ｔｉ＋１Ｕｊ−２Ｕｊ−１））mod ２ｉ＋１ −２ｉを代入する。次に、繰り返し判定部９３３は、ｕ０＞０であるかどうかを判定する（Ｓ１２３２）。ｕ０＞０の場合は（TRUE）、ステップＳ１２３３へ移る。ｕ０≦０の場合は（FALSE）、ステップＳ１２３４へ移る。
【０２７８】
ステップＳ１２３３では、加算部９３７は、点Ｑと前計算テーブル上の点ｕ０Ｐを加算し、点Ｑに格納する。一方、ステップＳ１２３４では、加算部９３７は、点Ｑから前計算テーブル上の点−ｕ０Ｐを減算し、点Ｑに格納する。
【０２７９】
次に、繰り返し判定部９３３は、ｄ０＝０であるかどうかを判定する（Ｓ１２３５）。ｄ０＝０の場合は（TRUE）、ステップＳ１２３６へ移る。ｄ０≠０の場合は（FALSE）、ステップＳ１２３７へ移る。
【０２８０】
ステップＳ１２３６では、加算部９３７は、点Ｑと点−Ｐを加算し、点Ｑに格納する。一方、ステップＳ１２３７では、加算部９３７は、点Ｑと点−τＰを加算し、点Ｑに格納する。そして、ステップＳ１２４１で、実計算部９０３は、点Ｑを出力する。
【０２８１】
上記第６の計算方法は、サイドチャネル攻撃に対する防御法に関しても有効である。この理由は以下の通りである。
【０２８２】
ステップＳ１２１１で、ｕｉに（１＋Σｄｉ−ｗ＋ｊ（ｔｗ＋１Ｕｊ−２Ｕｊ−１））mod ２ｗ＋１−２ｗを代入し、ステップＳ１２３１で、ｕ０に（１＋Σｄｊ（ｔｉ＋１Ｕｊ−２Ｕｊ−１））mod ２ｉ＋１−２ｉを代入している。
【０２８３】
ｉ＝ｍ＋ａ−１からｉ＝０までｕｉを左から右に並べた数値列ｕｍ＋ａ−１……ｕ０は、下記（式８７）のようなパターンで表わされる。
【０２８４】
｜０……０ｘ｜０……０ｘ｜……｜０……０ｘ｜        ・・・（式８７）
ここで各ｘは各々非０の値であり、それぞれ上記ｕ[j]に対応する。ここで“０……０”は、ｊ≠０のとき、ｗ−１個連続し、ｊ＝０のとき、高々ｗ−１個連続する。
【０２８５】
実計算部９０３がスカラー倍点を計算する際に、ステップＳ１２０４〜Ｓ１２１５の繰り返し処理において、ブロック｜０……０ｘ｜に対応する楕円曲線演算は、｜Ｔ……ＴＡ｜、すなわちｗ−１回のＴの後にＡとなる。ただし、Ｔはτ倍算を、ＡはＥＣＡＤＤをそれぞれ表わす。
【０２８６】
従って、すべてのスカラー値に対して、実行する楕円曲線演算は、実施の形態１及び２と同様に、下記（式８８）と固定されている。そのため、（式８８）のみからは、スカラー値ｄに関する情報を引き出すことができない。
【０２８７】
｜Ｔ……ＴＡ｜Ｔ……ＴＡ｜……｜Ｔ……ＴＡ｜        ・・・（式８８）
なお、実施の形態６において、前記処理１〜処理３を用いてよいことも、実施の形態１〜３と同様である。
【０２８８】
以上の通り、上記第６の計算方法は、コブリッツ曲線に対して適用可能で、サイドチャネル攻撃に有用な情報を与えないのでサイドチャネル攻撃に対して耐性があり、メモリ使用量及び処理高速性に優れるという特徴がある。
【０２８９】
（実施の形態７）
本発明の実施の形態７におけるスカラー倍計算方法、スカラー倍計算装置及びプログラムについて、図３，図１３〜図１５，図２１，図２２を参照しながら説明する。
【０２９０】
実施の形態７では、前記図３で示されるスカラー倍計算部１１５の機能ブロックを用いる。実施の形態７におけるスカラー倍計算部１１５（図１のスカラー倍計算部１３５に対応する）の構成は、実施の形態１，２及び５と同様である。
【０２９１】
実施の形態７で用いるスカラー倍計算方法として、スカラー倍計算部１１５がスカラー値ｄ、楕円曲線上の点Ｐ、ウィンドウ幅ｗから楕円曲線におけるスカラー倍点ｄＰを計算する第７の計算方法を説明する。第７の計算方法では、スカラー値ｄを、下記（式８９）を満たすｄｗ[ｉ]に対して、（式８５）を満たすようにエンコードする。
【０２９２】
ｄｗ[ｉ]＝１  または  ｄｗ[ｉ]＝−１        ・・・（式８９）
その際、前計算部３０３は、定点Ｐから下記（式９０）で示す点を計算する。
【０２９３】
τｗ−１Ｐ±τｗ−２Ｐ±……±τＰ±Ｐ        ・・・(式９０)
実計算部３０４は、（式８５），（式８９）を満たすスカラー値ｄ、及び、（式９０）を満たす前計算テーブル｛τｗ−１Ｐ±τｗ−２Ｐ±……±τＰ±Ｐ｝から、スカラー倍点ｄＰを計算する。
【０２９４】
実施の形態６と実施の形態７との違いは以下の通りである。実施の形態６では、スカラー値をエンコードした際、（式８５）において、各ｄｗ[ｉ]は、（式８６）を満たすのに対し、実施の形態７では、スカラー値をエンコードした際、（式８５）において、各ｄｗ[ｉ]は、（式８９）を満たす。
【０２９５】
実施の形態６と実施の形態７では、前計算テーブルに格納されている点が異なり、実施の形態６と比較して実施の形態７における前計算テーブルはより高速に作成することが可能であり、スカラー倍計算の更なる高速化を図ることができる。
【０２９６】
次に、エンコード部３０２、前計算部３０３、実計算部３０４の行う各処理について詳細に説明する。
【０２９７】
まず、図１３を用いて、エンコード部３０２がスカラー値ｄを、（式８５），（式８９）を満たすようにエンコードする方法を説明する。
【０２９８】
エンコード部３０２は、ｄを入力する(Ｓ１３０１)。次に、δ剰余変換部３２４は、ｄ mod δを計算し、ｄ mod δの実部分をｃ０に、ｄ mod δのτ部分をｃ１に、それぞれ代入する(Ｓ１３０２)。次に、ｉに０を代入する(Ｓ１３０３)。
【０２９９】
次に、ステップＳ１３０４で、繰り返し判定部３２３は、|ｃ０|≠１またはｃ１≠０であるかどうかを判定する。条件が成立する場合（TRUE）、ステップＳ１３１１へ移る。条件が成立しない場合（FALSE）、ステップＳ１３２１へ移る。
【０３００】
ステップＳ１３１１では、剰余取得部３２１は、（ｃ０＋２μｃ１ mod ４）−２を計算し、ｕに代入する。次に、ｕをｄ１[ｉ]に代入し、ｉにｉ＋１を代入する(Ｓ１３１２)。次に、ｃ０にｃ０−ｕを代入する(Ｓ１３１３)。次に、ｔにｃ０を、ｃ０にｃ１＋μｃ０／２を、ｃ１に−ｔ／２を、それぞれ代入し、ステップＳ１３０４へ戻る(Ｓ１３１４)。
【０３０１】
一方、ステップＳ１３２１では、ｃ０をｄ１[ｉ]に代入する(Ｓ１３２１)。次に、エンコード部３０２は、ｄ１[ｉ],……,ｄ１[０]を出力する(Ｓ１３２２)。
【０３０２】
次に、図１４を用いて、前計算部３０３が楕円曲線上の点から前計算テーブルを作成する概要を説明する。ただし、本実施の形態において、前記３３２で、２倍算部ではなく、τ倍算部を具備するものとする。
【０３０３】
ステップＳ１４０１において、Ｒ１[０]にＰを代入する。ｗ＝１のときは、ここで終了する。
【０３０４】
ステップＳ１４０２において、Ｒ２[１]にτＲ１[０]＋Ｒ１[０]を、Ｒ２[０]にτＲ１[０]−Ｒ１[０]を、それぞれ代入する。ｗ＝２のときは、ここで終了する。このとき、Ｒ２[１]＝τＰ＋Ｐ，Ｒ２[０]＝τＰ−Ｐである。
【０３０５】
ステップＳ１４０３において、Ｒ３[１||ｕ０]にτ２Ｒ１[０]＋Ｒ２[ｕ０]を、Ｒ３[０||~ｕ０]にτ２Ｒ１[０]−Ｒ２[ｕ０]を、それぞれ代入する。なお、図１４中の上付きバー付きの記号Ｘを、本文中では記号“~Ｘ”で表す。ｗ＝３のときは、ここで終了する。ｗの値が一般の場合は、上記の計算方法をｗまで続ける。ステップＳ１４０４，Ｓ１４０５は、ｗ＝４，５の場合を示すもので、同様に計算される。なお、記号“||”は、ビット列の結合を表す。また、上付きバー付きの記号、例えば上付きバー付きのｕ０は、ｕ０のビット反転を表す。また、ここでｕ０，ｌ０，ｌ１等は、各々１ビットの値で、０，１の値をとる。例えば、Ｓ１４０３におけるＲ３[０||~ｕ０]の場合、ｕ０＝０，１に対して、各々Ｒ３[０１]，Ｒ３[００]を表し、その値は、右辺にｕ０＝０，１を各々代入した値がＲ３[０１]，Ｒ３[００]に格納される。
【０３０６】
次に、図２１，図２２を用いて、前計算部３０３が楕円曲線上の点から前計算テーブルを作成する方法を説明する。
【０３０７】
前計算部３０３は、楕円曲線上の点Ｐ及びウィンドウ幅ｗを入力する(Ｓ２１０１)。次に、ステップＳ２１０３で、ＰをＲ１[０]に代入する(Ｓ２１０２)。次に、繰り返し判定部３２３は、ｗ＝１であるかどうかを判定する。条件が成立する場合（TRUE）、ステップＳ２１０４へ移る。条件が成立しない場合（FALSE）、ステップＳ２１１１へ移る。
【０３０８】
ステップＳ２１０４では、前計算部３０３は、点Ｒ１[０]を出力する(Ｓ２１０４)。
【０３０９】
ステップＳ２１１１では、加算部３３１とτ倍算部３３２は、τＲ１[０]＋Ｒ１[０]を計算し、その結果をＲ２[１]に代入する。また、加算部３３１とτ倍算部３３２は、τＲ１[０]−Ｒ１[０]を計算し、その結果をＲ２[０]に代入する。以下のステップＳ２１２２，Ｓ２１１３，Ｓ２２０２〜Ｓ２２０６，Ｓ２２１２〜Ｓ２２１９等では、加算部３３１とτ倍算部３３２により計算する。
【０３１０】
次に、繰り返し判定部３２３は、ｗ＝２であるかどうかを判定する（Ｓ２１１２）。条件が成立する場合（TRUE）、ステップＳ２１１３へ移る。条件が成立しない場合（FALSE）、ステップＳ２１２１へ移る。
【０３１１】
ステップＳ２１１３では、前計算部３０３は、点Ｒ２[０]，Ｒ２[１]を出力する。
【０３１２】
一方、ステップＳ２１２１では、繰り返し判定部３２３は、ｗ＝３または５であるかどうかを判定する。条件が成立する場合（TRUE）、ステップＳ２１２２へ移る。条件が成立しない場合（FALSE−Ａ）、図２２のステップＳ２２０１へ移る。
【０３１３】
ステップＳ２１２２では、加算部３３１とτ倍算部３３２は、τ２Ｒ１[０]＋Ｒ２[０]を計算し、その結果をＲ３[１０]に代入する。また、τ２Ｒ１[０]−Ｒ２[０]を計算し、その結果をＲ３[０１]に代入する。次に、同様に、τ２Ｒ１[０]＋Ｒ２[１]を計算し、その結果をＲ３[１１]に代入する。また、τ２Ｒ１[０]−Ｒ２[１]を計算し、その結果をＲ３[００]に代入する(Ｓ２１２３)。
【０３１４】
次に、繰り返し判定部３２３は、ｗ＝３であるかどうかを判定する(Ｓ２１２４)。条件が成立する場合（TRUE）、ステップＳ２１２５へ移る。条件が成立しない場合（FALSE−Ａ）、図２２のステップ２２０１へ移る。
【０３１５】
ステップＳ２１２５では、前計算部３０３は、点Ｒ３[１１]，Ｒ３[００]，Ｒ３[１０]，Ｒ３[０１]を出力し、終了する。
【０３１６】
図２２のＳ２２０１において、繰り返し判定部３２３は、ｗ＝４であるかどうかを判定する。条件が成立する場合（TRUE）、ステップＳ２２０２へ移る。条件が成立しない場合（FALSE）、ステップＳ２２１１へ移る。
【０３１７】
Ｓ２２０２では、加算部３３１とτ倍算部３３２は、τ２Ｒ２[１]＋Ｒ２[０]を計算し、その結果をＲ４[１１０]に代入する。また、τ２Ｒ２[１]−Ｒ２[０]を計算し、その結果をＲ４[１０１]に代入する。次に、τ２Ｒ２[１]＋Ｒ２[１]を計算してその結果をＲ４[１１１]に代入し、また、τ２Ｒ２[１]−Ｒ２[１]を計算してその結果をＲ４[１００]に代入する(Ｓ２２０３)。次に、τ２Ｒ２[０]＋Ｒ２[０]を計算してその結果をＲ４[０１０]に代入し、また、τ２Ｒ２[０]−Ｒ２[０]を計算してその結果をＲ４[００１]に代入する(Ｓ２２０４)。次に、τ２Ｒ２[０]＋Ｒ２[１]を計算してその結果をＲ４[０１１]に代入し、また、τ２Ｒ２[０]−Ｒ２[１]を計算してその結果をＲ４[０００]に代入する(Ｓ２２０５)。
【０３１８】
次に、前計算部３０３は、点Ｒ４[０００]，Ｒ４[００１]，Ｒ４[０１０]，Ｒ４[０１１]，Ｒ４[１００]，Ｒ４[１０１]，Ｒ４[１１０]，Ｒ４[１１１]を出力し、終了する(Ｓ２２０６)。
【０３１９】
一方、ステップＳ２２１１で、繰り返し判定部３２３は、ｗ＝５であるかどうかを判定する。条件が成立する場合（TRUE）、ステップＳ２２１２へ移る。条件が成立しない場合（FALSE）、終了する。
【０３２０】
ステップＳ２２１２では、加算部３３１とτ倍算部３３２は、τ３Ｒ２[１]＋Ｒ３[１１]を計算し、その結果をＲ５[１１１１]に代入する。また、τ３Ｒ２[１]−Ｒ３[１１]を計算し、その結果をＲ５[１０００]に代入する。次に、τ３Ｒ２[１]＋Ｒ３[１０]を計算してその結果をＲ５[１１１０]に代入し、また、τ３Ｒ２[１]−Ｒ３[１０]を計算してその結果をＲ５[１００１]に代入する(Ｓ２２１３)。次に、τ３Ｒ２[１]＋Ｒ３[０１]を計算してその結果をＲ５[１１０１]に代入し、また、τ３Ｒ２[１]−Ｒ３[０１]を計算してその結果をＲ５[１０１０]に代入する(Ｓ２２１４)。次に、τ３Ｒ２[１]＋Ｒ３[０１]を計算してその結果をＲ５[１１０１]に代入し、また、τ３Ｒ２[１]−Ｒ３[０１]を計算してその結果をＲ５[１０１０]に代入する(Ｓ２２１５)。次に、τ３Ｒ２[０]＋Ｒ３[１１]を計算してその結果をＲ５[０１１１]に代入し、また、τ３Ｒ２[０]−Ｒ３[１１]を計算してその結果をＲ５[００００]に代入する(Ｓ２２１６)。次に、τ３Ｒ２[０]＋Ｒ３[１０]を計算してその結果をＲ５[０１１０]に代入し、また、τ３Ｒ２[０]−Ｒ３[１０]を計算してその結果をＲ５[０００１]に代入する(Ｓ２２１７)。次に、τ３Ｒ２[０]＋Ｒ３[０１]を計算してその結果をＲ５[０１０１]に代入し、また、τ３Ｒ２[０]−Ｒ３[０１]を計算してその結果をＲ５[００１０]に代入する(Ｓ２２１８)。次に、τ３Ｒ２[０]＋Ｒ３[００]を計算してその結果をＲ５[０１００]に代入し、また、τ３Ｒ２[０]−Ｒ３[００]を計算してその結果をＲ５[００１１]に代入する(Ｓ２２１９)。
【０３２１】
次に、前計算部３０３は、点｛Ｒ５[００００]，Ｒ５[０００１]，Ｒ５[００１０]，Ｒ５[００１１]，Ｒ５[０１００]，Ｒ５[０１０１]，Ｒ５[０１１０]，Ｒ５[０１１１]，Ｒ５[１０００]，Ｒ５[１００１]，Ｒ５[１０１０]，Ｒ５[１０１１]，Ｒ５[１１００]，Ｒ５[１１０１]，Ｒ５[１１１０]，Ｒ５[１１１１]｝を出力し、終了する(Ｓ２１２０)。
【０３２２】
最後に、図１５を用いて、実計算部３０４が、エンコードされたスカラー値と楕円曲線上の点から、楕円曲線におけるスカラー倍点を計算する方法を説明する。
【０３２３】
まず、実計算部３０４は、ｄ１[ｉ],……,ｄ１[０],ｗ,Ｐ,Ｒｗ[０],……,Ｒｗ[２ｗ−１−１]を入力する(Ｓ１５０１)。次に、Ｑに無限遠点Ｏを、ｊにｉを、それぞれ代入する(Ｓ１５０２)。次に、繰り返し判定部３４４は、ｊ＞ｗ−１であるかどうかを判定する（Ｓ１５０３）。条件が成立する場合（TRUE）、ステップＳ１５１１へ移る。条件が成立しない場合（FALSE）、ステップＳ１５１５へ移る。
【０３２４】
ステップＳ１５１１では、ｕに、(１/２)＊(１−(−１)ｓ＊ｄ１[ｊ−１])２ｗ−２＋(１/２)＊(１−(−１)ｓ＊ｄ１[ｊ−２])２ｗ−３＋……＋(１/２)＊(１−(−１)ｓ*ｄ１[ｊ−ｗ＋１])２０を代入する。
【０３２５】
次に、加算部３４２とτ倍算部３４３は、τｗＱ＋ｄ１[ｊ]＊Ｒｗ[ｕ]を計算し、その結果をＱに代入する(Ｓ１５１２)。次に、ｊにｊ−ｗを代入し、ステップＳ１５０３へ戻る(Ｓ１５１３)。
【０３２６】
一方、ステップＳ１５１５では、繰り返し判定部３４４は、ｊ≧０であるかどうかを判定する。条件が成立する場合（TRUE）、ステップＳ１５２１へ移る。条件が成立しない場合（FALSE）、ステップＳ１５３１へ移る。
【０３２７】
ステップＳ１５２１では、加算部３４２とτ倍算部３４３は、τＱ＋ｄ１[ｊ]＊Ｐを計算し、その結果をＱに代入する。次に、ｊにｊ−１を代入し、ステップＳ１５１５へ戻る(Ｓ１５２２)。ステップＳ１５３１では、実計算部３０４は、Ｑを出力し、終了する。
【０３２８】
上記エンコード方法において、各桁ｄ１[ｉ]は、（式８９）を満たす。この理由は、以下の通りである。楕円曲線暗号において、秘密鍵ｄは奇数を用いる。ステップＳ１３０４〜Ｓ１３１４のループにおいて、整数ｃ０は常に奇数であることを説明する。
【０３２９】
整数ａ，ｂに対して、「ａ＋ｂτがτで割り切れる」⇔「ａは偶数」であり、「ａ＋ｂτがτ２で割り切れる」⇔「ａ≡２ｂ mod ４」であることが、非特許文献４に記載されている。ここで、“⇔”は、同値関係を表わす記号である。
【０３３０】
ステップＳ１３１１で、ｕ＝(ｃ０＋２μｃ１mod ４)−２を計算し、ステップＳ１３１３で、ｃ０にｃ０−ｕを代入している。ここで、ａ＝(ｃ０＋２μｃ１mod ４)−２，ｂ＝ｃ１とおくと、ａ mod ４ ≡ −２μｃ１＋２ mod ４である。ところが、−２μｃ１＋２ mod ４ ≡ ２ｃ１ mod ４は成立しない。これより、ａ mod ４ ≡ ２ｂ mod ４は成立しないことがわかる。従って、ステップＳ１３１３終了後のｃ０，ｃ１に関して、ｃ０＋ｃ１τはτで割り切れるが、τ２では割り切れないことがわかる。さらに、(ｃ０＋２μｃ１mod ４)＝１または３であることもわかる。ｕ＝(ｃ０＋２μｃ１ mod ４)−２であるから、（式８５）の各桁ｄ１[ｉ]は、１または−１である。以上から（式８５）の各桁ｄ１[ｉ]は、（式８９）を満たす。
【０３３１】
上記前計算テーブル作成方法は、実施の形態６と比較して高速に実行可能である。この理由は以下の通りである。
【０３３２】
実施の形態６では、前記図９における前計算部９０２はτ倍算部９２２ではなく２倍算部９２２を具備しているのに対し、実施の形態７では、前記図３における前計算部３０３はτ倍算部３３２を具備しており、楕円曲線上の２倍算と比較して、楕円曲線上のτ倍算は高速に計算できる。また、楕円曲線上の２点に対する楕円加算，楕円減算を同時に計算している。従って、上記前計算テーブル作成方法は、実施の形態６と比較して高速に実行可能である。
【０３３３】
上記スカラー倍計算方法は、サイドチャネル攻撃に対する防御法に関して有効である。この理由は以下の通りである。
【０３３４】
ステップＳ１５０３〜Ｓ１５１３の繰り返し処理において、実行される楕円曲線演算は、下記（式９１）と固定されている。ここで、Ｔは、ｗ−１個連続している。
【０３３５】
｜Ｔ……ＴＡ｜Ｔ……ＴＡ｜……｜Ｔ……ＴＡ｜        ・・・（式９１）
ステップＳ１５１５〜Ｓ１５２２の繰り返し処理において、実行される楕円曲線演算は、下記（式９２）と固定されている。ただし、（式９２）で、Ｔは、高々ｗ−１個連続している。
【０３３６】
｜Ｔ……ＴＡ｜        ・・・（式９２）
従って、実計算部３０４で、すべてのスカラー値に対して、実行する楕円曲線演算は、下記（式９３）と固定されているため、（式９３）のみからは、スカラー値に関する情報を引き出すことができない。すなわちサイドチャネル攻撃に対する防御法を有している。ただし、（式９３）において、最下位ブロック以外でＴはｗ個連続し、最下位ブロックでＴは高々ｗ−２個連続する。
【０３３７】
｜Ｔ……ＴＡ｜Ｔ……Ｔ｜……｜Ｔ……ＴＡ｜Ｔ……ＴＡ｜      ・・・（式９３）
以上の通り、上記第７の計算方法は、コブリッツ曲線に対して適用可能で、サイドチャネル攻撃に有用な情報を与えないのでサイドチャネル攻撃に対して耐性があり、メモリ使用量及び処理高速性に優れるという特徴がある。
【０３３８】
＜署名検証システム（１）＞
次に、本発明を署名検証システムに適用した実施の形態について説明する。まず、図２，図１６を参照して、本発明の実施の形態８における署名生成方法、署名生成装置及びプログラムについて説明する。図１６は、実施の形態８の署名検証システム（１）の構成を示し、この署名検証システムは、本発明の実施の形態における署名生成方法に従った署名生成処理を行う署名生成装置と、署名検証処理を行う署名検証装置とを含んで構成される。各々の装置は、前述した実施の形態１〜７のいずれか１つにおけるスカラー倍計算装置に従った処理を行うスカラー倍計算部を具備している。特に図１６に示す署名検証システムは、本発明の実施の形態における署名生成装置であるスマートカード１６０１と、署名検証装置であるコンピュータ１６２１とからなる。コンピュータ１６２１は、署名検証処理をプログラムの実行によって行う。スマートカード１６０１は、コンピュータ１６２１での署名検証処理に対応した署名生成処理を、プログラムの実行によって行う。コンピュータ１６２１とスマートカード１６０１の間で、データ・情報の授受が行われる。
【０３３９】
スマートカード１６０１は、ＣＰＵ１６１３、コプロセッサ１６１４、ＲＡＭ１６０３、ＲＯＭ１６０６、入出力インタフェース１６１０を備える。実施の形態１などと同様に、ＲＡＭ１６０３は、定数１６０４、秘密情報１６０５を記憶している。
【０３４０】
コンピュータ１６２１は、ＣＰＵ１６３３、コプロセッサ１６３４、ＲＡＭ１６２３、ＲＯＭ１６２６、外部記憶装置１６２７、入出力インタフェース１６３０を備える。実施の形態１などと同様に、ＲＡＭ１６２３は、定数１６２４、秘密情報１６２５を記憶している。
【０３４１】
ここでスマートカードとは、プロセッサを含むＩＣ（集積回路）を搭載した、可搬型のカード形状の装置を指している。本例では、スマートカード１６０１は、プロセッサとしてＣＰＵ１６１３及びコプロセッサ１６１４と、メモリとしてＲＡＭ１６０３及びＲＯＭ１６０６とを搭載した装置である。
【０３４２】
スマートカード１６０１は、前記図１に示すコンピュータＡ１０１と類似の構成を備え、ＣＰＵ１６１３やコプロセッサ１６１４などの演算装置が、記憶部１６０２に格納されているプログラムを実行することにより、処理部１６１１として、データ処理部１１２ではなく署名生成処理部１６１２を実現する。ただし、図１３に示すように、スマートカード１６０１では、前記図１に示す外部記憶装置１０７、ディスプレイ１０８、キーボード１０９などを備えなくてもよい。
【０３４３】
コンピュータ１６２１は、コンピュータＡ１０１と同様の構成を備え、ＣＰＵ１６１３が記憶部１６２２に格納されているプログラムを実行することにより、処理部１６３１として、データ処理部１１２ではなく署名検証処理部１６３２を実現する。各スカラー倍計算部１６１５，１６３５は、図１に示す各スカラー倍計算部１１５，１３５と同様の機能を備える。署名生成処理部１６１２と署名検証処理部１６３２とで対応した処理が行われる。
【０３４４】
なお、本実施の形態において、コンピュータ１６２１内の各プログラムは、あらかじめ、コンピュータ１６２１内の記憶部１６２２に格納されていてもよいし、必要なときに、コンピュータ１６２１が利用可能な媒体を介して他の装置から記憶部１６２２に導入されてもよい。更に、スマートカード１６０１内の各プログラムは、あらかじめ、スマートカード１６０１内の記憶部１６０２に格納されていてもよいし、必要なときに、入出力インタフェース１６１０を介して接続するコンピュータ、または当該コンピュータが利用可能な媒体を介して記憶部１６０２に導入されてもよい。前記利用可能な媒体とは、例えば当該コンピュータに着脱可能な記憶媒体、または通信媒体（すなわちネットワークまたはネットワークを伝搬する搬送波）を指す。
【０３４５】
前記図２を参照しながら、図１６に示す署名検証システムにおける署名生成と署名検証の動作を説明する。図２のデータ処理部１１２は、署名生成処理部１６１２、署名検証処理部１６３２に対応する。同様に、スカラー倍計算部１１５は、各スカラー倍計算部１６１５，１６３５に対応し、記憶部１０２は、各記憶部１６０２，１６２２に対応する。
【０３４６】
図１６において、コンピュータ１６２１とスマートカード１６０１の間で、所定のディジタル署名アルゴリズムに基づく処理を行う。離散対数問題に基づくディジタル署名方法を楕円曲線上の離散対数問題に基づく方法に対応させて構成する楕円曲線ディジタル署名アルゴリズム（ＥＣＤＳＡ）という署名方法がある。この方法を用いるＥＣＤＳＡ署名については、例えば、非特許文献１に記載されている。
【０３４７】
まず、コンピュータ１６２１は、ランダムに選んだ数値をチャレンジコード１６４２として入出力インタフェース１６３０より出力し、インタフェースを介してスマートカード１６０１に転送する。
【０３４８】
スマートカード１６０１は、入出力インタフェース１６１０を介してチャレンジコード１６４２を受け取る。署名生成処理部１６１２（図２の１１２）は、チャレンジコード１６４２を受け付け、受け取ったチャレンジコード１６４２のハッシュ値をとり、所定のビット長の数値ｆに変換する。
【０３４９】
そして、署名生成処理部１６１２は、乱数ｕを生成し、記憶部１６０２（図２の１０２）に格納されている定数１６０４から読み出した楕円曲線上の定点Ｑ(Ｓ２０５)と共に、スカラー倍計算部１６１５（図２の１１５）へ送る（Ｓ２０６）。
【０３５０】
そして、スカラー倍計算部１６１５は、定点Ｑ、乱数ｕによるスカラー倍点ｕＱ＝（ｘｕ，ｙｕ）を計算し、計算されたスカラー倍点ｕＱを署名生成処理部１６１２へ送る（Ｓ２０７）。
【０３５１】
そして、署名生成処理部１６１２は、送られたスカラー倍点ｕＱを用いて署名（ディジタル署名データ）の生成を行う。例えば、前記ＥＣＤＳＡ署名に従った処理を行う場合であれば、下記（式９４），（式９５）を計算することにより、チャレンジコード１６４２に対応する署名（ｓ，ｔ）を得る（Ｓ２０８）。
【０３５２】
ｓ＝ｘｕ mod ｑ                      ・・・（式９４）
ｔ＝ｕ−１（ｆ＋ｄｓ） mod ｑ        ・・・（式９５）
ここで、ｑは定点Ｑの位数、すなわち、定点Ｑのｑ倍点ｑＱが無限遠点になり、ｑより小さな数値ｍに対する定点Ｑのｍ倍点ｍＱは無限遠点にはならない、というような数値のことである。
【０３５３】
スマートカード１６０１は、署名生成処理部１６１２で生成した署名１６４１を、入出力インタフェース１６１０より出力し、インタフェースを介してコンピュータ１６２１へ転送する。
【０３５４】
コンピュータ１６２１の署名検証処理部１６３２（図２の１１２）は、署名１６４１が入力されると（Ｓ２０４）、署名１６４１の数値ｓ，ｔが適切な範囲内すなわち１≦ｓ＜ｑ，１≦ｔ＜ｑであるかを調べる。
【０３５５】
数値ｓ，ｔが上記範囲内になければ、チャレンジコード１６４２に対する署名１６４１についての検証結果として「無効」を出力し、スマートカード１６０１を拒絶する。数値ｓ，ｔが上記範囲内にあれば、署名検証処理部１６３２は、下記（式９６），（式９７），（式９８）を計算する。
【０３５６】
ｈ＝ｔ−１ mod ｑ                  ・・・（式９６）
ｈ１＝ｆｈ mod ｑ                ・・・（式９７）
ｈ２＝ｓｈ mod ｑ                ・・・（式９８）
そして、署名検証処理部１６３２は、記憶部１６２２（図２の１０２）に格納されている定数１６２４から読み出した公開鍵ｄＱ及び定点Ｑと（Ｓ２０５）、計算したｈ１，ｈ２とを、スカラー倍計算部１６３５（図２の１１５）へ送る（Ｓ２０６）。
【０３５７】
スカラー倍計算部１６３５は、定点Ｑとｈ１によるスカラー倍点ｈ１Ｑと、公開鍵ｄＱとｈ２によるスカラー倍点ｈ２ｄＱとを計算し、計算されたスカラー倍点を署名検証処理部１６３２へ送る（Ｓ２０７）。
【０３５８】
署名検証処理部１６３２は、送られたスカラー倍点を用いて、署名検証処理を行う。例えば、ＥＣＤＳＡ署名における署名検証であれば、下記（式９９）で表わす点Ｒを計算し、そのｘ座標をｘＲとしたとき、下記（式１００）で表わすｓ’を計算する。
【０３５９】
Ｒ＝ｈ１Ｑ＋ｈ２ｄＱ                  ・・・（式９９）
s'＝ｘＲmod ｑ                      ・・・（式１００）
そして、ｓ’＝ｓであれば、チャレンジコード１６４３に対する署名１６４１についての検証結果として「有効」を出力し、スマートカード１６０１を認証し受け入れる（Ｓ２０８）。また、ｓ’＝ｓでなければ、検証結果として「無効」を出力し、スマートカード１６０１を拒絶する（Ｓ２０８）。
【０３６０】
署名生成や署名検証では、楕円曲線上の点のスカラー倍算を計算する。従って、本実施の形態において、署名生成を行う際に、前記第１〜第７の計算方法または実施の形態１〜７のスカラー倍計算装置のいずれかを用いることが可能である。
【０３６１】
次に、署名生成処理部１６１２が署名生成を行うときのスカラー倍計算について詳細に説明する。
【０３６２】
署名生成の場合、スカラー倍計算部１６１５は、定点Ｑ、乱数ｕによるスカラー倍点ｕＱ＝（ｘｕ，ｙｕ）を計算し、計算されたスカラー倍点を署名生成処理部１６１２へ送る。このとき、定点Ｑ、乱数ｕによるスカラー倍点ｕＱの計算では、まず、乱数ｕを生成し、ｕをエンコードした後、定点Ｑのスカラー倍点を計算する。
【０３６３】
次に示す実施の形態９，１０（署名検証システム（２），（３））では、署名生成処理部１６１２が行う署名生成処理を示すものであり、乱数生成と乱数倍点ｕＱの計算を同時に行う。従って、乱数ｕのエンコード処理を行う必要がない。
【０３６４】
＜署名検証システム（２）＞
次に、本発明の他の実施の形態９における署名生成方法、署名生成装置及びプログラムについて、図１６〜図１８及び図２０を参照しながら説明する。実施の形態９の署名検証システム（２）では、前記図１６で示す署名検証システムの構成における署名生成装置であるスマートカード１６０１の構成と、図１７で示される署名生成処理部１６１２の機能ブロックを用いる。本署名検証システム（２）において、本実施の形態の署名生成装置であるスマートカード１６０１は、署名生成処理をプログラムの実行により行う。スマートカード１６０１は、乱数生成部とスカラー倍計算部とをあわせた構成であり、乱数生成と乱数倍点の計算を同時に行うので、図１６に示すスカラー倍計算部１６１５を具備する必要はない。図１８は、署名生成処理部１６１２での計算処理を示すフロー図である。本署名検証システム（２）における署名生成と署名検証の動作のシーケンス図として、前記図２ではなく図２０を用いる。
【０３６５】
図１７において、署名生成処理部１６１２は、乱数倍計算部１７０１からなる。乱数倍計算部１７０１は、前計算部１７０２、実計算部１７０３からなる。前計算部１７０２は、加算部１７２１、２倍算部１７２２、繰り返し判定部１７２３からなる。実計算部１７０３は、剰余取得部１７３１、剰余変換部１７３２、繰り返し判定部１７３３、格納部１７３４、ランダムビット生成部１７３５、Ψ関数計算部１７３６、ビット値判定部１７３７、加算部１７３８、τ倍算部１７３９からなる。
【０３６６】
図２０において、スマートカード１６０１の署名生成処理部１６１２は、コンピュータ１６２１からのチャレンジコード１６４２を受け付ける（Ｓ２００４）。署名生成処理部１６１２は、記憶部１６０２から楕円曲線上の定点を読み出し（Ｓ２００５）、楕円曲線上の点を乱数倍計算部１７０１に渡す（Ｓ２００６）。乱数倍計算部１７０１は、乱数、及び、乱数倍点を計算して署名生成処理部１６１２に渡す（Ｓ２００７）。署名生成処理部１６１２は、乱数及び乱数倍点をもとに署名１６４１を生成してコンピュータ１６２１へ送る。
【０３６７】
本実施の形態では、ベースポイントと呼ばれる楕円曲線上の点Ｑから、署名（ｓ，ｔ）を計算する計算方法を説明する。
【０３６８】
前計算部１７０２は、入力された楕円曲線上の点Ｑから、前計算テーブルを作成する。前計算部１７０２が楕円曲線上の点から前計算テーブルを作成する方法は、実施の形態１、５及び６と同様である。
【０３６９】
実計算部１７０３と署名生成処理部１６１２は、ベースポイントと呼ばれる楕円曲線上の点Ｑから乱数ｋ、及び、スカラー倍点ｋＱを計算する。署名生成処理部１６１２は、乱数ｋ、及び、スカラー倍点ｋＧから署名（ｓ，ｔ）を生成する。ただし、本実施の形態では、乱数ｋを直接生成せず、乱数生成後、その乱数ｋをエンコードしたり、メモリに格納したりすることなく、直接、ベースポイントＱのスカラー倍ｋＱを計算することができる。
【０３７０】
次に、署名生成処理部１６１２の行う各処理について詳細に説明する。図１８を用いて、楕円曲線上のベースポイントＱから乱数ｋ及び楕円曲線上の点ｋＱを計算する方法を説明する。
【０３７１】
署名生成処理部１６１２は、まず、Ｑに楕円曲線上の無限遠点Ｏ、ｃ０，ｃ１に０、ｉにｍ＋ａ−１を、それぞれ代入する（Ｓ１８０１）。次に、繰り返し判定部１７３３によりｉ＞ｗであるかどうかを判定する（Ｓ１８０２）。ｉ＞ｗの場合（TRUE）、ステップＳ１８０３へ移る。ｉ≦ｗの場合（FALSE）、ステップＳ１８２１へ移る。
【０３７２】
ステップＳ１８０３では、ランダムビット生成部１７３５は、集合｛±１，±３，……±（２ｗ−１）｝に属するｗ個のランダムな整数ｄｉ，ｄｉ−１，……，ｄｉ−ｗ＋１を選ぶ。次に、ｕｉに、（１＋Σｄｉ−ｗ＋ｊ（ｔｗ＋１Ｕｊ−２Ｕｊ−１））mod ２ｗ＋１−２ｗを代入する（Ｓ１８０４）。次に、ｊに１を代入する（Ｓ１８０５）。
【０３７３】
次に、繰り返し判定部１７３３によりｊ≦ｗであるかどうかを判定する（Ｓ１８０６）。ｊ≦ｗの場合（TRUE）、ステップＳ１８１１へ移る。ｊ＞ｗの場合（FALSE）、ステップＳ１８１２へ移る。
【０３７４】
ステップＳ１８１１では、ＱにτＱ、（ｃ０，ｃ１）に（−２ｃ１，ｃ０＋μｃ１）をそれぞれ代入する。
【０３７５】
ステップＳ１８１２では、繰り返し判定部１７３３によりｕｉ＞０であるかどうかを判定する。ｕｉ＞０の場合（TRUE）、ステップＳ１８１３へ移る。ｕｉ≦０の場合、ステップＳ１８１４へ移る。
【０３７６】
ステップＳ１８１３では、加算部１７３８は、ＱにＱ＋ｕｉＰを代入する。ステップＳ１８１４では、加算部１７３８は、ＱにＱ−（−ｕｉＰ）を代入する。次に、ステップＳ１８１５で、ｃ０にｃ０＋ｕ０、ｉにｉ−ｗをそれぞれ代入し、ステップＳ１８０２へ戻る。
【０３７７】
一方、ステップＳ１８２１では、ランダムビット生成部１７３５は、集合｛±１，±３，……±（２ｗ−１）｝に属するｉ＋１個のランダムな整数ｄｉ，ｄｉ−１，……，ｄ１，ｄ０を選ぶ。次に、ｕ０に、（１＋Σｄｊ（ｔｉ＋１Ｕｊ−２Ｕｊ−１））mod ２ｉ＋１−２ｉを代入する（Ｓ１８２２）。次に、ｊに１を代入する（Ｓ１８２３）。
【０３７８】
次に、繰り返し判定部１７３３によりｊ≦ｉであるかどうかを判定する（Ｓ１８２４）。ｊ≦ｉの場合（TRUE）、ステップＳ１８２５へ移る。ｊ＞ｉの場合、ステップＳ１８３１へ移る。
【０３７９】
ステップＳ１８２５では、ＱにτＱ、（ｃ０，ｃ１）に（−２ｃ１，ｃ０＋μｃ１）をそれぞれ代入する。
【０３８０】
ステップＳ１８３１では、繰り返し判定部１７３３によりｕ０＞０であるかどうかを判定する。ｕ０＞０の場合（TRUE）、ステップＳ１８３２へ移る。ｕ０≦０の場合（FALSE）、ステップＳ１８３３へ移る。
【０３８１】
ステップＳ１８３２では、加算部１４３８は、ＱにＱ＋ｕ０Ｐを代入する。ステップＳ１８３３では、加算部１４３８は、ＱにＱ−（−ｕ０Ｐ）を代入する。次に、ステップＳ１５３４で、ｃ０にｃ０＋ｕ０を代入する。
【０３８２】
次に、繰り返し判定部１７３３によりｄ０＝０であるかどうかを判定する（Ｓ１８３４）。ｄ０＝０の場合（TRUE）、ステップＳ１８３６へ移る。ｄ０≠０の場合（FALSE）、ステップＳ１８３７へ移る。
【０３８３】
ステップＳ１８３６では、ＱにＱ−Ｐ、ｃ０にｃ０−１をそれぞれ代入する。ステップＳ１８３７では、ＱにＱ−τＰ、ｃ１にｃ１−１をそれぞれ代入する。次に、ステップＳ１８３８で、ｋに（ｃ０＋ｃ１τ） mod ＃Ｅを代入する。ここで、＃Ｅは、楕円曲線Ｅ上の点全体の個数である。
【０３８４】
そして、ステップＳ１８４１で、実計算部１７０３は、乱数ｋと点Ｑを出力する。
【０３８５】
本実施の形態における乱数倍計算部１７０１は、前記図１のスカラー倍計算部１１５または１３５と同様の機能を備えるので、サイドチャネル攻撃を防ぐことができる、かつ処理速度やメモリ使用量をカスタマイズすることができるスカラー倍計算を実行できる。そのためスマートカード１６０１が署名生成処理を行う際に、またコンピュータ１６２１が署名検証処理を行う際に、サイドチャネル攻撃を防ぐことができる。
【０３８６】
＜署名検証システム（３）＞
次に、本発明の他の実施の形態１０における署名生成方法、署名生成装置及びプログラムについて、図４，図１６，図１７，図１９〜図２２を参照しながら説明する。本実施の形態１０の署名検証システム（３）でも、前記図１６で示す署名検証システムの構成における署名生成装置であるスマートカード１６０１の構成と、図１７で示される署名生成処理部１６１２の機能ブロックを用いる。本署名検証システム（３）においても、署名生成装置であるスマートカード１６０１は、署名生成処理をプログラムの実行により行う。スマートカード１６０１は、乱数生成部とスカラー倍計算部とをあわせた構成であり、乱数生成と乱数倍点の計算を同時に行うので、図１６に示すスカラー倍計算部１６１５を具備する必要はない。図１９は、署名生成処理部１６１２での計算処理を示すフロー図である。本署名検証システム（３）における署名生成と署名検証の動作のシーケンス図として、前記図２ではなく図２０を用いる。
【０３８７】
前記署名検証システム（２）と本署名検証システム（３）の違いは以下の通りである。署名検証システム（２）と署名検証システム（３）では、前計算テーブルに格納されている点が異なり、署名検証システム（２）と比較して署名検証システム（３）における前計算テーブルはより高速に作成することが可能であり、乱数によるスカラー倍計算の更なる高速化を図ることができる。
【０３８８】
本署名検証システム（３）においても、ベースポイントＱから、署名（ｓ，ｔ）を計算する計算方法を説明する。
【０３８９】
前計算部１７０２は、入力された楕円曲線上の点Ｑから、前計算テーブルを作成する。前計算部１７０２が楕円曲線上の点から前計算テーブルを作成する方法は、実施の形態７と同様である。
【０３９０】
実計算部１７０３と署名生成処理部１６１２は、ベースポイントと呼ばれる楕円曲線上の点Ｑから乱数ｄ、及び、スカラー倍点ｄＱを計算する。署名生成処理部１６１２は、乱数ｄ、及び、スカラー倍点ｄＱから署名（ｓ，ｔ）を生成する。ただし、本署名検証システム（３）でも、乱数ｄを直接生成せず、乱数生成後、その乱数ｄをエンコードしたり、メモリに格納したりすることなく、直接、ベースポイントＱのスカラー倍点ｄＱを計算することができる。次に、署名生成処理部１６１２の行う各処理について詳細に説明する。図１９を用いて、楕円曲線上のベースポイントＱから乱数ｄ及び楕円曲線上の点ｄＱを計算する方法を説明する。
【０３９１】
まず、実計算部１７０３は、Ｐ,Ｒｗ[０],……,Ｒｗ[２ｗ−１−１]を入力する(Ｓ１９０１)。次に、Ｑに無限遠点Ｏを、ｊにｍ＋ａ−１を、それぞれ代入する(Ｓ１９０２)。次に、繰り返し判定部１７３３は、ｊ＞ｗ−１であるかどうかを判定する(Ｓ１９０３)。条件が成立する場合（TRUE）、ステップＳ１９１１へ移る。条件が成立しない場合（FALSE）、ステップＳ１９４１へ移る。
【０３９２】
ステップＳ１９１１では、ランダムビット生成部１７３５は、各ランダムビットｄ１[ｗ−１]，ｄ１[ｗ−２]，……，ｄ１[０]を生成し、ｗ−１をｋに代入する。次に、繰り返し判定部１７３３は、ｋ≧０であるかどうかを判定する(Ｓ１９１２)。条件が成立する場合（TRUE）、ステップＳ１９２１へ移る。条件が成立しない場合（FALSE）、ステップＳ１９３１へ移る。
【０３９３】
ステップＳ１９２１では、ｔにｃ０を、ｃ０に−２ｃ１−(−１)ｄ１[ｋ]を、ｃ１に２μ(ｔ＋ｃ１)を、ｋにｋ−１を、それぞれ代入し、ステップＳ１９１２へ戻る。
【０３９４】
ステップＳ１９３１では、ｕにｄ１[ｗ−２]２ｗ−２＋……＋ｄ１[０]２０を代入する。次に、加算部１７３８とτ倍算部１７３９は、τｗＱ＋ｄ１[ｗ−１]＊Ｒｗ[ｕ]を計算し、その結果をＱに代入する(Ｓ１９３２)。次に、ｊにｊ−ｗを代入し、ステップＳ１９０３へ戻る(Ｓ１９３３)。
【０３９５】
一方、ステップＳ１９４１では、繰り返し判定部１７３３は、ｊ≧０であるかどうかを判定する。条件が成立する場合（TRUE）、ステップＳ１９４２へ移る。条件が成立しない場合（FALSE）、ステップＳ１９５１へ移る。
【０３９６】
ステップＳ１９４３では、ランダムビット生成部１７３５は、ランダムビットｄ１を生成する。次に、ｔにｃ０を、ｃ０に−２ｃ１＋(−１)ｄ１を、ｃ１にｔ＋μｃ１を、それぞれ代入する(Ｓ１９４３)。次に、加算部１７３８とτ倍算部１７３９は、τＱ＋ｄ１＊Ｐを計算し、その結果をＱに代入する(Ｓ１９４４)。次に、ｊにｊ−１を代入し、ステップＳ１９４１へ戻る(Ｓ１９４５)。
【０３９７】
ステップＳ１９５１では、実計算部１７０３は、乱数ｄ＝ｃ０＋ｃ１τ mod ｑ，乱数倍点Ｑを出力する。
【０３９８】
上記前計算テーブル作成方法は、署名検証システム（２）と比較して高速に実行可能である。この理由は、実施の形態７と同様である。
【０３９９】
本実施の形態における乱数倍計算部１７０１は、前記図１のスカラー倍計算部１１５または１３５と同様の機能を備えるので、上記計算方法と同様にサイドチャネル攻撃を防ぐことができる、かつ処理速度やメモリ使用量をカスタマイズすることができるスカラー倍計算を実行できる。そのためスマートカード１６０１が署名生成処理を行う際に、またコンピュータ１６２１が署名検証処理を行う際に、サイドチャネル攻撃を防ぐことができる。
【０４００】
＜鍵交換システム＞
次に、本発明を鍵交換システムに適用した実施の形態１１について説明する。図１，図２を参照して、本発明の実施の形態１１におけるデータ生成方法、データ生成装置及びプログラムについて説明する。本実施の形態１１においては、前記図１の情報処理システム構成が鍵交換システムの構成として応用できる。本鍵交換システムは、本発明の実施の形態におけるデータ生成装置であるコンピュータＡ１０１とコンピュータＢ１２１を含んで構成される。コンピュータＡ１０１及びコンピュータＢ１２１は、本発明の実施の形態におけるデータ生成方法に従ったデータ生成処理を、プログラムに従って実行する。
【０４０１】
図１のデータ処理部１１２，１３２は、本実施の形態においては、それぞれ鍵交換処理部１１２，１３２として機能する。また、鍵交換処理部１１２，１３２としての機能以外に、前述した暗号化や復号化などの機能を備えてもよい。鍵交換システムのコンピュータＡ１０１が、コンピュータＢ１２１側から入力されたデータ１４３からコンピュータＢ１２１との共有情報の導出を行う場合のデータ生成処理を含む動作について説明する。
【０４０２】
コンピュータＢ１２１のデータ処理部１３２（図２の１１２に対応する）は、記憶部１２２（図２の１０２に対応する）の秘密情報１２５から秘密鍵ｂを読み出して、コンピュータＢ１２１の公開鍵ｂＱを計算する。そして、ネットワーク１４２を介して、公開鍵ｂＱをデータ１４３としてコンピュータＡ１０１に転送する。
【０４０３】
コンピュータＡ１０１の鍵交換処理部１１２（図２の１１２に対応する）は、コンピュータＢ１２１の公開鍵ｂＱの入力を受け付ける（Ｓ２０４）。鍵交換処理部１１２は、コンピュータＢ１２１の公開鍵ｂＱを入力すると、記憶部１０２から読み出した秘密情報１０５であるコンピュータＡ１０１の秘密鍵ｄと(Ｓ２０５)、コンピュータＢ１２１の公開鍵ｂＱとを、スカラー倍計算部１１５へ送る（Ｓ２０６）。
【０４０４】
スカラー倍計算部１１５は、秘密鍵ｄと公開鍵ｂＱによるスカラー倍点ｄｂＱを計算し、計算されたスカラー倍点ｄｂＱを鍵交換処理部１１２へ送る（Ｓ２０７）。
【０４０５】
鍵交換処理部１１２は、送られたスカラー倍点ｄｂＱを用いて共有情報の導出を行い、記憶部１０２に秘密情報１０５として格納する。例えば、スカラー倍点ｄｂＱのｘ座標を、共有情報とする。
【０４０６】
次に、コンピュータＢ１２１が、コンピュータＡ１０１側から入力されたデータ１４１からコンピュータＡ１０１との共有情報の導出を行う場合のデータ生成処理を含む動作について説明する。
【０４０７】
コンピュータＡ１０１のデータ処理部１１２は、記憶部１０２の秘密情報１０５から秘密鍵ｄを読み出しコンピュータＡ１０１の公開鍵ｄＱを計算する。そして、ネットワーク１４２を介して、公開鍵ｄＱをデータ１４１としてコンピュータＢ１２１に転送する。
【０４０８】
コンピュータＢ１２１の鍵交換処理部１３２（図２の１１２）は、コンピュータＡ１０１の公開鍵ｄＱの入力を受け付ける（Ｓ２０４）。コンピュータＡ１０１の公開鍵ｄＱを入力すると、鍵交換処理部１３２は、記憶部１２２（図２の１０２）の秘密情報１２５から読み出したコンピュータＢ１２１の秘密鍵ｂと（Ｓ２０５）、コンピュータＡ１０１の公開鍵ｄＱとを、スカラー倍計算部１３５（図２の１１５）へ送る（Ｓ２０６）。
【０４０９】
スカラー倍計算部１３５は、秘密鍵ｂと、公開鍵ｄＱによるスカラー倍点ｂｄＱを計算し、計算されたスカラー倍点ｂｄＱを鍵交換処理部１３２へ送る（Ｓ２０７）。
【０４１０】
鍵交換処理部１３２は、送られたスカラー倍点ｂｄＱを用いて共有情報の導出を行い、記憶部１２２に秘密情報１２５として格納する。例えば、スカラー倍点ｂｄＱのｘ座標を、共有情報とする。ここで、数ｄｂと数ｂｄは数値として同じなので、点ｄｂＱと点ｂｄＱは同じ点となり、同じ情報がコンピュータＡ１０１とＢ１２１で導出されたことになる。
【０４１１】
ネットワーク１４２には、点ｄＱと点ｂＱが送信されるが、点ｄｂＱ（もしくは点ｂｄＱ）を計算するには秘密鍵ｄもしくは秘密鍵ｂを用いなければならない。すなわち、秘密鍵ｄもしくは秘密鍵ｂを知らなければ、共有情報を得ることができない。
【０４１２】
このようにして得られた共有情報は、共通鍵暗号の秘密鍵として利用できる。本実施の形態においても、スカラー倍計算部１１５，１３５は、前述した実施の形態１〜７のいずれか１つのスカラー倍算を適用して同じ特徴を備えるので、サイドチャネル攻撃を防ぐことができる。
【０４１３】
また、前述した各実施の形態におけるデータ処理部、すなわち、暗号化処理部、復号化処理部、署名生成処理部、署名検証処理部、及び鍵交換処理部などについては、専用のハードウェアを用いて構成して各処理を行う形態としてもよい。また、スカラー倍計算部をコプロセッサまたはそれ以外の専用ハードウェアで実現した形態としてもよい。また、データ処理部は、前記暗号化、復号化、署名生成、署名検証、鍵交換のためのデータ生成などの処理のうち、任意の一つ以上の処理を行えるように構成した形態としてもよい。
【０４１４】
以上、本発明者によってなされた発明を実施の形態に基づき具体的に説明したが、本発明は前記実施の形態に限定されるものではなく、その要旨を逸脱しない範囲で種々変更可能であることは言うまでもない。
【産業上の利用可能性】
【０４１５】
本発明は、暗号化などの各種セキュリティ技術に利用可能である。
【図面の簡単な説明】
【０４１６】
【図１】本発明の一実施の形態におけるスカラー倍計算装置を含んで構成される情報処理システムの構成を示す図である。
【図２】本発明の各実施の形態において各処理部間での情報の受け渡しの様子を示すシーケンス図である。
【図３】本発明の実施の形態１，２，５及び７において、スカラー倍計算部の機能ブロック構成を示す図である。
【図４】本発明の実施の形態１及び５において、エンコード部の行うエンコード方法を示すフロー図である。
【図５】本発明の実施の形態１，５，６及び本発明の一実施の形態における署名生成装置において、前計算部の前計算テーブル作成処理を示すフロー図である。
【図６】本発明の実施の形態１，２及び５において、実計算部のスカラー倍点の計算方法を示すフロー図である。
【図７】本発明の実施の形態２において、エンコード部の行うエンコード方法を示すフロー図である。
【図８】本発明の実施の形態２，３及び４において、前計算部の前計算テーブル作成処理を示すフロー図である。
【図９】本発明の実施の形態３，４及び６において、スカラー倍計算部の機能ブロック構成を示す図である。
【図１０】本発明の実施の形態３において、実計算部のスカラー倍点の計算方法を示すフロー図である。
【図１１】本発明の実施の形態４において、実計算部のスカラー倍点の計算方法を示すフロー図である。
【図１２】本発明の実施の形態６において、実計算部のスカラー倍点の計算方法を示すフロー図である。
【図１３】本発明の実施の形態７において、エンコード部の行うエンコード方法を示すフロー図である。
【図１４】本発明の実施の形態７、及び、本発明の一実施の形態における署名生成装置において、前計算部の前計算テーブル作成処理を示す概要図である。
【図１５】本発明の実施の形態７において、実計算部のスカラー倍点の計算方法を示すフロー図である。
【図１６】本発明の一実施の形態における署名生成装置を用いて構成される署名検証システムの構成を示す図である。
【図１７】本発明の一実施の形態における署名生成装置において、署名生成処理部における乱数倍計算部の機能ブロック構成を示す図である。
【図１８】本発明の実施の形態９における署名生成装置において、署名に必要な乱数生成及び乱数によるスカラー倍算の計算方法を示すフロー図である。
【図１９】本発明の実施の形態１０における署名生成装置において、署名に必要な乱数生成及び乱数によるスカラー倍算の計算方法を示すフロー図である。
【図２０】本発明の一実施の形態における署名生成装置を用いて構成される署名検証システムにおいて、各処理部間での情報の受け渡しを示すシーケンス図である。
【図２１】本発明の実施の形態７において、前計算部の前計算テーブル作成処理を示すフロー図（その１）である。
【図２２】本発明の実施の形態７において、前計算部の前計算テーブル作成処理を示すフロー図（その２）である。
【符号の説明】
【０４１７】
１０１，１２１，１６２１…コンピュータ、１６０１…スマートカード、１０２，１２２，１６０２，１６２２…記憶部、１１１，１３１，１６１１，１６３１…処理部、１１５，１３５，１６１５，１６３５…スカラー倍計算部、１１２，１３２…データ処理部、１６１２…署名生成処理部、１６３２…署名検証処理部、１０４，１２４，１６０４，１６２４…定数、１０５，１２５，１６０５，１６２５…秘密情報、１１０，１３０，１６１０，１６３０…入出力インタフェース、１０８，１２８，１６２８…ディスプレイ、１０９，１２９，１６２９…キーボード、１４２…ネットワーク、１６４２…チャレンジコード、１４１，１４３…データ、３０２…エンコード部、３０３…前計算部、３０４…実計算部、３２１…剰余取得部、３２２…剰余変換部、３２３…繰り返し判定部、３２４…δ剰余変換部、３２５…Ψ関数計算部、３２６…格納部、３３１…加算部、３３２…２倍算部、３３３…繰り返し判定部、３４１…ビット値判定部、３４２…加算部、３４３…τ倍算部、３４４…繰り返し判定部、９０２…前計算部、９０３…実計算部、９２１…加算部、９２２…τ倍算部、９２３…繰り返し判定部、９３１…剰余取得部、９３２…剰余変換部、９３３…繰り返し判定部、９３４…δ剰余変換部、９３５…Ψ関数計算部、９３６…ビット値判定部、９３７…加算部、９３８…τ倍算部、１７０１…乱数倍計算部、１７０２…前計算部、１７０３…実計算部、１７２１…加算部、１７２２…２倍算部、１７２３…繰り返し判定部、１７３１…剰余取得部、１７３２…剰余変換部、１７３３…繰り返し判定部、１７３４…格納部、１７３５…ランダムビット生成部、１７３６…Ψ関数計算部、１７３７…ビット値判定部、１７３８…加算部、１７３９…τ倍算部。
【図１】
2006243690.tif 000003
【図２】
2006243690.tif 000004
【図３】
2006243690.tif 000005
【図４】
2006243690.tif 000006
【図５】
2006243690.tif 000007
【図６】
2006243690.tif 000008
【図７】
2006243690.tif 000009
【図８】
2006243690.tif 000010
【図９】
2006243690.tif 000011
【図１０】
2006243690.tif 000012
【図１１】
2006243690.tif 000013
【図１２】
2006243690.tif 000014
【図１３】
2006243690.tif 000015
【図１４】
2006243690.tif 000016
【図１５】
2006243690.tif 000017
【図１６】
2006243690.tif 000018
【図１７】
2006243690.tif 000019
【図１８】
2006243690.tif 000020
【図１９】
2006243690.tif 000021
【図２０】
2006243690.tif 000022
【図２１】
2006243690.tif 000023
【図２２】
2006243690.tif 000024