[CTF实战解析] 从一道EasyRSA题目看RSA加密中的数学关系与参数推导

1. 从一道EasyRSA题目看RSA加密的核心数学关系第一次看到这道EasyRSA题目时我承认自己有点懵。题目给出了三个关键参数密文c、神秘参数z和模数n。最让人困惑的就是这个z它既不是常见的公钥指数e也不是标准的私钥参数。但仔细分析题目源码后我发现z的定义暗藏玄机zFraction(1,Derivative(arctan(p),p))-Fraction(1,Derivative(arth(q),q))这里用到了sympy库的导数计算和分数表示。经过查阅资料和实际推导我发现arctan(p)的导数是1/(1p²)arth(q)反双曲正切的导数是1/(1-q²)。于是z的表达式可以简化为z (1p²) - (1-q²) p² q²这个发现让我眼前一亮现在我们有n p × q RSA标准定义z p² q² 题目特殊关系这两个方程就像拼图的两块只要找到合适的数学工具就能解出p和q。这让我想起初中学过的代数公式(pq)² p² q² 2pq z 2n。这个简单的变形将成为我们破解的关键。2. 逆向推导RSA参数的完整过程2.1 从z和n推导pq与p-q有了前面的数学关系我们可以建立一个方程组来解出p和q。具体步骤如下计算(pq)² z 2n计算(p-q)² z - 2n对两边开平方得到pq √(z 2n)p-q √(z - 2n)在实际操作中我们需要确保开平方能得到整数结果。这里可以用gmpy2库的iroot函数进行整数开方from gmpy2 import iroot paddq, _ iroot(z 2*n, 2) # pq pmulq, _ iroot(z - 2*n, 2) # p-q2.2 解出素数p和q得到pq和p-q后解这个二元一次方程就简单了p (paddq pmulq) // 2 q paddq - p # 或者 q (paddq - pmulq) // 2这里需要注意检查p和q是否为素数。在实际CTF比赛中题目设计通常会确保这些值是素数但在真实场景中一定要验证from Crypto.Util.number import isPrime assert isPrime(p) and isPrime(q)2.3 计算私钥和解密有了p和q后续就是标准的RSA解密流程了计算欧拉函数 φ(n) (p-1)(q-1)计算私钥指数 d ≡ e⁻¹ mod φ(n)解密明文 m ≡ cᵈ mod n对应的Python实现phi (p-1) * (q-1) d pow(e, -1, phi) # Python 3.8可以直接用模逆元 m pow(c, d, n) flag bytes.fromhex(hex(m)[2:])3. 完整解题脚本与关键点解析把上述步骤整合起来完整的解题脚本如下from Crypto.Util.number import long_to_bytes from gmpy2 import iroot # 题目给出的参数 c 7922547866857761459807491502654216283012776177789511549350672958101810281348402284098310147796549430689253803510994877420135537268549410652654479620858691324110367182025648788407041599943091386227543182157746202947099572389676084392706406084307657000104665696654409155006313203957292885743791715198781974205578654792123191584957665293208390453748369182333152809882312453359706147808198922916762773721726681588977103877454119043744889164529383188077499194932909643918696646876907327364751380953182517883134591810800848971719184808713694342985458103006676013451912221080252735948993692674899399826084848622145815461035 z 32115748677623209667471622872185275070257924766015020072805267359839059393284316595882933372289732127274076434587519333300142473010344694803885168557548801202495933226215437763329280242113556524498457559562872900811602056944423967403777623306961880757613246328729616643032628964072931272085866928045973799374711846825157781056965164178505232524245809179235607571567174228822561697888645968559343608375331988097157145264357626738141646556353500994924115875748198318036296898604097000938272195903056733565880150540275369239637793975923329598716003350308259321436752579291000355560431542229699759955141152914708362494482 n 15310745161336895413406690009324766200789179248896951942047235448901612351128459309145825547569298479821101249094161867207686537607047447968708758990950136380924747359052570549594098569970632854351825950729752563502284849263730127586382522703959893392329333760927637353052250274195821469023401443841395096410231843592101426591882573405934188675124326997277775238287928403743324297705151732524641213516306585297722190780088180705070359469719869343939106529204798285957516860774384001892777525916167743272419958572055332232056095979448155082465977781482598371994798871917514767508394730447974770329967681767625495394441 e 65537 # 关键推导步骤 paddq, _ iroot(z 2*n, 2) # pq pmulq, _ iroot(z - 2*n, 2) # p-q p (paddq pmulq) // 2 q paddq - p # 标准RSA解密 phi (p-1) * (q-1) d pow(e, -1, phi) m pow(c, d, n) print(long_to_bytes(m))这个脚本中有几个容易踩坑的地方整数开方的精度处理iroot返回的是一个元组第二个值是是否完全平方的标志但本题中我们可以忽略这个检查大数运算的整除Python 3中//运算符会自动处理大整数但要注意确保被除数是偶数字节转换的边界情况long_to_bytes可能会因为m的十六进制表示长度奇数而出错这时需要手动处理4. RSA数学原理的深入理解4.1 为什么z p² q²能破解RSA这道题的关键在于给出了n和z两个独立方程使得我们可以解出p和q。在标准RSA中只知道npq时分解n是困难的这正是RSA安全性的基础。但题目额外给出了p²q²相当于多了一个约束条件。这类似于我们知道两个数的和与积设pq Spq n那么(p-q)² S² - 4np和q就是[S ± √(S²-4n)]/2在本题中我们通过z p²q²构造了类似的方程组只是形式稍有不同。4.2 RSA参数关系的其他变种CTF比赛中常见的RSA变种题目包括给出pq和n给出p-q和n给出φ(n)和n给出d和e每种情况都需要特定的数学技巧。例如如果知道φ(n)可以通过φ(n) n - (pq) 1建立方程。4.3 实际应用中的安全考量虽然这道题展示了一种特殊情况下的RSA破解方法但在真实场景中绝不会泄露与p、q相关的额外信息使用足够大的素数至少2048位确保p和q的差值足够大防止费马分解法我曾经在一个真实项目中遇到过RSA密钥生成的问题当时使用的伪随机数发生器不够安全导致生成的p和q有一定关联性差点造成安全隐患。这让我深刻理解到密码学实现中细节的重要性。