千葉大学 融合理工学府 数学情報科学専攻 数学・情報数理学コース 2018年8月実施 専門 B10

标签：

• Meet-in-the-Middle-Attack

Author

祭音Myyura (co-authored with GPT 6 Astra)

Description

鍵長 $k$、ブロック長 $n$ の暗号化関数 $E:\{0,1\}^k\times\{0,1\}^n\to\{0,1\}^n$ に対し、鍵長 $2k$ の二重暗号化を

$$F(K_1\Vert K_2,M)=E(K_2,E(K_1,M))$$

と定める。平文・暗号文の二組 $(m_1,c_1),(m_2,c_2)$ を得た場合、元の暗号が安全でも二重暗号には鍵の全数探索より少ない計算量の攻撃があることを示せ。ここで安全とは、鍵の全数探索未満の解読アルゴリズムが知られていないことをいう。

题目描述

将密钥长度为 $k$ 的分组密码用两个独立密钥串联，形成长度 $2k$ 的密钥。已知两组明文与密文，说明中间相遇攻击如何使二重加密的攻击复杂度低于直接穷举全部双密钥。

Kai

$D(K,\cdot)=E(K,\cdot)^{-1}$ とする。中間一致攻撃を行う。

1. すべての $K_1\in\{0,1\}^k$ に対して組 $v(K_1)=(E(K_1,m_1),E(K_1,m_2))$ を計算し、鍵とともに表へ保存する。
2. すべての $K_2$ に対して $w(K_2)=(D(K_2,c_1),D(K_2,c_2))$ を計算し、表の一致項を検索する。
3. $v(K_1)=w(K_2)$ となる組を鍵候補として取り出す。真の鍵は必ず含まれ、取り出した候補は二組の既知データを満たす。

必要な暗号化・復号回数は $4\cdot2^k$、保存量は $O(2^k)$ 件である。ハッシュ表なら検索は平均 $O(2^k)$、整列と二分探索でも $O(k2^k)$ 回の比較で済む。これは $2^{2k}$ 組を直接調べる全数探索より小さい。

通常の独立なブロック暗号として見積もると、誤った鍵組が二組とも一致する確率はおよそ $2^{-2n}$ であり、誤候補数の期待値はおよそ $2^{2k-2n}$。従って二重化しても $2k$ ビットの全数探索に相当する安全性は得られない。二組だけで鍵が一意になるとは限らず、複数候補が残れば追加の既知データで照合する。