加密野史：从山本五十六到中本聪

偷袭珍珠港得手后，山本五十六决定偷袭中途岛。

他派出四条先锋航母，航母指挥官们踮起脚尖，举起望远镜，争相脑补美军措手不及的画面时，美军轰炸机突然从云里穿出，遮住了天。

日军措手不及，几百架战机还没来得及飞、就被闷死在甲板上。

十分钟内，先锋航母全部喷火，王牌飞行员们直到被烤焦也没想到，美国人早就截获了他们的偷袭情报。

是谁走漏了风声？

一、对称加密的软肋

日军通讯密码以复杂出名，由一万个五位数组成，而且，太平洋战争期间升级12次，看似牢不可破，却难挡百密一疏。

这都怪美军击沉过一艘日本潜艇，从船舱里捞出来一份密码本，上面记满密语，美军由此洞穿日军80%的密电，并且得知：山本五十六正计划偷袭AF，但AF究竟在哪里？

美军翻到珍珠港被袭前夜的电报，山本五十六要求日本战机从马绍尔群岛出发，注意避开AF的空中侦察。

从地图上看，AF只能是中途岛。

为证实猜想，中途岛美军用明文假报淡水设备故障，日军截获情报，扭头告诉主力部队：带上淡水净化器，因为AF淡水匮乏。美军截获消息，确认AF就是中途岛。

最终，山本五十六的全部机密像X光片一样，摊在罗斯福总统的办公桌上，美国未战先胜。

物理战场的赢家，无一不是信息战场的胜者。就在同时，英国破译出德军的密码，加速了二战的结束。

二战时期的国家，真正的家当不是飞机、不是航母，而应该是密码本。当守护机密的重担全压在密码本上时，却没有东西能守护密码本本身，这是对称加密的软肋。

可二战之后就少有密码被破的事迹，特别是80年代美苏冷战期间，两国都使出奶劲破译对方密电，最后却都竹篮打水。

为什么会这样？这要从非对称加密的鼻祖RSA算法说起。

二、什么是RSA算法？

1977年，Rivest、Shamir和Adleman三位教授用名字的首字母命名一种新算法：RSA，可它居然不需要密码本，这在当时就像吃饭不需要碗筷刀叉。

为什么会那样清新脱俗？关键在于RSA把密码本拆分成公钥和私钥：公钥公开，用来加密；私钥私藏，用来解密。

RSA的原理很简单，但要先回忆三个初中数学小概念：质数、互质和取模。

质数：只能被它本身和1整除的自然数。比如：2、3、5、7、11、13、17……即：我们没法把一个质数拆成两个自然数之积。

互质：公约数只有1的两个正整数，比如：5和72互质。

取模：即除法中的余数，运算符是mod，比如7 ÷ 3 = 2余1，所以，7 mod 3 = 1。

RSA用四步设定密钥（公钥和私钥）：

1、找两个质数P和Q，P和Q相乘得到Max，即 Max = P × Q

2、把两个质数分别减1，相乘得到M，即 M = (P-1) × (Q-1)

3、找一个正整数E，使E与M互质，且 E＜M

4、找一个正整数D，使D × E 除以M余1，即(D × E) mod M = 1

E是公钥，加密就是让原文自乘（E-1）次，得到密文。

D是私钥，解密就是让密文自乘（D-1）次，得到原文。

我们挑两个质数：P=7, Q=13

Max = P × Q = 91

M = (P-1) × (Q-1) = 72

随机选公钥E=5，因为5与72互质，且5小于72

找到私钥D=29，因为5 × 29 ÷ 72 余 1

如果，你想把字符C传给你朋友，怎么加密才能抵抗破解？

字符C在ASCII码中对应的数字是67，加密原理很简单：

把原文67自乘4次（E-1次），注意：当自乘结果超过Max（Max = 91）时，需将结果取模后再乘。

活体演示：

原文67自乘第1次：

67 × 67 = 4489 ＞ 91

所以，4489 mod 91 = 30

把上一步的结果30拿过来，自乘第2次：

30 × 67 = 2010 ＞ 91

所以，2010 mod 91 = 8

自乘第3次：

8 × 67 = 536 ＞ 91

所以，536 mod 91 = 81

自乘第4次：

81 × 67 = 5427 ＞ 91

所以，5427 mod 91 = 58

