注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

苗得雨:网事争锋

我们在攻击邪恶和黑暗时要毫不留情,但是也要腾出时间来为善行鼓掌,为光明喝彩!

 
 
 

日志

 
 

黑客编年史 之加密之王Enigma英格玛  

2012-05-18 17:08:44|  分类: 网络安全专栏 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
 

在我渺小的日子里,我也曾阅历帝国的兴亡,

但是我并没有衰老;

当我把自己的忧患和那一切相比,

它虽曾奔腾象海湾中狂暴的浪涛,

却成了小小水化的泼溅,

随时平息;

的确,

有一些什么-连我也不明了-在支持这不知忍耐的灵魂;

我们并不白白地(即使仅仅为它自己)贩来痛苦。

——拜伦《书寄奥古斯达》选段

黑客是征服者的战争,然而征服往往是从被征服开始的。

二战前夕,随着世界上最先进的密码机Enigma(意为“谜”)在纳粹德国的铺开使用,让波兰、法国、英国等国家的顶尖智慧群体,陆续被卷入了这场旷日持久的密码战。加密、破解,疯狂升级,天才、叛徒,粉墨登场,也由此掀开了人类历史上最波澜壮阔的加密与解密大战……

第00000011/三章节 加密之王Enigma

第二次世界大战爆发于1939年,历时6年之久,先后有60多个国家和地区参战,波及20多亿人口,战争交战各方共动员军队1亿多人。在这场人类有史以来最惨烈的战争中,决定最后战争命运走向的竟然是几台机器和制造它们的天才数学家们。而在第二次世界大战中最大的军事秘密,除了原子弹外,就是纳粹德国的核心密码——Enigma。

Enigma从外表看起来并没有什么能够让人感到惊奇的地方,它似乎跟普通的打字机别无二致。Enigma是一种转轮式密码机,原理并不复杂,但在第二次世界大战之前要破解它却基本上是不可能的。

一台普通的Enigma通常有三个部分组成:键盘、转轮和显示器。

黑客编年史 之加密之王Enigma英格玛 - 苗得雨 - 苗得雨:网事争锋

 

黑客编年史 之加密之王Enigma英格玛 - 苗得雨 - 苗得雨:网事争锋

 

黑客编年史 之加密之王Enigma英格玛 - 苗得雨 - 苗得雨:网事争锋

 

黑客编年史 之加密之王Enigma英格玛 - 苗得雨 - 苗得雨:网事争锋

 

黑客编年史 之加密之王Enigma英格玛 - 苗得雨 - 苗得雨:网事争锋

 

黑客编年史 之加密之王Enigma英格玛 - 苗得雨 - 苗得雨:网事争锋

 

黑客编年史 之加密之王Enigma英格玛 - 苗得雨 - 苗得雨:网事争锋

 

黑客编年史 之加密之王Enigma英格玛 - 苗得雨 - 苗得雨:网事争锋

 

黑客编年史 之加密之王Enigma英格玛 - 苗得雨 - 苗得雨:网事争锋

 

黑客编年史 之加密之王Enigma英格玛 - 苗得雨 - 苗得雨:网事争锋

  

Enigma的键盘排列接近我们现在使用的计算机键盘。不过为了能够让密电尽量简短和难以破译,它没有空格和标点符号。而它使用的加密方法在现在计算机的很多软件注册中依然常见,这种加密方法叫做“代替密码算法(Substitution cipher)”。

代替密码算法是历史上最古老也是最有效的加密算法之一,它很早就登上了历史的舞台,最著名的“恺撒密码”(又名Caesar密码)所采用的就是这种加密方式。传说,它的发明人是人类历史上最著名的皇帝之一,有着“古罗马唯一的天才”之称的朱利斯·凯撒(Julius Caesar)。

据说凯撒是这样使用这种加密方法的:他先把自己的军事命令中的字母写成字母顺序的数字,然后他在将每个数字加3。如果这个数字大于字母表中的数字,那么凯撒就将这个数字与字母顺序中最后也是最大的那个数字相减之差来表示。通过这种数字机密的信息,凯撒派出的传令兵即便被抓到了,敌人也无法迫使他们供出绝密的信息,而接收到该加密密文的罗马将领们只需反过来运算,就可以得到原始军事命令了。例如:

明码字母表:abcdefghijklmnopqrstuvwxyz

密码字母表:DEFGHIJKLMNOPQRSTUVWXYZABC

根据上面的加密对照表,凯撒如果想发出“Veni,Vidi,Vici”,即凯撒征服本土国王之后向罗马元老院发出的呐喊“我来,我见,我征服!”,那么加密后的密文应该是这样的:

