密码学 从入门到放弃 分组密码

发表于 分类于 阅读次数：

XMan Day2，整理一下bibi师傅的笔记。

分组密码部分。

分组密码【Block Cipher的数学模型是将明文消息编码表示后的数字【简称明文数字，划分成长度为n的组，每组分别在密钥的控制下变换成等长的密文，常见的有DES和AES这两大对称加密算法。

分组密码通常是按固定规模将明文分组，对每组均使用一个固定的加密变换来进行运算。

DES

功能简述

给定一个64位的明文和一个64位的密钥，输出一个64位的密文。这个密文可以用相同的密钥解密。

而64位的秘钥中，只有54位在起作用。剩余的位可以直接丢弃，或者当作奇偶校验位。

算法流程图

img
秘钥置换详解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
def left_rotate(res, offset):
    return res[offset:] + res[:offset]


def PC1(key):
    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]
    k1 = []
    for i in pc1:
        k1.append(key[i - 1])
    return k1[0:28], k1[28:56]


def PC2(key):
    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[i - 1] for i in pc2]


def key_generate(key):
    l, r = PC1(key)
    offset = [1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1]
    res = []
    for i in offset:
        l = left_rotate(l, i)
        r = left_rotate(r, i)
        res.append(PC2(l + r))
    return res

传入key后，第一轮先经pc1选择置换获得56位秘钥，然后拆分成左右两半。

得到左右两半秘钥后，经左偏移表分别偏移相应位数，拼接，再经pc2选择置换获得48位的子秘钥。

左偏移表长为16位，因此共计16轮，最后得到16组48位的子秘钥。

加密主体
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
def IP(message):
    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]
    m1 = []
    for i in ip:
        m1.append(message[i - 1])
    return m1[0:32], m1[32:64]


def FP(m):
    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 [m[i - 1] for i in fp]

def S(m):
    s = [[
        [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]
    ]]

    m = [m[i:i + 6] for i in range(0, len(m), 6)]
    res = []

    for i in range(8):
        p = m[i]
        z = int(str(p[0]) + str(p[5]), 2)
        h = int(str(p[1]) + str(p[2]) + str(p[3]) + str(p[4]), 2)
        r = s[i][z][h]
        for j in bin(r)[2:].zfill(4):
            res.append(int(j))
    return res


def Expand(m):
    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 [m[i - 1] for i in e]


def P(m):
    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 [m[i - 1] for i in p]


def cipher_function(m, sub_key):
    t = xor(Expand(m), sub_key)
    t = S(t)
    t = P(t)
    return t


def go_round(l, r, sub_key):
    return r, xor(l, cipher_function(r, sub_key))


def encrypt(plain, key):
    sub_keys = key_generate(key)
    l, r = IP(plain)
    for i in range(16):
        l, r = go_round(l, r, sub_keys[i])
    return FP(r + l)

在获取子秘钥后，先将明文经IP置换，同秘钥置换中的第一步一样，拆封成左右两半。

然后经过十六轮的运算【主要是看cipher_function函数。

在cipher_function函数中，先将半段长为32位的明文拓展为48位，然后同子秘钥异或。

接下来每6位为一组，分8组，对应8组S盒，取6位中的0和5为纵坐标，1到4位横坐标，取数。

比如第一组是110100的时候，取下标0和5，是10，第2行，取下标1到4，是1010，第10列，取数为9，转二进制是1001。

这样便把48位混淆后的密文转为32位了。

然后再将其经P置换。

如此十六轮运算后将得到的左右密文拼接，再经FP置换，得到最终结果。

解密过程

数据解密的算法与加密算法相同，区别在于扩展后同子秘钥进行按位异或的密钥的使用顺序不同，即解密时将生成的16组子秘钥逆序使用。

1
2
3
4
5
6
def decrypt(plain, key):
    sub_keys = key_generate(key)[::-1]
    l, r = IP(plain)
    for i in range(16):
        l, r = go_round(l, r, sub_keys[i])
    return FP(r + l)
