ENIGMA的兴亡(三)

<![CDATA[

二、弱点(下)

 

德方每封密文最开始的六个字母,是此信密钥的三个字母重复两遍,由当日密钥加密而成。比如说这封信的密钥是ULJ(这是开始加密明文时由操作员临时随机选取的),那么操作员首先用当日通用的密钥加密ULJULJ,得到六个字母的加密后序列,比如说PEFNWZ,然后再用ULJ来作为密钥加密正文,最后把PEFNWZ放在加密后的正文前,一起用电报发给收信方。

雷杰夫斯基每天都会收到一大堆截获的德国电报,所以一天中可以得到许多这样的六个字母串,它们都由同一个当日密钥加密而成。比如说他收到四个电报,其中每封电报的开头的六个字母为

 

               1 2 3 4 5 6

第一封电报:L O K R G M

第二封电报:M V T X Z E

第三封电报:J K T M P E

第四封电报:D V Y P Z X

 

对于每封电报来说,它的第一个字母和第四个字母都是由同一个字母加密而来,同样地第二和第五个字母以及第三和第六个字母也是分别由同一个字母加密而来。比如说在第一封电报中,字母L和R是由同一字母加密而来。这个字母之所以先被加密成L,然后又被加密成了R,是因为在此期间转子向前转动了三个字母的位置。

从L和R是由同一个字母加密而来这点,雷杰夫斯基就有了判断转子的初始位置的一条线索。当转子处于这个初始位置时,字母L和R在某种意义下具有紧密的联系。每天截获的大量电文能够给出许多这样的紧密联系,从而使雷杰夫斯基最终能够判断出转子的初始位置。在上面的第二、三、四封电报中,我们看见M和X,J和M,D和P都有这种联系:

 

第一个字母:ABCDEFGHIJKLMNOPQRSTUVWXYZ

第四个字母:___P_____M_RX_____________

如果雷杰夫斯基每天可以得到充分多的电报,他就可以把上面这个关系表补充完整:

 

第一个字母:ABCDEFGHIJKLMNOPQRSTUVWXYZ

第四个字母:FQHPLWOGBMVRXUYCZITNJEASDK

 

光凭这个对应表格,雷杰夫斯基还是没办法知道当天的通用密钥。可是他知道,这个表格是由当天的通用密钥决定的,而且只由它决定。如果密钥不同,那么这个表格也应该不同——那么,有没有一种办法可以从这个对应表来推断出当日的通用密钥呢?雷杰夫斯基对这样的表格进行了仔细观察。从字母A开始看,它被对应成F;而F在此表中又被对应成W,接下去它被对应成A,我们又回到了最先开始的字母,于是就有了一个循环的字母圈A→F→W→A。如果考虑所有的字母,雷杰夫斯基就能写出关于此对应表的所有的循环圈:

 

A→F→W→A 3个字母的循环圈

B→Q→Z→K→V→E→L→R→I→B 9个字母的循环圈

C→H→G→O→Y→D→P→C 7个字母的循环圈

J→M→X→S→T→N→U→J 7个字母的循环圈

 

这里我们只是考虑了第一和第四个字母形成的对应表。同样地对第二和第五、第三和第六个字母形成的对应表,我们也可以写出类似的字母循环圈。由于每天的密钥都不同,雷杰夫斯基得到的循环圈也各不相同。

 

雷杰夫斯基观察到,这些循环圈长短不一。这使他有了一个重要的灵感:虽然这些循环圈是由当日密钥,也就是转子的位置,它们的初始方向以及连接板上字母置换造成的,但是每组循环圈的个数和每个循环圈的长度,却仅仅是由转子的位置和它们的初始方向决定的,和连接板上字母交换的情况无关!

 

假定在上面这个例子中,原来在接线板上字母S和G由一根连线相连。现在转子的位置和它们的初始方向保持不变,去掉这根连线而将字母T和K连在一起,那么第一和第四个字母的对应表就会变成

 

    第一个字母:ABCDEFGHIJKLMNOPQRSTUVWXYZ

  第四个字母:FQHPLWKSBMNRXUYCZIOVJEAGDT

 

(原来的G对应O,S对应T,去掉G和S的连线后,G就对应T,但是T被新的连线接到了K,所以G最终对应着K。其他受影响的字母还有H、K、 S、T、X、Z)。而循环圈表就变成了:

 

A→F→W→A 3个字母的循环圈

B→Q→Z→T→V→E→L→R→I→B 9个字母的循环圈

C→H→S→O→Y→D→P→C 7个字母的循环圈

J→M→X→G→K→N→U→J 7个字母的循环圈

 

某些循环圈中的字母变了,但是循环圈的数目仍旧是四个,每个循环圈的长度也没有改变。应用置换变换的理论,雷杰夫斯基可以从数学上严格证明这一点对于任何的连线变化都是成立的。

 

这是一个非常重大的进展。我们知道,如果要强行试遍所有的密钥来破解密文,那得要试一亿亿个密钥之多;但是ENIGMA的数量巨大的密钥主要是由连接板来提供的,如果只考虑转子的位置和它们的初始方向,只有105456种可能性。虽然这还是一个很大的数字,但是把所有的可能性都试验一遍,已经是一件可以做到的事情了。

 

波兰人按照汉斯-提罗·施密特提供的情报复制出了ENIGMA样机。到了1934年,他们有了十几台波兰造ENIGMA。雷杰夫斯基和他的同事们每天都在ENIGMA前工作,一个接一个地试验转子的不同位置和初始方向,然后产生相应的字母对应表并构造相应的字母循环圈,并把它们记录下来。比如说其中的一个记录可以是这样的:

 

第一和第四字母对应表中有4个循环圈,长度分别为3,9,7,7;  

第二和第五字母对应表中有4个循环圈,长度分别为2,3,9,12;  

第三和第六字母对应表中有5个循环圈,长度分别为5,5,5,3,8;

当对所有105456种转子位置和初始方向都编好记录以后,破译 ENIGMA生成的密文就比较容易了。首先要取得足够的当日电文来构造字母对应表并且写出字母循环圈;然后根据循环圈的数目和它们的长度从记录表中检索出相对应的转子位置和初始方向:这就是当日的密钥(连接板的情况还未知)。循环圈的个数和长度可以看作是这个密钥的“指纹”——通过建立密钥“指纹”档案,雷杰夫斯基就能及时地把当天的密钥找出来。通过分离转子的状态和连接板的状态,雷杰夫斯基大大简化了破译ENIGMA的工作。建立这样一个档案花了整整一年时间,工作相当艰苦,有时工作人员的手指都被磨出血来。

 

必须指出的是,上面对雷杰夫斯基的工作的介绍是极其简单化的,只以举例的形式介绍了其中最重要的思路。雷杰夫斯基对于ENIGMA 的分析是在密码分析史上最重要的成就之一,整个工作都是严格地数学化了的(求解关于置换矩阵的方程),决非上面所举例子可以包含。比如说,找到当日密钥中转子状态后,还需要找到连接板状态,才能真正译出密文。另外,ENIGMA中转子中的线路并非总是固定不变,雷杰夫斯基的理论允许从密文和密钥倒推出转子内部的连线状态。即便是施密特提供的情报也未明确指出转子内部的连线状态,雷杰夫斯基一项重要工作就是成功地判断出军用型ENIGMA的转子上字母以字母表顺序排列,而不是如商用型那样,字母以键盘上的顺序排列

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

One Response to ENIGMA的兴亡(三)

  1. Hi, interesting post. I have been thinking about this issue,so thanks for blogging. I’ll likely be coming back to your blog. Keep up great writing