読者です 読者をやめる 読者になる 読者になる

math314のブログ

主に競技プログラミング,CTFの結果を載せます

SECCON CTF 2013 Online

チーム : 竹田氏 で出ていました。 ところで竹田氏って誰ですか。

7位、3700ptです、予選通るのかな?

crypt100,200,300,400,500を解きました。

crypt 100

ボーリングのスコアを計算する。 hint 3,4がないと難しかった。

スコアを計算するpythonスクリプト拾ってきて、少し改造して通した。

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

import subprocess  # Python 2.4以上が必要
import os

def read(stdout):
  line = ""
  while True:
    r = stdout.read(1)  # 改行を含んで行を読み込む
    if not r:
      break
    line += r
    if r == "=":
      line = line[:-1]
      stdout.read(1)
      break
  line = line.rstrip()
  return line


def solve(line):
  cur = 0
  ret = []
  dt = {'G':0,'0':0,'1':1,'2':2,'3':3,'4':4,'5':5,'6':6,'7':7,'8':8,'9':9,'X':10,'-':0}
  last = 0
  for i in xrange(10):
    last = 0
    x = line[cur]
    cur += 1
    ppp = dt[x]
    last += 1
    if x == 'X':
      ret.append(10)
      continue
    else:
      ret.append(ppp)

    x = line[cur]
    last += 1
    cur += 1
    if x == '/':
      ret.append(10 - ppp)
      continue
    ppp = dt[x]
    ret.append(ppp)

  if cur == len(line) - 1:
    last += 1
    x = line[cur]
    ret.append(dt[x])
    cur += 1
  elif cur == len(line) - 2:
    last += 2
    x = line[cur]
    ret.append(dt[x])
    cur += 1
    y = line[cur]
    if y == '/':
      ret.append(10 - dt[x])
    else:
      ret.append(dt[y])
    cur += 1


  print ret,last
  return calc_score(ret,last == 3)

def calc_score(points,b):
  if len(points) <= 3 and b: return sum(points)
  if len(points) <= 2: return sum(points)
  if points[0] == 10:
    return sum(points[:3]) + calc_score(points[1:],b)
  elif points[0] + points[1] == 10:
    return sum(points[:3]) + calc_score(points[2:],b)
  else:
    return sum(points[:2]) + calc_score(points[2:],b)

print solve("819-166-4/15X3-7245")
print solve("XXXXXXXXXXXX")
print solve("XXXXXXXXX23") # 252
print solve("XXXXXXXXX7/X") # 277


os.environ['PATH'] = "/bin:/usr/bin"  # PATHが使用されるので、必要に応じて指定

cwd = "./"  # 作業ディレクトリ
cmdline = "nc calculateit.quals.seccon.jp 45105"  # スペースやタブで区切る
#cmdline = "for ((i = 1; i <= 5; i++)); do echo $i; sleep 1; done"  # 別の例
p = subprocess.Popen(cmdline, shell=True, cwd=cwd, stdin=subprocess.PIPE,
                     stdout=subprocess.PIPE, stderr=subprocess.STDOUT,
                     close_fds=True)
(stdout, stdin) = (p.stdout, p.stdin)  # ファイルオブジェクト


print "-" * 80  # 区切り表示(開始)
anses = []
while True:
  line = read(stdout)
  print line  # 後ろの改行を消して出力
  if line == "The total score":
    p.stdin.write(str(sum(anses)) + "\n")
    continue
  elif line == "The hi score":
    p.stdin.write(str(max(anses)) + "\n")
    continue
  elif line.startswith("The l"):
    p.stdin.write(str(min(anses)) + "\n")
    print read(stdout)
    print read(stdout)
    print read(stdout)
    print read(stdout)

    continue

  ans = solve(line)
  print "ans",ans
  anses.append(ans)
  p.stdin.write(str(ans) + "\n")



print "-" * 80  # 区切り表示(終了)
ret = p.wait()  # 戻り値が入る
print "Return code: %d" % ret

crypt 200

数独を解くだけ 昔書いたプログラムを改造したのでC++