完整代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
# 数值转2进制数组位数扩展
def int2bin(m, n):
    m = bin(m)[2:]
    if n >= len(m):
        m = m.zfill(n)
    else:
        m = m[len(m) - n:]
    res = []
    for i in m:
        res.append(int(i))
    return res


# 2进制数组转数值
def bin2int(a):
    s = ""
    for i in a:
        s += str(i)
    return int(s, 2)


# 异或
def xor(a, b):
    return [x ^ y for x, y in zip(a, b)]


# 左移
def left_rotate(res, offset):
    return res[offset:] + res[:offset]


# PC1盒置换
def PC1(key):
    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]
    k1 = []
    for i in pc1:
        k1.append(key[i - 1])
    return k1[0:28], k1[28:56]


# PC2盒置换
def PC2(key):
    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[i - 1] for i in pc2]


# 秘钥生成
def key_generate(key):
    l, r = PC1(key)
    offset = [1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1]
    res = []
    for i in offset:
        l = left_rotate(l, i)
        r = left_rotate(r, i)
        res.append(PC2(l + r))
    return res


# IP盒置换
def IP(message):
    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]
    m1 = []
    for i in ip:
        m1.append(message[i - 1])
    return m1[0:32], m1[32:64]


# FP盒置换
def FP(m):
    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 [m[i - 1] for i in fp]


# S盒置换
def S(m):
    s = [[
        [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]
    ]]

    m = [m[i:i + 6] for i in range(0, len(m), 6)]
    res = []

    for i in range(8):
        p = m[i]
        z = int(str(p[0]) + str(p[5]), 2)
        h = int(str(p[1]) + str(p[2]) + str(p[3]) + str(p[4]), 2)
        r = s[i][z][h]
        for j in bin(r)[2:].zfill(4):
            res.append(int(j))
    return res


# E盒扩展
def Expand(m):
    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 [m[i - 1] for i in e]


# P盒置换
def P(m):
    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 [m[i - 1] for i in p]


# 16轮加密
def cipher_function(m, sub_key):
    t = xor(Expand(m), sub_key)
    t = S(t)
    t = P(t)
    return t


# 交换左右子秘钥
def go_round(l, r, sub_key):
    return r, xor(l, cipher_function(r, sub_key))


# 加密
def encrypt(plain, key):
    sub_keys = key_generate(key)
    l, r = IP(plain)
    for i in range(16):
        l, r = go_round(l, r, sub_keys[i])
    return FP(r + l)


# 解密
def decrypt(plain, key):
    sub_keys = key_generate(key)[::-1]
    l, r = IP(plain)
    for i in range(16):
        l, r = go_round(l, r, sub_keys[i])
    return FP(r + l)


def des_encrypt(plain, key):
    # 字符串转16进制
    plain = int(plain.encode().hex(), 16)
    # 再转2进制数组
    plain_array = int2bin(plain, 64)
    # 秘钥转16进制
    key = int(key.encode().hex(), 16)
    # 再转2进制数组
    key_array = int2bin(key, 64)
    # 加密运算
    encrypt_array = encrypt(plain_array, key_array)
    # 2进制数组转数值
    encrypt_res = bin2int(encrypt_array)
    return encrypt_res


def des_decrypt(cipher, key):
    # 密文转2进制数组
    cipher_array = int2bin(cipher, 64)
    # 秘钥转16进制
    key = int(key.encode().hex(), 16)
    # 再转2进制数组
    key_array = int2bin(key, 64)
    # 解密运算
    decrypt_array = decrypt(cipher_array, key_array)
    # 2进制数组转16进制字符串
    decrypt_res = hex(bin2int(decrypt_array))[2:]
    return bytes.fromhex(decrypt_res).decode()


c = des_encrypt("south", "sea")
print(c)
m = des_decrypt(c, "sea")
print(m)
一些结论
  • IP与FP置换对于安全没有意义，是历史遗留问题，FP是IP的逆置换。
  • S盒作为DES算法中唯一的非线性器件，是加密的关键所在，然而，多年来，一直未有人将S盒的设计准则公开。
  • Expand拓展目的是在加密数据的过程中制造一些雪崩效应，使用数据块中的1位将在下一步操作中影响更多位，从而产生扩散效果。

