跳转到内容
← 返回算法
密码学算法计算机科学 · 密码学 · 数论约 18 分钟阅读

RSA 公钥密码

Public-Key Cryptography: RSA

1976 年，Whitfield Diffie 和 Martin Hellman 发表了一篇论文《密码学的新方向》（New Directions in Cryptography），提出了一个听起来矛盾的想法： 公开传递加密密钥，而不泄露解密能力。

RSA公钥密码非对称加密数论网络安全

1976 年，Whitfield Diffie 和 Martin Hellman 发表了一篇论文《密码学的新方向》（New Directions in Cryptography），提出了一个听起来矛盾的想法：

公开传递加密密钥，而不泄露解密能力。

几千年来，密码学的铁律是：加密和解密用同一把钥匙，这把钥匙必须秘密传递。Diffie 和 Hellman 的论文打破了这个假设。但他们只提出了框架，没给出完整算法。

一年后的 1977 年，MIT 的三位数学家——Ron Rivest、Adi Shamir 和 Leonard Adleman——给出了第一个实用的公钥密码系统：RSA（取三人姓氏首字母）。

破除误解：公钥加密不是"无法破解"

流行文化常把 RSA 描述为"绝对安全"的加密。这不准确。

RSA 的安全性基于一个数学难题的难解性：对大整数做质因数分解（Integer Factorization）极其困难。没有人证明了这个问题"一定没有高效算法"——理论上它可能被打破，只是迄今没人做到。这与数学证明的确定性完全不同。

更重要的是：RSA 的安全性随着算力提升和算法进步而衰减。1024 位 RSA 在 2000 年代被视为安全；今天已不被推荐。现代应用要求至少 2048 位，敏感应用建议 4096 位。

此外，实现错误（如弱随机数生成器、填充方案不当）会让数学上安全的 RSA 在实践中被攻破。密码学的安全不只是数学，更是工程。

数学基础：大数分解的不对称性

RSA 的核心是两个相反方向的计算代价极不对称：

  • 正向（乘法）：给两个 512 位质数 $p$ 和 $q$，计算 n=p×qn = p \times q——毫秒级
  • 逆向（分解）：给 $n$，恢复 $p$ 和 $q$——目前已知最快的算法在 RSA-2048 上需要数百亿年的计算

（注：目前被分解的最大 RSA 数是 RSA-250，829 位，由法国国家信息与自动化研究所等团队在 2020 年完成，花费了相当于约 2700 年单核 CPU 的计算量。）

RSA 还依赖欧拉定理（Euler's Theorem）：若 gcd⁡(m,n)=1\gcd(m, n) = 1，则 mϕ(n)≡1(modn)m^{\phi(n)} \equiv 1 \pmod{n}，其中 ϕ(n)\phi(n) 是欧拉函数。

欧拉定理在这里的角色，是保证加密和解密互为逆运算。密钥生成时选择 e×d≡1(modϕ(n))e \times d \equiv 1 \pmod{\phi(n)}，意味着存在整数 $k$ 使 ed=1+kϕ(n)ed = 1 + k\phi(n)。于是解密时：

cd≡med=m1+kϕ(n)=m⋅(mϕ(n))k≡m(modn)c^d \equiv m^{ed} = m^{1 + k\phi(n)} = m \cdot \left(m^{\phi(n)}\right)^k \equiv m \pmod{n}

明文被精确还原。整个方案的巧妙之处在于：正向计算 c=me mod nc = m^e \bmod n 只需要公钥；但要反向求 $m$，攻击者似乎必须先算出 ϕ(n)=(p−1)(q−1)\phi(n) = (p-1)(q-1)——而由 $n$ 和 ϕ(n)\phi(n) 联立即可解出 $p$ 和 $q$，所以"算出 ϕ(n)\phi(n)"与"分解 $n$"在计算上等价。分解难题就这样被焊进了求逆运算里。

公钥指数习惯取 e=65537=216+1e = 65537 = 2^{16} + 1：它是质数（与 ϕ(n)\phi(n) 互质的概率高），二进制展开里只有两个 1，用平方-乘算法做模幂只需 17 次模乘，加密与验签因此极快。$e$ 小还带来一个安全上的副产品：加密方几乎无秘密可泄露，所有秘密都集中在私钥一侧。

因子分解到底有多难：亚指数，而非指数

说"分解很难"太模糊——到底有多难，直接决定密钥该多长。