#define _USE_MATH_DEFINES
#define _CRT_SECURE_NO_DEPRECATE

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <cfloat>
#include <ctime>
#include <cassert>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <numeric>
#include <list>
#include <iomanip>


using namespace std;
typedef long long ll;
const int MODULO = 1000000007;
const int INF = 100000000; //1e8

typedef long long ll;
typedef pair<int, int> Pii;
typedef pair<ll, ll> Pll;
typedef complex<double> Cd;

#define FOR(i,n) for(int i = 0; i < (n); i++)
#define sz(c) ((int)(c).size())

int t[9][9];

bool isOK(int h, int w) {
    bool x[10] = {};
    FOR(i, 9) if (t[h][i]) {
        if (x[t[h][i]]) return false;
        x[t[h][i]] = true;
    }
    memset(x, 0, sizeof(x));
    FOR(i, 9) if (t[i][w]) {
        if (x[t[i][w]]) return false;
        x[t[i][w]] = true;
    }
    memset(x, 0, sizeof(x));
    int y = (h / 3) * 3, z = (w / 3) * 3;
    FOR(i, 3)FOR(j, 3) {
        if (t[y + i][z + j]) {
            if (x[t[y + i][z + j]]) return false;
            x[t[y + i][z + j]] = true;
        }
    }
    return true;
}

int dfs(int d) {
    if (d == 81) return 1;
    if (t[d / 9][d % 9]) return dfs(d + 1);
    int ans = 0;
    for (int i = 1; i <= 9; i++) {
        t[d / 9][d % 9] = i;
        if (isOK(d / 9, d % 9))
            ans += dfs(d + 1);
    }
    t[d / 9][d % 9] = 0;
    return ans;
}

int main() {
    //freopen("sudoku.txt", "r", stdin);
    int ans = 0;
    string s;
    while (!cin.eof()) {
        int cur = 0;
        vector<Pii> Xpts;
        for (int i = 0; i < 14; i++) {
            getline(cin, s);
            if (i == 0) continue;
            if (i == 1) continue;
            if (i == 5) continue;
            if (i == 9) continue;
            if (i == 13) continue;
            for (int j = 0; j < 9; j++) {
                int x = 3 + j * 2;
                t[cur][j] = s[x] - '0';
                if (s[x] == '.') t[cur][j] = 0;
            }
            cur++;
        }
        printf("X is = ");
        int X;
        getline(cin, s);
        sscanf(s.c_str(),"%d",&X);
        FOR(i, 9) FOR(j, 9) if(t[i][j] == 40) {
            t[i][j] = X;
        }
            int ans = dfs(0);
            cout << ans << endl;
    }

    cout << endl << "answer is " << ans << endl;

    return 0;
}

crypt 300

楕円曲線暗号(ECC)を解くと良い、"ecc implemention python"とかで調べて出てきたコードを改造した。 https://gist.github.com/bellbind/1414867 ただしmod_inverseの処理が重かったのでそこは改造。

本来ECCでの逆元を求めるのは困難だが、今回は法pが小さいので、全列挙出来て逆元も簡単に見つかる。

問題やるまでECC名前しか知らなかったので色んなページ検索してお勉強した。

#coding=utf-8
# Basics of Elliptic Curve Cryptography implementation on Python

import collections

def mod_inv_list(p):
    inverse = [0] * p
    inverse[1] = 1;
    for i in xrange(2,p): inverse[i] = (p - p / i) * inverse[p%i] % p;
    return inverse;