自乘4次之后，加密结束，得到密文58。查ASCII码表，58对应” : “，把“ : ”发出去，即使被截获，也不会泄露信息，因为对方没有私钥，解不了密。

那么，掌握私钥的人如何解密？

很简单，类似于加密，解密是用密文58自乘28次（D-1次），但每次相乘结果超过Max时，需取模后再乘：

密文58自乘第1次：

58 × 58 = 3364 ＞ 91

所以，3364 mod 91 = 88

把上一步结果88拿过来，自乘第2次：

88 × 58 = 5104 ＞ 91

所以，5104 mod 91 = 8

照葫芦画瓢，第3次：

8 × 58 = 464 ＞ 91

所以，464 mod 91 = 9

第4次：

9 × 58 = 522 ＞ 91

所以，522 mod 91 = 67

第5次：

67 × 58 = 3886 ＞ 91

所以，3886 mod 91 = 64

第6次：

64 × 58 = 3712 > 91

所以，3712 mod 91 = 72

第7次：

72 × 58 = 4176  > 91

所以， 4176 mod 91 = 81

第8次：

81 × 58 = 4698 > 91

所以， 4698 mod 91 = 57

第9次：

57 × 58 = 3306 > 91

所以， 3306 mod 91 = 30

第10次：

30 × 58 = 1740 > 91

所以，1740 mod 91 = 11

第11次：

11 × 58 =638 > 91

所以， 638 mod 91 = 1

第12次：

1 × 58 = 58 < 91

58 ＜ 91，所以不用取模，直接把58拖下来乘

第13次 :

58 × 58 =3364 > 91

所以， 3364 mod 91 = 88

我们发现，从第13次开始重复第1次结果：

第14次：8

第15次：9

第16次：67

第17次：64

第18次：72

第19次：81

第20次：57

第21次：30

第22次：11

第23次：1

第24次：58

第25次：88

第26次：8

第27次：9

第28次：67

解密完成，67就是原文。

我们发现，解密过程出现两道轮回，实际只有12种可能，而且存在密文与原文相同的情形（第12次），那是因为我们用的是小质数：7和13，现实中的质数稍微大一点：

P =

3388495837466721394368393204672181522815830368604993048084925840555281177

Q =

11658823406671259903148376558383270818131012258146392600439520994131344334162924536139

Max = P × Q =

39505874583265144526419767800614481996020776460304936454139376051579355626529450683609727842468219535093544305870490251995655335710209799226484977949442955603

选用大质数后，解密过程出现的可能性将超千亿，概率上不支持破解者发现规律。

另一方面，破解密文的唯一方式是破解密钥，而Max和公钥是公开信息，于是，破解私钥唯一的方法是从Max中分解出P和Q。

已知P和Q计算乘积，普通电脑一瞬间就能算出Max，可如果想把Max拆成P和Q，那就应了一句古话：没有耕坏的地，只有累死的牛。

我国最拉风的超级计算机神威·太湖之光，装备4万个处理器，占地足足一栋别墅，拆分1个200位数字，至少要等1000年。往前推1000年，那是北宋时期，我国历史上最善于解密的包青天年方十八。

所以，与其说是在大海捞针，不如说是在太阳系中排查一颗原子，撞上大运的概率比原子还小。

正算容易倒推难，这在密码学上称为陷门函数（Trapdoor Function），是非对称加密安全性的根基。陷门函数像是出站口的旋转门：出门容易，但想进来，那只有把门拱坏一条路。

RSA是古典和现代加密技术的分水岭，它的诞生堪称历史性突破，但和其他突破一样，随着历史一路颠簸，RSA身上悬挂的缺陷也开始叮当作响。

比如：

有些算法已能拆分特定的大数，所以为求安全，人们会用更大的质数，但这样，密钥长度会被拉长，最终拖慢加解密速度。

用户陷入两难：拉长密钥吧不便捷，不拉长密钥不安全。总得有种更出彩的算法，才能让人有盼头。

于是，地平线上又升起一种新算法：椭圆曲线加密。

三、什么是椭圆曲线加密？

椭圆曲线加密（Elliptic Curve Cryptography ）即ECC，1985年由Koblitz和Miller两位教授发明，被公认为最强的通用加密法。

