線形解読法

線形解読法

線形解読法（せんけいかいどくほう）は、暗号化されたデータに対して行う攻撃手法の一つであり、特にブロック暗号やストリーム暗号に応用されています。基本的なアプローチは、暗号化変換の様々な線形近似を使用して特定の鍵のビットを推測することにあります。この手法は松井充によって発見され、初めてFEAL暗号に適用されました。その後、DES暗号に対する攻撃も行われ、243個の既知の平文を必要とするものの、実験的な解読に成功し、暗号の弱点を明らかにしました。

線形解読法の基本原理

線形解読法は主に2つの操作から成り立っています。1つ目は、平文、暗号文、そして鍵を用いた線形方程式の作成です。この際、方程式が成立する確率をできるだけ1/2から遠ざけ、0または1に近づけるように努めます。2つ目の操作として、既知の平文とその対応する暗号文の組に対し、作成した線形方程式を適用することで、ターゲットとしている鍵のビットを導出します。これにより、推測された鍵のビットが次第に明らかになっていきます。

線型方程式の制作方法

線形解読法では、平文と暗号文のビットの排他的論理和（XOR）を利用して等式を形成します。例えば、平文の特定のビットと暗号文のビットとの間に排他的論理和が成立することを示すことができます。理想的な暗号であれば、任意の線形方程式の成立確率は1/2ですが、線形解読法ではその確率が変動するため、より精密には「線形近似式」として表現されます。これらの近似式は暗号ごとに異なる作成手順を必要とし、特にSPN構造のブロック暗号においてはSボックスの特性を利用して解析が行われます。

鍵ビットの導出手順

鍵の各ビットを推測するためには、特定のアルゴリズム、例えば松井のアルゴリズム2が用いられます。このアルゴリズムでは、既知の平文及び暗号文の組を用い、成立する確率が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”. Advances in Cryptology - EUROCRYPT 1993.
• - 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

もう一度検索