数据加密标准 (DES)

DES 设计参数

• 块（明文和密文）长度为64位

• 主密钥长度为64位

  • 但其中8位是奇偶校验位，所以有效密钥长度是56位。

• DES 由16轮构成，每轮使用一个由主密钥派生出的循环密钥（也叫子密钥）

  • 子密钥长度为48位，从56位密钥通过密钥调度派生而来。

DES 操作符号

• 位串块的循环移位：用 b<<<n 表示块b的位向左移动n。移出的位被添加到b的右侧。

  • 如：

    $$11000011<<<3=00011110$$

• 位的位置排列：写成输入位的输出顺序。

  • 如，排列4123表示：

    • 第四个输入位成为第一输出位

    • 第一个输入位成为第二输出位

    • ……

  • 我们使用 “排列”一词来表示位的重新排列，其中包括位的重复或丢弃，尽管这并不是一种正确的排列。

加密

1. 初始置换（IP）

2. 每一轮的操作

   • 将输入分成两等份 $M=(L_0,R_0)$$M = (L_0,R_0)$

   • 对右半部分应用费斯妥函数

   • 将结果与旧的左半部计算异或，成为新的左半部

   • 交换旧的右半部分和新的左半部分，除非我们处于最后一轮

      

     意即：

     对于每一轮

     $$i=1,2,...,16$$

     计算

     $$\begin{array}{cc}{L}_i=& R_{i-1}\\ R_i=& L_{i-1}\oplus F(K_i,R_{i-1})\end{array}$$

   最后得到 $C=(R_{16},L_{16})$$C = (R_{16}, L_{16})$

3. 最终置换（FP 或 IP^-1）

解密

与加密一样，但子密钥顺序相反

1. 最终置换（ FP或IP^-1 ）

2. 每一轮的操作

   • 将输入分成两等份 $C=(R_{16},L_{16})$$C = (R_{16}, L_{16})$

   • 对于每一轮

   $$i=16，15，...，1$$

   计算

   $$\begin{array}{cc}{R}_{i-1}=& L_i\\ L_{i-1}=& R_i\oplus F(K_i,L_1)\end{array}$$

   ---

   加密公式

   $$\begin{array}{cc}{L}_i=& R_{i-1}\\ R_i=& L_{i-1}\oplus F(K_i,R_{i-1})\end{array}$$

    

3. 初始置换（IP）

密钥调度

每一轮都有不同的密钥，由所谓的密钥调度计算得出

• 首先对主密钥应用 PC-1 排列，去掉奇偶校验位。这样就得到了 56 比特

• 将结果分成两等分，得到 $(C_0,D_0)$$(C_0,D_0)$

• 对于每一轮

计算

其中

• 现在，我们将 C_i 和 D_i 连接在一起，并使用 PC-2 产生 48 位输出，得到 K_i

费斯妥函数

1. 扩张置换（ E函数 ）

   • 通过将 16 个位加倍并排列，将 32 位半块扩展为 48 位块

2. 子密钥加

   • 计算子密钥与这个48位块的异或

3. S盒

   • 将 48 位分割成 8 个 6 位块。将 6 位块分别输入 8 个置换盒，由 4 位块置换出 6 位块。

   • DES的非线性操作，DES的核心

     • 什么是线性？

       $$f（a+b）=f(a)+f(b)$$

   • S盒是一个查找表，输入为6位，输出为4位。

     • 工作原理

       • 取出第一位和最后一位并连接它们，这个两位数字是行索引

       • 四个内部位表示列号

       • 输出是表中相应的条目

   • 它有以下约束条件：

     • 任何一个输出位都不应过于接近输入位的线性组合

     • 如果 S 盒的两个输入位正好相差一个位，那么它们的输出位必须至少相差两个位

     • 如果 S盒 的两个输入位在中间两个位上不同，那么它们的输出位必须至少在两个位上不同

     • 如果 S 盒的两个输入在前两个位上不同，而在后两个位上相同，则 S 盒的输出必须至少有两个位不同。

4. P盒

   • 将这 8 个 4 位数据块合并为 32 位数据块，再进行一次排列。

混淆和扩散

• 混淆：密文的每个位都应取决于密钥的多个部分，从而模糊了两者之间的联系

• 扩散：如果我们改变明文的一个位，那么（从统计学角度看）密文中一半的位都应该改变

3DES

按照今天的标准，DES是不安全的。

"2DES"

DES是一个很好的设计，但是由于它只有56位密钥，只有大约2⁵⁶的安全性（有一些对DES的密码分析攻击，但不是很严重，所以我们说它的安全性大约是2⁵⁶）。

对于 2DES：$En{c}_{K_1}(En{c}_{K_2}(M))$$Enc_{K_1}(Enc_{K_2}(M))$，安全性不会超过2⁵⁷：

• 尝试所有2⁵⁶个可能的密钥$K_2$$K_2$，并将所有结果存储在 $En{c}_{K2}(M)$$Enc_{K2} (M)$ 中。2⁵⁶用于加密，2⁵⁶log(2⁵⁶)用于排序（时间上的次要因素，忽略）。

• 尝试所有2⁵⁶个可能的密钥$K_1$$K_1$，计算$Dec{K}_1(C)$$Dec{K_1} (C)$，检查它是否是存储的$Enc{K}_2(M)$$Enc{K_2} (M)$之一。2⁵⁶用于解密，log(2⁵⁶)用于检查（对数级别，忽略）。

• $\text{总}\text{工}\text{作}\text{量}=2^{56}+2^{56}=2^{57}$$总工作量=2^{56}+2^{56}=2^{57}$

3DES 很好，但慢

$Enc{K}_1(Dec{K}_2(Enc{K}_3(M)))$$Enc{K_1}(Dec{K_2}(Enc{K_3}(M)))$

• 为什么是 Enc-Dec-Enc 而不是 Enc-Enc-Enc ？Enc-Dec-Enc 为我们提供了一个设置K₁ = K₂ = K₃ 的选项，这相当于DES，所以如果你有3DES，你可以让它做DES，这在某些情况下可能很有用。

• 3DES为我们提供了多少安全性？它并没有给我们提供2¹⁶⁸的安全性，因为与我们在“2DES”中遇到的相同的“中间相遇”攻击是可能的。据说它能给我们2¹¹⁸的安全性。