1. 为什么RSA看起来像魔术从一次现场演示说起先讲我第一次在项目里落地RSA时的困惑。当时我照着文档写了个Demo生成一对密钥用公钥加密HELLO拿私钥解密屏幕上顺利还原出HELLO。一切正常但我盯着那行M^e mod n和C^d mod n的代码愣了很久——凭什么一个数先做e次方取模再做d次方取模就能回到原来的数这不是巧合。RSA是公钥加密里少有的、能用三行公式讲清楚核心机制却需要三页纸才敢说自己理解的算法。很多人会调库、会生成密钥对、能完成加解密但一旦被问到如果明文恰好和模数不互质解密还成立吗为什么e和d是这种不对称的关系知道n和e之后暴力求解d到底难在哪里往往就卡住了。这篇我打算不按普通教程的路子走。不先给步骤而是把RSA拆成两条主线来讲一条线是确保加密后能被解密的数论基础另一条线是就算知道公钥也无法倒推出私钥的安全性边界。中间穿插几个非常重要的推论比如中国剩余定理加速、乘法同态、低指数攻击窗口以及明文与模数不互质这种教材通常避而不谈的极端情形。如果你已经会调用RSA接口但想搞懂底层原理或者正在学密码学、需要把数学和代码对上号这篇应该比较对路。我会尽量把每一个为什么都拆到能亲自验算的程度。2. 数论地基同余、互质、欧拉函数与欧拉定理RSA的数学几乎全部建立在一个概念上模运算。这个概念你可以直接理解成除法只关心余数。比如7除以5余2我们说7 ≡ 2 (mod 5)。钟表也是模运算13点就是1点(mod 12)。所有RSA加解密都是在某个钟面上转圈这个钟面的刻度就是模数n。第二个概念是互质。两个数互质的意思是它们的最大公约数是1比如8和15虽然15不是质数但8和15没有公共因子所以互质。RSA里有两处强制互质要求一是密钥生成时选择的公开指数e必须与φ(n)互质二是欧拉定理的使用前提就是底数与模数互质。第三个概念是欧拉函数φ(n)整数1到n当中与n互质的数的个数。如果n是质数p那1到p-1全部和p互质所以φ(p)p-1。如果n是两个不同质数p和q的乘积φ(n)有一个漂亮的乘法性质φ(pq)φ(p)φ(q)(p-1)(q-1)。因为与pq互质等价于同时与p互质且与q互质两者独立计数相乘。第四个概念是欧拉定理这是整篇内容的灵魂若gcd(a,n)1则 a^{φ(n)} ≡ 1 (mod n)这个式子说明在模n的世界里任何与n互质的数a经过φ(n)次方之后一定会回到1这个位置。你可以把φ(n)想象成模n乘法循环的一个固定周期。举个例子验算取n153×5φ(15)8。取a2gcd(2,15)1计算2^8256256除以15余1完全吻合。再取a44^86553665536除以15余数也是1。这不是某个数特有的性质而是所有与15互质的数都遵守的规律。欧拉定理还有一个推论叫费马小定理当模数是质数p时φ(p)p-1于是a^{p-1} ≡ 1 (mod p)。这个推论在RSA的严格正确性证明里会派上用场尤其当明文与模数不互质时。对刚接触RSA的朋友我的建议是先把欧拉定理亲手验算三次以上换不同的n和a直到产生这个定理是显然成立的感觉。因为后面的密钥生成、解密还原、安全性分析本质上都是对欧拉定理的反复套用。3. 密钥生成全流程每个参数为什么是这样少一步都不行现在进入实操环节。我把RSA密钥生成的完整过程列出来再逐个解释参数背后的约束条件。第一步选两个大质数p和q。这里要求p和q独立随机选取且不能太接近。如果p和q太接近攻击者可以用费马分解法快速分解n。实际生产中一般要求两者位数相同但数值上相差足够大。第二步计算npq。n就是模数也是钟面的刻度。公钥和私钥都包含n所以n是公开的。n的安全性完全取决于从n分解出p和q有多难。第三步计算φ(n)(p-1)(q-1)。这一步私密。一旦算出φ(n)结合公开的e任何人都能算出私钥d。所以p和q的保密本质上就是为了保密φ(n)。第四步选择公开指数e要求1eφ(n)且gcd(e,φ(n))1。gcd1的互质条件保证e在模φ(n)下有乘法逆元。实际工程里经常直接用固定值65537即2^161因为它是质数只要φ(n)不是65537的倍数就能用同时作为二进制数只有两个1做模幂运算时速度较快。第五步计算私钥d使 e·d ≡ 1 (mod φ(n))。这里的d就是e在模φ(n)下的乘法逆元。计算逆元使用的工具叫扩展欧几里得算法它的本质是解贝祖等式exφ(n)y1。整个过程中只有这一步需要递归和回溯但复杂度是O(logφ(n))计算很快。第六步销毁p、q、φ(n)。密钥对最终是公钥为(n,e)私钥为(n,d)。p、q、φ(n)这些中间参数在完成d的计算后不再需要必须安全删除。如果这些值泄漏任何人都能重新算出d。有一个容易踩的坑把p或q当成私钥的一部分保存在代码里。这在实际项目中常发生——出于调试方便保存了p和q结果私钥文件泄漏的后果就不是只泄漏一条私钥而是整个n的分解难度都被击穿。正确做法是签名或解密时必须用到p和q的时候比如CRT加速场景再在可信环境中导入用完立即从内存中擦除。密钥长度的选择也值得说。安全强度由n的二进制位数决定当前主流是2048位或3072位某些高安全场景用4096位。位数翻倍带来的计算开销接近指数上升但安全性收益却不是线性增长这里需要根据业务场景做取舍。我用一张表把这几个核心参数的角色压缩一下参数 | 公开还是保密 | 作用 | 约束条件 p, q | 保密用后即焚 | 计算n和φ(n)的唯一入口 | 大质数随机独立位数相近但数值相差远 n | 公开 | 加解密模数 | npq不能被分解 φ(n) | 保密 | 计算d的必要条件 | 等于(p-1)(q-1) e | 公开 | 加密指数 | 与φ(n)互质常用65537 d | 私密 | 解密指数 | e在模φ(n)下的逆元4. 加解密互为逆运算的核心证明欧拉定理如何撑起整个RSA有了密钥生成流程下面回答开头的问题为什么C^d mod n就能还原M。加密过程记作C M^e mod n解密过程是M C^d mod n。代入C实际要证明的是M^{ed} ≡ M (mod n)由于d满足ed ≡ 1 mod φ(n)所以存在整数k使得ed kφ(n) 1。现在分两种情况。**情况一gcd(M,n)1即明文与模数互质。**这种情况最干净。直接用欧拉定理M^{φ(n)} ≡ 1 (mod n)两边同时做k次方再乘一个MM^{kφ(n)1} ≡ M (mod n)于是M^{ed} ≡ M (mod n)解密成功。**情况二gcd(M,n)≠1。**明文恰好是p或q的倍数或者同时是p和q的倍数。这种情况概率极低但要做严格证明必须覆盖。先看M是p的倍数但不同时是q的倍数的情况。从模p的视角看M^ed ≡ 0 ≡ M (mod p)这一侧成立。从模q的视角看因为gcd(M,q)1并且q是质数可以用费马小定理M^{q-1} ≡ 1 (mod q)。由于ed-1kφ(n)k(p-1)(q-1)指数部分恰好包含(q-1)因子所以M^{ed} ≡ M^{k(p-1)(q-1)1} ≡ M (mod q)也就是说M^ed和M在模p下同余也在模q下同余。由于p和q互质根据中国剩余定理必然有M^ed ≡ M (mod pq)也就是mod n下同余。这个证明的关键在于把模n的难题拆成模p的平凡问题和模q的费马小定理问题然后用中国剩余定理拼回结果。把两种情况的证明合起来有一句值得反复咀嚼的话RSA加解密在任何情况下都正确是欧拉定理在互质情形下的应用以及费马小定理配合中国剩余定理在不互质情形下的兜底。不理解这个橙色边界等于没真正学过RSA。为了确保你不是只看不练我给出一个极小规模的可验算例子取p3q11n33φ(n)20。选e3gcd(3,20)1解3d ≡ 1 (mod 20)得到d7。明文M5加密5^3125125 mod 33 26。解密26^7。手动算26^726^2676≡16 mod 3326^4≡16^2256≡25 mod 33所以26^726^4×26^2×26 ≡ 25×16×26 mod 33。25×16400≡44×26104≡5。返回5完全正确。真正生产环境中不会这么手动算而是用快速幂取模把指数拆成二进制逐位处理复杂度从O(e)降到O(log e)。这也是RSA在计算上可行的原因之一。5. 部分重要推论从解密正确性延伸出来的几个关键结论标题里写了部分推论这里我挑四个个人认为最实用、也最容易被忽略的展开讲。推论一中国剩余定理可以把私钥运算提速约4倍。私钥持有者知道p和q因此可以把解密运算M C^d mod n拆成两条路并行计算先用d_p d mod (p-1)计算M_p C^{d_p} mod p再用d_q d mod (q-1)计算M_q C^{d_q} mod q最后用中国剩余定理从M_p和M_q合并出最终的M。原因在于解密正确性依赖的是模p-1的指数周期和模q-1的指数周期而CRT允许我们分别处理较小的模数p和q。更小的模数意味着更快的模幂运算两个子问题并行后整体提速通常接近4倍。所有生产级RSA实现几乎都默认开启CRT。但这也带来了一个新的安全要求如果CRT过程中某个中间结果出错比如内存翻转攻击者有可能通过错误结果反推出p。所以涉及私钥的硬件或软件都会加入结果校验一旦发现错误就拒绝输出。推论二RSA具有乘法同态性质。这个推论直接来自模运算的乘法性质E(m1)·E(m2) (m1^e·m2^e) mod n (m1·m2)^e mod n E(m1·m2)也就是说两段密文相乘再解密等价于两段明文的乘积。这个性质听起来很酷实际上是一把双刃剑。它可以用来构造盲签名场景签名者在不看到原始消息的情况下对消息的可信版本签名。但反过来攻击者可以利用同态性对密文做变换在不解密的情况下操纵明文内容。所以裸RSA绝不能直接用于加密真实业务数据必须加上填充方案比如PKCS#1 v1.5或OAEP填充的目的之一就是把乘法同态性破坏掉。推论三公开指数e较小的时候存在低指数攻击窗口。假设e3且用PKCS#1 v1.5之前的教科书式RSA如果三条不同消息的密文都满足C_i M_i^3 mod n_i不同模数且M^3比n_i小得多攻击者可以用中国剩余定理合并三条密文得到一个精确的立方值然后开立方还原M。这就是Håstad广播攻击的基本思路。现代实现里e65537本身已经足够大加上填充方案会让明文空间随机化这类攻击的窗口基本被堵死。但理解这个推论还是很有价值的指数和模数的组合不能只看单方安全性还要看数学结构上的耦合风险。推论四在不知道d的情况下已知e和n破译RSA的难度等价于分解n的难度。这句话是RSA安全性的基石。严格表述是如果能分解n得到p和q就能算出φ(n)并解出d这是充分方向反方向也成立如果已知一对(e,d)存在一个随机化算法可以大概率分解n。这意味着求私钥和分解大整数在计算复杂度上是等价的RSA的安全性就归约到大整数分解问题上。目前对2048位模数最有效的通用分解算法是数域筛GNFS运行时间随位数呈亚指数增长这也是为什么2048位至今仍被认为是安全底线。6. RSA的安全边界知道什么就能破解什么以及明文填充的必要性RSA告诉我们一个反直觉的事实**公钥能加密私钥能解密但公钥本身不能推出私钥。**要做到这一点除了前面讲的数学原理还有一条隐藏的边界需要理解。假设攻击者拿到n、e以及一条密文C攻击路径有哪些第一是分解n。这是最直接、也是最难的路径。如果n只有512位现代电脑几分钟就能分解1024位需要专用设备2048位目前被认为不可行。所以密钥长度的本质是把分解难度推到计算力边界之外。第二是直接求d。由于d满足ed ≡ 1 mod φ(n)而φ(n)(p-1)(q-1)一旦p、q未知就没有φ(n)求逆元无从谈起。所以保住p、q就是保住了整个私钥体系。第三是硬解模幂方程C M^e mod n。这被称为RSA问题目前没有已知的多项式算法可以求解且大量研究表明该问题与分解问题近似等价。但这里有一个经常被忽略的边界RSA保护的是私钥的不可推导性不保护明文的任何结构特征。如果业务方在加密前不处理明文直接在数值上做M^e mod n那么同一段明文反复加密会得到同一段密文频率分析就能泄露信息。更严重的是攻击者能利用同态性构造可预测的变换。解决方式就是填充。以OAEP最优非对称加密填充为例它的思路是把明文M与一组随机数混合进行两次哈希扩展后再送入RSA模幂。解密端先做模幂再逆推填充结构最后检验填充是否符合预期。如果填充校验失败解密端应返回错误而不暴露任何部分信息。这避免了密文的可预测性也让同态性质不再成为攻击面。我在项目里见过最常见的两个RSA误用一个是直接把字符串转成整数加密不加填充另一个是在签名场景中错误使用加密填充方案而不是PSS签名填充。前者会让密文模式可预测后者则可能导致某些标准库在验证签名时报错甚至在极端情况下引发签名伪造风险。实际使用中还有一个容易踩的坑私钥文件格式。现在业界普遍使用PKCS#8封装私钥但很多老系统还在用PKCS#1的裸RSA私钥格式。两者在ASN.1结构上的差异导致跨语言、跨平台解析经常出现私钥加载失败。一次我在给某跨平台系统对接时对方用A语言生成私钥B语言怎么也读不进来最后排查出就是格式前缀和嵌套结构不匹配。遇到这种问题不要怀疑算法先检查密钥格式。密钥轮换和过期策略同样重要。RSA不存在加密一次永久安全这回事。一方面量子计算发展让Shor算法成为远期威胁当前业界正在逐步切换到后量子密码标准另一方面如果某个服务器的私钥在日志中被意外记录唯一止损方式就是在最短时间内吊销证书、重新生成密钥。我们内部的做法是密钥有效期不超过一年并配合独立的硬件密钥存储确保持久性密钥材料不落盘。整体回顾一下RSA的核心链条始终围绕欧拉定理展开密钥生成时用φ(n)构造逆元加解密时用欧拉定理保证指数抵消安全性分析时用分解困难性兜底。把这条链条拆透之后你会发现任何RSA相关的应用层决策——密钥长度、填充模式、CRT开关、生命周期管理——都能回到数学原理上找到依据。最后分享一个个人经验。当年我为了验证自己是不是真懂写了一个极简的Python实现连CRT都不加手写扩展欧几里得和快速幂。用61和53生成一个3224位的n加密解密跑通的那一刻我才敢说自己理解了RSA。建议你也做一次这样的手工验算用纸笔走到3036位一下的规模就够不要急着上2048位。数学原理这关过了后面用任何语言的RSA库都不会再是调包侠。