主题:【原创】被征服的谜――ENIGMA的故事(一) -- 1001n

大河奔流 导读 复 13 阅 66234

全看 分页 树展 一览 主题

2005-04-19 06:54:24
主题:371599
1001n1001n`1349`http://storage.msn.com/x1pCAtekYRvGB3pLpHMw1Fp-rr8pZ5xaaMm9J8XDpzzQIbe2bHHWI87_wA9hiBL7EUVGL2k6crGm3OU53MoBXxJv5AR_0Clg0WHA5v4zrAaLTd-uc_WRXxbJqAxE9b9Y4_5-JCjG7vg7s-9ZzgxynIwVg`70`464`10611`136424`从四品上:太中大夫|宣威将军`2003-10-06 16:04:55`
【原创】被征服的谜――ENIGMA的故事(一) 59

被征服的谜――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多表替换法终于尝到了失败的滋味。而类似的,整个多表替换法也终于在数学的威力下败下阵来……


  • 本帖 6 回复
关键词(Tags): #密码(朴石)#西河名帖(朴石)资深推荐:抱朴仙人,不爱吱声, 通宝推:林风清逸,
AleaJactaEst 选转。
2005-04-19 06:54:24

全看 分页 树展 一览 主题