1. 从TSGCTF 2023的Crypto赛题我们能学到什么如果你对CTFCapture The Flag竞赛中的密码学Crypto方向感兴趣或者刚刚在“CTF秀”这类平台上被第二道密码题卡住那么复盘一场高质量比赛的具体题目尤其是像TSGCTF这种由顶尖强队出题的比赛是提升实战能力最快的方法。很多人觉得密码学就是套公式、用工具但真正的比赛里尤其是TSGCTF这个级别的题目往往是对经典密码学原理的巧妙变形和深度结合考验的是选手对原理本质的理解和灵活应用的能力。今天我就以TSGCTF 2023的几道典型Crypto赛题为例带你深入幕后拆解出题人的思路并还原解题时那些关键的“灵光一现”。这不仅仅是Writeup更是一次思维训练让你明白下次遇到类似“CTF秀crypto第二题”那种看似无从下手的题目时应该从何想起。2. 赛题核心思路与常见攻击模式解析TSGCTF的密码学题目向来以“优雅的难题”著称它们很少考察冷僻的算法而是喜欢在常见的RSA、离散对数、流密码等基础上设置一些精巧的约束条件或组合模式。理解这些常见攻击模式的本质是解题的第一步。2.1 模数分解与共模攻击的变种在RSA相关题目中单纯的给一个N让你分解在现在的比赛中已经几乎绝迹。更常见的是提供多个相关密文或密钥片段。比如一道题可能给你两个使用相同模数N、不同加密指数e1和e2加密同一明文m得到的密文c1和c2。这就是经典的共模攻击场景。其核心原理是利用扩展欧几里得算法找到满足e1*s1 e2*s2 1的整数s1和s2通常一正一负然后计算(c1^s1 * c2^s2) mod N其结果就等于m^(e1*s1 e2*s2) m^1 m。这里的关键是理解指数运算在模N下的可乘性。但TSGCTF可能会在此基础上增加难度。例如它可能不直接给你c1和c2而是给你用e1加密的m和用e2加密的m的某个线性变换比如m1。这时你就不能直接套用共模攻击公式。你需要设未知数建立方程。假设c1 ≡ m^e1 (mod N),c2 ≡ (m1)^e2 (mod N)。虽然不能直接恢复m但你可以利用这两个式子在整数环上构造一个关于m的多项式方程。例如从c1你可以得到m ≡ c1^d1 (mod N)的关系虽然d1未知但这个关系可以代入第二个式子进行推理。更实用的方法是注意到m和m1相差1结合c1和c2有时可以通过计算c2 * inverse(c1, N)^e2在模N下来消去m的高次项得到一个只与N和已知量有关的等式可能泄露N的因子。这要求对模运算和代数变形有深刻的理解。注意当指数e1和e2不互素时比如都是偶数标准的共模攻击可能失效因为s1和s2可能不存在整数解使得和为1。此时需要先计算g gcd(e1, e2)如果g较小可以考虑对c1和c2开g次方根在整数域尝试得到新的c1和c2然后对e1/g和e2/g应用共模攻击。2.2 基于中国剩余定理CRT的漏洞与故障注入RSA的CRT中国剩余定理优化算法是提高解密速度的标准方法但它也引入了新的攻击面即故障攻击。在CTF中这通常以“部分密钥泄露”或“错误签名”的形式出现。题目可能给你一个正常的RSA签名S以及另一个在CRT计算过程中某个模数项如Sp m^d mod p出错后得到的错误签名S。攻击原理如下设N p * q私钥d。正常签名S m^d mod N。根据CRT计算会分解为Sp m^d mod pSq m^d mod q再用CRT组合得到S。 如果计算Sp时发生故障得到错误的Sp那么组合出的错误签名S将满足S ≡ Sp (mod p)- 所以S - Sp ≡ 0 (mod p)S ≡ Sq (mod q)- 所以S - Sq ≡ 0 (mod q)不一定成立。 但关键是正确的S满足S ≡ Sp (mod p)和S ≡ Sq (mod q)。 如果我们有正确的S和错误的S那么计算gcd(S - S, N)。因为S - S ≡ (Sp - Sp) ≡ 0 (mod p)因为Sp和Sp都是模p下的数它们的差是p的倍数。S - S ≡ (Sq - Sq) ≡ 0 (mod q)不一定成立除非故障也影响了Sq通常题目假设只影响一个分支。 因此S - S很大概率是p的倍数而不是q的倍数那么gcd(S - S, N)就会得到p从而分解N。在TSGCTF中题目可能不会直接告诉你哪个是错误签名。它可能给你多个签名其中一些是正常的一些是有错误的让你自己去判断和利用。这就需要你编写脚本尝试计算所有签名对之间的gcd寻找非1和N的最大公约数。2.3 流密码与线性反馈移位寄存器LFSR的逆向流密码特别是基于LFSR的是Crypto方向的常客。LFSR的状态更新是线性的这既是其实现简单的优点也是其安全性的弱点。攻击的核心往往是利用密钥流keystream与初始状态密钥之间的线性关系。一个最简单的n级LFSR其下一时刻的状态是当前状态比特的线性组合。如果我们得到了足够长的密钥流片段至少2n比特我们就可以建立一系列线性方程来求解LFSR的反馈系数即抽头位置或初始状态。这通常通过Berlekamp-Massey (BM) 算法来完成该算法可以根据输出序列找到生成该序列的最短LFSR的阶数和反馈多项式。TSGCTF的题目可能会在简单LFSR基础上增加层次非线性组合生成器使用多个LFSR它们的输出通过一个非线性函数f组合成最终的密钥流比特。攻击思路往往是先猜测非线性函数f的结构如果未知或者如果f是已知的但涉及多个LFSR的少量输出可以尝试相关攻击即寻找密钥流与单个LFSR输出之间的相关性。带钟控的LFSR一个LFSR的输出决定另一个LFSR是否步进。这打破了输出的直接线性关系但通过分析停走模式可能可以建立概率模型。已知明文攻击与矩阵求解如果知道一段明文和对应的密文那么就能得到一段密钥流。对于LFSR密钥流k[i]与初始状态S满足线性关系k S * M其中M是由反馈多项式构成的矩阵。已知k求解S就是一个解线性方程组的问题在GF(2)上。TSGCTF可能会把状态S设计得比较大比如256位但给出的密钥流长度刚好够建立方程考察选手用SageMath或Python的numpy在GF(2)上求解大规模矩阵方程的能力。3. 典型赛题实战拆解与复现下面我们虚拟还原两道符合TSGCTF风格的题目并一步步拆解解题过程。请注意为了教学清晰我简化了部分参数但核心考点和攻击模式完全一致。3.1 题目一冗余的CRTRedundant CRT题目描述服务器实现了一个RSA签名服务使用CRT进行加速。由于代码bug服务器在计算签名时偶尔会错误地重复计算CRT中的q分支即计算两次Sq而p分支计算正确。我们得到了同一个消息m的10个签名其中大部分是正常的但恰好有一个签名是这种“冗余CRT”错误导致的。你能分解出N吗已知N2048位e65537消息m一个已知的随机长整数以及10个签名sig_list。解题思路拆解理解故障模型正常CRT签名S CRT(Sp, Sq)其中Sp m^d mod p,Sq m^d mod q。 错误签名模型S CRT(Sp, Sq, Sq)这说不通。更合理的解释是在组合CRT时错误地使用了错误的模数或系数。一个经典的“冗余”bug是在计算中国剩余定理的系数时用于q的系数被计算了两次。具体来说正常CRT组合公式为S Sq * (p * inv(p mod q)) Sp * (q * inv(q mod p)) mod N假设计算Sq的系数时本应是(p * inv(p mod q))但错误地变成了(p * inv(p mod q)) * t其中t是某个值比如2或者另一个inv(p mod q)。这会导致最终签名S在模q下仍然正确因为S ≡ Sq (mod q)但在模p下是错误的。建立数学关系设正常签名为S错误签名为S。我们有S ≡ m^d (mod N)-S^e ≡ m (mod N)验证通过。S在模q下验证通过S^e ≡ m (mod q)但在模p下不通过。 因此S^e - m是q的倍数但不是p的倍数大概率。同理S^e - m是N的倍数即p*q的倍数。构造攻击计算gcd(S^e - m, N)。因为S^e - m ≡ 0 (mod q)且S^e - m ≢ 0 (mod p)所以这个最大公约数就是q。从而分解N。 但问题是我们不知道10个签名中哪个是错的。所以需要遍历所有签名sig计算gcd(sig^e - m, N)。对于正常签名sig^e - m是N的倍数gcd结果就是N本身。对于错误签名gcd结果将是q一个大约1024位的大数。实操脚本import math from Crypto.Util.number import long_to_bytes, bytes_to_long # 假设已知以下变量 N 0xabcdef... # 2048位的N e 65537 m bytes_to_long(bKnown_Message_For_Signing) sig_list [ ... ] # 10个签名每个都是长整数 for i, sig in enumerate(sig_list): g math.gcd(pow(sig, e, N) - m, N) if g ! 1 and g ! N: print(fFound faulty signature at index {i}) q g p N // q print(fp {p}) print(fq {q}) break关键点与陷阱计算pow(sig, e, N)时一定要模N否则中间结果会巨大无比。验证分解出p和q后应计算phi (p-1)*(q-1)d pow(e, -1, phi)然后用私钥d验证是否能正确生成其他正常签名。这可以双重确认。为什么错误签名验证S^e ≡ m (mod N)会失败因为故障导致S不再是m^d mod N的正确值。服务器在生成错误签名后自己用S^e mod N验证也会失败但题目场景可能是服务器记录了这个错误的输出或者攻击者截获了错误中间值。这道题考察了对CRT实现细节的深刻理解以及如何将模糊的“冗余”描述转化为具体的、可计算的数学故障模型。3.2 题目二颤抖的LFSRShaky LFSR题目描述一个保密的流密码使用了一个80位的LFSR但其反馈多项式是未知的。我们通过侧信道获取了密钥流的前200位但得知在生成过程中由于硬件不稳定有少量比特不超过5位可能发生了翻转即0变1或1变0。你能还原出原始的LFSR反馈多项式吗已知keystream200位长的比特串可能有最多5个错误。解题思路拆解核心挑战标准的BM算法要求输入序列是精确的由某个LFSR生成的。现在序列中有少量错误直接使用BM算法会得到一个非常长可能接近200阶的、不正确的反馈多项式因为算法会试图用复杂的线性关系去拟合那些错误比特。攻击思路错误比特数很少≤5这是一个典型的纠错问题。我们可以暴力枚举错误的位置。200位中选5位出错组合数C(200,5)非常大直接暴力不可行。需要优化。利用LFSR的线性特性一个n级的LFSR其输出序列满足线性递推关系s[in] c0*s[i] c1*s[i1] ... c_{n-1}*s[in-1] mod 2其中c_i是反馈系数。对于一段没有错误的序列任意连续2n位都可以建立方程组解出c_i。反过来如果我们猜对了反馈多项式即系数c_i那么我们可以用这个多项式去验证整个序列用前n位预测第n1位看是否匹配然后滑动窗口一直预测下去。如果序列中有错误预测就会失败。具体步骤 a.假设LFSR阶数n题目说80位我们就从80开始尝试。也可以试探性尝试70-90的范围。 b.枚举错误模式我们不需要枚举所有5个错误的位置。一个更聪明的办法是先假设序列前2n位例如160位中没有错误或者错误很少。我们用这2n位通过解线性方程组或BM算法求出一个候选的反馈多项式P。 c.用多项式P验证并定位错误用求出的P去预测整个200位的序列。记录预测值与给定keystream不符的位置。这些位置就是潜在的“错误点”。如果这样的位置数量很少≤5并且它们分布合理比如如果我们纠正了这些位置的比特整个序列就能被P完美预测那么我们就找到了正确的P和错误位置。 d.迭代精炼由于前2n位也可能包含错误我们第一次求出的P可能不对。我们可以把上一步找出的疑似错误位置进行纠正翻转比特得到一个新的、更干净的序列片段然后用这个新片段重新计算P。重复这个过程几次可能会收敛到正确的解。实操脚本SageMath环境# SageMath 代码 def berlekamp_massey(seq): 标准BM算法返回生成该序列的最短LFSR的反馈多项式系数列表低位对应最早项 n len(seq) C [1] [0]*n # 连接多项式 B [1] [0]*n # 辅助多项式 L 0 m -1 b 1 for N in range(n): d seq[N] for i in range(1, L1): d ^ (C[i] seq[N-i]) # GF(2)上的内积 if d 1: T C[:] for i in range(0, n-Nm): C[N-mi] ^ B[i] if L N//2: L N 1 - L m N B T b d # 返回多项式系数C[0]是常数项1C[1..L]是反馈系数 return C[:L1] def verify_poly(poly, seq): 用多项式poly预测序列seq返回错误位置列表 n len(poly) - 1 # LFSR阶数 errors [] # 使用前n位作为初始状态 state seq[:n] for i in range(n, len(seq)): # 计算下一个比特 next_bit 0 for j in range(n): next_bit ^ (poly[j1] state[j]) # poly[0]是常数项1忽略 predicted next_bit if predicted ! seq[i]: errors.append(i) # 更新状态窗口 state state[1:] [predicted] # 注意这里用预测值更新模拟无错运行 # 但为了验证更好的方法是始终用原始seq更新状态除了在错误点我们不知道真实值 # 所以我们换一种验证方式用poly和原始seq的前i位计算下一个预测与seq[i]比较 # 更准确的验证滑动窗口计算 errors [] for i in range(len(seq) - n): window seq[i:in] next_bit sum(poly[j1]*window[j] for j in range(n)) % 2 if next_bit ! seq[in]: errors.append(in) return errors # 假设keystream是0/1列表长度200 keystream [0,1,1,0,...] # 你的数据 max_errors 5 candidate_n 80 for n in range(70, 91): # 尝试70到90的阶数 print(fTrying n {n}) # 取前2n位尝试计算初始多项式 subseq keystream[:2*n] poly berlekamp_massey(subseq) if len(poly) - 1 ! n: # BM找到的阶数不是n说明这段子序列可能包含错误或者n猜错了 continue errors verify_poly(poly, keystream) if len(errors) max_errors: print(fPotential found: n{n}, poly{poly}, errors at {errors}) # 可以尝试纠正错误重新计算验证 corrected_stream keystream[:] for pos in errors: corrected_stream[pos] ^ 1 # 翻转错误比特 # 用纠正后的完整序列再跑一次BM看多项式是否稳定 poly2 berlekamp_massey(corrected_stream) if poly poly2: print(fConfirmed! LFSR polynomial: {poly}) break关键点与陷阱BM算法对错误极其敏感。即使只有一个比特错误产生的多项式阶数也可能接近序列长度。我们的策略是基于“错误很少”的假设通过“猜测-验证-纠正”的循环来逼近答案。这本质上是一种穷搜但将搜索空间从C(200,5)降低到了对多项式阶数n和少量错误位置的搜索。在实际CTF中可能错误比特数是一个提示如“不超过5位”如果没有提示可能需要尝试不同的错误上限。验证时注意我们是用多项式去“预测”下一个比特并与给定序列比较。如果预测失败不一定就是该位置错了也可能是更早的位置错了导致状态偏离。所以算法可能需要多次迭代纠正。这道题将经典的流密码分析与纠错思想结合考察选手在非理想条件下有噪声的数据应用密码分析工具的能力。4. 实战中遇到的问题与深度排查技巧在实际操作中尤其是比赛环境下理论正确不代表能快速拿到flag。下面分享几个我踩过的坑和总结的技巧。4.1 数学运算的精度与边界问题问题场景在解一道涉及大整数开根或求解模方程的题目时脚本运行结果莫名奇妙或者得到负数、非常小的数。排查与解决检查整数与浮点数Python中/是浮点除法//是整数除法。在密码学计算中除非明确需要浮点否则一律使用//和%。例如计算(p-1)*(q-1)时确保p和q是整数。模逆元的存在性计算d pow(e, -1, phi)前必须确认gcd(e, phi) 1。如果不互素则模逆元不存在这是RSA的基本要求。如果题目故意给了不互素的e和phi那可能就是突破口意味着N可能不是标准的两个素数相乘或者phi计算有误可能是多素数RSA。大整数幂运算的内存与时间直接计算pow(a, b)而不取模结果会巨大无比导致内存溢出。务必使用pow(a, b, N)进行模幂运算。对于非常大的指数比如私钥dPython的pow函数配合三个参数是高度优化的。开方与近似当需要计算iroot整数次方根时使用gmpy2库的iroot函数或者用Python的int(x ** (1/n))并上下调整。注意浮点数精度问题对于非常大的数**运算可能产生精度误差。最安全的方法是使用二分查找法求整数根。def integer_nth_root(x, n): 返回 (y, bool)其中y是整数bool为True表示y^n x lo, hi 0, x while lo hi: mid (lo hi) // 2 pow_mid pow(mid, n) if pow_mid x: return mid, True elif pow_mid x: lo mid 1 else: hi mid - 1 return hi, False # hi是小于等于真实根的最大整数4.2 数据编码与格式转换的暗坑问题场景明明解密出了数字m转成字节后却是乱码或者提交flag格式不对。排查与解决字节序与整数转换long_to_bytes和bytes_to_long来自Crypto.Util.number是标准做法。但要注意这些函数默认使用大端序big-endian即最高有效字节在前。绝大多数CTF题目都遵循这个约定。如果遇到小端序的题目通常会有明确提示。处理非ASCII字符解密出的字节流可能包含不可打印字符。不要直接print可以用repr()查看转义形式或者用.hex()方法输出十六进制。Flag可能藏在十六进制字符串的特定位置。多种编码尝试如果直接转字节不对尝试以下常见编码long_to_bytes(m).decode(utf-8)如果明文是文本long_to_bytes(m).decode(latin-1)处理任意字节将整数m转为十六进制字符串hex(m)[2:]然后看是否有666c6167‘flag’的hex等模式。Flag格式CTFflag通常有固定格式如TSGCTF{...}、flag{...}、SECCON{...}等。解密出的明文可能就是这个完整字符串也可能只是花括号内的内容需要你加上前缀。仔细阅读题目描述。4.3 脚本调试与交互题技巧问题场景面对一个需要连接远程服务器、进行多轮交互的题目本地测试成功但远程却拿不到flag。排查与解决使用Pwntools这是CTF交互题的标配库。它处理TCP连接、发送接收数据、处理超时比用socket库手动写方便得多。务必熟悉recvline,recvuntil,sendline,interactive等基本方法。注意延迟与缓冲区远程服务器可能有响应延迟或者会一次性发送多行数据。使用recvuntil(bkeyword:)来稳定地接收到某个提示符为止避免因为接收不完整而解析错误。本地化测试如果题目提供了源码或描述足够清晰尽量在本地搭建一个模拟环境进行测试。用Python启动一个简单的socket服务器来模拟远程行为可以极大加快调试速度。日志与打印在脚本的关键步骤添加打印语句输出中间变量如收到的N、e、密文等。对于大整数可以打印其16进制的前后几位例如hex(N)[:20] ... hex(N)[-20:]以确认数据接收正确。异常处理网络可能不稳定。在循环交互中使用try...except捕获超时或连接错误并实现重试逻辑。4.4 思维定式与信息遗漏问题场景一道题卡了很久觉得所有思路都试过了最后发现漏看了一个附件里的注释或者误解了题目描述的一个词。排查与解决逐字阅读题目描述题目中的每一个词都可能有用。“偶尔”、“恰好有一个”、“冗余”、“颤抖”这些词都在暗示特定的攻击模型。将描述转化为精确的数学条件。检查所有附件除了主要的chall.py或task.py还要看有没有output.txt、data.txt、Dockerfile、README。Dockerfile里可能提示了环境或库版本README可能有提示。逆向思维如果正向攻击走不通想想是不是题目在考“构造”而不是“破解”。例如给你一个漏洞让你构造特殊的输入使服务器产生错误从而泄露信息。或者让你为一个弱的密码系统生成一对有效的明文-密文。利用搜索引擎和社区对于TSGCTF这种知名比赛其题目往往借鉴或改编自已知的密码学攻击论文或经典漏洞。用题目中的关键词如“Redundant CRT”加上“CTF writeup”搜索可能会找到相似的思路。但切记这应该是最后的手段并且重在理解思路而非抄袭答案。5. 工具链与学习资源推荐工欲善其事必先利其器。一套顺手的工具和高质量的学习资源能让你事半功倍。5.1 核心编程环境与库Python3 SageMath这是密码学方向的绝对主力。常规代数运算、RSA、离散对数用Python足矣。但涉及环、域、椭圆曲线、格基约减等高级运算SageMath是神器。它集成了Python语法和大量数学库可以像写数学公式一样操作多项式、矩阵和代数结构。建议通过Docker或直接安装SageMath。关键Python库Crypto.Util.number提供long_to_bytes,bytes_to_long,GCD,inverse等基础函数。gmpy2处理大整数运算和素性检测速度比Python原生整数快很多尤其是gcd,invert,iroot等函数。sympy符号计算可用于解方程、化简表达式在推导公式时很有用。numpy处理大规模线性方程组在GF(2)上需手动处理或使用galois库。交互工具pwntools用于网络交互题requests用于HTTP API类题目。5.2 针对性学习路径从经典到现代起步彻底理解RSA的原理、加解密、签名、各种基础攻击小公钥/小私钥、共模、广播、Franklin-Reiter相关消息攻击。进阶学习离散对数问题DLP在有限域上的求解BSGS、Pohlig-Hellman椭圆曲线密码学ECC的基本概念和简单攻击Smart攻击、MOV攻击。深入格基约减LLL算法及其在密码分析中的应用解小根方程、攻击RSA with dp泄露、背包密码等。这部分难度较大但TSGCTF等高端赛经常涉及。实践平台CTF秀、CTFHub、BugKu的Crypto板块适合新手入门题目分类清晰。CryptoHack交互式学习平台将密码学概念分解成一个个小挑战从易到难是系统学习的最佳途径之一。各大CTF赛事归档在CTFtime.org上找到历年比赛直接搜索“TSGCTF crypto writeup”阅读高质量的解题报告。不仅要看步骤更要理解解题者的思考过程。理解“为什么”每做一道题都要问自己出题人在这里设置了什么陷阱这个攻击为什么能成立它的前提条件是什么如果改变某个参数比如增加错误比特数攻击还成立吗这种追根问底的习惯能让你从“解出一道题”上升到“掌握一类题”。回过头看无论是TSGCTF的难题还是“CTF秀crypto第二题”那样的入门题其核心都是将密码学原理置于一个稍微非常规的场景下。解题的关键不在于记忆更多的攻击脚本而在于培养一种能力将模糊的文字描述转化为精确的数学模型并判断该模型对应哪种已知的攻击模式或需要何种新的组合推理。这需要扎实的基础知识、细致的观察力和不断的练习。下次当你再被一道题卡住时不妨停下来在白板上画一画数据流写一写数学等式也许那条隐藏的路径就清晰了。 TSGCTF 2023 Crypto赛题解析：从共模攻击到LFSR逆向实战
1. 从TSGCTF 2023的Crypto赛题我们能学到什么如果你对CTFCapture The Flag竞赛中的密码学Crypto方向感兴趣或者刚刚在“CTF秀”这类平台上被第二道密码题卡住那么复盘一场高质量比赛的具体题目尤其是像TSGCTF这种由顶尖强队出题的比赛是提升实战能力最快的方法。很多人觉得密码学就是套公式、用工具但真正的比赛里尤其是TSGCTF这个级别的题目往往是对经典密码学原理的巧妙变形和深度结合考验的是选手对原理本质的理解和灵活应用的能力。今天我就以TSGCTF 2023的几道典型Crypto赛题为例带你深入幕后拆解出题人的思路并还原解题时那些关键的“灵光一现”。这不仅仅是Writeup更是一次思维训练让你明白下次遇到类似“CTF秀crypto第二题”那种看似无从下手的题目时应该从何想起。2. 赛题核心思路与常见攻击模式解析TSGCTF的密码学题目向来以“优雅的难题”著称它们很少考察冷僻的算法而是喜欢在常见的RSA、离散对数、流密码等基础上设置一些精巧的约束条件或组合模式。理解这些常见攻击模式的本质是解题的第一步。2.1 模数分解与共模攻击的变种在RSA相关题目中单纯的给一个N让你分解在现在的比赛中已经几乎绝迹。更常见的是提供多个相关密文或密钥片段。比如一道题可能给你两个使用相同模数N、不同加密指数e1和e2加密同一明文m得到的密文c1和c2。这就是经典的共模攻击场景。其核心原理是利用扩展欧几里得算法找到满足e1*s1 e2*s2 1的整数s1和s2通常一正一负然后计算(c1^s1 * c2^s2) mod N其结果就等于m^(e1*s1 e2*s2) m^1 m。这里的关键是理解指数运算在模N下的可乘性。但TSGCTF可能会在此基础上增加难度。例如它可能不直接给你c1和c2而是给你用e1加密的m和用e2加密的m的某个线性变换比如m1。这时你就不能直接套用共模攻击公式。你需要设未知数建立方程。假设c1 ≡ m^e1 (mod N),c2 ≡ (m1)^e2 (mod N)。虽然不能直接恢复m但你可以利用这两个式子在整数环上构造一个关于m的多项式方程。例如从c1你可以得到m ≡ c1^d1 (mod N)的关系虽然d1未知但这个关系可以代入第二个式子进行推理。更实用的方法是注意到m和m1相差1结合c1和c2有时可以通过计算c2 * inverse(c1, N)^e2在模N下来消去m的高次项得到一个只与N和已知量有关的等式可能泄露N的因子。这要求对模运算和代数变形有深刻的理解。注意当指数e1和e2不互素时比如都是偶数标准的共模攻击可能失效因为s1和s2可能不存在整数解使得和为1。此时需要先计算g gcd(e1, e2)如果g较小可以考虑对c1和c2开g次方根在整数域尝试得到新的c1和c2然后对e1/g和e2/g应用共模攻击。2.2 基于中国剩余定理CRT的漏洞与故障注入RSA的CRT中国剩余定理优化算法是提高解密速度的标准方法但它也引入了新的攻击面即故障攻击。在CTF中这通常以“部分密钥泄露”或“错误签名”的形式出现。题目可能给你一个正常的RSA签名S以及另一个在CRT计算过程中某个模数项如Sp m^d mod p出错后得到的错误签名S。攻击原理如下设N p * q私钥d。正常签名S m^d mod N。根据CRT计算会分解为Sp m^d mod pSq m^d mod q再用CRT组合得到S。 如果计算Sp时发生故障得到错误的Sp那么组合出的错误签名S将满足S ≡ Sp (mod p)- 所以S - Sp ≡ 0 (mod p)S ≡ Sq (mod q)- 所以S - Sq ≡ 0 (mod q)不一定成立。 但关键是正确的S满足S ≡ Sp (mod p)和S ≡ Sq (mod q)。 如果我们有正确的S和错误的S那么计算gcd(S - S, N)。因为S - S ≡ (Sp - Sp) ≡ 0 (mod p)因为Sp和Sp都是模p下的数它们的差是p的倍数。S - S ≡ (Sq - Sq) ≡ 0 (mod q)不一定成立除非故障也影响了Sq通常题目假设只影响一个分支。 因此S - S很大概率是p的倍数而不是q的倍数那么gcd(S - S, N)就会得到p从而分解N。在TSGCTF中题目可能不会直接告诉你哪个是错误签名。它可能给你多个签名其中一些是正常的一些是有错误的让你自己去判断和利用。这就需要你编写脚本尝试计算所有签名对之间的gcd寻找非1和N的最大公约数。2.3 流密码与线性反馈移位寄存器LFSR的逆向流密码特别是基于LFSR的是Crypto方向的常客。LFSR的状态更新是线性的这既是其实现简单的优点也是其安全性的弱点。攻击的核心往往是利用密钥流keystream与初始状态密钥之间的线性关系。一个最简单的n级LFSR其下一时刻的状态是当前状态比特的线性组合。如果我们得到了足够长的密钥流片段至少2n比特我们就可以建立一系列线性方程来求解LFSR的反馈系数即抽头位置或初始状态。这通常通过Berlekamp-Massey (BM) 算法来完成该算法可以根据输出序列找到生成该序列的最短LFSR的阶数和反馈多项式。TSGCTF的题目可能会在简单LFSR基础上增加层次非线性组合生成器使用多个LFSR它们的输出通过一个非线性函数f组合成最终的密钥流比特。攻击思路往往是先猜测非线性函数f的结构如果未知或者如果f是已知的但涉及多个LFSR的少量输出可以尝试相关攻击即寻找密钥流与单个LFSR输出之间的相关性。带钟控的LFSR一个LFSR的输出决定另一个LFSR是否步进。这打破了输出的直接线性关系但通过分析停走模式可能可以建立概率模型。已知明文攻击与矩阵求解如果知道一段明文和对应的密文那么就能得到一段密钥流。对于LFSR密钥流k[i]与初始状态S满足线性关系k S * M其中M是由反馈多项式构成的矩阵。已知k求解S就是一个解线性方程组的问题在GF(2)上。TSGCTF可能会把状态S设计得比较大比如256位但给出的密钥流长度刚好够建立方程考察选手用SageMath或Python的numpy在GF(2)上求解大规模矩阵方程的能力。3. 典型赛题实战拆解与复现下面我们虚拟还原两道符合TSGCTF风格的题目并一步步拆解解题过程。请注意为了教学清晰我简化了部分参数但核心考点和攻击模式完全一致。3.1 题目一冗余的CRTRedundant CRT题目描述服务器实现了一个RSA签名服务使用CRT进行加速。由于代码bug服务器在计算签名时偶尔会错误地重复计算CRT中的q分支即计算两次Sq而p分支计算正确。我们得到了同一个消息m的10个签名其中大部分是正常的但恰好有一个签名是这种“冗余CRT”错误导致的。你能分解出N吗已知N2048位e65537消息m一个已知的随机长整数以及10个签名sig_list。解题思路拆解理解故障模型正常CRT签名S CRT(Sp, Sq)其中Sp m^d mod p,Sq m^d mod q。 错误签名模型S CRT(Sp, Sq, Sq)这说不通。更合理的解释是在组合CRT时错误地使用了错误的模数或系数。一个经典的“冗余”bug是在计算中国剩余定理的系数时用于q的系数被计算了两次。具体来说正常CRT组合公式为S Sq * (p * inv(p mod q)) Sp * (q * inv(q mod p)) mod N假设计算Sq的系数时本应是(p * inv(p mod q))但错误地变成了(p * inv(p mod q)) * t其中t是某个值比如2或者另一个inv(p mod q)。这会导致最终签名S在模q下仍然正确因为S ≡ Sq (mod q)但在模p下是错误的。建立数学关系设正常签名为S错误签名为S。我们有S ≡ m^d (mod N)-S^e ≡ m (mod N)验证通过。S在模q下验证通过S^e ≡ m (mod q)但在模p下不通过。 因此S^e - m是q的倍数但不是p的倍数大概率。同理S^e - m是N的倍数即p*q的倍数。构造攻击计算gcd(S^e - m, N)。因为S^e - m ≡ 0 (mod q)且S^e - m ≢ 0 (mod p)所以这个最大公约数就是q。从而分解N。 但问题是我们不知道10个签名中哪个是错的。所以需要遍历所有签名sig计算gcd(sig^e - m, N)。对于正常签名sig^e - m是N的倍数gcd结果就是N本身。对于错误签名gcd结果将是q一个大约1024位的大数。实操脚本import math from Crypto.Util.number import long_to_bytes, bytes_to_long # 假设已知以下变量 N 0xabcdef... # 2048位的N e 65537 m bytes_to_long(bKnown_Message_For_Signing) sig_list [ ... ] # 10个签名每个都是长整数 for i, sig in enumerate(sig_list): g math.gcd(pow(sig, e, N) - m, N) if g ! 1 and g ! N: print(fFound faulty signature at index {i}) q g p N // q print(fp {p}) print(fq {q}) break关键点与陷阱计算pow(sig, e, N)时一定要模N否则中间结果会巨大无比。验证分解出p和q后应计算phi (p-1)*(q-1)d pow(e, -1, phi)然后用私钥d验证是否能正确生成其他正常签名。这可以双重确认。为什么错误签名验证S^e ≡ m (mod N)会失败因为故障导致S不再是m^d mod N的正确值。服务器在生成错误签名后自己用S^e mod N验证也会失败但题目场景可能是服务器记录了这个错误的输出或者攻击者截获了错误中间值。这道题考察了对CRT实现细节的深刻理解以及如何将模糊的“冗余”描述转化为具体的、可计算的数学故障模型。3.2 题目二颤抖的LFSRShaky LFSR题目描述一个保密的流密码使用了一个80位的LFSR但其反馈多项式是未知的。我们通过侧信道获取了密钥流的前200位但得知在生成过程中由于硬件不稳定有少量比特不超过5位可能发生了翻转即0变1或1变0。你能还原出原始的LFSR反馈多项式吗已知keystream200位长的比特串可能有最多5个错误。解题思路拆解核心挑战标准的BM算法要求输入序列是精确的由某个LFSR生成的。现在序列中有少量错误直接使用BM算法会得到一个非常长可能接近200阶的、不正确的反馈多项式因为算法会试图用复杂的线性关系去拟合那些错误比特。攻击思路错误比特数很少≤5这是一个典型的纠错问题。我们可以暴力枚举错误的位置。200位中选5位出错组合数C(200,5)非常大直接暴力不可行。需要优化。利用LFSR的线性特性一个n级的LFSR其输出序列满足线性递推关系s[in] c0*s[i] c1*s[i1] ... c_{n-1}*s[in-1] mod 2其中c_i是反馈系数。对于一段没有错误的序列任意连续2n位都可以建立方程组解出c_i。反过来如果我们猜对了反馈多项式即系数c_i那么我们可以用这个多项式去验证整个序列用前n位预测第n1位看是否匹配然后滑动窗口一直预测下去。如果序列中有错误预测就会失败。具体步骤 a.假设LFSR阶数n题目说80位我们就从80开始尝试。也可以试探性尝试70-90的范围。 b.枚举错误模式我们不需要枚举所有5个错误的位置。一个更聪明的办法是先假设序列前2n位例如160位中没有错误或者错误很少。我们用这2n位通过解线性方程组或BM算法求出一个候选的反馈多项式P。 c.用多项式P验证并定位错误用求出的P去预测整个200位的序列。记录预测值与给定keystream不符的位置。这些位置就是潜在的“错误点”。如果这样的位置数量很少≤5并且它们分布合理比如如果我们纠正了这些位置的比特整个序列就能被P完美预测那么我们就找到了正确的P和错误位置。 d.迭代精炼由于前2n位也可能包含错误我们第一次求出的P可能不对。我们可以把上一步找出的疑似错误位置进行纠正翻转比特得到一个新的、更干净的序列片段然后用这个新片段重新计算P。重复这个过程几次可能会收敛到正确的解。实操脚本SageMath环境# SageMath 代码 def berlekamp_massey(seq): 标准BM算法返回生成该序列的最短LFSR的反馈多项式系数列表低位对应最早项 n len(seq) C [1] [0]*n # 连接多项式 B [1] [0]*n # 辅助多项式 L 0 m -1 b 1 for N in range(n): d seq[N] for i in range(1, L1): d ^ (C[i] seq[N-i]) # GF(2)上的内积 if d 1: T C[:] for i in range(0, n-Nm): C[N-mi] ^ B[i] if L N//2: L N 1 - L m N B T b d # 返回多项式系数C[0]是常数项1C[1..L]是反馈系数 return C[:L1] def verify_poly(poly, seq): 用多项式poly预测序列seq返回错误位置列表 n len(poly) - 1 # LFSR阶数 errors [] # 使用前n位作为初始状态 state seq[:n] for i in range(n, len(seq)): # 计算下一个比特 next_bit 0 for j in range(n): next_bit ^ (poly[j1] state[j]) # poly[0]是常数项1忽略 predicted next_bit if predicted ! seq[i]: errors.append(i) # 更新状态窗口 state state[1:] [predicted] # 注意这里用预测值更新模拟无错运行 # 但为了验证更好的方法是始终用原始seq更新状态除了在错误点我们不知道真实值 # 所以我们换一种验证方式用poly和原始seq的前i位计算下一个预测与seq[i]比较 # 更准确的验证滑动窗口计算 errors [] for i in range(len(seq) - n): window seq[i:in] next_bit sum(poly[j1]*window[j] for j in range(n)) % 2 if next_bit ! seq[in]: errors.append(in) return errors # 假设keystream是0/1列表长度200 keystream [0,1,1,0,...] # 你的数据 max_errors 5 candidate_n 80 for n in range(70, 91): # 尝试70到90的阶数 print(fTrying n {n}) # 取前2n位尝试计算初始多项式 subseq keystream[:2*n] poly berlekamp_massey(subseq) if len(poly) - 1 ! n: # BM找到的阶数不是n说明这段子序列可能包含错误或者n猜错了 continue errors verify_poly(poly, keystream) if len(errors) max_errors: print(fPotential found: n{n}, poly{poly}, errors at {errors}) # 可以尝试纠正错误重新计算验证 corrected_stream keystream[:] for pos in errors: corrected_stream[pos] ^ 1 # 翻转错误比特 # 用纠正后的完整序列再跑一次BM看多项式是否稳定 poly2 berlekamp_massey(corrected_stream) if poly poly2: print(fConfirmed! LFSR polynomial: {poly}) break关键点与陷阱BM算法对错误极其敏感。即使只有一个比特错误产生的多项式阶数也可能接近序列长度。我们的策略是基于“错误很少”的假设通过“猜测-验证-纠正”的循环来逼近答案。这本质上是一种穷搜但将搜索空间从C(200,5)降低到了对多项式阶数n和少量错误位置的搜索。在实际CTF中可能错误比特数是一个提示如“不超过5位”如果没有提示可能需要尝试不同的错误上限。验证时注意我们是用多项式去“预测”下一个比特并与给定序列比较。如果预测失败不一定就是该位置错了也可能是更早的位置错了导致状态偏离。所以算法可能需要多次迭代纠正。这道题将经典的流密码分析与纠错思想结合考察选手在非理想条件下有噪声的数据应用密码分析工具的能力。4. 实战中遇到的问题与深度排查技巧在实际操作中尤其是比赛环境下理论正确不代表能快速拿到flag。下面分享几个我踩过的坑和总结的技巧。4.1 数学运算的精度与边界问题问题场景在解一道涉及大整数开根或求解模方程的题目时脚本运行结果莫名奇妙或者得到负数、非常小的数。排查与解决检查整数与浮点数Python中/是浮点除法//是整数除法。在密码学计算中除非明确需要浮点否则一律使用//和%。例如计算(p-1)*(q-1)时确保p和q是整数。模逆元的存在性计算d pow(e, -1, phi)前必须确认gcd(e, phi) 1。如果不互素则模逆元不存在这是RSA的基本要求。如果题目故意给了不互素的e和phi那可能就是突破口意味着N可能不是标准的两个素数相乘或者phi计算有误可能是多素数RSA。大整数幂运算的内存与时间直接计算pow(a, b)而不取模结果会巨大无比导致内存溢出。务必使用pow(a, b, N)进行模幂运算。对于非常大的指数比如私钥dPython的pow函数配合三个参数是高度优化的。开方与近似当需要计算iroot整数次方根时使用gmpy2库的iroot函数或者用Python的int(x ** (1/n))并上下调整。注意浮点数精度问题对于非常大的数**运算可能产生精度误差。最安全的方法是使用二分查找法求整数根。def integer_nth_root(x, n): 返回 (y, bool)其中y是整数bool为True表示y^n x lo, hi 0, x while lo hi: mid (lo hi) // 2 pow_mid pow(mid, n) if pow_mid x: return mid, True elif pow_mid x: lo mid 1 else: hi mid - 1 return hi, False # hi是小于等于真实根的最大整数4.2 数据编码与格式转换的暗坑问题场景明明解密出了数字m转成字节后却是乱码或者提交flag格式不对。排查与解决字节序与整数转换long_to_bytes和bytes_to_long来自Crypto.Util.number是标准做法。但要注意这些函数默认使用大端序big-endian即最高有效字节在前。绝大多数CTF题目都遵循这个约定。如果遇到小端序的题目通常会有明确提示。处理非ASCII字符解密出的字节流可能包含不可打印字符。不要直接print可以用repr()查看转义形式或者用.hex()方法输出十六进制。Flag可能藏在十六进制字符串的特定位置。多种编码尝试如果直接转字节不对尝试以下常见编码long_to_bytes(m).decode(utf-8)如果明文是文本long_to_bytes(m).decode(latin-1)处理任意字节将整数m转为十六进制字符串hex(m)[2:]然后看是否有666c6167‘flag’的hex等模式。Flag格式CTFflag通常有固定格式如TSGCTF{...}、flag{...}、SECCON{...}等。解密出的明文可能就是这个完整字符串也可能只是花括号内的内容需要你加上前缀。仔细阅读题目描述。4.3 脚本调试与交互题技巧问题场景面对一个需要连接远程服务器、进行多轮交互的题目本地测试成功但远程却拿不到flag。排查与解决使用Pwntools这是CTF交互题的标配库。它处理TCP连接、发送接收数据、处理超时比用socket库手动写方便得多。务必熟悉recvline,recvuntil,sendline,interactive等基本方法。注意延迟与缓冲区远程服务器可能有响应延迟或者会一次性发送多行数据。使用recvuntil(bkeyword:)来稳定地接收到某个提示符为止避免因为接收不完整而解析错误。本地化测试如果题目提供了源码或描述足够清晰尽量在本地搭建一个模拟环境进行测试。用Python启动一个简单的socket服务器来模拟远程行为可以极大加快调试速度。日志与打印在脚本的关键步骤添加打印语句输出中间变量如收到的N、e、密文等。对于大整数可以打印其16进制的前后几位例如hex(N)[:20] ... hex(N)[-20:]以确认数据接收正确。异常处理网络可能不稳定。在循环交互中使用try...except捕获超时或连接错误并实现重试逻辑。4.4 思维定式与信息遗漏问题场景一道题卡了很久觉得所有思路都试过了最后发现漏看了一个附件里的注释或者误解了题目描述的一个词。排查与解决逐字阅读题目描述题目中的每一个词都可能有用。“偶尔”、“恰好有一个”、“冗余”、“颤抖”这些词都在暗示特定的攻击模型。将描述转化为精确的数学条件。检查所有附件除了主要的chall.py或task.py还要看有没有output.txt、data.txt、Dockerfile、README。Dockerfile里可能提示了环境或库版本README可能有提示。逆向思维如果正向攻击走不通想想是不是题目在考“构造”而不是“破解”。例如给你一个漏洞让你构造特殊的输入使服务器产生错误从而泄露信息。或者让你为一个弱的密码系统生成一对有效的明文-密文。利用搜索引擎和社区对于TSGCTF这种知名比赛其题目往往借鉴或改编自已知的密码学攻击论文或经典漏洞。用题目中的关键词如“Redundant CRT”加上“CTF writeup”搜索可能会找到相似的思路。但切记这应该是最后的手段并且重在理解思路而非抄袭答案。5. 工具链与学习资源推荐工欲善其事必先利其器。一套顺手的工具和高质量的学习资源能让你事半功倍。5.1 核心编程环境与库Python3 SageMath这是密码学方向的绝对主力。常规代数运算、RSA、离散对数用Python足矣。但涉及环、域、椭圆曲线、格基约减等高级运算SageMath是神器。它集成了Python语法和大量数学库可以像写数学公式一样操作多项式、矩阵和代数结构。建议通过Docker或直接安装SageMath。关键Python库Crypto.Util.number提供long_to_bytes,bytes_to_long,GCD,inverse等基础函数。gmpy2处理大整数运算和素性检测速度比Python原生整数快很多尤其是gcd,invert,iroot等函数。sympy符号计算可用于解方程、化简表达式在推导公式时很有用。numpy处理大规模线性方程组在GF(2)上需手动处理或使用galois库。交互工具pwntools用于网络交互题requests用于HTTP API类题目。5.2 针对性学习路径从经典到现代起步彻底理解RSA的原理、加解密、签名、各种基础攻击小公钥/小私钥、共模、广播、Franklin-Reiter相关消息攻击。进阶学习离散对数问题DLP在有限域上的求解BSGS、Pohlig-Hellman椭圆曲线密码学ECC的基本概念和简单攻击Smart攻击、MOV攻击。深入格基约减LLL算法及其在密码分析中的应用解小根方程、攻击RSA with dp泄露、背包密码等。这部分难度较大但TSGCTF等高端赛经常涉及。实践平台CTF秀、CTFHub、BugKu的Crypto板块适合新手入门题目分类清晰。CryptoHack交互式学习平台将密码学概念分解成一个个小挑战从易到难是系统学习的最佳途径之一。各大CTF赛事归档在CTFtime.org上找到历年比赛直接搜索“TSGCTF crypto writeup”阅读高质量的解题报告。不仅要看步骤更要理解解题者的思考过程。理解“为什么”每做一道题都要问自己出题人在这里设置了什么陷阱这个攻击为什么能成立它的前提条件是什么如果改变某个参数比如增加错误比特数攻击还成立吗这种追根问底的习惯能让你从“解出一道题”上升到“掌握一类题”。回过头看无论是TSGCTF的难题还是“CTF秀crypto第二题”那样的入门题其核心都是将密码学原理置于一个稍微非常规的场景下。解题的关键不在于记忆更多的攻击脚本而在于培养一种能力将模糊的文字描述转化为精确的数学模型并判断该模型对应哪种已知的攻击模式或需要何种新的组合推理。这需要扎实的基础知识、细致的观察力和不断的练习。下次当你再被一道题卡住时不妨停下来在白板上画一画数据流写一写数学等式也许那条隐藏的路径就清晰了。