对称加密算法-DES

密钥处理

概述

1. DES的64位密钥只是用来初始化分别作用于16轮中每一轮的48位密钥，64位密钥中有效的只有56位，其中8的倍数位（从1开始数，第8，16，……，64位）无作用。
   1. 64位密钥K经过PC-1置换矩阵压缩成56位置换密钥K+
   2. K+密钥每28位一组拆分成两组C0和D0
   3. C0和D0分别参考移位次数表进行以位为单位的循环左移，构造(C1，C1), (C2，D2)，……，(C16，D16)
   4. Cn和Dn合并成56位密钥，经过PC-2置换矩阵压缩成48位密钥，作为加密密钥Kn(K1, K2, …, K16)，直接作用于轮函数f

详细步骤

1. 64位密钥K经PC-1置换压缩成56位，置换矩阵如下表。57表示K+的第一位等于64位密钥K中的第57位，49表示K+的第二位等于K的第49位，以此类推。最终可以生成56位的置换密钥K+。从表中可以看出不存在8的倍数位。

   # Compression Permutation 1: 64 bits --> 56 bits
   PC_1 = [
      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,
   ]

   • 64位K = 00010011 00110100 01010111 01111001 10011011 10111100 11011111 11110001
   • 56位K+ = 1111000 0110011 0010101 0101111 0101010 1011001 1001111 0001111

   # sequence: 64位K
   # permutation: PC_1
   # 返回: K+
   def permute(sequence, permutation):
      result = [sequence[i - 1] for i in permutation]
      return result

2. 将56位密钥K+每28位一组拆分成两组C0和D0

   • K+ = 1111000 0110011 0010101 0101111 0101010 1011001 1001111 0001111
   • C0 = 1111000011001100101010101111
   • D0 = 0101010101100110011110001111

3. 移位表如下，n表示第几轮，count表示移位数。以位为单位分别将Cn-1，Dn-1循环左移“轮数n对应的移位次数（1或2）”，得到（Cn，Dn）。轮数从1开始。

   | n     | 1, 2, 9, 16 | other |
   | count | 1           | 2     |
   
   SHIFT_TABLE = [
      1, 1, 2, 2,
      2, 2, 2, 2,
      1, 2, 2, 2,
      2, 2, 2, 1
   ]

   • C0 = 1111000011001100101010101111
     D0 = 0101010101100110011110001111
   • C1 = 1110000110011001010101011111
     D1 = 1010101011001100111100011110
   • C2 = 1100001100110010101010111111
     D2 = 0101010110011001111000111101
   • C3 = 0000110011001010101011111111
     D3 = 0101011001100111100011110101
   • C4 = 0011001100101010101111111100
     D4 = 0101100110011110001111010101
   • C5 = 1100110010101010111111110000
     D5 = 0110011001111000111101010101
   • C6 = 0011001010101011111111000011
     D6 = 1001100111100011110101010101
   • C7 = 1100101010101111111100001100
     D7 = 0110011110001111010101010110
   • C8 = 0010101010111111110000110011
     D8 = 1001111000111101010101011001
   • C9 = 0101010101111111100001100110
     D9 = 0011110001111010101010110011
   • C10 = 0101010111111110000110011001
     D10 = 1111000111101010101011001100
   • C11 = 0101011111111000011001100101
     D11 = 1100011110101010101100110011
   • C12 = 0101111111100001100110010101
     D12 = 0001111010101010110011001111
   • C13 = 0111111110000110011001010101
     D13 = 0111101010101011001100111100
   • C14 = 1111111000011001100101010101
     D14 = 1110101010101100110011110001
   • C15 = 1111100001100110010101010111
     D15 = 1010101010110011001111000111
   • C16 = 1111000011001100101010101111
     D16 = 0101010101100110011110001111

   # 56位 --> 56位: (C0, D0) --> (C1, D1) --> ... --> (C16, D16)
   # cndn: (C0, D0)
   # shift_table: SHIFT_TABLE
   # 返回: 列表[(C0, D0), (C1, D1), ..., (C16, D16)]
   def shift(cndn, shift_table):
      result = []
      for i in range(len(shift_table)):
         # 每28位一组，分两组：c, d
         c = cndn[0:28]
         d = cndn[28:]
         # 移位次数
         shift_count = shift_table[i]
         # c移位
         c.extend(c[0:shift_count])
         c[0:shift_count] = []
         # d移位
         d.extend(d[0:shift_count])
         d[0:shift_count] = []
         # 合并c，d
         cndn = c + d
         result.append(cndn)
      return result