例题 2019-CISCN-part_des

1
2
Round n part_encode-> 0x92d915250119e12b
Key map -> 0xe0be661032d5f0b676f82095e4d67623628fe6d376363183aed373a60167af537b46abc2af53d97485591f5bd94b944a3f49d94897ea1f699d1cdc291f2d9d4a5c705f2cad89e938dbacaca15e10d8aeaed90236f0be2e954a8cf0bea6112e84

题目名是part_des。

给了一个Round n part_encode，长度为64位，可知是第n轮加密的结果。

给了一个key_map，长度为768位，除16得48，可知是16把48位的子秘钥。

可知，这是DES加密的中间结果，需要对其进行解密。

因此将上述加密过程加以改造即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
# @Author: south
# @Date: 2022-05-16 21:57

# 数值转2进制数组位数扩展
def int2bin(m, n):
    m = bin(m)[2:]
    if n >= len(m):
        m = m.zfill(n)
    else:
        m = m[len(m) - n:]
    res = []
    for i in m:
        res.append(int(i))
    return res


# 2进制数组转数值
def bin2int(a):
    s = ""
    for i in a:
        s += str(i)
    return int(s, 2)


# 异或
def xor(a, b):
    return [x ^ y for x, y in zip(a, b)]


# 左移
def left_rotate(res, offset):
    return res[offset:] + res[:offset]


# PC1盒置换
def PC1(key):
    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]
    k1 = []
    for i in pc1:
        k1.append(key[i - 1])
    return k1[0:28], k1[28:56]


# PC2盒置换
def PC2(key):
    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[i - 1] for i in pc2]


# 秘钥生成
def key_generate(key):
    l, r = PC1(key)
    offset = [1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1]
    res = []
    for i in offset:
        l = left_rotate(l, i)
        r = left_rotate(r, i)
        res.append(PC2(l + r))
    return res


# IP盒置换
def IP(message):
    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]
    m1 = []
    for i in ip:
        m1.append(message[i - 1])
    return m1[0:32], m1[32:64]


# FP盒置换
def FP(m):
    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 [m[i - 1] for i in fp]


# S盒置换
def S(m):
    s = [[
        [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]
    ]]

    m = [m[i:i + 6] for i in range(0, len(m), 6)]
    res = []

    for i in range(8):
        p = m[i]
        z = int(str(p[0]) + str(p[5]), 2)
        h = int(str(p[1]) + str(p[2]) + str(p[3]) + str(p[4]), 2)
        r = s[i][z][h]
        for j in bin(r)[2:].zfill(4):
            res.append(int(j))
    return res


# E盒扩展
def Expand(m):
    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 [m[i - 1] for i in e]


# P盒置换
def P(m):
    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 [m[i - 1] for i in p]


# 16轮加密
def cipher_function(m, sub_key):
    t = xor(Expand(m), sub_key)
    t = S(t)
    t = P(t)
    return t


# 交换左右子秘钥
def go_round(l, r, sub_key):
    return r, xor(l, cipher_function(r, sub_key))


# 加密
def encrypt(plain, key):
    sub_keys = key_generate(key)
    l, r = IP(plain)
    for i in range(16):
        l, r = go_round(l, r, sub_keys[i])
    return FP(r + l)


# 解密
def decrypt(plain, key):
    sub_keys = key_generate(key)[::-1]
    l, r = IP(plain)
    for i in range(16):
        l, r = go_round(l, r, sub_keys[i])
    return FP(r + l)


def des_encrypt(plain, key):
    # 字符串转16进制
    plain = int(plain.encode().hex(), 16)
    # 再转2进制数组
    plain_array = int2bin(plain, 64)
    # 秘钥转16进制
    key = int(key.encode().hex(), 16)
    # 再转2进制数组
    key_array = int2bin(key, 64)
    # 加密运算
    encrypt_array = encrypt(plain_array, key_array)
    # 2进制数组转数值
    encrypt_res = bin2int(encrypt_array)
    return encrypt_res


