BCTF 2015 experiment

--- English version is here (poor English)---

Hi, we have a short survey with 50 questions. You can get a flag as award once you finished it.
$ nc 104.197.7.111 13135

問題文によれば、50問問題を解けばフラグをくれるらしい。簡単っぽい？

最初の10問は四則演算の結果が整数か否かを答える問題。
次に、

Description: The prime numbers.
The sequence starts with: 2,3,5,7,11,13,17,19,23,29
(first term is for n = 1)
n = 2418, Answer:

のような問題が出されるので、該当する数を答える。
ちなみにはじめ数問は固定の問題だったが途中からは完全にランダムな問題になった。
制限時間はそこそこ長く、1~2分くらい放っておいても大丈夫。

数列をオンライン大数列辞典で検索すると、全く同じDescriptionの数列があることがわかる。
それを元に人力で何度も計算して解いていると、LINKSの欄に計算済みの値が載っていてかつ問題で提示されるnが含まれていることに気づいた。

最後の5問はちょっと形式が変わって、計算済みの値が載っていない問題が出題された。

46問目: 2000万オーバーの順番にある素数
47問目: リストに載っていないカタラン数
48問目: Number of sets of rooted connected graphs where every block is a complete graph.
49問目: Shapes of height-balanced AVL trees with n nodes.
50問目: a(n) = number of partitions of n (the partition numbers) modulo 1000000007

最後の方はなんだかよくわからない。Pari/GPとかMathematicaに式をコピペしてCPUをぶん回した。
46問目

? prime(23338403)
%1 = 439756091

48問目

etr[p_] := Module[{b}, b[n_] := b[n] = If[n == 0, 1, Sum[Sum[d*p[d], {d, Divisors[ j]}]*b[n-j], {j, 1, n}]/n]; b]; b = etr[aa]; c = etr[b]; aa = Function[{n}, If[n == 0, 0, c[n-1]]]; a = etr[aa]; Table[a[n], {n, 0, 700}] 

49問目

a[n_] := Module[{B}, B[x_, y_, d_, a_, b_] := If[a+b <= d, Expand[x+B[x^2+2*x*y, x, d, a+b, a]], x]; Coefficient[B[z, 0, n, 1, 1], z, n]]; 
a[1298]

計算式内にExpandを入れると計算量が減って速く解ける。
これに気づいていなければ永遠に解けなかった。

50問目

? {a(n) = if( n<0, 0, polcoeff( 1 / eta(x + x * O(x^n)), n))};
? a(23370) % 1000000007
%2 = 438545155

以下、コードです

import re
import time
import gmpy
import sympy
import requests
from pwn import *
 
s = remote('104.197.7.111', 13135)
s.recvuntil("Okay, let's begin with simple questions.\n")
 
problem_number = 1
 
for _ in range(10):
    print 'No. %d --------------------------' % problem_number
    x = s.recvuntil('Answer (yes/no): ')
    print x
    m = re.search('Is (.+) an integer or not?', x)
    expr = m.group(1)
    try:
        ans = str(safeeval.expr(expr))
        print expr
        print ans
        if ('.' not in ans) or re.search(r'\.0+$', ans):
            s.send('yes\n')
        else:
            s.send('no\n')
    except:
        s.send('no\n')
    problem_number += 1
 
print s.recvuntil('Time for calculating weird integer sequences.')
 
for i in range(35):
    print 'No. %d --------------------------' % problem_number
    s.recvuntil('Description: ')
    desc = s.recvuntil('\n')[:-1]
 
    buf = s.recv(1)
    seq = None
    if 'T' in buf:
        s.recvuntil('starts with: ')
        seq = s.recvuntil('\n')[:-1]
 
    print 'Description:', desc
    print 'The sequence starts with:', seq
    search = 'name:"%s"' % desc
    if seq and len(seq) < 40:
        search += ' seq:"%s"' % seq
 
    print 'Searching %s' % search
    res = requests.get('http://oeis.org/search', params={'q': search})
 
    m = re.search('<a href="/A([0-9]+)"', res.text)
    num = m.group(1)
    print 'found page:', num
 
    res = s.recvuntil('Answer: ')
    m = re.search(r' = (\d+), ', res)
    n = int(m.group(1))
    print 'n = ', n
 
    res = requests.get('http://oeis.org/A%s/b%s.txt' % (num, num))
    m = re.search('^%d +(-?[0-9]+)' % n, res.text, re.MULTILINE)
    if m is None:
        print 'not found'
        ans = raw_input('Input answer: ')
    else:
        ans = int(m.group(1))
    print 'Answer =', ans
    s.send(str(ans) + '\n')
    problem_number += 1
    time.sleep(0.2)
 
 
print 'No. %d --------------------------' % problem_number
s.recvuntil('Description: ')
desc = '"' + s.recvuntil('\n')[:-1] + '"'
s.recvuntil('The sequence starts with: ')
seq = s.recvuntil('\n')
res = s.recvuntil('Answer: ')
m = re.search(r'n = (\d+), ', res)
n = int(m.group(1))
print 'n = ', n
ans = raw_input('Input answer: ')
print 'Answer =', ans
s.send('%s\n' % ans)
problem_number += 1
 
print 'No. %d --------------------------' % problem_number
s.recvuntil('Description: ')
desc = '"' + s.recvuntil('\n')[:-1] + '"'
s.recvuntil('The sequence starts with: ')
seq = s.recvuntil('\n')
res = s.recvuntil('Answer: ')
m = re.search(r'n = (\d+), ', res)
n = int(m.group(1))
ans = sympy.binomial(2*n, n)/(n+1)
print 'Answer =', ans
s.send('%d\n' % ans)
problem_number += 1
 
s.interactive()

ちなみにこのコードは3回に1回くらいしか完走してくれない、プログラミングは難しい。

BCTF{Y0u_h4ve_m0ar_7ermz_than_205}