首页 > 代码库 > 恩尼格码的发明和破解
恩尼格码的发明和破解
恩尼格码是二战德军所采用的电子加密机械
其基本组成可以分为三部分:
键盘,转子和显示器
键盘一共具有26个键,类似于今天的计算机键盘(显示起见,省略为6个)
转子实际上有3个,缩略起见只画了1个
显示器在最右边,当键盘上的键被按下时,字母被加密后所对应的小灯就会在显示器上亮起来
即按下a灯,B灯会亮,这就意味着a被加密成了B
同样的,b被加密成了A,c被加密成了D,d被加密成了F,e被加密成了E,f被加密成了C。
这种加密方式称为“简单替换算法”。
“简单替换”在现实中很容易通过频率统计法破解,这就用到了转子。
转子的作用在于键盘上的一个键被按下时,相应的密文会在显示器上显示,然后转子的方向就会自动的转动一个字母的位置。
例如,当连续的按下3个b时:
第一次键入b时,信号通过转子中的连线使得A灯亮了起来,然后转子转动一格;
第二次键入b时,它所对应的字母就变成了C;
同样的,第三次键入b时,灯E会变亮。
这里看到了恩尼格码的关键:这并不是一个简单替换算法,同一个字母b在明文的不同位置时,可以被不同的字母所替换,而密文中不同位置的同一个字母,可以代表明文中的不同字母。这就使得频率分析法没有用武之地了。这种加密方式被称为“复式替换密码”
但是如果连续的键入6个键(实际有26个键),转子就会整整转一圈,回到原始的方向上,这时编码就和最初重复了。于是在实际的恩尼格码中,一共有3个转子(二战后期甚至有4个转子)
所以要在26*26*26=17576后才会重复原来的编码。
自此基础上,设计者巧妙地在三个转子的一端加上了反射器。
如图所示,键盘和显示器中的相同字母被连到了一起。反射器和转子一样,把一个字母连在另一个字母上,但是并不转动。乍一看这个固定的反射器并没有作用,并不增加可以使用的编码数目,但是如果将它和解码联系起来就会发现这种设计的别具匠心之处:
当一个键被按下时,信号并不从键盘直接传到显示器,而是首先通过三个转子连成的一条线路,然后通过反射器回到3个转子,再通过另一条线路到达显示器上。例如,b键被按下时,D灯亮。
如果此时按下的不是b键而是d键,则信号会按照相反的方向,到达B灯。
也就是说,反射器虽然没有增加可能的不重复方向,但是使得编码过程和解码过程完全一致。
在实际情况下:发信人首先要调整三个转子的方向,使其处于17576中的一个方向(其实转子的初始方向即为密钥,这是约定好的),然后依次键入明文,发送出去。解密方只需要使用一台相同的恩尼格码机,按照约定,将转子的方向调整至和发信方相同,依次键入得到的密文,就可以得到明文--这就是反射器的作用
我们也可以得到,反射器的一个副作用就是一个字母永远也不能被加密成它自己,因为反射器中的1个字母总是被连接到另外1个字母。
也就是说,转子的初始方向决定了整个密文的加密方式。
虽然17576很大,但是也足够进行暴力破解。当然设计者也可以再多增加转子,但是我们发现,每增加一个转子,也只是使得转子的初始方向增加了26倍(即乘26),同样增加了转子也就增加了恩尼格码的体积和成本
这时设计者使得三个转子做得可以拆卸下来互相交换,这样一来初始方向的可能性变成了原来的六倍:
即将3个转子编号为1、2、3,那么它们可以被放成,123-132-213-231-312-321一共六种不同的位置,也就是说,现在收发信息的双方除了要约定好转子的初始方向,还必须约定好六种排列中的一种。
不过增加6种转子的排列方式也并不能有效地回避暴力破解问题。
下一步设计者在键盘和第一转子之间增加了一个连接板,这块连接板允许使用者用一根连线把某个字母和另一个字母连起来,这样这个字母的信号在进入转子之前就会变成另一个字母的信号,这样的连线一共有6根。
这样就可以使得6对字母的信号互换,其他没有连线的字母保持不变。当然连线状况也需要约定好
那么由转子自身的初始方向,转子之间的位置,以及连接板连线的状况就组成了所有可能的密钥:
三个转子不同的方向为26*26*26=17576种;
三个转子之间的相对位置为6种;
连接板上两两交换6对字母的可能性很大,由排列组合可得为100391791500种;
于是一共具有17576*6*100391791500,大约1亿亿种可能性。
只要约定好上面的密钥,收发双方之间就可以简单的加密和解密,但是如果不知道密钥,破解出来基本没有可能。
我们总结一下可以发现,连线班对可能性的贡献最大,但是由于连线班本身是一个“简单替换”,非常容易被频率分析;转子的提供的可能虽然不多,但是其“复式替换”系统的设计,使得整个系统再也无法受到频率分析。这二者优势互补,增加了可能性,也使得暴力破解望而却步。(这是我认为恩尼格码机最出色,也是最有魅力的设计所在)。
“加密系统的保密性只应建立在对密钥的保密上,而不应该取决于加密算法的保密”。恩尼格码的设计使得,即使敌人获取了一台恩尼格码机,但是如果不知道密钥(即转子的初始方向,转子的相对位置以及连线板的连接情况),破解是不现实的。
在战争期间,如果每天只有一个密钥,那么难免被对方截获大量的以同一个密钥加密的信息,这对保密工作有害无益。尽管不知道对于恩尼格码机是否可以采用类似的方法,德国人还是留了个心眼。他们决定在当天密钥调整好的恩尼格码机上不直接加密要发送的明文,相反的,首先发送的是一个新的密钥。
例如,在连线板的连接顺序和转子的顺序不改变的情况下,随机选择三个字母,输入两次,比如PEHPEH,加密为比如KIVNSE(注意复式加密的会被加密成不同的形式,第一次KIV,第二次NSE),然后发信方把KIVNSE放在电文的最前面,接着重新调整三个转子的初始方向到PEH,才开始继续加密。
这种方法的每一份电报都有属于自己的三个表示初始方向的密钥。输入两遍是为了纠错。
恩尼格码的发明和破解