西西河

主题:【原创】被征服的谜――ENIGMA的故事(篇外之四B):多表替代的六人行 -- 1001n

共:💬5 🌺21 新:
全看分页树展 · 主题
家园 【原创】被征服的谜――ENIGMA的故事(篇外之四B):多表替代的六人行

【原创】被征服的谜――ENIGMA的故事(篇外之四B):多表替代的六人行

这不,Giovanni Battista Porta先生来了。

在跑这个接力的队伍里,比起建筑师、修道院院长、红衣主教随从,Porta先生看上去是最职业的,好歹是个科学家。在上本书出版十年后,他的著作《密写评介》出版了。

Porta先生年轻气盛,锋芒有点毕露,先也是介绍了一下此前的密码发展,之后就开始大声嘲笑那些所谓标准密码是“乡巴佬、妇女和小孩”才用的“猪圈”(pig-pen)密码。而他不猪圈的密码,就是密码学历史上第一次出现的双码替代密表构成的密码,实质上还是多表替代密码。这双码替代密表是张大表,上面满是象形文字,我就不列举了。。。还是说说这之外的工作吧。

在书里,他首先是建议,明文应该故意拼写错一些字,以增加对手破译的难度;也提到了完全不按字母序列排列的密表,可惜,他只是一提,在自己的举例中,用的仍然是规规矩矩的字母顺序式密表。而顺序排列和无序排列,那岂是一个层次上的东西?

比起他在密码编码上的贡献,倒是他在密码分析上的贡献更有意思一些。他首次阐明了“可能字猜译法”,实际上类似于我在前文密码ABC中所提到的第一种方式密文攻击和第二种已知明文攻击的综合体。比如,他说主题已经明确,谈战争的话,那么其中必然有士兵、战斗等词,以此猜解,可以减轻破译的难度。

比起以上不那么太足为训的贡献,他在多表替代的破解方面,倒确实有了接近真相的发现。不多讲了,引用一段他自己的文字:

“……反复出现同样的三连码之间,有五十一个字母,所以我认为密钥出现三次,并正确地断定密钥由十七个字母组成。”

思路完全正确,可惜,没有数学证明,他自己也没利用这个发现。否则,多表替代早就垮台了,又怎么能再撑上三百多年呢。。。可惜啊,不管是瞎打瞎撞,还是蓄谋已久,总归他真是摸对了多表替代的命门;而这个发现无疾而终,又实在让人遗憾。

对多表替代的建立和发展贡献很大的四棒接力,到这里就跑完了。但是,我们还有两个人要介绍一下,这也是本文题目叫六人行的原因――真不是我不会数数――多表替代的完善,也有着他们的不可磨灭的功劳。。。

首先就是Girolamo Cardano先生,另一位就是前文提到过的那位法国外交官Blaise De Vigenère先生。

关于Girolamo Cardano先生,故事还不少。他老人家是意大利的数学和医学教授,最出名的贡献绝对不是什么密码方面的,而是――他竟然是概率论的奠基人!有人也管他叫概率论之爹,但是这回,很多人不承认。。。算个野爹吧,总之,他写出了世界上第一篇真正的概率论论文。。。

拉回到多表替代,Girolamo Cardano先生最大的贡献在于,他认为,何必设置什么密钥字母呢,每个明文字母本身不就可以作为密钥字母么!比如刚才的TNND,把T按照T对应的密表加密,N、N、D也照此办理,不就完了么?用他这个思路构造的密钥,就叫autokey,也即“自身密钥”。

当然,这只是个粗略的类似。实际上,他的办法要稍微复杂一点。找明文开头里稍微长一点的单词,把每个字母记录下来,就是密钥。例如,TOMORROW WILL BE A RAINING DAY这一句,就拽出TOMORROW这个单词里的八个字母作为密钥。对明文加密的时候,采用分段错位的办法,比如下面这个样子(“|”符号是我加的,为了区别分段错位;顺便说一句,在纯文本写作时,保持字母对齐太困难了,郁闷):

明文 T O M | O R R O W | W I L L | B E | A | R A I N I N G | D A Y

密钥 T O M | T O M O R | T O M O | T O | T | T O M O R R O | T O M

密文我就不编造了。总之,就是按密钥指定的换字表,对明文相应字母进行加密。比如,第一个字母T,就用对应的密钥字母T指代的密表进行加密;第五个字母R,就用对应的密钥字母O指代的密表进行加密,以此类推。

这样,无须专门指定密钥字母,一个单词就够了。本例中,TOMORROW一共八个字母,对应的就是八张换字表。至于把明文中TOMORROW切开加密的目的,也是为了更好地保密,只要约定好,这都不是问题。

不知道大伙从这个加密方法中琢磨出点什么问题来没有?如果没有,那不妨先不急看下文;本来嘛,密码系列不仅是讲科学历史故事,也时不时带点儿脑力锻炼,嘿嘿……

下面揭晓谜底了……要不看答案的话,可还来得及哟:)

Cardano先生的思路很好,可惜,按这种描述,会有两个致命的缺陷:

