-
-
[旧帖]
[翻译]两个世纪破解总统密码
0.00雪花
-
发表于:
2009-7-17 07:26
3036
-
[旧帖] [翻译]两个世纪破解总统密码
0.00雪花
原文:http://online.wsj.com/article/SB124648494429082661.html
目的:翻译这篇文章的目的是进行科普,提高大家的兴趣。
200多年来,深埋在托马斯.杰斐逊(美国第三任总统)的信件和文件中,有一封神秘的用密码写的信件,直到现在也没有被人解开。
这个密码信件是由记者罗伯特帕.特森于1801年12月发给总统的。罗伯特.帕特森是美国宾夕法尼亚大学数学教授也是总统杰斐逊的朋友。总统杰弗逊和帕特森先生都在美国哲学学会任职。美国哲学学会是由一群热衷于研究自然科学和人文科学的人组成的。成员们喜好研究密码并定期交换有关密码研究的信息。
帕特森发的这封密码信是要向总统同时也是独立宣言主要作者的杰斐逊总统展示一个被他认为是一个近乎完美的密码。在这封信中,帕特森先生提到“秘密写作艺术”或称之为用密码书写已经吸引了政府人士和哲学家们多年的注意。同时帕特森先生指出大多数密码“远远没有达到完美的境界”。
帕特森先生认为,一个完美的密码应该有四个特性:应该适用于所有的自然语言,应该利于简单的学习和记忆;应该可以很容易地将信息加密和解密;而且最重要的是“绝对不能被所有不掌握密匙或机密的人破解。“
帕特森先生在信中用他的加密算法加密了一条信息并声称就算”利用全人类的智慧”也非常难解开他的密码。
没有任何历史证据表明,杰斐逊总统或其他任何人解开了帕特森的密码。但是杰弗逊总统确实认为帕特森密码非常神奇,并且他建议美国国务院使用这个密码算法,并把这个密码交给了当时美国驻驻法国的大使罗伯特.利文斯顿。
200年后,这个密码落到了劳伦.斯米斯兰手中。劳伦.斯米斯兰是一个拥有博士学位的36岁的数学家,专门研究数学和工程领域的密码学以及密码破译。他现在在位于普林斯顿的通信研究中心工作。该中心是美国国防分析研究院的一个分支机构。
几年前,斯米斯兰博士的一个在普林斯顿大学工作的邻居告诉了他有关帕特森先生的神秘密码。斯米斯兰博士非常好奇,就决定招来看看。 “像这样的一个密码问题可以让我晚上睡不着觉”他说。2007年,斯米斯兰博士解开了帕特森先生的神秘密码并且在最新的《美国科学家》杂志上发表了一篇论文阐述了解码方法。并且他还在他的母校的《哈佛杂志》上发表了一篇简介。
在帕特森先生的信中,他清楚地说明了他的密码算法不是简单的字符替代算法。字符替代算法就是把一个字母用另一个字母代替。替代算法的问题是可以用频率分析或计算特定字符出现的次数进行破解,例如字母“e”是最常见英文字母,因此,如果密文足够长的话,出现次数最多的基本上肯定是字母“e”的替代。
由于频率分析在19世纪已经众所周知,密码专家们因此转向了其他的方法。其中一个被称为nomenclator:数字目录,就是每个数字代表一个单词,音节,词组或字母。杰弗逊先生在信件中还表明,他用了几本书作为nomenclator数字目录。问题是根据帕特森先生的标准,这种nomenclator是太难记忆。
杰弗逊甚至提到他的天才代码是按他家乡佛教尼亚州蒙蒂塞洛称之为轮转编码器的模式设计的。轮转编码器设备是由筒形部件,刻在铁主轴上的螺纹,以及边缘刻有随机字母的轮子组成。使用者只需要简单地旋转轮子就可以加密和解密单词。
但是,帕特森先生还巧妙地隐藏了一些技巧。他的正文是先垂直再从左至右书写的,而且没有使用任何大写字母或空格。因此生成的文字形成一个40行,每行大约60个字母的网格。
然后,帕特森先生将这个网格分解成最多九行的几个区段,并给每一行进行从1到9的编号。下一步,帕特森先生再按编号重新排序以形成一个新的网格,再将新的网格重新分块并将各块中的每行进行编号后再按一定规律重新排序。 每一个区段是按同样的规则重新排序的。
在解释完这些后,帕特森先生在他的信中接着写到:“我认为想解开我密码的可能性是微乎其微的”。
这种加密方法的密钥是一系列两位数的数对。每个数的第一位数表示区段内的行数,而第二位数表示在每行的开头增加的字母的个数。举例来说,如果密钥是58,71,33,那这意味着帕特森先生将网格中第三行移到了区段的第一行并增加了8个随机字母,然后将网格的第7行移到了区段的
第二行,并增加了一个字母,然后将网格的第三行移到了区段的第三行,并增加了三个随机字母。帕特森先生估计要解密他的密码需要计算“超过9x10的15次方”组合。
毫无疑问,斯米斯兰博士决定解开这个密码。斯米斯兰博士从分析概率有向图以及字母对入手。某些字母对,如“dx”在英语不存在,而有些字母在几乎每一封英文信中都是伴随某些特定字母出现的,如“U”总是在“Q”后出现。
为了理解信件写作年代的语言模式,斯米斯兰博士研究了杰弗逊总统的80,000字国情咨文演讲,计算了字母对从“aa”,“ab”,“ac”,到“zz”的出现频率。
斯米斯兰博士然后提出了一系列的有根据的猜测,比如每个区段的行数,网格中的哪两行是相邻的,以及每行随机增加的字母的个数。
为了检测他的猜测,斯米斯兰博士利用了一种19世纪不具备的工具:计算机算法。他采用了称为“动态规划”的算法。这种算法的原理在于将一个大问题分解成小问题,并将各个小问题的答案最终联系在一起形成最终的结果。
最终,总的计算量少于10的5次方。斯米斯兰博士认为“就算在19世纪也是可行的,虽然十分繁琐”。
经过约一个星期的工作,斯米斯兰博士找到了帕特森先生的密匙-13,34,57,65,22,78,49。用这个密钥解密后的文字是:
“1776年7月4日在美国国会,美利坚合众国参议院的代表们发表声明,在人类的活动中...”
这正是由杰弗逊总统本人参与起草的独立宣言的开始部分,“帕特森给杰弗逊总统开了一个小小的玩笑,”,斯米斯兰博士说,“而直到现在才有人了解这个玩笑”。
[培训]内核驱动高级班,冲击BAT一流互联网大厂工作,每周日13:00-18:00直播授课