X-MAS CTF 2018 Writeup

この大会は2018/12/15 3:00(JST)~2018/12/22 3:00(JST)に開催されました。
今回もチームで参戦。結果は 2768点で1378チーム中62位でした。
自分で解けた問題をWriteupとして書いておきます。

Merry Christmas (Sanity Check 1)

問題にフラグが書いてあった。

X-MAS{HTSP_w1$h3s_y0u_4_m3rRy_Christmas}

Santa's Private Talks Room (Sanity Check 5)

Discordに入ると、generalチャネルにフラグが書いてあった。

X-MAS{d15c0rd_50_c00l_7h47_54n74_u535_17_700}

Santa The Weaver (Misc)

$ strings flag.png | grep X-MAS
X-MAS{S4n7a_l1k3s_h1di()g_gif7$}
X-MAS{S4n7a_l1k3s_h1di()g_gif7$}

Oh Christmas Tree (Forensics)

$ strings Merry\ Christmas.jpg | grep X-MAS
Copyright (c) 1998 Hewlett-X-MAS{0_Chr15tm

フラグが分離しているようだ。

$ strings Merry\ Christmas.jpg | grep as_
IEC as_tr33_1s_th1s_a
$ strings Merry\ Christmas.jpg | grep _ | grep }
IEC _flag_i_wond3r}..
    :
X-MAS{0_Chr15tmas_tr33_1s_th1s_a_flag_i_wond3r}

Santa's Security Levels (Forensics)

Audacityで開き、スペクトグラムを見る。
f:id:satou-y:20181224201446p:plain
モールス信号のようだ。

--. .. - .... ..- -...  -.-. --- --  --. --- --- --- --. .- .-..  -..- -- .- ...
GITHUBCOMGOOOGALXMAS

これはURLを表しているのかも。https://github.com/gooogal/xmasにアクセスしてみる。special message.txtに以下のように書いてある。

anta doesn't like people searching for his flags, but you look like a nice person. 
Anyway here's your flag:

vF ur uNq nAlguvat pbasvqraGvNy gb fnl, ur jebgr Vg ia pvcure, gung vF, ol FB punaTvat gur beqre bs gur Yrggref bs gur nycuNorg, gung abg n jbeQ pbhyq or ZnQR bHg.

https://quipqiup.com/で復号する。

iS he hAd aNything confidenTiAl to say, he wrote It ?n cipher, that iS, by SO chanGing the order of the Letters of the alphAbet, that not a worD could be MaDE oUt.

大文字を並べる。

SANTAISSGLADMDEU
X-MAS{santaissogladmdeu}

Message from Santa (Forensics)

FTK Imagerで開き、[root]-[.Trash-0]-[files]のファイル群をエクスポートする。
パズルを解くように画像を結合していくと、フラグが現れた。
f:id:satou-y:20181224201805p:plain

X-MAS{1t_l00k5_l1k3_s4nta_m4de_4_m1stak3_sorry}

Hanukkah (Crypto)

暗号のパラメータは以下の通り。

r: 256bit, 偶数
p =  3 * r**2 +  2 * r + 7331
q = 17 * r**2 + 18 * r + 1339
n = p * q

privekey = (p, q)
pubkey = n

rの高次方程式を解くことによって、p, qを求める。eが2になっているため、RSA暗号ではなく、Rabin暗号
Rabin暗号を解くと、4パターン復号できるが、その中でフラグの条件にあてはまるものを選択する。

