主题：【原创】被征服的谜――ENIGMA的故事（篇外之四A）：多表替代的六人行 -- 1001n
家园 【原创】被征服的谜――ENIGMA的故事（篇外之四A）：多表替代的六人行 【原创】被征服的谜――ENIGMA的故事（篇外之四A）：多表替代的六人行
在提到这位总统先生以前，我们还是继续回顾一下密码编码的进展吧。如前文提到的那样，虽然密码编码更早地肇始于几个文明古国，但是这期间，现代意义上的西方诸国也没有闲着。事实上，他们在漫长的时期里所研究的结果，正是今日他们在密码学研究上一路领先的坚实基础。
黄沙吹尽始到金。在这几十个世纪林林总总的发明中，真正能够对后世的密码学发展产生重大影响的，其实也不过就是几种。具体来说，其实也就是两种。
前文提到过，希腊人Polybius发明了方表法。简单的说，Polybius方表更象一个填满字母的九宫格（当然实际使用时，一般都不止九宫，也可以变形成为长方形等等），有点象纵横填字谜那样的东西。直到第一次世界大战的时候，这种方表的衍生后代还在用，并且还直接导致了重大的结果――具体情况，我们后文再介绍吧：）
而下文将要涉及的方表，只是把一行行字母序列按一定规则排列以后形成的一个方阵形状的字母集合，比如说，26*26的方阵，看上去象个方形的表，而已。
现在，我们就说说这第二种加密方法。这个方法影响之大，应用之广泛，应该说完成了现代意义上的密码编码学的奠基工作。说起来，不仅ENIGMA算是这个方法的嫡系子孙，据说――仅仅是据说――就连编码学高度进化的现代，依然有很多国家在应用它的原理，对信息进行各种高级加密，比如，外交系统的密码系统。
具体介绍这个方法以前，我们还是来看看它的发端吧。
1404年，意大利佛罗伦萨诞生了一个小男孩，他就是日后的Leon Battista Alberti先生（又是这么个介绍套路，下次我一定换……）。简要起见，我们直接把目光对准他62岁时发表的一篇论文吧。顺便说一句，他的职业是个建筑师，而这离我们的话题太远了……但是说到大器晚成，六十多岁的建筑师还能对密码学的发展有所贡献，怕也是很有启发意义的吧……
在这篇虽然不长，但是却是有据可查的西方第一篇密码学论文里，Alberti先生回顾了以前各种加密方法，诸如单字替代的各种变形、隐写法之类。之后笔锋一转，隆重推出了他自己“至高无上”的加密法，声称这是不可能被破译的。现在，就让我们看看这种“至高无上”的加密法，到底有些什么新东西吧。
“我用铜板做了两个圆盘。大的一个称为定盘，小的一个称为动盘。……每个圆盘的圆周分为二十四个等分，称为单元。”
为了更好地理解他的发明，设想一个圆盘，之后：
1、以盘的圆心为准，往外扩散着画一个同心圆C；
2、于是，C包围起来的区域就是小盘Y，C之外的圆盘区域就是大盘Z；
3、把Y和Z的圆心钉在一起，让Y可以转动，Z设置为静止的；
3、从圆心向外还辐射出很多径向直线，把Y和Z割成若干格；
4、把每一格里都顺序填上字母。
这就构成了他发明的这个密码圆盘系统。
根据这个构造我们不难得知，Y上的每个字母所在的格子，都对应着Z盘的一个字母所在的格子。
比较一下恺撒换字表，我们可以发现：如果把所有字母都写成一行，那么恺撒换字表实际就是把这行字向后错动了N个字符。打个比方就是：好像两把一样长的尺子A和B并排放在一起，把B沿着A的直边向后错动N厘米，再把B末尾处相对A长出的N厘米锯掉，加在B的开头一样。
这样的直线形式的加密和圆盘式的加密有什么区别呢？说起来，都是把明文的字母进行替换。但是，直线形式的替换中，尺子A和B一旦确定相互位置，就不再变化了。当然从理论上讲，A和B可以不断改变相对位置的，但是，恺撒密码没有这个特征：一次设定A和B的相对位置以后，就不再有任何变化了。
而Alberti圆盘呢？从刚才的叙述中，我们很自然地就会注意到：它是会转的。
――而密码学中登堂入室的那扇沉重大门，就被这个“转”字给一脚给踹开了！
以前分析ENIGMA的原理的时候，曾经反复提到转轮的概念。非常类似的，Alberti圆盘也是加密若干个字母（通常是三个字母）之后，就变换一次字母对应关系，办法就是把Y相对Z旋转一下。看起来简单的很，似乎没有特别大不了的。但是，它至少产生了两个结果：
一，多表替代法从此诞生。
二，西方国家因此第一次在密码学发展上占据了制高点。以多表替代法的诞生为标志，西方的密码学水平在这以后不仅再也没有落后过，而且还在它的基础上发力狂奔，直到把其它文明使用的加密手段都远远抛在了脑后。。。
再说回来。这个多表替代到底是个什么意思呢？而Alberti圆盘怎么就成了多表替代呢？
其实说穿了，还真是一点也不复杂。所谓多表替代法，指的就是对同一个字母，用多于一种换字表进行替代的方法。
举例来说，明文中的字母A，按照某种规则，可以对应成密文中的字母F；按照该规则继续进行加密，再碰上字母A时，就可能对应成密文字母K；再次遇到A的时候，也许还会分别对应成M、Q、Z……等等。而考虑到从A到Z的全部字母序列，每次对应出来的密文字母序列也都不一样；这就是说，换字表也都次次不同。于是经过一定的构造，我们可以很容易得到几十张甚至更多的换字表。而这，就是所谓的多表替代。
顺便说一句，这里把换字表用“张”来量度，只是为了和中文的“表”相对应。而一“张”换字表，不妨理解为一个换字序列的集合。
具体到Alberti圆盘这个例子，很容易理解，可以产生的换字表是26张，如果Alberti圆盘真就是简单地把26个字母依次填写进去的话。遗憾的是，Alberti圆盘没这么简单，要不怎么敢自称是“至高无上”的呢。Alberti先生在这里狡猾了一下，而这一狡猾，Alberti圆盘的加密水准也跟着有了质的飞跃――
注意到开始引用Alberti先生本人对圆盘的描述了么？他说的是，分成“二十四”个部分，而不是二十六个部分。换言之，他采用的并不是完整的字母表。实际上，里面的小盘Y，和外面的大盘Z，所采用的字母是不完全一样的。
在Y的24个格子里，他写下了随意排列顺序的小写字母。因为他的字母序列中没有j、u和w，这样，他就写下了23个小写字母。之后，他在还空着的最后一个格子里写上符号“et”，据说意思类似于“&”。这样，Y盘填写完毕。
在Z的24个格子里，他按照字母顺序写下了大写字母，并省略了H、K和Y。这样，24个格子里填写了20个，还有4个格子是空的。
玄机就在这空出来的4个格子里。Alberti先生妙手偶得一般，在这4个格子里不再填写字母，而是填进了数字：1，2，3，和4！
日本有个我个人认为挺好看的动画片，叫棋魂。讲的是一帮小孩子，孜孜不倦地钻研围棋。而其中，他们最期望自己在不断提高以后，能得到一种棋感，使自己在实战中能下出可望而不可即的“神之一手”。
而这1、2、3和4，就是Alberti先生弈出的那石破天惊的“神之一手”！
――Alberti先生用这4个数字构成两位数、三位数和四位数，也就是，从11开始，到4444为止。容易计算出来，这样的组合方式应该有360种。把这360种变化都写在本上，于是就有了密本。
――在准备对明文进行加密时，Alberti先生先跟收文方约定好规则，之后就把明文中完整的某词某句按规则加入密本里数字的各行中。这样抄写下来的初步密文，必然是字母之间夹带着大量的数字。
――拿到这个初步密文后，在大盘，也就是Z盘上，找到初步密文起初字母对应在Y盘上的密文字母，抄好。抄完前三个字母时，按事先约定的规则，转动Y盘，之后继续抄录第四个字母对应在Y盘上的密文字母。如此，每三个字母一次转动，并将所有经过二次加密的字母抄好。
――加密完成。
稍微回味一下他的发明，想想用他的办法形成的密文。利用这个时间，您也喝口水，我去抽根儿烟……
最后就很难不感慨――在十五世纪，这样水准的加密，才真堪称是skytale，天书！
Alberti先生因为在西方做到了三个首先，也就是：
首先阐明密码分析学原理，
首先发明多表替代，
首先发明加表密本（就是刚才那个记录着360组数字组合的密本），
从而当之无愧地成为西方密码学之爹。
顺便说一句，也许某位兄弟会说了，密码学之爹我知道，不过不是你说的这个Alberti先生。我说，那没关系，因为密码学本来就爹多――实情确实如此，另一位密码学之爹将在我们后面的故事里占据一个很重要的位置，现在我们就接着先把这位爹，Alberti先生的故事讲完吧。
Alberti先生的论文有点可惜了，他用的是他的母语，也就是意大利文发表的。这样一搞，能认识的不多，结果就是影响有限。虽然如此，他的工作还是直接影响了几十年后密码学史上挺有名的Argenti叔侄的工作――他们也是意大利人――限于篇幅，这二位我就不提了，咱们拣主要的说。
四百多年过去了，列强们才开始对密本进行加表处理，而且更让Alberti先生郁闷的是――如果他知道的话――那个加表的程度还不如他当年的发明的复杂成熟……
俗话说，罗马不是一天建成的，多表替代法加密能风光几百年，也必然有它的道理，必然有它的改进。按着我们故事的顺序，又一位修道院院长出现了――不务正业的人怎么这么多呢？
德国的Johannes Trithemius院长先生，在1508年也就是他46岁那年，写了本书，里面讲的就是密码学。书分为6卷，第1卷就提到了他的发明Ave Maria密码――看看人家这个命名，真是充满了虔诚啊――万福玛利亚密码，或者福哉玛利亚密码。。。
这个虔诚的密码的核心，就是先准备好384列拉丁词（很多是宗教用语），把它们按某种顺序写好，之后把明文的每个字母都给对应成N长的一个词，用这些词组成密文。
有这么个例子：五个字母的单词abbot（修道院院长），被加密成五个词汇构成的这么个结果：DEUS CLEMENTISSIMUS REGENS AEVUM INFINIVET（愿圣朝永世长存）。
老实说，这是我看了这么久密码资料里，唯一一个让我敬佩得无言以对的例子。。。
――如大家所见，最要命的是，密文居然还是一句很通顺的话，真能气死谁。。。当然，由于是多表替代的方法，两次对字母b加密的结果都不一样。顺便说一句，这样的密文出现在修道院的某张桌子上，谁看见也不会以为是什么密码，如果都很通顺的话――那么保密的目的不也就达到了么，呵呵。
这是第1卷的情况，后面5卷也很类似，给出了大量的排列。具体细节就不说了，要不这个系列的篇幅都用上也描述不完他的虔诚。。。
他最大的贡献就是，在第5卷里，他第一次提到了现代密码学意义上的方表的概念，也就是所谓Trithemius's tableau。而方表是什么？就是把字母序列一行行写好，之后每一行向前（向后）错动一个字母。这里，我给大家简单罗列一个例子：
ABCD……XYZ
ZABC……WXY
YZAB……VWX
XYZA……UVW
……
……
CDEF……ZAB
BCDE……YZA
首尾循环完成，一个方表构造完毕。
因为长度肯定是26，行数也肯定是26，如此写出来，肯定是个方形；这也就是方表的名字来源。这里要说一句，Trithemius先生所用的方表，实际跟刚才所构造的方表不太一样：他的表里只有24个字母，字母J和V是没有的。
Trithemius先生所列出的这个方表，实际每一行都是一个恺撒密表。如果仅仅只是罗列了26个恺撒密表，那么Trithemius先生也实在没什么了不起。但是他高明就高明在，他不是其中某一个表来加密，而是用所有这些密表给信息加密。
具体说就是，第一个明文字母他用第一行密表加密，第二个明文字母就用第二行密表加密。这样，写完24个字母后，他已经换了24张密表；从第25个字母开始，就换第二张方表进行加密――反正方表这东西，他愿意按什么顺序写就按什么顺序写，只要收信人按同样的规矩查找也就是了――直到把这信写完。
比刚才说的西方密码学之爹Alberti先生的工作来说，Trithemius先生显然更强一些。Alberti先生一般每隔三个字母才转动转盘一次，而Trithemius先生显然更加不怕麻烦，每个字母都换一次密表，也不管用光了24个字母以后，再去构造一张有24个密表的方表有多麻烦。
密码学的实践证明，胜利最后是属于不怕麻烦的群众的――多表替代法后来衍生出无数个变种，而方表就是所有这些变种共同的基础；此外，从Trithemius先生开始，逐个字母加密的精细操作终于取代了几个字母一批批加密的粗糙办法，消除了可能给密码分析者以点滴线索的重码现象，成为多表替代加密的主流。
写到这里不禁在想，如果1/3个1/3个字母加密又会如何？想必那更加接近乱码，更能达到迷惑敌人（和自己人）的效果吧。。。？
同时，Trithemius机制也是第一个采用推移序密钥（progressive key）的实例，在可用的密表用完以前，密钥是不会重复的。不重复的密钥正是现代加密起码的要求，当然，Trithemius先生限于环境，他的密表不可能是无限的，即便是非常大量也很难做到。
在这里也交代一下Trithemius先生的后来。他死后一年半，他的这本书才出版，成为密码学历史上的第一本印刷著作（莫非之前都是手抄本？），也正是这个原因，他赢得了崇高的声望。至于原书，我猜各位一看书名也就没兴趣拜读了：
――《多种写法之六卷书：前施潘海姆修道院院长，现维尔茨堡修道院院长Johannes Trithemius著，敬献给马克西米利安皇帝》……
按我个人的观点，去除废话，叫《密码：Johannes Trithemius著》足够了嘛。
第三位对多表替代作出贡献的是个默默无闻的小人物，但仍然是意大利人，Giovan Batista Belaso先生。他曾经是个红衣主教的随从，在上面那本名字狂长的书出版后43年后的1553年，他也出了本书，名字深得我心：《Giovan Batista Belaso先生的密码》。
Belaso先生的贡献看起来最简单：他提出，在明文每个字母的头顶，写下一个密钥字母；之后按这个密钥字母所对应的密表，对这个明文字母进行加密。比如
密钥字母： F H T N
明文字母： T N N D
对明文的T，就用密钥字母F对应的密表进行加密；对N，就用H对应的密表加密；对第二个N，用T对应的密表加密；对D，用N对应的密表加密。
如此一来，Trithemius先生设置的顺序加密的策略也被彻底打破了：每一个字母如何加密，不再取决于它在全文中处于第几个位置，而仅仅靠它头顶上的密钥字母来决定。这样，哪怕密表少点，也够让人摸不着头脑了。此外还有个好处，密钥可以分发给许多人，一旦怀疑密钥失密，换一个就是了――在外交上，大使们就可以把复杂问题简单化了。
这个办法既简单，又适合特定用途，注定是前途光明。结果果然如此，很快就大受欢迎。Belaso先生的发明直接影响了现代密码的复杂体制，也算是奠基人之一了。
这个多表替代法发展到这会儿，已经前赴后继地有了三位先生的努力了。但是男子接力，不管是4*100还是4*400，怎么都得四个人啊――那，跑第四棒的先生在哪里呢？
这不，Giovanni Battista Porta先生来了。
【原创】被征服的谜――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
元宝推荐：不爱吱声,
本帖一共被 5 帖 引用 (帖内工具实现)