DES是一种对称密钥的块加密算法。谓之 “对称密钥”，是因为加密、解密用的密钥是一样的（这不同于 RSA 等非对称密钥体系）。谓之 “块加密”，是因为这种算法把明文划分为很多个等长的块(block)，对每个块进行加密，最后以某种手段拼在一起。“块加密”亦称“分组加密”。
1973年，NSA向社会征集满足安全要求的加密算法。1973-1974年，IBM研发了 DES 加密算法。1974年，NSA开始了第二次征集，此后 DES 在1976年成为美国联邦标准。
推荐视频教程：（下面是 Youtube 视频，如果您没有挂代理，可能无法正常显示）。
另外，推荐文字教程：
- DES的维基百科： 数据加密标准
- DES中用到的常量表：DES补充材料
- 一个非常详细的示例，可以用来验证自己实现的DES程序： How does DES works
DES 概述
DES 的功能是：给定一个 64 位的明文和一个 64 位的密钥，输出一个 64 位的密文。这个密文可以用相同的密钥解密。所谓“64位的密钥”，其实里面只有54位在起作用。剩余的位可以直接丢弃，或者当作奇偶校验位。
虽然 DES 一次只能加密 8 个字节，但我们只需要把明文划分成每 8 个字节一组的块，就可以实现任意长度明文的加密。如果明文长度不是 8 个字节的倍数，还得进行填充。现在流行的填充方式是 PKCS7 / PKCS5，都是很简单的思路，用于把任意长度的文本填充成 8 字节的倍数长，也能方便地恢复原文，这里不再赘述。此外，独立地对每个块加密，最后直接拼起来是不行的（这种方式称为“电子密码本”，ECB 模式。它会导致明文中重复的块，加密结果也重复，这对于图片之类的数据来说几乎是致命的）。这个问题我们将在以后的博文中探讨。
DES 有一个非常不平凡的性质——加密与解密算法几乎一模一样。这大大简化了软件和硬件的设计。写完了加密算法，给它加上一行（倒转子密钥的顺序），就是一个解密算法了。这将给我们的编程带来帮助。
在这篇文章中，我们只关注一个核心任务——如何把 64 位的明文，用 64 位的密钥，加密成 64 位的密文，并执行解密。
DES 算法框架
DES 算法是在 Feistel network （费斯妥网络）的基础上执行的。以下是 DES 算法的流程图：
可以看到整个算法分为两大部分——迭代加密（左边的 16 轮迭代操作），以及密钥调度（右边生成子密钥的算法）。
所谓密钥调度，就是从一把 64-bit 的主钥匙，得到 16 把 48-bit 的子钥匙，然后把这些子钥匙用于迭代加密。那么，如何从一把主钥匙得到 16 把子钥匙呢？
- 从 64-bit 的主钥匙里面选取特定的 56 位，其余的位就没用了。于是我们现在手上有了一个 56 位的布尔数组。把它分成左、右两个半密钥，它们都是 28-bit 的布尔数组。
- 左、右两个半密钥都左旋（也就是循环左移。整个数组往左移，左边弹出去了的东西补到最右边去）一定位数，这个左移的位数也是指定的。有些轮次是 1 位，有些轮次是 2 位。
- 把左、右半密钥拼起来，再做一个置换，就得到了这一轮生成的子密钥。这个置换是从 56-bit 的数组里面选取指定的 48 位。所以现在每一轮都可以生成一个 48 位的子密钥。（注意，步骤 3 并不改变左右半密钥）。
- 重复 步骤 2、步骤 3 一共 16 次，于是得到了 16 个 48-bit 的子密钥。
现在我们手上有了 16 把子密钥。遂开始加密：
- 输入的明文（长度为 64 的布尔数组）做一个置换(IP置换)。仍然得到 64-bit 的数组（不然就丢失信息了！）
- 把得到的数组拆成左、右两半边。每边是 32 位长度。
- 每一轮迭代，都是接收一组
L, R，返回L', R'，作为下一轮迭代的L, R. 迭代过程如下：
$$\begin{aligned} L' &= R \\ R' &= L \oplus F(R, subkey)\end{aligned}$$其中 $F$ 函数（称为轮函数）是整个算法的核心，功能是：以一个子密钥，加密 32-bit 的信息。 - 利用之前得到的 16 个子密钥，执行步骤 3 一共 16 次。
- 将最终的 R 与 L 拼接，再做一次置换(FP置换)，即得到密文。
以上就是整个 DES 算法的加密过程。而解密过程与加密过程几乎一致，唯一的不同之处是：解密过程中子密钥的使用顺序，是与加密过程使用子密钥的顺序相反的。
在谈论 DES 算法的细节之前，笔者想先介绍几个密码学中的基本概念。
混淆和扩散
1945年，Shannon 提出了设计密码体制的两种基本方法——混淆(confusion)、扩散(diffusion).
混淆： 使密文与密钥之间的关系变得复杂。
本博客之前讨论过“维吉尼亚密码”的分析密钥长度攻击。它是利用了密文的一些统计学特征，来推测出密钥的长度。一个优秀的密码系统，应该很难通过几组密文推断出密钥的特征。
扩散：使明文与密文的关系变得复杂。
常常体现为：明文的任何一个bit的变动，都会对密文产生翻天覆地的变化。
我们之前讨论过针对 Many-Time-Pad 的攻击。这种攻击就是利用了“明文的异或等于密文的异或”这种特征，使得攻击者轻易地得到了明文的大量统计信息，帮助攻击者攻破密码体系。
在实践上，一些非线性的操作可以实现“混淆”。例如乘法（乘法对二进制位有很复杂的改变。回顾一下学《数字逻辑》的时候，一个乘法器需要大量的逻辑门才能实现）、S盒（Substitution-box，替换盒。就是一个特定的函数，其映射关系是精心设计以对抗攻击的）。DES 体系在轮函数中采用了 S-box.
一则小故事：DES 提出的时候，由于 S 盒来历不明，以及传说 NSA 唆使 IBM 公司把有效密钥长度从 64 位减少到 56 位，DES 被怀疑有 NSA 留下的后门。直到上世纪 90 年代， “差分密码攻击”被公开提出，相关质疑终于消解 —— DES 的 S 盒，恰到好处地提供了对差分密码攻击的超强防御能力；而如果采用随机的 S 盒，抗差分密码攻击的能力则大大减弱。
事实上，IBM 的研究员们早在 70 年代就已经发现了差分密码攻击方法，并针对此攻击方式特殊构建了 S 盒。出于国家安全的考虑，NSA 要求 IBM 保守秘密，于是差分密码攻击方法在二十余年后才得以重新被其他人发现。
至于对“扩散”的实现，一般采用线性变换、置换、循环移位等手段。多次迭代可以大大增强混淆和扩散的强度，使密文、明文、密钥之间的关系异常复杂，以至于攻击者极其难以分析。
编码与加密
编码(encode)与加密(encrypt)都是把一条数据变成另一条数据的函数，但它们有本质的区别——编码是公开的，是双向函数。任何人都可以把信息编码，也可以把信息解码。典型例子：十六进制编码、base64编码，以及 rot13 “加密”。它虽然名字是加密，但它事实上是一个编码——任何知道算法规则的人，都可以进行解密。
加密是私密的。必须有密钥才能加密，也必须有密钥才能解密（公钥与私钥可能不同）。此外，优秀的加密算法，安全性应该依赖于密钥的保密程度、解密的难度，而无关乎算法的秘密——也就是说，任何人都知道这个加密、解密算法是怎样的，任何人都可以实现算法，但拿不到密钥就没法解密。典型的例子是 RSA、DES、AES 等密码体系。
应当意识到，编码是不可靠的。置换之类的简单编码方式尤其不可靠。作为密码的设计者，应当假设攻击者知道算法的每一处细节，也就是说，设计算法的时候，应该认为编码对信息安全完全没有帮助。
有了这些概念在心里，我们来详细讨论 DES 算法。
密钥调度算法
来看 DES 是如何通过一把主密钥，造出 16 把子密钥的。图示如下：
首先，采用“选择置换1 (PC-1)”，从 64 位 key 里面选出 56 位。这一步属于encode，对信息安全没有帮助。PC-1 方法如下：
# 选择置换1，输入 key 为长度为 64 的 0/1 数组
# 从64位输入密钥中选择56位，分为左右两个28位半密钥
def PC1(key):
pc1_l = [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]
pc1_r = [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]
return [key[x-1] for x in pc1_l], [key[x-1] for x in pc1_r]经过 PC-1 之后，我们有了左、右两个半密钥，长度都是 28 位。接下来，我们每一轮把左、右半密钥左旋几位，再调用 PC-2 方法来造子密钥。框架如下：
# 子密钥生成算法，由一个64位主密钥导出16个48位子密钥
def keyGen(key):
assert len(key) == 64
l, r = PC1(key)
off = [1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1]
res = []
for x in range(16):
l = leftRotate(l, off[x])
r = leftRotate(r, off[x])
res.append(PC2(l + r))
return res 其中， leftRotate 是循环左移，实现如下：
# 循环左移off位
def leftRotate(a, off):
return a[off:] + a[:off]
assert leftRotate([0, 1, 0, 1, 1], 2) == [0, 1, 1, 0, 1]PC-2 又是一个简单置换，用于从左右半密钥拼起来的 56 位密钥中，选取 48 位作为一个子密钥。实现如下：
# 选择置换2
# 从56位的密钥中选取48位子密钥
def PC2(key):
assert len(key) == 56
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]
return [key[x-1] for x in pc2] 这样，我们就实现了密钥调度算法。执行 keyGen ，即可获得 16 把子密钥，长度均为 48-bit. 不难看出，整个密钥调度的过程都是对主密钥的 encode. 生成这么多子密钥的目的，是使得加密迭代变得更加复杂、难以分析。
加密迭代
加密迭代的过程已经描述过。先把信息进行一次初始置换(IP置换)；再进行 16 轮迭代；最后再给 (R+L) 这个数组来一次最终置换(FP置换)，即可输出作为密文。框架如下：
def DES(plain, key, method):
subkeys = keyGen(int2bin(key, 64))
if method == 'decrypt':
subkeys = subkeys[::-1]
m = IP(int2bin(plain, 64))
l, r = np.array(m, dtype=int).reshape(2, -1).tolist()
for i in range(16):
l, r = goRound(l, r, subkeys[i])
return bin2int(FP(r + l)) 在这里， goRound 是提供 L, R 和本轮加密使用的子密钥，返回 L', R' 以供下一轮迭代。 IP 和 FP 都是简单置换，对于密码安全没有任何意义，只是一个历史遗留原因。规定如下：
# 初始置换
def IP(a):
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]
return [a[x-1] for x in ip]
testM = [0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1]
assert IP(testM) == [1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0]
# 最终置换
def FP(a):
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]
return [a[x-1] for x in fp] 注意到 FP 就是 IP 的逆函数。这是为了保证“加密、解密算法几乎完全相同”。而至于 goRound ，我们知道它干的事情是$$\begin{aligned} L' &= R \\ R' &= L \oplus F(R, subkey)\end{aligned}$$代码实现如下：
def goRound(l, r, subKey):
return r, binXor(l, Feistel(r, subKey))因此，DES 的安全性在很大程度上取决于 F 函数，也就是轮函数。那么 Feistel 函数是干了什么事呢？来看下面一张流程图：
一个 32-bit 的块，经过一个扩张(Expand函数)，变成 48 位，然后与子密钥异或。得到的 48-bit 的结果分为 8 组，每一组是 6-bit 的数据，丢进对应的 S 盒，输出 4-bit 的信息。把这些输出收集起来，一共是 4*8 = 32 位，做一次置换 (P 置换)，得到 32-bit 的结果。这与输进来的 32-bit 信息是等长度的。
# F函数，用于处理一个半块
def Feistel(a, subKey):
assert len(a) == 32
assert len(subKey) == 48
t = binXor(Expand(a), subKey)
t = S(t)
t = P(t)
return tExpand 算法是指定的，P 置换是一个简单置换，因此都是 encode 过程。而这个 32-bit 的半块与 subkey 的混合过程，以及 S 盒提供的强有力的混淆能力，提供了 DES 体系的核心安全性。
Expand 算法如下：
# 扩张置换，将32位的数据扩展到48位
def Expand(a):
assert len(a) == 32
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]
return [a[x-1] for x in e]P 置换如下：
# P置换
def P(a):
assert len(a) == 32
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]
return [a[x-1] for x in p]需要注意一点：这个 P 置换是精心设计的，使得这一轮同一个 S 盒 输出的四个 bit，在下一回合的扩张之后，交由四个不同的 S 盒去处理。
接下来唯一要处理的就是 S 盒了。它一共有 8 张表，表长成下面这个样子：
什么意思呢？扩张之后的半块与子密钥异或之后，得到了 48 位结果；这些结果分成 8 个组，然后第一组使用 S1 这张表进行变换，第二组使用 S2 进行变换……依次类推。现在我们假设第二组是 101100 ，来看它在 S盒变换之后会得到什么结果：
由于这是第二组，故查询 S2 表。
它的首位、末尾是10，故查询第三行(1yyyy0行)。
它的中间 4 位是0110，查表知结果是 13.
把 13 转为二进制，得到1101，于是这就是输出。
代码实现也很简便：
# S盒变换，输入48位，输出32位
def S(a):
assert len(a) == 48
S_box = [[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]]
a = np.array(a, dtype=int).reshape(8, 6)
res = []
for i in range(8):
# 用 S_box[i] 处理6位a[i]，得到4位输出
p = a[i]
r = S_box[i][bin2int([p[0], p[5], p[1], p[2], p[3], p[4]])]
res.append(int2bin(r, 4))
res = np.array(res).flatten().tolist()
assert len(res) == 32
return res 到此为止，我们完整实现了 F 函数。有一个很有趣的事实——利用同一个子密钥，连续做两次 goRound ，等于什么也没做。请看：
print(l, r)
# [1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
# [1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0]
p, q = goRound(l, r, subkeys[0])
print(goRound(q, p, subkeys[0]))
# [1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0]
# [1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
同样的迭代循环，以特定方式连续做两次，等于什么也没做！这就是 DES 加密、解密算法几乎一致的原因所在。把加密、解密的流程图上下拼在一起，中间就会像消消乐一样不停地抵消（解密与加密使用 subkey 的顺序恰好是反的，所以最中间的两个操作会相互抵消），直到最后变得什么改变也没有——因此，这个解密做法是正确的。
所以，DES 加密解密算法就实现了。来看一个 DES 加密的例子(ECB模式就是每块单独加密)：
用这个例子来验证我们刚刚写的程序。明文为 0x11aabbccddeeff ，密钥为 0xcafababedeadbeaf . 按照 PKCS5 填充标准，实际交由 DES 加密的数据是 0x11aabbccddeeff01.来看我们的算法是不是输出 0x2973a7e54ec730a3 ：
print(hex(DES(0x11aabbccddeeff01, 0xcafababedeadbeaf, 'encrypt')))
# 0x2973a7e54ec730a3
print(hex(DES(0x2973a7e54ec730a3, 0xcafababedeadbeaf, 'decrypt')))
# 0x11aabbccddeeff01说明我们对算法的实现是正确的。Congratulations!
我们将在接下来的文章中讨论几种 DES 的工作方式，以及 DES 的安全性。最后，附上完整的加密、解密代码。
from functools import reduce
import numpy as np
# 整数转二进制数组，指定位长 n，大端序
def int2bin(a, n):
assert 0<=n and a < 2**n
res = np.zeros(n, dtype = int)
for x in range(n):
res[n-x-1] = a % 2
a = a // 2
return res.tolist()
assert int2bin(0x1a, 10) == [0, 0, 0, 0, 0, 1, 1, 0, 1, 0]
# 二进制数组转整数，大端序
def bin2int(a):
return reduce(lambda x,y: x*2+y, a)
assert bin2int([0, 0, 0, 0, 0, 1, 1, 0, 1, 0]) == 0x1a
# 循环左移off位
def leftRotate(a, off):
return a[off:] + a[:off]
assert leftRotate([0, 1, 0, 1, 1], 2) == [0, 1, 1, 0, 1]
# 异或
def binXor(a, b):
assert len(a) == len(b)
return [x^y for x, y in zip(a, b)]
assert binXor([1, 1, 0, 1], [0, 1, 1, 0]) == [1, 0, 1, 1]
# 初始置换
def IP(a):
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]
return [a[x-1] for x in ip]
testM = [0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1]
assert IP(testM) == [1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0]
# 最终置换
def FP(a):
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]
return [a[x-1] for x in fp]
# 选择置换1
# 从64位输入密钥中选择56位，分为左右两个28位半密钥
def PC1(key):
pc1_l = [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]
pc1_r = [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]
return [key[x-1] for x in pc1_l], [key[x-1] for x in pc1_r]
testKey = [0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1]
testL, testR = PC1(testKey)
assert testL + testR == [1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1]
# 选择置换2
# 从56位的密钥中选取48位子密钥
def PC2(key):
assert len(key) == 56
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]
return [key[x-1] for x in pc2]
# 子密钥生成算法，由一个64位主密钥导出16个48位子密钥
def keyGen(key):
assert len(key) == 64
l, r = PC1(key)
off = [1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1]
res = []
for x in range(16):
l = leftRotate(l, off[x])
r = leftRotate(r, off[x])
res.append(PC2(l + r))
return res
assert keyGen(testKey)[-1] == [1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1]
# S盒变换，输入48位，输出32位
def S(a):
assert len(a) == 48
S_box = [[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]]
a = np.array(a, dtype=int).reshape(8, 6)
res = []
for i in range(8):
# 用 S_box[i] 处理6位a[i]，得到4位输出
p = a[i]
r = S_box[i][bin2int([p[0], p[5], p[1], p[2], p[3], p[4]])]
res.append(int2bin(r, 4))
res = np.array(res).flatten().tolist()
assert len(res) == 32
return res
# 扩张置换，将32位的半块扩展到48位
def Expand(a):
assert len(a) == 32
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]
return [a[x-1] for x in e]
# P置换
def P(a):
assert len(a) == 32
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]
return [a[x-1] for x in p]
# F函数，用于处理一个半块
def Feistel(a, subKey):
assert len(a) == 32
assert len(subKey) == 48
t = binXor(Expand(a), subKey)
t = S(t)
t = P(t)
return t
def goRound(l, r, subKey):
return r, binXor(l, Feistel(r, subKey))
def DES(plain, key, method):
subkeys = keyGen(int2bin(key, 64))
if method == 'decrypt':
subkeys = subkeys[::-1]
m = IP(int2bin(plain, 64))
l, r = np.array(m, dtype=int).reshape(2, -1).tolist()
for i in range(16):
l, r = goRound(l, r, subkeys[i])
return bin2int(FP(r + l))
print(hex(DES(0x11aabbccddeeff01, 0xcafababedeadbeaf, 'encrypt')))
# 0x2973a7e54ec730a3
print(hex(DES(0x2973a7e54ec730a3, 0xcafababedeadbeaf, 'decrypt')))
# 0x11aabbccddeeff01