Frame 格式#

每个 Frame 文件是一个 ASCII 十六进制字符串，包含三段连续数据：

1
def parse_frame(filepath):
2
    with open(filepath, 'rb') as f:
3
        data = f.read().decode('ascii')
4
    n = int(data[0:256], 16)    # 模数 N（256 个 hex = 1024 位）
5
    e = int(data[256:512], 16)  # 公钥指数 e
6
    c = int(data[512:768], 16)  # 密文 c
7
    return n, e, c

消息填充结构#

从附件 3-1 的已知参数可以还原出 128 字节的消息填充格式：

1
字节   0-63:   全零
2
字节  64-71:   标记 0x9876543210ABCDEF
3
字节  72-75:   消息序号（4 字节大端，范围 0-15）
4
字节  76-119:  全零
5
字节 120-127:  8 字节消息片段（ASCII 编码）

加密前的填充消息 m 即为这 128 字节的大整数表示。这意味着对于任何帧，只有最后 8 字节（64 位）是真正未知的，其余 120 字节（包括标记和序号位置）是已知的填充结构。这个结构是后续 Coppersmith 攻击的关键前提。

附件 3-1 的信息#

附件 3-1 使用两对密钥加密了测试明文 "This is a test of my RSA system."（32 字节，分割为 4 个 8 字节片段）：

• Frame 0-1：共享一对 1024 位密钥 (p₁, q₁, n₁)，e = 0x10001
• Frame 2-3：共享另一对密钥 (p₂, q₂, n₂)，其中 q₂ 仅 40 位（0xE00258CB6F）

第二个密钥对中 q₂ 仅 40 位本身就暗示了脆弱性的存在——实际应用中素数至少应有 512 位以上，但实验环境中这种”故意留下的弱点”恰好是理解攻击的入口。

原理#

如果两个 RSA 模数 N₁ 和 N₂ 共享一个素数因子 p，那么直接计算最大公约数即可分解两者：

1
p = gcd(N₁, N₂)
2
q₁ = N₁ / p
3
q₂ = N₂ / p

这种情况在现实中出现的原因通常是：多个设备或证书使用了同一个有缺陷的随机数生成器，在生成素数时状态碰撞，导致”不同”的模数实际上共享了因子。

实现#

直接计算所有 21 帧模数之间的 GCD，发现 Frame 1 和 18 的模数共享 512 位公共因子。通过扩展欧几里得算法求模逆得到私钥 d，解密获得：

1
Frame  1: ". Imagin"（序号 11）
2
Frame 18: "m A to B"（序号 10）

两个帧快速被破解。GCD 攻击的一个变体是批处理 GCD：如果有几百个模数，可以用乘积树在 O(n log² n) 时间内找出所有共享因子对。2012 年就有研究者用这种方法在大规模 HTTPS 证书扫描中发现了数万个可分解的证书。

原理#

Pollard p-1 方法在素数 p 满足”p-1 是 B-smooth”（即 p-1 的所有素因子都不超过 B）时有效。核心思想基于费马小定理：

如果 p-1 的所有素因子都 ≤ B，那么 p-1 整除 B!。因此对于任意与 p 互素的整数 a：

$a^{B!} \equiv 1 \pmod{p}$

那么 $p \mid \gcd(a^{B!} - 1, N)$。算法实现从 a=2 开始，迭代计算 $a \leftarrow a^j \bmod n$（j 从 2 到 B），最后取 $\gcd(a-1, n)$。

1
def pollard_pm1(n, B=100000):
2
    a = 2
3
    for j in range(2, B + 1):
4
        a = pow(a, j, n)
5
    g = gcd(a - 1, n)
6
    return g if 1 < g < n else None

实验结果#

逐步增加边界 B 进行搜索：

1
Frame  2: B=50000  时找到 510 位因子 → " That is"（序号 6）
2
Frame 19: B=50000  时找到 40 位因子  → "instein."（序号 5）
3
Frame  6: B=200000 时找到 40 位因子  → "Logic "  （序号 7）

Frame 2 的 510 位因子说明 p-1 虽然数值很大，但其素因子分解全部 ≤ 50000，是一个高度光滑的”弱素数”。Frame 6 和 19 的素因子仅 40 位，直接可分解。安全实现中应该选择 p-1 含有一个大素因子的”强素数”来抵抗此攻击。

原理#