def des_decrypt(cipher, key):
    # 密文转2进制数组
    cipher_array = int2bin(cipher, 64)
    # 秘钥转16进制
    key = int(key.encode().hex(), 16)
    # 再转2进制数组
    key_array = int2bin(key, 64)
    # 解密运算
    decrypt_array = decrypt(cipher_array, key_array)
    # 2进制数组转16进制字符串
    decrypt_res = hex(bin2int(decrypt_array))[2:]
    return bytes.fromhex(decrypt_res).decode()

# 拆成左右两半
part_encode = 0x92d915250119e12b
part_encode = bin(part_encode)[2:]
l_part_encode = [int(part_encode[i]) for i in range(32)]
r_part_encode = [int(part_encode[i]) for i in range(32, 64)]
# 子秘钥拆成16组
key = 0xe0be661032d5f0b676f82095e4d67623628fe6d376363183aed373a60167af537b46abc2af53d97485591f5bd94b944a3f49d94897ea1f699d1cdc291f2d9d4a5c705f2cad89e938dbacaca15e10d8aeaed90236f0be2e954a8cf0bea6112e84
key = bin(key)[2:]
sub_keys = []
for i in range(16):
    s_k = key[i * 48:(i + 1) * 48]
    k = []
    for j in s_k:
        k.append(int(j))
    sub_keys.append(k)


for s in range(16):
    # 正向加密
    l, r = l_part_encode, r_part_encode
    for i in range(s, 16):
        l, r = go_round(l, r, sub_keys[i])
    cipher_array = FP(r + l)
    # 解密
    s_k = sub_keys[::-1]
    l, r = IP(cipher_array)
    for i in range(16):
        l, r = go_round(l, r, s_k[i])
    decrypt_array = FP(r + l)
    decrypt_res = hex(bin2int(decrypt_array))[2:]
    print(bytes.fromhex(decrypt_res))

得到有意义的字符串为y0ur9Ood。

3DES

相当于是对每个数据块应用三次DES算法。

有3个独立密钥的3DES的密钥安全性为168位，但由于中途相遇攻击【知道明文和密文】，它的有效安全性仅为112位。

加密

密文 = Ek3(Dk2(Ek1(明文)))

不是Ek3(Ek2(Ek1(明文)))，是为允许3DES用户通过重复密钥来解密由旧的单个DES用户加密的数据。

即重复秘钥时，3DES降级为DES。

解密

明文 = Dk3(Ek2(Dk1(密文)))

常见出题思路

普通题目：CBC模式攻击、Feistel结构的简单攻击方法。

困难题目：需计算差分、积分、代数、MITM等。

ECB模式

相同的明文分组会被转换为相同的密文分组，一组16个字节，当最后一个明文分组的内容小于分组长度时，需要用一些特定的数据进行填充。

我们可以将其理解为是一个巨大的明文分组→密文分组的对应表，因此ECB模式也称为电子密码本模式。

因此，如果明文中存在多个相同的明文分组，则这些明文分组最终都将被转换为相同的密文分组。这样一来，只要观察一下密文，就可以知道明文存在怎样的重复组合，并可以以此为线索来破译密码，因此ECB模式存在一定风险，且攻击者无需破译密码就能操纵明文【交换密文块来颠倒语意。

區塊加密法工作模式- 維基百科，自由的百科全書

CBC模式

CBC模式的加密方式为分组后，第一组和作为偏移量的随机字符串异或后被另一个作为秘钥的随机字符串加密，得到的密文用作下一组明文加密前的异或字符串操作，因此其优于ECB模式的一点是不会被交换密文的方式颠倒语意。

區塊加密法工作模式- 維基百科，自由的百科全書

CBC比特翻转攻击

已知明文攻击，可以通过修改密文，来使密文解密出来的特定位置的字符变成我们想要的字符，但会使得前序密文无意义。

