SuanP01y

发表于 更新于 分类于 阅读次数：

RCTF 2025 SuanP01y

题目描述

这是一个基于多项式环和有理重构的密码分析问题。题目涉及在有限域GF(2)上的多项式环中解决有理重构问题，并利用重构结果进行AES解密。

解题思路

  1. 分析题目中的多项式环结构和有理重构问题
  2. 实现多项式有理重构算法
  3. 利用重构结果生成AES密钥
  4. 通过穷举循环平移找到正确的解密密钥

解题过程

步骤1：理解多项式环结构

题目工作在有限域GF(2)上的多项式环，模数为m(x)=xr−1，其中r=16381。

数学表示：

  • 基础环：R=GF(2)[x]
  • 商环：S=R/⟨xr−1⟩

步骤2：多项式有理重构原理

有理重构问题：给定模多项式M(x)和多项式H(x)，寻找A(x)和B(x)满足：

1
H(x)≡B(x)A(x)(modM(x))

其中：

  1. gcd(B(x),M(x))=1
  2. A(x)和B(x)的次数限制较小（本题中汉明重量d=41）

步骤3：扩展欧几里得算法实现

使用扩展欧几里得算法进行有理重构：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def rational_reconstruction(hint_poly):
    r0, r1 = m, R(hint_poly)
    t0, t1 = R(0), R(1)
    step = 0

    while r1 != 0:
        q = r0 // r1
        r0, r1 = r1, r0 + q * r1  # 在GF(2)上，加法等同于异或
        t0, t1 = t1, t0 + q * t1
        step += 1

        if hwt(r0) == d and hwt(t0) == d:
            return r0, t0

    print("Fail")
    return None, None

算法步骤详解：

  1. 初始化：r0=M(x), r1=H(x), t0=0, t1=1
  2. 迭代计算：
    • 计算商式：q=r0÷r1
    • 更新余数：r0,r1=r1,r0−q⋅r1
    • 更新系数：t0,t1=t1,t0−q⋅t1
  3. 终止条件：当r0和t0的汉明重量都等于d=41时返回

步骤4：汉明重量计算

汉明重量定义为多项式中非零系数的个数：

1
2
def hwt(poly):
    return len(poly.exponents())

在GF(2)上，非零系数即为1，因此汉明重量就是多项式中项的数量。

步骤5：多项式解析

从字符串形式解析多项式：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
hint_str = lines[0].split('=')[1].strip()
exps = []
for term in hint_str.split('+'):
    term = term.strip()
    if not term:
        continue
    if term == '1':
        exps.append(0)
    elif term == 'X':
        exps.append(1)
    elif term.startswith('X^'):
        exps.append(int(term[2:]))

hint_poly = sum(x**e for e in exps)

将形如”1 + X + X^2 + … + X^r”的字符串转换为多项式对象。

步骤6：循环平移与解密

对重构得到的B(x)进行所有可能的循环平移：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
B_S = S(B)
nonce = b"suanp01y"

for k in range(r):
    h0_candidate = B_S * (X**k)  # 循环平移
    key = md5(str(h0_candidate).encode()).digest()

    try:
        cipher = AES.new(key, AES.MODE_CTR, nonce=nonce)
        flag = cipher.decrypt(ct)
        if flag.startswith(b"RCTF{"):
            print("Success!")
            print(flag)
            return
    except:
        continue

数学原理：在商环S=R/⟨xr−1⟩中，乘以xk相当于循环平移。

步骤7：完整解题代码

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 Crypto.Cipher import AES
from hashlib import md5

r = 16381
d = 41

R.<x> = PolynomialRing(GF(2))
m = x^r - 1
S.<X> = R.quo(m)

def hwt(poly):
    return len(poly.exponents())

def rational_reconstruction(hint_poly):
    r0, r1 = m, R(hint_poly)
    t0, t1 = R(0), R(1)
    step = 0

    while r1 != 0:
        q = r0 // r1
        r0, r1 = r1, r0 + q * r1
        t0, t1 = t1, t0 + q * t1
        step += 1

        if hwt(r0) == d and hwt(t0) == d:
            return r0, t0

    print("Fail")
    return None, None

def solve():
    with open("output.txt", "r") as f:
        lines = f.read().splitlines()

    hint_str = lines[0].split('=')[1].strip()
    exps = []

    for term in hint_str.split('+'):
        term = term.strip()
        if not term:
            continue
        if term == '1':
            exps.append(0)
        elif term == 'X':
            exps.append(1)
        elif term.startswith('X^'):
            exps.append(int(term[2:]))

    hint_poly = sum(x**e for e in exps)
    ct = bytes.fromhex(lines[1])

    A, B = rational_reconstruction(hint_poly)

    if B is None:
        print("Fail")
        return

    B_S = S(B)
    nonce = b"suanp01y"

    for k in range(r):
        h0_candidate = B_S * (X**k)
        key = md5(str(h0_candidate).encode()).digest()

        try:
            cipher = AES.new(key, AES.MODE_CTR, nonce=nonce)
            flag = cipher.decrypt(ct)
            if flag.startswith(b"RCTF{"):
                print("Success!")
                print(flag)
                return
        except:
            continue

if __name__ == '__main__':
    solve()

数学原理详解

多项式环与商环

  • 多项式环：GF(2)[x]表示系数在GF(2)上的多项式环
  • 商环构造：S=R/⟨m(x)⟩，其中m(x)=xr−1
  • 循环性质：在商环S中，xr≡1，因此乘以xk实现循环平移

有理重构的数学基础

有理重构问题等价于寻找满足以下条件的多项式：

1
H(x)⋅B(x)≡A(x)(modM(x))

其中A(x)和B(x)满足特定的大小约束（本题中为汉明重量约束）。

扩展欧几里得算法

算法保证在有限步内找到满足条件的A(x)和B(x)，当满足：

1
deg(A)+deg(B)≤deg(M)

时，解是唯一的。