全网首发！！！CTF BUUOJ [DASCTF X GFCTF 2022十月挑战赛！]Recover Secret Writeup

一、题目信息

• 题目名称：Recover Secret
• 来源：DASCTF X GFCTF 2022 十月挑战赛
• 分类：Crypto
• 题目描述：Little AT told K people the most precious secret, now K people gathered together, please help me to recover the secret.

二、题目分析

题目提供了加密脚本 recover secret.py 和输出文件 output。让我们先分析加密逻辑。

2.1 加密脚本核心逻辑

def main():
    k = 6
    sk = []
    flag = os.environ["flag for GFCTF2022-Crypto Recover Secret"]
    secret = libnum.s2n(flag)
    assert len(bin(secret)) < 514
    enc = Encryptor()
    sk = [enc.__key_gen__() for i in range(k)]
    print(sk)  # 关键点1：私钥直接输出！
    s = [_rand_int(_N - 1) for i in range(k)]
    s[0] = secret  # 秘密是s[0]
    # ... Commit部分用于生成X值，非关键 ...
    X = []
    Y = []
    for i in range(1, k + 1):
        # X_i = E(∑ i^j * r_j)，利用Paillier加法同态性
        # Y_i = E(∑ i^j * s_j)，即E(S(i))
        # S(x) = s_0 + s_1*x + s_2*x^2 + ... + s_5*x^5
        
    X_Y = shuffle(X, Y, 51)  # 关键点2：数据混淆
    print(X_Y)

2.2 关键发现

发现1：私钥泄露

print(sk)

私钥 sk 直接被打印到 output 文件中！这意味着我们可以直接解密所有Paillier加密的数据。
发现2：秘密共享结构

s[0] = secret
Y_i = E(S(i))

这是一个 Shamir秘密共享 的变体。秘密 secret 是多项式 $S(x)$ 的常数项 $s_0$：
$$S(x)=s_0+s_{1}x+s_2{x}^2+s_3{x}^3+s_4{x}^4+s_5{x}^5$$
发现3：噪声混淆

