转:ENIGMA的兴亡(一)

【本文出自《三思·科学》电子杂志第二期,2001年8月1日。三思科学网http://www.oursci.org/,由于该网站的改造,原来的链接找不到了。】

人类使用密码的历史,从今天已知的,最早可以一直追溯到古巴比伦人的泥板文字。古埃及人,古罗马人,古阿拉伯人……几乎世界历史上所有文明都使用过密码。军事和外交一直是密码应用的最重要的领域,国王、将军、外交官以及阴谋分子等,为了在通讯过程中保护自己信息不被外人所知,使用过形形色色的密码;而为了刺探于己不利的秘密,他们又绞尽脑汁地试图破译对手的密码。加密与解密一直是密码学这枚硬币互相对抗又互相促进的两面。在所有用于军事和外交的密码里,最著名的恐怕应属第二次世界大战中德国方面使用的 ENIGMA(读作“恩尼格玛”,意为“谜”)。

 

一、诞生   

直到第一次世界大战结束为止,所有密码都是使用手工来编码的。直接了当地说,就是铅笔加纸的方式。在我国,邮电局电报编码和译码直到很晚(大概是上个世纪八十年代初)还在使用这种手工方法。手工编码的方式给使用密码的一方带来很多的不便。首先,这使得发送信息的效率极其低下。明文(就是没有经过加密的原始文本)必须由加密员人工一个一个字母地转换为密文。考虑到不能多次重复同一种明文到密文的转换方式(这很容易使敌人猜出这种转换方式),和民用的电报编码解码不同,加密人员并不能把转换方式牢记于心。转换通常是采用查表的方法,所查表又每日不同,所以解码速度极慢。而接收密码一方又要用同样的方式将密文转为明文。其次,这种效率的低下的手工操作也使得许多复杂的保密性能更好的加密方法不能被实际应用,而简单的加密方法根本不能抵挡解密学的威力。   解密一方当时正值春风得意之时,几百年来被认为坚不可破的维吉耐尔(Vigenere)密码和它的变种也被破解。而无线电报的发明,使得截获密文易如反掌。无论是军事方面还是民用商业方面都需要一种可靠而又有效的方法来保证通讯的安全。   1918年,德国发明家亚瑟·谢尔比乌斯(Arthur Scherbius)和他的朋友理查德·里特(Richard Ritter)创办了谢尔比乌斯和里特公司。这是一家专营把新技术转化为应用方面的企业,很象现在的高新技术公司,利润不小,可是风险也很大。谢尔比乌斯负责研究和开发方面,紧追当时的新潮流。他曾在汉诺威和慕尼黑研究过电气应用,他的一个想法就是要用二十世纪的电气技术来取代那种过时的铅笔加纸的加密方法。

arthur-scherbius

谢尔比乌斯发明的加密电子机械名叫ENIGMA,在以后的年代里,它将被证明是有史以来最为可靠的加密系统之一,而对这种可靠性的盲目乐观,又使它的使用者遭到了灭顶之灾。这是后话,暂且不提。

enigma

ENIGMA看起来是一个装满了复杂而精致的元件的盒子。不过要是我们把它打开来,就可以看到它可以被分解成相当简单的几部分。下面的图是它的最基本部分的示意图,我们可以看见它的三个部分:键盘、转子和显示器。

roter-1

 

在上面ENIGMA的照片上,我们看见水平面板的下面部分就是键盘,一共有26个键,键盘排列接近我们现在使用的计算机键盘。为了使消息尽量地短和更难以破译,空格和标点符号都被省略。在示意图中我们只画了六个键。实物照片中,键盘上方就是显示器,它由标示了同样字母的26个小灯组成,当键盘上的某个键被按下时,和此字母被加密后的密文相对应的小灯就在显示器上亮起来。同样地,在示意图上我们只画了六个小灯。在显示器的上方是三个转子,它们的主要部分隐藏在面板之下,在示意图中我们暂时只画了一个转子。   

键盘、转子和显示器由电线相连,转子本身也集成了6条线路(在实物中是26条),把键盘的信号对应到显示器不同的小灯上去。在示意图中我们可以看到,如果按下a键,那么灯B就会亮,这意味着a被加密成了B。同样地我们看到,b被加密成了A,c被加密成了D,d被加密成了F,e被加密成了E,f被加密成了C。于是如果我们在键盘上依次键入cafe(咖啡),显示器上就会依次显示DBCE。这是最简单的加密方法之一,把每一个字母都按一一对应的方法替换为另一个字母,这样的加密方式叫做“简单替换密码”。   

