UIUCTF 2018 Writeup

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

We Read the Rules (other 0)

ルール記述の下にフラグが書いてある。

flag{0kay_s0unds_g00d_2_m3}

irc (other 1)

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

10:13 *topic :  Welcome to UIUCTF | CTF live at https://uiuc.tf/ flag{sorry_for_not_posting_link_to_irc_sooner}

flag{sorry_for_not_posting_link_to_irc_sooner}

ROT180 (Misc 1)

上下反対(180度回転)にするとフラグになっている。

flag{at_least_its_not_recon}

Hastad (Crypto 200)

Hastad's broadcast attackで攻撃できそう。
eは3なので、対応するnとcのペアが3つ必要。
ペアが分からず、cが15個もあるので、総当たりで攻撃する。

import functools
import itertools

def chinese_remainder(n, a):
    sum = 0
    prod = functools.reduce(lambda a, b: a*b, n)
    for n_i, a_i in zip(n, a):
        p = prod // n_i
        sum += a_i * mul_inv(p, n_i) * p
    return sum % prod
 
def mul_inv(a, b):
    b0 = b
    x0, x1 = 0, 1
    if b == 1: return 1
    while a > 1:
        q = a // b
        a, b = b, a%b
        x0, x1 = x1 - q * x0, x0
    if x1 < 0: x1 += b0
    return x1

def inv_pow(c, e):
    low = -1
    high = c+1
    while low + 1 < high:
        m = (low + high) // 2
        p = pow(m, e)
        if p < c:
            low = m
        else:
            high = m
    m = high
    if pow(m, e) != c:
        return 0
    return m

N1 = 0xbc4ec2b74d85fb57ec07f538b59987c1150042ef76178b7af6dc09ca139dc8570226fe0317f3b73e8f98de38eb03a986496431d8526be4e65d47d86130a4370348b8a8dbba80d922f4dbac31b95f1028baac1ba8f8cab00d6e362c761da0dece81a700b92a5c1d79ec50451b3147805123e92f424d422d688ab020280d35384f
N2 = 0xd83a59170679b7d8b2199e98656717c515e06e44e65b5f7b687e4fec6d21a7e6e75ecbcf208202f210ef8e29a7ad44ab72914b1f35d502f6d7f657e5512d4b989773515cbc046ca3ffef37f3090548ac1086d96c96fe7edb9bdeb58ba635fa1582da4a85357105293139c8152d70c2ec5ec667bb91197c353cd6aafac73476df
N3 = 0xc39ab84fbf6709048427c05dbd303f0ba2f90ecdd51a809f1d8da9df0546a771e982a6bccb299c4bf12d1b0b11df88b0627563d726bb70c5121cb5722c75e35b54e6d43d09443738fe3ac8e5a8bb74b1667ddf6592359d9fc65a05a32b98a50c52f1339ed8b5fab5616d52d81a11579a83fc33e069c4d9cfb93b24d752937ced
N = [N1, N2, N3]

e = 3

