暗号鍵解析方法、暗号鍵解析装置および暗号鍵解析プログラム
【課題】楕円曲線離散対数問題の解を求めるための計算量を削減すること。
【解決手段】暗号鍵解読装置１００は、テーブル生成部１３２がBaby-StepおよびGiant-Stepを実行して、Ｔｂテーブル１４１およびＴｂテーブル１４２を生成する場合に、楕円曲線演算の一部に、自己同型写像を適用することで、楕円曲線演算を実行すべき範囲を削減することができる。この結果、楕円曲線離散対数問題を解くための計算量を、従来のCheon解析法と比較して、１／（２ｍ）１／２に削減することができる。
【解決手段】暗号鍵解読装置１００は、テーブル生成部１３２がBaby-StepおよびGiant-Stepを実行して、Ｔｂテーブル１４１およびＴｂテーブル１４２を生成する場合に、楕円曲線演算の一部に、自己同型写像を適用することで、楕円曲線演算を実行すべき範囲を削減することができる。この結果、楕円曲線離散対数問題を解くための計算量を、従来のCheon解析法と比較して、１／（２ｍ）１／２に削減することができる。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号鍵解析方法、暗号鍵解析装置および暗号鍵解析プログラムに関する。
【背景技術】
【０００２】
近年、ネットショッピングやネットバンキングが普及している。ネットショッピングやネットバンキングにおいて通信を行う場合には、情報漏洩などを防止するために、ＳＳＬ（Secure Socket Layer）／ＴＬＳ（Transport Layer Security）等の暗号技術が用いられる。暗号化方式を大別すると共通鍵暗号と公開鍵暗号に分類することができる。
【０００３】
このうち、共通鍵暗号は、送信者と受信者とが同じ鍵を持つことにより暗号通信をおこなう方式である。すなわち、共通鍵暗号では、送信者は、あるメッセージを秘密の暗号鍵に基づいて暗号化して受信者に送る。受信者は、この暗号鍵を用いて暗号文を復号し、メッセージを入手する。
【０００４】
公開鍵暗号は、対になる２つの鍵を使ってデータの暗号化、復号をおこなう方式である。すなわち、送信者は受信者によって公開されている公開鍵でメッセージを暗号化して送信する。これに対して、受信者は、暗号化された暗号化されたメッセージを秘密鍵で復号する。公開鍵は、メッセージを暗号化するための鍵であり、秘密鍵は、公開鍵により暗号化された情報を復号するための鍵である。公開鍵で暗号化された情報は、対の秘密鍵でのみ復号することができる。
【０００５】
公開鍵暗号は、公開鍵を公開しても安全性を確保できるようにするために、数学的に難しいとされている問題に基づいて設計されている。例えば、公開鍵暗号には、ＲＳＡ（Rivest Shamir Adleman）暗号、エルガマル暗号、楕円曲線暗号（Elliptic Curve Cryptosystem）がある。
【０００６】
ＲＳＡ暗号は、素因数分解問題と呼ばれる数学的問題の困難性に基づいている。エルガマル暗号は、離散対数問題と呼ばれる数学的問題の困難性に基づいている。楕円曲線暗号は、楕円曲線上の離散対数問題を基に設計されている。楕円曲線上の離散対数問題を「楕円曲線離散対数問題」と称する。このように、公開鍵暗号の安全性は、数学的問題の困難性に基づいている。したがって、これらの数学的問題の安全性が、公開鍵暗号の安全性の指標となる。
【０００７】
楕円曲線暗号は、楕円曲線離散対数問題に基づく暗号である。楕円曲線離散対数問題に基づく暗号は、楕円曲線上の点および単位元となる無限遠点０の集合をなす加法群において定義される。この加法群に含まれる点の数を位数ｒと呼ぶ。楕円曲線上の点Ｐ１とＰ２に対する演算として、以下のものが定義されている。
加算：Ｐ３＝Ｐ１＋Ｐ２＝Ｐ２＋Ｐ１
２倍算：Ｐ２＝２×Ｐ１＝Ｐ１＋Ｐ１
減算：Ｐ３＝Ｐ１−Ｐ２
零点：０（無限遠点）＝Ｐ１−Ｐ１
スカラ倍算：ｋ×Ｐ＝Ｐ＋Ｐ＋・・・＋Ｐ
【０００８】
ここで、ｋ×ＰとＰとからｋを算出する問題を楕円曲線離散対数問題という。ｋは公開鍵暗号の秘密鍵に対応するものである。一般的に、位数ｒが十分に大きい場合には、解ｋを求めることは困難である。楕円曲線対数問題が困難であるという仮定のもとで、楕円曲線暗号は高い安全性を確保することができる。
【０００９】
さらに近年では、ペアリングという公開鍵暗号技術が注目されている。ペアリングは楕円曲線暗号の一種である。楕円曲線上の２点に対するペアリングと呼ばれる演算を用いることで、従来の楕円曲線の機能を拡張する。この場合、楕円曲線離散対数問題の困難性に加え、いくつかの数学的問題の困難性に関する新たな仮定が必要となる。（Ｌ＋１）双曲線Difie-Hellman指数問題と呼ばれる数学的問題の困難性を仮定することがある。（Ｌ＋１）双曲線Difie-Hellman指数問題は、Ｐ、ｋ×Ｐ、ｋ２×Ｐ、ｋ３×Ｐ、・・・、ｋＬ×Ｐから、ｋやｋＬ＋１を求めるものである。この場合、Ｐ、ｋ×Ｐからｋを求める楕円曲線離散対数問題に比べ、ｋ２×Ｐ、ｋ３×Ｐ、・・・、ｋＬ×Ｐなどの追加情報があることから、追加情報ありの楕円離散対数問題と呼ぶことがある。
【００１０】
ここで、公開鍵暗号の安全性を評価するためには、その基となっている数学的問題の解析が必要となる。例えば、安全生を決定するパラメータの一つに位数ｒがあり、この位数ｒの値を大きくすれば、公開鍵暗号の安全性を高めることができるが、あまりにおおきな値にすると、暗号化、復号にかかる処理負荷も大きくなる。このため、安全性を保証しつつ、暗号化、復号にかかる処理負荷をある程度おさえることができるちょうど良い位数ｒの大きさを求めるべく、実際に計算機実験を行って、数学的問題の評価をおこなうことが重要となる。
【００１１】
数学的問題の解析を行うものには、Ｐ、ｋ×Ｐ、ｋｄ×Ｐおよびｄから、ｋを求める補助入力付き楕円曲線離散対数問題がある。ここで、ｄは（ｒ−１）の約数である。この問題を解く方法として、例えば、Cheon解析法が知られている。Cheon解析法は、Baby-Step Giant-Step解析法（BSGS）を用いて攻撃を行う方法である。Cheon解析法では、BSGSを二重に処理することで攻撃を行う。BSGSでは２種類のテーブルを作成し、これら計算結果を比較して、秘密鍵ｋを求める。これにより、最小ｒ１／４の数倍程度の計算量で暗号鍵としての秘密鍵ｋを解くことができる。
【先行技術文献】
【特許文献】
【００１２】
【特許文献１】特開平１１−２８８２１５号公報
【特許文献２】特開２００３−２８８０１３号公報
【発明の概要】
【発明が解決しようとする課題】
【００１３】
しかしながら、上記のCheon解析法では、楕円曲線離散対数問題の解を求めるための計算量が多いという問題があった。
【００１４】
開示の技術は、上記に鑑みてなされたものであって、楕円曲線離散対数問題の解を求めるための計算量を削減することができる暗号鍵解析方法、暗号鍵解析装置、および、暗号鍵解析プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１５】
本願の開示する暗号鍵解析方法は、一つの態様において、コンピュータが、楕円曲線離散対数問題の解を楕円曲線上の点に対応する生成元のべき乗で示し、前記生成元のべき乗部分を第１部分と第２部分に分割する分割ステップと、前記第１部分の値を所定の値域で変化させた場合に前記生成元をべき乗することで算出される値を第１テーブルに格納する第１演算ステップと、前記第２部分の値を所定の値域で変化させた場合に前記生成元をべき乗することで算出される値と、前記生成元のべき乗部分の一部に自己同型写像を適用した値とを組あわせた値を第２テーブルに格納する第２演算ステップと、前記第１テーブルに格納された値と前記第２テーブルに格納された値とを比較し、一致した値に基づいて前記楕円曲線離散対数問題の解を算出することで暗号鍵を解析する暗号鍵解析ステップとを実行することを要件とする。
【発明の効果】
【００１６】
本願の開示する暗号鍵解析方法の一つの態様によれば、楕円曲線離散対数問題の解を求めるための計算量を削減することができるという効果を奏する。
【図面の簡単な説明】
【００１７】
【図１Ａ】図１Ａは、ＴｂテーブルとＴｇテーブルとを比較する処理を補足するための図である。
【図１Ｂ】図１Ｂは、BSGSの具体例を説明するための図である。
【図２】図２は、Cheon解析法の具体例を説明するための図（１）である。
【図３】図３は、Cheon解析法の具体例を説明するための図（２）である。
【図４】図４は、Cheon解析法の具体例を説明するための図（３）である。
【図５】図５は、従来のCheon解析法の処理手順を示すフローチャートである。
【図６】図６は、本実施例１にかかる暗号鍵解読装置の構成を示す図である。
【図７】図７は、自己同型写像を適用した場合と適用していない場合との楕円曲線演算を実行すべき範囲を示す図（１）である。
【図８】図８は、自己同型写像を適用した場合と適用していない場合との楕円曲線演算を実行すべき範囲を示す図（２）である。
【図９】図９は、本実施例１にかかるＴｂテーブルのデータ構造の一例を示す図である。
【図１０】図１０は、本実施例１にかかるＴｇテーブルのデータ構造の一例を示す図である。
【図１１】図１１は、本実施例１にかかるテーブル生成部の構成を示す図である。
【図１２】図１２は、本実施例１にかかる処理部の処理手順を示すフローチャートである。
【図１３】図１３は、本実施例１にかかるテーブル処理部の処理手順を示すフローチャートである。
【図１４】図１４は、本実施例２にかかる暗号解読装置の構成を示す図である。
【図１５】図１５は、本実施例２にかかるＴｂテーブルのデータ構造の一例を示す図である。
【図１６】図１６は、本実施例２にかかるＴｇテーブルのデータ構造の一例を示す図である。
【図１７】図１７は、本実施例２にかかるテーブル生成部の構成を示す図である。
【図１８】図１８は、本実施例２にかかる処理部の処理手順を示すフローチャートである。
【図１９】図１９は、本実施例３にかかる暗号鍵解読装置の構成を示す図である。
【図２０】図２０は、本実施例３にかかるテーブル生成部の処理の概要を示す図である。
【図２１】図２１は、本実施例３にかかるＴｂテーブルのデータ構造の一例を示す図である。
【図２２】図２２は、本実施例３にかかるＴｇテーブルのデータ構造の一例を示す図である。
【図２３】図２３は、本実施例３にかかるテーブル生成部の構成を示す図である。
【図２４】図２４は、本実施例３にかかる処理部の処理手順を示すフローチャートである。
【図２５】図２５は、本実施例３にかかるテーブル生成部の処理手順を示すフローチャートである。
【図２６】図２６は、従来のCheon解析法、実施例１〜３の楕円演算回数、テーブルのデータ量の比較結果を示す図（１）である。
【図２７】図２７は、従来のCheon解析法、実施例１〜３の楕円演算回数、テーブルのデータ量の比較結果を示す図（２）である。
【図２８】図２８は、テーブル作成時間とテーブル量とを示す図である。
【図２９】図２９は、暗号鍵解読プログラムを実行するコンピュータを示す図である。
【発明を実施するための形態】
【００１８】
まず、本願の開示する暗号鍵解読装置における技術を説明するうえでの原理を図面に基づいて説明する。以下では、Baby-Step Giant-Step解析法、Cheon解析法、自己同型写像、自己同型写像のべき表現の順に説明する。
【００１９】
まず、「Baby-Step Giant-Step解析法」について説明する。以下では、Baby-Step Giant-Step解析法をBSGSと表記する。BSGSは、楕円曲線離散対数問題の効率的な解法の一つである。位数ｒの楕円曲線パラメータを使用し、未知値ｘ（０＜ｘ＜ｒ）を、既知のｘ×ＧとＧから求める楕円曲線対数問題を解く場合には、BSGSは、２×ｒ１／２回程度の楕円曲線演算によって楕円曲線離散対数問題を解くことができる。これに対して、BSGSを用いず、楕円曲線離散対数問題を総当たりで求めると、平均ｒ／２回程度の演算が必要となってしまう。
【００２０】
BSGSでは、未知数ｘを「ｒ１／２の値を切り上げた値」の進数で、上位値ｘＨと下位値ｘＬに分割し、Baby-Stepを実行してＴｂテーブルを作成し、Giant-Stepを実行してＴｇテーブルを作成する。Baby-Stepでは、順次ｉの値を変化させながら「（ｘＬ−ｉ）×Ｇ」を順次算出し、Ｔｂテーブルに計算結果を順次格納する。一方、Giant-Stepでは、順次ｊの値を変化させながら「ｊ×Ｇ」を順次算出し、Ｔｇテーブルに計算結果を順次格納する。なお、ｉ、ｊには、進数に応じて所定の値が乗算される。
【００２１】
図１Ａは、ＴｂテーブルとＴｇテーブルとを比較する処理を補足するための図である。図１Ａの１ａは、未知数ｘの上位部分であり、１ｂは、未知数ｘの下位部分である。ＴｂテーブルとＴｇテーブルとを比較することは、図１Ａの２ａ部分に対応する値と、２ｂ部分に対応する値とを比較することである。
【００２２】
図１Ｂは、BSGSの具体例を説明するための図である。ここでは一例として、位数ｒ＝９７とし、ＧおよびｘＧの値が与えられるものとする。なお、未知数ｘ＝９６とする。Baby-Stepにおいて、BSGSは、ｉの値を順次変化させ、「ｘＬＧ−iＧ」を順次計算することで、Ｔｂテーブル１０ａを生成する。図１に示す例では、ｉの値を０〜９とする。Giant-Stepにおいて、BSGSは、ｊの値を順次変化させ、「ｊ×１０Ｇ」を順次計算することで、Ｔｇテーブル１０ｂを生成する。図１に示す例では、ｊの値を０〜９とする。
【００２３】
BSGSでは、Ｔｂテーブル１０ａの各値とＴｇテーブル１０ｂの各値とを比較し、各値が一致する場合のｉおよびｊの値を判定する。未知数ｘとｉ、ｊとの関係は、「ｘ＝ｉ＋１０ｊ」となるため、各値が一致する場合のｉおよびｊの値を判定することができれば、未知数ｘを算出することができる。図１に示す例では、Ｔｂテーブル１０ａのｉが「６」となる場合の値「９０」と、Ｔｇテーブル１０ｂのｊが「９」となる場合の値「９０」が一致する。このため、未知数ｘは、「ｘ＝６＋９×１０＝９６」となる。BSGSでは、このようにして未知数ｘを算出する。このときの楕円曲線演算は２０回となる。この回数は、上述した「２×ｒ１／２」の値とほぼ同じである。
【００２４】
ここで、楕円曲線離散対数問題を総当たりで求める場合について説明する。楕円曲線離散対数問題を総当たりで求める場合には、平均ｒ／２回程度の楕円曲線演算が行われる。ＧとｘＧの値が与えられた場合に、ｉの値を順次変化させ「ｉ×Ｇ」を順次計算し、計算結果とｘＧの値とを比較して未知数ｘを求める。例えば、未知数ｘ＝９６の場合には、ｉの値が９６になった場合に、「ｉ×Ｇ」の値とｘＧとの値が一致するため、未知数ｘ＝９６として求めることができる。この場合には、楕円曲線演算を９６回行う必要がある。
【００２５】
位数ｒの場合、BSGSでは平均２×ｒ１／２回程度の楕円曲線演算によって楕円曲線離散対数問題を解くことができるが、総当たり法では、平均ｒ／２回程度の楕円曲線演算が必要となる。以上のことから、BSGSは、総当たり法と比較して、楕円曲線問題を解く場合の楕円曲線演算の回数が少なくなる。
【００２６】
次に、「Cheon解析法」について説明する。Cheon解析法は、追加情報ありの楕円離散対数問題に対して、BSGSを適用して解を算出する方法である。上記BSGSでは、ＧとｘＧとから未知数ｘを求めたが、Cheon解析では、Ｇ、ｘＧ、ｘｄＧ、ｄを利用して、未知数ｘを求める。ｄはｒ−１の約数に対応するものである。Cheon解析法では、BSGSを二重に行うことで、計算量を削減する。仮に、ｄの値が、ｒ１／２の値とほぼ同じ値となる場合には、楕円曲線演算の回数がほぼｒ１／４となることが知られている。
【００２７】
以下において、Cheon解析法の具体例について説明する。図２〜図４は、Cheon解析法の具体例を説明するための図である。
【００２８】
Cheon解析法では、点Ｇに対する位数ｒの生成元ζを求め、ｘ＝ζｙとなるｙを見つける。ここで、ｙの値域は、０〜ｒ−１となる。図２の左側の各数値は、図１Ａに示した各数値と同様である。図２の右側において、ｙＨは、ｙを（ｒ−１）／ｄで除算した商に対応し、ｙＬは、ｙを（ｒ−１）／ｄで除算した余りに対応する。
【００２９】
図２に示すように、部分２ａに対応する値と部分２ｂに対応する値とを比較することは、部分３ａに対応する値と部分３ｂに対応する値とを比較することと同じである。なお、部分２ａに対応する値は「（ｘＬ−ｉ）×Ｇ」であり、部分２ｂに対応する値は「ｊ×Ｇ」である。部分３ａに対応する値は「
【数１】
」であり、部分３ｂに対応する値は「ζｊ×Ｇ」である。つまり、Cheon解析法では、ζの指数部分において、BSGSと同様の処理を実行することで、ｙを求める。
【００３０】
なお、Cheon解析法では、はじめからｘ＝ζｙとなるｙを求めるのではなく、ｙをｙＨとｙＬに分割し、ｙＨとｙＬとをそれぞれ求める。
【００３１】
まず、ｙＬを求める場合について説明する。ｘｄＧ＝ζｄｚＧとなるｚを求めることと、ｙＬを求めることは、数学的に同じ意味を持つ。だたし、ζｄ＝ζｄとする。ｚを求めるために、BSGSを適用することで、計算量０（ｒ１／４）でｚを求めることができる。
【００３２】
図３の右側に示すように、Cheon解析法では、ｚを上位ｚＨとｚＬに分割する。そして、Cheon解析法では、Baby-Stepにおいて、ｉの値を変化させながら「
【数２】
」を順次算出し、Ｔｂテーブルに計算結果を順次格納する。また、Giant-Stepにおいて、ｊの値を変化させながら「ζｄｊ×Ｇ」を順次算出し、Ｔｇテーブルに計算結果を順次格納する。Cheon解析法では、Ｔｂテーブルの各値とＴｇテーブルの各値とを比較し、各値が一致する場合のｉおよびｊの値を判定する。ｉとｊとの値が分かれば、ｚを求めることができる。
【００３３】
続いて、Cheon解析法では、ｙＬを求めた後に、残りのｙＨを求める。Cheon解析法では、
【数３】
となるｗの値を見つける。ｗの値は、ｙＨに対応するものである。ｗの値域は０〜ｄとなる。
【００３４】
図４の右側に示すように、ｗを上位ｗＨとｗＬに分割する。そして、Cheon解析法では、Baby-Stepにおいて、ｉの値を変化させながら「
【数４】
」を順次算出し、Ｔｂテーブルに計算結果を順次格納する。また、ｊの値を変化させながら「ζｄｊ×Ｇ」を順次算出し、Ｔｇテーブルに計算結果を順次格納する。Cheon解析法では、Ｔｂテーブルの各値とＴｇテーブルの各値とを比較し、各値が一致する場合のｉおよびｊの値を判定する。ｉとｊとの値が分かれば、ｗを求めることができる。
【００３５】
上記のように、図２〜図４の処理を実行することで、ｙＬに対応するｚと、ｙＨに対応するｗが求まるので、ｙの値が特定される。上記のCheon解析法では、最小０（ｒ１／４）の計算量で、追加情報ありの楕円離散対数問題を解析することができる。
【００３６】
次に、従来のCheon解析法の処理手順について説明する。図５は、従来のCheon解析法の処理手順を示すフローチャートである。図５に示すように、Cheon解析法では、未知数ｘ＝ζｙとし、ｙをｙＨとｙＬに分割する（ステップＳ１０）。
【００３７】
Cheon解析法では、ｙＬ部分に対してBaby-Stepを実行し、ζｄ−ｕ１×ｘｄＧとなるＴｂテーブルを作成する（ステップＳ１１）。ただし、ｕ１の値域を０≦ｕ１＜ｄ１とする。ここで、ｄ１は、（（ｒ−１）／ｄ）１／２の値を切り上げたものに対応する。
【００３８】
Cheon解析法では、ｙＬ部分に対してGiant-Stepを実行し、ζｄｖ１・ｄ１×ＧとなるＴｇテーブルを作成する（ステップＳ１２）。ただし、ｖ１の値域を０≦ｖ１＜ｄ１とする。
【００３９】
Cheon解析法では、ＴｂテーブルとＴｇテーブルとを比較し、ζｄ−ｕ１×ｘｄＧ＝ζｄｖ１・ｄ１×Ｇとなるｕ１、ｖ１の組を算出する（ステップＳ１３）。Cheon解析法では、ｕ１とｖ１とを加算することでｚを算出する（ステップＳ１４）。このｚは、ｙＬに対応するものである。
【００４０】
続いて、Cheon解析法では、上位部分に対してＢａｂｙ−Ｓｔｅｐを実行し、ζ−ｕ２（ｒ−１）／ｒ×ｘＧ｛０≦ｕ２＜ｄ１’’｝となるＴｂテーブル１４１を作成する（ステップＳ１５）。また、Cheon解析法では、上位部分に対してＧｉａｎｔ−Ｓｔｅｐを実行し、ζｋ１ζｒ２・ｄ２・（ｒ−１）／ｒ×Ｇ｛０≦ｖ２＜ｄ’’｝となるＴｇを計算し、全ての点からなるＴｇテーブルを作成する（ステップＳ１６）。
【００４１】
Cheon解析法では、ＴｂテーブルとＴｇテーブルとを比較し、ζ−ｕ２（ｒ−１）／ｒ×ｘＧ＝、ζｋ１ζｒ２・ｄ２・（ｒ−１）／ｒ×Ｇとなる（ｕ２、ｖ２）の組を算出する（ステップＳ１７）。Cheon解析法では、、ｗ＝ｙＨ＝ｕ２＋ｖ２ｄ’’により、ｙの上位部分ｗを算出する（ステップＳ１８）。このｗは、ｙＨに対応するものである。そして、Cheon解析法では、ｚとｗ（ｒ−１）／ｄとを加算することで、ｙを算出する（ステップＳ１９）。このｙは、ｘ＝ζｙと、未知数ｘに対応するものである。以上、Cheon解析法の具体例について説明した。このようにして、Cheon解析法では、未知数ｘを算出する。
【００４２】
次に、「自己同型写像」について説明する。一部の楕円曲線では、楕円曲線上の点ＰのFrobenius写像Φ（Ｐ）が高速に計算できる。例えば、有限体（３１２７）の楕円曲線では、点Ｐ＝（ｘ、ｙ）のFrobenius写像Φ（Ｐ）＝（ｘ３、ｙ３）も同一の楕円曲線上の点となる。このFrobenius写像Φ（Ｐ）は、各座標を３乗するだけであり、他の楕円曲線演算に比べて高速に計算できる。なお、点ＰにFrobenius写像Φ（Ｐ）をｉ回適用して得られる点であるΦ（ｉ）（Ｐ）は以下のように記述される。すなわち、Φ（ｉ）（Ｐ）＝Φ（Φ（・・・Φ（Ｐ）））となる。
【００４３】
また、一部の楕円曲線ではマイナス写像についても高速に計算できる。マイナス写像は、点Ｐを点−Ｐに対応させる写像である。例えば、有限体ＧＦ（３１２７）における楕円曲線では、点Ｐ＝（ｘ，ｙ）のマイナス写像−Ｐ＝（ｘ，−ｙ）も同一の楕円曲線上の点となる。以下では、Frobenius写像およびマイナス写像をまとめて自己同型写像と呼ぶ。
【００４４】
次に、「自己同型写像のべき表現」について説明する。有限体ＧＦ（ｑｍ）における楕円曲線の場合、任意の点にFrobenius写像をｍ回適用すると元の点に戻る。つまり、Φ（ｍ）（Ｐ）＝Ｐとなる。また、任意の点のマイナス写像を２回適用すると元の点に戻る。つまり、（−１）２×Ｐ＝Ｐとなる。
【００４５】
上記自己同型写像を生成元ζのべき乗として表すと、自己同型写像は、（−１）（ｉ）Φ（ｊ）Ｐ＝ζ（ｉ・ｍ＋２・ｃ・ｊ）（ｒ―１）／２ｍ×Ｐと表現することができる。ここで、ｃは楕円曲線と生成元の値によって一意に決まる定数である。ｉおよびｊの値は、ｉ＝０〜１、ｊ＝０〜ｍ−１である。
【００４６】
特に、有限体ＧＦ（３１２７）楕円曲線上の点でマイナス点とFrobenius写像も同じ楕円曲線上の点となるような点Ｐに関し、生成元ζ＝３、ｍ＝１２７、ｃ＝１１０の場合には、自己同型写像は、（−１）（ｉ）Φ（ｊ）Ｐ＝ζ（１２７・ｉ＋２２０・ｊ）（ｒ―１）／２５４×Ｐと表現することができる。
【００４７】
以上、本願の開示する暗号鍵解読装置における技術を説明する上での原理を説明した。以下に、本願の開示する暗号鍵解読装置の実施例を図面に基づいて詳細に説明する。なお、この実施例により発明が限定されるものではない。
【実施例１】
【００４８】
本実施例１にかかる暗号鍵解読装置について説明する。図６は、本実施例１にかかる暗号鍵解読装置の構成を示す図である。この暗号鍵解読装置１００は、楕円曲線離散対数問題を解くことで、公開鍵暗号の秘密鍵を算出する装置である。図６に示すように、この暗号鍵解読装置１００は、入力部１１０、出力部１２０、処理部１３０、記憶部１４０を有する。
【００４９】
入力部１１０は、外部から情報を入力する。例えば、入力部１１０は、ユーザからの指示を受け付けて、受け付けた指示を処理部１３０に入力する。また、入力部１１０は、楕円曲線離散対数問題を解読する場合に利用する各種のパラメータを受け付け、受け付けたパラメータを処理部１３０に入力する。出力部１２０は、楕円離散対数問題の解読結果を出力する。
【００５０】
処理部１３０は、パラメータ取得部１３１、テーブル生成部１３２、テーブル比較部１３３、未知数算出部１３４、制御部１３５を有する。
【００５１】
パラメータ取得部１３１は、入力部１１０からパラメータを取得し、取得したパラメータをテーブル生成部１３２に出力する処理部である。なお、パラメータ取得部１３１は、パラメータを記憶部１４０に記憶させておき、ユーザからの指示を受け付けた場合に、記憶部１４０に記憶されたパラメータを取得してもよい。
【００５２】
ここで、パラメータの一例について説明する。パラメータには、Ｇ＊、ζ＊、ｍ、ｄ’’が含まれる。このうち、Ｇ＊は、楕円曲線上の点である。ζ＊は、位数ｒの生成元である。ｍは、拡大次数である。ｄ’’は、テーブルの作成範囲を指定するものである。具体的に、自己同型写像を利用してｙＨを求める場合には、Ｇ＊＝Ｇｄ、ζ＊＝ζｄ、ｄ’’は、「（（ｒ−１）／ｄ／２ｍ）１／２の値を切り上げた値」となる。また、自己同型写像を利用してｙＨを求める場合には、Ｇ＊＝Ｇ、ζ＊＝ζ（ｒ−１）／ｄ、ｄ’’は、「（ｄ／２ｍ）１／２の値を切り上げた値」となる。自己同型写像を利用する場合、ｙＬを求める場合とｙＨを求める場合のどちらかでのみ使用されることが多い。そのため、以降では、特に記述がない場合にはｙＬの生成の場合について説明する。
【００５３】
テーブル生成部１３２は、Cheon解析法の要領で、Baby-StepおよびGiant-Stepを実行し、ＴｂテーブルおよびＴｇテーブルを生成する処理部である。特に、テーブル生成部１３２は、Giant-Stepを実行してＴｇテーブルを作成する場合に、楕円曲線演算の一部に、自己同型写像を適用することで、計算量の削減を図る。
【００５４】
自己同型写像をCheon解析法に適用するためには、自己同型写像を生成元ζの指数乗倍で表現する必要がある。自己同型写像を生成元ζの指数乗倍で表すと、（−１）（ｉ）Φ（ｊ）×Ｐ＝ζｄ（ｉ・ｍ＋２・ｃ・ｊ）ｄ’’Ｐとなる。ｄは、ｒ−１の約数であり、このｄは、約数２とｍを含めないように選択された値とする。自己同型写像を適用することで、楕円曲線演算を実行すべき範囲を削減することができる。このように選択すると、ｙＬを求めるのに自己同型写像を使用することになる。
【００５５】
ここで、自己同型写像を適用した場合と適用していない場合との楕円曲線演算を実行すべき範囲について説明する。図７および図８は、自己同型写像を適用した場合と適用していない場合との楕円曲線演算を実行すべき範囲を示す図である。図７の上段は、自己同型写像を適用しない従来のCheon解析法に対応する。図７の下段は、自己同型写像を適用する今回のアイデアに対応する。
【００５６】
図７では、探索範囲を上位ｄと下位（ｒ−１）／ｄに分割する場合を示している。例えば、図７の上段に示すように、（ｒ−１）／ｄの範囲を探索する場合には、（ｒ−１）／ｄの範囲に対して楕円曲線演算を実行し、ｚを算出する必要があった。ｚを算出する場合には、図３で説明したように、ｚをｚＨとｚＬに分割し、Baby-StepおよびGiant-Stepを実行して、ＴｂテーブルとＴｇテーブルとを比較することで、ｚを算出する。
【００５７】
これに対して、自己同型写像を適用すると、（ｒ−１）／ｄの範囲に対して楕円曲線演算を実行する必要がない。図７の下段に示すように、楕円曲線演算を実行する範囲は、（ｒ−１）／ｄ／２ｍでよくなり、残りの範囲は、自己同型写像「（−１）ｉΦｊ」を用いて求めればよい。
【００５８】
図８に示すように、Baby-Stepを実行する範囲は２０ｂとなり、Giang-Stepを実行する範囲は２０ａとなる。Baby-Stepを実行する範囲２０ｂには、自己同型写像を適用する範囲が含まれないので、Cheon解析法と同様にして、Ｔｂテーブルを作成する。これに対して、Giant-Stepを実行する範囲２０ｂには、自己同型写像を適用する範囲が含まれる。このため、Giant-Stepを実行する場合には、楕円曲線演算の一部に自己同型写像を適用してＴｇテーブルを作成する。
【００５９】
テーブル生成部１３２が、Baby-Stepを実行する場合の処理について説明する。テーブル生成部１３２は、ｕ１の値を変化させながら、「ζｄ−ｕ１×ｘｄＧ」を順次算出することで、Ｔｂテーブルを作成する。なお、ｕ１の値域を「０≦ｕ１＜ｄ１’’」とする。
【００６０】
図９は、本実施例１にかかるＴｂテーブルのデータ構造の一例を示す図である。図９に示すように、このＴｂテーブル１４１は、ｋの値と、ｋの値に応じたζｄ−ｋ×ｘｄＧの点とを対応付けて記憶する。Ｔｂテーブル１４１のｋは、ｕ１に対応する値である。
【００６１】
テーブル生成部１３２が、Giang-Stepを実行する場合の処理について説明する。テーブル生成部１３２は、ｖ１、ｉ、ｊの値を順次変化させながら、「（−１）（ｉ）Φ（ｊ）（ζｄｖ１・ｄ１×Ｇ）」を順次算出することで、Ｔｇテーブル１４２を作成する。なお、ｖ１の値域を「０≦ｖ１＜ｄ１’’」とする。ｉの値域を「０、１」とする。ｊの値域を「０≦ｊ＜ｍ−１」とする。
【００６２】
図１０は、本実施例１にかかるＴｇテーブルのデータ構造の一例を示す図である。図１０に示すように、このＴｇテーブル１４２は、ｋ、ｉ、ｊの値と、ｋ、ｉ、ｊの値に応じた（−１）（ｉ）Φ（ｊ）（ζｄｋ・ｄ１×Ｇ）の点とを対応付けて記憶する。Ｔｇテーブルのｋは、ｖ１に対応する値である。
【００６３】
ここで、テーブル生成部１３２の構成について説明する。図１１は、本実施例１にかかるテーブル生成部の構成を示す図である。図１１に示すように、テーブル生成部１３２は、テーブル生成制御部１５０、スカラ倍算部１５１、自己同型写像計算部１５２を有する。
【００６４】
テーブル生成制御部１５０は、スカラ倍算部１５１および自己同型写像計算部１５２を利用して、「ζｄ−ｕ１×ｘｄＧ」、「（−１）（ｉ）Φ（ｊ）（ζｄｖ１・ｄ１×Ｇ）」に対応する値を算出し、Ｔｂテーブル１４１およびＴｇテーブル１４２を作成する処理部である。
【００６５】
テーブル生成制御部１５０は、パラメータｄ１’’、ζ＊、Ｇ＊、ｍ、Ｔ＊を取得する。テーブル生成制御部１５０は、Ｔ＊に応じて、Ｔｂテーブル１４１またはＴｇテーブル１４２を生成すると判定する。Ｔ＊は、Ｔｂテーブル１４１を作成するのか、Ｔｇテーブル１４２を作成するのかを識別する情報である。テーブル生成制御部１５０は、制御部１３５からＴ＊を取得する。
【００６６】
テーブル生成制御部１５０が、Ｔｂテーブル１４１を生成する場合について説明する。テーブル生成制御部１５０は、スカラ倍算部１５１に、ζ＊、Ｇ＊、ｋを順次入力し、スカラ倍算部１５１から（ζ＊）ｋＧ＊を順次取得する。Ｔｂテーブル１４１を生成する場合のｋは、上記ｕ１に対応する。テーブル生成制御部１５０は、ｋと（ζ＊）ｋＧ＊とを対応付けて、Ｔｂテーブル１４１に登録する。
【００６７】
テーブル生成制御部１５０が、Ｔｇテーブル１４２を生成する場合について説明する。テーブル生成制御部１５０は、ζ＊、Ｇ＊、ｋをスカラ倍算部１５１に順次入力し、スカラ倍算部１５１から（ζ＊）ｋＧ＊を順次取得する。Ｔｇテーブル１４２を生成する場合のｋは、上記ｖ１に対応する。テーブル生成制御部１５０は、（ζ＊）ｋＧ＊を取得した後に、ｉ、ｊ、（ζ＊）ｋＧ＊を自己同型写像計算部１５２に順次入力し、自己同型写像計算部１５２から（−１）（ｉ）Φ（ｊ）（（ζ＊）ｋ×Ｇ＊）を取得する。テーブル生成制御部１５０は、ｉとｊとｋと（−１）（ｉ）Φ（ｊ）（（ζ＊）ｋ×Ｇ＊）とを対応付けて、Ｔｇテーブル１４２に登録する。
【００６８】
スカラ倍算部１５１は、テーブル生成制御部１５０から、ζ＊、Ｇ＊、ｋを受け付け、（ζ＊）ｋＧ＊を算出する処理部である。スカラ倍算部１５１は、（ζ＊）ｋＧ＊をテーブル生成制御部１５０に出力する。
【００６９】
自己同型写像計算部１５２は、テーブル生成制御部１５０から、ｉ、ｊ、（ζ＊）ｋＧ＊を受け付け、（−１）（ｉ）Φ（ｊ）（（ζ＊）ｋ×Ｇ＊）を算出する処理部である。自己同型写像計算部１５２は、（−１）（ｉ）Φ（ｊ）（（ζ＊）ｋ×Ｇ＊）をテーブル生成制御部１５０に出力する。
【００７０】
ところで、テーブル生成部１３２は、上記の処理を、未知数ｙの下位部分と、上位部分に対してそれぞれ実行するものとする。未知数ｙの下位部分は、図３に示した（ｒ−１）／ｄの範囲に対応する。また、未知数ｙの上位部分は、図４に示したｄの範囲に対応する。下位部を求める場合には、楕円曲線演算の一部に自己同型写像を適用することで、計算量を削減する。上位部を求める場合には、自己同型写像演算を用いない従来と同様の計算を行う。
【００７１】
図６の説明にもどる。テーブル比較部１３３は、Ｔｂテーブル１４１とＴｇテーブル１４２とを比較して、
ζｄ−ｕ１×ｘｄＧ＝（−１）（ｉ）Φ（ｊ）（ζｄｖ１・ｄ１×Ｇ）
となる（ｕ１、ｖ１、ｉ、ｊ）の組を求める処理部である。テーブル比較部１３３は、求めた（ｕ１、ｖ１、ｉ、ｊ）の組を未知数算出部１３４に出力する。
【００７２】
Ｔｂテーブル１４１、Ｔｇテーブル１４２は、未知数ｙの下位部分、上位部分に対応してそれぞれ作成される。このため、テーブル比較部１３３は、部分毎に、（ｕ１、ｖ１、ｉ、ｊ）の組を未知数算出部１３４に出力する。
【００７３】
未知数演算部１３４は、テーブル比較部１３３から、（ｕ１、ｖ１、ｉ、ｊ）の組を取得し、秘密鍵を算出する。ここでは、未知数ｙの下位部分をｚ、秘密鍵の上位部分をｗとする。
【００７４】
未知数演算部１３４は、下位部分から求められた組（ｕ１、ｖ１、ｉ、ｊ）を基にして、未知数ｙの下位部分をｚ＝ｕ１＋ｖ１・ｄ１’’＋（ｉ・ｍ＋２・ｃ・ｊ）ｄ’’により算出する。この場合には、ｘｄＧ＝ζｄｚＧとなるので、ｘｄ＝ζｄｚとなるｚが求まる。
【００７５】
未知数演算部１３４は、上位部分から求められた組（ｕ２、ｖ２）を基にして、未知数ｙの上位部分をｗ＝ｕ２＋ｖ２・ｄ１’’により算出する。ここで、ｄ’’＝ｄ２（従来値）とする。
【００７６】
未知数演算部１３４は、ｚとｗを求めた後に、ｙ＝ｚ＋ｗ（ｒ−１）／ｄにより求める。秘密鍵ｘとｙとの間には、ｘ＝ζｙの関係がある。未知数演算部１３４は、秘密鍵ｘとｙとの関係から、秘密鍵ｘを求め、求めた秘密鍵ｘの情報を出力部１２０に出力する。
【００７７】
制御部１３５は、パラメータ取得部１３１、テーブル生成部１３２、テーブル比較部１３３、未知数算出部１３４の各部に対して、上記で説明したような動作を行うように制御する処理部である。例えば、制御部１３５は、Ｔ＊をテーブル生成部１３２に入力して、Ｔｂテーブル１４１またはＴｇテーブル１４２を作成させる。そして、Ｔｂテーブル１４１、Ｔｇテーブル１４２が作成された後に、制御部１３５は、テーブル比較部１３３に指示を出し、Ｔｂテーブル１４１とＴｇテーブル１４２とを比較させる。
【００７８】
記憶部１４０は、Ｔｂテーブル１４１およびＴｇテーブル１４２を記憶する記憶部である。Ｔｂテーブル１４１のデータ構造は、図９のものとなる。Ｔｇテーブル１４２のデータ構造は、図１０のものとなる。
【００７９】
次に、本実施例１にかかる処理部１３０の処理手順について説明する。図１２は、本実施例１にかかる処理部の処理手順を示すフローチャートである。例えば、図１２に示す処理は、入力部１１０から、楕円曲線離散対数問題を解く旨の指示を受け付けた場合に実行される。図１２に示すように処理部１３０は、秘密鍵ｘ＝ζｙとし、ｙを上位部分と下位部分に分割する（ステップＳ１０１）。
【００８０】
処理部１３０は、下位部分に対してBaby-Stepを実行し、ζｄ−ｕ１×ｘｄＧ｛０≦ｕ１＜ｄ１’’｝となるＴｂテーブル１４１を作成する（ステップＳ１０２）。処理部１３０は、下位部分に対してGiant-Stepを実行し、ζｄｖ１・ｄ１×Ｇ｛０≦ｖ１＜ｄ１’’｝と、各点の自己同型写像（−１）（ｉ）Φ（ｊ）（ζｄｖ１・ｄ１×Ｇ）を算出し、全ての点からなるＴｇテーブル１４２を作成する（ステップＳ１０３）。
【００８１】
処理部１３０は、Ｔｂテーブル１４１とＴｇテーブル１４２とを比較し、ζｄ−ｕ１×ｘｄＧ＝（−１）（ｉ）Φ（ｊ）（ζｄｖ１・ｄ１×Ｇ）となる（ｕ１、ｖ１、ｉ、ｊ）の組を算出する（ステップＳ１０４）。処理部１３０は、ｚ＝ｕ１＋ｖ１・ｄ１’’＋（ｉ・ｍ＋２・ｃ・ｊ）ｄ’’により、ｙの下位部分ｚを算出する（ステップＳ１０５）。
【００８２】
処理部１３０は、上位部分に対してＢａｂｙ−Ｓｔｅｐを実行し、ζ−ｕ２（ｒ−１）／ｒ×ｘＧ｛０≦ｕ２＜ｄ１’’｝となるＴｂテーブル１４１を作成する（ステップＳ１０６）。処理部１３０は、上位部分に対してＧｉａｎｔ−Ｓｔｅｐを実行し、ζｋ１ζｒ２・ｄ２・（ｒ−１）／ｒ×Ｇ｛０≦ｖ２＜ｄ’’｝となるＴｇを計算し、全ての点からなるＴｇテーブルを作成する（ステップＳ１０７）。
【００８３】
処理部１３０は、ＴｂテーブルとＴｇテーブルとを比較し、ζ−ｕ２（ｒ−１）／ｒ×ｘＧ＝、ζｋ１ζｒ２・ｄ２・（ｒ−１）／ｒ×Ｇとなる（ｕ２、ｖ２）の組を算出する（ステップＳ１０８）。処理部１３０は、ｗ＝ｙＨ＝ｕ２＋ｖ２ｄ’’により、ｙの上位部分ｗを算出する（ステップＳ１０９）。なお、ｄ’’は、ｄ１／２の値を切り上げたものである。
【００８４】
処理部１３０は、ｙ＝ｚ＋ｗ（ｒ−１）／ｄにより、ｙの値を算出する（ステップＳ１１０）。処理部１３０は、ｘ＝ζｙの関係からｘを求め（ステップＳ１１１）、秘密鍵ｘを出力する（ステップＳ１１２）。
【００８５】
次に、本実施例１にかかるテーブル生成部１３２がＴｂテーブル１４１およびＴｇテーブル１４２を生成する処理手順について説明する。図１３は、本実施例１にかかるテーブル生成部の処理手順を示すフローチャートである。
【００８６】
図１３に示すように、テーブル生成部１３２は、パラメータｄ１’’、ζ＊、Ｇ＊、ｍ、Ｔ＊を取得し（ステップＳ２０１）、ｋを初期値に設定する（ステップＳ２０２）。テーブル生成部１３２は、スカラ倍計算（ζ＊）ｋＧ＊を実行し（ステップＳ２０３）、｛ｋ、（ζ＊）ｋＧ＊｝を記憶部１４０に出力する（ステップＳ２０４）。
【００８７】
テーブル生成部１３２は、ｉ＝０〜１、ｊ＝０〜ｍ−１に対して、自己同型写像計算（−１）（ｉ）Φ（ｊ）（（ζ＊）ｋ×Ｇ＊）を実行する（ステップＳ２０５）。テーブル生成部１３２は、｛ｋ、ｉ、ｊ、（−１）（ｉ）Φ（ｊ）（ζ＊）ｋ×Ｇ＊｝を記憶部１４０に出力する（ステップＳ２０６）。
【００８８】
テーブル生成部１３２は、ｋ＝ｋ＋１を算出し（ステップＳ２０７）、ｋの値がｄ’’−１の値よりも大きいか否かを判定する（ステップＳ２０８）。テーブル生成部１３２は、ｋの値がｄ’’−１の値以下の場合には（ステップＳ２０８，Ｎｏ）、ステップＳ２０３に移行する。一方、テーブル生成部１３２は、ｋの値がｄ’’−１の値より大きい場合には（ステップＳ２０８，Ｙｅｓ）、処理を終了する。
【００８９】
次に、本実施例１にかかる暗号解読装置１００の効果について説明する。本実施例１にかかる暗号解読装置１００は、Giant-Stepを実行して、Ｔｂテーブル１４１を生成する場合に、楕円曲線演算の一部に、自己同型写像を適用することで、楕円曲線演算を実行すべき範囲を削減することができる。下位部分の計算量を、従来のCheon解析法と比較して、１／（２ｍ）１／２に削減することができる。例えば、有限体ＧＦ（３ｍ）上の楕円曲線の場合には、ｍ＝１２７であるため、従来のCheon解析法と比較して、下位部分の計算量が（１／１６）１／２＝１／４程度となる。
【００９０】
ところで、図６に示した暗号鍵解読装置１００の構成は一例であり、暗号鍵解読装置１００は、必ずしも図６に示した各処理部を全て有していなくてもよい。例えば、暗号鍵解読装置１００は、分割部と、第１演算部と、第２演算部と、暗号鍵解析部とを有していればよい。
【００９１】
このうち分割部は、楕円曲線離散対数問題の解を楕円曲線上の点に対応する生成元のべき乗で示し、前記生成元のべき乗部分を第１部分と第２部分に分割する処理部である。第１演算部は、第１部分の値を所定の値域で変化させた場合に生成元をべき乗することで算出される値を第１テーブルに格納する処理部である。第２演算部は、第２部分の値を所定の値域で変化させた場合に前記生成元をべき乗することで算出される値と、前記生成元のべき乗部分の一部に自己同型写像を適用した値とを組あわせた値を第２テーブルに格納する処理部である。分割部、第１演算部、第２演算部は、テーブル生成部１３２に対応する。
【００９２】
暗号鍵解析部は、第１テーブルに格納された値と第２テーブルに格納された値とを比較し、一致した値に基づいて前記楕円曲線離散対数問題の解を算出することで暗号鍵を解析する処理部である。この暗号鍵解析部は、テーブル比較部１３３、未知数算出部１３４に対応する。
【実施例２】
【００９３】
ところで、上記の実施例１では、従来のCheon解析法と比較して、計算量を大幅に削減できるものの、Ｔｇテーブル２４２のデータ量が従来のものと比較して約８倍に増えてしまう。以下の実施例２では、データ量が増加させず、計算量を削減することを可能にする暗号鍵解読装置について説明する。
【００９４】
図１４は、本実施例２にかかる暗号鍵解読装置の構成を示す図である。図１４に示すように、この暗号鍵解読装置２００は、入力部２１０、出力部２２０、処理部２３０、記憶部２４０を有する。
【００９５】
このうち、入力部２１０、出力部２２０に関する説明は、図１に示した入力部１１０、出力部１２０に関する説明と同様である。
【００９６】
処理部２３０は、パラメータ取得部２３１、テーブル生成部２３２、テーブル比較部２３３、未知数算出部２３４、制御部２３５を有する。
【００９７】
パラメータ取得部２３１は、入力部２１０からパラメータを取得し、取得したパラメータをテーブル生成部２３２に出力する処理部である。パラメータは、実施例１と同様にして、Ｇ＊、ζ＊、ｍ、ｄ’’が含まれる。なお、パラメータ取得部２３１は、パラメータを記憶部２４０に記憶させておき、ユーザからの指示を受け付けた場合に、記憶部２４０に記憶されたパラメータを取得してもよい。
【００９８】
テーブル生成部２３２は、Cheon解析法の要領で、Baby-StepおよびGiant-Stepを実行し、Ｔｂテーブル２４１およびＴｇテーブル２４２を生成する処理部である。特に、テーブル生成部２３２は、Giant-Stepを実行してＴｂテーブル２４１を作成する場合に、楕円曲線演算の一部に、自己同型写像を適用することで、計算量の削減を図る。
【００９９】
ところで、実施例１のテーブル生成部１３２は、Baby-Stepを実行して、ｕ１の値を「０〜ｄ１’’」まで変化させながら、「ζｄ−ｕ１×ｘｄＧ」を順次算出していた。また、Giant-Stepを実行して、ｖ１の値を「０〜ｄ１’’」まで変化させながら、「ζｄｖ１・ｄ１×Ｇ」を順次算出していた。つまり、実施例１では、ｕ１の値域と、ｖ１の値域は「０〜ｄ１’’」で共通であった。
【０１００】
これに対して、テーブル生成部２３２は、ｕ１の値域と、ｖ１の値域とを不均一に設定する。具体的には、テーブル生成部２３２は、Baby-Stepを実行して、ｕ１の値を「０〜ｄ１ｂ」まで変化させながら、「ζｄ−ｕ１×ｘｄＧ」を順次算出する。ここで、ｄ１ｂ＝（（ｒ−１）／ｄ）１／２である。また、テーブル生成部２３２は、Giant-Stepを実行して、ｖ１の値を「０〜ｄ１ｇ」まで変化させながら、「ζｄｖ１・ｄ１×Ｇ」を順次算出する。ここで、ｄ１ｇ＝（（ｒ−１）／ｄ／２ｍ）／ｄ１ｂ）である。
【０１０１】
Baby-Stepを実行する場合のｕ１の値域０〜ｄ１ｂは、従来のCheon解析法の値域と同じであり、アルゴリズムも共通することから、Ｔｂテーブル２４１の計算量およびデータ量は、従来のものと同じになる。これに対して、Giant-Stepを実行する場合のｖ１の値域は、０〜ｄ１ｇであり、ｄ１ｇ＝ｄ１／２ｍの関係があるため、従来のものと比較して、計算量を約１／２に削減することができる。また、Ｔｇテーブル２４２のデータ量は従来のCheon解析法と同じになる。つまり、本実施例２のテーブル生成部２３２は、従来のCheon解析法と比較した場合には、データ量を増加させることなく、計算量を１／２に削減することができる。
【０１０２】
テーブル生成部が、Baby-Stepを実行する場合の処理について説明する。テーブル生成部２３２は、ｕ１の値を変化させながら、「ζｄ−ｕ１×ｘｄＧ」を順次算出することで、Ｔｂテーブル２４１を作成する。なお、ｕ１の値域は上記のように「０≦ｕ１＜ｄ１ｂ」とする。
【０１０３】
図１５は、本実施例２にかかるＴｂテーブルのデータ構造の一例を示す図である。図１５に示すように、このＴｂテーブル２４１は、ｋの値と、ｋの値に応じたζｄ−ｋ×ｘｄＧの点とを対応付けて記憶する。Ｔｂテーブル２４１のｋは、ｕ１に対応する値である。
【０１０４】
テーブル生成部２３２が、Giang-Stepを実行する場合の処理について説明する。テーブル生成部２３２は、ｖ１、ｉ、ｊの値を順次変化させながら、「
【数５】
」を順次算出することで、Ｔｇテーブル２４２を作成する。なお、ｖ１の値域を「０≦ｖ１＜ｄ１ｇ」とする。ｉの値域を「０、１」とする。ｊの値域を「０≦ｊ＜ｍ−１」とする。
【０１０５】
図１６は、本実施例２にかかるＴｇテーブルのデータ構造の一例を示す図である。図１６に示すように、このＴｇテーブル２４２は、ｋ、ｉ、ｊの値と、ｋ、ｉ、ｊの値に応じた「
【数６】
」の点とを対応付けて記憶する。Ｔｇテーブル２４２でのｋは、ｖ１に対応する値である。
【０１０６】
ここで、テーブル生成部２３２の構成について説明する。図１７は、本実施例２にかかるテーブル生成部の構成を示す図である。図１７に示すように、テーブル生成部２３２は、テーブル生成制御部２５０、スカラ倍算部２５１、自己同型写像計算部２５２を有する。
【０１０７】
テーブル生成制御部２５０は、パラメータｄ１’’、ζ＊、Ｇ＊、ｍ、Ｔ＊を取得する。テーブル生成制御部２５０は、Ｔ＊に応じて、Ｔｂテーブル２４１またはＴｇテーブル２４２を生成すると判定する。Ｔ＊は、Ｔｂテーブル２４１を作成するのか、Ｔｇテーブル２４２を作成するのかを識別する情報である。テーブル生成制御部２５０は、制御部２３５からＴ＊を取得する。
【０１０８】
テーブル生成制御部２５０が、Ｔｂテーブル２４１を生成する場合について説明する。テーブル生成制御部２５０は、スカラ倍算部２５１に、ζ＊、Ｇ＊、ｋを順次入力し、スカラ倍算部２５１から（ζ＊）ｋＧ＊を順次取得する。Ｔｂテーブル２４１を生成する場合のｋは、上記ｕ１に対応する。テーブル生成制御部２５０は、ｋと（ζ＊）ｋＧ＊とを対応付けて、Ｔｂテーブル２４１に登録する。
【０１０９】
テーブル生成制御部２５０が、Ｔｇテーブル２４２を生成する場合について説明する。テーブル生成制御部２５０は、ζ＊、Ｇ＊、ｋをスカラ倍算部２５１に順次入力し、スカラ倍算部２５１から（ζ＊）ｋＧ＊を順次取得する。Ｔｇテーブル２４２を生成する場合のｋは、上記ｖ１・ｄ１ｂに対応する。テーブル生成制御部２５０は、（ζ＊）ｋＧ＊を取得した後に、ｉ、ｊ、（ζ＊）ｋＧ＊を自己同型写像計算部２５２に順次入力し、自己同型写像計算部２５２から（−１）（ｉ）Φ（ｊ）（（ζ＊）ｋ×Ｇ＊）を取得する。テーブル生成制御部２５０は、ｉとｊとｋと（−１）（ｉ）Φ（ｊ）（（ζ＊）ｋ×Ｇ＊）とを対応付けて、Ｔｇテーブル２４２に登録する。
【０１１０】
スカラ倍算部２５１は、テーブル生成制御部２５０から、ζ＊、Ｇ＊、ｋを受け付け、（ζ＊）ｋＧ＊を算出する処理部である。スカラ倍算部２５１は、（ζ＊）ｋＧ＊をテーブル生成制御部２５０に出力する。
【０１１１】
自己同型写像計算部２５２は、テーブル生成制御部２５０から、ｉ、ｊ、（ζ＊）ｋＧ＊を受け付け、（−１）（ｉ）Φ（ｊ）（（ζ＊）ｋ×Ｇ＊）を算出する処理部である。自己同型写像計算部２５２は、（−１）（ｉ）Φ（ｊ）（（ζ＊）ｋ×Ｇ＊）をテーブル生成制御部２５０に出力する。
【０１１２】
ところで、テーブル生成部２３２は、上記の処理を、未知数ｙの下位部分と、上位部分に対してそれぞれ実行するものとする。未知数ｙの下位部分は、図３に示した（ｒ−１）／ｄの範囲に対応する。また、未知数ｙの上位部分は、図４に示したｄの範囲に対応する。いずれの場合も、Giant-Stepを実行する場合に、楕円曲線演算の一部に自己同型写像を適用することで、計算量を削減する。
【０１１３】
図１４の説明に戻る。テーブル比較部２３３は、Ｔｂテーブル２４１とＴｇテーブル２４２とを比較して、
【数７】
となる（ｕ１、ｖ１、ｉ、ｊ）の組を求める処理部である。テーブル比較部２３３は、求めた（ｕ１、ｖ１、ｉ、ｊ）の組を未知数算出部２３４に出力する。
【０１１４】
Ｔｂテーブル２４１、Ｔｇテーブル２４２は、未知数ｙの下位部分、上位部分に対応してそれぞれ作成される。このため、テーブル比較部２３３は、部分毎に、（ｕ１、ｖ１、ｉ、ｊ）の組を未知数算出部２３４に出力する。
【０１１５】
未知数演算部２３４は、テーブル比較部２３３から、（ｕ１、ｖ１、ｉ、ｊ）の組を取得し、秘密鍵を算出する。ここでは、未知数ｙの下位部分をｚ、秘密鍵の上位部分をｗとする。
【０１１６】
未知数演算部２３４は、下位部分から求められた組（ｕ１、ｖ１、ｉ、ｊ）を基にして、未知数ｙの下位部分をｚ＝ｕ１＋ｖ１・ｄ１ｂ＋（ｉ・ｍ＋２・ｃ・ｊ）ｄ’’により算出する。この場合には、ｘｄＧ＝ζｄｚＧとなるので、ｘｄ＝ζｄｚとなるｚが求まる。
【０１１７】
未知数演算部２３４は、上位部分から求められた組（ｕ２、ｖ２）を基にして、未知数ｙの上位部分をｗ＝ｕ２＋ｖ２・ｄ’’により算出する。
【０１１８】
未知数演算部２３４は、ｚとｗを求めた後に、未知数ｙをｙ＝ｚ＋ｗ（ｒ−１）／ｄにより求める。秘密鍵ｘとｙとの間には、ｘ＝ζｙの関係がある。未知数演算部２３４は、秘密鍵ｘとｙとの関係から、秘密鍵ｘを求め、求めた秘密鍵ｘの情報を出力部２２０に出力する。
【０１１９】
制御部２３５は、パラメータ取得部２３１、テーブル生成部２３２、テーブル比較部２３３、未知数算出部２３４の各部に対して、上記で説明したような動作を行うように制御する処理部である。例えば、制御部２３５は、Ｔ＊をテーブル生成部２３２に入力して、Ｔｂテーブル２４１またはＴｇテーブル２４２を作成させる。そして、Ｔｂテーブル２４１、Ｔｂテーブル２４２が作成された後に、制御部２３５は、テーブル比較部２３３に指示を出し、Ｔｂテーブル２４１とＴｇテーブル２４２とを比較させる。
【０１２０】
記憶部２４０は、Ｔｂテーブル２４１およびＴｇテーブル２４２を記憶する記憶部である。Ｔｂテーブル２４１のデータ構造は、図１５のものとなる。Ｔｇテーブル２４２のデータ構造は、図１６のものとなる。
【０１２１】
次に、本実施例２にかかる処理部２３０の処理手順について説明する。図１８は、本実施例２にかかる処理部の処理手順を示すフローチャートである。図１８に示す処理は、入力部２１０から、楕円曲線離散対数問題を解く旨の指示を受け付けた場合に実行される。
【０１２２】
図１８に示すように処理部２３０は、秘密鍵ｘ＝ζｙとし、ｙを上位部分と下位部分に分割する（ステップＳ３０１）。処理部２３０は、下位部分に対してBaby-Stepを実行し、ζｄ−ｕ１×ｘｄＧ｛０≦ｕ１＜ｄ１ｂ｝となるＴｂテーブル２４１を作成する（ステップＳ３０２）。処理部２３０は、下位部分に対してGiant-Stepを実行し、「
【数８】
」｛０≦ｖ１＜ｄ１ｂ｝と、各点の自己同型写像「
【数５】
」を算出し、全ての点からなるＴｇテーブル１４２を作成する（ステップＳ３０３）。
【０１２３】
処理部２３０は、Ｔｂテーブル２４１とＴｇテーブル２４２とを比較し、「
【数７】
」となる（ｕ１、ｖ１、ｉ、ｊ）の組を算出する（ステップＳ３０４）。処理部２３０は、ｚ＝ｕ１＋ｖ１・ｄ１ｂ＋（ｉ・ｍ＋２・ｃ・ｊ）ｄ’’により、ｙの下位部分ｚを算出する（ステップＳ３０５）。
【０１２４】
処理部２３０は、上位部分に対してＢａｂｙ−Ｓｔｅｐを実行し、ζ−ｕ２（ｒ−１）／ｒ×ｘＧ｛０≦ｕ２＜ｄ１’’｝となるＴｂテーブル１４１を作成する（ステップＳ３０６）。処理部２３０は、上位部分に対してＧｉａｎｔ−Ｓｔｅｐを実行し、ζｋ１ζｒ２・ｄ２・（ｒ−１）／ｒ×Ｇ｛０≦ｖ２＜ｄ’’｝となるＴｇを計算し、全ての点からなるＴｇテーブルを作成する（ステップＳ３０７）。
【０１２５】
処理部２３０は、ＴｂテーブルとＴｇテーブルとを比較し、ζ−ｕ２（ｒ−１）／ｒ×ｘＧ＝、ζｋ１ζｒ２・ｄ２・（ｒ−１）／ｒ×Ｇとなる（ｕ２、ｖ２）の組を算出する（ステップＳ３０８）。処理部２３０は、ｗ＝ｙＨ＝ｕ２＋ｖ２ｄ’’により、ｙの上位部分ｗを算出する（ステップＳ３０９）。
【０１２６】
処理部２３０は、ｙ＝ｚ＋ｗ（ｒ−１）／ｄにより、ｙの値を算出する（ステップＳ３１０）。処理部２３０は、ｘ＝ζｙの関係からｘを求め（ステップＳ３１１）、秘密鍵ｘを出力する（ステップＳ３１２）。
【０１２７】
次に、本実施例２にかかる暗号解読装置２００の効果について説明する。本実施例２にかかる暗号解読装置２００は、Giant-Stepを実行して、Ｔｂテーブル２４１を生成する場合に、楕円曲線演算の一部に、自己同型写像を適用する。更に、暗号解読装置２００は、Baby-Stepを実行する場合のｕ１の値域と、Giant-Stepを実行する場合のｖ１の値域とを不均一に設定する。楕円曲線演算に自己同型写像を適応すると、自己同型写像「（−１）（ｉ）Φ（ｊ）」と、「
【数８】
」との全ての組み合わせをＴｇテーブル２４２に格納する必要がある。このため、
【数８】
のｖ１の値域を制限してやれば、「
【数８】
」の演算結果の数が減るので、結果として、自己同型写像「（−１）（ｉ）Φ（ｊ）」と、「
【数８】
」との全ての組み合わせ数が減り、Ｔｇテーブル２４２のデータ量を削減することができる。したがって、本実施例２にかかる暗号解読装置２００によれば、従来のCheon解析法と比較して、テーブル量を増加させることなく、計算量を削減することができる。
【実施例３】
【０１２８】
実施例３にかかる暗号鍵解読装置について説明する。上記実施例１、２では、Giant-Step側に自己同型写像を適用していたが、本実施例３では、Baby-Step側およびGiant-Step側に自己同型写像を適用することで、計算量およびテーブル量を削減する。
【０１２９】
図１９は、本実施例３にかかる暗号鍵解読装置の構成を示す図である。図１９に示すように、この暗号鍵解読装置３００は、入力部３１０、出力部３２０、処理部３３０、記憶部３４０を有する。
【０１３０】
このうち、入力部３１０、出力部３２０に関する説明は、図１に示した入力部１１０、出力部１２０に関する説明と同様である。
【０１３１】
処理部３３０は、パラメータ取得部３３１、テーブル生成部３３２、テーブル比較部３３３、未知数算出部３３４、制御部３３５を有する。
【０１３２】
パラメータ取得部３３１は、入力部３１０からパラメータを取得し、取得したパラメータをテーブル生成部３３２に出力する処理部である。パラメータは、実施例１と同様にして、Ｇ＊、ζ＊、ｍ、ｄ’’が含まれる。なお、パラメータ取得部３３１は、パラメータを記憶部３４０に記憶させておき、ユーザからの指示を受け付けた場合に、記憶部３４０に記憶されたパラメータを取得してもよい。
【０１３３】
テーブル生成部３３２は、Cheon解析法の要領で、Baby-StepおよびGiant-Stepを実行し、Ｔｂテーブル３４１およびＴｇテーブル３４２を生成する処理部である。特に、テーブル生成部３３２は、Baby-StepおよびGiant-Step場合に、楕円曲線演算の一部に、自己同型写像を適用することで、計算量の削減を図る。
【０１３４】
図２０は、本実施例３にかかるテーブル生成部の処理の概要を示す図である。図２０では、検索範囲を上位ｄと下位（ｒ−１）／ｄに分割する場合を示している。テーブル生成部３３２が（ｒ−１）／ｄの範囲に対してBaby-Stepを実行する場合には、範囲３０ａに対して、楕円曲線演算を実行し、範囲４０ｂに対して自己同型写像を実行する。ここで、範囲４０ｂは、自己同型写像「（−１）（ｉ）Φ（ｊ」」の上位部分に対応する。テーブル生成部３３２は、自己同型写像の結果と楕円曲線演算の結果とを組あわせた値を、Ｔｂテーブル３４１に格納する。
【０１３５】
テーブル生成部３３２が（ｒ−１）／ｄの範囲に対してGiant-Stepを実行する場合には、範囲３０ｂに対して、楕円曲線演算を実行し、範囲４０ａに対して自己同型写像を実行する。ここで、範囲４０ｂは、自己同型写像「（−１）ｉΦｊ」の下位部分に対応する。テーブル生成部３３２は、自己同型写像の結果と楕円曲線演算の結果とを組あわせた値を、Ｔｇテーブル３４２に格納する。
【０１３６】
テーブル生成部３３２が、Baby-Stepを実行する場合の処理について説明する。テーブル生成部３３２は、ｕ１、ｉｂ、ｊｂの値を順次変化させながら、「（−１）（ｉｂ）Φ（ｊｂ）（ζｄｕ１×Ｇ）」を順次計算し、Ｔｂテーブル３４１を作成する。ただし、ｉ、ｊの選択条件を、「−（２ｍ）１／２＜（ｉ・ｍ＋ｊ・ｃ・２）ｍｏｄ ２ｍ≦０」とする。すなわち、テーブル生成部３３２は、上記選択条件をみたすｉ、ｊの組に対応する「（−１）（ｉｂ）Φ（ｊｂ）（ζｄｕ１×Ｇ）」の値のみを算出する。なお、ｕ１の値域を「０≦ｕ１＜ｄ１’’」とする。
【０１３７】
図２１は、本実施例３にかかるＴｂテーブルのデータ構造の一例を示す図である。図２１に示すように、このＴｂテーブル３４１は、ｋ、ｉ、ｊの値と、ｋ、ｉ、ｊの値に応じた（−１）（ｉ）Φ（ｊ）（ζｄ−ｋｘｄＧ）の点とを対応付けて記憶する。Ｔｂテーブル３４１のｋは、ｕ１に対応する値である。ｉ、ｊはそれぞれ、ｉｂ、ｊｂに対応する。
【０１３８】
テーブル生成部３３２が、Giant-Stepを実行する場合の処理について説明する。テーブル生成部３３２は、ｖ１、ｉｇ、ｊｇの値を順次変化させながら、「（−１）（ｉｇ）Φ（ｊｇ）（ζｄｖ１・ｄ’’×Ｇ）」を順次計算し、Ｔｂテーブル３４２を作成する。ただし、ｉ、ｊの選択条件を「（ｍ・ｉｇ＋２ｃ・ｊｇ） ｍｏｄ ２ｍ＝０」とする。すなわち、テーブル生成部３３２は、上記選択条件を満たすｉ、ｊの組に対応する「（−１）（ｉｇ）Φ（ｊｇ）（ζｄｖ１・ｄ’’×Ｇ）」の値のみを算出する。なお、ｖ１の値域を「０≦ｖ１＜ｄ１’’」とする。
【０１３９】
図２２は、本実施例３にかかるＴｇテーブルのデータ構造の一例を示す図である。図２２に示すように、このＴｇテーブル３４２は、ｋ、ｉ、ｊの値と、ｋ、ｉ、ｊの値に応じた（−１）（ｉ）Φ（ｊ）（ζｄ−ｋ・ｄ１Ｇ）の点とを対応付けて記憶する。Ｔｇテーブル３４２のｋは、ｖ１に対応する値である。ｉ、ｊはそれぞれ、ｉｇ、ｊｇに対応する。
【０１４０】
ここで、テーブル生成部３３２の構成について説明する。図２３は、本実施例３にかかるテーブル生成部の構成を示す図である。図２３に示すように、テーブル生成部２３２は、テーブル生成制御部３５０、スカラ倍算３５１、自己同型写像計算部３５２、自己同型写像選択部３５３を有する。
【０１４１】
テーブル生成制御部３５０は、パラメータｄ１’’、ζ＊、Ｇ＊、ｍ、Ｔ＊、ｉ，ｊの選択条件を取得する。このうち、ｉ，ｊの選択条件は、「−（２ｍ）１／２＜（ｉ・ｍ＋ｊ・ｃ・２）ｍｏｄ ２ｍ≦０」および「（ｍ・ｉｇ＋２ｃ・ｊｇ） ｍｏｄ ２ｍ＝０」である。
【０１４２】
テーブル生成制御部３５０は、Ｔ＊に応じて、Ｔｂテーブル３４１またはＴｇテーブル３４２を生成すると判定する。Ｔ＊は、Ｔｂテーブル３４１を作成するのか、Ｔｇテーブル３４２を作成するのかを識別する情報である。テーブル生成制御部３５０は、制御部２３５からＴ＊を取得する。
【０１４３】
テーブル生成制御部３５０が、Ｔｂテーブル３４１を生成する場合について説明する。テーブル生成制御部３５０は、スカラ倍算３５１に、ζ＊、Ｇ＊、ｋを順次入力し、スカラ倍算部３５１から（ζ＊）ｋＧ＊を順次取得する。Ｔｂテーブル３４１を生成する場合のｋは、上記ｕ１に対応する。
【０１４４】
テーブル生成制御部３５０は、（ζ＊）ｋＧ＊を取得した後に、ｉ、ｊ、（ζ＊）ｋＧ＊を自己同型写像計算部３５２に順次入力し、自己同型写像計算部３５２から（−１）（ｉ）Φ（ｊ）（（ζ＊）ｋ×Ｇ＊）を取得する。テーブル生成制御部３５０は、ｉとｊとｋと（−１）（ｉ）Φ（ｊ）（（ζ＊）ｋ×Ｇ＊）とを対応付けて、Ｔｂテーブル３４１に登録する。
【０１４５】
なお、テーブル生成制御部３５０は、ｉ、ｊの選択条件と、ｉ、ｊの組とを自己同型写像選択部３５３に入力し、ｉ、ｊの組が、ｉ、ｊの選択条件を満たしている場合に、かかるｉ、ｊの組と（ζ＊）ｋＧ＊を自己同型写像計算部３５２に入力する。Ｔｂテーブル３４１を生成する場合の、ｉ、ｊの選択条件は、「−（２ｍ）１／２＜（ｉ・ｍ＋ｊ・ｃ・２）ｍｏｄ ２ｍ≦０」である。
【０１４６】
テーブル生成制御部３５０が、Ｔｇテーブル３４２を生成する場合について説明する。テーブル生成部３５０は、スカラ倍算部３５１に、ζ＊、Ｇ＊、ｋを順次入力し、スカラ倍算部２５１から（ζ＊）ｋＧ＊を順次取得する。Ｔｇテーブル３４２を生成する場合のｋは、上記ｖ１に対応する。
【０１４７】
テーブル生成制御部３５０は、（ζ＊）ｋＧ＊を取得した後に、ｉ、ｊ、（ζ＊）ｋＧ＊を自己同型写像計算部３５２に順次入力し、自己同型写像計算部３５２から（−１）（ｉ）Φ（ｊ）（（ζ＊）ｋ×Ｇ＊）を取得する。テーブル生成制御部３５０は、ｉとｊとｋと（−１）（ｉ）Φ（ｊ）（（ζ＊）ｋ×Ｇ＊）とを対応付けて、Ｔｇテーブル３４２に登録する。
【０１４８】
なお、テーブル生成制御部３５０は、ｉ、ｊの選択条件と、ｉ、ｊの組とを自己同型写像選択部３５３に入力し、ｉ、ｊの組が、ｉ、ｊの選択条件を満たしている場合に、かかるｉ、ｊの組と（ζ＊）ｋＧ＊を自己同型写像計算部３５２に入力する。Ｔｇテーブル３４１を生成する場合の、ｉ、ｊの選択条件は、「（ｍ・ｉｇ＋２ｃ・ｊｇ） ｍｏｄ ２ｍ＝０」である。
【０１４９】
ところで、テーブル生成部３３２は、上記の処理を、未知数ｙの下位部分と、上位部分に対してそれぞれ実行するものとする。図３に示した（ｒ−１）／ｄの範囲に対応する。また、未知数ｙの上位部分は、図４に示したｄの範囲に対応する。いずれの場合も、Baby-StepおよびGiant-Stepを実行する場合に、楕円曲線演算の一部に自己同型写像を適用することで、計算量を削減する。
【０１５０】
図１９の説明に戻る。テーブル比較部３３３は、Ｔｂテーブル３４１とＴｇテーブル３４２とを比較して、
（−１）（ｉｂ）Φ（ｊｂ）（ζｄｕ１×Ｇ）＝（−１）（ｉｇ）Φ（ｊｇ）（ζｄｖ１・ｄ’’×Ｇ）
となる（ｕ１、ｖ１、ｉｂ、ｊｂ、ｉｇ、ｊｇ）の組を求める処理部である。テーブル比較部３３３は、求めた（ｕ１、ｖ１、ｉｂ、ｊｂ、ｉｇ、ｊｇ）の組を未知数算出部３３４に出力する。
【０１５１】
未知数演算部３３４は、テーブル比較部３３３から、（ｕ１、ｖ１、ｉｂ、ｊｂ、ｉｇ、ｊｇ）の組を取得し、秘密鍵を算出する。ここでは、未知数ｙの下位部分をｚ、秘密鍵の上位部分をｗとする。
【０１５２】
未知数演算部３３４は、下位部分から求められた組（ｕ１、ｖ１、ｉｂ、ｊｂ、ｉｇ、ｊｇ）を基にして、未知数ｙの下位部分ｚを求める。ｚは、ｚ＝ｕ１＋（ｉｂ・ｍ＋２・ｃ・ｊｂ）＋ｖ１・ｄ１’’＋（ｉｇ・ｍ＋２・ｃ・ｊｇ）・ｄ’’により求められる。この場合には、ｘｄＧ＝ζｄｚＧとなるので、ｘｄ＝ζｄｚとなるｚが求まる。
【０１５３】
未知数演算部３３４は、上位部分から求められた組（ｕ２、ｖ２）を基にして、未知数ｙの上位部分をｗ＝ｕ２＋ｖ２・ｄ’’により算出する。
【０１５４】
未知数演算部３３４は、ｚとｗを求めた後に、ｙ＝ｚ＋ｗ（ｒ−１）／ｄにより求める。秘密鍵ｘとｙとの間には、ｘ＝ζｙの関係がある。未知数演算部３３４は、秘密鍵ｘとｙとの関係から、秘密鍵ｘを求め、求めた秘密鍵ｘの情報を出力部３２０に出力する。
【０１５５】
制御部３３５は、パラメータ取得部３３１、テーブル生成部３３２、テーブル比較部３３３、未知数算出部３３４の各部に対して、上記で説明したような動作を行うように制御する処理部である。例えば、制御部３３５は、Ｔ＊をテーブル生成部３３２に入力して、Ｔｂテーブル３４１またはＴｇテーブル３４２を作成させる。そして、Ｔｂテーブル３４１、Ｔｂテーブル３４２が作成された後に、制御部３３５は、テーブル比較部３３３に指示を出し、Ｔｂテーブル３４１とＴｇテーブル３４２とを比較させる。
【０１５６】
記憶部３４０は、Ｔｂテーブル３４１およびＴｇテーブル３４２を記憶する記憶部である。Ｔｂテーブル３４１のデータ構造は、図２１に示すものとなる。Ｔｇテーブル３４２のデータ構造は、図２２に示すものとなる。
【０１５７】
次に、本実施例３にかかる処理部３３０の処理手順について説明する。図２４は、本実施例３にかかる処理部の処理手順を示すフローチャートである。例えば、図２４に示す処理は、入力部３１０から、楕円曲線離散対数問題を解く旨の指示を受け付けた場合に実行される。図２４に示すように処理部３３０は、秘密鍵ｘ＝ζｙとし、ｙを上位部分と下位部分に分割する（ステップＳ４０１）。
【０１５８】
処理部３３０は、下位部分に対してBaby-Stepを実行し、ζｄ−ｕ１×ｘｄＧ｛０≦ｕ１＜ｄ１’’｝と、各点の自己同型写像（−１）（ｉｂ）Φ（ｊｂ）（ζｄ−ｕ１×ｘｄＧ）を算出し、全ての点からなるＴｂテーブル３４１を作成する（ステップＳ４０２）。
【０１５９】
処理部３３０は、計算した点のうち、ｉｂ、ｊｂの組が、「−（２ｍ）１／２＜（ｉｂ・ｍ＋２・ｃ・ｊｂ）ｍｏｄ ２ｍ≦０」を満たす点だけＴｂテーブル３４１に格納する（ステップＳ４０３）。
【０１６０】
処理部３３０は、下位部分に対してGiant-Stepを実行し、ζｄｖ１・ｄ１’’×Ｇ｛０≦ｖ１＜ｄ１’’｝と、各点の自己同型写像（−１）（ｉｇ）Φ（ｊｇ）（ζｄｖ１・ｄ１’’×Ｇ）を算出し、全ての点からなるＴｇテーブル３４２を作成する（ステップＳ４０４）。
【０１６１】
処理部３３０は、計算した点のうち、ｉｇ、ｊｇの組が、（ｍ・ｉｇ＋２ｃ・ｊｇ） ｍｏｄ ２ｍ＝０」となる点だけＴｇテーブル３４２に格納する（ステップＳ４０５）。
【０１６２】
処理部３３０は、Ｔｂテーブル３４１とＴｇテーブル３４２とを比較し、（−１）（ｉｂ）Φ（ｊｂ）（ζｄ−ｕ１×ｘｄＧ）＝（−１）（ｉｇ）Φ（ｊｇ）（ζｄｖ１・ｄ１’’×Ｇ）となる（ｕ１、ｖ１、ｉｂ、ｊｂ、ｉｇ、ｊｇ）の組を算出する（ステップＳ４０６）。処理部３３０は、ｚ＝ｕ１＋（ｉｂ・ｍ＋２・ｃ・ｊｂ）＋ｖ１・ｄ１’’＋（ｉｇ・ｍ＋２・ｃ・ｊｇ）・ｄ’’により、ｚを算出する（ステップＳ４０７）。
【０１６３】
処理部３３０は、上位部分に対してBaby-Stepを実行し、上位部分に対してＢａｂｙ−Ｓｔｅｐを実行し、ζ−ｕ２（ｒ−１）／ｒ×ｘＧ｛０≦ｕ２＜ｄ１’’｝となるＴｂテーブル１４１を作成する（ステップＳ４０８）。
【０１６４】
処理部３３０は、上位部分に対してＧｉａｎｔ−Ｓｔｅｐを実行し、ζｋ１ζｒ２・ｄ２・（ｒ−１）／ｒ×Ｇ｛０≦ｖ２＜ｄ’’｝となるＴｇを計算し、全ての点からなるＴｇテーブルを作成する（ステップＳ４０９）。
【０１６５】
処理部３３０は、ＴｂテーブルとＴｇテーブルとを比較し、ζ−ｕ２（ｒ−１）／ｒ×ｘＧ＝、ζｋ１ζｒ２・ｄ２・（ｒ−１）／ｒ×Ｇとなる（ｕ２、ｖ２）の組を算出する（ステップＳ４１０）。処理部３３０は、ｗ＝ｙＨ＝ｕ２＋ｖ２ｄ’’により、ｙの上位部分ｗを算出する（ステップＳ４１１）。
【０１６６】
処理部３３０は、ｙ＝ｚ＋ｗ（ｒ−１）／ｄにより、ｙの値を算出する（ステップＳ４１２）。処理部３３０は、ｘ＝ζｙの関係からｘを求め（ステップＳ４１３）、秘密鍵ｘを出力する（ステップＳ４１４）。
【０１６７】
次に、本実施例３にかかるテーブル生成部３３２がＴｂテーブル３４１およびＴｇテーブル３４２を生成する処理手順について説明する。図２５は、本実施例３にかかるテーブル生成部の処理手順を示すフローチャートである。
【０１６８】
図２５に示すように、テーブル生成部３３２は、パラメータｄ１’’、ζ＊、Ｇ＊、ｍ、Ｔ＊、（ｉ、ｊ）の条件を取得し（ステップＳ５０１）、ｋを初期値に設定する（ステップＳ５０２）。テーブル生成部３３２は、スカラ倍計算（ζ＊）ｋＧ＊を実行する（ステップＳ５０３）。
【０１６９】
テーブル生成部３３２は、（ｉ、ｊ）の条件を満たすｉ＝０〜１、ｊ＝０〜ｍ−１に対して、自己同型写像計算（−１）（ｉ）Φ（ｊ）（（ζ＊）ｋＧ＊）を実行する（ステップＳ５０４）。テーブル生成部３３２は、｛ｉ、ｊ、ｋ、（−１）（ｉ）Φ（ｊ）（（ζ＊）ｋＧ＊）｝を記憶部３４０に出力する（ステップＳ５０５）。
【０１７０】
テーブル生成部３３２は、ｋ＝ｋ＋１を算出し（ステップＳ５０６）、ｋの値がｄ’’−１の値よりも大きいか否かを判定する（ステップＳ５０７）。テーブル生成部３３２は、ｋの値がｄ’’−１の値以下の場合には（ステップＳ５０７，Ｎｏ）、ステップＳ５０３に移行する。一方、テーブル生成部３３２は、ｋの値がｄ’’−１の値より大きい場合には（ステップＳ５０７，Ｙｅｓ）、処理を終了する。
【０１７１】
次に、本実施例３にかかる暗号解読装置３００の効果について説明する。本実施例３にかかる暗号解読装置３００は、Baby-StepおよびGiant-Stepを実行する場合に、楕円曲線演算の一部に、自己同型写像を適用することで、楕円曲線演算を実行すべき範囲を削減することができる。この結果、楕円曲線離散対数問題を解くための計算量を、従来のCheon解析法と比較して、１／（２ｍ）１／２に削減することができる。例えば、有限体ＧＦ（３ｍ）上の楕円曲線の場合には、ｍ＝１２７であるため、従来のCheon解析法と比較して、計算量が１／１６となる。
【０１７２】
また、本実施例３にかかる暗号装置３００は、ｉ、ｊの選択条件を満たさない、ｉ＝０〜１、ｊ＝０〜ｍ−１の組あわせに対応する自己同型写像の計算結果を、Ｔｂテーブル３４１、Ｔｇテーブル３４２に記憶しない。この結果、Ｔｂテーブル３４１、Ｔｇテーブル３４２のデータ量を、従来のCheon解析法と同量のデータ量に抑えることができる。
【０１７３】
次に、従来のCheon解析法、実施例１〜３の楕円演算回数、テーブルのデータ量の比較結果を示す。図２６および図２７は、従来のCheon解析法、実施例１〜３の楕円演算回数、テーブルのデータ量の比較結果を示す図である。
【０１７４】
図２６に示すように、従来のCheon解析法の楕円演算回数を１とすると、実施例１の楕円演算回数は１／（２ｍ）１／２となり、実施例２の楕円演算回数は１／２となり、実施例３の楕円演算回数は１／（２ｍ）１／２となる。また、従来のCheon解析法のテーブル量を１とすると、実施例１のテーブル量は１／（２ｍ）１／２となり、実施例２のテーブル量は１、実施例３のテーブル量は１となる。
【０１７５】
有限体ＧＦ（３１２７）上の楕円曲線の場合の、従来のCheon解析法、実施例１〜３の楕円演算回数、テーブルのデータ量の比較結果を示す。図２７に示すように、従来のCheon解析法の楕円演算回数を１とすると、実施例１の楕円演算回数は約１／１６となり、実施例２の楕円演算回数は約１／２となり、実施例３の楕円演算回数は約１／１６となる。また、従来のCheon解析法のテーブル量を１とすると、実施例１のテーブル量は約８倍となり、実施例２、３のテーブル量はほぼ同じとなる。
【０１７６】
理論値では、楕円演算回数で評価したが、実際のテーブル作成は自己同型写像の計算も処理時間がかかる。そこで、ここでは一例として、有限体ＧＦ（３１２７）上の楕円曲線で従来のCheon解析法、実施例３のテーブル作成時間の実験結果について説明する。図２８は、テーブル作成時間とテーブル量とを示す図である。
【０１７７】
図２８に示すように、従来のCheon解析法では、テーブル作成時間が７時間、テーブル量が１５．７８MByteとなる。これに対して、実施例３では、テーブル作成時間が４４分、テーブル量が１５．８５MByteとなる。したがって、実施例３は、従来のCheon解析法と比較して、１／９．５倍の時間でテーブルを作成することができ、テーブル量は１．００４倍でほとんど変わらないことが分かる。
【０１７８】
また、上記の各実施例で説明した暗号鍵解読装置１００、２００、３００の各種の処理は、あらかじめ用意されたプログラムをパーソナルコンピュータやワークステーションなどのコンピュータシステムで実行することによって実現することもできる。そこで、以下では、図２９を用いて、上記の実施例で説明した暗号鍵解読装置１００、２００、３００と同様の機能を有する暗号鍵解読プログラムを実行するコンピュータの一例を説明する。図２９は、暗号鍵解読プログラムを実行するコンピュータを示す図である。
【０１７９】
同図に示すように、暗号鍵解読装置１００、２００としてコンピュータ４００は、入出力制御部４１０、ＨＤＤ（Hard Disk Drive）４２０、ＲＡＭ（Random Access Memory）４３０およびＣＰＵ（Central Processing Unit）４４０を有する。各装置４１０〜４４０は、バス４５０で接続して構成される。
【０１８０】
ここで、入出力制御部４１０は、各種情報の入出力を制御する。ＨＤＤ４２０は、ＣＰＵ４４０による各種処理の実行に必要な情報を記憶する。ＲＡＭ４３０は、各種情報を一時的に記憶する。ＣＰＵ４４０は、各種演算処理を実行する。
【０１８１】
そして、ＨＤＤ４２０には、暗号鍵解読システムデータがあらかじめ記憶されている。この暗号鍵解読システムデータは、図６、図１４、図１９に示した暗号鍵解読装置１００、２００、３００の各処理部と同様の機能を発揮する暗号鍵解読プログラムを含む。また、暗号鍵解読システムデータは、処理に必要な各種パラメータを含む暗号鍵解読用データを含む。なお、この暗号鍵解読システムデータを適宜分散させて、ネットワークを介して通信可能に接続された他のコンピュータの記憶部に記憶させておくこともできる。
【０１８２】
そして、ＣＰＵ４４０が、この暗号鍵解読システムデータをＨＤＤ４２０から読み出してＲＡＭ４３０に展開することにより、暗号鍵解読システムデータは暗号鍵解読システムとして機能するようになる。この暗号鍵解読システムには暗号鍵解読プロセスが含まれる。
【０１８３】
すなわち、暗号鍵解読システムやそれに搭載された暗号鍵解読プロセスは、暗号鍵解読用データをＨＤＤ４２０から読み出して、ＲＡＭ４３０において自身に割り当てられた領域に展開し、この展開したデータ等に基づいて各種処理を実行する。
【０１８４】
なお、暗号鍵解読システム及び暗号鍵解読プロセスは、図６、図１４、図１９に示した各機能部において実行される処理に対応する。例えば、暗号鍵解読プロセスは、パラメータ取得部１３１、テーブル生成部１３２、テーブル比較部１３３、未知数算出部１３４に対応する。
【０１８５】
なお、上記した暗号鍵解読プログラムについては、必ずしも最初からＨＤＤ４２０に記憶させておく必要はない。
【０１８６】
例えば、コンピュータ４００に挿入されるフレキシブルディスク（ＦＤ）、ＣＤ−ＲＯＭ、ＤＶＤディスク、光磁気ディスク、ＩＣカードなどの「可搬用の物理媒体」に各プログラムを記憶させておく。そして、コンピュータ４００がこれらから各プログラムを読み出して実行するようにしてもよい。
【０１８７】
さらには、公衆回線、インターネット、ＬＡＮ、ＷＡＮなどを介してコンピュータ４００に接続される「他のコンピュータ（またはサーバ）」などに各プログラムを記憶させておく。そして、コンピュータ４００がこれらから各プログラムを読み出して実行するようにしてもよい。
【０１８８】
また、図示した各装置の各構成要素は機能概念的なものであり、必ずしも物理的に図示の如く構成されていることを要しない。すなわち、各装置の分散・統合の具体的状態は図示のものに限られず、その全部または一部を、各種の負荷や使用状況などに応じて、任意の単位で機能的または物理的に分散・統合して構成することができる。例えば、図６に示すテーブル生成部１３２とテーブル比較部１３３とが統合されてもよい。また、テーブル比較部１３３と未知数算出部１３４とが統合されてもよい。
【０１８９】
なお、図６、図１４、図１９に示した処理部１３０、２３０、３３０は、例えば、ＡＳＩＣ（Application Specific Integrated Circuit）や、ＦＰＧＡ（Field Programmable Gate Array）などの集積装置に対応する。または、各処理部１３０、２３０、３３０は、ＣＰＵやＭＰＵ（Micro Processing Unit）等の電子回路に対応する。また、図６、図１４、図１９に示した記憶部１４０、２４０、３４０は、例えば、ＲＡＭ、ＲＯＭ（Read Only Memory）、フラッシュメモリ（Flash Memory）などの半導体メモリ素子、またはハードディスク、光ディスクなどの記憶装置に対応する。
【０１９０】
以上の各実施例を含む実施形態に関し、さらに以下の付記を開示する。
【０１９１】
（付記１）コンピュータが、
楕円曲線離散対数問題の解を楕円曲線上の点に対応する生成元のべき乗で示し、前記生成元のべき乗部分を第１部分と第２部分に分割する分割ステップと、
前記第１部分の値を所定の値域で変化させた場合に前記生成元をべき乗することで算出される値を第１テーブルに格納する第１演算ステップと、
前記第２部分の値を所定の値域で変化させた場合に前記生成元をべき乗することで算出される値と、前記生成元のべき乗部分の一部に自己同型写像を適用した値とを組あわせた値を第２テーブルに格納する第２演算ステップと、
前記第１テーブルに格納された値と前記第２テーブルに格納された値とを比較し、一致した値に基づいて前記楕円曲線離散対数問題の解を算出することで暗号鍵を解析する暗号鍵解析ステップと
を実行することを特徴とする暗号鍵解析方法。
【０１９２】
（付記２）前記第２演算ステップは、前記第１演算ステップが変化させる所定の値域とは異なる値域によって、前記第１部分の値を変化させた場合に、前記生成元をべき乗することで算出される値と、前記生成元のべき乗部分の一部に自己同型写像を適用した値とを組あわせた値を第２テーブルに格納することを特徴とする付記１に記載の暗号鍵解析方法。
【０１９３】
（付記３）前記第１演算ステップは、前記生成元のべき乗部分の一部に自己同型写像を適用した値のうち所定の条件を満たす値と、前記第２部分の値を所定の値域で変化させた場合に前記生成元をべき乗することで算出される値とを組あわせた値を前記第１テーブルに格納し、前記第２演算ステップは、前記生成元のべき乗部分の一部に自己同型写像を適用した値のうち所定の条件を満たす値と、前記第１部分の値を所定の値域で変化させた場合に前記生成元をべき乗することで算出される値とを組あわせた値を前記第２テーブルに格納することを特徴とする付記１または２に記載の暗号鍵解析方法。
【０１９４】
（付記４）前記分割ステップは、前記生成元のべき乗部分を上位部と下位部にわけ、前記上位部および下位部分をそれぞれ、第１部分と第２部分に分割し、前記第２演算ステップは、前記上位部の第２部分または前記下位部の第２部分の内どちらか一方に、自己同型写像を適用することを特徴とする付記１、２または３に記載の暗号鍵解析方法。
【０１９５】
（付記５）楕円曲線離散対数問題の解を楕円曲線上の点に対応する生成元のべき乗で示し、前記生成元のべき乗部分を第１部分と第２部分に分割する分割部と、
前記第１部分の値を所定の値域で変化させた場合に前記生成元をべき乗することで算出される値を第１テーブルに格納する第１演算部と、
前記第２部分の値を所定の値域で変化させた場合に前記生成元をべき乗することで算出される値と、前記生成元のべき乗部分の一部に自己同型写像を適用した値とを組あわせた値を第２テーブルに格納する第２演算部と、
前記第１テーブルに格納された値と前記第２テーブルに格納された値とを比較し、一致した値に基づいて前記楕円曲線離散対数問題の解を算出することで暗号鍵を解析する暗号鍵解析部と
を備えたことを特徴とする暗号鍵解析装置。
【０１９６】
（付記６）前記第２演算部は、前記第１演算部が変化させる所定の値域とは異なる値域によって、前記第１部分の値を変化させた場合に、前記生成元をべき乗することで算出される値と、前記生成元のべき乗部分の一部に自己同型写像を適用した値とを組あわせた値を第２テーブルに格納することを特徴とする付記５に記載の暗号鍵解析装置。
【０１９７】
（付記７）前記第１演算部は、前記生成元のべき乗部分の一部に自己同型写像を適用した値のうち所定の条件を満たす値と、前記第２部分の値を所定の値域で変化させた場合に前記生成元をべき乗することで算出される値とを組あわせた値を前記第１テーブルに格納し、前記第２演算部は、前記生成元のべき乗部分の一部に自己同型写像を適用した値のうち所定の条件を満たす値と、前記第１部分の値を所定の値域で変化させた場合に前記生成元をべき乗することで算出される値とを組あわせた値を前記第３テーブルに格納することを特徴とする付記５または６に記載の暗号鍵解析装置。
【０１９８】
（付記８）前記分割部は、前記生成元のべき乗部分を上位部と下位部にわけ、前記上位部および下位部分をそれぞれ、第１部分と第２部分に分割し、前記第２演算部は、前記上位部の第２部分または前記下位部の第２部分の内どちらか一方に、自己同型写像を適用することを特徴とする付記５、６または７に記載の暗号鍵解析装置。
【０１９９】
（付記９）コンピュータに
楕円曲線離散対数問題の解を楕円曲線上の点に対応する生成元のべき乗で示し、前記生成元のべき乗部分を第１部分と第２部分に分割する分割手順と、
前記第１部分の値を所定の値域で変化させた場合に前記生成元をべき乗することで算出される値を第１テーブルに格納する第１演算手順と、
前記第２部分の値を所定の値域で変化させた場合に前記生成元をべき乗することで算出される値と、前記生成元のべき乗部分の一部に自己同型写像を適用した値とを組あわせた値を第２テーブルに格納する第２演算手順と、
前記第１テーブルに格納された値と前記第２テーブルに格納された値とを比較し、一致した値に基づいて前記楕円曲線離散対数問題の解を算出することで暗号鍵を解析する暗号鍵解析手順と
を実行させることを特徴とする暗号鍵解析プログラム。
【０２００】
（付記１０）前記第２演算手順は、前記第１演算ステップが変化させる所定の値域とは異なる値域によって、前記第１部分の値を変化させた場合に、前記生成元をべき乗することで算出される値と、前記生成元のべき乗部分の一部に自己同型写像を適用した値とを組あわせた値を第２テーブルに格納することを特徴とする付記９に記載の暗号鍵解析プログラム。
【０２０１】
（付記１１）前記第１演算手順は、前記生成元のべき乗部分の一部に自己同型写像を適用した値のうち所定の条件を満たす値と、前記第２部分の値を所定の値域で変化させた場合に前記生成元をべき乗することで算出される値とを組あわせた値を前記第１テーブルに格納し、前記第２演算手順は、前記生成元のべき乗部分の一部に自己同型写像を適用した値のうち所定の条件を満たす値と、前記第１部分の値を所定の値域で変化させた場合に前記生成元をべき乗することで算出される値とを組あわせた値を前記第２テーブルに格納することを特徴とする付記９または１０に記載の暗号鍵解析プログラム。
【０２０２】
（付記１２）前記分割手順は、前記生成元のべき乗部分を上位部と下位部にわけ、前記上位部および下位部分をそれぞれ、第１部分と第２部分に分割し、前記第２演算手順は、前記上位部の第２部分または前記下位部の第２部分の内どちらか一方に、自己同型写像を適用することを特徴とする付記９、１０または１１に記載の暗号鍵解析プログラム。
【符号の説明】
【０２０３】
１３１ パラメータ取得部
１３２ テーブル生成部
１３３ テーブル比較部
１３４ 未知数算出部
１３５ 制御部
【技術分野】
【０００１】
本発明は、暗号鍵解析方法、暗号鍵解析装置および暗号鍵解析プログラムに関する。
【背景技術】
【０００２】
近年、ネットショッピングやネットバンキングが普及している。ネットショッピングやネットバンキングにおいて通信を行う場合には、情報漏洩などを防止するために、ＳＳＬ（Secure Socket Layer）／ＴＬＳ（Transport Layer Security）等の暗号技術が用いられる。暗号化方式を大別すると共通鍵暗号と公開鍵暗号に分類することができる。
【０００３】
このうち、共通鍵暗号は、送信者と受信者とが同じ鍵を持つことにより暗号通信をおこなう方式である。すなわち、共通鍵暗号では、送信者は、あるメッセージを秘密の暗号鍵に基づいて暗号化して受信者に送る。受信者は、この暗号鍵を用いて暗号文を復号し、メッセージを入手する。
【０００４】
公開鍵暗号は、対になる２つの鍵を使ってデータの暗号化、復号をおこなう方式である。すなわち、送信者は受信者によって公開されている公開鍵でメッセージを暗号化して送信する。これに対して、受信者は、暗号化された暗号化されたメッセージを秘密鍵で復号する。公開鍵は、メッセージを暗号化するための鍵であり、秘密鍵は、公開鍵により暗号化された情報を復号するための鍵である。公開鍵で暗号化された情報は、対の秘密鍵でのみ復号することができる。
【０００５】
公開鍵暗号は、公開鍵を公開しても安全性を確保できるようにするために、数学的に難しいとされている問題に基づいて設計されている。例えば、公開鍵暗号には、ＲＳＡ（Rivest Shamir Adleman）暗号、エルガマル暗号、楕円曲線暗号（Elliptic Curve Cryptosystem）がある。
【０００６】
ＲＳＡ暗号は、素因数分解問題と呼ばれる数学的問題の困難性に基づいている。エルガマル暗号は、離散対数問題と呼ばれる数学的問題の困難性に基づいている。楕円曲線暗号は、楕円曲線上の離散対数問題を基に設計されている。楕円曲線上の離散対数問題を「楕円曲線離散対数問題」と称する。このように、公開鍵暗号の安全性は、数学的問題の困難性に基づいている。したがって、これらの数学的問題の安全性が、公開鍵暗号の安全性の指標となる。
【０００７】
楕円曲線暗号は、楕円曲線離散対数問題に基づく暗号である。楕円曲線離散対数問題に基づく暗号は、楕円曲線上の点および単位元となる無限遠点０の集合をなす加法群において定義される。この加法群に含まれる点の数を位数ｒと呼ぶ。楕円曲線上の点Ｐ１とＰ２に対する演算として、以下のものが定義されている。
加算：Ｐ３＝Ｐ１＋Ｐ２＝Ｐ２＋Ｐ１
２倍算：Ｐ２＝２×Ｐ１＝Ｐ１＋Ｐ１
減算：Ｐ３＝Ｐ１−Ｐ２
零点：０（無限遠点）＝Ｐ１−Ｐ１
スカラ倍算：ｋ×Ｐ＝Ｐ＋Ｐ＋・・・＋Ｐ
【０００８】
ここで、ｋ×ＰとＰとからｋを算出する問題を楕円曲線離散対数問題という。ｋは公開鍵暗号の秘密鍵に対応するものである。一般的に、位数ｒが十分に大きい場合には、解ｋを求めることは困難である。楕円曲線対数問題が困難であるという仮定のもとで、楕円曲線暗号は高い安全性を確保することができる。
【０００９】
さらに近年では、ペアリングという公開鍵暗号技術が注目されている。ペアリングは楕円曲線暗号の一種である。楕円曲線上の２点に対するペアリングと呼ばれる演算を用いることで、従来の楕円曲線の機能を拡張する。この場合、楕円曲線離散対数問題の困難性に加え、いくつかの数学的問題の困難性に関する新たな仮定が必要となる。（Ｌ＋１）双曲線Difie-Hellman指数問題と呼ばれる数学的問題の困難性を仮定することがある。（Ｌ＋１）双曲線Difie-Hellman指数問題は、Ｐ、ｋ×Ｐ、ｋ２×Ｐ、ｋ３×Ｐ、・・・、ｋＬ×Ｐから、ｋやｋＬ＋１を求めるものである。この場合、Ｐ、ｋ×Ｐからｋを求める楕円曲線離散対数問題に比べ、ｋ２×Ｐ、ｋ３×Ｐ、・・・、ｋＬ×Ｐなどの追加情報があることから、追加情報ありの楕円離散対数問題と呼ぶことがある。
【００１０】
ここで、公開鍵暗号の安全性を評価するためには、その基となっている数学的問題の解析が必要となる。例えば、安全生を決定するパラメータの一つに位数ｒがあり、この位数ｒの値を大きくすれば、公開鍵暗号の安全性を高めることができるが、あまりにおおきな値にすると、暗号化、復号にかかる処理負荷も大きくなる。このため、安全性を保証しつつ、暗号化、復号にかかる処理負荷をある程度おさえることができるちょうど良い位数ｒの大きさを求めるべく、実際に計算機実験を行って、数学的問題の評価をおこなうことが重要となる。
【００１１】
数学的問題の解析を行うものには、Ｐ、ｋ×Ｐ、ｋｄ×Ｐおよびｄから、ｋを求める補助入力付き楕円曲線離散対数問題がある。ここで、ｄは（ｒ−１）の約数である。この問題を解く方法として、例えば、Cheon解析法が知られている。Cheon解析法は、Baby-Step Giant-Step解析法（BSGS）を用いて攻撃を行う方法である。Cheon解析法では、BSGSを二重に処理することで攻撃を行う。BSGSでは２種類のテーブルを作成し、これら計算結果を比較して、秘密鍵ｋを求める。これにより、最小ｒ１／４の数倍程度の計算量で暗号鍵としての秘密鍵ｋを解くことができる。
【先行技術文献】
【特許文献】
【００１２】
【特許文献１】特開平１１−２８８２１５号公報
【特許文献２】特開２００３−２８８０１３号公報
【発明の概要】
【発明が解決しようとする課題】
【００１３】
しかしながら、上記のCheon解析法では、楕円曲線離散対数問題の解を求めるための計算量が多いという問題があった。
【００１４】
開示の技術は、上記に鑑みてなされたものであって、楕円曲線離散対数問題の解を求めるための計算量を削減することができる暗号鍵解析方法、暗号鍵解析装置、および、暗号鍵解析プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１５】
本願の開示する暗号鍵解析方法は、一つの態様において、コンピュータが、楕円曲線離散対数問題の解を楕円曲線上の点に対応する生成元のべき乗で示し、前記生成元のべき乗部分を第１部分と第２部分に分割する分割ステップと、前記第１部分の値を所定の値域で変化させた場合に前記生成元をべき乗することで算出される値を第１テーブルに格納する第１演算ステップと、前記第２部分の値を所定の値域で変化させた場合に前記生成元をべき乗することで算出される値と、前記生成元のべき乗部分の一部に自己同型写像を適用した値とを組あわせた値を第２テーブルに格納する第２演算ステップと、前記第１テーブルに格納された値と前記第２テーブルに格納された値とを比較し、一致した値に基づいて前記楕円曲線離散対数問題の解を算出することで暗号鍵を解析する暗号鍵解析ステップとを実行することを要件とする。
【発明の効果】
【００１６】
本願の開示する暗号鍵解析方法の一つの態様によれば、楕円曲線離散対数問題の解を求めるための計算量を削減することができるという効果を奏する。
【図面の簡単な説明】
【００１７】
【図１Ａ】図１Ａは、ＴｂテーブルとＴｇテーブルとを比較する処理を補足するための図である。
【図１Ｂ】図１Ｂは、BSGSの具体例を説明するための図である。
【図２】図２は、Cheon解析法の具体例を説明するための図（１）である。
【図３】図３は、Cheon解析法の具体例を説明するための図（２）である。
【図４】図４は、Cheon解析法の具体例を説明するための図（３）である。
【図５】図５は、従来のCheon解析法の処理手順を示すフローチャートである。
【図６】図６は、本実施例１にかかる暗号鍵解読装置の構成を示す図である。
【図７】図７は、自己同型写像を適用した場合と適用していない場合との楕円曲線演算を実行すべき範囲を示す図（１）である。
【図８】図８は、自己同型写像を適用した場合と適用していない場合との楕円曲線演算を実行すべき範囲を示す図（２）である。
【図９】図９は、本実施例１にかかるＴｂテーブルのデータ構造の一例を示す図である。
【図１０】図１０は、本実施例１にかかるＴｇテーブルのデータ構造の一例を示す図である。
【図１１】図１１は、本実施例１にかかるテーブル生成部の構成を示す図である。
【図１２】図１２は、本実施例１にかかる処理部の処理手順を示すフローチャートである。
【図１３】図１３は、本実施例１にかかるテーブル処理部の処理手順を示すフローチャートである。
【図１４】図１４は、本実施例２にかかる暗号解読装置の構成を示す図である。
【図１５】図１５は、本実施例２にかかるＴｂテーブルのデータ構造の一例を示す図である。
【図１６】図１６は、本実施例２にかかるＴｇテーブルのデータ構造の一例を示す図である。
【図１７】図１７は、本実施例２にかかるテーブル生成部の構成を示す図である。
【図１８】図１８は、本実施例２にかかる処理部の処理手順を示すフローチャートである。
【図１９】図１９は、本実施例３にかかる暗号鍵解読装置の構成を示す図である。
【図２０】図２０は、本実施例３にかかるテーブル生成部の処理の概要を示す図である。
【図２１】図２１は、本実施例３にかかるＴｂテーブルのデータ構造の一例を示す図である。
【図２２】図２２は、本実施例３にかかるＴｇテーブルのデータ構造の一例を示す図である。
【図２３】図２３は、本実施例３にかかるテーブル生成部の構成を示す図である。
【図２４】図２４は、本実施例３にかかる処理部の処理手順を示すフローチャートである。
【図２５】図２５は、本実施例３にかかるテーブル生成部の処理手順を示すフローチャートである。
【図２６】図２６は、従来のCheon解析法、実施例１〜３の楕円演算回数、テーブルのデータ量の比較結果を示す図（１）である。
【図２７】図２７は、従来のCheon解析法、実施例１〜３の楕円演算回数、テーブルのデータ量の比較結果を示す図（２）である。
【図２８】図２８は、テーブル作成時間とテーブル量とを示す図である。
【図２９】図２９は、暗号鍵解読プログラムを実行するコンピュータを示す図である。
【発明を実施するための形態】
【００１８】
まず、本願の開示する暗号鍵解読装置における技術を説明するうえでの原理を図面に基づいて説明する。以下では、Baby-Step Giant-Step解析法、Cheon解析法、自己同型写像、自己同型写像のべき表現の順に説明する。
【００１９】
まず、「Baby-Step Giant-Step解析法」について説明する。以下では、Baby-Step Giant-Step解析法をBSGSと表記する。BSGSは、楕円曲線離散対数問題の効率的な解法の一つである。位数ｒの楕円曲線パラメータを使用し、未知値ｘ（０＜ｘ＜ｒ）を、既知のｘ×ＧとＧから求める楕円曲線対数問題を解く場合には、BSGSは、２×ｒ１／２回程度の楕円曲線演算によって楕円曲線離散対数問題を解くことができる。これに対して、BSGSを用いず、楕円曲線離散対数問題を総当たりで求めると、平均ｒ／２回程度の演算が必要となってしまう。
【００２０】
BSGSでは、未知数ｘを「ｒ１／２の値を切り上げた値」の進数で、上位値ｘＨと下位値ｘＬに分割し、Baby-Stepを実行してＴｂテーブルを作成し、Giant-Stepを実行してＴｇテーブルを作成する。Baby-Stepでは、順次ｉの値を変化させながら「（ｘＬ−ｉ）×Ｇ」を順次算出し、Ｔｂテーブルに計算結果を順次格納する。一方、Giant-Stepでは、順次ｊの値を変化させながら「ｊ×Ｇ」を順次算出し、Ｔｇテーブルに計算結果を順次格納する。なお、ｉ、ｊには、進数に応じて所定の値が乗算される。
【００２１】
図１Ａは、ＴｂテーブルとＴｇテーブルとを比較する処理を補足するための図である。図１Ａの１ａは、未知数ｘの上位部分であり、１ｂは、未知数ｘの下位部分である。ＴｂテーブルとＴｇテーブルとを比較することは、図１Ａの２ａ部分に対応する値と、２ｂ部分に対応する値とを比較することである。
【００２２】
図１Ｂは、BSGSの具体例を説明するための図である。ここでは一例として、位数ｒ＝９７とし、ＧおよびｘＧの値が与えられるものとする。なお、未知数ｘ＝９６とする。Baby-Stepにおいて、BSGSは、ｉの値を順次変化させ、「ｘＬＧ−iＧ」を順次計算することで、Ｔｂテーブル１０ａを生成する。図１に示す例では、ｉの値を０〜９とする。Giant-Stepにおいて、BSGSは、ｊの値を順次変化させ、「ｊ×１０Ｇ」を順次計算することで、Ｔｇテーブル１０ｂを生成する。図１に示す例では、ｊの値を０〜９とする。
【００２３】
BSGSでは、Ｔｂテーブル１０ａの各値とＴｇテーブル１０ｂの各値とを比較し、各値が一致する場合のｉおよびｊの値を判定する。未知数ｘとｉ、ｊとの関係は、「ｘ＝ｉ＋１０ｊ」となるため、各値が一致する場合のｉおよびｊの値を判定することができれば、未知数ｘを算出することができる。図１に示す例では、Ｔｂテーブル１０ａのｉが「６」となる場合の値「９０」と、Ｔｇテーブル１０ｂのｊが「９」となる場合の値「９０」が一致する。このため、未知数ｘは、「ｘ＝６＋９×１０＝９６」となる。BSGSでは、このようにして未知数ｘを算出する。このときの楕円曲線演算は２０回となる。この回数は、上述した「２×ｒ１／２」の値とほぼ同じである。
【００２４】
ここで、楕円曲線離散対数問題を総当たりで求める場合について説明する。楕円曲線離散対数問題を総当たりで求める場合には、平均ｒ／２回程度の楕円曲線演算が行われる。ＧとｘＧの値が与えられた場合に、ｉの値を順次変化させ「ｉ×Ｇ」を順次計算し、計算結果とｘＧの値とを比較して未知数ｘを求める。例えば、未知数ｘ＝９６の場合には、ｉの値が９６になった場合に、「ｉ×Ｇ」の値とｘＧとの値が一致するため、未知数ｘ＝９６として求めることができる。この場合には、楕円曲線演算を９６回行う必要がある。
【００２５】
位数ｒの場合、BSGSでは平均２×ｒ１／２回程度の楕円曲線演算によって楕円曲線離散対数問題を解くことができるが、総当たり法では、平均ｒ／２回程度の楕円曲線演算が必要となる。以上のことから、BSGSは、総当たり法と比較して、楕円曲線問題を解く場合の楕円曲線演算の回数が少なくなる。
【００２６】
次に、「Cheon解析法」について説明する。Cheon解析法は、追加情報ありの楕円離散対数問題に対して、BSGSを適用して解を算出する方法である。上記BSGSでは、ＧとｘＧとから未知数ｘを求めたが、Cheon解析では、Ｇ、ｘＧ、ｘｄＧ、ｄを利用して、未知数ｘを求める。ｄはｒ−１の約数に対応するものである。Cheon解析法では、BSGSを二重に行うことで、計算量を削減する。仮に、ｄの値が、ｒ１／２の値とほぼ同じ値となる場合には、楕円曲線演算の回数がほぼｒ１／４となることが知られている。
【００２７】
以下において、Cheon解析法の具体例について説明する。図２〜図４は、Cheon解析法の具体例を説明するための図である。
【００２８】
Cheon解析法では、点Ｇに対する位数ｒの生成元ζを求め、ｘ＝ζｙとなるｙを見つける。ここで、ｙの値域は、０〜ｒ−１となる。図２の左側の各数値は、図１Ａに示した各数値と同様である。図２の右側において、ｙＨは、ｙを（ｒ−１）／ｄで除算した商に対応し、ｙＬは、ｙを（ｒ−１）／ｄで除算した余りに対応する。
【００２９】
図２に示すように、部分２ａに対応する値と部分２ｂに対応する値とを比較することは、部分３ａに対応する値と部分３ｂに対応する値とを比較することと同じである。なお、部分２ａに対応する値は「（ｘＬ−ｉ）×Ｇ」であり、部分２ｂに対応する値は「ｊ×Ｇ」である。部分３ａに対応する値は「
【数１】
」であり、部分３ｂに対応する値は「ζｊ×Ｇ」である。つまり、Cheon解析法では、ζの指数部分において、BSGSと同様の処理を実行することで、ｙを求める。
【００３０】
なお、Cheon解析法では、はじめからｘ＝ζｙとなるｙを求めるのではなく、ｙをｙＨとｙＬに分割し、ｙＨとｙＬとをそれぞれ求める。
【００３１】
まず、ｙＬを求める場合について説明する。ｘｄＧ＝ζｄｚＧとなるｚを求めることと、ｙＬを求めることは、数学的に同じ意味を持つ。だたし、ζｄ＝ζｄとする。ｚを求めるために、BSGSを適用することで、計算量０（ｒ１／４）でｚを求めることができる。
【００３２】
図３の右側に示すように、Cheon解析法では、ｚを上位ｚＨとｚＬに分割する。そして、Cheon解析法では、Baby-Stepにおいて、ｉの値を変化させながら「
【数２】
」を順次算出し、Ｔｂテーブルに計算結果を順次格納する。また、Giant-Stepにおいて、ｊの値を変化させながら「ζｄｊ×Ｇ」を順次算出し、Ｔｇテーブルに計算結果を順次格納する。Cheon解析法では、Ｔｂテーブルの各値とＴｇテーブルの各値とを比較し、各値が一致する場合のｉおよびｊの値を判定する。ｉとｊとの値が分かれば、ｚを求めることができる。
【００３３】
続いて、Cheon解析法では、ｙＬを求めた後に、残りのｙＨを求める。Cheon解析法では、
【数３】
となるｗの値を見つける。ｗの値は、ｙＨに対応するものである。ｗの値域は０〜ｄとなる。
【００３４】
図４の右側に示すように、ｗを上位ｗＨとｗＬに分割する。そして、Cheon解析法では、Baby-Stepにおいて、ｉの値を変化させながら「
【数４】
」を順次算出し、Ｔｂテーブルに計算結果を順次格納する。また、ｊの値を変化させながら「ζｄｊ×Ｇ」を順次算出し、Ｔｇテーブルに計算結果を順次格納する。Cheon解析法では、Ｔｂテーブルの各値とＴｇテーブルの各値とを比較し、各値が一致する場合のｉおよびｊの値を判定する。ｉとｊとの値が分かれば、ｗを求めることができる。
【００３５】
上記のように、図２〜図４の処理を実行することで、ｙＬに対応するｚと、ｙＨに対応するｗが求まるので、ｙの値が特定される。上記のCheon解析法では、最小０（ｒ１／４）の計算量で、追加情報ありの楕円離散対数問題を解析することができる。
【００３６】
次に、従来のCheon解析法の処理手順について説明する。図５は、従来のCheon解析法の処理手順を示すフローチャートである。図５に示すように、Cheon解析法では、未知数ｘ＝ζｙとし、ｙをｙＨとｙＬに分割する（ステップＳ１０）。
【００３７】
Cheon解析法では、ｙＬ部分に対してBaby-Stepを実行し、ζｄ−ｕ１×ｘｄＧとなるＴｂテーブルを作成する（ステップＳ１１）。ただし、ｕ１の値域を０≦ｕ１＜ｄ１とする。ここで、ｄ１は、（（ｒ−１）／ｄ）１／２の値を切り上げたものに対応する。
【００３８】
Cheon解析法では、ｙＬ部分に対してGiant-Stepを実行し、ζｄｖ１・ｄ１×ＧとなるＴｇテーブルを作成する（ステップＳ１２）。ただし、ｖ１の値域を０≦ｖ１＜ｄ１とする。
【００３９】
Cheon解析法では、ＴｂテーブルとＴｇテーブルとを比較し、ζｄ−ｕ１×ｘｄＧ＝ζｄｖ１・ｄ１×Ｇとなるｕ１、ｖ１の組を算出する（ステップＳ１３）。Cheon解析法では、ｕ１とｖ１とを加算することでｚを算出する（ステップＳ１４）。このｚは、ｙＬに対応するものである。
【００４０】
続いて、Cheon解析法では、上位部分に対してＢａｂｙ−Ｓｔｅｐを実行し、ζ−ｕ２（ｒ−１）／ｒ×ｘＧ｛０≦ｕ２＜ｄ１’’｝となるＴｂテーブル１４１を作成する（ステップＳ１５）。また、Cheon解析法では、上位部分に対してＧｉａｎｔ−Ｓｔｅｐを実行し、ζｋ１ζｒ２・ｄ２・（ｒ−１）／ｒ×Ｇ｛０≦ｖ２＜ｄ’’｝となるＴｇを計算し、全ての点からなるＴｇテーブルを作成する（ステップＳ１６）。
【００４１】
Cheon解析法では、ＴｂテーブルとＴｇテーブルとを比較し、ζ−ｕ２（ｒ−１）／ｒ×ｘＧ＝、ζｋ１ζｒ２・ｄ２・（ｒ−１）／ｒ×Ｇとなる（ｕ２、ｖ２）の組を算出する（ステップＳ１７）。Cheon解析法では、、ｗ＝ｙＨ＝ｕ２＋ｖ２ｄ’’により、ｙの上位部分ｗを算出する（ステップＳ１８）。このｗは、ｙＨに対応するものである。そして、Cheon解析法では、ｚとｗ（ｒ−１）／ｄとを加算することで、ｙを算出する（ステップＳ１９）。このｙは、ｘ＝ζｙと、未知数ｘに対応するものである。以上、Cheon解析法の具体例について説明した。このようにして、Cheon解析法では、未知数ｘを算出する。
【００４２】
次に、「自己同型写像」について説明する。一部の楕円曲線では、楕円曲線上の点ＰのFrobenius写像Φ（Ｐ）が高速に計算できる。例えば、有限体（３１２７）の楕円曲線では、点Ｐ＝（ｘ、ｙ）のFrobenius写像Φ（Ｐ）＝（ｘ３、ｙ３）も同一の楕円曲線上の点となる。このFrobenius写像Φ（Ｐ）は、各座標を３乗するだけであり、他の楕円曲線演算に比べて高速に計算できる。なお、点ＰにFrobenius写像Φ（Ｐ）をｉ回適用して得られる点であるΦ（ｉ）（Ｐ）は以下のように記述される。すなわち、Φ（ｉ）（Ｐ）＝Φ（Φ（・・・Φ（Ｐ）））となる。
【００４３】
また、一部の楕円曲線ではマイナス写像についても高速に計算できる。マイナス写像は、点Ｐを点−Ｐに対応させる写像である。例えば、有限体ＧＦ（３１２７）における楕円曲線では、点Ｐ＝（ｘ，ｙ）のマイナス写像−Ｐ＝（ｘ，−ｙ）も同一の楕円曲線上の点となる。以下では、Frobenius写像およびマイナス写像をまとめて自己同型写像と呼ぶ。
【００４４】
次に、「自己同型写像のべき表現」について説明する。有限体ＧＦ（ｑｍ）における楕円曲線の場合、任意の点にFrobenius写像をｍ回適用すると元の点に戻る。つまり、Φ（ｍ）（Ｐ）＝Ｐとなる。また、任意の点のマイナス写像を２回適用すると元の点に戻る。つまり、（−１）２×Ｐ＝Ｐとなる。
【００４５】
上記自己同型写像を生成元ζのべき乗として表すと、自己同型写像は、（−１）（ｉ）Φ（ｊ）Ｐ＝ζ（ｉ・ｍ＋２・ｃ・ｊ）（ｒ―１）／２ｍ×Ｐと表現することができる。ここで、ｃは楕円曲線と生成元の値によって一意に決まる定数である。ｉおよびｊの値は、ｉ＝０〜１、ｊ＝０〜ｍ−１である。
【００４６】
特に、有限体ＧＦ（３１２７）楕円曲線上の点でマイナス点とFrobenius写像も同じ楕円曲線上の点となるような点Ｐに関し、生成元ζ＝３、ｍ＝１２７、ｃ＝１１０の場合には、自己同型写像は、（−１）（ｉ）Φ（ｊ）Ｐ＝ζ（１２７・ｉ＋２２０・ｊ）（ｒ―１）／２５４×Ｐと表現することができる。
【００４７】
以上、本願の開示する暗号鍵解読装置における技術を説明する上での原理を説明した。以下に、本願の開示する暗号鍵解読装置の実施例を図面に基づいて詳細に説明する。なお、この実施例により発明が限定されるものではない。
【実施例１】
【００４８】
本実施例１にかかる暗号鍵解読装置について説明する。図６は、本実施例１にかかる暗号鍵解読装置の構成を示す図である。この暗号鍵解読装置１００は、楕円曲線離散対数問題を解くことで、公開鍵暗号の秘密鍵を算出する装置である。図６に示すように、この暗号鍵解読装置１００は、入力部１１０、出力部１２０、処理部１３０、記憶部１４０を有する。
【００４９】
入力部１１０は、外部から情報を入力する。例えば、入力部１１０は、ユーザからの指示を受け付けて、受け付けた指示を処理部１３０に入力する。また、入力部１１０は、楕円曲線離散対数問題を解読する場合に利用する各種のパラメータを受け付け、受け付けたパラメータを処理部１３０に入力する。出力部１２０は、楕円離散対数問題の解読結果を出力する。
【００５０】
処理部１３０は、パラメータ取得部１３１、テーブル生成部１３２、テーブル比較部１３３、未知数算出部１３４、制御部１３５を有する。
【００５１】
パラメータ取得部１３１は、入力部１１０からパラメータを取得し、取得したパラメータをテーブル生成部１３２に出力する処理部である。なお、パラメータ取得部１３１は、パラメータを記憶部１４０に記憶させておき、ユーザからの指示を受け付けた場合に、記憶部１４０に記憶されたパラメータを取得してもよい。
【００５２】
ここで、パラメータの一例について説明する。パラメータには、Ｇ＊、ζ＊、ｍ、ｄ’’が含まれる。このうち、Ｇ＊は、楕円曲線上の点である。ζ＊は、位数ｒの生成元である。ｍは、拡大次数である。ｄ’’は、テーブルの作成範囲を指定するものである。具体的に、自己同型写像を利用してｙＨを求める場合には、Ｇ＊＝Ｇｄ、ζ＊＝ζｄ、ｄ’’は、「（（ｒ−１）／ｄ／２ｍ）１／２の値を切り上げた値」となる。また、自己同型写像を利用してｙＨを求める場合には、Ｇ＊＝Ｇ、ζ＊＝ζ（ｒ−１）／ｄ、ｄ’’は、「（ｄ／２ｍ）１／２の値を切り上げた値」となる。自己同型写像を利用する場合、ｙＬを求める場合とｙＨを求める場合のどちらかでのみ使用されることが多い。そのため、以降では、特に記述がない場合にはｙＬの生成の場合について説明する。
【００５３】
テーブル生成部１３２は、Cheon解析法の要領で、Baby-StepおよびGiant-Stepを実行し、ＴｂテーブルおよびＴｇテーブルを生成する処理部である。特に、テーブル生成部１３２は、Giant-Stepを実行してＴｇテーブルを作成する場合に、楕円曲線演算の一部に、自己同型写像を適用することで、計算量の削減を図る。
【００５４】
自己同型写像をCheon解析法に適用するためには、自己同型写像を生成元ζの指数乗倍で表現する必要がある。自己同型写像を生成元ζの指数乗倍で表すと、（−１）（ｉ）Φ（ｊ）×Ｐ＝ζｄ（ｉ・ｍ＋２・ｃ・ｊ）ｄ’’Ｐとなる。ｄは、ｒ−１の約数であり、このｄは、約数２とｍを含めないように選択された値とする。自己同型写像を適用することで、楕円曲線演算を実行すべき範囲を削減することができる。このように選択すると、ｙＬを求めるのに自己同型写像を使用することになる。
【００５５】
ここで、自己同型写像を適用した場合と適用していない場合との楕円曲線演算を実行すべき範囲について説明する。図７および図８は、自己同型写像を適用した場合と適用していない場合との楕円曲線演算を実行すべき範囲を示す図である。図７の上段は、自己同型写像を適用しない従来のCheon解析法に対応する。図７の下段は、自己同型写像を適用する今回のアイデアに対応する。
【００５６】
図７では、探索範囲を上位ｄと下位（ｒ−１）／ｄに分割する場合を示している。例えば、図７の上段に示すように、（ｒ−１）／ｄの範囲を探索する場合には、（ｒ−１）／ｄの範囲に対して楕円曲線演算を実行し、ｚを算出する必要があった。ｚを算出する場合には、図３で説明したように、ｚをｚＨとｚＬに分割し、Baby-StepおよびGiant-Stepを実行して、ＴｂテーブルとＴｇテーブルとを比較することで、ｚを算出する。
【００５７】
これに対して、自己同型写像を適用すると、（ｒ−１）／ｄの範囲に対して楕円曲線演算を実行する必要がない。図７の下段に示すように、楕円曲線演算を実行する範囲は、（ｒ−１）／ｄ／２ｍでよくなり、残りの範囲は、自己同型写像「（−１）ｉΦｊ」を用いて求めればよい。
【００５８】
図８に示すように、Baby-Stepを実行する範囲は２０ｂとなり、Giang-Stepを実行する範囲は２０ａとなる。Baby-Stepを実行する範囲２０ｂには、自己同型写像を適用する範囲が含まれないので、Cheon解析法と同様にして、Ｔｂテーブルを作成する。これに対して、Giant-Stepを実行する範囲２０ｂには、自己同型写像を適用する範囲が含まれる。このため、Giant-Stepを実行する場合には、楕円曲線演算の一部に自己同型写像を適用してＴｇテーブルを作成する。
【００５９】
テーブル生成部１３２が、Baby-Stepを実行する場合の処理について説明する。テーブル生成部１３２は、ｕ１の値を変化させながら、「ζｄ−ｕ１×ｘｄＧ」を順次算出することで、Ｔｂテーブルを作成する。なお、ｕ１の値域を「０≦ｕ１＜ｄ１’’」とする。
【００６０】
図９は、本実施例１にかかるＴｂテーブルのデータ構造の一例を示す図である。図９に示すように、このＴｂテーブル１４１は、ｋの値と、ｋの値に応じたζｄ−ｋ×ｘｄＧの点とを対応付けて記憶する。Ｔｂテーブル１４１のｋは、ｕ１に対応する値である。
【００６１】
テーブル生成部１３２が、Giang-Stepを実行する場合の処理について説明する。テーブル生成部１３２は、ｖ１、ｉ、ｊの値を順次変化させながら、「（−１）（ｉ）Φ（ｊ）（ζｄｖ１・ｄ１×Ｇ）」を順次算出することで、Ｔｇテーブル１４２を作成する。なお、ｖ１の値域を「０≦ｖ１＜ｄ１’’」とする。ｉの値域を「０、１」とする。ｊの値域を「０≦ｊ＜ｍ−１」とする。
【００６２】
図１０は、本実施例１にかかるＴｇテーブルのデータ構造の一例を示す図である。図１０に示すように、このＴｇテーブル１４２は、ｋ、ｉ、ｊの値と、ｋ、ｉ、ｊの値に応じた（−１）（ｉ）Φ（ｊ）（ζｄｋ・ｄ１×Ｇ）の点とを対応付けて記憶する。Ｔｇテーブルのｋは、ｖ１に対応する値である。
【００６３】
ここで、テーブル生成部１３２の構成について説明する。図１１は、本実施例１にかかるテーブル生成部の構成を示す図である。図１１に示すように、テーブル生成部１３２は、テーブル生成制御部１５０、スカラ倍算部１５１、自己同型写像計算部１５２を有する。
【００６４】
テーブル生成制御部１５０は、スカラ倍算部１５１および自己同型写像計算部１５２を利用して、「ζｄ−ｕ１×ｘｄＧ」、「（−１）（ｉ）Φ（ｊ）（ζｄｖ１・ｄ１×Ｇ）」に対応する値を算出し、Ｔｂテーブル１４１およびＴｇテーブル１４２を作成する処理部である。
【００６５】
テーブル生成制御部１５０は、パラメータｄ１’’、ζ＊、Ｇ＊、ｍ、Ｔ＊を取得する。テーブル生成制御部１５０は、Ｔ＊に応じて、Ｔｂテーブル１４１またはＴｇテーブル１４２を生成すると判定する。Ｔ＊は、Ｔｂテーブル１４１を作成するのか、Ｔｇテーブル１４２を作成するのかを識別する情報である。テーブル生成制御部１５０は、制御部１３５からＴ＊を取得する。
【００６６】
テーブル生成制御部１５０が、Ｔｂテーブル１４１を生成する場合について説明する。テーブル生成制御部１５０は、スカラ倍算部１５１に、ζ＊、Ｇ＊、ｋを順次入力し、スカラ倍算部１５１から（ζ＊）ｋＧ＊を順次取得する。Ｔｂテーブル１４１を生成する場合のｋは、上記ｕ１に対応する。テーブル生成制御部１５０は、ｋと（ζ＊）ｋＧ＊とを対応付けて、Ｔｂテーブル１４１に登録する。
【００６７】
テーブル生成制御部１５０が、Ｔｇテーブル１４２を生成する場合について説明する。テーブル生成制御部１５０は、ζ＊、Ｇ＊、ｋをスカラ倍算部１５１に順次入力し、スカラ倍算部１５１から（ζ＊）ｋＧ＊を順次取得する。Ｔｇテーブル１４２を生成する場合のｋは、上記ｖ１に対応する。テーブル生成制御部１５０は、（ζ＊）ｋＧ＊を取得した後に、ｉ、ｊ、（ζ＊）ｋＧ＊を自己同型写像計算部１５２に順次入力し、自己同型写像計算部１５２から（−１）（ｉ）Φ（ｊ）（（ζ＊）ｋ×Ｇ＊）を取得する。テーブル生成制御部１５０は、ｉとｊとｋと（−１）（ｉ）Φ（ｊ）（（ζ＊）ｋ×Ｇ＊）とを対応付けて、Ｔｇテーブル１４２に登録する。
【００６８】
スカラ倍算部１５１は、テーブル生成制御部１５０から、ζ＊、Ｇ＊、ｋを受け付け、（ζ＊）ｋＧ＊を算出する処理部である。スカラ倍算部１５１は、（ζ＊）ｋＧ＊をテーブル生成制御部１５０に出力する。
【００６９】
自己同型写像計算部１５２は、テーブル生成制御部１５０から、ｉ、ｊ、（ζ＊）ｋＧ＊を受け付け、（−１）（ｉ）Φ（ｊ）（（ζ＊）ｋ×Ｇ＊）を算出する処理部である。自己同型写像計算部１５２は、（−１）（ｉ）Φ（ｊ）（（ζ＊）ｋ×Ｇ＊）をテーブル生成制御部１５０に出力する。
【００７０】
ところで、テーブル生成部１３２は、上記の処理を、未知数ｙの下位部分と、上位部分に対してそれぞれ実行するものとする。未知数ｙの下位部分は、図３に示した（ｒ−１）／ｄの範囲に対応する。また、未知数ｙの上位部分は、図４に示したｄの範囲に対応する。下位部を求める場合には、楕円曲線演算の一部に自己同型写像を適用することで、計算量を削減する。上位部を求める場合には、自己同型写像演算を用いない従来と同様の計算を行う。
【００７１】
図６の説明にもどる。テーブル比較部１３３は、Ｔｂテーブル１４１とＴｇテーブル１４２とを比較して、
ζｄ−ｕ１×ｘｄＧ＝（−１）（ｉ）Φ（ｊ）（ζｄｖ１・ｄ１×Ｇ）
となる（ｕ１、ｖ１、ｉ、ｊ）の組を求める処理部である。テーブル比較部１３３は、求めた（ｕ１、ｖ１、ｉ、ｊ）の組を未知数算出部１３４に出力する。
【００７２】
Ｔｂテーブル１４１、Ｔｇテーブル１４２は、未知数ｙの下位部分、上位部分に対応してそれぞれ作成される。このため、テーブル比較部１３３は、部分毎に、（ｕ１、ｖ１、ｉ、ｊ）の組を未知数算出部１３４に出力する。
【００７３】
未知数演算部１３４は、テーブル比較部１３３から、（ｕ１、ｖ１、ｉ、ｊ）の組を取得し、秘密鍵を算出する。ここでは、未知数ｙの下位部分をｚ、秘密鍵の上位部分をｗとする。
【００７４】
未知数演算部１３４は、下位部分から求められた組（ｕ１、ｖ１、ｉ、ｊ）を基にして、未知数ｙの下位部分をｚ＝ｕ１＋ｖ１・ｄ１’’＋（ｉ・ｍ＋２・ｃ・ｊ）ｄ’’により算出する。この場合には、ｘｄＧ＝ζｄｚＧとなるので、ｘｄ＝ζｄｚとなるｚが求まる。
【００７５】
未知数演算部１３４は、上位部分から求められた組（ｕ２、ｖ２）を基にして、未知数ｙの上位部分をｗ＝ｕ２＋ｖ２・ｄ１’’により算出する。ここで、ｄ’’＝ｄ２（従来値）とする。
【００７６】
未知数演算部１３４は、ｚとｗを求めた後に、ｙ＝ｚ＋ｗ（ｒ−１）／ｄにより求める。秘密鍵ｘとｙとの間には、ｘ＝ζｙの関係がある。未知数演算部１３４は、秘密鍵ｘとｙとの関係から、秘密鍵ｘを求め、求めた秘密鍵ｘの情報を出力部１２０に出力する。
【００７７】
制御部１３５は、パラメータ取得部１３１、テーブル生成部１３２、テーブル比較部１３３、未知数算出部１３４の各部に対して、上記で説明したような動作を行うように制御する処理部である。例えば、制御部１３５は、Ｔ＊をテーブル生成部１３２に入力して、Ｔｂテーブル１４１またはＴｇテーブル１４２を作成させる。そして、Ｔｂテーブル１４１、Ｔｇテーブル１４２が作成された後に、制御部１３５は、テーブル比較部１３３に指示を出し、Ｔｂテーブル１４１とＴｇテーブル１４２とを比較させる。
【００７８】
記憶部１４０は、Ｔｂテーブル１４１およびＴｇテーブル１４２を記憶する記憶部である。Ｔｂテーブル１４１のデータ構造は、図９のものとなる。Ｔｇテーブル１４２のデータ構造は、図１０のものとなる。
【００７９】
次に、本実施例１にかかる処理部１３０の処理手順について説明する。図１２は、本実施例１にかかる処理部の処理手順を示すフローチャートである。例えば、図１２に示す処理は、入力部１１０から、楕円曲線離散対数問題を解く旨の指示を受け付けた場合に実行される。図１２に示すように処理部１３０は、秘密鍵ｘ＝ζｙとし、ｙを上位部分と下位部分に分割する（ステップＳ１０１）。
【００８０】
処理部１３０は、下位部分に対してBaby-Stepを実行し、ζｄ−ｕ１×ｘｄＧ｛０≦ｕ１＜ｄ１’’｝となるＴｂテーブル１４１を作成する（ステップＳ１０２）。処理部１３０は、下位部分に対してGiant-Stepを実行し、ζｄｖ１・ｄ１×Ｇ｛０≦ｖ１＜ｄ１’’｝と、各点の自己同型写像（−１）（ｉ）Φ（ｊ）（ζｄｖ１・ｄ１×Ｇ）を算出し、全ての点からなるＴｇテーブル１４２を作成する（ステップＳ１０３）。
【００８１】
処理部１３０は、Ｔｂテーブル１４１とＴｇテーブル１４２とを比較し、ζｄ−ｕ１×ｘｄＧ＝（−１）（ｉ）Φ（ｊ）（ζｄｖ１・ｄ１×Ｇ）となる（ｕ１、ｖ１、ｉ、ｊ）の組を算出する（ステップＳ１０４）。処理部１３０は、ｚ＝ｕ１＋ｖ１・ｄ１’’＋（ｉ・ｍ＋２・ｃ・ｊ）ｄ’’により、ｙの下位部分ｚを算出する（ステップＳ１０５）。
【００８２】
処理部１３０は、上位部分に対してＢａｂｙ−Ｓｔｅｐを実行し、ζ−ｕ２（ｒ−１）／ｒ×ｘＧ｛０≦ｕ２＜ｄ１’’｝となるＴｂテーブル１４１を作成する（ステップＳ１０６）。処理部１３０は、上位部分に対してＧｉａｎｔ−Ｓｔｅｐを実行し、ζｋ１ζｒ２・ｄ２・（ｒ−１）／ｒ×Ｇ｛０≦ｖ２＜ｄ’’｝となるＴｇを計算し、全ての点からなるＴｇテーブルを作成する（ステップＳ１０７）。
【００８３】
処理部１３０は、ＴｂテーブルとＴｇテーブルとを比較し、ζ−ｕ２（ｒ−１）／ｒ×ｘＧ＝、ζｋ１ζｒ２・ｄ２・（ｒ−１）／ｒ×Ｇとなる（ｕ２、ｖ２）の組を算出する（ステップＳ１０８）。処理部１３０は、ｗ＝ｙＨ＝ｕ２＋ｖ２ｄ’’により、ｙの上位部分ｗを算出する（ステップＳ１０９）。なお、ｄ’’は、ｄ１／２の値を切り上げたものである。
【００８４】
処理部１３０は、ｙ＝ｚ＋ｗ（ｒ−１）／ｄにより、ｙの値を算出する（ステップＳ１１０）。処理部１３０は、ｘ＝ζｙの関係からｘを求め（ステップＳ１１１）、秘密鍵ｘを出力する（ステップＳ１１２）。
【００８５】
次に、本実施例１にかかるテーブル生成部１３２がＴｂテーブル１４１およびＴｇテーブル１４２を生成する処理手順について説明する。図１３は、本実施例１にかかるテーブル生成部の処理手順を示すフローチャートである。
【００８６】
図１３に示すように、テーブル生成部１３２は、パラメータｄ１’’、ζ＊、Ｇ＊、ｍ、Ｔ＊を取得し（ステップＳ２０１）、ｋを初期値に設定する（ステップＳ２０２）。テーブル生成部１３２は、スカラ倍計算（ζ＊）ｋＧ＊を実行し（ステップＳ２０３）、｛ｋ、（ζ＊）ｋＧ＊｝を記憶部１４０に出力する（ステップＳ２０４）。
【００８７】
テーブル生成部１３２は、ｉ＝０〜１、ｊ＝０〜ｍ−１に対して、自己同型写像計算（−１）（ｉ）Φ（ｊ）（（ζ＊）ｋ×Ｇ＊）を実行する（ステップＳ２０５）。テーブル生成部１３２は、｛ｋ、ｉ、ｊ、（−１）（ｉ）Φ（ｊ）（ζ＊）ｋ×Ｇ＊｝を記憶部１４０に出力する（ステップＳ２０６）。
【００８８】
テーブル生成部１３２は、ｋ＝ｋ＋１を算出し（ステップＳ２０７）、ｋの値がｄ’’−１の値よりも大きいか否かを判定する（ステップＳ２０８）。テーブル生成部１３２は、ｋの値がｄ’’−１の値以下の場合には（ステップＳ２０８，Ｎｏ）、ステップＳ２０３に移行する。一方、テーブル生成部１３２は、ｋの値がｄ’’−１の値より大きい場合には（ステップＳ２０８，Ｙｅｓ）、処理を終了する。
【００８９】
次に、本実施例１にかかる暗号解読装置１００の効果について説明する。本実施例１にかかる暗号解読装置１００は、Giant-Stepを実行して、Ｔｂテーブル１４１を生成する場合に、楕円曲線演算の一部に、自己同型写像を適用することで、楕円曲線演算を実行すべき範囲を削減することができる。下位部分の計算量を、従来のCheon解析法と比較して、１／（２ｍ）１／２に削減することができる。例えば、有限体ＧＦ（３ｍ）上の楕円曲線の場合には、ｍ＝１２７であるため、従来のCheon解析法と比較して、下位部分の計算量が（１／１６）１／２＝１／４程度となる。
【００９０】
ところで、図６に示した暗号鍵解読装置１００の構成は一例であり、暗号鍵解読装置１００は、必ずしも図６に示した各処理部を全て有していなくてもよい。例えば、暗号鍵解読装置１００は、分割部と、第１演算部と、第２演算部と、暗号鍵解析部とを有していればよい。
【００９１】
このうち分割部は、楕円曲線離散対数問題の解を楕円曲線上の点に対応する生成元のべき乗で示し、前記生成元のべき乗部分を第１部分と第２部分に分割する処理部である。第１演算部は、第１部分の値を所定の値域で変化させた場合に生成元をべき乗することで算出される値を第１テーブルに格納する処理部である。第２演算部は、第２部分の値を所定の値域で変化させた場合に前記生成元をべき乗することで算出される値と、前記生成元のべき乗部分の一部に自己同型写像を適用した値とを組あわせた値を第２テーブルに格納する処理部である。分割部、第１演算部、第２演算部は、テーブル生成部１３２に対応する。
【００９２】
暗号鍵解析部は、第１テーブルに格納された値と第２テーブルに格納された値とを比較し、一致した値に基づいて前記楕円曲線離散対数問題の解を算出することで暗号鍵を解析する処理部である。この暗号鍵解析部は、テーブル比較部１３３、未知数算出部１３４に対応する。
【実施例２】
【００９３】
ところで、上記の実施例１では、従来のCheon解析法と比較して、計算量を大幅に削減できるものの、Ｔｇテーブル２４２のデータ量が従来のものと比較して約８倍に増えてしまう。以下の実施例２では、データ量が増加させず、計算量を削減することを可能にする暗号鍵解読装置について説明する。
【００９４】
図１４は、本実施例２にかかる暗号鍵解読装置の構成を示す図である。図１４に示すように、この暗号鍵解読装置２００は、入力部２１０、出力部２２０、処理部２３０、記憶部２４０を有する。
【００９５】
このうち、入力部２１０、出力部２２０に関する説明は、図１に示した入力部１１０、出力部１２０に関する説明と同様である。
【００９６】
処理部２３０は、パラメータ取得部２３１、テーブル生成部２３２、テーブル比較部２３３、未知数算出部２３４、制御部２３５を有する。
【００９７】
パラメータ取得部２３１は、入力部２１０からパラメータを取得し、取得したパラメータをテーブル生成部２３２に出力する処理部である。パラメータは、実施例１と同様にして、Ｇ＊、ζ＊、ｍ、ｄ’’が含まれる。なお、パラメータ取得部２３１は、パラメータを記憶部２４０に記憶させておき、ユーザからの指示を受け付けた場合に、記憶部２４０に記憶されたパラメータを取得してもよい。
【００９８】
テーブル生成部２３２は、Cheon解析法の要領で、Baby-StepおよびGiant-Stepを実行し、Ｔｂテーブル２４１およびＴｇテーブル２４２を生成する処理部である。特に、テーブル生成部２３２は、Giant-Stepを実行してＴｂテーブル２４１を作成する場合に、楕円曲線演算の一部に、自己同型写像を適用することで、計算量の削減を図る。
【００９９】
ところで、実施例１のテーブル生成部１３２は、Baby-Stepを実行して、ｕ１の値を「０〜ｄ１’’」まで変化させながら、「ζｄ−ｕ１×ｘｄＧ」を順次算出していた。また、Giant-Stepを実行して、ｖ１の値を「０〜ｄ１’’」まで変化させながら、「ζｄｖ１・ｄ１×Ｇ」を順次算出していた。つまり、実施例１では、ｕ１の値域と、ｖ１の値域は「０〜ｄ１’’」で共通であった。
【０１００】
これに対して、テーブル生成部２３２は、ｕ１の値域と、ｖ１の値域とを不均一に設定する。具体的には、テーブル生成部２３２は、Baby-Stepを実行して、ｕ１の値を「０〜ｄ１ｂ」まで変化させながら、「ζｄ−ｕ１×ｘｄＧ」を順次算出する。ここで、ｄ１ｂ＝（（ｒ−１）／ｄ）１／２である。また、テーブル生成部２３２は、Giant-Stepを実行して、ｖ１の値を「０〜ｄ１ｇ」まで変化させながら、「ζｄｖ１・ｄ１×Ｇ」を順次算出する。ここで、ｄ１ｇ＝（（ｒ−１）／ｄ／２ｍ）／ｄ１ｂ）である。
【０１０１】
Baby-Stepを実行する場合のｕ１の値域０〜ｄ１ｂは、従来のCheon解析法の値域と同じであり、アルゴリズムも共通することから、Ｔｂテーブル２４１の計算量およびデータ量は、従来のものと同じになる。これに対して、Giant-Stepを実行する場合のｖ１の値域は、０〜ｄ１ｇであり、ｄ１ｇ＝ｄ１／２ｍの関係があるため、従来のものと比較して、計算量を約１／２に削減することができる。また、Ｔｇテーブル２４２のデータ量は従来のCheon解析法と同じになる。つまり、本実施例２のテーブル生成部２３２は、従来のCheon解析法と比較した場合には、データ量を増加させることなく、計算量を１／２に削減することができる。
【０１０２】
テーブル生成部が、Baby-Stepを実行する場合の処理について説明する。テーブル生成部２３２は、ｕ１の値を変化させながら、「ζｄ−ｕ１×ｘｄＧ」を順次算出することで、Ｔｂテーブル２４１を作成する。なお、ｕ１の値域は上記のように「０≦ｕ１＜ｄ１ｂ」とする。
【０１０３】
図１５は、本実施例２にかかるＴｂテーブルのデータ構造の一例を示す図である。図１５に示すように、このＴｂテーブル２４１は、ｋの値と、ｋの値に応じたζｄ−ｋ×ｘｄＧの点とを対応付けて記憶する。Ｔｂテーブル２４１のｋは、ｕ１に対応する値である。
【０１０４】
テーブル生成部２３２が、Giang-Stepを実行する場合の処理について説明する。テーブル生成部２３２は、ｖ１、ｉ、ｊの値を順次変化させながら、「
【数５】
」を順次算出することで、Ｔｇテーブル２４２を作成する。なお、ｖ１の値域を「０≦ｖ１＜ｄ１ｇ」とする。ｉの値域を「０、１」とする。ｊの値域を「０≦ｊ＜ｍ−１」とする。
【０１０５】
図１６は、本実施例２にかかるＴｇテーブルのデータ構造の一例を示す図である。図１６に示すように、このＴｇテーブル２４２は、ｋ、ｉ、ｊの値と、ｋ、ｉ、ｊの値に応じた「
【数６】
」の点とを対応付けて記憶する。Ｔｇテーブル２４２でのｋは、ｖ１に対応する値である。
【０１０６】
ここで、テーブル生成部２３２の構成について説明する。図１７は、本実施例２にかかるテーブル生成部の構成を示す図である。図１７に示すように、テーブル生成部２３２は、テーブル生成制御部２５０、スカラ倍算部２５１、自己同型写像計算部２５２を有する。
【０１０７】
テーブル生成制御部２５０は、パラメータｄ１’’、ζ＊、Ｇ＊、ｍ、Ｔ＊を取得する。テーブル生成制御部２５０は、Ｔ＊に応じて、Ｔｂテーブル２４１またはＴｇテーブル２４２を生成すると判定する。Ｔ＊は、Ｔｂテーブル２４１を作成するのか、Ｔｇテーブル２４２を作成するのかを識別する情報である。テーブル生成制御部２５０は、制御部２３５からＴ＊を取得する。
【０１０８】
テーブル生成制御部２５０が、Ｔｂテーブル２４１を生成する場合について説明する。テーブル生成制御部２５０は、スカラ倍算部２５１に、ζ＊、Ｇ＊、ｋを順次入力し、スカラ倍算部２５１から（ζ＊）ｋＧ＊を順次取得する。Ｔｂテーブル２４１を生成する場合のｋは、上記ｕ１に対応する。テーブル生成制御部２５０は、ｋと（ζ＊）ｋＧ＊とを対応付けて、Ｔｂテーブル２４１に登録する。
【０１０９】
テーブル生成制御部２５０が、Ｔｇテーブル２４２を生成する場合について説明する。テーブル生成制御部２５０は、ζ＊、Ｇ＊、ｋをスカラ倍算部２５１に順次入力し、スカラ倍算部２５１から（ζ＊）ｋＧ＊を順次取得する。Ｔｇテーブル２４２を生成する場合のｋは、上記ｖ１・ｄ１ｂに対応する。テーブル生成制御部２５０は、（ζ＊）ｋＧ＊を取得した後に、ｉ、ｊ、（ζ＊）ｋＧ＊を自己同型写像計算部２５２に順次入力し、自己同型写像計算部２５２から（−１）（ｉ）Φ（ｊ）（（ζ＊）ｋ×Ｇ＊）を取得する。テーブル生成制御部２５０は、ｉとｊとｋと（−１）（ｉ）Φ（ｊ）（（ζ＊）ｋ×Ｇ＊）とを対応付けて、Ｔｇテーブル２４２に登録する。
【０１１０】
スカラ倍算部２５１は、テーブル生成制御部２５０から、ζ＊、Ｇ＊、ｋを受け付け、（ζ＊）ｋＧ＊を算出する処理部である。スカラ倍算部２５１は、（ζ＊）ｋＧ＊をテーブル生成制御部２５０に出力する。
【０１１１】
自己同型写像計算部２５２は、テーブル生成制御部２５０から、ｉ、ｊ、（ζ＊）ｋＧ＊を受け付け、（−１）（ｉ）Φ（ｊ）（（ζ＊）ｋ×Ｇ＊）を算出する処理部である。自己同型写像計算部２５２は、（−１）（ｉ）Φ（ｊ）（（ζ＊）ｋ×Ｇ＊）をテーブル生成制御部２５０に出力する。
【０１１２】
ところで、テーブル生成部２３２は、上記の処理を、未知数ｙの下位部分と、上位部分に対してそれぞれ実行するものとする。未知数ｙの下位部分は、図３に示した（ｒ−１）／ｄの範囲に対応する。また、未知数ｙの上位部分は、図４に示したｄの範囲に対応する。いずれの場合も、Giant-Stepを実行する場合に、楕円曲線演算の一部に自己同型写像を適用することで、計算量を削減する。
【０１１３】
図１４の説明に戻る。テーブル比較部２３３は、Ｔｂテーブル２４１とＴｇテーブル２４２とを比較して、
【数７】
となる（ｕ１、ｖ１、ｉ、ｊ）の組を求める処理部である。テーブル比較部２３３は、求めた（ｕ１、ｖ１、ｉ、ｊ）の組を未知数算出部２３４に出力する。
【０１１４】
Ｔｂテーブル２４１、Ｔｇテーブル２４２は、未知数ｙの下位部分、上位部分に対応してそれぞれ作成される。このため、テーブル比較部２３３は、部分毎に、（ｕ１、ｖ１、ｉ、ｊ）の組を未知数算出部２３４に出力する。
【０１１５】
未知数演算部２３４は、テーブル比較部２３３から、（ｕ１、ｖ１、ｉ、ｊ）の組を取得し、秘密鍵を算出する。ここでは、未知数ｙの下位部分をｚ、秘密鍵の上位部分をｗとする。
【０１１６】
未知数演算部２３４は、下位部分から求められた組（ｕ１、ｖ１、ｉ、ｊ）を基にして、未知数ｙの下位部分をｚ＝ｕ１＋ｖ１・ｄ１ｂ＋（ｉ・ｍ＋２・ｃ・ｊ）ｄ’’により算出する。この場合には、ｘｄＧ＝ζｄｚＧとなるので、ｘｄ＝ζｄｚとなるｚが求まる。
【０１１７】
未知数演算部２３４は、上位部分から求められた組（ｕ２、ｖ２）を基にして、未知数ｙの上位部分をｗ＝ｕ２＋ｖ２・ｄ’’により算出する。
【０１１８】
未知数演算部２３４は、ｚとｗを求めた後に、未知数ｙをｙ＝ｚ＋ｗ（ｒ−１）／ｄにより求める。秘密鍵ｘとｙとの間には、ｘ＝ζｙの関係がある。未知数演算部２３４は、秘密鍵ｘとｙとの関係から、秘密鍵ｘを求め、求めた秘密鍵ｘの情報を出力部２２０に出力する。
【０１１９】
制御部２３５は、パラメータ取得部２３１、テーブル生成部２３２、テーブル比較部２３３、未知数算出部２３４の各部に対して、上記で説明したような動作を行うように制御する処理部である。例えば、制御部２３５は、Ｔ＊をテーブル生成部２３２に入力して、Ｔｂテーブル２４１またはＴｇテーブル２４２を作成させる。そして、Ｔｂテーブル２４１、Ｔｂテーブル２４２が作成された後に、制御部２３５は、テーブル比較部２３３に指示を出し、Ｔｂテーブル２４１とＴｇテーブル２４２とを比較させる。
【０１２０】
記憶部２４０は、Ｔｂテーブル２４１およびＴｇテーブル２４２を記憶する記憶部である。Ｔｂテーブル２４１のデータ構造は、図１５のものとなる。Ｔｇテーブル２４２のデータ構造は、図１６のものとなる。
【０１２１】
次に、本実施例２にかかる処理部２３０の処理手順について説明する。図１８は、本実施例２にかかる処理部の処理手順を示すフローチャートである。図１８に示す処理は、入力部２１０から、楕円曲線離散対数問題を解く旨の指示を受け付けた場合に実行される。
【０１２２】
図１８に示すように処理部２３０は、秘密鍵ｘ＝ζｙとし、ｙを上位部分と下位部分に分割する（ステップＳ３０１）。処理部２３０は、下位部分に対してBaby-Stepを実行し、ζｄ−ｕ１×ｘｄＧ｛０≦ｕ１＜ｄ１ｂ｝となるＴｂテーブル２４１を作成する（ステップＳ３０２）。処理部２３０は、下位部分に対してGiant-Stepを実行し、「
【数８】
」｛０≦ｖ１＜ｄ１ｂ｝と、各点の自己同型写像「
【数５】
」を算出し、全ての点からなるＴｇテーブル１４２を作成する（ステップＳ３０３）。
【０１２３】
処理部２３０は、Ｔｂテーブル２４１とＴｇテーブル２４２とを比較し、「
【数７】
」となる（ｕ１、ｖ１、ｉ、ｊ）の組を算出する（ステップＳ３０４）。処理部２３０は、ｚ＝ｕ１＋ｖ１・ｄ１ｂ＋（ｉ・ｍ＋２・ｃ・ｊ）ｄ’’により、ｙの下位部分ｚを算出する（ステップＳ３０５）。
【０１２４】
処理部２３０は、上位部分に対してＢａｂｙ−Ｓｔｅｐを実行し、ζ−ｕ２（ｒ−１）／ｒ×ｘＧ｛０≦ｕ２＜ｄ１’’｝となるＴｂテーブル１４１を作成する（ステップＳ３０６）。処理部２３０は、上位部分に対してＧｉａｎｔ−Ｓｔｅｐを実行し、ζｋ１ζｒ２・ｄ２・（ｒ−１）／ｒ×Ｇ｛０≦ｖ２＜ｄ’’｝となるＴｇを計算し、全ての点からなるＴｇテーブルを作成する（ステップＳ３０７）。
【０１２５】
処理部２３０は、ＴｂテーブルとＴｇテーブルとを比較し、ζ−ｕ２（ｒ−１）／ｒ×ｘＧ＝、ζｋ１ζｒ２・ｄ２・（ｒ−１）／ｒ×Ｇとなる（ｕ２、ｖ２）の組を算出する（ステップＳ３０８）。処理部２３０は、ｗ＝ｙＨ＝ｕ２＋ｖ２ｄ’’により、ｙの上位部分ｗを算出する（ステップＳ３０９）。
【０１２６】
処理部２３０は、ｙ＝ｚ＋ｗ（ｒ−１）／ｄにより、ｙの値を算出する（ステップＳ３１０）。処理部２３０は、ｘ＝ζｙの関係からｘを求め（ステップＳ３１１）、秘密鍵ｘを出力する（ステップＳ３１２）。
【０１２７】
次に、本実施例２にかかる暗号解読装置２００の効果について説明する。本実施例２にかかる暗号解読装置２００は、Giant-Stepを実行して、Ｔｂテーブル２４１を生成する場合に、楕円曲線演算の一部に、自己同型写像を適用する。更に、暗号解読装置２００は、Baby-Stepを実行する場合のｕ１の値域と、Giant-Stepを実行する場合のｖ１の値域とを不均一に設定する。楕円曲線演算に自己同型写像を適応すると、自己同型写像「（−１）（ｉ）Φ（ｊ）」と、「
【数８】
」との全ての組み合わせをＴｇテーブル２４２に格納する必要がある。このため、
【数８】
のｖ１の値域を制限してやれば、「
【数８】
」の演算結果の数が減るので、結果として、自己同型写像「（−１）（ｉ）Φ（ｊ）」と、「
【数８】
」との全ての組み合わせ数が減り、Ｔｇテーブル２４２のデータ量を削減することができる。したがって、本実施例２にかかる暗号解読装置２００によれば、従来のCheon解析法と比較して、テーブル量を増加させることなく、計算量を削減することができる。
【実施例３】
【０１２８】
実施例３にかかる暗号鍵解読装置について説明する。上記実施例１、２では、Giant-Step側に自己同型写像を適用していたが、本実施例３では、Baby-Step側およびGiant-Step側に自己同型写像を適用することで、計算量およびテーブル量を削減する。
【０１２９】
図１９は、本実施例３にかかる暗号鍵解読装置の構成を示す図である。図１９に示すように、この暗号鍵解読装置３００は、入力部３１０、出力部３２０、処理部３３０、記憶部３４０を有する。
【０１３０】
このうち、入力部３１０、出力部３２０に関する説明は、図１に示した入力部１１０、出力部１２０に関する説明と同様である。
【０１３１】
処理部３３０は、パラメータ取得部３３１、テーブル生成部３３２、テーブル比較部３３３、未知数算出部３３４、制御部３３５を有する。
【０１３２】
パラメータ取得部３３１は、入力部３１０からパラメータを取得し、取得したパラメータをテーブル生成部３３２に出力する処理部である。パラメータは、実施例１と同様にして、Ｇ＊、ζ＊、ｍ、ｄ’’が含まれる。なお、パラメータ取得部３３１は、パラメータを記憶部３４０に記憶させておき、ユーザからの指示を受け付けた場合に、記憶部３４０に記憶されたパラメータを取得してもよい。
【０１３３】
テーブル生成部３３２は、Cheon解析法の要領で、Baby-StepおよびGiant-Stepを実行し、Ｔｂテーブル３４１およびＴｇテーブル３４２を生成する処理部である。特に、テーブル生成部３３２は、Baby-StepおよびGiant-Step場合に、楕円曲線演算の一部に、自己同型写像を適用することで、計算量の削減を図る。
【０１３４】
図２０は、本実施例３にかかるテーブル生成部の処理の概要を示す図である。図２０では、検索範囲を上位ｄと下位（ｒ−１）／ｄに分割する場合を示している。テーブル生成部３３２が（ｒ−１）／ｄの範囲に対してBaby-Stepを実行する場合には、範囲３０ａに対して、楕円曲線演算を実行し、範囲４０ｂに対して自己同型写像を実行する。ここで、範囲４０ｂは、自己同型写像「（−１）（ｉ）Φ（ｊ」」の上位部分に対応する。テーブル生成部３３２は、自己同型写像の結果と楕円曲線演算の結果とを組あわせた値を、Ｔｂテーブル３４１に格納する。
【０１３５】
テーブル生成部３３２が（ｒ−１）／ｄの範囲に対してGiant-Stepを実行する場合には、範囲３０ｂに対して、楕円曲線演算を実行し、範囲４０ａに対して自己同型写像を実行する。ここで、範囲４０ｂは、自己同型写像「（−１）ｉΦｊ」の下位部分に対応する。テーブル生成部３３２は、自己同型写像の結果と楕円曲線演算の結果とを組あわせた値を、Ｔｇテーブル３４２に格納する。
【０１３６】
テーブル生成部３３２が、Baby-Stepを実行する場合の処理について説明する。テーブル生成部３３２は、ｕ１、ｉｂ、ｊｂの値を順次変化させながら、「（−１）（ｉｂ）Φ（ｊｂ）（ζｄｕ１×Ｇ）」を順次計算し、Ｔｂテーブル３４１を作成する。ただし、ｉ、ｊの選択条件を、「−（２ｍ）１／２＜（ｉ・ｍ＋ｊ・ｃ・２）ｍｏｄ ２ｍ≦０」とする。すなわち、テーブル生成部３３２は、上記選択条件をみたすｉ、ｊの組に対応する「（−１）（ｉｂ）Φ（ｊｂ）（ζｄｕ１×Ｇ）」の値のみを算出する。なお、ｕ１の値域を「０≦ｕ１＜ｄ１’’」とする。
【０１３７】
図２１は、本実施例３にかかるＴｂテーブルのデータ構造の一例を示す図である。図２１に示すように、このＴｂテーブル３４１は、ｋ、ｉ、ｊの値と、ｋ、ｉ、ｊの値に応じた（−１）（ｉ）Φ（ｊ）（ζｄ−ｋｘｄＧ）の点とを対応付けて記憶する。Ｔｂテーブル３４１のｋは、ｕ１に対応する値である。ｉ、ｊはそれぞれ、ｉｂ、ｊｂに対応する。
【０１３８】
テーブル生成部３３２が、Giant-Stepを実行する場合の処理について説明する。テーブル生成部３３２は、ｖ１、ｉｇ、ｊｇの値を順次変化させながら、「（−１）（ｉｇ）Φ（ｊｇ）（ζｄｖ１・ｄ’’×Ｇ）」を順次計算し、Ｔｂテーブル３４２を作成する。ただし、ｉ、ｊの選択条件を「（ｍ・ｉｇ＋２ｃ・ｊｇ） ｍｏｄ ２ｍ＝０」とする。すなわち、テーブル生成部３３２は、上記選択条件を満たすｉ、ｊの組に対応する「（−１）（ｉｇ）Φ（ｊｇ）（ζｄｖ１・ｄ’’×Ｇ）」の値のみを算出する。なお、ｖ１の値域を「０≦ｖ１＜ｄ１’’」とする。
【０１３９】
図２２は、本実施例３にかかるＴｇテーブルのデータ構造の一例を示す図である。図２２に示すように、このＴｇテーブル３４２は、ｋ、ｉ、ｊの値と、ｋ、ｉ、ｊの値に応じた（−１）（ｉ）Φ（ｊ）（ζｄ−ｋ・ｄ１Ｇ）の点とを対応付けて記憶する。Ｔｇテーブル３４２のｋは、ｖ１に対応する値である。ｉ、ｊはそれぞれ、ｉｇ、ｊｇに対応する。
【０１４０】
ここで、テーブル生成部３３２の構成について説明する。図２３は、本実施例３にかかるテーブル生成部の構成を示す図である。図２３に示すように、テーブル生成部２３２は、テーブル生成制御部３５０、スカラ倍算３５１、自己同型写像計算部３５２、自己同型写像選択部３５３を有する。
【０１４１】
テーブル生成制御部３５０は、パラメータｄ１’’、ζ＊、Ｇ＊、ｍ、Ｔ＊、ｉ，ｊの選択条件を取得する。このうち、ｉ，ｊの選択条件は、「−（２ｍ）１／２＜（ｉ・ｍ＋ｊ・ｃ・２）ｍｏｄ ２ｍ≦０」および「（ｍ・ｉｇ＋２ｃ・ｊｇ） ｍｏｄ ２ｍ＝０」である。
【０１４２】
テーブル生成制御部３５０は、Ｔ＊に応じて、Ｔｂテーブル３４１またはＴｇテーブル３４２を生成すると判定する。Ｔ＊は、Ｔｂテーブル３４１を作成するのか、Ｔｇテーブル３４２を作成するのかを識別する情報である。テーブル生成制御部３５０は、制御部２３５からＴ＊を取得する。
【０１４３】
テーブル生成制御部３５０が、Ｔｂテーブル３４１を生成する場合について説明する。テーブル生成制御部３５０は、スカラ倍算３５１に、ζ＊、Ｇ＊、ｋを順次入力し、スカラ倍算部３５１から（ζ＊）ｋＧ＊を順次取得する。Ｔｂテーブル３４１を生成する場合のｋは、上記ｕ１に対応する。
【０１４４】
テーブル生成制御部３５０は、（ζ＊）ｋＧ＊を取得した後に、ｉ、ｊ、（ζ＊）ｋＧ＊を自己同型写像計算部３５２に順次入力し、自己同型写像計算部３５２から（−１）（ｉ）Φ（ｊ）（（ζ＊）ｋ×Ｇ＊）を取得する。テーブル生成制御部３５０は、ｉとｊとｋと（−１）（ｉ）Φ（ｊ）（（ζ＊）ｋ×Ｇ＊）とを対応付けて、Ｔｂテーブル３４１に登録する。
【０１４５】
なお、テーブル生成制御部３５０は、ｉ、ｊの選択条件と、ｉ、ｊの組とを自己同型写像選択部３５３に入力し、ｉ、ｊの組が、ｉ、ｊの選択条件を満たしている場合に、かかるｉ、ｊの組と（ζ＊）ｋＧ＊を自己同型写像計算部３５２に入力する。Ｔｂテーブル３４１を生成する場合の、ｉ、ｊの選択条件は、「−（２ｍ）１／２＜（ｉ・ｍ＋ｊ・ｃ・２）ｍｏｄ ２ｍ≦０」である。
【０１４６】
テーブル生成制御部３５０が、Ｔｇテーブル３４２を生成する場合について説明する。テーブル生成部３５０は、スカラ倍算部３５１に、ζ＊、Ｇ＊、ｋを順次入力し、スカラ倍算部２５１から（ζ＊）ｋＧ＊を順次取得する。Ｔｇテーブル３４２を生成する場合のｋは、上記ｖ１に対応する。
【０１４７】
テーブル生成制御部３５０は、（ζ＊）ｋＧ＊を取得した後に、ｉ、ｊ、（ζ＊）ｋＧ＊を自己同型写像計算部３５２に順次入力し、自己同型写像計算部３５２から（−１）（ｉ）Φ（ｊ）（（ζ＊）ｋ×Ｇ＊）を取得する。テーブル生成制御部３５０は、ｉとｊとｋと（−１）（ｉ）Φ（ｊ）（（ζ＊）ｋ×Ｇ＊）とを対応付けて、Ｔｇテーブル３４２に登録する。
【０１４８】
なお、テーブル生成制御部３５０は、ｉ、ｊの選択条件と、ｉ、ｊの組とを自己同型写像選択部３５３に入力し、ｉ、ｊの組が、ｉ、ｊの選択条件を満たしている場合に、かかるｉ、ｊの組と（ζ＊）ｋＧ＊を自己同型写像計算部３５２に入力する。Ｔｇテーブル３４１を生成する場合の、ｉ、ｊの選択条件は、「（ｍ・ｉｇ＋２ｃ・ｊｇ） ｍｏｄ ２ｍ＝０」である。
【０１４９】
ところで、テーブル生成部３３２は、上記の処理を、未知数ｙの下位部分と、上位部分に対してそれぞれ実行するものとする。図３に示した（ｒ−１）／ｄの範囲に対応する。また、未知数ｙの上位部分は、図４に示したｄの範囲に対応する。いずれの場合も、Baby-StepおよびGiant-Stepを実行する場合に、楕円曲線演算の一部に自己同型写像を適用することで、計算量を削減する。
【０１５０】
図１９の説明に戻る。テーブル比較部３３３は、Ｔｂテーブル３４１とＴｇテーブル３４２とを比較して、
（−１）（ｉｂ）Φ（ｊｂ）（ζｄｕ１×Ｇ）＝（−１）（ｉｇ）Φ（ｊｇ）（ζｄｖ１・ｄ’’×Ｇ）
となる（ｕ１、ｖ１、ｉｂ、ｊｂ、ｉｇ、ｊｇ）の組を求める処理部である。テーブル比較部３３３は、求めた（ｕ１、ｖ１、ｉｂ、ｊｂ、ｉｇ、ｊｇ）の組を未知数算出部３３４に出力する。
【０１５１】
未知数演算部３３４は、テーブル比較部３３３から、（ｕ１、ｖ１、ｉｂ、ｊｂ、ｉｇ、ｊｇ）の組を取得し、秘密鍵を算出する。ここでは、未知数ｙの下位部分をｚ、秘密鍵の上位部分をｗとする。
【０１５２】
未知数演算部３３４は、下位部分から求められた組（ｕ１、ｖ１、ｉｂ、ｊｂ、ｉｇ、ｊｇ）を基にして、未知数ｙの下位部分ｚを求める。ｚは、ｚ＝ｕ１＋（ｉｂ・ｍ＋２・ｃ・ｊｂ）＋ｖ１・ｄ１’’＋（ｉｇ・ｍ＋２・ｃ・ｊｇ）・ｄ’’により求められる。この場合には、ｘｄＧ＝ζｄｚＧとなるので、ｘｄ＝ζｄｚとなるｚが求まる。
【０１５３】
未知数演算部３３４は、上位部分から求められた組（ｕ２、ｖ２）を基にして、未知数ｙの上位部分をｗ＝ｕ２＋ｖ２・ｄ’’により算出する。
【０１５４】
未知数演算部３３４は、ｚとｗを求めた後に、ｙ＝ｚ＋ｗ（ｒ−１）／ｄにより求める。秘密鍵ｘとｙとの間には、ｘ＝ζｙの関係がある。未知数演算部３３４は、秘密鍵ｘとｙとの関係から、秘密鍵ｘを求め、求めた秘密鍵ｘの情報を出力部３２０に出力する。
【０１５５】
制御部３３５は、パラメータ取得部３３１、テーブル生成部３３２、テーブル比較部３３３、未知数算出部３３４の各部に対して、上記で説明したような動作を行うように制御する処理部である。例えば、制御部３３５は、Ｔ＊をテーブル生成部３３２に入力して、Ｔｂテーブル３４１またはＴｇテーブル３４２を作成させる。そして、Ｔｂテーブル３４１、Ｔｂテーブル３４２が作成された後に、制御部３３５は、テーブル比較部３３３に指示を出し、Ｔｂテーブル３４１とＴｇテーブル３４２とを比較させる。
【０１５６】
記憶部３４０は、Ｔｂテーブル３４１およびＴｇテーブル３４２を記憶する記憶部である。Ｔｂテーブル３４１のデータ構造は、図２１に示すものとなる。Ｔｇテーブル３４２のデータ構造は、図２２に示すものとなる。
【０１５７】
次に、本実施例３にかかる処理部３３０の処理手順について説明する。図２４は、本実施例３にかかる処理部の処理手順を示すフローチャートである。例えば、図２４に示す処理は、入力部３１０から、楕円曲線離散対数問題を解く旨の指示を受け付けた場合に実行される。図２４に示すように処理部３３０は、秘密鍵ｘ＝ζｙとし、ｙを上位部分と下位部分に分割する（ステップＳ４０１）。
【０１５８】
処理部３３０は、下位部分に対してBaby-Stepを実行し、ζｄ−ｕ１×ｘｄＧ｛０≦ｕ１＜ｄ１’’｝と、各点の自己同型写像（−１）（ｉｂ）Φ（ｊｂ）（ζｄ−ｕ１×ｘｄＧ）を算出し、全ての点からなるＴｂテーブル３４１を作成する（ステップＳ４０２）。
【０１５９】
処理部３３０は、計算した点のうち、ｉｂ、ｊｂの組が、「−（２ｍ）１／２＜（ｉｂ・ｍ＋２・ｃ・ｊｂ）ｍｏｄ ２ｍ≦０」を満たす点だけＴｂテーブル３４１に格納する（ステップＳ４０３）。
【０１６０】
処理部３３０は、下位部分に対してGiant-Stepを実行し、ζｄｖ１・ｄ１’’×Ｇ｛０≦ｖ１＜ｄ１’’｝と、各点の自己同型写像（−１）（ｉｇ）Φ（ｊｇ）（ζｄｖ１・ｄ１’’×Ｇ）を算出し、全ての点からなるＴｇテーブル３４２を作成する（ステップＳ４０４）。
【０１６１】
処理部３３０は、計算した点のうち、ｉｇ、ｊｇの組が、（ｍ・ｉｇ＋２ｃ・ｊｇ） ｍｏｄ ２ｍ＝０」となる点だけＴｇテーブル３４２に格納する（ステップＳ４０５）。
【０１６２】
処理部３３０は、Ｔｂテーブル３４１とＴｇテーブル３４２とを比較し、（−１）（ｉｂ）Φ（ｊｂ）（ζｄ−ｕ１×ｘｄＧ）＝（−１）（ｉｇ）Φ（ｊｇ）（ζｄｖ１・ｄ１’’×Ｇ）となる（ｕ１、ｖ１、ｉｂ、ｊｂ、ｉｇ、ｊｇ）の組を算出する（ステップＳ４０６）。処理部３３０は、ｚ＝ｕ１＋（ｉｂ・ｍ＋２・ｃ・ｊｂ）＋ｖ１・ｄ１’’＋（ｉｇ・ｍ＋２・ｃ・ｊｇ）・ｄ’’により、ｚを算出する（ステップＳ４０７）。
【０１６３】
処理部３３０は、上位部分に対してBaby-Stepを実行し、上位部分に対してＢａｂｙ−Ｓｔｅｐを実行し、ζ−ｕ２（ｒ−１）／ｒ×ｘＧ｛０≦ｕ２＜ｄ１’’｝となるＴｂテーブル１４１を作成する（ステップＳ４０８）。
【０１６４】
処理部３３０は、上位部分に対してＧｉａｎｔ−Ｓｔｅｐを実行し、ζｋ１ζｒ２・ｄ２・（ｒ−１）／ｒ×Ｇ｛０≦ｖ２＜ｄ’’｝となるＴｇを計算し、全ての点からなるＴｇテーブルを作成する（ステップＳ４０９）。
【０１６５】
処理部３３０は、ＴｂテーブルとＴｇテーブルとを比較し、ζ−ｕ２（ｒ−１）／ｒ×ｘＧ＝、ζｋ１ζｒ２・ｄ２・（ｒ−１）／ｒ×Ｇとなる（ｕ２、ｖ２）の組を算出する（ステップＳ４１０）。処理部３３０は、ｗ＝ｙＨ＝ｕ２＋ｖ２ｄ’’により、ｙの上位部分ｗを算出する（ステップＳ４１１）。
【０１６６】
処理部３３０は、ｙ＝ｚ＋ｗ（ｒ−１）／ｄにより、ｙの値を算出する（ステップＳ４１２）。処理部３３０は、ｘ＝ζｙの関係からｘを求め（ステップＳ４１３）、秘密鍵ｘを出力する（ステップＳ４１４）。
【０１６７】
次に、本実施例３にかかるテーブル生成部３３２がＴｂテーブル３４１およびＴｇテーブル３４２を生成する処理手順について説明する。図２５は、本実施例３にかかるテーブル生成部の処理手順を示すフローチャートである。
【０１６８】
図２５に示すように、テーブル生成部３３２は、パラメータｄ１’’、ζ＊、Ｇ＊、ｍ、Ｔ＊、（ｉ、ｊ）の条件を取得し（ステップＳ５０１）、ｋを初期値に設定する（ステップＳ５０２）。テーブル生成部３３２は、スカラ倍計算（ζ＊）ｋＧ＊を実行する（ステップＳ５０３）。
【０１６９】
テーブル生成部３３２は、（ｉ、ｊ）の条件を満たすｉ＝０〜１、ｊ＝０〜ｍ−１に対して、自己同型写像計算（−１）（ｉ）Φ（ｊ）（（ζ＊）ｋＧ＊）を実行する（ステップＳ５０４）。テーブル生成部３３２は、｛ｉ、ｊ、ｋ、（−１）（ｉ）Φ（ｊ）（（ζ＊）ｋＧ＊）｝を記憶部３４０に出力する（ステップＳ５０５）。
【０１７０】
テーブル生成部３３２は、ｋ＝ｋ＋１を算出し（ステップＳ５０６）、ｋの値がｄ’’−１の値よりも大きいか否かを判定する（ステップＳ５０７）。テーブル生成部３３２は、ｋの値がｄ’’−１の値以下の場合には（ステップＳ５０７，Ｎｏ）、ステップＳ５０３に移行する。一方、テーブル生成部３３２は、ｋの値がｄ’’−１の値より大きい場合には（ステップＳ５０７，Ｙｅｓ）、処理を終了する。
【０１７１】
次に、本実施例３にかかる暗号解読装置３００の効果について説明する。本実施例３にかかる暗号解読装置３００は、Baby-StepおよびGiant-Stepを実行する場合に、楕円曲線演算の一部に、自己同型写像を適用することで、楕円曲線演算を実行すべき範囲を削減することができる。この結果、楕円曲線離散対数問題を解くための計算量を、従来のCheon解析法と比較して、１／（２ｍ）１／２に削減することができる。例えば、有限体ＧＦ（３ｍ）上の楕円曲線の場合には、ｍ＝１２７であるため、従来のCheon解析法と比較して、計算量が１／１６となる。
【０１７２】
また、本実施例３にかかる暗号装置３００は、ｉ、ｊの選択条件を満たさない、ｉ＝０〜１、ｊ＝０〜ｍ−１の組あわせに対応する自己同型写像の計算結果を、Ｔｂテーブル３４１、Ｔｇテーブル３４２に記憶しない。この結果、Ｔｂテーブル３４１、Ｔｇテーブル３４２のデータ量を、従来のCheon解析法と同量のデータ量に抑えることができる。
【０１７３】
次に、従来のCheon解析法、実施例１〜３の楕円演算回数、テーブルのデータ量の比較結果を示す。図２６および図２７は、従来のCheon解析法、実施例１〜３の楕円演算回数、テーブルのデータ量の比較結果を示す図である。
【０１７４】
図２６に示すように、従来のCheon解析法の楕円演算回数を１とすると、実施例１の楕円演算回数は１／（２ｍ）１／２となり、実施例２の楕円演算回数は１／２となり、実施例３の楕円演算回数は１／（２ｍ）１／２となる。また、従来のCheon解析法のテーブル量を１とすると、実施例１のテーブル量は１／（２ｍ）１／２となり、実施例２のテーブル量は１、実施例３のテーブル量は１となる。
【０１７５】
有限体ＧＦ（３１２７）上の楕円曲線の場合の、従来のCheon解析法、実施例１〜３の楕円演算回数、テーブルのデータ量の比較結果を示す。図２７に示すように、従来のCheon解析法の楕円演算回数を１とすると、実施例１の楕円演算回数は約１／１６となり、実施例２の楕円演算回数は約１／２となり、実施例３の楕円演算回数は約１／１６となる。また、従来のCheon解析法のテーブル量を１とすると、実施例１のテーブル量は約８倍となり、実施例２、３のテーブル量はほぼ同じとなる。
【０１７６】
理論値では、楕円演算回数で評価したが、実際のテーブル作成は自己同型写像の計算も処理時間がかかる。そこで、ここでは一例として、有限体ＧＦ（３１２７）上の楕円曲線で従来のCheon解析法、実施例３のテーブル作成時間の実験結果について説明する。図２８は、テーブル作成時間とテーブル量とを示す図である。
【０１７７】
図２８に示すように、従来のCheon解析法では、テーブル作成時間が７時間、テーブル量が１５．７８MByteとなる。これに対して、実施例３では、テーブル作成時間が４４分、テーブル量が１５．８５MByteとなる。したがって、実施例３は、従来のCheon解析法と比較して、１／９．５倍の時間でテーブルを作成することができ、テーブル量は１．００４倍でほとんど変わらないことが分かる。
【０１７８】
また、上記の各実施例で説明した暗号鍵解読装置１００、２００、３００の各種の処理は、あらかじめ用意されたプログラムをパーソナルコンピュータやワークステーションなどのコンピュータシステムで実行することによって実現することもできる。そこで、以下では、図２９を用いて、上記の実施例で説明した暗号鍵解読装置１００、２００、３００と同様の機能を有する暗号鍵解読プログラムを実行するコンピュータの一例を説明する。図２９は、暗号鍵解読プログラムを実行するコンピュータを示す図である。
【０１７９】
同図に示すように、暗号鍵解読装置１００、２００としてコンピュータ４００は、入出力制御部４１０、ＨＤＤ（Hard Disk Drive）４２０、ＲＡＭ（Random Access Memory）４３０およびＣＰＵ（Central Processing Unit）４４０を有する。各装置４１０〜４４０は、バス４５０で接続して構成される。
【０１８０】
ここで、入出力制御部４１０は、各種情報の入出力を制御する。ＨＤＤ４２０は、ＣＰＵ４４０による各種処理の実行に必要な情報を記憶する。ＲＡＭ４３０は、各種情報を一時的に記憶する。ＣＰＵ４４０は、各種演算処理を実行する。
【０１８１】
そして、ＨＤＤ４２０には、暗号鍵解読システムデータがあらかじめ記憶されている。この暗号鍵解読システムデータは、図６、図１４、図１９に示した暗号鍵解読装置１００、２００、３００の各処理部と同様の機能を発揮する暗号鍵解読プログラムを含む。また、暗号鍵解読システムデータは、処理に必要な各種パラメータを含む暗号鍵解読用データを含む。なお、この暗号鍵解読システムデータを適宜分散させて、ネットワークを介して通信可能に接続された他のコンピュータの記憶部に記憶させておくこともできる。
【０１８２】
そして、ＣＰＵ４４０が、この暗号鍵解読システムデータをＨＤＤ４２０から読み出してＲＡＭ４３０に展開することにより、暗号鍵解読システムデータは暗号鍵解読システムとして機能するようになる。この暗号鍵解読システムには暗号鍵解読プロセスが含まれる。
【０１８３】
すなわち、暗号鍵解読システムやそれに搭載された暗号鍵解読プロセスは、暗号鍵解読用データをＨＤＤ４２０から読み出して、ＲＡＭ４３０において自身に割り当てられた領域に展開し、この展開したデータ等に基づいて各種処理を実行する。
【０１８４】
なお、暗号鍵解読システム及び暗号鍵解読プロセスは、図６、図１４、図１９に示した各機能部において実行される処理に対応する。例えば、暗号鍵解読プロセスは、パラメータ取得部１３１、テーブル生成部１３２、テーブル比較部１３３、未知数算出部１３４に対応する。
【０１８５】
なお、上記した暗号鍵解読プログラムについては、必ずしも最初からＨＤＤ４２０に記憶させておく必要はない。
【０１８６】
例えば、コンピュータ４００に挿入されるフレキシブルディスク（ＦＤ）、ＣＤ−ＲＯＭ、ＤＶＤディスク、光磁気ディスク、ＩＣカードなどの「可搬用の物理媒体」に各プログラムを記憶させておく。そして、コンピュータ４００がこれらから各プログラムを読み出して実行するようにしてもよい。
【０１８７】
さらには、公衆回線、インターネット、ＬＡＮ、ＷＡＮなどを介してコンピュータ４００に接続される「他のコンピュータ（またはサーバ）」などに各プログラムを記憶させておく。そして、コンピュータ４００がこれらから各プログラムを読み出して実行するようにしてもよい。
【０１８８】
また、図示した各装置の各構成要素は機能概念的なものであり、必ずしも物理的に図示の如く構成されていることを要しない。すなわち、各装置の分散・統合の具体的状態は図示のものに限られず、その全部または一部を、各種の負荷や使用状況などに応じて、任意の単位で機能的または物理的に分散・統合して構成することができる。例えば、図６に示すテーブル生成部１３２とテーブル比較部１３３とが統合されてもよい。また、テーブル比較部１３３と未知数算出部１３４とが統合されてもよい。
【０１８９】
なお、図６、図１４、図１９に示した処理部１３０、２３０、３３０は、例えば、ＡＳＩＣ（Application Specific Integrated Circuit）や、ＦＰＧＡ（Field Programmable Gate Array）などの集積装置に対応する。または、各処理部１３０、２３０、３３０は、ＣＰＵやＭＰＵ（Micro Processing Unit）等の電子回路に対応する。また、図６、図１４、図１９に示した記憶部１４０、２４０、３４０は、例えば、ＲＡＭ、ＲＯＭ（Read Only Memory）、フラッシュメモリ（Flash Memory）などの半導体メモリ素子、またはハードディスク、光ディスクなどの記憶装置に対応する。
【０１９０】
以上の各実施例を含む実施形態に関し、さらに以下の付記を開示する。
【０１９１】
（付記１）コンピュータが、
楕円曲線離散対数問題の解を楕円曲線上の点に対応する生成元のべき乗で示し、前記生成元のべき乗部分を第１部分と第２部分に分割する分割ステップと、
前記第１部分の値を所定の値域で変化させた場合に前記生成元をべき乗することで算出される値を第１テーブルに格納する第１演算ステップと、
前記第２部分の値を所定の値域で変化させた場合に前記生成元をべき乗することで算出される値と、前記生成元のべき乗部分の一部に自己同型写像を適用した値とを組あわせた値を第２テーブルに格納する第２演算ステップと、
前記第１テーブルに格納された値と前記第２テーブルに格納された値とを比較し、一致した値に基づいて前記楕円曲線離散対数問題の解を算出することで暗号鍵を解析する暗号鍵解析ステップと
を実行することを特徴とする暗号鍵解析方法。
【０１９２】
（付記２）前記第２演算ステップは、前記第１演算ステップが変化させる所定の値域とは異なる値域によって、前記第１部分の値を変化させた場合に、前記生成元をべき乗することで算出される値と、前記生成元のべき乗部分の一部に自己同型写像を適用した値とを組あわせた値を第２テーブルに格納することを特徴とする付記１に記載の暗号鍵解析方法。
【０１９３】
（付記３）前記第１演算ステップは、前記生成元のべき乗部分の一部に自己同型写像を適用した値のうち所定の条件を満たす値と、前記第２部分の値を所定の値域で変化させた場合に前記生成元をべき乗することで算出される値とを組あわせた値を前記第１テーブルに格納し、前記第２演算ステップは、前記生成元のべき乗部分の一部に自己同型写像を適用した値のうち所定の条件を満たす値と、前記第１部分の値を所定の値域で変化させた場合に前記生成元をべき乗することで算出される値とを組あわせた値を前記第２テーブルに格納することを特徴とする付記１または２に記載の暗号鍵解析方法。
【０１９４】
（付記４）前記分割ステップは、前記生成元のべき乗部分を上位部と下位部にわけ、前記上位部および下位部分をそれぞれ、第１部分と第２部分に分割し、前記第２演算ステップは、前記上位部の第２部分または前記下位部の第２部分の内どちらか一方に、自己同型写像を適用することを特徴とする付記１、２または３に記載の暗号鍵解析方法。
【０１９５】
（付記５）楕円曲線離散対数問題の解を楕円曲線上の点に対応する生成元のべき乗で示し、前記生成元のべき乗部分を第１部分と第２部分に分割する分割部と、
前記第１部分の値を所定の値域で変化させた場合に前記生成元をべき乗することで算出される値を第１テーブルに格納する第１演算部と、
前記第２部分の値を所定の値域で変化させた場合に前記生成元をべき乗することで算出される値と、前記生成元のべき乗部分の一部に自己同型写像を適用した値とを組あわせた値を第２テーブルに格納する第２演算部と、
前記第１テーブルに格納された値と前記第２テーブルに格納された値とを比較し、一致した値に基づいて前記楕円曲線離散対数問題の解を算出することで暗号鍵を解析する暗号鍵解析部と
を備えたことを特徴とする暗号鍵解析装置。
【０１９６】
（付記６）前記第２演算部は、前記第１演算部が変化させる所定の値域とは異なる値域によって、前記第１部分の値を変化させた場合に、前記生成元をべき乗することで算出される値と、前記生成元のべき乗部分の一部に自己同型写像を適用した値とを組あわせた値を第２テーブルに格納することを特徴とする付記５に記載の暗号鍵解析装置。
【０１９７】
（付記７）前記第１演算部は、前記生成元のべき乗部分の一部に自己同型写像を適用した値のうち所定の条件を満たす値と、前記第２部分の値を所定の値域で変化させた場合に前記生成元をべき乗することで算出される値とを組あわせた値を前記第１テーブルに格納し、前記第２演算部は、前記生成元のべき乗部分の一部に自己同型写像を適用した値のうち所定の条件を満たす値と、前記第１部分の値を所定の値域で変化させた場合に前記生成元をべき乗することで算出される値とを組あわせた値を前記第３テーブルに格納することを特徴とする付記５または６に記載の暗号鍵解析装置。
【０１９８】
（付記８）前記分割部は、前記生成元のべき乗部分を上位部と下位部にわけ、前記上位部および下位部分をそれぞれ、第１部分と第２部分に分割し、前記第２演算部は、前記上位部の第２部分または前記下位部の第２部分の内どちらか一方に、自己同型写像を適用することを特徴とする付記５、６または７に記載の暗号鍵解析装置。
【０１９９】
（付記９）コンピュータに
楕円曲線離散対数問題の解を楕円曲線上の点に対応する生成元のべき乗で示し、前記生成元のべき乗部分を第１部分と第２部分に分割する分割手順と、
前記第１部分の値を所定の値域で変化させた場合に前記生成元をべき乗することで算出される値を第１テーブルに格納する第１演算手順と、
前記第２部分の値を所定の値域で変化させた場合に前記生成元をべき乗することで算出される値と、前記生成元のべき乗部分の一部に自己同型写像を適用した値とを組あわせた値を第２テーブルに格納する第２演算手順と、
前記第１テーブルに格納された値と前記第２テーブルに格納された値とを比較し、一致した値に基づいて前記楕円曲線離散対数問題の解を算出することで暗号鍵を解析する暗号鍵解析手順と
を実行させることを特徴とする暗号鍵解析プログラム。
【０２００】
（付記１０）前記第２演算手順は、前記第１演算ステップが変化させる所定の値域とは異なる値域によって、前記第１部分の値を変化させた場合に、前記生成元をべき乗することで算出される値と、前記生成元のべき乗部分の一部に自己同型写像を適用した値とを組あわせた値を第２テーブルに格納することを特徴とする付記９に記載の暗号鍵解析プログラム。
【０２０１】
（付記１１）前記第１演算手順は、前記生成元のべき乗部分の一部に自己同型写像を適用した値のうち所定の条件を満たす値と、前記第２部分の値を所定の値域で変化させた場合に前記生成元をべき乗することで算出される値とを組あわせた値を前記第１テーブルに格納し、前記第２演算手順は、前記生成元のべき乗部分の一部に自己同型写像を適用した値のうち所定の条件を満たす値と、前記第１部分の値を所定の値域で変化させた場合に前記生成元をべき乗することで算出される値とを組あわせた値を前記第２テーブルに格納することを特徴とする付記９または１０に記載の暗号鍵解析プログラム。
【０２０２】
（付記１２）前記分割手順は、前記生成元のべき乗部分を上位部と下位部にわけ、前記上位部および下位部分をそれぞれ、第１部分と第２部分に分割し、前記第２演算手順は、前記上位部の第２部分または前記下位部の第２部分の内どちらか一方に、自己同型写像を適用することを特徴とする付記９、１０または１１に記載の暗号鍵解析プログラム。
【符号の説明】
【０２０３】
１３１ パラメータ取得部
１３２ テーブル生成部
１３３ テーブル比較部
１３４ 未知数算出部
１３５ 制御部
【特許請求の範囲】
【請求項１】
コンピュータが、
楕円曲線離散対数問題の解を楕円曲線上の点に対応する生成元のべき乗で示し、前記生成元のべき乗部分を第１部分と第２部分に分割する分割ステップと、
前記第１部分の値を所定の値域で変化させた場合に前記生成元をべき乗することで算出される値を第１テーブルに格納する第１演算ステップと、
前記第２部分の値を所定の値域で変化させた場合に前記生成元をべき乗することで算出される値と、前記生成元のべき乗部分の一部に自己同型写像を適用した値とを組あわせた値を第２テーブルに格納する第２演算ステップと、
前記第１テーブルに格納された値と前記第２テーブルに格納された値とを比較し、一致した値に基づいて前記楕円曲線離散対数問題の解を算出することで暗号鍵を解析する暗号鍵解析ステップと
を実行することを特徴とする暗号鍵解析方法。
【請求項２】
前記第２演算ステップは、前記第１演算ステップが変化させる所定の値域とは異なる値域によって、前記第１部分の値を変化させた場合に、前記生成元をべき乗することで算出される値と、前記生成元のべき乗部分の一部に自己同型写像を適用した値とを組あわせた値を第２テーブルに格納することを特徴とする請求項１に記載の暗号鍵解析方法。
【請求項３】
前記第１演算ステップは、前記生成元のべき乗部分の一部に自己同型写像を適用した値のうち所定の条件を満たす値と、前記第２部分の値を所定の値域で変化させた場合に前記生成元をべき乗することで算出される値とを組あわせた値を前記第１テーブルに格納し、前記第２演算ステップは、前記生成元のべき乗部分の一部に自己同型写像を適用した値のうち所定の条件を満たす値と、前記第１部分の値を所定の値域で変化させた場合に前記生成元をべき乗することで算出される値とを組あわせた値を前記第２テーブルに格納することを特徴とする請求項１または２に記載の暗号鍵解析方法。
【請求項４】
前記分割ステップは、前記生成元のべき乗部分を上位部と下位部にわけ、前記上位部および下位部分をそれぞれ、第１部分と第２部分に分割し、前記第２演算ステップは、前記上位部の第２部分または前記下位部の第２部分の内どちらか一方に、自己同型写像を適用することを特徴とする請求項１、２または３に記載の暗号鍵解析方法。
【請求項５】
楕円曲線離散対数問題の解を楕円曲線上の点に対応する生成元のべき乗で示し、前記生成元のべき乗部分を第１部分と第２部分に分割する分割部と、
前記第１部分の値を所定の値域で変化させた場合に前記生成元をべき乗することで算出される値を第１テーブルに格納する第１演算部と、
前記第２部分の値を所定の値域で変化させた場合に前記生成元をべき乗することで算出される値と、前記生成元のべき乗部分の一部に自己同型写像を適用した値とを組あわせた値を第２テーブルに格納する第２演算部と、
前記第１テーブルに格納された値と前記第２テーブルに格納された値とを比較し、一致した値に基づいて前記楕円曲線離散対数問題の解を算出することで暗号鍵を解析する暗号鍵解析部と
を備えたことを特徴とする暗号鍵解析装置。
【請求項６】
コンピュータに
楕円曲線離散対数問題の解を楕円曲線上の点に対応する生成元のべき乗で示し、前記生成元のべき乗部分を第１部分と第２部分に分割する分割手順と、
前記第１部分の値を所定の値域で変化させた場合に前記生成元をべき乗することで算出される値を第１テーブルに格納する第１演算手順と、
前記第２部分の値を所定の値域で変化させた場合に前記生成元をべき乗することで算出される値と、前記生成元のべき乗部分の一部に自己同型写像を適用した値とを組あわせた値を第２テーブルに格納する第２演算手順と、
前記第１テーブルに格納された値と前記第２テーブルに格納された値とを比較し、一致した値に基づいて前記楕円曲線離散対数問題の解を算出することで暗号鍵を解析する暗号鍵解析手順と
を実行させることを特徴とする暗号鍵解析プログラム。
【請求項１】
コンピュータが、
楕円曲線離散対数問題の解を楕円曲線上の点に対応する生成元のべき乗で示し、前記生成元のべき乗部分を第１部分と第２部分に分割する分割ステップと、
前記第１部分の値を所定の値域で変化させた場合に前記生成元をべき乗することで算出される値を第１テーブルに格納する第１演算ステップと、
前記第２部分の値を所定の値域で変化させた場合に前記生成元をべき乗することで算出される値と、前記生成元のべき乗部分の一部に自己同型写像を適用した値とを組あわせた値を第２テーブルに格納する第２演算ステップと、
前記第１テーブルに格納された値と前記第２テーブルに格納された値とを比較し、一致した値に基づいて前記楕円曲線離散対数問題の解を算出することで暗号鍵を解析する暗号鍵解析ステップと
を実行することを特徴とする暗号鍵解析方法。
【請求項２】
前記第２演算ステップは、前記第１演算ステップが変化させる所定の値域とは異なる値域によって、前記第１部分の値を変化させた場合に、前記生成元をべき乗することで算出される値と、前記生成元のべき乗部分の一部に自己同型写像を適用した値とを組あわせた値を第２テーブルに格納することを特徴とする請求項１に記載の暗号鍵解析方法。
【請求項３】
前記第１演算ステップは、前記生成元のべき乗部分の一部に自己同型写像を適用した値のうち所定の条件を満たす値と、前記第２部分の値を所定の値域で変化させた場合に前記生成元をべき乗することで算出される値とを組あわせた値を前記第１テーブルに格納し、前記第２演算ステップは、前記生成元のべき乗部分の一部に自己同型写像を適用した値のうち所定の条件を満たす値と、前記第１部分の値を所定の値域で変化させた場合に前記生成元をべき乗することで算出される値とを組あわせた値を前記第２テーブルに格納することを特徴とする請求項１または２に記載の暗号鍵解析方法。
【請求項４】
前記分割ステップは、前記生成元のべき乗部分を上位部と下位部にわけ、前記上位部および下位部分をそれぞれ、第１部分と第２部分に分割し、前記第２演算ステップは、前記上位部の第２部分または前記下位部の第２部分の内どちらか一方に、自己同型写像を適用することを特徴とする請求項１、２または３に記載の暗号鍵解析方法。
【請求項５】
楕円曲線離散対数問題の解を楕円曲線上の点に対応する生成元のべき乗で示し、前記生成元のべき乗部分を第１部分と第２部分に分割する分割部と、
前記第１部分の値を所定の値域で変化させた場合に前記生成元をべき乗することで算出される値を第１テーブルに格納する第１演算部と、
前記第２部分の値を所定の値域で変化させた場合に前記生成元をべき乗することで算出される値と、前記生成元のべき乗部分の一部に自己同型写像を適用した値とを組あわせた値を第２テーブルに格納する第２演算部と、
前記第１テーブルに格納された値と前記第２テーブルに格納された値とを比較し、一致した値に基づいて前記楕円曲線離散対数問題の解を算出することで暗号鍵を解析する暗号鍵解析部と
を備えたことを特徴とする暗号鍵解析装置。
【請求項６】
コンピュータに
楕円曲線離散対数問題の解を楕円曲線上の点に対応する生成元のべき乗で示し、前記生成元のべき乗部分を第１部分と第２部分に分割する分割手順と、
前記第１部分の値を所定の値域で変化させた場合に前記生成元をべき乗することで算出される値を第１テーブルに格納する第１演算手順と、
前記第２部分の値を所定の値域で変化させた場合に前記生成元をべき乗することで算出される値と、前記生成元のべき乗部分の一部に自己同型写像を適用した値とを組あわせた値を第２テーブルに格納する第２演算手順と、
前記第１テーブルに格納された値と前記第２テーブルに格納された値とを比較し、一致した値に基づいて前記楕円曲線離散対数問題の解を算出することで暗号鍵を解析する暗号鍵解析手順と
を実行させることを特徴とする暗号鍵解析プログラム。
【図１Ａ】
【図１Ｂ】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【図２７】
【図２８】
【図２９】
【図１Ｂ】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【図２７】
【図２８】
【図２９】
【公開番号】特開２０１２−３２６４６（Ｐ２０１２−３２６４６Ａ）
【公開日】平成２４年２月１６日（２０１２．２．１６）
【国際特許分類】
【出願番号】特願２０１０−１７２７９６（Ｐ２０１０−１７２７９６）
【出願日】平成２２年７月３０日（２０１０．７．３０）
【国等の委託研究の成果に係る記載事項】（出願人による申告）平成２０年度、独立行政法人情報通信研究機構、「適切な暗号技術を選択可能とするための新しい暗号技術の評価手法 〜暗号の技術評価に関する研究開発〜」委託研究、産業技術力強化法第１９条の適用を受ける特許出願
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【Ｆターム（参考）】
【公開日】平成２４年２月１６日（２０１２．２．１６）
【国際特許分類】
【出願日】平成２２年７月３０日（２０１０．７．３０）
【国等の委託研究の成果に係る記載事項】（出願人による申告）平成２０年度、独立行政法人情報通信研究機構、「適切な暗号技術を選択可能とするための新しい暗号技術の評価手法 〜暗号の技術評価に関する研究開発〜」委託研究、産業技術力強化法第１９条の適用を受ける特許出願
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【Ｆターム（参考）】
[ Back to top ]