効率的な楕円曲線上の点生成方法、装置、及びプログラム
【課題】一般の楕円曲線に適用可能であり、入力に応じて処理性能に大きなばらつきがないような楕円曲線上の点の生成を実現すること。
【解決手段】
有限集合の元から予め定められた有限体ＧＦ（ｑ）（ｑ：奇素数ｐのべき）上定義された二次曲線ＣのＧＦ（ｑ）有理点を生成し、前記生成した二次曲線ＣのＧＦ（ｑ）有理点から当該楕円曲線のＧＦ（ｑ２）有理点を生成し、
前記楕円曲線ＥのＧＦ（ｑ２）有理点と前記有限集合の元の一部から前記楕円曲線ＥのＧＦ（ｑ）有理点を生成することを特徴とする楕円曲線上の点生成方法を提供する。
【解決手段】
有限集合の元から予め定められた有限体ＧＦ（ｑ）（ｑ：奇素数ｐのべき）上定義された二次曲線ＣのＧＦ（ｑ）有理点を生成し、前記生成した二次曲線ＣのＧＦ（ｑ）有理点から当該楕円曲線のＧＦ（ｑ２）有理点を生成し、
前記楕円曲線ＥのＧＦ（ｑ２）有理点と前記有限集合の元の一部から前記楕円曲線ＥのＧＦ（ｑ）有理点を生成することを特徴とする楕円曲線上の点生成方法を提供する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、セキュリティ技術に係り、特に楕円曲線上の点を生成する処理技術に関する。
【背景技術】
【０００２】
デジタル署名（以下、署名）は電子データに対する印鑑の役割を果たす。署名対象の電子データに対し、署名者は秘密にしている署名鍵を用いて署名データを生成し、もとの電子データと共に検証者に送信する。検証者は上記電子データ、及び、公開されている検証鍵を用い、上記署名データが署名者によって生成されたかどうかを検証する。従って、署名データは署名鍵を保持する者しか生成できず、また有効に生成された署名データは署名検証時に「有効」として受け入れられ、そうでないものは「無効」として拒絶されるような仕組みになっていなければならない。
【０００３】
上述の署名方法は1978年にＲ．Ｒｉｖｅｓｔ、Ａ．Ｓｈａｍｉｒ、Ｌ．Ａｄｌｅｍａｎにより公開鍵暗号技術を用いて実現された。その後、署名の安全性を暗号学的に証明する安全性証明理論の構築及び整備、効率性向上の技術のみならず、プライバシ問題を考慮したグループ署名のような特殊機能をもつ署名などが盛んに研究されている。
【０００４】
一般に、署名は任意長データを固定長データに圧縮するハッシュ関数と、数学関数を用いた公開鍵暗号プリミティブの組み合わせで構成されている。このような公開鍵暗号プリミティブのうち、有限体上定義された楕円曲線に基づくものは、素因数分解問題の困難性に基づくもの（ＲＳＡ、Ｒａｂｉｎなど）と比較して短い鍵長で同程度の安全性を達成でき、よって高速処理が可能であることから特に注目を集めている。
【０００５】
楕円曲線を利用した暗号や署名はＮ．Ｋｏｂｌｉｔｚ、Ｖ．Ｓ．Ｍｉｌｌｅｒにより提案された。一般に有限体ＧＦ(q)上で定義された楕円曲線のうちＷｅｉｅｒｓｔｒａｓｓ型と呼ばれるものは
ｙ２＝Ｆ（ｘ）＝ｘ３＋ａｘ＋ｂ，（ａ、ｂはともに有限体ＧＦ(q)の元） （式１）
の形の定義式で与えられる。上記で定義された楕円曲線に対し、（式１）を満たすＧＦ(q)の元の組（ｘ，ｙ）のことをＧＦ(q)有理点と呼ぶ。
【０００６】
近年、楕円曲線を用いた署名では長らく未解決であったｔｉｇｈｔ ｓｅｃｕｒｉｔｙ ｒｅｄｕｃｔｉｏｎを持つものも提案されている（例えば、非特許文献１参照。）。ここで、ｔｉｇｈｔ ｓｅｃｕｒｉｔｙ ｒｅｄｕｃｔｉｏｎとは、署名を偽造する困難性と、その署名の構成要素である公開鍵暗号プリミティブが安全性の根拠とする数論問題（例えば、素因数分解問題、有限体の乗法群／有限体上定義された楕円曲線の離散対数問題など）を解くための困難性が同程度（等価）であることを意味する。
【０００７】
上述の非特許文献１や非特許文献２などに記載されている署名は、楕円曲線上に値を持つハッシュ関数が利用されている。一般の楕円曲線上に値を持つハッシュ関数が非特許文献３に、特殊な楕円曲線上に値を持つハッシュ関数が非特許文献３、４に、それぞれ記載されている。
【先行技術文献】
【非特許文献】
【０００８】
【非特許文献１】B. Chevallier-Mames， “An Efficient CDH-based Signature Scheme With a Tight Security Reduction”， Advances in Cryptology - CRYPTO 2005， LNCS 3621， Springer-Verlag， pp.511−526， 2005.
【非特許文献２】E. J. Goh， S. Jarecki， “A signature Scheme as secure as the Diffie-Hellman Problem”， Advances in Cryptology - EUROCRYPT 2003， LNCS 2656， Springer-Verlag， pp.401-415， 2003.
【非特許文献３】D. Boneh， H. Shacham， and B. Lynn， “Short Signatures from the Weil Pairing”， Advances in Cryptology - ASIACRYPT 2001， LNCS 2248， Springer-Verlag， pp.514-532， 2001.
【非特許文献４】P. S. L. M. Barreto and H. Y. Kim， “Fast Hashing onto Elliptic Curves over Fields of Characteristic 3”， Cryptology ePrint Archive， Report 2001/098， 2001. available from: http://eprint.iacr.org/2001/098
【発明の概要】
【発明が解決しようとする課題】
【０００９】
情報化社会の高度化に伴い、電子情報に対する署名や、通信相手や機器を認証する技術は不可欠となってきている。上述のとおり、暗号技術に課せられる要件としては、安全性や効率性などがある。
【００１０】
非特許文献３に記載されている一般の楕円曲線に値を持つハッシュ関数は、予め定められた集合の元ｒから（式１）のｘ座標の候補を生成し、対応するｙ座標が定義体に含まれているかどうかを判定し、含まれていなければ、ある決まった方法にてｘを取替え、ｙ座標が含まれるまで繰り返す、という方法（以下、これを試行錯誤法と呼ぶ）である。試行錯誤法の場合、Ｈａｓｓｅの定理より繰り返しの平均回数は１．５回程度であることが知られているが、回数の分布にはばらつきがあり、実際にはそれを大幅に上回る計算が必要となることもしばしば起こる。ｙ座標が定義体に含まれるか否かを判定するにはある程度の処理が必要で、２、３回程度なら許容できたとしてもそれを超える回数では全体の処理においてボトルネックになる。
【００１１】
一方、非特許文献３、４に記載されている特殊な楕円曲線に値を持つハッシュ関数は、予め定められた集合の元ｒから（式１）のｘ座標の候補を生成し、対応するｙ座標を上記特殊な楕円曲線の定義方程式の性質を用いて決定する、という方法（以下、これを特殊曲線法と呼ぶ）であり、上述の一般の楕円曲線に値を持つハッシュ関数で実施する繰り返しを避け、効率性を向上させるために提案された方法である。
【００１２】
一般にハッシュ関数は、署名に用いる場合など、高効率性および入力に非依存な処理時間が求められることが多く、上述の試行錯誤法のように入力に応じて処理性能に大きなばらつきがある（繰り返し回数が変わるため）のは望ましくない。また、上述の特殊曲線法は特殊な楕円曲線のみに適用可能であり、一般の楕円曲線では同様の手法を用いることはできない。
【課題を解決するための手段】
【００１３】
本発明は、上記課題に鑑みてなされたもので、一般の楕円曲線に適用可能であり、入力に応じて処理性能が大きくばらつくことのない楕円曲線上の点の生成を実現する楕円曲線上の点生成方法および点生成装置を提供する。
【００１４】
以上の課題を解決するため、本発明は、楕円曲線の拡大体における有理点を使用する。
【００１５】
例えば、本発明は、有限集合の元から予め定められた有限体ＧＦ（ｑ）（ｑ：奇素数ｐのべき）上で定義された二次曲線ＣのＧＦ（ｑ）有理点を生成するステップと、
前記生成した二次曲線ＣのＧＦ（ｑ）有理点から当該楕円曲線のＧＦ（ｑ２）有理点を生成するステップと、
前記楕円曲線ＥのＧＦ（ｑ２）有理点と前記有限集合の元の一部から前記楕円曲線ＥのＧＦ（ｑ）有理点を生成するステップと、
を備えることを特徴とする。
【００１６】
より具体的な本発明の態様は、要素数が（ｑ＋１）／２（ｑは５以上の素数べき）の集合Ｓの元と要素数が２の集合Ｔの元から有限体ＧＦ（ｑ）上定義された楕円曲線ＥのＧＦ（ｑ）有理点を生成する点生成方法であって、
当該楕円曲線上の点生成方法は、
前記集合Ｓの元から予め定められた前記有限体ＧＦ（ｑ）上定義された二次曲線ＣのＧＦ（ｑ）有理点を生成する第一のステップと、
前記第一のステップで生成した前記二次曲線Ｃの前記ＧＦ（ｑ）有理点から前記楕円曲線ＥのＧＦ（ｑ２）有理点を生成する第二のステップと、
前記第二のステップで生成した前記楕円曲線ＥのＧＦ（ｑ２）有理点と前記集合Ｔの元から前記楕円曲線ＥのＧＦ（ｑ）有理点を生成する第三のステップと、
を備えることを特徴とする。
【００１７】
上記楕円曲線上の点生成方法において、さらに、
前記集合Ｓは集合ＧＦ（ｑ）＊／｛１，−１｝∪｛０｝、前記集合Ｔは｛１，−１｝であって、
前記第一のステップは、前記集合Ｓの元ｔから予め定められた２つのＧＦ（ｑ）上の有理関数α、βに対して、α（ｔ）、β（ｔ）を計算し、前記二次曲線ＣのＧＦ（ｑ）有理点Ｒ＝（α、β）を生成し、
前記第二のステップは、予め定められた前記有限体ＧＦ（ｑ２）の前記有限体ＧＦ（ｑ）上の基底（ξ，１）、及び前記二次曲線ＣのＧＦ（ｑ）有理点（α、β）から前記楕円曲線ＥのＧＦ（ｑ２）有理点Ｐ＝（α＋βξ，√（Ｆ（α＋βξ）））（Ｆは前記楕円曲線ＥのＷｅｉｅｒｓｔｒａｓｓ型の定義方程式ｙ２＝ｘ３＋ａｘ＋ｂ＝Ｆ（ｘ）に対して、Ｆ（ｘ）＝ｘ３＋ａｘ＋ｂなる多項式）を生成し、
前記第三のステップは、前記楕円曲線ＥのＧＦ（ｑ２）有理点Ｐから前記楕円曲線ＥのＦｒｏｂｅｎｉｕｓ自己準同型写像σを用いて前記楕円曲線ＥのＧＦ（ｑ）有理点（Ｐ＋σ（Ｐ））を生成してもよい。
【００１８】
また、具体的な本発明の他の態様は、要素数が（ｑ２＋１）／２（ｑは５以上の素数べき）の集合Ｓの元と要素数が２の集合Ｔの元から有限体ＧＦ（ｑ）上定義された楕円曲線ＥのＧＦ（ｑ）有理点を生成する点生成方法であって、
当該楕円曲線上の点生成方法は、
前記集合Ｓの元から予め定められた前記有限体ＧＦ（ｑ２）上定義された二次曲線ＣのＧＦ（ｑ２）有理点を生成する第四のステップと、
前記第四のステップで生成した前記二次曲線Ｃの前記ＧＦ（ｑ２）有理点から前記楕円曲線ＥのＧＦ（ｑ４）有理点を生成する第五のステップと、
前記第五のステップで生成した前記楕円曲線ＥのＧＦ（ｑ４）有理点と前記集合Ｔの元から前記楕円曲線ＥのＧＦ（ｑ）有理点を生成する第六のステップと、
を備えることを特徴とする。
【００１９】
上記楕円曲線上の点生成方法において、さらに、
前記集合Ｓは集合ＧＦ（ｑ２）＊／｛１，−１｝∪｛０｝、前記集合Ｔは｛１，−１｝であって、
前記第四のステップは、前記集合Ｓの元ｔから予め定められた２つのＧＦ（ｑ２）上の有理関数α、βに対して、α（ｔ）、β（ｔ）を計算し、前記二次曲線ＣのＧＦ（ｑ２）有理点Ｒ＝（α、β）を生成し、
前記第五のステップは、予め定められた前記有限体ＧＦ（ｑ４）の前記有限体ＧＦ（ｑ２）上の基底（ξ，１）、及び前記二次曲線ＣのＧＦ（ｑ２）有理点（α、β）に対して、前記楕円曲線ＥのＧＦ（ｑ２）有理点Ｐ＝（α＋βξ，√（Ｆ（α＋βξ）））（Ｆは前記楕円曲線ＥのＷｅｉｅｒｓｔｒａｓｓ型の定義方程式ｙ２＝ｘ３＋ａｘ＋ｂ＝Ｆ（ｘ）なる多項式）を生成し、
前記第六のステップは、前記楕円曲線ＥのＧＦ（ｑ４）有理点Ｐから、前期楕円曲線ＥのＦｒｏｂｅｎｉｕｓ自己準同型写像σを用いて前記楕円曲線ＥのＧＦ（ｑ）有理点Ｐ＋σ（Ｐ）＋σ２（Ｐ）＋σ３（Ｐ）を生成してもよい。
【発明の効果】
【００２０】
本発明により、一般の楕円曲線に適用可能であり、入力に応じて処理性能に大きなばらつきがないような楕円曲線上の点の生成が可能となる。これにより、一般の楕円曲線に値を持つハッシュ値の生成も可能となる。
【図面の簡単な説明】
【００２１】
【図１】第一の実施形態、及び第二の実施形態である点生成装置の機能構成の概略を例示する図。
【図２】コンピュータのハードウェア構成の概略図。
【図３】点生成装置における楕円曲線上の点生成処理を示すシーケンスを例示する図。
【図４】第一の実施形態における処理部での点生成処理を例示するフローチャート。
【図５】第二の実施形態における処理部での点生成処理を例示するフローチャート。
【発明を実施するための形態】
【００２２】
本発明の実施の形態を図面を用いて説明する。
【実施例１】
【００２３】
図１は、本発明の第一の実施形態である点生成装置１００の機能構成の概略図である。
【００２４】
図示するように、点生成装置１００は、記憶部１１１と、処理部１２０と、入力部１３１と、出力部１３２と、通信部１３３と、を備える。
【００２５】
本実施形態では、点生成装置で集合ＧＦ（ｑ）＊／｛１，−１｝∪｛０｝の元ｔと集合｛１，−１｝の元ιに対する上記有限体ＧＦ（ｑ）上定義された楕円曲線Ｅ（ＧＦ（ｑ）)上の点の生成を行う。ここでｑ＝ｐｒは素数ｐのべきである。
【００２６】
記憶部１１１は、有理関数記憶領域１１２と、基底記憶領域１１３と、パラメータ記憶部１１４と、を備える。
【００２７】
有理関数記憶領域１１２は、上記有限体ＧＦ（ｑ）から有限体ＧＦ（ｑ）上定義された２次曲線Ｃへの２つの有理関数に関する情報、及び上記２つの有理関数に付随する情報が格納される。ここで、上記有限体ＧＦ（ｑ）から有限体ＧＦ（ｑ）上定義された２次曲線Ｃへの２つの有理関数とは、上記有限体ＧＦ（ｑ）を係数にもつ１次または２次の多項式φ、ω、ψを用いてφ／ω、ψ／ωと表わされる関数であり、上記有限体ＧＦ（ｑ）から有限体ＧＦ（ｑ）上定義された２次曲線Ｃへの２つの有理関数に関する情報とは、例えば、上記φ、ω、ψの各係数である。また、上記有理関数φ／ω、ψ／ωの極（すなわち、ω（ｚ０）＝０）となる上記有限体ＧＦ（ｑ）の元ｚ０、及び上記多項式ψの零点（すなわち、ψ（ｚ１）＝０）となる上記有限体ＧＦ（ｑ）の元ｚ１である。なお、上記多項式ω、ψの零点となる上記各零点ｚ０、ｚ１を上記２つの有理関数に付随する情報を格納する理由については後述する。
【００２８】
基底記憶領域１１３には、上記有限体ＧＦ（ｑ）の２次拡大ＧＦ（ｑ２）の基底に関する情報が格納される。例えば、本実施形態においては、ξ∈ＧＦ（ｑ２）−ＧＦ（ｑ）、ｃ＝ξ２∈ＧＦ（ｑ）なる元ξが上記有限体ＧＦ（ｑ）の２次拡大ＧＦ（ｑ２）の基底に関する情報である。また、上記元ｃ∈ＧＦ（ｑ）も上記基底に関する情報として格納しておいてもよい。ここで、ＧＦ（ｑ２）−ＧＦ（ｑ）は上記有限体ＧＦ（ｑ）の２次拡大ＧＦ（ｑ２）から上記有限体ＧＦ（ｑ）の元を除いた集合を表わす。上記ξ、及び上記有限体ＧＦ（ｑ）の乗算に関する単位元１は、上記２次拡大ＧＦ（ｑ２）の上記有限体ＧＦ（ｑ）上の基底である。
【００２９】
パラメータ記憶部は、上記有限体ＧＦ（ｑ）、及び上記有限体ＧＦ（ｑ）上定義された楕円曲線Ｅ（ＧＦ（ｑ）)に関する情報が格納される。例えば、本実施形態においては、上記素数ｑ、及び上記楕円曲線Ｅ（ＧＦ（ｑ）)の定義方程式（式１）の係数ａ、ｂである。
【００３０】
処理部１２０は、有理関数計算部１２１と、有限体演算計算部１２２と、を備える。
【００３１】
例えば、本実施形態では、処理部１２０は、集合ＧＦ（ｑ）＊／｛１，−１｝∪｛０｝の元ｔと集合｛１，−１｝の元ιに対する上記楕円曲線Ｅ（ＧＦ（ｑ）)上の点を生成する処理を制御する。ここで、上記集合ＧＦ（ｑ）＊／｛１，−１｝∪｛０｝とは、有限体の乗法群ＧＦ(p）＊の元ｇに対して、ｇ＋ｈ＝０、またはｇ−ｈ＝０なる同値関係によって上記有限体の乗法群ＧＦ（ｑ）＊を割った集合を表わし、具体的には、ｑ＝ｐの場合は、上記集合ＧＦ（ｐ）＊／｛１，−１｝＝｛１，２，・・・（ｐ−１）／２｝である。
ｑ＝ｐｒ（ｒ＞＝２）の場合、上記集合ＧＦ（ｑ）＊／｛１，−１｝は、例えば、有限体の乗法群ＧＦ（ｑ）＊の元ｕ＝ａｒ−１γｒ−１＋ａｒ−２γｒ−２＋．．．＋ａ１γ＋ａ０であって、ａｉ≠０なる最大のｉをｊとするとき、０＜＝ａｊ＜＝（ｑ−１）／２を満たす元ｕからなる集合である。
【００３２】
また、上記集合ＧＦ（ｑ）＊／｛±１｝の構成方法は、実現可能であればその方法は問わない。
上記集合ＧＦ（ｑ）＊／｛１，−１｝∪｛０｝の要素数は、（ｑ−１）／２＋１＝（ｑ＋１）／２である。上記素数べきｑのビット長｜ｑ｜＝ｍのとき、ｑ≦２ｍ−１だから、（ｑ＋１）／２のビット長｜（ｑ＋１）／２｜≦｜｛（２ｍ−１）＋１｝／２｜＝｜２ｍ／２｜＝２ｍ−１である。
【００３３】
例えば、本実施形態では、処理部１２０は、入力データである上記元ｔと上記元ιに対して、有理関数記憶領域１１２に格納されている上記有理関数φ／ω、ψ／ωと、基底記憶領域１１３に格納されているＧＦ（ｑ２）−ＧＦ（ｑ）の元ξを取得して、ｔとともに、有理関数計算部１２１に送信する。有理関数計算部１２１は、予め定められたアルゴリズムによる計算を行い、上記有限体ＧＦ（ｑ）の２つの元α、βを生成する。そして、有理関数計算部１２１は、上記α、β、ξ、及び、パラメータ記憶部１１４に格納されている上記ａ、ｂを有限体演算計算部１２２に送信する。
【００３４】
有限体演算計算部１２２は、予め定められたアルゴリズムによる計算を行い、上記楕円曲線Ｅ（ＧＦ（ｑ））上の点Ｑを生成する。有限体演算計算部１２２は、上記生成した上記楕円曲線Ｅ（ＧＦ（ｑ））上の点Ｐを処理部１２０に出力する。入力部１３１は、当該点生成装置１００の外部から、記憶媒体１４４や、通信媒体（当該当該点生成装置１００に接続されるネットワークまたは当該ネットワークを伝播するデジタル信号や搬送波）を介して、情報の入力を受け付ける。出力部１３２は、当該点生成装置１００の外部へ、記憶媒体１４４や通信媒体を介して、情報を出力する。通信部１３３は、記憶部１１１と、処理部１２０と、入力部１３１と、出力部１３２と、の間の情報の送受信を行う。
【００３５】
以上に記載した点生成装置１００は、例えば、図２（コンピュータ１４０の概略図）に示すような、ＣＰＵ１４１と、メモリ１４２と、ＨＤＤ等の外部記憶装置１４３と、ＣＤ−ＲＯＭやＤＶＤ−ＲＯＭ等の可搬性を有する記憶媒体１４４から情報を読み出す読取装置１４５と、キーボードやマウスなどの入力装置１４６と、ディスプレイなどの出力装置１４７と、通信ネットワークに接続するためのＮＩＣ（Network Interface Card）等の通信装置１４８と、を備えた一般的なコンピュータ１４０で実現できる。
【００３６】
例えば、記憶部１１１は、ＣＰＵ１４１がメモリ１４２又は外部記憶装置１４３を利用することにより実現可能であり、処理部１２０は、外部記憶装置１４３に記憶されている所定のプログラムをメモリ１４２にロードしてＣＰＵ１４１で実行することで実現可能であり、入力部１３１は、ＣＰＵ１４１が入力装置１４６を利用することで実現可能であり、出力部１３２は、ＣＰＵ１４１が出力装置１４７を利用することで実現可能であり、通信部１３３は、ＣＰＵ１４１が通信装置１４８を利用することで実現可能である。
【００３７】
この所定のプログラムは、読取装置１４５を介して記憶媒体１４４から、あるいは、通信装置１４８を介して通信媒体から、外部記憶装置１４３にダウンロードされ、それから、メモリ１４２上にロードされてＣＰＵ１４１により実行されるようにしてもよい。また、読取装置１４５を介して記憶媒体１４４から、あるいは、通信装置１４８を介して通信媒体から、メモリ１４２上に直接ロードされ、ＣＰＵ１４１により実行されるようにしてもよい。
【００３８】
図３は、点生成装置１００における点生成処理を示すシーケンス図である。
【００３９】
まず、点生成装置１００の処理部１２０は、入力部１３１を介して入力された又はデータ記憶領域１３１に記憶されている有限体の元ｔ∈ＧＦ（ｑ）を取得する（Ｓ１０）。
【００４０】
次に、処理部１２０は、記憶部１２３の有理関数記憶領域１１２に記憶されている２つの有理関数φ／ω、ψ／ωと、基底記憶領域１１３に記憶されているξ∈ＧＦ（ｑ２）−ＧＦ（ｑ）と、パラメータ記憶領域１１４に記憶されている上記素数べきｑ、及び上記楕円曲線Ｅ（ＧＦ（ｑ）)の定義方程式（式１）の係数ａ、ｂと、を読み出す（Ｓ１１）。
【００４１】
そして、処理部１２０は、読み出した２つの有理関数φ／ω、ψ／ω、ξ∈ＧＦ（ｑ２）−ＧＦ（ｑ）、素数べきｑ、楕円曲線Ｅ（ＧＦ（ｑ）)の定義方程式（式１）の係数ａ、ｂ及び有限体の元ｔ∈ＧＦ（ｑ）を有理関数計算部１２１に入力する（Ｓ１２）。
【００４２】
有理関数計算部１２１は、入力された２つの有理関数φ／ω、ψ／ωと、ξ∈ＧＦ（ｑ２）−ＧＦ(ｑ）と、素数べきｑと、楕円曲線Ｅ（ＧＦ（ｑ）)の定義方程式（式１）の係数ａ、ｂと、有限体の元ｔ∈ＧＦ（ｑ）とから、有限体ＧＦ（ｑ）の元α、βを計算する（Ｓ１３）。
【００４３】
そして、有理関数計算部１２１は、計算した有限体ＧＦ（ｑ）の元α、βと、ξ∈ＧＦ（ｑ２）−ＧＦ（ｑ）と、素数べきｑと、楕円曲線Ｅ（ＧＦ（ｑ）)の定義方程式（式１）の係数ａ、ｂを有限体演算計算部１２２に出力する（Ｓ１４）。
【００４４】
有限体演算計算部１２２は、受け取った有限体ＧＦ（ｑ）の元α、βと、ξ∈ＧＦ（ｑ２）−ＧＦ（ｑ）と、素数べきｑと、楕円曲線Ｅ（ＧＦ（ｑ）)の定義方程式（式１）の係数ａ、ｂとから、楕円曲線上の点Ｐを生成する（Ｓ１５）。
【００４５】
有限体演算計算部１２２は、計算した楕円曲線上の点Ｐを処理部１２０に出力する（Ｓ１６）。
【００４６】
なお、ステップＳ１１において２つの有理関数φ／ω、ψ／ω、ξ∈ＧＦ（ｑ２）−ＧＦ（ｑ）、素数べきｑ、楕円曲線Ｅ（ＧＦ(ｑ）)の定義方程式（式１）の係数ａ、ｂの取得タイミングについては、有理関数計算部１２１へ２つの有理関数φ／ω、ψ／ω、ξ∈ＧＦ（ｑ２）−ＧＦ（ｑ）、素数べきｑ、楕円曲線Ｅ（ＧＦ（ｑ）)の定義方程式（式１）の係数ａ、ｂを出力する前であればよく、例えば、有限体の元ｔ∈ＧＦ（ｑ）を取得する（Ｓ１０）前であってもよい。また、ステップＳ１３の計算では、楕円曲線Ｅ（ＧＦ（ｑ）)の定義方程式（式１）の係数ａ、ｂは使用しないため、ステップＳ１１で読み出す必要はなく、ステップＳ１４の前であればよい。
【００４７】
楕円曲線Ｅ（ＧＦ（ｑ）)上の点Ｐを取得した処理部１２０は、記憶部１１１に記憶するか、または、出力部１３２や通信部１３３を介して、楕円曲線Ｅ（ＧＦ（ｑ）)上の点Ｐを出力する（Ｓ１７）。
【００４８】
図４は、有理関数計算部１２１と、有限体演算計算部１２２での楕円曲線Ｅ（ＧＦ（ｑ）)上の点Ｐの生成処理を示すフローチャートである。
【００４９】
ここで、本実施形態では、Ｅを、ａ、ｂが定義方程式（式１）の係数である有限体ＧＦ（ｑ）上定義された楕円曲線、φ、ψ、ωを、有限体ＧＦ（ｑ）を係数にもつ１次または２次の多項式とする。
【００５０】
以下、集合ＧＦ（ｑ）＊／｛１，−１｝∪｛０｝の元ｔと集合｛１，−１｝の元ιから上記楕円曲線Ｅ（ＧＦ（ｑ）)上の点Ｐを生成する方法を具体的に説明する。
【００５１】
有理関数計算部１２１と、有限体演算計算部１２２での楕円曲線上の点の生成処理は、集合ＧＦ（ｑ）＊／｛１，−１｝∪｛０｝の元ｔと集合｛１，−１｝の元ιを処理部１２０より受けることで開始される（Ｓ２０）。
【００５２】
処理部１２０より上記集合ＧＦ（ｑ）＊／｛１，−１｝∪｛０｝の元ｔと上記集合｛１，−１｝の元ιを受け取ると、有理関数計算部１２１は、入力された上記元ｔ∈ＧＦ（ｑ）＊／｛１，−１｝∪｛０｝からα＝φ（ｔ）／ω（ｔ）を計算する（Ｓ２１）。
【００５３】
そして、有限体演算計算部１２２は、有理関数計算部１２１より送信された上記α、上記楕円曲線ａ、ｂ、及び、上記素数べきｑを用いてτ＝−８α３−２ａα＋ｂを計算する（Ｓ２２）。
【００５４】
そして、有限体演算計算部１２２は、χｑ（τ）＝１であるかどうかを判定する（Ｓ２３）。そして、χｑ（τ）＝１である場合には（ステップＳ２３においてＹｅｓ）、ステップＳ２４に進み、χｑ（τ）＝１ではない場合には（ステップＳ２３においてＮｏ）、ステップＳ２５に進む。ここで、χｑは、ｓ∈（ＧＦ（ｑ）＊）２ならばχｑ（ｓ）＝１、ｓ∈（ＧＦ（ｑ）＊）２でないならばχｑ（ｓ）＝−１と定義される上記有限体の乗法群ＧＦ(ｑ）＊から集合｛１，−１｝への写像であり、２次指標と呼ばれている（さらにχｑ（０）＝０とし、χｑをＧＦ（ｑ）から｛０，１，−１｝への写像と拡張することもある。以下、上記χｑも上述のとおりに定義されるＧＦ（ｑ）から｛０，１，−１｝への写像とする）。
【００５５】
ステップＳ２４では、有限体演算計算部１２２は、τから√τを計算し、ｙに代入する（Ｓ２４）。
【００５６】
ステップＳ２５では、有限体演算計算部１２２は、τから√τ／ξ２を計算し、ｚに代入し、ｚω（ｔ）／ψ（ｔ）を計算してｗに代入する（Ｓ２５）。
【００５７】
ステップＳ２６では、有限体演算計算部１２２は、（−２α，ιｙ）をＰに代入し、上記Ｐを上記楕円曲線の点として出力する（Ｓ２６）。
【００５８】
ステップＳ２７では、有限体演算計算部１２２は、（ｗ２−２α，ι（ｗ２−３α）ｗ）をＰに代入し、上記Ｐを上記楕円曲線の点として出力する（Ｓ２７）。
【００５９】
なお、ステップＳ２４、及びステップＳ２５で実行する有限体における平方根計算については、例えば、H. Cohen， “A Course in Computational Algebraic Number Theory”， Springer-Verlag， GTM 138， 1993. に詳細に記載されている。
【００６０】
なお、ステップＳ２６、及びステップＳ２７で出力される上記Ｐが上記楕円曲線Ｅ（ＧＦ（ｑ））上の点であることは、上記楕円曲線Ｅ（ＧＦ（ｑ））の定義方程式（式１）にＰを代入することによって容易に確認することができる。
【００６１】
また、本実施形態では、上記集合ＧＦ（ｑ）＊／｛１，−１｝∪｛０｝の元ｔと集合｛１，−１｝の元ιに対して上記楕円曲線Ｅ（ＧＦ（ｑ））上の点ＰをＷｅｉｅｒｓｔｒａｓｓ型楕円曲線のアフィン座標で生成する方法を説明したが、Ｗｅｉｅｒｓｔｒａｓｓ型楕円曲線の射影座標、Ｗｅｉｅｒｓｔｒａｓｓ型楕円曲線のＪａｃｏｂｉａｎ座標などＷｅｉｅｒｓｔｒａｓｓ型楕円曲線のアフィン座標と異なる座標系で生成したり、Ｈｅｓｓｉａｎ型楕円曲線、Ｍｏｎｔｇｏｍｅｒｙ型楕円曲線、Ｅｄｗａｒｄｓ型楕円曲線上の点を生成することも可能である。この理由を、Ｗｅｉｅｒｓｔｒａｓｓ型楕円曲線のＪａｃｏｂｉａｎ座標の場合で説明する。
上記Ｗｅｉｅｒｓｔｒａｓｓ型楕円曲線のアフィン座標（Ｘ／Ｚ２，Ｙ／Ｚ３）とＷｅｉｅｒｓｔｒａｓｓ型楕円曲線のＪａｃｏｂｉａｎ座標（Ｘ：Ｙ：Ｚ）（Ｚ≠０）は対応している。このとき、本実施形態において、上記集合ＧＦ（ｑ）＊／｛１，−１｝∪｛０｝の元ｔと集合｛１，−１｝の元ιに対して、ステップＳ２６で出力される上記Ｗｅｉｅｒｓｔｒａｓｓ型楕円曲線のアフィン座標の点（−２α，ιｙ）に対応する上記Ｗｅｉｅｒｓｔｒａｓｓ型楕円曲線のＪａｃｏｂｉａｎ座標の点は（−２αω（ｔ）：ιｙω（ｔ）：ω（ｔ））、及び、ステップＳ２７で出力されるＷｅｉｅｒｓｔｒａｓｓ型楕円曲線のアフィン座標の点（ｗ２−２α，ι（ｗ２−３α）ｗ）に対応する上記Ｗｅｉｅｒｓｔｒａｓｓ型楕円曲線のＪａｃｏｂｉａｎ座標の点は（ξ２（τ−２ξ２αβ２ω（ｔ））：ιξ２（τ−３ξ２αβ２ω（ｔ））×√（ξ２τ）：ξ２βω（ｔ））であることが容易にわかるからである。ここで、τ＝−８α３ω（ｔ）−２ａαω（ｔ）３＋ｂω（ｔ）４である。したがって、上記集合ＧＦ（ｑ）＊／｛１，−１｝∪｛０｝の元ｔと集合｛１，−１｝の元ιに対して、Ｗｅｉｅｒｓｔｒａｓｓ型楕円曲線のＪａｃｏｂｉａｎ座標の点を生成するには、上記ステップＳ２１から上記ステップＳ２７の上記各ステップ（及び、図４の上記ステップＳ２１から上記ステップＳ２７の上記各ステップ）を以下のように変更すればよい：
α＝φ（ｔ）、γ＝ω（ｔ）を計算する（Ｓ２１）。
【００６２】
τ＝−８α３γ−２ａαγ３＋ｂγ４を計算する（Ｓ２２）。
【００６３】
χｑ（τ）＝１であるかどうかを判定する（Ｓ２３）。χｑ（τ）＝１である場合には（ステップＳ２３においてＹｅｓ）、ステップＳ２４に進み、χｑ（τ）＝１ではない場合には（ステップＳ２３においてＮｏ）、ステップＳ２５に進む。
【００６４】
√τを計算し、ｙに代入する（Ｓ２４）。
【００６５】
√（τξ２）を計算し、ｚに代入する（Ｓ２５）。
【００６６】
Ｐ＝（−２αγ：ιｙγ：γ）とし、上記Ｐを上記楕円曲線の点として出力する（Ｓ２６）。
【００６７】
Ｐ＝（ξ２（τ−２ξ２αβ２γ）：ιξ２（τ−３ξ２αβ２γ）×√（ξ２τ）：ξ２βγ）とし、上記Ｐを上記楕円曲線の点として出力する（Ｓ２７）。
【００６８】
また、上記多項式ω、ψの零点となる上記各零点ｚ０、ｚ１を上記２つの有理関数に付随する情報を格納する理由は以下の通りである。上記ステップＳ２１において、α＝φ（ｔ）／ω（ｔ）を計算する。ｔ＝ｚ０ならばω（ｚ０）＝０となるので、αを計算することができない（有理関数φ／ωはｔ＝ｚ０で定義されない）からである。さらに、上記ステップＳ２５において、ｗ＝ｚω（ｔ）／ψ（ｔ）を計算する。ｔ＝ｚ１ならばψ（ｚ１）＝０となるので、ｗを計算することができない（有理関数ｚω／ψはｔ＝ｚ１で定義されない）からである。
【００６９】
そのため、上記ｚ０，ｚ１に対応する楕円曲線Ｅ（ＧＦ（ｑ））上の点Ｐ０，Ｐ１を予め定めておき、ステップＳ２０でｔ＝ｚ０またはｔ＝ｚ１が入力された場合は上記予め定められた点Ｐ０，Ｐ１を出力してもよいし、ｔ＝ｚ０またはｔ＝ｚ１が入力された場合、ｔ＝ｔ＋１とし、ｔ≠ｚ０かつｔ≠ｚ１となるまでｔ＝ｔ＋１を繰り返してもよいし、上記集合ＧＦ（ｑ）＊／｛１，−１｝∪｛０｝からω（ｔ）＝０なる元ｔ∈ＧＦ（ｑ）＊／｛１，−１｝∪｛０｝、及びψ（ｔ）＝０なる元ｔ∈ＧＦ（ｑ）＊／｛１，−１｝∪｛０｝を予め除いておいてもよい。
【００７０】
ω（ｚ０）＝０なる元ｚ０∈ＧＦ（ｑ）＊／｛１，−１｝∪｛０｝の個数、及びψ（ｚ１）＝０なる元ｚ１∈ＧＦ（ｑ）＊／｛１，−１｝∪｛０｝の個数はそれぞれ高々２個であるから、上記ｔ＝ｔ＋１なる繰り返し回数は高々４回であり、上記ｔ＝ｔ＋１なる繰り返しの処理時間は、上記ステップＳ２４、または上記ステップＳ２５の平方根計算の処理時間と比べると非常に小さいので、上記ステップＳ２０の入力によって、上記点の生成処理時間は大きくばらつくことはない。
【００７１】
上記有理関数φ／ω、ψ／ωは、例えば以下に示す方法で決定することができる。一般に、有限体ＧＦ（ｑ）上定義された上記２次曲線Ｃ上の点（α０，β０）を一つ決め、固定する。上記２次曲線Ｃの上記点（α０，β０）以外の任意の点（α，β）に対し、上記点（α０，β０）と上記点（α，β）を結んだ直線とｘ軸（または、ｙ軸）との交点をｔとすることにより、上記２次曲線Ｃから上記点（α０，β０）を除いた集合から上記有限体ＧＦ(ｑ）への写像が構成できる。この逆写像（ｔ→（φ／ω）（ｔ），（ψ／ω）（ｔ））を上記有理関数とすればよい。
【００７２】
また、本実施形態を用いることによって、楕円曲線上に値を持つハッシュ関数を容易に構成することができる理由は以下の通りである。例えば、非特許文献２に記載の署名では、任意長のビット列｛０，１｝＊から楕円曲線Ｅ（ＧＦ（ｑ））へのハッシュ関数Ｈ：｛０，１｝＊→Ｅ（ＧＦ（ｑ））を使用する。ｈを任意長のビット列｛０，１｝＊から固定長のビット列｛０，１｝ｍへの暗号学的ハッシュ関数（例えば、ＳＨＡ−２５６など）とし、上記素数べきｑのビット長｜ｑ｜＝ｍとする。任意長のビット列Ｍ∈｛０，１｝＊に対し、上記Ｍのハッシュ値ｈ（Ｍ）を計算し、上位ｍ−１ビットをｔ、最下位１ビットをιとする。すなわち、Ｍ＝ｔ｜｜ιである。ここで、｜｜は２つのビット列の結合を表す。
【００７３】
上記ｔを予め定められた方法でＧＦ（ｑ）の元と見なし（例えば、ビット列ｔ＝ｔｍ−２ｔｍ−１．．．ｔ０に対し、ｔ＝ｔｍ−２２ｍ−２＋ｔｍ−１２ｍ−１＋．．．＋ｔ０とする）、上記ｔ∈ＧＦ（ｑ）＊／｛１，−１｝∪｛０｝と上記ι∈｛１，−１｝に対して本実施形態に記載の点生成方法で生成した点Ｐを上記ビット列Ｍに対するハッシュ値とすることにより、特許文献２に記載の署名に記載されている任意長のビット列｛０，１｝＊から楕円曲線Ｅ（ＧＦ（ｑ））へのハッシュ関数Ｈ：｛０，１｝＊→Ｅ（ＧＦ（ｑ））が構成できる。
【００７４】
また、任意長のビット列｛０，１｝＊から｛ＧＦ（ｑ）＊／｛１，−１｝∪｛０｝)×｛１，−１｝へのハッシュ関数の構成方法は、実現可能であればその方法は問わない。さらに、楕円曲線上に値を持つその他のハッシュ関数（例えば、非特許文献１など）も上記ハッシュ関数Ｈと類似の方法で実現可能である。
【００７５】
以上の通り、本実施形態の楕円曲線上の点生成は、一般の楕円曲線に適用可能であり、入力に応じて処理性能に大きなばらつきがないような楕円曲線上の点の生成が可能になる。
【実施例２】
【００７６】
次に、第二の実施形態である楕円曲線上の点の生成方法について説明する。
【００７７】
第一の実施形態に記載の楕円曲線上の点の生成方法をΦとし、写像
ｆ１、ｆ２、ｆ３を、
ｆ１：ＧＦ（ｑ）＊／｛１，−１｝∪｛０｝→Ｃ（ＧＦ（ｑ）），
ｔ→ｆ１（ｔ）＝（α＝φ（ｔ）／ω（ｔ），β＝ψ（ｔ）／ω（ｔ））
（式２）
ｆ２：Ｃ（ＧＦ（ｑ））→Ｅ（１）（ＧＦ（ｑ２）／ＧＦ（ｑ）），
（α，β）→Ｑ＝（α＋βξ，√Ｆ（α＋βξ）） （式３）
ｆ３：Ｅ（１）（ＧＦ（ｑ２）／ＧＦ（ｑ））→Ｅ（ＧＦ（ｑ）），
Ｑ＝（α＋βξ，√Ｆ（α＋βξ））→Ｑ＋σ（Ｑ） （式４）
とする。ここで、（式２）のφ、ψ、ωは上記有限体ＧＦ（ｑ）を係数にもつ１次または２次の多項式であり、（式３）のＦ（α＋βξ）は（式１）の定義方程式の右辺Ｆ（ｘ）＝ｘ３＋ａｘ＋ｂよりＦ（α＋βξ）＝（α＋βξ）３＋ａ（α＋βξ）＋ｂである。上記楕円曲線Ｅ上の点Ｐ１，Ｐ２に対して、Ｐ１＝Ｐ２またはＰ１＝−Ｐ２のとき、Ｐ１〜Ｐ２なる同値関係を定義する。Ｅ（１）（ＧＦ（ｑ２）／ＧＦ（ｑ））、Ｅ（ＧＦ（ｑ））はそれぞれ集合｛（ｘ，ｙ）∈Ｅ（ＧＦ（ｑ２））｜ｘ∈ＧＦ（ｑ２）−ＧＦ（ｑ），ｙ２∈ＧＦ（ｑ）｝、集合Ｅ（（ＧＦ（ｑ））を同値関係〜で割った集合である。σはｑ乗Ｆｒｏｂｅｎｉｕｓ写像である。このとき、上記集合ＧＦ（ｑ）＊／｛１，−１｝∪｛０｝の元ｔ、及び上記集合｛１，−１｝の元ιから第一の実施形態に記載の方法で生成した点ＰはＰ＝ｆ３（ｆ２（ｆ１（ｔ，ι）））に他ならない。
【００７８】
第二の実施形態は、第一の実施形態における上記有限体ＧＦ（ｑ）を２次拡大体ＧＦ（ｑ２）、上記有限体ＧＦ（ｑ）の乗法群ＧＦ(ｑ）＊を２次拡大体ＧＦ（ｑ２）の乗法群ＧＦ（ｑ２）＊、２次拡大体ＧＦ(ｑ２）を２次拡大体ＧＦ(ｑ２）の２次拡大（上記有限体ＧＦ（ｑ）の４次拡大）ＧＦ（ｑ４）、として第一の実施形態に記載の方法で楕円曲線ＥのＧＦ（ｑ２）有理点を生成し、さらに上記楕円曲線Ｅ（ＧＦ（ｑ２））上の点から（式9）を用いて上記楕円曲線Ｅ（ＧＦ（ｑ））上の点を生成する方法である。
【００７９】
ここで、本実施形態における点生成装置も、第一の実施形態と同様に、記憶部１１１と、処理部１２０と、入力部１３１と、出力部１３２と、通信部１３３と、を備える。
【００８０】
本実施形態では、点生成装置で集合ＧＦ（ｑ２）＊／｛１，−１｝∪｛０｝の元ｔと集合｛１，−１｝の元ιに対する上記有限体ＧＦ（ｑ）上定義された楕円曲線Ｅ（ＧＦ（ｑ）)上の点の生成を行う。
【００８１】
記憶部１１１の機能構成は第一の実施形態と同様である。
【００８２】
有理関数記憶領域１１２は、上記有限体ＧＦ（ｑ２）から有限体ＧＦ（ｑ２）上定義された２次曲線Ｃへの２つの有理関数に関する情報、及び上記２つの有理関数に付随する情報が格納される。ここで、上記有限体ＧＦ（ｑ２）から有限体ＧＦ（ｑ２）上定義された２次曲線Ｃへの２つの有理関数とは、上記有限体ＧＦ（ｑ２）を係数にもつ１次または２次の多項式φ、ω、ψを用いてφ／ω、ψ／ωと表わされる関数であり、上記有限体ＧＦ（ｑ２）から有限体ＧＦ（ｑ２）上定義された２次曲線Ｃへの２つの有理関数に関する情報とは、例えば、上記φ、ω、ψの各係数である。また、上記有理関数φ／ω、ψ／ωの極（すなわち、ω（ｚ０）＝０）となる上記有限体ＧＦ（ｑ２）の元ｚ０、及び上記多項式ψの零点（すなわち、ψ（ｚ１）＝０）となる上記有限体ＧＦ（ｑ２）の元ｚ１である。なお、上記多項式ω、ψの零点となる上記各零点ｚ０、ｚ１を上記２つの有理関数に付随する情報を格納する理由については後述する。
【００８３】
基底記憶領域１１３には、上記有限体ＧＦ（ｑ２）の２次拡大ＧＦ（ｑ４）の基底に関する情報が格納される。例えば、本実施形態においては、ξ∈ＧＦ（ｑ４）−ＧＦ（ｑ２）、ｃ＝ξ２∈ＧＦ（ｑ２）なる元ξが上記有限体ＧＦ（ｑ２）の２次拡大ＧＦ（ｑ４）の基底に関する情報である。また、上記元ｃ∈ＧＦ（ｑ２）も上記基底に関する情報として格納しておいてもよい。ここで、ＧＦ（ｑ４）−ＧＦ（ｑ２）は上記有限体ＧＦ（ｑ２）の２次拡大ＧＦ（ｑ４）から上記有限体ＧＦ（ｑ２）の元を除いた集合を表わす。上記ξ、及び上記有限体ＧＦ（ｑ２）の乗算に関する単位元１は、上記２次拡大ＧＦ（ｑ４）の上記有限体ＧＦ（ｑ２）上の基底である。
【００８４】
パラメータ記憶部は、有限体ＧＦ（ｑ）、及び上記有限体ＧＦ（ｑ）上定義された楕円曲線Ｅ（ＧＦ（ｑ）)に関する情報が格納される。例えば、本実施形態においては、上記素数べきｑ、及び上記楕円曲線Ｅ（ＧＦ（ｑ）)の定義方程式（式１）の係数ａ、ｂである。
【００８５】
処理部１２０の機能構成も第一の実施形態と同様である。
【００８６】
例えば、本実施形態では、処理部１２０は、集合ＧＦ（ｑ２）＊／｛１，−１｝∪｛０｝の元ｔと集合｛１，−１｝の元ιに対する上記楕円曲線Ｅ（ＧＦ（ｑ）)上の点を生成する処理を制御する。ここで、上記集合ＧＦ（ｑ２）＊／｛１，−１｝∪｛０｝とは、有限体の乗法群ＧＦ（ｑ２）＊の元ｇに対して、ｇ＋ｈ＝０、またはｇ−ｈ＝０なる同値関係によって上記有限体の乗法群ＧＦ（ｑ２）＊を割った集合を表わす。
【００８７】
例えば、本実施形態では、処理部１２０は、入力データである上記元ｔと上記元ιに対して、有理関数記憶領域１１２に格納されている上記有理関数φ／ω、ψ／ωと、基底記憶領域１１３に格納されているＧＦ（ｑ４）−ＧＦ（ｑ２）の元ξを取得して、ｔとともに、有理関数計算部１２１に送信する。有理関数計算部１２１は、予め定められたアルゴリズムによる計算を行い、上記有限体ＧＦ（ｑ２）の２つの元α、βを生成する。そして、有理関数計算部１２１は、上記α、β、ξ、及び、パラメータ記憶部１１４に格納されている上記ａ、ｂを有限体演算計算部１２２に送信する。
【００８８】
有限体演算計算部１２２は、予め定められたアルゴリズムによる計算を行い、上記楕円曲線Ｅ（ＧＦ（ｑ）)上の点Ｐを生成する。有限体演算計算部１２２は、上記生成した上記楕円曲線Ｅ（ＧＦ（ｑ）)上の点Ｐを処理部１２０に出力する。入力部１３１は、情報の入力を受け付ける。出力部１３２は、情報を出力する。通信部１３３は、記憶部１１１と、処理部１２０と、入力部１３１と、出力部１３２と、の間の情報の送受信を行う。
【００８９】
以上に記載した点生成装置１００も、第一の実施形態と同様、例えば、図２（コンピュータ１４０の概略図）に示すような、ＣＰＵ１４１と、メモリ１４２と、ＨＤＤ等の外部記憶装置１４３と、ＣＤ−ＲＯＭやＤＶＤ−ＲＯＭ等の可搬性を有する記憶媒体１４４から情報を読み出す読取装置１４５と、キーボードやマウスなどの入力装置１４６と、ディスプレイなどの出力装置１４７と、通信ネットワークに接続するためのＮＩＣ（Network Interface Card）等の通信装置１４８と、を備えた一般的なコンピュータ１４０で実現できる。処理部１２０が、外部記憶装置１４３に記憶されている所定のプログラムをメモリ１４２にロードしてＣＰＵ１４１で実行することで実現可能であることも、第一の実施形態と同様である。
【００９０】
本実施形態の点生成装置１００における点生成処理を示すシーケンス図も第一の実施形態（図３）と同様である。ただし、ステップＳ１０のｔは、ＧＦ（ｑ２）＊／｛１，−１｝∪｛０｝の元、ステップＳ１１、及びステップＳ１２のφ、ω、ψは上記有限体ＧＦ（ｑ２）を係数にもつ１次または２次の多項式、ステップＳ１１、及びステップ１４のξはＧＦ（ｑ４）のＧＦ（ｑ２）上の上記基底、ステップＳ１３、及びステップＳ１４のα、βは上記有限体ＧＦ（ｑ２）の元、である。
【００９１】
図５は、有理関数計算部１２１と、有限体演算計算部１２２での楕円曲線Ｅ（ＧＦ（ｑ）)上の点Ｐの生成処理を示すフローチャートである。
【００９２】
ここで、本実施形態では、Ｅを、ａ、ｂが定義方程式（式１）の係数である有限体ＧＦ(ｑ）上定義された楕円曲線、φ、ψ、ωを、上記有限体ＧＦ（ｑ２）を係数にもつ１次または２次の多項式とする。
【００９３】
以下、集合ＧＦ（ｑ２）＊／｛１，−１｝∪｛０｝の元ｔと集合｛１，−１｝の元ιから上記楕円曲線Ｅ（ＧＦ（ｑ）)上の点Ｐを生成する方法を具体的に説明する。
【００９４】
有理関数計算部１２１と、有限体演算計算部１２２での楕円曲線上の点の生成処理は、集合ＧＦ（ｑ２）＊／｛１，−１｝∪｛０｝の元ｔと集合｛１，−１｝の元ιを処理部１２０より受けることで開始される（Ｓ３０）。
【００９５】
処理部１２０より上記集合ＧＦ（ｑ２）＊／｛１，−１｝∪｛０｝の元ｔと上記集合｛１，−１｝の元ιを受け取ると、有理関数計算部１２１は、入力された上記元ｔ∈ＧＦ（ｑ２）＊／｛１，−１｝∪｛０｝からα＝φ（ｔ）／ω（ｔ）を計算する（Ｓ３１）。
【００９６】
そして、有限体演算計算部１２２は、有理関数計算部１２１より送信された上記α、上記楕円曲線ａ、ｂ、及び、上記素数べきｑを用いてτ＝−８α３−２ａα＋ｂを計算する（Ｓ３２）。
【００９７】
そして、有限体演算計算部１２２は、χｑ２（τ）＝１であるかどうかを判定する（Ｓ３３）。そして、χｑ２（τ）＝１である場合には（ステップＳ３３においてＹｅｓ）、ステップＳ３４に進み、χｑ２（τ）＝１ではない場合には（ステップＳ３３においてＮｏ）、ステップＳ３５に進む。ここで、χｑ２は、ｓ∈（ＧＦ（ｑ２）＊）２ならばχｑ２（ｓ）＝１、ｓ∈（ＧＦ（ｑ２）＊）２でないならばχｑ２（ｓ）＝−１と定義される上記有限体の乗法群ＧＦ（ｑ２）＊から集合｛１，−１｝への写像である（さらにχｑ２（０）＝０とし、χｑ２をＧＦ（ｑ２）から｛０，１，−１｝への写像と拡張することもある。以下、上記χｑ２も上述のとおりに定義されるＧＦ(ｑ）から｛０，１，−１｝への写像とする）。
【００９８】
ステップＳ３４では、有限体演算計算部１２２は、τから√τを計算し、ｙに代入する（Ｓ３４）。
【００９９】
ステップＳ３５では、有限体演算計算部１２２は、τから√τ／ξ２を計算し、ｚに代入し、ｚω（ｔ）／ψ（ｔ）を計算してｗに代入する（Ｓ３５）。
【０１００】
ステップＳ３６では、有限体演算計算部１２２は、（−２α，ιｙ）をＱに代入する（Ｓ３６）。
【０１０１】
ステップＳ３７では、有限体演算計算部１２２は、（ｗ２−２α，ι（ｗ２−３α）ｗ）をＱに代入する（Ｓ３７）。
【０１０２】
ステップＳ３８では、Ｑ＋σ（Ｑ）をＰに代入し、上記Ｐを上記楕円曲線の点として出力する（Ｓ３７）。ここで、σはｑ乗Ｆｒｏｂｅｎｉｕｓ写像である。
なお、ステップＳ３４、ステップＳ３５、及びステップＳ３７（Ｑ＋σ（Ｑ）の計算）で実行する有限体における平方根計算については、例えば、H. Cohen， “A Course in Computational Algebraic Number Theory”， Springer-Verlag， GTM 138， 1993. に詳細に記載されている。
【０１０３】
なお、ステップＳ３７で出力される上記Ｐが上記楕円曲線Ｅ（ＧＦ（ｑ））上の点であることも、第一の実施形態と同様、上記楕円曲線Ｅ（ＧＦ（ｑ））の定義方程式（式１）にＰを代入することによって容易に確認することができる。
【０１０４】
また、本実施形態では、上記集合ＧＦ（ｑ）＊／｛１，−１｝∪｛０｝の元ｔと集合｛１，−１｝の元ιに対して上記楕円曲線Ｅ（ＧＦ（ｑ））上の点ＰをＷｅｉｅｒｓｔｒａｓｓ型楕円曲線のアフィン座標で生成する方法を説明したが、Ｗｅｉｅｒｓｔｒａｓｓ型楕円曲線の射影座標、Ｗｅｉｅｒｓｔｒａｓｓ型楕円曲線のＪａｃｏｂｉａｎ座標などＷｅｉｅｒｓｔｒａｓｓ型楕円曲線のアフィン座標と異なる座標系で生成したり、Ｈｅｓｓｉａｎ型楕円曲線、Ｍｏｎｔｇｏｍｅｒｙ型楕円曲線、Ｅｄｗａｒｄｓ型楕円曲線上の点を生成することも可能である。この理由も第一の実施形態と同様である。
【０１０５】
また、上記多項式ω、ψの零点となる上記各零点ｚ０、ｚ１を上記２つの有理関数に付随する情報を格納する理由、及び、上記集合ＧＦ（ｑ２）＊／｛１，−１｝∪｛０｝の元ｔがｚ０、またはｚ１と等しい場合における上記楕円曲線Ｅ（ＧＦ（ｑ））上の点Ｐの生成方法も第一の実施形態と同様である。
【０１０６】
上記有理関数φ／ω、ψ／ωの決定方法も第一の実施形態と同様である。
【０１０７】
また、本実施形態を用いることによって、楕円曲線上に値を持つハッシュ関数を容易に構成することができる理由は以下の通りである。例えば、非特許文献２に記載の署名では、上述の通り、任意長のビット列｛０，１｝＊から楕円曲線Ｅ（ＧＦ（ｑ））へのハッシュ関数Ｈ：｛０，１｝＊→Ｅ（ＧＦ（ｑ））を使用する。ｈを任意長のビット列｛０，１｝＊から固定長のビット列｛０，１｝２ｍへの暗号学的ハッシュ関数（例えば、ＳＨＡ−２５６など）とし、上記素数べきｑのビット長｜ｑ｜＝ｍとする。任意長のビット列Ｍ∈｛０，１｝＊に対し、上記Ｍのハッシュ値ｈ（Ｍ）を計算し、上位（ｍ−１）／２ビットをｔ１、次の（ｍ−１）／２ビットをｔ２、最下位２ビットをιとする。すなわち、Ｍ＝ｔ１｜｜ｔ２｜｜ιである。ここで、｜｜は２つのビット列の結合を表す。上記ｔ１、ｔ２を予め定められた方法でＧＦ（ｑ）の元と見なし（例えば、ビット列ｔ１＝ｔ１，ｍ−２ｔ１，ｍ−３．．．ｔ１，０、ｔ２＝ｔ２，ｍ−２ｔ２，ｍ−３．．．ｔ２，０、に対し、ｔ１＝ｔ１，ｍ−２２ｍ−２＋ｔ１，ｍ−３２ｍ−３＋．．．＋ｔ１，０、ｔ２＝ｔ２，ｍ−２２ｍ−２＋ｔ２，ｍ−３２ｍ−３＋．．．＋ｔ２，０とする）、さらに、ι＝ι１｜｜ι２、すなわち、ιの上位１ビットをι１、ιの下位１ビットをι２とする。上記ｔ＝ｔ１＋ｔ２ξ∈ＧＦ（ｑ２）＊／｛１，−１｝∪｛０｝と上記ι１（または、ι２）∈｛１，−１｝に対して本実施形態に記載の点生成方法で生成した点Ｐを上記ビット列Ｍに対するハッシュ値とすることにより、特許文献２に記載の署名に記載されている任意長のビット列｛０，１｝＊から楕円曲線Ｅ（ＧＦ（ｑ））へのハッシュ関数Ｈ：｛０，１｝＊→Ｅ（ＧＦ（ｑ））が構成できる。また、任意長のビット列｛０，１｝＊から｛ＧＦ（ｑ２）＊／｛１，−１｝∪｛０｝)×｛１，−１｝へのハッシュ関数の構成方法は、実現可能であればその方法は問わない。さらに、楕円曲線上に値を持つその他のハッシュ関数（例えば、非特許文献１など）も上記ハッシュ関数Ｈと類似の方法で実現可能である。
【０１０８】
以上の通り、本実施形態の楕円曲線上の点生成は、一般の楕円曲線に適用可能であり、入力に応じて処理性能に大きなばらつきがないような楕円曲線上の点の生成が可能になる。
【符号の説明】
【０１０９】
１００：点生成装置、１１１：記憶部、１１２：有理関数記憶領域、１１３：基底記憶領域、１１４：パラメータ記憶領域、１２０：処理部、１２１：有理関数計算部、１２２：有限体演算計算部、１３１：入力部、１３２：出力部、１３３：通信部。
【技術分野】
【０００１】
本発明は、セキュリティ技術に係り、特に楕円曲線上の点を生成する処理技術に関する。
【背景技術】
【０００２】
デジタル署名（以下、署名）は電子データに対する印鑑の役割を果たす。署名対象の電子データに対し、署名者は秘密にしている署名鍵を用いて署名データを生成し、もとの電子データと共に検証者に送信する。検証者は上記電子データ、及び、公開されている検証鍵を用い、上記署名データが署名者によって生成されたかどうかを検証する。従って、署名データは署名鍵を保持する者しか生成できず、また有効に生成された署名データは署名検証時に「有効」として受け入れられ、そうでないものは「無効」として拒絶されるような仕組みになっていなければならない。
【０００３】
上述の署名方法は1978年にＲ．Ｒｉｖｅｓｔ、Ａ．Ｓｈａｍｉｒ、Ｌ．Ａｄｌｅｍａｎにより公開鍵暗号技術を用いて実現された。その後、署名の安全性を暗号学的に証明する安全性証明理論の構築及び整備、効率性向上の技術のみならず、プライバシ問題を考慮したグループ署名のような特殊機能をもつ署名などが盛んに研究されている。
【０００４】
一般に、署名は任意長データを固定長データに圧縮するハッシュ関数と、数学関数を用いた公開鍵暗号プリミティブの組み合わせで構成されている。このような公開鍵暗号プリミティブのうち、有限体上定義された楕円曲線に基づくものは、素因数分解問題の困難性に基づくもの（ＲＳＡ、Ｒａｂｉｎなど）と比較して短い鍵長で同程度の安全性を達成でき、よって高速処理が可能であることから特に注目を集めている。
【０００５】
楕円曲線を利用した暗号や署名はＮ．Ｋｏｂｌｉｔｚ、Ｖ．Ｓ．Ｍｉｌｌｅｒにより提案された。一般に有限体ＧＦ(q)上で定義された楕円曲線のうちＷｅｉｅｒｓｔｒａｓｓ型と呼ばれるものは
ｙ２＝Ｆ（ｘ）＝ｘ３＋ａｘ＋ｂ，（ａ、ｂはともに有限体ＧＦ(q)の元） （式１）
の形の定義式で与えられる。上記で定義された楕円曲線に対し、（式１）を満たすＧＦ(q)の元の組（ｘ，ｙ）のことをＧＦ(q)有理点と呼ぶ。
【０００６】
近年、楕円曲線を用いた署名では長らく未解決であったｔｉｇｈｔ ｓｅｃｕｒｉｔｙ ｒｅｄｕｃｔｉｏｎを持つものも提案されている（例えば、非特許文献１参照。）。ここで、ｔｉｇｈｔ ｓｅｃｕｒｉｔｙ ｒｅｄｕｃｔｉｏｎとは、署名を偽造する困難性と、その署名の構成要素である公開鍵暗号プリミティブが安全性の根拠とする数論問題（例えば、素因数分解問題、有限体の乗法群／有限体上定義された楕円曲線の離散対数問題など）を解くための困難性が同程度（等価）であることを意味する。
【０００７】
上述の非特許文献１や非特許文献２などに記載されている署名は、楕円曲線上に値を持つハッシュ関数が利用されている。一般の楕円曲線上に値を持つハッシュ関数が非特許文献３に、特殊な楕円曲線上に値を持つハッシュ関数が非特許文献３、４に、それぞれ記載されている。
【先行技術文献】
【非特許文献】
【０００８】
【非特許文献１】B. Chevallier-Mames， “An Efficient CDH-based Signature Scheme With a Tight Security Reduction”， Advances in Cryptology - CRYPTO 2005， LNCS 3621， Springer-Verlag， pp.511−526， 2005.
【非特許文献２】E. J. Goh， S. Jarecki， “A signature Scheme as secure as the Diffie-Hellman Problem”， Advances in Cryptology - EUROCRYPT 2003， LNCS 2656， Springer-Verlag， pp.401-415， 2003.
【非特許文献３】D. Boneh， H. Shacham， and B. Lynn， “Short Signatures from the Weil Pairing”， Advances in Cryptology - ASIACRYPT 2001， LNCS 2248， Springer-Verlag， pp.514-532， 2001.
【非特許文献４】P. S. L. M. Barreto and H. Y. Kim， “Fast Hashing onto Elliptic Curves over Fields of Characteristic 3”， Cryptology ePrint Archive， Report 2001/098， 2001. available from: http://eprint.iacr.org/2001/098
【発明の概要】
【発明が解決しようとする課題】
【０００９】
情報化社会の高度化に伴い、電子情報に対する署名や、通信相手や機器を認証する技術は不可欠となってきている。上述のとおり、暗号技術に課せられる要件としては、安全性や効率性などがある。
【００１０】
非特許文献３に記載されている一般の楕円曲線に値を持つハッシュ関数は、予め定められた集合の元ｒから（式１）のｘ座標の候補を生成し、対応するｙ座標が定義体に含まれているかどうかを判定し、含まれていなければ、ある決まった方法にてｘを取替え、ｙ座標が含まれるまで繰り返す、という方法（以下、これを試行錯誤法と呼ぶ）である。試行錯誤法の場合、Ｈａｓｓｅの定理より繰り返しの平均回数は１．５回程度であることが知られているが、回数の分布にはばらつきがあり、実際にはそれを大幅に上回る計算が必要となることもしばしば起こる。ｙ座標が定義体に含まれるか否かを判定するにはある程度の処理が必要で、２、３回程度なら許容できたとしてもそれを超える回数では全体の処理においてボトルネックになる。
【００１１】
一方、非特許文献３、４に記載されている特殊な楕円曲線に値を持つハッシュ関数は、予め定められた集合の元ｒから（式１）のｘ座標の候補を生成し、対応するｙ座標を上記特殊な楕円曲線の定義方程式の性質を用いて決定する、という方法（以下、これを特殊曲線法と呼ぶ）であり、上述の一般の楕円曲線に値を持つハッシュ関数で実施する繰り返しを避け、効率性を向上させるために提案された方法である。
【００１２】
一般にハッシュ関数は、署名に用いる場合など、高効率性および入力に非依存な処理時間が求められることが多く、上述の試行錯誤法のように入力に応じて処理性能に大きなばらつきがある（繰り返し回数が変わるため）のは望ましくない。また、上述の特殊曲線法は特殊な楕円曲線のみに適用可能であり、一般の楕円曲線では同様の手法を用いることはできない。
【課題を解決するための手段】
【００１３】
本発明は、上記課題に鑑みてなされたもので、一般の楕円曲線に適用可能であり、入力に応じて処理性能が大きくばらつくことのない楕円曲線上の点の生成を実現する楕円曲線上の点生成方法および点生成装置を提供する。
【００１４】
以上の課題を解決するため、本発明は、楕円曲線の拡大体における有理点を使用する。
【００１５】
例えば、本発明は、有限集合の元から予め定められた有限体ＧＦ（ｑ）（ｑ：奇素数ｐのべき）上で定義された二次曲線ＣのＧＦ（ｑ）有理点を生成するステップと、
前記生成した二次曲線ＣのＧＦ（ｑ）有理点から当該楕円曲線のＧＦ（ｑ２）有理点を生成するステップと、
前記楕円曲線ＥのＧＦ（ｑ２）有理点と前記有限集合の元の一部から前記楕円曲線ＥのＧＦ（ｑ）有理点を生成するステップと、
を備えることを特徴とする。
【００１６】
より具体的な本発明の態様は、要素数が（ｑ＋１）／２（ｑは５以上の素数べき）の集合Ｓの元と要素数が２の集合Ｔの元から有限体ＧＦ（ｑ）上定義された楕円曲線ＥのＧＦ（ｑ）有理点を生成する点生成方法であって、
当該楕円曲線上の点生成方法は、
前記集合Ｓの元から予め定められた前記有限体ＧＦ（ｑ）上定義された二次曲線ＣのＧＦ（ｑ）有理点を生成する第一のステップと、
前記第一のステップで生成した前記二次曲線Ｃの前記ＧＦ（ｑ）有理点から前記楕円曲線ＥのＧＦ（ｑ２）有理点を生成する第二のステップと、
前記第二のステップで生成した前記楕円曲線ＥのＧＦ（ｑ２）有理点と前記集合Ｔの元から前記楕円曲線ＥのＧＦ（ｑ）有理点を生成する第三のステップと、
を備えることを特徴とする。
【００１７】
上記楕円曲線上の点生成方法において、さらに、
前記集合Ｓは集合ＧＦ（ｑ）＊／｛１，−１｝∪｛０｝、前記集合Ｔは｛１，−１｝であって、
前記第一のステップは、前記集合Ｓの元ｔから予め定められた２つのＧＦ（ｑ）上の有理関数α、βに対して、α（ｔ）、β（ｔ）を計算し、前記二次曲線ＣのＧＦ（ｑ）有理点Ｒ＝（α、β）を生成し、
前記第二のステップは、予め定められた前記有限体ＧＦ（ｑ２）の前記有限体ＧＦ（ｑ）上の基底（ξ，１）、及び前記二次曲線ＣのＧＦ（ｑ）有理点（α、β）から前記楕円曲線ＥのＧＦ（ｑ２）有理点Ｐ＝（α＋βξ，√（Ｆ（α＋βξ）））（Ｆは前記楕円曲線ＥのＷｅｉｅｒｓｔｒａｓｓ型の定義方程式ｙ２＝ｘ３＋ａｘ＋ｂ＝Ｆ（ｘ）に対して、Ｆ（ｘ）＝ｘ３＋ａｘ＋ｂなる多項式）を生成し、
前記第三のステップは、前記楕円曲線ＥのＧＦ（ｑ２）有理点Ｐから前記楕円曲線ＥのＦｒｏｂｅｎｉｕｓ自己準同型写像σを用いて前記楕円曲線ＥのＧＦ（ｑ）有理点（Ｐ＋σ（Ｐ））を生成してもよい。
【００１８】
また、具体的な本発明の他の態様は、要素数が（ｑ２＋１）／２（ｑは５以上の素数べき）の集合Ｓの元と要素数が２の集合Ｔの元から有限体ＧＦ（ｑ）上定義された楕円曲線ＥのＧＦ（ｑ）有理点を生成する点生成方法であって、
当該楕円曲線上の点生成方法は、
前記集合Ｓの元から予め定められた前記有限体ＧＦ（ｑ２）上定義された二次曲線ＣのＧＦ（ｑ２）有理点を生成する第四のステップと、
前記第四のステップで生成した前記二次曲線Ｃの前記ＧＦ（ｑ２）有理点から前記楕円曲線ＥのＧＦ（ｑ４）有理点を生成する第五のステップと、
前記第五のステップで生成した前記楕円曲線ＥのＧＦ（ｑ４）有理点と前記集合Ｔの元から前記楕円曲線ＥのＧＦ（ｑ）有理点を生成する第六のステップと、
を備えることを特徴とする。
【００１９】
上記楕円曲線上の点生成方法において、さらに、
前記集合Ｓは集合ＧＦ（ｑ２）＊／｛１，−１｝∪｛０｝、前記集合Ｔは｛１，−１｝であって、
前記第四のステップは、前記集合Ｓの元ｔから予め定められた２つのＧＦ（ｑ２）上の有理関数α、βに対して、α（ｔ）、β（ｔ）を計算し、前記二次曲線ＣのＧＦ（ｑ２）有理点Ｒ＝（α、β）を生成し、
前記第五のステップは、予め定められた前記有限体ＧＦ（ｑ４）の前記有限体ＧＦ（ｑ２）上の基底（ξ，１）、及び前記二次曲線ＣのＧＦ（ｑ２）有理点（α、β）に対して、前記楕円曲線ＥのＧＦ（ｑ２）有理点Ｐ＝（α＋βξ，√（Ｆ（α＋βξ）））（Ｆは前記楕円曲線ＥのＷｅｉｅｒｓｔｒａｓｓ型の定義方程式ｙ２＝ｘ３＋ａｘ＋ｂ＝Ｆ（ｘ）なる多項式）を生成し、
前記第六のステップは、前記楕円曲線ＥのＧＦ（ｑ４）有理点Ｐから、前期楕円曲線ＥのＦｒｏｂｅｎｉｕｓ自己準同型写像σを用いて前記楕円曲線ＥのＧＦ（ｑ）有理点Ｐ＋σ（Ｐ）＋σ２（Ｐ）＋σ３（Ｐ）を生成してもよい。
【発明の効果】
【００２０】
本発明により、一般の楕円曲線に適用可能であり、入力に応じて処理性能に大きなばらつきがないような楕円曲線上の点の生成が可能となる。これにより、一般の楕円曲線に値を持つハッシュ値の生成も可能となる。
【図面の簡単な説明】
【００２１】
【図１】第一の実施形態、及び第二の実施形態である点生成装置の機能構成の概略を例示する図。
【図２】コンピュータのハードウェア構成の概略図。
【図３】点生成装置における楕円曲線上の点生成処理を示すシーケンスを例示する図。
【図４】第一の実施形態における処理部での点生成処理を例示するフローチャート。
【図５】第二の実施形態における処理部での点生成処理を例示するフローチャート。
【発明を実施するための形態】
【００２２】
本発明の実施の形態を図面を用いて説明する。
【実施例１】
【００２３】
図１は、本発明の第一の実施形態である点生成装置１００の機能構成の概略図である。
【００２４】
図示するように、点生成装置１００は、記憶部１１１と、処理部１２０と、入力部１３１と、出力部１３２と、通信部１３３と、を備える。
【００２５】
本実施形態では、点生成装置で集合ＧＦ（ｑ）＊／｛１，−１｝∪｛０｝の元ｔと集合｛１，−１｝の元ιに対する上記有限体ＧＦ（ｑ）上定義された楕円曲線Ｅ（ＧＦ（ｑ）)上の点の生成を行う。ここでｑ＝ｐｒは素数ｐのべきである。
【００２６】
記憶部１１１は、有理関数記憶領域１１２と、基底記憶領域１１３と、パラメータ記憶部１１４と、を備える。
【００２７】
有理関数記憶領域１１２は、上記有限体ＧＦ（ｑ）から有限体ＧＦ（ｑ）上定義された２次曲線Ｃへの２つの有理関数に関する情報、及び上記２つの有理関数に付随する情報が格納される。ここで、上記有限体ＧＦ（ｑ）から有限体ＧＦ（ｑ）上定義された２次曲線Ｃへの２つの有理関数とは、上記有限体ＧＦ（ｑ）を係数にもつ１次または２次の多項式φ、ω、ψを用いてφ／ω、ψ／ωと表わされる関数であり、上記有限体ＧＦ（ｑ）から有限体ＧＦ（ｑ）上定義された２次曲線Ｃへの２つの有理関数に関する情報とは、例えば、上記φ、ω、ψの各係数である。また、上記有理関数φ／ω、ψ／ωの極（すなわち、ω（ｚ０）＝０）となる上記有限体ＧＦ（ｑ）の元ｚ０、及び上記多項式ψの零点（すなわち、ψ（ｚ１）＝０）となる上記有限体ＧＦ（ｑ）の元ｚ１である。なお、上記多項式ω、ψの零点となる上記各零点ｚ０、ｚ１を上記２つの有理関数に付随する情報を格納する理由については後述する。
【００２８】
基底記憶領域１１３には、上記有限体ＧＦ（ｑ）の２次拡大ＧＦ（ｑ２）の基底に関する情報が格納される。例えば、本実施形態においては、ξ∈ＧＦ（ｑ２）−ＧＦ（ｑ）、ｃ＝ξ２∈ＧＦ（ｑ）なる元ξが上記有限体ＧＦ（ｑ）の２次拡大ＧＦ（ｑ２）の基底に関する情報である。また、上記元ｃ∈ＧＦ（ｑ）も上記基底に関する情報として格納しておいてもよい。ここで、ＧＦ（ｑ２）−ＧＦ（ｑ）は上記有限体ＧＦ（ｑ）の２次拡大ＧＦ（ｑ２）から上記有限体ＧＦ（ｑ）の元を除いた集合を表わす。上記ξ、及び上記有限体ＧＦ（ｑ）の乗算に関する単位元１は、上記２次拡大ＧＦ（ｑ２）の上記有限体ＧＦ（ｑ）上の基底である。
【００２９】
パラメータ記憶部は、上記有限体ＧＦ（ｑ）、及び上記有限体ＧＦ（ｑ）上定義された楕円曲線Ｅ（ＧＦ（ｑ）)に関する情報が格納される。例えば、本実施形態においては、上記素数ｑ、及び上記楕円曲線Ｅ（ＧＦ（ｑ）)の定義方程式（式１）の係数ａ、ｂである。
【００３０】
処理部１２０は、有理関数計算部１２１と、有限体演算計算部１２２と、を備える。
【００３１】
例えば、本実施形態では、処理部１２０は、集合ＧＦ（ｑ）＊／｛１，−１｝∪｛０｝の元ｔと集合｛１，−１｝の元ιに対する上記楕円曲線Ｅ（ＧＦ（ｑ）)上の点を生成する処理を制御する。ここで、上記集合ＧＦ（ｑ）＊／｛１，−１｝∪｛０｝とは、有限体の乗法群ＧＦ(p）＊の元ｇに対して、ｇ＋ｈ＝０、またはｇ−ｈ＝０なる同値関係によって上記有限体の乗法群ＧＦ（ｑ）＊を割った集合を表わし、具体的には、ｑ＝ｐの場合は、上記集合ＧＦ（ｐ）＊／｛１，−１｝＝｛１，２，・・・（ｐ−１）／２｝である。
ｑ＝ｐｒ（ｒ＞＝２）の場合、上記集合ＧＦ（ｑ）＊／｛１，−１｝は、例えば、有限体の乗法群ＧＦ（ｑ）＊の元ｕ＝ａｒ−１γｒ−１＋ａｒ−２γｒ−２＋．．．＋ａ１γ＋ａ０であって、ａｉ≠０なる最大のｉをｊとするとき、０＜＝ａｊ＜＝（ｑ−１）／２を満たす元ｕからなる集合である。
【００３２】
また、上記集合ＧＦ（ｑ）＊／｛±１｝の構成方法は、実現可能であればその方法は問わない。
上記集合ＧＦ（ｑ）＊／｛１，−１｝∪｛０｝の要素数は、（ｑ−１）／２＋１＝（ｑ＋１）／２である。上記素数べきｑのビット長｜ｑ｜＝ｍのとき、ｑ≦２ｍ−１だから、（ｑ＋１）／２のビット長｜（ｑ＋１）／２｜≦｜｛（２ｍ−１）＋１｝／２｜＝｜２ｍ／２｜＝２ｍ−１である。
【００３３】
例えば、本実施形態では、処理部１２０は、入力データである上記元ｔと上記元ιに対して、有理関数記憶領域１１２に格納されている上記有理関数φ／ω、ψ／ωと、基底記憶領域１１３に格納されているＧＦ（ｑ２）−ＧＦ（ｑ）の元ξを取得して、ｔとともに、有理関数計算部１２１に送信する。有理関数計算部１２１は、予め定められたアルゴリズムによる計算を行い、上記有限体ＧＦ（ｑ）の２つの元α、βを生成する。そして、有理関数計算部１２１は、上記α、β、ξ、及び、パラメータ記憶部１１４に格納されている上記ａ、ｂを有限体演算計算部１２２に送信する。
【００３４】
有限体演算計算部１２２は、予め定められたアルゴリズムによる計算を行い、上記楕円曲線Ｅ（ＧＦ（ｑ））上の点Ｑを生成する。有限体演算計算部１２２は、上記生成した上記楕円曲線Ｅ（ＧＦ（ｑ））上の点Ｐを処理部１２０に出力する。入力部１３１は、当該点生成装置１００の外部から、記憶媒体１４４や、通信媒体（当該当該点生成装置１００に接続されるネットワークまたは当該ネットワークを伝播するデジタル信号や搬送波）を介して、情報の入力を受け付ける。出力部１３２は、当該点生成装置１００の外部へ、記憶媒体１４４や通信媒体を介して、情報を出力する。通信部１３３は、記憶部１１１と、処理部１２０と、入力部１３１と、出力部１３２と、の間の情報の送受信を行う。
【００３５】
以上に記載した点生成装置１００は、例えば、図２（コンピュータ１４０の概略図）に示すような、ＣＰＵ１４１と、メモリ１４２と、ＨＤＤ等の外部記憶装置１４３と、ＣＤ−ＲＯＭやＤＶＤ−ＲＯＭ等の可搬性を有する記憶媒体１４４から情報を読み出す読取装置１４５と、キーボードやマウスなどの入力装置１４６と、ディスプレイなどの出力装置１４７と、通信ネットワークに接続するためのＮＩＣ（Network Interface Card）等の通信装置１４８と、を備えた一般的なコンピュータ１４０で実現できる。
【００３６】
例えば、記憶部１１１は、ＣＰＵ１４１がメモリ１４２又は外部記憶装置１４３を利用することにより実現可能であり、処理部１２０は、外部記憶装置１４３に記憶されている所定のプログラムをメモリ１４２にロードしてＣＰＵ１４１で実行することで実現可能であり、入力部１３１は、ＣＰＵ１４１が入力装置１４６を利用することで実現可能であり、出力部１３２は、ＣＰＵ１４１が出力装置１４７を利用することで実現可能であり、通信部１３３は、ＣＰＵ１４１が通信装置１４８を利用することで実現可能である。
【００３７】
この所定のプログラムは、読取装置１４５を介して記憶媒体１４４から、あるいは、通信装置１４８を介して通信媒体から、外部記憶装置１４３にダウンロードされ、それから、メモリ１４２上にロードされてＣＰＵ１４１により実行されるようにしてもよい。また、読取装置１４５を介して記憶媒体１４４から、あるいは、通信装置１４８を介して通信媒体から、メモリ１４２上に直接ロードされ、ＣＰＵ１４１により実行されるようにしてもよい。
【００３８】
図３は、点生成装置１００における点生成処理を示すシーケンス図である。
【００３９】
まず、点生成装置１００の処理部１２０は、入力部１３１を介して入力された又はデータ記憶領域１３１に記憶されている有限体の元ｔ∈ＧＦ（ｑ）を取得する（Ｓ１０）。
【００４０】
次に、処理部１２０は、記憶部１２３の有理関数記憶領域１１２に記憶されている２つの有理関数φ／ω、ψ／ωと、基底記憶領域１１３に記憶されているξ∈ＧＦ（ｑ２）−ＧＦ（ｑ）と、パラメータ記憶領域１１４に記憶されている上記素数べきｑ、及び上記楕円曲線Ｅ（ＧＦ（ｑ）)の定義方程式（式１）の係数ａ、ｂと、を読み出す（Ｓ１１）。
【００４１】
そして、処理部１２０は、読み出した２つの有理関数φ／ω、ψ／ω、ξ∈ＧＦ（ｑ２）−ＧＦ（ｑ）、素数べきｑ、楕円曲線Ｅ（ＧＦ（ｑ）)の定義方程式（式１）の係数ａ、ｂ及び有限体の元ｔ∈ＧＦ（ｑ）を有理関数計算部１２１に入力する（Ｓ１２）。
【００４２】
有理関数計算部１２１は、入力された２つの有理関数φ／ω、ψ／ωと、ξ∈ＧＦ（ｑ２）−ＧＦ(ｑ）と、素数べきｑと、楕円曲線Ｅ（ＧＦ（ｑ）)の定義方程式（式１）の係数ａ、ｂと、有限体の元ｔ∈ＧＦ（ｑ）とから、有限体ＧＦ（ｑ）の元α、βを計算する（Ｓ１３）。
【００４３】
そして、有理関数計算部１２１は、計算した有限体ＧＦ（ｑ）の元α、βと、ξ∈ＧＦ（ｑ２）−ＧＦ（ｑ）と、素数べきｑと、楕円曲線Ｅ（ＧＦ（ｑ）)の定義方程式（式１）の係数ａ、ｂを有限体演算計算部１２２に出力する（Ｓ１４）。
【００４４】
有限体演算計算部１２２は、受け取った有限体ＧＦ（ｑ）の元α、βと、ξ∈ＧＦ（ｑ２）−ＧＦ（ｑ）と、素数べきｑと、楕円曲線Ｅ（ＧＦ（ｑ）)の定義方程式（式１）の係数ａ、ｂとから、楕円曲線上の点Ｐを生成する（Ｓ１５）。
【００４５】
有限体演算計算部１２２は、計算した楕円曲線上の点Ｐを処理部１２０に出力する（Ｓ１６）。
【００４６】
なお、ステップＳ１１において２つの有理関数φ／ω、ψ／ω、ξ∈ＧＦ（ｑ２）−ＧＦ（ｑ）、素数べきｑ、楕円曲線Ｅ（ＧＦ(ｑ）)の定義方程式（式１）の係数ａ、ｂの取得タイミングについては、有理関数計算部１２１へ２つの有理関数φ／ω、ψ／ω、ξ∈ＧＦ（ｑ２）−ＧＦ（ｑ）、素数べきｑ、楕円曲線Ｅ（ＧＦ（ｑ）)の定義方程式（式１）の係数ａ、ｂを出力する前であればよく、例えば、有限体の元ｔ∈ＧＦ（ｑ）を取得する（Ｓ１０）前であってもよい。また、ステップＳ１３の計算では、楕円曲線Ｅ（ＧＦ（ｑ）)の定義方程式（式１）の係数ａ、ｂは使用しないため、ステップＳ１１で読み出す必要はなく、ステップＳ１４の前であればよい。
【００４７】
楕円曲線Ｅ（ＧＦ（ｑ）)上の点Ｐを取得した処理部１２０は、記憶部１１１に記憶するか、または、出力部１３２や通信部１３３を介して、楕円曲線Ｅ（ＧＦ（ｑ）)上の点Ｐを出力する（Ｓ１７）。
【００４８】
図４は、有理関数計算部１２１と、有限体演算計算部１２２での楕円曲線Ｅ（ＧＦ（ｑ）)上の点Ｐの生成処理を示すフローチャートである。
【００４９】
ここで、本実施形態では、Ｅを、ａ、ｂが定義方程式（式１）の係数である有限体ＧＦ（ｑ）上定義された楕円曲線、φ、ψ、ωを、有限体ＧＦ（ｑ）を係数にもつ１次または２次の多項式とする。
【００５０】
以下、集合ＧＦ（ｑ）＊／｛１，−１｝∪｛０｝の元ｔと集合｛１，−１｝の元ιから上記楕円曲線Ｅ（ＧＦ（ｑ）)上の点Ｐを生成する方法を具体的に説明する。
【００５１】
有理関数計算部１２１と、有限体演算計算部１２２での楕円曲線上の点の生成処理は、集合ＧＦ（ｑ）＊／｛１，−１｝∪｛０｝の元ｔと集合｛１，−１｝の元ιを処理部１２０より受けることで開始される（Ｓ２０）。
【００５２】
処理部１２０より上記集合ＧＦ（ｑ）＊／｛１，−１｝∪｛０｝の元ｔと上記集合｛１，−１｝の元ιを受け取ると、有理関数計算部１２１は、入力された上記元ｔ∈ＧＦ（ｑ）＊／｛１，−１｝∪｛０｝からα＝φ（ｔ）／ω（ｔ）を計算する（Ｓ２１）。
【００５３】
そして、有限体演算計算部１２２は、有理関数計算部１２１より送信された上記α、上記楕円曲線ａ、ｂ、及び、上記素数べきｑを用いてτ＝−８α３−２ａα＋ｂを計算する（Ｓ２２）。
【００５４】
そして、有限体演算計算部１２２は、χｑ（τ）＝１であるかどうかを判定する（Ｓ２３）。そして、χｑ（τ）＝１である場合には（ステップＳ２３においてＹｅｓ）、ステップＳ２４に進み、χｑ（τ）＝１ではない場合には（ステップＳ２３においてＮｏ）、ステップＳ２５に進む。ここで、χｑは、ｓ∈（ＧＦ（ｑ）＊）２ならばχｑ（ｓ）＝１、ｓ∈（ＧＦ（ｑ）＊）２でないならばχｑ（ｓ）＝−１と定義される上記有限体の乗法群ＧＦ(ｑ）＊から集合｛１，−１｝への写像であり、２次指標と呼ばれている（さらにχｑ（０）＝０とし、χｑをＧＦ（ｑ）から｛０，１，−１｝への写像と拡張することもある。以下、上記χｑも上述のとおりに定義されるＧＦ（ｑ）から｛０，１，−１｝への写像とする）。
【００５５】
ステップＳ２４では、有限体演算計算部１２２は、τから√τを計算し、ｙに代入する（Ｓ２４）。
【００５６】
ステップＳ２５では、有限体演算計算部１２２は、τから√τ／ξ２を計算し、ｚに代入し、ｚω（ｔ）／ψ（ｔ）を計算してｗに代入する（Ｓ２５）。
【００５７】
ステップＳ２６では、有限体演算計算部１２２は、（−２α，ιｙ）をＰに代入し、上記Ｐを上記楕円曲線の点として出力する（Ｓ２６）。
【００５８】
ステップＳ２７では、有限体演算計算部１２２は、（ｗ２−２α，ι（ｗ２−３α）ｗ）をＰに代入し、上記Ｐを上記楕円曲線の点として出力する（Ｓ２７）。
【００５９】
なお、ステップＳ２４、及びステップＳ２５で実行する有限体における平方根計算については、例えば、H. Cohen， “A Course in Computational Algebraic Number Theory”， Springer-Verlag， GTM 138， 1993. に詳細に記載されている。
【００６０】
なお、ステップＳ２６、及びステップＳ２７で出力される上記Ｐが上記楕円曲線Ｅ（ＧＦ（ｑ））上の点であることは、上記楕円曲線Ｅ（ＧＦ（ｑ））の定義方程式（式１）にＰを代入することによって容易に確認することができる。
【００６１】
また、本実施形態では、上記集合ＧＦ（ｑ）＊／｛１，−１｝∪｛０｝の元ｔと集合｛１，−１｝の元ιに対して上記楕円曲線Ｅ（ＧＦ（ｑ））上の点ＰをＷｅｉｅｒｓｔｒａｓｓ型楕円曲線のアフィン座標で生成する方法を説明したが、Ｗｅｉｅｒｓｔｒａｓｓ型楕円曲線の射影座標、Ｗｅｉｅｒｓｔｒａｓｓ型楕円曲線のＪａｃｏｂｉａｎ座標などＷｅｉｅｒｓｔｒａｓｓ型楕円曲線のアフィン座標と異なる座標系で生成したり、Ｈｅｓｓｉａｎ型楕円曲線、Ｍｏｎｔｇｏｍｅｒｙ型楕円曲線、Ｅｄｗａｒｄｓ型楕円曲線上の点を生成することも可能である。この理由を、Ｗｅｉｅｒｓｔｒａｓｓ型楕円曲線のＪａｃｏｂｉａｎ座標の場合で説明する。
上記Ｗｅｉｅｒｓｔｒａｓｓ型楕円曲線のアフィン座標（Ｘ／Ｚ２，Ｙ／Ｚ３）とＷｅｉｅｒｓｔｒａｓｓ型楕円曲線のＪａｃｏｂｉａｎ座標（Ｘ：Ｙ：Ｚ）（Ｚ≠０）は対応している。このとき、本実施形態において、上記集合ＧＦ（ｑ）＊／｛１，−１｝∪｛０｝の元ｔと集合｛１，−１｝の元ιに対して、ステップＳ２６で出力される上記Ｗｅｉｅｒｓｔｒａｓｓ型楕円曲線のアフィン座標の点（−２α，ιｙ）に対応する上記Ｗｅｉｅｒｓｔｒａｓｓ型楕円曲線のＪａｃｏｂｉａｎ座標の点は（−２αω（ｔ）：ιｙω（ｔ）：ω（ｔ））、及び、ステップＳ２７で出力されるＷｅｉｅｒｓｔｒａｓｓ型楕円曲線のアフィン座標の点（ｗ２−２α，ι（ｗ２−３α）ｗ）に対応する上記Ｗｅｉｅｒｓｔｒａｓｓ型楕円曲線のＪａｃｏｂｉａｎ座標の点は（ξ２（τ−２ξ２αβ２ω（ｔ））：ιξ２（τ−３ξ２αβ２ω（ｔ））×√（ξ２τ）：ξ２βω（ｔ））であることが容易にわかるからである。ここで、τ＝−８α３ω（ｔ）−２ａαω（ｔ）３＋ｂω（ｔ）４である。したがって、上記集合ＧＦ（ｑ）＊／｛１，−１｝∪｛０｝の元ｔと集合｛１，−１｝の元ιに対して、Ｗｅｉｅｒｓｔｒａｓｓ型楕円曲線のＪａｃｏｂｉａｎ座標の点を生成するには、上記ステップＳ２１から上記ステップＳ２７の上記各ステップ（及び、図４の上記ステップＳ２１から上記ステップＳ２７の上記各ステップ）を以下のように変更すればよい：
α＝φ（ｔ）、γ＝ω（ｔ）を計算する（Ｓ２１）。
【００６２】
τ＝−８α３γ−２ａαγ３＋ｂγ４を計算する（Ｓ２２）。
【００６３】
χｑ（τ）＝１であるかどうかを判定する（Ｓ２３）。χｑ（τ）＝１である場合には（ステップＳ２３においてＹｅｓ）、ステップＳ２４に進み、χｑ（τ）＝１ではない場合には（ステップＳ２３においてＮｏ）、ステップＳ２５に進む。
【００６４】
√τを計算し、ｙに代入する（Ｓ２４）。
【００６５】
√（τξ２）を計算し、ｚに代入する（Ｓ２５）。
【００６６】
Ｐ＝（−２αγ：ιｙγ：γ）とし、上記Ｐを上記楕円曲線の点として出力する（Ｓ２６）。
【００６７】
Ｐ＝（ξ２（τ−２ξ２αβ２γ）：ιξ２（τ−３ξ２αβ２γ）×√（ξ２τ）：ξ２βγ）とし、上記Ｐを上記楕円曲線の点として出力する（Ｓ２７）。
【００６８】
また、上記多項式ω、ψの零点となる上記各零点ｚ０、ｚ１を上記２つの有理関数に付随する情報を格納する理由は以下の通りである。上記ステップＳ２１において、α＝φ（ｔ）／ω（ｔ）を計算する。ｔ＝ｚ０ならばω（ｚ０）＝０となるので、αを計算することができない（有理関数φ／ωはｔ＝ｚ０で定義されない）からである。さらに、上記ステップＳ２５において、ｗ＝ｚω（ｔ）／ψ（ｔ）を計算する。ｔ＝ｚ１ならばψ（ｚ１）＝０となるので、ｗを計算することができない（有理関数ｚω／ψはｔ＝ｚ１で定義されない）からである。
【００６９】
そのため、上記ｚ０，ｚ１に対応する楕円曲線Ｅ（ＧＦ（ｑ））上の点Ｐ０，Ｐ１を予め定めておき、ステップＳ２０でｔ＝ｚ０またはｔ＝ｚ１が入力された場合は上記予め定められた点Ｐ０，Ｐ１を出力してもよいし、ｔ＝ｚ０またはｔ＝ｚ１が入力された場合、ｔ＝ｔ＋１とし、ｔ≠ｚ０かつｔ≠ｚ１となるまでｔ＝ｔ＋１を繰り返してもよいし、上記集合ＧＦ（ｑ）＊／｛１，−１｝∪｛０｝からω（ｔ）＝０なる元ｔ∈ＧＦ（ｑ）＊／｛１，−１｝∪｛０｝、及びψ（ｔ）＝０なる元ｔ∈ＧＦ（ｑ）＊／｛１，−１｝∪｛０｝を予め除いておいてもよい。
【００７０】
ω（ｚ０）＝０なる元ｚ０∈ＧＦ（ｑ）＊／｛１，−１｝∪｛０｝の個数、及びψ（ｚ１）＝０なる元ｚ１∈ＧＦ（ｑ）＊／｛１，−１｝∪｛０｝の個数はそれぞれ高々２個であるから、上記ｔ＝ｔ＋１なる繰り返し回数は高々４回であり、上記ｔ＝ｔ＋１なる繰り返しの処理時間は、上記ステップＳ２４、または上記ステップＳ２５の平方根計算の処理時間と比べると非常に小さいので、上記ステップＳ２０の入力によって、上記点の生成処理時間は大きくばらつくことはない。
【００７１】
上記有理関数φ／ω、ψ／ωは、例えば以下に示す方法で決定することができる。一般に、有限体ＧＦ（ｑ）上定義された上記２次曲線Ｃ上の点（α０，β０）を一つ決め、固定する。上記２次曲線Ｃの上記点（α０，β０）以外の任意の点（α，β）に対し、上記点（α０，β０）と上記点（α，β）を結んだ直線とｘ軸（または、ｙ軸）との交点をｔとすることにより、上記２次曲線Ｃから上記点（α０，β０）を除いた集合から上記有限体ＧＦ(ｑ）への写像が構成できる。この逆写像（ｔ→（φ／ω）（ｔ），（ψ／ω）（ｔ））を上記有理関数とすればよい。
【００７２】
また、本実施形態を用いることによって、楕円曲線上に値を持つハッシュ関数を容易に構成することができる理由は以下の通りである。例えば、非特許文献２に記載の署名では、任意長のビット列｛０，１｝＊から楕円曲線Ｅ（ＧＦ（ｑ））へのハッシュ関数Ｈ：｛０，１｝＊→Ｅ（ＧＦ（ｑ））を使用する。ｈを任意長のビット列｛０，１｝＊から固定長のビット列｛０，１｝ｍへの暗号学的ハッシュ関数（例えば、ＳＨＡ−２５６など）とし、上記素数べきｑのビット長｜ｑ｜＝ｍとする。任意長のビット列Ｍ∈｛０，１｝＊に対し、上記Ｍのハッシュ値ｈ（Ｍ）を計算し、上位ｍ−１ビットをｔ、最下位１ビットをιとする。すなわち、Ｍ＝ｔ｜｜ιである。ここで、｜｜は２つのビット列の結合を表す。
【００７３】
上記ｔを予め定められた方法でＧＦ（ｑ）の元と見なし（例えば、ビット列ｔ＝ｔｍ−２ｔｍ−１．．．ｔ０に対し、ｔ＝ｔｍ−２２ｍ−２＋ｔｍ−１２ｍ−１＋．．．＋ｔ０とする）、上記ｔ∈ＧＦ（ｑ）＊／｛１，−１｝∪｛０｝と上記ι∈｛１，−１｝に対して本実施形態に記載の点生成方法で生成した点Ｐを上記ビット列Ｍに対するハッシュ値とすることにより、特許文献２に記載の署名に記載されている任意長のビット列｛０，１｝＊から楕円曲線Ｅ（ＧＦ（ｑ））へのハッシュ関数Ｈ：｛０，１｝＊→Ｅ（ＧＦ（ｑ））が構成できる。
【００７４】
また、任意長のビット列｛０，１｝＊から｛ＧＦ（ｑ）＊／｛１，−１｝∪｛０｝)×｛１，−１｝へのハッシュ関数の構成方法は、実現可能であればその方法は問わない。さらに、楕円曲線上に値を持つその他のハッシュ関数（例えば、非特許文献１など）も上記ハッシュ関数Ｈと類似の方法で実現可能である。
【００７５】
以上の通り、本実施形態の楕円曲線上の点生成は、一般の楕円曲線に適用可能であり、入力に応じて処理性能に大きなばらつきがないような楕円曲線上の点の生成が可能になる。
【実施例２】
【００７６】
次に、第二の実施形態である楕円曲線上の点の生成方法について説明する。
【００７７】
第一の実施形態に記載の楕円曲線上の点の生成方法をΦとし、写像
ｆ１、ｆ２、ｆ３を、
ｆ１：ＧＦ（ｑ）＊／｛１，−１｝∪｛０｝→Ｃ（ＧＦ（ｑ）），
ｔ→ｆ１（ｔ）＝（α＝φ（ｔ）／ω（ｔ），β＝ψ（ｔ）／ω（ｔ））
（式２）
ｆ２：Ｃ（ＧＦ（ｑ））→Ｅ（１）（ＧＦ（ｑ２）／ＧＦ（ｑ）），
（α，β）→Ｑ＝（α＋βξ，√Ｆ（α＋βξ）） （式３）
ｆ３：Ｅ（１）（ＧＦ（ｑ２）／ＧＦ（ｑ））→Ｅ（ＧＦ（ｑ）），
Ｑ＝（α＋βξ，√Ｆ（α＋βξ））→Ｑ＋σ（Ｑ） （式４）
とする。ここで、（式２）のφ、ψ、ωは上記有限体ＧＦ（ｑ）を係数にもつ１次または２次の多項式であり、（式３）のＦ（α＋βξ）は（式１）の定義方程式の右辺Ｆ（ｘ）＝ｘ３＋ａｘ＋ｂよりＦ（α＋βξ）＝（α＋βξ）３＋ａ（α＋βξ）＋ｂである。上記楕円曲線Ｅ上の点Ｐ１，Ｐ２に対して、Ｐ１＝Ｐ２またはＰ１＝−Ｐ２のとき、Ｐ１〜Ｐ２なる同値関係を定義する。Ｅ（１）（ＧＦ（ｑ２）／ＧＦ（ｑ））、Ｅ（ＧＦ（ｑ））はそれぞれ集合｛（ｘ，ｙ）∈Ｅ（ＧＦ（ｑ２））｜ｘ∈ＧＦ（ｑ２）−ＧＦ（ｑ），ｙ２∈ＧＦ（ｑ）｝、集合Ｅ（（ＧＦ（ｑ））を同値関係〜で割った集合である。σはｑ乗Ｆｒｏｂｅｎｉｕｓ写像である。このとき、上記集合ＧＦ（ｑ）＊／｛１，−１｝∪｛０｝の元ｔ、及び上記集合｛１，−１｝の元ιから第一の実施形態に記載の方法で生成した点ＰはＰ＝ｆ３（ｆ２（ｆ１（ｔ，ι）））に他ならない。
【００７８】
第二の実施形態は、第一の実施形態における上記有限体ＧＦ（ｑ）を２次拡大体ＧＦ（ｑ２）、上記有限体ＧＦ（ｑ）の乗法群ＧＦ(ｑ）＊を２次拡大体ＧＦ（ｑ２）の乗法群ＧＦ（ｑ２）＊、２次拡大体ＧＦ(ｑ２）を２次拡大体ＧＦ(ｑ２）の２次拡大（上記有限体ＧＦ（ｑ）の４次拡大）ＧＦ（ｑ４）、として第一の実施形態に記載の方法で楕円曲線ＥのＧＦ（ｑ２）有理点を生成し、さらに上記楕円曲線Ｅ（ＧＦ（ｑ２））上の点から（式9）を用いて上記楕円曲線Ｅ（ＧＦ（ｑ））上の点を生成する方法である。
【００７９】
ここで、本実施形態における点生成装置も、第一の実施形態と同様に、記憶部１１１と、処理部１２０と、入力部１３１と、出力部１３２と、通信部１３３と、を備える。
【００８０】
本実施形態では、点生成装置で集合ＧＦ（ｑ２）＊／｛１，−１｝∪｛０｝の元ｔと集合｛１，−１｝の元ιに対する上記有限体ＧＦ（ｑ）上定義された楕円曲線Ｅ（ＧＦ（ｑ）)上の点の生成を行う。
【００８１】
記憶部１１１の機能構成は第一の実施形態と同様である。
【００８２】
有理関数記憶領域１１２は、上記有限体ＧＦ（ｑ２）から有限体ＧＦ（ｑ２）上定義された２次曲線Ｃへの２つの有理関数に関する情報、及び上記２つの有理関数に付随する情報が格納される。ここで、上記有限体ＧＦ（ｑ２）から有限体ＧＦ（ｑ２）上定義された２次曲線Ｃへの２つの有理関数とは、上記有限体ＧＦ（ｑ２）を係数にもつ１次または２次の多項式φ、ω、ψを用いてφ／ω、ψ／ωと表わされる関数であり、上記有限体ＧＦ（ｑ２）から有限体ＧＦ（ｑ２）上定義された２次曲線Ｃへの２つの有理関数に関する情報とは、例えば、上記φ、ω、ψの各係数である。また、上記有理関数φ／ω、ψ／ωの極（すなわち、ω（ｚ０）＝０）となる上記有限体ＧＦ（ｑ２）の元ｚ０、及び上記多項式ψの零点（すなわち、ψ（ｚ１）＝０）となる上記有限体ＧＦ（ｑ２）の元ｚ１である。なお、上記多項式ω、ψの零点となる上記各零点ｚ０、ｚ１を上記２つの有理関数に付随する情報を格納する理由については後述する。
【００８３】
基底記憶領域１１３には、上記有限体ＧＦ（ｑ２）の２次拡大ＧＦ（ｑ４）の基底に関する情報が格納される。例えば、本実施形態においては、ξ∈ＧＦ（ｑ４）−ＧＦ（ｑ２）、ｃ＝ξ２∈ＧＦ（ｑ２）なる元ξが上記有限体ＧＦ（ｑ２）の２次拡大ＧＦ（ｑ４）の基底に関する情報である。また、上記元ｃ∈ＧＦ（ｑ２）も上記基底に関する情報として格納しておいてもよい。ここで、ＧＦ（ｑ４）−ＧＦ（ｑ２）は上記有限体ＧＦ（ｑ２）の２次拡大ＧＦ（ｑ４）から上記有限体ＧＦ（ｑ２）の元を除いた集合を表わす。上記ξ、及び上記有限体ＧＦ（ｑ２）の乗算に関する単位元１は、上記２次拡大ＧＦ（ｑ４）の上記有限体ＧＦ（ｑ２）上の基底である。
【００８４】
パラメータ記憶部は、有限体ＧＦ（ｑ）、及び上記有限体ＧＦ（ｑ）上定義された楕円曲線Ｅ（ＧＦ（ｑ）)に関する情報が格納される。例えば、本実施形態においては、上記素数べきｑ、及び上記楕円曲線Ｅ（ＧＦ（ｑ）)の定義方程式（式１）の係数ａ、ｂである。
【００８５】
処理部１２０の機能構成も第一の実施形態と同様である。
【００８６】
例えば、本実施形態では、処理部１２０は、集合ＧＦ（ｑ２）＊／｛１，−１｝∪｛０｝の元ｔと集合｛１，−１｝の元ιに対する上記楕円曲線Ｅ（ＧＦ（ｑ）)上の点を生成する処理を制御する。ここで、上記集合ＧＦ（ｑ２）＊／｛１，−１｝∪｛０｝とは、有限体の乗法群ＧＦ（ｑ２）＊の元ｇに対して、ｇ＋ｈ＝０、またはｇ−ｈ＝０なる同値関係によって上記有限体の乗法群ＧＦ（ｑ２）＊を割った集合を表わす。
【００８７】
例えば、本実施形態では、処理部１２０は、入力データである上記元ｔと上記元ιに対して、有理関数記憶領域１１２に格納されている上記有理関数φ／ω、ψ／ωと、基底記憶領域１１３に格納されているＧＦ（ｑ４）−ＧＦ（ｑ２）の元ξを取得して、ｔとともに、有理関数計算部１２１に送信する。有理関数計算部１２１は、予め定められたアルゴリズムによる計算を行い、上記有限体ＧＦ（ｑ２）の２つの元α、βを生成する。そして、有理関数計算部１２１は、上記α、β、ξ、及び、パラメータ記憶部１１４に格納されている上記ａ、ｂを有限体演算計算部１２２に送信する。
【００８８】
有限体演算計算部１２２は、予め定められたアルゴリズムによる計算を行い、上記楕円曲線Ｅ（ＧＦ（ｑ）)上の点Ｐを生成する。有限体演算計算部１２２は、上記生成した上記楕円曲線Ｅ（ＧＦ（ｑ）)上の点Ｐを処理部１２０に出力する。入力部１３１は、情報の入力を受け付ける。出力部１３２は、情報を出力する。通信部１３３は、記憶部１１１と、処理部１２０と、入力部１３１と、出力部１３２と、の間の情報の送受信を行う。
【００８９】
以上に記載した点生成装置１００も、第一の実施形態と同様、例えば、図２（コンピュータ１４０の概略図）に示すような、ＣＰＵ１４１と、メモリ１４２と、ＨＤＤ等の外部記憶装置１４３と、ＣＤ−ＲＯＭやＤＶＤ−ＲＯＭ等の可搬性を有する記憶媒体１４４から情報を読み出す読取装置１４５と、キーボードやマウスなどの入力装置１４６と、ディスプレイなどの出力装置１４７と、通信ネットワークに接続するためのＮＩＣ（Network Interface Card）等の通信装置１４８と、を備えた一般的なコンピュータ１４０で実現できる。処理部１２０が、外部記憶装置１４３に記憶されている所定のプログラムをメモリ１４２にロードしてＣＰＵ１４１で実行することで実現可能であることも、第一の実施形態と同様である。
【００９０】
本実施形態の点生成装置１００における点生成処理を示すシーケンス図も第一の実施形態（図３）と同様である。ただし、ステップＳ１０のｔは、ＧＦ（ｑ２）＊／｛１，−１｝∪｛０｝の元、ステップＳ１１、及びステップＳ１２のφ、ω、ψは上記有限体ＧＦ（ｑ２）を係数にもつ１次または２次の多項式、ステップＳ１１、及びステップ１４のξはＧＦ（ｑ４）のＧＦ（ｑ２）上の上記基底、ステップＳ１３、及びステップＳ１４のα、βは上記有限体ＧＦ（ｑ２）の元、である。
【００９１】
図５は、有理関数計算部１２１と、有限体演算計算部１２２での楕円曲線Ｅ（ＧＦ（ｑ）)上の点Ｐの生成処理を示すフローチャートである。
【００９２】
ここで、本実施形態では、Ｅを、ａ、ｂが定義方程式（式１）の係数である有限体ＧＦ(ｑ）上定義された楕円曲線、φ、ψ、ωを、上記有限体ＧＦ（ｑ２）を係数にもつ１次または２次の多項式とする。
【００９３】
以下、集合ＧＦ（ｑ２）＊／｛１，−１｝∪｛０｝の元ｔと集合｛１，−１｝の元ιから上記楕円曲線Ｅ（ＧＦ（ｑ）)上の点Ｐを生成する方法を具体的に説明する。
【００９４】
有理関数計算部１２１と、有限体演算計算部１２２での楕円曲線上の点の生成処理は、集合ＧＦ（ｑ２）＊／｛１，−１｝∪｛０｝の元ｔと集合｛１，−１｝の元ιを処理部１２０より受けることで開始される（Ｓ３０）。
【００９５】
処理部１２０より上記集合ＧＦ（ｑ２）＊／｛１，−１｝∪｛０｝の元ｔと上記集合｛１，−１｝の元ιを受け取ると、有理関数計算部１２１は、入力された上記元ｔ∈ＧＦ（ｑ２）＊／｛１，−１｝∪｛０｝からα＝φ（ｔ）／ω（ｔ）を計算する（Ｓ３１）。
【００９６】
そして、有限体演算計算部１２２は、有理関数計算部１２１より送信された上記α、上記楕円曲線ａ、ｂ、及び、上記素数べきｑを用いてτ＝−８α３−２ａα＋ｂを計算する（Ｓ３２）。
【００９７】
そして、有限体演算計算部１２２は、χｑ２（τ）＝１であるかどうかを判定する（Ｓ３３）。そして、χｑ２（τ）＝１である場合には（ステップＳ３３においてＹｅｓ）、ステップＳ３４に進み、χｑ２（τ）＝１ではない場合には（ステップＳ３３においてＮｏ）、ステップＳ３５に進む。ここで、χｑ２は、ｓ∈（ＧＦ（ｑ２）＊）２ならばχｑ２（ｓ）＝１、ｓ∈（ＧＦ（ｑ２）＊）２でないならばχｑ２（ｓ）＝−１と定義される上記有限体の乗法群ＧＦ（ｑ２）＊から集合｛１，−１｝への写像である（さらにχｑ２（０）＝０とし、χｑ２をＧＦ（ｑ２）から｛０，１，−１｝への写像と拡張することもある。以下、上記χｑ２も上述のとおりに定義されるＧＦ(ｑ）から｛０，１，−１｝への写像とする）。
【００９８】
ステップＳ３４では、有限体演算計算部１２２は、τから√τを計算し、ｙに代入する（Ｓ３４）。
【００９９】
ステップＳ３５では、有限体演算計算部１２２は、τから√τ／ξ２を計算し、ｚに代入し、ｚω（ｔ）／ψ（ｔ）を計算してｗに代入する（Ｓ３５）。
【０１００】
ステップＳ３６では、有限体演算計算部１２２は、（−２α，ιｙ）をＱに代入する（Ｓ３６）。
【０１０１】
ステップＳ３７では、有限体演算計算部１２２は、（ｗ２−２α，ι（ｗ２−３α）ｗ）をＱに代入する（Ｓ３７）。
【０１０２】
ステップＳ３８では、Ｑ＋σ（Ｑ）をＰに代入し、上記Ｐを上記楕円曲線の点として出力する（Ｓ３７）。ここで、σはｑ乗Ｆｒｏｂｅｎｉｕｓ写像である。
なお、ステップＳ３４、ステップＳ３５、及びステップＳ３７（Ｑ＋σ（Ｑ）の計算）で実行する有限体における平方根計算については、例えば、H. Cohen， “A Course in Computational Algebraic Number Theory”， Springer-Verlag， GTM 138， 1993. に詳細に記載されている。
【０１０３】
なお、ステップＳ３７で出力される上記Ｐが上記楕円曲線Ｅ（ＧＦ（ｑ））上の点であることも、第一の実施形態と同様、上記楕円曲線Ｅ（ＧＦ（ｑ））の定義方程式（式１）にＰを代入することによって容易に確認することができる。
【０１０４】
また、本実施形態では、上記集合ＧＦ（ｑ）＊／｛１，−１｝∪｛０｝の元ｔと集合｛１，−１｝の元ιに対して上記楕円曲線Ｅ（ＧＦ（ｑ））上の点ＰをＷｅｉｅｒｓｔｒａｓｓ型楕円曲線のアフィン座標で生成する方法を説明したが、Ｗｅｉｅｒｓｔｒａｓｓ型楕円曲線の射影座標、Ｗｅｉｅｒｓｔｒａｓｓ型楕円曲線のＪａｃｏｂｉａｎ座標などＷｅｉｅｒｓｔｒａｓｓ型楕円曲線のアフィン座標と異なる座標系で生成したり、Ｈｅｓｓｉａｎ型楕円曲線、Ｍｏｎｔｇｏｍｅｒｙ型楕円曲線、Ｅｄｗａｒｄｓ型楕円曲線上の点を生成することも可能である。この理由も第一の実施形態と同様である。
【０１０５】
また、上記多項式ω、ψの零点となる上記各零点ｚ０、ｚ１を上記２つの有理関数に付随する情報を格納する理由、及び、上記集合ＧＦ（ｑ２）＊／｛１，−１｝∪｛０｝の元ｔがｚ０、またはｚ１と等しい場合における上記楕円曲線Ｅ（ＧＦ（ｑ））上の点Ｐの生成方法も第一の実施形態と同様である。
【０１０６】
上記有理関数φ／ω、ψ／ωの決定方法も第一の実施形態と同様である。
【０１０７】
また、本実施形態を用いることによって、楕円曲線上に値を持つハッシュ関数を容易に構成することができる理由は以下の通りである。例えば、非特許文献２に記載の署名では、上述の通り、任意長のビット列｛０，１｝＊から楕円曲線Ｅ（ＧＦ（ｑ））へのハッシュ関数Ｈ：｛０，１｝＊→Ｅ（ＧＦ（ｑ））を使用する。ｈを任意長のビット列｛０，１｝＊から固定長のビット列｛０，１｝２ｍへの暗号学的ハッシュ関数（例えば、ＳＨＡ−２５６など）とし、上記素数べきｑのビット長｜ｑ｜＝ｍとする。任意長のビット列Ｍ∈｛０，１｝＊に対し、上記Ｍのハッシュ値ｈ（Ｍ）を計算し、上位（ｍ−１）／２ビットをｔ１、次の（ｍ−１）／２ビットをｔ２、最下位２ビットをιとする。すなわち、Ｍ＝ｔ１｜｜ｔ２｜｜ιである。ここで、｜｜は２つのビット列の結合を表す。上記ｔ１、ｔ２を予め定められた方法でＧＦ（ｑ）の元と見なし（例えば、ビット列ｔ１＝ｔ１，ｍ−２ｔ１，ｍ−３．．．ｔ１，０、ｔ２＝ｔ２，ｍ−２ｔ２，ｍ−３．．．ｔ２，０、に対し、ｔ１＝ｔ１，ｍ−２２ｍ−２＋ｔ１，ｍ−３２ｍ−３＋．．．＋ｔ１，０、ｔ２＝ｔ２，ｍ−２２ｍ−２＋ｔ２，ｍ−３２ｍ−３＋．．．＋ｔ２，０とする）、さらに、ι＝ι１｜｜ι２、すなわち、ιの上位１ビットをι１、ιの下位１ビットをι２とする。上記ｔ＝ｔ１＋ｔ２ξ∈ＧＦ（ｑ２）＊／｛１，−１｝∪｛０｝と上記ι１（または、ι２）∈｛１，−１｝に対して本実施形態に記載の点生成方法で生成した点Ｐを上記ビット列Ｍに対するハッシュ値とすることにより、特許文献２に記載の署名に記載されている任意長のビット列｛０，１｝＊から楕円曲線Ｅ（ＧＦ（ｑ））へのハッシュ関数Ｈ：｛０，１｝＊→Ｅ（ＧＦ（ｑ））が構成できる。また、任意長のビット列｛０，１｝＊から｛ＧＦ（ｑ２）＊／｛１，−１｝∪｛０｝)×｛１，−１｝へのハッシュ関数の構成方法は、実現可能であればその方法は問わない。さらに、楕円曲線上に値を持つその他のハッシュ関数（例えば、非特許文献１など）も上記ハッシュ関数Ｈと類似の方法で実現可能である。
【０１０８】
以上の通り、本実施形態の楕円曲線上の点生成は、一般の楕円曲線に適用可能であり、入力に応じて処理性能に大きなばらつきがないような楕円曲線上の点の生成が可能になる。
【符号の説明】
【０１０９】
１００：点生成装置、１１１：記憶部、１１２：有理関数記憶領域、１１３：基底記憶領域、１１４：パラメータ記憶領域、１２０：処理部、１２１：有理関数計算部、１２２：有限体演算計算部、１３１：入力部、１３２：出力部、１３３：通信部。
【特許請求の範囲】
【請求項１】
要素数が（ｑ＋１）／２（ｑは５以上の素数べき）の集合Ｓの元と要素数が２の集合Ｔの元から有限体ＧＦ（ｑ）上定義された楕円曲線ＥのＧＦ（ｑ）有理点を生成する点生成方法であって、
前記集合Ｓの元から予め定められた前記有限体ＧＦ（ｑ）上定義された二次曲線ＣのＧＦ（ｑ）有理点を生成する第一のステップと、
前記第一のステップで生成した前記二次曲線Ｃの前記ＧＦ（ｑ）有理点から前記楕円曲線ＥのＧＦ（ｑ２）有理点を生成する第二のステップと、
前記第二のステップで生成した前記楕円曲線ＥのＧＦ（ｑ２）有理点と前記集合Ｔの元から前記楕円曲線ＥのＧＦ（ｑ）有理点を生成する第三のステップと、
を備えることを特徴とする楕円曲線上の点生成方法。
【請求項２】
請求項１に記載の楕円曲線上の点生成方法であって、
前記集合Ｓは集合ＧＦ（ｑ）＊／｛１，−１｝∪｛０｝、前記集合Ｔは｛１，−１｝であり、
前記第一のステップは、前記集合Ｓの元ｔから予め定められた２つのＧＦ（ｑ）上の有理関数α、βに対して、α（ｔ）、β（ｔ）を計算し、前記二次曲線ＣのＧＦ（ｑ）有理点Ｒ＝（α、β）を生成し、
前記第二のステップは、予め定められた前記有限体ＧＦ（ｑ２）の前記有限体ＧＦ（ｑ）上の基底（ξ，１）、及び前記二次曲線ＣのＧＦ（ｑ）有理点（α、β）から前記楕円曲線ＥのＧＦ（ｑ２）有理点Ｐ＝（α＋βξ，√（Ｆ（α＋βξ）））（Ｆは前記楕円曲線ＥのＷｅｉｅｒｓｔｒａｓｓ型の定義方程式ｙ２＝ｘ３＋ａｘ＋ｂ＝Ｆ（ｘ）に対して、Ｆ（ｘ）＝ｘ３＋ａｘ＋ｂなる多項式）を生成し、
前記第三のステップは、前記楕円曲線ＥのＧＦ（ｑ２）有理点Ｐから前記楕円曲線ＥのＦｒｏｂｅｎｉｕｓ自己準同型写像σを用いて前記楕円曲線ＥのＧＦ（ｑ）有理点（Ｐ＋σ（Ｐ））を生成すること、
を特徴とする楕円曲線上の点生成方法。
【請求項３】
要素数が（ｑ２＋１）／２（ｑは５以上の素数べき）の集合Ｓの元と要素数が２の集合Ｔの元から有限体ＧＦ（ｑ）上定義された楕円曲線ＥのＧＦ（ｑ）有理点を生成する点生成方法であって、
前記集合Ｓの元から予め定められた前記有限体ＧＦ（ｑ２）上定義された二次曲線ＣのＧＦ（ｑ２）有理点を生成する第一のステップと、
前記第一のステップで生成した前記二次曲線Ｃの前記ＧＦ（ｑ２）有理点から前記楕円曲線ＥのＧＦ（ｑ４）有理点を生成する第二のステップと、
前記第二のステップで生成した前記楕円曲線ＥのＧＦ（ｑ４）有理点と前記集合Ｔの元から前記楕円曲線ＥのＧＦ（ｑ）有理点を生成する第三のステップと、
を備えることを特徴とする楕円曲線上の点生成方法。
【請求項４】
請求項３に記載の楕円曲線上の点生成方法であって、
前記集合Ｓは集合ＧＦ（ｑ２）＊／｛１，−１｝∪｛０｝、前記集合Ｔは｛１，−１｝であり、
前記第一のステップは、前記集合Ｓの元ｔから予め定められた２つのＧＦ（ｑ２）上の有理関数α、βに対して、α（ｔ）、β（ｔ）を計算し、前記二次曲線ＣのＧＦ（ｑ２）有理点Ｒ＝（α、β）を生成し、
前記第二のステップは、予め定められた前記有限体ＧＦ（ｑ４）の前記有限体ＧＦ（ｑ２）上の基底（ξ，１）、及び前記二次曲線ＣのＧＦ（ｑ２）有理点（α、β）に対して、前記楕円曲線ＥのＧＦ（ｑ２）有理点Ｐ＝（α＋βξ，√（Ｆ（α＋βξ）））（Ｆは前記楕円曲線ＥのＷｅｉｅｒｓｔｒａｓｓ型の定義方程式ｙ２＝ｘ３＋ａｘ＋ｂ＝Ｆ（ｘ）なる多項式）を生成し、
前記第三のステップは、前記楕円曲線ＥのＧＦ（ｑ４）有理点Ｐから、前期楕円曲線ＥのＦｒｏｂｅｎｉｕｓ自己準同型写像σを用いて前記楕円曲線ＥのＧＦ（ｑ）有理点Ｐ＋σ（Ｐ）＋σ２（Ｐ）＋σ３（Ｐ）を生成すること、
を特徴とする楕円曲線上の点生成方法。
【請求項５】
要素数が（ｑ＋１）／２（ｑは５以上の素数べき）の集合Ｓの元と要素数が２の集合Ｔの元から有限体ＧＦ（ｑ）上定義された楕円曲線ＥのＧＦ（ｑ）有理点を生成する点生成装置であって、
前記集合Ｓの元から予め定められた前記有限体ＧＦ（ｑ）上定義された二次曲線ＣのＧＦ（ｑ）有理点を生成する第一の手段と、
前記第一の手段で生成した前記二次曲線Ｃの前記ＧＦ（ｑ）有理点から前記楕円曲線ＥのＧＦ（ｑ２）有理点を生成する第二の手段と、
前記第二の手段で生成した前記楕円曲線ＥのＧＦ（ｑ２）有理点と前記集合Ｔの元から前記楕円曲線ＥのＧＦ（ｑ）有理点を生成する第三の手段と、
を備えることを特徴とする楕円曲線上の点生成装置。
【請求項６】
請求項５に記載の楕円曲線上の点生成装置であって、
前記集合Ｓは集合ＧＦ（ｑ）＊／｛１，−１｝∪｛０｝、前記集合Ｔは｛１，−１｝であり、
前記第一の手段は、前記集合Ｓの元ｔから予め定められた２つのＧＦ（ｑ）上の有理関数α、βに対して、α（ｔ）、β（ｔ）を計算し、前記二次曲線ＣのＧＦ（ｑ）有理点Ｒ＝（α、β）を生成し、
前記第二の手段は、予め定められた前記有限体ＧＦ（ｑ２）の前記有限体ＧＦ（ｑ）上の基底（ξ，１）、及び前記二次曲線ＣのＧＦ（ｑ）有理点（α、β）から前記楕円曲線ＥのＧＦ（ｑ２）有理点Ｐ＝（α＋βξ，√（Ｆ（α＋βξ）））（Ｆは前記楕円曲線ＥのＷｅｉｅｒｓｔｒａｓｓ型の定義方程式ｙ２＝ｘ３＋ａｘ＋ｂ＝Ｆ（ｘ）に対して、Ｆ（ｘ）＝ｘ３＋ａｘ＋ｂなる多項式）を生成し、
前記第三の手段は、前記楕円曲線ＥのＧＦ（ｑ２）有理点Ｐから前記楕円曲線ＥのＦｒｏｂｅｎｉｕｓ自己準同型写像σを用いて前記楕円曲線ＥのＧＦ（ｑ）有理点（Ｐ＋σ（Ｐ））を生成すること、
を特徴とする楕円曲線上の点生成装置。
【請求項７】
要素数が（ｑ２＋１）／２（ｑは５以上の素数べき）の集合Ｓの元と要素数が２の集合Ｔの元から有限体ＧＦ（ｑ）上定義された楕円曲線ＥのＧＦ（ｑ）有理点を生成する点生成装置であって、
前記集合Ｓの元から予め定められた前記有限体ＧＦ（ｑ２）上定義された二次曲線ＣのＧＦ（ｑ２）有理点を生成する第一の手段と、
前記第一の手段で生成した前記二次曲線Ｃの前記ＧＦ（ｑ２）有理点から前記楕円曲線ＥのＧＦ（ｑ４）有理点を生成する第二の手段と、
前記第二の手段で生成した前記楕円曲線ＥのＧＦ（ｑ４）有理点と前記集合Ｔの元から前記楕円曲線ＥのＧＦ（ｑ）有理点を生成する第三の手段と、
を備えることを特徴とする楕円曲線上の点生成装置。
【請求項８】
請求項７に記載の楕円曲線上の点生成装置であって、
前記集合Ｓは集合ＧＦ（ｑ２）＊／｛１，−１｝∪｛０｝、前記集合Ｔは｛１，−１｝であり、
前記第一の手段は、前記集合Ｓの元ｔから予め定められた２つのＧＦ（ｑ２）上の有理関数α、βに対して、α（ｔ）、β（ｔ）を計算し、前記二次曲線ＣのＧＦ（ｑ２）有理点Ｒ＝（α、β）を生成し、
前記第二の手段は、予め定められた前記有限体ＧＦ（ｑ４）の前記有限体ＧＦ（ｑ２）上の基底（ξ，１）、及び前記二次曲線ＣのＧＦ（ｑ２）有理点（α、β）に対して、前記楕円曲線ＥのＧＦ（ｑ２）有理点Ｐ＝（α＋βξ，√（Ｆ（α＋βξ）））（Ｆは前記楕円曲線ＥのＷｅｉｅｒｓｔｒａｓｓ型の定義方程式ｙ２＝ｘ３＋ａｘ＋ｂ＝Ｆ（ｘ）なる多項式）を生成し、
前記第三の手段は、前記楕円曲線ＥのＧＦ（ｑ４）有理点Ｐから、前期楕円曲線ＥのＦｒｏｂｅｎｉｕｓ自己準同型写像σを用いて前記楕円曲線ＥのＧＦ（ｑ）有理点Ｐ＋σ（Ｐ）＋σ２（Ｐ）＋σ３（Ｐ）を生成すること、
を特徴とする楕円曲線上の点生成装置。
【請求項９】
コンピュータに、要素数が（ｑ＋１）／２（ｑは５以上の素数べき）の集合Ｓの元と要素数が２の集合Ｔの元から有限体ＧＦ（ｑ）上定義された楕円曲線ＥのＧＦ（ｑ）有理点を生成させる点生成プログラムであって、
前記集合Ｓの元から予め定められた前記有限体ＧＦ（ｑ）上定義された二次曲線ＣのＧＦ（ｑ）有理点を生成する第一のステップと、
前記第一のステップで生成した前記二次曲線Ｃの前記ＧＦ（ｑ）有理点から前記楕円曲線ＥのＧＦ（ｑ２）有理点を生成する第二のステップと、
前記第二のステップで生成した前記楕円曲線ＥのＧＦ（ｑ２）有理点と前記集合Ｔの元から前記楕円曲線ＥのＧＦ（ｑ）有理点を生成する第三のステップと、
を備えることを特徴とする点生成プログラム。
【請求項１０】
請求項９に記載の点生成プログラムであって、
前記集合Ｓは集合ＧＦ（ｑ）＊／｛１，−１｝∪｛０｝、前記集合Ｔは｛１，−１｝であり、
前記第一のステップは、前記集合Ｓの元ｔから予め定められた２つのＧＦ（ｑ）上の有理関数α、βに対して、α（ｔ）、β（ｔ）を計算し、前記二次曲線ＣのＧＦ（ｑ）有理点Ｒ＝（α、β）を生成し、
前記第二のステップは、予め定められた前記有限体ＧＦ（ｑ２）の前記有限体ＧＦ（ｑ）上の基底（ξ，１）、及び前記二次曲線ＣのＧＦ（ｑ）有理点（α、β）から前記楕円曲線ＥのＧＦ（ｑ２）有理点Ｐ＝（α＋βξ，√（Ｆ（α＋βξ）））（Ｆは前記楕円曲線ＥのＷｅｉｅｒｓｔｒａｓｓ型の定義方程式ｙ２＝ｘ３＋ａｘ＋ｂ＝Ｆ（ｘ）に対して、Ｆ（ｘ）＝ｘ３＋ａｘ＋ｂなる多項式）を生成し、
前記第三のステップは、前記楕円曲線ＥのＧＦ（ｑ２）有理点Ｐから前記楕円曲線ＥのＦｒｏｂｅｎｉｕｓ自己準同型写像σを用いて前記楕円曲線ＥのＧＦ（ｑ）有理点（Ｐ＋σ（Ｐ））を生成すること、
を特徴とする点生成プログラム。
【請求項１１】
コンピュータに、要素数が（ｑ２＋１）／２（ｑは５以上の素数べき）の集合Ｓの元と要素数が２の集合Ｔの元から有限体ＧＦ（ｑ）上定義された楕円曲線ＥのＧＦ（ｑ）有理点を生成させる点生成プログラムであって、
前記集合Ｓの元から予め定められた前記有限体ＧＦ（ｑ２）上定義された二次曲線ＣのＧＦ（ｑ２）有理点を生成する第一のステップと、
前記第一のステップで生成した前記二次曲線Ｃの前記ＧＦ（ｑ２）有理点から前記楕円曲線ＥのＧＦ（ｑ４）有理点を生成する第二のステップと、
前記第二のステップで生成した前記楕円曲線ＥのＧＦ（ｑ４）有理点と前記集合Ｔの元から前記楕円曲線ＥのＧＦ（ｑ）有理点を生成する第三のステップと、
を備えることを特徴とする点生成プログラム。
【請求項１２】
請求項１１に記載の点生成プログラムであって、
前記集合Ｓは集合ＧＦ（ｑ２）＊／｛１，−１｝∪｛０｝、前記集合Ｔは｛１，−１｝であり、
前記第一のステップは、前記集合Ｓの元ｔから予め定められた２つのＧＦ（ｑ２）上の有理関数α、βに対して、α（ｔ）、β（ｔ）を計算し、前記二次曲線ＣのＧＦ（ｑ２）有理点Ｒ＝（α、β）を生成し、
前記第二のステップは、予め定められた前記有限体ＧＦ（ｑ４）の前記有限体ＧＦ（ｑ２）上の基底（ξ，１）、及び前記二次曲線ＣのＧＦ（ｑ２）有理点（α、β）に対して、前記楕円曲線ＥのＧＦ（ｑ２）有理点Ｐ＝（α＋βξ，√（Ｆ（α＋βξ）））（Ｆは前記楕円曲線ＥのＷｅｉｅｒｓｔｒａｓｓ型の定義方程式ｙ２＝ｘ３＋ａｘ＋ｂ＝Ｆ（ｘ）なる多項式）を生成し、
前記第三のステップは、前記楕円曲線ＥのＧＦ（ｑ４）有理点Ｐから、前期楕円曲線ＥのＦｒｏｂｅｎｉｕｓ自己準同型写像σを用いて前記楕円曲線ＥのＧＦ（ｑ）有理点Ｐ＋σ（Ｐ）＋σ２（Ｐ）＋σ３（Ｐ）を生成すること、
を特徴とする点生成プログラム。
【請求項１】
要素数が（ｑ＋１）／２（ｑは５以上の素数べき）の集合Ｓの元と要素数が２の集合Ｔの元から有限体ＧＦ（ｑ）上定義された楕円曲線ＥのＧＦ（ｑ）有理点を生成する点生成方法であって、
前記集合Ｓの元から予め定められた前記有限体ＧＦ（ｑ）上定義された二次曲線ＣのＧＦ（ｑ）有理点を生成する第一のステップと、
前記第一のステップで生成した前記二次曲線Ｃの前記ＧＦ（ｑ）有理点から前記楕円曲線ＥのＧＦ（ｑ２）有理点を生成する第二のステップと、
前記第二のステップで生成した前記楕円曲線ＥのＧＦ（ｑ２）有理点と前記集合Ｔの元から前記楕円曲線ＥのＧＦ（ｑ）有理点を生成する第三のステップと、
を備えることを特徴とする楕円曲線上の点生成方法。
【請求項２】
請求項１に記載の楕円曲線上の点生成方法であって、
前記集合Ｓは集合ＧＦ（ｑ）＊／｛１，−１｝∪｛０｝、前記集合Ｔは｛１，−１｝であり、
前記第一のステップは、前記集合Ｓの元ｔから予め定められた２つのＧＦ（ｑ）上の有理関数α、βに対して、α（ｔ）、β（ｔ）を計算し、前記二次曲線ＣのＧＦ（ｑ）有理点Ｒ＝（α、β）を生成し、
前記第二のステップは、予め定められた前記有限体ＧＦ（ｑ２）の前記有限体ＧＦ（ｑ）上の基底（ξ，１）、及び前記二次曲線ＣのＧＦ（ｑ）有理点（α、β）から前記楕円曲線ＥのＧＦ（ｑ２）有理点Ｐ＝（α＋βξ，√（Ｆ（α＋βξ）））（Ｆは前記楕円曲線ＥのＷｅｉｅｒｓｔｒａｓｓ型の定義方程式ｙ２＝ｘ３＋ａｘ＋ｂ＝Ｆ（ｘ）に対して、Ｆ（ｘ）＝ｘ３＋ａｘ＋ｂなる多項式）を生成し、
前記第三のステップは、前記楕円曲線ＥのＧＦ（ｑ２）有理点Ｐから前記楕円曲線ＥのＦｒｏｂｅｎｉｕｓ自己準同型写像σを用いて前記楕円曲線ＥのＧＦ（ｑ）有理点（Ｐ＋σ（Ｐ））を生成すること、
を特徴とする楕円曲線上の点生成方法。
【請求項３】
要素数が（ｑ２＋１）／２（ｑは５以上の素数べき）の集合Ｓの元と要素数が２の集合Ｔの元から有限体ＧＦ（ｑ）上定義された楕円曲線ＥのＧＦ（ｑ）有理点を生成する点生成方法であって、
前記集合Ｓの元から予め定められた前記有限体ＧＦ（ｑ２）上定義された二次曲線ＣのＧＦ（ｑ２）有理点を生成する第一のステップと、
前記第一のステップで生成した前記二次曲線Ｃの前記ＧＦ（ｑ２）有理点から前記楕円曲線ＥのＧＦ（ｑ４）有理点を生成する第二のステップと、
前記第二のステップで生成した前記楕円曲線ＥのＧＦ（ｑ４）有理点と前記集合Ｔの元から前記楕円曲線ＥのＧＦ（ｑ）有理点を生成する第三のステップと、
を備えることを特徴とする楕円曲線上の点生成方法。
【請求項４】
請求項３に記載の楕円曲線上の点生成方法であって、
前記集合Ｓは集合ＧＦ（ｑ２）＊／｛１，−１｝∪｛０｝、前記集合Ｔは｛１，−１｝であり、
前記第一のステップは、前記集合Ｓの元ｔから予め定められた２つのＧＦ（ｑ２）上の有理関数α、βに対して、α（ｔ）、β（ｔ）を計算し、前記二次曲線ＣのＧＦ（ｑ２）有理点Ｒ＝（α、β）を生成し、
前記第二のステップは、予め定められた前記有限体ＧＦ（ｑ４）の前記有限体ＧＦ（ｑ２）上の基底（ξ，１）、及び前記二次曲線ＣのＧＦ（ｑ２）有理点（α、β）に対して、前記楕円曲線ＥのＧＦ（ｑ２）有理点Ｐ＝（α＋βξ，√（Ｆ（α＋βξ）））（Ｆは前記楕円曲線ＥのＷｅｉｅｒｓｔｒａｓｓ型の定義方程式ｙ２＝ｘ３＋ａｘ＋ｂ＝Ｆ（ｘ）なる多項式）を生成し、
前記第三のステップは、前記楕円曲線ＥのＧＦ（ｑ４）有理点Ｐから、前期楕円曲線ＥのＦｒｏｂｅｎｉｕｓ自己準同型写像σを用いて前記楕円曲線ＥのＧＦ（ｑ）有理点Ｐ＋σ（Ｐ）＋σ２（Ｐ）＋σ３（Ｐ）を生成すること、
を特徴とする楕円曲線上の点生成方法。
【請求項５】
要素数が（ｑ＋１）／２（ｑは５以上の素数べき）の集合Ｓの元と要素数が２の集合Ｔの元から有限体ＧＦ（ｑ）上定義された楕円曲線ＥのＧＦ（ｑ）有理点を生成する点生成装置であって、
前記集合Ｓの元から予め定められた前記有限体ＧＦ（ｑ）上定義された二次曲線ＣのＧＦ（ｑ）有理点を生成する第一の手段と、
前記第一の手段で生成した前記二次曲線Ｃの前記ＧＦ（ｑ）有理点から前記楕円曲線ＥのＧＦ（ｑ２）有理点を生成する第二の手段と、
前記第二の手段で生成した前記楕円曲線ＥのＧＦ（ｑ２）有理点と前記集合Ｔの元から前記楕円曲線ＥのＧＦ（ｑ）有理点を生成する第三の手段と、
を備えることを特徴とする楕円曲線上の点生成装置。
【請求項６】
請求項５に記載の楕円曲線上の点生成装置であって、
前記集合Ｓは集合ＧＦ（ｑ）＊／｛１，−１｝∪｛０｝、前記集合Ｔは｛１，−１｝であり、
前記第一の手段は、前記集合Ｓの元ｔから予め定められた２つのＧＦ（ｑ）上の有理関数α、βに対して、α（ｔ）、β（ｔ）を計算し、前記二次曲線ＣのＧＦ（ｑ）有理点Ｒ＝（α、β）を生成し、
前記第二の手段は、予め定められた前記有限体ＧＦ（ｑ２）の前記有限体ＧＦ（ｑ）上の基底（ξ，１）、及び前記二次曲線ＣのＧＦ（ｑ）有理点（α、β）から前記楕円曲線ＥのＧＦ（ｑ２）有理点Ｐ＝（α＋βξ，√（Ｆ（α＋βξ）））（Ｆは前記楕円曲線ＥのＷｅｉｅｒｓｔｒａｓｓ型の定義方程式ｙ２＝ｘ３＋ａｘ＋ｂ＝Ｆ（ｘ）に対して、Ｆ（ｘ）＝ｘ３＋ａｘ＋ｂなる多項式）を生成し、
前記第三の手段は、前記楕円曲線ＥのＧＦ（ｑ２）有理点Ｐから前記楕円曲線ＥのＦｒｏｂｅｎｉｕｓ自己準同型写像σを用いて前記楕円曲線ＥのＧＦ（ｑ）有理点（Ｐ＋σ（Ｐ））を生成すること、
を特徴とする楕円曲線上の点生成装置。
【請求項７】
要素数が（ｑ２＋１）／２（ｑは５以上の素数べき）の集合Ｓの元と要素数が２の集合Ｔの元から有限体ＧＦ（ｑ）上定義された楕円曲線ＥのＧＦ（ｑ）有理点を生成する点生成装置であって、
前記集合Ｓの元から予め定められた前記有限体ＧＦ（ｑ２）上定義された二次曲線ＣのＧＦ（ｑ２）有理点を生成する第一の手段と、
前記第一の手段で生成した前記二次曲線Ｃの前記ＧＦ（ｑ２）有理点から前記楕円曲線ＥのＧＦ（ｑ４）有理点を生成する第二の手段と、
前記第二の手段で生成した前記楕円曲線ＥのＧＦ（ｑ４）有理点と前記集合Ｔの元から前記楕円曲線ＥのＧＦ（ｑ）有理点を生成する第三の手段と、
を備えることを特徴とする楕円曲線上の点生成装置。
【請求項８】
請求項７に記載の楕円曲線上の点生成装置であって、
前記集合Ｓは集合ＧＦ（ｑ２）＊／｛１，−１｝∪｛０｝、前記集合Ｔは｛１，−１｝であり、
前記第一の手段は、前記集合Ｓの元ｔから予め定められた２つのＧＦ（ｑ２）上の有理関数α、βに対して、α（ｔ）、β（ｔ）を計算し、前記二次曲線ＣのＧＦ（ｑ２）有理点Ｒ＝（α、β）を生成し、
前記第二の手段は、予め定められた前記有限体ＧＦ（ｑ４）の前記有限体ＧＦ（ｑ２）上の基底（ξ，１）、及び前記二次曲線ＣのＧＦ（ｑ２）有理点（α、β）に対して、前記楕円曲線ＥのＧＦ（ｑ２）有理点Ｐ＝（α＋βξ，√（Ｆ（α＋βξ）））（Ｆは前記楕円曲線ＥのＷｅｉｅｒｓｔｒａｓｓ型の定義方程式ｙ２＝ｘ３＋ａｘ＋ｂ＝Ｆ（ｘ）なる多項式）を生成し、
前記第三の手段は、前記楕円曲線ＥのＧＦ（ｑ４）有理点Ｐから、前期楕円曲線ＥのＦｒｏｂｅｎｉｕｓ自己準同型写像σを用いて前記楕円曲線ＥのＧＦ（ｑ）有理点Ｐ＋σ（Ｐ）＋σ２（Ｐ）＋σ３（Ｐ）を生成すること、
を特徴とする楕円曲線上の点生成装置。
【請求項９】
コンピュータに、要素数が（ｑ＋１）／２（ｑは５以上の素数べき）の集合Ｓの元と要素数が２の集合Ｔの元から有限体ＧＦ（ｑ）上定義された楕円曲線ＥのＧＦ（ｑ）有理点を生成させる点生成プログラムであって、
前記集合Ｓの元から予め定められた前記有限体ＧＦ（ｑ）上定義された二次曲線ＣのＧＦ（ｑ）有理点を生成する第一のステップと、
前記第一のステップで生成した前記二次曲線Ｃの前記ＧＦ（ｑ）有理点から前記楕円曲線ＥのＧＦ（ｑ２）有理点を生成する第二のステップと、
前記第二のステップで生成した前記楕円曲線ＥのＧＦ（ｑ２）有理点と前記集合Ｔの元から前記楕円曲線ＥのＧＦ（ｑ）有理点を生成する第三のステップと、
を備えることを特徴とする点生成プログラム。
【請求項１０】
請求項９に記載の点生成プログラムであって、
前記集合Ｓは集合ＧＦ（ｑ）＊／｛１，−１｝∪｛０｝、前記集合Ｔは｛１，−１｝であり、
前記第一のステップは、前記集合Ｓの元ｔから予め定められた２つのＧＦ（ｑ）上の有理関数α、βに対して、α（ｔ）、β（ｔ）を計算し、前記二次曲線ＣのＧＦ（ｑ）有理点Ｒ＝（α、β）を生成し、
前記第二のステップは、予め定められた前記有限体ＧＦ（ｑ２）の前記有限体ＧＦ（ｑ）上の基底（ξ，１）、及び前記二次曲線ＣのＧＦ（ｑ）有理点（α、β）から前記楕円曲線ＥのＧＦ（ｑ２）有理点Ｐ＝（α＋βξ，√（Ｆ（α＋βξ）））（Ｆは前記楕円曲線ＥのＷｅｉｅｒｓｔｒａｓｓ型の定義方程式ｙ２＝ｘ３＋ａｘ＋ｂ＝Ｆ（ｘ）に対して、Ｆ（ｘ）＝ｘ３＋ａｘ＋ｂなる多項式）を生成し、
前記第三のステップは、前記楕円曲線ＥのＧＦ（ｑ２）有理点Ｐから前記楕円曲線ＥのＦｒｏｂｅｎｉｕｓ自己準同型写像σを用いて前記楕円曲線ＥのＧＦ（ｑ）有理点（Ｐ＋σ（Ｐ））を生成すること、
を特徴とする点生成プログラム。
【請求項１１】
コンピュータに、要素数が（ｑ２＋１）／２（ｑは５以上の素数べき）の集合Ｓの元と要素数が２の集合Ｔの元から有限体ＧＦ（ｑ）上定義された楕円曲線ＥのＧＦ（ｑ）有理点を生成させる点生成プログラムであって、
前記集合Ｓの元から予め定められた前記有限体ＧＦ（ｑ２）上定義された二次曲線ＣのＧＦ（ｑ２）有理点を生成する第一のステップと、
前記第一のステップで生成した前記二次曲線Ｃの前記ＧＦ（ｑ２）有理点から前記楕円曲線ＥのＧＦ（ｑ４）有理点を生成する第二のステップと、
前記第二のステップで生成した前記楕円曲線ＥのＧＦ（ｑ４）有理点と前記集合Ｔの元から前記楕円曲線ＥのＧＦ（ｑ）有理点を生成する第三のステップと、
を備えることを特徴とする点生成プログラム。
【請求項１２】
請求項１１に記載の点生成プログラムであって、
前記集合Ｓは集合ＧＦ（ｑ２）＊／｛１，−１｝∪｛０｝、前記集合Ｔは｛１，−１｝であり、
前記第一のステップは、前記集合Ｓの元ｔから予め定められた２つのＧＦ（ｑ２）上の有理関数α、βに対して、α（ｔ）、β（ｔ）を計算し、前記二次曲線ＣのＧＦ（ｑ２）有理点Ｒ＝（α、β）を生成し、
前記第二のステップは、予め定められた前記有限体ＧＦ（ｑ４）の前記有限体ＧＦ（ｑ２）上の基底（ξ，１）、及び前記二次曲線ＣのＧＦ（ｑ２）有理点（α、β）に対して、前記楕円曲線ＥのＧＦ（ｑ２）有理点Ｐ＝（α＋βξ，√（Ｆ（α＋βξ）））（Ｆは前記楕円曲線ＥのＷｅｉｅｒｓｔｒａｓｓ型の定義方程式ｙ２＝ｘ３＋ａｘ＋ｂ＝Ｆ（ｘ）なる多項式）を生成し、
前記第三のステップは、前記楕円曲線ＥのＧＦ（ｑ４）有理点Ｐから、前期楕円曲線ＥのＦｒｏｂｅｎｉｕｓ自己準同型写像σを用いて前記楕円曲線ＥのＧＦ（ｑ）有理点Ｐ＋σ（Ｐ）＋σ２（Ｐ）＋σ３（Ｐ）を生成すること、
を特徴とする点生成プログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図２】
【図３】
【図４】
【図５】
【公開番号】特開２０１０−２１０８４４（Ｐ２０１０−２１０８４４Ａ）
【公開日】平成２２年９月２４日（２０１０．９．２４）
【国際特許分類】
【出願番号】特願２００９−５５８９１（Ｐ２００９−５５８９１）
【出願日】平成２１年３月１０日（２００９．３．１０）
【出願人】（０００００５１０８）株式会社日立製作所 (27,607)
【Ｆターム（参考）】
【公開日】平成２２年９月２４日（２０１０．９．２４）
【国際特許分類】
【出願日】平成２１年３月１０日（２００９．３．１０）
【出願人】（０００００５１０８）株式会社日立製作所 (27,607)
【Ｆターム（参考）】
[ Back to top ]