主题:【原创】被征服的谜――ENIGMA的故事(一) -- 1001n
被征服的谜――ENIGMA的故事(一)
首先声明,本文不全是1001n的研究心血,特别是其中关于enigma机的主要内容来自三思科学期刊http://www.oursci.org/,原文分为四个部分,主要编译自Simon Singh的著作The Code Book。毫不客气的说,其中的内容相当精彩。为了写点前因后果,也是为了顺便塞点私货,本文在参考其它文献的基础上,对其进行了部分归纳和发挥,不当之处,还请批评指正。
再扯远一点,大家对我发的帖子的争论和支持,让我很感动,也很受教育。特别是指出我文中的处处硬伤的高手,实在让我受益匪浅。我这人有个缺点,不太喜欢回帖――因为一回就走题――习惯如此,绝没有对大家意见置之不理的意思:)以及,中医系列开了个头,后来发现高手如云,有点不敢说了,只有傻眼看着,会不会接着写,谁知道呢:)在这里多罗嗦一句,大伙说的写的,我都看见了,感谢大家!
――――――――――――――――――――――――――――――――――――――――
ENIGMA在密码学界里,绝对是划时代的丰碑。而且,还不是一座丰碑,而是两座:研究并制造ENIGMA是一座,研究并破解ENIGMA又是一座。
稍微看看ENIGMA的历史,任何人都会因其中透出的人类智慧之美而折服。如果要向这样辉煌的智慧敬献花环的话,那么主要的应该献给三个人:
首先是德国人亚瑟?谢尔比乌斯(Arthur Scherbius);
其次是波兰人马里安?雷杰夫斯基(Marian Rejewski);
第三个就是英国人阿兰?图灵(Alan Turing)。
这三个人中,
德国人发明了ENIGMA;
波兰人初步解破了简单的ENIGMA;
而英国人彻底终结了最高难的ENIGMA。
顺着时间的主轴,先从德国人亚瑟?谢尔比乌斯说起。
(一)密码的前世
一战终于结束了,时间转眼就跨入了1918年。而在这一年,密码学界的一件大事“终于”发生了:在德国人亚瑟?谢尔比乌斯天才的努力下,第一台非手工编码的密码机――ENIGMA横空出世了!
说是终于发生,也是因为确实有点奇怪。在工业革命浪潮席卷欧洲那么多年以后,天上有了飞机,地上有了坦克,海里有了潜艇,甚至连毒气都上了战场的情况下,密码学的发展竟然不可思议地始终是停滞的――千百年来人们用来加密文件的办法,竟然还是手工操作!
此外,加密的方式也受到了重大的挑战,简单的明文字母替换法已经被频率分析法毫无难度地破解了,曾经认为是完美的维吉耐尔(Vigenere)密码和它的变种也被英国人Charles Babbage破解了。顺便说一句,这个Charles Babbage可不是凡人,他设计了差分机Difference Engine和分析机Analytical Engine,而这东西就是现在计算机的先驱。而他老人家(1792-1871)可是19世纪的人!
扯远一点,先说说这个加密的方式。一般来说,把明文里的文字用其它字母替换,可以达到无法直接识别的目的。具体操作起来,当时流行的操作有这么几种:
1、每个字母都用其它固定的字母代替,比如A换成T,也就是一对一对应的单字替换法;
2、用多个字母替代一个字母,比如A换成TVW,也就是多对一的多名码替换法;
3、几个字母成为固定组合,被另外的固定组合代替,比如AQUA换成EDDTYM,也就是多对多的字母替换法;
4、每次用不同的字母替换同一字母,比如A换成T,下次则A换成U,比如AQUA换成TWCU,也就是不断变换的多表替换法。
首先说说这个单字替换法。
我们可以自己拟定一个规则,比如说,CODE一词的字母C、O、D、E,分别被替换成A、K、L、Y。而根据同一法则,DECODE就应该成为LYAKLY。猛一看到LYAKLY,一般人是得发晕,不知道这说的是什么。但是,数学家不是一般人,他们统计了相当数量的文本以后,发明了频率分析法,专门对付这个单字替换法。
列个简单的单子,看看频率分析法是怎么破解单字替换法的:
A 0.082 | B 0.015 | C 0.028 | D 0.043 | E 0.127 | F 0.022 | G 0.020……| T 0.091 | ……| Z 0.001
其中,字母后面跟着的数字代表它在文本中出现的统计频率。可以看出,什么字母出现概率最大?毫无疑问就是e。管你怎么替换,这个字母不会是别的。分析相当数量的根据同一法则替换之后的密文,完全可以轻松将每个字母的去向一一标明,进而,也就无密可保了。
看上去更象个小聪明的单字替换法就这么可耻地失败了。而类似地,多名码替换法、字母替换法这些加密方式一样无法逃避频率分析的威力,也跟着纷纷被拿下了。但是多名码替换法却还有人在用,直到一战中,英国人还在用这个明显不可靠的加密方式,原因为何,真是只有鬼知道了。
而最后一种,也就是多表替换法,却一跃成为了一时的主宰。
多表替换法好就好在,它的明文和密文之间的字母对应是会变的。这个“变”字,就成为密码学上一个非常成功的概念。甚至后来的ENIGMA,成功也就成功在这个变字上。
1568年Leon Battista首先发明了多表替换法,之后美国内战期间,北军用的就是这个加密方法。1858年,法国的外交官Blaise De Vigenère发明了另一套以他名字命名的Vigenère密码,从Vigenère密码里又衍生出了Beaufort密码,等等。
从原理上看,无论Battista、Vigenère和Beaufort等多表替换密码,其实都只是一个范畴的不同表现而已。而数学家所使用的频率分析法失灵的原因就是,每次变的那一下子,使密文完全不符合字母出现频率的规则了。
它的原理简单描述一下,大概是这个样子(不是很严密的):第一次对A加密的时候,出来T;下次再碰上A,按照某种顺序,比如最简单的递加顺序,则顺延T+1,变成U;第三次再碰上A,继续顺延成T+2,变成V。
于是,初始位置不知道,还可以用频率分析予以破解;但是顺延之后,频率分析就无能为力了。何况,谁知道是递加还是递减呢?谁知道是加几或者减几呢?以及,对手万一不用递加或递减,而是采用乘法除法,或者利用某个数列,比如素数数列来加密呢?而Vigenère法恰恰用的不是顺延,而是任意一组指定的数列!
这样一来,似乎无法破解的多表替代加密法就成为了密码之王。
但是,既然有人能发明,总有人能找到它的弱点。数学家又出现了!
还以多表法中最著名的Vigenère法来说。按当时的习惯,Vigenère法是这样加密明文的:
明文:ABCDEFGHIJK
密钥:3,2,6,8,1,4(表示字母向后顺延的位数)
则密文应该变为
A+3,B+2,C+6,D+8,E+1,F+4,(密钥用尽,从头开始重复加密)G+3,H+2,I+6,J+8,K+1
也就是
DDJLFJJJOQL
一次标准的加密就完成了。如果要解密,就需要知道密钥,然后倒着推算回去就是了。
从刚才的例子可以看出,密文DDJLFJJJOQL里面出现了4个J(我倒,真是随手一写,没想到搞成这样),2个D,2个L,而这些所对应的明文竟然是没有重复的ABCDEFGHIJK……Vigenère法的厉害可见一斑!
但是牛人出现了。上文说过,1858年,法国人Blaise De Vigenère发明了Vigenère多表替换法。而之后仅仅五年,普鲁士的一个少校军官,F.Kasiski找到了破解的办法!顺便说一句,又过了七年,普法战争就开始了……
说起具体的破解方法,的确就是个纯粹的数学问题了,我这人,天生不擅长数学,就不具体写了,――因为也写不出来,写出来也是别人的,自己看不懂:(――但是,可以描述一下它的原理,那就是:密钥因为种种原因,是循环使用的。上文例子中,用了六位密钥,也就是说,每六个字母,就要循环使用一次相同的密钥加密――破绽就在这里!
实际上,除非你用的多表替换的密钥无限长,那么自然无法破解――稍微想想就明白了,那相当于你发明了另外一门使用相同字母的语言啊――但是,密钥是不可能无限长的,特别是在手工操作加密和解密的时代。例如,怎么能够想像,战火纷飞的战场上,解码员手里拿着厚厚一千多页的密钥去一个个查对字母――太长了,也容易出错啊!
当时在实际应用中,密钥一般是二十位左右长。这样,就取得了一个便用性和保密性的平衡。但是,二十位的密钥,还是太短了――在数学家眼里,这相当于把彩票要选的数字从36个降到只选5个,于是,中奖的概率大大增加了。
他们用的办法还是分析。这次,主要是分析密钥的长度,换言之,是经过多少次加密以后会出现循环现象。具体算法就不罗列了,很精彩,这里只给出一个理想情况下的结果:
如果密钥字长度为M,那么密文中随机两个字母的重合指数约为0.065(也就是说,比如我挑密文中的字母A,它对应的明文恰好也是字母A的重合指数是0.065);
如果长度不是M,也就是密钥完全由随机字母形成,那么随机两个字母的重合指数约为0.038。
具体算法别问我,问我也不懂,咱只是照抄:)
曾经牛的一塌糊涂的Vigenère多表替换法终于尝到了失败的滋味。而类似的,整个多表替换法也终于在数学的威力下败下阵来……
本帖一共被 17 帖 引用 (帖内工具实现)
- 【原创】密码传奇(一):1、西线屠刀背后的五字幽灵
- 【长期有效】请大家推荐给孩子们的好书好电影好玩具
- 【原创】被征服的谜――ENIGMA的故事(四):波兰人的绝地反击(上)
- 【原创】被征服的谜――ENIGMA的故事(四)(篇外):最年轻的数学家
- 西西河能为中华民族做些什么?(一)
- 【原创】被征服的谜――ENIGMA的故事(四):波兰人的绝地反击(下下)
- 【原创】被征服的谜――ENIGMA的故事(四):波兰人的绝地反击(中上)
- 【原创】被征服的谜――ENIGMA的故事(四):波兰人的绝地反击(中中)
- 1001n的《密码传奇》系列网址
- 【原创】被征服的谜――ENIGMA的故事(四):波兰人的绝地反击(中下)
- 【原创】被征服的谜――ENIGMA的故事(四):波兰人的绝地反击(下中)
- 【原创】被征服的谜――ENIGMA的故事(篇外之二):密码的ABC
- 【原创】被征服的谜――ENIGMA的故事(篇外之四B):多表替代的六人行
- 【原创】被征服的谜――ENIGMA的故事(篇外之三):老密码,老故事
- 【原创】被征服的谜――ENIGMA的故事(篇外之四A):多表替代的六人行
- 1001n的密码故事文集
- 【目录】2。信息科学
- 相关回复 上下关系8
【原创】被征服的谜――ENIGMA的故事(一)
🙂英国portsmouth海军博物馆里面有 qianji 字26 2007-10-02 07:22:20
好文! LEADER 字0 2005-08-01 09:47:24
【欣赏】][二战剧情悬疑经典收藏][拦截密码战]/[Enigma] 3 zhonghuahero 字1525 2005-07-06 18:21:12
🙂刚看完,好片啊! 棋人鲁大耍 字219 2007-10-02 02:25:39
😜这个题目好啊,慢慢写,多写点 beyourself 字0 2005-04-19 22:23:13
疑问 晨枫 字122 2005-04-19 20:14:42
密钥您就这么理解吧 看看 字275 2005-04-19 21:45:55