试除法这类朴素算法的代价对密钥长度是指数级的。但现代最优的一般数域筛法（General Number Field Sieve, GNFS，1990 年代初由 Pollard 的原始构想发展而来，经 Buhler、Lenstra、Pomerance 等人系统化）已把代价压到亚指数：

exp⁡ ⁣((649)1/3(ln⁡n)1/3(ln⁡ln⁡n)2/3)≈exp⁡ ⁣(1.923 (ln⁡n)1/3(ln⁡ln⁡n)2/3)\exp\!\left( \left(\tfrac{64}{9}\right)^{1/3} (\ln n)^{1/3} (\ln \ln n)^{2/3} \right) \approx \exp\!\left(1.923\, (\ln n)^{1/3} (\ln \ln n)^{2/3}\right)

这不是多项式，但远好于对密钥长度的纯指数。这个"中间档"有一个直接后果：对称密钥和 RSA 密钥的长度不能按同一尺度比较。128 位对称密钥意味着穷举约 21282^{128} 次；而要让分解代价也达到 21282^{128} 量级，RSA 模数需要约 3072 位（NIST 的通行换算）。前文说 ECC 凭 256 位密钥即可对标 3072 位 RSA，原因也在这里——椭圆曲线离散对数迄今没有对应的亚指数算法，攻击者只剩指数级的通用算法。

另一个含义更隐蔽：GNFS 的渐进形式说明分解难度的"坡度"是平缓的。密钥加长一倍，破解代价的增长远低于翻倍——历史上每次算法或硬件的实质进步，都会迫使推荐密钥长度整体上移。1024 位 RSA 从行业标准沦为不推荐，正是这个坡度的实证。

RSA 的工作原理

密钥生成：

  1. 随机选两个大质数 $p$ 和 $q$（各约 1024 位）
  2. 计算 n=p×qn = p \times q（这是公开的模数）
  3. 计算 ϕ(n)=(p−1)(q−1)\phi(n) = (p-1)(q-1)（保密）
  4. 选公钥指数 $e$（常用 65537，质数且计算高效）
  5. 计算私钥指数 $d$：满足 e×d≡1(modϕ(n))e \times d \equiv 1 \pmod{\phi(n)}（用扩展欧几里得算法）

公钥：$(n, e)$；私钥：$(n, d)$。

加密（用公钥）：

c=memod  nc = m^e \mod n

解密（用私钥）：

m=cdmod  nm = c^d \mod n

正确性由欧拉定理保证：cd=(me)d=med≡m(modn)c^d = (m^e)^d = m^{ed} \equiv m \pmod{n}（在适当条件下成立）。

数字签名（反向使用密钥）：

  • 签名：用私钥对消息哈希值签名：s=h(m)dmod  ns = h(m)^d \mod n
  • 验证：用公钥验证：h(m)=semod  nh(m) = s^e \mod n

签名只有私钥持有者能生成，任何人用公钥可验证。这是 HTTPS 证书、代码签名、软件更新验证的基础。

教科书 RSA 为什么不能用：填充方案是生死线

上文写的 c=me mod nc = m^e \bmod n 常被称为"教科书 RSA"（textbook RSA）——它只应存在于教科书里。直接部署会被攻破，原因不在数学，而在明文空间的可预测性：

  • 确定性：同一明文永远加密成同一密文。当消息只有几种可能（"是/否"、一次投票的选项）时，攻击者把每种可能都加密一遍比对即可。
  • 可延展性（malleability）：RSA 是乘法同态的，E(m1)⋅E(m2)≡E(m1⋅m2)(modn)E(m_1) \cdot E(m_2) \equiv E(m_1 \cdot m_2) \pmod{n}。攻击者可以把截获的密文乘上 ses^e，得到一个解密结果为 s⋅ms \cdot m 的新密文——不知道 $m$，却能操纵它。

业界的修法是在模幂之前先做填充（padding）。但早期的 PKCS#1 v1.5 填充（1993 年定稿）留下了致命缺口：1998 年，Daniel Bleichenbacher 证明，只要服务器在解密后发现"填充格式不合法"时报出可区分的错误（哪怕只是响应时间的细微差别），攻击者就能把服务器当成预言机（oracle），用约一百万次精心构造的查询逐步还原出完整明文——即著名的"百万消息攻击"（CRYPTO '98）。它完全不需要分解 $n$，利用的只是实现"嘴不严"。

