e路易过考试题

概率论：数学让密码学加速进化 你想过一个问题没有： 是什么因素决定了一个密码能否被破译呢？ 对比一下古典密码和现代密码，你就能发现答案了。 古典密码学，加密和解密过程中，最小操作单位都是单个字符或者符号，所以古典密码学的核心就是移位法和替代法。 现代密码学，把研究对象用数来描述，再对数进行运算。不但突破了字母作为最小变化单位的限制，还可以使用更高等的数学工具做运算，因此破译就变得越来越难。 所以，加密时所用的数学工具，决定了一个密码能否被破译。 第二代的移位法和替换法的安全性很好，也比较好用，但到了16世纪，这个局面扭转了。因为概率论的出现，这两种加密法可以破解了。 自此之后，加密与解密的对抗战中，因为数学的应用，解密一方暂时占据优势。 两个破解 第二代加密法 最经典的案例。 一个发生在16世纪的苏格兰女王玛丽一世身上，一个发生在17世纪中后期到18世纪初的法国国王路易十四身上。 玛丽一世女王，她是我听说过的最刚烈的女人。在这门课《密码学人物列传》的模块中，我会专门用一讲详细讲讲她的故事。这节课，我们还是主要围绕密码展开。 27岁时，玛丽一世被自己的姑姑英格兰女王伊丽莎白一世关押了起来，一关18年。到44岁时，监狱里的她和外界反叛军密谋要杀害姑姑，一旦谋杀成功，她自己就能坐上王位。当时的信件都是通过特殊渠道传入监狱，最后由侍女在递送红酒时，藏在瓶塞中带进去。 玛丽一世很聪明，包含暗杀计划的并不是普通的信，而是加密过的。就算不慎落入伊丽莎白一世的手中，也没人看得懂。 其中用到的加密方法，就是替代法。所有的英文字母被类似符文的东西替换，一些常用词也用符号代替。具体的对应方式，你可以参考下面这个图表。 玛丽此后就通过这个特殊渠道和反叛军通信，几个月后，她熟练掌握，写信可以直接用密文，不用一个个字母查对照表了。 不幸的是，这个特殊消息传递的渠道里，竟然隐藏着一个双面间谍，他把情况汇报给了伊丽莎白。在位的女王正愁抓不到把柄，这下终于有机会名正言顺的处死玛丽了。 不过现在还急不得，必须抓到足够硬的证据，而且最好把整个阴谋背后所有的参与者一起除掉，所以伊丽莎白没有打草惊蛇。 此后玛丽和外界的通信，每一封都先经过双面间谍送到密码学校，花1个小时誊写好，然后再密封好，就像从没有被截获过那样，递出皇宫。密码学校的人再拿着誊写好的密文想法破解，最终他们成功了。 破解方法，就叫做“ 频率分析法 ”。这种方法其实在9世纪的阿拉伯就出现了，只是到了16世纪才被欧洲数学家注意到。 下面咱们讲讲它的原理。很简单，英文中字母出现的频率，是不一样的。比如字母e是出现频率最高的，占；其次是t，；然后是a，o，i，n等，最少的是z，只占。 英语中字母频率统计 除了英语，其他语言也有详细统计。 玛丽和外界用密文往来很多，字符总量足够多，全部收集到一起，统计哪个符号出现的比例最高，那个字符大概就是字母e。 当然，有些字母出现的频率极为接近，比如h，r和s，分别是，和。但只要稍微留意字母前后的关联，就可以区分出来。比如：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