破译美国国安局加密推特

5月5日，美国国安局负责招聘的Twitter帐户发表了一条内容看似错乱无章的推特^[1]：

tpfccdlfdtte pcaccplircdt dklpcfrp?qeiq lhpqlipqeodf gpwafopwprti izxndkiqpkii krirrifcapnc dxkdciqcafmd vkfpcadf. #MissionMonday #NSA #news

该推特很快就被破解了：

Want to know what it takes to work at NSA? Check back each Monday in May as we explore careers essential to protecting our nation.

这条密文使用的是简单的置换加密方式，简单地说，就是把26个字母相互映射，产生常人所不能理解的密文。例如，密文中的T对应原文中的W，P对应A，F对应N，C对应T，则上述密文的前4个字母TPFC解密为Want。置换加密是古典密码中的一种，但由于英文字母具有特定的频率分布，这些密码都有一个致命弱点：不能对抗词频统计。

使用python编程对big.txt^[2]进行英文字母的频率统计，如下所示：

import matplotlib.pyplot as plt

import numpy as np

from collections import Counter

import re

# 统计总英文字母数

#TotalChar = [x for x in open(r"D:\Eric5\big.txt", "r").read().lower() if 97<=ord(x)<=122]

TotalChar = list(''.join(re.findall('[a-z]+', open(r"D:\Eric5\big.txt", "r").read().lower()))) #速度比上者快

TotalNum = len(TotalChar)

# 统计不同英文字母的重复次数

CountChar = Counter(TotalChar)

mylist = CountChar.items()

mylist_sortedbyletter = sorted(mylist, key=lambda e:e[0])

label1 = []

for (letter, freq) in mylist_sortedbyletter:

label1.append(letter)

mylist_sortedbyfrequency = sorted(mylist, key=lambda e:e[1], reverse=True)

label2 = []

for (letter, freq) in mylist_sortedbyfrequency:

label2.append(letter)

fig = plt.figure()

fig.suptitle('Letter Frequencies', fontsize=14)

ax1 = fig.add_subplot(211)

ax1.set_xticks(np.arange(len(mylist_sortedbyletter))+0.5);

ax1.set_xticklabels(label1)

ax1.set_xlabel('Letter')

ax1.set_ylabel('Frequency')

for i in range(len(mylist_sortedbyletter)):

ax1.bar(i, mylist_sortedbyletter[i][1]/TotalNum, width=1, color='0.7', edgecolor='0.9');

ax2 = fig.add_subplot(212)

ax2.set_xticks(np.arange(len(mylist_sortedbyletter))+0.5);

ax2.set_xticklabels(label2)

ax2.set_xlabel('Letter')

ax2.set_ylabel('Frequency')

for k in range(len(mylist_sortedbyfrequency)):

ax2.bar(k, mylist_sortedbyfrequency[k][1]/TotalNum, width=1, color='0.7', edgecolor='0.9');

plt.show()

letter_frequency
从上图可以看到，字母e的出现频率最高，大概在12%~13%之间，而字母z的出现频率最低，不足1%。因此，为了破解使用简单置换加密方法进行加密的密文，首先对密文中的字母频率进行统计，并与上述字母分布规律进行对比，密文中出现最多的字母很可能对应于e、t或者a，而密文中没出现或者出现极少的字母很可能对应于x、j、q或者z。

一种在线的解密方法和解密置换密码python程序在[3]中提及。

参考：
[1] http://goo.gl/hZJkfu
[2] http://norvig.com/spell-correct.html
[3] http://goo.gl/HTXeP4

破译美国国安局加密推特

Speak Your Mind Cancel reply