【算法分析与设计】第33篇：RSA公钥密码体制的算法原理与安全性

在前两篇中我们分别建立了模运算与扩展欧几里得算法的基本框架以及素数检测与概率方法的工具集。这两套数论工具的汇合恰好构成了RSA公钥密码体制的全部技术要素。Diffie和Hellman在1976年提出了公钥密码的思想Rivest、Shamir和Adleman于1977年首次给出了具体的构造方案。近半个世纪后的今天RSA依然是互联网安全通信的基石之一。理解RSA不仅需要掌握其算法流程更需要深入其数学本质与安全边界。一、密钥生成从随机数到公私钥对RSA密钥生成的每一步都建立在前面篇章的算法之上。第一步随机生成两个大素数 pp 和 qq。实际做法是随机生成一个给定比特长度的奇数用Miller-Rabin测试检验其素性若非素数则递增2继续尝试直至通过足够多轮测试。记 NpqNpqNN 称为模数其比特长度即为RSA密钥长度——常见的有2048位或4096位。第二步计算欧拉函数 φ(N)φ(N)。由于 pp 和 qq 均为素数且互质有 φ(N)(p−1)(q−1)φ(N)(p−1)(q−1)。这一函数值在生成私钥后必须严格保密甚至可以销毁——因为知道 φ(N)φ(N) 等价于知道 pp 和 qq 的乘积与和从而可解出两个素因子。第三步选取公钥指数 ee。ee 须满足 1eφ(N)1eφ(N) 且 gcd⁡(e,φ(N))1gcd(e,φ(N))1。实践中通常选用固定的小素数以加速加密最常用的取值为 e655372161e655372161它既是素数又仅有两位二进制1模幂运算极快。第四步计算私钥指数 dd。dd 是 ee 模 φ(N)φ(N) 的乘法逆元满足ed≡1(modφ(N))ed≡1(modφ(N))这一步直接调用扩展欧几里得算法。由 gcd⁡(e,φ(N))1gcd(e,φ(N))1 知 dd 必存在且唯一模 φ(N)φ(N) 意义下。最终(N,e)(N,e) 作为公钥公开发布(N,d)(N,d) 作为私钥严格保管。pp、qq 和 φ(N)φ(N) 在生成完成后应安全销毁以防私钥泄露。二、加密与解密模幂运算的正确性RSA的加密与解密操作极为简洁本质上是一次模幂运算。加密发送方获取接收方的公钥 (N,e)(N,e)。将明文编码为整数 m∈[0,N−1]m∈[0,N−1]计算密文cme mod NcmemodN解密接收方使用私钥 (N,d)(N,d)对密文执行相同的模幂运算m′cd mod Nm′cdmodN需要证明 m′mm′m即 (me)d≡m(modN)(me)d≡m(modN)。由 ed≡1(modφ(N))ed≡1(modφ(N)) 知存在整数 kk 使得 ed1kφ(N)ed1kφ(N)。于是medm1kφ(N)m⋅(mφ(N))kmedm1kφ(N)m⋅(mφ(N))k若 gcd⁡(m,N)1gcd(m,N)1由欧拉定理 mφ(N)≡1(modN)mφ(N)≡1(modN)立即得 med≡m(modN)med≡m(modN)。若 gcd⁡(m,N)≠1gcd(m,N)1由于 NpqNpqmm 必为 pp 或 qq 的倍数。不妨设 p∣mp∣m 而 q∤mq∤m。模 pp 下两端均为 00同余成立。模 qq 下gcd⁡(m,q)1gcd(m,q)1由费马小定理 mq−1≡1(modq)mq−1≡1(modq)进而 mk(p−1)(q−1)≡1(modq)mk(p−1)(q−1)≡1(modq)故 med≡m(modq)med≡m(modq)。由中国剩余定理med≡m(modpq)med≡m(modpq) 对任意 mm 成立。至此正确性证毕。三、数字签名加密过程的逆用RSA的加解密结构天然支持数字签名。签名本质上是“用私钥加密用公钥解密”——与加密过程正好相反。签名生成签名者持有私钥 (N,d)(N,d)。对消息 mm或其哈希值 h(m)h(m)计算签名sh(m)d mod Nsh(m)dmodN签名验证验证者使用签名者的公钥 (N,e)(N,e)计算 h′se mod Nh′semodN。若 h′h(m)h′h(m)则签名有效。签名的正确性由与解密完全相同的数学推导保证se≡(hd)e≡hed≡h(modN)se≡(hd)e≡hed≡h(modN)。签名与加密的关键区别在于安全目标。加密追求机密性——只有持有私钥的接收方能解密。签名追求不可否认性与完整性——只有持有私钥的签名者能生成有效签名任何人都可用公钥验证。在实际部署中通常先对消息哈希再签名既提升效率又防止针对签名结构的数学攻击。四、安全假设与攻击分析RSA的安全性建立在以下核心假设之上在经典计算模型下大整数分解不存在多项式时间算法。若攻击者能从 NN 分解出 pp 和 qq便可计算 φ(N)(p−1)(q−1)φ(N)(p−1)(q−1)进而通过扩展欧几里得算法从 ee 求出 dd整个体制宣告崩溃。然而分解 NN 并非攻破RSA的唯一途径。以下是几种经典的攻击方法及其防御。共模攻击若同一消息 mm 用相同的 NN 但不同的 e1e1​ 和 e2e2​ 分别加密且 gcd⁡(e1,e2)1gcd(e1​,e2​)1则攻击者可利用扩展欧几里得算法找到 x,yx,y 使 xe1ye21xe1​ye2​1进而计算 c1x⋅c2y≡mxe1ye2≡m(modN)c1x​⋅c2y​≡mxe1​ye2​≡m(modN)从而无需私钥即可恢复明文。防御策略很简单永远不要向多个接收方发送相同的明文而是为每次通信生成随机的会话密钥。低解密指数攻击Wiener攻击若为加速解密而选取过小的 dd如 dN1/4/3dN1/4/3则 dd 可通过连分数展开从 (e,N)(e,N) 中高效恢复。这一攻击揭示了RSA参数选择中一个重要的安全约束dd 不能太小即使牺牲解密效率也必须保证安全。选择密文攻击RSA的乘法同态性质——E(m1)⋅E(m2)E(m1⋅m2)E(m1​)⋅E(m2​)E(m1​⋅m2​)——使得攻击者可以构造特定的密文来获取关于明文的线索。实际部署中通过填充方案如OAEP破坏这种同态结构使加密不再是单纯的模幂而是一个带有随机性和冗余结构的完整变换。量子计算威胁Shor在1994年证明量子计算机可以在多项式时间内分解大整数。这意味着一旦大规模通用量子计算机成为现实RSA的安全性将不复存在。后量子密码学目前正在寻找能够抵抗量子攻击的替代方案如基于格的密码体制。五、实践中的RSA填充与混合加密教科书式的RSA——直接对 mm 做模幂——在实践中存在多处安全隐患。实际部署的RSA通常包含以下增强。OAEP填充最优非对称加密填充在明文前插入随机数和冗余校验信息使加密过程具有随机化语义安全性。同样的明文两次加密会产生完全不同的密文同时提供了选择密文攻击的抵抗能力。混合加密RSA的加密速度远慢于对称密码如AES。实践中通常用RSA加密一个随机生成的对称会话密钥再用该会话密钥以AES加密实际的大量数据。这种混合模式兼顾了公钥的密钥分发便利性与对称密码的加解密效率。六、总结与展望RSA以极简洁的数学结构——两次模幂运算——实现了公钥加密与数字签名两大核心安全功能。它的正确性由欧拉定理和中国剩余定理严格保证其安全性则建立在整数的乘法远比分解容易这一数学不对称性之上。从密钥生成中的Miller-Rabin测试到私钥计算中的扩展欧几里得算法再到攻击分析中的连分数与格约化RSA串联起了数论算法篇章的全部知识链条。RSA的成功也引出一个深刻的理论问题是否存在与因子分解难度等价或更优的公钥密码体制下一篇我们将转向公钥密码的另一种数学基础——离散对数问题。Diffie-Hellman密钥交换与ElGamal加密体制将在不同于因子分解的代数结构中构建安全通信同时也将为后续的椭圆曲线密码学铺平道路。