Snippets
Created by
Masafumi Yabu
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 | //
// Created by nomeaning on 2/24/18.
//
#include <iostream>
#include <cstdint>
#include <vector>
using namespace std;
const int M = 10; // 入力数
uint32_t vs[M][2] = {{1781623155, 1950693744}, {1163420792, 1415932486}, {1379489906, 1735677043}, {1248945014, 1282699074}, {1145525059, 1869035876}, {1985170249, 1649043810}, {2000243553, 1783645803}, {1665291573, 1312312901}, {1683317838, 1313697141}, {1365789552, 1732340020}};
int data[M][657] =
#include "data.hpp"
;
const uint32_t delta = 0x9e3779b9;
void solve_single(vector<uint32_t> &ret, const vector<uint32_t> &vs, uint32_t ham, uint32_t col_idx, int shift, uint32_t k) {
bool ok = true;
for(int i = 0; i < vs.size(); i++) {
uint32_t v = vs[i];
if (shift >= 0) {
v = v << shift;
} else {
v = v >> (-shift);
}
uint32_t v2 = (v + k);
if (__builtin_popcountll(v ^ v2) != data[i][col_idx]) {
ok = false; break;
}
}
if (ok) {
ret.push_back(k);
}
}
void dfs(vector<uint32_t> &ret, const vector<uint32_t> &vs, uint32_t ham, uint32_t col_idx, int shift, int pos, int h = 0, uint32_t cur = 0) {
if (pos == 32) {
solve_single(ret, vs, ham, col_idx, shift, cur);
} else {
if (h + (32 - pos) < ham) {
return;
}
if (h < ham) {
dfs(ret, vs, ham, col_idx, shift, pos + 1, h + 1, cur | (1u << pos));
}
dfs(ret, vs, ham, col_idx, shift, pos + 1, h, cur);
}
}
vector<uint32_t> solve_single(const vector<uint32_t> &vs, uint32_t ham, uint32_t col_idx, int shift) {
vector<uint32_t> ret;
dfs(ret, vs, ham, col_idx, shift, 0);
return ret;
}
bool check(uint32_t k0, uint32_t k1, uint32_t k2, uint32_t k3) {
vector<uint32_t> v0(M), v1(M);
for (int i = 0; i < M; i++) {
v0[i] = vs[i][0];
v1[i] = vs[i][1];
}
uint32_t sum = 0;
for(int i = 0; i < 32; i++) {
sum += delta;
for (int j = 0; j < M; j++) {
uint32_t v = v1[j] << 4;
uint32_t vt = v + k0;
if (__builtin_popcount(v ^ vt) != data[j][i * 20 + 18]) {
return false;
}
v0[j] += ((v1[j]<<4) + k0) ^ (v1[j] + sum) ^ ((v1[j]>>5) + k1);
v1[j] += ((v0[j]<<4) + k2) ^ (v0[j] + sum) ^ ((v0[j]>>5) + k3);
}
}
return true;
}
void solve_k2_k3(uint32_t k0, uint32_t k1) {
vector<uint32_t> v0(M);
vector<uint32_t> v1(M);
for (int i = 0; i < M; i++) {
v0[i] = vs[i][0];
v1[i] = vs[i][1];
v0[i] += ((v1[i] << 4) + k0) ^ (v1[i] + delta) ^ ((v1[i] >> 5) + k1);
}
auto k2c = solve_single(v0, data[0][12], 26, 4),
k3c = solve_single(v0, data[0][13], 29, -5);
for (auto k2: k2c) {
for (auto k3: k3c) {
// cerr << "Key candidate: " << k0 << ',' << k1 << ',' << k2 << ',' << k3 << endl;
if (check(k0, k1, k2, k3)) {
cout << "Key Found: (" << k0 << ", " << k1 << ", "<< k2 << ", " << k3 << ")" << endl;
}
}
}
}
void solve_k0_k1() {
vector<uint32_t> v1(M);
for (int i = 0; i < M; i++) {
v1[i] = vs[i][1];
}
auto k0c = solve_single(v1, data[0][10], 18, 4),
k1c = solve_single(v1, data[0][11], 21, -5);
#pragma omp parallel for
for(int i = 0; i < k0c.size() * k1c.size(); i++) {
solve_k2_k3(k0c[i % k0c.size()], k1c[i / k0c.size()]);
}
}
int main() {
solve_k0_k1();
}
|
Comments (0)
You can clone a snippet to your computer for local editing. Learn more.