(57)【要約】【課題】楕円曲線多重スカラー倍計算方法において、与えられたメモリ量に応じて最適な処理を行う楕円曲線多重スカラー倍計算方法を提供する。  【解決手段】楕円曲線において、複数のスカラー値、及び、スカラー値の個数と同数の楕円曲線上の点から多重スカラー倍点を計算する楕円曲線暗号における多重スカラー倍計算装置において、スカラー値を第一の数値列にエンコードし、前記第一の数値列に対し、０となる項数を増加させることによって、高速演算可能な多重スカラー倍計算を可能とする。  【選択図】図１
2006309201.tif 000002
【特許請求の範囲】
【請求項１】
楕円曲線において、複数のスカラー値、及び、前記複数のスカラー値の個数と同数の前記楕円曲線上の点から多重スカラー倍点を計算する多重スカラー倍計算装置であって、
前記複数のスカラー値を各々、数値列にエンコードするエンコード部と、
前記楕円曲線上の点から事前計算テーブルを作成する前計算部と、
前記エンコードした各数値列、及び、前記事前計算テーブルから多重スカラー倍点を計算する実計算部と、
を具備し、
前記エンコード部は、
一つの前記スカラー値を第一の数値列にエンコードする第一のエンコード処理と、
前記第一の数値列から前記第一の各数値列とは異なる第二の各数値列にエンコードする第二のエンコード処理と、を実行し、
前記第一のエンコード処理は、数値計算部が前記各スカラー値のバイナリ表現に対し、連続する２ビットに対する減算を行うステップを含み、
前記第二のエンコード処理は、
数値変換部が複数の予め定められた桁数から、予め定められた順序で、前記桁数を一つ選択するステップと、
拡張可否判定部が前記第一の各数値列に対し、連続する前記選択した桁数だけ桁を見て、０に変換可能な桁の総数を判定するステップと、
前記０に変換可能な桁の総数が予め定められた値以上の場合は、数値計算部が前記連続する桁を変換するステップと、
前記０に変換可能な桁の総数が予め定められた値以下の場合は、前記桁数を一つ選択するステップへ行くステップと、
前記桁数を一つ選択するステップ、前記０に変換可能な桁の総数を判定するステップ、前記連続する桁を変換するステップ、前記桁数を一つ選択するステップへ行くステップを繰り返すステップと、を実行する
ことを特徴とする多重スカラー倍計算装置。
【請求項２】
請求項１に記載の多重スカラー倍計算装置であって、
前記第二のエンコード処理は、
数値変換部、及び、拡張可否判定部が前記第一の数値列に対し、連続する第一の桁数に対して０に変換可能な項を判定する第一のステップと、
数値変換部、及び、拡張可否判定部が前記連続する第一の桁数と異なる連続する第二のビット数に対して０に変換可能な項を判定する第二のステップと、
拡張可否判定部が前記第一のステップにおける０に変換可能な項の総数と前記第二のステップにおける０に変換可能な項の総数とを比較する第三のステップと、
前記第三のステップにおいて、前記第二のステップにおける０に変換可能な項の総数が予め定められた値以上の場合は、数値計算部が前記第二のステップを用いて前記第一の数値列を変換する第四のステップと、
前記第三のステップにおいて、前記第二のステップにおける０に変換可能な項の総数が予め定められた値より小さい場合は、数値計算部が前記第一のステップを用いて前記第一の数値列を変換する第四のステップと、
繰り返し判定部が前記第一のステップ、前記第二のステップ、前記第三のステップ、前記第四のステップを繰り返す第五のステップと、からなる
ことを特徴とする多重スカラー倍計算装置。
【請求項３】
請求項１に記載の多重スカラー倍計算装置であって、
前記多重スカラー倍計算装置は、
多重スカラー倍計算に必要なメモリ使用量を判定するメモリ使用量判定部と、
あらかじめ決められた複数の異なる多重スカラー倍計算方法について前記メモリ使用量判定部が判定するメモリ使用量から、最適な多重スカラー倍計算方法を選択する多重スカラー倍計算方法選択部と、
前記選択された多重スカラー倍計算方法を用いて多重スカラー倍計算を実行する多重スカラー倍計算実行部と、を具備する
ことを特徴とする多重スカラー倍計算装置。
【請求項４】
データと署名データとから署名検証検証結果を出力する署名検証部と、前記署名検証結果を作成するために必要な多重スカラー倍点を計算する多重スカラー倍計算部と、を有する署名検証装置であって、
前記多重スカラー倍計算部は、請求項１に記載のスカラー倍計算装置を用いて、前記多重スカラー倍点を計算するステップを実行する
ことを特徴とする署名検証装置。
【請求項５】
データからディジタル署名データを生成する署名生成装置であって、
請求項１に記載の多重スカラー倍計算装置を用いてスカラー倍点を計算するステップを有する署名生成処理を行う
ことを特徴とする署名生成装置。
【請求項６】
データから暗号化データを生成する暗号化装置であって、
請求項１に記載の多重スカラー倍計算装置を用いてスカラー倍点を計算するステップを有する暗号化処理を行う
ことを特徴とする暗号化装置。
【請求項７】
暗号化データから復号化データを生成する復号化装置であって、
請求項１に記載の多重スカラー倍計算装置を用いてスカラー倍点を計算するステップを有する復号化処理を行う
ことを特徴とする復号化装置。
【請求項８】
第一のデータから第一のデータとは異なる第二のデータを生成するデータ生成装置であって、
請求項１に記載の多重スカラー倍計算装置を用いてスカラー倍点を計算するステップを有するデータ生成処理を行う
ことを特徴とするデータ生成装置。
【請求項９】
楕円曲線において、入力された複数のスカラー値及び入力された前記複数のスカラー値の個数と同数の前記楕円曲線上の複数の点を用いて多重スカラー倍点を計算して出力する多重スカラー倍計算装置であって、
前記入力された複数のスカラー値を受け付ける受付部と、
前記入力された前記楕円曲線上の複数の点を記憶する記憶部と、
前記受け付けた複数のスカラー値を各々、数値列にエンコードするエンコード部と、
前記記憶されている楕円曲線上の各点を用いて事前計算テーブルを作成する前計算部と、
前記エンコードした各数値列、及び、前記事前計算テーブルを用いて多重スカラー倍点を計算して出力する実計算部と、
を具備し、
前記エンコード部は、
前記複数のスカラー値をそれぞれ複数の第一の数値列にエンコードする第一エンコード処理部と、
前記複数の第一の数値列をそれぞれ前記複数の第一の数値列とは異なる複数の第二の数値列にエンコードして前記第二の数値列を前記数値列とする第二エンコード処理部と、を備え、
前記第一エンコード処理部は、前記複数のスカラー値それぞれのバイナリ表現を２倍したものから前記バイナリ表現を減算することにより前記複数の第一の数値列を得、
前記第二エンコード処理部は、
前記複数の第一の数値列のいずれかの端から順に、予め定められた条件を満足する、変換する桁数（変換桁数）と変換を開始する桁（変換開始桁）とを決定する変換判定部と、
前記変換判定部が決定した変換開始桁から前記変換桁数分、前記複数の第一の数値列を前記複数の第二の数値列にエンコードし、先にエンコードされている前記複数の第二の数値列に追加して前記複数の第二の数値列とする数値変換部と、を備えること
を特徴とする多重スカラー倍計算装置。
【請求項１０】
請求項９記載の多重スカラー倍計算装置であって、
前記変換判定部は、変換桁数とすべき桁数を１桁から2桁ずつ増加させ、前記複数の第一の数値列を前記変換開始桁から当該変換桁数とすべき桁数分それぞれ前記複数の第二の数値列にエンコードした際、それぞれの同じ桁位置の数値が０にエンコードされる桁の数が前記変換桁数とすべき桁数の半分以上となったとき、当該桁数を変換桁数と決定するとともに、前記変換開始桁から決定した桁数目の次の桁を変換開始桁と決定すること
を特徴とする多重スカラー倍計算装置。
【請求項１１】
請求項９記載の多重スカラー倍計算装置であって、
前記変換判定部は、変換桁数とすべき桁数を２桁から２桁ずつ増加させ、前記変換桁数とすべき桁数を２つの奇数桁の組に分割し、前記複数の第一の数値列それぞれを前記変換開始桁から当該２つの奇数桁分別々に前記複数の第二の数値列にエンコードした際、前記複数の第二の数値列それぞれの同じ桁位置の数値が０にエンコードされる桁の数が前記２つの奇数桁両方についてそれぞれの奇数桁の半分以上となったとき、当該変換すべき桁数を変換桁数と決定するとともに、前記変換開始桁から決定した桁数目の次の桁を変換開始桁と決定すること
を特徴とする多重スカラー倍計算装置。
【請求項１２】
請求項９記載の多重スカラー倍計算装置であって、
前記変換判定部は、
前記複数の第二の数値列それぞれの同じ桁位置の数値が０となる桁（以後、０の項と呼ぶ。）を生成可能な桁位置を計算する数値計算部と、
前記数値計算部での計算結果に基づいて前記変換桁数を増加させるべきか否かを判別し、前記変換桁数を決定する拡張可否判定部と、を備え、
前記数値変換部は、前記エンコード後、前記変換開始桁から前記決定した変換桁数目の次の桁を変換開始桁とすること
を特徴とする多重スカラー倍計算装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はセキュリティ技術に関し、特に、楕円曲線演算を用いたメッセージ認証の技術に関する。
【背景技術】
【０００２】
情報通信ネットワークの進展と共に電子情報に対する秘匿や認証の為に暗号技術は不可欠な要素となってきている。暗号技術に課せられる要件としては、安全性以外にも、処理速度や少ないメモリ使用量などがあるが、一般的に安全性、処理速度、メモリ使用量の間にはトレードオフの関係があり、全ての要件をみたすことは難しい。
【０００３】
暗号技術には，共通鍵暗号と公開鍵暗号があるが、公開鍵暗号の一種にＮ．  Ｋｏｂｌｉｔｚ，  Ｖ．  Ｓ．  Ｍｉｌｌｅｒにより提案された楕円曲線暗号がある。
【０００４】
楕円曲線暗号は、楕円曲線上の離散対数問題が非常に困難である為に、素因数分解の困難性を安全性の根拠にしている暗号と比べて、楕円曲線暗号は鍵長を比較的短くすることができる。
【０００５】
公開鍵暗号には、公開鍵（Ｐｕｂｌｉｃ  Ｋｅｙ）と呼ばれる一般に公開してよい情報と、秘密鍵（Ｐｒｉｖａｔｅ  Ｋｅｙ）と呼ばれる秘匿しなければならない秘密情報がある。平文メッセージの暗号化や署名の検証には公開鍵を用い、暗号文メッセージの復号化や署名の生成には秘密鍵を用いる。
【０００６】
楕円曲線暗号における秘密鍵は、後述するスカラー値が担っている。また、楕円曲線暗号の安全性は楕円曲線上の離散対数問題の求解が困難であることに由来している。楕円曲線上の離散対数問題とは、楕円曲線上のある点Ｐとそのスカラー倍の点ｄＰが与えられた時、スカラー値ｄを求める問題である。楕円曲線上の点とは、楕円曲線の定義方程式をみたす数の組をいい、楕円曲線上の点全体には、無限遠点という仮想的な点を単位元とした演算、すなわち楕円曲線上の加法（または加算）が定義される。
【０００７】
ある点に対し、特定の回数だけ加法を行うことをスカラー倍といい、その結果をスカラー倍点、その回数のことをスカラー値という。また、楕円曲線上の点Ｐ１，Ｐ２，・・・，Ｐｋと整数ａ１，ａ２，・・・，ａｋに対し、
点ａ１Ｐ１＋ａ２Ｐ２＋・・・＋ａｋＰｋの計算を行うことを多重スカラー倍算といい、その結果を多重スカラー倍点という。
【０００８】
そして、同じ点同士による楕円曲線上の加法のことを、特に楕円曲線上の２倍算という。楕円曲線上の２点の加法は次のようにして計算される。２点を通る直線を引くとその直線は楕円曲線と他の点において交わる。その交わった点とｘ軸に関して対称な点を、加法を行った結果の点とする。例えば、ワイエルシュトラス型楕円曲線の場合には、点（ｘ１，ｙ１）と点（ｘ２，ｙ２）の加算（ｘ３，ｙ３）＝（ｘ１，ｙ１）＋（ｘ２，ｙ２）は
ｘ３＝（（ｙ２−ｙ１）／（ｘ２−ｘ１））２−ｘ１−ｘ２                （式１）
ｙ３＝（（ｙ２−ｙ１）／（ｘ２−ｘ１））（ｘ１−ｘ３）−ｙ１          （式２）
を計算することにより得られる。
【０００９】
ここで、ワイエルシュトラス型楕円曲線の定義方程式は
ｙ２＝ｘ３＋Ａｘ＋Ｂ                    （式３）
で与えられる。すなわち、式３のｘ，ｙに各々ｘｉ，ｙｉ（ｉ＝１，２，３）を代入した場合に、式３の等式が成り立つ。
【００１０】
楕円曲線上の点の２倍算は次のようにして計算される。楕円曲線上の点における接線をひくと、その接線は楕円曲線上の他の一点において交わる。その交わった点とｘ座標に関して対称な点を、２倍算を行った結果の点とする。例えば、ワイエルシュトラス型楕円曲線の場合には、点（ｘ１，ｙ１）の２倍算を行った結果
（ｘ３，ｙ３）＝２（ｘ１，ｙ１）＝（ｘ１，ｙ１）＋（ｘ１，ｙ１）は、
ｘ３＝（（３ｘ１２＋Ａ）／（２ｙ１））２２ｘ１                （式４）
ｙ３＝（（３ｘ１２＋Ａ）／（２ｙ１））（ｘ１−ｘ３）−ｙ１      （式５）
を計算することにより得られる。
【００１１】
楕円曲線暗号においては、鍵交換、与えられたメッセージの暗号化、復号化、署名の生成、検証は、楕円曲線演算を用いて行う必要がある。特に、楕円曲線暗号において最も処理に時間がかかる署名検証において、楕円曲線上の多重スカラー倍の計算が用いられる。
【００１２】
楕円曲線多重スカラー倍計算方法が非特許文献１、及び、非特許文献２に、楕円曲線スカラー倍計算方法が非特許文献３に、それぞれ記載されている。
【００１３】
【非特許文献１】Ｊ．Ａ．Ｓｏｌｉｎａｓ，”Ｌｏｗ−ｗｅｉｇｈｔ  ｂｉｎａｒｙ  ｒｅｐｒｅｓｅｎｔａｔｉｏｎｓ  ｆｏｒ  ｐａｉｒｓ  ｏｆ  ｉｎｔｅｇｅｒｓ，”Ｔｅｃｈｎｉｃａｌ  Ｒｅｐｏｒｔ  ｏｆ  ＣＡＣＲ，  ＣＯＲＲ  ２００１−４１，  Ｕｎｉｖｅｒｓｉｔｙ  ｏｆ  Ｗａｔｅｒｌｏｏ，  ２００１．［平成１８年２月２４日検索］インターネット＜ＵＲＬ；ｈｔｔｐ：／／ｗｗｗ．ｃａｃｒ．ｍａｔｈ．ｕｗａｔｅｒｌｏｏ．ｃａ／ｔｅｃｈｒｅｐｏｒｔｓ／２００１／ｃｏｒｒ２００１−４１．ｐｓ＞
【非特許文献２】Ｒ．Ｍ．Ａｖａｎｚｉ，“Ｏｎ  ｍｕｌｔｉ−ｅｘｐｏｎｅｎｔｉａｔｉｏｎ  ｉｎ  ｃｒｙｐｔｏｆｒａｐｈｙ，”Ｃｒｙｐｔｏｌｏｇｙ  ｅＰｒｉｎｔ  Ａｒｃｈｉｖｅ：Ｒｅｐｏｒｔ  ２００２／１５４，  ２００２．［平成１８年２月２４日検索］インターネット＜ＵＲＬ；ｈｔｔｐ：／／ｅｐｒｉｎｔ．ｉａｃｒ．ｏｒｇ／２００２／１５４．＞
【非特許文献３】Ｋ．Ｏｋｅｙａ，Ｋ．Ｓｃｈｍｉｄｔ−Ｓａｍｏａ，Ｃ．Ｓｐａｈｎ，Ｔ．Ｔａｋａｇｉ，“Ｓｉｇｎｅｄ  Ｂｉｎａｒｙ  Ｒｅｐｒｅｓｅｎｔａｔｉｏｎｓ  Ｒｅｖｉｓｉｔｅｄ，”  Ａｄｖａｎｃｅｓ  ｉｎ  Ｃｒｙｐｔｏｌｏｇｙ−ＣＲＹＰＴＯ  ２００４，  ＬＮＣＳ  ３１５２，（２００４）．
【発明の開示】
【発明が解決しようとする課題】
【００１４】
上述のように楕円曲線暗号を用いれば、計算能力、メモリ容量などのリソースが比較的少なくても暗号処理を行うことが可能である。しかしながら、スマートカード（ＩＣカードともいう）のように、一般の計算機に比べ、さらにリソースの少ないデバイスは、少ないメモリ量に応じて最適な処理を行うことによって、処理速度に優れる暗号処理が必要となる。
【００１５】
非特許文献１、２の技術は、一旦、２つのスカラー値の表現を変換し、その後、変換した表現を用いて多重スカラー倍算を実行するために、変換したスカラー値の表現を格納するためのメモリが必要となる。また、変換と暗号処理を並列に行うとすると、楕円加算の計算方法として高速な手法を用いることができない。これは、スカラー値の変換処理が最下位ビットから最上位ビットに向けて（ｒｉｇｈｔ−ｔｏ−ｌｅｆｔ）処理が行われるのに対し、楕円加算の高速計算手法は最上位ビットから最下位ビットに向けて（ｌｅｆｔ−ｔｏ−ｒｉｇｈｔ）処理が行われたときに適用可能だからである。したがって、上記技術は、処理速度の改善、といった点について十分に考慮されていない。
【００１６】
多重スカラー倍計算では、まず複数のスカラー値を各数値列にエンコードする。ここで、エンコードとはスカラー値として用いられる大きな整数（２の１６０乗程度の値）を小さな数の列に変換する操作であり、この小さな数の列を数値列という。そして上記複数のスカラー値を上記数値列にエンコード後、上記各数値列を用いて、上記各数値列の各桁において、いずれかの数値列に０でない数値がある場合、楕円加算演算を用い、桁をずらす際に楕円２倍演算を用いる必要がある。ここで、各数値列の同じ桁位置に１つでも０でない数値がある桁、すなわち、各数値列の同じ桁位置が同時に０となるを非零桁と呼ぶ。上記各数値列における（非零桁の個数）／（桁数）の漸近的な値を非零濃度という。
【００１７】
非零濃度が小さくなると、上記各数値列における「０の桁」が増えることを意味するので、多重スカラー倍計算において、楕円加算演算の回数が減少し、その結果、多重スカラー倍計算の高速化を図ることができる。
【００１８】
また、非特許文献１の技術は、２つのスカラー値を０，１，−１の３値を用いてエンコードしているため前計算テーブルのサイズは小さいが、スマートカード等のリソースに余裕があり、前計算テーブルを大きくして高速化を図ることが可能な場合であっても対応できない。
【００１９】
非特許文献３の技術は、スカラー値のエンコードをｌｅｆｔ−ｔｏ−ｒｉｇｈｔで高速に行なうことができるが、多重スカラー倍算に対する考察がなされていない。
【課題を解決するための手段】
【００２０】
本発明は、与えられたメモリ量に応じて最適な処理を行うことによって、高速計算可能な楕円曲線演算方法を提供する。
【００２１】
本発明は、楕円曲線演算において、複数のスカラー値、及び、スカラー値の個数と同数の楕円曲線上の点から多重スカラー倍点を計算する楕円曲線暗号における多重スカラー倍計算装置であって、上記各スカラー値を独立に各数値列にエンコードし、上記楕円曲線上の点から事前計算テーブルを作成し、上記エンコードした各数値列、及び、上記事前計算テーブルから多重スカラー倍点を計算することによって、与えられたメモリ使用量に応じて最適な処理を行う、高速演算可能な楕円曲線演算方法を提供する。
【００２２】
また、本発明は、上記エンコード結果の非零濃度を小さくできる、つまり、エンコード結果における「０でない桁数」（つまり、エンコード結果における非零濃度）を減らすこと、及び、エンコード結果における「０である桁数」を増やすことができる楕円曲線多重スカラー倍計算を提供する。
【００２３】
非零濃度とは、スカラー値のエンコード結果（これは数値列である）における「０でない桁」の割合を表わす。楕円曲線スカラー倍計算、及び、多重スカラー倍計算においては、非零濃度が小さいと計算が高速になることが知られている。この理由は、次の通りである。
【００２４】
多重スカラー倍算においては、スカラー値のエンコード結果の各ビットの値が零でないとき、各々、楕円曲線上の加算を１回行う。したがって、ある決まったビット長のスカラー値に対し、非零ビットの個数が少なければ、楕円曲線上の加算の回数を減少させることができる。すなわち、非零濃度が小さくなると、エンコード結果における「０の桁」が増えることを意味するので、多重スカラー倍計算において、楕円加算演算の回数が減少し、この結果、多重スカラー倍計算の高速化を図ることができる。
＜発明概念を用いた説明＞
従来技術を用いた多重スカラー倍計算方法と本発明による多重スカラー倍計算方法との違いを図２６、図２７に示す例を用いて説明する。
【００２５】
２つのスカラー値ｄ０＝３２５４３４、ｄ１＝３８２５８と楕円曲線上の２つの点Ｐ０、Ｐ１に対して、多重スカラー倍点ｄ０Ｐ０＋ｄ１Ｐ１を計算する。図２６に記す従来技術を用いた多重スカラー倍計算方法では、
（１）前記スカラー値ｄ０，ｄ１をエンコードする。ただし、従来技術を用いた多重スカラー倍計算において、エンコードとは、各スカラー値ｄ０，ｄ１のバイナリ表現を、数値列に変換する操作であり、前記数値列における各桁は０、±１の何れか一つである。
ここでは、ｄ０、ｄ１はそれぞれ
ｄ０＝（０１０１００００−１０００−１−１００−１０１０）
ｄ１＝（００００１０１０−１０−１０−１００−１００１０）
にエンコードされる。
【００２６】
（２）前記楕円曲線上の点Ｐ０、Ｐ１から点Ｐ０＋Ｐ１、点Ｐ０−Ｐ１を計算する。前計算テーブルは、点Ｐ０、Ｐ１、Ｐ０＋Ｐ１、Ｐ０−Ｐ１の４点からなる。例えば、点Ｐ０、Ｐ１のビット長が５０バイト程度の場合、前計算テーブルは２００バイト程度の大きさとなる。
【００２７】
（３）前記各エンコード結果の各桁を見る。ここで、ｄ０、ｄ１のｉ桁目（ｉは自然数）の数値をそれぞれｄ０［ｉ］、ｄ１［ｉ］で表す。（ｄ０［ｉ］ｄ１［ｉ］）が（００）の場合は楕円加算を行わない。（１０）、（−１０）の場合には、点Ｐ０、点−Ｐ０をそれぞれ加算する。（０１）、（０−１）の場合には、点Ｐ１、点−Ｐ１をそれぞれ加算する。（１１）、（−１−１）の場合には、点Ｐ０＋Ｐ１、点−（Ｐ０＋Ｐ１）をそれぞれ加算する。（１−１）、（−１１）の場合には、点Ｐ０−Ｐ１、点−（Ｐ０−Ｐ１）をそれぞれ加算する。
【００２８】
例えば、図２６の多重スカラー倍点ｄ０Ｐ０＋ｄ１Ｐ１計算では、
まず、点Ｒ（これはワークメモリである）を上記楕円曲線の無限遠点で初期化する。
【００２９】
次に、多重スカラー倍計算を最上位ビット（最も左）から最下位ビット（最も右）に向けて（ｌｅｆｔ−ｔｏ−ｒｉｇｈｔ）実行する。
【００３０】
具体的には、上記（ｄ０、ｄ１）の最上位桁は（００）だから楕円加算を行わない。２桁目（１０）より点Ｒに点Ｐ０を加算し、桁ずらしのために楕円２倍算を行う。３桁目（００）より楕円加算を行わず、桁ずらしのために楕円２倍算を行う。４桁目（１０）より点Ｒに点Ｐ０を加算し、桁ずらしのために楕円２倍算を行う。５桁目（０１）より点Ｒに点Ｐ１を加算し、桁ずらしのために楕円２倍算を行う。上記処理を上記各数値列の最下位桁まで繰り返す。
【００３１】
これに対し、図２７に記す本発明による多重スカラー倍計算方法では、
（１）上記各スカラー値のバイナリ表現に対し、連続する２ビットに対する減算を行い、第一の数値列を得る。この第一の数値列をＭＯＦ表現という。
ここでは、ｄ０、ｄ１はそれぞれ、
ｄ０＝（１−１０１０００−１１００−１０１００−１１−１０）
ｄ１＝（０００１−１０１−１１−１１−１１００−１０１−１０）
にエンコードされる。
【００３２】
上記連続する２ビットに対する減算とは以下の通りである。
【００３３】
ｄ０＝３２５４３４に対するバイナリ表現は
ｄ０＝（１００１１１１０１１１００１１１０１０）
であり、２ｄ０のバイナリ表現は、ｄ０を左に１ビットシフトしたものであり、
２ｄ０＝（１００１１１１０１１１００１１１０１００）
である。対応するビット位置のビット毎に減算を行うと、第一の数値列ｄ０
ｄ０＝（１−１０１０００−１１００−１０１００−１１−１０）
を得る。言い換えると、元のビット位置のビットの１ビット右のビットからの減算を、ビット毎に行っていることになる。この計算が、連続する２ビットに対する減算である。
【００３４】
ｄ１に対する第一の数値列計算方法も同様である。
【００３５】
（２）上記第一の数値列から前記第一の各数値列とは異なる第二の各数値列
ｅ０＝（ｅ０［ｎ］ｅ０［ｎ−１］…ｅ０［０］）
ｅ１＝（ｅ１［ｎ］ｅ１［ｎ−１］…ｅ１［０］）
にエンコードする。ただし、各ｉ、ｊに対し、ｅｉ［ｊ］は
−（２ｗ−１−１）≦ｅｉ［ｊ］≦（２ｗ−１−１）
を満たす奇数もしくは０である。また、数値列ｅ０のビット長はｎ＋１であり、ｅ０［ｎ］は、数値列ｅ０の右からｎ＋１桁目の数値を示す。ｉ、ｊは、それぞれ自然数である。ここで、ｗはあらかじめ定めた正の整数で、ウィンドウ幅と呼ばれる。計算時間を優先する場合はｗを大きな値とする。メモリ使用量を小さくする場合はｗを小さな値にする。図２７では、ｗ＝２、３の場合について上記第二の各数値列を計算しているが、ｗ＝３の場合のみ説明する（つまり、−３≦ｅｉ［ｊ］≦３を満たす奇数もしくは０）。上記第二の各数値列にエンコードする方法は以下の通りである。
【００３６】
まず、前記第一の各数値列を見て、０に変更可能であるかどうかを判定し、０に変更可能な項は１、０に変更することができない項は０を用いて表わす（図２７の変換可否判定（ｗ＝３））。
【００３７】
上記判定を用いて、上記第二の各数値列にエンコードする。ただし、図２７の変換可否判定において、最上位にある［１０１］は、最上位の三桁を見て、０に変換可能な項の総数が２つであるから、最上位の三桁を変換する。次の［１１０１０］は最上位三桁と隣り合う五桁を見ることを意味する。ここでは、最初から五桁を見るのではなく、三桁を見て、０に変換可能な項の総数が予め定められた数より小さいので、五桁を見て変換を行う。次に［１１０１０］と隣り合う四桁を見る。ここでも、最初から四桁を見るのではなく、三桁を見て、０に変換可能な項の総数が予め定められた数より小さく、五桁を見て、０に変換可能な項の総数が予め定められた数より小さいので、四桁を見て変換を行う。
【００３８】
次に［１１００］と隣り合う三桁を見る。ただし、［１１００］が示す桁の最下位桁が含まれている。［１１００］が示す桁の最下位桁を含む理由は、０に変換可能な項の総数を増加させるためである。上記処理を上記各数値列の最下位ビット列までを対象に繰り返す。
【００３９】
図２６における２つのスカラー値のエンコード結果は０の項の総数が９個であるのに対し、図２７における２つのスカラー値のエンコード結果は０の項の総数が１２個であり、０の項の総数が増加していることがわかる。
【００４０】
（２）前記楕円曲線上の点Ｐ０、−Ｐ１から点ａＰ０＋ｂＰ１（ただし、−３≦ａ，ｂ≦３なる奇数および０で、ａ，ｂ双方が０の場合を除く）を計算する。前計算テーブルは、点ａＰ０＋ｂＰ１（ただし、１≦ａ≦３なる奇数および０、−３≦ｂ≦３なる奇数および０で、ａ，ｂ双方が０の場合を除く）の１２個の点からなる。例えば、点Ｐ０、Ｐ１のビット長が５０バイト程度の場合、前計算テーブルは６００バイト程度の大きさとなる。
【００４１】
（３）多重スカラー倍点ｄ０Ｐ０＋ｄ１Ｐ１計算方法は上記図２６（３）における多重スカラー倍計算方法と同様である。
【００４２】
図２６における従来技術を用いたスカラー倍計算方法では（点Ｐ０、Ｐ１のビット長が５０バイト程度の場合）、前計算テーブルのサイズは２００バイト程度、楕円加算回１０回、楕円２倍算１８回であるのに対し、図２７における本発明を用いたスカラー倍計算方法では、前計算テーブルのサイズは６００バイト程度、楕円加算７回、楕円２倍算１８回であり、図２６と比較して多重スカラー倍計算を高速に実行できることがわかる。また、上記の例では、ｗ＝３の場合に説明しているが、一般のｗに対するエンコード方法も同様である。
【００４３】
本発明は更に、上記楕円曲線演算方法を用いた、署名検証方法、暗号化処理方法、復号化処理方法、データ共有方法、及び、鍵生成方法を提供する。
【００４４】
本発明は更に、上記楕円曲線演算方法を用いた、署名検証装置、署名生成装置、暗号化処理装置、復号化処理装置、データ生成装置を提供する。
【００４５】
より具体的な本発明の一態様においては、楕円曲線演算において、複数のスカラー値、及び、スカラー値の個数と同数の楕円曲線上の点から多重スカラー倍点を計算する楕円曲線暗号における多重スカラー倍計算装置は、上記第一の各数値列にエンコードするステップと、上記各スカラー値のバイナリ表現に対し、連続する２ビットに対する減算を行い、上記第二の数値列にエンコードするステップは、上記第一の各数値列に対し、連続する第一のビット数に対して０に変換可能な項を判定するステップと、連続する第一のビット数を含み、第一のビット数と異なる第二のビット数に対して０に変換可能な項を判定するステップと、０に変換可能な項の総数とを比較するステップと、０に変換可能な項の総数が予め定められた値以上の場合は、第一の数値列を変換するステップと、０に変換可能な項の総数が予め定められた値より小さい場合は、第一のステップを用いて第一の数値列を変換するステップと、上記ステップを繰り返し行う第五のステップと、を実行することを特徴とする。
【発明の効果】
【００４６】
本発明によれば、メモリ使用量が少なく，高速計算可能なスカラー倍演算装置を実現することができる。
【発明を実施するための最良の形態】
【００４７】
以下、本発明の実施の形態を図面に基づいて詳細に説明する。
【００４８】
図１はネットワーク１４２によって接続された本発明による楕円曲線演算方法を適用したコンピュータ１０１、スマートカード１２１がネットワーク１４２により接続されたシステム構成を示すものである。本発明を署名検証システムに適用する実施形態を、図１と図２を用いて説明する。
【００４９】
図１の署名検証システムは、コンピュータ１０１と署名検証処理を行うスマートカード１２１とから成る。
【００５０】
コンピュータ１０１は、ＣＰＵ１１３やコプロセッサ１１４などの演算装置、ＲＡＭ１０３、ＲＯＭ１０６や外部記憶装置１０７などの記憶装置、コンピュータ外部とのデータ入出力を行なう入出力インタフェース１１０を装備しており、外部にはコンピュータ１０１をユーザが操作するためのディスプレイ１０８、キーボード１０９、着脱可能な可搬型記憶媒体の読み書き装置などが接続されている。
【００５１】
更にコンピュータ１０１は、ＲＡＭ１０３、ＲＯＭ１０６や外部記憶装置１０７などの記憶装置によって、記憶部１０２を実現し、ＣＰＵ１１３やコプロセッサ１１４などの演算装置が、記憶部１０２に格納されたプログラムを実行することにより、署名生成処理部１１２とスカラー倍計算部１１５とそれらに含まれる各処理部とを実現する。
【００５２】
署名生成処理部１１２は、入力されたメッセージの署名生成を行なう。
【００５３】
スカラー倍計算部１１５は、署名生成処理部１１２で署名生成を行なうのに必要なパラメタを計算する。記憶部１０２は、定数１０４（例えば、楕円曲線の定義式や楕円曲線上の定点である）、秘密情報１０５（例えば、秘密鍵である）などを記憶している。
【００５４】
スマートカード１２１は、コンピュータ１０１と同様に、演算装置、外部記憶装置、入出力インタフェースを備えており、ＣＰＵ１１３がプログラムを実行することにより、署名検証処理部１３２と多重スカラー倍計算部１３５とそれらに含まれる各処理部とを実現する。
【００５５】
なお、各実施例の構成において、コンピュータ１２１内の各プログラムは、あらかじめ、上記コンピュータ内の記憶部に格納されていても良いし、必要なときに、スマートカード１２１が利用可能な媒体を介して他の装置から上記記憶部に導入されてもよい。
【００５６】
さらに、コンピュータ１０１内の各プログラムは、あらかじめ、上記コンピュータ１０１内の記憶部に格納されていても良いし、必要なときに、入出力インタフェースを介して接続するコンピュータ、または当該コンピュータが利用可能な媒体を介して上記記憶部に導入されてもよい。媒体とは、たとえば当該コンピュータに着脱可能な記憶媒体、または通信媒体（すなわちネットワークまたはネットワークを伝搬する搬送波やディジタル信号）を指す。
【００５７】
次に、図１の署名検証システムにおいて、署名生成処理部１１２が行う署名生成処理を、図２を参照して説明する。
【００５８】
離散対数問題に基づくディジタル署名方法を楕円曲線上の離散対数問題に基づく方法に対応させて構成する楕円曲線ディジタル署名アルゴリズム（ＥＣＤＳＡ）という署名方法がある。ＥＣＤＳＡ署名については、たとえば文献
Ｄ．Ｊｏｈｎｓｏｎ，Ａ．Ｍｅｎｅｚｅｓ，“Ｔｈｅ  Ｅｌｌｉｐｔｉｃ  Ｃｕｒｖｅ  Ｄｉｇｉｔａｌ  Ｓｉｇｎａｔｕｒｅ  Ａｌｇｏｒｉｔｈｍ  （ＥＣＤＳＡ）”，  Ｔｅｃｈｎｉａｌ  Ｒｅｐｏｒｔ  ＣＯＲＲ  ９９−３４，  Ｄｅｐｔ．  ｏｆ  Ｃ＆Ｏ，  Ｕｎｉｖｅｒｓｉｔｙ  ｏｆ  Ｗａｔｅｒｌｏｏ，  Ｃａｎａｄａ．  ＜ＵＲＬ＞  ｈｔｔｐ：／／ｗｗｗ．ｃａｃｒ．ｍａｔｈ．ｕｗａｔｅｒｌｏｏ．ｃａ／ｔｅｃｈｒｅｐｏｒｔｓ／１９９９／ｃｏｒｒ９９−３４．ｐｄｆ（以下、文献ＥＣＤＳＡという）に記載されている。
【００５９】
スマートカード１２１は、ランダムに選んだ数値をチャレンジコード１４２として、インタフェースを介してコンピュータ１０１に転送する（図２の２０１）。
【００６０】
署名生成処理部１１２（図２の１１２）は、チャレンジコード１４２を受け付け、チャレンジコード１４２のハッシュ値をとり、所定のビット長の数値ｆに変換する。
【００６１】
署名生成処理部１１２は、乱数ｕを生成し、記憶部１０２（図２の１０２）に格納されている定数１０４から読み出した（図２の２０２）楕円曲線上の定点Ｑとともにスカラー倍計算部１１５（図２の１１５）へ送る（図２の２０３）。
【００６２】
スカラー倍計算部１１５は、定点Ｑ、乱数ｕによるスカラー倍点ｕＱ＝（ｘｕ，ｙｕ）を計算し、計算されたスカラー倍点を署名生成処理部１１２へ送る（図２の２０５）。
【００６３】
署名生成処理部１１２は、送られたスカラー倍点を用いて署名の生成を行う。例えば、上記文献ＥＣＤＳＡに記載のＥＣＤＳＡ署名であれば、
ｓ＝ｘｕ  ｍｏｄ  ｑ                    （式６）
ｔ＝ｕ−１（ｆ＋ｄｓ）  ｍｏｄ  ｑ        （式７）
を計算することによりチャレンジコード１４２に対応する署名（ｓ，ｔ）を得る（図２の２０６）。
【００６４】
ここで、ｑは定点Ｑの位数、すなわち定点Ｑのｑ倍点ｑＱが無限遠点になり、ｑより小さな数値ｍに対する定点Ｑのｍ倍点ｍＱは無限遠点にはならない、というような数値のことである。
【００６５】
署名検証処理部１３２が行う署名検証処理を、図３を参照して説明する。
【００６６】
コンピュータ１０１は、署名生成処理部１１２で生成した署名１４１を入出力インタフェース１１０より出力し、インタフェースを介してスマートカード１２１へ転送する（図３の３０１）。
【００６７】
スマートカード１２１の署名検証処理部１３２（図３の１３２）は、署名１４１が入力される（図３の３０１）と、署名１４１の数値ｓ，ｔが適切な範囲内すなわち１≦ｓ，ｔ＜ｑであるかを調べる。
【００６８】
数値ｓ，ｔが上記範囲内になければチャレンジコード１４２に対する署名の検証結果として「無効」を出力し、コンピュータ１０１を拒絶する（図３の３０２）。数値ｓ，ｔが上記範囲内にあれば、署名検証処理部１３２は、
ｈ＝ｔ−１  ｍｏｄ  ｑ              （式８）
ｈ１＝ｆｈ  ｍｏｄ  ｑ              （式９）
ｈ２＝ｓｈ  ｍｏｄ  ｑ              （式１０）
を計算する。
【００６９】
そして、記憶部１２２（図３の１２２）に格納されている定数１２４から読み出した（図３の３０３）公開鍵ｄＱ及び定点Ｑと計算したｈ１，ｈ２を多重スカラー倍計算部１３５（図２の１３５）へ送る（図３の３０４）。
【００７０】
署名検証処理部１３２は、送られたスカラー倍点を用いて、署名検証処理を行う。例えば、ＥＣＤＳＡの署名検証であれば、多重スカラー倍点Ｒ
Ｒ＝ｈ１Ｑ＋ｈ２（ｄＱ）            （式１１）
を計算し、計算された多重スカラー倍点を署名検証処理部１３２へ送る（図３の３０５）。
【００７１】
署名検証処理部１３２は、Ｒのｘ座標をｘＲとしたとき、
ｓ´＝ｘＲ  ｍｏｄ  ｑ              （式１２）
を計算し、ｓ´＝ｓであればチャレンジコード１４２に対する署名の検証結果として「有効」を出力し、スマートカード１０１を認証し、受け入れる（図３の３０６）。
【００７２】
ｓ´＝ｓでなければ「無効」を出力し、スマートカードを拒絶する（図３の３０２）。
【００７３】
次に、スマートカード１２１が、署名検証処理を行う場合の、多重スカラー倍計算部１３５の処理を詳細に説明する。なお、多重スカラー倍算においては、スカラー値のエンコード結果の各ビットの値が零でないとき、各々、楕円曲線上の加算を１回行うため、エンコード結果における「０の桁」を増加させ、非零濃度を小さくすることにより、多重スカラー倍計算の高速化を図ることができる。
【００７４】
＜多重スカラー倍計算部の実施例１＞
本実施例では、図４で示される多重スカラー倍計算部１３５の機能ブロックを用いる。多重スカラー倍計算部１３５は、エンコード部４０２、前計算部４０３、実計算部４０４からなる。エンコード部４０２は、数値計算部４２１、数値変換部４２２、拡張可否判定部４２３、拡張部４２４、繰り返し判定部４２５、格納部４２６からなる。前計算部４０３は、加算部４３１、２倍算部４３２、繰り返し判定部４３３からなる。実計算部４０４は、ビット値判定部４４１、加算部４４２、２倍算部４４３、繰り返し判定部４４４からなる。
【００７５】
多重スカラー倍計算部１３５がスカラー値ｄ０、ｄ１、及び、楕円曲線上の点Ｐ０、Ｐ１から、楕円曲線における多重スカラー倍点ｄ０Ｐ０＋ｄ１Ｐ１を計算する第一の計算方法を説明する。多重スカラー倍計算部１３５が署名検証処理部１３２からスカラー値ｄ０、ｄ１と楕円曲線上の点Ｐ０、Ｐ１を受け取ると、エンコード部４０２は、入力されたスカラー値ｄ０、ｄ１を
ｅ０＝（ｅ０［ｎ］ｅ０［ｎ−１］…ｅ０［０］）          （式１３）
ｅ１＝（ｅ１［ｎ］ｅ１［ｎ−１］…ｅ１［０］）          （式１４）
にエンコードする。
【００７６】
ただし、各ｉ，ｊに対して、ｅｉ［ｊ］は
−（２ｗ−１−１）≦ｅｉ［ｊ］≦（２ｗ−１−１）          （式１５）
を満たす奇数もしくは０である。
【００７７】
ここで、エンコードとは、スカラー値として用いられるような大きな整数（２１６０程度）から小さな数の列に変換する操作である。ただし、エンコード前のスカラー値ｄとエンコード後の数値列ｅは、それらが表す数値として等しい。すなわち次の式をみたす。
【００７８】
ｄ＝ｅ［ｎ］２ｎ＋ｅ［ｎ−１］２ｎ−１＋…＋ｅ［０］        （式１６）
ｗはあらかじめ定めた正の整数で、ウィンドウ幅と呼ばれる。計算時間を優先する場合はｗを大きな値とする。メモリ使用量を小さくする場合はｗを小さな値にする。
【００７９】
前計算部４０３は、入力された楕円曲線上の点Ｐ０、Ｐ１から、前計算テーブルを作成する。前計算テーブルは点ａＰ０＋ｂＰ１により構成される。ここで、ａ，ｂは、−（２ｗ−１−１）≦ａ，ｂ≦（２ｗ−１−１）を満たす奇数または０（ただしａ，ｂ双方が０の場合を除く。ａ’Ｐ０＋ｂ’Ｐ１＝−（ａＰ０＋ｂＰ１）となるａ’Ｐ０＋ｂ’Ｐ１は格納しなくとも良い。）である。本実施例では、ｗ＝３とする。
【００８０】
実計算部４０４は、２つのスカラー値をエンコードした数値列ｅ０，ｅ１、楕円曲線上の点Ｐ０、Ｐ１および前計算テーブルから多重スカラー倍点ｄ０Ｐ０＋ｄ１Ｐ１を計算する。
【００８１】
なお、本実施例では、エンコード処理のフローチャートでサブルーチンを呼び出す処理があり、上記処理については、図６〜９で説明する。呼び出されるサブルーチンは全部で４つあり、０の項が生成可能なビット位置を返すサブルーチンｃａｌ（ｄ０，ｄ１，ｕ，Ｌ，ｃ）、より多くの０の項を生成するために読み込むビット列を増加させた方がよいかどうかを判定するサブルーチンｅｘｐａｎｄ判定、読み込むビット列を増加させた方が良い場合に読み込みビット列を拡張させるサブルーチンｅｘｐａｎｄ（ｄ）、０の項が生成可能なビット位置に関する情報に基づき実際に変換を行うサブルーチンｃｏｎｖｅｒｔ（ｄ）である。なお、サブルーチンの呼び出し、制御、及び、データの流れに関するシーケンス図が図２５に記載されている。
【００８２】
次にエンコード部４０２、前計算部４０３、実計算部４０４の行う各処理について詳細に説明する。まず、図５〜図９を用いて、エンコード部４０２がスカラー値ｄ０、ｄ１をｅ０，ｅ１にエンコードする方法を説明する。図５は、本実施例のエンコード処理（ｅｎｃｏｄｉｎｇ）全体を説明するための図である。ここでは、上述のようにｗは３、数値列数（ｋ）は２、処理は最下位ビットから最上位ビットに向けて（ｒｉｇｈｔ−ｔｏ−ｌｅｆｔ）行う。
【００８３】
エンコード部４０２は、受け取った入力ｄ０，ｄ１に対して連続する２ビットに対する減算を行い各々のＭＯＦ表現を計算し、それぞれｅ０，ｅ１に格納し、ｅ０［ｎ］に０、ｅ１［ｎ］に０、ｕに０をそれぞれ代入する（５０１）。本処理において、ｕは、変換対象の数値のビット位置を示す変数である。
【００８４】
繰り返し判定部４２５は、ｕ＜ｎ−１かどうかを判定する。条件が成立する場合、ステップ５０３へ行く。条件が成立しない場合、ステップ５１９へ行く（５０２）。
【００８５】
繰り返し判定部４２５は、ｅ０［ｕ］＝０かつｅ１［ｕ］＝０かどうかを判定する。条件が成立する場合、ステップ５０４へ行く。条件が成立しない場合、ステップ５０５へ行く（５０３）［一桁チェック］。
【００８６】
ｕにｕ＋１を代入し、ステップ５０２へ行く（５０４）。
【００８７】
Ｌにｕ＋２を代入し、数値計算部４２１は、ｚｕ，Ｌ＝ｃａｌ（ｅ０，ｅ１，ｕ，Ｌ，１）を計算する（５０５）［三桁チェック］。ここでｚｕ，Ｌは、どのビット位置で０の項を生成することができるかを示す数値であり、数値ｚｕ，Ｌをバイナリ表現した際、ビット値１はそのビット位置において０の項が生成可能、ビット値０はそのビット位置において０の項が生成不可能であることを示している。
【００８８】
繰り返し判定部４２５は、ｎ≦Ｌまたはｚｕ，Ｌが（１０１），（１１０），（０１１）のどれか一つと等しいかどうかを判定する。条件が成立する場合、ステップ５０７へ行く。条件が成立しない場合、ステップ５１０へ行く（５０６）。
【００８９】
拡張可否判定部４２３は、ｅｘｐａｎｄ（ｅ０）、ｅｘｐａｎｄ（ｅ１）が計算できるかどうか判定する。条件が成立する場合、ステップ５０９へ行く。条件が成立しない場合、ステップ５０８へ行く（５０７）。
【００９０】
数値変換部４２２は、ｃｏｎｖｅｒｔ（ｅ０）、ｃｏｎｖｅｒｔ（ｅ１）を計算し、ｕにｕ＋３を代入し、ステップ５０２へ行く（５０８）。
【００９１】
ｚｕ，Ｌに（０１０）を代入し、拡張部４２４は、ｅｘｐａｎｄ（ｅ０）、ｅｘｐａｎｄ（ｅ１）を計算し、数値変換部４２２は、ｃｏｎｖｅｒｔ（ｅ０）、ｃｏｎｖｅｒｔ（ｅ１）を計算し、ｕにｕ＋２を代入し、ステップ５０２へ行く（５０９）。
【００９２】
Ｌにｕ＋４を代入し、数値計算部４２１は、ｚｕ，Ｌ＝ｃａｌ（ｅ０，ｅ１，ｕ，Ｌ，１）を計算する（５１０）［五桁チェック］。
【００９３】
繰り返し判定部４２５は、ｚｕ，Ｌ＝（１１０１０）であるかどうかを判定する。条件が成立する場合、ステップ５１２へ行く。条件が成立しない場合、ステップ５１５へ行く（５１１）。
【００９４】
拡張可否判定部４２３は、ｅｘｐａｎｄ（ｅ０）、ｅｘｐａｎｄ（ｅ１）が計算できるかどうか判定する。条件が成立する場合、ステップ５１４へ行く。条件が成立しない場合、ステップ５１３へ行く（５１２）。
【００９５】
数値変換部４２２は、ｃｏｎｖｅｒｔ（ｅ０）、ｃｏｎｖｅｒｔ（ｅ１）を計算し、ｕにｕ＋５を代入し、ステップ５０２へ行く（５１３）。
【００９６】
ｚｕ，Ｌに（０１０１０）を代入し、拡張部４２４は、ｅｘｐａｎｄ（ｅ０）、ｅｘｐａｎｄ（ｅ１）を計算し、数値変換部４２２は、ｃｏｎｖｅｒｔ（ｅ０）、ｃｏｎｖｅｒｔ（ｅ１）を計算し、ｕにｕ＋４を代入し、ステップ５０２へ行く（５１４）。
【００９７】
Ｌにｕ＋３を代入し、数値計算部４２１は、ｚｕ，Ｌ＝ｃａｌ（ｅ０，ｅ１，ｕ，Ｌ，１）を計算する（５１５）［四桁チェック］。
【００９８】
拡張可否判定部４２３は、ｅｘｐａｎｄ（ｅ０）、ｅｘｐａｎｄ（ｅ１）が計算できるかどうか判定する。条件が成立する場合、ステップ５１８へ行く。条件が成立しない場合、ステップ５１７へ行く（５１６）。
【００９９】
数値変換部４２２は、ｃｏｎｖｅｒｔ（ｅ０）、ｃｏｎｖｅｒｔ（ｅ１）を計算し、ｕにｕ＋４を代入し、ステップ５０２へ行く（５１７）。
【０１００】
ｚｕ，Ｌに（０１００）を代入し、拡張部４２４は、ｅｘｐａｎｄ（ｅ０）、ｅｘｐａｎｄ（ｅ１）を計算し、数値変換部４２２は、ｃｏｎｖｅｒｔ（ｅ０）、ｃｏｎｖｅｒｔ（ｅ１）を計算し、ｕにｕ＋３を代入し、ステップ５０２に行く（５１８）。
【０１０１】
エンコード部４０２は、ｅ０［０］、…、ｅ０［ｎ］、ｅ１［０］、…、ｅ１［ｎ］を出力する（５１９）。
【０１０２】
図６を用いて、ステップ５０５、ステップ５１０、ステップ５１５で数値計算部４２１がｚｕ，Ｌ＝ｃａｌ（ｄ０，ｄ１，ｕ，Ｌ，ｃ）を計算する方法（ｃａｌｃｕｌａｔｅ  ｚ）を説明する。
【０１０３】
数値計算部４２１は、与えられた二つのスカラー値ｄ０，ｄ１においてビット位置ｕからビット位置Ｌまでのビット列に対して、キャリービットｃに応じてどのビット位置で０の項を生成することができるかを示す数値ｚを出力する。数値ｚをバイナリ表現した際、ビット値１はそのビット位置において０の項が生成可能、ビット値０はそのビット位置において０の項が生成不可能であることを示している。
【０１０４】
数値計算部４２１はｄ０、ｄ１、Ｌ、ｕ、ｃを入力として受け取り、ｉに０を代入する（６０１）。
【０１０５】
数値計算部４２１は、ｉ≦１であるかどうかを判定する。条件が成立する場合、ステップ６０３へ行く。条件が成立しない場合、ステップ６１０へ行く（６０２）。
【０１０６】
ｆｉに−１を代入する（６０３）。ｆｉは、ｄｉがどの相対ビット位置で０とすることができないかを示す相対ビット位置を示す変数である。
【０１０７】
ｊにｕ−Ｌを代入する（６０４）。
【０１０８】
数値計算部４２１は、ｊ≧０であるかどうかを判定する。条件が成立する場合、ステップ６０７へ行く。条件が成立しない場合、ステップ６０６へ行く（６０５）。
【０１０９】
ｉにｉ＋１を代入する（６０６）。
【０１１０】
数値計算部４２１は、ｄｉ［ｊ＋Ｌ］＝０であるかどうかを判定する。条件が成立する場合、ステップ６０９へ行く。条件が成立しない場合、ステップ６０８へ行く（６０７）。
【０１１１】
ｆｉにｊを代入する（６０８）。
【０１１２】
ｊにｊ−１を代入する（６０９）。
【０１１３】
ｒに０、ｊにｕ−Ｌを代入する（６１０）。
【０１１４】
数値計算部４２１は、ｊ≧０であるかどうかを判定する。条件が成立する場合、ステップ６１２へ行く。条件が成立しない場合、ステップ６１８へ行く（６１１）。
【０１１５】
数値計算部４２１は、ｊ＝ｆ０またはｊ＝ｆ１またはｒ＝２であるかどうかを判定する。条件が成立する場合、ステップ６１４へ行く。条件が成立しない場合、ステップ６１３へ行く（６１２）。
【０１１６】
ｚｊに１、ｒにｒ＋１を代入し、ステップ６１５へ行く（６１３）。
【０１１７】
ｚｊに０、ｒに０を代入する（６１４）。
【０１１８】
数値計算部４２１は、ｃ＝０かつｊ＝ｕＬかつｚｕ−Ｌ＝１であるかどうかを判定する。条件が成立する場合、ステップ６１６へ行く。条件が成立しない場合、ステップ６１７へ行く（６１５）。
【０１１９】
ｒに２を代入する（６１６）。
【０１２０】
ｊにｊ−１を代入し、ステップ６１１へ行く（６１７）。
【０１２１】
数値計算部４２１は、ｚを出力する（６１８）。
【０１２２】
図７を用いて、ステップ５０８、ステップ５０９、ステップ５１３、ステップ５１４、ステップ５１７、ステップ５１８で数値変換部４２２が、ｃｏｎｖｅｒｔ（ｄ０）、ｃｏｎｖｅｒｔ（ｄ１）を計算する方法（ｃｏｎｖｅｒｓｉｏｎ）について説明する。数値変換部４２２は、与えられたビット列ｄ０，ｄ１を、ｃａｌ（ｄ０，ｄ１，ｕ，Ｌ，ｃ）の出力した数値ｚに基づき、ｚのバイナリ表現においてビット値が１となるビット位置において０の項となる数値列ｄ０，ｄ１に変換する。以下の処理では、０の項に変換すべきビット位置（次の部分ビット列の左端のビット）において、１００・・・０（−１）を０１１・・・１１、（−１）００・・・０１を０（−１）（−１）・・・（−１）（−１）、１００・・・０１を０３（−１）・・・（−１）（−１）、（−１）００・・・０（−１）を０（−３）１・・・１１と変換する基本処理を繰り返すことにより達成している。
【０１２３】
数値変換部４２２は、ｄ０、ｄ１、Ｌ、ｕ、ｚを入力として受け取り、ｉに０を代入する（７０１）。
【０１２４】
数値変換部４２２は、ｉ≦１であるかどうかを判定する。条件が成立する場合、ステップ７０３へ行く。条件が成立しない場合、ステップ７２０へ行く（７０２）。
【０１２５】
ｊにｕを代入する（７０３）。
【０１２６】
数値変換部４２２は、ｊ≧Ｌであるかどうかを判定する。条件が成立する場合、ステップ７０６へ行く。条件が成立しない場合、ステップ７０５へ行く（７０４）。
【０１２７】
ｉにｉ＋１を代入し、ステップ７０２へ行く（７０５）。
【０１２８】
数値変換部４２２は、ｚｊＬ＝１かつｄｉ［ｊ］≠０であるかどうかを判定する。条件が成立する場合、ステップ７０７へ行く。条件が成立しない場合、ステップ７１９へ行く（７０６）。
【０１２９】
ｓにｊ−１を代入する（７０７）。
【０１３０】
数値変換部４２２は、ｄｉ［ｓ］＝０であるかどうかを判定する。条件が成立する場合、ステップ７０９へ行く。条件が成立しない場合、ステップ７１０へ行く（７０８）。
【０１３１】
ｓにｓ−１を代入し、ステップ７０８へ行く（７０９）。
【０１３２】
数値変換部４２２は、ｄｉ［ｊ］＝ｄｉ［ｓ］であるかどうかを判定する。条件が成立する場合、ステップ７１５へ行く。条件が成立しない場合、ステップ７１１へ行く（７１０）。
【０１３３】
ｔにｊ−１を代入する（７１１）。
【０１３４】
数値変換部４２２は、ｓ≦ｔであるかどうかを判定する。条件が成立する場合、ステップ７１３へ行く。条件が成立しない場合、ステップ７１４へ行く（７１２）。
【０１３５】
ｄｉ［ｔ］にｄｉ［ｊ］、ｔにｔ−１をそれぞれ代入し、ステップ７１２へ行く（７１３）。
【０１３６】
ｄｉ［ｊ］に０を代入し、ステップ７１９へ行く（７１４）。
【０１３７】
ｄｉ［ｊ−１］に３ｄｉ［ｊ］、ｔにｊ−２をそれぞれ代入する（７１５）。
【０１３８】
数値変換部４２２は、ｓ≦ｔであるかどうかを判定する。条件が成立する場合、ステップ７１７へ行く。条件が成立しない場合、ステップ７１８へ行く（７１６）。
【０１３９】
ｄｉ［ｔ］に−ｄｉ［ｊ］、ｔにｔ−１をそれぞれ代入し、ステップ７１６へ行く（７１７）。
【０１４０】
ｄｊ［ｊ］に０を代入する（７１８）。
【０１４１】
ｊにｊ−１を代入し、ステップ７０４へ行く（７１９）。
【０１４２】
数値変換部４２２は、ｄ０とｄ１を出力する（７２０）。
【０１４３】
図８を用いて、ステップ５０７、ステップ５１２、ステップ５１６で拡張可否判定部４２３が、ｅｘｐａｎｄ（ｄ０）、ｅｘｐａｎｄ（ｄ１）が計算できるかどうか判定する方法（ｄｅｃｉｓｉｏｎ  ｆｏｒ  ｅｘｐａｎｓｉｏｎ）について説明する。
拡張可否判定部４２３は、数値変換部４２２が複数の数値列を変換する処理において、変換後に数値列が含む０の総数を最適化することができるかどうかを判定する。具体的には、数値列ｄ０，ｄ１，ビット位置ｕ，Ｌの入力に対し、数値列ｄ０，ｄ１においてビット位置ｕからビット位置Ｌまでで構成される数値列に対して、変換後の数値列の最上位ビットを次の変換のために再利用した方がよいかどうかを判定し、その判定結果を出力する。
【０１４４】
拡張可否判定部４２３は、ｄ０，ｄ１，Ｌ，ｕを入力として受け取る（８０１）。
【０１４５】
拡張可否判定部４２３は、Ｌ≦ｎ−３であるかどうかを判定する。条件が成立する場合、ステップ８０３へ行く。条件が成立しない場合、ステップ８０７へ行く（８０２）。
【０１４６】
拡張可否判定部４２３は、ｄ０［Ｌ＋２］≠０かつｄ０［Ｌ＋１］＝０かつｄ１［Ｌ＋１］≠０であるか、または、ｄ１［Ｌ＋２］≠０かつｄ１［Ｌ＋１］＝０かつｄ０［Ｌ＋１］≠０であるかどうかを判定する。どちらか一方の条件が成立する場合、ステップ８０４へ行く。どちらの条件も成立しない場合、ステップ８０７へ行く（８０３）。
【０１４７】
拡張可否判定部４２３は、ｄ０［Ｌ＋２］＝０かつｄ０［Ｌ＋１］＝０かつｄ１［Ｌ＋２］＝０かつｄ１［Ｌ＋１］＝０であるかどうかを判定する。条件が成立する場合、ステップ８０７へ行く。条件が成立しない場合、ステップ８０５へ行く（８０４）。
【０１４８】
拡張可否判定部４２３は、Σｊ＝ｕＬｄ０［ｊ］≠０かつΣｊ＝ｕＬ１［ｊ］≠０であるかどうかを判定する。条件が成立する場合、ステップ８０６へ行く。条件が成立しない場合、ステップ８０７へ行く（８０５）。
【０１４９】
拡張可否判定部４２３は、ｅｘｐａｎｄ（ｄ０）、ｅｘｐａｎｄ（ｄ１）が計算可能と判定する（８０６）。
【０１５０】
拡張可否判定部４２３は、ｅｘｐａｎｄ（ｄ０）、ｅｘｐａｎｄ（ｄ１）が計算不可能と判定する（８０７）。
【０１５１】
図９を用いて、ステップ５０９、ステップ５１４、ステップ５１８で、拡張部４２４が、ｅｘｐａｎｄ（ｄ）を計算する方法（ｅｘｐａｎｓｉｏｎ）を説明する。具体的には、数値列ｄ，ビット位置ｕ，Ｌの入力に対し、数値列ｄにおいてビット位置ｕからビット位置Ｌまでで構成される数値列に対して、それに対応する０無し表現を生成し出力する。０無し表現とは、０を用いない数値列表現である。例えば、符号付２進表現（１，０，０，−１）に対して、その０無し表現は（１，−１，−１，１）である。
【０１５２】
拡張部４２４は、拡張可否判定部４２３が拡張可能と判定した場合に行う処理である。
【０１５３】
拡張部４２４は、ｄ，Ｌ，ｕを入力として受け取り、ｊにｕを代入する（９０１）。
【０１５４】
拡張部４２４は、ｊ＝Ｌであるかどうかを判定する。条件が成立する場合、ステップ９１７へ行く。条件が成立しない場合、ステップ９０３へ行く（９０２）。
【０１５５】
ｋにｊ＋１を代入する（９０３）。
【０１５６】
拡張部４２４は、ｄ［ｊ］≠０かつｄ［ｋ］＝０であるかどうかを判定する。条件が成立する場合、ステップ９０５へ行く。条件が成立しない場合、ステップ９１６へ行く（９０４）。
【０１５７】
拡張部４２４は、ｄ［ｋ］＝０かつｋ＜Ｌであるかどうかを判定する。条件が成立する場合、ステップ９０６へ行く。条件が成立しない場合、ステップ９０７へ行く（９０５）。
【０１５８】
ｋにｋ＋１を代入し、ステップ９０５へ行く（９０６）。
【０１５９】
拡張部４２４は、ｄ［ｋ］＝０であるかどうかを判定する。条件が成立する場合、ステップ９０８へ行く。条件が成立しない場合、ステップ９１２へ行く（９０７）。
【０１６０】
ｉにｊを代入する（９０８）。
【０１６１】
拡張部４２４は、ｉ＝ｋであるかどうか判定する。条件が成立する場合、ステップ９１１へ行く。条件が成立しない場合、ステップ９１０へ行く（９０９）。
【０１６２】
ｄ［ｉ］に−ｄ［ｊ］、ｉにｉ＋１をそれぞれ代入し、ステップ９０９へ行く（９１０）。
【０１６３】
ｄ［ｉ］にｄ［ｉ−１］を代入し、ステップ９１６へ行く（９１１）。
【０１６４】
ｉにｊを代入する（９１２）。
【０１６５】
拡張部４２４は、ｉ＝ｋ−１であるかどうかを判定する。条件が成立する場合、ステップ９１５へ行く。条件が成立しない場合、ステップ９１４へ行く（９１３）。
【０１６６】
ｄ［ｉ］に−ｄ［ｊ］、ｉにｉ＋１をそれぞれ代入し、ステップ９１３へ行く（９１４）。
【０１６７】
ｄ［ｉ］にｄ［ｉ−１］を代入し、ステップ９１６へ行く（９１５）。
【０１６８】
ｊにｋを代入し、ステップ９０２へ行く（９１６）。
【０１６９】
拡張部４２４は、ｅｘｐａｎｄ（ｄ）を出力する（９１７）。
【０１７０】
次に、図１０を用いて、前計算部４０３が楕円曲線上の点から、前計算テーブルを作成する方法（ｐｒｅｃｏｍｐｕｔａｔｉｏｎ）を説明する。前計算テーブルは、点ａＰ０＋ｂＰ１（ただし、１≦ａ≦３なる奇数および０、−３≦ｂ≦３なる奇数および０で、ａ，ｂ双方が０の場合等を除く）の１２個の点からなる。Ｐ０，Ｐ１以外の残りの１０個の点Ｑ０，Ｑ１，…，Ｑ９にはそれぞれ、Ｑ０＝３Ｐ０，Ｑ１＝３Ｐ１，Ｑ２＝Ｐ０＋Ｐ１，Ｑ３＝Ｐ０−Ｐ１，Ｑ４＝３Ｐ０＋Ｐ１，Ｑ５＝３Ｐ０−Ｐ１，Ｑ６＝Ｐ０＋３Ｐ１，Ｑ７＝Ｐ０−３Ｐ１，Ｑ８＝３Ｐ０＋３Ｐ１，Ｑ９＝３Ｐ０−３Ｐ１が格納される。
【０１７１】
前計算部４０３は点Ｐ０、Ｐ１を入力として受け取る（１００１）。
【０１７２】
２倍算部４３２は、点Ｐ０、Ｐ１の２倍点（ＥＣＤＢＬ（Ｐ０）、ＥＣＤＢＬ（Ｐ１））を計算し、その結果をＱ８、Ｑ９にそれぞれ代入する（１００２）。
【０１７３】
加算部４３１は、点Ｐ０と点Ｑ８の加算（ＥＣＡＤＤ（Ｐ０，Ｑ８））を計算し、その結果をＱ０に、点Ｐ１と点Ｑ９の加算（ＥＣＡＤＤ（Ｐ１，Ｑ９））を計算し、その結果をＱ１にそれぞれ代入する（１００３）。
【０１７４】
加算部４３１は、点Ｐ０と点Ｐ１の加算（ＥＣＡＤＤ（Ｐ０，Ｐ１））を計算し、その結果をＱ２に、点Ｐ０と点−Ｐ１の加算（ＥＣＡＤＤ（Ｐ０，−Ｐ１））を計算し、その結果をＱ３にそれぞれ代入する（１００４）。
【０１７５】
加算部４３１は、点Ｑ２と点Ｑ８の加算（ＥＣＡＤＤ（Ｑ２，Ｑ８））を計算し、その結果をＱ４に、点Ｑ３と点Ｑ８の加算（ＥＣＡＤＤ（Ｑ３，Ｑ８））を計算し、その結果をＱ５に、点Ｑ２と点Ｑ９の加算（ＥＣＡＤＤ（Ｑ２，Ｑ９））を計算し、その結果をＱ６に、点Ｑ３と点−Ｑ９の加算（ＥＣＡＤＤ（Ｑ３，−Ｑ９））を計算し、その結果をＱ７にそれぞれ代入する（１００５）。
【０１７６】
加算部４３１は、点Ｑ６と点Ｑ８の加算（ＥＣＡＤＤ（Ｑ５，Ｑ８））を計算し、その結果をＱ９に、点Ｑ６と点Ｑ８の加算（ＥＣＡＤＤ（Ｑ６，Ｑ８））を計算し、その結果をＱ８にそれぞれ代入する（１００６）。
【０１７７】
前計算部４０３は、前計算テーブルを出力する（１００７）。
【０１７８】
加算は式１、２を用いて、２倍算は式４、５を用いてそれぞれ計算される。
【０１７９】
なお、加算、２倍算の計算には式１、２、及び、式４、５を用いる以外にも、射影座標やヤコビアン座標における計算公式がある。
【０１８０】
また、楕円曲線上の点Ｐ＝（ｘ，ｙ）に対して、楕円曲線加算に関する逆元の点−Ｐはワイエルシュトラス型楕円曲線の場合、−Ｐ＝（ｘ，−ｙ）と表されるため、点Ｐの座標が与えられていれば容易に計算できる。そのため、点Ｑ０，Ｑ１，…，Ｑ９のみを前計算テーブルとして格納する。その後の実計算部３０４が行う計算で必要となる点−Ｑ０，−Ｑ１，…，−Ｑ９は、それらから導出すればよく、前計算テーブルには格納する必要はない。
【０１８１】
なお、点−Ｑ０，−Ｑ１，…，−Ｑ９の導出を省くために、それらの点のｙ座標の値のみを前計算テーブルに格納しておいてもよい。
【０１８２】
なお、前計算部４０３の行う前計算テーブルの作成処理は、点Ｑ０，Ｑ１，…，Ｑ９が計算されればよい。そのため、Ｃｏｈｅｎ，Ｈ．，Ａ  ｃｏｕｒｓｅ  ｉｎ  ｃｏｍｐｕｔａｔｉｏｎａｌ  ａｌｇｅｂｒａｉｃ  ｎｕｍｂｅｒ  ｔｈｅｏｒｙ，ＧＴＭ１３８，Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，（１９９３）の４８１ページにあるモンゴメリトリックによる逆元演算共通化方法を用いて、楕円曲線演算で必要となる逆元演算の計算の共通化を行うことにより、高速化をはかってもよい。
【０１８３】
最後に、図１１を用いて、実計算部４０４がエンコードされたスカラー値、楕円曲線上の点及び前計算テーブルから、楕円曲線における多重スカラー倍点を計算する方法（ｍｕｌｔｉ−ｓｃａｌａｒ）を説明する。
【０１８４】
実計算部４０４は、Ｐ０，Ｐ１，Ｑ０，Ｑ１，…，Ｑ９，ｅ０，ｅ１を入力として受け取る（１１０１）。
ｓにｎ、Ｒに無限遠点Ｏをそれぞれ代入する（１１０２）。
【０１８５】
繰り返し判定部４４４は、ｓ≧０であるかどうかを判定する。条件が成立する場合、ステップ１１０４へ行く。条件が成立しない場合、ステップ１１０８へ行く（１１０３）。
【０１８６】
２倍算部４４３は、点Ｒの２倍点を計算し、その結果をＲに代入する（１１０４）。
【０１８７】
繰り返し判定部４４４は、ｅ０［ｓ］＝０かつｅ１［ｓ］＝０であるかどうかを判定する。条件が成立する場合、ステップ１１０７へ行く。条件が成立しない場合、ステップ１１０６へ行く（１１０５）。
【０１８８】
加算部４４２は、点Ｒと点ｅ０［ｓ］Ｐ０＋ｅ１［ｓ］Ｐ１を加算し、その結果をＲに代入する（１１０６）。なお、ｅ０［ｓ］，ｅ１［ｓ］は、式１５をみたす奇数ないしは０であるので、ｅ０［ｓ］Ｐ０＋ｅ１［ｓ］Ｐ１もしくは−（ｅ０［ｓ］Ｐ０＋ｅ１［ｓ］Ｐ１）のいずれかが、前計算テーブルに格納されている。
【０１８９】
ｓにｓ−１を代入し、ステップ１１０３へ戻る（１１０７）。
【０１９０】
実計算部４０４はＲを出力する（１１０８）。
【０１９１】
本実施例によれば、スカラー値のエンコード結果における非零濃度が約０．３６０６となる。非零濃度とは、上述の通り、（非零ビットの個数）／（ビット長）の漸近的な値を指す。なお、比零濃度の計算には、例えば、本実施例のアルゴリズムにおけるステップ５０３，５０６，５１１などの変換判定フローを状態遷移として表し、各状態においてｃｏｎｖｅｒｔ（ｄ）により出力されるビット列のビット長及び非零ビットの個数を用いて、有限マルコフ過程の理論を適用することにより求めることができる。
【０１９２】
非特許文献１の多重スカラー倍計算方法を用いた際の非零濃度は１／２であり、本実施例における非零濃度の方が小さいことがわかる。
【０１９３】
以上の通り、上記計算方法は、楕円曲線多重スカラー倍計算の高速性に優れるという特徴がある。
【０１９４】
＜多重スカラー倍計算部の実施例２＞
本実施例２では、図４で示される多重スカラー倍計算部１３５の機能ブロックを用いる。
【０１９５】
多重スカラー倍計算部１３５（図１の１３５）の構成は、実施例１と同様である。
【０１９６】
多重スカラー倍計算部１３５がスカラー値ｄ０、ｄ１、及び、楕円曲線上の点Ｐ０、Ｐ１から、楕円曲線における多重スカラー倍点ｄ０Ｐ０＋ｄ１Ｐ１を計算する第二の計算方法を説明する。実施例２では、多重スカラー倍計算を最上位ビットから最下位ビットに向けて（ｌｅｆｔ−ｔｏ−ｒｉｇｈｔ）処理することが可能である。ｌｅｆｔ−ｔｏ−ｒｉｇｈｔの計算を用いることにより、特殊な加算公式（ヤコビアン座標系においてＺ座標を１とするなど）を用いることによる高速化や、エンコード処理結果を一旦メモリに格納することなく直接楕円曲線演算を行うことによるメモリ使用量の削減などを行うことができる。
【０１９７】
多重スカラー倍計算部１３５が署名検証処理部１３２からスカラー値ｄ０、ｄ１と楕円曲線上の点Ｐ０、Ｐ１を受け取ると、エンコード部４０２は、入力されたスカラー値ｄ０、ｄ１を
ｅ０＝（ｅ０［ｎ］ｅ０［ｎ−１］…ｅ０［０］）          （式１７）
ｅ１＝（ｅ１［ｎ］ｅ１［ｎ−１］…ｅ１［０］）          （式１８）
にエンコードする。ただし、各ｉ，ｊに対して、ｅｉ［ｊ］は式１５を満たす奇数もしくは０である。
【０１９８】
前計算部４０３は、入力された楕円曲線上の点Ｐ０、Ｐ１からから、前計算テーブルを作成する。前計算テーブル作成方法は実施例１と同様である。
【０１９９】
実計算部４０４は、エンコードされた２つのスカラー値と楕円曲線上の点Ｐ、Ｑから、前計算テーブルを用いて多重スカラー倍点ｄ０Ｐ０＋ｄ１Ｐ１を計算する。多重スカラー倍計算方法は実施例１と同様である。
【０２００】
本実施例でも、エンコード処理のフローチャートでサブルーチン（ｃａｌ（ｄ０，ｄ１，ｕ，Ｌ，ｃ）、ｃｏｎｖｅｒｔ（ｄ））を呼び出す処理があり、これらの処理は実施例１と同様である。
【０２０１】
次にエンコード部４０２、前計算部４０３、実計算部４０４の行う各処理について詳細に説明する。まず、図１２を用いて、エンコード部４０２がスカラー値ｄ１、ｄ２をｅ０，ｅ１にエンコードする方法（ｅｎｃｏｄｉｎｇ）を説明する。ここでは、ｗは３、数値列数（ｋ）は２、処理は最上位ビットから最下位ビットに向けて（ｌｅｆｔ−ｔｏ−ｒｉｇｈｔ）行う。
【０２０２】
エンコード部４０２は、受け取った入力ｄ０，ｄ１に対して連続する２ビットに対する減算を行い各々のＭＯＦ表現を計算し、それぞれｅ０，ｅ１に格納し、ｅ０［−１］に０、ｅ１［−１］に０、ｕにｎ−１、ｃに１をそれぞれ代入する（１２０１）。
【０２０３】
繰り返し判定部４２５は、ｕ＞０であるかどうかを判定する。条件が成立する場合は、ステップ１２０３へ行く。条件が成立しない場合は、ステップ１２１８へ行く（１２０２）。
【０２０４】
繰り返し判定部４２５は、ｅ０［ｕ］＝０かつｅ１［ｕ］であるかどうかを判定する。条件が成立する場合は、ステップ１２０４へ行く。条件が成立しない場合は、ステップ１２０５へ行く（１２０３）［一桁チェック］。
【０２０５】
ｕにｕ−１、ｃに１をそれぞれ代入し、ステップ１２０２へ行く（１２０４）。
【０２０６】
Ｌにｕ−（ｃ＋１）を代入し、数値計算部４２１は、ｚｕ，Ｌ＝ｃａｌ（ｅ０，ｅ１，ｕ，Ｌ，ｃ）を計算する（１２０５）［二桁（ｃ＝０）ないしは三桁（ｃ＝１）チェック］。
【０２０７】
繰り返し判定部４２５は、Ｌ≦０、または、ｃ＝０かつｚｕ，Ｌ∈｛（１０），（０１）｝、または、ｃ＝１かつｚｕ，Ｌ∈｛（１０１），（１１０），（０１１）｝であるかどうかを判定する。条件が成立する場合は、ステップ１２０７へ行く。条件が成立しない場合は、ステップ１２０８へ行く（１２０６）。
【０２０８】
数値変換部４２２は、ｃｏｎｖｅｒｔ（ｅ０）、ｃｏｎｖｅｒｔ（ｅ１）を計算し、ｕにｕ−（ｃ＋２）、ｃに１をそれぞれ代入し、ステップ１２０２へ行く（１２０７）。
【０２０９】
Ｌにｕ−（ｃ＋３）を代入し、数値計算部４２１は、ｚｕ，Ｌ＝ｃａｌ（ｅ０，ｅ１，ｕ，Ｌ，ｃ）を計算する（１２０８）［四桁（ｃ＝０）ないしは五桁（ｃ＝１）チェック］。
【０２１０】
繰り返し判定部４２５は、ｃ＝０かつｚｕ，Ｌ＝（１０１０）、または、ｃ＝１かつｚｕ，Ｌ＝（１１０１０）であるかどうかを判定する。条件が成立する場合は、ステップ１２１０へ行く。条件が成立しない場合は、ステップ１２１１へ行く（１２０９）。
【０２１１】
数値変換部４２２は、ｃｏｎｖｅｒｔ（ｅ０）、ｃｏｎｖｅｒｔ（ｅ１）を計算し、ｕにｕ−（ｃ＋４）、ｃに１をそれぞれ代入し、ステップ１２０２へ行く（１２１０）。
【０２１２】
Ｌにｕ−（ｃ＋２）を代入し、数値計算部４２１は、ｚｕ，Ｌ＝ｃａｌ（ｅ０，ｅ１，ｕ，Ｌ，ｃ）を計算する（１２１１）［三桁（ｃ＝０）ないしは四桁（ｃ＝１）チェック］。
【０２１３】
τ０［１］にｅ０［Ｌ＋１］、τ０［０］にｅ０［Ｌ］、τ１［１］にｅ１［Ｌ＋１］、τ１［０］にｅ１［Ｌ］をそれぞれ代入し、数値変換部４２２は、ｃｏｎｖｅｒｔ（ｅ０）、ｃｏｎｖｅｒｔ（ｅ１）を計算する（１２１２）。
【０２１４】
繰り返し判定部４２５は、ｅ０［Ｌ＋１］＝τ０［１］かつｅ０［Ｌ］＝τ０［０］かつｅ１［Ｌ＋１］＝τ１［１］かつｅ１［Ｌ］＝τ１［０］であるかどうかを判定する。条件が成立する場合は、ステップ１２１４へ行く。条件が成立しない場合、ステップ１２１５へ行く（１２１３）。
【０２１５】
ｕにｕ−（ｃ＋１）、ｃに１をそれぞれ代入し、ステップ１２０２へ行く（１２１４）。
【０２１６】
繰り返し判定部４２５は、ｅ０［Ｌ］≠±３かつｅ１［Ｌ］≠±３であるかどうかを判定する。条件が成立する場合、ステップ１２１６へ行く。条件が成立しない場合、ステップ１２１７へ行く（１２１５）。
【０２１７】
ｕにｕ−（ｃ＋２）、ｃに０をそれぞれ代入し、ステップ１２０２へ行く（１２１６）。
【０２１８】
ｕにｕ−（ｃ＋３）、ｃに１をそれぞれ代入し、ステップ１２０２へ行く（１２１７）。
【０２１９】
エンコード部４０２は、ｅ０とｅ１を出力する（１２１８）。
【０２２０】
前計算部４０３が楕円曲線上の点から、前計算テーブルを作成する方法は、実施例１と同様である。
【０２２１】
加算は式１、式２を用いて、２倍算は式４、式５を用いてそれぞれ計算される。
【０２２２】
なお、加算、２倍算の計算には式１、式２、及び、式４、式５を用いる以外にも、射影座標やヤコビアン座標における計算公式がある。
【０２２３】
また、点−Ｑ０，−Ｑ１，…，−Ｑ９を前計算テーブルには格納する必要がない理由、点Ｑ０，Ｑ１，…，Ｑ９の導出を省くために、それらの点のｙ座標の値のみを前計算テーブルに格納しておいてもよい理由、及び、モンゴメリトリックによる逆元演算共通化方法を用いて、楕円曲線演算で必要となる逆元演算の計算の共通化を行うことにより、高速化をはかってもよい理由も実施例１と同様である。
【０２２４】
実計算部４０４がエンコードされたスカラー値、楕円曲線上の点及び前計算テーブルから、楕円曲線における多重スカラー倍点を計算する方法は実施例１と同様である。
【０２２５】
本実施例によれば、スカラー値のエンコード結果における非零濃度は２３９／６６１≒０．３６１５となり、非特許文献１の多重スカラー倍計算方法を用いた際の非零濃度１／２より小さいことがわかる。
【０２２６】
以上の通り、上記計算方法は、楕円曲線多重スカラー倍計算の高速性に優れるという特徴がある。
【０２２７】
＜多重スカラー倍計算部の実施例３＞
実施例３では、図４で示される多重スカラー倍計算部１３５の機能ブロックを用いる。多重スカラー倍計算部１３５（図１の１３５）は、実施例１、及び、実施例２と同様である。
【０２２８】
多重スカラー倍計算部１３５がスカラー値ｄ０、ｄ１、…、ｄｋ−１及び、楕円曲線上の点Ｐ０、Ｐ１、…、Ｐｋ−１から、楕円曲線における多重スカラー倍点ｄ０Ｐ０＋ｄ１Ｐ１＋…＋ｄｋ−１Ｐｋ−１を計算する計算方法を説明する。
【０２２９】
実施例３では、ウィンドウ幅ｗ＝２の場合にスカラー値及び楕円曲線上の点の個数がｋ個の場合に多重スカラー倍計算を行なうことが可能である。したがって、スカラー値及び楕円曲線上の点の個数が一般の場合でも多重スカラー倍計算を行なうことが可能である。また、多重スカラー倍計算を最上位ビットから最下位ビットに向けて（ｌｅｆｔ−ｔｏ−ｒｉｇｈｔ）処理することが可能であり、処理速度およびメモリ使用量の観点で優れる。
【０２３０】
多重スカラー倍計算部１３５が署名検証処理部１３２からスカラー値ｄ０、ｄ１、…、ｄｋ１と楕円曲線上の点Ｐ０、Ｐ１、…、Ｐｋ−１を受け取ると、エンコード部４０２は、入力されたスカラー値ｄ０、ｄ１、…、ｄｋ１を
ｅ０＝（ｅ０［ｎ］ｅ０［ｎ−１］…ｅ０［０］）
ｅ１＝（ｅ１［ｎ］ｅ１［ｎ−１］…ｅ１［０］）
・・・
ｅｋ−１＝（ｅｋ−１［ｎ］ｅｋ−１［ｎ−１］…ｅｋ−１［０］）
にエンコードする。ただし、各ｉ，ｊに対して、ｅｉ［ｊ］は、ｅｉ［ｊ］＝−１，０，１のいずれかの値である（すなわち、式１５でｗ＝２の場合である）。
【０２３１】
前計算部４０３は、入力されたｋ個の楕円曲線上の点Ｐ０、Ｐ１、…、Ｐｋ−１から、前計算テーブルを作成する。前計算テーブルは点ａ０Ｐ０＋ａ１Ｐ１＋…＋ａｋ−１Ｐｋ−１により構成される。ここで、ａ０，ａ１，…，ａｋ−１は、−１，０，１のいずれか（ただしａ０，ａ１，…，ａｋ−１全てが０の場合を除く。ａ０’Ｐ０＋ａ１’Ｐ１＋…＋ａｋ−１’Ｐｋ−１＝−（ａ０Ｐ０＋ａ１Ｐ１＋…＋ａｋ−１Ｐｋ−１）となるａ０’Ｐ０＋ａ１’Ｐ１＋…＋ａｋ−１’Ｐｋ−１は格納しなくとも良い）である。
【０２３２】
実計算部４０４は、エンコードされたｋ個のスカラー値ｄ０、ｄ１、…、ｄｋ−１をエンコードした数値列ｅ０、ｅ１、…、ｅｋ−１及び楕円曲線上の点Ｐ０、Ｐ１、…、Ｐｋ−１から、前計算テーブルを用いて多重スカラー倍点ｄ０Ｐ０＋ｄ１Ｐ１＋…＋ｄｋ−１Ｐｋ−１を計算する。
【０２３３】
なお、本実施例では、エンコード処理のフローチャートでサブルーチンを呼び出す処理があり、上記処理については、図１４，１５で説明する。呼び出されるサブルーチンは全部で２つあり、０の項が生成可能なビット位置を返すサブルーチンｃａｌ（ｄ０，ｄ１，…，ｄｋ−１，ｕ，Ｌ）、０の項が生成可能なビット位置に関する情報に基づき実際に変換を行うサブルーチンｃｏｎｖｅｒｔ（ｄ）である。
【０２３４】
次にエンコード部４０２、前計算部４０３、実計算部４０４の行う各処理について詳細に説明する。まず、図１３〜図１５を用いて、エンコード部４０２がｋ個のスカラー値ｄ０、ｄ１、…、ｄｋ−１をエンコードする方法を説明する。図１３は、本実施例のエンコード処理（ｅｎｃｏｄｉｎｇ）を説明するための図である。ここでは、ｗは２、数値列数（ｋ）は特に限定されず、処理は最上位ビットから最下位ビットに向けて（ｌｅｆｔ−ｔｏ−ｒｉｇｈｔ）行う。
【０２３５】
エンコード部４０２は、受け取った入力ｄ０，ｄ１，…，ｄｋ−１に対して連続する２ビットに対する減算を行い各々のＭＯＦ表現を計算し、それぞれｅ０，ｅ１，…，ｅｋ−１に格納し、ｕにｎ−１を代入する（１３０１）。
【０２３６】
繰り返し判定部４２５は、０≦ｕであるかどうかを判定する。条件が成立する場合、ステップ１３０３へ行く。条件が成立しない場合、ステップ１３１４へ行く（１３０２）。
【０２３７】
繰り返し判定部４２５は、ｅ０［ｕ］＝０かつｅ１［ｕ］＝０かつ…かつｅｋ−１［ｕ］＝０であるかどうかを判定する。条件が成立する場合、ステップ１３０６へ行く。条件が成立しない場合、１３０４へ行く（１３０３）［一桁チェック］。
【０２３８】
ｉに２を代入する（１３０４）。
【０２３９】
繰り返し判定部４２５は、ｉ≦ｋ＋１であるかどうかを判定する。条件が成立する場合、ステップ１３０７へ行く。条件が成立しない場合、ステップ１３０６へ行く（１３０５）。
【０２４０】
ｕにｕ−１を代入し、ステップ１３０２へ行く（１３０６）。
【０２４１】
Ｌに０を代入する（１３０７）。
【０２４２】
繰り返し判定部４２５は、０≦ｕ−ｉ＋１であるかどうかを判定する。条件が成立する場合、ステップ１３０９へ行く。条件が成立しない場合、ステップ１３１０へ行く（１３０８）［複数桁（ｉ桁）チェック］。
【０２４３】
Ｌにｕ−ｉ＋１を代入する（１３０９）。
【０２４４】
数値計算部４２１は、ｚ＝ｃａｌ（ｅ０，ｅ１，…，ｅｋ−１，ｕ，Ｌ）を計算する（１３１０）。
【０２４５】
繰り返し判定部４２５は、ｚ≠−１であるかどうかを判定する。条件が成立する場合、ステップ１３１２へ行く。条件が成立しない場合、ステップ１３１３へ行く（１３１１）。
【０２４６】
数値変換部４２２は、ｃｏｎｖｅｒｔ（ｅ０）、ｃｏｎｖｅｒｔ（ｅ１）、…、ｃｏｎｖｅｒｔ（ｅｋ−１）を計算し、ｕにｕ−ｉを代入し、ステップ１３０２へ行く（１３１２）。
【０２４７】
ｉにｉ＋１を代入し、ステップ１３０５へ行く（１３１３）。
【０２４８】
エンコード部４０２は、ｅ０［０］、…、ｅ０［ｎ−１］、ｅ１［０］、…、ｅ１［ｎ−１］、ｅｋ−１［０］、…、ｅｋ−１［ｎ−１］を出力する（１３１４）。
【０２４９】
図１４を用いて、ステップ１３１０において数値計算部４２１がｚ＝ｃａｌ（ｄ０，ｄ１，…，ｄｋ−１，ｕ，Ｌ）を計算する方法（ｃａｌｃｕｌａｔｅ  ｚ）について説明する。
【０２５０】
数値計算部４２１は、与えられたｋ個のスカラー値ｄ０，ｄ１，…，ｄｋ−１においてビット位置ｕからビット位置Ｌまでのビット列に対して、どのビット位置で０の項を生成できるかを示す数値ｚを出力する。数値ｚは、ビット位置Ｌを基点とした相対ビット位置で０の項を生成できることを示し、ｚ＝−１の場合は０の項が生成できないことを示す。
【０２５１】
数値計算部４２１は、ｄ０，ｄ１，…，ｄｋ−１を入力として受け取り、ｉに０を代入する（１４０１）。
【０２５２】
数値計算部４２１は、ｉ＜ｋであるかどうかを判定する。条件が成立する場合、ステップ１４０３へ行く。条件が成立しない場合、ステップ１４１０へ行く（１４０２）。
【０２５３】
ｆｉに−１を代入する（１４０３）。ｆｉは、ｄｉがどの相対ビット位置で０とすることができないかを示す相対ビット位置を示す変数である。
【０２５４】
ｊにｕ−Ｌを代入する（１４０４）。
【０２５５】
数値計算部４２１は、０≦ｊであるかどうかを判定する。条件が成立する場合、ステップ１４０７へ行く。条件が成立しない場合、ステップ１４０６へ行く（１４０５）。
【０２５６】
ｉにｉ＋１を代入し、ステップ１４０２へ行く（１４０６）。
【０２５７】
数値計算部４２１は、ｄｉ［ｊ＋Ｌ］≠０であるかどうかを判定する。条件が成立する場合、ステップ１４０８へ行く。条件が成立しない場合、ステップ１４０９へ行く（１４０７）。
【０２５８】
ｆｉにｊを代入する（１４０８）。
【０２５９】
ｊにｊ−１を代入し、ステップ１４０５へ行く（１４０９）。
【０２６０】
ｚにｕ−Ｌを代入する（１４１０）。
【０２６１】
数値計算部４２１は、０≦ｚであるかどうかを判定する。条件が成立する場合、ステップ１４１２へ行く。条件が成立しない場合、ステップ１４１９へ行く（１４１１）。
【０２６２】
ｂに１、ｉに０をそれぞれ代入する（１４１２）。ｂは、変数ｚが示す相対位置で０の項が生成できるかどうかを示すフラグである。ｂ＝１は生成可能、ｂ＝０は生成不可能を示す。
【０２６３】
数値計算部４２１は、ｉ＜ｋであるかどうかを判定する。条件が成立する場合、ステップ１４１４へ行く。条件が成立しない場合、ステップ１４１７へ行く（１４１３）。
【０２６４】
数値計算部４２１は、ｚ＝ｆｉであるかどうかを判定する。条件が成立する場合、ステップ１４１５へ行く。条件が成立しない場合、ステップ１４１６へ行く（１４１４）。
【０２６５】
ｂに０を代入する（１４１５）。
【０２６６】
ｉにｉ＋１を代入し、ステップ１４１３へ行く（１４１６）。
【０２６７】
数値計算部４２１は、ｂ＝１であるかどうかを判定する。条件が成立する場合、ステップ１４２０へ行く。条件が成立しない場合、ステップ１４１８へ行く（１４１７）。
【０２６８】
ｚにｚ−１を代入し、ステップ１４１１へ行く（１４１８）。
【０２６９】
数値計算部４２１は、−１を出力する（１４１９）。
【０２７０】
数値計算部４２１は、ｚを出力する（１４２０）。
【０２７１】
図１５を用いて、ステップ１３１２において、数値変換部４２２がｃｏｎｖｅｒｔ（ｄ０）、ｃｏｎｖｅｒｔ（ｄ１）、…、ｃｏｎｖｅｒｔ（ｄｋ−１）を計算する方法（ｃｏｎｖｅｒｓｉｏｎ）について説明する。数値変換部４２２は、与えられたビット列ｄ０，ｄ１，…，ｄｋ−１を、ｃａｌ（ｄ０，ｄ１，…，ｄｋ−１，ｕ，Ｌ）の出力した相対ビット位置ｚにおいて、０の項となる数値列ｄ０，ｄ１，…，ｄｋ−１に変換する。以下の処理においては、０の項に変換すべきビット位置（次の部分ビット列の左端のビット）において、１００…０（−１）を０１１…１１、（−１）００…０１を０（−１）（−１）…（−１）（−１）と変換する基本処理を繰り返すことにより達成している。
【０２７２】
数値変換部４２２は、ｄ０，ｄ１，…，ｄｋ−１，ｕ，Ｌ，ｚを入力として受け取り、ｊにｚ＋Ｌ、ｉに０を代入する（１５０１）。
【０２７３】
数値変換部４２２は、ｉ＜ｋであるかどうかを判定する。条件が成立する場合、ステップ１５０３へ行く。条件が成立しない場合、１５１２へ行く（１５０２）。
【０２７４】
数値変換部４２２は、ｄｉ［ｊ］≠０であるかどうかを判定する。条件が成立する場合、ステップ１５０４へ行く。条件が成立しない場合、１５１１へ行く（１５０３）。
【０２７５】
ｓにｊ＋１を代入する（１５０４）。
【０２７６】
数値変換部４２２は、ｄｉ［ｓ］＝０であるかどうかを判定する。条件が成立する場合、ステップ１５０６へ行く。条件が成立しない場合、１５０７へ行く（１５０５）。
【０２７７】
ｓにｓ＋１を代入する（１５０６）。
【０２７８】
ｔにｊ＋１を代入する（１５０７）。
【０２７９】
数値変換部４２２は、ｓ≦ｔであるかどうかを判定する。条件が成立する場合、ステップ１５０９へ行く。条件が成立しない場合、１５１０へ行く（１５０８）。
【０２８０】
ｄｉ［ｔ］にｄｉ［ｊ］、ｔにｔ＋１をそれぞれ代入する（１５０９）。
【０２８１】
ｄｉ［ｊ］に０を代入する（１５１０）。
【０２８２】
ｉにｉ＋１を代入する（１５１１）。
【０２８３】
数値変換部４２２は、ｄ０，ｄ１，…，ｄｋ−１を出力する（１５１２）。
【０２８４】
次に、図１６を用いて、前計算部４０３が楕円曲線上の点から、前計算テーブルを作成する方法（ｐｒｅｃｏｍｐｕｔａｔｉｏｎ）を説明する。前計算テーブルは、点ａ０Ｐ０＋ａ１Ｐ１＋…＋ａｋ−１Ｐｋ−１（ただし、ａ０，ａ１，…，ａｋ−１は、−１，０，１のいずれか）で構成される。前計算テーブルには、ｓ＝（ａ０，ａ１，…，ａｋ−１）に対して、点Ｑｓ＝ａ０Ｐ０＋ａ１Ｐ１＋…＋ａｋ−１Ｐｋ−１が格納される。
前計算部４０３は、点Ｐ０、Ｐ１、…、Ｐｋ−１を入力として受け取る（１６０１）。
【０２８５】
Ｓに｛０，±１｝ｋを代入する（１６０２）。
【０２８６】
繰り返し判定部４３３は、Ｓが空集合であるかどうかを判定する。条件が成立する場合、ステップ１６１０へ行く。条件が成立しない場合、ステップ１６０４へ行く（１６０３）。
【０２８７】
Ｓの元ｓ＝（ｓ［０］，…，ｓ［ｋ−１］）を一つ選ぶ（１６０４）。
【０２８８】
繰り返し判定部４３３は、Ｑ−ｓ＝ｎｕｌｌであるかどうかを判定する。すなわち、Ｑｓがまだ計算されていないかどうかを判定する。条件が成立する場合、ステップ１６０６へ行く。条件が成立しない場合、ステップ１６０９へ行く（１６０５）。
【０２８９】
ｉに０、ＱｓにＯをそれぞれ代入する（１６０６）。
【０２９０】
繰り返し判定部４３３は、ｉ≦ｋ−１であるかどうかを判定する。条件が成立する場合、ステップ１６０８へ行く。条件が成立しない場合、ステップ１６０９へ行く（１６０７）。
【０２９１】
加算部４３１は、点Ｑｓと点ｓ［ｊ］Ｐｊを加算（ＥＣＡＤＤ（Ｑｓ，ｓ［ｊ］Ｐｊ）し、その結果をＱｓに代入し、ｉ＋１をｉに代入する（１６０８）。
【０２９２】
Ｓから｛ｓ｝を除き、その集合をＳとする（１６０９）。
【０２９３】
前計算部４０３は、前計算テーブルを出力する（１６１０）。
【０２９４】
加算は式１、２を用いて、２倍算は式４、５を用いてそれぞれ計算される。
なお、加算、２倍算の計算には式１、２、及び、式４、５を用いる以外にも、射影座標やヤコビアン座標における計算公式がある。
【０２９５】
なお、前計算テーブルは、点ａ０Ｐ０＋ａ１Ｐ１＋…＋ａｋ−１Ｐｋ−１（ただし、ａ０，ａ１，…，ａｋ−１は、−１，０，１のいずれか）で構成されるが、ａ０’Ｐ０＋ａ１’Ｐ１＋…＋ａｋ−１’Ｐｋ−１＝−（ａ０Ｐ０＋ａ１Ｐ１＋…＋ａｋ−１Ｐｋ−１）となるａ０’Ｐ０＋ａ１’Ｐ１＋…＋ａｋ−１’Ｐｋ−１は格納しなくとも良いため、ａ０，ａ１，…，ａｉ−１がすべて０の場合はａｉ＝−１となるものは格納しなくともよい。また、ａ０，ａ１，…，ａｋ−１全てが０の場合についても格納しなくともよい。また、点−Ｑｓの導出を省くために、その点のｙ座標のみを前計算テーブルに格納しておいてもよい理由、モンゴメリトリックによる逆元演算共通化方法を用いて、楕円曲線演算で必要となる逆元演算の計算の共通化を行うことにより、高速化をはかってもよい理由、及び、点Ｐが固定点である場合、点Ｑｓを再計算する必要がない理由は、実施例１、及び、実施例２と同様である。
【０２９６】
最後に、図１７を用いて、実計算部４０４がエンコードされたスカラー値、楕円曲線上の点及び前計算テーブルから、楕円曲線における多重スカラー倍点を計算する方法（ｍｕｌｔｉ−ｓｃａｌａｒ）を説明する。
【０２９７】
実計算部４０４は、楕円曲線上の点Ｐ０、Ｐ１、…、Ｐｋ−１、事前計算テーブルＱｓ、エンコードされたスカラー値ｅ０、ｅ１、…、ｅｋ−１を入力として受け取る（１７０１）。
【０２９８】
ｓにｎ、Ｒに０をそれぞれ代入する（１７０２）。
繰り返し判定部４４４は、０≦ｓであるかどうかを判定する。条件が成立する場合、ステップ１７０４へ行く。条件が成立しない場合、ステップ１７０９へ行く（１７０３）。
【０２９９】
２倍算部４４３は、点Ｒの２倍点（ＥＣＤＢＬ（Ｒ））を計算し、その結果をＲに代入する（１７０４）。
【０３００】
繰り返し判定部４４４は、Ｑ（ｅ０［ｓ］，…，ｅｋ−１［ｓ］）＝ｎｕｌｌであるかどうかを判定する。すなわち事計算テーブルに点Ｑｓが格納されているかどうかを判定する。条件が成立する場合、ステップ１７０６へ行く。条件が成立しない場合、ステップ１７０７へ行く（１７０５）。
【０３０１】
加算部４４２は、点Ｒと点−Ｑ（ｅ０［ｓ］，…，ｅｋ−１［ｓ］）を加算（ＥＣＡＤＤ（Ｒ，−Ｑ（ｅ０［ｓ］，…，ｅｋ−１［ｓ］））し、その結果をＲに代入する（１７０６）。
【０３０２】
加算部４４２は、点Ｒと点Ｑ（ｅ０［ｓ］，…，ｅｋ−１［ｓ］）を加算（ＥＣＡＤＤ（Ｒ，Ｑ（ｅ０［ｓ］，…，ｅｋ−１［ｓ］））し、その結果をＲに代入する（１７０７）。
【０３０３】
ｓにｓ−１を代入する（１７０８）。
【０３０４】
実計算部４０４は、点Ｒを出力する（１７０９）。
【０３０５】
この場合、非零濃度が１−（１／ｃｋ−１）となることが、Ｊ．Ｐｒｏｏｓ，”Ｊｏｉｎｔ  Ｓｐａｒｓｅ  Ｆｏｒｍｓ  ａｎｄ  Ｇｅｎｅｒａｔｉｏｎｇ  Ｚｅｒｏ  Ｃｏｌｕｍｎｓ  ｗｈｅｎ  Ｃｏｍｂｉｎｇ”，Ｔｅｃｈｎｉｃａｌ  Ｒｅｐｏｒｔ  ｏｆ  ＣＡＣＲ，ＣＯＲＲ２００３−２３，Ｕｎｉｖｅｒｓｉｔｙ  ｏｆ  Ｗａｔｅｒｌｏｏ，２００３．＜ＵＲＬ＞ｈｔｔｐ：／／ｗｗｗ．ｃａｃｒ．ｍａｔｈ．ｕｗａｔｅｒｌｏｏ．ｃａ／ｔｅｃｈｒｅｐｏｒｔｓ／２００３／ｃｏｒｒ２００３−２３．ｐｓに記載されている。
【０３０６】
ここで、ｃｋ−１＝（１／２ｋ−１）＊（３＋Σｉ＝１ｋ−１ｋＣｉ（ｃｉ＋１））であり、ｋＣｉは、ｋ個の異なるものからｉ個を選ぶときの組み合わせの総数を表わす。
【０３０７】
以上の通り、上記計算方法は、楕円曲線多重スカラー倍計算の高速性に優れるという特徴がある。
【０３０８】
なお、上記において、実施例３は、多重スカラー倍計算を最上位ビットから最下位ビットに向けて（ｌｅｆｔ−ｔｏ−ｒｉｇｈｔ）処理するものとして説明したが、最下位ビットから最上位ビットに向けて（ｒｉｇｈｔ−ｔｏ−ｌｅｆｔ）処理することも可能である。
【０３０９】
＜多重スカラー倍計算部の実施例４＞
実施例４では、実施例２で説明したエンコード処理を最上位ビットから最下位ビットに向けて（ｌｅｆｔ−ｔｏ−ｒｉｇｈｔ）行う多重スカラー倍計算を用い、エンコード結果をメモリに格納することなく、直接多重スカラー倍計算を行う場合を説明する。
【０３１０】
実施例４では、図１８で示される多重スカラー倍計算部１３５の機能ブロックを用いる。多重スカラー倍計算部１３５は、前計算部１８０１、実計算部１８０２からなる。前計算部１８０１は、加算部１８１１、２倍算部１８１２、繰り返し判定部１８１３からなる。実計算部１８０２は、数値計算部１８２１、数値変換部１８２２、拡張可否判定部１８２３、拡張部１８２４、ビット値判定部１８２５、加算部１８２６、２倍算部１８２７、繰り返し判定部１８２８からなる。
【０３１１】
多重スカラー倍計算部１３５がスカラー値ｄ０、ｄ１及び、楕円曲線上の点Ｐ０、Ｐ１から、楕円曲線における多重スカラー倍点ｄ０Ｐ０＋ｄ１Ｐ１を計算する第四の計算方法を説明する。実施例４では、スカラー値をエンコードした値を格納することなく、直接、多重スカラー倍計算を計算できるという特徴がある。したがって、多重スカラー倍計算を行なう際に、エンコード結果を格納するメモリを節約することが可能である。
【０３１２】
前計算部１８０１は、入力された楕円曲線上の点Ｐ０、Ｐ１から、前計算テーブルを作成する。前計算テーブル作成方法は実施例１、及び、実施例２と同様である。
【０３１３】
実計算部１８０２は、２つのスカラー値と楕円曲線上の点Ｐ０、Ｐ１から、前計算テーブルを用いて多重スカラー倍点ｄ０Ｐ０＋ｄ１Ｐ１を計算する。
【０３１４】
次に、図１９、図２０を用いて、実計算部１８０２がスカラー値ｄ０、ｄ１、楕円曲線上の点Ｐ０、Ｐ１及び前計算テーブルＱから多重スカラー倍点ｄ０Ｐ０＋ｄ１Ｐ１を計算する方法（ｏｎ−ｔｈｅ−ｆｌｙ  ｍｕｌｔｉ−ｓｃａｌａｒ）を詳細に説明する。ここでは、ｗは３、数値列数（ｋ）は２、処理は最上位ビットから最下位ビットに向けて（ｌｅｆｔ−ｔｏ−ｒｉｇｈｔ）行う。
【０３１５】
実計算部１８０２は、Ｐ０，Ｐ１，ｄ０，ｄ１及び前計算テーブルＱを入力として受け取る（１９０１）。
【０３１６】
ｄ０［ｎ］に０、ｄ０［−１］に０、ｄ１［ｎ］に０、ｄ１［−１］に０、ｕにｎ、ｃに１、Ｒに無限遠点Ｏをそれぞれ代入する（１９０２）。
【０３１７】
繰り返し判定部１８２８は、ｕ＞０であるかどうかを判定する。条件が成立する場合、ステップ１９０４へ行く。条件が成立しない場合、ステップ１９１０へ行く（１９０３）。
【０３１８】
数値計算部１８２１、及び数値変換部１８２２は、（ｄ０，ｄ１，ｕ）を部分的にエンコードした表現（ｅ０，ｅ１，ｓ）を求める（１９０４）（（ｅ０，ｅ１，ｓ）＝ｅｎｃｏｄｅ（ｄ０，ｄ１，ｕ）；詳細は後述する。）。
【０３１９】
繰り返し判定部１８２８は、０≦ｓであるかどうかを判定する。条件が成立する場合、ステップ１９０６へ行く。条件が成立しない場合、ステップ１９０３へ行く（１９０５）。
【０３２０】
２倍算部１８２７は、点Ｒの２倍点（ＥＣＤＢＬ（Ｒ））を計算し、その結果をＲに代入する（１９０６）。
【０３２１】
繰り返し判定部１８２８は、ｅ０［ｓ］＝０かつｅ１［ｓ］＝０であるかどうかを判定する。条件が成立する場合、ステップ１９０９へ行く。条件が成立しない場合、ステップ１９０８へ行く（１９０７）。
【０３２２】
加算部１８２６は、点Ｒと点ｅ０［ｓ］Ｐ０＋ｅ１［ｓ］Ｐ１を加算（ＥＣＡＤＤ（Ｒ，ｅ０［ｓ］Ｐ０＋ｅ１［ｓ］Ｐ１））し、その結果をＲに代入する（１９０８）。なお、ｅ０［ｓ］，ｅ１［ｓ］は、式１５をみたす奇数ないしは０であるので、ｅ０［ｓ］Ｐ０＋ｅ１［ｓ］Ｐ１もしくは−（ｅ０［ｓ］Ｐ０＋ｅ１［ｓ］Ｐ１）のいずれかが、前計算テーブルに格納されている。
ｓにｓ−１を代入する（１９０９）。
【０３２３】
実計算部１８０２はＲを出力する（１９１０）。
【０３２４】
図２０を用いて、ステップ１９０４で、（ｄ０，ｄ１，ｕ）を部分的にエンコードした表現（ｅ０，ｅ１，ｓ）を求める方法（ｅｎｃｏｄｅ（ｄ０，ｄ１，ｕ）；ｅｎｃｏｄｉｎｇ）を説明する。ここでｅ０，ｅ１，はエンコード結果であり、ｓは何ビットエンコードしたかを示す数値である。また、この部分エンコード処理においては、この処理内でのみ用いる変数ｃ，τ０，τ１があり、処理終了後も値を保持し、次の処理においてそれらの値が用いられる。なお、明示的にそれらの値を入出力することにより、データの受け渡しを行ってもよい。また、本実施例でも、部分エンコード処理においてサブルーチン（ｃａｌ（ｄ０，ｄ１，ｕ，Ｌ，ｃ）、ｃｏｎｖｅｒｔ（ｄ））を呼び出す処理があり、これらの処理は実施例１、実施例２と同様である。
【０３２５】
（ｄ０，ｄ１，ｕ）を入力として受け取る（２００１）。
【０３２６】
繰り返し判定部１８２８は、ｄ０［ｕ］＝ｄ０［ｕ−１］かつｄ１［ｕ］＝ｄ１［ｕ−１］であるかどうかを判定する。条件が成立する場合、ステップ２００３へ行く。条件が成立しない場合、ステップ２００４へ行く（２００２）［一桁チェック］。
【０３２７】
ｅ０に０を、ｅ１に０を、ｕにｕ−１を、ｃに１を、ｓに０をそれぞれ代入し、ステップ２０２０へ行く（２００３）。
【０３２８】
Ｌにｕ−（ｃ＋１）を代入し、数値計算部１８２１は、ｚ＝ｃａｌ（ｅ０，ｅ１，ｕ，Ｌ，ｃ）を計算する（２００４）［二桁（ｃ＝０）ないしは三桁（ｃ＝１）チェック］。
【０３２９】
繰り返し判定部１８２８は、Ｌ≦０、または、ｃ＝０かつｚ∈｛（１０），（０１）｝、またはｃ＝１かつｚ∈｛（１０１），（１１０），（０１１）｝であるかどうかを判定する。条件が成立する場合、ステップ２００６へ行く。条件が成立しない場合、ステップ２００８へ行く（２００５）。
【０３３０】
ｅ０［ｕ−Ｌ］にｄ０［ｕ−１］−ｄ０［ｕ］を、…、ｅ０［０］にｅ０［Ｌ−１］−ｄ０［Ｌ］を、ｅ１［ｕ−Ｌ］にｄ１［ｕ−１］ｄ１［ｕ］を、…、ｅ１［０］にｄ１［Ｌ−１］ｄ１［Ｌ］をそれぞれ代入する（２００６）［ＭＯＦ表現への変換］。
【０３３１】
ｅ０［ｕ−Ｌ＋ｃ］にτ０を、ｅ１［ｕ−Ｌ＋ｃ］にτ１を代入し、数値変換部１８２２は、ｃｏｎｖｅｒｔ（ｅ０，ｅ１，ｕ，Ｌ，ｚ）を計算し、その結果を（ｅ０，ｅ１）に格納する。さらに、ｕにｕ−（ｃ＋２）を、ｃに１を、ｓにｕ−Ｌをそれぞれ代入し、ステップ２０２０へ行く（２００７）。
【０３３２】
Ｌにｕ−（ｃ＋３）を代入し、数値計算部１８２１は、ｚ＝ｃａｌ（ｅ０，ｅ１，ｕ，Ｌ，ｃ）を計算する（２００８）［四桁（ｃ＝０）ないしは五桁（ｃ＝１）チェック］。
【０３３３】
繰り返し判定部１８２８は、ｃ＝０かつｚ＝（１０１０）、または、ｃ＝１かつｚ＝（１１０１０）であるかどうかを判定する。条件が成立する場合、ステップ２０１０へ行く。条件が成立しない場合、ステップ２０１２へ行く（２００９）。
【０３３４】
ｅ０［ｕ−Ｌ］にｄ０［ｕ−１］−ｄ０［ｕ］を、…、ｅ０［０］にｄ０［Ｌ−１］−ｄ０［Ｌ］を、ｅ１［ｕ−Ｌ］にｄ１［ｕ−１］−ｄ１［ｕ］を、…、ｅ１［０］にｄ１［Ｌ−１］−ｄ１［Ｌ］をそれぞれ代入する（２０１０）［ＭＯＦ表現への変換］。
【０３３５】
ｅ０［ｕ−Ｌ＋ｃ］にτ０を、ｅ１［ｕ−Ｌ＋ｃ］にτ１を代入し、数値変換部１８２２は、ｃｏｎｖｅｒｔ（ｅ０，ｅ１，ｕ，Ｌ，ｚ）を計算し、その結果を（ｅ０，ｅ１）に格納する。さらに、ｕにｕ−（ｃ＋４）を、ｃに１を、ｓにｕ−Ｌをそれぞれ代入し、ステップ２０２０へ行く（２０１１）。
【０３３６】
Ｌにｕ−（ｃ＋２）を代入し、数値計算部１８２１は、ｚ＝ｃａｌ（ｅ０，ｅ１，ｕ，Ｌ，ｃ）を計算する（２０１２）［三桁（ｃ＝０）ないしは四桁（ｃ＝１）チェック］。
【０３３７】
ｅ０［ｕ−Ｌ］にｄ０［ｕ−１］−ｄ０［ｕ］を、…、ｅ０［０］にｄ０［Ｌ−１］−ｄ０［Ｌ］を、ｅ１［ｕ−Ｌ］にｄ１［ｕ−１］−ｄ１［ｕ］を、…、ｅ１［０］にｄ１［Ｌ−１］−ｄ１［Ｌ］をそれぞれ代入する（２０１３）［ＭＯＦ表現への変換］。
【０３３８】
ｅ０［ｕ−Ｌ＋ｃ］にτ０を、ｅ１［ｕ−Ｌ＋ｃ］にτ１をそれぞれ代入し、数値変換部１８２２は、ｃｏｎｖｅｒｔ（ｅ０，ｅ１，ｕ，Ｌ，ｚ）を計算し、その結果を（ｅ０，ｅ１）に格納する（２０１４）。
【０３３９】
繰り返し判定部１８２８は、ｅ０［１］＝ｄ０［Ｌ＋１］かつｅ０［０］＝ｄ０［Ｌ］かつｅ１［１］＝ｄ０［Ｌ＋１］かつｅ１［０］＝ｄ１［Ｌ］であるかどうかを判定する。条件が成立する場合、ステップ２０１６へ行く。条件が成立しない場合、ステップ２０１７へ行く（２０１５）。
【０３４０】
ｕにｕ−（ｃ＋１）を、ｃに１を、ｓにｕ−Ｌをそれぞれ代入し、ステップ２０２０へ行く（２０１６）。
【０３４１】
繰り返し判定部１８２８は、ｅ０［０］≠±３かつｅ１［０］≠±３かつ（ｅ０［０］，ｅ１［０］）≠（０，０）であるかどうかを判定する。条件が成立する場合、ステップ２０１８へ行く。条件が成立しない場合、ステップ２０１９へ行く（２０１７）。
【０３４２】
ｕにｕ−（ｃ＋２）を、ｃに０を、ｓにｕ−Ｌを、τ０にｅ０［０］を、τ１にｅ１［０］をそれぞれ代入し、ステップ２０２０へ行く（２０１８）。
【０３４３】
ｕにｕ−（ｃ＋３）を、ｃに１を、ｓにｕ−Ｌをそれぞれ代入し、ステップ２０２０へ行く（２０１９）。
【０３４４】
部分エンコード結果として、ｅ０，ｅ１，ｓを出力する（２０２０）。
【０３４５】
なお、ステップ２００４、ステップ２００８、及び、ステップ２０１２において、数値計算部１８２１が、ｃａｌ（ｅ０，ｅ１，ｕ，Ｌ，ｃ）を計算する方法とステップ２００７、ステップ２０１１、及び、ステップ２０１４で数値変換部が、ｃｏｎｖｅｒｔ（ｅ０，ｅ１，ｕ，Ｌ，ｚ）を計算する方法は、実施例１及び実施例２と同様である。
【０３４６】
この場合、非零濃度は実施例２と同様、２３９／６６１≒０．３６１５となる。
【０３４７】
上記計算方法が、楕円曲線多重スカラー倍計算の高速性に優れる理由は、実施例２と同様である。
【０３４８】
また、本実施例は、部分エンコード処理に、実施例２のエンコード処理を用いた場合を例に挙げて記載した。しかし、実施例３のエンコード処理を用いることも可能である。
【０３４９】
＜多重スカラー倍計算部の実施例５＞
多重スカラー倍計算部１３５がスカラー値ｄ０、ｄ１、及び、楕円曲線上の点Ｐ０、Ｐ１から、楕円曲線における多重スカラー倍点ｄ０Ｐ０＋ｄ１Ｐ１を計算する第五の計算方法を実施例５として説明する。
【０３５０】
本実施例５では、図２８で示される多重スカラー倍計算部１３５の機能ブロックを用いる。多重スカラー倍計算部１３５（図１の１３５）の構成は、基本的に実施例１、実施例２、実施例３と同様である。ただし、エンコード部２８０２が変換判定部２８２１、数値変換部２８２２、繰り返し判定部２８２５、格納部２８２６で構成される点が異なっている。
【０３５１】
実施例５のエンコード部２８０２は、実施例１、実施例２、実施例３のエンコード部４０２同様、入力されたスカラー値ｄ０、ｄ１をＭＯＦ表現の第一の数値列ｅ０、ｅ１にエンコードする（第一のエンコード処理）。そして、第一の数値列ｅ０、ｅ１それぞれを、第一の数値列ｅ０、ｅ１とは異なる第二の数値列にエンコードする（第二のエンコード処理）。
【０３５２】
実施例１、実施例２では、数値計算部４２１がどのビット位置で０の項を生成することができるかを、両数値列ｅ０、ｅ１について求め、拡張可否判定部４２３が、前記数値計算部４２１の計算結果を用いて、両数値列ｅ０、ｅ１について同じ桁位置の数値が０になる桁数が所定数以上であるかどうか、１桁、３桁、５桁、４桁の順に所定数以上との結果が得られるまで判別する。そして、所定数以上との結論が得られた桁数分、数値変換部４２２が第二の数値列にエンコードする。
【０３５３】
なお、拡張可否判定部４２３は、取り出した１桁について、数値計算部４２１の計算結果に基づいて両数値列ｅ０、ｅ１がともに０であるか否かを判別する。両数値列ｅ０、ｅ１がともに０であれば、当該桁をそのまま第二の数値列にエンコードする。
【０３５４】
一方、両数値列ｅ０、ｅ１の少なくとも一方が０でないとき、拡張可否判定部４２３は、数値計算部４２１の計算結果に基づいて、取り出した１桁に連続する２桁加え３桁分とさらに連続する２桁を加えた５桁分とを比較して、いずれがより同じ桁位置の数値が０となる桁数が多いか判別し、取り出した１桁から多い方の桁数分、第二の数値列にエンコードする。
【０３５５】
なお、実施例３では、入力されるスカラー値の数は２つに限られない。
【０３５６】
このように、実施例１、実施例２等では、エンコード処理を行う際に読み込むビット長を、１桁、３桁、５桁、４桁に限定していた。しかし、実施例５では、エンコード処理を行う際に読み込むビット長の最大値を設けない。これにより、エンコード処理結果の非零濃度を小さくすることができ、更なる高速化を達成することができる。
【０３５７】
また、多重スカラー倍計算を最上位ビットから最下位ビットに向けて（ｌｅｆｔ−ｔｏ−ｒｉｇｈｔ）処理することが可能であり、最上位ビットから最下位ビットに向けて処理を行う他の実施例同様、高速性やメモリ使用量の観点で優れる。
【０３５８】
多重スカラー倍計算部１３５が署名検証処理部１３２からスカラー値ｄ０、ｄ１と楕円曲線上の点Ｐ０、Ｐ１を受け取ると、エンコード部２８０２は、入力されたスカラー値ｄ０、ｄ１を、式１７、式１８をみたすようにエンコードする。
【０３５９】
前計算部４０３は、入力された楕円曲線上の点Ｐ０、Ｐ１から、前計算テーブルを作成する。前計算テーブル作成方法は実施例１、実施例２、実施例４と同様である。
【０３６０】
実計算部４０４は、エンコードされた２つのスカラー値と楕円曲線上の点Ｐ、Ｑから、前計算テーブルを用いて多重スカラー倍点ｄ０Ｐ０＋ｄ１Ｐ１を計算する。多重スカラー倍計算方法は実施例１、実施例２と同様である。
【０３６１】
次にエンコード部２８０２の行う各処理について詳細に説明する。まず、エンコード部２８０２における変換判定部２８２１、数値変換部２８２２の行う処理について説明する。
【０３６２】
変換判定部２８２１は、与えられた二つのビット列τ０，τ１と整数ｒに対して、真偽を示す値を以下の条件に応じて出力する。出力値Ｏ１（τ０，τ１，ｒ）が真となるのは、τ０，τ１の列においてｒ個の０の項を生成できるときであり、偽となるのは、それ以外のときである。
【０３６３】
数値変換部２８２２は、与えられた二つのビット列τ０，τ１と整数ｒに対して、ｒ個の０の項を含む表現Ｏ２（τ０，τ１，ｒ）に変換する。
【０３６４】
次に、図２９を用いて、エンコード部２８０２がスカラー値ｄ０、ｄ１をエンコードする方法を説明する。以下において、ｕ、Ｌは、上記各実施例と同様の変数である。また、本実施例においてｒは、０の項の所望の個数を示す。
【０３６５】
ｄ０、ｄ１を入力し、ｄ０［−１］に０、ｄ０［ｎ］に０、ｄ１［−１］に０、ｄ１［ｎ］に０、ｕにｎ、Ｌにｎ、ｒに１、τ０［０］にｄ０［ｎ−１］−ｄ０［ｎ］、τ１［０］にｄ１［ｎ−１］−ｄ１［ｎ］をそれぞれ代入する（２９０１）。
【０３６６】
変換判定部２８２１は、Ｏ１（τ０［ｕ−Ｌ．．０］，τ１［ｕ−Ｌ．．０］，ｒ）が真であるかどうかを判定する。ここで、Ａ［ａ．．ｂ］は、数値列Ａの右からｂ桁目からａ桁目までの（ａ−ｂ）桁の数値からなる数値列を示す。真の場合は、ステップ２９０６へ行く。偽の場合は、ステップ２９０３へ行く（２９０２）。
【０３６７】
ステップ２９０２で偽の場合、エンコード部２８０２は、ｒにｒ＋１、ＬにＬ−２を代入する（２９０３）。
【０３６８】
繰り返し判定部２８２５は、Ｌ＞＝０かどうかを判定する。Ｌ＞＝０の場合、ステップ２９０５へ行く。Ｌ＜０の場合は、最大ビット長に至ったため、ステップ２９０９へ行く（２９０４）。
【０３６９】
ステップ２９０４でＬ＞＝０の場合、エンコード部２８０２は、τ０、τ１それぞれを２ビット左シフト（すなわち、τ０［ｕ−Ｌ］にτ０［ｕ−Ｌ−２］、τ０［ｕ−Ｌ−１］にτ０［ｕ−Ｌ−３］、…τ０［２］にτ０［０］、ならびにτ１［ｕ−Ｌ］にτ１［ｕ−Ｌ−２］、τ１［ｕ−Ｌ−１］にτ１［ｕ−Ｌ−３］、…τ１［２］にτ１［０］をそれぞれ代入する）し、τ０［１］にｄ０［Ｌ］−ｄ０［Ｌ＋１］、τ０［０］にｄ０［Ｌ−１］−ｄ０［Ｌ］、τ１［１］にｄ１［Ｌ］−ｄ１［Ｌ＋１］、τ１［０］にｄ１［Ｌ−１］−ｄ１［Ｌ］をそれぞれ代入し、ステップ２９０２へ戻る（２９０５）。
【０３７０】
ステップ２９０４でＬ＜０の場合、エンコード部２８０２は、τ０、τ１をそれぞれ２＋Ｌビット左シフトし、τ０［１＋Ｌ］にｄ０［−１］−ｄ０［０］、τ１［１＋Ｌ］にｄ１［−１］−ｄ１［０］を代入し、さらにｒに（ｕ＋２＋Ｌ）／２を代入し、数値変換部２８２２による変換表現Ｏ２（τ０［ｕ．．０］，τ１［ｕ．．０］，ｒ）のτ０［ｕ．．０］，τ１［ｕ．．０］をそれぞれμ０［ｕ．．０］，μ１［ｕ．．０］に代入し、ステップ２９１０へ行く（２９０９）。
【０３７１】
ステップ２９０２で真の場合、エンコード部２８０２は、数値変換部２８２２による変換表現Ｏ２（τ０［ｕ−Ｌ．．０］，τ１［ｕ−Ｌ．．０］，ｒ）のτ０［ｕ−Ｌ．．０］，τ１［ｕ−Ｌ．．０］をそれぞれμ０［ｕ．．Ｌ］，μ１［ｕ．．Ｌ］に代入し、さらに、ｕにＬ−１、ＬにＬ−１、ｒに１を代入しする（２９０６）。
【０３７２】
繰り返し判定部２８２５は、Ｌ＞＝０かどうかを判定する。Ｌ＞＝０の場合、ステップ２９０８へ行く。Ｌ＜０の場合、最大ビット長に至ったため、ステップ２９１０へ行く（２９０７）。
【０３７３】
ステップ２９０７でＬ＞＝０の場合、エンコード部２８０２は、τ０［０］にｄ０［ｕ−１］−ｄ０［ｕ］、τ１［０］にｄ１［ｕ−１］−ｄ１［ｕ］を代入し、ステップ２９０２へ戻る（２９０８）。
【０３７４】
ステップ２９０７でＬ＜０の場合、エンコード部２８０２は、ｄ０、ｄ１をエンコードした値としてμ０，μ１を出力し、エンコード処理を終了する（２９１０）。
【０３７５】
本実施例によれば、スカラー値のエンコード結果における非零濃度は７１／１９８≒０．３５８６となり、より少ない非零濃度を達成できる。従って、楕円曲線多重スカラー倍計算を高速化できる。特に、他の実施例同様、各スカラー値ｄ０、ｄ１の同じ桁がともに０となるビット数が増加するため、より高速化できる。
【０３７６】
なお、上記において、実施例５は、多重スカラー倍計算を最上位ビットから最下位ビットに向けて（ｌｅｆｔ−ｔｏ−ｒｉｇｈｔ）処理するものとして説明したが、最下位ビットから最上位ビットに向けて（ｒｉｇｈｔ−ｔｏ−ｌｅｆｔ）処理することも可能である。
【０３７７】
＜多重スカラー倍計算部の実施例６＞
本実施例６では、図２８で示される多重スカラー倍計算部１３５の機能ブロックを用いる。多重スカラー倍計算部１３５（図１の１３５）の構成は、実施例５と同様である。
【０３７８】
多重スカラー倍計算部１３５がスカラー値ｄ０、ｄ１、及び、楕円曲線上の点Ｐ０、Ｐ１から、楕円曲線における多重スカラー倍点ｄ０Ｐ０＋ｄ１Ｐ１を計算する第六の計算方法を説明する。実施例６では、エンコード処理を行う際に読み込むビット長の最大値を設けないことに加え、読み込むビット長が同じ場合にさらに良い出力結果（非零濃度の小さい結果）を生じるケースを積極的に探索する。これにより、エンコード処理結果の非零濃度を小さくすることができ、更なる高速化を達成することができる。
【０３７９】
また、多重スカラー倍計算を最上位ビットから最下位ビットに向けて（ｌｅｆｔ−ｔｏ−ｒｉｇｈｔ）処理することが可能であり、最上位ビットから最下位ビットに向けて処理を行う他の実施例同様、高速性やメモリ使用量の観点で優れる。
【０３８０】
なお、本実施例では、偶数桁単位で非零濃度の度合いを判定する。本実施例では、抽出した偶数桁を２つの奇数桁の組に分け、それぞれの非零濃度を判定する。予め定めた非零濃度が得られるまで、奇数桁への分け方を変更する、さらに桁数を増やすの２段階で非零濃度判定の対象を変更する。以下、具体的に処理を説明する。
【０３８１】
多重スカラー倍計算部１３５が署名検証処理部１３２からスカラー値ｄ０、ｄ１と楕円曲線上の点Ｐ０、Ｐ１を受け取ると、エンコード部２８０２は、入力されたスカラー値ｄ０、ｄ１を、式１７、式１８をみたすようにエンコードする。
【０３８２】
前計算部４０３は、入力された楕円曲線上の点Ｐ０、Ｐ１からから、前計算テーブルを作成する。前計算テーブル作成方法は実施例１、実施例２、実施例４、実施例５と同様である。
【０３８３】
実計算部４０４は、エンコードされた２つのスカラー値と楕円曲線上の点Ｐ、Ｑから、前計算テーブルを用いて多重スカラー倍点ｄ０Ｐ０＋ｄ１Ｐ１を計算する。多重スカラー倍計算方法は実施例１、実施例２、実施例５と同様である。
【０３８４】
次にエンコード部２８０２の行う各処理について詳細に説明する。エンコード部２８０２における変換判定部２８２１、数値変換部２８２２の行う処理は、実施例５と同様である。
【０３８５】
次に、図３０を用いて、エンコード部２８０２がスカラー値ｄ０、ｄ１をエンコードする方法を説明する。
【０３８６】
ｄ０、ｄ１を入力し、ｕにｎ−１、Ｗに２、ｉに１をそれぞれ代入する（３００１）。Ｗは、読み込むビット長を示す。
【０３８７】
変換判定部２８２１は、Ｏ１（τ０［ｕ．．ｕ−ｉ＋１］，τ１［ｕ．．ｕ−ｉ＋１］，（ｉ＋１）／２）、及びＯ１（τ０［ｕ−ｉ．．ｕ−Ｗ＋１］，τ１［ｕ−ｉ．．ｕ−Ｗ＋１］，（Ｗ−ｉ＋１）／２）が共に真であるかどうかを判定する。共に真の場合は、ステップ３００７へ行く。いずれかが偽の場合は、ステップ３００３へ行く（３００２）。
【０３８８】
ステップ３００２でいずれかが偽の場合、繰り返し判定部２８２５は、ｉ＝Ｗ−１であるかどうかを判定する。ｉ＝Ｗ−１の場合はステップ３００５へ行く。ｉ≠Ｗ−１の場合はステップ３００４へ行く（３００３）。
【０３８９】
ステップ３００３でｉ≠Ｗ−１の場合、エンコード部２８０２は、ｉにｉ＋２を代入し、ステップ３００２へ戻る（３００４）。
【０３９０】
ステップ３００３でｉ＝Ｗ−１の場合、エンコード部２８０２は、ＷにＷ＋２、ｉに１をそれぞれ代入しする（３００５）。
【０３９１】
繰り返し判定部２８２５は、ｕ−Ｗ＋１＞＝０であるかどうかを判定する。ｕ−Ｗ＋１＞＝０の場合はステップ３００２へ戻る。ｕ−Ｗ＋１＜０の場合はステップ３００９へ行く（３００６）。
【０３９２】
ステップ３００６でｕ−Ｗ＋１＜０の場合、繰り返し判定部２８２５は、ｕ−Ｗ＋１＝−１であるかどうかを判定する。ｕ−Ｗ＋１＝−１の場合はステップ３０１０へ行く。ｕ−Ｗ＋１≠−１の場合はステップ３０１２へ行く（３００９）。
【０３９３】
ステップ３００９でｕ−Ｗ＋１＝−１の場合、変換判定部２８２１は、Ｏ１（τ０［ｕ．．０］，τ１［ｕ．．０］，（ｕ＋２）／２）が真であるかどうかを判定する。真の場合はステップ３０１１へ行く。偽の場合はステップ３０１２へ行く（３０１０）。
【０３９４】
ステップ３０１０で真の場合、エンコード部２８０２は、ｒに（ｕ＋２）／２を代入し、ステップ３０１４へ行く（３０１１）。
【０３９５】
ステップ３００９でｕ−Ｗ＋１≠−１の場合ならびにステップ３０１０３で偽の場合、エンコード部２８０２は、ｒに（ｕ＋１）／２を代入し、ステップ３０１４へ行く（３０１２）。
【０３９６】
ステップ３００２で共に真の場合、エンコード部２８０２は、ｒに（ｉ＋１）／２を代入し、数値変換部２８２２による変換表現Ｏ２（τ０［ｕ．．ｕ−ｉ＋１］，τ１［ｕ．．ｕ−ｉ＋１］，ｒ）を、μ０［ｕ．．ｕ−ｉ＋１］，μ１［ｕ．．ｕ−ｉ＋１］に代入し、さらにｕにｕ−ｉ、ＷにＷ−ｉ＋１、ｉにＷ−１をそれぞれ代入する（３００７）。
【０３９７】
繰り返し判定部２８２５は、ｕ−Ｗ＋１＞＝０かどうかを判定する。ｕ−Ｗ＋１＞＝０の場合はステップ３００２へ戻る。ｕ−Ｗ＋１＜０の場合はステップ３０１３へ行く（３００８）。
【０３９８】
ステップ３００８でｕ−Ｗ＋１＜０の場合、エンコード部２８０２は、ｒに（ｕ＋２）／２を代入し、ステップ３０１４へ行く（３０１３）。
【０３９９】
エンコード部２８０２は、数値変換部２８２２による変換表現Ｏ２（τ０［ｕ．．０］，τ１［ｕ．．０］，ｒ）のτ０［ｕ．．０］，τ１［ｕ．．０］をそれぞれμ０［ｕ．．０］，μ１［ｕ．．０］に代入する（３０１４）。
【０４００】
エンコード部２８０２は、ｄ１、ｄ２をエンコードした値としてμ０，μ１を出力し、エンコード処理を終了する（３０１５）。
【０４０１】
本実施例によれば、スカラー値のエンコード結果における非零濃度をさらに向上させることができ、楕円曲線多重スカラー倍計算を高速化できる。
【０４０２】
＜多重スカラー倍計算部の実施例７＞
実施例７では、図２１で示される多重スカラー倍計算部１３５の機能ブロックを用いる。多重スカラー倍計算部１３５は、メモリ使用量計算部２１０１、多重スカラー倍計算法選択部２１０２、多重スカラー倍計算法Ａ１処理部１３５Ａ１、多重スカラー倍計算法Ａ２処理部１３５Ａ２、…、多重スカラー倍計算法Ａｎ処理部１３５Ａｎからなる。
【０４０３】
ここで、多重スカラー倍計算法Ａ１処理部１３５Ａ１、多重スカラー倍計算法Ａ２処理部１３５Ａ２、…、多重スカラー倍計算法Ａｎ処理部１３５Ａｎは、それぞれ実施例１から実施例６の何れか一つに記載の異なる多重スカラー倍計算部の機能を実現する。また、各多重スカラー倍計算法Ａｉ処理部１３５Ａｉには、多重スカラー倍計算の速度を表わす相対的な数値（例えば非零濃度）が格納されているものとする。
【０４０４】
図２２を用いて、多重スカラー倍計算部１３５がスカラー値ｄ０、ｄ１、…、ｄｋ−１及び、楕円曲線上の点Ｐ０、Ｐ１、…、Ｐｋ−１から、楕円曲線における多重スカラー倍点ｄ０Ｐ０＋ｄ１Ｐ１＋…＋ｄｋ−１Ｐｋ−１を計算する第七の計算方法を説明する。
【０４０５】
多重スカラー倍計算部１３５は、スカラー値ｄ０、ｄ１、…、ｄｋ−１及び、楕円曲線上の点Ｐ０、Ｐ１、…、Ｐｋ−１をメモリ使用量計算部２１０１へ送る（２２０１）。
【０４０６】
メモリ使用量計算部２１０１は、記憶部１２２において利用可能なメモリ使用量Ｍを計算する（２２０２）。なお、メモリ使用量Ｍは、記憶部１２２内の、本計算に割り当て可能な容量であり、メモリ使用量計算部２１０１記憶部１２２にアクセスし、空き容量を取得する。
【０４０７】
多重スカラー倍計算法選択部２１０２は、Ｍｉ＜Ｍを満たす各多重スカラー倍計算法Ａｉ処理部１３５Ａｉに格納されている多重スカラー倍計算の速度を表わす相対的な数値を比較し、最も高速なものを選択する（２２０３）。例えば、上記相対的な数値として非零濃度を用いた場合、Ｍｉ＜Ｍを満たす各多重スカラー倍計算法Ａｉ処理部１３５Ａｉに格納されている非零濃度のうち、最小な非零濃度を持つ多重スカラー倍計算法処理部１３５Ａｉを選択すればよい。
【０４０８】
ここで、Ｍｉは、多重スカラー倍計算法Ａｉ処理部１３５Ａｉを用いる際に必要なメモリ使用量である。メモリ使用量計算部２１０１が、与えられたスカラー値ｄ０、ｄ１、…、ｄｋ−１及び、楕円曲線上の点Ｐ０、Ｐ１、…、Ｐｋ−１を用いて、各多重スカラー倍計算法Ａｉ処理部１３５Ａｉが実現する多重スカラー倍計算方法において必要な事前計算テーブルに格納する点の数に基づいて求めるものである。
【０４０９】
ステップ２２０３で選択された多重スカラー倍計算法Ａｉ処理部１３５Ａｉは、多重スカラー倍点ｄ０Ｐ０＋ｄ１Ｐ１＋…＋ｄｋ−１Ｐｋ−１を計算する（２２０４）。
【０４１０】
多重スカラー倍計算部１３５は、多重スカラー倍点ｄ０Ｐ０＋ｄ１Ｐ１＋…＋ｄｋ−１Ｐｋ−１を出力する（２２０５）。
【０４１１】
上記計算方法が、楕円曲線多重スカラー倍計算の高速性に優れる理由は、与えられたメモリ使用量に合わせて、実施例１から実施例６に記載されている多重スカラー倍計算方法から最適な多重スカラー倍計算方法を選択し、多重スカラー倍計算を行っているからである。
【０４１２】
すなわち、本実施例によれば、使用可能なメモリの容量、要求される処理速度に応じて、最適な計算方法を選択し、多重スカラー倍計算を行うことができる。
【０４１３】
＜実施例８＞
本発明を暗号化処理システム、及び、復号化処理システムに適用する応用実施例である実施例８を、図２３と図２４を用いて説明する。
【０４１４】
図２３はネットワーク２３４２によって接続された本発明による楕円曲線演算方法を適用したコンピュータＡ２３０１、コンピュータＢ２３２１がネットワークにより接続されたシステム構成を示すものである。
【０４１５】
図２３の暗号通信システムにおけるコンピュータＡ２３０１でメッセ―ジの暗号化を行うには、Ｐｍ＋ｋ（ｄＱ）及びｋＱを計算して出力し、コンピュータＢ２３２１で暗号文の復号化を行うには、秘密鍵ｄ及びｋＱより−ｄ（ｋＱ）を計算し、
（Ｐｍ＋ｋ（ｄＱ））−ｄ（ｋＱ）          （式１９）
を計算して出力すればよい。
【０４１６】
ここでＰｍはメッセージ、ｋは乱数、ｄは秘密鍵を示す定数、Ｑは定点、ｄＱは公開鍵を示す点である。ネットワーク２３４２には、Ｐｍ＋ｋ（ｄＱ），ｋＱのみ送信され、メッセージＰｍを復元するためには、ｋｄＱ、すなわちｋＱのｄ倍を計算する必要がある。ところが、秘密鍵ｄはネットワーク２３４２には送信されないため、秘密鍵ｄを保持しているものだけが、Ｐｍを復元できることになる。
【０４１７】
図２３において、コンピュータＡ２３０１は、ＣＰＵ２３１３やコプロセッサ２３１４などの演算装置、ＲＡＭ２３０３、ＲＯＭ２３０６や外部記憶装置２３０７などの記憶装置、コンピュータ外部とのデータ入出力を行う入出力インタフェース２３１０を装備しており、外部にはコンピュータＡ２３０１をユーザが操作するためのディスプレイ２３０８、キーボード２３０９、着脱可能な可搬型記憶媒体の読み書き装置などが接続されている。
【０４１８】
更にコンピュータＡ２３０１は、ＲＡＭ２３０３、ＲＯＭ２３０６や外部記憶装置２３０７などの記憶装置によって、記憶部２３０２を実現し、ＣＰＵ２３１３やコプロセッサ２３１４などの演算装置が、記憶部２３０２に格納されたプログラムを実行することにより、データ処理部２３１２、多重スカラー倍計算部２３１５、スカラー値変換部２３１６とそれらに含まれる各処理部を実現する。
【０４１９】
データ処理部２３１２は、本実施形態においては、暗号化処理部２３１２として機能し、入力されたメッセージの暗号化を行う。
【０４２０】
多重スカラー倍計算部２３１５は、暗号処理部２３１２で暗号化を行うのに必要なパラメタを計算する。
【０４２１】
記憶部２３０２は、定数２３０４（例えば、楕円曲線の定義式や楕円曲線上の定点である）、秘密情報２３０５（例えば、秘密鍵である）などを記憶している。
【０４２２】
コンピュータＢ２３２１は、コンピュータＡ２３０１と同様のハードウェア構成を備える。
【０４２３】
更にコンピュータＢ２３２１は、ＲＡＭ２３２３、ＲＯＭ２３２６や外部記憶装置２３２７などの記憶装置によって、記憶部２３２２を実現し、ＣＰＵ２３３３やコプロセッサ２３３４などの演算装置が、記憶部２３２２に格納されたプログラムを実行することにより、データ処理部２３３２、スカラー倍計算部２３３５、スカラー値変換部２３３６とそれらに含まれる各処理部を実現する。
【０４２４】
データ処理部２３３２は、本実施形態においては、復号化処理部２３３２として機能し、暗号化されたメッセージである暗号文２３４１の復号化を行う。
【０４２５】
多重スカラー倍計算部２３３５は、復号化処理部２３３２で復号化を行うのに必要なパラメタを計算する。
【０４２６】
記憶部２３２２は、定数２３２４（例えば、楕円曲線の定義式や楕円曲線上の定点である）、秘密情報２３２５（例えば、秘密鍵である。）などを記憶している。
【０４２７】
なお、上記各プログラムは、あらかじめ、上記コンピュータ内の記憶部に格納されていても良いし、必要なときに、入出力インタフェース２３１０もしくは２３３０と上記コンピュータ２３０１もしくは２３２１が利用可能な媒体を介して、他の装置から上記記憶部に導入されてもよい。媒体とは、たとえば、入出力インタフェース２３１０もしくは２３３０に着脱可能な記憶媒体、または通信媒体（すなわちネットワークまたはネットワークを伝搬する搬送波）を指す。
【０４２８】
図２４は、コンピュータＡ２３０１、コンピュータＢ２３２１の各処理部が行う情報の受け渡しの様子を示したものである。
【０４２９】
次に、図２３のコンピュータＡ２３０１が、入力されたメッセージを暗号化する場合の動作について説明する。メッセージはディジタル化されたデータであれば良く、テキスト、画像、映像、音などの種類は問わない。
【０４３０】
暗号化処理部２３１２（図２４のデータ処理部２３１２）は、入出力インタフェース１１０を介して、平文メッセージ（図２４の入力メッセージ２４０１）を受け取ると、入力された平文メッセージのビット長が予め定めたビット長か否かを判断する。予め定めたビット長より長い場合には、予め定めたビット長となるように平文メッセージを区切る。
【０４３１】
以下、所定のビット長に区切られている部分メッセージ（単にメッセージともいう）について説明する。暗号化処理部２３１２は、メッセージのビット列によって表される数値をｘ座標（ｘ１）にもつ楕円曲線上の点Ｐｍのｙ座標の値（ｙ１）を計算する。例えば、ワイエルシュトラス型楕円曲線は、式３で表わされるので、これよりｙ座標の値を求めることができる。
【０４３２】
次に、暗号化処理部２３１２は、乱数ｋを生成する。そして、記憶部２３０２に格納されている定数２３０４から読み出した（図２４の２４０２）公開鍵ｄＱとＱのｘ座標と、求めたｙ座標の値と乱数ｋとをスカラー値変換部２３１６へ送る（図２４の２４０３）。
【０４３３】
文献Ｒ．Ｐ．Ｇａｌｌａｎｔ，Ｊ．Ｌ．Ｌａｍｂｅｒｔ，ａｎｄＳ．Ａ．Ｖａｎｓｔｏｎｅ“Ｆａｓｔｅｒ  Ｐｏｉｎｔ  Ｍｕｌｔｉｐｌｉｃａｔｉｏｎ  ｏｎ  Ｅｌｌｉｐｔｉｃ  Ｃｕｒｖｅｓ  ｗｉｔｈ  Ｅｆｆｉｃｉｅｎｔ  Ｅｎｄｏｍｏｒｐｈｉｓｍｓ”，Ｉｎ  Ｊ．Ｋｉｌｉａｎ，ｅｄｉｔｏｒ，Ａｄｖａｎｃｅｓ  ｉｎ  Ｃｒｙｐｔｏｌｏｇｙ    Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ＣＲＹＰＴＯ２００１，ｖｏｌｕｍｅ  ２１３９  ｏｆ  Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ，１９０−２００．Ｓｐｒｉｎｇｅｒ，２００１．
に記載のワイエルシュトラス型楕円曲線に対し、点Ｐ、スカラー値ｄに対するスカラー倍点ｄＰを、多重スカラー倍点
ｄＰ＝ｋ０Ｐ＋ｋ１（ΨＰ）          （式２０）
に変換する方法が記載されており、スカラー倍計算を多重スカラー倍計算に置き換えることができる。ここで、ｋ０、ｋ１は、０から√ｎまでの範囲にある正の整数、ΨはＥの自己準同型写像、ｎは点Ｐの位数である。
【０４３４】
したがって、Ｐ０＝Ｐ、Ｐ１＝ΨＰとすると、点Ｐ、スカラー値ｄに対するスカラー倍点ｄＰのスカラー倍計算は、実施例１から実施例７の何れか一つに記載の多重スカラー倍計算方法を用いて多重スカラー倍点ｋ０Ｐ０＋ｋ１Ｐ１を計算することにより、高速性に優れた多重スカラー倍計算が可能である。
【０４３５】
スカラー値変換部２３１６は、乱数ｋを
ｋＱ＝ｋ０Ｑ＋ｋ１（ΨＱ）          （式２１）
を満たす整数ｋ０，ｋ１に変換し、
点Ｑ、ΨＱ、及び、整数ｋ０，ｋ１を多重スカラー倍計算部２３１５へ送る（図２４の２４０４）。
【０４３６】
多重スカラー倍計算部２３１５は、実施例１から実施例７の何れか一つに記載の多重スカラー倍計算方法を用いて、Ｑのｘ座標、ｙ座標の値、乱数ｋによるスカラー倍点（ｘｄ１，ｙｄ１）＝ｋＱと、公開鍵ｄＱのｘ座標、ｙ座標の値、乱数によるスカラー倍点（ｘｄ２，ｙｄ２）＝ｋ（ｄＱ）とを計算する。計算されたスカラー倍点を暗号化処理部２３１２へ送る（図２４の２４０５）。
【０４３７】
暗号化処理部２３１２は、送られたスカラー倍点を用いて、暗号化処理を行う。例えば、ワイエルシュトラス型楕円曲線では、ｋＱとＰｍ＋ｋ（ｄＱ）を計算する。すなわち、
ｘｅ１＝（（ｙｄ１−ｙ１）／（ｘｄ１−ｘ１））２−ｘ１−ｘｄ１          （式２２）
ｘｅ２＝ｘｄ２          （式２３）
を計算し、暗号化されたメッセージｘｅ１，ｘｅ２を得る。
【０４３８】
コンピュータＡ２３０１は暗号化処理部２３１２で暗号化された１つ以上の部分メッセージから暗号化された出力メッセージを組み立てる（図２の２４０６）。
【０４３９】
コンピュータＡ２３０１は、暗号化された出力メッセージをデータ２３４１として入出力インタフェース２３１０より出力し、ネットワーク２３４２を介してコンピュータＢ２３２１へ転送する。
【０４４０】
なお、図２３の記憶部２３０２からの情報読み出しは、多重スカラー計算部２３１５へ当該情報を送る前で有れば、入力メッセージを受け付ける前であっても良い。
【０４４１】
次に、コンピュータＢ２３２１が、暗号化されたメッセージ２３４１を復号化する場合の動作について、図２４を参照しつつ説明する。
【０４４２】
復号化処理部２３３２（図２４のデータ処理部２３１２）は、入出力インタフェース２３３０を介して、暗号化されたデータ２３４１（図２４の入力メッセージ２４０１）が入力されると、入力された暗号化されたデータ２３４１のビット長が予め定めたビット長か否かを判断する。予め定めたビット長より長い場合には、予め定めたビット長となるように暗号化されたデータを区切る。
【０４４３】
以下、所定のビット長に区切られている部分データ（単にデータともいう）について説明する。データ２３４１のビット列によって表される数値をｘ座標にもつ楕円曲線上のｙ座標の値を計算する。暗号化されたメッセージがｘｅ１，ｘｅ２のビット列であり、ワイエルシュトラス型楕円曲線ではｙ座標の値ｙｅ１，ｙｅ２は、式３から得ることができる。
【０４４４】
復号化処理部２３３２は、記憶部２３２２（図２４の２４０２）に格納されている秘密情報２３２５から読み出した（図２４の２３０２）秘密鍵ｄと、ｘ座標、ｙ座標の値（ｘｅ１，ｙｅ１）とを、多重スカラー倍計算部２３３５（図２４の２３３５）へ送る（図２４の２３０２）。
【０４４５】
暗号化処理と同様に、上記文献に記載されているスカラー倍計算から多重スカラー倍計算への変換方法を用いると、秘密鍵ｄを、式２０を満たすｋ０，ｋ１に変換することができ、スカラー倍計算を多重スカラー倍計算に変換することが可能である。スカラー値変換部２３３６は、秘密鍵ｄを、式２１を満たす整数ｋ０，ｋ１に変換し、点（ｘｅ１，ｙｅ１）、及び、整数ｋ０，ｋ１を多重スカラー倍計算部２３３５へ送る（図２４の２４０４）。
【０４４６】
多重スカラー倍計算部２３３５は、実施例１から実施例７の何れか一つに記載の多重スカラー倍計算方法を用いて、（ｘｄ３，ｙｄ３）＝ｄ（ｘｅ１，ｙｅ１）＝ｋ０（ｘｅ１，ｙｅ１）＋ｋ１Ψ（ｘｅ１，ｙｅ１）を計算する。多重スカラー倍計算部２３３５は、計算されたスカラー倍点を復号化処理部２３３２へ送る（図２４の２４０５）。
【０４４７】
復号化処理部２３３２は、送られたスカラー倍点を用いて、復号化処理を行う。例えば、暗号化されたメッセージが、ｘｅ１，ｘｅ２のビット列であり、ワイエルシュトラス型楕円曲線では、（Ｐｍ＋ｋ（ｄＱ））−ｄ（ｋＱ）＝（ｘｅ２，ｙｅ２）−（ｘｄ３，ｙｄ３）を計算することにより達成する。すなわち、
ｘｆ１＝（（ｙｅ１＋ｙｄ３）／（ｘｅ１−ｘｄ３））２−ｘｅ１−ｘｄ３          （式２４）
を計算し、暗号化される前の部分メッセージｘ１に相当するｘｆ１を得る。
【０４４８】
コンピュータＢ２３２１は、復号化処理部２３３２で復号化された部分メッセージから平文メッセージを組み立て（図２４の２４０６）、入出力インタフェース２３３０を介して、ディスプレイ２３２８などから出力する。
【０４４９】
＜実施例９＞
次に本発明を鍵生成、及び、鍵交換システムに適用する実施形態を実施例９として説明する。本実施形態においては、図２３のシステム構成が応用できる。
【０４５０】
図２３のデータ処理部２３１２、２３３２は、本実施形態においては、それぞれ鍵交換処理部２３１２、２３３２として機能する。鍵交換システムのコンピュータＡ２３０１が、入力されたデータ２３４３から共有情報の導出を行う場合の動作について図２３、図２４を参照して説明する。
【０４５１】
コンピュータＢ２３２１のデータ処理部２３３２（図２４の２３１２）は、記憶部２３２２（図２４の２３０２）の定数２３２５から秘密鍵ｂを読み出しコンピュータＢ２３２１の公開鍵ｂＱを計算する。スカラー倍計算ｂＱは、上記暗号化処理、及び、復号化処理と同様に、多重スカラー倍計算に置き換え、多重スカラー倍計算を行う。
【０４５２】
そして、ネットワーク２３４２を介して、公開鍵ｂＱをデータ２３４３としてコンピュータＡ２３０１に転送する。コンピュータＡ２３０１の鍵交換処理部２３１２（図２４の２３１２）はコンピュータＢ２３２１の公開鍵ｂＱの入力を受け付ける（図２４の２４０１）と、鍵交換処理部２３１２は、記憶部２３０２から読み出した（図２４の２４０２）秘密情報２３０５であるコンピュータＡ２３０１の秘密鍵ａと、コンピュータＢ２３２１の公開鍵ｂＱとを多重スカラー倍計算部２３１５へ送る（図２４の２４０３及び２４０４）。
【０４５３】
多重スカラー倍計算部２３１５は、秘密鍵ｄと、公開鍵ｂＱによるスカラー倍点ｄｂＱを計算し、計算されたスカラー倍点を鍵交換処理部２３１２へ送る（図２４の２４０５）。
【０４５４】
鍵交換処理部２３１２は、送られたスカラー倍点を用いて共有情報の導出を行い、記憶部２３０２に秘密情報２３０５として格納する。例えば、スカラー倍点ｄｂＱのｘ座標を、共有情報とする。
【０４５５】
次に、コンピュータＢ２３２１が、入力されたデータ２３４１から共有情報の導出を行う場合の動作について説明する。
【０４５６】
コンピュータＡ２３０１のデータ処理部２３１２は、記憶部２３０２の定数２３０５から秘密鍵ｄを読み出しコンピュータＡ２３０１の公開鍵ｄＱを計算する。そして、ネットワーク２３４２を介して、公開鍵ｄＱをデータ２３４１としてコンピュータＢ２３２１に転送する。
【０４５７】
コンピュータＢ２３２１の鍵交換処理部２３３２（図２４の２３１２）はコンピュータＡ２３０１の公開鍵ｄＱの入力を受け付ける（図２４の２４０１）と、鍵交換処理部２３３２は、記憶部２３２２（図２４の２３０２）の定数２３２５から読み出した（図２４の２４０２）秘密情報２３２５であるコンピュータＢ２３２１の秘密鍵ｂと、コンピュータＡ２３０１の公開鍵ｄＱとをスカラー倍計算部２３３５（図２４の２３１５）へ送る（図２４の２４０３及び２４０４）。
【０４５８】
多重スカラー倍計算部２３３５は、秘密鍵ｂと、公開鍵ｄＱによるスカラー倍点ｂｄＱを計算し、計算されたスカラー倍点を鍵交換処理部２３３２へ送る（図２４の２４０５）。
【０４５９】
鍵交換処理部２３３２は、送られたスカラー倍点を用いて共有情報の導出を行い、記憶部２３２２に秘密情報２３２５として格納する。例えば、スカラー倍点ｂｄＱのｘ座標を、共有情報とする。ここで、数ｄｂと数ｂｄは数値として同じなので、点ｄｂＱと点ｂｄＱは同じ点となり、同じ情報が導出されたことになる。
【０４６０】
なお、本実施形態においても、暗号化処理、及び、復号化処理と同様に、上記文献に記載されているスカラー倍計算から多重スカラー倍計算への変換方法を用いると、秘密鍵ｄを、式２０を満たすｋ０，ｋ１に変換することができ、スカラー倍計算を多重スカラー倍計算に変換することが可能である。
【０４６１】
また、コンピュータＡ２３０１のデータ処理部２３１２が鍵生成処理において、記憶部２３０２の定数２３０５から秘密鍵ｄを読み出しコンピュータＡ２３０１の公開鍵ｄＱを計算する際、定点Ｑは記憶部２３０２の定数２３０５に格納されている。
【０４６２】
そのため、例えば秘密鍵ｄのサイズが１９２ｂｉｔ程度のとき、定点Ｑのスカラー倍点Ｐ１＝２３２Ｑ、Ｐ２＝２６４Ｑ、Ｐ３＝２９６Ｑ、Ｐ４＝２１２８Ｑをあらかじめ計算し、記憶部１０２に格納しておくことにより、秘密鍵値ｄ、定点Ｑによる公開鍵ｄＱのスカラー倍計算では、
ｄＱ＝ｄ０Ｐ０＋ｄ１Ｐ１＋ｄ２Ｐ２＋ｄ３Ｐ３＋ｄ４Ｐ４          （式２５）
より、スカラー倍計算を多重スカラー倍計算に置き換えることができることが非特許文献２に記載されている。
ここで、ｄ０、…、ｄ４は、
ｄ＝ｄ０＋２３２ｄ１＋２６４ｄ２＋２９６ｄ３＋２１２８ｄ４          （式２６）
を満たす整数のバイナリ表現である。
【０４６３】
ネットワーク２３４２には、点ｄＱと点ｂＱが送信されるが、点ｄｂＱ（もしくは点ｂｄＱ）を計算するには秘密鍵ｄもしくは秘密鍵ｂを用いなければならない。すなわち、秘密鍵ｄもしくは秘密鍵ｂを知らなければ、共有情報を得ることができない。このようにして得られた共有情報は、共通鍵暗号の秘密鍵として利用できる。
【０４６４】
また、上記非特許文献２に記載の方法を用いて、署名検証処理システムにおける多重スカラー倍計算を行ってもよい。
【０４６５】
また、上記各実施形態における署名生成部、署名検証部、暗号化処理部、復号化処理部、鍵生成部、鍵交換処理部は、専用のハードウェアを用いて行ってもよい。また、スカラー倍計算部をコプロセッサまたはそれ以外の専用ハードウェアで実現しても良い。また、データ処理部は、上記署名生成処理、署名検証処理、暗号化処理、復号化処理、鍵生成処理、鍵交換処理のうち、任意の一つ以上の処理を行えるように構成してもよい。
【図面の簡単な説明】
【０４６６】
【図１】実施形態におけるシステム構成図である。
【図２】署名生成処理における情報の受け渡しを例示するシーケンス図である。
【図３】署名検証処理における情報の受け渡しを例示するシーケンス図である。
【図４】実施例１〜実施例３における多重スカラー倍計算部の構成図である。
【図５】実施例１におけるエンコード部の行うエンコード方法を例示するフローチャート図である。
【図６】実施例１、及び、実施例２におけるエンコード部の行うエンコード方法を例示するフローチャート図である。
【図７】実施例１、及び、実施例２におけるエンコード部の行うエンコード方法を例示するフローチャート図である。
【図８】実施例１におけるエンコード部の行うエンコード方法を例示するフローチャート図である。
【図９】実施例１におけるエンコード部の行うエンコード方法を例示するフローチャート図である。
【図１０】実施例１、実施例２、及び、実施例４における前計算部の前計算テーブル作成方法を示す図である。
【図１１】実施例１、及び、実施例２における実計算部の多重スカラー倍の計算方法を例示するフローチャート図である。
【図１２】実施例２におけるエンコード部の行うエンコード方法を例示するフローチャート図である。
【図１３】実施例３におけるエンコード部の行うエンコード方法を例示するフローチャート図である。
【図１４】実施例３におけるエンコード部の行うエンコード方法を例示するフローチャート図である。
【図１５】実施例３におけるエンコード部の行うエンコード方法を例示するフローチャート図である。
【図１６】実施例３における前計算部の前計算テーブル作成を例示する図である。
【図１７】実施例３における実計算部の多重スカラー倍の計算方法を例示するフローチャート図である。
【図１８】実施例４の実施形態における多重スカラー倍計算部の構成図である。
【図１９】実施例４における実計算部の多重スカラー倍の計算方法を例示するフローチャート図である。
【図２０】実施例４における実計算部の多重スカラー倍の計算方法を例示するフローチャート図である。
【図２１】実施例７の実施形態における多重スカラー倍計算部の構成図である。
【図２２】実施例７における実計算部の多重スカラー倍の計算方法を例示するフローチャート図である。
【図２３】暗号化処理、復号化処理、及び、鍵交換処理におけるシステム構成図である。
【図２４】暗号化処理、復号化処理、及び、鍵交換処理における情報の受け渡しを例示するシーケンス図である。
【図２５】実施例１におけるサブルーチンの呼び出し、制御、及び、データの流れに関するシーケンス図である。
【図２６】従来技術を用いた多重スカラー倍計算方法の説明図である。
【図２７】本発明を用いた多重スカラー倍計算方法の説明図である。
【図２８】実施例５、６の実施形態における多重スカラー倍計算部の構成図である。
【図２９】実施例５におけるエンコード部の行うエンコード方法を例示するフローチャート図である。
【図３０】実施例６におけるエンコード部の行うエンコード方法を例示するフローチャート図である。
【符号の説明】
【０４６７】
１０１、２３０１、２３２１：コンピュータ、１２１：スマートカード、１０２、１２２、２３０２、２３２２：記憶部、１１１、１３１、２３１１、２３３１：処理部、１１５：スカラー倍計算部、１３５、２３１５、２３３５：多重スカラー倍計算部、１１２：署名生成処理部、１３２：署名検証処理部、２３２１、２３３１：データ処理部、１０４、１２４、２３０４、２３２４：定数、１０５、１２５、２３０５、２３２５：秘密情報、１１０、１３０、２３１０、２３３０：入出力インタフェース、１０７、２３０７、２３２７：外部記憶装置、１０８、２３０８、２３２８：ディスプレイ、１０９、２３０９、２３２９：キーボード、２３４２：ネットワーク、１４２：チャレンジコード、２３４１、２３４３：データ、４０２：エンコード部、４０３：前計算部、４０４：実計算部、４２１：数値計算部、４２２：数値変換部、４２３：拡張可否判定部、４２４：拡張部、４２５：繰り返し判定部、４２６：格納部、４３１：加算部、４３２：２倍算部、４３３：繰り返し判定部、４４１：ビット値判定部、４４２：加算部、４４３：２倍算部、４４４：繰り返し判定部、１８０１：前計算部、１８０２：実計算部、１８１１：加算部、１８１２：２倍算部、１８１３：繰り返し判定部、１８２１：数値計算部、１８２２：数値変換部、１８２３：拡張可否判定部、１８２４：拡張部、１８２５：ビット値判定部、１８２６：加算部、１８２７：２倍算部、１８２８：繰り返し判定部、２８０２：エンコード部、２８２１：変換判定部、２８２２：数値変換部、２８２５：繰り返し判定部、２８２６：格納部
【図１】
2006309201.tif 000003
【図２】
2006309201.tif 000004
【図３】
2006309201.tif 000005
【図４】
2006309201.tif 000006
【図５】
2006309201.tif 000007
【図６】
2006309201.tif 000008
【図７】
2006309201.tif 000009
【図８】
2006309201.tif 000010
【図９】
2006309201.tif 000011
【図１０】
2006309201.tif 000012
【図１１】
2006309201.tif 000013
【図１２】
2006309201.tif 000014
【図１３】
2006309201.tif 000015
【図１４】
2006309201.tif 000016
【図１５】
2006309201.tif 000017
【図１６】
2006309201.tif 000018
【図１７】
2006309201.tif 000019
【図１８】
2006309201.tif 000020
【図１９】
2006309201.tif 000021
【図２０】
2006309201.tif 000022
【図２１】
2006309201.tif 000023
【図２２】
2006309201.tif 000024
【図２３】
2006309201.tif 000025
【図２４】
2006309201.tif 000026
【図２５】
2006309201.tif 000027
【図２６】
2006309201.tif 000028
【図２７】
2006309201.tif 000029
【図２８】
2006309201.tif 000030
【図２９】
2006309201.tif 000031
【図３０】
2006309201.tif 000032