4. Cn和Dn合并成56位密钥，经过PC-2置换矩阵压缩成48位密钥，作为加密密钥Kn(K1, K2, …, K16)。14表示56位密钥CnDn中第14位作为48位密钥Kn的第1位，17表示CnDn中的第17位作为Kn的第2位，以此类推。生成16个48位密钥，在16轮加密过程中分别作用于相应轮n中的函数f。

    # Compression Permutation 2: 56 bits --> 48 bits
   PC_2 = [
      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,
   ]

   • K1 = 000110 110000 001011 101111 111111 000111 000001 110010
   • K2 = 011110 011010 111011 011001 110110 111100 100111 100101
   • K3 = 010101 011111 110010 001010 010000 101100 111110 011001
   • K4 = 011100 101010 110111 010110 110110 110011 010100 011101
   • K5 = 011111 001110 110000 000111 111010 110101 001110 101000
   • K6 = 011000 111010 010100 111110 010100 000111 101100 101111
   • K7 = 111011 001000 010010 110111 111101 100001 100010 111100
   • K8 = 111101 111000 101000 111010 110000 010011 101111 111011
   • K9 = 111000 001101 101111 101011 111011 011110 011110 000001
   • K10 = 101100 011111 001101 000111 101110 100100 011001 001111
   • K11 = 001000 010101 111111 010011 110111 101101 001110 000110
   • K12 = 011101 010111 000111 110101 100101 000110 011111 101001
   • K13 = 100101 111100 010111 010001 111110 101011 101001 000001
   • K14 = 010111 110100 001110 110111 111100 101110 011100 111010
   • K15 = 101111 111001 000110 001101 001111 010011 111100 001010
   • K16 = 110010 110011 110110 001011 000011 100001 011111 110101

   # sequence: [(C0, D0), (C1, D1), ..., (C16, D16)]
   # permutation: PC_2
   # 返回: 列表[K1, K2, ..., K16]
   def permute(sequence, permutation):
      result = [sequence[i - 1] for i in permutation]
      return result

加密过程

概述

1. 明文以64位为单位进行分组，如果采用最简单但最不安全的ECB模式加密，则64位分组之间都是独立加密。如果明文长度不是64位的整数倍，明文就需要填充，一般逐位填充0直到二进制长度为64的整数倍。
   1. 64位明文分块M经过IP（initial permutation ）置换矩阵进行搅乱，生成64位块IP。
   2. 将块IP每32位分成两组L0 和 R0。
   3. 根据Ln-1 和 Rn-1计算（Ln，Rn）。计算过程涉及到轮函数f。
   4. 将最后一组（L16，R16）交换位置（R16，L16），经过IP-1 置换矩阵生成密文。
   5. M –> IP（L0 ，R0）–>（L1，R1）–>（L2，R2）–>（Ln，Rn）–>（L16，R16）–>（R16，L16）– > C

详细过程

1. 64位明文分块M经过IP（initial permutation ）置换矩阵进行搅乱，生成64位块IP。下表中58表示明文块M中的第58位作为IP的第1位，50表示明文块M中的第50位作为IP的第2位。

   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,
   ]

   • 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

   # sequence: 64位明文块M
   # permutation: IP
   # 返回: 64位混淆后的明文
   def permute(sequence, permutation):
      result = [sequence[i - 1] for i in permutation]
      return result

2. 每32位一组分割IP为两组，L0 和R0

   • IP = 1100 1100 0000 0000 1100 1100 1111 1111 1111 0000 1010 1010 1111 0000 1010 1010
   • L0 = 1100 1100 0000 0000 1100 1100 1111 1111
   • R0 = 1111 0000 1010 1010 1111 0000 1010 1010