明文:veni, vidi, vici

密文:YHAL, YLGL, YLFL

小知识:消息(Message)被称为明文(Plaintext)。用某种方法伪装消息以隐藏它的内容的过程被称为加密(Encryption),被加密的消息称为密文(Ciphertexe),而负责把密文转变成明文的过程成为解密(Decryption)

Enigma采用的加密方法正是这种看似简单的加密方式。它通过由电线相连的键盘、转轮和显示器,将键盘上的信号对应到加密机显示器上。但是很明显,这种简单的方法只有26种可能性,不足以实际应用,用这种方法所得到的密文还是相当容易被破解的。

因此在公元九世纪,阿拉伯的密码破译专家就已经娴熟地掌握了用统计字母出现频率的方法来击破简单代替密码。破解的原理很简单:在每种拼音文字语言中,每个字母出现的频率并不相同,比如说在英语中,e出现的次数就要大大高于其他字母——这种方法后来在计算机应用密码学中被称之为重合码计数法(Counting coincidence)。

所以如果取得了足够多的密文,通过统计每个字母出现的频率,通过揣摩上下文等基本密码破译手段,很快就可以猜出密码中的一个字母对应于明码中哪个字母。柯南?道尔在他著名的福尔摩斯探案集中《跳舞的人》里就详细叙述了福尔摩斯使用频率统计法破译跳舞人形密码的过程。

因此谢尔比乌斯发明了对于Enigma来说最关键的加密部件——转轮机(Rotor machine)。它是一个会自动转动替换对应字母的设备,是从凯撒加密法中延伸出来的更为复杂的维吉尼亚(Vigenere)和博福特(Beaufort)密码的电子机械实现。维吉尼亚密码与凯撒加密法的最大区别就在于它引入了“密钥(Key)”这一概念,即根据密钥来决定用哪一行的密表来进行替换,以此来对抗字频统计。

当在Enigma键盘上一个键被按下时,相应的密文在显示器上显示,然后转轮的方向就自动地转动一个字母的位置。也就是说,当第一次键入b时,信号通过转轮中的连线,灯A亮起来,放开键后,转轮转动一格,各字母所对应的密码就改变了;第二次键入b时,它所对应的字母就变成了C;同样地,第三次键入b时,灯E闪亮。

这是Enigma的秘密所在,它绝非是以往的那种“简单代替密码算法(Simple Substitution cipher)”。同一个字母b在明文的不同位置时,可以被不同的字母替换,而密文中不同位置的同一个字母,可以代表明文中的不同字母,频率分析法在这里就没有用武之地了。这种加密方式被称为“多表代替密码算法(polyalphabetic substitution cipher)”。

多表代替密码有多个单字母密钥,每一个密钥被用来加密一个明文字母。第一个密钥加密明文的第一个字母,第二个密钥加密明文的第二个字母等等。在所有的密钥用完后,密钥又再循环使用,若有20个单个字母密钥,那么每隔20个字母的明文都被同一密钥加密,这叫做密码的周期。

在经典密码学中,密码周期越长越难破译,使用计算机就能够轻易破译具有很长周期的代替密码。跟今天不断升级的加密算法位数一样,加密过程中编码重复出现的现象是很危险的,重合指数(index of coincidence)过高可以使试图破译密码的人看见规律性的东西。为了避免在加密过程中产生大量的重复编码,Enigma可以在机器中任意添加转轮,每添加一个转轮,就会增加新的破解难度,如同64位加密算法升级到128位一样,当第一个转轮转动整整一圈以后,它上面有一个齿拨动第二个转轮,使得它的方向转动一个字母的位置。

用这样的方法,要26*26=676个字母后才会重复原来的编码。而事实上通常使用的Enigma里有三个转轮,它使得不重复的方向个数达到26*26*26=17576个。机密度更高的部门可以添加更多的转轮,如二战后期德国海军所用的Enigma甚至有四个转轮,因为所有的转轮以不同的速度移动,n个转轮的机器的加密周期就是26的n次方,这样的加密强度可想而知。

而在此基础上,谢尔比乌斯更是十分巧妙地在三个转轮的一端加上了一个反射器,这样能够让Enigma把键盘和显示器中的相同字母用电线连在一起。反射器和转轮一样,把某一个字母连在另一个字母上,但是它并不转动。

事实上它只是一个巧妙的开关,使用者并不需要知道它的是如何工作的情况。他们只需要知道,当一个键被按下时,信号不是直接从键盘传到显示器(要是这样就没有加密了),而是首先通过三个转轮连成的一条线路,然后经过反射器再回到三个转轮,通过另一条线路再到达显示器上,在这种设计下,反射器虽然没有像转轮那样增加可能的不重复的方向,但是它可以使译码的过程和编码的过程完全一样,大大的提高了使用的简洁性。

