本实验基于 RSA 公钥加密算法，通过分析截获的 21 个加密 Frame 数据，使用多种密码分析攻击方法完成密文破解。攻击方法包括：GCD 攻击、共模攻击、低指数广播攻击、Pollard p-1 分解及 Fermat 分解等。实验成功恢复了大部分明文分片，并按通信序号拼接得到完整明文，验证了 RSA 系统在特定条件下可能存在的安全漏洞。实验过程中，针对不同攻击策略，优化了解密参数和明文提取方式，提高了破解成功率。

1. RSA加密体制概述

RSA是一种基于大整数因式分解困难性的公钥密码体制。其基本流程如下：
选取两个大素数 p,q，计算模数 N=pq。
计算欧拉函数 φ(N)=(p−1)(q−1)。
选择公钥指数 e，满足 gcd(e,φ(N))=1。
计算私钥指数 d，满足 ed≡1(modφ(N))。
公钥为 (e,N)，私钥为 d。
加密过程：
c ≡ m^e mod N
解密过程：
m ≡ c^d mod N
理论上当N达到1024bit以上时难以直接分解。
但如果参数选择不合理，则可能被破解。

2.漏洞分析

根据题目给出的加密说明，可以发现以下潜在漏洞：
(1)多个模数可能共享素因子
如果gcd(N1,N2)>1,则可直接得到素因子。
(2)可能存在低加密指数
如：e=3,容易受到广播攻击。
(3)p−1过于光滑
适用于Pollard p−1攻击。
(4)p和q过于接近
适用于Fermat分解法。
(5)存在重复明文
容易形成共模攻击条件。

3. 实验思路

(1)解析截获的加密帧数据（N, e, c）。
(2)检查模数是否共享因子（gcd(N_i, N_j) > 1）。
(3)根据明文结构分析填充模式，尝试恢复明文。
(4)若可分解N，则计算 φ(N) 并求解私钥 d。
(5)记录已恢复的明文及参数，分析剩余部分无法破解的原因

4.主要实现步骤

本实验针对题目提供的 21 个 RSA 加密分片（Frame0～Frame20）进行分析。首先对所有 Frame 文件进行解析，提取模数 n、加密指数 e 以及密文 c。随后根据不同 Frame 的参数特点，选择相应的攻击方法进行破解。

(1)数据预处理

题目提供的每个 Frame 文件均由三部分组成：
前 256 个十六进制字符：RSA 模数 n
中间 256 个十六进制字符：公钥指数 e
后 256 个十六进制字符：密文 c
程序首先读取所有 Frame 文件，并将其转换为整数形式保存，便于后续数学运算。

(2)GCD攻击

对于 RSA 系统而言，如果两个用户错误地使用了同一个素数作为模数因子，则：
n₁ = p × q₁，n₂ = p × q₂
此时可以通过计算：gcd(n₁,n₂)，直接得到公共素因子 p。
获得 p 后即可计算：q = n / p
进一步求出欧拉函数：φ(n) = (p-1)(q-1)
最后利用d = e⁻¹ mod φ(n)恢复私钥并完成解密。
实验中通过遍历所有模数，计算任意两个模数之间的最大公约数，成功发现了存在公共因子的模数对，从而恢复了对应 Frame 的明文。

(3)共模攻击

如果两个用户使用相同的模数 n，但采用不同的公钥指数 e₁ 和 e₂ 对同一明文进行加密：c₁ = m^(e₁) mod n ， c₂ = m^(e₂) mod n ，且gcd(e₁,e₂)=1，则根据扩展欧几里得算法，可以求得：s₁e₁+s₂e₂=1，从而得到：m = c₁^s₁ × c₂^s₂ mod n，无需分解模数即可直接恢复原始明文。
实验中发现 Frame0 与 Frame4 满足该条件，因此利用共模攻击成功恢复了对应明文。

(4)Broadcast Attack（低指数广播攻击）

当同一条消息被发送给多个用户，并且使用相同的小公钥指数 e，而不同用户使用不同模数时：cᵢ = m^e mod nᵢ
若收集到不少于 e 个不同密文，则可以利用中国剩余定理（CRT）构造：
M = m^e,由于me < n₁n₂…nₑ,因此不发生模约减。随后直接计算m = e次整数根(M),即可恢复原始明文。
实验中：
Frame3、8、12、16、20 对应 e=5
Frame7、11、15 对应 e=3
因此尝试使用广播攻击恢复明文。其中 e=5 组成功恢复部分明文，而 e=3 组由于条件不完全满足，未能成功恢复。

(5)Pollard p-1 分解攻击

Pollard p-1 算法适用于以下情况：
若 RSA 模数因子 p 满足p-1只包含较小素因子，则可利用模幂运算快速求得：gcd(a^M-1,n),从而得到非平凡因子 p,获得 p 后即可分解模数并恢复私钥。
实验中利用 Pollard p-1 算法成功分解了部分 RSA 模数，恢复了 Frame2、Frame6 和 Frame19 对应的明文信息。

(6)Fermat 分解攻击

Fermat 分解利用平方差公式n=a²-b²=(a+b)(a-b),当 RSA 模数的两个素因子 p 和 q 较为接近时p≈q,可以快速找到：a=(p+q)/2 , b=(q-p)/2,从而实现模数分解。
实验中发现 Frame10 对应模数满足该特征，因此采用 Fermat 分解方法成功恢复明文。

(7)明文恢复与结果整理

RSA 解密后得到的数据块包含：
固定标识字段
通信序号
填充数据
真实消息内容
通过分析题目给出的填充格式，发现每个数据块最后 8 字节为有效明文内容。因此程序统一提取解密结果的最后 8 字节作为明文片段，并按照 Frame 编号顺序进行整理和输出，得到最终恢复结果。
最终成功恢复了多个明文分片，为后续完整消息重构提供了基础。

5.总结

通过本次实验，深入理解了RSA加密体制的实现原理以及实际系统中可能存在的安全隐患。
实验表明，即使RSA模数长度达到1024位，如果：
随机数生成器设计不安全；素数选择存在规律；公钥指数设置不合理；重复使用模数；
都会导致RSA被成功破解。
本实验不仅加深了对数论知识的理解，也掌握了多种经典RSA攻击方法，包括：
共模攻击；广播攻击；Pollard p−1攻击；Fermat分解；因数碰撞攻击。
实验进一步说明：密码系统的安全性不仅取决于算法本身，更依赖于参数生成与实现过程的安全设计。