分组密码之DES

发表于 | 分类于
| 字数统计: 2.7k
一个人炫耀什么，说明内心缺少什么

算法分析

  1. DES是一个对称密码体制，加密解密使用同一秘钥，有效密钥长度为56比特。
  2. DES是一个分组密码算法，明文分组和密文分组长度均为64比特。
  3. DES使用Feistel结果，具有加密相似特性，加解密算法相同，只是解密子密钥与加密子密钥的使用顺序相反。
  4. DES由初始置换，16轮迭代，逆初始置换组成。
  5. 具体过程如下：
  • 64位明文经过初始置换（IP）而重新排列，并将其分为左右两个分组L0和R0，各为32位。
  • 在秘钥的参与下，对左右两个分组进行16轮相同轮函数的迭代。最后一轮输出为64位，且其左半部分和右半部分不进行交换。
  • 最后的与输出再通过初始逆置换产生64位密文。

算法实现

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
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
import re

# Permutation and translation tables for DES
# 压缩置换矩阵  从64位里选56位
pc1 = [56, 48, 40, 32, 24, 16,  8,
      0, 57, 49, 41, 33, 25, 17,
      9,  1, 58, 50, 42, 34, 26,
     18, 10,  2, 59, 51, 43, 35,
     62, 54, 46, 38, 30, 22, 14,
      6, 61, 53, 45, 37, 29, 21,
     13,  5, 60, 52, 44, 36, 28,
     20, 12,  4, 27, 19, 11,  3
]

# number left rotations of pc1
shifttimes = [
    1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1
]

# permuted choice key (table 2)
# 压缩置换矩阵  从56位里选48位
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]


# The (in)famous S-boxes
# S盒 的置换矩阵
sbox = [
    # 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],
]

# 32-bit permutation function P used on the output of the S-boxes
# 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]

# initial permutation IP
# IP置换的 置换矩阵
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]

# Expansion table for turning 32 bit blocks into 48 bits
# E扩展置换矩阵
e_expansion = [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]

# final permutation IP^-1
# IP逆置换矩阵
ipreverse = [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]

# IP置换
def IP(text):
    #如果长度不是64位 就退出
    assert len(text) == 64
    t = ""
    #通过循环 进行IP置换
    for i in ip :
        t += text[i - 1]
    return t

# 秘钥移位
def shift(s, times):
    s = s[times:] + s[0:times]
    return s

# 生成子秘钥
def createSubkey(key):
    # 如果key长度不是64 就退出
    assert len(key) == 64
    # DES的密钥由64位减至56位，每个字节的第8位作为奇偶校验位
    # 把56位 变成 2个28位
    Llist = pc1[0:28]
    Rlist = pc1[28:56]
    # 初始生成 左右两组28位密钥
    L0 = ""
    R0 = ""
    for i in Llist:
        L0 += key[i - 1]
    for i in Rlist:
        R0 += key[i - 1]
    assert len(L0) == 28
    assert len(R0) == 28
    # 定义返回的subkey
    subkey = []
    # 轮函数生成 48位密钥开始轮置换
    for i in range(0, 16):
        # 获取左半边 和 右半边  shift函数用来左移生成轮数
        L0 = shift(L0, shifttimes[i])
        R0 = shift(R0, shifttimes[i])
        #合并左右部分
        merge = L0 + R0
        tempkey = ""
        # 压缩置换矩阵  从56位里选48位
        # 选出48位子密钥
        for i in pc2:
            tempkey += merge[i - 1]
        assert len(tempkey) == 48
        # 加入生成子密钥
        subkey.append(tempkey)
    return subkey

# E扩展
def E_expand(Ri):
    expand = ""
    for i in e_expansion:
        expand += Ri[i - 1]
    assert len(expand) == 48
    return expand

# S盒代换
def S_replace(s):
    # 从第二位开始的子串,去掉0X
    s = bin(s)[2:]
    while len(s) < 48:
        s = "0" + s
    index = 0
    replace = ""
    for S in sbox:
        # 输入的高低两位做为行数row
        row = int(s[index] + s[index + 5], base=2)
        # 中间四位做为列数L
        col = int(s[index + 1:index + 5], base=2)
        # 得到result的单个四位输出
        out = bin(S[row * 16 + col])[2:]
        # 尾数为0，要把0补全
        while len(out) < 4:
            out = "0" + out
        # 合并单个输出
        replace += out
        # index + 6 进入下一个六位输入
        index += 6
    assert len(replace) == 32
    return replace

# P 盒置换
def P(Ri):
    t = ""
    for i in p:
        t += Ri[i - 1]
    return t

# Ri_P(P置换后的输出)和Li（上一轮次的L）异或
def requirexor(Ri_P , Li, Ri): # Ri上一轮次的R
    # P盒置换的结果与最初的64位分组左半部分L0异或
    RI = int(Ri_P, base=2) ^ int(Li, base=2)
    RI = bin(RI)[2:] # RI这一轮次的R
    while len(RI) < 32:
        RI = "0" + RI
    assert len(RI) == 32
    # 这一轮次的L即为上一轮次的R，即LI=Ri
    LI = Ri
    return (LI, RI)

# IP逆置换
def IP_reverse(L16, R16):
    t = L16 + R16
    res = ""
    for i in ipreverse:
        res += t[i - 1]
    assert len(res) == 64
    return res

