線形解読法
線形解読法(せんけいかいどくほう、英語: Linear cryptanalysis)とは、暗号化変換の線形近似式を発見することを基本とした一般化された暗号解読手法の一つである。 この攻撃は、ブロック暗号およびストリーム暗号に適用される。 線形解読法は、ブロック暗号にもっとも適用される攻撃法の二つのうちの一つである(もうひとつは、差分解読法である)。
以下のような鍵のビットの導出があるとき、
P i 1 ⊕ P i 2 ⊕ ⋯ ⊕ C j 1 ⊕ C j 2 ⊕ ⋯ = K k 1 ⊕ K k 2 ⊕ ⋯ {\displaystyle P_{i_{1}}\oplus P_{i_{2}}\oplus \cdots \oplus C_{j_{1}}\oplus C_{j_{2}}\oplus \cdots =K_{k_{1}}\oplus K_{k_{2}}\oplus \cdots }
既知の平文と暗号文のペアに対してアルゴリズム(松井のアルゴリズム2)を適用することで、式の右辺にある鍵の各ビットの値を推測できる。
右辺にある鍵の各ビット(部分鍵(partial key)と呼ばれる)の集合それぞれに対して、既知の平文と暗号文のペアに対して何回値が真になったかをカウントし、この回数をTとする。平文と暗号文のペアの数を2で割った数と、このTとの絶対差が最大になったものが、それらの鍵の各ビットに対して最もそれらしい値と推測される。これは、正しい部分鍵であれば線形近似式の成立する確率が1/2から大きく偏ると考えられるためである。つまりここでは、成立する確率そのものよりも、確率の偏差のほうが重要である。
以上の手続きを複数の線形近似式を使って繰り返し実行し、鍵のビットの値を推測していく。鍵中の未知のビットが総当たり攻撃で攻撃できる程度に少なくなるまで繰り返すことで攻撃が行える。