正确的替代是 OAEP（Optimal Asymmetric Encryption Padding，Bellare 与 Rogaway 1994 年在 Eurocrypt 提出）：加密前先把明文与一个随机种子送进两轮 Feistel 式的掩码结构，互相搅拌，使整个编码看上去随机。OAEP 让每次加密结果不可预测（治好确定性），又让"构造一个能通过解码检查的密文"在不知明文时不可行（治好可延展性）。配合 RSA 使用时，其抗选择密文攻击（IND-CCA2）的安全性可归约到 RSA 假设本身——Fujisaki、Okamoto、Pointcheval 与 Stern 在 2001 年补全了这一严格证明。今天仍在使用 RSA 加密的场合，标准要求 OAEP（加密）与 PSS（签名）；TLS 1.3 则干脆移除了 RSA 密钥交换。

HTTPS：RSA 的最大规模部署

当浏览器连接 https://bank.com：

  1. 服务器发送包含其公钥的数字证书（由受信任的证书颁发机构 CA 签名）
  2. 浏览器验证证书的有效性（证书链、有效期、域名匹配）
  3. 双方用公钥机制协商一个对称密钥（实际加密用 AES，因为比 RSA 快 100-1000 倍）
  4. 后续通信用对称密钥加密

RSA（或现代的椭圆曲线 ECDH）只用在握手阶段——解决密钥分发问题。实际数据加密用对称密码（AES-GCM）。这种混合方案兼顾了非对称加密的"不需要预先共享密钥"和对称加密的速度。

工程实现：加速的代价与侧信道

私钥操作（解密、签名）是 RSA 最贵的一步。标准优化是用中国剩余定理（CRT）：不直接算 m=cd mod nm = c^d \bmod n，而是分别算 mp=cd mod (p−1) mod pm_p = c^{d \bmod (p-1)} \bmod p 和 mq=cd mod (q−1) mod qm_q = c^{d \bmod (q-1)} \bmod q，再合并。模数和指数都缩短一半，而模幂开销大致随位长的三次方增长，总体提速约 4 倍——几乎所有生产实现都这么做。

