brute.cpp

#include <vector>
#include <fstream>
#include <array>
#include <cstdint>
#include <iostream>

using u32 = uint32_t;
using u64 = uint64_t;
const auto SECRET = 14810031;
const u32 masks[] = {43, 578, 22079, 142962};
const u32 mask_lengths[] = {6, 10, 15, 18};
const u32 SKIP = 160;

std::array<std::vector<u32>, 4> read_random() {
    // generate stdin with
    /*
def generate_randdata(length):
    masks = [43, 578, 22079, 142962]
    out = []
    for mask in masks:
        rand = Random()
        rand.seed(SECRET + mask)
        out.append([rand.getrandbits(20) for _ in range(length)])
    return out
randdata = generate_randdata(160+200)
with open('randdata', 'w') as f:
    for x in zip(*randdata):
        print(*x, sep='\n', file=f)

     */
    std::array<std::vector<u32>, 4> out;
    u32 x1, x2, x3, x4;
    while (std::cin >> x1 >> x2 >> x3 >> x4) {
        out[0].push_back(x1);
        out[1].push_back(x2);
        out[2].push_back(x3);
        out[3].push_back(x4);
    }
    return out;
}

template<u32 mask, u32 maskLength>
class Lfsr {
public:
    Lfsr(u32 init, std::vector<u32>& random) : init(init), random(random), index(0) {}
    u32 next() {
        u32 r = random[index++];
        u32 nextdata = ((init << 1) & 0xffffff) ^ (mask & r);
        u32 output = 0;
        int i = 31;
        while (0 == (nextdata & (1ULL << i)) && i) {
            i--;
        }
        int h = i/2;
        //std::cout << i << "|" << h << "\n";
        while (i > h) {
            u32 bit = ((1ULL << i) & nextdata) > 0;
            output += bit;
            //std::cout << bit << " ";
            init = nextdata ^ output;
            i -= 2;
        }
        //std::cout << "\n" << nextdata << " "<<output << "\n";
        return output % 2;
    }
private:
    u32 init;
    u32 index;
    std::vector<u32>& random;
};

u32 combine(u32 a, u32 b, u32 c, u32 d) {
    return (a^b)^(a|c)^(b|c)^(c|d);
}

template<u32 mask, u32 maskLength, size_t len>
u64 generate(std::vector<u32>& random, u32 seed) {
    static_assert(len <= 64);
    u64 output = 0;
    Lfsr<mask, maskLength> lfsr(seed, random);
    for (size_t i = 0; i < SKIP; ++i) {
        lfsr.next();
    }
    for (size_t i = 0; i < len; ++i) {
        output = (output << 1) | lfsr.next();
    }
    return output;
}

template<u32 mask, u32 maskLength, size_t len>
std::vector<u64> generate_(std::vector<u32>& random) {
    u32 start = 1 << (maskLength - 1);
    u32 end = 1 << maskLength;
    std::vector<u64> output(end - start);
    for (u32 x = start; x < end; ++x) {
        //std::cerr << x  << " " << end << "\n";
        output[x - start] = generate<mask, maskLength, len>(random, x);
    }
    return output;
}

bool verify_streams(std::vector<bool>& correct, size_t len, u64 x0, u64 x1, u64 x2, u64 x3) {
    for (size_t i = len; i > 0; --i) {
        bool y0 = x0 >> (len - 1);
        bool y1 = x1 >> (len - 1);
        bool y2 = x2 >> (len - 1);
        bool y3 = x3 >> (len - 1);
        auto b = combine(y0, y1, y2, y3);
        if (b != correct[len - i]) 
            return false;
    }
    return true;
}

const size_t len = 56;

void brute(std::array<std::vector<u32>, 4>& random, std::vector<bool>& correct, int start, int end) {
    std::array<std::vector<u64>, 4> streams;
    streams[0] = generate_<43,      6, len>(random[0]);
    std::cerr << "generated 0\n";
    streams[1] = generate_<578,    10, len>(random[1]);
    std::cerr << "generated 1\n";
    streams[2] = generate_<22079,  15, len>(random[2]);
    std::cerr << "generated 2\n";
    streams[3] = generate_<142962, 18, len>(random[3]);
    std::cerr << "generated 3\n";
    std::vector<u32> s(4);

    if (start == -1)
        start = (1<<(mask_lengths[3]-1));
    if (end == -1)
        end = (1<<mask_lengths[3]);

    for (s[3] = start; s[3] < end; ++s[3]) {
        if (s[3] % (1<<8) == 0) {
            std::cerr << s[3] - start << "\n";
        }
        for (s[1] = (1 << (mask_lengths[1]-1)); s[1] < (1 << mask_lengths[1]); ++s[1]) {
            if (s[3] % s[1] != 0)
                continue;
            for (s[0] = (1<<(mask_lengths[0]-1)); s[0] < (1<<mask_lengths[0]); ++s[0]) {
                for (s[2] = (1<<(mask_lengths[2]-1)); s[2] < (1<<mask_lengths[2]); ++s[2]) {
                    u64 x0, x1, x2, x3;
                    x0 = streams[0][s[0] - (1<<(mask_lengths[0]-1))];
                    x1 = streams[1][s[1] - (1<<(mask_lengths[1]-1))];
                    x2 = streams[2][s[2] - (1<<(mask_lengths[2]-1))];
                    x3 = streams[3][s[3] - (1<<(mask_lengths[3]-1))];
                    if (verify_streams(correct, len, x0, x1, x2, x3)) {
                        std::cout << "\nFound: " << s[0] << " " << s[1] << " " << s[2] << " " << s[3] << "\n";
                    }
                }
            }
        }
    }
}

int main(int argc, char* argv[]) {
    auto rand = read_random();
    std::vector<bool> correct;
    {
        std::ifstream f("rem_data");
        for (size_t i = 0; i < len; ++i) {
            char c;
            f >> c;
            correct.push_back(c == '1');
        }
    }
    int start = -1, end = -1;
    if (argc >= 3) {
        start = std::stoi(argv[1]);
        end = std::stoi(argv[2]);
    }
    brute(rand, correct, start, end);
}