只需将上一组对应位置的字符与已知对应位置的明文和目标解密明文分别异或一次即可。

例题
1
2
3
4
5
6
7
8
9
10
11
12
import binascii

from Crypto.Cipher import AES

m = b"hahahahahahahaha=1;admin=0;uid=1"
key = b"1234567890abcdef"
iv = b"fedcba0987654321"
aes = AES.new(key, AES.MODE_CBC, iv)
c = aes.encrypt(m)
print(binascii.b2a_hex(c))

# 49a98685a527bdfa4077c400963a4e3c9effb4148566f10bce9e07ccbb731896

那么根据公式。

1
2
3
4
5
6
7
∵
Decrypt(Cipher[2][i]) = Cipher[1][i] ^ Plain[2][i]
Plain[2][i] == 0
Plain[2][i] → x
∴
Plain[2][i] ^ x = 0 ^ x = x
Decrypt(Cipher[2][i]) = Cipher[1][i] ^ Plain[2][i] ^ x

因此根据上述公式构造Payload来进行CBC翻转攻击使得admin=1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import binascii

from Crypto.Cipher import AES

m = b"hahahahahahahaha=1;admin=0;uid=1"
key = b"1234567890abcdef"
iv = b"fedcba0987654321"
aes = AES.new(key, AES.MODE_CBC, iv)
# c = aes.encrypt(m)
# print(binascii.b2a_hex(c))

c = "49a98685a527bdfa4077c400963a4e3c9effb4148566f10bce9e07ccbb731896"
tmp = int(c[9 * 2:10 * 2]) ^ ord('0') ^ ord('1')
fake_cipher = c[:9 * 2] + str(tmp) + c[10 * 2:]
d = aes.decrypt(bytes.fromhex(fake_cipher))
print(d)

# b'\xf0\xe6(r\xf6i\xb0\x9aC\x98\x9d\xba\xb0\x01\xd6#=1;admin=1;uid=1'

可见admin已经成功更改为1，但前序明文无意义了。

例题

Jarvis OJ的一题xbitf。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Unbuffered(object):
   def __init__(self, stream):
       self.stream = stream
   def write(self, data):
       self.stream.write(data)
       self.stream.flush()
   def __getattr__(self, attr):
       return getattr(self.stream, attr)
import sys
sys.stdout = Unbuffered(sys.stdout)
#import signal
#signal.alarm(600)

import random
import time
flag=open("./flag","r").read()

from Crypto.Cipher import AES
import os

def aes_cbc(key,iv,m):
    handler=AES.new(key,AES.MODE_CBC,iv)
    return handler.encrypt(m).encode("hex")
def aes_cbc_dec(key,iv,c):
    handler=AES.new(key,AES.MODE_CBC,iv)
    return handler.decrypt(c.decode("hex"))

key=os.urandom(16)
iv=os.urandom(16)
session=os.urandom(8)
token="session="+session.encode("hex")+";admin=0"
checksum=aes_cbc(key,iv,token)
print token+";checksum="+checksum
for i in range(10):
    token_rcv=raw_input("token:")
    if token_rcv.split("admin=")[1][0]=='1' and token_rcv.split("session=")[1][0:16].decode("hex")==session:
        c_rcv=token_rcv.split("checksum=")[1].strip()
        m_rcv=aes_cbc_dec(key,iv,c_rcv)
        print m_rcv
        if m_rcv.split("admin=")[1][0]=='1':
            print flag

# session=762fda4eacfb8321;admin=0;checksum=
# 77df89f8da92cbde1baa5d34a9e9e791c763cf14ef63dc3c32ce1e757603de30

那么依题意。

1
2
3
4
5
6
7
token = "session=762fda4eacfb8321;admin=0;checksum=77df89f8da92cbde1baa5d34a9e9e791c763cf14ef63dc3c32ce1e757603de30"

