攻防世界的Crypto板块我刷过不少要说最容易被新人误解的一道题easy_RSA肯定榜上有名。表面上它只要你在输入框里填一个十进制字符串实际上考的是RSA密钥生成里最关键的一步在已知p、q、e的情况下把私钥d推导出来。题面干净到极点就三个数——p473398607161、q4511491、e17可很多人第一步就卡住了不知道该按什么公式算、算出来对不对、提交的时候要不要加前缀。这篇就把它从头到尾拆开讲顺便把CTF里和它相关的几类RSA攻击思路一起梳理出来。适合刚接触Crypto、想搞懂RSA本质的读者也适合准备软考信息安全工程师时复习RSA计算题的朋友。1. easy_RSA题面解析考的就是RSA密钥生成的反向推导1.1 题目给了什么又要你交什么攻防世界的easy_RSA是Crypto板块的经典入门题整个题面几乎没有任何多余信息。已知条件就三个数两个素数p、q一个公钥指数e要求你算出私钥d并提交。表面上这是“求一个数”实际上它把RSA密钥生成流程完整地考了一遍——你需要自己走一遍n、φ(n)、d的计算链路最后输入那个十进制结果。很多人刚上手时会迷茫不知道题目的flag到底是什么。这里明确一下这道题的答案就是d本身不需要加任何前缀或括号提交纯十进制数字即可。也有一部分人会误以为要提交n或者某种加密后的密文这些想法都是因为没理解RSA密钥生成的定义。为什么这道题敢叫easy因为它把RSA里面最困难的一步——大整数分解——直接跳过了。p和q都白给你了你不需要去解因式分解只需要做四则运算和一次模逆元计算。这其实是一个非常重要的信号RSA的数学骨架就是“给定p、q、e求d”只要这一步想明白后续那些看起来复杂的攻击方式本质上都是在这个骨架上做文章。1.2 私钥d是怎么来的从数学定义说起RSA密钥生成的完整流程是这样的随机选择两个大素数p和q计算模数n p × qn的二进制长度决定了密钥长度计算欧拉函数φ(n) (p - 1) × (q - 1)选择一个与φ(n)互素的公钥指数e工程上通常选65537计算私钥d使得d ≡ e⁻¹ (mod φ(n))这里的关键是最后一步。d不是随便选的它必须满足e × d ≡ 1 (mod φ(n))。换句话说e和d在模φ(n)的意义下互为倒数。这就像你有一把锁和一把钥匙公钥e负责加密私钥d负责解密两者在数学上正好是一对搭档。很多初学者会困惑为什么解密一定要用d而不是直接用e再算一次这就牵扯到欧拉定理了。对于与n互素的明文m有m^φ(n) ≡ 1 (mod n)。因为e × d k × φ(n) 1所以m^(e×d) ≡ m^(k×φ(n)1) ≡ (m^φ(n))^k × m ≡ 1^k × m ≡ m (mod n)这个过程可以类比成一个“模数时钟”站在0点出发先拨e格再拨d格最终回到原点。只要e和d在φ(n)这个时钟上互逆加解密就能闭环。那攻击者为什么拿RSA没办法因为他不知道φ(n)。n是公开的但要从n反推出p和q就要做大整数分解这是公认的困难问题。一旦有人通过某种途径拿到了p和q他就是拿到了“钥匙坯子的参数”可以轻松算出私钥d。所以这道easy_RSA的真正用意就是让你体验一次“拥有p和q等于拥有全世界”的感觉。2. 一步一步算出d手算、脚本、验证三管齐下2.1 先手工走一遍扩展欧几里得求模逆元既然p和q都给了第一步就是把φ(n)算出来。代入具体数值p - 1 473398607160 q - 1 4511490 φ(n) 473398607160 × 4511490 2135733082216268400这个数很大手算乘法时要特别小心建议分步乘或者用计算器复核一次。接下来就是核心操作求e17在模2135733082216268400下的乘法逆元d。你不能直接拿17去除因为模逆元的定义不是实数除法而是要找到一个整数d让17 × d除以φ(n)的余数等于1。最标准的做法是扩展欧几里得算法它的本质是辗转相除法的逆过程。把整个过程写出来2135733082216268400 17 × 125631357777427552 16 17 16 × 1 1 16 1 × 16 0辗转相除到余数为0后再从下往上回代1 17 - 16 × 1 16 2135733082216268400 - 17 × 125631357777427552所以1 17 - [2135733082216268400 - 17 × 125631357777427552] 1 17 × 125631357777427553 - 2135733082216268400也就是说17 × 125631357777427553 ≡ 1 (mod 2135733082216268400)因此d 125631357777427553这就是你要提交的答案。这里有个细节值得注意为什么回代后的d刚好比上面那个商大1因为φ(n)除以17的余数是16也就是-1的等价形式。当余数出现“差1”的情况时回代会自然地给系数加上一个商数。数学上没有任何玄学但手算时如果你发现结果差1别急着怀疑自己算错了先回头检查余数和回代步骤。2.2 不依赖第三方库的解法自己写扩展欧几里得手算只能用于小数据真实场景里p、q都是1024位甚至2048位的整数必须交给程序。理解扩展欧几里得的递归写法很重要这里给出一份可以直接跑的Python代码def egcd(a, b): if b 0: return a, 1, 0 g, x1, y1 egcd(b, a % b) return g, y1, x1 - (a // b) * y1 p 473398607161 q 4511491 e 17 phi (p - 1) * (q - 1) g, d, _ egcd(e, phi) d d % phi print(d)运行结果就是125631357777427553。代码里egcd返回的最大公约数g在这里其实用不上但保留它能让你看到这个算法的完整结构。d取模phi这一步是必须的因为扩展欧几里得求出来的x可能落在负数区间取模后才会变成0到φ(n)-1范围内的正数。如果你用的是Python 3.8及以上版本还有一个更省事的内建写法d pow(e, -1, phi) print(d)pow函数传入三个参数时是做模幂运算传入-1这个指数等价于求模逆元这是Python标准库自带的能力不需要安装任何第三方包。CTF场景中大家更常用gmpy2库因为gmpy2的底层是GMP大整数库运算速度比Python内置实现快得多import gmpy2 d gmpy2.invert(e, phi) print(d)三个方法得到的d完全一致因为数学上d在0到φ(n)-1之间是唯一的。你自己写一遍扩展欧几里得最大的收获是能看清它到底在干什么——它不是黑魔法只是把“找一组整数x、y使axbygcd(a,b)”这件事用递归手段做出来而已。2.3 验证用公钥加密、私钥解密跑个回环算出d之后怎么确定它没算错最直观的方法不是回头核对公式而是直接跑一个加解密回环。用公钥加密一条消息再用私钥解密如果最后得到的是原文说明d正确。n p * q m 20240701 c pow(m, e, n) m2 pow(c, d, n) print(m2)输出应该就是20240701。这一步的价值在于它把“求d”这个抽象问题变成了一个可验证的工程问题。如果你在回环测试中发现输出不等于原文那基本可以断定d算错了或者某个参数填错了位。这里要特别提醒pow(m, e, n)和pow(m, e) % n是两个完全不同的东西。前者是模幂运算Python在计算过程中会不断取模中间结果始终不会超过n的量级后者会先把m^e这个天文数字完整算出来再取模在RSA这种大数场景下这个中间结果可能比宇宙中的原子总数还大程序会直接卡死或内存溢出。养成用三参数pow的习惯是写RSA脚本的第一课。另外真实世界里的RSA不会像这道题一样裸奔。实际加密前要给明文做填充比如OAEP或者PKCS#1 v1.5否则会有很多数学攻击面。CTF里的easy_RSA属于教科书式裸RSA它故意省略了填充目的就是让你看清数学骨架而不是让你以为真实RSA就长这样。3. 一道easy_RSA背后的攻击面从CTF到真实案例3.1 为什么e要选65537低加密指数攻击初探easy_RSA里的e取的是17看起来很小。CTF里还经常见到e3的情况不少题目就靠这个做文章。那工程上为什么普遍选65537这个固定值因为e要小加密和验签才快但太小会出事。最典型的攻击是低加密指数攻击也叫小明文攻击。当e3并且明文m本身很小使得m³ n时密文c m³ mod n实际上就等于m³本身完全没有取模的效果。这种情况下攻击者只需要对c做整数开三次方就能直接还原明文mimport gmpy2 m gmpy2.iroot(c, 3)[0]一行代码RSA直接神化。为什么选65537因为它是费马素数二进制形式是1000000000000000001只有两个1计算模幂时性能很好同时它足够大不会再出现“m^e比n还小”的尴尬局面。这是一个典型的“安全性、性能、实现便利性”三者权衡的结果。看题的时候要学会识别信号如果一道CTF题给出很小的e、超大的n、很小的c第一反应就应该是“用iroot开个方试试”。这种信号驱动的解题方式在Crypto题目里非常重要。3.2 共模攻击同一n、两组(e, c)的利用还有一种高频考法是共模攻击。它的场景是同一个n下分别用两个不同的公钥指数e1、e2加密了同一条明文m攻击者拿到了两组密文c1、c2。因为e1和e2互素所以存在整数s、t使得e1 × s e2 × t 1然后可以通过如下方式恢复明文c1^s × c2^t ≡ m^(e1×s) × m^(e2×t) ≡ m^(e1×s e2×t) ≡ m (mod n)这个攻击的恐怖之处在于它完全不需要分解n只需要做扩展欧几里得和模幂运算就能直接拿到明文。代码实现也不复杂def egcd(a, b): if b 0: return a, 1, 0 g, x1, y1 egcd(b, a % b) return g, y1, x1 - (a // b) * y1 _, s, t egcd(e1, e2) if s 0: c1 pow(c1, -1, n) s -s if t 0: c2 pow(c2, -1, n) t -t m (pow(c1, s, n) * pow(c2, t, n)) % n这里有一个细节如果s或t是负数就要先对对应的密文做模逆元操作再取正指数。这跟前面求d时取模修正的思路一脉相承。现实世界里共模攻击对应的是“懒惰工程”有些系统为了省事让所有用户共用同一个模数n只是给不同用户分配不同的e。这种设计一旦被滥用明文就有被恢复的风险。CTF中如何识别这类题两个密文、同一个n、两个互素的e看到这个组合直接往共模攻击上想。3.3 公因子攻击多个公钥共用素数的灾难热搜词里有“rsa公因子的网络攻击案例”这其实对应CTF中非常经典的一类题型给你一堆n让你找出有共同素数的两个。攻击前提是两个模数共享同一个素数因子n1 p × q1 n2 p × q2此时只需要求n1和n2的最大公约数就能拿到pfrom math import gcd p gcd(n1, n2) q1 n1 // p q2 n2 // p拿到了p和q整个RSA就跟easy_RSA一样毫无秘密可言。这种攻击不是算法层面的突破而是随机数生成器质量差导致的灾难。真实案例里研究人员曾在物联网设备批量生成的证书中发现大量公钥共享同一个素数因子。原因很简单设备生成素数时使用了低熵的随机数源两个设备“碰巧”选中了同一个素数。这种问题跟RSA算法本身无关完全属于工程实现不当。在CTF题目中公因子攻击通常会成为一道题目的“突破口”。你拿到多个n单个看都很大无法分解但只要两两求gcd立刻就能戳穿它们的血缘关系。这也是我在实际刷题中最喜欢的一类题目代码只有几行但背后反映的安全教训极其深刻。3.4 软考与CTF的RSA计算题速算技巧对照搜热词里出现了“软考信息安全工程师密码学rsa计算题”这说明RSA不只是CTF玩家的专利也是软考的重要考点。考试是闭卷你不能跑Python所以手算技巧必须过关。软考常见的题型是给定p11、q13、e7求d。流程跟前面完全一样只是数字变小了n 11 × 13 143 φ(n) 10 × 12 120 求7在模120下的逆元这里可以直接用一个小技巧7 × 17 119 ≡ -1 (mod 120)所以7 × (-17) ≡ 1 (mod 120)于是d ≡ -17 ≡ 103 (mod 120)。验证一下7 × 103 721 6 × 120 1正确。这个“凑到φ(n)-1再取相反数”的技巧在手算模逆元时非常好用。只要e相对小先试着凑一个k让e×k接近φ(n)的整数倍再调整符号即可。如果需要计算密文c m^e mod n可以用快速幂。比如m2、e7、n1432^1 mod 143 2 2^2 mod 143 4 2^4 mod 143 16 2^7 2^4 × 2^2 × 2^1 ≡ 16 × 4 × 2 ≡ 128 (mod 143)考试中e一般不会给太大但如果e有几百上千一定要学会把指数拆成二进制用“平方-乘”的方法边算边取模。软考和CTF的差别在于一个限制工具、一个鼓励工具但底层数学是完全一致的。我建议两套技能都掌握理解公式能让你在CTF中快速选型手算熟练能让你在试卷上不丢分。4. 实操中的那些坑从刷题到工程落地4.1 d算出来是负数、结果是浮点数怎么办很多人在自己实现扩展欧几里得时会遇到一个经典问题求出来的d是负数。这太正常了因为扩展欧几里得返回的系数组合不唯一它只是保证等式成立没有保证x落在模数区间内。处理办法就是取模修正d d % phiPython的%运算结果恒为非负所以一次取模就够。如果你用Java或者C语言写注意它们对负数取模的处理方式不同常规修正是 d (d % phi phi) % phi。这个坑我在教学时见过无数次看起来是小事但会让整个解密结果全错。还有一个隐蔽的小坑除法符号。如果你不小心在代码里写了 phi (p - 1) * (q - 1) / 1Python会返回浮点数。浮点数参与的取模运算结果会带小数后续pow函数的模数参数如果出现浮点轻则精度丢失重则直接报错。正确的整数计算要注意除法部分确保使用//而不是/。4.2 大数计算与精度问题RSA里的数字动辄几十上百位很多语言的native整数类型根本放不下。Python的整数是任意精度的所以CTF里用Python做RSA非常顺手但这不等于你可以乱写幂运算。我见过一个典型错误用 pow(c, d) % n 替代 pow(c, d, n)。当d和n都是512位时pow(c, d)会计算一个天文数字级的中间结果程序轻则卡死重则直接内存溢出。三参数pow是专门为模幂运算设计的它在每次乘法后都会取模中间结果永远不会超过模数的平方量级。如果数据量特别大或者需要对大量候选值做分解、开方、求逆建议直接上gmpy2库。它的底层是GMP比Python内置的大数运算快一个数量级。另一个常用库是sympy适合做符号化简和小规模数论操作。CTF环境里装一下gmpy2基本能覆盖90%的RSA题型需求。4.3 在线工具与本地脚本怎么选网上有不少RSA相关的在线工具比如factordb.com可以查大整数分解结果有些站点提供模逆元计算。这类工具适合快速验证但不建议过度依赖。原因很简单私钥是敏感数据你把私钥相关参数贴到第三方网站等于把你的钥匙坯子交出去这种做法在真实工作环境里绝对要避免。CTF刷题时我就养成了一个习惯能本地跑脚本就本地跑在线工具只用来做“二次验证”。比如算出d之后再用另一个独立实现的方法复核一次这样可以避免因为单个脚本的隐藏bug导致提交失败。easy_RSA完全不需要联网前面那段Python脚本离线跑完直接提交答案即可。4.4 工程落地PB调用RSA时的“public key not find”这类问题热词里出现了“pb调用rsa加密算法”和“rsa public key not find”这是典型的“把RSA从CTF题搬到真实系统”后遇到的问题。PowerBuilder这类老语言调用RSA加密时报“public key not find”的常见原因我梳理过大概有这几种第一公钥字符串带了换行、空格或者多余字符Base64解码失败。你从证书文件或者配置文件里复制公钥时很容易混入看不见的换行符这在CTF环境里无所谓但在工程代码里就直接导致解析失败。第二公钥格式不匹配。PKCS#1格式的公钥和PKCS#8格式的公钥头部标记和ASN.1结构完全不同。“BEGIN RSA PUBLIC KEY”和“BEGIN PUBLIC KEY”指向的是两种DER封装混用就会出现找不到公钥的报错。用OpenSSL互转可以解决openssl rsa -in key.pem -pubin -RSAPublicKey_out -out pkcs1.pem 之类的操作可以切换格式。第三密钥容器没有初始化。有些库要求先加载密钥到内存对象中再执行加密操作顺序反了就会报“not find”。排查时先确认调用链是否在加密前正确装载了密钥。第四明文超长。RSA单次加密的明文长度受限于模数长度比如1024位密钥最多只能加密117字节明文PKCS#1 v1.5填充超长必须分段加密。如果你发现“能加密但解密失败”或者“公钥找不到”这类怪问题也要检查是不是数据长度触发了边界条件。下面的表可以当一个速查手册用现象可能原因处理方式d为负数扩展欧几里得返回负系数d d % phi解密回环失败模数、指数参数填错或填充不一致检查n、d、幂运算参数公钥字符串报错换行、空格、Base64损坏清理字符串后重新解码public key not findPKCS#1/PKCS#8格式不匹配用OpenSSL转换密钥格式加密后解密异常明文超过单次加密上限分段加密或使用混合加密我在实际项目中排过不少这类问题最后发现大多数时候不是RSA算法本身有毛病而是密钥格式和初始化环境在捣乱。CTF里那套数学正确性在工程里只是第一步。我当初刷easy_RSA的时候其实卡了挺久。不是不会算而是不敢相信答案真就这么简单反复用不同办法验了三遍才提交。后来才明白Crypto题就是这样一个领域数学原理一旦通了剩下的就是把原理翻译成代码。把这道题彻底吃透之后低加密指数攻击、共模攻击、公因子攻击再出现在眼前你一眼就能认出它们的套路因为内核都是同一套RSA数学骨架。做题如此工程上也一样——遇到RSA的问题先想清楚它卡在哪一环是参数、格式还是随机数而不是急着上网搜代码。