不能差分探索装置、不能差分探索方法及びプログラム
【課題】入力ワード差分と出力ワード差分の組み合わせが非ゼロと非ゼロの場合についてもＩＤ特性を検出することができる不能差分探索装置の提供。
【解決手段】不能差分探索装置は、共通鍵ブロック暗号を構成するラウンド関数内部で使用される非線形関数の入力差分値と出力差分値とに関する１対多の対応表を保持し、該１対多の対応表を用いて、複数のワードで構成される入力差分の入力ワード差分から取り得る入力差分値と、複数のワードで構成される出力差分の出力ワード差分から取り得る出力差分値と、の組み合わせがあり得るか否かを判定する判定部を用いて、入力差分から生成した各入力差分値と、各入力差分値に対応する位置の出力差分値との組み合わせがあり得るか否かを判定してゆき、取りうる出力差分値のすべてが前記入力差分値との組み合わせとしてあり得ない出力ワード差分の存在を１つでも確認できた場合に、その入力差分と出力差分の組が不能差分であると判定する。
【解決手段】不能差分探索装置は、共通鍵ブロック暗号を構成するラウンド関数内部で使用される非線形関数の入力差分値と出力差分値とに関する１対多の対応表を保持し、該１対多の対応表を用いて、複数のワードで構成される入力差分の入力ワード差分から取り得る入力差分値と、複数のワードで構成される出力差分の出力ワード差分から取り得る出力差分値と、の組み合わせがあり得るか否かを判定する判定部を用いて、入力差分から生成した各入力差分値と、各入力差分値に対応する位置の出力差分値との組み合わせがあり得るか否かを判定してゆき、取りうる出力差分値のすべてが前記入力差分値との組み合わせとしてあり得ない出力ワード差分の存在を１つでも確認できた場合に、その入力差分と出力差分の組が不能差分であると判定する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、不能差分探索装置、不能差分探索方法及びプログラムに関し、特に、暗号アルゴリズムの安全性の評価に用いる不能差分特性を検出する不能差分探索装置、不能差分探索方法及びプログラムに関する。
【背景技術】
【０００２】
不能差分解析は、ブロック暗号の解析手法の一つである。不能差分解析は、成立し得ない差分特性（この特性を不能差分特性（Ｉｍｐｏｓｓｉｂｌｅ Ｄｉｆｆｅｒｅｎｔｉａｌｓ）と呼び、以降「ＩＤ特性」と記載する。）を使い、ブロック暗号の最初の数ラウンドや最後の数ラウンドの鍵を求めるものである（非特許文献１参照）。入力データをＸ個のサブブロックに分割して処理する構造を持つ共通鍵ブロック暗号では上記分割数Ｘが大きいほど、長いＩＤ特性があることが知られており、ＩＤ特性を見つけることは、上記不能差分解析にとって大変重要である。
【０００３】
非特許文献２のＩＤ特性探索手法は暗号化処理の順方向（入力は平文側、出力は暗号文側）と逆方向（入力は暗号文側、出力は平文側）にラウンド通過毎の差分（以降、ラウンド差分と呼ぶ）を計算する。その際、ブロック幅でのすべての入力差分値についてラウンド差分を計算することは、計算量的に実現が困難である。そこで、非特許文献２の手法では、差分をＸ個のワードに分割した上でワード毎の差分（以降、ワード差分と呼ぶ）をいくつかに分類し、ラウンド関数やラウンド関数内の部品関数の入力ワード差分と出力ワード差分を１対１で対応させる表を参照してラウンド差分を計算することで計算量を削減している（非特許文献２の表１、表２参照）。非特許文献２は、このようにして順方向と逆方向に差分を計算して得られた差分同士を比較し、ＩＤ特性を見つける方法を開示している。
【０００４】
また、特許文献１に、暗号仕様に従って差分集合をワード長単位に操作してＩＤ特性を検出する方法が開示されている。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２０００−２１４７７０号公報
【非特許文献】
【０００６】
【非特許文献１】Ｅ． Ｂｉｈａｍ， Ａ． Ｂｉｒｙｕｋｏｖ ａｎｄ Ａ． Ｓｈａｍｉｒ， “Ｃｒｙｐｔａｎａｌｙｓｉｓ ｏｆ Ｓｋｉｐｊａｃｋ Ｒｅｄｕｃｅｄ ｔｏ ３１ Ｒｏｕｎｄｓ Ｕｓｉｎｇ Ｉｍｐｏｓｓｉｂｌｅ Ｄｉｆｆｅｒｅｎｔｉａｌｓ”， ＥＵＲＯＣＲＹＰＴ’９９， ＬＮＣＳ １５９２， Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ， １９９９， ｐｐ．１２−２３．
【非特許文献２】中嶋、辻原、茂、川幡、角尾、 “不能差分特性探索手法の改良”、２００８年暗号と情報セキュリティシンポジウム（ＳＣＩＳ２００８）、２Ａ４−２、２００８
【発明の概要】
【発明が解決しようとする課題】
【０００７】
以上の特許文献１および非特許文献１、２の全開示内容は、本書に引用をもって繰り込み記載されているものとする。
以下の分析は、本発明の観点から与えられる。
【０００８】
図１７に示す関数Ｆが繰り返される暗号アルゴリズムを用いて、非特許文献２のＩＤ特性探索手法の具体例を説明する。図１７の関数Ｆは１ワードが４ビットである４ワードのデータを変換する関数とし、４ワードのデータは、２行２列の行列または、ワード数４のベクトルで表現する。関数ＳＢは４ビット幅の非線形変換部（Ｓ−ｂｏｘ）を用いて各ワードを変換する。関数ＳＲは、２行目のデータを１バイト左ローテイトシフトする、つまり２行目の２ワードを入れ替える。関数ＭＣは次の［数１］のように、２行２列の行列によってデータを変換する。ここで行列演算は既約多項式ｘ＾４＋ｘ＋１で規定されるＧＦ（２＾４）上の演算とする。また関数ＡＫはデータに４ワードの鍵データを排他的論理和する。
【０００９】
【数１】
【００１０】
図１８は、復号化で用いられる関数Ｆの逆関数を示している。関数ＳＢ＾−１、ＳＲ＾−１、ＭＣ＾−１、ＡＫ＾−１はそれぞれ関数ＳＢ、ＳＲ、ＭＣ、ＡＫの逆関数である。関数ＭＣ＾−１の行列演算は、［数２］となる。
【００１１】
【数２】
【００１２】
非特許文献２のＩＤ特性探索手法では、ワード差分を例えば図１９の０ｄ、ｎｄ、ｎｄ＊、ｒｄ（非特許文献２のＺｅｒｏ、Ｄｅｌｔａ、Ｆｉｘ（Ｆｉｘ２）、Ｒａｎｄｏｍに相当。）に分類し、関数Ｆおよび関数Ｆ＾−１中における各部品関数の入力ワード差分と出力ワード差分の１対１の対応関係を図２０のように定義している。図２０のｎ，ｍは互いに異なる数値とする。
【００１３】
このような関数を入出力差分が順方向または逆方向に進む毎に各関数の差分を計算し遷移させる。図２１は、入力差分が（１ｄ＊、０ｄ、０ｄ、０ｄ）、逆方向の入力である出力差分が（１ｄ、０ｄ、０ｄ、０ｄ）の場合の差分の遷移を表している。入力差分（１ｄ＊、０ｄ、０ｄ、０ｄ）は、関数ＳＲを通過して（１ｄ＊、０ｄ、０ｄ、０ｄ）となる。さらに（１ｄ＊、０ｄ、０ｄ、０ｄ）が、関数ＭＣを通過すると、（１ｄ＊、１ｄ＊、０ｄ、０ｄ）となる。他の関数も同様に差分を計算し遷移させる。
【００１４】
上記のようにして入力差分から計算されたｄｉｆ１と、出力差分から計算されたｄｉｆ２とを図２２の判定表を用いて比較する。図２２の例ではｎ≠ｍ、ｋ≠ｋ’とし、比較するワード差分の組み合わせとしてありえないものがｉｍｐｏｓｓｉｂｌｅ、ありえるものがｐｏｓｓｉｂｌｅと設定されている。例えば、ワード差分０ｄと１ｄの比較では、差分０と非ゼロの差分の比較なので、判定はｉｍｐｏｓｓｉｂｌｅとなる。図２１のｄｉｆ１とｄｉｆ２は、２ワード目と３ワード目でワード差分１ｄと０ｄが不能と判定され、入力差分が（１ｄ＊、０ｄ、０ｄ、０ｄ）であり出力差分が（１ｄ、０ｄ、０ｄ、０ｄ）というＩＤ特性が見つかる。
【００１５】
上記非特許文献２のＩＤ特性探索手法では、ラウンド関数またはラウンド関数内の非線形関数における入力差分と出力差分のワード差分を１対１で対応させる表（図２０参照）を参照することで、ラウンド関数または非線形関数通過後の差分を計算している。しかし、この方法では不能差分を判定する際の入力ワード差分と出力ワード差分の組み合わせが（非ゼロ，ゼロ）である場合と（ゼロ，非ゼロ）である場合しか不能差分として判定することができない。
【００１６】
しかしながら実際には、ラウンド関数またはラウンド関数内の非線形関数の入力と出力とを見たときに、入力ワード差分と出力ワード差分の組み合わせが（非ゼロ，非ゼロ）の場合でも不能差分が存在することがある。
【００１７】
例えば、図２３は、上記非特許文献２のＩＤ特性探索手法における入力差分が（１ｄ＊、２ｄ＊、０ｄ、０ｄ）、出力差分が（１ｄ、０ｄ、０ｄ、０ｄ）の場合の差分の遷移を表している。入力差分から計算されたｄｉｆ３と出力差分から計算されたｄｉｆ４とを図２２の判定表を用いて比較したとき、いずれの４ワードでもｐｏｓｓｉｂｌｅとなり、不能とは判定されない。
【００１８】
このように非特許文献２のＩＤ特性探索手法では入力ワード差分と出力ワード差分の組み合わせが（非ゼロの特定の差分，任意の差分）である場合と（任意の差分，非ゼロの特定の差分）である場合のＩＤ特性が検出できないという問題点がある。
【００１９】
本発明は、上記した事情に鑑みてなされたものであって、その目的とするところは、ラウンド関数またはラウンド関数内の非線形関数の入力ワード差分と出力ワード差分の組み合わせが非ゼロと非ゼロの場合についてもＩＤ特性を検出することができる不能差分探索装置、不能差分探索方法及びプログラムを提供することにある。
【課題を解決するための手段】
【００２０】
本発明の第１の視点によれば、共通鍵ブロック暗号を構成するラウンド関数内部で使用される非線形関数の入力差分値と出力差分値とに関する１対多の対応表を保持し、該１対多の対応表を用いて、２つ以上のワード（入力ワード差分）で構成される入力差分の入力ワード差分から取り得る入力差分値と、２つ以上のワード（出力ワード差分）で構成される出力差分の出力ワード差分から取り得る出力差分値と、の組み合わせがあり得るか否かを判定する判定部と、前記判定部を用いて、入力差分から生成した各入力差分値と、各入力差分値に対応する位置の出力差分値との組み合わせがあり得るか否かを判定してゆき、取りうる出力差分値のすべてが前記入力差分値との組み合わせとしてあり得ない出力ワード差分の存在を１つでも確認できた場合に、その入力差分と出力差分の組が不能差分であると判定する不能差分判定部と、を備える不能差分探索装置が提供される。
【００２１】
本発明の第２の視点によれば、共通鍵ブロック暗号を構成するラウンド関数内部で使用される非線形関数の入力差分値と出力差分値とに関する１対多の対応表を保持し、該１対多の対応表を用いて、２つ以上のワード（入力ワード差分）で構成される入力差分の入力ワード差分から取り得る入力差分値と、２つ以上のワード（出力ワード差分）で構成される出力差分の出力ワード差分から取り得る出力差分値と、の組み合わせがあり得るか否かを判定するステップを繰り返し、取りうる出力差分値のすべてが前記入力差分値との組み合わせとしてあり得ない出力ワード差分の存在を１つでも確認できた場合に、その入力差分と出力差分の組が不能差分であると判定する不能差分探索方法が提供される。なお、本方法は、不能差分探索装置という、特定の機械に結びつけられている。
【００２２】
本発明の第３の視点によれば、共通鍵ブロック暗号を構成するラウンド関数内部で使用される非線形関数の入力差分値と出力差分値とに関する１対多の対応表を保持し、該１対多の対応表を用いて、２つ以上のワード（入力ワード差分）で構成される入力差分の入力ワード差分から取り得る入力差分値と、２つ以上のワード（出力ワード差分）で構成される出力差分の出力ワード差分から取り得る出力差分値と、の組み合わせがあり得るか否かを判定する処理を繰り返し、取りうる出力差分値のすべてが前記入力差分値との組み合わせとしてあり得ない出力ワード差分の存在を１つでも確認できた場合に、その入力差分と出力差分の組が不能差分であると判定する処理をコンピュータに実行させるプログラムが提供される。なお、このプログラムは、コンピュータが読み取り可能な記憶媒体に記録することができる。
【発明の効果】
【００２３】
本発明によれば、ラウンド関数またはラウンド関数内の非線形関数の入力ワード差分と出力ワード差分の組み合わせが非ゼロと非ゼロの場合についてもＩＤ特性を検出することができる。
【図面の簡単な説明】
【００２４】
【図１】本発明の概要および本発明の第１の実施形態を説明するための図である。
【図２】本発明に係る不能差分探索装置による不能差分の探索例を示す図である。
【図３】本発明の第１の実施形態の構成を示すブロック図である。
【図４】１対多の対応表の一例を示す図である。
【図５】本発明の第１の実施形態の不能差分の探索処理の流れを表したフローチャートである。
【図６】本発明の第２の実施形態の構成を示すブロック図である。
【図７】本発明の第２の実施形態の不能差分の探索処理の流れを表したフローチャートである。
【図８】本発明の第３の実施形態の構成を示すブロック図である。
【図９】関数ＭＣ内の排他的論理和における入出力差分１対１対応表の例を示す図である。
【図１０】関数ＭＣ内の乗算における入出力差分１対１対応表の例を示す図である。
【図１１】本発明の第３の実施形態のラウンド差分部によるラウンド差分計算例（順方向）を示す図である。
【図１２】本発明の第３の実施形態のラウンド差分部によるラウンド差分計算例（逆方向）を示す図である。
【図１３】本発明の第３の実施形態の不能差分の探索処理の流れを表したフローチャートである。
【図１４】本発明の第３の実施形態の１対多対応位置決定部における処理の流れを表したフローチャートである。
【図１５】本発明の第４の実施形態の構成を示すブロック図である。
【図１６】本発明の第４の実施形態の不能差分の探索処理の流れを表したフローチャートである。
【図１７】評価対象の暗号アルゴリズムの関数Ｆを示す図である。
【図１８】評価対象の暗号アルゴリズムの復号に用いる逆関数Ｆ＾−１を示す図である。
【図１９】ワード差分定義の例を示す図である。
【図２０】図１７の関数ＳＢおよび図１８のＳＢ＾−１内のＳ−ｂｏｘでの入出力差分１対１対応表の例を示す図である。
【図２１】非特許文献２の手法による不能差分の探索例を示す図である。
【図２２】非特許文献２の手法における不能差分の判定に用いる表である。
【図２３】非特許文献２の手法では不能差分と判定できない例を示す図である。
【発明を実施するための形態】
【００２５】
はじめに、本発明の概要について説明する。本発明では、ラウンド関数内部のＳ−ｂｏｘのような非線形関数における入力差分値と出力差分値の１対多の対応関係を表した対応表を用いる（図４参照）。例えば、この１対多の対応表には、入力差分値５に対して出力差分値は１、３、５という奇数を取り得るといった１対多の対応関係が示される。
【００２６】
本発明に係る不能差分探索装置は、上記１対多の対応表を参照し、入力差分値と出力差分値の組が有り得るか、有り得ないかを判定する判定部を備える。本発明に係る不能差分探索装置は、上記判定部を用いて、入力ワード差分が取りうる入力差分値（例えば、図１のａ１、ａ２、・・・）に対し、出力差分が、一つでもあり得ない出力差分値を持つことを確認できた場合に、その入力差分と出力差分の組が不能差分であると判定する。
【００２７】
図２は、図２３と同じ入力差分（１ｄ＊、２ｄ＊、０ｄ、０ｄ）と出力差分（１ｄ、０ｄ、０ｄ、０ｄ）を本発明の不能差分探索装置に入力した場合の差分の遷移を示している。図２のｄｉｆ５は、非ゼロの特定の差分であり、ｄｉｆ６は任意の差分であるため、非特許文献２の手法では、ＩＤ特性を検出することができない。
【００２８】
本発明によれば、ｄｉｆ５とｄｉｆ６が入出力差分となる関数ＳＢ（Ａ１）で、図４に示すような関数ＳＢのＳ−ｂｏｘの１対多の対応表を用いて不能差分であるか否かを判定するため、ＩＤ特性を検出することが可能になる。
【００２９】
［第１の実施形態］
続いて、本発明の第１の実施形態について図面を参照して詳細に説明する。図３は、本発明の第１の実施形態の構成を示すブロック図である。図３を参照すると、キーボードや各種メディアドライブ等の入力装置１０と、プログラム制御により動作する不能差分探索装置２１と、ディスプレイ装置や印刷装置等の出力装置３０とが示されている。
【００３０】
入力装置１０より、評価パラメータとして”１対多の対応表”、”入力差分”、”出力差分”、そして”ワード差分定義”の４つが入力される。
【００３１】
１対多の対応表は、ラウンド関数もしくはラウンド関数内の非線形関数における入力差分値と出力差分値との対応関係を表した表である。非線形関数としては、例えば共通鍵ブロック暗号でしばしば利用されるＳ−ｂｏｘがある。図４は、ある非線形関数における１対多の対応表の例であり、入力差分値毎に取り得るすべての出力差分値を対応付けたものとなっている。
【００３２】
入力差分には、非線形関数の入力側のＸ個のワード差分を指定する。また、出力差分には、非線形関数の出力側のＸ個のワード差分を指定する。入力差分と出力差分には、任意のワード差分を与えることができる。
【００３３】
図１９は、ワード差分定義の一例を示している。図１９の例では、差分値が０であれば０ｄ、非ゼロであればｎｄ、非ゼロであるが特定の差分値であればｎｄ＊、そして差分値の有無が不明であればｒｄとするという定義が与えられている。
【００３４】
不能差分探索装置２１は、入力差分値生成部２０１と、出力差分値生成部２０２と、１対多の対応表記憶部２０３と、判定部２０４と、関係式探索部２０５と、不能差分判定部２０６と、を備えている。これらはそれぞれ次のように動作する。
【００３５】
入力差分値生成部２０１は、入力差分において同一グループに属するワードには同じ入力差分値が設定されるように入力ワード差分から取り得る入力差分値を生成する。ここで、グループとは、Ｘ個のワード差分の中でワード差分として等しい要素の集合であり、後記するように関係式探索部２０５により決定される。
【００３６】
出力差分値生成部２０２は、出力差分において同一グループに属するワードには同じ出力差分値が設定されるように出力ワード差分から取り得る出力差分値を生成する。
【００３７】
１対多の対応表記憶部２０３は、図４に例示する入力差分値と出力差分値の１対多の対応表を記憶する。
【００３８】
関係式探索部２０５は、Ｘワードの入力差分とＸワードの出力差分それぞれについて、Ｘ個のワード差分の中でワード差分として等しいものの集合をＮ個のグループとしてグループ化できる場合に、各ワードにグループ番号Ｍを付与し、グループ数Ｎを計算する。
【００３９】
判定部２０４は、１対多の対応表記憶部２０３に記憶されている１対多の対応表を参照して、入力差分値生成部２０１と出力差分値生成部２０２で生成された入力差分値と出力差分値の組が有り得るか、有り得ないかを判定する。
【００４０】
不能差分判定部２０６は、入力差分値が生成される度に、出力ワード差分の同一グループに属するワードすべてに同じ出力差分値が設定された状態で、それらのワードのうち、一つでもあり得ないと判定された場合に、その入力差分値と出力差分値がｉｍｐｏｓｓｉｂｌｅ（あり得ない組み合わせ）であると判断する。そして、入力差分値毎に、ｉｍｐｏｓｓｉｂｌｅ（あり得ない組み合わせ）である出力ワード差分のグループの存在が一つ以上確認された場合に、入力差分とＸワードの出力差分がｉｍｐｏｓｓｉｂｌｅ（あり得ない組み合わせ）であると判断する。また、この入力差分値とＸワードの出力差分の判定において、一つ以上の入力差分値がｐｏｓｓｉｂｌｅ（あり得る組み合わせ）であると判断された場合に、不能差分判定部２０６は、Ｘワードの入力差分とＸワードの出力差分がｐｏｓｓｉｂｌｅ（あり得る組み合わせ）であると判断する。
【００４１】
なお、上記不能差分探索装置２１の入力差分値生成部２０１、出力差分値生成部２０２、判定部２０４、関係式探索部２０５及び不能差分判定部２０６は、不能差分探索装置を構成するコンピュータに実行させるプログラムにより実現することができる。
【００４２】
続いて、本実施形態の動作について、図５のフローチャートを参照して詳細に説明する。また、各ステップにおいて、適宜図１を参照して具体的な処理内容を説明する。
【００４３】
まず、関係式探索部２０５が、Ｘワードの入力差分の各ワードにグループ番号Ｍｉｎ［ｉ］（以下、ｉは、１≦ｉ≦Ｘを満たす整数である。）を、Ｘワードの出力差分の各ワードにグループ番号Ｍｏｕｔ［ｊ］（以下、ｊは、１≦ｉ≦Ｘを満たす整数である。）を付与する。グループ番号は、ワード差分が等しいものの集合ごとに１から順に設定する。次に、入力差分のグループ数Ｎｉｎと出力差分のグループ数Ｎｏｕｔを計算する（ステップＳ１）。
【００４４】
図１の例では、入力差分は（１ｄ，２ｄ，３ｄ，１ｄ）である。この場合、入力差分の１つ目の入力ワード差分１ｄにはグループ番号Ｍｉｎ［１］として１を、２つ目の入力ワード差分２ｄにはグループ番号Ｍｉｎ［２］として２を、３つ目の入力ワード差分３ｄにはグループ番号Ｍｉｎ［３］として３を、そして４つ目の入力ワード差分１ｄは１つ目の入力ワード差分と同じなので、グループ番号Ｍｉｎ［４］として１を付与する。
【００４５】
次に、入力ワード差分のグループとして１ｄのグループ、２ｄのグループ、３ｄのグループの３つがあるため、グループ数Ｎｉｎは３と算出される。同様に出力差分は（４ｄ，５ｄ，４ｄ，５ｄ）であるため、Ｍｏｕｔ［１］とＭｏｕｔ［３］には１を、Ｍｏｕｔ［２］とＭｏｕｔ［４］には２を付与する。グループ数Ｎｏｕｔは２と算出される。
【００４６】
次に、入力差分値生成部２０１が、関係式探索部２０５でグループ分けされた各入力ワード差分について、図１９に例示するワード差分定義を参照して入力ワード差分から取り得る入力差分値を生成する（ステップＳ２）。
【００４７】
ここで、図１の入力差分（１ｄ，２ｄ，３ｄ，１ｄ）の例を説明する。入力差分値生成部２０１は、図１９に例示するワード差分定義を参照して、入力ワード差分１ｄについて、差分値として取り得る０以外の差分値すべてを差分値１から差分値２＾ｓ−１（ｓはワードのビット幅）まで順に生成する。入力ワード差分２ｄに対しては、差分値として取り得る０以外の差分値すべてを差分値１から差分値２＾ｓ−１まで順に生成する。同様に入力ワード差分のすべてのグループについて取り得る入力差分値を生成する。グループ数が３の場合、入力差分の差分値の組み合わせの総数は、（２＾ｓ−１）＾３となる。
【００４８】
入力差分値生成部２０１は、上記ステップＳ２で生成した各ワードに対応する入力差分値から、Ｘワードの入力差分値を生成し、Ｄｉｎ［ｉ］に設定する（ステップＳ３）。
【００４９】
例えば、図１では入力差分の各ワードのグループ番号が（１，２，３，１）であり、グループ１に属するワード差分の入力差分値がａ１、グループ２に属するワード差分の入力差分値がｂ１、グループ３に属するワード差分の入力差分値がｃ１である。この場合、４ワードの入力差分値（ａ１，ｂ１，ｃ１，ａ１）を生成し、Ｄｉｎ［１］にａ１を、Ｄｉｎ［２］にｂ１を、Ｄｉｎ［３］にｃ１を、そしてＤｉｎ［４］にａ１を設定する。
【００５０】
不能差分判定部２０６は、１つ目の出力ワード差分を探索対象としてそのワード番号１をｊに設定し、出力差分の１つ目の出力ワード差分が属するグループ番号Ｍｏｕｔ［ｊ］をグループ番号の変数ｇに設定する（ステップＳ４）。
【００５１】
例えば、図１の場合、出力差分の１つ目の出力ワード差分である４ｄが探索対象になる。また、そのワード番号１をｊに設定し、出力差分の１つ目の出力ワード差分が属するグループ番号であるＭｏｕｔ［１］に設定されている１を変数ｇに設定する。
【００５２】
次に、出力差分値生成部２０２は、関係式探索部２０５でグループ分けされた各出力ワード差分について、図１９のワード差分定義を参照して出力ワード差分から取り得る出力差分値を生成する（ステップＳ５）。
【００５３】
ここで、図１の出力差分（４ｄ，５ｄ，４ｄ，５ｄ）の例を説明する。出力ワード差分４ｄに対しては、差分値として取り得る０以外の差分値すべてを差分値１から差分値２＾ｓ−１まで順に生成し、生成した差分値をＤｏｕｔとする。例えば、出力ワード差分４ｄから出力差分値ｄ１を生成し、Ｄｏｕｔに設定する。
【００５４】
次に、判定部２０４が、１対多の対応表記憶部２０３に記憶されている１対多の対応表を参照して、出力差分で探索対象となっているワードとワード位置が等しい入力差分値Ｄｉｎ［ｊ］から、ステップＳ５で生成した出力差分値Ｄｏｕｔを取り得るかを判定する（ステップＳ６、Ｓ７）。
【００５５】
例えば図１では、ステップＳ５で探索対象となった出力ワード差分４ｄとワード位置が等しい入力差分値Ｄｉｎ［１］＝ａ１から、ステップＳ５で生成した出力差分値Ｄｏｕｔ＝ｄ１を取り得るかを判定する。
【００５６】
判定部２０４で判定した結果、入力差分値から出力差分値を取り得ると判定した場合、入力差分値と出力差分値の組ごとに決まる判定結果ｒ１［ｎ１］（１≦ｎ１≦探索対象となっているグループｇに属するワード数）をｐｏｓｓｉｂｌｅとし（ステップＳ８）、入力差分値から出力差分値を取り得ないと判定した場合、判定結果ｒ１［ｎ１］をｉｍｐｏｓｓｉｂｌｅとする（ステップＳ９）。
【００５７】
続いて、判定部２０４は、不能差分判定部２０６からの指示に従い、グループｇと同じ出力ワード差分のグループ内の次の出力ワード差分を探索対象とし、そのワード番号をｊに設定する（ステップＳ１０）。
【００５８】
例えば、図１の出力差分の１つ目のワードの次の探索対象は、１つ目のワードのグループ番号１と等しいグループ番号である３つ目のワード（４ｄ）となり、そのワード番号３をｊに設定する。
【００５９】
判定部２０４は、不能差分判定部２０６からの指示に従い、上記ステップＳ６〜Ｓ１０を、出力差分の出力ワード差分が同じグループすべてについて繰り返す（ステップＳ１１）。なお、上記繰り返しの間、グループ番号が等しい出力ワードを探索対象としているため、判定部２０４に渡される出力差分値は、ステップＳ５で生成したＤｏｕｔである。
【００６０】
例えば、図１の出力ワード差分グループ１の２つ目のワードを探索対象とした場合、つまり出力差分の３つ目のワードを探索対象とした場合、入力差分値ｃ１から出力差分値Ｄｏｕｔが取り得るか否かの判定結果がｒ１［２］に設定される。
【００６１】
不能差分判定部２０６は、出力差分の出力ワード差分が同じグループすべてについて、判定結果ｒ１［ｎ１］がすべてｐｏｓｓｉｂｌｅである場合、入力差分値と出力ワード差分が同じグループに共通に設定した出力差分値の組ごとに決まる判定結果ｒ２［ｎ２］（１≦ｎ２≦出力ワード差分のグループから取り得る出力差分値の数の最大値）をｐｏｓｓｉｂｌｅとし（ステップＳ１３）、判定結果ｒ１［ｎ１］のうち１つでもｉｍｐｏｓｓｉｂｌｅの組がある場合、判定結果ｒ２［ｎ２］をｉｍｐｏｓｓｉｂｌｅとする（ステップＳ１４）。
【００６２】
図１の例を参照してより具体的に説明する。不能差分判定部２０６は、入力ワード差分１ｄより生成された入力差分値ａ１と、入力ワード差分３ｄより生成された入力差分値ｃ１に対し、出力ワード差分４ｄより生成された出力差分値ｄ１の判定結果ｒ１がともにｐｏｓｓｉｂｌｅである場合、不能差分判定部２０６は、判定結果ｒ２［１］をｐｏｓｓｉｂｌｅとし、入力差分値ａ１とｃ１のうち１つでもｄ１を取り得ない場合、判定結果ｒ２をｉｍｐｏｓｓｉｂｌｅとする。
【００６３】
判定部２０４および不能差分判定部２０６は、上記ステップＳ５〜Ｓ１４を、出力差分値生成部２０２により生成される出力差分値の全通りについて繰り返す（ステップＳ１５）。
【００６４】
例えば、図１では出力差分の１つ目と３つ目の出力ワード差分である４ｄから生成される出力差分値ｄ１，ｄ２，…のすべてについて繰り返すことで、判定結果ｒ２［１］、ｒ２［２］、・・・が設定される。
【００６５】
出力差分の出力ワード差分が同じグループ内の出力差分値すべてについて、判定結果ｒ２がすべてｉｍｐｏｓｓｉｂｌｅである場合、不能差分判定部２０６は、入力差分値と出力ワード差分のグループの組ごとに決まる判定結果ｒ３［ｎ３］（１≦ｎ３≦Ｎｏｕｔ）をｉｍｐｏｓｓｉｂｌｅとし（ステップＳ１７）、判定結果ｒ２［ｎ２］のうち１つでもｐｏｓｓｉｂｌｅの組がある場合、判定結果ｒ３［ｎ３］をｐｏｓｓｉｂｌｅとする（ステップＳ１８）。
【００６６】
例えば、入力差分の１つ目の入力ワード差分１ｄから生成された入力差分値ａ１と、入力差分の３つ目の入力ワード差分３ｄから生成された入力差分値ｃ１に対する、出力差分の１つ目と３つ目の出力ワード差分である４ｄから生成される出力差分値の判定結果ｒ２のすべてがｉｍｐｏｓｓｉｂｌｅの場合に判定結果ｒ３［ｇ］をｉｍｐｏｓｓｉｂｌｅとし、判定結果ｒ２のうち１つでもｐｏｓｓｉｂｌｅの組がある場合は判定結果ｒ３［ｇ］をｐｏｓｓｉｂｌｅとする。
【００６７】
次に、探索対象となっているグループのグループ番号ｇを１増やした出力ワード差分のグループの１つ目のワード差分を不能差分の探索対象としてそのワード位置をｊに設定し、グループ番号ｇを１インクリメントする（ステップＳ１９）。
【００６８】
図１の例では、グループ番号ｇを１から２へ更新し、探索対象となる出力ワード差分５ｄのワード番号２をｊに設定する。
【００６９】
判定部２０４および不能差分判定部２０６は、上記ステップＳ５〜Ｓ１９を、出力ワード差分のすべてのグループについて繰り返す（ステップＳ２０）。
【００７０】
図１の例では、出力ワード差分４ｄのグループと５ｄのグループについて繰り返すことになる。
【００７１】
出力ワード差分のすべてのグループについて、判定結果ｒ３［ｎ３］がすべてｐｏｓｓｉｂｌｅである場合、不能差分判定部２０６は、入力差分値と出力差分の組ごとに決まる判定結果ｒ４［ｎ４］（１≦ｎ４≦Ｘワードの入力差分値の総数）をｐｏｓｓｉｂｌｅとし（ステップＳ２２）、判定結果ｒ３［ｎ３］のうち１つでもｉｍｐｏｓｓｉｂｌｅの組がある場合、入力差分値と出力差分の組ごとに決まる判定結果ｒ４［ｎ４］をｉｍｐｏｓｓｉｂｌｅとする（ステップＳ２３）。
【００７２】
図１の例では、入力差分値ａ１、ｂ１、ｃ１、ａ１に対して、出力差分のワード差分４ｄと５ｄの判定結果ｒ３［１］とｒ３［２］がともにｐｏｓｓｉｂｌｅである場合、判定結果ｒ４［１］をｐｏｓｓｉｂｌｅとし、判定結果ｒ３［１］と判定結果ｒ３［２］のどちらか１つでもｉｍｐｏｓｓｉｂｌｅである場合は判定結果ｒ４［１］をｉｍｐｏｓｓｉｂｌｅとする。
【００７３】
判定部２０４および不能差分判定部２０６は、上記ステップＳ２〜Ｓ２３を、入力差分値の全通りについて繰り返す（ステップＳ２４）。
【００７４】
図１の例では、１ｄ、２ｄ、３ｄから生成される入力差分値の全通りについて繰り返す。
【００７５】
入力差分値生成部２０１により生成されるすべての入力差分値について、判定結果ｒ４がすべてｉｍｐｏｓｓｉｂｌｅである場合、入力差分と出力差分の組ごとに決まる不能差分判定結果ｒ５をｉｍｐｏｓｓｉｂｌｅとする（ステップＳ２６）。
【００７６】
図１の例では、入力差分（１ｄ，２ｄ，３ｄ，１ｄ）から生成されるすべての入力差分値について判定結果ｒ４［ｎ４］がすべてｉｍｐｏｓｓｉｂｌｅである場合に不能差分判定結果ｒ５をｉｍｐｏｓｓｉｂｌｅとする。
【００７７】
以上のように、本発明の第１の実施形態によれば、関係式探索部２０３を備え、不能差分判定部２０６が、入力差分値と出力差分値との組み合わせがあり得ないものであるか否かの判定を前記グループ単位で実施していくため、効率よくＩＤ特性を検出することができる。
【００７８】
［第２の実施形態］
続いて、本発明の第２の実施形態について図面を参照して詳細に説明する。図６は、本発明の第２の実施形態の構成を示すブロック図である。上記第１の実施形態との構成上の相違点は、非不能差分判定部２０７が追加されている点である。
【００７９】
非不能差分判定部２０７は、出力ワード差分のすべてが、入力差分値との組み合わせとしてあり得る出力差分値を持つことを確認できた場合に、その入力差分と出力差分の組が不能差分ではないと判定する。
【００８０】
続いて、本実施形態の動作を説明する。本実施形態の動作は、上記した第１の実施形態の動作とほぼ共通するので、以下、その相違点を中心に説明する。
【００８１】
図７は、本発明の第２の実施形態の不能差分の探索処理の流れを表したフローチャートである。第１の実施形態と同様、本発明の第２の実施形態では、不能差分判定結果ｒ５を判定する処理ステップＳ２５において、入力差分値生成部２０１により生成されるすべての入力差分値について、判定結果ｒ４［ｎ４］がすべてｉｍｐｏｓｓｉｂｌｅである場合、ステップＳ２６で入力差分と出力差分の組ごとに決まる不能差分判定結果ｒ５をｉｍｐｏｓｓｉｂｌｅとしている。本実施形態では、さらに、ステップＳ２５において、入力差分値生成部２０１により生成されるすべての入力差分値について、判定結果ｒ４［ｎ４］のうち１つでもｐｏｓｓｉｂｌｅの組がある場合、入力差分と出力差分の組ごとに決まる不能差分判定結果ｒ５をｐｏｓｓｉｂｌｅとする処理ＳＡ１を追加している。
【００８２】
以上のように、本発明の第２の実施形態によれば、非不能差分判定部２０７を用いて入力差分と出力差分との組み合わせがあり得るとの判定結果を得ることが可能になる。
【００８３】
［第３の実施形態］
続いて、本発明の第３の実施形態について図面を参照して詳細に説明する。図８は、本発明の第３の実施形態の構成を示すブロック図である。上記第２の実施形態との構成上の相違点は、入力側に、入力差分生成部４１、出力差分生成部４２、１対１の対応表記億部４３、ラウンド差分計算部４４および１対多対応位置決定部２０８が追加され、出力側に、結果出力部４５が追加されている点である。
【００８４】
本実施形態は、１対多対応位置決定部２０８を用いて１対多の対応表を適用する位置を決定し、その位置で１対多の対応表を用いて不能差分を判定することでＩＤ特性の有無を判定する点で上記第１、第２の実施形態と異なっている。以下、上記入力差分生成部４１〜結果出力部４５およびこれらを備えたことに伴う相違点について説明する。
【００８５】
本実施形態の入力装置１０には、評価パラメータとして”１対多の対応表”、”暗号部品毎の１対１対応表”、”暗号装置アルゴリズム”、そして”ワード差分定義”の４つが入力される。
【００８６】
暗号部品毎の１対１対応表は、評価対象の暗号のラウンド関数もしくは部品関数すべてにおける入力ワード差分と出力ワード差分の対応を示す表を入力する。例えば、図１７の関数Ｆが繰り返される暗号を評価対象とする場合、関数ＳＢと関数ＳＢ＾−１のＳ−ｂｏｘにおける１対１の対応表は、図２０に例示したとおりとなる。また、図９は、図１７の関数ＭＣ内の排他的論理和における１対１対応表の例であり、図１０は、関数ＭＣ内の乗算における１対１対応表の例である。
【００８７】
暗号装置アルゴリズムとして、各関数において、ワード差分を１対１の対応表を用いて計算するアルゴリズムを入力する。例えば、関数ＭＣに対しては上述の数１を入力する。
【００８８】
入力差分生成部４１と出力差分生成部４２は、上記のように入力装置１０から入力された内容に基づいて、評価対象とする暗号装置のＸワードの入力差分と出力差分をそれぞれ生成する。
【００８９】
１対１の対応表記憶部４３は、上記暗号部品毎の１対１対応表を記憶する。
【００９０】
ラウンド差分計算部４４は、上記暗号装置アルゴリズムに従って暗号部品毎の１対１対応表を参照し、順方向と逆方向に差分を計算し、１対多対応位置決定部２０８に出力する。
【００９１】
結果出力部４５は、不能差分と判定された入力差分と出力差分の組すべてについて、不能差分となったラウンド数が最も大きい組を選択して出力する。
【００９２】
１対多対応位置決定部２０８は、ラウンド差分計算部４４で計算された順方向のラウンド数ｍａｘαとラウンド差分α［ｉ］（０≦ｉ≦ｍａｘα）、１対多の対応表の対象関数である非線形関数の入力位置番号α＿ＮＬ［ｉ２］（１≦ｉ２≦非線形関数の入力位置のα［ｉ］の数）、逆方向のラウンド数ｍａｘβとラウンド差分β［ｊ］（０≦ｊ≦ｍａｘβ）、非線形関数の出力位置番号β＿ＮＬ［ｊ２］（１≦ｊ２≦非線形関数の出力位置のβ［ｊ］の数）を受け取り、１対多の対応表を適用する位置を決定し、関係式探索部２０５にＸワードの入力差分と出力差分を出力する。
【００９３】
１対多対応位置決定部２０８の入力について、図１１、図１２を用いて、具体的に説明する。
【００９４】
順方向のラウンド差分α［ｉ］は、入力差分生成部４１で生成された入力差分を暗号装置アルゴリズムに従って暗号部品毎の１対１対応表を参考にすべてのワード差分が不明なワード差分ｒｄになるまで計算したｉ番目の関数通過後のラウンド差分である。すべてのワード差分がｒｄとなった時の関数通過数がｍａｘαである。
【００９５】
図１１は、入力差分（１ｄ＊、２ｄ＊、０ｄ、０ｄ）を順方向に遷移させたラウンド差分の例を示している。ｍａｘα＝６、α［０］＝（１ｄ＊、２ｄ＊、０ｄ、０ｄ）、α［１］＝（１ｄ＊、０ｄ、０ｄ、２ｄ＊）、α［２］＝（１ｄ＊、１ｄ＊、２ｄ＊、２・２ｄ＊）、．．．、α［６］＝（ｒｄ、ｒｄ、ｒｄ、ｒｄ）である。非線形関数の入力位置はα［３］の位置だけであり、この場合、α＿ＮＬ［１］＝３と決定される。
【００９６】
逆方向のラウンド数ｍａｘβ、ラウンド差分β［ｊ］も同様である。図１２は、出力差分（１ｄ、０ｄ、０ｄ、０ｄ）を逆方向に遷移させたラウンド差分の例を示している。ｍａｘβ＝１３、β［０］＝β［１］＝β［２］＝β［３］＝β［４］＝（１ｄ、０ｄ、０ｄ、０ｄ）、β［５］＝（８・１ｄ、ｆ・１ｄ、０ｄ、０ｄ）、．．．、β［１３］＝（ｒｄ、ｒｄ、ｒｄ、ｒｄ）である。非線形関数の出力位置はβ［１０］とβ［６］とβ［２］の位置であり、この場合、β＿ＮＬ［１］＝１０、β＿ＮＬ［２］＝６、β＿ＮＬ［３］＝２と決定される。
【００９７】
続いて、本実施形態の動作を説明する。本実施形態の動作も、上記した第２の実施形態の動作とほぼ共通するので、以下、その相違点を中心に説明する。
【００９８】
図１３は、本発明の第３の実施形態の不能差分の探索処理の流れを表したフローチャートである。本発明の第３の実施形態の処理の流れは、上記本発明の第２の実施形態の処理の流れを表した図７のフローチャートと同様であるが、処理開始に当たって、１対多対応位置決定部２０８を用いて１対多の対応表を適用する位置を決定する処理（ステップＳＢ１）が追加されている。以下、ステップＳＢ１の手順を詳細に説明する。
【００９９】
図１４は、１対多対応位置決定部２０８における処理（ステップＳＢ１）の流れを表したフローチャートである。
【０１００】
図１４を参照すると、まず、１対多対応位置決定部２０８は、最初の非線形関数の入力位置α＿ＮＬ［１］を指すためのカウンタｉ２を１にする（ステップＳＢ１０１）。
【０１０１】
１対多対応位置決定部２０８は、ラウンド差分α［α＿ＮＬ［ｉ２］］を取り出す（ステップＳＢ１０２）。
【０１０２】
次に、１対多対応位置決定部２０８は、取り出したラウンド差分α［α＿ＮＬ［ｉ２］］のワード差分のうち１つ以上のワード差分が不明なワード差分ｒｄがあれば、次の非線形関数の入力位置を指すためのカウンタｉ２を１インクリメントする（ステップＳＢ１０３のＹｅｓ、ステップＳＢ１０４）。
【０１０３】
次の非線形関数の入力が存在すれば、１対多対応位置決定部２０８は、ステップＳＢ１０２からＳＢ１０４を繰り返す（ステップＳＢ１０５のＹｅｓ）。
【０１０４】
ステップＳＢ１０５で次の非線形関数の入力が存在しない場合は、１対多対応位置決定部２０８は、探索不可能として処理を終了する（ステップＳＢ１０５のＮｏ）。
【０１０５】
一方、ステップＳＢ１０３でワード差分すべてが不明なワード差分ｒｄ以外である場合、１対多対応位置決定部２０８は、関係式探索部２０５に渡す入力差分をα［α＿ＮＬ［ｉ２］］とする（ステップＳＢ１０６）。
【０１０６】
逆方向についても同様に、関係式探索部２０５に渡す出力差分を決定する（ステップＳＢ１０７〜ＳＢ１１２）。
【０１０７】
以上のように、本実施形態によれば、”暗号部品毎の１対１対応表”、”暗号装置アルゴリズム”から入出力差分を生成し、ＩＤ特性を探索し、不能差分となったラウンド数が最も大きい組を得ることが可能になる。
【０１０８】
［第４の実施形態］
続いて、本発明の第４の実施形態について図面を参照して詳細に説明する。図１５は、本発明の第４の実施形態の構成を示すブロック図である。上記第３の実施形態との構成上の相違点は、１対多の対応表生成部２０９が追加されている点である。
【０１０９】
１対多の対応表生成部２０９は、非線形関数を用いて、非線形関数の入力差分値から出力差分値の１対多の対応表を生成するものである。具体的には、入力差分値を全通り非線形関数に入力し、入力差分値ごとに取り得る出力差分値を生成して、図４に例示した１対多の対応表を生成する。
【０１１０】
続いて、本実施形態の動作を説明する。本実施形態の動作は、上記した第３の実施形態の動作とほぼ共通するので、以下、その相違点を中心に説明する。
【０１１１】
図１６は、本発明の第４の実施形態の不能差分の探索処理の流れを表したフローチャートである。本発明の第４の実施形態の処理の流れは、上記本発明の第３の実施形態の処理の流れを表した図１３のフローチャートと同様であるが、処理開始に当たって、１対多の対応表の作成処理（ステップＳＢ１）が追加されている。
【０１１２】
本実施形態によれば、１対多の対応表を予め用意しなくとも、ＩＤ特性を検出できるという効果がある。
【０１１３】
以上、本発明の実施形態を説明したが、本発明は、上記した実施形態に限定されるものではなく、本発明の基本的技術的思想を逸脱しない範囲で、更なる変形・置換・調整を加えることができる。例えば、上記した実施形態では、第１の実施形態から、第４の実施形態へと段階的に構成を追加して説明をしたが、各実施形態の特徴は、適宜組み合わせて実施することが可能である。
【符号の説明】
【０１１４】
１０ 入力装置
２１ 不能差分探索装置
２２ 不能差分探索装置
２３ 不能差分探索装置
２４ 不能差分探索装置
３０ 出力装置
４１ 入力差分生成部
４２ 出力差分生成部
４３ １対１の対応表記憶部
４４ ラウンド差分計算部
４５ 結果出力部
２０１ 入力差分値生成部
２０２ 出力差分値生成部
２０３ １対多の対応表記憶部
２０４ 判定部
２０５ 関係式探索部
２０６ 不能差分判定部
２０７ 非不能差分判定部
２０８ １対多対応位置決定部
２０９ １対多の対応表生成部
【技術分野】
【０００１】
本発明は、不能差分探索装置、不能差分探索方法及びプログラムに関し、特に、暗号アルゴリズムの安全性の評価に用いる不能差分特性を検出する不能差分探索装置、不能差分探索方法及びプログラムに関する。
【背景技術】
【０００２】
不能差分解析は、ブロック暗号の解析手法の一つである。不能差分解析は、成立し得ない差分特性（この特性を不能差分特性（Ｉｍｐｏｓｓｉｂｌｅ Ｄｉｆｆｅｒｅｎｔｉａｌｓ）と呼び、以降「ＩＤ特性」と記載する。）を使い、ブロック暗号の最初の数ラウンドや最後の数ラウンドの鍵を求めるものである（非特許文献１参照）。入力データをＸ個のサブブロックに分割して処理する構造を持つ共通鍵ブロック暗号では上記分割数Ｘが大きいほど、長いＩＤ特性があることが知られており、ＩＤ特性を見つけることは、上記不能差分解析にとって大変重要である。
【０００３】
非特許文献２のＩＤ特性探索手法は暗号化処理の順方向（入力は平文側、出力は暗号文側）と逆方向（入力は暗号文側、出力は平文側）にラウンド通過毎の差分（以降、ラウンド差分と呼ぶ）を計算する。その際、ブロック幅でのすべての入力差分値についてラウンド差分を計算することは、計算量的に実現が困難である。そこで、非特許文献２の手法では、差分をＸ個のワードに分割した上でワード毎の差分（以降、ワード差分と呼ぶ）をいくつかに分類し、ラウンド関数やラウンド関数内の部品関数の入力ワード差分と出力ワード差分を１対１で対応させる表を参照してラウンド差分を計算することで計算量を削減している（非特許文献２の表１、表２参照）。非特許文献２は、このようにして順方向と逆方向に差分を計算して得られた差分同士を比較し、ＩＤ特性を見つける方法を開示している。
【０００４】
また、特許文献１に、暗号仕様に従って差分集合をワード長単位に操作してＩＤ特性を検出する方法が開示されている。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２０００−２１４７７０号公報
【非特許文献】
【０００６】
【非特許文献１】Ｅ． Ｂｉｈａｍ， Ａ． Ｂｉｒｙｕｋｏｖ ａｎｄ Ａ． Ｓｈａｍｉｒ， “Ｃｒｙｐｔａｎａｌｙｓｉｓ ｏｆ Ｓｋｉｐｊａｃｋ Ｒｅｄｕｃｅｄ ｔｏ ３１ Ｒｏｕｎｄｓ Ｕｓｉｎｇ Ｉｍｐｏｓｓｉｂｌｅ Ｄｉｆｆｅｒｅｎｔｉａｌｓ”， ＥＵＲＯＣＲＹＰＴ’９９， ＬＮＣＳ １５９２， Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ， １９９９， ｐｐ．１２−２３．
【非特許文献２】中嶋、辻原、茂、川幡、角尾、 “不能差分特性探索手法の改良”、２００８年暗号と情報セキュリティシンポジウム（ＳＣＩＳ２００８）、２Ａ４−２、２００８
【発明の概要】
【発明が解決しようとする課題】
【０００７】
以上の特許文献１および非特許文献１、２の全開示内容は、本書に引用をもって繰り込み記載されているものとする。
以下の分析は、本発明の観点から与えられる。
【０００８】
図１７に示す関数Ｆが繰り返される暗号アルゴリズムを用いて、非特許文献２のＩＤ特性探索手法の具体例を説明する。図１７の関数Ｆは１ワードが４ビットである４ワードのデータを変換する関数とし、４ワードのデータは、２行２列の行列または、ワード数４のベクトルで表現する。関数ＳＢは４ビット幅の非線形変換部（Ｓ−ｂｏｘ）を用いて各ワードを変換する。関数ＳＲは、２行目のデータを１バイト左ローテイトシフトする、つまり２行目の２ワードを入れ替える。関数ＭＣは次の［数１］のように、２行２列の行列によってデータを変換する。ここで行列演算は既約多項式ｘ＾４＋ｘ＋１で規定されるＧＦ（２＾４）上の演算とする。また関数ＡＫはデータに４ワードの鍵データを排他的論理和する。
【０００９】
【数１】
【００１０】
図１８は、復号化で用いられる関数Ｆの逆関数を示している。関数ＳＢ＾−１、ＳＲ＾−１、ＭＣ＾−１、ＡＫ＾−１はそれぞれ関数ＳＢ、ＳＲ、ＭＣ、ＡＫの逆関数である。関数ＭＣ＾−１の行列演算は、［数２］となる。
【００１１】
【数２】
【００１２】
非特許文献２のＩＤ特性探索手法では、ワード差分を例えば図１９の０ｄ、ｎｄ、ｎｄ＊、ｒｄ（非特許文献２のＺｅｒｏ、Ｄｅｌｔａ、Ｆｉｘ（Ｆｉｘ２）、Ｒａｎｄｏｍに相当。）に分類し、関数Ｆおよび関数Ｆ＾−１中における各部品関数の入力ワード差分と出力ワード差分の１対１の対応関係を図２０のように定義している。図２０のｎ，ｍは互いに異なる数値とする。
【００１３】
このような関数を入出力差分が順方向または逆方向に進む毎に各関数の差分を計算し遷移させる。図２１は、入力差分が（１ｄ＊、０ｄ、０ｄ、０ｄ）、逆方向の入力である出力差分が（１ｄ、０ｄ、０ｄ、０ｄ）の場合の差分の遷移を表している。入力差分（１ｄ＊、０ｄ、０ｄ、０ｄ）は、関数ＳＲを通過して（１ｄ＊、０ｄ、０ｄ、０ｄ）となる。さらに（１ｄ＊、０ｄ、０ｄ、０ｄ）が、関数ＭＣを通過すると、（１ｄ＊、１ｄ＊、０ｄ、０ｄ）となる。他の関数も同様に差分を計算し遷移させる。
【００１４】
上記のようにして入力差分から計算されたｄｉｆ１と、出力差分から計算されたｄｉｆ２とを図２２の判定表を用いて比較する。図２２の例ではｎ≠ｍ、ｋ≠ｋ’とし、比較するワード差分の組み合わせとしてありえないものがｉｍｐｏｓｓｉｂｌｅ、ありえるものがｐｏｓｓｉｂｌｅと設定されている。例えば、ワード差分０ｄと１ｄの比較では、差分０と非ゼロの差分の比較なので、判定はｉｍｐｏｓｓｉｂｌｅとなる。図２１のｄｉｆ１とｄｉｆ２は、２ワード目と３ワード目でワード差分１ｄと０ｄが不能と判定され、入力差分が（１ｄ＊、０ｄ、０ｄ、０ｄ）であり出力差分が（１ｄ、０ｄ、０ｄ、０ｄ）というＩＤ特性が見つかる。
【００１５】
上記非特許文献２のＩＤ特性探索手法では、ラウンド関数またはラウンド関数内の非線形関数における入力差分と出力差分のワード差分を１対１で対応させる表（図２０参照）を参照することで、ラウンド関数または非線形関数通過後の差分を計算している。しかし、この方法では不能差分を判定する際の入力ワード差分と出力ワード差分の組み合わせが（非ゼロ，ゼロ）である場合と（ゼロ，非ゼロ）である場合しか不能差分として判定することができない。
【００１６】
しかしながら実際には、ラウンド関数またはラウンド関数内の非線形関数の入力と出力とを見たときに、入力ワード差分と出力ワード差分の組み合わせが（非ゼロ，非ゼロ）の場合でも不能差分が存在することがある。
【００１７】
例えば、図２３は、上記非特許文献２のＩＤ特性探索手法における入力差分が（１ｄ＊、２ｄ＊、０ｄ、０ｄ）、出力差分が（１ｄ、０ｄ、０ｄ、０ｄ）の場合の差分の遷移を表している。入力差分から計算されたｄｉｆ３と出力差分から計算されたｄｉｆ４とを図２２の判定表を用いて比較したとき、いずれの４ワードでもｐｏｓｓｉｂｌｅとなり、不能とは判定されない。
【００１８】
このように非特許文献２のＩＤ特性探索手法では入力ワード差分と出力ワード差分の組み合わせが（非ゼロの特定の差分，任意の差分）である場合と（任意の差分，非ゼロの特定の差分）である場合のＩＤ特性が検出できないという問題点がある。
【００１９】
本発明は、上記した事情に鑑みてなされたものであって、その目的とするところは、ラウンド関数またはラウンド関数内の非線形関数の入力ワード差分と出力ワード差分の組み合わせが非ゼロと非ゼロの場合についてもＩＤ特性を検出することができる不能差分探索装置、不能差分探索方法及びプログラムを提供することにある。
【課題を解決するための手段】
【００２０】
本発明の第１の視点によれば、共通鍵ブロック暗号を構成するラウンド関数内部で使用される非線形関数の入力差分値と出力差分値とに関する１対多の対応表を保持し、該１対多の対応表を用いて、２つ以上のワード（入力ワード差分）で構成される入力差分の入力ワード差分から取り得る入力差分値と、２つ以上のワード（出力ワード差分）で構成される出力差分の出力ワード差分から取り得る出力差分値と、の組み合わせがあり得るか否かを判定する判定部と、前記判定部を用いて、入力差分から生成した各入力差分値と、各入力差分値に対応する位置の出力差分値との組み合わせがあり得るか否かを判定してゆき、取りうる出力差分値のすべてが前記入力差分値との組み合わせとしてあり得ない出力ワード差分の存在を１つでも確認できた場合に、その入力差分と出力差分の組が不能差分であると判定する不能差分判定部と、を備える不能差分探索装置が提供される。
【００２１】
本発明の第２の視点によれば、共通鍵ブロック暗号を構成するラウンド関数内部で使用される非線形関数の入力差分値と出力差分値とに関する１対多の対応表を保持し、該１対多の対応表を用いて、２つ以上のワード（入力ワード差分）で構成される入力差分の入力ワード差分から取り得る入力差分値と、２つ以上のワード（出力ワード差分）で構成される出力差分の出力ワード差分から取り得る出力差分値と、の組み合わせがあり得るか否かを判定するステップを繰り返し、取りうる出力差分値のすべてが前記入力差分値との組み合わせとしてあり得ない出力ワード差分の存在を１つでも確認できた場合に、その入力差分と出力差分の組が不能差分であると判定する不能差分探索方法が提供される。なお、本方法は、不能差分探索装置という、特定の機械に結びつけられている。
【００２２】
本発明の第３の視点によれば、共通鍵ブロック暗号を構成するラウンド関数内部で使用される非線形関数の入力差分値と出力差分値とに関する１対多の対応表を保持し、該１対多の対応表を用いて、２つ以上のワード（入力ワード差分）で構成される入力差分の入力ワード差分から取り得る入力差分値と、２つ以上のワード（出力ワード差分）で構成される出力差分の出力ワード差分から取り得る出力差分値と、の組み合わせがあり得るか否かを判定する処理を繰り返し、取りうる出力差分値のすべてが前記入力差分値との組み合わせとしてあり得ない出力ワード差分の存在を１つでも確認できた場合に、その入力差分と出力差分の組が不能差分であると判定する処理をコンピュータに実行させるプログラムが提供される。なお、このプログラムは、コンピュータが読み取り可能な記憶媒体に記録することができる。
【発明の効果】
【００２３】
本発明によれば、ラウンド関数またはラウンド関数内の非線形関数の入力ワード差分と出力ワード差分の組み合わせが非ゼロと非ゼロの場合についてもＩＤ特性を検出することができる。
【図面の簡単な説明】
【００２４】
【図１】本発明の概要および本発明の第１の実施形態を説明するための図である。
【図２】本発明に係る不能差分探索装置による不能差分の探索例を示す図である。
【図３】本発明の第１の実施形態の構成を示すブロック図である。
【図４】１対多の対応表の一例を示す図である。
【図５】本発明の第１の実施形態の不能差分の探索処理の流れを表したフローチャートである。
【図６】本発明の第２の実施形態の構成を示すブロック図である。
【図７】本発明の第２の実施形態の不能差分の探索処理の流れを表したフローチャートである。
【図８】本発明の第３の実施形態の構成を示すブロック図である。
【図９】関数ＭＣ内の排他的論理和における入出力差分１対１対応表の例を示す図である。
【図１０】関数ＭＣ内の乗算における入出力差分１対１対応表の例を示す図である。
【図１１】本発明の第３の実施形態のラウンド差分部によるラウンド差分計算例（順方向）を示す図である。
【図１２】本発明の第３の実施形態のラウンド差分部によるラウンド差分計算例（逆方向）を示す図である。
【図１３】本発明の第３の実施形態の不能差分の探索処理の流れを表したフローチャートである。
【図１４】本発明の第３の実施形態の１対多対応位置決定部における処理の流れを表したフローチャートである。
【図１５】本発明の第４の実施形態の構成を示すブロック図である。
【図１６】本発明の第４の実施形態の不能差分の探索処理の流れを表したフローチャートである。
【図１７】評価対象の暗号アルゴリズムの関数Ｆを示す図である。
【図１８】評価対象の暗号アルゴリズムの復号に用いる逆関数Ｆ＾−１を示す図である。
【図１９】ワード差分定義の例を示す図である。
【図２０】図１７の関数ＳＢおよび図１８のＳＢ＾−１内のＳ−ｂｏｘでの入出力差分１対１対応表の例を示す図である。
【図２１】非特許文献２の手法による不能差分の探索例を示す図である。
【図２２】非特許文献２の手法における不能差分の判定に用いる表である。
【図２３】非特許文献２の手法では不能差分と判定できない例を示す図である。
【発明を実施するための形態】
【００２５】
はじめに、本発明の概要について説明する。本発明では、ラウンド関数内部のＳ−ｂｏｘのような非線形関数における入力差分値と出力差分値の１対多の対応関係を表した対応表を用いる（図４参照）。例えば、この１対多の対応表には、入力差分値５に対して出力差分値は１、３、５という奇数を取り得るといった１対多の対応関係が示される。
【００２６】
本発明に係る不能差分探索装置は、上記１対多の対応表を参照し、入力差分値と出力差分値の組が有り得るか、有り得ないかを判定する判定部を備える。本発明に係る不能差分探索装置は、上記判定部を用いて、入力ワード差分が取りうる入力差分値（例えば、図１のａ１、ａ２、・・・）に対し、出力差分が、一つでもあり得ない出力差分値を持つことを確認できた場合に、その入力差分と出力差分の組が不能差分であると判定する。
【００２７】
図２は、図２３と同じ入力差分（１ｄ＊、２ｄ＊、０ｄ、０ｄ）と出力差分（１ｄ、０ｄ、０ｄ、０ｄ）を本発明の不能差分探索装置に入力した場合の差分の遷移を示している。図２のｄｉｆ５は、非ゼロの特定の差分であり、ｄｉｆ６は任意の差分であるため、非特許文献２の手法では、ＩＤ特性を検出することができない。
【００２８】
本発明によれば、ｄｉｆ５とｄｉｆ６が入出力差分となる関数ＳＢ（Ａ１）で、図４に示すような関数ＳＢのＳ−ｂｏｘの１対多の対応表を用いて不能差分であるか否かを判定するため、ＩＤ特性を検出することが可能になる。
【００２９】
［第１の実施形態］
続いて、本発明の第１の実施形態について図面を参照して詳細に説明する。図３は、本発明の第１の実施形態の構成を示すブロック図である。図３を参照すると、キーボードや各種メディアドライブ等の入力装置１０と、プログラム制御により動作する不能差分探索装置２１と、ディスプレイ装置や印刷装置等の出力装置３０とが示されている。
【００３０】
入力装置１０より、評価パラメータとして”１対多の対応表”、”入力差分”、”出力差分”、そして”ワード差分定義”の４つが入力される。
【００３１】
１対多の対応表は、ラウンド関数もしくはラウンド関数内の非線形関数における入力差分値と出力差分値との対応関係を表した表である。非線形関数としては、例えば共通鍵ブロック暗号でしばしば利用されるＳ−ｂｏｘがある。図４は、ある非線形関数における１対多の対応表の例であり、入力差分値毎に取り得るすべての出力差分値を対応付けたものとなっている。
【００３２】
入力差分には、非線形関数の入力側のＸ個のワード差分を指定する。また、出力差分には、非線形関数の出力側のＸ個のワード差分を指定する。入力差分と出力差分には、任意のワード差分を与えることができる。
【００３３】
図１９は、ワード差分定義の一例を示している。図１９の例では、差分値が０であれば０ｄ、非ゼロであればｎｄ、非ゼロであるが特定の差分値であればｎｄ＊、そして差分値の有無が不明であればｒｄとするという定義が与えられている。
【００３４】
不能差分探索装置２１は、入力差分値生成部２０１と、出力差分値生成部２０２と、１対多の対応表記憶部２０３と、判定部２０４と、関係式探索部２０５と、不能差分判定部２０６と、を備えている。これらはそれぞれ次のように動作する。
【００３５】
入力差分値生成部２０１は、入力差分において同一グループに属するワードには同じ入力差分値が設定されるように入力ワード差分から取り得る入力差分値を生成する。ここで、グループとは、Ｘ個のワード差分の中でワード差分として等しい要素の集合であり、後記するように関係式探索部２０５により決定される。
【００３６】
出力差分値生成部２０２は、出力差分において同一グループに属するワードには同じ出力差分値が設定されるように出力ワード差分から取り得る出力差分値を生成する。
【００３７】
１対多の対応表記憶部２０３は、図４に例示する入力差分値と出力差分値の１対多の対応表を記憶する。
【００３８】
関係式探索部２０５は、Ｘワードの入力差分とＸワードの出力差分それぞれについて、Ｘ個のワード差分の中でワード差分として等しいものの集合をＮ個のグループとしてグループ化できる場合に、各ワードにグループ番号Ｍを付与し、グループ数Ｎを計算する。
【００３９】
判定部２０４は、１対多の対応表記憶部２０３に記憶されている１対多の対応表を参照して、入力差分値生成部２０１と出力差分値生成部２０２で生成された入力差分値と出力差分値の組が有り得るか、有り得ないかを判定する。
【００４０】
不能差分判定部２０６は、入力差分値が生成される度に、出力ワード差分の同一グループに属するワードすべてに同じ出力差分値が設定された状態で、それらのワードのうち、一つでもあり得ないと判定された場合に、その入力差分値と出力差分値がｉｍｐｏｓｓｉｂｌｅ（あり得ない組み合わせ）であると判断する。そして、入力差分値毎に、ｉｍｐｏｓｓｉｂｌｅ（あり得ない組み合わせ）である出力ワード差分のグループの存在が一つ以上確認された場合に、入力差分とＸワードの出力差分がｉｍｐｏｓｓｉｂｌｅ（あり得ない組み合わせ）であると判断する。また、この入力差分値とＸワードの出力差分の判定において、一つ以上の入力差分値がｐｏｓｓｉｂｌｅ（あり得る組み合わせ）であると判断された場合に、不能差分判定部２０６は、Ｘワードの入力差分とＸワードの出力差分がｐｏｓｓｉｂｌｅ（あり得る組み合わせ）であると判断する。
【００４１】
なお、上記不能差分探索装置２１の入力差分値生成部２０１、出力差分値生成部２０２、判定部２０４、関係式探索部２０５及び不能差分判定部２０６は、不能差分探索装置を構成するコンピュータに実行させるプログラムにより実現することができる。
【００４２】
続いて、本実施形態の動作について、図５のフローチャートを参照して詳細に説明する。また、各ステップにおいて、適宜図１を参照して具体的な処理内容を説明する。
【００４３】
まず、関係式探索部２０５が、Ｘワードの入力差分の各ワードにグループ番号Ｍｉｎ［ｉ］（以下、ｉは、１≦ｉ≦Ｘを満たす整数である。）を、Ｘワードの出力差分の各ワードにグループ番号Ｍｏｕｔ［ｊ］（以下、ｊは、１≦ｉ≦Ｘを満たす整数である。）を付与する。グループ番号は、ワード差分が等しいものの集合ごとに１から順に設定する。次に、入力差分のグループ数Ｎｉｎと出力差分のグループ数Ｎｏｕｔを計算する（ステップＳ１）。
【００４４】
図１の例では、入力差分は（１ｄ，２ｄ，３ｄ，１ｄ）である。この場合、入力差分の１つ目の入力ワード差分１ｄにはグループ番号Ｍｉｎ［１］として１を、２つ目の入力ワード差分２ｄにはグループ番号Ｍｉｎ［２］として２を、３つ目の入力ワード差分３ｄにはグループ番号Ｍｉｎ［３］として３を、そして４つ目の入力ワード差分１ｄは１つ目の入力ワード差分と同じなので、グループ番号Ｍｉｎ［４］として１を付与する。
【００４５】
次に、入力ワード差分のグループとして１ｄのグループ、２ｄのグループ、３ｄのグループの３つがあるため、グループ数Ｎｉｎは３と算出される。同様に出力差分は（４ｄ，５ｄ，４ｄ，５ｄ）であるため、Ｍｏｕｔ［１］とＭｏｕｔ［３］には１を、Ｍｏｕｔ［２］とＭｏｕｔ［４］には２を付与する。グループ数Ｎｏｕｔは２と算出される。
【００４６】
次に、入力差分値生成部２０１が、関係式探索部２０５でグループ分けされた各入力ワード差分について、図１９に例示するワード差分定義を参照して入力ワード差分から取り得る入力差分値を生成する（ステップＳ２）。
【００４７】
ここで、図１の入力差分（１ｄ，２ｄ，３ｄ，１ｄ）の例を説明する。入力差分値生成部２０１は、図１９に例示するワード差分定義を参照して、入力ワード差分１ｄについて、差分値として取り得る０以外の差分値すべてを差分値１から差分値２＾ｓ−１（ｓはワードのビット幅）まで順に生成する。入力ワード差分２ｄに対しては、差分値として取り得る０以外の差分値すべてを差分値１から差分値２＾ｓ−１まで順に生成する。同様に入力ワード差分のすべてのグループについて取り得る入力差分値を生成する。グループ数が３の場合、入力差分の差分値の組み合わせの総数は、（２＾ｓ−１）＾３となる。
【００４８】
入力差分値生成部２０１は、上記ステップＳ２で生成した各ワードに対応する入力差分値から、Ｘワードの入力差分値を生成し、Ｄｉｎ［ｉ］に設定する（ステップＳ３）。
【００４９】
例えば、図１では入力差分の各ワードのグループ番号が（１，２，３，１）であり、グループ１に属するワード差分の入力差分値がａ１、グループ２に属するワード差分の入力差分値がｂ１、グループ３に属するワード差分の入力差分値がｃ１である。この場合、４ワードの入力差分値（ａ１，ｂ１，ｃ１，ａ１）を生成し、Ｄｉｎ［１］にａ１を、Ｄｉｎ［２］にｂ１を、Ｄｉｎ［３］にｃ１を、そしてＤｉｎ［４］にａ１を設定する。
【００５０】
不能差分判定部２０６は、１つ目の出力ワード差分を探索対象としてそのワード番号１をｊに設定し、出力差分の１つ目の出力ワード差分が属するグループ番号Ｍｏｕｔ［ｊ］をグループ番号の変数ｇに設定する（ステップＳ４）。
【００５１】
例えば、図１の場合、出力差分の１つ目の出力ワード差分である４ｄが探索対象になる。また、そのワード番号１をｊに設定し、出力差分の１つ目の出力ワード差分が属するグループ番号であるＭｏｕｔ［１］に設定されている１を変数ｇに設定する。
【００５２】
次に、出力差分値生成部２０２は、関係式探索部２０５でグループ分けされた各出力ワード差分について、図１９のワード差分定義を参照して出力ワード差分から取り得る出力差分値を生成する（ステップＳ５）。
【００５３】
ここで、図１の出力差分（４ｄ，５ｄ，４ｄ，５ｄ）の例を説明する。出力ワード差分４ｄに対しては、差分値として取り得る０以外の差分値すべてを差分値１から差分値２＾ｓ−１まで順に生成し、生成した差分値をＤｏｕｔとする。例えば、出力ワード差分４ｄから出力差分値ｄ１を生成し、Ｄｏｕｔに設定する。
【００５４】
次に、判定部２０４が、１対多の対応表記憶部２０３に記憶されている１対多の対応表を参照して、出力差分で探索対象となっているワードとワード位置が等しい入力差分値Ｄｉｎ［ｊ］から、ステップＳ５で生成した出力差分値Ｄｏｕｔを取り得るかを判定する（ステップＳ６、Ｓ７）。
【００５５】
例えば図１では、ステップＳ５で探索対象となった出力ワード差分４ｄとワード位置が等しい入力差分値Ｄｉｎ［１］＝ａ１から、ステップＳ５で生成した出力差分値Ｄｏｕｔ＝ｄ１を取り得るかを判定する。
【００５６】
判定部２０４で判定した結果、入力差分値から出力差分値を取り得ると判定した場合、入力差分値と出力差分値の組ごとに決まる判定結果ｒ１［ｎ１］（１≦ｎ１≦探索対象となっているグループｇに属するワード数）をｐｏｓｓｉｂｌｅとし（ステップＳ８）、入力差分値から出力差分値を取り得ないと判定した場合、判定結果ｒ１［ｎ１］をｉｍｐｏｓｓｉｂｌｅとする（ステップＳ９）。
【００５７】
続いて、判定部２０４は、不能差分判定部２０６からの指示に従い、グループｇと同じ出力ワード差分のグループ内の次の出力ワード差分を探索対象とし、そのワード番号をｊに設定する（ステップＳ１０）。
【００５８】
例えば、図１の出力差分の１つ目のワードの次の探索対象は、１つ目のワードのグループ番号１と等しいグループ番号である３つ目のワード（４ｄ）となり、そのワード番号３をｊに設定する。
【００５９】
判定部２０４は、不能差分判定部２０６からの指示に従い、上記ステップＳ６〜Ｓ１０を、出力差分の出力ワード差分が同じグループすべてについて繰り返す（ステップＳ１１）。なお、上記繰り返しの間、グループ番号が等しい出力ワードを探索対象としているため、判定部２０４に渡される出力差分値は、ステップＳ５で生成したＤｏｕｔである。
【００６０】
例えば、図１の出力ワード差分グループ１の２つ目のワードを探索対象とした場合、つまり出力差分の３つ目のワードを探索対象とした場合、入力差分値ｃ１から出力差分値Ｄｏｕｔが取り得るか否かの判定結果がｒ１［２］に設定される。
【００６１】
不能差分判定部２０６は、出力差分の出力ワード差分が同じグループすべてについて、判定結果ｒ１［ｎ１］がすべてｐｏｓｓｉｂｌｅである場合、入力差分値と出力ワード差分が同じグループに共通に設定した出力差分値の組ごとに決まる判定結果ｒ２［ｎ２］（１≦ｎ２≦出力ワード差分のグループから取り得る出力差分値の数の最大値）をｐｏｓｓｉｂｌｅとし（ステップＳ１３）、判定結果ｒ１［ｎ１］のうち１つでもｉｍｐｏｓｓｉｂｌｅの組がある場合、判定結果ｒ２［ｎ２］をｉｍｐｏｓｓｉｂｌｅとする（ステップＳ１４）。
【００６２】
図１の例を参照してより具体的に説明する。不能差分判定部２０６は、入力ワード差分１ｄより生成された入力差分値ａ１と、入力ワード差分３ｄより生成された入力差分値ｃ１に対し、出力ワード差分４ｄより生成された出力差分値ｄ１の判定結果ｒ１がともにｐｏｓｓｉｂｌｅである場合、不能差分判定部２０６は、判定結果ｒ２［１］をｐｏｓｓｉｂｌｅとし、入力差分値ａ１とｃ１のうち１つでもｄ１を取り得ない場合、判定結果ｒ２をｉｍｐｏｓｓｉｂｌｅとする。
【００６３】
判定部２０４および不能差分判定部２０６は、上記ステップＳ５〜Ｓ１４を、出力差分値生成部２０２により生成される出力差分値の全通りについて繰り返す（ステップＳ１５）。
【００６４】
例えば、図１では出力差分の１つ目と３つ目の出力ワード差分である４ｄから生成される出力差分値ｄ１，ｄ２，…のすべてについて繰り返すことで、判定結果ｒ２［１］、ｒ２［２］、・・・が設定される。
【００６５】
出力差分の出力ワード差分が同じグループ内の出力差分値すべてについて、判定結果ｒ２がすべてｉｍｐｏｓｓｉｂｌｅである場合、不能差分判定部２０６は、入力差分値と出力ワード差分のグループの組ごとに決まる判定結果ｒ３［ｎ３］（１≦ｎ３≦Ｎｏｕｔ）をｉｍｐｏｓｓｉｂｌｅとし（ステップＳ１７）、判定結果ｒ２［ｎ２］のうち１つでもｐｏｓｓｉｂｌｅの組がある場合、判定結果ｒ３［ｎ３］をｐｏｓｓｉｂｌｅとする（ステップＳ１８）。
【００６６】
例えば、入力差分の１つ目の入力ワード差分１ｄから生成された入力差分値ａ１と、入力差分の３つ目の入力ワード差分３ｄから生成された入力差分値ｃ１に対する、出力差分の１つ目と３つ目の出力ワード差分である４ｄから生成される出力差分値の判定結果ｒ２のすべてがｉｍｐｏｓｓｉｂｌｅの場合に判定結果ｒ３［ｇ］をｉｍｐｏｓｓｉｂｌｅとし、判定結果ｒ２のうち１つでもｐｏｓｓｉｂｌｅの組がある場合は判定結果ｒ３［ｇ］をｐｏｓｓｉｂｌｅとする。
【００６７】
次に、探索対象となっているグループのグループ番号ｇを１増やした出力ワード差分のグループの１つ目のワード差分を不能差分の探索対象としてそのワード位置をｊに設定し、グループ番号ｇを１インクリメントする（ステップＳ１９）。
【００６８】
図１の例では、グループ番号ｇを１から２へ更新し、探索対象となる出力ワード差分５ｄのワード番号２をｊに設定する。
【００６９】
判定部２０４および不能差分判定部２０６は、上記ステップＳ５〜Ｓ１９を、出力ワード差分のすべてのグループについて繰り返す（ステップＳ２０）。
【００７０】
図１の例では、出力ワード差分４ｄのグループと５ｄのグループについて繰り返すことになる。
【００７１】
出力ワード差分のすべてのグループについて、判定結果ｒ３［ｎ３］がすべてｐｏｓｓｉｂｌｅである場合、不能差分判定部２０６は、入力差分値と出力差分の組ごとに決まる判定結果ｒ４［ｎ４］（１≦ｎ４≦Ｘワードの入力差分値の総数）をｐｏｓｓｉｂｌｅとし（ステップＳ２２）、判定結果ｒ３［ｎ３］のうち１つでもｉｍｐｏｓｓｉｂｌｅの組がある場合、入力差分値と出力差分の組ごとに決まる判定結果ｒ４［ｎ４］をｉｍｐｏｓｓｉｂｌｅとする（ステップＳ２３）。
【００７２】
図１の例では、入力差分値ａ１、ｂ１、ｃ１、ａ１に対して、出力差分のワード差分４ｄと５ｄの判定結果ｒ３［１］とｒ３［２］がともにｐｏｓｓｉｂｌｅである場合、判定結果ｒ４［１］をｐｏｓｓｉｂｌｅとし、判定結果ｒ３［１］と判定結果ｒ３［２］のどちらか１つでもｉｍｐｏｓｓｉｂｌｅである場合は判定結果ｒ４［１］をｉｍｐｏｓｓｉｂｌｅとする。
【００７３】
判定部２０４および不能差分判定部２０６は、上記ステップＳ２〜Ｓ２３を、入力差分値の全通りについて繰り返す（ステップＳ２４）。
【００７４】
図１の例では、１ｄ、２ｄ、３ｄから生成される入力差分値の全通りについて繰り返す。
【００７５】
入力差分値生成部２０１により生成されるすべての入力差分値について、判定結果ｒ４がすべてｉｍｐｏｓｓｉｂｌｅである場合、入力差分と出力差分の組ごとに決まる不能差分判定結果ｒ５をｉｍｐｏｓｓｉｂｌｅとする（ステップＳ２６）。
【００７６】
図１の例では、入力差分（１ｄ，２ｄ，３ｄ，１ｄ）から生成されるすべての入力差分値について判定結果ｒ４［ｎ４］がすべてｉｍｐｏｓｓｉｂｌｅである場合に不能差分判定結果ｒ５をｉｍｐｏｓｓｉｂｌｅとする。
【００７７】
以上のように、本発明の第１の実施形態によれば、関係式探索部２０３を備え、不能差分判定部２０６が、入力差分値と出力差分値との組み合わせがあり得ないものであるか否かの判定を前記グループ単位で実施していくため、効率よくＩＤ特性を検出することができる。
【００７８】
［第２の実施形態］
続いて、本発明の第２の実施形態について図面を参照して詳細に説明する。図６は、本発明の第２の実施形態の構成を示すブロック図である。上記第１の実施形態との構成上の相違点は、非不能差分判定部２０７が追加されている点である。
【００７９】
非不能差分判定部２０７は、出力ワード差分のすべてが、入力差分値との組み合わせとしてあり得る出力差分値を持つことを確認できた場合に、その入力差分と出力差分の組が不能差分ではないと判定する。
【００８０】
続いて、本実施形態の動作を説明する。本実施形態の動作は、上記した第１の実施形態の動作とほぼ共通するので、以下、その相違点を中心に説明する。
【００８１】
図７は、本発明の第２の実施形態の不能差分の探索処理の流れを表したフローチャートである。第１の実施形態と同様、本発明の第２の実施形態では、不能差分判定結果ｒ５を判定する処理ステップＳ２５において、入力差分値生成部２０１により生成されるすべての入力差分値について、判定結果ｒ４［ｎ４］がすべてｉｍｐｏｓｓｉｂｌｅである場合、ステップＳ２６で入力差分と出力差分の組ごとに決まる不能差分判定結果ｒ５をｉｍｐｏｓｓｉｂｌｅとしている。本実施形態では、さらに、ステップＳ２５において、入力差分値生成部２０１により生成されるすべての入力差分値について、判定結果ｒ４［ｎ４］のうち１つでもｐｏｓｓｉｂｌｅの組がある場合、入力差分と出力差分の組ごとに決まる不能差分判定結果ｒ５をｐｏｓｓｉｂｌｅとする処理ＳＡ１を追加している。
【００８２】
以上のように、本発明の第２の実施形態によれば、非不能差分判定部２０７を用いて入力差分と出力差分との組み合わせがあり得るとの判定結果を得ることが可能になる。
【００８３】
［第３の実施形態］
続いて、本発明の第３の実施形態について図面を参照して詳細に説明する。図８は、本発明の第３の実施形態の構成を示すブロック図である。上記第２の実施形態との構成上の相違点は、入力側に、入力差分生成部４１、出力差分生成部４２、１対１の対応表記億部４３、ラウンド差分計算部４４および１対多対応位置決定部２０８が追加され、出力側に、結果出力部４５が追加されている点である。
【００８４】
本実施形態は、１対多対応位置決定部２０８を用いて１対多の対応表を適用する位置を決定し、その位置で１対多の対応表を用いて不能差分を判定することでＩＤ特性の有無を判定する点で上記第１、第２の実施形態と異なっている。以下、上記入力差分生成部４１〜結果出力部４５およびこれらを備えたことに伴う相違点について説明する。
【００８５】
本実施形態の入力装置１０には、評価パラメータとして”１対多の対応表”、”暗号部品毎の１対１対応表”、”暗号装置アルゴリズム”、そして”ワード差分定義”の４つが入力される。
【００８６】
暗号部品毎の１対１対応表は、評価対象の暗号のラウンド関数もしくは部品関数すべてにおける入力ワード差分と出力ワード差分の対応を示す表を入力する。例えば、図１７の関数Ｆが繰り返される暗号を評価対象とする場合、関数ＳＢと関数ＳＢ＾−１のＳ−ｂｏｘにおける１対１の対応表は、図２０に例示したとおりとなる。また、図９は、図１７の関数ＭＣ内の排他的論理和における１対１対応表の例であり、図１０は、関数ＭＣ内の乗算における１対１対応表の例である。
【００８７】
暗号装置アルゴリズムとして、各関数において、ワード差分を１対１の対応表を用いて計算するアルゴリズムを入力する。例えば、関数ＭＣに対しては上述の数１を入力する。
【００８８】
入力差分生成部４１と出力差分生成部４２は、上記のように入力装置１０から入力された内容に基づいて、評価対象とする暗号装置のＸワードの入力差分と出力差分をそれぞれ生成する。
【００８９】
１対１の対応表記憶部４３は、上記暗号部品毎の１対１対応表を記憶する。
【００９０】
ラウンド差分計算部４４は、上記暗号装置アルゴリズムに従って暗号部品毎の１対１対応表を参照し、順方向と逆方向に差分を計算し、１対多対応位置決定部２０８に出力する。
【００９１】
結果出力部４５は、不能差分と判定された入力差分と出力差分の組すべてについて、不能差分となったラウンド数が最も大きい組を選択して出力する。
【００９２】
１対多対応位置決定部２０８は、ラウンド差分計算部４４で計算された順方向のラウンド数ｍａｘαとラウンド差分α［ｉ］（０≦ｉ≦ｍａｘα）、１対多の対応表の対象関数である非線形関数の入力位置番号α＿ＮＬ［ｉ２］（１≦ｉ２≦非線形関数の入力位置のα［ｉ］の数）、逆方向のラウンド数ｍａｘβとラウンド差分β［ｊ］（０≦ｊ≦ｍａｘβ）、非線形関数の出力位置番号β＿ＮＬ［ｊ２］（１≦ｊ２≦非線形関数の出力位置のβ［ｊ］の数）を受け取り、１対多の対応表を適用する位置を決定し、関係式探索部２０５にＸワードの入力差分と出力差分を出力する。
【００９３】
１対多対応位置決定部２０８の入力について、図１１、図１２を用いて、具体的に説明する。
【００９４】
順方向のラウンド差分α［ｉ］は、入力差分生成部４１で生成された入力差分を暗号装置アルゴリズムに従って暗号部品毎の１対１対応表を参考にすべてのワード差分が不明なワード差分ｒｄになるまで計算したｉ番目の関数通過後のラウンド差分である。すべてのワード差分がｒｄとなった時の関数通過数がｍａｘαである。
【００９５】
図１１は、入力差分（１ｄ＊、２ｄ＊、０ｄ、０ｄ）を順方向に遷移させたラウンド差分の例を示している。ｍａｘα＝６、α［０］＝（１ｄ＊、２ｄ＊、０ｄ、０ｄ）、α［１］＝（１ｄ＊、０ｄ、０ｄ、２ｄ＊）、α［２］＝（１ｄ＊、１ｄ＊、２ｄ＊、２・２ｄ＊）、．．．、α［６］＝（ｒｄ、ｒｄ、ｒｄ、ｒｄ）である。非線形関数の入力位置はα［３］の位置だけであり、この場合、α＿ＮＬ［１］＝３と決定される。
【００９６】
逆方向のラウンド数ｍａｘβ、ラウンド差分β［ｊ］も同様である。図１２は、出力差分（１ｄ、０ｄ、０ｄ、０ｄ）を逆方向に遷移させたラウンド差分の例を示している。ｍａｘβ＝１３、β［０］＝β［１］＝β［２］＝β［３］＝β［４］＝（１ｄ、０ｄ、０ｄ、０ｄ）、β［５］＝（８・１ｄ、ｆ・１ｄ、０ｄ、０ｄ）、．．．、β［１３］＝（ｒｄ、ｒｄ、ｒｄ、ｒｄ）である。非線形関数の出力位置はβ［１０］とβ［６］とβ［２］の位置であり、この場合、β＿ＮＬ［１］＝１０、β＿ＮＬ［２］＝６、β＿ＮＬ［３］＝２と決定される。
【００９７】
続いて、本実施形態の動作を説明する。本実施形態の動作も、上記した第２の実施形態の動作とほぼ共通するので、以下、その相違点を中心に説明する。
【００９８】
図１３は、本発明の第３の実施形態の不能差分の探索処理の流れを表したフローチャートである。本発明の第３の実施形態の処理の流れは、上記本発明の第２の実施形態の処理の流れを表した図７のフローチャートと同様であるが、処理開始に当たって、１対多対応位置決定部２０８を用いて１対多の対応表を適用する位置を決定する処理（ステップＳＢ１）が追加されている。以下、ステップＳＢ１の手順を詳細に説明する。
【００９９】
図１４は、１対多対応位置決定部２０８における処理（ステップＳＢ１）の流れを表したフローチャートである。
【０１００】
図１４を参照すると、まず、１対多対応位置決定部２０８は、最初の非線形関数の入力位置α＿ＮＬ［１］を指すためのカウンタｉ２を１にする（ステップＳＢ１０１）。
【０１０１】
１対多対応位置決定部２０８は、ラウンド差分α［α＿ＮＬ［ｉ２］］を取り出す（ステップＳＢ１０２）。
【０１０２】
次に、１対多対応位置決定部２０８は、取り出したラウンド差分α［α＿ＮＬ［ｉ２］］のワード差分のうち１つ以上のワード差分が不明なワード差分ｒｄがあれば、次の非線形関数の入力位置を指すためのカウンタｉ２を１インクリメントする（ステップＳＢ１０３のＹｅｓ、ステップＳＢ１０４）。
【０１０３】
次の非線形関数の入力が存在すれば、１対多対応位置決定部２０８は、ステップＳＢ１０２からＳＢ１０４を繰り返す（ステップＳＢ１０５のＹｅｓ）。
【０１０４】
ステップＳＢ１０５で次の非線形関数の入力が存在しない場合は、１対多対応位置決定部２０８は、探索不可能として処理を終了する（ステップＳＢ１０５のＮｏ）。
【０１０５】
一方、ステップＳＢ１０３でワード差分すべてが不明なワード差分ｒｄ以外である場合、１対多対応位置決定部２０８は、関係式探索部２０５に渡す入力差分をα［α＿ＮＬ［ｉ２］］とする（ステップＳＢ１０６）。
【０１０６】
逆方向についても同様に、関係式探索部２０５に渡す出力差分を決定する（ステップＳＢ１０７〜ＳＢ１１２）。
【０１０７】
以上のように、本実施形態によれば、”暗号部品毎の１対１対応表”、”暗号装置アルゴリズム”から入出力差分を生成し、ＩＤ特性を探索し、不能差分となったラウンド数が最も大きい組を得ることが可能になる。
【０１０８】
［第４の実施形態］
続いて、本発明の第４の実施形態について図面を参照して詳細に説明する。図１５は、本発明の第４の実施形態の構成を示すブロック図である。上記第３の実施形態との構成上の相違点は、１対多の対応表生成部２０９が追加されている点である。
【０１０９】
１対多の対応表生成部２０９は、非線形関数を用いて、非線形関数の入力差分値から出力差分値の１対多の対応表を生成するものである。具体的には、入力差分値を全通り非線形関数に入力し、入力差分値ごとに取り得る出力差分値を生成して、図４に例示した１対多の対応表を生成する。
【０１１０】
続いて、本実施形態の動作を説明する。本実施形態の動作は、上記した第３の実施形態の動作とほぼ共通するので、以下、その相違点を中心に説明する。
【０１１１】
図１６は、本発明の第４の実施形態の不能差分の探索処理の流れを表したフローチャートである。本発明の第４の実施形態の処理の流れは、上記本発明の第３の実施形態の処理の流れを表した図１３のフローチャートと同様であるが、処理開始に当たって、１対多の対応表の作成処理（ステップＳＢ１）が追加されている。
【０１１２】
本実施形態によれば、１対多の対応表を予め用意しなくとも、ＩＤ特性を検出できるという効果がある。
【０１１３】
以上、本発明の実施形態を説明したが、本発明は、上記した実施形態に限定されるものではなく、本発明の基本的技術的思想を逸脱しない範囲で、更なる変形・置換・調整を加えることができる。例えば、上記した実施形態では、第１の実施形態から、第４の実施形態へと段階的に構成を追加して説明をしたが、各実施形態の特徴は、適宜組み合わせて実施することが可能である。
【符号の説明】
【０１１４】
１０ 入力装置
２１ 不能差分探索装置
２２ 不能差分探索装置
２３ 不能差分探索装置
２４ 不能差分探索装置
３０ 出力装置
４１ 入力差分生成部
４２ 出力差分生成部
４３ １対１の対応表記憶部
４４ ラウンド差分計算部
４５ 結果出力部
２０１ 入力差分値生成部
２０２ 出力差分値生成部
２０３ １対多の対応表記憶部
２０４ 判定部
２０５ 関係式探索部
２０６ 不能差分判定部
２０７ 非不能差分判定部
２０８ １対多対応位置決定部
２０９ １対多の対応表生成部
【特許請求の範囲】
【請求項１】
共通鍵ブロック暗号を構成するラウンド関数内部で使用される非線形関数の入力差分値と出力差分値とに関する１対多の対応表を保持し、該１対多の対応表を用いて、２つ以上のワード（入力ワード差分）で構成される入力差分の入力ワード差分から取り得る入力差分値と、２つ以上のワード（出力ワード差分）で構成される出力差分の出力ワード差分から取り得る出力差分値と、の組み合わせがあり得るか否かを判定する判定部と、
前記判定部を用いて、入力差分から生成した各入力差分値と、該各入力差分値に対応する出力ワード差分から生成した出力差分値との組み合わせがあり得るか否かを判定してゆき、取りうる出力差分値のすべてが前記入力差分値との組み合わせとしてあり得ない出力ワード差分の存在を１つでも確認できた場合に、その入力差分と出力差分の組が不能差分であると判定する不能差分判定部と、
を備える不能差分探索装置。
【請求項２】
さらに、
前記入力差分および出力差分についてそれぞれワード差分が一致する要素の集合が１つのグループとなるように、前記入力ワード差分と出力ワード差分とをそれぞれグループ化する関係式探索部と、
前記関係式探索部で分類された入力ワード差分の各グループにおいて、入力ワード差分から取り得るすべての入力差分値を生成する入力差分値生成部と、
前記関係式探索部で分類された出力ワード差分の各グループにおいて、出力ワード差分から取り得るすべての出力差分値を生成する出力差分値生成部と、を備え、
前記入力差分から生成した各入力差分値に対して、出力差分値があり得ないものであるか否かの判定を前記グループ単位で実施していく請求項１の不能差分探索装置。
【請求項３】
不能差分探索対象の暗号アルゴリズムの暗号部品毎に記憶した入出力差分の１対１対応表を参照し、入力差分および出力差分について順方向および逆方向の差分を算出するラウンド差分計算部と、
入力差分と出力差分が不明な状態になるまで、前記ラウンド差分計算部を動作させて前記１対多の対応表を適用する位置を決定し、前記関係式探索部に当該位置の入力差分および出力差分を出力する１対多対応位置決定部と、
を備える請求項２の不能差分探索装置。
【請求項４】
さらに、
前記判定部を用いて、入力差分から生成した各入力差分値と、各入力差分値に対応する位置の出力差分値との組み合わせがあり得るか否かを判定してゆき、出力ワード差分のすべてが、前記入力差分値との組み合わせとしてあり得る出力差分値を持つことを確認できた場合に、その入力差分と出力差分の組が不能差分ではないと判定する非不能差分判定部を備える請求項１から３いずれか一の不能差分探索装置。
【請求項５】
さらに、
不能差分探索対象の暗号アルゴリズムの非線形関数を用いて、１対多の対応表を生成する１対多の対応表生成部を備える請求項１から４いずれか一の不能差分探索装置。
【請求項６】
共通鍵ブロック暗号を構成するラウンド関数内部で使用される非線形関数の入力差分値と出力差分値とに関する１対多の対応表を保持し、該１対多の対応表を用いて、２つ以上のワード（入力ワード差分）で構成される入力差分の入力ワード差分から取り得る入力差分値と、２つ以上のワード（出力ワード差分）で構成される出力差分の出力ワード差分から取り得る出力差分値と、の組み合わせがあり得るか否かを判定するステップを繰り返し、
取りうる出力差分値のすべてが前記入力差分値との組み合わせとしてあり得ない出力ワード差分の存在を１つでも確認できた場合に、その入力差分と出力差分の組が不能差分であると判定する不能差分探索方法。
【請求項７】
共通鍵ブロック暗号を構成するラウンド関数内部で使用される非線形関数の入力差分値と出力差分値とに関する１対多の対応表を保持し、該１対多の対応表を用いて、２つ以上のワード（入力ワード差分）で構成される入力差分の入力ワード差分から取り得る入力差分値と、２つ以上のワード（出力ワード差分）で構成される出力差分の出力ワード差分から取り得る出力差分値と、の組み合わせがあり得るか否かを判定する処理を繰り返し、取りうる出力差分値のすべてが前記入力差分値との組み合わせとしてあり得ない出力ワード差分の存在を１つでも確認できた場合に、その入力差分と出力差分の組が不能差分であると判定する処理をコンピュータに実行させるプログラム。
【請求項１】
共通鍵ブロック暗号を構成するラウンド関数内部で使用される非線形関数の入力差分値と出力差分値とに関する１対多の対応表を保持し、該１対多の対応表を用いて、２つ以上のワード（入力ワード差分）で構成される入力差分の入力ワード差分から取り得る入力差分値と、２つ以上のワード（出力ワード差分）で構成される出力差分の出力ワード差分から取り得る出力差分値と、の組み合わせがあり得るか否かを判定する判定部と、
前記判定部を用いて、入力差分から生成した各入力差分値と、該各入力差分値に対応する出力ワード差分から生成した出力差分値との組み合わせがあり得るか否かを判定してゆき、取りうる出力差分値のすべてが前記入力差分値との組み合わせとしてあり得ない出力ワード差分の存在を１つでも確認できた場合に、その入力差分と出力差分の組が不能差分であると判定する不能差分判定部と、
を備える不能差分探索装置。
【請求項２】
さらに、
前記入力差分および出力差分についてそれぞれワード差分が一致する要素の集合が１つのグループとなるように、前記入力ワード差分と出力ワード差分とをそれぞれグループ化する関係式探索部と、
前記関係式探索部で分類された入力ワード差分の各グループにおいて、入力ワード差分から取り得るすべての入力差分値を生成する入力差分値生成部と、
前記関係式探索部で分類された出力ワード差分の各グループにおいて、出力ワード差分から取り得るすべての出力差分値を生成する出力差分値生成部と、を備え、
前記入力差分から生成した各入力差分値に対して、出力差分値があり得ないものであるか否かの判定を前記グループ単位で実施していく請求項１の不能差分探索装置。
【請求項３】
不能差分探索対象の暗号アルゴリズムの暗号部品毎に記憶した入出力差分の１対１対応表を参照し、入力差分および出力差分について順方向および逆方向の差分を算出するラウンド差分計算部と、
入力差分と出力差分が不明な状態になるまで、前記ラウンド差分計算部を動作させて前記１対多の対応表を適用する位置を決定し、前記関係式探索部に当該位置の入力差分および出力差分を出力する１対多対応位置決定部と、
を備える請求項２の不能差分探索装置。
【請求項４】
さらに、
前記判定部を用いて、入力差分から生成した各入力差分値と、各入力差分値に対応する位置の出力差分値との組み合わせがあり得るか否かを判定してゆき、出力ワード差分のすべてが、前記入力差分値との組み合わせとしてあり得る出力差分値を持つことを確認できた場合に、その入力差分と出力差分の組が不能差分ではないと判定する非不能差分判定部を備える請求項１から３いずれか一の不能差分探索装置。
【請求項５】
さらに、
不能差分探索対象の暗号アルゴリズムの非線形関数を用いて、１対多の対応表を生成する１対多の対応表生成部を備える請求項１から４いずれか一の不能差分探索装置。
【請求項６】
共通鍵ブロック暗号を構成するラウンド関数内部で使用される非線形関数の入力差分値と出力差分値とに関する１対多の対応表を保持し、該１対多の対応表を用いて、２つ以上のワード（入力ワード差分）で構成される入力差分の入力ワード差分から取り得る入力差分値と、２つ以上のワード（出力ワード差分）で構成される出力差分の出力ワード差分から取り得る出力差分値と、の組み合わせがあり得るか否かを判定するステップを繰り返し、
取りうる出力差分値のすべてが前記入力差分値との組み合わせとしてあり得ない出力ワード差分の存在を１つでも確認できた場合に、その入力差分と出力差分の組が不能差分であると判定する不能差分探索方法。
【請求項７】
共通鍵ブロック暗号を構成するラウンド関数内部で使用される非線形関数の入力差分値と出力差分値とに関する１対多の対応表を保持し、該１対多の対応表を用いて、２つ以上のワード（入力ワード差分）で構成される入力差分の入力ワード差分から取り得る入力差分値と、２つ以上のワード（出力ワード差分）で構成される出力差分の出力ワード差分から取り得る出力差分値と、の組み合わせがあり得るか否かを判定する処理を繰り返し、取りうる出力差分値のすべてが前記入力差分値との組み合わせとしてあり得ない出力ワード差分の存在を１つでも確認できた場合に、その入力差分と出力差分の組が不能差分であると判定する処理をコンピュータに実行させるプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【公開番号】特開２０１１−１３６３３（Ｐ２０１１−１３６３３Ａ）
【公開日】平成２３年１月２０日（２０１１．１．２０）
【国際特許分類】
【出願番号】特願２００９−１６００３５（Ｐ２００９−１６００３５）
【出願日】平成２１年７月６日（２００９．７．６）
【出願人】（０００００４２３７）日本電気株式会社 (19,353)
【出願人】（０００２４２６６６）北陸日本電気ソフトウェア株式会社 (11)
【Ｆターム（参考）】
【公開日】平成２３年１月２０日（２０１１．１．２０）
【国際特許分類】
【出願日】平成２１年７月６日（２００９．７．６）
【出願人】（０００００４２３７）日本電気株式会社 (19,353)
【出願人】（０００２４２６６６）北陸日本電気ソフトウェア株式会社 (11)
【Ｆターム（参考）】
[ Back to top ]