但每一次工程优化，都在数学之外开出新的攻击面：

  • 时序攻击：1996 年，Paul Kocher 证明，模幂运算的耗时依赖密钥比特的取值（平方-乘算法遇到 1 要多做一次乘法），对大量操作的耗时做统计分析，可以逐位还原私钥（CRYPTO '96）。对策是"常数时间"实现——让执行路径不依赖秘密数据。
  • 故障攻击：1997 年，Boneh、DeMillo 与 Lipton 指出，CRT 实现只要在两次模幂中算错一次（例如用电压毛刺、激光照射智能卡制造瞬时故障），得到的错误签名 $s'$ 便满足 s′e≡m(modq)s'^e \equiv m \pmod q 但不同余模 $p$，于是 gcd⁡(s′e−m, n)\gcd(s'^e - m,\ n) 直接给出 $q$——一次故障就分解了模数（Eurocrypt '97）。对策朴素而有效：输出前用公钥验算一遍。

这些攻击的共同点是：被攻破的不是 RSA 的数学，而是"数学被物理设备执行"这一事实。密码工程的大部分功力，都花在弥合数学与现实之间的这道缝上。

椭圆曲线密码（ECC）：RSA 的替代

2020 年代，椭圆曲线密码学（Elliptic Curve Cryptography, ECC）正在大量替代 RSA：

为什么替代：ECC 可以用小得多的密钥提供同等安全级别。256 位 ECC 密钥的安全性大致等同于 3072 位 RSA 密钥。密钥更短意味着更快的握手、更小的证书、更低的计算开销。

ECDH（椭圆曲线 Diffie-Hellman）用于密钥协商；ECDSA 和 EdDSA（如 Ed25519）用于数字签名。现代 TLS 1.3 优先使用 ECDH 而非 RSA。

后量子密码学：下一个十年的转型

RSA 和 ECC 面临一个未来的威胁：Shor 算法（1994）可以在量子计算机上以多项式时间分解大整数和解决离散对数问题——这意味着足够大的量子计算机会同时打破 RSA 和 ECC。

2024 年 8 月，美国 NIST 正式发布三项后量子密码（Post-Quantum Cryptography）标准： - FIPS 203：ML-KEM（基于模格 CRYSTALS-Kyber）——密钥封装 - FIPS 204：ML-DSA（基于模格 CRYSTALS-Dilithium）——数字签名 - FIPS 205：SLH-DSA（基于哈希的 SPHINCS+）——数字签名

这些算法基于格密码学（lattice cryptography）和哈希函数，当前最好的量子算法也无法高效破解。各大操作系统和浏览器已开始集成，全球基础设施正在经历史上最大规模的密码学迁移。

代价与争议

密钥长度争议：推荐密钥长度随时间升级，造成"历史上生成的 RSA 密钥可能现在已不安全"的问题——长期存储的加密数据的前向安全性（forward secrecy）成问题。

随机数的关键性：RSA 密钥生成依赖高质量随机数。2012 年，Lenstra 等人分析了从互联网收集的约 1140 万个公开 RSA 公钥，发现其中约 0.2%（每一千个里约有两个）共享了某个质因数——多半是嵌入式设备（路由器、防火墙等）的随机数生成器熵不足导致两台设备"撞"出了同一个质数。一旦两个模数 n1,n2n_1, n_2 共享一个质因数，攻击者只需对它们求最大公约数（gcd⁡(n1,n2)\gcd(n_1, n_2)），就能在毫秒内同时分解两把密钥——无需触碰大整数分解这个"难题"。这篇论文戏谑地题为《Ron was wrong, Whit is right》，是"实现比数学先出问题"的典型案例。

量子计算的时间表：破解 RSA-2048 需要约 400 万个高质量物理量子比特（按现有估计），而目前最好的量子计算机只有几百个有噪声的比特。但"先记录后解密"（harvest now, decrypt later）攻击已经存在：攻击者现在收集加密流量，等量子计算机成熟后解密。

跨域连接

  • 数论：整套方案坐在欧拉定理与扩展欧几里得算法之上：模幂正向易算，反解指数却要先分解模数。安全性来自两个方向的代价不对称，而不是任何一方被证明不可能——这也是它随算力与算法进步而持续贬值的原因。
  • 群：同一套协议换一个群，结论就变。椭圆曲线上的离散对数目前没有像整数域那样的高效攻击手段，因此同等安全强度所需的密钥长度可以短一个量级，握手更快、证书更小。密钥"多少位才够"从来不是普适数字，它随群而变。
  • 量子算法：把分解归约为寻找一个模幂函数的周期，再用量子傅里叶变换在多项式时间内找出它。这是一条已经被证明的定理，缺的只是机器——而由于攻击者可以先截获密文、日后再解，迁移不能等到机器出现才启动。
  • 随机算法：密钥生成依赖高质量随机数，这一步的失败方式极其难看。若两台设备因熵不足生成了共享同一个素因子的模数，攻击者只需对两个模数求一次最大公约数，根本不必碰分解这个难题——数学没被攻破，实现被攻破了。
  • 正当性：公钥本身无法自证归属，它必须由证书链上的第三方背书。于是密码学把"该不该信任这个人"换成了"该不该信任这套授权制度"，问题没有消失，只是被搬到了另一层——签发规则、吊销机制与根证书的管辖权都成了安全性的一部分。数学能保证的是签名不可伪造，保证不了签发者的判断。

参考文献

  • Rivest, R., Shamir, A. & Adleman, L. A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. CACM 21(2), 1978. （RSA 原始论文）
  • Diffie, W. & Hellman, M. New Directions in Cryptography. IEEE Trans. Inf. Theory 22(6), 1976.
  • Buhler, J. P., Lenstra, H. W. & Pomerance, C. Factoring Integers with the Number Field Sieve. In Lenstra & Lenstra (eds.), The Development of the Number Field Sieve, LNCS 1554, Springer (1993).
  • Bellare, M. & Rogaway, P. Optimal Asymmetric Encryption — How to Encrypt with RSA. EUROCRYPT '94, LNCS 950, Springer (1994).
  • Kocher, P. C. Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems. CRYPTO '96, LNCS 1109, 104–113.
  • Boneh, D., DeMillo, R. A. & Lipton, R. J. On the Importance of Checking Cryptographic Protocols for Faults. EUROCRYPT '97, LNCS 1233, 37–51.
  • Bleichenbacher, D. Chosen Ciphertext Attacks Against Protocols Based on the RSA Encryption Standard PKCS #1. CRYPTO '98, LNCS 1462, Springer (1998).
  • Lenstra, A. et al. Ron was Wrong, Whit is Right. IACR ePrint 2012/064. （随机数缺陷导致 RSA 公钥泄漏的分析）
  • NIST. Post-Quantum Cryptography Standards (FIPS 203/204/205). 2024.

延伸阅读

  • Boneh, D. & Shoup, V. A Graduate Course in Applied Cryptography. （免费在线教材，crypto.stanford.edu）

正文中引用本条 · 8 · 其中 4 条来自其他领域

数学欧拉数论素数定理素数之谜