zer0pts CTF 2021 Writeup

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

Welcome (welcome)

Discordに入り、#announcementチャネルのメッセージを見ると、フラグがあった。

zer0pts{1375_4v0id_3nding_wi7h_zer0pts!}

war(sa)mup (crypto, warmup)

暗号処理の概要は以下の通り。

・p, q: 512ビット素数
・n = p * q
・phi = (p-1)*(q-1)
・e = 1337
※GCD(phi, e) は 1

・m = pad(int.from_bytes(flag, "big"), n)
　・ms：flag
　・ns：nの文字列化
　・psは8文字以上で、\x00以外から構成される。
　・"\x00\x02" + ps + b"\x00" + ms　⇒数値化して返却

・c1 = pow(m, e, n)
・c2 = pow(m//2, e, n)

mが偶数の場合は以下のことが言える。

c2 = pow(M, e, n)
c1 = pow(M*2, e, n) = (pow(M, e, n) * pow(2, e, n)) % n
   = (c2 * pow(2, e, n)) % n

計算が合わないので、mは奇数であることがわかる。

c1 = pow(M*2+1, e, n)
pow(M*2, e, n) = pow(M, e, n) * pow(2, e, n)
               = (c2 * pow(2, e, n)) % n

平文の差が1の暗号化がわかるので、Franklin-Reiter Related Message Attackで復号する。

#!/usr/bin/sage
from Crypto.Util.number import *

def related_message_attack(c1, c2, diff, e, n):
    PRx.<x> = PolynomialRing(Zmod(n))
    g1 = x^e - c1
    g2 = (x+diff)^e - c2

    def gcd(g1, g2):
        while g2:
            g1, g2 = g2, g1 % g2
        return g1.monic()

    return -gcd(g1, g2)[0]

n = 113135121314210337963205879392132245927891839184264376753001919135175107917692925687745642532400388405294058068119159052072165971868084999879938794441059047830758789602416617241611903275905693635535414333219575299357763227902178212895661490423647330568988131820052060534245914478223222846644042189866538583089
e = 1337
c1= 89077537464844217317838714274752275745737299140754457809311043026310485657525465380612019060271624958745477080123105341040804682893638929826256518881725504468857309066477953222053834586118046524148078925441309323863670353080908506037906892365564379678072687516738199061826782744188465569562164042809701387515
c2= 18316499600532548540200088385321489533551929653850367414045951501351666430044325649693237350325761799191454032916563398349042002392547617043109953849020374952672554986583214658990393359680155263435896743098100256476711085394564818470798155739552647869415576747325109152123993105242982918456613831667423815762

C1 = c1
C2 = (c2 * pow(2, e, n)) % n
m = related_message_attack(C2, C1, 1, e, n) + 1
flag = long_to_bytes(m).split('\x00')[-1]
print flag

zer0pts{y0u_g07_47_13457_0v3r_1_p0in7}

Survey (survey)

アンケートに答えたら、フラグが表示された。

zer0pts{h0p3_u_3nj0y3d_zer0pts_CTF_2021!}