GHCTF2025 Crypto题目解析与教学文档

GHCTF2025 Crypto题目解析与教学文档 1. baby_ signin 题目描述 RSA加密问题，其中 gcd(e,(p-1)*(q-1)) = 4 （最大公因数为4）。 解题方法 有限域开方 ：由于公因数不为1，不能直接使用常规RSA解密方法 需要计算模数的四次根（因为最大公因数为4） 解决步骤 计算 n = p*q 计算 phi = (p-1)*(q-1) 确认 gcd(e, phi) = 4 使用有限域开方算法求解密文模四次根 2. baby_ factor 题目描述 标准的RSA解密问题。 解题方法 常规RSA解密流程 解决步骤 分解n得到p和q 计算 phi = (p-1)*(q-1) 计算 d = inverse(e, phi) 解密 m = pow(c, d, n) 3. EZ_ Fermat 题目描述 多项式方程求解问题。 解题方法 费马分解法 ：用于分解大整数 先将x=1代入方程得到f(1) 解决步骤 将x=1代入多项式方程，计算f(1) 使用费马分解法分解得到的值 从分解结果中提取关键信息 4. baby_ factor_ revenge 题目描述 已知phi分解n的问题，类似于NKCTF2023的ezRSA part1。 解题方法 已知phi分解n ：利用phi和n的关系分解模数 遍历三个因子组合 解决步骤 已知phi(n)，建立方程 phi(n) = (p-1)*(q-1)*(r-1) （假设n有三个素因子） 解方程得到可能的p,q,r值 遍历所有可能的因子组合 验证每个组合的正确性 5. baby_ lattice 题目描述 隐藏数问题(HNP)，类似于BabyHNP问题。 解题方法 格基约减 ：构造适当的格来解决问题 参考构格方式： Dexter's Blog 解决步骤 根据题目描述构造格 使用LLL算法进行格基约减 从约减结果中提取key 使用key解密AES加密的内容 6. MIMT_ RSA 题目描述 中间相遇攻击RSA问题，key为36位。 解题方法 中间相遇攻击 ：将key分解为两部分分别爆破 将 ck = key^e mod n 拆分为 ck = A^e * B^e mod n 解决步骤 确定key的位数分配（如17位+19位或16位+20位） 构建前半部分和后半部分的可能值表 通过碰撞查找匹配的组合 逐步逼近正确的key值 7. EZ_ Fermat_ bag_ PRO 题目描述 多项式方程组求解问题，需要求出p。 解题方法 将y表示为 n//x 将x=1代入多项式方程组 使用费马分解法 解决步骤 将y表示为 n//x 代入x=1简化方程 使用费马分解法分解结果 从分解结果中提取p 特殊flag处理 flag具有特殊性： flag > p且大很多 flag仅由p的数字组成（0-9的数字） 参考： easy_ mod系列 最终flag示例： NSSCTF{38886172735077060750460332815973614272222523052135584902884007925985948919714862} 8. RSA_ and_ DSA 题目描述 包含两部分： 维纳攻击RSA DSA的线性关系攻击 解题方法 维纳攻击 ：针对小解密指数d的情况 DSA线性关系 ：类似于NSSRound#1 Basic的number_ by_ number 解决步骤 第一部分：维纳攻击 使用连分数展开e/n 寻找可能的k/d候选 验证候选的正确性 恢复d1 第二部分：DSA攻击 利用线性关系建立方程 解方程得到ink 利用已知签名关系恢复私钥 9. Sin 题目描述 三角函数等式问题。 题目分析 给定三角函数等式： 2*sin(m) - 2*sin(m)*cos(2m) = 4*sin(m)^3 解题方法 化简三角函数表达式 开立方根 格构造攻击 解决步骤 将给定等式化简为 4*sin(m)^3 除以4得到 sin(m)^3 开三次方得到 sin(m) 构造适当的格 使用LLL算法找到满足条件的m值 总结 本教学文档涵盖了GHCTF2025中的多个密码学题目，涉及以下关键技术点： RSA在各种条件下的攻击方法（常规解密、有限域开方、维纳攻击、中间相遇攻击） 因数分解技术（费马分解法、已知phi分解n） 格基约减技术（HNP问题） 数字签名攻击（DSA线性关系） 多项式方程和三角函数方程的求解 每个题目都提供了清晰的解题思路和步骤，关键点包括： 数学原理的应用（数论、代数） 特定攻击方法的实施细节 实际解题中的注意事项 特殊情况的处理方法 通过系统学习这些技术，可以全面掌握现代密码学竞赛中的常见攻击方法和解题技巧。