30、加密算法逆向（三）：RSA/ECC非对称加密算法逆向分析
非对称加密，说白了就是两把钥匙——一把公开，一把私藏。RSA和ECC是这里面最硬核的两个家伙。我在逆向分析中碰到它们的频率，说实话比对称加密高得多。为什么？因为很多开发者觉得「用了非对称就安全了」，结果实现上全是漏洞。
今天我们就来聊聊，怎么在二进制里把RSA和ECC的算法逻辑给揪出来，以及如何利用它们的实现缺陷做逆向突破。
RSA算法逆向：从模幂运算入手
RSA的核心就一个运算：模幂运算（modular exponentiation）。你想想看，c = m^e mod n 这种操作，在二进制里特征非常明显。
我个人习惯先搜大数常量。RSA的模数n、公钥e、私钥d，这些动辄1024位甚至2048位的超大整数，在二进制里是一串连续的字节。用IDA Pro的搜索功能，直接搜0x00 0x00 0x00...这种大数开头的零填充，往往能快速定位。
我记得有一次逆向一个金融SDK，里面藏了个RSA-2048的私钥。开发者居然把私钥硬编码在.data段，还加了混淆。我直接搜0x00 0xFF 0xFF...这种RSA模数特有的高位模式，三分钟就找到了。
- 大数常量：通常以0x00开头（正数表示），后面跟着256字节（2048位）或128字节（1024位）
- 模幂运算函数：特征为三层循环嵌套，内部有乘法和取模操作
- 中国剩余定理（CRT）：如果看到两个模数p和q分别参与运算，说明用了CRT优化
实战：定位RSA模幂运算
来看一段典型的RSA模幂运算反汇编特征：
; 模幂运算的典型循环结构
loc_401000:
mov ecx, [ebp+exp_bits] ; 指数位数
xor eax, eax
mov [ebp+result], 1 ; 初始化结果=1
loc_401010:
; 平方操作
push [ebp+result]
push [ebp+result]
call bigint_mul ; result = result * result
add esp, 8
push [ebp+modulus]
call bigint_mod ; result = result mod n
add esp, 4
; 判断当前指数位是否为1
mov edx, [ebp+current_bit]
bt [ebp+exponent], edx ; 位测试
jnc short loc_401030
; 乘操作（指数位为1时执行）
push [ebp+base]
push [ebp+result]
call bigint_mul ; result = result * base
add esp, 8
push [ebp+modulus]
call bigint_mod ; result = result mod n
add esp, 4
loc_401030:
dec ecx
jnz short loc_401010
看到这种「平方-判断-乘」的三段式结构了吗？这就是RSA模幂运算的指纹。我管它叫「平方乘算法」（Square-and-Multiply）。
ECC算法逆向：曲线参数是命门
ECC比RSA复杂一些，因为它涉及椭圆曲线上的点加和点乘运算。但核心突破口是一样的——找曲线参数。
一条椭圆曲线由 y² = x³ + ax + b 定义，外加一个基点G和阶n。这些参数在二进制里是固定长度的字节序列。比如secp256k1（比特币用的曲线），参数都是32字节。
我曾经逆向过一个区块链钱包，里面用了自定义的椭圆曲线。开发者觉得「自己造曲线更安全」——嗯，结果曲线参数里藏了个后门，我通过逆向把参数提取出来，发现阶n有小的素因子，直接可以用Pohlig-Hellman算法攻破。
ECC点乘运算的逆向特征
ECC的核心运算是标量乘法（点乘）：Q = k * G。这个运算在二进制里表现为：
- 点加函数：涉及模逆运算（求倒数），特征为扩展欧几里得算法
- 点倍函数：涉及切线斜率计算，有大量的模乘和模加
- 主循环：类似RSA的平方乘，但这里是「点倍-判断-点加」
来看一个ECC点乘的伪代码特征：
// ECC标量乘法（蒙哥马利阶梯，防侧信道）
function scalar_mult(k, P):
R0 = 0 (无穷远点)
R1 = P
for i from bits-1 down to 0:
if bit_i of k == 0:
R1 = R0 + R1 // 点加
R0 = 2 * R0 // 点倍
else:
R0 = R0 + R1 // 点加
R1 = 2 * R1 // 点倍
return R0
看到没？无论k的当前位是0还是1，都执行一次点加和一次点倍。这就是蒙哥马利阶梯，用来防时间攻击的。如果你在逆向时发现这种「无分支」的循环结构，基本可以确定是ECC。
常见实现漏洞与逆向利用
光能识别算法还不够，你得知道怎么利用它们的实现缺陷。我整理了几个实战中遇到的高频漏洞：
| 漏洞类型 | 特征 | 利用方法 |
|---|---|---|
| 私钥硬编码 | .rodata或.data段出现大数常量 | 直接提取，解密通信数据 |
| 随机数重用（ECC） | 签名中r值相同 | 直接计算私钥 k = (s1 - s2) / (r1 - r2) |
| CRT未做冗余检查 | RSA-CRT实现中缺少校验 | 注入故障，利用贝尔科攻击恢复p和q |
| 侧信道泄露 | 运算时间随密钥位变化 | SPA/DPA分析，逐位恢复密钥 |
SVG：非对称加密逆向分析知识体系
逆向分析实战流程
说了这么多理论，来点实际的。我一般按这个流程走：
- 静态定位：用IDA搜索大数常量，定位到加密相关函数
- 算法识别：根据模幂运算或点乘运算的特征，确认是RSA还是ECC
- 参数提取：从二进制中提取模数n、公钥e、曲线参数等
- 漏洞扫描：检查是否有硬编码密钥、随机数重用、CRT缺陷等
- 动态验证：用调试器跑起来，在关键函数下断点，观察输入输出
非对称加密的逆向，说白了就是「找参数、识算法、抓漏洞」这三板斧。RSA看模幂，ECC看点乘，剩下的就是细心和耐心。你想想看，那些号称「军用级加密」的软件，有多少是把私钥直接塞在二进制里的？我见过的案例，比你想象的要多得多。