暗号鍵解読方法、暗号鍵解読装置および暗号鍵解読プログラム
【課題】離散対数問題に基づく公開鍵暗号のＰｏｌｌａｒｄのρ法による解読にかかる計算量を削減する。
【解決手段】暗号鍵解読装置２００は、点列生成処理部１４１と、判定処理部２４２とを有する。点列生成処理部１４１は、点に対して写像を実行し、写像の実行結果となる点に対して再度写像を実行する処理を繰り返し実行することで複数の点を生成する。また、点列生成処理部１４１は、生成した点が所定の特徴を有する特徴点であるか否かを判定する。判定処理部２４２は、点列生成処理部１４１において生成された点のうち、特徴点でないと判定した点を判定点として記憶装置に記憶する。また、判定処理部２４２は、点列生成処理部１４１によって生成された点と前記記憶装置に記憶された判定点とを比較して、生成された点と判定点とが一致した場合に、特徴点同士の衝突が起こらないと判定して演算を中断し、別の初期点から演算を再開する。
【解決手段】暗号鍵解読装置２００は、点列生成処理部１４１と、判定処理部２４２とを有する。点列生成処理部１４１は、点に対して写像を実行し、写像の実行結果となる点に対して再度写像を実行する処理を繰り返し実行することで複数の点を生成する。また、点列生成処理部１４１は、生成した点が所定の特徴を有する特徴点であるか否かを判定する。判定処理部２４２は、点列生成処理部１４１において生成された点のうち、特徴点でないと判定した点を判定点として記憶装置に記憶する。また、判定処理部２４２は、点列生成処理部１４１によって生成された点と前記記憶装置に記憶された判定点とを比較して、生成された点と判定点とが一致した場合に、特徴点同士の衝突が起こらないと判定して演算を中断し、別の初期点から演算を再開する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号鍵解読方法、暗号鍵解読装置および暗号鍵解読プログラムに関する。
【背景技術】
【０００２】
従来、情報通信において情報を保護するために用いられる暗号化方式の一つとして、公開鍵暗号が存在する。公開鍵暗号は、情報を暗号化するための公開鍵と、公開鍵により暗号化された情報を復号化するための秘密鍵とで一対の異なる鍵を用いる暗号方式である。公開鍵暗号では、送信者は、受信者が公開している公開鍵で情報を暗号化して送信し、受信者は、暗号化された情報を自分だけが保持している秘密鍵で復号する。
【０００３】
公開鍵暗号は、公開鍵から秘密鍵が解読されないようにするために、数学的に難しいとされる問題に基づいて設計される。例えば、公開鍵暗号には、ＥｌＧａｍａｌ暗号や楕円曲線暗号のように、計算量的に解読が困難である離散対数問題に基づいて設計されるものが存在する。離散対数問題とは、素数ｐに対して有限体ＧＦ（ｐ）の生成元αを固定し、有限体ＧＦ（ｐ）の元βに対してβ＝αｘを満たす整数ｘを求めるという問題である。
【０００４】
公開鍵暗号により情報を保護するためには、現状および今後の計算機能力を見積もり、容易に解読できないような計算量になるようにパラメータを設計する必要がある。このため、公開鍵暗号を実際に解読し、解読にかかる計算量を評価する方法が存在する。例えば、上記の離散対数問題に基づく公開鍵暗号を解読する方法として、Pollardのρ法がある。このPollardのρ法は、所定の点に対して写像を適用して新たな点を生成し、生成した点に対して写像を更に適用することで、点の生成を繰り返す。そして、Pollardのρ法は、生成した複数の点のうち２点が一致する場合に得られる関係式を用いることで、離散対数問題を解く方法である。
【０００５】
ここで、Pollardのρ法について説明する。図１１および図１２は、従来のPollardのρ法を説明するための図である。図１１に示すように、Pollardのρ法では、まず、初期点Ｐ０が生成される。続いて、点Ｐｉ−１から点Ｐｉへの写像Ｆを用いて、点Ｐ１，点Ｐ２，点Ｐ３・・・のように点Ｐｉが生成される。生成された点Ｐｉは、図１２に示すように、メモリに記憶される。なお、写像Ｆは、下記の式（１）によって示され、下記の式（２）が成り立つｕｉおよびｖｉを一意に算出できる写像である。
【０００６】
Ｐｉ＝Ｆ（Ｐｉ−１）・・・（１）
【０００７】
Ｐｉ＝α＾｛ｕｉ｝＊β＾｛ｖｉ｝・・・（２）
【０００８】
続いて、点Ｐｊがメモリに新たに記憶されるごとに、点Ｐｊが既に記憶された点Ｐ１〜点Ｐｊ−１のいずれかと一致するか否かが判定される。点Ｐｊが既に記憶された点Ｐ１〜点Ｐｊ−１のいずれかと一致する場合には、２つの点の一致を衝突として検出する。すなわち、点Ｐｊと点Ｐｉとが衝突する場合には、下記の式（３）が成り立つ。
【０００９】
Ｐｉ＝Ｐｊ・・・（３）
【００１０】
続いて、点Ｐｉの式（２）および２点の衝突によって得られる式（３）から、下記の式（４）が導かれる。式（４）に離散対数問題の条件式β＝αｘをあてはめると、下記の式（５）が導かれる。そして、式（５）にｕｉ，ｖｉ，ｕｊ，ｖｊを代入することで、秘密鍵ｘが算出される。なお、秘密鍵ｘが算出されるのは、ｖｉ≠ｖｊが成り立つ場合である。
【００１１】
α＾｛ｕｉ｝＊β＾｛ｖｉ｝＝α＾｛ｕｊ｝＊β＾｛ｖｊ｝・・・（４）
【００１２】
ｘ＝（ｕｉ−ｕｊ）／（ｖｊ−ｖｉ）・・・（５）
【００１３】
しかし、Pollardのρ法を用いて公開鍵暗号の解読を実行すると、多数の点Ｐｉが生成され、生成された点Ｐｉを記憶するためのメモリ使用量が膨大になってしまうという問題があった。このメモリ使用量を削減する技術として、特徴点（distinguished point）を導入したρ法が存在する。この方法は、生成された点Ｐｉのうち、数値に特徴を有する特徴点のみを記憶することで、メモリ使用量を削減する方法である。
【００１４】
ここで、特徴点を導入したρ法について説明する。図１３は、従来の特徴点を導入したρ法を説明するための図である。図１３に示す例では、点Ｐｉの数値の下位２桁が００である点を特徴点として設定した場合を説明する。図１３に示す白丸印は特徴点を示し、黒丸印は特徴点でない点を示す。特徴点を導入したρ法では、生成された全ての点Ｐｉを記憶するのではなく、特徴点のみをメモリに記憶する。衝突の検出はメモリ上で行われるので、図１３に示すように、特徴点でない点Ｐ１０と点Ｐ２８とが一致していたとしても、この一致は衝突として検出されない。しかし、写像Ｆは一意の写像であるので、同一の点からの写像は常に一致する。つまり、点Ｐ２８が点Ｐ１０と一致した場合には、次の点Ｐ２９は点Ｐ１１と一致する。さらに、次々に生成される点Ｐ３０，点Ｐ３１，点Ｐ３２・・・は、点Ｐ１２，点Ｐ１３，点Ｐ１４・・・とそれぞれ一致する。このように、新たな点が既に生成された点のいずれかと一致すると、同一の点が生成され続けるループが形成される。このため、このループ上に特徴点が含まれる場合には、衝突が検出される。図１３に示す例では、ループ上に点Ｐ１７，点Ｐ２９の２点が含まれるので、点Ｐ３５が生成された時点で、点Ｐ１７と点Ｐ３５との衝突が検出される。このように、特徴点を導入したρ法では、解読にかかる計算量は増加するものの、メモリ使用量は削減される。
【先行技術文献】
【特許文献】
【００１５】
【特許文献１】特開２００８−２０６５３号公報
【発明の概要】
【発明が解決しようとする課題】
【００１６】
しかしながら、上記従来技術では、特徴点のみを記憶するので、メモリ使用量を低減できるものの、解が算出されない場合があった。このため、解が算出されないにもかかわらず、演算処理が継続されてしまい、解読にかかる計算量が膨大になっていた。
【００１７】
図１４および図１５を用いて、解が算出されない場合について説明する。図１４および図１５は、従来技術の問題を説明するための図である。図１４および図１５に示す白丸印は特徴点を示し、黒丸印は特徴点でない点を示す。
【００１８】
図１４に示す例では、特徴点を含まないループが発生した場合を説明する。図１４に示すように、ループが形成されると、写像Ｆを繰り返し実行したとしても、周期的に同じ点が生成されてしまう。このため、ループ上に特徴点が含まれていなければ、特徴点でない点が生成され続けるため、特徴点の衝突を検出することができず、解を算出することができない。
【００１９】
図１５に示す例では、自明な衝突が発生した場合を説明する。この自明な衝突とは、２点Ｐｉ，Ｐｊが衝突した場合に、衝突した２点の係数ｕｉ，ｖｉ，ｕｊ，ｖｊが等しくなることである。つまり、自明な衝突が発生すると、Ｐｉ＝Ｐｊ，ｕｉ＝ｕｊ，ｖｉ＝ｖｊが成り立つ。図１５に示すように、自明な衝突が発生した場合には、写像Ｆの演算処理を繰り返したとしても、２点間の写像を繰り返すのみである。このため、この２点がいずれも特徴点でなければ、特徴点の衝突を検出することができず、解を算出することができない。また、仮に、この２点のいずれかが特徴点であったとしても、ｖｉ＝ｖｊを満たすので、上記の式（５）を用いても解を算出することができない。
【００２０】
開示の技術は、上記に鑑みてなされたものであって、解読にかかる計算量を削減することができる暗号鍵解読方法、暗号鍵解読装置および暗号鍵解読プログラムを提供することを目的とする。
【課題を解決するための手段】
【００２１】
本願の開示する技術は、一つの態様において、コンピュータが、点生成ステップと、判定点記憶ステップと、判定ステップとを実行することを要件とする。点生成ステップは、点に対して写像を実行し、写像の実行結果となる点に対して再度写像を実行する処理を繰り返し実行することで複数の点を生成する。判定点記憶ステップは、点生成ステップによって生成された点が、所定の特徴を有する特徴点であるか否かを判定し、特徴点でないと判定した点を判定点として記憶装置に記憶する。判定ステップは、点生成ステップによって生成された点と記憶装置に記憶された判定点とを比較して、点と判定点とが一致した場合に、特徴点同士の衝突が起こらないと判定する。
【発明の効果】
【００２２】
本願の開示する技術の一つの態様によれば、解読にかかる計算量を削減することができるという効果を奏する。
【図面の簡単な説明】
【００２３】
【図１】図１は、本実施例１にかかる暗号鍵解読装置の構成を示す図である。
【図２】図２は、点列データのデータ構造の一例を示す図である。
【図３】図３は、本実施例１にかかる暗号鍵解読装置の処理手順を示すフローチャートである。
【図４】図４は、演算処理回数に閾値を設定する根拠を説明するための図である。
【図５】図５は、本実施例２にかかる暗号鍵解読装置の構成を示す図である。
【図６】図６は、本実施例２にかかる暗号鍵解読装置の処理手順を示すフローチャートである。
【図７】図７は、本実施例３にかかる暗号鍵解読装置の構成を示す図である。
【図８】図８は、本実施例３にかかる暗号鍵解読装置の処理手順を示すフローチャートである。
【図９】図９は、本実施例１〜３にかかる暗号鍵解読装置の効果を比較して説明するための図である。
【図１０】図１０は、本実施例にかかる暗号鍵解読装置を構成するコンピュータのハードウェア構成を示す図である。
【図１１】図１１は、従来のPollardのρ法を説明するための図である。
【図１２】図１２は、従来のPollardのρ法を説明するための図である。
【図１３】図１３は、従来の特徴点を導入したρ法を説明するための図である。
【図１４】図１４は、従来技術の問題を説明するための図である。
【図１５】図１５は、従来技術の問題を説明するための図である。
【発明を実施するための形態】
【００２４】
以下に、本願の開示する暗号鍵解読方法、暗号鍵解読装置および暗号鍵解読プログラムの実施例を図面に基づいて詳細に説明する。なお、この実施例によりこの発明が限定されるものではない。各実施例は、処理内容を矛盾させない範囲で適宜組み合わせることが可能である。
【実施例１】
【００２５】
本実施例１にかかる暗号鍵解読装置の構成の一例について説明する。図１は、本実施例１にかかる暗号鍵解読装置の構成を示す図である。図１に示すように、この暗号鍵解読装置１００は、入力部１１０、出力部１２０、記憶部１３０、制御部１４０を有する。
【００２６】
入力部１１０は、各種情報の入力を受け付ける入力装置である。例えば、入力部１１０は、パラメータ（ｐ，α，β）の入力や秘密鍵ｘを算出する命令の入力を受け付ける。入力部１１０は、キーボードやマウスなどに対応する装置である。出力部１２０は、各種情報を出力する出力装置である。例えば、出力部１２０は、後述する解算出処理部１４４から受け付けた秘密鍵ｘを出力する。出力部１２０は、ディスプレイやモニタなどに対応する装置である。
【００２７】
記憶部１３０は、点列データ１３１を有する。この点列データ１３１は、ｉと、Ｑｉと、ｕｉと、ｖｉとを対応付けて記憶する。このうち、ｉは、インデックスであり、１以上の整数である。また、Ｑｉは、Ｑｉ−１を写像した値であり、ｕｉ、ｖｉは、Ｑｉの係数である。
【００２８】
図２は、点列データのデータ構造の一例を示す図である。図２に示すように、例えば、点列データ１３１は、ｉ＝３と、Ｑｉ＝１７１００と、ｕｉ＝１９と、ｖｉ＝６とを対応付けて記憶する。また、点列データ１３１は、ｉ＝１７と、Ｑｉ＝４５００と、ｕｉ＝４４と、ｖｉ＝３とを対応付けて記憶する。また、点列データ１３１は、ｉ＝２９と、Ｑｉ＝４３００と、ｕｉ＝２６と、ｖｉ＝５とを対応付けて記憶する。また、点列データ１３１は、ｉ＝３５と、Ｑｉ＝４５００と、ｕｉ＝８と、ｖｉ＝６９とを対応付けて記憶する。
【００２９】
制御部１４０は、点列生成処理部１４１、判定処理部１４２、衝突検知処理部１４３、解算出処理部１４４を有する。
【００３０】
点列生成処理部１４１は、所定の点に対して写像を適用して新たな点を生成し、生成した点に対して写像を更に適用することで、点の生成を繰り返す。そして、点列生成処理部１４１は、点を生成する度に、生成した点が数値に所定の特徴を有する特徴点であるか否かを判定し、特徴点であると判定された点の情報を点列データ１３１に格納する処理部である。
【００３１】
以下において、点列生成処理部１４１の処理について具体的に説明する。例えば、点列生成処理部１４１は、入力部１１０を介して受け付けたパラメータ（ｐ，α，β）と下記の式（６）とを用いて、初期点Ｐ０を算出する。なお、例えば、式（６）のｕ０は、ランダムに選択される初期値である。また、例えば、ｖ０は、０である。
【００３２】
Ｐ０＝α＾｛ｕ０｝＊β＾｛ｖ０｝・・・（６）
【００３３】
続いて、点列生成処理部１４１は、初期点Ｐ０をＱ０と設定し、下記の式（７）を用いて、点Ｑｉを算出する。なお、式（７）のＦは、点Ｑｉ−１から点Ｑｉへの写像であり、下記の式（８）が成り立つｕｉおよびｖｉを一意に算出できる写像である。また、式（７）のｉは、インデックスであり、写像Ｆの演算処理回数に対応する。つまり、ｉは、点Ｑｉが写像される度に、１インクリメントされる。
【００３４】
Ｑｉ＝Ｆ（Ｑｉ−１）・・・（７）
【００３５】
Ｑｉ＝α＾｛ｕｉ｝＊β＾｛ｖｉ｝・・・（８）
【００３６】
また、点列生成処理部１４１は、点Ｑｉを生成する度に、生成した点Ｑｉが数値に特徴を有する特徴点であるか否かを判定する。ここで、特徴点とは、例えば、点Ｑｉの数値の下位２桁が００である点を指す。点列生成処理部１４１は、点Ｑｉが特徴点であると判定された場合には、点Ｑｉの情報としてｉと、Ｑｉと、ｕｉと、ｖｉとを対応付けて点列データ１３１に格納する。例えば、点列生成処理部１４１は、点Ｑ３が特徴点であると判定された場合には、点Ｑ３の情報として、ｉ＝３と、Ｑｉ＝１７１００と、ｕｉ＝１９と、ｖｉ＝６とを対応付けて点列データ１３１に格納する。また、点列生成処理部１４１は、点Ｑｉが特徴点でないと判定された場合には、点Ｑｉの情報を判定処理部１４２に出力する。
【００３７】
判定処理部１４２は、点列生成処理部１４１による演算処理回数と所定の閾値とを比較し、演算処理回数が所定の閾値以上である場合に、解が算出されないと判定する処理部である。ここで、衝突とは、点列データ１３１に新たに格納された点が、点列データ１３１に既に記憶された点のいずれかと一致することを指す。
【００３８】
例えば、判定処理部１４２は、点Ｑｉの情報を点列生成処理部１４１から受け付けて、受け付けた点Ｑｉに対応するｉと所定の閾値とを比較する。判定処理部１４２は、ｉが所定の閾値以上である場合には、解が算出されないと判定し、出力部１２０にＮＧを出力する。これに対して、ｉが所定の閾値未満である場合には、判定処理部１４２は、次の点Ｑｉの情報を受け付けるまで待機する。ここで比較される閾値は、例えば、特徴点が出力される確率が最も高いｉの値を１０倍した値である。例えば、点Ｑｉの数値の下位２桁が００である点を特徴点とした場合には、閾値は１０００に設定される。
【００３９】
衝突検知処理部１４３は、衝突を探索する処理部である。例えば、衝突検知処理部１４３は、新たな特徴点が点列データ１３１に格納されるごとに、新たな特徴点が既に記憶された特徴点のいずれかと一致するか否かを判定する。衝突検知処理部１４３は、新たな特徴点が既に記憶された特徴点のいずれかと一致する場合には、２つの特徴点の一致を衝突として検出する。すなわち、２つの特徴点が衝突する場合には、下記の式（９）が成り立つ。なお、式（９）のｋは、衝突した２つの特徴点のｉの差分である。
【００４０】
Ｑｉ＝Ｑｉ＋ｋ・・・（９）
【００４１】
続いて、衝突検知処理部１４３は、衝突した２つの特徴点に対応するｕｉ，ｖｉ，ｕｉ＋ｋ，ｖｉ＋ｋを解算出処理部１４４に出力する。なお、衝突検知処理部１４３は、衝突を検出するまで衝突を探索する。
【００４２】
図２に示す例では、衝突検知処理部１４３は、特徴点Ｑ３５＝４５００が点列データ１３１に格納された時点で、特徴点Ｑ３５が既に記憶された特徴点のいずれかと一致するか否かを判定する。衝突検知処理部１４３は、特徴点Ｑ３５＝４５００が特徴点Ｑ１７＝４５００と一致するので、特徴点Ｑ３５と特徴点Ｑ１７の衝突を検出する。そして、衝突検知処理部１４３は、ｕ１７，ｖ１７，ｕ３５，ｖ３５の値を解算出処理部１４４に出力する。
【００４３】
解算出処理部１４４は、解を算出する処理部である。例えば、解算出処理部１４４は、衝突検知処理部１４３から受け付けたｕ１７，ｖ１７，ｕ３５，ｖ３５の値を用いて、秘密鍵ｘを算出する。
【００４４】
ここで、解算出処理部１４４が秘密鍵ｘを算出するために用いる式について説明する。まず、点Ｑｉの式（８）および２点の衝突によって得られる式（９）から、下記の式（１０）が導かれる。そして、式（１０）に離散対数問題の条件式β＝αｘをあてはめると、下記の式（１１）が導かれる。
【００４５】
α＾｛ｕｉ｝＊β＾｛ｖｉ｝＝α＾｛ｕｉ＋ｋ｝＊β＾｛ｖｉ＋ｋ｝・・・（１０）
【００４６】
ｘ＝（ｕｉ−ｕｉ＋ｋ）／（ｖｉ＋ｋ−ｖｉ）・・・（１１）
【００４７】
すなわち、解算出処理部１４４は、衝突検知処理部１４３から受け付けたｕｉ，ｖｉ，ｕｉ＋ｋ，ｖｉ＋ｋを式（１１）に代入することで、秘密鍵ｘを算出する。そして、解算出処理部１４４は、算出した秘密鍵ｘを出力部１２０に出力する。なお、解算出処理部１４４が秘密鍵ｘを算出するのは、ｖｉ≠ｖｉ＋ｋが成り立つ場合である。これに対して、ｖｉ＝ｖｉ＋ｋが成り立つ場合には、解算出処理部１４４は、秘密鍵ｘを算出できないので、出力部１２０にＮＧを出力する。
【００４８】
なお、解算出処理部１４４は、入力部１１０から秘密鍵ｘを算出する命令を受け付けた時間を取得し、取得した時間を用いて秘密鍵ｘが算出されるまでに要した演算時間を算出しても良い。そして、解算出処理部１４４は、算出した演算時間を出力部１２０に出力しても良い。
【００４９】
次に、本実施例１にかかる暗号鍵解読装置１００の処理手順について説明する。図３は、本実施例１にかかる暗号鍵解読装置の処理手順を示すフローチャートである。例えば、図３に示す処理は、暗号鍵解読装置１００が、入力部１１０を介して秘密鍵ｘを算出する命令を受け付けたことを契機として実行される。
【００５０】
図３に示すように、暗号鍵解読装置１００は、入力部１１０を介して受け付けたパラメータを用いて初期点Ｐ０を算出し（ステップＳ１０１）、初期点Ｐ０を点Ｑ０（ｉ＝１）と設定する（ステップＳ１０２）。暗号鍵解読装置１００は、点Ｑｉ−１に対して写像Ｆを適用して点Ｑｉを生成し（ステップＳ１０３）、ｉを１インクリメントさせる（ステップＳ１０４）。暗号鍵解読装置１００は、点Ｑｉが特徴点である場合には（ステップＳ１０５，Ｙｅｓ）、点Ｑｉの情報を点列データ１３１に格納する（ステップＳ１０６）。
【００５１】
暗号鍵解読装置１００は、点Ｑｉの情報を点列データ１３１に格納するごとに、衝突を探索する（ステップＳ１０７）。暗号鍵解読装置１００は、衝突を検知した場合には（ステップＳ１０８，Ｙｅｓ）、秘密鍵ｘを算出し（ステップＳ１０９）、処理を終了する。一方、暗号鍵解読装置１００は、衝突を検知しなかった場合には（ステップＳ１０８，Ｎｏ）、ステップＳ１０３に移行する。
【００５２】
暗号鍵解読装置１００は、ステップＳ１０５において、点Ｑｉが特徴点でない場合には（ステップＳ１０５，Ｎｏ）、ｉが閾値以上であるか否かを判定する（ステップＳ１１０）。暗号鍵解読装置１００は、ｉが閾値以上である場合には（ステップＳ１１０，Ｙｅｓ）、解が算出されないと判定してＮＧを出力し（ステップＳ１１１）、処理を終了する。一方、暗号鍵解読装置１００は、ｉが閾値未満である場合には（ステップＳ１１０，Ｎｏ）、ステップＳ１０３に移行する。
【００５３】
なお、上記の処理手順では、ＮＧを出力した後に、処理を終了すると説明したが、必ずしも処理を終了しなくても良い。例えば、暗号鍵解読装置１００は、ＮＧを出力した後に、新たな初期点Ｐ０を算出し、処理を継続しても良い。具体的には、ＮＧを出力する処理であるステップＳ１１１の処理の後に、新たな初期点Ｐ０を算出する処理を実行し、ステップＳ１０３に移行しても良い。
【００５４】
次に、本実施例１にかかる暗号鍵解読装置１００の効果について説明する。従来技術では、特徴点を含まないループや自明な衝突が発生した場合には、解が算出されないにもかかわらず、演算処理が継続されていた。これに対して、暗号鍵解読装置１００は、写像Ｆの演算処理回数に上限となる閾値を設定し、演算処理回数が閾値に到達した時点で解が算出されないと判定する。このため、暗号鍵解読装置１００は、特徴点を含まないループや自明な衝突が発生した場合でも、演算処理を確実に中断でき、解読にかかる計算量の増加を防ぐことができる。
【００５５】
ここで、演算処理回数に閾値を設定する根拠を説明する。図４は、演算処理回数に閾値を設定する根拠を説明するための図である。図４に示す例では、点Ｑｉの数値の下位２桁が００である点を特徴点とした場合を説明する。図４に示すグラフの横軸は、写像Ｆの演算処理回数ｉを示し、縦軸は、特徴点が生成される確率を示す。図４に示すように、特徴点が生成される確率は、写像Ｆの演算処理回数ｉの増加に伴って上昇するものの、１００回目をピークとして、その後低下する。特に、写像Ｆの演算処理回数ｉが１０００回を超えた場合に、特徴点がほとんど出力されなくなるのは、特徴点を含まないループが発生したか、あるいは自明な衝突が発生したものと推測されるからである。このため、判定処理部１４２で用いられる閾値は、１０００、すなわち、特徴点が出力される確率が最も高い演算処理回数ｉの１０倍に設定されることが望ましい。なお、閾値については、この例示に限るものではなく、暗号鍵解読装置１００を利用する者が任意の値に設定してよい。
【実施例２】
【００５６】
次に、本実施例２にかかる暗号鍵解読装置の構成の一例について説明する。図５は、本実施例２にかかる暗号鍵解読装置の構成を示す図である。図５に示すように、この暗号鍵解読装置２００は、入力部１１０、出力部１２０、記憶部１３０、制御部２４０を有する。このうち、図５に示す入力部１１０、出力部１２０、記憶部１３０の説明は、図１に示した入力部１１０、出力部１２０、記憶部１３０の説明と同様である。
【００５７】
制御部２４０は、点列生成処理部１４１、判定処理部２４２、衝突検知処理部１４３、解算出処理部１４４を有する。このうち、図５に示す点列生成処理部１４１、衝突検知処理部１４３、解算出処理部１４４の説明は、図１に示した点列生成処理部１４１、衝突検知処理部１４３、解算出処理部１４４の説明と同様である。
【００５８】
判定処理部２４２は、点列生成処理部１４１において生成された点のうち、特徴点でないと判定された点を判定点として設定し、設定した判定点と一致する点が生成された時点で、今後、解が算出されないと判定する処理部である。
【００５９】
具体的には、判定処理部２４２は、点列生成処理部１４１が生成した点のうち、特徴点でない一点を判定点Ｒとして保存する。この判定点Ｒは、点Ｑ０が初期点として保存され、写像Ｆの演算処理回数が回数ｍに到達する度に、ｍ回目に生成された点Ｑｉに更新される値である。例えば、ｍが１０である場合には、判定点Ｒは、最初に点Ｑ０が保存され、点Ｑ１０，点Ｑ２０，点Ｑ３０・・・と更新される。なお、回数ｍについては、この例示に限るものではなく、暗号鍵解読装置１００を利用する者が任意の値に設定してよい。
【００６０】
また、判定処理部２４２は、点列生成処理部１４１が点Ｑｉを生成するごとに、点Ｑｉが判定点Ｒと一致するか否かを判定する。判定処理部２４２は、点Ｑｉが判定点Ｒと一致する場合には、解が算出されないと判定し、出力部１２０にＮＧを出力する。これに対して、判定処理部２４２は、点Ｑｉが判定点Ｒと一致しない場合には、次の点Ｑｉの情報を受け付けるまで待機する。
【００６１】
次に、本実施例２にかかる暗号鍵解読装置２００の処理手順について説明する。図６は、本実施例２にかかる暗号鍵解読装置の処理手順を示すフローチャートである。例えば、図６に示す処理は、暗号鍵解読装置２００が、入力部１１０を介して秘密鍵ｘを算出する命令を受け付けたことを契機として実行される。
【００６２】
図６に示すように、暗号鍵解読装置２００は、入力部１１０を介して受け付けたパラメータを用いて初期点Ｐ０を算出し（ステップＳ２０１）、初期点Ｐ０を点Ｑ０（ｉ＝１）と設定し、さらに点Ｑ０を判定点Ｒ（ｊ＝１）と設定する（ステップＳ２０２）。なお、このｊは、判定処理部２４２が判定点Ｒの更新タイミングを管理するために設定される値である。ｊは、点Ｑｉが写像される度に１インクリメントされ、回数ｍに達する度に１に再設定される。
【００６３】
暗号鍵解読装置２００は、点Ｑｉ−１に対して写像Ｆを適用して点Ｑｉを生成し（ステップＳ２０３）、ｉおよびｊをそれぞれ１インクリメントさせる（ステップＳ２０４）。暗号鍵解読装置２００は、点Ｑｉが特徴点である場合には（ステップＳ２０５，Ｙｅｓ）、点Ｑｉの情報を点列データ１３１に格納する（ステップＳ２０６）。
【００６４】
暗号鍵解読装置２００は、点Ｑｉの情報を点列データ１３１に格納するごとに、衝突を探索する（ステップＳ２０７）。暗号鍵解読装置２００は、衝突を検知した場合には（ステップＳ２０８，Ｙｅｓ）、秘密鍵ｘを算出し（ステップＳ２０９）、処理を終了する。一方、暗号鍵解読装置２００は、衝突を検知しなかった場合には（ステップＳ２０８，Ｎｏ）、ステップＳ２０３に移行する。
【００６５】
暗号鍵解読装置２００は、ステップＳ２０５において、点Ｑｉが特徴点でない場合には（ステップＳ２０５，Ｎｏ）、点Ｑｉが判定点Ｒと一致するか否かを判定する（ステップＳ２１０）。暗号鍵解読装置２００は、点Ｑｉが判定点Ｒと一致する場合には（ステップＳ２１０，Ｙｅｓ）、解が算出されないと判定してＮＧを出力し（ステップＳ２１１）、処理を終了する。一方、暗号鍵解読装置２００は、点Ｑｉが判定点Ｒと一致しない場合には（ステップＳ２１０，Ｎｏ）、ｊがｍに到達する度に、判定点Ｒを点Ｑｉに更新するとともに、ｊを１に設定し（ステップＳ２１２）、ステップＳ２０３に移行する。
【００６６】
なお、上記の処理手順では、ＮＧを出力した後に、処理を終了すると説明したが、必ずしも処理を終了しなくても良い。例えば、暗号鍵解読装置２００は、ＮＧを出力した後に、新たな初期点Ｐ０を算出し、処理を継続しても良い。具体的には、ＮＧを出力する処理であるステップＳ２１１の処理の後に、新たな初期点Ｐ０を算出する処理を実行し、ステップＳ２０３に移行しても良い。
【００６７】
次に、本実施例２にかかる暗号鍵解読装置２００の効果について説明する。図１４および図１５に示したように、従来技術では、特徴点を含まないループや自明な衝突が発生し、ループが形成された場合には、解が算出されないにもかかわらず、演算処理が継続されていた。これに対して、暗号鍵解読装置２００は、生成した点のうち、特徴点でない点を判定点として設定し、演算処理が所定回数に到達する度に、判定点を新たな点に更新する。このため、特徴点を含まないループや自明な衝突が発生した場合には、ループ上の点のいずれかが判定点に設定されるので、暗号鍵解読装置２００は、判定点と今後生成される点との衝突を判定することで、今後解が算出されないということを早期に検出できる。したがって、暗号鍵解読装置２００は、特徴点を含まないループや自明な衝突が発生した場合でも、演算処理を早期に中断でき、解読にかかる計算量を削減することができる。
【００６８】
ところで、図５に示した暗号鍵解読装置２００の構成は一例であり、暗号鍵解読装置２００は、必ずしも図５に示した各処理部を全て有していなくても良い。例えば、暗号鍵解読装置２００は、点生成部と判定点記憶部と判定部の機能を有していれば良い。
【００６９】
このうち、点生成部は、点に対して写像を実行し、写像の実行結果となる点に対して再度写像を実行する処理を繰り返し実行することで複数の点を生成する処理部である。この点生成部は、点列生成処理部１４１に対応する。判定点記憶部は、点生成部によって生成された点が、所定の特徴を有する特徴点であるか否かを判定し、特徴点でないと判定した点を判定点として記憶装置に記憶する処理部である。この判定点記憶部は、点列生成処理部１４１と判定処理部２４２とに対応する。また、判定部は、点生成部によって生成された点と前記記憶装置に記憶された判定点とを比較して、前記点と判定点とが一致した場合に、特徴点同士の衝突が起こらないと判定する処理部である。この判定部は、判定処理部２４２に対応する。
【実施例３】
【００７０】
次に、本実施例３にかかる暗号鍵解読装置の構成の一例について説明する。図７は、本実施例３にかかる暗号鍵解読装置の構成を示す図である。図７に示すように、この暗号鍵解読装置３００は、入力部１１０、出力部１２０、記憶部１３０、制御部３４０を有する。このうち、図７に示す入力部１１０、出力部１２０、記憶部１３０の説明は、図１に示した入力部１１０、出力部１２０、記憶部１３０の説明と同様である。
【００７１】
制御部３４０は、点列生成処理部１４１、判定処理部３４２、衝突検知処理部１４３、解算出処理部１４４を有する。このうち、図７に示す点列生成処理部１４１、衝突検知処理部１４３、解算出処理部１４４の説明は、図１に示した点列生成処理部１４１、衝突検知処理部１４３、解算出処理部１４４の説明と同様である。
【００７２】
判定処理部３４２は、図１に示した判定処理部１４２と同様の機能と、図５に示した判定処理部２４２と同様の機能とを有する。すなわち、判定処理部３４２は、点列生成処理部１４１による演算処理回数と所定の閾値とを比較し、演算処理回数が所定の閾値以上である場合に、解が算出されないと判定する。また、判定処理部３４２は、点列生成処理部１４１において生成された点のうち、特徴点でないと判定された点を判定点として設定し、設定した判定点と一致する点が生成された時点で、解が算出されないと判定する。
【００７３】
次に、本実施例３にかかる暗号鍵解読装置３００の処理手順について説明する。図８は、本実施例３にかかる暗号鍵解読装置の処理手順を示すフローチャートである。例えば、図８に示す処理は、暗号鍵解読装置３００が、入力部１１０を介して秘密鍵ｘを算出する命令を受け付けたことを契機として実行される。
【００７４】
図８に示すように、暗号鍵解読装置３００は、入力部１１０を介して受け付けたパラメータを用いて初期点Ｐ０を算出し（ステップＳ３０１）、初期点Ｐ０を点Ｑ０（ｉ＝１）と設定し、さらに点Ｑ０を判定点Ｒ（ｊ＝１）と設定する（ステップＳ３０２）。暗号鍵解読装置３００は、点Ｑｉ−１に対して写像Ｆを適用して点Ｑｉを生成し（ステップＳ３０３）、ｉおよびｊをそれぞれ１インクリメントさせる（ステップＳ３０４）。暗号鍵解読装置３００は、点Ｑｉが特徴点である場合には（ステップＳ３０５，Ｙｅｓ）、点Ｑｉの情報を点列データ１３１に格納する（ステップＳ３０６）。
【００７５】
暗号鍵解読装置３００は、点Ｑｉの情報を点列データ１３１に格納するごとに、衝突を探索する（ステップＳ３０７）。暗号鍵解読装置３００は、衝突を検知した場合には（ステップＳ３０８，Ｙｅｓ）、秘密鍵ｘを算出し（ステップＳ３０９）、処理を終了する。一方、暗号鍵解読装置３００は、衝突を検知しなかった場合には（ステップＳ３０８，Ｎｏ）、ステップＳ３０３に移行する。
【００７６】
暗号鍵解読装置３００は、ステップＳ３０５において、点Ｑｉが特徴点でない場合には（ステップＳ３０５，Ｎｏ）、ｉが閾値以上であるか否かを判定する（ステップＳ３１０）。暗号鍵解読装置３００は、ｉが閾値以上である場合には（ステップＳ３１０，Ｙｅｓ）、解が算出されないと判定してＮＧを出力し（ステップＳ３１１）、処理を終了する。一方、暗号鍵解読装置３００は、ｉが閾値未満である場合には（ステップＳ３１０，Ｎｏ）、点Ｑｉが判定点Ｒと一致するか否かを判定する（ステップＳ３１２）。暗号鍵解読装置３００は、点Ｑｉが判定点Ｒと一致する場合には（ステップＳ３１２，Ｙｅｓ）、ステップＳ３１１に移行する。一方、暗号鍵解読装置３００は、点Ｑｉが判定点Ｒと一致しない場合には（ステップＳ３１２，Ｎｏ）、ｊがｍに到達する度に、判定点Ｒを点Ｑｉに更新するとともに、ｊを１に設定し（ステップＳ３１３）、ステップＳ３０３に移行する。
【００７７】
なお、上記の処理手順では、ＮＧを出力した後に、処理を終了すると説明したが、必ずしも処理を終了しなくても良い。例えば、暗号鍵解読装置３００は、ＮＧを出力した後に、新たな初期点Ｐ０を算出し、処理を継続しても良い。具体的には、ＮＧを出力する処理であるステップＳ３１１の処理の後に、新たな初期点Ｐ０を算出する処理を実行し、ステップＳ３０３に移行しても良い。
【００７８】
また、上記の処理手順は、上記の順番に限定されるものではなく、処理内容を矛盾させない範囲で適宜変更されても良い。例えば、上記の処理手順では、ｉが閾値以上であるか否かを判定する処理を実行した後に、点Ｑｉが判定点Ｒと一致するか否かを判定する処理を実行すると説明したが、これらの処理を逆の順序で実行しても良い。具体的には、ｉが閾値以上であるか否かを判定する処理であるステップＳ３１０の処理は、点Ｑｉが判定点Ｒと一致するか否かを判定する処理であるステップＳ３１２〜ステップＳ３１３の処理の後に実行されても良い。
【００７９】
次に、本実施例３にかかる暗号鍵解読装置３００の効果について説明する。従来技術では、特徴点を含まないループや自明な衝突が発生した場合には、解が算出されないにもかかわらず、演算処理が継続されていた。これに対して、暗号鍵解読装置３００は、特徴点を含まないループや自明な衝突が発生した場合でも、判定点を用いることで、演算処理を早期に中断でき、解読にかかる計算量を削減できる。
【００８０】
また、判定点と一致する点が検出されない場合でも、衝突が発生しないことが原因で、演算処理回数が増加してしまう場合がある。このような場合には、図４に示したように、演算処理回数が増加するほど、特徴点が生成される確率は低下するので、解が算出され難くなる。これに対して、暗号鍵解読装置３００は、演算処理回数に閾値を設定することで、演算処理を確実に中断でき、解読にかかる計算量の増加を防止できる。
【００８１】
ここで、本実施例１〜３にかかる暗号鍵解読装置の効果を比較して説明する。図９は、本実施例１〜３にかかる暗号鍵解読装置の効果を比較して説明するための図である。図９に示す例では、点Ｑｉの数値の下位２桁が００である点を特徴点とし、演算処理回数の閾値を１０００とし、ｍ＝１０とした場合を説明する。図９に示すように、従来の特徴点を導入しない技術では、写像Ｆを用いて生成した全ての点を記憶して衝突を探索するので、衝突を必ず検知できる。しかし、この従来技術では、全ての点を記憶する必要があるのでメモリ使用量が膨大になっていた。また、この従来技術では、全ての点を用いて衝突を探索するので、衝突の検知速度は遅かった。
【００８２】
これに対して、本実施例１にかかる暗号鍵解読装置１００は、特徴点のみを記憶するので、メモリ使用量が削減される。また、暗号鍵解読装置１００は、特徴点のみを用いて衝突を探索するので、従来技術に比べて処理速度が上がり、衝突を早く検出できる。また、暗号鍵解読装置１００は、特徴点を含まないループや自明な衝突が発生した場合でも、演算処理回数の上限を設定するので、演算処理を確実に中断でき、無駄な点を１０００個以内に抑えることができる。このため、暗号鍵解読装置１００は、新たな初期点Ｐ０を生成することで、演算処理を再び実行できるので、衝突を確実に検出できる。
【００８３】
また、本実施例２にかかる暗号鍵解読装置２００は、特徴点を含まないループや自明な衝突が発生した場合でも、判定点を用いることで、演算処理を早期に中断でき、無駄な点を１０個程度に抑えることができる。このため、暗号鍵解読装置１００は、演算処理回数が少ない段階で新たな初期点Ｐ０を生成し、演算処理を再び実行できるので、衝突を早期に検出できる。
【００８４】
しかし、暗号鍵解読装置２００は、判定点と一致する点を検出しない場合でも、衝突が発生しないことが原因で、演算処理回数が増加してしまう場合があった。これに対して、本実施例３にかかる暗号鍵解読装置３００は、演算処理回数の上限を設定するので、演算処理を確実に中断でき、無駄な点を１０００個以内に抑えることができる。このため、暗号鍵解読装置３００は、衝突を早期に、かつ、確実に検出できる。
【００８５】
また、図１，５，７に示した記憶部１３０は、例えば、ＲＡＭ（Random Access Memory）、ＲＯＭ（Read Only Memory）、フラッシュメモリ（Flash Memory）などの半導体メモリ素子、ハードディスクや光ディスクなどの記憶装置に対応する。また、図１，５，７に示した制御部１４０，２４０，３４０は、例えば、ＡＳＩＣ（Application Specific Integrated Circuit）やＦＰＧＡ（Field Programmable Gate Array）などの集積装置に対応する。または、制御部１４０，２４０，３４０は、例えば、ＣＰＵ（Central Processing Unit）やＭＰＵ（Micro Processing Unit）などの電子回路に対応する。
【００８６】
また、本実施例１〜３において説明した各処理のうち、自動的に行われるものとして説明した処理の全部または一部を手動的に行うこともでき、あるいは、手動的に行われるものとして説明した処理の全部または一部を公知の方法で自動的に行うこともできる。この他、上述文書中や図面中で示した処理手順、制御手順、具体的名称、各種のデータやパラメータを含む情報については、特記する場合を除いて任意に変更することができる。
【００８７】
また、図示した各装置の各構成要素は機能概念的なものであり、必ずしも物理的に図示の如く構成されていることを要しない。すなわち、各装置の分散・統合の具体的形態は図示のものに限られず、その全部または一部を、各種の負荷や使用状況などに応じて、任意の単位で機能的または物理的に分散・統合して構成することができる。例えば、図１に示した点列生成処理部１４１〜解算出処理部１４４のうちいずれかの機能をサーバに持たせ、かかるサーバと暗号鍵解読装置１００とが協働することで、解が算出されないことを判定しても良い。
【００８８】
また、暗号鍵解読装置１００〜３００は、既知のパーソナルコンピュータ、ワークステーション、携帯電話、ＰＨＳ端末、移動体通信端末またはＰＤＡなどの情報処理装置に、暗号鍵解読装置１００〜３００の各機能を搭載することによって実現することもできる。
【００８９】
図１０は、本実施例にかかる暗号鍵解読装置を構成するコンピュータのハードウェア構成を示す図である。図１０に示すように、このコンピュータ４００は、各種演算処理を実行するＣＰＵ４０１と、ユーザからのデータの入力を受け付ける入力装置４０２と、モニタ４０３を有する。また、コンピュータ４００は、記憶媒体からプログラム等を読み取る媒体読み取り装置４０４と、ネットワークを介して他のコンピュータとの間でデータの授受を行うネットワークインターフェース装置４０５を有する。また、コンピュータ４００は、各種情報を一時記憶するＲＡＭ（Random Access Memory）４０６と、ハードディスク装置４０７を有する。各装置４０１〜４０７は、バス４０８に接続される。
【００９０】
そして、ハードディスク装置４０７は、図１，５，７に示した、点列生成処理部１４１、判定処理部１４２，２４２，３４２、衝突検知処理部１４３、解算出処理部１４４と同様の機能を有する暗号鍵解読プログラム４０７ａを記憶する。また、ハードディスク装置４０７は、図１，５，７に示した点列データ１３１に対応する点列データ４０７ｂを記憶する。
【００９１】
ＣＰＵ４０１が暗号鍵解読プログラム４０７ａをハードディスク装置４０７から読み出してＲＡＭ４０６に展開することにより、暗号鍵解読プログラム４０７ａは、暗号鍵解読プロセス４０６ａとして機能する。そして、ＣＰＵ４０１がハードディスク装置４０７から点列データ４０７ｂを読み出して、ＲＡＭ４０６に点列データ４０６ｂを展開し、暗号鍵解読プロセス４０６ａが点列データ４０６ｂを利用して処理を実行する。
【００９２】
なお、上記の暗号鍵解読プログラム４０７ａは、必ずしもハードディスク装置４０７に記憶されている必要はない。例えば、ＣＤ−ＲＯＭ等の記憶媒体に記憶されたプログラムを、コンピュータ４００が読み出して実行するようにしても良い。また、公衆回線、インターネット、ＬＡＮ（Local Area Network）、ＷＡＮ（Wide Area Network）等にこのプログラムを記憶させておき、コンピュータ４００がこれらからプログラムを読み出して実行するようにしても良い。
【００９３】
以上の各実施例を含む実施形態に関し、さらに以下の付記を開示する。
【００９４】
（付記１）コンピュータが、
点に対して写像を実行し、該写像の実行結果となる点に対して再度前記写像を実行する処理を繰り返し実行することで複数の点を生成する点生成ステップと、
前記点生成ステップによって生成された点が、所定の特徴を有する特徴点であるか否かを判定し、特徴点でないと判定した点を判定点として記憶装置に記憶する判定点記憶ステップと、
前記点生成ステップによって生成された点と前記記憶装置に記憶された判定点とを比較して、前記点と判定点とが一致した場合に、特徴点同士の衝突が起こらないと判定する判定ステップと
を実行することを特徴とする暗号鍵解読方法。
【００９５】
（付記２）前記写像が所定回数実行される毎に、前記記憶装置に記憶された判定点を新たに生成された点に更新する判定点更新ステップを更に実行することを特徴とする付記１に記載の暗号鍵解読方法。
【００９６】
（付記３）前記判定ステップは、前記写像が実行された回数と閾値とを比較し、写像が実行された回数が閾値以上である場合に、特徴点同士の衝突が起こらないと更に判定することを特徴とする付記１または２に記載の暗号鍵解読方法。
【００９７】
（付記４）点に対して写像を実行し、該写像の実行結果となる点に対して再度前記写像を実行する処理を繰り返し実行することで複数の点を生成する点生成部と、
前記点生成部によって生成された点が、所定の特徴を有する特徴点であるか否かを判定し、特徴点でないと判定した点を判定点として記憶装置に記憶する判定点記憶部と、
前記点生成部によって生成された点と前記記憶装置に記憶された判定点とを比較して、前記点と判定点とが一致した場合に、特徴点同士の衝突が起こらないと判定する判定部と
を備えたことを特徴とする暗号鍵解読装置。
【００９８】
（付記５）前記写像が所定回数実行される毎に、前記記憶装置に記憶された判定点を新たに生成された点に更新する判定点更新部を更に備えたことを特徴とする付記４に記載の暗号鍵解読装置。
【００９９】
（付記６）前記判定部は、前記写像が実行された回数と閾値とを比較し、写像が実行された回数が閾値以上である場合に、特徴点同士の衝突が起こらないと更に判定することを特徴とする付記４または５に記載の暗号鍵解読装置。
【０１００】
（付記７）コンピュータに、
点に対して写像を実行し、該写像の実行結果となる点に対して再度前記写像を実行する処理を繰り返し実行することで複数の点を生成する点生成手順と、
前記点生成手順によって生成された点が、所定の特徴を有する特徴点であるか否かを判定し、特徴点でないと判定した点を判定点として記憶装置に記憶する判定点記憶手順と、
前記点生成手順によって生成された点と前記記憶装置に記憶された判定点とを比較して、前記点と判定点とが一致した場合に、特徴点同士の衝突が起こらないと判定する判定手順と
を実行させることを特徴とする暗号鍵解読プログラム。
【０１０１】
（付記８）前記写像が所定回数実行される毎に、前記記憶装置に記憶された判定点を新たに生成された点に更新する判定点更新手順を更に実行させることを特徴とする付記７に記載の暗号鍵解読プログラム。
【０１０２】
（付記９）前記判定手順は、前記写像が実行された回数と閾値とを比較し、写像が実行された回数が閾値以上である場合に、特徴点同士の衝突が起こらないと更に判定することを特徴とする付記７または８に記載の暗号鍵解読プログラム。
【符号の説明】
【０１０３】
１００ 暗号鍵解読装置
１１０ 入力部
１２０ 出力部
１３０ 記憶部
１３１ 点列データ
１４０ 制御部
１４１ 点列生成処理部
１４２ 判定処理部
１４３ 衝突検知処理部
１４４ 解算出処理部
２００ 暗号鍵解読装置
２４０ 制御部
２４２ 判定処理部
３００ 暗号鍵解読装置
３４０ 制御部
３４２ 判定処理部
【技術分野】
【０００１】
本発明は、暗号鍵解読方法、暗号鍵解読装置および暗号鍵解読プログラムに関する。
【背景技術】
【０００２】
従来、情報通信において情報を保護するために用いられる暗号化方式の一つとして、公開鍵暗号が存在する。公開鍵暗号は、情報を暗号化するための公開鍵と、公開鍵により暗号化された情報を復号化するための秘密鍵とで一対の異なる鍵を用いる暗号方式である。公開鍵暗号では、送信者は、受信者が公開している公開鍵で情報を暗号化して送信し、受信者は、暗号化された情報を自分だけが保持している秘密鍵で復号する。
【０００３】
公開鍵暗号は、公開鍵から秘密鍵が解読されないようにするために、数学的に難しいとされる問題に基づいて設計される。例えば、公開鍵暗号には、ＥｌＧａｍａｌ暗号や楕円曲線暗号のように、計算量的に解読が困難である離散対数問題に基づいて設計されるものが存在する。離散対数問題とは、素数ｐに対して有限体ＧＦ（ｐ）の生成元αを固定し、有限体ＧＦ（ｐ）の元βに対してβ＝αｘを満たす整数ｘを求めるという問題である。
【０００４】
公開鍵暗号により情報を保護するためには、現状および今後の計算機能力を見積もり、容易に解読できないような計算量になるようにパラメータを設計する必要がある。このため、公開鍵暗号を実際に解読し、解読にかかる計算量を評価する方法が存在する。例えば、上記の離散対数問題に基づく公開鍵暗号を解読する方法として、Pollardのρ法がある。このPollardのρ法は、所定の点に対して写像を適用して新たな点を生成し、生成した点に対して写像を更に適用することで、点の生成を繰り返す。そして、Pollardのρ法は、生成した複数の点のうち２点が一致する場合に得られる関係式を用いることで、離散対数問題を解く方法である。
【０００５】
ここで、Pollardのρ法について説明する。図１１および図１２は、従来のPollardのρ法を説明するための図である。図１１に示すように、Pollardのρ法では、まず、初期点Ｐ０が生成される。続いて、点Ｐｉ−１から点Ｐｉへの写像Ｆを用いて、点Ｐ１，点Ｐ２，点Ｐ３・・・のように点Ｐｉが生成される。生成された点Ｐｉは、図１２に示すように、メモリに記憶される。なお、写像Ｆは、下記の式（１）によって示され、下記の式（２）が成り立つｕｉおよびｖｉを一意に算出できる写像である。
【０００６】
Ｐｉ＝Ｆ（Ｐｉ−１）・・・（１）
【０００７】
Ｐｉ＝α＾｛ｕｉ｝＊β＾｛ｖｉ｝・・・（２）
【０００８】
続いて、点Ｐｊがメモリに新たに記憶されるごとに、点Ｐｊが既に記憶された点Ｐ１〜点Ｐｊ−１のいずれかと一致するか否かが判定される。点Ｐｊが既に記憶された点Ｐ１〜点Ｐｊ−１のいずれかと一致する場合には、２つの点の一致を衝突として検出する。すなわち、点Ｐｊと点Ｐｉとが衝突する場合には、下記の式（３）が成り立つ。
【０００９】
Ｐｉ＝Ｐｊ・・・（３）
【００１０】
続いて、点Ｐｉの式（２）および２点の衝突によって得られる式（３）から、下記の式（４）が導かれる。式（４）に離散対数問題の条件式β＝αｘをあてはめると、下記の式（５）が導かれる。そして、式（５）にｕｉ，ｖｉ，ｕｊ，ｖｊを代入することで、秘密鍵ｘが算出される。なお、秘密鍵ｘが算出されるのは、ｖｉ≠ｖｊが成り立つ場合である。
【００１１】
α＾｛ｕｉ｝＊β＾｛ｖｉ｝＝α＾｛ｕｊ｝＊β＾｛ｖｊ｝・・・（４）
【００１２】
ｘ＝（ｕｉ−ｕｊ）／（ｖｊ−ｖｉ）・・・（５）
【００１３】
しかし、Pollardのρ法を用いて公開鍵暗号の解読を実行すると、多数の点Ｐｉが生成され、生成された点Ｐｉを記憶するためのメモリ使用量が膨大になってしまうという問題があった。このメモリ使用量を削減する技術として、特徴点（distinguished point）を導入したρ法が存在する。この方法は、生成された点Ｐｉのうち、数値に特徴を有する特徴点のみを記憶することで、メモリ使用量を削減する方法である。
【００１４】
ここで、特徴点を導入したρ法について説明する。図１３は、従来の特徴点を導入したρ法を説明するための図である。図１３に示す例では、点Ｐｉの数値の下位２桁が００である点を特徴点として設定した場合を説明する。図１３に示す白丸印は特徴点を示し、黒丸印は特徴点でない点を示す。特徴点を導入したρ法では、生成された全ての点Ｐｉを記憶するのではなく、特徴点のみをメモリに記憶する。衝突の検出はメモリ上で行われるので、図１３に示すように、特徴点でない点Ｐ１０と点Ｐ２８とが一致していたとしても、この一致は衝突として検出されない。しかし、写像Ｆは一意の写像であるので、同一の点からの写像は常に一致する。つまり、点Ｐ２８が点Ｐ１０と一致した場合には、次の点Ｐ２９は点Ｐ１１と一致する。さらに、次々に生成される点Ｐ３０，点Ｐ３１，点Ｐ３２・・・は、点Ｐ１２，点Ｐ１３，点Ｐ１４・・・とそれぞれ一致する。このように、新たな点が既に生成された点のいずれかと一致すると、同一の点が生成され続けるループが形成される。このため、このループ上に特徴点が含まれる場合には、衝突が検出される。図１３に示す例では、ループ上に点Ｐ１７，点Ｐ２９の２点が含まれるので、点Ｐ３５が生成された時点で、点Ｐ１７と点Ｐ３５との衝突が検出される。このように、特徴点を導入したρ法では、解読にかかる計算量は増加するものの、メモリ使用量は削減される。
【先行技術文献】
【特許文献】
【００１５】
【特許文献１】特開２００８−２０６５３号公報
【発明の概要】
【発明が解決しようとする課題】
【００１６】
しかしながら、上記従来技術では、特徴点のみを記憶するので、メモリ使用量を低減できるものの、解が算出されない場合があった。このため、解が算出されないにもかかわらず、演算処理が継続されてしまい、解読にかかる計算量が膨大になっていた。
【００１７】
図１４および図１５を用いて、解が算出されない場合について説明する。図１４および図１５は、従来技術の問題を説明するための図である。図１４および図１５に示す白丸印は特徴点を示し、黒丸印は特徴点でない点を示す。
【００１８】
図１４に示す例では、特徴点を含まないループが発生した場合を説明する。図１４に示すように、ループが形成されると、写像Ｆを繰り返し実行したとしても、周期的に同じ点が生成されてしまう。このため、ループ上に特徴点が含まれていなければ、特徴点でない点が生成され続けるため、特徴点の衝突を検出することができず、解を算出することができない。
【００１９】
図１５に示す例では、自明な衝突が発生した場合を説明する。この自明な衝突とは、２点Ｐｉ，Ｐｊが衝突した場合に、衝突した２点の係数ｕｉ，ｖｉ，ｕｊ，ｖｊが等しくなることである。つまり、自明な衝突が発生すると、Ｐｉ＝Ｐｊ，ｕｉ＝ｕｊ，ｖｉ＝ｖｊが成り立つ。図１５に示すように、自明な衝突が発生した場合には、写像Ｆの演算処理を繰り返したとしても、２点間の写像を繰り返すのみである。このため、この２点がいずれも特徴点でなければ、特徴点の衝突を検出することができず、解を算出することができない。また、仮に、この２点のいずれかが特徴点であったとしても、ｖｉ＝ｖｊを満たすので、上記の式（５）を用いても解を算出することができない。
【００２０】
開示の技術は、上記に鑑みてなされたものであって、解読にかかる計算量を削減することができる暗号鍵解読方法、暗号鍵解読装置および暗号鍵解読プログラムを提供することを目的とする。
【課題を解決するための手段】
【００２１】
本願の開示する技術は、一つの態様において、コンピュータが、点生成ステップと、判定点記憶ステップと、判定ステップとを実行することを要件とする。点生成ステップは、点に対して写像を実行し、写像の実行結果となる点に対して再度写像を実行する処理を繰り返し実行することで複数の点を生成する。判定点記憶ステップは、点生成ステップによって生成された点が、所定の特徴を有する特徴点であるか否かを判定し、特徴点でないと判定した点を判定点として記憶装置に記憶する。判定ステップは、点生成ステップによって生成された点と記憶装置に記憶された判定点とを比較して、点と判定点とが一致した場合に、特徴点同士の衝突が起こらないと判定する。
【発明の効果】
【００２２】
本願の開示する技術の一つの態様によれば、解読にかかる計算量を削減することができるという効果を奏する。
【図面の簡単な説明】
【００２３】
【図１】図１は、本実施例１にかかる暗号鍵解読装置の構成を示す図である。
【図２】図２は、点列データのデータ構造の一例を示す図である。
【図３】図３は、本実施例１にかかる暗号鍵解読装置の処理手順を示すフローチャートである。
【図４】図４は、演算処理回数に閾値を設定する根拠を説明するための図である。
【図５】図５は、本実施例２にかかる暗号鍵解読装置の構成を示す図である。
【図６】図６は、本実施例２にかかる暗号鍵解読装置の処理手順を示すフローチャートである。
【図７】図７は、本実施例３にかかる暗号鍵解読装置の構成を示す図である。
【図８】図８は、本実施例３にかかる暗号鍵解読装置の処理手順を示すフローチャートである。
【図９】図９は、本実施例１〜３にかかる暗号鍵解読装置の効果を比較して説明するための図である。
【図１０】図１０は、本実施例にかかる暗号鍵解読装置を構成するコンピュータのハードウェア構成を示す図である。
【図１１】図１１は、従来のPollardのρ法を説明するための図である。
【図１２】図１２は、従来のPollardのρ法を説明するための図である。
【図１３】図１３は、従来の特徴点を導入したρ法を説明するための図である。
【図１４】図１４は、従来技術の問題を説明するための図である。
【図１５】図１５は、従来技術の問題を説明するための図である。
【発明を実施するための形態】
【００２４】
以下に、本願の開示する暗号鍵解読方法、暗号鍵解読装置および暗号鍵解読プログラムの実施例を図面に基づいて詳細に説明する。なお、この実施例によりこの発明が限定されるものではない。各実施例は、処理内容を矛盾させない範囲で適宜組み合わせることが可能である。
【実施例１】
【００２５】
本実施例１にかかる暗号鍵解読装置の構成の一例について説明する。図１は、本実施例１にかかる暗号鍵解読装置の構成を示す図である。図１に示すように、この暗号鍵解読装置１００は、入力部１１０、出力部１２０、記憶部１３０、制御部１４０を有する。
【００２６】
入力部１１０は、各種情報の入力を受け付ける入力装置である。例えば、入力部１１０は、パラメータ（ｐ，α，β）の入力や秘密鍵ｘを算出する命令の入力を受け付ける。入力部１１０は、キーボードやマウスなどに対応する装置である。出力部１２０は、各種情報を出力する出力装置である。例えば、出力部１２０は、後述する解算出処理部１４４から受け付けた秘密鍵ｘを出力する。出力部１２０は、ディスプレイやモニタなどに対応する装置である。
【００２７】
記憶部１３０は、点列データ１３１を有する。この点列データ１３１は、ｉと、Ｑｉと、ｕｉと、ｖｉとを対応付けて記憶する。このうち、ｉは、インデックスであり、１以上の整数である。また、Ｑｉは、Ｑｉ−１を写像した値であり、ｕｉ、ｖｉは、Ｑｉの係数である。
【００２８】
図２は、点列データのデータ構造の一例を示す図である。図２に示すように、例えば、点列データ１３１は、ｉ＝３と、Ｑｉ＝１７１００と、ｕｉ＝１９と、ｖｉ＝６とを対応付けて記憶する。また、点列データ１３１は、ｉ＝１７と、Ｑｉ＝４５００と、ｕｉ＝４４と、ｖｉ＝３とを対応付けて記憶する。また、点列データ１３１は、ｉ＝２９と、Ｑｉ＝４３００と、ｕｉ＝２６と、ｖｉ＝５とを対応付けて記憶する。また、点列データ１３１は、ｉ＝３５と、Ｑｉ＝４５００と、ｕｉ＝８と、ｖｉ＝６９とを対応付けて記憶する。
【００２９】
制御部１４０は、点列生成処理部１４１、判定処理部１４２、衝突検知処理部１４３、解算出処理部１４４を有する。
【００３０】
点列生成処理部１４１は、所定の点に対して写像を適用して新たな点を生成し、生成した点に対して写像を更に適用することで、点の生成を繰り返す。そして、点列生成処理部１４１は、点を生成する度に、生成した点が数値に所定の特徴を有する特徴点であるか否かを判定し、特徴点であると判定された点の情報を点列データ１３１に格納する処理部である。
【００３１】
以下において、点列生成処理部１４１の処理について具体的に説明する。例えば、点列生成処理部１４１は、入力部１１０を介して受け付けたパラメータ（ｐ，α，β）と下記の式（６）とを用いて、初期点Ｐ０を算出する。なお、例えば、式（６）のｕ０は、ランダムに選択される初期値である。また、例えば、ｖ０は、０である。
【００３２】
Ｐ０＝α＾｛ｕ０｝＊β＾｛ｖ０｝・・・（６）
【００３３】
続いて、点列生成処理部１４１は、初期点Ｐ０をＱ０と設定し、下記の式（７）を用いて、点Ｑｉを算出する。なお、式（７）のＦは、点Ｑｉ−１から点Ｑｉへの写像であり、下記の式（８）が成り立つｕｉおよびｖｉを一意に算出できる写像である。また、式（７）のｉは、インデックスであり、写像Ｆの演算処理回数に対応する。つまり、ｉは、点Ｑｉが写像される度に、１インクリメントされる。
【００３４】
Ｑｉ＝Ｆ（Ｑｉ−１）・・・（７）
【００３５】
Ｑｉ＝α＾｛ｕｉ｝＊β＾｛ｖｉ｝・・・（８）
【００３６】
また、点列生成処理部１４１は、点Ｑｉを生成する度に、生成した点Ｑｉが数値に特徴を有する特徴点であるか否かを判定する。ここで、特徴点とは、例えば、点Ｑｉの数値の下位２桁が００である点を指す。点列生成処理部１４１は、点Ｑｉが特徴点であると判定された場合には、点Ｑｉの情報としてｉと、Ｑｉと、ｕｉと、ｖｉとを対応付けて点列データ１３１に格納する。例えば、点列生成処理部１４１は、点Ｑ３が特徴点であると判定された場合には、点Ｑ３の情報として、ｉ＝３と、Ｑｉ＝１７１００と、ｕｉ＝１９と、ｖｉ＝６とを対応付けて点列データ１３１に格納する。また、点列生成処理部１４１は、点Ｑｉが特徴点でないと判定された場合には、点Ｑｉの情報を判定処理部１４２に出力する。
【００３７】
判定処理部１４２は、点列生成処理部１４１による演算処理回数と所定の閾値とを比較し、演算処理回数が所定の閾値以上である場合に、解が算出されないと判定する処理部である。ここで、衝突とは、点列データ１３１に新たに格納された点が、点列データ１３１に既に記憶された点のいずれかと一致することを指す。
【００３８】
例えば、判定処理部１４２は、点Ｑｉの情報を点列生成処理部１４１から受け付けて、受け付けた点Ｑｉに対応するｉと所定の閾値とを比較する。判定処理部１４２は、ｉが所定の閾値以上である場合には、解が算出されないと判定し、出力部１２０にＮＧを出力する。これに対して、ｉが所定の閾値未満である場合には、判定処理部１４２は、次の点Ｑｉの情報を受け付けるまで待機する。ここで比較される閾値は、例えば、特徴点が出力される確率が最も高いｉの値を１０倍した値である。例えば、点Ｑｉの数値の下位２桁が００である点を特徴点とした場合には、閾値は１０００に設定される。
【００３９】
衝突検知処理部１４３は、衝突を探索する処理部である。例えば、衝突検知処理部１４３は、新たな特徴点が点列データ１３１に格納されるごとに、新たな特徴点が既に記憶された特徴点のいずれかと一致するか否かを判定する。衝突検知処理部１４３は、新たな特徴点が既に記憶された特徴点のいずれかと一致する場合には、２つの特徴点の一致を衝突として検出する。すなわち、２つの特徴点が衝突する場合には、下記の式（９）が成り立つ。なお、式（９）のｋは、衝突した２つの特徴点のｉの差分である。
【００４０】
Ｑｉ＝Ｑｉ＋ｋ・・・（９）
【００４１】
続いて、衝突検知処理部１４３は、衝突した２つの特徴点に対応するｕｉ，ｖｉ，ｕｉ＋ｋ，ｖｉ＋ｋを解算出処理部１４４に出力する。なお、衝突検知処理部１４３は、衝突を検出するまで衝突を探索する。
【００４２】
図２に示す例では、衝突検知処理部１４３は、特徴点Ｑ３５＝４５００が点列データ１３１に格納された時点で、特徴点Ｑ３５が既に記憶された特徴点のいずれかと一致するか否かを判定する。衝突検知処理部１４３は、特徴点Ｑ３５＝４５００が特徴点Ｑ１７＝４５００と一致するので、特徴点Ｑ３５と特徴点Ｑ１７の衝突を検出する。そして、衝突検知処理部１４３は、ｕ１７，ｖ１７，ｕ３５，ｖ３５の値を解算出処理部１４４に出力する。
【００４３】
解算出処理部１４４は、解を算出する処理部である。例えば、解算出処理部１４４は、衝突検知処理部１４３から受け付けたｕ１７，ｖ１７，ｕ３５，ｖ３５の値を用いて、秘密鍵ｘを算出する。
【００４４】
ここで、解算出処理部１４４が秘密鍵ｘを算出するために用いる式について説明する。まず、点Ｑｉの式（８）および２点の衝突によって得られる式（９）から、下記の式（１０）が導かれる。そして、式（１０）に離散対数問題の条件式β＝αｘをあてはめると、下記の式（１１）が導かれる。
【００４５】
α＾｛ｕｉ｝＊β＾｛ｖｉ｝＝α＾｛ｕｉ＋ｋ｝＊β＾｛ｖｉ＋ｋ｝・・・（１０）
【００４６】
ｘ＝（ｕｉ−ｕｉ＋ｋ）／（ｖｉ＋ｋ−ｖｉ）・・・（１１）
【００４７】
すなわち、解算出処理部１４４は、衝突検知処理部１４３から受け付けたｕｉ，ｖｉ，ｕｉ＋ｋ，ｖｉ＋ｋを式（１１）に代入することで、秘密鍵ｘを算出する。そして、解算出処理部１４４は、算出した秘密鍵ｘを出力部１２０に出力する。なお、解算出処理部１４４が秘密鍵ｘを算出するのは、ｖｉ≠ｖｉ＋ｋが成り立つ場合である。これに対して、ｖｉ＝ｖｉ＋ｋが成り立つ場合には、解算出処理部１４４は、秘密鍵ｘを算出できないので、出力部１２０にＮＧを出力する。
【００４８】
なお、解算出処理部１４４は、入力部１１０から秘密鍵ｘを算出する命令を受け付けた時間を取得し、取得した時間を用いて秘密鍵ｘが算出されるまでに要した演算時間を算出しても良い。そして、解算出処理部１４４は、算出した演算時間を出力部１２０に出力しても良い。
【００４９】
次に、本実施例１にかかる暗号鍵解読装置１００の処理手順について説明する。図３は、本実施例１にかかる暗号鍵解読装置の処理手順を示すフローチャートである。例えば、図３に示す処理は、暗号鍵解読装置１００が、入力部１１０を介して秘密鍵ｘを算出する命令を受け付けたことを契機として実行される。
【００５０】
図３に示すように、暗号鍵解読装置１００は、入力部１１０を介して受け付けたパラメータを用いて初期点Ｐ０を算出し（ステップＳ１０１）、初期点Ｐ０を点Ｑ０（ｉ＝１）と設定する（ステップＳ１０２）。暗号鍵解読装置１００は、点Ｑｉ−１に対して写像Ｆを適用して点Ｑｉを生成し（ステップＳ１０３）、ｉを１インクリメントさせる（ステップＳ１０４）。暗号鍵解読装置１００は、点Ｑｉが特徴点である場合には（ステップＳ１０５，Ｙｅｓ）、点Ｑｉの情報を点列データ１３１に格納する（ステップＳ１０６）。
【００５１】
暗号鍵解読装置１００は、点Ｑｉの情報を点列データ１３１に格納するごとに、衝突を探索する（ステップＳ１０７）。暗号鍵解読装置１００は、衝突を検知した場合には（ステップＳ１０８，Ｙｅｓ）、秘密鍵ｘを算出し（ステップＳ１０９）、処理を終了する。一方、暗号鍵解読装置１００は、衝突を検知しなかった場合には（ステップＳ１０８，Ｎｏ）、ステップＳ１０３に移行する。
【００５２】
暗号鍵解読装置１００は、ステップＳ１０５において、点Ｑｉが特徴点でない場合には（ステップＳ１０５，Ｎｏ）、ｉが閾値以上であるか否かを判定する（ステップＳ１１０）。暗号鍵解読装置１００は、ｉが閾値以上である場合には（ステップＳ１１０，Ｙｅｓ）、解が算出されないと判定してＮＧを出力し（ステップＳ１１１）、処理を終了する。一方、暗号鍵解読装置１００は、ｉが閾値未満である場合には（ステップＳ１１０，Ｎｏ）、ステップＳ１０３に移行する。
【００５３】
なお、上記の処理手順では、ＮＧを出力した後に、処理を終了すると説明したが、必ずしも処理を終了しなくても良い。例えば、暗号鍵解読装置１００は、ＮＧを出力した後に、新たな初期点Ｐ０を算出し、処理を継続しても良い。具体的には、ＮＧを出力する処理であるステップＳ１１１の処理の後に、新たな初期点Ｐ０を算出する処理を実行し、ステップＳ１０３に移行しても良い。
【００５４】
次に、本実施例１にかかる暗号鍵解読装置１００の効果について説明する。従来技術では、特徴点を含まないループや自明な衝突が発生した場合には、解が算出されないにもかかわらず、演算処理が継続されていた。これに対して、暗号鍵解読装置１００は、写像Ｆの演算処理回数に上限となる閾値を設定し、演算処理回数が閾値に到達した時点で解が算出されないと判定する。このため、暗号鍵解読装置１００は、特徴点を含まないループや自明な衝突が発生した場合でも、演算処理を確実に中断でき、解読にかかる計算量の増加を防ぐことができる。
【００５５】
ここで、演算処理回数に閾値を設定する根拠を説明する。図４は、演算処理回数に閾値を設定する根拠を説明するための図である。図４に示す例では、点Ｑｉの数値の下位２桁が００である点を特徴点とした場合を説明する。図４に示すグラフの横軸は、写像Ｆの演算処理回数ｉを示し、縦軸は、特徴点が生成される確率を示す。図４に示すように、特徴点が生成される確率は、写像Ｆの演算処理回数ｉの増加に伴って上昇するものの、１００回目をピークとして、その後低下する。特に、写像Ｆの演算処理回数ｉが１０００回を超えた場合に、特徴点がほとんど出力されなくなるのは、特徴点を含まないループが発生したか、あるいは自明な衝突が発生したものと推測されるからである。このため、判定処理部１４２で用いられる閾値は、１０００、すなわち、特徴点が出力される確率が最も高い演算処理回数ｉの１０倍に設定されることが望ましい。なお、閾値については、この例示に限るものではなく、暗号鍵解読装置１００を利用する者が任意の値に設定してよい。
【実施例２】
【００５６】
次に、本実施例２にかかる暗号鍵解読装置の構成の一例について説明する。図５は、本実施例２にかかる暗号鍵解読装置の構成を示す図である。図５に示すように、この暗号鍵解読装置２００は、入力部１１０、出力部１２０、記憶部１３０、制御部２４０を有する。このうち、図５に示す入力部１１０、出力部１２０、記憶部１３０の説明は、図１に示した入力部１１０、出力部１２０、記憶部１３０の説明と同様である。
【００５７】
制御部２４０は、点列生成処理部１４１、判定処理部２４２、衝突検知処理部１４３、解算出処理部１４４を有する。このうち、図５に示す点列生成処理部１４１、衝突検知処理部１４３、解算出処理部１４４の説明は、図１に示した点列生成処理部１４１、衝突検知処理部１４３、解算出処理部１４４の説明と同様である。
【００５８】
判定処理部２４２は、点列生成処理部１４１において生成された点のうち、特徴点でないと判定された点を判定点として設定し、設定した判定点と一致する点が生成された時点で、今後、解が算出されないと判定する処理部である。
【００５９】
具体的には、判定処理部２４２は、点列生成処理部１４１が生成した点のうち、特徴点でない一点を判定点Ｒとして保存する。この判定点Ｒは、点Ｑ０が初期点として保存され、写像Ｆの演算処理回数が回数ｍに到達する度に、ｍ回目に生成された点Ｑｉに更新される値である。例えば、ｍが１０である場合には、判定点Ｒは、最初に点Ｑ０が保存され、点Ｑ１０，点Ｑ２０，点Ｑ３０・・・と更新される。なお、回数ｍについては、この例示に限るものではなく、暗号鍵解読装置１００を利用する者が任意の値に設定してよい。
【００６０】
また、判定処理部２４２は、点列生成処理部１４１が点Ｑｉを生成するごとに、点Ｑｉが判定点Ｒと一致するか否かを判定する。判定処理部２４２は、点Ｑｉが判定点Ｒと一致する場合には、解が算出されないと判定し、出力部１２０にＮＧを出力する。これに対して、判定処理部２４２は、点Ｑｉが判定点Ｒと一致しない場合には、次の点Ｑｉの情報を受け付けるまで待機する。
【００６１】
次に、本実施例２にかかる暗号鍵解読装置２００の処理手順について説明する。図６は、本実施例２にかかる暗号鍵解読装置の処理手順を示すフローチャートである。例えば、図６に示す処理は、暗号鍵解読装置２００が、入力部１１０を介して秘密鍵ｘを算出する命令を受け付けたことを契機として実行される。
【００６２】
図６に示すように、暗号鍵解読装置２００は、入力部１１０を介して受け付けたパラメータを用いて初期点Ｐ０を算出し（ステップＳ２０１）、初期点Ｐ０を点Ｑ０（ｉ＝１）と設定し、さらに点Ｑ０を判定点Ｒ（ｊ＝１）と設定する（ステップＳ２０２）。なお、このｊは、判定処理部２４２が判定点Ｒの更新タイミングを管理するために設定される値である。ｊは、点Ｑｉが写像される度に１インクリメントされ、回数ｍに達する度に１に再設定される。
【００６３】
暗号鍵解読装置２００は、点Ｑｉ−１に対して写像Ｆを適用して点Ｑｉを生成し（ステップＳ２０３）、ｉおよびｊをそれぞれ１インクリメントさせる（ステップＳ２０４）。暗号鍵解読装置２００は、点Ｑｉが特徴点である場合には（ステップＳ２０５，Ｙｅｓ）、点Ｑｉの情報を点列データ１３１に格納する（ステップＳ２０６）。
【００６４】
暗号鍵解読装置２００は、点Ｑｉの情報を点列データ１３１に格納するごとに、衝突を探索する（ステップＳ２０７）。暗号鍵解読装置２００は、衝突を検知した場合には（ステップＳ２０８，Ｙｅｓ）、秘密鍵ｘを算出し（ステップＳ２０９）、処理を終了する。一方、暗号鍵解読装置２００は、衝突を検知しなかった場合には（ステップＳ２０８，Ｎｏ）、ステップＳ２０３に移行する。
【００６５】
暗号鍵解読装置２００は、ステップＳ２０５において、点Ｑｉが特徴点でない場合には（ステップＳ２０５，Ｎｏ）、点Ｑｉが判定点Ｒと一致するか否かを判定する（ステップＳ２１０）。暗号鍵解読装置２００は、点Ｑｉが判定点Ｒと一致する場合には（ステップＳ２１０，Ｙｅｓ）、解が算出されないと判定してＮＧを出力し（ステップＳ２１１）、処理を終了する。一方、暗号鍵解読装置２００は、点Ｑｉが判定点Ｒと一致しない場合には（ステップＳ２１０，Ｎｏ）、ｊがｍに到達する度に、判定点Ｒを点Ｑｉに更新するとともに、ｊを１に設定し（ステップＳ２１２）、ステップＳ２０３に移行する。
【００６６】
なお、上記の処理手順では、ＮＧを出力した後に、処理を終了すると説明したが、必ずしも処理を終了しなくても良い。例えば、暗号鍵解読装置２００は、ＮＧを出力した後に、新たな初期点Ｐ０を算出し、処理を継続しても良い。具体的には、ＮＧを出力する処理であるステップＳ２１１の処理の後に、新たな初期点Ｐ０を算出する処理を実行し、ステップＳ２０３に移行しても良い。
【００６７】
次に、本実施例２にかかる暗号鍵解読装置２００の効果について説明する。図１４および図１５に示したように、従来技術では、特徴点を含まないループや自明な衝突が発生し、ループが形成された場合には、解が算出されないにもかかわらず、演算処理が継続されていた。これに対して、暗号鍵解読装置２００は、生成した点のうち、特徴点でない点を判定点として設定し、演算処理が所定回数に到達する度に、判定点を新たな点に更新する。このため、特徴点を含まないループや自明な衝突が発生した場合には、ループ上の点のいずれかが判定点に設定されるので、暗号鍵解読装置２００は、判定点と今後生成される点との衝突を判定することで、今後解が算出されないということを早期に検出できる。したがって、暗号鍵解読装置２００は、特徴点を含まないループや自明な衝突が発生した場合でも、演算処理を早期に中断でき、解読にかかる計算量を削減することができる。
【００６８】
ところで、図５に示した暗号鍵解読装置２００の構成は一例であり、暗号鍵解読装置２００は、必ずしも図５に示した各処理部を全て有していなくても良い。例えば、暗号鍵解読装置２００は、点生成部と判定点記憶部と判定部の機能を有していれば良い。
【００６９】
このうち、点生成部は、点に対して写像を実行し、写像の実行結果となる点に対して再度写像を実行する処理を繰り返し実行することで複数の点を生成する処理部である。この点生成部は、点列生成処理部１４１に対応する。判定点記憶部は、点生成部によって生成された点が、所定の特徴を有する特徴点であるか否かを判定し、特徴点でないと判定した点を判定点として記憶装置に記憶する処理部である。この判定点記憶部は、点列生成処理部１４１と判定処理部２４２とに対応する。また、判定部は、点生成部によって生成された点と前記記憶装置に記憶された判定点とを比較して、前記点と判定点とが一致した場合に、特徴点同士の衝突が起こらないと判定する処理部である。この判定部は、判定処理部２４２に対応する。
【実施例３】
【００７０】
次に、本実施例３にかかる暗号鍵解読装置の構成の一例について説明する。図７は、本実施例３にかかる暗号鍵解読装置の構成を示す図である。図７に示すように、この暗号鍵解読装置３００は、入力部１１０、出力部１２０、記憶部１３０、制御部３４０を有する。このうち、図７に示す入力部１１０、出力部１２０、記憶部１３０の説明は、図１に示した入力部１１０、出力部１２０、記憶部１３０の説明と同様である。
【００７１】
制御部３４０は、点列生成処理部１４１、判定処理部３４２、衝突検知処理部１４３、解算出処理部１４４を有する。このうち、図７に示す点列生成処理部１４１、衝突検知処理部１４３、解算出処理部１４４の説明は、図１に示した点列生成処理部１４１、衝突検知処理部１４３、解算出処理部１４４の説明と同様である。
【００７２】
判定処理部３４２は、図１に示した判定処理部１４２と同様の機能と、図５に示した判定処理部２４２と同様の機能とを有する。すなわち、判定処理部３４２は、点列生成処理部１４１による演算処理回数と所定の閾値とを比較し、演算処理回数が所定の閾値以上である場合に、解が算出されないと判定する。また、判定処理部３４２は、点列生成処理部１４１において生成された点のうち、特徴点でないと判定された点を判定点として設定し、設定した判定点と一致する点が生成された時点で、解が算出されないと判定する。
【００７３】
次に、本実施例３にかかる暗号鍵解読装置３００の処理手順について説明する。図８は、本実施例３にかかる暗号鍵解読装置の処理手順を示すフローチャートである。例えば、図８に示す処理は、暗号鍵解読装置３００が、入力部１１０を介して秘密鍵ｘを算出する命令を受け付けたことを契機として実行される。
【００７４】
図８に示すように、暗号鍵解読装置３００は、入力部１１０を介して受け付けたパラメータを用いて初期点Ｐ０を算出し（ステップＳ３０１）、初期点Ｐ０を点Ｑ０（ｉ＝１）と設定し、さらに点Ｑ０を判定点Ｒ（ｊ＝１）と設定する（ステップＳ３０２）。暗号鍵解読装置３００は、点Ｑｉ−１に対して写像Ｆを適用して点Ｑｉを生成し（ステップＳ３０３）、ｉおよびｊをそれぞれ１インクリメントさせる（ステップＳ３０４）。暗号鍵解読装置３００は、点Ｑｉが特徴点である場合には（ステップＳ３０５，Ｙｅｓ）、点Ｑｉの情報を点列データ１３１に格納する（ステップＳ３０６）。
【００７５】
暗号鍵解読装置３００は、点Ｑｉの情報を点列データ１３１に格納するごとに、衝突を探索する（ステップＳ３０７）。暗号鍵解読装置３００は、衝突を検知した場合には（ステップＳ３０８，Ｙｅｓ）、秘密鍵ｘを算出し（ステップＳ３０９）、処理を終了する。一方、暗号鍵解読装置３００は、衝突を検知しなかった場合には（ステップＳ３０８，Ｎｏ）、ステップＳ３０３に移行する。
【００７６】
暗号鍵解読装置３００は、ステップＳ３０５において、点Ｑｉが特徴点でない場合には（ステップＳ３０５，Ｎｏ）、ｉが閾値以上であるか否かを判定する（ステップＳ３１０）。暗号鍵解読装置３００は、ｉが閾値以上である場合には（ステップＳ３１０，Ｙｅｓ）、解が算出されないと判定してＮＧを出力し（ステップＳ３１１）、処理を終了する。一方、暗号鍵解読装置３００は、ｉが閾値未満である場合には（ステップＳ３１０，Ｎｏ）、点Ｑｉが判定点Ｒと一致するか否かを判定する（ステップＳ３１２）。暗号鍵解読装置３００は、点Ｑｉが判定点Ｒと一致する場合には（ステップＳ３１２，Ｙｅｓ）、ステップＳ３１１に移行する。一方、暗号鍵解読装置３００は、点Ｑｉが判定点Ｒと一致しない場合には（ステップＳ３１２，Ｎｏ）、ｊがｍに到達する度に、判定点Ｒを点Ｑｉに更新するとともに、ｊを１に設定し（ステップＳ３１３）、ステップＳ３０３に移行する。
【００７７】
なお、上記の処理手順では、ＮＧを出力した後に、処理を終了すると説明したが、必ずしも処理を終了しなくても良い。例えば、暗号鍵解読装置３００は、ＮＧを出力した後に、新たな初期点Ｐ０を算出し、処理を継続しても良い。具体的には、ＮＧを出力する処理であるステップＳ３１１の処理の後に、新たな初期点Ｐ０を算出する処理を実行し、ステップＳ３０３に移行しても良い。
【００７８】
また、上記の処理手順は、上記の順番に限定されるものではなく、処理内容を矛盾させない範囲で適宜変更されても良い。例えば、上記の処理手順では、ｉが閾値以上であるか否かを判定する処理を実行した後に、点Ｑｉが判定点Ｒと一致するか否かを判定する処理を実行すると説明したが、これらの処理を逆の順序で実行しても良い。具体的には、ｉが閾値以上であるか否かを判定する処理であるステップＳ３１０の処理は、点Ｑｉが判定点Ｒと一致するか否かを判定する処理であるステップＳ３１２〜ステップＳ３１３の処理の後に実行されても良い。
【００７９】
次に、本実施例３にかかる暗号鍵解読装置３００の効果について説明する。従来技術では、特徴点を含まないループや自明な衝突が発生した場合には、解が算出されないにもかかわらず、演算処理が継続されていた。これに対して、暗号鍵解読装置３００は、特徴点を含まないループや自明な衝突が発生した場合でも、判定点を用いることで、演算処理を早期に中断でき、解読にかかる計算量を削減できる。
【００８０】
また、判定点と一致する点が検出されない場合でも、衝突が発生しないことが原因で、演算処理回数が増加してしまう場合がある。このような場合には、図４に示したように、演算処理回数が増加するほど、特徴点が生成される確率は低下するので、解が算出され難くなる。これに対して、暗号鍵解読装置３００は、演算処理回数に閾値を設定することで、演算処理を確実に中断でき、解読にかかる計算量の増加を防止できる。
【００８１】
ここで、本実施例１〜３にかかる暗号鍵解読装置の効果を比較して説明する。図９は、本実施例１〜３にかかる暗号鍵解読装置の効果を比較して説明するための図である。図９に示す例では、点Ｑｉの数値の下位２桁が００である点を特徴点とし、演算処理回数の閾値を１０００とし、ｍ＝１０とした場合を説明する。図９に示すように、従来の特徴点を導入しない技術では、写像Ｆを用いて生成した全ての点を記憶して衝突を探索するので、衝突を必ず検知できる。しかし、この従来技術では、全ての点を記憶する必要があるのでメモリ使用量が膨大になっていた。また、この従来技術では、全ての点を用いて衝突を探索するので、衝突の検知速度は遅かった。
【００８２】
これに対して、本実施例１にかかる暗号鍵解読装置１００は、特徴点のみを記憶するので、メモリ使用量が削減される。また、暗号鍵解読装置１００は、特徴点のみを用いて衝突を探索するので、従来技術に比べて処理速度が上がり、衝突を早く検出できる。また、暗号鍵解読装置１００は、特徴点を含まないループや自明な衝突が発生した場合でも、演算処理回数の上限を設定するので、演算処理を確実に中断でき、無駄な点を１０００個以内に抑えることができる。このため、暗号鍵解読装置１００は、新たな初期点Ｐ０を生成することで、演算処理を再び実行できるので、衝突を確実に検出できる。
【００８３】
また、本実施例２にかかる暗号鍵解読装置２００は、特徴点を含まないループや自明な衝突が発生した場合でも、判定点を用いることで、演算処理を早期に中断でき、無駄な点を１０個程度に抑えることができる。このため、暗号鍵解読装置１００は、演算処理回数が少ない段階で新たな初期点Ｐ０を生成し、演算処理を再び実行できるので、衝突を早期に検出できる。
【００８４】
しかし、暗号鍵解読装置２００は、判定点と一致する点を検出しない場合でも、衝突が発生しないことが原因で、演算処理回数が増加してしまう場合があった。これに対して、本実施例３にかかる暗号鍵解読装置３００は、演算処理回数の上限を設定するので、演算処理を確実に中断でき、無駄な点を１０００個以内に抑えることができる。このため、暗号鍵解読装置３００は、衝突を早期に、かつ、確実に検出できる。
【００８５】
また、図１，５，７に示した記憶部１３０は、例えば、ＲＡＭ（Random Access Memory）、ＲＯＭ（Read Only Memory）、フラッシュメモリ（Flash Memory）などの半導体メモリ素子、ハードディスクや光ディスクなどの記憶装置に対応する。また、図１，５，７に示した制御部１４０，２４０，３４０は、例えば、ＡＳＩＣ（Application Specific Integrated Circuit）やＦＰＧＡ（Field Programmable Gate Array）などの集積装置に対応する。または、制御部１４０，２４０，３４０は、例えば、ＣＰＵ（Central Processing Unit）やＭＰＵ（Micro Processing Unit）などの電子回路に対応する。
【００８６】
また、本実施例１〜３において説明した各処理のうち、自動的に行われるものとして説明した処理の全部または一部を手動的に行うこともでき、あるいは、手動的に行われるものとして説明した処理の全部または一部を公知の方法で自動的に行うこともできる。この他、上述文書中や図面中で示した処理手順、制御手順、具体的名称、各種のデータやパラメータを含む情報については、特記する場合を除いて任意に変更することができる。
【００８７】
また、図示した各装置の各構成要素は機能概念的なものであり、必ずしも物理的に図示の如く構成されていることを要しない。すなわち、各装置の分散・統合の具体的形態は図示のものに限られず、その全部または一部を、各種の負荷や使用状況などに応じて、任意の単位で機能的または物理的に分散・統合して構成することができる。例えば、図１に示した点列生成処理部１４１〜解算出処理部１４４のうちいずれかの機能をサーバに持たせ、かかるサーバと暗号鍵解読装置１００とが協働することで、解が算出されないことを判定しても良い。
【００８８】
また、暗号鍵解読装置１００〜３００は、既知のパーソナルコンピュータ、ワークステーション、携帯電話、ＰＨＳ端末、移動体通信端末またはＰＤＡなどの情報処理装置に、暗号鍵解読装置１００〜３００の各機能を搭載することによって実現することもできる。
【００８９】
図１０は、本実施例にかかる暗号鍵解読装置を構成するコンピュータのハードウェア構成を示す図である。図１０に示すように、このコンピュータ４００は、各種演算処理を実行するＣＰＵ４０１と、ユーザからのデータの入力を受け付ける入力装置４０２と、モニタ４０３を有する。また、コンピュータ４００は、記憶媒体からプログラム等を読み取る媒体読み取り装置４０４と、ネットワークを介して他のコンピュータとの間でデータの授受を行うネットワークインターフェース装置４０５を有する。また、コンピュータ４００は、各種情報を一時記憶するＲＡＭ（Random Access Memory）４０６と、ハードディスク装置４０７を有する。各装置４０１〜４０７は、バス４０８に接続される。
【００９０】
そして、ハードディスク装置４０７は、図１，５，７に示した、点列生成処理部１４１、判定処理部１４２，２４２，３４２、衝突検知処理部１４３、解算出処理部１４４と同様の機能を有する暗号鍵解読プログラム４０７ａを記憶する。また、ハードディスク装置４０７は、図１，５，７に示した点列データ１３１に対応する点列データ４０７ｂを記憶する。
【００９１】
ＣＰＵ４０１が暗号鍵解読プログラム４０７ａをハードディスク装置４０７から読み出してＲＡＭ４０６に展開することにより、暗号鍵解読プログラム４０７ａは、暗号鍵解読プロセス４０６ａとして機能する。そして、ＣＰＵ４０１がハードディスク装置４０７から点列データ４０７ｂを読み出して、ＲＡＭ４０６に点列データ４０６ｂを展開し、暗号鍵解読プロセス４０６ａが点列データ４０６ｂを利用して処理を実行する。
【００９２】
なお、上記の暗号鍵解読プログラム４０７ａは、必ずしもハードディスク装置４０７に記憶されている必要はない。例えば、ＣＤ−ＲＯＭ等の記憶媒体に記憶されたプログラムを、コンピュータ４００が読み出して実行するようにしても良い。また、公衆回線、インターネット、ＬＡＮ（Local Area Network）、ＷＡＮ（Wide Area Network）等にこのプログラムを記憶させておき、コンピュータ４００がこれらからプログラムを読み出して実行するようにしても良い。
【００９３】
以上の各実施例を含む実施形態に関し、さらに以下の付記を開示する。
【００９４】
（付記１）コンピュータが、
点に対して写像を実行し、該写像の実行結果となる点に対して再度前記写像を実行する処理を繰り返し実行することで複数の点を生成する点生成ステップと、
前記点生成ステップによって生成された点が、所定の特徴を有する特徴点であるか否かを判定し、特徴点でないと判定した点を判定点として記憶装置に記憶する判定点記憶ステップと、
前記点生成ステップによって生成された点と前記記憶装置に記憶された判定点とを比較して、前記点と判定点とが一致した場合に、特徴点同士の衝突が起こらないと判定する判定ステップと
を実行することを特徴とする暗号鍵解読方法。
【００９５】
（付記２）前記写像が所定回数実行される毎に、前記記憶装置に記憶された判定点を新たに生成された点に更新する判定点更新ステップを更に実行することを特徴とする付記１に記載の暗号鍵解読方法。
【００９６】
（付記３）前記判定ステップは、前記写像が実行された回数と閾値とを比較し、写像が実行された回数が閾値以上である場合に、特徴点同士の衝突が起こらないと更に判定することを特徴とする付記１または２に記載の暗号鍵解読方法。
【００９７】
（付記４）点に対して写像を実行し、該写像の実行結果となる点に対して再度前記写像を実行する処理を繰り返し実行することで複数の点を生成する点生成部と、
前記点生成部によって生成された点が、所定の特徴を有する特徴点であるか否かを判定し、特徴点でないと判定した点を判定点として記憶装置に記憶する判定点記憶部と、
前記点生成部によって生成された点と前記記憶装置に記憶された判定点とを比較して、前記点と判定点とが一致した場合に、特徴点同士の衝突が起こらないと判定する判定部と
を備えたことを特徴とする暗号鍵解読装置。
【００９８】
（付記５）前記写像が所定回数実行される毎に、前記記憶装置に記憶された判定点を新たに生成された点に更新する判定点更新部を更に備えたことを特徴とする付記４に記載の暗号鍵解読装置。
【００９９】
（付記６）前記判定部は、前記写像が実行された回数と閾値とを比較し、写像が実行された回数が閾値以上である場合に、特徴点同士の衝突が起こらないと更に判定することを特徴とする付記４または５に記載の暗号鍵解読装置。
【０１００】
（付記７）コンピュータに、
点に対して写像を実行し、該写像の実行結果となる点に対して再度前記写像を実行する処理を繰り返し実行することで複数の点を生成する点生成手順と、
前記点生成手順によって生成された点が、所定の特徴を有する特徴点であるか否かを判定し、特徴点でないと判定した点を判定点として記憶装置に記憶する判定点記憶手順と、
前記点生成手順によって生成された点と前記記憶装置に記憶された判定点とを比較して、前記点と判定点とが一致した場合に、特徴点同士の衝突が起こらないと判定する判定手順と
を実行させることを特徴とする暗号鍵解読プログラム。
【０１０１】
（付記８）前記写像が所定回数実行される毎に、前記記憶装置に記憶された判定点を新たに生成された点に更新する判定点更新手順を更に実行させることを特徴とする付記７に記載の暗号鍵解読プログラム。
【０１０２】
（付記９）前記判定手順は、前記写像が実行された回数と閾値とを比較し、写像が実行された回数が閾値以上である場合に、特徴点同士の衝突が起こらないと更に判定することを特徴とする付記７または８に記載の暗号鍵解読プログラム。
【符号の説明】
【０１０３】
１００ 暗号鍵解読装置
１１０ 入力部
１２０ 出力部
１３０ 記憶部
１３１ 点列データ
１４０ 制御部
１４１ 点列生成処理部
１４２ 判定処理部
１４３ 衝突検知処理部
１４４ 解算出処理部
２００ 暗号鍵解読装置
２４０ 制御部
２４２ 判定処理部
３００ 暗号鍵解読装置
３４０ 制御部
３４２ 判定処理部
【特許請求の範囲】
【請求項１】
コンピュータが、
点に対して写像を実行し、該写像の実行結果となる点に対して再度前記写像を実行する処理を繰り返し実行することで複数の点を生成する点生成ステップと、
前記点生成ステップによって生成された点が、所定の特徴を有する特徴点であるか否かを判定し、特徴点でないと判定した点を判定点として記憶装置に記憶する判定点記憶ステップと、
前記点生成ステップによって生成された点と前記記憶装置に記憶された判定点とを比較して、前記点と判定点とが一致した場合に、特徴点同士の衝突が起こらないと判定する判定ステップと
を実行することを特徴とする暗号鍵解読方法。
【請求項２】
前記写像が所定回数実行される毎に、前記記憶装置に記憶された判定点を新たに生成された点に更新する判定点更新ステップを更に実行することを特徴とする請求項１に記載の暗号鍵解読方法。
【請求項３】
前記判定ステップは、前記写像が実行された回数と閾値とを比較し、写像が実行された回数が閾値以上である場合に、特徴点同士の衝突が起こらないと更に判定することを特徴とする請求項１または２に記載の暗号鍵解読方法。
【請求項４】
点に対して写像を実行し、該写像の実行結果となる点に対して再度前記写像を実行する処理を繰り返し実行することで複数の点を生成する点生成部と、
前記点生成部によって生成された点が、所定の特徴を有する特徴点であるか否かを判定し、特徴点でないと判定した点を判定点として記憶装置に記憶する判定点記憶部と、
前記点生成部によって生成された点と前記記憶装置に記憶された判定点とを比較して、前記点と判定点とが一致した場合に、特徴点同士の衝突が起こらないと判定する判定部と
を備えたことを特徴とする暗号鍵解読装置。
【請求項５】
コンピュータに、
点に対して写像を実行し、該写像の実行結果となる点に対して再度前記写像を実行する処理を繰り返し実行することで複数の点を生成する点生成手順と、
前記点生成手順によって生成された点が、所定の特徴を有する特徴点であるか否かを判定し、特徴点でないと判定した点を判定点として記憶装置に記憶する判定点記憶手順と、
前記点生成手順によって生成された点と前記記憶装置に記憶された判定点とを比較して、前記点と判定点とが一致した場合に、特徴点同士の衝突が起こらないと判定する判定手順と
を実行させることを特徴とする暗号鍵解読プログラム。
【請求項１】
コンピュータが、
点に対して写像を実行し、該写像の実行結果となる点に対して再度前記写像を実行する処理を繰り返し実行することで複数の点を生成する点生成ステップと、
前記点生成ステップによって生成された点が、所定の特徴を有する特徴点であるか否かを判定し、特徴点でないと判定した点を判定点として記憶装置に記憶する判定点記憶ステップと、
前記点生成ステップによって生成された点と前記記憶装置に記憶された判定点とを比較して、前記点と判定点とが一致した場合に、特徴点同士の衝突が起こらないと判定する判定ステップと
を実行することを特徴とする暗号鍵解読方法。
【請求項２】
前記写像が所定回数実行される毎に、前記記憶装置に記憶された判定点を新たに生成された点に更新する判定点更新ステップを更に実行することを特徴とする請求項１に記載の暗号鍵解読方法。
【請求項３】
前記判定ステップは、前記写像が実行された回数と閾値とを比較し、写像が実行された回数が閾値以上である場合に、特徴点同士の衝突が起こらないと更に判定することを特徴とする請求項１または２に記載の暗号鍵解読方法。
【請求項４】
点に対して写像を実行し、該写像の実行結果となる点に対して再度前記写像を実行する処理を繰り返し実行することで複数の点を生成する点生成部と、
前記点生成部によって生成された点が、所定の特徴を有する特徴点であるか否かを判定し、特徴点でないと判定した点を判定点として記憶装置に記憶する判定点記憶部と、
前記点生成部によって生成された点と前記記憶装置に記憶された判定点とを比較して、前記点と判定点とが一致した場合に、特徴点同士の衝突が起こらないと判定する判定部と
を備えたことを特徴とする暗号鍵解読装置。
【請求項５】
コンピュータに、
点に対して写像を実行し、該写像の実行結果となる点に対して再度前記写像を実行する処理を繰り返し実行することで複数の点を生成する点生成手順と、
前記点生成手順によって生成された点が、所定の特徴を有する特徴点であるか否かを判定し、特徴点でないと判定した点を判定点として記憶装置に記憶する判定点記憶手順と、
前記点生成手順によって生成された点と前記記憶装置に記憶された判定点とを比較して、前記点と判定点とが一致した場合に、特徴点同士の衝突が起こらないと判定する判定手順と
を実行させることを特徴とする暗号鍵解読プログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【公開番号】特開２０１２−３２５９６（Ｐ２０１２−３２５９６Ａ）
【公開日】平成２４年２月１６日（２０１２．２．１６）
【国際特許分類】
【出願番号】特願２０１０−１７１７５０（Ｐ２０１０−１７１７５０）
【出願日】平成２２年７月３０日（２０１０．７．３０）
【国等の委託研究の成果に係る記載事項】（出願人による申告）平成２０年度、独立行政法人情報通信研究機構、「適切な暗号技術を選択可能とするための新しい暗号技術の評価手法 〜暗号の技術評価に関する研究開発〜」委託研究、産業技術力強化法第１９条の適用を受ける特許出願
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【Ｆターム（参考）】
【公開日】平成２４年２月１６日（２０１２．２．１６）
【国際特許分類】
【出願日】平成２２年７月３０日（２０１０．７．３０）
【国等の委託研究の成果に係る記載事項】（出願人による申告）平成２０年度、独立行政法人情報通信研究機構、「適切な暗号技術を選択可能とするための新しい暗号技術の評価手法 〜暗号の技術評価に関する研究開発〜」委託研究、産業技術力強化法第１９条の適用を受ける特許出願
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【Ｆターム（参考）】
[ Back to top ]