from Crypto.Util.number import long_to_bytes
from sympy import *

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        gcd, y, x = egcd(b % a, a)
        return gcd, x - (b // a) * y, y

pubkey = 577080346122592746450960451960811644036616146551114466727848435471345510503600476295033089858879506008659314011731832530327234404538741244932419600335200164601269385608667547863884257092161720382751699219503255979447796158029804610763137212345011761551677964560842758022253563721669200186956359020683979540809

var('r')
eq = Eq((3 * r**2 +  2 * r + 7331) * (17 * r**2 + 18 * r + 1339) - pubkey)
ans = solve(eq)
r = ans[0]

p = 3 * r**2 +  2 * r + 7331
q = 17 * r**2 + 18 * r + 1339

assert pubkey == p * q
assert p % 4 == 3
assert q % 4 == 3

with open('flag.enc', 'r') as f:
    ct = int(f.read().split(' = ')[1])

r = pow(ct, long((p+1)/4), long(p))
s = pow(ct, long((q+1)/4), long(q))

gcd, c, d = egcd(p, q)
x = (r * d * q + s * c * p) % pubkey
y = (r * d * q - s * c * p) % pubkey
plains = [x, pubkey - x, y, pubkey - y]

for plain in plains:
    flag = long_to_bytes(plain)
    if flag[-1] == 'X':
        print flag.rstrip('X')
        break
X-MAS{H4nukk4h_Rabb1_and_Rab1n_l0ok_4nd_s0und_v3ry_much_alik3_H4nukk4h}

Special Christmas Wishlist (Crypto)

図形を文字に置き換えてみる。

ABCDCEFG AHIJDCEFG KHELG LDJI
JDMBNNG NBODAP QHHRGIFL
KCOA QGGM JABLLGL LGC HN CSH
QBF FHJ SDLFHO CEOQAGML
BFTGICEMGM OEACDCHHA UADV SBCUK
CSDJ OBMLKOBAAHS LRGSGM

途中でquipqiupで復号する。

LATITUDE LONGITUDE HOUSE SIGN
GIRAFFE FAMILY BOOKENDS
HTML BEER GLASSES SET OF TWO
BAD DOG WISDOM TUMBLERS
ADVENTURER MULTITOOL CLIP WATCH
TWIG MARSHMALLOW SKEWER

結構長いので、FLAGの文字を探すことにする。対応付けたNABJがFLAGになる。
すると最後の方にFLAGの文字があることがわかる。

CKG NABJ DL
ZOBLYHEBMGLHJHHFBCLEQLCDCECDHIUDVKGML

この最後の二行だけ復号してみる。

LATITUDE LONGITUDE HOUSE SIGN
GIRAFFE FAMILY BOOKENDS
HTML BEER GLASSES SET OF TWO
BAD DOG WISDOM TUMBLERS
ADVENTURER MULTITOOL CLIP WATCH
TWIG MARSHMALLOW SKEWER
            :
THE FLAG IS
XMASYOUARESOGOODATSUBSTITUTIONCIPHERS
xmasyouaresogoodatsubstitutionciphers

Santa's list (Crypto)

$ nc 95.179.163.167 16001
Ho, ho, ho and welcome back!
Your list for this year:

Sarah - Nice
Bob - Nice
Eve - Naughty
Galf - 9bb1ea1bc3fd26da23bcc981ee043c2882c72521121dc4b2fd1be39ea2bd22887902950b7c6a3c2d58463da517383a2831d00c1b4efac7e157e3a70185bfbf5d606565a4cc7d1d806cb5274353df350852a18f7b78a18d01eb0900e03a5cec37a950027168ed70dea21f84089b67c67b8a9c6e77f65173f6d5e0378e522164be
Alice - Nice
Johnny - Naughty

[1] Encrypt
[2] Decrypt
[3] Exit

スクリプトの概要は以下の通り。

・encrypt
平文(数値)を指定すると、暗号化して表示する。
平文(数値)が使用済みリストに入る。

・decrypt
フラグの暗号文と同じだと復号しない。
encryptで暗号化したものは復号しない。
それ以外は復号結果を表示する。

以下の方針で解く。

encryptでnを算出する。
decrypt側でLSB Decryption Oracle Attackで復号する。
import socket
import re
from fractions import Fraction
from Crypto.Util.number import long_to_bytes

def recvuntil(s, tail):
    data = ''
    while True:
        if tail in data:
            return data
        data += s.recv(1)

def egcd(a, b):
    x,y, u,v = 0,1, 1,0
    while a != 0:
        q, r = b//a, b%a
        m, n = x-u*q, y-v*q
        b,a, x,y, u,v = a,r, u,v, m,n
    gcd = b
    return gcd, x, y

def lsb_oracle(s, enc):
    print '2'
    s.sendall('2\n')
    data = recvuntil(s, '> ')
    print data + enc
    s.sendall(enc + '\n')
    data = recvuntil(s, '\n').strip()
    data += recvuntil(s, '\n').strip()
    print data
    if 'Ho, ho, no...' in data:
        dec = 0
    else:
        dec = data.split('Decrypted: ')[1]
    data = recvuntil(s, 'Exit\n').strip()
    print data

    return int(dec) % 2

s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.connect(('95.179.163.167', 16001))

data = recvuntil(s, 'Exit\n').strip()
print data

#### get c ####
pattern = 'Galf - (.+)'
m = re.search(pattern, data)
c = int(m.group(1), 16)
print 'c =', c

#### calculate n ####
try_rsa_enc = []
for pt in [2, 4, 16]:
    print '1'
    s.sendall('1\n')
    data = recvuntil(s, '> ')
    print data + chr(pt)
    s.sendall(chr(pt) + '\n')
    data = recvuntil(s, '\n').strip()
    data += recvuntil(s, '\n').strip()
    print data
    enc = data.split('Encrypted: ')[1]
    try_rsa_enc.append(int(enc))
    data = recvuntil(s, 'Exit\n').strip()
    print data

diff1 = (try_rsa_enc[0]) ** 2 - try_rsa_enc[1]
diff2 = (try_rsa_enc[1]) ** 2 - try_rsa_enc[2]

n, _, _ = egcd(diff1, diff2)
e = 65537

for i in range(100, 1, -1):
    if n % i == 0:
        n /= i
        break

#### get flag ####
bounds = [0, Fraction(n)]

i = 0
while True:
    print 'Round %d' % (i+1)
    i += 1

    c2 = (c * pow(2, e, n)) % n
    lsb = lsb_oracle(s, str(c2))
    if lsb == 1:
        bounds[0] = sum(bounds)/2
    else:
        bounds[1] = sum(bounds)/2
    diff = bounds[1] - bounds[0]
    diff = diff.numerator / diff.denominator

    if diff == 0:
        m = bounds[1].numerator / bounds[1].denominator
        break
    c = c2

flag = long_to_bytes(m)
print flag
X-MAS{N1c3_bu7_chr1s7m4s_is_n0t_ab0u7_g1f7s_17_1s_ab0u7_fl4gs}

Xⁿ-Mas (Crypto)

最大49乗まで考慮し、xが0~49に対して、以下の値がいくつになるかを確認する。
a0 * x^49 + a1 * x^48 + ... + a48 * x + a49 (mod n)

49元方程式として行列にし、逆元から計算し、係数を求める。その係数がASCIIコードになっているので、文字にするとフラグになった。

# solve.sage
import socket

def recvuntil(s, tail):
    data = ''
    while True:
        if tail in data:
            return data
        data += s.recv(1)


s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.connect(('95.179.163.167', 16000))

data = recvuntil(s, 'luck!\n').strip()
print data
n = int(data.split('\n')[2].split(' ')[3][:-1])

coeff = []
for x in range(50):
    row = []
    for i in range(49, -1, -1):
        row.append(pow(x, i))
    coeff.append(row)

A = matrix(Zmod(n), coeff)

B = []
for x in range(50):
    data = recvuntil(s, 'integer:')
    print data + str(x)
    s.sendall(str(x) + '\n')
    data = recvuntil(s, '\n').strip()
    print data
    val = int(data.split(': ')[1])
    B.append(val)

X = A.inverse()

flag = ''
for row in range(50):
    sum = 0
    for col in range(50):
        sum += X[row][col] * B[col]
    if sum % n != 0:
        flag += chr(sum % n)

print flag
X-MAS{W3_w1sh_you_4_m3rry_Christmas}

Santa's lucky number (Web)

どこかのページにフラグが隠されているらしい。
0ページ目から順に確認していくスクリプトを作成し実行する。

import requests
import string

def check_hexstr(s):
    for c in s:
        if c not in string.hexdigits:
            return False
    return True

for p in range(10000):
    print p
    url = 'http://199.247.6.180:12005/?page=%d' % p
    r = requests.get(url)
    t = r.text
    m = t.rfind('">')
    if check_hexstr(t[m+3:-5]) == False:
        print(r.text)
        break

1327ページ目にフラグが書いてあった。

X-MAS{W00pS_S0m30n3_73l1_S4n7a_h1s_c00k1eS_Ar3_BuRn1ng}

BoJack Horseman's Sad Christmas (Misc / Forensics)

$ zsteg bojack.png 
b1,g,lsb,xy         .. file: JPEG image data, JFIF standard 1.01, resolution (DPI), density 300x300, segment length 16, baseline, precision 8, 182x268, frames 3
b1,g,msb,xy         .. text: ["\r" repeated 50 times]
b2,b,lsb,xy         .. text: "u}UUUWUWUWUW]"
b2,rgb,lsb,xy       .. file: AIX core file fulldump
b2,bgr,lsb,xy       .. file: AIX core file fulldump
b3,g,lsb,xy         .. text: "rG#nG#n8"
b4,r,lsb,xy         .. text: ["w" repeated 9 times]
b4,g,lsb,xy         .. text: "DDDDDDDKDDKD"
b4,g,msb,xy         .. text: "-\"\"\"\"\"\"\""

StegSolveのData Extractで、Blue 1のみチェックを入れて、保存する。保存したJPGファイルにフラグが書いてあった。
f:id:satou-y:20181224202208j:plain

X-MAS{1_L0V3_B0J4ckH0rs3m4n}

Unown Gift (Misc / Crypto)

0xffをXORキーとして復号する。TrID にかけてみると GBA だと分かる。GBAエミュレータでゲームを進める。
f:id:satou-y:20181224202601p:plain
f:id:satou-y:20181224202613p:plain
f:id:satou-y:20181224202627p:plain
f:id:satou-y:20181224202638p:plain
f:id:satou-y:20181224202651p:plain
f:id:satou-y:20181224202706p:plain

I see! You got yout first part.
n=0x919988e16d5192c24b43f1c7b5
1856b5e56789aa3fc0d3b820500dde
307e414b1dd3525e19340cbc895a34
b0cae3db

Hm! you got your second part.
It's one worth nothing.
e=0x9ed98456b3387cafe143978372
4eb683b2434c4cdf387a3267f84217
19e12fd1ccdb7fdca650afea6a42de
ebe21e1

Ah! A third part!
You shiould note it patiently.
c=0x3731a737c24e83be7ca2256ed8
c1794be4aab34947441b92407420d2
5c6ad5b4966ab3b6ae0afbf0a2be20
87e3cb

RSA暗号のパラメータを見つけた。eが非常に大きいので、Wiener's attackで復号する。

from fractions import Fraction

def egcd(a, b):
    x,y, u,v = 0,1, 1,0
    while a != 0:
        q, r = b//a, b%a
        m, n = x-u*q, y-v*q
        b,a, x,y, u,v = a,r, u,v, m,n
        gcd = b
    return gcd, x, y

def decrypt(p, q, e, c):
    n = p * q
    phi = (p - 1) * (q - 1)
    gcd, a, b = egcd(e, phi)
    d = a
    pt = pow(c, d, n)
    return hex(pt)[2:-1].decode('hex')

def continued_fractions(n,e):
    cf = [0]
    while e != 0:
        cf.append(int(n/e))
        N = n
        n = e
        e = N%e
    return cf

def calcKD(cf):
    kd = list()
    for i in range(1,len(cf)+1):
        tmp = Fraction(0)
        for j in cf[1:i][::-1]:
            tmp = 1/(tmp+j)
        kd.append((tmp.numerator,tmp.denominator))
    return kd

def int_sqrt(n):
    def f(prev):
        while True:
            m = (prev + n/prev)/2
            if m >= prev:
                return prev
            prev = m
    return f(n)

def calcPQ(a,b):
    if a*a < 4*b or a < 0:
        return None
    c = int_sqrt(a*a-4*b)
    p = (a + c) /2
    q = (a - c) /2
    if p + q == a and p * q == b:
        return (p,q)
    else:
        return None

def wiener(n,e):
    kd = calcKD(continued_fractions(n,e))
    for (k,d) in kd:
        if k == 0:
            continue
        if (e*d-1) % k != 0:
            continue
        phin = (e*d-1) / k
        if phin >= n:
            continue
        ans = calcPQ(n-phin+1,n)
        if ans is None:
            continue
        return (ans[0],ans[1])

n = 0x919988e16d5192c24b43f1c7b51856b5e56789aa3fc0d3b820500dde307e414b1dd3525e19340cbc895a34b0cae3db
e = 0x9ed98456b3387cafe1439783724eb683b2434c4cdf387a3267f8421719e12fd1ccdb7fdca650afea6a42deebe21e1
c = 0x3731a737c24e83be7ca2256ed8c1794be4aab34947441b92407420d25c6ad5b4966ab3b6ae0afbf0a2be2087e3cb

p, q = wiener(n, e)

flag = decrypt(p, q, e, c)
print flag
X-MAS{Wh4t_4n_un3xp3ct3d_chr1stm45_pr3s3nt}

OtterCTF Writeup

この大会は2018/12/6 21:00(JST)~2018/12/11 2:00(JST)に開催されました。
今回もチームで参戦。結果は 1100点で290チーム中54位でした。
自分で解けた問題をWriteupとして書いておきます。

ReCurse (Misc 150)

添付ファイルは何重にも圧縮されたファイル。112回解凍すると、flag.zipは暗号化zipになっている。
zipのファイル名を連結し、Base64デコードする。

import zipfile
import os

DIR = './work/'

flag_file = DIR + 'flag.zip'
os.rename(DIR + 'a.zip', flag_file)

passwd = 'a'

i = 1
while True:
    try:
        print 'Round %d' % i
        with zipfile.ZipFile(flag_file, 'r') as zf:
            zf.extractall(DIR)

        os.remove(flag_file)
        files = os.listdir(DIR)
        file = DIR + files[0]
        passwd += files[0][0]
        os.rename(file, flag_file)

        i += 1
    except:
        break

print passwd.decode('base64')

上記のコードを実行すると、以下のURLが出てきた。

https://www.exoticanimalsforsale.net/sale/39353-2-female-small-claw-Asian-otters.asp

暗号化ZIPに入っているファイル名はEmailMeThis.txt。メールアドレスがパスワードかも。上記URLにリンクからメールアドレスがわかった。

Brking1991@gmail.com

これをパスワードとして暗号化ZIPを解凍する。EmailMeThis.txtにフラグが書いてあった。

flag{Recursion_1S_T3rribl3_AnD_1_H4t3_My_L1F3!!}

Birdman's Data (Network 150)

httpで絞ると、暗号化システムで暗号化していることがわかる。

No.419: key
No.423: iv
No.449: ciphertext

AES-CBCモードであることもわかるので、復号する。

from Crypto.Cipher import AES

def unpad(s):
    return s[:-ord(s[-1])]

key = 'XfCtxvD1yFZbxQ/+ULhAcA=='.decode('base64')
iv = 'sEhrZxQpnNnINixu3KQ1Tg=='.decode('base64')
enc = 'qKOtD3sK0WMMbAkIKach40aXJpNSz+N4dxcQC5I84ZOe7RqsK2ScQPQ4FO0NLvpU0M9uIJoZE1Z/8pY3qP5SyCebGjiEggb/LN0ODbud9YEjP69m44O4FqXHrJnhktoIV352sWOu0dj3hVl9KQd/nduPtSwec+Legwpy1ri7XEpOi8tbf89+hegQbJCt+5kxFPVdx++ymka3Lf/2rj2m9QV7EVz6AiIg6lsSUv23gpaGbWF57g+hUqLC+zhHVrWt3OzuYE9Tf0mxklrWWOAGUPQBNhCy93Q1iu8yB7x6j2ijh/k9gnibdjiLKjww/p88LF3Xv4GaoBH1Qzocpe21NWFp+RI1UNzB7duJ5L6V8rxsuIuFn27u4N9YhuM8QPBaiLd0fCB6bk6fmXivNLxRoqrgIOIXG7Oa4W+G1TOwt4IOO6VcgSIlgL5jJkFm4baXNAZ4ppylgQzRUBac49EGubFU4Bp7tXmu/w4H3YzkJPbFhm5q0gitLtZx91zpeTra8b3zrV0C/r0tbToFsNYHvUDjlT/yrWW3G20Q5Hy1eKmbubDB2h9BuIcmFW7ZjPK5hu65n8xTND7jgn/AoqpO7c94JdttKSeo7pbfjP4/1BpIUr7F8+HGy/yIWY1ZXRbNqP4dOEyhjkylvQOhun34FhSjFHaLQMK1//jeoEP9x1q66wze+oLeB53OjJdM5LhusIEN7wnwm2KDAPV7s9XimA4D8m9PImnKAT2ag1/7VqqpbKCU3JvVGQnmfuF4gUpYC7Q02O1BheqCI6OGxkcWif3Yd6Pe0KzXrhobWbTityQMVRGIBrcdHpikUNz6Y580Bdwjsnt+1P9/qCa9f9LzXjGdT4aBGS+9OWwUUnaRuoT9N6lG2apXbeqb9zJziwz6RjwYYXYAQ6c+9P1mzPjm9gnPZYigu7/0RwEq3UHnIjGkOsU5YhzciSiQQxBoda+7noLlfQd0IaL1jrtjQksGy3vALQNA3MLECe9juJ429aB+ndsSjYZ74ckNtITdVhJSwS3p2bWuOia0TSg1leDJPiDWD6DhhafpTWwxyo1Vp3pCv2HgMjgmnRIxPwcHPkTYkxNmk5G6UWhkSKbCtvvPsWZ2s//0PsbdhnN3vCDLrbIoYoIy40aCH98eWjuF1rGKbX6TdcFrjzhGUiKPW6vk+bF/ZSSkTsDBi1lIj7gdxbEzFsGUdO/mHyC3Rwo5yFqFFo+z4e78OhFVezRx/CPzyKzRlLubHzwpz2cvdLfdmndta9AwgwKD2czcjkGtJRBtZUeegN5R70yER7KSa1BbnX5mFgy4CiyLcT1hVSdjD+Cb3K+qtqh51kY8YHcq2koRrR6XHVOYoECXf2ElmOZ067I2vuFgaKqgp08cMA+4HgHIAsWJEOy8Xk7C7inIfWxzBpPdeC+erwvJgcqCm58TwNyjC0KprD5HeVK7ADcI6VFfB8PTtf/RDBGOVwa0SCgmX0pw1GbWsRgHD5QDXgee6PpD/+ug7/vArQBGaYsYiqkbI+ACROR2tRBH0iJq8ptbhW6eER8XqN7fAT87Mzw0Sx4VcWhAMlZZbycvxRUz+OiEjedNE5nBPGzQYorIyychpErdG/1fqjSkM7jwPQxqRNQwiGxE9M6aWDjLuvJ8nDMV0ShOkBlNQ0dQOH6ih7E4cnbm7bIVqXLkcyvwLEllMHHkVrLDeleDpu1c7+uL8DljSsHiygRnMexOR3pwXmnaZ+lMLoJkwrXc0+j9R4i37lVO8GtO0PqbXd0xnzTVpRu/8HFHIfobIaHpbTDcO+YrWmj6KqS4/87DOvxoc/PuoqrYlECoFGEJFms+AysRZ6hJ2TiyjAwEUAJNeqaSckilTm/mqfPgzM2XwFfBaZMXu46Ah9grhWem1gVR+OnixoFoQmvDfRcjavjtHvwNvESiVdxbgeU2oImV+reHoUYWKSbLh4jqjlqpXrH7dU2pSRuQ05/VM5W/ns4+gQeI+6K1KLGKKdieTnFESfgENPXLKTn3B3pEssYobGLnhjjAYUF57R5pIdShnRGTnsUeguP0QuCShQkWKUrtADazFaI351Lxkns/mF1dOz2Ao91nGiSekw6yWO/5dQqvUAiHQx7Uj168UpmI8wYCVorC/bL5B8OOWC1rJd79uM+Znu3NGY2fOSejFaGdK24ULEtU1M5dJeMacFR238OX1/59PQZfk7ZvwJcPTcfKtoER9YybY5/3kYUTS2w7CcrWmstixLeKtRopeHR35mfRgi4r+CpUJPCdUqthWYXYkmD4lni2rAFpex2ffotNT4VVus3KpDQocYFQpnWDJ8pnMKpHQyfqjgr4oGXGJeCl3iLTAlrTzLsYsykLxhuHmSNe9+9MrmiMizdrJHVPjTWLXKBB9o4giC220dodVLgiot0POixbKSaiiNlNRGtgsjJii2C1Pe0W1aEOUn0thCh30KQstnfxG4J+L51jTBI6yNeaaIdsaMBF5gRqP6afljhvT+koPG8sinnQNKR/T12UaJzdtsWrUFIV1+5b+M+CioH5lfWXx/CiCi+uCwUsgKMS3PbISidmdjYEqAC+Iqo87zfcmZsramZuhxs7JuiwF0Xr6L1/EoxnhfQovP/ny2QMC5ibVltpBZf0BJmZ9KT/MlZdWGkpBLQHxyia5VrvUeZEyvwVhuV1df436fE57Bp00X76pTjqZUmdEV/2VfU2/rWiosval7ZwT/+0XOdjEx/9T+x5QFS6i+4gMpINL1XsnDuBBOuoGJC1ElBY2wFtyKXvq+lCnlfQT4lTDLdQlXSEYM8AnT5Sb/9N2CExNkuRWRXgJGkFe66darkElMuQVAWfwkvtu5qQjIwm5GKGyGNb08VucDORtGn2ehrkmKSR/RYxDEYW3RzT8A+UvkaGxyL0AA8zqgNz6mLOR021qgH7NvtoYXKIYiVKvzNM38TtzfQU4lVZ6tDFKpRC1d+bTzAgyfETNn5YJD3U+KjutSU3FmLr0fgpIkNN3NaM8MGUcIK+xRve8yCXeH9zyTqTbMACodNly9Tc3iquUppiAZgDVKBNL18OR1H4YjAeAI23nkTts4QA+x5EwFdFrKVHf/kklNikVnkfA20y/ngxkdkcFBwT7Z4n7Cm+1QTUjDG4Cf2j78IM4CpvR5WqoOQ3y0jrhs8hPhKGqtSqZP2NRJQCSsb2Vx5peLKpf0wv8FNiVnJTj1HQWBj9ozLIekc9cPbThlqbI5Cr7LiOG/4RbjjwD7hW1gtoW1/mqN4iEgL0z3qOkD2Q22IKxxwNUZOIu7gm7lmtbi21QWexLRJKCCCV8dSBFVSyQrrx8i6HbONFLhHCD/3BV4PWjlUBOwre7CsPA0OzlxIZ76h0Bik1bZvk6wXaAvMBubAQDq4vObxRidEsXG2cQximadPiKSEAMLLe/ICYAnh7SaYyn3PFKIslama90lcCBm9i17QNkVRnMMqjze8Wt/v0p3hX28BQxSZgGEBxd3+oD3b4+Z1kYjneVyhRLb/xeTl731nR3xXX96aZMG4uS13nNmaPT5aO/yKeqIoPEYBg6UYsSneFX6g+H4WMs/7tLY98F6Z1ZOZIpU8XMHj8GuEXS3mv62CW4kMc+SnGo6Ase1ZDpGyY77UcfRwtv0jSV2ot2bLCHEp5q5VKjTFlweSyZCS1CoISzQx1wdliDgAI/R1gBi+VsgCbVstK72ulwr30NTO64O8vYvip71eKEPocDUtXXv5K0l/+AdT/x8Q46M0CjOy9XwTqEq49TqknLAnZCD0GHDtzaBB39XXVT6WqO0Xb+VBRwGi0OMwSKcoek4pPxXFr58cXbvW5ZRbGOCsL+zPN8sc2m4896YCNKOJMV99ladLJ3tVvup6KY0QBwym6NyAh/CznnMxqOAsVJrk3sFP8GB8k2bLc8jqvsSSJan6pb/QdlGfuXGvToIfcJbOgHEU5OEmpPr8LfVBjrm4zocJIAvYE90gE3Q5kxeq5fVy1TbdOYs923HUdGEVq7fGyLuqG9/2YyKV0nHOYPG56TGuyUzUbVtwNVpzxhcIWwsekItUX7HaF6c8a8XeZwYEH7Ds4kGqfGsOP++uYFbjT2tXBIfdFg6sSNbP7VDQOxt9L0nzAjcxzayGatCt1+20ESyxKKDd4P9jXvKeKVHx45+EL7hJjyKkgnSaWqUA92fodVFXZ89NiOKd7ydxgxVUYtgU8Mo9qz2X8hrFCl4YSVfihUy3yIJJwjJLqadmihK41+qwS2m8/2vze3Lzt4VknTGcW/yq9GMMWTNLMbu0D4X2YQeil6rlNrfhC4uBGoBhtFvUGe4MxFpWPBIeQacqzVOQi42Q0C0fmiwbMrXb2+4jWCS2TW2N7GeyqgInyp4sqiRjj49Bz7tEnY9h6hkEkXACHTZLCwq0jrOn9usR3W15ebmB7RFJA136X/5K7jxad1ReXAJMcHzg8VaVxfI9LEMDf/EERtFpCd4eBQsGddB3BCrJAKrn4c+DvOcumVQJrxMqL1FRNZVlmEE8v/lp94gd1aaFltM6vA9+eNowT/u0i8ehSe9Zy05saT8eOlGeVXvcPx5w35SQ+62e/xnZXP58esdrz4y30bFEZ7qa5BsiQppa6R9Ix2QKSzViS1EyRBWr/ttLi1e12+1jQ51+ZJu2/F5sNF6Y0ZTfg0KWf+LrIE9Hsi1qs2wbevKEvUsE9a59Ay/jWGJEYHzDZivhmSDOwX9Fj6/5+yZNmyT984NiapCozRuW+RaW+9x1bbm8s98QjGL7Y1AT1Op6ZyQDVxo09eX88rlSLHvI='.decode('base64')

aes = AES.new(key, AES.MODE_CBC, iv)
dec = unpad(aes.decrypt(enc))
print dec

lines = dec.split('\n')
flag = ''
for line in lines:
    flag += line[0]

print flag

実行結果は以下の通り。

Chance Something's wrong, I can feel it (Six minutes, Slim Shady, you're on) Just a feeling I've got, like something's about
To happen, but I don't know what If that means, what I think it means, we're in trouble, big trouble, And if he is as bananas as you say, I'm not taking any chances You were just what the doctor ordered I'm beginning to
Feel like a Rap God, Rap God All my people from the front to the back nod, back nod Now who thinks their arms are long
{
Enough to slap box, slap box? They said I rap like a robot, so call
me Rapbot But for me to rap like a computer must be
in my genes I got a laptop in my back pocket My pen'll go off when I half-c*** it Got a fat knot from that rap profit Made a living and a killing off it Ever since Bill Clinton was still in office With Monica Lewinsky feeling on his
Nut-sack I'm an MC still as honest But as rude and indecent as all hell syllables, killaholic (Kill 'em all with) This slickety, gibbedy, hibbedy hip hop You don't really wanna get into a pissing match with this rappidy rap Packing a Mac in the back of the Ac, pack backpack rap, yep, yackidy-yac The
exact same time I attempt these lyrical acrobat stunts while I'm practicing That I'll still be able to break a
Motherf***in' table Over the back of a couple of
_
Faggots and crack it in half
Only
Realized it was ironic I was signed to Aftermath after the fact How could I not blow? All I do is drop F-bombs, feel my wrath of attack Rappers are having a rough time period, here's a Maxipad It's actually disastrously bad For the wack while I'm masterfully constructing this masterpiece as I'm beginning to feel
_
Like a Rap God, Rap God All my people from the front to the back nod, back nod Now who thinks their arms are long enough to slap box, slap box? Let me show you maintaining this s*** ain't that hard, that hard Everybody want the key and the secret to rap
immortality like I have got Well, to be truthful the blueprint's simply rage and youthful exuberance Everybody loves to root
for a nuisance Hit the
Earth like an asteroid, did nothing but shoot for the moon since MC's
_
get taken to school with this music Cause I use it as a vehicle to bust a rhyme Now I lead a new school full of students Me? I'm a product of Rakim, Lakim Shabazz, 2Pac N- -W.A, Cube, hey, Doc, Ren, Yella,
Eazy, thank you, they got Slim Inspired
enough to one day grow up, blow up and be in a position To meet Run DMC and induct them into the motherf***in' Rock n' Roll Hall of Fame Even though I walk in the church and burst in a ball of flames Only Hall of Fame I be inducted in is the alcohol of fame On the wall of shame You fags think it's all a game 'til I walk a flock of flames Off of planking, tell me what in the f*** are you thinking? Little gay looking boy So gay I can barely say it with a straight face looking boy You witnessing a massacre Like you watching a church gathering take place looking boy Oy vey, that boy's gay, that's all they say looking boy You get a thumbs up, pat on the back And a way to go from your label everyday looking boy Hey, looking boy, what you say looking boy? I got a "hell yeah" from Dre looking boy I'mma work for everything I have Never ask nobody for s***, get outta my face looking boy Basically boy you're never gonna be capable To keep up with the same pace looking boy 'Cause I'm beginning to feel like a Rap God, Rap God All my people from the front to the back nod, back nod The way I'm racing around the track, call me Nascar, Nascar Dale Earnhardt of the trailer park, the White Trash God Kneel before General
zorb
}

