西西河

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

共:💬14 🌺64 新:
分页树展主题 · 全看
  • 家园 【原创】被征服的谜――ENIGMA的故事(一)

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

    关键词(Tags): #密码(朴石)#西河名帖(朴石)元宝推荐:抱朴仙人,不爱吱声, 通宝推:林风清逸,

    本帖一共被 17 帖 引用 (帖内工具实现)
    • 家园 英国portsmouth海军博物馆里面有

      英格玛的实物

      可惜不给拍照

    • 家园 好文!
    • 家园 【欣赏】][二战剧情悬疑经典收藏][拦截密码战]/[Enigma]

      中文片名:《拦截密码战》又名《密码迷情》又名《谜》

      ◆英文片名:Enigma

      ◆出产地区:英国 / 美国

      ◆制作公司:Broadway Pictures [us]

      ◆发行公司:Shochiku Films Ltd. [jp]

      ◆首映日期:2001年01月22日(美国)

      ◆影片类型:战争(War)/爱情(Love)/剧情(Plot)/悬疑(Suspense)

      ◆官方网站: http://www.enigma-themovie.com/

      ◆MPAA级别:Rated R for a sex scene and language.

      ◆影片长度:119分钟

      ◆影片格式:高清晰/DVD-RMVB

      ◆对白语言:英语

      ◆语言字幕:中文字幕

      ◆导 演:迈克尔?艾普特 (Michael Apted)

      ◆编 剧:汤姆?斯托帕德 (Tom Stoppard)

      汉纳?维格 (Hannah Weg)

      ◆主 演:道格瑞?斯科特 Dougray Scott

      杰瑞米?诺森 Jeremy Northam .... Wigram

      凯特?温斯莱特 Kate Winslet .... Hester Wallace

      Mick Jagger .... Soldier in Bar (uncredited)

      萨弗蓉?布罗斯 Saffron Burrows .... Claire Romilly

      Tim Bentinck .... U-Boat Commander

      Wilhelm Brückner .... Himself (accompanies Hitler) (archive footage)

      Emma Buckley .... Land Army Girl

      Nikolaj Coster-Waldau .... Jozef 'Puck' Pukowski

      Emma Davies .... Pamela

      Anne-Marie Duff .... Kay

      汤姆?菲舍尔 Tom Fisher .... Upjohn

      Josef Goebbels .... Himself (accompanies Hitler) (archive footage)

      Edward Hardwicke .... Heaviside

      Adolf Hitler .... Himself (arrives at rally) (archive footage) (uncredited)

      Tom Hollander .... Logie

      bt 链接

      http://www.qqoo.net/job.php?action=download&pid=tpc&tid=18334&aid=19085

      • 家园 刚看完,好片啊!

        1001N兄当年的这个密码系列让俺佩服得五体投地啊。然后就是那个《与青春有关的日子》的剧评。刚看完这片子就赶紧来找这密码系列,于是在他老人家的博客挖啊挖的——竟意外发现还是个川菜爱好者。大牛啊大牛!

        经鉴定,此牛比萨苏还大。

    • 家园 这个题目好啊,慢慢写,多写点
    • 家园 疑问

      频率分析法对英文有效,对法文、德文是不是要用不同的频率?对中文怎么办呢?

      WINZIP有128位的key,是不是就是文中所提的密钥?

      • 疑问
        家园 密钥您就这么理解吧

        比如拿字母替换法来说吧,密钥就是密码本,字母替换就是加密/解密算法,加上明文、密文,一个加密系统就齐全了。

        您要换一个密码本,就等于是换了个密钥,这样同样的明文经过同样的算法加密出来的密文就不同了。解密的人除非也有您更换了的密码本,否则他从密文中解出来的明文就牛头不对马嘴了。

      • 疑问
        家园 中文也有词频分析

        而且开展得不算太晚。

        不知道你注意过没有,市面上这些个拼音输入法,候选字、词的排列顺序都大同小异?这个就是词频统计的贡献了。

        原先读书的时候见过一个,老师在课堂上展示的,记得是中科院的成果。排头的字词除了“的”“地”“得”、“这”“那”“不”“是”什么的,接下来的居然是“革命”、“专政”、“无产阶级”......

        当然这个也在不断变化更新。

        • 家园 嗯,是有这么回事

          不过不管怎么说,中文的词频毕竟比英文要复杂一点,因为英文的常用字母是不变的,而中文的常用“字母”是变的,君不见,网络一时兴,“砍”,“妹儿”,这些本来并不高频的字、词一下子出现频率大涨,这词频分析必须是动态的,与时俱进才行。

      • 疑问
        家园 试验回答

        的确,那个单子是英文字母在英文文献中出现的频率。对待法文,德文,甚至俄文等等,连字母都不一样了,当然要结合该语种的文献另外统计频率表了:)

        关于中文,确实是个很有意思的问题。由于密码学的发展主要确实在西方(唉。。),我能看到的披露的研究密码的文献,一般的重点也在英文等语种上。

        对于中文如何密码化,我确实所知甚少,只好猜测一下了。个人觉得,中文较之拼音化语言,在编码上有个先天的麻烦,也是个先天的优势,那就是:拼音化文字常常只有二三十个字母,如:

        英语26个字母;

        丹麦语29个字母;

        希伯莱语21个字母;

        阿拉伯语28个字母;

        越南语30个字母;

        西班牙语27个字母;

        即便是最麻烦的日语假名,也只有79个字母。

        但中文是非拼音化语言,光GB2312里规定的一级常用汉字就有3755个,到GB18030就发展为27533个汉字,考虑到康熙字典,更是收录了47035个汉字……

        有时候我在想,这么多的汉字,其实本身就是一种非常优异的编码。只是,谁也不可能造出一个有着成千上万按键的键盘来输入中文,在计算机时代,这个缺陷就一票否决了原样不动的汉字录入方案。

        而对汉字进行编码,无论是区位也好,拼音也好,实际上都是把关联不大的汉字活活地给装在由数字或者字母构成的笼子里。这样,汉字可以用普通键盘输入了,代价就是丧失了汉字的感官上的、构成上的、相近相异方面上的所有特性。

        但不这样,似乎也没有更好的办法……

        而数字化或字母化之后,中文就跟别的语言没有什么区别了,能编码加密了,自然也能解码解密了。

        话说回来,现代的加密技术早已经突飞猛进到了很高的水准。我以前几篇文章所写的内容,其实在密码学上,都被称为古典密码。呵呵,够老土的吧?

        而winzip用的128位加密,其实已经不是古典加密的范畴了,而此密钥非彼密钥,这个问题容我有时间慢慢写来:)

        • 家园 这个可能是这样,

          输入方法和存储/传输方法是不同的,中文和西欧文字存储都是以二进制存储传输,但是西文相当于把词语“打碎”成字母,而汉字相当于把词语“拼凑”成字,每个存储单位比ASCII要长,对于词频分析难度自然要大点。

          不过对于“现代密码学”,都差不多了。

        • 家园 继续请教

          用拼音输入的中文,同样的拼音,可以有很多组合,一个句子下来,组合数就大大增加,是不是还具有“天然编码”的优点呢?

    • 家园 沙发!

      先顶再看,呵呵

分页树展主题 · 全看


有趣有益,互惠互利;开阔视野,博采众长。
虚拟的网络,真实的人。天南地北客,相逢皆朋友

Copyright © cchere 西西河