RSA 加密:光天化日之下的秘密

#TL;DR

1976 年之前,每一个加密系统都有同一个致命缺陷:你需要一把密钥,而且双方必须在能安全通话之前就都握有它。这意味着信使、密封信封、预先共享的密码本——这些在一个”陌生人要在公网上交换信用卡号”的世界里全都行不通。Diffie 和 Hellman 证明了一个激进的想法是可行的:两个人可以在不交换任何秘密的前提下约定一个共享秘密。一年后,MIT 的三位研究员——Rivest、Shamir、Adleman——造出了第一套实用系统:RSA。它的诀窍是一扇数学活门。把两个巨大的素数相乘微不足道;把结果反过来分解回那两个素数,实际上是做不到的。你发起过的每一次 HTTPS 连接,都依赖这个不对称。

#密钥分发问题

密码学自古有之。凯撒用过字母替换;Enigma 差点赢下了一场战争。但 1970 年代之前的每一个系统都有一个共通的致命假设:收发双方已经有了同一把密钥。

对有信使的将军来说没问题。对一张网络来说是灾难。

想象 1975 年的 ARPANET。你想从 UCLA 给 MIT 发一条涉密消息。你用一把秘密密钥加密它。但 MIT 怎么拿到这把密钥?你没法在网上发——任何监听者都能截住它,进而读到你的消息。你可以用邮寄、甚至亲自飞过去,但那就违背了”有一张网络”的意义。并且每对通信方都需要不同的密钥。一张 100 节点的网络需要 4,950 把独立密钥,每一把都要事先交换。

这被称为密钥分发问题,密码学家困在这个问题上几个世纪。每一种聪明的加密方案不过是把问题换了个地方——你仍然需要一条安全信道去传密钥,但你要真有一条安全信道,那还要加密干嘛?

#改变一切的一篇论文

1976 年 11 月,斯坦福的 Whitfield Diffie 和 Martin Hellman 发表了 “New Directions in Cryptography” ——计算机科学史上最重要的论文之一。

他们的洞见很激进:如果加密和解密用的是不同的密钥呢?一把钥匙上锁,完全另一把钥匙开锁。你可以把上锁那把钥匙公布给全世界——钉在公告栏上、在广播里读出来——只有持有那把开锁钥匙的人才能读消息。

他们把这个叫公钥密码学。概念优雅且可证明可行。但他们没有可用的实现。他们证明了这把锁可以存在,但还没把锁造出来。

那个挑战——找出一个一个方向算起来很容易、反向几乎不可能的数学函数——是在向世上每一位数学家和计算机科学家下战书。

#MIT 的一个逾越节夜

在 MIT,三位年轻研究员接下了这个挑战。

Ron Rivest 是计算机科学家。Adi Shamir 是数学家。Leonard Adleman 是怀疑主义者——一位理论计算机科学家,他自认的角色就是把 Rivest 和 Shamir 想出来的方案一个个打破。流程总是这样:Rivest 提方案,Shamir 帮着完善,Adleman 找出漏洞。他们试过几十种方案。

1977 年 4 月,Rivest 在一顿逾越节家宴(Passover seder)之后熬夜,一边喝酒一边想数论。到凌晨四点,他有了一个完整的系统——数学、证明、算法。他把它写下来,第二天早上交给 Adleman。

Adleman 破不了。没人破得了。

这个系统以三位作者命名为 RSA。按字母顺序 Rivest 和 Shamir 的首字母在前,Adleman 一开始拒绝把自己的名字署上去——他觉得这”不过是一篇计算机科学论文”。Rivest 坚持。它后来成了这个领域被引用最多的论文之一。

#活门

RSA 建立在一个独特的不对称之上:乘法很容易,分解很难。

取两个大素数——叫它们 p 和 q。把它们相乘易如反掌,1977 年的计算机也一样:

p = 61
q = 53
n = p × q = 3233

现在忘掉 p 和 q。只给你 n = 3233,你能找回原来的素数吗?数小的时候当然可以。但当 p 和 q 各自有 300 位长、n 因此有 600 位时,没有已知算法能在任何合理时间内把它分解。一年不行,到宇宙寿命结束也不行。

这就是一扇活门函数(trapdoor function):一个方向掉下去很容易,反向爬回来几乎不可能。

RSA 把它变成加密的做法:

密钥生成 — 只做一次的事:

from math import gcd

# 1. 选两个素数(这里用小的,真 RSA 用 1024+ 位素数)
p, q = 61, 53
n = p * q          # 3233 —— 模数,公钥和私钥共有