復号結果にフラグは含まれていないが、行頭をつなげるとフラグになった。

CTF{EmiNeM_FOR_LifE_gEez}

OTR 1 - Find The Lutra (Forensics 100)

ファイル形式は以下のような感じ。

ヘッダ(18バイト)
・Magic: 6バイト
・セクション数:4バイト
・4バイト
・作成日:4バイト

セクション
・セクション名:8バイト
・データ長:4バイト
・CRC32:8バイト
・Uppercase flag:?バイト
・Data:データ長に記載している長さ

いろいろ調べたら、Uppercase flagの長さはデータ長に記載している長さ/8になることがわかる。
それをもとにセクション名を取り出し、leetでlutraになるものを探す。

import os
import struct

def read_section_name(data, start):
    name = data[start:start+8].rstrip('\x00')
    length = struct.unpack('I', data[start+8:start+12])[0]
    end = start + 8 + 4 + 8 + length/8 + length
    return name, end

DIR = 'otr/'
files = os.listdir(DIR)

leet_dic = {'1': 'l', '7': 't', '4': 'a'}
for file in files:
    with open(DIR + file, 'rb') as f:
        data = f.read()
    idx = 18
    while True:
        name, idx = read_section_name(data, idx)
        name2 = name.lower()
        name3 = ''
        for i in range(len(name2)):
            if name2[i] in leet_dic:
                name3 += leet_dic[name2[i]]
            else:
                name3 += name2[i]
        if name3 == 'lutra':
            print file
            print name
        if idx == len(data):
            break

