这一篇记录现代密码学实验四内容是一个 RSA 加密体制破译题。和实验三里“实现 RSA”不一样这次不是单纯写加密解密流程而是分析题目给出的 21 个 RSA 加密帧利用 RSA 参数使用不当时留下的弱点恢复明文。实验题目及链接RSA 加密体制破译题目链接代码仓库https://github.com/yfe1y1ng46-creator/Crypto-Experiment/tree/main/experiment4参考题解2016 全国高校密码数学挑战赛-赛题三 - Tr0ys Blog题目理解题目给了 21 个被截获的 RSA 通信帧每个帧都是一长串十六进制数据。每个 Frame 的结构是1024 bit N || 1024 bit e || 1024 bit c其中c m^e mod N明文块 m 是 512 bit格式大概是64 bit flag || 32 bit 通信序号 || 一段 0 填充 || 最后 64 bit 明文文本也就是说每个帧真正保存的文本只有最后 8 个 ASCII 字符。Frame0、Frame1 这些文件名只是接收顺序不一定是真正的通信顺序。真正拼接明文时要看明文块里的 sequence。这道题的重点不是硬分解 1024 bit RSA而是找 RSA 使用中的各种漏洞比如相同模数被重复使用不同模数共享素因子小指数广播p-1 比较光滑可以用 Pollard p-1 分解p 和 q 太接近可以用 Fermat 分解小指数加上明文结构已知可以用 Coppersmith 小根攻击代码整体结构我把实验四代码拆成了两个文件experiment4/ ├── common.py ├── solve_rsa_break.py └── requirements.txtcommon.py 里主要放一些通用数学函数比如扩展欧几里得、模逆、中国剩余定理、整数开方、Pollard p-1、Fermat 分解和 Coppersmith 小根函数。solve_rsa_break.py 负责读取 Frame 文件然后依次尝试不同攻击。运行方式cd A:\Gpt_result\Crypto-Experiment python -m pip install -r .\experiment4\requirements.txt python .\experiment4\solve_rsa_break.py1. 数据解析因为每个 Frame 文件里是连续的十六进制字符串所以直接按长度切开def load_frames() - list[dict[str, int]]: frames: list[dict[str, int]] [] for path in sorted(FRAME_DIR.glob(Frame*), keylambda p: int(p.name[5:])): text path.read_text(encodingascii).strip() frames.append( { id: int(path.name[5:]), n: int(text[:256], 16), e: int(text[256:512], 16), c: int(text[512:], 16), } ) return frames解密出 m 之后也不能直接当字符串看而要按题目给的格式解析def parse_plain_block(m: int) - tuple[str, int, bytes, bool]: block_hex f{m:0128x}[-128:] flag block_hex[:16] sequence int(block_hex[16:24], 16) zero_area block_hex[24:-16] chunk bytes.fromhex(block_hex[-16:]) padding_ok set(zero_area) {0} return flag, sequence, chunk, padding_ok这里 0128x 的意思是把明文块补齐到 128 个十六进制字符也就是 512 bit。如果不补齐前面的 flag、sequence、0 填充和最后 8 字节文本的位置就会错。2. 共模攻击Frame0 和 Frame4 使用了相同的模数 N但是指数不同。如果两个指数 e1 和 e2 互素就可以用扩展欧几里得求出a * e1 b * e2 1又因为c1 m^e1 mod N c2 m^e2 mod N所以c1^a * c2^b m^(a e1 b e2) m mod N关键代码def common_modulus_attack(frames, result): groups: dict[int, list[dict[str, int]]] defaultdict(list) for frame in frames: groups[frame[n]].append(frame) for group in groups.values(): if len(group) 2: continue left, right group[0], group[1] g, a, b extended_gcd(left[e], right[e]) if g ! 1: continue n left[n] c1 pow(left[c], a, n) if a 0 else pow(invmod(left[c], n), -a, n) c2 pow(right[c], b, n) if b 0 else pow(invmod(right[c], n), -b, n) m (c1 * c2) % n恢复结果Frame00: seq00 textMy secre Frame04: seq00 textMy secre3. 共享素因子攻击如果两个不同的 RSA 模数共享同一个素因子那么直接对它们求 gcd 就可以分解p gcd(N1, N2) q N / p这道题里 Frame1 和 Frame18 就共享了一个 512 bit 素因子。关键代码def shared_factor_attack(frames, result): for i, left in enumerate(frames): for right in frames[i 1 :]: factor gcd(left[n], right[n]) if 1 factor left[n]: for frame in (left, right): m, d, p, q decrypt_with_factor(frame[n], frame[e], frame[c], factor) add_plaintext(result, frame, m, shared prime factor)分解出 p 和 q 之后就按正常 RSA 解密phi (p - 1) * (q - 1) d e^{-1} mod phi m c^d mod N恢复结果Frame01: seq11 text. Imagin Frame18: seq10 textm A to B4. Hastad 广播攻击Frame3、Frame8、Frame12、Frame16、Frame20 的指数都是 e5并且它们加密的是相同明文。如果同一个明文用小指数 e 加密给至少 e 个互素模数就可以用中国剩余定理合并c_i m^e mod N_i得到M m^e然后直接对 M 开整数 e 次方根就能得到 m。关键代码def broadcast_attack(frames, result): groups: dict[int, list[dict[str, int]]] defaultdict(list) for frame in frames: groups[frame[e]].append(frame) for e, group in groups.items(): if e 1 or len(group) e: continue residues [(frame[c], frame[n]) for frame in group[:e]] combined, _ crt(residues) m, exact integer_nth_root(combined, e) if not exact: continue恢复结果Frame03: seq01 textt is a f Frame08: seq01 textt is a f Frame12: seq01 textt is a f Frame16: seq01 textt is a f Frame20: seq01 textt is a f5. Pollard p-1 分解Pollard p-1 适用于某个素因子 p 的 p-1 比较光滑的情况。简单理解就是如果 p-1 可以被很多小素数整除那么可以构造一个比较大的指数 M让a^M 1 mod p然后gcd(a^M - 1, N)就有机会得到 p。关键代码def pollard_p_minus_1(n: int, bound: int 200_000) - int | None: a 2 for prime in first_primes(bound): power prime while power * prime bound: power * prime a pow(a, power, n) factor gcd(a - 1, n) if 1 factor n: return factor return None本题中可以恢复Frame02: seq06 text That is Frame06: seq07 text Logic Frame19: seq05 textinstein.6. Coppersmith 小根攻击这一部分是这道题里最有意思的地方。Frame7、Frame11、Frame15 的指数是 e3。正常来说单个 e3 密文也不能直接开三次方因为这里 m^3 已经超过了 N做了取模。但是题目明文格式是固定的flag || sequence || 0 padding || 最后 8 字节文本也就是说除了最后 8 字节文本以外其他大部分内容都可以确定。于是可以把明文写成m prefix x其中 x 2^64。然后构造多项式(prefix x)^3 - c ≡ 0 mod N这就变成了一个小根问题。代码里用 sympy 的 LLL 来做一个小维度格约化找到这个小的 x。关键代码def coppersmith_attack(frames, result): flags [int(str(item[flag]), 16) for item in result.values() if item.get(flag)] flag flags[0] if flags else int(9876543210abcdef, 16) for frame in frames: if frame[id] in result or frame[e] ! 3: continue for sequence in range(len(frames)): prefix (flag (32 352 64)) | (sequence (352 64)) roots coppersmith_e3_known_prefix(prefix, frame[n], frame[c]) if not roots: continue m prefix roots[0] add_plaintext(result, frame, m, Coppersmith e3 small-root) break恢复结果Frame07: seq02 textamous sa Frame11: seq03 textying of Frame15: seq04 textAlbert E7. Fermat 近素数分解如果 RSA 生成素数时 p 和 q 太接近就可以用 Fermat 分解。原理是N p * q如果 p 和 q 接近就可以写成N a^2 - b^2 (a - b)(a b)从 ceil(sqrt(N)) 开始尝试只要找到a^2 - N b^2就能得到p a - b q a b关键代码def fermat_factor_at_offset(n: int, offset: int) - tuple[int, int] | None: a gmpy2.isqrt(n) if a * a n: a 1 a offset b2 a * a - n if gmpy2.is_square(b2): b gmpy2.isqrt(b2) return int(a - b), int(a b) return None这道题里 Frame10 很快就能分解Frame14 的搜索偏移更大。程序里记录了已经测出的偏移用来避免每次复现实验都重复跑很久。恢复结果Frame10: seq08 textwill get Frame14: seq09 text you fro最终运行结果程序运行输出如下frames_total: 21 frames_recovered: 17 Recovered plaintext by communication sequence: 00: My secre 01: t is a f 02: amous sa 03: ying of 04: Albert E 05: instein. 06: That is 07: Logic 08: will get 09: you fro 10: m A to B 11: . Imagin joined: My secret is a famous saying of Albert Einstein. That is Logic will get you from A to B. Imagin Final passphrase inferred from recovered chunks: My secret is a famous saying of Albert Einstein. That is Logic will get you from A to B. Imagination will take you everywhere. unrecovered_frames: [5, 9, 13, 17] runtime_seconds: 1.464这里程序直接恢复了 17 个帧剩下的 Frame5、Frame9、Frame13、Frame17 没有被当前实现的这些攻击直接恢复。但是已经恢复出来的序号 00 到 11 是连续的拼起来是My secret is a famous saying of Albert Einstein. That is Logic will get you from A to B. Imagin结合前后语义和爱因斯坦名言可以推出完整密语My secret is a famous saying of Albert Einstein. That is Logic will get you from A to B. Imagination will take you everywhere.总结这次实验和实验三的 RSA 实现联系很强。实验三主要是理解c m^e mod n m c^d mod n而实验四则是从攻击角度看如果 RSA 参数没有正确生成和使用会出现哪些问题。我觉得这道题最能说明的是RSA 本身不是“只要位数够长就一定安全”。比如同一个 N 不能被不同用户或不同指数重复使用生成素数时随机数不能出问题否则可能共享素因子小指数不能随便用尤其不能直接加密有结构的明文p 和 q 不能太接近真实场景不能裸 RSA 加密必须使用安全 padding比如 OAEP实现过程中比较容易踩坑的是明文解析。因为明文块里前面有 flag、sequence 和 0 填充最后 8 字节才是真正文本所以必须把整数补齐到 512 bit 再解析。否则很容易出现“明文只解出来一部分”或者序号错位的问题。另一个比较有收获的是 Coppersmith 小根攻击。它不是暴力枚举最后 8 字节而是利用“未知量很小”这个条件把问题转成多项式小根问题。这一点比单纯 gcd 或 Fermat 分解更能体现 RSA 数学攻击的味道。最后实验结果虽然没有直接恢复全部 21 个帧但已经恢复出足够连续的通信片段可以确定最终密语。剩余 4 个帧如果继续深入可以再分析题目中随机数生成器或者更多隐藏弱点。