…… “古哥古点”强烈建议您点击上方音频来收听节目 ……
《隐蔽周期和频率平移》
电报的出现彻底改变了人类的通讯方式，这是人类第一次摆脱实物化信息的传递方式，而是通过信息编码和物理状态的受控迁移进行信息递送。电报的日渐普及带来了一个直接而影响深远的后果就是密码的使用更加广泛和普遍。此同时人们对密码安全性的关注和要求也越来越高。好在当时的人们已经掌握了维热纳尔密码，一种多字母表替换的编码方法，这种密码曾经被认为是无法破解的，所以用户们可以放心大胆的使用电报而不必担心电报内容被截获。这种情况延续了一段时间，直到一个牛人的出现，他就是查尔斯·巴比奇。
查尔斯·巴比奇
巴比奇生于1791年的英格兰德文郡，那一年法国大革命正达到最高潮。巴比奇多才多艺，在许多领域都做出了杰出贡献，其综合才能几乎堪比达芬奇。巴比奇的家境优越，父亲是个银行家，他年轻时因为没有经过父亲同意便私自结婚，被剥夺了财产继承权，尽管如此，他还是得到了一大笔钱，足够他过上衣食不愁的生活，这就使得他可以专心于自己喜爱的科学研究。
我们可以来看看他都做过什么事。巴比奇24岁就成为英国皇家学会会员，获得过文学硕士学位，参与创建了剑桥天文学会，担任过剑桥大学卢卡斯数学教授。他做出了世界上第一张死亡概率统计表，至今仍在寿险行业使用；他设计了世界上首个邮政单一计价体系，并沿用至今；他第一个认识到树木年轮的宽窄反映了历史气候；他创造性地把运筹学引入到企业管理，率先提出了对工人进行分红奖励，这个理念早费雷德里克·泰勒75年。当然，他最重要的成就还是设计出了世界上首台解析机的完整结构，或者说他设计出了计算机最早的雏形。尽管他因为自己的暴躁脾气，没有得到政府的持续资助，而最终功亏一篑未能制造出这台命名为“差分机二号”的计算机器。但是他在1871年临去世前曾写道：“如果我能够多活几年，解析机将会问世，而它的成果将会传遍整个世界。”从后来计算机的巨大的影响力来看，这话一点都没有说错。
巴比奇对此也曾抱怨过英国政府，说英国人只会挑剔和否定，他气愤的说“如果你告诉英国人可以设计一台削土豆的机器，他们会说不可能；如果你在他们面前已经用这台机器切削土豆皮，他们又会说这个机器没有用，因为它不会削菠萝。”不过客观的讲，我们并不能谴责英国政府没有远见，事实上他们已经为解析机的研究投入了17470英镑，当时的这些钱足够建造两艘大型军舰。当然，我们今天的故事并不是介绍解析机，而是要说明巴比奇在密码学上的贡献，正是他攻克了看似牢不可破的维热纳尔密码系统，将保密与解密的竞赛推向了新的高潮。可以说，这是自九世纪阿拉伯数学家建立频率分析法之后又一次重大的理论突破。
参照巴比奇设计制作的差分机
巴比奇从小就对密码破译非常感兴趣，并积累了许多知识，长大后他在密码界的名气越来越大，曾经在1854年和一位律师合作通过破解密码侦破了一起大案。当时，大多数密码专家已经放弃了破解维热纳尔密码的念头，因为实在太困难了。但巴比奇却因为一次偶然的事件，走上了破解之路。那时有一位名叫赛瓦特（真的叫赛瓦特，不是赛西施、赛貂蝉那样的赛瓦特）的牙医声称自己发明了一套全新的密码系统，想申请专利。经过巴比奇检验，发现医生的这套密码其实就是维热纳尔系统，算不上什么新发明。赛瓦特很生气，他说巴比奇是因为破解不了这套密码，才故意把该系统说成是在几个世纪前已经问世了。巴比奇的暴脾气哪能受得了这种嘲弄，他决定一定要破解维热纳尔密码。
破解密码必须有某种信息的抓手，就如同以前的密码系统会留下频率的印记一样。但是现在维热纳尔系统似乎是一面光滑的峭壁，找不到任何可供分析的痕迹，所有的特征都被消除掉了。但事实真的是这样吗？
巴比奇开始仔细思考多字母表替换加密的原理。维热纳尔的系统看似复杂，但说穿了也很简单，不过是把原先全体明文字母都只使用一套字母表进行加密的方式，强化成为了全体明文字母分成若干组后分别按照不同的字母表进行加密。如果能够知道密码系统具体用的是哪几个字母表，那问题就简单了，只要把密文按组拆开，那每一组内等于都是一种传统的单字母表替换加密的结果。这样便可以用老方法解密了。
维热纳尔密码轮
可问题是，系统使用哪几套字母表是由密钥决定的，而密钥是不可能提前知道的。假设现在使用的密钥是一个四字母的关键词KING，那么明文中的字母就会依照先后次序，分别挑选K行、I行、N行、G行的字母表进行加密，之后再重复使用这四个字母表。注意到了吗？这里出现了重复，以后我们会反复强调一个观念，密码的所有破绽全都来自于重复。尽管KING这个关键词破译者不可能事先知道，但是这种四套字母表周而复始的周期性有没有可能产生信息痕迹呢？这个思考点就是巴比奇的过人之处，他首先意识到替换字母表的循环有可能留下信息的抓手。
以英文单词The为例，如果明文某处有这个单词，且加密其首字母T的时候正好挑选到K行字母表，则THE加密的结果就是DPR；如果THE的首字母正好赶上了I行字母表，则THE加密后变为BUK；如果T碰到了N行，结果是GNO；如果碰上了G行，结果是ZRM。这说明在使用4字母关键词的密钥时，一个单词经过维热纳尔系统加密后，理论上最多能出现四种不同的结果。由于定冠词THE常常被大量的使用，其位置分布比较随机，因此在大多数场合下，四种加密结果在密文中应该都会出现，而且每种结果很有可能出现不止一次。一旦存在重复，比如密文中出现了两个BUK，那么极有可能意味着明文中存在两个THE。当然也有一种例外情况，就是其他的字母在加密后碰巧形成了BUK组合，不过这样的情形出现概率比第一种情况要小很多。
如果明文中是有两个THE，且都加密成了BUK，那么这两个THE在明文的位置上，一定是相差4个或者4的整数倍个字母。因为只有如此，两个THE才会挑选到同一行的替换字母表，形成相同的加密结果。而由于明文和密文的位置是一一对应的，既然明文中两个THE差4的整数倍，那密文中两个BUK肯定也差4的整数倍。现在把这个思路反过来，如果我们扫描一下密文中重复出现的BUK字符串，就很可能会发现大部分重复出现的BUK之间都相距4个字母的整数倍。因为这些重复的BUK大部分是由于重复的THE加密产生的，这个结果同样适用于DPR、GNO、ZRM这几个字符串。
维热纳尔加密程序
以上的分析不仅对THE，对其他的单词一样适用。只要一个词汇在明文中重复出现，并间隔4的倍数个字母，那么密文中一定也会出现重复的字符串；反过来，如果密文中出现了重复字符串，那么极有可能是由明文中的单词重复造成的，且重复的明文单词之间一定相隔4或4的倍数个字母，故而密文中重复的字符串也相隔4或者4的倍数个字母。至此我们得到一个关键结论，如果我们检索密文寻找重复字符串，那么大部分的重复字符串之间都会相隔4或者4的倍数个字母。要是大部分重复的字符串相隔是5或者5的倍数，这只能说明加密系统使用的密钥长度是5。由此我们找到了一个方法可以捕捉周期信息，猜出关键词的长度，那就是寻找重复字符串。
这一步非常重要，一旦知道了密钥的长度，比如说是4，那我们就会明白密文的第1，第5，第9...这些字母都是采用密钥所决定的第一个替换字母表加密的，第2，第6，第10...这些字母都是采用密钥决定的第二个字母表加密的。以此类推，我们就可以把整体密文区分成四组，每组各自使用一个密钥字母所决定的替换字母表。这样一来，一个多字母混合加密的密文就被切分成了四组单字母加密的密文。
对密文重复字符串的查找和距离计算可以估计密钥长度。上面的例子中密钥长度应为5。
接下来要确定的问题是这四组密文各自采用了哪一行的替换字母表，也就是确定出密钥是什么？这步就简单多了。不同的凯撒字母表之间，其统计频率的形状完全是一样的，所不同的只是这个形状的横向位置。随着凯撒表行号的向下，这个图形也会逐渐先后移动，因此只要用一个标准的字母表的直方图和上述各分组直方图去进行对比，确定出图形的位移量就能推断出每一组加密文所用是哪一行的凯撒表。至此原先复杂的多字母表密码破解问题就变成了几组简单的单字母表密码破解问题，密码至此得到解决。
简单的总结一下这个神奇的破解过程，巴比奇敏锐的觉察到维热纳尔密码系统循环使用的关键词有可能留下用于破解的抓手，而这种痕迹就隐藏在密文当中重复出现的字符串上。通过检测密文中大量的重复字符串之间的间距，找到那个出现频率最高，并且大部分间距都是其整数倍的间距数值，这就是密钥长度。根据这个长度，将密文分组，保证每组密文都是一个单字母替换表的加密结果。通过比对每组频率图和标准频率图的图形，找出位移量，就确定了该组密文使用的字母表的行号。之后再用传统方法进行破解，整个密码便被完全破译。
频率对比寻找平移量
巴比奇提出的这个密码破解方法非常重要也非常有名，但有趣的是，它最后却被命名为卡西斯基测试法。因为巴比奇虽然早在1854年就提出了这种破译手段，但是他却一直没有发表这项成果，只是记录在自己的笔记当中。结果大约在十年后，普鲁士军队的退役军官德里克·威廉·卡西斯基（FriedrichKasiski）独立的创造出了这种破译方法，因此卡西斯基的名字就成为了这套方法的冠名。至于巴比奇为什么不发表自己的成果，很有可能的一个原因是当时的英国正在和俄国进行克里米亚战争，为了对俄国人封锁消息，不让对方知道英国已经能够破解维热纳尔密码，英国军方不允许巴比奇公布破解消息。这种可能性是很大的，因为到了后来的一战和二战，英国人一再的上演着这种隐瞒的好戏。
卡西斯基和巴比奇的出色贡献，让密码竞争中一度领先的加密方又失去了优势，破译者再次掌握了主动。那么加密者又该如何应对来提升自己的防护能力呢？密码之争开始从难度走向速度。
喜欢文章，就给个好看哦
原文始发于微信公众号（商密君）：密码传奇（三）计算机之父出手破解超强密码
- 左青龙
- 微信扫一扫
-
- 右白虎
- 微信扫一扫
-
评论