#include <vector>
#include <cstdint>
#include <algorithm>
using namespace std;
// 强位混合加密哈希函数 (基于 MurmurHash3 原理)
uint64_t mix_hash(uint64_t x) {
x ^= x >> 30;
x *= 0xbf58476d1ce4e5b9ULL;
x ^= x >> 27;
x *= 0x94d049bb133111ebULL;
x ^= x >> 31;
return x;
}
vector<bool> send_packet(vector<bool> A);
// Aisha 的发送端策略
void send_message(vector<bool> M, vector<bool> C) {
int S = M.size();
int D = (S + 15) / 16;
vector<int> safe;
for (int i = 0; i < 31; ++i) {
if (!C[i]) safe.push_back(i);
}
vector<vector<bool>> R;
int idx = 0;
// 1. 发送原始消息数据
for (int p = 0; p < D; ++p) {
vector<bool> A(31, false);
for (int i = 0; i < 16; ++i) {
if (idx < S) A[safe[i]] = M[idx++];
}
R.push_back(send_packet(A));
}
// 2. 发送消息的确切长度 S
vector<bool> AS(31, false);
for (int i = 0; i < 16; ++i) {
AS[safe[i]] = (S >> i) & 1;
}
R.push_back(send_packet(AS));
// 3. 计算基于全局反馈的 48-bit 加密哈希
uint64_t h[31] = {0};
for (int c = 0; c < 31; ++c) {
uint64_t state = 0x123456789ABCDEFULL ^ c;
for (size_t p = 0; p < R.size(); ++p) {
state = mix_hash(state ^ (R[p][c] ? 0x9e3779b97f4a7c15ULL : 0));
}
h[c] = state & 0xFFFFFFFFFFFFULL; // 截取 48 bit
}
// 4. 计算属于安全列的 48-bit 异或目标并分发到最后 3 个包
uint64_t target = 0;
for (int i = 0; i < 16; ++i) target ^= h[safe[i]];
for (int p = 0; p < 3; ++p) {
vector<bool> A(31, false);
for (int i = 0; i < 16; ++i) {
A[safe[i]] = (target >> (p * 16 + i)) & 1;
}
R.push_back(send_packet(A));
}
}
// 递归生成所有组合以便在 MITM 中使用
void get_subsets(const vector<int>& cols, int k, vector<pair<uint64_t, int>>& res,
const uint64_t* H, const uint64_t* V, int rank_offset) {
int n = cols.size();
int mask = (1 << k) - 1;
while (mask < (1 << n)) {
uint64_t val = 0;
int rank = rank_offset;
for (int i = 0; i < n; ++i) {
if ((mask >> i) & 1) {
int c = cols[i];
val ^= H[c] ^ (V[c] << rank); // 将比特回归至原本属于 Target 的位置对齐
rank++;
}
}
res.push_back({val, mask});
if (k == 0) break;
uint32_t c_mask = mask & -mask;
uint32_t r = mask + c_mask;
mask = (((r ^ mask) >> 2) / c_mask) | r;
}
}
// Basma 的接收端策略
vector<bool> receive_message(vector<vector<bool>> R) {
int Q = R.size();
int D = Q - 4; // 推算得知承载数据包的明确数量
uint64_t H[31] = {0};
uint64_t V[31] = {0};
for (int c = 0; c < 31; ++c) {
uint64_t state = 0x123456789ABCDEFULL ^ c;
for (int p = 0; p <= D; ++p) { // 根据前 D+1 个包计算出哈希参照
state = mix_hash(state ^ (R[p][c] ? 0x9e3779b97f4a7c15ULL : 0));
}
H[c] = state & 0xFFFFFFFFFFFFULL;
// 拼凑 Cleopatra 篡改后的最后 3 个包内的分布值
uint64_t v0 = R[D+1][c] ? 1 : 0;
uint64_t v1 = R[D+2][c] ? 1 : 0;
uint64_t v2 = R[D+3][c] ? 1 : 0;
V[c] = (v2 << 32) | (v1 << 16) | v0;
}
vector<int> left_cols, right_cols;
for (int i = 0; i < 16; ++i) left_cols.push_back(i);
for (int i = 16; i < 31; ++i) right_cols.push_back(i);
// 双向折半碰撞搜索 (Meet-In-The-Middle)，耗时 < 10ms
for (int k = 0; k <= 16; ++k) {
if (k > 16 || (16 - k) > 15) continue;
vector<pair<uint64_t, int>> left_res, right_res;
get_subsets(left_cols, k, left_res, H, V, 0);
get_subsets(right_cols, 16 - k, right_res, H, V, k);
sort(left_res.begin(), left_res.end());
sort(right_res.begin(), right_res.end());
int i = 0, j = 0;
while (i < left_res.size() && j < right_res.size()) {
if (left_res[i].first == right_res[j].first) {
int maskL = left_res[i].second;
int maskR = right_res[j].second;
vector<int> safe;
for (int m = 0; m < 16; ++m) if ((maskL >> m) & 1) safe.push_back(left_cols[m]);
for (int m = 0; m < 15; ++m) if ((maskR >> m) & 1) safe.push_back(right_cols[m]);
// 首先解析真实的长度 S
int S = 0;
for (int m = 0; m < 16; ++m) {
if (R[D][safe[m]]) S |= (1 << m);
}
// 根据绝对安全的列索引，抽离纯净的消息 M
vector<bool> M_ret;
int idx = 0;
for (int p = 0; p < D; ++p) {
for (int m = 0; m < 16; ++m) {
if (idx < S) {
M_ret.push_back(R[p][safe[m]]);
idx++;
}
}
}
return M_ret;
} else if (left_res[i].first < right_res[j].first) {
i++;
} else {
j++;
}
}
}
return {};
}
