现代密码学实验四
现代密码学实验报告RSA加密体制破译2016全国密码数学挑战赛赛题三–摘要 (Abstract)本实验基于2016年全国高校密码数学挑战赛的RSA体制破译赛题对一个具有底层参数生成缺陷的1024比特RSA加解密软件进行了全面的安全性分析与破译。实验利用该软件在素数生成机制随机数发生器缺陷、通信习惯重复发送以及公共模数管理等方面的漏洞综合应用了 GCD 因数碰撞、公共模数攻击、Hastad 低加密指数广播攻击、费马因式分解以及 Pollard’s p-1 因式分解等五种经典密码分析学算法。通过自动化脚本对截获的加密数据帧进行批量扫描成功还原了绝大部分明文碎片。对于少数因参数具备强安全属性而未能直接破译的碎片实验结合自然语言的语义上下文进行了逻辑推演最终完整地还原了发送方 Alice 的英文通关密语。本次实验深刻验证了“RSA算法的安全性不仅依赖于模数的长度更依赖于其参数生成的严谨性”这一核心密码学原则。一、 题目描述本次实验的核心目标是破译一个基于存在漏洞的RSA软件生成的加密通信数据。题目设定发送方 Alice 使用该软件发送了一段通关密语所有的通信数据已被截获为多个数据帧FrameXX。已知该 RSA 密码体制的模数NpqNpqNpq规模为 1024 比特但素数ppp和qqq是由某一随机数发生器生成的这暗示了素数之间可能存在统计缺陷或碰撞风险。在加密规则上每次最多对 8 个字符64比特的明文分片进行加密。在执行模幂运算前软件会将明文填充Padding为 512 比特格式为高位64比特标志位 32比特通信序号 若干比特0 64比特明文ASCII码截获的每个帧数据文件包含 3072 比特的十六进制数据依次为1024 比特的模数NNN、1024 比特的加密指数eee和 1024 比特的密文ccc。此外Alice 初次使用软件可能存在多次重复发送相同明文分片的行为。参赛者需要仅利用这些截获的加密帧通过数论分析与密码攻击方法尽可能多地恢复通关密语及 RSA 参数。二、 破译过程与原理解析针对该 RSA 加密系统破译过程的核心在于识别并利用参数生成和使用者行为上的漏洞。在此背景下主要利用了以下五种密码学攻击原理GCD 因数碰撞法由于该软件的随机数发生器存在缺陷不同的数据帧可能生成了相同的素数因子。通过对所有帧的模数NNN进行两两最大公约数计算gcd(Ni,Nj)\gcd(N_i, N_j)gcd(Ni,Nj)若结果大于 1则可直接分解出素数ppp和qqq进而求得私钥解密。公共模数攻击若发现两个帧使用了完全相同的模数NNN但加密指数e1,e2e_1, e_2e1,e2不同且互素便可通过扩展欧几里得算法求出裴蜀系数利用两次密文的组合直接还原明文。Hastad 低加密指数广播攻击已知 Alice 会重复发送同一分片若同一明文被相同的低加密指数如e5e5e5在不同模数下多次加密利用中国剩余定理CRT即可在实数域内直接开高次方根得出明文。费马因式分解法针对随机数发生器产生的两个非常接近的素数ppp和qqqNNN会极其接近某个数的平方通过寻找A≈NA \approx \sqrt{N}A≈N使A2−NA^2 - NA2−N构成完全平方数即可实现NNN的快速分解。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, errorsignore) 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. 低加密指数广播攻击 (e3 或 e5) 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, fHastad广播攻击(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. Pollards 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 fFrame{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)
)
)
