现代密码学实验四

现代密码学实验报告：RSA加密体制破译（2016全国密码数学挑战赛赛题三）

–

摘要 (Abstract)

本实验基于2016年全国高校密码数学挑战赛的RSA体制破译赛题，对一个具有底层参数生成缺陷的1024比特RSA加解密软件进行了全面的安全性分析与破译。实验利用该软件在素数生成机制（随机数发生器缺陷）、通信习惯（重复发送）以及公共模数管理等方面的漏洞，综合应用了 GCD 因数碰撞、公共模数攻击、Hastad 低加密指数广播攻击、费马因式分解以及 Pollard’s p-1 因式分解等五种经典密码分析学算法。

通过自动化脚本对截获的加密数据帧进行批量扫描，成功还原了绝大部分明文碎片。对于少数因参数具备强安全属性而未能直接破译的碎片，实验结合自然语言的语义上下文进行了逻辑推演，最终完整地还原了发送方 Alice 的英文通关密语。本次实验深刻验证了“RSA算法的安全性不仅依赖于模数的长度，更依赖于其参数生成的严谨性”这一核心密码学原则。

一、 题目描述

本次实验的核心目标是破译一个基于存在漏洞的RSA软件生成的加密通信数据。题目设定发送方 Alice 使用该软件发送了一段通关密语，所有的通信数据已被截获为多个数据帧（FrameXX）。

已知该 RSA 密码体制的模数N=pqN=pqN=pq规模为 1024 比特，但素数ppp和qqq是由某一随机数发生器生成的，这暗示了素数之间可能存在统计缺陷或碰撞风险。在加密规则上，每次最多对 8 个字符（64比特）的明文分片进行加密。在执行模幂运算前，软件会将明文填充（Padding）为 512 比特，格式为：
高位64比特标志位 + 32比特通信序号 + 若干比特0 + 64比特明文ASCII码

截获的每个帧数据文件包含 3072 比特的十六进制数据，依次为：1024 比特的模数NNN、1024 比特的加密指数eee和 1024 比特的密文ccc。此外，Alice 初次使用软件可能存在多次重复发送相同明文分片的行为。参赛者需要仅利用这些截获的加密帧，通过数论分析与密码攻击方法，尽可能多地恢复通关密语及 RSA 参数。

二、 破译过程与原理解析

针对该 RSA 加密系统，破译过程的核心在于识别并利用参数生成和使用者行为上的漏洞。在此背景下，主要利用了以下五种密码学攻击原理：

1. GCD 因数碰撞法：由于该软件的随机数发生器存在缺陷，不同的数据帧可能生成了相同的素数因子。通过对所有帧的模数NNN进行两两最大公约数计算（gcd⁡(Ni,Nj)\gcd(N_i, N_j)gcd(Ni​,Nj​)），若结果大于 1，则可直接分解出素数ppp和qqq，进而求得私钥解密。
2. 公共模数攻击：若发现两个帧使用了完全相同的模数NNN但加密指数e1,e2e_1, e_2e1​,e2​不同且互素，便可通过扩展欧几里得算法求出裴蜀系数，利用两次密文的组合直接还原明文。
3. Hastad 低加密指数广播攻击：已知 Alice 会重复发送同一分片，若同一明文被相同的低加密指数（如e=5e=5e=5）在不同模数下多次加密，利用中国剩余定理（CRT）即可在实数域内直接开高次方根得出明文。
4. 费马因式分解法：针对随机数发生器产生的两个非常接近的素数ppp和qqq，NNN会极其接近某个数的平方，通过寻找A≈NA \approx \sqrt{N}A≈N​使A2−NA^2 - NA2−N构成完全平方数，即可实现NNN的快速分解。
5. Pollard’s p-1 因式分解法：当随机生成的素数导致p−1p-1p−1极其“光滑”（即仅包含较小素因子）时，依据费马小定理，通过迭代计算即可剥离出素数ppp。

核心实验步骤：

• 第一步（数据解析）：利用文件I/O读取所有截获的 Frame 数据文件，并按照每 256 个十六进制字符切片，将模数NNN、加密指数eee和密文ccc解析为大整数类型。
• 第二步（漏洞扫描）：将解析出的参数集合依次传入上述五种攻击算法模块中。一旦某种算法成功分解了NNN或直接还原了密文，即保存结果。
• 第三步（明文解包）：将解密得到的 512 比特大整数转换为十六进制字符串，根据题目既定的填充格式，提取出其中的 32 比特通信序号以及尾部的 64 比特（8字符）明文 ASCII 码片段。
• 第四步（密语拼装）：将所有成功破译的碎片按照提取出的通信序号依次进行排列，拼接出原始的文本信息。

自动化破译脚本代码

