密码学作业记录(一)

前言

最近在学习密码学,研究了一些密码学算法,特此记录一下。

古典密码

古典密码体制是基于古代落后的计算条件和落后的密码学与数学知识建立的,本部分选取了凯撒密码仿射密码

凯撒密码

凯撒密码本质上是一种置换密码,且为一对一的置换加密方式。明文中的所有字母都在字母表上向后(或向前)按照一个固定数目进行偏移后被替换成密文。例如,当偏移量是3的时候,所有的字母A将被替换成D,B变成E,以此类推。这个加密方法是以罗马共和时期恺撒的名字命名的,当年恺撒曾用此方法与其将军们进行联系。

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# 名密文输入范围是26个英文小写字母
import sys

mode = sys.argv[1]
if mode == "encrypt":
plain = raw_input("Please input plaintext: ")
key = input("Please input key: ")
cip = ""
for i in range(len(plain)):
temp = (ord(plain[i]) - ord('a') + key) % 26 + ord('a')
cip += chr(temp)
print("cipher: " + cip)

elif mode == "decrypt":
cipher = raw_input("Please input cipher: ")
key = input("Please input key: ")
pla = ""
for i in range(len(cipher)):
temp = (ord(cipher[i])-ord("a") - key) % 26 + ord('a')
pla += chr(temp)
print("plaintext: " + pla)
else:
print(sys.argv[1]," is not supported:(")

demo

安全性分析:可以看到,凯撒密码的加解密方式简单,手工即可实现,在古代落后的计算能力之下,该中算法拥有着很高的安全性,但是放在现在由于计算能力的提高,该算法表现出脆弱性,无法抵抗穷举攻击,因为对于一串明文,可能的加密组合只有26种,以现在的计算手段,对于任何攻击方式都表现出极大的脆弱性,当遭受已知明文攻击时完全没有抵抗性,故而现代密码体制中已不再采用该密码。

仿射密码

仿射密码的加密算法就是一个线性变换,及对任意的明文字符x,对应的密文字符为 y≡e(x)≡ax+b(mod 26),其中a,b均为26以内的正整数,并且要求gcd(a,26)=1,函数e(x)称为仿射加密函数,解密时用x≡d(e(x))≡a'(e(x)-b)(mod 26)来解密。

代码如下:

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
import sys
import math

def get_re(a):
for i in range(0,27):
if i*a % 26 == 1:
return i

# ex = ax+b
mode = sys.argv[1]
if mode == "e":
p = str(input("Plz input plain: "))
a = int(input("Plz input a: "))
b = int(input("Plz input b: "))
c = ""
for i in range(len(p)):
t = ((ord(p[i]) - ord('a')) * a + b) % 26 + ord('a')
c += chr(t)
print("cipher: " + c)
elif mode == "d":
# a'(e(x)-b)
c = str(input("Plz input cipher: "))
a = int(input("Plz input a: "))
b = int(input("Plz input b: "))
p = ""
_a = get_re(a)
for i in range(len(c)):
t = (ord(c[i]) - ord('a') - b)*_a % 26 + ord('a')
p += chr(t)
print("plain: " + p)
else:
print("Input Error:(")

加密时按照加密公式给出,解密时用穷举法求出a的逆元从而解密。

实例演示

demo


  可以看到,仿射加密和凯撒加密本质都是一种一对一的加密方式,这种加密方式没有将字母出现的统计规律隐藏起来,在英文中对于足够长的英文文本来说,字符的出现频率是相对固定的,还有字母的有些组合出现频率也是相对固定的,这样就可以通过统计分析法来破解上述加密方式加密出来的密文。

频率分析法破解仿射密码

1
2
假如我们已知一串密文 fmxvedkaphferbndkrxrsrefmorudsdkdvshvufedkaprkdlyevlrhhrh,
此时可以通过频率分析法尝试爆破出明文

代码如下

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
import gmpy2
import sys

dic = ['e','t','a','o','i','n','s','h','r','d','l','c','u','m','w','f','g','y','p','b','v','k','j','x','q','z']
freq = [0] * 26
cipher = input("Plz input cipher: ")

# 频率统计
for i in range(len(cipher)):
t = ord(cipher[i])-ord('a')
freq[t] += 1

