CTF新手必看：手把手教你用Python分解大整数，搞定那道经典的Alice与Bob题

CTF密码学入门：从大整数分解到MD5哈希的全链路实战

第一次参加CTF比赛时，我盯着那道关于Alice和Bob的密码学题目发呆了半小时。屏幕上那个长达11位的数字98554799767仿佛在嘲笑我的无知。直到一位前辈拍了拍我的肩膀说："知道Pollard Rho算法吗？它能让这个大整数像黄油一样被切开。"那一刻，我意识到密码学挑战并非遥不可及。本文将带你用Python重现这个经典解题过程，不仅告诉你"怎么做"，更解释"为什么这么做"。

1. 理解题目本质与密码学背景

在CTF竞赛中，大整数分解问题通常属于密码学中的"数学难题"类挑战。这类题目往往模拟了现实世界中RSA加密系统的核心弱点——当大整数难以被分解时，系统是安全的；而一旦成功分解，整个加密体系就会被攻破。

题目给出的数字98554799767需要被分解为两个素数，这直接对应了RSA算法中模数n=p×q的特性。在真实的CTF比赛中，这类题目通常考察三个核心能力：

1. 数学算法实现：能否编程实现因数分解算法
2. 工具链使用：是否掌握验证素数和计算哈希的工具
3. 解题流程规范：是否遵循题目要求的输出格式

初学者常犯的错误包括：忘记验证分解结果是否为素数、拼接顺序错误、哈希计算时包含多余空格等。有经验的选手会建立标准化流程来避免这些低级失误。

提示：在本地保存一个crypto_utils.py文件，积累常用的素数检测、哈希计算等函数，可以大幅提高解题效率

2. 搭建Python密码学实验环境

工欲善其事，必先利其器。我们先配置一个适合密码学实验的Python环境：

# 创建虚拟环境 python -m venv crypto_env source crypto_env/bin/activate # Linux/Mac crypto_env\Scripts\activate # Windows # 安装必要库 pip install pycryptodome gmpy2 sympy

核心库的功能说明：

基础环境准备好后，我们创建一个新的Python文件alice_bob.py，开始实现解题逻辑。建议采用以下项目结构：

/ctf-challenge │── alice_bob.py # 主解题脚本 │── crypto_utils.py # 通用密码学函数 │── tests/ # 单元测试 │── test_factoring.py

3. Pollard Rho算法深度解析与实现

Pollard Rho算法是John Pollard在1975年提出的因数分解算法，特别适合分解具有小质因数的大整数。其核心思想基于生日悖论和Floyd判圈算法，时间复杂度约为O(√p)，其中p是n的最小质因数。

3.1 算法数学原理

算法使用一个伪随机函数f(x) = (x² + c) mod n来生成序列，通常选择c=1。为什么选择x²+1这个函数？主要有三个原因：

1. 计算简单高效
2. 能产生足够"随机"的序列
3. 避免陷入固定点（如选择f(x)=x²会卡在0和1）

算法的关键在于：当x ≡ y mod p (p是n的一个因数)时，gcd(x-y, n)会给出p的倍数。由于我们不知道p，所以通过计算gcd(abs(x_i - x_{2i}), n)来寻找。

3.2 Python实现代码

以下是带有详细注释的Pollard Rho实现：

from random import randint from math import gcd import sys def pollard_rho(n, max_iter=100000): """Pollard's Rho算法实现""" if n % 2 == 0: return 2 if n % 3 == 0: return 3 if n % 5 == 0: return 5 while True: # 随机选择初始值和常数c c = randint(1, n-1) f = lambda x: (pow(x, 2, n) + c) % n x, y, d = 2, 2, 1 for _ in range(max_iter): x = f(x) y = f(f(y)) d = gcd(abs(x-y), n) if d == n: break # 失败，重新选择c if d > 1: return d # 超过最大迭代次数仍未找到因数 raise ValueError("分解失败，尝试增加max_iter或更换算法") def factorize(n): """递归分解整数""" factors = [] def _factorize(n): if n == 1: return if is_prime(n): factors.append(n) return d = pollard_rho(n) _factorize(d) _factorize(n // d) _factorize(n) return sorted(factors)

3.3 素数检测优化

高效的素数检测对算法性能至关重要。我们采用Miller-Rabin测试的确定性变体：

def is_prime(n, k=5): """Miller-Rabin素数检测""" if n <= 1: return False for p in [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]: if n % p == 0: return n == p d = n - 1 s = 0 while d % 2 == 0: d //= 2 s += 1 for a in [2, 325, 9375, 28178, 450775, 9780504, 1795265022]: if a >= n: continue x = pow(a, d, n) if x == 1 or x == n - 1: continue for _ in range(s - 1): x = pow(x, 2, n) if x == n - 1: break else: return False return True

