CTF实战：手把手教你用Python脚本破解RSA低加密指数广播攻击（附完整代码）

CTF实战用Python脚本破解RSA低加密指数广播攻击的完整指南在CTF竞赛中RSA加密系统一直是密码学挑战的热门考点。其中低加密指数广播攻击Low Public Exponent Broadcast Attack因其巧妙的数学原理和实际应用价值成为参赛者必须掌握的技能。本文将带你从零开始深入理解攻击原理并手把手教你编写自动化破解脚本。1. 攻击原理深度解析低加密指数广播攻击的核心场景是当同一份明文m被多个不同的公钥(e,n_i)加密且加密指数e较小时常见e3或e65537攻击者可以通过收集足够多的密文c_i来恢复原始明文。数学基础中国剩余定理CRT给定同余方程组m^e ≡ c1 mod n1 m^e ≡ c2 mod n2 ... m^e ≡ ck mod nk当k ≥ e时可通过CRT求出m^e的精确值由于m^e ∏n_i直接开e次方即可得m实战中的变种当不同n_i存在共同素因子时可先通过计算gcd(n_i, n_j)来分解模数。这也是BUUCTF RSA5题目的实际考察点。2. 环境准备与工具配置工欲善其事必先利其器。我们需要配置以下Python环境pip install gmpy2 libnum关键库的作用gmpy2提供大整数运算和快速GCD计算libnum辅助进行数字与字节流的转换注意在CTF竞赛环境中通常已预装这些库。本地测试时建议使用Python 3.8版本3. 攻击脚本分步实现3.1 输入数据处理首先组织题目给出的数据。以BUUCTF RSA5为例import gmpy2 from libnum import n2s e 65537 n [n0, n1, n2, ..., n19] # 实际题目中的20个n值 c [c0, c1, c2, ..., c19] # 对应的20个密文3.2 模数分解检测寻找具有共同素因子的模数对def find_common_factor(n_list): for i in range(len(n_list)): for j in range(i1, len(n_list)): gcd gmpy2.gcd(n_list[i], n_list[j]) if gcd ! 1: return i, j, gcd return None, None, None i, j, p find_common_factor(n) if p: print(fFound common factor between n[{i}] and n[{j}]) print(fp {p}) q n[i] // p3.3 私钥计算与解密得到p和q后计算私钥d并解密def decrypt(p, q, e, c): phi (p-1)*(q-1) d gmpy2.invert(e, phi) m pow(c, d, p*q) return n2s(int(m)) plaintext decrypt(p, q, e, c[i]) print(fDecrypted: {plaintext})4. 完整自动化脚本将上述步骤整合为完整解决方案import gmpy2 from libnum import n2s def rsa_broadcast_attack(n_list, c_list, e): # Step 1: Find common factors for i in range(len(n_list)): for j in range(i1, len(n_list)): p gmpy2.gcd(n_list[i], n_list[j]) if p ! 1: print(f[] Found common factor between n[{i}] and n[{j}]) q n_list[i] // p # Step 2: Compute private key phi (p-1)*(q-1) try: d gmpy2.invert(e, phi) except: continue # Step 3: Decrypt message m pow(c_list[i], d, n_list[i]) return n2s(int(m)) return b # 示例用法 e 65537 n [n0, n1, ..., n19] # 填入实际n值 c [c0, c1, ..., c19] # 填入实际c值 flag rsa_broadcast_attack(n, c, e) print(fFlag: {flag})5. 实战技巧与注意事项效率优化当n数量较多时两两计算GCD可能较慢可先对n进行排序优先比较大小接近的模数错误处理try: d gmpy2.invert(e, phi) except ZeroDivisionError: print(Inversion failed - wrong factors) continue扩展场景如果没有共同因子需使用标准的低指数广播攻击实现CRT恢复m^e的代码示例def crt_attack(c_list, n_list, e): N 1 for ni in n_list: N * ni result 0 for ci, ni in zip(c_list, n_list): Ni N // ni inv_Ni gmpy2.invert(Ni, ni) result ci * Ni * inv_Ni m gmpy2.iroot(result % N, e) if m[1]: # 检查是否完全开方 return n2s(int(m[0])) return b在CTF竞赛中遇到类似题目时建议先检查模数是否存在共同因子再决定采用哪种攻击方式。掌握这两种方法你就能应对绝大多数RSA广播攻击的变种题目。