# 2. 算欧拉函数:有多少个 < n 的数与 n 互素
phi = (p - 1) * (q - 1)  # 3120

# 3. 选一个公钥指数 e,与 phi 互素
e = 17  # 常见选择;真实实现里多用 65537

# 4. 算私钥指数 d:e 在 mod phi 下的模逆
#    也就是找一个 d 使得 (e * d) % phi == 1
d = pow(e, -1, phi)  # 2753

# 公钥: (e=17, n=3233)   —— 向全世界公布
# 私钥: (d=2753, n=3233) —— 拿命守住它

加密 — 任何人拿你的公钥都能做:

message = 65  # 要加密的数字(比如 ASCII 'A')
ciphertext = pow(message, e, n)  # 65^17 mod 3233 = 2790

解密 — 只有你拿着私钥能做:

plaintext = pow(ciphertext, d, n)  # 2790^2753 mod 3233 = 65

魔法在于:65 → 2790 → 65。公钥把消息打乱,私钥——它从未被传输、从未被共享、从未离开你的机器——把它还原。

拦截到 2790、又知道公钥 (17, 3233) 的攻击者,要恢复 d 就得先把 3233 分解。对玩具数字来说微不足道;对今天的 2048 位密钥来说,在计算上是不可能的。

#数字签名:证明是你写的

RSA 还有第二招。如果说加密是公钥 → 私钥(人人都能上锁,只有你能开锁),那么反方向就给你数字签名:私钥 → 公钥(只有你能签,人人都能验)。

# 签名:用你的私钥"加密"
document_hash = 42
signature = pow(document_hash, d, n)  # 只有你能产出

# 验签:用你的公钥"解密"
verified = pow(signature, e, n)       # 任何人都能核对
assert verified == document_hash      # 对上了就说明你签的

这解决了一个和文字一样古老的问题:怎么证明一条消息没被篡改、并且确实来自它自称的那个人? 数字签名支撑着软件更新、法律文件、加密货币交易,以及你签过的每一条 git commit。

#NSA、专利,以及”数学归谁所有”之争

RSA 不是悄无声息降临的。美国的信号情报机构 NSA 对此极其不安。他们多年的权力建立在”强加密是政府专利”这个前提之上。平民是不该拥有它的。

1977 年,一位 NSA 员工给 IEEE 写信警告,发表密码学研究可能违反《武器出口管制法》——这是和导弹技术同样的法。言下之意:Rivest、Shamir、Adleman 可能因为发表一篇数学论文而被起诉。

威胁没有生效——学术界强烈反击——但它预示了接下来几十年的冲突。1990 年代,密码战争爆发,美国政府试图限制平民可用的密钥长度、强推后门(Clipper 芯片),并把加密软件归类为军火。Phil Zimmermann 因为把用了 RSA 的 PGP(Pretty Good Privacy)作为自由软件发布,被调查了三年。

密码学家赢了。政府退让。强加密对所有人合法。但这场争论——公民是否应该拥有连政府也破不了的加密?——从未真正结束。今天每一次关于加密消息应用的争吵里,都能听到它的回声。

#RSA 做对了什么

RSA 发表 49 年了。计算机比当年快了几十亿倍。RSA 仍在工作——不是因为没人攻击它,而是因为它核心的数学不对称真的难:

密钥分发问题被解决了。 你可以把公钥登在广告牌上,系统依然安全。两个陌生人不用见面也能私下通信。这是互联网商业的基础。
不仅是保密,还有身份认证。 数字签名证明公钥密码学不只是用来藏消息——它也用来证明身份、验证完整性、在从未见过的机器之间建立信任。
纵深防御。 实践中 RSA 并不单独工作。现代 TLS 用 RSA(或其椭圆曲线后代)来交换一把会话密钥,然后切换到 AES 之类更快的对称加密来加密真正的数据。这种分层方法意味着某一环变弱时,整体系统可以优雅降级。
数学成为基础设施。 RSA 之前,密码学是特工技艺。RSA 之后,它是计算机科学的一部分。这个算法把一个涉密军事研究分支,变成了一门任何人都可以学习、改进和构建的公开学科。

地平线上还有一朵乌云。RSA 的安全性依赖”分解大数在计算上不可行”这一假设。运行 Shor 算法的量子计算机可能改变这一点——把分解 2048 位的数从千年变成几个小时。这还没发生,但密码学界已经在准备,设计不依赖分解的后量子算法。撑了五十年的那扇活门也许需要换新——但公钥密码学这个概念、Diffie、Hellman、Rivest、Shamir、Adleman 掀起的那场革命,是永久的。