#coding:utf_8
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 + pow(float(freq[x]) / len(s), 2)
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 '开始猜测周期'
guessMN()#结果显示,重合指数得分较高的都是6的整数倍,所以周期极有可能是6
l = 6
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: #若i与26不互素,则解除的明文不唯一,所以i一定不是2和13的倍数
continue
for j in range(26):
s = decrypt(c, i, j)
# print s
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 '开始猜测密钥组合'
guessAllKeys()
# 根据打印结果,发现最佳组合依次是
# 19,10
# 7,9
# 23,3
# 19,24
# 7,14
# 23,15
# 将l设置成12、18、24或更多,还是可以得到这样的组合的重复
# 现在基本可以确定密钥应该是这样的
key_a = [19, 7, 23]
key_k = [10, 9, 3, 24, 14, 15]
#利用key_a, key_k解密完整的密文,得到明文
p = ''
for i in range(len(c)):
p += decryptChar(c[i], key_a[i % 3], key_k[i % 6])
print p
# 明文.......flagishelloxnucagoodluck
# 末尾是flagishelloxnucagoodluck
# 由此可得falg:helloxnucagoodluck