楕円曲線生成方法、楕円曲線生成装置及び楕円曲線生成プログラム
【課題】楕円曲線を効率良く生成すること。
【解決手段】楕円曲線生成装置は、算出部と生成部とを有する。算出部は、Ｂｒｅｚｉｎｇ−Ｗｅｎｇ法における埋め込み次数を入力値として受け付け、受け付けた入力値に対して、Ｂｒｅｚｉｎｇ−Ｗｅｎｇ法における部分群位数多項式の次数が所定値以下となる判別式を、埋め込み次数と判別式に係る円分体の拡大次数に基づいて算出する。生成部は、算出部により算出された判別式と埋め込み次数とを用いて、Ｂｒｅｚｉｎｇ−Ｗｅｎｇ法に基づいて楕円曲線を生成する。
【解決手段】楕円曲線生成装置は、算出部と生成部とを有する。算出部は、Ｂｒｅｚｉｎｇ−Ｗｅｎｇ法における埋め込み次数を入力値として受け付け、受け付けた入力値に対して、Ｂｒｅｚｉｎｇ−Ｗｅｎｇ法における部分群位数多項式の次数が所定値以下となる判別式を、埋め込み次数と判別式に係る円分体の拡大次数に基づいて算出する。生成部は、算出部により算出された判別式と埋め込み次数とを用いて、Ｂｒｅｚｉｎｇ−Ｗｅｎｇ法に基づいて楕円曲線を生成する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、楕円曲線生成方法、楕円曲線生成装置及び楕円曲線生成プログラムに関する。
【背景技術】
【０００２】
従来、情報漏洩などを防止するために、公開鍵暗号が利用されている。この公開鍵暗号は、対になる公開鍵と秘密鍵とを用いてデータの暗号化、復号化を行う方式である。公開鍵は、情報を暗号化するために受信者によって公開されている鍵であり、秘密鍵は、公開鍵により暗号化された情報を復号化するための鍵である。
【０００３】
さらに近年では、公開鍵暗号の一つとして、個人のＩＤ（Identification）やメールアドレスなどを公開鍵とするＩＤベース暗号などを構築できるペアリング暗号が注目されている。このペアリング暗号は、楕円曲線上の２点に対するペアリングと呼ばれる演算を用いる暗号技術である。このペアリング暗号を実装するには、ペアリング暗号に適した楕円曲線を生成することを要する。なお、ペアリング暗号に適した楕円曲線は、ペアリングフレンドリ曲線とも呼ばれる。
【０００４】
ペアリング暗号に適した楕円曲線を生成する方法として、Ｂｒｅｚｉｎｇ−Ｗｅｎｇ法（以下、ＢＷ法と省略する）がある。ＢＷ法では、埋め込み次数ｋと判別式Ｄとが入力値として用いられる。なお、埋め込み次数ｋは、拡大体の最小の拡大次数である。
【０００５】
ここで、ＢＷ法の手順について説明する。ＢＷ法では、入力値である埋め込み次数ｋ及び判別式Ｄに対して定まる多項式の組（ｔ（ｘ）、ｒ（ｘ）、ｑ（ｘ））を用意する。そして、整数ｘ０を選択し、ｘにｘ０を代入することで整数の組（ｔ、ｒ、ｑ）＝（ｔ（ｘ０）、ｒ（ｘ０）、ｑ（ｘ０））を生成する。このうち、ｔはトレース、ｒは部分群位数、ｑは定義体位数とそれぞれ呼ばれる。そして、整数の組（ｔ、ｒ、ｑ）から、楕円曲線Ｅの位数がｑ＋１−ｔとなる有限体ＧＦ（ｑ）上の楕円曲線Ｅを生成する。ここでは、非特許文献１に記載されるように、整数の組（ｔ、ｒ、ｑ）から楕円曲線Ｅを生成するＣＭ（Complex Multiplication）法を用いる。なお、ＣＭ法は、虚数乗法とも呼ばれる。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】Ｄ．Ｆｒｅｅｍａｎ，Ｍ．Ｓｃｏｔｔ ａｎｄ Ｅ．Ｔｅｓｋｅ，“Ａ ｔａｘｏｎｏｍｙ ｏｆ ｐａｉｒｉｎｇ−ｆｒｉｅｎｄｌｙ ｅｌｌｉｐｔｉｃ ｃｕｒｖｅｓ”，Ｊ．Ｃｒｙｐｔｏｌｏｇｙ ２３（２０１０），ｐｐ．２２４−２８０．
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、上記従来技術では、楕円曲線を効率良く生成することが難しいという問題があった。例えば、ＢＷ法で生成される整数の組（ｔ、ｒ、ｑ）のそれぞれの値は、入力値である埋め込み次数ｋ及び判別式Ｄによって変化するので、ペアリング暗号に適したサイズにならない場合があった。特に、部分群位数ｒの値はペアリング暗号の安全性に関わるパラメータであり、この部分群位数ｒが大きくなれば安全性は高まるが、あまりに大きな値になると、暗号化、復号化にかかる処理負荷が大きくなる。
【０００８】
ここで、判別式Ｄが大きくなると部分群位数ｒも大きくなりやすいため、判別式Ｄには１を入力することが一般的である。そして、判別式Ｄに１を入力しても部分群位数ｒが適したサイズにならない場合には、部分群位数ｒが適したサイズになるまで埋め込み次数ｋに入力する値を変えていくことになる。しかし、埋め込み次数ｋはペアリング暗号の安全性に関わるパラメータであるため、現代のコンピュータの処理性能を考慮すると、埋め込み次数ｋとしては２〜６程度が推奨される。このため、従来技術では、埋め込み次数ｋ及び判別式Ｄとして入力される値の組合せは限られており、楕円曲線を効率良く生成することはできなかった。
【０００９】
開示の技術は、上記に鑑みてなされたものであって、楕円曲線を効率良く生成することができる楕円曲線生成方法、楕円曲線生成装置及び楕円曲線生成プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１０】
本願の開示する楕円曲線生成方法は、Ｂｒｅｚｉｎｇ−Ｗｅｎｇ法における埋め込み次数を入力値として受け付ける。また、楕円曲線生成方法は、受け付けた入力値に対して、Ｂｒｅｚｉｎｇ−Ｗｅｎｇ法における部分群位数多項式の次数が所定値以下となる判別式を、埋め込み次数と判別式に係る円分体の拡大次数に基づいて算出する。また、楕円曲線生成方法は、前記判別式を算出する処理により算出された判別式と前記入力値とを用いて、Ｂｒｅｚｉｎｇ−Ｗｅｎｇ法に基づいて楕円曲線を生成する。
【発明の効果】
【００１１】
本願の開示する技術の一つの態様によれば、楕円曲線を効率良く生成することができるという効果を奏する。
【図面の簡単な説明】
【００１２】
【図１】図１は、実施例１に係る楕円曲線生成装置の機能構成を示すブロック図である。
【図２】図２は、実施例１に係る楕円曲線生成装置の処理手順を示すフローチャートである。
【図３】図３は、実施例１に係る楕円曲線生成装置の効果を説明するための図である。
【図４】図４は、楕円曲線生成プログラムを実行するコンピュータの一例を示す図である。
【発明を実施するための形態】
【００１３】
以下に、本願の開示する楕円曲線生成方法、楕円曲線生成装置及び楕円曲線生成プログラムの実施例を図面に基づいて詳細に説明する。なお、この実施例によりこの発明が限定されるものではない。各実施例は、処理内容を矛盾させない範囲で適宜組み合わせることが可能である。
【実施例１】
【００１４】
実施例１に係る楕円曲線生成装置の機能構成の一例について説明する。図１は、実施例１に係る楕円曲線生成装置の機能構成を示すブロック図である。図１に示すように、この楕円曲線生成装置１００は、記憶部１１０と、制御部１２０とを有する。
【００１５】
記憶部１１０は、算出データ１１１を有する。記憶部１１０は、例えば、ＲＡＭ（Random Access Memory）、ＲＯＭ（Read Only Memory）、フラッシュメモリ（Flash Memory）などの半導体メモリ素子、ハードディスクや光ディスクなどの記憶装置に対応する。
【００１６】
算出データ１１１は、後述する算出部１２２により算出された算出結果を示すデータである。例えば、算出データ１１１は、入力値である埋め込み次数ｋと所定値ｍと、算出結果である判別式Ｄとを対応づけたデータである。具体的には、算出データ１１１は、例えば、埋め込み次数「ｋ＝３」と、所定値「ｍ＝８」と、判別式「Ｄ＝１，３，５，１５」とを対応づけたデータである。つまり、算出データ１１１は、埋め込み次数ｋ＝３及び所定値ｍ＝８が入力値として算出部１２２に入力された場合に、４つの判別式Ｄ＝１，３，５，１５が算出されたことを示す。
【００１７】
制御部１２０は、受付部１２１と、算出部１２２と、生成部１２３と、出力部１２４とを有する。制御部１２０の機能は、例えば、ＡＳＩＣ（Application Specific Integrated Circuit）やＦＰＧＡ（Field Programmable Gate Array）などの集積回路により実現することができる。また、制御部１２０の機能は、例えば、ＣＰＵ（Central Processing Unit）が所定のプログラムを実行することで実現することができる。
【００１８】
受付部１２１は、各種情報の入力を受け付ける。例えば、受付部１２１は、埋め込み次数ｋと所定値ｍとを入力値として受け付ける。受付部１２１は、受け付けた入力値を算出部１２２に出力する。
【００１９】
算出部１２２は、受付部１２１によって受け付けた埋め込み次数ｋと所定値ｍとを用いて、ＢＷ法における部分群位数多項式ｒ（ｘ）の次数が所定値ｍ以下となる判別式Ｄを、埋め込み次数ｋと判別式Ｄに係る円分体の拡大次数に基づいて算出する。
【００２０】
ここで、部分群位数多項式ｒ（ｘ）の次数が所定値ｍ以下となる判別式Ｄを算出するのは、部分群位数ｒがペアリング暗号の安全性に関わるパラメータであり、選択できる値には制限があるからである。つまり、多項式ｒ（ｘ）の次数が大きい場合には、部分群位数ｒの値が大きくなってしまい、ペアリング暗号に適したサイズの部分群位数ｒを得ることができない。また、埋め込み次数ｋもペアリング暗号の安全性に関わるパラメータであり、選択できる値には制限がある。これに対して、判別式Ｄには、このような制限が無い。このため、発明者らは、多項式ｒ（ｘ）の次数に上限値を設定することで、ペアリング暗号に適したサイズの部分群位数ｒを出力する判別式Ｄを埋め込み次数ｋから求めることができ、楕円曲線を効率良く生成することができるという着想に至った。
【００２１】
例えば、算出部１２２は、埋め込み次数ｋの倍数ｎのうち、オイラー関数φ（ｎ）の値が所定値ｍ以下となる整数ｎを選択する。算出部１２２は、円分体Ｑ（ζｎ）に含まれる虚２次体Ｋの定義多項式ｆ（ｘ）＝ｘ２＋ａｘ＋ｂの係数ａ及びｂを算出する。算出部１２２は、ｆ（ｘ）の係数ａ及びｂから（４ｂ−ａ２）の値を算出し、算出した値の非平方因子を判別式Ｄとして算出する。なお、ζｋは、１の原始ｋ乗根である。また、ｎは埋め込み次数ｋの倍数であるので、円分体Ｑ（ζｎ）はζｋを含む。また、ｆ（ｘ）は、Ｋ＝Ｑ［ｘ］／（ｆ（ｘ））を満たす多項式である。
【００２２】
以下において、算出部１２２の処理を詳細に説明する。ここでは、一例として、埋め込み次数ｋ＝３かつ所定値ｍ＝８の場合を説明する。なお、埋め込み次数ｋ及び所定値ｍの値については、この例示に限定されるものではなく、楕円曲線生成装置１００を利用する者が任意の値に設定して良い。
【００２３】
まず、算出部１２２が整数ｎを選択する処理について説明する。例えば、算出部１２２は、埋め込み次数ｋ＝３の倍数ｎ＝３，６，９，１２，１５・・・を求める。そして、算出部１２２は、求めた倍数ｎについて、下記の式（１）を用いてφ（ｎ）を算出する。なお、式（１）において、倍数ｎは正整数である。また、ｐ１，ｐ２・・・ｐｉは、倍数ｎの相違なる全ての素因子である。
【００２４】
φ（ｎ）＝ｎ（１−１／ｐ１）（１−１／ｐ２）・・・（１−１／ｐｉ）・・・（１）
【００２５】
例えば、算出部１２２は、式（１）を用いてφ（３）＝２，φ（６）＝２，φ（９）＝６，φ（１２）＝４，φ（１５）＝８・・・を算出する。そして、算出部１２２は、φ（ｎ）≦ｍとなる倍数ｎを選択する。つまり、埋め込み次数ｋ＝３かつ所定値ｍ＝８の場合には、算出部１２２は、ｎ＝３，６，９，１２，１５，１８，２４，３０を選択する。なお、以下では、説明の都合上、倍数ｎ＝１５の場合を説明するが、算出部１２２は、選択した他の倍数ｎについても同様に処理するものとする。また、算出部１２２が倍数ｎを選択する方法は、上記の方法に限定されるものではない。例えば、算出部１２２は、φ（ｎ）≦ｍとなる値を算出した後に、算出した値のうち埋め込み次数ｋの倍数となる倍数ｎを選択するようにしても良い。具体的には、所定値ｍ＝８の場合には、算出部１２２は、φ（ｎ）≦８となる値として、２，３，４，５，６，７，８，９，１０，１２，１４，１５，１６，１８，２０，２４，３０を算出する。そして、算出部１２２は、φ（ｎ）≦８となる値のうち、埋め込み次数ｋ＝３の倍数ｎとして、３，６，９，１２，１５，１８，２４，３０を選択する。
【００２６】
このように、算出部１２２は、埋め込み次数ｋの倍数ｎのうち、オイラー関数φ（ｎ）の値が所定値ｍ以下となる整数ｎを選択する。例えば、埋め込み次数ｋ＝３かつ所定値ｍ＝８の場合には、算出部１２２は、整数ｎとして、３，６，９，１２，１５，１８，２４，３０を選択する。
【００２７】
また、算出部１２２が、円分体Ｑ（ζｎ）に含まれる虚２次体Ｋの定義多項式ｆ（ｘ）＝ｘ２＋ａｘ＋ｂの係数ａ及びｂを算出する処理について説明する。例えば、算出部１２２は、倍数ｎ＝１５の場合には、円分体Ｑ（ζ１５）に含まれる虚２次体Ｋの定義多項式ｆ（ｘ）＝ｘ２＋ａｘ＋ｂの係数ａ及びｂを算出する。ここで、ガロア理論より円分体Ｑ（ζｎ）に含まれる虚２次体Ｋは群（Ｚ／ｎＺ）＊の指数２の部分群に対応することが知られている。よって、算出部１２２は、群（Ｚ／ｎＺ）＊を生成し、生成した群（Ｚ／ｎＺ）＊の指数２の部分群を生成することで、虚２次体Ｋを生成することができる。以下で、虚２次体Ｋの定義多項式ｆ（ｘ）＝ｘ２＋ａｘ＋ｂの係数ａ及びｂの具体的な算出方法を説明する。
【００２８】
例えば、整数ｎ＝１５を選択した場合を説明する。円分体Ｑ（ζ１５）の次数は、φ（ｎ）に等しいので、φ（１５）＝８である。群（Ｚ／ｎＺ）＊は、１〜ｎの整数であり、かつ、ｎの素因数で割り切れる数を除外したものである。よって、算出部１２２は、１〜１５の整数うち、１５の素因数「３」及び「５」で割り切れる数を除外して、群（Ｚ／１５Ｚ）＊＝｛１，２，４，７，８，１１，１３，１４｝を生成する。そして、算出部１２２は、生成した群（Ｚ／ｎＺ）＊の指数２の部分群を生成する。
【００２９】
ここで、群（Ｚ／ｎＺ）＊の指数２の部分群を生成する処理について説明する。算出部１２２は、群（Ｚ／ｎＺ）＊から元ｇを一つ選択し、選択した元ｇに元ｇを乗算する。算出した値が倍数ｎより小さい場合には、算出部１２２は、算出した値をそのまま取得する。一方、算出した値が倍数ｎより大きい場合には、算出部１２２は、算出した値が倍数ｎより小さくなるまで算出した値から倍数ｎを減算し、減算した値を取得する。算出部１２２は、取得した値に対してさらに元ｇを乗算し、算出した値を取得する。算出部１２２は、取得した値が「１」になるまで、取得した値に元ｇを乗算する処理を繰り返す。取得した値が「１」になった場合には、算出部１２２は、取得した値と選択した元ｇとを新たな元として部分群＜ｇ＞を生成する。また、算出部１２２は、群（Ｚ／ｎＺ）＊に含まれる他の元についても同様に部分群を生成する。
【００３０】
例えば、群（Ｚ／１５Ｚ）＊について、算出部１２２が元ｇ＝２を選択した場合を説明する。算出部１２２は、「２×２＝４」を算出する。「４」は「１５」より小さいので、算出部１２２は、「４」を取得する。算出部１２２は、「４×２＝８」を算出する。「８」は「１５」より小さいので、算出部１２２は、「８」を取得する。算出部１２２は、「８×２＝１６」を算出する。算出された「１６」は「１５」より大きいので、算出部１２２は、「１６−１５＝１」を算出し、算出した「１」を取得する。ここで取得した値が「１」であるので、算出部１２２は、取得した値と選択した元ｇ＝２とを新たなを元として部分群＜２＞＝｛１，２，４，８｝を生成する。なお、この部分群＜２＞に含まれる元の個数は「４」である。また、算出部１２２は、群（Ｚ／１５Ｚ）＊に含まれる他の元についても同様に、指数２の部分群を生成する。例えば、算出部１２２は、群（Ｚ／１５Ｚ）＊から元ｇ＝４を選択し、部分群＜４＞＝｛１，４｝を生成する。この部分群＜４＞に含まれる元の個数は「２」であるため、指数２の部分群にならないことに注意しておく。
【００３１】
例えば、算出部１２２は、指数２の部分群＜２＞に対応する虚２次体Ｋを選択する。この場合、算出部１２２は、ガロア理論に基づき定義多項式ｆ（ｘ）の２つの解ｓ及びｓ〜を求める。この解ｓは、部分群＜２＞に含まれる元を用いると、ｓ＝ζ＋ζ２＋ζ４＋ζ８となる。また、解ｓ〜は、群（Ｚ／ｎＺ）＊に含まれる元のうち、部分群＜２＞に含まれる元以外の元を用いると、ｓ〜＝ζ７＋ζ１１＋ζ１３＋ζ１４となる。なお、ここでは、ζ１５をζと略記する。
【００３２】
例えば、算出部１２２は、定義多項式ｆ（ｘ）＝ｘ２＋ａｘ＋ｂの２つの解と係数との関係式と、ζ１５＝１という性質とを用いて、係数ａ及びｂを算出する。なお、この関係式は、下記の式（２）及び（３）によって表される。
【００３３】
ａ＝−（ｓ＋ｓ〜）・・・（２）
【００３４】
ｂ＝ｓ×ｓ〜・・・（３）
【００３５】
例えば、算出部１２２は、ｆ（ｘ）の２つの解ｓ及びｓ〜を式（２）に代入し、ζ１５＝１という性質を用いて演算することで、係数ａ＝０を算出する。また、例えば、算出部１２２は、ｆ（ｘ）の２つの解ｓ及びｓ〜を式（３）に代入し、ζ１５＝１という性質を用いて演算することで、係数ｂ＝１５を算出する。
【００３６】
なお、算出部１２２は、部分群＜４＞を選択した場合、この部分群は指数２の部分群ではないので、定義多項式ｆ（ｘ）の２つの解ｓ及びｓ〜を求める処理を行わずに、他の部分群についての処理に移行する。
【００３７】
このように、算出部１２２は、円分体Ｑ（ζｎ）に含まれる虚２次体Ｋの定義多項式ｆ（ｘ）＝ｘ２＋ａｘ＋ｂの係数ａ及びｂを算出する。例えば、整数ｎ＝１５を選択し、群（Ｚ／１５Ｚ）＊の指数２の部分群＜２＞を用いた場合には、算出部１２２は、定義多項式ｆ（ｘ）＝ｘ２＋ａｘ＋ｂの係数ａ＝０及びｂ＝１５を算出する。また、算出部１２２は、他の部分群についても同様に処理を実行し、他の部分群に対応する定義多項式ｆ（ｘ）の係数ａ及びｂを算出する。
【００３８】
また、算出部１２２が判別式Ｄを算出する処理について説明する。例えば、算出部１２２は、定義多項式ｆ（ｘ）の係数ａ及びｂから（４ｂ−ａ２）の値を算出し、算出した値の非平方因子を判別式Ｄとして算出する。例えば、算出部１２２は、下記の式（４）を用いて、判別式Ｄを算出する。なお、式（４）において、ｙ２は、平方因子である。
【００３９】
４ｂ−ａ２＝Ｄｙ２・・・（４）
【００４０】
例えば、算出した係数がａ＝０及びｂ＝１５であった場合には、４ｂ−ａ２＝１５×２２となるので、算出部１２２は、非平方因子１５を判別式Ｄ＝１５として算出する。また、算出部１２２は、定義多項式ｆ（ｘ）の係数ａ及びｂを算出するごとに、判別式Ｄを算出する。
【００４１】
以上のように、算出部１２２は、多項式ｒ（ｘ）の次数が所定値ｍ以下となる判別式Ｄを算出する。例えば、埋め込み次数ｋ＝３かつ所定値ｍ＝８の場合には、算出部１２２は、オイラー関数φ（ｎ）の値が所定値ｍ以下となる倍数ｎ＝３，６，９，１２，１５，１８，２４，３０を選択する。算出部１２２は、選択した倍数ｎについて、円分体Ｑ（ζｎ）に含まれる虚２次体Ｋの定義多項式ｆ（ｘ）＝ｘ２＋ａｘ＋ｂの係数ａ及びｂを算出する。そして、算出部１２２は、定義多項式ｆ（ｘ）の係数ａ及びｂを算出するごとに、（４ｂ−ａ２）の値の非平方因子を算出し、判別式Ｄ＝１，３，５，１５を求める。
【００４２】
また、算出部１２２は、算出結果を算出データ１１１として記憶部１１０に格納する。例えば、算出部１２２は、埋め込み次数「ｋ＝３」と、所定値「ｍ＝８」と、判別式「Ｄ＝１，３，５，１５」とを対応づけて、算出データ１１１として記憶部１１０に格納する。
【００４３】
生成部１２３は、算出した判別式Ｄと埋め込み次数ｋとを用いて、Ｂｒｅｚｉｎｇ−Ｗｅｎｇ法（以下、ＢＷ法と省略する）に基づいて楕円曲線を生成する。例えば、生成部１２３は、記憶部１１０に記憶された算出データ１１１から埋め込み次数ｋと判別式Ｄとを取得する。そして、生成部１２３は、例えば、非特許文献１に記載されるように、取得した埋め込み次数ｋと判別式Ｄとを用いて楕円曲線を生成するＢＷ法に基づいて、楕円曲線を生成する。
【００４４】
出力部１２４は、各種情報を出力する。例えば、出力部１２４は、生成部１２３により生成された楕円曲線を示す情報を出力する。また、例えば、出力部１２４は、埋め込み次数ｋと、判別式Ｄと、楕円曲線を示す情報とを対応づけて出力するようにしても良い。
【００４５】
次に、実施例１に係る楕円曲線生成装置１００の処理手順について説明する。図２は、実施例１に係る楕円曲線生成装置の処理手順を示すフローチャートである。図２に示す処理は、例えば、楕円曲線生成装置１００に電源から電力が供給されている間、所定時間間隔で実行される。
【００４６】
図２に示すように、入力値である埋め込み次数ｋ及び所定値ｍを受け付けると（ステップＳ１０１，Ｙｅｓ）、算出部１２２は、埋め込み次数ｋの倍数ｎのうち、オイラー関数φ（ｎ）の値が所定値ｍ以下となる整数ｎを選択する（ステップＳ１０２）。例えば、埋め込み次数ｋ＝３かつ所定値ｍ＝８の場合には、算出部１２２は、整数ｎとして、３，６，９，１２，１５，１８，２４，３０を選択する。
【００４７】
算出部１２２は、円分体Ｑ（ζｎ）に含まれる虚２次体Ｋの定義多項式ｆ（ｘ）＝ｘ２＋ａｘ＋ｂの係数ａ及びｂを算出する（ステップＳ１０３）。つまり、選択した整数ｎに対して群（Ｚ／ｎＺ）＊を生成し、生成した群（Ｚ／ｎＺ）＊の指数２の部分群を生成する。算出部１２２は、部分群に含まれる元の個数と、円分体Ｑ（ζｎ）の次数を虚２次体の次数で除算した値とが一致する場合に、虚２次体Ｋが存在すると判定する。虚２次体Ｋが存在する部分群について、算出部１２２は、ガロア理論に基づき定義多項式ｆ（ｘ）＝ｘ２＋ａｘ＋ｂの係数ａ及びｂを算出する。なお、虚２次体Ｋが存在する部分群が複数存在する場合には、他の部分群についても同様に処理を実行し、他の部分群に対応する定義多項式ｆ（ｘ）の係数ａ及びｂを算出する。また、選択した整数ｎが複数存在する場合には、他の整数ｎについても同様に処理を実行し、他の部分群に対応する定義多項式ｆ（ｘ）の係数ａ及びｂを算出する。
【００４８】
算出部１２２は、定義多項式ｆ（ｘ）の係数ａ及びｂから（４ｂ−ａ２）の値を算出し、算出した値の非平方因子を判別式Ｄとして算出する（ステップＳ１０４）。なお、算出部１２２は、定義多項式ｆ（ｘ）の係数ａ及びｂを算出するごとに、判別式Ｄを算出する。また、算出部１２２は、算出結果を算出データ１１１として記憶部１１０に格納する。
【００４９】
生成部１２３は、算出した判別式Ｄと埋め込み次数ｋとを用いて、ＢＷ法に基づいて楕円曲線を生成する（ステップＳ１０５）。例えば、生成部１２３は、記憶部１１０に記憶された算出データ１１１から埋め込み次数ｋと判別式Ｄとを取得する。そして、生成部１２３は、例えば、非特許文献１に記載されるように、取得した埋め込み次数ｋと判別式Ｄとを用いて楕円曲線を生成するＢＷ法に基づいて、楕円曲線を生成する。
【００５０】
なお、ステップＳ１０４の処理において、算出部１２２は、定義多項式ｆ（ｘ）の係数ａ及びｂを算出するごとに判別式Ｄを算出するものと説明したが、これに限定されるものではない。例えば、ステップＳ１０３の処理において、定義多項式ｆ（ｘ）の係数ａ及びｂを複数算出した後に、ステップＳ１０４の処理において、算出部１２２は、判別式Ｄを算出するようにしても良い。
【００５１】
次に、実施例１に係る楕円曲線生成装置１００の効果について説明する。楕円曲線生成装置１００は、Ｂｒｅｚｉｎｇ−Ｗｅｎｇ法における埋め込み次数を入力値として受け付ける。また、楕円曲線生成装置１００は、受け付けた入力値に対して、Ｂｒｅｚｉｎｇ−Ｗｅｎｇ法における部分群位数多項式の次数が所定値以下となる判別式を、埋め込み次数と判別式に係る円分体の拡大次数に基づいて算出する。また、楕円曲線生成装置１００は、算出した判別式と入力値とを用いて、Ｂｒｅｚｉｎｇ−Ｗｅｎｇ法に基づいて楕円曲線を生成する。このように、楕円曲線生成装置１００は、多項式ｒ（ｘ）の次数に上限値を設定することで、ペアリング暗号に適したサイズの部分群位数ｒを出力する判別式Ｄを埋め込み次数ｋから求めることができ、楕円曲線を効率良く生成することができる。
【００５２】
図３は、実施例１に係る楕円曲線生成装置の効果を説明するための図である。図３は、楕円曲線生成装置１００により算出される判別式Ｄの値と、生成される楕円曲線の個数とを対応づけて示す。図３に示すように、埋め込み次数ｋ＝３かつ所定値ｍ＝８の場合には、楕円曲線生成装置１００は、判別式Ｄ＝１，３，５，１５を算出する。この判別式Ｄ＝１，３，５，１５の値に対して、ＢＷ法において得られる多項式ｒ（ｘ）の次数は、それぞれ４，４，８，８となる。多項式ｒ（ｘ）の次数が多いほど生成される楕円曲線の個数は少なくなることが知られており、得られる楕円曲線の個数の比は、判別式Ｄ＝１のときを１とすると、判別式Ｄ＝１，３，５，１５の値に対して、それぞれ１，１，０．５，０．５となる。従来のＢＷ法においては、判別式Ｄには１を入力することが一般的であったため、得られる楕円曲線の個数の比は１である。これに対して、楕円曲線生成装置１００により算出された判別式Ｄ＝３，５，１５を用いて楕円曲線を生成すると、得られる楕円曲線の個数の比は３となる。このため、楕円曲線生成装置１００は、従来のＢＷ法と比べて３倍多くの楕円曲線を得ることができ、楕円曲線を効率良く生成することができる。
【実施例２】
【００５３】
さて、これまで本発明の実施例について説明したが、本発明は上述した実施例以外にも、その他の実施例にて実施されても良い。そこで、以下では、その他の実施例について説明する。
【００５４】
実施例１において説明した各処理のうち、自動的に行われるものとして説明した処理の全部または一部を手動的に行うこともでき、あるいは、手動的に行われるものとして説明した処理の全部または一部を公知の方法で自動的に行うこともできる。例えば、図２に示した処理手順は、受付部１２１が入力値である埋め込み次数ｋ及び所定値ｍを受け付けた場合に自動的に開始されるものとして説明したが、楕円曲線生成装置１００を利用する者が手動的に開始しても良い。この他、上述文書中や図面中で示した処理手順、制御手順、具体的名称、各種のデータやパラメータを含む情報については、特記する場合を除いて任意に変更することができる。例えば、算出データ１１１は、埋め込み次数ｋと、所定値ｍと、判別式Ｄとを対応づけると説明したが、所定値ｍを含む必要はない。つまり、算出データ１１１は、埋め込み次数ｋと、判別式Ｄとを対応づけたデータであっても良い。
【００５５】
また、図１に示した楕円曲線生成装置１００の各構成要素は機能概念的なものであり、必ずしも物理的に図示の如く構成されていることを要しない。すなわち、楕円曲線生成装置１００の分散・統合の具体的形態は図示のものに限られず、その全部または一部を、各種の負荷や使用状況などに応じて、任意の単位で機能的または物理的に分散・統合して構成することができる。例えば、図１に示した生成部１２３を楕円曲線生成装置１００が有している必要は無い。つまり、楕円曲線生成装置１００は、算出部１２２により算出された算出結果を算出データ１１１として記憶部１１０に格納しておき、格納した算出データ１１１を出力するようにしても良い。
【００５６】
また、楕円曲線生成装置１００は、楕円曲線生成装置１００の各機能を既知の情報処理装置に搭載することによって実現することもできる。既知の情報処理装置は、例えば、パーソナルコンピュータ、ワークステーション、携帯電話、ＰＨＳ（Personal Handy-phone System）端末、移動体通信端末またはＰＤＡ（Personal Digital Assistant）などの装置に対応する。
【００５７】
図４は、楕円曲線生成プログラムを実行するコンピュータの一例を示す図である。図４に示すように、コンピュータ３００は、各種演算処理を実行するＣＰＵ３０１と、ユーザからデータの入力を受け付ける入力装置３０２と、モニタ３０３とを有する。また、コンピュータ３００は、記憶媒体からプログラム等を読み取る媒体読み取り装置３０４と、他の装置と接続するためのインターフェース装置３０５と、他の装置と無線により接続するための無線通信装置３０６とを有する。また、コンピュータ３００は、各種情報を一時記憶するＲＡＭ（Random Access Memory）３０７と、ハードディスク装置３０８とを有する。また、各装置３０１〜３０８は、バス３０９に接続される。
【００５８】
ハードディスク装置３０８には、図１に示した算出部１２２及び生成部１２３の各処理部と同様の機能を有する楕円曲線生成プログラムが記憶される。また、ハードディスク装置３０８には、楕円曲線生成プログラムを実現するための各種データが記憶される。
【００５９】
ＣＰＵ３０１は、ハードディスク装置３０８に記憶された各プログラムを読み出して、ＲＡＭ３０７に展開し、各種の処理を行う。また、これらのプログラムは、コンピュータを図１に示した算出部１２２及び生成部１２３として機能させることができる。
【００６０】
なお、上記の楕円曲線生成プログラムは、必ずしもハードディスク装置３０８に記憶されている必要はない。例えば、コンピュータが読み取り可能な記録媒体に記憶されたプログラムを、コンピュータ３００が読み出して実行するようにしても良い。コンピュータが読み取り可能な記録媒体は、例えば、ＣＤ−ＲＯＭやＤＶＤディスク、ＵＳＢメモリ等の可搬型記録媒体、フラッシュメモリ等の半導体メモリ、ハードディスクドライブ等が対応する。また、公衆回線、インターネット、ＬＡＮ（Local Area Network）、ＷＡＮ（Wide Area Network）等に接続された装置にこのプログラムを記憶させておき、コンピュータ３００がこれらからプログラムを読み出して実行するようにしても良い。
【００６１】
以上の各実施例を含む実施形態に関し、さらに以下の付記を開示する。
【００６２】
（付記１）コンピュータが実行する楕円曲線生成方法であって、
Ｂｒｅｚｉｎｇ−Ｗｅｎｇ法における埋め込み次数を入力値として受け付け、受け付けた入力値に対して、Ｂｒｅｚｉｎｇ−Ｗｅｎｇ法における部分群位数多項式の次数が所定値以下となる判別式を、埋め込み次数と判別式に係る円分体の拡大次数に基づいて算出し、
前記判別式を算出する処理により算出された判別式と前記入力値とを用いて、Ｂｒｅｚｉｎｇ−Ｗｅｎｇ法に基づいて楕円曲を生成する
ことを特徴とする楕円曲線生成方法。
【００６３】
（付記２）前記判別式を算出する処理は、入力値ｋの倍数ｎのうち、オイラー関数φ（ｎ）の値が所定値以下となるｎを選択し、円分体Ｑ（ζｎ）に含まれる虚２次体Ｋの定義多項式ｆ（ｘ）＝ｘ２＋ａｘ＋ｂを算出し、ｆ（ｘ）の係数ａ及びｂから（４ｂ−ａ２）の値を算出し、算出した値の非平方因子を判別式として算出することを特徴とする付記１に記載の楕円曲線生成方法。ただし、ζｋは、１の原始ｋ乗根であり、ｆ（ｘ）は、Ｋ＝Ｑ［ｘ］／（ｆ（ｘ））となる多項式である。
【００６４】
（付記３）Ｂｒｅｚｉｎｇ−Ｗｅｎｇ法における埋め込み次数を入力値として受け付け、受け付けた入力値に対して、Ｂｒｅｚｉｎｇ−Ｗｅｎｇ法における部分群位数多項式の次数が所定値以下となる判別式を、埋め込み次数と判別式に係る円分体の拡大次数に基づいて算出する算出部と、
前記算出部により算出された判別式と前記入力値とを用いて、Ｂｒｅｚｉｎｇ−Ｗｅｎｇ法に基づいて楕円曲線を生成する生成部と
を備えたことを特徴とする楕円曲線生成装置。
【００６５】
（付記４）前記算出部は、入力値ｋの倍数ｎのうち、オイラー関数φ（ｎ）の値が所定値以下となるｎを選択し、円分体Ｑ（ζｎ）に含まれる虚２次体Ｋの定義多項式ｆ（ｘ）＝ｘ２＋ａｘ＋ｂを算出し、ｆ（ｘ）の係数ａ及びｂから（４ｂ−ａ２）の値を算出し、算出した値の非平方因子を判別式として算出することを特徴とする付記３に記載の楕円曲線生成装置。ただし、ζｋは、１の原始ｋ乗根であり、ｆ（ｘ）は、Ｋ＝Ｑ［ｘ］／（ｆ（ｘ））となる多項式である。
【００６６】
（付記５）コンピュータに、
Ｂｒｅｚｉｎｇ−Ｗｅｎｇ法における埋め込み次数を入力値として受け付け、受け付けた入力値に対して、Ｂｒｅｚｉｎｇ−Ｗｅｎｇ法における部分群位数多項式の次数が所定値以下となる判別式を、埋め込み次数と判別式に係る円分体の拡大次数に基づいて算出し、
前記判別式を算出する処理により算出された判別式と前記入力値とを用いて、Ｂｒｅｚｉｎｇ−Ｗｅｎｇ法に基づいて楕円曲を生成する
ことを特徴とする楕円曲線生成プログラム。
【００６７】
（付記６）前記判別式を算出する処理は、入力値ｋの倍数ｎのうち、オイラー関数φ（ｎ）の値が所定値以下となるｎを選択し、円分体Ｑ（ζｎ）に含まれる虚２次体Ｋの定義多項式ｆ（ｘ）＝ｘ２＋ａｘ＋ｂを算出し、ｆ（ｘ）の係数ａ及びｂから（４ｂ−ａ２）の値を算出し、算出した値の非平方因子を判別式として算出することを特徴とする付記５に記載の楕円曲線生成プログラム。ただし、ζｋは、１の原始ｋ乗根であり、ｆ（ｘ）は、Ｋ＝Ｑ［ｘ］／（ｆ（ｘ））となる多項式である。
【符号の説明】
【００６８】
１００ 楕円曲線生成装置
１１０ 記憶部
１１１ 算出データ
１２０ 制御部
１２１ 受付部
１２２ 算出部
１２３ 生成部
１２４ 出力部
３００ コンピュータ
３０１ ＣＰＵ
３０２ 入力装置
３０３ モニタ
３０４ 媒体読み取り装置
３０５ インターフェース装置
３０６ 無線通信装置
３０７ ＲＡＭ
３０８ ハードディスク装置
３０９ バス
【技術分野】
【０００１】
本発明は、楕円曲線生成方法、楕円曲線生成装置及び楕円曲線生成プログラムに関する。
【背景技術】
【０００２】
従来、情報漏洩などを防止するために、公開鍵暗号が利用されている。この公開鍵暗号は、対になる公開鍵と秘密鍵とを用いてデータの暗号化、復号化を行う方式である。公開鍵は、情報を暗号化するために受信者によって公開されている鍵であり、秘密鍵は、公開鍵により暗号化された情報を復号化するための鍵である。
【０００３】
さらに近年では、公開鍵暗号の一つとして、個人のＩＤ（Identification）やメールアドレスなどを公開鍵とするＩＤベース暗号などを構築できるペアリング暗号が注目されている。このペアリング暗号は、楕円曲線上の２点に対するペアリングと呼ばれる演算を用いる暗号技術である。このペアリング暗号を実装するには、ペアリング暗号に適した楕円曲線を生成することを要する。なお、ペアリング暗号に適した楕円曲線は、ペアリングフレンドリ曲線とも呼ばれる。
【０００４】
ペアリング暗号に適した楕円曲線を生成する方法として、Ｂｒｅｚｉｎｇ−Ｗｅｎｇ法（以下、ＢＷ法と省略する）がある。ＢＷ法では、埋め込み次数ｋと判別式Ｄとが入力値として用いられる。なお、埋め込み次数ｋは、拡大体の最小の拡大次数である。
【０００５】
ここで、ＢＷ法の手順について説明する。ＢＷ法では、入力値である埋め込み次数ｋ及び判別式Ｄに対して定まる多項式の組（ｔ（ｘ）、ｒ（ｘ）、ｑ（ｘ））を用意する。そして、整数ｘ０を選択し、ｘにｘ０を代入することで整数の組（ｔ、ｒ、ｑ）＝（ｔ（ｘ０）、ｒ（ｘ０）、ｑ（ｘ０））を生成する。このうち、ｔはトレース、ｒは部分群位数、ｑは定義体位数とそれぞれ呼ばれる。そして、整数の組（ｔ、ｒ、ｑ）から、楕円曲線Ｅの位数がｑ＋１−ｔとなる有限体ＧＦ（ｑ）上の楕円曲線Ｅを生成する。ここでは、非特許文献１に記載されるように、整数の組（ｔ、ｒ、ｑ）から楕円曲線Ｅを生成するＣＭ（Complex Multiplication）法を用いる。なお、ＣＭ法は、虚数乗法とも呼ばれる。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】Ｄ．Ｆｒｅｅｍａｎ，Ｍ．Ｓｃｏｔｔ ａｎｄ Ｅ．Ｔｅｓｋｅ，“Ａ ｔａｘｏｎｏｍｙ ｏｆ ｐａｉｒｉｎｇ−ｆｒｉｅｎｄｌｙ ｅｌｌｉｐｔｉｃ ｃｕｒｖｅｓ”，Ｊ．Ｃｒｙｐｔｏｌｏｇｙ ２３（２０１０），ｐｐ．２２４−２８０．
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、上記従来技術では、楕円曲線を効率良く生成することが難しいという問題があった。例えば、ＢＷ法で生成される整数の組（ｔ、ｒ、ｑ）のそれぞれの値は、入力値である埋め込み次数ｋ及び判別式Ｄによって変化するので、ペアリング暗号に適したサイズにならない場合があった。特に、部分群位数ｒの値はペアリング暗号の安全性に関わるパラメータであり、この部分群位数ｒが大きくなれば安全性は高まるが、あまりに大きな値になると、暗号化、復号化にかかる処理負荷が大きくなる。
【０００８】
ここで、判別式Ｄが大きくなると部分群位数ｒも大きくなりやすいため、判別式Ｄには１を入力することが一般的である。そして、判別式Ｄに１を入力しても部分群位数ｒが適したサイズにならない場合には、部分群位数ｒが適したサイズになるまで埋め込み次数ｋに入力する値を変えていくことになる。しかし、埋め込み次数ｋはペアリング暗号の安全性に関わるパラメータであるため、現代のコンピュータの処理性能を考慮すると、埋め込み次数ｋとしては２〜６程度が推奨される。このため、従来技術では、埋め込み次数ｋ及び判別式Ｄとして入力される値の組合せは限られており、楕円曲線を効率良く生成することはできなかった。
【０００９】
開示の技術は、上記に鑑みてなされたものであって、楕円曲線を効率良く生成することができる楕円曲線生成方法、楕円曲線生成装置及び楕円曲線生成プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１０】
本願の開示する楕円曲線生成方法は、Ｂｒｅｚｉｎｇ−Ｗｅｎｇ法における埋め込み次数を入力値として受け付ける。また、楕円曲線生成方法は、受け付けた入力値に対して、Ｂｒｅｚｉｎｇ−Ｗｅｎｇ法における部分群位数多項式の次数が所定値以下となる判別式を、埋め込み次数と判別式に係る円分体の拡大次数に基づいて算出する。また、楕円曲線生成方法は、前記判別式を算出する処理により算出された判別式と前記入力値とを用いて、Ｂｒｅｚｉｎｇ−Ｗｅｎｇ法に基づいて楕円曲線を生成する。
【発明の効果】
【００１１】
本願の開示する技術の一つの態様によれば、楕円曲線を効率良く生成することができるという効果を奏する。
【図面の簡単な説明】
【００１２】
【図１】図１は、実施例１に係る楕円曲線生成装置の機能構成を示すブロック図である。
【図２】図２は、実施例１に係る楕円曲線生成装置の処理手順を示すフローチャートである。
【図３】図３は、実施例１に係る楕円曲線生成装置の効果を説明するための図である。
【図４】図４は、楕円曲線生成プログラムを実行するコンピュータの一例を示す図である。
【発明を実施するための形態】
【００１３】
以下に、本願の開示する楕円曲線生成方法、楕円曲線生成装置及び楕円曲線生成プログラムの実施例を図面に基づいて詳細に説明する。なお、この実施例によりこの発明が限定されるものではない。各実施例は、処理内容を矛盾させない範囲で適宜組み合わせることが可能である。
【実施例１】
【００１４】
実施例１に係る楕円曲線生成装置の機能構成の一例について説明する。図１は、実施例１に係る楕円曲線生成装置の機能構成を示すブロック図である。図１に示すように、この楕円曲線生成装置１００は、記憶部１１０と、制御部１２０とを有する。
【００１５】
記憶部１１０は、算出データ１１１を有する。記憶部１１０は、例えば、ＲＡＭ（Random Access Memory）、ＲＯＭ（Read Only Memory）、フラッシュメモリ（Flash Memory）などの半導体メモリ素子、ハードディスクや光ディスクなどの記憶装置に対応する。
【００１６】
算出データ１１１は、後述する算出部１２２により算出された算出結果を示すデータである。例えば、算出データ１１１は、入力値である埋め込み次数ｋと所定値ｍと、算出結果である判別式Ｄとを対応づけたデータである。具体的には、算出データ１１１は、例えば、埋め込み次数「ｋ＝３」と、所定値「ｍ＝８」と、判別式「Ｄ＝１，３，５，１５」とを対応づけたデータである。つまり、算出データ１１１は、埋め込み次数ｋ＝３及び所定値ｍ＝８が入力値として算出部１２２に入力された場合に、４つの判別式Ｄ＝１，３，５，１５が算出されたことを示す。
【００１７】
制御部１２０は、受付部１２１と、算出部１２２と、生成部１２３と、出力部１２４とを有する。制御部１２０の機能は、例えば、ＡＳＩＣ（Application Specific Integrated Circuit）やＦＰＧＡ（Field Programmable Gate Array）などの集積回路により実現することができる。また、制御部１２０の機能は、例えば、ＣＰＵ（Central Processing Unit）が所定のプログラムを実行することで実現することができる。
【００１８】
受付部１２１は、各種情報の入力を受け付ける。例えば、受付部１２１は、埋め込み次数ｋと所定値ｍとを入力値として受け付ける。受付部１２１は、受け付けた入力値を算出部１２２に出力する。
【００１９】
算出部１２２は、受付部１２１によって受け付けた埋め込み次数ｋと所定値ｍとを用いて、ＢＷ法における部分群位数多項式ｒ（ｘ）の次数が所定値ｍ以下となる判別式Ｄを、埋め込み次数ｋと判別式Ｄに係る円分体の拡大次数に基づいて算出する。
【００２０】
ここで、部分群位数多項式ｒ（ｘ）の次数が所定値ｍ以下となる判別式Ｄを算出するのは、部分群位数ｒがペアリング暗号の安全性に関わるパラメータであり、選択できる値には制限があるからである。つまり、多項式ｒ（ｘ）の次数が大きい場合には、部分群位数ｒの値が大きくなってしまい、ペアリング暗号に適したサイズの部分群位数ｒを得ることができない。また、埋め込み次数ｋもペアリング暗号の安全性に関わるパラメータであり、選択できる値には制限がある。これに対して、判別式Ｄには、このような制限が無い。このため、発明者らは、多項式ｒ（ｘ）の次数に上限値を設定することで、ペアリング暗号に適したサイズの部分群位数ｒを出力する判別式Ｄを埋め込み次数ｋから求めることができ、楕円曲線を効率良く生成することができるという着想に至った。
【００２１】
例えば、算出部１２２は、埋め込み次数ｋの倍数ｎのうち、オイラー関数φ（ｎ）の値が所定値ｍ以下となる整数ｎを選択する。算出部１２２は、円分体Ｑ（ζｎ）に含まれる虚２次体Ｋの定義多項式ｆ（ｘ）＝ｘ２＋ａｘ＋ｂの係数ａ及びｂを算出する。算出部１２２は、ｆ（ｘ）の係数ａ及びｂから（４ｂ−ａ２）の値を算出し、算出した値の非平方因子を判別式Ｄとして算出する。なお、ζｋは、１の原始ｋ乗根である。また、ｎは埋め込み次数ｋの倍数であるので、円分体Ｑ（ζｎ）はζｋを含む。また、ｆ（ｘ）は、Ｋ＝Ｑ［ｘ］／（ｆ（ｘ））を満たす多項式である。
【００２２】
以下において、算出部１２２の処理を詳細に説明する。ここでは、一例として、埋め込み次数ｋ＝３かつ所定値ｍ＝８の場合を説明する。なお、埋め込み次数ｋ及び所定値ｍの値については、この例示に限定されるものではなく、楕円曲線生成装置１００を利用する者が任意の値に設定して良い。
【００２３】
まず、算出部１２２が整数ｎを選択する処理について説明する。例えば、算出部１２２は、埋め込み次数ｋ＝３の倍数ｎ＝３，６，９，１２，１５・・・を求める。そして、算出部１２２は、求めた倍数ｎについて、下記の式（１）を用いてφ（ｎ）を算出する。なお、式（１）において、倍数ｎは正整数である。また、ｐ１，ｐ２・・・ｐｉは、倍数ｎの相違なる全ての素因子である。
【００２４】
φ（ｎ）＝ｎ（１−１／ｐ１）（１−１／ｐ２）・・・（１−１／ｐｉ）・・・（１）
【００２５】
例えば、算出部１２２は、式（１）を用いてφ（３）＝２，φ（６）＝２，φ（９）＝６，φ（１２）＝４，φ（１５）＝８・・・を算出する。そして、算出部１２２は、φ（ｎ）≦ｍとなる倍数ｎを選択する。つまり、埋め込み次数ｋ＝３かつ所定値ｍ＝８の場合には、算出部１２２は、ｎ＝３，６，９，１２，１５，１８，２４，３０を選択する。なお、以下では、説明の都合上、倍数ｎ＝１５の場合を説明するが、算出部１２２は、選択した他の倍数ｎについても同様に処理するものとする。また、算出部１２２が倍数ｎを選択する方法は、上記の方法に限定されるものではない。例えば、算出部１２２は、φ（ｎ）≦ｍとなる値を算出した後に、算出した値のうち埋め込み次数ｋの倍数となる倍数ｎを選択するようにしても良い。具体的には、所定値ｍ＝８の場合には、算出部１２２は、φ（ｎ）≦８となる値として、２，３，４，５，６，７，８，９，１０，１２，１４，１５，１６，１８，２０，２４，３０を算出する。そして、算出部１２２は、φ（ｎ）≦８となる値のうち、埋め込み次数ｋ＝３の倍数ｎとして、３，６，９，１２，１５，１８，２４，３０を選択する。
【００２６】
このように、算出部１２２は、埋め込み次数ｋの倍数ｎのうち、オイラー関数φ（ｎ）の値が所定値ｍ以下となる整数ｎを選択する。例えば、埋め込み次数ｋ＝３かつ所定値ｍ＝８の場合には、算出部１２２は、整数ｎとして、３，６，９，１２，１５，１８，２４，３０を選択する。
【００２７】
また、算出部１２２が、円分体Ｑ（ζｎ）に含まれる虚２次体Ｋの定義多項式ｆ（ｘ）＝ｘ２＋ａｘ＋ｂの係数ａ及びｂを算出する処理について説明する。例えば、算出部１２２は、倍数ｎ＝１５の場合には、円分体Ｑ（ζ１５）に含まれる虚２次体Ｋの定義多項式ｆ（ｘ）＝ｘ２＋ａｘ＋ｂの係数ａ及びｂを算出する。ここで、ガロア理論より円分体Ｑ（ζｎ）に含まれる虚２次体Ｋは群（Ｚ／ｎＺ）＊の指数２の部分群に対応することが知られている。よって、算出部１２２は、群（Ｚ／ｎＺ）＊を生成し、生成した群（Ｚ／ｎＺ）＊の指数２の部分群を生成することで、虚２次体Ｋを生成することができる。以下で、虚２次体Ｋの定義多項式ｆ（ｘ）＝ｘ２＋ａｘ＋ｂの係数ａ及びｂの具体的な算出方法を説明する。
【００２８】
例えば、整数ｎ＝１５を選択した場合を説明する。円分体Ｑ（ζ１５）の次数は、φ（ｎ）に等しいので、φ（１５）＝８である。群（Ｚ／ｎＺ）＊は、１〜ｎの整数であり、かつ、ｎの素因数で割り切れる数を除外したものである。よって、算出部１２２は、１〜１５の整数うち、１５の素因数「３」及び「５」で割り切れる数を除外して、群（Ｚ／１５Ｚ）＊＝｛１，２，４，７，８，１１，１３，１４｝を生成する。そして、算出部１２２は、生成した群（Ｚ／ｎＺ）＊の指数２の部分群を生成する。
【００２９】
ここで、群（Ｚ／ｎＺ）＊の指数２の部分群を生成する処理について説明する。算出部１２２は、群（Ｚ／ｎＺ）＊から元ｇを一つ選択し、選択した元ｇに元ｇを乗算する。算出した値が倍数ｎより小さい場合には、算出部１２２は、算出した値をそのまま取得する。一方、算出した値が倍数ｎより大きい場合には、算出部１２２は、算出した値が倍数ｎより小さくなるまで算出した値から倍数ｎを減算し、減算した値を取得する。算出部１２２は、取得した値に対してさらに元ｇを乗算し、算出した値を取得する。算出部１２２は、取得した値が「１」になるまで、取得した値に元ｇを乗算する処理を繰り返す。取得した値が「１」になった場合には、算出部１２２は、取得した値と選択した元ｇとを新たな元として部分群＜ｇ＞を生成する。また、算出部１２２は、群（Ｚ／ｎＺ）＊に含まれる他の元についても同様に部分群を生成する。
【００３０】
例えば、群（Ｚ／１５Ｚ）＊について、算出部１２２が元ｇ＝２を選択した場合を説明する。算出部１２２は、「２×２＝４」を算出する。「４」は「１５」より小さいので、算出部１２２は、「４」を取得する。算出部１２２は、「４×２＝８」を算出する。「８」は「１５」より小さいので、算出部１２２は、「８」を取得する。算出部１２２は、「８×２＝１６」を算出する。算出された「１６」は「１５」より大きいので、算出部１２２は、「１６−１５＝１」を算出し、算出した「１」を取得する。ここで取得した値が「１」であるので、算出部１２２は、取得した値と選択した元ｇ＝２とを新たなを元として部分群＜２＞＝｛１，２，４，８｝を生成する。なお、この部分群＜２＞に含まれる元の個数は「４」である。また、算出部１２２は、群（Ｚ／１５Ｚ）＊に含まれる他の元についても同様に、指数２の部分群を生成する。例えば、算出部１２２は、群（Ｚ／１５Ｚ）＊から元ｇ＝４を選択し、部分群＜４＞＝｛１，４｝を生成する。この部分群＜４＞に含まれる元の個数は「２」であるため、指数２の部分群にならないことに注意しておく。
【００３１】
例えば、算出部１２２は、指数２の部分群＜２＞に対応する虚２次体Ｋを選択する。この場合、算出部１２２は、ガロア理論に基づき定義多項式ｆ（ｘ）の２つの解ｓ及びｓ〜を求める。この解ｓは、部分群＜２＞に含まれる元を用いると、ｓ＝ζ＋ζ２＋ζ４＋ζ８となる。また、解ｓ〜は、群（Ｚ／ｎＺ）＊に含まれる元のうち、部分群＜２＞に含まれる元以外の元を用いると、ｓ〜＝ζ７＋ζ１１＋ζ１３＋ζ１４となる。なお、ここでは、ζ１５をζと略記する。
【００３２】
例えば、算出部１２２は、定義多項式ｆ（ｘ）＝ｘ２＋ａｘ＋ｂの２つの解と係数との関係式と、ζ１５＝１という性質とを用いて、係数ａ及びｂを算出する。なお、この関係式は、下記の式（２）及び（３）によって表される。
【００３３】
ａ＝−（ｓ＋ｓ〜）・・・（２）
【００３４】
ｂ＝ｓ×ｓ〜・・・（３）
【００３５】
例えば、算出部１２２は、ｆ（ｘ）の２つの解ｓ及びｓ〜を式（２）に代入し、ζ１５＝１という性質を用いて演算することで、係数ａ＝０を算出する。また、例えば、算出部１２２は、ｆ（ｘ）の２つの解ｓ及びｓ〜を式（３）に代入し、ζ１５＝１という性質を用いて演算することで、係数ｂ＝１５を算出する。
【００３６】
なお、算出部１２２は、部分群＜４＞を選択した場合、この部分群は指数２の部分群ではないので、定義多項式ｆ（ｘ）の２つの解ｓ及びｓ〜を求める処理を行わずに、他の部分群についての処理に移行する。
【００３７】
このように、算出部１２２は、円分体Ｑ（ζｎ）に含まれる虚２次体Ｋの定義多項式ｆ（ｘ）＝ｘ２＋ａｘ＋ｂの係数ａ及びｂを算出する。例えば、整数ｎ＝１５を選択し、群（Ｚ／１５Ｚ）＊の指数２の部分群＜２＞を用いた場合には、算出部１２２は、定義多項式ｆ（ｘ）＝ｘ２＋ａｘ＋ｂの係数ａ＝０及びｂ＝１５を算出する。また、算出部１２２は、他の部分群についても同様に処理を実行し、他の部分群に対応する定義多項式ｆ（ｘ）の係数ａ及びｂを算出する。
【００３８】
また、算出部１２２が判別式Ｄを算出する処理について説明する。例えば、算出部１２２は、定義多項式ｆ（ｘ）の係数ａ及びｂから（４ｂ−ａ２）の値を算出し、算出した値の非平方因子を判別式Ｄとして算出する。例えば、算出部１２２は、下記の式（４）を用いて、判別式Ｄを算出する。なお、式（４）において、ｙ２は、平方因子である。
【００３９】
４ｂ−ａ２＝Ｄｙ２・・・（４）
【００４０】
例えば、算出した係数がａ＝０及びｂ＝１５であった場合には、４ｂ−ａ２＝１５×２２となるので、算出部１２２は、非平方因子１５を判別式Ｄ＝１５として算出する。また、算出部１２２は、定義多項式ｆ（ｘ）の係数ａ及びｂを算出するごとに、判別式Ｄを算出する。
【００４１】
以上のように、算出部１２２は、多項式ｒ（ｘ）の次数が所定値ｍ以下となる判別式Ｄを算出する。例えば、埋め込み次数ｋ＝３かつ所定値ｍ＝８の場合には、算出部１２２は、オイラー関数φ（ｎ）の値が所定値ｍ以下となる倍数ｎ＝３，６，９，１２，１５，１８，２４，３０を選択する。算出部１２２は、選択した倍数ｎについて、円分体Ｑ（ζｎ）に含まれる虚２次体Ｋの定義多項式ｆ（ｘ）＝ｘ２＋ａｘ＋ｂの係数ａ及びｂを算出する。そして、算出部１２２は、定義多項式ｆ（ｘ）の係数ａ及びｂを算出するごとに、（４ｂ−ａ２）の値の非平方因子を算出し、判別式Ｄ＝１，３，５，１５を求める。
【００４２】
また、算出部１２２は、算出結果を算出データ１１１として記憶部１１０に格納する。例えば、算出部１２２は、埋め込み次数「ｋ＝３」と、所定値「ｍ＝８」と、判別式「Ｄ＝１，３，５，１５」とを対応づけて、算出データ１１１として記憶部１１０に格納する。
【００４３】
生成部１２３は、算出した判別式Ｄと埋め込み次数ｋとを用いて、Ｂｒｅｚｉｎｇ−Ｗｅｎｇ法（以下、ＢＷ法と省略する）に基づいて楕円曲線を生成する。例えば、生成部１２３は、記憶部１１０に記憶された算出データ１１１から埋め込み次数ｋと判別式Ｄとを取得する。そして、生成部１２３は、例えば、非特許文献１に記載されるように、取得した埋め込み次数ｋと判別式Ｄとを用いて楕円曲線を生成するＢＷ法に基づいて、楕円曲線を生成する。
【００４４】
出力部１２４は、各種情報を出力する。例えば、出力部１２４は、生成部１２３により生成された楕円曲線を示す情報を出力する。また、例えば、出力部１２４は、埋め込み次数ｋと、判別式Ｄと、楕円曲線を示す情報とを対応づけて出力するようにしても良い。
【００４５】
次に、実施例１に係る楕円曲線生成装置１００の処理手順について説明する。図２は、実施例１に係る楕円曲線生成装置の処理手順を示すフローチャートである。図２に示す処理は、例えば、楕円曲線生成装置１００に電源から電力が供給されている間、所定時間間隔で実行される。
【００４６】
図２に示すように、入力値である埋め込み次数ｋ及び所定値ｍを受け付けると（ステップＳ１０１，Ｙｅｓ）、算出部１２２は、埋め込み次数ｋの倍数ｎのうち、オイラー関数φ（ｎ）の値が所定値ｍ以下となる整数ｎを選択する（ステップＳ１０２）。例えば、埋め込み次数ｋ＝３かつ所定値ｍ＝８の場合には、算出部１２２は、整数ｎとして、３，６，９，１２，１５，１８，２４，３０を選択する。
【００４７】
算出部１２２は、円分体Ｑ（ζｎ）に含まれる虚２次体Ｋの定義多項式ｆ（ｘ）＝ｘ２＋ａｘ＋ｂの係数ａ及びｂを算出する（ステップＳ１０３）。つまり、選択した整数ｎに対して群（Ｚ／ｎＺ）＊を生成し、生成した群（Ｚ／ｎＺ）＊の指数２の部分群を生成する。算出部１２２は、部分群に含まれる元の個数と、円分体Ｑ（ζｎ）の次数を虚２次体の次数で除算した値とが一致する場合に、虚２次体Ｋが存在すると判定する。虚２次体Ｋが存在する部分群について、算出部１２２は、ガロア理論に基づき定義多項式ｆ（ｘ）＝ｘ２＋ａｘ＋ｂの係数ａ及びｂを算出する。なお、虚２次体Ｋが存在する部分群が複数存在する場合には、他の部分群についても同様に処理を実行し、他の部分群に対応する定義多項式ｆ（ｘ）の係数ａ及びｂを算出する。また、選択した整数ｎが複数存在する場合には、他の整数ｎについても同様に処理を実行し、他の部分群に対応する定義多項式ｆ（ｘ）の係数ａ及びｂを算出する。
【００４８】
算出部１２２は、定義多項式ｆ（ｘ）の係数ａ及びｂから（４ｂ−ａ２）の値を算出し、算出した値の非平方因子を判別式Ｄとして算出する（ステップＳ１０４）。なお、算出部１２２は、定義多項式ｆ（ｘ）の係数ａ及びｂを算出するごとに、判別式Ｄを算出する。また、算出部１２２は、算出結果を算出データ１１１として記憶部１１０に格納する。
【００４９】
生成部１２３は、算出した判別式Ｄと埋め込み次数ｋとを用いて、ＢＷ法に基づいて楕円曲線を生成する（ステップＳ１０５）。例えば、生成部１２３は、記憶部１１０に記憶された算出データ１１１から埋め込み次数ｋと判別式Ｄとを取得する。そして、生成部１２３は、例えば、非特許文献１に記載されるように、取得した埋め込み次数ｋと判別式Ｄとを用いて楕円曲線を生成するＢＷ法に基づいて、楕円曲線を生成する。
【００５０】
なお、ステップＳ１０４の処理において、算出部１２２は、定義多項式ｆ（ｘ）の係数ａ及びｂを算出するごとに判別式Ｄを算出するものと説明したが、これに限定されるものではない。例えば、ステップＳ１０３の処理において、定義多項式ｆ（ｘ）の係数ａ及びｂを複数算出した後に、ステップＳ１０４の処理において、算出部１２２は、判別式Ｄを算出するようにしても良い。
【００５１】
次に、実施例１に係る楕円曲線生成装置１００の効果について説明する。楕円曲線生成装置１００は、Ｂｒｅｚｉｎｇ−Ｗｅｎｇ法における埋め込み次数を入力値として受け付ける。また、楕円曲線生成装置１００は、受け付けた入力値に対して、Ｂｒｅｚｉｎｇ−Ｗｅｎｇ法における部分群位数多項式の次数が所定値以下となる判別式を、埋め込み次数と判別式に係る円分体の拡大次数に基づいて算出する。また、楕円曲線生成装置１００は、算出した判別式と入力値とを用いて、Ｂｒｅｚｉｎｇ−Ｗｅｎｇ法に基づいて楕円曲線を生成する。このように、楕円曲線生成装置１００は、多項式ｒ（ｘ）の次数に上限値を設定することで、ペアリング暗号に適したサイズの部分群位数ｒを出力する判別式Ｄを埋め込み次数ｋから求めることができ、楕円曲線を効率良く生成することができる。
【００５２】
図３は、実施例１に係る楕円曲線生成装置の効果を説明するための図である。図３は、楕円曲線生成装置１００により算出される判別式Ｄの値と、生成される楕円曲線の個数とを対応づけて示す。図３に示すように、埋め込み次数ｋ＝３かつ所定値ｍ＝８の場合には、楕円曲線生成装置１００は、判別式Ｄ＝１，３，５，１５を算出する。この判別式Ｄ＝１，３，５，１５の値に対して、ＢＷ法において得られる多項式ｒ（ｘ）の次数は、それぞれ４，４，８，８となる。多項式ｒ（ｘ）の次数が多いほど生成される楕円曲線の個数は少なくなることが知られており、得られる楕円曲線の個数の比は、判別式Ｄ＝１のときを１とすると、判別式Ｄ＝１，３，５，１５の値に対して、それぞれ１，１，０．５，０．５となる。従来のＢＷ法においては、判別式Ｄには１を入力することが一般的であったため、得られる楕円曲線の個数の比は１である。これに対して、楕円曲線生成装置１００により算出された判別式Ｄ＝３，５，１５を用いて楕円曲線を生成すると、得られる楕円曲線の個数の比は３となる。このため、楕円曲線生成装置１００は、従来のＢＷ法と比べて３倍多くの楕円曲線を得ることができ、楕円曲線を効率良く生成することができる。
【実施例２】
【００５３】
さて、これまで本発明の実施例について説明したが、本発明は上述した実施例以外にも、その他の実施例にて実施されても良い。そこで、以下では、その他の実施例について説明する。
【００５４】
実施例１において説明した各処理のうち、自動的に行われるものとして説明した処理の全部または一部を手動的に行うこともでき、あるいは、手動的に行われるものとして説明した処理の全部または一部を公知の方法で自動的に行うこともできる。例えば、図２に示した処理手順は、受付部１２１が入力値である埋め込み次数ｋ及び所定値ｍを受け付けた場合に自動的に開始されるものとして説明したが、楕円曲線生成装置１００を利用する者が手動的に開始しても良い。この他、上述文書中や図面中で示した処理手順、制御手順、具体的名称、各種のデータやパラメータを含む情報については、特記する場合を除いて任意に変更することができる。例えば、算出データ１１１は、埋め込み次数ｋと、所定値ｍと、判別式Ｄとを対応づけると説明したが、所定値ｍを含む必要はない。つまり、算出データ１１１は、埋め込み次数ｋと、判別式Ｄとを対応づけたデータであっても良い。
【００５５】
また、図１に示した楕円曲線生成装置１００の各構成要素は機能概念的なものであり、必ずしも物理的に図示の如く構成されていることを要しない。すなわち、楕円曲線生成装置１００の分散・統合の具体的形態は図示のものに限られず、その全部または一部を、各種の負荷や使用状況などに応じて、任意の単位で機能的または物理的に分散・統合して構成することができる。例えば、図１に示した生成部１２３を楕円曲線生成装置１００が有している必要は無い。つまり、楕円曲線生成装置１００は、算出部１２２により算出された算出結果を算出データ１１１として記憶部１１０に格納しておき、格納した算出データ１１１を出力するようにしても良い。
【００５６】
また、楕円曲線生成装置１００は、楕円曲線生成装置１００の各機能を既知の情報処理装置に搭載することによって実現することもできる。既知の情報処理装置は、例えば、パーソナルコンピュータ、ワークステーション、携帯電話、ＰＨＳ（Personal Handy-phone System）端末、移動体通信端末またはＰＤＡ（Personal Digital Assistant）などの装置に対応する。
【００５７】
図４は、楕円曲線生成プログラムを実行するコンピュータの一例を示す図である。図４に示すように、コンピュータ３００は、各種演算処理を実行するＣＰＵ３０１と、ユーザからデータの入力を受け付ける入力装置３０２と、モニタ３０３とを有する。また、コンピュータ３００は、記憶媒体からプログラム等を読み取る媒体読み取り装置３０４と、他の装置と接続するためのインターフェース装置３０５と、他の装置と無線により接続するための無線通信装置３０６とを有する。また、コンピュータ３００は、各種情報を一時記憶するＲＡＭ（Random Access Memory）３０７と、ハードディスク装置３０８とを有する。また、各装置３０１〜３０８は、バス３０９に接続される。
【００５８】
ハードディスク装置３０８には、図１に示した算出部１２２及び生成部１２３の各処理部と同様の機能を有する楕円曲線生成プログラムが記憶される。また、ハードディスク装置３０８には、楕円曲線生成プログラムを実現するための各種データが記憶される。
【００５９】
ＣＰＵ３０１は、ハードディスク装置３０８に記憶された各プログラムを読み出して、ＲＡＭ３０７に展開し、各種の処理を行う。また、これらのプログラムは、コンピュータを図１に示した算出部１２２及び生成部１２３として機能させることができる。
【００６０】
なお、上記の楕円曲線生成プログラムは、必ずしもハードディスク装置３０８に記憶されている必要はない。例えば、コンピュータが読み取り可能な記録媒体に記憶されたプログラムを、コンピュータ３００が読み出して実行するようにしても良い。コンピュータが読み取り可能な記録媒体は、例えば、ＣＤ−ＲＯＭやＤＶＤディスク、ＵＳＢメモリ等の可搬型記録媒体、フラッシュメモリ等の半導体メモリ、ハードディスクドライブ等が対応する。また、公衆回線、インターネット、ＬＡＮ（Local Area Network）、ＷＡＮ（Wide Area Network）等に接続された装置にこのプログラムを記憶させておき、コンピュータ３００がこれらからプログラムを読み出して実行するようにしても良い。
【００６１】
以上の各実施例を含む実施形態に関し、さらに以下の付記を開示する。
【００６２】
（付記１）コンピュータが実行する楕円曲線生成方法であって、
Ｂｒｅｚｉｎｇ−Ｗｅｎｇ法における埋め込み次数を入力値として受け付け、受け付けた入力値に対して、Ｂｒｅｚｉｎｇ−Ｗｅｎｇ法における部分群位数多項式の次数が所定値以下となる判別式を、埋め込み次数と判別式に係る円分体の拡大次数に基づいて算出し、
前記判別式を算出する処理により算出された判別式と前記入力値とを用いて、Ｂｒｅｚｉｎｇ−Ｗｅｎｇ法に基づいて楕円曲を生成する
ことを特徴とする楕円曲線生成方法。
【００６３】
（付記２）前記判別式を算出する処理は、入力値ｋの倍数ｎのうち、オイラー関数φ（ｎ）の値が所定値以下となるｎを選択し、円分体Ｑ（ζｎ）に含まれる虚２次体Ｋの定義多項式ｆ（ｘ）＝ｘ２＋ａｘ＋ｂを算出し、ｆ（ｘ）の係数ａ及びｂから（４ｂ−ａ２）の値を算出し、算出した値の非平方因子を判別式として算出することを特徴とする付記１に記載の楕円曲線生成方法。ただし、ζｋは、１の原始ｋ乗根であり、ｆ（ｘ）は、Ｋ＝Ｑ［ｘ］／（ｆ（ｘ））となる多項式である。
【００６４】
（付記３）Ｂｒｅｚｉｎｇ−Ｗｅｎｇ法における埋め込み次数を入力値として受け付け、受け付けた入力値に対して、Ｂｒｅｚｉｎｇ−Ｗｅｎｇ法における部分群位数多項式の次数が所定値以下となる判別式を、埋め込み次数と判別式に係る円分体の拡大次数に基づいて算出する算出部と、
前記算出部により算出された判別式と前記入力値とを用いて、Ｂｒｅｚｉｎｇ−Ｗｅｎｇ法に基づいて楕円曲線を生成する生成部と
を備えたことを特徴とする楕円曲線生成装置。
【００６５】
（付記４）前記算出部は、入力値ｋの倍数ｎのうち、オイラー関数φ（ｎ）の値が所定値以下となるｎを選択し、円分体Ｑ（ζｎ）に含まれる虚２次体Ｋの定義多項式ｆ（ｘ）＝ｘ２＋ａｘ＋ｂを算出し、ｆ（ｘ）の係数ａ及びｂから（４ｂ−ａ２）の値を算出し、算出した値の非平方因子を判別式として算出することを特徴とする付記３に記載の楕円曲線生成装置。ただし、ζｋは、１の原始ｋ乗根であり、ｆ（ｘ）は、Ｋ＝Ｑ［ｘ］／（ｆ（ｘ））となる多項式である。
【００６６】
（付記５）コンピュータに、
Ｂｒｅｚｉｎｇ−Ｗｅｎｇ法における埋め込み次数を入力値として受け付け、受け付けた入力値に対して、Ｂｒｅｚｉｎｇ−Ｗｅｎｇ法における部分群位数多項式の次数が所定値以下となる判別式を、埋め込み次数と判別式に係る円分体の拡大次数に基づいて算出し、
前記判別式を算出する処理により算出された判別式と前記入力値とを用いて、Ｂｒｅｚｉｎｇ−Ｗｅｎｇ法に基づいて楕円曲を生成する
ことを特徴とする楕円曲線生成プログラム。
【００６７】
（付記６）前記判別式を算出する処理は、入力値ｋの倍数ｎのうち、オイラー関数φ（ｎ）の値が所定値以下となるｎを選択し、円分体Ｑ（ζｎ）に含まれる虚２次体Ｋの定義多項式ｆ（ｘ）＝ｘ２＋ａｘ＋ｂを算出し、ｆ（ｘ）の係数ａ及びｂから（４ｂ−ａ２）の値を算出し、算出した値の非平方因子を判別式として算出することを特徴とする付記５に記載の楕円曲線生成プログラム。ただし、ζｋは、１の原始ｋ乗根であり、ｆ（ｘ）は、Ｋ＝Ｑ［ｘ］／（ｆ（ｘ））となる多項式である。
【符号の説明】
【００６８】
１００ 楕円曲線生成装置
１１０ 記憶部
１１１ 算出データ
１２０ 制御部
１２１ 受付部
１２２ 算出部
１２３ 生成部
１２４ 出力部
３００ コンピュータ
３０１ ＣＰＵ
３０２ 入力装置
３０３ モニタ
３０４ 媒体読み取り装置
３０５ インターフェース装置
３０６ 無線通信装置
３０７ ＲＡＭ
３０８ ハードディスク装置
３０９ バス
【特許請求の範囲】
【請求項１】
コンピュータが実行する楕円曲線生成方法であって、
Ｂｒｅｚｉｎｇ−Ｗｅｎｇ法における埋め込み次数を入力値として受け付け、受け付けた入力値に対して、Ｂｒｅｚｉｎｇ−Ｗｅｎｇ法における部分群位数多項式の次数が所定値以下となる判別式を、埋め込み次数と判別式に係る円分体の拡大次数に基づいて算出し、
前記判別式を算出する処理により算出された判別式と前記入力値とを用いて、Ｂｒｅｚｉｎｇ−Ｗｅｎｇ法に基づいて楕円曲線を生成する
ことを特徴とする楕円曲線生成方法。
【請求項２】
前記判別式を算出する処理は、入力値ｋの倍数ｎのうち、オイラー関数φ（ｎ）の値が所定値以下となるｎを選択し、円分体Ｑ（ζｎ）に含まれる虚２次体Ｋの定義多項式ｆ（ｘ）＝ｘ２＋ａｘ＋ｂを算出し、ｆ（ｘ）の係数ａ及びｂから（４ｂ−ａ２）の値を算出し、算出した値の非平方因子を判別式として算出することを特徴とする請求項１に記載の楕円曲線生成方法。
ただし、ζｋは、１の原始ｋ乗根であり、ｆ（ｘ）は、Ｋ＝Ｑ［ｘ］／（ｆ（ｘ））となる多項式である。
【請求項３】
Ｂｒｅｚｉｎｇ−Ｗｅｎｇ法における埋め込み次数を入力値として受け付け、受け付けた入力値に対して、Ｂｒｅｚｉｎｇ−Ｗｅｎｇ法における部分群位数多項式の次数が所定値以下となる判別式を、埋め込み次数と判別式に係る円分体の拡大次数に基づいて算出する算出部と、
前記算出部により算出された判別式と前記入力値とを用いて、Ｂｒｅｚｉｎｇ−Ｗｅｎｇ法に基づいて楕円曲線を生成する生成部と
を備えたことを特徴とする楕円曲線生成装置。
【請求項４】
コンピュータに、
Ｂｒｅｚｉｎｇ−Ｗｅｎｇ法における埋め込み次数を入力値として受け付け、受け付けた入力値に対して、Ｂｒｅｚｉｎｇ−Ｗｅｎｇ法における部分群位数多項式の次数が所定値以下となる判別式を、埋め込み次数と判別式に係る円分体の拡大次数に基づいて算出し、
前記判別式を算出する処理により算出された判別式と前記入力値とを用いて、Ｂｒｅｚｉｎｇ−Ｗｅｎｇ法に基づいて楕円曲線を生成する
処理を実行させることを特徴とする楕円曲線生成プログラム。
【請求項１】
コンピュータが実行する楕円曲線生成方法であって、
Ｂｒｅｚｉｎｇ−Ｗｅｎｇ法における埋め込み次数を入力値として受け付け、受け付けた入力値に対して、Ｂｒｅｚｉｎｇ−Ｗｅｎｇ法における部分群位数多項式の次数が所定値以下となる判別式を、埋め込み次数と判別式に係る円分体の拡大次数に基づいて算出し、
前記判別式を算出する処理により算出された判別式と前記入力値とを用いて、Ｂｒｅｚｉｎｇ−Ｗｅｎｇ法に基づいて楕円曲線を生成する
ことを特徴とする楕円曲線生成方法。
【請求項２】
前記判別式を算出する処理は、入力値ｋの倍数ｎのうち、オイラー関数φ（ｎ）の値が所定値以下となるｎを選択し、円分体Ｑ（ζｎ）に含まれる虚２次体Ｋの定義多項式ｆ（ｘ）＝ｘ２＋ａｘ＋ｂを算出し、ｆ（ｘ）の係数ａ及びｂから（４ｂ−ａ２）の値を算出し、算出した値の非平方因子を判別式として算出することを特徴とする請求項１に記載の楕円曲線生成方法。
ただし、ζｋは、１の原始ｋ乗根であり、ｆ（ｘ）は、Ｋ＝Ｑ［ｘ］／（ｆ（ｘ））となる多項式である。
【請求項３】
Ｂｒｅｚｉｎｇ−Ｗｅｎｇ法における埋め込み次数を入力値として受け付け、受け付けた入力値に対して、Ｂｒｅｚｉｎｇ−Ｗｅｎｇ法における部分群位数多項式の次数が所定値以下となる判別式を、埋め込み次数と判別式に係る円分体の拡大次数に基づいて算出する算出部と、
前記算出部により算出された判別式と前記入力値とを用いて、Ｂｒｅｚｉｎｇ−Ｗｅｎｇ法に基づいて楕円曲線を生成する生成部と
を備えたことを特徴とする楕円曲線生成装置。
【請求項４】
コンピュータに、
Ｂｒｅｚｉｎｇ−Ｗｅｎｇ法における埋め込み次数を入力値として受け付け、受け付けた入力値に対して、Ｂｒｅｚｉｎｇ−Ｗｅｎｇ法における部分群位数多項式の次数が所定値以下となる判別式を、埋め込み次数と判別式に係る円分体の拡大次数に基づいて算出し、
前記判別式を算出する処理により算出された判別式と前記入力値とを用いて、Ｂｒｅｚｉｎｇ−Ｗｅｎｇ法に基づいて楕円曲線を生成する
処理を実行させることを特徴とする楕円曲線生成プログラム。
【図１】
【図２】
【図３】
【図４】
【図２】
【図３】
【図４】
【公開番号】特開２０１２−２１１９５７（Ｐ２０１２−２１１９５７Ａ）
【公開日】平成２４年１１月１日（２０１２．１１．１）
【国際特許分類】
【出願番号】特願２０１１−７６７５１（Ｐ２０１１−７６７５１）
【出願日】平成２３年３月３０日（２０１１．３．３０）
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【Ｆターム（参考）】
【公開日】平成２４年１１月１日（２０１２．１１．１）
【国際特許分類】
【出願日】平成２３年３月３０日（２０１１．３．３０）
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【Ｆターム（参考）】
[ Back to top ]