(57)【特許請求の範囲】
【請求項１】
（ａ）曲線の複雑さの度合いを指定する2つの異なる素数a、b、および、使用したい暗号鍵のサイズnを入力する入力装置と、
（ｂ）前記入力手段に入力された素数a、素数b、暗号鍵のサイズnをそれぞれ記憶するa記憶手段、b記憶手段、および、n記憶手段と、
（ｃ）前記a記憶手段、前記b記憶手段からそれぞれ素数a、素数bを取得し、円のab分体におけるスティッケルバーガー要素ωを演算するスティッケルバーガー要素計算装置と、
（ｄ）前記スティッケルバーガー要素計算装置により演算されたスティッケルバーガー要素ωを記憶するω記憶手段と、
（ｅ）前記a記憶手段、前記b記憶手段、前記n記憶手段、前記ω記憶手段からそれぞれ素数a、素数b、暗号鍵のサイズn、スティッケルバーガー要素ωを取得し、2つの異なる素数a、素数bに対するヤコビ和候補値jおよびヤコビ和候補値jに対応する素数pを演算するヤコビ和候補値計算装置と、
（ｆ）前記ヤコビ和候補値計算装置により演算された素数p、ヤコビ和候補値jをそれぞれ記憶するp記憶手段、およびj記憶手段と、
（ｇ）前記a記憶手段、前記b記憶手段、前記j記憶手段から、それぞれ素数a、素数b、ヤコビ和候補値jを取得し、素数a、素数bで指定される代数曲線のヤコビアン群の位数の複数の候補値からなる集合Hを演算する位数候補値計算装置と、
（ｈ）前記位数候補値計算装置により演算された集合Hを記憶するH記憶手段と、
（ｉ）前記H記憶手段から集合Hを取得し、集合Hの中から概素数性等の安全性条件を満たす候補値hを検索する安全性判定装置と、
（ｊ）前記安全性判定装置により検索された候補値hを記憶するh記憶手段と、
（ｋ）前記a記憶手段、前記b記憶手段、前記p記憶手段、前記h記憶手段からそれぞれ素数a、素数b、素数p、候補値hを取得し、素数a、素数b、素数pで指定される代数曲線でそのヤコビアン群の位数が候補値hと一致する代数曲線のパラメータを演算するパラメータ決定装置と、
（ｌ）前記パラメータ決定装置で演算された代数曲線のパラメータを出力する出力装置と、
を備えたことを特徴とするαYa +βXb + 1 = 0という形の定義方程式をもつ代数曲線暗号における安全なパラメータの生成装置。
【請求項２】
前記a記憶手段、前記b記憶手段からそれぞれ素数a、素数bを取得し、式ω = Σt [<t/a> + <t/b>] σ_{-t-1}（tはabを法とする既約剰余類の代表系を走り、[λ]は有理数λを超えない最大の整数を表し、<λ>は有理数λの小数部分λ-[λ]を表し、σtは円のab分体におけるガロア写像ζ → ζtを表す(ζは1の原始ab乗根)）を用いてスティッケルバーガー要素ωを演算する前記スティッケルバーガー要素計算装置を備えることを特徴とする請求項１記載のαYa +βXb + 1 = 0という形の定義方程式をもつ代数曲線暗号における安全なパラメータの生成装置。
【請求項３】
前記a記憶手段、前記b記憶手段、前記n記憶手段、前記ω記憶手段からそれぞれ素数a、素数b、暗号鍵のサイズn、スティッケルバーガー要素ωを取得し、１の原始ab乗根で生成される円分体Kの素イデアルを生成する代数的整数γで、その絶対ノルムが2n/(a-1)(b-1)程度のビット長の素数pとなるαをランダムに生成し、式j = γωを用いてヤコビ和候補値jを演算する前記ヤコビ和候補値計算装置を備えることを特徴とする請求項１または２記載のαYa +βXb + 1 = 0という形の定義方程式をもつ代数曲線暗号における安全なパラメータの生成装置。
【請求項４】
前記a記憶手段、前記b記憶手段、前記j記憶手段からそれぞれ素数a、素数b、ヤコビ和候補値jを取得し、１以上2ab以下の整数である各kに対して、ζを１の原始ab乗根とするとき、式 hk = NormK|Q(１+ (-ζ)k j)（Norm_{K|Q}は、円のab分体Kにおけるノルム写像）を用いて、パラメータa、bで指定される代数曲線のヤコビアン群の位数の候補値hkを演算し、候補値の集合H={h1、h2、．．．、h2ab}を演算する前記位数候補値計算装置を備えることを特徴とする請求項１、２、または３記載のαYa +βXb + 1 = 0という形の定義方程式をもつ代数曲線暗号における安全なパラメータの生成装置。
【請求項５】
前記a記憶手段、前記b記憶手段、前記p記憶手段、前記h記憶手段からそれぞれ素数a、素数b、素数p、候補値hを取得し、素数pを法とする１の原始a乗根ζaおよび１の原始b乗根ζbを求め、１以上a以下の各整数l、および１以上b以下の各整数mに対して、式ζal Ya + ζbm Xb +１=０で定義される代数曲線上のランダムな点Gを生成し、点Gの表すヤコビアン群における要素のh倍を計算し、結果がヤコビアン群における単位元に等しいならば、素数a、素数bで指定される代数曲線でそのヤコビアン群の位数が候補値hと一致する代数曲線のパラメータとしてp、ζalおよびζbmを出力する前記パラメータ決定装置を備えることを特徴とする請求項１、２、３または４記載のαYa +βXb + 1 = 0という形の定義方程式をもつ代数曲線暗号における安全なパラメータの生成装置。
【請求項６】
（ａ）入力装置が、曲線の複雑さの度合いを指定する2つの異なる素数a、b、および、使用したい暗号鍵のサイズnを入力する手順と、
（ｂ）a記憶手段、b記憶手段、および、n記憶手段が、それぞれ、前記入力手段に入力された素数a、素数b、暗号鍵のサイズnを記憶する手順と、
（ｃ）スティッケルバーガー要素計算装置が、前記a記憶手段、前記b記憶手段からそれぞれ素数a、素数bを取得し、円のab分体におけるスティッケルバーガー要素ωを演算する手順と、
（ｄ）ω記憶手段が、前記スティッケルバーガー要素計算装置により演算されたスティッケルバーガー要素ωを記憶する手順と、
（ｅ）ヤコビ和候補値計算装置が、前記a記憶手段、前記b記憶手段、前記n記憶手段、前記ω記憶手段からそれぞれ素数a、素数b、暗号鍵のサイズn、スティッケルバーガー要素ωを取得し、2つの異なる素数a、素数bに対するヤコビ和候補値jおよびヤコビ和候補値jに対応する素数pを演算する手順と、
（ｆ）p記憶手段、およびj記憶手段が、それぞれ、前記ヤコビ和候補値計算装置により演算された素数p、ヤコビ和候補値jを記憶する手順と、
（ｇ）位数候補値計算装置が、前記a記憶手段、前記b記憶手段、前記j記憶手段から、それぞれ素数a、素数b、ヤコビ和候補値jを取得し、素数a、素数bで指定される代数曲線のヤコビアン群の位数の複数の候補値からなる集合Hを演算する手順と、
（ｈ）H記憶手段が、前記位数候補値計算装置により演算された集合Hを記憶する手順と、
（ｉ）安全性判定装置が、前記H記憶手段から集合Hを取得し、集合Hの中から概素数性等の安全性条件を満たす候補値hを検索する手順と、
（ｊ）h記憶手段が、前記安全性判定装置により検索された候補値hを記憶する手順と、
（ｋ）パラメータ決定装置が、前記a記憶手段、前記b記憶手段、前記p記憶手段、前記h記憶手段からそれぞれ素数a、素数b、素数p、候補値hを取得し、素数a、素数b、素数pで指定される代数曲線でそのヤコビアン群の位数が候補値hと一致する代数曲線のパラメータを演算する手順と、
（ｌ）出力装置が、前記パラメータ決定装置で演算された代数曲線のパラメータを出力する手順と、
を含むことを特徴とするαYa +βXb + 1 = 0という形の定義方程式をもつ代数曲線暗号における安全なパラメータの生成方法。
【請求項７】
前記スティッケルバーガー要素計算装置が、前記a記憶手段、前記b記憶手段からそれぞれ素数a、素数bを取得し、式ω = Σt [<t/a> + <t/b>] σ_{-t-1}（tはabを法とする既約剰余類の代表系を走り、[λ]は有理数λを超えない最大の整数を表し、<λ>は有理数λの小数部分λ-[λ]を表し、σtは円のab分体におけるガロア写像ζ → ζtを表す(ζは1の原始ab乗根)）を用いてスティッケルバーガー要素ωを演算する手順を含むことを特徴とする請求項６記載のαYa +βXb + 1 = 0という形の定義方程式をもつ代数曲線暗号における安全なパラメータの生成方法。
【請求項８】
前記ヤコビ和候補値計算装置が、前記a記憶手段、前記b記憶手段、前記n記憶手段、前記ω記憶手段からそれぞれ素数a、素数b、暗号鍵のサイズn、スティッケルバーガー要素ωを取得し、１の原始ab乗根で生成される円分体Kの素イデアルを生成する代数的整数γで、その絶対ノルムが2n/(a-1)(b-1)程度のビット長の素数pとなるαをランダムに生成し、式j = γωを用いてヤコビ和候補値jを演算する手順を含むことを特徴とする請求項６または７記載のαYa +βXb + 1 = 0という形の定義方程式をもつ代数曲線暗号における安全なパラメータの生成方法。
【請求項９】
前記位数候補値計算装置が、前記a記憶手段、前記b記憶手段、前記j記憶手段からそれぞれ素数a、素数b、ヤコビ和候補値jを取得し、１以上2ab以下の整数である各kに対して、ζを１の原始ab乗根とするとき、式 hk = NormK|Q(１+ (-ζ)k j)（Norm_{K|Q}は、円のab分体Kにおけるノルム写像）を用いて、パラメータa、bで指定される代数曲線のヤコビアン群の位数の候補値hkを演算し、候補値の集合H={h1、h2、．．．、h2ab}を演算する手順を含むことを特徴とする請求項６、７、または８記載のαYa +βXb + 1 = 0という形の定義方程式をもつ代数曲線暗号における安全なパラメータの生成方法。
【請求項１０】
前記パラメータ決定装置が、前記a記憶手段、前記b記憶手段、前記p記憶手段、前記h記憶手段からそれぞれ素数a、素数b、素数p、候補値hを取得し、素数pを法とする１の原始a乗根ζaおよび１の原始b乗根ζbを求め、１以上a以下の各整数l、および１以上b以下の各整数mに対して、式ζal Ya + ζbm Xb +１=０で定義される代数曲線上のランダムな点Gを生成し、点Gの表すヤコビアン群における要素のh倍を計算し、結果がヤコビアン群における単位元に等しいならば、素数a、素数bで指定される代数曲線でそのヤコビアン群の位数が候補値hと一致する代数曲線のパラメータとしてp、ζalおよびζbmを出力する手順を含むことを特徴とする請求項６、７、８または９記載のαYa +βXb + 1 = 0という形の定義方程式をもつ代数曲線暗号における安全なパラメータの生成方法。
【請求項１１】
（ａ）入力装置に、曲線の複雑さの度合いを指定する2つの異なる素数a、b、および、使用したい暗号鍵のサイズnを入力する手順を実行させ
（ｂ）a記憶手段、b記憶手段、および、n記憶手段に、それぞれ、前記入力手段に入力された素数a、素数b、暗号鍵のサイズnを記憶する手順を実行させ
（ｃ）スティッケルバーガー要素計算装置に、前記a記憶手段、前記b記憶手段からそれぞれ素数a、素数bを取得し、円のab分体におけるスティッケルバーガー要素ωを演算する手順を実行させ
（ｄ）ω記憶手段に、前記スティッケルバーガー要素計算装置により演算されたスティッケルバーガー要素ωを記憶する手順を実行させ
（ｅ）ヤコビ和候補値計算装置に、前記a記憶手段、前記b記憶手段、前記n記憶手段、前記ω記憶手段からそれぞれ素数a、素数b、暗号鍵のサイズn、スティッケルバーガー要素ωを取得し、2つの異なる素数a、素数bに対するヤコビ和候補値jおよびヤコビ和候補値jに対応する素数pを演算する手順を実行させ
（ｆ）p記憶手段、およびj記憶手段に、それぞれ、前記ヤコビ和候補値計算装置により演算された素数p、ヤコビ和候補値jを記憶する手順を実行させ
（ｇ）位数候補値計算装置に、前記a記憶手段、前記b記憶手段、前記j記憶手段から、それぞれ素数a、素数b、ヤコビ和候補値jを取得し、素数a、素数bで指定される代数曲線のヤコビアン群の位数の複数の候補値からなる集合Hを演算する手順を実行させ
（ｈ）H記憶手段に、前記位数候補値計算装置により演算された集合Hを記憶する手順を実行させ
（ｉ）安全性判定装置に、前記H記憶手段から集合Hを取得し、集合Hの中から概素数性等の安全性条件を満たす候補値hを検索する手順を実行させ
（ｊ）h記憶手段に、前記安全性判定装置により検索された候補値hを記憶する手順を実行させ
（ｋ）パラメータ決定装置に、前記a記憶手段、前記b記憶手段、前記p記憶手段、前記h記憶手段からそれぞれ素数a、素数b、素数p、候補値hを取得し、素数a、素数b、素数pで指定される代数曲線でそのヤコビアン群の位数が候補値hと一致する代数曲線のパラメータを演算する手順を実行させ
（ｌ）出力装置に、前記パラメータ決定装置で演算された代数曲線のパラメータを出力する手順を実行させるαYa +βXb + 1 = 0という形の定義方程式をもつ代数曲線暗号における安全なパラメータの生成プログラムを記録したことを特徴とする記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、離散対数型暗号（以下、代数曲線暗号と記す）における安全なパラメータの生成装置、生成方法、および記録媒体に関し、特に、代数曲線のヤコビアン群を用いた離散対数型暗号における安全なパラメータの生成装置、生成方法、および記録媒体に関する。
【０００２】
【従来の技術】
離散対数型暗号は、与えられた有限群上の離散対数問題の困難性に基づく公開鍵暗号方式である。暗号の安全性を保つためには、用いる有限群の位数は、ほぼ素数、すなわち、小さな整数と大きな素数の積でなければならない。離散対数型暗号の一種である代数曲線暗号では、ヤコビアン群の位数がほぼ素数である代数曲線を用いる必要がある。
【０００３】
最も簡単な代数曲線である楕円曲線の場合には、任意の楕円曲線に対して、そのヤコビアン群の位数を計算する効率的なアルゴリズムが知られている。例えば、１９９５年、レネ＝スクーフ著、カウンティング＝ポインツ＝オン＝エリプティック＝カーブズ＝オーバー＝ファイナイト＝フィールズ、ジャーナル＝ドゥ＝セオリ＝ドゥ＝ノンブル、７巻、２１９−２５４（Ｒｅｎｅ  Ｓｃｈｏｏｆ、Ｃｏｕｎｔｉｎｇ  ｐｏｉｎｔｓ  ｏｎ  ｅｌｌｉｐｔｉｃ  ｃｕｒｖｅｓ  ｏｖｅｒ  ｆｉｎｉｔｅ  ｆｉｅｌｄｓ、Ｊｏｕｒｎａｌ  ｄｅ  Ｔｈｅｏｒｉｅ  ｄｅｓ  Ｎｏｍｂｒｅｓ、ｄｅ  Ｂｏｒｄｅａｕｘ  ７  （１９９５）、２１９−２５４、Ｉｎｓｔｉｔｕｅ  ｄｅＭａｔｈｅｍａｔｉｑｕｅ  ｄｅ  Ｂｏｒｄｅａｕｘ）に詳しい記述がある。ヤコビアン群の位数がほぼ素数である楕円曲線を得るには、上記のアルゴリズムを利用して、以下のようにすればよい。
【０００４】
１。ランダムな楕円曲線Ｅを生成する。
２。Ｅのヤコビアン群の位数ｎを計算する。
３。ｎがほぼ素数ならばＥを出力し、そうでないならば１に戻る。
【０００５】
楕円曲線以外の代数曲線の場合には、例外的な一部の超楕円曲線を除いて、そのヤコビアン群の位数を計算する効率的なアルゴリズムは知られていない。そのため、代数曲線暗号で使用できる代数曲線は、楕円曲線および例外的な一部の超楕円曲線に限定されてしまう。
【０００６】
また、ヤコビアン群における要素のｈ倍演算に関しては、「有田、吉川、宮内、Ｃａｂ曲線を用いた離散対数型暗号のソフトウェア実装、１９９９年暗号と情報セキュリティシンポジウム、ｐｐ．５７３−５７８」が知られている。
【０００７】
また、「特開平６−２８２２２６号公報」記載の技術は、「任意の素数を選び、素数に対応した暗号化鍵を公開ファイル装置に登録し、素数、暗号鍵に対応する復号鍵表により生成し、素数と共に復号鍵表を復号装置に記憶しておき、暗号化装置が公開ファイル装置より受信者（復号装置）の公開鍵を入手し、平文を楕円曲線上で乗算し、その値を暗号文として復号装置に送信し、復号装置が暗号文から楕円曲線のパラメータを計算し、復号鍵表を用いてパラメータに対応する復号鍵を選び、暗号文を楕円曲線で乗算した値から中国剰余定理を用いて平文を得る」ものである。
【０００８】
【発明が解決しようとする課題】
上述した従来技術においては、使用できる代数曲線が、楕円曲線および例外的な一部の超楕円曲線に限定されている。楕円曲線および超楕円曲線は、代数曲線全体から見ると、極めて特殊な代数曲線であり、暗号解読のためのターゲットが狭くなるため、代数曲線暗号の安全性に問題がある。
【０００９】
本発明の目的は、従来使用できなかった高次の複雑な代数曲線を代数曲線暗号に用いることを可能とし、代数曲線暗号の安全性を向上させることである。
【００１０】
【課題を解決するための手段】
本発明の第１のαYa +βXb + 1 = 0という形の定義方程式をもつ代数曲線暗号における安全なパラメータの生成装置は、
（ａ）曲線の複雑さの度合いを指定する2つの異なる素数a、b、および、使用したい暗号鍵のサイズnを入力する入力装置と、
（ｂ）前記入力手段に入力された素数a、素数b、暗号鍵のサイズnをそれぞれ記憶するa記憶手段、b記憶手段、および、n記憶手段と、
（ｃ）前記a記憶手段、前記b記憶手段からそれぞれ素数a、素数bを取得し、円のab分体におけるスティッケルバーガー要素ωを演算するスティッケルバーガー要素計算装置と、
（ｄ）前記スティッケルバーガー要素計算装置により演算されたスティッケルバーガー要素ωを記憶するω記憶手段と、
（ｅ）前記a記憶手段、前記b記憶手段、前記n記憶手段、前記ω記憶手段からそれぞれ素数a、素数b、暗号鍵のサイズn、スティッケルバーガー要素ωを取得し、2つの異なる素数a、素数bに対するヤコビ和候補値jおよびヤコビ和候補値jに対応する素数pを演算するヤコビ和候補値計算装置と、
（ｆ）前記ヤコビ和候補値計算装置により演算された素数p、ヤコビ和候補値jをそれぞれ記憶するp記憶手段、およびj記憶手段と、
（ｇ）前記a記憶手段、前記b記憶手段、前記j記憶手段から、それぞれ素数a、素数b、ヤコビ和候補値jを取得し、素数a、素数bで指定される代数曲線のヤコビアン群の位数の複数の候補値からなる集合Hを演算する位数候補値計算装置と、
（ｈ）前記位数候補値計算装置により演算された集合Hを記憶するH記憶手段と、
（ｉ）前記H記憶手段から集合Hを取得し、集合Hの中から概素数性等の安全性条件を満たす候補値hを検索する安全性判定装置と、
（ｊ）前記安全性判定装置により検索された候補値hを記憶するh記憶手段と、
（ｋ）前記a記憶手段、前記b記憶手段、前記p記憶手段、前記h記憶手段からそれぞれ素数a、素数b、素数p、候補値hを取得し、素数a、素数b、素数pで指定される代数曲線でそのヤコビアン群の位数が候補値hと一致する代数曲線のパラメータを演算するパラメータ決定装置と、
（ｌ）前記パラメータ決定装置で演算された代数曲線のパラメータを出力する出力装置と、
を備える。
【００１１】
本発明の第２のαYa +βXb + 1 = 0という形の定義方程式をもつ代数曲線暗号における安全なパラメータの生成装置は、前記第１のαYa +βXb + 1 = 0という形の定義方程式をもつ代数曲線暗号における安全なパラメータの生成装置であって、
前記a記憶手段、前記b記憶手段からそれぞれ素数a、素数bを取得し、式ω = Σt [<t/a> + <t/b>] σ_{-t-1}（tはabを法とする既約剰余類の代表系を走り、[λ]は有理数λを超えない最大の整数を表し、<λ>は有理数λの小数部分λ-[λ]を表し、σtは円のab分体におけるガロア写像ζ → ζtを表す(ζは1の原始ab乗根)）を用いてスティッケルバーガー要素ωを演算する前記スティッケルバーガー要素計算装置を備える。
【００１２】
本発明の第３のαYa +βXb + 1 = 0という形の定義方程式をもつ代数曲線暗号における安全なパラメータの生成装置は、前記第１または第２のαYa +βXb + 1 = 0という形の定義方程式をもつ代数曲線暗号における安全なパラメータの生成装置であって、
前記a記憶手段、前記b記憶手段、前記n記憶手段、前記ω記憶手段からそれぞれ素数a、素数b、暗号鍵のサイズn、スティッケルバーガー要素ωを取得し、１の原始ab乗根で生成される円分体Kの素イデアルを生成する代数的整数γで、その絶対ノルムが2n/(a-1)(b-1)程度のビット長の素数pとなるαをランダムに生成し、式j = γωを用いてヤコビ和候補値jを演算する前記ヤコビ和候補値計算装置を備える。
【００１３】
本発明の第４のαYa +βXb + 1 = 0という形の定義方程式をもつ代数曲線暗号における安全なパラメータの生成装置は、前記第１、第２または第３のαYa +βXb + 1 = 0という形の定義方程式をもつ代数曲線暗号における安全なパラメータの生成装置であって、
前記a記憶手段、前記b記憶手段、前記j記憶手段からそれぞれ素数a、素数b、ヤコビ和候補値jを取得し、１以上2ab以下の整数である各kに対して、ζを１の原始ab乗根とするとき、式 hk = NormK|Q(１+ (-ζ)k j)（Norm_{K|Q}は、円のab分体Kにおけるノルム写像）を用いて、パラメータa、bで指定される代数曲線のヤコビアン群の位数の候補値hkを演算し、候補値の集合H={h1、h2、．．．、h2ab}を演算する前記位数候補値計算装置を備える。
【００１４】
本発明の第５のαYa +βXb + 1 = 0という形の定義方程式をもつ代数曲線暗号における安全なパラメータの生成装置は、前記第１、第２、第３または第４ののαYa +βXb + 1 = 0という形の定義方程式をもつ代数曲線暗号における安全なパラメータの生成装置であって、
前記a記憶手段、前記b記憶手段、前記p記憶手段、前記h記憶手段からそれぞれ素数a、素数b、素数p、候補値hを取得し、素数pを法とする１の原始a乗根ζaおよび１の原始b乗根ζbを求め、１以上a以下の各整数l、および１以上b以下の各整数mに対して、式ζal Ya + ζbm Xb +１=０で定義される代数曲線上のランダムな点Gを生成し、点Gの表すヤコビアン群における要素のh倍を計算し、結果がヤコビアン群における単位元に等しいならば、素数a、素数bで指定される代数曲線でそのヤコビアン群の位数が候補値hと一致する代数曲線のパラメータとしてp、ζalおよびζbmを出力する前記パラメータ決定装置を備える。
【００１５】
本発明の第１のαYa +βXb + 1 = 0という形の定義方程式をもつ代数曲線暗号における安全なパラメータの生成方法は、
（ａ）入力装置が、曲線の複雑さの度合いを指定する2つの異なる素数a、b、および、使用したい暗号鍵のサイズnを入力する手順と、
（ｂ）a記憶手段、b記憶手段、および、n記憶手段が、それぞれ、前記入力手段に入力された素数a、素数b、暗号鍵のサイズnを記憶する手順と、
（ｃ）スティッケルバーガー要素計算装置が、前記a記憶手段、前記b記憶手段からそれぞれ素数a、素数bを取得し、円のab分体におけるスティッケルバーガー要素ωを演算する手順と、
（ｄ）ω記憶手段が、前記スティッケルバーガー要素計算装置により演算されたスティッケルバーガー要素ωを記憶する手順と、
（ｅ）ヤコビ和候補値計算装置が、前記a記憶手段、前記b記憶手段、前記n記憶手段、前記ω記憶手段からそれぞれ素数a、素数b、暗号鍵のサイズn、スティッケルバーガー要素ωを取得し、2つの異なる素数a、素数bに対するヤコビ和候補値jおよびヤコビ和候補値jに対応する素数pを演算する手順と、
（ｆ）p記憶手段、およびj記憶手段が、それぞれ、前記ヤコビ和候補値計算装置により演算された素数p、ヤコビ和候補値jを記憶する手順と、
（ｇ）位数候補値計算装置が、前記a記憶手段、前記b記憶手段、前記j記憶手段から、それぞれ素数a、素数b、ヤコビ和候補値jを取得し、素数a、素数bで指定される代数曲線のヤコビアン群の位数の複数の候補値からなる集合Hを演算する手順と、
（ｈ）H記憶手段が、前記位数候補値計算装置により演算された集合Hを記憶する手順と、
（ｉ）安全性判定装置が、前記H記憶手段から集合Hを取得し、集合Hの中から概素数性等の安全性条件を満たす候補値hを検索する手順と、
（ｊ）h記憶手段が、前記安全性判定装置により検索された候補値hを記憶する手順と、
（ｋ）パラメータ決定装置が、前記a記憶手段、前記b記憶手段、前記p記憶手段、前記h記憶手段からそれぞれ素数a、素数b、素数p、候補値hを取得し、素数a、素数b、素数pで指定される代数曲線でそのヤコビアン群の位数が候補値hと一致する代数曲線のパラメータを演算する手順と、
（ｌ）出力装置が、前記パラメータ決定装置で演算された代数曲線のパラメータを出力する手順と、
を含む。
【００１６】
本発明の第２のαYa +βXb + 1 = 0という形の定義方程式をもつ代数曲線暗号における安全なパラメータの生成方法は、前記第１のαYa +βXb + 1 = 0という形の定義方程式をもつ代数曲線暗号における安全なパラメータの生成方法であって、
前記スティッケルバーガー要素計算装置が、前記a記憶手段、前記b記憶手段からそれぞれ素数a、素数bを取得し、式ω = Σt [<t/a> + <t/b>] σ_{-t-1}（tはabを法とする既約剰余類の代表系を走り、[λ]は有理数λを超えない最大の整数を表し、<λ>は有理数λの小数部分λ-[λ]を表し、σtは円のab分体におけるガロア写像ζ → ζtを表す(ζは1の原始ab乗根)）を用いてスティッケルバーガー要素ωを演算する手順を含む。
【００１７】
本発明の第３のαYa +βXb + 1 = 0という形の定義方程式をもつ代数曲線暗号における安全なパラメータの生成方法は、前記第１、または第２のαYa +βXb + 1 = 0という形の定義方程式をもつ代数曲線暗号における安全なパラメータの生成方法であって、
前記ヤコビ和候補値計算装置が、前記a記憶手段、前記b記憶手段、前記n記憶手段、前記ω記憶手段からそれぞれ素数a、素数b、暗号鍵のサイズn、スティッケルバーガー要素ωを取得し、１の原始ab乗根で生成される円分体Kの素イデアルを生成する代数的整数γで、その絶対ノルムが2n/(a-1)(b-1)程度のビット長の素数pとなるαをランダムに生成し、式j = γωを用いてヤコビ和候補値jを演算する手順を含む。
【００１８】
本発明の第４のαYa +βXb + 1 = 0という形の定義方程式をもつ代数曲線暗号における安全なパラメータの生成方法は、前記第１、第２、または第３のαYa +βXb + 1 = 0という形の定義方程式をもつ代数曲線暗号における安全なパラメータの生成方法であって、
前記位数候補値計算装置が、前記a記憶手段、前記b記憶手段、前記j記憶手段からそれぞれ素数a、素数b、ヤコビ和候補値jを取得し、１以上2ab以下の整数である各kに対して、ζを１の原始ab乗根とするとき、式 hk = NormK|Q(１+ (-ζ)k j)（Norm_{K|Q}は、円のab分体Kにおけるノルム写像）を用いて、パラメータa、bで指定される代数曲線のヤコビアン群の位数の候補値hkを演算し、候補値の集合H={h1、h2、．．．、h2ab}を演算する手順を含む。
【００１９】
本発明の第５のαYa +βXb + 1 = 0という形の定義方程式をもつ代数曲線暗号における安全なパラメータの生成方法は、前記第１、第２、第３、または第４のαYa +βXb + 1 = 0という形の定義方程式をもつ代数曲線暗号における安全なパラメータの生成方法であって、
前記パラメータ決定装置が、前記a記憶手段、前記b記憶手段、前記p記憶手段、前記h記憶手段からそれぞれ素数a、素数b、素数p、候補値hを取得し、素数pを法とする１の原始a乗根ζaおよび１の原始b乗根ζbを求め、１以上a以下の各整数l、および１以上b以下の各整数mに対して、式ζal Ya + ζbm Xb +１=０で定義される代数曲線上のランダムな点Gを生成し、点Gの表すヤコビアン群における要素のh倍を計算し、結果がヤコビアン群における単位元に等しいならば、素数a、素数bで指定される代数曲線でそのヤコビアン群の位数が候補値hと一致する代数曲線のパラメータとしてp、ζalおよびζbmを出力する手順を含む。
【００２０】
本発明の記録媒体は、
（ａ）入力装置に、曲線の複雑さの度合いを指定する2つの異なる素数a、b、および、使用したい暗号鍵のサイズnを入力する手順を実行させ
（ｂ）a記憶手段、b記憶手段、および、n記憶手段に、それぞれ、前記入力手段に入力された素数a、素数b、暗号鍵のサイズnを記憶する手順を実行させ
（ｃ）スティッケルバーガー要素計算装置に、前記a記憶手段、前記b記憶手段からそれぞれ素数a、素数bを取得し、円のab分体におけるスティッケルバーガー要素ωを演算する手順を実行させ
（ｄ）ω記憶手段に、前記スティッケルバーガー要素計算装置により演算されたスティッケルバーガー要素ωを記憶する手順を実行させ
（ｅ）ヤコビ和候補値計算装置に、前記a記憶手段、前記b記憶手段、前記n記憶手段、前記ω記憶手段からそれぞれ素数a、素数b、暗号鍵のサイズn、スティッケルバーガー要素ωを取得し、2つの異なる素数a、素数bに対するヤコビ和候補値jおよびヤコビ和候補値jに対応する素数pを演算する手順を実行させ
（ｆ）p記憶手段、およびj記憶手段に、それぞれ、前記ヤコビ和候補値計算装置により演算された素数p、ヤコビ和候補値jを記憶する手順を実行させ
（ｇ）位数候補値計算装置に、前記a記憶手段、前記b記憶手段、前記j記憶手段から、それぞれ素数a、素数b、ヤコビ和候補値jを取得し、素数a、素数bで指定される代数曲線のヤコビアン群の位数の複数の候補値からなる集合Hを演算する手順を実行させ
（ｈ）H記憶手段に、前記位数候補値計算装置により演算された集合Hを記憶する手順を実行させ
（ｉ）安全性判定装置に、前記H記憶手段から集合Hを取得し、集合Hの中から概素数性等の安全性条件を満たす候補値hを検索する手順を実行させ
（ｊ）h記憶手段に、前記安全性判定装置により検索された候補値hを記憶する手順を実行させ
（ｋ）パラメータ決定装置に、前記a記憶手段、前記b記憶手段、前記p記憶手段、前記h記憶手段からそれぞれ素数a、素数b、素数p、候補値hを取得し、素数a、素数b、素数pで指定される代数曲線でそのヤコビアン群の位数が候補値hと一致する代数曲線のパラメータを演算する手順を実行させ
（ｌ）出力装置に、前記パラメータ決定装置で演算された代数曲線のパラメータを出力する手順を実行させるαYa +βXb + 1 = 0という形の定義方程式をもつ代数曲線暗号における安全なパラメータの生成プログラムを記録する。
【００２１】
【発明の実施の形態】
まず、本発明の原理について説明する。
【００２２】
本発明は、αＹａ  ＋βＸｂ  ＋  １  ＝  ０という形の定義方程式をもつ代数曲線のクラスから、そのヤコビアン群の位数がほぼ素数である代数曲線を効率的に探索し、従来使用できなかった高次の複雑な代数曲線を代数曲線暗号に用いることを可能にするものである。ここで、パラメータａ、ｂは曲線の複雑さの程度を表す。
【００２３】
αＹａ  ＋βＸｂ  ＋  １  ＝  ０という形の定義方程式をもつ、位数ｑの有限体Ｆｑ上の代数曲線をＣ（ｑ、α、β）とおく。代数曲線Ｃ（ｑ、α、β）に対しては、そのＬ関数がヤコビ和を用いて記述されることを用いて、そのヤコビアン群の位数を設計することができるのである。以下簡単のため、ｑ  ：＝  ｐ（ｐをｑとおく）  は素数であり、ｐ≡  １  ｍｏｄ  ＬＣＭ（ａ、ｂ）とする（ＬＣＭは最小公倍数）。また、１の原始ａｂ乗根をζとおく。素数ｐは円分体Ｑ（ζ）において、ｍ個の素イデアルＰ１、Ｐ２、．．．、Ｐｍに完全分解する。ここで、ｍは、法ａｂの既約剰余類の個数である。
【００２４】
有限体Ｆｐの乗法群Ｆｐ＊の生成元ｗを固定し、（ｐ−１）ｓが整数となる有理数ｓに対して、Ｆｐ＊の指標χｓをχｓ（ｗ）  ＝  ｅｘｐ（２πｉｓ）（ｉは虚数）によって定義する。χｓ（０）＝０  （ｓ：  整数でないとき）、  ＝１  （ｓ：  整数のとき）として、定義域をＦｐ全体に拡張する。整数  ｌ＝１、２、．．．、ａ−１および整数  ｍ＝１、２、．．．、ｂ−１に対して、ｊｐ（ｌ、ｍ）  ＝  Σ＿｛１＋ｖ１＋ｖ２＝０｝  χｌ／ａ（ｖ１）χｍ／ｂ（ｖ２）  はヤコビ和と呼ばれる。ここで、ｖ１、  ｖ２は１＋ｖ１＋ｖ２＝０を満たすｖ１、  ｖ２  ∈Ｆｐを走る。このとき、Ｃ（ｐ、α、β）のＬ関数Ｌｐ（Ｕ）は以下のようにヤコビ和を用いて表されることが知られている。
【００２５】
Ｌｐ（Ｕ）  ＝  Πｌ＝１、２、．．．、ａ−１、 ｍ＝１、２、．．．、ｂ−１  （１  ＋  χｌ／ａ（α−１）χｍ／ｂ（β−１）  ｊｐ（ｌ、ｍ）  Ｕ  ）。
したがって、Ｃ（ｐ、α、β）のヤコビアン群の位数ｈは、
ｈ  ＝  Ｌｐ（１）  ＝  Πｌ＝１、２、．．．、ａ−１、 ｍ＝１、２、．．．、ｂ−１  （  １  ＋χｌ／ａ（α−１）χｍ／ｂ（β−１）  ｊｐ（ｌ、ｍ）  ）
で与えられる。よって、ヤコビアン群の位数を求めるには、ヤコビ和ｊｐ（ｌ、ｍ）が計算できればよい。しかしながら、ヤコビ和ｊｐ（ｌ、ｍ）を定義式に従って直接計算することは計算量的に不可能なので、次のヤコビ和に対するスティッケルバーガー要素を用いる。
【００２６】
［λ］は有理数λを超えない最大の整数を表し、＜λ＞は有理数λの小数部分λ−［λ］を表すとする。また、σｔ  は円分体Ｑ（ζ）のガロア写像ζ  →  ζｔ  を表すとする。群環Ｚ［Ｇａｌ（Ｑ（ζ）｜  Ｑ）］の元であるスティッケルバーガー要素ω（ａ、ｂ）を、
ω（ａ、ｂ）  ＝  Σｔ  ［＜ｔ／ａ＞  ＋  ＜ｔ／ｂ＞］  σ−ｔ−１とおく。
ただし、ｔは、ａｂを法とする既約剰余類の代表系を走るとする。
【００２７】
このとき、円分体Ｑ（ζ）のイデアルとして、（ｊｐ（ｌ、ｍ））  ＝  Ｐω（ａ、ｂ）が成立することが知られている。ここで、Ｐはｐの上にある素イデアルである。上式より、ｊｐ（ｌ、ｍ）は１の２ａｂ乗根を除いて一意に定まる。そのうち、ａｂ乗根分の自由度はＣ（ｐ、α、β）の係数α、β  ∈  Ｆｑの自由度から得られる。
【００２８】
以上より、次のような安全な曲線Ｃ（ｐ、α、β）の探索アルゴリズムが得られる。
安全な曲線Ｃ（ｐ、α、β）の探索アルゴリズム
入力：ヤコビアンのビット数ｎ
出力：ｐ、α、β
（１）ｇ  ←  （ａ−１）（ｂ−１）／２
（２）ある  ｎ／ｇ  ビット程度の素数ｐに対するヤコビ和の候補ｊを後述のヤコビ和の候補値の計算アルゴリズムを用いて探す：
（ｐ、ｊ）  ←  ｛ヤコビ和の候補値の計算アルゴリズム｝（ｎ／ｇ）。
（３）各ｋ  ＝  ０、１、．．．、ａｂ  に対して、
ｈｋ  ←Πｌ＝１、２、．．．、ａ−１、 ｍ＝１、２、．．．、ｂ−１  （  １  ＋  （−ζ）ｋ  ｊ）
（４）｛  ｈ０、ｈ１、．．．、ｈａｂ  ｝にほぼ素数である  ｈｋ  があるかどうかを調べる。なければ、（１）へ戻る。あれば、ｈ  ：＝  ｈｋ  とする。
（５）ζａ、ζｂ  をそれぞれ  Ｆｐ  における１のａ乗根、ｂ乗根とする。各  ｌ  ＝  ０、１、．．．、ａ−１  および各  ｍ  ＝  ０、１、．．．、ｂ−１  に対して、曲線Ｃ（ｐ、ζａｌ、ζｂｍ）：ζａｌ  ｙａ  ＋ζｂｍ  ｘｂ  ＋  １  ＝  ０  のヤコビアン群のオーダーが  ｈ  に等しいかどうか調べる。等しければ、ｐ、α＝ζａｌ、β＝ζｂｍ  を出力して終了する。そのようなｌ、  ｍ  がなければ、（２）へ。
上で用いた、ヤコビ和の候補値の計算アルゴリズムでは、前記のスティッケルバーガー要素ω（ａ、ｂ）  ＝  Σｔ  ［＜ｔ／ａ＞  ＋  ＜ｔ／ｂ＞］  σ−ｔ−１  を用いて、ヤコビ和の候補値を求める。
ヤコビ和の候補値の計算アルゴリズムは以下のようである。
入力：ビット数ｍ、
出力：ｐ、ｊ、
（１）ω  ←  Σｔ  （＜ｔ／ａ＞  ＋  ＜ｔ／ｂ＞）σ−ｔ−１、
（２）γ０  ＝  Σｌ＝０ｍ−１  ｃｌζｌ  （−１０  ＜  ｃｌ  ＜  １０）  をランダムに生成。
（３）各  ｉ  ＝  １、２、．．．  に対して、
γ  ←  γ０  ＋  Ｉ、
ｐ  ←  ＮｏｒｍＱ（ζ）｜Ｑ（γ）、
ｐ  が約  ｍ  ビットより小さいか？、
ｙｅｓ  →  ｃｏｎｔｉｎｕｅ、
ｐ  が約  ｍ  ビットより大きいか？、
ｙｅｓ  →  （２）へ、
ｐ  が素数か？
ｎｏ  →  ｃｏｎｔｉｎｕｅ、
（４）ｊ  ←  γω  、  ｐ  および  ｊ  を出力して終了。
【００２９】
次に、本発明の第１の実施の形態について図面を参照して詳細に説明する。
【００３０】
図１は、本発明の第１の実施の形態を示すブロック図である。
図１を参照すると、本発明の第１の実施の形態は、スティッケルバーガー要素計算装置１１と、ヤコビ和候補値計算装置１２と、位数候補値計算装置１３と、安全性判定装置１４と、パラメータ決定装置１５と、メモリ１６と、入力装置１７と、出力装置１８と、中央処理装置１９とから構成される。
【００３１】
また、メモリ１６は、ａ記憶ファイル１６１、ｂ記憶ファイル１６２、ω記憶ファイル１６３、ｊ記憶ファイル１６４、Ｈ記憶ファイル１６５、ｈ記憶ファイル１６６、ｐ記憶ファイル１６７、および、ｎ記憶ファイル１６８を含む。
【００３２】
以下では、円分体Ｑ（ζ）における代数的数の四則演算、およびノルムＮＱ（ζ）｜ Ｑの演算、および円分体Ｑ（ζ）に対するガロア群Ｇ（Ｑ（ζ）｜  Ｑ）の作用の演算、および整数環Ｚ係数のガロア群Ｇ（Ｑ（ζ）｜  Ｑ）上の群環Ｚ［Ｇ（Ｑ（ζ）｜  Ｑ）］における加法および乗法演算に関しては、既知の手法を用いるものとする。
【００３３】
次に、本発明の第１の実施の形態の動作について説明する。
図２は、スティッケルバーガー要素計算装置１１の動作を示すフローチャートである。
図３は、ヤコビ和候補値計算装置１２の動作を示すフローチャートである。
図４は、位数候補値計算装置１３の動作を示すフローチャートである。
図５は、パラメータ決定装置１５の動作を示すフローチャートである。
【００３４】
曲線の複雑さの度合いを指定する２つの異なる素数ａ＝３、ｂ＝７、および使用したい暗号鍵のサイズｎ＝１６０が入力装置１７から入力された場合について説明する。入力されたａ、ｂは中央処理装置１９を介してそれぞれａ記憶ファイル１６１、ｂ記憶ファイル１６２に一時的に記憶される。また、以下の記述において現れる変数は、メモリ１６に格納される。
【００３５】
次に、スティッケルバーガー要素計算装置１１が、図２に示す処理にしたがって、ａ記憶ファイル１６１、ｂ記憶ファイル１６２よりａ＝３、ｂ＝７を取得して以下のように動作する。
【００３６】
図２のステップＳ２１において、変数Ｌにａ・ｂ  ＝  ３×７＝２１を法とする既約剰余類の代表系｛１、２、４、５、８、１０、１１、１３、１６、１７、１９、２０｝が格納される。
【００３７】
次に、図２のステップＳ２２において、変数Ｌ＝｛１、２、４、５、８、１０、１１、１３、１６、１７、１９、２０｝に含まれる各整数ｔに対して、例えば、ｔ＝１のとき、［＜１／３＞＋＜１／７＞］  ＝  ［１／３＋１／７］＝［１０／２１］＝０なので、変数ｍに０が格納され、−１−１  ≡  −１  ≡  ２０  ｍｏｄ２１なので、変数ｓに２０が格納され、０×σ２０  ＝  ０なので、変数λ１に０が格納される。
【００３８】
他のｔについても同様にして、変数λ２に［＜２／３＞＋＜２／７＞］＝［２／３＋２／７］＝［２０／２１］＝０なので０が、変数λ４に［＜４／３＞＋＜４／７＞］＝［１／３＋４／７］＝［１９／２１］＝０なので０が、変数λ５に［＜５／３＞＋＜５／７＞］＝［２／３＋５／７］＝［２９／２１］＝１で（−５）−１  ≡  １６−１  ≡  ４  ｍｏｄ  ２１なのでσ４が、変数λ８に［＜８／３＞＋＜８／７＞］＝［２／３＋１／７］＝［１７／２１］＝０なので０が、変数λ１０に［＜１０／３＞＋＜１０／７＞］＝［１／３＋３／７］＝［１６／２１］＝０なので０が、変数λ１１に［＜１１／３＞＋＜１１／７＞］＝［２／３＋４／７］＝［２６／２１］＝１で（−１１）−１  ≡  １０−１  ≡  １９  ｍｏｄ  ２１なのでσ１９が、変数λ１３に［＜１３／３＞＋＜１３／７＞］＝［１／３＋６／７］＝［２５／２１］＝１で（−１３）  −１  ≡  ８−１  ≡  ８ｍｏｄ  ２１なのでσ８が、変数λ１６に［＜１６／３＞＋＜１６／７＞］＝［１／３＋２／７］＝［１３／２１］＝０なので０が、変数λ１７に［＜１７／３＞＋＜１７／７＞］＝［２／３＋３／７］＝［２３／２１］＝１で（−１７）  −１  ≡  ４−１  ≡  １６  ｍｏｄ  ２１なのでσ１６が、変数λ１９に［＜１９／３＞＋＜１９／７＞］＝［１／３＋５／７］＝［２２／２１］＝１で（−１９）  −１  ≡  ２−１  ≡  １１  ｍｏｄ  ２１なのでσ１１が、変数λ２０に［＜２０／３＞＋＜２０／７＞］＝［２／３＋６／７］＝［３２／２１］＝１で（−２０）  −１  ≡  １−１  ≡  １  ｍｏｄ  ２１  なのでσ１が、それぞれ格納される。
【００３９】
次に、図２のステップＳ２３において、各変数λ１、λ２、λ４、λ５、λ８、λ１０、λ１１、λ１３、λ１６、λ１７、λ１９、λ２０に記憶された全データの総和ω  ＝  σ４  ＋  σ１９  ＋  σ８  ＋  σ１６  ＋  σ１１  ＋  σ１  が計算される。ここでの総和は、群環Ｚ［Ｇ（Ｑ（ζ）｜  Ｑ）］における総和であり、  各σｉをシンボルとみなし、各σｉごとの係数の総和を意味する。演算結果であるωは中央処理装置１９を介して、ω記憶ファイル１６３に一時的に記憶される。
【００４０】
次に、ヤコビ和候補値計算装置１２が、ａ記憶ファイル１６１、ｂ記憶ファイル１６２、ｎ記憶ファイル１６８、ω記憶ファイル１６３から、ａ＝３、ｂ＝７、ｎ＝１６０、ω＝σ４  ＋  σ１９  ＋  σ８  ＋  σ１６  ＋  σ１１  ＋  σ１を取得して、図３に示す処理にしたがって、以下のようにしてヤコビ和の候補値ｊを演算する。
【００４１】
まず、図３のステップＳ３１において、変数ζに、ａｂ＝２１なので、１の原始２１乗根を格納し、変数ｍに、２ｎ  ／  （ａ−１）（ｂ−１）  ＝  ２６．６．．．なので、２７を格納する。
【００４２】
次に、図３のステップＳ３２において、変数γ０に円分体Ｑ（ζ）のランダム整数を以下のようにして格納する。変数γ０を０に初期化し、ｔ＝０に対し、乱数ｒ０  ＝  −２を発生し、γ０にｒ０  ζ０  ＝  −２を加え、γ０＝−２とし、ｔ＝１に対し、乱数ｒ１  ＝  ２を発生し、γ０にｒ１  ζ１  ＝  ２  ζを加え、γ０  ＝  −２  ＋  ２ζとし、以下同様の操作をｔ＝１１まで繰り返して、γ０  ＝  −２  ＋  ２ζ−ζ２  ＋  ２ζ３  ＋  ２ζ５  −  ζ６  −  ζ７  −  ２  ζ８  ＋  ２ζ９  −  ζ１１を得る。
【００４３】
次に、図３のステップＳ３３において、各整数ｉ＝０、１、２、．．．に対して、以下の操作を行う。ｉ＝０に対し、変数γにγ０  ＋  ０を格納し、γ  ＝  −２  ＋  ２ζ−ζ２  ＋  ２ζ３  ＋  ２ζ５  −  ζ６  −  ζ７  −  ２  ζ８  ＋  ２ζ９  −  ζ１１  を得て、  そのノルムＮＱ（ζ）｜ Ｑ（γ）を計算し、１２９５７１５１３を得てｐ記憶ファイル１６７に格納し、変数ｌにｐ＝１２９５７１５１３のビット数２９を格納し、ｌ＝２９がｍ＝２７程度であることを確認し、ｐ＝１２９５７１５１３を既知の方法により素因数分解するとｐ＝１２９５７１５１３＝４３×２１１×１４２８１となりｐ＝１２９５７１５１３は素数ではないので、ｉ＝０に対する処理を終了し、ｉ＝１に対して、同様の操作を繰り返す。本実施の形態の場合は、ｉ＝２となるまで同様の操作が続き、ｉ＝２に対し、変数γにγ０  ＋  ２を格納し、γ  ＝  ２ζ−ζ２  ＋  ２ζ３  ＋  ２ζ５  −  ζ６  −  ζ７  −  ２  ζ８  ＋  ２ζ９  −  ζ１１  を得て、そのノルムＮＱ（ζ）｜ Ｑ（γ）を計算し、１６３２５５５９７を得てｐ記憶ファイル１６７に格納し、変数ｌにｐ＝１６３２５５５９７のビット数２８を格納し、ｌ＝２８がｍ＝２７程度であり、ｐ＝１６３２５５５９７は素数と判定されるので（素数判定には既知の手法を用いる）、ステップＳ３３の操作は終了する。
【００４４】
次に、図３のステップＳ３４において、変数γの値２ζ−ζ２  ＋  ２ζ３  ＋  ２ζ５  −  ζ６  −  ζ７  −  ２  ζ８  ＋  ２ζ９  −  ζ１１  に、スティッケルバーガー要素ω＝σ４  ＋  σ１９  ＋  σ８  ＋  σ１６  ＋  σ１１  ＋  σ１を作用させ、結果をｊ記憶ファイル１６４に格納する。
【００４５】
すなわち、ｊ  ＝  σ４（γ）σ１９（γ）σ８（γ）σ１６（γ）  σ１１（γ）σ１（γ）
＝  −１１３４６  ＋  ４１５８ζ  ＋  ９３３７ζ２  −  １０９３０ζ３  ＋  ３０６０ζ４  ＋  １１１３２ζ５  −  １４０８ζ６  −  １００００ζ７  ＋  ７５０６ζ８  ＋  １２３７ζ９  −  ９８９４ζ１０  ＋  １６４０６  ζ１１
となるので、ｊ記憶ファイル１６４の内容は  −１１３４６  ＋  ４１５８ζ  ＋  ９３３７ζ２  −  １０９３０ζ３  ＋  ３０６０ζ４  ＋  １１１３２ζ５  −  １４０８ζ６  −  １００００ζ７  ＋  ７５０６ζ８  ＋  １２３７ζ９  −  ９８９４ζ１０  ＋  １６４０６  ζ１１となる。
【００４６】
次に、位数候補値計算装置１３が、図４に示す処理にしたがって、ａ記憶ファイル１６１、ｂ記憶ファイル１６２、ｊ記憶ファイル１６４からそれぞれａ、ｂ、ｊを取得し、以下のようにしてヤコビ群の位数の候補値を計算する。
【００４７】
まず、図４のステップＳ４１において、変数ζに、ａｂ＝２１なので、１の原始２１乗根を格納する。
【００４８】
次に、図４のステップＳ４２において、各整数ｋ＝１、．．．、２ａｂ＝４２に対して、ヤコビ和候補値ｊを用いて、ＮＱ（ζ）｜ Ｑ  （１  ＋  （−ζ）ｋ  ｊ）  を計算し、結果を変数ｈｋに格納する。すなわち、ｋ＝１に対して、ＮＱ（ζ）｜ Ｑ  （１  ＋  （−ζ）  ｊ）＝  １８９４５７５０５５４２２４６７４８６２７２０９１７３７９２１４０５０９６８７４９５４７２４９５７７なので、変数ｈ１に１８９４５７５０５５４２２４６７４８６２７２０９１７３７９２１４０５０９６８７４９５４７２４９５７７が格納され、ｋ＝２に対して、ＮＱ（ζ）｜ Ｑ  （１  ＋  （−ζ）２  ｊ）  ＝  １８９２８９６９３０５２６５７９６９７８８３０９４１９３８７７２１８０７７７０５０４１７７２１９４９なので、変数ｈ２に１８９２８９６９３０５２６５７９６９７８８３０９４１９３８７７２１８０７７７０５０４１７７２１９４９が格納される。
【００４９】
以下同様にして、変数ｈ３に１８９３９４４２３９７７５７５５９６３９１７６５８６１２８４０４３８３４７９０７６１４２１３５７６１が、変数ｈ４に１８９３５０６０３４５４０６４３７２４７９８４２４９５９０１２１９８０３２１２４４８６２４９６７６１が、変数ｈ５に１８９３５６２２６７６８５２７２６６８４９０２８１６９７０６１２４７０２３７４７４５４１８０９６６４が、変数ｈ６に１８９３１９３６９０３６６５７０５４７５５８１６４７３０５５７４４４４７８６２６３２３７０６９０８１が、変数ｈ７に１８９２９５６０６５４７７１８６０１０１３８３３１８１８５９９７６７４１１６９２９６２６０１２８８９が、変数ｈ８に１８９３９１５０２０３６５０２５０１８６１６６３１５２４２１２６３５５７８６７９９２８０５９２４６９が、変数ｈ９に１８９３２６７５８０７２７３６７４６９３９３６１１５５７２１０３３７９６６９３８０３７８３６９４７３が、変数ｈ１０に１８９４２３０９９６５８２１４０５４１４９７０６１４９９２２３９７４９６９１０４２３７５１７００３３が、変数ｈ１１に１８９３４２２９２９０６３５１７６８３０７６４０３５５３２０４６５１０８３９７９１７１９４４２３８９が、変数ｈ１２に１８９３５８３４１７２５８８６０３０２６５０８８０７５１４９６１６５３６０３４３１９６８２９３３６９が、変数ｈ１３に１８９３８０７８７４３０５３９４５９４７８３１９３２１３４８３５８９９６７８９６９０８０７１０２８１が、変数ｈ１４に１８９３０９８０８５４１１４６９８５２１１９７６９２３４１１０７８２６７９６８４０２２５３６８４６１が、変数ｈ１５に１８９２５９２６３４８４８２１２６０４６７９７４０８１９０９５１９３０４７３６０９３７３７９１３５３が、変数ｈ１６に１８９３６２２９７２４３１４３３８３２７６０８１５５９９９１９３４６４４９２９１３２１８４５９６３３が、変数ｈ１７に１８９３５３８９０９８２７８４８７４９５２０５７４０２８５０５２８１２１７０９４３８７８８２３２５３が、変数ｈ１８に１８９３１６９１５６７７８１５４２９９８０５０８９６５２２５７１３５８０２７３７４４４５６６５０７３が、変数ｈ１９に１８９３２７３４１８０６１０９２６１０８１６６７０３６０９０４９２０７７１６１８０１４５７１７８４９が、変数ｈ２０に１８９３８６６４４１１７４３７２４８１５８０３７８４５９３７６１８０１４６１５７９７０５６４７６９３が、変数ｈ２１に１８９３３９４２７５２７７０１０５１７９８３７９８９４７３４７２０８０６１６４７４４２３２５４９６９が、変数ｈ２２に１８９１９３０２９８６３３５７７７３６７０４９５４０２６８４８４２７３８６１９０３１０６３９０７６９が、変数ｈ２３に１８９３６０７５３９６８８５２７０３７３７８１７１１７６５１８０５２２４９７４０８６１３７１３６２１が、変数ｈ２４に１８９２５６０４３２８９８４５９２６２９６２７４６５１９４３４３１９１２０６５９４１６００３７０７３が、変数ｈ２５に１８９２９９８４８６３７８８４１８７５１８３６１５６２６１７１２２９９３７２０８３２３１６３３５７７が、変数ｈ２６に１８９２９４２２５３１７９３６４８１７０１１１２２８３３９７４１１９８１５００９４９８３４９９７７６が、変数ｈ２７に１８９３３１０７９５４５４１５２８８６５１５２８４８８０４０６２６７２７５３１６６４４８４６０７６１が、変数ｈ２８に１８９３５４８３６３４７０５４８７０５３０４３５６３５９４３９１０４８２９９３３３７３５７０３９９３が、変数ｈ２９に１８９２５８９６８４８３４００６２８５１９７２１３６６９６７８３３４８２２１１２７４５５０９８３４９が、変数ｈ３０に１８９３２３６８４９０４７５２０５１５９１２４４５３９３３００７６８１５５５７４４６８６３２６７７７が、変数ｈ３１に１８９２２７３９３３６８６４４４８７４２７５０２８１５３８７１９５９９１０３２３２７１７６４２８７３が、変数ｈ３２に１８９３０８１５１７５２１７３４４８２６６０９４９２３７５１８６４２３７２４６９４０１４５５１９５７が、変数ｈ３３に１８９２９２１０５１０３６０４０６２２６０５７６５９３７２４７２２３０８８５１７５４２１０７７００９が、変数ｈ３４に１８９２６９６７３２７９３６７３０１７８２５０５３７８８４８６２１３７８１５１８８７１８１４０６７３が、変数ｈ３５に１８９３４０６３７６３２７２１２６４５０６２３７８７６００２３３８４３５２７３９６４００８１２４３７が、変数ｈ３６に１８９３９１２０５５９７６１８７６８０１０５４２９２５０６８８１７００８８５４１５２８７７０１０４１が、変数ｈ３７に１８９２８８１６３１５７１０６２３５３００８９４６０６０７６０８７９７３３７０８１８００６３２４７３が、変数ｈ３８に１８９２９６５６５３８５７０９８２７２０４３８０７２８０９６５２０７２２０３８５７５７１９４１７８９が、変数ｈ３９に１８９３３３５２９３３８６２１７６６０６３３１２３０５３１１８９５７９１８６００７９８３０２４２４９が、変数ｈ４０に１８９３２３１０６６３２７４９９４４４５５９９７４３１８００３２０７９９３７１４７６８７８０５１２１が、変数ｈ４１に１８９２６３８１９４５７０２７２６４０６１８２６２４５５７０２２３４４１１３０３７９５７９９１７０９が、変数ｈ４２に１８９３１１０２６８１７８９０９５０７２２２９６７６２６２９７５５７７３４４３１４２６６４３３６１７が、それぞれ格納される。
【００５０】
最後に、位数候補値計算装置１３は、ヤコビアン群の位数の候補値として変数ｈ１〜変数ｈ４２の内容をＨとして、Ｈ記憶ファイル１６５にまとめて格納する。
【００５１】
次に、安全性判定装置１４が、Ｈ記憶ファイル１６５からＨを取得し、Ｈに含まれる位数の候補値ｈ１、ｈ２、．．．、ｈ４２から概素数性等の安全性条件を満たす候補値ｈを検索し、ｈ記憶ファイル１６６に格納する。本実施の形態では、説明を簡明にするため、安全性条件は概素数性のみを検討する。既知の素数判定法を用いると、ｈ１１  ＝  １８９３４２２９２９０６３５１７６８３０７６４０３５５３２０４６５１０８３９７９１７１９４４２３８９が素数と判定され、安全性判定装置１４は、ｈ  ＝  ｈ１１  ＝  １８９３４２２９２９０６３５１７６８３０７６４０３５５３２０４６５１０８３９７９１７１９４４２３８９をｈ記憶ファイル１６６に格納する。
【００５２】
次に、パラメータ決定装置１５が、ａ記憶ファイル１６１、ｂ記憶ファイル１６２、ｐ記憶ファイル１６７、ｈ記憶ファイル１６６からそれぞれａ、ｂ、ｐ、ｈを取得し、図５に示す処理にしたがって動作する。
【００５３】
まず、図５のステップＳ５１において、変数ζ３にｐ＝１６３２５５５９７を法とする１の原始３乗根である１２７９９４５８７を、変数ζ７にｐ＝１６３２５５５９７を法とする１の原始７乗根である８３４２６４８をそれぞれ格納する。
【００５４】
次に、図５のステップＳ５２において、各整数ｌ＝１、２、３および各整数ｍ＝１、２、３、４、５、６、７に対して、以下のような処理を行う。
【００５５】
まず、ｌ＝１、ｍ＝１に対して、変数εにζ３  ＝  １２７９９４５８７を格納し、変数ηにζ７  ＝８３４２６４８を格納し、式  ε  ｙ３  ＋  η  ｘ７  ＋  １  ＝  １２７９９４５８７  ｙ３  ＋  ８３４２６４８  ｘ７  ＋  １  ＝０  で定義される代数曲線のヤコビアン群のランダムな元｛１５１７０７０１７  ＋  １０４６７８４９１  ｘ  ＋  １２３６４６０８３  ｘ２  ＋  １８７５３９８８  ｙ  ＋  ８７６３４４９３  ｘ３  ＋  ６１２７４３３６  ｘ  ｙ  ＋  ｘ４、  １３８７９９７８５  ＋  １４５１０５６８４  ｘ  ＋  ５８４３９５  ｘ２  ＋  ８０８２８８７３  ｙ  ＋  ３４７１５８９２  ｘ３  ＋  １２１８８５８７４  ｘｙ  ＋  ５９７８７８４４  ｘ４  ＋  ｘ２  ｙ、  １６１１６２２２４  ＋  １１７１５００９７  ｘ  ＋  １００９５６１００  ｘ２  ＋  ８９３８００６１  ｙ  ＋  １４００３２５５５  ｘ３  ＋  ４３３６７０１９  ｘ  ｙ  ＋  ｙ２  ｝を生成し、これを変数Ｇに格納し、変数Ｇに格納されている点の、ヤコビアン群におけるｈ＝１８９３４２２９２９０６３５１７６８３０７６４０３５５３２０４６５１０８３９７９１７１９４４２３８９倍を計算し、計算結果である  ｛１３３６５９４９７  ＋  １０３４２４７４６  ｘ  ＋  １３６０３２８９７  ｘ２  ＋  １３１０２９１９９  ｙ  ＋  ２４６１８８６７  ｘ３  ＋  １１４９４４０３４  ｘ  ｙ  ＋  ｘ４、  ８６１２５４２６  ＋  １２５８９１８９３  ｘ  ＋  １９５６８２６９  ｘ２  ＋  ２７０４４３１４  ｙ  ＋  ８０４２０９６０  ｘ３  ＋  １３７５６２０９２  ｘ  ｙ  ＋  ｘ２  ｙ、  ５３６０４１１２  ＋  ６５９９０５０１  ｘ  ＋  ５１２６９２２１  ｘ２  ＋  ５５２７１５０２  ｙ  ＋  ７９７４２３３  ｘ３  ＋  ８４９２２２２０  ｘ  ｙ  ＋  ｙ２  ｝  を変数Ｇに格納する。
【００５６】
変数Ｇの上記内容がヤコビアン群における単位元｛｝に等しくないので、次に、ｌ＝１、ｍ＝２に対して、変数εにζ３  ＝  １２７９９４５８７を格納し、変数ηにζ７２  ＝  ８３４２６４８２  ｍｏｄ  １６３２５５５９７  ＝  １５９７７２０７３を格納し、上記の処理を繰り返す。
【００５７】
本実施の形態の場合、ｌ＝２、ｍ＝２に対して、ε＝３５２６１００９、η＝１５９７７２０７３となり、ランダムに生成された点Ｇ  ＝  ｛４５６８０７１  ＋  １４１８４３７１５  ｘ  ＋  ６８２５６７４３  ｘ２  ＋  ７１９０３５０１  ｙ  ＋  １２８９５３７８３  ｘ３  ＋  １０７８１９６０  ｘ  ｙ  ＋  ｘ４、  ４８２７２７８８  ＋  ４５６１５２２９  ｘ  ＋  １５０６９２０３４  ｘ２  ＋  ５３９７３３５０  ｙ  ＋  １１１１４７６５  ｘ３  ＋  ７８５５０１３０  ｘ  ｙ  ＋  ６１３３１３５４  ｘ４  ＋  ｘ２  ｙ、１１７５５２８０７  ＋  １３５４４８９０７  ｘ  ＋  ６４０７４７１１  ｘ２  ＋  １４１０５８９７４  ｙ  ＋  ４９２０８２４６  ｘ３  ＋  ９３９４０３１７  ｘ  ｙ  ＋  ｙ２  ｝のｈ＝１８９３４２２９２９０６３５１７６８３０７６４０３５５３２０４６５１０８３９７９１７１９４４２３８９倍が単位元｛｝となり、パラメータ決定装置１５は安全な代数曲線のパラメータとして、ｐ＝１６３２５５５９７、ε＝３５２６１００９、η＝１５９７７２０７３を出力する。
【００５８】
最後に、パラメータ決定装置１５の出力したパラメータｐ＝１６３２５５５９７、ε＝３５２６１００９、η＝１５９７７２０７３が出力装置１８より出力される。
【００５９】
次に、本発明の第２の実施の形態について詳細に説明する。
本発明の第２の実施の形態は、
（ａ）ａ記憶ファイル１６１、ｂ記憶ファイル１６２から、それぞれ素数ａ、ｂを取得し、円のａｂ分体におけるスティッケルバーガー要素ωを演算するスティッケルバーガー要素計算手順と、
（ｂ）前記スティッケルバーガー要素計算手順により演算されたスティッケルバーガー要素ωをω記憶ファイル１６３に記憶する手順と、
（ｃ）ａ記憶ファイル１６１、ｂ記憶ファイル１６２、ｎ記憶ファイル１６８、ω記憶ファイル１６３からそれぞれ素数ａ、素数ｂ、暗号鍵のサイズｎ、スティッケルバーガー要素ωを取得し、２つの異なる素数ａ、素数ｂに対するヤコビ和候補値ｊおよびヤコビ和候補値ｊに対応する素数ｐを演算するヤコビ和候補値計算手順と、（ｄ）前記ヤコビ和候補値計算手順により演算された素数ｐ、ヤコビ和候補値ｊをそれぞれｐ記憶ファイル１６７、およびｊ記憶ファイル１６４に記憶する手順と、
（ｅ）ａ記憶ファイル１６１、ｂ記憶ファイル１６２、ｊ記憶ファイル１６４から、それぞれ素数ａ、素数ｂ、ヤコビ和候補値ｊを取得し、素数ａ、素数ｂで指定される代数曲線のヤコビアン群の位数の複数の候補値からなる集合Ｈを演算する位数候補値計算手順と、
（ｆ）前記位数候補値計算手順により演算された集合ＨをＨ記憶ファイル１６５に記憶する手順と、
（ｇ）Ｈ記憶ファイル１６５から集合Ｈを取得し、集合Ｈの中から概素数性等の安全性条件を満たす候補値ｈを検索する安全性判定手順と、
（ｈ）前記安全性判定手順により検索された候補値ｈをｈ記憶ファイル１６６に記憶する手順と、
（ｉ）ａ記憶ファイル１６１、ｂ記憶ファイル１６２、ｐ記憶ファイル１６７、ｈ記憶ファイル１６６からそれぞれ素数ａ、素数ｂ、素数ｐ、候補値ｈを取得し、素数ａ、素数ｂ、素数ｐで指定される代数曲線でそのヤコビアン群の位数が候補値ｈと一致する代数曲線のパラメータを演算するパラメータ決定手順と、
を含むことを特徴とする代数曲線暗号における安全なパラメータの生成方法である。
【００６０】
次に、本発明の第３の実施の形態について図面を参照して詳細に説明する。
図６は、本発明の第３の実施の形態を示すブロック図である。
図６を参照すると、本発明の第３の実施の形態は、本発明の第２の実施の形態の各手順をコンピュータ１００に実行させるプログラムを記録する記録媒体１３０である。このプログラムは、コンピュータ１００の記憶装置にロードされ実行される。
【００６１】
【発明の効果】
本発明の効果は、従来使用できなかった高次の複雑な代数曲線を代数曲線暗号に用いることができ、代数曲線暗号の安全性を向上することである。
【００６２】
その理由は、αＹａ  ＋βＸｂ  ＋  １  ＝  ０という形の定義方程式をもつ代数曲線のクラスから、そのヤコビアン群の位数がほぼ素数である代数曲線を効率的に探索することが可能となり、使用できる代数曲線の範囲が広がり、攻撃者の解読作業が分散増加するからである。
【図面の簡単な説明】
【図１】本発明の第１の実施の形態を示すブロック図である。
【図２】スティッケルバーガー要素計算装置の動作を示すフローチャートである。
【図３】ヤコビ和候補値計算装置の動作を示すフローチャートである。
【図４】位数候補値計算装置の動作を示すフローチャートである。
【図５】パラメータ決定装置の動作を示すフローチャートである。
【図６】本発明の第３の実施の形態を示すブロック図である。
【符号の説明】
１１    スティッケルバーガー要素計算装置
１２    ヤコビ和候補値計算装置
１３    位数候補値計算装置
１４    安全性判定装置
１５    パラメータ決定装置
１６    メモリ
１７    入力装置
１８    出力装置
１９    中央処理装置
１００    コンピュータ
１３０    記録媒体
１６１    ａ記憶ファイル
１６２    ｂ記憶ファイル
１６３    ω記憶ファイル
１６４    ｊ記憶ファイル
１６５    Ｈ記憶ファイル
１６６    ｈ記憶ファイル
１６７    ｐ記憶ファイル
１６８    ｎ記憶ファイル
【図１】
0003551853.tif 000002
【図２】
0003551853.tif 000003
【図３】
0003551853.tif 000004
【図４】
0003551853.tif 000005
【図５】
0003551853.tif 000006
【図６】
0003551853.tif 000007