class EC(object):
    """System of Elliptic Curve"""
    def __init__(self, a, b, q):
        """elliptic curve as: (y**2 = x**3 + a * x + b) mod q
        - a, b: params of curve formula
        - q: prime number
        """
        assert 0 < a and a < q and 0 < b and b < q and q > 2
        assert (4 * (a ** 3) + 27 * (b ** 2))  % q != 0
        self.a = a
        self.b = b
        self.q = q
        # just as unique ZERO value representation for "add": (not on curve)
        self.zero = (0, 0)
        self.inv = mod_inv_list(q)

    def is_valid(self, p):
        if p == self.zero: return True
        l = (p[1] ** 2) % self.q
        r = ((p[0] ** 3) + self.a * p[0] + self.b) % self.q
        return l == r

    def neg(self, p):
        """negate p
        >>> assert ec.is_valid(ec.neg(p))
        """
        return (p[0], -p[1] % self.q)

    def add(self, p1, p2):
        """<add> of elliptic curve: negate of 3rd cross point of (p1,p2) line
        >>> d = ec.add(a, b)
        >>> assert ec.is_valid(d)
        >>> assert ec.add(d, ec.neg(b)) == a
        >>> assert ec.add(a, ec.neg(a)) == ec.zero
        >>> assert ec.add(a, b) == ec.add(b, a)
        >>> assert ec.add(a, ec.add(b, c)) == ec.add(ec.add(a, b), c)
        """
        if p1 == self.zero: return p2
        if p2 == self.zero: return p1
        if p1[0] == p2[0] and (p1[1] != p2[1] or p1[1] == 0):
            # p1 + -p1 == 0
            return self.zero
        if p1[0] == p2[0]:
            # p1 + p1: use tangent line of p1 as (p1,p1) line
            l = (3 * p1[0] * p1[0] + self.a) * self.inv[2 * p1[1] % self.q] % self.q
            pass
        else:
            l = (p2[1] - p1[1]) * self.inv[(p2[0] - p1[0]) % self.q] % self.q
            pass
        x = (l * l - p1[0] - p2[0]) % self.q
        y = (l * (p1[0] - x) - p1[1]) % self.q
        return (x, y)

    def mul(self, p, n):
        """n times <mul> of elliptic curve
        >>> m = ec.mul(p, n)
        >>> assert ec.is_valid(m)
        >>> assert ec.mul(p, 0) == ec.zero
        """
        r = self.zero
        m2 = p
        # O(log2(n)) add
        while 0 < n:
            if n & 1 == 1:
                r = self.add(r, m2)
                pass
            n, m2 = n >> 1, self.add(m2, m2)
            pass
        # [ref] O(n) add
        #for i in range(n):
        #    r = self.add(r, p)
        #    pass
        return r

    def order(self, g):
        """order of point g
        >>> o = ec.order(g)
        >>> assert ec.is_valid(a) and ec.mul(a, o) == ec.zero
        >>> assert o <= ec.q
        """
        assert self.is_valid(g) and g != self.zero
        for i in range(1, self.q + 1):
            if self.mul(g, i) == self.zero:
                return i
            pass
        raise Exception("Invalid order")
    pass

def test():
    ec = EC(1234577,3213242,7654319)
    g = (5234568,2287747)
    Pk = (2366653,1424308)
    CR1 = (5081741,6744615)
    CR2 = (610619,6218)

    # ec.is_valid(g)
    # ec.is_valid(Pk)
    # ec.is_valid(CR1)

    Z = g
    idx = 1
    while Z != CR1:
        idx += 1
        Z = ec.add(Z,g)

    alpha = idx

    print alpha
    plain = ec.add(CR2,ec.neg(ec.mul(Pk, alpha)))
    print plain
    print sum(plain)
    # print len(v)

test()

crypt 400

oxで遊ぶ問題 pythonで書こうとしたら"too slow"と煽られて辛かったのでC++

#define _USE_MATH_DEFINES
#define _CRT_SECURE_NO_DEPRECATE

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <cfloat>
#include <ctime>
#include <cassert>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <numeric>
#include <list>
#include <iomanip>


using namespace std;
typedef long long ll;
const int MODULO = 1000000007;
const int INF = 100000000; //1e8

typedef long long ll;
typedef pair<int, int> Pii;
typedef pair<ll, ll> Pll;
typedef complex<double> Cd;

#define FOR(i,n) for(int i = 0; i < (n); i++)
#define sz(c) ((int)(c).size())

struct F {
    int ocnt, xcnt;
    bool hash_comp;
    int hash;
};

int H, W;
vector<F> frow,fcol;
vector<string> gvs;
char chash[1 << 20];
char rhash[1 << 20];

