書記が数学やるだけ#876 ブロック暗号の解読

ブロック暗号の解読についていくつか見ていく。

問題

説明

DES暗号には相補性（平文と鍵をビット反転すると暗号文もビット反転したものになる）があり，これにより総当たり攻撃の探索空間が半減する。また，鍵の中には弱鍵（同じ鍵で二回暗号化すると元の平文に戻る）や半弱鍵（鍵K1で暗号化したものをK2で復号すると元に戻る鍵の組み合わせ）が含まれている。

DESの解読法として，置換ネットワークを通してどのように差分が波及するかを追跡する差分解読法や，暗号化変換の線形近似式を発見することで解読する線形解読法などが知られている。

解答

トリプルDESにはいくつかの種類があるが，重要なのは鍵が異なるときに安全性が向上するかである。ここでもしDESが群を形成していた場合，3DESは単なるDESの1回適用と同じものに還元される可能性があるが，DESが群ではないため，3DESを適用すると元のDESに還元されることなく安全性が向上する。

相補性の証明は，DESの各手順に対しビット反転を代入した結果を考えれば良い。

弱鍵の証明は具体的な計算で示せる。

差分解読法の計算について，Sボックスに対し差分（ΔX=0110）を解析すると「3: 4回，5: 3回，12: 2回，15: 2回，14: 2回，13: 2回」というように偏りが出ることから，鍵の候補を絞ることができる。

線形解読法の計算について，平文の1ビット目と3ビット目および暗号文の2ビット目のXORは「0が4個，1が9個」であり偏りがあることから，線形関係の説明に役立つ。

本記事のもくじはこちら：