暗号鍵解析方法、暗号鍵解析装置および暗号鍵解析プログラム
【課題】点を生成する処理と各点の衝突を検出する処理との並列化を効率的に行うこと。
【解決手段】データビット長算出部１４３が、検査データのビット長ｌを、衝突検知までに必要なデータ量の期待値と、特徴点の出現頻度とを基に算出する。衝突検知依頼部１４４は、点生成部１２０ａ〜１２０ｃが生成した特徴点から、ビット長ｌの検査データを抽出し、衝突検知部１３０ａ〜１３０ｃに各検査データが一致するか否かの判定依頼を行う。解算出部１４５は、一致した検査データに対応する特徴点同士を改めて比較して、衝突しているか否かを判定し、解を算出する。
【解決手段】データビット長算出部１４３が、検査データのビット長ｌを、衝突検知までに必要なデータ量の期待値と、特徴点の出現頻度とを基に算出する。衝突検知依頼部１４４は、点生成部１２０ａ〜１２０ｃが生成した特徴点から、ビット長ｌの検査データを抽出し、衝突検知部１３０ａ〜１３０ｃに各検査データが一致するか否かの判定依頼を行う。解算出部１４５は、一致した検査データに対応する特徴点同士を改めて比較して、衝突しているか否かを判定し、解を算出する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号鍵解析方法、暗号鍵解析装置および暗号鍵解析プログラムに関する。
【背景技術】
【０００２】
近年、情報漏洩を防止する暗号技術の一つとして、公開鍵暗号が知られている。この公開鍵暗号は、受信者が公開する公開鍵によって送信者が暗号化を行い、受信者は未公開の秘密鍵によって復号を行うものである。
【０００３】
現在標準の公開鍵暗号は、公開鍵に基づいて秘密鍵を解読するための計算量が膨大であることを安全性の根拠としている。その一方で解読技術や実装技術は日に日に改良が加えられ、また計算能力も日々増加している。そのため、今後も安全な暗号を利用し続けるためには、現状および今後の計算能力の見積もりを行い、容易に解読できないような計算量となるように、鍵ビット長などの暗号パラメータを適切に設計する必要がある。そのためには、解読実験をおこなって、暗号の安全性、強度を評価することが重要である。
【０００４】
公開鍵暗号には、離散対数問題に基づいて設計された楕円曲線暗号等がある。離散対数問題とは、「素数ｐに対して、有限体ＧＦ（ｐ）の生成元αを固定した場合に、有限体ＧＦ（ｐ）の元βに対して、β＝αｘを満たす整数ｘを求めよ」というものである。
【０００５】
この離散対数問題を解読する方法の一つにPollardのρ法がある。このρ法は、写像ＦによってＰｉ−１から次のＰｉを順次算出し、異なるｉ、ｊに対してＰｉ＝Ｐｊとなるものを見つけることで、公開鍵暗号の秘密鍵を解くというものである。
【０００６】
ここで、写像Ｆは、下記の式（１）によって示される。この写像により、下記の式（２）が成り立つｕｉおよびｖｉを一意に算出することができる。また、Ｐｉ＝Ｐｊとなることを衝突と呼ぶ。例えば、Ｐｉ＝Ｐｊで衝突がおこると、式（３）の関係が成り立ち、解を求めることができる。具体的には、式（４）によって解を求めることができる。ただし、ｖｊ≠ｖｉとする。
【０００７】
Ｐｉ＝Ｆ（Ｐｉ−１）・・・（１）
Ｐｉ＝α＾｛ｕｉ｝＊β＾｛ｖｉ｝・・・（２）
α＾｛ｕｉ｝＊β＾｛ｖｉ｝＝α＾｛ｕｊ｝＊β＾｛ｖｊ｝・・・（３）
ｘ＝（ｕｉ−ｕｊ）／（ｖｊ−ｖｉ）・・・（４）
【０００８】
図７は、ρ法の原理を説明するための図である。図７に示す例では、初期点Ｐ０として、写像Ｆを繰り返し実行することで、Ｐ１、Ｐ２、・・・Ｐｉ＋５、・・・、Ｐｊが順次求められている。図７に示すように写像Ｆを繰り返し実行していくと、Ｐｉ＝Ｐｊにおいて衝突が発生する。このため、式（４）に基づいて解が求まる。
【０００９】
なお、上記のρ法では、写像Ｆによって算出した多数の点Ｐｉを全て記憶するため、メモリ使用量が膨大になってしまうという問題があった。このメモリ使用量を削減する技術として、特徴点（distinguished point）を導入したρ法が存在する。この特徴点を導入したρ法は、写像Ｆによって算出した点Ｐｉのうち、所定の特徴を有する特徴点のみを記憶し、衝突を検出するものである。
【００１０】
図８は、特徴点を導入したρ法を説明するための図である。なお実際の楕円曲線上の点Ｐｉは、２変数（Ｘｉ、Ｙｉ）のベクトル値として表されるが、ここではρ法の簡易な説明のためスカラー値を用いる。図８に示す例では、Ｐｉの下２桁が００となる点を特徴点とする。特徴点を白丸で示し、それ以外の点を黒丸で示す。例えば、Ｐ３、Ｐ１７、Ｐ２９、Ｐ３５は、下２桁が００となるため、Ｐ３、Ｐ１７、Ｐ２９、Ｐ３５は特徴点となる。したがって、Ｐ３、Ｐ１７、Ｐ２９、Ｐ３５が保存され、特徴点以外の点は保存されない。このように、特徴点のみを保存する場合でも特徴点同士が一致すれば、衝突を検出でき、解を求めることができる。図８に示す例では、Ｐ１７＝Ｐ３５となるため、解を求めることができる。
【００１１】
図８において、全ての点を保存していれば、Ｐ１０で初めて衝突を検出可能であるが、Ｐ１０は特徴点では無い。このため、特徴点を導入したρ法では、Ｐ１０が保存されておらず、Ｐ１０で衝突を検出することができない。しかし、写像Ｆは、一意の写像であるため、特徴点がループ上に存在していれば、いずれは、Ｐｉ＝Ｐｊとなる特徴点を検出することができる。
【００１２】
ところで、従来技術では、ρ法による離散対数問題の解析を並列的に処理することで、点の生成や衝突を検出する処理を効率化させている。ここで、従来の暗号鍵解析装置の一例について説明する。図９は、従来の暗号鍵解析装置の構成を示す図である。図９に示すように、暗号鍵解析装置１０は、点生成部１ａ〜１ｃ、特徴点判定部２、特徴点記憶部３、衝突検出部４ａ〜４ｃ、解算出部５を有する。
【００１３】
点生成部１ａ〜１ｃは、式（１）に基づいて写像を繰り返し実行し、写像によって生成した点を特徴点判定部２に出力する。各点生成部１ａ〜１ｃは、それぞれ異なる初期点が入力され、この初期点から順に写像を繰り返し実行する。
【００１４】
特徴点判定部２は、点生成部１ａ〜１ｃから点を取得し、各点のうち、特徴点となる点を判定する処理部である。特徴点判定部２は、特徴点を特徴点記憶部３に登録する。特徴点記憶部３は、特徴点を記憶する記憶部である。
【００１５】
衝突検出部４ａ〜４ｃは、特徴点記憶部３から２つの特徴点を取得し、各特徴点を比較して、衝突が起こったか否かを判定する処理部である。なお、特徴点は特徴点記憶部３によって一元管理されるため、衝突検出部４ａ〜４ｃは、特徴点記憶部３に記憶された特徴点を複製して、自身のメモリに記憶し、衝突を検出する。衝突検出部４ａ〜４ｃは、衝突を検出した場合に、衝突した特徴点の識別情報を解算出部５に通知する。
【００１６】
解算出部５は、衝突した特徴点の識別情報を取得した場合に、該当する特徴点の情報を特徴点記憶部３から取り出し、各特徴点を比較することによって、秘密鍵を算出する処理部である。具体的に、解算出部５は、式（４）に基づいて、秘密鍵を算出する。
【００１７】
図９に示したように、暗号鍵解析装置１０は、複数の点生成部１ａ〜１ｃが並列的に点を生成し、複数の衝突検出部４ａ〜４ｃが並列的に各特徴点の衝突検出を実行する。このため、点の生成や衝突を効率的に実行することができる。
【先行技術文献】
【特許文献】
【００１８】
【特許文献１】特開２００４−２２９１６３号公報
【特許文献２】特開２００５−１３４４５４号公報
【特許文献３】特開２００６−４８１９２号公報
【発明の概要】
【発明が解決しようとする課題】
【００１９】
しかしながら、上述した従来技術では、点を生成する処理と各点の衝突を検出する処理との並列化を効率的に行うことができないという問題があった。
【００２０】
例えば、図９に示した従来の暗号鍵解析装置１０では、各衝突検出部４ａ〜４ｃは、特徴点記憶部３に記憶された特徴点を読み出して、特徴点の衝突を検出する。この場合、一時的に、同一の特徴点の情報が、衝突検出部４ａ〜４ｃおよび特徴点記憶部３に重複して存在することになるため、メモリ使用量が増加してしまう。
【００２１】
これに対して、特徴点記憶部３に記憶される特徴点の数を少なくすることで、メモリ使用量を削減することが考えられる。しかし、特徴点の数を少なくすると、各特徴点が衝突するまでに時間がかかってしまうため、メモリ使用量が削減されるかわりに、計算時間が増加してしまう。
【００２２】
開示の技術は、上記に鑑みてなされたものであって、点を生成する処理と各点の衝突を検出する処理との並列化を効率的に行うことができる暗号鍵解析方法、暗号鍵解析装置および暗号鍵解析プログラムを提供することを目的とする。
【課題を解決するための手段】
【００２３】
本願の開示する暗号鍵解析方法は、コンピュータが、点に対して写像を実行し、該写像の実行結果となる点に対して再度前記写像を実行する処理を繰り返し行う複数の点生成装置から点をそれぞれ取得し、取得した各点を記憶装置に記憶する記憶ステップと、前記記憶装置に記憶された複数の点から２つの点を選択し、選択した点の値の一部を検査データとしてそれぞれ抽出する抽出ステップと、前記抽出ステップが抽出した各検査データを複数の検出装置に通知することで、前記検査データが一致するか否かの判定要求を行い、各検出装置から判定結果を取得する判定要求ステップとを実行することを要件とする。
【発明の効果】
【００２４】
本願の開示する暗号鍵解析方法の一つの態様によれば、点を生成する処理と各点の衝突を検出する処理との並列化を効率的に行うことができるという効果を奏する。
【図面の簡単な説明】
【００２５】
【図１】図１は、本実施例にかかる暗号鍵解析装置の構成を示す図である。
【図２】図２は、特徴点テーブルのデータ構造の一例を示す図である。
【図３】図３は、実験環境定義ファイルのデータ構造の一例を示す図である。
【図４】図４は、本実施例にかかる暗号鍵解析装置の処理手順を示すフローチャートである。
【図５】図５は、点生成部の処理手順を示すフローチャートである。
【図６】図６は、暗号鍵解析プログラムを実行するコンピュータを示す図である。
【図７】図７は、ρ法の原理を説明するための図である。
【図８】図８は、特徴点を導入したρ法を説明するための図である。
【図９】図９は、従来の暗号鍵解析装置の構成を示す図である。
【発明を実施するための形態】
【００２６】
以下に、本願の開示する暗号鍵解析方法、暗号鍵解析装置および暗号鍵解析プログラムの実施例を図面に基づいて詳細に説明する。なお、この実施例によりこの発明が限定されるものではない。
【実施例】
【００２７】
本実施例にかかる暗号鍵解析装置の構成について説明する。図１は、本実施例にかかる暗号鍵解析装置の構成を示す図である。図１に示すように、この暗号鍵解析装置１００は、記憶部１１０と、点生成部１２０ａ〜１２０ｃと、衝突検出部１３０ａ〜１３０ｃと、制御部１４０を有する。ここでは説明の便宜上、点生成部１２０ａ〜１２０ｃ、衝突検出部１３０ａ〜１３０ｃを示す。しかし、暗号鍵解析装置１００は、その他にも、点生成部１２０、衝突検出部１３０を有しても良い。
【００２８】
記憶部１１０は、秘密鍵を解析するために必要となる各種のデータや解析結果を記憶する記憶部である。図１に示すように、記憶部１１０は、特徴点テーブル１１１と、初期点テーブル１１２と、実験環境定義ファイル１１３と、解析結果データ１１４を記憶する。
【００２９】
特徴点テーブル１１１は、点生成部１２０ａ〜１２０ｃが生成する点のうち、所定の特徴を有する特徴点の情報を記憶するテーブルである。図２は、特徴点テーブルのデータ構造の一例を示す図である。図２に示すように、特徴点テーブル１１１は、ｉ、Ｘｉ、Ｙｉ、Ｕｉ、Ｖｉを対応付けて記憶する。
【００３０】
このうち、ｉは、写像を行った回数である。Ｐｉは点の値である。Ｕｉ、Ｖｉはそれぞれ、Ｐｉを求める際に利用したαの巾指数ならびにβの巾指数であり、ＰｉとＵｉ、Ｖｉとの関係は、上記式（２）となる。Ｘｉは、ＰｉのＸ座標である。Ｙｉは、ＰｉのＹ座標である。なお、ｉの値は１０進数で表しており、Ｘｉ、Ｙｉ、Ｕｉ、Ｖｉの各値は１６進数で表している。
【００３１】
例えば、ｉ「９３」に対応するものは、Ｘ３「０ｘ４３Ｃ９Ｅ３１４００００」、Ｙ３「０ｘ３７１Ｆ６ＢＡ６ＦＢ６Ａ」、Ｕ３「０ｘ４Ｅ４９４１９ＤＦＡＢＦ」、Ｖ３「０ｘ０３２８８１１４６Ｃ１２」となる。
【００３２】
初期点テーブル１１２は、点生成部１２０ａ〜１２０ｃにそれぞれ入力する複数の初期点を記憶するテーブルである。各初期点は、それぞれ異なる値とする。
【００３３】
実験環境定義ファイル１１３は、点の写像を行う場合に利用するパラメータ等を記憶するファイルである。図３は、実験環境定義ファイルのデータ構造の一例を示す図である。図３に示すように、この実験環境定義ファイル１１３は、素体標数、楕円曲線、楕円曲線の定数ａ、ｂ、位数、期待値Ｎ、出現頻度θ、調整用パラメータγを含む。また、実験環境定義ファイル１１３は、αのＸ座標、αのＹ座標、βのＸ座標、βのＹ座標を含む。
【００３４】
解析結果データ１１４は、制御部１４０が実行した秘密鍵の解析結果の情報である。
【００３５】
点生成部１２０ａ〜１２０ｃは、式（１）に基づいて写像を繰り返し実行し、写像によって生成した点を特徴点判定部１４２に出力する処理部である。点生成部１２０ａ〜１２０ｃは、写像を行う場合に利用する各種のパラメータを、パラメータ通知部１４１から取得する。また、点生成部１２０ａは、それぞれ異なる初期点が設定され、この初期点から順に写像を繰り返し実行する。
【００３６】
衝突検出部１３０ａ〜１３０ｃは、衝突検知依頼部１４４から特徴点の一部のデータとなる検査データを２つ取得し、各検査データを比較して、各検査データが一致するか否かを判定する処理部である。衝突検出部１３０ａは、判定結果を衝突検知依頼部１４４に通知する。例えば、衝突検出部１３０ａ〜１３０ｃは、各検査データが一致すると判定した場合には、一致した各検査データに付与されるインデックスｉを、衝突検知依頼部１４４に通知する。
【００３７】
制御部１４０は、パラメータ通知部１４１、特徴点判定部１４２、データビット長算出部１４３、衝突検知依頼部１４４、解算出部１４５を有する。
【００３８】
パラメータ通知部１４１は、写像を行う場合に利用される各種のパラメータを点生成部１２０ａ〜１２０ｃに出力する処理部である。具体的に、パラメータ通知部１４１は、実験環境定義ファイル１１３に含まれる素体標数、楕円曲線、楕円曲線の定数ａ，ｂ、位数の情報を、点生成部１２０ａ〜１２０ｃに出力する処理部である。また、パラメータ通知部１４１は、初期点テーブル１１２に含まれる各初期点を点生成部１２０ａ〜１２０ｃに出力する。各点生成部１２０ａ〜１２０ｃに入力される初期点はそれぞれ異なる値とする。
【００３９】
特徴点判定部１４２は、点生成部１２０ａ〜１２０ｃから写像結果となる点を取得し、取得した点のうち、所定の特徴を有する特徴点を特徴点テーブル１１１に登録する処理部である。例えば、特徴点判定部１４２は、点の値の下２桁が「００」となるものを特徴点と判定する。
【００４０】
データビット長算出部１４３は、検査データのビット長を算出し、算出結果を衝突検知依頼部１４４に出力する処理部である。具体的に、データビット長算出部１４３は、ビット長ｌを式（５）によって算出する。
ｌ＝ｌｏｇ２（Ｎ／θ）＋γ・・・（５）
【００４１】
ここで、データビット長算出部１４３は、式（５）に含まれるパラメータＮ、θ、αを実験環境定義ファイル１１３から取得する。例えば、Ｎが「０ｘＢＦ３Ｄ９６」、θが「０ｘ１００００」、γが「１」の場合には、式（５）より、ビット長ｌは「９ｂｉｔ」となる。
【００４２】
衝突検知依頼部１４４は、ビット長ｌに基づいて、複数の特徴点から検査データをそれぞれ抽出し、２つの検査データを一組として、衝突検出部１３０ａ〜１３０ｃに出力することで、各検査データが一致するか否かの判定要求を行う処理部である。衝突検知依頼部１４４は、判定結果を取得し、各検査データが一致する場合には、各検査データの抽出元となる特徴点を解算出部１４５に出力する。
【００４３】
ここでは一例として、衝突検知依頼部１４４が特徴点Ｐｉから検査データを抽出する処理について説明する。まず、衝突検知依頼部１４４は、特徴点Ｐｉに対応するＸｉの値を特徴点テーブル１１１から取得する。例えば、特徴点Ｐ３に対応するＸ３の値は、図２に示すように、「０ｘ３Ｆ６４Ｄ９２４００００」となる。
【００４４】
衝突検知依頼部１４４は、Ｘｉの有効数値からビット長ｌとなる検査データを抽出する。例えば、ビット長ｌを「９ｂｉｔ」とし、Ｘ３「０ｘ３Ｆ６４Ｄ９２４００００」とする場合には、有効数値は「３Ｆ６４Ｄ９２４」となる。有効数値の基準を最下位ビットとすると、検査データは１６進数表記で「０ｘ１２４」となる。なお、「０ｘ１２４」を２進数で表すと「１００１００１００」となり、ビット長ｌは９ｂｉｔとなる。
【００４５】
衝突検知依頼部１４４は、各特徴点から検査データを抽出し、二つの検査データを組にして、衝突検出部１３０ａ〜１３０ｃに出力する。衝突検知依頼部１４４は、各検査データに、該当するインデックスをそれぞれ付与する。例えば、衝突検知依頼部１４４は、図２のｉ「３」に対応する特徴点のＸ３から検査データを取得した場合には、この検査データにインデックス「３」を付与する。
【００４６】
衝突検知依頼部１４４は、衝突検出部１３０ａ〜１３０ｃから判定結果を取得し、各検査データが一致する場合には、一致する検査データのインデックスの組を取得する。衝突検知依頼部１４４は、インデックスをキーにして、該当する特徴点の情報を解算出部１４５に出力する。衝突検知依頼部１４４は、特徴点の情報として、Ｐｉ＝（Ｘｉ、Ｙｉ）、Ｕｉ、Ｖｉ、Ｐｊ＝（Ｘｊ、Ｙｊ）、Ｕｊ、Ｖｊの情報を解算出部１４５に出力する。
【００４７】
例えば、衝突検知依頼部１４４は、一致する各検査データのインデックスが１７、５３の場合には、特徴点テーブル１１１に記憶されたＰ１７、Ｕ１７、Ｖ１７，Ｐ５３、Ｕ５３、Ｖ５３を解算出部１４５に出力する。
【００４８】
解算出部１４５は、特徴点Ｐｉ、Ｐｊの情報を取得した場合に、各特徴点Ｐの値が等しいか否かを改めて判定し、各特徴点Ｐの値が等しい場合には、特徴点の情報に基づいて解を算出する処理部である。解算出部１４５は、算出結果を解析結果データ１１４に登録する。具体的には、解算出部１４５は、上記式（４）に基づいて解を算出する。
【００４９】
ここで、解算出部１４５が改めて各Ｐの値が等しいか否かを判定する意義について説明する。上記の衝突検出部１３０ａ〜１３０ｃは、特徴点の情報を全て比較しているわけではないので、各検査データが一致しているからといって、特徴点が衝突しているとはいえない。したがって、解算出部１４５は、検査データの抽出元となった特徴点を比較することで、各特徴点が衝突しているか否かを判定する。
【００５０】
解算出部１４５が、はじめから何の手がかりもなく、特徴点の情報を全て比較しようとすると、比較対象となる情報が多いため、計算量が膨大なものになってしまう。このため、特徴点が衝突する可能性のある点を衝突検出部１３０ａ〜１３０ｃに検出させ、衝突する特徴点同士のめぼしをつけた後に、特徴点の衝突を判定することで、計算量を削減することができる。
【００５１】
次に、本実施例にかかる暗号鍵解析装置１００の処理手順について説明する。図４は、本実施例にかかる暗号鍵解析装置の処理手順を示すフローチャートである。例えば、図４に示す処理は、点生成部１２０ａ〜１２０ｃに初期点が入力されたことを契機として実行される。暗号鍵解析装置１００は、初期点を点生成部１２０ａ〜１２０ｃに入力し（ステップＳ１００）、点生成部１２０ａ〜１２０ｃは、写像を繰り返し実行することで順次点を生成する（ステップＳ１０１）。
【００５２】
暗号鍵解析装置１００は、特徴点から検査データを抽出し（ステップＳ１０２）、検査データを比較する（ステップＳ１０３）。暗号鍵解析装置１００は、検査データが一致しない場合には（ステップＳ１０４，Ｎｏ）、ステップＳ１０１に移行する。
【００５３】
一方、暗号鍵解析装置１００は、検査データが一致する場合には（ステップＳ１０４，Ｙｅｓ）、一致した検査データに対応する特徴点を比較する（ステップＳ１０５）。暗号鍵解析装置１００は、特徴点が衝突しない場合には（ステップＳ１０６，Ｎｏ）、ステップＳ１０１に移行する。
【００５４】
一方、暗号鍵解析装置１００は、特徴点が衝突した場合には（ステップＳ１０６，Ｙｅｓ）、解を算出する（ステップＳ１０７）。暗号鍵解析装置１００は、解読に失敗した場合には（ステップＳ１０８，Ｎｏ）、ステップＳ１０１に移行する。一方、暗号鍵解析装置１００は、解読に成功した場合には（ステップＳ１０８，Ｙｅｓ）、処理を終了する。
【００５５】
次に、点生成部１２０ａが写像を実行して点を生成する処理手順について説明する。点生成部１２０ｂ，１２０ｃの処理手順は、点生成部１２０ａの処理手順と同じである。図５は、点生成部の処理手順を示すフローチャートである。図５に示す処理は、例えば、初期点Ｐ０が入力されたことを契機として実行される。
【００５６】
図５に示すように、点生成部１２０ａは、初期値Ｐ０を設定し（ステップＳ２００）、ｉを初期値に設定する（ステップＳ２０１）。点生成部１２０ａは、写像Ｆを用いてＰｉを算出し（ステップＳ２０２）、Ｐｉを特徴点判定部１４２に出力する（ステップＳ２０３）。
【００５７】
点生成部１２０ａは、ｉに１を加算し（ステップＳ２０４）、ｉが閾値未満の場合には（ステップＳ２０５，Ｎｏ）、ステップＳ２０２に移行する。一方、ｉが閾値以上の場合には（ステップＳ２０５，Ｙｅｓ）、処理を終了する。
【００５８】
次に、本実施例にかかる暗号鍵解析装置１００の効果について説明する。従来技術では、特徴点の衝突を検出する場合には、特徴点に含まれる情報を全て衝突検出部１３０ａ〜１３０ｃに出力していたため、同一の特徴点の情報が暗号鍵解析装置１００内で重複してしまい、メモリ使用量が多くなっていた。これに対して、暗号鍵解析装置１００は、特徴点の一部を検査データとして抽出し、抽出した検査データを衝突検出部１３０ａ〜１３０ｃに出力することで、特徴点に衝突が発生している可能性があるか否かの判定要求を行う。このため、暗号鍵解析装置１００内で重複するデータ量を削減することができ、メモリ使用量を削減することができる。
【００５９】
また、暗号鍵解析装置１００は、特徴点に衝突が発生している可能性がある場合には、改めて衝突の可能性がある特徴点同士を比較し、特徴点同士の衝突を検出するので、メモリ使用量を削減した場合であっても、正確に秘密鍵を算出することができる。
【００６０】
また、暗号鍵解析装置１００は、従来技術と比較して、特徴点テーブル１１１に記憶する特徴点の数を減らすことなく、メモリ使用量を削減している。このため、暗号鍵解析装置１００では、従来技術と比較して、特徴点衝突を発見するまでの時間が遅延することがないので、計算量を増加させることなく、メモリ使用量を削減することができる。
【００６１】
また、暗号鍵解析装置１００は、検査データのビット長ｌを、衝突検知までに必要なデータ量の期待値と、特徴点の出現頻度とを基にして算出する。このため、最適なビット長によって、衝突検出部１３０ａ〜１３０ｃは、特徴点の衝突の可能性を検出することができる。
【００６２】
また、暗号鍵解析装置１００は、点生成部１２０ａ〜１２０ｃが生成する点のうち、特徴点のみを特徴点テーブル１１１に登録する。このため、メモリ使用量を削減することができる。
【００６３】
なお、図１に示した暗号鍵解析装置１００の構成は一例であり、暗号鍵解析装置１００は、必ずしも図１に示した各処理部を全て有していなくてもよい。例えば、暗号鍵解析装置１００は、記憶部と、抽出部と、判定要求部とを有していればよい。この場合、暗号鍵解析装置１００は、点を生成する複数の点生成装置と、衝突を検出する複数の検出装置に接続されているものとする。
【００６４】
記憶部は、点生成部が生成した点をそれぞれ取得し、取得した点を記憶する記憶部である。この記憶部は、図１の記憶部１１０に対応する。検出部は、記憶部に記憶された複数の点から２つの点を選択し、選択した点の値の一部を検査データとしてそれぞれ抽出する処理部である。判定要求部は、各検査データを複数の検出装置に通知することで、検査データが一致するか否かの判定要求を行い、各検出装置から判定結果を取得する処理部である。抽出部および判定要求部は、図１の衝突検知依頼部１４４に対応する。
【００６５】
ところで、上記の各実施例で説明した暗号鍵解析装置１００の各種の処理は、あらかじめ用意されたプログラムをパーソナルコンピュータやワークステーションなどのコンピュータシステムで実行することによって実現することもできる。そこで、以下では、図６を用いて、上記の実施例で説明した暗号鍵解析装置１００と同様の機能を有する暗号鍵解析プログラムを実行するコンピュータの一例を説明する。図６は、暗号鍵解析プログラムを実行するコンピュータを示す図である。
【００６６】
同図に示すように、暗号鍵解析装置１００としてコンピュータ２００は、入出力制御部２１０、ＨＤＤ（Hard Disk Drive）２２０、ＲＡＭ（Random Access Memory）２３０およびＣＰＵ（Central Processing Unit）２４０を有する。各装置２１０〜２４０は、バス２５０で接続して構成される。
【００６７】
ここで、入出力制御部２１０は、各種情報の入出力を制御する。ＨＤＤ２２０は、ＣＰＵ２４０による各種処理の実行に必要な情報を記憶する。ＲＡＭ２３０は、各種情報を一時的に記憶する。ＣＰＵ２４０は、各種演算処理を実行する。
【００６８】
そして、ＨＤＤ２２０には、暗号鍵解析システムデータがあらかじめ記憶されている。この暗号鍵解析システムデータは、図１に示した暗号鍵解析装置１００の各処理部と同様の機能を発揮する暗号鍵解析プログラムを含む。また、暗号鍵解析システムデータは、処理に必要な各種パラメータを含む暗号鍵解析用データを含む。なお、この暗号鍵解析システムデータを適宜分散させて、ネットワークを介して通信可能に接続された他のコンピュータの記憶部に記憶させておくこともできる。
【００６９】
そして、ＣＰＵ２４０が、この暗号鍵解析システムデータをＨＤＤ２２０から読み出してＲＡＭ２３０に展開することにより、暗号鍵解析システムデータは暗号鍵解析システムとして機能するようになる。この暗号鍵解析システムには暗号鍵解析プロセスが含まれる。
【００７０】
すなわち、暗号鍵解析システムやそれに搭載された暗号鍵解析プロセスは、暗号鍵解析用データをＨＤＤ２２０から読み出して、ＲＡＭ２３０において自身に割り当てられた領域に展開し、この展開したデータ等に基づいて各種処理を実行する。
【００７１】
なお、暗号鍵解読システム及び暗号鍵解析プロセスは、図１に示した制御部１４０において実行される処理に対応する。なお、上記した暗号鍵解析プログラムについては、必ずしも最初からＨＤＤ２２０に記憶させておく必要はない。
【００７２】
例えば、コンピュータ２００に挿入されるフレキシブルディスク（ＦＤ）、ＣＤ−ＲＯＭ、ＤＶＤディスク、光磁気ディスク、ＩＣカードなどの「可搬用の物理媒体」に各プログラムを記憶させておく。そして、コンピュータ２００がこれらから各プログラムを読み出して実行するようにしてもよい。
【００７３】
さらには、公衆回線、インターネット、ＬＡＮ、ＷＡＮなどを介してコンピュータ２００に接続される「他のコンピュータ（またはサーバ）」などに各プログラムを記憶させておく。そして、コンピュータ２００がこれらから各プログラムを読み出して実行するようにしてもよい。
【００７４】
また、図示した各装置の各構成要素は機能概念的なものであり、必ずしも物理的に図示の如く構成されていることを要しない。すなわち、各装置の分散・統合の具体的状態は図示のものに限られず、その全部または一部を、各種の負荷や使用状況などに応じて、任意の単位で機能的または物理的に分散・統合して構成することができる。例えば、図１に示した点生成部１２０ａ〜１２０ｃ、衝突検出部１３０ａ〜１３０ｃを、それぞれ異なるコンピュータに実装させ、各コンピュータに点の生成、衝突検出を実行させることができる。
【００７５】
また、衝突検知依頼部１４４は、検査データをＸｉから抽出していたがこれに限定されるものではない。例えば、衝突検知依頼部１４４は、Ｙｉから検査データを抽出してもよい。
【００７６】
なお、図１に示した制御部１４０は、例えば、ＡＳＩＣ（Application Specific Integrated Circuit）や、ＦＰＧＡ（Field Programmable Gate Array）などの集積装置に対応する。または、制御部１４０は、ＣＰＵやＭＰＵ（Micro Processing Unit）等の電子回路に対応する。また、図１に示した記憶部１１０は、例えば、ＲＡＭ、ＲＯＭ（Read Only Memory）、フラッシュメモリ（Flash Memory）などの半導体メモリ素子、またはハードディスク、光ディスクなどの記憶装置に対応する。
【００７７】
以上の各実施例を含む実施形態に関し、さらに以下の付記を開示する。
【００７８】
（付記１）コンピュータが、
点に対して写像を実行し、該写像の実行結果となる点に対して再度前記写像を実行する処理を繰り返し行う複数の点生成装置から点をそれぞれ取得し、取得した各点を記憶装置に記憶する記憶ステップと、
前記記憶装置に記憶された複数の点から２つの点を選択し、選択した点の値の一部を検査データとしてそれぞれ抽出する抽出ステップと、
前記抽出ステップが抽出した各検査データを複数の検出装置に通知することで、前記検査データが一致するか否かの判定要求を行い、各検出装置から判定結果を取得する判定要求ステップと
を実行することを特徴とする暗号鍵解析方法。
【００７９】
（付記２）前記検出装置によって各検査データが一致すると判定された場合に、一致すると判定された各検査データの抽出元となる点の値をそれぞれ比較し、各点の値が一致するか否かを判定する判定ステップを更に含んだことを特徴とする付記１に記載の暗号鍵解析方法。
【００８０】
（付記３）前記点生成装置によって生成される点が所定の特徴を有する点となる頻度と、前記判定ステップによって各点の値が一致すると判定されるまでに必要となるデータ量の期待値とを基にして、前記検査データのビット長を判定するビット長判定ステップを更に含み、前記抽出ステップは、前記ビット長に基づいて点の値から前記検査データを抽出することを特徴とする付記２に記載の暗号鍵解析方法。
【００８１】
（付記４）前記記憶ステップは、前記点生成装置が生成した複数の点のうち、所定の特徴を有する点を前記記憶装置に記憶することを特徴とする付記１〜３のいずれか一つに記載の暗号鍵解析方法。
【００８２】
（付記５）点に対して写像を実行し、該写像の実行結果となる点に対して再度前記写像を実行する処理を繰り返し行う複数の点生成部から点をそれぞれ取得し、取得した各点を記憶する記憶部と、
前記記憶部に記憶された複数の点から２つの点を選択し、選択した点の値の一部を検査データとしてそれぞれ抽出する抽出部と、
前記抽出部が抽出した各検査データを複数の検出部に通知することで、前記検査データが一致するか否かの判定要求を行い、各検出部から判定結果を取得する判定要求部と
備えたことを特徴とする暗号鍵解析装置。
【００８３】
（付記６）前記検出部によって各検査データが一致すると判定された場合に、一致すると判定された各検査データの抽出元となる点の値をそれぞれ比較し、各点の値が一致するか否かを判定する判定部を更に備えたことを特徴とする付記５に記載の暗号鍵解析装置。
【００８４】
（付記７）前記点生成部によって生成される点が所定の特徴を有する点となる頻度と、前記点判定部によって各点の値が一致すると判定されるまでに必要となるデータ量の期待値とを基にして、前記検査データのビット長を判定するビット長判定部を更に備え、前記抽出部は、前記ビット長に基づいて点の値から前記検査データを抽出することを特徴とする付記６に記載の暗号鍵解析装置。
【００８５】
（付記８）前記記憶部は、前記点生成部が生成した複数の点のうち、所定の特徴を有する点を記憶することを特徴とする付記５〜７のいずれか一つに記載の暗号鍵解析装置。
【００８６】
（付記９）コンピュータに、
点に対して写像を実行し、該写像の実行結果となる点に対して再度前記写像を実行する処理を繰り返し行う複数の点生成装置から点をそれぞれ取得し、取得した各点を記憶装置に記憶する記憶手順と、
前記記憶装置に記憶された複数の点から２つの点を選択し、選択した点の値の一部を検査データとしてそれぞれ抽出する抽出手順と、
前記抽出手順が抽出した各検査データを複数の検出装置に通知することで、前記検査データが一致するか否かの判定要求を行い、各検出装置から判定結果を取得する判定要求手順と、
を実行させることを特徴とする暗号鍵解析プログラム。
【００８７】
（付記１０）前記検出装置によって各検査データが一致すると判定された場合に、一致すると判定された各検査データの抽出元となる点の値をそれぞれ比較し、各点の値が一致するか否かを判定する判定手順を更に実行させることを特徴とする付記９に記載の暗号鍵解析プログラム。
【００８８】
（付記１１）前記点生成装置によって生成される点が所定の特徴を有する点となる頻度と、前記判定手順によって各点の値が一致すると判定されるまでに必要となるデータ量の期待値とを基にして、前記検査データのビット長を判定するビット長判定手順を更に実行させ、前記抽出手順は、前記ビット長に基づいて点の値から前記検査データを抽出することを特徴とする付記１０に記載の暗号鍵解析プログラム。
【００８９】
（付記１２）前記記憶手順は、前記点生成装置が生成した複数の点のうち、所定の特徴を有する点を前記記憶装置に記憶することを特徴とする付記９〜１１のいずれか一つに記載の暗号鍵解析プログラム。
【符号の説明】
【００９０】
１００ 暗号鍵解析装置
１１０ 記憶部
１２０ａ，１２０ｂ，１２０ｃ 点生成部
１３０ａ，１３０ｂ，１３０ｃ 衝突検出部
１４０ 制御部
【技術分野】
【０００１】
本発明は、暗号鍵解析方法、暗号鍵解析装置および暗号鍵解析プログラムに関する。
【背景技術】
【０００２】
近年、情報漏洩を防止する暗号技術の一つとして、公開鍵暗号が知られている。この公開鍵暗号は、受信者が公開する公開鍵によって送信者が暗号化を行い、受信者は未公開の秘密鍵によって復号を行うものである。
【０００３】
現在標準の公開鍵暗号は、公開鍵に基づいて秘密鍵を解読するための計算量が膨大であることを安全性の根拠としている。その一方で解読技術や実装技術は日に日に改良が加えられ、また計算能力も日々増加している。そのため、今後も安全な暗号を利用し続けるためには、現状および今後の計算能力の見積もりを行い、容易に解読できないような計算量となるように、鍵ビット長などの暗号パラメータを適切に設計する必要がある。そのためには、解読実験をおこなって、暗号の安全性、強度を評価することが重要である。
【０００４】
公開鍵暗号には、離散対数問題に基づいて設計された楕円曲線暗号等がある。離散対数問題とは、「素数ｐに対して、有限体ＧＦ（ｐ）の生成元αを固定した場合に、有限体ＧＦ（ｐ）の元βに対して、β＝αｘを満たす整数ｘを求めよ」というものである。
【０００５】
この離散対数問題を解読する方法の一つにPollardのρ法がある。このρ法は、写像ＦによってＰｉ−１から次のＰｉを順次算出し、異なるｉ、ｊに対してＰｉ＝Ｐｊとなるものを見つけることで、公開鍵暗号の秘密鍵を解くというものである。
【０００６】
ここで、写像Ｆは、下記の式（１）によって示される。この写像により、下記の式（２）が成り立つｕｉおよびｖｉを一意に算出することができる。また、Ｐｉ＝Ｐｊとなることを衝突と呼ぶ。例えば、Ｐｉ＝Ｐｊで衝突がおこると、式（３）の関係が成り立ち、解を求めることができる。具体的には、式（４）によって解を求めることができる。ただし、ｖｊ≠ｖｉとする。
【０００７】
Ｐｉ＝Ｆ（Ｐｉ−１）・・・（１）
Ｐｉ＝α＾｛ｕｉ｝＊β＾｛ｖｉ｝・・・（２）
α＾｛ｕｉ｝＊β＾｛ｖｉ｝＝α＾｛ｕｊ｝＊β＾｛ｖｊ｝・・・（３）
ｘ＝（ｕｉ−ｕｊ）／（ｖｊ−ｖｉ）・・・（４）
【０００８】
図７は、ρ法の原理を説明するための図である。図７に示す例では、初期点Ｐ０として、写像Ｆを繰り返し実行することで、Ｐ１、Ｐ２、・・・Ｐｉ＋５、・・・、Ｐｊが順次求められている。図７に示すように写像Ｆを繰り返し実行していくと、Ｐｉ＝Ｐｊにおいて衝突が発生する。このため、式（４）に基づいて解が求まる。
【０００９】
なお、上記のρ法では、写像Ｆによって算出した多数の点Ｐｉを全て記憶するため、メモリ使用量が膨大になってしまうという問題があった。このメモリ使用量を削減する技術として、特徴点（distinguished point）を導入したρ法が存在する。この特徴点を導入したρ法は、写像Ｆによって算出した点Ｐｉのうち、所定の特徴を有する特徴点のみを記憶し、衝突を検出するものである。
【００１０】
図８は、特徴点を導入したρ法を説明するための図である。なお実際の楕円曲線上の点Ｐｉは、２変数（Ｘｉ、Ｙｉ）のベクトル値として表されるが、ここではρ法の簡易な説明のためスカラー値を用いる。図８に示す例では、Ｐｉの下２桁が００となる点を特徴点とする。特徴点を白丸で示し、それ以外の点を黒丸で示す。例えば、Ｐ３、Ｐ１７、Ｐ２９、Ｐ３５は、下２桁が００となるため、Ｐ３、Ｐ１７、Ｐ２９、Ｐ３５は特徴点となる。したがって、Ｐ３、Ｐ１７、Ｐ２９、Ｐ３５が保存され、特徴点以外の点は保存されない。このように、特徴点のみを保存する場合でも特徴点同士が一致すれば、衝突を検出でき、解を求めることができる。図８に示す例では、Ｐ１７＝Ｐ３５となるため、解を求めることができる。
【００１１】
図８において、全ての点を保存していれば、Ｐ１０で初めて衝突を検出可能であるが、Ｐ１０は特徴点では無い。このため、特徴点を導入したρ法では、Ｐ１０が保存されておらず、Ｐ１０で衝突を検出することができない。しかし、写像Ｆは、一意の写像であるため、特徴点がループ上に存在していれば、いずれは、Ｐｉ＝Ｐｊとなる特徴点を検出することができる。
【００１２】
ところで、従来技術では、ρ法による離散対数問題の解析を並列的に処理することで、点の生成や衝突を検出する処理を効率化させている。ここで、従来の暗号鍵解析装置の一例について説明する。図９は、従来の暗号鍵解析装置の構成を示す図である。図９に示すように、暗号鍵解析装置１０は、点生成部１ａ〜１ｃ、特徴点判定部２、特徴点記憶部３、衝突検出部４ａ〜４ｃ、解算出部５を有する。
【００１３】
点生成部１ａ〜１ｃは、式（１）に基づいて写像を繰り返し実行し、写像によって生成した点を特徴点判定部２に出力する。各点生成部１ａ〜１ｃは、それぞれ異なる初期点が入力され、この初期点から順に写像を繰り返し実行する。
【００１４】
特徴点判定部２は、点生成部１ａ〜１ｃから点を取得し、各点のうち、特徴点となる点を判定する処理部である。特徴点判定部２は、特徴点を特徴点記憶部３に登録する。特徴点記憶部３は、特徴点を記憶する記憶部である。
【００１５】
衝突検出部４ａ〜４ｃは、特徴点記憶部３から２つの特徴点を取得し、各特徴点を比較して、衝突が起こったか否かを判定する処理部である。なお、特徴点は特徴点記憶部３によって一元管理されるため、衝突検出部４ａ〜４ｃは、特徴点記憶部３に記憶された特徴点を複製して、自身のメモリに記憶し、衝突を検出する。衝突検出部４ａ〜４ｃは、衝突を検出した場合に、衝突した特徴点の識別情報を解算出部５に通知する。
【００１６】
解算出部５は、衝突した特徴点の識別情報を取得した場合に、該当する特徴点の情報を特徴点記憶部３から取り出し、各特徴点を比較することによって、秘密鍵を算出する処理部である。具体的に、解算出部５は、式（４）に基づいて、秘密鍵を算出する。
【００１７】
図９に示したように、暗号鍵解析装置１０は、複数の点生成部１ａ〜１ｃが並列的に点を生成し、複数の衝突検出部４ａ〜４ｃが並列的に各特徴点の衝突検出を実行する。このため、点の生成や衝突を効率的に実行することができる。
【先行技術文献】
【特許文献】
【００１８】
【特許文献１】特開２００４−２２９１６３号公報
【特許文献２】特開２００５−１３４４５４号公報
【特許文献３】特開２００６−４８１９２号公報
【発明の概要】
【発明が解決しようとする課題】
【００１９】
しかしながら、上述した従来技術では、点を生成する処理と各点の衝突を検出する処理との並列化を効率的に行うことができないという問題があった。
【００２０】
例えば、図９に示した従来の暗号鍵解析装置１０では、各衝突検出部４ａ〜４ｃは、特徴点記憶部３に記憶された特徴点を読み出して、特徴点の衝突を検出する。この場合、一時的に、同一の特徴点の情報が、衝突検出部４ａ〜４ｃおよび特徴点記憶部３に重複して存在することになるため、メモリ使用量が増加してしまう。
【００２１】
これに対して、特徴点記憶部３に記憶される特徴点の数を少なくすることで、メモリ使用量を削減することが考えられる。しかし、特徴点の数を少なくすると、各特徴点が衝突するまでに時間がかかってしまうため、メモリ使用量が削減されるかわりに、計算時間が増加してしまう。
【００２２】
開示の技術は、上記に鑑みてなされたものであって、点を生成する処理と各点の衝突を検出する処理との並列化を効率的に行うことができる暗号鍵解析方法、暗号鍵解析装置および暗号鍵解析プログラムを提供することを目的とする。
【課題を解決するための手段】
【００２３】
本願の開示する暗号鍵解析方法は、コンピュータが、点に対して写像を実行し、該写像の実行結果となる点に対して再度前記写像を実行する処理を繰り返し行う複数の点生成装置から点をそれぞれ取得し、取得した各点を記憶装置に記憶する記憶ステップと、前記記憶装置に記憶された複数の点から２つの点を選択し、選択した点の値の一部を検査データとしてそれぞれ抽出する抽出ステップと、前記抽出ステップが抽出した各検査データを複数の検出装置に通知することで、前記検査データが一致するか否かの判定要求を行い、各検出装置から判定結果を取得する判定要求ステップとを実行することを要件とする。
【発明の効果】
【００２４】
本願の開示する暗号鍵解析方法の一つの態様によれば、点を生成する処理と各点の衝突を検出する処理との並列化を効率的に行うことができるという効果を奏する。
【図面の簡単な説明】
【００２５】
【図１】図１は、本実施例にかかる暗号鍵解析装置の構成を示す図である。
【図２】図２は、特徴点テーブルのデータ構造の一例を示す図である。
【図３】図３は、実験環境定義ファイルのデータ構造の一例を示す図である。
【図４】図４は、本実施例にかかる暗号鍵解析装置の処理手順を示すフローチャートである。
【図５】図５は、点生成部の処理手順を示すフローチャートである。
【図６】図６は、暗号鍵解析プログラムを実行するコンピュータを示す図である。
【図７】図７は、ρ法の原理を説明するための図である。
【図８】図８は、特徴点を導入したρ法を説明するための図である。
【図９】図９は、従来の暗号鍵解析装置の構成を示す図である。
【発明を実施するための形態】
【００２６】
以下に、本願の開示する暗号鍵解析方法、暗号鍵解析装置および暗号鍵解析プログラムの実施例を図面に基づいて詳細に説明する。なお、この実施例によりこの発明が限定されるものではない。
【実施例】
【００２７】
本実施例にかかる暗号鍵解析装置の構成について説明する。図１は、本実施例にかかる暗号鍵解析装置の構成を示す図である。図１に示すように、この暗号鍵解析装置１００は、記憶部１１０と、点生成部１２０ａ〜１２０ｃと、衝突検出部１３０ａ〜１３０ｃと、制御部１４０を有する。ここでは説明の便宜上、点生成部１２０ａ〜１２０ｃ、衝突検出部１３０ａ〜１３０ｃを示す。しかし、暗号鍵解析装置１００は、その他にも、点生成部１２０、衝突検出部１３０を有しても良い。
【００２８】
記憶部１１０は、秘密鍵を解析するために必要となる各種のデータや解析結果を記憶する記憶部である。図１に示すように、記憶部１１０は、特徴点テーブル１１１と、初期点テーブル１１２と、実験環境定義ファイル１１３と、解析結果データ１１４を記憶する。
【００２９】
特徴点テーブル１１１は、点生成部１２０ａ〜１２０ｃが生成する点のうち、所定の特徴を有する特徴点の情報を記憶するテーブルである。図２は、特徴点テーブルのデータ構造の一例を示す図である。図２に示すように、特徴点テーブル１１１は、ｉ、Ｘｉ、Ｙｉ、Ｕｉ、Ｖｉを対応付けて記憶する。
【００３０】
このうち、ｉは、写像を行った回数である。Ｐｉは点の値である。Ｕｉ、Ｖｉはそれぞれ、Ｐｉを求める際に利用したαの巾指数ならびにβの巾指数であり、ＰｉとＵｉ、Ｖｉとの関係は、上記式（２）となる。Ｘｉは、ＰｉのＸ座標である。Ｙｉは、ＰｉのＹ座標である。なお、ｉの値は１０進数で表しており、Ｘｉ、Ｙｉ、Ｕｉ、Ｖｉの各値は１６進数で表している。
【００３１】
例えば、ｉ「９３」に対応するものは、Ｘ３「０ｘ４３Ｃ９Ｅ３１４００００」、Ｙ３「０ｘ３７１Ｆ６ＢＡ６ＦＢ６Ａ」、Ｕ３「０ｘ４Ｅ４９４１９ＤＦＡＢＦ」、Ｖ３「０ｘ０３２８８１１４６Ｃ１２」となる。
【００３２】
初期点テーブル１１２は、点生成部１２０ａ〜１２０ｃにそれぞれ入力する複数の初期点を記憶するテーブルである。各初期点は、それぞれ異なる値とする。
【００３３】
実験環境定義ファイル１１３は、点の写像を行う場合に利用するパラメータ等を記憶するファイルである。図３は、実験環境定義ファイルのデータ構造の一例を示す図である。図３に示すように、この実験環境定義ファイル１１３は、素体標数、楕円曲線、楕円曲線の定数ａ、ｂ、位数、期待値Ｎ、出現頻度θ、調整用パラメータγを含む。また、実験環境定義ファイル１１３は、αのＸ座標、αのＹ座標、βのＸ座標、βのＹ座標を含む。
【００３４】
解析結果データ１１４は、制御部１４０が実行した秘密鍵の解析結果の情報である。
【００３５】
点生成部１２０ａ〜１２０ｃは、式（１）に基づいて写像を繰り返し実行し、写像によって生成した点を特徴点判定部１４２に出力する処理部である。点生成部１２０ａ〜１２０ｃは、写像を行う場合に利用する各種のパラメータを、パラメータ通知部１４１から取得する。また、点生成部１２０ａは、それぞれ異なる初期点が設定され、この初期点から順に写像を繰り返し実行する。
【００３６】
衝突検出部１３０ａ〜１３０ｃは、衝突検知依頼部１４４から特徴点の一部のデータとなる検査データを２つ取得し、各検査データを比較して、各検査データが一致するか否かを判定する処理部である。衝突検出部１３０ａは、判定結果を衝突検知依頼部１４４に通知する。例えば、衝突検出部１３０ａ〜１３０ｃは、各検査データが一致すると判定した場合には、一致した各検査データに付与されるインデックスｉを、衝突検知依頼部１４４に通知する。
【００３７】
制御部１４０は、パラメータ通知部１４１、特徴点判定部１４２、データビット長算出部１４３、衝突検知依頼部１４４、解算出部１４５を有する。
【００３８】
パラメータ通知部１４１は、写像を行う場合に利用される各種のパラメータを点生成部１２０ａ〜１２０ｃに出力する処理部である。具体的に、パラメータ通知部１４１は、実験環境定義ファイル１１３に含まれる素体標数、楕円曲線、楕円曲線の定数ａ，ｂ、位数の情報を、点生成部１２０ａ〜１２０ｃに出力する処理部である。また、パラメータ通知部１４１は、初期点テーブル１１２に含まれる各初期点を点生成部１２０ａ〜１２０ｃに出力する。各点生成部１２０ａ〜１２０ｃに入力される初期点はそれぞれ異なる値とする。
【００３９】
特徴点判定部１４２は、点生成部１２０ａ〜１２０ｃから写像結果となる点を取得し、取得した点のうち、所定の特徴を有する特徴点を特徴点テーブル１１１に登録する処理部である。例えば、特徴点判定部１４２は、点の値の下２桁が「００」となるものを特徴点と判定する。
【００４０】
データビット長算出部１４３は、検査データのビット長を算出し、算出結果を衝突検知依頼部１４４に出力する処理部である。具体的に、データビット長算出部１４３は、ビット長ｌを式（５）によって算出する。
ｌ＝ｌｏｇ２（Ｎ／θ）＋γ・・・（５）
【００４１】
ここで、データビット長算出部１４３は、式（５）に含まれるパラメータＮ、θ、αを実験環境定義ファイル１１３から取得する。例えば、Ｎが「０ｘＢＦ３Ｄ９６」、θが「０ｘ１００００」、γが「１」の場合には、式（５）より、ビット長ｌは「９ｂｉｔ」となる。
【００４２】
衝突検知依頼部１４４は、ビット長ｌに基づいて、複数の特徴点から検査データをそれぞれ抽出し、２つの検査データを一組として、衝突検出部１３０ａ〜１３０ｃに出力することで、各検査データが一致するか否かの判定要求を行う処理部である。衝突検知依頼部１４４は、判定結果を取得し、各検査データが一致する場合には、各検査データの抽出元となる特徴点を解算出部１４５に出力する。
【００４３】
ここでは一例として、衝突検知依頼部１４４が特徴点Ｐｉから検査データを抽出する処理について説明する。まず、衝突検知依頼部１４４は、特徴点Ｐｉに対応するＸｉの値を特徴点テーブル１１１から取得する。例えば、特徴点Ｐ３に対応するＸ３の値は、図２に示すように、「０ｘ３Ｆ６４Ｄ９２４００００」となる。
【００４４】
衝突検知依頼部１４４は、Ｘｉの有効数値からビット長ｌとなる検査データを抽出する。例えば、ビット長ｌを「９ｂｉｔ」とし、Ｘ３「０ｘ３Ｆ６４Ｄ９２４００００」とする場合には、有効数値は「３Ｆ６４Ｄ９２４」となる。有効数値の基準を最下位ビットとすると、検査データは１６進数表記で「０ｘ１２４」となる。なお、「０ｘ１２４」を２進数で表すと「１００１００１００」となり、ビット長ｌは９ｂｉｔとなる。
【００４５】
衝突検知依頼部１４４は、各特徴点から検査データを抽出し、二つの検査データを組にして、衝突検出部１３０ａ〜１３０ｃに出力する。衝突検知依頼部１４４は、各検査データに、該当するインデックスをそれぞれ付与する。例えば、衝突検知依頼部１４４は、図２のｉ「３」に対応する特徴点のＸ３から検査データを取得した場合には、この検査データにインデックス「３」を付与する。
【００４６】
衝突検知依頼部１４４は、衝突検出部１３０ａ〜１３０ｃから判定結果を取得し、各検査データが一致する場合には、一致する検査データのインデックスの組を取得する。衝突検知依頼部１４４は、インデックスをキーにして、該当する特徴点の情報を解算出部１４５に出力する。衝突検知依頼部１４４は、特徴点の情報として、Ｐｉ＝（Ｘｉ、Ｙｉ）、Ｕｉ、Ｖｉ、Ｐｊ＝（Ｘｊ、Ｙｊ）、Ｕｊ、Ｖｊの情報を解算出部１４５に出力する。
【００４７】
例えば、衝突検知依頼部１４４は、一致する各検査データのインデックスが１７、５３の場合には、特徴点テーブル１１１に記憶されたＰ１７、Ｕ１７、Ｖ１７，Ｐ５３、Ｕ５３、Ｖ５３を解算出部１４５に出力する。
【００４８】
解算出部１４５は、特徴点Ｐｉ、Ｐｊの情報を取得した場合に、各特徴点Ｐの値が等しいか否かを改めて判定し、各特徴点Ｐの値が等しい場合には、特徴点の情報に基づいて解を算出する処理部である。解算出部１４５は、算出結果を解析結果データ１１４に登録する。具体的には、解算出部１４５は、上記式（４）に基づいて解を算出する。
【００４９】
ここで、解算出部１４５が改めて各Ｐの値が等しいか否かを判定する意義について説明する。上記の衝突検出部１３０ａ〜１３０ｃは、特徴点の情報を全て比較しているわけではないので、各検査データが一致しているからといって、特徴点が衝突しているとはいえない。したがって、解算出部１４５は、検査データの抽出元となった特徴点を比較することで、各特徴点が衝突しているか否かを判定する。
【００５０】
解算出部１４５が、はじめから何の手がかりもなく、特徴点の情報を全て比較しようとすると、比較対象となる情報が多いため、計算量が膨大なものになってしまう。このため、特徴点が衝突する可能性のある点を衝突検出部１３０ａ〜１３０ｃに検出させ、衝突する特徴点同士のめぼしをつけた後に、特徴点の衝突を判定することで、計算量を削減することができる。
【００５１】
次に、本実施例にかかる暗号鍵解析装置１００の処理手順について説明する。図４は、本実施例にかかる暗号鍵解析装置の処理手順を示すフローチャートである。例えば、図４に示す処理は、点生成部１２０ａ〜１２０ｃに初期点が入力されたことを契機として実行される。暗号鍵解析装置１００は、初期点を点生成部１２０ａ〜１２０ｃに入力し（ステップＳ１００）、点生成部１２０ａ〜１２０ｃは、写像を繰り返し実行することで順次点を生成する（ステップＳ１０１）。
【００５２】
暗号鍵解析装置１００は、特徴点から検査データを抽出し（ステップＳ１０２）、検査データを比較する（ステップＳ１０３）。暗号鍵解析装置１００は、検査データが一致しない場合には（ステップＳ１０４，Ｎｏ）、ステップＳ１０１に移行する。
【００５３】
一方、暗号鍵解析装置１００は、検査データが一致する場合には（ステップＳ１０４，Ｙｅｓ）、一致した検査データに対応する特徴点を比較する（ステップＳ１０５）。暗号鍵解析装置１００は、特徴点が衝突しない場合には（ステップＳ１０６，Ｎｏ）、ステップＳ１０１に移行する。
【００５４】
一方、暗号鍵解析装置１００は、特徴点が衝突した場合には（ステップＳ１０６，Ｙｅｓ）、解を算出する（ステップＳ１０７）。暗号鍵解析装置１００は、解読に失敗した場合には（ステップＳ１０８，Ｎｏ）、ステップＳ１０１に移行する。一方、暗号鍵解析装置１００は、解読に成功した場合には（ステップＳ１０８，Ｙｅｓ）、処理を終了する。
【００５５】
次に、点生成部１２０ａが写像を実行して点を生成する処理手順について説明する。点生成部１２０ｂ，１２０ｃの処理手順は、点生成部１２０ａの処理手順と同じである。図５は、点生成部の処理手順を示すフローチャートである。図５に示す処理は、例えば、初期点Ｐ０が入力されたことを契機として実行される。
【００５６】
図５に示すように、点生成部１２０ａは、初期値Ｐ０を設定し（ステップＳ２００）、ｉを初期値に設定する（ステップＳ２０１）。点生成部１２０ａは、写像Ｆを用いてＰｉを算出し（ステップＳ２０２）、Ｐｉを特徴点判定部１４２に出力する（ステップＳ２０３）。
【００５７】
点生成部１２０ａは、ｉに１を加算し（ステップＳ２０４）、ｉが閾値未満の場合には（ステップＳ２０５，Ｎｏ）、ステップＳ２０２に移行する。一方、ｉが閾値以上の場合には（ステップＳ２０５，Ｙｅｓ）、処理を終了する。
【００５８】
次に、本実施例にかかる暗号鍵解析装置１００の効果について説明する。従来技術では、特徴点の衝突を検出する場合には、特徴点に含まれる情報を全て衝突検出部１３０ａ〜１３０ｃに出力していたため、同一の特徴点の情報が暗号鍵解析装置１００内で重複してしまい、メモリ使用量が多くなっていた。これに対して、暗号鍵解析装置１００は、特徴点の一部を検査データとして抽出し、抽出した検査データを衝突検出部１３０ａ〜１３０ｃに出力することで、特徴点に衝突が発生している可能性があるか否かの判定要求を行う。このため、暗号鍵解析装置１００内で重複するデータ量を削減することができ、メモリ使用量を削減することができる。
【００５９】
また、暗号鍵解析装置１００は、特徴点に衝突が発生している可能性がある場合には、改めて衝突の可能性がある特徴点同士を比較し、特徴点同士の衝突を検出するので、メモリ使用量を削減した場合であっても、正確に秘密鍵を算出することができる。
【００６０】
また、暗号鍵解析装置１００は、従来技術と比較して、特徴点テーブル１１１に記憶する特徴点の数を減らすことなく、メモリ使用量を削減している。このため、暗号鍵解析装置１００では、従来技術と比較して、特徴点衝突を発見するまでの時間が遅延することがないので、計算量を増加させることなく、メモリ使用量を削減することができる。
【００６１】
また、暗号鍵解析装置１００は、検査データのビット長ｌを、衝突検知までに必要なデータ量の期待値と、特徴点の出現頻度とを基にして算出する。このため、最適なビット長によって、衝突検出部１３０ａ〜１３０ｃは、特徴点の衝突の可能性を検出することができる。
【００６２】
また、暗号鍵解析装置１００は、点生成部１２０ａ〜１２０ｃが生成する点のうち、特徴点のみを特徴点テーブル１１１に登録する。このため、メモリ使用量を削減することができる。
【００６３】
なお、図１に示した暗号鍵解析装置１００の構成は一例であり、暗号鍵解析装置１００は、必ずしも図１に示した各処理部を全て有していなくてもよい。例えば、暗号鍵解析装置１００は、記憶部と、抽出部と、判定要求部とを有していればよい。この場合、暗号鍵解析装置１００は、点を生成する複数の点生成装置と、衝突を検出する複数の検出装置に接続されているものとする。
【００６４】
記憶部は、点生成部が生成した点をそれぞれ取得し、取得した点を記憶する記憶部である。この記憶部は、図１の記憶部１１０に対応する。検出部は、記憶部に記憶された複数の点から２つの点を選択し、選択した点の値の一部を検査データとしてそれぞれ抽出する処理部である。判定要求部は、各検査データを複数の検出装置に通知することで、検査データが一致するか否かの判定要求を行い、各検出装置から判定結果を取得する処理部である。抽出部および判定要求部は、図１の衝突検知依頼部１４４に対応する。
【００６５】
ところで、上記の各実施例で説明した暗号鍵解析装置１００の各種の処理は、あらかじめ用意されたプログラムをパーソナルコンピュータやワークステーションなどのコンピュータシステムで実行することによって実現することもできる。そこで、以下では、図６を用いて、上記の実施例で説明した暗号鍵解析装置１００と同様の機能を有する暗号鍵解析プログラムを実行するコンピュータの一例を説明する。図６は、暗号鍵解析プログラムを実行するコンピュータを示す図である。
【００６６】
同図に示すように、暗号鍵解析装置１００としてコンピュータ２００は、入出力制御部２１０、ＨＤＤ（Hard Disk Drive）２２０、ＲＡＭ（Random Access Memory）２３０およびＣＰＵ（Central Processing Unit）２４０を有する。各装置２１０〜２４０は、バス２５０で接続して構成される。
【００６７】
ここで、入出力制御部２１０は、各種情報の入出力を制御する。ＨＤＤ２２０は、ＣＰＵ２４０による各種処理の実行に必要な情報を記憶する。ＲＡＭ２３０は、各種情報を一時的に記憶する。ＣＰＵ２４０は、各種演算処理を実行する。
【００６８】
そして、ＨＤＤ２２０には、暗号鍵解析システムデータがあらかじめ記憶されている。この暗号鍵解析システムデータは、図１に示した暗号鍵解析装置１００の各処理部と同様の機能を発揮する暗号鍵解析プログラムを含む。また、暗号鍵解析システムデータは、処理に必要な各種パラメータを含む暗号鍵解析用データを含む。なお、この暗号鍵解析システムデータを適宜分散させて、ネットワークを介して通信可能に接続された他のコンピュータの記憶部に記憶させておくこともできる。
【００６９】
そして、ＣＰＵ２４０が、この暗号鍵解析システムデータをＨＤＤ２２０から読み出してＲＡＭ２３０に展開することにより、暗号鍵解析システムデータは暗号鍵解析システムとして機能するようになる。この暗号鍵解析システムには暗号鍵解析プロセスが含まれる。
【００７０】
すなわち、暗号鍵解析システムやそれに搭載された暗号鍵解析プロセスは、暗号鍵解析用データをＨＤＤ２２０から読み出して、ＲＡＭ２３０において自身に割り当てられた領域に展開し、この展開したデータ等に基づいて各種処理を実行する。
【００７１】
なお、暗号鍵解読システム及び暗号鍵解析プロセスは、図１に示した制御部１４０において実行される処理に対応する。なお、上記した暗号鍵解析プログラムについては、必ずしも最初からＨＤＤ２２０に記憶させておく必要はない。
【００７２】
例えば、コンピュータ２００に挿入されるフレキシブルディスク（ＦＤ）、ＣＤ−ＲＯＭ、ＤＶＤディスク、光磁気ディスク、ＩＣカードなどの「可搬用の物理媒体」に各プログラムを記憶させておく。そして、コンピュータ２００がこれらから各プログラムを読み出して実行するようにしてもよい。
【００７３】
さらには、公衆回線、インターネット、ＬＡＮ、ＷＡＮなどを介してコンピュータ２００に接続される「他のコンピュータ（またはサーバ）」などに各プログラムを記憶させておく。そして、コンピュータ２００がこれらから各プログラムを読み出して実行するようにしてもよい。
【００７４】
また、図示した各装置の各構成要素は機能概念的なものであり、必ずしも物理的に図示の如く構成されていることを要しない。すなわち、各装置の分散・統合の具体的状態は図示のものに限られず、その全部または一部を、各種の負荷や使用状況などに応じて、任意の単位で機能的または物理的に分散・統合して構成することができる。例えば、図１に示した点生成部１２０ａ〜１２０ｃ、衝突検出部１３０ａ〜１３０ｃを、それぞれ異なるコンピュータに実装させ、各コンピュータに点の生成、衝突検出を実行させることができる。
【００７５】
また、衝突検知依頼部１４４は、検査データをＸｉから抽出していたがこれに限定されるものではない。例えば、衝突検知依頼部１４４は、Ｙｉから検査データを抽出してもよい。
【００７６】
なお、図１に示した制御部１４０は、例えば、ＡＳＩＣ（Application Specific Integrated Circuit）や、ＦＰＧＡ（Field Programmable Gate Array）などの集積装置に対応する。または、制御部１４０は、ＣＰＵやＭＰＵ（Micro Processing Unit）等の電子回路に対応する。また、図１に示した記憶部１１０は、例えば、ＲＡＭ、ＲＯＭ（Read Only Memory）、フラッシュメモリ（Flash Memory）などの半導体メモリ素子、またはハードディスク、光ディスクなどの記憶装置に対応する。
【００７７】
以上の各実施例を含む実施形態に関し、さらに以下の付記を開示する。
【００７８】
（付記１）コンピュータが、
点に対して写像を実行し、該写像の実行結果となる点に対して再度前記写像を実行する処理を繰り返し行う複数の点生成装置から点をそれぞれ取得し、取得した各点を記憶装置に記憶する記憶ステップと、
前記記憶装置に記憶された複数の点から２つの点を選択し、選択した点の値の一部を検査データとしてそれぞれ抽出する抽出ステップと、
前記抽出ステップが抽出した各検査データを複数の検出装置に通知することで、前記検査データが一致するか否かの判定要求を行い、各検出装置から判定結果を取得する判定要求ステップと
を実行することを特徴とする暗号鍵解析方法。
【００７９】
（付記２）前記検出装置によって各検査データが一致すると判定された場合に、一致すると判定された各検査データの抽出元となる点の値をそれぞれ比較し、各点の値が一致するか否かを判定する判定ステップを更に含んだことを特徴とする付記１に記載の暗号鍵解析方法。
【００８０】
（付記３）前記点生成装置によって生成される点が所定の特徴を有する点となる頻度と、前記判定ステップによって各点の値が一致すると判定されるまでに必要となるデータ量の期待値とを基にして、前記検査データのビット長を判定するビット長判定ステップを更に含み、前記抽出ステップは、前記ビット長に基づいて点の値から前記検査データを抽出することを特徴とする付記２に記載の暗号鍵解析方法。
【００８１】
（付記４）前記記憶ステップは、前記点生成装置が生成した複数の点のうち、所定の特徴を有する点を前記記憶装置に記憶することを特徴とする付記１〜３のいずれか一つに記載の暗号鍵解析方法。
【００８２】
（付記５）点に対して写像を実行し、該写像の実行結果となる点に対して再度前記写像を実行する処理を繰り返し行う複数の点生成部から点をそれぞれ取得し、取得した各点を記憶する記憶部と、
前記記憶部に記憶された複数の点から２つの点を選択し、選択した点の値の一部を検査データとしてそれぞれ抽出する抽出部と、
前記抽出部が抽出した各検査データを複数の検出部に通知することで、前記検査データが一致するか否かの判定要求を行い、各検出部から判定結果を取得する判定要求部と
備えたことを特徴とする暗号鍵解析装置。
【００８３】
（付記６）前記検出部によって各検査データが一致すると判定された場合に、一致すると判定された各検査データの抽出元となる点の値をそれぞれ比較し、各点の値が一致するか否かを判定する判定部を更に備えたことを特徴とする付記５に記載の暗号鍵解析装置。
【００８４】
（付記７）前記点生成部によって生成される点が所定の特徴を有する点となる頻度と、前記点判定部によって各点の値が一致すると判定されるまでに必要となるデータ量の期待値とを基にして、前記検査データのビット長を判定するビット長判定部を更に備え、前記抽出部は、前記ビット長に基づいて点の値から前記検査データを抽出することを特徴とする付記６に記載の暗号鍵解析装置。
【００８５】
（付記８）前記記憶部は、前記点生成部が生成した複数の点のうち、所定の特徴を有する点を記憶することを特徴とする付記５〜７のいずれか一つに記載の暗号鍵解析装置。
【００８６】
（付記９）コンピュータに、
点に対して写像を実行し、該写像の実行結果となる点に対して再度前記写像を実行する処理を繰り返し行う複数の点生成装置から点をそれぞれ取得し、取得した各点を記憶装置に記憶する記憶手順と、
前記記憶装置に記憶された複数の点から２つの点を選択し、選択した点の値の一部を検査データとしてそれぞれ抽出する抽出手順と、
前記抽出手順が抽出した各検査データを複数の検出装置に通知することで、前記検査データが一致するか否かの判定要求を行い、各検出装置から判定結果を取得する判定要求手順と、
を実行させることを特徴とする暗号鍵解析プログラム。
【００８７】
（付記１０）前記検出装置によって各検査データが一致すると判定された場合に、一致すると判定された各検査データの抽出元となる点の値をそれぞれ比較し、各点の値が一致するか否かを判定する判定手順を更に実行させることを特徴とする付記９に記載の暗号鍵解析プログラム。
【００８８】
（付記１１）前記点生成装置によって生成される点が所定の特徴を有する点となる頻度と、前記判定手順によって各点の値が一致すると判定されるまでに必要となるデータ量の期待値とを基にして、前記検査データのビット長を判定するビット長判定手順を更に実行させ、前記抽出手順は、前記ビット長に基づいて点の値から前記検査データを抽出することを特徴とする付記１０に記載の暗号鍵解析プログラム。
【００８９】
（付記１２）前記記憶手順は、前記点生成装置が生成した複数の点のうち、所定の特徴を有する点を前記記憶装置に記憶することを特徴とする付記９〜１１のいずれか一つに記載の暗号鍵解析プログラム。
【符号の説明】
【００９０】
１００ 暗号鍵解析装置
１１０ 記憶部
１２０ａ，１２０ｂ，１２０ｃ 点生成部
１３０ａ，１３０ｂ，１３０ｃ 衝突検出部
１４０ 制御部
【特許請求の範囲】
【請求項１】
コンピュータが、
点に対して写像を実行し、該写像の実行結果となる点に対して再度前記写像を実行する処理を繰り返し行う複数の点生成装置から点をそれぞれ取得し、取得した各点を記憶装置に記憶する記憶ステップと、
前記記憶装置に記憶された複数の点から２つの点を選択し、選択した点の値の一部を検査データとしてそれぞれ抽出する抽出ステップと、
前記抽出ステップが抽出した各検査データを複数の検出装置に通知することで、前記検査データが一致するか否かの判定要求を行い、各検出装置から判定結果を取得する判定要求ステップと
を実行することを特徴とする暗号鍵解析方法。
【請求項２】
前記検出装置によって各検査データが一致すると判定された場合に、一致すると判定された各検査データの抽出元となる点の値をそれぞれ比較し、各点の値が一致するか否かを判定する判定ステップを更に含んだことを特徴とする請求項１に記載の暗号鍵解析方法。
【請求項３】
前記点生成装置によって生成される点が所定の特徴を有する点となる頻度と、前記判定ステップによって各点の値が一致すると判定されるまでに必要となるデータ量の期待値とを基にして、前記検査データのビット長を判定するビット長判定ステップを更に含み、前記抽出ステップは、前記ビット長に基づいて点の値から前記検査データを抽出することを特徴とする請求項２に記載の暗号鍵解析方法。
【請求項４】
前記記憶ステップは、前記点生成装置が生成した複数の点のうち、所定の特徴を有する点を前記記憶装置に記憶することを特徴とする請求項１〜３のいずれか一つに記載の暗号鍵解析方法。
【請求項５】
点に対して写像を実行し、該写像の実行結果となる点に対して再度前記写像を実行する処理を繰り返し行う複数の点生成部から点をそれぞれ取得し、取得した各点を記憶する記憶部と、
前記記憶部に記憶された複数の点から２つの点を選択し、選択した点の値の一部を検査データとしてそれぞれ抽出する抽出部と、
前記抽出部が抽出した各検査データを複数の検出部に通知することで、前記検査データが一致するか否かの判定要求を行い、各検出部から判定結果を取得する判定要求部と
備えたことを特徴とする暗号鍵解析装置。
【請求項６】
コンピュータに、
点に対して写像を実行し、該写像の実行結果となる点に対して再度前記写像を実行する処理を繰り返し行う複数の点生成装置から点をそれぞれ取得し、取得した各点を記憶装置に記憶する記憶手順と、
前記記憶装置に記憶された複数の点から２つの点を選択し、選択した点の値の一部を検査データとしてそれぞれ抽出する抽出手順と、
前記抽出手順が抽出した各検査データを複数の検出装置に通知することで、前記検査データが一致するか否かの判定要求を行い、各検出装置から判定結果を取得する判定要求手順と、
を実行させることを特徴とする暗号鍵解析プログラム。
【請求項１】
コンピュータが、
点に対して写像を実行し、該写像の実行結果となる点に対して再度前記写像を実行する処理を繰り返し行う複数の点生成装置から点をそれぞれ取得し、取得した各点を記憶装置に記憶する記憶ステップと、
前記記憶装置に記憶された複数の点から２つの点を選択し、選択した点の値の一部を検査データとしてそれぞれ抽出する抽出ステップと、
前記抽出ステップが抽出した各検査データを複数の検出装置に通知することで、前記検査データが一致するか否かの判定要求を行い、各検出装置から判定結果を取得する判定要求ステップと
を実行することを特徴とする暗号鍵解析方法。
【請求項２】
前記検出装置によって各検査データが一致すると判定された場合に、一致すると判定された各検査データの抽出元となる点の値をそれぞれ比較し、各点の値が一致するか否かを判定する判定ステップを更に含んだことを特徴とする請求項１に記載の暗号鍵解析方法。
【請求項３】
前記点生成装置によって生成される点が所定の特徴を有する点となる頻度と、前記判定ステップによって各点の値が一致すると判定されるまでに必要となるデータ量の期待値とを基にして、前記検査データのビット長を判定するビット長判定ステップを更に含み、前記抽出ステップは、前記ビット長に基づいて点の値から前記検査データを抽出することを特徴とする請求項２に記載の暗号鍵解析方法。
【請求項４】
前記記憶ステップは、前記点生成装置が生成した複数の点のうち、所定の特徴を有する点を前記記憶装置に記憶することを特徴とする請求項１〜３のいずれか一つに記載の暗号鍵解析方法。
【請求項５】
点に対して写像を実行し、該写像の実行結果となる点に対して再度前記写像を実行する処理を繰り返し行う複数の点生成部から点をそれぞれ取得し、取得した各点を記憶する記憶部と、
前記記憶部に記憶された複数の点から２つの点を選択し、選択した点の値の一部を検査データとしてそれぞれ抽出する抽出部と、
前記抽出部が抽出した各検査データを複数の検出部に通知することで、前記検査データが一致するか否かの判定要求を行い、各検出部から判定結果を取得する判定要求部と
備えたことを特徴とする暗号鍵解析装置。
【請求項６】
コンピュータに、
点に対して写像を実行し、該写像の実行結果となる点に対して再度前記写像を実行する処理を繰り返し行う複数の点生成装置から点をそれぞれ取得し、取得した各点を記憶装置に記憶する記憶手順と、
前記記憶装置に記憶された複数の点から２つの点を選択し、選択した点の値の一部を検査データとしてそれぞれ抽出する抽出手順と、
前記抽出手順が抽出した各検査データを複数の検出装置に通知することで、前記検査データが一致するか否かの判定要求を行い、各検出装置から判定結果を取得する判定要求手順と、
を実行させることを特徴とする暗号鍵解析プログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【公開番号】特開２０１２−３２５２３（Ｐ２０１２−３２５２３Ａ）
【公開日】平成２４年２月１６日（２０１２．２．１６）
【国際特許分類】
【出願番号】特願２０１０−１７０８５０（Ｐ２０１０−１７０８５０）
【出願日】平成２２年７月２９日（２０１０．７．２９）
【国等の委託研究の成果に係る記載事項】（出願人による申告）平成２０年度、独立行政法人情報通信研究機構、「適切な暗号技術を選択可能とするための新しい暗号技術の評価手法 〜暗号の技術評価に関する研究開発〜」委託研究、産業技術力強化法第１９条の適用を受ける特許出願
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【Ｆターム（参考）】
【公開日】平成２４年２月１６日（２０１２．２．１６）
【国際特許分類】
【出願日】平成２２年７月２９日（２０１０．７．２９）
【国等の委託研究の成果に係る記載事項】（出願人による申告）平成２０年度、独立行政法人情報通信研究機構、「適切な暗号技術を選択可能とするための新しい暗号技術の評価手法 〜暗号の技術評価に関する研究開発〜」委託研究、産業技術力強化法第１９条の適用を受ける特許出願
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【Ｆターム（参考）】
[ Back to top ]