终极密码


​ 公元前 54 年,深冬。

​ 高卢,毕布拉克德。

​ 罗马共和国高卢行省长——尤里乌斯·恺撒,借着帐篷里的烛火,正在一张羊皮上写着什么。

​ 战况紧急! 恺撒的爱将西塞罗,突然遭到维尔纳人的围攻。

​ 现在,必须立刻派一名骑兵送信给西塞罗,命令他重整旗鼓,两军合力突围。

​ 可是,万一这封信被敌人截获怎么办?

​ 想到这里,他不由自主地停下了笔,棱角分明的脸上,分明掠过一丝狡猾的微笑……


凯撒大帝、福尔摩斯与密码学

​ 作为罗马的第一位独裁者,恺撒大帝还有一个鲜为人知的技能点:

​ 其实,大帝不是历史上第一个想出加密算法的人。据说,我朝的姜子牙在 3000 年前,就发明了古装版密码本「阴书」。

​ 但恺撒密码,却很有可能是首个广泛运用到军事通信领域的加密技术。

​ 恺撒密码的原理,说白了就是一个字:替换

​ 如果心里想的是字母 A,纸上就写 B;要写 B,就用 C 代替。当然,我也可以用 D 替换 A,用 E 替换 B,以此类推(偏移 3 个字母)。

​ 只要收发双方都知道偏移量是几,就能轻松加密和解密;而外人看到的无非是一堆乱码。

​ 这就让上课传小纸条,有了新招数!心里想(明文):I love U,老师看到(密文):L oryh X。

​ 在今天看来,这种算法极易破解,毫无技术含量可言。但在当年的罗马战场,这就是令吃瓜群众望而生畏的黑科技!

​ 在恺撒制霸罗马的全盛时期,就连教主耶稣都不得不服: 上帝的归上帝,恺撒的归恺撒。

​ 然而讽刺的是,这样一位狂拽酷炫屌炸天、还精通密码谍战的军事天才,却死于一场密谋政变,生生被戳了 23 刀。为了纪念大帝,人们把恺撒制成了扑克牌上的标本:方块 K。

​ 又过了一千多年,恺撒大帝和他的罗马帝国早已灰飞烟灭,恺撒密码和扑克却被后人发扬光大。

​ 原版的恺撒密码,是用字母替换字母,而且所有字母还是按照偏移量顺序替换的,极大地降低了破解难度。到了维多利亚时代,这两个弱点终于被改进。于是,连福尔摩斯逮到的一个普通黑帮小弟,都学会原创这样的密码了:

​ 我们来看,传说中的卷福,是怎样破解这种图形密码的。

​ 在英文字母中 E 最常见。第一张纸条上的 15 个小人,其中有 4 个完全一样,因此猜它是 E。

​ 这些图形中,有的带小旗,有的没有小旗。从小旗的分布来看,带旗的图形可能是用来把这个句子分成一个个单词。

​ 现在最难的问题来了。

​ 因为,除了 E 以外,英文字母出现次数的顺序并不很清楚,要是把每一种组合都试一遍,那会是一项繁琐且无止境的工作。

​ 根据似乎只有一个单词的一句话,我找出了第 2 个和第 4 个都是 E。

​ 这个单词可能是 sever(切断),也可能是 lever(杠杆),或者 never(决不)。

​ 毫无疑问,使用 never 这个词来回答一项请求的可能性极大,所以其他三个小人分别代表 N、V 和 R。

​ 如此这般以此类推,福尔摩斯利用上(主)下(角)文(光)逐(环)个(的)击(加)破(持),分分钟破译了全部 52 个密文。

​ 不过,所有基于替换法的加密算法,都有一个致命的弱点:因为凡是用字母构成的文字,其字母分布都要符合语言规律,比如英文单词中 E 最常见,Z 和 X 最罕见,无论把字母替换成多么奇葩的东西,符号的分布规律永远不会变,用概率统计+穷举法+玩填字游戏的基本技巧,任何密文的破解只是时间问题。

​ 就当小伙伴们都以为恺撒密码的发展已经走到头的时候,德国人谢尔比乌斯却给替换式密码来了一次大升级,造就了有史以来最可靠的加密系统,一度令盟军绝望的噩梦,让希特勒成也萧何败也萧何的二战谍报神器——英格玛密码机,又叫恩尼格玛密码机(ENIGMA)。


二战谍报神器跌落神坛

