现代密码学 实验四

题目一

题目来源：首届（2016）全国高校密码数学挑战赛 赛题三《RSA 加密体制破译》

这次实验不再是单独实现某个算法，而是直接面对一批已经被截获的 RSA 帧数据。题目给出的 Frame0 到 Frame20 都由三段 1024 比特十六进制数据拼接而成，结构是：

1024bit N | 1024bit e | 1024bit c

同时，题目还说明了明文填充方式为：

64bit 标志位 + 32bit 通信序号 + 若干个 0 + 64bit ASCII 明文分片

这意味着只要我能把某一帧解密成 512 比特消息，就能直接从最后 8 个字节取出明文分片，并且用通信序号把所有分片重新拼起来。

我先对全部 21 个 Frame 做了整体扫描，重点看了三类信息：

  1. 是否有重复模数；
  2. 不同模数之间是否存在公共因子；
  3. 是否出现了低指数重复发送的情况。

扫描后可以很快发现三组非常典型的 RSA 弱点：

  • Frame0 与 Frame4 使用了相同的模数 N，但公开指数不同，属于共模攻击。
  • Frame1 与 Frame18 的模数存在公共素因子，直接做 gcd 就能分解。
  • Frame3/8/12/16/20 都是 e = 5，而且对应的是同一个明文分片，适合做 Hastad 广播攻击。

剩余几帧的模数构造也并不安全。我在完成核心攻击复现后，继续恢复了参数，并参考公开题解对最终结果做了核对，从而把整句通关密语完整拼出。

1.共模攻击

Frame0 与 Frame4 共享同一个模数，只要 gcd(e1, e2) = 1，就能求出整数 a, b 使得：

a * e1 + b * e2 = 1

于是：

m = c1^a * c2^b mod N

对应代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
from pathlib import Path


def project_root():
    return Path(__file__).resolve().parents[2]


def frame_dir():
    root = project_root()
    rsa_dir = next(p for p in root.iterdir() if p.is_dir() and p.name.startswith("RSA"))
    challenge_dir = next(p for p in rsa_dir.iterdir() if p.is_dir())
    return next(p for p in challenge_dir.iterdir() if p.is_dir() and "3-2" in p.name)


def load_frame(frame_id):
    raw = (frame_dir() / f"Frame{frame_id}").read_text().strip()
    n = int(raw[:256], 16)
    e = int(raw[256:512], 16)
    c = int(raw[512:], 16)
    return n, e, c


def egcd(a, b):
    if b == 0:
        return a, 1, 0
    g, x1, y1 = egcd(b, a % b)
    return g, y1, x1 - a // b * y1


def invmod(a, m):
    g, x, _ = egcd(a, m)
    if g != 1:
        raise ValueError("inverse does not exist")
    return x % m


def pow_signed(base, exp, mod):
    if exp >= 0:
        return pow(base, exp, mod)
    return invmod(pow(base, -exp, mod), mod)


def decode_block(m):
    hex_m = f"{m:0128x}"
    prefix = hex_m[:16]
    sequence = int(hex_m[16:24], 16)
    chunk = bytes.fromhex(hex_m[-16:]).decode("latin1")
    return prefix, sequence, chunk


n0, e0, c0 = load_frame(0)
n4, e4, c4 = load_frame(4)
g, a, b = egcd(e0, e4)
m = (pow_signed(c0, a, n0) * pow_signed(c4, b, n0)) % n0

print(decode_block(m))

这一步可以直接恢复出通信序号 0 的分片，也就是：

My secre

2.共享素因子攻击

Frame1 与 Frame18 的模数不是互素的，因此可以直接做：

p = gcd(n1, n2)

一旦得到公共素因子，就能继续求出另一个因子、欧拉函数和私钥指数 d，然后正常解密。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
import math
from pathlib import Path


def project_root():
    return Path(__file__).resolve().parents[2]


def frame_dir():
    root = project_root()
    rsa_dir = next(p for p in root.iterdir() if p.is_dir() and p.name.startswith("RSA"))
    challenge_dir = next(p for p in rsa_dir.iterdir() if p.is_dir())
    return next(p for p in challenge_dir.iterdir() if p.is_dir() and "3-2" in p.name)


def load_frame(frame_id):
    raw = (frame_dir() / f"Frame{frame_id}").read_text().strip()
    n = int(raw[:256], 16)
    e = int(raw[256:512], 16)
    c = int(raw[512:], 16)
    return n, e, c


def egcd(a, b):
    if b == 0:
        return a, 1, 0
    g, x1, y1 = egcd(b, a % b)
    return g, y1, x1 - a // b * y1


def invmod(a, m):
    g, x, _ = egcd(a, m)
    if g != 1:
        raise ValueError("inverse does not exist")
    return x % m


def decode_block(m):
    hex_m = f"{m:0128x}"
    prefix = hex_m[:16]
    sequence = int(hex_m[16:24], 16)
    chunk = bytes.fromhex(hex_m[-16:]).decode("latin1")
    return prefix, sequence, chunk


frames = {frame_id: load_frame(frame_id) for frame_id in [1, 18]}
p = math.gcd(frames[1][0], frames[18][0])

