# DATA ENCRYPTION STANDARD (DES)

DES 是经典的对称加密算法，今天我们结合 DES 的官方设计文档，使用 java 来实现 DES 加密算法。

DES 算法设计的目标是使用 64 位的控制密钥 Key 来加解密 64 位的块数据。解密实际上为加密的逆过程，两者需使用相同的 Key。

# DES 加密流程

对于一个块数据，首先 1）使用初始置换 IP 更改块中数据的位置。之后 2）经过一系列基于 key 的复杂运算 $f$ ，最终 3）使用初始置换的逆 $IP^{-1}$ 来还原块中数据位置。

解密流程与加密流程相同，利用异或操作的自反性，即 $x \oplus f \oplus f = x$ 来完成数据块的还原。

具体流程图如下所示：

具体加密过程中，数据块会被分为左右两部分，即 $L_{n}$ 和 $R_{n}$ 。共进行 16 轮加密变化，每轮只处理 $L_{n}$ 的数据， $R_{n}$ 直接作为下一轮的左半边输入 $L_{n+1} = R_{n}$ 。

从上图我们可以看到 16 轮，共有 16 个不同的密钥 $K_{n}$ 。这些密钥都是从最初的密钥 key，通过密钥调度算法（key schedule， KS）计算得到的。

# DES 算法细节及相关代码

# 初始置换 IP

private static final int[] 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
};

58，意味着将块数据中第 58 位的数据移到第 1 位。

# 初始置换的逆IP^

private static final int[] FP = {
    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
};

这个逆置换中，我们可以看到第 58 个数字为 1，即将第 1 位的数据还原回第 58 位。

# 加密计算

我们将 64 位的输入分为左右两个连续的 32 位块数据，即 L 和 R。输入可表示为 LR。

每一轮的迭代输出 L’R’由下面计算过程获得：

L’ = R

R’ = $L \oplus f(R, K)$

其中 K 是一个由 64 位原始 key 选择得到的 48 位块。 $\oplus$ 操作指位与位的异或。

密钥调度算法我们稍后再详细介绍，目前先将整体的加密流程完整顺一遍。

# 加密函数 $f(R, K)$

先看完整流程图

E 为扩展变化，将 32 位的 R 扩展为 48 位，其中多出的 16 位为重复数据。扩展表如下所示

private static final int[] E = {
    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
};

R 扩展之后与 48 位的轮密钥 K 做异或操作，得到 48 位的输出。

48 位输出，经过 8 个选择函数（select functions），获得 32 位的结果。我们称这些选择函数为 S 盒（Substitution Box）。

S 盒替换
用于非线性替换，同时使得输入输出映射更加复杂化，使得加密过程更加复杂和安全。

输入： 6 位二进制
输出： 4 位二进制
S 盒示例，S1

行 / 列	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	5	10	3	0
3	15	12	8	2	4	9	1	7	5	11	3	14	10	0	6	13

替换过程示例：

假设输入为 6 位二进制串 011011
- 输入第 1 位和第 6 位，作为行索引 01（即第一行）
- 输入第 2-5 位，作为列索引 1101（即第 13 列）
- 查找 S1 盒，得到 5，将其转换为 4 位二进制 0101
- 结果：011011 => 0101
完整的 S 盒可见官方文档。

P 置换

private static final int[] P = {
    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
};

至此，我们可以获得 $R_{n} = L_{n-1} \oplus f(R_{n-1}, K_{n})$

# 密钥调度算法

现在，整个算法中我们还缺轮密钥的生成过程。首先，我们先看一下密钥调度算法的整体流程。

初始 64 位密钥 KEY 先经过置换选择（PERMUTED CHOICE 1，PC-1）得到 56 位的输出。

private static final int[] PC1 = {
		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
};

输出分为左右两个 28 位的块 $C_{0}$ 和D_

$C_{0}$ 和 $D_{0}$ 经过循环左移特定位数后，得到 $C_{1}$ 和D_

1	private static final int[] SHIFTS = {1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1};

$C_{1}$ 和 $D_{1}$ 再经过置换选择（PERMUTED CHOICE 2，PC-2）得到 48 位输出

private static final int[] PC2 = {
		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
};

循环 16 轮，得到 16 个轮密钥。

至此我们就完成了完整的 DES 加密。

# DES 解密浅析

分析加密过程的最后一轮，如下图所示。

Q: 当我们得到输出 R’L’，我们如何还原回 $R_{16}L_{16}$ ?

A：是做 $PC^{-1}$ 的逆变换，也就是做 $PC$ 。所以解密第一步和加密完全相同。

Q: 得到 $R_{16}L_{16}$ 后，我们如何还原得到 $R_{15}L_{15}$ 呢？

A: $R_{15} = L_{16}$ ，所以目前只需要知道 $L_{15}$ 即可。由前面介绍的异或自反性，我们可知

$L_{15} = L_{15} \oplus f(R_{15}, K_{16}) \oplus f(R_{15}, K_{16})$

分析上面式子，其中 $R_{15} = L_{16}$ ， $K_{16}$ 这两个部分已知， $R_{16} = L_{15} \oplus f(R_{15}, K_{16})$

所以，我们替换一下可得 $L_{15} = R_{16} \oplus f(L_{16}, K_{16})$ 。形式上与加密过程完全一样，只需替换其中 L 和 R。所以我们可以很容易得到解密过程。

# java 源代码实现

https://github.com/snowroll/crypto/blob/main/src/DESKeyGenerator.java

待开源

心生，种种魔生；心灭，种种魔灭。

——《西游记》

crypto

行 / 列	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	5	10	3	0
3	15	12	8	2	4	9	1	7	5	11	3	14	10	0	6	13

行 / 列	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	5	10	3	0
3	15	12	8	2	4	9	1	7	5	11	3	14	10	0	6	13