主题:【原创】密码传奇(一):4、决战之前,六字幽灵出现了 -- 1001n
呵呵,还是感谢大家关注,让我在这数字游戏和历史故事交缠的写作中,能够痛并快乐着地坚持下去……
至于太傅表示要亲自破密一事,实在是令人感动。。只是,只是现在。。早不用古典密码了。。唉,我总觉得,密码对抗变成计算机和计算机的对抗以后,意思也就不太大了,虽然说操纵计算机的,还是一个个具体的人。。呵呵。。。
棱角九片兄对我一贯的乱扯提出了很高的评价,于是我更加的。。那还是接着扯吧,如何?呵呵
--------------------------------------
――还是把话题拉回ADFGX密码吧,呵呵,不知不觉间,又给扯远了……
而本文的主角,法国29岁的陆军中尉Georges Painvin(因为这时候他是军人,就暂时不叫先生了吧),正坐在屋子里面对着这五个该死的字母发呆。为了明晰起见,我们在这里再次把他看见的那份编号为CHI-110的电文列在下面:
ADXDAXGFXGDAXXGXGDADFFGXDAGAGFFFDXGDDGADFADGAAFFSXDDDXDDGXAXADXFFDDXFAGXGGAGAGFGFFAGXXDDAGGFDAADXFXADFGXDAAXAG
这叫什么鬼玩意儿啊……而作为密码分析的专业人员,Painvin确实比我们强――他一下就想到,能用区区几个字母来替代全部字母,这样的加密肯定是利用了我们上文提到的方表体制。在方表中,不是有一个横坐标和一个纵坐标的概念么?Painvin估计,这A、D、F、G、X五个字母,就是德军方表所使用的横纵坐标。
作为一个能够使用的战地密码,绝对不会仅仅使用一个变形的方表而已;Painvin猜测,德国人大概在乱序方表的基础又做了一次移位。这样,这个ADFGX可确实是够结实的,绝不是那么好对付的。
而Painvin的猜测一点错也没有:ADFGX的发明人,那位德国的Fritz Nebel上校,在构造这个加密方法的时候,正是先采取了乱序方表,再根据密钥进行移位的。
为了更好地理解ADFGX密码,下面,我们索性就把它放上解剖台,用模拟它加密的办法来深入了解一下ADFGX吧。
需要说明的是,除了方表属于1001n临时构造的键盘顺序方表以外,其它的步骤都是标准的ADFGX操作;此外由于y在德语中使用较少,ADFGX方表中是略去y的,正好构成5*5的方表。这样,方表也就是下面这个样子:
A D F G X
A q w e r t
D u i o p a
F s d f g h
G j k l z x
X c v b n m
现在我们假定要编码一句明文,开始我们的加密过程。这明文定什么好呢……算了,就用西西河的名字吧:Chinese Culture Here。按照电文的要求,首先全部变为大写或小写,之后删除空格,整理成这个样子(在这里我选择的是小写):
chineseculturecere
按上面的方表,我们从第一个字母c开始编码:
c对应的横坐标是X,纵坐标是A,于是记录为XA;之后继续编码第二个字母h,按同样的操作可以得到FX。
继续直到编码全部完成,我们可以得到:
原始明文:c h i n e s e c u l t u r e h e r e
对应密文:XA FX DD XG AF FA AF XA DA GF AX DA AG AF FX AF AG AF
连起来就是
XAFXDDXGAFFAAFXADAGFAXDAAGAFFXAFAGAF
――看上去有点战地密码的意思了吧?呵呵,我也觉得满像了。不过,对自己的发明精益求精的Nebel上校觉得还不像,他提出,要再进行一次变换。这次变换的依据,就是我们将要设定的密钥。
这个密钥其实就是随意选择一个从1到n的整数数列,要求只有一个:打乱它。比如,12345678,打乱成63482517。很显然地,这时候n=8。而在ADFGX当年的使用中,这个n一般要取到20左右。
确定我们的密钥为63482517,现在我们要对刚才得到的密文进行第二次加密了;也就是说,对初步密文进行变换操作了。
变换的具体办法是再次设置一个表,方法是:
根据刚才的设置:n=8,那么这个表就设置为8个纵列;
将密文填入这8个纵列里,遇到末尾就另起一行继续填写;
如此循环,直到所有密文填写完毕。
为了更清晰地说明这个过程,现在我们就演练一回吧。
按密钥63482517,准备写一个8个纵列的表,其中每个纵列都以相应的数字开头:
6 3 4 8 2 5 1 7
准备填写初步密文
XAFXDDXGAFFAAFXADAGFAXDAAGAFFXAFAGAF
已经顺序填入前六个字母的样子:
6 3 4 8 2 5 1 7
X A F X D D
在第八个字母填进第8个纵列后,该填写第九个字母时就另起一行,变成这样:
6 3 4 8 2 5 1 7
X A F X D D X G
A
继续,填写了两行零三个字母后,成为这样:
6 3 4 8 2 5 1 7
X A F X D D X G
A F F A A F X A
D A G
如此继续,把全部的密文字母填写完毕以后,可以得到这么个结果:
6 3 4 8 2 5 1 7 -------列的序号
X A F X D D X G ┐
A F F A A F X A │
D A G F A X D A │-----按从左至右,换行时从上至下的顺序填写的密文
A G A F F X A F │
A G A F ┘
到这时候,初步准备工作完毕,可以开始着手进行换位了。
现在我们不再管63482517了,而按自然顺序,也即12345678的顺序,读取每列的字母。
首先让我们读取1这一列的字母:
1
X
X
D
A
并整理成这个样子:
1
XXDA
然后是2,即
2
D
A
A
F
相应地整理好,并接在刚才的1的结果后,成为下面这个样子:
1 2
XXDA DAFF
之后是3……4……5……
直到把所有数字全部读取并整理好,换位的工作就完成了。在本例中,我们会得到下面的结果:
1 2 3 4 5 6 7 8 ----列的序号
XXDA DAAF AFAGG FFGAA DFXX XADAA GAAF XAFFF ----该列的全部字母,从上至下抄录
把读出的这行字母去掉空格连接起来,这就是最终密文了。而把整个替代-变换的过程记录下来,就是下面这个样子的:
明文 c h i n e s e c u l t u r e h e r e
初步密文 XAFXDDXGAFFAAFXADAGFAXDAAGAFFXAFAGAF
最终密文 XXDADAAFAFAGGFFGAADFXXXADAAGAAFXAFFF
这就是西西河经过1001n键盘顺序方表和密钥63482517双重加密,――也就是完全按ADFGX战地密码规则加密得到的结果啊。呵呵,绝对独一份儿啊。。。还是有点酷,不是么?
容易发现,这样加密得到的密文有个特点:由于ADFGX体制采用了双码替代的方法,其密文长度必然是明文的2倍。这与我们前文提到的Playfair加密方法正好相反,它的密文长度只有明文的一半――密码这个大丈夫,果然是妥帖保护,伸缩自如啊。。。
当接收方(而不是截获方)要解码的时候,他只要找出事先约好的方表和密钥,反过来经过两次解密就可以得到明文了。而由于加密的方法是先替代再换位,所以解密的顺序自然应该倒过来:先解决换位,再解决替代。
说起来就这么一句话,但是具体理解起来,还是有点麻烦的。那么就不妨再演示一次,看看当年的德军译电员是怎么解出明文来的:
首先收到密文
XXDADAAFAFAGGFFGAADFXXXADAAGAAFXAFFF
而根据事先约定,已知密钥是63482517,即n=8,意味着发电文方进行换位加密时候用的是8纵列的表。
数一数密文,共有36个字母。用36/8,商为4,余数为4。两个都是4,――真让我郁闷,这不是增加我的解释工作量么――区别起见,下面提到的时候将标注是哪个4:)
这样,接收方就知道:
这8个纵列里,有4(余数)个纵列是全部填满的,有(8-4)=4个纵列是不满的;
而另外的那个4(商)则说明,无论填满和没有填满的纵列,长度至少应该是4;相应地,填满的纵列长度自然应该加1,即4+1=5。
回顾一下刚才的表,也确实是这样的(尽力对齐了,还是不太理想,呵呵):
6 3 4 8 2 5 1 7
长 ┌ X A F X D D X G ┐
列 │ A F F A A F X A │短列长度4
长 │ D A G F A X D A │
度 │ A G A F F X A F ┘
5 └ A G A F└――┘
└――┘ 4个短列
4个长列
根据填写字母的规则(从左至右,到头后折向下一行继续从左到右),解码员可以知道:
这四个长列必然位于表的左边,而四个短列必然位于表的右边。
根据密钥63482517,从刚才的分析可以知道:
排在前面的四个数字属于长列,也就是6、3、4、8列;
之后剩余的四个数字属于短列,也就是2、5、1、7列;
并且,长列长度为5,短列长度为4。
于是,现在可以把密钥中本来已经被打乱的数字顺序,重新整理成按12345678的次序排列了;他就从数字1开始,顺次整理。
因为1位于短列中,长度应该是4,说明第一段密文的长度就是4。这意味着第一段是由4个字母组成的,于是从密文头4个字母处断开,得到:
1
XXDA DAAFAFAGGFFGAADFXXXADAAGAAFXAFFF
之后是2了。2还是个短列,长度是4,于是再断开4个字母,得到
1 2
XXDA DAAF AFAGGFFGAADFXXXADAAGAAFXAFFF
轮到3了。3是长列,长度是5,于是断开5个字母,得到
1 2 3
XXDA DAAF AFAGG FFGAADFXXXADAAGAAFXAFFF
照这个办法,把剩下的4,5,6,7,8全部整理完,就得到
1 2 3 4 5 6 7 8
XXDA DAAF AFAGG FFGAA DFXX XADAA GAAF XAFFF
现在,译电员就可以恢复被换位加密的方表的本来面目了。
这下一步,他要做的事情就是把行恢复成列。按照密钥63482517,把第一个数字,也就是6代表的这五个字母,以纵列的形式写下来:
6
X
A
D
A
A
尔后,轮到63482517中的3了:
6 3
X A
A F
D A
A G
A G
然后是4:
6 3 4
X A F
A F F
D A G
A G A
A G A
按此办法,把63482517全部填写完毕,即得到整个方表:
6 3 4 8 2 5 1 7
X A F X D D X G
A F F A A F X A
D A G F A X D A
A G A F F X A F
A G A F
好,换位加密的解密工作已经完成,而译电员也很及时地忘了那个密钥――它已经没用了。现在,他也不用再一列一列地看,而恢复成一行一行地看了:
X A F X D D X G ---第一行
A F F A A F X A ---第二行
D A G F A X D A ---第三行
A G A F F X A F ---第四行
A G A F ---第五行
这时他的工作就是把这些字母一行行地抄下来,得到
第一行 第二行 第三行 第四行 第五行
XAFXDDXG AFFAAFXA DAGFAXDA AGAFFXAF AGAF
打破行与行的界限,把它们连接在一起,即
XAFXDDXGAFFAAFXADAGFAXDAAGAFFXAFAGAF
使每两个字母构成一组,一组组整理下来就是:
XA FX DD XG AF FA AF XA DA GF AX DA AG AF FX AF AG AF
尔后翻出双方事先约定好的方表,比如这次,就是著名的1001n键盘顺序方表(哈哈,狂笑三到五声后突然收住:是不是有点傻。。?):
A D F G X
A q w e r t
D u i o p a
F s d f g h
G j k l z x
X c v b n m
根据刚才整理出来的字母两两成组的结果
XA FX DD XG AF FA AF XA DA GF AX DA AG AF FX AF AG AF
以第一个字母为横坐标,第二个字母为纵坐标,一个个查找到对应的字母,很快就能得到
chineseculturehere
成了,这不就是我们要的明文么?至于大写和句读之空格这样的小问题,等到给领导看的时候,再改再加也不迟吧:)
纵观整个过程,加密就象是老师出考卷设计试题,而解密就象学生回答问题:他们所用的思路完全是互逆的,每一步都是可以倒推回去的。也正因为它们互逆同时又是可逆的,倒推解密才有了可能性。
在这里不难看出,ADFGX与ENIGMA加密的区别:ADFGX是一条胡同走到黑,直到有人把它沿原路拽回来;而ENIGMA则是走着走着就拐了个弯,自己默默又绕回来了――而按常理来看,显然ADFGX这种互逆并可逆的加密解密方式,从感觉上更接近“加”和“解”的字面意思。
正是从这个角度考虑,前文才会称ENIGMA的加密解密同相性为“匪夷所思”――即便从字面上理解,都得费点儿劲,呵呵。
从道理上说,本来ADFGX的加密和解密既然是可逆的,似乎用不着罗嗦这么多,一步步再解释解密的具体过程。但是我个人看法,了解这个解密过程还是有必要的,因为这对理解即将介绍的Painvin破解过程有着很大的帮助――实际上,如果不罗列这个解密过程,而直接介绍Painvin的破解,很可能是我说也说不明白,大伙也跟着云山雾罩着似懂非懂,那就罪莫大焉了。
要强调的一点是,译电员的整个解密过程还是很流畅的,而流畅的先决条件有二:
有加密用的方表;
有换位用的密钥。
Painvin也要解密,可是这两个先决条件他一个都不具备。译电员和Painvin干的活虽然类似,但是水准之别真是高低立判――试试看,只用上面给出的密文,而不告诉你用来加密的方表的构成,也不告诉你密钥,甚至连密钥的位数都不告诉你――大家还能从那一大堆的ADFGX里面读出西西河来么……或许真有牛人能?反正我是死也读不出来,呵呵。。。
而Painvin能看到的,只有这么一串串让人发疯的密文……而整个法军,都在等待他从这些幽灵般的字母串里读出德国人的秘密来……
这还没完,更让Painvin搓火的是,ADFGX本身还是变化的。。。
事实上,ADFGX的发明人,德国的Nebel上校并不觉得这个加密就够保险了;谨慎的他曾经提出:替换-换位之后形成的密文,应该再换位一次,才能作为最后的密文发出去。
而德国无线电和密码机关人员认为,这还不行?够结实啦,除非上帝本人来,没人破的了的――何况,作为战地密码,再往复杂里搞不仅容易出错,也白白增加加密和解密的时间;而在战场上,什么比时间更重要呢?――于是,这个给敌军找麻烦的主意被否决了。
――如果这些人当时就知道,增加一道加密工序的这个小麻烦,可以让他们在多大程度上避免更致命的大麻烦,至少能多多少少拖延一下敌人的破译速度,进而改变这场战争的结局的话――我猜他们真的会宁愿要求再加一百次密,也不会再那么肯定地轻信自己的判断了……
不过说起来,他们也不全是白痴。前文提过,最保险的加密方式就是一文一密,不重复使用密钥:从理论上,这样的密文是不可能被破掉的。
扯远点儿说,比如,经过某种加密的映射机制,我肯定能把一本新华字典映射成红楼梦的前五章(主要是红楼梦太长了,呵呵,只好粗略估计着选了五章)。也就是说,新华字典是明文,红楼梦是密文。
这绝对不是不可能的:我可以设置一个密本,把新华字典连汉字带拼音带数字,通通一段段地指定为红楼梦章节中的相关内容――呵呵,虽然有点耍赖,但确实是可以做到的。而现在,拿到这本红楼梦的人里,谁能知道它其实是本字典啊……?
而这样的手段还是不能多用,用多了,在统计分析的照妖镜下一样要露馅――所以,最好的办法就是只用一次,之后就扔了那本新华字典。这样,破译人员面对文笔优美的红楼梦,也只有干瞪眼;纵使是天篷元帅携嫦娥姐姐一起下凡,也绝对不可能破译――除非他们拿到了密本,也就是替换的规则。
可在实战中,一文一密那是不可能做到的。不要说一文一密,就两文一密,三文一密……也是做不到的。简单想想就明白了:如果每天有1000份密电,那么一年就是365000份密电(忽略闰年。。。)。而为这些数量的密电编写N文一密的密码,如果N不是非常大的话,完全是个不可能完成的任务――即便十文一密,也要编出三万多套密码来――想都别想,这东西不要说在战地,就是在政府机关舒舒服服的办公室里,都是没有可用性的――除非使用机器密码,那就完全是另一回事了。
所以,只有勤快点儿,经常更换密钥和密本了。而德国的密码部门在这个方面,多少弥补了他们轻率判断的错误:他们规定,必须经常更换ADFGX所用的方表,和那一串数字密钥。
这个“经常”,他们规定的是――每天。
――现在看来,这应该是古典密码时代,对密码使用的最最起码的要求了――后文就要说到,这么初级的常识,居然又因为轻信密码的“不可破译”,而再次被试图偷懒的德国人违反了!
唉,德国人啊德国人。。。又把自己的好东西葬送了――说实在的,如果不是Painvin过人的聪颖,这个ADFGX密码机制其实还是不错的。。。
虽然这样,很酷的ADFGX还是有个缺点,不知道大家看出来没有。那就是,在表示数字的时候,ADFGX机制先天不足:
例如,电文是(按英语来举例,现编的,因为实在是不懂德文)
371soldierwerekilled
而因为ADFGX里没有数字,于是就只有变成文本形式的数字再发出,就是下面这个样子:
threehundredandseventyonesoldierswerekilled
电文明显变长了,但是信息量并没有跟着增加,实际上是自己给自己找麻烦。而在战场上,数字不仅用来表示时间、部队的番号、兵力、弹药给养、伤亡情况……等等,很多时候还直接以代号的形式表示阵地、高级指挥人员、作战计划名称……等等。
总之一句话,把战场上常常要用到的数字完全用文本方式表示,的确是既不方便又不直观,并且增加了出错的概率。举个中文的例子,大概能让我们体会到这一点:
进攻三二六点八高地的三十七军一○九师三二六团现伤亡二百三十七人
或
进攻326.8高地的37军109师326团现伤亡237人
哪种看上去更清晰一些,应该是没有争议的;至少我个人看到中文形式的数字时,往往错觉般地无法直接感受到它的大小,特别是一堆中文数字摞在一起的时候――何况,在西方文字中,用文本方式表示数字比中文还要麻烦;如上文所举的例子里,你是喜欢three hundred and seventy one,还是371?
德国人很快注意到了这个问题,并且迅速地予以修正。在ADFGX使用将近3个月的1918年6月1日,德军启用了升级版的ADFGX,也就是ADFGVX。
顺便说一句:今天,可是著名的ADFGVX密码在实战中启用87周年的纪念日哟――虽然我又仔细想了想,除了对我这篇文章,也着实没看出有什么好纪念的。。。
从ADFGVX的名字就可以看出,现在的密文又多了一个字母,也就是V。粗粗看去,似乎没什么大不了,不就是又多了个字母么?而实际上,这个新添上去的V字,可颇是不寻常。。。
从迷信一点的角度讲,德军选择这个V字,似乎是为了胜利――就在当天,又一次大规模的攻势发动了;从发报的角度讲,字母V的摩尔斯电码为_...,好发好认。
这里顺便说一下,之所以选择26个字母里的A、D、F、G、X,也有这个原因。这五个字母的摩尔斯电码如下:
A ._ D _... F .._. G _ _. X _.._
都是一些无论在发电还是在接电的时候,都不容易出错的字母。这一点非常重要:在战火纷飞的环境里,密码操作员的精神是高度紧张的,这时候如果事先考虑的不够周到,在设计密码的时候,忽略了战地这个最重要的干扰因素,那么应用时出错的几率必将大大增加。这么看起来,如何设计这个战地密码,其实也真是一门学问:)
――而增添这个V字更深层更重要的原因是,原来的方表只有A、D、F、G、X五个字母,只能构成5*5的方表;现在则是A、D、F、G、V、X六个字母,可以构成6*6的方表。
比起ADFGX的老机制来说,ADFGVX方表扩大了(6*6)-(5*5)=36-25=11个格子,换言之,方表里可以多容纳11个字符了。在ADFGX中不是省略了字母y么?现在y可以加进去了。这样,还多10个字符的空位。。。
――不用我多说大家也能看出,这10个位置正好可以用来容纳1、2、3、4、5、6、7、8、9、0这十个数字。于是,看上去只是名字长了一位的ADFGVX,现在就可以直接表达数字了。
稍微深入分析一下我们不难看出,这些数字由于是被填进方表中的,在使用的时候每个数字都和别的字母一样,要被横纵两个坐标上的字母替换加密――换言之,现在电文中的ADFGVX们不仅可能是文本,还可能是阿拉伯数字。。。
――这一招,的确设置的好!如此一来,试图根据语言特性频率分析来对付ADFGVX,难度无疑就大大上升了。毕竟,数字不象语言,几乎就没有什么诸如the、army之类的固定搭配。即便有点儿如部队番号之类的固定组合,也会被迅速淹没在大量的其它数字里。。。
毫无疑问,ADFGVX的安全强度要好于ADFGX。这也是德军新攻势前更换新密码的最重要原因:为了击溃法军,形成更大的优势以改变战局,一切的小心都不是多余的。他们相信,无论是法国人,还是英国人,甚至已经登陆欧洲的美国人,都不能很快破译ADFGX/ADFGVX密码。
而在ADFGX还没被确认已遭破译的前提下,他们又主动更换了新的也是更强大的ADFGVX――德国人对这一攻势的期望之高可见一斑!
――只要协约国的军人们不能迅速破译这个密码,那么之后即便破译了,他们也败局已定――没用了,到了那个时候,什么都没用了!
这一点,德国人清楚的很。
这一点,法国人也清楚的很。
这一点,Painvin也清楚的很。
――而法军中尉Painvin的成名一战,也正在于此!
【原创】密码传奇(一):1、西线屠刀背后的五字幽灵
http://www.cchere.net/article/404818
【原创】密码传奇(一):2、血河洗刷的人间地狱
http://www.cchere.net/article/405853
【原创】密码传奇(一):3、生命换来的密码学教训
http://www.cchere.net/article/407084
本帖一共被 2 帖 引用 (帖内工具实现)
- 相关回复 上下关系8
【原创】密码传奇(一):4、决战之前,六字幽灵出现了
越看头越大 西河泳者 字0 2005-06-26 11:52:16
😄篇篇精品,篇篇送花 landlord 字0 2005-06-01 06:37:01
看密码故事,自己也紧张 本因坊幻庵 字90 2005-06-01 00:18:43
😉一看解密,就想到了《暗算》一书,呵呵! lily 字0 2005-05-31 23:55:51
说真的,那书不咋样。 葡萄干 字66 2005-06-01 00:10:09
说实在的,《暗算》的密码学跟徐迟的哥德巴赫猜想水平相当, 抱朴仙人 字190 2005-06-01 04:04:44
《在秘密帷幕背后―美国黑屋的特种行动》这书相当好 葡萄干 字18 2005-06-01 04:31:56