暗号鍵解析方法、暗号鍵解析装置および暗号鍵解析プログラム
【課題】記憶容量が圧迫されずに、暗号鍵を解くこと。
【解決手段】所定の点に対して自己同型写像を適用して算出した第１の点の集合の中から代表点を選択して記憶部に記憶させる。この集合に関する代表点に対して擬似乱数を用いて算出した点に対して自己同型写像を適用することで、第１の点の集合に関する新たな代表点を記憶部に追加して記憶させる。また、所定の暗号鍵から定まる点に対して自己同型写像を適用して算出した第２の点の集合の中から代表点を記憶部に記憶させる。この集合の点に関する代表点に対して擬似乱数を用いて点を算出し、点に対して自己同型写像を適用することで、第２の点の集合の新たな代表点を記憶部に追加して記憶させる。そして、第１および第２の点の集合に関する各代表点のうち、一致した代表点に基づいて暗号鍵を算出する。
【解決手段】所定の点に対して自己同型写像を適用して算出した第１の点の集合の中から代表点を選択して記憶部に記憶させる。この集合に関する代表点に対して擬似乱数を用いて算出した点に対して自己同型写像を適用することで、第１の点の集合に関する新たな代表点を記憶部に追加して記憶させる。また、所定の暗号鍵から定まる点に対して自己同型写像を適用して算出した第２の点の集合の中から代表点を記憶部に記憶させる。この集合の点に関する代表点に対して擬似乱数を用いて点を算出し、点に対して自己同型写像を適用することで、第２の点の集合の新たな代表点を記憶部に追加して記憶させる。そして、第１および第２の点の集合に関する各代表点のうち、一致した代表点に基づいて暗号鍵を算出する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号鍵解析方法、暗号鍵解析装置および暗号鍵解析プログラムに関する。
【背景技術】
【０００２】
近年、ネットショッピングやネットバンキングなどが普及している。ネットショッピングやネットバンキングにおいて通信を行う場合には、ＳＳＬ(Secure Sockets Layer)／ＴＬＳ(Transport Layer Security)などの暗号技術が用いられる。暗号技術の代表である暗号化方式は、大別すると共通鍵暗号と公開鍵暗号との２つに分類される。
【０００３】
共通鍵暗号は、送信者と受信者とが同じ鍵を持つことにより暗号通信を行う方式である。すなわち、共通鍵暗号では、送信者は、あるメッセージを秘密の暗号鍵に基づいて暗号化して受信者に送る。受信者は、この暗号鍵を用いて暗号文を復号し、メッセージを入手する。
【０００４】
公開鍵暗号では、送信者は、受信者の公開されている鍵（公開鍵）でメッセージを暗号化して送信する。受信者は暗号化されたメッセージを自分だけが保持している鍵（秘密鍵）で復号する。すなわち、公開鍵暗号では、公開鍵は情報を暗号化するための鍵である。また、秘密鍵は、公開鍵により暗号化された情報を復号するための鍵である。公開鍵で暗号化された情報は、秘密鍵でのみ復号することができる。
【０００５】
公開鍵暗号は、公開鍵を公開しても安全性を確保できるようにするために、数学的に難しいとされている問題に基づいて設計されている。例えば、ＲＳＡ(Rivest Shamir Adleman)暗号は、素因数分解問題と呼ばれる数学的問題の困難性に基づいている。また、エルガマル暗号は、離散対数問題と呼ばれる数学的問題の困難性に基づいている。さらに、楕円曲線暗号（Elliptic Curve Cryptosystem）は、楕円曲線上の離散対数問題を基に設計されている。なお、楕円曲線上の離散対数問題を「楕円曲線離散対数問題」と称する。このように、公開鍵暗号の安全性は、数学的問題の困難性に基づいている。そのため、これらの数学的問題の解読計算量が、公開鍵暗号の安全性の指標となる。
【０００６】
楕円曲線暗号は、楕円曲線離散対数問題に基づく暗号である。楕円曲線離散対数問題に基づく暗号は、楕円曲線上の点Ｐおよび単位元となる無限遠点Οの集合のなす加法群において定義される。この加法群に含まれる点の数を位数ｒと呼ぶ。 楕円曲線上の点Ｐ１とＰ２に対する演算として、以下が容易に計算できることが知られている。
加算：Ｐ３＝Ｐ１＋Ｐ２＝Ｐ２＋Ｐ１
２倍算：Ｐ２＝２×Ｐ１＝Ｐ１＋Ｐ１
減算：Ｐ３＝Ｐ１−Ｐ２
零点：Ο（無限遠点）＝Ｐ１−Ｐ１
スカラ倍算：ｋ×Ｐ＝Ｐ＋Ｐ＋・・・＋Ｐ（ｋ個のＰの和）
【０００７】
ここで、ｋ×ＰとＰとからｋを算出する問題を楕円曲線離散対数問題という。位数ｒが巨大な場合、解を求めることは困難であることが知られている。楕円曲線離散対数問題が困難であるという仮定のもとで、楕円曲線のパラメータを用いた楕円曲線暗号の安全性が保証される。なお、ｋは秘密鍵として使用されることが多い。
【０００８】
さらに近年では、ペアリングという公開鍵暗号技術が注目されている。ペアリングは楕円曲線暗号の一種である。楕円曲線上の２点に対するペアリングと呼ばれる演算を用いることで、従来の楕円曲線暗号の機能を拡張する。この場合、楕円曲線離散対数問題の困難性に加え、いくつかの数学的問題の困難性に関する新たな仮定が必要となる。例えばペアリングを使った放送暗号では、Ｌ−双線形性Ｄｉｆｆｉｅ‐Ｈｅｌｌｍａｎ指数問題（Ｌ−ＢＤＨＥ問題）と呼ばれる数学的問題の困難性を仮定することがある。ここでＬ−ＢＤＨＥ問題とは、Ｐ、ｋ×Ｐ、ｋ2×Ｐ、ｋ3×Ｐ、・・・、ｋL×ＰからｋやｋL+1を求める問題である。この場合、Ｐ、ｋ×Ｐからｋを求める楕円曲線離散対数問題に比べ、ｋ2×Ｐ、ｋ3×Ｐ、…、ｋL×Ｐなどの補助情報があることから、この問題を補助入力付き楕円曲線離散対数問題と呼ぶことがある。
【０００９】
また、数学的問題として、例えば、Ｐ、ｋ×Ｐ、ｋｄ×Ｐ及びｄから、ｋを求める補助入力付き楕円曲線離散対数問題がある。ここで、ｄは（ｒ−１）の約数である。この問題を解く方法として、例えば、Ｃｈｅｏｎ解析法が知られている。Ｃｈｅｏｎ解析法は、Ｂａｂｙ−Ｓｔｅｐ Ｇｉａｎｔ−Ｓｔｅｐ解析法（ＢＳＧＳ）を用いて攻撃を行う方法である。Ｃｈｅｏｎ解析法では、ＢＳＧＳを二重に処理することで攻撃を行う。ＢＳＧＳでは２種類のテーブルを作成し、各テーブルに記憶された計算結果を比較して、秘密鍵ｋを求める。これにより、最小ｒ１／４の数倍程度の計算量で暗号鍵としての秘密鍵ｋを解くことができる。
【先行技術文献】
【非特許文献】
【００１０】
【非特許文献１】D.Hankerson,A.Menezes and S.Vanstone“Guide to Elliptic Curve Cryptography”p.161‐163
【発明の概要】
【発明が解決しようとする課題】
【００１１】
しかしながら、上記のＣｈｅｏｎ解析法では、記憶される上記計算結果の量が、ｒ１／４程度と大きいため、記憶容量が圧迫されるという問題があった。
【００１２】
開示の技術は、上記に鑑みてなされたものであって、記憶容量が圧迫されずに、暗号鍵を解くことができる暗号鍵解析方法、暗号鍵解析装置、および暗号鍵解析プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１３】
本願の開示する暗号鍵解析方法は、一つの態様において、コンピュータが、第１の代表点選択ステップと、第２の代表点選択ステップと、暗号鍵算出ステップとを実行することを特徴とする。第１の代表点選択ステップは、楕円曲線上の所定の点に対して自己同型写像を適用して第１の点の集合を算出する。第１の代表点選択ステップは、第１の点の集合の中から代表点を選択して記憶部に記憶させる。第１の代表点選択ステップは、記憶部に記憶された第１の点の集合に関する代表点に対して擬似乱数を用いて楕円曲線上の点を算出する。第１の代表点選択ステップは、点に対して自己同型写像を適用することで、第１の点の集合に関する新たな代表点を選択して記憶部に追加して記憶させる。第２の代表点選択ステップは、楕円曲線上において所定の暗号鍵から定まる点に対して自己同型写像を適用して第２の点の集合を算出する。第２の代表点選択ステップは、第２の点の集合の中から代表点を選択して記憶部に記憶させる。第２の代表点選択ステップは、第２の集合の点に関する代表点に対して擬似乱数を用いて楕円曲線上の点を算出する。第２の代表点選択ステップは、点に対して自己同型写像を適用することで、第２の点の集合の新たな代表点を記憶部に追加して記憶させる。暗号鍵算出ステップは、記憶部に記憶された第１の点の集合に関する代表点と第２の点の集合に関する代表点とを比較し、一致した代表点に基づいて暗号鍵を算出する。
【発明の効果】
【００１４】
本願の開示する暗号鍵解析方法の一つの態様によれば、記憶容量が圧迫されずに、暗号鍵を解くことができるという効果を奏する。
【図面の簡単な説明】
【００１５】
【図１】図１は、ＢＳＧＳの具体例を説明するための図である。
【図２】図２は、Ｃｈｅｏｎ解析法の具体例を説明するための図である。
【図３】図３は、Ｃｈｅｏｎ解析法の具体例を説明するための図である。
【図４】図４は、Ｃｈｅｏｎ解析法の具体例を説明するための図である。
【図５】図５は、ＲＷ関数の適用を説明するための図である。
【図６】図６は、特徴点のテクニックの併用を説明するための図である。
【図７】図７は、実施例１に係る暗号鍵解読装置の構成を示す図である。
【図８】図８は、テーブル生成部のブロック図である。
【図９】図９は、実施例１に係る解の計算処理の処理手順を示すフローチャートである。
【図１０】図１０は、解の計算処理を説明するための図である。
【図１１】図１１は、ループの発生を示す図である。
【図１２】図１２は、実施例２に係る暗号鍵解読装置の構成を示す図である。
【図１３】図１３は、テーブル生成部のブロック図である。
【図１４】図１４は、実施例２に係る解の計算処理の処理手順を示すフローチャートである。
【図１５】図１５は、実施例２の暗号鍵解読装置の効果を説明するための図である。
【図１６】図１６は、暗号鍵解読プログラムを実行するコンピュータを示す図である。
【発明を実施するための形態】
【００１６】
まず、本願の開示する暗号鍵解読装置における技術を説明する上での原理を図面に基づいて、いくつか説明する。
【００１７】
［Ｂａｂｙ−Ｓｔｅｐ Ｇｉａｎｔ−Ｓｔｅｐ解析法］
最初に、Ｂａｂｙ−Ｓｔｅｐ Ｇｉａｎｔ−Ｓｔｅｐ解析法について説明する。以下、Ｂａｂｙ−Ｓｔｅｐ Ｇｉａｎｔ−Ｓｔｅｐ解析法を「ＢＳＧＳ」と称する。ＢＳＧＳは、楕円曲線離散対数問題の効率的な解析法の一つである。位数ｒの楕円曲線パラメータを使用した場合、ＢＳＧＳでは、（２×ｒ１／２）回程度の楕円曲線演算によって楕円曲線離散対数問題が解かれる。ＢＳＧＳでは、秘密鍵ｋが位数ｒ１／２進数で上位と下位とに分割される。ＢＳＧＳでは、秘密鍵ｋの下位値が０となるものを含むテーブルをＢａｂｙ−Ｓｔｅｐで作成する。また、ＢＳＧＳでは、秘密鍵ｋの下位値が０の場合を総当りするテーブルをＧｉａｎｔ−Ｓｔｅｐで作成する。さらに、ＢＳＧＳでは、各テーブルの値を比較する。そして、ＢＳＧＳでは、比較結果に基づいて、秘密鍵ｋを解として算出する。ＢＳＧＳでは、各テーブルの値を比較することで、効率的に楕円曲線離散対数問題が解かれる。
【００１８】
図１は、ＢＳＧＳの具体例を説明するための図である。位数ｒ＝９７とし、秘密鍵ｋ＝９６とした場合、図１に示すように、ＢＳＧＳでは、Ｂａｂｙ−Ｓｔｅｐで（ｋ×Ｐ−ｉ×Ｐ）（ｉ＝０〜９）を計算する。なお、Ｐは所定の楕円曲線上の所定の点である。Ｂａｂｙ−Ｓｔｅｐでは、さらに、計算結果をＴｂテーブル１に登録する。これにより、Ｔｂテーブル１が作成される。ＢＳＧＳでは、Ｇｉａｎｔ−Ｓｔｅｐで、（ｊ×１０×Ｐ）（ｊ＝０〜９）を計算する。Ｇｉａｎｔ−Ｓｔｅｐでは、さらに、計算結果をＴｇテーブル２に登録する。これにより、Ｔｇテーブル２が作成される。ＢＳＧＳでは、Ｔｂテーブル１の各値とＴｇテーブル２の各値とを比較する。ここで、値とは、例えば、図１に示す例では、点の座標を指す。図１に示す例の場合では、Ｔｂテーブル１の値（５０，１２）と、Ｔｇテーブル２の値（５０，１２）とが一致する。このとき、ｉ＝６、ｊ＝９となる。ここで、秘密鍵ｋ＝（ｉ＋ｊ×１０）と表される。よって、図１に示す例の場合では、秘密鍵ｋ＝（６＋９×１０）＝９６となる。ＢＳＧＳでは、このようにして秘密鍵ｋが解として算出される。この例の場合では、楕円曲線演算は２０回（≒２×９６１／２）行われる。
【００１９】
ここで、総当り法で楕円曲線離散対数問題を解く場合を説明する。総当り法で楕円曲線離散対数問題を解く場合には、平均ｒ／２回程度の楕円曲線演算が行われる。例えば、位数ｒ＝９７とし、秘密鍵ｋ＝９６とした場合、総当り法では、Ｐとｋ×Ｐとに対し、０×Ｐ，１×Ｐ，・・・，９６×Ｐを計算する。そして、総当り法では、秘密鍵ｋ＝９６を解として算出する。この場合、平均でｒ／２＝４８回の楕円曲線演算が行われる。
【００２０】
以上のことから、ＢＳＧＳは、総当り法と比較して、楕円曲線離散対数問題を解く場合における楕円曲線演算の回数が削減される。
【００２１】
［Ｃｈｅｏｎ解析法］
次に、Ｃｈｅｏｎ解析法について説明する。Ｃｈｅｏｎ解析法は、補助入力付き楕円曲線離散対数問題に対して、ＢＳＧＳ法を適用して解を算出する方法である。Ｃｈｅｏｎ解析法では、ＢＳＧＳを二重に処理することで計算量が削減される。例えば、Ｃｈｅｏｎ解析法では、（ｄ１／２＋（ｒ／ｄ）１／２）回程度の楕円曲線演算で、補助入力付き楕円曲線離散対数問題の解が算出される。特に、ｄ≒ｒ１／２となる場合が最も効果的に計算量が削減される。例えば、ｄ≒ｒ１／２となる場合、ｒ１／４回程度の楕円曲線演算で解が算出される。なお、ｄは（ｒ−１）の約数である。
【００２２】
Ｃｈｅｏｎ解析法の具体例について説明する。図２〜４は、Ｃｈｅｏｎ解析法の具体例を説明するための図である。
【００２３】
Ｃｈｅｏｎ解析法では、まず、位数ｒの生成元ζを求め、秘密鍵ｋ＝ζｙとする（ステップＳ１）。ここで、ｙの値域は０〜ｒ−１である。図２には、比較対象のｋ×Ｐがζｙ×Ｐに変換された例が示されている。
【００２４】
次に、図２に示すように、ζの指数部分のｙを上位ｙＨと下位ｙＬ−ｉとに分割し、ｋを上位ｊと、下位値を０とした下位ｊ´とに分割する（ステップＳ２）。なお、ｙＨは、ｙを（（ｒ−１）／ｄ）で除算した商とする。また、ｙＬは、ｙを（（ｒ−１）／ｄ）で除算した余りとする。
【００２５】
次に、方程式ｋｄ×Ｐ＝（ζｄ）ｚ×Ｐからｚを算出する（ステップＳ３）。図３には、比較対象のζｙ×Ｐとζｋ×Ｐとを変形する例が示されている。ｚの算出の際には、図３に示すように、ｚを上位ｚＨと下位ｚＬ−ｉとに分割してＢＳＧＳと同等の処理を行う。なお、ｚを算出することと、ｙＬを算出することは数学的に等価である。よって、ｚが算出されることで、ｙＬが算出される。
【００２６】
次に、算出されたｙＬを用いて、図４に示すｗ（ｙＨ）を算出する（ステップＳ４）。ここで、ｗは、ｋ＝ζｙＬ＋ｗ（ｒ−１）／ｄを満たす。図４には、比較対象のζｙ×Ｐとζｋ×Ｐとを変形する例が示されている。このｗの算出の際には、図４に示すように、ｗを上位ｗＨと下位ｗＬ−ｉとに分割してＢＳＧＳと同等の処理を行う。
【００２７】
次に、ステップＳ３で算出されたｙＬと、ステップＳ４で算出されたｙＨとからｙを算出する（ステップＳ５）。そして、ステップＳ５で算出されたｙを用いて、秘密鍵ｋ＝ζｙを算出する（ステップＳ６）。以上、Ｃｈｅｏｎ解析法の具体例について説明した。このようにして、Ｃｈｅｏｎ解析法では、秘密鍵ｋの算出が行われる。
【００２８】
［ランダムウォーク関数の適用］
上記のように、Ｃｈｅｏｎ解析法は補助入力付き楕円曲線対数問題を効率的に解くことが可能である。しかしながら、Ｂａｂｙ−Ｓｔｅｐ、Ｇｉａｎｔ−Ｓｔｅｐで生成するＴｂテーブル１、Ｔｇテーブル２のサイズが大きいという問題がある。例えば、有限体ＧＦ（３１２７）におけるある楕円曲線では、パラメータｒはｒ＝９３１４８５６００４９８６２２３９６２６０１３９９となる。この場合、最適なｄを用いたとしても、Ｔｂテーブル１およびＴｇテーブル２の各テーブルには、１７４７０００個の楕円曲線上の点データが登録される。このとき、各テーブルのサイズは約８０ＭＢｙｔｅとなる。よって、計算量を増大させずに、解を得るための計算において記憶されるデータ量が削減されることが望まれる。
【００２９】
このような背景から、計算量を増大させずに、解を得るための計算において記憶されるデータ量が削減される方法が生み出された。このような方法では、例えば、Ｃｈｅｏｎ解析法において、ＢＳＧＳを用いずに、ランダムウォーク関数を適用する。そこで、この方法について説明する。また、以下、ランダムウォーク関数を「ＲＷ関数」と称する。ＲＷ関数とは、楕円曲線上の点を入力として、楕円曲線上の別の点を出力する関数である。例えば、ＲＷ関数は、楕円曲線上の点Ｐに対し、ζｄ×Ｒｎｄ（Ｐ）×Ｐのように定義される。ここで、Ｒｎｄ（Ｐ）は、点Ｐから一意的に０以上で（（ｒ−１）／ｄ）以下のランダムな整数を生成する擬似乱数生成関数である。なお、ランダムな整数を「擬似乱数」と称する。
【００３０】
図５は、ＲＷ関数の適用を説明するための図である。Ｃｈｅｏｎ解析法のステップＳ３に、上記したＲＷ関数を適用した場合、図５に示すように、点Ｐを開始点として、点ＰにＲＷ関数を適用して得られる点Ｐｓを算出し、算出された点Ｐｓを記憶する。次に、算出された点ＰｓにＲＷ関数を適用して得られる点Ｐｓを新たに算出し、新たに算出された点Ｐｓを記憶する。以降、この動作を繰り返し、点Ｐを開始点とした場合のＲＷ関数を適用して得られる各点Ｐｓがテーブルに登録される。同様に、図５に示すように、点ｋｄ×Ｐを開始点として、点ｋｄ×ＰにＲＷ関数を適用して得られる点Ｐｔを算出し、算出された点を記憶する。次に、算出された点にＲＷ関数を適用して得られる点を新たに算出し、新たに算出された点を記憶する。以降、この動作を繰り返し、点ｋｄ×Ｐを開始点とした場合のＲＷ関数を適用して得られる各点Ｐｔがテーブルに登録される。
【００３１】
そして、生成されたこれらのテーブルを比較し、一致した点Ｐ´を検出する。一致した点の情報からｋｄ×Ｐ＝ζｄ×ｋ１×Ｐを満たすｋ１を算出する。このとき、誕生日の逆理により、テーブルの大きさは（（ｒ−１）／ｄ）１／２程度でよいことが知られている。そのため、テーブル作成に必要な楕円曲線演算の回数も（（ｒ−１）／ｄ）１／２程度となる。なお、図５に示すように、ある点Ｐ´で一致すると、その後は、新たに算出された互いの点が一致するようになる。
【００３２】
［特徴点のテクニックの併用］
そして、特徴点のテクニックを併用して、以下のようにして、計算量を増大させずに、テーブルに記憶されるデータ量を削減する。図６は、特徴点のテクニックの併用を説明するための図である。図６に示すように、算出した全ての点Ｐｓ，Ｐｔを記憶せず、特徴的な点（特徴点）Ｐ´ｓ，Ｐ´ｔだけを記憶する。なお、図６では、テーブルに記憶された点Ｐ´ｓ，Ｐ´ｔは実線で示され、記憶されない点Ｐｓ，Ｐｔは破線で示されている。ここで、特徴点とは、特徴的な性質を持つ点のことである。例えば、特徴点は、点のｘ座標の下位１６ビットがすべて０であるような点である。この場合、特徴点は、確率的に２１６個に１個の割合で算出される。よって、テーブルに記憶されるデータ量は１／２１６に削減される。したがって、ＢＳＧＳを用いるＣｈｅｏｎ解析法と比較すると、計算量を増大させずに、テーブルに記憶されるデータ量が削減される。なお、一致する点Ｐ´がテーブルに一部記憶されない可能性がある。しかしながら、一致が起きれば、その後に出現する特徴点Ｐ´´でも一致することになる。そのため、問題は生じない。
【００３３】
［自己同型写像］
次に、自己同型写像について説明する。一部の楕円曲線では、楕円曲線上の点ＰのＦｒｏｂｅｎｉｕｓ写像Φ（Ｐ）が高速に計算できる。例えば、有限体ＧＦ（３１２７）における楕円曲線では、点Ｐ＝（ｘ，ｙ）のＦｒｏｂｅｎｉｕｓ写像Φ（Ｐ）＝（ｘ３，ｙ３）も同一の楕円曲線上の点となる。また、Φ（Ｐ）＝ｓ×Ｐとなるｓを簡単に求めることができる。Ｆｒｏｂｅｎｉｕｓ写像Φ（Ｐ）の計算は、各座標の値を３乗するだけである。そのため、他の楕円曲線演算に比べて高速に計算できる。よって、ｓ×Ｐも高速に計算できる。なお、点ＰにＦｒｏｂｅｎｉｕｓ写像Φ（Ｐ）をＩ回適用して得られる点であるΦ（Ｉ）（Ｐ）は以下のように記述される。すなわち、点Φ（Ｉ）（Ｐ）＝Φ（Φ（・・・（Φ（Ｐ））））となる。
【００３４】
また、一部の楕円曲線では、楕円曲線上の点のマイナス写像についても高速に計算できる。なお、マイナス写像とは、例えば、点Ｐを点−Ｐに対応させる写像である。例えば、有限体ＧＦ（３１２７）における楕円曲線では、点Ｐ＝（ｘ，ｙ）のマイナス写像−Ｐ＝（ｘ，−ｙ）も同一の楕円曲線上の点となる。また、−Ｐ＝ｔ×Ｐと表される。他の楕円曲線演算に比べて高速に計算できるため、ｔ×Ｐも高速に計算できる。
【００３５】
これらＦｒｏｂｅｎｉｕｓ写像およびマイナス写像は、楕円曲線上の点Ｐを同一の楕円曲線上の点に対応させる自己同型写像である。
【００３６】
［自己同型写像のべき表現］
そして、これらの自己同型写像を、べき表現する場合について説明する。Ｃｈｅｏｎ解析法において、自己同型写像を使用するには、自己同型写像が生成元ζの指数乗倍で表現される。有限体ＧＦ（ｑｍ）における楕円曲線の場合、任意の点にＦｒｏｂｅｎｉｕｓ写像をｍ回適用すると元の点に戻る。つまり、Φ（ｍ）（Ｐ）＝Ｐとなる。また、任意の点にマイナス写像を２回適用すると元の点に戻る。つまり、（−１）２×Ｐ＝Ｐとなる。そこで、自己同型写像（−１）（ｉ）Φ（ｊ）×Ｐ＝ζ（ｉ・ｍ＋２・ｃ・ｊ）（ｒ−１）／２ｍ×Ｐと表される。このように、自己同型写像（−１）（ｉ）Φ（ｊ）×Ｐはζのべき乗で表される。このように、べき乗で表すことを「べき表現」と称する。ここで、ｃは楕円曲線と生成元の値とによって一意に決定される定数である。また、ｉ＝０〜１である。また、ｊ＝０〜ｍ−１である。例えば、有限体ＧＦ（３１２７）、ζ＝３の場合、ｍ＝１２７、ｃ＝１１０となる。このとき、自己同型写像は以下のように表される。すなわち、（−１）（ｉ）Φ（ｊ）×Ｐ＝ζ（１２７・ｉ＋２２０・ｊ）（ｒ−１）／２５４×Ｐとなる。
【００３７】
以上、本願の開示する暗号鍵解読装置における技術を説明する上での原理を説明した。以下に、本願の開示する暗号鍵解読装置の実施例を図面に基づいて詳細に説明する。なお、この実施例によりこの発明が限定されるものではない。
【実施例１】
【００３８】
［実施例１の装置構成］
本実施例１に係る暗号鍵解読装置について説明する。図７は、本実施例１に係る暗号鍵解読装置の構成を示す図である。暗号鍵解読装置１００は、楕円曲線離散対数問題を解いて暗号鍵である秘密鍵ｋを算出する装置である。図７に示すように、暗号鍵解読装置１００は、入力部１１０、出力部１２０、処理部１３０、および記憶部１４０を有する。
【００３９】
入力部１１０は、外部から情報を入力する。例えば、入力部１１０は、ユーザからの指示を受け付けて、受け付けた指示を処理部１３０に入力する。入力部１１０は、例えば、通信によって外部装置からパラメータを取得し、取得したパラメータを処理部１３０に入力してもよい。また、入力部１１０は、例えば、マウスやキーボードを含んでもよい。また、指示としては、例えば、詳細を後述する「補助入力付き楕円曲線対数問題の解の計算処理」を実行する指示がある。以下、「補助入力付き楕円曲線対数問題の解の計算処理」を、「解の計算処理」と略する。
【００４０】
出力部１２０は、外部へ情報を出力する。例えば、出力部１２０は、秘密鍵ｋおよび計算時間Ｔを後述するＤＬＰ計算部１３４から受け付ける。なお、計算時間Ｔは、解の計算に要する時間である。出力部１２０は、受け付けた秘密鍵ｋおよび計算時間Ｔの各値を出力する。出力部１２０は、例えば、ディスプレイを含んで構成するようにしてもよい。この場合、ディスプレイに秘密鍵ｋおよび計算時間Ｔの各値が表示される。また、出力部１２０は、例えば、スピーカーを含んで構成されてもよい。この場合、スピーカーから音声によって秘密鍵ｋおよび計算時間Ｔの各値が出力される。また、出力部１２０は、通信によって外部の装置に秘密鍵ｋおよび計算時間Ｔの各値を出力してもよい。
【００４１】
記憶部１４０は、第１のテーブル１４１と第２のテーブル１４２とを有する。第１のテーブル１４１には、後述する代表点Ｐ＊ｒｅｐｉと指標ｉｎｄｅｘｉとが対応付けて登録される。第２のテーブル１４２には、後述する代表点Ｐ＊ｒｅｐｄｉと指標ｉｎｄｅｘｄｉとが対応付けて登録される。
【００４２】
処理部１３０は、パラメータ取得部１３１、テーブル生成部１３２およびテーブル比較部１３３を有する。また、処理部１３０は、ＤＬＰ（Ｄｉｓｃｒｅｔｅ Ｌｏｇａｒｉｔｈｍ Ｐｒｏｂｌｅｍ）計算部１３４および制御部１３５を有する。
【００４３】
パラメータ取得部１３１は、解の計算処理の指示が入力された場合に、以下の処理を行う。すなわち、パラメータ取得部１３１は、例えば、外部装置から入力部１１０を介してシステムパラメータを取得する。そして、パラメータ取得部１３１は、取得したシステムパラメータをテーブル生成部１３２に入力する。なお、記憶部１４０に予めシステムパラメータを記憶しておき、パラメータ取得部１３１は、記憶部１４０からこのシステムパラメータを取得してもよい。
【００４４】
システムパラメータの一例について説明する。システムパラメータには、楕円曲線Ｅ上の所定の点である点Ｐ、点（ｋ×Ｐ）、所定の暗号鍵から定まる点である点（ｋｄ×Ｐ）およびｄが含まれる。また、楕円曲線のパラメータには秘密鍵ｋのビット長なども含まれる。また、システムパラメータには、テーブルの登録番号を示す指標ｉｎｄｅｘ０が含まれる。なお、指標ｉｎｄｅｘｎは、例えば、数値ｎを示す。なお、楕円曲線のパラメータはこれらに限られない。
【００４５】
テーブル生成部１３２は、入力されたシステムパラメータに基づいて、楕円曲線Ｅ上の点Ｐに対して自己同型写像を適用して点の集合を算出する。テーブル生成部１３２は、点Ｐを開始点として算出された点（以下、第１の点と称する場合がある）の集合の中から代表点（以下、第１の代表点と称する場合がある）を選択して記憶部１４０に記憶させる。テーブル生成部１３２は、第１の代表点に対して擬似乱数を用いて楕円曲線Ｅ上の点を算出する。テーブル生成部１３２は、後述する制御部１３５の制御によってこれらの処理を繰り返し行うことで、記憶部１４０に追加して第１の代表点を記憶して、複数の第１の代表点を記憶部１４０に記憶する。
【００４６】
また、テーブル生成部１３２は、楕円曲線Ｅ上において点（ｋｄ×Ｐ）に対して自己同型写像を適用して点の集合を算出する。テーブル生成部１３２は、点（ｋｄ×Ｐ）を開始点として算出された点（以下、第２の点と称する場合がある）の集合の中から代表点（以下、第２の代表点と称する場合がある）を選択して記憶部１４０に記憶させる。テーブル生成部１３２は、第２の代表点に対して擬似乱数を用いて楕円曲線Ｅ上の点を算出する。テーブル生成部１３２は、後述するテーブル比較部１３３で第１の代表点に一致する第２の代表点が検出されるまで、制御部１３５の制御によって、これらの処理を繰り返し行う。これにより、テーブル生成部１３２は、記憶部１４０に追加して第２の代表点を記憶して、複数の第２の代表点を記憶部１４０に記憶する。
【００４７】
ここで、テーブル生成部１３２の詳細を説明する。図８はテーブル生成部１３２のブロック図である。テーブル生成部１３２は、テーブル生成制御部１５０、自己同型写像計算部１５１、代表点選択部１５２およびＲＷ関数部１５３を有する。
【００４８】
テーブル生成制御部１５０は、パラメータ取得部１３１から指標ｉｎｄｅｘ０と点Ｐ＊（点Ｐ）とを受け付ける。また、テーブル生成制御部１５０は、パラメータ取得部１３１から指標ｉｎｄｅｘ０と点Ｐ＊ｄ（ｋｄ×Ｐ）とを受け付ける。テーブル生成制御部１５０は、受け付けた点Ｐ＊または点Ｐ＊ｄを自己同型写像計算部１５１に出力する。テーブル生成制御部１５０は、代表点選択部１５２から第１の代表点である代表点Ｐ＊ｒｅｐｉ（ｉ＝０〜ｖ）または第２の代表点であるＰ＊ｒｅｐｄｉを受け付ける。テーブル生成制御部１５０は、指標ｉｎｄｅｘｉと受け付けた代表点Ｐ＊ｒｅｐｉとを対応付けて第１のテーブル１４１に登録する。また、テーブル生成制御部１５０は、指標ｉｎｄｅｘｉと受け付けた代表点Ｐ＊ｒｅｐｄｉとを対応付けて第２のテーブル１４２に登録する。
【００４９】
テーブル生成制御部１５０は、受け付けた指標ｉｎｄｅｘｉと代表点Ｐ＊ｒｅｐｉまたはＰ＊ｒｅｐｄｉとをＲＷ関数部１５３へ出力する。テーブル生成制御部１５０は、ＲＷ関数部１５３から指標ｉｎｄｅｘｉ＋１と点Ｐ＊ｉ＋１または点Ｐ＊ｄｉ＋１とを受け付ける。そして、テーブル生成制御部１５０は、ＲＷ関数部１５３から受け付けた点Ｐ＊ｉ＋１または点Ｐ＊ｄｉ＋１を自己同型写像計算部１５１に出力する。テーブル生成制御部１５０は上記の処理を繰り返し行って、第１のテーブル１４１に複数の代表点Ｐ＊ｒｅｐｉおよび第２のテーブル１４２に複数の代表点Ｐ＊ｒｅｐｄｉを追加して登録する。
【００５０】
自己同型写像計算部１５１は、テーブル生成制御部１５０から点Ｐ＊ｉまたは点Ｐ＊ｄｉを受け付ける。なお、点Ｐは、ｉ＝０として、点Ｐ＊０と表される。また、点（ｋｄ×Ｐ）は、ｉ＝０として、点Ｐ＊ｄ０と表される。自己同型写像計算部１５１は、受け付けた点Ｐ＊ｉに対して、下記の式（１）、式（２）に示す自己同型写像を適用する。また、自己同型写像計算部１５１は、受け付けた点Ｐ＊ｄｉに対して、以下の式（３）、（４）に示す自己同型写像を適用する。
【００５１】
【数１】
【００５２】
【数２】
【００５３】
【数３】
【００５４】
【数４】
【００５５】
ただし、ω´はω＝ω´・ｄを満たす。また、ν´はν＝ν´・ｄを満たす。また、ωは、Φ（Ｐ）＝（ｘ３，ｙ３）＝Ω×Ｐ＝ζω×Ｐを満たす。また、νは、−Ｐ＝ζν×Ｐを満たす。
【００５６】
自己同型写像計算部１５１は、例えば、受け付けた点Ｐ＊ｉに対して、式（１）に示す自己同型写像をｍ−１回適用させる。すると、点Ｐ＊ｉを含めるとｍ個の点｛Ｐ＊ｉ（ｓ）｝（ｓ＝０〜ｍ−１）の集合が算出される。そして、自己同型写像計算部１５１は、｛Ｐ＊ｉ（ｓ）｝の各点に対して、式（２）に示す自己同型写像を適用する。これにより、結果として、点Ｐ＊ｉから２ｍ個の点｛Ｐ＊ｉ（ｈ）｝（ｈ＝０〜２ｍ−１）が算出される。
【００５７】
また、自己同型写像計算部１５１は、例えば、受け付けた点Ｐ＊ｄｉに対して、式（３）に示す自己同型写像をｍ−１回適用させる。すると、点Ｐ＊ｄｉを含めるとｍ個の点｛Ｐ＊ｄｉ（ｓ）｝（ｓ＝０〜ｍ−１）の集合が算出される。そして、自己同型写像計算部１５１は、｛Ｐ＊ｄｉ（ｓ）｝の各点に対して、式（４）に示す自己同型写像を適用する。これにより、結果として、点Ｐ＊ｄｉから２ｍ個の点｛Ｐ＊ｄｉ（ｈ）｝（ｈ＝０〜２ｍ−１）が算出される。
【００５８】
自己同型写像計算部１５１は、自己同型写像によって対応させた２ｍ個の点｛Ｐ＊ｉ（ｈ）｝または２ｍ個の点｛Ｐ＊ｄｉ（ｈ）｝を１つの集合として代表点選択部１５２へ出力する。
【００５９】
代表点選択部１５２は、自己同型写像計算部１５１から２ｍ個の点｛Ｐ＊ｉ（ｈ）｝または２ｍ個の点｛Ｐ＊ｄｉ（ｈ）｝を受け付ける。代表点選択部１５２は、受け付けた２ｍ個の点｛Ｐ＊ｉ（ｈ）｝の中から代表点Ｐ＊ｒｅｐｉを一つ選択する。また、代表点選択部１５２は、受け付けた２ｍ個の点｛Ｐ＊ｄｉ（ｈ）｝の中から代表点Ｐ＊ｒｅｐｄｉを一つ選択する。代表点選択部１５２は、選択した代表点Ｐ＊ｒｅｐｉまたはＰ＊ｒｅｐｄｉをテーブル生成制御部１５０へ出力する。なお、代表点選択部１５２は、例えば、２ｍ個の点｛Ｐ＊ｉ（ｈ）｝または｛Ｐ＊ｄｉ（ｈ）｝の中からｘ座標の値が最も小さい点を代表点として選択する。なお、代表点の選択の方法はこれに限られない。
【００６０】
ＲＷ関数部１５３は、テーブル生成制御部１５０から指標ｉｎｄｅｘｉと代表点Ｐ＊ｒｅｐｉまたはＰ＊ｒｅｐｄｉとを受け付ける。ＲＷ関数部１５３は、ＲＷ関数を用いて代表点Ｐ＊ｒｅｐｉから点Ｐ＊ｉ＋１を算出する。また、ＲＷ関数部１５３は、ＲＷ関数を用いて代表点Ｐ＊ｒｅｐｄｉから点Ｐ＊ｄｉ＋１を算出する。なお、ＲＷ関数は、楕円曲線上の点Ｐ＊ｒｅｐｉに対し、下記の式（５）に示すように定義される。同様に、ＲＷ関数は、楕円曲線上の点Ｐ＊ｒｅｐｄｉに対し、下記の式（６）に示すように定義される。ここで、Ｒｎｄ（Ｐ）は、点Ｐから一意的に０以上で（（ｒ−１）／ｄ）以下のランダムな整数を生成する擬似乱数生成関数である。
【００６１】
【数５】
【００６２】
【数６】
【００６３】
ＲＷ関数部１５３は受け付けた指標ｉｎｄｅｘｉを１インクリメントさせて指標ｉｎｄｅｘｉ＋１を算出する。ＲＷ関数部１５３は、指標ｉｎｄｅｘｉ＋１と、算出した点Ｐ＊ｉ＋１または点Ｐ＊ｄｉ＋１とをテーブル生成制御部１５０へ出力する。
【００６４】
ここで、図７の説明に戻る。テーブル比較部１３３は、第１のテーブル１４１に登録された代表点Ｐ＊ｒｅｐｉと第２のテーブル１４２に登録された代表点Ｐ＊ｒｅｐｄｉとを比較して一致する代表点を検出する。テーブル比較部１３３は、一致する代表点の情報をＤＬＰ計算部１３４に出力する。
【００６５】
ＤＬＰ計算部１３４は、一致する代表点の情報に基づいて、秘密鍵ｋを算出する。また、ＤＬＰ計算部１３４は、計算時間Ｔを算出する。なお、計算時間Ｔは、解の計算に要する時間である。例えば、計算時間Ｔは、後述する解の計算処理のステップＳ１０２〜Ｓ１１５までに要した時間である。ＤＬＰ計算部１３４は、算出された秘密鍵ｋおよび計算時間Ｔを出力部１２０に出力する。また、ＤＬＰ計算部１３４は、算出された秘密鍵ｋおよび計算時間Ｔを記憶部１４０に格納する。
【００６６】
制御部１３５は、パラメータ取得部１３１、テーブル生成部１３２、テーブル比較部１３３およびＤＬＰ計算部１３４の各部に対して、上記で説明したような動作を行うように制御する。例えば、制御部１３５は、算出された点Ｐ＊ｉに対して自己同型写像を適用して新たな第１の点である点｛Ｐ＊ｉ（ｈ）｝の集合を算出するようにテーブル生成部１３２を制御する。制御部１３５は、新たな点｛Ｐ＊ｉ（ｈ）｝の集合の中から新たな代表点Ｐ＊ｒｅｐｉを選択して記憶部１４０に追加して記憶させるようにテーブル生成部１３２を制御する。制御部１３５は、新たな代表点Ｐ＊ｒｅｐｉに対して擬似乱数を用いて楕円曲線Ｅ上の新たな点Ｐ＊ｉ＋１を算出するようにテーブル生成部１３２を制御する。制御部１３５は、これらの上記制御を複数回行って、複数の点｛Ｐ＊ｉ（ｈ）｝の集合に関する複数の代表点Ｐ＊ｒｅｐｉを記憶部１４０に記憶させる。ここで、複数回とは、例えば、（ｒ−１）回である。
【００６７】
また、制御部１３５は、テーブル比較部１３３の比較結果に基づいて、第２の点｛Ｐ＊ｄｉ（ｈ）｝の集合に関する代表点Ｐ＊ｒｅｐｄｉに一致する代表点Ｐ＊ｒｅｐｉがない場合には、以下の処理を行う。すなわち、制御部１３５は、今回記憶された代表点Ｐ＊ｒｅｐｄｉに対して擬似乱数を用いて楕円曲線Ｅ上の新たな点Ｐ＊ｄｉ＋１を算出するようにテーブル生成部１３２を制御する。そして、制御部１３５は、算出された新たな点Ｐ＊ｄｉ＋１に対して自己同型写像を適用して新たな第２の点｛Ｐ＊ｄｉ＋１（ｈ）｝の集合を算出するようにテーブル生成部１３２を制御する。そして、制御部１３５は、新たな第２の点｛Ｐ＊ｄｉ＋１（ｈ）｝の集合の中から新たな代表点Ｐ＊ｒｅｐｄｉ＋１を選択して記憶部１４０に追加して記憶させるようにテーブル生成部１３２を制御する。そして、制御部１３５は、これらの上記制御を、代表点が一致するまで繰り返し行う。
【００６８】
［実施例１の処理手順］
次に、処理部１３０による解の計算処理の処理手順について説明する。図９は、処理部１３０による解の計算処理の処理手順を示すフローチャートである。
【００６９】
図９に示すように、処理部１３０は、入力部１１０から解の計算処理を実行する指示が入力されたか否かを判定する（ステップＳ１００）。処理部１３０は、当該指示が入力された場合には（ステップＳ１００，Ｙｅｓ）、タイマーをスタートさせて時間Ｔの計測を開始する（ステップＳ１０１）。
【００７０】
処理部１３０は、システムパラメータを取得する（ステップＳ１０２）。処理部１３０は、取得したシステムパラメータの中から点Ｐ＊ｉ（ｉ＝０）を抽出する（ステップＳ１０３）。
【００７１】
処理部１３０は、点Ｐ＊ｉに対して、上記の式（１）、式（２）に示す自己同型写像を適用して、２ｍ個の点｛Ｐ＊ｉ（ｈ）｝を算出する（ステップＳ１０４）。すなわち、ステップＳ１０４で、Ｐ＊ｉから２ｍ個の点｛Ｐ＊ｉ（ｈ）｝の集合を算出する。処理部１３０は、算出された２ｍ個の点｛Ｐ＊ｉ（ｈ）｝の集合の中から代表点Ｐ＊ｒｅｐｉを一つ選択する（ステップＳ１０５）。
【００７２】
処理部１３０は、選択された代表点Ｐ＊ｒｅｐｉと指標ｉｎｄｅｘｉとを対応付けて、第１のテーブル１４１に登録する（ステップＳ１０６）。これにより、記憶部１４０に、代表点Ｐ＊ｒｅｐｉが記憶される。
【００７３】
処理部１３０は、ＲＷ関数を用いて代表点Ｐ＊ｒｅｐｉから点Ｐ＊ｉ＋１を算出する（ステップＳ１０７）。処理部１３０は、ｉを１インクリメントする（ステップＳ１０８）。処理部１３０は、ｉの値が所定値ｖ以上であるか否かを判定する（ステップＳ１０９）。処理部１３０は、ｉの値が所定値ｖ未満である場合には（ステップＳ１０９，Ｎｏ）、上記ステップＳ１０４へ戻り、上記で説明した処理を行う。このように、ステップＳ１０４〜１０９の処理を繰り返すことにより、テーブル１４１にはｖ個の代表点Ｐ＊ｒｅｐｉ（ｉ＝０〜ｖ−１）が登録される。すなわち、記憶部１４０には、ｖ個の代表点Ｐ＊ｒｅｐｉが記憶される。なお、所定値ｖの値を、例えば、ｒ−１としてもよい。所定値ｖの値をｒ−１とした場合には、記憶部１４０には、ｒ−１個の代表点Ｐ＊ｒｅｐｉが記憶される。
【００７４】
図１０は、解の計算処理を説明するための図である。図１０に示すように、点（｛Ｐ＊ｉ（ｈ）｝）５２の集合５０の中から代表点（Ｐ＊ｒｅｐｉ）５１が、解を得るための情報として選択され、テーブル１４１に登録される。そして、代表点５１から、ＲＷ関数により当該代表点５１が属する集合とは異なる集合５０の点（｛Ｐ＊ｉ＋１（ｈ）｝）５２が算出される。これらの処理がステップＳ１００〜１０９で繰り返されることで、複数の代表点５１がテーブル１４１に登録される。
【００７５】
一方、ｉの値が所定値ｖ以上である場合には（ステップＳ１０９，Ｙｅｓ）、処理部１３０は、取得したシステムパラメータの中から点Ｐ＊ｄｉ（ｉ＝０）を抽出する（ステップＳ１１０）。
【００７６】
処理部１３０は、点Ｐ＊ｄｉに対して、上記の式（３）、式（４）に示す自己同型写像を適用して、２ｍ個の点｛Ｐ＊ｄｉ（ｈ）｝を算出する（ステップＳ１１１）。すなわち、ステップＳ１１１で、Ｐ＊ｄｉから２ｍ個の点｛Ｐ＊ｄｉ（ｈ）｝の集合を算出する。
【００７７】
処理部１３０は、算出された２ｍ個の点｛Ｐ＊ｄｉ（ｈ）｝の集合の中から代表点Ｐ＊ｒｅｐｄｉを一つ選択する（ステップＳ１１２）。処理部１３０は、選択された代表点Ｐ＊ｒｅｐｄｉと指標ｉｎｄｅｘｄｉとを対応付けて、第２のテーブル１４２に登録する（ステップＳ１１３）。これにより、記憶部１４０に、代表点Ｐ＊ｒｅｐｄｉが記憶される。
【００７８】
処理部１３０は、第１のテーブル１４１に登録された複数の代表点Ｐ＊ｒｅｐｉの各々と、第２のテーブル１４２に今回登録された代表点Ｐ＊ｒｅｐｄｉとを比較し、代表点Ｐ＊ｒｅｐｄｉに一致する代表点Ｐ＊ｒｅｐｉがあるか否かを判定する（ステップＳ１１４）。
【００７９】
代表点Ｐ＊ｒｅｐｄｉに一致する代表点Ｐ＊ｒｅｐｉがある場合には（ステップＳ１１４，Ｙｅｓ）、処理部１３０は、一致する代表点の情報に基づいて、秘密鍵ｋを算出する（ステップＳ１１５）。処理部１３０は、タイマーをストップする（ステップＳ１１６）。これにより、解の計算に要する時間である計算時間Ｔが算出される。処理部１３０は、算出された秘密鍵ｋおよび計算時間Ｔを出力部１２０に出力する（ステップＳ１１７）。このとき、処理部１３０は、秘密鍵ｋおよび計算時間Ｔを記憶部１４０に格納する（同ステップＳ１１７）。
【００８０】
一方、代表点Ｐ＊ｒｅｐｄｉに一致する代表点Ｐ＊ｒｅｐｉがない場合には（ステップＳ１１４，Ｎｏ）、処理部１３０は、ＲＷ関数を用いて代表点Ｐ＊ｒｅｐｄｉから点Ｐ＊ｄｉ＋１を算出する（ステップＳ１１８）。処理部１３０は、ｉを１インクリメントし（ステップＳ１１９）、上記ステップＳ１１１へ戻り、上記で説明した処理を行う。ステップＳ１１０〜１１４、１１８、１１９の処理では、点（｛Ｐ＊ｄｉ（ｈ）｝）の集合の中から代表点（Ｐ＊ｒｅｐｄｉ）が、解を得るための情報として選択され、テーブル１４２に登録される。そして、代表点（Ｐ＊ｒｅｐｄｉ）から、ＲＷ関数により当該代表点（Ｐ＊ｒｅｐｄｉ）が属する集合とは異なる集合５０の点（｛Ｐ＊ｉ＋１（ｈ）｝）が算出される。これらの処理がステップＳ１１０〜１１４、１１８、１１９で繰り返されることで、複数の代表点（Ｐ＊ｒｅｐｄｉ）がテーブル１４２に登録される。
【００８１】
［実施例１の効果等］
以上、本実施例１に係る暗号鍵解読装置１００について説明した。本実施例１によれば、Ｃｈｅｏｎ解析法にＲＷ関数を適用し、上述した自己同型写像を適用して数学的問題を解いている。例えば、本実施例１によれば、楕円曲線Ｅ上の所定の点であるＰに対して自己同型写像を適用して点｛Ｐ＊０（ｈ）｝の集合が算出される。また、この集合の中から代表点Ｐ＊ｒｅｐ０を選択して記憶部１４０に記憶させる。また、代表点Ｐ＊ｒｅｐ０に対して擬似乱数を用いて楕円曲線Ｅ上の点Ｐ＊１を算出する。また、本実施例１によれば、点Ｐ＊１に対して自己同型写像を適用することで、新たな代表点Ｐ＊ｒｅｐｉを記憶部１４０に記憶させる。
【００８２】
また、本実施例１によれば、楕円曲線Ｅ上において所定の暗号鍵ｋから定まる点である（ｋｄ×Ｐ）に対して自己同型写像を適用して点｛Ｐ＊ｄ０（ｈ）｝の集合を算出する。また、この集合の中から代表点Ｐ＊ｒｅｐｄ０を選択して記憶部１４０に記憶させる。また、代表点Ｐ＊ｒｅｐｄ０に対して擬似乱数を用いて楕円曲線Ｅ上の点Ｐ＊ｄ１を算出する。また、点Ｐ＊ｄ１に対して自己同型写像を適用することで、新たな代表点Ｐ＊ｒｅｐｄｉを記憶部１４０に記憶させる。また、記憶部１４０に記憶された代表点Ｐ＊ｒｅｐｉと代表点Ｐ＊ｒｅｐｄｉとを比較し、一致した代表点に基づいて暗号鍵ｋを算出する。
【００８３】
従って、本実施例１によれば、記憶容量が圧迫されずに、暗号鍵ｋを解くことができる。例えば、本実施例１によれば、計算に必要な記憶容量が（（ｒ−１）／２ｍ）１／４となる。従来のＣｈｅｏｎ解析法では計算に必要な記憶容量が（ｒ−１）１／４であった。このように暗号鍵解読装置１００によれば、従来のＣｈｅｏｎ解析法と比較すると、計算に必要な記憶容量が１／（２ｍ）１／４倍削減される。
【実施例２】
【００８４】
［実施例２の装置構成］
次に、実施例２に係る暗号鍵解読装置について説明する。図１１はループの発生を示す図である。上記で説明した実施例１に係る暗号鍵解読装置１００では、図１１に示すように、代表点５１が、既に選択された代表点５１を含む集合５０内に、再び、ＲＷ関数によって算出されてしまうことがある。これは、ＲＷ関数で生成される擬似乱数の最大値が（（ｒ−１）／ｄ）となるからである。このような場合、既に選択された代表点５１を選択し続けることになる。そのため、点５２および代表点５１が算出されない集合５０´が存在してしまう。よって、暗号鍵解読の観点から更なる改良が望まれる。そこで、実施例２に係る暗号鍵解読装置では、既に選択された代表点を含む集合とは異なる集合に属する点５２を算出することができるようにした。なお、既に選択された代表点５１を選択し続ける現象を「ループ」と称する。
【００８５】
なお、実施例１と同様の構成および処理については同一の符号を付し、説明を省略する。図１２は、本実施例２に係る暗号鍵解読装置の構成を示す図である。図１２に示すように、暗号鍵解読装置２００は、入力部１１０、出力部１２０、処理部２３０、および記憶部１４０を有する。本実施例２に係る暗号鍵解読装置２００では、実施例１の処理部１３０に代えて処理部２３０を有する。なお、入力部１１０、出力部１２０、および記憶部１４０は実施例１と同様の構成であるので、以下では説明は省略する。
【００８６】
処理部２３０は、パラメータ取得部１３１、テーブル生成部２３２およびテーブル比較部１３３を有する。また、処理部２３０は、ＤＬＰ（Ｄｉｓｃｒｅｔｅ Ｌｏｇａｒｉｔｈｍ Ｐｒｏｂｌｅｍ）計算部１３４および制御部１３５を有する。
【００８７】
テーブル生成部２３２は、入力されたシステムパラメータに基づいて、楕円曲線Ｅ上の点Ｐに対して自己同型写像を適用して点の集合を算出する。テーブル生成部２３２は、点Ｐを開始点として算出された第１の点の集合の中から第１の代表点を選択して記憶部１４０に記憶させる。テーブル生成部２３２は、第１の代表点に対して擬似乱数を用いて楕円曲線Ｅ上の点を算出する。テーブル生成部２３２は、制御部１３５の制御によってこれらの処理を繰り返し行うことで、記憶部１４０に追加して第１の代表点を記憶して、複数の第１の代表点を記憶部１４０に記憶する。
【００８８】
また、テーブル生成部２３２は、楕円曲線Ｅ上において点（ｋｄ×Ｐ）に対して自己同型写像を適用して点の集合を算出する。テーブル生成部２３２は、点（ｋｄ×Ｐ）を開始点として算出された第２の点の集合の中から第２の代表点を選択して記憶部１４０に記憶させる。テーブル生成部２３２は、第２の代表点に対して擬似乱数を用いて楕円曲線Ｅ上の点を算出する。テーブル生成部２３２は、テーブル比較部１３３で第１の代表点に一致する第２の代表点が検出されるまで、制御部１３５の制御によって、これらの処理を繰り返し行う。これにより、テーブル生成部２３２は、記憶部１４０に追加して第２の代表点を記憶して、複数の第２の代表点を記憶部１４０に記憶する。
【００８９】
ここで、テーブル生成部２３２の詳細に説明する。図１３はテーブル生成部２３２のブロック図である。テーブル生成部２３２は、テーブル生成制御部１５０、自己同型写像計算部１５１、代表点選択部１５２およびＲＷ関数部２５３を有する。
【００９０】
テーブル生成制御部１５０、自己同型写像計算部１５１、および代表点選択部１５２については実施例１と同様の構成であるので説明を省略する。
【００９１】
ＲＷ関数部２５３は、テーブル生成制御部１５０から指標ｉｎｄｅｘｉと代表点Ｐ＊ｒｅｐｉまたはＰ＊ｒｅｐｄｉとを受け付ける。ＲＷ関数部２５３は、ＲＷ関数を用いて代表点Ｐ＊ｒｅｐｉから点Ｐ＊ｉ＋１を算出する。ＲＷ関数部２５３は、ＲＷ関数を用いて代表点Ｐ＊ｒｅｐｄｉから点Ｐ＊ｄｉ＋１を算出する。なお、ＲＷ関数は、楕円曲線上の点Ｐ＊ｒｅｐｉに対し、以下の式（７）に示すように定義される。同様に、ＲＷ関数は、楕円曲線上の点Ｐ＊ｒｅｐｄｉに対し、以下の式（８）に示すように定義される。ここで、この場合のＲｎｄ（Ｐ）は、点Ｐから一意的に０以上で（（ｒ−１）／２ｍｄ）以下のランダムな整数を生成する擬似乱数生成関数である。
【００９２】
【数７】
【００９３】
【数８】
【００９４】
ここで、自己同型写像計算部１５１で適用される自己同型写像について説明する。上記式（１）、式（２）の自己同型写像は、下記の式（９）のように表される。
【００９５】
【数９】
【００９６】
ただし、ωはω＝（ｃ・（ｒ−１）／ｍ）を満たす。ただし、ｃはζによって一意に定まる定数である。また、νはν＝（ｒ−１）／２を満たす。また、ζは、Φ（Ｐ）＝（ｘ３，ｙ３）＝Ω×Ｇ＝ζω×Ｇを満たし、−Ｐ＝ζν×Ｇを満たす。このように、ω、νは点の位数ｒと拡大次数ｍ（ＧＦ（ｑｍ））で表現される。
【００９７】
以上のように、擬似乱数Ｒｎｄ（）の値の範囲が、実施例１では、０≦ｄ・Ｒｎｄ（）≦（（ｒ−１））であったのが、実施例２では、０≦ｄ・Ｒｎｄ（）≦（（ｒ−１）／２ｍ）となる。これにより、実施例２では、擬似乱数の最大値が、実施例１と比較して１／２ｍ倍に削減される。また、式（７）、式（８）のζの指数部に注目すると、この指数部は、（μ×（ｒ−１）／２ｍ）＋（ｄ×Ｒｎｄ（））と記述される。これは、（（ｒ−１）／２ｍ）の倍数は自己同型写像で探索し、（（ｒ−１）／２ｍ）の倍数でないものをＲＷ関数で探索することを意味している。
【００９８】
よって、ＲＷ関数によって算出される点Ｐ＊ｉ＋１または点Ｐ＊ｉ＋１は、既に選択した点Ｐ＊ｒｅｐｉまたは点Ｐ＊ｒｅｐｄｉを含む集合の点とは異なる集合の点となる。これにより、ループが防止される。より詳細に説明する。実施例１では、ランダム関数で生成される擬似乱数Ｒｎｄ（）の値の範囲が上記の０≦ｄ・Ｒｎｄ（）≦（（ｒ−１））である。このため、ランダム関数によって既に生成されたある点の集合内で別の点がランダム関数によって生成される場合がある。この場合には、この集合内の点では既に選択された代表点と同一の代表点が選択されてしまう。その結果、ループが発生する。
【００９９】
一方、実施例２では、ランダム関数で生成される擬似乱数Ｒｎｄ（）の値の範囲を上記の０≦ｄ・Ｒｎｄ（）≦（（ｒ−１）／２ｍ）とした結果、ランダム関数によって既に生成されたある点の集合とは異なる集合の点がランダム関数によって算出される。
【０１００】
また、ＲＷ関数部２５３は受け付けた指標ｉｎｄｅｘｉを１インクリメントさせて指標ｉｎｄｅｘｉ＋１を算出する。ＲＷ関数部２５３は、指標ｉｎｄｅｘｉ＋１と、算出した点Ｐ＊ｉ＋１または点Ｐ＊ｄｉ＋１とをテーブル生成制御部１５０へ出力する。
【０１０１】
制御部１３５は、パラメータ取得部１３１、テーブル生成部２３２、テーブル比較部１３３およびＤＬＰ計算部１３４の各部に対して、上記で説明したような動作を行うように制御する。例えば、制御部１３５は、算出された点Ｐ＊ｉに対して自己同型写像を適用して新たな第１の点である点｛Ｐ＊ｉ（ｈ）｝の集合を算出するようにテーブル生成部２３２を制御する。制御部１３５は、新たな点｛Ｐ＊ｉ（ｈ）｝の集合の中から新たな代表点Ｐ＊ｒｅｐｉを選択して記憶部１４０に追加して記憶させるようにテーブル生成部２３２を制御する。制御部１３５は、新たな代表点Ｐ＊ｒｅｐｉに対して擬似乱数を用いて楕円曲線Ｅ上の新たな点Ｐ＊ｉ＋１を算出するようにテーブル生成部２３２を制御する。制御部１３５は、これらの上記制御を複数回行って、複数の点｛Ｐ＊ｉ（ｈ）｝の集合に関する複数の代表点Ｐ＊ｒｅｐｉを記憶部１４０に記憶させる。
【０１０２】
また、制御部１３５は、テーブル比較部１３３の比較結果に基づいて、第２の点｛Ｐ＊ｄｉ（ｈ）｝の集合に関する代表点Ｐ＊ｒｅｐｄｉに一致する代表点Ｐ＊ｒｅｐｉがない場合には、以下の処理を行う。すなわち、制御部１３５は、今回記憶された代表点Ｐ＊ｒｅｐｄｉに対して擬似乱数を用いて楕円曲線Ｅ上の新たな点Ｐ＊ｄｉ＋１を算出するようにテーブル生成部２３２を制御する。そして、制御部１３５は、算出された新たな点Ｐ＊ｄｉ＋１に対して自己同型写像を適用して新たな第２の点｛Ｐ＊ｄｉ＋１（ｈ）｝の集合を算出するようにテーブル生成部２３２を制御する。そして、制御部１３５は、新たな第２の点｛Ｐ＊ｄｉ＋１（ｈ）｝の集合の中から新たな代表点Ｐ＊ｒｅｐｄｉ＋１を選択して記憶部１４０に追加して記憶させるようにテーブル生成部２３２を制御する。そして、制御部１３５は、これらの上記制御を、代表点が一致するまで繰り返し行う。
【０１０３】
次に、処理部２３０による解の計算処理の処理手順について説明する。図１４は、処理部２３０の解の計算処理の処理手順を示すフローチャートである。
【０１０４】
なお、本実施例２における解の計算処理では、実施例１のステップＳ１０７に代えてステップＳ２０７が実行される。また、実施例１のステップＳ１１８に代えてステップＳ２１８が実行される。そのため、これらのステップＳ２０７、２１８について説明を行い、その他の実施例１と同様のステップについては説明を省略する。
【０１０５】
ステップＳ２０７について説明する。処理部２３０は、ＲＷ関数を用いて、擬似乱数を生成し、代表点Ｐ＊ｒｅｐｉから点Ｐ＊ｉ＋１を算出する（ステップＳ２０７）。ここで、この擬似乱数は、上述したように以下の式（１０）に示す範囲内で生成される。
【０１０６】
【数１０】
【０１０７】
ただし、Ｗは当該擬似乱数の値であり、ｍは楕円曲線暗号が定義された有限体における拡大次数であり、ｄは（ｒ−１）の約数である。
【０１０８】
上記式（１０）が示す範囲内で擬似乱数を生成することで、ステップＳ２０７において、ステップＳ１０５で既に選択された代表点Ｐ＊ｒｅｐｉを含む集合とは異なる集合に属する点Ｐ＊ｉ＋１が算出される。
【０１０９】
さらに、ステップＳ２１８について説明する。処理部２３０は、ＲＷ関数を用いて、擬似乱数を生成し、代表点Ｐ＊ｒｅｐｄｉから点Ｐ＊ｄｉ＋１を算出する（ステップＳ２１８）。この擬似乱数は、上述したように上記式（１０）に示す範囲内で生成される。上記式（１０）が示す範囲内で擬似乱数を生成することで、ステップＳ２１８において、ステップＳ１１２で既に選択された代表点Ｐ＊ｒｅｐｄｉを含む集合とは異なる集合に属する点Ｐ＊ｄｉ＋１が算出される。
【０１１０】
［実施例２の効果等］
以上、本実施例２に係る暗号鍵解読装置２００について説明した。実施例２によれば、Ｃｈｅｏｎ解析法と比較して、計算時に記憶されるデータ量が少なくなるため、記憶容量が圧迫されずに、暗号鍵を解くことができる。また、実施例２によれば、ループを防止できる。また、実施例２によれば、ループを防止できるので、実施例１よりも、暗号鍵の解読に必要な計算量が少なくなる。
【０１１１】
図１５は本実施例２の暗号鍵解読装置２００の効果を説明するための図である。既に説明したが、図１５に示すように、実施例１では計算に必要な記憶容量が（（ｒ−１）／２ｍ）１／４となる。そのため、従来の技術であるＣｈｅｏｎ解析法と比較すると、実施例１では、計算に必要な記憶容量が１／（２ｍ）１／４倍削減される。
【０１１２】
しかしながら、図１５に示すように、実施例１ではループになる確率が高くなる。Ｃｈｅｏｎ解析法でループになる確率を１とすると、実施例１ではループになる確率が２ｍとなる。また、実施例１では、計算量が増加し、２ｍ×２×（（ｒ−１）／２ｍ）１／４となる。なお、図１５の各項目の下段は、有限体ＧＦ（３１２７）の場合を示す。例えば、有限体ＧＦ（３１２７）においては、実施例１のループになる確率は、従来技術の２５４倍となる。また、計算量は従来技術では２２０．５となるが、実施例１では２２１．５となる。また、計算時に記憶されるデータ量は、従来技術では２２０．５だが、実施例１では２１６．５となる。
【０１１３】
本実施例２では、ＲＷ関数において、生成される擬似乱数の値の範囲の最大値を（ｒ−１）／２ｍｄにして、既に選択された代表点を含む集合とは異なる集合に属する点を算出するようにした。このため、図１５に示すように、実施例１では、ループになる確率は１となった。また、実施例１では、計算量は２×（（ｒ−１）／２ｍ）１／４となった。よって、実施例１と比較すると、本実施例２では、計算量およびループになる確率が減少する。例えば、有限体ＧＦ（３１２７）においては、本実施例２では、計算量が２１７．５となる。
【０１１４】
ところで、上記の各実施例１，２では、代表点Ｐ＊ｒｅｐｄｉが選択されるごとに、テーブル１４１に登録された複数の代表点Ｐ＊ｒｅｐｉの各々と、１つの代表点Ｐ＊ｒｅｐｄｉとを比較して一致する代表点を検出する例について説明した。しかしながら、実施例はこれに限られない。例えば、複数の代表点Ｐ＊ｒｅｐｄｉを求めてテーブル１４２に登録しておき、テーブル１４１に登録された複数の代表点Ｐ＊ｒｅｐｉの各々と、テーブル１４１に登録された複数の代表点Ｐ＊ｒｅｐｄｉの各々とを比較するようにしてもよい。
【０１１５】
また、上記の各実施例１，２では、点Ｐと点（ｋｄ×Ｐ）とを開始点として、比較対象となる代表点Ｐ＊ｒｅｐｉおよび代表点Ｐ＊ｒｅｐｄｉを求める例について説明した。しかしながら、実施例はこれに限られない。例えば、点Ｐおよび点（ｋｄ×Ｐ）に加えて、点Ｐおよび点（ｋｄ×Ｐ）とは異なる楕円曲線Ｅ上の点、例えば、点（ｋｇ×Ｐ）（g∈Ｎ、２≦ｇ≦（ｄ−１））を開始点として、同様の処理によって代表点Ｇ＊ｒｅｐｉを求めてもよい。この場合、代表点Ｇ＊ｒｅｐｉを登録するためのテーブルが新たに設けられる。そして、代表点Ｐ＊ｒｅｐｉと代表点Ｐ＊ｒｅｐｄｉとを比較することに加えて、代表点Ｇ＊ｒｅｐｉと代表点Ｐ＊ｒｅｐｄｉとを比較し、代表点Ｇ＊ｒｅｐｉと代表点Ｐ＊ｒｅｐｄｉとを比較する。そして、一致する代表点を検出する。
【０１１６】
また、点Ｐおよび点（ｋｄ×Ｐ）に加えて、楕円曲線Ｅ上の複数の点（ｋｇ×Ｐ）を開始点として、各開始点に対応する代表点を求めるようにしてもよい。この場合、各開始点に対応する代表点ごとに、当該代表点を登録するためのテーブルが設けられる。この場合、各代表点を比較して、一致する代表点を検出する。
【０１１７】
また、複数台のコンピュータの各々で、代表点をテーブルに登録する処理を並行に行うことで、処理の高速化を図ってもよい。
【０１１８】
［暗号鍵解読プログラム］
また、上記の各実施例で説明した暗号鍵解読装置１００、２００の各種の処理は、あらかじめ用意されたプログラムをパーソナルコンピュータやワークステーションなどのコンピュータシステムで実行することによって実現することもできる。そこで、以下では、図１６を用いて、上記の実施例で説明した暗号鍵解読装置１００、２００と同様の機能を有する暗号鍵解読プログラムを実行するコンピュータの一例を説明する。図１６は、暗号鍵解読プログラムを実行するコンピュータを示す図である。
【０１１９】
同図に示すように、暗号鍵解読装置１００、２００としてコンピュータ３００は、入出力制御部３１０、ＨＤＤ（Ｈａｒｄ Ｄｉｓｋ Ｄｒｉｖｅ）３２０、ＲＡＭ（Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ）３３０およびＣＰＵ（Ｃｅｎｔｒａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）３４０をバス４００で接続して構成される。
【０１２０】
ここで、入出力制御部３１０は、各種情報の入出力を制御する。ＨＤＤ３２０は、ＣＰＵ３４０による各種処理の実行に必要な情報を記憶する。ＲＡＭ３３０は、各種情報を一時的に記憶する。ＣＰＵ３４０は、各種演算処理を実行する。
【０１２１】
そして、ＨＤＤ３２０には、暗号鍵解読システムデータがあらかじめ記憶されている。係る暗号鍵解読システムデータは、図７や図１２に示した暗号鍵解読装置１００、２００の各処理部と同様の機能を発揮する暗号鍵解読プログラムを含む。また、暗号鍵解読システムデータは、処理に必要な各種パラメータを含む暗号鍵解読用データを含む。なお、この暗号鍵解読システムデータを適宜分散させて、ネットワークを介して通信可能に接続された他のコンピュータの記憶部に記憶させておくこともできる。
【０１２２】
そして、ＣＰＵ３４０が、この暗号鍵解読システムデータをＨＤＤ３２０から読み出してＲＡＭ３３０に展開することにより、暗号鍵解読システムデータは暗号鍵解読システムとして機能するようになる。係る暗号鍵解読システムには暗号鍵解読プロセスが含まれる。
【０１２３】
すなわち、暗号鍵解読システムやそれに搭載された暗号鍵解読プロセスは、暗号鍵解読用データをＨＤＤ３２０から読み出して、ＲＡＭ３３０において自身に割り当てられた領域に展開し、この展開したデータ等に基づいて各種処理を実行する。
【０１２４】
なお、暗号鍵解読システム及び暗号鍵解読プロセスは、図７や図１２に示した各機能部（例えば、パラメータ取得部１３１、テーブル生成部１３２，２３２、テーブル比較部１３３、ＤＬＰ計算部１３４）において実行される処理に対応する。
【０１２５】
なお、上記した暗号鍵解読プログラムについては、必ずしも最初からＨＤＤ３２０に記憶させておく必要はない。
【０１２６】
例えば、コンピュータ３００に挿入されるフレキシブルディスク（ＦＤ）、ＣＤ−ＲＯＭ、ＤＶＤディスク、光磁気ディスク、ＩＣカードなどの「可搬用の物理媒体」に各プログラムを記憶させておく。そして、コンピュータ３００がこれらから各プログラムを読み出して実行するようにしてもよい。
【０１２７】
さらには、公衆回線、インターネット、ＬＡＮ、ＷＡＮなどを介してコンピュータ３００に接続される「他のコンピュータ（またはサーバ）」などに各プログラムを記憶させておく。そして、コンピュータ３００がこれらから各プログラムを読み出して実行するようにしてもよい。
【０１２８】
また、本実施例において説明した各処理のうち、自動的に行われるものとして説明した処理の全部または一部を手動的に行うこともできる。また、本実施例において説明した各処理のうち、手動的に行われるものとして説明した処理の全部または一部を公知の方法で自動的に行うこともできる。例えば、図９、図１４の解の計算処理において、当該処理を実行する指示が手動で入力された場合に、ステップＳ１０１以降の処理が開始されたが、自動的にステップＳ１０１以降の処理を開始してもよい。
【０１２９】
また、図示した各装置の各構成要素は機能概念的なものであり、必ずしも物理的に図示の如く構成されていることを要しない。すなわち、各装置の分散・統合の具体的状態は図示のものに限られず、その全部または一部を、各種の負荷や使用状況などに応じて、任意の単位で機能的または物理的に分散・統合して構成することができる。例えば、図７に示すテーブル生成部１３２とテーブル比較部１３３とが統合されてもよい。また、テーブル比較部１３３とＤＬＰ計算部１３４とが統合されてもよい。また、図１２に示すテーブル生成部２３２とテーブル比較部１３３とが統合されてもよい。
【０１３０】
また、テーブル生成部１３２は、以下の機能を有している。すなわち、テーブル生成部１３２は、入力されたシステムパラメータに基づいて、楕円曲線Ｅ上の点Ｐに対して自己同型写像を適用して点の集合を算出する機能を有している。また、テーブル生成部１３２は、算出された集合の中から第１の代表点を選択して記憶部１４０に記憶させる機能を有している。さらに、テーブル生成部１３２は、第１の代表点に対して擬似乱数を用いて楕円曲線Ｅ上の点を算出する機能を有している。これらの各機能を分散して構成するようにしてもよい。
【０１３１】
また、テーブル生成部１３２は、楕円曲線Ｅ上において点（ｋｄ×Ｐ）に対して自己同型写像を適用して点の集合を算出する機能を有している。テーブル生成部１３２は、算出された集合の中から第２の代表点を選択して記憶部１４０に記憶させる機能を有している。テーブル生成部１３２は、第２の代表点に対して擬似乱数を用いて楕円曲線Ｅ上の点を算出する機能を有している。これらの各機能についても、分散して構成するようにしてもよい。同様に、テーブル生成部２３２についても各機能を分散して構成するようにしてもよい。
【符号の説明】
【０１３２】
１００、２００ 暗号鍵解読装置
１１０ 入力部
１２０ 出力部
１３０、２３０ 処理部
１４０ 記憶部
１３１ パラメータ取得部
１３２、２３２ テーブル生成部
１３３ テーブル比較部
１３４ ＤＬＰ計算部
１３５ 制御部
【技術分野】
【０００１】
本発明は、暗号鍵解析方法、暗号鍵解析装置および暗号鍵解析プログラムに関する。
【背景技術】
【０００２】
近年、ネットショッピングやネットバンキングなどが普及している。ネットショッピングやネットバンキングにおいて通信を行う場合には、ＳＳＬ(Secure Sockets Layer)／ＴＬＳ(Transport Layer Security)などの暗号技術が用いられる。暗号技術の代表である暗号化方式は、大別すると共通鍵暗号と公開鍵暗号との２つに分類される。
【０００３】
共通鍵暗号は、送信者と受信者とが同じ鍵を持つことにより暗号通信を行う方式である。すなわち、共通鍵暗号では、送信者は、あるメッセージを秘密の暗号鍵に基づいて暗号化して受信者に送る。受信者は、この暗号鍵を用いて暗号文を復号し、メッセージを入手する。
【０００４】
公開鍵暗号では、送信者は、受信者の公開されている鍵（公開鍵）でメッセージを暗号化して送信する。受信者は暗号化されたメッセージを自分だけが保持している鍵（秘密鍵）で復号する。すなわち、公開鍵暗号では、公開鍵は情報を暗号化するための鍵である。また、秘密鍵は、公開鍵により暗号化された情報を復号するための鍵である。公開鍵で暗号化された情報は、秘密鍵でのみ復号することができる。
【０００５】
公開鍵暗号は、公開鍵を公開しても安全性を確保できるようにするために、数学的に難しいとされている問題に基づいて設計されている。例えば、ＲＳＡ(Rivest Shamir Adleman)暗号は、素因数分解問題と呼ばれる数学的問題の困難性に基づいている。また、エルガマル暗号は、離散対数問題と呼ばれる数学的問題の困難性に基づいている。さらに、楕円曲線暗号（Elliptic Curve Cryptosystem）は、楕円曲線上の離散対数問題を基に設計されている。なお、楕円曲線上の離散対数問題を「楕円曲線離散対数問題」と称する。このように、公開鍵暗号の安全性は、数学的問題の困難性に基づいている。そのため、これらの数学的問題の解読計算量が、公開鍵暗号の安全性の指標となる。
【０００６】
楕円曲線暗号は、楕円曲線離散対数問題に基づく暗号である。楕円曲線離散対数問題に基づく暗号は、楕円曲線上の点Ｐおよび単位元となる無限遠点Οの集合のなす加法群において定義される。この加法群に含まれる点の数を位数ｒと呼ぶ。 楕円曲線上の点Ｐ１とＰ２に対する演算として、以下が容易に計算できることが知られている。
加算：Ｐ３＝Ｐ１＋Ｐ２＝Ｐ２＋Ｐ１
２倍算：Ｐ２＝２×Ｐ１＝Ｐ１＋Ｐ１
減算：Ｐ３＝Ｐ１−Ｐ２
零点：Ο（無限遠点）＝Ｐ１−Ｐ１
スカラ倍算：ｋ×Ｐ＝Ｐ＋Ｐ＋・・・＋Ｐ（ｋ個のＰの和）
【０００７】
ここで、ｋ×ＰとＰとからｋを算出する問題を楕円曲線離散対数問題という。位数ｒが巨大な場合、解を求めることは困難であることが知られている。楕円曲線離散対数問題が困難であるという仮定のもとで、楕円曲線のパラメータを用いた楕円曲線暗号の安全性が保証される。なお、ｋは秘密鍵として使用されることが多い。
【０００８】
さらに近年では、ペアリングという公開鍵暗号技術が注目されている。ペアリングは楕円曲線暗号の一種である。楕円曲線上の２点に対するペアリングと呼ばれる演算を用いることで、従来の楕円曲線暗号の機能を拡張する。この場合、楕円曲線離散対数問題の困難性に加え、いくつかの数学的問題の困難性に関する新たな仮定が必要となる。例えばペアリングを使った放送暗号では、Ｌ−双線形性Ｄｉｆｆｉｅ‐Ｈｅｌｌｍａｎ指数問題（Ｌ−ＢＤＨＥ問題）と呼ばれる数学的問題の困難性を仮定することがある。ここでＬ−ＢＤＨＥ問題とは、Ｐ、ｋ×Ｐ、ｋ2×Ｐ、ｋ3×Ｐ、・・・、ｋL×ＰからｋやｋL+1を求める問題である。この場合、Ｐ、ｋ×Ｐからｋを求める楕円曲線離散対数問題に比べ、ｋ2×Ｐ、ｋ3×Ｐ、…、ｋL×Ｐなどの補助情報があることから、この問題を補助入力付き楕円曲線離散対数問題と呼ぶことがある。
【０００９】
また、数学的問題として、例えば、Ｐ、ｋ×Ｐ、ｋｄ×Ｐ及びｄから、ｋを求める補助入力付き楕円曲線離散対数問題がある。ここで、ｄは（ｒ−１）の約数である。この問題を解く方法として、例えば、Ｃｈｅｏｎ解析法が知られている。Ｃｈｅｏｎ解析法は、Ｂａｂｙ−Ｓｔｅｐ Ｇｉａｎｔ−Ｓｔｅｐ解析法（ＢＳＧＳ）を用いて攻撃を行う方法である。Ｃｈｅｏｎ解析法では、ＢＳＧＳを二重に処理することで攻撃を行う。ＢＳＧＳでは２種類のテーブルを作成し、各テーブルに記憶された計算結果を比較して、秘密鍵ｋを求める。これにより、最小ｒ１／４の数倍程度の計算量で暗号鍵としての秘密鍵ｋを解くことができる。
【先行技術文献】
【非特許文献】
【００１０】
【非特許文献１】D.Hankerson,A.Menezes and S.Vanstone“Guide to Elliptic Curve Cryptography”p.161‐163
【発明の概要】
【発明が解決しようとする課題】
【００１１】
しかしながら、上記のＣｈｅｏｎ解析法では、記憶される上記計算結果の量が、ｒ１／４程度と大きいため、記憶容量が圧迫されるという問題があった。
【００１２】
開示の技術は、上記に鑑みてなされたものであって、記憶容量が圧迫されずに、暗号鍵を解くことができる暗号鍵解析方法、暗号鍵解析装置、および暗号鍵解析プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１３】
本願の開示する暗号鍵解析方法は、一つの態様において、コンピュータが、第１の代表点選択ステップと、第２の代表点選択ステップと、暗号鍵算出ステップとを実行することを特徴とする。第１の代表点選択ステップは、楕円曲線上の所定の点に対して自己同型写像を適用して第１の点の集合を算出する。第１の代表点選択ステップは、第１の点の集合の中から代表点を選択して記憶部に記憶させる。第１の代表点選択ステップは、記憶部に記憶された第１の点の集合に関する代表点に対して擬似乱数を用いて楕円曲線上の点を算出する。第１の代表点選択ステップは、点に対して自己同型写像を適用することで、第１の点の集合に関する新たな代表点を選択して記憶部に追加して記憶させる。第２の代表点選択ステップは、楕円曲線上において所定の暗号鍵から定まる点に対して自己同型写像を適用して第２の点の集合を算出する。第２の代表点選択ステップは、第２の点の集合の中から代表点を選択して記憶部に記憶させる。第２の代表点選択ステップは、第２の集合の点に関する代表点に対して擬似乱数を用いて楕円曲線上の点を算出する。第２の代表点選択ステップは、点に対して自己同型写像を適用することで、第２の点の集合の新たな代表点を記憶部に追加して記憶させる。暗号鍵算出ステップは、記憶部に記憶された第１の点の集合に関する代表点と第２の点の集合に関する代表点とを比較し、一致した代表点に基づいて暗号鍵を算出する。
【発明の効果】
【００１４】
本願の開示する暗号鍵解析方法の一つの態様によれば、記憶容量が圧迫されずに、暗号鍵を解くことができるという効果を奏する。
【図面の簡単な説明】
【００１５】
【図１】図１は、ＢＳＧＳの具体例を説明するための図である。
【図２】図２は、Ｃｈｅｏｎ解析法の具体例を説明するための図である。
【図３】図３は、Ｃｈｅｏｎ解析法の具体例を説明するための図である。
【図４】図４は、Ｃｈｅｏｎ解析法の具体例を説明するための図である。
【図５】図５は、ＲＷ関数の適用を説明するための図である。
【図６】図６は、特徴点のテクニックの併用を説明するための図である。
【図７】図７は、実施例１に係る暗号鍵解読装置の構成を示す図である。
【図８】図８は、テーブル生成部のブロック図である。
【図９】図９は、実施例１に係る解の計算処理の処理手順を示すフローチャートである。
【図１０】図１０は、解の計算処理を説明するための図である。
【図１１】図１１は、ループの発生を示す図である。
【図１２】図１２は、実施例２に係る暗号鍵解読装置の構成を示す図である。
【図１３】図１３は、テーブル生成部のブロック図である。
【図１４】図１４は、実施例２に係る解の計算処理の処理手順を示すフローチャートである。
【図１５】図１５は、実施例２の暗号鍵解読装置の効果を説明するための図である。
【図１６】図１６は、暗号鍵解読プログラムを実行するコンピュータを示す図である。
【発明を実施するための形態】
【００１６】
まず、本願の開示する暗号鍵解読装置における技術を説明する上での原理を図面に基づいて、いくつか説明する。
【００１７】
［Ｂａｂｙ−Ｓｔｅｐ Ｇｉａｎｔ−Ｓｔｅｐ解析法］
最初に、Ｂａｂｙ−Ｓｔｅｐ Ｇｉａｎｔ−Ｓｔｅｐ解析法について説明する。以下、Ｂａｂｙ−Ｓｔｅｐ Ｇｉａｎｔ−Ｓｔｅｐ解析法を「ＢＳＧＳ」と称する。ＢＳＧＳは、楕円曲線離散対数問題の効率的な解析法の一つである。位数ｒの楕円曲線パラメータを使用した場合、ＢＳＧＳでは、（２×ｒ１／２）回程度の楕円曲線演算によって楕円曲線離散対数問題が解かれる。ＢＳＧＳでは、秘密鍵ｋが位数ｒ１／２進数で上位と下位とに分割される。ＢＳＧＳでは、秘密鍵ｋの下位値が０となるものを含むテーブルをＢａｂｙ−Ｓｔｅｐで作成する。また、ＢＳＧＳでは、秘密鍵ｋの下位値が０の場合を総当りするテーブルをＧｉａｎｔ−Ｓｔｅｐで作成する。さらに、ＢＳＧＳでは、各テーブルの値を比較する。そして、ＢＳＧＳでは、比較結果に基づいて、秘密鍵ｋを解として算出する。ＢＳＧＳでは、各テーブルの値を比較することで、効率的に楕円曲線離散対数問題が解かれる。
【００１８】
図１は、ＢＳＧＳの具体例を説明するための図である。位数ｒ＝９７とし、秘密鍵ｋ＝９６とした場合、図１に示すように、ＢＳＧＳでは、Ｂａｂｙ−Ｓｔｅｐで（ｋ×Ｐ−ｉ×Ｐ）（ｉ＝０〜９）を計算する。なお、Ｐは所定の楕円曲線上の所定の点である。Ｂａｂｙ−Ｓｔｅｐでは、さらに、計算結果をＴｂテーブル１に登録する。これにより、Ｔｂテーブル１が作成される。ＢＳＧＳでは、Ｇｉａｎｔ−Ｓｔｅｐで、（ｊ×１０×Ｐ）（ｊ＝０〜９）を計算する。Ｇｉａｎｔ−Ｓｔｅｐでは、さらに、計算結果をＴｇテーブル２に登録する。これにより、Ｔｇテーブル２が作成される。ＢＳＧＳでは、Ｔｂテーブル１の各値とＴｇテーブル２の各値とを比較する。ここで、値とは、例えば、図１に示す例では、点の座標を指す。図１に示す例の場合では、Ｔｂテーブル１の値（５０，１２）と、Ｔｇテーブル２の値（５０，１２）とが一致する。このとき、ｉ＝６、ｊ＝９となる。ここで、秘密鍵ｋ＝（ｉ＋ｊ×１０）と表される。よって、図１に示す例の場合では、秘密鍵ｋ＝（６＋９×１０）＝９６となる。ＢＳＧＳでは、このようにして秘密鍵ｋが解として算出される。この例の場合では、楕円曲線演算は２０回（≒２×９６１／２）行われる。
【００１９】
ここで、総当り法で楕円曲線離散対数問題を解く場合を説明する。総当り法で楕円曲線離散対数問題を解く場合には、平均ｒ／２回程度の楕円曲線演算が行われる。例えば、位数ｒ＝９７とし、秘密鍵ｋ＝９６とした場合、総当り法では、Ｐとｋ×Ｐとに対し、０×Ｐ，１×Ｐ，・・・，９６×Ｐを計算する。そして、総当り法では、秘密鍵ｋ＝９６を解として算出する。この場合、平均でｒ／２＝４８回の楕円曲線演算が行われる。
【００２０】
以上のことから、ＢＳＧＳは、総当り法と比較して、楕円曲線離散対数問題を解く場合における楕円曲線演算の回数が削減される。
【００２１】
［Ｃｈｅｏｎ解析法］
次に、Ｃｈｅｏｎ解析法について説明する。Ｃｈｅｏｎ解析法は、補助入力付き楕円曲線離散対数問題に対して、ＢＳＧＳ法を適用して解を算出する方法である。Ｃｈｅｏｎ解析法では、ＢＳＧＳを二重に処理することで計算量が削減される。例えば、Ｃｈｅｏｎ解析法では、（ｄ１／２＋（ｒ／ｄ）１／２）回程度の楕円曲線演算で、補助入力付き楕円曲線離散対数問題の解が算出される。特に、ｄ≒ｒ１／２となる場合が最も効果的に計算量が削減される。例えば、ｄ≒ｒ１／２となる場合、ｒ１／４回程度の楕円曲線演算で解が算出される。なお、ｄは（ｒ−１）の約数である。
【００２２】
Ｃｈｅｏｎ解析法の具体例について説明する。図２〜４は、Ｃｈｅｏｎ解析法の具体例を説明するための図である。
【００２３】
Ｃｈｅｏｎ解析法では、まず、位数ｒの生成元ζを求め、秘密鍵ｋ＝ζｙとする（ステップＳ１）。ここで、ｙの値域は０〜ｒ−１である。図２には、比較対象のｋ×Ｐがζｙ×Ｐに変換された例が示されている。
【００２４】
次に、図２に示すように、ζの指数部分のｙを上位ｙＨと下位ｙＬ−ｉとに分割し、ｋを上位ｊと、下位値を０とした下位ｊ´とに分割する（ステップＳ２）。なお、ｙＨは、ｙを（（ｒ−１）／ｄ）で除算した商とする。また、ｙＬは、ｙを（（ｒ−１）／ｄ）で除算した余りとする。
【００２５】
次に、方程式ｋｄ×Ｐ＝（ζｄ）ｚ×Ｐからｚを算出する（ステップＳ３）。図３には、比較対象のζｙ×Ｐとζｋ×Ｐとを変形する例が示されている。ｚの算出の際には、図３に示すように、ｚを上位ｚＨと下位ｚＬ−ｉとに分割してＢＳＧＳと同等の処理を行う。なお、ｚを算出することと、ｙＬを算出することは数学的に等価である。よって、ｚが算出されることで、ｙＬが算出される。
【００２６】
次に、算出されたｙＬを用いて、図４に示すｗ（ｙＨ）を算出する（ステップＳ４）。ここで、ｗは、ｋ＝ζｙＬ＋ｗ（ｒ−１）／ｄを満たす。図４には、比較対象のζｙ×Ｐとζｋ×Ｐとを変形する例が示されている。このｗの算出の際には、図４に示すように、ｗを上位ｗＨと下位ｗＬ−ｉとに分割してＢＳＧＳと同等の処理を行う。
【００２７】
次に、ステップＳ３で算出されたｙＬと、ステップＳ４で算出されたｙＨとからｙを算出する（ステップＳ５）。そして、ステップＳ５で算出されたｙを用いて、秘密鍵ｋ＝ζｙを算出する（ステップＳ６）。以上、Ｃｈｅｏｎ解析法の具体例について説明した。このようにして、Ｃｈｅｏｎ解析法では、秘密鍵ｋの算出が行われる。
【００２８】
［ランダムウォーク関数の適用］
上記のように、Ｃｈｅｏｎ解析法は補助入力付き楕円曲線対数問題を効率的に解くことが可能である。しかしながら、Ｂａｂｙ−Ｓｔｅｐ、Ｇｉａｎｔ−Ｓｔｅｐで生成するＴｂテーブル１、Ｔｇテーブル２のサイズが大きいという問題がある。例えば、有限体ＧＦ（３１２７）におけるある楕円曲線では、パラメータｒはｒ＝９３１４８５６００４９８６２２３９６２６０１３９９となる。この場合、最適なｄを用いたとしても、Ｔｂテーブル１およびＴｇテーブル２の各テーブルには、１７４７０００個の楕円曲線上の点データが登録される。このとき、各テーブルのサイズは約８０ＭＢｙｔｅとなる。よって、計算量を増大させずに、解を得るための計算において記憶されるデータ量が削減されることが望まれる。
【００２９】
このような背景から、計算量を増大させずに、解を得るための計算において記憶されるデータ量が削減される方法が生み出された。このような方法では、例えば、Ｃｈｅｏｎ解析法において、ＢＳＧＳを用いずに、ランダムウォーク関数を適用する。そこで、この方法について説明する。また、以下、ランダムウォーク関数を「ＲＷ関数」と称する。ＲＷ関数とは、楕円曲線上の点を入力として、楕円曲線上の別の点を出力する関数である。例えば、ＲＷ関数は、楕円曲線上の点Ｐに対し、ζｄ×Ｒｎｄ（Ｐ）×Ｐのように定義される。ここで、Ｒｎｄ（Ｐ）は、点Ｐから一意的に０以上で（（ｒ−１）／ｄ）以下のランダムな整数を生成する擬似乱数生成関数である。なお、ランダムな整数を「擬似乱数」と称する。
【００３０】
図５は、ＲＷ関数の適用を説明するための図である。Ｃｈｅｏｎ解析法のステップＳ３に、上記したＲＷ関数を適用した場合、図５に示すように、点Ｐを開始点として、点ＰにＲＷ関数を適用して得られる点Ｐｓを算出し、算出された点Ｐｓを記憶する。次に、算出された点ＰｓにＲＷ関数を適用して得られる点Ｐｓを新たに算出し、新たに算出された点Ｐｓを記憶する。以降、この動作を繰り返し、点Ｐを開始点とした場合のＲＷ関数を適用して得られる各点Ｐｓがテーブルに登録される。同様に、図５に示すように、点ｋｄ×Ｐを開始点として、点ｋｄ×ＰにＲＷ関数を適用して得られる点Ｐｔを算出し、算出された点を記憶する。次に、算出された点にＲＷ関数を適用して得られる点を新たに算出し、新たに算出された点を記憶する。以降、この動作を繰り返し、点ｋｄ×Ｐを開始点とした場合のＲＷ関数を適用して得られる各点Ｐｔがテーブルに登録される。
【００３１】
そして、生成されたこれらのテーブルを比較し、一致した点Ｐ´を検出する。一致した点の情報からｋｄ×Ｐ＝ζｄ×ｋ１×Ｐを満たすｋ１を算出する。このとき、誕生日の逆理により、テーブルの大きさは（（ｒ−１）／ｄ）１／２程度でよいことが知られている。そのため、テーブル作成に必要な楕円曲線演算の回数も（（ｒ−１）／ｄ）１／２程度となる。なお、図５に示すように、ある点Ｐ´で一致すると、その後は、新たに算出された互いの点が一致するようになる。
【００３２】
［特徴点のテクニックの併用］
そして、特徴点のテクニックを併用して、以下のようにして、計算量を増大させずに、テーブルに記憶されるデータ量を削減する。図６は、特徴点のテクニックの併用を説明するための図である。図６に示すように、算出した全ての点Ｐｓ，Ｐｔを記憶せず、特徴的な点（特徴点）Ｐ´ｓ，Ｐ´ｔだけを記憶する。なお、図６では、テーブルに記憶された点Ｐ´ｓ，Ｐ´ｔは実線で示され、記憶されない点Ｐｓ，Ｐｔは破線で示されている。ここで、特徴点とは、特徴的な性質を持つ点のことである。例えば、特徴点は、点のｘ座標の下位１６ビットがすべて０であるような点である。この場合、特徴点は、確率的に２１６個に１個の割合で算出される。よって、テーブルに記憶されるデータ量は１／２１６に削減される。したがって、ＢＳＧＳを用いるＣｈｅｏｎ解析法と比較すると、計算量を増大させずに、テーブルに記憶されるデータ量が削減される。なお、一致する点Ｐ´がテーブルに一部記憶されない可能性がある。しかしながら、一致が起きれば、その後に出現する特徴点Ｐ´´でも一致することになる。そのため、問題は生じない。
【００３３】
［自己同型写像］
次に、自己同型写像について説明する。一部の楕円曲線では、楕円曲線上の点ＰのＦｒｏｂｅｎｉｕｓ写像Φ（Ｐ）が高速に計算できる。例えば、有限体ＧＦ（３１２７）における楕円曲線では、点Ｐ＝（ｘ，ｙ）のＦｒｏｂｅｎｉｕｓ写像Φ（Ｐ）＝（ｘ３，ｙ３）も同一の楕円曲線上の点となる。また、Φ（Ｐ）＝ｓ×Ｐとなるｓを簡単に求めることができる。Ｆｒｏｂｅｎｉｕｓ写像Φ（Ｐ）の計算は、各座標の値を３乗するだけである。そのため、他の楕円曲線演算に比べて高速に計算できる。よって、ｓ×Ｐも高速に計算できる。なお、点ＰにＦｒｏｂｅｎｉｕｓ写像Φ（Ｐ）をＩ回適用して得られる点であるΦ（Ｉ）（Ｐ）は以下のように記述される。すなわち、点Φ（Ｉ）（Ｐ）＝Φ（Φ（・・・（Φ（Ｐ））））となる。
【００３４】
また、一部の楕円曲線では、楕円曲線上の点のマイナス写像についても高速に計算できる。なお、マイナス写像とは、例えば、点Ｐを点−Ｐに対応させる写像である。例えば、有限体ＧＦ（３１２７）における楕円曲線では、点Ｐ＝（ｘ，ｙ）のマイナス写像−Ｐ＝（ｘ，−ｙ）も同一の楕円曲線上の点となる。また、−Ｐ＝ｔ×Ｐと表される。他の楕円曲線演算に比べて高速に計算できるため、ｔ×Ｐも高速に計算できる。
【００３５】
これらＦｒｏｂｅｎｉｕｓ写像およびマイナス写像は、楕円曲線上の点Ｐを同一の楕円曲線上の点に対応させる自己同型写像である。
【００３６】
［自己同型写像のべき表現］
そして、これらの自己同型写像を、べき表現する場合について説明する。Ｃｈｅｏｎ解析法において、自己同型写像を使用するには、自己同型写像が生成元ζの指数乗倍で表現される。有限体ＧＦ（ｑｍ）における楕円曲線の場合、任意の点にＦｒｏｂｅｎｉｕｓ写像をｍ回適用すると元の点に戻る。つまり、Φ（ｍ）（Ｐ）＝Ｐとなる。また、任意の点にマイナス写像を２回適用すると元の点に戻る。つまり、（−１）２×Ｐ＝Ｐとなる。そこで、自己同型写像（−１）（ｉ）Φ（ｊ）×Ｐ＝ζ（ｉ・ｍ＋２・ｃ・ｊ）（ｒ−１）／２ｍ×Ｐと表される。このように、自己同型写像（−１）（ｉ）Φ（ｊ）×Ｐはζのべき乗で表される。このように、べき乗で表すことを「べき表現」と称する。ここで、ｃは楕円曲線と生成元の値とによって一意に決定される定数である。また、ｉ＝０〜１である。また、ｊ＝０〜ｍ−１である。例えば、有限体ＧＦ（３１２７）、ζ＝３の場合、ｍ＝１２７、ｃ＝１１０となる。このとき、自己同型写像は以下のように表される。すなわち、（−１）（ｉ）Φ（ｊ）×Ｐ＝ζ（１２７・ｉ＋２２０・ｊ）（ｒ−１）／２５４×Ｐとなる。
【００３７】
以上、本願の開示する暗号鍵解読装置における技術を説明する上での原理を説明した。以下に、本願の開示する暗号鍵解読装置の実施例を図面に基づいて詳細に説明する。なお、この実施例によりこの発明が限定されるものではない。
【実施例１】
【００３８】
［実施例１の装置構成］
本実施例１に係る暗号鍵解読装置について説明する。図７は、本実施例１に係る暗号鍵解読装置の構成を示す図である。暗号鍵解読装置１００は、楕円曲線離散対数問題を解いて暗号鍵である秘密鍵ｋを算出する装置である。図７に示すように、暗号鍵解読装置１００は、入力部１１０、出力部１２０、処理部１３０、および記憶部１４０を有する。
【００３９】
入力部１１０は、外部から情報を入力する。例えば、入力部１１０は、ユーザからの指示を受け付けて、受け付けた指示を処理部１３０に入力する。入力部１１０は、例えば、通信によって外部装置からパラメータを取得し、取得したパラメータを処理部１３０に入力してもよい。また、入力部１１０は、例えば、マウスやキーボードを含んでもよい。また、指示としては、例えば、詳細を後述する「補助入力付き楕円曲線対数問題の解の計算処理」を実行する指示がある。以下、「補助入力付き楕円曲線対数問題の解の計算処理」を、「解の計算処理」と略する。
【００４０】
出力部１２０は、外部へ情報を出力する。例えば、出力部１２０は、秘密鍵ｋおよび計算時間Ｔを後述するＤＬＰ計算部１３４から受け付ける。なお、計算時間Ｔは、解の計算に要する時間である。出力部１２０は、受け付けた秘密鍵ｋおよび計算時間Ｔの各値を出力する。出力部１２０は、例えば、ディスプレイを含んで構成するようにしてもよい。この場合、ディスプレイに秘密鍵ｋおよび計算時間Ｔの各値が表示される。また、出力部１２０は、例えば、スピーカーを含んで構成されてもよい。この場合、スピーカーから音声によって秘密鍵ｋおよび計算時間Ｔの各値が出力される。また、出力部１２０は、通信によって外部の装置に秘密鍵ｋおよび計算時間Ｔの各値を出力してもよい。
【００４１】
記憶部１４０は、第１のテーブル１４１と第２のテーブル１４２とを有する。第１のテーブル１４１には、後述する代表点Ｐ＊ｒｅｐｉと指標ｉｎｄｅｘｉとが対応付けて登録される。第２のテーブル１４２には、後述する代表点Ｐ＊ｒｅｐｄｉと指標ｉｎｄｅｘｄｉとが対応付けて登録される。
【００４２】
処理部１３０は、パラメータ取得部１３１、テーブル生成部１３２およびテーブル比較部１３３を有する。また、処理部１３０は、ＤＬＰ（Ｄｉｓｃｒｅｔｅ Ｌｏｇａｒｉｔｈｍ Ｐｒｏｂｌｅｍ）計算部１３４および制御部１３５を有する。
【００４３】
パラメータ取得部１３１は、解の計算処理の指示が入力された場合に、以下の処理を行う。すなわち、パラメータ取得部１３１は、例えば、外部装置から入力部１１０を介してシステムパラメータを取得する。そして、パラメータ取得部１３１は、取得したシステムパラメータをテーブル生成部１３２に入力する。なお、記憶部１４０に予めシステムパラメータを記憶しておき、パラメータ取得部１３１は、記憶部１４０からこのシステムパラメータを取得してもよい。
【００４４】
システムパラメータの一例について説明する。システムパラメータには、楕円曲線Ｅ上の所定の点である点Ｐ、点（ｋ×Ｐ）、所定の暗号鍵から定まる点である点（ｋｄ×Ｐ）およびｄが含まれる。また、楕円曲線のパラメータには秘密鍵ｋのビット長なども含まれる。また、システムパラメータには、テーブルの登録番号を示す指標ｉｎｄｅｘ０が含まれる。なお、指標ｉｎｄｅｘｎは、例えば、数値ｎを示す。なお、楕円曲線のパラメータはこれらに限られない。
【００４５】
テーブル生成部１３２は、入力されたシステムパラメータに基づいて、楕円曲線Ｅ上の点Ｐに対して自己同型写像を適用して点の集合を算出する。テーブル生成部１３２は、点Ｐを開始点として算出された点（以下、第１の点と称する場合がある）の集合の中から代表点（以下、第１の代表点と称する場合がある）を選択して記憶部１４０に記憶させる。テーブル生成部１３２は、第１の代表点に対して擬似乱数を用いて楕円曲線Ｅ上の点を算出する。テーブル生成部１３２は、後述する制御部１３５の制御によってこれらの処理を繰り返し行うことで、記憶部１４０に追加して第１の代表点を記憶して、複数の第１の代表点を記憶部１４０に記憶する。
【００４６】
また、テーブル生成部１３２は、楕円曲線Ｅ上において点（ｋｄ×Ｐ）に対して自己同型写像を適用して点の集合を算出する。テーブル生成部１３２は、点（ｋｄ×Ｐ）を開始点として算出された点（以下、第２の点と称する場合がある）の集合の中から代表点（以下、第２の代表点と称する場合がある）を選択して記憶部１４０に記憶させる。テーブル生成部１３２は、第２の代表点に対して擬似乱数を用いて楕円曲線Ｅ上の点を算出する。テーブル生成部１３２は、後述するテーブル比較部１３３で第１の代表点に一致する第２の代表点が検出されるまで、制御部１３５の制御によって、これらの処理を繰り返し行う。これにより、テーブル生成部１３２は、記憶部１４０に追加して第２の代表点を記憶して、複数の第２の代表点を記憶部１４０に記憶する。
【００４７】
ここで、テーブル生成部１３２の詳細を説明する。図８はテーブル生成部１３２のブロック図である。テーブル生成部１３２は、テーブル生成制御部１５０、自己同型写像計算部１５１、代表点選択部１５２およびＲＷ関数部１５３を有する。
【００４８】
テーブル生成制御部１５０は、パラメータ取得部１３１から指標ｉｎｄｅｘ０と点Ｐ＊（点Ｐ）とを受け付ける。また、テーブル生成制御部１５０は、パラメータ取得部１３１から指標ｉｎｄｅｘ０と点Ｐ＊ｄ（ｋｄ×Ｐ）とを受け付ける。テーブル生成制御部１５０は、受け付けた点Ｐ＊または点Ｐ＊ｄを自己同型写像計算部１５１に出力する。テーブル生成制御部１５０は、代表点選択部１５２から第１の代表点である代表点Ｐ＊ｒｅｐｉ（ｉ＝０〜ｖ）または第２の代表点であるＰ＊ｒｅｐｄｉを受け付ける。テーブル生成制御部１５０は、指標ｉｎｄｅｘｉと受け付けた代表点Ｐ＊ｒｅｐｉとを対応付けて第１のテーブル１４１に登録する。また、テーブル生成制御部１５０は、指標ｉｎｄｅｘｉと受け付けた代表点Ｐ＊ｒｅｐｄｉとを対応付けて第２のテーブル１４２に登録する。
【００４９】
テーブル生成制御部１５０は、受け付けた指標ｉｎｄｅｘｉと代表点Ｐ＊ｒｅｐｉまたはＰ＊ｒｅｐｄｉとをＲＷ関数部１５３へ出力する。テーブル生成制御部１５０は、ＲＷ関数部１５３から指標ｉｎｄｅｘｉ＋１と点Ｐ＊ｉ＋１または点Ｐ＊ｄｉ＋１とを受け付ける。そして、テーブル生成制御部１５０は、ＲＷ関数部１５３から受け付けた点Ｐ＊ｉ＋１または点Ｐ＊ｄｉ＋１を自己同型写像計算部１５１に出力する。テーブル生成制御部１５０は上記の処理を繰り返し行って、第１のテーブル１４１に複数の代表点Ｐ＊ｒｅｐｉおよび第２のテーブル１４２に複数の代表点Ｐ＊ｒｅｐｄｉを追加して登録する。
【００５０】
自己同型写像計算部１５１は、テーブル生成制御部１５０から点Ｐ＊ｉまたは点Ｐ＊ｄｉを受け付ける。なお、点Ｐは、ｉ＝０として、点Ｐ＊０と表される。また、点（ｋｄ×Ｐ）は、ｉ＝０として、点Ｐ＊ｄ０と表される。自己同型写像計算部１５１は、受け付けた点Ｐ＊ｉに対して、下記の式（１）、式（２）に示す自己同型写像を適用する。また、自己同型写像計算部１５１は、受け付けた点Ｐ＊ｄｉに対して、以下の式（３）、（４）に示す自己同型写像を適用する。
【００５１】
【数１】
【００５２】
【数２】
【００５３】
【数３】
【００５４】
【数４】
【００５５】
ただし、ω´はω＝ω´・ｄを満たす。また、ν´はν＝ν´・ｄを満たす。また、ωは、Φ（Ｐ）＝（ｘ３，ｙ３）＝Ω×Ｐ＝ζω×Ｐを満たす。また、νは、−Ｐ＝ζν×Ｐを満たす。
【００５６】
自己同型写像計算部１５１は、例えば、受け付けた点Ｐ＊ｉに対して、式（１）に示す自己同型写像をｍ−１回適用させる。すると、点Ｐ＊ｉを含めるとｍ個の点｛Ｐ＊ｉ（ｓ）｝（ｓ＝０〜ｍ−１）の集合が算出される。そして、自己同型写像計算部１５１は、｛Ｐ＊ｉ（ｓ）｝の各点に対して、式（２）に示す自己同型写像を適用する。これにより、結果として、点Ｐ＊ｉから２ｍ個の点｛Ｐ＊ｉ（ｈ）｝（ｈ＝０〜２ｍ−１）が算出される。
【００５７】
また、自己同型写像計算部１５１は、例えば、受け付けた点Ｐ＊ｄｉに対して、式（３）に示す自己同型写像をｍ−１回適用させる。すると、点Ｐ＊ｄｉを含めるとｍ個の点｛Ｐ＊ｄｉ（ｓ）｝（ｓ＝０〜ｍ−１）の集合が算出される。そして、自己同型写像計算部１５１は、｛Ｐ＊ｄｉ（ｓ）｝の各点に対して、式（４）に示す自己同型写像を適用する。これにより、結果として、点Ｐ＊ｄｉから２ｍ個の点｛Ｐ＊ｄｉ（ｈ）｝（ｈ＝０〜２ｍ−１）が算出される。
【００５８】
自己同型写像計算部１５１は、自己同型写像によって対応させた２ｍ個の点｛Ｐ＊ｉ（ｈ）｝または２ｍ個の点｛Ｐ＊ｄｉ（ｈ）｝を１つの集合として代表点選択部１５２へ出力する。
【００５９】
代表点選択部１５２は、自己同型写像計算部１５１から２ｍ個の点｛Ｐ＊ｉ（ｈ）｝または２ｍ個の点｛Ｐ＊ｄｉ（ｈ）｝を受け付ける。代表点選択部１５２は、受け付けた２ｍ個の点｛Ｐ＊ｉ（ｈ）｝の中から代表点Ｐ＊ｒｅｐｉを一つ選択する。また、代表点選択部１５２は、受け付けた２ｍ個の点｛Ｐ＊ｄｉ（ｈ）｝の中から代表点Ｐ＊ｒｅｐｄｉを一つ選択する。代表点選択部１５２は、選択した代表点Ｐ＊ｒｅｐｉまたはＰ＊ｒｅｐｄｉをテーブル生成制御部１５０へ出力する。なお、代表点選択部１５２は、例えば、２ｍ個の点｛Ｐ＊ｉ（ｈ）｝または｛Ｐ＊ｄｉ（ｈ）｝の中からｘ座標の値が最も小さい点を代表点として選択する。なお、代表点の選択の方法はこれに限られない。
【００６０】
ＲＷ関数部１５３は、テーブル生成制御部１５０から指標ｉｎｄｅｘｉと代表点Ｐ＊ｒｅｐｉまたはＰ＊ｒｅｐｄｉとを受け付ける。ＲＷ関数部１５３は、ＲＷ関数を用いて代表点Ｐ＊ｒｅｐｉから点Ｐ＊ｉ＋１を算出する。また、ＲＷ関数部１５３は、ＲＷ関数を用いて代表点Ｐ＊ｒｅｐｄｉから点Ｐ＊ｄｉ＋１を算出する。なお、ＲＷ関数は、楕円曲線上の点Ｐ＊ｒｅｐｉに対し、下記の式（５）に示すように定義される。同様に、ＲＷ関数は、楕円曲線上の点Ｐ＊ｒｅｐｄｉに対し、下記の式（６）に示すように定義される。ここで、Ｒｎｄ（Ｐ）は、点Ｐから一意的に０以上で（（ｒ−１）／ｄ）以下のランダムな整数を生成する擬似乱数生成関数である。
【００６１】
【数５】
【００６２】
【数６】
【００６３】
ＲＷ関数部１５３は受け付けた指標ｉｎｄｅｘｉを１インクリメントさせて指標ｉｎｄｅｘｉ＋１を算出する。ＲＷ関数部１５３は、指標ｉｎｄｅｘｉ＋１と、算出した点Ｐ＊ｉ＋１または点Ｐ＊ｄｉ＋１とをテーブル生成制御部１５０へ出力する。
【００６４】
ここで、図７の説明に戻る。テーブル比較部１３３は、第１のテーブル１４１に登録された代表点Ｐ＊ｒｅｐｉと第２のテーブル１４２に登録された代表点Ｐ＊ｒｅｐｄｉとを比較して一致する代表点を検出する。テーブル比較部１３３は、一致する代表点の情報をＤＬＰ計算部１３４に出力する。
【００６５】
ＤＬＰ計算部１３４は、一致する代表点の情報に基づいて、秘密鍵ｋを算出する。また、ＤＬＰ計算部１３４は、計算時間Ｔを算出する。なお、計算時間Ｔは、解の計算に要する時間である。例えば、計算時間Ｔは、後述する解の計算処理のステップＳ１０２〜Ｓ１１５までに要した時間である。ＤＬＰ計算部１３４は、算出された秘密鍵ｋおよび計算時間Ｔを出力部１２０に出力する。また、ＤＬＰ計算部１３４は、算出された秘密鍵ｋおよび計算時間Ｔを記憶部１４０に格納する。
【００６６】
制御部１３５は、パラメータ取得部１３１、テーブル生成部１３２、テーブル比較部１３３およびＤＬＰ計算部１３４の各部に対して、上記で説明したような動作を行うように制御する。例えば、制御部１３５は、算出された点Ｐ＊ｉに対して自己同型写像を適用して新たな第１の点である点｛Ｐ＊ｉ（ｈ）｝の集合を算出するようにテーブル生成部１３２を制御する。制御部１３５は、新たな点｛Ｐ＊ｉ（ｈ）｝の集合の中から新たな代表点Ｐ＊ｒｅｐｉを選択して記憶部１４０に追加して記憶させるようにテーブル生成部１３２を制御する。制御部１３５は、新たな代表点Ｐ＊ｒｅｐｉに対して擬似乱数を用いて楕円曲線Ｅ上の新たな点Ｐ＊ｉ＋１を算出するようにテーブル生成部１３２を制御する。制御部１３５は、これらの上記制御を複数回行って、複数の点｛Ｐ＊ｉ（ｈ）｝の集合に関する複数の代表点Ｐ＊ｒｅｐｉを記憶部１４０に記憶させる。ここで、複数回とは、例えば、（ｒ−１）回である。
【００６７】
また、制御部１３５は、テーブル比較部１３３の比較結果に基づいて、第２の点｛Ｐ＊ｄｉ（ｈ）｝の集合に関する代表点Ｐ＊ｒｅｐｄｉに一致する代表点Ｐ＊ｒｅｐｉがない場合には、以下の処理を行う。すなわち、制御部１３５は、今回記憶された代表点Ｐ＊ｒｅｐｄｉに対して擬似乱数を用いて楕円曲線Ｅ上の新たな点Ｐ＊ｄｉ＋１を算出するようにテーブル生成部１３２を制御する。そして、制御部１３５は、算出された新たな点Ｐ＊ｄｉ＋１に対して自己同型写像を適用して新たな第２の点｛Ｐ＊ｄｉ＋１（ｈ）｝の集合を算出するようにテーブル生成部１３２を制御する。そして、制御部１３５は、新たな第２の点｛Ｐ＊ｄｉ＋１（ｈ）｝の集合の中から新たな代表点Ｐ＊ｒｅｐｄｉ＋１を選択して記憶部１４０に追加して記憶させるようにテーブル生成部１３２を制御する。そして、制御部１３５は、これらの上記制御を、代表点が一致するまで繰り返し行う。
【００６８】
［実施例１の処理手順］
次に、処理部１３０による解の計算処理の処理手順について説明する。図９は、処理部１３０による解の計算処理の処理手順を示すフローチャートである。
【００６９】
図９に示すように、処理部１３０は、入力部１１０から解の計算処理を実行する指示が入力されたか否かを判定する（ステップＳ１００）。処理部１３０は、当該指示が入力された場合には（ステップＳ１００，Ｙｅｓ）、タイマーをスタートさせて時間Ｔの計測を開始する（ステップＳ１０１）。
【００７０】
処理部１３０は、システムパラメータを取得する（ステップＳ１０２）。処理部１３０は、取得したシステムパラメータの中から点Ｐ＊ｉ（ｉ＝０）を抽出する（ステップＳ１０３）。
【００７１】
処理部１３０は、点Ｐ＊ｉに対して、上記の式（１）、式（２）に示す自己同型写像を適用して、２ｍ個の点｛Ｐ＊ｉ（ｈ）｝を算出する（ステップＳ１０４）。すなわち、ステップＳ１０４で、Ｐ＊ｉから２ｍ個の点｛Ｐ＊ｉ（ｈ）｝の集合を算出する。処理部１３０は、算出された２ｍ個の点｛Ｐ＊ｉ（ｈ）｝の集合の中から代表点Ｐ＊ｒｅｐｉを一つ選択する（ステップＳ１０５）。
【００７２】
処理部１３０は、選択された代表点Ｐ＊ｒｅｐｉと指標ｉｎｄｅｘｉとを対応付けて、第１のテーブル１４１に登録する（ステップＳ１０６）。これにより、記憶部１４０に、代表点Ｐ＊ｒｅｐｉが記憶される。
【００７３】
処理部１３０は、ＲＷ関数を用いて代表点Ｐ＊ｒｅｐｉから点Ｐ＊ｉ＋１を算出する（ステップＳ１０７）。処理部１３０は、ｉを１インクリメントする（ステップＳ１０８）。処理部１３０は、ｉの値が所定値ｖ以上であるか否かを判定する（ステップＳ１０９）。処理部１３０は、ｉの値が所定値ｖ未満である場合には（ステップＳ１０９，Ｎｏ）、上記ステップＳ１０４へ戻り、上記で説明した処理を行う。このように、ステップＳ１０４〜１０９の処理を繰り返すことにより、テーブル１４１にはｖ個の代表点Ｐ＊ｒｅｐｉ（ｉ＝０〜ｖ−１）が登録される。すなわち、記憶部１４０には、ｖ個の代表点Ｐ＊ｒｅｐｉが記憶される。なお、所定値ｖの値を、例えば、ｒ−１としてもよい。所定値ｖの値をｒ−１とした場合には、記憶部１４０には、ｒ−１個の代表点Ｐ＊ｒｅｐｉが記憶される。
【００７４】
図１０は、解の計算処理を説明するための図である。図１０に示すように、点（｛Ｐ＊ｉ（ｈ）｝）５２の集合５０の中から代表点（Ｐ＊ｒｅｐｉ）５１が、解を得るための情報として選択され、テーブル１４１に登録される。そして、代表点５１から、ＲＷ関数により当該代表点５１が属する集合とは異なる集合５０の点（｛Ｐ＊ｉ＋１（ｈ）｝）５２が算出される。これらの処理がステップＳ１００〜１０９で繰り返されることで、複数の代表点５１がテーブル１４１に登録される。
【００７５】
一方、ｉの値が所定値ｖ以上である場合には（ステップＳ１０９，Ｙｅｓ）、処理部１３０は、取得したシステムパラメータの中から点Ｐ＊ｄｉ（ｉ＝０）を抽出する（ステップＳ１１０）。
【００７６】
処理部１３０は、点Ｐ＊ｄｉに対して、上記の式（３）、式（４）に示す自己同型写像を適用して、２ｍ個の点｛Ｐ＊ｄｉ（ｈ）｝を算出する（ステップＳ１１１）。すなわち、ステップＳ１１１で、Ｐ＊ｄｉから２ｍ個の点｛Ｐ＊ｄｉ（ｈ）｝の集合を算出する。
【００７７】
処理部１３０は、算出された２ｍ個の点｛Ｐ＊ｄｉ（ｈ）｝の集合の中から代表点Ｐ＊ｒｅｐｄｉを一つ選択する（ステップＳ１１２）。処理部１３０は、選択された代表点Ｐ＊ｒｅｐｄｉと指標ｉｎｄｅｘｄｉとを対応付けて、第２のテーブル１４２に登録する（ステップＳ１１３）。これにより、記憶部１４０に、代表点Ｐ＊ｒｅｐｄｉが記憶される。
【００７８】
処理部１３０は、第１のテーブル１４１に登録された複数の代表点Ｐ＊ｒｅｐｉの各々と、第２のテーブル１４２に今回登録された代表点Ｐ＊ｒｅｐｄｉとを比較し、代表点Ｐ＊ｒｅｐｄｉに一致する代表点Ｐ＊ｒｅｐｉがあるか否かを判定する（ステップＳ１１４）。
【００７９】
代表点Ｐ＊ｒｅｐｄｉに一致する代表点Ｐ＊ｒｅｐｉがある場合には（ステップＳ１１４，Ｙｅｓ）、処理部１３０は、一致する代表点の情報に基づいて、秘密鍵ｋを算出する（ステップＳ１１５）。処理部１３０は、タイマーをストップする（ステップＳ１１６）。これにより、解の計算に要する時間である計算時間Ｔが算出される。処理部１３０は、算出された秘密鍵ｋおよび計算時間Ｔを出力部１２０に出力する（ステップＳ１１７）。このとき、処理部１３０は、秘密鍵ｋおよび計算時間Ｔを記憶部１４０に格納する（同ステップＳ１１７）。
【００８０】
一方、代表点Ｐ＊ｒｅｐｄｉに一致する代表点Ｐ＊ｒｅｐｉがない場合には（ステップＳ１１４，Ｎｏ）、処理部１３０は、ＲＷ関数を用いて代表点Ｐ＊ｒｅｐｄｉから点Ｐ＊ｄｉ＋１を算出する（ステップＳ１１８）。処理部１３０は、ｉを１インクリメントし（ステップＳ１１９）、上記ステップＳ１１１へ戻り、上記で説明した処理を行う。ステップＳ１１０〜１１４、１１８、１１９の処理では、点（｛Ｐ＊ｄｉ（ｈ）｝）の集合の中から代表点（Ｐ＊ｒｅｐｄｉ）が、解を得るための情報として選択され、テーブル１４２に登録される。そして、代表点（Ｐ＊ｒｅｐｄｉ）から、ＲＷ関数により当該代表点（Ｐ＊ｒｅｐｄｉ）が属する集合とは異なる集合５０の点（｛Ｐ＊ｉ＋１（ｈ）｝）が算出される。これらの処理がステップＳ１１０〜１１４、１１８、１１９で繰り返されることで、複数の代表点（Ｐ＊ｒｅｐｄｉ）がテーブル１４２に登録される。
【００８１】
［実施例１の効果等］
以上、本実施例１に係る暗号鍵解読装置１００について説明した。本実施例１によれば、Ｃｈｅｏｎ解析法にＲＷ関数を適用し、上述した自己同型写像を適用して数学的問題を解いている。例えば、本実施例１によれば、楕円曲線Ｅ上の所定の点であるＰに対して自己同型写像を適用して点｛Ｐ＊０（ｈ）｝の集合が算出される。また、この集合の中から代表点Ｐ＊ｒｅｐ０を選択して記憶部１４０に記憶させる。また、代表点Ｐ＊ｒｅｐ０に対して擬似乱数を用いて楕円曲線Ｅ上の点Ｐ＊１を算出する。また、本実施例１によれば、点Ｐ＊１に対して自己同型写像を適用することで、新たな代表点Ｐ＊ｒｅｐｉを記憶部１４０に記憶させる。
【００８２】
また、本実施例１によれば、楕円曲線Ｅ上において所定の暗号鍵ｋから定まる点である（ｋｄ×Ｐ）に対して自己同型写像を適用して点｛Ｐ＊ｄ０（ｈ）｝の集合を算出する。また、この集合の中から代表点Ｐ＊ｒｅｐｄ０を選択して記憶部１４０に記憶させる。また、代表点Ｐ＊ｒｅｐｄ０に対して擬似乱数を用いて楕円曲線Ｅ上の点Ｐ＊ｄ１を算出する。また、点Ｐ＊ｄ１に対して自己同型写像を適用することで、新たな代表点Ｐ＊ｒｅｐｄｉを記憶部１４０に記憶させる。また、記憶部１４０に記憶された代表点Ｐ＊ｒｅｐｉと代表点Ｐ＊ｒｅｐｄｉとを比較し、一致した代表点に基づいて暗号鍵ｋを算出する。
【００８３】
従って、本実施例１によれば、記憶容量が圧迫されずに、暗号鍵ｋを解くことができる。例えば、本実施例１によれば、計算に必要な記憶容量が（（ｒ−１）／２ｍ）１／４となる。従来のＣｈｅｏｎ解析法では計算に必要な記憶容量が（ｒ−１）１／４であった。このように暗号鍵解読装置１００によれば、従来のＣｈｅｏｎ解析法と比較すると、計算に必要な記憶容量が１／（２ｍ）１／４倍削減される。
【実施例２】
【００８４】
［実施例２の装置構成］
次に、実施例２に係る暗号鍵解読装置について説明する。図１１はループの発生を示す図である。上記で説明した実施例１に係る暗号鍵解読装置１００では、図１１に示すように、代表点５１が、既に選択された代表点５１を含む集合５０内に、再び、ＲＷ関数によって算出されてしまうことがある。これは、ＲＷ関数で生成される擬似乱数の最大値が（（ｒ−１）／ｄ）となるからである。このような場合、既に選択された代表点５１を選択し続けることになる。そのため、点５２および代表点５１が算出されない集合５０´が存在してしまう。よって、暗号鍵解読の観点から更なる改良が望まれる。そこで、実施例２に係る暗号鍵解読装置では、既に選択された代表点を含む集合とは異なる集合に属する点５２を算出することができるようにした。なお、既に選択された代表点５１を選択し続ける現象を「ループ」と称する。
【００８５】
なお、実施例１と同様の構成および処理については同一の符号を付し、説明を省略する。図１２は、本実施例２に係る暗号鍵解読装置の構成を示す図である。図１２に示すように、暗号鍵解読装置２００は、入力部１１０、出力部１２０、処理部２３０、および記憶部１４０を有する。本実施例２に係る暗号鍵解読装置２００では、実施例１の処理部１３０に代えて処理部２３０を有する。なお、入力部１１０、出力部１２０、および記憶部１４０は実施例１と同様の構成であるので、以下では説明は省略する。
【００８６】
処理部２３０は、パラメータ取得部１３１、テーブル生成部２３２およびテーブル比較部１３３を有する。また、処理部２３０は、ＤＬＰ（Ｄｉｓｃｒｅｔｅ Ｌｏｇａｒｉｔｈｍ Ｐｒｏｂｌｅｍ）計算部１３４および制御部１３５を有する。
【００８７】
テーブル生成部２３２は、入力されたシステムパラメータに基づいて、楕円曲線Ｅ上の点Ｐに対して自己同型写像を適用して点の集合を算出する。テーブル生成部２３２は、点Ｐを開始点として算出された第１の点の集合の中から第１の代表点を選択して記憶部１４０に記憶させる。テーブル生成部２３２は、第１の代表点に対して擬似乱数を用いて楕円曲線Ｅ上の点を算出する。テーブル生成部２３２は、制御部１３５の制御によってこれらの処理を繰り返し行うことで、記憶部１４０に追加して第１の代表点を記憶して、複数の第１の代表点を記憶部１４０に記憶する。
【００８８】
また、テーブル生成部２３２は、楕円曲線Ｅ上において点（ｋｄ×Ｐ）に対して自己同型写像を適用して点の集合を算出する。テーブル生成部２３２は、点（ｋｄ×Ｐ）を開始点として算出された第２の点の集合の中から第２の代表点を選択して記憶部１４０に記憶させる。テーブル生成部２３２は、第２の代表点に対して擬似乱数を用いて楕円曲線Ｅ上の点を算出する。テーブル生成部２３２は、テーブル比較部１３３で第１の代表点に一致する第２の代表点が検出されるまで、制御部１３５の制御によって、これらの処理を繰り返し行う。これにより、テーブル生成部２３２は、記憶部１４０に追加して第２の代表点を記憶して、複数の第２の代表点を記憶部１４０に記憶する。
【００８９】
ここで、テーブル生成部２３２の詳細に説明する。図１３はテーブル生成部２３２のブロック図である。テーブル生成部２３２は、テーブル生成制御部１５０、自己同型写像計算部１５１、代表点選択部１５２およびＲＷ関数部２５３を有する。
【００９０】
テーブル生成制御部１５０、自己同型写像計算部１５１、および代表点選択部１５２については実施例１と同様の構成であるので説明を省略する。
【００９１】
ＲＷ関数部２５３は、テーブル生成制御部１５０から指標ｉｎｄｅｘｉと代表点Ｐ＊ｒｅｐｉまたはＰ＊ｒｅｐｄｉとを受け付ける。ＲＷ関数部２５３は、ＲＷ関数を用いて代表点Ｐ＊ｒｅｐｉから点Ｐ＊ｉ＋１を算出する。ＲＷ関数部２５３は、ＲＷ関数を用いて代表点Ｐ＊ｒｅｐｄｉから点Ｐ＊ｄｉ＋１を算出する。なお、ＲＷ関数は、楕円曲線上の点Ｐ＊ｒｅｐｉに対し、以下の式（７）に示すように定義される。同様に、ＲＷ関数は、楕円曲線上の点Ｐ＊ｒｅｐｄｉに対し、以下の式（８）に示すように定義される。ここで、この場合のＲｎｄ（Ｐ）は、点Ｐから一意的に０以上で（（ｒ−１）／２ｍｄ）以下のランダムな整数を生成する擬似乱数生成関数である。
【００９２】
【数７】
【００９３】
【数８】
【００９４】
ここで、自己同型写像計算部１５１で適用される自己同型写像について説明する。上記式（１）、式（２）の自己同型写像は、下記の式（９）のように表される。
【００９５】
【数９】
【００９６】
ただし、ωはω＝（ｃ・（ｒ−１）／ｍ）を満たす。ただし、ｃはζによって一意に定まる定数である。また、νはν＝（ｒ−１）／２を満たす。また、ζは、Φ（Ｐ）＝（ｘ３，ｙ３）＝Ω×Ｇ＝ζω×Ｇを満たし、−Ｐ＝ζν×Ｇを満たす。このように、ω、νは点の位数ｒと拡大次数ｍ（ＧＦ（ｑｍ））で表現される。
【００９７】
以上のように、擬似乱数Ｒｎｄ（）の値の範囲が、実施例１では、０≦ｄ・Ｒｎｄ（）≦（（ｒ−１））であったのが、実施例２では、０≦ｄ・Ｒｎｄ（）≦（（ｒ−１）／２ｍ）となる。これにより、実施例２では、擬似乱数の最大値が、実施例１と比較して１／２ｍ倍に削減される。また、式（７）、式（８）のζの指数部に注目すると、この指数部は、（μ×（ｒ−１）／２ｍ）＋（ｄ×Ｒｎｄ（））と記述される。これは、（（ｒ−１）／２ｍ）の倍数は自己同型写像で探索し、（（ｒ−１）／２ｍ）の倍数でないものをＲＷ関数で探索することを意味している。
【００９８】
よって、ＲＷ関数によって算出される点Ｐ＊ｉ＋１または点Ｐ＊ｉ＋１は、既に選択した点Ｐ＊ｒｅｐｉまたは点Ｐ＊ｒｅｐｄｉを含む集合の点とは異なる集合の点となる。これにより、ループが防止される。より詳細に説明する。実施例１では、ランダム関数で生成される擬似乱数Ｒｎｄ（）の値の範囲が上記の０≦ｄ・Ｒｎｄ（）≦（（ｒ−１））である。このため、ランダム関数によって既に生成されたある点の集合内で別の点がランダム関数によって生成される場合がある。この場合には、この集合内の点では既に選択された代表点と同一の代表点が選択されてしまう。その結果、ループが発生する。
【００９９】
一方、実施例２では、ランダム関数で生成される擬似乱数Ｒｎｄ（）の値の範囲を上記の０≦ｄ・Ｒｎｄ（）≦（（ｒ−１）／２ｍ）とした結果、ランダム関数によって既に生成されたある点の集合とは異なる集合の点がランダム関数によって算出される。
【０１００】
また、ＲＷ関数部２５３は受け付けた指標ｉｎｄｅｘｉを１インクリメントさせて指標ｉｎｄｅｘｉ＋１を算出する。ＲＷ関数部２５３は、指標ｉｎｄｅｘｉ＋１と、算出した点Ｐ＊ｉ＋１または点Ｐ＊ｄｉ＋１とをテーブル生成制御部１５０へ出力する。
【０１０１】
制御部１３５は、パラメータ取得部１３１、テーブル生成部２３２、テーブル比較部１３３およびＤＬＰ計算部１３４の各部に対して、上記で説明したような動作を行うように制御する。例えば、制御部１３５は、算出された点Ｐ＊ｉに対して自己同型写像を適用して新たな第１の点である点｛Ｐ＊ｉ（ｈ）｝の集合を算出するようにテーブル生成部２３２を制御する。制御部１３５は、新たな点｛Ｐ＊ｉ（ｈ）｝の集合の中から新たな代表点Ｐ＊ｒｅｐｉを選択して記憶部１４０に追加して記憶させるようにテーブル生成部２３２を制御する。制御部１３５は、新たな代表点Ｐ＊ｒｅｐｉに対して擬似乱数を用いて楕円曲線Ｅ上の新たな点Ｐ＊ｉ＋１を算出するようにテーブル生成部２３２を制御する。制御部１３５は、これらの上記制御を複数回行って、複数の点｛Ｐ＊ｉ（ｈ）｝の集合に関する複数の代表点Ｐ＊ｒｅｐｉを記憶部１４０に記憶させる。
【０１０２】
また、制御部１３５は、テーブル比較部１３３の比較結果に基づいて、第２の点｛Ｐ＊ｄｉ（ｈ）｝の集合に関する代表点Ｐ＊ｒｅｐｄｉに一致する代表点Ｐ＊ｒｅｐｉがない場合には、以下の処理を行う。すなわち、制御部１３５は、今回記憶された代表点Ｐ＊ｒｅｐｄｉに対して擬似乱数を用いて楕円曲線Ｅ上の新たな点Ｐ＊ｄｉ＋１を算出するようにテーブル生成部２３２を制御する。そして、制御部１３５は、算出された新たな点Ｐ＊ｄｉ＋１に対して自己同型写像を適用して新たな第２の点｛Ｐ＊ｄｉ＋１（ｈ）｝の集合を算出するようにテーブル生成部２３２を制御する。そして、制御部１３５は、新たな第２の点｛Ｐ＊ｄｉ＋１（ｈ）｝の集合の中から新たな代表点Ｐ＊ｒｅｐｄｉ＋１を選択して記憶部１４０に追加して記憶させるようにテーブル生成部２３２を制御する。そして、制御部１３５は、これらの上記制御を、代表点が一致するまで繰り返し行う。
【０１０３】
次に、処理部２３０による解の計算処理の処理手順について説明する。図１４は、処理部２３０の解の計算処理の処理手順を示すフローチャートである。
【０１０４】
なお、本実施例２における解の計算処理では、実施例１のステップＳ１０７に代えてステップＳ２０７が実行される。また、実施例１のステップＳ１１８に代えてステップＳ２１８が実行される。そのため、これらのステップＳ２０７、２１８について説明を行い、その他の実施例１と同様のステップについては説明を省略する。
【０１０５】
ステップＳ２０７について説明する。処理部２３０は、ＲＷ関数を用いて、擬似乱数を生成し、代表点Ｐ＊ｒｅｐｉから点Ｐ＊ｉ＋１を算出する（ステップＳ２０７）。ここで、この擬似乱数は、上述したように以下の式（１０）に示す範囲内で生成される。
【０１０６】
【数１０】
【０１０７】
ただし、Ｗは当該擬似乱数の値であり、ｍは楕円曲線暗号が定義された有限体における拡大次数であり、ｄは（ｒ−１）の約数である。
【０１０８】
上記式（１０）が示す範囲内で擬似乱数を生成することで、ステップＳ２０７において、ステップＳ１０５で既に選択された代表点Ｐ＊ｒｅｐｉを含む集合とは異なる集合に属する点Ｐ＊ｉ＋１が算出される。
【０１０９】
さらに、ステップＳ２１８について説明する。処理部２３０は、ＲＷ関数を用いて、擬似乱数を生成し、代表点Ｐ＊ｒｅｐｄｉから点Ｐ＊ｄｉ＋１を算出する（ステップＳ２１８）。この擬似乱数は、上述したように上記式（１０）に示す範囲内で生成される。上記式（１０）が示す範囲内で擬似乱数を生成することで、ステップＳ２１８において、ステップＳ１１２で既に選択された代表点Ｐ＊ｒｅｐｄｉを含む集合とは異なる集合に属する点Ｐ＊ｄｉ＋１が算出される。
【０１１０】
［実施例２の効果等］
以上、本実施例２に係る暗号鍵解読装置２００について説明した。実施例２によれば、Ｃｈｅｏｎ解析法と比較して、計算時に記憶されるデータ量が少なくなるため、記憶容量が圧迫されずに、暗号鍵を解くことができる。また、実施例２によれば、ループを防止できる。また、実施例２によれば、ループを防止できるので、実施例１よりも、暗号鍵の解読に必要な計算量が少なくなる。
【０１１１】
図１５は本実施例２の暗号鍵解読装置２００の効果を説明するための図である。既に説明したが、図１５に示すように、実施例１では計算に必要な記憶容量が（（ｒ−１）／２ｍ）１／４となる。そのため、従来の技術であるＣｈｅｏｎ解析法と比較すると、実施例１では、計算に必要な記憶容量が１／（２ｍ）１／４倍削減される。
【０１１２】
しかしながら、図１５に示すように、実施例１ではループになる確率が高くなる。Ｃｈｅｏｎ解析法でループになる確率を１とすると、実施例１ではループになる確率が２ｍとなる。また、実施例１では、計算量が増加し、２ｍ×２×（（ｒ−１）／２ｍ）１／４となる。なお、図１５の各項目の下段は、有限体ＧＦ（３１２７）の場合を示す。例えば、有限体ＧＦ（３１２７）においては、実施例１のループになる確率は、従来技術の２５４倍となる。また、計算量は従来技術では２２０．５となるが、実施例１では２２１．５となる。また、計算時に記憶されるデータ量は、従来技術では２２０．５だが、実施例１では２１６．５となる。
【０１１３】
本実施例２では、ＲＷ関数において、生成される擬似乱数の値の範囲の最大値を（ｒ−１）／２ｍｄにして、既に選択された代表点を含む集合とは異なる集合に属する点を算出するようにした。このため、図１５に示すように、実施例１では、ループになる確率は１となった。また、実施例１では、計算量は２×（（ｒ−１）／２ｍ）１／４となった。よって、実施例１と比較すると、本実施例２では、計算量およびループになる確率が減少する。例えば、有限体ＧＦ（３１２７）においては、本実施例２では、計算量が２１７．５となる。
【０１１４】
ところで、上記の各実施例１，２では、代表点Ｐ＊ｒｅｐｄｉが選択されるごとに、テーブル１４１に登録された複数の代表点Ｐ＊ｒｅｐｉの各々と、１つの代表点Ｐ＊ｒｅｐｄｉとを比較して一致する代表点を検出する例について説明した。しかしながら、実施例はこれに限られない。例えば、複数の代表点Ｐ＊ｒｅｐｄｉを求めてテーブル１４２に登録しておき、テーブル１４１に登録された複数の代表点Ｐ＊ｒｅｐｉの各々と、テーブル１４１に登録された複数の代表点Ｐ＊ｒｅｐｄｉの各々とを比較するようにしてもよい。
【０１１５】
また、上記の各実施例１，２では、点Ｐと点（ｋｄ×Ｐ）とを開始点として、比較対象となる代表点Ｐ＊ｒｅｐｉおよび代表点Ｐ＊ｒｅｐｄｉを求める例について説明した。しかしながら、実施例はこれに限られない。例えば、点Ｐおよび点（ｋｄ×Ｐ）に加えて、点Ｐおよび点（ｋｄ×Ｐ）とは異なる楕円曲線Ｅ上の点、例えば、点（ｋｇ×Ｐ）（g∈Ｎ、２≦ｇ≦（ｄ−１））を開始点として、同様の処理によって代表点Ｇ＊ｒｅｐｉを求めてもよい。この場合、代表点Ｇ＊ｒｅｐｉを登録するためのテーブルが新たに設けられる。そして、代表点Ｐ＊ｒｅｐｉと代表点Ｐ＊ｒｅｐｄｉとを比較することに加えて、代表点Ｇ＊ｒｅｐｉと代表点Ｐ＊ｒｅｐｄｉとを比較し、代表点Ｇ＊ｒｅｐｉと代表点Ｐ＊ｒｅｐｄｉとを比較する。そして、一致する代表点を検出する。
【０１１６】
また、点Ｐおよび点（ｋｄ×Ｐ）に加えて、楕円曲線Ｅ上の複数の点（ｋｇ×Ｐ）を開始点として、各開始点に対応する代表点を求めるようにしてもよい。この場合、各開始点に対応する代表点ごとに、当該代表点を登録するためのテーブルが設けられる。この場合、各代表点を比較して、一致する代表点を検出する。
【０１１７】
また、複数台のコンピュータの各々で、代表点をテーブルに登録する処理を並行に行うことで、処理の高速化を図ってもよい。
【０１１８】
［暗号鍵解読プログラム］
また、上記の各実施例で説明した暗号鍵解読装置１００、２００の各種の処理は、あらかじめ用意されたプログラムをパーソナルコンピュータやワークステーションなどのコンピュータシステムで実行することによって実現することもできる。そこで、以下では、図１６を用いて、上記の実施例で説明した暗号鍵解読装置１００、２００と同様の機能を有する暗号鍵解読プログラムを実行するコンピュータの一例を説明する。図１６は、暗号鍵解読プログラムを実行するコンピュータを示す図である。
【０１１９】
同図に示すように、暗号鍵解読装置１００、２００としてコンピュータ３００は、入出力制御部３１０、ＨＤＤ（Ｈａｒｄ Ｄｉｓｋ Ｄｒｉｖｅ）３２０、ＲＡＭ（Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ）３３０およびＣＰＵ（Ｃｅｎｔｒａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）３４０をバス４００で接続して構成される。
【０１２０】
ここで、入出力制御部３１０は、各種情報の入出力を制御する。ＨＤＤ３２０は、ＣＰＵ３４０による各種処理の実行に必要な情報を記憶する。ＲＡＭ３３０は、各種情報を一時的に記憶する。ＣＰＵ３４０は、各種演算処理を実行する。
【０１２１】
そして、ＨＤＤ３２０には、暗号鍵解読システムデータがあらかじめ記憶されている。係る暗号鍵解読システムデータは、図７や図１２に示した暗号鍵解読装置１００、２００の各処理部と同様の機能を発揮する暗号鍵解読プログラムを含む。また、暗号鍵解読システムデータは、処理に必要な各種パラメータを含む暗号鍵解読用データを含む。なお、この暗号鍵解読システムデータを適宜分散させて、ネットワークを介して通信可能に接続された他のコンピュータの記憶部に記憶させておくこともできる。
【０１２２】
そして、ＣＰＵ３４０が、この暗号鍵解読システムデータをＨＤＤ３２０から読み出してＲＡＭ３３０に展開することにより、暗号鍵解読システムデータは暗号鍵解読システムとして機能するようになる。係る暗号鍵解読システムには暗号鍵解読プロセスが含まれる。
【０１２３】
すなわち、暗号鍵解読システムやそれに搭載された暗号鍵解読プロセスは、暗号鍵解読用データをＨＤＤ３２０から読み出して、ＲＡＭ３３０において自身に割り当てられた領域に展開し、この展開したデータ等に基づいて各種処理を実行する。
【０１２４】
なお、暗号鍵解読システム及び暗号鍵解読プロセスは、図７や図１２に示した各機能部（例えば、パラメータ取得部１３１、テーブル生成部１３２，２３２、テーブル比較部１３３、ＤＬＰ計算部１３４）において実行される処理に対応する。
【０１２５】
なお、上記した暗号鍵解読プログラムについては、必ずしも最初からＨＤＤ３２０に記憶させておく必要はない。
【０１２６】
例えば、コンピュータ３００に挿入されるフレキシブルディスク（ＦＤ）、ＣＤ−ＲＯＭ、ＤＶＤディスク、光磁気ディスク、ＩＣカードなどの「可搬用の物理媒体」に各プログラムを記憶させておく。そして、コンピュータ３００がこれらから各プログラムを読み出して実行するようにしてもよい。
【０１２７】
さらには、公衆回線、インターネット、ＬＡＮ、ＷＡＮなどを介してコンピュータ３００に接続される「他のコンピュータ（またはサーバ）」などに各プログラムを記憶させておく。そして、コンピュータ３００がこれらから各プログラムを読み出して実行するようにしてもよい。
【０１２８】
また、本実施例において説明した各処理のうち、自動的に行われるものとして説明した処理の全部または一部を手動的に行うこともできる。また、本実施例において説明した各処理のうち、手動的に行われるものとして説明した処理の全部または一部を公知の方法で自動的に行うこともできる。例えば、図９、図１４の解の計算処理において、当該処理を実行する指示が手動で入力された場合に、ステップＳ１０１以降の処理が開始されたが、自動的にステップＳ１０１以降の処理を開始してもよい。
【０１２９】
また、図示した各装置の各構成要素は機能概念的なものであり、必ずしも物理的に図示の如く構成されていることを要しない。すなわち、各装置の分散・統合の具体的状態は図示のものに限られず、その全部または一部を、各種の負荷や使用状況などに応じて、任意の単位で機能的または物理的に分散・統合して構成することができる。例えば、図７に示すテーブル生成部１３２とテーブル比較部１３３とが統合されてもよい。また、テーブル比較部１３３とＤＬＰ計算部１３４とが統合されてもよい。また、図１２に示すテーブル生成部２３２とテーブル比較部１３３とが統合されてもよい。
【０１３０】
また、テーブル生成部１３２は、以下の機能を有している。すなわち、テーブル生成部１３２は、入力されたシステムパラメータに基づいて、楕円曲線Ｅ上の点Ｐに対して自己同型写像を適用して点の集合を算出する機能を有している。また、テーブル生成部１３２は、算出された集合の中から第１の代表点を選択して記憶部１４０に記憶させる機能を有している。さらに、テーブル生成部１３２は、第１の代表点に対して擬似乱数を用いて楕円曲線Ｅ上の点を算出する機能を有している。これらの各機能を分散して構成するようにしてもよい。
【０１３１】
また、テーブル生成部１３２は、楕円曲線Ｅ上において点（ｋｄ×Ｐ）に対して自己同型写像を適用して点の集合を算出する機能を有している。テーブル生成部１３２は、算出された集合の中から第２の代表点を選択して記憶部１４０に記憶させる機能を有している。テーブル生成部１３２は、第２の代表点に対して擬似乱数を用いて楕円曲線Ｅ上の点を算出する機能を有している。これらの各機能についても、分散して構成するようにしてもよい。同様に、テーブル生成部２３２についても各機能を分散して構成するようにしてもよい。
【符号の説明】
【０１３２】
１００、２００ 暗号鍵解読装置
１１０ 入力部
１２０ 出力部
１３０、２３０ 処理部
１４０ 記憶部
１３１ パラメータ取得部
１３２、２３２ テーブル生成部
１３３ テーブル比較部
１３４ ＤＬＰ計算部
１３５ 制御部
【特許請求の範囲】
【請求項１】
コンピュータが、
楕円曲線上の所定の点に対して自己同型写像を適用して第１の点の集合を算出し、前記第１の点の集合の中から代表点を選択して記憶部に記憶させ、前記記憶部に記憶された第１の点の集合に関する代表点に対して擬似乱数を用いて前記楕円曲線上の点を算出し、当該点に対して前記自己同型写像を適用することで、前記第１の点の集合に関する新たな代表点を選択して前記記憶部に追加して記憶させる第１の代表点選択ステップと、
前記楕円曲線上において所定の暗号鍵から定まる点に対して前記自己同型写像を適用して第２の点の集合を算出し、前記第２の点の集合の中から代表点を選択して記憶部に記憶させ、前記記憶部に記憶された第２の点の集合に関する代表点に対して擬似乱数を用いて前記楕円曲線上の点を算出し、当該点に対して前記自己同型写像を適用することで、前記第２の点の集合に関する新たな代表点を選択して前記記憶部に追加して記憶させる第２の代表点選択ステップと、
前記記憶部に記憶された第１の点の集合に関する代表点と第２の点の集合に関する代表点とを比較し、一致した代表点に基づいて前記暗号鍵を算出する暗号鍵算出ステップと
を実行することを特徴とする暗号鍵解析方法。
【請求項２】
前記第１および第２の代表点選択ステップは、前記擬似乱数を用いて前記楕円曲線上の点を算出する場合に、既に選択された代表点を含む集合とは異なる集合に属する点を算出するように、当該算出に用いる前記擬似乱数を生成することを特徴とする請求項１に記載の暗号鍵解析方法。
【請求項３】
前記第１および第２の代表点選択ステップは、前記擬似乱数として、以下の式（１）に示す範囲内である擬似乱数を生成することを特徴とする請求項２に記載の暗号鍵解析方法。
【数１】
ただし、Ｗは擬似乱数の値であり、ｍは楕円曲線暗号における拡大次数であり、ｄは（ｒ−１）の約数である。
【請求項４】
楕円曲線上の所定の点に対して自己同型写像を適用して第１の点の集合を算出する第１の写像計算部と、
前記第１の写像計算部によって算出された前記第１の点の集合の中から代表点を選択して記憶部に記憶させる第１の代表点選択部と、
前記第１の代表点選択部によって前記記憶部に記憶された前記第１の点の集合に関する代表点に対して擬似乱数を用いて前記楕円曲線上の点を算出する第１の乱数部と、
前記第１の乱数部で算出された点に対して前記自己同型写像を適用して新たな第１の点の集合を算出するように前記第１の写像計算部を制御し、新たな第１の点の集合の中から新たな代表点を選択して前記記憶部に追加して記憶させるように前記第１の代表点選択部を制御し、新たな代表点に対して擬似乱数を用いて前記楕円曲線上の新たな点を算出するように前記第１の乱数部を制御することを複数回行って、複数の前記第１の点の集合に関する複数の代表点を前記記憶部に記憶させる第１の制御部と、
前記楕円曲線上において所定の暗号鍵から定まる点に対して前記自己同型写像を適用して第２の点の集合を算出する第２の写像計算部と、
前記第２の写像計算部によって算出された前記第２の点の集合の中から代表点を選択して記憶部に記憶させる第２の代表点選択部と、
前記第２の代表点選択部によって選択された前記第２の点の集合に関する代表点に対して擬似乱数を用いて前記楕円曲線上の点を算出する第２の乱数部と、
前記記憶部に記憶された複数の前記第１の点の集合に関する複数の代表点の各々と、前記第２の代表点選択部によって前記記憶部に記憶された前記第２の点の集合に関する代表点とを比較し、前記第２の点の集合に関する代表点に一致する前記第１の点の集合に関する代表点がない場合には、今回記憶された第２の点の集合に関する代表点に対して前記擬似乱数を用いて前記楕円曲線上の新たな点を算出するように前記第２の乱数部を制御し、算出された新たな点に対して前記自己同型写像を適用して新たな第２の点の集合を算出するように前記第２の写像計算部を制御し、新たな第２の点の集合の中から新たな代表点を選択して前記記憶部に追加して記憶させるように前記第２の代表点選択部を制御し、複数の前記第１の点の集合に関する複数の代表点の各々と、新たな前記第２の点の集合に関する代表点とを比較することを、新たな前記第２の点の集合に関する代表点が複数の前記第１の点の集合に関する複数の代表点の少なくとも一つに一致するまで繰り返し行う第２の制御部と、
一致した代表点に基づいて前記暗号鍵を算出する暗号鍵算出部と
を備えることを特徴とする暗号鍵解析装置。
【請求項５】
楕円曲線上の所定の点に対して自己同型写像を適用して第１の点の集合を算出し、前記第１の点の集合の中から代表点を選択して記憶部に記憶させ、前記記憶部に記憶された第１の点の集合に関する代表点に対して擬似乱数を用いて前記楕円曲線上の点を算出し、当該点に対して前記自己同型写像を適用することで、前記第１の点の集合に関する新たな代表点を選択して前記記憶部に追加して記憶させる第１の代表点選択手順と、
前記楕円曲線上において所定の暗号鍵から定まる点に対して前記自己同型写像を適用して第２の点の集合を算出し、前記第２の点の集合の中から代表点を選択して記憶部に記憶させ、前記記憶部に記憶された第２の点の集合に関する代表点に対して擬似乱数を用いて前記楕円曲線上の点を算出し、当該点に対して前記自己同型写像を適用することで、前記第２の点の集合に関する新たな代表点を選択して前記記憶部に追加して記憶させる第２の代表点選択手順と、
前記記憶部に記憶された第１の点の集合に関する代表点と第２の点の集合に関する代表点とを比較し、一致した代表点に基づいて前記暗号鍵を算出する暗号鍵算出手順と
をコンピュータに実行させることを特徴とする暗号鍵解析プログラム。
【請求項１】
コンピュータが、
楕円曲線上の所定の点に対して自己同型写像を適用して第１の点の集合を算出し、前記第１の点の集合の中から代表点を選択して記憶部に記憶させ、前記記憶部に記憶された第１の点の集合に関する代表点に対して擬似乱数を用いて前記楕円曲線上の点を算出し、当該点に対して前記自己同型写像を適用することで、前記第１の点の集合に関する新たな代表点を選択して前記記憶部に追加して記憶させる第１の代表点選択ステップと、
前記楕円曲線上において所定の暗号鍵から定まる点に対して前記自己同型写像を適用して第２の点の集合を算出し、前記第２の点の集合の中から代表点を選択して記憶部に記憶させ、前記記憶部に記憶された第２の点の集合に関する代表点に対して擬似乱数を用いて前記楕円曲線上の点を算出し、当該点に対して前記自己同型写像を適用することで、前記第２の点の集合に関する新たな代表点を選択して前記記憶部に追加して記憶させる第２の代表点選択ステップと、
前記記憶部に記憶された第１の点の集合に関する代表点と第２の点の集合に関する代表点とを比較し、一致した代表点に基づいて前記暗号鍵を算出する暗号鍵算出ステップと
を実行することを特徴とする暗号鍵解析方法。
【請求項２】
前記第１および第２の代表点選択ステップは、前記擬似乱数を用いて前記楕円曲線上の点を算出する場合に、既に選択された代表点を含む集合とは異なる集合に属する点を算出するように、当該算出に用いる前記擬似乱数を生成することを特徴とする請求項１に記載の暗号鍵解析方法。
【請求項３】
前記第１および第２の代表点選択ステップは、前記擬似乱数として、以下の式（１）に示す範囲内である擬似乱数を生成することを特徴とする請求項２に記載の暗号鍵解析方法。
【数１】
ただし、Ｗは擬似乱数の値であり、ｍは楕円曲線暗号における拡大次数であり、ｄは（ｒ−１）の約数である。
【請求項４】
楕円曲線上の所定の点に対して自己同型写像を適用して第１の点の集合を算出する第１の写像計算部と、
前記第１の写像計算部によって算出された前記第１の点の集合の中から代表点を選択して記憶部に記憶させる第１の代表点選択部と、
前記第１の代表点選択部によって前記記憶部に記憶された前記第１の点の集合に関する代表点に対して擬似乱数を用いて前記楕円曲線上の点を算出する第１の乱数部と、
前記第１の乱数部で算出された点に対して前記自己同型写像を適用して新たな第１の点の集合を算出するように前記第１の写像計算部を制御し、新たな第１の点の集合の中から新たな代表点を選択して前記記憶部に追加して記憶させるように前記第１の代表点選択部を制御し、新たな代表点に対して擬似乱数を用いて前記楕円曲線上の新たな点を算出するように前記第１の乱数部を制御することを複数回行って、複数の前記第１の点の集合に関する複数の代表点を前記記憶部に記憶させる第１の制御部と、
前記楕円曲線上において所定の暗号鍵から定まる点に対して前記自己同型写像を適用して第２の点の集合を算出する第２の写像計算部と、
前記第２の写像計算部によって算出された前記第２の点の集合の中から代表点を選択して記憶部に記憶させる第２の代表点選択部と、
前記第２の代表点選択部によって選択された前記第２の点の集合に関する代表点に対して擬似乱数を用いて前記楕円曲線上の点を算出する第２の乱数部と、
前記記憶部に記憶された複数の前記第１の点の集合に関する複数の代表点の各々と、前記第２の代表点選択部によって前記記憶部に記憶された前記第２の点の集合に関する代表点とを比較し、前記第２の点の集合に関する代表点に一致する前記第１の点の集合に関する代表点がない場合には、今回記憶された第２の点の集合に関する代表点に対して前記擬似乱数を用いて前記楕円曲線上の新たな点を算出するように前記第２の乱数部を制御し、算出された新たな点に対して前記自己同型写像を適用して新たな第２の点の集合を算出するように前記第２の写像計算部を制御し、新たな第２の点の集合の中から新たな代表点を選択して前記記憶部に追加して記憶させるように前記第２の代表点選択部を制御し、複数の前記第１の点の集合に関する複数の代表点の各々と、新たな前記第２の点の集合に関する代表点とを比較することを、新たな前記第２の点の集合に関する代表点が複数の前記第１の点の集合に関する複数の代表点の少なくとも一つに一致するまで繰り返し行う第２の制御部と、
一致した代表点に基づいて前記暗号鍵を算出する暗号鍵算出部と
を備えることを特徴とする暗号鍵解析装置。
【請求項５】
楕円曲線上の所定の点に対して自己同型写像を適用して第１の点の集合を算出し、前記第１の点の集合の中から代表点を選択して記憶部に記憶させ、前記記憶部に記憶された第１の点の集合に関する代表点に対して擬似乱数を用いて前記楕円曲線上の点を算出し、当該点に対して前記自己同型写像を適用することで、前記第１の点の集合に関する新たな代表点を選択して前記記憶部に追加して記憶させる第１の代表点選択手順と、
前記楕円曲線上において所定の暗号鍵から定まる点に対して前記自己同型写像を適用して第２の点の集合を算出し、前記第２の点の集合の中から代表点を選択して記憶部に記憶させ、前記記憶部に記憶された第２の点の集合に関する代表点に対して擬似乱数を用いて前記楕円曲線上の点を算出し、当該点に対して前記自己同型写像を適用することで、前記第２の点の集合に関する新たな代表点を選択して前記記憶部に追加して記憶させる第２の代表点選択手順と、
前記記憶部に記憶された第１の点の集合に関する代表点と第２の点の集合に関する代表点とを比較し、一致した代表点に基づいて前記暗号鍵を算出する暗号鍵算出手順と
をコンピュータに実行させることを特徴とする暗号鍵解析プログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【公開番号】特開２０１２−１００３９（Ｐ２０１２−１００３９Ａ）
【公開日】平成２４年１月１２日（２０１２．１．１２）
【国際特許分類】
【出願番号】特願２０１０−１４３１８９（Ｐ２０１０−１４３１８９）
【出願日】平成２２年６月２３日（２０１０．６．２３）
【国等の委託研究の成果に係る記載事項】（出願人による申告）平成２０年度、独立行政法人情報通信研究機構、「適切な暗号技術を選択可能とするための新しい暗号技術の評価手法 〜暗号の技術評価に関する研究開発〜」委託研究、産業技術力強化法第１９条の適用を受ける特許出願
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【Ｆターム（参考）】
【公開日】平成２４年１月１２日（２０１２．１．１２）
【国際特許分類】
【出願日】平成２２年６月２３日（２０１０．６．２３）
【国等の委託研究の成果に係る記載事項】（出願人による申告）平成２０年度、独立行政法人情報通信研究機構、「適切な暗号技術を選択可能とするための新しい暗号技術の評価手法 〜暗号の技術評価に関する研究開発〜」委託研究、産業技術力強化法第１９条の適用を受ける特許出願
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【Ｆターム（参考）】
[ Back to top ]