4. 完整解题流程实现

现在我们将各个模块组合成完整的解题流程：

import hashlib def solve_challenge(n): # 步骤1：因数分解 factors = factorize(n) if len(factors) != 2: raise ValueError("分解结果不是两个素数") # 步骤2：验证素数并排序 p, q = sorted(factors) if not (is_prime(p) and is_prime(q)): raise ValueError("分解结果包含非素数") # 步骤3：拼接数字 combined = int(f"{p}{q}") # 步骤4：计算MD5哈希 md5_hash = hashlib.md5(str(combined).encode()).hexdigest() return { "factors": (p, q), "combined": combined, "md5_hash": md5_hash } if __name__ == "__main__": n = 98554799767 result = solve_challenge(n) print(f"分解结果: {result['factors']}") print(f"组合数字: {result['combined']}") print(f"MD5哈希值: {result['md5_hash']}")

执行这个脚本，你应该能看到如下输出：

分解结果: (101999, 966233) 组合数字: 101999966233 MD5哈希值: d450209323a847c8d01c6be47c81811a

5. 验证与调试技巧

在实际CTF比赛中，验证每个步骤的正确性至关重要。以下是一些实用技巧：

5.1 在线工具验证

• 素数验证：使用Wolfram Alpha输入"isprime(101999)"进行验证
• 因数分解：factordb.com可以查询已知整数的因数
• MD5计算：Linux系统终端命令echo -n "101999966233" | md5sum

5.2 常见错误排查

1. 算法不收敛：尝试增加Pollard Rho的max_iter参数或更换随机种子
2. 错误的结果：检查素数检测函数是否正确，特别是边缘情况
3. 哈希不匹配：确保没有在字符串中添加额外空格或换行符

5.3 性能优化建议

对于更大的整数（如300+位），可以考虑以下优化：

1. 使用gmpy2库的mpz类型处理大整数
2. 实现更高效的因数分解算法如Quadratic Sieve
3. 添加并行计算支持

# 使用gmpy2加速的版本示例 import gmpy2 from gmpy2 import mpz def pollard_rho_gmpy2(n): n = mpz(n) if gmpy2.is_prime(n): return n while True: c = gmpy2.mpz_random(gmpy2.random_state(), n-3) + 1 f = lambda x: (gmpy2.powmod(x, 2, n) + c) % n x, y, d = mpz(2), mpz(2), mpz(1) while d == 1: x = f(x) y = f(f(y)) d = gmpy2.gcd(abs(x-y), n) if d != n: return d

6. 扩展应用与类似题目

掌握大整数分解技术后，你可以解决许多CTF密码学题目。以下是一些变体类型：

1. 多素数RSA：n由多个素数相乘组成，需要全部分解
2. 弱密钥检测：当p和q接近时，使用Fermat分解更高效
3. 已知部分信息：当知道p或q的部分位时，使用Coppersmith方法

例如，BUUCTF的另一道题目给出了n和e，要求解密消息。解题步骤通常是：

1. 分解n得到p和q
2. 计算φ(n) = (p-1)(q-1)
3. 求d ≡ e⁻¹ mod φ(n)
4. 使用pow(c, d, n)解密密文c

在本地测试时，可以构造一个简单的RSA示例来验证你的代码：

from Crypto.Util.number import getPrime, inverse p, q = getPrime(512), getPrime(512) n = p * q e = 65537 phi = (p-1)*(q-1) d = inverse(e, phi) msg = 123456789 cipher = pow(msg, e, n) decrypted = pow(cipher, d, n) assert msg == decrypted

7. 建立密码学解题工具库

长期参与CTF比赛，建议建立自己的密码学工具库。以下是推荐的功能模块：

• 数论工具：

  • 模逆元计算
  • 中国剩余定理实现
  • 离散对数求解

• RSA相关：

  • 常见攻击实现（Wiener、Hastad等）
  • 多线程Pollard Rho
  • 小指数检测

• 实用函数：

  def bytes_to_long(b): return int.from_bytes(b, 'big') def long_to_bytes(n): return n.to_bytes((n.bit_length()+7)//8, 'big') def root(n, k): """计算整数n的k次方根""" low = 1 high = n while low < high: mid = (low + high) // 2 if mid**k < n: low = mid + 1 else: high = mid return low if low**k == n else low - 1

将这些工具整理成模块后，未来的CTF挑战会变得轻松许多。比如遇到需要计算离散对数的题目，可以直接调用已有实现，而不必每次都从头编写。