Frame 0 和 Frame 4 使用相同的模数 N，不同的公钥指数 e₀ 和 e₄，加密了相同的消息 m。若 $\gcd(e₀, e₄) = 1$，利用扩展欧几里得算法找到整数 a、b 使得：

$a \cdot e_0 + b \cdot e_4 = 1$

那么：

$c_0^a \cdot c_4^b \equiv m^{a \cdot e_0} \cdot m^{b \cdot e_4} \equiv m^{a \cdot e_0 + b \cdot e_4} \equiv m \pmod{N}$

如果 a 为负数（通常如此），需要计算对应密文在模 N 下的逆元再幂次。

实现与附注#

1
n0 = ZZ(intercepted[0][0])
2
e0, e4 = ZZ(intercepted[0][1]), ZZ(intercepted[4][1])
3
c0, c4 = ZZ(intercepted[0][2]), ZZ(intercepted[4][2])
4

5
_, a, b = xgcd(e0, e4)
6

7
if a < 0:
8
    m = (pow(c0.inverse_mod(n0), int(-a), n0) * pow(c4, int(b), n0)) % n0
9
else:
10
    m = (pow(c0, int(a), n0) * pow(c4.inverse_mod(n0), int(-b), n0)) % n0

一个值得注意的细节是 Frame 4 的 e 值超过了 N。在标准 RSA 中 e 通常远小于 φ(N)，但这里的异常取值并不影响共模攻击的数学关系——扩展欧几里得算法和模逆运算在 e > N 时仍然有效。

1
Frame 0/4: "My secre"（序号 0）

共模攻击的教训很明确：绝不应对不同接收者使用相同的模数。即使加密指数不同，只要同一条消息被加密两次，攻击者就能直接恢复明文。这就是为什么每个 RSA 密钥对必须独立生成。

原理#

这是整个实验中解决帧数最多的攻击方法。当公钥指数 e 很小（如 e = 3 或 5）且消息的大部分比特已知时，Coppersmith 方法可以在多项式时间内恢复未知的低比特位。

本实验中，128 字节的消息中只有最后 8 字节消息文本（64 位）和 4 字节序号是未知的，其余 120 字节是已知的填充结构。由于序号只有 21 种可能（0-20），可以对每种假设分别构造多项式求解。

加密方程为：

$m^e = (\text{known\_high} + x)^e \equiv c \pmod{N}$

定义多项式 $f(x) = (\text{known\_high} + x)^e - c$ 在模 N 下。如果未知量 x 足够小（ < N^{1/e}），Coppersmith 定理保证可以在多项式时间内找到小根。

实现与关键调试#

1
for seq_guess in range(21):
2
    known_high = (INTERCEPT_MARKER << 32) + seq_guess
3
    known_high = known_high << (52 * 8)  # 移到字节 64-75
4

5
    R = PolynomialRing(Zmod(n), 'x')
6
    x = R.gen()
7
    f = (known_high + x)**e - c
8

9
    try:
10
        roots = f.small_roots(X=2**64, beta=1.0, epsilon=0.03)
11
        if roots:
12
            m_candidate = known_high + int(roots[0])
13
            marker, seq, msg = unpack_message(m_candidate)
14
            if marker == INTERCEPT_MARKER:
15
                # 攻击成功
16
                break
17
    except:
18
        pass

构造已知部分时有一个容易出错的关键细节：标记（8 字节）和序号（4 字节）组成 12 字节块，应向左移位 52 × 8 位（即字节 64-75 拼接到 76-127 前面），而不是错误地移 (128-76) × 8 位。如果位偏移计算错误，将导致根搜索空间扩大到 416 位（远超 Coppersmith 可处理范围），从而使攻击失败。

实验结果#

1
e=3 的帧（3 帧，全部独立消息）：
2
  Frame  7: "amous sa"（序号 2）
3
  Frame 11: "ying of "（序号 3）
4
  Frame 15: "Albert E"（序号 4）
5

6
e=5 的帧（5 帧，全部为重复加密）：
7
  Frame  3: "t is a f"（序号 1）
8
  Frame  8: "t is a f"（序号 1，重复）
9
  Frame 12: "t is a f"（序号 1，重复）
10
  Frame 16: "t is a f"（序号 1，重复）
11
  Frame 20: "t is a f"（序号 1，重复）

