DES-X

一般
設計者	ロナルド・リベスト
初版発行日	1984年
派生元	DES
暗号詳細
鍵長	184ビット
ブロック長	64ビット
構造	Feistel構造
ラウンド数	16

DES-X (DESX) はDES (Data Encryption Standard) から派生したブロック暗号の一種で、key whitening と呼ばれる技法を使って総当り攻撃への耐性を強化している。

元々のDESのアルゴリズムは1976年に策定されたもので、鍵長が56ビットであり、鍵のとりうる値は 2⁵⁶ 個ある。このため、例えばアメリカ国家安全保障局 (NSA) などの政府機関が総当り攻撃を実行できるかもしれないという指摘があった。DESのアルゴリズムを実質的には変更せず、鍵長だけを大きくしたのがDES-Xで、1984年5月にロナルド・リベストが提案した。

このアルゴリズムは、1980年代末以降、RSAセキュリティのBSAFE暗号ライブラリに含まれている。

DES-Xは、追加の64ビットの鍵 (K₁) を平文にXORで適用してから、DESの暗号化を行い、さらに別の64ビットの鍵 (K₂) を暗号文にXORで適用する。

${\mbox{DES-X}}(M)=K_{2}\oplus {\mbox{DES}}_{K}(M\oplus K_{1})$

したがって鍵長は 56 + 2 × 64 = 184 ビットに強化されている。

しかし、実効鍵長（セキュリティ）は 56+64-1-lb(M) = 119 - lb(M) = ~119 ビットにしかならない。ここで M は、解読しようとする者が入手できる平文と暗号文のペアの数、lb は2を底とする対数である（このため、実装によっては K₁ と K から一方向関数で K₂ を生成することもある）。

DES-XはDESに比較して差分解読法や線形解読法に対しても強くなっているが、その度合いは総当り攻撃の場合よりも小さい。差分解読法の場合、2⁶¹ 個の選択平文を必要とすると見積もられている（DESの場合は 2⁴⁷）。線形解読法では 2⁶⁰ の既知平文を必要とする（DESの場合は 2⁴³）。なお、DESの場合（あるいはブロック長が64ビットのブロック暗号全般では）、2⁶⁴ の平文（選択か既知かは問わない）があれば、完全に破ることができる。

関連項目

• 中間一致攻撃
• トリプルDES

参考文献

• Joe Kilian and Phillip Rogaway, How to protect DES against exhaustive key search (PostScript), Advances in Cryptology - Crypto '96, Springer-Verlag (1996), pp. 252–267.
• P. Rogaway, The security of DESX (PostScript), CryptoBytes 2(2) (Summer 1996).

外部リンク

• RSA FAQ Entry