鍵の各ビットの導出
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/12/29 23:13 UTC 版)
以下のような鍵のビットの導出があるとき、 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から大きく偏ると考えられるためである。つまりここでは、成立する確率そのものよりも、確率の偏差のほうが重要である。 以上の手続きを複数の線形近似式を使って繰り返し実行し、鍵のビットの値を推測していく。鍵中の未知のビットが総当たり攻撃で攻撃できる程度に少なくなるまで繰り返すことで攻撃が行える。
※この「鍵の各ビットの導出」の解説は、「線形解読法」の解説の一部です。
「鍵の各ビットの導出」を含む「線形解読法」の記事については、「線形解読法」の概要を参照ください。
- 鍵の各ビットの導出のページへのリンク
