1. 从TSGCTF 2023的Crypto赛题说起一次密码学实战的深度复盘最近复盘了TSGCTF 2023的密码学Crypto赛题感觉收获颇丰。这类CTF比赛中的Crypto题目往往不是让你去实现一个标准的加密算法而是考察你对密码学原理的深刻理解、对数学漏洞的敏锐洞察以及将理论转化为攻击脚本的工程能力。很多人一看到RSA、离散对数这些词就头疼觉得数学门槛太高。但我想说CTF Crypto的魅力恰恰在于此——它把抽象的数学变成了一个个可以“破解”的谜题。通过解这些题你能真正明白为什么RSA要选大素数为什么随机数不能重复这些知识比单纯背公式有用得多。这篇文章我就以TSGCTF 2023 Crypto部分的解题思路为引子拆解其中涉及的核心密码学概念、常见的攻击手法并分享如何用Python将这些攻击自动化。无论你是CTF新手想入门Crypto还是有一定基础想提升实战能力相信都能从中找到值得参考的东西。2. 赛题核心考点与密码学背景串联TSGCTF的题目一向以高质量和巧妙的构思著称。其Crypto题目通常会围绕几个经典的公钥密码体系如RSA、ECC或对称密码、哈希函数展开但出题人会在参数生成、协议设计或实现细节上故意埋下漏洞。这些漏洞往往对应着密码学中著名的攻击模型。因此解题的第一步不是盲目写代码而是识别题目背后的“考点”。2.1 RSA体系及其常见“脆弱点”RSA绝对是CTF Crypto的“顶流”TSGCTF 2023也大概率少不了它。我们得先搞清楚RSA在哪些地方容易出问题。RSA基础重温首先快速过一遍RSA的流程。Alice想生成一对密钥选择两个大质数p和q计算N p * q。这个N就是模数会出现在公钥里。计算欧拉函数φ(N) (p-1)*(q-1)。选择一个整数e满足1 e φ(N)且e与φ(N)互质。e通常是65537作为公钥的一部分。计算e关于φ(N)的模逆元d即满足e*d ≡ 1 (mod φ(N))的d。这个d就是私钥的核心必须严格保密。加密时对明文m需转换为整数且小于N计算密文c ≡ m^e (mod N)。 解密时用私钥计算m ≡ c^d (mod N)。整个系统的安全性基于大数分解难题给定一个大整数N难以在有效时间内分解出p和q。一旦分解成功φ(N)唾手可得进而可以算出私钥d。CTF中RSA的常见攻击面模数N过小或可分解这是最直接的情况。如果N只有几百位可以用factordb这样的在线数据库或yafu、sage等工具尝试分解。有时N可能本身是素数根本不是两个素数的乘积这会导致φ(N) N-1如果e已知且与N-1互质可以直接计算私钥。共模攻击Common Modulus Attack如果相同的N被用于多个不同的公钥(e1, e2)加密同一明文m且e1和e2互质那么攻击者可以在不知道私钥的情况下恢复m。利用扩展欧几里得算法找到r和s使得e1*r e2*s 1那么m ≡ (c1^r * c2^s) (mod N)。TSGCTF历史上就有过此类变种题。低加密指数攻击当公钥指数e非常小比如3并且明文m也很小使得m^e N时加密过程实际上没有取模密文c m^e就是一个普通整数直接对c开e次方根即可得到m。低解密指数攻击Wiener‘s Attack如果私钥d相对N过小满足d (1/3) * N^(1/4)可以通过连分数展开的方法快速逼近d。这通常发生在e很大的时候。因数碰撞/共享素数在多组RSA密钥对中如果两个不同的N1和N2共享了一个质因数p那么计算gcd(N1, N2)就能快速得到这个p从而分解两个N。这在批量生成密钥时如果随机数生成器有问题就可能发生。选择密文攻击与Padding Oracle这类题目通常提供一个“解密服务器”你可以发送任意密文给它除了比赛密文它会返回解密结果或错误信息如Padding是否有效。通过分析这些返回信息可以一步步推算出原始密文对应的明文。这考验对PKCS#1 v1.5等填充方案的理解。2.2 离散对数与椭圆曲线密码学ECC问题除了RSA基于离散对数难题的密码体系如ElGamal、DSA和椭圆曲线密码学ECC也是常客。离散对数问题DLP在有限循环群G中给定生成元g和元素y找到整数x使得g^x y。在乘法群Z_p^*p为素数上这就是经典DLP。CTF常见攻击小模数p直接暴力破解或使用Pohlig-Hellman算法当p-1的因子都是小素数时特别有效。光滑阶群如果群的阶p-1可以分解为许多小素数的乘积Pohlig-Hellman算法可以将其分解为多个小子问题大大降低难度。指数e与阶不互质当e和群阶有公因子时可能无法唯一解密或者可以利用中国剩余定理CRT来求解。椭圆曲线密码学ECC在椭圆曲线构成的加法群上定义离散对数问题ECDLP。通常更高效密钥短但理解难度稍大。CTF常见攻击无效曲线攻击如果实现允许攻击者提供自定义的曲线参数可能会提供一个阶包含小因子的曲线从而在小因子子群上解决离散对数问题。小子群攻击类似DLP中的光滑阶如果曲线阶含有小因子攻击可能在小阶子群上生效。Smart‘s Attack针对定义在GF(p)上且曲线阶等于p的异常曲线存在多项式时间攻击。2.3 对称密码与编码识别虽然公钥密码是主流但对称密码AES、DES、流密码RC4以及各种编码Base64、Base32、Hex、ASCII、莫尔斯电码、猪圈密码等也常作为混合题的一部分出现。关键技能是识别。给出一串乱码要能通过字符集范围、长度特征、常见模式如填充提示Base64快速判断可能使用的编码或简单替换密码。3. 实战工具链与Python解题环境搭建光有理论不够得有称手的工具。CTF Crypto解题高度依赖数学计算和脚本编写Python因其丰富的库gmpy2,pycryptodome,sage接口成为绝对主力。3.1 核心Python库详解gmpy2这是处理大整数的神器。Python原生的int虽然支持大数但gmpy2底层基于GMP库在模幂运算、素数检测、最大公约数gcd、模逆计算等方面速度快几个数量级。import gmpy2 from gmpy2 import mpz N mpz(1234567890123456789012345678901234567890) e mpz(65537) c mpz(...) # 模幂运算计算 c^d mod N 极快 # 假设我们有了d d mpz(...) m gmpy2.powmod(c, d, N) # 求最大公约数 p gmpy2.gcd(N1, N2) # 求模逆元 d gmpy2.invert(e, phi_N) # 下一个素数 next_prime gmpy2.next_prime(n)PyCryptodome / Crypto提供了几乎所有标准密码算法的实现。常用于验证加解密过程、生成密钥、使用标准块加密模式等。from Crypto.Util.number import bytes_to_long, long_to_bytes, inverse, getPrime from Crypto.Cipher import AES, PKCS1_OAEP from Crypto.PublicKey import RSA # 数字和字节转换 m bflag{hello} m_int bytes_to_long(m) m_bytes long_to_bytes(m_int) # 生成RSA密钥用于本地测试 key RSA.generate(2048) # 计算模逆小数字可用大数还是用gmpy2 d inverse(e, phi_N)SageMath这是一个基于Python的数学软件系统集成了众多代数、数论、密码学工具。对于复杂的数论问题如多项式环、格基约化、椭圆曲线运算Sage是终极武器。你可以通过https://sagecell.sagemath.org/在线使用或本地安装。# Sage示例分解N使用强大的factor函数 N 1234567890123456789012345678901234567890 print(factor(N)) # 可能输出2 * 3^2 * 5 * 101 * 3541 * 3607 * 3803 * 27961 # 解模方程 x var(x) solve_mod(3*x 5 7, 11) # 在模11下解方程 # 椭圆曲线运算 E EllipticCurve(GF(101), [1, 2]) # 定义在GF(101)上的曲线 y^2 x^3 x 2 G E.gen(0) # 获取一个生成元很多离线CTF题尤其是涉及格攻击LLL算法的几乎必须用Sage来解。3.2 辅助工具与在线资源factordb.com大数分解数据库。遇到一个N首先扔进去查一下说不定已经被分解过了。RsaCtfTool一个强大的RSA攻击工具集用Python写成。它集成了数十种针对RSA的攻击方法如维纳攻击、共模攻击、小d攻击、因数碰撞等。对于不熟悉脚本编写的初学者可以直接用这个工具尝试自动攻击。CyberChef瑞士军刀般的网络工具在浏览器中运行。特别适合各种编码解码Base家族、ROT13、URL编码、哈希计算、简单异或、进制转换的快速测试和探索。Python交互式环境强烈推荐使用Jupyter Notebook或VS Code的Python交互窗口。解题过程往往是探索性的尝试一个思路写几行代码看看结果根据结果调整思路。交互式环境比反复运行完整脚本高效得多。4. 针对TSGCTF 2023 Crypto的解题策略推演与脚本编写由于没有具体的题目内容我将基于常见模式推演几种可能在TSGCTF 2023中出现的题型并给出完整的Python解题脚本框架。你可以把这些脚本当作模板遇到类似题目时修改参数和逻辑。4.1 场景一RSA因数碰撞与共享素数攻击题目假设我们拿到了两个密文c1和c2以及它们对应的公钥(N1, e1)和(N2, e2)。密文由同一明文m加密而来。初步尝试发现N1和N2都很大无法直接分解。解题思路首先怀疑是否存在共享素数。计算gcd(N1, N2)如果结果不为1则找到了一个公共质因子p。随后可以分别分解N1和N2计算出各自的私钥d1和d2解密得到明文。Python解题脚本import gmpy2 from Crypto.Util.number import long_to_bytes # 题目给出的数据此处为示例值需替换 N1 mpz(1234567890123456789012345678901234567890) e1 65537 c1 mpz(...) N2 mpz(9876543210987654321098765432109876543210) e2 65537 c2 mpz(...) # 1. 检查是否存在共享素数 p gmpy2.gcd(N1, N2) print(fgcd(N1, N2) {p}) if p 1: print(f[] 发现共享素数 p {p}) # 分解N1 q1 N1 // p # 分解N2 q2 N2 // p # 计算私钥d1 phi1 (p - 1) * (q1 - 1) d1 gmpy2.invert(e1, phi1) # 计算私钥d2 phi2 (p - 1) * (q2 - 1) d2 gmpy2.invert(e2, phi2) # 解密 m1 gmpy2.powmod(c1, d1, N1) m2 gmpy2.powmod(c2, d2, N2) # 理论上m1和m2应该是同一个明文 print(f解密结果1: {long_to_bytes(m1)}) print(f解密结果2: {long_to_bytes(m2)}) else: print([-] N1和N2互质不存在共享素数。需尝试其他攻击如共模攻击。)注意事项在实际比赛中N的值可能长达1024位或2048位gmpy2.mpz是必须的。计算出的p和q需要验证是否为素数虽然由gcd得到但严谨起见可以用gmpy2.is_prime快速检查。如果e1和e2不同且互质即使没有共享素数也可能适用共模攻击。4.2 场景二基于中国剩余定理CRT的RSA故障攻击或相关消息攻击题目假设有时题目会给出多组加密结果这些结果可能源于同一明文在不同但有关联的模数下的加密或者源于一个故障的RSA-CRT实现。中国剩余定理CRT可以将模不同数的方程组合并有时能直接恢复明文或缩小明文范围。一个经典模型Håstad’s Broadcast Attack如果相同的明文m用相同的小加密指数e比如e3但不同的模数N1, N2, N3进行加密且满足m^e N1*N2*N3即m小于所有N的乘积那么可以利用CRT恢复m^e然后直接开方。Python解题脚本import gmpy2 from Crypto.Util.number import long_to_bytes # 假设e3有三组密文和模数 e 3 Ns [mpz(N1), mpz(N2), mpz(N3)] # 替换为实际N cs [mpz(c1), mpz(c2), mpz(c3)] # 替换为实际c # 使用中国剩余定理求解 m^e def crt(remainders, moduli): 中国剩余定理求解 x ≡ remainders[i] (mod moduli[i]) 返回满足所有同余式的x (mod prod(moduli)) total mpz(0) prod mpz(1) for m in moduli: prod * m for r_i, n_i in zip(remainders, moduli): p prod // n_i total r_i * gmpy2.invert(p, n_i) * p return total % prod # 计算 M m^e M crt(cs, Ns) print(f通过CRT恢复的 M m^{e} {M}) # 尝试对M开e次方根 m_candidate, exact gmpy2.iroot(M, e) if exact: print(f[] 成功恢复明文 m {m_candidate}) print(f明文字节: {long_to_bytes(int(m_candidate))}) else: print([-] M不是完全e次方数攻击失败或条件不满足。) # 可能需要检查 m^e 是否真的小于所有N的乘积或者尝试更大的e。关键点这个攻击成立的关键条件是m^e N1*N2*...*Nk。如果e很小如3而k足够多3组或以上这个条件很容易满足。如果e较大可能需要更多组密文和模数。4.3 场景三离散对数问题DLP与Pohlig-Hellman算法题目假设给了一个DLP问题在模素数p的乘法群上已知生成元g目标值h求x使得g^x ≡ h (mod p)。并且提示p-1是光滑的即p-1的因子都是小素数。解题思路这正是Pohlig-Hellman算法大显身手的时候。该算法将大的DLP问题分解为在每个小素数因子q^eq^e整除p-1子群上的小问题然后用中国剩余定理组合得到最终解。Python解题脚本使用SageMath更简单这里展示原理性Python实现import gmpy2 from Crypto.Util.number import isPrime from functools import reduce import operator def pohlig_hellman(g, h, p, factors): g: 生成元 h: 目标值 p: 素数模数 factors: p-1的因子分解列表例如 [(2, 3), (3, 2), (5, 1)] 表示 p-1 2^3 * 3^2 * 5 返回 x 使得 g^x ≡ h (mod p) residues [] moduli [] for q, e in factors: # 计算当前子群的阶 pe q ** e # 计算 g_i 和 h_i g_i pow(g, (p-1)//pe, p) h_i pow(h, (p-1)//pe, p) # 在阶为pe的子群中解DLP: g_i ^ x_i ≡ h_i (mod p) # 这里可以用穷举、BSGS或Pollard‘s rho因为pe较小 x_i solve_dlp_in_small_subgroup(g_i, h_i, p, pe) residues.append(x_i) moduli.append(pe) # 使用中国剩余定理组合所有x_i x crt(residues, moduli) return x def solve_dlp_in_small_subgroup(g, h, p, order): 在小子群阶为order中解DLPorder较小可以用穷举或BSGS # 方法1简单穷举适用于非常小的order # for i in range(order): # if pow(g, i, p) h: # return i # raise ValueError(DLP not found) # 方法2Baby-Step Giant-Step (BSGS)适用于稍大的order m gmpy2.isqrt(order) 1 baby_steps {} # Baby steps e 1 for j in range(m): baby_steps[e] j e (e * g) % p # Compute g^{-m} inv_g_m gmpy2.invert(pow(g, m, p), p) # Giant steps gamma h for i in range(m): if gamma in baby_steps: j baby_steps[gamma] x i * m j if x order: return x gamma (gamma * inv_g_m) % p raise ValueError(DLP not found in subgroup) def crt(a, n): 中国剩余定理a是余数列表n是模数列表 # 同上文的crt函数实现此处省略... pass # 示例用法 p mpz(1000003) # 一个光滑素数p-1 2 * 3 * 166667 g mpz(5) # 假设5是模p的原根 h mpz(123456) # 目标值 factors [(2, 1), (3, 1), (166667, 1)] # p-1的因子分解 try: x pohlig_hellman(g, h, p, factors) print(f[] 解得 x {x}) # 验证 if pow(g, x, p) h: print([] 验证成功) except ValueError as e: print(f[-] 求解失败: {e})重要提示实际比赛中p-1的分解可能通过factordb或sage的factor(p-1)得到。Pohlig-Hellman算法在Sage中有内置函数discrete_log如果安装了sage环境直接调用是最方便的x discrete_log(mod(h, p), mod(g, p))。4.4 场景四编码识别与流密码密钥重用攻击题目假设给了一段看似乱码的文本或文件以及一段Python脚本片段。脚本显示使用了简单的异或XOR加密或者类似RC4的流密码并且可能泄露了密钥或存在密钥重用。解题思路识别编码先用CyberChef或Python的binascii尝试常见编码Hex, Base64, Base32等。观察字符集是否局限于[A-Za-z0-9/]Base64或[A-Z2-7]Base32。分析加密逻辑如果脚本是异或且密钥长度小于明文那么就是重复密钥异或Vigenère类型。攻击方法包括已知明文攻击如果知道部分明文如flag{或CTF{可以恢复部分密钥。重合指数Index of Coincidence分析对于未知密钥长度的重复密钥异或可以分析密文的重合指数来猜测密钥长度然后按字节进行频率分析。Python解题脚本针对重复密钥异或import base64 import string def xor_bytes(b1, b2): 对两个字节串进行异或 return bytes([a ^ b for a, b in zip(b1, b2)]) def guess_key_length(ciphertext, max_len50): 通过计算平均重合指数猜测密钥长度 best_len 1 best_avg_ic 0 for key_len in range(1, max_len1): ics [] # 将密文按key_len分块每一列是使用同一密钥字节加密的 for i in range(key_len): column ciphertext[i::key_len] if len(column) 2: continue # 计算该列的重合指数 freq {} for byte in column: freq[byte] freq.get(byte, 0) 1 ic sum([f*(f-1) for f in freq.values()]) / (len(column)*(len(column)-1)) ics.append(ic) if ics: avg_ic sum(ics) / len(ics) # 英语文本的IC约0.067随机文本约0.038-0.045 if avg_ic best_avg_ic: best_avg_ic avg_ic best_len key_len return best_len def break_single_byte_xor(ciphertext_column): 对单字节异或的密文列进行暴力破解返回最可能的密钥字节解密文本 best_score -1 best_key None best_plain None for key in range(256): plain bytes([c ^ key for c in ciphertext_column]) # 简单的评分计算可打印ASCII字母和空格的数量 score sum([1 for b in plain if 32 b 126 or b in (9, 10, 13)]) if score best_score: best_score score best_key key best_plain plain return best_key, best_plain # 假设ciphertext是字节串 # ciphertext base64.b64decode(...) 或 bytes.fromhex(...) ciphertext b你的密文字节串 # 1. 猜测密钥长度 key_len guess_key_length(ciphertext) print(f猜测的密钥长度: {key_len}) # 2. 按长度分列逐列破解 key bytearray() plain_parts [] for i in range(key_len): column ciphertext[i::key_len] key_byte, plain_part break_single_byte_xor(column) key.append(key_byte) plain_parts.append(plain_part) # 3. 重组明文 plaintext bytearray(len(ciphertext)) for i in range(len(ciphertext)): plaintext[i] plain_parts[i % key_len][i // key_len] print(f恢复的密钥字节: {bytes(key)}) print(f恢复的明文: {bytes(plaintext)})注意事项这种方法基于一个强假设——明文是英文或类似的可读文本。对于完全随机的明文如加密后的flag本身可能像随机数据频率分析会失效。此时需要寻找其他线索比如已知的固定文件头如PNG的\x89PNG、协议格式等。5. 高级技巧与比赛中的实战思维解CTF Crypto题除了掌握具体攻击方法更需要一种“攻击者思维”。5.1 信息收集与“脑洞”仔细阅读题目描述和附件出题人给的每一句话、每一个文件名都可能隐藏提示。比如题目名“Broken RSA”可能暗示密钥生成有问题“Lost Key”可能暗示需要从其他信息恢复私钥。观察数字特征N是奇数还是偶数e是不是特别大或特别小p和q是不是很接近导致p-q很小可以用费马分解p-1或q-1是不是很光滑尝试所有简单情况拿到RSA的N先试试factordb再试试yafu的factor(N)。如果e3且密文c很小试试直接开立方。如果e和N一样大想想Wiener攻击。利用中间人或Oracle如果题目提供了一个可以交互的服务器Oracle想想它能回答什么是解密任意密文并返回结果还是只告诉你解密后的Padding是否正确Padding Oracle这往往是突破点。5.2 脚本调试与效率优化模块化代码将常用的函数如crt,bytes_to_long, 各种攻击函数封装好存成一个工具脚本比如crypto_utils.py。比赛时直接导入节省时间。善用交互环境在Jupyter或IPython里分步执行查看中间变量。用print()或logging输出关键步骤的结果。处理大数和精度始终使用gmpy2.mpz处理大整数。避免使用Python原生浮点数进行开方等运算用gmpy2.iroot进行整数开方。超时处理如果某个攻击算法运行时间过长比如暴力破解先预估一下复杂度。如果不可行赶紧换思路。可以给脚本设置超时signal.alarm或multiprocessing。5.3 从解题到出题理解漏洞本质真正吃透一个知识点最好的方法就是尝试自己出题。思考如果我想考“共享素数攻击”该怎么设计题目除了给两个N还能怎么包装也许可以把N藏在图片的元数据里或者需要先解一个简单的编码题才能拿到。这个过程能极大地加深你对漏洞触发条件和利用方式的理解。TSGCTF 2023的Crypto题目无疑会包含上述几种经典攻击的变种或组合。真正的挑战在于如何从题目给出的有限信息中准确地识别出它对应哪种或哪几种攻击模型并选择最有效的工具链将其实现。这需要大量的练习和经验积累。我建议在赛后不仅满足于解出题目拿到flag更要去官方Writeup或社区分享中看看别人的解题思路尤其是那些更优雅、更通用的方法。把每次比赛都当成一次密码学知识的压力测试和思维拓展你的实战能力才会快速提升。