c = [
0x10652cdfaa86ddbee1409ac7ac327a0c848081ee6e3b110867085f1074755785b0a5a6a2343b791695c3e91fdb370d5b26be3b6d2fc449c7788bbb1ab67ddc361b4115010618e39c883449b757fc1624369b440236ee65,
0x10652cdfaa8c9ef24fc044b5fed749888632ad132bd412f22d9d905e6ffd27b288c22884b24fe130d83aaab9c2dc6e942418dff89d2b66a66e40900db9456813d70eb63d0c38697f89ff387969d3d40163376416270965,
0x10652cdfaa8ab16290cf92bacf31b23d6a0ea95c2ebd6eb8afe4f038d852a7f17e98f965f299b4d00126611d403c5208a145157ed1d71079fc558eaa888e993360fac35c7a816ad183190867b1b7580a2677cd6871aa65,
0x10652cdfaa86ddbee1409ac7ac327a0c848081ee6e3b110867085f1074755785b0a5a6a2343b791695c3e91fdb370d5b26be3b6d2fc449c7788bbb1ab67ddc361b4115010618e39c883449b757fc1624369b440236ee65,
0x10652cdfaa875a9ac01e472ea5896c1d460410508b9a7c723b5ba904fb5b64d68a1e96254ba04b08c92d51f1fe6c3d6bb426e1ee8c61c8a6ff1eeab9e07f51d8057f2f0c54b27c7006539f7148484ff26a02e4cb1d3165,
0x10652cdfaa8c9ef24fc044b5fed749888632ad132bd412f22d9d905e6ffd27b288c22884b24fe130d83aaab9c2dc6e942418dff89d2b66a66e40900db9456813d70eb63d0c38697f89ff387969d3d40163376416270965,
0x10652cdfaa875a9ac01e472ea5896c1d460410508b9a7c723b5ba904fb5b64d68a1e96254ba04b08c92d51f1fe6c3d6bb426e1ee8c61c8a6ff1eeab9e07f51d8057f2f0c54b27c7006539f7148484ff26a02e4cb1d3165,
0x10652cdfaa8210601d22f4a15aa380233420f9ee9a276d3ac8e05cfc4f6f515f78331e8e74484e8533221e88f78671dd08622e78233e458978a35036680d1c5caaba2fa3bce3b914ad48501a276d6a88adc16db282e065,
0x10652cdfaa8ab16290cf92bacf31b23d6a0ea95c2ebd6eb8afe4f038d852a7f17e98f965f299b4d00126611d403c5208a145157ed1d71079fc558eaa888e993360fac35c7a816ad183190867b1b7580a2677cd6871aa65,
0x10652cdfaa8c2701b8bb7c11fc3218cc2d97cd4707f6de55637bc093f474d231b4d4fe8635261b8e4f772d0e51a25f8e713777a137be6f04e0d28ddd6ec0b852aaf357d33e08aed23e034fcd1ced38542fbeb5aa0eee65,
0x10652cdfaa8210601d22f4a15aa380233420f9ee9a276d3ac8e05cfc4f6f515f78331e8e74484e8533221e88f78671dd08622e78233e458978a35036680d1c5caaba2fa3bce3b914ad48501a276d6a88adc16db282e065,
0x10652cdfaa8c9ef24fc044b5fed749888632ad132bd412f22d9d905e6ffd27b288c22884b24fe130d83aaab9c2dc6e942418dff89d2b66a66e40900db9456813d70eb63d0c38697f89ff387969d3d40163376416270965,
0x10652cdfaa8ab162128a955a58d3b780f2656800796eb70c345c56d7b8523d614ef4ca920471f56493c83ca48500033a0c0b31988ca6e66a76e0ed559b38616688941558b127260cdf70261822929efa0aa6b6d79d1665,
0x10652cdfaa8ab162128a955a58d3b780f2656800796eb70c345c56d7b8523d614ef4ca920471f56493c83ca48500033a0c0b31988ca6e66a76e0ed559b38616688941558b127260cdf70261822929efa0aa6b6d79d1665,
0x10652cdfaa8c2701b8bb7c11fc3218cc2d97cd4707f6de55637bc093f474d231b4d4fe8635261b8e4f772d0e51a25f8e713777a137be6f04e0d28ddd6ec0b852aaf357d33e08aed23e034fcd1ced38542fbeb5aa0eee65]

i = 0
for elm in itertools.permutations(c, 3):
    error = False
    C = [elm[0], elm[1], elm[2]]
    a = chinese_remainder(N, C)
    for n, c in zip(N, C):
        if a % n != c:
            error = True
            break
    if error == False:
        m = inv_pow(a, e)
        if m != 0:
            flag = ('%x' % m).decode('hex')
            print flag
            break

flag{wh00ps_srry_4_br0adcast}