CTF密码学实战：从数学推导到Python脚本破解RSA

第一次参加CTF比赛时，我盯着那道RSA密码题整整两小时毫无头绪。直到一位资深选手拍了拍我肩膀说："CTF中的RSA从来不是考加密算法本身，而是考察你如何从看似杂乱的信息中重建数学关系。"这句话彻底改变了我解题的思路。今天，我们就以一道典型CTF题为例，完整展示从题目分析到脚本编写的全流程思维。

1. 题目分析与数学关系拆解

拿到题目后，我们首先看到三个关键输出：密文c、神秘参数z和模数n。根据题目描述：

p=getPrime(1024)
q=getPrime(1024)
n=p*q
z=Fraction(1,Derivative(arctan(p),p))-Fraction(1,Derivative(arth(q),q))

关键突破点 在于理解z的数学含义。通过查阅sympy文档和数学手册，我们发现：

• Derivative(arctan(p),p) 实际上是求arctan(p)对p的导数，即1/(1+p²)
• Derivative(arth(q),q) 是反双曲正切函数的导数，等于1/(1-q²)
• 因此z可以简化为：z = (1+p²) - (1-q²) = p² + q²

这个转换将看似复杂的符号计算简化为清晰的数学关系。现在我们有：

n = p × q
z = p² + q²

2. 从z和n推导p、q的数学方法

有了这两个方程，我们可以构建一个二元二次方程组来解出p和q。具体推导过程如下：

1. 我们知道 (p + q)² = p² + q² + 2pq = z + 2n
2. 同理 (p - q)² = p² + q² - 2pq = z - 2n
3. 因此可以得到：

   p_plus_q = isqrt(z + 2*n)  # 整数平方根
   p_minus_q = isqrt(z - 2*n)  # 整数平方根
   

4. 最后解出：

   p = (p_plus_q + p_minus_q) // 2
   q = (p_plus_q - p_minus_q) // 2
   

这里需要注意 大整数平方根计算 的精度问题。普通Python的math.sqrt对超大整数会有精度损失，必须使用gmpy2库的iroot函数：

from gmpy2 import iroot

p_plus_q, exact = iroot(z + 2*n, 2)
if not exact:
    print("Warning: 可能不是完全平方数")

3. 完整Python解密脚本实现

结合以上分析，我们可以编写完整的解密脚本。这里使用Python的Crypto库和gmpy2库：

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

# 题目给出的数据
c = 7922547866857761459807491502654216283012776177789511549350672958101810281348402284098310147796549430689253803510994877420135537268549410652654479620858691324110367182025648788407041599943091386227543182157746202947099572389676084392706406084307657000104665696654409155006313203957292885743791715198781974205578654792123191584957665293208390453748369182333152809882312453359706147808198922916762773721726681588977103877454119043744889164529383188077499194932909643918696646876907327364751380953182517883134591810800848971719184808713694342985458103006676013451912221080252735948993692674899399826084848622145815461035
z = 32115748677623209667471622872185275070257924766015020072805267359839059393284316595882933372289732127274076434587519333300142473010344694803885168557548801202495933226215437763329280242113556524498457559562872900811602056944423967403777623306961880757613246328729616643032628964072931272085866928045973799374711846825157781056965164178505232524245809179235607571567174228822561697888645968559343608375331988097157145264357626738141646556353500994924115875748198318036296898604097000938272195903056733565880150540275369239637793975923329598716003350308259321436752579291000355560431542229699759955141152914708362494482
n = 15310745161336895413406690009324766200789179248896951942047235448901612351128459309145825547569298479821101249094161867207686537607047447968708758990950136380924747359052570549594098569970632854351825950729752563502284849263730127586382522703959893392329333760927637353052250274195821469023401443841395096410231843592101426591882573405934188675124326997277775238287928403743324297705151732524641213516306585297722190780088180705070359469719869343939106529204798285957516860774384001892777525916167743272419958572055332232056095979448155082465977781482598371994798871917514767508394730447974770329967681767625495394441
e = 65537

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

p = (p_plus_q + p_minus_q) // 2
q = (p_plus_q - p_minus_q) // 2