実行結果は以下の通り。

a358f694d1e5113ccd1a9ad7f1385549.otr
Lu7r4
CTF{a358f694d1e5113ccd1a9ad7f1385549}

OTR 5 - Wrong Place, Wrong Time (Forensics 100)

Creation dateを取り出し、ファイルの最終修正時刻と比較する。その際、Jerusalem local timeであることに注意する。

import os
import struct
from datetime import datetime
import pytz

def read_creation_date(file):
    with open(file, 'rb') as f:
        data = f.read()
    cre_date = struct.unpack('I', data[14:18])[0]
    return cre_date

DIR = 'otr/'
files = os.listdir(DIR)

diff = 3600 * (9 - 3)
for file in files:
    cre_date = read_creation_date(DIR + file) - diff
    timestamp = int(os.stat(DIR + file).st_mtime) - diff
    if cre_date != timestamp and cre_date != timestamp + 3600:
        print file
        cre_date_obj = datetime.fromtimestamp(cre_date)
        timestamp_obj = datetime.fromtimestamp(timestamp)
        print cre_date_obj
        print timestamp_obj

        fmt = 'CTF{%H:%M:%S %d/%m/%Y}'
        ny_tz = pytz.timezone('Asia/Jerusalem')
        flag = ny_tz.localize(cre_date_obj).strftime(fmt)
        print flag

