[原创]RSA 加密 1 字节 patchN 的提速算法研究

一句话总结：快的关键不是"算得更快"，而是别对每个候选单独试除——利用候选之间的等差结构，把「候选 × 2.6 万个小素数」压成「2.6 万个小素数」，再把真正昂贵的 Miller-Rabin 压到 1/4。

背景

软件破解场景，试图只 patch 一个字节就能生成 RSA 私钥、过 RSA 公钥验证。没啥实际意义，但是比较好玩。
具体是这样的：手里有一个 RSA 模数 n，要找出一个 n'，它和 n 恰好只差一个字节，并且满足

n' = p × q            p 是小素数，q 是素数
gcd(e, φ(n')) = 1     φ(n') = (p − 1)(q − 1)

找到之后就能算出私钥指数 d = e⁻¹ mod φ(n')，得到配套的私钥。

穷举空间不算大：4096 bit 的模数是 512 个字节，每个位置 255 种取值，一共约 13 万个候选。问题在于——怎么快速判断这 13 万个候选里哪些可以分解、商又是不是素数。

朴素做法慢在哪

一种很自然的实现路线是"逐个候选"：每生成一个 n'，就把它当成一个独立的因子分解问题，跑一遍完整的分解流水线——判素、试除、Brent、P-1/ECM，找到因子再看商是不是素数。

复杂度是 O(候选数 × 单个候选的分解成本)。分解本身既贵又带随机性，这条路的开销基本随候选数线性增长。

拿 4096 bit 粗估一下：13 万个候选，如果每个候选只做一遍千万级以内的试除，

130,560 × 1,077,871 ≈ 1.4 × 10^11 次大整数整除

单线程按每次 30 ~ 50 ns 也要一两个小时，后面的 Brent/ECM 还没算。

本文的做法是

512 个位置 × 2.6 万个素数 ≈ 1.33 × 10^7 次 32 位乘加

差四个数量级，而且只和「位置数 × 素数数」有关、与候选数无关。

关键在于这些候选不是互相独立的：固定字节位置 m 时，

n'(d) = n + d · 256^m        d = 新字节 − 旧字节

同一个位置的 256 个候选，只差一个小整数 d。这种等差结构可以一起算。

优化一：一次扫描算完 256 个候选

对任意奇素数 r：

n'(d) ≡ 0 (mod r)   ⟺   d ≡ −n · 256^(−m) (mod r)

也就是说：只要知道 n · 256^(−m) mod r 这一个余数，就能反推出这个位置上 256 个 d 里哪些会被 r 整除——对 r > 255 至多一个，对 r ≤ 255 则是等间隔的几个。

于是扫一遍素数表，就能把该位置 256 个候选的整除情况全部算出来：

• cnt[b]：改成 b 之后被几个小素数整除（饱和到 2，够用了）
• killer[b]：其中最小的那个素因子

成本从「候选数 × 素数个数」降到「素数个数」——一次性降了一个维度。

优化二：换位置只要两次 32 位乘法

下一个位置需要的是 n · 256^(−(m+1)) mod r，而它正好等于上一个余数乘以 256^(−1)：

n · 256^(−(m+1)) ≡ (n · 256^(−m)) · 256^(−1)  (mod r)

直接对大整数重新取模是 O(位数) 的；这里换一种做法：预先算好 r^(−1) mod 256，让 t + k·r 能被 256 整除，然后右移 8 位，就等于"乘 256 的逆"：

const std::uint32_t k = std::uint8_t(0u - t * inv);   // inv = r^-1 mod 256
const std::uint32_t d = t ? r - t : 0;                // 当前需要的位移
if (d <= hi)                 mark(old_b + d, r);     // 命中一个候选
else if (r - d <= old_b)     mark(old_b - (r - d), r);
t = std::uint32_t((std::uint64_t(t) + std::uint64_t(k) * r) >> 8);

每个（位置, 素数）就是两次 32 位乘法加一次移位，和模数有几千位无关。这一步是整条算法里最重要的常数因子。

优化三：两道近乎免费的预筛

扫完之后，只有 cnt == 1 的候选值得判素：

• cnt ≥ 2：被两个以上小素数整除，必是合数；
• cnt == 0：没有不超过上界的小素因子，按这个搜索空间的定义找不到 p；
• cnt == 1：恰好有一个小素因子 p，此时商 q = n'/p 与所有小素数互素，判素命中率高。

判素之前再筛一道：gcd(e, φ(n')) ≠ 1 的候选算不出 d，连 Miller-Rabin 都不用做（e = 3 时能扔掉约 3/4）。

实测每个位置 256 个候选里，平均只剩下 57 ~ 66 个要真正判素。

优化四：筛表上界不是越大越好

预筛的收益，来自"用便宜的小素数除法换掉昂贵的 Miller-Rabin"。那第一个问题就是：筛表上界 B 取多大？

B 越大，cnt == 1 的候选越少；但每个位置要扫的素数按 O(π(B)) 涨，建表和求 n mod p 也要时间。两条曲线的斜率差得很远——4096 bit 实测（同一个模数）：

素数多了 8 倍，候选只少 12%。所以上界不是越大越好：模数小的时候，多扫的素数根本省不回来；只有单次 Miller-Rabin 变得足够贵（模数大），加大上界才划算。

代码里的规则就是按这个权衡定的：n ≤ 2048 bit 用 3×10⁴，更大用 3×10⁵。顺带 B 也是正确性边界——能找到的 p 不会超过它。

并行

生产者线程按字节位置从低到高扫描，把候选按批投递到队列；消费者线程（hardware_concurrency() 个）并行做整除、gcd、Miller-Rabin。

位置从低到高、同一位置取最小的新字节值，保证结果完全确定——同样的输入永远得到同样的输出。

为什么必须用 GCC

MSVC 没有 GCC 风格的 __int128。GMP 在 x86_64 上的 mpn 快路（64×64→128 位的单指令乘法）在 MSVC 下拿不到，只能回落到"把 64 位操作数拆成两个 32 位再拼高位"的 C 代码。

而 MinGW 这份 GMP 是 fat 构建：libgmp.a 里有 680 条 mulq/mulx，运行时按 CPUID 选 k8/bd1 变体。整个程序 99.9% 的时间都在 Miller-Rabin，也就都在这条汇编路径上。

objdump -d libgmp.a | grep -cE 'mulq|mulx'   # 680

所以同一个算法用 MSVC 编，理论上是能跑的，但最热的那部分会被换掉。

实测

机器：AMD Ryzen 5 5600（6 核 12 线程，3.5 GHz）、16 GB、Windows 11、GCC 16.2.0（MSYS2 UCRT64）、GMP 6.3.0（静态 libgmp.a，fat 构建）。编译选项 -O3 -DNDEBUG -static -s --gc-sections。

每个尺寸一个用例，各跑 15 次取中位数，对比闭源实现 rpatch(8a2K9s2c8@1M7s2y4Q4x3@1q4Q4x3V1k6Q4x3V1k6Y4K9i4c8Z5N6h3u0Q4x3X3g2U0L8$3#2Q4x3V1k6F1M7%4A6&6x3o6l9%4i4K6u0r3M7Y4m8S2N6r3y4Z5) ：

至于飘X阁的 RSA 一字节替换工具 v1.3 以及开源实现 RSA-PATCH-TOOLKIT(afeK9s2c8@1M7s2y4Q4x3@1q4Q4x3V1k6Q4x3V1k6Y4K9i4c8Z5N6h3u0Q4x3X3g2U0L8$3#2Q4x3V1k6r3g2q4y4f1g2q4)9J5c8W2u0e0b7g2)9J5k6q4m8m8g2p5y4t1i4K6u0V1g2p5!0a6e0p5E0u0g2l9`.`.) ，速度差距更大，4096 bit 上千倍起步。

仓库

做成了C++ header-only 库（d26K9s2c8@1M7s2y4Q4x3@1q4Q4x3V1k6Q4x3V1k6Y4K9i4c8Z5N6h3u0Q4x3X3g2U0L8$3#2Q4x3V1k6D9N6%4c8%4x3e0t1K6y4o6f1$3i4K6u0r3L8$3&6W2i4K6g2X3j5Y4W2@1k6g2)9#2k6Y4m8S2N6r3y4Z5e0R3`.`.）。