e=3 的三个帧分别对应不同的消息片段（序号 2-4），而 e=5 的五个帧全部加密了同一个消息片段（序号 1）。这说明 e=5 的帧使用了不同的密钥对来加密同一条消息——实现上没有问题（不同密钥就是不同密钥），但消息内容的大量重复从侧面印证了附加 3-2 数据集的构造特征。

Coppersmith 方法的核心教训是：即使使用安全的模数长度，如果公钥指数太小且消息的高比特位可预测，RSA 依然不安全。这也解释了为什么现实中几乎总是使用 e = 65537——它足够大以抵抗 Coppersmith 攻击，同时作为 $2^{16}+1$（二进制只有两位是 1）模幂运算仍然高效。此外，使用 OAEP 等引入随机性的填充方案可以消除”已知高位”的假设，从根本上阻止此类攻击。

原理#

如果 N = pq 的两个素因子 p 和 q 过于接近，Fermat 分解可以快速找到它们。设 $a = \lceil \sqrt{N} \rceil$，逐渐增加 a，检查 $b^2 = a^2 - N$ 是否为完全平方数。如果是，则：

$N = a^2 - b^2 = (a+b)(a-b) = pq$

1
def fermat_factor(n):
2
    a = math.isqrt(n)
3
    if a * a < n:
4
        a += 1
5
    while True:
6
        b2 = a * a - n
7
        b = math.isqrt(b2)
8
        if b * b == b2:
9
            return a + b, a - b
10
        a += 1

算法的时间复杂度取决于 p 和 q 的差距。当 $|p - q| < N^{1/4}$ 时，Fermat 分解在多项式时间内可完成。这意味着安全地生成 RSA 素数时，p 和 q 不仅需要随机独立选择，位长通常也应略有差异。

实验结果#

Frame 10 的 p 和 q 非常接近，在 1000 次迭代内成功分解：

1
Frame 10: "will get"（序号 8）

原理#

这些帧的 RSA 素因子由一个 16 位种子的线性同余生成器（LCG）生成：

1
X_{n+1} = (365 × X_n - 1) mod 2¹⁶

每个 16 位 PRNG 输出被拼接成一个比特串，当这个比特串表示的整数被证明为素数时，就用作 RSA 的素因子。由于种子空间仅 16 位（1 到 65536），攻击者可以枚举所有可能的种子并重演 PRNG 序列来尝试分解 N。

实现与关键调试#

1
def prng_factor(n, max_bits=520):
2
    for seed in range(1, 65537):
3
        xn_int = seed
4
        xn = format(seed, '016b')
5
        while len(xn) < max_bits:
6
            xn_int = (365 * xn_int - 1) % (1 << 16)
7
            xn += format(xn_int, '016b')
8
            candidate = int(xn, 2)
9
            if candidate < n and n % candidate == 0:
10
                return candidate, seed
11
    return None

这个地方有一个非常重要的调试经历。初始实现错误地从左侧截断比特（即检查序列的后缀），导致 Frame 13 和 17 未能恢复。正确的做法是从右侧截断（检查序列的前缀），因为 PRNG 的首个输出对应的是素数的高位比特。修正后全部 5 帧成功恢复：

1
Frame  5 (seed=41714): "ation wi"（序号 12）
2
Frame  9 (seed=46818): "ll take "（序号 13）
3
Frame 14 (seed=53546): " you fro"（序号 9）
4
Frame 13 (seed=34410): "you ever"（序号 14）
5
Frame 17 (seed=40530): 'ywhere."'（序号 15）

这个 bug 的本质是对位序方向的理解错误。PRNG 序列的第一个 16 位输出拼接在比特串的最左边（最高位），随着序列增长，新的输出追加在右边（低位）。因此应该检查序列的前缀（从左截断），而不是后缀（从右截断）。这是一个非常典型的 “bit ordering” 类错误，值得铭记。

教训#

16 位的种子空间意味着最多 65536 次尝试即可穷举全部可能，在现代计算机上几秒内就能完成。更微妙的是，即使 PRNG 使用了更大的状态空间，如果它从系统时间等低熵源获取种子，攻击者同样可以通过猜测时间窗口来缩小搜索空间。

密码学中，随机数生成器是系统的命门。本实验中至少四条攻击路线（GCD 共享因子、Pollard p-1、Fermat 分解、弱 PRNG）都直接或间接源于密钥生成阶段使用了不可靠的随机性。