从PolarCTF一道Crypto题看群同构：如何把自定义加法变成乘法来秒解离散对数？
从群同构到离散对数：PolarCTF Crypto题"trod"的数学洞察与实战解析
1. 挑战背景与问题抽象
在PolarCTF 2025冬季个人挑战赛中，一道名为"trod"的密码学题目展示了一个基于Python实现的加密系统，其核心是定义了一套非标准的加法运算规则。题目给出了两个点在自定义加法群中的运算公式：
x₃ = (x₁x₂ - x₁y₂ - x₂y₁ + 2y₁y₂)/(x₁ + x₂ - y₁ - y₂ - 1) y₃ = (y₁y₂)/(x₁ + x₂ - y₁ - y₂ - 1)通过代数变形可以发现，存在一个群同构映射φ将这种复杂的加法运算转换为模p乘法运算：
φ((x,y)) = (x-y)/y mod p满足φ(A+B) ≡ φ(A)×φ(B) mod p。这实际上将原问题转化为离散对数问题(DLP)：已知A = aliceSecret·g，求aliceSecret满足φ(A) ≡ φ(g)^aliceSecret mod p。
2. 同构映射的构造原理
2.1 群同构的数学基础
群同构的核心在于保持运算结构不变。对于题目定义的特殊加法群G和乘法群(ℤₚ*, ×)，我们需要证明：
- 映射的双射性：φ是双射（一一对应）
- 运算保持性：φ(a⊕b) = φ(a)⊗φ(b)
通过数学推导可以发现，给定的φ映射确实满足这些性质。关键在于观察到：
(x₁,y₁)⊕(x₂,y₂) → (x₃,y₃) ⇒ φ(x₃,y₃) ≡ φ(x₁,y₁)×φ(x₂,y₂) mod p2.2 同构构造的启发式方法
在实际解题中，如何想到这样的同构映射？以下是可能的思路路径：
- 观察运算分母：发现所有运算共享相同分母D = x₁+x₂-y₁-y₂-1
- 寻找不变量：尝试构造(x,y)的组合使得D能被约去
- 试探线性组合：尝试(x-y)/y形式，验证其运算保持性
提示：在CTF密码题中，当遇到复杂运算时，尝试寻找与简单运算（如乘法）的同构关系是常见策略
3. Pohlig-Hellman算法的适用条件
3.1 算法原理概述
Pohlig-Hellman算法适用于当群阶的素因子都较小时的离散对数问题。其核心思想是将问题分解到每个素因子的子群中求解，最后用中国剩余定理组合结果。
算法效率取决于群阶n=p-1的分解：
- 若n = ∏p_i^e_i，且max(p_i^e_i)足够小
- 则算法复杂度为O(∑e_i(log n + √p_i))
3.2 本题中的具体应用
在题目中，p-1的分解决定了Pohlig-Hellman的可行性。使用SageMath的discrete_log函数（基于Pohlig-Hellman）可以高效求解：
# SageMath示例代码 p = 518176062457782304884612410952519332834134329945067733347561865398388593 K = GF(p) g_prime = K(φ(g)) # 将生成元映射到乘法群 A_prime = K(φ(A)) # 将目标点映射到乘法群 # 求解离散对数 alice_secret = discrete_log(A_prime, g_prime) print(f"Alice's secret: {alice_secret}")4. 完整解题流程与实现
4.1 解题步骤分解
实现群运算和同构映射：
def add(a, b, p): if a == -1: return b if b == -1: return a x1,y1 = a; x2,y2 = b D = (x1 + x2 - y1 - y2 - 1) % p inv_D = pow(D, -1, p) x3 = (x1*x2 - x1*y2 - x2*y1 + 2*y1*y2) * inv_D % p y3 = (y1 * y2) * inv_D % p return (x3, y3) def phi(P, p): x,y = P return (x - y) * pow(y, -1, p) % p转换问题到乘法群：
g_prime = phi(g, p) A_prime = phi(A, p)求解离散对数：
alice_secret = discrete_log(A_prime, g_prime, operation='*')计算共享密钥：
shared_secret = multiply(B, alice_secret, p)
4.2 关键代码实现
from Crypto.Util.number import long_to_bytes # 题目参数 p = 0x123... # 实际大素数 g = (0x123..., 0x456...) # 生成元 A = (0x789..., 0xabc...) # Alice的公钥 B = (0xdef..., 0xghi...) # Bob的公钥 encrypted = 0x1122334455667788 # 密文 # 同构映射 def phi(P, p): x,y = P return (x-y) * pow(y, -1, p) % p # 转换到乘法群 g_prime = phi(g, p) A_prime = phi(A, p) # 求解离散对数 alice_secret = discrete_log(A_prime, g_prime) # 计算共享密钥 shared_point = multiply(B, alice_secret, p) master_key = shared_point[0] * shared_point[1] % p flag = long_to_bytes(encrypted ^^ master_key) print(flag.decode())5. 密码学启示与扩展思考
5.1 群同构在密码分析中的应用
群同构攻击的核心在于找到复杂群与简单群之间的结构保持映射。这种技术不仅适用于本题，还出现在：
- 椭圆曲线密码中奇异曲线的归约
- 基于配对的双线性映射攻击
- 多项式环到整数环的同构
5.2 防御措施与最佳实践
为防止此类攻击：
- 群选择：使用安全性证明的群结构
- 参数验证：检查是否存在非预期同构
- 密钥派生：使用安全的KDF处理原始密钥材料
实际工程中，应避免使用自定义的群运算结构，优先选择标准化、经过充分研究的密码方案
6. 实战技巧与调试建议
中间验证：逐步验证同构映射的正确性
# 验证同构性质 P, Q = (g, add(g,g,p)) assert phi(add(P,Q), p) == phi(P,p)*phi(Q,p) % p小参数测试：先用小素数验证整个流程
边界处理：特别注意分母为零的情况
7. 总结与延伸
通过这道题目，我们深入理解了：
- 如何识别和构造群同构
- 将复杂运算归约到已知问题的技巧
- Pohlig-Hellman算法的实际应用
这种将抽象代数应用于密码分析的能力，是解决现代CTF密码题目的关键。建议进一步研究：
- 椭圆曲线密码的特殊攻击
- 指数积分法在高阶群的应用
- 同构密码学的前沿发展
在CTF竞赛中，遇到非标准加密系统时，尝试寻找与经典问题的同构关系往往是突破口。这种"问题转化"的思维方式，在密码分析和算法设计中都具有重要价值。