bool is_vaild() {
    FOR(i, H) {
        int cont = 0;
        char last = 'P';
        FOR(j, W) {
            if (last == gvs[i][j]) {
                cont++;
            } else {
                cont = 1;
                last = gvs[i][j];
            }
            if (cont >= 3 && gvs[i][j] != '.') {
                return false;
            }
        }
    }
    FOR(j, W) {
        int cont = 0;
        char last = 'P';
        FOR(i, H) {
            if (last == gvs[i][j]) {
                cont++;
            } else {
                cont = 1;
                last = gvs[i][j];
            }
            if (cont >= 3 && gvs[i][j] != '.') {
                return false;
            }
        }
    }
    return true;
}

bool check_info(int h, int w) {
    const char c = gvs[h][w];
    if (c == 'o') {
        if (frow[h].ocnt > W / 2) return false;
        if (fcol[w].ocnt > H / 2) return false;
    } else {
        if (frow[h].xcnt > W / 2) return false;
        if (fcol[w].xcnt > H / 2) return false;
    }
    if (w == W - 1) { if (rhash[frow[h].hash] >= 2) return false; }
    if (h == H - 1) { if (chash[fcol[w].hash] >= 2) return false; }
    return true;
}

void add_info(int h, int w) {
    const char c = gvs[h][w];
    int hash_add = c == 'o';
    if (c == 'o') {
        frow[h].ocnt++;
        fcol[w].ocnt++;
    } else {
        frow[h].xcnt++;
        fcol[w].xcnt++;
    }
    frow[h].hash = frow[h].hash * 2 + hash_add;
    fcol[w].hash = fcol[w].hash * 2 + hash_add;
    if (w == W - 1) rhash[frow[h].hash]++, frow[h].hash_comp = true;
    if (h == H - 1) chash[fcol[w].hash]++, fcol[w].hash_comp = true;
}

void rem_info(int h, int w) {
    const char c = gvs[h][w];
    if (c == 'o') {
        frow[h].ocnt--;
        fcol[w].ocnt--;
    } else {
        frow[h].xcnt--;
        fcol[w].xcnt--;
    }
    if (w == W - 1) rhash[frow[h].hash]--, frow[h].hash_comp = false;
    if (h == H - 1) chash[fcol[w].hash]--, fcol[w].hash_comp = false;
    frow[h].hash /= 2;
    fcol[w].hash /= 2;
}

bool dfs(int id) {
    if (id == H * W) {
        return true;
    }
    int h = id / W, w = id % W;
    char prv = gvs[h][w];
    char d[] = "ox";
    FOR(k, 2) {
        if (prv != '.' && prv != d[k]) continue;
        gvs[h][w] = d[k];
        add_info(h, w);
        bool ok = check_info(h, w);
        bool b = false;
        if (ok && is_vaild()) {
            b = dfs(id + 1);
        }
        if (b) return true;
        rem_info(h, w);
    }
    gvs[h][w] = prv;
    return false;
}



void solve1() {
    int x;
    scanf("Question %d [%d,%d]",&x,&H,&W);
    string tmp;
    getline(cin, tmp);
    FOR(i,H){
        getline(cin, tmp);
        gvs.push_back(tmp);
    }

    bool ok = is_vaild();
    frow = vector<F>(H);
    fcol = vector<F>(W);
    assert(ok);
    dfs(0);

    FOR(i,sz(gvs)) cout << gvs[i] << endl;
}


int main() {
    solve1();

    return 0;
}

これをpythonを使ってncに流した。ちょっとpythonのコードがきれいになってきてる

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

from subprocess import Popen,STDOUT,PIPE # Python 2.4以上が必要
import os

def next_line(stdout):
  line = ""
  while True:
    r = stdout.read(1)
    if r == '\n':
      break
    line += r
  print line
  return line


os.environ['PATH'] = "/bin:/usr/bin:."  # PATHが使用されるので、必要に応じて指定

cwd = "./"  # 作業ディレクトリ
cmdline = "nc 133.242.18.173 12321"  # スペースやタブで区切る
p = Popen(cmdline, shell=True, cwd=cwd, stdin=PIPE,
  stdout=PIPE, stderr=STDOUT,close_fds=True)