# 验证计算是否正确
assert p * q == n, "p和q计算有误！"

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

flag = long_to_bytes(m)
print(flag.decode())

4. 实战中的常见问题与调试技巧

在实际解题过程中，可能会遇到各种意外情况。以下是几个常见问题及解决方法：

问题1：平方根计算结果不是整数

p_plus_q, exact = iroot(z + 2*n, 2)
if not exact:
    # 检查z的计算是否正确
    # 可能需要重新审视题目给出的z表达式

问题2：解出的p和q乘积不等于n

if p * q != n:
    # 可能是计算过程中整数除法的问题
    # 尝试调整计算顺序或检查中间变量类型
    # 有时需要+1或-1微调
    for delta in [-2, -1, 0, 1, 2]:
        p_candidate = (p_plus_q + p_minus_q + delta) // 2
        if n % p_candidate == 0:
            p = p_candidate
            q = n // p
            break

问题3：解密后的flag乱码

可能原因及解决方法：

1. 字节序问题 ：尝试不同的编码方式

   print(flag.decode('utf-8', errors='ignore'))
   

2. 解密错误 ：检查d的计算是否正确

   assert (e * d) % phi == 1, "d值计算有误"
   

3. 数据截断 ：可能需要处理填充字节

   flag = flag.replace(b'\x00', b'')
   

5. CTF密码学进阶技巧

掌握了基础解法后，我们可以进一步优化解题流程：

技巧1：自动化数学关系识别

对于复杂的数学表达式，可以使用SymPy进行符号计算：

from sympy import symbols, diff, atan, atanh

p, q = symbols('p q')
expr1 = 1/diff(atan(p), p)
expr2 = 1/diff(atanh(q), q)
z_simplified = expr1 - expr2  # 输出p**2 + q**2

技巧2：多线程爆破辅助

当部分参数不确定时，可以结合爆破：

from concurrent.futures import ThreadPoolExecutor

def try_solve(delta):
    p_candidate = (p_plus_q + p_minus_q + delta) // 2
    if n % p_candidate == 0:
        return p_candidate

with ThreadPoolExecutor() as executor:
    results = executor.map(try_solve, range(-10, 10))
    p = next(r for r in results if r is not None)

技巧3：RSA参数快速验证

建立一套参数检查流程：

def validate_rsa_params(p, q, n, e, d=None):
    checks = [
        ('n == p*q', n == p*q),
        ('p是素数', is_prime(p)),
        ('q是素数', is_prime(q)),
        ('e与phi互质', gcd(e, (p-1)*(q-1)) == 1)
    ]
    if d is not None:
        checks.append(('d有效', (e*d) % ((p-1)*(q-1)) == 1))
    
    for name, result in checks:
        print(f"{name}: {'✓' if result else '✗'}")

6. 密码学题目资源与训练建议

想要在CTF密码学领域快速提升，需要系统的训练方法：

推荐学习路径

1. 基础理论 ：

   • 《应用密码学》Bruce Schneier
   • Cryptopals挑战题（https://cryptopals.com/）

2. CTF专项训练 ：

   • CTFtime上的RSA分类题目
   • PicoCTF的密码学题库

3. 工具掌握 ：

   # 常用工具列表
   pip install gmpy2 pycryptodome sage sympy
   

训练方法建议

• 每周至少解3道中等难度密码题
• 建立自己的密码学代码片段库
• 参加线上CTF比赛实战演练
• 复盘每道题的至少两种解法

典型题目特征分析

题目类型	关键特征	解题思路
基础RSA	给出p,q,e,c	直接计算私钥d解密
参数关系	给出n和p,q的关系式	建立方程求解
小指数攻击	e很小(如3)	直接开方或Coppersmith
共模攻击	相同n不同e	扩展欧几里得算法
选择密文	可查询解密oracle	利用乘法性质攻击

在CTF比赛中，密码学题目往往是最容易"一分耕耘一分收获"的领域。通过系统性的数学训练和编程实践，大多数RSA相关问题都能在30分钟内解决。记住，关键在于培养从复杂表达式中识别数学关系的能力，这比记忆特定攻击方法更重要。