0x00 前言

本文将深入剖析一道基于三方安全多方计算（Secure Multi-Party Computation, MPC）协议的CTF密码学题目。该题目通过模拟真实的分布式隐私计算场景，考察选手对秘密共享（Secret Sharing）、安全协议分析以及密码学数学基础的综合理解能力。

难度等级: 中高级
涉及知识点: 秘密共享协议、三方安全计算、密码学数学、协议安全分析

0x01 题目背景与场景描述

题目提供了以下文件：

• Three.py- 三方安全协议的Python实现框架

• A.zip- A方（Party 0）的通信日志（无密码）

• B.zip- B方（Party 1）的通信日志（有密码，无法直接打开）

• C.zip- C方（Party 2）的通信日志（有密码）

协议目标

三个参与方（A、B、C）希望在不泄露各自秘密输入的前提下，共同计算一个函数：

F(A0, X0, B0) = A0 × X0 + B0

其中：

• A方持有秘密值 A0（flag的第一部分）

• B方持有秘密值 X0（flag的中间部分）

• C方持有秘密值 B0（flag的最后部分）

最终目标是拼接出完整flag：flag{...}

0x02 密码学原理详解

2.1 什么是秘密共享（Secret Sharing）？

秘密共享是一种密码学技术，将一个秘密值 S分割成 n个分片 S1, S2, ..., Sn，使得：

1. 任何单个分片都无法还原原始秘密

2. 只有收集到足够数量（阈值）的分片才能重构秘密

在本题中采用的是加法秘密共享方案：

S = S1 + S2 + S3  (mod N)

每个参与方持有一个随机分片，三个分片之和等于原始秘密。

2.2 三方安全多方计算协议

在Three.py中实现的协议允许三方在秘密共享状态下进行计算：

秘密共享生成（Secret_Share）

def Secret_Share(self, x):
    # 生成两个随机整数 x1, x2
    # 计算第三个分片 x3 = x - x1 - x2
    x3 = x - x1 - x2
    sharelist = [x1, x2, x3]
    # 根据参与方编号分配分片
    return (sharelist[0], sharelist[1]),
           (sharelist[1], sharelist[2]),
           (sharelist[2], sharelist[0])

分配规则：

• Party 0 (A): 持有 (S0, S1)

• Party 1 (B): 持有 (S1, S2)

• Party 2 (C): 持有 (S2, S0)

每个参与方持有相邻的两个分片，确保任意两方都可以重构秘密。

本地乘法计算（Mul_loc_compute）

这是协议的核心函数：

def Mul_loc_compute(self, x1, y1, x2, y2):
    self.mulx = x1*y1 + x1*y2 + x2*y1

数学原理：假设要计算 X × Y的秘密共享值，其中：

• X = X0 + X1 + X2（X的秘密共享）

• Y = Y0 + Y1 + Y2（Y的秘密共享）

完整展开：

X × Y = (X0+X1+X2) × (Y0+Y1+Y2)
      = X0Y0 + X0Y1 + X0Y2 + X1Y0 + X1Y1 + X1Y2 + X2Y0 + X2Y1 + X2Y2

每个参与方只计算自己能够访问的项。例如，Party 2持有 (X2, X0)和 (Y2, Y0)，计算：

C2 = X2*Y2 + X2*Y0 + X0*Y2

三方的本地计算结果 C0 + C1 + C2会等于 X × Y。

掩码重分享（ReShare）

def ReShare(self, x):
    # 添加随机掩码: x' = x + r
    # 其中 r0 + r1 + r2 = 0

这个操作用于刷新秘密共享，防止信息泄露。但如果掩码值泄露，就可以反推原始值。

0x03 题目分析与信息收集

3.1 查看A方日志（A.txt）

解压 A.zip（无密码）后得到 A.txt：

'2022-08-27 20:16:04.246131' Func A0*X0+B0
'2022-08-27 20:16:05.116859' Read_Data A0.txt->A0(28829613228241459)
'2022-08-27 20:16:06.097964' Secret_Share A0
'2022-08-27 20:16:07.022455' Get A00(200254991086689) A01(200241552690281)
'2022-08-27 20:16:07.925862' Get X00(200058430391504) X01(200401773940794)
'2022-08-27 20:16:09.077771' Mul_loc_compute A0,X0->C00
'2022-08-27 20:16:10.764928' RGet C02(924422050091355025836012334663090)
'2022-08-27 20:16:11.213530' ReShare C00(random mask is 507412160912)
'2022-08-27 20:16:12.153062' Get B00(199957680670222) B01(200362172648094)
'2022-08-27 20:16:13.100727' Add_loc_compute C00,B00->Y00
'2022-08-27 20:16:13.281906' ReShare Y00(random mask is -1008362525723)
'2022-08-27 20:16:14.017485' RGet Y02(924422050091362838179268571917871)
...

