共通鍵ブロック暗号評価装置、共通鍵ブロック暗号評価方法及びプログラム
【課題】これまでの飽和特性探索では、バランス状態が非線形関数に入力されるとその出力状態は不明として扱っていた。しかしながら、非線形関数の構造と入力の状態によっては、出力状態がバランスする場合があり、正確な評価を行えなかった。
【解決手段】評価を行う暗号アルゴリズムの関数Ｆの構造を考慮したうえで、全数データが関数Ｆを通過する回数を調べる。全数データが関数Ｆを１回だけ通過したデータどうしの排他的論理和であるデータならば、関数Ｆの構造から特殊なバランス状態であるかどうかを判定する。
【解決手段】評価を行う暗号アルゴリズムの関数Ｆの構造を考慮したうえで、全数データが関数Ｆを通過する回数を調べる。全数データが関数Ｆを１回だけ通過したデータどうしの排他的論理和であるデータならば、関数Ｆの構造から特殊なバランス状態であるかどうかを判定する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、共通鍵ブロック暗号に対する解読法である飽和攻撃で利用する飽和特性の探索を行う共通鍵ブロック暗号評価装置、共通鍵ブロック暗号評価方法及びプログラムに関する。
【背景技術】
【０００２】
共通鍵ブロック暗号の解読法の一つに飽和攻撃（Saturation attacks）がある。飽和攻撃は、選択平文攻撃に分類される。飽和攻撃が最初に提案され、適用された暗号は、Daemenらによって提案されたブロック暗号ＳＱＵＡＲＥであった。提案された当時は、ＳＱＵＡＲＥ攻撃と呼ばれていたが、近年は飽和攻撃と呼ばれている。
【０００３】
まず、飽和攻撃の前提知識として、全単射について説明する。
【０００４】
図１に示すように、ｆ：Ａ→Ｂという写像があったとき、集合Ａの任意の元が集合Ｂの任意の元と一対一に定義される写像を全単射という。
【０００５】
関数ｆを、ｎビット入出力の全単射な関数としたとき、入力値と出力値はそれぞれ、０〜２n−１のいずれかとなる。
【０００６】
ここで、０〜２n−１の全ての値のビット毎の排他的論理和（以降、ＸＯＲと記述し、“＋"の記号で表記する）による総和は、ゼロになるという特性がある。
【０００７】
例えばｎ＝２の場合、０〜２2−１（＝３）となり、ビットで表現すると、００（０）、０１（１）、１０（２）、１１（３）となる。
【０００８】
右側のビット位置をビット０とすると、ビット０の総和は、０＋１＋０＋１＝０、ビット１の総和は、０＋０＋１＋１＝０となる。
【０００９】
この特性は、ｎ（ｎ＞１）の値に依らず保たれる。以降、総和がゼロになることを“バランスする"、そのような状態を“バランス状態”という。
【００１０】
バランス状態には以下の４つの種類がある。
【００１１】
（１）．全通りの値が１回ずつ出現
前述したように、ｎビット幅で２n種類の値が１回ずつ出現している状態である。
【００１２】
（２）．一部の値、または全通りの値が偶数回ずつ出現
同じ値どうしのＸＯＲはゼロであるため、偶数個の同じ値をＸＯＲしてもバランスする。どのような値が出ていようとも値ごとの総和はゼロとなるので、全体でもゼロとなりバランスする。以降、これを“偶数バランス"と表現する。
【００１３】
（３）．全通りの値が全て奇数回ずつ出現
奇数回は（偶数回＋１回）であるため、全通りの値が出現していれば（全通りの値が偶数回＋全通りの値が１回）という状態といえるので、これもバランスする。以降、これを“奇数バランス"と表現する。
【００１４】
（４）．混合状態
偶数回と奇数回が入り混じったような、複雑なバランス状態である。以降、これを“混合バランス"と表現する。
【００１５】
これら４つとは別に、一種類の値のみが偶数回出現していても総和はバランスするが、これは“定数"として区別する。
【００１６】
上記（１）〜（３）の３つのバランス状態は、全単射な写像を何回繰り返してもバランス状態は保たれるが、混合バランスは値の絶妙な組み合わせでバランスしているので、次に全単射な写像による変換が行われるとバランス状態が保たれる保証はない。
【００１７】
次に、飽和攻撃の手順を簡単に説明する。
【００１８】
Ｒラウンドで構成される共通鍵ブロック暗号があり、いくらかの平文を与えたときに、Ｒ−１ラウンドの出力がバランスする特性があったとする。
【００１９】
このとき、第Ｒラウンドの鍵を仮定し、得られている暗号文全てについて遡り、第Ｒ−１ラウンドの出力データを得る。
【００２０】
遡ったデータの総和を計算し、バランスしなければ鍵の仮定が誤っていたとして正解の鍵候補から棄却できる。バランスした鍵が正解の鍵候補となる。候補が一つになればそれが正しい鍵と判断する。
【００２１】
このように飽和攻撃では、バランス状態が何ラウンド後まで存在するかが解読可能となるラウンド数に影響するため、バランス状態を正しく評価する必要がある。
【００２２】
図２は、共通鍵ブロック暗号の一例である。入力データをｘ0〜ｘ3の４つに分割して処理を行う一般化Ｆｅｉｓｔｅｌ構造である。
【００２３】
１ラウンドあたり、４つのデータのうちの２つが関数Ｆで変換され、残りの２つのデータにそれぞれＸＯＲされる。図中の＋記号を丸で囲った記号は、ＸＯＲを表す。
【００２４】
各データはそれぞれｍビットとする。関数Ｆ0と関数Ｆ1はｍビットのデータと鍵データとの攪拌を行う。入力されたｍビットのデータに対して、鍵データｋｅｙがＸＯＲされる。
【００２５】
Ｓ0とＳ1はそれぞれ一般的にＳ−ｂｏｘと呼ばれる非線形変換である。それぞれの入出力データサイズは、ｍ／２ビットとなる。
【００２６】
Ｍ0とＭ1はそれぞれ線形変換である。Ｍ0を例として説明すると、以下のような式で表される変換である。
【００２７】
【数１】
【００２８】
【数２】
【００２９】
ここで行われる演算は有限体上のものであり、結果が変数のサイズより大きくなることはない。ここでα0はＳ0の出力、α1はＳ1の出力である。β0とβ1を連結した値がＭ0の出力、つまり関数Ｆ0の出力である。
【００３０】
このように、Ｓ−ｂｏｘと拡散層によって構成されている構造をＳＰ型と呼ぶことにする。
【００３１】
なお、以降の説明では、鍵データの値は状態遷移には影響しないので、図を簡単にするために関数Ｆに入力される鍵データは省略してある。
【００３２】
図中の記号“Ａ"は全通りの値が現れることを、記号“Ｂ"はバランス状態であることを、記号“Ｃ"は定数であることを、そして記号“Ｕ"は状態が不明であることを表す。なお、Ｂがどのような状態によって構成されているかはここでは区別していない。
【００３３】
状態は、関数Ｆを通過したり、ＸＯＲされたりすると変化する。状態遷移は、図３に示すような表で表すことができる。
【００３４】
入力のＡは０〜２m−１までの２m通りのデータであり、Ｃは任意の定数である。つまり、入力の｛Ｃ、Ａ、Ｃ、Ｃ｝は２m通りのデータの集合を意味する。
【００３５】
第４ラウンドの出力データ３２は、ＡとＡのＸＯＲであり、その結果はＢとなる。関数Ｆ0と関数Ｆ1では、鍵データが作用するため、全数の値の出現順序は不明である。すなわち、Ｂがどのバランス状態にあるのかは知ることができない。
【００３６】
従って、これまではＢが関数Ｆを通過すると、状態はＵとして評価を行っていた。非特許文献１に記載される飽和攻撃評価でもそのように評価されている。
【非特許文献１】Sony Corporation、The 128-bit Blockcipher CLEFIA Security and Performance Evaluations Revision 1.0、インターネット＜URL:http://www.sony.co.jp/Products/clefia/technical/data/clefia-eval-1.0.pdf＞
【発明の開示】
【発明が解決しようとする課題】
【００３７】
しかしながら、従来における飽和特性探索法では、バランス状態の構成を区別できないため、バランス状態が非線形変換を通過すると、その出力の状態は不明として扱うしかなかった。
【００３８】
不明な状態は、飽和攻撃には利用できない特性なので、バランス状態を不明として扱うことがあれば、評価として不十分ということになる。
【００３９】
そこで本発明は、上記問題点に鑑みてなされたもので、飽和攻撃に対する評価指標である飽和特性の探索法について、関数Ｆを通過してもバランス状態が保持されるバランス状態を探索できる共通鍵ブロック暗号評価装置を提供することを目的とする。
【課題を解決するための手段】
【００４０】
上記課題を解決するため、本発明における共通鍵ブロック暗号評価装置は、データの分割数ｐと、データサイズｑと、が２ｐ≧ｑを満たすか否かを判定する関数タイプ判定手段と、入力状態を飽和特性の初期状態として、関係式を用いてラウンド処理後の飽和特性を計算する状態遷移計算手段と、を有し、状態遷移計算手段は、関係式に関数の項を含むと、データの全数が関数を通過した回数とバランス状態とを対応させた状態遷移表を参照してバランス状態を計算し、特殊なバランス状態になる可能性があると判定されたときに、関数タイプ判定手段による判定結果を参照して特殊なバランス状態となる構造であるか否かを判定することを特徴とする。
【００４１】
また、本発明における共通鍵ブロック暗号評価方法は、データの分割数ｐと、データサイズｑと、が２ｐ≧ｑを満たすか否かを判定する関数タイプ判定ステップと、関係式に関数の項を含むと、データの全数が関数を通過した回数とバランス状態とを対応させた状態遷移表を参照してバランス状態を計算し、特殊なバランス状態になる可能性があると判定されたときに、関数タイプ判定ステップによる判定結果を参照して特殊なバランス状態となる構造であるか否かを判定する状態遷移計算ステップと、を有することを特徴とする。
【００４２】
また、本発明におけるプログラムは、データの分割数ｐと、データサイズｑと、が２ｐ≧ｑを満たすか否かを判定する関数タイプ判定処理と、関係式に関数の項を含むと、データの全数が関数を通過した回数とバランス状態とを対応させた状態遷移表を参照してバランス状態を計算し、特殊なバランス状態になる可能性があると判定されたときに、関数タイプ判定処理による判定結果を参照して特殊なバランス状態となる構造であるか否かを判定する状態遷移計算処理と、をコンピュータに実行させることを特徴とする。
【発明の効果】
【００４３】
本発明により、評価を行う暗号アルゴリズムの関数Ｆの構造を考慮し、入力が関数Ｆを通過する回数を調べることによって、これまで検出することができなかった特殊なバランス状態を検出することができるようになる。また、特殊なバランス状態を検出することができるようになることによって、飽和攻撃に対する暗号アルゴリズムの安全性をより厳密に評価できるようになる。
【発明を実施するための最良の形態】
【００４４】
まず、関数Ｆにバランス状態が入力されてもその出力がバランス状態となる入力条件を示す。
【００４５】
図２を例に説明すると、入力ｘ1にＡ、その他をＣとしたときに、第５ラウンドの関数Ｆ1の入力となるデータ３２が後述する“特殊なバランス状態"のとき、第５ラウンドの関数Ｆ1の出力データ３３がバランスする。
【００４６】
Ｃは状態に影響を与えないので省略すると、データ３２は、関数Ｆ0３０と関数Ｆ1３１の出力をＸＯＲしたものといえるので、図４のように書き直すことができる。
【００４７】
データ３２をｙとすると、ｙはｘ1の式で表すことが出来る。ｘとｙは関数Ｆ0と関数Ｆ1の内部処理に合わせて、それぞれ、ｘ10とｘ11、ｙ0とｙ1に分割するとｙ0とｙ1は次式で表現できる。
【００４８】
【数３】
【００４９】
【数４】
【００５０】
数３を項の種類ごとにまとめて記述すると、次式のように書き換えることが出来る。ここで、Ｇ0とＧ1は非線形変換を意味する。
【００５１】
【数５】
【００５２】
このように、入力の各項が独立に変換されていることがわかる。このような状態において、Ｇ0とＧ1がバランスし、且つ、式における項の種類数をｐ、項のデータ幅をｑビットとしたとき、次式が成り立つならば、ｙ0は偶数バランス、もしくは奇数バランスのいずれかとなる。
【００５３】
【数６】
【００５４】
数５をみると、項の種類はｘ10とｘ11の２種類なので、種類数ｐは２となる。例えば、データ幅ｑが４（＝２・２）ビット以下ならば、数６は成り立つ。５ビット以上であれば成り立たないので、混合バランスとなる。
【００５５】
数５と数６の条件により、ｙ0が偶数バランスか奇数バランスのどちらかになることを図４を例に説明する。なお、ｙ1も同様に説明できる。
【００５６】
ここでは、ｘ1のサイズｍを８ビットとして説明することとするので、ｐ＝２、ｑ＝４の場合である。これは数６を満たすので、偶数バランス、または奇数バランスのどちらかとなる。
【００５７】
関数Ｆ0と関数Ｆ1の入力となるｘ1には全数が与えられるので、０〜２５５までの２５６（＝２8）通りデータが与えられる。
【００５８】
ｘ10とｘ11は、ｘ1を２分割したものになるので、Ｓ0とＳ1にはそれぞれ、０〜１５までの１６（＝２4）通りのデータが各々１６回与えられる。数５のＧ0とＧ1は他方がある値のときにそれぞれ独立にバランスすることは明らかである。
【００５９】
ここで、各Ｇの出力値の出現パターンを分析する。
【００６０】
ｘ10がある値のときに、ｘ11を全通り与えると、Ｇ1の出力値１６通りの出現回数としては、以下の３通りが考えられる。
【００６１】
（１）．出現回数が０回と偶数回のみ
（２）．出現回数が０回と奇数回のみ
（３）．出現回数が０回と偶数回と奇数回
【００６２】
図５が０回と偶数回のみの例である。実際には、ｘ10の１６通りの値ごとに表の出現回数が得られるので、出現回数の総和は図５の１６倍の出現回数となる。
【００６３】
図６は、出現回数が０回と偶数回と奇数回の例である。値が１、２、４、７の出現回数が奇数回となっている。
【００６４】
Ｇとしてバランスするので、出現回数が奇数回となる値でバランスすることになる。この例では、１＋２＋４＋７＝０となるので、バランスしている。
【００６５】
異なる２種類の値をＸＯＲしても０にはなりえないので、最低３種類必要となるが３種類の出現回数の合計は奇数回になるので、残りの出現回数も奇数回となってしまう。
【００６６】
一方、残りの出現回数は偶数回のものであるから、矛盾する。よって、奇数回となる値は４種類以上の偶数種類に限られる。こちらも実際には１６倍カウントされる。
【００６７】
Ｇの一方が０回と偶数回のみの場合、他方に関係なくｙ0は０回か偶数回、つまり偶数バランスとなる。
【００６８】
ここでは、Ｇ0とＧ1の両方が“０回と奇数回のみ"と“０回と偶数回と奇数回"の場合について説明する。
【００６９】
偶数回出現する値は、それのみでバランスするので奇数回に注目すると、“０回と偶数回と奇数回"は、“０回と奇数回のみ"と条件としては同じである。
【００７０】
Ｇ0で奇数回となった値をａ0、ａ1、ａ2、ａ3、Ｇ1で奇数回となった値をｂ0、ｂ1、ｂ2、ｂ3とする。先述したように、ａ、ｂそれぞれでバランスするので、
【００７１】
【数７】
【００７２】
【数８】
【００７３】
である。奇数回出現した値のＸＯＲの組合せとしては、
【００７４】
【数９】
【００７５】
の１６（＝４2）通り存在する。
【００７６】
ここで、（ａ0＋ｂ0）と（ａ1＋ｂ2）が等しいと仮定すると、
【００７７】
【数１０】
【００７８】
数１０は、交換則が成り立つので、次式が得られる。
【００７９】
【数１１】
【００８０】
更に数７、数８も同様に交換則が成り立つので、数１０、数１１から次式が得られる。数１０に数７を代入して
【００８１】
【数１２】
【００８２】
数１２を変形すると、
【００８３】
【数１３】
【００８４】
数１０に数８を代入すると、
【００８５】
【数１４】
【００８６】
数１４を変形すると、
【００８７】
【数１５】
【００８８】
数１２に数８を代入すると、
【００８９】
【数１６】
【００９０】
数１６を変形すると、
【００９１】
【数１７】
【００９２】
このように、Ｇ0で奇数回出力された任意の値ａiとａj、Ｇ1で奇数回出力された任意の値ｂm、ｂnについて、ａi＋ｂm＝ａj＋ｂnが成り立つならば、その他の組み合わせ全てについて互いに等しくなるものが存在する。このような状態のとき、ｙ0に出現する値の出現回数は全て偶数回となる。
【００９３】
逆に、ａi＋ｂm＝ａj＋ｂnとなるものが存在しない場合、ａxとｂyのＸＯＲの組み合わせ１６通り全てが異なる。すなわち、全通りの値（０〜１５）が全て奇数回出現することになる。
【００９４】
このとき、他に偶数回出現する値があったとしても、ｙ0には全通りの値が出現し、且つ、出現回数は全て奇数回となる。
【００９５】
ここで、数６で示す条件式について、詳細に説明する。
【００９６】
Ｇの種類、つまり項の種類になるが、これは関数Ｆの分割数ｐと等しくなる。分割した各データのサイズがｑビットのとき、値の種類としては、２q通りとなる。
【００９７】
全通りの値が出現するためには、各Ｇから出現される奇数回となった値の種類の組み合わせの数が、２q以上である必要がある。
【００９８】
前述のように、各Ｇから出現する値で出現回数が奇数回となるのは、最低４種類となる。すなわち、
【００９９】
【数１８】
【０１００】
であり、べき数に注目すると、数６が得られる。
【０１０１】
ところで、ｙ0とｙ1の両方が、数５と数６を満たすならば、ｙ0とｙ1は偶数バランスか奇数バランスのどちらかであるが、それらを区別することはできない。
【０１０２】
ここで、ｙ0とｙ1を結合したｍビットのｙでみると、混合バランスとなる可能性がある。
【０１０３】
混合バランスを関数Ｆで変換すると、出力の状態は不明となるが、ｙ0とｙ1がそれぞれ偶数バランスか奇数バランスのどちらかであるという状態であれば、関数Ｆで変換しても出力の状態はバランスする。
【０１０４】
関数ＦがＳＰ型であるならば、Ｓ−ｂｏｘの出力は入力のバランス状態が保たれ、拡散層もＸＯＲによって各入力データを攪拌するため、関数Ｆの出力はバランスする。
【０１０５】
このように、バランスしているデータを分割して見たときに、各々が偶数バランスか奇数バランスである状態を“特殊なバランス状態"と呼ぶことにする。
【０１０６】
次に、次式で示す例でみると、ｘ10とｘ11がそれぞれＳ0とＳ1で独立に変換されているが、それぞれをＸＯＲしたものがＳ2で変換されている。
【０１０７】
このような場合は、数５のように入力の項毎に括ることができないので、ｙ2は混合バランスの可能性がある。
【０１０８】
【数１９】
【０１０９】
図２のデータ３４は、第２ラウンドと第３ラウンドの２回の関数Ｆ0による変換が行われるため、数１９のようにＳ−ｂｏｘの入れ子の式となることは明らかである。
【０１１０】
このように、関数Ｆを２回以上通過したデータは、特殊なバランス状態になる保証はない。特殊なバランス状態となるためには、入力データが異なる２つの関数Ｆによってそれぞれ１回のみ変換されている必要がある。
【０１１１】
すなわち、関数Ｆがその内部でデータをｐ個に分割して処理を行い、それぞれのビット幅がｑであり、数６を満たす暗号アルゴリズムについて、入力ｘにＡを与え、Ｆ0（ｘ）とＦ1（ｘ）がＸＯＲされたデータは、特殊なバランス状態となる。
【０１１２】
次に、本発明の実施の形態について図面を参照して詳細に説明する。
【０１１３】
図７は、本発明の実施形態における共通鍵ブロック暗号評価装置の構成図である。本装置は、キーボード等の入力部１と、プログラム制御により動作する状態遷移計算手段２１と、関数タイプ判定手段２２とを有する飽和特性探索部２と、ディスプレイや印刷装置等の出力部３と、を有して構成される。
【０１１４】
入力部１より、評価パラメータとして“ラウンド数"、“関係式"、“入力状態"、“分割数"、そして“データサイズ"の５つが入力される。
【０１１５】
ラウンド数には評価を行うラウンド数を指定する。１０ラウンドまで評価を行うならば“１０"を指定する。
【０１１６】
関係式は、評価対象暗号アルゴリズムの構造を表すものであり、図２の暗号アルゴリズムの場合、関係式は次式で表される４式となる。
【０１１７】
【数２０】
【０１１８】
【数２１】
【０１１９】
【数２２】
【０１２０】
【数２３】
【０１２１】
入力状態には入力ｘ0〜ｘ3に対して、全数を与える変数と定数を与える変数を指定する。例えば、図２の例のようにｘ1に全数、その他には定数を与えるならば、｛Ｃ，Ａ０，Ｃ，Ｃ｝とする。Ａの添え字０は、初期状態であることを意味する。また、本評価装置では、全数は１箇所のみに与えるものとする。
【０１２２】
分割数は、評価対象暗号アルゴリズムの関数Ｆ内部のデータ分割数を指定する。図２の例では、関数Ｆ0と関数Ｆ1でそれぞれデータを２分割して内部処理を行っているので、“２"となる。
【０１２３】
データサイズは、分割されたデータのサイズをビットで表したものである。
【０１２４】
まず、関数タイプ判定手段２２について説明する。関数タイプ判定手段２２は、評価対象暗号アルゴリズムの関数Ｆの構造から特殊なバランス状態となり得るかどうかを判定する。
【０１２５】
次に、関数タイプ判定手段２２の動作について図８を参照して説明する。
【０１２６】
関数タイプ判定手段２２には、入力された５つのパラメータのうち、分割数とデータサイズの２つが渡され、分割数をｐ、データサイズをｑとしたとき、２ｐ≧ｑが成り立つか否かを判断する（ステップＡ１）。
【０１２７】
もし成り立つならば、フラグをＯＮに設定し（ステップＡ２）、成り立たないなら、フラグをＯＦＦに設定する（ステップＡ３）。なお、設定したフラグは、状態遷移計算手段２１へ渡される。
【０１２８】
次に、図９を参照して状態遷移計算手段２１の動作について説明する。
【０１２９】
状態遷移計算手段２１は、入力状態を飽和特性の初期状態として、関係式を用いてラウンド処理後の飽和特性を計算し、パラメータのラウンド数まで処理すると終了する。
【０１３０】
入力された関係式の数をｍ、ラウンド数をｎとする。入力されたパラメータの入力状態を状態の初期値としてＳ0,0〜Ｓ0,m-1に設定する（ステップＢ１）。図２の例では、入力状態が｛Ｃ，Ａ０，Ｃ，Ｃ｝とき、Ｓ0,0＝Ｃ、Ｓ0,1＝Ａ０、Ｓ0,2＝Ｃ、Ｓ0,3＝Ｃに設定される。
【０１３１】
現在の計算ラウンドを示すカウンタｉに１を設定する（ステップＢ２）。関係式の入力ｘの項に状態Ｓi-1を設定する（ステップＢ３）。計算式の番号を示すカウンタｊに０を設定する（ステップＢ４）。以降、第ｉラウンドの出力の状態Ｓiを計算するステップに入る。
【０１３２】
関係式ｙjがただの代入であるか否かを判断し（ステップＢ５）、代入であれば、代入元の状態をそのままＳi,jに設定する（ステップＢ６）。例えば、数２１や数２３が代入の例である。
【０１３３】
一方、関係式ｙjが代入ではなければ、関数Ｆの項があるか否かを判断し（ステップＢ７）、図１０に示す関数Ｆの状態遷移表を用いて関数Ｆの項を計算する（ステップＢ８）。例えば、数２０や数２２のＦ0（ｘ0）やＦ1（ｘ2）の項を計算する。
【０１３４】
関数Ｆの入力となる項の状態がＡの場合、添え字が１だけインクリメントされる。入力状態としてＡ０が関数Ｆの入力となったとき、その出力の状態はＡ１となり、もう一度入力されるとＡ２となる。つまり、Ａの添え字は関数Ｆを通過した回数を意味する。
【０１３５】
バランス状態は、ＢとＢ*の２種類で区別する。Ｂは、先に述べた４種類のバランス状態のいずれかであり、Ｂ*は、特殊なバランス状態である。Ｂは混合状態のバランスも含むため、関数Ｆの出力はＵとなるが、Ｂ*の出力はＢとなる点が異なる。
【０１３６】
関数Ｆの項を状態遷移させると、数２０と数２２は以下のようになる。
【０１３７】
【数２４】
【０１３８】
【数２５】
【０１３９】
上式のようにＸＯＲのみの式になるので、図１０のＸＯＲの状態遷移表を用いて状態の計算を行う。
【０１４０】
ここで、Ａ１とＡ１のＸＯＲのみ状態であるか否かを判断し、一意に決定しない（ステップＢ９）。Ａ１は、全数が関数Ｆを１回通過した状態を意味するので、Ａ１とＡ１のＸＯＲは特殊なバランス状態になる可能性がある。特殊なバランス状態になるかどうかは、関数Ｆの構造に依存する。関数タイプ判定手段２２で、関数Ｆの構造が調べられており、結果をフラグとして受け取っている。
【０１４１】
Ａ１とＡ１のＸＯＲのみ状態であれば、フラグがＯＮかＯＦＦかを判断する（ステップＢ１０）。フラグがＯＮであれば、特殊なバランス状態となる構造なので、状態Ｓi,jにはＢ*が設定される（ステップＢ１１）。
【０１４２】
一方、フラグがＯＦＦならば、特殊なバランス状態とはならない構造なので、状態Ｓi,jにはＢが設定される（ステップＢ１２）。
【０１４３】
一方、Ａ１とＡ１以外のＸＯＲの場合は、ＸＯＲの状態遷移表の通りの状態をＳi,jに設定する（ステップＢ１３）。
【０１４４】
関係式ｙjの状態計算を終了すると、カウンタｊがインクリメントされて（ステップＢ１４）、カウンタｊが式数ｍ未満であるか否かを判断し（ステップＢ１５）、カウンタｊが式数ｍ未満であれば、次の式の状態計算を同様に行う。一方、カウンタｊがｍまでカウントアップされると、第ｉラウンドの状態計算は終了する。
【０１４５】
ここで、第ｉラウンドの状態Ｓiが全てＵであるか否かを判断し（ステップＢ１６）、全てがＵであれば、以降のラウンドの状態もＵとなり評価を行う必要がないので、終了する。
【０１４６】
一方、状態ＳiにＵ以外の状態があれば、カウンタｉをインクリメントし（ステップＢ１７）、カウンタｉがパラメータで指定されたラウンド数ｎを超えれば、評価を終了する（ステップＢ１８）。達していないならば、次のラウンドの評価を同様に実施する。
【０１４７】
（他の実施の形態）
【０１４８】
次に、本発明の第２の実施の形態について図面を参照して詳細に説明する。
【０１４９】
図１１は、本発明の他の実施の形態における共通鍵ブロック暗号評価装置の構成図である。本装置は、キーボード等の入力部１と、プログラム制御により動作する状態遷移計算手段２１と、関数タイプ判定手段２２と、入力状態生成手段２３と、を有する飽和特性探索部２と、ディスプレイや印刷装置等の出力部３と、を有して構成される。
【０１５０】
本実施形態の共通鍵ブロック暗号評価装置においては、入力状態が入力状態生成手段２３で自動生成される。入力状態生成手段２３の動作について図１２を用いて説明する。
【０１５１】
入力状態生成手段２３には入力されたパラメータのうち関係式が渡される。入力状態生成手段２３では、関係式からその数を計算する。
【０１５２】
変数ｓは入力状態を生成するためのものであり、関係式分の桁を持つ。変数ｓの初期値として、最右を１、残りを０に設定する（ステップＣ１）。
【０１５３】
０は状態Ｃを意味し、１は全数Ａを意味する。変数ｓの１の位置をＡ０、０の位置をＣとして入力状態を生成する（ステップＣ２）。図２の例では、式数は４なので、最初に生成される入力状態は、｛Ｃ，Ｃ，Ｃ，Ａ０｝である。
【０１５４】
生成した入力状態を出力し（ステップＣ３）、出力した入力状態が｛Ａ０，Ｃ，…，Ｃ｝である、すなわちｓの最左が１であるか否かを判断する（ステップＣ４）。ｓの最左が１でなければ、ｓを１だけ左巡回シフトする（ステップＣ５）。ｓが０００１であれば、００１０となり、次の状態を生成する。
【０１５５】
最終的にｓの最左が１となれば終了する。
【０１５６】
以上、本発明の好適な実施の形態により本発明を説明した。ここでは特定の具体例を示して本発明を説明したが、特許請求の範囲に定義された本発明の広範囲な趣旨および範囲から逸脱することなく、これら具体例に様々な修正および変更が可能である。
【産業上の利用可能性】
【０１５７】
入力データを２ｎ（ｎ≧２）以上に分割し、そのうちのｎのデータ各々を基本関数で鍵データと攪拌し、残りのｎのデータに排他的論理和する処理を繰り返し行い、更に基本関数は入力データを２つ以上に分割し、鍵の排他的論理和と非線形変換を順に行い、分割したそれぞれのデータが基本関数の出力全てに影響するように攪拌を行う拡散層で構成され、更に基本関数が複数種類で構成された共通鍵ブロック暗号方式を採用した暗号化装置に対して、飽和特性を探索する装置として利用可能である。
【図面の簡単な説明】
【０１５８】
【図１】全単射の例を示す図である。
【図２】飽和特性の状態遷移の一例を表す図である。
【図３】従来技術の関数ＦとＸＯＲによる状態遷移を表す図である。
【図４】図２の第５ラウンドの関数Ｆ１の入力を表した図である。
【図５】Ｇから出力される値が０回と偶数回のみの例を表す図である。
【図６】Ｇから出力される値が０回と偶数回と奇数回の例を表す図である。
【図７】本発明の第１の実施の形態の構成を示すブロック図である。
【図８】関数タイプ判定手段の動作を示すフローチャート図である。
【図９】状態遷移計算手段の動作を示すフローチャート図である。
【図１０】本発明の関数ＦとＸＯＲによる状態遷移を表す図である。
【図１１】本発明の第２の実施の形態の構成を示すブロック図である。
【図１２】入力状態生成手段の動作を示すフローチャート図である。
【符号の説明】
【０１５９】
１ 入力部
２ 飽和特性探索部
３ 出力部
４ 飽和特性探索部
２１ 状態遷移計算手段
２２ 関数タイプ判定手段
２３ 入力状態生成手段
３０ 関数Ｆ0
３１ 関数Ｆ1
３２ 第４ラウンドの中間データ
３３ 第５ラウンドの関数Ｆ1の出力データ
３４ 中間データ
【技術分野】
【０００１】
本発明は、共通鍵ブロック暗号に対する解読法である飽和攻撃で利用する飽和特性の探索を行う共通鍵ブロック暗号評価装置、共通鍵ブロック暗号評価方法及びプログラムに関する。
【背景技術】
【０００２】
共通鍵ブロック暗号の解読法の一つに飽和攻撃（Saturation attacks）がある。飽和攻撃は、選択平文攻撃に分類される。飽和攻撃が最初に提案され、適用された暗号は、Daemenらによって提案されたブロック暗号ＳＱＵＡＲＥであった。提案された当時は、ＳＱＵＡＲＥ攻撃と呼ばれていたが、近年は飽和攻撃と呼ばれている。
【０００３】
まず、飽和攻撃の前提知識として、全単射について説明する。
【０００４】
図１に示すように、ｆ：Ａ→Ｂという写像があったとき、集合Ａの任意の元が集合Ｂの任意の元と一対一に定義される写像を全単射という。
【０００５】
関数ｆを、ｎビット入出力の全単射な関数としたとき、入力値と出力値はそれぞれ、０〜２n−１のいずれかとなる。
【０００６】
ここで、０〜２n−１の全ての値のビット毎の排他的論理和（以降、ＸＯＲと記述し、“＋"の記号で表記する）による総和は、ゼロになるという特性がある。
【０００７】
例えばｎ＝２の場合、０〜２2−１（＝３）となり、ビットで表現すると、００（０）、０１（１）、１０（２）、１１（３）となる。
【０００８】
右側のビット位置をビット０とすると、ビット０の総和は、０＋１＋０＋１＝０、ビット１の総和は、０＋０＋１＋１＝０となる。
【０００９】
この特性は、ｎ（ｎ＞１）の値に依らず保たれる。以降、総和がゼロになることを“バランスする"、そのような状態を“バランス状態”という。
【００１０】
バランス状態には以下の４つの種類がある。
【００１１】
（１）．全通りの値が１回ずつ出現
前述したように、ｎビット幅で２n種類の値が１回ずつ出現している状態である。
【００１２】
（２）．一部の値、または全通りの値が偶数回ずつ出現
同じ値どうしのＸＯＲはゼロであるため、偶数個の同じ値をＸＯＲしてもバランスする。どのような値が出ていようとも値ごとの総和はゼロとなるので、全体でもゼロとなりバランスする。以降、これを“偶数バランス"と表現する。
【００１３】
（３）．全通りの値が全て奇数回ずつ出現
奇数回は（偶数回＋１回）であるため、全通りの値が出現していれば（全通りの値が偶数回＋全通りの値が１回）という状態といえるので、これもバランスする。以降、これを“奇数バランス"と表現する。
【００１４】
（４）．混合状態
偶数回と奇数回が入り混じったような、複雑なバランス状態である。以降、これを“混合バランス"と表現する。
【００１５】
これら４つとは別に、一種類の値のみが偶数回出現していても総和はバランスするが、これは“定数"として区別する。
【００１６】
上記（１）〜（３）の３つのバランス状態は、全単射な写像を何回繰り返してもバランス状態は保たれるが、混合バランスは値の絶妙な組み合わせでバランスしているので、次に全単射な写像による変換が行われるとバランス状態が保たれる保証はない。
【００１７】
次に、飽和攻撃の手順を簡単に説明する。
【００１８】
Ｒラウンドで構成される共通鍵ブロック暗号があり、いくらかの平文を与えたときに、Ｒ−１ラウンドの出力がバランスする特性があったとする。
【００１９】
このとき、第Ｒラウンドの鍵を仮定し、得られている暗号文全てについて遡り、第Ｒ−１ラウンドの出力データを得る。
【００２０】
遡ったデータの総和を計算し、バランスしなければ鍵の仮定が誤っていたとして正解の鍵候補から棄却できる。バランスした鍵が正解の鍵候補となる。候補が一つになればそれが正しい鍵と判断する。
【００２１】
このように飽和攻撃では、バランス状態が何ラウンド後まで存在するかが解読可能となるラウンド数に影響するため、バランス状態を正しく評価する必要がある。
【００２２】
図２は、共通鍵ブロック暗号の一例である。入力データをｘ0〜ｘ3の４つに分割して処理を行う一般化Ｆｅｉｓｔｅｌ構造である。
【００２３】
１ラウンドあたり、４つのデータのうちの２つが関数Ｆで変換され、残りの２つのデータにそれぞれＸＯＲされる。図中の＋記号を丸で囲った記号は、ＸＯＲを表す。
【００２４】
各データはそれぞれｍビットとする。関数Ｆ0と関数Ｆ1はｍビットのデータと鍵データとの攪拌を行う。入力されたｍビットのデータに対して、鍵データｋｅｙがＸＯＲされる。
【００２５】
Ｓ0とＳ1はそれぞれ一般的にＳ−ｂｏｘと呼ばれる非線形変換である。それぞれの入出力データサイズは、ｍ／２ビットとなる。
【００２６】
Ｍ0とＭ1はそれぞれ線形変換である。Ｍ0を例として説明すると、以下のような式で表される変換である。
【００２７】
【数１】
【００２８】
【数２】
【００２９】
ここで行われる演算は有限体上のものであり、結果が変数のサイズより大きくなることはない。ここでα0はＳ0の出力、α1はＳ1の出力である。β0とβ1を連結した値がＭ0の出力、つまり関数Ｆ0の出力である。
【００３０】
このように、Ｓ−ｂｏｘと拡散層によって構成されている構造をＳＰ型と呼ぶことにする。
【００３１】
なお、以降の説明では、鍵データの値は状態遷移には影響しないので、図を簡単にするために関数Ｆに入力される鍵データは省略してある。
【００３２】
図中の記号“Ａ"は全通りの値が現れることを、記号“Ｂ"はバランス状態であることを、記号“Ｃ"は定数であることを、そして記号“Ｕ"は状態が不明であることを表す。なお、Ｂがどのような状態によって構成されているかはここでは区別していない。
【００３３】
状態は、関数Ｆを通過したり、ＸＯＲされたりすると変化する。状態遷移は、図３に示すような表で表すことができる。
【００３４】
入力のＡは０〜２m−１までの２m通りのデータであり、Ｃは任意の定数である。つまり、入力の｛Ｃ、Ａ、Ｃ、Ｃ｝は２m通りのデータの集合を意味する。
【００３５】
第４ラウンドの出力データ３２は、ＡとＡのＸＯＲであり、その結果はＢとなる。関数Ｆ0と関数Ｆ1では、鍵データが作用するため、全数の値の出現順序は不明である。すなわち、Ｂがどのバランス状態にあるのかは知ることができない。
【００３６】
従って、これまではＢが関数Ｆを通過すると、状態はＵとして評価を行っていた。非特許文献１に記載される飽和攻撃評価でもそのように評価されている。
【非特許文献１】Sony Corporation、The 128-bit Blockcipher CLEFIA Security and Performance Evaluations Revision 1.0、インターネット＜URL:http://www.sony.co.jp/Products/clefia/technical/data/clefia-eval-1.0.pdf＞
【発明の開示】
【発明が解決しようとする課題】
【００３７】
しかしながら、従来における飽和特性探索法では、バランス状態の構成を区別できないため、バランス状態が非線形変換を通過すると、その出力の状態は不明として扱うしかなかった。
【００３８】
不明な状態は、飽和攻撃には利用できない特性なので、バランス状態を不明として扱うことがあれば、評価として不十分ということになる。
【００３９】
そこで本発明は、上記問題点に鑑みてなされたもので、飽和攻撃に対する評価指標である飽和特性の探索法について、関数Ｆを通過してもバランス状態が保持されるバランス状態を探索できる共通鍵ブロック暗号評価装置を提供することを目的とする。
【課題を解決するための手段】
【００４０】
上記課題を解決するため、本発明における共通鍵ブロック暗号評価装置は、データの分割数ｐと、データサイズｑと、が２ｐ≧ｑを満たすか否かを判定する関数タイプ判定手段と、入力状態を飽和特性の初期状態として、関係式を用いてラウンド処理後の飽和特性を計算する状態遷移計算手段と、を有し、状態遷移計算手段は、関係式に関数の項を含むと、データの全数が関数を通過した回数とバランス状態とを対応させた状態遷移表を参照してバランス状態を計算し、特殊なバランス状態になる可能性があると判定されたときに、関数タイプ判定手段による判定結果を参照して特殊なバランス状態となる構造であるか否かを判定することを特徴とする。
【００４１】
また、本発明における共通鍵ブロック暗号評価方法は、データの分割数ｐと、データサイズｑと、が２ｐ≧ｑを満たすか否かを判定する関数タイプ判定ステップと、関係式に関数の項を含むと、データの全数が関数を通過した回数とバランス状態とを対応させた状態遷移表を参照してバランス状態を計算し、特殊なバランス状態になる可能性があると判定されたときに、関数タイプ判定ステップによる判定結果を参照して特殊なバランス状態となる構造であるか否かを判定する状態遷移計算ステップと、を有することを特徴とする。
【００４２】
また、本発明におけるプログラムは、データの分割数ｐと、データサイズｑと、が２ｐ≧ｑを満たすか否かを判定する関数タイプ判定処理と、関係式に関数の項を含むと、データの全数が関数を通過した回数とバランス状態とを対応させた状態遷移表を参照してバランス状態を計算し、特殊なバランス状態になる可能性があると判定されたときに、関数タイプ判定処理による判定結果を参照して特殊なバランス状態となる構造であるか否かを判定する状態遷移計算処理と、をコンピュータに実行させることを特徴とする。
【発明の効果】
【００４３】
本発明により、評価を行う暗号アルゴリズムの関数Ｆの構造を考慮し、入力が関数Ｆを通過する回数を調べることによって、これまで検出することができなかった特殊なバランス状態を検出することができるようになる。また、特殊なバランス状態を検出することができるようになることによって、飽和攻撃に対する暗号アルゴリズムの安全性をより厳密に評価できるようになる。
【発明を実施するための最良の形態】
【００４４】
まず、関数Ｆにバランス状態が入力されてもその出力がバランス状態となる入力条件を示す。
【００４５】
図２を例に説明すると、入力ｘ1にＡ、その他をＣとしたときに、第５ラウンドの関数Ｆ1の入力となるデータ３２が後述する“特殊なバランス状態"のとき、第５ラウンドの関数Ｆ1の出力データ３３がバランスする。
【００４６】
Ｃは状態に影響を与えないので省略すると、データ３２は、関数Ｆ0３０と関数Ｆ1３１の出力をＸＯＲしたものといえるので、図４のように書き直すことができる。
【００４７】
データ３２をｙとすると、ｙはｘ1の式で表すことが出来る。ｘとｙは関数Ｆ0と関数Ｆ1の内部処理に合わせて、それぞれ、ｘ10とｘ11、ｙ0とｙ1に分割するとｙ0とｙ1は次式で表現できる。
【００４８】
【数３】
【００４９】
【数４】
【００５０】
数３を項の種類ごとにまとめて記述すると、次式のように書き換えることが出来る。ここで、Ｇ0とＧ1は非線形変換を意味する。
【００５１】
【数５】
【００５２】
このように、入力の各項が独立に変換されていることがわかる。このような状態において、Ｇ0とＧ1がバランスし、且つ、式における項の種類数をｐ、項のデータ幅をｑビットとしたとき、次式が成り立つならば、ｙ0は偶数バランス、もしくは奇数バランスのいずれかとなる。
【００５３】
【数６】
【００５４】
数５をみると、項の種類はｘ10とｘ11の２種類なので、種類数ｐは２となる。例えば、データ幅ｑが４（＝２・２）ビット以下ならば、数６は成り立つ。５ビット以上であれば成り立たないので、混合バランスとなる。
【００５５】
数５と数６の条件により、ｙ0が偶数バランスか奇数バランスのどちらかになることを図４を例に説明する。なお、ｙ1も同様に説明できる。
【００５６】
ここでは、ｘ1のサイズｍを８ビットとして説明することとするので、ｐ＝２、ｑ＝４の場合である。これは数６を満たすので、偶数バランス、または奇数バランスのどちらかとなる。
【００５７】
関数Ｆ0と関数Ｆ1の入力となるｘ1には全数が与えられるので、０〜２５５までの２５６（＝２8）通りデータが与えられる。
【００５８】
ｘ10とｘ11は、ｘ1を２分割したものになるので、Ｓ0とＳ1にはそれぞれ、０〜１５までの１６（＝２4）通りのデータが各々１６回与えられる。数５のＧ0とＧ1は他方がある値のときにそれぞれ独立にバランスすることは明らかである。
【００５９】
ここで、各Ｇの出力値の出現パターンを分析する。
【００６０】
ｘ10がある値のときに、ｘ11を全通り与えると、Ｇ1の出力値１６通りの出現回数としては、以下の３通りが考えられる。
【００６１】
（１）．出現回数が０回と偶数回のみ
（２）．出現回数が０回と奇数回のみ
（３）．出現回数が０回と偶数回と奇数回
【００６２】
図５が０回と偶数回のみの例である。実際には、ｘ10の１６通りの値ごとに表の出現回数が得られるので、出現回数の総和は図５の１６倍の出現回数となる。
【００６３】
図６は、出現回数が０回と偶数回と奇数回の例である。値が１、２、４、７の出現回数が奇数回となっている。
【００６４】
Ｇとしてバランスするので、出現回数が奇数回となる値でバランスすることになる。この例では、１＋２＋４＋７＝０となるので、バランスしている。
【００６５】
異なる２種類の値をＸＯＲしても０にはなりえないので、最低３種類必要となるが３種類の出現回数の合計は奇数回になるので、残りの出現回数も奇数回となってしまう。
【００６６】
一方、残りの出現回数は偶数回のものであるから、矛盾する。よって、奇数回となる値は４種類以上の偶数種類に限られる。こちらも実際には１６倍カウントされる。
【００６７】
Ｇの一方が０回と偶数回のみの場合、他方に関係なくｙ0は０回か偶数回、つまり偶数バランスとなる。
【００６８】
ここでは、Ｇ0とＧ1の両方が“０回と奇数回のみ"と“０回と偶数回と奇数回"の場合について説明する。
【００６９】
偶数回出現する値は、それのみでバランスするので奇数回に注目すると、“０回と偶数回と奇数回"は、“０回と奇数回のみ"と条件としては同じである。
【００７０】
Ｇ0で奇数回となった値をａ0、ａ1、ａ2、ａ3、Ｇ1で奇数回となった値をｂ0、ｂ1、ｂ2、ｂ3とする。先述したように、ａ、ｂそれぞれでバランスするので、
【００７１】
【数７】
【００７２】
【数８】
【００７３】
である。奇数回出現した値のＸＯＲの組合せとしては、
【００７４】
【数９】
【００７５】
の１６（＝４2）通り存在する。
【００７６】
ここで、（ａ0＋ｂ0）と（ａ1＋ｂ2）が等しいと仮定すると、
【００７７】
【数１０】
【００７８】
数１０は、交換則が成り立つので、次式が得られる。
【００７９】
【数１１】
【００８０】
更に数７、数８も同様に交換則が成り立つので、数１０、数１１から次式が得られる。数１０に数７を代入して
【００８１】
【数１２】
【００８２】
数１２を変形すると、
【００８３】
【数１３】
【００８４】
数１０に数８を代入すると、
【００８５】
【数１４】
【００８６】
数１４を変形すると、
【００８７】
【数１５】
【００８８】
数１２に数８を代入すると、
【００８９】
【数１６】
【００９０】
数１６を変形すると、
【００９１】
【数１７】
【００９２】
このように、Ｇ0で奇数回出力された任意の値ａiとａj、Ｇ1で奇数回出力された任意の値ｂm、ｂnについて、ａi＋ｂm＝ａj＋ｂnが成り立つならば、その他の組み合わせ全てについて互いに等しくなるものが存在する。このような状態のとき、ｙ0に出現する値の出現回数は全て偶数回となる。
【００９３】
逆に、ａi＋ｂm＝ａj＋ｂnとなるものが存在しない場合、ａxとｂyのＸＯＲの組み合わせ１６通り全てが異なる。すなわち、全通りの値（０〜１５）が全て奇数回出現することになる。
【００９４】
このとき、他に偶数回出現する値があったとしても、ｙ0には全通りの値が出現し、且つ、出現回数は全て奇数回となる。
【００９５】
ここで、数６で示す条件式について、詳細に説明する。
【００９６】
Ｇの種類、つまり項の種類になるが、これは関数Ｆの分割数ｐと等しくなる。分割した各データのサイズがｑビットのとき、値の種類としては、２q通りとなる。
【００９７】
全通りの値が出現するためには、各Ｇから出現される奇数回となった値の種類の組み合わせの数が、２q以上である必要がある。
【００９８】
前述のように、各Ｇから出現する値で出現回数が奇数回となるのは、最低４種類となる。すなわち、
【００９９】
【数１８】
【０１００】
であり、べき数に注目すると、数６が得られる。
【０１０１】
ところで、ｙ0とｙ1の両方が、数５と数６を満たすならば、ｙ0とｙ1は偶数バランスか奇数バランスのどちらかであるが、それらを区別することはできない。
【０１０２】
ここで、ｙ0とｙ1を結合したｍビットのｙでみると、混合バランスとなる可能性がある。
【０１０３】
混合バランスを関数Ｆで変換すると、出力の状態は不明となるが、ｙ0とｙ1がそれぞれ偶数バランスか奇数バランスのどちらかであるという状態であれば、関数Ｆで変換しても出力の状態はバランスする。
【０１０４】
関数ＦがＳＰ型であるならば、Ｓ−ｂｏｘの出力は入力のバランス状態が保たれ、拡散層もＸＯＲによって各入力データを攪拌するため、関数Ｆの出力はバランスする。
【０１０５】
このように、バランスしているデータを分割して見たときに、各々が偶数バランスか奇数バランスである状態を“特殊なバランス状態"と呼ぶことにする。
【０１０６】
次に、次式で示す例でみると、ｘ10とｘ11がそれぞれＳ0とＳ1で独立に変換されているが、それぞれをＸＯＲしたものがＳ2で変換されている。
【０１０７】
このような場合は、数５のように入力の項毎に括ることができないので、ｙ2は混合バランスの可能性がある。
【０１０８】
【数１９】
【０１０９】
図２のデータ３４は、第２ラウンドと第３ラウンドの２回の関数Ｆ0による変換が行われるため、数１９のようにＳ−ｂｏｘの入れ子の式となることは明らかである。
【０１１０】
このように、関数Ｆを２回以上通過したデータは、特殊なバランス状態になる保証はない。特殊なバランス状態となるためには、入力データが異なる２つの関数Ｆによってそれぞれ１回のみ変換されている必要がある。
【０１１１】
すなわち、関数Ｆがその内部でデータをｐ個に分割して処理を行い、それぞれのビット幅がｑであり、数６を満たす暗号アルゴリズムについて、入力ｘにＡを与え、Ｆ0（ｘ）とＦ1（ｘ）がＸＯＲされたデータは、特殊なバランス状態となる。
【０１１２】
次に、本発明の実施の形態について図面を参照して詳細に説明する。
【０１１３】
図７は、本発明の実施形態における共通鍵ブロック暗号評価装置の構成図である。本装置は、キーボード等の入力部１と、プログラム制御により動作する状態遷移計算手段２１と、関数タイプ判定手段２２とを有する飽和特性探索部２と、ディスプレイや印刷装置等の出力部３と、を有して構成される。
【０１１４】
入力部１より、評価パラメータとして“ラウンド数"、“関係式"、“入力状態"、“分割数"、そして“データサイズ"の５つが入力される。
【０１１５】
ラウンド数には評価を行うラウンド数を指定する。１０ラウンドまで評価を行うならば“１０"を指定する。
【０１１６】
関係式は、評価対象暗号アルゴリズムの構造を表すものであり、図２の暗号アルゴリズムの場合、関係式は次式で表される４式となる。
【０１１７】
【数２０】
【０１１８】
【数２１】
【０１１９】
【数２２】
【０１２０】
【数２３】
【０１２１】
入力状態には入力ｘ0〜ｘ3に対して、全数を与える変数と定数を与える変数を指定する。例えば、図２の例のようにｘ1に全数、その他には定数を与えるならば、｛Ｃ，Ａ０，Ｃ，Ｃ｝とする。Ａの添え字０は、初期状態であることを意味する。また、本評価装置では、全数は１箇所のみに与えるものとする。
【０１２２】
分割数は、評価対象暗号アルゴリズムの関数Ｆ内部のデータ分割数を指定する。図２の例では、関数Ｆ0と関数Ｆ1でそれぞれデータを２分割して内部処理を行っているので、“２"となる。
【０１２３】
データサイズは、分割されたデータのサイズをビットで表したものである。
【０１２４】
まず、関数タイプ判定手段２２について説明する。関数タイプ判定手段２２は、評価対象暗号アルゴリズムの関数Ｆの構造から特殊なバランス状態となり得るかどうかを判定する。
【０１２５】
次に、関数タイプ判定手段２２の動作について図８を参照して説明する。
【０１２６】
関数タイプ判定手段２２には、入力された５つのパラメータのうち、分割数とデータサイズの２つが渡され、分割数をｐ、データサイズをｑとしたとき、２ｐ≧ｑが成り立つか否かを判断する（ステップＡ１）。
【０１２７】
もし成り立つならば、フラグをＯＮに設定し（ステップＡ２）、成り立たないなら、フラグをＯＦＦに設定する（ステップＡ３）。なお、設定したフラグは、状態遷移計算手段２１へ渡される。
【０１２８】
次に、図９を参照して状態遷移計算手段２１の動作について説明する。
【０１２９】
状態遷移計算手段２１は、入力状態を飽和特性の初期状態として、関係式を用いてラウンド処理後の飽和特性を計算し、パラメータのラウンド数まで処理すると終了する。
【０１３０】
入力された関係式の数をｍ、ラウンド数をｎとする。入力されたパラメータの入力状態を状態の初期値としてＳ0,0〜Ｓ0,m-1に設定する（ステップＢ１）。図２の例では、入力状態が｛Ｃ，Ａ０，Ｃ，Ｃ｝とき、Ｓ0,0＝Ｃ、Ｓ0,1＝Ａ０、Ｓ0,2＝Ｃ、Ｓ0,3＝Ｃに設定される。
【０１３１】
現在の計算ラウンドを示すカウンタｉに１を設定する（ステップＢ２）。関係式の入力ｘの項に状態Ｓi-1を設定する（ステップＢ３）。計算式の番号を示すカウンタｊに０を設定する（ステップＢ４）。以降、第ｉラウンドの出力の状態Ｓiを計算するステップに入る。
【０１３２】
関係式ｙjがただの代入であるか否かを判断し（ステップＢ５）、代入であれば、代入元の状態をそのままＳi,jに設定する（ステップＢ６）。例えば、数２１や数２３が代入の例である。
【０１３３】
一方、関係式ｙjが代入ではなければ、関数Ｆの項があるか否かを判断し（ステップＢ７）、図１０に示す関数Ｆの状態遷移表を用いて関数Ｆの項を計算する（ステップＢ８）。例えば、数２０や数２２のＦ0（ｘ0）やＦ1（ｘ2）の項を計算する。
【０１３４】
関数Ｆの入力となる項の状態がＡの場合、添え字が１だけインクリメントされる。入力状態としてＡ０が関数Ｆの入力となったとき、その出力の状態はＡ１となり、もう一度入力されるとＡ２となる。つまり、Ａの添え字は関数Ｆを通過した回数を意味する。
【０１３５】
バランス状態は、ＢとＢ*の２種類で区別する。Ｂは、先に述べた４種類のバランス状態のいずれかであり、Ｂ*は、特殊なバランス状態である。Ｂは混合状態のバランスも含むため、関数Ｆの出力はＵとなるが、Ｂ*の出力はＢとなる点が異なる。
【０１３６】
関数Ｆの項を状態遷移させると、数２０と数２２は以下のようになる。
【０１３７】
【数２４】
【０１３８】
【数２５】
【０１３９】
上式のようにＸＯＲのみの式になるので、図１０のＸＯＲの状態遷移表を用いて状態の計算を行う。
【０１４０】
ここで、Ａ１とＡ１のＸＯＲのみ状態であるか否かを判断し、一意に決定しない（ステップＢ９）。Ａ１は、全数が関数Ｆを１回通過した状態を意味するので、Ａ１とＡ１のＸＯＲは特殊なバランス状態になる可能性がある。特殊なバランス状態になるかどうかは、関数Ｆの構造に依存する。関数タイプ判定手段２２で、関数Ｆの構造が調べられており、結果をフラグとして受け取っている。
【０１４１】
Ａ１とＡ１のＸＯＲのみ状態であれば、フラグがＯＮかＯＦＦかを判断する（ステップＢ１０）。フラグがＯＮであれば、特殊なバランス状態となる構造なので、状態Ｓi,jにはＢ*が設定される（ステップＢ１１）。
【０１４２】
一方、フラグがＯＦＦならば、特殊なバランス状態とはならない構造なので、状態Ｓi,jにはＢが設定される（ステップＢ１２）。
【０１４３】
一方、Ａ１とＡ１以外のＸＯＲの場合は、ＸＯＲの状態遷移表の通りの状態をＳi,jに設定する（ステップＢ１３）。
【０１４４】
関係式ｙjの状態計算を終了すると、カウンタｊがインクリメントされて（ステップＢ１４）、カウンタｊが式数ｍ未満であるか否かを判断し（ステップＢ１５）、カウンタｊが式数ｍ未満であれば、次の式の状態計算を同様に行う。一方、カウンタｊがｍまでカウントアップされると、第ｉラウンドの状態計算は終了する。
【０１４５】
ここで、第ｉラウンドの状態Ｓiが全てＵであるか否かを判断し（ステップＢ１６）、全てがＵであれば、以降のラウンドの状態もＵとなり評価を行う必要がないので、終了する。
【０１４６】
一方、状態ＳiにＵ以外の状態があれば、カウンタｉをインクリメントし（ステップＢ１７）、カウンタｉがパラメータで指定されたラウンド数ｎを超えれば、評価を終了する（ステップＢ１８）。達していないならば、次のラウンドの評価を同様に実施する。
【０１４７】
（他の実施の形態）
【０１４８】
次に、本発明の第２の実施の形態について図面を参照して詳細に説明する。
【０１４９】
図１１は、本発明の他の実施の形態における共通鍵ブロック暗号評価装置の構成図である。本装置は、キーボード等の入力部１と、プログラム制御により動作する状態遷移計算手段２１と、関数タイプ判定手段２２と、入力状態生成手段２３と、を有する飽和特性探索部２と、ディスプレイや印刷装置等の出力部３と、を有して構成される。
【０１５０】
本実施形態の共通鍵ブロック暗号評価装置においては、入力状態が入力状態生成手段２３で自動生成される。入力状態生成手段２３の動作について図１２を用いて説明する。
【０１５１】
入力状態生成手段２３には入力されたパラメータのうち関係式が渡される。入力状態生成手段２３では、関係式からその数を計算する。
【０１５２】
変数ｓは入力状態を生成するためのものであり、関係式分の桁を持つ。変数ｓの初期値として、最右を１、残りを０に設定する（ステップＣ１）。
【０１５３】
０は状態Ｃを意味し、１は全数Ａを意味する。変数ｓの１の位置をＡ０、０の位置をＣとして入力状態を生成する（ステップＣ２）。図２の例では、式数は４なので、最初に生成される入力状態は、｛Ｃ，Ｃ，Ｃ，Ａ０｝である。
【０１５４】
生成した入力状態を出力し（ステップＣ３）、出力した入力状態が｛Ａ０，Ｃ，…，Ｃ｝である、すなわちｓの最左が１であるか否かを判断する（ステップＣ４）。ｓの最左が１でなければ、ｓを１だけ左巡回シフトする（ステップＣ５）。ｓが０００１であれば、００１０となり、次の状態を生成する。
【０１５５】
最終的にｓの最左が１となれば終了する。
【０１５６】
以上、本発明の好適な実施の形態により本発明を説明した。ここでは特定の具体例を示して本発明を説明したが、特許請求の範囲に定義された本発明の広範囲な趣旨および範囲から逸脱することなく、これら具体例に様々な修正および変更が可能である。
【産業上の利用可能性】
【０１５７】
入力データを２ｎ（ｎ≧２）以上に分割し、そのうちのｎのデータ各々を基本関数で鍵データと攪拌し、残りのｎのデータに排他的論理和する処理を繰り返し行い、更に基本関数は入力データを２つ以上に分割し、鍵の排他的論理和と非線形変換を順に行い、分割したそれぞれのデータが基本関数の出力全てに影響するように攪拌を行う拡散層で構成され、更に基本関数が複数種類で構成された共通鍵ブロック暗号方式を採用した暗号化装置に対して、飽和特性を探索する装置として利用可能である。
【図面の簡単な説明】
【０１５８】
【図１】全単射の例を示す図である。
【図２】飽和特性の状態遷移の一例を表す図である。
【図３】従来技術の関数ＦとＸＯＲによる状態遷移を表す図である。
【図４】図２の第５ラウンドの関数Ｆ１の入力を表した図である。
【図５】Ｇから出力される値が０回と偶数回のみの例を表す図である。
【図６】Ｇから出力される値が０回と偶数回と奇数回の例を表す図である。
【図７】本発明の第１の実施の形態の構成を示すブロック図である。
【図８】関数タイプ判定手段の動作を示すフローチャート図である。
【図９】状態遷移計算手段の動作を示すフローチャート図である。
【図１０】本発明の関数ＦとＸＯＲによる状態遷移を表す図である。
【図１１】本発明の第２の実施の形態の構成を示すブロック図である。
【図１２】入力状態生成手段の動作を示すフローチャート図である。
【符号の説明】
【０１５９】
１ 入力部
２ 飽和特性探索部
３ 出力部
４ 飽和特性探索部
２１ 状態遷移計算手段
２２ 関数タイプ判定手段
２３ 入力状態生成手段
３０ 関数Ｆ0
３１ 関数Ｆ1
３２ 第４ラウンドの中間データ
３３ 第５ラウンドの関数Ｆ1の出力データ
３４ 中間データ
【特許請求の範囲】
【請求項１】
データの分割数ｐと、データサイズｑと、が
２ｐ≧ｑ
を満たすか否かを判定する関数タイプ判定手段と、
入力状態を飽和特性の初期状態として、関係式を用いてラウンド処理後の前記飽和特性を計算する状態遷移計算手段と、を有し、
前記状態遷移計算手段は、前記関係式に関数の項を含むと、前記データの全数が前記関数を通過した回数とバランス状態とを対応させた状態遷移表を参照してバランス状態を計算し、特殊なバランス状態になる可能性があると判定されたときに、前記関数タイプ判定手段による判定結果を参照して特殊なバランス状態となる構造であるか否かを判定することを特徴とする共通鍵ブロック暗号評価装置。
【請求項２】
前記状態遷移計算手段は、前記全数がそれぞれ前記関数を１回だけ通過したデータの排他的論理和であれば、特殊なバランス状態になる可能性があると判定することを特徴とする請求項１記載の共通鍵ブロック暗号評価装置。
【請求項３】
前記状態遷移計算手段は、バランス状態を特殊なバランス状態か否かの２種類で区別することを特徴とする請求項１又は２記載の共通鍵ブロック暗号評価装置。
【請求項４】
前記状態遷移計算手段により状態が全て不明と判定されると、以降のラウンドの状態も不明として、処理を終了することを特徴とする請求項１から３のいずれか１項に記載の共通鍵ブロック暗号評価装置。
【請求項５】
前記関係式から桁数を設定して、前記初期状態を生成する入力状態生成手段を有することを特徴とする請求項１から４のいずれか１項に記載の共通鍵ブロック暗号評価装置。
【請求項６】
データの分割数ｐと、データサイズｑと、が
２ｐ≧ｑ
を満たすか否かを判定する関数タイプ判定ステップと、
関係式に関数の項を含むと、前記データの全数が前記関数を通過した回数とバランス状態とを対応させた状態遷移表を参照してバランス状態を計算し、特殊なバランス状態になる可能性があると判定されたときに、前記関数タイプ判定ステップによる判定結果を参照して特殊なバランス状態となる構造であるか否かを判定する状態遷移計算ステップと、を有することを特徴とする共通鍵ブロック暗号評価方法。
【請求項７】
データの分割数ｐと、データサイズｑと、が
２ｐ≧ｑ
を満たすか否かを判定する関数タイプ判定処理と、
関係式に関数の項を含むと、前記データの全数が前記関数を通過した回数とバランス状態とを対応させた状態遷移表を参照してバランス状態を計算し、特殊なバランス状態になる可能性があると判定されたときに、前記関数タイプ判定処理による判定結果を参照して特殊なバランス状態となる構造であるか否かを判定する状態遷移計算処理と、をコンピュータに実行させるプログラム。
【請求項１】
データの分割数ｐと、データサイズｑと、が
２ｐ≧ｑ
を満たすか否かを判定する関数タイプ判定手段と、
入力状態を飽和特性の初期状態として、関係式を用いてラウンド処理後の前記飽和特性を計算する状態遷移計算手段と、を有し、
前記状態遷移計算手段は、前記関係式に関数の項を含むと、前記データの全数が前記関数を通過した回数とバランス状態とを対応させた状態遷移表を参照してバランス状態を計算し、特殊なバランス状態になる可能性があると判定されたときに、前記関数タイプ判定手段による判定結果を参照して特殊なバランス状態となる構造であるか否かを判定することを特徴とする共通鍵ブロック暗号評価装置。
【請求項２】
前記状態遷移計算手段は、前記全数がそれぞれ前記関数を１回だけ通過したデータの排他的論理和であれば、特殊なバランス状態になる可能性があると判定することを特徴とする請求項１記載の共通鍵ブロック暗号評価装置。
【請求項３】
前記状態遷移計算手段は、バランス状態を特殊なバランス状態か否かの２種類で区別することを特徴とする請求項１又は２記載の共通鍵ブロック暗号評価装置。
【請求項４】
前記状態遷移計算手段により状態が全て不明と判定されると、以降のラウンドの状態も不明として、処理を終了することを特徴とする請求項１から３のいずれか１項に記載の共通鍵ブロック暗号評価装置。
【請求項５】
前記関係式から桁数を設定して、前記初期状態を生成する入力状態生成手段を有することを特徴とする請求項１から４のいずれか１項に記載の共通鍵ブロック暗号評価装置。
【請求項６】
データの分割数ｐと、データサイズｑと、が
２ｐ≧ｑ
を満たすか否かを判定する関数タイプ判定ステップと、
関係式に関数の項を含むと、前記データの全数が前記関数を通過した回数とバランス状態とを対応させた状態遷移表を参照してバランス状態を計算し、特殊なバランス状態になる可能性があると判定されたときに、前記関数タイプ判定ステップによる判定結果を参照して特殊なバランス状態となる構造であるか否かを判定する状態遷移計算ステップと、を有することを特徴とする共通鍵ブロック暗号評価方法。
【請求項７】
データの分割数ｐと、データサイズｑと、が
２ｐ≧ｑ
を満たすか否かを判定する関数タイプ判定処理と、
関係式に関数の項を含むと、前記データの全数が前記関数を通過した回数とバランス状態とを対応させた状態遷移表を参照してバランス状態を計算し、特殊なバランス状態になる可能性があると判定されたときに、前記関数タイプ判定処理による判定結果を参照して特殊なバランス状態となる構造であるか否かを判定する状態遷移計算処理と、をコンピュータに実行させるプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【公開番号】特開２０１０−１３４２４７（Ｐ２０１０−１３４２４７Ａ）
【公開日】平成２２年６月１７日（２０１０．６．１７）
【国際特許分類】
【出願番号】特願２００８−３１０９５４（Ｐ２００８−３１０９５４）
【出願日】平成２０年１２月５日（２００８．１２．５）
【出願人】（０００００４２３７）日本電気株式会社 (19,353)
【出願人】（０００２４２６６６）北陸日本電気ソフトウェア株式会社 (11)
【Ｆターム（参考）】
【公開日】平成２２年６月１７日（２０１０．６．１７）
【国際特許分類】
【出願日】平成２０年１２月５日（２００８．１２．５）
【出願人】（０００００４２３７）日本電気株式会社 (19,353)
【出願人】（０００２４２６６６）北陸日本電気ソフトウェア株式会社 (11)
【Ｆターム（参考）】
[ Back to top ]