第二十二讲、第二十三讲 DES的安全性 3DES

1 DES的弱密钥

关于DES密钥

DES的弱密钥

2 DES的密钥长度的争论

• DES算法正式公开发表以后，引起了一场激烈的争论

• 对DES安全性批评意见中，较为一致的看法是DES的密钥短了些。IBM最初向 NBS提交的建议方案采用112 bits密钥，但公布的DES标准采用64 bits密钥。 有人认为NSA故意限制DES的密钥长度。

• 采用穷搜索已经对DES构成了威胁。

• 1977年Diffie和Hellman提出了制造一个每秒能测试106个密钥的大规模芯片，这种芯片的机器大约一天就可以搜索DES算法的整个密钥空间，制造这样的机器需要两千万美元。

密钥搜索

• 1993年，R.Session和M.Wiener给出了一个非常详细的密钥搜索机器的设计方案

• 基于并行的密钥搜索芯片，此芯片每秒测试5×107个密钥

• 当时这种芯片的造价是10.5美元，5760个这样的芯片组成的系统需要10万美元，这一系统平均1.5天即可找到密钥

• 如果利用10个这样的系统，费用是100万美元，但搜索时间可以降到2.5小时。

密钥搜索与超级计算

• DES的56位短密钥面临的另外一个严峻而现实的问题是：国际互 联网Internet的超级计算能力。

• 1997年1月28日，美国的RSA数据安全公司在互联网上开展了一项名为“密钥挑战”的竞赛，悬赏一万美元，破解一段用56位密钥加密的DES密文。

密钥挑战

• 一位名叫Rocke Verser的程序员设计了一个可以通过互联网分段运行的密钥穷举搜索程序，组织实施了一个称为DESHALL的搜索行动，成千上万的志愿者加入到计划中

• 计划实施的第96天，即挑战赛计划公布的第140天，1997年6月17 日晚上10点39分，美国盐湖城Inetz公司的职员Michael Sanders 成功地找到了密钥

• 在计算机上显示了明文：“The unknown message is: Strong cryptography makes the world a safer place”

DES的破解

• 1998年7月电子前沿基金会（EFF）使用一台25万美圆的电脑在56 小时内破译了56比特密钥的DES；

• 1999年1月RSA数据安全会议期间，电子前沿基金会用22小时15分 钟就宣告破解了一个DES的密钥。

DES的安全性的其他方面

• 如果一个分组密码易受到穷举密钥搜索攻击，那么对同一消息加密多次就有可能增强安全性

• 多重DES就是使用多个密钥利用DES对明文进行多次加密。使用多重DES可以增加密钥量，从而大大提高抵抗穷举密钥搜索攻击的能力

• 多重加密类似于一个有着多个相同密码的级联，但各级密码无需独立，且 每级密码既可以是一个分组密码加密函数，也可是相应的解密函数

3 双重DES算法

• 简单的对消息  利用两个不同的密钥进行两次加密

• 目的是为了抵抗穷搜索攻击，期望密钥长度扩展为112比特

中间相遇攻击

中间相遇攻击的步骤

给定一已知明密文对(x1 ,y1 )，可按下述方法攻击。

• 以密钥k1的所有个可能的取值对此明文x1加密，并将密文z存储在一个表中；

• 从所有可能的个密钥k2中依任意次序选出一个对给定的密文y1解密，并将每次解密结果z在上述表中查找相匹配的值。一旦找到，则可确定出两个密钥k1和k2；

• 以此对密钥k1和k2对另一已知明文密文对(x2 , y2)中的明文x2进行加密，如果能得出相应的密文y2就可确定k1和k2是所要找的密钥。

中间相遇攻击的复杂度

• 对于给定明文x，以两重DES加密将有个可能的密文。

• 可能的密钥数为个。所以，在给定明文下，将有个密钥能产生给定的密文。

• 用另一对64比特明文/密文对进行检验，就使虚报率降为 。

• 这一攻击法所需的存储量为 Byte，最大试验的加密次数 。 这说明破译双重DES的难度为量级

4 三重DES算法

• 三重DES中三个密码组件既可以是一个加密函数，也可以是一个解密函数。

• 当时，则称为双密钥三重DES

双密钥三重DES算法

双密钥三重DES算法的安全性

• 破译它的穷举密钥搜索量为量级

• 差分分析破译也要超过​​​​​​​量级

• 此方案仍有足够的安全性