第一,同样一份密文,能倒推出一份以上的明文。上文里没有给出密文,主要是构造密表太麻烦,而且很容易出错。纯粹思考体操一下,我们不难发现:对同一个密文字母,比如说T,既可能是字母S通过密表S加密而来,也可能是字母W通过密表W加密而来。这样,脱密的时候,如何确定这个T到底是S还是W呢?

而一份密文能脱出两份甚至三份四份明文,这不是要命是什么呢?

第二,更加致命的问题接踵而来。在面对整个密文的第一个字母的时候,收信人和试图破译这封密信的密码分析员完全处于一样的境地。换言之,他们都需要明文的第一个词。一旦有了这个词,后面的密文就势如破竹,想保密也不可能了。

很好的思路并没有带来很好的结果,Cardano先生的自身密钥系统由于先天不足很快遭到了失败,或者换言之,从来就没取得成功。但是他的失败并不代表自身密钥构造的失败,如果有针对性的改良的话,自身密钥并不是完全不可取的。

还记得我们前面提过的第三棒,那个主教身边的小人物Belaso先生么?他倒是提出了一个可以避免以上两个致命问题的自身密钥加密方法。1564年,他在他那本名字起的深得我心的书里的第三版里,提出一个新的加密方法,也就是采用部分自身密钥加密的同时,进行部分顺序推移的办法进行,直到加密完全部明文。这个具体解释起来起来就实在有点长了,干脆略过了吧:)

回到我们的科学顽童Cardano先生身上吧。他还有一个漏格板的发明,以及对于密码坚强程度的理论认识。关于漏格板,以后我们还会涉及到,这里暂时先不提了。

而对于密码坚强程度,过去都没有一个可以量化比较的标准。你说你的密码强,我还说我的密码强呢,――无从比起啊。而Cardano先生是什么人?那可是某些人的概率论之爹啊,他研究的就是这个;也正因此,他提出的比较方法就比较数学一些,简单的说,就是比各种密码体制中的所有变化可能的数量。概括起来,他认为,变化可能越多的密码,越难被破译。

这个办法有没有道理?肯定有一定道理。是不是颠扑不破?同样肯定,不是颠扑不破。等目前这些看上去比较枯燥的密码理论知识介绍完以后,本系列将会相对比较详细地涉及到精彩的美日密码大战。而在那个时候我们就会看到,变化更多的密码如何反而更快更容易地被破解――这当然都是后话,咱现在就是做个广告,呵呵。

但是不管如何,Cardano先生的这个理论确实很有影响力,也很难一下指出他的谬误所在。以至于,后世很多密码学家依然认为,变化更多的密码,安全强度也就越大――呵呵,也很难颠覆这个常识般的认识了。说到底,当我们认识到一定程度正确的真理以后,绝对不要无限扩大,否则,它必然有变成谬误的那一天。

不过扯点闲话说,Cardano先生还是挺有意思的一个人。他老人家为什么会在概率论上有造诣?那绝对不是白来的,那是用在赌场浸泡的时光换来的――在他一生中,有那么四十多年,他天天几乎都在赌博。还年轻的时候,他老人家就认定:

――如果一个人赌博不是为了钱,那么就没有什么能够弥补在赌博中耗去的时间。这些时间本来是可以花在更值得做的事上的,比如学习。

不提别的,虽然我不爱赌博(在论坛上也有点不爱吱声),但是我个人觉得,Cardano先生这辈子真是过的挺爽……

在我们的多表替代六人行中,最后一个出场的就是那个法国外交官Blaise De Vigenère先生。顺便说一句,别被这个De给骗了,他可不是什么贵族,只是指他的祖籍是Vigenère村而已。

1858年,他写了本书,《论密码》。Vigenère先生后来成为多表替代的一个代表性人物绝非偶然,跟这本书大有关系。书中,他描述了两种多表替代的加密方法:

第一种,他取消了Cardano先生设定的一个单词作为全文密钥的特征,而是改用自然全文做密钥。比如 Tomorrow will be a raining day这句明文,他的设置是:双方先约定一个密钥字母,比如K。之后,用K加密明文第一个字母T,再用明文第一个字母T加密明文第二个字母o,用明文第二个字母o加密明文第三个字母m,依次类推(这里忽略大小写的问题,下同);

第二种,更加前进一步。还是以约定的密钥K加密上面那句为例。用K加密明文第一个字母T,比如得到第一个密文字母X。那么,用X加密明文第二个字母o,比如得到L。再用L加密明文第三个字母M,比如得到R。再用R加密第三个明文字母m,依次类推。

其中,第一种方式在后来的机器密码时代也在应用。而第二种,有个也挺要命的缺点,大家也不妨想想是什么,呵呵,点根烟休息一下中……

……时间到。

这个缺点就是,对于试图破译这份密文的人来说,的确是很快乐的――因为所有的密钥都在你眼前,呵呵,整份密文不就是一个个密钥组成的么……

Vigenère先生阐述的这两种办法都被归于Vigenère体制,从这个体制里,又派生出了一些变形密码。到现在,在网上试着搜索一下多表替代,十有六七要提到这个Vigenère密码体制,可见他对多表替代的贡献之大。