3. Feistal网络，每一轮加密如下，n代表第几轮（1，2，……，16）。关键步骤在轮函数f。

   1. Ln = Rn-1

      • L1 = R0 = 1111 0000 1010 1010 1111 0000 1010 1010

   2. Rn = Ln-1 xor f(Rn-1,Kn)

      • R1 = L0 xor f(R0, K1) = 1110 1111 0100 1010 0110 0101 0100 0100

        def festial(ip_seq, key_set, mode):
              left = ip_seq[0:32]
              right = ip_seq[32:]
              # 2. Festial网络
              # 确定加密还是解密
              if mode == "enc":
                  rou_num = range(0, 16)
              else:
                  rou_num = range(15, -1, -1)
              for i in rou_num:
                  key_seq = key_set[i]
                  f_value = f(right, key_seq)
                  zipped = zip(left, f_value)
                  # 异或运算
                  left, right = right, [i[0] ^ i[1] for i in zipped]
              return left, right

   3. 轮函数f(Rn-1,Kn)过程：32位Rn-1扩充得到48位E(Rn-1) –》Kn xor E(Rn-1) –》6位一组共8组经过8个S盒压缩成32位 –》P矩阵置换–》输出Rn。

      1. 由于Rn-1是32位，而Kn是48位，因此在轮函数f中需要将Rn-1经过置换矩阵E扩充到48位。下表中32表示E(Rn-1)的第1位等于Rn-1中第32位，1表示E(Rn-1)的第2位等于Rn-1中第1位，表中会有重复的数字，这是必然的（因为要扩充）。如表中最后一位（E(Rn-1)第48位）为1表示第48位等于Rn-1的第1位。

         # Expansion Permutation
         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,
         ]

         • R0 = 1111 0000 1010 1010 1111 0000 1010 1010

         • E(R0) = 011110 100001 010101 010101 011110 100001 010101 010101

         # 1. 扩充: 32位R --> 48位E(R)
         # sequence: R
         # permutation: E
         # 返回: 48位E(R)
         r = permute(r, box.E)

      2. 将Kn 和 E(Rn-1)异或运算，即Kn xor E(Rn-1)。

         • K1 = 000110 110000 001011 101111 111111 000111 000001 110010
         • E(R0) = 011110 100001 010101 010101 011110 100001 010101 010101
         • K1 XOR E(R0) = 011000 010001 011110 111010 100001 100110 010100 100111

         # 2. 异或运算: E(R) xor KEY
         zipped = zip(r, key_seq)
         r_xor_key = [i[0] ^ i[1] for i in zipped]

      3. 将Kn xor E(Rn-1)每6位一组可分8组，Kn xor E(Rn-1) = B1B2B3B4B5B6B7B8。根据Bi的索引i从8个S盒中选择相应的的Si盒，计算Si(Bi)。S盒为4*16矩阵，将6位分组Bi中的第一位和最后一位组合形成2位二进制值（刚好可以表示4种状态）作为Si盒的行（row）索引，中间4位二进制值（刚好可以表示16种状态）作为Si盒的列（column）索引。根据row和column定位得到的16进制值（4位二进制位）即为Si(Bi)。最终输出32位（S(B1)，S2(B2)，……，S8(B8)）。。

         S1盒
         | row\column |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|
         
         S1 = [
            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,
         ]
         S2 = [
            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,
         ]
         S3 = [
            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,
         ]
         S4 = [
            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,
         ]
         S5 = [
            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,
         ]
         S6 = [
            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,
         ]
         S7 = [
            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,
         ]
         S8 = [
            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,
         ]
         S = [S1, S2, S3, S4, S5, S6, S7, S8]

         • K1 XOR E(R0) = 011000 010001 011110 111010 100001 100110 010100 100111

         • B1 = 011000

         • S1(B1) 索引为（00， 1100） = （0，12）= 5 = 0101

         • S1(B1)S2(B2)S3(B3)S4(B4)S5(B5)S6(B6)S7(B7)S8(B8) = 0101 1100 1000 0010 1011 0101 1001 0111

         # 3. S盒置换: 48位 --> 32位
         result = []
         for i in range(8):
            s = box.S[i]
            base = i * 6
            row = r_xor_key[base] * 2 + r_xor_key[base + 5]
            column = r_xor_key[base + 1] * 8 + r_xor_key[base + 2] * 4 + r_xor_key[base + 3] * 2 + r_xor_key[base + 4]
            temp = s[row * 16 + column]
            result.extend([int(j) for j in bin(temp)[2:].zfill(4)])

      4. S1(B1)S2(B2)S3(B3)S4(B4)S5(B5)S6(B6)S7(B7)S8(B8)经过P矩阵混淆（不扩充和压缩）

         |             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   |

         • S1(B1)S2(B2)S3(B3)S4(B4)S5(B5)S6(B6)S7(B7)S8(B8) = 0101 1100 1000 0010 1011 0101 1001 0111

         • f(Rn-1,Kn) = 0010 0011 0100 1010 1010 1001 1011 1011

         # 4. 搅乱置换: 32位 --> 32位
         result = permute(result, box.P)

4. 将第16轮的输出（L16，R16）颠倒形成（R16，L16），通过IP-1 置换矩阵就生成了密文。40表示（R16，L16）的第40位作为密文C的第1位，8表示（R16，L16）的第8位作为密文C的第2位。

   |                         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   |

   • M = 0123456789ABCDEF

   • C = 85E813540F0AB405

   # 交换left，right的位置
   right.extend(left)
   # 3. 置换 32位 --> 32位
   result = permute(right, box.IP_1)

   参考

5. 全部都是盗取于此

6. 不详细但更漂亮