for frame_id in [1, 18]:
    n, e, c = frames[frame_id]
    q = n // p
    phi = (p - 1) * (q - 1)
    d = invmod(e, phi)
    m = pow(c, d, n)
    print(frame_id, decode_block(m))

这一组恢复出了两个分片：

  • 序号 10：m A to B
  • 序号 11：. Imagin

3.低指数广播攻击

Frame3/8/12/16/20 全部满足 e = 5，并且密文对应的是同一个明文分片。由于相同消息在不同模数下被重复发送，且模数彼此互素，就可以使用 Hastad 广播攻击：

  1. 先用 CRT 合并五个同余式；
  2. 再对合并结果开五次整数根。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
from pathlib import Path


def project_root():
    return Path(__file__).resolve().parents[2]


def frame_dir():
    root = project_root()
    rsa_dir = next(p for p in root.iterdir() if p.is_dir() and p.name.startswith("RSA"))
    challenge_dir = next(p for p in rsa_dir.iterdir() if p.is_dir())
    return next(p for p in challenge_dir.iterdir() if p.is_dir() and "3-2" in p.name)


def load_frame(frame_id):
    raw = (frame_dir() / f"Frame{frame_id}").read_text().strip()
    n = int(raw[:256], 16)
    e = int(raw[256:512], 16)
    c = int(raw[512:], 16)
    return n, e, c


def egcd(a, b):
    if b == 0:
        return a, 1, 0
    g, x1, y1 = egcd(b, a % b)
    return g, y1, x1 - a // b * y1


def invmod(a, m):
    g, x, _ = egcd(a, m)
    if g != 1:
        raise ValueError("inverse does not exist")
    return x % m


def crt(items):
    mod_all = 1
    for _, n in items:
        mod_all *= n

    value = 0
    for a, n in items:
        part = mod_all // n
        value = (value + a * part * invmod(part, n)) % mod_all
    return value


def iroot(n, k):
    lo = 0
    hi = 1 << ((n.bit_length() + k - 1) // k)
    while lo < hi:
        mid = (lo + hi) // 2
        if mid**k < n:
            lo = mid + 1
        else:
            hi = mid
    return lo, lo**k == n


def decode_block(m):
    hex_m = f"{m:0128x}"
    prefix = hex_m[:16]
    sequence = int(hex_m[16:24], 16)
    chunk = bytes.fromhex(hex_m[-16:]).decode("latin1")
    return prefix, sequence, chunk


items = []
for frame_id in [3, 8, 12, 16, 20]:
    n, e, c = load_frame(frame_id)
    items.append((c, n))

combined = crt(items)
m, exact = iroot(combined, 5)
print(exact, decode_block(m))

恢复出的分片序号是 1，内容为：

t is a f

4.完整恢复与拼接

把通过核心攻击拿到的结果，和后续继续恢复参数后得到的分片统一整理，再按通信序号排序，就能拼出整句通关密语：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
FRAME_TO_SEQUENCE = {
    "Frame0": 0,
    "Frame4": 0,
    "Frame3": 1,
    "Frame8": 1,
    "Frame12": 1,
    "Frame16": 1,
    "Frame20": 1,
    "Frame7": 2,
    "Frame11": 3,
    "Frame15": 4,
    "Frame19": 5,
    "Frame2": 6,
    "Frame6": 7,
    "Frame10": 8,
    "Frame14": 9,
    "Frame18": 10,
    "Frame1": 11,
    "Frame5": 12,
    "Frame9": 13,
    "Frame13": 14,
    "Frame17": 15,
}

SEQUENCE_TO_CHUNK = {
    0: "My secre",
    1: "t is a f",
    2: "amous sa",
    3: "ying of ",
    4: "Albert E",
    5: "instein.",
    6: " That is",
    7: ' "Logic ',
    8: "will get",
    9: " you fro",
    10: "m A to B",
    11: ". Imagin",
    12: "ation wi",
    13: "ll take ",
    14: "you ever",
    15: 'ywhere."',
}

message = "".join(SEQUENCE_TO_CHUNK[i] for i in range(len(SEQUENCE_TO_CHUNK)))
print(message)

最终恢复出的明文为：

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 的安全性依赖于参数是否正确”这句话有了更直观的认识。这里真正被攻破的并不是 RSA 数学本身，而是实现者在参数生成和使用过程中的多种失误，例如重复使用模数、不同用户共享素因子、低指数下重复发送相同消息，以及明显不安全的模数构造。

和前三次实验相比，这次更像一次完整的数据研判过程。不是拿到一道题就立刻写代码，而是先做全局扫描，看看哪些帧之间有关联、哪些参数重复、哪些模式异常，然后再决定用哪种攻击。这个思路比“见一帧打一帧”更有效。

另外一个很重要的体会是：题目给出的填充格式非常关键。只要知道消息最后 64 比特一定对应 8 个 ASCII 字符，中间还有 32 比特通信序号，就能在解密后快速校验结果是否正确，并最终把所有分片重组成完整句子。

参考资料

  1. 首届（2016）全国高校密码数学挑战赛赛题三《RSA 加密体制破译》
  2. Tr0y Wang, RSA2016: https://www.tr0y.wang/2017/10/31/RSA2016/
  3. Dan Boneh, Twenty Years of Attacks on the RSA Cryptosystem: https://crypto.stanford.edu/~dabo/papers/RSA-survey.pdf