def get_ab(x,y):
dic = ['e','t','a','o','i','n','s','h','r','d','l','c','u','m','w','f','g','y','p','b','v','k','j','x','q','z']
repeat = [] # 去除重复计算的项
for one in dic:
for two in dic:
o = ord(one) - ord('a')
t = ord(two) - ord('a')
oo = ord(x) - ord('a')
tt = ord(y) - ord('a')
# oo = a*o+b
# tt = a*t+b
if o - t == 0:
continue
a = ((oo-tt)//(o-t)) % 26
b = (oo - a * o) % 26
test = int(gmpy2.gcd(a, 26))
if test != 1:
continue
else:
_a = gmpy2.invert(a, 26)
plain = ""
if (a,b) in repeat:
continue
for item in cipher:
ex = ord(item) - ord('a')
p = (_a * (ex - b)) % 26
plain += chr(p+ord('a'))
repeat.append((a,b))
print(plain,end="")
print("**" + str(a) + "**" + str(b))
print("共" + str(len(repeat)) + "项.")

x = chr(freq.index(max(freq)) + ord('a'))
freq[freq.index(max(freq))] = 0
y = chr(freq.index(max(freq)) + ord('a'))
get_ab(x,y)

代码思路是先统计密文的字母出现频率,由频率高低依次对应字母频次表,联立方程组,由于未知数只有a、b,所以只需要两个方程是即可解出,依次尝试不同的变换组合即可,直至得到有意义的明文,由于统计基数的原因,密文越长,则越可能早的得到有意义的密文。为了使结果显示更加有效,代码中过滤了冗余的待选明文项(即a、b相同的情况)。

demo

可以看到密文被成功破解


  从对古典密码分析中可以看到,一个密码体系要保证安全性,应该尽可能的隐藏语言特性,即密文均匀分布,且加密的可选字符区间应尽可能的大,否则无法抵抗穷举攻击。在现代密码体制中,这两点都有了比较好的保证。

分组密码

DES加密算法

DES算法为密码体制中的对称密码体制,又被称为美国数据加密标准,是1972年美国IBM公司研制的对称密码体制加密算法。 明文按64位进行分组,密钥长64位,密钥事实上是56位参与DES运算(第8、16、24、32、40、48、56、64位是校验位, 使得每个密钥都有奇数个1)分组后的明文组和56位的密钥按位替代或交换的方法形成密文组。

DES加密流程如下图

demo

解密时只需要将机密流程逆序即可。

算法大致步骤如下:

  1. 初始置换

​DES算法使用64位的密钥key将64位的明文输入块变为64位的密文输出块,并把输出块分为L0、R0两部分,每部分均为32位。初始置换规则可查表获得,这里不再赘述。初始置换是固定的、公开的函数,因此这个初始置换及逆初始置换都没有密码意义,主要目的是为了更好地将明文和密文分组。


下一步是进行轮函数(F函数)迭代,F函数具体步骤如下

  1. 扩展置换(E盒)

初始置换结束后,将得到64位序列分成两组,各32位,而E盒将数据的右32位输入扩展为48位输出,改变了位的次序,重复了某些位。

该步骤的目的是:a、产生与秘钥相同长度的数据以进行异或运算,R0是32位,子秘钥是48位,所以R0要先进行扩展置换之后与子秘钥进行异或运算;b、提供更长的结果,使得在替代运算时能够进行压缩。

  1. 秘钥加运算

该步骤非常简单,将E扩展输出的48位与48位子秘钥进行逐位异或,输出48位数据。

  1. 代换盒(S盒)

此步骤的功能是进行非线性变换,S盒是DES中唯一的非线性部分,经过S盒代换压缩之后,48位的数据重新被压缩成32位。

代换压缩由8个不同的代替盒(S盒)完成。每个S-盒有6位输入,4位输出。所以48位的输入块被分成8个6位的分组,每一个分组对应一个S-盒代替操作。经过S-盒代替,形成8个4位分组结果

S盒具有良好的非线性,输入的每一个比特与全部输入比特有关,两个输入相差1比特时,输入至少相差2比特,极大的保证了安全性。

  1. 置换运算(P盒)

置换运算(P盒)只是进行简单位置置换,而不进行扩展和压缩。

至此F函数结束


  1. 逆置换

将初始置换进行16次的迭代,即进行16层的加密变换,这个运算过程我们暂时称为F函数。得到L16和R16,将此作为输入块,进行逆置换得到最终的密文输出块。

代码如下:

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
import sys
import binascii

ip = [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, 56, 48, 40, 32, 24, 16, 8, 0, 58, 50, 42, 34, 26, 18, 10, 2, 60,
52, 44, 36, 28, 20, 12, 4, 62, 54, 46, 38, 30, 22, 14, 6]

# 逆矩阵
_ip = [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, 32, 0, 40, 8, 48, 16, 56, 24]

# 初始化c、d数组
c = [""]*17
d = [""]*17
k = [""]*17

# 左右32位数组
l = [""]*17
r = [""]*17
def generate_secretkey(key, round):
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,
4, 36, 28, 20, 12, 4, 27, 19, 11, 3]
respc1 = ""
for i in range(56):
respc1 += key[pc1[i]]
c[0] = respc1[:28]
d[0] = respc1[28:]
k[0] = c[0] + d[0]
for i in range(1,round+1):
if i in (1,2,9,16):
# 左移1位
c[i] = c[i-1][1:] + c[i-1][:1]
d[i] = d[i-1][1:] + d[i-1][:1]
else:
c[i] = c[i-1][2:] + c[i-1][:2]
d[i] = d[i-1][2:] + d[i-1][:2]
secret = c[round] + d[round]
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]
s_key = "" # 生成本轮最终秘钥
for i in range(48):
s_key += secret[pc2[i]-1]
return s_key

