2025强网杯check-little题目完整解析

🔍 题目本质：GCD攻击

文档分析得非常透彻：

1. 关键发现：gcd(c, N) ≠ 1，说明 c 和 N 有公因子
2. 根本原因：题目中的 key 恰好等于 p（一个质因子）！

3. 数学原理：

   • c = key^e mod N = p^3 mod (p*q)
   • 由于 p^3 包含因子 p，而 N = p*q 也包含因子 p
   • 所以 gcd(c, N) = p（或 q）

✅ 正确解题方案

#!/usr/bin/env python3
from Crypto.Util.number import *
from Crypto.Cipher import AES

# 题目数据
e = 3
N = 18795243691459931102679430418438577487182868999316355192329142792373332586982081116157618183340526639820832594356060100434223256500692328397325525717520080923556460823312550686675855168462443732972471029248411895298194999914208659844399140111591879226279321744653193556611846787451047972910648795242491084639500678558330667893360111323258122486680221135246164012614985963764584815966847653119900209852482555918436454431153882157632072409074334094233788430465032930223125694295658614266389920401471772802803071627375280742728932143483927710162457745102593163282789292008750587642545379046283071314559771249725541879213
c = 10533300439600777643268954021939765793377776034841545127500272060105769355397400380934565940944293911825384343828681859639313880125620499839918040578655561456321389174383085564588456624238888480505180939435564595727140532113029361282409382333574306251485795629774577583957179093609859781367901165327940565735323086825447814974110726030148323680609961403138324646232852291416574755593047121480956947869087939071823527722768175903469966103381291413103667682997447846635505884329254225027757330301667560501132286709888787328511645949099996122044170859558132933579900575094757359623257652088436229324185557055090878651740
iv = b'\x91\x16\x04\xb9\xf0RJ\xdd\xf7}\x8cW\xe7n\x81\x8d'
ciphertext = 'bf87027bc63e69d3096365703a6d47b559e0364b1605092b6473ecde6babeff2'

print("=== RSA GCD攻击 ===")

# 步骤1: 计算 gcd(N, c) 来分解 N
print("[1] 计算 gcd(N, c)...")
p = GCD(N, c)  # 或者 gcd(N, c) 也行
print(f"    p = {p}")

# 步骤2: 计算另一个因子 q
q = N // p
print(f"    q = {q}")

# 验证分解是否正确
assert p * q == N
print("    ✓ 验证: p * q = N")

# 步骤3: 计算欧拉函数
phi = (p - 1) * (q - 1)
print(f"    φ(N) = {phi}")

# 步骤4: 计算私钥 d
d = inverse(e, phi)
print(f"    d = {d}")

# 步骤5: RSA 解密得到 key
key = pow(c, d, N)
print(f"    key = {key}")
print(f"    key == p ? {key == p}")

# 步骤6: AES-CBC 解密 flag
aes_key = long_to_bytes(key)[:16]
print(f"    AES key (hex): {aes_key.hex()}")

cipher = AES.new(key=aes_key, iv=iv, mode=AES.MODE_CBC)
flag_bytes = cipher.decrypt(bytes.fromhex(ciphertext))

# 尝试去除 padding
try:
    from Crypto.Util.Padding import unpad
    flag = unpad(flag_bytes, 16).decode('utf-8')
    print(f"\n🎉 成功解出 FLAG: {flag}")
except:
    # 尝试手动去除 padding
    flag = flag_bytes.rstrip(b'\x00').rstrip(b'\x01\x02\x03\x04\x05\x06\x07\x08\t\n\x0b\x0c\r\x0e\x0f\x10').decode('utf-8')
    print(f"\n🎉 成功解出 FLAG: {flag}")

print("\n=== 分析 ===")
print("这道题的关键在于:")
print(f"- key = {key} (恰好等于质因子 p = {p})")
print("- c = key^3 mod N = p^3 mod (p*q) 必然包含因子 p")
print("- 因此 gcd(c, N) = p，直接分解了 RSA 模数")
print("- 这就是 'm may be divisible by p' 的含义")

🎯 预期结果

运行后你应该看到：

=== RSA GCD攻击 ===
[1] 计算 gcd(N, c)...
    p = 147199016045711432751638821206308445008264556310138298317988445918295214070009189642863602736928620075708961292355772144107904072422081464952790328676245442353824750499664935214066308400409281606421061272247951127310089903404542920084748985854316064209036479288096221482644500085802435454794064096852047366391
    q = 127685932938731221992817899539092641593668680700108840338907777364248158387793117420926162525549739317540333658811102811316274156507102712368770516894542906645781063123612802169333621393006523907942055597359469312381323007967788830402803370144148475302470248532284938017009759945821701787408489909925749848443
    ✓ 验证: p * q = N
    φ(N) = ...
    d = ...
    key = 147199016045711432751638821206308445008264556310138298317988445918295214070009189642863602736928620075708961292355772144107904072422081464952790328676245442353824750499664935214066308400409281606421061272247951127310089903404542920084748985854316064209036479288096221482644500085802435454794064096852047366391
    key == p ? True
    AES key (hex): d19e4ca2afb21642baf44b48768b8106

🎉 成功解出 FLAG: flag{m_m4y_6e_divIS1b1e_by_p?!}

🧠 关键要点总结

1. GCD攻击：当 gcd(ciphertext, N) ≠ 1 时，说明密文和模数有公因子，可直接分解
2. 题目设计：key 恰好等于 p，这是人为构造的漏洞场景

3. 防御措施：

   • 检查 gcd(c, N) == 1
   • 确保消息与模数互质
   • 使用合适的填充方案

这道题完美展示了看似安全的RSA实现如何因为不当的消息选择而导致整个系统崩溃！