攻撃探索装置、攻撃探索方法、攻撃探索プログラム
【課題】位数ｐを含めて攻撃成功の可能性を探索する。
【解決手段】本発明の攻撃探索装置は、少なくとも多項式の演算として線形和を行うことが許可された条件で、攻撃が成功する可能性があるかを探索する。攻撃探索装置は、データ取得部、処理情報生成部、数式処理部、出力部を備える。データ取得部は、攻撃に利用できる多項式Ａ１，…，ＡＮ、解の条件Ｇ１＝Ｈ１，…，ＧＭ＝ＨＭを取得する。処理情報生成部は、前記解の条件の左辺と右辺の差をそれぞれ求め、多項式Ｅ１，…，ＥＭとする。数式処理部は、多項式Ｅ１からＥＭ中に現れる変数Ｘ１からＸＫのそれぞれ対して、
のように多項式Ａ１，…，ＡＮの線形和で表現できる０以上ｐ−１以下の整数ｃｍ１，…，ｃｍＮが存在し、かつ、Ｅ１＝ｂ１ｐ，…，ＥＭ＝ｂＭｐを満足する素数ｐと整数ｂ１，…，ｂＭが存在するかを探索する。
【解決手段】本発明の攻撃探索装置は、少なくとも多項式の演算として線形和を行うことが許可された条件で、攻撃が成功する可能性があるかを探索する。攻撃探索装置は、データ取得部、処理情報生成部、数式処理部、出力部を備える。データ取得部は、攻撃に利用できる多項式Ａ１，…，ＡＮ、解の条件Ｇ１＝Ｈ１，…，ＧＭ＝ＨＭを取得する。処理情報生成部は、前記解の条件の左辺と右辺の差をそれぞれ求め、多項式Ｅ１，…，ＥＭとする。数式処理部は、多項式Ｅ１からＥＭ中に現れる変数Ｘ１からＸＫのそれぞれ対して、
のように多項式Ａ１，…，ＡＮの線形和で表現できる０以上ｐ−１以下の整数ｃｍ１，…，ｃｍＮが存在し、かつ、Ｅ１＝ｂ１ｐ，…，ＥＭ＝ｂＭｐを満足する素数ｐと整数ｂ１，…，ｂＭが存在するかを探索する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号方式などに対する攻撃が可能かを探索する攻撃探索装置、攻撃探索方法、攻撃探索プログラムに関する。
【背景技術】
【０００２】
暗号方式などに対する攻撃が可能かを探索する従来技術として、群要素の恒等式を成り立たせるようなケースの有無を探索するＡＣＴＡＳ（Associative and Commutative Tree Automata Simulator）などが知られている（非特許文献１）。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】結合則・交換則ツリーオートマトンシミュレータ、ユーザーマニュアル（2005年4月1日作成）［平成２２年１０月２１日検索］、インターネット<URL: http://staff.aist.go.jp/hitoshi.ohsaki/actas/index.html>.
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、従来方法の場合、まず、ある位数ｐを具体的な値としてセットし、そのセットした位数ｐについて、攻撃者が攻撃成功となる場合が存在するか否かを探索する。しかし、得られる効果は、あくまでもある具体的に設定した位数ｐの値での攻撃成功の存在の有無であり、位数ｐを別の値に設定した場合の安全性については、別途改めて、位数ｐを設定し、探索結果を見なければならない。
【０００５】
本発明は、位数ｐを含めて攻撃成功の可能性を探索できる技術を提供することを目的とする。
【課題を解決するための手段】
【０００６】
本発明の攻撃探索装置は、少なくとも多項式の演算として線形和を行うことが許可された条件で、攻撃が成功する可能性があるかを探索する。なお、線形和以外にも多項式同士の乗算などを許可してもよい。本発明の攻撃探索装置は、データ取得部、処理情報生成部、数式処理部、出力部を備える。データ取得部は、攻撃に利用できる多項式Ａ１，…，ＡＮ、解の条件Ｇ１＝Ｈ１，…，ＧＭ＝ＨＭを取得する（ただし、Ｍ，Ｎは１以上の整数、Ｇ１，…，ＧＭ、Ｈ１，…，ＨＭは多項式）。なお、多項式の演算として線形和以外も許容する場合は、データ取得部は、どのような演算が許容させるのかの情報も受け取ればよい。処理情報生成部は、解の条件の左辺と右辺の差をそれぞれ求め、多項式Ｅ１，…，ＥＭとする。具体的には、Ｅ１＝Ｇ１−Ｈ１，…，ＥＭ＝ＧＭ−ＨＭまたはＥ１＝Ｈ１−Ｇ１，…，ＥＭ＝ＨＭ−ＧＭのように多項式Ｅ１，…，ＥＭを求めればよい。数式処理部は、多項式Ｅ１からＥＭ中に現れる変数Ｘ１からＸＫのそれぞれ対して、
【０００７】
【数１】
【０００８】
のように多項式Ａ１，…，ＡＮの線形和で表現できる０以上ｐ−１以下の整数ｃｍ１，…，ｃｍＮが存在して、かつ、Ｅ１＝ｂ１ｐ，…，ＥＭ＝ｂＭｐを満足する素数ｐと整数ｂ１，…，ｂＭが存在するかを探索する（ただし、Ｋは１以上の整数、ｋは１以上Ｋ以下の整数、ｍは１以上Ｍ以下の整数）。なお、多項式の演算として線形和以外も許容する場合は、数式処理部は、許容された演算も利用して多項式Ｅ１，…，ＥＭ中に現れる変数Ｘ１からＸＫが表現できないかも探索する。出力部は、数式処理部の探索結果を出力する。
【発明の効果】
【０００９】
本発明の攻撃探索装置によれば、探索を開始する際に、ある具体的に特定した位数ｐを設定する必要が無いので、あらゆる位数ｐについての、攻撃者の成功の可能性を一気に探索することができる。
【図面の簡単な説明】
【００１０】
【図１】本発明の攻撃探索装置の機能構成例を示す図。
【図２】本発明の攻撃探索装置の処理フローを示す図。
【発明を実施するための形態】
【００１１】
以下、本発明の実施の形態について、詳細に説明する。なお、同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【実施例１】
【００１２】
図１に本発明の攻撃探索装置の機能構成例を示す。図２に本発明の攻撃探索装置の処理フローを示す。本発明の攻撃探索装置は、少なくとも多項式の演算として線形和を行うことが許可された条件で、攻撃が成功する可能性があるかを探索する。なお、線形和以外にも多項式同士の乗算などを許可してもよい。攻撃探索装置１００は、データ取得部１１０、処理情報生成部１２０、数式処理部１３０、出力部１４０、記録部１９０を備える。以下の説明では、Ｋ，Ｍ，Ｎは１以上の整数、ｋは１以上Ｋ以下の整数、ｍは１以上Ｍ以下の整数、ｎは１以上Ｎ以下の整数とする。また、多項式には、定数だけの場合（変数がない場合）、項が１つだけの場合も含むものとする。
【００１３】
データ取得部１１０は、攻撃に利用できる多項式Ａ１，…，ＡＮ、解の条件Ｇ１＝Ｈ１，…，ＧＭ＝ＨＭを取得する（Ｓ１１０）。ここで、Ｇ１，…，ＧＭ、Ｈ１，…，ＨＭは多項式である。なお、多項式の演算として線形和以外も許容する場合は、データ取得部は、どのような演算が許容させるのかの情報も受け取ればよい。処理情報生成部１２０は、解の条件の左辺と右辺の差をそれぞれ求め、多項式Ｅ１，…，ＥＭとする（Ｓ１２０）。具体的には、Ｅ１＝Ｇ１−Ｈ１，…，ＥＭ＝ＧＭ−ＨＭまたはＥ１＝Ｈ１−Ｇ１，…，ＥＭ＝ＨＭ−ＧＭのように多項式Ｅ１，…，ＥＭを求めればよい。
【００１４】
数式処理部１３０は、多項式Ｅ１からＥＭ中に現れる変数Ｘ１からＸＫのそれぞれ対して、
【００１５】
【数２】
【００１６】
のように多項式Ａ１，…，ＡＮの線形和で表現できる０以上ｐ−１以下の整数ｃｍ１，…，ｃｍＮが存在し、かつ、Ｅ１＝ｂ１ｐ，…，ＥＭ＝ｂＭｐを満足する素数ｐと整数ｂ１，…，ｂＭが存在するかを探索する（Ｓ１３０）。なお、多項式の演算として線形和以外も許容する場合は、数式処理部１３０は、許容された演算も利用して多項式Ｅ１，…，ＥＭ中に現れる変数Ｘ１からＸＫが表現できないかも探索すればよいが、少なくとも上記の探索は行う。また、数式処理部１３０の処理は、Ｍａｐｌｅ(メイプル)などの一般的な数式処理・数式モデル用のソフトウェアを利用すれば実行できる（参考文献１：数式処理・数式モデル設計環境、Ｍａｐｌｅ(メイプル)［平成２２年１０月２１日検索］、インターネット<URL: http://www.cybernet.co.jp/maple/product/maple/>.）。
【００１７】
出力部１４０は、数式処理部１３０の探索結果を出力する（Ｓ１４０）。探索の結果、いずれかの素数ｐに対して、整数ｃ1１，…，ｃ1Ｎ，ｃ２１，…，ｃ２Ｎ，…，ｃｍ１，…，ｃｍＮ，…，ｃＭ１，…，ｃＭＮ、整数ｂ１，…，ｂＭが存在すれば、その素数ｐを位数とする場合には解の条件Ｇ１＝Ｈ１，…，ＧＭ＝ＨＭを成り立たせる場合が存在することになる。したがって、探索結果によって攻撃成功の可能性の有無が分かる。
【００１８】
このように、本発明の攻撃探索装置によれば、探索を開始する際に、ある具体的に特定した位数ｐを設定する必要が無いので、あらゆる位数ｐについての、攻撃者の成功の可能性を一気に探索できる。
【００１９】
［プログラム、記録媒体］
上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【００２０】
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
【００２１】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００２２】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００２３】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００２４】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【産業上の利用可能性】
【００２５】
本発明は、暗号システムの安全性の確認に利用できる。
【符号の説明】
【００２６】
１００ 攻撃探索装置 １１０ データ取得部
１２０ 処理情報生成部 １３０ 数式処理部
１４０ 出力部 １９０ 記録部
【技術分野】
【０００１】
本発明は、暗号方式などに対する攻撃が可能かを探索する攻撃探索装置、攻撃探索方法、攻撃探索プログラムに関する。
【背景技術】
【０００２】
暗号方式などに対する攻撃が可能かを探索する従来技術として、群要素の恒等式を成り立たせるようなケースの有無を探索するＡＣＴＡＳ（Associative and Commutative Tree Automata Simulator）などが知られている（非特許文献１）。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】結合則・交換則ツリーオートマトンシミュレータ、ユーザーマニュアル（2005年4月1日作成）［平成２２年１０月２１日検索］、インターネット<URL: http://staff.aist.go.jp/hitoshi.ohsaki/actas/index.html>.
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、従来方法の場合、まず、ある位数ｐを具体的な値としてセットし、そのセットした位数ｐについて、攻撃者が攻撃成功となる場合が存在するか否かを探索する。しかし、得られる効果は、あくまでもある具体的に設定した位数ｐの値での攻撃成功の存在の有無であり、位数ｐを別の値に設定した場合の安全性については、別途改めて、位数ｐを設定し、探索結果を見なければならない。
【０００５】
本発明は、位数ｐを含めて攻撃成功の可能性を探索できる技術を提供することを目的とする。
【課題を解決するための手段】
【０００６】
本発明の攻撃探索装置は、少なくとも多項式の演算として線形和を行うことが許可された条件で、攻撃が成功する可能性があるかを探索する。なお、線形和以外にも多項式同士の乗算などを許可してもよい。本発明の攻撃探索装置は、データ取得部、処理情報生成部、数式処理部、出力部を備える。データ取得部は、攻撃に利用できる多項式Ａ１，…，ＡＮ、解の条件Ｇ１＝Ｈ１，…，ＧＭ＝ＨＭを取得する（ただし、Ｍ，Ｎは１以上の整数、Ｇ１，…，ＧＭ、Ｈ１，…，ＨＭは多項式）。なお、多項式の演算として線形和以外も許容する場合は、データ取得部は、どのような演算が許容させるのかの情報も受け取ればよい。処理情報生成部は、解の条件の左辺と右辺の差をそれぞれ求め、多項式Ｅ１，…，ＥＭとする。具体的には、Ｅ１＝Ｇ１−Ｈ１，…，ＥＭ＝ＧＭ−ＨＭまたはＥ１＝Ｈ１−Ｇ１，…，ＥＭ＝ＨＭ−ＧＭのように多項式Ｅ１，…，ＥＭを求めればよい。数式処理部は、多項式Ｅ１からＥＭ中に現れる変数Ｘ１からＸＫのそれぞれ対して、
【０００７】
【数１】
【０００８】
のように多項式Ａ１，…，ＡＮの線形和で表現できる０以上ｐ−１以下の整数ｃｍ１，…，ｃｍＮが存在して、かつ、Ｅ１＝ｂ１ｐ，…，ＥＭ＝ｂＭｐを満足する素数ｐと整数ｂ１，…，ｂＭが存在するかを探索する（ただし、Ｋは１以上の整数、ｋは１以上Ｋ以下の整数、ｍは１以上Ｍ以下の整数）。なお、多項式の演算として線形和以外も許容する場合は、数式処理部は、許容された演算も利用して多項式Ｅ１，…，ＥＭ中に現れる変数Ｘ１からＸＫが表現できないかも探索する。出力部は、数式処理部の探索結果を出力する。
【発明の効果】
【０００９】
本発明の攻撃探索装置によれば、探索を開始する際に、ある具体的に特定した位数ｐを設定する必要が無いので、あらゆる位数ｐについての、攻撃者の成功の可能性を一気に探索することができる。
【図面の簡単な説明】
【００１０】
【図１】本発明の攻撃探索装置の機能構成例を示す図。
【図２】本発明の攻撃探索装置の処理フローを示す図。
【発明を実施するための形態】
【００１１】
以下、本発明の実施の形態について、詳細に説明する。なお、同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【実施例１】
【００１２】
図１に本発明の攻撃探索装置の機能構成例を示す。図２に本発明の攻撃探索装置の処理フローを示す。本発明の攻撃探索装置は、少なくとも多項式の演算として線形和を行うことが許可された条件で、攻撃が成功する可能性があるかを探索する。なお、線形和以外にも多項式同士の乗算などを許可してもよい。攻撃探索装置１００は、データ取得部１１０、処理情報生成部１２０、数式処理部１３０、出力部１４０、記録部１９０を備える。以下の説明では、Ｋ，Ｍ，Ｎは１以上の整数、ｋは１以上Ｋ以下の整数、ｍは１以上Ｍ以下の整数、ｎは１以上Ｎ以下の整数とする。また、多項式には、定数だけの場合（変数がない場合）、項が１つだけの場合も含むものとする。
【００１３】
データ取得部１１０は、攻撃に利用できる多項式Ａ１，…，ＡＮ、解の条件Ｇ１＝Ｈ１，…，ＧＭ＝ＨＭを取得する（Ｓ１１０）。ここで、Ｇ１，…，ＧＭ、Ｈ１，…，ＨＭは多項式である。なお、多項式の演算として線形和以外も許容する場合は、データ取得部は、どのような演算が許容させるのかの情報も受け取ればよい。処理情報生成部１２０は、解の条件の左辺と右辺の差をそれぞれ求め、多項式Ｅ１，…，ＥＭとする（Ｓ１２０）。具体的には、Ｅ１＝Ｇ１−Ｈ１，…，ＥＭ＝ＧＭ−ＨＭまたはＥ１＝Ｈ１−Ｇ１，…，ＥＭ＝ＨＭ−ＧＭのように多項式Ｅ１，…，ＥＭを求めればよい。
【００１４】
数式処理部１３０は、多項式Ｅ１からＥＭ中に現れる変数Ｘ１からＸＫのそれぞれ対して、
【００１５】
【数２】
【００１６】
のように多項式Ａ１，…，ＡＮの線形和で表現できる０以上ｐ−１以下の整数ｃｍ１，…，ｃｍＮが存在し、かつ、Ｅ１＝ｂ１ｐ，…，ＥＭ＝ｂＭｐを満足する素数ｐと整数ｂ１，…，ｂＭが存在するかを探索する（Ｓ１３０）。なお、多項式の演算として線形和以外も許容する場合は、数式処理部１３０は、許容された演算も利用して多項式Ｅ１，…，ＥＭ中に現れる変数Ｘ１からＸＫが表現できないかも探索すればよいが、少なくとも上記の探索は行う。また、数式処理部１３０の処理は、Ｍａｐｌｅ(メイプル)などの一般的な数式処理・数式モデル用のソフトウェアを利用すれば実行できる（参考文献１：数式処理・数式モデル設計環境、Ｍａｐｌｅ(メイプル)［平成２２年１０月２１日検索］、インターネット<URL: http://www.cybernet.co.jp/maple/product/maple/>.）。
【００１７】
出力部１４０は、数式処理部１３０の探索結果を出力する（Ｓ１４０）。探索の結果、いずれかの素数ｐに対して、整数ｃ1１，…，ｃ1Ｎ，ｃ２１，…，ｃ２Ｎ，…，ｃｍ１，…，ｃｍＮ，…，ｃＭ１，…，ｃＭＮ、整数ｂ１，…，ｂＭが存在すれば、その素数ｐを位数とする場合には解の条件Ｇ１＝Ｈ１，…，ＧＭ＝ＨＭを成り立たせる場合が存在することになる。したがって、探索結果によって攻撃成功の可能性の有無が分かる。
【００１８】
このように、本発明の攻撃探索装置によれば、探索を開始する際に、ある具体的に特定した位数ｐを設定する必要が無いので、あらゆる位数ｐについての、攻撃者の成功の可能性を一気に探索できる。
【００１９】
［プログラム、記録媒体］
上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【００２０】
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
【００２１】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００２２】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００２３】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００２４】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【産業上の利用可能性】
【００２５】
本発明は、暗号システムの安全性の確認に利用できる。
【符号の説明】
【００２６】
１００ 攻撃探索装置 １１０ データ取得部
１２０ 処理情報生成部 １３０ 数式処理部
１４０ 出力部 １９０ 記録部
【特許請求の範囲】
【請求項１】
少なくとも多項式の演算として線形和を行うことが許可された条件で、攻撃が成功する可能性があるかを探索する攻撃探索装置であって、
Ｋ，Ｍ，Ｎは１以上の整数、ｋは１以上Ｋ以下の整数、ｍは１以上Ｍ以下の整数、ｎは１以上Ｎ以下の整数とし、
攻撃に利用できる多項式Ａ１，…，ＡＮ、解の条件Ｇ１＝Ｈ１，…，ＧＭ＝ＨＭを取得するデータ取得部と、
前記解の条件の左辺と右辺の差をそれぞれ求め、多項式Ｅ１，…，ＥＭとする処理情報生成部と、
多項式Ｅ１からＥＭ中に現れる変数Ｘ１からＸＫのそれぞれ対して、
【数３】
のように多項式Ａ１，…，ＡＮの線形和で表現できる０以上ｐ−１以下の整数ｃｍ１，…，ｃｍＮが存在し、かつ、Ｅ１＝ｂ１ｐ，…，ＥＭ＝ｂＭｐを満足する素数ｐと整数ｂ１，…，ｂＭが存在するかを探索する数式処理部と、
前記数式処理部の探索結果を出力する出力部と、
を備える攻撃探索装置。
【請求項２】
少なくとも多項式の演算として線形和を行うことが許可された条件で、攻撃が成功する可能性があるかを探索する攻撃探索方法であって、
Ｋ，Ｍ，Ｎは１以上の整数、ｋは１以上Ｋ以下の整数、ｍは１以上Ｍ以下の整数、ｎは１以上Ｎ以下の整数とし、
データ取得部が、攻撃に利用できる多項式Ａ１，…，ＡＮ、解の条件Ｇ１＝Ｈ１，…，ＧＭ＝ＨＭを取得するデータ取得ステップと、
処理情報生成部が、前記解の条件の左辺と右辺の差をそれぞれ求め、多項式Ｅ１，…，ＥＭとする処理情報生成ステップと、
数式処理部が、多項式Ｅ１からＥＭ中に現れる変数Ｘ１からＸＫのそれぞれ対して、
【数４】
のように多項式Ａ１，…，ＡＮの線形和で表現できる０以上ｐ−１以下の整数ｃｍ１，…，ｃｍＮが存在し、かつ、Ｅ１＝ｂ１ｐ，…，ＥＭ＝ｂＭｐを満足する素数ｐと整数ｂ１，…，ｂＭが存在するかを探索する数式処理ステップと、
出力部が、前記数式処理ステップの探索結果を出力する出力ステップと、
を有する攻撃探索方法。
【請求項３】
請求項１記載の攻撃探索装置としてコンピュータを機能させるための攻撃探索プログラム。
【請求項１】
少なくとも多項式の演算として線形和を行うことが許可された条件で、攻撃が成功する可能性があるかを探索する攻撃探索装置であって、
Ｋ，Ｍ，Ｎは１以上の整数、ｋは１以上Ｋ以下の整数、ｍは１以上Ｍ以下の整数、ｎは１以上Ｎ以下の整数とし、
攻撃に利用できる多項式Ａ１，…，ＡＮ、解の条件Ｇ１＝Ｈ１，…，ＧＭ＝ＨＭを取得するデータ取得部と、
前記解の条件の左辺と右辺の差をそれぞれ求め、多項式Ｅ１，…，ＥＭとする処理情報生成部と、
多項式Ｅ１からＥＭ中に現れる変数Ｘ１からＸＫのそれぞれ対して、
【数３】
のように多項式Ａ１，…，ＡＮの線形和で表現できる０以上ｐ−１以下の整数ｃｍ１，…，ｃｍＮが存在し、かつ、Ｅ１＝ｂ１ｐ，…，ＥＭ＝ｂＭｐを満足する素数ｐと整数ｂ１，…，ｂＭが存在するかを探索する数式処理部と、
前記数式処理部の探索結果を出力する出力部と、
を備える攻撃探索装置。
【請求項２】
少なくとも多項式の演算として線形和を行うことが許可された条件で、攻撃が成功する可能性があるかを探索する攻撃探索方法であって、
Ｋ，Ｍ，Ｎは１以上の整数、ｋは１以上Ｋ以下の整数、ｍは１以上Ｍ以下の整数、ｎは１以上Ｎ以下の整数とし、
データ取得部が、攻撃に利用できる多項式Ａ１，…，ＡＮ、解の条件Ｇ１＝Ｈ１，…，ＧＭ＝ＨＭを取得するデータ取得ステップと、
処理情報生成部が、前記解の条件の左辺と右辺の差をそれぞれ求め、多項式Ｅ１，…，ＥＭとする処理情報生成ステップと、
数式処理部が、多項式Ｅ１からＥＭ中に現れる変数Ｘ１からＸＫのそれぞれ対して、
【数４】
のように多項式Ａ１，…，ＡＮの線形和で表現できる０以上ｐ−１以下の整数ｃｍ１，…，ｃｍＮが存在し、かつ、Ｅ１＝ｂ１ｐ，…，ＥＭ＝ｂＭｐを満足する素数ｐと整数ｂ１，…，ｂＭが存在するかを探索する数式処理ステップと、
出力部が、前記数式処理ステップの探索結果を出力する出力ステップと、
を有する攻撃探索方法。
【請求項３】
請求項１記載の攻撃探索装置としてコンピュータを機能させるための攻撃探索プログラム。
【図１】
【図２】
【図２】
【公開番号】特開２０１２−１０４９８３（Ｐ２０１２−１０４９８３Ａ）
【公開日】平成２４年５月３１日（２０１２．５．３１）
【国際特許分類】
【出願番号】特願２０１０−２５０５２５（Ｐ２０１０−２５０５２５）
【出願日】平成２２年１１月９日（２０１０．１１．９）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【出願人】（５０４１７６９１１）国立大学法人大阪大学 (1,536)
【Ｆターム（参考）】
【公開日】平成２４年５月３１日（２０１２．５．３１）
【国際特許分類】
【出願日】平成２２年１１月９日（２０１０．１１．９）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【出願人】（５０４１７６９１１）国立大学法人大阪大学 (1,536)
【Ｆターム（参考）】
[ Back to top ]