線形解読法

線形解読法（せんけいかいどくほう、英語: Linear cryptanalysis）とは、暗号化変換の線形近似式を発見することを基本とした一般化された暗号解読手法の一つである。 この攻撃は、ブロック暗号およびストリーム暗号に適用される。 線形解読法は、ブロック暗号にもっとも適用される攻撃法の二つのうちの一つである（もうひとつは、差分解読法である）。

概要

松井充によって発見され、最初にFEALに適用された(Matsui and Yamagishi, 1992)。 次に松井はDESに対する攻撃を発表した。DESに対する攻撃は、2⁴³の既知平文を必要とし、一般的には現実的ではない。しかし、DESの解読実験に成功し、これはDESを実験的に解読した初めての一般的に公開された報告である(Matsui, 1993; 1994)。

複数の線形近似式を用いる手法や、非線形関数を用いる手法など、いくつかの改良が提案されている。新しい暗号の設計では、差分解読攻撃法と共に、線形解読法に対する耐性の根拠が必要とされている。

解読法の内容

線形解読法は2つの操作で構成されている。一つ目は、平文・暗号文・鍵の3つを使った線形方程式の組み立てである。この際、線型方程式は偏差ができるだけ大きくなるようにする。すなわち、変数の取りうる値全てに対して、等式の成立する確率ができるだけ1/2から遠く、1または0に近くなるようにする。二つ目は、既知の平文と暗号文のペアに対する作成した線形方程式の適用であり、これにより鍵の各ビットを導出する。

線型方程式の作成

線形解読法では、二進数の排他的論理和(XOR)で作られた2つの式が等しくなることを線形方程式で表す。例えば以下の等式は、平文の1ビット目と3ビット目、および暗号文の1ビット目の排他的論理和が、鍵の2ビット目と等しいことを表している。

$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）。

鍵の各ビットの導出

以下のような鍵のビットの導出があるとき、

$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から大きく偏ると考えられるためである。つまりここでは、成立する確率そのものよりも、確率の偏差のほうが重要である。

以上の手続きを複数の線形近似式を使って繰り返し実行し、鍵のビットの値を推測していく。鍵中の未知のビットが総当たり攻撃で攻撃できる程度に少なくなるまで繰り返すことで攻撃が行える。

参考文献

• Matsui, M. and Yamagishi, A. "A new method for known plaintext attack of FEAL cipher". Advances in Cryptology - EUROCRYPT 1992.
• Matsui, M. "Linear cryptanalysis method for DES cipher" (PDF). Advances in Cryptology - EUROCRYPT 1993. 2007年2月22日閲覧。
• Matsui, M. "The first experimental cryptanalysis of the data encryption standard". Advances in Cryptology - CRYPTO 1994.

関連項目

• Piling-up lemma
• 差分解読法

外部リンク

• A tutorial on linear (and differential) cryptanalysis of block ciphers
• Linear cryptanalysis: a literature survey
• Improving the Time Complexity of Matsui's Linear Cryptanalysis 高速フーリエ変換を利用した線形解読法の改良