(57)【特許請求の範囲】
【請求項１】
３以上の素数から順に素数ｐを決定する素数ｐ決定部と、
２以上の小さな整数から順に種数ｇを決定する種数ｇ決定部と、
種数ｇに基づいて拡大次数ｎを決定する拡大次数ｎ決定部と、
種数ｇから超楕円曲線Ｃの次数を決定して超楕円曲線Ｃを順次生成するとともに、決定された拡大次数ｎに基づく有限体Ｆq（要素数ｑ＝ｐn ）と上記超楕円曲線Ｃとから超楕円曲線Ｃに付随する有限体Ｆq 上のヤコビ多様体Ｊ（Ｃ，Ｆq ）の要素数＃Ｊ（Ｃ，Ｆq ）を計算し、最大の素因数を求め、最大の素因数が暗号の安全性の目安となる目安整数Ｋ以上となるような超楕円曲線Ｃを選択する超楕円曲線Ｃ決定部と
を備えたことを特徴とする超楕円曲線Ｃ生成装置。
【請求項２】
上記拡大次数ｎ決定部は、暗号の安全性の目安となる目安整数Ｋを入力し、種数ｇと目安整数Ｋから拡大次数ｎを計算することを特徴とする請求項１記載の超楕円曲線Ｃ生成装置。
【請求項３】
上記種数ｇ決定部は、超楕円曲線Ｃ決定部が目安整数Ｋより大きな値を持つ最大の素因数を求められないとき、種数ｇの値を大きくすることを特徴とする請求項２記載の超楕円曲線Ｃ生成装置。
【請求項４】
上記素数ｐ決定部は、素数ｐを３と決定し、
上記拡大次数ｎ決定部は、拡大次数ｎを５９と決定し、
上記超楕円曲線Ｃ決定部は、上記超楕円曲線Ｃとして、ｖ2 ＝ｕ5 ＋ｕ4 ＋ｕ3＋ｕ＋１を選択する
ことを特徴とする請求項１記載の超楕円曲線Ｃ生成装置。
【請求項５】
上記素数ｐ決定部は、素数ｐを３と決定し、
上記拡大次数ｎ決定部は、拡大次数ｎを３７と決定し、
上記超楕円曲線Ｃ決定部は、上記超楕円曲線Ｃとして、ｖ2 ＝ｕ7 ＋ｕ5 ＋ｕ3 ＋ｕ2 ＋ｕ＋１を選択する
ことを特徴とする請求項１記載の超楕円曲線Ｃ生成装置。
【請求項６】
上記素数ｐ決定部は、素数ｐを３と決定し、
上記拡大次数ｎ決定部は、拡大次数ｎを３７と決定し、
上記超楕円曲線Ｃ決定部は、上記超楕円曲線Ｃとして、ｖ2 ＝ｕ7 ＋ｕ6 ＋ｕ5 ＋ｕ4 ＋１を選択する
ことを特徴とする請求項１記載の超楕円曲線Ｃ生成装置。
【請求項７】
上記素数ｐ決定部は、素数ｐを３と決定し、
上記拡大次数ｎ決定部は、拡大次数ｎを２９と決定し、
上記超楕円曲線Ｃ決定部は、上記超楕円曲線Ｃとして、ｖ2 ＝ｕ9 ＋ｕ8 ＋ｕ7 ＋ｕ4 ＋ｕ3 ＋ｕ2 ＋ｕ＋１を選択する
ことを特徴とする請求項１記載の超楕円曲線Ｃ生成装置。
【請求項８】
上記素数ｐ決定部は、素数ｐを３と決定し、
上記拡大次数ｎ決定部は、拡大次数ｎを２９と決定し、
上記超楕円曲線Ｃ決定部は、上記超楕円曲線Ｃとして、ｖ2 ＝ｕ9 ＋ｕ6 ＋ｕ5 ＋ｕ3 ＋１を選択する
ことを特徴とする請求項１記載の超楕円曲線Ｃ生成装置。
【請求項９】
上記素数ｐ決定部は、素数ｐを３と決定し、
上記拡大次数ｎ決定部は、拡大次数ｎを２９と決定し、
上記超楕円曲線Ｃ決定部は、上記超楕円曲線Ｃとして、ｖ2 ＝ｕ9 ＋ｕ7 ＋ｕ5 ＋ｕ4 ＋ｕ3 ＋ｕ＋１を選択する
ことを特徴とする請求項１記載の超楕円曲線Ｃ生成装置。
【請求項１０】
上記素数ｐ決定部は、素数ｐを３と決定し、
上記拡大次数ｎ決定部は、拡大次数ｎを２９と決定し、
上記超楕円曲線Ｃ決定部は、上記超楕円曲線Ｃとして、ｖ2 ＝ｕ9 ＋ｕ7 ＋ｕ6 ＋ｕ2 ＋１を選択する
ことを特徴とする請求項１記載の超楕円曲線Ｃ生成装置。
【請求項１１】
上記素数ｐ決定部は、素数ｐを３と決定し、
上記拡大次数ｎ決定部は、拡大次数ｎを２９と決定し、
上記超楕円曲線Ｃ決定部は、上記超楕円曲線Ｃとして、ｖ2 ＝ｕ9 ＋ｕ7 ＋ｕ6 ＋ｕ5 ＋ｕ4 ＋ｕ3 ＋ｕ＋１を選択する
ことを特徴とする請求項１記載の超楕円曲線Ｃ生成装置。
【請求項１２】
上記素数ｐ決定部は、素数ｐを５と決定し、
上記拡大次数ｎ決定部は、拡大次数ｎを４３と決定し、
上記超楕円曲線Ｃ決定部は、上記超楕円曲線Ｃとして、ｖ2 ＝ｕ5 ＋ｕ2 ＋１を選択する
ことを特徴とする請求項１記載の超楕円曲線Ｃ生成装置。
【請求項１３】
上記素数ｐ決定部は、素数ｐを５と決定し、
上記拡大次数ｎ決定部は、拡大次数ｎを２３と決定し、
上記超楕円曲線Ｃ決定部は、上記超楕円曲線Ｃとして、ｖ2 ＝ｕ7 ＋ｕ6 ＋ｕ2 ＋１を選択する
ことを特徴とする請求項１記載の超楕円曲線Ｃ生成装置。
【請求項１４】
上記素数ｐ決定部は、素数ｐを５と決定し、
上記拡大次数ｎ決定部は、拡大次数ｎを１９と決定し、
上記超楕円曲線Ｃ決定部は、上記超楕円曲線Ｃとして、ｖ2 ＝ｕ9 ＋ｕ6 ＋ｕ4 ＋ｕ3 ＋１を選択する
ことを特徴とする請求項１記載の超楕円曲線Ｃ生成装置。
【請求項１５】
上記素数ｐ決定部は、素数ｐを５と決定し、
上記拡大次数ｎ決定部は、拡大次数ｎを１９と決定し、
上記超楕円曲線Ｃ決定部は、上記超楕円曲線Ｃとして、ｖ2 ＝ｕ9 ＋ｕ7 ＋ｕ6 ＋ｕ5 ＋ｕ3 ＋ｕ＋１を選択する
ことを特徴とする請求項１記載の超楕円曲線Ｃ生成装置。
【請求項１６】
上記素数ｐ決定部は、素数ｐを５と決定し、
上記拡大次数ｎ決定部は、拡大次数ｎを１９と決定し、
上記超楕円曲線Ｃ決定部は、上記超楕円曲線Ｃとして、ｖ2 ＝ｕ9 ＋ｕ8 ＋ｕ7 ＋ｕ4 ＋ｕ＋１を選択する
ことを特徴とする請求項１記載の超楕円曲線Ｃ生成装置。
【請求項１７】
上記素数ｐ決定部は、素数ｐを７と決定し、
上記拡大次数ｎ決定部は、拡大次数ｎを２９と決定し、
上記超楕円曲線Ｃ決定部は、上記超楕円曲線Ｃとして、ｖ2 ＝ｕ5 ＋ｕ4 ＋ｕ2 ＋１を選択する
ことを特徴とする請求項１記載の超楕円曲線Ｃ生成装置。
【請求項１８】
上記素数ｐ決定部は、素数ｐを７と決定し、
上記拡大次数ｎ決定部は、拡大次数ｎを１９と決定し、
上記超楕円曲線Ｃ決定部は、上記超楕円曲線Ｃとして、ｖ2 ＝ｕ7 ＋ｕ6 ＋ｕ5 ＋ｕ3 ＋ｕ＋１を選択する
ことを特徴とする請求項１記載の超楕円曲線Ｃ生成装置。
【請求項１９】
上記素数ｐ決定部は、素数ｐを７と決定し、
上記拡大次数ｎ決定部は、拡大次数ｎを１７と決定し、
上記超楕円曲線Ｃ決定部は、上記超楕円曲線Ｃとして、ｖ2 ＝ｕ9 ＋ｕ8 ＋ｕ6 ＋ｕ5 ＋ｕ3 ＋ｕ＋１を選択する
ことを特徴とする請求項１記載の超楕円曲線Ｃ生成装置。
【請求項２０】
上記請求項１〜請求項１９のいずれかに記載した超楕円曲線Ｃ生成装置と、
上記超楕円曲線Ｃ生成装置が計算した要素数＃Ｊ（Ｃ，Ｆq ）から求めた上記最大の素因数を位数として持つ要素Ｄを選択し、選択した要素Ｄと上記超楕円曲線Ｃ生成装置が選択した超楕円曲線Ｃと上記拡大次数ｎ決定部により決定された拡大次数ｎに基づく有限体Ｆq とを暗号通信で使用するパラメータとして出力する要素Ｄ生成部と
を備えたことを特徴とする暗号管理装置。
【請求項２１】
上記請求項２０に記載した暗号管理装置が出力したパラメータに基づき、データを暗号化する計算手段と、
上記計算手段が暗号化したデータをデータ受信装置へ送信する暗号文出力手段と
を備えることを特徴とするデータ送信装置。
【請求項２２】
データ送信装置が送信した暗号化したデータを入力する暗号文入力手段と、
上記請求項２０に記載した暗号管理装置が出力したパラメータに基づき、上記暗号文入力手段が入力した暗号文を復号する計算手段と
を備えることを特徴とするデータ受信装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、ディジタル情報を暗号化して安全に暗号通信する技術に関する。
【０００２】
【従来の技術】
従来の超楕円曲線を用いた暗号化方法について説明する。
従来の超楕円曲線を用いた暗号化方法には、松尾、趙、辻井著、“拡大体上のアーベル多様体に基づく暗号系の構成方法”、暗号と情報セキュリティシンポジウム（ＳＣＩＳ）、（１９９７）、ＳＣＩＳ’９７−１２Ｅがある。また、公開鍵暗号及び離散対数問題については、岡本龍明、山本博資著、“現代暗号”、産業図書（１９９７）に記載されている。
【０００３】
まず、本発明の技術的背景である公開鍵暗号、離散対数問題、超楕円曲線及びヤコビ多様体について簡単に説明する。
公開鍵暗号通信においては、利用者毎に秘密鍵ｘと公開鍵Ｙの組が用意され、秘密鍵ｘは、各利用者が秘密に保持しておく。公開鍵Ｙは、利用者自身以外の一般に公開する。利用者Ｂが利用者Ａに秘密にデータを送りたい時は、利用者Ｂは、利用者Ａに対応する公開鍵Ｙを用いてデータを暗号化する。この暗号文は、秘密鍵ｘを知る利用者Ａにしか復号できない。
離散対数問題とは群Ｇの２つの要素ｇ1 ，ｇ2 に対して、ｇ1 ＝ｍｇ2 （ｍは整数）を満たすようなｍを求める問題である。群Ｇの要素の数が大きい場合、離散対数問題を解くことは、計算量的に非常に困難になることが知られている。この事実を利用して公開鍵暗号を設計することができ、本発明においても離散対数問題を解く困難さを暗号の安全性の根拠にして暗号化を行う。
超楕円曲線Ｃとは、ｖ2 ＋ｈ（ｕ）ｖ＝ｆ（ｕ）と表される方程式で、曲線の種数をｇとすると、ｆ（ｕ）は次数２ｇ＋１のモニック多項式、ｈ（ｕ）は次数が高々ｇの多項式である。
種数ｇとは、曲線の特徴を表すパラメータである。例えば、種数ｇ＝３の場合の超楕円曲線は、次数が２ｇ＋１＝２・３＋１＝７となり、例えば、ｖ2 ＋ｖ＝ｕ7 となる。超楕円曲線Ｃと有限体Ｆq を決めると、超楕円曲線Ｃに付随する有限体Ｆq 上のヤコビ多様体Ｊ（Ｃ，Ｆq ）（以下、単にＪともいう）が構成される。ヤコビ多様体Ｊ（Ｃ，Ｆq ）の要素数＃Ｊ（Ｃ，Ｆq ）（以下、単に＃Ｊともいう）は、およそ＃Ｊ＝ｑg になることが知られている。即ち、ヤコビ多様体の要素数＃Ｊが同じならば、種数ｇが大きくなるほど有限体Ｆq の要素数ｑは小さくなる。
【０００４】
ここで、現在の暗号処理に用いられている楕円曲線について説明する。
楕円曲線とは、例えば、ｙ2 ＋ｘｙ＝ｘ3 ＋ａ1 ｘ2 ＋ａ2 と表される３次式の方程式で、種数ｇは１であり、次数は３（２ｇ＋１＝２＋１＝３）である。超楕円曲線は、種数が１以上の値をとるのに対し、楕円曲線は、種数ｇは必ず１である。そして、超楕円曲線の種数ｇ＝１の場合は、楕円曲線となる。また、実際の計算は有限体（Ｆq ）上で行われるが、楕円曲線の群の要素は点（ｘ，ｙ）で表されるのに対し、超楕円曲線に付随する有限体Ｆq 上のヤコビ多様体Ｊ（Ｃ，Ｆq ）の要素は、有限体Ｆq 係数の２つ多項式ａ（ｕ），ｂ（ｕ）により表現される。ここで、ａ（ｕ）の次数はｇ以下、ｂ（ｕ）の次数はａ（ｕ）の次数未満である。また、有限体Ｆq の要素は、ｑ＝２n のときｎビットの整数で表される。従って、超楕円曲線の計算は、楕円曲線に比べて複雑となる。
【０００５】
図７，図８，図９は、従来の超楕円曲線を用いた暗号化方法を示すフローチャートである。
図７は、暗号鍵生成方法を示すフローチャートである。
図８は、暗号化方法を示すフローチャートである。
図９は、復号化方法を示すフローチャートである。
図において、Ｓ４０１は超楕円曲線Ｃ：ｖ2 ＋ｈ（ｕ）ｖ＝ｆ（ｕ）と、ｑ個の要素を持つ有限体Ｆq と、ヤコビ多様体Ｊの要素Ｄを選択するステップである。超楕円曲線Ｃの種数ｇは、この従来例ではｇ＝２が選ばれている。Ｓ４０２は整数ｘを選択し、整数ｘを秘密鍵とするステップ、Ｓ４０３はヤコビ多様体Ｊ上でＹ＝ｘＤを計算し、Ｙを公開鍵とするステップ、Ｓ５０１は平文ｍと整数ｒを選択するステップ、Ｓ５０２はヤコビ多様体Ｊ上でＣ1 ＝ｒＤとＣ2 ＝ｒＹ＋ｍを計算するステップ、Ｓ５０３は（Ｃ1 ，Ｃ2 ）を平文ｍを暗号化した暗号文とするステップ、Ｓ６０１は暗号文（Ｃ1 ，Ｃ2 ）と秘密鍵ｘとからヤコビ多様体Ｊ上でｍ＝Ｃ2 −ｘＣ1 を計算するステップ、Ｓ６０２はｍを平文とするステップである。
【０００６】
次に、動作を説明する。
まず、暗号鍵生成方法を図７に基づいて説明する。
暗号通信の利用者は、まず、Ｓ４０１において、ｑ個の要素を持つ有限体Ｆq と、超楕円曲線Ｃ：ｖ2 ＋ｈ（ｕ）ｖ＝ｆ（ｕ）を選択する。この際、ヤコビ多様体の要素数＃Ｊが大きな素数で割り切れるように、超楕円曲線Ｃ及び有限体Ｆq を選択しなければならない。これは、超楕円曲線を用いた公開鍵暗号の解読を困難にするための条件である。次に、ヤコビ多様体Ｊの要素Ｄを選択する。次に、Ｓ４０２において、整数ｘを選択する。整数ｘを秘密鍵として秘密に保存しておく。Ｓ４０３において、公開鍵Ｙを計算する。公開鍵Ｙは、Ｙ＝ｘＤとして計算される。
次に、暗号化方法を図８に基づいて説明する。
まず、Ｓ５０１において、暗号化したいデータｍ（これを平文と呼ぶ）と整数ｒを選択する。次に、Ｓ５０２において、ヤコビ多様体Ｊ（Ｃ，Ｆq ）上で、Ｃ1 ＝ｒＤと、Ｃ2 ＝ｒＹ＋ｍを計算する。次に、Ｓ５０３において、Ｃ1 とＣ2 の組（Ｃ1 ，Ｃ2 ）を暗号文とする。
【０００７】
次に、復号化方法を図９に基づいて説明する。
まず、Ｓ６０１において、暗号文（Ｃ1 ，Ｃ2 ）と秘密鍵ｘとから、有限体Ｆq 上でｍ＝Ｃ2 −ｘＣ1 （ｍ＝Ｃ2 −ｒＹ＝Ｃ2 −ｒｘＤ＝Ｃ2 −ｘＣ1 ）を計算する。Ｓ６０２において、ｍを平文とする。
【０００８】
超楕円曲線を用いた暗号化方法では、一般に、演算は全て有限体Ｆq 上で行われる。有限体Ｆq の要素数ｑは、ある素数ｐのべき乗でｑ＝ｐn と表される。有限体Ｆpnは、有限体Ｆp の拡大体と呼ばれ、ｎは拡大次数と呼ばれる。ｐが３以上の素数の拡大体を用いた暗号化方法においては、ｐが小さい方が暗号化／復号化の速度が速い。従来の暗号化方法では、有限体Ｆ3131が用いられていた。
【０００９】
【発明が解決しようとする課題】
従来のｐ＞２の有限体Ｆpnを用いた超楕円曲線を用いた暗号化方法は、以上のようにｐ＝３１であるため、より小さいｐと比較して、暗号化及び復号化の速度が遅くなるという課題があった。
【００１０】
本発明の目的は、係る課題を解決するためになされたもので、ヤコビ多様体Ｊ（Ｃ，Ｆq ）の有限体Ｆq として、ｐ＞２の拡大体Ｆpnを用いる場合に、ｐを小さな素数（例えば、３又は５又は７）にして、高速に暗号化及び復号化を行うことができ、かつ、安全な暗号を得ることにある。即ち、本発明の目的は、超楕円曲線を用いた暗号処理の実用的速度の達成を目的とする。
【００１１】
【課題を解決するための手段】
この発明に係る暗号管理装置は、超楕円曲線Ｃに付随する有限体Ｆq 上のヤコビ多様体をＪ（Ｃ，Ｆq ）とし、要素数ｑをｐn （ｐは３以上の素数、ｎは拡大次数）とするとき、
３以上の小さな素数ｐから順に超楕円曲線Ｃを生成する超楕円曲線Ｃ生成部を備えたことを特徴とする。
【００１２】
上記超楕円曲線Ｃ生成部は、
３以上の素数から順に素数ｐを決定する素数ｐ決定部と、
２以上の小さな整数から順に種数ｇを決定する種数ｇ決定部と、
種数ｇに基づいて拡大次数ｎを決定する拡大次数ｎ決定部と、
種数ｇから超楕円曲線Ｃの次数を決定して超楕円曲線Ｃを順次生成するとともに、選択された拡大次数ｎに基づく有限体Ｆq と上記超楕円曲線Ｃとからヤコビ多様体Ｊ（Ｃ，Ｆq ）の要素数＃Ｊ（Ｃ，Ｆq ）を計算し、最大の素因数を求め、最大の素因数が暗号の安全性の目安となる目安整数Ｋ以上となるような超楕円曲線Ｃを選択する超楕円曲線Ｃ決定部と
を備えたことを特徴とする。
【００１３】
上記拡大次数ｎ決定部は、暗号の安全性の目安となる目安整数Ｋを入力し、種数ｇと目安整数Ｋから拡大次数ｎを計算することを特徴とする。
【００１４】
上記種数ｇ決定部は、超楕円曲線Ｃ決定部が目安整数Ｋより大きな値を持つ最大の素因数を求められないとき、種数ｇの値を大きくすることを特徴とする。
【００１５】
この発明に係る暗号化方法は、素数ｐをメモリから取得して決定する工程と、
種数ｇをメモリから取得して決定する工程と、
ヤコビ多様体Ｊの目安整数Ｋをメモリから取得する工程と、
種数ｇと目安整数Ｋから拡大次数ｎを決定する工程と、
種数ｇから超楕円曲線Ｃの次数を計算し、計算した次数に基づく超楕円曲線Ｃを生成し、決定した拡大次数ｎに基づく有限体Ｆpnと生成した超楕円曲線Ｃとから要素数＃Ｊを計算し、最大の素因数を検出し、メモリに記憶する工程と、
メモリに記憶された最大の素因数が目安整数Ｋより大きい場合に、メモリに記憶された最大の素因数を生成した超楕円曲線Ｃを暗号に用いる超楕円曲線Ｃとして決定する工程と
を備えたことを特徴とする。
【００１６】
この発明に係る暗号化方法は、超楕円曲線Ｃに付随する有限体Ｆ3n上のヤコビ多様体をＪ（Ｃ，Ｆ3n）とするとき、
前記ヤコビ多様体Ｊ（Ｃ，Ｆ3n）の要素の数＃Ｊ（Ｃ，Ｆ3n）が大きな素数で割り切れるように前記超楕円曲線Ｃと前記有限体Ｆ3nをとり、
前記ヤコビ多様体Ｊ（Ｃ，Ｆ3n）上定義される離散対数問題の困難さを安全性の根拠に持つことを特徴とする。
【００１７】
前記ｎは５９、前記Ｃはｖ2＝ｕ5＋ｕ4＋ｕ3＋ｕ＋１であることを特徴とする。
【００１８】
前記ｎは３７、前記Ｃはｖ2 ＝ｕ7 ＋ｕ5 ＋ｕ3 ＋ｕ2 ＋ｕ＋１であることを特徴とする。
【００１９】
前記ｎは３７、前記Ｃはｖ2 ＝ｕ7 ＋ｕ6 ＋ｕ5 ＋ｕ4 ＋１であることを特徴とする。
【００２０】
前記ｎは２９、前記Ｃはｖ2 ＝ｕ9 ＋ｕ8 ＋ｕ7 ＋ｕ4 ＋ｕ3 ＋ｕ2 ＋ｕ＋１であることを特徴とする。
【００２１】
前記ｎは２９、前記Ｃはｖ2 ＝ｕ9 ＋ｕ6 ＋ｕ5 ＋ｕ3 ＋１であることを特徴とする。
【００２２】
前記ｎは２９、前記Ｃはｖ2 ＝ｕ9 ＋ｕ7 ＋ｕ5 ＋ｕ4 ＋ｕ3 ＋ｕ＋１であることを特徴とする。
【００２３】
前記ｎは２９、前記Ｃはｖ2 ＝ｕ9 ＋ｕ7 ＋ｕ6 ＋ｕ2 ＋１であることを特徴とする。
【００２４】
前記ｎは２９、前記Ｃはｖ2 ＝ｕ9 ＋ｕ7 ＋ｕ6 ＋ｕ5 ＋ｕ4 ＋ｕ3 ＋ｕ＋１であることを特徴とする。
【００２５】
この発明に係る暗号化方法は、超楕円曲線Ｃに付随する有限体Ｆ5n上のヤコビ多様体をＪ（Ｃ，Ｆ5n）とするとき、
前記ヤコビ多様体Ｊ（Ｃ，Ｆ5n）の要素の数＃Ｊ（Ｃ，Ｆ5n）が大きな素数で割り切れるように前記超楕円曲線Ｃと前記有限体Ｆ5nをとり、
前記ヤコビ多様体Ｊ（Ｃ，Ｆ5n）上定義される離散対数問題の困難さを安全性の根拠に持つことを特徴とする。
【００２６】
前記ｎは４３、前記Ｃはｖ2 ＝ｕ5 ＋ｕ2 ＋１であることを特徴とする。
【００２７】
前記ｎは２３、前記Ｃはｖ2 ＝ｕ7 ＋ｕ6 ＋ｕ2 ＋１であることを特徴とする。
【００２８】
前記ｎは１９、前記Ｃはｖ2 ＝ｕ9 ＋ｕ6 ＋ｕ4 ＋ｕ3 ＋１であることを特徴とする。
【００２９】
前記ｎは１９、前記Ｃはｖ2 ＝ｕ9 ＋ｕ7 ＋ｕ6 ＋ｕ5 ＋ｕ3 ＋ｕ＋１であることを特徴とする。
【００３０】
前記ｎは１９、前記Ｃはｖ2 ＝ｕ9 ＋ｕ8 ＋ｕ7 ＋ｕ4 ＋ｕ＋１であることを特徴とする。
【００３１】
この発明に係る暗号化方法は、超楕円曲線Ｃに付随する有限体Ｆ7n上のヤコビ多様体をＪ（Ｃ，Ｆ7n）とするとき、
前記ヤコビ多様体Ｊ（Ｃ，Ｆ7n）の要素の数＃Ｊ（Ｃ，Ｆ7n）が大きな素数で割り切れるように前記超楕円曲線Ｃと前記有限体Ｆ7nをとり、
前記ヤコビ多様体Ｊ（Ｃ，Ｆ7n）上定義される離散対数問題の困難さを安全性の根拠に持つことを特徴とする。
【００３２】
前記ｎは２９、前記Ｃはｖ2 ＝ｕ5 ＋ｕ4 ＋ｕ2 ＋１であることを特徴とする。
【００３３】
前記ｎは１９、前記Ｃはｖ2 ＝ｕ7 ＋ｕ6 ＋ｕ5 ＋ｕ3 ＋ｕ＋１であることを特徴とする。
【００３４】
前記ｎは１７、前記Ｃはｖ2 ＝ｕ9 ＋ｕ8 ＋ｕ6 ＋ｕ5 ＋ｕ3 ＋ｕ＋１であることを特徴とする。
【００３５】
【発明の実施の形態】
実施の形態１．
本発明による暗号化方法の一実施の形態を図１，図２，図３，図４に基づいて説明する。
図１は、本実施の形態による暗号化方法における鍵生成の方法を説明したフローチャートである。
図において、Ｓ１０１は本発明の特徴となる超楕円曲線Ｃと有限体Ｆq をｐ＝３又は５又は７等の３以上の小さな素数になるように選択し、ヤコビ多様体Ｊの要素Ｄを選択するステップ、Ｓ１０２は整数ｘを選択し、整数ｘを秘密鍵とするステップ、Ｓ１０３はヤコビ多様体Ｊ上でＹ＝ｘＤを計算し、Ｙを公開鍵とするステップである。
【００３６】
図２は、本実施の形態による暗号化方法を説明したフローチャートである。
図において、Ｓ２０１はデータｍと整数ｒを選択するステップで、データｍは平文ｍとも呼ばれる。Ｓ２０２はヤコビ多様体Ｊ上で、Ｃ1 ＝ｒＤとＣ2 ＝ｒＹ＋ｍを計算するステップ、Ｓ２０３はＣ1 とＣ2 の組（Ｃ1 ，Ｃ2 ）を平文ｍを暗号化した結果である暗号文とするステップである。
【００３７】
図３は、本実施の形態による復号化方法を説明したフローチャートである。
図において、Ｓ３０１は暗号文（Ｃ1 ，Ｃ2 ）と秘密鍵ｘとから、ヤコビ多様体Ｊ上でｍ＝Ｃ2 −ｘＣ1 を計算するステップで、Ｓ３０２は計算されたｍを平文とするステップである。
【００３８】
図４は、本実施の形態による暗号化方法を用いた公開鍵暗号通信を説明した図である。
図において、７０１はデータ受信装置、７０２は整数ｘ生成手段、７０３はＹ＝ｘＤ計算手段、７０４は公開鍵Ｙ出力手段、７０５は秘密鍵ｘ記憶手段、７０６は暗号文入力手段、７０７はデータｍ＝Ｃ2 −ｘＣ1 計算手段、７０８はデータ送信装置、７０９はデータ入力手段、７１０は公開鍵入力手段、７１１は整数ｒ生成手段、７１２はＣ1 ＝ｒＤとＣ2 ＝ｒＹ＋ｍを計算する計算手段、７１３は暗号文（Ｃ1 ，Ｃ2 ）生成手段、７１４は暗号文出力手段、７１５は暗号処理を管理する暗号管理装置、７１６は超楕円曲線及び有限体及びヤコビ多様体の要素Ｄを生成する生成手段、７１７は公開鍵記憶手段である。
【００３９】
次に、動作を説明する。
まず、暗号鍵生成方法を説明する。
まず、Ｓ１０１において、超楕円曲線Ｃと有限体Ｆq をｐ＝３又は５又は７等の３以上の小さな素数になるように選択し、ヤコビ多様体Ｊ（Ｃ，Ｆpn）の要素Ｄを選択する。超楕円曲線Ｃは、ｖ2 ＋ｈ（ｕ）ｖ＝ｆ（ｕ）と表される方程式で、曲線の種数をｇとすると、ｆ（ｕ）は次数２ｇ＋１のモニック多項式、ｈ（ｕ）は次数が高々ｇの多項式である。ｇは、超楕円曲線Ｃの性質を特徴付けるパラメータで種数と呼ばれる。超楕円曲線Ｃと有限体Ｆpnを決めると、それに付随するヤコビ多様体Ｊ（Ｃ，Ｆpn）が構成される。ヤコビ多様体Ｊの要素において、加法を定義することができ、この加法に関してヤコビ多様体は群をなす。ヤコビ多様体及び加法の演算方法に関しては、前述の文献に詳しく記載されている。次に、Ｓ１０２において、整数ｘを選択する。この整数ｘは、公開鍵暗号通信における秘密鍵として使用され、公開鍵暗号通信の利用者各自に秘密に保持される。
次に、Ｓ１０３において、ヤコビ多様体Ｊ上で、Ｙ＝ｘＤを計算する。計算されたＹは、公開鍵暗号通信において公開鍵として使用され、公開鍵Ｙは秘密に保持する必要はなく、一般に公開される。
【００４０】
次に、データの暗号化方法を説明する。
まず、Ｓ２０１において、暗号化したいデータｍと整数ｒを選択する。次に、Ｓ２０２において、Ｓ１０１において選択されたヤコビ多様体Ｊ上で、Ｊの要素Ｄと公開鍵Ｙを用いて、Ｃ1 ＝ｒＤとＣ2 ＝ｒＹ＋ｍを計算する。Ｓ２０３において、Ｃ1 とＣ2 の組（Ｃ1 ，Ｃ2 ）を暗号文とした生成する。
このように、暗号文は公開鍵Ｙを用いて生成される。
【００４１】
次に、データの復号化方法を説明する。
まず、Ｓ３０１において、暗号文（Ｃ1 ，Ｃ2 ）と、秘密に保持された秘密鍵ｘとから、Ｓ１０１において、生成されたヤコビ多様体Ｊ上でｍ＝Ｃ2 −ｘＣ1 を計算する。Ｓ３０２において、これを平文ｍとする。
【００４２】
次に、以上で説明した、鍵生成方法、暗号化方法、復号化方法を用いて実際に公開鍵暗号通信を行う方法を図４に基づいて説明する。
データ送信装置７０８からデータ受信装置７０１へデータが送信される。また、暗号管理装置７１５では暗号通信に使用されるシステム全体の共通パラメータである超楕円曲線Ｃ及び有限体Ｆpn及びヤコビ多様体Ｊの要素Ｄが生成され、更に、データ暗号化に使用される公開鍵Ｙの管理が行われる。公開鍵Ｙは、システムの利用者全員が利用できるように公開される。但し、秘密鍵ｘは、利用者各自が秘密に保持しておかなくてはならない。
【００４３】
まず、暗号管理装置７１５でシステム全体のパラメータを生成する。生成手段７１６において、超楕円曲線Ｃと有限体Ｆq とヤコビ多様体ＪとＪの要素Ｄを生成する。これらのパラメータは、前述のように、ヤコビ多様体Ｊの要素の数が大きな素数で割り切れるように設定する。
【００４４】
図５は、生成手段７１６の構成図である。
生成手段７１６は、メモリ１０と回路部２０から構成されている。メモリ１０は、素数ｐレジスタ１４と種数ｇレジスタ１５と目安整数Ｋレジスタ１２と最大素因数レジスタ１３から構成されている。回路部２０は、超楕円曲線Ｃ生成部３０とヤコビ多様体Ｊの要素Ｄ生成部２５から構成されている。超楕円曲線Ｃ生成部３０は、素数ｐ決定部２４と種数ｇ決定部２１と拡大次数ｎ決定部２２と超楕円曲線Ｃ決定部２３とから構成されている。
【００４５】
素数ｐレジスタ１４は、超楕円曲線Ｃの探索を試みる３以上の小さな素数を１つ以上記憶するレジスタである。種数ｇレジスタ１５は、超楕円曲線Ｃの探索を試みる２以上の小さな整数を１つ以上記憶するレジスタである。目安整数Ｋレジスタ１２は、安全性の目安となるヤコビ多様体Ｊの要素数＃Ｊの最大素因数の大きさを記憶するレジスタである。最大素因数レジスタ１３は、最大素因数を記憶するレジスタである。
素数ｐレジスタ１４に記憶される素数は、予めｐ＝３，５，７という値が設定されているものとする。種数ｇレジスタ１５に記憶される整数は、予めｇ＝２，３，４，５，６という値が設定されているものとする。目安整数Ｋレジスタ１２に記憶される整数も予めＫ＝２160 という値が設定されているものとする。
【００４６】
まず、回路部２０の動作の概略を説明する。
安全な暗号通信を行うためのヤコビ多様体Ｊ（Ｃ，Ｆq ）は、ヤコビ多様体の要素数＃Ｊを素因数分解した際の最大素因数の大きさが、大きくなければならない。本実施の形態では、２160 以上であればよいとしている。ヤコビ多様体は、超楕円曲線Ｃの方程式と、有限体Ｆq を決めれば一意に決まり、要素数＃Ｊも一意に決まる。つまり、超楕円曲線Ｃと有限体Ｆq を適切に（ヤコビ多様体の要素数＃Ｊの最大素因数が大きくなるように）決めることが必要である。本実施の形態では、ｑはｐのべき乗ｐn に設定し、かつ、ｐをできるだけ小さな素数にすることがＦpnを決める上での制約条件である（なお、Ｆpnのｎのことを数学では“拡大次数”と呼ぶ）。
ヤコビ多様体の要素数＃Ｊは、だいたいｑg （＝ｐng）の大きさとなる。つまり、有限体Ｆpnの拡大次数ｎと、超楕円曲線Ｃの種数ｇ（超楕円曲線の次数は２ｇ＋１となる）を決めれば、ヤコビ多様体の要素数＃Ｊの大きさはだいたい決まる。ここで重要なのは、ヤコビ多様体の要素数＃Ｊの大きさがだいたい決まる（だいたいｐngになる）ということで、正確なヤコビ多様体の要素数＃Ｊの値は、ｐng前後の値をとるということである。結果として、拡大次数ｎと種数ｇが同じでも超楕円曲線Ｃの方程式を変えると、ヤコビ多様体の要素数＃Ｊの大きさはだいたい同じであっても、ヤコビ多様体の要素数＃Ｊの最大素因数の大きさは全く異なる。
例えば、仮に、ｐng＝１００になったとすると、超楕円曲線Ｃのとり方によってヤコビ多様体の要素数＃Ｊは、１０２になったり、９９になったりする。１０２＝２×５１，９９＝３×３×１１であるから、ヤコビ多様体の要素数＃Ｊの最大素因数は、それぞれ５１，１１となり、暗号として好ましいのはヤコビ多様体の要素数＃Ｊ＝１０２になる超楕円曲線Ｃの方ということになる。
従って、ヤコビ多様体Ｊの生成手順は、まず、素数ｐと種数ｇと拡大次数ｎを決めておいて、超楕円曲線Ｃの方程式をいろいろ変えてヤコビ多様体の要素数＃Ｊとその最大素因数を計算し、最大素因数が安全性を決めるパラメータ（目安整数Ｋ、Ｋ＝２160 ）よりも大きくなる超楕円曲線Ｃが得られたら終了とする。
種数ｇと拡大次数ｎは、ヤコビ多様体の要素数＃Ｊの大きさはだいたいｐng前後なので、ｐng＞Ｋ（＝２160 ）になるようにしておけばよい。なぜなら、ヤコビ多様体の要素数＃Ｊの最大素因数の大きさは、必ずヤコビ多様体の要素数＃Ｊより小さくなり、ヤコビ多様体の要素数＃Ｊがヤコビ多様体の要素数＃Ｊに近い大きさの最大素因数を持つようなヤコビ多様体Ｊを得ることを期待するからである。種数ｇは、小さい方が暗号化速度が速いので、２以上の最小の整数ｇから超楕円曲線Ｃの探索を開始する。拡大次数ｎは、ｐng＞Ｋ（＝２160 ）を満たす最小整数値とする。
【００４７】
次に、回路部２０の動作を図５，図６を用いて詳細に説明する。
図６は、図１に示したＳ１０１の詳細なフローチャート図である。
素数ｐ決定部２４は、Ｓ１２において、素数ｐレジスタ１４から最小の素数を取得する。種数ｇ決定部２１は、Ｓ１３において、種数ｇレジスタ１５から最小の整数を取得する。例えば、ここでは、ｐ＝３，ｇ＝２が取得されたものとする。
次に、拡大次数ｎ決定部２２は、目安整数Ｋレジスタ１２から目安整数Ｋを取得する。ここでは、目安整数Ｋ＝２160 とする。次に、拡大次数ｎ決定部２２は、Ｓ１４において、拡大次数ｎを計算する。Ｋ＜２N(g)を満足する最小の整数である。この例においては、２160 ＜（ｐn ）g ＝（３n ）2 から、拡大次数ｎが求められる。こうして有限体Ｆq ＝Ｆpnが決定する。
超楕円曲線Ｃ決定部２３は、Ｓ１５において、種数ｇから超楕円曲線Ｃの次数を計算する。次数は、２ｇ＋１である。超楕円曲線Ｃ決定部２３は、この次数を持つ超楕円曲線Ｃを１つ生成する。超楕円曲線Ｃ決定部２３は、超楕円曲線の方程式を満足し、かつ、種数ｇから計算された次数を満足する超楕円曲線Ｃを生成する。この際、いろいろな超楕円曲線Ｃが考えられるが、とりあえず、ある１つの超楕円曲線Ｃを生成するものとする。超楕円曲線Ｃ決定部２３は、所定のアルゴリズムに基づき、種数ｇから計算された次数を満足する全ての超楕円曲線Ｃを順に生成するものとする。
次に、超楕円曲線Ｃ決定部２３は、超楕円曲線Ｃと有限体Ｆpnとから要素数＃Ｊを計算する。この要素数＃Ｊの計算は、既に知られている計算方法を用いることにより、ある１つの要素数＃Ｊが計算される。次に、超楕円曲線Ｃ決定部２３は、要素数＃Ｊを素因数分解し、素因数分解された素因数の内、最大の素因数を最大素因数レジスタ１３に記憶する。もし、この最大素因数の値が目安整数Ｋよりも大きな値なら、生成した超楕円曲線Ｃを求めたかった超楕円曲線Ｃとして決定する。もし、この最大素因数の値が目安整数Ｋよりも小さな値なら、Ｓ１５に戻り別な超楕円曲線Ｃを生成して、Ｓ１６，Ｓ１７を繰り返す。最大素因数レジスタ１３は、これらの繰り返し処理の中で生じる最大素因数の最大の値を保持するものとする。
もし、超楕円曲線Ｃを変えても、最大素因数の値が目安整数Ｋよりも大きな値をとらない場合は、Ｓ１３に戻りｇ＝２の次に小さな種数ｇを取得し（即ち、ｇ＝３として）、Ｓ１４からＳ１７を実行する。もし、それでも、この最大素因数の値が目安整数Ｋよりも大きな値をとらない場合は、Ｓ１３において、更に大きな値の種数ｇ（ｇ＝４，５，６）を取得してＳ１４からＳ１７を繰り返す。最大素因数レジスタ１３は、これらの繰り返し処理の中で生じる最大素因数の最大の値を保持するものとする。
もし、これらの繰り返し処理により最大素因数の値が目安整数Ｋよりも大きな値をとらない場合は、Ｓ１２に戻り、ｐ＝３の次に小さな素数ｐを取得し（即ち、ｐ＝５として）、Ｓ１３からＳ１７を実行する。もし、それでも、この最大素因数の値が目安整数Ｋよりも大きな値をとらない場合は、Ｓ１２において、更に大きな値の素数ｐ（ｐ＝７）を取得し、Ｓ１３からＳ１７を繰り返す。最大素因数レジスタ１３は、これらの繰り返し処理の中で生じる最大素因数の最大の値を保持するものとする。
もし、これらの繰り返し処理により最大素因数の値が目安整数Ｋよりも大きな値をとらない場合は、超楕円曲線Ｃの生成の失敗を報告する。又は、安全性は満たさないという警告を発しながら、最大素因数レジスタ１３に記憶された最大素因数の中の最大の値を生成した超楕円曲線Ｃを取り敢えず選択する。
超楕円曲線Ｃが決定したら、次に、ヤコビ多様体Ｊの要素Ｄ生成部２５は、Ｓ１８において、最大素因数レジスタ１３に記憶された最大素因数を位数として持つ、ヤコビ多様体Ｊの要素Ｄを選択して出力する。また、有限体Ｆq と超楕円曲線Ｃを出力する。以上が、生成手段７１６の動作である。
【００４８】
次に、データ受信装置７０１における整数ｘ生成手段７０２で整数ｘが生成される。このｘが、データ復号の際に使用される秘密鍵ｘとなる。秘密鍵ｘは、秘密鍵ｘ記憶手段７０５において秘密に保持し、他の暗号通信利用者に知られないようにしておく。次に、７０３において、秘密鍵ｘに対応する公開鍵Ｙ＝ｘＤを計算する。ヤコビ多様体の要素Ｄは、暗号管理装置７１５から受け取ったものを使用する。計算された公開鍵Ｙは、公開鍵Ｙ出力手段７０４から暗号管理装置７１５へ送信され、公開鍵Ｙを暗号管理装置７１５が管理しておく。
以上で、データ送信装置７０８がデータ受信装置７０１へデータを送信するための前準備が終了する。
【００４９】
次に、データ送信装置７０８でデータを暗号化する処理を行う。まず、データ入力手段７０９に暗号化したいデータｍが入力される。次に、公開鍵入力手段７１０に、暗号管理装置７１５の公開鍵記憶手段７１７から公開鍵Ｙを入力する。次に、整数ｒ生成手段７１１において、整数ｒを生成する。次に、計算手段７１２において、データｍの暗号化処理を行う。計算手段７１２では、Ｃ1 ＝ｒＤとＣ2 ＝ｒＹ＋ｍが計算される。計算されたＣ1 とＣ2 の組を、暗号文（Ｃ1 ，Ｃ2 ）生成手段７１３において（Ｃ1 ，Ｃ2 ）として暗号文とする。生成された暗号文を暗号文出力手段７１４からデータ受信装置７０１へ出力する。
【００５０】
次に、データ送信装置７０８から送信された暗号文をデータ受信装置７０１で復号する処理を説明する。
まず、暗号文（Ｃ1 ，Ｃ2 ）が暗号文入力手段７０６へ入力される。入力された暗号文（Ｃ1 ，Ｃ2 ）は、予め保持されていた秘密鍵ｘを用いて、７０７において、ｍ＝Ｃ2 −ｘＣ1 を計算することにより、もとの平文ｍに復号される。
【００５１】
以上のように、データを公開鍵暗号通信によって送信すれば、秘密鍵ｘを知っているデータ受信者のみが暗号文を平文ｍに復号できるため、安全な秘密通信を行うことができる。
また、超楕円曲線Ｃに付随するヤコビ多様体Ｊの群で構成される離散対数問題を解く難しさに安全性の根拠をおいているので、安全な秘密通信を行うことができる。また、高速な暗号化復号化処理を行うことができる。
【００５２】
本実施の形態１では、公開鍵Ｙは管理装置を介してデータ送信装置に送られたが、データ受信装置から直接データ送信装置へ送ってもよい。
【００５３】
この実施の形態の大きな特徴は、ある一定の暗号の安全性を確保する場合に、即ち、ｑg ＝ｐngを一定とする場合に、素数ｐを小さくすれば、処理速度が速くなるという超楕円曲線Ｃの特性に着目したものである。更に、種数ｇを小さくすれば、処理速度が速くなるという超楕円曲線Ｃの特性に着目したものである。
【００５４】
また、上記図６のＳ１５においては、超楕円曲線Ｃを１つだけ選択したが、複数の超楕円曲線Ｃを選択して、選択した複数の超楕円曲線Ｃに対して並列的にＳ１５からＳ１７までの演算を行っても構わない。
また、上記図６のＳ１４において、Ｋ＜ｐngを満足する最小の素数を選択したが、最小より大きな素数を選択しても構わない。
また、Ｓ１７において、最大素因数が安全性を決めるパラメータ（目安整数Ｋ、Ｋ＝２160 ）よりも大きくなる超楕円曲線Ｃが得られたら処理終了としたが、そのままＳ１２からＳ１７を繰り返し、ｐ＝７まで、かつ、ｇ＝６までの全てのケースについて超楕円曲線Ｃを探索してもよい。
【００５５】
また、目安整数Ｋレジスタ１２に、暗号通信に要求される安全性に対応して、複数の目安整数Ｋを記憶できるようにしても構わない。
【００５６】
以下に、ｐとｇを変化させて超楕円曲線を検索した実施例を示す。
【００５７】
実施例１．
有限体をＦ359 、超楕円曲線をＣ：ｖ2 ＝ｕ5 ＋ｕ4 ＋ｕ3 ＋ｕ＋１とすれば、ヤコビ多様体Ｊ（Ｃ，Ｆ359 ）の要素数は、
＃Ｊ（Ｃ，Ｆ359 ）＝１９９６６７８１１１０１６０２３００６６５６０１８４２０９２８８７９０６９８１６９９２４７７８９３４３５２４８８５
＝５×３９９３３５６２２２０３２０４６０１３３１２０３６８４１８５７７５８１３９６３３９８４９５５７８６８７０４９７７
となり、１８５ビットの素数３９９３３５６２２２０３２０４６０１３３１２０３６８４１８５７７５８１３９６３３９８４９５５７８６８７０４９７７で割り切れるため、安全である。
また、暗号化／復号化の演算は、有限体上で行われるためｐ＞２の拡大体Ｆpnを用いる場合、ｐが小さい方が高速であるが、本実施例では、ｐ＝３としているため高速処理が可能である。
【００５８】
実施例２．
有限体をＦ337 、超楕円曲線をＣ：ｖ2 ＝ｕ7 ＋ｕ5 ＋ｕ3 ＋ｕ2 ＋ｕ＋１とすれば、ヤコビ多様体Ｊ（Ｃ，Ｆ337 ）の要素数は、
＃Ｊ（Ｃ，Ｆ337 ）＝９１２９７５８１４０８８２７４３３７２８１２３１４３１１１０２０１８１３５６４７９０４０６９６１７２１９５
＝５×７×２６０８５０２３２５９６６４９８１０６５１７８０４０８８８８６２９０８９５８９９４０１１６２７４７７７７
となり、１７１ビットの素数２６０８５０２３２５９６６４９８１０６５１７８０４０８８８８６２９０８９５８９９４０１１６２７４７７７７で割り切れるため、安全な暗号通信が行える。
また、暗号化／復号化の演算は有限体上で行われるためｐ＞２の拡大体Ｆpnを用いる場合、ｐが小さい方が高速であるが、本実施例では、ｐ＝３としているため高速処理が可能である。
【００５９】
実施例３．
有限体をＦ337 、超楕円曲線をＣ：ｖ2 ＝ｕ7 ＋ｕ6 ＋ｕ5 ＋ｕ4 ＋１とすれば、ヤコビ多様体Ｊ（Ｃ，Ｆ337 ）の要素数は、
＃Ｊ（Ｃ，Ｆ337 ）＝９１２９７５８２０２９８２６６２５５４２３４８８５３９６４２２４７２５３６４３５３１４３０７０３２６０１１
＝４７×１４９×１３０３６９２４４６５２０４４３０３２１６２６２８２１５９６７７９５５９２８０８１２７１３２２３３７
となり、１６４ビットの素数１３０３６９２４４６５２０４４３０３２１６２６２８２１５９６７７９５５９２８０８１２７１３２２３３７で割り切れるため、安全な暗号通信が行える。
【００６０】
実施例４．
有限体をＦ329 、超楕円曲線をＣ：ｖ2 ＝ｕ9 ＋ｕ8 ＋ｕ7 ＋ｕ4 ＋ｕ3 ＋ｕ2 ＋ｕ＋１とすれば、ヤコビ多様体Ｊ（Ｃ，Ｆ329 ）の要素数は、
＃Ｊ（Ｃ，Ｆ329 ）＝２２１８５３１３７４３４５４３７７６５３５５４７３７７７９７７８１０３３８０１６８５７４８４０５１４１９７５５９
＝１３７×１６１９３６５９６６６７５５０２０１８５０７６４５０９３４１４４６０１００７４２２３１７４０１８３５１８０７
となり、１７７ビットの素数１６１９３６５９６６６７５５０２０１８５０７６４５０９３４１４４６０１００７４２２３１７４０１８３５１８０７で割り切れるため、安全な暗号通信が行える。
【００６１】
実施例５．
有限体をＦ329 、超楕円曲線をＣ：ｖ2 ＝ｕ9 ＋ｕ6 ＋ｕ5 ＋ｕ3 ＋１とすれば、ヤコビ多様体Ｊ（Ｃ，Ｆ329 ）の要素数は、
＃Ｊ（Ｃ，Ｆ329 ）＝２２１８５３０１０５２０３３８９３２５２１３４８２５５２３３０１７８３６０７７３８５９７８８０６６１２６７６８６
＝２×４３×２５７９６８６１６８８４１１５０３７８１５５２１２２７０１５１３７０１８６９４６３４８５９０７７４５６６０１
となり、１７８ビットの素数２５７９６８６１６８８４１１５０３７８１５５２１２２７０１５１３７０１８６９４６３４８５９０７７４５６６０１で割り切れるため、安全な暗号通信が行える。
【００６２】
実施例６．
有限体をＦ329 、超楕円曲線をＣ：ｖ2 ＝ｕ9 ＋ｕ7 ＋ｕ5 ＋ｕ4 ＋ｕ3 ＋ｕ＋１とすれば、ヤコビ多様体Ｊ（Ｃ，Ｆ329 ）の要素数は、
＃Ｊ（Ｃ，Ｆ329 ）＝２２１８５３１４２３４５７１２５４５３２８９８２４４３８８２９４７８６０８８７４６９８７９５９７２２９８４７８６
＝２×５３×２０９２９５４１７３０７２７５９８６１５９４１７３９９８８９５７３４５３６６７４２４４１４７１４３６７７８１
となり、１７８ビットの素数２０９２９５４１７３０７２７５９８６１５９４１７３９９８８９５７３４５３６６７４２４４１４７１４３６７７８１で割り切れるため、安全な暗号通信が行える。
【００６３】
実施例７．
有限体をＦ329 、超楕円曲線をＣ：ｖ2 ＝ｕ9 ＋ｕ7 ＋ｕ6 ＋ｕ2 ＋１とすれば、ヤコビ多様体Ｊ（Ｃ，Ｆ329 ）の要素数は、
＃Ｊ（Ｃ，Ｆ329 ）＝２２１８５３１０８５４９４３９２１０４７９４９２３５２８８６９３５２８２８９２９４８９８１４４３６８３７１７６３
＝３×３７×１９９８６７６６５３５９８５５１４４５７６１１９２３６８３５０７６８３１４３５０８９１７２４７１７８７１３３
となり、１７８ビットの素数１９９８６７６６５３５９８５５１４４５７６１１９２３６８３５０７６８３１４３５０８９１７２４７１７８７１３３で割り切れるため、安全な暗号通信が行える。
【００６４】
実施例８．
有限体をＦ329 、超楕円曲線をＣ：ｖ2 ＝ｕ9 ＋ｕ7 ＋ｕ6 ＋ｕ5 ＋ｕ4 ＋ｕ3 ＋ｕ＋１とすれば、ヤコビ多様体Ｊ（Ｃ，Ｆ329 ）の要素数は、
＃Ｊ（Ｃ，Ｆ329 ）＝２２１８５３０９０５１８１９０３０９４４７７４１２６８４２７３８５９１５３６２９５９３５５４２４８１９０８９１５
＝５×１９×２３３５２９５６８９６６５１６１１５２０８１４８７０３６０７７７４６４７７５０４８３５３２０２６１２５３５７
となり、１７８ビットの素数２３３５２９５６８９６６５１６１１５２０８１４８７０３６０７７７４６４７７５０４８３５３２０２６１２５３５７で割り切れるため、安全な暗号通信が行える。
【００６５】
実施例９．
有限体をＦ543 、超楕円曲線をＣ：ｖ2 ＝ｕ5 ＋ｕ2 ＋１とすれば、ヤコビ多様体Ｊ（Ｃ，Ｆ543 ）の要素数は、
＃Ｊ（Ｃ，Ｆ543 ）＝１２９２４６９７０７１１４１０２６９２１１４６８１５６９４６３８９５２６４２１４７９６２４４７９９６０４１１５６９３０６０＝２×２×５×６４６２３４８５３５５７０５１３４６０５７３４０７８４７３１９４７６３２１０７３９８１２２３９９８０２０５７８４６５３
となり、１９６ビットの素数６４６２３４８５３５５７０５１３４６０５７３４０７８４７３１９４７６３２１０７３９８１２２３９９８０２０５７８４６５３で割り切れるため、安全な暗号通信が行える。
【００６６】
実施例１０．
有限体をＦ523 、超楕円曲線をＣ：ｖ2 ＝ｕ7 ＋ｕ6 ＋ｕ2 ＋１とすれば、ヤコビ多様体Ｊ（Ｃ，Ｆ523 ）の要素数は、
＃Ｊ（Ｃ，Ｆ523 ）＝１６９４０６５８７１０２９１７９３７０７６９０３５９０６７６５８１４４２９９５２１７７８３０１９３
＝３×４３×１３１３２２９３５７３８６９６０７５２５３４１３６３６１８３３９６４６７４３８１５３３２０１７
となり、１５４ビットの素数１３１３２２９３５７３８６９６０７５２５３４１３６３６１８３３９６４６７４３８１５３３２０１７で割り切れるため、安全な暗号通信が行える。
【００６７】
実施例１１．
有限体をＦ519 、超楕円曲線をＣ：ｖ2 ＝ｕ9 ＋ｕ6 ＋ｕ4 ＋ｕ3 ＋１とすれば、ヤコビ多様体Ｊ（Ｃ，Ｆ519 ）の要素数は、
＃Ｊ（Ｃ，Ｆ519 ）＝１３２３４８９４７５７７０７７６８６１２１７２５２７２８２４９９６１８６２７２７９３１８１９５２４４８１７４
＝２×９６７×６８４３２７５４６９３４２１７６１１７９７９５９０１１５０４６３３８４８３５９８４０６５１２５３６１
となり、１６６ビットの素数６８４３２７５４６９３４２１７６１１７９７９５９０１１５０４６３３８４８３５９８４０６５１２５３６１で割り切れるため、安全な暗号通信が行える。
【００６８】
実施例１２．
有限体をＦ519 、超楕円曲線をＣ：ｖ2 ＝ｕ9 ＋ｕ7 ＋ｕ6 ＋ｕ5 ＋ｕ3 ＋ｕ＋１とすれば、ヤコビ多様体Ｊ（Ｃ，Ｆ519 ）の要素数は、
＃Ｊ（Ｃ，Ｆ519 ）＝１３２３４９０１１０６９３９５３４６８６４６１６４１８４４７４８１８８４９９４１７１４９１５７８５９６８３７
＝３×１５１×２９２１６１１７２３３８６２１０７４７５６３２７６３４５４１９０２６１５８８１１７３２７０５９２９２９
となり、１６８ビットの素数２９２１６１１７２３３８６２１０７４７５６３２７６３４５４１９０２６１５８８１１７３２７０５９２９２９で割り切れるため、安全な暗号通信が行える。
【００６９】
実施例１３．
有限体をＦ519 、超楕円曲線をＣ：ｖ2 ＝ｕ9 ＋ｕ8 ＋ｕ7 ＋ｕ4 ＋ｕ＋１とすれば、ヤコビ多様体Ｊ（Ｃ，Ｆ519 ）の要素数は、
＃Ｊ（Ｃ，Ｆ519 ）＝１３２３４９０７４８７２５９３５７３１１６４６６２５３２８１３０５５０１９８１０５２２３６１０９５６１６７３
＝１７×７３×１０６６４７１１９１５５９９８０４４４１２９４６２１５３７５７４９８００１４５８９２２１２８１９９５３
となり、１６７ビットの素数１０６６４７１１９１５５９９８０４４４１２９４６２１５３７５７４９８００１４５８９２２１２８１９９５３で割り切れるため、安全な暗号通信が行える。
【００７０】
実施例１４．
有限体をＦ729 、超楕円曲線をＣ：ｖ2 ＝ｕ5 ＋ｕ4 ＋ｕ2 ＋１とすれば、ヤコビ多様体Ｊ（Ｃ，Ｆ729 ）の要素数は、
＃Ｊ（Ｃ，Ｆ729 ）＝１０３６７７９３０７６３３７１８５７３７０５４２６５３６９２７５０６７０３４７６００３９２４５７７９
＝７９×１３１２３７８８７０４２２４２８５７４３１０６６６５０２４３９８８１９０３１３４１８２１８３０１
となり、１５７ビットの素数１３１２３７８８７０４２２４２８５７４３１０６６６５０２４３９８８１９０３１３４１８２１８３０１で割り切れるため、安全な暗号通信が行える。
【００７１】
実施例１５．
有限体をＦ719 、超楕円曲線をＣ：ｖ2 ＝ｕ7 ＋ｕ6 ＋ｕ5 ＋ｕ3 ＋ｕ＋１とすれば、ヤコビ多様体Ｊ（Ｃ，Ｆ719 ）の要素数は、
＃Ｊ（Ｃ，Ｆ719 ）＝１４８１１１３３１９５２８９１０６２５１９４１７１８５４５５４０８８６２４３３６１６２９８０９８４
＝２×２×２×４１×４５１５５８９３８８８０７６５４３４５１０４１８２４８３３９６６１１６５９５６１４７２５０３
となり、１５２ビットの素数４５１５５８９３８８８０７６５４３４５１０４１８２４８３３９６６１１６５９５６１４７２５０３で割り切れるため、安全な暗号通信が行える。
【００７２】
実施例１６．
有限体をＦ717 、超楕円曲線をＣ：ｖ2 ＝ｕ9 ＋ｕ8 ＋ｕ6 ＋ｕ5 ＋ｕ3 ＋ｕ＋１とすれば、ヤコビ多様体Ｊ（Ｃ，Ｆ717 ）の要素数は、
＃Ｊ（Ｃ，Ｆ717 ）＝２９２８６４５５３０８４５９１９０７３８７８６６９９５０３１５２９０９８４０６７３０６４０５９７１６９６７２５８７２
＝２×２×２×２×９７×１８８７０１３８７２９６７７３１３６２０３５２２５４８３４５０５７４０８７６７２２３３５０９００２３８１９１１
となり、１８１ビットの素数１８８７０１３８７２９６７７３１３６２０３５２２５４８３４５０５７４０８７６７２２３３５０９００２３８１９１１で割り切れるため、安全な暗号通信が行える。
【００７３】
【発明の効果】
以上のように、本発明によれば、離散対数問題を構成するヤコビ多様体Ｊの要素数＃Ｊの最大素因数が大きいので、安全な暗号通信を行うことができる。
また、本発明によれば、ヤコビ多様体Ｊにおける有限体Ｆq がｐ＞２の拡大体Ｆpnのとき、ｐが小さいので、また、ｇが小さいので、高速に暗号化復号化できる。
【図面の簡単な説明】
【図１】  本発明の暗号化方法を説明するフローチャート図である。
【図２】  本発明の暗号化方法を説明するフローチャート図である。
【図３】  本発明の暗号化方法を説明するフローチャート図である。
【図４】  本発明の暗号化方式を説明する図である。
【図５】  本発明の生成手段７１６の構成図である。
【図６】  本発明の生成手段７１６の動作フローチャート図である。
【図７】  従来の暗号化方法を説明するフローチャート図である。
【図８】  従来の暗号化方法を説明するフローチャート図である。
【図９】  従来の暗号化方法を説明するフローチャート図である。
【符号の説明】
１０  メモリ、１２  目安整数Ｋレジスタ、１３  最大素因数レジスタ、１４素数ｐレジスタ、１５  種数ｇレジスタ、２０  回路部、２１  種数ｇ決定部、２２  拡大次数ｎ決定部、２３  超楕円曲線Ｃ決定部、２４  素数ｐ決定部、２５  ヤコビ多様体Ｊの要素Ｄ生成部、３０  超楕円曲線Ｃ生成部。
【図１】
0004237306.tif 000002
【図２】
0004237306.tif 000003
【図３】
0004237306.tif 000004
【図４】
0004237306.tif 000005
【図５】
0004237306.tif 000006
【図６】
0004237306.tif 000007
【図７】
0004237306.tif 000008
【図８】
0004237306.tif 000009
【図９】
0004237306.tif 000010