print "-" * 80  # 区切り表示(開始)

while True:
  line = next_line(p.stdout)
  if line.startswith("Question 0"):
    continue

  if line.startswith("Question"):
    # solve question
    H,W = [int(i) for i in line.split()[-1][1:-1].split(',')]
    c41 = Popen('./crypt41', shell=True, cwd=cwd, stdin=PIPE,
      stdout=PIPE, stderr=STDOUT,close_fds=True)
    line += "\n"
    for l in xrange(H):
      line += next_line(p.stdout) + "\n"

    print "solve"
    print line

    c41.stdin.write(line)
    c41.wait()
    w = c41.stdout.read()

    print "solved"
    print w

    p.stdin.write(w)



print "-" * 80  # 区切り表示(終了)
ret = p.wait()  # 戻り値が入る
print "Return code: %d" % ret

crypt 500

暗号を解く問題 decryptoに投げましょう http://www.blisstonia.com/software/WebDecrypto/index.php と思ったけど流石に投げるのはアレだと思ってjar落として実行!

ところがCTF用のubuntuVMにjavaが入ってない、apt-get ... とあたふたしていた 後jar作りなおしたりしてたら変なエラーが出てきて、仕方ないのでソース落として改造してjar作り直し。

無駄な労力を使った。 にも関わらず、空白の場所を見つけるオプションが働いてくれずにstage12のみ運任せの実装になった。 stage1-5,11は単語の頻度解析するだけで通ったのでdecryptoに頼ってない、自力実装。 この実装には https://github.com/masayu-a/NAIST-edic にある checked.txt を使用した。

stage6-10はdecryptoに投げた。 stage12はアルファベットに頻度解析のみで通した。 'a'は3番目くらいに出てくる頻度が高い。 http://en.wikipedia.org/wiki/Letter_frequency

一回で当たる確率が 5/26だとすると,22回stage12に到達するまでに、99%解答を見つけられる事になる。 CTFのサーバ大丈夫かなーと心配だった

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

from subprocess import Popen,STDOUT,PIPE # Python 2.4以上が必要
import os
import time

def next_line(stdout):
  line = ""
  while True:
    r = stdout.read(1)
    if r == '\n':
      break
    line += r
  print line

  return line[:-1]

def ca(x,rot):
  al = list('abcdefghijklmnopqrstuvwxyz')
  au = list('ABCDEFGHIJKLMNOPQRSTUVWXYZ')
 
  if x in al: 
    return al[(al.index(x)+rot)%(len(al))]
  if x in au: 
    return au[(au.index(x)+rot)%(len(au))]

  return x

def caeser_decode(text,rot):
    return "".join([ca(c,rot) for c in text])

dl = [l.split("\t")[0] for l in file("checked.txt")]


def hu(s,rot):
  val = caeser_decode(s,rot).lower()
  pt = 0
  for l in dl:
    pt += val.count(l)
  return pt,chr(ord('a')+((26-rot)%26)),val

def solve1(s):
  values = [hu(s,rot) for rot in xrange(26)]
  pt = 0
  ans = None
  for i,k,val in values:
    if pt < i:
      pt = i
      ans = (k,val)

  print pt,ans
  return ans[0]

def solve3(s):
  values = [hu(s,rot) for rot in xrange(26)]
  pt = 0
  ans = None
  for i,k,val in values:
    if pt < i:
      pt = i
      ans = (k,val)

  print pt,ans
  return ans[0]

import random
def solve4(s):
  s = s.lower()
  x = [(s.count(i),i) for i in 'abcdefghijklmnopqrstuvwxyz']
  x.sort(reverse=True)
  print x[:5]
  v = random.randint(2,6)
  return x[v][1]

