(57)【要約】【課題】リソースが限られた環境で、安全性を低下させることなく、τ−ＮＡＦなどのＫｏｂｌｉｔｚ曲線上での従来のスカラー倍計算より高速であり、かつＫｏｂｌｉｔｚ曲線上の最小な加算回数と最小なフロベニウス写像の回数で処理可能なＫｏｂｌｉｔｚ曲線演算技術を実現することを目的とする。【解決手段】τ−ＮＡＦ表現の符号列と、このτ−ＮＡＦ表現の符号列と同値であり、かつ予め最小な加算回数で処理でき、かつ最小なフロベニウス写像の回数で処理可能なτ−ＭＬＦ表現の符号列と、を対応付けて格納している変換テーブル３６（３６ａ）を記憶部に有しており、入力されたスカラー値をτ−ＮＡＦ表現の符号列に変換した後、前記変換テーブル３６（３６ａ）に従って、前記τ−ＮＡＦ表現の符号列を前記τ−ＭＬＦ表現の符号列へ変換することを特徴とする。【選択図】図３
2011081147.tif 000002
【特許請求の範囲】
【請求項１】
入力部を介して入力されたＫｏｂｌｉｔｚ曲線上の点の座標およびスカラー値を基に、前記Ｋｏｂｌｉｔｚ曲線上におけるスカラー倍点の座標を算出するスカラー倍計算装置であって、
τ−ＮＡＦ変換された第１の符号列と、第１の符号列より短い符号長を有し、かつτ−ＮＡＦ表現において前記第１の符号列と同一の値を有する第２の符号列と、を有している変換情報を格納している記憶部と、
情報を処理する処理部と、を有し、
前記処理部が、
入力された前記スカラー値を前記第１の符号列に変換し、
前記変換情報を基に、前記第１の符号列に対応する第２の符号列を取得し、
前記取得した第２の符号列を前記スカラー値の符号列として出力し、
前記出力された第２の符号列と、前記入力されたＫｏｂｌｉｔｚ曲線上の点の座標と、を基に、前記Ｋｏｂｌｉｔｚ曲線上の点を前記スカラー値の値でスカラー倍した前記スカラー倍点の座標を算出する
ことを特徴とするスカラー倍計算装置。
【請求項２】
前記第１の符号列のうち、変換対象の符号列は、符号列の内、上位６桁の符号列である
ことを特徴とする請求項１に記載のスカラー倍計算装置。
【請求項３】
前記第１の符号列と、前記第２の符号列の対応は、以下の関係である
ことを特徴とする請求項２に記載のスカラー倍計算装置。
【数３】
2011081147.tif 000005
なお、前記関係において、左側の各符号列が前記第１の符号列であり、右側の各符号列が前記第２の符号列であり、μ＝（−１）１−ａ（ａは前記Ｋｏｂｌｉｔｚ曲線の係数）であり、前記した第１の符号列以外の符号列は、変換されずに前記第２の符号列となる。
【請求項４】
入力部を介して入力されたＫｏｂｌｉｔｚ曲線上の点の座標およびスカラー値を基に、前記Ｋｏｂｌｉｔｚ曲線上におけるスカラー倍点の座標を算出するスカラー倍計算装置であって、
所定の符号列をτ進複素数表現した値と、前記τ進複素数表現に対応している第３の符号列と、を有している変換情報を格納している記憶部と、
情報を処理する処理部と、を有し、
前記処理部が、
（ａ１）前記入力されたスカラー値を前記τ進複素数表現にした値へ変換し、
（ａ２）前記変換されたτ進複素数表現が、前記変換情報に格納されていない場合、第４の符号列にτ−ＮＡＦ変換した符号を１つ追加し、
（ａ３）前記τ進複素数表現の実部および虚部の値を予め設定されている第１の方法に従って更新し、
（ａ４）前記変換されたτ進複素数表現が、前記変換情報に格納されている場合、前記変換情報から、前記τ進複素数表現に対応する前記第３の符号列を取得し、前記前記τ進複素数表現の実部および虚部の値に、０を代入し
（ａ５）前記更新された前記τ進複素数表現の実部および虚部の値が、共に０となるまで、前記（ａ２）〜（ａ４）の処理を繰り返し、
（ａ６）前記τ進複素数表現の実部および虚部の値が、共に０となった場合、前記第４の符号列の上位の桁に、前記第３の符号列を追加した第５の符号列を、前記スカラー値の符号列として出力し、
前記出力された第５の符号列と、前記入力されたＫｏｂｌｉｔｚ曲線上の点の座標と、を基に、前記Ｋｏｂｌｉｔｚ曲線上の点を前記スカラー値の値でスカラー倍した前記スカラー倍点の座標を算出する
ことを特徴とするスカラー倍計算装置。
【請求項５】
前記τ進複素数表現の値と、前記第３の符号列の関係は、以下の関係である
ことを特徴とする請求項４に記載のスカラー倍計算装置。
【数４】
2011081147.tif 000006
なお、当該関係において、左側の各式が前記τ進複素数表現の値であり、右側の各符号列が前記第３の符号列であり、μ＝（−１）１−ａ（ａは前記Ｋｏｂｌｉｔｚ曲線の係数）である。
【請求項６】
入力部を介して入力されたＫｏｂｌｉｔｚ曲線上の点の座標およびスカラー値を基に、前記Ｋｏｂｌｉｔｚ曲線上におけるスカラー倍点の座標を算出するスカラー倍計算装置であって、
前記入力部を介して入力された前記スカラー値を２進表現でビット列を、予め設定されている第２の方法で変換した第６の符号列と、前記第６の符号列に対応している第７の符号列と、を有している変換情報を格納している記憶部と、
情報を処理する処理部と、を有し、
前記処理部が、
（ｂ１）前記スカラー値が２進表現のビット列として入力され、
（ｂ２）前記ビット列の最大桁数が６桁以上であり、かつ現在計算している桁が上位６桁以外である場合、予め設定されている第３の方法に従って（１，０、−１）の３値のうちのいずれかの符号を生成し、当該生成した符号を第８の符号列に追加し、現在計算している桁が上位６桁以内となるまで、前記（ｂ２）の処理を繰り返し、
（ｂ３）前記ビット列の最大桁数が６桁未満である、または現在計算している桁が上位６桁以内である場合、前記ビット列のうち、現在している桁以下７桁の符号列を、前記第２の方法で変換した第９の符号列が、前記変換情報に格納されている第６の符号列のいずれかと一致するか否かを判定し、
（ｂ４）前記判定の結果、前記第９の符号列が、前記変換情報に格納されている第６の符号列のうちのいずれとも一致しない場合、予め設定されている第４の方法に従って（１，０、−１）の３値のうちのいずれかの符号を生成し、当該生成した符号を第８の符号列に追加し、現在計算している桁が前記ビット列の最大桁数より大きくなるまで、前記（ｂ４）の処理を繰り返し、
（ｂ５）前記判定の結果、前記第９の符号列が、前記変換情報に格納されている第６の符号列のいずれかと一致する場合、前記変換情報から、前記第９の符号列に対応する前記第７の符号列を取得し、前記第８の符号列の上位の桁に前記第７の符号列を追加した第１０の符号列を、前記スカラー値の符号列として出力し、
前記出力された第１０の符号列と、前記入力されたＫｏｂｌｉｔｚ曲線上の点の座標と、を基に、前記Ｋｏｂｌｉｔｚ曲線上の点を前記スカラー値の値でスカラー倍した前記スカラー倍点の座標を算出する
ことを特徴とするスカラー倍計算装置。
【請求項７】
前記処理部は、
前記第６の符号列と、前記第７の符号列の関係は、以下の関係であることを特徴とする請求項６に記載のスカラー倍計算装置。
（ｘ、１，０，０，１，０，０）→（０，０，−μ，−１，０，０）τ
（ａ，１，０，１，１，０，０）→（０，０，μ，１，０，０）τ
（ｘ、１，０，０，１，０，１）→（０，０，−μ，−１，０，１）τ
（ａ，１，０，１，１，１，１）→（０，０，μ，１，０，−１）τ
（ｘ，１，０，０，１，１，１）→（０，０，０，−１，μ，１）τ
（ａ，１，０，１，１，０，１）→（０，０，０，１，−μ，−１）τ
（ｘ，１，ｘ、１，０，０，０）→（０，１，−μ，０，０，０）τ
（ａ，１，ａ，１，０，０，０）→（０，−１，μ，０，０，０）τ
（ｘ，１，ｘ，１，０，０，１）→（０，１，−μ，０，０，１）τ
（ａ，１，ａ，１，０，１，１）→（０，−１，μ，０，０，−１）τ
（ｘ，１，ｘ，１，０，１，１）→（０，０，０，−１，μ，１）τ
（ａ，１，ａ，１，０，０，１）→（０，０，０，１，μ，−１）τ
（ｘ，１，ｘ，１，ｘ，１，０）→（０，１，−μ，０，μ，０）τ
（ａ，１，ａ，１，ａ，１，０）→（０，−１，μ，０，−μ，０）τ
（ｘ，１，ｘ，１，ａ，１，０）→（０，１，−μ，０，−μ，０）τ
（ａ，１，ａ，１，ｘ，１，０）→（０，−１，μ，０，μ，０）τ
ただし、当該関係において、左側の各符号列が前記第６の符号列であり、右側の各符号列が前記第７の符号列であり、ａはＫｏｂｌｉｔｚ曲線の係数であり、ｘはｘ＝（ａ−１）ｍｏｄ２であり、μ＝（−１）１−ａ（ａは前記Ｋｏｂｌｉｔｚ曲線の係数）である。
【請求項８】
入力部を介して、入力されたデータから暗号化データを生成する暗号化装置であって、
前記入力されたデータと、Ｋｏｂｌｉｔｚ曲線のスカラー倍点を用いて暗号化データを生成する暗号部と、前記スカラー倍点を計算するスカラー倍計算部と、
を有し、
前記スカラー倍計算部は、請求項１から請求項７のいずれか一項に記載のスカラー倍計算装置であることを特徴とする暗号化装置。
【請求項９】
入力部を介して、入力された暗号化データから復号化データを生成する復号化装置であって、
前記入力された暗号化データと、Ｋｏｂｌｉｔｚ曲線のスカラー倍点を用いて前記復号化データを生成する復号部と、
前記スカラー倍点を計算するスカラー倍計算部と、
を有し、
前記スカラー倍計算部は、請求項１から請求項７のいずれか一項に記載のスカラー倍計算装置であることを特徴とする復号化装置。
【請求項１０】
入力部を介して、入力されたデータから署名データを生成する署名生成装置であって、
前記入力されたデータと、Ｋｏｂｌｉｔｚ曲線のスカラー倍点を用いて前記署名データを生成する署名生成処理部と、
前記スカラー倍点を計算するスカラー倍計算部と、
を有し、
前記スカラー倍計算部は、請求項１から請求項７のいずれか一項に記載のスカラー倍計算装置であることを特徴とする署名生成装置。
【請求項１１】
前記署名生成装置は、演算装置を備える可搬型小型記憶媒体である
ことを特徴とする請求項１０に記載の署名生成装置。
【請求項１２】
入力された署名データを検証する署名検証装置であって、
前記入力された署名データと、Ｋｏｂｌｉｔｚ曲線のスカラー倍点を用いて前記署名データの検証を行う署名検証処理部と、
前記スカラー倍点を計算するスカラー倍計算部と、
を有し、
前記スカラー倍計算部は、請求項１から請求項７のいずれか一項に記載のスカラー倍計算装置であることを特徴とする署名検証装置。
【請求項１３】
楕円Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ鍵共有スキームを用いて、公開鍵の生成および送信を行う鍵交換装置であって、
請求項１から請求項７のいずれか一項に記載のスカラー倍計算装置であるスカラー倍計算部を有し、
前記スカラー倍計算部は、記憶部に格納されている秘密鍵と、Ｋｏｂｌｉｔｚ曲線上の点と、のスカラー倍点である第１のスカラー倍点を算出し、当該第１のスカラー倍点を公開鍵とし、
前記公開鍵を外部から取得すると、記憶部に格納されている秘密鍵と、前記取得した公開鍵と、のスカラー倍点である第２のスカラー倍点を算出し、当該第２のスカラー倍点から共有情報を取得する
ことを特徴とする鍵交換装置。
【請求項１４】
入力部を介して入力されたＫｏｂｌｉｔｚ曲線上の点の座標およびスカラー値を基に、前記Ｋｏｂｌｉｔｚ曲線上におけるスカラー倍点の座標を算出するスカラー倍計算装置によるスカラー倍計算方法であって、
前記スカラー倍計算装置は、
記憶部と、処理部と、を有し、
前記記憶部は、
τ−ＮＡＦ変換された第１の符号列と、第１の符号列より短い符号長を有し、かつτ−ＮＡＦ表現において前記第１の符号列と同一の値を有する第２の符号列と、を有している変換情報を格納しており、
前記処理部が、
入力された前記スカラー値を前記第１の符号列に変換し、
前記変換情報を基に、前記第１の符号列に対応する第２の符号列を取得し、
前記取得した第２の符号列を前記スカラー値の符号列として出力し、
前記出力された第２の符号列と、前記入力されたＫｏｂｌｉｔｚ曲線上の点の座標と、を基に、前記Ｋｏｂｌｉｔｚ曲線上の点を前記スカラー値の値でスカラー倍した前記スカラー倍点の座標を算出する
ことを特徴とするスカラー倍計算方法。
【請求項１５】
入力部を介して入力されたＫｏｂｌｉｔｚ曲線上の点の座標およびスカラー値を基に、前記Ｋｏｂｌｉｔｚ曲線上におけるスカラー倍点の座標を算出するスカラー倍計算装置によるスカラー倍計算方法であって、
前記スカラー倍計算装置は、
記憶部と、処理部と、を有し、
前記記憶部は、
所定の符号列をτ進複素数表現した値と、前記τ進複素数表現に対応している第３の符号列と、を有している変換情報を格納しており、
前記処理部が、
（ａ１）前記入力されたスカラー値を前記τ進複素数表現にした値へ変換し、
（ａ２）前記変換されたτ進複素数表現が、前記変換情報に格納されていない場合、第４の符号列にτ−ＮＡＦ変換した符号を１つ追加し、
（ａ３）前記τ進複素数表現の実部および虚部の値を予め設定されている第１の方法に従って更新し、
（ａ４）前記変換されたτ進複素数表現が、前記変換情報に格納されている場合、前記変換情報から、前記τ進複素数表現に対応する前記第３の符号列を取得し、前記前記τ進複素数表現の実部および虚部の値に、０を代入し、
（ａ５）前記更新された前記τ進複素数表現の実部および虚部の値が、共に０となるまで、前記（ａ２）〜（ａ４）の処理を繰り返し、
（ａ６）前記τ進複素数表現の実部および虚部の値が、共に０となった場合、前記第４の符号列の上位の桁に、前記第３の符号列を追加した第５の符号列を、前記スカラー値の符号列として出力し、
前記出力された第５の符号列と、前記入力されたＫｏｂｌｉｔｚ曲線上の点の座標と、を基に、前記Ｋｏｂｌｉｔｚ曲線上の点を前記スカラー値の値でスカラー倍した前記スカラー倍点の座標を算出する
ことを特徴とするスカラー倍計算方法。
【請求項１６】
入力部を介して入力されたＫｏｂｌｉｔｚ曲線上の点の座標およびスカラー値を基に、前記Ｋｏｂｌｉｔｚ曲線上におけるスカラー倍点の座標を算出するスカラー倍計算装置によるスカラー倍計算方法であって、
前記スカラー倍計算装置は、
記憶部と、処理部と、を有し、
前記記憶部は、
前記入力部を介して入力された前記スカラー値を２進表現でビット列を、予め設定されている第２の方法で変換した第６の符号列と、前記第６の符号列に対応している第７の符号列と、を有している変換情報を格納しており、
前記処理部が、
（ｂ１）前記スカラー値が２進表現のビット列として入力され、
（ｂ２）前記ビット列の最大桁数が６桁以上であり、かつ現在計算している桁が上位６桁以外である場合、予め設定されている第３の方法に従って（１，０、−１）の３値のうちのいずれかの符号を生成し、当該生成した符号を第８の符号列に追加し、現在計算している桁が上位６桁以内となるまで、前記（ｂ２）の処理を繰り返し、
（ｂ３）前記ビット列の最大桁数が６桁未満である、または現在計算している桁が上位６桁以内である場合、前記ビット列のうち、現在している桁以下７桁の符号列を、前記第２の方法で変換した第９の符号列が、前記変換情報に格納されている第６の符号列のいずれかと一致するか否かを判定し、
（ｂ４）前記判定の結果、前記第９の符号列が、前記変換情報に格納されている第６の符号列のうちのいずれとも一致しない場合、予め設定されている第４の方法に従って（１，０、−１）の３値のうちのいずれかの符号を生成し、当該生成した符号を第８の符号列に追加し、現在計算している桁が前記ビット列の最大桁数より大きくなるまで、前記（ｂ４）の処理を繰り返し、
（ｂ５）前記判定の結果、前記第９の符号列が、前記変換情報に格納されている第６の符号列のいずれかと一致する場合、前記変換情報から、前記第９の符号列に対応する前記第７の符号列を取得し、前記第８の符号列の上位の桁に前記第７の符号列を追加した第１０の符号列を、前記スカラー値の符号列として出力し、
前記出力された第１０の符号列と、前記入力されたＫｏｂｌｉｔｚ曲線上の点の座標と、を基に、前記Ｋｏｂｌｉｔｚ曲線上の点を前記スカラー値の値でスカラー倍した前記スカラー倍点の座標を算出する
ことを特徴とするスカラー倍計算方法。
【請求項１７】
請求項１４から請求項１６のいずれか一項に記載のスカラー倍計算方法をコンピュータに実行させることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、Ｋｏｂｌｉｔｚ曲線のスカラー倍計算におけるスカラー倍計算装置、暗号化装置、復号化装置、署名生成装置、署名検証装置、鍵交換装置、スカラー倍計算方法およびプログラムの技術に関する。
【背景技術】
【０００２】
楕円曲線暗号はN. Koblitz、V. S. Millerにより提案された公開鍵暗号の一種である。公開鍵暗号には、公開鍵（Public Key）と呼ばれる一般に公開してよい情報と、秘密鍵（Private Key）と呼ばれる秘匿しなければならない秘密情報がある。そして、与えられたメッセージの暗号化や署名の検証には公開鍵を用い、与えられたメッセージの復号化や署名の生成には秘密鍵を用いる。
【０００３】
楕円曲線暗号における秘密鍵はスカラー値を用いる。また、楕円曲線暗号の安全性は楕円曲線上の離散対数問題の求解が困難であることに由来している。楕円曲線上の離散対数問題とは、楕円曲線上のある点Ｐとそのスカラー倍の点ｄＰが与えられた時、スカラー値ｄを求める問題である。楕円曲線上の点とは、楕円曲線の定義方程式を満たす数の組をいい、楕円曲線上の点全体には、無限遠点という仮想的な点を単位元とした演算、すなわち楕円曲線上の加法（または加算）が定義される。そして、同じ点同士による楕円曲線上の加法のことを、特に楕円曲線上の２倍算という。
【０００４】
楕円曲線上の２点の加法は次のようにして計算される。２点を通る直線を引くとその直線は楕円曲線と他の点において交わる。その交わった点とｘ軸に関して対称な点を、加法を行った結果の点とする。
例えば、有限体Ｆ２ｒ上に定義されたワイエルシュトラス型楕円曲線（以後、楕円曲線Ｅと呼ぶ。）の場合には、点（ｘ１，ｙ１）と点（ｘ２，ｙ２）とを加算した結果の点（ｘ３，ｙ３）（（ｘ３，ｙ３）＝（ｘ１，ｙ１）＋（ｘ２，ｙ２））は、以下の式（１）〜（３）を計算することにより得られる。
【０００５】
ｘ３＝λ２＋λ＋ｘ１＋ｘ２＋ａ  ・・・  式（１）
ｙ３＝（ｘ１＋ｘ３）λ＋ｘ３＋ｙ１  ・・・  式（２）
λ＝（ｙ２＋ｙ１）／（ｘ２＋ｘ１）  ・・・  式（３）
【０００６】
ここで、楕円曲線Ｅ／Ｆ２ｒの定義方程式は、以下の式（４）で与えられる。
【０００７】
ｙ２＋ｘｙ＝ｘ３＋ａｘ２＋ｂ，（ａ，ｂはともに有限体Ｆ２ｒの元）  ・・・  式（４）
【０００８】
なお、式（１）〜（３）における点（ｘ１，ｙ１）と点（ｘ２，ｙ２）と点（ｘ３，ｙ３）はいずれも楕円曲線Ｅ上の点である。すなわち、式（４）のｘ，ｙに各々ｘｉ，ｙｉ（ｉ＝１，２，３）を代入しても、式（４）の等式が成り立つ。
また、有限体Ｆ２ｒは式（４）で与えられる楕円曲線Ｅの定義体と呼ばれる。ここで、ｒは正の整数である。
以後、正の整数ｒは、ｒ＝１とする。
【０００９】
また、以後、楕円曲線暗号に用いる可換群としてＥ（Ｆ２ｍ）を考える。ただし、Ｅ（Ｆ２ｍ）は、式（４）の定義方程式で与えられる楕円曲線であり、楕円曲線上の各点Ｐ＝（ｘ，ｙ）に対して、ｘ，ｙがともにＦ２ｍの元であることを意味し、ｍは拡大次数と呼ばれる自然数である。以後、ｍは、Ｅ（Ｆ２ｍ）の要素数＃Ｅ（Ｆ２ｍ）＝ｈ×ｎ（ｈ：小さな整数、ｎ：大きな素数）を満たすような奇素数とする。
【００１０】
楕円曲線上の点の２倍算は次のようにして計算される。楕円曲線上の点における接線をひくと、その接線は楕円曲線上の他の一点において交わる。その交わった点とｘ座標に関して対称な点を、２倍算を行った結果の点とする。例えば、楕円曲線Ｅの場合には、点（ｘ１，ｙ１）の２倍算を行った結果の点（ｘ３，ｙ３）（（ｘ３，ｙ３）＝２（ｘ１，ｙ１）＝（ｘ１，ｙ１）＋（ｘ１，ｙ１））は、以下の式（５）〜（７）を計算することにより得られる。
【００１１】
ｘ３＝λ２＋λ＋ａ  ・・・  式（５）
ｙ３＝ｘ１２＋λｘ３＋ｘ３  ・・・  式（６）
λ＝ｘ１＋ｙ１／ｘ１  ・・・  式（７）
【００１２】
しかしながら、式（５）〜（７）の計算では、処理負荷の高い乗算が３回使用され、さらに乗算より処理負荷の高い除算が１回使用されている。
このような処理負荷の軽減のために、Ｋｏｂｌｉｔｚ曲線と呼ばれる楕円曲線Ｅ上の点に対して、フロベニウス写像τと呼ばれる自己準同型写像を施すことが可能である。
点（ｘ１，ｙ１）に対してフロベニウス写像τを施すとは、以下の式（８）を計算することである。
【００１３】
τ（ｘ１，ｙ１）＝（ｘ１２，ｙ１２）  ・・・  式（８）
【００１４】
式（８）によれば、乗算を２回までに軽減することが可能である。
また、以下の式（９）が成り立つことが知られている。
【００１５】
（ｘ４，ｘ４）＋２（ｘ，ｙ）＝ｔ（ｘ２，ｙ２）  ・・・  式（９）
【００１６】
そして、式（９）の性質によりτを、以下の式（１０）を満たす複素数と考えることができる。
【００１７】
τ２＋２＝μτ  ・・・  式（１０）
【００１８】
ここで、式（９）のｔは式（４）で与えられるＫｏｂｌｉｔｚ曲線Ｅのトレースと呼ばれる整数であり、式（４）の係数ａを用いてμ＝（−１）１−ａと書けることが知られている（例えば、非特許文献１参照）。
【００１９】
楕円曲線Ｅ上の点（ｘ１，ｙ１）に対してフロベニウス写像τを施した点τ（ｘ１，ｙ１）＝（ｘ１２，ｙ１２）もＫｏｂｌｉｔｚ曲線Ｅ上の点であることが知られている。
前記したように、ある点に対し、特定の回数だけ加法を行うことをスカラー倍といい、その結果の点をスカラー倍点、その回数のことをスカラー値という。
楕円曲線暗号においては、与えられたメッセージの暗号化、復号化、署名の生成、および、その検証は、楕円曲線演算を用いて行う。その中で楕円曲線上のスカラー倍の計算は、前記の暗号化、復号化などの各処理において最も処理時間を要する計算である。そのため、楕円曲線暗号を高速に実行するためには、楕円曲線上のスカラー倍計算を高速に行う必要がある。特に、楕円曲線暗号において、スカラー値はおよび２１６０といったオーダとなり、計算時間の高速化の必要性が高い。
【００２０】
最も基本的な楕円曲線のスカラー倍計算方法であるバイナリ法では、スカラー値の２進展開を左から右に向けて（または右から左に向けて）各桁を見て、零でない（非零）場合に楕円曲線上の加算を行い、桁をずらすことで楕円曲線上の２倍算を行う。
【００２１】
これに対し、フロベニウス写像を実行することができる楕円曲線上のスカラー倍計算では、桁をずらすために楕円曲線上の２倍算を行う代わりにフロベニウス写像を用いることができることが知られている。フロベニウス写像は、楕円曲線暗号実装の際に、楕円曲線上の点を、正規基底を用いて実装した場合、シフト演算のみを用いて計算でき、２倍算に比べて処理が高速である（多項式基底、および、正規基底については、例えば、非特許文献１参照）。
【００２２】
従って、楕円曲線暗号実装の際に楕円曲線として、フロベニウス写像を持つ楕円曲線を採用し、フロベニウス写像を用いた展開（フロベニウス展開）を用いればスカラー倍計算の高速化が可能となる。
この性質を利用して、楕円曲線上のスカラー倍計算を高速に計算できる曲線の一つとしてＫｏｂｌｉｔｚ曲線が知られている（例えば、非特許文献１参照）。
また、２倍算を減らすだけでなく、スカラー倍計算の際に必要な楕円曲線上の加算回数自体を低減することにより、スカラー倍計算を高速化できる。楕円曲線上のスカラー倍計算では、前記したように、非零の場合に加算が行われるため、非零濃度を最小とすることにより、高速化する方法がある。ここで、非零濃度とは、（非零桁の個数）／（展開の桁長）の漸近的な値を指す。一般に、与えられたスカラー値に対して、ある展開における非零濃度が最小のとき、その展開を用いたスカラー倍計算は、スカラー倍計算に関して高速化されることは、前記のように知られている。
【００２３】
この性質を利用して楕円曲線上のスカラー倍計算を高速に行う手法の一つとして、与えられたスカラー値に対して、予め定められた整数を用いてエンコードした場合のスカラー値の非零濃度が最小となる展開（ＮＡＦ（Non-Adjacent Form））を行うことにより、楕円曲線上のスカラー倍計算の高速化を図る方法がある（例えば、非特許文献２参照）。
さらに、前記したフロベニウス展開と小さな非零濃度をもつ展開を同時に実現することにより、さらなる高速化を図る方法としてＫｏｂｌｉｔｚ曲線におけるτ−ＮＡＦが知られている（非特許文献１参照）。また、このτ−ＮＡＦは非零濃度が最小であることが知られている（非特許文献３参照）。
また、与えられたスカラー値のビット表現からτ-ＮＡＦにエンコードする処理には比較的重い処理が含まれているため、τ−ＮＡＦにエンコードする際に比較的重い処理を排除するエンコード方法がある（例えば、特許文献１および非特許文献２参照）。
【先行技術文献】
【特許文献】
【００２４】
【特許文献１】米国特許出願公開第２００４／０１１９６１４号明細書
【非特許文献】
【００２５】
【非特許文献１】J. A. Solinas, Efficient Arithmetic on Koblitz Curves, Designs, Codes and Cryptography, Vol.19, No.2-3, Kluwer Academic Publishers, pp. 195 - 249, 2000.
【非特許文献２】M. Joye, and C. Tymen, Compact Encoding of Non-Adjacent Forms with Applications to Elliptic Curve Cryptography, In 4th International Workshop on Practice and Theory in Public Key Cryptography(PKC 2001), Vol.1992 of Lecture Notes in Computer Science, pp. 353 - 364, Springer-Verlag, 2001.
【非特許文献３】R. M. Avanzi, C. Heuberger, and H. Prodinger, Minimality of the Hamming Weight of the τ-NAF for Koblitz Curves and Improved Combination with Point Halving, In Selected Areas in Cryptography - SAC 2005, Vol.3897 of Lecture Notes in Computer Science, pp. 332 - 344, Springer-Verlag, 2006.
【発明の概要】
【発明が解決しようとする課題】
【００２６】
情報通信ネットワークの進展と共に電子情報に対する秘匿や認証の為に暗号技術は不可欠な要素となってきている。暗号技術に課せられる要件としては、安全性以外にも、処理速度やメモリ使用量などがある。しかし、一般に安全性、処理速度、メモリ使用量の間にはトレードオフの関係があり、すべての要件を満たすことは難しい。
一般に、暗号に用いられる鍵の長さ（鍵長）は安全性の指標とされ、長いほど安全性が高くなることが知られている。しかしながら、鍵長が長いほど処理に時間がかかる。
【００２７】
楕円曲線上の離散対数問題の求解の困難性は素因数分解の困難性に比べて高いため、素因数分解の困難性を安全性の根拠にしている暗号と比べて、楕円曲線暗号は鍵長を比較的短くすることができる。従って、楕円曲線暗号によれば、計算能力、メモリ容量などのリソースが比較的少なくても、素因数分解問題の困難性を利用する暗号処理と同等の安全性を有する暗号処理を短時間の処理、すなわち、リソースへの負担が少ない処理で実現することが可能である。
【００２８】
最近では、スマートカード（ＩＣ（Integrated Circuit）カードともいう）など、利用可能なリソースがかなり限られている環境においても、安全性の高い暗号処理の必要性が高まっている。スマートカードのようなリソースの少ない環境では、限られたリソース内で暗号処理の最適化を図る必要がり、安全性を高めるために鍵長を長くすると処理負担の増大が大きくなるため、さらにリソースへの負担の少ない高速な処理が求められている。
非特許文献１には、入力された整数を、最小な非零濃度をもつフロベニウス展開τ−ＮＡＦに変換し、このτ−ＮＡＦを用いたＫｏｂｌｉｔｚ曲線におけるスカラー倍計算方法が記載されている。しかし、一回のフロベニウス写像は高速に処理できるが、τ−ＮＡＦの展開の長さの低減まで考慮されていない。
【００２９】
また、特許文献１および非特許文献２には、入力された整数を、予め定められた変換テーブルを利用して最小な非零濃度をもつフロベニウス展開τ−ＮＡＦに変換し、このτ−ＮＡＦを用いたＫｏｂｌｉｔｚ曲線におけるスカラー倍計算方法が記載されている。しかし、一回のフロベニウス写像は高速に処理できるが、τ−ＮＡＦの展開の長さの低減まで考慮されていない。
すなわち、Ｋｏｂｌｉｔｚ曲線上での従来のスカラー倍計算においては、Ｋｏｂｌｉｔｚ曲線上の加算回数の最小化は実現されているが、フロベニウス写像の回数の最小化を実現することが可能なものはない。
【００３０】
このような背景に鑑みて本発明がなされたのであり、本発明は、リソースが限られた環境で、安全性を低下させることなく、τ−ＮＡＦなどのＫｏｂｌｉｔｚ曲線上での従来のスカラー倍計算より高速であり、かつＫｏｂｌｉｔｚ曲線上の最小な加算回数と最小なフロベニウス写像の回数で処理可能なＫｏｂｌｉｔｚ曲線演算技術を実現することを目的とする。
【課題を解決するための手段】
【００３１】
前記課題を解決するため、本発明は、第１の符号列と、この第１の符号列と同値であり、かつ予め最小な加算回数で処理でき、かつ最小なフロベニウス写像の回数で処理可能な第２の符号列と、を対応付けて格納している変換情報を記憶部に有しており、入力されたスカラー値を第１の符号列に変換した後、前記変換情報に従って、前記第１の符号列を前記第２の符号列へ変換することを特徴とする。
その他の解決手段については、実施形態中で適宜説明する。
【発明の効果】
【００３２】
本発明によれば、リソースが限られた環境で、安全性を低下させることなく、τ−ＮＡＦなどのＫｏｂｌｉｔｚ曲線上での従来のスカラー倍計算より高速であり、かつＫｏｂｌｉｔｚ曲線上の最小な加算回数と最小なフロベニウス写像の回数で処理可能な楕円曲線演算技術を実現することができる。
【図面の簡単な説明】
【００３３】
【図１】本実施形態の暗号通信システムのシステム構成図である。
【図２】本実施形態に係るスカラー倍計算部の構成例を示す図である。
【図３】第１実施形態に係る変換テーブルの構成を示す図である。
【図４】第１実施形態に係るメッセージ暗号化処理について説明するタイミングチャートである。
【図５】第１実施形態に係るメッセージ復号化処理について説明するタイミングチャートである。
【図６】第１実施形態に係るエンコード処理の流れを示すフローチャートである。
【図７】第１実施形態に係る実計算処理の流れを示すフローチャートである。
【図８】第２実施形態に係る変換テーブルの構成例を示す図である。
【図９】第２実施形態に係るエンコード処理の流れを示すフローチャートである。
【図１０】第３実施形態に係るスカラー倍計算部の構成例を示す図である。
【図１１】第３実施形態に係る変換テーブルの構成例である。
【図１２】第３実施形態に係るエンコード処理の流れを示すフローチャートである（その１）。
【図１３】第３実施形態に係るエンコード処理の流れを示すフローチャートである（その２）。
【図１４】第４実施形態に係る署名検証システムのシステム構成図である。
【図１５】第４実施形態に係るメッセージの署名生成処理について説明するタイミングチャートである（その１）。
【図１６】第４実施形態に係るメッセージの署名検証処理について説明するタイミングチャートである（その２）。
【図１７】第５実施形態に係る鍵交換システムの構成例を示す図である。
【図１８】第５実施形態に係る鍵交換処理について説明するタイミングチャートである。
【発明を実施するための形態】
【００３４】
次に、本発明を実施するための形態（「実施形態」という）について、適宜図面を参照しながら詳細に説明する。なお、各図において、同様の構成要素に対しては同一の符号を付して説明を省略することとする。
本実施形態における計算方法は、スカラー値のτ−ＮＡＦ表現を、非零濃度を変えることなく長さが最小となるエンコード方法であり、以下、このエンコード方法をτ−ＭＬＦ（τ-adic Minimal Length Form）と称し、τ−ＭＬＦによる数値列をτ−ＭＬＦ表現の数値列と称することとする。
【００３５】
《第１実施形態》
まず、図１〜図７を参照して、本発明に係る第１実施形態を説明する。
【００３６】
（システム構成）
図１は、本実施形態の暗号通信システムのシステム構成図である。
暗号通信システムＡは、ネットワーク６により接続された暗号化コンピュータ１Ａおよび復号化コンピュータ１Ｂとを備える。
【００３７】
本実施形態の暗号通信システムＡにおいては、暗号化コンピュータ１ＡでメッセージＰｍの暗号化を行い、復号化コンピュータ１Ｂで暗号メッセージの復号を行う。ここで、暗号化コンピュータ１Ａおよび復号化コンピュータ１Ｂは、それぞれ専用のコンピュータという意味ではなく、実行されるプログラムによるものである。つまり、実行されるプログラムによっては、暗号化コンピュータ１Ａが復号化コンピュータ１Ｂにもなり得るし、復号化コンピュータ１Ｂが暗号化コンピュータ１Ａにもなり得る。
【００３８】
図１において、暗号化コンピュータ１Ａおよび復号化コンピュータ１Ｂは、ＣＰＵ（Central Processing Unit）２１Ａ，２１Ｂやコプロセッサ２２Ａ，２２Ｂなどの演算装置（処理部２Ａ，２Ｂ）、ＲＡＭ（Random Access Mmory)３１Ａ，３１Ｂ、ＲＯＭ（Read Only Memory）３４Ａ，３４Ｂや外部記憶装置３５Ａ，３５Ｂなどの記憶装置（記憶部３Ａ（３），３Ｂ（３））、コンピュータ外部とのデータ入出力を行う入出力インタフェース（入力部）４Ａ，４Ｂを有している。さらに、暗号化コンピュータ１Ａおよび復号化コンピュータ１Ｂは、外部にユーザが操作するためのキーボード６Ａ，６Ｂおよびディスプレイ５Ａ，５Ｂ、着脱可能な可搬型記憶媒体の読書装置（図示せず）などが接続されている。
【００３９】
さらに、暗号化コンピュータ１Ａでは、外部記憶装置３５Ａに格納されているデータ処理部３２Ａや、スカラー倍計算部３３Ａ（３３）のプログラムがＲＡＭ３１Ａに展開され、ＣＰＵ２１Ａやコプロセッサ２２Ａなどの演算装置によって実行されている。
データ処理部３２Ａは、第１実施形態〜第３実施形態においては、暗号化処理部として機能し、入力されたメッセージの暗号化を行う。
スカラー倍計算部３３Ａは、データ処理部３２Ａで暗号化を行うのに必要なパラメタを計算する。スカラー倍計算部３３Ａの詳細な構成は図２を参照して説明する。
なお、暗号化コンピュータ１Ａの外部記憶装置３５Ａには、図３、図８、図１１を参照して後記する変換テーブル（変換情報）３６Ａ（３６）や、秘密情報３７Ａ（例えば、秘密鍵）や、定数３８Ａ（例えば、公開鍵や、Ｋｏｂｌｉｔｚ曲線の定義式や、Ｋｏｂｌｉｔｚ曲線上の定点）などが格納されている。
【００４０】
ｋは乱数、ｄは秘密鍵を示す定数、ＱはＫｏｂｌｉｔｚ曲線上の定点、ｄＱは公開鍵を示す点とすると、暗号化コンピュータ１Ａは、Ｐｍ＋ｋ（ｄＱ）およびｋＱを計算して出力する機能を有している。そして、復号化コンピュータ１Ｂは、秘密鍵ｄ、および、ｋＱより−ｄ（ｋＱ）を計算し、式（１１）を計算して出力する機能を有している。
【００４１】
（Ｐｍ＋ｋ（ｄＱ））-ｄ（ｋＱ）  ・・・  式（１１）
【００４２】
ここで、メッセージＰｍを復元するためには、ｋｄＱ、すなわちｋＱのｄ倍を計算する必要がある。ところが、暗号通信システムＡのネットワーク６には、Ｐｍ＋ｋ（ｄＱ）、ｋＱのみ送信され、秘密鍵ｄは送信されないため、秘密鍵ｄを保持しているものだけが、Ｐｍを復元できることになる。
【００４３】
また、復号化コンピュータ１Ｂでは、外部記憶装置３５Ｂに記憶されているデータ処理部３２Ｂや、スカラー倍計算部３３Ｂ（３３）のプログラムがＲＡＭ３１Ｂに展開され、ＣＰＵ２１Ｂやコプロセッサ２２Ｂなどの演算装置によって実行されている。
データ処理部３２Ｂは、復号化コンピュータ１Ｂにおいては、復号化処理部として機能し、暗号化されたメッセージである暗号メッセージの復号を行う。
スカラー倍計算部３３Ｂは、データ処理部３２Ｂで復号化を行うのに必要なパラメタを計算する。スカラー倍計算部３３Ｂの詳細な構成は図２を参照して説明する。
なお、暗号化コンピュータ１Ｂの外部記憶装置３５Ｂには、図３、図８、図１１を参照して後記する変換テーブル３６Ｂ（３６）や、秘密情報３７Ｂ（例えば、秘密鍵）や、定数３８Ｂ（例えば、公開鍵や、使用するＫｏｂｌｉｔｚ曲線の定義式やＫｏｂｌｉｔｚ曲線上の定点）などが格納などが記憶されている。
なお、定数３８Ａおよび定数３８Ｂには、共通のＫｏｂｌｉｔｚ曲線上の定点Ｑが格納されている。
【００４４】
なお、データ処理部３２Ａ，３２Ｂや、スカラー倍計算部３３Ａ，３３Ｂのプログラムは、予めコンピュータ内の外部記憶装置３５Ａ，３５Ｂや、図示しないフラッシュメモリなどに格納されていてもよいし、必要な時に、入出力インタフェース４Ａ，４Ｂおよび各コンピュータが利用可能な媒体を介して、他の装置から外部記憶装置３５Ａ，３５Ｂに記憶されてもよい。ここで、媒体とは、例えば、入出力インタフェース４Ａ，４Ｂに着脱可能な記憶媒体、または通信媒体（すなわち、ネットワーク６またはネットワーク６を伝搬する搬送波）を指す。
【００４５】
（スカラー倍計算部構成）
図２は、本実施形態に係るスカラー倍計算部の構成例を示す図である。なお、図２に示す構成は、図１における暗号化コンピュータ１Ａおよび復号化コンピュータ１Ｂにおいて、共通の構成である。
スカラー倍計算部３３は、スカラー値およびＫｏｂｌｉｔｚ曲線上の定点を入力とし、スカラー倍点を出力するものであり、エンコード部３００と、実計算部３５０とを備える。
そして、エンコード部３００は、τ−ＮＡＦ計算部３０１、τ−ＮＡＦ長計算部３０２、格納部３０３、δ剰余計算部３０４、条件判定部３０５、τ−ＭＬＦ計算部３０６を備える。また、実計算部３５０は、加算部３５１、τ倍算部３５２、繰り返し判定部３５３、数値判定部３５４を有する。各部３０１〜３０６，３５１〜３５４の機能については、処理の説明において後記する。
【００４６】
（変換テーブル）
図３は、第１実施形態に係る変換テーブルの構成を示す図である。
変換テーブル３６ａ（３６）は、左から変換前の数値列（τ−ＮＡＦ表現の数値列：第１の符号列）、変換後の数値列（τ−ＭＬＦ表現の数値列：第２の符号列）、変換後の桁数を示している。
【００４７】
図３の変換テーブル３６ａの１列目には、６桁のτ−ＮＡＦ表現の数値列（ｅｎ−１，ｅｎ−２，ｅｎ−３，ｅｎ−４，ｅｎ−５，ｅｎ−６）τのすべてのパターンが記載されている。ここで対象となる数値列は、スカラー値をτ−ＮＡＦ変換した数値列のうち、上位６桁が対象となるものである。
２列目には、１列目の同一行に記載されている６桁のτ−ＮＡＦ表現の数値列（ｅｎ−１,ｅｎ−２，ｅｎ−３，ｅｎ−４,ｅｎ−５,ｅｎ−６）τに対応するτ−ＭＬＦの数値列（ｇｍ−１，・・・，ｇｎ−６）τが記載されている。
そして、３列目には、１列目の同一行に記載されている６桁のτ−ＮＡＦ表現（ｅｎ−１，ｅｎ−２，ｅｎ−３，ｅｎ−４，ｅｎ−５，ｅｎ−６）τを２列目の同一行に記載されているτ−ＭＬＦ（ｇｍ−１，・・・，ｇｎ−６）τに変換した場合の桁数ｍの値が記載されている。３列目におけるｎは、τ−ＮＡＦ表現の数値列の全桁数である。
【００４８】
例えば、符号４０１の数値列などは無変換である。つまり、桁数を減ずることはできない。しかしながら、例えば符号４０２の数値列は、数値列が示す数値を保ったまま、２桁減ずることができる。
【００４９】
ここで、図３の変換テーブル３６ａに記載されているμは式（１０）を満たす整数である。図３の変換テーブル３６ａを用いて６桁のτ−ＮＡＦ表現の数値列（ｅｎ−１，ｅｎ−２，ｅｎ−３，ｅｎ−４，ｅｎ−５，ｅｎ−６）τからτ−ＭＬＦ（ｇｍ−１，・・・，ｇｎ−６）τへ変換する方法を説明する。例えば、行４０２に示されている６桁のτ−ＮＡＦ表現の数値列（±μ，０，０，±１，０，０）τを変換する場合、エンコード部３００（図２）は以下の変換を行う。
【００５０】
【数１】
2011081147.tif 000003
【００５１】
この場合、６桁のτ−ＮＡＦ表現をτ−ＭＬＦに変換すると、２桁分短くなっているので、τ−ＭＬＦの長さｍ＝ｎ−２となる。
【００５２】
なお、τ−ＭＬＦの長さｍは２列目のτ−ＭＬＦから計算することが可能なので、３列目を変換テーブル３６ａに記載しなくてもよい。また、３列目のｍがｎ＝ｍであれば同一行に記載されている６桁のτ−ＮＡＦ表現とτ−ＭＬＦ表現は一致するため、ｎ＝ｍを満たす６桁のτ−ＮＡＦ表現とτ−ＭＬＦ表現は変換テーブル３６ａに記載せず、ｍがｎ−３≦ｍ≦ｎ−１の場合のみの数値の対を変換テーブル３６ａに記載するようにしてもよい。また、変換テーブル３６ａにおいて、ｍがｎ−３≦ｍ≦ｎ−１となるτ−ＮＡＦ表現とτ−ＭＬＦ表現の対をすべて記載する必要はなく、少なくとも一つ以上を変換テーブル３６ａに記載し、後記するステップＳ２０５において、変換テーブル３６ａに記載されている６桁のτ−ＮＡＦ表現の数値列のみを、τ−ＭＬＦ表現の数値列に変換するようにしてもよい。
【００５３】
（情報の送受信）
次に、図１および図２を参照しつつ、図４および図５に沿ってメッセージの暗号化処理および復号化処理の概要を説明する。
図４および図５は、メッセージの暗号化処理および復号化処理を行う場合における暗号化コンピュータ１Ａおよび復号化コンピュータ１Ｂ内の情報の送受信について説明するタイミングチャートである。
まず、暗号化コンピュータ１Ａが、入力されたメッセージを暗号化する場合の動作について図４を参照して説明する。メッセージはディジタル化されたデータであればよく、テキスト、画像、映像、音などの種類は問わない。
まず、データ処理部３２Ａは、入出力インタフェース４Ａを介して、平文メッセージ（入力メッセージ）を取得する（Ｓ１０１）。
そして、データ処理部３２Ａは、入力された平文メッセージのビット長があらかじめ定めたビット長か否かを判断する。平文メッセージのビット長が、予め定めたビット長よりも長い場合、データ処理部３２Ａは、予め定めたビット長となるように平文メッセージを区切り、部分メッセージを生成する（Ｓ１０２）。以下、メッセージとは、所定のビット長に区切られている部分メッセージであるものとして説明する。
【００５４】
次に、データ処理部３２Ａは、メッセージのビット列によって表される数値をｘ座標（ｘ１）に持つＫｏｂｌｉｔｚ曲線上の定点Ｐｍのｙ座標（ｙ１）の値を計算する（Ｓ１０３）。
ここで、使用する楕円曲線をＫｏｂｌｉｔｚ曲線とすると、Ｋｏｂｌｉｔｚ曲線は、ａを定数とするとき、式（１２）で表されるので、データ処理部３２Ａは、この式（１２）よりｙ座標の値を求めることができる。
【００５５】
ｙ２＋ｘｙ＝ｘ３＋ａｘ２＋１  ・・・  式（１２）
【００５６】
次に、データ処理部３２Ａは、乱数ｋを生成する（Ｓ１０４）。そして、データ処理部３２Ａは、記憶部３Ａ（具体的には外部記憶装置３５Ａ）に格納されている定数３８Ａから公開鍵ｄＱと、Ｋｏｂｌｉｔｚ曲線上の定点Ｑのｘ座標とを取得する（Ｓ１０５）。
そして、データ処理部３２Ａは、読み出した公開鍵ｄＱとＱのｘ座標と、求めたｙ座標の値（Ｋｏｂｌｉｔｚ曲線上の定点）と、乱数ｋ（スカラー値）とをスカラー倍計算部３３Ａへ送る（Ｓ１０６）。
スカラー倍計算部３３Ａのエンコード部３００（図２）が、ｋのτ−ＭＬＦ表現の数値列を計算するエンコード処理を行い（Ｓ１０７）、実計算部３５０が、ｋのτ−ＭＬＦ表現の数値列を使用して、Ｑのｘ座標、ｙ座標の値、乱数ｋによるスカラー倍点（ｘｄ１，ｙｄ１）＝ｋＱと、公開鍵ｄＱのｘ座標、ｙ座標の値、乱数ｋによるスカラー倍点（ｘｄ２，ｙｄ２）＝ｋ（ｄＱ）とを計算する実計算処理を行い（Ｓ１０８）、スカラー倍計算部３３Ａは、計算したスカラー倍点をデータ処理部３２Ａへ送る（Ｓ１０９）。エンコード処理は、図６、図９、図１２および図１３で後記する処理が行われる。また、実計算処理は、図７で後記する処理が行われる。
【００５７】
データ処理部３２Ａは、受け取ったスカラー倍点を用いて、暗号化処理を行う（Ｓ１１０）。Ｋｏｂｌｉｔｚ曲線の場合、Ｐｍ＋ｋ（ｄＱ）を計算するすなわち、データ処理部３２Ａは、以下の式（１３），（１４）を計算し、暗号化されたメッセージｘｅ１，ｘｅ２を得る。
【００５８】
ｘｅ１＝（（ｙｄ１＋ｙ１）／（ｘｄ１＋ｘ１））２＋（（ｙｄ１＋ｙ１）／（ｘｄ１＋ｘ１））＋ｘ１＋ｘｄ１＋ａ  ・・・  式（１３）
ｘｅ２＝ｘｄ２  ・・・  式（１４）
【００５９】
そして、データ処理部３２Ａは、１つ以上の部分メッセージから暗号化された出力メッセージを組み立て、この出力メッセージをデータとして入出力インタフェース４Ａから出力する（Ｓ１１１）。出力メッセージは、ネットワーク６を介して復号化コンピュータ１Ｂへ転送される。
【００６０】
なお、図４において記憶部３Ａからの情報の読み出し（Ｓ１０５）は、スカラー倍計算部３３Ａへ、当該情報を送る処理（Ｓ１０６）の前であればよい。例えば、入力メッセージを受け付ける（Ｓ１０１）の前であってもよい。
【００６１】
次に、復号化コンピュータ１Ｂが、暗号化されたメッセージである出力メッセージを復号化する場合の動作について、図５を用いて説明する。
復号化コンピュータ１Ｂのデータ処理部３２Ｂは、入出力インタフェース４Ｂを介して、暗号化コンピュータ１Ａによって暗号化されたメッセージを入力メッセージとして入力を受け付けると（Ｓ２０１）、入力メッセージのデータ１４１のビット長が予め定められているビット長か否かを判断する。予め定めたビット長よりも長い場合、データ処理部３２Ｂは、予め定めたビット長となるように暗号化されたデータを区切ることによって部分メッセージを生成する（Ｓ２０２）。以下、メッセージは、所定のビット長に区切られている部分データ（単にデータともいう）であるものとして説明する。
【００６２】
次に、データ処理部３２Ｂは、データ１４１のビット列によって表される数値をｘ座標にもつＫｏｂｌｉｔｚ曲線上のｙ座標の値を計算する（Ｓ２０３）。
暗号化されたメッセージがｘｅ１，ｘｅ２のビット列であり、Ｋｏｂｌｉｔｚ曲線の場合、ｙ座標の値（ｙｅ１）は、以下の式（１５）（ただし、ａは式（１２）と同じ定数である。）から得ることができる。
【００６３】
ｙｅ１２＋ｘｅ１ｙｅ１＝ｘｅ１３＋ａｘｅ１２＋１  ・・・  式（１５）
【００６４】
続いて、データ処理部３２Ｂは、記憶部３Ｂ（具体的には、外部記憶装置３５Ｂ）に格納されている秘密情報３７Ｂから秘密鍵ｄを読み出す（Ｓ２０４）。
そして、データ処理部３２Ｂは、読み出した秘密鍵ｄ（スカラー値）と、Ｋｏｂｌｉｔｚ曲線上の定点としてのｘ座標、ｙ座標の値（ｘｅ２，ｙｅ２）を、スカラー倍計算部３３Ｂへ送る（Ｓ２０５）。
スカラー倍計算部３３Ｂのエンコード部３００は、秘密鍵ｄのτ−ＭＬＦ表現の数値列を計算するエンコード処理を行い（Ｓ２０６）、秘密鍵ｄのτ−ＭＬＦ表現の数値列を用いて、Ｋｏｂｌｉｔｚ曲線上の定点のｘ座標、ｙ座標の値、秘密情報３７Ｂ（秘密鍵ｄ）のスカラー倍点（ｘｄ３，ｙｄ３）＝ｄ（ｘｅ２，ｙｅ２）を計算する実計算処理を行う（Ｓ２０７）。
その後、スカラー倍計算部３３Ｂは、計算されたスカラー倍点をデータ処理部３２Ｂへ送る（Ｓ２０８）。データ処理部３２Ｂは、送られたスカラー倍点を用いて、復号化処理を行う（Ｓ２０９）。
【００６５】
例えば、暗号化されたメッセージが、ｘｅ１，ｘｅ２のビット列であり、Ｋｏｂｌｉｔｚ曲線の場合、データ処理部３２Ｂが、以下の式（１６）を計算することにより復号化を達成できる。
【００６６】
（Ｐｍ＋ｋ（ｄＱ））-ｄ（ｋＱ）＝（ｘｅ１，ｙｅ１）−（ｘｄ３，ｙｄ３）  式（１６）
【００６７】
すなわち、データ処理部３２Ｂは以下の式（１７）を計算し、暗号化される前の部分メッセージｘ１に相当するｘｆ１を得る。
【００６８】
ｘｆ１＝（（ｙｅ１＋ｙｄ３）／（ｘｅ１−ｘｄ３））２＋（（ｙｅ１＋ｙｄ３）／（ｘｅ１−ｘｄ３））＋ｘｅ１＋ｘｄ３＋ａ  ・・・  式（１７）
【００６９】
復号化コンピュータ１Ｂは、データ処理部３２Ｂで復号された部分メッセージから平文メッセージを組み立て、入出力インタフェース４Ｂを介して、ディスプレイ５Ｂなどから出力メッセージとしての平文メッセージを出力する（Ｓ２１０）。
【００７０】
ここで、第１実施形態によるスカラー倍演算処理の詳細な説明に入る前に、スカラー倍計算部３３が、スカラー値ｄとＫｏｂｌｉｔｚ曲線上の定点Ｐとから、Ｋｏｂｌｉｔｚ曲線におけるスカラー倍点ｄＰを計算する第１の計算方法の概略を説明する。
【００７１】
本実施形態におけるスカラー倍計算処理は、Ｋｏｂｌｉｔｚ曲線上の定点とスカラー値とからスカラー倍点を計算するにあたり、スカラー値を第１の数値列（第１の符号列）にエンコードした後、さらに、第１の数値列とは異なる第２の数値列（第２の符号列）に、変換テーブル３６に従って変換し、第２の数値列を用いてスカラー倍点を計算する。このとき、第１の数値列は、τ−ＮＡＦ表現の数値列であり、第２の数値列は、τ−ＮＡＦ表現の数値列（第１の数値列）の上位６桁を予め定められた規則に従って変換した数値列（τ−ＭＬＦ表現の数値列）である。図３の変換テーブル３６ａで説明したように、第１の数値列の一部は、より数値列の長さが短い第２の数値列に変換することができる。
【００７２】
スカラー倍計算部３３は、この第２の数値列であるτ−ＭＬＦ表現の数値列とＫｏｂｌｉｔｚ曲線上の定点とを用いてスカラー倍計算を実行することにより、高速化を実現する。
第１実施形態のスカラー倍計算処理全体の概要は以下の通りである。
スカラー倍計算部３３がデータ処理部３２Ａ，３２Ｂからスカラー値ｄとＫｏｂｌｉｔｚ曲線上の定点Ｐとを受け取ると、エンコード部３００は、入力されたスカラー値ｄを数値列ｐｉにエンコードする。すなわち、式（１８），（１９）を満たすｐｉに、スカラー値ｄを変換する。
【００７３】
ｄｃ＝ｐ０＋ｐ１τ＋ｐ２τ２＋…＋ｐｑ−１τｑ−１  ・・・  式（１８）
−１≦ｐｉ≦１  ・・・  式（１９）
【００７４】
ここで、式（１８）の長さｑは前記した拡大次数ｍを用いて以下の式（２０）を満たす正整数である。
【００７５】
ｑ≦ｍ＋２  ・・・  式（２０）
【００７６】
また、ｄｃ＝ｒ０＋ｒ１τは以下の式（２１）を満たす複素数δに対して、式（２２）を満たす複素数であり、Ｑは複素数である。
【００７７】
δ＝（τｍ−１）／（τ−１）  ・・・  式（２１）
ｄ＝δＱ＋ｄｃ  ・・・  式（２２）
【００７８】
このとき、本実施形態では、０≦ｉ≦ｑ−７なる各ｉについて、隣り合う数値の対（ｐｉ＋１，ｐｉ）は以下の式（２３）を満たす。
【００７９】
ｐｉ＋１ｐｉ＝０  ・・・  式（２３）
【００８０】
そして、ｑ−６≦ｉ≦ｑ−１のとき、数値列（ｐｑ−１，ｐｑ−２，ｐｑ−３，ｐｑ−４，ｐｑ−５，ｐｑ−６）τは、図３の変換テーブル３６ａにおける（ｇｍ−１，・・・，ｇｎ−６）τのいずれか一つと等しい。
ここで、（ｐｑ−１，ｐｑ−２，ｐｑ−３，ｐｑ−４，ｐｑ−５，ｐｑ−６）τは、以下の式（２４）を意味する。
【００８１】
（ｐｑ−１，ｐｑ−２，ｐｑ−３，ｐｑ−４，ｐｑ−５，ｐｑ−６）τ＝ｐｎ−６＋ｐｎ−５τ＋ｐｎ−４τ２＋ｐｎ−３τ３＋ｐｎ−２τ４＋ｐｎ−１τ５  ・・・  式（２４）
【００８２】
実計算部３５０は、後に記載するエンコード処理によって、τ−ＭＬＦ表現にエンコードされたスカラー値ｄ＝（ｇｍ−１，ｇｍ−２，…，ｇ１，ｇ０）τとＫｏｂｌｉｔｚ曲線上の定点Ｐとを用いてスカラー倍点ｄＰを計算する。
【００８３】
（エンコード処理）
次に、図２および図３を参照しつつ、図６および図７に沿ってスカラー倍計算処理時のエンコード部３００、実計算部３５０の行う各処理について詳細に説明する。
図６は、第１実施形態に係るエンコード処理（図４のステップＳ１０７）の流れを示すフローチャートである。なお、図５のステップＳ２０６のエンコード処理も同様の処理手順である。
ここでは、スカラー値を第１の数値列（τ−ＮＡＦ表現の数値列）にエンコードし、さらに、第１の数値列を第２の数値列（τ−ＭＬＦ表現の数値列）にエンコードする処理を行う。
まず、エンコード部３００が、スカラー値ｄの入力を受け付ける（Ｓ３０１）。
次に、δ剰余計算部３０４が、入力されたスカラー値ｄに対して、式（２５）を満たす整数ｄａを計算する（Ｓ３０２）。ここで、式（２５）におけるδは式（２１）により算出される値である。
【００８４】
ｄａ＝ｄ  ｍｏｄ  δ  ・・・  式（２５）
【００８５】
そして、τ−ＮＡＦ計算部３０１とτ−ＮＡＦ長計算部３０２は、整数ｄａを、式（２６）〜（２８）を満たすτ−ＮＡＦ表現の数値列に変換する（Ｓ３０３）。
【００８６】
ｄａ＝ｅ０＋ｅ１τ＋…＋ｅｎ−１τｎ−１  ・・・  式（２６）
｜ｅｉ｜≦１  ・・・  式（２７）
ｅｉ＋１ｅｉ＝０  ・・・  式（２８）
【００８７】
ここで、式（２６）のｅｎ−１はｅｎ−１≠０を満たす。
スカラー値ｄから式（２５）を満たす整数ｄａを計算する方法、および、整数ｄａを式（２６）〜（２８）を満たすように展開する方法は、非特許文献１に記載されている。
なお、式（２６）のｎと前記した拡大次数ｍの間に、以下の式（２９）を満たす関係があることは、例えば、「D. Gordon, A survey of fast exponentiation methods, Journal of Algorithms, Vol.27, No.1, pp.129-146, 1998.」に記載されている。
【００８８】
ｎ≦ｍ＋２  ・・・  式（２９）
【００８９】
次に、エンコード部３００は、ステップＳ３０４〜Ｓ３０７の処理でτ−ＮＡＦ表現の数値列（ｅｎ−１，ｅｎ−２，…，ｅ０）τから、τ−ＭＬＦ表現の数値列（ｇｍ−１，ｇｍ−２，・・・，ｇ０）τを生成する。
まず、条件判定部３０５は、ｎ≧６であるか否かを判定する（Ｓ３０４）。
ステップＳ３０４の結果、ｎ≧６が成立する場合（Ｓ３０４→Ｙｅｓ）、τ−ＭＬＦ計算部３０６は、図３の変換テーブル３６ａに従ってτ−ＮＡＦ表現の数値列の上位６桁を変換する（Ｓ３０５）。
具体的には、τ−ＭＬＦ計算部３０６はτ−ＮＡＦ表現の数値列の上位６桁（ｅｎ−１，ｅｎ−２，ｅｎ−３，ｅｎ−４，ｅｎ−５，ｅｎ−６）τを、図３の変換テーブル３６ａに従って（ｇｍ−１，・・・，ｇｎ−６）τに変換する。そして、τ−ＭＬＦ計算部３０６は、τ−ＮＡＦ表現の数値列の下位ｎ−６桁（ｅｎ−７，ｅｎ−８，…，ｅ０）τを無変換の状態で（ｇｍ−７，ｇｍ−８，…，ｇ０）τに代入する。
ステップＳ３０５の結果、図３の行４０２のように桁の減少が可能な数値列は、桁数を減少することができる。
【００９０】
ステップＳ３０４の結果、ｎ≧６が成立しない場合（Ｓ３０４→Ｎｏ）、τ−ＭＬＦ計算部３０６は、（ｅｎ−１，ｅｎ−２，…，ｅ０）τを、無変換の状態で（ｇｍ−１，ｇｍ−２，…，ｇ０）τに代入する無変換処理を行う（Ｓ３０６）。つまり、τ−ＭＬＦ計算部３０６は、τ−ＮＡＦ表現の数値列を、そのままτ−ＭＬＦ表現の数値列とする。
ステップＳ３０５またはステップＳ３０６の後、エンコード部３００は、τ−ＭＬＦ表現の数値列（ｇｍ−１，ｇｍ−２，…，ｇ０）τを出力する（Ｓ３０７）。
【００９１】
（実計算処理）
図７は、第１実施形態に係る実計算処理（図４のステップＳ１０８）の流れを示すフローチャートである。なお、図５のステップＳ２０７の実計算処理も同様の処理手順である。
ここでは、エンコード部３００により得られたτ−ＭＬＦ表現の数値列としてエンコードされたスカラー値ｄ＝（ｇｍ−１，ｇｍ−２，…，ｇ０）τと、Ｋｏｂｌｉｔｚ曲線上の定点Ｐとから、スカラー倍点ｄＰを計算する。なお、図７に示す処理は公知の処理である。
まず、実計算部３５０は、τ−ＭＬＦ表現の数値列としてエンコードされたスカラー値ｄ＝（ｇｍ−１，ｇｍ−２，…，ｇ０）τと、記憶部３からＫｏｂｌｉｔｚ曲線上の定点Ｐの入力を受け付ける（Ｓ４０１）。
次に、加算部３５１は、Ｑに無限遠点Ｏを代入する（Ｓ４０２）。
そして、繰り返し判定部３５３は、ｉにｍ−１を代入し（Ｓ４０３）、ｉ≧０であるか否かを判定する（Ｓ４０４）。
ステップＳ４０４の結果、ｉ≧０でない場合（Ｓ４０４→Ｎｏ）、実計算部３５０は、Ｑを出力する（Ｓ４０５）。
【００９２】
ステップＳ４０４の結果、ｉ≧０である場合（Ｓ４０４→Ｙｅｓ）、τ倍算部３５２は、τ（Ｑ）を計算し、計算の結果をＱに代入する（Ｓ４０６）。ここで、Ｋｏｂｌｉｔｚ曲線上の定点ＱをＱ＝（ｘ，ｙ）と表すと、τ（Ｑ）は式（８）の定義を満たす。
そして、数値判定部３５４が、ｇｉ≠０であるか否かを判定する（Ｓ４０７）。
ステップＳ４０７の結果、ｇｉ≠０である場合（Ｓ４０７→Ｙｅｓ）、加算部３５１は、Ｑ＋ｓｉｇｎ（ｇｉ）Ｐを計算し、計算結果をＱに代入する（Ｓ４０８）。ここで、「ｓｉｇｎ」は、非零整数ｘに対し、ｘ＞０のときｓｉｇｎ（ｘ）＝１、ｘ＜０のときｓｉｇｎ（ｘ）＝−１なる非零整数全体の集合から集合｛±１｝への写像である。
【００９３】
ステップＳ４０７の結果、ｉ≧０ではない場合（Ｓ４０７→Ｎｏ）、またはステップＳ４０８の結果、繰り返し判定部３５３は、ｉにｉ−１を代入し（Ｓ４０９）、ステップＳ４０４へ処理を戻す
【００９４】
以上説明したように、エンコード部３００から出力されるｇｉは、式（１８）を満たす。この理由は次の通りである。
まず、図６のステップＳ３０３で計算したτ−ＮＡＦ表現の数値列（ｅｎ−１，ｅｎ−２，…，ｅ０）τとｄａが等しい理由は非特許文献１に記載されている。τ−ＮＡＦ表現の数値列とτ−ＭＬＦ表現の数値列（ｇｍ−１，ｇｍ−２，…，ｇ０）τが等しい理由は、ステップＳ２０５とステップＳ２０６のいずれの場合も（ｅｎ−７，ｅｎ−８，…，ｅ０）τ＝（ｇｍ−１，ｇｍ−２，…，ｇ０）τが成り立つこと、および図３の変換テーブル３６ａの１列目の６桁τ−ＮＡＦ表現と、対となっている２列目のτ−ＭＬＦ表現が数値として等しいことによる。さらに、ｇｉが式（１９）を満たす理由は式（１８）を満たす理由と同様である。ｍが式（２０）を満たす理由は、式（２９）と図３の変換テーブル３６ａの３列目による。
【００９５】
実計算部３５０が出力する点Ｑはスカラー倍点ｄＰに等しい。この理由は次の通りである。実計算部３５０が出力する点Ｑは、以下の式（３０）を満たし、ｄａは式（２２）を満たす。
【００９６】
Ｑ＝ｄａＰ  ・・・  式（３０）
【００９７】
また、Ｋｏｂｌｉｔｚ曲線上では、δＰは無限遠点となることが知られている。従って実計算部３５０が出力する点Ｑは点ｄＰに等しい。
エンコード部３００が出力するτ−ＭＬＦ表現の数値列は、その各桁ｇｉが式（１８）を満たすτ進展開のうち、非零濃度が最小である。この理由も式（１８）を満たす理由と同様である。
【００９８】
以上よりτ−ＭＬＦ表現の数値列は、その各桁が式（１８）を満たすτ進展開のうち、非零濃度が最小であるといえる。
また、エンコード部３００が出力するτ−ＭＬＦ表現は、その各桁ｇｉが式（１８）を満たす非零濃度が最小なτ進展開のうち、長さが最小である。この理由は、τ−ＭＬＦ表現より短い長さを持つような式（１８）を満たす非零濃度が最小なτ進展開が存在すると仮定することにより矛盾を導いて証明できる。
【００９９】
第１実施形態では、スカラー値をτ−ＮＡＦ表現の数値列（第１の符号列）に変換し、さらにτ−ＮＡＦ表現の数値列をτ−ＭＬＦ表現の数値列（第２の符号列）に変換した後、このτ−ＭＬＦ表現の数値列を用いてスカラー倍点を計算する方法を説明したが、τ−ＭＬＦ表現の数値列の計算に合わせてスカラー倍点を計算するｏｎ  ｔｈｅ  ｆｌｙ法を用いてスカラー倍点を計算してもよい。
また、本実施形態では、暗号化コンピュータ１Ａおよび復号化コンピュータ１Ｂにおいて、ＰＣ（Personal Computer）を想定しているが、これに限らず、少なくともどちらか一方が、スマートカードのような演算装置を有する可搬型小型記憶媒体でもよい。
【０１００】
（第１実施形態の効果）
以上のように、第１実施形態のスカラー倍計算方法によれば、τ−ＮＡＦ表現の数値列から、桁数の減少が可能な数値列に関して桁数を減少させτ−ＭＬＦ表現の数値列をスカラー値の数値列として出力することができる。これにより、リソースが限られた環境で、安全性を低下させることなく、最小な加算回数と最小なフロベニウス写像の回数によって、高速計算可能が可能となる。。
すなわち、本実施形態によれば、Ｋｏｂｌｉｔｚ曲線が持つ高い安全性とリソース利用効率の良さを保ちつつ、高速性に優れたメッセージ処理が可能になる。
【０１０１】
《第２実施形態》
次に、図８および図９を参照して、本発明に係る第２実施形態について説明する。
第２実施形態において、第１実施形態と異なるのは変換テーブル３６の構成およびエンコード処理であるため、ここではこれらの説明を記載し、それ以外の構成および処理は図示および説明を省略することとする。
なお、第２実施形態におけるスカラー倍計算部３３は、図２のτ−ＮＡＦ計算部３０１、τ−ＮＡＦ長計算部３０２は備えていなくてもよい。
【０１０２】
第２実施形態では、スカラー倍計算部３３がスカラー値ｄとＫｏｂｌｉｔｚ曲線上の定点Ｐから、Ｋｏｂｌｉｔｚ曲線におけるスカラー倍点ｄＰを計算する第２の計算方法を説明する。
【０１０３】
詳細な説明を行う前に、ここで第２実施形態の概要を説明する。
第１実施形態では、スカラー値ｄから式（２６）、式（２７）、式（２８）を満たすτ−ＮＡＦ表現の数値列にエンコードした後、変換テーブル３６ａ（図３）に従って、さらに、τ−ＮＡＦ表現の数値列とは異なるτ−ＭＬＦ表現の数値列にエンコードし、このτ−ＭＬＦ表現の数値列を用いてスカラー倍点を計算した。これに対し、第２実施形態は、スカラー値ｄから式（２６）、式（２７）、式（２８）を満たすτ−ＮＡＦ表現の数値列を計算することなく、τ−ＭＬＦ表現の数値列を直接計算し、このτ−ＭＬＦ表現の数値列を用いてスカラー倍点を計算することを特徴とする。
そして、実計算部３５０が、このτ−ＭＬＦ表現の数値列と、Ｋｏｂｌｉｔｚ曲線上の定点とを用いてスカラー倍計算を実行することにより高速化を実現する。以下、この計算方法を具体的に説明する。
【０１０４】
（変換テーブル）
図８は、第２実施形態に係る変換テーブルの構成例を示す図である。
変換テーブル３６ｂ（３６）の１列目には、後記する図９のステップＳ４０２で算出され、ステップＳ５０５，Ｓ５０７，Ｓ５０９で更新されるτ進複素数表現ｒ０＋ｒ１τの値が記載されている。ここで、ｒ０＋ｒ１τ＝±３、±４、±５は、ｒ０＝±３、±４、±５、かつｒ１＝０を意味する。
２列目には、１列目の同一行に記載されているｒ０＋ｒ１τに対応するｇｈに代入する値（第３の符号列）が記載されている。
そして、３列目には、１列目の同一行に記載されているｒ０＋ｒ１τに対応するｈの計算方法が記載されている。ｈの意味については、図９において後記する。
そして、４列目と５列目には、１列目の同一行に記載されているｒ０＋ｒ１τに対応するｒ０とｒ１の更新値が記載されている。ここでは、すべて「０」に更新される。
【０１０５】
なお、ｈは２列目のｇｈの個数を用いて計算することが可能なので、３列目を変換テーブル３６ｂに記載しなくてもよい。また、変換テーブル３６ｂに記載されているすべてのｒ０＋ｒ１τを記載する必要はなく、少なくとも一つ以上を変換テーブル３６ｂに記載し、後記するステップＳ４０５では、変換テーブル３６ｂに記載されているｒ０＋ｒ１τのみを、変換するようにしてもよい。
【０１０６】
（エンコード処理）
次に、図２および図８を参照しつつ、図９に沿って第２実施形態に係るエンコード処理の説明を行う。
図９は、第２実施形態に係るエンコード処理（図４のステップＳ１０７）の流れを示すフローチャートである。なお、図５のステップＳ２０６のエンコード処理も同様の処理手順である。
図９の処理では、スカラー値をτ−ＭＬＦ表現の数値列にエンコードする処理を行う。
まず、エンコード部３００は、スカラー値ｄの入力を受け付ける（Ｓ５０１）。
次に、δ剰余計算部３０４は、入力されたスカラー値ｄに対して、式（２５）を満たす整数ｄａ＝ｒ０＋ｒ１τ＝ｄ  ｍｏｄ  δ（τ進複素数表現）を計算し、ｈに０を代入する（Ｓ５０２）。なお、ｈは現在計算している桁を示す変数である。
次に、条件判定部３０５はｒ０≠０またはｒ１≠０であるか否かを判定する（Ｓ５０３）。
【０１０７】
ステップＳ５０３の結果、ｒ０≠０またはｒ１≠０である場合（Ｓ５０３→Ｙｅｓ）、条件判定部３０５は条件Ｚ１が満たされているか否かを判定する（Ｓ５０４）。
ここで、条件Ｚ１とは、ｒ０＋ｒ１τ（τ進複素数表現）が図８の変換テーブル３６ｂの１列目に登録されていることである。
すなわち、ステップＳ５０４において、条件判定部３０５は、ステップＳ５０２で計算されたτ進複素数表現が下記のいずれかであるか否かを判定する。
【０１０８】
【数２】
2011081147.tif 000004
【０１０９】
ステップＳ５０４の結果、条件Ｚ１を満たす場合（Ｓ５０４→Ｙｅｓ）、τ−ＭＬＦ計算部３０６は変換テーブル３６ｂから、該当するｇｈ（第３の符号列）ｈ、、ｒ０、ｒ１を取得する（Ｓ５０５）。このとき、ｈ、ｒ０、ｒ１の値は更新される。そして、エンコード部３００はステップＳ５０３へ処理を戻す。
【０１１０】
ステップＳ５０４の結果、条件Ｚ１を満たさない場合（Ｓ５０４→Ｎｏ）、条件判定部３０５はｒ０が奇数であるか否かを判定する（Ｓ５０６）。
ステップＳ５０６の結果、ｒ０が奇数である場合（Ｓ５０６→Ｙｅｓ）τ−ＭＬＦ計算部３０６はｇｈ（第４の符号列）に２−（ｒ０−２ｒ１  ｍｏｄ  ４）を代入し、ｒ０にｒ０−ｇｈを代入して（Ｓ５０７）、ステップＳ５０９へ処理を進める。
ステップＳ５０６の結果、ｒ０が奇数ではない場合（Ｓ５０６→Ｎ０）、τ−ＭＬＦ計算部３０６はｇｈ（第４の符号列）に０を代入して（Ｓ５０８）、ステップＳ５０９へ処理を進める。
ステップＳ５０７，Ｓ５０８の後、τ−ＭＬＦ計算部３０６はｔにｒ０を、ｒ０にｒ１＋μｒ０／２を、ｒ０にｒ１−ｔ／２を、ｈにｈ＋１をそれぞれ代入し（Ｓ５０９）、エンコード部３００はステップＳ５０３へ処理を戻す。
【０１１１】
ステップＳ５０３の結果、ｒ０およびｒ１が０であった場合（Ｓ５０３→Ｎｏ）、エンコード部３００は、（ｇｈ−１，ｇｈ−２，…，ｇ０）τをτ−ＭＬＦ表現の数値列（第５の符号列）として出力する（Ｓ５１０）。
なお、図９の処理において、第１の方法であるステップＳ５０７およびステップＳＳ５０９は、一般的に周知であるτ−ＮＡＦの演算処理である。
そして、実計算部３５０の行う処理は、図７と同様であるため、前記したように説明を省略する。
【０１１２】
以上説明したように、エンコード部３００から出力されるτ−ＭＬＦ表現の数値列におけるｇｉは、式（１８）を満たす。この理由は第１実施形態と同様である。
また、実計算部３５０が出力する点Ｑはスカラー倍点ｄＰに等しい。この理由は第１実施形態と同様である。
そして、Ｋｏｂｌｉｔｚ曲線上では、δＰは無限遠点となることが知られている。従って実計算部３５０が出力する点Ｑは点ｄＰに等しい。
さらに、エンコード部３００が出力するτ−ＭＬＦ表現の数値列（第２の数値列）は、その各桁の数値ｇｉが式（１８）を満たすτ進展開のうち、非零濃度が最小である。この理由は第１実施形態と同様である。
また、エンコード部３００が出力するτ−ＭＬＦ表現の数値列は、その各桁ｇｉが式（１８）を満たす非零濃度が最小なτ進展開のうち、長さが最小である。この理由も第１実施形態と同様である。
【０１１３】
なお、第２実施形態でも、スカラー値ｄをτ−ＭＬＦ表現の数値列に変換し、このτ−ＭＬＦ表現を用いてスカラー倍点を計算するが、τ−ＭＬＦ表現の計算に合わせてスカラー倍点を計算するｏｎ  ｔｈｅ  ｆｌｙ法を用いてスカラー倍点を計算してもよい。
【０１１４】
（第２実施形態の効果）
以上のように、第２実施形態のスカラー倍計算方法によれば、第１実施形態と同様にリソースが限られた環境で、安全性を低下させることなく、最小な加算回数と最小なフロベニウス写像の回数によって、高速計算可能が可能となる。
すなわち、第２実施形態によれば、第１実施形態と同様に楕円曲線暗号が持つ高い安全性とリソース利用効率の良さを保ちつつ、高速性に優れたメッセージ処理が可能になる。
さらに、第２実施形態によれば、第１実施形態のように１度τ−ＮＡＦ表現による数値列を算出することなく、直接τ−ＭＬＦを算出するため、第１実施形態より処理の高速化・低負荷化が可能である。
【０１１５】
《第３実施形態》
次に、図１０〜図１３を参照して、本発明に係る第３の実施形態について説明する。
第３実施形態において、第１実施形態と異なるのはスカラー倍計算部３３の構成、変換テーブル３６の構成およびエンコード処理であるため、ここではこれらの説明を記載し、それ以外の構成および処理は図示および説明を省略することとする。
【０１１６】
（スカラー倍計算部構成）
図１０は、第３実施形態に係るスカラー倍計算部の構成例を示す図である。
図１０のスカラー倍計算部３３ａのエンコード部３００ａにおいて、図２と異なる点は、τ−ＮＡＦ計算部３０１、τ−ＮＡＦ長計算部３０２が、桁対計算部３１１、長さ判定部３１２にそれぞれ置き換わっている点である。これらの機能については、処理の説明において後記する。
【０１１７】
第３実施形態では、スカラー倍計算部３３Ａが２進表現（ｅｍ＋２，ｅｍ＋１，…，ｅ０）とＫｏｂｌｉｔｚ曲線上の定点Ｐとから、Ｋｏｂｌｉｔｚ曲線におけるスカラー倍点ｄｂＰを計算する第３の計算方法を説明する。
【０１１８】
詳細な説明を行う前に、ここで第３実施形態の概要を説明する。
第１実施形態および第２の実施形態では、スカラー値ｄからτ−ＭＬＦ表現の数値列にエンコードし、このτ−ＭＬＦ表現の数値列を用いてスカラー倍点を計算した。このとき、スカラー値ｄからｄａ＝ｄ  ｍｏｄ  δを計算する手続きを必ず実施する（ｄ  ｍｏｄ  δをδ剰余計算と呼ぶ）。このδ剰余計算は比較的重い処理である。
これに対し、入力された２進表現（ｅｍ＋２，ｅｍ＋１，…，ｅ０）（コンピュータにおいて、入力される数値はｄのような数値ではなく、これを２進表現にした数値列が入力される）から、δ剰余計算を計算することなくτ−ＮＡＦ表現ｄ＝（ｙｍ＋１，ｙｍ，…，ｙ０）τを計算し、このτ−ＮＡＦ表現ｄ＝（ｙｍ＋１，ｙｍ，…，ｙ０）τを用いてスカラー倍点ｄＰを計算する手法が非特許文献２に記載されている。
【０１１９】
非特許文献２では、比較的重い処理であるδ剰余計算を実施することなく、入力された２進表現（ｅｍ＋２，ｅｍ＋１，…，ｅ０）からτ−ＮＡＦ表現の数値列を計算している。
第３の実施形態でも、比較的重い処理であるδ剰余計算を実施することなく、入力された２進表現（ｅｍ＋２，ｅｍ＋１，…，ｅ０）からτ−ＭＬＦ表現の数値列ｄｂ＝（ｇｍ＋１，ｇｍ，…，ｇ０）τを計算し、このτ−ＭＬＦ表現の数値列ｄｂ＝（ｇｍ＋１，ｇｍ，…，ｇ０）τを用いてスカラー倍点ｄｂＰを計算する。ここで、同一の２進表現ｅｍ＋２ｅｍ＋１…ｅ０に対し、非特許文献２に記載の方法で計算したスカラー値ｄ＝（ｙｍ＋１，ｙｍ，…，ｙ０）τと、第３実施形態の方法で計算したスカラー値ｄｂ＝（ｇｍ＋１，ｇｍ，…，ｇ０）τにはｄＰ＝ｄｂＰなる関係がある。
【０１２０】
第３実施形態では、このτ−ＭＬＦ表現とこのＫｏｂｌｉｔｚ曲線上の定点とを用いてスカラー倍計算を実行することにより、第１実施形態および第２実施形態より高速な処理を実現することを目的とする。
【０１２１】
（変換テーブル）
図１１は、第３実施形態に係る変換テーブルの構成例である。
変換テーブル３６ｃの１列目には、入力された２値のビット列（ｅｊ，ｅｊ−１，ｅｊ−２，ｅｊ−３，ｅｊ−４，ｅｊ−５，ｅｊ−６）（第６の符号列）の値が記載されている。２列目には、１列目の同一行に記載されている（ｅｊ，ｅｊ−１，ｅｊ−２，ｅｊ−３，ｅｊ−４，ｅｊ−５，ｅｊ−６）に対応する数値列（ｇｊ，ｇｊ−１，ｇｊ−２，ｇｊ−３，ｇｊ−４，ｇｊ−５）（第７の符号列）が記載されている。
先頭の「０」は、その桁における数値がないことを示す。例えば、符号５０１の２列目における（０，０，０、−１，−μ，１）は、実質的には３桁である。
ここで、１列目と２列目を比較すると、一部の行で２列目の数値列の桁数が減少していることが分かる（例えば、符号５０１）。これにより、数値列の桁数の減少が可能となる。
【０１２２】
なお、変換テーブル３６ｃにおいてすべての（ｅｊ，ｅｊ−１，ｅｊ−２，ｅｊ−３，ｅｊ−４，ｅｊ−５，ｅｊ−６）を記載する必要はなく、少なくとも一つ以上を変換テーブル３６ｃに記載し、後記する図１３のステップＳ６１９では、変換テーブル３６ｃに記載されている（ｅｊ，ｅｊ−１，ｅｊ−２，ｅｊ−３，ｅｊ−４，ｅｊ−５，ｅｊ−６）のみを、変換するようにしてもよい。
【０１２３】
（エンコード処理）
次に、図１０および図１１を参照しつつ、図１２および図１３に沿って第３実施形態に係るエンコード処理の説明を行う。
図１２および図１３は、第３実施形態に係るエンコード処理（図４のステップＳ１０７）の流れを示すフローチャートである。なお、図５のステップＳ２０６のエンコード処理も同様の処理手順である。
図１２および図１３では、スカラー値を数値列（τ−ＭＬＦ）にエンコードする処理を行う。
まず、エンコード部３００ａは、ｍ＋３ビットのビット列である２進表現（ｅｍ＋２，ｅｍ＋１，…，ｅ０）の入力を受ける（Ｓ６０１）。ここで入力される（ｅｍ＋２，ｅｍ＋１，…，ｅ０）は図６のステップＳ３０１や、図９のステップＳ５０１で入力されるｄを２進表現したビット列である。
桁対計算部３１１は、ｅｍ＋３に０を代入し、長さ判定部３１２は、受け取った２進表現（ｅｍ＋２，ｅｍ＋１，…，ｅ０）に対して、ｅｋ≠０なる最大のｋを計算する（Ｓ６０２）。ここで、ｋはビット列の桁数となる。これは、例えば（０，０，１，０，１）のようなビット列が入力されるのを想定しているためであり、このビット列例のｋは３となる。
【０１２４】
次に、条件判定部３０５は、ｉに０を代入する（Ｓ６０３）。ｉは、現在処理していているビット列の桁数となる。
そして、条件判定部３０５はｋが６以上であるか否かを判定する（Ｓ６０４）。
ステップＳ６０４の結果、ｋが６以上でない場合（Ｓ６０４→Ｎｏ）、エンコード部３００ａは図１３のステップＳ６１２へ処理を進める。ステップＳ６１２以降の処理は後記して説明する。
ステップＳ６０４の結果、ｋが６以上である場合（Ｓ６０４→Ｙｅｓ）、条件判定部３０５は、ｉがｋ−６以下であるか否かを判定する（Ｓ６０５）。
ステップＳ６０５の結果、ｉがｋ−６以下でない場合（Ｓ６０５→Ｎｏ）、エンコード部３００ａは図１３はステップＳ６１２へ処理を進める。ステップＳ６１２以降の処理は後記して説明する。
【０１２５】
ステップＳ６０５の結果、ｉがｋ−６以下である場合（Ｓ６０５→Ｙｅｓ）、条件判定部３０５は、ｅｉが１であるか否かを判定する（Ｓ６０６）。
ステップＳ６０６の結果、ｅｉが１でない場合（Ｓ６０６→Ｎｏ）、τ−ＭＬＦ計算部３０６はｇｉ（第８の符号列）に０を代入し、ｉにｉ＋１を代入した（Ｓ６０７）後、エンコード部３００ａはステップＳ６０５へ処理を戻す。
ステップＳ６０６の結果、ｅｉが１である場合（Ｓ６０６→Ｙｅｓ）、条件判定部３０５は、ｅｉ＋１が１であるか否かを判定する（Ｓ６０８）。
ステップＳ６０８の結果、ｅｉ＋１が１である場合（Ｓ６０８→Ｙｅｓ）τ−ＭＬＦ計算部３０６は、ｇｉ＋１（第８の符号列）に０を代入し、ｇｉ（第８の符号列）に−１を代入した（Ｓ６０９）後、エンコード部３００ａはステップＳ６１１へ処理を進める。
ステップＳ６０８の結果、ｅｉ＋１が１でない場合（Ｓ６０８→Ｎｏ）、τ−ＭＬＦ計算部３０６は、ｇｉ＋１（第８の符号列）に０を代入し、ｇｉ（第８の符号列）に１を代入した（Ｓ６１０）後、エンコード部３００ａはステップＳ６１１へ処理を進める。
ステップＳ６０９，Ｓ６１０の処理後、条件判定部３０５は、ｉにｉ＋２を代入し（Ｓ６１１）、エンコード部３００ａはステップＳ６０５へ処理を戻す。
なお、本処理のステップＳ６０６〜Ｓ６１１が第３の方法である。また、ステップＳ６０６〜Ｓ６１１の処理は非特許文献２に記載の処理方法である。
【０１２６】
ステップＳ６０４の結果、ｋが６以上ではない場合（Ｓ６０４→Ｎｏ）、またはステップＳ６０５の結果、ｉがｋ−６以下ではない場合（Ｓ６０５→Ｎｏ）、条件判定部３０５は、ｘに（ａ−１）  ｍｏｄ  ２を代入する（図１３のＳ６１２）。ここで、ａは式（１２）の定数であり、ａ＝０またはａ＝１である。また、ａ＝０のときｘ＝（ａ−１）  ｍｏｄ  ２＝−１  ｍｏｄ  ２＝１、ａ＝１のときｘ＝（ａ−１）  ｍｏｄ  ２＝０  ｍｏｄ  ２  ＝０となるので、ｘ＝０またはｘ＝１である。
次に、条件判定部３０５は、ｉがｋ−６であるか否かを判定する（Ｓ６１３）。
ステップＳ６１３の結果、ｉがｋ−６である場合（Ｓ６１３→Ｙｅｓ）、条件判定部３０５は、ｊにｋを代入し（Ｓ６１４）、エンコード部３００ａはステップＳ６１８へ処理を進める。
ステップＳ６１３の結果、ｉがｋ−６ではない場合（Ｓ６１３→Ｎｏ）、条件判定部３０５は、ｉがｋ−５であるか否かを判定する（Ｓ６１５）。
ステップＳ６１５の結果、ｉがｋ−５である場合（Ｓ６１５→Ｙｅｓ）、条件判定部３０５は、ｅｋ＋１に０を代入し、ｊにｋ＋１を代入し（Ｓ６１６）、エンコード部３００ａはステップＳ６１８へ処理を進める。
ステップＳ６１５の結果、ｉがｋ−５でない場合（Ｓ６１５→Ｎｏ）、条件判定部３０５は、ｊに６を代入し（Ｓ６１７）、エンコード部３００ａは図１３のステップＳ６１８へ処理を進める。
【０１２７】
ステップＳ６１４、Ｓ６１６，Ｓ６１７の処理後、条件判定部３０５は、条件Ｚ２が満たされるか否かを判定する（Ｓ６１８）。ここで、条件Ｚ２は、（ｅｊ，ｅｊ−１，…，ｅｊ−５）において、第２の方法である所定の方法で符号が変換された数値列（第９の符号列）が、図１１の変換テーブル３６ｃの１列目に登録されている数値列のいずれか１つと一致することである。ここで、所定の方法（第２の方法）とは、変換テーブル３６ｃの１列目におけるａ，ｘの位置に従って、（ｅｊ，ｅｊ−１，…，ｅｊ−５）の符号を置き換えるものである。
ステップＳ６１８の結果、条件Ｚ２が満たされない場合（Ｓ６１８→Ｎｏ）、すなわち、第２の方法で変換された（ｅｊ，ｅｊ−１，…，ｅｊ−５）が、図１１の変換テーブル３６ｃの１列目に登録されている（ｅｊ，ｅｊ−１，…，ｅｊ−５）のいずれとも一致しない場合、エンコード部３００ａはステップＳ６２３へ処理を進める。ステップＳ６２３以降の処理は後記して説明する。
【０１２８】
ステップＳ６１８の結果、条件Ｚ２を満たす場合（Ｓ６１８→Ｙｅｓ）、すなわち、第２の方法で変換された（ｅｊ，ｅｊ−１，…，ｅｊ−５）が、図１１の変換テーブル３６ｃの１列目に登録されている（ｅｊ，ｅｊ−１，…，ｅｊ−５）のいずれか一つと一致する場合、τ−ＭＬＦ計算部３０６は図１１の変換テーブル３６ｃから、（ｅｊ，ｅｊ−１，…，ｅｊ−５）に対応する（ｇｊ，・・・，ｇｊ−５）τを取得する（Ｓ６１９）。
そして、条件判定部３０５はｉにｊ＋１を代入し（Ｓ６２０）、ｉがｍ＋３以下ならば、τ−ＭＬＦ計算部３０６は、ｇｍ＋３，ｇｍ＋２，…，ｇｉにそれぞれ０を代入する（Ｓ６２１）。
そして、エンコード部３００ａは、ｄｂ＝（ｇｍ＋１，ｇｍ，…，ｇ０）τ（第１０の符号列）をτ−ＭＬＦ表現の数値列として出力する（Ｓ６２２）。
【０１２９】
一方、ステップＳ６１８の結果、条件Ｚ２が満たされない場合（Ｓ６１８→Ｎｏ）、条件判定部３０５は、ｉがｋ以下であるか否かを判定する（Ｓ６２３）。
ステップＳ６２３の結果、ｉがｋ以下ではない場合（Ｓ６２３→Ｎｏ）、エンコード部３００ａはステップＳ６２１へ処理を進める。ステップＳ６２１以降の処理は前記したため、ここでの説明は省略する。
ステップＳ６２３の結果、ｉがｋ以下である場合（Ｓ６２３→Ｙｅｓ）、条件判定部３０５は、ｅｉが１であるか否かを判定する（Ｓ６２４）。
ステップＳ６２４の結果、ｅｉが１でない場合（Ｓ６２４→Ｎｏ）、τ−ＭＬＦ計算部３０６は、ｇｉ（第８の符号列）に０を代入し、条件判定部３０５はｉにｉ＋１を代入し（Ｓ６２５）、エンコード部３００ａはステップＳ６２３へ処理を戻す。
【０１３０】
ステップＳ６２４の結果、ｅｉが１である場合（Ｓ６２４→Ｙｅｓ）、条件判定部３０５は、ｅｉ＋１が１であるか否かを判定する（Ｓ６２６）。
ステップＳ６２６の結果、ｅｉ＋１が１である場合（Ｓ６２６→Ｙｅｓ）、τ−ＭＬＦ計算部３０６は、ｇｉ＋１（第８の符号列）に０を代入し、ｇｉ（第８の符号列）に−１を代入し（Ｓ６２７）、エンコード部３００ａはステップＳ６２９へ処理を進める。
ステップＳ６２６の結果、ｅｉ＋１が１でない場合（Ｓ６２６→Ｎｏ）、τ−ＭＬＦ計算部３０６は、ｇｉ＋１（第８の符号列）に０を代入し、ｇｉ（第８の符号列）に１を代入し（Ｓ６２８）、エンコード部３００ａはステップＳ６２９へ処理を進める。
ステップＳ６２７、Ｓ６２８の処理後、条件判定部３０５は、ｉにｉ＋２を代入し（Ｓ６２９）、エンコード部３００ａはステップＳ６２３へ処理を戻す。
なお、本処理におけるステップＳ６２３〜Ｓ６２９は第４の方法である。また、ステップＳ６２３〜Ｓ６２９の処理は非特許文献２に記載の処理方法である。
なお、ステップＳ６０１〜Ｓ６１１およびステップＳ６２１〜Ｓ６２９の処理は、特許文献１に記載の処理と同様の処理である。
以降、実計算部３５０が図７と同様の処理を行い、スカラー倍点を計算する。
【０１３１】
以上説明したように、ステップＳ６０１で入力される２進表現（ｅｍ＋２ｅｍ＋１…ｅ０）に対し、エンコード部３００ａから出力される（ｇｍ＋１，ｇｍ，…，ｇ０）τと非特許文献２に記載の方法で計算したスカラー値（ｙｍ＋１，ｙｍ，…，ｙ０）τは、（ｇｍ＋１，ｇｍ，…，ｇ０）τ＝（ｙｍ＋１，ｙｍ，…，ｙ０）τを満たす。この理由は明らかである。
そして、実計算部３５０が出力する点Ｑはスカラー倍点ｄｂＰに等しい。この理由は第１実施形態、および第２の実施形態と同様である。
【０１３２】
（第３実施形態の効果）
以上のように、第３実施形態のスカラー倍計算方法によれば、リソースが限られた環境で、安全性を低下させることなく、最小な加算回数と最小なフロベニウス写像の回数によって、高速計算可能が可能となる。
すなわち、第３実施形態によれば、Ｋｏｂｌｉｔｚ曲線が持つ高い安全性とリソース利用効率の良さを保ちつつ、高速性に優れたメッセージ処理が可能になる。
さらに、第３実施形態によれば、比較的重い処理であるδ剰余計算を実施することなく、入力された２進表現（ｅｍ＋２，ｅｍ＋１，…，ｅ０）からτ−ＭＬＦ表現の数値列を計算しているため、第１実施形態および第２実施形態より、処理の高速化・低負荷化が可能である。  なお、δ剰余計算を実施することなく、入力された２進表現（ｅｍ＋２，ｅｍ＋１，…，ｅ０）からτ−ＮＡＦ表現の数値列を計算している非特許文献２の技術とは異なり、τ−ＭＬＦ表現の数値列を計算するため、非特許文献２の技術よりも、リソースが限られた環境で、安全性を低下させることなく、最小な加算回数と最小なフロベニウス写像の回数によって、高速計算可能が可能な数値列を出力することができる。。
【０１３３】
《第４実施形態：署名検証システム》
次に、図１４〜図１６を参照して第１実施形態〜第３実施形態を適用した署名検証システムＢを第４実施形態として説明する。
【０１３４】
（署名検証システムの構成図）
図１４は、第４実施形態に係る署名検証システムのシステム構成図である。
署名検証システムＢは、スマートカード（署名生成装置、可搬型小型記憶媒体）１Ｃと署名検証処理を行うコンピュータ（署名検証装置）１Ｄとを有する。
スマートカード１Ｃは、第１実施形態〜第３の実施形態の図１の暗号化コンピュータ１０１と類似の構成を備える。すなわち、スマートカード１Ｃにおける符号２Ｃ，４Ｃ，２１Ｃ，２２Ｃ，３１Ｃ，３３Ｃ，３４Ｃ，３６Ｃ〜３８Ｃは、それぞれ図１における符号２Ａ，４Ａ，２１Ａ，２２Ａ，３１Ａ，３３Ａ，３４Ａ，３６Ａ〜３８Ａと同様の構成要素である。
ここで、スマートカード１Ｃと、図１の暗号化コンピュータ１Ａとの差異は以下の通りである。まず、図１におけるデータ処理部３２Ａが署名生成処理部３２Ｃに置き換わっている。また、図１における外部記憶装置３５Ａ、ディスプレイ５Ａ、キーボード６Ｂを備えていない。
そして、変換テーブル３６Ｃ（３６）、秘密情報３７Ｃおよび定数３８Ｃが、ＲＯＭ３４Ｃに格納されている。
【０１３５】
一方、コンピュータ１Ｄは、復号化コンピュータ１Ｂと同様の構成を備える。すなわち、コンピュータ１Ｄにおける２Ｄ〜６Ｄ，２１Ｄ，２２Ｄ，３１Ｄ，３３Ｄ〜３８Ｄは、図１の復号化コンピュータ１Ｂにおける２Ｂ〜６Ｂ，２１Ｂ，２２Ｂ，３１Ｂ，３３Ｂ〜３８Ｂと同様の構成要素である。
コンピュータ１Ｄと、図１の暗号化コンピュータ１Ｂとの差異は、データ処理部３２Ｂの代わりに署名検証処理部３２Ｄを有している点である。
【０１３６】
なお、署名生成処理部３２Ｃおよび署名検証処理部３２Ｄは、ＲＯＭ３４Ｃや、外部記憶装置３５Ｄや、図示しないフラッシュメモリなどに格納されたプログラムが、ＲＡＭ３１Ｃ，３１Ｄに展開され、ＣＰＵ２１Ｃ，２１Ｄによって実行されることによって具現化する。
また、スカラー倍計算部３３Ｃ，３３Ｄは、図２または図１０に示す構成を有しているため、図示および説明を省略する。
なお、定数３８Ｃおよび定数３８Ｄには、共通のＫｏｂｌｉｔｚ曲線上の定点Ｑが格納されている。
【０１３７】
第４実施形態においても、前記した実施形態同様、コンピュータ１Ｄ内の各プログラムは、予め、コンピュータ１Ｄ内のＲＯＭ３４Ｄや外部記憶装置３５Ｄに格納されていてもよいし、必要なときに、コンピュータ１Ｄが利用可能な媒体を介して、他の装置からＲＯＭ３４Ｄや外部記憶装置３５Ｄに格納してもよい。
さらに、スマートカード１Ｃ内の各プログラムは、予め、スマートカード１Ｃ内のＲＯＭ３４Ｃに格納されていてもよいし、必要なときに、入出力インタフェース４Ｃを介して接続するコンピュータ、または当該コンピュータが利用可能な媒体を介して、ＲＡＭ３１Ｃに展開されてもよい。ここで、媒体とは、たとえば当該コンピュータに着脱可能な記憶媒体、または通信媒体（すなわちネットワークまたはネットワークを伝搬する搬送波）を指す。
【０１３８】
次に、第４実施形態の署名検証システムＢにおける署名生成処理と署名検証処理を、図１４を参照しつつ、図１５および図１６に沿って説明する。
離散対数問題に基づくディジタル署名方法を楕円曲線上の離散対数問題に基づく方法に対応させて構成する楕円曲線ディジタル署名アルゴリズム（ＥＣＤＳＡ：Elliptic Curve Digital Signature Algorithm）という署名方法がある。ＥＣＤＳＡ署名については、例えば、D. Johnson, A. Menezes, The Elliptic Curve Digital Signature Algorithm (ECDSA), Technical Report CORR 99-34, Department of Combinatorics and Optimization, University of Waterloo, Canada.（http://www.cacr.math.uwaterloo.ca/techreports/1999/corr99-34.pdf）に記載されている。
【０１３９】
（情報の送受信）
まず、図１５を参照して、第４実施形態に係る署名生成処理を説明する。
図１５および図１６は、第４実施形態に係るメッセージの署名生成処理および署名検証処理を行う場合におけるスマートカード１Ｃおよびコンピュータ１Ｄ内の情報の送受信について説明するタイミングチャートである。
まず、コンピュータ１Ｄは、ランダムに選んだ数値をチャレンジコードとして、インタフェース４Ｃを介してスマートカード１Ｃに転送する。
そして、スマートカード１Ｃの署名生成処理部３２Ｃは、チャレンジコードを入力メッセージとして受け付け（Ｓ７０１）、チャレンジコードのハッシュ値をとり、所定のビット長の数値ｆに変換する。
そして、署名生成処理部３２Ｃは、乱数ｕを生成し（Ｓ７０２）、記憶部３Ｃ（具体的にはＲＯＭ３４Ｃ）に格納されている秘密情報３７Ｃから秘密鍵ｄを読み出し、定数３８ＣからＫｏｂｌｉｔｚ曲線上の定点Ｑを読み出す（Ｓ７０３）。生成した乱数ｕ（スカラー値）を読み出したＫｏｂｌｉｔｚ曲線上の定点Ｑとともにスカラー倍計算部３３Ｃへ送る（Ｓ７０４）。
スカラー倍計算部３３Ｃのエンコード部３００（図２）あるいはエンコード部３００ａ（図１０）は、第１実施形態〜第３実施形態のうちいずれかのエンコード処理を行うことによって（Ｓ７０５）、乱数ｕのτ−ＭＬＦ表現の数値列を計算する。
そして、実計算部３５０は、乱数ｕのτ−ＭＬＦ表現の数値列を使用して、定点Ｑのスカラー倍点ｕＱ＝（ｘｕ，ｙｕ）を計算する実計算処理（図７）を行う（Ｓ７０６）。
そして、スカラー倍計算部３３Ｃは、計算されたスカラー倍点を署名生成処理部３２Ｃへ送る（Ｓ７０７）。
署名生成処理部３２Ｃは、送られたスカラー倍点を用いて署名生成処理を行う（Ｓ７０８）。例えば、前記したＥＣＤＳＡ署名であれば、署名生成処理部３２Ｃは、以下の式（３１），（３２）を計算することにより、チャレンジコードに対応する署名（ｓ，ｔ）を得る。
【０１４０】
ｓ＝ｘｕ  ｍｏｄ  ｑ  ・・・式（３１）
ｔ＝ｕ−１（ｆ＋ｄｓ）  ｍｏｄ  ｑ  ・・・式（３２）
【０１４１】
ここで、ｑは定点Ｑの位数、すなわち、定点Ｑのｑ倍点ｑＱが無限遠点になり、ｑより小さな数値ｍに対する定点Ｑのｍ倍点ｍＱは無限遠点にはならない、という数値のことである。
署名生成処理部３２Ｃは、生成した署名を出力メッセージとして入出力インタフェース４Ｃを介して出力し（Ｓ７０９）、インタフェース４Ｄを介してコンピュータ１Ｄへ転送する。
【０１４２】
次に、図１６を参照してコンピュータ１Ｄにおける署名検証処理を説明する。
コンピュータ１Ｄの署名検証処理部３２Ｄは、スマートカード１Ｃから署名が入力メッセージとして入力されると（Ｓ８０１）、署名の数値ｓ，ｔが適切な範囲内すなわち１≦ｓ，ｔ＜ｑであるかを調べる署名範囲検証処理を行う（Ｓ８０２）。
数値ｓ，ｔがこの範囲内になければチャレンジコードに対する署名の検証結果として「無効」を出力し、スマートカード１Ｃを拒絶する（図示せず）。
【０１４３】
一方、数値ｓ，ｔがこの範囲内にあれば、署名検証処理部３２Ｄは、以下の式（３３）〜（３５）を計算する。
【０１４４】
ｈ＝ｔ−１  ｍｏｄ  ｑ  ・・・  式（３３）
ｈ１＝ｆｈ  ｍｏｄ  ｑ  ・・・  式（３４）
ｈ２＝ｓｈ  ｍｏｄ  ｑ  ・・・  式（３５）
【０１４５】
署名検証処理部３２Ｄは、記憶部３Ｄ（具体的には外部記憶装置３５Ｄ）に格納されている定数３８Ｄから公開鍵ｄＱおよびＫｏｂｌｉｔｚ曲線上の定点Ｑを読み出す（Ｓ８０３）。なお、公開鍵ｄＱは、スカラー倍計算部３３Ｄによって第１実施形態〜第３実施形態のいずれかの方法で予め計算され、記憶部３Ｄに格納されている。そして、読み出した公開鍵ｄＱおよび定点Ｑ（いずれもＫｏｂｌｉｔｚ曲線上の定点）と、計算したｈ１，ｈ２（スカラー値）とを、スカラー倍計算部３３Ｄへ送る（Ｓ８０４）。
スカラー倍計算部３３Ｄのエンコード部３００（図２）またはエンコード部３００ａ（図１０）は、第１実施形態〜第３実施形態のうち、いずれかのエンコード処理を行う（Ｓ８０５）ことによって、ｈ１およびｈ２のτ−ＭＬＦ表現の数値列を計算する。
そして、実計算部３５０（図２）が、定点Ｑとｈ１とによるスカラー倍点ｈ１Ｑと、公開鍵ｄＱとｈ２とによるスカラー倍点ｈ２ｄＱとを計算する実計算処理（図７）を行う（Ｓ８０６）。
そして、スカラー倍計算部３３Ｄは、出力された定点Ｑとｈ１とによるスカラー倍点ｈ１Ｑと、公開鍵ｄＱとｈ２とによるスカラー倍点ｈ２ｄＱとを署名検証処理部３２Ｄへ送る（Ｓ８０７）。
【０１４６】
署名検証処理部３２Ｄは、送られたスカラー倍点を用いて署名検証処理を行う（Ｓ８０８）。
例えば、ＥＣＤＳＡの署名検証であれば、署名検証処理部３２Ｄは、点Ｒを以下の式（３６）により計算する。
【０１４７】
Ｒ＝ｈ１Ｑ＋ｈ２ｄＱ  ・・・  式（３６）
【０１４８】
そして、そのｘ座標をｘＲとしたとき、署名検証処理部３２Ｄは、以下の式（３７）を計算する。
【０１４９】
ｓａ＝ｘＲ  ｍｏｄ  ｑ  ・・・  式（３７）
【０１５０】
ｓａ＝ｓであれば、署名検証処理部３２Ｄは、チャレンジコード１１４２に対する署名の検証結果（出力メッセージ）として「有効」をディスプレイ５Ｄに出力し（Ｓ８０９）、スマートカード１Ｃを認証する。
一方、ｓａ＝ｓでなければ、署名検証処理部３２Ｄは、チャレンジコード１１４２に対する署名の検証結果（出力メッセージ）として「無効」をディスプレイ５Ｄに出力し（Ｓ８０９）、スマートカード１Ｃを拒絶する。
【０１５１】
（第４実施形態の効果）
このように、第４実施形態では署名生成処理および署名検証処理において、スカラー倍点を計算する。従って、署名生成および署名検証におけるスカラー倍計算を行う際に、第１実施形態、第２実施形態または第３実施形態のスカラー倍計算方法を用いることが可能である。これらの実施形態のスカラー倍計算方法を用いることにより、スマートカード１Ｃといったリソースが限られた環境においても、高い安全性と高速な処理とを実現することができる。
【０１５２】
なお、第４実施形態では、スマートカード１Ｃを用いたが、演算装置を有している可搬型小型記憶媒体であればよく、例えば演算装置を有しているＵＳＢ（Universal Serial Bus）メモリなどを用いてもよい。また、例えばＲＦＩＤ（Radio Frequency Identification）に秘密情報３７Ｃと、定数３８Ｃを格納しておき、ライタが署名生成処理部３２Ｃ、スカラー倍計算部３３Ｃ、変換テーブル３６Ｃを有し、ライタが署名の生成を行ってもよい。
【０１５３】
なお、本実施形態では、署名生成をスマートカード１Ｃが行い、署名検証をコンピュータ１Ｄが行ったが、これに限らず、署名生成をコンピュータが行い、署名検証をスマートカードが行ってもよいし、署名生成・署名検証の双方をコンピュータが行ってもよい。        
【０１５４】
《第５実施形態：鍵交換システム》
次に、本発明をＫｏｂｌｉｔｚ曲線を用いた楕円Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ鍵共有スキームに適用して実現する鍵交換システムＣを第５実施形態として説明する。
図１７は、第５実施形態に係る鍵交換システムの構成例を示す図である。
本実施形態の鍵交換システムＣのシステム構成は、図１と同様である。ただし、図１のデータ処理部３２Ａ，３２Ｂは、本実施形態においては、それぞれコンピュータ１Ｅ，１Ｆの鍵交換処理部３２Ｅ，３２Ｆとして機能する。
図１７の符号２Ｅ〜６Ｅ，２１Ｅ，２２Ｅ，３１Ｅ，３３Ｅ〜３８Ｅは、図１の符号２Ａ〜６Ａ，２１Ａ，２２Ａ，３１Ａ，３３Ａ〜３８Ａと同様の構成要素である。
また、図１７の符号２Ｆ〜６Ｆ，２１Ｆ，２２Ｆ，３１Ｆ，３３Ｆ〜３８Ｆは、図１の符号２Ｂ〜６Ｂ，２１Ｂ，２２Ｂ，３１Ｂ，３３Ｂ〜３８Ｂと同様の構成要素である。
なお、定数３８Ｅおよび定数３８Ｆには、共通のＫｏｂｌｉｔｚ曲線上の定点Ｑが格納されている。
【０１５５】
鍵交換処理部３２Ｅ，３２Ｆは、外部記憶装置３５Ｅ，３５Ｆや、ＲＯＭ３４Ｅ，３４Ｆや、図示しないフラッシュメモリなどに格納されているプログラムがＲＡＭ３１Ｅ，３１Ｆに展開され、ＣＰＵ２１Ｅ、２１Ｆやコプロセッサ２２Ｅ，２２Ｆなどの演算装置によって実行されている。
【０１５６】
（情報の送受信）
次に、第５実施形態の鍵交換システムＣのコンピュータ１Ｅおよびコンピュータ１Ｆが、入力されたデータから共有情報の導出を行う場合の動作について図１７を参照しつつ、図１８に沿って説明する。
図１８は、第５実施形態に係る鍵交換処理を行う場合におけるコンピュータ１Ｅおよびコンピュータ１Ｆ内の情報の送受信について説明するタイミングチャートである。
【０１５７】
コンピュータ１Ｅの鍵交換処理部３２Ｅは、コンピュータ１Ｆが出力した公開鍵ｂＱのデータを入力メッセージとして受け付ける（Ｓ９０１）。ここで、公開鍵ｂＱはＫｏｂｌｉｔｚ曲線上の定点である。
そして、鍵交換処理部３２Ｅは、記憶部３Ｅ（具体的には、外部記憶装置３５Ｅ）の秘密情報３７Ｅからコンピュータ１Ｅの秘密鍵ｄを読み出し（Ｓ９０２）、秘密鍵ｄ（スカラー値）とコンピュータ１Ｆが出力した公開鍵ｂＱ（Ｋｏｂｌｉｔｚ曲線上の定点）とをスカラー倍計算部３３Ｅへ送る（Ｓ９０３）。
【０１５８】
スカラー倍計算部３３Ｅのエンコード部３００（図２）またはエンコード部３００ａ（図１０）は、第１実施形態〜第３実施形態のうち、いずれかのエンコード処理を行う（Ｓ９０４）ことによって、秘密鍵ｄのτ−ＭＬＦ表現の数値列を計算する。
そして、実計算部３５０（図２）が、秘密鍵ｄのτ−ＭＬＦ表現の数値列を用いて、公開鍵ｂＱによるスカラー倍点ｄｂＱを計算する実計算処理（図７）を行う（Ｓ９０５）。
そして、スカラー倍計算部３３Ｅは、計算したスカラー倍点ｄｂＱと秘密鍵ｄとを鍵交換処理部３２Ｅへ送る（Ｓ９０６）。
鍵交換処理部３２Ｅは、送られたスカラー倍点ｄｂＱを用いて共有情報の導出を行い（Ｓ９０７）、記憶部３Ｅ（具体的には外部記憶装置３５Ｅ）に秘密情報３７Ｅとして格納する（Ｓ９０８）。ステップＳ９０７において、鍵交換処理部３２Ｅは、例えば、スカラー倍点ｄｂＱのｘ座標を共有情報とする。
【０１５９】
コンピュータ１Ｅの鍵交換処理部３２Ｅおよびスカラー倍計算部３３Ｅは、記憶部３Ｅの秘密情報３７Ｅから秘密鍵ｄを読み出し（Ｓ９０９）、定数３７ＥからＫｏｂｌｉｔｚ曲線上の定点Ｑを読み出し、コンピュータ１Ｅの公開鍵ｄＱを計算する（Ｓ９１０）。具体的には、鍵交換処理部３２Ｅは、スカラー値としての秘密鍵ｄと、Ｋｏｂｌｉｔｚ曲線上の定点Ｑをスカラー倍計算部３３Ｅへ送り、スカラー倍計算部３３Ｅは第１実施形態〜第３実施形態のいずれかの方法でスカラー倍点ｄＱを計算する。そして、スカラー倍計算部３３Ｅは、計算したスカラー倍点ｄＱを鍵交換処理部３２Ｅへ送る。
【０１６０】
そして、鍵交換処理部３２Ｅは、ネットワーク６を介して、計算した公開鍵ｄＱを出力メッセージとしてコンピュータ１Ｆに転送する（Ｓ９１１）。
【０１６１】
次に、コンピュータ１Ｆが、入力されたデータから共有情報の導出を行う場合の動作について同じく図１８を参照して説明する。
コンピュータ１Ｆの鍵交換処理部３２Ｆは、コンピュータ１Ｅの公開鍵ｄＱを、入力メッセージとして受け付ける（Ｓ９０１）。
そして、鍵交換処理部３２Ｆは、記憶部３Ｆ（具体的には外部記憶装置３５Ｆ）の秘密情報３７Ｆからコンピュータ１Ｆの秘密鍵ｂを読み出し（Ｓ９０２）、読み出した秘密鍵ｂ（スカラー値）とコンピュータ１Ｅから受信した公開鍵ｄＱ（Ｋｏｂｌｉｔｚ曲線上の定点）とをスカラー倍計算部３３Ｆへ送る（Ｓ９０３）。
【０１６２】
スカラー倍計算部３３Ｆのエンコード部３００（図２）またはエンコード部３００ａ（図１０）は、第１実施形態〜第３実施形態のうち、いずれかのエンコード処理を行う（Ｓ９０４）ことにより、秘密鍵ｂのτ−ＭＬＦ表現の数値列を計算する。
そして、実計算部３５０（図２）が、秘密鍵ｂのτ−ＭＬＦ表現の数値列を用いて公開鍵ｄＱによるスカラー倍点ｂｄＱを計算する実計算処理（図７）を行う（Ｓ９０５）。
そして、スカラー倍計算部３３Ｆは、計算されたスカラー倍点ｂｄＱと秘密鍵ｂとを鍵交換処理部３２Ｆへ送る（Ｓ９０６）。
鍵交換処理部３２Ｆは、送られたスカラー倍点を用いて共有情報の導出を行い（Ｓ９０７）、記憶部３Ｆ（具体的には外部記憶装置３５Ｆ）に秘密情報３７Ｆとして格納する（Ｓ９０８）ステップＳ９０７において、鍵交換処理部３２Ｆは、例えば、スカラー倍点ｂｄＱのｘ座標を共有情報とする。
コンピュータ１Ｆの鍵交換処理部３２Ｆおよびスカラー倍計算部３３Ｆは、記憶部３Ｆの秘密情報３７Ｆから秘密鍵ｂを読み出し、定数３８ＦからＫｏｂｌｉｔｚ曲線上の定点Ｑを読み出し、コンピュータ１Ｆの公開鍵ｂＱを計算する（Ｓ９０９）。
具体的には、鍵交換処理部３２Ｆは、スカラー値としての秘密鍵ｂと、Ｋｏｂｌｉｔｚ曲線上の定点Ｑをスカラー倍計算部３３Ｆへ送り、スカラー倍計算部３３Ｆは第１実施形態〜第３実施形態のいずれかの方法でスカラー倍点ｂＱを計算する。そして、スカラー倍計算部３３Ｆは、計算したスカラー倍点ｂＱを鍵交換処理部３２Ｆへ送る。
【０１６３】
そして、鍵交換処理部３２Ｆは、ネットワーク６を介して、公開鍵ｂＱを出力メッセージとしてコンピュータ１Ｅに転送する（Ｓ９０９）。
【０１６４】
例えば、スカラー倍点ｂｄＱのｘ座標を共有情報とする。ここで、数ｄｂと数ｂｄとは数値として同じなので、点ｄｂＱと点ｂｄＱとは同じ点となり、同じ情報が導出されたことになる。
【０１６５】
ネットワーク６には、Ｋｏｂｌｉｔｚ曲線上の定点ｄＱと点ｂＱが送信される。しかし、点ｄｂＱ（もしくは点ｂｄＱ）を計算するためには、秘密鍵ｄもしくは秘密鍵ｂが必要である。すなわち、秘密鍵ｄもしくは秘密鍵ｂを知らなければ、共有情報を得ることはできない。従って、これらの方法で得られた共有情報は、共通鍵暗号の秘密鍵として利用できる。
【０１６６】
なお、第５実施形態ではコンピュータ１Ｅ，１ＦとしてＰＣを想定しているが、これに限らず、どちらか一方がスマートカードのような演算装置を有する可搬型小型記憶媒体でもよい。
【０１６７】
（第５実施形態の効果）
第５実施形態の鍵交換システムＣでは、受け取った点のスカラー倍点を計算する。従って、鍵交換を行う際に、第１実施形態〜第３実施形態のうちのいずれかのスカラー倍計算方法を用いることが可能である。これらの実施形態のスカラー倍計算方法を用いることにより、高い安全性と高速な処理とを実現することができる。
【０１６８】
なお、前記した各実施形態では、データ処理部３２Ａ，３２Ｂ、署名生成処理部３２Ｃ、署名検証処理部３２Ｄ、鍵交換処理部３２Ｅ，３２Ｆを、ソフトウェアで実現するものとして説明したが、専用のハードウェアを用いて実現してもよい。また、スカラー倍計算部３３Ａ〜３３Ｆをコプロセッサ２２Ａ〜２２Ｆまたはそれ以外の専用ハードウェアで実現してもよい。また、１台のコンピュータが、データ処理部３２Ａ，３２Ｂ、署名生成処理部３２Ｃ、署名検証処理部３２Ｄ、鍵交換処理部３２Ｅ，３２Ｆのうち、任意の一つ以上の処理を行うことができるよう構成してもよい。
【符号の説明】
【０１６９】
１Ａ    暗号化コンピュータ（スカラー倍計算装置，暗号化装置）
１Ｂ    復号化コンピュータ（スカラー倍計算装置，復号化装置）
１Ｃ    スマートカード（署名生成装置、可搬型小型記憶媒体）
１Ｄ    コンピュータ（署名検証装置）
１Ｅ，１Ｆ  コンピュータ（鍵交換装置）
２Ａ〜２Ｆ  処理部
３Ａ〜３Ｆ  記憶部
４Ａ〜４Ｆ  入出力インタフェース（入力部）
５Ａ，５Ｂ，５Ｄ〜５Ｆ  ディスプレイ
６Ａ，６Ｂ，６Ｄ〜６Ｆ  キーボード
２１Ａ〜２１Ｆ  ＣＰＵ
２２Ａ〜２２Ｆ  コプロセッサ
３１Ａ〜３１Ｆ  ＲＡＭ
３２Ａ，３２Ｂ  データ処理部
３２Ｃ  署名生成処理部
３２Ｄ  署名検証処理部
３２Ｅ，３２Ｆ  鍵交換処理部
３３，３３Ａ，３３Ａ〜３３Ｆ  スカラー倍計算部
３４Ａ〜３４Ｆ  ＲＯＭ
３５Ａ，３５Ｂ，３５Ｄ〜３５Ｆ  外部記憶装置
３６，３６Ａ〜３６Ｆ，３６ａ〜３６ｃ  変換テーブル（変換情報）
３７，３７Ａ〜３７Ｆ  秘密情報
３８Ａ〜３８Ｆ  定数
３００，３００ａ  エンコード部
３０１  τ−ＮＡＦ計算部
３０２  τ−ＮＡＦ長計算部
３０３  格納部
３０４  δ剰余計算部
３０５  条件判定部
３０６  τ−ＭＬＦ計算部
３１１  桁対計算部
３１２  長さ判定部
３５０  実計算部
３５１  加算部
３５２  τ倍算部
３５３  繰り返し判定部
３５４  数値判定部
Ａ      暗号通信システム
Ｂ      署名検証システム
Ｃ      鍵交換システム
【図１】
2011081147.tif 000007
【図２】
2011081147.tif 000008
【図３】
2011081147.tif 000009
【図４】
2011081147.tif 000010
【図５】
2011081147.tif 000011
【図６】
2011081147.tif 000012
【図７】
2011081147.tif 000013
【図８】
2011081147.tif 000014
【図９】
2011081147.tif 000015
【図１０】
2011081147.tif 000016
【図１１】
2011081147.tif 000017
【図１２】
2011081147.tif 000018
【図１３】
2011081147.tif 000019
【図１４】
2011081147.tif 000020
【図１５】
2011081147.tif 000021
【図１６】
2011081147.tif 000022
【図１７】
2011081147.tif 000023
【図１８】
2011081147.tif 000024