DAY 8- 《区块密码1》DES(2)- 密钥生成及安全性

これはです。

子密钥生成

上一篇说到，在 DES 加密过程中的第二步，需要重复进行16次，
而每一次都会使用到一个子密钥，因此总供需要16个子密钥。
子密钥有48位元，由56位元的原始密钥产生。

现在要先来澄清一件事情。

输入密钥时需要输入64位元，而真正会使用到的只有56位元，剩下的8位元作为奇偶校验。
我们先将64位元分成8组，每组8位元。每一组的最後一个位元作为奇偶校验（parity bit）。
如果左边7个位元有奇数/偶数个1，那奇偶校验元就是1/0 。

输入 DES 的密钥会经过以下这张表的转换成为密钥，
而这经过这张表的转换之後，校验元将会被去除。

所以我们现在有一个56位元的密钥。
接着这个密钥会进入下一轮（PC-2）。

在这一轮总共会进行16回合，
每一回合都先将56位元分成左右两半，
左右两半都会向左移动1（1,2,9,16回合）或2位元。
移动过後再经过下表的转换成为子密钥。

安全性

暴力破解

暴力破解就是试过每一种密钥可能的破解方式。
以 DES 来看，因为其密钥只有56位元，因此所有的密钥可能只有 $2^{56}$ 种。
这是其最大的缺点，
如此短的密钥让现代电脑技术可以用很短的时间破解。
甚至在西元1999年就有机器可以在一天之内破解 DES （DES challenge 3）。

分析攻击

DES 在实务上可以抵抗分析攻击。（我们之後再来看什麽是分析攻击。）
而事实上分析攻击在 DES 发布後才被发现。

3DES（Triple DES）

3DES顾名思义就是做3次DES，
比较特别的是，我们在做第二次DES的时候用的是解密，而不是加密。

$y = DES_{k_3}(DES^{-1}_{k_2}(DES_{k_1}(x)))$

注意到每一次使用的密钥是不一样的，所以总密钥长度是168位元。
不过其有效的密钥长度只有112位元（如果使用meet-in-the-middle attack）。

Meet-in-the-middle attack

一种用空间代替时间的攻击方法，什麽意思呢？
假设我们今天用的不是3DES，我们用2DES。
照理来说，2DES会有 $2^{112}$ 的安全性（因为有两把不同的k），但其实他只有 $2^{57}$ 的安全性。
2DES 加密两次，加密第一次後的讯息我们称为中间值好了。
明文到中间值的密钥叫做k1，另一个叫做k2。