简单替换密码在历史上很早就出现了。著名的“凯撒法”就是一种简单替换法,它把每个字母和它在字母表中后若干个位置中的那个字母相对应。比如说我们取后三个位置,那么字母的一一对应就如下表所示:   

明码字母表:abcdefghijklmnopqrstuvwxyz   

密码字母表:DEFGHIJKLMNOPQRSTUVWXYZABC   

于是我们就可以从明文得到密文:(veni, vidi, vici,“我来,我见,我征服”是儒勒·凯撒征服本都王法那西斯后向罗马元老院宣告的名言)   

明文:veni, vidi, vici   

密文:YHAL, YLGL, YLFL   

 

很明显,这种简单的方法只有26种可能性,不足以实际应用。一般上是规定一个比较随意的一一对应,比如   

明码字母表:abcdefghijklmnopqrstuvwxyz   

密码字母表:JQKLZNDOWECPAHRBSMYITUGVXF

甚至可以自己定义一个密码字母图形而不采用拉丁字母。但是用这种方法所得到的密文还是相当容易被破解的。至迟在公元九世纪,阿拉伯的密码破译专家就已经娴熟地掌握了用统计字母出现频率的方法来击破简单替换密码。破解的原理很简单:在每种拼音文字语言中,每个字母出现的频率并不相同,比如说在英语中,e出现的次数就要大大高于其他字母。所以如果取得了足够多的密文,通过统计每个字母出现的频率,我们就可以猜出密码中的一个字母对应于明码中哪个字母(当然还要通过揣摩上下文等基本密码破译手段)。柯南·道尔在他著名的福尔摩斯探案集中《跳舞的人》里详细叙述了福尔摩斯使用频率统计法破译跳舞人形密码的过程。

  所以如果转子的作用仅仅是把一个字母换成另一个字母,那就没有太大的意思了。但是大家可能已经猜出来了,所谓的“转子”,它会转动!这就是谢尔比乌斯关于ENIGMA的最重要的设计——当键盘上一个键被按下时,相应的密文在显示器上显示,然后转子的方向就自动地转动一个字母的位置(在示意图中就是转动1/6圈,而在实际中转动1/26圈)。下面的示意图表示了连续键入3个b的情况:

 

roter-2

 

当第一次键入b时,信号通过转子中的连线,灯A亮起来,放开键后,转子转动一格,各字母所对应的密码就改变了;第二次键入b时,它所对应的字母就变成了C;同样地,第三次键入b时,灯E闪亮。

 

roter-3

照片左方是一个完整的转子,右方是转子的分解,我们可以看到安装在转子中的电线。

  这里我们看到了ENIGMA加密的关键:这不是一种简单替换密码。同一个字母b在明文的不同位置时,可以被不同的字母替换,而密文中不同位置的同一个字母,可以代表明文中的不同字母,频率分析法在这里就没有用武之地了。这种加密方式被称为“复式替换密码”。

   但是我们看到,如果连续键入6个字母(实物中26个字母),转子就会整整转一圈,回到原始的方向上,这时编码就和最初重复了。而在加密过程中,重复的现象是很危险的,这可以使试图破译密码的人看见规律性的东西。于是谢尔比乌斯在机器上又加了一个转子。当第一个转子转动整整一圈以后,它上面有一个齿拨动第二个转子,使得它的方向转动一个字母的位置。看下面的示意图(为了简单起见,现在我们将它表示为平面形式):

roter-4

这里(a)图中我们假设第一个转子(左边的那个)已经整整转了一圈,按b键时显示器上D灯亮;当放开b键时第一个转子上的齿也带动第二个转子同时转动一格,于是(b)图中第二次键入b时,加密的字母为F;而再次放开键b时,就只有第一个转子转动了,于是(c)图中第三次键入b 时,与b相对应的就是字母B。   

我们看到用这样的方法,要6*6=36(实物中为26*26=676)个字母后才会重复原来的编码。而事实上ENIGMA里有三个转子(二战后期德国海军用ENIGMA甚至有四个转子),不重复的方向个数达到26*26*26 =17576个。

 

