solve.py

#! /usr/bin/env python3
##
# Script for PicoCTF SmallSign challenge
# Created by Amos (LFlare) Ng
##
import socket
import re
import time

s = socket.socket()
s.connect(("shell2017.picoctf.com", 5596))

def recv_line():
    r = ""
    while "\n" not in r:
        r += s.recv(1).decode()
    print(r)
    return r

def send(o):
    p = str(o) + "\n"
    s.sendall(p.encode())

def prime_factors(n):
    i = 2
    factors = []
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            factors.append(i)
    if n > 1:
        factors.append(n)
    return factors

def gen_primes():
    D = {}
    q = 2
    while True:
        if q not in D:
            yield q
            D[q * q] = [q]
        else:
            for p in D[q]:
                D.setdefault(p + q, []).append(p)
            del D[q]
        
        q += 1

recv_line() # Dump initial response

# Get initial n and e variables
n = int(re.findall("N: ([0-9]+)", recv_line())[0])
e = int(re.findall("e: ([0-9]+)", recv_line())[0])

# Get prime dictionaries
mappings = dict()
timeout = time.time() + 55
for i in gen_primes():
    print("Sending: %d" % i)
    send(i)
    signature = int(re.findall("([0-9]+)", recv_line())[1])
    mappings[i] = signature
    if len(mappings) > 400:
        break

# Get challenge
send(-1)
challenge = int(re.findall("([0-9]+)", recv_line())[1])
print(challenge)

# Do challenge
total = 1
factors = prime_factors(challenge)
print("C: %d" % challenge)
print("Prime Factors: " + "*".join(str(factor) for factor in factors))
for factor in factors:
    total *= mappings[factor]

total = total % n
print("Total: %d" % total)

# Try to submit
send(total)
recv_line()