Yet another key extraction challenge (C++)

[dila]

Congrats ArC for getting the key(s).

I forgot to post my solution program here before:

#include <iostream>
#include <sstream>
#include <stdint.h>
#include <vector>
#include <set>

int main(int argc, char* argv[])
{
  /* identity matrix */
  int bits[64][64] = {0};
  for (int i = 0; i < 64; ++i) {
    bits[i][i] = 1;
  }

  /* build the parity check matrix */
  uint32_t s = 0;
  for (int i = 0; i < 10000; ++i) {
    s = s * 1664525 + 1013904223;
    int j = s % 64;
    for (int i = 0; i < 64; ++i) {
      int t = bits[0][i];
      bits[0][i] ^= bits[j][i];
      bits[j][i] ^= t;
    }
  }

  /* right-hand side "known" vector */
  uint64_t r = 0x3141592653589793 ^ 0x1221777f1c3e4341;
  int rv[64] = {0};
  for (int i = 0; i < 64; ++i) {
    rv[i] = (r >> i) & 1;
  }

  /* initialize row permutation lookup table */
  int p[64] = {0};
  for (int i = 0; i < 64; ++i) {
    p[i] = i;
  }

  /* run gaussian elimination */
  std::set<int> bf;
  std::set<int> pbf;
  for (int i = 0; i < 64; ++i) {
    bool ok = false;
    for (int j = i; j < 64; ++j) {
      if (bf.find(p[j]) != bf.end()) {
        continue;
      }
      if (bits[p[j]][i]) {
        int t = p[i];
        p[i] = p[j];
        p[j] = t;
        ok = true;
        break;
      }
    }
    if (!ok) {
      /* system is singular */
      /* reduce it from an NxN system to a (N-1)x(N-1) system */
      pbf.insert(p[i]); /* brute force this bit later */
      bf.insert(i);
      continue;
    }
    for (int j = i+1; j < 64; ++j) {
      if (pbf.find(p[j]) != pbf.end()) {
        continue;
      }
      if (bits[p[j]][i]) {
        for (int k = 0; k < 64; ++k) {
          bits[p[j]][k] ^= bits[p[i]][k];
        }
        rv[p[j]] ^= rv[p[i]];
      }
    }
  }

  std::vector<int> bfv;
  bfv.insert(bfv.end(), bf.begin(), bf.end());

  /* back-substitute to solve */
  std::set<int> solved;
  int bf_max = 1 << bf.size();
  for (int bfc = 0; bfc < bf_max; ++bfc) {
    int v[64] = {0};
    for (size_t i = 0; i < bfv.size(); ++i) {
      v[bfv[i]] = (bfc >> i) & 1; /* insert the bits we are brute forcing */
      solved.insert(bfv[i]);
    }
    for (int i = 0; i < 64; ++i) {
      int j = 64 - i - 1;
      if (bf.find(j) != bf.end()) {
        continue; /* we are guessing this */
      }
      int s = -1;
      int t = rv[p[j]];
      for (int k = 0; k < 64; ++k) {
        if (bits[p[j]][k]) {
          if (solved.find(k) != solved.end()) {
            t ^= v[k];
          } else {
            s = k;
          }
        }
      }
      if (s != -1) {
        /* solved one bit */
        v[s] = t;
        solved.insert(s);
      }
    }

    /* copy the solution to an int */
    uint64_t sol = 0;
    for (int i = 0; i < 64; ++i) {
      sol |= (uint64_t(v[i]) << i);
    }

    /* run the original algorithm */
    uint64_t key = sol;
    uint32_t s = 0;
    for (int i = 0; i < 10000; ++i) {
      s = s * 1664525 + 1013904223;
      int j = s % 64;
      uint64_t a = (key >> j) & 1;
      uint64_t b = (key & 1) << j;
      key ^= a ^ b;
    }

    /* test the soluton */
    r = key ^ 0x1221777f1c3e4341;
    if (r == 0x3141592653589793) {
      std::cout << std::hex << sol << std::endl;
    }

    /* repeat to find all keys */
    solved.clear();
  }

  return 0;
}