概率论 数学让密码学加速进化(替代法密码学)
概率论 数学让密码学加速进化(替代法密码学)
概率论：数学让密码学加速进化
你想过一个问题没有：
是什么因素决定了一个密码能否被破译呢？
对比一下古典密码和现代密码，你就能发现答案了。
古典密码学，加密和解密过程中，最小操作单位都是单个字符或者符号，所以古典密码学的核心就是移位法和替代法。
现代密码学，把研究对象用数来描述，再对数进行运算。不但突破了字母作为最小变化单位的限制，还可以使用更高等的数学工具做运算，因此破译就变得越来越难。
所以，加密时所用的数学工具，决定了一个密码能否被破译。
第二代的移位法和替换法的安全性很好，也比较好用，但到了16世纪，这个局面扭转了。因为概率论的出现，这两种加密法可以破解了。
自此之后，加密与解密的对抗战中，因为数学的应用，解密一方暂时占据优势。
两个破解 第二代加密法 最经典的案例。
一个发生在16世纪的苏格兰女王玛丽一世身上，一个发生在17世纪中后期到18世纪初的法国国王路易十四身上。
玛丽一世女王，她是我听说过的最刚烈的女人。在这门课《密码学人物列传》的模块中，我会专门用一讲详细讲讲她的故事。这节课，我们还是主要围绕密码展开。
27岁时，玛丽一世被自己的姑姑英格兰女王伊丽莎白一世关押了起来，一关18年。到44岁时，监狱里的她和外界反叛军密谋要杀害姑姑，一旦谋杀成功，她自己就能坐上王位。当时的信件都是通过特殊渠道传入监狱，最后由侍女在递送红酒时，藏在瓶塞中带进去。
玛丽一世很聪明，包含暗杀计划的并不是普通的信，而是加密过的。就算不慎落入伊丽莎白一世的手中，也没人看得懂。
其中用到的加密方法，就是替代法。所有的英文字母被类似符文的东西替换，一些常用词也用符号代替。具体的对应方式，你可以参考下面这个图表。
玛丽此后就通过这个特殊渠道和反叛军通信，几个月后，她熟练掌握，写信可以直接用密文，不用一个个字母查对照表了。
不幸的是，这个特殊消息传递的渠道里，竟然隐藏着一个双面间谍，他把情况汇报给了伊丽莎白。在位的女王正愁抓不到把柄，这下终于有机会名正言顺的处死玛丽了。
不过现在还急不得，必须抓到足够硬的证据，而且最好把整个阴谋背后所有的参与者一起除掉，所以伊丽莎白没有打草惊蛇。
此后玛丽和外界的通信，每一封都先经过双面间谍送到密码学校，花1个小时誊写好，然后再密封好，就像从没有被截获过那样，递出皇宫。密码学校的人再拿着誊写好的密文想法破解，最终他们成功了。
破解方法，就叫做“ 频率分析法 ”。这种方法其实在9世纪的阿拉伯就出现了，只是到了16世纪才被欧洲数学家注意到。
下面咱们讲讲它的原理。很简单，英文中字母出现的频率，是不一样的。比如字母e是出现频率最高的，占12.7%；其次是t，9.1%；然后是a，o，i，n等，最少的是z，只占0.1%。
英语中字母频率统计
除了英语，其他语言也有详细统计。
玛丽和外界用密文往来很多，字符总量足够多，全部收集到一起，统计哪个符号出现的比例最高，那个字符大概就是字母e。
当然，有些字母出现的频率极为接近，比如h，r和s，分别是6.09%，5.98%和6.32%。但只要稍微留意字母前后的关联，就可以区分出来。比如：t几乎不可能出现在b，d，g，j，k，m，q这些字母的旁边，h和e经常连在一起，ee一起出现的频率远比aa一起出现高得多等等。
频率分析法的实质，就是大幅降低字母排列组合的可能性。
从前我们假设每个符文都可以是26个字母的任意一个，有多少个替代符号出现，就有26的多少次方种可能。但频率分析法把很多符号的可能性大大降低，有的降低为只有1种可能，有的降低为只有2-3种可能。
这样一来，即便第一步统计各种符号出现的频率时并不完全确定，但只要再根据拼写规律筛选一下，替代符号对应的真实字母就确定了。
在审讯的过程中，尽管玛丽始终没有承认谋反，但证人和密码学专家一起向公众展示了密文和原文，讲解了解密规则，最后玛丽一世还是被砍了头。
这是加密和解密在皇权斗争中最著名的一次应用，解密法大胜。
解密方法公布后，替代法就不再有效。起码对欧洲王室来说，决心要破解的话，一定可以破。
加密一方当然不甘落败，怎么办？
很快就出现了另一种叫做“ 同音替代法 ”的方法。
比如说字母a可以用11，23，41三个数字替代，这三个数字翻译过来都是a。越常用的字母，比如e，就用越多的符号代替它。这种想法的终极目标，就是让每个数字出现的频率都大致相等。频率特征没有了，密码就不容易破解了。
同音替代法
从上面这张同音替代法的表格中可以看到，最常使用的e，替代的字符最多。
不过这种方法的解密法马上也出现了，就是通过字母前后顺序关系来猜。
最典型的例子是，q后面出现的最大可能是u，而q又是一个不常用的字母，有很大概率猜出来。其他字母猜出来的难度大一些，但只要肯花时间，总能破解。
史上最有名的采用同音替代法的密码，是法国国王路易十三、十四时期的“大密码”（Grand Chiffre）。它使用了40多年后，随着拿破仑倒台突然失传。直到1890年才被完整破解，破解方法就是从单词拼读规律入手的。
这套加密法用了587种数字，来表示不同的发音。其中陷阱还很多，比如有些数字只代表字母，不代表发音；很多数字是干扰字符，它们没有意义；还有一些数字既不是发音也不是字符，而是代表删掉前一个字符。
大密码被破解后，很多200年前路易十四的宫廷秘闻才大白于天下。
其中有一段，是法国宫廷传奇“铁面人”的新发现。铁面人的故事在欧洲，就像咱们关心康熙晚年雍正是怎么即位的故事那样。无数小说都以这个为背景，大仲马和伏尔泰都写过。
故事说的是一个犯人从1669年被捕后，一直关押。而且负责关押他的监狱长不论工作怎么调动，总把这个犯人带上，一关就是34年。按说这么重的罪，就让他把牢底坐穿吧。不，给他吃的都是美味，穿的都是华服，还可以弹琴，有医生定期探望，甚至转移监狱时都是高级马车护送。什么都有，只是没自由。
有狱卒看到过这个人在远离其他犯人的地方散步，脸上总带着一个铁面具，没人知道他长什么样。
铁面人到底是谁，有N种猜测，在大密码告破之前，有猜是路易十四同父异母哥哥的，有猜是路易十四亲生父亲的，有猜是英国国王私生子、法国财务大臣、意大利外交官的。之所以有争议，是因为每个说法都有漏洞。
在大密码告破后，又多了一种解释，那就是当时路易十四手下的德布隆德将军（Vivien de Bulonde）。解密后，有一封信是战争部长写给路易十四的，提到立即抓捕德布隆德将军，晚上关进牢房看管，白天可以允许他带着面具在城垛上活动。
这个说法虽然后来也发现了漏洞，但因大密码破解而公布的文件和信件，让法国宫廷内部的历史变得更有据可查。
你想过为什么替代法会被破解吗？是宫廷天才对猜字游戏很擅长，还是双面间谍的勇敢机智？
这些因素当然都有。但最重要的观察视角是——那个年代的数学突飞猛进，终于诞生了“ 概率 ”这种新概念。
今天的人听到“某个字母在一篇文章里出现的概率”这样的表述，当然不会觉得难以理解。但400多年前的人虽然也知道，硬币扔出去，女王头像一面朝上的机率是一半，这样粗浅的概率知识。但他们大都不会用这个视角衡量感兴趣的对象。
其实直到现在，大多数人也没什么机会用这个视角去思考，唯一涉及切身利益的就是买彩票。
而当年概率论之所以诞生，正因为第一个研究概率论的那个数学家卡尔达诺（Girolamo Cardano）是个赌徒，他还是三次方程一般解法的发现者，也是最早使用复数概念的人。世界上第一本概率著作《论赌徒的游戏》，就是他写的。正是这本书写完5年后，玛丽女王被姑姑囚禁了起来。
数学的发展，有两个高峰。一次是公元前500年到公元前300年，那之后一直在下滑，大约在公元500年跌到谷底。另一次高峰是在这1000年之后，大约在玛丽女王时代，才超越古希腊巅峰时期的水平，而且这个高峰现在还没出现最高值。
随着数学水平的提高，不只是密码学，所有使用到数学的应用学科也会跟着变。很多在1500年之前只是旁门左道的事情，逐渐成为独立的行业，或者单独的学科分支。
创文链接：
• 执剑与破壁的永恒之光
• 密码为什么要从俚语加密开始Why do passwords start with slang encryption
作为古典密码学时代加密法发展的巅峰，恩尼格玛机的出现，意味着从此开始，密码学不再依赖纸和笔的运算，使用机械和电子加密的时代正式到来。
第一台恩尼格玛机，是一战刚刚结束的时候由德国发明家雪毕伍斯（Arthur Scherbius）和里特（Richard Ritter）制造出的。
它主要由三部分组成，分别是键盘、编码器和显示板。
1.键盘
这相当于恩尼格玛机的“输入设备”，它与普通打字机相似，用来输入信息的原文。但出于安全考虑，键盘只有26个字母，而没有标点符号。
2.显示板
这相当于恩尼格玛机的“输出设备”，板上显示26个字母，每个字母下面有一个小灯泡，用来显示加密或解密后的字母。
3.编码器
这是恩尼格玛机的核心部分，由一堆可以手工设置的机械部件组成，主要包括了转子、反射器和接线板，通过线路与键盘和显示板相连接，任何地方的调整都会改变加密的结果。
转子一般有3套齿轮，类似于时钟的时针、分针、秒针，位于最右侧的齿轮每转动一圈，中间的齿轮转动一个刻度，每个齿轮有26个刻度，代表26个字母；
反射器固定不动，它与转子的3套齿轮位于同一个轴上，可以使解码过程完全重现编码过程；
接线板一般有6根连接线，将26个字母中的12个两两相连，比如字母A和B相连，那么输入字母A时，显示的就是B。
输入的字母每经过编码器中的一个装置，就会完成一次替换。
通过恩尼格玛机的组成可以看出，它基于的原理仍然是第二代加密法——替代法，只不过由于经过了多套替换，对应的原文与密文之间存在数以亿计种可能，同时也使频率分析法无用武之地。
使用恩尼格玛机完成一次加密，大概要经过9个步骤：
1.设置好三个转子的初始值，并用6根插头电线连好接线板上的6对插口；
2.在键盘上打明文，每打一个字母，该字母信号就会通过相应的电线传到接线板；
3.在接线板上，如果该字母恰好属于6对连接起来的插口中的一对，则字母互换，否则字母不变，通过接线圆环把字母信号传到右面第一个齿轮上；
4.该齿轮通过内部电线的连接方式，对输入的字母进行替换，然后传到中间的转轮，同时自己转运一个刻度；
5.中间的齿轮再对字母进行替换，然后传到左边第一个齿轮；如果这时右边的齿轮恰好从25刻度转到0刻度，则中间齿轮转动一个刻度，否则不转；
6.左边的齿轮再对字母进行替换，然后传给最左边的反射器；如果这时中间的齿轮恰好从25刻度转到0刻度，则左边齿轮转动一个刻度，否则不转；
7.反射器对字母进行替换，然后传回给左边齿轮；
8.字母信号再从左边齿轮、中间齿轮、右边齿轮和接线板依次转回，每经过一次都会进行一次字母替换；
9.最后，信号传到字母板上，使相应字母下面的小灯泡点亮，显示出加密后的字母。
那么，这个加密过程，其安全性能达到什么程度呢？
我们可以看到，在整个加密过程中，一个字母要经过7-9次的替换：被3套齿轮各替换两次，被反射器替换一次，共7次；如果还经过接线板，则再加两次，一共9次。
再来计算一下有多少种替换的可能：
a.3个齿轮的排列位置可以是任意的，所以共有 种排列方式；
b.3个齿轮的排列位置确定后，一共可以有 种初始转动位置；
c.接线板上，从26个字母中任意选取6对字母互换的方式可以有
种
所以，替换的可能数有：
共有1亿亿余种可能。
更为关键的是，如此复杂的替换过程完成由机械完成，加密人员只需要设定好转子的初始位置，连接好接线板，然后像打字员一样正常输入字母就可以，密文随之自动生成。
这也就是恩尼格玛机为何如此受青睐的原因，它达到了安全和效率的完美平衡。
这样强大的加密杀器，究竟能不能被破解呢？
往期文章：
密码那些事儿｜（十三）尴尬的维吉尼亚3.0
密码那些事儿｜（十二）短命的维吉尼亚2.0
密码那些事儿｜（十一）南北战争时的维吉尼亚密码大战
密码那些事儿｜（十）“钥匙”打开维吉尼亚的锁
密码那些事儿｜（九）维吉尼亚登场
密码那些事儿｜（八）玛丽女王被密码改变的人生
密码那些事儿｜（七）以频率之矛，攻移位之盾
密码那些事儿｜（六）中外古时候的移位加密
密码那些事儿｜（五）换个位置，面目全非
密码那些事儿｜（四）隐藏的消息
密码那些事儿｜（三）“风语者”——从未被破解的密码
本人是官方授权会员推广专员，点击 会员专属通道 成为会员，您将会获得钻奖励及诸多权益！
《钻奖励调整公告》
同音替换法就是一种用多个符号代替一个字符（字母，数字或汉字）的加密方法
