線形解読法
線形解読法では、二進数の排他的論理和(XOR)で作られた2つの式が等しくなることを線形方程式で表す。例えば以下の等式は、平文の1ビット目と3ビット目、および暗号文の1ビット目の排他的論理和が、鍵の2ビット目と等しいことを表している。
P 1 ⊕ P 3 ⊕ C 1 = K 2 . {\displaystyle P_{1}\oplus P_{3}\oplus C_{1}=K_{2}.}
理想的な暗号ならば、平文・暗号文・鍵から作られたいかなる線形方程式においても、それが成立する確率は1/2となる。なお線形解読法における等式は成立・不成立の確率が変わるため、より正確に線形近似式と呼ばれる。
線形近似式の作成手順は、暗号によってそれぞれ異なる。最も基本的なタイプであるSPN構造のブロック暗号においては、暗号処理において唯一非線形な部分であるSボックスの解析に主眼が置かれる。Sボックスが十分に小さければ、Sボックスの入力と出力に対してすべての線形方程式を列挙し、バイアスを算出して最良の候補を選択することも可能である。Sボックスに対する線形近似式を作成したら、暗号中の他の処理(permutationとkey mixing)と結合され、暗号処理全体に対する線形近似式が構成される。この結合にはPiling-up lemmaが利用できる。また、線形近似式を繰り返し改善していく手法もある(Matsui, 1994)。
線形解読法は2つの操作で構成されている。一つ目は、平文・暗号文・鍵の3つを使った線形方程式の組み立てである。この際、線型方程式は偏差ができるだけ大きくなるようにする。すなわち、変数の取りうる値全てに対して、等式の成立する確率ができるだけ1/2から遠く、1または0に近くなるようにする。二つ目は、既知の平文と暗号文のペアに対する作成した線形方程式の適用であり、これにより鍵の各ビットを導出する。