LOADING

加载过慢请开启缓存 浏览器默认开启

RSA 常见漏洞与真实 Frame 破译案例

Cryptography CTF 密码学 RSA 阅读量 0

RSA 常见漏洞与真实 Frame 破译案例

这篇文章记录一次 RSA 破译实验。数据来自“RSA 加密体制破译题目”的真实附件，不使用自造小数据。

题目背景大致是：Alice 使用一个 RSA 加解密软件发送通关密语，所有加密帧已经被截获。我们要尽量从截获数据恢复明文和 RSA 参数。如果不能完全恢复，也要说明哪些部分已经恢复，哪些部分不能靠当前数据验证。

题目规定每个 Frame 文件结构如下：

1024-bit N | 1024-bit e | 1024-bit ciphertext

也就是说，每个文件都是一个 3072-bit 的十六进制字符串，里面依次包含：

RSA 模数 N
公钥指数 e
密文 c = m^e mod N

1. 先理解题目中的填充格式

题目还规定每次最多加密 8 个明文字符。明文分片会填充成 512 bit 后再加密。

填充结构是：

64-bit 标志位 | 32-bit 通信序号 | 若干个 0 | 最后 64-bit 明文分片 ASCII

因此恢复出整数 m 后，不能直接把整块都当作字符串，而要解析：

def decode_padded_message(message: int) -> dict[str, str | int]:
    block = message.to_bytes(64, "big")
    return {
        "marker_hex": block[:8].hex(),
        "sequence": int.from_bytes(block[8:12], "big"),
        "chunk_hex": block[-8:].hex(),
        "chunk": block[-8:].decode("latin1"),
        "full_block_hex": block.hex(),
    }

其中最重要的是：

sequence  通信序号
chunk     最后 8 字符明文分片

Frame 文件名中的编号是接收序号，不一定等于通信序号，所以拼接明文时要看填充里解析出的 sequence。

2. 解析 Frame 文件

每个 Frame 是 768 个十六进制字符：

256 hex chars for N
256 hex chars for e
256 hex chars for c

解析代码如下：

from dataclasses import dataclass
from pathlib import Path


@dataclass(frozen=True)
class Frame:
    name: str
    n: int
    e: int
    c: int


def load_frames(directory: Path) -> list[Frame]:
    frames = []
    for path in sorted(directory.glob("Frame*"), key=lambda p: int(p.name.replace("Frame", ""))):
        text = path.read_text(encoding="ascii").strip()
        if len(text) != 768:
            raise ValueError(f"{path} is not a 3072-bit hexadecimal frame")
        frames.append(Frame(path.name, int(text[:256], 16), int(text[256:512], 16), int(text[512:], 16)))
    return frames

运行：

python work\experiment_04_rsa_challenge\01_parse_frame_files.py

真实 VSCode 截图：

Frame 解析运行截图

结果显示：

Frame count: 21
Unique modulus count: 20

21 个帧只有 20 个唯一模数，说明至少存在一次模数复用。

3. 检查危险关系

RSA 不是看到 1024 bit 就直接去分解。正常 1024 bit RSA 很难直接分解。应该先检查参数之间有没有明显弱关系。

本实验检查三类关系：

相同模数 N
不同模数是否共享素因子
小指数 e 是否有重复组

代码：

def analyze_frame_relations(frames: list[Frame]) -> list[str]:
    lines = []
    for left, right in combinations(frames, 2):
        factor = math.gcd(left.n, right.n)
        if 1 < factor < left.n:
            lines.append(f"shared factor: {left.name} / {right.name}, factor_bits={factor.bit_length()}")
        if left.n == right.n:
            lines.append(
                f"same modulus: {left.name} / {right.name}, gcd(e1,e2)={math.gcd(left.e, right.e)}"
            )

    by_e: dict[int, list[str]] = {}
    for frame in frames:
        by_e.setdefault(frame.e, []).append(frame.name)

    for e, names in sorted(by_e.items(), key=lambda item: (item[0].bit_length(), item[0])):
        label = str(e) if e.bit_length() < 32 else f"{e.bit_length()}-bit exponent"
        lines.append(f"same exponent group: e={label}, count={len(names)}, frames={','.join(names)}")
    return lines

运行：

python work\experiment_04_rsa_challenge\02_analyze_vulnerable_relations.py

截图：

RSA 参数关系分析截图

关键发现：

same modulus: Frame0 / Frame4, gcd(e1,e2)=1
shared factor: Frame1 / Frame18, factor_bits=512
same exponent group: e=5, count=5, frames=Frame3,Frame8,Frame12,Frame16,Frame20
same exponent group: e=3, count=3, frames=Frame7,Frame11,Frame15
same exponent group: e=65537, count=11

这些关系对应三类攻击：

共模攻击
共享素因子分解
Håstad 广播攻击

4. 共模攻击

适用条件：

同一个 N
同一个明文 m
两个指数 e1, e2 互素

假设：

c1 = m^e1 mod N
c2 = m^e2 mod N
gcd(e1, e2) = 1

由扩展欧几里得可得：

a * e1 + b * e2 = 1

所以：

c1^a * c2^b = m^(a e1 + b e2) = m mod N

代码中要注意负指数，负指数需要先求模逆：

