那么, DES 是如何工作的呢? 本文解释了 DNS 加密中涉及的各个步骤, 并通过一个简单的示例说明了每个步骤如何工作. 自 DES 创建以来, 基于与 DES 类似的设计原则, 出现了许多其他算法 (改变数据的方法) 一旦您理解了 DES 中的基本转换, 您就会发现 跟上这些最新算法所涉及的步骤是容易的.
但是, 首先我们应该了解一下 DES 的历史, 以及对未来的展望.
在 Richard Nixon 执政期间的 1973 年 5 月 15 日, 美国国家标准局 (National Bureau of Standards, NBS) 在《联邦公报》(Federal Register) 上发布了一份征求用来保护传输和存储过程中的数据的加密算法提议的公告. 同时, 该公告解释了加密的重要性.
在过去的十年中, 政府, 工业和私营部门的其他组织在数字数据的积累和交流方面正在加速增长. 这些通信和存储的数据的内容通常具有非常重要的价值, 同时可能有着较高的敏感程度. 现在常见的数据传输包括数百万美元的资金转移, 证券的买卖, 执法机构之间传送的逮捕或逮捕令和定罪记录, 对航空公司和乘客来说代表投资和价值的机票预订业务, 以及医生和治疗中心之间传送的病人健康状况和护理记录.NBS 一直在等待回应. 直到 1974 年 8 月 6 日, 也就是 Nixon 辞职的前三天, IBM 公司提交了其内部开发的一种名为 LUCIFER 算法作为候选者. 在美国国家安全局 (National Security Agency, NSA) 的帮助下对算法进行评估后, NBS 于 1977 年 7 月 15 日采用了 LUCIFER 算法的修改版作为新的 Data Encryption Standard (DES).随着商业机构和政府部门传输和存储的数据的数量, 价值和机密性的不断增加, 人们对这些记录在未经授权的情况下被访问和使用的风险有了更高的认识和关注. 这种滥用的形式可以是盗窃或篡改代表金钱的数据记录, 恶意修改商业库存或截取和滥用有关个人的机密信息. 因此, 数据保护的需求是显而易见的, 也是迫在眉睫的. 1
人们认识到, encryption (scrambling, enciphering or privacy transformation) 是在传输过程中保护此类数据的唯一方法, 也是保护存储在各种介质上的数据内容的有用方法, 但前提是可以设计和验证足够强度的加密方式, 并且其本身可集成到系统架构中. NBS 征求有关计算机数据加密技术和算法的建议. NBS 还征求为实现加密功能的推荐技术的实现, 推荐技术有: 生成, 评估和保护加密密钥; 维护过期密钥下的加密文件; 对加密文件进行部分更新; 为实现数据的标记, 轮询和路由而混合明文和加密数据等技术. 该局在制定标准和协助政府和行业评估技术方面发挥着作用, 并将安排对加密方法进行评估, 以便制定指导方针.
DES 很快被用于非数字媒体, 如音频电话线 (voice-grade public telephone lines). 举个例子, 在几年内, 美国国际香精香料公司 (International Flavors and Fragrances, IFF) 使用 DES 来保护其通过电话传输的宝贵配方 ("With Data Encryption, Scents Are Safe at IFF," Computerworld 14, No. 21, 95 (1980).)
与此同时, 银行业作为政府之外最大的加密用户, 采用了 DES 作为批发银行标准. 批发银行业的标准由美国国家标准协会 (American National Standards Institute, ANSI) 制定. 1980 年通过的 ANSI X3.92 规定了 DES 算法的使用.
DES 对 64 个信息比特组 (相当于 16 个十六进制数) 进行加密. 为了进行加密, DES 使用 "keys", 其长度显然也是 16 个十六进制数 (64-bits). 但是, 在 DES 算法中, 每个密钥中有 8-bits 会被忽略, 因此密钥的有效长度为 56 位. 但是, 无论如何, 64-bits (16 个十六进制数) 是 DES 组织的整数.
例如, 如果我们将明文 "8787878787878787" 用 DES 密钥 "0E329232EA6D0D73" 进行加密, 最终得到密文 "0000000000000000". 如果使用相同的 DES 密钥 "0E329232EA6D0D73" 对密文进行解密, 则将得到原始明文 "8787878787878787".
这个例子之所以整齐有序, 是因为我们的明文长度正好是 64-bits. 如果明文恰好是 64-bits 的倍数, 情况也是如此. 但大多数的信息不属于这一情况. 它们不会是 64-bits 的整数倍 (16 个十六进制数的整数倍).
例如，"Your lips are smoother than vaseline", 这个明文信息长 38 个字节 (76 个十六进制数字). 因此, 必须在信息尾部添加一些额外字节进行加密. 一旦加密信息被解密, 这些额外的字节将被丢弃. 当然, 有不同的填充方案 (添加额外字节的不同方法). 在这里，我们只需在末尾添加 0 即可，使得信息总量是 8 字节 (16 个十六进制数字，或 64-bits) 的倍数.
明文信息 "Your lips are smoother than vaseline" 的十六进制编码为:
596F7572206C6970 732061726520736D 6F6F746865722074 68616E2076617365 6C696E650D0A
(请注意, 前 72 位十六进制数字表示英文报文, 十六进制数 "0D" 表示回车, 十六进制数 "0A" 表示换行, 表示报文文件已结束)
换行符
然后, 我们在报文末尾填充一些 0, 得到总共 80 位十六进制数字:
596F7572206C6970 732061726520736D 6F6F746865722074 68616E2076617365 6C696E650D0A0000
如果我们使用与之前相同的 DES 密钥 "0E329232EA6D0D73" 对该明文信息进行加密, 每次加密 64 位 (16 位十六进制数字),
就可以得到密文:
C0999FDDE378D7ED 727DA00BCA5A84EE 47F269A4D6438190 9DD52F78F5358499 828AC9B453E0E653
这就是可以传输或存储的密文. 对密文进行解密, 就可以恢复原来的信息----"Your lips are smoother than vaseline". (Think how much better off Bill Clinton would be today, if Monica Lewinsky had used encryption on her Pentagon computer!)
DES 是一种分块密码 (block cipher), 这意味着它对给定大小 (64 bits) 的明文块进行操作, 并返回相同大小的密文块. 因此, DES 会产生 $2^{64}$ 种可能的 64 位排列 (permutation), 每个位可能是 0 或 1. 每个 64 位块被分为两个各 32 位块----左半块 $L$ 和右半块 $R$. (这种划分仅在某些操作中使用.)
Example: 明文 $M$ = 0123456789ABCDEF, 其中 $M$ 为十六进制格式.
将其改写为二进制格式，我们得到-64 bits 的文本块:
$M$ = 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111
$L$ = 0000 0001 0010 0011 0100 0101 0110 0111
$R$ = 1000 1001 1010 1011 1100 1101 1110 1111
从左向右读取: $M$ 的第一位为 0, 最后一位为 1.
DES 使用 56-bits 大小的密钥对 64-bits 的数据块进行操作. 密钥实际上被存储为 64-bits, 但是每个密钥中有 8-bits 没有被使用 (即8, 16, 24, 32, 40, 48, 56 和 64位 )
然而, 在下面的计算中, 我们将左至右对每位依次编号为 1 到 64. 但是, 正如您所看到的, 当我们创建子密钥时, 刚才提到的 8 位将被删除.
Example: 十六进制密钥 $K$ = 133457799BBCDFF1 这样就得到了二进制密钥 (1 = 0001,
3=0011等, 每 8 位位 1 组, 每组的最后一位未使用):
$K$ = 00010011 00110100 01010111 01111001 10011011 10111100 11011111 11110001
DES 算法有以下几个步骤:
64 bits 密钥按照下表 (PC-1) 进行排列. 由于表中的第一个条目是 "57", 这意味着原始密钥 $K$ 的第 57 位变成了置换密钥 $K+$ 的第 1 位. 原始密钥的第 49 位成为置换密钥的第 2 位. 原始密钥的第 4 位成为了置换密钥的最后一位. 请注意, 只有 56 bits 的原始密钥出现在置换密钥中.
| 57 | 49 | 41 | 33 | 25 | 17 | 9 |
| 1 | 58 | 50 | 42 | 34 | 26 | 18 |
| 10 | 2 | 59 | 51 | 43 | 35 | 27 |
| 19 | 11 | 3 | 60 | 52 | 44 | 36 |
| 63 | 55 | 47 | 39 | 31 | 23 | 15 |
| 7 | 62 | 54 | 46 | 38 | 30 | 22 |
| 14 | 6 | 61 | 53 | 45 | 37 | 29 |
| 21 | 13 | 5 | 28 | 20 | 12 | 4 |
Example: 原始的 64-bits 密钥:
$K$ = 00010011 00110100 01010111 01111001 10011011 10111100 11011111 11110001
我们得到 56-bits 的置换密钥:
$K+$ = 1111000 0110011 0010101 0101111 0101010 1011001 1001111 0001111
然后, 将密钥分成左右两半, 即 $C_0$ 和 $D_0$, 每半有 28-bits.
Example: 从置换密钥 $K+$ 我们得到:
$C_0$ = 1111000 0110011 0010101 0101111, $D_0$ = 0101010 1011001 1001111 0001111
在定义了 $C_0$ 和 $D_0$ 之后, 我们现在构造 16 个 $C_n, D_n, 1 \leq n \leq 16$. 在 $n = 1, 2, ..., 16$ 的情况下, 每一对 $C_n 和 D_n$ 分别由上一对 $C_{n-1} 和 D_{n-1}$ 使用下面表进行左移操作完成. 左移时, 除第一位外, 每一位向左移动一位, 第一位则循环到块的末尾.
| Iteration | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Number of Left Shifts | 1 | 1 | 2 | 2 | 2 | 2 | 2 | 2 | 1 | 2 | 2 | 2 | 2 | 2 | 2 | 1 |
例如, $C_3 和 D_3$ 分别由 $C_2 和 D_2$ 通过左移两次得到, $C_{16} 和 D_{16}$ 分别由 $C_{15} 和 D_{15}$ 通过左移一次得到. 在所有情况下, 一次左移是指将比特向左旋转一位. 这样, 经过一次左移后, 28-bits 块上的比特就是之前2, 3, ..., 28,1 位上的比特.
Example: 由原始配对 $C_0$ 和 $D_0$ 可得:
$C_0$ = 1111000011001100101010101111, $D_0$ = 0101010101100110011110001111
$C_1$ = 1110000110011001010101011111, $D_1$ = 1010101011001100111100011110
$C_2$ = 1100001100110010101010111111, $D_2$ = 0101010110011001111000111101
$C_3$ = 0000110011001010101011111111, $D_3$ = 0101011001100111100011110101
$C_4$ = 0011001100101010101111111100, $D_4$ = 0101100110011110001111010101
$C_5$ = 1100110010101010111111110000, $D_5$ = 0110011001111000111101010101
$C_6$ = 0011001010101011111111000011, $D_6$ = 1001100111100011110101010101
$C_7$ = 1100101010101111111100001100, $D_7$ = 0110011110001111010101010110
$C_8$ = 0010101010111111110000110011, $D_8$ = 1001111000111101010101011001
$C_9$ = 0101010101111111100001100110, $D_9$ = 0011110001111010101010110011
$C_{10}$ = 0101010111111110000110011001, $D_{10}$ = 1111000111101010101011001100
$C_{11}$ = 0101011111111000011001100101, $D_{11}$ = 1100011110101010101100110011
$C_{12}$ = 0101111111100001100110010101, $D_{12}$ = 0001111010101010110011001111
$C_{13}$ = 0111111110000110011001010101, $D_{13}$ = 0111101010101011001100111100
$C_{14}$ = 1111111000011001100101010101, $D_{14}$ = 1110101010101100110011110001
$C_{15}$ = 1111100001100110010101010111, $D_{15}$ = 1010101010110011001111000111
$C_{16}$ = 1111000011001100101010101111, $D_{16}$ = 0101010101100110011110001111
现在, 我们通过对每个连接的密钥对 $C_nD_n$ 应用下面的置换表来形成密钥 $K_n (1 \leq n \leq 16)$. 每对密钥有 56 位, 但 PC-2 只使用其中的 48 位.
| 14 | 17 | 11 | 24 | 1 | 5 |
| 3 | 28 | 15 | 6 | 21 | 10 |
| 23 | 19 | 12 | 4 | 26 | 8 |
| 16 | 7 | 27 | 20 | 13 | 2 |
| 41 | 52 | 31 | 37 | 47 | 55 |
| 30 | 40 | 51 | 45 | 33 | 48 |
| 44 | 49 | 39 | 56 | 34 | 53 |
| 46 | 42 | 50 | 36 | 29 | 32 |
因此, $K_n$ 的第 1 位是 $C_nD_n$ 的第 14 位, 第 2 位是第 17 位, 以此类推, $K_n$ 的第 48 位是 $C_nD_n$ 的第 32 位.
Example: 对于第一个密钥, 我们有
$C_1D_1$ = 1110000 1100110 0101010 1011111 1010101 0110011 0011110 0011110
应用置换表 PC-2 后,
$K_1$ = 000110 110000 001011 101111 111111 000111 000001 110010
其他密钥:
$K_2$ = 011110 011010 111011 011001 110110 111100 100111 100101
$K_3$ = 010101 011111 110010 001010 010000 101100 111110 011001
$K_4$ = 011100 101010 110111 010110 110110 110011 010100 011101
$K_5$ = 011111 001110 110000 000111 111010 110101 001110 101000
$K_6$ = 011000 111010 010100 111110 010100 000111 101100 101111
$K_7$= 111011 001000 010010 110111 111101 100001 100010 111100
$K_8$= 111101 111000 101000 111010 110000 010011 101111 111011
$K_9$= 111000 001101 101111 101011 111011 011110 011110 000001
$K_{10}$= 101100 011111 001101 000111 101110 100100 011001 001111
$K_{11}$= 001000 010101 111111 010011 110111 101101 001110 000110
$K_{12}$= 011101 010111 000111 110101 100101 000110 011111 101001
$K_{13}$= 100101 111100 010111 010001 111110 101011 101001 000001
$K_{14}$= 010111 110100 001110 110111 111100 101110 011100 111010
$K_{15}$= 101111 111001 000110 001101 001111 010011 111100 001010
$K_{16}$= 110010 110011 110110 001011 000011 100001 011111 110101
子密钥就介绍到这里. 现在我们来看看信息本身.
对需加密的信息 $M$ 的 64-bits 进行 初始置换 (initial permutation, IP). 根据下表重新排列比特位, 表中条目表示比特位在初始顺序基础上的新排列. $M$ 的第 58 位成为 $IP$ 的第 1 位. $M$ 的第 50 位成为 $IP$ 的第 2 位. $M$ 的第 7 位是 $IP$ 的最后一位.
| 58 | 50 | 42 | 34 | 26 | 18 | 10 | 2 |
| 60 | 52 | 44 | 36 | 28 | 20 | 12 | 4 |
| 62 | 54 | 46 | 38 | 30 | 22 | 14 | 6 |
| 64 | 56 | 48 | 40 | 32 | 24 | 16 | 8 |
| 57 | 49 | 41 | 33 | 25 | 17 | 9 | 1 |
| 59 | 51 | 43 | 35 | 27 | 19 | 11 | 3 |
| 61 | 53 | 45 | 37 | 29 | 21 | 13 | 5 |
| 63 | 55 | 47 | 39 | 31 | 23 | 15 | 7 |
Example: 将初始置换应用于之前给出的文本块 $M$, 我们得到:
$M$ = 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111
$IP$ = 1100 1100 0000 0000 1100 1100 1111 1111 1111 0000 1010 1010 1111 0000 1010 1010
这里 $M$ 的第 58 位为 "1", 成为 $IP$ 的第 1 位. $M$ 的第 50 位为 "1", 成为 $M$ 的第 2 位. $M$ 的第 7 位为 "0"，成为 $IP$ 的最后一位.
接下来, 将置换块 $IP$ 分成左半部分 $L_0$ (32 bits) 和右半部分 $R_0$ (32 bits).
Example: 从 $IP$, 我们得到 $L_0 和 R_0$:
$L_0$ = 1100 1100 0000 0000 1100 1100 1111 1111
$R_0$ = 1111 0000 1010 1010 1111 0000 1010 1010
在 $1 \leq n \leq 16$ 时, 我们使用函数 $f$ 对两个数据块 (一个 32-bits 的数据块和一个 48-bits 的密钥 $K_n$) 进行 16 次迭代, 以产生一个 32-bits 的数据块. 让 + 表示 XOR 加法 (逐位加法 2 模). 对于 n 从 1 到 16, 我们可以计算出:
$L_n = R_{n-1}$
$R_n = L_{n-1} \oplus f (R_{n-1}, K_n)$
最终块即为 $n = 16$ 时的 $L_{16}R_{16}$. 也就是说, 在每一次迭代中, 我们取前一次运算结果的右 32 位作为当前运算步骤的左 32 位. 对于当前步骤的右 32 位, 我们将上一步骤的左 32 位与计算结果 $f$ 进行 XOR 运算.
Example: 对 $n = 1$, 我们有:
$K_1$ = 000110 110000 001011 101111 111111 000111 000001 110010
$L_1$ = $R_0$ = 1111 0000 1010 1010 1111 0000 1010 1010
$R_1$ = $L_0 \oplus f(R_0, K_1)$
下面将解释函数 $f$ 的工作原理. 为了计算 $f$, 我们首先将每个块 $R_{n-1}$ 从 32 bits 扩展到 48 bits. 为此, 我们使用一个选择表来重复 $R_{n-1}$ 中的某些位的比特. 我们将这个选择表称为函数 $E$. 因此, $E(R_{n-1})$ 需要 32-bits 的输入, 并且输出 48-bits 的块.
$E$ 的 48 位输出 (写成 8 块, 每块 6 bits) 是通过按照下表的顺序选择其输入的位而得到的 :
| 32 | 1 | 2 | 3 | 4 | 5 |
| 4 | 5 | 6 | 7 | 8 | 9 |
| 8 | 9 | 10 | 11 | 12 | 13 |
| 12 | 13 | 14 | 15 | 16 | 17 |
| 16 | 17 | 18 | 19 | 20 | 21 |
| 20 | 21 | 22 | 23 | 24 | 25 |
| 24 | 25 | 26 | 27 | 28 | 29 |
| 28 | 29 | 30 | 31 | 32 | 1 |
因此, $E(R_{n-1})$ 的前三位是 $R_{n-1}$ 的第 32, 1 和 2位, 而 $E(R_{n-1})$ 的后两位是$R_{n-1}$ 第 32 和 1 位.
Example: 我们根据 $R_0$ 计算 $E(R_0)$ 如下所示:
$R_0$ = 1111 0000 1010 1010 1111 0000 1010 1010
$E(R_0)$ = 011110 100001 010101 010101 011110 100001 010101 010101
(注意, 每个由 4 个原始比特组成的比特块已经扩展为一个由 6 个输出比特组成的比特块).
接下来在 $f$ 计算中, 我们将输出的 $E(R_{n-1})$ 与密钥 $K_n$ 进 行XOR 运算: $$K_n \oplus E(R_{n-1})$$ 对于 $K_1, R(R_0)$, 我们有:
$K_1$ = 000110 110000 001011 101111 111111 000111 000001 110010
$E(R_0)$ = 011110 100001 010101 010101 011110 100001 010101 010101
$K_1 \oplus E(R_0)$ = 011000 010001 011110 111010 100001 100110 010100 100111
我们尚未完成函数 $f$ 的计算. 到目前为止, 我们已经使用选择表将 $R_{n-1}$ 从 32-bits 扩展到 48-bits, 并将结果与密钥 $K_n$ 进行了 XOR. 现在我们有 48-bits (8 组 6-bits). 现在, 我们要对每组的 6-bits 做一些奇怪的事情: 把它们作为地址放入名为 "S 盒 (S boxes)" 的表中. 每组 6-bits 将为我们提供一个不同 S 盒中的位置. 位于该位置的将是一个 4-bits 数字. 这个 4-bits 数字将取代原来的 6-bits 数字. 最终结果是, 8 组 6-bits 数据转换成 8 组 4-bits (S 盒的 4 位输出) 共计 32 位数据.
将前面的 48-bits 结果写成如下形式: $$K_n + E(R_{n-1}) = B_1B_2B_3B_4B_5B_6B_7B_8$$ 其中每个 $B_i$ 是一组 6-bits. 我们现在计算: $$S_1(B_1)S_2(B_2)S_3(B_3)S_4(B_4)S_5(B_5)S_6(B_6)S_7(B_7)S_8(B_8)$$ 其中 $S_i(B_i)$ 指的是第 i 个 S 盒的输出. 重复一下, 每个函数 $S_1, S_2, ...,S_8$ 都采用 6-bits 块作为输入, 4-bits 块作为输出. $S_1$ 的表格如下所示并进行了解释:
| Row No. |
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 14 | 4 | 13 | 1 | 2 | 15 | 11 | 8 | 3 | 10 | 6 | 12 | 5 | 9 | 0 | 7 |
| 1 | 0 | 15 | 7 | 4 | 14 | 2 | 13 | 1 | 10 | 6 | 12 | 11 | 9 | 5 | 3 | 8 |
| 2 | 4 | 1 | 14 | 8 | 13 | 6 | 2 | 11 | 15 | 12 | 9 | 7 | 3 | 10 | 5 | 0 |
| 3 | 15 | 12 | 8 | 2 | 4 | 9 | 1 | 7 | 5 | 11 | 3 | 14 | 10 | 0 | 6 | 13 |
设 $S_1$ 是此表中定义的函数, $B$ 是 6-bits 块, 那么 $S_1(B)$ 的确定方法如下: B 的第 1 位和最后一位用来表示二进制下的 在十进制 0 - 3 (二进制: 00 - 11) 范围中的一个数字, 令这个数字为 $i$; $B$ 中间的 4 位表示二进制下的 在十进制 0 - 15 (二进制: 0000 - 1111) 范围中的一个数字, 令这个数字为 $j$. 在表格中查找第 $i$ 行第 $j$ 列中的数字. 它是一个范围在 0 - 15 之间的数字, 唯一表示成一个 4-bits 的数据块. 例如: 对于输入块 $B = 011011$, 第 1 位是 "0", 最后一位是 "1", 因此选择第 01 行 (即第 1 行). 中间四位是 "1101". 这相当于十进制数 13 的二进制形式, 因此列号为 13. 第 1 行第 12 列是 5. 这决定了输出; 5 的二进制是 0101, 因此输出是 0101. 所以 $S_1(011011) = 0101$.
函数 $S_1, ..., S_8$ 定义如下表所示:
| 14 | 4 | 13 | 1 | 2 | 15 | 11 | 8 | 3 | 10 | 6 | 12 | 5 | 9 | 0 | 7 |
| 0 | 15 | 7 | 4 | 14 | 2 | 13 | 1 | 10 | 6 | 12 | 11 | 9 | 5 | 3 | 8 |
| 4 | 1 | 14 | 8 | 13 | 6 | 2 | 11 | 15 | 12 | 9 | 7 | 3 | 10 | 5 | 0 |
| 15 | 12 | 8 | 2 | 4 | 9 | 1 | 7 | 5 | 11 | 3 | 14 | 10 | 0 | 6 | 13 |
| 15 | 1 | 8 | 14 | 6 | 11 | 3 | 4 | 9 | 7 | 2 | 13 | 12 | 0 | 5 | 10 |
| 3 | 13 | 4 | 7 | 15 | 2 | 8 | 14 | 12 | 0 | 1 | 10 | 6 | 9 | 11 | 5 |
| 0 | 14 | 7 | 11 | 10 | 4 | 13 | 1 | 5 | 8 | 12 | 6 | 9 | 3 | 2 | 15 |
| 13 | 8 | 10 | 1 | 3 | 15 | 4 | 2 | 11 | 6 | 7 | 12 | 0 | 5 | 14 | 9 |
| 10 | 0 | 9 | 14 | 6 | 3 | 15 | 5 | 1 | 13 | 12 | 7 | 11 | 4 | 2 | 8 |
| 13 | 7 | 0 | 9 | 3 | 4 | 6 | 10 | 2 | 8 | 5 | 14 | 12 | 11 | 15 | 1 |
| 13 | 6 | 4 | 9 | 8 | 15 | 3 | 0 | 11 | 1 | 2 | 12 | 5 | 10 | 14 | 7 |
| 1 | 10 | 13 | 0 | 6 | 9 | 8 | 7 | 4 | 15 | 14 | 3 | 11 | 5 | 2 | 12 |
| 7 | 13 | 14 | 3 | 0 | 6 | 9 | 10 | 1 | 2 | 8 | 5 | 11 | 12 | 4 | 15 |
| 13 | 8 | 11 | 5 | 6 | 15 | 0 | 3 | 4 | 7 | 2 | 12 | 1 | 10 | 14 | 9 |
| 10 | 6 | 9 | 0 | 12 | 11 | 7 | 13 | 15 | 1 | 3 | 14 | 5 | 2 | 8 | 4 |
| 3 | 15 | 0 | 6 | 10 | 1 | 13 | 8 | 9 | 4 | 5 | 11 | 12 | 7 | 2 | 14 |
| 2 | 12 | 4 | 1 | 7 | 10 | 11 | 6 | 8 | 5 | 3 | 15 | 13 | 0 | 14 | 9 |
| 14 | 11 | 2 | 12 | 4 | 7 | 13 | 1 | 5 | 0 | 15 | 10 | 3 | 9 | 8 | 6 |
| 4 | 2 | 1 | 11 | 10 | 13 | 7 | 8 | 15 | 9 | 12 | 5 | 6 | 3 | 0 | 14 |
| 11 | 8 | 12 | 7 | 1 | 14 | 2 | 13 | 6 | 15 | 0 | 9 | 10 | 4 | 5 | 3 |
| 12 | 1 | 10 | 15 | 9 | 2 | 6 | 8 | 0 | 13 | 3 | 4 | 14 | 7 | 5 | 11 |
| 10 | 15 | 4 | 2 | 7 | 12 | 9 | 5 | 6 | 1 | 13 | 14 | 0 | 11 | 3 | 8 |
| 9 | 14 | 15 | 5 | 2 | 8 | 12 | 3 | 7 | 0 | 4 | 10 | 1 | 13 | 11 | 6 |
| 4 | 3 | 2 | 12 | 9 | 5 | 15 | 10 | 11 | 14 | 1 | 7 | 6 | 0 | 8 | 13 |
| 4 | 11 | 2 | 14 | 15 | 0 | 8 | 13 | 3 | 12 | 9 | 7 | 5 | 10 | 6 | 1 |
| 13 | 0 | 11 | 7 | 4 | 9 | 1 | 10 | 14 | 3 | 5 | 12 | 2 | 15 | 8 | 6 |
| 1 | 4 | 11 | 13 | 12 | 3 | 7 | 14 | 10 | 15 | 6 | 8 | 0 | 5 | 9 | 2 |
| 6 | 11 | 13 | 8 | 1 | 4 | 10 | 7 | 9 | 5 | 0 | 15 | 14 | 2 | 3 | 12 |
| 13 | 2 | 8 | 4 | 6 | 15 | 11 | 1 | 10 | 9 | 3 | 14 | 5 | 0 | 12 | 7 |
| 1 | 15 | 13 | 8 | 10 | 3 | 7 | 4 | 12 | 5 | 6 | 11 | 0 | 14 | 9 | 2 |
| 7 | 11 | 4 | 1 | 9 | 12 | 14 | 2 | 0 | 6 | 10 | 13 | 15 | 3 | 5 | 8 |
| 2 | 1 | 14 | 7 | 4 | 10 | 8 | 13 | 15 | 12 | 9 | 0 | 3 | 5 | 6 | 11 |
Example: 在第 1 轮中, 我们得到了 8 个 $S$ 箱的输出结果:
$K_1 \oplus E(R_0)$ = 011000 010001 011110 111010 100001 100110 010100 100111
$S_1(B_1)S_2(B_2)S_3(B_3)S_4(B_4)S_5(B_5)S_6(B_6)S_7(B_7)S_8(B_8)$ =
0101 1100 1000 0010 1011 0101 1001 0111
最后阶段是对 对 S 盒输出进行置换 $P$, 以获得 $f$ 的最终值: $$f = P(S_1(B_1)S_2(B_2)...S_8(B_8))$$ 置换 $P$ 的定义如下表所示. $P$ 通过对输入块的位进行置换, 实现从 32 位输入产生 32 位输出.
| 16 | 7 | 20 | 21 |
| 29 | 12 | 28 | 17 |
| 1 | 15 | 23 | 26 |
| 5 | 18 | 31 | 10 |
| 2 | 8 | 24 | 14 |
| 32 | 27 | 3 | 9 |
| 19 | 13 | 30 | 6 |
| 22 | 11 | 4 | 25 |
Example: 8 个 $S$ 盒的输出:
0101 1100 1000 0010 1011 0101 1001 0111
我们得到:
0010 0011 0100 1010 1010 1001 1011 1011
$R_1 = L_0 \oplus f(R_0, K_1)$ =
1100 1100 0000 0000 1100 1100 1111 1111 $\oplus$
0010 0011 0100 1010 1010 1001 1011 1011 =
1110 1111 0100 1010 0110 0101 0100 0100
在下一轮中, 我们将有 $L_2 = R_1$, 也就是我们刚刚计算出的图块, 然后我们必须计算 $R_2 = L_1 \oplus f(R_1, K_2)$, 如此循环 16 次. 第 16 轮结束时, 我们得到了块 $L_{16} 和 R_{16}$. 然后, 我们将这两个区块的顺序颠倒 (reverse)过来, 变成 64 位块. $$R_{16}L_{16}$$ 并对其进行下表定义的最终排列 (final permutation) $IP^{-1}$:
| 40 | 8 | 48 | 16 | 56 | 24 | 64 | 32 |
| 39 | 7 | 47 | 15 | 55 | 23 | 63 | 31 |
| 38 | 6 | 46 | 14 | 54 | 22 | 62 | 30 |
| 37 | 5 | 45 | 13 | 53 | 21 | 61 | 29 |
| 36 | 4 | 44 | 12 | 52 | 20 | 60 | 28 |
| 35 | 3 | 43 | 11 | 51 | 19 | 59 | 27 |
| 34 | 2 | 42 | 10 | 50 | 18 | 58 | 26 |
| 33 | 1 | 41 | 9 | 49 | 17 | 57 | 25 |
Example: 如果我们使用前面定义的方法处理所有 16 个区块, 那么在第 16 轮时, 我们会得到:
$L_{16}$ = 0100 0011 0100 0010 0011 0010 0011 0100
$R_{16}$ = 0000 1010 0100 1100 1101 1001 1001 0101
我们将这两个块的顺序颠倒, 并对其进行最终排列:
$R_{16}L_{16}$ = 00001010 01001100 11011001 10010101 01000011 01000010 00110010 00110100
$IP^{-1}$ = 10000101 11101000 00010011 01010100 00001111 00001010 10110100 00000101
它的十六进制形式为: 85E813540F0AB405
这是 $M$ = 0123456789ABCDEF的加密形式, 即 $C$ = 85E813540F0AB405.
解密仅仅是加密的逆过程, 按照上述相同的步骤进行, 但是需要反转应用子密钥的顺序.
DES 算法将一个 64-bits 消息块 $M$ 转换为一个 64-bits 的密文块 $C$. 如果每个 64-bits 块都单独进行加密, 那么加密的模式称为 电子密码本 (Electronic Code Book, ECB)模式. 还有两种其他的 DES 加密模式, 分别是链式块编码 (Cipher Block Chaining, CBC) 和密文反馈 (Cipher Feedback, CFB)模式, 这些模式通过初始的异或运算使得每个密文块依赖于前面所有的消息块.
在 DES 成为国家标准之前, 在 NBS 征求对该算法的意见期间, 公钥密码学的创始人 Martin Hellman 和 Whitfield Diffie 对使用 DES 作为加密算法提出了一些反对意见. Hellman 写道: "Whit Diffie and I have become concerned that the proposed data encryption standard, while probably secure against commercial assault, may be extremely vulnerable to attack by an intelligence organization"（letter to NBS, October 22, 1975). [这句话的中文翻译: Whit Diffie 和我担心所提议的数据加密标准, 虽然可能对商业攻击是安全的, 但可能极易受到情报机构的攻击]
Diffie 和 Hellman 随后概述了一种对 DES 的 "穷举攻击" (brute force, 即尝试解密密文以得到合理的明文消息之前, 尝试尽可能多的 $2^{56}$ 个可能的密钥). 他们提议建造一台特殊用途的 "并行计算机", 它使用一百万个芯片并且每秒能够尝试一百万个密钥, 这样一台机器成本估计为 2000 万美元.
快进到 1998 年，根据 EFF 的 John Gilmore 的指导, 一个团队花费了 22 万美元, 并构建了一台能够在平均 4.5 天内遍历整个 56-bits 的 DES 密钥空间的计算机. 1998 年 7 月 17 日, 他们宣布他们已经在 56 小时内破解了一个 56-bits 的密钥. 这台名为 "Deep Crack" 的计算机, 它包含 27 个板, 每个板上有 64 个芯片, 每秒可以测试 900 亿个密钥.
尽管如此，就在 1998 年 6 月 8 日, 司法部主要副助理检察长 (principal associate deputy attorney general at the Department of Justice) Robert Litt 否认 FBI 有可能破解 DES: " Let me put the technical problem in context: It took 14,000 Pentium computers working for four months to decrypt a single message . . . . We are not just talking FBI and NSA [needing massive computing power], we are talking about every police department." [这句话的中文翻译: 让我把技术问题放在适当的背景下: 14000 台奔腾计算机工作了四个月才解密了一条消息.... 我们不仅仅在谈论 FBI 和 NSA [需要大规模计算能力], 我们还在谈论每个警察部门.]
密码学专家 Bruce Schneier 回应说:". . . the FBI is either incompetent or lying, or both." [这句话的中文翻译: ...FBI 要么无能, 要么在撒谎, 要么两者都有.] Schneier 继续说：The only solution here is to pick an algorithm with a longer key; there isn't enough silicon in the galaxy or enough time before the sun burns out to brute-force triple-DES" (Crypto-Gram, Counterpane Systems, August 15, 1998). [这句话的中文翻译: 唯一的解决办法是选择一个密钥更长的算法; 在银河系内没有足够的硅片, 也没有足够的时间, 在太阳燃烧殆尽之前进行三重 DES 的穷举攻击]
三重 DES (Triple-DES) 实际上是使用两个 56-bits 密钥对 进行三次 DES. 给定一个明文消息, 首先使用第 1 个密钥对消息进行 DES 加密. 然后使用第 2 个密钥对加密后的消息进行 DES 解密 (由于第 2 个密钥不是正确的密钥, 所以这个解密过程只会进一步混淆数据). 接下来, 将经过两次混淆的消息再次使用第 1 个密钥进行加密, 得到最终的密文. 这个三步过程被称为三重 DES.
三重 DES 实际上就是按照特定顺序使用两个密钥对 DES 进行三次操作. (也可以使用三个独立的密钥进行三重 DES 操作, 无论使用两个还是三个密钥, 所得到的密钥空间约为 $2^{112}$.)
"Cryptographic Algorithms for Protection of Computer Data During Transmission and Dormant Storage," Federal Register 38, No. 93 (May 15, 1973).
Data Encryption Standard, Federal Information Processing Standard (FIPS) Publication 46, National Bureau of Standards, U.S. Department of Commerce, Washington D.C. (January 1977).
Carl H. Meyer and Stephen M. Matyas, Cryptography: A New Dimension in Computer Data Security, John Wiley & Sons, New York, 1982.
Dorthy Elizabeth Robling Denning, Cryptography and Data Security, Addison-Wesley Publishing Company, Reading, Massachusetts, 1982.
D.W. Davies and W.L. Price, Security for Computer Networks: An Introduction to Data Security in Teleprocessing and Electronics Funds Transfer, Second Edition, John Wiley & Sons, New York, 1984, 1989.
Miles E. Smid and Dennis K. Branstad, "The Data Encryption Standard: Past and Future," in Gustavus J. Simmons, ed., Contemporary Cryptography: The Science of Information Integrity, IEEE Press, 1992.
Douglas R. Stinson, Cryptography: Theory and Practice, CRC Press, Boca Raton, 1995.
Bruce Schneier, Applied Cryptography, Second Edition, John Wiley & Sons, New York, 1996.
Alfred J. Menezes, Paul C. van Oorschot, and Scott A. Vanstone, Handbook of Applied Cryptography, CRC Press, Boca Raton, 1997.
This article appeared in Laissez Faire City Times, Vol 2, No. 28.
Homepage: http://orlingrabbe.com/
Laissez Faire City Times: http://zolatimes.com/
译者注: "改变数据的方法" 出现的有些让人摸不着头脑, 个人认为, 其表示的是 "其他算法" 可用"改变数据的方法" 代替.
译者注: "跟上这些最新算法所涉及的步骤" 个人认为即为理解那些基于与 DES 类似的设计原则是的最新算法.
译者注: 因译者水平有限, 无法完美地翻译这个标题, 故保留此标题不做任何翻译.
译者注: 尼克松总统, 因与主动与中国改善关系和水门事件而被中国人民熟悉.
译者注: 英文原文为: other organizations in the private sector
译者注: 英文原文为: The contents of these communicated and stored data often have very significant value and/or sensitivity., 这里进行了部分意译, 而非完全按照原文进行的翻译.
译者注: 个人认为 warrants for arrests 和 arrest and conviction records 虽有重复的地方, 但是表示的含义则有所不同故将两者均保留.
译者注: airline reservations and ticketing 同意, 翻译为了 "机票预订业务".
译者注:health 被翻译为了 "病人健康状况".
译者注: 这一段在很大程度上进行了修改, 使其更符合中文的语言习惯.
译者注: 这里直接保留, 未对这些名词做任何翻译.
译者注: 英文原文为 The Bureau also solicits recommended techniques for implementing the cryptographic function: for generating, evaluating, and protecting cryptographic keys; for maintaining files encoded under expiring keys; for making partial updates to encrypted files; and mixed clear and encrypted data to permit labelling, polling, routing, etc.
译者注: 英文原文为 But, in any case, 64 bits (16 hexadecimal digits) is the round number upon which DES is organized. 个人认为这个句子的含义就是 DES 算法每次处理一个 64 bits 的数据.
译者注: 一句无关紧要的话, 以增加文章的趣味性. 翻译过来便是: "想想看, 如果 Monica Lewinsky 在五角大楼的电脑上使用了加密技术，Bill Clinton 今天会过得多好!" 个人认为, 与之更为贴切的, 应该是陈冠希的 "艳照门" 事件.
译者注: 这段文字告诉了我们在一个密钥中那些位没有被使用, 如果读者想要自己实现 DES 算法, 应当注意到那些位没有使用这一关键问题.
译者注: 这里选择了直接翻译, 原文想要表达的意思应该是获取 C 和 D 时, 采用的左移策略是循环左移, 整个比特串往左移, 左边弹出去了的位补到最右边去.
译者注: 即将下标一致的 $C_n 和 D_n$ 拼接在一起, 形成一个 56 位的比特串.
译者注: 这里使用 latex 中提供的 $\oplus$ 符号, 表示异或. 而不按照原文的符号进行表示.
译者注: 自己曾在网上找到许多其他描述这个扩展表 (扩展算法) 的图片, 读者可自行搜索.
译者注: for example 翻译为了 "举个例子". 😂
译者注: 这句话的英文原文为: Note here that the first 72 hexadecimal digits represent the English message, while "0D" is hexadecimal for Carriage Return, and "0A" is hexadecimal for Line Feed, showing that the message file has terminated. 个人认为 "showing that the message file has terminated." 可能存在歧义, 因为它既能说 "0A" 是一行结束的标志, 也能解释成 "0D0A" 是一行结束的标志. 个人更倾向于后一种解释.
译者注: 这句话的英文原文为 as recently as June 8, 1998