2020 Defenit CTF Writeup

CTF writeup

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

Sanity Check (Misc)

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

Defenit{Welcome_to_the_2020_Defenit_CTF}

Double Message (Crypto)

先頭の大部分が同じ平文の暗号化がわかっているので、Coppersmith's Short Pad Attackで復号する。

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

def coppersmith_short_pad(C1, C2, N, e = 3, eps = 1/25):
    P.<x, y> = PolynomialRing(Zmod(N))
    P2.<y> = PolynomialRing(Zmod(N))

    g1 = (x^e - C1).change_ring(P2)
    g2 = ((x + y)^e - C2).change_ring(P2)
 
    res = g1.resultant(g2, variable=x)
    roots = res.univariate_polynomial().change_ring(Zmod(N))\
        .small_roots(epsilon=eps)

    return roots[0]

def franklin_reiter(C1, C2, N, r, e=3):
    P.<x> = PolynomialRing(Zmod(N))
    equations = [x ^ e - C1, (x + r) ^ e - C2]
    g1, g2 = equations
    return -composite_gcd(g1,g2).coefficients()[0]

def composite_gcd(g1,g2):
    return g1.monic() if g2 == 0 else composite_gcd(g2, g1 % g2)

e = 3
n = 0xcfb6152ae5a6f9a40e97f84e0869ac7e20f90bfa0318df1878dc69eba44df38e549cda7946dc6ceebdd8bac4c0b94053d6d7044d30ff3ce6c55faeeb120d01c77dc2f1633af9ead59f6356bba03c43252ea2fed558252dfea465b108fc3261f080f17fd3db442b3e5e6cfceb6cbcc2323683db5f862bd1df093e73b7373a77750f4a3cbf38c44559b1252981f0d9325b10d90dbdf44cc982f4c7f955025b639cf9736977d84253b3473001cc0778776ce3d8442d3f300d65efb920ca289d8321b38f2eaf0314e9c14acea509709852839a7367dba5efd03f41e595b51a69a96ee1ea7626496746a318b8583a2bbc8920c25c085f7237c248530b847f5d146fd3
C1 = 0x86a4cc0a6a8f22fe35b11870b741495a9d9abc84e1ec76e03bd3495832b260aa9014b621bf515258ba33c72f94e75df8ab3969bedc86dd946af79cb0f333ae16267d4728ad5b3e48ff72439a159b0b1d0cd5303765607fbe58353361ae7ac27eabc0bebdecc2bcaeb4a18a3463deb4527d7078d9ed9141d79e3e819e2a407ce6a71933c587e4da51a2d936c1233247246936880de615db6511b2588977b6e974ff900daa5901af0df1d4623cbdb6b5939082621397bb20b6da3f40d0020d16fa2d9a5820bf2135725d164d338684809084353efea1c8339d4367e152a54ca36e42e94f0cd67392af2fa4ade80e3ba6173b642c3a9848b65d5214ac870786aa3e
C2 = 0x79f267c0b913f21f508a65d85e43a95e28896f92d127feeabe2e5f8068f518ae2fc9315753cd3eb116a4a8410b65ebfc70ed3c183d034ff48296f919a80564e5c91fcf7c9d3ffbc101dc3d155703609d6be3546d6edabbb27201543a93172d9b24a19835c298f6cae8f0ead507971463549fc9b165000fd9ea75b5181a361769fed258091be76ffccdf347d404a95d6b7f33ee4bd2d61e7b2c935cc93394b69cf281fed2ebebb5e5174e0a3a820cdb9ed16a0bebb7dc919cba560a99d47db2d35a3cd92e3ace4cca42666c2cc3b85705796690941b3861a468ec07fb178e057ff6327b0514830d85535d5d7fb9a3d85ab46ae89842cc7e3af06d6f6a1eeef1ae

delta = coppersmith_short_pad(C1, C2, n)
m1 = franklin_reiter(C1, C2, n, delta)

M1 = long_to_bytes(m1)
Flag = M1[:-16]
print Flag

Defenit{Oh_C@Pp3r_SM1TH_SH0Rt_P4D_4TT4CK!!_Th1S_I5_Ve12Y_F4M0US3_D0_Y0u_UnderSt4Nd_ab@ut_LLL_AlgoriTHM?}

Survey (Misc)

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

Defenit{Thank_you_for_playing_2020_Defenit_CTF}