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
|
import gmpy2 as gm
c =
best_index_of_Coincidence = 0.065
best_freq = {}
best_freq['a'] = 0.08167
best_freq['b'] = 0.01492
best_freq['c'] = 0.02782
best_freq['d'] = 0.04253
best_freq['e'] = 0.12702
best_freq['f'] = 0.02228
best_freq['g'] = 0.02015
best_freq['h'] = 0.06094
best_freq['i'] = 0.06966
best_freq['j'] = 0.00153
best_freq['k'] = 0.00772
best_freq['l'] = 0.04025
best_freq['m'] = 0.02406
best_freq['n'] = 0.06749
best_freq['o'] = 0.07507
best_freq['p'] = 0.01929
best_freq['q'] = 0.00095
best_freq['r'] = 0.05987
best_freq['s'] = 0.06327
best_freq['t'] = 0.09056
best_freq['u'] = 0.02758
best_freq['v'] = 0.00978
best_freq['w'] = 0.02360
best_freq['x'] = 0.00150
best_freq['y'] = 0.01974
best_freq['z'] = 0.00074
print best_freq
def index_of_coincidence(s):
'''
计算字符串s的重合指数，即所有字符出现概率的平方和
:param s:密文字符串
:return:s的重合指数
'''
zimubiao = 'abcdefghijklmnopqrstuvwxyz'
freq = {}
for x in zimubiao:
freq[x] = 0
for x in s:
freq[x] = freq[x] + 1
index = 0
for x in zimubiao:
index = index + float(freq[x] * (freq[x] - 1)) / (len(s) * (len(s) - 1))
return index
def index_of_coincidence_2(s):
'''
计算明文s的拟重合指数，即s中字母的频率与英文字母的统计规律吻合程度
:param s:解出的明文
:return:s的拟重合指数
'''
zimubiao = 'abcdefghijklmnopqrstuvwxyz'
freq = {}
for x in zimubiao:
freq[x] = 0
for x in s:
freq[x] = freq[x] + 1
index = 0
for x in zimubiao:
index = index + float(freq[x]) / len(s) * best_freq[x]
return index
def guessMN():
'''
根据题意，该加密应当会周期使用密钥，该周期是key_a长度和key_k长度的最小公倍数。
遍历周期1到100，分别测试不同周期下各个子密文段的重合指数，然后求平均
:return:无返回值，打印出所有与最佳重合指数相差小于0.01的周期
'''
for l in range(1, 100):
avergage_index = 0
for i in range(l):
s = ''.join([c[j * l + i] for j in range(0, len(c) / l)])
index = index_of_coincidence(s)
avergage_index += index
avergage_index = avergage_index / l - best_index_of_Coincidence
if abs(avergage_index) < 0.01:
print 'l=', l
print avergage_index
print '开始猜测周期'
l=55
def decryptChar(c, i, j):
'''
对单个密文字符解密。
:param c: 单个密文字符
:param i: 与字符c相乘的那个密钥
:param j: 用于位移的密钥
:return: 明文字符
'''
i_inv = gm.invert(i, 26)
p = chr((ord(c) - ord('a') - j) * i_inv % 26 + ord('a'))
return p
def decrypt(s, i, j):
'''
用固定的i和j，解密子密文段
:param s: 使用相同i和j加密的子密文段
:param i: 与字符c相乘的那个密钥
:param j: 用于位移的密钥
:return: 明文字符串
'''
p = ''
for c in s:
p += decryptChar(c, i, j)
return p
def guessKey(c):
'''
对子密文段爆破它所使用的i和j
:param c: 子密文段
:return: 无返回值，但是打印拟重合指数最佳的i和j，即解出的明文统计规律与英文字符统计规律最吻合的i和j
'''
for i in range(26):
if i % 2 == 0 or i == 13:
continue
for j in range(26):
s = decrypt(c, i, j)
index = index_of_coincidence_2(s)
index = abs(index - 0.065)
if index < 0.01:
print i, j, index
def guessAllKeys():
'''
以l为周期，将完整密文c切分成l个子密文段，对这l个子密文段分别爆破其所使用密钥i和j
:return: 无返回值，但打印出最佳的密钥组合
'''
for i in range(l):
s = ''.join([c[j * l + i] for j in range(0, len(c) / l)])
print i
guessKey(s)
print '开始猜测密钥组合'
key_a = [23, 25, 21,3,19]
key_k = [9, 21, 9, 10, 16,3, 22,13,14,21,15]
p = ''
for i in range(len(c)):
p += decryptChar(c[i], key_a[i % 5], key_k[i % 11])
print p
|
