RSA这种题目在CTF里属于那种“会者不难，难者不会”的类型。刚接触的时候，很多人卡在第一步：拿到一个安卓APK或者Java的class文件，不知道从哪里下手；就算反编译出来了，看到一堆n、e、d、p、q的变量名，也不知道哪个是哪个。这篇就专门聊聊“从反编译到私钥求解”这条完整链路，用一道典型题目把思路捋清楚。
先说清楚这篇文章适合谁。如果你已经知道RSA的基本原理——比如公钥加密、私钥解密、n = p * q——但一碰到实际题目就懵，不知道怎么把代码里的数字“捞出来”变成flag，那这篇就是给你准备的。如果你连RSA是什么都不太清楚，我也会把必要的数学背景揉进步骤里讲，不至于让你看得云里雾里。
CTF里的RSA题目，说穿了就两件事：找到私钥材料和把私钥算出来。前者考验反编译和代码审计能力，后者考验数论和工具使用能力。这篇文章会用一个非常典型的场景——反编译APK后从Java代码里提取RSA参数——带你走完从“拿到一个文件”到“解出明文”的全过程，顺带把我踩过的坑和排查思路一并交代清楚。
1. 题目拆解：拿到一个APK先干什么
很多RSA入门题不会直接给你flag.txt或者一组数字，而是给一个Android安装包，或者一个Java的Jar包。这道题就是典型的“反编译型RSA”：题目把公钥和私钥的生成过程写在了代码里，但藏得不算深，只要你会反编译、会看Java代码，就能找到关键参数。
1.1 先判断文件类型，别急着反编译
拿到题目附件第一步，不是双击打开，也不是直接扔进反编译器，而是先看文件头。在终端里执行file命令，或者用Hex编辑器看前几个字节：
file mystery.apk如果是APK，文件头是50 4B 03 04（ZIP格式），因为APK本质就是ZIP压缩包。如果是纯Java的class文件，文件头是CA FE BA BE。这一步看似废话，但真有人把APK当成ZIP直接解压，解出来一堆资源文件却不知道dex在哪。
APK的处理方式很简单：先用unzip解压，或者直接改后缀名成.zip再解压。解出来你会看到classes.dex，这才是真正的代码。要读dex里的代码，两种常用路径：
- 用
jadx直接打开APK，它会自动把dex反编译成Java源码，同时保留资源文件。 - 用
dex2jar先把dex转成jar，再用jd-gui打开。
我个人推荐jadx，原因是它对现代Android项目的还原度更高，字符串、资源引用、匿名内部类都能看得比较清楚，命令行操作也方便。
jadx -d output_dir mystery.apk这条命令会把反编译结果输出到output_dir目录，然后用任何文本编辑器或者IDE打开就能浏览Java代码。对CTF来说，我们主要关心的是代码逻辑，而不是资源文件，所以直接看.java文件就对了。
1.2 在代码里找RSA的影子
反编译出来以后，代码可能不少，但我们的目标很明确：找RSA相关的类和方法。用全局搜索效率最高，搜这些关键词：
RSACiphergenerateKeyPairRSAPrivateKeyBigIntegermodPowgetModulus
因为RSA题目离不开大数运算，在Java里就是BigInteger。如果看到类似下面这种代码，恭喜你，题目核心已经找到了：
BigInteger p = new BigInteger("..."); BigInteger q = new BigInteger("..."); BigInteger e = new BigInteger("65537"); BigInteger n = p.multiply(q); BigInteger phi = p.subtract(BigInteger.ONE).multiply(q.subtract(BigInteger.ONE)); BigInteger d = e.modInverse(phi);这段代码是RSA密钥生成的教科书写法。p和q是两个大素数，n是它们的乘积，phi是欧拉函数值，d是e关于phi的模逆元。只要代码里出现了这几行，就说明私钥材料全都在眼前，剩下的就是把这些字符串提取出来算d。
但这里有个非常容易翻车的细节：很多题目不会把p、q明文写在代码里。可能只写n和e，也可能把p、q做了某种编码，更有甚者会把私钥存在Android的SharedPreferences里，或者用Base64编码后藏在资源文件里。所以搜索的时候，别只盯着BigInteger看，String类型的数字字符串也要留意。
1.3 分清哪些参数是“真私钥材料”
看到一堆大数字，先别急着高兴。我们要解决的是“求解私钥”，但题目代码里给的不一定都是能直接用p * q互乘关系的材料。常见的几种情况：
| 场景 | 代码中出现的东西 | 能否直接解出私钥 |
|---|---|---|
| 最理想 | p、q、e都给了 | 能，直接算d = e^-1 mod (p-1)(q-1) |
| 较常见 | n、e给了，p和q没给 | 看n是否够小，能分解就能解 |
| 坑爹型 | 只给n和d | 其实已经拿到私钥了，不用算，直接解密 |
| 混淆型 | 给了n、e、d_p、d_q | 用CRT（中国剩余定理）参数解密 |
对照题目代码，大多数入门题都是第一种：p和q直接作为字符串躺在代码里。这时你需要的数学运算量其实很小，难的是提取和格式处理。但我也见过不少题把p和q藏得很深，后面我会专门讲这种“不老实”的情况怎么应对。
2. 从反编译代码到参数提取的完整实操
这一节我们进入实际操作。假设你已经用jadx反编译完题目APK，发现了一个名为MainActivity或RsaUtil的类，里面有一段生成密钥和解密的逻辑。
2.1 典型题目代码长什么样
反编译出来的代码可能有混淆，变量名可能变成a、b、c，但逻辑不会变。一个典型的代码如下：
public class RsaUtil { public static String decrypt(String cipherText) throws Exception { String pStr = "112546134717849078547429349198187862871909466247568253465"; String qStr = "165227247462589441751784638512913747979538923264757784499"; BigInteger p = new BigInteger(pStr); BigInteger q = new BigInteger(qStr); BigInteger n = p.multiply(q); BigInteger e = BigInteger.valueOf(65537); BigInteger phi = p.subtract(BigInteger.ONE).multiply(q.subtract(BigInteger.ONE)); BigInteger d = e.modInverse(phi); BigInteger cipher = new BigInteger(cipherText); BigInteger plain = cipher.modPow(d, n); return new String(plain.toByteArray()); } }这里我把数字改为接近真实规模的素数，方便演示。题目代码形式上可能会把pStr和qStr拼成别的变量名，也可能把decrypt方法包装成字符串处理的复杂形式，但只要看懂了这段，万变不离其宗。
特别注意BigInteger.valueOf(65537)。65537是RSA公钥指数e最常用的值，经典永流传。如果你在代码里看到e = 65537，基本可以直接用e.modInverse(phi)求d。如果e是3这种小指数，那又是另一类攻击思路，这里先不展开。
2.2 参数提取的正确姿势
把pStr和qStr从代码里复制出来以后，最忌讳的就是手抄。大素数的字符串动辄几十位甚至上百位，手抄错一位，后面的解密全盘皆输。正确做法是：
- 直接复制jadx反编译出来的字符串常量。
- 去掉多余的空格、换行和注释。
- 确认字符串里只有数字，没有十六进制前缀
0x，没有逗号分隔。
我在实际做题时会写一个简单的Python脚本，把p、q、e这些参数丢进去跑。脚本里顺便加个校验：p * q是否等于某个已知的n（如果题目代码里有n的话）。如果不能验证，就至少检查一下p和q的位数是否合理，再看看phi算出来是不是偶数——因为两个奇素数的欧拉函数一定是偶数。
提取完成后，我们的材料清单长这样：
p：一个约50位的十进制大数q：一个约50位的十进制大数e：65537- 密文
c：通常是一个十进制数，也可能是Base64编码后的字节
如果题目把密文也放在代码里，比如String cipherText = "123456..."，那就直接提取。如果密文在另一个文件里（比如flag.enc），就用Python读文件转成十进制数。
2.3 算私钥：Python一行代码的事
拿到p、q、e之后，求d需要的数学就是扩展欧几里得算法，Python的pow函数都帮我们封装好了。下面这个脚本可以直接用：
from math import gcd p = 112546134717849078547429349198187862871909466247568253465 q = 165227247462589441751784638512913747979538923264757784499 e = 65537 n = p * q phi = (p - 1) * (q - 1) # 校验 e 和 phi 互质，不互质没法求模逆元 assert gcd(e, phi) == 1, "e and phi are not coprime!" d = pow(e, -1, phi) print("n =", n) print("d =", d)Python 3.8以后内置pow(a, -1, mod)可以直接求模逆元，不需要自己写扩展欧几里得。如果你环境版本比较老，也可以用gmpy2.invert(e, phi)，效果一样。
算出来d之后，解密就是一次模幂运算：
c = 52390468007850947847580923442384723094830298423094823094823 # 实际密文 m = pow(c, d, n) flag = m.to_bytes((m.bit_length() + 7) // 8, 'big') print(flag.decode())to_bytes的字节长度用bit_length换算，避免出现位数不足或溢出的问题。这里有个小细节：如果m的最高位是0，直接to_bytes可能丢字节，所以有些脚本会固定长度。CTF里flag通常是ASCII字符串，所以decode()一般不会出错。
2.4 代码没有给你p和q怎么办
上面是最顺利的情况。但实际题目中，不少会把p、q藏起来，只留n和e。这时你需要的是分解大整数n。
CTF入门阶段，分解n的武器库按优先级排列：
factordb.com：在线大数分解数据库，本地试一下就知道，很多题目用的n是现成的或者弱素数。yafu：经典的大数分解工具，对几百比特以内的合数杀伤力极强。sage：factor(n)一行命令，内置多种分解算法。- Python的
sympy.factorint：对于入门题够用，再大就吃力了。
如果你在代码里看到的是n和e，第一步一定是先把n丢进factordb。如果数库里没有，再用yafu跑。原因很简单：factordb查一次只需要几秒，yafu可能要跑几分钟甚至更久，效率优先。
分解得到p、q之后，回到上面的脚本，一切照旧。
注意：如果你用factordb查询，注意区分
n和p*q的结果展示。有时候factordb会把一个合数显示成两个素数相乘的形式，但两个素数可能顺序和p、q的原始定义不一致，这不影响phi的计算，因为(p-1)*(q-1)和(q-1)*(p-1)完全一样。
3. 解密环节的常见工程问题
私钥d算出来了，按理说解密就像喝凉水一样简单。但我在带新人做题时发现，卡在最后一步的人非常多，而且问题往往不是数学，而是“数据格式”这层窗户纸没捅破。
3.1 密文是十进制字符串还是Base64
题目给密文的方式千奇百怪：
- 直接给十进制字符串：最常见，直接用
BigInteger或者Python的int转成整数就行。 - 给Base64字符串：先
base64.b64decode()还原成原始字节，再转成整数。 - 给十六进制字符串：
int(hex_str, 16)直接转。
看代码里Cipher是怎么初始化的。Java里如果用BigInteger直接构造，那密文多半是十进制或十六进制字符串。如果用了Cipher.getInstance("RSA/ECB/PKCS1Padding")这种标准JCE接口，那密文就是原始字节数组，可能在传输时被Base64编码成了字符串。
解密时如果发现m.to_bytes()出来的字节开头有奇怪的填充，比如\x00\x01\x02...，那就是PKCS1模式的填充。正经RSA实现会自动去填充，CTF题目代码如果是手写modPow，一般不会有填充，直接转字符串就是明文。
3.2 大数字符串里的空格和换行
从jadx的图形界面复制代码时，字符串可能被格式化成多行，比如：
String pStr = "112546134717849078547429349198187862871909466247568253" + "465";Java里字符串拼接不稀奇，但你在Python里要把两个片段拼起来时，得把中间的空格、引号、加号全部去掉，只保留纯数字。写个replace清洗是好习惯：
import re raw = "112546134717849078547429349198187862871909466247568253 465" p = int(re.sub(r'\D', '', raw))虽然大多数时候你手动复制不会出错，但碰到几百位的数字，肉眼检查不现实，正则清理最靠谱。
3.3 输出flag乱码怎么办
解密出来的字节数组直接decode('utf-8')报错，或者打印出来是一堆不可见字符，这种情况我见过不下五次。原因一般有两种：
第一，字节序问题。modPow的结果转成字节时，Python默认用大端序，Java的BigInteger.toByteArray()也是大端序，理论上不会错。但如果你用了sagemath或者某些工具中间转过格式，就可能出现高低位反转，这时候试试m.to_bytes(..., byteorder='little')。
第二，长度不对。正常flag是flag{...}这种ASCII格式，长度和m的字节长度匹配。如果出现比n还长的结果，那多半是解密公式用错了，比如把cipher和m搞反了。
提示：如果
m.to_bytes()少了字节，Python会报OverflowError。解决方法是手动指定一个足够长的长度，比如(n.bit_length() + 7) // 8，因为m一定小于n，所以这个长度永远不会溢出。
4. 常见问题与排查技巧实录
做题多了，你就能总结出一套“症状-病因-药方”的排查表。我把RSA反编译题里最高频的问题整理成一张表，照着查能省很多时间。
| 现象 | 可能原因 | 解决办法 |
|---|---|---|
| 反编译后代码里找不到RSA | 被混淆器改名，或RSA逻辑在native层 | 搜BigInteger、modPow、Cipher，别只搜RSA |
拿到n和e但分解不动 | n太大，或者用了强素数 | 先试factordb，再试yafu的factor()，最后考虑题目是否用了其他攻击面 |
| 解出来是乱码 | 字节序不对或长度不对 | 检查to_bytes的byteorder，用n.bit_length()确定长度 |
d算出来是负数或异常大 | e和phi不互质 | 检查p和q是不是素数，检查e是不是被篡改过 |
解密结果有\x00开头 | 明文本身就是二进制，或填充字节 | 尝试去掉开头的\x00，或者用lstrip(b'\x00') |
| jadx打不开APK | APK损坏或加了壳 | 用unzip看能否正常解压，加壳的需要脱壳，这属于进阶内容 |
有一个非常隐蔽的坑必须单独提：Java的BigInteger.toString()输出的是十进制，但某些反编译工具会把大数显示成十六进制。比如jadx在某些版本显示new BigInteger("2A51...", 16)，这里的16就是radix参数。如果你直接把字符串当成十进制提取，数字就完全是错的。识别方法是看构造函数的第二个参数：new BigInteger(String, int radix)。有16就是十六进制，有2就是二进制，以此类推。
另外一个小技巧：题目代码里如果有Cipher.getInstance("RSA")，说明用的是标准Java加密接口，这种情况下n和e很可能通过KeyGenerator或KeyPairGenerator生成，不会在代码里出现明文p、q。此时你要找的是RSAPrivateKey的编码——通常是PKCS8格式的字节数组。这种情况下，直接用openssl或者Python的rsa库去解析私钥文件，比从代码里抠参数要快得多。
openssl rsa -in private.pem -text -noout这条命令会直接打印出modulus、privateExponent、prime1、prime2等全部参数，省去了所有反编译分析的力气。如果题目给的是PEM文件，这就是捷径中的捷径。
5. 从入门到进阶：这道题的延展思路
解决了这道“RSA入门：从反编译到私钥求解”之后，你会发现RSA题型的几个变种其实都是从同一个核心出发的：代码或者文件里一定有某种形式的密钥材料，你的任务是找到它、理解它、利用它。
往后你会遇到的常见变种包括：
- 共模攻击：同一个
n，两个不同的e，用扩展欧几里得就能解出明文。 - 低加密指数攻击：
e很小（比如3），密文的e次方根就是明文。 - Wiener攻击：
d很小，连分数展开能恢复d。 - 已知
p、q的高位或低位：利用Coppersmith定理求解完整因子。
这些攻击的本质都是“私钥参数缺失或部分泄露时，从数学上恢复私钥”。和入门题不同的是，入门题把参数放在你眼前，进阶题把参数藏进数论结构里。但无论如何，你都需要先熟练掌握“从代码/文件中提取参数”这门基本功。
以这道题为例，如果你把p、q提取出来后，先不急着算d，而是把n丢进factordb验证一下，你可能会发现n是某个数据库里已知的弱模数。这说明出题人可能在n的生成上留了更深的漏洞，而不仅仅是你看到代码里明文的p、q。遇到这种情况，多留个心眼总没错。
我个人做这类题的一个习惯是：永远先写一个通用的RSA解密脚本模板，把p、q、e、c都设成变量，再根据题目的代码逻辑往里面填。这样一来，每次做题只需要跑一次脚本就行，不用重复写模逆元和解密代码。这个模板从一开始的十几行，慢慢会扩展出处理Base64、处理十六进制、处理PEM文件的功能，最后变成自己的“RSA解题工具箱”。
最后再分享一个小技巧：反编译代码里如果出现了类似BigInteger.probablePrime(512, new Random())这种写法，说明p和q是随机生成的，每次运行都可能不同。这种题你几乎不可能从代码里直接复制出确定的p、q，但代码里一定会有运行时的输出，或者把密钥参数写到了某个日志文件里。解题思路也要跟着变——不是从代码里抠参数，而是从运行结果里找数据。用调试器跑一遍目标程序，往往比死磕反编译结果更快。