import os def egcd(a, b): if a == 0: return b, 0, 1 g, y, x = egcd(b % a, a) return g, x - (b // a) * y, y def modinv(a, m): g, x, y = egcd(a, m) if g != 1: raise Exception('Modular inverse does not exist') return x % m def iroot(k, n): u, s = n, n + 1 while u < s: s = u t = (k - 1) * s + n // pow(s, k - 1) u = t // k return s def extract_message(m_int, frame_idx, method_name): m_hex = hex(m_int)[2:].zfill(128) try: seq = int(m_hex[16:24], 16) ascii_msg = bytes.fromhex(m_hex[-16:]).decode('ascii', errors='ignore') print(f"[+] 成功破译! 帧: Frame{frame_idx} | 方法: {method_name} | 序号: {seq:02d} | 碎片内容: '{ascii_msg}'") return (seq, ascii_msg) except: return None def attack_gcd(ns, es, cs): """1. 因数碰撞法""" results = [] for i in range(len(ns)): for j in range(i + 1, len(ns)): p = math.gcd(ns[i], ns[j]) if 1 < p < ns[i]: for idx in [i, j]: q = ns[idx] // p phi = (p - 1) * (q - 1) try: d = modinv(es[idx], phi) m = pow(cs[idx], d, ns[idx]) results.append((idx, m, "GCD因数碰撞")) except: pass return results def attack_common_modulus(ns, es, cs): """2. 公共模数攻击""" results = [] for i in range(len(ns)): for j in range(i + 1, len(ns)): if ns[i] == ns[j] and es[i] != es[j]: n = ns[i] g, x, y = egcd(es[i], es[j]) c1 = cs[i] if x > 0 else modinv(cs[i], n) c2 = cs[j] if y > 0 else modinv(cs[j], n) m = (pow(c1, abs(x), n) * pow(c2, abs(y), n)) % n results.append((i, m, "公共模数攻击")) results.append((j, m, "公共模数攻击")) return results def attack_hastad(ns, es, cs): """3. 低加密指数广播攻击 (e=3 或 e=5)""" results = [] e_dict = {} for i, e in enumerate(es): if e in [3, 5]: e_dict.setdefault(e, []).append((cs[i], ns[i], i)) for e, items in e_dict.items(): if len(items) >= e: subset = items[:e] N_total = 1 for _, n, _ in subset: N_total *= n m_e = 0 for c, n, _ in subset: m_i = N_total // n _, inv, _ = egcd(m_i, n) m_e += c * inv * m_i m_e %= N_total m = iroot(e, m_e) if pow(m, e, subset[0][1]) == subset[0][0]: for _, _, idx in subset: results.append((idx, m, f"Hastad广播攻击(e={e})")) return results def attack_fermat(ns, es, cs): """4. 费马因式分解 (针对 p,q 极近)""" results = [] for i, n in enumerate(ns): a = math.isqrt(n) + 1 b2 = a * a - n b = math.isqrt(b2) count = 0 while b * b != b2 and count < 100000: # 设置阈值防止死循环 a += 1 b2 = a * a - n b = math.isqrt(b2) count += 1 if b * b == b2: p, q = a + b, a - b phi = (p - 1) * (q - 1) try: d = modinv(es[i], phi) m = pow(cs[i], d, n) results.append((i, m, "费马分解法")) except: pass return results def attack_pollard_p1(ns, es, cs): """5. Pollard's p-1 (针对 p-1 光滑)""" results = [] for i, n in enumerate(ns): a = 2 for j in range(2, 50000): # 阈值 a = pow(a, j, n) p = math.gcd(a - 1, n) if 1 < p < n: q = n // p phi = (p - 1) * (q - 1) try: d = modinv(es[i], phi) m = pow(cs[i], d, n) results.append((i, m, "Pollard p-1分解")) except: pass break return results if __name__ == "__main__": ns, es, cs = [], [], [] frames_count = 21 print("[*] 正在加载密文数据帧...") for i in range(frames_count): filename = f"Frame{i}" if not os.path.exists(filename): ns.append(1); es.append(1); cs.append(1) continue with open(filename, "r") as f: data = f.read().strip() ns.append(int(data[0:256], 16)) es.append(int(data[256:512], 16)) cs.append(int(data[512:768], 16)) print("[*] 开始进行多重 RSA 漏洞破译...\n") all_results = [] all_results.extend(attack_gcd(ns, es, cs)) all_results.extend(attack_common_modulus(ns, es, cs)) all_results.extend(attack_hastad(ns, es, cs)) all_results.extend(attack_fermat(ns, es, cs)) all_results.extend(attack_pollard_p1(ns, es, cs)) recovered_fragments = {} for idx, m_int, method in all_results: parsed = extract_message(m_int, idx, method) if parsed: seq, txt = parsed recovered_fragments[seq] = txt print("\n" + "=" * 50) print("[*] 拼接最终通关密语:") final_message = "" for seq in sorted(recovered_fragments.keys()): final_message += recovered_fragments[seq] print(f"\n=> 最终明文为: {final_message}") print("=" * 50)