[BUUCTF]REVERSE——RSA加密原理与实战破解

1. RSA加密原理入门指南第一次接触RSA加密时我也被那一堆数学符号搞得头晕眼花。但后来发现它就像我们日常用的密码锁——只不过这个锁的钥匙是数学公式。RSA作为目前最流行的非对称加密算法在CTF比赛中出现的频率高得惊人。简单来说RSA加密就是两个大素数的魔术。想象你手里有两个超级大的质数p和q比如几百位长把它们相乘得到N。这个N就像是挂在你家门口的公钥锁盒谁都可以往里面塞纸条加密但只有拿着私钥的你才能打开解密。有趣的是即使大家都知道N的值想反推出p和q也几乎不可能——这就是RSA安全的核心。加密过程就像在计算器上按几个键对明文m进行e次方运算然后除以N取余数得到的余数就是密文c。用数学表达就是c ≡ m^e mod N。而解密则是用另一个神奇的数字d做类似操作m ≡ c^d mod N。这里的(e, N)组合是公钥(d, N)组合就是私钥。2. CTF中的RSA题目破解实战去年参加BUUCTF时遇到一道典型RSA题题目就给了两个文件public.key和flag.enc。这种配置在CTF中太常见了解题过程就像玩解密游戏我们得一步步拆解系统。先用openssl看看公钥内容openssl rsa -pubin -in public.key -text -modulus输出会显示模数N和指数e通常是65537。拿到N这个大家伙后关键是要分解出p和q。我常用factordb.com这个网站把N转成十进制输进去运气好的话直接就能得到分解结果。那次比赛的N值分解后得到p 285960468890451637935629440372639283459 q 3040087416046019244943281559752724184633. 私钥生成与解密全流程拿到p和q就像拿到了宝箱的两片钥匙碎片。接下来要计算φ(N)(p-1)(q-1)这个φ(N)在数论中叫欧拉函数。然后求e关于φ(N)的模反元素d也就是解方程e*d ≡ 1 mod φ(N)。Python的gmpy2库有个现成函数import gmpy2 d gmpy2.invert(e, (p-1)*(q-1))有了d值完整的私钥就齐活了。用Python的rsa库加载私钥解密特别方便import rsa private_key rsa.PrivateKey(n, e, d, p, q) with open(flag.enc,rb) as f: print(rsa.decrypt(f.read(), private_key))记得我第一次做这题时因为没把密文文件用二进制模式读取死活解不出来折腾了半天才发现这个坑。所以特别提醒文件操作一定要加b模式4. 常见问题与调试技巧在实际操作中有几点特别容易翻车。首先是数字格式问题——N值可能在公钥里显示为十六进制而分解网站需要十进制输入。可以用Python直接转换n 0xC0332C5C64AE47182F6C1C876D42336910545A58F7EEFEFC0BCAAF5AF341CCDD print(int(n)) # 转为十进制其次是当p和q特别接近时用费马分解法可能比网站更快。我写了个小脚本备用from math import isqrt def fermat_factor(n): a isqrt(n) 1 b2 a*a - n while not isqrt(b2)**2 b2: a 1 b2 a*a - n return (a - isqrt(b2), a isqrt(b2))最后要注意的是有些题目会故意用非常小的e值比如3这时可能直接开e次方就能得到明文根本不需要分解N。这种技巧在CTF中称为低指数攻击。5. 深入理解数学原理为什么RSA这么可靠核心在于大数分解的难度。即使现在最快的超级计算机要分解一个600位的N值也需要宇宙年龄那么长的时间。不过在实际比赛中出题人通常不会设置这么变态的数字。那个关键的d值其实是e在模φ(N)下的乘法逆元。这里φ(N)不是随便什么数而是欧拉函数计算小于N且与N互质的正整数的个数。对于Npqφ(N)(p-1)(q-1)。这个性质让整个系统完美运转。有次我遇到一道变种题给的φ(N)值而不是N。这时候可以直接用公式d e^(-1) mod φ(N)连分解N的步骤都省了可见理解公式背后的数学原理多么重要。6. 高效工具链推荐经过多次比赛我整理了一套趁手的RSA解题工具包OpenSSL查看公钥信息的瑞士军刀factordb在线分解N值的首选RsaCtfTool集成了多种攻击方式的Python工具sage数学软件处理复杂数论运算对于Python环境建议直接安装pip install gmpy2 rsa pycryptodome有个小技巧当遇到特别大的N值时可以先用yafu这个软件在本地跑分解它支持多线程运算速度比在线网站快很多。记得比赛时有一次factordb上查不到的N值用yafu跑了半小时就分解出来了。7. CTF真题进阶技巧真正的比赛中RSA题目往往不会这么直白。常见的变种包括给多个密文使用相同模数N共模攻击p和q取值不当导致N容易分解Pollards p-1算法故意泄露部分私钥信息已知d高位攻击有道经典题是给两个加密flagc1 m^e1 mod N c2 m^e2 mod N当e1和e2互质时可以用扩展欧几里得算法找到x和y使得e1x e2y1然后计算m (c1^x * c2^y) mod N这类题目考察的是对RSA原理的灵活运用。我建议准备一个Jupyter Notebook把这些常见攻击脚本都整理好比赛时直接调用能省不少时间。