cipher = token.split("checksum=")[1].strip().decode('hex')
fake_cipher = (cipher[:15] + chr(ord(cipher[15]) ^ 0 ^ 1) + cipher[16:])
print "session=762fda4eacfb8321;admin=1;checksum=" + fake_cipher.encode('hex')

# session=762fda4eacfb8321;admin=1;checksum=77df89f8da92cbde1baa5d34a9e9e790c763cf14ef63dc3c32ce1e757603de30

就好了。

1
2
3
4
session=762fda4eacfb8321;admin=0;checksum=77df89f8da92cbde1baa5d34a9e9e791c763cf14ef63dc3c32ce1e757603de30
token:session=762fda4eacfb8321;admin=1;checksum=77df89f8da92cbde1baa5d34a9e9e790c763cf14ef63dc3c32ce1e757603de30
�l!_��zv�%��acfb8321;admin=1
flag{xman_bit_flip_112233}

CBC选择密文攻击

攻击目的是恢复出偏移量IV，当输入密文可控且有解密后明文返回时可解。

明文每次加密前都会和IV异或，IV每次会更新为上一组的密文。

则满足上述条件时，使得cipher[0]==cipher[1]，IV可解，公式如下。

1
2
3
4
5
6
∵
Decrypt(Cipher[0]) ^ IV = Plain[0]
Decrypt(Cipher[1]) ^ Cipher[0] = Plain[1]
Cipher[0] == Cipher[1]
∴
IV = Plain[0] ^ Plain[1] ^ Cipher[0]
例题

Jarvis OJ的一题xcc。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Unbuffered(object):
    def __init__(self, stream):
        self.stream = stream

    def write(self, data):
        self.stream.write(data)
        self.stream.flush()

    def __getattr__(self, attr):
        return getattr(self.stream, attr)


import sys

sys.stdout = Unbuffered(sys.stdout)

flag = open("./flag", "r").read()

from Crypto.Cipher import AES
import os


def aes_cbc(key, iv, m):
    handler = AES.new(key, AES.MODE_CBC, iv)
    return handler.encrypt(m).encode("hex")


def aes_cbc_dec(key, iv, c):
    handler = AES.new(key, AES.MODE_CBC, iv)
    return handler.decrypt(c.decode("hex"))


key = os.urandom(16)
iv = flag

for i in range(10):
    c = raw_input("c:")
    print aes_cbc_dec(key, iv, c).encode("hex")

此时，输入密文可控，且有解密后的明文返回。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from zio import *

def cbc_chosen_cipher_recover_iv(cc,mm):
    assert cc[0:16]==cc[16:32]
    def _xorstr(a, b):
        s = ""
        for i in range(16):
            s += chr(ord(a[i]) ^ ord(b[i]))
        return s
    p0=mm[0:16]
    p1=mm[16:32]
    return _xorstr(_xorstr(p0, p1), cc[0:16])

target=("47.97.215.88",10001)
io=zio(target)
io.read_until("c:")
io.writeline(("1"*32).encode("hex"))
mm=io.readline().strip().decode("hex")
iv=cbc_chosen_cipher_recover_iv("1"*32,mm)
print iv
io.interact()

Padding Oracle Attack

满足的攻击条件：

  • 加密时采用了PKCS5的填充【填充的数值是填充的字符个数。
  • 攻击者可以和服务器进行交互，可以提交密文，服务器会以某种返回信息告知客户端的Padding是否正常。

可在不清楚Key和IV的时候解密任意密文。

例如对Cipher[1]解密，Plain[1] = Decrypt(Cipher[1]) ^ Cipher[0]。

Cipher[1]前拼接一个伪造的Cipher[0]，用于当做Cipher[1]的初始向量，发送Cipher解密。

爆破Cipher[1]解密后Plain[0]的最后一位流程如下：

构造Cipher[0]最后一位为X ^ 1，发送并观察Padding的结果是否正确，错误返回1。

Feistel 密码结构

Feistel密码结构是用于分组密码中的一种对称结构。

一组明文分成二组，L和R。

L使用K[i]作为秘钥经过F()加密，再和R异或后作为下一轮的R，R不变作为下一轮的L。

