線形解読法

線形解読法（せんけいかいどくほう、英語: 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ビット目と等しいことを表している。

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

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

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

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

• 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 高速フーリエ変換を利用した線形解読法の改良

表 話 編 歴 ブロック暗号 アルゴリズム AES ARIA Blowfish Camellia CAST-128 CAST-256 DES DES-X 3DES FEAL IDEA KASUMI Lucifer MISTY1 MULTI2 RC2 RC5 RC6 SEED Serpent Square Twofish スキップジャック 設計 Feistel構造 S-box SPN構造 攻撃 （暗号解読） 総当たり攻撃 レインボーテーブル 中間一致攻撃 線形解読法 差分解読法 切詰 高階 関連鍵攻撃 標準化 AES公募 CRYPTREC NESSIE NSA Suite B（英語版） CNSA 用語 初期化ベクトル 暗号利用モード カテゴリ 表 話 編 歴 ストリーム暗号 アルゴリズム A5/1 KCipher-2 MUGI RC4 Salsa20 （暗号利用モード） 理論 シフトレジスタ 線形帰還シフトレジスタ 初期化ベクトル 攻撃 総当たり攻撃 線形解読法 差分解読法 関連鍵攻撃 相関攻撃 標準化 CRYPTREC カテゴリ

表 話 編 歴 暗号 暗号史 暗号解読 Cryptography portal en:Outline of cryptography 共通鍵暗号 ブロック暗号 ストリーム暗号 暗号利用モード 公開鍵暗号 暗号学的ハッシュ関数 メッセージ認証コード 認証付き暗号 乱数生成器 ステガノグラフィー

カテゴリ