现代密码教程—古典密码体制
现代密码学教程—古典密码体制
作业（尚未订正）
令仿射密码的密钥k = （9, 3），gcd（9, 26） = 1。明文hot = （7, 14, 19），求加解密过程。
加密:
（9 × 7 + 3） mod 26 = 14 （9 × 14 + 3） mod 26 = 25
（9 × 19 + 3） mod 26 = 18 密文为（14, 25, 18） = （o, z, s）
解密：
$9^{-1}=3 mod 26$
（14 - 3） × 3mod 26 = 7 （25 - 3 ） × 3mod 26 = 14
（18 - 3） × 3mod 26 = 19 明文为（7, 14, 190） = hot
用维吉尼亚密码加密明文
please keep this message in secret，其中使用的密钥为computer，试求其密文。密文为：
rzqpmxovgdfwclqvugmvybrjgqdtn用Hill密码加密明文
hill，使用的密钥是$k =
\begin{bmatrix}
1 & 2 & 3 \\
4 & 5 & 6 \\
7 & 8 & 9
\end{bmatrix}
$试设计实现仿射密码和单表代换密码：给出密钥生成（随机选择小于26的数、选择和26互素的密钥；以及生成0-25上的一个随机指挥）、加解密的伪代码。
仿射密码：
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
51import random
def gcd（a, b）:
if b == 0:
return a
else:
return gcd（b, a % b）
# 求模26下x的逆
def inv_（x）:
for inv_a in range（1, 26, 2）:
for j in range（27）:
if x * inv_a == 26 * j + 1:
return inv_a
# 仿射密码
print（'仿射密码'）
while True:
state = input（"加密/解密："）
if state == "加密":
# 字母表
alphabet = dict（）
for i in range（26）:
alphabet[chr（i + 97）] = i
# 生成密钥a和b，生成随机数后判断是否与26互素
while True:
a = random.randint（1, 25）
if gcd（a, 26） == 1:
break
b = random.randint（0, 25）
print（'key:（{},{}）'.format（a, b））
# 输入明文，产生密文
c = ''
p = input（'明文：'）.lower（）
for word in p:
num = （a * alphabet[word] + b） % 26
for key, value in alphabet.items（）:
if value == num:
c += key
print（'密文:{}'.format（c））
break
elif state == "解密":
c = input（"密文："）.lower（）
key_a, key_b = map（int, input（"密钥："）.split（））
a_ = inv_（key_a）
print（"明文：", end=''）
for word in c:
print（chr（（（（ord（word） - 97 - key_b） * a_） % 26） + 97）, end=''）
break
else:
print（"请输入：加密或解密"）单表代换：
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
26import random
alphabet = list（）
for i in range（26）:
alphabet.append（chr（i + 97））
# 打乱列表，并对应原来字母表
random.shuffle（alphabet）
key = dict（）
for i in range（26）:
key[chr（i + 97）] = alphabet[i]
print（'加密表:\n{}'.format（key））
print（'*' * 15 + '加密' + '*' * 15）
p = input（'明文：'）.lower（）
c = ''
for word in p:
c += key[word]
print（'密文：{}'.format（c））
print（'*' * 15 + '解密' + '*' * 15）
p = input（'密文：'）.lower（）
print（"明文：", end=''）
for word in p:
for k, value in key.items（）:
if value == word:
print（k, end=''）给出移位、仿射、单表代换、维吉尼亚密码、多表代换（每个密钥是一个单表代换）、置换密码穷尽搜索的复杂度（即密钥空间大小）。
- 移位：25
- 仿射: $\varphi（26）*26=312$
- 单表代换：26!
- 维吉尼亚：$26^{m}$
- 多表代换：$（26!）^{m}$ （m为密钥长度）
- 置换: m! （m为分组长度）
区分单表代换、多表代换、置换密码、希尔密码，哪个属于分组加密范畴，为什么？
多表代换，置换密码，希尔密码属于分组加密。多表代换要将明文m个分组成一段，不足m的元素填充按密钥对应不同的密码表加密。置换密码和希尔密码分组后不足m的要进行补齐，然后进行换位或与矩阵做乘法。
已知下列密文是通过维吉尼亚密码加密得来的，试求其明文。
点击查看
Per zlrracm, vxmcs r qipqlczhs. Qs fcv rihw sxx hblrxh sm nkidhvzphw. Ixxvn qsn, lysh sifecs uui jrrfyg, mk xj suvc kd ss wbrzrrz uqh jpp zyw qv ylgn osfz fin isi bpgyoj, fg dm zdqzap, cl sifecs qks cdfy iu xyxey iu tipp zcni dt. Sin lj nt rfy jszcx hi jik iyfixky iysmh hzuwwwxpk izayv; mw lv olh kfxeu nr gitrhy d afgcr qkiit vjyucsdum bdw kwv cjssiilbcwc kd wwhg e ads, ohg ewuffx fscavuy; lj nt rfy jszcx hi vemt kvy hrmxichpiei rbx giwtrh zxxlgv duqhvbzqm, wlvc ns uui xdzba ws ypms nr hf xk hijikwvf.
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
176import re
from functools import reduce
# 最大公因数
def GCD（a, b）:
if b == 0:
return a
else:
return GCD（b, a % b）
# 整理原文段，删去除字母以外的内容，都改成小写
def neat（c）:
c_new = ''
for word in c:
if （65 <= ord（word） <= 90） or （97 <= ord（word） <= 122）:
c_new += word.lower（）
return c_new
def toletter（offset）:
letter = ''
alphabet = [chr（i） for i in range（97, 123）]
for i in offset:
letter += alphabet[i]
print（"密钥：{}".format（letter））
return letter
# 26字母出现的频数字典,原文按照秘钥长度分组
def P_freq（c_new, key_len, col）:
text = list（） # 存放原文按秘钥长度分组后的内容
P_fre = list（） # 存放text中26字母的频数/秘钥长度
alphabet = [chr（i） for i in range（97, 123）] # 26字母列表
# 原文分组
for i in range（len（c_new））:
if i % key_len == col:
text.append（c_new[i]）
# 频率计算
for i in range（26）:
P_fre.append（text.count（alphabet[i]） / key_len）
return P_fre
# 计算P、Q相关卷积，最大值对应位移量
def Correlation（P, Q）:
max_cor = 0 # 记录最大的卷积
for i in range（26）:
cor = 0
for j in range（26）:
# 卷积计算
cor += P[（j + i） % 26] * Q[j]
# 找出最大的卷积，其索引为key
if cor > max_cor:
max_cor = cor
key = i
return key
# Kasiski测试：秘钥长度
def Kasiski（c_new）:
# 储存单个重复字段开始索引
indexes = list（）
# 设定重复字段长度
word_len = 3
# 记录大重复字段出现次数
count = 0
# 记录重复字段
K_word_dict = dict（）
# 用于存储多个距离差 重复字段的索引-重复字段第一次出现索引
tpl = tuple（）
# gcd的结果
gcd_result_lst = list（）
# 滑动窗口样式的遍历全文，找到全部存在的重复字段，存到字典当中，重复字段：出现次数
for i in range（len（c_new） - 2）:
K_word = ''
for j in range（0, word_len）:
K_word += c_new[i + j]
# 查询整段密文字段重复次数
count = c_new.count（K_word）
# 记录最多出现的
if count >= 2:
if K_word not in K_word_dict.keys（）:
K_word_dict[K_word] = count
# 遍历字典
for w in K_word_dict.keys（）:
# 找出一个重复字段的出现的位置
index = re.finditer（w, c_new）
for i in index:
indexes.append（i.span（）[0] + 1）
# 位置存放在indexes中，计算距离差：每个值都减去第一次出现这个字段的位置索引，并删去第一个位置。
for j in range（len（indexes））:
if j > 0:
indexes[j] -= indexes[0]
indexes.pop（0）
tpl += tuple（indexes）
indexes.clear（）
# 算出这个重复字段距离差的GCD
gcd_result_lst.append（reduce（GCD, tpl））
print（'密文中重复出现的文字段：\n{}'.format（K_word_dict））
print（'对应文字段距离差为：\n{}'.format（gcd_result_lst））
# 如果计算出为1，则猜测为列表中的非1数值
gcd_result = reduce（GCD, tuple（gcd_result_lst））
if gcd_result == 1:
print（'猜测密钥为：{}'.format（（list（set（gcd_result_lst）））））
else:
print（'猜测密钥为：{}'.format（gcd_result））
# 拟重合指数测试法
# 拟重合指数法：求偏移量
def Chi（c_new, key_len）:
result = list（） # 存放全部位移量
# 通常文本的字母概率分布Q
Q = [8.19, 1.47, 3.83, 3.91, 12.25, 2.26, 1.71, 4.57, 7.10, 0.14, 0.41, 3.77, 3.34, 7.06, 7.26, 2.89, 0.09, 6.85,
6.36, 9.41, 2.58, 1.09, 1.59, 0.21, 1.58, 0.08]
# 密文的字母概率分布P
P = list（）
for i in range（0, key_len）:
P = P_freq（c_new, key_len, i）
result.append（Correlation（P, Q））
P.clear（）
print（'偏移量分别为：{}'.format（result））
return result
# 加密
def encrypto（mingwen, key）:
miwen = [0] * （len（mingwen））
count = 0
for i in range（len（mingwen））:
if （mingwen[i].isalpha（））:
if （mingwen[i].isupper（））:
offset1 = ord（key[（i - count） % len（key）]） - ord（'a'）
miwen[i] = chr（（（ord（mingwen[i]） - ord（'A'）） + offset1） % 26 + ord（'A'））
else:
offset2 = ord（key[（i - count） % len（key）]） - ord（'a'）
miwen[i] = chr（（（ord（mingwen[i]） - ord（'a'）） + offset2） % 26 + ord（'a'））
else:
miwen[i] = mingwen[i]
count = count + 1
return miwen
# 解密
def decrypto（miwen, key）:
mingwen = [0] * （len（miwen））
count = 0
for i in range（len（miwen））:
if （miwen[i].isalpha（））:
if （miwen[i].isupper（））:
offset1 = ord（key[（i - count） % len（key）]） - ord（'a'）
mingwen[i] = chr（（（ord（miwen[i]） + ord（'A'）） - offset1） % 26 + ord（'A'））
else:
offset2 = ord（key[（i - count） % len（key）]） - ord（'a'）
mingwen[i] = chr（（（ord（miwen[i]） - ord（'a'）） - offset2） % 26 + ord（'a'））
else:
mingwen[i] = miwen[i]
count = count + 1
print（'明文：'）
print（''.join（mingwen））
if __name__ == '__main__':
c = input（'请输入密文：'）
# 密文优化：删除标点，改为小写
ciphertext = neat（c）
# 密钥长度
key_len = Kasiski（ciphertext）
while True:
# 输入密钥长度
key_len_input = int（input（'请输入想要实验的密钥长度：'））
# 拟重合指数测试法：求偏移量
offset = Chi（ciphertext, key_len_input）
# 转换成英文字母
key = toletter（offset）
# 解密
decrypto（ciphertext, key）
# 多次试验
stop = input（'是否试验其他密钥（y/n）:'）.lower（）
if stop == 'n':
break
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 LRBlog！
相关推荐
评论