programming/numbers-2

403 points

Writeup by Aryan

When we connect too the server, we have to solve three types of problems: GCD, LCM, and finding greatest prime factor. All can be solved in sub-linear time with basic algorithms, so we can just automate the process.

import socket

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def lcm(a, b):
    return abs(a * b) // gcd(a, b)

def get_greatest_prime_factor(n):
    if n <= 1: return None
    factor = 2
    while factor * factor <= n:
        if n % factor:
            factor += 1
        else:
            n //= factor
    return n

def main():
    server_address = ('challs.n00bzunit3d.xyz', 10482)
    s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
    s.connect(server_address)

    try:
        while True:
            data = s.recv(1024).decode()
            if not data:
                break
            if 'greatest prime factor' in data:
                number = int(data.split()[-1][:-1])
                answer = get_greatest_prime_factor(number)
                s.sendall(f"{answer}\n".encode())
            elif 'greatest common divisor' in data:
                numbers = data.split()[-3:]
                a, b = int(numbers[0]), int(numbers[2][:-1])
                answer = gcd(a, b)
                s.sendall(f"{answer}\n".encode())
            elif 'least common multiple' in data:
                numbers = data.split()[-3:]
                a, b = int(numbers[0]), int(numbers[2][:-1])
                answer = lcm(a, b)
                s.sendall(f"{answer}\n".encode())
            if 'flag' in data:
                flag = data.split('flag: ')[-1].strip()
                print(f"Flag received: {flag}")
                break
    finally:
        s.close()

if __name__ == "__main__":
    main()

Flag: n00bz{numb3r5_4r3_fun_7f3d4a_8b91aa78c330}