SEC-T CTF 2019 Writeup

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

Sanity check (warm-up, misc)

freenodeで#sect-ctfチャネルに入ると、メッセージにフラグが書いてあった。

SECT{SECT_CTF_2019}

Trivial_rsa (crypto, warm-up)

与えられた情報を式にしてみる。A, Bは与えられた定数。

n1 = p1 * q1
n2 = p2 * q2
(p1 - p2) % (q1 - q2) = A
(q1 - q2) % (p1 - p2) = B

p1 - p2 と q1 - q2 のどちらかが大きいため、
p1 - p2 = A or q1 - q2 = B

式を変形していく。

p1 - p2 = A + (q1 - q2) * K1
q1 - q2 = B + (p1 - p2) * K2
　　　　↓
p1 - p2 = A + (B + (p1 - p2) * K2) * K1
q1 - q2 = B + (A + (q1 - q2) * K1) * K2
　　　　↓
p1 - p2 = A + B*K1 + K1 * K2 * (p1 - p2)
q1 - q2 = B + A*K2 + K1 * K2 * (q1 - q2)

p1 - p2 と q1 - q2 のどちらかが大きいため、K1 = 0 or K2 = 0

p1 - p2 = A + B * K1
q1 - q2 = B + A * K2

K1 = 0の場合
・p1 - p2 = A
・q1 - q2 = B + A * K2
　　　　↓
・p2 = p1 - A
・q2 = q1 - (B + A * K2)
　　　　↓
n2 = p2*q2 = (p1 - A) * (q1 - (B + A * K2))
   = (p1 - A) * (n1/p1 - (B + A * K2))
n2 * p1 = (p1 - A) * (n1 - p1 * (B + A * K2))

K2 = 0の場合
・p1 - p2 = A + B * K1
・q1 - q2 = B
　　　　↓
・p2 = p1 - (A + B * K1)
・q2 = q1 - B
　　　　↓
n2 = p2*q2 = (p1 - (A + B * K1)) * (q1 - B)
   = (p1 - (A + B * K1)) * (n1/p1 - B)
n2 * p1 = (p1 - (A + B * K1)) * (n1 - B * p1)

K1やK2はあまり大きい数字ではないと推測して、ブルートフォースし、こここまでの情報を元に方程式を解き、整数解が出るものを探す。p1がわかれば、q1も算出でき、復号することができる。

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

n1 = 16665162598091416675035243372929255215330237988600063606115453406246759269279788760269977993441302227754535063989940158801403082299136924692382379772238783511717805089453627769958409474798262234585212880036578100065244955419654350030210214612873050000707217728997449651244785327256673209001617229204596903739745000294771409411741050416912250410842101344110865361910624576900847453308353320549785990249062848385268654951594713494728031930339317011245422247813046177464952338694367015023462166849724348822067012372916419798329882575892837697474973759070677459272935998500533063881083981623170007582400032456357369057331
n2 = 12327967666608400089684292637697723886692743047311943117634453297696672596602132832770180763706410481136385428797064430470744303260875130025364968184033440278168149230015012651339700361911455246276535179299003908649820055478166532502332896978314839548456221498409689020137730201961802661796522959185289676293168958100994789278927928614060667061494784764996405812503722093377901735054396731379083755482112808051044511509930814761992548239396939638987562480503407989092943629763956630828533555667490559450650474172687439499014071217245302164885369990725379389835929411041979972161099398047802667999958241746711037377019

# (p1 - p2) % (q1 - q2)
A = 651462892194717457221755220174856890047929116650078860763950453454949587828096234616831315488704251531401792609600066162972268247282594239275742779598127716518383086923760296725577120504817396207799394031948181614036825015620143890966541423830037471615505961486852765107641800802598611031433822941186606730
# (q1 - q2) % (p1 - p2)
B = 442296418993240063675266142454740191465599525570774611710139968474930425844945295951472133337584882919079119792948035796322583493017921438477858246253211352232247225094327539626813294415765610979636199753519138117254187197466480294243789769005210602152862859358315543589192060482998253522480707816974954144

e1 = 65537
c1 = 7899134322955645246464106475661567371519411492907819361218537936109003314263398594946847506479710018156056516572597388680265129465680577498126784603599657304217232946737359907830193767343579320119617475061103397775839997585822041520474984253434505877605909867411822079954503549880731554010164405517963598831678530319685550356656748243909520671642189043288332595811057445820791781035731118992393238366930032136586970961554635691292784903624264141333213116074342104788426932419021114413087179933685563867060402709899375500659953038354210747849030819495299042436380277429490866466199179979698665821921998413237763283416

var('p1')
for i in range(100):
    eq = Eq(n2 * p1 - (p1 - A) * (n1 - p1 * (B + A * i)))
    ans = solve(eq)
    if ans[0].is_Integer or ans[1].is_Integer:
        if n1 % ans[0] == 0:
            p1 = ans[0]
        elif n1 % ans[1] == 0:
            p1 = ans[1]
        break

    eq = Eq(n2 * p1 - (p1 - (A + B * i)) * (n1 - B * p1))
    ans = solve(eq)
    if ans[0].is_Integer or ans[1].is_Integer:
        if n1 % ans[0] == 0:
            p1 = ans[0]
        elif n1 % ans[1] == 0:
            p1 = ans[1]
        break

q1 = n1 / p1
phi1 = (p1 - 1) * (q1 - 1)
d1 = inverse(e1, phi1)
m1 = pow(c1, d1, n1)
flag = long_to_bytes(m1)
print flag

実行結果は以下の通り。

SECT{ju99lin_w1d_d3m_alg3br0s}綠uXY&ﾃｳf鬱6ｵ€ﾏｫｰASﾗvｬ穂}ﾍv惨ｩ.,・ｭ?ﾚGﾑｮSHS践t2ｬ6T-7&・ﾑ        ・KﾕGﾋEﾚ跿ｨ・ﾓ・}萃5]・S

SECT{ju99lin_w1d_d3m_alg3br0s}