_, a, b = egcd(left.e, right.e)
left_part = pow(left.c, a, left.n) if a >= 0 else pow(invmod(left.c, left.n), -a, left.n)
right_part = pow(right.c, b, right.n) if b >= 0 else pow(invmod(right.c, right.n), -b, right.n)
decoded = decode_padded_message((left_part * right_part) % left.n)

本题中 Frame0 和 Frame4 满足条件，恢复：

seq=0
chunk='My secre'

5. 共享素因子攻击

适用条件：

两个不同模数 N1、N2 共享素因子

如果：

N1 = p * q1
N2 = p * q2

那么：

gcd(N1, N2) = p

拿到 p 后，任一相关模数都能被分解：

q = N / p
phi = (p - 1) * (q - 1)
d = e^(-1) mod phi
m = c^d mod N

代码：

factor = math.gcd(left.n, right.n)
if 1 < factor < left.n:
    for frame in (left, right):
        p = factor
        q = frame.n // factor
        phi = (p - 1) * (q - 1)
        d = invmod(frame.e, phi)
        decoded = decode_padded_message(pow(frame.c, d, frame.n))

本题中 Frame1 和 Frame18 共享 512-bit 因子，恢复：

Frame18: seq=10, chunk='m A to B'
Frame1 : seq=11, chunk='. Imagin'

6. Håstad 广播攻击

适用条件：

同一明文 m
相同小指数 e
至少 e 个不同且两两互素的模数
没有随机填充破坏同明文关系

如果收集到：

c_i = m^e mod N_i

并且 N_i 两两互素，就能用 CRT 合并：

C = m^e mod product(N_i)

当 m^e < product(N_i) 时，合并结果就是普通整数意义下的 m^e，对它开 e 次方即可恢复 m。

代码核心：

combined, _ = crt([(frame.c, frame.n) for frame in group])
root, exact = int_nth_root(combined, e)
if exact:
    decoded = decode_padded_message(root)

本题中 e=5 的 5 个 Frame：

Frame3, Frame8, Frame12, Frame16, Frame20

恢复：

seq=1
chunk='t is a f'

注意：题目里也有 e=3 组，但不能看到 e=3 就直接认定成功。代码必须检查模数两两互素、CRT 后是否能精确开方，以及解出的填充是否合理。

7. 攻击脚本真实运行结果

运行：

python work\experiment_04_rsa_challenge\03_run_rsa_attacks.py

真实 VSCode 截图：

RSA 攻击运行截图

恢复条目如下：

Frame0:  seq=0,  chunk='My secre', attack=common modulus (Frame0, Frame4)
Frame4:  seq=0,  chunk='My secre', attack=common modulus (Frame0, Frame4)
Frame12: seq=1,  chunk='t is a f', attack=Hastad broadcast e=5
Frame16: seq=1,  chunk='t is a f', attack=Hastad broadcast e=5
Frame20: seq=1,  chunk='t is a f', attack=Hastad broadcast e=5
Frame3:  seq=1,  chunk='t is a f', attack=Hastad broadcast e=5
Frame8:  seq=1,  chunk='t is a f', attack=Hastad broadcast e=5
Frame18: seq=10, chunk='m A to B', attack=shared-prime factorization
Frame1:  seq=11, chunk='. Imagin', attack=shared-prime factorization

按通信序号去重拼接，得到已验证片段：

My secret is a fm A to B. Imagin

这里必须强调：没有恢复出的 Frame 不应该靠语感补全。报告和博客都只写数学关系能证明恢复的部分。

8. 单元测试截图

实验还用附件 3-1 的加密案例做了解析校验，并确认附件 3-2 至少恢复非空片段。

RSA 单元测试截图

9. 常见问题

9.1 直接尝试分解 1024-bit N

正常 1024-bit RSA 模数不是本实验里优先走的方向。先找共模、共享因子、小指数重复这些参数关系，效率更高，也更符合题目设置。

9.2 共模攻击忘记负指数

Bézout 系数可能是负数。负指数不能直接普通幂运算，要先求密文关于 N 的模逆。

9.3 广播攻击只看 e 的数量

有 e 个相同指数密文还不够，还要确认模数两两互素、明文相同、CRT 合并后能精确开方。

9.4 把 Frame 文件名当通信序号

题目明确说 FrameXX 是接收序号，不一定等于通信序号。通信序号在解出的填充块里。

9.5 把重复分片当作新内容

题目说明 Alice 初次使用软件，可能重复发送某一明文分片。因此同一个 chunk 出现在多个 Frame 中时，要按通信序号去重。

10. 小结

这次 RSA 破译流程可以概括为：

解析 Frame
按题目格式切出 N/e/c
检查相同 N
两两 gcd 查共享素因子
按 e 分组尝试小指数广播
解出 512-bit 填充块
提取通信序号和 8 字符 chunk
只报告可验证片段

RSA 的危险往往不在公式本身，而在参数、随机性和填充使用错误。只要出现共模、共享素因子、小指数同明文重复发送，就会从“1024 bit 很难分解”变成“几行数论代码即可恢复部分明文”。

参考资料

  • 首届全国高校密码数学挑战赛赛题三：RSA 加密体制破译
  • Dan Boneh, Twenty Years of Attacks on the RSA Cryptosystem
  • Don Coppersmith, Finding a Small Root of a Univariate Modular Equation
  • Cryptopals Set 5 Challenge 39: https://www.cryptopals.com/sets/5/challenges/39