# 初始置换,输入为64位数据,8个ascii字符
def init_replace(data):
re = ""
for i in range(64):
re += data[ip[i]]
return re

# 扩展置换,输入为32位数据,输出为48位数据
def e_replace(data):
e_box = [31, 0, 1, 2, 3, 4, 3, 4, 5, 6, 7, 8, 7, 8, 9, 10, 11,
12, 11, 12, 13, 14, 15, 16, 15, 16, 17, 18, 19, 20, 19, 20, 21,
22, 23, 24, 23, 24, 25, 26, 27, 28, 27, 28, 29, 30, 31, 0]
re = ['a'] * 48
for i in range(48):
re[i] = data[e_box[i]]
return re

# 秘钥加处理
def secret_plus(data, key):
out = ""
for i in range(48):
out += str(int(data[i])^int(key[i]))
return out

# s盒置换,输入48位,输出32位
def s_replace(data):
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]]
re = []
for i in range(48//6):
re.append(data[6*i:6*i+6])

# 开始进行s盒置换
dic = [s1,s2,s3,s4,s5,s6,s7,s8]
retn = ""
for i in range(8):
r = int(re[i][0] + re[i][5],2)
c = int(re[i][1:5], 2)
temp = str(bin(dic[i][r][c]))[2:]
temp = "0"*(4-len(temp)) + temp
retn += temp
# print(len(retn))
return retn

# p盒置换,输入输出均为32位
def p_replace(data):
p = [15, 6, 19, 20, 28, 11, 27, 16, 0, 14, 22, 25, 4, 17, 30, 9, 1, 7,
23, 13, 31, 26, 2, 8, 18, 12, 29, 5, 21, 10, 3, 24]
re = ""
for i in range(32):
re += data[p[i]]
return re


# F函数,32位数据,子秘钥,轮数
def f_function(data, key, round):
cipher = data # 左侧32位
cipher = e_replace(cipher)
cipher = secret_plus(cipher, key)
cipher = s_replace(cipher)
cipher = p_replace(cipher)
return cipher

def convert_key_bin(key):
word = key
key = ""
for i in word:
key += f'{bin(ord(i))[2:]:0>8}'
return key

# 终极加密函数,参数为秘钥和明文(明文暂时测试为64位以内)
def des_encrypt(ptext, key):
for i in range(17):
l[i] = ""
r[i] = ""
key = convert_key_bin(key)
cipher = init_replace(ptext)
l[0] = cipher[0:32]
r[0] = cipher[32:]
# 进行16层循环
for i in range(1,16):
l[i] = r[i-1]
secret_key = generate_secretkey(key,i) # 生成子秘钥
f_result = f_function(r[i-1],secret_key,i)
for j in range(32):
r[i] += str(int(l[i-1][j])^int(f_result[j]))
secret_key = generate_secretkey(key,16)
f_result = f_function(r[15],secret_key,16)
l[16] = ""
for j in range(32):
l[16] += str(int(l[15][j])^int(f_result[j]))
r[16] = r[15]
temp = l[16] + r[16]
final_cipher = ""
for i in range(64):
final_cipher += temp[_ip[i]]
return f'{hex(int(final_cipher,2))[2:]:0>16}'

def des_decrypt(cipher,key):
for i in range(17):
l[i] = ""
r[i] = ""

# 恢复为64位密文
key = convert_key_bin(key)
temp = bin(int(cipher, 16))[2:]
cipher = "0"*(64-len(temp)) + temp
cipher = init_replace(cipher)
l[16] = cipher[:32]
r[16] = cipher[32:]
for i in range(16,1,-1):
l[i-1] = r[i]
secret_key = generate_secretkey(key,i) # 生成子秘钥
f_result = f_function(r[i],secret_key,i)
r[i-1] = ""
for j in range(32):
r[i-1] += str(int(l[i][j])^int(f_result[j]))
r[0] = r[1]
secret_key = generate_secretkey(key,1)
l[0] = ""
f_result = f_function(r[1],secret_key,1)
for j in range(32):
l[0] += str(int(l[1][j])^int(f_result[j]))
temp = l[0] + r[0]
bintext = ""
for i in range(64):
bintext += temp[_ip[i]]
plaintext = ""
for i in range(8):
plaintext += chr(int(bintext[8*i:8*i+8],2))
return plaintext

def str2bin(text):
if len(text) % 8 != 0:
text = text + " "*(8-(len(text)%8))
binplain = ""
for i in text:
binplain += '{:0>8}'.format(bin(ord(i))[2:])
return binplain


def encrypt(text, key):
longbinplain = str2bin(text)
group_plain = ""
longcipher = ""
for i in range(len(longbinplain)//64):
group_plain = ""
group_plain = longbinplain[64*i:64*i+64]
longcipher += des_encrypt(group_plain,key)
return longcipher

def decrypt(cipher,key):
plaintext = ""
for i in range(len(cipher)//16):
plaintext += des_decrypt(cipher[16*i:16*i+16], key)
return plaintext.rstrip()

if __name__ == '__main__':
mode = sys.argv[1]
while mode in ("e","d"):
data = input("Plz input data: ")
key = str(input("Plz input key: "))
if mode == "e":
ans = encrypt(data, key)
print(ans)
elif mode == "d":
ans = decrypt(data, key)
print(ans)
mode = input("quit or continue?\n")

为了增强通用性,增加代码重用性,该算法使用了包封装,从而使其能够被其它程序重用。该DES支持短信息加密,也支持长消息加密。为了使密文便于显示和存储转化为16进制显示

实例演示:

demo

安全性分析

​ DES算法具有极高的安全性,到目前为止,除了用穷举搜索法对DES算法进行攻击外,还没有发现更有效的办法。 而56位长的密钥的穷举空间为2^56,这意味着如果一台计算机的速度是每一秒钟检测一百万个密钥,则它搜索完全部密钥就需要将近2285年的时间,可见,这是难以实现的。然而,这并不等于说DES是不可破解的。而实际上,随着硬件技术和Internet的发展,其破解的可能性越来越大,而且,所需要的时间越来越少。使用经过特殊设计的硬件并行处理要几个小时。

​ 由DES算法的密钥生成步骤中我们可以看到:DES算法中只用到64位密钥中的其中56位,而第8、16、24、……64位8个位并未参与DES运算,这一点,向我们提出了一个应用上的要求,即DES的安全性是基于除了8,16,24,……64位外的其余56位的组合变化256才得以保证的。因此,在实际应用中,我们应避开使用第8,16,24,……64位作为有效数据位,而使用其它的56位作为有效数据位,才能保证DES算法安全可靠地发挥作用。如果不了解这一点,把密钥Key的8,16,24,….. .64位作为有效数据使用,将不能保证DES加密数据的安全性,对运用DES来达到保密作用的系统产生数据被破译的危险,这正是DES算法在应用上的误区,留下了被人攻击、被人破译的极大隐患。

​ 此外,由于DES算法各轮(F函数)的子密钥是通过改变初始密钥这种方式得到的,因此有些初始密钥成了弱密钥(weakkey)。初始密钥分成两部分,每部分各自独立的移动。如果每一部分的所有位都是0或1,那么算法的任意一个周期的密钥都是相同的。当密钥是全1、全0、或者一半全1、一半全0时,会发生这种情况。所以我们在选择密钥时要进行检查,以防止产生弱密钥

​ 随着密码学的发展,差分分析和线性分析的发展对分组密码的安全性构成了挑战,也推动了分组密码设计技术的发展。

​ 随着计算机计算能力的提高与密码分析技术的进步,DES的密钥长度已经被证明不能够满足当前安全性能的需求,为了克服DES密钥空间小的缺陷,人们又提出了三重DES的变形形式,即使用多个不同的DES秘钥利用DES算法对明文进行多次加密,这样可以增加密钥量。

算法实用性分析

​ DES算法拥有着良好的安全性,目前最有效的破解方法依然是穷举攻击,所以在一些安全性要求相对不高的情况下可以使用DES算法,此外,由于DES的广泛的使用量,为了充分利用有关DES的软硬件资源,可以使用DES的改进算法如三重DES算法等。

​ 由于DES算法要进行多轮迭代,所以DES的运算速度相对较慢,此外,密码生命周期也比较短。


​ 分组密码与序列密码相比,具有扩散性好,插入敏感等优点,缺点是加解密处理速度慢、存在错误传播。用途上,在对于处理数据分组的应用,比如文件传递、电子邮件,分组密码非常合适。

-------------本文结束感谢您的阅读-------------
您今天怎么辣么迷人!