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

全网首发！！！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$ 个数据点。

三、解题思路

四、详细解题过程

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 数据位数分析

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

五、总结

5.1 知识点总结

5.2 解题关键

5.3 Flag

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