和RSA一样，ECC也是非对称加密：公钥加密，私钥解密。但两者生成公钥和私钥的机制不同，ECC比RSA更安全、更便捷。

为什么？我们从一个方程说起：

y² = x³ + ax + b（a和b是常数）

即使没在教科书里见过，你也完全不必害怕，只要画出来，你就会发现这不过是只插在竹签上的章鱼。

图1 椭圆曲线

章鱼的轮廓就是椭圆曲线，它的身体沿x轴对称，而且，任何竹签直插上去和章鱼轮廓最多有三个交点。

如果你去查资料，你会发现ECC的公式天罗地网，任何一个公式都会缠住你，但你马上就会知道，即使ECC看起来艰涩，但本质上不过是一局桌球游戏，只是桌球的弹射规律有点奇怪。

我们在椭圆曲线上任选一点A开球。

1、球打向B，弹往另一交点，再折向交点与x轴的对称点C；

2、到C后会弹向A，途经曲线交点时，球会折向交点的对称点D；

3、到D后会沿AD方向，射向曲线与直线的另一交点，接着弹到交点的对称点E；

图2 椭圆曲线（动图）

动图描绘的是3次撞击过程，桌球叮叮咚咚撞n次后，停在终点。

如果你知道起点坐标和撞击次数n，就能算出终点坐标。可是，这时有人跑进来，他知道起点和终点坐标，如果你问他，撞击次数n是多少？他会和球一样愣在原地，因为真的没法算。

撞击次数n就是你的私钥，一个你选的超大整数；桌球撞击n次停下，而终点坐标相当于公钥；如果你想再做一个公钥，那么改变起点坐标即可。

椭圆曲线方程、起点和终点坐标完全公开，但计算球撞了几次才停下来却没有捷径、只能一次次试，这项事业比RSA中拆分Max的任务还要艰巨，都能把量子计算机们累出血，这就是为什么说ECC比RSA更安全的原因。

同样面对228位长度的密钥，如果破解RSA需要烧开一勺水的能量，那么破解ECC所需要的能量，足以烧开地球上所有的水。

——德国数学家 Lenstra

ECC早已无处不在：我们的第二代身份证都基于ECC，美国政府部门也用ECC加密内部通信，开源浏览器Foxfire、谷歌的Chrome、苹果的iMessage服务都使用ECC。

除此之外，匿名网络Tor用ECC保护使用者隐私。中本聪曾经穿梭在各大论坛，但他的身份至今是谜，全靠Tor网络底层的ECC。

而中本聪的业余小发明——比特币，也使用ECC的数字签名算法ECDSA（Elliptic Curve Digital Signature Algorithm），不单安全性能好，而且ECDSA签起名来要比RSA签名快两个数量级。准确地说，256位的私钥用ECDSA要比2048位的RSA签名算法快20倍，是四轮车和三轮车的差别。

尽管花好稻好，可ECC也非完美无缺。

ECC需要一些随机数，而随机数的产生有赖于生成器里的“种子”，曾有人爆料：美国国家安全局（NSA）曾经对随机数生成器动过手脚，让破解难度大幅降低，这样就便于特工破译采用ECC加密的数据。

爆料者的名字叫斯诺登，他是美国棱镜门事件的主角。

根据曝光材料，NSA开发出一条伪随机数曲线secp256r1。可幸运的是，中本聪并没有选择NSA的伪随机数曲线secp256r1，而是使用了另一条非伪随机数曲线secp256k1，带着比特币躲过密码学历史上的一支暗箭，否则只要暴露过公钥的人都有一定概率被NSA内部人士猜出私钥。

结语

中本聪被公认为非对称加密年代冲刷出来的天才，而山本五十六却被定格在对称加密时代，一份密码本让它丢的不仅是四艘航母，还有自己的命。

1943年4月18日，美国空军稳稳击落山本五十六的座机，解密文件显示，美军破译出日军JN25密码本，提前获知机密行程，让他成为对称加密时期最高级别的祭品。

和对称加密相比，非对称加密可以把秘密写在明信片上，消灭了密码本被破解的问题，但加密技术进化之路并非坦途，因为密码攻防问题始终存在。

所以，并不存在绝对安全的加密方法，如果有种算法可以让我们安全享用50年，就已经足够，至于进化中的问题，就让进化本身来修补。

本文于2018年6月16日发布于微信公众号：概念地图 gainianditu