说实话我第一次在攻防世界Crypto区点开easy_RSA的时候心里想的是“这题能有多easy”。但真正把它做完、把RSA从头到尾理清楚之后我发现绝大多数新手其实不是卡在代码上而是卡在“根本不知道为什么要写这几行代码”。CTF密码学方向的入门题里RSA几乎就是第一道分水岭而easy_RSA则是这道分水岭上最友好的那一块垫脚石。这篇内容就从题目本身出发把RSA解密涉及的数学原理、工具选型、实际操作和踩坑经验一次讲透适合刚接触CTF、想系统理解RSA计算流程的读者也适合备考信息安全工程师时遇到RSA计算题不知道怎么下手的同学。保证你看完能自己独立把这道题做出来而不是光抄一个脚本。攻防世界这道题的交flag方式很有意思——题目给你p、q、e三个数让你求d然后把d的十进制数值当成答案提交。你没看错不需要解密密文不需要还原明文字符串答案就是一个数。但从这个“简单到极致”的流程里你能把RSA密钥生成、私钥求解、加解密闭环完整地走一遍。这几步搞明白了后面再遇到Normal_RSA、共模攻击、低加密指数攻击你至少知道自己在干嘛。1. easy_RSA这道题到底在考什么1.1 题目拆解拿到手的已知量只有三个先看题目给出的数据这是我在做题时拿到的参数攻防世界不同批次的题目可能微调但结构一致p 473398607161 q 4511491 e 17就这三行。没有n没有密文c没有任何多余的解释。你需要提交的flag是私钥d的十进制形式。我第一次看到这题的反应是e我认识是公钥指数p和q我也认识是两个素数。但为什么有了这三个数就能算出dd到底是什么这里就得回到RSA密钥生成的最基本流程。选两个大素数p和q把它们乘起来得到模数n计算欧拉函数φ(n)(p-1)(q-1)再选一个与φ(n)互质的整数e作为公钥指数最后求e关于φ(n)的模反元素得到私钥指数d。公钥是(n,e)私钥是(n,d)。题目现在给了p、q、e相当于把密钥生成过程进行到一半把最难的那一步——大整数分解——直接帮你做完了。你要做的只是顺着流程把d求出来。所以这道题的本质不是让你破解RSA而是让你验证自己懂不懂RSA密钥生成。这就好比你不需要去撬锁门主已经把锁芯拆下来给你了你只需要照着图纸把钥匙配出来。1.2 为什么这个思路在真实场景里站得住脚很多人做CTF题觉得“给p、q求d”太理想化现实中怎么可能泄露这两个数但恰恰相反p和q泄露的场景在安全事件里是真实存在的。比如某次开源代码仓库泄露开发人员把生成密钥的随机种子、素数或者中间变量一并提交到了Git上再比如共享素数攻击——两个不同的n恰好共用了同一个素数因子p攻击者用欧几里得算法把两个n的最大公约数一算p就暴露了。一旦p、q泄露私钥d就等于直接写在纸上了。所以easy_RSA不只是给新手练手它对应的是“拿到素数因子即可还原私钥”这一类真实攻击路径。理解了这一点你再回头看这道题就会明白它考的不是编程而是对RSA数学结构的理解程度。数据是死的流程是活的。2. 动手前必须吃透的三个数学概念2.1 欧拉函数为什么偏偏是(p-1)(q-1)欧拉函数φ(n)的定义是小于等于n且与n互质的正整数的个数。如果n本身就是素数p那小于p的数里除了0以外1到p-1全部与p互质所以φ(p)p-1。如果n是两个不同素数p和q的乘积情况稍微复杂一点但欧拉函数有一个很好的性质——它是积性函数当p和q互质时φ(p×q)φ(p)×φ(q)。于是就有了RSA里最经典的那个公式φ(n) (p - 1) × (q - 1)我拿个小数字验证一下你就明白为什么积性成立。设p3q5则n15。小于15且与15互质的正整数有1、2、4、7、8、11、13、14一共8个。而(3-1)×(5-1)2×48结果完全一致。这个例子虽然小但它能帮你建立直觉φ(n)不是靠“枚举互质数”算出来的而是靠素数结构直接推出来的。这也是为什么RSA要求n的两个因子必须是素数——只有素数因子才能让欧拉函数这么干净地拆开。2.2 模反元素求d本质上是在“配钥匙”私钥d的定义是e和d关于φ(n)互为模反元素。写成同余式就是e × d ≡ 1 (mod φ(n))这个式子的意思是e×d减去某个整数倍的φ(n)之后余数是1。把它改写一下更直观e × d 1 k × φ(n)其中k是任意整数。所以求d的过程本质上就是找到一对整数(d, k)让这个等式成立。这里的d就是私钥指数也就是这道题要你提交的答案。那模反元素为什么一定存在这完全依赖于e和φ(n)互质。如果它们有大于1的公因子等式右边永远是某个数的倍数加1永远不可能被那个公因子整除同余方程就无解。题目里e选的是1717是个素数只要φ(n)不是17的倍数就一定存在唯一的d。这解释了为什么RSA规范里推荐用65537作为公钥指数——65537也是素数且计算效率高同时它跟绝大多数φ(n)都互质省去了很多校验麻烦。求模反元素的标准算法是扩展欧几里得算法。它不仅能求出两个数的最大公约数还能在计算过程中反推出满足axbygcd(a,b)的那组系数。当gcd(e, φ(n))1时这个等式就退化成了我们需要的模反元素方程。手动推这个算法其实很考验耐心但对做题来说Python已经帮你封装好了直接用就行。2.3 模幂运算真正解密的临门一脚虽然easy_RSA只要求你求d但我强烈建议你把下一步的解密也顺手做了哪怕题目没有给密文。解密的核心运算是m c^d mod n这里的关键词是“mod n”。你可能会想直接算c的d次方再取余不就行了问题在于c和d都是几百位的大整数c^d这个中间结果的大小会让你直接内存爆炸。举个例子如果c是1024位、d是1024位c^d的位数大约是100万位普通计算机根本存不下。所以实际实现必须用快速幂模运算把指数按二进制展开每一步都做平方和取模把中间结果始终控制在n的范围内。这个算法的复杂度是O(log d)次乘法而不是O(d)次。Python内置的pow函数用的就是这套优化逻辑。m pow(c, d, n) # 正确写法 # m (c ** d) % n # 错误写法不要这么干这条经验在做CTF时救过我很多次。你看到网上有些脚本写的是pow(c, d, n)有的写gmpy2.powmod(c, d, n)本质上都是同一个东西只是底层库不同。后面工具章节我会细说。3. 工具链准备Python环境与两个关键库3.1 gmpy2CTF密码学解题的第一依赖做RSA相关题目gmpy2几乎是我每道题都会用的库。它是对GMPGNU Multiple Precision Arithmetic Library的Python封装专门处理任意精度的大整数运算。在RSA场景里你很少用到它那些复杂的数论功能最常用的就三个gmpy2.invert(e, phi)用来求模反元素gmpy2.powmod(c, d, n)用来做模幂运算gmpy2.is_prime(n)用来判断一个数是不是素数。选择gmpy2而不是手写算法不是因为懒而是因为它底层是C语言实现的在处理1024位、2048位大整数时性能比纯Python实现高出几个数量级。CTF比赛有严格的时间限制一道题如果你用Python的for循环去试除找因子比赛结束都未必能跑完。用gmpy2的成熟算法毫秒级出结果。安装方式很简单pip install gmpy2在Windows上如果遇到编译错误去PyPI的wheel页面下载对应Python版本的.whl文件再pip安装即可。macOS和Linux上一般直接装就能用。这里有个小细节值得说不要自己去编译GMP你看到网上教程让apt-get install libgmp-dev再pip install gmpy2那只适用于某些特殊环境普通用户直接用wheel包是最快的。3.2 pycryptodome处理整数和字符串转换的瑞士军刀另一个高频库是pycryptodome。它在CTF里的角色和gmpy2不太一样——gmpy2负责大整数数学运算pycryptodome负责把大整数和实际数据格式之间做转换。最常用的两个函数是from Crypto.Util.number import long_to_bytes, bytes_to_long # 整数转字节串 flag_bytes long_to_bytes(m) # 字节串转整数 m_int bytes_to_long(bflag)真实题目里给了密文后你解出来的明文m是一串大整数必须转换成ASCII字符串才能看到flag。long_to_bytes就是干这个的。它内部的处理逻辑是把整数转成十六进制字符串再按两个字符一组转成字节。理解了这一点你就知道为什么有时候直接用bytes.fromhex(hex(m)[2:])也能达到同样效果——原理相同。还有一点要注意pip安装的时候是pycryptodome不是pycrypto。pycrypto这个库已经停止维护多年而且存在已知安全漏洞网上很多老教程还在用它你照着抄很容易踩坑。3.3 绕开Python版本带来的暗坑Python 3.8开始内置的pow函数支持了模反元素计算写法是pow(e, -1, phi)。这意味着你其实可以完全不用gmpy2只用标准库就能求出d。这个特性知道的人不多但在比赛环境里非常有用——如果靶机环境没装gmpy2你又不方便装库这个内置方法就是救命稻草。d pow(e, -1, phi) # Python 3.8 内置模反元素不过从实际体验来看gmpy2的invert在错误提示上更友好。比如当e和phi不互质时invert会返回一个异常告诉你不可逆而pow(e, -1, phi)在旧版本里会直接抛ValueError。两者都能用我个人的习惯是优先gmpy2它在大整数场景下更稳。顺带提一句Python 2和Python 3在整数类型上有很大差异。Python 2里大整数是long类型打印出来会带一个L后缀比如125631357777427553L。如果你在旧题解里看到这种输出把它当flag提交之前必须把L去掉。Python 3统一了int类型以后这坑基本不复存在但你要能看懂老博客里的写法。4. 从读题到出答案完整解题复现4.1 第一步整理已知量和未知量做任何RSA题第一件事永远是列一个清单明确已知什么、要求什么符号含义本题值p大素数之一473398607161q大素数之二4511491e公钥指数17n模数np×q需要计算φ(n)欧拉函数(p-1)(q-1)需要计算d私钥指数e的模反元素需要计算这个表看起来简单但养成这个习惯能帮你避免很多低级错误。我见过太多人拿到题目直接写代码写着写着把p和q抄反了或者该用φ(n)的地方用了n最后答案怎么都不对。4.2 第二步两行代码求出私钥d有了前面的准备工作解题代码其实短得惊人import gmpy2 p 473398607161 q 4511491 e 17 phi (p - 1) * (q - 1) d gmpy2.invert(e, phi) print(d)跑完这段代码输出是125631357777427553这个数字就是本题的flag。如果你用的是Python 3.8以上的环境下面这段代码效果完全相同不需要第三方库p 473398607161 q 4511491 e 17 phi (p - 1) * (q - 1) d pow(e, -1, phi) print(d)两道代码无论跑哪个输出的d都是一样的。因为模反元素在模φ(n)意义下是唯一的不会因为你用了不同的库就得到不同的值。这一点你可以当成自查标准如果你的代码算出来的d跟这个不一样那一定是在某个步骤上出了岔子。4.3 第三步用一条完整的加解密链路验证d题目本身到上一步就结束了但我强烈建议你多走一步自己构造一条加解密链路验证d的正确性。操作方式是随便编一个明文m先加密再解密看能不能还原出来。这里我给一个可运行的完整例子import gmpy2 from Crypto.Util.number import long_to_bytes, bytes_to_long p 473398607161 q 4511491 e 17 phi (p - 1) * (q - 1) n p * q d gmpy2.invert(e, phi) # 构造一条明文 m bytes_to_long(bhello-easy-rsa) print(原始明文:, long_to_bytes(m)) # 公钥加密 c gmpy2.powmod(m, e, n) print(加密后:, c) # 私钥解密 m2 gmpy2.powmod(c, d, n) print(解密结果:, long_to_bytes(m2)) # 验证加解密闭环 assert m m2 print(加解密验证通过)跑完之后你会看到控制台输出一段可读的明文这就证明d是对的密钥对是匹配的。在这个验证过程中顺便就把bytes_to_long、long_to_bytes、powmod这几个以后一定会反复用到的函数都过了一遍。对于easy_RSA这种入门题多走这一步的意义不在于提交flag而在于把RSA的加解密逻辑在你脑子里串联起来。后面遇到真正给密文的题目你只需要把代码里的m替换成题目给的c就可以直接解密出flag。5. 我在刷这道题时踩过的坑与总结的套路5.1 提交格式与进制问题这道题最大的坑其实不在算法上而在提交格式上。题目要求提交的是d的十进制数值也就是125631357777427553这串数字本身。但很多新手在解完题之后会习惯性地把这个数字转成十六进制然后再转成字符串去提交结果得到一堆乱码。为什么会这样因为RSA解出来的明文m才是需要转字符串的东西而d本身只是一个整数。它没有对应的可读字符串含义强行转换只会得到乱码。所以提交flag的时候一定看清楚题目要的是十进制数字还是十六进制还是字符串格式。攻防世界不同版本的题目可能要求不同有的要求包上flag{}外壳有的直接填数字。这个信息通常在题面描述里写得很清楚做题前先把题面完整读一遍。顺带说一句这个题在攻防世界平台以外的变体里有时候会要求你求d之后继续解密一段给定的密文c。那种情况下你需要把密文从十六进制字符串转成整数解密后再用long_to_bytes转回字符串。流程跟上面第4.3节完全一样只是把m替换成了c的整数形式。5.2 欧拉函数写错漏减一的惨案另一个高频错误是把φ(n)写成了p×q忘了各自减一。这个错误在easy_RSA这种数据量级下不会报错你会得到一个数字但提交上去就是不对。原因很简单RSA的数学结构建立在φ(n)(p-1)×(q-1)之上私钥d的公私钥配对性质只有在使用正确的φ(n)时才成立。怎么自查你可以像第4.3节那样做一个加解密闭环验证。如果你用的φ(n)是错的求出来的d是错的解密出的结果必然不等于原始明文。这一步测试比肉眼检查公式更可靠。我在实际做题时凡是涉及RSA求d的都会顺手跑一遍加解密验证几秒钟的事能省下大把排错时间。5.3 软考计算题场景的延伸顺带提一个和CTF关系不大、但我猜不少人会搜到这篇内容的场景软考信息安全工程师的下午题里偶尔会出现RSA计算题给你p、q、e或者n、e、c让你手工或借助计算器求d、解明文。考场上没有Python环境怎么办我当时的方法是理解扩展欧几里得算法的迭代步骤遇到小数值的手算遇到大数值的用科学计算器的取模功能辅助。这个能力在CTF里同样有价值。比赛环境如果网络受限装不了库纯Python手写扩展欧几里得也能解决问题。我贴一个标准实现建议理解并默写这个函数def egcd(a, b): if b 0: return a, 1, 0 g, x1, y1 egcd(b, a % b) x y1 y x1 - (a // b) * y1 return g, x, y # 求 e 关于 phi 的模反元素 g, x, _ egcd(e, phi) if g ! 1: raise ValueError(e 和 phi 不互质无解) d x % phix % phi这一步很关键因为扩展欧几里得求出的x可能是负数取模之后才能归一化到[0, phi-1]区间内这才是合法的私钥指数d。这个函数看起来不起眼但它是很多RSA攻击脚本的基础设施。理解了它你对模反元素的理解就从“调用库函数”上升到了“知道库函数在干嘛”。5.4 识别已知量组合直接套用解题模板刷的RSA题多了以后你会发现所有题目本质上都是根据“已知量的组合”来决定用哪种攻击方式。我整理了一个粗糙但实用的判断表已知量组合解题方向p, q, e直接求dn, e, c且n很小或可分解分解n得到p、q再求d两个n共享同一个素数因子用gcd求公因子分解两个n同一个n两个不同的e和c共模攻击e很小如e3c也小低加密指数攻击直接开e次方私钥指数d很小Wiener攻击连分数逼近easy_RSA就是这张表里第一行的最典型代表。你把这张表记在脑子里以后看到任何RSA题目先归类再动手能少走很多弯路。这张表的每一行展开都是一篇文章的体量但起点都在这道easy_RSA上。6. 走出easy_RSA之后面对真实密文怎么办6.1 完整解密流程的标准化写法假设你现在遇到的题目是攻击世界Crypto区的另一道题给出这样的数据p 285960468890451637935629440372639283459 q 304008741604601924494328155975272418463 e 17 c 704073792705359107976457966254973868895812063986888497040127149267662596156617710120137724230765921103229403063038942394304100722629987583740465362158264这种题就要求你进一步解出明文m。标准代码如下import gmpy2 from Crypto.Util.number import long_to_bytes p 285960468890451637935629440372639283459 q 304008741604601924494328155975272418463 e 17 c 704073792705359107976457966254973868895812063986888497040127149267662596156617710120137724230765921103229403063038942394304100722629987583740465362158264 n p * q phi (p - 1) * (q - 1) d gmpy2.invert(e, phi) m gmpy2.powmod(c, d, n) # 方式一用 pycryptodome print(long_to_bytes(m)) # 方式二纯标准库 hex_m format(m, x) if len(hex_m) % 2 1: hex_m 0 hex_m print(bytes.fromhex(hex_m))特别注意format(m, x)这行——如果m转换成十六进制后长度是奇数bytes.fromhex会直接报错。解决办法就是手动补一个前导零。这个坑在写解密脚本时非常常见因为整数转十六进制时最高位的0会被省略导致字符串长度变奇。long_to_bytes内部已经处理了这个边界情况所以用标准库手写转换时记得这个细节。6.2 你可以继续深入的几个方向easy_RSA之后攻防世界Crypto区还有一系列RSA进阶题等着你。比如Normal_RSA会给你一个很大的n让你自己想办法分解Sherlock这类题目会涉及多个密文之间的代数关系broadcast是典型的低加密指数广播攻击。每个题背后对应着不同的数学攻击思路但它们的底层都离不开你对d、φ(n)、模幂运算这些基础概念的掌握。我个人刷题的习惯是每做完一道题就把它的已知量组合和攻击方式记到那张判断表里形成自己的方法论。RSA这个大方向拼的不是记住某个脚本而是理解每个参数在数学上扮演的角色。easy_RSA给了你一把打开RSA大门的钥匙门后面的世界很宽从Wiener攻击到Coppersmith方法从共模攻击到格密码够你玩很久。遇到不熟悉的概念别急着去搜现成脚本先想清楚题目里的每个数从哪里来、要到哪里去。RSA的美妙之处就在于它把抽象的数论变成了可以亲手验证的代码。你亲手把d算出来的那一刻这个算法的核心秘密就已经属于你了。