春秋杯与 Trinity Masquerade 题解

发表于 分类于 阅读次数：

春秋杯与 Trinity Masquerade 题解

本文整理春秋杯 hello_lcg 和一道 Trinity Masquerade 题目。两道题都需要从公开的中间结果反推隐藏状态。

题目索引

春秋杯 hello_lcg

题目概述

题目使用一个 LCG 变种生成 AES 密钥。状态由 (x, y) 组成：

1
2
x' = 5y + 7  (mod p)
y' = 11x + 13 (mod p)

每 10 步输出一次：

1
(x * y)^2 mod p

共有 11 个输出。设第 i 个输出为 ots[i]，则：

每个输出有两个可能的乘积值，总共需要枚举 2^11 种符号组合。

矩阵化状态转移

令：

1
2
3
v = [x, y]^T
M = [[0, 5], [11, 0]]
c = [7, 13]^T

则：

每 10 步可以写成：

其中 A = M^10，b = (I + M + ... + M^9)c。继续展开后，v_{10i} 可以表示成初始状态 (x, y) 的线性函数，代入乘积约束后得到二元二次方程组。

Sage 解题框架

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
from itertools import product

import hashlib
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad
from sage.all import GF, Matrix, PolynomialRing, vector


def solve(prime, outputs, ciphertext_hex):
    field = GF(prime)
    roots = []
    for output in outputs:
        value = field(output)
        roots.append([value.sqrt(), -value.sqrt()] if value else [field(0)])

    matrix = Matrix(field, [[0, 5], [11, 0]])
    offset = vector(field, [7, 13])
    identity = Matrix.identity(field, 2)
    step_matrix = matrix ** 10
    step_offset = sum(matrix ** i for i in range(10)) * offset

    coefficients = []
    transform = identity
    translation = vector(field, [0, 0])
    for _ in outputs:
        coefficients.append((
            transform[0, 0], transform[0, 1],
            transform[1, 0], transform[1, 1],
            translation[0], translation[1],
        ))
        translation = translation + transform * step_offset
        transform = transform * step_matrix

    ring = PolynomialRing(field, names=("x", "y"))
    x, y = ring.gens()

    for signs in product(*roots):
        equations = []
        for index in range(2):
            a, b, c, d, e, f = coefficients[index]
            equations.append(
                (a * x + b * y + e) * (c * x + d * y + f)
                - signs[index]
            )

        basis = ring.ideal(equations).groebner_basis()
        # 从 Groebner 基中提取一元多项式并枚举根，
        # 再用其余 11 个输出验证候选状态。
        for polynomial in basis:
            if len(polynomial.variables()) != 1:
                continue
            for root, _ in polynomial.univariate_polynomial().roots():
                candidate_x, candidate_y = recover_other_variable(
                    basis, polynomial, root
                )
                if verify(candidate_x, candidate_y, coefficients, signs):
                    key = hashlib.sha256(
                        f"{candidate_x}{candidate_y}".encode()
                    ).digest()[:16]
                    plaintext = AES.new(
                        key, AES.MODE_ECB
                    ).decrypt(bytes.fromhex(ciphertext_hex))
                    return unpad(plaintext, 16).decode()

    return None

题目材料没有提供完整的 p、输出数组和密文，因此这里保留求解框架，不虚构最终输出。

Trinity Masquerade

题目分析

题目使用三个素数：

并给出 N、H、e 和密文 c。

观察 H 与 N/H 的关系，可以发现：

1
H - N / H ≈ 1

这说明 r 接近 N // H - 1。从这个候选值开始逐步搜索能整除 N 的数，即可恢复 r。

解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from Crypto.Util.number import inverse, long_to_bytes


t = N // H - 1
while N % t:
    t += 2

r = t
assert N % r == 0
assert N // r == H - r

# M = p*q，且 r 是一个已知因子。
exponent = inverse(e, r - 1)
message = pow(c, exponent, r)
print(long_to_bytes(message))

原始材料未附上运行输出，因此最终 flag 仍待补充。