実行結果は以下の通り。

44b2f36604d1ca6ff7f0d6b46f95c85d.otr
1995-08-15 08:27:12
2004-10-05 09:49:13
CTF{08:27:12 15/08/1995}
CTF{08:27:12 15/08/1995}

hxp CTF 2018 Writeup

この大会は2018/12/7 21:00(JST)~2018/12/9 21:00(JST)に開催されました。
今回もチームで参戦。結果は 385点で818チーム中57位でした。
自分で解けた問題をWriteupとして書いておきます。

daring (CRY 100)

AES暗号(CTRモード)とRSA暗号の結果とRSA暗号の公開鍵が添付されている。
AES暗号の結果は43バイト。RSA暗号の結果は128バイト。
このことから、フラグは43バイトであることがわかる。また、スクリプトからRSA暗号の場合は平文を256**95かけてから暗号化していることがわかる。

(m * 256**95) ** e = c mod n
↓
m**e * 256**95**e = c mod n
↓
m**e = inv(256**95**e, n) * c mod n

またeが3であることからmを3乗してもnを超えるか超えないかという数値になることから簡単に復号できる。

from Crypto.PublicKey import RSA
from Crypto.Util.number import *
import gmpy

with open('aes.enc', 'rb') as f:
    enc_aes = f.read()

