DES是一种对称密钥的块加密算法。谓之 “对称密钥”,是因为加密、解密用的密钥是一样的(这不同于 RSA 等非对称密钥体系)。谓之 “块加密”,是因为这种算法把明文划分为很多个等长的块(block),对每个块进行加密,最后以某种手段拼在一起。“块加密”亦称“分组加密”。

  1973年,NSA向社会征集满足安全要求的加密算法。1973-1974年,IBM研发了 DES 加密算法。1974年,NSA开始了第二次征集,此后 DES 在1976年成为美国联邦标准。

  推荐视频教程:(下面是 Youtube 视频,如果您没有挂代理,可能无法正常显示)。

  另外,推荐文字教程:


DES 概述

  DES 的功能是:给定一个 64 位的明文和一个 64 位的密钥,输出一个 64 位的密文。这个密文可以用相同的密钥解密。所谓“64位的密钥”,其实里面只有54位在起作用。剩余的位可以直接丢弃,或者当作奇偶校验位。

  虽然 DES 一次只能加密 8 个字节,但我们只需要把明文划分成每 8 个字节一组的块,就可以实现任意长度明文的加密。如果明文长度不是 8 个字节的倍数,还得进行填充。现在流行的填充方式是 PKCS7 / PKCS5,都是很简单的思路,用于把任意长度的文本填充成 8 字节的倍数长,也能方便地恢复原文,这里不再赘述。此外,独立地对每个块加密,最后直接拼起来是不行的(这种方式称为“电子密码本”,ECB 模式。它会导致明文中重复的块,加密结果也重复,这对于图片之类的数据来说几乎是致命的)。这个问题我们将在以后的博文中探讨。

  DES 有一个非常不平凡的性质——加密与解密算法几乎一模一样。这大大简化了软件和硬件的设计。写完了加密算法,给它加上一行(倒转子密钥的顺序),就是一个解密算法了。这将给我们的编程带来帮助。

  在这篇文章中,我们只关注一个核心任务——如何把 64 位的明文,用 64 位的密钥,加密成 64 位的密文,并执行解密。

DES 算法框架

  DES 算法是在 Feistel network (费斯妥网络)的基础上执行的。以下是 DES 算法的流程图:

source: http://homepage.usask.ca/~dtr467/400/

  可以看到整个算法分为两大部分——迭代加密(左边的 16 轮迭代操作),以及密钥调度(右边生成子密钥的算法)。

  所谓密钥调度,就是从一把 64-bit 的主钥匙,得到 16 把 48-bit 的子钥匙,然后把这些子钥匙用于迭代加密。那么,如何从一把主钥匙得到 16 把子钥匙呢?

  1. 从 64-bit 的主钥匙里面选取特定的 56 位,其余的位就没用了。于是我们现在手上有了一个 56 位的布尔数组。把它分成左、右两个半密钥,它们都是 28-bit 的布尔数组。
  2. 左、右两个半密钥都左旋(也就是循环左移。整个数组往左移,左边弹出去了的东西补到最右边去)一定位数,这个左移的位数也是指定的。有些轮次是 1 位,有些轮次是 2 位。
  3. 把左、右半密钥拼起来,再做一个置换,就得到了这一轮生成的子密钥。这个置换是从 56-bit 的数组里面选取指定的 48 位。所以现在每一轮都可以生成一个 48 位的子密钥。(注意,步骤 3 并不改变左右半密钥)。
  4. 重复 步骤 2、步骤 3 一共 16 次,于是得到了 16 个 48-bit 的子密钥。

  现在我们手上有了 16 把子密钥。遂开始加密:

  1. 输入的明文(长度为 64 的布尔数组)做一个置换(IP置换)。仍然得到 64-bit 的数组(不然就丢失信息了!)
  2. 把得到的数组拆成左、右两半边。每边是 32 位长度。
  3. 每一轮迭代,都是接收一组 L, R,返回 L', R' ,作为下一轮迭代的 L, R . 迭代过程如下:
    $$\begin{aligned} L' &= R \\ R' &= L \oplus F(R, subkey)\end{aligned}$$其中 $F$ 函数(称为轮函数)是整个算法的核心,功能是:以一个子密钥,加密 32-bit 的信息。
  4. 利用之前得到的 16 个子密钥,执行步骤 3 一共 16 次。
  5. 将最终的 R 与 L 拼接,再做一次置换(FP置换),即得到密文。
迭代加密过程。图片来源:wikipedia

  以上就是整个 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 把子密钥的。图示如下:

密钥调度算法。 图片来源: wikipedia 

首先,采用“选择置换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' 以供下一轮迭代。 IPFP 都是简单置换,对于密码安全没有任何意义,只是一个历史遗留原因。规定如下:

# 初始置换
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 函数是干了什么事呢?来看下面一张流程图:

轮函数。 图片来源:wikipedia 

  一个 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 t

  Expand 算法是指定的,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 张表,表长成下面这个样子:

S盒, wikipedia 

  什么意思呢?扩张之后的半块与子密钥异或之后,得到了 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模式就是每块单独加密):

利用 CyberChef 进行 DES加密

  用这个例子来验证我们刚刚写的程序。明文为 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