当然,他也跟很多科学史上的人一样,死了以后才轮到他出名。三百多年后,这两种密码编码方式又被人重新“发明”出来,才终于又被人想起来。

顺便说一句,现在常说的Vigenère方表,也就是Vigenère tableau,实际上跟Vigenère先生清楚阐述过的机制没什么关系。第一,它用的不是Vigenère先生所设计的自身密钥机制,而只是字母的自然序列;第二,它不是使用不重复的密钥字母,而是反复使用短密钥词里的字母,这个办法实际更象老顽童Cardano先生的招数。

这事情真是奇怪了,明明Vigenère先生阐述的体制就是针对多表替代的缺陷的,结果后世以他的名字流传的方表竟然正是他要竭力改良的靶子――简直莫名其妙。而这个张冠李戴的Vigenère方表破解难度要比真正的Vigenère加密体制容易的多的多,看看它的两个特点就明白,它跟真正的Vigenère加密体制根本不在一个水准上。

而就是这个相对比较烂的方表,三百年后被重新“发明”出来以后,又被猛烈地吹嘘为“不可破译”的,尽管其实真正的密码分析员里,不少人都曾有破掉Vigenère方表的经历。而甚至连Vigenère先生本人,也曾经一针见血地指出,对整个多表替代系统而言,“密钥越长,破译密表就越困难”――那么短的密钥词,能有多高的加密强度?

结果,Vigenère方表被证明不够结实以后,脏水反过来又泼在三个多世纪以前的Vigenère先生身上,诸如“Vigenère体制是种十分低级的加密体制”等等,不一而足。呵呵,历史就是这样,让人无话可说。好在Vigenère先生早就去世了,眼不见心不烦,也好。

多表替代的六人行到这里总算告一段落了。正是以这六个人为代表的密码学爱好者的研究下,西方的密码学水准终于开始遥遥领先了。而多表替代的破解,在本系列的最初曾经提到过,就不再重复了。

附:

中古时代的密码学发展看来不是很受欢迎,呵呵。毕竟,跟ENIGMA比起来,太老的密码时代果然有点历史有余,故事不足。不过我个人觉得,这段历史也是挺有意思的,毕竟这方面的文献不是太多见,大家一起看个热闹也好。而且,这个时代的加密思路其实挺好玩的,而且也挺有启发性的。比如说让我,在没有任何提示的前提下发明一种英文加密方法,我估计用我一辈子也不可能独自研究到多表替代这个高度,呵呵。

前人的智慧拆穿了看,都很简单;但是正是这样简单的智慧一点点的迭加,才终于堆积到了一个我们今天只能仰视的高度――科学史对人的启发中,大概也该有这一条吧,就是:尊重前人的劳动和智慧,用我们今天的创造和劳动,为后人开辟更高的平台。

而科学不也正是这样,在无数人的尽力交接中,走到今天这个样子,走向更加灿烂的未来么?

【原创】被征服的谜――ENIGMA的故事(一):密码的前世

http://www.cchere.net/article/371599

【原创】被征服的谜――ENIGMA的故事(二):ENIGMA横空出世(上)

http://www.cchere.net/article/372331

【原创】被征服的谜――ENIGMA的故事(二):ENIGMA横空出世(下)

http://www.cchere.net/article/372349

【原创】被征服的谜――ENIGMA的故事(三):丘吉尔托起的灿烂星座

http://www.cchere.net/article/374308

【原创】被征服的谜――ENIGMA的故事(四):波兰人的绝地反击(上)

http://www.cchere.net/article/375877

【原创】被征服的谜――ENIGMA的故事(四):波兰人的绝地反击(中上)

http://www.cchere.net/article/377011

【原创】被征服的谜――ENIGMA的故事(四):波兰人的绝地反击(中中)

http://www.cchere.net/article/378141

【原创】被征服的谜――ENIGMA的故事(四):波兰人的绝地反击(中下)

http://www.cchere.net/article/379376

【原创】被征服的谜――ENIGMA的故事(四)(篇外):最年轻的数学家

http://www.cchere.net/article/383181

【原创】被征服的谜――ENIGMA的故事(四):波兰人的绝地反击(下上)

http://www.cchere.net/article/384482

【原创】被征服的谜――ENIGMA的故事(四):波兰人的绝地反击(下中)

http://www.cchere.net/article/386464

【原创】被征服的谜――ENIGMA的故事(四):波兰人的绝地反击(下下)

http://www.cchere.net/article/388743

【原创】被征服的谜――ENIGMA的故事(篇外之二):密码的ABC

http://www.cchere.net/article/395281

【原创】被征服的谜――ENIGMA的故事(篇外之三):老密码,老故事

http://www.cchere.net/article/398801

【原创】被征服的谜――ENIGMA的故事(篇外之四A):多表替代的六人行

http://www.cchere.net/article/401057

元宝推荐:不爱吱声,

本帖一共被 4 帖 引用 (帖内工具实现)
全看分页树展 · 主题


有趣有益,互惠互利;开阔视野,博采众长。
虚拟的网络,真实的人。天南地北客,相逢皆朋友

Copyright © cchere 西西河