情報セキュリティにおける線形解読法とは何ですか？

線形解読法は既知の平文攻撃であり、攻撃者は平文、暗号文、隠し鍵のパリティビット間の線形近似と呼ばれる確率的線形関係を研究します。

このアプローチでは、攻撃者は既知のプレーンテキストと暗号文のパリティビットを計算することにより、隠しキーのパリティビットの確率の高い近似値を取得します。攻撃者は、補助的な手法を含むいくつかのアプローチを使用して、攻撃を拡張し、秘密鍵の余分なビットを発見することができます。

線形解読法と差分解読法は、ブロック暗号に対して一般的に使用される攻撃です。線形解読法は、松井充が最初にFEAL暗号に使用したことによって最初に発明されました。

線形解読法には一般に2つの部分があります。最初の部分は、平文、暗号文、およびバイアスの大きいキービットに関連付けられた線形方程式を作成することです。それは、保持の確率が00r1に可能な限り近いものです。

2番目の部分は、キービットを駆動するために既知の平文と暗号文のペアと組み合わせてこれらの一次方程式を必要とすることです。

線形解読法は、線形近似を使用して、暗号化手順の非線形プロセスをモデル化します。大量の既知平文への近似を使用して、特定の確率で正しい1つのキービットを最終的に見つけることができます。このアプローチの暗号固有の改良により、複数のキービットを見つけることができます。

線形解読法攻撃は、データ暗号化標準で実装された変換を定義するための線形近似の発見に基づいています。このアプローチでは、差分解読法のために選択された247の平文とは異なり、243の既知の平文が与えられた場合にデータ暗号化標準キーを検出できます。

選択された平文の代わりに既知の平文を取得する方が簡単であり、データ暗号化標準への攻撃として線形解読法を実行不可能にする可能性があるため、これでも小さな進歩です。

線形解読法の目的は、次の形式の効果的な線形方程式を発見することです-

$$ \ mathrm {P \ left [\ alpha 1、\：\ alpha 2 \：... \ alpha a \ right] \ oplus \、C \ left [\ beta 1、\：\ beta 2 \：.. 。\betab \ right] =K \ left [\ gamma 1、\、\ gamma 2 \：... \ gamma c \ right]} $$

（ここで、x =0または1;1≤a、b≤n、1≤c≤mであり、α、β、およびγの項は固定された特定のビット位置を表します）確率p≠0.5で影響します。

pが0.5から離れるほど、方程式はより効果的になります。将来の関連付けが決定されるため、プロセスは、多数の平文と暗号文のペアについて、前の式の左辺の結果を評価することです。結果が半分以上の時間0である場合、K [γ1、γ2...γc]=0と仮定します。

ほとんどの場合1である場合、K [γ1、γ2...γc] =1と仮定します。これにより、キービットの線形方程式が得られます。キービットを解決できるように、このような関係をさらに受信しようとすることができます。この論文では一次方程式を使って管理しているため、問題は一度に1ラウンドの暗号にアプローチでき、結果が結び付けられます。