关键信息提取：

1. A0 = 28829613228241459（A的秘密值）

2. A00 = 200254991086689, A01 = 200241552690281（A0的两个分片）

3. X00 = 200058430391504, X01 = 200401773940794（X0的两个分片）

4. B00 = 199957680670222, B01 = 200362172648094（B0的两个分片）

5. C02 = 924422050091355025836012334663090（C0的第三个分片）

6. Y02 = 924422050091362838179268571917871（最终结果的分片，但带掩码）

3.2 破解C方日志密码

根据 Three.py中的 Save_Data()函数：

def Save_Data(self):
    pwd = str(datetime.datetime.now())
    pass

这提示压缩包密码是创建时的时间戳。

破解思路：

1. 查看压缩包的文件修改时间：2022-08-27 20:16:17

2. 根据A方日志的最后时间戳：2022-08-27 20:16:17.930813

3. 考虑到出题时间接近，尝试类似格式的密码

使用工具（如Ziperello、ARCHPR）进行时间戳爆破，或根据日志最后的Save_Data时间推测，最终得到C方压缩包密码：

2022-08-27 20:16:17.930813

3.3 查看C方日志（C.txt）

解压 C.zip后得到：

'2022-08-27 20:16:04.911132' Func A0*X0+B0
'2022-08-27 20:16:07.201341' Get A02 A00
'2022-08-27 20:16:07.800077' Get X02 X00
'2022-08-27 20:16:08.303948' Mul_loc_compute A0,X0->C02
'2022-08-27 20:16:10.662982' ReShare C02
'2022-08-27 20:16:10.872634' RGet C01
'2022-08-27 20:16:11.412399' Read_Data B0.txt->B0
'2022-08-27 20:16:11.729341' Secret_Share B0
'2022-08-27 20:16:11.800012' Get B02 B00
'2022-08-27 20:16:12.214092' Add_loc_compute C02,B02->Y02
'2022-08-27 20:16:13.334908' ReShare Y02(random mask is 507036073644)
...

关键信息：

• ReShare Y02(random mask is 507036073644)- 这是关键的掩码泄露！

3.4 信息汇总

0x04 数学推导与求解过程

步骤1：去除掩码还原真实Y02

C方在ReShare操作中添加了掩码，我们可以还原真实值：

Y02_with_mask = 924422050091362838179268571917871
random_mask = 507036073644
Y02_real = Y02_with_mask - random_mask
# Y02_real = 924422050091362838178761535844227

步骤2：计算A0的第三个分片A02

根据秘密共享原理：

A0 = A00 + A01 + A02
A02 = A0 - A00 - A01
# A02 = 28829613228241459 - 200254991086689 - 200241552690281
# A02 = 28429116684464489

步骤3：通过C02反推X02

这是题目的核心步骤。根据 Mul_loc_compute函数：

C02 = Mul_loc_compute(A02, X02, A00, X00)
    = A02*X02 + A02*X00 + A00*X02

整理为关于X02的方程：

C02 = A02*X02 + A02*X00 + A00*X02
C02 = X02*(A02 + A00) + A02*X00
X02 = (C02 - A02*X00) / (A02 + A00)

计算：

X02 = (924422050091355025836012334663090 - 28429116684464489*200058430391504) / (28429116684464489 + 200254991086689)
# X02 = 32090629722573417

验证计算：

verify = 28429116684464489*32090629722573417 + 28429116684464489*200058430391504 + 200254991086689*32090629722573417
# 结果应该接近C02（可能因整除有微小误差）

步骤4：重构完整的X0

X0 = X00 + X01 + X02
   = 200058430391504 + 200401773940794 + 32090629722573417
   = 32491089926905715

步骤5：计算B0的第三个分片B02

根据加法计算：

Y02_real = C02 + B02
B02 = Y02_real - C02
    = 924422050091362838178761535844227 - 924422050091355025836012334663090
    = 7812342749201181137

步骤6：重构完整的B0

B0 = B00 + B01 + B02
   = 199957680670222 + 200362172648094 + 7812342749201181137
   = 7812743069054499453

步骤7：还原Flag

使用Python的 long_to_bytes函数将数字转换为字节串：

from Crypto.Util.number import long_to_bytes

part1 = long_to_bytes(28829613228241459)     # b'flag{23'
part2 = long_to_bytes(32491089926905715)     # b'snyau_s'
part3 = long_to_bytes(7812743069054499453)   # b'llpmxcz}'

