The source is kind-of obfuscated, but not too badly. After making things prettier, this is what we came up with:
#!/usr/bin/python from collections import defaultdict as d from itertools import count as c from operator import mul as m def generate_primes(): _b, __b = , d(list) _c = 1 for a in c(): if a < len(_b): _c = _b[a] else: _c += 1 while _c in __b: for b in __b[_c]: __b[_c+b]+=[b] del __b[_c] _c += 1 __b[_c+_c]+=[_c] _b.append(_c) yield _c def prime_factors(n): for _c in generate_primes(): if _c > n: return _d = 0 while n % _c == 0: _d, n = _d + 1, n / _c if _d != 0: yield _c def relative_prime(x, y): # return ___a(x * y) == ___a(y) * ___a(x) from fractions import gcd return gcd(x, y) == 1 def in_bounds(i, j): if not 10000 < i < 100000: return False if not 100 <= j <= 999: return False return True def is_prime(n): import math if n < 2: return False i = 2 while i <= math.sqrt(n): if n % i == 0: return False i += 1 return True def main(): try: c = raw_input('Serial: ').split('-') if len(c) != 6: raise for x in range(0, 6, 2): # c[x] is 5 chars long, c[x+1] is 3 if not in_bounds(int(c[x]),int(c[x+1])): raise # Tests if c[x] is a prime if not is_prime(int(c[x])): raise # Tests whether c[x] and c[x+1] are relative primes if not relative_prime(int(c[x]), int(c[x+1])): raise # c[x] and c[x+1] have to be unique if len([y for y in c if y == c[x]]) > 1: raise if len([z for z in c if z == c[x+1]]) > 1: raise c.reverse() for k in range(7,10): a,b = int(c.pop()),int(c.pop()) for x in [a+b*n for n in range(k)]: if not is_prime(x): raise with open('flag.txt','r') as f: print f.read() except: print 'Bzzt. Wrong!' if __name__ == '__main__': main()
Additionally, one of my teammates discovered a very nice trick to bypass the part that makes sure we entered 3 different sections. The numbers are compared in string form, and so we can prepend a 0 to them and they will appear different. Since int() uses base 10 by default, this isn't a problem in python (other languages may detect octal notation). In the end, we couldn't use this method, it didn't work remotely for some reason.
I wrote this script to brute force a serial:
def serial_test(b, s, k): for x in [b+s*n for n in range(k)]: if not x in big_primes: return False return True def main(): primes = generate_primes() p = primes.next() while p < 10000: p = primes.next() while p < 100000: big_primes.append(p) p = primes.next() for s in range(100, 1000): print s for b in big_primes: if serial_test(b, s, 9): print b, s
This script was rather slow, it took about 2-3 seconds to check a single s value (with k=9). We could have made tons of changes to make it fast, but we decided not to waste time and just ran this in parallel. In the end we found 3 values that work up to k=9, though we only needed k=8 and k=7 for two of these. The resulting serial was: 61637-420-10859-210-10861-840. Sending this to the server resulted in a key: "ThesePrimesAreNotIllegal".
Thanks to AKG and KT, and the whole SpamAndHex (Lite) team. Thanks to the Ghost in the Shellcode team for making this amazing CTF, we had lots of fun.