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

红太狼 2023-03-03 11:11 197阅读 0赞

# 1 DES的弱密钥 #

### 关于DES密钥 ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70][]

### DES的弱密钥 ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 1][]

# 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的安全性的其他方面 ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 2][]

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

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

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

# 3 双重DES算法 #

• 简单的对消息 ![x\_i][x_i] 利用两个不同的密钥进行两次加密

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 3][]

### 中间相遇攻击 ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 4][]

### 中间相遇攻击的步骤 ###

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

• 以密钥k1的所有![2^\{56\}][2_56]个可能的取值对此明文x1加密，并将密文z存储在一个表中；

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

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

### 中间相遇攻击的复杂度 ###

• 对于给定明文x，以两重DES加密将有![2^\{ 64\}][2_ 64]个可能的密文。

• 可能的密钥数为![2^\{112\}][2_112]个。所以，在给定明文下，将有![2^\{112\}/2^\{64\} =2^\{48\}][2_112_2_64_ _2_48]个密钥能产生给定的密文。

• 用另一对64比特明文/密文对进行检验，就使虚报率降为![2^\{48-64\}=2^\{ -16\}][2_48-64_2_ -16] 。

• 这一攻击法所需的存储量为![2^\{56\}\*8][2_56_8] Byte，最大试验的加密次数![2\*2^\{56\} =2^\{57\}][2_2_56_ _2_57] 。 这说明破译双重DES的难度为![2^\{57\}][2_57]量级

# 4 三重DES算法 #

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

• 当![k\_1=k\_3][k_1_k_3]时，则称为双密钥三重DES

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 5][]

### 双密钥三重DES算法 ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 6][]

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

• 破译它的穷举密钥搜索量为![2^\{112\}\\approx 5\*10^\{35\}][2_112_approx 5_10_35]量级

• 差分分析破译也要超过![10^\{52\}][10_52]量级

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

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70]: /images/20230208/ce2e5b75926a4ba4b0d9135a8a22db13.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 1]: /images/20230208/ae42dfc936994f81b5ed302abcf1feef.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 2]: /images/20230208/63607944fe13451d98c1cb985b0ae401.png
[x_i]: https://private.codecogs.com/gif.latex?x_i
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 3]: /images/20230208/0dd8b1bb5faf4ce48cc09161e1a39d74.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 4]: /images/20230208/07617f4b871e4bbc9af52e41f2ee83cf.png
[2_56]: https://private.codecogs.com/gif.latex?2%5E%7B56%7D
[2_ 64]: https://private.codecogs.com/gif.latex?2%5E%7B%2064%7D
[2_112]: https://private.codecogs.com/gif.latex?2%5E%7B112%7D
[2_112_2_64_ _2_48]: https://private.codecogs.com/gif.latex?2%5E%7B112%7D/2%5E%7B64%7D%20%3D2%5E%7B48%7D
[2_48-64_2_ -16]: https://private.codecogs.com/gif.latex?2%5E%7B48-64%7D%3D2%5E%7B%20-16%7D
[2_56_8]: https://private.codecogs.com/gif.latex?2%5E%7B56%7D*8
[2_2_56_ _2_57]: https://private.codecogs.com/gif.latex?2*2%5E%7B56%7D%20%3D2%5E%7B57%7D
[2_57]: https://private.codecogs.com/gif.latex?2%5E%7B57%7D
[k_1_k_3]: https://private.codecogs.com/gif.latex?k_1%3Dk_3
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 5]: /images/20230208/738fdf47ddd648849287b6c889a5d154.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 6]: /images/20230208/ee2fcde9b0204ac4aac477f9ace1ed0b.png
[2_112_approx 5_10_35]: https://private.codecogs.com/gif.latex?2%5E%7B112%7D%5Capprox%205*10%5E%7B35%7D
[10_52]: https://private.codecogs.com/gif.latex?10%5E%7B52%7D