攻防世界GFSJ1229 Three

题目编号：GFSJ1229

解题过程

1. 附件下载是三个压缩包A.zip B.zip C.zip和一个python程序Three.py

2. A.zip可以直接解压出来，内容如下:

```
'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)
'2022-08-27 20:16:17.000001' Open Y00
'2022-08-27 20:16:17.000101' RGet Y01(12163251699969281466186532960410)
'2022-08-27 20:16:17.000299' Cyberloafing!!
'2022-08-27 20:16:17.004194' ReBuild Y0
'2022-08-27 20:16:17.013270' Save_Data

```
3. B.zip 和C.zip有密码，查看Three.py，代码加了注释后如下：

```Python
import datetime

import numpy as np

# 协议类，用于处理多方参与的加密计算

class Protocol:

def __init__(self, party_num):

# 初始化协议类，指定当前参与方编号 (party_num: 0, 1, 或 2)

self.pn = party_num # 参与方编号 (party_num: 0, 1, 2)

def Read_Data(self, path):

# 读取数据文件中的内容，尝试将其转换为数值（整数或浮点数）

data = open(path).readline().strip() # 从文件中读取一行数据并去除首尾空格

try:

if '.' in data:

data = float(data) # 如果数据包含小数点，则转换为浮点数

else:

data = int(data) # 否则，转换为整数

except:

# 如果转换失败，打印错误信息并退出程序

print('No number')

exit(-1)

return data # 返回读取的数据

def Get(self, x1, x2):

# 获取两个秘密共享的值 (函数未实现)

pass

def RGet(self, x1):

# 获取一个秘密共享的值 (函数未实现)

pass

def ReShare(self, x):

# 重新共享值 x，x = x + ri，其中 r0 + r1 + r2 = 0

# ri (i=0,1,2) 是随机整数，然后将 x 发送给 (self.pn + 1) % 3 的参与方

pass

def Secret_Share(self, x):

# 秘密共享函数，将 x 拆分为三个秘密共享的值

# x1 和 x2 是随机整数，x3 = x - x1 - x2

# sharelist 存储了三部分的秘密共享值，loc 确定了当前参与方的位置

# reserved 保存了两个与当前参与方相关的共享值，用于后续计算

x1, x2 = np.random.randint(0, 100), np.random.randint(0, 100) # 随机生成 x1 和 x2

x3 = x - x1 - x2 # 计算 x3，使 x1 + x2 + x3 = x

sharelist = [x1, x2, x3] # 将 x 分成三个部分

loc = self.pn # 当前参与方的位置

self.reserved = (sharelist[loc], sharelist[(loc + 1) % 3]) # 保留两个共享值

return (sharelist[0], sharelist[1]), (sharelist[1], sharelist[2]), (sharelist[2], sharelist[0])

def Mul_loc_compute(self, x1, y1, x2, y2):

# 局部乘法计算，使用秘密共享的 x1 和 y1 计算乘积

# 计算过程为 x1*y1 + x1*y2 + x2*y1，并将结果存储在 self.mulx

self.mulx = x1 * y1 + x1 * y2 + x2 * y1

def Add_loc_compute(self, x1, y1):

# 局部加法计算，计算两个共享值的和并存储在 self.addx

self.addx = x1 + y1

def Cyberslacking(self):

# 打印表示 "消极工作" 的消息 (仅作示例用途)

print('Cyberloafing!!')

def Save_Data(self):

# 保存数据的默认方法 (可选)

# 使用当前时间生成密码 (pwd)，压缩所有数据后重建函数的答案 (未实现)

pwd = str(datetime.datetime.now())

pass

def Func(self, expression):

# 打印数学表达式，将会计算表达式，但保证隐私不泄露

print('Math expression', expression, 'will be computed! You can get the answer without leak your privacy!')

def ReBuild(self, x1, x2, x3):

# 重建函数的答案，利用秘密共享的值 x1, x2, x3 求和得到原始数据

return x1 + x2 + x3

# 示例：A0 表示 'flag{xxxxxxxxxxx'，X0 表示 xxxxx...xxx，B0 表示 xxxxxxxxx}

# A (参与方 0) 拥有 A0，B (参与方 1) 拥有 X0，C (参与方 2) 拥有 B0

# 函数表示 A0 * X0 + B0

p0 = Protocol(0)

p1 = Protocol(1)

p2 = Protocol(2)
```
是C的算法，其中pwd = str(datetime.datetime.now())暴露了如何计算密码的，密码格式为当前时间精确到微秒，如'YYYY-MM-DD HH:MM:SS.ssssss'。

4. 破解C.zip的密码：

