#include <assert.h>
#include <stdio.h>
#include <stdlib.h>

#include <unicorn/unicorn.h>

unsigned char buf[0x100000];
FILE* binary;

uint64_t exgcd(uint64_t a, uint64_t b, uint64_t* x, uint64_t* y) {
  if (b == 0) {
    *x = 1;
    *y = 0;
    return a;
  }
  uint64_t r = exgcd(b, a % b, x, y);
  uint64_t t = *y;
  *y = *x - (a / b) * (*y);
  *x = t;
  return r;
}

void do_emulation(FILE* fp,
                  uint64_t start,
                  uint64_t end,
                  uint64_t r12,
                  uint64_t r13,
                  uint64_t* x,
                  uint64_t* y) {
  uc_engine* uc;
  uint64_t size = end - start;
  uint64_t rsp = 0x280000, rbp = 0x2c0000;

  assert(uc_open(UC_ARCH_X86, UC_MODE_64, &uc) == UC_ERR_OK);
  assert(uc_mem_map(uc, 0x1000, 0x100000, UC_PROT_ALL) == UC_ERR_OK);
  assert(uc_mem_map(uc, 0x200000, 0x100000, UC_PROT_ALL) == UC_ERR_OK);
  assert(fseek(fp, start, SEEK_SET) == 0);
  assert(fread(buf, size, 1, fp) == 1);
  assert(uc_mem_write(uc, start, buf, size) == UC_ERR_OK);
  assert(uc_reg_write(uc, UC_X86_REG_RSP, &rsp) == UC_ERR_OK);
  assert(uc_reg_write(uc, UC_X86_REG_RBP, &rbp) == UC_ERR_OK);
  assert(uc_reg_write(uc, UC_X86_REG_R12, &r12) == UC_ERR_OK);
  assert(uc_reg_write(uc, UC_X86_REG_R13, &r13) == UC_ERR_OK);
  assert(uc_emu_start(uc, start, end, 0, 0) == UC_ERR_OK);
  assert(uc_reg_read(uc, UC_X86_REG_R12, x) == UC_ERR_OK);
  assert(uc_reg_read(uc, UC_X86_REG_R13, y) == UC_ERR_OK);
  uc_close(uc);
}

void solve(uint64_t start,
           uint64_t middle,
           uint64_t end,
           uint64_t x,
           uint64_t y,
           uint64_t* ox,
           uint64_t* oy) {
  uint64_t z, w, s, t;
  uint32_t a, b;
  do_emulation(binary, middle, end, x ^ y, 0, &z, &w);
  do_emulation(binary, start, middle, 1, 0, &s, &t);
  printf("z=%lx w=%lx s=%lx t=%lx\n", z, w, s, t);
  b = (w ^ y) - t;
  uint64_t m, n;
  assert(exgcd(0x100000001, s, &m, &n) == 1);
  a = ((x ^ w) * n) % 0x100000001;
  if (n & (1UL << 63)) {
    a -= 1;
  }
  printf("n=%lx a=%x b=%x\n", n, a, b);
  *ox = a;
  *oy = b;
}

void decrypt(uint32_t xx, uint32_t yy, uint32_t* a, uint32_t* b) {
  uint64_t x = xx, y = yy;
  solve(0x83A25, 0x84C19, 0x92756, x, y, &x, &y);
  solve(0x75467, 0x76695, 0x83A25, x, y, &x, &y);
  solve(0x66ED9, 0x680D2, 0x75467, x, y, &x, &y);
  solve(0x58191, 0x5938A, 0x66ED9, x, y, &x, &y);
  solve(0x4949C, 0x4A68D, 0x58191, x, y, &x, &y);
  solve(0x3AF70, 0x3C19B, 0x4949C, x, y, &x, &y);
  solve(0x2CA30, 0x2DC24, 0x3AF70, x, y, &x, &y);
  solve(0x1E4DE, 0x1F70E, 0x2CA30, x, y, &x, &y);
  solve(0xF7AD, 0x109DB, 0x1E4DE, x, y, &x, &y);
  solve(0x11F4, 0x241A, 0xF7AD, x, y, &x, &y);
  *a = x;
  *b = y;
}

int main() {
  uint32_t x[] = {0xc94dac3e, 0xb2d4f81d, 0xd9c808c2, 0x483a21f1,
                  0x4e9d5687, 0xa3c64916, 0xa7459ba4, 0x6ff8306e};
  uint32_t *a, *b;
  char plain[33];
  int i;
  assert((binary = fopen("./chall", "rb")) != NULL);
  for (i = 0; i < 4; i++) {
    a = (uint32_t*)(plain + 8 * i + 4);
    b = (uint32_t*)(plain + 8 * i);
    decrypt(x[i * 2 + 1], x[i * 2], a, b);
  }
  fclose(binary);
  plain[32] = '\0';
  printf("flag{%s}\n", plain);
  return 0;
}