在此基础上谢尔比乌斯十分巧妙地在三个转子的一端加上了一个反射器,而把键盘和显示器中的相同字母用电线连在一起。反射器和转子一样,把某一个字母连在另一个字母上,但是它并不转动。乍一看这么一个固定的反射器好象没什么用处,它并不增加可以使用的编码数目,但是把它和解码联系起来就会看出这种设计的别具匠心了。见下图:

roter-5

 

我们看见这里键盘和显示器中的相同字母由电线连在一起。事实上那是一个很巧妙的开关,不过我们并不需要知道它的具体情况。我们只需要知道,当一个键被按下时,信号不是直接从键盘传到显示器(要是这样就没有加密了),而是首先通过三个转子连成的一条线路,然后经过反射器再回到三个转子,通过另一条线路再到达显示器上,比如说上图中b键被按下时,亮的是D灯。我们看看如果这时按的不是b键而是d键,那么信号恰好按照上面b键被按下时的相反方向通行,最后到达B灯。换句话说,在这种设计下,反射器虽然没有象转子那样增加可能的不重复的方向,但是它可以使译码的过程和编码的过程完全一样。

roter-6

 

想象一下要用ENIGMA发送一条消息。发信人首先要调节三个转子的方向,使它们处于17576个方向中的一个(事实上转子的初始方向就是密匙,这是收发双方必须预先约定好的),然后依次键入明文,并把闪亮的字母依次记下来,然后就可以把加密后的消息用比如电报的方式发送出去。当收信方收到电文后,使用一台相同的ENIGMA,按照原来的约定,把转子的方向调整到和发信方相同的初始方向上,然后依次键入收到的密文,并把闪亮的字母依次记下来,就得到了明文。于是加密和解密的过程就是完全一样的——这都是反射器起的作用。稍微考虑一下,我们很容易明白,反射器带来的一个副作用就是一个字母永远也不会被加密成它自己,因为反射器中一个字母总是被连接到另一个不同的字母。

roter-7

安装在ENIGMA中的反射器和三个转子

 

于是转子的初始方向决定了整个密文的加密方式。如果通讯当中有敌人监听,他会收到完整的密文,但是由于不知道三个转子的初始方向,他就不得不一个个方向地试验来找到这个密匙。问题在于17576 个初始方向这个数目并不是太大。如果试图破译密文的人把转子调整到某一方向,然后键入密文开始的一段,看看输出是否象是有意义的信息。如果不象,那就再试转子的下一个初始方向……如果试一个方向大约要一分钟,而他二十四小时日夜工作,那么在大约两星期里就可以找遍转子所有可能的初始方向。如果对手用许多台机器同时破译,那么所需要的时间就会大大缩短。这种保密程度是不太足够的。

当然谢尔比乌斯还可以再多加转子,但是我们看见每加一个转子初始方向的可能性只是乘以了26。尤其是,增加转子会增加ENIGMA 的体积和成本。谢尔比乌斯希望他的加密机器是便于携带的(事实上它最终的尺寸是34cm*28cm*15cm),而不是一个具有十几个转子的庞然大物。首先他把三个转子做得可以拆卸下来互相交换,这样一来初始方向的可能性变成了原来的六倍。假设三个转子的编号为1、2、3,那么它们可以被放成123-132-213-231-312-321六种不同位置,当然现在收发消息的双方除了要预先约定转子自身的初始方向,还要约定好这六种排列中的使用一种。

 

下一步谢尔比乌斯在键盘和第一转子之间增加了一个连接板。这块连接板允许使用者用一根连线把某个字母和另一个字母连接起来,这样这个字母的信号在进入转子之前就会转变为另一个字母的信号。这种连线最多可以有六根(后期的ENIGMA具有更多的连线),这样就可以使6对字母的信号互换,其他没有插上连线的字母保持不变。在上面ENIGMA的实物图里,我们看见这个连接板处于键盘的下方。当然连接板上的连线状况也是收发信息的双方需要预先约定的。

roter-8

在上面示意图中,当b键被按下时,灯C亮。

 

  于是转

This entry was posted in Uncategorized and tagged . Bookmark the permalink.

Comments are closed.