★ FEATURED ARTICLE 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 04ZIP格式因为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位的十进制大数e65537密文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经典的大数分解工具对几百比特以内的合数杀伤力极强。sagefactor(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(..., byteorderlittle)。第二长度不对。正常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打不开APKAPK损坏或加了壳用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但代码里一定会有运行时的输出或者把密钥参数写到了某个日志文件里。解题思路也要跟着变——不是从代码里抠参数而是从运行结果里找数据。用调试器跑一遍目标程序往往比死磕反编译结果更快。
阅读完成 · 觉得有帮助？
