专题 · 8 环 · 3 环的主人不在馆里
密码与信任
终点：地址栏里那把锁
两个素未谋面的人，在一条所有人都能偷听的线路上，怎么商量出一个只有他们俩知道的秘密——这件事在 1976 年之前被认为不可能。它的全部本钱是数论里几个「正着算容易、反着算难」的运算。
缩略轴按先后排列，间距不表示年数；实心＝馆里有他，空心＝还没有。
- 约前300
辗转相除求最大公约数算法
《原本》第七卷头两个命题。它是已知最早的非平凡算法，而且至今没有被更好的通用方法取代；它的扩展形式正是今天 RSA 里求私钥的那一步。
- 1640
p 是素数时，a 的 p 次方与 a 同余结构
写在给弗雷尼克勒的一封信里，照例没给证明。今天它有两个用处：判一个大数是不是素数（费马素性检验），以及 RSA 正确性的基石。
- 1763
模不是素数时也成立的那个版本结构
φ(n) 数的是小于 n 且与 n 互素的整数有多少个。RSA 的公钥与私钥互为模 φ(n) 的逆元——这一整套就架在欧拉这条推广上。
- 1801
- 1830
元素个数有限的四则运算体系结构
他二十岁上写下有限域时，想的是五次方程。一百三十年后，纠错码和分组密码发现自己需要的正是「一套有限的、封闭的、除法也做得通的算术」——而世上只有他构造的那一种。
- 1976
在公开线路上商量出一个共同的秘密结构
迪菲与赫尔曼《密码学的新方向》不在馆里
双方各自取一个秘密指数，交换公开值，各自再幂一次就得到同一个数——而偷听者要从公开值倒推指数，就得解离散对数。密码学从此分成 1976 年之前和之后。同一思路英国政府通信总部的埃利斯一伙早几年做出来过，但被列为机密，1997 年才解密。
- 1977
把公钥和私钥分开结构
里韦斯特、沙米尔与阿德曼RSA不在馆里
正着算是两个大素数相乘，反着算是大整数分解。今天的安全建立在「分解很难」这个至今未被证明的假设上——库克那条 P 与 NP 的分界线正压在这里。
- 1985
把同一套把戏搬到椭圆曲线上结构
科布利茨与米勒各自独立不在馆里
椭圆曲线上的有理点构成一个群，这件事是十九世纪的老货——魏尔斯特拉斯给了标准形式，庞加莱研究过它的结构。换到这个群上之后，同样的安全强度只要五分之一的密钥长度，所以手机和智能卡用的几乎都是它。