密文破译

来自计算思维百科
跳转至: 导航搜索

密文破译1.jpg

在以前,人们不想自己发送的信息被发现,会把原文(即明文)中的字母按照某种配对关系替换成其他字母,从而得到一段别人看不到的密文。比方说我们现在要对下面这段明文进行加密:

When you are old and grey and full of sleep

按照上面的替换规则(如图所示)加密后,我们将得到一段密文:

KRUZ NAI CFU AXP CZP EFUN CZP TIXX AT GXUUB

那么我有什么办法复原成明文吗?

解决方案

方案1---穷举法

解决方法:穷举法理论上可以解决这个问题,但是我们可以算一下:26个字母可能的排列顺序是4.03*10^26种之多,这意味着如果世界上60亿人每人每秒可以测试一种可能的密码表,也需要21亿年才能试完所有的排列组合。事实上,在很长的一段时间里,这种简单的替换密码被认为是无法被破解的。

方案2—基于概率论的排除法

解决方法:在使用字母文字的语言中,每一个字母在普通的文本中出现的概率事实上是不同的。以英语为例,在一片普通的文章中,字母e,a,t出现的概率远远大于j,x,z出现的概率。如果对足够多的文本进行分析,我们可以就可以统计出的每一个字母在英语文本出现的平均概率。下面一张图来自维基百科,显示26个字母在普通英文文本中出现的概率:

密文破译2.png

虽然每一个字母都被替换成其他的字母,但这并不能改变它在一段文本中出现的概率;如果我们截获的密文足够长,我们可以统计它各个单词出现的概率,然后跟上面这张图匹配一下,就可以对密文进行破解了。比如说我们发现密文中c出现的概率远远低于其他字母,把密文中的c依次替换成j,q,x,以同样的道理,对上述的替换密码亦即密钥进行猜测,从而快速地破解密文。这样,这种单字母替换密码就被无情地破解了。

以上内容节选自知乎的一个回答:https://www.zhihu.com/question/28397034

涉及的计算思维

信息安全是个永远都不会过时的领域,特别是军队,做到秘密不被泄露就是胜利的关键。下面将简单讲一下以前密码学里面的一些基础内容。密文的破译体现了规律发现的计算思维。