Tokyo Westerns CTF 3rd: Liar's Trap

main.cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <random>
#include <atomic>
#include <boost/multiprecision/cpp_int.hpp>

using namespace std;
namespace mp = boost::multiprecision;
static const int NUM_ITER = 3000000;
static const int K = 25;
static const mp::int512_t P("115792089237316195423570985008687907853269984665640564039457584007913129639747");

template <typename T>
static std::pair<T, T> extended_gcd(const T& a, const T& b){
    if(b == 0){ return std::pair<T, T>(1, 0); }
    const auto p = extended_gcd(b, a % b);
    return std::pair<T, T>(p.second, p.first - a / b * p.second);
}

static mp::int512_t mod_inverse(const mp::int512_t& x, const mp::int512_t& m){
    return (extended_gcd(x, m).first % m + m) % m;
}

inline mp::int512_t modmul(const mp::int512_t& a, const mp::int512_t& b){
    return static_cast<mp::int512_t>(static_cast<mp::int1024_t>(a) * b % P);
}

inline mp::int512_t solve(
    vector<vector<mp::int512_t>>& a, vector<mp::int512_t>& b)
{
    const int n = a.size();
    for(int i = 0; i < n; ++i){
        const auto r = mod_inverse(a[i][i], P);
        for(int j = i; j < n; ++j){
            a[i][j] = modmul(a[i][j], r);
        }
        b[i] = modmul(b[i], r);
        for(int j = i + 1; j < n; ++j){
            if(a[j][i] == 0){ continue; }
            const auto q = a[j][i];
            for(int k = i; k < n; ++k){
                a[j][k] = (a[j][k] - modmul(a[i][k], q) + P) % P;
            }
            b[j] = (b[j] - modmul(b[i], q) + P) % P;
        }
    }
    return b.back();
}

int main(){
    ios_base::sync_with_stdio(false);
    string line;
    getline(cin, line);
    const int m = 100;
    vector<mp::int512_t> y(m);
    for(int i = 0; i < m; ++i){
        cin >> line >> line; // User x:
        cin >> y[i];
    }
    atomic<int> trials(0);
#pragma omp parallel
    {
        random_device device;
        default_random_engine engine(device());
#pragma omp for
        for(int iter = 0; iter < NUM_ITER; ++iter){
            const int current = trials++;
            if(current % 1024 == 0){ cerr << "."; }
            const int n = K;
            vector<int> sel(m);
            for(int i = 0; i < m; ++i){ sel[i] = i; }
            shuffle(sel.begin(), sel.end(), engine);
            vector<vector<mp::int512_t>> a(n, vector<mp::int512_t>(n));
            vector<mp::int512_t> b(n);
            for(int i = 0; i < n; ++i){
                for(int j = 0; j < n; ++j){
                    a[i][n - 1 - j] =
                        mp::powm(mp::int512_t(sel[i] + 1), mp::int512_t(j), P);
                }
                b[i] = y[sel[i]];
            }
            mp::int512_t sec[4];
            sec[0] = solve(a, b);
            for(int i = 1; i < 4; ++i){
                for(int j = 0; j < n; ++j){
                    a[n - 1][n - 1 - j] =
                        mp::powm(mp::int512_t(sel[n + i] + 1), mp::int512_t(j), P);
                }
                mp::int512_t c = y[sel[n + 1]];
                for(int j = 0; j + 1 < n; ++j){
                    const auto t = a[n - 1][j];
                    for(int k = j; k < n; ++k){
                        a[n - 1][k] = (a[n - 1][k] - modmul(a[j][k], t) + P) % P;
                    }
                    c = (c - modmul(b[j], t) + P) % P;
                }
                c = modmul(c, mod_inverse(a[n - 1][n - 1], P));
                sec[i] = c;
            }
            mp::int512_t answer = -1;
            for(int i = 0; i < 4; ++i){
                for(int j = i + 1; j < 4; ++j){
                    if(sec[i] == sec[j]){ answer = sec[i]; }
                }
            }
            if(answer >= 0){
#pragma omp critical
                cout << answer << endl;
            }
        }
    }
    return 0;
}

run.py

import sys
import socket
from subprocess import Popen, PIPE
from selectors import DefaultSelector, EVENT_READ

HOST = 'ppc2.chal.ctf.westerns.tokyo'
PORT = 42453

sock = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
sock.connect((HOST, PORT))

solver = Popen(['./a.out'], stdin=PIPE, stdout=PIPE)

def send_to_solver(fd, mask):
    line = b''
    while True:
        x = sock.recv(1)
        line += x
        if x == b'\n':
            break
    if not line.startswith(b'User'):
        sys.stdout.write('>>>' + line.decode('utf-8').strip() + '\n')
        sys.stdout.flush()
    solver.stdin.write(line)
    solver.stdin.flush()

def send_to_sock(fd, mask):
    line = fd.readline()
    sys.stdout.write('<<<' + line.decode('utf-8').strip() + '\n')
    sys.stdout.flush()
    sock.send(line)

selector = DefaultSelector()
selector.register(sock, EVENT_READ, send_to_solver)
selector.register(solver.stdout, EVENT_READ, send_to_sock)

while True:
    events = selector.select()
    for key, mask in events:
        callback = key.data
        callback(key.fileobj, mask)

run.sh

#!/bin/bash
while :
do
	timeout 23 python3 run.py
	echo
done