(57)【特許請求の範囲】
【請求項１】
超楕円曲線Ｃに付随する有限体Ｆq 上のヤコビ多様体をＪ（Ｃ，Ｆq ）とするとき、
ＣＰＵビット幅Ｎと、暗号の安全性の目安となる目安整数Ｋとに基づいて、Ｋ＜２Ｎｇを満たす最小の整数を種数ｇとして計算することにより、ＣＰＵビット幅Ｎを拡大次数ｎとして選択した場合に、ヤコビ多様体Ｊ（Ｃ，Ｆq ）の要素数＃Ｊ（Ｃ，Ｆq ）が目安整数Ｋよりも多くなる超楕円曲線Ｃを構成可能な種数ｇを計算する種数ｇ計算部と、
ＣＰＵビット幅Ｎ以下の素数であって、上位３つの素数の少なくともいずれかの素数を拡大次数ｎとして選択する拡大次数ｎ選択部と、
種数ｇから次数を決定して超楕円曲線Ｃを順次生成するとともに、選択された拡大次数ｎに基づく有限体Ｆq と上記超楕円曲線Ｃとからヤコビ多様体Ｊ（Ｃ，Ｆq ）の要素数＃Ｊ（Ｃ，Ｆq ）を計算し、最大の素因数を求め、最大の素因数が暗号の安全性の目安となる目安整数Ｋ以上となるような超楕円曲線Ｃを選択する超楕円曲線Ｃ決定部と
を備え、
上記種数ｇ計算部は、上記超楕円曲線Ｃ決定部が目安整数Ｋより大きな値を持つ最大の素因数を求められないとき、種数ｇの値を大きくする
ことを特徴とする暗号管理装置。
【請求項２】
上記ヤコビ多様体Ｊ（Ｃ，Ｆq ）の要素数＃Ｊ（Ｃ，Ｆq ）が大きな素数で割り切れるように上記超楕円曲線Ｃと上記有限体Ｆq をとり、
上記ヤコビ多様体Ｊ（Ｃ，Ｆq ）における演算が、多倍長精度演算を必要としない通常の整数演算で行うことができることを特徴とするとともに、上記ヤコビ多様体Ｊ（Ｃ，Ｆq ）上定義される離散対数問題の困難さを安全性の根拠に持つことを特徴とする超楕円曲線を用いた請求項１記載の暗号管理装置。
【請求項３】
上記種数ｇは、６以上であることを特徴とする請求項１又は２に記載の暗号管理装置。
【請求項４】
上記有限体Ｆq の要素の数ｑは、２32以下であることを特徴とする請求項１から３までのいずれかに記載の暗号管理装置。
【請求項５】
上記有限体Ｆq の要素の数ｑは、２16以下であることを特徴とする請求項１から３までのいずれかに記載の暗号管理装置。
【請求項６】
上記超楕円曲線Ｃは、ｖ2 ＋ｖ＝ｕ13＋ｕ11＋ｕ7＋ｕ3 ＋１であり、上記有限体Ｆq は、Ｆ229 であることを特徴とする請求項４記載の暗号管理装置。
【請求項７】
上記超楕円曲線Ｃは、ｖ2 ＋ｖ＝ｕ13＋ｕ11＋ｕ9＋ｕ5 ＋１であり、上記有限体Ｆq は、Ｆ229 であることを特徴とする請求項４記載の暗号管理装置。
【請求項８】
上記超楕円曲線Ｃは、ｖ2 ＋ｖ＝ｕ31であり、上記有限体Ｆq は、Ｆ213であることを特徴とする請求項５記載の暗号管理装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、ディジタル情報を暗号化して安全に暗号通信する技術に関する。
【０００２】
【従来の技術】
従来の超楕円曲線を用いた暗号化方法について説明する。
従来の超楕円曲線を用いた暗号化方法には、Ｎｅａｌ  Ｋｏｂｌｉｔｚ著，“Ｈｙｐｅｒｅｌｌｉｐｔｉｃ  Ｃｒｙｐｔｏｓｙｓｔｅｍｓ”，Ｊ．Ｃｒｙｐｔｏｌｏｇｙ  Ｖｏｌ．１，（１９８９），ｐｐ１３９−１５０がある。また、公開鍵暗号及び離散対数問題については、岡本龍明、太田和夫著、“暗号ゼロ知識証明数論”、共立出版（１９９５）に記載されている。
【０００３】
まず、本発明の技術的背景である公開鍵暗号、離散対数問題、超楕円曲線及びヤコビ多様体について簡単に説明する。
公開鍵暗号通信においては、利用者毎に秘密鍵ｘと公開鍵Ｙの組が用意され、秘密鍵ｘは、各利用者が秘密に保持しておく。公開鍵Ｙは、利用者自身以外の一般に公開する。利用者Ｂが利用者Ａに秘密にデータを送りたい時は、利用者Ｂは、利用者Ａに対応する公開鍵Ｙを用いてデータを暗号化する。この暗号文は、秘密鍵ｘを知る利用者Ａにしか復号できない。
離散対数問題とは群Ｇの２つの要素ｇ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 とすると、計算機上ではｎビットの整数として表現される。また、暗号が安全であるためには、ヤコビ多様体Ｊ（Ｃ，Ｆq ）の要素数＃Ｊの大きさは、２160 程度なければならない。＃Ｊは、曲線の種数をｇとすると、ｑg 程度であることから、従来のようにｇ＝２の場合、十分安全な暗号化方法を得るためには、有限体Ｆq の要素数ｑは、ｑg ＝２160 ＝（２80）2 となり、ｑ＝２80程度の大きさが必要であった。つまり、従来の有限体Ｆq の要素は、計算機上では８０ビット程度の大きさの整数として表現されていた。従って、パーソナルコンピュータ等の３２ビットＣＰＵ（セントラル・プロセッシング・ユニット）を持つ計算機や、ＩＣ（インテグレーテッド・サーキット）カード等の１６ビットＣＰＵを持つ計算機では、有限体Ｆq の演算を行うためには、“多倍長演算”と呼ばれる技術が必要であった。多倍長演算は、通常の整数演算よりも、演算速度が遅くなるという問題がある。
【０００９】
【発明が解決しようとする課題】
従来の超楕円曲線を用いた暗号化方法は、以上のように構成されているため、安全な暗号化方法を得るためには、有限体上の演算を多倍長演算を用いて行わなければならず、暗号化及び復号化の速度が遅くなるという課題があった。
この暗号化及び復号化の速度が遅くなるという課題があるため、超楕円曲線を用いた暗号化方法は、研究レベルの段階であり、現在のところ実用化されていないという課題があった。
【００１０】
本発明の目的は、係る課題を解決するためになされたもので、ヤコビ多様体Ｊ（Ｃ，Ｆq ）の有限体Ｆq の要素数ｑを小さくし、多倍長演算を必要としない通常の整数演算で高速に暗号化及び復号化を行うことができ、かつ、安全な暗号を得ることにある。即ち、本発明の目的は、超楕円曲線を用いた暗号処理の実用的速度の達成を目的とする。
【００１１】
【課題を解決するための手段】
この発明に係る暗号管理装置は、超楕円曲線Ｃに付随する有限体Ｆq 上のヤコビ多様体をＪ（Ｃ，Ｆq ）とするとき、
ＣＰＵビット幅Ｎに基づいて超楕円曲線Ｃを生成する超楕円曲線Ｃ生成部を備えたことを特徴とする。
【００１２】
上記超楕円曲線Ｃ生成部は、ＣＰＵビット幅Ｎに基づいて種数ｇを計算する種数ｇ計算部と、
ＣＰＵビット幅Ｎ以下の素数を拡大次数ｎとして選択する拡大次数ｎ選択部と、
種数ｇから次数を決定して超楕円曲線Ｃを順次生成するとともに、選択された拡大次数ｎに基づく有限体Ｆq と上記超楕円曲線Ｃとからヤコビ多様体Ｊ（Ｃ，Ｆq ）の要素数＃Ｊ（Ｃ，Ｆq ）を計算し、最大の素因数を求め、最大の素因数が暗号の安全性の目安となる目安整数Ｋ以上となるような超楕円曲線Ｃを選択する超楕円曲線Ｃ決定部と
を備えたことを特徴とする。
【００１３】
上記種数ｇ計算部は、更に、暗号の安全性の目安となる目安整数Ｋを入力し、ＣＰＵビット幅Ｎと目安整数Ｋから種数ｇを計算することを特徴とする。
【００１４】
上記種数ｇ計算部は、超楕円曲線Ｃ決定部が目安整数Ｋより大きな値を持つ最大の素因数を求められないとき、種数ｇの値を大きくすることを特徴とする。
【００１５】
上記ヤコビ多様体Ｊ（Ｃ，Ｆq ）の要素数＃Ｊ（Ｃ，Ｆq ）が大きな素数で割り切れるように上記超楕円曲線Ｃと上記有限体Ｆq をとり、
上記ヤコビ多様体Ｊ（Ｃ，Ｆq ）における演算が、多倍長精度演算を必要としない通常の整数演算で行うことができることを特徴とするとともに、上記ヤコビ多様体Ｊ（Ｃ，Ｆq ）上定義される離散対数問題の困難さを安全性の根拠に持つことを特徴とする。
【００１６】
上記種数ｇは、６以上であることを特徴とする。
【００１７】
上記有限体Ｆq の要素の数ｑは、２32以下であることを特徴とする。
【００１８】
上記有限体Ｆq の要素の数ｑは、２16以下であることを特徴とする。
【００１９】
上記超楕円曲線Ｃは、ｖ2 ＋ｖ＝ｕ13＋ｕ11＋ｕ7 ＋ｕ3 ＋１であり、上記有限体Ｆq は、Ｆ229 であることを特徴とする。
【００２０】
上記超楕円曲線Ｃは、ｖ2 ＋ｖ＝ｕ13＋ｕ11＋ｕ9 ＋ｕ5 ＋１であり、上記有限体Ｆq は、Ｆ229 であることを特徴とする。
【００２１】
上記超楕円曲線Ｃは、ｖ2 ＋ｖ＝ｕ31であり、上記有限体Ｆq は、Ｆ213 であることを特徴とする。
【００２２】
この発明に係る暗号化方法は、ＣＰＵビット幅Ｎをメモリから取得する工程と、
ヤコビ多様体Ｊの目安整数Ｋをメモリから取得する工程と、
ＣＰＵビット幅Ｎと目安整数Ｋから種数ｇを計算する工程と、
ＣＰＵビット幅Ｎから素数を拡大次数として選択する工程と、
種数ｇから次数を計算し、計算した次数に基づく超楕円曲線Ｃを生成し、選択した拡大次数に基づく有限体Ｆq と生成した超楕円曲線Ｃとから要素数＃Ｊを計算し、最大の素因数を検出し、メモリに記憶する工程と、
メモリに記憶された最大の素因数が目安整数Ｋより大きい場合に、メモリに記憶された最大の素因数を生成した超楕円曲線Ｃを暗号に用い入る超楕円曲線Ｃとして決定する工程と
を備えたことを特徴とする。
【００２３】
【発明の実施の形態】
実施の形態１．
本発明による暗号化方法の一実施の形態を図１，図２，図３，図４に基づいて説明する。
図１は、本実施の形態による暗号化方法における鍵生成の方法を説明したフローチャートである。
図において、Ｓ１０１は本発明の特徴となる超楕円曲線Ｃと有限体Ｆq とヤコビ多様体Ｊの要素Ｄを選択するステップ、Ｓ１０２は整数ｘを選択し、整数ｘを秘密鍵とするステップ、Ｓ１０３はヤコビ多様体Ｊ上でＹ＝ｘＤを計算し、Ｙを公開鍵とするステップである。
【００２４】
図２は、本実施の形態による暗号化方法を説明したフローチャートである。
図において、Ｓ２０１はデータｍと整数ｒを選択するステップで、データｍは平文ｍとも呼ばれる。Ｓ２０２はヤコビ多様体Ｊ上で、Ｃ1 ＝ｒＤとＣ2 ＝ｒＹ＋ｍを計算するステップ、Ｓ２０３はＣ1 とＣ2 の組（Ｃ1 ，Ｃ2 ）を平文ｍを暗号化した結果である暗号文とするステップである。
【００２５】
図３は、本実施の形態による復号化方法を説明したフローチャートである。
図において、Ｓ３０１は暗号文（Ｃ1 ，Ｃ2 ）と秘密鍵ｘとから、ヤコビ多様体Ｊ上でｍ＝Ｃ2 −ｘＣ1 を計算するステップで、Ｓ３０２は計算されたｍを平文とするステップである。
【００２６】
図４は、本実施の形態による暗号化方法を用いた公開鍵暗号通信を説明した図である。
図において、７０１はデータ受信装置、７０２は整数ｘ生成手段、７０３はＹ＝ｘＤ計算手段、７０４は公開鍵Ｙ出力手段、７０５は秘密鍵ｘ記憶手段、７０６は暗号文入力手段、７０７はデータｍ＝Ｃ2 −ｘＣ1 計算手段、７０８はデータ送信装置、７０９はデータ入力手段、７１０は公開鍵入力手段、７１１は整数ｒ生成手段、７１２はＣ1 ＝ｒＤとＣ2 ＝ｒＹ＋ｍを計算する計算手段、７１３は暗号文（Ｃ1 ，Ｃ2 ）生成手段、７１４は暗号文出力手段、７１５は暗号処理を管理する暗号管理装置、７１６は超楕円曲線及び有限体及びヤコビ多様体の要素Ｄを生成する生成手段、７１７は公開鍵記憶手段である。
【００２７】
次に、動作を説明する。
まず、暗号鍵生成方法を説明する。
まず、Ｓ１０１において、超楕円曲線Ｃと有限体Ｆq とヤコビ多様体Ｊ（Ｃ，Ｆq ）の要素Ｄを選択する。超楕円曲線Ｃは、ｖ2 ＋ｈ（ｕ）ｖ＝ｆ（ｕ）と表される方程式で、曲線の種数をｇとすると、ｆ（ｕ）は次数２ｇ＋１のモニック多項式、ｈ（ｕ）は次数が高々ｇの多項式である。ｇは、超楕円曲線Ｃの性質を特徴付けるパラメータで種数と呼ばれる。超楕円曲線Ｃと有限体Ｆq を決めると、それに付随するヤコビ多様体Ｊ（Ｃ，Ｆq ）が構成される。ヤコビ多様体Ｊの要素において、加法を定義することができ、この加法に関してヤコビ多様体は群をなす。ヤコビ多様体及び加法の演算方法に関しては、前述の文献、Ｋｏｂｌｉｔｚ著、“Ｈｙｐｅｒｅｌｌｉｐｔｉｃ  Ｃｒｙｐｔｏｓｙｓｔｅｍｓ”，Ｊｏｕｒｎａｌ  ｏｆ  Ｃｒｙｐｔｏｌｏｇｙ，（１９８８）に詳しく記載されている。
有限体Ｆq の要素は、ｑ＝２n の場合、ｎビットの整数として計算機上で表現される。ｎが計算機のＣＰＵのレジスタの大きさを超える場合、有限体上の演算のために、多倍長演算と呼ばれる技術が必要になり、演算が遅くなる。従って、多倍長演算を必要とせず、通常の整数演算だけですむように、有限体Ｆq を選択する。また、暗号通信の安全性のために、ヤコビ多様体Ｊの要素の数＃Ｊが大きな素数で割り切れるように、ヤコビ多様体Ｊを構成する必要がある。つまり、この条件を満たすように、超楕円曲線Ｃと有限体Ｆq を選択しなければならない。超楕円曲線Ｃと有限体Ｆq の選択については、後述する。
次に、Ｓ１０２において、整数ｘを選択する。この整数ｘは、公開鍵暗号通信における秘密鍵として使用され、公開鍵暗号通信の利用者各自に秘密に保持される。
次に、Ｓ１０３において、ヤコビ多様体Ｊ上で、Ｙ＝ｘＤを計算する。計算されたＹは、公開鍵暗号通信において公開鍵として使用され、公開鍵Ｙは秘密に保持する必要はなく、一般に公開される。
【００２８】
次に、データの暗号化方法を説明する。
まず、Ｓ２０１において、暗号化したいデータｍと整数ｒを選択する。次に、Ｓ２０２において、Ｓ１０１において選択されたヤコビ多様体Ｊ上で、Ｊの要素Ｄと公開鍵Ｙを用いて、Ｃ1 ＝ｒＤとＣ2 ＝ｒＹ＋ｍを計算する。Ｓ２０３において、Ｃ1 とＣ2 の組（Ｃ1 ，Ｃ2 ）を暗号文とした生成する。
このように、暗号文は公開鍵Ｙを用いて生成される。
【００２９】
次に、データの復号化方法を説明する。
まず、Ｓ３０１において、暗号文（Ｃ1 ，Ｃ2 ）と、秘密に保持された秘密鍵ｘとから、Ｓ１０１において、生成されたヤコビ多様体Ｊ上でｍ＝Ｃ2 −ｘＣ1を計算する。Ｓ３０２において、これを平文ｍとする。
【００３０】
次に、以上で説明した、鍵生成方法、暗号化方法、復号化方法を用いて実際に公開鍵暗号通信を行う方法を図４に基づいて説明する。
データ送信装置７０８からデータ受信装置７０１へデータが送信される。また、暗号管理装置７１５では暗号通信に使用されるシステム全体の共通パラメータである超楕円曲線Ｃ及び有限体Ｆq 及びヤコビ多様体Ｊの要素Ｄが生成され、更に、データ暗号化に使用される公開鍵Ｙの管理が行われる。公開鍵Ｙは、システムの利用者全員が利用できるように公開される。但し、秘密鍵ｘは、利用者各自が秘密に保持しておかなくてはならない。
【００３１】
まず、暗号管理装置７１５でシステム全体のパラメータを生成する。生成手段７１６において、超楕円曲線Ｃと有限体Ｆq とヤコビ多様体ＪとＪの要素Ｄを生成する。これらのパラメータは、前述のように、ヤコビ多様体Ｊの要素の数が大きな素数で割り切れるように設定する。
【００３２】
図５は、生成手段７１６の構成図である。
生成手段７１６は、メモリ１０と回路部２０から構成されている。メモリ１０は、ＣＰＵビット幅Ｎレジスタ１１と目安整数Ｋレジスタ１２と最大素因数レジスタ１３から構成されている。回路部２０は、超楕円曲線Ｃ生成部３０とヤコビ多様体Ｊの要素Ｄ生成部２５から構成されている。超楕円曲線Ｃ生成部３０は、種数ｇ計算部２１と拡大次数ｎ選択部２２と超楕円曲線Ｃ決定部２３とから構成されている。
【００３３】
ＣＰＵビット幅Ｎレジスタ１１は、実際に暗号演算処理を行うデータ送信装置７０８とデータ受信装置７０１のＣＰＵビット幅Ｎを記憶するレジスタである。目安整数Ｋレジスタ１２は、安全性の目安となるヤコビ多様体Ｊの要素数＃Ｊの最大素因数の大きさを記憶するレジスタである。最大素因数レジスタ１３は、最大素因数を記憶するレジスタである。
ＣＰＵビット幅Ｎレジスタ１１に記憶されるＣＰＵビット幅Ｎは、予めＮ＝３２という値が設定されているものとする。目安整数Ｋレジスタ１２に記憶される整数も予めＫ＝２160 という値が設定されているものとする。
【００３４】
まず、回路部２０の動作の概略を説明する。
安全な暗号通信を行うためのヤコビ多様体Ｊ（Ｃ，Ｆq ）は、ヤコビ多様体の要素数＃Ｊを素因数分解した際の最大素因数の大きさが、大きくなければならない。本実施の形態では、２160 以上であればよいとしている。ヤコビ多様体は、超楕円曲線Ｃの方程式と、有限体Ｆq を決めれば一意に決まり、要素数＃Ｊも一意に決まる。つまり、超楕円曲線Ｃと有限体Ｆq を適切に（ヤコビ多様体の要素数＃Ｊの最大素因数が大きくなるように）決めることが必要である。本実施の形態では、ｑは２のべき乗２n に設定し、かつ、ｎをＣＰＵビット幅以下にとることがＦq を決める上での制約条件である（なお、Ｆ2nのｎのことを数学では“拡大次数”と呼ぶ）。
ヤコビ多様体の要素数＃Ｊは、だいたいｑg （＝２ng）の大きさとなる。つまり、有限体Ｆ2nの拡大次数ｎと、超楕円曲線Ｃの種数ｇ（超楕円曲線の次数は２ｇ＋１となる）を決めれば、ヤコビ多様体の要素数＃Ｊの大きさはだいたい決まる。ここで重要なのは、ヤコビ多様体の要素数＃Ｊの大きさがだいたい決まる（だいたい２ngになる）ということで、正確なヤコビ多様体の要素数＃Ｊの値は、２ng前後の値をとるということである。結果として、拡大次数ｎと種数ｇが同じでも超楕円曲線Ｃの方程式を変えると、ヤコビ多様体の要素数＃Ｊの大きさはだいたい同じであっても、ヤコビ多様体の要素数＃Ｊの最大素因数の大きさは全く異なる。
例えば、仮に、２ng＝１００になったとすると、超楕円曲線Ｃのとり方によってヤコビ多様体の要素数＃Ｊは、１０２になったり、９９になったりする。１０２＝２×５１，９９＝３×３×１１であるから、ヤコビ多様体の要素数＃Ｊの最大素因数は、それぞれ５１，１１となり、暗号として好ましいのはヤコビ多様体の要素数＃Ｊ＝１０２になる超楕円曲線Ｃの方ということになる。
従って、ヤコビ多様体Ｊの生成手順は、まず、種数ｇと拡大次数ｎを決めておいて、超楕円曲線Ｃの方程式をいろいろ変えてヤコビ多様体の要素数＃Ｊとその最大素因数を計算し、最大素因数が安全性を決めるパラメータ（目安整数Ｋ、Ｋ＝２160 ）よりも大きくなる超楕円曲線Ｃが得られたら終了とする。
種数ｇと拡大次数ｎは、ヤコビ多様体の要素数＃Ｊの大きさはだいたい２ng前後なので、２ng＞Ｋ（＝２160 ）になるようにしておけばよい。なぜなら、ヤコビ多様体の要素数＃Ｊの最大素因数の大きさは、必ずヤコビ多様体の要素数＃Ｊより小さくなり、ヤコビ多様体の要素数＃Ｊがヤコビ多様体の要素数＃Ｊに近い大きさの最大素因数を持つようなヤコビ多様体Ｊを得ることを期待するからである。拡大次数ｎは、ＣＰＵのレジスタ幅以下にする。種数ｇは、小さい方が暗号化速度が速いので、２ng＞Ｋ（＝２160 ）を満たす最小の整数ｇを選ぶ。
【００３５】
次に、回路部２０の動作を図５，図６を用いて詳細に説明する。
図６は、図１に示したＳ１０１の詳細なフローチャート図である。
種数ｇ計算部２１は、Ｓ１１において、ＣＰＵビット幅Ｎレジスタ１１からＣＰＵビット幅Ｎを取得する。例えば、ここでは、ＣＰＵビット幅Ｎ＝３２が取得されたものとする。
次に、種数ｇ計算部２１は、目安整数Ｋレジスタ１２から目安整数Ｋを取得する。ここでは、目安整数Ｋ＝２160 とする。次に、種数ｇ計算部２１は、Ｓ１３において、種数ｇを計算する。種数ｇは、Ｋ＜２N(g)を満足する最小の整数である種数ｇを選択する。この例においては、２160 ＜（２32）g ＝２32g であるから、ｇ＞１６０／３２＝５となり、ｇ＝６となる。即ち、種数ｇ＝６が求められる。種数ｇ計算部２１は、種数ｇ＝６を超楕円曲線Ｃ決定部２３に出力する。
次に、拡大次数ｎ選択部２２は、Ｓ１４において、ＣＰＵビット幅Ｎ以下の最大素数を選択する。この例においては、Ｎが３２であるから、３１，２９，２３，１９，１７，・・・という素数の中で最大素数３１が選択される。この素数３１が拡大次数ｎとなる。また、こうして有限体Ｆq ＝Ｆ2nが決定する。超楕円曲線Ｃ決定部２３は、Ｓ１５において、種数ｇから次数を計算する。次数は、２ｇ＋１である。超楕円曲線Ｃ決定部２３は、この次数を持つ超楕円曲線Ｃを１つ生成する。超楕円曲線Ｃ決定部２３は、超楕円曲線の方程式を満足し、かつ、種数ｇから計算された次数を満足する超楕円曲線Ｃを生成する。この際、いろいろな超楕円曲線Ｃが考えられるが、とりあえず、ある１つの超楕円曲線Ｃを生成するものとする。
次に、超楕円曲線Ｃ決定部２３は、超楕円曲線Ｃと有限体Ｆ2nとから要素数＃Ｊを計算する。この要素数＃Ｊの計算は、既に知られている計算方法を用いることにより、ある１つの要素数＃Ｊが計算される。次に、超楕円曲線Ｃ決定部２３は、要素数＃Ｊを素因数分解し、素因数分解された素因数の内、最大の素因数を最大素因数レジスタ１３に記憶する。この時点で、素数３１を用いた場合の要素数＃Ｊの最大の素因数が最大素因数レジスタ１３に記憶される。もし、この最大素因数の値が目安整数Ｋよりも大きな値なら、生成した超楕円曲線Ｃを求めたかった超楕円曲線Ｃとして決定する。もし、この最大素因数の値が目安整数Ｋよりも小さな値なら、Ｓ１５に戻り別な超楕円曲線Ｃを生成して、Ｓ１６，Ｓ１７を繰り返す。最大素因数レジスタ１３は、これらの繰り返し処理の中で生じる最大素因数の最大の値を保持するものとする。
もし、超楕円曲線Ｃを変えても、最大素因数の値が目安整数Ｋよりも大きな値をとらない場合は、Ｓ１３に戻り種数ｇを大きくして（例えば、ｇ＝ｇ＋１として）Ｓ１４からＳ１７を実行する。もし、それでも、この最大素因数の値が目安整数Ｋよりも大きな値をとらない場合は、Ｓ１３において、更に大きな値の種数ｇを生成してＳ１４からＳ１７を繰り返す。最大素因数レジスタ１３は、これらの繰り返し処理の中で生じる最大素因数の最大の値を保持するものとする。
もし、これらの繰り返し処理により最大素因数の値が目安整数Ｋよりも大きな値をとらない場合は、超楕円曲線Ｃの生成の失敗を報告する。又は、安全性は満たさないという警告を発しながら、最大素因数レジスタ１３に記憶された最大素因数の中の最大の値を生成した超楕円曲線Ｃを取り敢えず選択する。
超楕円曲線Ｃが決定したら、次に、ヤコビ多様体Ｊの要素Ｄ生成部２５は、Ｓ１８において、最大素因数レジスタ１３に記憶された最大素因数を位数として持つ、ヤコビ多様体Ｊの要素Ｄを選択して出力する。また、有限体Ｆq と超楕円曲線Ｃを出力する。以上が、生成手段７１６の動作である。
【００３６】
次に、データ受信装置７０１における整数ｘ生成手段７０２で整数ｘが生成される。このｘが、データ復号の際に使用される秘密鍵ｘとなる。秘密鍵ｘは、秘密鍵ｘ記憶手段７０５において秘密に保持し、他の暗号通信利用者に知られないようにしておく。次に、７０３において、秘密鍵ｘに対応する公開鍵Ｙ＝ｘＤを計算する。ヤコビ多様体の要素Ｄは、暗号管理装置７１５から受け取ったものを使用する。計算された公開鍵Ｙは、公開鍵Ｙ出力手段７０４から暗号管理装置７１５へ送信され、公開鍵Ｙを暗号管理装置７１５が管理しておく。
以上で、データ送信装置７０８がデータ受信装置７０１へデータを送信するための前準備が終了する。
【００３７】
次に、データ送信装置７０８でデータを暗号化する処理を行う。まず、データ入力手段７０９に暗号化したいデータｍが入力される。次に、公開鍵入力手段７１０に、暗号管理装置７１５の公開鍵記憶手段７１７から公開鍵Ｙを入力する。次に、整数ｒ生成手段７１１において、整数ｒを生成する。次に、計算手段７１２において、データｍの暗号化処理を行う。計算手段７１２では、Ｃ1 ＝ｒＤとＣ2 ＝ｒＹ＋ｍが計算される。計算されたＣ1 とＣ2 の組を、暗号文（Ｃ1 ，Ｃ2 ）生成手段７１３において（Ｃ1 ，Ｃ2 ）として暗号文とする。生成された暗号文を暗号文出力手段７１４からデータ受信装置７０１へ出力する。
【００３８】
次に、データ送信装置７０８から送信された暗号文をデータ受信装置７０１で復号する処理を説明する。
まず、暗号文（Ｃ1 ，Ｃ2 ）が暗号文入力手段７０６へ入力される。入力された暗号文（Ｃ1 ，Ｃ2 ）は、予め保持されていた秘密鍵ｘを用いて、７０７において、ｍ＝Ｃ2 −ｘＣ1 を計算することにより、もとの平文ｍに復号される。
【００３９】
以上のように、データを公開鍵暗号通信によって送信すれば、秘密鍵ｘを知っているデータ受信者のみが暗号文を平文ｍに復号できるため、安全な秘密通信を行うことができる。
また、超楕円曲線Ｃに付随するヤコビ多様体Ｊの群で構成される離散対数問題を解く難しさに安全性の根拠をおいているので、安全な秘密通信を行うことができ、かつ、有限体Ｆq 上の演算を多倍長演算によらない通常の整数演算で行うことができるので、高速な暗号化復号化処理を行うことができる。
【００４０】
本実施の形態１では、公開鍵Ｙは管理装置を介してデータ送信装置に送られたが、データ受信装置から直接データ送信装置へ送ってもよい。
【００４１】
暗号の安全性は、＃Ｊの最大素因数によって決まる。また、有限体Ｆq の要素は、ｑ＝２n のときｎビットの整数で表現することができる。もし、暗号の安全性を一定値とするならば、即ち、ｑg を一定の値（例えば、２160 ）とするならば、図７に示すように、種数ｇが大きくなれば要素数ｑは小さな値となる。即ち、ｎの値は小さくなり、結果として、ＣＰＵビット幅を小さくすることができる。例えば、図７に示すように、種数ｇ＝５とすれば、要素数ｑ＝２32となる。このように、有限体Ｆq の要素数ｑ＝２n をｎ≦３２とすれば、有限体の要素を３２ビット以下の整数として計算機上で表現でき、パーソナルコンピュータ等の３２ビットＣＰＵを持つ計算機では通常の整数演算だけで、暗号化演算行うことができる。
【００４２】
また、図７に示すように、種数ｇ＝１０とすれば、要素数ｑ＝２16となる。このように、有限体Ｆq の要素数ｑ＝２n をｎ≦１６とすれば、有限体の要素を１６ビット以下の整数として計算機上で表現でき、ＩＣカード等の１６ビットＣＰＵを持つ計算機では通常の整数演算だけで、暗号化演算行うことができる。
【００４３】
この実施の形態の大きな特徴は、ある一定の暗号の安全性を確保する場合に、即ち、ｑg を一定とする場合に、種数ｇを大きくすれば、要素数ｑが小さくて済むという超楕円曲線Ｃの特性に着目したものである。種数ｇが大きくなればなるほど、要素数ｑは小さくて済み、ビット幅が少ない演算で暗号化を行うことができる。現在のＣＰＵビット幅Ｎは、１６ビット、３２ビット、６４ビットのように１６の倍数、或いは、３２の倍数で増加している。要素数ｑ＝２n のｎがこのＣＰＵビット幅Ｎ（１６の倍数、或いは、３２の倍数）に限りなく近い大きな値をとることにより、多倍長演算を全く用いない通常の整数演算だけで暗号化演算を行うことができる。図７に示すように、種数ｇ＝５又は種数ｇ＝１０を選択する場合に、３２ビット、或いは、１６ビットのＣＰＵで多倍長演算を用いない通常の整数演算だけで暗号化演算を行うことが可能となる。
【００４４】
また、上記図６のＳ１５においては、超楕円曲線Ｃを１つだけ選択したが、複数の超楕円曲線Ｃを選択して、選択した複数の超楕円曲線Ｃに対して並列的にＳ１５からＳ１７までの演算を行っても構わない。
また、上記図６のＳ１４において、最大の素数をしたが、上位３つの素数を選択しても構わない。或いは、全ての素数を用いても構わない。
【００４５】
また、図５に示したＣＰＵビット幅Ｎレジスタ１１には、１つのＣＰＵビット幅を記憶するようにしていたが、複数種類のデータ送信装置及びデータ受信装置に対応して複数のＣＰＵビット幅を記憶できるようにしても構わない。同様に、目安整数Ｋレジスタ１２にも暗号通信に要求される安全性に対応して、複数の目安整数Ｋを記憶できるようにしても構わない。このように、複数のＣＰＵビット幅と複数の要素数を記憶しておくことにより、データ送信装置及びデータ受信装置が使用しているＣＰＵビット幅にマッチした暗号演算を行うことができる。
なお、データ送信装置及びデータ受信装置のＣＰＵビット幅が異なる場合は、ＣＰＵビット幅の最大値、最小値又は最大公約数のいずれかをＣＰＵビット幅Ｎレジスタ１１に設定すればよい。
【００４６】
また、多倍長演算を用いない通常の整数演算だけで暗号化演算を行う場合に限らず、多倍長演算の回数を減少させるためにも本思想を利用することができる。例えば、１６ビットＣＰＵにおいて、ｑ＝２40の場合の計算を行うと、３回の多倍長演算が必要となるが、ｑ＝32以下ならば２回の多倍長演算で済む。従って、図７に示す１６ビットＣＰＵに対して、最大素因数が小さくなってしまう等の理由によりｑ＝２16を選択できない場合、２17≦ｑ≦２32の範囲で種数を選択すれば、２40以上を選択するより多倍長演算が少なくて済む。
【００４７】
実施例１．
ＣＰＵビット幅Ｎレジスタ１１に記憶するＣＰＵビット幅Ｎを３２とし、目安整数Ｋレジスタ１２に記憶する整数の大きさを２160 とし、超楕円曲線Ｃが、種数６のｖ2 ＋ｖ＝ｕ13＋ｕ11＋ｕ7 ＋ｕ3 ＋１という曲線で、有限体Ｆq がＦ229 である場合を説明する。この場合、ヤコビ多様体Ｊ（Ｃ，Ｆ229 ）の要素の数＃Ｊは、次の値となる。
＃Ｊ＝２３９４２７３０９０２０６８２８３４０２７７０９５５９２８５０４７７８９０１７４４４２６００１８３５００９
また、＃Ｊを素因数分解すると、
＃Ｊ＝２３×１０４０９８８３０００８９９２５３６５３３７８６７６４９０６５４２５１６９６４１０６２００００７９７８３
となる。＃Ｊ（Ｃ，Ｆ229 ）の最大素因数は、１７０ビットであり十分大きい。従って、このヤコビ多様体Ｊ（Ｃ，Ｆ229 ）上の離散対数問題を解くことは困難で、このヤコビ多様体を用いれば、安全な暗号通信を行うことができる。
また、有限体Ｆ229 の要素は、２９ビットの整数として計算機上で表現でき、パーソナルコンピュータ等の３２ビットＣＰＵを持つ計算機上では、多倍長演算を用いない通常の整数演算だけで暗号化演算を行うことができるので、高速に暗号化復号化が行える。
【００４８】
実施例２．
ＣＰＵビット幅Ｎレジスタ１１に記憶するＣＰＵビット幅Ｎを３２とし、目安整数Ｋレジスタ１２に記憶する整数の大きさを２160 とし、超楕円曲線Ｃが、種数６のｖ2 ＋ｖ＝ｕ13＋ｕ11＋ｕ9 ＋ｕ5 ＋１という曲線で、有限体Ｆq がＦ229 である場合を説明する。この場合、ヤコビ多様体Ｊ（Ｃ，Ｆ229 ）の要素の数＃Ｊは、次の値となる。
＃Ｊ＝２３９４１４０６６７１３３７４６８２７４７０２６６５０２５６５４８４９４７６０１８２４３６２０４８３０７３
また、＃Ｊを素因数分解すると、
＃Ｊ＝１３×１８４１６４６６６７０２５９５９０９８０５４０５１１５５８１９６０３８０５８４７５５７２０１５７５６２１
となる。＃Ｊ（Ｃ，Ｆ229 ）の最大素因数は、１７１ビットであり十分大きい。従って、このヤコビ多様体Ｊ（Ｃ，Ｆ229 ）上の離散対数問題を解くことは困難で、このヤコビ多様体を用いれば、安全な暗号通信を行うことができる。
また、有限体Ｆ229 の要素は、２９ビットの整数として計算機上で表現でき、パーソナルコンピュータ等の３２ビットＣＰＵを持つ計算機上では、多倍長演算を用いない通常の整数演算だけで暗号化演算を行うことができるので、高速に暗号化復号化が行える。
【００４９】
実施例３．
ＣＰＵビット幅Ｎレジスタ１１に記憶するＣＰＵビット幅Ｎを３２とし、目安整数Ｋレジスタ１２に記憶する整数の大きさを２160 とし、超楕円曲線Ｃが、種数１５のｖ2 ＋ｖ＝ｕ31いう曲線で、有限体Ｆq がＦ213 である場合を説明する。この場合は、種数ｇの値を大きくしていった場合である。この場合、ヤコビ多様体Ｊ（Ｃ，Ｆ213 ）の要素の数＃Ｊは、次の値となる。
＃Ｊ＝５０２１６８１３８４９２１１０８７６６４２６０６１２２２０６１７３５７８６００４４１９３７５０１５７４９３６４１２１７
また、＃Ｊを素因数分解すると、
＃Ｊ＝３１×８５３×１８９９０５８８７５６６５０５６４４８３７０４８０３６２３１２０４３１８１９４０１８０５２９８２４８１１６１９
となる。＃Ｊ（Ｃ，Ｆ213 ）の最大素因数は、１８１ビットであり十分大きい。従って、このヤコビ多様体Ｊ（Ｃ，Ｆ213 ）上の離散対数問題を解くことは困難で、このヤコビ多様体を用いれば、安全な暗号通信を行うことができる。
また、有限体Ｆ（２13）の要素は、１３ビットの整数として計算機上で表現でき、ＩＣカード等の１６ビットＣＰＵを持つ計算機上では、多倍長演算を用いない通常の整数演算だけで暗号化演算を行うことができるので、高速に暗号化復号化が行える。
【００５０】
【発明の効果】
以上のように、本発明によれば、離散対数問題を構成するヤコビ多様体Ｊの要素数＃Ｊの最大素因数が大きいので、安全な暗号通信を行うことができる。
また、本発明によれば、ヤコビ多様体Ｊにおける有限体Ｆq 上の演算を、多倍長演算を必要としない通常の整数演算で行えるため、高速に暗号化復号化できる。
【図面の簡単な説明】
【図１】  本発明の暗号化方法を説明するフローチャート図である。
【図２】  本発明の暗号化方法を説明するフローチャート図である。
【図３】  本発明の暗号化方法を説明するフローチャート図である。
【図４】  本発明の暗号化方式を説明する図である。
【図５】  本発明の生成手段７１６の構成図である。
【図６】  本発明の生成手段７１６の動作フローチャート図である。
【図７】  本発明の種数ｇと要素数ｑの関係を示す図である。
【図８】  従来の暗号化方法を説明するフローチャート図である。
【図９】  従来の暗号化方法を説明するフローチャート図である。
【図１０】  従来の暗号化方法を説明するフローチャート図である。
【符号の説明】
１０  メモリ、１１  ＣＰＵビット幅Ｎレジスタ、１２  目安整数Ｋレジスタ、１３  最大素因数レジスタ、２０  回路部、２１  種数ｇ計算部、２２  拡大次数ｎ選択部、２３  超楕円曲線Ｃ決定部、２５  ヤコビ多様体Ｊの要素Ｄ生成部、３０  超楕円曲線Ｃ生成部。
【図１】
0004243874.tif 000002
【図２】
0004243874.tif 000003
【図３】
0004243874.tif 000004
【図４】
0004243874.tif 000005
【図５】
0004243874.tif 000006
【図６】
0004243874.tif 000007
【図７】
0004243874.tif 000008
【図８】
0004243874.tif 000009
【図９】
0004243874.tif 000010
【図１０】
0004243874.tif 000011