wgmy2020_lcg_solver.py

#!/usr/bin/env python3
from pwn import remote
import sys

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, x, y = egcd(b % a, a)
        return (g, y - (b // a) * x, x)

def modinv(b, n):
    g, x, _ = egcd(b, n)
    if g == 1:
        return x % n

def crack_multiplier(states, modulus):
    return (states[2] - states[1]) * modinv(states[1] - states[0], modulus) % modulus

def crack_increment(states, modulus, multiplier):
    return (states[1] - states[0] * multiplier) % modulus

def main():
    try:
        modulus = 11760071327054544317

        conn = remote('159.89.198.90', 2000)

        # get the output from the connection
        # split into lines, select line at index 5
        # get only the numbers in that line and split them by ,
        # map the numbers into int and convert the map into list
        states = list(map(int, conn.recv().decode().split('\n')[5][16:].split(',')))

        multiplier = crack_multiplier(states, modulus)

        increment = crack_increment(states, modulus, multiplier)

        for i in range(1000):
            last_state = states[len(states) - 1]

            next_state = (last_state * multiplier + increment) % modulus

            states.append(next_state)

            # need to modulo with 10000, refer to original server.py
            answer = str(next_state % 10000) + '\r\n'

            conn.send(answer.encode())

            res = conn.recv().decode().strip()

            print(res)

    except TypeError:
        # sometimes error will occur, so we have to re-do the process
        return main()

try:
    main()
except KeyboardInterrupt:
    sys.exit()