線形解読法
線形解読法（せんけいかいどくほう、英語: Linear cryptanalysis）とは、暗号化変換の線形近似式を発見することを基本とした一般化された暗号解読手法の一つである。 この攻撃は、ブロック暗号およびストリーム暗号に適用される。 線形解読法は、ブロック暗号にもっとも適用される攻撃法の二つのうちの一つである（もうひとつは、差分解読法である）。
概要
松井充によって発見され、最初にFEALに適用された(Matsui and Yamagishi, 1992)。 次に松井はDESに対する攻撃を発表した。DESに対する攻撃は、243の既知平文を必要とし、一般的には現実的ではない。しかし、DESの解読実験に成功し、これはDESを実験的に解読した初めての一般的に公開された報告である(Matsui, 1993; 1994)。
複数の線形近似式を用いる手法や、非線形関数を用いる手法など、いくつかの改良が提案されている。新しい暗号の設計では、差分解読攻撃法と共に、線形解読法に対する耐性の根拠が必要とされている。
解読法の内容
線形解読法は2つの操作で構成されている。一つ目は、平文・暗号文・鍵の3つを使った線形方程式の組み立てである。この際、線型方程式は偏差ができるだけ大きくなるようにする。すなわち、変数の取りうる値全てに対して、等式の成立する確率ができるだけ1/2から遠く、1または0に近くなるようにする。二つ目は、既知の平文と暗号文のペアに対する作成した線形方程式の適用であり、これにより鍵の各ビットを導出する。
線型方程式の作成
線形解読法では、二進数の排他的論理和(XOR)で作られた2つの式が等しくなることを線形方程式で表す。例えば以下の等式は、平文の1ビット目と3ビット目、および暗号文の1ビット目の排他的論理和が、鍵の2ビット目と等しいことを表している。
カテゴリアルゴリズム 理論 攻撃 標準化
- Linear cryptanalysisのページへのリンク