```python
## Three.py是C的算法

import zipfile # 导入 zipfile 库，用于处理 ZIP 文件

def extract(file, password):

"""

解压指定的 ZIP 文件到当前目录，使用给定的密码解压缩。

参数:

- file: 要解压缩的 zipfile.ZipFile 对象

- password: 解压密码，以字符串列表的形式提供

"""

file.extractall(path='.', pwd=''.join(password).encode('utf-8')) # 将密码拼接为字符串并编码为 UTF-8 格式

# 初始化空的密码列表，将用于存储所有可能的密码组合

password_lst = []

# 设置密码前缀，假设所有密码以同一时间戳前缀开头

prestr = '2022-08-27 20:16:17.'#从A.txt中找到getData的起始时间

# 构造 6 位数的密码组合并添加到 password_lst 列表中

for i in range(0, 999999): # 生成从 000000 到 999999 的所有可能组合

s = str(i) # 将数字转换为字符串

tmpnum = '0' * (6 - len(s)) + s # 前面补足 0 使其成为 6 位数

password_lst.append(prestr + tmpnum) # 将时间戳前缀和 6 位数字组合并添加到密码列表

# 打开指定路径的 ZIP 文件，并设为读模式

zfile = zipfile.ZipFile("C.zip", 'r')

# 遍历所有可能的密码，尝试解压 ZIP 文件

for pwd in password_lst:

try:

extract(zfile, pwd) # 尝试使用当前密码解压缩

print(pwd) # 如果解压成功，打印正确的密码

break # 成功后退出循环

except:

continue # 如果解压失败（密码错误），继续尝试下一个密码

##print: 2022-08-27 20:16:17.930813
```

5. 使用上面获得的密码解压C.zip, 获得C.txt内容如下：

```
'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)
'2022-08-27 20:16:13.923122' RGet Y01
'2022-08-27 20:16:15.000382' Open Y02
'2022-08-27 20:16:17.000892' RGet Y00
'2022-08-27 20:16:17.009702' Cyberloafing!!
'2022-08-27 20:16:17.019991' ReBuild Y0
'2022-08-27 20:16:17.930813' Save_Data
```

6. A.txt和C.txt提供了A0、A1以及加密分享和掩码，以及过程中的Y0和X0相关值，可以逆向计算，因为总的计算公式是A0*X0+B0=Y0，可以求出B0，计算程序如下：

```python
from Crypto.Util.number import long_to_bytes

# 定义局部乘法计算函数

# 通过已知的秘密共享值 A00、A01、X00 和 X01，计算出 C00 的真实值

# 此函数在秘密共享中用于计算多方参与的局部乘法

def Mul_loc_compute(x1, y1, x2, y2):

return x1 * y1 + x1 * y2 + x2 * y1

# 已知的 A0 值和各秘密共享的具体值，根据日志记录得出以下共享值：

# A0：是目标值，日志显示为 28829613228241459。

# A00_true 和 A01_true 是 A0 的两个共享值，来自 A 方日志的 'Get A00' 和 'Get A01'。

# X00_true 和 X01_true 是 X0 的两个共享值，来自 A 方日志的 'Get X00' 和 'Get X01'。

A0 = 28829613228241459

A00_true = 200254991086689

A01_true = 200241552690281

X00_true = 200058430391504

X01_true = 200401773940794

B00_true = 199957680670222

# 计算 C00 的真实值

# 使用 Mul_loc_compute 函数来计算局部乘法结果 C00_true，以便后续计算。

# 通过 A00_true 和 X00_true, A01_true 和 X01_true 的共享值计算得出。

C00_true = Mul_loc_compute(A00_true, X00_true, A01_true, X01_true)

# 根据日志，C00 经过了掩码操作，掩码值为 507412160912，来源于 A 方日志的 'ReShare C00'。

# 计算带掩码的 C00 值（C00_mask），供后续 Y00 的计算使用。

C00_mask = C00_true + 507412160912

# 计算 Y00_true

# 根据 A 方日志的 'Add_loc_compute C00,B00->Y00' 可知 Y00 是 C00 和 B00 的局部相加结果

# 因此，Y00_true = C00_mask + B00_true。

Y00_true = C00_mask + B00_true

# A 方日志的 'ReShare Y00' 显示 Y00 被应用了掩码 -1008362525723

# 计算出 Y00 的带掩码值 Y00_mask，以供最终计算使用。

Y00_mask = Y00_true + (-1008362525723)

# 读取 C 方日志获取 Y02 的带掩码值 924422050091362838179268571917871 和掩码 507036073644

# Y02_mask 和 Y02_true 分别表示 Y02 的带掩码值和真实值

Y02_mask = 924422050091362838179268571917871

Y02_true = Y02_mask - 507036073644

# C 方日志显示 Y01_mask 值为 12163251699969281466186532960410，将其直接使用

Y01_mask = 12163251699969281466186532960410

# A 方日志显示 C02_mask 的值为 924422050091355025836012334663090

# 使用 Y02_true 和 C02_mask 计算 B02_true，这是 B0 的一部分。

C02_mask = 924422050091355025836012334663090

B02_true = Y02_true - C02_mask

# 根据 A 和 C 日志中 B 的各共享值 (B00_true, B01_true) 以及计算出的 B02_true

# 还原 B0 值，这是最终的关键结果之一。

B01_true = 200362172648094

B0 = B00_true + B01_true + B02_true

# 计算 Y0 的总和，用于还原 X0 值

# 使用 Y00_mask、Y01_mask 和 Y02_mask，通过累加得到 Y0 的值

Y0 = Y00_mask + Y01_mask + Y02_mask

# 计算 X0 值

# 根据公式 X0 = (Y0 - B0) // A0 计算得出 X0，这是最终需要的另一个关键结果

X0 = (Y0 - B0) // A0

# 将 A0、X0 和 B0 转换为 ASCII，并组合成 flag，代表最终解密的结果。

flag = long_to_bytes(A0) + long_to_bytes(X0) + long_to_bytes(B0)

print(flag)# b'flag{23snyau_sllpmxcz}'
```

