(57)【要約】【課題】サイドチャネル攻撃を防ぐことのできる、かつ処理速度とメモリ使用量をカスタマイズできる、楕円曲線スカラー倍計算方法を提供すること。【解決手段】スカラー値及び楕円曲線上の点からスカラー倍点を計算するスカラー倍計算方法において、前計算テーブルの要素数を任意の値を取るように拡張し、前計算テーブルに格納する要素をランダムに選び、計算中に用いる前計算テーブルの要素を確率的に選択することにより、サイドチャネル攻撃を防ぐことができ、処理速度とメモリ使用量をカスタマイズできる。【選択図】  図１
2005055488.tif 000002
【特許請求の範囲】
【請求項１】
楕円曲線において、スカラー値及び楕円曲線上の点からスカラー倍点を計算する楕円曲線暗号におけるスカラー倍計算方法であって、
前記スカラー値を数値列にエンコードするステップと、
前記楕円曲線上の点から、ランダムに選んだ値を含む前計算テーブルを作成するステップと、
前記エンコードした数値列及び前記前計算テーブルからスカラー倍点を計算するステップと、を有する。
【請求項２】
請求項１記載のスカラー倍計算方法であって、さらに、
前記エンコードするステップは、前記スカラー値の剰余を選択するステップを含む。
【請求項３】
請求項１記載のスカラー倍計算方法であって、さらに、
前記エンコードするステップは、
前記スカラー値に対する第１の剰余と第２の剰余からどちらか一方の剰余を選択するステップを含み、
前記剰余を選択するステップは、
前記第１の剰余の大きさが予め定められた大きさより小さい場合は、予め定めた確率により前記第１の剰余もしくは前記第２の剰余を選択するステップと、
前記第１の剰余の大きさが前記大きさ以上の場合は、前記第１の剰余に付随する楕円曲線上の点が前計算テーブルに存在するか否かにより判定するステップとを含む。
【請求項４】
請求項２記載のスカラー倍計算方法であって、さらに、
前記スカラー倍点を計算するステップは、
第１の演算を予め定められた回数を実行するステップと、
第１の演算とは異なる第２の演算を実行するステップとを含む。
【請求項５】
楕円曲線において、スカラー値及び楕円曲線上の点からスカラー倍点を計算する楕円曲線暗号におけるスカラー倍計算方法であって、
前記楕円曲線上の点から、ランダムに選んだ値を含む前計算テーブルを作成するステップと、
前記スカラー値及び前記前計算テーブルからスカラー倍点を計算するステップと、を有する。
【請求項６】
請求項５記載のスカラー倍計算方法であって、さらに、
前記スカラー倍を計算するステップは、前記スカラー値の剰余を選択するステップを含む。
【請求項７】
請求項５記載のスカラー倍計算方法であって、さらに、
前記スカラー倍を計算するステップは、
前記スカラー値に対する第１の剰余と第２の剰余からどちらか一方の剰余を選択するステップを含み、
前記剰余を選択するステップは、
前記第１の剰余の大きさが予め定められた大きさより小さい場合は、予め定めた確率により前記第１の剰余もしくは前記第２の剰余を選択するステップと、
前記第１の剰余の大きさが前記大きさ以上の場合は、前記第１の剰余に付随する楕円曲線上の点が前計算テーブルに存在するか否かにより判定するステップとを含む。
【請求項８】
請求項６記載のスカラー倍計算方法であって、さらに、
前記スカラー倍点を計算するステップは、
第１の演算を予め定められた回数を実行するステップと、
第１の演算とは異なる第２の演算を実行するステップとを含む。
【請求項９】
請求項４記載のスカラー倍計算方法であって、
楕円曲線としてワイエルシュトラス型楕円曲線またはモンゴメリ型楕円曲線または標数２の有限体上で定義された楕円曲線またはＯＥＦ上で定義された楕円曲線を用いる。
【請求項１０】
請求項８記載のスカラー倍計算方法であって、
楕円曲線としてワイエルシュトラス型楕円曲線またはモンゴメリ型楕円曲線または標数２の有限体上で定義された楕円曲線またはＯＥＦ上で定義された楕円曲線を用いる。
【請求項１１】
第１のデータから第２のデータを生成するデータ生成方法であって、
請求項１に記載のスカラー倍計算方法を用いてスカラー倍を計算するステップを有する。
【請求項１２】
データから署名データを生成する署名作成方法であって、
請求項１に記載のスカラー倍計算方法を用いてスカラー倍を計算するステップを。
【請求項１３】
暗号化されたデータから復号化されたデータを生成する復号化方法であって、
請求項１に記載のスカラー倍計算方法を用いてスカラー倍を計算するステップを有する。
【請求項１４】
楕円曲線暗号における楕円曲線において、スカラー値及び楕円曲線上の点からスカラー倍点を計算するスカラー倍計算装置であって、
前記スカラー値を数値列にエンコードするエンコード部と、
前記楕円曲線上の点から、ランダムに選んだ値を含む前計算テーブルを作成する前計算部と、
前記エンコードした数値列及び前記前計算テーブルからスカラー倍点を計算する実計算部とを有する。
【請求項１５】
楕円曲線暗号における楕円曲線において、スカラー値及び楕円曲線上の点からスカラー倍点を計算するスカラー倍計算装置であって、
前記楕円曲線上の点から、ランダムに選んだ値を含む前計算テーブルを作成する前計算部と、
前記スカラー値及び前記前計算テーブルからスカラー倍点を計算する実計算部とを有する。
【請求項１６】
第１のデータから第２のデータを生成するデータ変換部と、前記データ変換部より依頼されてスカラー倍を計算するスカラー倍計算部とを有するデータ生成装置であって、
前記スカラー倍計算部は、請求項１に記載のスカラー倍計算方法を用いてスカラー倍を計算するステップを有。
【請求項１７】
データから署名データを生成する署名部と、前記署名部より依頼されてスカラー倍を計算するスカラー倍計算部とを有する署名作成装置であって、
前記スカラー倍計算部は、請求項１に記載のスカラー倍計算方法を用いてスカラー倍を計算するステップを有する。
【請求項１８】
暗号化されたデータから復号化されたデータを生成する復号部と、前記復号部より依頼されてスカラー倍を計算するスカラー倍計算部とを有する復号化装置であって、
前記スカラー倍計算部は、請求項１に記載のスカラー倍計算方法を用いてスカラー倍を計算するステップを有する。
【請求項１９】
請求項１に記載のスカラー倍計算方法を計算機に実行させるプログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明はセキュリティ技術に係り、特に楕円曲線演算を用いたメッセージ処理方法に関する。
【０００２】
【従来の技術】
楕円曲線暗号はＮ．  Ｋｏｂｌｉｔｚ，  Ｖ．  Ｓ．  Ｍｉｌｌｅｒにより提案された公開鍵暗号の一種である。公開鍵暗号には、公開鍵と呼ばれる一般に公開してよい情報と、秘密鍵（Ｐｒｉｖａｔｅ  Ｋｅｙ）と呼ばれる秘匿しなければならない秘密情報がある。与えられたメッセージの暗号化や署名の検証には公開鍵を用い、与えられたメッセージの復号化や署名の作成には秘密鍵を用いる。
【０００３】
楕円曲線暗号における秘密鍵は、スカラー値が担っている。また、楕円曲線暗号の安全性は楕円曲線上の離散対数問題の求解が困難であることに由来している。楕円曲線上の離散対数問題とは、楕円曲線上のある点Ｐとそのスカラー倍の点ｄＰが与えられた時、スカラー値ｄを求める問題である。
【０００４】
楕円曲線上の点とは、楕円曲線の定義方程式をみたす数の組をいい、楕円曲線上の点全体には、無限遠点という仮想的な点を単位元とした演算、すなわち楕円曲線上の加法（乃至は加算）が定義される。そして、同じ点同士による楕円曲線上の加法のことを、特に楕円曲線上の２倍算という。
【０００５】
楕円曲線上の２点の加法は次のようにして計算される。２点を通る直線を引くとその直線は楕円曲線と他の点において交わる。その交わった点とｘ軸に関して対称な点を、加法を行った結果の点とする。例えば、ワイエルシュトラス型楕円曲線の場合には、点（ｘ１，ｙ１）と点（ｘ２，ｙ２）の加算
（ｘ３，ｙ３）＝（ｘ１，ｙ１）＋（ｘ２，ｙ２）は
ｘ３＝（（ｙ２−ｙ１）／（ｘ２−ｘ１））２−ｘ１−ｘ２          （式１）
ｙ３＝（（ｙ２−ｙ１）／（ｘ２−ｘ１））（ｘ１−ｘ３）−ｙ１      （式２）を計算することにより得られる。ここで、ワイエルシュトラス型楕円曲線の定義式は
ｙ２＝ｘ３＋Ａｘ＋Ｂ                        （式３）
で与えられる。すなわち、式３のｘ，ｙに各々ｘｉ，ｙｉ  （ｉ＝１，２，３）  を代入した場合に、式３の等式が成り立つ。
【０００６】
楕円曲線上の点の２倍算は次のようにして計算される。楕円曲線上の点における接線をひくと、その接線は楕円曲線上の他の点において交わる。その交わった点とｘ座標に関して対称な点を、２倍算を行った結果の点とする。例えば、ワイエルシュトラス型楕円曲線の場合には、点（ｘ１，ｙ１）の２倍算
（ｘ３，ｙ３）＝２（ｘ１，ｙ１）＝（ｘ１，ｙ１）＋（ｘ１，ｙ１）は
ｘ３＝（（３ｘ１ ２＋Ａ）／（２ｙ１））２−２ｘ１            （式４）
ｙ３＝（（３ｘ１ ２＋Ａ）／（２ｙ１））（ｘ１−ｘ３）−ｙ１      （式５）
を計算することにより得られる。
【０００７】
ある点に対し、特定の回数だけ加法を行うことをスカラー倍といい、その結果をスカラー倍点、その回数のことをスカラー値という。
【０００８】
楕円曲線上の離散対数問題の求解の困難性が理論的に確立されてきている一方で、実際の実装においては秘密鍵等の秘密情報に関連する情報（計算時間や電力消費量など）が暗号処理において漏洩する場合があり、その漏洩情報をもとに秘密情報を復元するといった、サイドチャネル攻撃という攻撃法が提案されている。
【０００９】
楕円曲線暗号に対するサイドチャネル攻撃が、非特許文献１に記載されている。
【００１０】
楕円曲線暗号においては、与えられたメッセージの暗号化、復号化、署名の作成またはその検証は、楕円曲線演算を用いて行う必要がある。特に楕円曲線上のスカラー倍の計算は、秘密情報であるスカラー値を用いた暗号処理において用いられる。
【００１１】
楕円曲線暗号に対するサイドチャネル攻撃の防御法が、非特許文献２に記載されている。
【００１２】
【非特許文献１】
Ｊ．Ｃｏｒｏｎ，  Ｒｅｓｉｓｔａｎｃｅ  ａｇａｉｎｓｔ  Ｄｉｆｆｅｒｅｎｔｉａｌ  Ｐｏｗｅｒ  Ａｎａｌｙｓｉｓ  ｆｏｒ  Ｅｌｌｉｐｔｉｃ  Ｃｕｒｖｅ  Ｃｒｙｐｔｏｓｙｓｔｅｍｓ，  Ｃｒｙｐｔｏｇｒａｐｈｉｃ  Ｈａｒｄｗａｒｅ  ａｎｄ  Ｅｍｂｅｄｄｅｄ  Ｓｙｓｔｅｍｓ：  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ＣＨＥＳ’９９，  ＬＮＣＳ  １７１７，  Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，  （１９９９）  ｐｐ．２９２−３０２．
【非特許文献２】
Ｋ．Ｏｋｅｙａ，  Ｔ．Ｔａｋａｇｉ，  Ｔｈｅ  Ｗｉｄｔｈ−ｗ  ＮＡＦ  Ｍｅｔｈｏｄ  Ｐｒｏｖｉｄｅｓ  Ｓｍａｌｌ  Ｍｅｍｏｒｙ  ａｎｄ  Ｆａｓｔ  Ｅｌｌｉｐｔｉｃ  Ｓｃａｌａｒ  Ｍｕｌｔｉｐｌｉｃａｔｉｏｎｓ  Ｓｅｃｕｒｅ  ａｇａｉｎｓｔ  Ｓｉｄｅ  Ｃｈａｎｎｅｌ  Ａｔｔａｃｋｓ，  ＲＳＡ  ｃｏｎｆｅｒｅｎｃｅ  ｃｒｙｐｔｏｇｒａｐｈｅｒ’ｓ  ｔｒａｃｋ  （ＣＴ−ＲＳＡ  ２００３），  ＬＮＣＳ  ２６１２，  Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，  （２００３），  ｐｐ．３２８−３４１．
【００１３】
【発明が解決しようとする課題】
情報通信ネットワークの進展と共に電子情報に対する秘匿や認証の為に暗号技術は不可欠な要素となってきている。暗号技術に課せられる要件としては、安全性以外にも、処理速度や少ないメモリ使用量などがあるが、一般的に安全性、処理速度、メモリ使用量の間にはトレードオフの関係があり、全ての要件をみたすことは難しい。他方、楕円曲線上の離散対数問題が非常に困難である為に、素因数分解の困難性を安全性の根拠にしている暗号と比べて、楕円曲線暗号は鍵長を比較的短くすることができる。そのため計算能力、メモリ容量などのリソースが比較的少なくても暗号処理を行うことが可能である。しかしながら、スマートカード（ＩＣカードともいう）等においては利用可能なリソースは少なく、限られたリソース内で最適な暗号処理を行うように処理速度やメモリ使用量をカスタマイズできる暗号処理が必要となる。
【００１４】
上記技術は、サイドチャネル攻撃を防ぐ方法として有効であるが、処理速度やメモリ使用量をカスタマイズするという点については考慮されていない。
【００１５】
【課題を解決するための手段】
本発明は、サイドチャネル攻撃を防ぐことができる、かつ処理速度とメモリ使用量をカスタマイズできる、楕円曲線演算方法を提供する。
【００１６】
本発明は更に、上記楕円曲線演算方法を用いた、暗号化処理方法、復号化処理方法、署名作成方法、署名検証方法、データ共有方法を提供する。
【００１７】
本発明は、楕円曲線演算において、スカラー値と楕円曲線上の点からスカラー倍点を計算するスカラー倍計算方法であって、上記スカラー値を数値列にエンコードするステップと、上記楕円曲線上の点から前計算テーブルを作成するステップと、上記エンコードした数値列及び前記前計算テーブルからスカラー倍点を計算するステップとを有し、上記前計算テーブルはランダムに選ばれた要素を含む。
【００１８】
本発明は、また、上記エンコードするステップは、前記スカラー値の剰余を選択するステップを含むように構成してもよい。
【００１９】
本発明は、また、上記エンコードするステップは、上記スカラー値に対する第１の剰余と第２の剰余からどちらか一方の剰余を選択するステップを含み、上記剰余を選択するステップは、上記第１の剰余の大きさが予め定められた大きさより小さい場合は、予め定めた確率により上記第１の剰余もしくは上記第２の剰余を選択するステップと、上記第１の剰余の大きさが上記大きさ以上の場合は、上記第１の剰余に付随する楕円曲線上の点が前計算テーブルに存在するか否かにより判定するステップとを含むように構成してもよい。
【００２０】
本発明は、また、上記スカラー倍点を計算するステップは、第１の演算を予め定められた回数を実行するステップと、第１の演算とは異なる第２の演算を実行するステップとを含むように構成してもよい。
【００２１】
本発明は、また、楕円曲線演算において、スカラー値と楕円曲線上の点からスカラー倍点を計算するスカラー倍計算方法であって、上記楕円曲線上の点から前計算テーブルを作成するステップと、上記スカラー値及び上記前計算テーブルからスカラー倍点を計算するステップとを有し、上記前計算テーブルはランダムに選ばれた要素を含むように構成してもよい。
【００２２】
以上のように本発明のスカラー倍計算方法によれば、前計算テーブルに格納する点の個数の選択範囲が広く、かつ前計算テーブルの要素はランダムに選ばれるため、サイドチャネル攻撃を防ぐことができ、かつ処理速度とメモリ使用量をカスタマイズできるスカラー倍計算方法が利用可能になる。
【００２３】
【発明の実施の形態】
以下、本発明の実施例を図面により説明する。
【００２４】
図１はネットワーク１４２によって接続された本発明による楕円曲線演算方法を適用したコンピュータＡ１０１、コンピュータＢ１２１がネットワーク１４２により接続されたシステム構成を示すものである。
【００２５】
図１の暗号通信システムにおけるコンピュータＡ１０１でメッセージの暗号化を行うには、
Ｐｍ＋ｋ（ａＱ）及びｋＱを計算して出力し、コンピュータＢ１２１で暗号文の復号化を行うには、
秘密鍵ａ及びｋＱより−ａ（ｋＱ）を計算し、
（Ｐｍ＋ｋ（ａＱ））−ａ（ｋＱ）                （式６）
を計算して出力すればよい。ここでＰｍはメッセージ、ｋは乱数、ａは秘密鍵を示す定数、Ｑは定点、ａＱは公開鍵を示す点である。
【００２６】
ネットワーク１４２には、Ｐｍ＋ｋ（ａＱ），ｋＱのみ送信され、メッセージＰｍを復元するためには、ｋａＱ、すなわちｋＱのａ倍を計算する必要がある。ところが、秘密鍵ａはネットワーク１４２には送信されないため、秘密鍵ａを保持しているものだけが、Ｐｍを復元できることになる。
【００２７】
図１において、コンピュータＡ１０１は、ＣＰＵ１１３やコプロセッサ１１４などの演算装置、ＲＡＭ１０３、ＲＯＭ１０６や外部記憶装置１０７などの記憶装置、コンピュータ外部とのデータ入出力を行う入出力インタフェース１１０を装備しており、外部にはコンピュータＡ１０１をユーザが操作するためのディスプレイ１０８、キーボード１０９、着脱可能な可搬型記憶媒体の読み書き装置などが接続されている。
【００２８】
更にコンピュータＡ１０１は、ＲＡＭ１０３、ＲＯＭ１０６や外部記憶装置１０７などの記憶装置によって、記憶部１０２を実現し、ＣＰＵ１１３やコプロセッサ１１４などの演算装置が、記憶部１０２に格納されたプログラムを実行することにより、データ処理部１１２、スカラー倍計算部１１５とそれらに含まれる各処理部を実現する。
【００２９】
データ処理部１１２は、本実施形態においては、暗号化処理部１１２として機能し、入力されたメッセージの暗号化を行う。
【００３０】
スカラー倍計算部１１５は、暗号処理部１１２で暗号化を行うのに必要なパラメタを計算する。記憶部１０２は、定数１０４（例えば、楕円曲線の定義式や楕円曲線上の定点である）、秘密情報１０５（例えば、秘密鍵である）などを記憶している。
【００３１】
コンピュータＢ１２１は、コンピュータＡ１０１と同様のハードウェア構成を備える。
【００３２】
更にコンピュータＢ１２１は、ＲＡＭ１２３、ＲＯＭ１２６や外部記憶装置１０７などの記憶装置によって、記憶部１２２を実現し、ＣＰＵ１３３やコプロセッサ１３４などの演算装置が、記憶部１２２に格納されたプログラムを実行することにより、データ処理部１３２、スカラー倍計算部１３５とそれらに含まれる各処理部を実現する。
【００３３】
データ処理部１３２は、本実施形態においては、復号化処理部１３２として機能し、暗号化されたメッセージである暗号文１４１の復号化を行う。
【００３４】
スカラー倍計算部１３５は、復号化処理部１３２で復号化を行うのに必要なパラメタを計算する。記憶部１２２は、定数１２４（例えば、楕円曲線の定義式や楕円曲線上の定点である。）、秘密情報１２５（例えば、秘密鍵である。）などを記憶している。
【００３５】
なお、上記各プログラムは、あらかじめ、上記コンピュータ内の記憶部に格納されていても良いし、必要なときに、入出力インタフェース１１０と上記コンピュータ７２１が利用可能な媒体を介して、他の装置から上記記憶部に導入されてもよい。媒体とは、たとえば、入出力インタフェース１１０に着脱可能な記憶媒体、または通信媒体（すなわちネットワークまたはネットワークを伝搬する搬送波）を指す。
【００３６】
図２は、コンピュータＡ１０１、コンピュータＢ１２１の各処理部が行う情報の受け渡しの様子を示したものである。
【００３７】
次に、図１のコンピュータＡ１０１が、入力されたメッセージを暗号化する場合の動作について説明する。メッセージはディジタル化されたデータであれば良く、テキスト、画像、映像、音などの種類は問わない。
【００３８】
暗号化処理部１１２は、入出力インタフェース１１０を介して、平文メッセージ（図２の入力メッセージ２０４）を受け取ると、入力された平文メッセージのビット長が予め定めたビット長か否かを判断する。予め定めたビット長より長い場合には、予め定めたビット長となるように平文メッセージを区切る。以下、所定のビット長に区切られている部分メッセージ（単にメッセージともいう）について説明する。
【００３９】
次に、暗号化処理部１１２は、メッセージのビット列によって表される数値をｘ座標（ｘ１）にもつ楕円曲線上の点Ｐｍのｙ座標の値（ｙ１）を計算する。
【００４０】
例えば、ワイエルシュトラス型楕円曲線は、Ａ，Ｂをそれぞれ定数とするとき、ｙ１ ２＝ｘ１ ３＋Ａｘ１＋Ｂ      （式７）
で表されるので、これよりｙ座標の値を求めることができる。
【００４１】
次に、暗号化処理部１１２は、乱数ｋを生成する。そして、記憶部１０２に格納されている定数１０４から読み出した（図２の２０５）公開鍵ａＱとＱのｘ座標と、求めたｙ座標の値と乱数ｋとをスカラー倍計算部１１５へ送る（図２の２０６）。
【００４２】
スカラー倍計算部１１５は、Ｑのｘ座標、ｙ座標の値、乱数ｋによるスカラー倍点（ｘｄ１，ｙｄ１）＝ｋＱと、公開鍵ａＱのｘ座標、ｙ座標の値、乱数によるスカラー倍点（ｘｄ２，ｙｄ２）＝ｋ（ａＱ）とを計算し、計算されたスカラー倍点を暗号化処理部１１２へ送る（図２の２０７）。
【００４３】
暗号化処理部１１２は、送られたスカラー倍点を用いて、暗号化処理を行う。例えば、ワイエルシュトラス型の楕円曲線については、Ｐｍ＋ｋ（ａＱ）とｋＱを計算する。すなわち、
ｘｅ１＝（（ｙｄ１−ｙ１）／（ｘｄ１−ｘ１））２−ｘ１−ｘｄ１，          （式８）
ｘｅ２＝ｘｄ２                              （式９）
を計算し、暗号化されたメッセージｘｅ１，ｘｅ２を得る。
【００４４】
コンピュータＡ１０１は暗号化処理部１１２で暗号化された１つ以上の部分メッセージから暗号化された出力メッセージを組み立てる（図２の２０８）。
【００４５】
コンピュータＡ１０１は、暗号化された出力メッセージをデータ１４１として入出力インタフェース１１０より出力し、ネットワーク１４２を介してコンピュータＢ１２１へ転送する。
【００４６】
なお、図２の記憶部１０２からの情報読み出しは、スカラー計算部１１５へ当該情報を送る前で有れば、入力メッセージを受け付ける前であっても良い。
【００４７】
次に、コンピュータＢ１２１が、暗号化されたメッセージ１４１を復号化する場合の動作について、図２を参照しつつ説明する。
【００４８】
復号化処理部１３２（図２のデータ処理部１１２）は、入出力インタフェース１１０を介して、暗号化されたデータ１４１（図２の入力メッセージ２０４）が入力されると、入力された暗号化されたデータ１４１のビット長が予め定めたビット長か否かを判断する。予め定めたビット長より長い場合には、予め定めたビット長となるように暗号化されたデータを区切る。以下、所定のビット長に区切られている部分データ（単にデータともいう）について説明する。
【００４９】
データ１４１のビット列によって表される数値をｘ座標にもつ楕円曲線上のｙ座標の値を計算する。
【００５０】
暗号化されたメッセージがｘｅ１，ｘｅ２のビット列であり、ワイエルシュトラス型楕円曲線の場合、ｙ座標の値（ｙｅ１）は
ｙｅ１ ２＝ｘｅ１ ３＋Ａｘｅ１＋Ｂ              （式１０）
（ただし、Ａ，Ｂはそれぞれ定数である）
から得ることができる。
【００５１】
復号化処理部１３２は、記憶部１２２（図２の１０２）に格納されている秘密情報１２５から読み出した（図２の２０５）秘密鍵ａと、ｘ座標、ｙ座標の値（ｘｅ１，ｙｅ１）を、スカラー倍計算部１３５（図２の１１５）へ送る（図２の２０６）。
【００５２】
スカラー倍計算部１３５は、ｘ座標、ｙ座標の値、秘密情報ａ１２５からスカラー倍点（ｘｄ３，ｙｄ３）＝ａ（ｘｅ２，ｙｅ２）を計算する。スカラー倍計算部１３５は、計算されたスカラー倍点を復号化処理部１３２へ送る（図２の２０７）。復号化処理部１３２は、送られたスカラー倍点を用いて、復号化処理を行う。
【００５３】
例えば、暗号化されたメッセージが、ｘｅ１，ｘｅ２のビット列であり、ワイエルシュトラス型の楕円曲線の場合は、
（Ｐｍ＋ｋ（ａＱ））−ａ（ｋＱ）＝（ｘｅ１，ｙｅ１）−（ｘｄ３，ｙｄ３）
を計算することにより達成する。すなわち、
ｘｆ１＝（（ｙｅ１＋ｙｄ３）／（ｘｅ１−ｘｄ３））２−ｘｅ１−ｘｄ３        （式１１）
を計算し、暗号化される前の部分メッセージｘ１に相当するｘｆ１を得る。
【００５４】
コンピュータＢ１２１は、復号化処理部１３２で復号化された部分メッセージから平文メッセージを組み立て（図２の２０８）、入出力インタフェース１１０を介して、ディスプレイ１０８などから出力する。
【００５５】
次に、コンピュータＢ１２１が、復号化処理を行う場合の、スカラー倍計算部１３５の処理を詳細に説明する。
【００５６】
第１実施例では、図３で示されるスカラー倍計算部の機能ブロックを用いる。スカラー倍計算部１１５（図１の１３５）は、エンコード部３０２、前計算部３０３、実計算部３０４からなる。エンコード部３０２は、剰余取得部３２１、インデックス集合生成部３２２、剰余選択部３２３、繰り返し判定部３２４、格納部３２５からなる。前計算部３０３は、加算部３３１、２倍算部３３２、繰り返し判定部３３３からなる。実計算部３０４は、ビット値判定部３４１、加算部３４２、２倍算部３４３、繰り返し判定部３４４からなる。
【００５７】
スカラー倍計算部１１５がスカラー値ｄ及び楕円曲線上の点Ｐから、楕円曲線におけるスカラー倍点ｄＰを計算する第１の計算方法を説明する。
【００５８】
スカラー倍計算部１１５が復号化処理部１３２からスカラー値ｄと楕円曲線上の点Ｐを受け取ると、エンコード部３０２は、入力されたスカラー値ｄを数値列ｄｗ［ｊ］にエンコードする。すなわち、
ｄ＝ｄｗ［ｎ＋ｗ０−１］２ｎ＋ｗ０−１＋ｄｗ［ｎ＋ｗ０−２］２ｎ＋ｗ０−２＋・・・＋ｄｗ［ｊ］２ｊ＋・・・  ＋ｄｗ［０］
（式１２）
−２ｗ０−１≦ｄｗ［ｊ］≦２ｗ０−１  ｏｒ  ｄｗ［ｊ］∈Ｂ                                                        （式１３）
をみたすｄｗ［ｊ］に、スカラー値ｄを変換する。ここで、ｎはスカラー値ｄを２進表記した場合のビット長であり、ｗはあらかじめ定めた小さな正有理数で、ウィンドウ幅と呼ばれる。ｗ０は正整数であり、ｗ０＝ｃｅｉｌ（ｗ）をみたす。ただし、ｃｅｉｌ（ｗ）はｗ以上の最小の整数を表す。Ｂはランダムに選ばれたインデックス集合であり、
Ｂ＝｛±ｂ１，±ｂ２，・・・，±ｂｍ｝と表される。ただし、ｍ個の相異なるｂ１，ｂ２，・・・，ｂｍは
｛２ｗ０−１＋１，２ｗ０−１＋３，・・・，２ｗ０−１｝の範囲から選ばれる。
ここで、ｍ＝ｗ１２ｗ０−２，  ｗ１＝ｗ−（ｗ０−１）である。計算時間を優先する場合はｗを大きな値とする。メモリ使用量を小さくする場合はｗを小さな値にする。尚、ウィンドウ幅ｗはｍが整数となるように定められる。正整数ｗ０を固定し、ウィンドウ幅ｗを動かした場合、整数ｍは０から２ｗ０−２までの値を取り得る。
【００５９】
前計算部３０３は、入力された楕円曲線上の点Ｐから、インデックス集合Ｂを用いて前計算テーブルを作成する。前計算テーブルはＰ，  ３Ｐ，  ・・・，  （２ｗ０−１−１）Ｐ及びｂｊＰ，  ｊ＝１，・・・，ｍにより構成される。
【００６０】
実計算部３０４は、エンコードされたスカラー値と楕円曲線上の点Ｐから、前計算テーブルを用いてスカラー倍点ｄＰを計算する。
【００６１】
次にエンコード部３０２、前計算部３０３、実計算部３０４の行う各処理について詳細に説明する。
【００６２】
まず、図４を用いて、エンコード部３０２がスカラー値ｄをエンコードする方法を説明する。
【００６３】
変数ｄ’にスカラー値ｄを代入する。ｗ０にｃｅｉｌ（ｗ）を、ｗ１にｗ−（ｗ０−１）をそれぞれ割り当てる（４０１）。
【００６４】
インデックス集合生成部３２２は、ｍ＝ｗ１２ｗ０−２とし、ｍ個の相異なる
ｂ１，ｂ２，・・・，ｂｍを｛２ｗ０−１＋１，２ｗ０−１＋３，・・・，２ｗ０−１｝よりランダムに選び、インデックス集合ＢをＢ＝｛±ｂ１，±ｂ２，・・・，±ｂｍ｝とする。確率を示す数値Ｐｗにｗ１を割り当てる（４０２）。
【００６５】
変数ｒに初期値０を、変数ｉに初期値０をそれぞれ代入する（４０３）。
【００６６】
繰り返し判定部３２４は、変数ｄ’が１より大きいかどうかを判定する。
【００６７】
ｄ’が１より大きければステップ４１１へ行く。１以下であればステップ４３１へ行く（４０４）。
【００６８】
ステップ４０４でｄ’が１より大きい場合、
剰余取得部３２１は、スカラー値ｄ’の２ｗ０＋１による剰余から２ｗ０を引いた値をｘ［ｉ］に、スカラー値ｄ’の２ｗ０による剰余から２ｗ０−１を引いた値をｙ［ｉ］に、それぞれ格納する（４１１）。
【００６９】
剰余選択部３２３は、｜ｘ［ｉ］｜＜２ｗ０−１であるかどうかを判定する。ここで、｜ｘ［ｉ］｜はｘ［ｉ］の絶対値を表す。｜ｘ［ｉ］｜＜２ｗ０−１であればステップ４１３へ行く。｜ｘ［ｉ］｜≧  ２ｗ０−１であればステップ４２１へ行く（４１２）。
【００７０】
ステップ４１２で｜ｘ［ｉ］｜＜２ｗ０−１  の場合、
剰余選択部３２３は、確率Ｐｗでｒｉにｗ０を、ｕ［ｉ］にｘ［ｉ］をそれぞれ格納し、確率１−Ｐｗでｒｉにｗ０−１を、ｕ［ｉ］にｙ［ｉ］をそれぞれ格納し、ステップ４１４へ行く（４１３）。
【００７１】
ステップ４１２で｜ｘ［ｉ］｜≧  ２ｗ０−１の場合、
剰余選択部３２３は、ｘ［ｉ］が集合Ｂに属するかどうかを判定する。ｘ［ｉ］がＢに属する場合はステップ４２２へ行く。ｘ［ｉ］がＢに属さない場合はステップ４２３へ行く（４２１）。
【００７２】
ステップ４２１でｘ［ｉ］がＢに属する場合、
剰余選択部３２３は、ｒｉにｗ０を、ｕ［ｉ］にｘ［ｉ］をそれぞれ格納し、ステップ４１４へ行く（４２２）。
【００７３】
ステップ４２１でｘ［ｉ］がＢに属さない場合、
剰余選択部３２３は、ｒｉにｗ０−１を、ｕ［ｉ］にｙ［ｉ］をそれぞれ格納し、ステップ４１４へ行く（４２３）。
【００７４】
剰余取得部３２１は、（ｄ’−ｕ［ｉ］）／２ｒｉを計算し、それを新たなｄ’とする（４１４）。
【００７５】
格納部３２５は、ｄｗ［ｒ＋ｒｉ−１］，  ｄｗ［ｒ＋ｒｉ−２］，  ・・・，  ｄｗ［ｒ］にそれぞれ、０，０，・・・，０，ｕ［ｉ］を格納する（４１５）。
【００７６】
変数ｒをｒｉだけ増加させ、変数ｉを１増加させ、ステップ４０４へ戻る（４１６）。
【００７７】
ステップ４０４でｄ’が１以下であった場合、
格納部３２５は、ｄｗ［ｎ＋ｗ０−１］，・・・，ｄｗ［ｒ＋１］，ｄｗ［ｒ］にそれぞれ、０，・・・，０，１を格納する（４３１）。
【００７８】
エンコード部３０２は、ｄｗ［ｎ＋ｗ０−１］，・・・，ｄｗ［０］及びＢを実計算部３０４へ出力する（４３２）。
【００７９】
次に、図５を用いて、前計算部３０３が楕円曲線上の点から、インデックス集合Ｂを用いて前計算テーブルを作成する方法を説明する。
【００８０】
点ＰをＥＣＤＢＬにより２倍し、その結果を２Ｐに格納する（５０１）。
【００８１】
変数ｊに初期値１を代入する（５０２）。
【００８２】
繰り返し判定部３３３により、ｊが２ｗ０−１より小さいかどうかを判定する。ｊが２ｗ０−１より小さい場合はステップ５０４へ行く。ｊが２ｗ０−１以上の場合はステップ５１１へ行く（５０３）。
【００８３】
ステップ５０３でｊが２ｗ０−１より小さい場合、
点ｊＰと点２ＰをＥＣＡＤＤにより加算し、その結果を（ｊ＋２）Ｐに格納する（５０４）。
【００８４】
変数ｊを２増加させ、ステップ５０３へ戻る（５０５）。
【００８５】
ステップ５０３でｊが２ｗ０−１以上の場合、
点（２ｗ０−１−１）Ｐと点ＰをＥＣＡＤＤにより加算し、その結果を２ｗ０−１Ｐに格納する（５１１）。
【００８６】
変数ｊに１を代入する（５１２）。
【００８７】
繰り返し判定部３３３により、ｊがｍ以下であるかどうかを判定する。ｊがｍ以下であればステップ５１４へ行く。ｊがｍより大きい場合はステップ５２１へ行く（５１３）。
【００８８】
ステップ５１３でｊがｍ以下の場合、
点２ｗ０−１Ｐと点（ｂｊ−２ｗ０−１）ＰをＥＣＡＤＤにより加算し、その結果をｂｊＰに格納する（５１４）。
【００８９】
変数ｊを１増加させ、ステップ５１３へ戻る（５１５）。
【００９０】
ステップ５１３でｊがｍより大きい場合、
Ｐ，  ３Ｐ，  ・・・，  （２ｗ０−１−１）Ｐ及びｂｊＰ，  ｊ＝１，・・・，ｍを前計算テーブルとして出力する（５２１）。
【００９１】
ただし、ＥＣＡＤＤ，  ＥＣＤＢＬはそれぞれ楕円曲線における加算、２倍算を表す。加算は式１，２を用いて、２倍算は式４，５を用いてそれぞれ計算される。なお、加算、２倍算の計算には式１，２、および式４，５を用いる以外にも、射影座標やヤコビアン座標における計算公式があり、
非特許文献３：Ｃｏｈｅｎ，  Ｈ．，  Ｍｉｙａｊｉ，  Ａ．，  Ｏｎｏ，  Ｔ．，  Ｅｆｆｉｃｉｅｎｔ  Ｅｌｌｉｐｔｉｃ  Ｃｕｒｖｅ  Ｅｘｐｏｎｅｎｔｉａｔｉｏｎ  Ｕｓｉｎｇ  Ｍｉｘｅｄ  Ｃｏｏｒｄｉｎａｔｅｓ，  Ａｄｖａｎｃｅｓ  ｉｎ  Ｃｒｙｐｔｏｌｏｇｙ  −  ＡＳＩＡＣＲＹＰＴ  １９９８，  ＬＮＣＳ  １５１４，  Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，  （１９９８），  ｐｐ．５１−６５．
に記載されている。
【００９２】
また、楕円曲線上の点Ｑ＝（ｘ，ｙ）に対して、楕円曲線加算に関する逆元の点−Ｑは、−Ｑ＝（ｘ，−ｙ）と表されるため、点Ｑの座標が与えられていれば容易に計算できる。
そのため、
点Ｐ，  ３Ｐ，  ・・・，  （２ｗ０−１−１）Ｐ及びｂｊＰ，  ｊ＝１，・・・，ｍ  のみを前計算テーブルとして格納する。その後の実計算部３０４が行う計算で必要となる
点−Ｐ，  −３Ｐ，  ・・・，  −（２ｗ０−１−１）Ｐ及び−ｂｊＰ，  ｊ＝１，・・・，ｍ  は、それらから導出すればよく、前計算テーブルには格納する必要はない。
【００９３】
なお、点−Ｐ，  −３Ｐ，  ・・・，  −（２ｗ−１）Ｐ及び−ｂｊＰ，  ｊ＝１，・・・，ｍの導出を省くために、それらの点のｙ座標の値のみを前計算テーブルに格納しておいてもよい。
【００９４】
なお、前計算部３０３の行う前計算テーブルの作成処理は、
点Ｐ，  ３Ｐ，  ・・・，  （２ｗ０−１−１）Ｐ及びｂｊＰ，  ｊ＝１，・・・，ｍが計算されればよい。そのため、モンゴメリトリックを用いて、楕円曲線演算で必要となる逆元演算の計算の共通化を行うことにより、高速化をはかってもよい。
【００９５】
モンゴメリトリックによる逆元演算共通化方法が
非特許文献４：Ｃｏｈｅｎ，  Ｈ．，  Ａ  ｃｏｕｒｓｅ  ｉｎ  ｃｏｍｐｕｔａｔｉｏｎａｌ  ａｌｇｅｂｒａｉｃ  ｎｕｍｂｅｒ  ｔｈｅｏｒｙ，  ＧＴＭ１３８，  Ｓｐｒｉｎｇｅｒ  −Ｖｅｒｌａｇ，  （１９９３）．
の４８１ページに記載されている。
【００９６】
また、点Ｐが固定点である場合、前計算部３０３の行う前計算テーブルの作成処理のうち、
点Ｐ，  ３Ｐ，  ・・・，  （２ｗ０−１−１）Ｐの計算、すなわち、ステップ５０１からステップ５１１の処理は、ただ一度行えばよい。なぜならば、
点Ｐ，  ３Ｐ，  ・・・，  （２ｗ０−１−１）Ｐは、インデックス集合Ｂに依存していないからである。そのため、一旦
点Ｐ，  ３Ｐ，  ・・・，  （２ｗ０−１−１）Ｐを計算すれば、それ以降のスカラー倍計算では、
点Ｐ，  ３Ｐ，  ・・・，  （２ｗ０−１−１）Ｐを再計算する必要はなく、インデックス集合Ｂに依存する部分のみを再計算すればよい。
【００９７】
最後に、図６を用いて、実計算部３０４がエンコードされたスカラー値と楕円曲線上の点から、楕円曲線におけるスカラー倍点を計算する方法を説明する。
【００９８】
変数ｃに初期値ｎ＋ｗ０−１を代入する（６０１）。
【００９９】
ｄｗ［ｃ］が０か０でないかを判定する。
【０１００】
ｄｗ［ｃ］が０の場合はステップ６０３へ行く。０でなければステップ６１１へ行く（６０２）。
【０１０１】
変数ｃを１減少させ、ステップ６０２へ戻る（６０３）。
【０１０２】
ステップ６０２でｄｗ［ｃ］が０でない場合、点Ｑにｄｗ［ｃ］Ｐを代入する（６１１）。
【０１０３】
変数ｊに初期値ｃ−１を代入する（６１２）。
【０１０４】
ｊが０より小さいかどうかを判定する。ｊが０より小さい場合はステップ６２１へ行く。０以上の場合はステップ６１４へ行く（６１３）。
【０１０５】
点ＱをＥＣＤＢＬにより２倍し、点Ｑに再び格納する（６１４）。
【０１０６】
ｄｗ［ｊ］が０か０でないかを判定する。
【０１０７】
ｄｗ［ｊ］が０の場合はステップ６１７へ行く。０でなければステップ６１６へ行く（６１５）。
【０１０８】
ステップ６１５でｄｗ［ｊ］が０でない場合、
点Ｑとｄｗ［ｊ］ＰとをＥＣＡＤＤにより加算する。ただし、ｄｗ［ｊ］が負の場合は（−ｄｗ［ｊ］）Ｐのｙ座標を反転したものを用いて加算を行う。その結果を点Ｑに格納し、ステップ６１７へ行く（６１６）。
なお、ｄｗ［ｊ］が０でない場合は、ｄｗ［ｊ］は式１３をみたす奇数である。そのため、ｄｗ［ｊ］Ｐもしくは（−ｄｗ［ｊ］）Ｐのいずれかが、前計算テーブルに必ず存在する。
【０１０９】
変数ｊを１減少させ、ステップ６１３へと戻る（６１７）。
【０１１０】
ステップ６１３でｊが０より小さい場合、点Ｑを出力する（６２１）。
【０１１１】
エンコード部３０２が行う処理により出力されるｄｗ［ｊ］は、式１２，  式１３をみたす。
この理由は次の通りである。
ステップ４０４からステップ４１６のループにおいて、ｉ回目のｄ’の値をｄ’［ｉ］とおく。
すなわち、ステップ４１４で
ｄ’［ｉ＋１］＝（ｄ’［ｉ］−ｕ［ｉ］）／２ｒｉ                （式１４）
が計算される。０回目のループでは
ｄ＝ｄ’［０］                                                  （式１５）
となる。１回目のループでは
ｄ＝ｄ’［１］２ｒ０＋ｕ［０］                                  （式１６）
となる。以下同様にして、ｉ回目のループでは
ｄ＝（・・・（ｄ’［ｉ］２ｒｉ＋ｕ［ｉ］）２ｒｉ−１＋・・・＋ｕ［１］）２ｒ０＋ｕ［０］        （式４８）
となる。ステップ４１４の計算は、ｄ’［ｉ］＜２ｒｉ＋１のとき、
ｄ’−（（ｄ’ｍｏｄ  ２ｒｉ＋１）−２ｒｉ）＝２ｒｉ                （式１７）
となるため、ｄ’［ｉ＋１］＝１となる。ステップ４１５で、ｄｗ［ｒ］以外に０が割り当てられていることに注意すれば、ｄが式１２をみたすことがわかる。
ステップ４１１で計算されるｙ［ｉ］は、
−２ｗ０−１≦ｙ［ｉ］≦２ｗ０−１                                （式１８）
の範囲となることは容易にわかる。
ｘ［ｉ］が
−２ｗ０−１≦ｘ［ｉ］≦２ｗ０−１                                （式１９）
の範囲にある場合は特に問題はない。
ｘ［ｉ］が式１９の範囲外の場合は、ステップ４１２の判定結果によりステップ４２１へ行く。ステップ４２１ではｘ［ｉ］∈Ｂの場合に、ステップ４２２へ行き、ｘ［ｉ］が選択される。
すなわち、
ｘ［ｉ］∈Ｂ                                                  （式２０）
をみたす。ｕ［ｉ］はｘ［ｉ］，ｙ［ｉ］のいずれかが割り当てられ、０以外のｄｗ［ｒ］はｕ［ｉ］が割り当てられる。
したがって、式１３をみたす。
【０１１２】
エンコード部３０２が行う処理で計算されるｕ［ｉ］はｉ＝０を除き全て奇数となる。この理由は次の通りである。ステップ４１１で、ｄ’［ｉ］が奇数であれば、ｘ［ｉ］，ｙ［ｉ］は奇数となる。そのため、ｄ’［ｉ］が奇数の場合、ｕ［ｉ］は奇数となる。一方、ステップ４１４で、ｄ’［ｉ＋１］＝（ｄ’［ｉ］−ｕ［ｉ］）／２ｒｉが計算される。
ｄ’［ｉ］−（（ｄ’［ｉ］  ｍｏｄ  ２ｒｉ＋１）−２ｒｉ）  ｍｏｄ  ２ｒｉ＋１  ＝  ２ｒｉ          （式２１）
であるため、ｄ’［ｉ＋１］は奇数となる。したがって、ｉ＝０を除き、ｕ［ｉ］は全て奇数である。
【０１１３】
なお、ｕ［０］も奇数とするためには、スカラー値ｄが奇数であればよい。そのためには、入力されたスカラー値ｄが偶数の時は、ｄ＋１を改めてスカラー値ｄ’としてエンコードする。すなわち、ｄを奇数に変換する。そして、スカラー倍点ｄ’Ｐを計算する。
ｄ’Ｐ＝（ｄ＋１）Ｐ＝ｄＰ＋Ｐ            （式２２）
であるので、ｄ’Ｐから点Ｐを引き、その値をスカラー倍点ｄＰとして出力すればよい。
【０１１４】
また、入力されたｄが奇数の時は、ｄ＋２を改めてスカラー値ｄ’としてエンコードし、
ｄ’Ｐ＝（ｄ＋２）Ｐ＝ｄＰ＋２Ｐ            （式２３）
を利用して、スカラー倍点ｄＰを求めてもよい。この場合、ｄが奇数の場合も偶数の場合も、行う処理が一致するという利点がある。
【０１１５】
実計算部３０４が出力する点Ｑはスカラー倍点ｄＰに等しい。この理由は次の通りである。
【０１１６】
ステップ６１３において点Ｑが
（ｄｗ［ｃ］２ｃ−（ｊ＋１）＋ｄｗ［ｃ−１］２（ｃ−１）−（ｊ＋１）＋・・・＋  ｄｗ［ｊ＋１］２（ｊ＋１）−（ｊ＋１））Ｐ                （式２４）
と表されるとする。このとき、次にステップ６１３に来る時も点Ｑは式２４をみたすことを示す。
【０１１７】
点Ｑはステップ６１４で２倍され、ｄｗ［ｊ］が０でなければステップ６１６でｄｗ［ｊ］Ｐが加えられる。そのためステップ６１６の直後では、点Ｑの値は
（ｄｗ［ｃ］２ｃ−ｊ＋ｄｗ［ｃ−１］２（ｃ−１）−ｊ＋・・・＋ｄｗ［ｊ＋１］２（ｊ＋１）−ｊ＋  ｄｗ［ｊ］２ｊ−ｊ）Ｐ              （式２５）
となる。したがってｄｗ［ｊ］＝０の時も含めて、ステップ６１７の直前で、点Ｑは式２５をみたす。ステップ６１７でｊが１減少するので、式２５のｊにｊ＋１を代入すると式２４になる。すなわち、次にステップ６１３に来る時も点Ｑは式２４をみたす。
【０１１８】
ｊ＞ｃに対するｄｗ［ｊ］の値は０であるので、ステップ６２１で出力される点Ｑの値は
（ｄｗ［ｎ］２ｎ＋ｄｗ［ｎ−１］２ｎ−１＋・・・＋ｄｗ［０］）Ｐ        （式２６）
に等しい。実計算部３０４に入力されるスカラー値は、エンコード部３０２によりエンコードされたｄｗ［ｊ］であるので、そのｄｗ［ｊ］は式１２をみたす。したがって、Ｑ＝ｄＰである。
【０１１９】
上記スカラー倍におけるメモリ使用量は、前計算部３０３の前計算テーブルの大きさにより定まる。上記スカラー倍計算方法では、前計算テーブルは
Ｐ，３Ｐ，・・・，（２ｗ０−１−１）Ｐ及びｂｊＰ，  ｊ＝１，・・・，ｍ  により構成される。すなわち、格納する点の個数は（２ｗ０−２＋ｍ）個である。正整数ｗ０を固定し、ウィンドウ幅ｗを動かした場合、整数ｍは０から２ｗ０−２までの値を取り得る。そのため、ウィンドウ幅ｗを適切に選択することにより、格納する点の個数は任意の値にできる。一方、非特許文献２の方法では、前計算テーブルに格納する点の個数は１，２，４，８，・・・  と２ベキの値しか選択できない。そのため、上記スカラー倍計算方法は、非特許文献２の方法と比べて、前計算テーブルに格納する点の個数の選択範囲が広く、処理速度やメモリ使用量をカスタマイズすることができる。
【０１２０】
また、上記スカラー倍方法は、サイドチャネル攻撃に対する防御法に関しても有効である。この理由は次の通りである。
【０１２１】
エンコード部３０２によりスカラー値ｄは数値列ｄｗ［ｊ］にエンコードされる。この数値列ｄｗ［ｊ］はパターン
｜０・・・０ｘ｜０・・・０ｘ｜・・・｜０・・・０ｘ｜    （式２７）
をもつ。ここで各ｘは各々非０の値であり、それぞれｕ［ｉ］に対応する。ここで０・・・０はｒｉ個、すなわちｗ０−１個もしくはｗ０−２個連続する。実計算部３０４がスカラー倍点を計算する際に、ステップ６１３−６１７の繰り返し処理において、｜０・・・０ｘ｜のブロックに対応する楕円曲線演算は、｜Ｄ・・・ＤＡ｜、すなわちｗ０回もしくはｗ０−１回のＤの後にＡとなる。ただし、ＤはＥＣＤＢＬを、ＡはＥＣＡＤＤをそれぞれ表す。一方ｒｉは、確率Ｐｗでｗ０となり、確率１−Ｐｗでｗ０＋１となる。
なぜならば、｜ｘ［ｉ］｜＜２ｗ０−１の場合、ステップ４１３において確率Ｐｗでｒｉ＝ｗ０、確率１−Ｐｗでｒｉ＝ｗ０＋１となる。
また｜ｘ［ｉ］｜≧２ｗ０−１の場合、ｘ［ｉ］∈Ｂとなる確率は、
（Ｂの要素数）／（２ｗ０−１≦｜ｋ｜＜２ｗ０をみたす奇数ｋの個数）＝ｗ１であるので、Ｐｗとなる。
この場合、
ｘ［ｉ］∈Ｂの時にｒｉ＝ｗ０、そうでない時にｒｉ＝ｗ０−１となる。したがって、いずれの場合においても、ｒｉは、確率Ｐｗでｗ０となり、確率１−Ｐｗでｗ０−１となる。確率Ｐｗは公開情報であるｗ１にのみ依存し、秘密情報には依存していない。結果として、全てのスカラー値に対して、実行する楕円曲線演算は
｜Ｄ・・・ＤＡ｜Ｄ・・・ＤＡ｜・・・｜Ｄ・・・ＤＡ｜    （式２８）
となり、Ｄの連続する回数は各々ｒｉであるが、この値は公開情報ｗ１にのみ依存し、秘密情報には依存しない。特に、式２８のみからは、スカラー値ｄに関する情報を引き出すことができない。
【０１２２】
なお、非特許文献１のランダム化射影座標を併用してスカラー倍計算を行ってもよい。そうすると、同じ点Ｐを入力しても実行毎に異なる値に変換してスカラー倍計算を行うので、攻撃者が中間値の値を予測できなくなる。
【０１２３】
また、前計算テーブルに格納されている点が読み出されるたびに、再びランダム化して、前計算テーブルに書き込んでもよい。そうすると、同じデータの再使用がなくなるため、より一層、サイドチャネル攻撃への耐性が増す。
【０１２４】
また、一つのスカラー倍計算中に一度以上、当該計算中に参照する前計算テーブルを再作成してもよい。そうすることにより、テーブルから引用される値がより頻繁に変更されることになり、サイドチャネル攻撃への耐性がさらに増す。
【０１２５】
また、任意回数のスカラー倍計算において、同一の前計算テーブルを再利用してもよい。そうすることにより、前計算テーブルの作成処理に掛かる時間を減らせるため、計算時間を短縮することができる。
【０１２６】
また、スカラー倍計算毎に、必要とされる計算速度、同時に使用する他のアプリケーションの優先度などの状況に応じて、前計算テーブルのサイズを変更してもよい。
【０１２７】
より具体的には、利用可能なワーク領域を調べて、そのワーク領域に応じた前計算テーブルサイズを選択し、スカラー倍を計算してもよい。そうすることにより、個別状況に応じたカスタマイズをより繊細に行うことができる。
【０１２８】
あるいは、スカラー倍以外のモジュールの処理に優先的にワーク領域を割り当てるために、前計算テーブルのサイズを小さくしてスカラー倍計算を行ってもよい。
【０１２９】
あるいは、スカラー倍計算を高速に行うため、前計算テーブルのサイズを大きくしてスカラー倍計算を行なってもよい。
【０１３０】
以上の通り、上記計算方法は、サイドチャネル攻撃に有用な情報を与えないので、サイドチャネル攻撃に対して耐性がある。また、前計算テーブルに格納する点の個数の選択範囲が広いため、処理速度やメモリ使用量をカスタマイズすることができる。
【０１３１】
なお、第１の計算方法では楕円曲線としてワイエルシュトラス型楕円曲線を用いたが、標数２の有限体上で定義された楕円曲線や、ＯＥＦ（Ｏｐｔｉｍａｌ  Ｅｘｔｅｎｓｉｏｎ  Ｆｉｅｌｄ）上で定義された楕円曲線、もしくはモンゴメリ型楕円曲線を用いてもよい。ＯＥＦについては、
非特許文献５：Ｄ．Ｖ．  Ｂａｉｌｅｙ，  Ｃ．  Ｐａａｒ，  Ｏｐｔｉｍａｌ  Ｅｘｔｅｎｓｉｏｎ  Ｆｉｅｌｄｓ  ｆｏｒ  Ｆａｓｔ  Ａｒｉｔｈｍｅｔｉｃ  ｉｎ  Ｐｕｂｌｉｃ−Ｋｅｙ  Ａｌｇｏｒｉｔｈｍｓ，  Ａｄｖａｎｃｅｓ  ｉｎ  Ｃｒｙｐｔｏｌｏｇｙ  Ｃｒｙｐｔｏ  ’９８，  ＬＮＣＳ  １４６２，  （１９９８），  ４７２−４８５．
に記載されている。
【０１３２】
第２実施例では、図７で示されるスカラー倍計算部の機能ブロックを用いる。スカラー倍計算部１１５（図１の１３５）は、前計算部７０３、実計算部７０４からなる。前計算部７０３は、加算部３３１、２倍算部３３２、繰り返し判定部３３３、インデックス集合生成部７３４からなる。実計算部３０４は、加算部３４２、２倍算部３４３、繰り返し判定部３４４、スカラー値表現変換部７４５、ウィンドウ幅選択部７４６からなる。
【０１３３】
スカラー倍計算部１１５がスカラー値ｄ及び楕円曲線上の点Ｐから、楕円曲線におけるスカラー倍点ｄＰを計算する第２の計算方法を説明する。第２の計算方法では、スカラー値ｄを数値列にエンコードすることなくスカラー倍点を計算するという特徴がある。
【０１３４】
スカラー倍計算部１１５が復号化処理部１３２からスカラー値ｄと楕円曲線上の点Ｐを受け取ると、前計算部７０３は、インデックス集合Ｂを生成し、入力された楕円曲線上の点Ｐとインデックス集合Ｂを用いて前計算テーブルを作成する。前計算テーブルは
Ｐ，  ３Ｐ，  ・・・，  （２ｗ０−１−１）Ｐ及びｂｊＰ，  ｊ＝１，・・・，ｍにより構成されることは、第１の計算方法と同様である。インデックス集合Ｂが
Ｂ＝｛±ｂ１，±ｂ２，・・・，±ｂｍ｝と表され、ｍ個の相異なるｂ１，ｂ２，・・・，ｂｍは
｛２ｗ０−１＋１，２ｗ０−１＋３，・・・，２ｗ０−１｝の範囲から選ばれることも第１の計算方法と同様である。
【０１３５】
実計算部３０４は、入力されたスカラー値ｄと楕円曲線上の点Ｐから、インデックス集合と前計算テーブルを用いてスカラー倍点ｄＰを計算する。
【０１３６】
次に前計算部７０３、実計算部７０４の行なう各処理について詳細に説明する。
【０１３７】
まず、図８を用いて、前計算部７０３が楕円曲線上の点から、前計算テーブル及びインデックス集合Ｂを作成する方法を説明する。
【０１３８】
点ＰをＥＣＤＢＬにより２倍し、その結果を２Ｐに格納する（８０１）。
【０１３９】
変数ｊに初期値１を代入する（８０２）。
【０１４０】
繰り返し判定部７３３により、ｊが２ｗ０−１より小さいかどうかを判定する。ｊが２ｗ０−１より小さい場合はステップ８０４へ行く。ｊが２ｗ０−１以上の場合はステップ８１１へ行く（８０３）。
【０１４１】
ステップ８０３でｊが２ｗ０−１より小さい場合、
点ｊＰと点２ＰをＥＣＡＤＤにより加算し、その結果を（ｊ＋２）Ｐに格納する（８０４）。
【０１４２】
変数ｊを２増加させ、ステップ８０３へ戻る（８０５）。
【０１４３】
ステップ８０３でｊが２ｗ０−１以上の場合、
点（２ｗ０−１−１）Ｐと点ＰをＥＣＡＤＤにより加算し、その結果を２ｗ０−１Ｐに格納する（８１１）。
【０１４４】
インデックス集合Ｂに空集合を初期値として代入し、変数ｊに１を代入する（８１２）。
【０１４５】
繰り返し判定部７３３により、ｊがｍ以下であるかどうかを判定する。ｊがｍ以下であればステップ８１４へ行く。ｊがｍより大きい場合はステップ８２１へ行く（８１３）。
【０１４６】
ステップ８１３でｊがｍ以下の場合、
インデックス集合生成部７３４は、｛２ｗ０−１＋１，２ｗ０−１＋３，・・・，２ｗ０−１｝の範囲よりｂｊをランダムに選ぶ（８１４）。
【０１４７】
インデックス集合生成部７３４により、ｂｊがＢの要素として既に含まれているかどうかを判定する。ＢｊがＢの要素として含まれていればステップ８１４へ戻る、ｂｊがＢの要素として含まれていなければステップ８１６へ行く（８１５）。
【０１４８】
点２ｗ０−１Ｐと点（ｂｊ−２ｗ０−１）ＰをＥＣＡＤＤにより加算し、その結果をｂｊＰに格納する（８１６）。
【０１４９】
インデックス集合生成部７３４は、インデックス集合Ｂにｂｊを要素として追加する（８１７）。
【０１５０】
変数ｊを１増加させ、ステップ８１３へ戻る（８１８）。
【０１５１】
ステップ８１３でｊがｍより大きい場合、
Ｐ，  ３Ｐ，  ・・・，  （２ｗ０−１−１）Ｐ及びｂｊＰ，  ｊ＝１，・・・，ｍを前計算テーブルとして出力する。
インデックス集合Ｂを出力する（８２１）。
【０１５２】
また、点Ｐ，  ３Ｐ，  ・・・，  （２ｗ−１）Ｐのみを前計算テーブルとして格納し、
点−Ｐ，  −３Ｐ，  ・・・，  −（２ｗ−１）Ｐを前計算テーブルには格納する必要はないことは第１の計算方法と同様である。
【０１５３】
なお、点−Ｐ，  −３Ｐ，  ・・・，  −（２ｗ−１）Ｐ及び−ｂｊＰ，  ｊ＝１，・・・，ｍの導出を省くために、それらの点のｙ座標の値のみを前計算テーブルに格納しておいてもよいことも第１の計算方法と同様である。
【０１５４】
点Ｐが固定点である場合、前計算部３０３の行う前計算テーブルの作成処理のうち、
点Ｐ，  ３Ｐ，  ・・・，  （２ｗ０−１−１）Ｐの計算、すなわち、ステップ８０１からステップ８１１の処理は、ただ一度行えばよいことは第１の計算方法と同様である。
【０１５５】
前計算部７０３の行う前計算テーブルの作成処理は、
点Ｐ，  ３Ｐ，  ・・・，  （２ｗ−１）Ｐが計算されればよい。そのため、モンゴメリトリックを用いて、楕円曲線演算で必要となる逆元演算の計算の共通化を行うことにより、高速化をはかってもよいことも、第１の計算方法と同様である。
【０１５６】
次に、図９、図１０を用いて、実計算部７０４が入力されたスカラー値ｄと楕円曲線上の点Ｐから、インデックス集合Ｂと前計算テーブルを用いて楕円曲線におけるスカラー倍点を計算する方法を説明する。
【０１５７】
点Ｑに無限遠点を代入する（９０１）。
【０１５８】
スカラー値表現変換部７４５は、スカラー値ｄを１，−１により表現したｄ￣に変換する（９０２）。すなわち、ｄ￣は整数としてｄに等しく、かつ
ｄ￣＝ｄｎ−１￣２ｎ−１＋ｄｎ−２￣２ｎ−２＋・・・＋ｄ０￣，  ｄｉ￣＝１  ｏｒ  −１                      （式２９）
と表される。この変換を達成するためには、スカラー値ｄを
ｄ＝ｄｎ−１２ｎ−１＋ｄｎ−２２ｎ−２＋・・・＋ｄ０，  ｄｉ＝  ０  ｏｒ  １                  （式３０）
と表したとき、
ｄｎ−１￣＝１                                                                      （式３１）
ｄｉ￣＝１    ｉｆ  ｄｉ＋１  ＝  １  ｆｏｒ  ｉ＝０，・・・，ｎ−２                  （式３２）
ｄｉ￣＝−１  ｉｆ  ｄｉ＋１  ＝  ０  ｆｏｒ  ｉ＝０，・・・，ｎ−２                  （式３３）
により変換すると、式２９をみたす。尚、ｄ￣に変換できるのは、ｄが奇数の時のみである。
【０１５９】
変数ｉに初期値ｎを代入する（９０３）。
【０１６０】
繰り返し判定部７３３は、ｉがｗ０−１より大きいかどうかを判定する。ｉがｗ０−１よ大きい場合はステップ９１１へ行く。ｗ０−１以下であればステップ１００１へ行く（９０４）。
【０１６１】
ステップ９０４でｉがｗ０−１より大きい場合、
ウィンドウ幅選択部７４６は、変数ｘに整数ＭＳＢｗ０（ｄ￣）を格納する（９１１）。ただし、ＭＳＢｗ０（ｄ￣）はｄ￣の上位ｗ０ビットにより構成される数値を表す。
【０１６２】
ウィンドウ幅選択部７４６は、変数ｘの値がインデックス集合Ｂの要素として含まれている場合はｂに１を格納する。含まれていない場合はｂに０を格納する（９１２）。
【０１６３】
ウィンドウ幅選択部７４６は、確率Ｐｗでｐに１を格納し、確率１−Ｐｗでｐを格納する（９１３）。
【０１６４】
ウィンドウ幅選択部７４６は、変数ｕに
１−｜ＭＳＢ２（ｄ￣）／２｜を格納する（９１４）。
【０１６５】
ウィンドウ幅選択部７４６は、変数ｒに
ｗ０−１＋（（ｕ∧ｐ）∨（（１−ｕ）∧ｂ））を代入する（９１５）。
【０１６６】
変数ｊに１を代入する（９１６）。
【０１６７】
点ＱをＥＣＤＢＬにより２倍し、点Ｑに再び格納する（９１７）。
【０１６８】
繰り返し判定部７３３は、ｊがｒ以上であるかどうかを判定する。ｊがｒ以上であればステップ９２１へ行く。ｒより小さければステップ９１９へ行く（９１８）。
【０１６９】
ステップ９１８でｊがｒ以上の場合、変数ｊを１増加させ、ステップ９１７へ戻る（９１９）。
【０１７０】
ステップ９１８でｊがｒより小さい場合、点ＱとＭＳＢｒ（ｄ￣）ＰとをＥＣＡＤＤにより加算する。ただし、ＭＳＢｒ（ｄ￣）が負の場合は（−ＭＳＢｒ（ｄ￣））Ｐのｙ座標を反転したものを用いて加算を行う。その結果を点Ｑに格納する。（９２１）。
【０１７１】
変数ｉをｒ減少させ、ステップ９０４へ戻る（９２２）。
【０１７２】
ステップ９０４でｉがｗ０−１以下の場合、
繰り返し判定部７３３は、ｉが０以下であるかどうかを判定する。ｉが０以下の場合はステップ１００７へ行く。ｉが０より大きい場合はステップ１００２へ行く（１００１）。
【０１７３】
ステップ１００１でｉが０より大きい場合、
変数ｊに１を代入する（１００２）。
【０１７４】
点ＱをＥＣＤＢＬにより２倍し、点Ｑに再び格納する（１００３）。
【０１７５】
繰り返し判定部７３３は、ｊがｉ以上であるかを判定する。ｊがｉ以上であればステップ１００６へ行く。ｉより小さければステップ１００５へ行く（１００５）。
【０１７６】
ステップ１００４でｊがｉより小さい場合、
変数ｊを１増加させ、ステップ１００３へ戻る（１００５）。
【０１７７】
ステップ１００４でｊがｉ以上の場合、点Ｑとｄ￣ＰとをＥＣＡＤＤにより加算する。ただし、ｄ￣が負の場合は（−ｄ￣）Ｐのｙ座標を反転したものを用いて加算を行う。その結果を点Ｑに格納する。（１００６）。
【０１７８】
点Ｑを出力する（１００７）。
【０１７９】
実計算部７０４が行う処理により出力されるスカラー倍点はｄＰに一致する。この理由は次の通りである。
ステップ９０４からステップ９２２のループにおいて、ｋ回目のループにおけるｒの値をｒｋとおく。
ステップ９０１で楕円曲線上の点Ｑに無限遠点が代入される。
１回目のループ終了後では
Ｑ＝ｒ１Ｐ                                                                （式３４）
となる。２回目のループ終了後では
Ｑ＝（ｒ１２ｒ２＋ｒ２）Ｐ                                                  （式３５）
となる。以下同様にして、ｋ回目のループ終了後では
Ｑ＝（（・・・（ｒ１２ｒ２＋ｒ２）２ｒ３＋・・・＋ｒｋ−１）２ｒｋ＋ｒｋ）Ｐ            （式３６）
となる。ステップ１００２からステップ１００６の処理も同様であることに注意すれば、ステップ１００７における点ＱはＱ＝ｄ￣Ｐをみたすことがわかる。数値としてｄ＝ｄ￣であるため、Ｑ＝ｄＰとなる。
【０１８０】
実計算部７０４のステップ９２１の楕円加算で用いる点ＭＳＢｒ（ｄ￣）Ｐに対して、ＭＳＢｒ（ｄ￣）Ｐもしくは（−ＭＳＢｒ（ｄ￣））Ｐのいずれかが前計算テーブルに必ず存在する。この理由は次の通りである。まず、
ＭＳＢｒ（ｄ￣）  ｍｏｄ  ２  ＝  １であり、ＭＳＢｒ（ｄ￣）は奇数である。ステップ９１５で変数ｒにｗ０−１，  ｗ０のいずれかの値が代入される。ｒ＝ｗ０−１の場合、前計算テーブルは
Ｐ，３Ｐ，・・・，（２ｗ０−１−１）Ｐを含むので、ＭＳＢｒ（ｄ￣）Ｐもしくは（−ＭＳＢｒ（ｄ￣））Ｐのいずれかが前計算テーブルに必ず存在する。次にｒ＝ｗ０の場合を考える。ｒ＝ｗ０となるためには、（ｕ∧ｐ）＝１であるか、もしくは
（（１−ｕ）∧ｂ）＝１である必要がある。（ｕ∧ｐ）＝１の時、ｕ＝１であるので、ｄ￣の最上位ビットの符号と上位２番目のビットの符号は異なる。そのため
−２ｗ０−１≦ＭＳＢｗ０（ｄ￣）≦２ｗ０−１                            （式３７）
となり、ＭＳＢｒ（ｄ￣）Ｐもしくは（−ＭＳＢｒ（ｄ￣））Ｐのいずれかが前計算テーブルに存在する。
（（１−ｕ）∧ｂ）＝１の時、ｂ＝１であるので、ＭＳＢｗ０（ｄ￣）はインデックス集合Ｂの要素である。そのため、ＭＳＢｒ（ｄ￣）Ｐもしくは（−ＭＳＢｒ（ｄ￣））Ｐのいずれかが前計算テーブルに存在する。結果として、いずれの場合も、ＭＳＢｒ（ｄ￣）Ｐもしくは（−ＭＳＢｒ（ｄ￣））Ｐのいずれかが前計算テーブルに必ず存在する。
【０１８１】
なお、ｄをｄ￣に変換するためには、スカラー値ｄが奇数である必要がある。そのためには、入力されたスカラー値ｄが偶数の時は、ｄ＋１を改めてスカラー値ｄ’としてエンコードする。すなわち、ｄを奇数に変換する。そして、スカラー倍点ｄ’Ｐを計算する。
ｄ’Ｐ＝（ｄ＋１）Ｐ＝ｄＰ＋Ｐ            （式３８）
であるので、ｄ’Ｐから点Ｐを引き、その値をスカラー倍点ｄＰとして出力すればよい。
【０１８２】
また、入力されたｄが奇数の時は、ｄ＋２を改めてスカラー値ｄ’としてエンコードし、
ｄ’Ｐ＝（ｄ＋２）Ｐ＝ｄＰ＋２Ｐ            （式３９）
を利用して、スカラー倍点ｄＰを求めてもよい。この場合、ｄが奇数の場合も偶数の場合も、行う処理が一致するという利点がある。
【０１８３】
上記スカラー倍におけるメモリ使用量は、前計算部７０３の前計算テーブルの大きさにより定まる。上記スカラー倍計算方法では、前計算テーブルは
Ｐ，３Ｐ，・・・，（２ｗ０−１−１）Ｐ及びｂｊＰ，  ｊ＝１，・・・，ｍ  により構成され、格納する点の個数は（２ｗ０−２＋ｍ）個である。正整数ｗ０を固定し、ウィンドウ幅ｗを動かした場合、整数ｍは０から２ｗ０−２までの値を取り得る。そのため、ウィンドウ幅ｗを適切に選択することにより、格納する点の個数は任意の値にできる。一方、非特許文献２が開示する従来の方法では、前計算テーブルに格納する点の個数は１，２，４，８，・・・  と２ベキの値しか選択できない。そのため、上記スカラー倍計算方法は、非特許文献２の方法と比べて、前計算テーブルに格納する点の個数の選択範囲が広く、高速処理性能やメモリ容量を考慮してカスタマイズすることができる。
【０１８４】
また、上記スカラー倍方法は、サイドチャネル攻撃に対する防御法に関しても有効である。この理由は次の通りである。
【０１８５】
実計算部７０４がスカラー倍点を計算する際に、ステップ９０４−９２１の繰り返し処理において実行される楕円曲線演算は、一回のループにつき  ｜Ｄ・・・ＤＡ｜  となる。すなわちｗ０回もしくはｗ０−１回のＤの後にＡとなる。ただし、ＤはＥＣＤＢＬを、ＡはＥＣＡＤＤをそれぞれ表す。一方ｒは、確率Ｐｗでｗ０となり、確率１−Ｐｗでｗ０＋１となる。
【０１８６】
この理由について、まずｕ＝１の場合について考察する。変数ｐは、ステップ９１３において確率Ｐｗでｐ＝１、確率１−Ｐｗでｐ＝０が割り当てられる。そのため、確率Ｐｗでｒ＝ｗ０、確率１−Ｐｗでｒ＝ｗ０−１となる。
【０１８７】
次にｕ＝０の場合について考察する。変数ｂは、ステップにおいてｘがＢの要素であるときｂ＝１、ｘがＢの要素でないときｂ＝０が割り当てられる。
｜ｘ｜≧２ｗ０−１の場合、ｘ∈Ｂとなる確率は、
（Ｂの要素数）／（２ｗ０−１≦｜ｋ｜＜２ｗ０をみたす奇数ｋの個数）＝ｗ１であるので、Ｐｗとなる。
変数ｕは、ステップ９１４で
ｕ＝１−｜ＭＳＢ２（ｄ￣）／２｜が割り当てられる。すなわち、ｕ＝０は｜ｘ｜≧２ｗ０−１と同値である。そのため、ｕ＝０の場合、確率Ｐｗでｒ＝ｗ０、確率１−Ｐｗでｒ＝ｗ０−１となる。
【０１８８】
したがって、いずれの場合においても、ｒは、確率Ｐｗでｗ０となり、確率１−Ｐｗでｗ０−１となる。確率Ｐｗは公開情報であるｗ１にのみ依存し、秘密情報には依存していない。結果として、全てのスカラー値に対して、実行する楕円曲線演算は
｜Ｄ・・・ＤＡ｜Ｄ・・・ＤＡ｜・・・｜Ｄ・・・ＤＡ｜    （式４０）
となり、Ｄの連続する回数は各々ｗ０もしくはｗ０−１であるが、どちらの値が選択されるかは公開情報ｗ１にのみ依存し、秘密情報には依存しない。特に、式３５のみからは、スカラー値ｄに関する情報を引き出すことができない。
【０１８９】
なお、第２の計算方法でも、第１の計算方法と同様に、非特許文献１のランダム化射影座標を併用してスカラー倍計算を行ってもよい。そうすると、同じ点Ｐを入力しても実行毎に異なる値に変換してスカラー倍計算を行うので、攻撃者が中間値の値を予測できなくなる。
【０１９０】
また、第１の計算方法と同様に、前計算テーブルに格納されている点が読み出されるたびに、再びランダム化して、前計算テーブルに書き込んでもよい。そうすると、同じデータの再使用がなくなるため、より一層、サイドチャネル攻撃への耐性が増す。
【０１９１】
以上の通り、第２の計算方法は、サイドチャネル攻撃に有用な情報を与えないので、サイドチャネル攻撃に対して耐性がある。また、前計算テーブルに格納する点の個数の選択範囲が広いため、処理速度やメモリ使用量をカスタマイズすることができる。
【０１９２】
なお、第２の計算方法では楕円曲線としてワイエルシュトラス型楕円曲線を用いたが、標数２の有限体上で定義された楕円曲線や、ＯＥＦ（Ｏｐｔｉｍａｌ  Ｅｘｔｅｎｓｉｏｎ  Ｆｉｅｌｄ）上で定義された楕円曲線、もしくはモンゴメリ型楕円曲線を用いてもよい。ＯＥＦについては非特許文献５に記載されている。
【０１９３】
以上、コンピュータＢ１２１が、暗号化されたデータ１４１を復号化する場合のスカラー倍計算部１３５の動作を説明したが、コンピュータＡ１０１が入力メッセージを暗号化する場合も同様である。
【０１９４】
その場合には、コンピュータＡ１０１のスカラー倍計算部１１５は、既に説明した楕円曲線上の点Ｑ、乱数ｋによるスカラー倍点ｋＱと、公開鍵ａＱと乱数ｋによるスカラー倍点ｋ（ａＱ）を出力する。このとき、上記計算方法で説明したスカラー値ｄを乱数ｋ、楕円曲線上の点Ｐを楕円曲線上の点Ｑ、公開鍵ａＱとして同様の処理を行うことにより、それぞれのスカラー倍点を求めることができる。
【０１９５】
次に本発明を署名検証システムに適用する実施形態を、図１１と図２を用いて説明する。
【０１９６】
図１１の署名検証システムは、スマートカード１１０１と署名検証処理を行うコンピュータ１１２１とから成る。
【０１９７】
スマートカード１１０１は、図１のコンピュータＡ１０１と類似の構成を備え、ＣＰＵ１１３やコプロセッサ１１４などの演算装置とが記憶部１０２に格納されているプログラムを実行することにより、データ処理部１１２ではなく、署名生成処理部１１１２を実現する。ただし、図１に示す外部記憶装置１０７、ディスプレイ１０８、キーボード１０９を備えなくてもよい。
【０１９８】
コンピュータ１１２１は、コンピュータＡ１０１と同様の構成を備え、ＣＰＵ１１３がプログラムを実行することによりデータ処理部１１２ではなく、署名検証処理部１１３２を実現する。
【０１９９】
スカラー倍計算部１１１５と１１３５は、図１に示すスカラー倍計算部１１５または１３５と同様の機能を備える。
【０２００】
なお、本実施例において、コンピュータ１１２１内の各プログラムは、あらかじめ、上記コンピュータ内の記憶部に格納されていても良いし、必要なときに、コンピュータ１１２１が利用可能な媒体を介して他の装置から上記記憶部に導入されてもよい。
【０２０１】
さらに、スマートカード１１０１内の各プログラムは、あらかじめ、上記スマートカード１１０１内の記憶部に格納されていても良いし、必要なときに、入出力インタフェースを介して接続するコンピュータ、または当該コンピュータが利用可能な媒体を介して上記記憶部に導入されてもよい。
【０２０２】
媒体とは、たとえば当該コンピュータに着脱可能な記憶媒体、または通信媒体（すなわちネットワークまたはネットワークを伝搬する搬送波）を指す。
【０２０３】
図１１の署名検証システムにおける署名作成と署名検証動作を、図２を参照して説明する。
【０２０４】
コンピュータ１１２１は、ランダムに選んだ数値をチャレンジコード１１４３として、インタフェース１１４２を介してスマートカード１１０１に転送する。
【０２０５】
署名生成処理部１１１２（図２の１１２）は、チャレンジコード１１４３を受け付け、チャレンジコード１１４３のハッシュ値をとり、所定のビット長の数値ｆに変換する。
【０２０６】
署名生成処理部１１１２は、乱数ｕを生成し、記憶部１１０２（図２の１０２）に格納されている定数１１０４から読み出した（図２の２０５）楕円曲線上の定点Ｑとともにスカラー倍計算部１１１５（図２の１１５）へ送る（図２の２０６）。
【０２０７】
スカラー倍計算部１１１５は、定点Ｑ、乱数ｕによるスカラー倍点（ｘｕ，ｙｕ）を計算し、計算されたスカラー倍点を署名生成処理部１１１２へ送る（図２の２０７）。
【０２０８】
署名生成処理部１１１２は、送られたスカラー倍点を用いて署名の生成を行う。例えば、ＥＣＤＳＡ署名であれば、
ｓ  ＝  ｘｕ  ｍｏｄ  ｑ                （式４１）
ｔ  ＝  ｕ−１（ｆ＋ｄｓ）  ｍｏｄ  ｑ        （式４２）
を計算することによりチャレンジコード１１４３に対応する署名（ｓ，ｔ）を得る（図２の２０８）。
【０２０９】
ここで、ｑは定点Ｑの位数、すなわち定点Ｑのｑ倍点ｑＱが無限遠点になり、ｑより小さな数値ｍに対する定点Ｑのｍ倍点ｍＱは無限遠点にはならない、というような数値のことである。
【０２１０】
ＥＣＤＳＡ署名については、例えば、
非特許文献６：ＡＮＳＩ  Ｘ９．６２  Ｐｕｂｌｉｃ  Ｋｅｙ  Ｃｒｙｐｔｏｇｒａｐｈｙ  ｆｏｒ  ｔｈｅ  Ｆｉｎａｎｃｉａｌ  Ｓｅｒｖｉｃｅｓ  Ｉｎｄｕｓｔｒｙ，  Ｔｈｅ  Ｅｌｌｉｐｔｉｃ  Ｃｕｒｖｅ  Ｄｉｇｉｔａｌ  Ｓｉｇｎａｔｕｒｅ  Ａｌｇｏｒｉｔｈｍ  （ＥＣＤＳＡ），  （１９９８）
に記載されている。
【０２１１】
スマートカード１１０１は、署名生成処理部１１１２で作成した署名１１４１を入出力インタフェース１１１０より出力し、インタフェース１１４２を介してコンピュータ１１２１へ転送する。
【０２１２】
コンピュータ１１２１の署名検証処理部１１３２（図２の１１２）は、署名１１４１が入力される（図２の２０４）と、署名１１４１の数値ｓ，ｔが適切な範囲内すなわち１≦ｓ，  ｔ＜ｑであるかを調べる。
【０２１３】
数値ｓ，  ｔが上記範囲内になければチャレンジコード１１４３に対する署名の検証結果として「無効」を出力し、スマートカード１１０１を拒絶する。数値ｓ，  ｔが上記範囲内にあれば、署名検証処理部１１３２は、
ｈ    ＝  ｔ−１  ｍｏｄ  ｑ                （式４３）
ｈ１  ＝  ｆｈ  ｍｏｄ  ｑ                （式４４）
ｈ２  ＝  ｓｈ  ｍｏｄ  ｑ                （式４５）
を計算する。そして、記憶部１１２２（図２の１０２）に格納されている定数１１２４から読み出した（図２の２０５）公開鍵ａＱ及び定点Ｑと計算したｈ１，ｈ２をスカラー倍計算部１１３５（図２の１１５）へ送る（図２の２０６）。
【０２１４】
スカラー倍計算部１１３５は、定点Ｑとｈ１によるスカラー倍点ｈ１Ｑと、公開鍵ａＱとｈ２によるスカラー倍点ｈ２ａＱとを計算し、計算されたスカラー倍点を署名検証処理部１１３２へ送る（図２の２０７）。
【０２１５】
署名検証処理部１１３２は、送られたスカラー倍点を用いて、署名検証処理を行う。例えば、ＥＣＤＳＡの署名検証であれば、点Ｒ
Ｒ＝ｈ１Ｑ＋ｈ２ａＱ                （式４６）
を計算し、そのｘ座標をｘＲとしたとき、
ｓ’  ＝  ｘＲ  ｍｏｄ  ｑ                （式４７）
を計算し、ｓ’＝ｓであればチャレンジコード１１４３に対する署名の検証結果として「有効」を出力し、スマートカード１１０１を認証し、受け入れる（図２の２０８）。
【０２１６】
ｓ’＝ｓでなければ「無効」を出力し、スマートカードを拒絶する（図２の２０８）。
【０２１７】
上記実施形態のスカラー倍計算部１１１５、１１３５は、図１のスカラー倍計算部１１５または１３５と同様の機能を備えるので、サイドチャネル攻撃を防ぐことができる、かつ処理速度やメモリ使用量をカスタマイズすることができるスカラー倍計算を実行できる。
【０２１８】
そのためスマートカード１１０１は署名作成処理を行う際に、コンピュータ１１２１は署名検証処理を行う際に、サイドチャネル攻撃を防ぐことができる、そのうえ処理速度やメモリ使用量をカスタマイズすることができる。
【０２１９】
次に本発明を鍵交換システムに適用する実施形態を説明する。本実施形態においては、図１のシステム構成が応用できる。
【０２２０】
図１のデータ処理部１１２、１３２は、本実施形態においては、それぞれ鍵交換処理部１１２、１３２として機能する。
【０２２１】
鍵交換システムのコンピュータＡ１０１が、入力されたデータ１４３から共有情報の導出を行う場合の動作について図１、図２を参照して説明する。
【０２２２】
コンピュータＢ１２１のデータ処理部１３２（図２の１１２）は、記憶部１２２（図２の１０２）の定数１２５から秘密鍵ｂを読み出しコンピュータＢ１２１の公開鍵ｂＱを計算する。そして、ネットワーク１４２を介して、公開鍵ｂＱをデータ１４３としてコンピュータＡ１０１に転送する。
【０２２３】
コンピュータＡ１０１の鍵交換処理部１１２（図２の１１２）はコンピュータＢ１２１の公開鍵ｂＱの入力を受け付ける（図２の２０４）と、鍵交換処理部１１２は、記憶部１０２から読み出した（図２の２０５）秘密情報１０５であるコンピュータＡ１０１の秘密鍵ａと、コンピュータＢ１２１の公開鍵ｂＱとをスカラー倍計算部１１５へ送る（図２の２０６）。
【０２２４】
スカラー倍計算部１１５は、秘密鍵ａと、公開鍵ｂＱによるスカラー倍点ａｂＱを計算し、計算されたスカラー倍点を鍵交換処理部１１２へ送る（図２の２０７）。
【０２２５】
鍵交換処理部１１２は、送られたスカラー倍点を用いて共有情報の導出を行い、記憶部１０２に秘密情報１０５として格納する。例えば、スカラー倍点ａｂＱのｘ座標を、共有情報とする。
【０２２６】
次に、コンピュータ１２１が、入力されたデータ１４１から共有情報の導出を行う場合の動作について説明する。
【０２２７】
コンピュータＡ１０１のデータ処理部１１２は、記憶部１０２の定数１０５から秘密鍵ａを読み出しコンピュータＡ１０１の公開鍵ａＱを計算する。そして、ネットワーク１４２を介して、公開鍵ａＱをデータ１４１としてコンピュータＢ１２１に転送する。
【０２２８】
コンピュータＢ１２１の鍵交換処理部１３２（図２の１１２）はコンピュータＡ１０１の公開鍵ａＱの入力を受け付ける（図２の２０４）と、鍵交換処理部１３２は、記憶部１２２（図２の１０２）の定数１２５から読み出した（図２の２０５）  秘密情報１２５であるコンピュータＢ１２１の秘密鍵ｂと、コンピュータＡ１０１の公開鍵ａＱとをスカラー倍計算部１３５（図２の１１５）へ送る（図２の２０６）。
【０２２９】
スカラー倍計算部１３５は、秘密鍵ｂと、公開鍵ａＱによるスカラー倍点ｂａＱを計算し、計算されたスカラー倍点を鍵交換処理部１３２へ送る（図２の２０７）。
【０２３０】
鍵交換処理部１３２は、送られたスカラー倍点を用いて共有情報の導出を行い、記憶部１２２に秘密情報１２５として格納する。例えば、スカラー倍点ｂａＱのｘ座標を、共有情報とする。
【０２３１】
ここで、数ａｂと数ｂａは数値として同じなので、点ａｂＱと点ｂａＱは同じ点となり、同じ情報が導出されたことになる。
【０２３２】
ネットワーク１４２には、点ａＱと点ｂＱが送信されるが、点ａｂＱ（もしくは点ｂａＱ）を計算するには秘密鍵ａもしくは秘密鍵ｂを用いなければならない。すなわち、秘密鍵ａもしくは秘密鍵ｂを知らなければ、共有情報を得ることができない。このようにして得られた共有情報は、共通鍵暗号の秘密鍵として利用できる。
【０２３３】
本実施形態においても、スカラー倍計算部１１５、１３５は、上述の特徴を備えるので、サイドチャネル攻撃を防ぐことができる、そのうえ処理速度やメモリ使用量をカスタマイズすることができるような鍵交換処理が可能になる。
【０２３４】
また、上記各実施形態における暗号化処理部、復号化処理部、署名作成部、署名検証部、鍵交換処理部は、専用のハードウェアを用いて行ってもよい。また、スカラー倍計算部をコプロセッサまたはそれ以外の専用ハードウェアで実現しても良い。
【０２３５】
また、データ処理部は、上記暗号化処理、復号化処理、署名作成処理、署名検証処理、鍵交換処理のうち、任意の一つ以上の処理を行えるように構成してもよい。
【０２３６】
【発明の効果】
本発明によれば、サイドチャネル攻撃に対して安全で、かつ処理速度やメモリ使用量をカスタマイズすることができる、楕円曲線演算を用いたメッセージ処理が可能になる。
【図面の簡単な説明】
【図１】実施形態におけるシステム構成図である。
【図２】各実施形態における情報の受け渡しを示すシーケンス図である。
【図３】第１実施例の実施形態におけるスカラー倍計算部の構成図である。
【図４】第１実施例におけるエンコード部の行うエンコード方法を示すフローチャート図である。
【図５】第１実施例における前計算部の行う前計算方法を示すフローチャート図である。
【図６】第１実施例における実計算部の行う実計算方法を示すフローチャート図である。
【図７】第２実施例の実施形態におけるスカラー倍計算部の構成図である。
【図８】第２実施例における前計算部の行う前計算方法を示すフローチャート図である。
【図９】第２実施例における実計算部の行う実計算方法を示すフローチャート図である。
【図１０】第２実施例における実計算部の行う実計算方法を示すフローチャート図である。
【図１１】実施形態における署名検証システム構成図である。
【符号の説明】
１０１、１２１、１１２１：コンピュータ、１１０１：スマートカード、１０２、１２２、１１０２、１１２２：記憶部、１１１、１３１、１１１１、１１３１：処理部、１１５、１３５、１１１５、１１３５：スカラー倍計算部、１１２、１３２：データ処理部、１１１２：署名生成処理部、１１３２：署名検証処理部、１０４、１２４、１１０４、１１２４：定数、１０５、１２５、１１０５、１１２５：秘密情報、１１０、１３０、１１１０、１１３０：入出力インタフェース、１０８、１２８、１１２８：ディスプレイ、１０９、１２９、１１２９：キーボード、１４２：ネットワーク、１１４２：インタフェース、１４１、１４３：データ、３０２：エンコード部、３０３：前計算部、３０４：実計算部、３２１：剰余取得部、３２２：インデックス集合生成部、３２３：剰余選択部、３２４：繰り返し判定部、３２５：格納部、３３１：加算部、３３２：２倍算部、３３３：繰り返し判定部、３４１：ビット値判定部、３４２：加算部、３４３：２倍算部、３４４：繰り返し判定部、７０３：前計算部、７０４：実計算部、７３１：加算部、７３２：２倍算部、７３３：繰り返し判定部、７３４：インデックス集合生成部、７４２：加算部、７４３：２倍算部、７４４：繰り返し判定部、７４５：スカラー値表現変換部、７４６：ウィンドウ幅選択部。
【図１】
2005055488.tif 000003
【図２】
2005055488.tif 000004
【図３】
2005055488.tif 000005
【図４】
2005055488.tif 000006
【図５】
2005055488.tif 000007
【図６】
2005055488.tif 000008
【図７】
2005055488.tif 000009
【図８】
2005055488.tif 000010
【図９】
2005055488.tif 000011
【図１０】
2005055488.tif 000012
【図１１】
2005055488.tif 000013