DES-Xのソースを表示

{{Infobox Encryption method
| name          = 
| image         = 
| caption       = 
| designers     = [[ロナルド・リベスト]]
| publish date  = 1984年
| derived from  = [[Data Encryption Standard|DES]]
| derived to    = 
| key size      = 184ビット
| block size    = 64ビット
| structure     = Feistel構造
| rounds        = 16
| cryptanalysis = 
}}

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

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

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

DES-Xは、追加の64ビットの鍵 (K<sub>1</sub>) を[[平文]]に[[排他的論理和|XOR]]で適用してから、DESの暗号化を行い、さらに別の64ビットの鍵 (K<sub>2</sub>) を暗号文にXORで適用する。

<math>\mbox{DES-X}(M) = K_2 \oplus \mbox{DES}_K(M \oplus K_1)</math>

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

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

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

== 関連項目 ==
* [[中間一致攻撃]]
* [[トリプルDES]]

== 参考文献 ==
* Joe Kilian and Phillip Rogaway, [http://wwwcsif.cs.ucdavis.edu/~rogaway/papers/desx.ps How to protect DES against exhaustive key search] (PostScript), Advances in Cryptology - Crypto '96, Springer-Verlag (1996), pp. 252–267.
* P. Rogaway, [http://www.cs.ucdavis.edu/~rogaway/papers/cryptobytes.ps The security of DESX] (PostScript), CryptoBytes '''2'''(2) (Summer 1996).

== 外部リンク ==
* [http://www.rsasecurity.com/rsalabs/node.asp?id=2232 RSA FAQ Entry]

{{cryptography navbox|block}}