線型方程式の作成
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2021/12/29 23:13 UTC 版)
線形解読法では、二進数の排他的論理和(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)。
※この「線型方程式の作成」の解説は、「線形解読法」の解説の一部です。
「線型方程式の作成」を含む「線形解読法」の記事については、「線形解読法」の概要を参照ください。
- 線型方程式の作成のページへのリンク