从一道CTF题解锁RSA数学推导的思维艺术

RSA算法作为现代密码学的基石，早已成为各类CTF竞赛的常客。但真正考验选手的往往不是标准RSA的实现，而是那些看似"离经叛道"的变种题目——它们要求选手抛开公式记忆，回归数学本质进行灵活推导。本文将以一道融合反三角函数与代数技巧的CTF题目为例，带你体验密码学破解中的数学艺术。

1. 题目解析与数学关系挖掘

当我们拿到这道EasyRSA题目时，首先注意到它给出了三个关键参数：密文c、神秘值z和模数n。与传统RSA不同，这里引入了一个看似复杂的z值定义：

z = Fraction(1,Derivative(arctan(p),p)) - Fraction(1,Derivative(arth(q),q))

第一步需要破解这个数学表达式的实际含义 。通过查阅sympy文档和微积分知识，我们可以解析出：

• Derivative(arctan(p),p) 表示arctan(p)对p的导数，即1/(1+p²)
• Derivative(arth(q),q) 表示artanh(q)对q的导数，即1/(1-q²)
• 因此z的表达式可简化为：

z = (1/(1/(1+p²))) - (1/(1/(1-q²))) = (1+p²) - (1-q²) = p² + q²

这个简化过程展示了密码学中 数学直觉 的重要性——能够识别复杂表达式背后的本质关系。现在，我们得到了两个核心方程：

1. n = p × q （标准RSA定义）
2. z = p² + q² （题目给出的额外条件）

2. 构建方程组的求解策略

有了这两个方程，我们需要解出p和q的值。这需要巧妙的代数技巧：

1. 首先回忆平方和公式：(p + q)² = p² + q² + 2pq
2. 将已知条件代入： (p + q)² = z + 2n
3. 同理可得：(p - q)² = z - 2n

通过这两个推导，我们可以建立以下求解步骤：

# 计算p+q和p-q的值
p_add_q, _ = iroot(z + 2*n, 2)  # 平方根计算
p_sub_q, _ = iroot(z - 2*n, 2)   # 平方根计算

# 解出p和q
p = (p_add_q + p_sub_q) // 2
q = (p_add_q - p_sub_q) // 2

这个解法展示了如何将 代数技巧 与 编程实现 相结合。关键在于：

• 识别出(p+q)和(p-q)与已知量z、n的关系
• 使用平方根运算还原中间变量
• 通过简单的加减法解出原始变量

3. Python实现与验证

为了确保我们的推导正确，下面用Python实现完整的解题流程：

from Crypto.Util.number import long_to_bytes
from gmpy2 import iroot, invert

# 题目给定值
c = 7922547866857761459807491502654216283012776177789511549350672958101810281348402284098310147796549430689253803510994877420135537268549410652654479620858691324110367182025648788407041599943091386227543182157746202947099572389676084392706406084307657000104665696654409155006313203957292885743791715198781974205578654792123191584957665293208390453748369182333152809882312453359706147808198922916762773721726681588977103877454119043744889164529383188077499194932909643918696646876907327364751380953182517883134591810800848971719184808713694342985458103006676013451912221080252735948993692674899399826084848622145815461035
z = 32115748677623209667471622872185275070257924766015020072805267359839059393284316595882933372289732127274076434587519333300142473010344694803885168557548801202495933226215437763329280242113556524498457559562872900811602056944423967403777623306961880757613246328729616643032628964072931272085866928045973799374711846825157781056965164178505232524245809179235607571567174228822561697888645968559343608375331988097157145264357626738141646556353500994924115875748198318036296898604097000938272195903056733565880150540275369239637793975923329598716003350308259321436752579291000355560431542229699759955141152914708362494482
n = 15310745161336895413406690009324766200789179248896951942047235448901612351128459309145825547569298479821101249094161867207686537607047447968708758990950136380924747359052570549594098569970632854351825950729752563502284849263730127586382522703959893392329333760927637353052250274195821469023401443841395096410231843592101426591882573405934188675124326997277775238287928403743324297705151732524641213516306585297722190780088180705070359469719869343939106529204798285957516860774384001892777525916167743272419958572055332232056095979448155082465977781482598371994798871917514767508394730447974770329967681767625495394441

# 计算p+q和p-q
p_add_q, _ = iroot(z + 2*n, 2)
p_sub_q, _ = iroot(z - 2*n, 2)

# 解出p和q
p = (p_add_q + p_sub_q) // 2
q = (p_add_q - p_sub_q) // 2

# 验证计算是否正确
assert p * q == n
assert p**2 + q**2 == z

# 标准RSA解密流程
e = 65537
phi = (p-1)*(q-1)
d = invert(e, phi)
m = pow(c, d, n)
flag = long_to_bytes(m)
print(flag)

关键验证步骤 确保了我们的解是正确的：

1. 检查p×q是否等于n
2. 检查p²+q²是否等于z
3. 只有通过这两个验证，才能确保后续解密的有效性

4. 密码学竞赛的思维训练

这道题目给我们展示了CTF密码学题目的典型解题思路：

1. 逆向思维 ：从给定的输出反推输入
2. 数学转化 ：将复杂表达式简化为基本数学关系
3. 系统构建 ：建立方程组并寻找解法
4. 编程实现 ：将数学推导转化为可执行代码

在实战中，我们还需要注意以下常见陷阱：

陷阱类型	防范措施	本题中的应用
数学简化错误	逐步验证每一步推导	确认z的简化过程正确
整数运算误差	使用高精度计算库	采用gmpy2进行大数运算
边界条件遗漏	添加断言检查	验证p*q=n和p²+q²=z
算法选择不当	了解时间复杂度	平方根运算效率可接受

这类题目训练的核心能力是 将抽象的数学知识转化为具体的解题步骤 。在实际CTF比赛中，这种能力往往比记住标准算法更重要。

5. 扩展思考：RSA变种题目的解题框架

通过这道题，我们可以总结出解决非标准RSA题目的通用方法：

1. 参数分析 ：识别题目给出的所有参数及其关系
2. 数学建模 ：建立参数间的数学方程
3. 理论求解 ：在数学层面推导解法
4. 编程实现 ：用代码实现数学推导
5. 验证检查 ：确保中间步骤的正确性

对于想深入密码学的学习者，建议：

• 夯实数论基础（模运算、素数理论等）
• 熟悉常见加密算法的标准实现
• 练习将数学论文中的结论转化为代码
• 参与CTF比赛积累实战经验

密码学的魅力正在于这种 理论与实践的完美结合 ——既需要严谨的数学思维，又需要灵活的编程实现。当你能自如地在两者间切换时，那些看似复杂的加密系统将逐渐展现出它们内在的美学结构。