def solve2(s):
  s = s.replace("\n"," ");

  # #from cache
  # f = open("cache.txt","r")
  # for l in f:
  #   print l
  #   i = l.split(":-:")
  #   print i
  #   if i[0] == s:
  #     print "--- cache ---"
  #     j = i[1][1:-2].split(', ')[0][1:-1]
  #     return j
  # f.close()

  f = open("cur.pzl","w")
  f.write(s)
  f.close()
  os.popen('java -jar dec.jar --timelimit 2.0 --puzzlefile cur.pzl > out.result')
  f = open("out.result","r")
  ans = ""
  for l in f:
    if l.startswith("<script>solsum("):
      #print l
      ans = ",".join(l.split(',')[2:])[1:-13].lower()
      break
  ans = ans.replace("&nbsp","")

  print len(s),len(ans)
  print "src is : ", s
  print "ans is : ", ans
  ret = ""
  st = set('abcdefghijklmnopqrstuvwxyz')
  for i in xrange(min(len(s),len(ans))):
    if ans[i] == 'a': return s[i].lower()
    elif ans[i] in st:
      st.remove(ans[i])

  return list(st)[0]
# solve1("""Jogpsnbujpo Sfrvftu (uzqf 15). Uijt nfttbhf jt opx pctpmfuf cvu ju xbt psjhjobmmz vtfe up sfrvftu dpogjhvsbujpo jogpsnbujpo gspn bopuifs efwjdf.
# Uijt wfstjpo sfmfbtfe cz Uzf NdRvffo (iuuq://qfsmnpolt.psh/?opef=uzf).
# Bu qsftfou uifsf jt op xbz up gbjm.""")


# solve1("""Rityzmv::Kri nzcc rcjf jlggfik tfdgivjjvu fi xqzggvu kri wzcvj.
# Dlckzgifkftfc Crsvc Jnzktyzex (kpgv 0o8847).
# Ivkliej kyv ivjlckj rj r czjk ze kyv rsfmv fiuvi.""")

def test2():

  print solve2("""Aqie tjepzimje lvj lz ylzj gkvhrkhje aqka kzj rejt iv aqj okzikva.
  Eja lz zjazijoj aqj jbazk givdjz ngkhe. Zjarzve kv kzzkwzjn ln ngkhe.
  Vl ewymlgip plveakvae kzj zjsrizjt mw aqie IL::Rvplyczjee::Hrvxic ka czjejva.""")

  #print solve2("""This describes one or more languages that are used in the variant. Set or retrieve the extra linker flags. Returns an arrayref of flags. No symbolic constants are required by this IO::Uncompress::Gunwip at present.""")

  print solve2("""JxqWqrku::BpvjBpvjt dit qfj pcprkpykj pqqtrywqju.
  Tjqwtau qfj qiqpk awbyjt id yeqju zibmtjuujg yeqju ramwq qi radkpqj.
  Ajqzpq (it pae iqfjt rbmkjbjaqpqria), Azpq ru biuq gjdrarqjke ypujg ia Ajqzpq ra umrtrq pag dwazqriapkrqe.""")

def main():

  print "-" * 80  # 区切り表示(開始)

  os.environ['PATH'] = "/bin:/usr/bin:."  # PATHが使用されるので、必要に応じて指定

  cwd = "./"  # 作業ディレクトリ
  cmdline = "telnet 133.242.50.48 65437"
  p = Popen(cmdline, shell=True, cwd=cwd, stdin=PIPE,
    stdout=PIPE, stderr=STDOUT,close_fds=True)

  while True:
    line = next_line(p.stdout)
    if line.startswith("***"):
      solver = None
      XX = int(line.split()[2])
      if XX <= 5:
        solver = solve1
      elif XX <= 10:
        solver = solve2
      elif XX <= 11:
        solver = solve3
      else:
        solver = solve4
        
      sln = ""
      while True:
        line = next_line(p.stdout)
        if line == "": break
        sln += line + ' '
      ans = solver(sln)
      print "ans is '%s'" % ans
      p.stdin.write(ans)
      p.stdin.write('\n')
      #p.stdin.flush()
      veve = ""
      veve += next_line(p.stdout)
      veve += next_line(p.stdout)
      print veve
      if " Good job" not in veve:
        return False

      if XX == 12:
        
        v = p.stdout.read()
        print v
        if "Wrong answer" in v:
          return False
        else:
          return True
          print "answer" , v
          print "answer" , v
          print "answer" , v
          print "answer" , v

#test2()
while True:
  if main(): break
  time.sleep(30)