(57)【要約】  本発明は、入力サイズと出力サイズが異なる部品関数を持つ暗号装置及び処理が複雑で計算では表現できない部品関数を持つ暗号装置に対する不能差分を探索する装置を提供することを目的とする。処理定義記憶装置１５は、入力データと鍵データとを攪拌する演算又はその組合せを複数ラウンド繰り返す構造における入力差分と出力差分との対応表を記憶し、ラウンド差分計算部１２は、その対応表を参照し、かかる構造について入力差分から出力差分を計算する（図１）。
2009031559.tif 000002
【特許請求の範囲】
【請求項１】
暗号装置に対する不能差分を探索する不能差分探索装置であって、
入力データと鍵データとを攪拌する演算又はその組合せを複数ラウンド繰り返す構造における入力差分と出力差分との対応表を参照し、前記構造について入力差分から出力差分を計算するように構成されたラウンド差分計算部を備えることを特徴とする不能差分探索装置。
【請求項２】
前記対応表を記憶するように構成された処理定義記憶装置を備えることを特徴とする不能差分探索装置。
【請求項３】
不能差分が存在する最大ラウンド数、及び／又は、そのときの入出力差分を出力するように構成された不能差分出力部を備えることを特徴とする、請求項１又は２に記載の不能差分探索装置。
【請求項４】
前記対応表は、論理積、論理和若しくは排他的論理和、加算、減算、乗算若しくは除算又は置換表（Ｓ−ｂｏｘ）のいずれか一又はこれらの２以上の組合せに対する入力差分と出力差分との対応表であることを特徴とする、請求項１ないし３のいずれか１項に記載の不能差分探索装置。
【請求項５】
前記ラウンド差分計算部は、平文から順方向に前記構造の出力差分を計算するとともに暗号文から逆方向に前記構造の出力差分を計算するように構成されたことを特徴とする、請求項１ないし４のいずれか１項に記載の不能差分探索装置。
【請求項６】
前記ラウンド差分計算部で計算された順方向の出力差分と逆方向の出力差分とを比較して矛盾を検出するように構成された不能差分検出部を備えることを特徴とする、請求項５に記載の不能差分探索装置。
【請求項７】
暗号装置に対する不能差分を探索する不能差分探索方法であって、
入力データと鍵データとを攪拌する演算又はその組合せを複数ラウンド繰り返す構造における入力差分と出力差分との対応表を参照し、前記構造について入力差分から出力差分を計算するラウンド差分計算工程を含むことを特徴とする不能差分探索方法。
【請求項８】
不能差分が存在する最大ラウンド数、及び／又は、そのときの入出力差分を出力する工程を含むことを特徴とする、請求項７に記載の不能差分探索方法。
【請求項９】
前記対応表が、論理積、論理和若しくは排他的論理和、加算、減算、乗算若しくは除算又は置換表（Ｓ−ｂｏｘ）のいずれか一又はこれらの２以上の組合せに対する入力差分と出力差分との対応表であることを特徴とする、請求項７又は８に記載の不能差分探索方法。
【請求項１０】
前記ラウンド差分計算工程において、平文から順方向に前記構造の出力差分を計算するとともに暗号文から逆方向に前記構造の出力差分を計算することを特徴とする、請求項７ないし９のいずれか１項に記載の不能差分探索方法。
【請求項１１】
前記ラウンド差分計算工程において計算された順方向の出力差分と逆方向の出力差分とを比較して矛盾を検出する工程を含むことを特徴とする、請求項１０に記載の不能差分探索方法。
【請求項１２】
暗号装置に対する不能差分を探索する処理をコンピュータに実行させる不能差分探索プログラムであって、
入力データと鍵データとを攪拌する演算又はその組合せを複数ラウンド繰り返す構造における入力差分と出力差分との対応表をコンピュータの記憶部から入力し、前記構造について入力差分から出力差分を計算するラウンド差分計算処理をコンピュータに実行させることを特徴とする不能差分探索プログラム。
【請求項１３】
不能差分が存在する最大ラウンド数、及び／又は、そのときの入出力差分を出力する処理をコンピュータに実行させることを特徴とする、請求項１２に記載の不能差分探索プログラム。
【請求項１４】
前記対応表が、論理積、論理和若しくは排他的論理和、加算、減算、乗算若しくは除算又は置換表（Ｓ−ｂｏｘ）のいずれか一又はこれらの２以上の組合せに対する入力差分と出力差分との対応表であることを特徴とする、請求項１２又は１３に記載の不能差分探索プログラム。
【請求項１５】
前記ラウンド差分計算処理において、平文から順方向に前記構造の出力差分を計算するとともに暗号文から逆方向に前記構造の出力差分を計算する処理をコンピュータに実行させることを特徴とする、請求項１２ないし１４のいずれか１項に記載の不能差分探索プログラム。
【請求項１６】
前記ラウンド差分計算処理において計算された順方向の出力差分と逆方向の出力差分とを比較して矛盾を検出する処理をコンピュータに実行させることを特徴とする、請求項１５に記載の不能差分探索プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
（関連出願についての記載）
本願は、先の日本特許出願２００７−２３０３１８号（２００７年９月５日出願）の優先権を主張するものであり、前記先の出願の全記載内容は、本書に引用をもって繰込み記載されているものとみなされる。
本発明は、不能差分探索装置、方法及びプログラムに関し、特に、不能差分を検出して暗号装置の安全性を評価する不能差分探索装置、方法及びプログラムに関する。
【背景技術】
【０００２】
不能差分解析は、ブロック暗号の解析手法の一つである。不能差分解析は、成立し得ない差分特性である不能差分（Ｉｍｐｏｓｓｉｂｌｅ  Ｄｉｆｆｅｒｅｎｔｉａｌｓ）に基づいて、ブロック暗号の最初のラウンドや最後の数ラウンドの鍵を求めるものである（非特許文献１）。【０００３】
不能差分は次の３種類に分類して定義される。
１．確率０型
入力差分Ａの組を暗号化処理の順方向にｒｆラウンド実行したときの出力差分がＢでない（すなわち、Ｂである確率は０である）ｒｆラウンドの不能差分を確率０型と定義する。
２．中間不一致型
入力差分Ａの組を順方向にｒｆラウンド実行したときの出力差分が確率１でＣであり、入力差分Ｂの組を逆方向にｒｂラウンド実行したときの出力差分が確率１でＤであり、かつ、同じビット位置で中間差分がＣ≠Ｄである（ｒｆ＋ｒｂ）ラウンドの不能差分を中間不一致型と定義する。
３．全単射型
全単射なＦ関数で構成されるＧｅｎｅｒａｌｉｚｅｄ  Ｆｅｉｓｔｅｌ構造において、入力差分Ａの組を順方向にｒｆラウンド実行したときの出力差分が確率１でＣであり、入力差分Ｂの組を逆方向にｒｂラウンド実行したときの出力差分が確率１でＤである場合において、ＣとＤとで挟まれるラウンドのＦ関数入力差分が非０であり、Ｆ関数出力差分が０である（ｒｆ＋１＋ｒｂ）ラウンドの不能差分を全単射型と定義する。また、ＣとＤとで挟まれるラウンドのＦ関数入力差分が０であり、Ｆ関数出力差分が非０である場合にも、全単射型の不能差分と定義する。【０００４】
ここで、ｒｂ＝０の場合、中間不一致型は確率０型と等価となる。すなわち、確率０型は中間不一致型に含まれるため、中間不一致型及び全単射型の不能差分を探索すれば十分である。【０００５】
従来、確率０型の不能差分の探索方法としては全数探索的な方法しか知られておらず、かかる方法は計算量が多いため、適用することが困難であった。しかし、ブロック暗号がｎ個のサブブロックに分割して処理する構造の場合には、いくつかの手法が提案されている（非特許文献３及び非特許文献４）。【０００６】
中間不一致型の不能差分に対しても、いくつかの探索方法が提案されている。非特許文献１において、各サブブロックの差分が任意の非０か又は０かに注目する探索手法、非特許文献５において確率０型の探索を中間不一致型に拡張した手法が開示されている。【０００７】
非特許文献６において、Ｋｉｍらによって、中間不一致型と全単射型の両方を探索する手法が提案されている。彼らの手法においても、対象とするブロック暗号はｎ個のサブブロックに分割して処理する構造である。Ｋｉｍらの手法においては、Ｆ関数の入力と出力のサイズが同じである全単射関数であって、１ラウンド分の処理をｎ×ｎ行列で表すことができる構造に限定し、行列の要素間の矛盾を見つけることで、不能差分の最大ラウンド数を出力する。【０００８】
例えば、図４のようなＦｅｉｓｔｅｌ構造の場合、行列εによって処理が表される。また、差分の種類は図１３、処理１＿Ｆは図１４のように定義されている。さらに、排他的論理和演算４１は図１５のように定義されている（ただし、ｋ∈｛０、１、１＊、２＊、ｔ｝、ｔ’≧２とする。）。このときの計算例を図１０に示す。【０００９】
【非特許文献１】E. Biham, A. Biryukov and A. Shamir,"Cryptanalysis of Skipjack Reduced to 31 Rounds Using Impossible Differentials,"EUROCRYPT’99, LNCS 1592, Springer-Verlag, 1999, pp.12-23.
【非特許文献２】S. Lucks,"On the Security of the 128-bit Block Cipher DEAL,"FSE'99, Springer-Verlag, 1999, pp.60-70.
【非特許文献３】K. Aoki,"On Cryptanalysis with Impossible Defferentials,"SCIS'99, 1999, pp.685-689.
【非特許文献４】M. Sugita, K Kobara, K. Uehara, S. Kubota, and H. Imai,"Relationships among Differential, Truncated Differential, Impossible Differential Cryptanalyses against Word-Oriented Block Ciphers like Rijndael, E2,”Presented at Third AES Workshop, April 2000.
【非特許文献５】K. Aoki and M. Kanda ,"Search for Impossible Differential of E2,”April 15, 1999. Available athttp://csrc.nist.gov/CryptoToolkit/aes/round1/comments/990415-kaoki4.pdf
【非特許文献６】J. Kim, S. Hong, J. Sung, S. Lee, J. Lim and S. Sung,"Impossible Differential Cryptanalysis for Block Cipher Structures,"INDOCRYPT2003, LNCS 2904, Springer-Verlag, 2003, pp.82-96.
【非特許文献７】C. Burwick, D. Coppersmith, E. C'Avignon, R. Gennaro, S. Halevi, C. Jutla, S.M. Matyas, L. O'Connor, M. Peyravian, D. Safford, and N. Zunic,"MARS - A Candidate Cipher for AES,"NIST AES Proposal, June 1998.
【発明の開示】
【発明が解決しようとする課題】
【００１０】
なお、上記の非特許文献の各開示を、本書に引用をもって繰り込むものとする。以下の分析は、本発明者によってなされたものである。【００１１】
非特許文献６の手法では、例えば、入力サイズと出力サイズが異なるＦ関数を持つ暗号装置の不能差分は探索することができない。また、処理が複雑で図１４のような計算では表現できないＦ関数を持つ暗号装置の不能差分も探索することができない。一例として、図１１及び図１２に示すＭＡＲＳのＥ関数（非特許文献７）がある。Ｅ関数は、入力サイズと出力サイズとが異なり、出力の一部のみが全単射で確率１の差分特性を持つため、非特許文献６の手法に基づいて、この不能差分を探索することはできない。【００１２】
そこで、入力サイズと出力サイズが異なる部品関数を持つ暗号装置及び処理が複雑で計算では表現できない部品関数を持つ暗号装置に対する不能差分を探索する装置を提供することが課題となる。
【課題を解決するための手段】
【００１３】
本発明の第１の視点に係る不能差分探索装置は、暗号装置に対する不能差分を探索する不能差分探索装置であって、入力データと鍵データとを攪拌する演算又はその組合せを複数ラウンド繰り返す構造における入力差分と出力差分との対応表を参照し、前記構造について入力差分から出力差分を計算するように構成されたラウンド差分計算部を備えることを特徴とする。また、不能差分探索装置は、上記対応表を記憶する処理定義記装置を備えるようにしてもよい。【００１４】
本発明の第２の視点に係る不能差分探索方法は、暗号装置に対する不能差分を探索する不能差分探索方法であって、入力データと鍵データとを攪拌する演算又はその組合せを複数ラウンド繰り返す構造における入力差分と出力差分との対応表を参照し、前記構造について入力差分から出力差分を計算するラウンド差分計算工程を含むことを特徴とする。【００１５】
本発明の第３の視点に係る不能差分探索プログラムは、暗号装置に対する不能差分を探索する処理をコンピュータに実行させる不能差分探索プログラムであって、入力データと鍵データとを攪拌する演算又はその組合せを複数ラウンド繰り返す構造における入力差分と出力差分との対応表をコンピュータの記憶部から入力し、前記構造について入力差分から出力差分を計算するラウンド差分計算処理をコンピュータに実行させることを特徴とする。【００１６】
第１の展開形態の不能差分探索装置は、不能差分が存在する最大ラウンド数、及び／又は、そのときの入出力差分を出力するように構成された不能差分出力部を備えることが好ましい。【００１７】
第２の展開形態の不能差分探索装置は、前記対応表が、論理積、論理和若しくは排他的論理和、加算、減算、乗算若しくは除算又は置換表（Ｓ−ｂｏｘ）のいずれか一又はこれらの２以上の組合せに対する入力差分と出力差分との対応表であってもよい。【００１８】
第３の展開形態の不能差分探索装置は、前記ラウンド差分計算部が、平文から順方向に前記構造の出力差分を計算するとともに暗号文から逆方向に前記構造の出力差分を計算するように構成されることが好ましい。【００１９】
第４の展開形態の不能差分探索装置は、前記ラウンド差分計算部で計算された順方向の出力差分と逆方向の出力差分とを比較して矛盾を検出するように構成された不能差分検出部を備えることが好ましい。【００２０】
第５の展開形態の不能差分探索方法は、不能差分が存在する最大ラウンド数、及び／又は、そのときの入出力差分を出力する工程を含むことが好ましい。【００２１】
第６の展開形態の不能差分探索方法は、前記対応表が、論理積、論理和若しくは排他的論理和、加算、減算、乗算若しくは除算又は置換表（Ｓ−ｂｏｘ）のいずれか一又はこれらの２以上の組合せに対する入力差分と出力差分との対応表であってもよい。【００２２】
第７の展開形態の不能差分探索方法は、前記ラウンド差分計算工程において、平文から順方向に前記構造の出力差分を計算するとともに暗号文から逆方向に前記構造の出力差分を計算することが好ましい。【００２３】
第８の展開形態の不能差分探索方法は、前記ラウンド差分計算工程において計算された順方向の出力差分と逆方向の出力差分とを比較して矛盾を検出する工程を含むことが好ましい。【００２４】
第９の展開形態の不能差分探索プログラムは、不能差分が存在する最大ラウンド数、及び／又は、そのときの入出力差分を出力する処理をコンピュータに実行させることが好ましい。【００２５】
第１０の展開形態の不能差分探索プログラムは、前記対応表が、論理積、論理和若しくは排他的論理和、加算、減算、乗算若しくは除算又は置換表（Ｓ−ｂｏｘ）のいずれか一又はこれらの２以上の組合せに対する入力差分と出力差分との対応表であってもよい。【００２６】
第１１の展開形態の不能差分探索プログラムは、前記ラウンド差分計算処理において、平文から順方向に前記構造の出力差分を計算するとともに暗号文から逆方向に前記構造の出力差分を計算する処理をコンピュータに実行させることが好ましい。【００２７】
第１２の展開形態の不能差分探索プログラムは、前記ラウンド差分計算処理において計算された順方向の出力差分と逆方向の出力差分とを比較して矛盾を検出する処理をコンピュータに実行させることが好ましい。
【発明の効果】
【００２８】
本発明に係る不能差分探索装置によって、入力サイズと出力サイズが異なる部品関数を持つ暗号装置及び処理が複雑で計算では表現できない部品関数を持つ暗号装置に対する不能差分を探索することができる。
【図面の簡単な説明】
【００２９】
【図１】本発明の実施例に係る不能差分探索装置のブロック図である。
【図２】本発明の実施例に係る不能差分探索装置を説明するための図である。
【図３】本発明の実施例に係る不能差分探索装置における処理のフローチャートである。
【図４】従来技術が対象とする暗号装置のブロック図である。
【図５】本発明の実施例における差分の種類を示す図である。
【図６】本発明の実施例におけるＦ関数における入出力差分の対応表である。
【図７】本発明の実施例における排他的論理和演算における入出力差分の対応表である。
【図８】本発明の実施例における中間不一致型の判定結果を示す図である。
【図９】本発明の実施例におけるＥ関数における入出力差分の対応表である。
【図１０】非特許文献６における従来技術に基づく評価例を示す図である。
【図１１】非特許文献７におけるブロック暗号ＭＡＲＳの一部を表した図である。
【図１２】非特許文献７におけるブロック暗号ＭＡＲＳのＥ関数を表す図である。
【図１３】非特許文献６における差分の種類を表す図である。
【図１４】非特許文献６における処理１＿Ｆの定義を示す図である。
【図１５】非特許文献６における排他的論理和演算の定義を示す図である。
【符号の説明】
【００３０】
１０  不能差分探索装置
１１  暗号装置入力差分生成部
１２  ラウンド差分計算部
１３  不能差分検出部
１４  不能差分出力部
１５  処理定義記憶装置
１６  差分遷移情報記憶装置
【発明を実施するための最良の形態】
【００３１】
本発明の実施形態に係る不能差分探索装置について、図面を参照して説明する。【００３２】
不能差分探索装置１０は、図１を参照すると、暗号装置に対する不能差分を探索する装置である。処理定義記憶装置１５は、入力データと鍵データとを攪拌する演算又はその組合せを複数ラウンド繰り返す構造における入力差分と出力差分との対応表を記憶する。ラウンド差分計算部１２は、その対応表を参照し、かかる構造について入力差分から出力差分を計算する。
【実施例】
【００３３】
次に、本発明の実施例について図面を参照して詳細に説明する。【００３４】
図１は、本発明の実施例に係る不能差分探索装置のブロック図である。【００３５】
不能差分探索装置１０は、図１を参照すると、暗号装置入力差分生成部１１、ラウンド差分計算部１２、不能差分検出部１３、不能差分出力部１４、処理定義記憶装置１５及び差分遷移情報記憶装置１６を備える。【００３６】
本実施例に係る不能差分探索装置においては、ブロック暗号は平文を均等にｎ個のサブブロックに分割して処理する構造とする。【００３７】
差分は種類に応じていくつかに分類する。例えば、差分を図５の５種類Ｚ、Ｄ、Ｆ、Ｆ２、Ｒに分類する。【００３８】
ここで、Ｆ、Ｆ２は攻撃に都合の良いように攻撃者が選択できるものとする。Ｆ２はＦ関数の出力差分であり、Ｆ≠Ｆ２である。さらに、攻撃者は入力差分Ｆを固定することによって、出力差分Ｆ２も固定することができる。【００３９】
Ｆ関数が全単射であるか否かにかかわらず、Ｆ関数が鍵に依存しない確率１の差分特性をもつ場合には、Ｆ関数の入力差分→出力差分を、Ｆ→Ｆ２と定義する。ここで、確率１の差分特性とは、次のいずれかである。
・Ｆ関数の入力差分がａならば出力差分は必ずｂとなる。
・Ｆ関数の入力差分がａならば起こりえない出力差分があるため、出力差分はｂ０、ｂ１、ｂ２、…に限られる。【００４０】
図６はＦ関数の入出力差分を示す。このＦ関数は入力サイズと出力サイズとが等しく、その入力サイズが１つのサブブロックである。Ｆ関数が確率１の差分特性をもたないとき、その入力差分→出力差分はＦ→Ｄ（あるいはＲ）と定義する。Ｆ関数が全単射であるとき、その入力差分→出力差分はおのおのＦ→Ｆ２（あるいはＤ）、Ｆ２→Ｄ、Ｄ→Ｄと定義する。Ｆ関数の入力サイズと出力サイズが等しくない、あるいは、入力が複数のサブブロックから成るならば、図６ではすべての入出力差分組を定義する。【００４１】
図７は排他的論理和演算の入出力差分を示す。排他的論理和演算の２個の入力差分を図５の５種類の差分の全ての組み合わせとし、排他的論理和演算の出力差分を定義する。例えば、入力差分の一方がＺであれば、もう一方の入力差分が出力差分としてそのまま出力される。一方の入力差分がＦで、もう一方の入力差分がＦ２のとき、出力差分はＤである。また、入力差分の両方が同じ差分であれば、排他的論理和演算で消しあい出力差分はＺとなる。【００４２】
本探索法は、最初に、暗号化処理の順方向（入力は平文側、出力は暗号文側）と逆方向（入力は暗号文側、出力は平文側）にラウンド毎の出力差分を計算する。次に、両方の出力差分同士を比較し、中間不一致型と全単射型の不能差分を見つける。【００４３】
まず、暗号化処理の順方向の差分をＺｆ、Ｆｆ、Ｆ２ｆ、Ｄｆ、Ｒｆ、逆方向の差分をＺｂ、Ｆｂ、Ｆ２ｂ、Ｄｂ、Ｒｂとする。【００４４】
順方向と逆方向の出力差分同士を比較し、同じサブブロック位置で、その組が矛盾のある組ならば中間不一致型であると決定する。【００４５】
図８は矛盾のある組（「ｍｉｓｓ」）と、矛盾のない組（「−」）を示す。（Ｆｆ、Ｆｂ）、（Ｆｆ、Ｆ２ｂ）、（Ｆ２ｆ、Ｆｂ）、（Ｆ２ｆ、Ｆ２ｂ）の組が、おのおのＦｆ≠Ｆｂ、Ｆｆ≠Ｆ２ｂ、Ｆ２ｆ≠Ｆｂ、Ｆ２ｆ≠Ｆ２ｂに固定されるならば、そのときに限りｍｉｓｓである。【００４６】
順方向と逆方向の出力差分同士を比較し、次のいずれかの条件を満たすならば全単射型と判定する。
条件１．Ｆ関数の入力差分が非０（Ｆ、Ｆ２、Ｄ）かつ出力差分がＺ
条件２．Ｆ関数の入力差分がＺかつ出力差分が非０（Ｆ、Ｆ２、Ｄ）
まず、図２のようにＩｆ、Ｉｂ、Ｏｆ、Ｏｂを定義する。【００４７】
条件１の場合、（Ｉｆ、Ｉｂ）の少なくとも一方がＦ、Ｆ２、Ｄならば、Ｆ関数の入力差分は非０である。さらに、（Ｏｆ、Ｏｂ）が、（Ｚｆ、Ｚｂ）、（Ｆｆ、Ｆｂ）、（Ｆｆ、Ｆ２ｂ）、（Ｆ２ｆ、Ｆｂ）又は（Ｆ２ｆ、Ｆ２ｂ）のいずれかであるならばＦ関数の出力差分はＺである。【００４８】
（Ｆｆ、Ｆｂ）、（Ｆｆ、Ｆ２ｂ）、（Ｆ２ｆ、Ｆｂ）、（Ｆ２ｆ、Ｆ２ｂ）の組が、おのおのＦｆ≠Ｆｂ、Ｆｆ≠Ｆ２ｂ、Ｆ２ｆ≠Ｆｂ、Ｆ２ｆ≠Ｆ２ｂに固定されるならば、そのときに限りＺである。【００４９】
条件２の場合、（Ｉｆ、Ｉｂ）の少なくとも一方がＺならばＦ関数の入力差分はＺである。さらに、（Ｏｆ、Ｏｂ）が、（Ｚｆ、Ｚｂ）、（Ｚｆ、Ｆ２ｂ）、（Ｚｆ、Ｄｂ）、（Ｆｆ、Ｚｂ）、（Ｆｆ、Ｆｂ）、（Ｆｆ、Ｆ２ｂ）、（Ｆ２ｆ、Ｚｂ）、（Ｆ２ｆ、Ｆｂ）、（Ｆ２ｆ、Ｆ２ｂ）又は（Ｄｆ、Ｚｆ）のいずれかであるならばＦ関数の出力差分は非０である。【００５０】
（Ｆｆ、Ｆｂ）、（Ｆｆ、Ｆ２ｂ）、（Ｆ２ｆ、Ｆｂ）、（Ｆ２ｆ、Ｆ２ｂ）の組が、おのおのＦｆ≠Ｆｂ、Ｆｆ≠Ｆ２ｂ、Ｆ２ｆ≠Ｆｂ、Ｆ２ｆ≠Ｆ２ｂに固定されるならば、そのときに限り非０である。【００５１】
本実施例に係る不能差分探索装置１０における不能差分の探索アルゴリズムを図３のフローチャートを参照して説明する。【００５２】
最初に、（暗号装置入力差分生成部１１はラウンド差分計算部１２に対し、）順方向に暗号装置入力差分を与え、（ラウンド差分計算部１２は）差分遷移情報（順/逆方向、暗号装置入力差分、通過ラウンド数、通過ラウンド数後の出力差分を１組とする情報）を計算し（ステップＳ１）、（差分遷移情報記憶装置１６は、計算された差分遷移情報を）記憶する。【００５３】
暗号装置入力差分生成部１１は、暗号装置入力差分α０ｉ（１≦ｉ≦２＾｛ｎ−１｝）を生成する。ここで、ｉを２進数で表現したときの０にＺを割り当て、１にＦを割り当てる。例えば、α０１＝（Ｚ、…、Ｚ、Ｆ）、α０２＝（Ｚ、…、Ｆ、Ｚ）とする。【００５４】
ラウンド差分計算部１２は、処理定義記憶装置１５に記憶された処理定義を参照しつつ、すべてのα０ｉに対して、すべてのサブブロックがＲとなるまでαｒｉ（１≦ｒ）を計算する。【００５５】
計算した差分遷移情報は、差分遷移情報記憶装置１６に記憶される。【００５６】
記憶した順方向の差分遷移情報のうち、一番大きい通過ラウンド数をｍａｘαとする。【００５７】
また、逆方向についても同様に、（ラウンド差分計算部１２は）差分遷移情報を計算し（ステップＳ２）、（差分遷移情報記憶装置１６は、計算された差分遷移情報を）記憶する。具体的には以下の処理を行う。【００５８】
暗号装置入力差分β０ｉ（１≦ｉ≦２＾｛ｎ−１｝）を、暗号装置入力差分生成部１１で生成する。【００５９】
ラウンド差分計算部１２は、処理定義記憶装置１５に記憶された処理定義を参照しつつ、すべてのβ０ｉに対して、すべてのサブブロックがＲとなるまでβｒｉ（１≦ｒ）を計算する。【００６０】
差分遷移情報記憶装置１６は、（ラウンド差分計算部１２により）計算された差分遷移情報を記憶する。【００６１】
逆方向の差分遷移情報のうち、一番大きい通過ラウンド数をｍａｘβとする。【００６２】
次に、不能差分検出部１３は、記憶した差分遷移情報を参照しつつ、不能差分を検出する（ステップＳ３）。不能差分を検出した場合、不能差分出力部１４は、最大ラウンド数又は不能差分を出力する（ステップＳ４）。最大ラウンド数を出力することによって、（不能差分探索装置１０の利用者は）不能差分解析に対する安全性を定量的に評価することができる。また、不能差分を出力することによって、不能差分を利用する具体的な鍵復元解析を検討することができるため、（不能差分探索装置１０の利用者は）より詳細に安全性を評価することができる。以下に具体的な手順を説明する。【００６３】
探索ラウンドｒｓをｒｓ＝ｍａｘα＋ｍａｘβ＋１とする。【００６４】
（不能差分検出部１３は）全てのαｘｉ、βｙｉの組について、ｘ＋ｙ＝ｒｓとなる組について中間不一致型を判定し（ステップＳ３）、不能差分出力部１４は不能差分を出力する（ステップＳ４）。【００６５】
（不能差分検出部１３は）全てのαｘｉ、βｙｉの組について、ｘ＋ｙ＝ｒｓ−１となる組について全単射型を判定し（ステップＳ３）、不能差分出力部１４は不能差分を出力する（ステップＳ４）。【００６６】
もし、中間不一致型及び全単射型のいずれの不能差分も見つかった場合又はｒｓ＝２となった場合（ステップＳ５のＮｏ）には、不能差分の探索処理（ステップＳ３及びＳ４）を終了する。それ以外の場合（ステップＳ５のＹｅｓ）には、ｒｓをｒｓ−１として（ステップＳ６）、ステップＳ３へ遷移する。【００６７】
本実施例に係る不能差分探索装置１０は、上記の手順によって、非特許文献６において探索することのできた暗号装置の不能差分を探索することができる。なお、非特許文献６における探索については非特許文献６を参照するものとし、本明細書においては、これ以上の説明は省略する。【００６８】
また、ＭＡＲＳのＥ関数に対しては、次のように不能差分の探索を行う。なお、ＭＡＲＳのＥ関数に関し、さらなる詳細については非特許文献７を参照するものとし、本明細書においては記載を省略する。【００６９】
図１１は、ＭＡＲＳのＫｅｙｅｄ  Ｆｏｒｗａｒｄ  Ｔｒａｎｓｆｏｒｍａｔｉｏｎを示す。Ｋｅｙｅｄ  Ｆｏｒｗａｒｄ  Ｔｒａｎｓｆｏｒｍａｔｉｏｎは、ブロックサイズ１２８ビット、１サブブロックサイズは３２ビットである。また、図１２にＥ関数を示す。Ｅ関数は、入力サイズ３２ビット、出力は３２ビットのサイズのものが３個ある。【００７０】
ここで、入力サイズ３２ビット、出力サイズ３２×３ビットのＥ関数の入出力差分を図９のように定義する。図１１における加算５１及び５２は、排他的論理和とみなす。さらに、１３ビット左巡回シフト５３については、攻撃者が差分を容易に操作できるため、探索において無視する。Ｅ関数の入力差分が０ｘ０００４００００であるならば、出力差分ｏｕｔ３は０ｘ０００００２００という確率１の差分特性をもつ。さらに、出力ｏｕｔ３は全単射であるので、入力差分がＦ２又はＤならばｏｕｔ３はＤと定義する。最後に、Ｆ及びＦ２は攻撃に都合の良いように攻撃者が選択できると仮定しているので、この仮定が成り立つＦ及びＦ２があるか否かを確認する。【００７１】
このように、図６を図９へと置き換えるだけで、非特許文献６においては探索することができなかった暗号装置の不能差分も探索することができる。【００７２】
本実施例に係る不能差分探索装置は、処理定義を図６や図７のような対応表で備えるとともに、この対応表を参照しつつ差分を計算するため、非特許文献６において探索することのできた構造に対応することができる。また、対応表を、例えば、図７から図９へと置き換えるだけで、非特許文献７において探索することのできなかった構造についても対応することができる。【００７３】
以上の記載は実施例に基づいて行ったが、本発明は、上記実施例に限定されるものではない。【００７４】
本発明の全開示（請求の範囲を含む）の枠内において、さらにその基本的技術思想に基づいて、実施形態ないし実施例の変更・調整が可能である。また、本発明の請求の範囲の枠内において種々の開示要素の多様な組み合わせないし選択が可能である。すなわち、本発明は、請求の範囲を含む全開示、技術的思想にしたがって当業者であればなし得るであろう各種変形、修正を含むことは勿論である。
【図１】
2009031559.tif 000003
【図２】
2009031559.tif 000004
【図３】
2009031559.tif 000005
【図４】
2009031559.tif 000006
【図５】
2009031559.tif 000007
【図６】
2009031559.tif 000008
【図７】
2009031559.tif 000009
【図８】
2009031559.tif 000010
【図９】
2009031559.tif 000011
【図１０】
2009031559.tif 000012
【図１１】
2009031559.tif 000013
【図１２】
2009031559.tif 000014
【図１３】
2009031559.tif 000015
【図１４】
2009031559.tif 000016
【図１５】
2009031559.tif 000017
【手続補正書】
【提出日】平成21年3月3日(2009.3.3)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
暗号装置に対する不能差分を探索する不能差分探索装置であって、
入力データと鍵データとを攪拌する演算又はその組合せを複数ラウンド繰り返す構造においてＦ関数が全単射である場合と全単射でない場合とに応じて入力差分と出力差分との対応表を参照し、前記構造について入力差分から出力差分を計算するように構成されたラウンド差分計算部を備えることを特徴とする不能差分探索装置。
【請求項２】
前記対応表を記憶するように構成された処理定義記憶装置を備えることを特徴とする不能差分探索装置。
【請求項３】
不能差分が存在する最大ラウンド数、及び／又は、そのときの入出力差分を出力するように構成された不能差分出力部を備えることを特徴とする、請求項１又は２に記載の不能差分探索装置。
【請求項４】
前記対応表は、論理積、論理和若しくは排他的論理和、加算、減算、乗算若しくは除算又は置換表（Ｓ−ｂｏｘ）のいずれか一又はこれらの２以上の組合せに対する入力差分と出力差分との対応表であることを特徴とする、請求項１ないし３のいずれか１項に記載の不能差分探索装置。
【請求項５】
前記ラウンド差分計算部は、平文から順方向に前記構造の出力差分を計算するとともに暗号文から逆方向に前記構造の出力差分を計算するように構成されたことを特徴とする、請求項１ないし４のいずれか１項に記載の不能差分探索装置。
【請求項６】
前記ラウンド差分計算部で計算された順方向の出力差分と逆方向の出力差分とを比較して矛盾を検出するように構成された不能差分検出部を備えることを特徴とする、請求項５に記載の不能差分探索装置。
【請求項７】
暗号装置に対する不能差分を探索する不能差分探索方法であって、
入力データと鍵データとを攪拌する演算又はその組合せを複数ラウンド繰り返す構造においてＦ関数が全単射である場合と全単射でない場合とに応じて入力差分と出力差分との対応表を参照し、前記構造について入力差分から出力差分を計算するラウンド差分計算工程を含むことを特徴とする不能差分探索方法。
【請求項８】
不能差分が存在する最大ラウンド数、及び／又は、そのときの入出力差分を出力する工程を含むことを特徴とする、請求項７に記載の不能差分探索方法。
【請求項９】
前記対応表が、論理積、論理和若しくは排他的論理和、加算、減算、乗算若しくは除算又は置換表（Ｓ−ｂｏｘ）のいずれか一又はこれらの２以上の組合せに対する入力差分と出力差分との対応表であることを特徴とする、請求項７又は８に記載の不能差分探索方法。
【請求項１０】
前記ラウンド差分計算工程において、平文から順方向に前記構造の出力差分を計算するとともに暗号文から逆方向に前記構造の出力差分を計算することを特徴とする、請求項７ないし９のいずれか１項に記載の不能差分探索方法。
【請求項１１】
前記ラウンド差分計算工程において計算された順方向の出力差分と逆方向の出力差分とを比較して矛盾を検出する工程を含むことを特徴とする、請求項１０に記載の不能差分探索方法。
【請求項１２】
暗号装置に対する不能差分を探索する処理をコンピュータに実行させる不能差分探索プログラムであって、
入力データと鍵データとを攪拌する演算又はその組合せを複数ラウンド繰り返す構造においてＦ関数が全単射である場合と全単射でない場合とに応じて入力差分と出力差分との対応表をコンピュータの記憶部から入力し、前記構造について入力差分から出力差分を計算するラウンド差分計算処理をコンピュータに実行させることを特徴とする不能差分探索プログラム。
【請求項１３】
不能差分が存在する最大ラウンド数、及び／又は、そのときの入出力差分を出力する処理をコンピュータに実行させることを特徴とする、請求項１２に記載の不能差分探索プログラム。
【請求項１４】
前記対応表が、論理積、論理和若しくは排他的論理和、加算、減算、乗算若しくは除算又は置換表（Ｓ−ｂｏｘ）のいずれか一又はこれらの２以上の組合せに対する入力差分と出力差分との対応表であることを特徴とする、請求項１２又は１３に記載の不能差分探索プログラム。
【請求項１５】
前記ラウンド差分計算処理において、平文から順方向に前記構造の出力差分を計算するとともに暗号文から逆方向に前記構造の出力差分を計算する処理をコンピュータに実行させることを特徴とする、請求項１２ないし１４のいずれか１項に記載の不能差分探索プログラム。
【請求項１６】
前記ラウンド差分計算処理において計算された順方向の出力差分と逆方向の出力差分とを比較して矛盾を検出する処理をコンピュータに実行させることを特徴とする、請求項１５に記載の不能差分探索プログラム。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】０００４
【補正方法】変更
【補正の内容】
【０００４】
性を持つため、非特許文献６の手法に基づいて、この不能差分を探索することはできない。
［００１２］
そこで、入力サイズと出力サイズが異なる部品関数を持つ暗号装置及び処理が複雑で計算では表現できない部品関数を持つ暗号装置に対する不能差分を探索する装置を提供することが課題となる。
課題を解決するための手段
［００１３］
本発明の第１の視点に係る不能差分探索装置は、暗号装置に対する不能差分を探索する不能差分探索装置であって、入力データと鍵データとを攪拌する演算又はその組合せを複数ラウンド繰り返す構造においてＦ関数が全単射である場合と全単射でない場合とに応じて入力差分と出力差分との対応表を参照し、前記構造について入力差分から出力差分を計算するように構成されたラウンド差分計算部を備えることを特徴とする。また、不能差分探索装置は、上記対応表を記憶する処理定義記装置を備えるようにしてもよい。
［００１４］
本発明の第２の視点に係る不能差分探索方法は、暗号装置に対する不能差分を探索する不能差分探索方法であって、入力データと鍵データとを攪拌する演算又はその組合せを複数ラウンド繰り返す構造においてＦ関数が全単射である場合と全単射でない場合とに応じて入力差分と出力差分との対応表を参照し、前記構造について入力差分から出力差分を計算するラウンド差分計算工程を含むことを特徴とする。
［００１５］
本発明の第３の視点に係る不能差分探索プログラムは、暗号装置に対する不能差分を探索する処理をコンピュータに実行させる不能差分探索プログラムであって、入力データと鍵データとを攪拌する演算又はその組合せを複数ラウンド繰り返す構造においてＦ関数が全単射である場合と全単射でない場合とに応じて入力差分と出力差分との対応表をコンピュータの記憶部から入力し、前記構造について入力差分から出力差分を計算するラウンド差分計算処理をコンピュータに実行させることを特徴とする。
［００１６］
第１の展開形態の不能差分探索装置は、不能差分が存在する最大ラウンド数、及び／又は、そのときの入出力差分を出力するように構成された不能差分出力部を備えることが好ましい。
［００１７］
第２の展開形態の不能差分探索装置は、前記対応表が、論理積、論理和若しくは排他的論理和、加算、減算、乗算若しくは除算又は置換表（Ｓ−ｂｏｘ）のいずれか一
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】０００７
【補正方法】変更
【補正の内容】
【０００７】
［００３０］
１０  不能差分探索装置
１１  暗号装置入力差分生成部
１２  ラウンド差分計算部
１３  不能差分検出部
１４  不能差分出力部
１５  処理定義記憶装置
１６  差分遷移情報記憶装置
発明を実施するための最良の形態
［００３１］
本発明の実施形態に係る不能差分探索装置について、図面を参照して説明する。
［００３２］
不能差分探索装置１０は、図１を参照すると、暗号装置に対する不能差分を探索する装置である。処理定義記憶装置１５は、入力データと鍵データとを攪拌する演算又はその組合せを複数ラウンド繰り返す構造においてＦ関数が全単射である場合と全単射でない場合とに応じて入力差分と出力差分との対応表を記憶する。ラウンド差分計算部１２は、その対応表を参照し、かかる構造について入力差分から出力差分を計算する。
実施例
［００３３］
次に、本発明の実施例について図面を参照して詳細に説明する。
［００３４］
図１は、本発明の実施例に係る不能差分探索装置のブロック図である。
［００３５］
不能差分探索装置１０は、図１を参照すると、暗号装置入力差分生成部１１、ラウンド差分計算部１２、不能差分検出部１３、不能差分出力部１４、処理定義記憶装置１５及び差分遷移情報記憶装置１６を備える。
［００３６］
本実施例に係る不能差分探索装置においては、ブロック暗号は平文を均等にｎ個のサブブロックに分割して処理する構造とする。
［００３７］
差分は種類に応じていくつかに分類する。例えば、差分を図５の５種類Ｚ、Ｄ、Ｆ、Ｆ２、Ｒに分類する。
［００３８］
ここで、Ｆ、Ｆ２は攻撃に都合の良いように攻撃者が選択できるものとする。Ｆ２はＦ関数の出力差分であり、Ｆ≠Ｆ２である。さらに、攻撃者は入力差分Ｆを固定することによって、出力差分Ｆ２も固定することができる。
［００３９］
Ｆ関数が全単射であるか否かにかかわらず、Ｆ関数が鍵に依存しない確率１の差分
【国際調査報告】
2009031559.tif 000018
2009031559.tif 000019