N1CTF 2018 - MathGame

# Segment between a and b
class Line:
	def __init__(self, a, b):
		self.l, self.m, self.n = b[0] - a[0], b[1] - a[1], b[2] - a[2]
		self.a, self.b = a, b
	def perpendicular(self, b):
		return self.l * b.l + self.m * b.m + self.n * b.n == 0
	def points(self):
		# Just go into parametric form and evaluate. It's ugly but it kinda works
		out = set()
		for t in range(0, 10001):
			x = int(round(self.a[0] + t * self.l / 10000.0))
			y = int(round(self.a[1] + t * self.m / 10000.0))
			z = int(round(self.a[2] + t * self.n / 10000.0))
			out.add((x,y,z))
		return out
	def __repr__(self):
		return str(self.a) + ' -> ' + str(self.b)

#!/usr/bin/python
# -*- coding: utf-8 -*-

from pwn import *
from math import *
from collections import defaultdict
import random, string, hashlib, sys
import sympy, numpy

def captcha():
	line = r.readline()
	while len(line.strip()) == 0:
		line = r.readline().strip()
	base, target = line.split('"')[1::2]
	print 'Solving captcha for', base, target
	
	while True:
		z = ''.join(random.choice(string.ascii_letters) for _ in range(10))
		h = hashlib.sha256(base + z).hexdigest()
		if h.startswith(target):
			r.sendline(z)
			break

def readFace(name):
	print 'Reading face', name
	line = r.readline().strip()
	while line != name:
		line = r.readline().strip()
	
	out = []
	for i in range(7):
		r.readline()
		out.append(map(int, r.readline().strip()[1:-1].split('|')))
	return out

# 90° clockwise
def rotate(face):
	out = []
	for i in range(7):
		row = []
		for j in range(6, -1, -1):
			row.append(face[j][i])
		out += [row]
	return out

def flip(face):
	return face[::-1]

def getFace(a, b, faces, avoid):
	for i in range(6):
		if i == avoid:
			continue
		face = faces[i]
		for _ in range(2):
			for _ in range(4):
				if face[0][0] == a and face[0][6] == b:
					return i, face
				face = rotate(face)
			face = flip(face)
	print "Couldn't get face for", a, b
	quit()

def build(faces):
	nums = set()
	for f in faces:
		for l in f:
			for e in l:
				nums.add(e)
	print 'Nums:', len(nums)
	
	coords = {}
	# Back face
	for i in range(7):
		for j in range(7):
			coords[faces[0][i][j]] = (j, 6 - i, 0)
	
	# Left face
	a, b = faces[0][6][0], faces[0][0][0]
	idx, f = getFace(a, b, faces, 0)
	for i in range(7):
		for j in range(7):
			if f[i][j] in coords:
				assert coords[f[i][j]] == (0, j, i)
			else: coords[f[i][j]] = (0, j, i)
	
	# Right face
	a, b = faces[0][0][6], faces[0][6][6]
	idx, f = getFace(a, b, faces, 0)
	for i in range(7):
		for j in range(7):
			if f[i][j] in coords:
				assert coords[f[i][j]] == (6, 6 - j, i)
			else: coords[f[i][j]] = (6, 6 - j, i)
	
	# Bottom face
	a, b = faces[0][6][0], faces[0][6][6]
	idx, f = getFace(a, b, faces, 0)
	for i in range(7):
		for j in range(7):
			if f[i][j] in coords:
				assert coords[f[i][j]] == (j, 0, i)
			else: coords[f[i][j]] = (j, 0, i)
	
	# Top face
	a, b = faces[0][0][0], faces[0][0][6]
	idx, f = getFace(a, b, faces, 0)
	for i in range(7):
		for j in range(7):
			if f[i][j] in coords:
				assert coords[f[i][j]] == (j, 6, i)
			else: coords[f[i][j]] = (j, 6, i)
	
	# Front face
	a, b = f[6][0], f[6][6]
	idx, f = getFace(a, b, faces, idx)
	for i in range(7):
		for j in range(7):
			if f[i][j] in coords:
				assert coords[f[i][j]] == (j, 6 - i, 6)
			else: coords[f[i][j]] = (j, 6 - i, 6)
	
	return (coords, nums)

# Line between a and b
class Line:
	def __init__(self, a, b):
		self.l, self.m, self.n = b[0] - a[0], b[1] - a[1], b[2] - a[2]
		self.a, self.b = a, b
	def perpendicular(self, b):
		return self.l * b.l + self.m * b.m + self.n * b.n == 0
	def points(self):
		# Just go into parametric form and evaluate. It's ugly but it kinda works
		out = set()
		for t in range(0, 10001):
			f = round#floor if self.l > 0 else ceil
			x = int(f(self.a[0] + t * self.l / 10000.0))
			y = int(f(self.a[1] + t * self.m / 10000.0))
			z = int(f(self.a[2] + t * self.n / 10000.0))
			out.add((x,y,z))
		return out
	def __repr__(self):
		return str(self.a) + ' -> ' + str(self.b)


# Only even, prime and primefactors were actually needed
def even(x): return x % 2 == 0
def prime(x): return sympy.isprime(x)
def pal(x): return str(x) == str(x)[::-1]
def power(x, b):
	p = int(log(x, b) + 0.5)
	return b ** p == x
def perfect(x, p):
	r = x ** (1.0 / p)
	return int(r + 0.5) ** p == x
def primefactors(x): return sympy.primefactors(x)[0] < 10000

checks = [even, prime, pal, primefactors]

for i in range(2, 30):
	checks.append(lambda c: power(i, c))
	checks.append(lambda c: perfect(i, c))

def check(nums, f):
	m = defaultdict(list)
	for e in nums:
		m[f(e)].append(e)
	if len(m) != 2:
		#print 'Fails', m
		return ([], [])
	out = [x for x in m]
	return (m[out[0]], m[out[1]])

def solve(faces):
	coords, nums = build(faces)
	
	for c in checks:
		n = check(nums, c)
		if len(n[0]) == 7 or len(n[1]) == 7:
			print 'Check succedeed:', c
			vals = n[0] if len(n[0]) == 7 else n[1]
			print vals
			
			lines = []
			for i in range(len(vals)):
				for j in range(i):
					lines.append(Line(coords[vals[i]], coords[vals[j]]))
			
			sol = []
			for i in range(len(lines)):
				for j in range(i):
					a, b = lines[i], lines[j]
					if a.perpendicular(b):
						# print 'Perpendicular:', a, b
						pa = a.points()
						pb = b.points()
						inter = [x for x in pa.intersection(pb) if x[0] * x[1] * x[2] > 0 and x[0] < 6 and x[1] < 6 and x[2] < 6]
						# print inter
						sol += inter
			print 'Solutions:', sol
			if len(sol) == 0:
				print 'No solution found'
				# print faces
				quit()
			
			return sol[0]
	
	print 'No solver found'
	print faces
	quit()

if __name__ == "__main__":
	r = remote('47.75.60.212', 11011)
	
	captcha()
	if len(sys.argv) > 1:
		r.interactive()
		quit()
	
	for _ in range(5):
		print "=== Solving level", _, '==='
		
		try:
			faces = [readFace(ch) for ch in 'ABCDEF']
		except:
			print "Nope, failed again :/"
			quit()
		
		sol = solve(faces)
		
		r.recvuntil('x:')
		r.sendline(str(sol[0]))
		r.recvuntil('y:')
		r.sendline(str(sol[1]))
		r.recvuntil('z:')
		r.sendline(str(sol[2]))

	r.interactive()