# DES 算法实现 flag是标志位 当为-1时， 是DES解密， flag默认为0
def DES(text, key, flag = "0"):
    InitKeyCode = IP(text)
    # 产生子密钥 集合
    subkeylist = createSubkey(key)
    # 获得Ln 和 Rn
    Ln = InitKeyCode[0:32]
    Rn = InitKeyCode[32:]
    # 如果是解密的过程 把子密钥次序反过来 就变成解密过程了
    if (flag == "-1") :
        subkeylist = subkeylist[::-1]
    for subkey in subkeylist:
        while len(Rn) < 32:
            Rn = "0" + Rn
        while len(Ln) < 32:
            Ln = "0" + Ln
        # 对右边进行E-扩展
        Rn_expand = E_expand(Rn)
        # 压缩后的密钥与扩展分组异或以后得到48位的数据，将这个数据送入S盒
        S_Input = int(Rn_expand, base=2) ^ int(subkey, base=2)
        # 进行S盒替代
        S_sub = S_replace(S_Input)
        # P盒置换
        tem = P(S_sub)
        #  获得下一轮的Ln和Rn
        (Ln, Rn) = requirexor(tem, Ln, Rn)
        #进行下一轮轮置换
    # 最后一轮之后  左、右两半部分并未进行交换
    # 而是两部分合并形成一个分组做为末置换的输入
    # 所以要置换 一次
    (Ln, Rn) = (Rn, Ln)
    # IP逆置换得到密文
    re_text = IP_reverse(Ln, Rn)
    return re_text

# 字符串转换为二进制字符串
def strtobin(s):
    res = []
    for c in s:
        tem = bin(ord(c)).replace('b', '')
        # 转为字符串时，后7位中，如果存在前面为0，会自动去掉，需要加回来，使之满足8位
        if len(tem) < 8:
            tem = "0" + tem
        res.append(tem)
    return ''.join(res)

# 二进制转字符串
def bintostr(s):
    tem = ""
    for i in s:
        tem += str(chr(int(i, base=2)))
    return tem

# 将明文字符串分割为指定长度字符串并存于列表中
def cut_text(text, lenth):
    tem = re.findall('.{' + str(lenth) + '}', text)
    tem.append(text[(len(tem) * lenth):])
    # 由于分割后，末尾出现一个空字符，故去掉
    result = [i for i in tem if i != '']
    return result

if __name__ == "__main__":
    # 秘钥，长度必须为64位
    key = "asdfghjk"
    #明文
    plaintext = "ifnottothesunforsmilingwarmisstillinthesuntherebutwewilllaughmoreconfidentcalmifturnedtofoundhisownshadowappropriateescapethesunwillbethroughtheheartwarmeachplacebehindthecornerifanoutstretchedpalmcannotfallbutterflythenclenchedwavingarmsgivenpowerificanthavebrightsmileitwillfacetothesunshineandsunshinesmiletogetherinfullbloom"
    print("明文为： \n" + plaintext)

    # 加密
    key = strtobin(key)
    # 当明文长度不为64位的倍数时，填充空格满足条件
    while len(plaintext) % 8 != 0:
        plaintext += " "
    # 将明文分割成每组8字节，即64位
    mlist = cut_text(plaintext, 8)
    ciphertext = ""
    for t in mlist:
        mtext = strtobin(t)
        # 对每组明文分别加密
        ciphertext += DES(mtext, key)
    # 将结果转换成16进制表示，并去掉头部0X
    print("加密后的密文为： \n" + hex(int(ciphertext, base=2))[2:].upper())

    #解密
    ctext = ""
    # 加密得到的密文为二进制，故直接分割为64位每组
    clist = cut_text(ciphertext, 64)
    for c in clist:
        ctext += DES(c, key, "-1")
    # 将二进制字符串按每字节分割
    result = cut_text(ctext, 8)
    # 转换为相应字符并合并成字符串
    ans = bintostr(result)
    print("解密后的明文为： \n" + ans.rstrip())

加密与解密

当key = “asdfghjk”，时，加密与解密如图所示：

安全性分析

如今，DES的安全性已经无法满足需求（三重DES安全性能达到要求，但存在许多缺陷）故存在许多可行攻击。

  1. 固有的安全问题：互补性和弱密钥问题。
  • 互补性： 对明文𝑚和密钥𝐾逐位取补，则加密后的密文同样为原密文的补。故互补性使得DES在选择明文攻击下所需的工作量减半。

  • 弱密钥：初始密钥会生成16个相同的子密钥，这样的弱密钥有

    1
    2
    3
    4
    0x0101010101010101
    0xFEFEFEFEFEFEFEFE
    0xE0E0E0E0F1F1F1F1
    0x1F1F1F1F0E0E0E0E

  • 半弱密钥：即用K2加密明文，可以用K1解密，这种半弱密钥有：

    1
    2
    3
    4
    5
    6
    0x011F011F010E010E:0x1F011F010E010E01
    0x01E001E001F101F1:0xE001E001F101F101
    0x01FE01FE01FE01FE:0xFE01FE01FE01FE01
    0x1FE01FE00EF10EF1:0xE01FE01FF10EF10E
    0x1FFE1FFE0EFE0EFE:0xFE1FFE1FFE0EFE0E
    0xE0FEE0FEF1FEF1FE:0xFEE0FEE0FEF1FEF1

  • 还有四分之一弱密钥，八分之一弱密钥等。这些秘钥的安全性很差，故一般生成秘钥后，都x需要进行弱密码检查。

  1. 穷举攻击：如今，穷举时间已经减少到不足24小时。
  2. 差分分析：这种方法对破译16轮的DES不能提供一种实用的方法，但对破译轮数较低的DES是很成功的。
  3. 线性分析：用这种方法破译DES比差分分析方法更有效。可用2^47个已知明文破译8－轮DES。
0%