密码学科普小说 · 第 7 章

素数信封：RSA 的逾越节之夜

1977 年 4 月，麻省理工。一场逾越节晚宴刚散，三个年轻人——罗纳德·李维斯特（Rivest）、阿迪·萨莫尔（Shamir）、伦纳德·阿德曼（Adleman）——还在宿舍里喝着酒争论。Alice 和 Bob 这次的身份是“隔壁借暖瓶的学生”。

他们在找迪菲和赫尔曼没找到的东西：一个“陷门单向函数”——正着算很容易，反着算很难，但如果你手里有一个秘密的“后门”，反着算也变得很容易。

那天夜里，李维斯特一个人在沙发上翻来覆去睡不着，最后坐起来写了一夜。第二天早上，他把一份手稿拍在桌上。

Bob 后来给 Alice 讲了个简化版：

第一步，偷偷挑两个很大的素数 p 和 q，乘起来得到 n。

第二步，挑一个公开的数 e（常用 65537），再用 p 和 q 算出一个秘密的数 d，使得“先 e 次方、再 d 次方”（都对 n 取余）会把任何数变回原样。

第三步，把 (n, e) 公开——这就是公钥，也就是 Alice 当初说的“挂锁”。d 自己藏好——这就是私钥。

谁想给你发消息，就把消息变成数字 m，算 m^e mod n 发过来；你用 d 一算就还原了。而别人要算出 d，就必须知道 p 和 q——也就是要把 n 分解质因数。

Alice：“如果 n 很小呢？”

Bob：“3233 你心算一会儿就能拆成 61×53。可如果 n 有 617 位十进制数字（也就是 2048 比特），按目前已知最好的算法，全世界的计算机一起拆也拆不动。”

更妙的是，这把锁还能倒着用：用私钥 d 对一段消息“签名”，任何人都能用公钥 e 验证——验证通过，说明这段消息确实出自持有私钥的人，而且一个字都没被改。这就是数字签名，它同时解决了第一章里的“完整性”和“真实性”。

窗外天快亮了。萨莫尔打着哈欠说：“我们是不是该给它起个名字？”

阿德曼说：“按姓氏首字母排吧。”

“RSA，”Alice 轻声说，“我知道这个名字。”

三个人奇怪地看着她。