在今天,我们仍然可以想象这样场景,一台Enigma摆放在我们的面前,我们将它轻轻的开启,发送一条消息。我们首先通过调节Enigma三个转轮方向,使它们处于17576个方向中的一个,而转轮的初始方向就密匙,这是我们收发双方事前就预先约定好的秘密。

我们轻轻敲打它富有历史感觉的键盘,加入明文的消息。在Enigma的显示器中,每个被键入的字母都依次闪亮并被记录下来,接着它把加密后的消息转换为密文通过电报传送出去。我们的收信方在接收到密电后,打开手中同样的Enigma。

按照我们的事先约定,把转轮的方向调整到和发信方相同的初始方向上,然依次键入收到的密文,并把闪亮的字母依次记下来,就得到了明文于是加密和解密的过程就是完全一样的——这都是反射器起的作用。不过反射器也并非十全十美的,它所带来的一个副作用就是你输入的每一个字母都永远也不会被加密成它自己本身,因为反射器中每一个字母总是被连到另一个不同的字母伤了。

在Enigma的设计思想理念中,转轮的初始方向决定了整个密文的加密方式。这就造成了一个问题,如果通讯过程中有敌人监听,而且他能够截获到完整的密文,这样他就可以实施破解。但是由于不知道三个转轮的初始方向,他唯一的办法就是不得不一个个方向地试验来找到这个密匙。

此时关键的问题出现了。

17576个初始方向似乎并不是非常大的一个数字,如果试图破译密文的人非常有耐心你,他就可以把转轮调整到某一方向,然后键入密文开头的一段话,再判断一下出现的结果是否是有意义的内容。如果没有意义,那么再转动一下转轮,让它调换到下一个出示方向——如果测试一个方向只需要一分钟,而他一天二十四小时日以继夜地工作,那么在大约两星期后,敌人就能够找遍转轮所有可能的初始方向。此时,如果对手用许多台机器同时破译,那么所需要的时间更会大大缩短。

显然,这种加密的强度显然不够健壮和强大。

当然,你可以让谢尔比乌斯继续增加转轮,但是每加一个转轮只是让初始方向的可能性多了二十六倍而已,而仅仅依靠转轮的增加来增强加密强度,也会让Enigma的体积无限增大,缺乏易用性。此时,谢尔比乌斯相当了一个更加巧妙的办法。

首先谢尔比乌斯把Enigma的三个加密转轮制作成为可方便自由拆卸的形式,这样能够让使用者自己DIY调整Enigma转轮的组合方式,这样一来初始方向的可能性变成了原来的六倍。

假设三个转轮的编号为1、2、3,那么它们可以被放成123-132-213-231-312-321六种不同位置,当然现在收发消息的双方除了要预先约定转轮自身的初始方向,还要约定好这六种排列中的使用一种。

接下来,谢尔比乌斯又在Enigma的键盘和第一个转轮之间增加了一个连接板。这块连接板能够让使用者用一根信号线将某一个字母和另外一个字母任意连接,这样这个字母的信号在进入转轮之前就会转变为另一个字母的信号。这种连线最多可以有六根甚至更多,当然连接板上的连线状况也是收发信息的双方需要预先约定的。

于是转轮自身的初始方向,转轮之间的相互位置,以及连接板连线的状况就组成了所有可能的密匙,好的,现在让我们来算一算做了这样改动的Enigma一共到底有多少种组合加密可能性哪?

三个转轮不同的方向组成了26*26*26=17576种不同可能性;

三个转轮间不同的相对位置为6种可能性;

连接板上两两交换6对字母的可能性数目非常巨大,有 100391791500种;

于是一共有17576*6*100391791500,大约为10000000000000000,即一亿亿种可能性。

如果双方都有密匙,那么收发密文与加密解密很容易。但是对于不知道密匙的破解者来说,在这巨大的可能性面前,想通过逐一尝试来找到密匙的方法是没有任何可行性的。

既然连接板如此重要,那么为什么谢尔比乌斯还要兴师动众的为Enigma设计转轮之类的东西呢?原因在于连接板本身其实就是一个简单替换密码系统,在整个加密过程中,连接是固定的,所以单使用它是十分容易用频率分析法来破译的。

转轮系统虽然提供的可能性不多,但是在加密过程中它们不停地转动,使整个系统变成了复式替换系统,频率分析法对它再也无能为力,与此同时,连接板却使得可能性数目大大增加,使得暴力破解的方法成为永远的不可能。

