(57)【特許請求の範囲】
【請求項１】
標数ｐ（＞３）の体上で定義された楕円曲線を用いる楕円曲線暗号の楕円曲線データに基づいて、超楕円曲線暗号の超楕円曲線データを生成する鍵生成装置に使用される鍵生成プログラムであって、
前記鍵生成装置のコンピュータを、
入力された前記楕円曲線データ及び多項式基底に基づき、ヴェイユ降下を用いて前記超楕円曲線データを作成する超楕円曲線作成手段、
として機能させるための鍵生成プログラム。
【請求項２】
請求項１に記載の鍵生成プログラムにおいて、
前記鍵生成装置のコンピュータを、
前記超楕円曲線作成手段により作成された超楕円曲線データに関し、微分した超楕円曲線の式と共通の解が無いかと、任意の被約因子を２ｖ倍（ｖ：素数）して０になるかとを各々判定し、判定結果が両者とも肯定的であるとき、前記超楕円曲線データを出力する判定手段、
として機能させるための鍵生成プログラム。
【請求項３】
標数ｐ（＞３）の体上で定義された楕円曲線を用いる楕円曲線暗号の楕円曲線データに基づいて、超楕円曲線暗号の超楕円曲線データを生成する鍵生成装置に使用される鍵生成装置であって、
入力された前記楕円曲線データ及び多項式基底に基づき、ヴェイユ降下を用いて前記超楕円曲線データを作成する超楕円曲線作成手段、
を備えたことを特徴とする鍵生成装置。
【請求項４】
請求項３に記載の鍵生成装置において、
前記超楕円曲線作成手段により作成された超楕円曲線データに関し、微分した超楕円曲線の式と共通の解が無いかと、任意の被約因子を２ｖ倍（ｖ：素数）して０になるかとを各々判定し、判定結果が両者とも肯定的であるとき、前記超楕円曲線データを出力する判定手段、
を備えたことを特徴とする鍵生成装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、公開鍵暗号に用いる超楕円曲線を生成する鍵生成プログラム及び装置に関する。
【０００２】
【従来の技術】
近年、公開鍵暗号の分野では、楕円曲線暗号をさらに進めた技術として、有限体上の超楕円曲線を鍵として生成する鍵生成方式が研究されている。
【０００３】
ここで、楕円曲線とは、次式において、ｄ＝３のものを意味している。
【０００４】
ｙ２＝ｘｄ＋ａdｘ(d-1)＋…＋ａ1ｘ＋ａ0
有限体Ｆｐ（又はＦpn）上の係る楕円曲線上の点は群構造を持つ。なお、有限体Ｆｐは、ｐ個の元を有し、整数Ｚを素数ｐで割った余りの系Ｚ／ｐＺ（ｐを法とする既約剰余類）で示される。また、有限体Ｆpnは、ｐn個の元を有しており、以下、拡大体Ｆpnともいう。
【０００５】
一方、同様に、超楕円曲線の場合は、超楕円曲線に付随した商群であるヤコビアン（jacobian）が群構造を持つ。また、次数ｄが偶数の時にｇ＝（ｄ−２）／２とし、また、ｄが奇数の時にｇ＝（ｄ−１）／２として定義されるｇを種数と呼ぶ。楕円曲線は種数ｇ＝１であり、超楕円曲線は種数ｇ≧２である。
【０００６】
楕円曲線暗号が安全であるには、その位数が大きい素数で割れる必要がある。同様に超楕円曲線のヤコビアンも位数が大きい素数で割れる必要がある。なお、超楕円曲線とヤコビアン及び後述する被約因子の詳細は、例えば、文献「Ｎ．コブリッツ著，林彬訳，“暗号の代数理論”，シュプリンガー・フェアラーク東京，p198−p.201，p.212-p.244 （1999）」に紹介されている。
【０００７】
係る超楕円曲線の生成法としては、ＣＭ（complex multiplication: 虚数乗法）法、スクーフ（schoof）法及びヘス・セロウッシ・スマート（Hess-Seroussi-Smart）法の３つが知られている。
【０００８】
しかしながら、ＣＭ法は、現在、研究途上である。また、スクーフ法は、現在の所、計算量が多すぎて実用的でない。但し、ＣＭ法及びスクーフ法は、楕円曲線の生成法としては実用的に使用可能できる。
【０００９】
一方、ヘス・セロウッシ・スマート法は、２の拡大体上の超楕円曲線の場合、実用的な生成方法であり、ヴェイユ降下（weil descent）が使用される特徴を有している。なお、詳細はインターネット上で紹介されている（F.HESS, G.SEROUSSI, AND N.P.SMART, “TWO TOPICS IN HYPERELLIPTIC CRYPTOGRAPHY”, http://www.hpl.hp.com/techreports/2000/HPL-2000-110.html また、これの基礎となる理論の論文のＵＲＬは、http://www.hpl.hp.com/techreports/2000/HPL-2000-10.html及び http://www.hpl.hp.com/techreports/1999/HPL-1999-70.html）。
【００１０】
以下、このヘス・セロウッシ・スマート法の概略を図３のフローチャートを用いて説明する。
有限体Ｆｑの位数ｑ＝２ｒのとき、Ｆｑ上の超楕円曲線を構成する。
［Step１］
Ｆｑ2上の楕円曲線で位数が大きい素数ｖで割れる楕円曲線を（Ａ）式に示すように構成する。
ｙ２＋ｘｙ＝ｘ３＋ａｘ２＋ｂ    …（Ａ）
［Step２］
有限体Ｆｑ上のＦｑ2の正規基底（ｗ，ｗ２）（ｗ＋ｗ２＝１）を使い、ｙ＝ｙ0ｗ＋ｙ1ｗ２、ｘ＝ｘ0ｗ＋ｘ1ｗ２とし、これらｙ，ｘを（Ａ）式に代入する。
次に、両辺のｗ，ｗ２の係数を整理して（ｘ0，ｘ1，ｙ0，ｙ1）の連立方程式（Ｂ）を得る。
【００１１】
［Step３］
この（Ｂ）式と、超平面ｘ0＝ｘ1＝ｘとの交点に基づき、変数ｙ1を消去してｙ0，ｘの式を得る。ｙ0をｙと置き直してｙ，ｘの（Ｃ）式を得る。なお、（Ｃ）式を得る操作をヴェイユ降下（weil descent）と呼ぶ。
［Step4］
この（Ｃ）式に対し、双有理変換と呼ばれる変数変換を施して、種数２の超楕円曲線の式を得る。この超楕円曲線の式を出力する。
【００１２】
なお、（Ａ）式→（Ｃ）式の準同型写像が存在することから、（Ａ）式→ヤコビアンｊ(Ｃ)［（Ｃ）式のヤコビアン］の準同型写像が存在する。よって、ヤコビアンｊ(Ｃ)も素数ｖで割れる可能性が非常に高くなる。
従って、ヘス・セロウッシ・スマート法によれば、安全な超楕円曲線が生成可能となっている。
【００１３】
【発明が解決しようとする課題】
しかしながら以上のようなヘス・セロウッシ・スマートの方法は、２の拡大体、すなわち、標数２の場合に限定されている。
【００１４】
ここで、本発明者の考察によれば、標数２以外の場合についても、超楕円曲線を生成可能とすることが好ましい。一方、楕円曲線の標準形は、標数２、標数３及び標数２，３以外、の３通りある。本発明者の考察によれば、楕円曲線の標準形が異なると、超楕円曲線の生成方式も異なる可能性が高い。そこで、本発明者は、今回、２，３以外の標数の超楕円曲線の生成を図ることにした（但し、本発明と同じ方式により標数３の超楕円曲線も生成できる可能性はある）。
【００１５】
本発明は上記実情を考慮してなされたもので、超楕円曲線暗号に関し、２，３以外の一般標数の超楕円曲線を生成し得る鍵生成プログラム及び装置を提供することを目的とする。
【００１６】
【課題を解決するための手段】
第１の発明は、標数ｐ（＞３）の体上で定義された楕円曲線を用いる楕円曲線暗号の楕円曲線データに基づいて、超楕円曲線暗号の超楕円曲線データを生成する鍵生成装置に使用される鍵生成プログラムであって、前記鍵生成装置のコンピュータを、入力された前記楕円曲線データ及び多項式基底に基づき、ヴェイユ降下を用いて前記超楕円曲線データを作成する超楕円曲線作成手段、として機能させるための鍵生成プログラムである。
これにより、超楕円曲線暗号に関し、２，３以外の一般標数の超楕円曲線を生成することができる。
【００１７】
第２の発明は、第１の発明において、前記鍵生成装置のコンピュータを、前記超楕円曲線作成手段により作成された超楕円曲線データに関し、微分した超楕円曲線の式と共通の解が無いかと、任意の被約因子を２ｖ倍（ｖ：素数）して０になるかとを各々判定し、判定結果が両者とも肯定的であるとき、前記超楕円曲線データを出力する判定手段、として機能させるための鍵生成プログラムである。
これにより、第１の発明の作用に加え、超楕円曲線データを用いた超楕円曲線暗号の安全性を確保することができる。
【００１８】
なお、上記各発明は、記載の簡潔性の観点から、プログラムとして表現された場合のみを示したが、装置、方法、システム等の他のカテゴリーで表現してもよいことは言うまでもない。
【００１９】
【発明の実施の形態】
以下、本発明の一実施形態について図面を参照して説明する。
図１は本発明の一実施形態に係る鍵生成装置の構成を示す模式図である。この鍵生成装置１は、楕円曲線生成部１０、超楕円曲線生成部２０及び判定部３０を備えており、各部１０，２０，３０は、それぞれハードウェア、ソフトウェア又はそれらの組合せにより構成可能となっている。なお、ソフトウェアにより構成される場合、各部１０，２０，３０の機能を実現するためのプログラムが鍵生成装置のコンピュータに予めインストールされている。
【００２０】
楕円曲線生成部１０は、前述したＣＭ法又はスクーフ法などの処理機能の如き、楕円曲線ｙ２＝ｘ３＋ａｘ＋ｂを生成する周知の生成機能を有し、具体的には、基底作成部１１及び曲線作成部１２を備えている。
【００２１】
基底作成部１１は、有限体Ｆｐの位数ｑが入力されると、この位数ｑに基づいて、多項式基底（１，ｔ）を作成し、得られた多項式基底（１，ｔ）を曲線作成部１２に送出する機能をもっている。
【００２２】
曲線作成部１２は、基底作成部１１から受けた多項式基底（１，ｔ）に基づいて、Ｆｐ上で位数２ｖ（ｖは大きな素数）の楕円曲線を作成し、得られた楕円曲線の係数データａ，ｂ（楕円曲線データ）及び用いた多項式基底（１，ｔ）を超楕円曲線作成部２０に入力する機能をもっている。なお、２ｖに代えて、３ｖ，４ｖ等のように、ｖに任意の小さい値ｓを乗じた位数ｓｖを用いてもよい。
【００２３】
超楕円曲線作成部２０は、曲線作成部１２から受けた楕円曲線の係数データａ，ｂ及び多項式基底（１，ｔ）に基づいて、超楕円曲線を作成し、得られた超楕円曲線の係数データ（超楕円曲線データ）を判定部３０に出力する機能をもっている。
【００２４】
判定部３０は、超楕円曲線作成部２０から受けた超楕円曲線の係数データに基づいて、この超楕円曲線の安全性を判定する機能を有し、安全性が高いと判定した超楕円曲線の係数データを通過させる機能をもっている。但し、判定部３０は、超楕円曲線の生成に必須な構成ではないため、適宜、省略してもよい。
【００２５】
次に、以上のように構成された鍵生成装置の動作を図２のフローチャートを用いて説明する。なお、この動作は、ヘス・セロウッシ・スマートの方法を標数ｐ（ｐは２，３以外の一般の素数）に拡張した内容であり、ｑ＝ｐのとき、Ｆｐ上の超楕円曲線を構成するものである。
【００２６】
まず、準備として、楕円曲線生成部１０においては、基底作成部１１が、入力された有限体Ｆｐの位数ｑに基づいて、多項式基底（１，ｔ）を作成して曲線作成部１２に送出する。
【００２７】
［Step１*］
曲線作成部１２は、この多項式基底（１，ｔ）に基づいて、Ｆｐ上の楕円曲線で位数が大きい素数ｖで割れるように、位数２ｖの楕円曲線の（Ａ*）式を構成する。
【００２８】
ｙ２＝ｘ３＋ａｘ＋ｂ    …（Ａ*）
しかる後、曲線作成部１２は、得られた楕円曲線の係数データａ，ｂ及び用いた多項式基底（１，ｔ）を超楕円曲線作成部２０に入力する。
【００２９】
［Step２*］
超楕円曲線作成部２０は、Ｆｐ上のＦｐ2の多項式基底（１，ｔ）（ｔ2＝ｕはＦｐの元）を使い、ｙ＝ｙ0＋ｙ1ｔ、ｘ＝ｘ0＋ｘ1ｔとする。
次に、これらｙ，ｘを（Ａ*）式に代入し、展開により生じるｔ2をｕに置き換えながら数式処理を進める。
しかる後、両辺のｔの係数を整理して（ｘ0，ｘ1，ｙ0，ｙ1）の連立方程式の（Ｂ*）式を得る。
【００３０】
［Step３*］
次に、超楕円曲線作成部２０は、この（Ｂ）式と、超平面ｘ0＝ｘ1＝ｘとの交点に基づき、変数ｙ1を消去してｙ0，ｘの式を得る。ｙ0をｙと置き直してｙ，ｘの（Ｃ*）式を得る（ヴェイユ降下）。この（Ｃ*）式は次の形になる。
【００３１】
（ｙ2−ｆ(ｘ)）2 ＝ｈ(ｘ)      …（Ｃ*）
ここで、ｆ(ｘ)は３次式になる可能性が高く、ｈ(ｘ)は６次式になる可能性が高い。なお、ｆ(ｘ)＝（１＋３ｗ）ｘ3＋…でｗ≡−1/3(mod p)の場合以外はｆ(ｘ)が３次式になり、ｈ(ｘ)＝（１−ｗ）3／４＊ｘ6＋…でｗ≡１(mod p)の場合以外はｈ(ｘ)が６次式になる。そして、ｗ≡−1/3,１(mod p)となる場合は、例えば予め曲線作成部１２の設定により回避可能となっている。
【００３２】
［Step4*］
（Ｃ*）式中、ｅ＝ｙ２−ｆ(ｘ)と置くと、（ｘ，ｙ）→（ｘ，ｅ）は、２対１対応（±ｙ対ｅ対応）により２次の被覆となり、次に示すように、種数２の超楕円曲線の（Ｄ）式を得る。
【００３３】
ｅ２＝ｈ(ｘ)    …（Ｄ）
よって、超楕円曲線作成部２０は、この超楕円曲線の（Ｄ）式における６次式ｈ(ｘ)の係数データを判定部３０に出力する。
【００３４】
［Step5*］
判定部３０は、超楕円曲線の（Ｄ）式に関し、安全性の観点から、（条件１）微分した式ｈ’(ｘ)と共通の解（＝重根）が無いこと、（条件２）任意の被約因子を２ｖ倍して０になる（＝大きい素数ｖで割れる）こと、という２つの条件を満たすか否かを確認する。なお、条件２は、例えば３〜４個の被約因子を対象にして行い、１回でも確認されればよい。ここで、被約因子は、ヤコビアンの全ての元を一意的に表現可能な性質を有しており、詳しくは前述した文献「暗号の代数理論」に紹介されている。
【００３５】
また、判定部３０は、判定結果が各条件の１つでも満たさなければ処理を終了し、最初の楕円曲線作成部１０から鍵生成処理を繰り返させる。
一方、判定結果が各条件を満たせば、判定部３０は、超楕円曲線の（Ｄ）式における６次式ｈ(ｘ)の係数データを通過出力させる。
【００３６】
なお、（Ｄ）式のヤコビアンをｊ(Ｄ)と置くと、ｊ(Ｄ)→ｊ（Ｃ*）の準同型写像が存在する。前述した（Ａ*）→ｊ(Ｃ*)の準同型写像と合成して、（Ａ*）→ｊ(Ｄ)の準同型写像を得る。ここで、（Ａ*）式の位数は素数ｖで割れるので、ｊ(Ｄ)の位数は素数ｖで割れる可能性が高い。よって、得られた超楕円曲線の式(Ｄ)は安全性が高いと考えられる。
【００３７】
以下、判定部３０から出力された超楕円曲線の式の係数データは、超楕円曲線暗号方式の公開鍵として、この超楕円曲線暗号方式の適用された各種システムに使用される。
【００３８】
上述したように本実施形態によれば、超楕円曲線暗号に関し、２，３以外の一般標数の超楕円曲線を生成することができる。また、生成した超楕円曲線を用いた超楕円曲線暗号の安全性を確保することができる。
【００３９】
なお、本実施形態は、ｑ＝ｐとした場合を説明したが、これに限らず、ｑ＝ｐrとしても、本発明を同様に実施して同様の効果を得ることができる。
【００４０】
また、本実施形態は、Ｆｐ上のＦｐ2の多項式基底（１,ｔ）を用い、ｙ＝ｙ0＋ｙ1ｔ、ｘ＝ｘ0＋ｘ1ｔとしてｙ,ｘを（Ａ*）式に代入した場合について説明したが、これに限らず、Ｆｐ上のＦｐ3の多項式基底（１,ｔ,ｔ3）を用い、ｙ＝ｙ0＋ｙ1ｔ＋ｙ2ｔ3、ｘ＝ｘ0＋ｘ1ｔ＋ｘ2ｔ3としてｙ,ｘを（Ａ*）式に代入しても、本発明を同様に実施して同様の効果を得ることができる。
【００４１】
なお、上記実施形態に記載した手法は、コンピュータに実行させることのできるプログラムとして、磁気ディスク（フロッピーディスク、ハードディスクなど）、光ディスク（ＣＤ−ＲＯＭ、ＤＶＤなど）、光磁気ディスク（ＭＯ）、半導体メモリなどの記憶媒体に格納して頒布することもできる。
【００４２】
また、この記憶媒体としては、プログラムを記憶でき、かつコンピュータが読み取り可能な記憶媒体であれば、その記憶形式は何れの形態であっても良い。
【００４３】
また、記憶媒体からコンピュータにインストールされたプログラムの指示に基づきコンピュータ上で稼働しているＯＳ（オペレーティングシステム）や、データベース管理ソフト、ネットワークソフト等のＭＷ（ミドルウェア）等が本実施形態を実現するための各処理の一部を実行しても良い。
【００４４】
さらに、本発明における記憶媒体は、コンピュータと独立した媒体に限らず、ＬＡＮやインターネット等により伝送されたプログラムをダウンロードして記憶または一時記憶した記憶媒体も含まれる。
【００４５】
また、記憶媒体は１つに限らず、複数の媒体から本実施形態における処理が実行される場合も本発明における記憶媒体に含まれ、媒体構成は何れの構成であっても良い。
【００４６】
尚、本発明におけるコンピュータは、記憶媒体に記憶されたプログラムに基づき、本実施形態における各処理を実行するものであって、パソコン等の１つからなる装置、複数の装置がネットワーク接続されたシステム等の何れの構成であっても良い。
【００４７】
また、本発明におけるコンピュータとは、パソコンに限らず、情報処理機器に含まれる演算処理装置、マイコン等も含み、プログラムによって本発明の機能を実現することが可能な機器、装置を総称している。
【００４８】
なお、本願発明は、上記各実施形態に限定されるものでなく、実施段階ではその要旨を逸脱しない範囲で種々に変形することが可能である。また、各実施形態は可能な限り適宜組み合わせて実施してもよく、その場合、組み合わされた効果が得られる。さらに、上記各実施形態には種々の段階の発明が含まれており、開示される複数の構成用件における適宜な組み合わせにより種々の発明が抽出され得る。例えば実施形態に示される全構成要件から幾つかの構成要件が省略されることで発明が抽出された場合には、その抽出された発明を実施する場合には省略部分が周知慣用技術で適宜補割れるものである。
【００４９】
その他、本発明はその要旨を逸脱しない範囲で種々変形して実施できる。
【００５０】
【発明の効果】
以上説明したように本発明によれば、超楕円曲線暗号に関し、２，３以外の一般標数の超楕円曲線を生成できる。
【図面の簡単な説明】
【図１】本発明の一実施形態に係る鍵生成装置の構成を示す模式図
【図２】同実施形態における動作を説明するためのフローチャート
【図３】従来の超楕円曲線の生成動作を説明するためのフローチャート
【符号の説明】
１…鍵生成装置
１０…楕円曲線生成部
１１…基底作成部
１２…曲線作成部
２０…超楕円曲線作成部
３０…判定部
【図１】
0004693252.tif 000002
【図２】
0004693252.tif 000003
【図３】
0004693252.tif 000004