#include <vector>
#include <cstdint>
#include <algorithm>
using namespace std;
vector<bool> send_packet(vector<bool> A);
void send_message(vector<bool> M, vector<bool> C) {
int S = M.size();
vector<int> safe_cols;
for(int i = 0; i < 31; ++i) {
if(!C[i]) safe_cols.push_back(i);
}
// Fill safe_stream exactly to 1024 bits
vector<bool> safe_stream;
for(int i = 0; i < S; ++i) safe_stream.push_back(M[i]);
if(S < 1024) safe_stream.push_back(true);
while(safe_stream.size() < 1024) safe_stream.push_back(false);
bool flag = (S == 1024);
vector<vector<bool>> B(66, vector<bool>(31, false));
for(int p = 0; p < 64; ++p) {
vector<bool> A(31, false);
for(int j = 0; j < 16; ++j) {
A[safe_cols[j]] = safe_stream[p * 16 + j];
}
B[p] = send_packet(A);
}
// 31-bit strong cryptographic Target hashing over columns
uint32_t Target = 0;
for(int j = 0; j < 16; ++j) {
uint32_t h = 0x811c9dc5 ^ j;
for(int p = 0; p < 64; ++p) {
h ^= (B[p][safe_cols[j]] ? 1 : 0);
h *= 0x01000193;
}
h ^= h >> 16; h *= 0x85ebca6b;
h ^= h >> 13; h *= 0xc2b2ae35;
h ^= h >> 16;
Target ^= (h & 0x7FFFFFFF);
}
// Construct signature packets (Packet 64 & 65)
vector<bool> A64(31, false), A65(31, false);
A64[safe_cols[0]] = flag;
A65[safe_cols[0]] = (Target >> 15) & 1;
for(int j = 1; j < 16; ++j) {
A64[safe_cols[j]] = (Target >> (j - 1)) & 1;
A65[safe_cols[j]] = (Target >> (15 + j)) & 1;
}
send_packet(A64);
send_packet(A65);
}
// Generate subsets for MITM combinations
void get_subsets(const vector<int>& cols, int k, vector<pair<uint32_t, int>>& res,
const uint32_t H[31][16], const uint32_t V[31][16], int rank_offset) {
int n = cols.size();
int mask = (1 << k) - 1;
while(mask < (1 << n)) {
uint32_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][rank] ^ V[c][rank];
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;
}
}
vector<bool> receive_message(vector<vector<bool>> R) {
uint32_t H[31][16];
uint32_t V[31][16];
for(int c = 0; c < 31; ++c) {
for(int j = 0; j < 16; ++j) {
uint32_t h = 0x811c9dc5 ^ j;
for(int p = 0; p < 64; ++p) {
h ^= (R[p][c] ? 1 : 0);
h *= 0x01000193;
}
h ^= h >> 16; h *= 0x85ebca6b;
h ^= h >> 13; h *= 0xc2b2ae35;
h ^= h >> 16;
H[c][j] = h & 0x7FFFFFFF;
// Extract the shifted Target bits assignment per column mechanism
if(j == 0) {
V[c][j] = (R[65][c] ? 1 : 0) << 15;
} else {
V[c][j] = ((R[64][c] ? 1 : 0) << (j - 1)) | ((R[65][c] ? 1 : 0) << (15 + j));
}
}
}
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 subset iteration
for(int k = 0; k <= 16; ++k) {
if(k > 16 || (16 - k) > 15) continue;
vector<pair<uint32_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> S_cols;
for(int m = 0; m < 16; ++m) if((maskL >> m) & 1) S_cols.push_back(left_cols[m]);
for(int m = 0; m < 15; ++m) if((maskR >> m) & 1) S_cols.push_back(right_cols[m]);
bool flag = R[64][S_cols[0]];
vector<bool> M;
for(int p = 0; p < 64; ++p) {
for(int c = 0; c < 16; ++c) {
M.push_back(R[p][S_cols[c]]);
}
}
if(!flag) {
while(!M.empty() && !M.back()) M.pop_back();
if(!M.empty()) M.pop_back();
}
return M;
} else if(left_res[i].first < right_res[j].first) {
i++;
} else {
j++;
}
}
}
return {};
}