with open('rsa.enc', 'rb') as f:
    enc_rsa = f.read()

with open('pubkey.txt', 'r') as f:
    pem = f.read()

len_pad = len(enc_rsa) - len(enc_aes)

pubkey = RSA.importKey(pem)
n = pubkey.n
e = pubkey.e
c = bytes_to_long(enc_rsa) * inverse(2**(len_pad * 8 * e), n) % n

c2 = c
while True:
    m = gmpy.root(c2, e)[0]
    if m**e == c2:
        break
    c2 += n

flag = long_to_bytes(m)
print flag
hxp{DARINGPADS_1s_4n_4n4gr4m_0f_RSAPADDING}

Pwn2Win CTF 2018 Writeup

この大会は2018/12/1 0:37(JST)~2018/12/3 0:37(JST)に開催されました。
今回もチームで参戦。結果は 530点で163チーム中44位でした。
自分で解けた問題をWriteupとして書いておきます。

A Segregated New World [Read first] (Story)

長文の中にフラグが書いてある。

CTF-BR{I_know_about_th3_r1sks!}

g00d b0y (Bonus)

ルールのページ(https://pwn2win.party/rules/?lang=br)の最下部にフラグが書いてある。

CTF-BR{RTFM_1s_4_g00d_3xpr3ss10n_v4.0}

Sum [Hello World Platform] (PPC-M, Platform)

SSL接続するサンプルプログラムがついているので、実行してみる。

received: 5 7 3 5 6 3 6 1 5 3 9 2 0
sent: 55
received: 2 2 5 3 8 0
sent: 20
received: 9 6 9 3 4 2 4 0
sent: 37
received: 3 4 1 7 3 9 3 3 7 8 9 2 8 8 6 6 2 8 0
sent: 97
received: 5 3 4 2 1 5 5 0
sent: 25
received: 2 4 8 3 4 6 2 4 9 8 0
sent: 50
received: 3 9 9 4 7 3 4 8 0
sent: 47
received: 5 4 2 9 8 9 4 1 5 6 3 4 8 9 5 7 8 0
sent: 97
received: 4 8 4 8 1 3 4 2 2 6 3 2 3 7 0
sent: 57
received: 6 8 2 9 7 8 4 9 8 5 5 7 3 6 3 3 7 0
sent: 100
received: 2 7 5 6 9 3 6 0
sent: 38
received: 4 5 7 1 9 1 6 4 1 3 7 5 1 3 5 0
sent: 62
received: 6 5 3 3 7 4 9 0
sent: 37
received: 3 1 8 6 1 1 1 6 4 7 5 7 0
sent: 50
received: 6 2 2 5 9 2 3 5 3 0
sent: 37
received: 6 4 7 6 8 1 8 1 8 6 2 8 3 3 0
sent: 71
received: 3 6 9 5 9 4 1 5 6 2 9 6 4 6 8 7 1 6 0
sent: 97
received: 7 6 5 1 7 9 6 8 0
sent: 49
received: 9 3 5 1 6 1 5 7 5 5 0
sent: 47
received: 6 3 7 7 1 8 7 9 2 5 9 3 7 1 8 8 5 0
sent: 96
received: CTF-BR{Congrats!_you_know_how_to_sum!}
CTF-BR{Congrats!_you_know_how_to_sum!}

The Bavarian Hierarchy (PPC-M, Platform)

最初の1行はNとMを表している。Nは上司、部下の関係みたいな組み合わせの数。Mはある2名の従業員番号の情報の数。
次のN行が上記の組み合わせ。次のM行が上記2名で問題となっている。

N行は左が最も上位で、右の番号に別のデータの左の番号を連結させていくと階層になる。問題となっている2名で共通の上司の数を求める問題になっていることを考慮して、コードを書く。テンプレートは与えられているので、solve関数の中だけ追記すればよい。

def solve(N,M,edges,queries):
    # Solution here, ans = array of answers to each of the queries
    trees = []
    for edge in edges:
        found = False
        for i in range(len(trees)):
            if trees[i][-1] == edge[0]:
                found = True
                trees[i].append(edge[1])
                break
            elif edge[0] in trees[i]:
                found = True
                idx = trees[i].index(edge[0])
                new_tree = [trees[i][j] for j in range(idx + 1)]
                new_tree.append(edge[1])
                trees.append(new_tree)
                break
        if not found:
            trees.append(list(edge))

    ans = []
    for query in queries:
        q = list(query)
        paths = []
        found1 = False
        found2 = False
        for i in range(len(trees)):
            if found1 == False and q[0] in trees[i]:
                found1 = True
                paths.append(trees[i])
            if found2 == False and q[1] in trees[i]:
                found2 = True
                paths.append(trees[i])

        if len(paths[0]) < len(paths[1]):
            min_path = len(paths[0])
        else:
            min_path = len(paths[1])

        count = 0
        for i in range(min_path):
            if paths[0][i] == paths[1][i]:
                count += 1
            else:
                break
        ans.append(count)

    return '\n'.join(map(str,ans)).strip()

    
import ssl, socket

class Connect(object):
    def __init__(self, host, port):
        self.context = ssl.create_default_context()
        self.conn = self.context.wrap_socket(
            socket.socket(socket.AF_INET),
            server_hostname=host)
        self.conn.connect((host, port))
        self.f = self.conn.makefile('rwb', 0)
    def __enter__(self):
        return self.f
    def __exit__(self, type, value, traceback):
        self.f.close()

with Connect('programming.pwn2.win', 9003) as f:
    inew,M = 0,0
    edges = list()
    queries = list()
    for il,line in enumerate(f):
        line = line.strip()
        print('received line %d: %s' % (il,line))
        
        if b'CTF-BR{' in line or b'WRONG' in line: break
            
        if il==inew:
            N,M = map(int,line.split())
            edges = list()
            queries = list()
        elif il<=inew+N:
            a,b = line.split()
            edges.append((a.strip(),b.strip()))
        elif il<=inew+N+M:
            a,b = line.split()
            queries.append((a.strip(),b.strip()))
        
        if il==inew+N+M:
            ans = solve(N,M,edges,queries)

            f.write((ans+'\n').encode('utf-8'))
            print(ans)  # for debugging purposes
            
            inew = il+1

実行すると、15ラウンドほどでフラグが表示された。

CTF-BR{L0w357_C0mMoN_4ncE57Or_1s_u53fu1l_f0r_8i3r4rch13S}

BCTF 2018 Writeup

この大会は2018/11/27 15:00(JST)~2018/11/29 3:00(JST)に開催されました。
今回もチームで参戦。結果は 876点で318チーム中41位でした。
自分で解けた問題をWriteupとして書いておきます。

IRC checkin (Misc)

freenodeで#BCTFチャネルに入る。

21:48 *topic :  BCTF 2018 will start at Nov 27 10:00(UTC+4), Beijing Time 14:00(UTC+8) at https://bctf.xctf.org.cn (if you had registered xctf account, just use it, otherwise please register one and create a team to play) | Flag format: bctf{.+}, if not will be clarified in challenge description. The flag is BCTF{Welcome_to_BCTF2018}
BCTF{Welcome_to_BCTF2018}

guess_polynomial (Crypto)

n: 100以上120以下のランダム整数
coeffリスト: n個の配列(0以上[1をnビットシフトした値]以下のランダム整数)
x: 入力

calcでxを掛けながら配列の各要素に対して和を取る。この和の値を表示する。coeffを推測できればフラグが表示される。
x を2**120より大きい値を指定すれば、簡単に推測できそう。

import socket

def recvuntil(s, tail):
    data = ''
    while True:
        if tail in data:
            return data
        data += s.recv(1)

def guess_nums(num, x):
    guess = []
    while True:
        guess.append(str(num % x))
        num /= x
        if num == 0:
            break
    guess.reverse()
    return guess

s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.connect(('39.96.8.114', 9999))

coeff = 2**128

for i in range(10):
    data = recvuntil(s, 'coeff: ')
    print data + str(coeff)
    s.sendall(str(coeff) + '\n')
    data = recvuntil(s, '\n').strip()
    print data

    num = int(data[17:])
    guess = guess_nums(num, coeff)
    guess = ' '.join(guess)
    data = recvuntil(s, 'coeff!')
    print data + guess
    s.sendall(guess + '\n')

data = recvuntil(s, '\n').strip()
print data
BCTF{One_T1m3_10_Gue33_Coeff_1s_0K!}

ASIS CTF Finals 2018 Writeup

この大会は2018/11/24 15:00(JST)~2018/11/26 15:00(JST)に開催されました。
今回もチームで参戦。結果は 811点で182チーム中28位でした。
自分で解けた問題をWriteupとして書いておきます。

Mic check! (Trivia, Warmup)

問題にフラグが書いてあった。

ASIS{w3lc0m3_b4ck!_7h1s_p14c3_h45n7_b33n_753_s4m3_w1750u7_y0u}

John-Bull (Crypto)

pubkeyを因数分解する。

r**6 + 5*r**5 + 10*r**4 + 13*r**3 + 10*r**2 + 5*r + 1
= (r**2 + r + 1)**2 * (r**2 + 3*r + 1)
= p**2 * q

rは6次方程式になるが、sympyで求められる。上記からp, qがわかり、pubkeyを素因数分解できる。ここでの暗号は以下のようになっている。

enc = pow(m, pubkey, pubkey)
pubkey = p * p * q
phi = p * (p-1) * (q-1)

p * p * q は p * (p-1) * (q-1)と互いに素にならないので、そのまま復号できない。暗号の式を変えてみる。

enc = pow(m, p * p * q, p * p * q)
↓
c = enc % (p * q)とする。
c = pow(m, p * p * q, p * q)

p * p * q は (p-1) * (q-1)と互いに素。これで通常のRSAの復号方法が使える。

from sympy import *
from Crypto.Util.number import *

pubkey = 3415775651990117231114868059991823731694168391465118261123541073986397702947056759501589697018682285283905893102019391953165129250445987511496328390478214156138550568081360884795196720007402795178414072586445084589188812271144227913976270609786532206307549154139514246177504313696905220271023590900584622193476455815728425827517096143262953674043805121028581660274394493861460258597130188538332977679416970808454282017991307383835356188698891323239771333178860346825972405652914210954631134409600833327693593543421410732434281694454355747008933885889869077937880862749049074740126067215284910788706518425606114203333939656875871818894784079170292840540681948732880660003000926906333894065117345867196506856521542472349855590932301830372695420851264943795112040150205561483289746364835891125359307397506516272039186039783992620965800450343112765502550149168357851547665186618429181796721954012847077634388652598794182315250366936611355658686688939934516900009808518223359241944137277154786476218874224865037819222158865245588353031015122185374014406127446401298766736266831637852985756300017995390160761028057020573055543615912481389851812757348379419397130083208775789655825117981028241260930861007152057766814139170496584713321278626253968883276653358428036897577768739458725693447122759791961361097160265922640311146274535842798727318743122276126487545827596583971543880517021741131581309905790220398409615820785382645469996656013188425862658824568438227653902664968157149269346732859000330582545267782235066499139875211275390674091559851875853548905976806413521230016513322214240509217605309858575530246251875145909490471112222194075412324792050366838359937779806344187239056856471058353548936427916942194109609165854034767323294935701500110192365307711393371247166567444590592355257900093259599574780053937287600294098393324949090038950101

enc = 172254401616728337848224556256193294668254066768665624620573955921904663415844987360305683044269987528418379305124320147209588306619600641931717574384801086412717165043339754089854945269488039157031822759552038220243667748187712406870604130874288848961422658181035116276222087495309539815379227353704980160563111860011813283093207521575802100014408033039719223557618408913808906098293389776713037943338000210957134248117986210892735617670398002934139712508431588063592442750666131635721232279579114412057382482634199793027886476451072132799009262126068858578298283046601000880559403008084425323306037979617803443696059413247270929031458924282241105950888791411422687779723342754994324724737283365077742875322607687106058784350376580745162809296384205316865766883773721914203935128431492247985755204159286761485776182149007712492892483933270120585324692872062057327390303613634093538988078627329297217605056348331910353384255935457914956221810806802338940927281542361188610818936740209620052730118914762676848436107226923154169182628394200511074094416135594725057729803618271672713265182266181460723433237689954353512385555171399460870707449024037962690482864822971633650492835486036834553508571232609988066578567702464349018675580536990329927725573108328721614238899767792645665535623446031410358844459259283846182131541439033837736746980370117933542817231688533759434901524622912254499686908606070397662874360407075300248727974071742299708009048853008697832021516188431289704110567432234451743516365186915321744582268642673156685090283640357282428092579506635927396169516769103184205482482269342855874163597222301484981530193824960936155581252590505096646005478378577133665334258562017564658379524993172647857018916805201682065829122503078635804169426240558643597061660475712949155431727872200202869508621492240387907991955060578185917725771

var('r')
eq = Eq(r**6 + 5*r**5 + 10*r**4 + 13*r**3 + 10*r**2 + 5*r + 1 - pubkey)
ans = solve(eq)

r = ans[0]
p, q = r**2+r+1, r**2+3*r+1

assert p * p * q == pubkey

c = enc % (p * q)
phi = (p - 1) * (q - 1)
d = inverse(pubkey, phi)

m = pow(int(c), int(d), int(p * q))

flag = long_to_bytes(m)
print flag
ASIS{_Wo0W_Y0u_4r3_Mas73R_In____Schmidt-Samoa___}