7. 备注解释下多方加密（by AI）

在这个三方安全计算协议中，`A00`、`B00`、`C00`、`X00` 等变量是每个参与方持有的秘密共享值的部分。这些共享值通过分割和掩码等方式隐藏了原始数据，在不泄露完整信息的情况下进行计算。

### 各变量的含义

- **A0、B0、X0**：这些是原始值，代表 Allen、Bob 和其他参与方各自拥有的秘密数据。例如：
- `A0`：由 Allen 持有的原始值。
- `X0`：是 Allen 和其他参与方希望参与计算的一个值。
- `B0`：由 Bob 持有的原始值。

- **A00、B00、C00、X00**：这些是 `A0`、`B0`、`C0`、`X0` 的分片，每个原始值被分割为多份秘密共享的片段，各参与方只持有其中一部分。
- **A00**：`A0` 的分片，由参与方之一持有。
- **B00**：`B0` 的分片，由参与方之一持有。
- **C00**：`C0` 的分片，这是计算过程中生成的中间结果。
- **X00**：`X0` 的分片。

这些分片和共享值的划分是为了让多个参与方共同进行计算，同时保护隐私，使得单个参与方无法独立得出完整的原始数据。

### 计算流程概述

在一次多方计算中，每个参与方通过持有的共享值分片参与运算，具体的流程如下：

1. **秘密共享（Secret Sharing）**：
- 将每个参与方的原始值（如 `A0`、`B0`、`X0`）分成多个共享片段，如 `A00`、`A01`、`A02` 等。
- 这些共享片段被分配给不同的参与方。例如，Allen 可能持有 `A00`，Bob 持有 `A01`，Crosley 持有 `A02`。这样，任何单独一个片段都无法还原 `A0` 的完整值。

2. **局部计算（Local Computation）**：
- 每个参与方在自己持有的分片上执行局部计算。例如：
- Allen 计算 `A00 * X00`，Bob 计算 `A01 * X01`，Crosley 计算 `A02 * X02`。
- 这些局部计算结果形成了 `C00`、`C01`、`C02` 等中间共享值。

3. **重新共享和掩码处理（ReShare and Masking）**：
- 为了防止泄露中间结果，每个参与方会给自己的计算结果加上随机掩码。例如，Allen 的局部计算结果 `C00` 会加上一个掩码 `C00_mask`。
- 然后，带掩码的结果 `C00_mask` 会被共享给其他参与方，以供后续的合并计算。

4. **合并局部结果（Combine Local Results）**：
- 所有局部计算的结果（如 `C00_mask`, `C01_mask`, `C02_mask`）在各参与方间汇总，通过计算得到最终结果的共享值。
- 合并结果的过程确保了各参与方能共同计算出所需的结果（例如 `A0 * X0 + B0`），而每个参与方都不会泄露自己的原始数据。

5. **最终重建（ReBuild）**：
- 当所有计算完成后，所有共享值可以重构为最终结果。各方将合并后的共享值返回给 Allen，Allen 可以使用这些值恢复出最终的结果。

### 例子：如何运作

假设 Allen 希望计算 `A0 * X0 + B0`，整个过程可以总结如下：

1. **秘密共享阶段**：`A0`、`X0` 和 `B0` 被分割成 `A00, A01, A02`，`X00, X01, X02`，`B00, B01, B02` 三个部分，每个参与方持有一部分。
2. **局部计算**：每个参与方计算 `A00 * X00`、`A01 * X01`、`A02 * X02`。
3. **掩码和重新共享**：每个局部结果加上随机掩码，形成 `C00_mask`、`C01_mask`、`C02_mask`，防止泄露中间数据。
4. **加法和最终重建**：各方汇总带掩码的局部结果，并执行加法操作得到加法结果 `Y0`。最终 `Y0` 被重构并解码，恢复出最终的计算结果。

通过这种流程，所有参与方可以在保护数据隐私的同时共同完成 `A0 * X0 + B0` 的计算。