RSA没破？但密钥生成、填充与侧信道三层命门必须守

干这行久了每隔一阵就能看到“RSA 被破”的标题几乎成了密码学圈的保留节目。作为实际部署过不少公钥体系的人我先把话说清楚RSA 的数学内核也就是大整数分解问题到今天依然没被公开推翻真正让我在代码和协议里反复踩坑的是一堆围绕 RSA 的“结构命门”。这篇文章就把我这些年看到的、验证过的、以及做密钥审计时最先检查的那些命门按密钥生成、填充、侧信道和迁移四个角度拆开来讲。如果你正在用 RSA 做签名、加密或密钥交换哪怕不是专职密码学也值得花十几分钟过一遍。1. 先说结论RSA 到底破没破1.1 “破解”这件事先把定义对齐聊“RSA 破没破”最先要做的不是翻论文而是把“破解”两个字对齐。我看到的大部分“RSA 被破解”新闻其实说的是某台设备私钥被提取、某个协议被绕过、某个随机数生成器出了问题。这些属于实现层面的攻破和“在数学上找到一种通用算法从 n 算出 p 和 q”完全是两码事。前者年年发生后者至今没有公开验证过的例子。从我接触过的安全审计经验来看真正被拿下的 RSA 系统九成以上都不是败在数论而是败在周围环境密钥生成时随机源太弱、填充实现返回了不该有的错误差异、解密时间随私钥位变化而产生波动。这些攻击有一个共同点它们利用的是 RSA 这个数学结构在被工程化之后留下的缝隙而不是 RSA 的数学假设本身出错。也正因为这样我对“结构命门”的定义很窄不是某个能让你一键分解 2048 位模数的秘密而是 RSA 在被实现和使用时那些反复被命中的结构性弱点。标题里说“我不能说”其实是两层意思。第一层如果我真有能破 RSA 数学结构的算法应该去发论文而不是来写博客第二层我能拿出来说的弱点早都在公开文献里写了很多年并不存在“只有我知道”的秘密。真正稀缺的是把这些已知弱点落实到密钥生成、协议填充和工程实现里的纪律。1.2 数学地基大整数分解难题还站在那儿RSA 的算法结构很简单选两个大素数 p 和 q算 n p × q再选公钥指数 e通常取 65537生成私钥指数 d满足 e × d 对 (p-1)(q-1) 取模等于 1。加密时算 c m^e mod n解密时算 m c^d mod n。这个体系的全部安全性压在“给你 n在合理时间内找不到 p 和 q”这个假设上。只要分解 n 很快私钥 d 马上就能算出来。经典计算下大整数分解最好的公开算法是亚指数级别不是多项式级别。这意味着 n 每增加一些位数分解难度会以远超线性的速度增长。512 位模数在很久以前就能被分解768 位模数在十几年前也有过公开的分解记录1024 位模数到今天依然没有公开分解记录但业界认为它的安全余量已经不够宽裕不少合规要求都把它列为不可接受。2048 位是当前最常见的选择在经典计算模型下仍被广泛认为处在安全边界以上对长期敏感数据越来越多的人开始往 3072 位甚至更高走。新手容易混淆一点RSA 的“密钥长度”不是指私钥文件里有几个字符而是指模数 n 的二进制位数。生成 RSA 密钥时真正的成本大头是找两个大约 n 一半长度的素数不是随便填一段随机字节。公钥本身包含了 n 和 e所以公钥文件通常比私钥小很多但从公钥文件里看不出 p、q更不可能直接倒推出私钥指数。1.3 那“结构命门”到底指什么如果要给 RSA 的结构命门做一个归纳我会分成三层。第一层是密钥生成层。随机源不够好、素数的选取方式有问题、模数之间存在共享因子这些会让本应不可分解的 n 在数学上“看起来没问题、实际上弱得离谱”。第二层是协议和填充层。教科书 RSA 的代数结构太干净同样的明文永远得到同样的密文密文之间还存在乘法同态如果不加合适的填充方案加密体系就会被各种非常规操作钻空子。第三层是物理实现层。就算 n、e、d 都完全正确私钥在解密过程中也会通过时间、功耗、电磁辐射、缓存命中等通道悄悄流出。这三层任何一个出问题攻击者都不需要碰“大整数分解”这座大山。后面几节按这三层展开最后一节聊量子计算对 RSA 的长期影响。每个部分我都尽可能给出可以落地的观察和检查方法而不是只把公式念一遍。2. 密钥生成第一道也是最重要的命门2.1 随机数质量一个坏随机源毁掉一切密钥生成阶段最容易出的问题是随机数质量。RSA 密钥的安全性依赖两个素数不可预测而素数来自随机数生成器。随机数生成器一旦熵不足或者被植入确定性逻辑攻击者就可以从几万个公钥里猜出私钥甚至不需要和服务器有交互。这类问题在真实世界反复出现过一台设备、一批证书、一个版本的随机数库出问题就可能感染整片生态。我审计时第一件事就是确认密钥是在哪里生成的用了什么随机源。常见服务器系统上用户态程序通常不应该自己去“设计”随机数生成逻辑应该直接使用系统内核提供的安全随机接口或者使用成熟密码学库的高层接口。那些为了“提升性能”而手动给随机数生成器加种子、缓存熵、在虚拟机上复制镜像造成完全相同随机状态的做法都是高危操作。给一个小技巧批量生成密钥时把几个公钥拿来做对比如果发现大量模数 n 相同或者存在公共因子基本可以确定随机源出了问题。后面第 5 节我会给一个简单的批量检测脚本。另外生成私钥文件的机器如果本身就是被入侵过的环境那一切随机数讨论都白搭所以密钥生成尽量在受控机器上离线完成。2.2 模数结构p 和 q 的“近亲问题”第二类命门藏在素数的“形状”里。RSA 模数 n 是 p 和 q 的乘积如果 p 和 q 靠得太近n 就会很接近某个完全平方数。这种情况下有一种基于平方差展开的分解思路会很好用把 n 写成两个平方的差利用“两数之差”还原出 p 和 q。素数位数越大p 和 q 之间的距离越难保证所以随机生成时如果不小心约束了范围就可能埋下结构性隐患。这不是只存在于纸面的理论。真实环境中如果密钥生成逻辑让两个素数都从同一个很窄的区间里选取p 和 q 的差值就会很小分解门槛低到连普通开发者都能在合理时间内完成。为了避免这类问题行业共识是让 p 和 q 各自独立地、从完整的可用空间里随机选取并且在生成后检查它们的长度和差值。另外还有一个容易被忽视的问题p-1 和 q-1 的因子结构。某些分解方法对比较“光滑”的 p-1 或 q-1 格外有效如果 p-1 由很多小素数因子组成就能被加速分解。现代密钥生成库一般会通过随机挑选足够大的素数来规避这类情况但如果你看到了那种“手写 RSA 生成器”的代码务必检查它是否只验证了 p 和 q 是素数而没有验证它们的随机性和边界条件。这里的结论是用成熟库别自己拼装参数。2.3 指数选择不是随便挑个数字就行RSA 里有两个指数公钥指数 e 和私钥指数 d。常见的 e 是 65537这个选择有数学上的理由它足够大能抵抗一些针对小指数的攻击它又与 (p-1)(q-1) 互素的概率很高很少需要重试同时它的二进制表示里只有两个 1做模幂运算时比较高效。相比之下e 3 虽然计算更快但在教科书式使用场景下会把某些特殊明文结构暴露给攻击者。看到公钥里 e 是 3 或 5 时我会直接把它标记为风险项。私钥指数 d 同样不能太小。如果 d 的位数远小于 n攻击者可以利用连分数展开从公钥信息逼近私钥这类小私钥指数攻击很早就有公开结果。标准流程里 d 是通过 e 对 (p-1)(q-1) 求逆得到的通常和 n 接近同长所以正常生成不太会翻车真正需要注意的是手写密钥生成逻辑时有没有在求逆之后对 d 做长度验证。最后提醒一个经常被忽略的合规点不要在多套系统里复用同一个私钥或模数。复用模数会让任何一个知道这个公钥的人永远拥有解密权限如果两个不同公钥共享一个素因子攻击者只需要一次最大公约数计算就能分解出两个模数。这个看起来不像“算法”的问题其实在批量设备场景里是最现实的结构命门。3. 填充与协议别把教科书 RSA 当成品3.1 教科书 RSA 的三个坏习惯很多刚接触 RSA 的人看到的公式只有 m^e mod n 和 c^d mod n于是以为“加密就是直接对明文算幂”。这么做出来的东西在密码学上叫教科书 RSA离可用成品差着一整个填充层。直接裸算的问题有三个。第一同一个明文永远得到同一个密文攻击者可以建字典、做重放也能通过密文是否相同判断明文内容。第二RSA 有乘法同态性两个密文相乘的运算结果恰好等于对应明文相乘后的加密结果攻击者可以拼装出新的有效密文去诱导解密。第三密文本身可以被改写成各种变体如果系统只是简单解密并回显攻击者就能间接还原出明文。拿现实生活类比RSA 的数学内核像一只保险柜加密就是把东西锁进柜子。但教科书 RSA 这只保险柜有个毛病柜门上的锁孔可以被外面的人再插一根杆子进去把里面的东西重新排列。真正的协议设计必须再裹一层“信封”让外界看不到也碰不着内容的代数结构。这个“信封”就是填充方案。这也是我一直建议的原因不要在自己实现的通信协议里直接调用底层 RSA 原语而是使用成熟密码学库提供的“加密/解密封装”或“签名/验签封装”。封装里已经处理了填充、随机化、错误检查等细节比手写公式安全得多。3.2 从 v1.5 到 OAEP填充方案在跟什么对抗RSA 的填充方案经历过一个明显的演进。早期常见的 PKCS#1 v1.5 填充会规定密文解密后的结构比如明文前有一段固定格式的头部。问题在于一旦服务器对不同格式错误给出不同的返回信息攻击者就能把服务器变成一个判断“填充是否合法”的预言机。反复试探合法与不合法的边界最终可以从错误回答中一点点还原出明文。这种攻击在 1998 年就被公开提出来属于典型的“实现看着没问题、协议结构上有缝隙”的案例。后来业界主流转向 OAEP 这类随机化填充。OAEP 会把明文、随机盐和散列结果一起揉进一个带结构的块里再交给 RSA 运算。它的好处是加密相同明文时每次密文都不同而且密文的代数可塑性被大幅削弱攻击者很难再通过翻转几个比特来制造有意义的密文。再加上解密端对填充错误统一处理预言机攻击的空间就小了很多。不过要强调填充方案不是选对了就万事大吉。实现 OAEP 时标签、散列函数、随机数源都要保持一致解密失败后返回什么错误、耗时多久也都要尽量统一。有些库提供一个“伪造错误路径”的选项就是为了让攻击者无论如何都分不清失败原因这是我建议在服务端开启的加固点。3.3 为什么“预言机”类攻击屡禁不止预言机类攻击的本质是把“解密方对输入的反应”变成信息通道。这里的反应不只是报错文字还包括返回码不同、响应时间不同、连接是否重置、日志里有没有产生额外记录。哪怕这些差异只有一个比特大量采样之后也能被放大成可用的信号。现实里这类问题很难彻底消除因为协议层通常需要告诉调用方“这次操作成功还是失败”。一旦成功和失败的路径在耗时或返回上存在差异预言机就出现了。更麻烦的是有些业务逻辑会主动把差异暴露出来比如“证书解密失败”和“签名验证失败”返回不同的 HTTP 状态码。做安全审计时我会重点盯这些位置所有失败分支是否合并、是否加入了固定时延、是否做了统一的随机错误响应。给一个直接的工程建议解密或验签失败的返回不要区分“填充错误”“格式错误”“长度错误”统一成一个模糊的错误描述如果性能允许加上一个固定的最小响应时间把时间差抹平。RSA 的安全性不是只靠一条数学公式而是靠整个响应面都“滴水不漏”。4. 侧信道私钥不只在数学里也在时间轴里4.1 时间侧信道耗时差异是天然预言机第三层命门在物理实现。RSA 解密要做模幂运算而模幂运算通常是一位一位处理私钥指数 d 的比特。如果实现里用“判断当前位是否为 1是则多做一次乘法”的分支那么私钥中 1 多的位置就会比 0 多的位置慢。攻击者不需要知道私钥只要反复测量解密耗时就能逐步推测 d 的比特。这属于时间侧信道。缓解方法是常数时间实现让模幂运算无论私钥是什么都走同一套指令序列不做依赖私钥的分支跳转。现代密码学库普遍实现了常数时间的模幂、常数时间的比较但如果你在低端芯片上自己写 RSA很容易忽略这一点。一个经典检查方法用很多不同的私钥对同一批密文做解密统计耗时的方差如果耗时和 d 的权重有明确相关性就要立刻改造。另外解密流程里的填充检查和错误返回也要固定时间。否则就算模幂是常数时间填充错误返回得快、正确返回得慢照样成为一种时间预言机。我看到过不少库解决了幂运算却栽在错误分支的耗时上。4.2 功耗、电磁与缓存物理世界的读心术时间只是众多侧信道通道中的一条。在智能卡、手机安全芯片、甚至普通服务器上攻击者还可以通过功耗曲线、电磁辐射、缓存命中差异来推断内部状态。模幂运算里每个乘法和每个分支都有独特的功耗特征在共享 CPU 的环境里恶意租户可能通过缓存访问模式观察目标进程的查表操作是否把特定数据带入了缓存行从而恢复密钥位。对大多数软件工程师来说不需要亲自去采集功耗曲线但要知道为什么芯片厂商和安全库一直强调“盲化”。盲化的思路是每次运算前给密文乘一个随机数把真实运算对象藏进随机噪声里让攻击者看到的功耗和电磁波形与真实私钥操作解耦。像 RSA 这类公钥算法的标准实现基本都会做随机盲化这是代码里“多出的那几行乘法”的真正意义。如果你在采购安全硬件重点不是看它宣传的“硬件加密”而是看它有没有通过常见的侧信道攻击测试如果你在写软件串接 RSA至少要做到不用自己拼装模幂逻辑、不记录解密原始输入、不在日志里打印与错误类型有关的细节。4.3 工程自查常数时间到底在查什么一个简单实用的自查顺序是这样的。第一密钥生成有没有用安全随机源第二解密和签名路径里有没有明显的按私钥位跳转第三比较两个值比如校验和、认证标签时用了什么函数默认的字符串比较通常不是常数时间第四所有错误分支的返回耗时是否接近第五是否给每次 RSA 操作加了随机盲化。这五条不需要很深的理论逐条对着代码过一遍就能排查掉大部分真实侧信道漏洞。5. 实战视角批量审计与密钥自查5.1 批量公钥 GCD 检测为什么能挖出弱密钥在设备出厂、证书批量签发等场景里一个常见但隐蔽的命门是“两个模数共享素因子”。假设公钥 A 的模数是 p × q1公钥 B 的模数是 p × q2只要 p 在生成时被重复使用那么对两个公钥做一次最大公约数计算就能直接得到 p继而分解出两个模数。这就是批量公钥 GCD 检测的基本思想收集大量公钥两两求 gcd遇到大于 1 的公约数就说明这批密钥里存在共享因子。这不是攻击手法而是防御侧的审计手段。真实世界中凡是出现过“用同一个随机种子生成大量密钥”的产品事故事后都能靠这种方式快速确认受影响范围。审计人员只是用公开的公钥信息做数学上的“体检”不需要私钥也不需要入侵系统。我把这个检查放进常规动作之后几乎每次都能在历史遗留的证书堆里发现一批异常密钥。处理方式很简单把相关证书吊销用安全的随机源重新生成全部替换。这个动作看起来不起眼但它是成本最低、效果最明确的 RSA 结构加固之一。5.2 三步自查你的 RSA 密钥第一步确认密钥长度。用常见命令行工具生成一个 3072 位的 RSA 密钥命令如下openssl genpkey -algorithm RSA -pkeyopt rsa_keygen_bits:3072 -out rsa_priv.pem openssl rsa -in rsa_priv.pem -pubout -out rsa_pub.pem openssl rsa -in rsa_priv.pem -text -noout | head -n 20观察输出里的模数位长、公钥指数 e。正常情况下e 应该是 65537n 的位数要和预期一致。密钥文件生成后记得把私钥文件权限收紧到当前用户例如chmod 600 rsa_priv.pem。第二步检查公钥指数和模数特征。如果看到 e 是 3 这类小指数或者 n 的位长明显低于预期要立即更换。不同库输出格式有差别但核心字段就这几个人眼扫描就能发现明显异常。第三步运行批量 GCD 扫描。把收集到的公钥文件放到一个目录用下面的 Python 脚本做两两检查from pathlib import Path from math import gcd from cryptography.hazmat.primitives.serialization import load_pem_public_key pubkeys [] for path in Path(pems).glob(*.pem): pub load_pem_public_key(path.read_bytes()) pubkeys.append(pub.public_numbers().n) for i in range(len(pubkeys)): for j in range(i 1, len(pubkeys)): g gcd(pubkeys[i], pubkeys[j]) if g 1 and pubkeys[i] ! pubkeys[j]: print(f发现共享因子: key{i} 与 key{j}请立即吊销并重新签发)脚本只读取公钥中的模数 n不做任何私钥运算也不涉及网络流量。运行完以后没有输出基本可以认为这批公钥没有共享因子。如果输出了按 5.1 的流程处理即可。5.3 常见自查问题速查表现象可能原因建议处置密钥长度只有 1024 位旧版本默认参数或手动指定过小迁移到 2048 位或 3072 位公钥指数 e 为 3 或 5历史配置或手动选择小指数重新生成密钥使用 65537私钥文件权限为 0644生成后未收紧权限chmod 600并检查备份文件大量公钥模数相同随机源被复用或模板拷贝全部吊销重新生成解密失败信息区分“填充错误”和“格式错误”协议层直接透传异常统一为模糊错误增加固定时延解密耗时波动大模幂分支依赖私钥位改用常数时间库实现开启盲化这张表只是入门。真正做合规审计时还需要把密钥用途、证书链、日志保留等拉进来一起看但前三条是人人都能立刻动手的。6. 后量子时代RSA 的结构命门还能撑多久6.1 量子算法威胁的是分解还是结构聊 RSA 的未来绕不开量子计算。量子范畴内有一种算法能够在多项式时间内完成大整数分解这直接打击的是 RSA 的数学假设本身。一旦具备足够规模、足够低噪声的量子计算机出现2048 位甚至更长的 RSA 模数都会在法律意义上“可破”这是量变到质变级别的威胁。不过目前还不需要恐慌。业界对资源开销的估算普遍在数百万物理量子比特量级还要叠加纠错和容错设计目前的设备规模距离这个目标还很远。更值得警惕的是“先存储、后解密”策略攻击者现在就在大量抓取加密流量等未来算力成熟后再回头解密。对数据有效期长达十年、二十年的业务来说这个威胁不是未来的概念而是现在就必须开始规划的工程问题。从结构命门的角度看量子算法威胁的并不是 RSA 的某个填充实现或某个素数形状而是 RSA 扎根的分解难题本身。这意味着打补丁式的修复没法解决问题只能替换算法族。6.2 迁移思路先把“别用 RSA 硬扛”当成工程计划后量子迁移并不是一句“明天全换掉”的口号。现实里RSA 遍布在证书、签名、密钥交换、老旧设备固件里直接切换会产生兼容性灾难。比较稳妥的做法是混合模式在关键路径上同时部署经典算法和后量子算法两边各自独立只要其中一边没被攻破整个通道就依然安全。即便未来经典算法出现重大突破混合模式里另一条后量子腿仍然兜底。另一个思路是在密钥管理上提前做隔离。把长期数据的加密密钥和传输密钥分开定期轮换新签发的证书优先选用更强健的密钥类型让 RSA 只出现在兼容层和存量系统里。这样未来强制迁移时需要改造的范围会小很多。我个人在迁移评估里的体会是RSA 不会立刻消失但它会逐渐从“默认选项”退到“兼容选项”。密码学领域有个朴素规律一个算法的结构命门越多围绕它的工程约束就越重。RSA 的三层命门不是新发现只是它们每一个都需要你去认真对待而比“破解 RSA”更现实的问题是太多系统连这三层命门的第一层都没守住。最后说个我个人常对团队讲的小结论每次有人拿“RSA 被破了”的标题来问我我都会反问他一句你的随机源换过了吗你的填充库升级了吗你的错误信息统一了吗这三个问题能拦住九成真实风险。RSA 的数学命门目前还在论文预印本之外RSA 的工程命门绝大多数就在你自己代码的细节里。与其花时间找一把不存在的万能钥匙不如把这三件事钉死在项目规范里。