情報セキュリティにおける線形解読法とは？仕組みと2段階の手順を解説

線形解読法（Linear Cryptanalysis）は既知平文攻撃の一種です。攻撃者は、平文・暗号文・隠された秘密鍵の各パリティビット間に存在する確率的な線形関係（「線形近似」と呼ばれます）を分析します。

この手法では、攻撃者は既知の平文と暗号文のパリティビットを計算することで、秘密鍵のパリティビットに関する高確率の近似値を取得します。さらに、補助技術をはじめとする複数の手法を組み合わせることで、攻撃を拡張し、秘密鍵の追加のビットまで発見できる場合があります。

ブロック暗号に対する代表的な攻撃手法

線形解読法は、差分解読法（Differential Cryptanalysis）と並んで、ブロック暗号に対して最も広く用いられる攻撃手法のひとつです。この技法は日本の研究者である松井充（Mitsuru Matsui）氏によって初めて考案され、当初はFEAL暗号に対して適用されました。

線形解読法の2つの段階

線形解読法は、一般的に次の2つの部分から構成されます。

第1段階：高バイアスの線形方程式を作成する

まず、平文・暗号文・鍵ビットを関連付ける線形方程式を作成します。ここで重要なのは「バイアス（偏り）」が大きいこと、すなわち方程式が成立する確率が0または1にできる限り近いことです。

第2段階：既知の平文・暗号文ペアで鍵ビットを導出する

次に、これらの線形方程式を既知の平文・暗号文ペアと組み合わせて使用し、鍵ビットを導出します。

非線形処理を線形近似でモデル化

線形解読法は、暗号化プロセス内の非線形処理を線形近似によってモデル化します。大量の既知平文にこの近似を適用することで、最終的に特定の確率で正しい鍵ビットを1つ見つけ出すことができます。さらに、暗号ごとの特性に応じた改良を加えることで、複数の鍵ビットを同時に特定することも可能です。

DES（データ暗号化標準）への適用

線形解読攻撃は、Data Encryption Standard（DES）に実装された変換を記述する線形近似を発見することに基づいています。この手法によれば、約2⁴³個の既知平文からDESの鍵を導出できます。これは、差分解読法に必要とされる2⁴⁷個の選択平文と対照的です。

既知平文は選択平文よりも入手が簡単であるため、これは一種の進歩と言えます。しかし、依然として膨大な量の既知平文が必要となるため、当時の線形解読法はDESに対する現実的な攻撃としては実行困難なものでした。

目的となる線形方程式の形式

線形解読法の目的は、次の形式の有効な線形方程式を見つけることにあります。

P[α₁, α₂ … α_a] ⊕ C[β₁, β₂ … β_b] = K[γ₁, γ₂ … γ_c]

ここで、x = 0 または 1、1 ≤ a, b ≤ n、1 ≤ c ≤ m であり、α・β・γ の各項は固定された特定のビット位置を表します。この式は確率 p ≠ 0.5 で成立し、p が 0.5 から遠ざかるほど、方程式はより有効になります。

鍵ビットの推定手順

有望な関係式が決まったら、次の工程として、多数の平文・暗号文ペアについて上記方程式の左辺の結果を評価します。

結果が半分以上の割合で 0 になれば、K[γ₁, γ₂ … γ_c] = 0 と仮定します。逆に、大部分の場合で 1 となれば、K[γ₁, γ₂ … γ_c] = 1 と仮定します。これにより、鍵ビットに関する1本の線形方程式が得られます。

このような関係式をさらに多く収集すれば、連立方程式として鍵ビットを解き明かすことができます。線形方程式を扱う这一般、問題には暗号の1ラウンドずつ順にアプローチし、それぞれの結果をつなぎ合わせていくことが可能です。