强大的Enigma让德国军方很快的爱上了它,他们几乎对于Enigma的加密信心显得无比十足。而Enigma的强悍加密方式在当时而言,也的确是困扰盟军的巨大障碍,面对一个个通过Enigma相互联系的德国海狼U型潜艇们,面对如此高强度但造价却低廉的Enigma,盟军第一次开始品尝到加密的噩梦。

而Enigma也成为了战争史上最成功的信息加密之王。

但它是真的是不可能被破解的吗?

……待续……

黑客编年史 之加密之王Enigma英格玛 - 苗得雨 - 苗得雨:网事争锋

 

黑客编年史 之加密之王Enigma英格玛 - 苗得雨 - 苗得雨:网事争锋

 

黑客编年史 之加密之王Enigma英格玛 - 苗得雨 - 苗得雨:网事争锋

 

黑客编年史 之加密之王Enigma英格玛 - 苗得雨 - 苗得雨:网事争锋

 

黑客编年史 之加密之王Enigma英格玛 - 苗得雨 - 苗得雨:网事争锋

 

黑客编年史 之加密之王Enigma英格玛 - 苗得雨 - 苗得雨:网事争锋

 

黑客编年史 之加密之王Enigma英格玛 - 苗得雨 - 苗得雨:网事争锋

 

黑客编年史 之加密之王Enigma英格玛 - 苗得雨 - 苗得雨:网事争锋

 

黑客编年史 之加密之王Enigma英格玛 - 苗得雨 - 苗得雨:网事争锋

  

资料:Enigma发展史

1926年,民族仇恨绝不比丘吉尔先生弱的德国海军、首当其冲吃了英国海军部“第40号房间”大亏的德国海军,率先决定采购Enigma的海军型——Enigma Funkschlüssel C型。

1927年,Enigma-D开发成功;

1927年,Enigma-E开发成功;

1927年,Enigma-F开发成功;

1927年,Enigma-D在英国获得专利;

1928年,Enigma-D被美国军队获取;

1928年,Enigma-G军用型开发成功,德国陆军、空军开始批量采购;

1929年,Enigma-H开发成功;

1930年,Enigma-Ⅰ(这里是罗马数字Ⅰ)军用型开发成功,被德国陆军、空军批量采购;

1930年,Enigma-H在英国申请专利,次年获得专利权;

1931年,Enigma-K开发成功;

1932年,波兰、瑞典先后获得EnigmaK;

1932年,在Enigma-Ⅰ军用型的基础上,Enigma-Ⅱ军用型开发成功,再次被德国陆军、空军采购;

1934年,日本购得Enigma-K;

1934年,Enigma Funkschltissel M(海军型)开发成功;

1935年,西班牙、意大利先后获得Enigma-K;

1936年,在Enigma-Ⅰ军用型的基础上,改制出德国国防军型Enigma(Wehrmacht Enigma);

1937年,日本依靠购来的Enigma-K,参考借鉴后成功研发出大名鼎鼎的紫密;

1937年,德国党卫队开始装备Enigma;

1938年,Enigma MOB-38型开发成功,装备德国陆军、空军;

1938年,Enigma的海军型升级为Enigma Funkschlossel M-2型(即M2型Enigma);

1938年,Enigma商业型(具体型号不详)被德国帝国邮政局采购并装备;

1938年,Enigma商业型(具体型号不详)被德国帝国铁路局采购并装备;

1939年,日本在Enigma-K及紫密的基础上,发展出日本海军型密码机;

1939年,Enigma MOB-39型开发成功,装备德国陆军、空军;

1939年,Enigma的海军型再次升级为Enigma Funkschltissel M-3型(即M3型Enigma);

1939年,开发出德国军事情报署型Enigma(Abwehr Enigma)。

二战爆发

1942年,Enigma的海军型升级为Enigma Funkschltissel M-4型(即M4型Enigma);

1942年,开发出德国一日本海军通用型号Enigma-T(或EnigmaModel T型);

1943年,海军型又升级出M-B型、M-8型;

1945战争结束,甚至到了纳粹德国苟延残喘的1945年,全新开发的M-5型和由M-B型发展而来的M-10型还分别装备了陆海空三军……

参考资料:

D.Kahn,The Codebreakers: The Story of Secret Writing,New York: Macmillan Publishing Co.1967

B.C.W.Hagelin,” The Story of the Hagelin Cryptos ”

Bruce Schneier,《应用密码学——协议、算法与C源程序》

  评论这张
 
阅读(5967)| 评论(1)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017