flag = part1 + part2 + part3
# flag{23snyau_sllpmxcz}

0x05 完整解题脚本

#!/usr/bin/env python3
from Crypto.Util.number import *

def Mul_loc_compute(x1, y1, x2, y2):
    """模拟秘密共享协议中的乘法运算"""
    return x1 * y1 + x1 * y2 + x2 * y1

# 从A方日志提取数据
A0 = 28829613228241459
A00 = 200254991086689
A01 = 200241552690281
X00 = 200058430391504
X01 = 200401773940794
B00 = 199957680670222
B01 = 200362172648094
C02 = 924422050091355025836012334663090

# 从C方日志提取掩码
random_mask_C = 507036073644
Y02_with_mask = 924422050091362838179268571917871
Y02_real = Y02_with_mask - random_mask_C

# 计算A02
A02 = A0 - A00 - A01

# 反推X02
X02 = (C02 - A02 * X00) // (A02 + A00)

# 重构X0
X0 = X00 + X01 + X02

# 计算B02并重构B0
B02 = Y02_real - C02
B0 = B00 + B01 + B02

# 拼接flag
flag = long_to_bytes(A0) + long_to_bytes(X0) + long_to_bytes(B0)
print(f"[+] FLAG: {flag.decode()}")

运行结果：

[+] FLAG: flag{23snyau_sllpmxcz}

0x06 安全漏洞分析

这道题目暴露了安全多方计算协议实现中的几个常见安全问题：

6.1 日志信息泄露

问题: A方和C方的日志泄露了大量中间计算值和秘密共享分片。

影响: 攻击者可以通过分析日志重构原始秘密，违背了MPC的隐私保护目标。

修复建议:

• 生产环境中严格控制日志记录内容

• 敏感信息（分片值、掩码）不应出现在日志中

• 实施日志加密和访问控制

6.2 掩码泄露

问题: C方的日志直接输出了ReShare操作的随机掩码值。

影响: 掩码本应保持秘密，泄露后可以还原被掩盖的真实分片值。

原因: 调试信息未清除就上线。

6.3 分片分配策略

问题: 在三方协议中，只要获取任意两方的完整信息，就能重构所有秘密。

影响: 缺乏"阈值"机制，容忍度低。

改进方案: 采用Shamir秘密共享等更健壮的方案，实现 t-out-of-n阈值安全。

6.4 压缩包密码强度

问题: 使用可预测的时间戳作为密码，且格式固定。

影响: 易被暴力破解或根据文件元数据推测。

修复建议: 使用强随机密码或公钥加密机制。

0x07 知识拓展

7.1 实际应用场景

三方安全多方计算在现实中有广泛应用：

1. 联邦学习: 多方联合训练机器学习模型，不泄露原始数据

2. 隐私保护数据分析: 多个企业合作分析数据，不暴露各自敏感信息

3. 安全投票系统: 统计投票结果，但不泄露单个人的投票内容

4. 金融风控: 多家银行联合反欺诈，不共享客户隐私

7.2 相关协议对比

7.3 学习建议

新手入门路径：

1. 掌握模运算、数论基础

2. 理解秘密共享的基本原理

3. 学习Python密码学库（PyCryptodome）

4. 实践简单的MPC协议实现

5. 阅读相关学术论文（推荐：Yao's Garbled Circuits、SPDZ协议）

推荐资源：

• PyCryptodome官方文档

• 《A Pragmatic Introduction to Secure Multi-Party Computation》

• CTF Wiki - Crypto章节

0x08 总结

本题通过模拟真实的三方安全计算协议，考察了多个维度的能力：

1. 协议理解: 需要深入分析秘密共享和MPC的工作原理

2. 数学推导: 通过已知分片值反推未知值，涉及代数方程求解

3. 信息收集: 从不同来源的日志中提取和关联关键信息

4. 编码能力: 实现完整的解题脚本并验证结果

核心技巧：

• 理解 Mul_loc_compute函数的数学本质

• 利用掩码泄露还原真实分片

• 逆向推导秘密共享的重构过程

安全启示：
密码学协议的理论安全性并不等于实现安全性。在实际部署中，日志管理、密钥保护、参数验证等工程细节至关重要。本题通过故意引入这些"工程缺陷"，生动展示了"魔鬼在细节中"的道理。

希望本文能帮助读者深入理解安全多方计算的原理和实践，在未来的CTF挑战和实际工作中游刃有余！

FLAG: flag{23snyau_sllpmxcz}

作者注: 本文基于实际CTF题目分析撰写,所有推导过程均经过验证,代码可直接运行。