(57)【要約】  署名生成の処理に用いられる値を解析困難にすることのできる署名生成装置を提供する。  署名生成装置は、乱数生成モジュールにより、ｌｅｎビットからなる乱数ｕを生成し、選択モジュールにより、生成した乱数ｕをビット表現に変換し、各ビット値に対応する元対をテーブルメモリ部から取得する。署名生成装置は、ランダム元生成モジュールにより、取得したすべての元対に対して、第１の群Ｇ及び第２の群の基本演算を施して、第１の群Ｇ上の元Ｐｋ及び第２の群Ｇａ上の元Ｐａｋを算出する。署名生成装置は、メッセージｍのハッシュ値ｈ、第１の群Ｇ上の元Ｐｋ及び第２の群Ｇａ上の元Ｐａｋ、変換モジュール、主要演算モジュール、逆変換モジュール、乗算モジュール、除算モジュール及び署名データ生成モジュールを用いて、メッセージｍに対する署名データＳを生成する。
2007074836.tif 000002
【特許請求の範囲】
【請求項１】
群Ｇ及び群Ｇａ上の離散対数問題を安全性の根拠として、群Ｇ上の基本元Ｐについて並びに群Ｇａ上の基本元Ｐａについて基本演算を複数回繰り返す冪演算を施すことにより、メッセージに対するディジタル署名を生成する署名生成装置であって、
複数の数の各々に分解組が予め対応付けられており、各分解組は複数の分解対を含み、各分解対は第１の分解値と第２の分解値とを含み、各第１の分解値は基本元Ｐについて任意の正整数を冪とする冪演算が施されて算出された群Ｇ上の元であり、各第２の分解値は基本元Ｐａについて当該第２の分解値に対応する第１の分解値において用いられた正整数を冪とする冪演算が施されて算出された群Ｇａ上の元であり、
前記署名生成装置は、
前記複数の分解組を記憶する分解値記憶手段と、
前記複数の数からランダムに数ｕを選択し、選択した数ｕに対応する分解組を前記分解値記憶手段から選択する選択手段と、
選択された分解組に含まれる２つ以上の第１の分解値について、前記群Ｇの基本演算を施して、第１の冪乗元を生成し、選択された分解組に含まれ、且つ前記２つ以上の第１の分解値のそれぞれに対応する第２の分解値について、前記群Ｇａの基本演算を施して、第２の冪乗元を生成する生成手段と、
生成された前記第１の冪乗元及びメッセージそれぞれを群Ｇａ上の元に変換し、変換された第１の冪乗元、変換されたメッセージ及び前記第２の冪乗元に対して前記群Ｇａ上の演算を施し、第１の離散対数及び第２の離散対数を算出し、算出した第１及び第２の離散対数を用いて、メッセージに対するディジタル署名を生成する署名手段と
を備えることを特徴とする署名生成装置。
【請求項２】
前記複数の数の各々は、長さが２以上の所定長からなるビット列で表現される数であり、
前記所定長からなるビット列の各ビット値に応じて分解対が対応付けられており、
前記選択手段は、
選択した前記数ｕを前記所定長のビット列からなるビット表現へと変換し、各ビットそれぞれの値に応じた分解対からなる前記分解組を前記分解値記憶手段から選択する
ことを特徴とする請求項１に記載の署名生成装置。
【請求項３】
前記生成手段は、
ビット値ごとに選択された分解対からなる前記分解組に含まれる２つ以上の第１の分解値に対して、前記群Ｇにおける基本演算を施して前記第１の冪乗元を生成し、
ビット値ごとに選択された分解対からなる前記分解組に含まれ、且つ前記２つ以上の第１の分解値のそれぞれに対応する第２の分解値に対して、前記群Ｇａにおける前記基本演算を施して前記第２の冪乗元を生成する
ことを特徴とする請求項２に記載の署名生成装置。
【請求項４】
前記第１の冪乗元は、２つ以上の値を含み、
前記署名手段は、
前記メッセージに対するハッシュ値を冪とし、前記基本元Ｐａに対して群Ｇａにおける前記冪演算を施すことにより、前記ハッシュ値を前記群Ｇａに属する変換後ハッシュ値へと変換する変換部と、
前記第１の冪乗元に含まれる１つの値を用いて、第１のデータを算出する第１演算部と、
前記変換後ハッシュ値に、前記群Ｇａ上の基本演算を施し、前記群Ｇａに属する第３の冪乗元を算出する第２演算部と、
前記群Ｇａ又は前記群Ｇａに真に含まれる部分群Ｓａにおいて、前記第２の冪乗元及び前記第３の冪乗元それぞれに対して、前記変換部にて行われる変換の冪演算の逆算を施すことにより、第１及び第２の離散対数を求める逆変換部と、
前記第１及び前記第２の離散対数を用いて、第２のデータを算出する第３演算部と、
前記第１のデータと前記第２のデータとの組からなるディジタル署名を生成するデータ生成部と
を含むことを特徴とする請求項１に記載の署名生成装置。
【請求項５】
前記署名生成装置は、さらに、
秘密鍵を冪として前記基本元Ｐａに対して前記群Ｇａの基本演算を施して、前記群Ｇａに属する変換後秘密鍵を記憶している変換後秘密鍵記憶手段を備え、
前記第２演算部は、
前記変換後秘密鍵に対して前記第１のデータを冪とする前記群Ｇａの冪演算を施して得られる前記群Ｇａ上の元である演算結果と、前記変換後ハッシュ値とに対して前記群Ｇａ上の基本演算を施して前記第３の冪乗元を算出する
ことを特徴とする請求項４に記載の署名生成装置。
【請求項６】
前記群Ｇ及び前記群Ｇａは、剰余整数環の乗法群であり、
前記群Ｇ及び前記群Ｇａのそれぞれにおける基本演算とは、各元に対して乗算を施す乗法演算であり、
前記群Ｇ及び前記群Ｇａのそれぞれにおける冪演算とは、正整数を冪数とする冪乗演算である
ことを特徴とする請求項５に記載の署名生成装置。
【請求項７】
前記群Ｇａは、２つの素数ｐ、ｑと、正整数ｍとを用いて表されるｎ＝ｐ＾ｍ×ｑに対し、Ｚ／ｎＺの乗法群であり、＾は冪乗算を示す演算子であり、×は、乗算を示す演算子であり、Ｚは整数環であり、Ｚ／ｎＺは剰余整数環である
ことを特徴とする請求項６に記載の署名生成装置。
【請求項８】
前記部分群Ｓａは、Ｚ／ｐ＾ｍ  Ｚの乗法群である
ことを特徴とする請求項７に記載の署名生成装置。
【請求項９】
前記正整数ｍは２である
ことを特徴とする請求項８に記載の署名生成装置。
【請求項１０】
前記群Ｇは、楕円曲線の群であり、
前記部分群Ｓａは、アノマラス楕円曲線の群であり、
前記群Ｇ及び前記群Ｇａのそれぞれにおける基本演算とは、各元に対して楕円曲線上の加算を施す演算であり、
前記群Ｇ及び前記群Ｇａのそれぞれにおける冪演算とは、前記正整数に楕円曲線上の乗算を施す演算である
ことを特徴とする請求項４に記載の署名生成装置。
【請求項１１】
前記群Ｇは、楕円曲線の群であり、
前記群Ｇａは、２つのアノマラス楕円曲線の直積であり、
前記群Ｇ及び前記群Ｇａのそれぞれにおける基本演算とは、各元に対して楕円曲線上の加算を施す演算であり、
前記群Ｇ及び前記群Ｇａのそれぞれにおける冪演算とは、正整数に楕円曲線上の乗算を施す演算である
ことを特徴とする請求項４に記載の署名生成装置。
【請求項１２】
前記逆変換部は、前記群Ｇａに属する元を、前記部分群Ｓａに属する元に還元する還元部を含み、
前記逆変換部は、前記還元部を用いて前記第２の冪乗元及び前記第３の冪乗元それぞれを、前記部分群Ｓａに属する元に還元し、還元した元それぞれに対して、前記逆算を施すことにより、前記第１の離散対数及び前記第２の離散対数を求める
ことを特徴とする請求項４に記載の署名生成装置。
【請求項１３】
群Ｇ及び群Ｇａ上の離散対数問題を安全性の根拠として、群Ｇ上の基本元Ｐについて並びに群Ｇａ上の基本元Ｐａについて基本演算を複数回繰り返す冪演算を施すことにより、メッセージに対するディジタル署名を生成する署名生成装置であって、
複数の数の各々に分解組が予め対応付けられており、各分解組は複数の分解対を含み、各分解対は第１の分解値と第２の分解値とを含み、各第１の分解値は基本元Ｐについて任意の正整数を冪とする冪演算が施されて算出された群Ｇ上の元であり、各第２の分解値は基本元Ｐａについて当該第２の分解値に対応する第１の分解値において用いられた正整数を冪とする冪演算が施されて算出された群Ｇａ上の元であり、
前記署名生成装置は、
前記複数の分解組を記憶する分解値記憶手段と、
前記複数の数からランダムに数ｕを選択し、選択した数ｕに対応する分解対を前記分解値記憶手段から選択する選択手段と、
選択された分解対に含まれる第１の分解値及びメッセージそれぞれを群Ｇａ上の元に変換し、変換された第１の分解対、変換されたメッセージ及び選択された分解対に含まれる第２の分解値に対して前記群Ｇａ上の演算を施し、離散対数問題を解いて第１及び第２の離散対数を算出し、算出した第１及び第２の離散対数を用いて、メッセージに対するディジタル署名を生成する署名手段と
を備えることを特徴とする署名生成装置。
【請求項１４】
群Ｇ及び群Ｇａ上の離散対数問題を安全性の根拠として、群Ｇ上の基本元Ｐについて並びに群Ｇａ上の基本元Ｐａについて基本演算を複数回繰り返す冪演算を施すことにより、メッセージに対するディジタル署名を生成する署名生成装置で用いられる署名生成方法であって、
複数の数の各々に分解組が予め対応付けられており、各分解組は複数の分解対を含み、各分解対は第１の分解値と第２の分解値とを含み、各第１の分解値は基本元Ｐについて任意の正整数を冪とする冪演算が施されて算出された群Ｇ上の元であり、各第２の分解値は基本元Ｐａについて当該第２の分解値に対応する第１の分解値において用いられた正整数を冪とする冪演算が施されて算出された群Ｇａ上の元であり、
前記署名生成装置は、
前記複数の分解組を記憶する分解値記憶手段を備え、
前記署名生成方法は、
前記複数の数からランダムに数ｕを選択し、選択した数ｕに対応する分解組を前記分解値記憶手段から選択する選択ステップと、
選択された分解組に含まれる２つ以上の第１の分解値について、前記群Ｇの基本演算を施して、第１の冪乗元を生成し、選択された分解組に含まれ、且つ前記２つ以上の第１の分解値のそれぞれに対応する第２の分解値について、前記群Ｇａの基本演算を施して、第２の冪乗元を生成する生成ステップと、
生成された前記第１の冪乗元及びメッセージそれぞれを群Ｇａ上の元に変換し、変換された第１の冪乗元、変換されたメッセージ及び前記第２の冪乗元に対して前記群Ｇａ上の演算を施し、第１の離散対数及び第２の離散対数を算出し、算出した第１及び第２の離散対数を用いて、メッセージに対するディジタル署名を生成する署名ステップと
を含むことを特徴とする署名生成方法。
【請求項１５】
群Ｇ及び群Ｇａ上の離散対数問題を安全性の根拠として、群Ｇ上の基本元Ｐについて並びに群Ｇａ上の基本元Ｐａについて基本演算を複数回繰り返す冪演算を施すことにより、メッセージに対するディジタル署名を生成する署名生成装置で用いられる署名生成プログラムであって、
複数の数の各々に分解組が予め対応付けられており、各分解組は複数の分解対を含み、各分解対は第１の分解値と第２の分解値とを含み、各第１の分解値は基本元Ｐについて任意の正整数を冪とする冪演算が施されて算出された群Ｇ上の元であり、各第２の分解値は基本元Ｐａについて当該第２の分解値に対応する第１の分解値において用いられた正整数を冪とする冪演算が施されて算出された群Ｇａ上の元であり、
前記署名生成装置は、
前記複数の分解組を記憶する分解値記憶手段を備え、
前記署名生成プログラムは、
前記複数の数からランダムに数ｕを選択し、選択した数ｕに対応する分解組を前記分解値記憶手段から選択する選択ステップと、
選択された分解組に含まれる２つ以上の第１の分解値について、前記群Ｇの基本演算を施して、第１の冪乗元を生成し、選択された分解組に含まれ、且つ前記２つ以上の第１の分解値のそれぞれに対応する第２の分解値について、前記群Ｇａの基本演算を施して、第２の冪乗元を生成する生成ステップと、
生成された前記第１の冪乗元及びメッセージそれぞれを群Ｇａ上の元に変換し、変換された第１の冪乗元、変換されたメッセージ及び前記第２の冪乗元に対して前記群Ｇａ上の演算を施し、第１の離散対数及び第２の離散対数を算出し、算出した第１及び第２の離散対数を用いて、メッセージに対するディジタル署名を生成する署名ステップと
を含むことを特徴とする署名生成プログラム。
【請求項１６】
前記複数の数の各々は、長さが２以上の所定長からなるビット列で表現される数であり、
前記所定長からなるビット列の各ビット値に応じて分解対が対応付けられており、
前記選択ステップは、
選択した前記数ｕを前記所定長のビット列からなるビット表現へと変換し、各ビットそれぞれの値に応じた分解対からなる前記分解組を前記分解値記憶手段から選択する
ことを特徴とする請求項１５に記載の署名生成プログラム。
【請求項１７】
前記生成ステップは、
ビット値ごとに選択された分解対からなる前記分解組に含まれる２つ以上の第１の分解値に対して、前記群Ｇにおける基本演算を施して前記第１の冪乗元を生成し、
ビット値ごとに選択された分解対からなる前記分解組に含まれ、且つ前記２つ以上の第１の分解値のそれぞれに対応する第２の分解値に対して、前記群Ｇａにおける前記基本演算を施して前記第２の冪乗元を生成する
ことを特徴とする請求項１６に記載の署名生成プログラム。
【請求項１８】
前記署名生成プログラムは、コンピュータ読み取り可能な記録媒体に記録されていることを特徴とする請求項１５に記載の署名生成プログラム。
【請求項１９】
群Ｇ及び群Ｇａ上の離散対数問題を安全性の根拠として、群Ｇ上の基本元Ｐについて並びに群Ｇａ上の基本元Ｐａについて基本演算を複数回繰り返す冪演算を施すことにより、メッセージに対するディジタル署名を生成する署名生成装置の集積回路であって、
複数の数の各々に分解組が予め対応付けられており、各分解組は複数の分解対を含み、各分解対は第１の分解値と第２の分解値とを含み、各第１の分解値は基本元Ｐについて任意の正整数を冪とする冪演算が施されて算出された群Ｇ上の元であり、各第２の分解値は基本元Ｐａについて当該第２の分解値に対応する第１の分解値において用いられた正整数を冪とする冪演算が施されて算出された群Ｇａ上の元であり、
前記集積回路は、
前記複数の分解組を記憶する分解値記憶手段と、
前記複数の数からランダムに数ｕを選択し、選択した数ｕに対応する分解組を前記分解値記憶手段から選択する選択手段と、
選択された分解組に含まれる２つ以上の第１の分解値について、前記群Ｇの基本演算を施して、第１の冪乗元を生成し、選択された分解組に含まれ、且つ前記２つ以上の第１の分解値のそれぞれに対応する第２の分解値について、前記群Ｇａの基本演算を施して、第２の冪乗元を生成する生成手段と、
生成された前記第１の冪乗元及びメッセージそれぞれを群Ｇａ上の元に変換し、変換された第１の冪乗元、変換されたメッセージ及び前記第２の冪乗元に対して前記群Ｇａ上の演算を施し、第１の離散対数及び第２の離散対数を算出し、算出した第１及び第２の離散対数を用いて、メッセージに対するディジタル署名を生成する署名手段と
を備えることを特徴とする集積回路。
【請求項２０】
群Ｇ及び群Ｇａ上の離散対数問題を安全性の根拠として、群Ｇ上の基本元Ｐについて並びに群Ｇａ上の基本元Ｐａについて基本演算を複数回繰り返す冪演算を施す演算装置であって、
複数の数の各々に分解組が予め対応付けられており、各分解組は複数の分解対を含み、各分解対は第１の分解値と第２の分解値とを含み、各第１の分解値は基本元Ｐについて任意の正整数を冪とする冪演算が施されて算出された群Ｇ上の元であり、各第２の分解値は基本元Ｐａについて当該第２の分解値に対応する第１の分解値において用いられた正整数を冪とする冪演算が施されて算出された群Ｇａ上の元であり、
前記演算装置は、
前記複数の分解組を記憶する分解値記憶手段と、
前記複数の数からランダムに数ｕを選択し、選択した数ｕに対応する分解組を前記分解値記憶手段から選択する選択手段と、
選択された分解組に含まれる２つ以上の第１の分解値について、前記群Ｇの基本演算を施して、第１の冪乗元を生成し、選択された分解組に含まれ、且つ前記２つ以上の第１の分解値のそれぞれに対応する第２の分解値について、前記群Ｇａの基本演算を施して、第２の冪乗元を生成する生成手段と
を備えることを特徴とする演算装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報セキュリティ技術としてのソフトウェアの難読化方法、特にディジタル署名方法の難読化の技術に関する。
【背景技術】
【０００２】
暗号ソフトを実装する場合、鍵や暗号アルゴリズムをそのまま実装すると、ソフトを解析された場合に、簡単に不正使用できる。そのため、ソフト解析を困難にする耐タンパーソフト技術が要望されている。耐タンパーソフト技術として、特許文献１において、演算及び演算領域を変換して、変換前の演算領域を推測困難にすることにより、ソフト解析困難とする方式が記載されている。【０００３】
その方式は、一次変換などにより変換を行う。例えば、鍵とデータの加算を変換する場合、鍵とデータを変換し、変換後のデータを変換後の領域における加算を行い、その結果に逆変換を実行することにより鍵とデータの加算結果を得る。このような難読化された加算方法を、共通鍵暗号を用いた暗号化プログラムや復号化プログラムに適用することにより、プログラムを解析して鍵を得る攻撃に対する安全性を向上させることが可能になる。【０００４】
以下に、特許文献１にて開示された技術の具体例を説明する。
ここで、入力ａ、ｂに対し、演算結果ａ＋ｂを出力するプログラムであり、主要演算モジュール、逆変換モジュール、及び出力モジュールから構成される加算プログラムについて説明する。
変換モジュールは、整数ｋ１、ｋ２を保持し、入力値ａ、ｂを受け付けると、保持している整数ｋ１、ｋ２を用いて、入力値ａ、ｂをそれぞれｔａ＝ｋ１×ａ＋ｋ２、ｔｂ＝ｋ１×ｂ＋ｋ２に変換する。ただし、×は乗算を示す。次に、主要演算モジュールは、値ｔａ、ｔｂに対して、ｔａｂ＝ｔａ＋ｔｂを計算する。逆変換モジュールは、ｔａｂに対して、ｃ＝（ｔａｂ−２×ｋ２）／ｋ１を計算する。出力モジュールは、演算結果ｃを出力する。【０００５】
上記のように処理すると、ｔａｂ＝ｔａ＋ｔｂ＝ｋ１×ａ＋ｋ２＋ｋ１×ｂ＋ｋ２＝ｋ１×（ａ＋ｂ）＋２×ｋ２より、（ｔａｂ−２×ｋ２）／ｋ１＝ａ＋ｂが成り立つ。したがって、ｃ＝ａ＋ｂとなり、加算プログラムは、入力値ａ、ｂからａとｂの加算結果を算出することができる。
ここで、変換モジュール及び逆変換モジュールを解析困難なように実現した場合、第三者（解析者）が解析可能なものは、ｔａ、ｔｂ、ｔａｂのみであり、これらの値からａ、ｂを推測するのが難しいため、ａ、ｂを隠蔽することが可能になる。【０００６】
特許文献１では、データを一次変換することで変換しており、データ自体を解析しにくくしているが、演算の種類、すなわち、「加算」は変換先においても「加算」を実行しており、演算の種類を隠蔽することまではできていない。
特許文献２では、ある情報（落し戸）を持っていれば容易に解ける落し戸付の離散対数問題に基づいて、「加算」を「乗算」もしくは、「楕円曲線上の群の加算」に変換することで、演算の種類の隠蔽を行っている。【０００７】
また、ここで、従来用いられている楕円ＤＳＡ（Ｄｉｇｉｔａｌ  Ｓｉｇｎａｔｕｒｅ  Ａｌｇｏｒｉｔｈｍ）署名方式（以下、「従来型の楕円ＤＳＡ署名方式」という。）について説明する。従来型の楕円ＤＳＡ署名方式については、非特許文献３の４ページに記載されているので、ここでは簡単に説明する。
（１）パラメータ
従来型の楕円ＤＳＡ署名方式では、楕円曲線Ｅの方程式ｙ＾２＝ｘ＾３＋ａ×ｘ＋ｂの変数ａ、ｂ、楕円曲線Ｅの定義体ＧＦ（ｐ）、ベース点Ｐ及びベース点の位数ｑをパラメータとして持つ。ここで、ｘ＾ｙはｘのｙ乗を示し、ｑとＰはｑ＊Ｐ＝Ｏを満たす。Ｏは楕円曲線の群の零元であり、＊は楕円曲線のスカラ倍演算を示し、ｑ＊Ｐはｑ個のＰを加算したものを表す。【０００８】
（２）秘密鍵及び公開鍵
秘密鍵をｋｓ（０＜ｋｓ＜ｑ）とし、ＫＰ＝ｋｓ＊Ｐを公開鍵とする。
（３）署名生成
従来型の楕円ＤＳＡ署名方式の署名生成では、以下のステップで署名の対象となるメッセージｍのディジタル署名Ｓを生成する。【０００９】
（ステップＳ１）  ｈ＝Ｈａｓｈ（ｍ）を計算する。ここで、Ｈａｓｈ（ｍ）はｍのハッシュ値である。メッセージからハッシュ値を求めるハッシュ関数は、例えば、ＳＨＡ−１である。ハッシュ関数については、非特許文献１の１９２〜１９５ページが詳しい。
（ステップＳ２）  乱数ｋを選択し、楕円曲線上の点Ｒ＝ｋ＊Ｐを計算する。
（ステップＳ３）  ｒ＝ｘ（Ｒ）  ｍｏｄ  ｑを計算する。ここで、ｘ（Ｒ）はＲのｘ座標を示す。【００１０】
（ステップＳ４）  ｓ＝（ｈ＋ｒ×ｋｓ）／ｋ  ｍｏｄ  ｑを計算する。
（ステップＳ５）  Ｓ＝（ｒ，ｓ）を出力し終了。
（４）署名検証
従来型の楕円ＤＳＡ署名方式の署名検証では、以下のステップでディジタル署名Ｓを検証し、検証結果（ＯＫまたはＮＧ）を出力する。【００１１】
（ステップＳ１０）  ｈ＝Ｈａｓｈ（ｍ）を計算する。
（ステップＳ１１）  Ｒ’＝（ｈ／ｓ  ｍｏｄ  ｑ）＊Ｐ＋（ｒ／ｓ  ｍｏｄ  ｑ）＊ＫＰを計算し、ｒ’＝ｘ（Ｒ’）とする。
（ステップＳ１２）  ｒ＝ｒ’であるかをチェック。成り立つ場合は、ＯＫ、成り立たない場合は、ＮＧを出力し終了。
【特許文献１】米国特許第６，５９４，７６１号明細書
【特許文献２】国際公開第２００５／０９８７９５号パンフレット
【特許文献３】特許第３，４０２，４４１号明細書
【非特許文献１】岡本龍明、山本博資、「現代暗号」、産業図書（１９９７年）
【非特許文献２】Ｈｅｎｒｉ  Ｃｏｈｅｎ，  “Ａ  Ｃｏｕｒｓｅ  ｉｎ  Ｃｏｍｐｕｔａｔｉｏｎａｌ  Ａｌｇｅｂｒａｉｃ  Ｎｕｍｂｅｒ  Ｔｈｅｏｒｙ”，  ＧＴＭ  １３８，  Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，  １９９３，  ｐｐ．１６−１９
【非特許文献３】Ｉ．  Ｂｌａｋｅ，  Ｇ．  Ｓｅｒｏｕｓｓｉ  ａｎｄ  Ｎ．  Ｓｍａｒｔ，  “Ｅｌｌｉｐｔｉｃ  Ｃｕｒｖｅｓ  ｉｎ  Ｃｒｙｐｔｏｇｒａｐｈｙ”，ＣＡＭＢＲＩＤＧＥ  ＵＮＩＶＥＲＳＩＴＹ  ＰＲＥＳＳ，  １９９９
【非特許文献４】Ｎ．  Ｋｕｎｉｈｉｒｏ  ａｎｄ  Ｋ．  Ｋｏｙａｍａ，  “Ｔｗｏ  Ｄｉｓｃｒｅｔｅ  Ｌｏｇ  Ａｌｇｏｒｉｔｈｍｓ  ｆｏｒ  Ｓｕｐｅｒ−Ａｎｏｍａｌｏｕｓ  Ｅｌｌｉｐｔｉｃ  Ｃｕｒｖｅｓ”，  ＳＣＩＳ’９９，  １９９９，  ｐｐ．  ８６９−８７４
【発明の開示】
【発明が解決しようとする課題】
【００１２】
従来型の楕円ＤＳＡ署名方式の署名生成においては、秘密鍵ｋｓだけでなく、乱数ｋをも秘密にする必要がある。なぜなら、乱数ｋが第三者に知られると、ステップＳ４の式を使ってｋｓを逆算することが可能であるからである。
しかしながら、上記従来例の方式は、演算（加算）の変換を行っており、その演算を使用する部分については、解析困難にすることが可能であるが、従来型の楕円ＤＳＡ署名方式の署名生成において、乱数ｋを解析困難にすることはできない。【００１３】
そこで、本発明は、上記課題に鑑みて、署名生成の処理に用いられる値を解析困難にすることのできる署名生成装置、署名生成方法、署名生成プログラム、記録媒体及び集積回路を提供することを目的とする。
【課題を解決するための手段】
【００１４】
上記目的を達成するために、本発明は、群Ｇ及び群Ｇａ上の離散対数問題を安全性の根拠として、群Ｇ上の基本元Ｐについて並びに群Ｇａ上の基本元Ｐａについて基本演算を複数回繰り返す冪演算を施すことにより、メッセージに対するディジタル署名を生成する署名生成装置であって、複数の数の各々に分解組が予め対応付けられており、各分解組は複数の分解対を含み、各分解対は第１の分解値と第２の分解値とを含み、各第１の分解値は基本元Ｐについて任意の正整数を冪とする冪演算が施されて算出された群Ｇ上の元であり、各第２の分解値は基本元Ｐａについて当該第２の分解値に対応する第１の分解値において用いられた正整数を冪とする冪演算が施されて算出された群Ｇａ上の元であり、前記署名生成装置は、前記複数の分解組を記憶する分解値記憶手段と、前記複数の数からランダムに数ｕを選択し、選択した数ｕに対応する分解組を前記分解値記憶手段から選択する選択手段と、選択された分解組に含まれる２つ以上の第１の分解値について、前記群Ｇの基本演算を施して、第１の冪乗元を生成し、選択された分解組に含まれ、且つ前記２つ以上の第１の分解値のそれぞれに対応する第２の分解値について、前記群Ｇａの基本演算を施して、第２の冪乗元を生成する生成手段と、生成された前記第１の冪乗元及びメッセージそれぞれを群Ｇａ上の元に変換し、変換された第１の冪乗元、変換されたメッセージ及び前記第２の冪乗元に対して前記群Ｇａ上の演算を施し、第１の離散対数及び第２の離散対数を算出し、算出した第１及び第２の離散対数を用いて、メッセージに対するディジタル署名を生成する署名手段とを備えることを特徴とする。
【発明の効果】
【００１５】
上記に示した構成によると、署名生成装置は、ディジタル署名に用いる値の隠蔽だけでなく、演算そのものを隠蔽することができる。
ここで、前記複数の数の各々は、長さが２以上の所定長からなるビット列で表現される数であり、前記所定長からなるビット列の各ビット値に応じて分解対が対応付けられており、前記選択手段は、選択した前記数ｕを前記所定長のビット列からなるビット表現へと変換し、各ビットそれぞれの値に応じた分解対からなる前記分解組を前記分解値記憶手段から選択するとしてもよい。【００１６】
この構成によると、署名生成装置は、使用する隠蔽された値を容易に選択することができる。
ここで、前記生成手段は、ビット値ごとに選択された分解対からなる前記分解組に含まれる２つ以上の第１の分解値に対して、前記群Ｇにおける基本演算を施して前記第１の冪乗元を生成し、ビット値ごとに選択された分解対からなる前記分解組に含まれ、且つ前記２つ以上の第１の分解値のそれぞれに対応する第２の分解値に対して、前記群Ｇａにおける前記基本演算を施して前記第２の冪乗元を生成するとしてもよい。【００１７】
この構成によると、群Ｇ及び群Ｇａにおける基本演算において、使用する値及び演算を隠匿することができる。
ここで、前記第１の冪乗元は、２つ以上の値を含み、前記署名手段は、前記メッセージに対するハッシュ値を冪とし、前記基本元Ｐａに対して群Ｇａにおける前記冪演算を施すことにより、前記ハッシュ値を前記群Ｇａに属する変換後ハッシュ値へと変換する変換部と、前記第１の冪乗元に含まれる１つの値を用いて、第１のデータを算出する第１演算部と、前記変換後ハッシュ値に、前記群Ｇａ上の基本演算を施し、前記群Ｇａに属する第３の冪乗元を算出する第２演算部と、前記群Ｇａ又は前記群Ｇａに真に含まれる部分群Ｓａにおいて、前記第２の冪乗元及び前記第３の冪乗元それぞれに対して、前記変換部にて行われる変換の冪演算の逆算を施すことにより、第１及び第２の離散対数を求める逆変換部と、前記第１及び前記第２の離散対数を用いて、第２のデータを算出する第３演算部と、前記第１のデータと前記第２のデータとの組からなるディジタル署名を生成するデータ生成部とを含むとしてもよい。【００１８】
この構成によると、署名生成装置は、署名手段において、使用する値及び演算を隠蔽することができる。
ここで、前記署名生成装置は、さらに、秘密鍵を冪として前記基本元Ｐａに対して前記群Ｇａの基本演算を施して、前記群Ｇａに属する変換後秘密鍵を記憶している変換後秘密鍵記憶手段を備え、前記第２演算部は、前記変換後秘密鍵に対して前記第１のデータを冪とする前記群Ｇａの冪演算を施して得られる前記群Ｇａ上の元である演算結果と、前記変換後ハッシュ値とに対して前記群Ｇａ上の基本演算を施して前記第３の冪乗元を算出するとしてもよい。【００１９】
この構成によると、署名生成装置は、第２演算部において、使用する値及び演算を隠蔽することができる。
ここで、前記群Ｇ及び前記群Ｇａは、剰余整数環の乗法群であり、前記群Ｇ及び前記群Ｇａのそれぞれにおける基本演算とは、各元に対して乗算を施す乗法演算であり、前記群Ｇ及び前記群Ｇａのそれぞれにおける冪演算とは、正整数を冪数とする冪乗演算であるとしてもよい。【００２０】
この構成によると、署名生成装置は、第１、第２及び第３の冪乗元の生成に用いられる演算は乗法演算であり、冪乗演算とは異なるので、演算を隠蔽することができる。
ここで、前記群Ｇは、楕円曲線の群であり、前記部分群Ｓａは、アノマラス楕円曲線の群であり、前記群Ｇ及び前記群Ｇａのそれぞれにおける基本演算とは、各元に対して楕円曲線上の加算を施す演算であり、前記群Ｇ及び前記群Ｇａのそれぞれにおける冪演算とは、前記正整数に楕円曲線上の乗算を施す演算であるとしてもよい。また、前記群Ｇは、楕円曲線の群であり、前記群Ｇａは、２つのアノマラス楕円曲線の直積であり、前記群Ｇ及び前記群Ｇａのそれぞれにおける基本演算とは、各元に対して楕円曲線上の加算を施す演算であり、前記群Ｇ及び前記群Ｇａのそれぞれにおける冪演算とは、正整数に楕円曲線上の乗算を施す演算であるとしてもよい。【００２１】
これらの構成によると、署名生成装置は、第１、第２及び第３の冪乗元の生成に用いられる演算は楕円曲線上の加算演算であり、整数の加算演算とは異なるので、演算を隠蔽することができる。
また、本発明は、群Ｇ及び群Ｇａ上の離散対数問題を安全性の根拠として、群Ｇ上の基本元Ｐについて並びに群Ｇａ上の基本元Ｐａについて基本演算を複数回繰り返す冪演算を施すことにより、メッセージに対するディジタル署名を生成する署名生成装置であって、複数の数の各々に分解組が予め対応付けられており、各分解組は複数の分解対を含み、各分解対は第１の分解値と第２の分解値とを含み、各第１の分解値は基本元Ｐについて任意の正整数を冪とする冪演算が施されて算出された群Ｇ上の元であり、各第２の分解値は基本元Ｐａについて当該第２の分解値に対応する第１の分解値において用いられた正整数を冪とする冪演算が施されて算出された群Ｇａ上の元であり、前記署名生成装置は、前記複数の分解組を記憶する分解値記憶手段と、前記複数の数からランダムに数ｕを選択し、選択した数ｕに対応する分解対を前記分解値記憶手段から選択する選択手段と、選択された分解対に含まれる第１の分解値及びメッセージそれぞれを群Ｇａ上の元に変換し、変換された第１の分解対、変換されたメッセージ及び選択された分解対に含まれる第２の分解値に対して前記群Ｇａ上の演算を施し、離散対数問題を解いて第１及び第２の離散対数を算出し、算出した第１及び第２の離散対数を用いて、メッセージに対するディジタル署名を生成する署名手段とを備えることを特徴とする。【００２２】
この構成によると、署名生成装置は、ディジタル署名に使用する値を隠匿することができる。
【図面の簡単な説明】
【００２３】
【図１】署名生成システム１の概要を示すブロック図である。
【図２】署名生成装置１０の構成を示すブロック図である。
【図３】テーブルメモリ部１０２に格納している各テーブルのデータ構造の一例を示す図である。
【図４】署名生成プログラム１１０に含まれる各モジュールを示す図である。
【図５】テーブル生成装置２０の構成を示すブロック図である。
【図６】署名生成処理の動作を示す流れ図である。図７へ続く。
【図７】署名生成処理の動作を示す流れ図である。図６から続く。
【図８】テーブル生成装置２０の動作を示す流れ図である。
【図９】本発明において、値ｒ、ｈから値ｓ（＝（ｒ×ｋｓ＋ｈ）／ｋ  ｍｏｄ  ｑ）を生成する際の動作の概要を示す図である。
【図１０】本発明のＤＳＡ楕円署名方式の特徴部分を示す図である。
【符号の説明】
【００２４】
１    署名生成システム
１０    署名生成装置
２０    テーブル生成装置
３０    メッセージ受付装置
４０    署名データ送信装置
５０    署名データ受信装置
６０    インターネット
１０１    プロセッサ
１０２    テーブルメモリ部
１０３    秘密パラメータメモリ部
１０４    公開パラメータメモリ部
１０５    変換後秘密鍵メモリ部
１０６    プログラムメモリ部
１１０    署名生成プログラム
１２１    ハッシュ値生成モジュール
１２２    乱数生成モジュール
１２３    選択モジュール
１２４    ランダム元生成モジュール
１２５    変換モジュール
１２６    主要演算モジュール
１２７    逆変換モジュール
１２８    乗算モジュール
１２９    除算モジュール
１３０    署名データ生成モジュール
２０１    公開パラメータメモリ部
２０２    乱数生成部
２０３    群演算部
２０４    格納処理部
【発明を実施するための最良の形態】
【００２５】
以下、発明を実施するための最良の実施形態を、図面を参照しながら説明する。
１．第１の実施の形態
１．１  準備
ここでは、本発明にかかる実施の形態を説明する上で、必要となる“楕円曲線上の楕円べき倍演算”について説明する。【００２６】
一例として、１００＊Ｐの計算について説明する。
１００＊Ｐ＝２（２（Ｐ＋２（２（２（Ｐ＋２Ｐ）））））と表すと、１００＊Ｐは、楕円曲線上の点による６回の２倍算と２回の加算により計算される。
このように、楕円べき倍演算は、楕円曲線上の２倍算及び加算による演算に帰着する。
ここで、楕円曲線Ｅの方程式を  ｙ＾２ ＝  ｘ＾３ ＋ａ×ｘ＋ｂ  とし、楕円曲線上の任意の点Ｐの座標を（ｘ１，ｙ１）とし、任意の点Ｑの座標を（ｘ２，ｙ２）とする。ここで、Ｒ＝Ｐ＋Ｑで定まる点Ｒの座標を（ｘ３，ｙ３）とする。【００２７】
Ｐ≠Ｑの場合、Ｒ＝Ｐ＋Ｑは、楕円曲線上の加算の演算となる。加算の公式を以下に示す。
ｘ３ ＝｛（ｙ２ −ｙ１）／（ｘ２ −ｘ１）｝＾２ −ｘ１ −ｘ２ 
ｙ３ ＝｛（ｙ２ −ｙ１ ）／（ｘ２ −ｘ１）｝（ｘ１ −ｘ３）−ｙ１
Ｐ＝Ｑの場合、Ｒ＝Ｐ＋Ｑ＝Ｐ＋Ｐ＝２×Ｐとなり、Ｒ＝Ｐ＋Ｑは、楕円曲線上の２倍算の演算となる。２倍算の公式を以下に示す。【００２８】
ｘ３ ＝｛（３×ｘ１＾２ ＋ａ）／（２×ｙ１） ｝＾２ −（２×ｘ１） 
ｙ３ ＝｛（３×ｘ１＾２ ＋ａ）／（２×ｙ１） ｝（ｘ１ −ｘ３）−ｙ１ 
ここで、上記演算は、楕円曲線が定義される有限体上での演算である。
なお、楕円曲線の演算公式については、“Ｅｆｆｉｃｉｅｎｔ  ｅｌｌｉｐｔｉｃ  ｃｕｒｖｅ  ｅｘｐｏｎｅｎｔｉａｔｉｏｎ”（Ｍｉｙａｊｉ， Ｏｎｏ， ａｎｄ Ｃｏｈｅｎ著，Ａｄｖａｎｃｅｓ  ｉｎ  ｃｒｙｐｔｏｌｏｇｙ−ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ＩＣＩＣＳ‘９７，Ｌｅｃｔｕｒｅ  ｎｏｔｅｓ  ｉｎ  ｃｏｍｐｕｔｅｒ  ｓｃｉｅｎｃｅ，１９９７，Ｓｐｒｉｎｇｅｒ−ｖｅｒｌａｇ，  ２８２−２９０．）に詳しく説明されている。
１．２  署名生成システム１の構成
本発明にかかる実施の形態としての署名生成システム１について説明する。【００２９】
署名生成システム１は、図１にて示すように、署名生成装置１０、テーブル生成装置２０、メッセージ受付装置３０、署名データ送信装置４０、及び署名データ受信装置５０から構成されている。
メッセージ受付装置３０は、ユーザ操作によりメッセージｍを受け付け、受け付けたメッセージｍを署名生成装置１０へ出力する。【００３０】
テーブル生成装置２０は、本発明における楕円ＤＳＡ署名方式（以下、単に「楕円ＤＳＡ署名方式」という。）の署名生成にて使用する複数の元対と、変換後秘密鍵とを生成し、生成した複数の元対と、変換後秘密鍵とを署名生成装置１０へ格納する。ここで、元対とは、第１の楕円曲線上の群の元と、第２の楕円曲線上の群の元との組である。また、変換後秘密鍵とは、秘密鍵に第２の楕円曲線上の楕円べき倍演算を施した演算結果である。【００３１】
なお、元対、変換後秘密鍵の詳細については、後述する。
署名生成装置１０は、メッセージｍをメッセージ受付装置３０から受け付け、受け付けたメッセージｍに対し、楕円ＤＳＡ署名方式の署名生成により署名データＳ（＝（ｒ，ｓ））を生成する。
署名生成装置１０は、生成した署名データＳと、メッセージ受付装置３０から受け付けたメッセージｍを署名データ送信装置４０へ出力する。【００３２】
署名データ送信装置４０は、例えば、インターネット６０により署名データ受信装置５０とネットワーク接続されている。署名データ送信装置４０は、署名生成装置１０からメッセージｍと、メッセージｍに対する署名データＳとを受け取ると、受け取ったメッセージｍ及び署名データＳを、インターネット６０を介して署名データ受信装置５０へ送信する。【００３３】
署名データ受信装置５０は、署名データ送信装置４０からインターネット６０を介して、メッセージｍと、メッセージｍに対する署名データＳとを受信すると、署名検証を行う。
１．３  署名生成装置１０の構成
ここでは、署名生成装置１０の構成について説明する。【００３４】
署名生成装置１０は、図２にて示すように、プロセッサ１０１、テーブルメモリ部１０２、秘密パラメータメモリ部１０３、公開パラメータメモリ部１０４、変換後秘密鍵メモリ部１０５、及びプログラムメモリ部１０６から構成されている。
（１）プロセッサ１０１
プロセッサ１０１は、コンピュータシステムを構成しており、プログラムメモリ部１０６に格納された署名生成プログラム１１０を読み込み、読み込んだ署名生成プログラム１１０とハードウェア資源とが協働することにより機能を達成する。【００３５】
プロセッサ１０１は、プログラムメモリ部１０６に記憶されている署名生成プログラム１１０から１個ずつコンピュータ命令を読み出し、解釈し、その解釈結果に応じて動作する。
なお、署名生成プログラム１１０の詳細については後述する。
（２）テーブルメモリ部１０２
テーブルメモリ部１０２は、第１の群Ｇに属する元と、第２の群Ｇａに属する元の対である元対を複数個記憶している。なお、元対は、テーブル生成装置２０で生成される。【００３６】
（２−１）第１の群Ｇ及び第２の群Ｇａについて
第１の群Ｇは、楕円ＤＳＡ署名方式で使用する楕円曲線Ｅの点を元とする群である。ここで、楕円曲線Ｅの方程式をｙ＾２＝ｘ＾３＋ａ×ｘ＋ｂとする。楕円曲線Ｅの方程式をもつ体ＧＦ（ｐ）上の楕円曲線の点から構成される群をＥ（ＧＦ（ｐ））とするとき、第１の群Ｇは、Ｅ（ＧＦ（ｐ））となる。【００３７】
第２の群Ｇａは、ｎ＝ｐ１×ｐ２（ｐ１、ｐ２は素数）に対し、ＧＦ（ｐ１）上の楕円曲線Ｅａの点から構成される群Ｅａ（ＧＦ（ｐ１））と、ＧＦ（ｐ２）上の楕円曲線Ｅａの点から構成される群Ｅａ（ＧＦ（ｐ２））の直積Ｅａ（ＧＦ（ｐ１））×Ｅａ（ＧＦ（ｐ２））とする。Ｚ／ｎＺは体ではなく、環であるため、数学的には「Ｚ／ｎＺ上の楕円曲線」とはよべないが、ここでは便宜上、その直積をＺ／ｎＺ上の楕円曲線の群とよぶ。なお、Ｚは整数環であり、Ｚ／ｎＺは、数ｎを法とする剰余整数環である。【００３８】
ここで、楕円曲線Ｅａの方程式をｙ＾２＝ｘ＾３＋ａａ×ｘ＋ｂａとする。また、素数ｐ１及びｐ２は、楕円曲線Ｅのベース点の位数ｑとは異なる数であり、第三者が知ることができないように生成及び管理がなされているものとする。
Ｅａ（ＧＦ（ｐ１））上の点Ｐａ１＝（ｘａ１，ｙａ１）  ｍｏｄ  ｐ１と、Ｅａ（ＧＦ（ｐ２））上の点Ｐａ２＝（ｘａ２，ｙａ２）  ｍｏｄ  ｐ２に対応するＺ／ｎＺ上の楕円曲線Ｅａ（ＧＦ（ｐ１））×Ｅａ（ＧＦ（ｐ２））の点Ｐａ＝（ｘａ，ｙａ）  ｍｏｄ  ｎは、以下のように定義する。ｘａをｘａ  ｍｏｄ  ｐ１＝ｘａ１，ｘａ  ｍｏｄ  ｐ２＝ｘａ２を満たす数、ｙａをｙａ  ｍｏｄ  ｐ１＝ｙａ１，ｙａ  ｍｏｄ  ｐ２＝ｙａ２を満たす数とする。【００３９】
この定義より、Ｅａ（ＧＦ（ｐ１））×Ｅａ（ＧＦ（ｐ２））上の点Ｐａ＝（ｘａ，ｙａ）  ｍｏｄ  ｎに対応するＥａ（ＧＦ（ｐ１））上の点Ｐａ１をＰａ１＝（ｘａ１，ｙａ１）  ｍｏｄ  ｐ１とし、Ｅａ（ＧＦ（ｐ２））上の点Ｐａ２をＰａ２＝（ｘａ２，ｙａ２）  ｍｏｄ  ｐ２とすることで、Ｅａ（ＧＦ（ｐ１）），Ｅａ（ＧＦ（ｐ２））をＥａ（ＧＦ（ｐ１））×Ｅａ（ＧＦ（ｐ２））の部分群とみなす。【００４０】
楕円曲線Ｅａはｍｏｄ  ｐ１での楕円曲線の位数、すなわち、点の個数がｐ１であるとする。このような体ＧＦ（ｐ１）上の楕円曲線をアノマラス（Ａｎｏｍａｌｏｕｓ）楕円曲線とよぶ。さらに、ｍｏｄ  ｐ２での楕円曲線の位数がｐ２である、すなわち、ＧＦ（ｐ２）上でもアノマラス楕円曲線であるとする。このとき、Ｚ／ｎＺ上の楕円曲線は、スーパーアノマラス（Ｓｕｐｅｒ−Ａｎｏｍａｌｏｕｓ）楕円曲線とよぶ。スーパーアノマラス楕円曲線については非特許文献４が詳しい。このとき、Ｚ／ｎＺ上の楕円曲線の群はＥａ（ＧＦ（ｐ１））×Ｅａ（ＧＦ（ｐ２））であるので、楕円曲線の位数はｎ（＝ｐ１×ｐ２）となる。【００４１】
素数ｐ１のビット数を２×ｌｅｎ＋１ビットとする。なお、ｐ１のビット数は２×ｌｅｎ＋１より大きくてもよい。ｌｅｎは例えば、１６０である。ｐ２は、例えば、ｎ＝ｐ１×ｐ２のビット数が１０２４となるような大きさの素数である。
（２−２）テーブルメモリ部１０２に格納する元対について
テーブルメモリ部１０２は、２×ｌｅｎ個の元対ＰＰ＿（ｉ，ｊ）を格納する。ここで、ｉは０または１、ｊは０からｌｅｎ−１の値のいずれかであり、「＿」は下付き文字を示し、ｉ，ｊはＰＰのインデックスである。ＰＰ＿（ｉ，ｊ）＝（ｖ＿（ｉ，ｊ）＊Ｐ  ｍｏｄ  ｐ，ｖ＿（ｉ，ｊ）＊Ｐａ  ｍｏｄ  ｎ）である。＊は、Ｐに対しては、楕円曲線Ｅ上のスカラ倍演算、Ｐａに対しては、楕円曲線Ｅａ上のスカラ倍演算を示す。ｖ＿（ｉ，ｊ）は、ｌｅｎビットの値である。ここで、ＰＰ＿（ｉ，ｊ）に含まれる２点のスカラは等しいことに注意する。【００４２】
ここで、元対の格納方法の一例を以下に示す。
テーブルメモリ部１０２は、複数の元対を格納するための領域を有している。
テーブルメモリ部１０２は、図３にて示すように、テーブルＴ１０１、Ｔ１０２、・・・、Ｔ１０３を格納している。つまり、テーブルメモリ部１０２は、ｌｅｎ個のテーブルを有している。【００４３】
テーブルＴ１０１は、テーブル名称Ｔ１１０（ここでは、「テーブル０」）と、２値項目Ｔ１２０、Ｔ１２１（ここでは、「０」、「１」）と各２値項目Ｔ１２０、Ｔ１２１における元対Ｔ１３０、Ｔ１３１とから構成されている。１つのテーブルにおいて、２つの元対が格納されているので、テーブルメモリ部１０２は、テーブルをｌｅｎ個格納することにより、２×ｌｅｎ個の元対を格納することになる。【００４４】
テーブル名称Ｔ１１０は、値ｊと対応付けがされている。つまり、テーブル名称Ｔ１１０（テーブル０）は、ｊ＝０と対応付けされており、テーブル名称Ｔ１１１（ここではテーブル１）は、ｊ＝１と対応付けされている。これにより、ｊ＝０、・・・、ｌｅｎ−１のそれぞれに対してテーブル名称が対応付けされている。
また、元対Ｔ１３０において、Ｐ＿（０，０）は、ｖ＿（０，０）＊Ｐ  ｍｏｄ  ｐであり、Ｐａ＿（０，０）は、ｖ＿（０，０）＊Ｐａ  ｍｏｄ  ｎである。元対Ｔ１３０において、Ｐ＿（１，０）は、ｖ＿（１，０）＊Ｐ  ｍｏｄ  ｐであり、Ｐａ＿（１，０）は、ｖ＿（１，０）＊Ｐａ  ｍｏｄ  ｎである。ＰＰ＿（ｉ，ｊ）＝（Ｐ＿（ｉ，ｊ），Ｐａ＿（ｉ，ｊ））であることに注意する。【００４５】
元対のそれぞれは、２進数と対応付けがされている。具体的には、２進数の値が０である場合には、２値項目「０」における元対が対応付けされ、２進数の値が１である場合には、２値項目「１」における元対が対応付けされている。
（３）秘密パラメータメモリ部１０３
秘密パラメータメモリ部１０３は、耐タンパ性を有しており、素数ｐ１を記憶している。【００４６】
（４）公開パラメータメモリ部１０４
公開パラメータメモリ部１０４は、楕円曲線Ｅの方程式ｙ＾２＝ｘ＾３＋ａ×ｘ＋ｂにおける変数ａ、ｂ、素数ｐ、楕円曲線Ｅ上のベース点Ｐ、及びその位数ｑと、楕円曲線Ｅａの方程式ｙ＾２＝ｘ＾３＋ａａ×ｘ＋ｂａにおける変数ａａ、ｂａ、合成数ｎ（＝ｐ１×ｐ２）、及び楕円曲線Ｅａ上の点Ｐａをそれぞれパラメータとして記憶している。ここで、点を記憶するとは、点の座標を記憶することを意味する。また、ｐ、ｑはｌｅｎビットの素数とする。【００４７】
（５）変換後秘密鍵メモリ部１０５
変換後秘密鍵メモリ部１０５は、秘密鍵ｋｓに第２の楕円曲線Ｅａ上の楕円べき倍演算を施すことにより、秘密鍵ｋｓを変換した変換後秘密鍵ＫＳＴ（＝ｋｓ＊Ｐａ）を格納している。変換後秘密鍵ＫＳＴは、テーブル生成装置２０で生成される。
（６）プログラムメモリ部１０６
プログラムメモリ部１０６は、署名生成プログラム１１０を記憶している。【００４８】
署名生成プログラム１１０は、図４にて示すように、ハッシュ値生成モジュール１２１、乱数生成モジュール１２２、選択モジュール１２３、ランダム元生成モジュール１２４、変換モジュール１２５、主要演算モジュール１２６、逆変換モジュール１２７、乗算モジュール１２８、除算モジュール１２９、及び署名データ生成モジュール１３０から構成されている。【００４９】
本プログラムは、入力であるメッセージｍに対し、ｍの署名データＳ（＝（ｒ，ｓ））を出力するものである。
各モジュールは、機械語形式の複数の命令コードを組み合わせて構成されるコンピュータプログラムである。前記機械語形式は、プロセッサ１０１により解読され実行される形式である。【００５０】
（６−１）ハッシュ値生成モジュール１２１
ハッシュ値生成モジュール１２１は、入力であるメッセージｍを、メッセージ受付装置３０から受け付け、受け付けたメッセージｍにハッシュ関数を施して、メッセージｍのハッシュ値ｈを計算する。ハッシュ関数は、例えば、ＳＨＡ−１である。
ハッシュ値生成モジュール１２１は、ハッシュ値ｈを変換モジュール１２５へ出力する。【００５１】
（６−２）乱数生成モジュール１２２
乱数生成モジュール１２２は、ｌｅｎビットのランダムな正整数（乱数）ｕを生成し、生成した乱数ｕを選択モジュール１２３へ出力する。
（６−３）選択モジュール１２３
選択モジュール１２３は、乱数生成モジュール１２２から乱数ｕを受け取り、受け取った乱数ｕをビット表現に変換する。【００５２】
選択モジュール１２３は、ビット表現に変換された乱数ｕ＝ｕ＿０＋ｕ＿１×２＋ｕ＿２×２＾２＋…＋ｕ＿（ｌｅｎ−１）×２＾（ｌｅｎ−１）に対し、テーブルメモリ部１０２からＰＰ＿（ｕ＿０，０），ＰＰ＿（ｕ＿１，１），ＰＰ＿（ｕ＿２，２），…，ＰＰ＿（ｕ＿（ｌｅｎ−１），ｌｅｎ−１）を選択する（ここで、ｉ＝０，１，２，…，ｌｅｎ−１に対しｕ＿ｉ＝０または１）。【００５３】
ここでは、ｕ＿ｋにおける添え字ｋ（ｋ＝０，１，・・・，ｌｅｎ―１）の値がテーブルメモリ部１０２に格納されているテーブルのテーブル名称と対応付けされている。つまり、ｕ＿０はテーブル０と、ｕ＿１はテーブル１と、・・・、ｕ＿ｌｅｎ−１はテーブルｌｅｎ−１と対応付けがされている。
選択モジュール１２３は、選択したＰＰ＿（ｕ＿０，０），ＰＰ＿（ｕ＿１，１），ＰＰ＿（ｕ＿２，２），…，ＰＰ＿（ｕ＿（ｌｅｎ−１），ｌｅｎ−１）をランダム元生成モジュール１２４へ出力する。【００５４】
（６−４）ランダム元生成モジュール１２４
ランダム元生成モジュール１２４は、選択モジュール１２３からｌｅｎ個の元対ＰＰ＿（ｕ＿ｉ，ｉ）＝（Ｐ＿（ｕ＿ｉ，ｉ），Ｐａ＿（ｕ＿ｉ，ｉ））を受け取り、受け取った元対それぞれに含まれるＰ＿（ｕ＿ｉ，ｉ）を公開パラメータメモリ部１０４で記憶している楕円曲線Ｅのパラメータａ、ｂ、素数ｐ、楕円曲線Ｅ上のベース点Ｐを用いて、楕円曲線Ｅ上で加算することにより、Ｐｋ（＝（ｖ＿（ｕ＿０，０）＊Ｐ＋ｖ＿（ｕ＿１，１）＊Ｐ＋・・・＋ｖ＿（ｕ＿ｌｅｎ−１，ｌｅｎ−１）＊Ｐ）を算出する（ここで、ｉ＝０，１，２，…，ｌｅｎ−１）。なお、Ｐｋ＝（ｖ＿（ｕ＿０，０）＋ｖ＿（ｕ＿１，１）＋・・・＋ｖ＿（ｕ＿（ｌｅｎ−１），ｌｅｎ−１））＊Ｐであることに注意する。【００５５】
ランダム元生成モジュール１２４は、公開パラメータメモリ部１０４で記憶している楕円曲線Ｅａのパラメータａａ、ｂａ、合成数ｎを用いて、Ｐａ＿（ｕ＿ｉ，ｉ）  ｍｏｄ  ｎ（ｉ＝０，１，２，…，ｌｅｎ−１）を楕円曲線Ｅａ上で加算してＰａｋ  ｍｏｄ  ｎ（＝（ｖ＿（ｕ＿０，０）＊Ｐａ＋ｖ＿（ｕ＿１，１）＊Ｐａ＋・・・＋ｖ＿（ｕ＿ｌｅｎ−１，ｌｅｎ−１）＊Ｐａ））とする。ここで、Ｐａｋ＝（ｖ＿（ｕ＿０，０）＋ｖ＿（ｕ＿１，１）＋・・・＋ｖ＿（ｕ＿（ｌｅｎ−１），ｌｅｎ−１））＊Ｐａであることに注意する。【００５６】
ランダム元生成モジュール１２４は、算出したＰｋを主要演算モジュール１２６へ出力し、算出したＰａｋを逆変換モジュール１２７へ出力する。
（６−５）変換モジュール１２５
変換モジュール１２５は、ハッシュ値生成モジュール１２１からハッシュ値ｈを受け取ると、公開パラメータメモリ部１０４で記憶している楕円曲線Ｅａのパラメータａａ、ｂａ、合成数ｎと楕円曲線Ｅａ上の点Ｐａと、受け取ったハッシュ値ｈとを用いて、ｈＰａ＝ｈ＊Ｐａ  ｍｏｄ  ｎを計算する。【００５７】
変換モジュール１２５は、算出したｈＰａを主要演算モジュール１２６へ出力する。
（６−６）主要演算モジュール１２６
主要演算モジュール１２６は、ランダム元生成モジュール１２４からＰｋを受け取り、変換モジュール１２５からｈＰａを受け取る。
主要演算モジュール１２６は、ｒ＝ｘ（Ｐｋ）  ｍｏｄ  ｑを計算する。ここで、ｘ（Ｐｋ）は、Ｐｋのｘ座標を示す。【００５８】
主要演算モジュール１２６は、変換後秘密鍵メモリ部１０５で記憶している変換後秘密鍵ＫＳＴと、公開パラメータメモリ部１０４で記憶している楕円曲線Ｅａのパラメータａａ、ｂｂ、合成数ｎを用いて、楕円曲線Ｅａ上でｒ＊ＫＳＴを計算し、ｈＰａと楕円曲線Ｅａ上の加算を行い、Ｑａ＝ｒ＊ＫＳＴ＋ｈＰａとする。
主要演算モジュール１２６は、算出したｒを署名データ生成モジュール１３０へ出力し、算出したＱａを逆変換モジュール１２７へ出力する。【００５９】
（６−７）逆変換モジュール１２７
逆変換モジュール１２７は、ランダム元生成モジュール１２４からＰａｋを受け取り、主要演算モジュール１２６からＱａを受け取る。
逆変換モジュール１２７は、秘密パラメータメモリ部１０３で記憶している素数ｐ１を用いて、Ｐａ  ｍｏｄ  ｐ１に対するＱａの離散対数ｃＱと、Ｐａ  ｍｏｄ  ｐ１に対するＰａｋの離散対数ｃｋを計算する。【００６０】
逆変換モジュール１２７は、算出した離散対数ｃＱ、ｃｋを乗算モジュール１２８へ出力する。
まず、Ｑａの離散対数ｃＱを求める際の処理を示す。
（ステップＳ２０）  Ｑａ１＝Ｑａ  ｍｏｄ  ｐ１，Ｐａ１＝Ｐａ  ｍｏｄ  ｐ１を計算。【００６１】
（ステップＳ２１）  Ｐａ１に対するＱａ１の離散対数ｃＱ（すなわち、Ｑａ１＝ｃＱ＊Ｐａ１を満たすｃＱ）を計算する。
次に、Ｐａｋの離散対数ｃｋを求める際の処理を示す。
（ステップＳ３０）  ｃｋ１＝Ｐａｋ  ｍｏｄ  ｐ１，Ｐａ１＝Ｐａ  ｍｏｄ  ｐ１を計算。【００６２】
（ステップＳ３１）  Ｐａ１に対するｃｋ１の離散対数ｃｋ（すなわち、ｃｋ１＝ｃｋ＊Ｐａ１を満たすｃｋ）を計算する。
ここで、ステップＳ２１及びＳ３１で計算している離散対数ｃＱ及びｃｋは、アノマラス楕円曲線上の離散対数問題の解である。
アノマラス楕円曲線上の離散対数問題を解く方法は、非特許文献３の８８〜９１ページが詳しい。計算方法はこの文献に記載されているため、ここでは説明を省略する。【００６３】
なお、逆変換モジュール１２７は、処理内容の解析を困難にするために、ハード対策やソフトウェア対策により耐タンパ性を有する領域で実行されるものとする。
（６−８）乗算モジュール１２８
乗算モジュール１２８は、逆変換モジュール１２７から離散対数ｃＱ、ｃｋを受け取ると、乱数βを生成する。【００６４】
乗算モジュール１２８は、公開パラメータメモリ部１０４で記憶している楕円曲線Ｅ上のベース点Ｐの位数ｑを用いて、離散対数ｃＱ及びｃｋに対し生成したβを乗じ、ｃＱ’＝ｃＱ×β  ｍｏｄ  ｑ，  ｃｋ’＝ｃｋ×β  ｍｏｄ  ｑを計算する。
乗算モジュール１２８は、算出したｃＱ’、ｃｋ’を除算モジュール１２９へ出力する。【００６５】
なお、乗算モジュール１２８は、処理内容の解析を困難にするために、ハード対策やソフトウェア対策により耐タンパ性を有する領域で実行されるものとする。
（６−９）除算モジュール１２９
除算モジュール１２９は、乗算モジュール１２８からｃＱ’、ｃｋ’を受け取る。
除算モジュール１２９は、ｃｋ’のｍｏｄ  ｑでの逆元であるｃｋｉを計算する。ここで、ｃｋｉ×ｃｋ’＝１  ｍｏｄ  ｑを満たす。【００６６】
除算モジュール１２９は、ｃｋｉとｃＱ’を乗じｍｏｄ  ｑをして、ｓ＝ｃｋｉ×ｃＱ’  ｍｏｄ  ｑを求める。逆元の計算については、非特許文献２が詳しい。
除算モジュール１２９は、算出したｓを署名データ生成モジュール１３０へ出力する。
（６−１０）署名データ生成モジュール１３０
署名データ生成モジュール１３０は、主要演算モジュール１２６からｒを受け取り、除算モジュール１２９からｓを受け取る。【００６７】
署名データ生成モジュール１３０は、主要演算モジュール１２６から受け取ったｒと、除算モジュール１２９から受け取ったｓを１対として、署名データＳ＝（ｒ，ｓ）を生成する。
署名データ生成モジュール１３０は、ハッシュ値生成モジュール１２１が受け付けたメッセージｍと、生成した署名データＳを署名データ送信装置４０へ出力する。
１．４  テーブル生成装置２０の構成
ここでは、テーブル生成装置２０の構成について説明する。【００６８】
テーブル生成装置２０は、図５にて示すように、公開パラメータメモリ部２０１、乱数生成部２０２、群演算部２０３、及び格納処理部２０４から構成されている。
（１）公開パラメータメモリ部２０１
公開パラメータメモリ部２０１は、楕円曲線Ｅの方程式ｙ＾２＝ｘ＾３＋ａ×ｘ＋ｂの変数ａ、ｂ、素数ｐ、楕円曲線Ｅ上のベース点Ｐ、その位数ｑ、楕円曲線Ｅａの方程式ｙ＾２＝ｘ＾３＋ａａ×ｘ＋ｂａのａａ、ｂａ、合成数ｎ、楕円曲線Ｅａ上の点Ｐａのそれぞれをパラメータとして記憶している。ここで、点を記憶するとは、点の座標を記憶することを意味する。【００６９】
（２）乱数生成部２０２
乱数生成部２０２は、乱数生成部２０２は、２×ｌｅｎ個のｌｅｎビットの乱数ｖ＿（ｉ，ｊ）  （ｉ＝０または１、ｊ＝０，１，…，ｌｅｎ−１）を生成する。
乱数生成部２０２は、１個のｌｅｎビットの乱数ｋｓを生成する（ただし、０＜ｋｓ＜ｑ）。【００７０】
なお、乱数生成部２０２が生成した乱数ｋｓが秘密鍵となることに注意する。
（３）群演算部２０３
群演算部２０３は、公開パラメータメモリ部２０１に記憶している楕円曲線Ｅのパラメータａ、ｂ、素数ｐ、ベース点Ｐを用いて、乱数ｖ＿（ｉ，ｊ）  （ｉ＝０または１、ｊ＝０，１，…，ｌｅｎ−１）に対応するスカラ倍点ｖ＿（ｉ，ｊ）＊Ｐを計算する。【００７１】
群演算部２０３は、公開パラメータメモリ部２０１に記憶している楕円曲線Ｅａのパラメータａａ、ｂｂ、合成数ｎ、楕円曲線Ｅａ上の点Ｐａを用いて、乱数ｖ＿（ｉ，ｊ）  （ｉ＝０または１、ｊ＝０，１，…，ｌｅｎ−１）に対応するスカラ倍点ｖ＿（ｉ，ｊ）＊Ｐａを計算する。
群演算部２０３は、生成した各スカラ倍点ｖ＿（ｉ，ｊ）＊Ｐと、スカラ倍点ｖ＿（ｉ，ｊ）＊Ｐａとを用いて、図３にて示すテーブルＴ１０１、Ｔ１０２、・・・、Ｔ１０３を生成する。これにより、群演算部２０３は、２×ｌｅｎ個の元対を生成することになる。【００７２】
群演算部２０３は、公開パラメータメモリ部２０１に記憶している楕円曲線Ｅａのパラメータａａ、ｂｂ、合成数ｎ、楕円曲線Ｅａ上の点Ｐａを用いて、乱数ｋｓに対するスカラ倍点ＫＳＴ＝ｋｓ＊Ｐａを計算する。
なお、算出されたスカラ倍点ＫＳＴが変換後秘密鍵となることに注意する。
（４）格納処理部２０４
格納処理部２０４は、群演算部２０３にて生成されたテーブルＴ１０１、Ｔ１０２、・・・、Ｔ１０３を署名生成装置１０のテーブルメモリ部１０２に格納する。これにより、格納処理部２０４は、元対（ｖ＿（ｉ，ｊ）＊Ｐ，  ｖ＿（ｉ，ｊ）＊Ｐａ）  （ｉ＝０または１、ｊ＝０，１，…，ｌｅｎ−１）を署名生成装置１０のテーブルメモリ部１０２に格納することができる。【００７３】
格納処理部２０４は、群演算部２０３にて算出されたＫＳＴ（＝ｋｓ＊Ｐａ）を署名生成装置１０の変換後秘密鍵メモリ部１０５に格納する。
１．５  署名生成装置１０の動作
ここでは、署名生成装置１０にて行われる署名データの生成の動作について説明する。なお、テーブルメモリ部１０２には予めｌｅｎ−１個のテーブルＴ１０１、Ｔ１０２、・・・、Ｔ１０３がテーブル生成装置２０により格納され、変換後秘密鍵メモリ部１０５には予め変換後秘密鍵ＫＳＴがテーブル生成装置２０により格納されているものとする。【００７４】
（１）動作概要
署名生成装置１０は、プロセッサ１０１により、プログラムメモリ部１０６に記憶している署名生成プログラム１１０から１個ずつコンピュータ命令を読み出し、解釈し、その解釈結果に応じて、テーブルメモリ部１０２、秘密パラメータメモリ部１０３、公開パラメータメモリ部１０４及び変換後秘密鍵メモリ部１０５を読み出しながら、メッセージｍに対する署名データＳを生成する。署名データＳの生成処理の具体的な動作については、後述する。【００７５】
（２）署名生成処理の動作
ここでは、署名データＳを生成する署名生成処理の動作について図６及び図７にて示す流れ図を用いて説明する。
ハッシュ値生成モジュール１２１は、入力であるメッセージｍをメッセージ受付装置３０から受け付け（ステップＳ１００）、受け付けたメッセージｍのハッシュ値ｈを計算する（ステップＳ１０５）。【００７６】
乱数生成モジュール１２２は、ｌｅｎビットの正整数（乱数）ｕを生成する（ステップＳ１１０）。
選択モジュール１２３は、乱数ｕのビット表現（ｕ＝ｕ＿０＋ｕ＿１×２＋ｕ＿２×２＾２＋…＋ｕ＿（ｌｅｎ−１）×２＾（ｌｅｎ−１）  （ｉ＝０，１，２，…，ｌｅｎ−１に対しｕ＿ｉ＝０または１））に基づいて、テーブルメモリ部１０２に記憶している元対ＰＰ＿（ｕ＿０，０），ＰＰ＿（ｕ＿１，１），ＰＰ＿（ｕ＿２，２），…，ＰＰ＿（ｕ＿（ｌｅｎ−１），ｌｅｎ−１）を選択する（ステップＳ１１５）。【００７７】
ランダム元生成モジュール１２４は、選択モジュール１２３で選択したＰＰ＿（ｕ＿ｉ，ｉ）＝（Ｐ＿（ｕ＿ｉ，ｉ），Ｐａ＿（ｕ＿ｉ，ｉ））（ｉ＝０，１，２，…，ｌｅｎ−１）に対し、Ｐ＿（ｕ＿ｉ，ｉ）  （ｉ＝０，１，２，…，ｌｅｎ−１）を公開パラメータメモリ部１０４で記憶している楕円曲線Ｅのパラメータａ、ｂ、素数ｐ、楕円曲線Ｅ上のベース点Ｐを用いて、楕円曲線Ｅ上で加算することにより、Ｐｋ（＝（ｖ＿（ｕ＿０，０）＊Ｐ＋ｖ＿（ｕ＿１，１）＊Ｐ＋・・・＋ｖ＿（ｕ＿ｌｅｎ−１，ｌｅｎ−１）＊Ｐ）を算出する（ステップＳ１２０）。【００７８】
ランダム元生成モジュール１２４は、公開パラメータメモリ部１０４で記憶している楕円曲線Ｅａのパラメータａａ、ｂａ、合成数ｎを用いて、Ｐａ＿（ｕ＿ｉ，ｉ）  ｍｏｄ  ｎ（ｉ＝１，２，…，ｌｅｎ−１）を楕円曲線Ｅａ上で加算することにより、Ｐａｋ（＝（ｖ＿（ｕ＿０，０）＊Ｐａ＋ｖ＿（ｕ＿１，１）＊Ｐａ＋・・・＋ｖ＿（ｕ＿ｌｅｎ−１，ｌｅｎ−１）＊Ｐａ）を計算する（ステップＳ１２５）。【００７９】
変換モジュール１２５は、公開パラメータメモリ部１０４で記憶している楕円曲線Ｅａのパラメータａａ、ｂａ、合成数ｎと楕円曲線Ｅａ上の点Ｐａとハッシュ値ｈとを用いて、ｈＰａ＝ｈ＊Ｐａ  ｍｏｄ  ｎを計算する（ステップＳ１３０）。
主要演算モジュール１２６は、ｒ＝ｘ（Ｐｋ）  ｍｏｄ  ｑを計算する（ステップＳ１３５）。ここで、ｘ（Ｐｋ）は、Ｐｋのｘ座標を示す。【００８０】
主要演算モジュール１２６は、変換後秘密鍵メモリ部１０５で記憶している変換後秘密鍵ＫＳＴと、公開パラメータメモリ部１０４で記憶している楕円曲線Ｅａのパラメータａａ、ｂｂ、合成数ｎを用いて、楕円曲線Ｅａ上でｒ＊ＫＳＴを計算する（ステップＳ１４０）。
主要演算モジュール１２６は、ｈＰａと楕円曲線Ｅａ上の加算を行うことにより、Ｑａ＝ｒ＊ＫＳＴ＋ｈＰａを計算する（ステップＳ１４５）。【００８１】
逆変換モジュール１２７は、秘密パラメータメモリ部１０３で記憶している素数ｐ１を用いて、Ｐａ  ｍｏｄ  ｐ１に対するＱａの離散対数ｃＱを算出する（ステップＳ１５０）。
逆変換モジュール１２７は、秘密パラメータメモリ部１０３で記憶している素数ｐ１を用いて、Ｐａ  ｍｏｄ  ｐ１に対するＰａｋの離散対数ｃｋを算出する（ステップＳ１５５）。【００８２】
乗算モジュール１２８は、乱数βを生成する（ステップＳ１６０）。
乗算モジュール１２８は、公開パラメータメモリ部１０４で記憶している楕円曲線Ｅ上のベース点Ｐの位数ｑと、ステップＳ１５０にて算出された離散対数ｃＱと、乱数βとを用いて、ｃＱ’＝ｃＱ×β  ｍｏｄ  ｑを計算する（ステップＳ１６５）。
乗算モジュール１２８は、公開パラメータメモリ部１０４で記憶している楕円曲線Ｅ上のベース点Ｐの位数ｑと、ステップＳ１５５にて算出された離散対数ｃｋと、乱数βとを用いて、ｃｋ’＝ｃｋ×β  ｍｏｄ  ｑを計算する（ステップＳ１７０）。【００８３】
除算モジュール１２９は、ステップＳ１７０にて算出されたｃｋ’のｍｏｄ  ｑでの逆元であるｃｋｉを計算する（ステップＳ１７５）。ここで、ｃｋｉは、ｃｋｉ×ｃｋ’＝１  ｍｏｄ  ｑを満たす値である。
除算モジュール１２９は、公開パラメータメモリ部１０４で記憶している楕円曲線Ｅ上のベース点Ｐの位数ｑと、ステップＳ１７５にて算出されたｃｋｉと、ステップＳ１６５にて算出されたｃＱ’とを用いて、ｓ＝ｃｋｉ×ｃＱ’  ｍｏｄ  ｑを算出する（ステップＳ１８０）。【００８４】
署名データ生成モジュール１３０は、ステップＳ１３５にて生成されたｒと、ステップＳ１８０にて生成されたｓを１対とする署名データＳ＝（ｒ，ｓ）を生成する（ステップＳ１８５）。
署名データ生成モジュール１３０は、ハッシュ値生成モジュール１２１が受け付けたメッセージｍと、生成した署名データＳを署名データ送信装置４０へ出力する。
１．６  テーブル生成装置２０の動作
ここでは、テーブル生成装置２０にて行われるテーブル及び変換後秘密鍵の生成の動作について図８にて示す流れ図を用いて説明する。【００８５】
乱数生成部２０２は、ｌｅｎビットの乱数ｖ＿（ｉ，ｊ）  （ｉ＝０，１、ｊ＝０，１，…，ｌｅｎ−１）を２×ｌｅｎ個生成する（ステップＳ２００）。
乱数生成部２０２は、１個のｌｅｎビットの乱数（秘密鍵）ｋｓを生成する（ステップＳ２０５）。ただし、ｋｓは、０＜ｋｓ＜ｑを満たす数である。
群演算部２０３は、公開パラメータメモリ部２０１に記憶している楕円曲線Ｅのパラメータａ、ｂ、素数ｐ、ベース点Ｐを用いて、乱数ｖ＿（ｉ，ｊ）  （ｉ＝０，１、ｊ＝０，１，…，ｌｅｎ−１）に対応するスカラ倍点ｖ＿（ｉ，ｊ）＊Ｐを計算する（ステップＳ２１０）。【００８６】
群演算部２０３は、公開パラメータメモリ部２０１に記憶している楕円曲線Ｅａのパラメータａａ、ｂｂ、合成数ｎ、楕円曲線Ｅａ上の点Ｐａを用いて、乱数ｖ＿（ｉ，ｊ）  （ｉ＝０，１、ｊ＝０，１，…，ｌｅｎ−１）に対応するスカラ倍点ｖ＿（ｉ，ｊ）＊Ｐａを計算する（ステップＳ２１５）。
群演算部２０３は、生成した各スカラ倍点ｖ＿（ｉ，ｊ）＊Ｐと、スカラ倍点ｖ＿（ｉ，ｊ）＊Ｐａとを用いて、ｌｅｎ個のテーブルＴ１０１、Ｔ１０２、・・・、Ｔ１０３を生成する（ステップＳ２２０）。【００８７】
群演算部２０３は、公開パラメータメモリ部２０１に記憶している楕円曲線Ｅａのパラメータａａ、ｂｂ、合成数ｎ、楕円曲線Ｅａ上の点Ｐａを用いて、乱数ｋｓに対するスカラ倍点（変換後秘密鍵）ＫＳＴ＝ｋｓ＊Ｐａを計算する（ステップＳ２２５）。
格納処理部２０４は、ステップＳ２２０にて生成されたテーブルＴ１０１、Ｔ１０２、・・・、Ｔ１０３を署名生成装置１０のテーブルメモリ部１０２に格納し、ステップＳ２２５にて算出されたＫＳＴ（＝ｋｓ＊Ｐａ）を署名生成装置１０の変換後秘密鍵メモリ部１０５に格納する（ステップＳ２３０）。【００８８】
これにより、格納処理部２０４は、元対（ｖ＿（ｉ，ｊ）＊Ｐ，  ｖ＿（ｉ，ｊ）＊Ｐａ）  （ｉ＝０または１、ｊ＝０，１，…，ｌｅｎ−１）を署名生成装置１０のテーブルメモリ部１０２に格納することができる。
１．７  実施の形態の動作検証
ここでは、上記実施の形態における署名生成プログラム１１０が、従来型の楕円ＤＳＡ署名方式の署名生成にて生成される署名と同一の署名を生成することを以下に示す。【００８９】
署名生成プログラム１１０では、ランダム元生成モジュール１２４において、ランダムな点Ｐｋを計算している。さらに署名生成プログラム１１０では、ランダム元生成モジュール１２４において、スーパーアノマラス楕円曲線ＥａにおけるＰａｋを計算している。
ここで、テーブルメモリ部１０２の元対に含まれる楕円曲線Ｅ上の点とスーパーアノマラス楕円曲線Ｅａ上の点はそれぞれ、点Ｐ、点Ｐａに対する離散対数が同じ値となっている。すなわち、選択モジュール１２３で元対を選択し、ランダム元生成モジュール１２４では選択した元対に含まれる点をそれぞれの楕円曲線Ｅ、Ｅａ上で加算するため、Ｐに対するＰｋの離散対数と、Ｐａに対するＰａｋの離散対数は同じ値（ここでは、ｖ＿（ｕ＿０，０）＋ｖ＿（ｕ＿１，１）＋・・・＋ｖ＿（ｕ＿ｌｅｎ−１，ｌｅｎ−１）である。）となる。この離散対数を従来型の楕円ＤＳＡ署名方式のステップＳ２にて生成される乱数ｋとみなすことで、署名生成プログラム１１０が生成するＳ＝（ｒ，ｓ）は、従来型の楕円ＤＳＡ署名方式の署名生成にて生成される署名Ｓと同じとなる。【００９０】
以下、署名生成プログラム１１０が生成するＳ＝（ｒ，ｓ）と、従来型の楕円ＤＳＡ署名方式の署名生成にて生成される署名Ｓとが同一となることを示す。
点Ｐａに対する点Ｑａの離散対数ｃＱについて考える。上述したように、Ｑａ＝ｒ＊ＫＳＴ＋ｈＰａであり、ＫＳＴ＝ｋｓ＊Ｐａ，ｈＰａ＝ｈ＊Ｐａである。これにより、Qa＝（ｒ×ｋｓ＋ｈ）＊Paとなることが分かる。したがって、点Ｐａに対する点Ｑａの離散対数はｃＱは、ｃＱ＝ｒ×ｋｓ＋ｈとなる。また、点Ｐａに対する点Ｐａｋの離散対数はｃｋは、ｃｋ＝ｋとなる。【００９１】
以下、この理由を示す。
上記にて示すステップＳ３０によりｃｋ１＝Pak  ｍｏｄ  ｐ１，Ｐａ１＝Ｐａ  ｍｏｄ  ｐ１であり、上記にて示すステップＳ３１によりｃｋ１＝ｃｋ＊Ｐａ１であることから、ｃｋ１＝Ｐａｋ  ｍｏｄ  ｐ１  ＝ｃｋ＊Ｐａ  ｍｏｄ  ｐ１  となる。一方、Ｐａｋの算出方法により、Ｐａｋ＝ｋ＊Ｐａ  ｍｏｄ  ｎである。ここで、ｎ＝ｐ１×ｐ２であることから、（Ｐａｋ  ｍｏｄ  ｎ）  ｍｏｄ  ｐ１  ＝Ｐａｋ  ｍｏｄ  ｐ１となり、ｃｋ１＝Ｐａｋ  ｍｏｄ  ｐ１  ＝ｋ＊Ｐａ  ｍｏｄ  ｐ１である。したがって、この式より、ｃｋ１＝ｃｋ＊Ｐａ１＝  ｃｋ＊Ｐａ  ｍｏｄ  ｐ１  ＝ｋ＊Ｐａ  ｍｏｄ  ｐ１となり、この式よりｃｋ＝ｋとなることが分かる。【００９２】
上記（６−９）にて示すように、ｓ＝ｃｋｉ×ｃＱ’  ｍｏｄ  ｑ  ＝ｃＱ’／ｃｋ’  ｍｏｄ  ｑ  ＝ｃＱ×β／（ｃｋ×β）  ｍｏｄ  ｑ  ＝（ｒ×ｋｓ＋ｈ）／ｋ  ｍｏｄ  ｑ  となるので、除算モジュール１２９は、従来型の楕円ＤＳＡ署名方式の署名生成のステップＳ４で求める値ｓを算出していることになる。
また、署名生成プログラム１１０の主要演算モジュール１２６にて算出される値ｒは、従来型の楕円ＤＳＡ署名方式の署名生成と同じく点Ｐのｋ倍点である。【００９３】
したがって、主要演算モジュール１２６にて算出される値ｒと、除算モジュール１２９にて算出される値ｓとの組が、従来型の楕円ＤＳＡ署名方式の署名生成にて生成される署名Ｓと同一になる。
以上より、実施の形態における署名生成プログラム１１０は正しく署名生成できることが分かる。
１．８  実施の形態の効果
秘密パラメータメモリ部１０３、署名生成プログラム１１０の逆変換モジュール１２７と乗算モジュール１２８が解析困難な場合に、解析者はｎの因数であるｐ１、ｐ２を知らないため、スーパーアノマラス楕円曲線における離散対数問題を解くことができない。解析者は、変換後秘密鍵ＫＳＴとＰａｋを解析可能であるが、スーパーアノマラス楕円曲線における離散対数問題を解けないため、これらから秘密鍵ｋｓ及びＰａｋの離散対数ｋを求められない。【００９４】
ここで、Ｐａｋの離散対数ｋを求められないようシステムを設計した理由について、以下で説明する。もし、解析者がｋを知ることができれば、ｒ、ｓ、ｈ及びｑは解析者が知ることができるため、ｓ＝（ｒ×ｋｓ＋ｈ）／ｋ  ｍｏｄ  ｑから、解析者が秘密鍵ｋｓを求めることができてしまう。したがって、Ｐａｋの離散対数ｋは求められないようシステムを設計する必要がある。【００９５】
また、従来の楕円ＤＳＡ署名方式の署名生成において、秘密鍵ｋｓだけでなく、乱数ｋをも秘密にする必要がある。
なぜなら、値ｈ、ｒ、ｓは、解析者（攻撃者）が知ることができる。さらに、乱数ｋが知られると、ステップＳ４により秘密鍵ｋｓを求めることが可能であるからである。
そこで、本発明は、乱数ｋ及び秘密鍵ｋｓが用いられるステップＳ２及び４において、解析者による解析を困難にしている。【００９６】
本発明では、上述したように、ステップＳ４の解析を困難にするために、スーパーアノマラス楕円を用いた準同型変換を利用することにより、秘密鍵ｋｓと乱数ｋとをスーパーアノマラス楕円上に点に変換して、解析者が解析できないようにしている。したがって、解析者は秘密鍵ｋｓを知ることができなくなるため、実施の形態における署名生成システムは安全である。【００９７】
ここで、従来型の楕円ＤＳＡ署名方式と本発明の楕円ＤＳＡ署名方式との対応について図９を用いて説明する。
図９は、本発明の楕円ＤＳＡ署名方式の動作のうち、従来型の楕円ＤＳＡ署名方式の署名生成におけるステップＳ４に対応する動作部分を示す。
図９において破線で囲んだ処理群３１０は、図６にて示すステップＳ１４０に対応している。ここで、処理群３１０は、変換後秘密鍵メモリ部１０５と、ｒ＊ＫＳＴを算出する処理群３０１とから構成されている。【００９８】
処理群３１１は、ステップＳ１３０に対応している。ここで、処理群３１１は、公開パラメータメモリ部１０４と、ｈＰａを算出する処理群３０２とから構成されている。
処理群３１０及び処理群３１１による結果を加算する処理群３０３は、ステップＳ１４５に対応している。
離散対数問題ｃＱを算出する処理群３０４はステップＳ１５０に対応し、離散対数ｃｋを算出する処理群３０５は、ステップＳ１５５に対応している。【００９９】
処理群３０４及び３０５の算出結果それぞれにβを乗算する処理群３０６は、ステップＳ１６０からＳ１７０に対応している。
さらには、署名データＳ＝（ｒ，ｓ）に含まれるデータｓを算出する処理群３０７は、ステップＳ１７５、Ｓ１８０に対応している。
処理群３２０は解析可能な領域にて実行され、処理群３２１は、上述したように、処理内容の解析を困難にするために、ハード対策やソフトウェア対策により耐タンパ性を有する領域で実行される。【０１００】
ここで、上述したように、秘密鍵ｋｓは、ＫＳＴ（＝ｋｓ＊Ｐａ）に予め変換され記憶されており、秘密鍵ｋｓ自体は署名生成を行う際には現れることはないので、解析者は秘密鍵ｋｓを知ることができない。また、乱数ｋは、そのままの値で、解析可能な領域にて現れることはない。乱数ｋは、解析可能な領域では、スーパーアノマラス楕円上に点に変換されているので、解析が困難となる。【０１０１】
また、スーパーアノマラス楕円を用いた準同型変換を用いると、乱数ｋの代わりに、アノマラス楕円Ｅａにおけるｋ＊Ｐが必要になり、さらには、ｋを算出するために、楕円ＤＳＡ署名方式による署名を行う楕円Ｅのｋ＊Ｐｋと、アノマラス楕円Ｅａにおけるｋ＊Ｐａとが必要になる。
そこで、本発明は、テーブルメモリ部１０２、乱数生成モジュール１２２、選択モジュール１２３及びランダム元生成モジュール１２４を用いて、ｋを生成し使用することなくｋ＊Ｐ及びｋ＊Ｐａを算出している。これにより、従来型の楕円ＤＳＡ署名方式のステップＳ２によりＲ（＝ｋ＊Ｐ）を求める際には、乱数ｋが現れているが、本発明では、乱数ｋを出現させることなくＰｋ（＝ｋ＊Ｐ）を算出しているので、Ｐｋの算出時にはｋを求めることができない。また、算出結果からｋを求めることも困難にしている。【０１０２】
従来、秘密鍵ｋｓ及び乱数ｋを解析困難にするためには、ステップＳ２及びステップＳ４の実行において、ハード対策を施す必要がある。しかしながら、本発明では、離散対数問題を解き、解を用いる動作部分（処理群３０４、３０５、及び３０６）に対して解析が困難になるようにハード対策を施せばよい。これにより、ハード対策を施す部分が限定されるので、署名生成装置の実装が従来より容易となる。【０１０３】
また、図１０において、従来の楕円ＤＳＡ署名方式の署名生成による各ステップと、本発明の署名生成装置１０の構成要素による動作との対応を示す。なお、各構成要素間における接続線は、図２及び図４に示しているので、図１０では省略している。
ハッシュ値生成モジュール１２１により、ステップＳ１と同等の動作が実現できる。
ステップＳ２には、テーブルメモリ部１０２、乱数生成モジュール１２２、選択モジュール１２３及びランダム元生成モジュール１２４からなる構成群４０１により、ステップＳ２と同等の動作が実現できる。【０１０４】
主要演算モジュール１２６にて行われる値ｒの算出により、ステップＳ３と同等の動作が実現できる。
変換モジュール１２５、主要演算モジュール１２６、逆変換モジュール１２７、乗算モジュール１２８及び除算モジュール１２９からなる構成群４０２により、ステップＳ４と同等の動作が実現できる。【０１０５】
署名データ生成モジュール１３０により、ステップＳ５と同等の動作が実現できる。
また、秘密パラメータメモリ部１０３、公開パラメータメモリ部１０４、変換後秘密鍵メモリ部１０５は、各モジュールの動作に応じて利用される。
また、逆変換モジュール１２７及び乗算モジュール１２８からなる構成群４０２は、上述したように、解析困難にするためにハード対策を施す必要がある部分である。【０１０６】
なお、解析困難にするためにハード対策を施すとしたが、これに限定されない。解析を困難にする対策であれば、ハード対策に限らず他の対策でもよい。
１．９  変形例
上記に説明した実施の形態は、本発明の実施の一例であり、本発明はこの実施の形態に何ら限定されるものではなく、その旨を逸脱しない範囲において種々なる態様で実施し得るものである。例えば、以下のような場合も本発明に含まれる。【０１０７】
（１）実施の形態において、ｐ、ｑ、ｕのビット数ｌｅｎを１６０としているが、これに限らない。１６０より大きい、例えば１９２や２２４としてもよい。また、ｎのビット数を１０２４としているが、これに限らない。１０２４より大きい、例えば２０４８や４０９６としてもよい。
（２）実施の形態では、署名生成プログラムの形態であるが、これを暗号化プログラムや復号化プログラムの形態としてもよい。【０１０８】
（３）実施の形態においては、第２の群として楕円曲線Ｅａ上の群を使用したが、これに限定されない。第２の群として剰余整数環の乗法群や、その他の群を利用するとしてもよい。
また、実施の形態では楕円曲線のスカラ倍演算を行って、整数を変換したが、これに限定されない。整数を変換する演算として、群の冪演算を用いてもよい。ここで、冪演算とは、群の基本演算、すなわち、剰余整数環では乗算、楕円曲線上の群では楕円曲線加算を、整数回行った結果を求める演算である。したがって、剰余整数環の乗法群の冪演算は冪乗演算、楕円曲線上の群の冪演算は楕円曲線のスカラ倍演算である。実施の形態では、第２の群Ｇａは、Ｅａ（ＧＦ（ｐ１））×Ｅａ（ＧＦ（ｐ２））であり、離散対数問題はこの「部分群」である、Ｅａ（ＧＦ（ｐ１））で解いているが、剰余整数環Ｚ／ｎＺの乗法群やその他の群の「部分群」において離散対数問題を解いてもよい。また、第２の群を特許文献３における剰余整数環の乗法群としてもよい。【０１０９】
（４）上記実施の形態において、第２の群Ｇａは、合成数ｎ（＝ｐ１×ｐ２）に対するＺ／ｎＺ上の楕円曲線上の群としたが、これに限定されない。なお、ｐ１，ｐ２は互いに異なるに素数である。
第２の群Ｇａは、合成数ｎ（＝ｐ１＾ｍ×ｐ２）に対する対するＺ／ｎＺ上の楕円曲線上の群であってもよい。だたし、ｍは１以上の整数である。ここで、ｐ１＾ｍはｐ１のｍ乗を示す。【０１１０】
または、第２の群Ｇａは、合成数ｎ（＝ｐ１＾ｍ×ｐ２）に対する対するＺ／ｎＺ上の乗法群であってもよい。だたし、ｍは１以上の整数である。このとき、第２の群の部分群は、Ｚ／ｐ１＾ｍ  Ｚ上の乗法群としてもよい。
（５）上記実施の形態において、署名生成装置１０は、ランダム元生成モジュール１２４にて２つのランダム元（Ｐｋ、Ｐａｋ）を生成したが、これに限定されない。【０１１１】
ランダム元生成モジュール１２４は、１つのランダム元（例えば、Ｐｋ）のみを生成してもよい。この場合、署名生成装置１０は、２×ｌｅｎ個の元対の代わりに２×ｌｅｎ個のＰ＿（ｉ，ｊ）を格納している（ｉ＝０，１、ｊ＝０，１，・・・，ｌｅｎ−１）。署名生成装置１０は、ｌｅｎビットの乱数ｕを生成すると、生成した乱数ｕを用いて第１の群Ｇの元Ｐｋを算出する。算出方法は、上記実施の形態にて示す方法と同様であるため、ここでの説明は省略する。これにより、署名生成装置１０は、乱数ｋを第三者に知られることがないように第１の群Ｇの元Ｐｋを算出することができる。【０１１２】
または、ランダム元生成モジュール１２４は、２個以上のランダム元（Ｐｋ、Ｐａｋ１、Ｐａｋ２、・・・、Ｐａｋｎ）を生成してもよい（ｎは、１以上の整数）。
（６）上記実施の形態において、署名生成装置１０における選択モジュール１２３は、乱数生成モジュール１２２にて生成された正整数ｕをビット数がｌｅｎビットからなるビット表現に変換し、各ビットに対応する元対を選択したが、これに限定されない。【０１１３】
選択モジュール１２３は、乱数生成モジュール１２２にて生成された正整数ｕから直接元対を求めてもよい。
このとき、テーブルメモリ部１０２は、正整数１、２、３、・・・に対して、元対（ｖ＿１＊Ｐ，ｖ＿１＊Ｐａ）、（ｖ＿２＊Ｐ，ｖ＿２＊Ｐａ）、（ｖ＿３＊Ｐ，ｖ＿３＊Ｐａ）、・・・を記憶している。【０１１４】
選択モジュール１２３は、乱数生成モジュール１２２にて生成された正整数ｕに対応する元対（ｖ＿ｕ＊Ｐ，ｖ＿ｕ＊Ｐａ）をテーブルメモリ部１０２が記憶しているテーブルから選択する。
ランダム元生成モジュール１２４は、選択された元対（ｖ＿ｕ＊Ｐ，ｖ＿ｕ＊Ｐａ）に対して、Ｐｋ＝ｖ＿ｕ＊Ｐ、Ｐａｋ＝ｖ＿ｕ＊Ｐａとする。【０１１５】
以降の動作は、実施の形態と同様であるので、ここでの説明は省略する。
以下、別の例を説明する。
または、テーブルメモリ部１０２は、元対（ｖ＿１＊Ｐ，ｖ＿１＊Ｐａ）、（ｖ＿２＊Ｐ，ｖ＿２＊Ｐａ）、（ｖ＿３＊Ｐ，ｖ＿３＊Ｐａ）、・・・、（ｖ＿ｔ＊Ｐ，ｖ＿ｔ＊Ｐａ）を記憶している。ｔは１以上の整数である。【０１１６】
選択モジュール１２３は、以下のようにして１個以上の元対を選択する。
選択モジュール１２３は、正整数ｕがｔ以下である場合には、元対（ｖ＿ｕ＊Ｐ，ｖ＿ｕ＊Ｐａ）をテーブルメモリ部１０２が記憶しているテーブルから選択する。
選択モジュール１２３は、正整数ｕがｔより大きい場合には、ｕ＝ｔ１＋ｔ２＋・・・＋ｔｐとなるｔ１、ｔ２、・・・、ｔｐを取得する。ここで、ｐは、２以上の整数であり、ｔ１、ｔ２、・・・、ｔｐのそれぞれは、ｔ以下の数である。選択モジュール１２３は、取得したｔ１、ｔ２、・・・、ｔｐそれぞれに対応する元対（ｖ＿ｔ１＊Ｐ，ｖ＿ｔ１＊Ｐａ）、（ｖ＿ｔ２＊Ｐ，ｖ＿ｔ２＊Ｐａ）、・・・、（ｖ＿ｔｐ＊Ｐ，ｖ＿ｔｐ＊Ｐａ）をテーブルメモリ部１０２が記憶しているテーブルから選択する。【０１１７】
ランダム元生成モジュール１２４は、選択された元対が１個である場合には、選択された元対（ｖ＿ｕ＊Ｐ，ｖ＿ｕ＊Ｐａ）に対して、Ｐｋ＝ｖ＿ｕ＊Ｐ、Ｐａｋ＝ｖ＿ｕ＊Ｐａとする。
ランダム元生成モジュール１２４は、選択された元対が２個以上である場合には、選択された元対（ｖ＿ｔ１＊Ｐ，ｖ＿ｔ１＊Ｐａ）、（ｖ＿ｔ２＊Ｐ，ｖ＿ｔ２＊Ｐａ）、・・・、（ｖ＿ｔｐ＊Ｐ，ｖ＿ｔｐ＊Ｐａ）に対して、ｖ＿ｔ１＊Ｐ、ｖ＿ｔ２＊Ｐ、・・・、ｖ＿ｔｐ＊Ｐを楕円曲線Ｅ上で加算することにより、Ｐｋを算出し、ｖ＿ｔ１＊Ｐａ、ｖ＿ｔ２＊Ｐａ、・・・、ｖ＿ｔｐ＊Ｐａを楕円曲線Ｅａ上で加算することにより、Ｐａｋを計算する。【０１１８】
以降の動作は、実施の形態と同様であるので、ここでの説明は省略する。
（７）上記実施の形態において、ランダム元生成モジュール１２４は、選択モジュール１２３にて選択されたｌｅｎ個全ての元対を用いて、Ｐｋ及びＰａｋを算出したが、これに限定されない。
ランダム元生成モジュール１２４は、選択されたｌｅｎ個の元対からｗ個の元対を選択し、選択したｗ個の元対を用いてＰｋ及びＰａｋを算出してもよい。ここで、ｗは、２以上ｌｅｎ以下の数である。【０１１９】
例えば、数ｗは予め与えられており、ランダム元生成モジュール１２４は、選択されたｌｅｎ個の元対からランダムにｗ個の元対を選択する。
また別の例として、ランダム元生成モジュール１２４は、選択されたｌｅｎ個の元対からビット値「１」に対応するｗ個の元対のみを選択してもよいし、ビット値「０」に対応するｗ個の元対のみを選択してもよい。【０１２０】
または、ランダム元生成モジュール１２４は、ビット値が１であるビットの個数とビット値が「０」であるビットの個数とを比較し、個数が多いほうのビット値に対応するｗ個の元対のみを選択してもよい。
または、数ｗは予め与えられており、ランダム元生成モジュール１２４は、選択されたｌｅｎ個の元対から、上位ビットｗ個分の元対を選択する。なお、ランダム元生成モジュール１２４は、選択されたｌｅｎ個の元対から、下位ビットｗ個分の元対を選択してもよい。【０１２１】
ここでは、ｗは、２以上ｌｅｎ以下の数であるとしたが、ｗは、１以上ｌｅｎ以下の数であってもよい。ｗ＝１の場合、ランダム元生成モジュール１２４は、選択された元対（ｖ＿ｕ＊Ｐ，ｖ＿ｕ＊Ｐａ）に対して、Ｐｋ＝ｖ＿ｕ＊Ｐ、Ｐａｋ＝ｖ＿ｕ＊Ｐａとする。
（８）本発明における分解組とは、上記実施の形態にて示すテーブルメモリ部１０２の記憶内容としてもよいし、正整数ｕ毎に対する複数の分解対（つまり、元対）、すなわち、正整数ｕの各ビットに対して選択された分解対の組み合わせとしてもよい。【０１２２】
（９）上記実施の形態において、署名生成は、署名生成プログラムにて生成されるとしたが、これに限定されない。
署名生成は、署名を生成するハードウェアにより生成されるとしてもよい。
つまり、署名生成プログラムに含まれる各モジュールは、上記にて説明した機能を達成する手段からなるとしてもよい。【０１２３】
（１０）上記の各装置は、具体的には、マイクロプロセッサ、ＲＯＭ、ＲＡＭ、ハードディスクユニット、ディスプレイユニット、キーボード、マウスなどから構成されるコンピュータシステムである。前記ＲＡＭまたはハードディスクユニットには、コンピュータプログラムが記憶されている。前記マイクロプロセッサが、前記コンピュータプログラムにしたがって動作することにより、各装置は、その機能を達成する。ここでコンピュータプログラムは、所定の機能を達成するために、コンピュータに対する指令を示す命令コードが複数個組み合わされて構成されたものである。【０１２４】
（１１）上記の各装置を構成する構成要素の一部または全部は、１個のシステムＬＳＩ（Ｌａｒｇｅ  Ｓｃａｌｅ  Ｉｎｔｅｇｒａｔｉｏｎ：大規模集積回路）から構成されているとしてもよい。システムＬＳＩは、複数の構成部を１個のチップ上に集積して製造された超多機能ＬＳＩであり、具体的には、マイクロプロセッサ、ＲＯＭ、ＲＡＭなどを含んで構成されるコンピュータシステムである。前記ＲＡＭには、コンピュータプログラムが記憶されている。前記マイクロプロセッサが、前記コンピュータプログラムにしたがって動作することにより、システムＬＳＩは、その機能を達成する。【０１２５】
（１２）上記の各装置を構成する構成要素の一部または全部は、各装置に脱着可能なＩＣカードまたは単体のモジュールから構成されているとしてもよい。前記ＩＣカードまたは前記モジュールは、マイクロプロセッサ、ＲＯＭ、ＲＡＭなどから構成されるコンピュータシステムである。前記ＩＣカードまたは前記モジュールは、上記の超多機能ＬＳＩを含むとしてもよい。マイクロプロセッサが、コンピュータプログラムにしたがって動作することにより、前記ＩＣカードまたは前記モジュールは、その機能を達成する。このＩＣカードまたはこのモジュールは、耐タンパ性を有するとしてもよい。【０１２６】
（１３）本発明は、上記に示す方法であるとしてもよい。また、これらの方法をコンピュータにより実現するコンピュータプログラムであるとしてもよいし、前記コンピュータプログラムからなるディジタル信号であるとしてもよい。
また、本発明は、前記コンピュータプログラムまたは前記ディジタル信号をコンピュータ読み取り可能な記録媒体、例えば、フレキシブルディスク、ハードディスク、ＣＤ−ＲＯＭ、ＭＯ、ＤＶＤ、ＤＶＤ−ＲＯＭ、ＤＶＤ−ＲＡＭ、ＢＤ（Ｂｌｕ−ｒａｙ  Ｄｉｓｃ）、半導体メモリなどに記録したものとしてもよい。また、これらの記録媒体に記録されている前記コンピュータプログラムまたは前記ディジタル信号であるとしてもよい。【０１２７】
また、本発明は、前記コンピュータプログラムまたは前記ディジタル信号を、電気通信回線、無線または有線通信回線、インターネットを代表とするネットワーク、データ放送等を経由して伝送するものとしてもよい。
また、本発明は、マイクロプロセッサとメモリを備えたコンピュータシステムであって、前記メモリは、上記コンピュータプログラムを記憶しており、前記マイクロプロセッサは、前記コンピュータプログラムにしたがって動作するとしてもよい。【０１２８】
また、前記プログラムまたは前記ディジタル信号を前記記録媒体に記録して移送することにより、または前記プログラムまたは前記ディジタル信号を前記ネットワーク等を経由して移送することにより、独立した他のコンピュータシステムにより実施するとしてもよい。
（１４）これらの実施の形態及び変形例の組合せであってもよい。
２．まとめ
本発明は、有限体上や楕円曲線上における離散対数問題を安全性の根拠とする署名方式（例えば、ＤＳＡ署名方式やＥＣＤＳＡ署名方式）を実装したプログラムを、攻撃者が解析困難にするソースコード難読化方法を提供することを目的とする。【０１２９】
以下に、本発明における特徴を以下に示す。
（１）本発明は、秘密鍵を用いて、メッセージに対するディジタル署名を生成する署名生成装置に実行させる署名生成プログラムであって、前記署名生成装置は、第１の群Ｇに属する第１の元と第２の群Ｇａに属する第２の元との対である元対を複数個記憶しているテーブルメモリ部と、前記署名生成プログラムを記憶しているプログラムメモリ部と、前記プログラムメモリ部に記憶されている前記署名生成プログラムから１個ずつコンピュータ命令を読み出し、解釈し、その解釈結果に応じて動作するプロセッサとを備え、前記署名生成プログラムは、第１の整数を生成する整数生成モジュールと、前記第１の整数に基づいて、前記テーブルメモリ部で記憶している複数の前記元対の中から、複数の前記元対を選択し、出力する選択モジュールと、前記選択モジュールが出力した複数の前記対を使用して、前記第１の群Ｇに属する第３の元と前記第２の群Ｇａに属する第４の元を計算する群演算モジュールとを含み、前記第１の元と前記第２の元はそれぞれ、前記第１の群Ｇに属する予め与えられた元である第１の基本元Ｐと、前記第２の群Ｇａに属する予め与えられた元である第２の基本元Ｐａと、予め与えられた正整数である冪数に対して、前記冪数を冪とした前記第１の基本元Ｐの前記第１の群Ｇにおける冪演算を行うことで得られる元と、前記冪数を冪とした前記第２の基本元Ｐａの前記第２の群Ｇａにおける冪演算を行うことで得られる元であることを特徴とする。【０１３０】
（２）上記（１）の署名生成プログラムにおいて、前記選択モジュールは、前記第１の整数のビット値ごとに一つの前記対を選択するとしてもよい。
（３）上記（２）の署名生成プログラムにおいて、前記第３の元は、前記選択モジュールが選択した前記対の個々に含まれる前記第１の群Ｇに属する元のすべてに対して、前記第１の群Ｇの基本演算を行った結果得られる前記第１の群Ｇの元であり、前記第４の元は、前記選択モジュールが選択した前記対の個々に含まれる前記第２の群Ｇａに属する元のすべてに対して、前記第２の群Ｇａの基本演算を行った結果得られる前記第２の群Ｇａの元であるとしてもよい。【０１３１】
（４）上記（１）から（３）のいずれかに記載の署名生成プログラムにおいて、前記署名生成プログラムはさらに、前記第２の群Ｇａ上の冪演算を行うことにより、整数を前記第２の群に属する元に変換する変換モジュールと、前記第２の群Ｇａ上の基本演算を行う主要演算モジュールと、前記第２の群Ｇａまたは、前記第２の群Ｇａが真に含む前記第２の群Ｇａの部分群Ｓａにおける前記変換モジュールで行う変換の逆変換を行う逆変換モジュールとを含むとしてもいよい。【０１３２】
（５）上記（１）から（４）のいずれかに記載の署名生成プログラムにおいて、前記署名生成装置はさらに、前記秘密鍵と前記第２の基本元から生成される前記第２の群に属する元である変換後秘密鍵を記憶している変換後秘密鍵メモリ部を備え、前記署名生成プログラムはさらに、前記変換後秘密鍵メモリ部に記憶されている変換後秘密鍵を用いて、前記第２の群Ｇａの冪演算を行う変換後秘密鍵演算モジュールとを含むとしてもよい。【０１３３】
（６）上記（１）から（５）のいずれかに記載の署名生成プログラムにおいて、前記第１の群Ｇ及び前記第２の群Ｇａは、剰余整数環の乗法群であるとしてもよい。
（７）上記（１）に記載の署名生成プログラムにおいて、前記第２の群Ｇａは、２つの素数ｐ、ｑと正整数ｍを用いて表されるｎ＝ｐ＾ｍ×ｑに対し、Ｚ／ｎＺの乗法群であるとしてもよい（ただし、ｘ＾ｙはｘのｙ乗を示す）。【０１３４】
（８）上記（７）に記載の署名生成プログラムにおいて、前記部分群Ｓａは、Ｚ／ｐ＾ｍ  Ｚの乗法群であるとしてもよい。
（９）上記（８）に記載の署名生成プログラムにおいて、前記正整数ｍは２であるとしてもよい。
（１０）上記（１）から（５）のいずれかに記載の署名生成プログラムにおいて、前記第１の群Ｇは楕円曲線の群であり、前記部分群Ｓａは、アノマラス楕円曲線の群であるとしてもよい。【０１３５】
（１１）上記（１）から（５）のいずれかに記載の署名生成プログラムにおいて、前記第２の群Ｇａは、二つのアノマラス楕円曲線の群の直積であるとしてもよい。
（１２）上記（１）から（５）、（１１）及び（１２）のいずれかに記載の署名生成プログラムにおいて、前記逆変換モジュールは、前記第２の群Ｇａに属する元を前記部分群Ｓａに属する元に還元する還元手段を備えるとしてもよい。【０１３６】
（１３）本発明は、群の演算を行う演算装置に実行させる演算プログラムであって、前記演算装置は、第１の群Ｇに属する第１の元と第２の群Ｇａに属する第２の元との対を複数個記憶しているテーブルメモリ部と、前記署名生成プログラムを記憶しているプログラムメモリ部と、前記プログラムメモリ部に記憶されている前記署名生成プログラムから１個ずつコンピュータ命令を読み出し、解釈し、その解釈結果に応じて動作するプロセッサとを備え、前記演算プログラムは、第１の整数を生成する整数生成モジュールと、前記第１の整数に基づいて、前記テーブルメモリ部で記憶している複数の前記対の中から、複数の前記対を選択する選択モジュールと、前記選択モジュールが選択した複数の前記対を使用して、前記第１の群Ｇに属する第３の元と前記第２の群Ｇａに属する第４の元を計算する群演算モジュールとを含み、前記第１の元と前記第２の元はそれぞれ、予め与えられた前記第１の群Ｇに属する元である第１の基本元Ｐと、予め与えられた前記第２の群Ｇａに属する元である第２の基本元Ｐａと、予め与えられた正整数である冪数に対して、前記冪数を冪とした前記第１の基本元Ｐの前記第１の群Ｇにおける冪演算を行うことで得られる元と、前記冪数を冪とした前記第２の基本元Ｐａの前記第２の群Ｇａにおける冪演算を行うことで得られる元であることを特徴とする。【０１３７】
（１４）本発明は、秘密鍵を用いて、メッセージに対するディジタル署名を生成する署名生成装置であって、第１の群Ｇに属する第１の元と第２の群Ｇａに属する第２の元との対を複数個記憶しているテーブルメモリ部と、第１の整数を生成する整数生成部と、前記第１の整数に基づいて、前記テーブルメモリ部で記憶している複数の前記対の中から、複数の前記対を選択する選択部と、前記選択部が選択した複数の前記対を使用して、前記第１の群Ｇに属する第３の元と前記第２の群Ｇａに属する第４の元を計算する群演算部とを備え、前記第１の元と前記第２の元はそれぞれ、予め与えられた前記第１の群Ｇに属する元である第１の基本元Ｐと、予め与えられた前記第２の群Ｇａに属する元である第２の基本元Ｐａと、予め与えられた正整数である冪数に対して、前記冪数を冪とした前記第１の基本元Ｐの前記第１の群Ｇにおける冪演算を行うことで得られる元と、前記冪数を冪とした前記第２の基本元Ｐａの前記第２の群Ｇａにおける冪演算を行うことで得られる元であることを特徴とする。【０１３８】
（１５）上記（１４）に記載の署名生成装置において、前記選択部は、前記第１の整数のビット値ごとに一つの前記対を選択するとしてもよい。
（１６）上記（１４）または（１５）に記載の署名生成装置において、前記第３の元は、前記選択部が選択した前記対の個々に含まれる前記第１の群Ｇに属する元のすべてに対して、前記第１の群Ｇの基本演算を行った結果得られる前記第１の群Ｇの元であり、前記第４の元は、前記選択部が選択した前記対の個々に含まれる前記第２の群Ｇａに属する元のすべてに対して、前記第２の群Ｇａの基本演算を行った結果得られる前記第２の群Ｇａの元であるとしてもよい。【０１３９】
（１７）上記にて示す署名生成プログラムにおける署名方式は、有限体上や楕円曲線上における離散対数問題を安全性の根拠としているので、攻撃者が解析困難にすることができ、その価値は大きい。
また、上記にて示す署名生成装置は、有限体上や楕円曲線上における離散対数問題を安全性の根拠とする署名方式にて署名生成を行うので、攻撃者が解析困難にすることができ、その価値は大きい。【０１４０】
（１８）また、本発明は、群Ｇ上の離散対数問題を安全性の根拠として、群Ｇ上の基本元Ｐについて基本演算を複数回繰り返す冪演算を施す演算装置であって、複数の数の各々に分解組が予め対応付けられており、各分解組は複数の分解値を含み、各分解値は基本元Ｐについて任意の正整数を冪とする冪演算が施されて算出された群Ｇ上の元であり、前記演算装置は、前記複数の分解組を記憶する分解対記憶手段と、前記複数の数からランダムに数ｕを選択し、選択した数ｕに対応する分解組を前記分解値記憶手段から選択する選択手段と、選択された分解組に含まれる全ての分解値について、前記群Ｇの基本演算を施して、冪乗元を生成する生成手段とを備えることを特徴とする。【０１４１】
（１９）以上説明したように、本発明によると、演算に使用する値の隠蔽だけでなく、演算そのものを隠蔽することができる。
【産業上の利用可能性】
【０１４２】
本発明を構成する各装置、各方法及びコンピュータプログラムは、情報を安全かつ確実に扱う必要があるあらゆる産業において、経営的に、また継続的及び反復的に使用することができる。また、本発明を構成する各装置、各方法及び各コンピュータプログラムは、電器機器製造産業において、経営的に、また継続的及び反復的に、製造し、販売することができる。
【図１】
2007074836.tif 000003
【図２】
2007074836.tif 000004
【図３】
2007074836.tif 000005
【図４】
2007074836.tif 000006
【図５】
2007074836.tif 000007
【図６】
2007074836.tif 000008
【図７】
2007074836.tif 000009
【図８】
2007074836.tif 000010
【図９】
2007074836.tif 000011
【図１０】
2007074836.tif 000012
【手続補正書】
【提出日】平成20年6月4日(2008.6.4)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
群Ｇ及び群Ｇａ上の離散対数問題を安全性の根拠として、群Ｇ上の基本元Ｐについて並びに群Ｇａ上の基本元Ｐａについて基本演算を複数回繰り返す冪演算を施すことにより、メッセージに対するディジタル署名を生成する署名生成装置であって、
複数の数の各々に分解組が予め対応付けられており、各分解組は複数の分解対を含み、各分解対は第１の分解値と第２の分解値とを含み、各第１の分解値は基本元Ｐについて任意の正整数を冪とする冪演算が施されて算出された群Ｇ上の元であり、各第２の分解値は基本元Ｐａについて当該第２の分解値に対応する第１の分解値において用いられた正整数を冪とする冪演算が施されて算出された群Ｇａ上の元であり、
前記署名生成装置は、
前記複数の分解組を記憶する分解値記憶手段と、
前記複数の数からランダムに数ｕを選択し、選択した数ｕに対応する分解組を前記分解値記憶手段から選択する選択手段と、
選択された分解組に含まれる２つ以上の第１の分解値について、前記群Ｇの基本演算を施して、第１の冪乗元を生成し、選択された分解組に含まれ、且つ前記２つ以上の第１の分解値のそれぞれに対応する第２の分解値について、前記群Ｇａの基本演算を施して、第２の冪乗元を生成する生成手段と、
生成された前記第１の冪乗元及びメッセージそれぞれを群Ｇａ上の元に変換し、変換された第１の冪乗元、変換されたメッセージ及び前記第２の冪乗元に対して前記群Ｇａ上の演算を施し、第１の離散対数及び第２の離散対数を算出し、算出した第１及び第２の離散対数を用いて、メッセージに対するディジタル署名を生成する署名手段と
を備えることを特徴とする署名生成装置。
【請求項２】
前記複数の数の各々は、長さが２以上の所定長からなるビット列で表現される数であり、
前記所定長からなるビット列の各ビット値に応じて分解対が対応付けられており、
前記選択手段は、
選択した前記数ｕを前記所定長のビット列からなるビット表現へと変換し、各ビットそれぞれの値に応じた分解対からなる前記分解組を前記分解値記憶手段から選択する
ことを特徴とする請求項１に記載の署名生成装置。
【請求項３】
前記生成手段は、
ビット値ごとに選択された分解対からなる前記分解組に含まれる２つ以上の第１の分解値に対して、前記群Ｇにおける基本演算を施して前記第１の冪乗元を生成し、
ビット値ごとに選択された分解対からなる前記分解組に含まれ、且つ前記２つ以上の第１の分解値のそれぞれに対応する第２の分解値に対して、前記群Ｇａにおける前記基本演算を施して前記第２の冪乗元を生成する
ことを特徴とする請求項２に記載の署名生成装置。
【請求項４】
前記第１の冪乗元は、２つ以上の値を含み、
前記署名手段は、
前記メッセージに対するハッシュ値を冪とし、前記基本元Ｐａに対して群Ｇａにおける前記冪演算を施すことにより、前記ハッシュ値を前記群Ｇａに属する変換後ハッシュ値へと変換する変換部と、
前記第１の冪乗元に含まれる１つの値を用いて、第１のデータを算出する第１演算部と、
前記変換後ハッシュ値に、前記群Ｇａ上の基本演算を施し、前記群Ｇａに属する第３の冪乗元を算出する第２演算部と、
前記群Ｇａ又は前記群Ｇａに真に含まれる部分群Ｓａにおいて、前記第２の冪乗元及び前記第３の冪乗元それぞれに対して、前記変換部にて行われる変換の冪演算の逆算を施すことにより、第１及び第２の離散対数を求める逆変換部と、
前記第１及び前記第２の離散対数を用いて、第２のデータを算出する第３演算部と、
前記第１のデータと前記第２のデータとの組からなるディジタル署名を生成するデータ生成部と
を含むことを特徴とする請求項１に記載の署名生成装置。
【請求項５】
前記署名生成装置は、さらに、
秘密鍵を冪として前記基本元Ｐａに対して前記群Ｇａの基本演算を施して、前記群Ｇａに属する変換後秘密鍵を記憶している変換後秘密鍵記憶手段を備え、
前記第２演算部は、
前記変換後秘密鍵に対して前記第１のデータを冪とする前記群Ｇａの冪演算を施して得られる前記群Ｇａ上の元である演算結果と、前記変換後ハッシュ値とに対して前記群Ｇａ上の基本演算を施して前記第３の冪乗元を算出する
ことを特徴とする請求項４に記載の署名生成装置。
【請求項６】
前記群Ｇ及び前記群Ｇａは、剰余整数環の乗法群であり、
前記群Ｇ及び前記群Ｇａのそれぞれにおける基本演算とは、各元に対して乗算を施す乗法演算であり、
前記群Ｇ及び前記群Ｇａのそれぞれにおける冪演算とは、正整数を冪数とする冪乗演算である
ことを特徴とする請求項５に記載の署名生成装置。
【請求項７】
前記群Ｇａは、２つの素数ｐ、ｑと、正整数ｍとを用いて表されるｎ＝ｐ＾ｍ×ｑに対し、Ｚ／ｎＺの乗法群であり、＾は冪乗算を示す演算子であり、×は、乗算を示す演算子であり、Ｚは整数環であり、Ｚ／ｎＺは剰余整数環である
ことを特徴とする請求項６に記載の署名生成装置。
【請求項８】
前記部分群Ｓａは、Ｚ／ｐ＾ｍ  Ｚの乗法群である
ことを特徴とする請求項７に記載の署名生成装置。
【請求項９】
前記正整数ｍは２である
ことを特徴とする請求項８に記載の署名生成装置。
【請求項１０】
前記群Ｇは、楕円曲線の群であり、
前記部分群Ｓａは、アノマラス楕円曲線の群であり、
前記群Ｇ及び前記群Ｇａのそれぞれにおける基本演算とは、各元に対して楕円曲線上の加算を施す演算であり、
前記群Ｇ及び前記群Ｇａのそれぞれにおける冪演算とは、前記正整数に楕円曲線上の乗算を施す演算である
ことを特徴とする請求項４に記載の署名生成装置。
【請求項１１】
前記群Ｇは、楕円曲線の群であり、
前記群Ｇａは、２つのアノマラス楕円曲線の直積であり、
前記群Ｇ及び前記群Ｇａのそれぞれにおける基本演算とは、各元に対して楕円曲線上の加算を施す演算であり、
前記群Ｇ及び前記群Ｇａのそれぞれにおける冪演算とは、正整数に楕円曲線上の乗算を施す演算である
ことを特徴とする請求項４に記載の署名生成装置。
【請求項１２】
前記逆変換部は、前記群Ｇａに属する元を、前記部分群Ｓａに属する元に還元する還元部を含み、
前記逆変換部は、前記還元部を用いて前記第２の冪乗元及び前記第３の冪乗元それぞれを、前記部分群Ｓａに属する元に還元し、還元した元それぞれに対して、前記逆算を施すことにより、前記第１の離散対数及び前記第２の離散対数を求める
ことを特徴とする請求項４に記載の署名生成装置。
【請求項１３】
群Ｇ及び群Ｇａ上の離散対数問題を安全性の根拠として、群Ｇ上の基本元Ｐについて並びに群Ｇａ上の基本元Ｐａについて基本演算を複数回繰り返す冪演算を施すことにより、メッセージに対するディジタル署名を生成する署名生成装置であって、
複数の数の各々に分解組が予め対応付けられており、各分解組は複数の分解対を含み、各分解対は第１の分解値と第２の分解値とを含み、各第１の分解値は基本元Ｐについて任意の正整数を冪とする冪演算が施されて算出された群Ｇ上の元であり、各第２の分解値は基本元Ｐａについて当該第２の分解値に対応する第１の分解値において用いられた正整数を冪とする冪演算が施されて算出された群Ｇａ上の元であり、
前記署名生成装置は、
前記複数の分解組を記憶する分解値記憶手段と、
前記複数の数からランダムに数ｕを選択し、選択した数ｕに対応する分解対を前記分解値記憶手段から選択する選択手段と、
選択された分解対に含まれる第１の分解値及びメッセージそれぞれを群Ｇａ上の元に変換し、変換された第１の分解対、変換されたメッセージ及び選択された分解対に含まれる第２の分解値に対して前記群Ｇａ上の演算を施し、離散対数問題を解いて第１及び第２の離散対数を算出し、算出した第１及び第２の離散対数を用いて、メッセージに対するディジタル署名を生成する署名手段と
を備えることを特徴とする署名生成装置。
【請求項１４】
群Ｇ及び群Ｇａ上の離散対数問題を安全性の根拠として、群Ｇ上の基本元Ｐについて並びに群Ｇａ上の基本元Ｐａについて基本演算を複数回繰り返す冪演算を施すことにより、メッセージに対するディジタル署名を生成する署名生成装置で用いられる署名生成方法であって、
複数の数の各々に分解組が予め対応付けられており、各分解組は複数の分解対を含み、各分解対は第１の分解値と第２の分解値とを含み、各第１の分解値は基本元Ｐについて任意の正整数を冪とする冪演算が施されて算出された群Ｇ上の元であり、各第２の分解値は基本元Ｐａについて当該第２の分解値に対応する第１の分解値において用いられた正整数を冪とする冪演算が施されて算出された群Ｇａ上の元であり、
前記署名生成装置は、
前記複数の分解組を記憶する分解値記憶手段を備え、
前記署名生成方法は、
前記複数の数からランダムに数ｕを選択し、選択した数ｕに対応する分解組を前記分解値記憶手段から選択する選択ステップと、
選択された分解組に含まれる２つ以上の第１の分解値について、前記群Ｇの基本演算を施して、第１の冪乗元を生成し、選択された分解組に含まれ、且つ前記２つ以上の第１の分解値のそれぞれに対応する第２の分解値について、前記群Ｇａの基本演算を施して、第２の冪乗元を生成する生成ステップと、
生成された前記第１の冪乗元及びメッセージそれぞれを群Ｇａ上の元に変換し、変換された第１の冪乗元、変換されたメッセージ及び前記第２の冪乗元に対して前記群Ｇａ上の演算を施し、第１の離散対数及び第２の離散対数を算出し、算出した第１及び第２の離散対数を用いて、メッセージに対するディジタル署名を生成する署名ステップと
を含むことを特徴とする署名生成方法。
【請求項１５】
群Ｇ及び群Ｇａ上の離散対数問題を安全性の根拠として、群Ｇ上の基本元Ｐについて並びに群Ｇａ上の基本元Ｐａについて基本演算を複数回繰り返す冪演算を施すことにより、メッセージに対するディジタル署名を生成する署名生成装置で用いられる署名生成プログラムであって、
複数の数の各々に分解組が予め対応付けられており、各分解組は複数の分解対を含み、各分解対は第１の分解値と第２の分解値とを含み、各第１の分解値は基本元Ｐについて任意の正整数を冪とする冪演算が施されて算出された群Ｇ上の元であり、各第２の分解値は基本元Ｐａについて当該第２の分解値に対応する第１の分解値において用いられた正整数を冪とする冪演算が施されて算出された群Ｇａ上の元であり、
前記署名生成装置は、
前記複数の分解組を記憶する分解値記憶手段を備え、
前記署名生成プログラムは、
前記複数の数からランダムに数ｕを選択し、選択した数ｕに対応する分解組を前記分解値記憶手段から選択する選択ステップと、
選択された分解組に含まれる２つ以上の第１の分解値について、前記群Ｇの基本演算を施して、第１の冪乗元を生成し、選択された分解組に含まれ、且つ前記２つ以上の第１の分解値のそれぞれに対応する第２の分解値について、前記群Ｇａの基本演算を施して、第２の冪乗元を生成する生成ステップと、
生成された前記第１の冪乗元及びメッセージそれぞれを群Ｇａ上の元に変換し、変換された第１の冪乗元、変換されたメッセージ及び前記第２の冪乗元に対して前記群Ｇａ上の演算を施し、第１の離散対数及び第２の離散対数を算出し、算出した第１及び第２の離散対数を用いて、メッセージに対するディジタル署名を生成する署名ステップと
を含むことを特徴とする署名生成プログラム。
【請求項１６】
前記複数の数の各々は、長さが２以上の所定長からなるビット列で表現される数であり、
前記所定長からなるビット列の各ビット値に応じて分解対が対応付けられており、
前記選択ステップは、
選択した前記数ｕを前記所定長のビット列からなるビット表現へと変換し、各ビットそれぞれの値に応じた分解対からなる前記分解組を前記分解値記憶手段から選択する
ことを特徴とする請求項１５に記載の署名生成プログラム。
【請求項１７】
前記生成ステップは、
ビット値ごとに選択された分解対からなる前記分解組に含まれる２つ以上の第１の分解値に対して、前記群Ｇにおける基本演算を施して前記第１の冪乗元を生成し、
ビット値ごとに選択された分解対からなる前記分解組に含まれ、且つ前記２つ以上の第１の分解値のそれぞれに対応する第２の分解値に対して、前記群Ｇａにおける前記基本演算を施して前記第２の冪乗元を生成する
ことを特徴とする請求項１６に記載の署名生成プログラム。
【請求項１８】
前記署名生成プログラムは、コンピュータ読み取り可能な記録媒体に記録されていることを特徴とする請求項１５に記載の署名生成プログラム。
【請求項１９】
群Ｇ及び群Ｇａ上の離散対数問題を安全性の根拠として、群Ｇ上の基本元Ｐについて並びに群Ｇａ上の基本元Ｐａについて基本演算を複数回繰り返す冪演算を施すことにより、メッセージに対するディジタル署名を生成する署名生成装置の集積回路であって、
複数の数の各々に分解組が予め対応付けられており、各分解組は複数の分解対を含み、各分解対は第１の分解値と第２の分解値とを含み、各第１の分解値は基本元Ｐについて任意の正整数を冪とする冪演算が施されて算出された群Ｇ上の元であり、各第２の分解値は基本元Ｐａについて当該第２の分解値に対応する第１の分解値において用いられた正整数を冪とする冪演算が施されて算出された群Ｇａ上の元であり、
前記集積回路は、
前記複数の分解組を記憶する分解値記憶手段と、
前記複数の数からランダムに数ｕを選択し、選択した数ｕに対応する分解組を前記分解値記憶手段から選択する選択手段と、
選択された分解組に含まれる２つ以上の第１の分解値について、前記群Ｇの基本演算を施して、第１の冪乗元を生成し、選択された分解組に含まれ、且つ前記２つ以上の第１の分解値のそれぞれに対応する第２の分解値について、前記群Ｇａの基本演算を施して、第２の冪乗元を生成する生成手段と、
生成された前記第１の冪乗元及びメッセージそれぞれを群Ｇａ上の元に変換し、変換された第１の冪乗元、変換されたメッセージ及び前記第２の冪乗元に対して前記群Ｇａ上の演算を施し、第１の離散対数及び第２の離散対数を算出し、算出した第１及び第２の離散対数を用いて、メッセージに対するディジタル署名を生成する署名手段と
を備えることを特徴とする集積回路。
【請求項２０】
群Ｇ及び群Ｇａ上の離散対数問題を安全性の根拠として、群Ｇ上の基本元Ｐについて並びに群Ｇａ上の基本元Ｐａについて基本演算を複数回繰り返す冪演算を施す演算装置であって、
複数の数の各々に分解組が予め対応付けられており、各分解組は複数の分解対を含み、各分解対は第１の分解値と第２の分解値とを含み、各第１の分解値は基本元Ｐについて任意の正整数を冪とする冪演算が施されて算出された群Ｇ上の元であり、各第２の分解値は基本元Ｐａについて当該第２の分解値に対応する第１の分解値において用いられた正整数を冪とする冪演算が施されて算出された群Ｇａ上の元であり、
前記演算装置は、
前記複数の分解組を記憶する分解値記憶手段と、
前記複数の数からランダムに数ｕを選択し、選択した数ｕに対応する分解組を前記分解値記憶手段から選択する選択手段と、
選択された分解組に含まれる２つ以上の第１の分解値について、前記群Ｇの基本演算を施して、第１の冪乗元を生成し、選択された分解組に含まれ、且つ前記２つ以上の第１の分解値のそれぞれに対応する第２の分解値について、前記群Ｇａの基本演算を施して、第２の冪乗元を生成する生成手段と
を備えることを特徴とする演算装置。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報セキュリティ技術としてのソフトウェアの難読化方法、特にディジタル署名方法の難読化の技術に関する。
【背景技術】
【０００２】
暗号ソフトを実装する場合、鍵や暗号アルゴリズムをそのまま実装すると、ソフトを解析された場合に、簡単に不正使用できる。そのため、ソフト解析を困難にする耐タンパーソフト技術が要望されている。耐タンパーソフト技術として、特許文献１において、演算及び演算領域を変換して、変換前の演算領域を推測困難にすることにより、ソフト解析困難とする方式が記載されている。
【０００３】
その方式は、一次変換などにより変換を行う。例えば、鍵とデータの加算を変換する場合、鍵とデータを変換し、変換後のデータを変換後の領域における加算を行い、その結果に逆変換を実行することにより鍵とデータの加算結果を得る。このような難読化された加算方法を、共通鍵暗号を用いた暗号化プログラムや復号化プログラムに適用することにより、プログラムを解析して鍵を得る攻撃に対する安全性を向上させることが可能になる。
【０００４】
以下に、特許文献１にて開示された技術の具体例を説明する。
ここで、入力ａ、ｂに対し、演算結果ａ＋ｂを出力するプログラムであり、主要演算モジュール、逆変換モジュール、及び出力モジュールから構成される加算プログラムについて説明する。
変換モジュールは、整数ｋ１、ｋ２を保持し、入力値ａ、ｂを受け付けると、保持している整数ｋ１、ｋ２を用いて、入力値ａ、ｂをそれぞれｔａ＝ｋ１×ａ＋ｋ２、ｔｂ＝ｋ１×ｂ＋ｋ２に変換する。ただし、×は乗算を示す。次に、主要演算モジュールは、値ｔａ、ｔｂに対して、ｔａｂ＝ｔａ＋ｔｂを計算する。逆変換モジュールは、ｔａｂに対して、ｃ＝（ｔａｂ−２×ｋ２）／ｋ１を計算する。出力モジュールは、演算結果ｃを出力する。
【０００５】
上記のように処理すると、ｔａｂ＝ｔａ＋ｔｂ＝ｋ１×ａ＋ｋ２＋ｋ１×ｂ＋ｋ２＝ｋ１×（ａ＋ｂ）＋２×ｋ２より、（ｔａｂ−２×ｋ２）／ｋ１＝ａ＋ｂが成り立つ。したがって、ｃ＝ａ＋ｂとなり、加算プログラムは、入力値ａ、ｂからａとｂの加算結果を算出することができる。
ここで、変換モジュール及び逆変換モジュールを解析困難なように実現した場合、第三者（解析者）が解析可能なものは、ｔａ、ｔｂ、ｔａｂのみであり、これらの値からａ、ｂを推測するのが難しいため、ａ、ｂを隠蔽することが可能になる。
【０００６】
特許文献１では、データを一次変換することで変換しており、データ自体を解析しにくくしているが、演算の種類、すなわち、「加算」は変換先においても「加算」を実行しており、演算の種類を隠蔽することまではできていない。
特許文献２では、ある情報（落し戸）を持っていれば容易に解ける落し戸付の離散対数問題に基づいて、「加算」を「乗算」もしくは、「楕円曲線上の群の加算」に変換することで、演算の種類の隠蔽を行っている。
【０００７】
また、ここで、従来用いられている楕円ＤＳＡ（Ｄｉｇｉｔａｌ  Ｓｉｇｎａｔｕｒｅ  Ａｌｇｏｒｉｔｈｍ）署名方式（以下、「従来型の楕円ＤＳＡ署名方式」という。）について説明する。従来型の楕円ＤＳＡ署名方式については、非特許文献３の４ページに記載されているので、ここでは簡単に説明する。
（１）パラメータ
従来型の楕円ＤＳＡ署名方式では、楕円曲線Ｅの方程式ｙ＾２＝ｘ＾３＋ａ×ｘ＋ｂの変数ａ、ｂ、楕円曲線Ｅの定義体ＧＦ（ｐ）、ベース点Ｐ及びベース点の位数ｑをパラメータとして持つ。ここで、ｘ＾ｙはｘのｙ乗を示し、ｑとＰはｑ＊Ｐ＝Ｏを満たす。Ｏは楕円曲線の群の零元であり、＊は楕円曲線のスカラ倍演算を示し、ｑ＊Ｐはｑ個のＰを加算したものを表す。
【０００８】
（２）秘密鍵及び公開鍵
秘密鍵をｋｓ（０＜ｋｓ＜ｑ）とし、ＫＰ＝ｋｓ＊Ｐを公開鍵とする。
（３）署名生成
従来型の楕円ＤＳＡ署名方式の署名生成では、以下のステップで署名の対象となるメッセージｍのディジタル署名Ｓを生成する。
【０００９】
（ステップＳ１）  ｈ＝Ｈａｓｈ（ｍ）を計算する。ここで、Ｈａｓｈ（ｍ）はｍのハッシュ値である。メッセージからハッシュ値を求めるハッシュ関数は、例えば、ＳＨＡ−１である。ハッシュ関数については、非特許文献１の１９２〜１９５ページが詳しい。
（ステップＳ２）  乱数ｋを選択し、楕円曲線上の点Ｒ＝ｋ＊Ｐを計算する。
（ステップＳ３）  ｒ＝ｘ（Ｒ）  ｍｏｄ  ｑを計算する。ここで、ｘ（Ｒ）はＲのｘ座標を示す。
【００１０】
（ステップＳ４）  ｓ＝（ｈ＋ｒ×ｋｓ）／ｋ  ｍｏｄ  ｑを計算する。
（ステップＳ５）  Ｓ＝（ｒ，ｓ）を出力し終了。
（４）署名検証
従来型の楕円ＤＳＡ署名方式の署名検証では、以下のステップでディジタル署名Ｓを検証し、検証結果（ＯＫまたはＮＧ）を出力する。
【００１１】
（ステップＳ１０）  ｈ＝Ｈａｓｈ（ｍ）を計算する。
（ステップＳ１１）  Ｒ’＝（ｈ／ｓ  ｍｏｄ  ｑ）＊Ｐ＋（ｒ／ｓ  ｍｏｄ  ｑ）＊ＫＰを計算し、ｒ’＝ｘ（Ｒ’）とする。
（ステップＳ１２）  ｒ＝ｒ’であるかをチェック。成り立つ場合は、ＯＫ、成り立たない場合は、ＮＧを出力し終了。
【特許文献１】米国特許第６，５９４，７６１号明細書
【特許文献２】国際公開第２００５／０９８７９５号パンフレット
【特許文献３】特許第３，４０２，４４１号明細書
【非特許文献１】岡本龍明、山本博資、「現代暗号」、産業図書（１９９７年）
【非特許文献２】Ｈｅｎｒｉ  Ｃｏｈｅｎ，  “Ａ  Ｃｏｕｒｓｅ  ｉｎ  Ｃｏｍｐｕｔａｔｉｏｎａｌ  Ａｌｇｅｂｒａｉｃ  Ｎｕｍｂｅｒ  Ｔｈｅｏｒｙ”，  ＧＴＭ  １３８，  Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，  １９９３，  ｐｐ．１６−１９
【非特許文献３】Ｉ．  Ｂｌａｋｅ，  Ｇ．  Ｓｅｒｏｕｓｓｉ  ａｎｄ  Ｎ．  Ｓｍａｒｔ，  “Ｅｌｌｉｐｔｉｃ  Ｃｕｒｖｅｓ  ｉｎ  Ｃｒｙｐｔｏｇｒａｐｈｙ”，ＣＡＭＢＲＩＤＧＥ  ＵＮＩＶＥＲＳＩＴＹ  ＰＲＥＳＳ，  １９９９
【非特許文献４】Ｎ．  Ｋｕｎｉｈｉｒｏ  ａｎｄ  Ｋ．  Ｋｏｙａｍａ，  “Ｔｗｏ  Ｄｉｓｃｒｅｔｅ  Ｌｏｇ  Ａｌｇｏｒｉｔｈｍｓ  ｆｏｒ  Ｓｕｐｅｒ−Ａｎｏｍａｌｏｕｓ  Ｅｌｌｉｐｔｉｃ  Ｃｕｒｖｅｓ”，  ＳＣＩＳ’９９，  １９９９，  ｐｐ．  ８６９−８７４
【発明の開示】
【発明が解決しようとする課題】
【００１２】
従来型の楕円ＤＳＡ署名方式の署名生成においては、秘密鍵ｋｓだけでなく、乱数ｋをも秘密にする必要がある。なぜなら、乱数ｋが第三者に知られると、ステップＳ４の式を使ってｋｓを逆算することが可能であるからである。
しかしながら、上記従来例の方式は、演算（加算）の変換を行っており、その演算を使用する部分については、解析困難にすることが可能であるが、従来型の楕円ＤＳＡ署名方式の署名生成において、乱数ｋを解析困難にすることはできない。
【００１３】
そこで、本発明は、上記課題に鑑みて、署名生成の処理に用いられる値を解析困難にすることのできる署名生成装置、署名生成方法、署名生成プログラム、記録媒体及び集積回路を提供することを目的とする。
【課題を解決するための手段】
【００１４】
上記目的を達成するために、本発明は、群Ｇ及び群Ｇａ上の離散対数問題を安全性の根拠として、群Ｇ上の基本元Ｐについて並びに群Ｇａ上の基本元Ｐａについて基本演算を複数回繰り返す冪演算を施すことにより、メッセージに対するディジタル署名を生成する署名生成装置であって、複数の数の各々に分解組が予め対応付けられており、各分解組は複数の分解対を含み、各分解対は第１の分解値と第２の分解値とを含み、各第１の分解値は基本元Ｐについて任意の正整数を冪とする冪演算が施されて算出された群Ｇ上の元であり、各第２の分解値は基本元Ｐａについて当該第２の分解値に対応する第１の分解値において用いられた正整数を冪とする冪演算が施されて算出された群Ｇａ上の元であり、前記署名生成装置は、前記複数の分解組を記憶する分解値記憶手段と、前記複数の数からランダムに数ｕを選択し、選択した数ｕに対応する分解組を前記分解値記憶手段から選択する選択手段と、選択された分解組に含まれる２つ以上の第１の分解値について、前記群Ｇの基本演算を施して、第１の冪乗元を生成し、選択された分解組に含まれ、且つ前記２つ以上の第１の分解値のそれぞれに対応する第２の分解値について、前記群Ｇａの基本演算を施して、第２の冪乗元を生成する生成手段と、生成された前記第１の冪乗元及びメッセージそれぞれを群Ｇａ上の元に変換し、変換された第１の冪乗元、変換されたメッセージ及び前記第２の冪乗元に対して前記群Ｇａ上の演算を施し、第１の離散対数及び第２の離散対数を算出し、算出した第１及び第２の離散対数を用いて、メッセージに対するディジタル署名を生成する署名手段とを備えることを特徴とする。
【発明の効果】
【００１５】
上記に示した構成によると、署名生成装置は、ディジタル署名に用いる値の隠蔽だけでなく、演算そのものを隠蔽することができる。
ここで、前記複数の数の各々は、長さが２以上の所定長からなるビット列で表現される数であり、前記所定長からなるビット列の各ビット値に応じて分解対が対応付けられており、前記選択手段は、選択した前記数ｕを前記所定長のビット列からなるビット表現へと変換し、各ビットそれぞれの値に応じた分解対からなる前記分解組を前記分解値記憶手段から選択するとしてもよい。
【００１６】
この構成によると、署名生成装置は、使用する隠蔽された値を容易に選択することができる。
ここで、前記生成手段は、ビット値ごとに選択された分解対からなる前記分解組に含まれる２つ以上の第１の分解値に対して、前記群Ｇにおける基本演算を施して前記第１の冪乗元を生成し、ビット値ごとに選択された分解対からなる前記分解組に含まれ、且つ前記２つ以上の第１の分解値のそれぞれに対応する第２の分解値に対して、前記群Ｇａにおける前記基本演算を施して前記第２の冪乗元を生成するとしてもよい。
【００１７】
この構成によると、群Ｇ及び群Ｇａにおける基本演算において、使用する値及び演算を隠匿することができる。
ここで、前記第１の冪乗元は、２つ以上の値を含み、前記署名手段は、前記メッセージに対するハッシュ値を冪とし、前記基本元Ｐａに対して群Ｇａにおける前記冪演算を施すことにより、前記ハッシュ値を前記群Ｇａに属する変換後ハッシュ値へと変換する変換部と、前記第１の冪乗元に含まれる１つの値を用いて、第１のデータを算出する第１演算部と、前記変換後ハッシュ値に、前記群Ｇａ上の基本演算を施し、前記群Ｇａに属する第３の冪乗元を算出する第２演算部と、前記群Ｇａ又は前記群Ｇａに真に含まれる部分群Ｓａにおいて、前記第２の冪乗元及び前記第３の冪乗元それぞれに対して、前記変換部にて行われる変換の冪演算の逆算を施すことにより、第１及び第２の離散対数を求める逆変換部と、前記第１及び前記第２の離散対数を用いて、第２のデータを算出する第３演算部と、前記第１のデータと前記第２のデータとの組からなるディジタル署名を生成するデータ生成部とを含むとしてもよい。
【００１８】
この構成によると、署名生成装置は、署名手段において、使用する値及び演算を隠蔽することができる。
ここで、前記署名生成装置は、さらに、秘密鍵を冪として前記基本元Ｐａに対して前記群Ｇａの基本演算を施して、前記群Ｇａに属する変換後秘密鍵を記憶している変換後秘密鍵記憶手段を備え、前記第２演算部は、前記変換後秘密鍵に対して前記第１のデータを冪とする前記群Ｇａの冪演算を施して得られる前記群Ｇａ上の元である演算結果と、前記変換後ハッシュ値とに対して前記群Ｇａ上の基本演算を施して前記第３の冪乗元を算出するとしてもよい。
【００１９】
この構成によると、署名生成装置は、第２演算部において、使用する値及び演算を隠蔽することができる。
ここで、前記群Ｇ及び前記群Ｇａは、剰余整数環の乗法群であり、前記群Ｇ及び前記群Ｇａのそれぞれにおける基本演算とは、各元に対して乗算を施す乗法演算であり、前記群Ｇ及び前記群Ｇａのそれぞれにおける冪演算とは、正整数を冪数とする冪乗演算であるとしてもよい。
【００２０】
この構成によると、署名生成装置は、第１、第２及び第３の冪乗元の生成に用いられる演算は乗法演算であり、冪乗演算とは異なるので、演算を隠蔽することができる。
ここで、前記群Ｇは、楕円曲線の群であり、前記部分群Ｓａは、アノマラス楕円曲線の群であり、前記群Ｇ及び前記群Ｇａのそれぞれにおける基本演算とは、各元に対して楕円曲線上の加算を施す演算であり、前記群Ｇ及び前記群Ｇａのそれぞれにおける冪演算とは、前記正整数に楕円曲線上の乗算を施す演算であるとしてもよい。また、前記群Ｇは、楕円曲線の群であり、前記群Ｇａは、２つのアノマラス楕円曲線の直積であり、前記群Ｇ及び前記群Ｇａのそれぞれにおける基本演算とは、各元に対して楕円曲線上の加算を施す演算であり、前記群Ｇ及び前記群Ｇａのそれぞれにおける冪演算とは、正整数に楕円曲線上の乗算を施す演算であるとしてもよい。
【００２１】
これらの構成によると、署名生成装置は、第１、第２及び第３の冪乗元の生成に用いられる演算は楕円曲線上の加算演算であり、整数の加算演算とは異なるので、演算を隠蔽することができる。
また、本発明は、群Ｇ及び群Ｇａ上の離散対数問題を安全性の根拠として、群Ｇ上の基本元Ｐについて並びに群Ｇａ上の基本元Ｐａについて基本演算を複数回繰り返す冪演算を施すことにより、メッセージに対するディジタル署名を生成する署名生成装置であって、複数の数の各々に分解組が予め対応付けられており、各分解組は複数の分解対を含み、各分解対は第１の分解値と第２の分解値とを含み、各第１の分解値は基本元Ｐについて任意の正整数を冪とする冪演算が施されて算出された群Ｇ上の元であり、各第２の分解値は基本元Ｐａについて当該第２の分解値に対応する第１の分解値において用いられた正整数を冪とする冪演算が施されて算出された群Ｇａ上の元であり、前記署名生成装置は、前記複数の分解組を記憶する分解値記憶手段と、前記複数の数からランダムに数ｕを選択し、選択した数ｕに対応する分解対を前記分解値記憶手段から選択する選択手段と、選択された分解対に含まれる第１の分解値及びメッセージそれぞれを群Ｇａ上の元に変換し、変換された第１の分解対、変換されたメッセージ及び選択された分解対に含まれる第２の分解値に対して前記群Ｇａ上の演算を施し、離散対数問題を解いて第１及び第２の離散対数を算出し、算出した第１及び第２の離散対数を用いて、メッセージに対するディジタル署名を生成する署名手段とを備えることを特徴とする。
【００２２】
この構成によると、署名生成装置は、ディジタル署名に使用する値を隠匿することができる。
【発明を実施するための最良の形態】
【００２３】
以下、発明を実施するための最良の実施形態を、図面を参照しながら説明する。
１．第１の実施の形態
１．１  準備
ここでは、本発明にかかる実施の形態を説明する上で、必要となる“楕円曲線上の楕円べき倍演算”について説明する。
【００２４】
一例として、１００＊Ｐの計算について説明する。
１００＊Ｐ＝２（２（Ｐ＋２（２（２（Ｐ＋２Ｐ）））））と表すと、１００＊Ｐは、楕円曲線上の点による６回の２倍算と２回の加算により計算される。
このように、楕円べき倍演算は、楕円曲線上の２倍算及び加算による演算に帰着する。
ここで、楕円曲線Ｅの方程式を  ｙ＾２ ＝  ｘ＾３ ＋ａ×ｘ＋ｂ  とし、楕円曲線上の任意の点Ｐの座標を（ｘ１，ｙ１）とし、任意の点Ｑの座標を（ｘ２，ｙ２）とする。ここで、Ｒ＝Ｐ＋Ｑで定まる点Ｒの座標を（ｘ３，ｙ３）とする。
【００２５】
Ｐ≠Ｑの場合、Ｒ＝Ｐ＋Ｑは、楕円曲線上の加算の演算となる。加算の公式を以下に示す。
ｘ３ ＝｛（ｙ２ −ｙ１）／（ｘ２ −ｘ１）｝＾２ −ｘ１ −ｘ２ 
ｙ３ ＝｛（ｙ２ −ｙ１ ）／（ｘ２ −ｘ１）｝（ｘ１ −ｘ３）−ｙ１
Ｐ＝Ｑの場合、Ｒ＝Ｐ＋Ｑ＝Ｐ＋Ｐ＝２×Ｐとなり、Ｒ＝Ｐ＋Ｑは、楕円曲線上の２倍算の演算となる。２倍算の公式を以下に示す。
【００２６】
ｘ３ ＝｛（３×ｘ１＾２ ＋ａ）／（２×ｙ１） ｝＾２ −（２×ｘ１） 
ｙ３ ＝｛（３×ｘ１＾２ ＋ａ）／（２×ｙ１） ｝（ｘ１ −ｘ３）−ｙ１ 
ここで、上記演算は、楕円曲線が定義される有限体上での演算である。
なお、楕円曲線の演算公式については、“Ｅｆｆｉｃｉｅｎｔ  ｅｌｌｉｐｔｉｃ  ｃｕｒｖｅ  ｅｘｐｏｎｅｎｔｉａｔｉｏｎ”（Ｍｉｙａｊｉ， Ｏｎｏ， ａｎｄ Ｃｏｈｅｎ著，Ａｄｖａｎｃｅｓ  ｉｎ  ｃｒｙｐｔｏｌｏｇｙ−ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ＩＣＩＣＳ‘９７，Ｌｅｃｔｕｒｅ  ｎｏｔｅｓ  ｉｎ  ｃｏｍｐｕｔｅｒ  ｓｃｉｅｎｃｅ，１９９７，Ｓｐｒｉｎｇｅｒ−ｖｅｒｌａｇ，  ２８２−２９０．）に詳しく説明されている。
１．２  署名生成システム１の構成
本発明にかかる実施の形態としての署名生成システム１について説明する。
【００２７】
署名生成システム１は、図１にて示すように、署名生成装置１０、テーブル生成装置２０、メッセージ受付装置３０、署名データ送信装置４０、及び署名データ受信装置５０から構成されている。
メッセージ受付装置３０は、ユーザ操作によりメッセージｍを受け付け、受け付けたメッセージｍを署名生成装置１０へ出力する。
【００２８】
テーブル生成装置２０は、本発明における楕円ＤＳＡ署名方式（以下、単に「楕円ＤＳＡ署名方式」という。）の署名生成にて使用する複数の元対と、変換後秘密鍵とを生成し、生成した複数の元対と、変換後秘密鍵とを署名生成装置１０へ格納する。ここで、元対とは、第１の楕円曲線上の群の元と、第２の楕円曲線上の群の元との組である。また、変換後秘密鍵とは、秘密鍵に第２の楕円曲線上の楕円べき倍演算を施した演算結果である。
【００２９】
なお、元対、変換後秘密鍵の詳細については、後述する。
署名生成装置１０は、メッセージｍをメッセージ受付装置３０から受け付け、受け付けたメッセージｍに対し、楕円ＤＳＡ署名方式の署名生成により署名データＳ（＝（ｒ，ｓ））を生成する。
署名生成装置１０は、生成した署名データＳと、メッセージ受付装置３０から受け付けたメッセージｍを署名データ送信装置４０へ出力する。
【００３０】
署名データ送信装置４０は、例えば、インターネット６０により署名データ受信装置５０とネットワーク接続されている。署名データ送信装置４０は、署名生成装置１０からメッセージｍと、メッセージｍに対する署名データＳとを受け取ると、受け取ったメッセージｍ及び署名データＳを、インターネット６０を介して署名データ受信装置５０へ送信する。
【００３１】
署名データ受信装置５０は、署名データ送信装置４０からインターネット６０を介して、メッセージｍと、メッセージｍに対する署名データＳとを受信すると、署名検証を行う。
１．３  署名生成装置１０の構成
ここでは、署名生成装置１０の構成について説明する。
【００３２】
署名生成装置１０は、図２にて示すように、プロセッサ１０１、テーブルメモリ部１０２、秘密パラメータメモリ部１０３、公開パラメータメモリ部１０４、変換後秘密鍵メモリ部１０５、及びプログラムメモリ部１０６から構成されている。
（１）プロセッサ１０１
プロセッサ１０１は、コンピュータシステムを構成しており、プログラムメモリ部１０６に格納された署名生成プログラム１１０を読み込み、読み込んだ署名生成プログラム１１０とハードウェア資源とが協働することにより機能を達成する。
【００３３】
プロセッサ１０１は、プログラムメモリ部１０６に記憶されている署名生成プログラム１１０から１個ずつコンピュータ命令を読み出し、解釈し、その解釈結果に応じて動作する。
なお、署名生成プログラム１１０の詳細については後述する。
（２）テーブルメモリ部１０２
テーブルメモリ部１０２は、第１の群Ｇに属する元と、第２の群Ｇａに属する元の対である元対を複数個記憶している。なお、元対は、テーブル生成装置２０で生成される。
【００３４】
（２−１）第１の群Ｇ及び第２の群Ｇａについて
第１の群Ｇは、楕円ＤＳＡ署名方式で使用する楕円曲線Ｅの点を元とする群である。ここで、楕円曲線Ｅの方程式をｙ＾２＝ｘ＾３＋ａ×ｘ＋ｂとする。楕円曲線Ｅの方程式をもつ体ＧＦ（ｐ）上の楕円曲線の点から構成される群をＥ（ＧＦ（ｐ））とするとき、第１の群Ｇは、Ｅ（ＧＦ（ｐ））となる。
【００３５】
第２の群Ｇａは、ｎ＝ｐ１×ｐ２（ｐ１、ｐ２は素数）に対し、ＧＦ（ｐ１）上の楕円曲線Ｅａの点から構成される群Ｅａ（ＧＦ（ｐ１））と、ＧＦ（ｐ２）上の楕円曲線Ｅａの点から構成される群Ｅａ（ＧＦ（ｐ２））の直積Ｅａ（ＧＦ（ｐ１））×Ｅａ（ＧＦ（ｐ２））とする。Ｚ／ｎＺは体ではなく、環であるため、数学的には「Ｚ／ｎＺ上の楕円曲線」とはよべないが、ここでは便宜上、その直積をＺ／ｎＺ上の楕円曲線の群とよぶ。なお、Ｚは整数環であり、Ｚ／ｎＺは、数ｎを法とする剰余整数環である。
【００３６】
ここで、楕円曲線Ｅａの方程式をｙ＾２＝ｘ＾３＋ａａ×ｘ＋ｂａとする。また、素数ｐ１及びｐ２は、楕円曲線Ｅのベース点の位数ｑとは異なる数であり、第三者が知ることができないように生成及び管理がなされているものとする。
Ｅａ（ＧＦ（ｐ１））上の点Ｐａ１＝（ｘａ１，ｙａ１）  ｍｏｄ  ｐ１と、Ｅａ（ＧＦ（ｐ２））上の点Ｐａ２＝（ｘａ２，ｙａ２）  ｍｏｄ  ｐ２に対応するＺ／ｎＺ上の楕円曲線Ｅａ（ＧＦ（ｐ１））×Ｅａ（ＧＦ（ｐ２））の点Ｐａ＝（ｘａ，ｙａ）  ｍｏｄ  ｎは、以下のように定義する。ｘａをｘａ  ｍｏｄ  ｐ１＝ｘａ１，ｘａ  ｍｏｄ  ｐ２＝ｘａ２を満たす数、ｙａをｙａ  ｍｏｄ  ｐ１＝ｙａ１，ｙａ  ｍｏｄ  ｐ２＝ｙａ２を満たす数とする。
【００３７】
この定義より、Ｅａ（ＧＦ（ｐ１））×Ｅａ（ＧＦ（ｐ２））上の点Ｐａ＝（ｘａ，ｙａ）  ｍｏｄ  ｎに対応するＥａ（ＧＦ（ｐ１））上の点Ｐａ１をＰａ１＝（ｘａ１，ｙａ１）  ｍｏｄ  ｐ１とし、Ｅａ（ＧＦ（ｐ２））上の点Ｐａ２をＰａ２＝（ｘａ２，ｙａ２）  ｍｏｄ  ｐ２とすることで、Ｅａ（ＧＦ（ｐ１）），Ｅａ（ＧＦ（ｐ２））をＥａ（ＧＦ（ｐ１））×Ｅａ（ＧＦ（ｐ２））の部分群とみなす。
【００３８】
楕円曲線Ｅａはｍｏｄ  ｐ１での楕円曲線の位数、すなわち、点の個数がｐ１であるとする。このような体ＧＦ（ｐ１）上の楕円曲線をアノマラス（Ａｎｏｍａｌｏｕｓ）楕円曲線とよぶ。さらに、ｍｏｄ  ｐ２での楕円曲線の位数がｐ２である、すなわち、ＧＦ（ｐ２）上でもアノマラス楕円曲線であるとする。このとき、Ｚ／ｎＺ上の楕円曲線は、スーパーアノマラス（Ｓｕｐｅｒ−Ａｎｏｍａｌｏｕｓ）楕円曲線とよぶ。スーパーアノマラス楕円曲線については非特許文献４が詳しい。このとき、Ｚ／ｎＺ上の楕円曲線の群はＥａ（ＧＦ（ｐ１））×Ｅａ（ＧＦ（ｐ２））であるので、楕円曲線の位数はｎ（＝ｐ１×ｐ２）となる。
【００３９】
素数ｐ１のビット数を２×ｌｅｎ＋１ビットとする。なお、ｐ１のビット数は２×ｌｅｎ＋１より大きくてもよい。ｌｅｎは例えば、１６０である。ｐ２は、例えば、ｎ＝ｐ１×ｐ２のビット数が１０２４となるような大きさの素数である。
（２−２）テーブルメモリ部１０２に格納する元対について
テーブルメモリ部１０２は、２×ｌｅｎ個の元対ＰＰ＿（ｉ，ｊ）を格納する。ここで、ｉは０または１、ｊは０からｌｅｎ−１の値のいずれかであり、「＿」は下付き文字を示し、ｉ，ｊはＰＰのインデックスである。ＰＰ＿（ｉ，ｊ）＝（ｖ＿（ｉ，ｊ）＊Ｐ  ｍｏｄ  ｐ，ｖ＿（ｉ，ｊ）＊Ｐａ  ｍｏｄ  ｎ）である。＊は、Ｐに対しては、楕円曲線Ｅ上のスカラ倍演算、Ｐａに対しては、楕円曲線Ｅａ上のスカラ倍演算を示す。ｖ＿（ｉ，ｊ）は、ｌｅｎビットの値である。ここで、ＰＰ＿（ｉ，ｊ）に含まれる２点のスカラは等しいことに注意する。
【００４０】
ここで、元対の格納方法の一例を以下に示す。
テーブルメモリ部１０２は、複数の元対を格納するための領域を有している。
テーブルメモリ部１０２は、図３にて示すように、テーブルＴ１０１、Ｔ１０２、・・・、Ｔ１０３を格納している。つまり、テーブルメモリ部１０２は、ｌｅｎ個のテーブルを有している。
【００４１】
テーブルＴ１０１は、テーブル名称Ｔ１１０（ここでは、「テーブル０」）と、２値項目Ｔ１２０、Ｔ１２１（ここでは、「０」、「１」）と各２値項目Ｔ１２０、Ｔ１２１における元対Ｔ１３０、Ｔ１３１とから構成されている。１つのテーブルにおいて、２つの元対が格納されているので、テーブルメモリ部１０２は、テーブルをｌｅｎ個格納することにより、２×ｌｅｎ個の元対を格納することになる。
【００４２】
テーブル名称Ｔ１１０は、値ｊと対応付けがされている。つまり、テーブル名称Ｔ１１０（テーブル０）は、ｊ＝０と対応付けされており、テーブル名称Ｔ１１１（ここではテーブル１）は、ｊ＝１と対応付けされている。これにより、ｊ＝０、・・・、ｌｅｎ−１のそれぞれに対してテーブル名称が対応付けされている。
また、元対Ｔ１３０において、Ｐ＿（０，０）は、ｖ＿（０，０）＊Ｐ  ｍｏｄ  ｐであり、Ｐａ＿（０，０）は、ｖ＿（０，０）＊Ｐａ  ｍｏｄ  ｎである。元対Ｔ１３０において、Ｐ＿（１，０）は、ｖ＿（１，０）＊Ｐ  ｍｏｄ  ｐであり、Ｐａ＿（１，０）は、ｖ＿（１，０）＊Ｐａ  ｍｏｄ  ｎである。ＰＰ＿（ｉ，ｊ）＝（Ｐ＿（ｉ，ｊ），Ｐａ＿（ｉ，ｊ））であることに注意する。
【００４３】
元対のそれぞれは、２進数と対応付けがされている。具体的には、２進数の値が０である場合には、２値項目「０」における元対が対応付けされ、２進数の値が１である場合には、２値項目「１」における元対が対応付けされている。
（３）秘密パラメータメモリ部１０３
秘密パラメータメモリ部１０３は、耐タンパ性を有しており、素数ｐ１を記憶している。
【００４４】
（４）公開パラメータメモリ部１０４
公開パラメータメモリ部１０４は、楕円曲線Ｅの方程式ｙ＾２＝ｘ＾３＋ａ×ｘ＋ｂにおける変数ａ、ｂ、素数ｐ、楕円曲線Ｅ上のベース点Ｐ、及びその位数ｑと、楕円曲線Ｅａの方程式ｙ＾２＝ｘ＾３＋ａａ×ｘ＋ｂａにおける変数ａａ、ｂａ、合成数ｎ（＝ｐ１×ｐ２）、及び楕円曲線Ｅａ上の点Ｐａをそれぞれパラメータとして記憶している。ここで、点を記憶するとは、点の座標を記憶することを意味する。また、ｐ、ｑはｌｅｎビットの素数とする。
【００４５】
（５）変換後秘密鍵メモリ部１０５
変換後秘密鍵メモリ部１０５は、秘密鍵ｋｓに第２の楕円曲線Ｅａ上の楕円べき倍演算を施すことにより、秘密鍵ｋｓを変換した変換後秘密鍵ＫＳＴ（＝ｋｓ＊Ｐａ）を格納している。変換後秘密鍵ＫＳＴは、テーブル生成装置２０で生成される。
（６）プログラムメモリ部１０６
プログラムメモリ部１０６は、署名生成プログラム１１０を記憶している。
【００４６】
署名生成プログラム１１０は、図４にて示すように、ハッシュ値生成モジュール１２１、乱数生成モジュール１２２、選択モジュール１２３、ランダム元生成モジュール１２４、変換モジュール１２５、主要演算モジュール１２６、逆変換モジュール１２７、乗算モジュール１２８、除算モジュール１２９、及び署名データ生成モジュール１３０から構成されている。
【００４７】
本プログラムは、入力であるメッセージｍに対し、ｍの署名データＳ（＝（ｒ，ｓ））を出力するものである。
各モジュールは、機械語形式の複数の命令コードを組み合わせて構成されるコンピュータプログラムである。前記機械語形式は、プロセッサ１０１により解読され実行される形式である。
【００４８】
（６−１）ハッシュ値生成モジュール１２１
ハッシュ値生成モジュール１２１は、入力であるメッセージｍを、メッセージ受付装置３０から受け付け、受け付けたメッセージｍにハッシュ関数を施して、メッセージｍのハッシュ値ｈを計算する。ハッシュ関数は、例えば、ＳＨＡ−１である。
ハッシュ値生成モジュール１２１は、ハッシュ値ｈを変換モジュール１２５へ出力する。
【００４９】
（６−２）乱数生成モジュール１２２
乱数生成モジュール１２２は、ｌｅｎビットのランダムな正整数（乱数）ｕを生成し、生成した乱数ｕを選択モジュール１２３へ出力する。
（６−３）選択モジュール１２３
選択モジュール１２３は、乱数生成モジュール１２２から乱数ｕを受け取り、受け取った乱数ｕをビット表現に変換する。
【００５０】
選択モジュール１２３は、ビット表現に変換された乱数ｕ＝ｕ＿０＋ｕ＿１×２＋ｕ＿２×２＾２＋…＋ｕ＿（ｌｅｎ−１）×２＾（ｌｅｎ−１）に対し、テーブルメモリ部１０２からＰＰ＿（ｕ＿０，０），ＰＰ＿（ｕ＿１，１），ＰＰ＿（ｕ＿２，２），…，ＰＰ＿（ｕ＿（ｌｅｎ−１），ｌｅｎ−１）を選択する（ここで、ｉ＝０，１，２，…，ｌｅｎ−１に対しｕ＿ｉ＝０または１）。
【００５１】
ここでは、ｕ＿ｋにおける添え字ｋ（ｋ＝０，１，・・・，ｌｅｎ―１）の値がテーブルメモリ部１０２に格納されているテーブルのテーブル名称と対応付けされている。つまり、ｕ＿０はテーブル０と、ｕ＿１はテーブル１と、・・・、ｕ＿ｌｅｎ−１はテーブルｌｅｎ−１と対応付けがされている。
選択モジュール１２３は、選択したＰＰ＿（ｕ＿０，０），ＰＰ＿（ｕ＿１，１），ＰＰ＿（ｕ＿２，２），…，ＰＰ＿（ｕ＿（ｌｅｎ−１），ｌｅｎ−１）をランダム元生成モジュール１２４へ出力する。
【００５２】
（６−４）ランダム元生成モジュール１２４
ランダム元生成モジュール１２４は、選択モジュール１２３からｌｅｎ個の元対ＰＰ＿（ｕ＿ｉ，ｉ）＝（Ｐ＿（ｕ＿ｉ，ｉ），Ｐａ＿（ｕ＿ｉ，ｉ））を受け取り、受け取った元対それぞれに含まれるＰ＿（ｕ＿ｉ，ｉ）を公開パラメータメモリ部１０４で記憶している楕円曲線Ｅのパラメータａ、ｂ、素数ｐ、楕円曲線Ｅ上のベース点Ｐを用いて、楕円曲線Ｅ上で加算することにより、Ｐｋ（＝（ｖ＿（ｕ＿０，０）＊Ｐ＋ｖ＿（ｕ＿１，１）＊Ｐ＋・・・＋ｖ＿（ｕ＿ｌｅｎ−１，ｌｅｎ−１）＊Ｐ）を算出する（ここで、ｉ＝０，１，２，…，ｌｅｎ−１）。なお、Ｐｋ＝（ｖ＿（ｕ＿０，０）＋ｖ＿（ｕ＿１，１）＋・・・＋ｖ＿（ｕ＿（ｌｅｎ−１），ｌｅｎ−１））＊Ｐであることに注意する。
【００５３】
ランダム元生成モジュール１２４は、公開パラメータメモリ部１０４で記憶している楕円曲線Ｅａのパラメータａａ、ｂａ、合成数ｎを用いて、Ｐａ＿（ｕ＿ｉ，ｉ）  ｍｏｄ  ｎ（ｉ＝０，１，２，…，ｌｅｎ−１）を楕円曲線Ｅａ上で加算してＰａｋ  ｍｏｄ  ｎ（＝（ｖ＿（ｕ＿０，０）＊Ｐａ＋ｖ＿（ｕ＿１，１）＊Ｐａ＋・・・＋ｖ＿（ｕ＿ｌｅｎ−１，ｌｅｎ−１）＊Ｐａ））とする。ここで、Ｐａｋ＝（ｖ＿（ｕ＿０，０）＋ｖ＿（ｕ＿１，１）＋・・・＋ｖ＿（ｕ＿（ｌｅｎ−１），ｌｅｎ−１））＊Ｐａであることに注意する。
【００５４】
ランダム元生成モジュール１２４は、算出したＰｋを主要演算モジュール１２６へ出力し、算出したＰａｋを逆変換モジュール１２７へ出力する。
（６−５）変換モジュール１２５
変換モジュール１２５は、ハッシュ値生成モジュール１２１からハッシュ値ｈを受け取ると、公開パラメータメモリ部１０４で記憶している楕円曲線Ｅａのパラメータａａ、ｂａ、合成数ｎと楕円曲線Ｅａ上の点Ｐａと、受け取ったハッシュ値ｈとを用いて、ｈＰａ＝ｈ＊Ｐａ  ｍｏｄ  ｎを計算する。
【００５５】
変換モジュール１２５は、算出したｈＰａを主要演算モジュール１２６へ出力する。
（６−６）主要演算モジュール１２６
主要演算モジュール１２６は、ランダム元生成モジュール１２４からＰｋを受け取り、変換モジュール１２５からｈＰａを受け取る。
主要演算モジュール１２６は、ｒ＝ｘ（Ｐｋ）  ｍｏｄ  ｑを計算する。ここで、ｘ（Ｐｋ）は、Ｐｋのｘ座標を示す。
【００５６】
主要演算モジュール１２６は、変換後秘密鍵メモリ部１０５で記憶している変換後秘密鍵ＫＳＴと、公開パラメータメモリ部１０４で記憶している楕円曲線Ｅａのパラメータａａ、ｂｂ、合成数ｎを用いて、楕円曲線Ｅａ上でｒ＊ＫＳＴを計算し、ｈＰａと楕円曲線Ｅａ上の加算を行い、Ｑａ＝ｒ＊ＫＳＴ＋ｈＰａとする。
主要演算モジュール１２６は、算出したｒを署名データ生成モジュール１３０へ出力し、算出したＱａを逆変換モジュール１２７へ出力する。
【００５７】
（６−７）逆変換モジュール１２７
逆変換モジュール１２７は、ランダム元生成モジュール１２４からＰａｋを受け取り、主要演算モジュール１２６からＱａを受け取る。
逆変換モジュール１２７は、秘密パラメータメモリ部１０３で記憶している素数ｐ１を用いて、Ｐａ  ｍｏｄ  ｐ１に対するＱａの離散対数ｃＱと、Ｐａ  ｍｏｄ  ｐ１に対するＰａｋの離散対数ｃｋを計算する。
【００５８】
逆変換モジュール１２７は、算出した離散対数ｃＱ、ｃｋを乗算モジュール１２８へ出力する。
まず、Ｑａの離散対数ｃＱを求める際の処理を示す。
（ステップＳ２０）  Ｑａ１＝Ｑａ  ｍｏｄ  ｐ１，Ｐａ１＝Ｐａ  ｍｏｄ  ｐ１を計算。
【００５９】
（ステップＳ２１）  Ｐａ１に対するＱａ１の離散対数ｃＱ（すなわち、Ｑａ１＝ｃＱ＊Ｐａ１を満たすｃＱ）を計算する。
次に、Ｐａｋの離散対数ｃｋを求める際の処理を示す。
（ステップＳ３０）  ｃｋ１＝Ｐａｋ  ｍｏｄ  ｐ１，Ｐａ１＝Ｐａ  ｍｏｄ  ｐ１を計算。
【００６０】
（ステップＳ３１）  Ｐａ１に対するｃｋ１の離散対数ｃｋ（すなわち、ｃｋ１＝ｃｋ＊Ｐａ１を満たすｃｋ）を計算する。
ここで、ステップＳ２１及びＳ３１で計算している離散対数ｃＱ及びｃｋは、アノマラス楕円曲線上の離散対数問題の解である。
アノマラス楕円曲線上の離散対数問題を解く方法は、非特許文献３の８８〜９１ページが詳しい。計算方法はこの文献に記載されているため、ここでは説明を省略する。
【００６１】
なお、逆変換モジュール１２７は、処理内容の解析を困難にするために、ハード対策やソフトウェア対策により耐タンパ性を有する領域で実行されるものとする。
（６−８）乗算モジュール１２８
乗算モジュール１２８は、逆変換モジュール１２７から離散対数ｃＱ、ｃｋを受け取ると、乱数βを生成する。
【００６２】
乗算モジュール１２８は、公開パラメータメモリ部１０４で記憶している楕円曲線Ｅ上のベース点Ｐの位数ｑを用いて、離散対数ｃＱ及びｃｋに対し生成したβを乗じ、ｃＱ’＝ｃＱ×β  ｍｏｄ  ｑ，  ｃｋ’＝ｃｋ×β  ｍｏｄ  ｑを計算する。
乗算モジュール１２８は、算出したｃＱ’、ｃｋ’を除算モジュール１２９へ出力する。
【００６３】
なお、乗算モジュール１２８は、処理内容の解析を困難にするために、ハード対策やソフトウェア対策により耐タンパ性を有する領域で実行されるものとする。
（６−９）除算モジュール１２９
除算モジュール１２９は、乗算モジュール１２８からｃＱ’、ｃｋ’を受け取る。
除算モジュール１２９は、ｃｋ’のｍｏｄ  ｑでの逆元であるｃｋｉを計算する。ここで、ｃｋｉ×ｃｋ’＝１  ｍｏｄ  ｑを満たす。
【００６４】
除算モジュール１２９は、ｃｋｉとｃＱ’を乗じｍｏｄ  ｑをして、ｓ＝ｃｋｉ×ｃＱ’  ｍｏｄ  ｑを求める。逆元の計算については、非特許文献２が詳しい。
除算モジュール１２９は、算出したｓを署名データ生成モジュール１３０へ出力する。
（６−１０）署名データ生成モジュール１３０
署名データ生成モジュール１３０は、主要演算モジュール１２６からｒを受け取り、除算モジュール１２９からｓを受け取る。
【００６５】
署名データ生成モジュール１３０は、主要演算モジュール１２６から受け取ったｒと、除算モジュール１２９から受け取ったｓを１対として、署名データＳ＝（ｒ，ｓ）を生成する。
署名データ生成モジュール１３０は、ハッシュ値生成モジュール１２１が受け付けたメッセージｍと、生成した署名データＳを署名データ送信装置４０へ出力する。
１．４  テーブル生成装置２０の構成
ここでは、テーブル生成装置２０の構成について説明する。
【００６６】
テーブル生成装置２０は、図５にて示すように、公開パラメータメモリ部２０１、乱数生成部２０２、群演算部２０３、及び格納処理部２０４から構成されている。
（１）公開パラメータメモリ部２０１
公開パラメータメモリ部２０１は、楕円曲線Ｅの方程式ｙ＾２＝ｘ＾３＋ａ×ｘ＋ｂの変数ａ、ｂ、素数ｐ、楕円曲線Ｅ上のベース点Ｐ、その位数ｑ、楕円曲線Ｅａの方程式ｙ＾２＝ｘ＾３＋ａａ×ｘ＋ｂａのａａ、ｂａ、合成数ｎ、楕円曲線Ｅａ上の点Ｐａのそれぞれをパラメータとして記憶している。ここで、点を記憶するとは、点の座標を記憶することを意味する。
【００６７】
（２）乱数生成部２０２
乱数生成部２０２は、乱数生成部２０２は、２×ｌｅｎ個のｌｅｎビットの乱数ｖ＿（ｉ，ｊ）  （ｉ＝０または１、ｊ＝０，１，…，ｌｅｎ−１）を生成する。
乱数生成部２０２は、１個のｌｅｎビットの乱数ｋｓを生成する（ただし、０＜ｋｓ＜ｑ）。
【００６８】
なお、乱数生成部２０２が生成した乱数ｋｓが秘密鍵となることに注意する。
（３）群演算部２０３
群演算部２０３は、公開パラメータメモリ部２０１に記憶している楕円曲線Ｅのパラメータａ、ｂ、素数ｐ、ベース点Ｐを用いて、乱数ｖ＿（ｉ，ｊ）  （ｉ＝０または１、ｊ＝０，１，…，ｌｅｎ−１）に対応するスカラ倍点ｖ＿（ｉ，ｊ）＊Ｐを計算する。
【００６９】
群演算部２０３は、公開パラメータメモリ部２０１に記憶している楕円曲線Ｅａのパラメータａａ、ｂｂ、合成数ｎ、楕円曲線Ｅａ上の点Ｐａを用いて、乱数ｖ＿（ｉ，ｊ）  （ｉ＝０または１、ｊ＝０，１，…，ｌｅｎ−１）に対応するスカラ倍点ｖ＿（ｉ，ｊ）＊Ｐａを計算する。
群演算部２０３は、生成した各スカラ倍点ｖ＿（ｉ，ｊ）＊Ｐと、スカラ倍点ｖ＿（ｉ，ｊ）＊Ｐａとを用いて、図３にて示すテーブルＴ１０１、Ｔ１０２、・・・、Ｔ１０３を生成する。これにより、群演算部２０３は、２×ｌｅｎ個の元対を生成することになる。
【００７０】
群演算部２０３は、公開パラメータメモリ部２０１に記憶している楕円曲線Ｅａのパラメータａａ、ｂｂ、合成数ｎ、楕円曲線Ｅａ上の点Ｐａを用いて、乱数ｋｓに対するスカラ倍点ＫＳＴ＝ｋｓ＊Ｐａを計算する。
なお、算出されたスカラ倍点ＫＳＴが変換後秘密鍵となることに注意する。
（４）格納処理部２０４
格納処理部２０４は、群演算部２０３にて生成されたテーブルＴ１０１、Ｔ１０２、・・・、Ｔ１０３を署名生成装置１０のテーブルメモリ部１０２に格納する。これにより、格納処理部２０４は、元対（ｖ＿（ｉ，ｊ）＊Ｐ，  ｖ＿（ｉ，ｊ）＊Ｐａ）  （ｉ＝０または１、ｊ＝０，１，…，ｌｅｎ−１）を署名生成装置１０のテーブルメモリ部１０２に格納することができる。
【００７１】
格納処理部２０４は、群演算部２０３にて算出されたＫＳＴ（＝ｋｓ＊Ｐａ）を署名生成装置１０の変換後秘密鍵メモリ部１０５に格納する。
１．５  署名生成装置１０の動作
ここでは、署名生成装置１０にて行われる署名データの生成の動作について説明する。なお、テーブルメモリ部１０２には予めｌｅｎ−１個のテーブルＴ１０１、Ｔ１０２、・・・、Ｔ１０３がテーブル生成装置２０により格納され、変換後秘密鍵メモリ部１０５には予め変換後秘密鍵ＫＳＴがテーブル生成装置２０により格納されているものとする。
【００７２】
（１）動作概要
署名生成装置１０は、プロセッサ１０１により、プログラムメモリ部１０６に記憶している署名生成プログラム１１０から１個ずつコンピュータ命令を読み出し、解釈し、その解釈結果に応じて、テーブルメモリ部１０２、秘密パラメータメモリ部１０３、公開パラメータメモリ部１０４及び変換後秘密鍵メモリ部１０５を読み出しながら、メッセージｍに対する署名データＳを生成する。署名データＳの生成処理の具体的な動作については、後述する。
【００７３】
（２）署名生成処理の動作
ここでは、署名データＳを生成する署名生成処理の動作について図６及び図７にて示す流れ図を用いて説明する。
ハッシュ値生成モジュール１２１は、入力であるメッセージｍをメッセージ受付装置３０から受け付け（ステップＳ１００）、受け付けたメッセージｍのハッシュ値ｈを計算する（ステップＳ１０５）。
【００７４】
乱数生成モジュール１２２は、ｌｅｎビットの正整数（乱数）ｕを生成する（ステップＳ１１０）。
選択モジュール１２３は、乱数ｕのビット表現（ｕ＝ｕ＿０＋ｕ＿１×２＋ｕ＿２×２＾２＋…＋ｕ＿（ｌｅｎ−１）×２＾（ｌｅｎ−１）  （ｉ＝０，１，２，…，ｌｅｎ−１に対しｕ＿ｉ＝０または１））に基づいて、テーブルメモリ部１０２に記憶している元対ＰＰ＿（ｕ＿０，０），ＰＰ＿（ｕ＿１，１），ＰＰ＿（ｕ＿２，２），…，ＰＰ＿（ｕ＿（ｌｅｎ−１），ｌｅｎ−１）を選択する（ステップＳ１１５）。
【００７５】
ランダム元生成モジュール１２４は、選択モジュール１２３で選択したＰＰ＿（ｕ＿ｉ，ｉ）＝（Ｐ＿（ｕ＿ｉ，ｉ），Ｐａ＿（ｕ＿ｉ，ｉ））（ｉ＝０，１，２，…，ｌｅｎ−１）に対し、Ｐ＿（ｕ＿ｉ，ｉ）  （ｉ＝０，１，２，…，ｌｅｎ−１）を公開パラメータメモリ部１０４で記憶している楕円曲線Ｅのパラメータａ、ｂ、素数ｐ、楕円曲線Ｅ上のベース点Ｐを用いて、楕円曲線Ｅ上で加算することにより、Ｐｋ（＝（ｖ＿（ｕ＿０，０）＊Ｐ＋ｖ＿（ｕ＿１，１）＊Ｐ＋・・・＋ｖ＿（ｕ＿ｌｅｎ−１，ｌｅｎ−１）＊Ｐ）を算出する（ステップＳ１２０）。
【００７６】
ランダム元生成モジュール１２４は、公開パラメータメモリ部１０４で記憶している楕円曲線Ｅａのパラメータａａ、ｂａ、合成数ｎを用いて、Ｐａ＿（ｕ＿ｉ，ｉ）  ｍｏｄ  ｎ（ｉ＝１，２，…，ｌｅｎ−１）を楕円曲線Ｅａ上で加算することにより、Ｐａｋ（＝（ｖ＿（ｕ＿０，０）＊Ｐａ＋ｖ＿（ｕ＿１，１）＊Ｐａ＋・・・＋ｖ＿（ｕ＿ｌｅｎ−１，ｌｅｎ−１）＊Ｐａ）を計算する（ステップＳ１２５）。
【００７７】
変換モジュール１２５は、公開パラメータメモリ部１０４で記憶している楕円曲線Ｅａのパラメータａａ、ｂａ、合成数ｎと楕円曲線Ｅａ上の点Ｐａとハッシュ値ｈとを用いて、ｈＰａ＝ｈ＊Ｐａ  ｍｏｄ  ｎを計算する（ステップＳ１３０）。
主要演算モジュール１２６は、ｒ＝ｘ（Ｐｋ）  ｍｏｄ  ｑを計算する（ステップＳ１３５）。ここで、ｘ（Ｐｋ）は、Ｐｋのｘ座標を示す。
【００７８】
主要演算モジュール１２６は、変換後秘密鍵メモリ部１０５で記憶している変換後秘密鍵ＫＳＴと、公開パラメータメモリ部１０４で記憶している楕円曲線Ｅａのパラメータａａ、ｂｂ、合成数ｎを用いて、楕円曲線Ｅａ上でｒ＊ＫＳＴを計算する（ステップＳ１４０）。
主要演算モジュール１２６は、ｈＰａと楕円曲線Ｅａ上の加算を行うことにより、Ｑａ＝ｒ＊ＫＳＴ＋ｈＰａを計算する（ステップＳ１４５）。
【００７９】
逆変換モジュール１２７は、秘密パラメータメモリ部１０３で記憶している素数ｐ１を用いて、Ｐａ  ｍｏｄ  ｐ１に対するＱａの離散対数ｃＱを算出する（ステップＳ１５０）。
逆変換モジュール１２７は、秘密パラメータメモリ部１０３で記憶している素数ｐ１を用いて、Ｐａ  ｍｏｄ  ｐ１に対するＰａｋの離散対数ｃｋを算出する（ステップＳ１５５）。
【００８０】
乗算モジュール１２８は、乱数βを生成する（ステップＳ１６０）。
乗算モジュール１２８は、公開パラメータメモリ部１０４で記憶している楕円曲線Ｅ上のベース点Ｐの位数ｑと、ステップＳ１５０にて算出された離散対数ｃＱと、乱数βとを用いて、ｃＱ’＝ｃＱ×β  ｍｏｄ  ｑを計算する（ステップＳ１６５）。
乗算モジュール１２８は、公開パラメータメモリ部１０４で記憶している楕円曲線Ｅ上のベース点Ｐの位数ｑと、ステップＳ１５５にて算出された離散対数ｃｋと、乱数βとを用いて、ｃｋ’＝ｃｋ×β  ｍｏｄ  ｑを計算する（ステップＳ１７０）。
【００８１】
除算モジュール１２９は、ステップＳ１７０にて算出されたｃｋ’のｍｏｄ  ｑでの逆元であるｃｋｉを計算する（ステップＳ１７５）。ここで、ｃｋｉは、ｃｋｉ×ｃｋ’＝１  ｍｏｄ  ｑを満たす値である。
除算モジュール１２９は、公開パラメータメモリ部１０４で記憶している楕円曲線Ｅ上のベース点Ｐの位数ｑと、ステップＳ１７５にて算出されたｃｋｉと、ステップＳ１６５にて算出されたｃＱ’とを用いて、ｓ＝ｃｋｉ×ｃＱ’  ｍｏｄ  ｑを算出する（ステップＳ１８０）。
【００８２】
署名データ生成モジュール１３０は、ステップＳ１３５にて生成されたｒと、ステップＳ１８０にて生成されたｓを１対とする署名データＳ＝（ｒ，ｓ）を生成する（ステップＳ１８５）。
署名データ生成モジュール１３０は、ハッシュ値生成モジュール１２１が受け付けたメッセージｍと、生成した署名データＳを署名データ送信装置４０へ出力する。
１．６  テーブル生成装置２０の動作
ここでは、テーブル生成装置２０にて行われるテーブル及び変換後秘密鍵の生成の動作について図８にて示す流れ図を用いて説明する。
【００８３】
乱数生成部２０２は、ｌｅｎビットの乱数ｖ＿（ｉ，ｊ）  （ｉ＝０，１、ｊ＝０，１，…，ｌｅｎ−１）を２×ｌｅｎ個生成する（ステップＳ２００）。
乱数生成部２０２は、１個のｌｅｎビットの乱数（秘密鍵）ｋｓを生成する（ステップＳ２０５）。ただし、ｋｓは、０＜ｋｓ＜ｑを満たす数である。
群演算部２０３は、公開パラメータメモリ部２０１に記憶している楕円曲線Ｅのパラメータａ、ｂ、素数ｐ、ベース点Ｐを用いて、乱数ｖ＿（ｉ，ｊ）  （ｉ＝０，１、ｊ＝０，１，…，ｌｅｎ−１）に対応するスカラ倍点ｖ＿（ｉ，ｊ）＊Ｐを計算する（ステップＳ２１０）。
【００８４】
群演算部２０３は、公開パラメータメモリ部２０１に記憶している楕円曲線Ｅａのパラメータａａ、ｂｂ、合成数ｎ、楕円曲線Ｅａ上の点Ｐａを用いて、乱数ｖ＿（ｉ，ｊ）  （ｉ＝０，１、ｊ＝０，１，…，ｌｅｎ−１）に対応するスカラ倍点ｖ＿（ｉ，ｊ）＊Ｐａを計算する（ステップＳ２１５）。
群演算部２０３は、生成した各スカラ倍点ｖ＿（ｉ，ｊ）＊Ｐと、スカラ倍点ｖ＿（ｉ，ｊ）＊Ｐａとを用いて、ｌｅｎ個のテーブルＴ１０１、Ｔ１０２、・・・、Ｔ１０３を生成する（ステップＳ２２０）。
【００８５】
群演算部２０３は、公開パラメータメモリ部２０１に記憶している楕円曲線Ｅａのパラメータａａ、ｂｂ、合成数ｎ、楕円曲線Ｅａ上の点Ｐａを用いて、乱数ｋｓに対するスカラ倍点（変換後秘密鍵）ＫＳＴ＝ｋｓ＊Ｐａを計算する（ステップＳ２２５）。
格納処理部２０４は、ステップＳ２２０にて生成されたテーブルＴ１０１、Ｔ１０２、・・・、Ｔ１０３を署名生成装置１０のテーブルメモリ部１０２に格納し、ステップＳ２２５にて算出されたＫＳＴ（＝ｋｓ＊Ｐａ）を署名生成装置１０の変換後秘密鍵メモリ部１０５に格納する（ステップＳ２３０）。
【００８６】
これにより、格納処理部２０４は、元対（ｖ＿（ｉ，ｊ）＊Ｐ，  ｖ＿（ｉ，ｊ）＊Ｐａ）  （ｉ＝０または１、ｊ＝０，１，…，ｌｅｎ−１）を署名生成装置１０のテーブルメモリ部１０２に格納することができる。
１．７  実施の形態の動作検証
ここでは、上記実施の形態における署名生成プログラム１１０が、従来型の楕円ＤＳＡ署名方式の署名生成にて生成される署名と同一の署名を生成することを以下に示す。
【００８７】
署名生成プログラム１１０では、ランダム元生成モジュール１２４において、ランダムな点Ｐｋを計算している。さらに署名生成プログラム１１０では、ランダム元生成モジュール１２４において、スーパーアノマラス楕円曲線ＥａにおけるＰａｋを計算している。
ここで、テーブルメモリ部１０２の元対に含まれる楕円曲線Ｅ上の点とスーパーアノマラス楕円曲線Ｅａ上の点はそれぞれ、点Ｐ、点Ｐａに対する離散対数が同じ値となっている。すなわち、選択モジュール１２３で元対を選択し、ランダム元生成モジュール１２４では選択した元対に含まれる点をそれぞれの楕円曲線Ｅ、Ｅａ上で加算するため、Ｐに対するＰｋの離散対数と、Ｐａに対するＰａｋの離散対数は同じ値（ここでは、ｖ＿（ｕ＿０，０）＋ｖ＿（ｕ＿１，１）＋・・・＋ｖ＿（ｕ＿ｌｅｎ−１，ｌｅｎ−１）である。）となる。この離散対数を従来型の楕円ＤＳＡ署名方式のステップＳ２にて生成される乱数ｋとみなすことで、署名生成プログラム１１０が生成するＳ＝（ｒ，ｓ）は、従来型の楕円ＤＳＡ署名方式の署名生成にて生成される署名Ｓと同じとなる。
【００８８】
以下、署名生成プログラム１１０が生成するＳ＝（ｒ，ｓ）と、従来型の楕円ＤＳＡ署名方式の署名生成にて生成される署名Ｓとが同一となることを示す。
点Ｐａに対する点Ｑａの離散対数ｃＱについて考える。上述したように、Ｑａ＝ｒ＊ＫＳＴ＋ｈＰａであり、ＫＳＴ＝ｋｓ＊Ｐａ，ｈＰａ＝ｈ＊Ｐａである。これにより、Qa＝（ｒ×ｋｓ＋ｈ）＊Paとなることが分かる。したがって、点Ｐａに対する点Ｑａの離散対数はｃＱは、ｃＱ＝ｒ×ｋｓ＋ｈとなる。また、点Ｐａに対する点Ｐａｋの離散対数はｃｋは、ｃｋ＝ｋとなる。
【００８９】
以下、この理由を示す。
上記にて示すステップＳ３０によりｃｋ１＝Pak  ｍｏｄ  ｐ１，Ｐａ１＝Ｐａ  ｍｏｄ  ｐ１であり、上記にて示すステップＳ３１によりｃｋ１＝ｃｋ＊Ｐａ１であることから、ｃｋ１＝Ｐａｋ  ｍｏｄ  ｐ１  ＝ｃｋ＊Ｐａ  ｍｏｄ  ｐ１  となる。一方、Ｐａｋの算出方法により、Ｐａｋ＝ｋ＊Ｐａ  ｍｏｄ  ｎである。ここで、ｎ＝ｐ１×ｐ２であることから、（Ｐａｋ  ｍｏｄ  ｎ）  ｍｏｄ  ｐ１  ＝Ｐａｋ  ｍｏｄ  ｐ１となり、ｃｋ１＝Ｐａｋ  ｍｏｄ  ｐ１  ＝ｋ＊Ｐａ  ｍｏｄ  ｐ１である。したがって、この式より、ｃｋ１＝ｃｋ＊Ｐａ１＝  ｃｋ＊Ｐａ  ｍｏｄ  ｐ１  ＝ｋ＊Ｐａ  ｍｏｄ  ｐ１となり、この式よりｃｋ＝ｋとなることが分かる。
【００９０】
上記（６−９）にて示すように、ｓ＝ｃｋｉ×ｃＱ’  ｍｏｄ  ｑ  ＝ｃＱ’／ｃｋ’  ｍｏｄ  ｑ  ＝ｃＱ×β／（ｃｋ×β）  ｍｏｄ  ｑ  ＝（ｒ×ｋｓ＋ｈ）／ｋ  ｍｏｄ  ｑ  となるので、除算モジュール１２９は、従来型の楕円ＤＳＡ署名方式の署名生成のステップＳ４で求める値ｓを算出していることになる。
また、署名生成プログラム１１０の主要演算モジュール１２６にて算出される値ｒは、従来型の楕円ＤＳＡ署名方式の署名生成と同じく点Ｐのｋ倍点である。
【００９１】
したがって、主要演算モジュール１２６にて算出される値ｒと、除算モジュール１２９にて算出される値ｓとの組が、従来型の楕円ＤＳＡ署名方式の署名生成にて生成される署名Ｓと同一になる。
以上より、実施の形態における署名生成プログラム１１０は正しく署名生成できることが分かる。
１．８  実施の形態の効果
秘密パラメータメモリ部１０３、署名生成プログラム１１０の逆変換モジュール１２７と乗算モジュール１２８が解析困難な場合に、解析者はｎの因数であるｐ１、ｐ２を知らないため、スーパーアノマラス楕円曲線における離散対数問題を解くことができない。解析者は、変換後秘密鍵ＫＳＴとＰａｋを解析可能であるが、スーパーアノマラス楕円曲線における離散対数問題を解けないため、これらから秘密鍵ｋｓ及びＰａｋの離散対数ｋを求められない。
【００９２】
ここで、Ｐａｋの離散対数ｋを求められないようシステムを設計した理由について、以下で説明する。もし、解析者がｋを知ることができれば、ｒ、ｓ、ｈ及びｑは解析者が知ることができるため、ｓ＝（ｒ×ｋｓ＋ｈ）／ｋ  ｍｏｄ  ｑから、解析者が秘密鍵ｋｓを求めることができてしまう。したがって、Ｐａｋの離散対数ｋは求められないようシステムを設計する必要がある。
【００９３】
また、従来の楕円ＤＳＡ署名方式の署名生成において、秘密鍵ｋｓだけでなく、乱数ｋをも秘密にする必要がある。
なぜなら、値ｈ、ｒ、ｓは、解析者（攻撃者）が知ることができる。さらに、乱数ｋが知られると、ステップＳ４により秘密鍵ｋｓを求めることが可能であるからである。
そこで、本発明は、乱数ｋ及び秘密鍵ｋｓが用いられるステップＳ２及び４において、解析者による解析を困難にしている。
【００９４】
本発明では、上述したように、ステップＳ４の解析を困難にするために、スーパーアノマラス楕円を用いた準同型変換を利用することにより、秘密鍵ｋｓと乱数ｋとをスーパーアノマラス楕円上に点に変換して、解析者が解析できないようにしている。したがって、解析者は秘密鍵ｋｓを知ることができなくなるため、実施の形態における署名生成システムは安全である。
【００９５】
ここで、従来型の楕円ＤＳＡ署名方式と本発明の楕円ＤＳＡ署名方式との対応について図９を用いて説明する。
図９は、本発明の楕円ＤＳＡ署名方式の動作のうち、従来型の楕円ＤＳＡ署名方式の署名生成におけるステップＳ４に対応する動作部分を示す。
図９において破線で囲んだ処理群３１０は、図６にて示すステップＳ１４０に対応している。ここで、処理群３１０は、変換後秘密鍵メモリ部１０５と、ｒ＊ＫＳＴを算出する処理群３０１とから構成されている。
【００９６】
処理群３１１は、ステップＳ１３０に対応している。ここで、処理群３１１は、公開パラメータメモリ部１０４と、ｈＰａを算出する処理群３０２とから構成されている。
処理群３１０及び処理群３１１による結果を加算する処理群３０３は、ステップＳ１４５に対応している。
離散対数問題ｃＱを算出する処理群３０４はステップＳ１５０に対応し、離散対数ｃｋを算出する処理群３０５は、ステップＳ１５５に対応している。
【００９７】
処理群３０４及び３０５の算出結果それぞれにβを乗算する処理群３０６は、ステップＳ１６０からＳ１７０に対応している。
さらには、署名データＳ＝（ｒ，ｓ）に含まれるデータｓを算出する処理群３０７は、ステップＳ１７５、Ｓ１８０に対応している。
処理群３２０は解析可能な領域にて実行され、処理群３２１は、上述したように、処理内容の解析を困難にするために、ハード対策やソフトウェア対策により耐タンパ性を有する領域で実行される。
【００９８】
ここで、上述したように、秘密鍵ｋｓは、ＫＳＴ（＝ｋｓ＊Ｐａ）に予め変換され記憶されており、秘密鍵ｋｓ自体は署名生成を行う際には現れることはないので、解析者は秘密鍵ｋｓを知ることができない。また、乱数ｋは、そのままの値で、解析可能な領域にて現れることはない。乱数ｋは、解析可能な領域では、スーパーアノマラス楕円上に点に変換されているので、解析が困難となる。
【００９９】
また、スーパーアノマラス楕円を用いた準同型変換を用いると、乱数ｋの代わりに、アノマラス楕円Ｅａにおけるｋ＊Ｐが必要になり、さらには、ｋを算出するために、楕円ＤＳＡ署名方式による署名を行う楕円Ｅのｋ＊Ｐｋと、アノマラス楕円Ｅａにおけるｋ＊Ｐａとが必要になる。
そこで、本発明は、テーブルメモリ部１０２、乱数生成モジュール１２２、選択モジュール１２３及びランダム元生成モジュール１２４を用いて、ｋを生成し使用することなくｋ＊Ｐ及びｋ＊Ｐａを算出している。これにより、従来型の楕円ＤＳＡ署名方式のステップＳ２によりＲ（＝ｋ＊Ｐ）を求める際には、乱数ｋが現れているが、本発明では、乱数ｋを出現させることなくＰｋ（＝ｋ＊Ｐ）を算出しているので、Ｐｋの算出時にはｋを求めることができない。また、算出結果からｋを求めることも困難にしている。
【０１００】
従来、秘密鍵ｋｓ及び乱数ｋを解析困難にするためには、ステップＳ２及びステップＳ４の実行において、ハード対策を施す必要がある。しかしながら、本発明では、離散対数問題を解き、解を用いる動作部分（処理群３０４、３０５、及び３０６）に対して解析が困難になるようにハード対策を施せばよい。これにより、ハード対策を施す部分が限定されるので、署名生成装置の実装が従来より容易となる。
【０１０１】
また、図１０において、従来の楕円ＤＳＡ署名方式の署名生成による各ステップと、本発明の署名生成装置１０の構成要素による動作との対応を示す。なお、各構成要素間における接続線は、図２及び図４に示しているので、図１０では省略している。
ハッシュ値生成モジュール１２１により、ステップＳ１と同等の動作が実現できる。
ステップＳ２には、テーブルメモリ部１０２、乱数生成モジュール１２２、選択モジュール１２３及びランダム元生成モジュール１２４からなる構成群４０１により、ステップＳ２と同等の動作が実現できる。
【０１０２】
主要演算モジュール１２６にて行われる値ｒの算出により、ステップＳ３と同等の動作が実現できる。
変換モジュール１２５、主要演算モジュール１２６、逆変換モジュール１２７、乗算モジュール１２８及び除算モジュール１２９からなる構成群４０２により、ステップＳ４と同等の動作が実現できる。
【０１０３】
署名データ生成モジュール１３０により、ステップＳ５と同等の動作が実現できる。
また、秘密パラメータメモリ部１０３、公開パラメータメモリ部１０４、変換後秘密鍵メモリ部１０５は、各モジュールの動作に応じて利用される。
また、逆変換モジュール１２７及び乗算モジュール１２８からなる構成群４０２は、上述したように、解析困難にするためにハード対策を施す必要がある部分である。
【０１０４】
なお、解析困難にするためにハード対策を施すとしたが、これに限定されない。解析を困難にする対策であれば、ハード対策に限らず他の対策でもよい。
１．９  変形例
上記に説明した実施の形態は、本発明の実施の一例であり、本発明はこの実施の形態に何ら限定されるものではなく、その旨を逸脱しない範囲において種々なる態様で実施し得るものである。例えば、以下のような場合も本発明に含まれる。
【０１０５】
（１）実施の形態において、ｐ、ｑ、ｕのビット数ｌｅｎを１６０としているが、これに限らない。１６０より大きい、例えば１９２や２２４としてもよい。また、ｎのビット数を１０２４としているが、これに限らない。１０２４より大きい、例えば２０４８や４０９６としてもよい。
（２）実施の形態では、署名生成プログラムの形態であるが、これを暗号化プログラムや復号化プログラムの形態としてもよい。
【０１０６】
（３）実施の形態においては、第２の群として楕円曲線Ｅａ上の群を使用したが、これに限定されない。第２の群として剰余整数環の乗法群や、その他の群を利用するとしてもよい。
また、実施の形態では楕円曲線のスカラ倍演算を行って、整数を変換したが、これに限定されない。整数を変換する演算として、群の冪演算を用いてもよい。ここで、冪演算とは、群の基本演算、すなわち、剰余整数環では乗算、楕円曲線上の群では楕円曲線加算を、整数回行った結果を求める演算である。したがって、剰余整数環の乗法群の冪演算は冪乗演算、楕円曲線上の群の冪演算は楕円曲線のスカラ倍演算である。実施の形態では、第２の群Ｇａは、Ｅａ（ＧＦ（ｐ１））×Ｅａ（ＧＦ（ｐ２））であり、離散対数問題はこの「部分群」である、Ｅａ（ＧＦ（ｐ１））で解いているが、剰余整数環Ｚ／ｎＺの乗法群やその他の群の「部分群」において離散対数問題を解いてもよい。また、第２の群を特許文献３における剰余整数環の乗法群としてもよい。
【０１０７】
（４）上記実施の形態において、第２の群Ｇａは、合成数ｎ（＝ｐ１×ｐ２）に対するＺ／ｎＺ上の楕円曲線上の群としたが、これに限定されない。なお、ｐ１，ｐ２は互いに異なるに素数である。
第２の群Ｇａは、合成数ｎ（＝ｐ１＾ｍ×ｐ２）に対する対するＺ／ｎＺ上の楕円曲線上の群であってもよい。だたし、ｍは１以上の整数である。ここで、ｐ１＾ｍはｐ１のｍ乗を示す。
【０１０８】
または、第２の群Ｇａは、合成数ｎ（＝ｐ１＾ｍ×ｐ２）に対する対するＺ／ｎＺ上の乗法群であってもよい。だたし、ｍは１以上の整数である。このとき、第２の群の部分群は、Ｚ／ｐ１＾ｍ  Ｚ上の乗法群としてもよい。
（５）上記実施の形態において、署名生成装置１０は、ランダム元生成モジュール１２４にて２つのランダム元（Ｐｋ、Ｐａｋ）を生成したが、これに限定されない。
【０１０９】
ランダム元生成モジュール１２４は、１つのランダム元（例えば、Ｐｋ）のみを生成してもよい。この場合、署名生成装置１０は、２×ｌｅｎ個の元対の代わりに２×ｌｅｎ個のＰ＿（ｉ，ｊ）を格納している（ｉ＝０，１、ｊ＝０，１，・・・，ｌｅｎ−１）。署名生成装置１０は、ｌｅｎビットの乱数ｕを生成すると、生成した乱数ｕを用いて第１の群Ｇの元Ｐｋを算出する。算出方法は、上記実施の形態にて示す方法と同様であるため、ここでの説明は省略する。これにより、署名生成装置１０は、乱数ｋを第三者に知られることがないように第１の群Ｇの元Ｐｋを算出することができる。
【０１１０】
または、ランダム元生成モジュール１２４は、２個以上のランダム元（Ｐｋ、Ｐａｋ１、Ｐａｋ２、・・・、Ｐａｋｎ）を生成してもよい（ｎは、１以上の整数）。
（６）上記実施の形態において、署名生成装置１０における選択モジュール１２３は、乱数生成モジュール１２２にて生成された正整数ｕをビット数がｌｅｎビットからなるビット表現に変換し、各ビットに対応する元対を選択したが、これに限定されない。
【０１１１】
選択モジュール１２３は、乱数生成モジュール１２２にて生成された正整数ｕから直接元対を求めてもよい。
このとき、テーブルメモリ部１０２は、正整数１、２、３、・・・に対して、元対（ｖ＿１＊Ｐ，ｖ＿１＊Ｐａ）、（ｖ＿２＊Ｐ，ｖ＿２＊Ｐａ）、（ｖ＿３＊Ｐ，ｖ＿３＊Ｐａ）、・・・を記憶している。
【０１１２】
選択モジュール１２３は、乱数生成モジュール１２２にて生成された正整数ｕに対応する元対（ｖ＿ｕ＊Ｐ，ｖ＿ｕ＊Ｐａ）をテーブルメモリ部１０２が記憶しているテーブルから選択する。
ランダム元生成モジュール１２４は、選択された元対（ｖ＿ｕ＊Ｐ，ｖ＿ｕ＊Ｐａ）に対して、Ｐｋ＝ｖ＿ｕ＊Ｐ、Ｐａｋ＝ｖ＿ｕ＊Ｐａとする。
【０１１３】
以降の動作は、実施の形態と同様であるので、ここでの説明は省略する。
以下、別の例を説明する。
または、テーブルメモリ部１０２は、元対（ｖ＿１＊Ｐ，ｖ＿１＊Ｐａ）、（ｖ＿２＊Ｐ，ｖ＿２＊Ｐａ）、（ｖ＿３＊Ｐ，ｖ＿３＊Ｐａ）、・・・、（ｖ＿ｔ＊Ｐ，ｖ＿ｔ＊Ｐａ）を記憶している。ｔは１以上の整数である。
【０１１４】
選択モジュール１２３は、以下のようにして１個以上の元対を選択する。
選択モジュール１２３は、正整数ｕがｔ以下である場合には、元対（ｖ＿ｕ＊Ｐ，ｖ＿ｕ＊Ｐａ）をテーブルメモリ部１０２が記憶しているテーブルから選択する。
選択モジュール１２３は、正整数ｕがｔより大きい場合には、ｕ＝ｔ１＋ｔ２＋・・・＋ｔｐとなるｔ１、ｔ２、・・・、ｔｐを取得する。ここで、ｐは、２以上の整数であり、ｔ１、ｔ２、・・・、ｔｐのそれぞれは、ｔ以下の数である。選択モジュール１２３は、取得したｔ１、ｔ２、・・・、ｔｐそれぞれに対応する元対（ｖ＿ｔ１＊Ｐ，ｖ＿ｔ１＊Ｐａ）、（ｖ＿ｔ２＊Ｐ，ｖ＿ｔ２＊Ｐａ）、・・・、（ｖ＿ｔｐ＊Ｐ，ｖ＿ｔｐ＊Ｐａ）をテーブルメモリ部１０２が記憶しているテーブルから選択する。
【０１１５】
ランダム元生成モジュール１２４は、選択された元対が１個である場合には、選択された元対（ｖ＿ｕ＊Ｐ，ｖ＿ｕ＊Ｐａ）に対して、Ｐｋ＝ｖ＿ｕ＊Ｐ、Ｐａｋ＝ｖ＿ｕ＊Ｐａとする。
ランダム元生成モジュール１２４は、選択された元対が２個以上である場合には、選択された元対（ｖ＿ｔ１＊Ｐ，ｖ＿ｔ１＊Ｐａ）、（ｖ＿ｔ２＊Ｐ，ｖ＿ｔ２＊Ｐａ）、・・・、（ｖ＿ｔｐ＊Ｐ，ｖ＿ｔｐ＊Ｐａ）に対して、ｖ＿ｔ１＊Ｐ、ｖ＿ｔ２＊Ｐ、・・・、ｖ＿ｔｐ＊Ｐを楕円曲線Ｅ上で加算することにより、Ｐｋを算出し、ｖ＿ｔ１＊Ｐａ、ｖ＿ｔ２＊Ｐａ、・・・、ｖ＿ｔｐ＊Ｐａを楕円曲線Ｅａ上で加算することにより、Ｐａｋを計算する。
【０１１６】
以降の動作は、実施の形態と同様であるので、ここでの説明は省略する。
（７）上記実施の形態において、ランダム元生成モジュール１２４は、選択モジュール１２３にて選択されたｌｅｎ個全ての元対を用いて、Ｐｋ及びＰａｋを算出したが、これに限定されない。
ランダム元生成モジュール１２４は、選択されたｌｅｎ個の元対からｗ個の元対を選択し、選択したｗ個の元対を用いてＰｋ及びＰａｋを算出してもよい。ここで、ｗは、２以上ｌｅｎ以下の数である。
【０１１７】
例えば、数ｗは予め与えられており、ランダム元生成モジュール１２４は、選択されたｌｅｎ個の元対からランダムにｗ個の元対を選択する。
また別の例として、ランダム元生成モジュール１２４は、選択されたｌｅｎ個の元対からビット値「１」に対応するｗ個の元対のみを選択してもよいし、ビット値「０」に対応するｗ個の元対のみを選択してもよい。
【０１１８】
または、ランダム元生成モジュール１２４は、ビット値が１であるビットの個数とビット値が「０」であるビットの個数とを比較し、個数が多いほうのビット値に対応するｗ個の元対のみを選択してもよい。
または、数ｗは予め与えられており、ランダム元生成モジュール１２４は、選択されたｌｅｎ個の元対から、上位ビットｗ個分の元対を選択する。なお、ランダム元生成モジュール１２４は、選択されたｌｅｎ個の元対から、下位ビットｗ個分の元対を選択してもよい。
【０１１９】
ここでは、ｗは、２以上ｌｅｎ以下の数であるとしたが、ｗは、１以上ｌｅｎ以下の数であってもよい。ｗ＝１の場合、ランダム元生成モジュール１２４は、選択された元対（ｖ＿ｕ＊Ｐ，ｖ＿ｕ＊Ｐａ）に対して、Ｐｋ＝ｖ＿ｕ＊Ｐ、Ｐａｋ＝ｖ＿ｕ＊Ｐａとする。
（８）本発明における分解組とは、上記実施の形態にて示すテーブルメモリ部１０２の記憶内容としてもよいし、正整数ｕ毎に対する複数の分解対（つまり、元対）、すなわち、正整数ｕの各ビットに対して選択された分解対の組み合わせとしてもよい。
【０１２０】
（９）上記実施の形態において、署名生成は、署名生成プログラムにて生成されるとしたが、これに限定されない。
署名生成は、署名を生成するハードウェアにより生成されるとしてもよい。
つまり、署名生成プログラムに含まれる各モジュールは、上記にて説明した機能を達成する手段からなるとしてもよい。
【０１２１】
（１０）上記の各装置は、具体的には、マイクロプロセッサ、ＲＯＭ、ＲＡＭ、ハードディスクユニット、ディスプレイユニット、キーボード、マウスなどから構成されるコンピュータシステムである。前記ＲＡＭまたはハードディスクユニットには、コンピュータプログラムが記憶されている。前記マイクロプロセッサが、前記コンピュータプログラムにしたがって動作することにより、各装置は、その機能を達成する。ここでコンピュータプログラムは、所定の機能を達成するために、コンピュータに対する指令を示す命令コードが複数個組み合わされて構成されたものである。
【０１２２】
（１１）上記の各装置を構成する構成要素の一部または全部は、１個のシステムＬＳＩ（Ｌａｒｇｅ  Ｓｃａｌｅ  Ｉｎｔｅｇｒａｔｉｏｎ：大規模集積回路）から構成されているとしてもよい。システムＬＳＩは、複数の構成部を１個のチップ上に集積して製造された超多機能ＬＳＩであり、具体的には、マイクロプロセッサ、ＲＯＭ、ＲＡＭなどを含んで構成されるコンピュータシステムである。前記ＲＡＭには、コンピュータプログラムが記憶されている。前記マイクロプロセッサが、前記コンピュータプログラムにしたがって動作することにより、システムＬＳＩは、その機能を達成する。
【０１２３】
（１２）上記の各装置を構成する構成要素の一部または全部は、各装置に脱着可能なＩＣカードまたは単体のモジュールから構成されているとしてもよい。前記ＩＣカードまたは前記モジュールは、マイクロプロセッサ、ＲＯＭ、ＲＡＭなどから構成されるコンピュータシステムである。前記ＩＣカードまたは前記モジュールは、上記の超多機能ＬＳＩを含むとしてもよい。マイクロプロセッサが、コンピュータプログラムにしたがって動作することにより、前記ＩＣカードまたは前記モジュールは、その機能を達成する。このＩＣカードまたはこのモジュールは、耐タンパ性を有するとしてもよい。
【０１２４】
（１３）本発明は、上記に示す方法であるとしてもよい。また、これらの方法をコンピュータにより実現するコンピュータプログラムであるとしてもよいし、前記コンピュータプログラムからなるディジタル信号であるとしてもよい。
また、本発明は、前記コンピュータプログラムまたは前記ディジタル信号をコンピュータ読み取り可能な記録媒体、例えば、フレキシブルディスク、ハードディスク、ＣＤ−ＲＯＭ、ＭＯ、ＤＶＤ、ＤＶＤ−ＲＯＭ、ＤＶＤ−ＲＡＭ、ＢＤ（Ｂｌｕ−ｒａｙ  Ｄｉｓｃ）、半導体メモリなどに記録したものとしてもよい。また、これらの記録媒体に記録されている前記コンピュータプログラムまたは前記ディジタル信号であるとしてもよい。
【０１２５】
また、本発明は、前記コンピュータプログラムまたは前記ディジタル信号を、電気通信回線、無線または有線通信回線、インターネットを代表とするネットワーク、データ放送等を経由して伝送するものとしてもよい。
また、本発明は、マイクロプロセッサとメモリを備えたコンピュータシステムであって、前記メモリは、上記コンピュータプログラムを記憶しており、前記マイクロプロセッサは、前記コンピュータプログラムにしたがって動作するとしてもよい。
【０１２６】
また、前記プログラムまたは前記ディジタル信号を前記記録媒体に記録して移送することにより、または前記プログラムまたは前記ディジタル信号を前記ネットワーク等を経由して移送することにより、独立した他のコンピュータシステムにより実施するとしてもよい。
（１４）これらの実施の形態及び変形例の組合せであってもよい。
２．まとめ
本発明は、有限体上や楕円曲線上における離散対数問題を安全性の根拠とする署名方式（例えば、ＤＳＡ署名方式やＥＣＤＳＡ署名方式）を実装したプログラムを、攻撃者が解析困難にするソースコード難読化方法を提供することを目的とする。
【０１２７】
以下に、本発明における特徴を以下に示す。
（１）本発明は、秘密鍵を用いて、メッセージに対するディジタル署名を生成する署名生成装置に実行させる署名生成プログラムであって、前記署名生成装置は、第１の群Ｇに属する第１の元と第２の群Ｇａに属する第２の元との対である元対を複数個記憶しているテーブルメモリ部と、前記署名生成プログラムを記憶しているプログラムメモリ部と、前記プログラムメモリ部に記憶されている前記署名生成プログラムから１個ずつコンピュータ命令を読み出し、解釈し、その解釈結果に応じて動作するプロセッサとを備え、前記署名生成プログラムは、第１の整数を生成する整数生成モジュールと、前記第１の整数に基づいて、前記テーブルメモリ部で記憶している複数の前記元対の中から、複数の前記元対を選択し、出力する選択モジュールと、前記選択モジュールが出力した複数の前記対を使用して、前記第１の群Ｇに属する第３の元と前記第２の群Ｇａに属する第４の元を計算する群演算モジュールとを含み、前記第１の元と前記第２の元はそれぞれ、前記第１の群Ｇに属する予め与えられた元である第１の基本元Ｐと、前記第２の群Ｇａに属する予め与えられた元である第２の基本元Ｐａと、予め与えられた正整数である冪数に対して、前記冪数を冪とした前記第１の基本元Ｐの前記第１の群Ｇにおける冪演算を行うことで得られる元と、前記冪数を冪とした前記第２の基本元Ｐａの前記第２の群Ｇａにおける冪演算を行うことで得られる元であることを特徴とする。
【０１２８】
（２）上記（１）の署名生成プログラムにおいて、前記選択モジュールは、前記第１の整数のビット値ごとに一つの前記対を選択するとしてもよい。
（３）上記（２）の署名生成プログラムにおいて、前記第３の元は、前記選択モジュールが選択した前記対の個々に含まれる前記第１の群Ｇに属する元のすべてに対して、前記第１の群Ｇの基本演算を行った結果得られる前記第１の群Ｇの元であり、前記第４の元は、前記選択モジュールが選択した前記対の個々に含まれる前記第２の群Ｇａに属する元のすべてに対して、前記第２の群Ｇａの基本演算を行った結果得られる前記第２の群Ｇａの元であるとしてもよい。
【０１２９】
（４）上記（１）から（３）のいずれかに記載の署名生成プログラムにおいて、前記署名生成プログラムはさらに、前記第２の群Ｇａ上の冪演算を行うことにより、整数を前記第２の群に属する元に変換する変換モジュールと、前記第２の群Ｇａ上の基本演算を行う主要演算モジュールと、前記第２の群Ｇａまたは、前記第２の群Ｇａが真に含む前記第２の群Ｇａの部分群Ｓａにおける前記変換モジュールで行う変換の逆変換を行う逆変換モジュールとを含むとしてもいよい。
【０１３０】
（５）上記（１）から（４）のいずれかに記載の署名生成プログラムにおいて、前記署名生成装置はさらに、前記秘密鍵と前記第２の基本元から生成される前記第２の群に属する元である変換後秘密鍵を記憶している変換後秘密鍵メモリ部を備え、前記署名生成プログラムはさらに、前記変換後秘密鍵メモリ部に記憶されている変換後秘密鍵を用いて、前記第２の群Ｇａの冪演算を行う変換後秘密鍵演算モジュールとを含むとしてもよい。
【０１３１】
（６）上記（１）から（５）のいずれかに記載の署名生成プログラムにおいて、前記第１の群Ｇ及び前記第２の群Ｇａは、剰余整数環の乗法群であるとしてもよい。
（７）上記（１）に記載の署名生成プログラムにおいて、前記第２の群Ｇａは、２つの素数ｐ、ｑと正整数ｍを用いて表されるｎ＝ｐ＾ｍ×ｑに対し、Ｚ／ｎＺの乗法群であるとしてもよい（ただし、ｘ＾ｙはｘのｙ乗を示す）。
【０１３２】
（８）上記（７）に記載の署名生成プログラムにおいて、前記部分群Ｓａは、Ｚ／ｐ＾ｍ  Ｚの乗法群であるとしてもよい。
（９）上記（８）に記載の署名生成プログラムにおいて、前記正整数ｍは２であるとしてもよい。
（１０）上記（１）から（５）のいずれかに記載の署名生成プログラムにおいて、前記第１の群Ｇは楕円曲線の群であり、前記部分群Ｓａは、アノマラス楕円曲線の群であるとしてもよい。
【０１３３】
（１１）上記（１）から（５）のいずれかに記載の署名生成プログラムにおいて、前記第２の群Ｇａは、二つのアノマラス楕円曲線の群の直積であるとしてもよい。
（１２）上記（１）から（５）、（１１）及び（１２）のいずれかに記載の署名生成プログラムにおいて、前記逆変換モジュールは、前記第２の群Ｇａに属する元を前記部分群Ｓａに属する元に還元する還元手段を備えるとしてもよい。
【０１３４】
（１３）本発明は、群の演算を行う演算装置に実行させる演算プログラムであって、前記演算装置は、第１の群Ｇに属する第１の元と第２の群Ｇａに属する第２の元との対を複数個記憶しているテーブルメモリ部と、前記署名生成プログラムを記憶しているプログラムメモリ部と、前記プログラムメモリ部に記憶されている前記署名生成プログラムから１個ずつコンピュータ命令を読み出し、解釈し、その解釈結果に応じて動作するプロセッサとを備え、前記演算プログラムは、第１の整数を生成する整数生成モジュールと、前記第１の整数に基づいて、前記テーブルメモリ部で記憶している複数の前記対の中から、複数の前記対を選択する選択モジュールと、前記選択モジュールが選択した複数の前記対を使用して、前記第１の群Ｇに属する第３の元と前記第２の群Ｇａに属する第４の元を計算する群演算モジュールとを含み、前記第１の元と前記第２の元はそれぞれ、予め与えられた前記第１の群Ｇに属する元である第１の基本元Ｐと、予め与えられた前記第２の群Ｇａに属する元である第２の基本元Ｐａと、予め与えられた正整数である冪数に対して、前記冪数を冪とした前記第１の基本元Ｐの前記第１の群Ｇにおける冪演算を行うことで得られる元と、前記冪数を冪とした前記第２の基本元Ｐａの前記第２の群Ｇａにおける冪演算を行うことで得られる元であることを特徴とする。
【０１３５】
（１４）本発明は、秘密鍵を用いて、メッセージに対するディジタル署名を生成する署名生成装置であって、第１の群Ｇに属する第１の元と第２の群Ｇａに属する第２の元との対を複数個記憶しているテーブルメモリ部と、第１の整数を生成する整数生成部と、前記第１の整数に基づいて、前記テーブルメモリ部で記憶している複数の前記対の中から、複数の前記対を選択する選択部と、前記選択部が選択した複数の前記対を使用して、前記第１の群Ｇに属する第３の元と前記第２の群Ｇａに属する第４の元を計算する群演算部とを備え、前記第１の元と前記第２の元はそれぞれ、予め与えられた前記第１の群Ｇに属する元である第１の基本元Ｐと、予め与えられた前記第２の群Ｇａに属する元である第２の基本元Ｐａと、予め与えられた正整数である冪数に対して、前記冪数を冪とした前記第１の基本元Ｐの前記第１の群Ｇにおける冪演算を行うことで得られる元と、前記冪数を冪とした前記第２の基本元Ｐａの前記第２の群Ｇａにおける冪演算を行うことで得られる元であることを特徴とする。
【０１３６】
（１５）上記（１４）に記載の署名生成装置において、前記選択部は、前記第１の整数のビット値ごとに一つの前記対を選択するとしてもよい。
（１６）上記（１４）または（１５）に記載の署名生成装置において、前記第３の元は、前記選択部が選択した前記対の個々に含まれる前記第１の群Ｇに属する元のすべてに対して、前記第１の群Ｇの基本演算を行った結果得られる前記第１の群Ｇの元であり、前記第４の元は、前記選択部が選択した前記対の個々に含まれる前記第２の群Ｇａに属する元のすべてに対して、前記第２の群Ｇａの基本演算を行った結果得られる前記第２の群Ｇａの元であるとしてもよい。
【０１３７】
（１７）上記にて示す署名生成プログラムにおける署名方式は、有限体上や楕円曲線上における離散対数問題を安全性の根拠としているので、攻撃者が解析困難にすることができ、その価値は大きい。
また、上記にて示す署名生成装置は、有限体上や楕円曲線上における離散対数問題を安全性の根拠とする署名方式にて署名生成を行うので、攻撃者が解析困難にすることができ、その価値は大きい。
【０１３８】
（１８）また、本発明は、群Ｇ上の離散対数問題を安全性の根拠として、群Ｇ上の基本元Ｐについて基本演算を複数回繰り返す冪演算を施す演算装置であって、複数の数の各々に分解組が予め対応付けられており、各分解組は複数の分解値を含み、各分解値は基本元Ｐについて任意の正整数を冪とする冪演算が施されて算出された群Ｇ上の元であり、前記演算装置は、前記複数の分解組を記憶する分解対記憶手段と、前記複数の数からランダムに数ｕを選択し、選択した数ｕに対応する分解組を前記分解値記憶手段から選択する選択手段と、選択された分解組に含まれる全ての分解値について、前記群Ｇの基本演算を施して、冪乗元を生成する生成手段とを備えることを特徴とする。
【０１３９】
（１９）以上説明したように、本発明によると、演算に使用する値の隠蔽だけでなく、演算そのものを隠蔽することができる。
【産業上の利用可能性】
【０１４０】
本発明を構成する各装置、各方法及びコンピュータプログラムは、情報を安全かつ確実に扱う必要があるあらゆる産業において、経営的に、また継続的及び反復的に使用することができる。また、本発明を構成する各装置、各方法及び各コンピュータプログラムは、電器機器製造産業において、経営的に、また継続的及び反復的に、製造し、販売することができる。
【図面の簡単な説明】
【０１４１】
【図１】署名生成システム１の概要を示すブロック図である。
【図２】署名生成装置１０の構成を示すブロック図である。
【図３】テーブルメモリ部１０２に格納している各テーブルのデータ構造の一例を示す図である。
【図４】署名生成プログラム１１０に含まれる各モジュールを示す図である。
【図５】テーブル生成装置２０の構成を示すブロック図である。
【図６】署名生成処理の動作を示す流れ図である。図７へ続く。
【図７】署名生成処理の動作を示す流れ図である。図６から続く。
【図８】テーブル生成装置２０の動作を示す流れ図である。
【図９】本発明において、値ｒ、ｈから値ｓ（＝（ｒ×ｋｓ＋ｈ）／ｋ  ｍｏｄ  ｑ）を生成する際の動作の概要を示す図である。
【図１０】本発明のＤＳＡ楕円署名方式の特徴部分を示す図である。
【符号の説明】
【０１４２】
１    署名生成システム
１０    署名生成装置
２０    テーブル生成装置
３０    メッセージ受付装置
４０    署名データ送信装置
５０    署名データ受信装置
６０    インターネット
１０１    プロセッサ
１０２    テーブルメモリ部
１０３    秘密パラメータメモリ部
１０４    公開パラメータメモリ部
１０５    変換後秘密鍵メモリ部
１０６    プログラムメモリ部
１１０    署名生成プログラム
１２１    ハッシュ値生成モジュール
１２２    乱数生成モジュール
１２３    選択モジュール
１２４    ランダム元生成モジュール
１２５    変換モジュール
１２６    主要演算モジュール
１２７    逆変換モジュール
１２８    乗算モジュール
１２９    除算モジュール
１３０    署名データ生成モジュール
２０１    公開パラメータメモリ部
２０２    乱数生成部
２０３    群演算部
２０４    格納処理部
【手続補正３】
【補正対象書類名】図面
【補正対象項目名】全図
【補正方法】変更
【補正の内容】
【図１】
2007074836.tif 000013
【図２】
2007074836.tif 000014
【図３】
2007074836.tif 000015
【図４】
2007074836.tif 000016
【図５】
2007074836.tif 000017
【図６】
2007074836.tif 000018
【図７】
2007074836.tif 000019
【図８】
2007074836.tif 000020
【図９】
2007074836.tif 000021
【図１０】
2007074836.tif 000022
【国際調査報告】
2007074836.tif 000023
2007074836.tif 000024
2007074836.tif 000025