​ 英格玛(Enigma)密码机牛在哪里?

  1. 机器加密

    这是世界首台全自动的加密机器,而此前编码、译码一直靠人力。我国由于国情原因,直到 20 世纪 80 年代还在用铅笔+纸的人肉编码方法。用机器的好处不仅是省力,而且,可以轻松搞定人力难以企及的复杂算法。

  2. 复式替换

    虽然基础原理和恺撒密码相同,但英格玛的字符替换方式却高级了不止一个档次:复式替换。

​ 也就是说,如果你连打 3 个 A,恺撒密码的密文可能是 DDD,但英格玛的密文却可能是 BDA。

​ 英格玛的神奇之处在于「转子」,它通过转动的方式实时改变替换方式,每敲一个字所用的替换方式都不同,这让依赖频率分析、概率统计的破解方法从此无的放矢。

​ 原版的英格玛密码机只有一个转子,二战时期德军为了万无一失,把转子加到了 3 个。

​ 每个转子都有独立的设置,3 个转子所有可能的设置,高达 105654 种组合!这样一来,连穷举法暴力破解的一线希望都断了念想。

​ 正因为英格玛在当时太过逆天,以至于德军从此高枕无忧,以为盟军这辈子也别想破解了。

​ 他们说得没错。单凭人力,是不可能干过英格玛密码机的。能够破解这台机器的,只能是另一台机器,一台算力更强大的机器。

​ 马拉松运动员同志阿兰·图灵 1941 年发明的机器解码,用传统的频率分析+机器暴力穷举干掉了英格玛,从此军情六处把德军的情报兜了个底朝天。直到盟军诺曼底登陆,德国人还没有反应过来,他们正是被自己的传家宝坑死的。

​ 而图灵的这台机器,就是世界上第一台计算机。

​ 在计算机时代,复式替换加密从此跌落神坛、万劫不复。

​ 而且实战中还发现,有时最容易攻破的反而不是算法,而是人。

​ 只要搞定那个掌握密码本的人,一切密钥都不攻自破。


全民加密:RSA 技术

​ 显然,拥有密码本的人越少越好。

​ 但问题是 How?

​ 曾经,这是个无解的难题。

​ 道理很简单:密码本必须人手一本,否则卧底同志们还拿什么来加密通信呢?

​ 历史告诉我们,当所有人都认为无解的时候,换个思路,往往就是柳暗花明、醍醐灌顶的时刻。

​ 传统的密码学中,无论采用何种加密算法,都默默地遵循着一个思维定式:加密和解密是互逆的,也就是说,只要知道如何加密,就一定知道如何解密,反之亦然。

​ 这被称为「对称加密」。

​ 而世间还有一种「非对称加密」(RSA):我可以把加密方法公开给全世界(公钥),但解密算法(私钥)只有我一个人知道,就算你知道如何加密,也不可能据此推出如何解密。

​ RSA 为什么能做到「知道加密算法也推不出解密算法」?

​ 这基于一个数学事实:将两个大素数相乘十分容易,但对乘积因式分解、还原成两个素数却极其困难,而且数字越大,困难级别指数上升。

​ 解密靠的是私钥,而破解私钥的唯一方法是猜出公钥是哪两个数字的乘积,因此,把大数乘积作为公钥公开是非常安全的。

​ 举个例子:37×97=3589

​ 小学生都会手算,但是,问 3589 是哪两个数的乘积?你回答得出来吗?

​ 在对称加密时代,密码本只能人手一本;有了 RSA,真正的密码本(私钥)只要总部的领导一个人知道就行,在各地卧底的特工们靠公钥就能加密发密文。

​ 这就是为什么 RSA 能在短短 40 年内取代流传两千多年的恺撒,成为当今世界全民加密的事实标准:方便。

​ 生活中,当你网购时,浏览器用公开下载的公钥把你的付款信息加密发送给服务器,服务器用没人知道的私钥解密信息,这一切是在你没有丝毫察觉的情况下悄然完成的。更给力的是,RSA 还是一个相当坚固的加密算法。

​ 比如,上面那个用来吓人的数字,有 232 位(768 比特),这已经是当今地球上计算机能分解的最大整数了。

​ 而你在网上随便申请一个免费的 https 加密证书,长度都有 2048 比特!

​ 在回顾了人类几千年来的密码学成果之后,请你,把它们统统忘掉。

​ 因为现在,无敌的量子通信来了。

​ 它靠的可不是什么逆天的算法,而仅仅是两枚神奇的硬币。


下一章:无敌的量子通信


闪耀的小星星🌟