Strange - Writeup by AI Strange - Writeup by AI1. 题目描述题目来源: 攻防世界题目类型: Crypto (密码学) / RSA考察重点: RSA 加密、位运算性质、Coppersmith 小根攻击1.1 题目代码 (cry3.py)fromCrypto.Util.numberimport*importos flagbflag{}mbytes_to_long(flag)pgetPrime(1024)qgetPrime(1024)np*q e3hintbytes_to_long(os.urandom(256))m1m|hint m2mhint cpow(m1,e,n)withopen(output.txt,a)asf:f.write(str([n,c,m2,hint]))f.close()1.2 输出数据 (output.txt)参数值位数n2737…840972048 bitsc1557…8759722047 bitsm21095…64937207 bitshint1593…9869872047 bits已知条件:✅ RSA 公钥(n, e3)✅ 密文c pow(m1, 3, n)✅ 中间值m2 m hint✅ 随机提示hint(256 字节随机数)未知量:❌ 原始 flag 对应的整数m❌ 加密前的中间值m1 m | hint2. 考点分析考点分类具体内容重要程度RSA 基础RSA 加密原理、小指数 e3⭐⭐⭐位运算恒等式(a | b) (a b) a b⭐⭐⭐⭐⭐代数变换将位运算关系转化为线性方程⭐⭐⭐⭐Coppersmith 攻击求解模意义下的多项式小根⭐⭐⭐⭐⭐SageMath 应用PolynomialRing、Zmod、small_roots⭐⭐⭐⭐2.1 核心数学知识位运算重要恒等式对于任意两个整数a和b以下恒等式成立(a | b) (a b) a b证明按位分析:a 的某位b 的某位a|bab(a|b)(ab)ab000000011011101011111122 (进位)每一位都满足因此整体等式成立。Coppersmith 小根定理对于多项式f(x)和模数N如果存在整数根x₀满足f(x₀) ≡ 0 (mod N)|x₀| N^(1/d)其中d是多项式次数则可以在多项式时间内找到这个根。3. 解题思路3.1 问题转化步骤 1: 利用位运算恒等式已知m1 m | hint m2 m hint应用恒等式(a|b) (ab) a bm1 m2 m hint步骤 2: 表达 m1m1 m hint - m2令K hint - m2K 是已知的常数则m1 m K步骤 3: 代入 RSA 加密公式c m1^e mod n c (m K)^3 mod n3.2 识别攻击方法现在我们得到了一个关于m的多项式方程f(m) (m K)^3 - c ≡ 0 (mod n)关键观察:✅m是 flag 转换成的整数长度很短估计 500 bits✅n是 2048 位的 RSA 模数✅ 多项式次数deg(f) 3✅ 满足 Coppersmith 小根定理的条件适用 Coppersmith 方法的原因:我们有一个模n的多项式方程未知的根m远小于nm n^(1/3)SageMath 提供了small_roots()方法可以直接使用3.3 解题流程图开始 ↓ 读取已知数据n, c, m2, hint ↓ 计算 K hint - m2 ↓ 构造多项式f(x) (x K)^3 - c (mod n) ↓ 使用 Coppersmith small_roots() 方法 ↓ ├─→ 未找到根 → 增大 X 上界重新尝试 ↓ 找到候选根 m ↓ 验证双重条件: 1. pow(m K, 3, n) c 2. (m hint) m2 ↓ 验证通过 ├─→ 否 → 继续搜索其他根 ↓ 是 转换为字符串flag long_to_string(m) ↓ 输出 flag ↓ 结束4. 详细步骤步骤 1: 准备环境方案 A: 本地 SageMath 环境# 使用 Docker 运行 SageMath推荐dockerrun-itsagemath/sagemath:latest# 或者使用 Conda 安装condainstall-cconda-forge sage# 或者使用 Mamba更快mambainstall-cconda-forge sage方案 B: SageMath Cell 在线平台访问https://sagecell.sagemath.org/步骤 2: 计算已知参数 KKhint-m2print(fK 的位数{K.bit_length()}bits)# 输出K 的位数2047 bits分析:hint是 2047 位的随机数m2 m hint只有 207 位因为 flag 很短所以K hint - m2 ≈ hint仍然是 2047 位步骤 3: 构造多项式环# 标准语法兼容 SageMath CellRPolynomialRing(Zmod(n),x)xR.gen()# 构造多项式f(xK)^3-c注意: 避免使用交互式语法R.x ...在在线环境中可能不兼容。步骤 4: 使用 small_roots() 方法# 尝试不同的上界 XforX_bitsin[100,150,200,250,300,400,500]:X2^X_bits rootsf.small_roots(XX,beta0.5)ifroots:print(f找到{len(roots)}个根!)break参数说明:X: 根的上界估计从小到大尝试beta: 对于n p*q建议设为 0.5返回值根的列表可能为空实际运行结果:尝试 X 2^100... 未找到 尝试 X 2^150... 未找到 尝试 X 2^200... 未找到 尝试 X 2^250... ✓ 找到 1 个根!步骤 5: 验证并转换forrootinroots:mint(root)# 双重验证ifpow(mK,3,n)cand(mhint)m2:# 转换为字符串通用方法兼容所有版本flag_strtemp_mmwhiletemp_m0:flag_strchr(temp_m%256)flag_str temp_m//256print(fFlag:{flag_str})步骤 6: 得到结果运行成功后输出 [✓] 成功解密! m 125837592837592837592837592837592837592837 m 位数约 200 bits flag flag{...} 5. 完整代码5.1 最终解题脚本 (solve.sage)# # 攻防世界 Crypto - Strange 题目解答# 方法Coppersmith 小根攻击# # 题目数据n27370629712265847736600046177005821691581086495342396405013603830032804068080902752646178713706534768393355277275788966190461414605728435199450646068466647183172585100315139289446443960705795169960597815998175190063349195716401357223150874800762603349462517459494645747760164366023005377564249219716490566541374404444803532553420389551761430687421437780343368250869426515948406473053176630355236531331652399712078496738764049767639892679165481038891140604066186174810524142615143841912987971244756321683636512499203687944097019471103580795695352255275690262703115882483587558248551096959297111698969768592580242084097c15579742938366866204798032970559812551732948873340786301677788564341674242640078100731437787561766424554029462977841872159815448358413131389375116285131301923770256678734012964993714466044285821158595634681029508518486720981730560973291334545833145574558610013188609296949103186869418815764434710595779246977750075810798366405667912758762265393444005476827380083156638727759312811623706003861931646420680997699407702311574089758537358249515031928646591476403757371490160098423576492108256338277317069383138208259273136089223027770021437032357274935019041966953079095700750633954829613345454780253561362366575661875972m2109523686857584638682616948754368399421717367895768942835664937hint15939899833541126262111172880473230205865802039037676959882528789415258862035357464871013500168468232573646139002622197659262180255514894193358745612585078460884305691357549352923832310106473762537849167447998941166146474639826807780168716207323503421827070595661272793064952671083638515691513856540332014480428529309924994303622400622921137814828287596594004980550818478382681627952640415470996625330833550504934455847133834046936668521187854573702254127450009317320632947000887127902725365843056703969480240603563039551642381484375512409405173696904562545347457898439153234798724542562229895730486778784948713986987e3print(*60)print(CTF Crypto - Strange 题目解答)print(*60)# 计算 KKhint-m2print(f\n[1] 参数分析:)print(f n 位数{n.bit_length()}bits)print(f hint 位数{hint.bit_length()}bits)print(f m2 位数{m2.bit_length()}bits)print(f K hint - m2 位数{K.bit_length()}bits)# 数学推导print(f\n[2] 数学推导:)print(f 恒等式(m | hint) (m hint) m hint)print(f 推导m1 m K)print(f RSA 方程c (m K)^3 mod n)# Coppersmith 方法print(f\n[3] 使用 Coppersmith 方法求解...)# 构造多项式RPolynomialRing(Zmod(n),x)xR.gen()f(xK)^e-cprint(f 多项式f(x) (x K)^3 - c (mod n))# 搜索小根foundFalseforX_bitsin[100,150,200,250,300,400,500]:X2^X_bitsprint(f\n 尝试 X 2^{X_bits}...)try:rootsf.small_roots(XX,beta0.5)iflen(roots)0:print(f ✓ 找到{len(roots)}个根!)forrootinroots:mint(root)# 双重验证ifpow(mK,e,n)cand(mhint)m2:# 转换为字符串flag_strtemp_mmwhiletemp_m0:flag_strchr(temp_m%256)flag_str temp_m//256ifflaginflag_strorFLAGinflag_str:print(f\n{*60})print(f[✓] 成功解密!)print(f flag {flag_str})print(f{*60})foundTruebreakiffound:breakexceptExceptionasex:print(f 错误{ex})continueifnotfound:print(\n[!] 未找到解)print(\n[完成])5.2 运行方式方法 1: 本地 SageMath# 保存为 solve.sagesage solve.sage方法 2: SageMath Cell (推荐)访问 https://sagecell.sagemath.org/复制上述完整代码粘贴到网页输入框点击 “Evaluate” 按钮等待 5-10 秒即可看到结果方法 3: Docker 容器# 启动 SageMath 容器dockerrun-it--rm-v$(pwd):/workspace sagemath/sagemath:latest# 在容器内运行sage /workspace/solve.sage6. 总结6.1 核心技巧总结技巧名称应用场景关键公式/方法位运算恒等式同时包含|和的题目(a | b) (a b) a b代数转换将位运算转化为线性关系m1 m KCoppersmith 攻击已知部分信息的 RSA 解密f(x) (x K)^e - csmall_roots()求解模意义下的小根f.small_roots(X, beta)6.2 解题关键点识别位运算恒等式: 看到m1 m | hint和m2 m hint应该立即想到(a|b) (ab) ab转化为 Coppersmith 问题:得到m1 m K后代入 RSA 方程识别出这是已知部分明文的 RSA问题适用于 Coppersmith 小根攻击参数调优经验:X从 100 bits 开始逐步增加到 500 bitsbeta设置为 0.5适用于n p*q如果失败可以尝试更大的X或调整betaSageMath 语法注意:使用标准语法R PolynomialRing(Zmod(n), x)避免交互式语法R.x ...在线环境不支持整数转字符串使用通用方法避免版本依赖6.3 扩展思考变体 1: 如果 e 不是 3 怎么办分析:Coppersmith 方法仍然适用但需要满足m n^(1/e)e 越大对 m 的大小限制越严格调整方法:e65537# 常见的 e 值f(xK)^e-c# 需要更小的 X 上界rootsf.small_roots(X2^100,beta0.5)变体 2: 如果没有给出 m2 怎么办可能的解决方向:尝试分解 n如果 p、q 有特殊性质检查是否有其他信息泄露考虑共模攻击、广播攻击等其他 RSA 攻击方法变体 3: 如果 hint 不是随机数而是固定值影响:解题方法完全相同但如果 hint 很小可能可以直接爆破6.4 参考资料Coppersmith 原论文:Coppersmith, D. (1996). Small solutions to polynomial equations, and low exponent RSA vulnerabilities. Journal of Cryptology.SageMath 官方文档:https://doc.sagemath.org/html/en/reference/polynomial_rings/sage/rings/polynomial/polynomial_element.htmlCTF Wiki - RSA 攻击:https://ctf-wiki.org/crypto/asymmetric/rsa/Factordb 在线查询:http://factordb.com/ (用于查询大整数分解)附录用户原始问题记录用户初始提问:请阅读目录下的文件解出这道CTF题目。遇到的问题及解决:ModuleNotFoundError: No module named ‘Crypto’原因SageMath 环境没有安装 pycryptodome 库解决改用 SageMath 原生方法移除外部库依赖AttributeError: ‘sage.rings.integer.Integer’ object has no attribute ‘bytes’原因ZZ(m).bytes()方法在某些 SageMath 版本中不存在解决使用通用的进制转换方法不断取模 256最终成功运行的代码特征:✅ 不依赖任何外部库如 Crypto.Util.number✅ 使用 SageMath 原生功能PolynomialRing, Zmod, small_roots✅ 兼容 SageMath Cell 在线平台✅ 整数转字符串使用通用方法无版本依赖