每一轮都是可推理的，且每个的内容均为L ^ R ^ K。

L R
R RLK1
RLK1 LK1K2
LK1K2 RK2K3
RK2K3 RLK1K3K4
RLK1K3K4 LK1K2K4K5
LK1K2K4K5 RK2K3K5K6
RK2K3K5K6 RLK1K3K4K6K7
R^KY LRKX

如果F()函数是线性的，即可进行已知明文攻击。

只要知道一组明密文对，就可以解密所有密文。

例题

Jarvis OJ的一题xfz。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
import os
def xor(a,b):
    assert len(a)==len(b)
    c=""
    for i in range(len(a)):
        c+=chr(ord(a[i])^ord(b[i]))
    return c
def round(M,K):
    L=M[0:27]
    R=M[27:54]
    new_l=R
    new_r=xor(xor(R,L),K)
    return new_l+new_r
def fez(m,K):
    for i in K:
        m=round(m,i)
    return m

K=[]
for i in range(7):
    K.append(os.urandom(27))
m=open("flag","rb").read()
assert len(m)<54
m+=os.urandom(54-len(m))

test=os.urandom(54)
print test.encode("hex")
print fez(test,K).encode("hex")
print fez(m,K).encode("hex")

print xor(test[:27],m[:27]).encode("hex")

# 5ca045c3402219b13eee964e650fefb438d6bcaf1081cf86b50ebcade518e4c5c4b5c8567492405e26f1bcd47015ba86947600f4fb3a
# e8cb1fadcb6c4be6fe4a9a67e1507833c0db402e6b1eb91d3377f16fd805f15b1116443bb359245fab6251db8dc382edef95a89b3207
# 7c586f783cc0cd40de53759c7ac1d22d719a654f16ff96b76afa8fc187518097f9ec2051214cced65046900d2c6c7adfbe45e21dd8a1

根据如上加密过程，推得公式如下。

1
2
3
4
5
6
7
test_K[:27] = test[-27:] ^ K2 ^ K3 ^ K5 ^ K6
m_K[:27] = m[-27:] ^ K2 ^ K3 ^ K5 ^ K6
m[-27:] = test[-27:] ^ test_k[:27] ^ m_K[:27]

test_K[-27:] = test[:27] ^ test[-27:] ^ K1 ^ K3 ^ K4 ^ K6 ^ K7
m_K[-27:] = m[:27] ^ m[-27:] ^ K1 ^ K3 ^ K4  ^ K6 ^ K7
m[:27] = test_K[-27:] ^ test[:27] ^ test[-27:] ^ m_K[-27:] ^ m[-27:]

根据公式写出脚本。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
test = "d8dc053d372d0690194553d7ffbed36750703f417bcb989f98b181a07203ec4807e239df7f4dd9f983cc8d5081b8f7673e7b9ea32b51".decode("hex")
test_K = "f55847d90055888b420b5e3921f3697a63fe88e6c6541a8e53e58cd89e1702c45498b45b57516feb01925de8fa9e359ce226ed1aa5be".decode("hex")
m_K = "6c5c2c047a3a59dceb196ebad9dd9e98055e3f0325f0891e783010ff2a1885f2702a009f655e649bf4d7b3811c20a75bbc1d84c3a8c7".decode("hex")


def xor(a, b):
    assert len(a) == len(b)
    c = ""
    for i in range(len(a)):
        c += chr(ord(a[i]) ^ ord(b[i]))
    return c


m_back = xor(xor(test_K[:27], m_K[:27]), test[-27:])

m_front = xor(xor(xor(test_K[-27:], test[:27]), xor(test[-27:], m_K[-27:])), m_back)

print m_front + m_back
# flag{festel_weak_666_10fjid9vh12h3nvm}Z�;o6!������

更多高级的攻击方式

  • 差分攻击
  • 积分攻击
  • MITM
  • 代数攻击

Refer

加密技术01-对称加密-DES原理

DES算法原理及实现

数据加密算法--详解DES加密算法原理与实现