def shuffle(X, Y, x):
    res = []
    for i in range(len(X)):
        res.append([i, X[i], Y[i]])  # 真实数据
        for j in range(x):
            # 添加噪声数据
            res.append([i, X[i] + random.randint(-X[i], X[i]), 
                           Y[i] + random.randint(-Y[i], Y[i])
    random.shuffle(res)
    return res

每个真实数据点 $(X_i,Y_i)$ 对应 51 个噪声点，总共 $6+6\times 51=312$ 个数据点。

三、解题思路

1. 解析output文件：提取私钥 sk 和混淆数据 X_Y
2. Paillier解密：使用泄露的私钥解密所有 Y 值
3. 数据筛选：
   • 真实数据解密后约 514-525位（多项式值）
   • 噪声数据解密后约 1018-1024位（接近模数n）
   • 选择每个索引对应的最小解密值
4. 拉格朗日插值：使用筛选出的6个点计算 $S(0)=s_0$

四、详细解题过程

4.1 完整解题脚本

import gmpy2
from gmpy2 import mpz, powmod
import libnum
import re
import ast
from fractions import Fraction
def paillier_dec(c, n, lmd, mu):
    """Paillier解密"""
    n2 = n * n
    x = powmod(c, lmd, n2)
    Lx = (x - 1) // n
    m = (Lx * mu) % n
    return m
def clean_mpz(s):
    """清理mpz标记"""
    return re.sub(r'mpz\((.*?)\)', r'\1', s)
def safe_eval(s):
    """安全的eval"""
    try:
        return ast.literal_eval(s)
    except:
        return ast.literal_eval(clean_mpz(s))
def bit_length(n):
    """获取位数"""
    return gmpy2.bit_length(n)
# 读取文件
with open('output', 'r', encoding='utf-8') as f:
    lines = [l.strip() for l in f.read().strip().split('\n') if l.strip()]
all_data = [safe_eval(line) for line in lines]
sk = all_data[0]    # 第1行：私钥
X_Y = all_data[3]   # 第4行：混淆数据
print(f"数据: sk(6组密钥), X_Y({len(X_Y)}个点)\n")
# 关键步骤：找到每个索引对应的最小解密值
print("="*60)
print("筛选真实数据点（选择最小解密值）...")
print("="*60 + "\n")
# 对每个索引，收集所有解密结果
idx_values = {}  # idx -> [(y_dec, y_val), ...]
for item in X_Y:
    idx = item[0]
    y_val = item[2]
    
    # 获取对应密钥
    n_i = mpz(sk[idx][0][0])
    lmd = mpz(sk[idx][1][0])
    mu = mpz(sk[idx][1][1])
    
    try:
        y_dec = paillier_dec(mpz(y_val), n_i, lmd, mu)
        if idx not in idx_values:
            idx_values[idx] = []
        idx_values[idx].append((int(y_dec), int(y_val)))
    except:
        pass
# 选择最小的解密值（真实数据约528位，噪声接近1024位）
points = {}
for idx in range(6):
    if idx in idx_values:
        min_dec, _ = min(idx_values[idx], key=lambda x: x[0])
        points[idx + 1] = min_dec
        bits = bit_length(min_dec)
        print(f"idx={idx}, x={idx+1}: 最小解密值 {bits} 位")
print(f"\n收集到 {len(points)} 个数据点\n")
# 拉格朗日插值求S(0)
print("="*60)
print("拉格朗日插值")
print("="*60 + "\n")
x_vals = sorted(points.keys())
secret_frac = Fraction(0, 1)
for i in x_vals:
    xi, yi = i, points[i]
    
    numerator = Fraction(1, 1)
    denominator = Fraction(1, 1)
    
    for j in x_vals:
        if i != j:
            numerator *= Fraction(0 - j, 1)
            denominator *= Fraction(xi - j, 1)
    
    l_i_0 = numerator / denominator
    secret_frac += Fraction(yi, 1) * l_i_0
secret = secret_frac.numerator // secret_frac.denominator
print(f"恢复的秘密: {secret}")
print(f"位数: {bit_length(abs(secret)) if secret != 0 else 0}")
try:
    flag = libnum.n2s(abs(int(secret)))
    print(f"\nFlag: {flag}")
    try:
        print(f"Flag decoded: {flag.decode()}")
    except:
        pass
except Exception as e:
    print(f"\n转换失败: {e}")
    print(f"Hex: {hex(abs(int(secret)))}")

4.2 运行结果

数据: sk(6组密钥), X_Y(312个点)

============================================================
筛选真实数据点（选择最小解密值）...
============================================================

idx=0, x=1: 最小解密值 514 位
idx=1, x=2: 最小解密值 518 位
idx=2, x=3: 最小解密值 521 位
idx=3, x=4: 最小解密值 523 位
idx=4, x=5: 最小解密值 524 位
idx=5, x=6: 最小解密值 525 位

收集到 6 个数据点

============================================================
拉格朗日插值
============================================================

恢复的秘密: 2445986771771386901982964970052402491236020951408388483652278064206253525614398139039401896841700904887165
位数: 351

Flag: b'DASCTF{fe22ca94-c002-d10b-7104-1c5eff3f335c}'
Flag decoded: DASCTF{fe22ca94-c002-d10b-7104-1c5eff3f335c}

4.3 数据位数分析

观察解密结果的位数变化：

idx	x值	最小解密值位数
0	1	514 位
1	2	518 位
2	3	521 位
3	4	523 位
4	5	524 位
5	6	525 位
位数随x值增大而增大，这完全符合多项式值的增长规律！
而噪声数据解密后位数都在 1018-1024位，接近Paillier模数n的位数（1022位），因此可以通过选择最小解密值来过滤噪声。

五、总结

5.1 知识点总结

知识点	说明
Paillier加密	加法同态加密，$E(m_1)\cdot E(m_2)=E(m_1+m_2)$
Shamir秘密共享	秘密作为多项式常数项，通过拉格朗日插值恢复
数据混淆与过滤	利用数值大小的显著差异区分真实数据和噪声
私钥泄露	出题人的"失误"（或故意设计）大大降低了题目难度

5.2 解题关键

1. 识别私钥泄露：发现 print(sk) 直接暴露了私钥
2. 理解秘密共享结构：意识到 $S(0)$ 就是flag
3. 噪声过滤策略：利用位长差异筛选真实数据（这是本题的核心难点）
4. 精确计算：使用 Fraction 进行有理数运算，避免精度损失

5.3 Flag

DASCTF{fe22ca94-c002-d10b-7104-1c5eff3f335c}