RSA这个算法估计是学过密码学、搞过后端、碰过安全审计的人绕不开的一个名字。但大多数人聊到这里都停在同一个层面公钥加密、私钥解密、原理就是大数分解。这套话本身没错可真到了要你解释“为什么公钥加密后私钥能解”“密钥长度为什么要设2048”“解密失败常见原因有哪些”的时候很多人就开始打磕巴。这篇东西我用做项目的方式重新梳理一遍RSA从欧拉函数到CRT加速从教科书公式到工程填充把数学推论和实战踩坑放在一起说。适合刚接触密码学的同学也适合想彻底搞明白再动手实现或配置RSA的开发者。1. RSA在解决什么问题1.1 从对称加密的“钥匙分发”说起对称加密的问题在于双方得先共享同一把钥匙。你有一个文件要传给对方如果钥匙也通过网络发给对方中间人截获了钥匙后续加密就形同虚设。你可以走线下送钥匙但场景一多、人一多线下分发成本高得吓人。RSA的价值就在于它把“加密钥匙”和“解密钥匙”拆成两把不同的钥匙一把公开谁都能拿一把私有只有自己留着。别人用公开的那把锁把消息锁进保险箱只有你手里的私有钥匙能打开钥匙本身根本不需要传递。实际工程里RSA通常也不是用来加密大段数据的。它更常见的角色是“密钥交换的搬运工”先用RSA把一个临时的对称密钥安全传过去之后双方用对称加密处理海量数据。原因后面会讲RSA慢对称算法快混合使用才是正经做法。1.2 单向函数锁好造钥匙难配RSA的安全直觉可以用一个“锁”的比喻理解把锁扣上任何人都能在一秒内完成但被锁住了之后想凭锁本身做出一把能开锁的钥匙几乎不可能。数学上RSA对应的单向操作是大整数乘法你知道两个大素数p、q把它们乘起来得到n只需要一次乘法但反过来拿到一个上千位的n要拆回p、q目前没有多项式时间的算法只能靠暴力分解加各种优化。这个不对称性就是所有RSA安全性讨论的出发点。但光有单向还不够还得给合法持有者留一条“后门”持有p、q的人可以轻松从n反推出一整套解密参数。这条路就是陷阱门。RSA的陷阱门藏起来的那条路正是后面要推导的欧拉函数和模逆元。没有陷阱门的单向函数只能用来做哈希不能用来构造可逆加密RSA巧妙的地方在于这个门不是凭空出现的而是基于素因子分解的知识谁掌握p、q谁就掌握门。1.3 一个可以手算验证的小例子为了后面推导不悬空先用一组很小的参数走一遍流程。取p61、q53则n3233φ(n)60×523120。选e17满足gcd(17,3120)1再用扩展欧几里得算出d2753因为17×27534680115×31201。公钥就是(3233,17)私钥是(3233,2753)。现在要加密消息m42c 42^17 mod 3233 2557 m 2557^2753 mod 3233 42这个例子里的数字很小真的可以手算或写几行代码验证。真正使用时的密钥长度是2048位这里的例子只是为了让你对“加密和解密都只是模幂运算”这件事有一个体感。2. 数学地基与核心推论2.1 模运算、同余与互素三个基础概念必须先铺一下。模运算就是取余数时钟上的13点其实就是1点因为13 mod 12 1。这里所有计算都在模n的范围内结果永远小于n这对加密结果的长度是个硬约束后面讲解密失败时会用到。同余记为a ≡ b (mod n)意思是a和b除以n的余数相同。互素就是最大公约数为1记为gcd(a,b)1。这些概念看起来简单但RSA里几乎所有推导都在它们之间打转尤其“互素”决定了能不能求逆元这是生成密钥的关键前提。我可以先把结论放在这里在模n世界里如果某个数和模数互素它必然存在一个逆元也就是能找到一个数相乘后余1这个事实是整个私钥生成算法的根基不理解它后面看d的计算会一头雾水。2.2 欧拉函数为什么φ(n)等于(p-1)(q-1)欧拉函数φ(n)定义为1到n之间与n互素的正整数个数。对素数p来说1、2、...、p-1全和p互素所以φ(p)p-1。当npq是两个不同素数的乘积时我们可以这么数从1到n-1一共有pq-1个数其中是p的倍数的有q-1个是q的倍数的有p-1个这两个集合在1到n-1范围内不会重合因为重合点是lcm(p,q)pq已经超出范围。因此φ(n) (pq - 1) - (q - 1) - (p - 1) (p - 1)(q - 1)这就是RSA初始化时最常看到的公式。φ(n)是一个必须严格保密的值因为它和e直接决定了私钥d一旦泄露任何人都能算出私钥。2.3 欧拉定理整个正确性证明的地基欧拉定理说若gcd(a,n)1则a^φ(n) ≡ 1 (mod n)。直观理解模n的互素剩余类在乘法下构成一个群这个群的元素个数是φ(n)个任何一个元素a反复乘自己其“周期”必然能整除群的大小φ(n)所以乘φ(n)次后回到单位元1。当n是素数时φ(n)n-1欧拉定理就退化成费马小定理a^(n-1) ≡ 1 (mod n)。这个定理的价值在于它让我们能够在指数上做“模φ(n)”的约简。RSA解密正确性的全部关键就是把这个约简用在加密和解密的复合运算上。2.4 RSA正确性的完整推导现在可以把整条逻辑串起来了。密钥生成时我们选择e满足gcd(e, φ(n))1然后计算d使得e × d ≡ 1 (mod φ(n))即 e × d k × φ(n) 1加密是c m^e mod n解密是c^d mod n。把两步合起来c^d ≡ (m^e)^d ≡ m^(ed) ≡ m^(k·φ(n)1) (mod n)若gcd(m,n)1直接用欧拉定理m^φ(n) ≡ 1 (mod n)于是上式等于m。那m和n不互素怎么办标准证明里很多教材一笔带过这里补全。因为npq且mnm和n不互素只有两种情况p|m但q不整除m或q|m但p不整除m。以第一种为例在模p下左边右边都是0恒成立在模q下因为gcd(m,q)1欧拉定理在素数q上继续适用于是m^(kφ(n)1) ≡ m (mod q)也成立。两边分别同余再由中国剩余定理可以推出两边在模n下也同余。这就是“m可能和n不互素时RSA依然成立”的完整说明。这个推导建议自己写一遍尤其是最后不互素的那一段。写一次之后才算真正理解RSA为什么是对的而不是死记公式。3. 密钥生成从选素数到私钥参数3.1 大素数怎么来概率素性检测与安全约束生成RSA密钥的第一步是随机挑两个位长相同的大素数p、q。2048位密钥对应1024位的素数随机取到这个数的概率极低所以真实流程是“随机猜测概率素性检测”。工程里用的检测算法可以在很短时间内把合数判掉对素数给出带误判概率的“通过”。实际库通常会做多轮不同基底的测试把误判概率压到极低再配合一些确定性的小因子预筛速度很快。生成素数时还有几个隐含约束。第一p和q的差值不能太小否则攻击者可以用费马分解法从√n附近开始暴力搜索很快拆出因子。很多库会检查|p-q|是否大于某个阈值比如2^(keylen/2-100)。第二p-1和q-1不能只有很小的素因子否则可能受到基于p-1光滑数的分解攻击。现代随机生成的大素数基本满足这个条件但自实现时要明白这些检查不是多此一举。3.2 计算n和φ(n)以及公开参数选定p、q后计算n p × q φ(n) (p - 1) × (q - 1)公钥是(n, e)私钥最核心的部分是(n, d)。注意φ(n)只在生成阶段使用算完d后应当立即从内存中擦掉。这个值一旦泄露攻击者可以解出d。很多新手自己写RSA工具时把φ(n)写进日志或者存进配置这是非常危险的坏习惯。3.3 公钥指数e为什么是65537e的选择标准是1 e φ(n)且gcd(e, φ(n))1。理论上可以选任意满足条件的数工程实现几乎全部选65537也就是2^161。选它有三个好处它是素数和φ(n)不互素的概率极低二进制表示只有两个1做模幂运算比随机指数快很多它足够大能规避早期用e3带来的小指数攻击。小指数攻击的意思是如果e3且明文m很小没有填充m^3甚至比n还小直接对密文开三次方就能还原m。65537从根源上把这类问题挡在门外。3.4 用扩展欧几里得算私钥d私钥指数d是e在模φ(n)下的乘法逆元。求模逆元的标准算法是扩展欧几里得算法既然gcd(e, φ(n))1我们可以通过辗转相除找到s、t使得e × s φ(n) × t 1那么s就是我们要的d如果为负取模φ(n)为正即可。算法本身不复杂但值得自己实现一遍。它做的是在辗转相除过程中不断回溯系数最终在gcd为1时把系数组合出来。你如果只在数学课上看过辗转相除可能会觉得这里跳了一下建议手推一遍17和3120的扩展过程大概几轮就能得到系数。def egcd(a, b): if b 0: return (a, 1, 0) g, x, y egcd(b, a % b) return (g, y, x - (a // b) * y) def modinv(a, m): g, x, _ egcd(a, m) if g ! 1: raise ValueError(a 和 m 不互素) return x % m用前面例子验证modinv(17, 3120)会得到2753。这一步如果没有先验证gcd(e, φ(n))1modinv会直接抛异常这也是自实现RSA时最常见的一类报错。3.5 真实私钥文件里为什么还有CRT参数用命令行工具生成密钥后看私钥结构会看到一堆额外字段prime1、prime2、exponent1、exponent2、coefficient。它们分别是p、q、d mod (p-1)、d mod (q-1)、q^{-1} mod p。这些参数不是多余的而是为了解密加速也就是常说的CRT解密。后面有一章专门讲这里先记住标准私钥里包含这些参数是正常的去掉它们虽然还能解密但性能会差很多。实际生成命令很简单openssl genrsa -out private.pem 2048 openssl rsa -in private.pem -pubout -out public.pem openssl rsa -in private.pem -text -noout第三条命令会打印私钥的完整参数结构适合用来对照理解。4. 教科书RSA和工程RSA是两件事4.1 为什么不能直接用裸公式前面推导的加解密公式叫“教科书RSA”。它的最大问题是确定性同一个明文永远产生同一个密文。攻击者只要准备一个常见明文表比如可能的金额、用户名、协议头加密后对着表比较就能猜出密文对应内容。这还是最轻的攻击更严重的是乘法同态性质和低指数组合攻击。工程里的RSA消息必须经过随机化填充让相同明文在不同次加密中得到不同密文。这是RSA使用中最重要的一条规则很多新手一上来直接把公式写成代码去加解密业务数据迟早出事。4.2 主流填充方案PKCS#1 v1.5与OAEP目前见到最多的两种填充方案是这样的。PKCS#1 v1.5加密结构是0x00、0x02、若干非零随机字节、0x00、明文随机字节最少8个字节。它实现简单但历史上出过著名的填充预言攻击安全实现必须非常小心错误处理逻辑最好用常数时间比较。OAEP是新推荐的选择它先用哈希和掩码生成函数把明文混合成类似随机数的块再做RSA运算解密端先做逆变换再取明文能够抵抗选择密文攻击。能选OAEP就选OAEP。填充类型随机化明文长度上限(k字节)安全性表现适用场景NoPadding无k差仅教学演示PKCS#1 v1.5有k-11可用但需谨慎实现兼容老系统OAEP有k-42左右好新系统首选实际命令里用命令行工具加密数据可以显式指定填充模式openssl pkeyutl -encrypt -pubin -inkey public.pem -pkeyopt rsa_padding_mode:oaep -in plain.txt -out cipher.bin openssl pkeyutl -decrypt -inkey private.pem -pkeyopt rsa_padding_mode:oaep -in cipher.bin -out plain_back.txt4.3 签名不是“私钥加密”每次有人把数字签名说成“用私钥加密”我都想纠正一下RSA签名在数学形式上确实是私钥指数运算但工程算法完全不是加密的逆过程。标准签名流程是先对消息做摘要哈希例如SHA-256然后对固定格式的摘要做RSA私钥运算验签方先算同一哈希值再做公钥运算提取出摘要并比对。这样做的原因有三个RSA只能加密有限长度真实消息可能任意长直接对整条消息做私钥运算会把消息内容暴露给能拿到公钥的任何人等于用公钥解密了签名没有任何保密性先哈希可以让签名固定长度并防范结构化攻击。签名方案上新系统优先考虑PSS它的安全证明更完整老系统常见的是PKCS#1 v1.5签名。4.4 公钥加密和签名场景不要混用公钥加密的适用场景是别人想给你发私密消息用你的公钥加密。签名的适用场景是你想证明一条消息确实出自你之手任何人可以用你的公钥验证。加密保护的是保密性签名保护的是完整性和不可否认性两者虽然共用同一套RSA参数但在密钥用途、填充方案、消息处理方式上都不同。混用会引入交叉攻击正确做法是给一对密钥明确一个用途或者不同用途分配不同密钥。5. 性能、瓶颈与CRT加速5.1 RSA慢在哪RSA的核心计算是模幂也就是反复做2048位整数的乘法和取模运算一次私钥操作要跑几千次这样的乘法。AES做的是128位分组内字节级的置换和混合还支持硬件指令集加速。两者完全不是一个量级。我实测下来一台普通笔记本上RSA公钥加密一次大概零点几毫秒私钥解密一次几毫秒AES在硬件加速下每秒能处理几个GB。这就是为什么实际系统不会用RSA直接加密大数据而是用RSA传对称密钥再用对称算法加密内容。5.2 快速模幂算法平方-乘计算m^e mod n最直接的做法是把m乘e次e是2048位的数这个方案不可能实现。平方-乘算法把e写成二进制逐位处理遇到当前位是1就把结果乘上当前的base每处理一位都要把base平方。这样乘法和平方的总次数和e的位数同阶也就是几千次而不是2^2048次。def mod_pow(base, exp, mod): result 1 base % mod while exp 0: if exp 1: result (result * base) % mod base (base * base) % mod exp 1 return result这也是为什么e选65537更划算它的二进制只有两个1运算量更小。d没有任何特殊结构平均一半的位上都有1所以私钥运算天然比公钥运算慢。5.3 CRT如何让解密快四倍左右中国剩余定理可以用在RSA解密上。解密计算m c^d mod n其中d很大。如果只算模p和模q的结果因为p、q只有半个n的位数每个模幂的成本会大幅下降最后再合并结果。用预先算好的dp、dq、qinvdef rsa_decrypt_crt(c, d, p, q): dp d % (p - 1) dq d % (q - 1) qinv pow(q, -1, p) m1 pow(c, dp, p) m2 pow(c, dq, q) h (qinv * (m1 - m2)) % p return m2 h * q最后返回的m2h*q就是明文m。原理不复杂m2是m模q的结果h×q只影响模p的余数不影响模q的余数所以组合出来的值在模p和模q下都正确由中国剩余定理保证它在模n下唯一落在0到n-1之间后就是明文。密钥里那些CRT参数就是为了每次解密省去算dp、dq、qinv的时间。同样大小密钥下CRT解密的整体耗时大约是非CRT解密的四分之一这也是为什么标准私钥结构里要存这些参数。5.4 关于性能测速的一个小提醒别拿特别小的消息去比较RSA加密和AES加密然后得出结论说RSA也很快。RSA单次操作毫秒级AES单次操作微秒级都不到差距是三个数量级起步。性能优化上最有效的不是去抠模幂代码而是调整系统架构让RSA只处理短密钥大数据全部走对称加密解密场景都用CRT参数公钥操作如果极高频可以考虑硬件加速设备或者预计算。这些比手写底层模幂划算得多。6. 常见问题与排查技巧实录6.1 解密失败和字符串问题解密失败十有八九是下面几类。现象可能原因定位手段解出来乱码密文把二进制的原始字节当成字符串处理转Base64传输别直接读字节流工具报data too large加密明文长度超过当前密钥和填充允许上限改用混合加密或换更长密钥解密或验证失败加密和解密用的填充模式不一致统一为OAEP或统一为PKCS#1 v1.5解密成功但结果是错的公钥和私钥根本不是一对用同一密钥对做一次已知明文自测程序报invalid padding密文损坏或填充结构不对检查密文完整性别忽略异常经典场景是加密方把密文存成了字符串再解密时转回字节字节序列已被破坏。密文应用Base64编码做文本传输或者直接存二进制文件。另外RSA单次能加密的最大字节数是固定的2048位密钥下PKCS#1 v1.5最多245字节OAEP更少一些。超过上限的正确做法是拆块或改用对称算法强行截断明文会让解密数据面目全非。6.2 安全配置上的老坑小指数攻击和共模攻击在我接触过的旧系统里都真实出现过。小指数攻击发生在e3且明文短没有填充时密文直接开三次方就是明文。共模攻击则更隐蔽多个用户共用同一个n只是e和d不同当同一个明文用两组公钥加密时攻击者结合两个密文可以在不知道私钥的情况下恢复明文。解决办法就是开头说的随机填充以及永远不要在不同密钥对之间共用n。另外密钥长度小于2048的旧密钥要尽快淘汰512位密钥在现代工具下几分钟甚至几秒钟就能分解768位也在多年前就被实际分解过这不是理论风险而是现实风险。6.3 自实现RSA的几道红线如果只是为了学习自实现一遍RSA非常值得但有几条红线必须遵守。第一生成素数不要用普通随机数库的随机方法它不够安全攻击者可以通过预测种子猜出私钥。要用密码学安全随机源比如操作系统的安全随机接口。第二生成后必须验证p和q是否满足安全距离不能拿来就用。第三算完d后要销毁φ(n)不给日志留机会。第四业务系统不要直接用教科书式无填充RSA至少要用标准库的OAEP或PSS方案。第五不要自己实现底层的模运算和素性检测用于生产环境成熟密码库已经经过大量安全性审查重复造轮子出问题的概率远高于收益。6.4 排障时最实用的一组命令手头有一套私钥和公钥先确认它们是否匹配最直接的办法是做一个加解密闭环echo hello test.txt openssl pkeyutl -encrypt -pubin -inkey public.pem -pkeyopt rsa_padding_mode:oaep -in test.txt -out test.enc openssl pkeyutl -decrypt -inkey private.pem -pkeyopt rsa_padding_mode:oaep -in test.enc -out test.dec cat test.dec如果这句能通过说明密钥对本身没问题问题大概率出在应用层的编码、填充参数或数据处理。再用openssl rsa -in private.pem -text -noout看一眼密钥长度和CRT参数是否存在很多性能问题一眼就能看出来。最后分享一点个人经验我现在审查一个系统里的RSA使用基本只看三件事密钥长度是不是至少2048填充方案是不是OAEP或PSS私钥是不是放在受保护的硬件或密钥管理服务里。这三件事如果都做到系统的安全底线就已经立住了。至于密钥生命周期管理也要纳入日常巡检过期、泄露、更换流程这些细节才是真正决定一套密码系统能不能长期可靠运行的关键。
