LoginSignup
0
0

More than 1 year has passed since last update.

@peloeil

TSG LIVE CTF 9 Writeup

Last updated at Posted at 2022-11-22

2022/11/19
駒場祭の企画として行われた TSG-LIVE-CTF に TeamBlue として参加した。
本当に最近 CTF を始めた初心者なので、1問くらい解けたらいいなくらいの気持ちで望んだ。
まだ Crypto しかできないので、Crypto のみの writeup。

Crypto

1問目: RSA debug?

問題のソースコード
problems.py
def my_pow(a, n, m):
    result = 1
    while n > 0:
        if n % 2 != 0:
            result = (result + a) % m # omg! 
        a = (a + a) % m # oops!
        n = n // 2
    return result

from Crypto.Util.number import getPrime, bytes_to_long

p = getPrime(512)
q = getPrime(512)
N = p * q
phi = (p - 1) * (q - 1)
e = 0x101
d = my_pow(e, -1, phi)

with open('flag.txt', 'rb') as f:
    flag = bytes_to_long(f.read())


c = my_pow(flag, e, N)

print(f'N = {N}')
print(f'e = {e}')
print(f'c = {c}')

if my_pow(c, d, N) != flag:
    print('there is a bug i guess lol')
出力
output.txt
N = 142152419619953056039030613006300356362328489550709389999387369748296278181079224756839343268342516013642694413617303501060708009652311527189475960379078488611592094334453807443536588862100338035073773947550237167141330041879985706663975671411606265404764401055491939553565105755943917581461262323010934286591
e = 257
c = 1032307400372525030420319173259503709384961767939821142794251896087430140750696054688678035256705431662987859651860033467060026426212901209540363
there is a bug i guess lol

自作した累乗関数で RSA を行っている。公開鍵 $N, e$ と 暗号文 $c$ が与えられる。
二分累乗法にバグがあり、掛け算にすべきところ2箇所がどちらも足し算になっている。
本番では、味方の競プロつよつよの人が解いてくれそうだったので次に行った。

こういう算数チックなやつあんまり得意じゃない。
ちょっと実験すると($\mathrm{my\_pow}(i, e, N)$を$i = 1,\ldots,5$ で出力してみると)、$\mathrm{my\_pow}(i, e, N)$ が $i^e \pmod N$ ではなく $ei + 1 \pmod N$ を計算していることがわかる。
よって、$c = e\cdot\mathrm{flag} + 1 \pmod N$ とわかるので、$\mathrm{flag} = (c - 1)e^{-1} \pmod N$

ちなみに、$N, c$ の値を比べると $c$ が圧倒的に小さいことから、$c$ は $\mathrm{mod}$ を取られていないことがわかるので、更に単純に $\mathrm{flag} = \dfrac{c - 1}{e}$ とできる。

コードと実行結果
solve.py
from Crypto.Util.number import long_to_bytes

N = 142152419619953056039030613006300356362328489550709389999387369748296278181079224756839343268342516013642694413617303501060708009652311527189475960379078488611592094334453807443536588862100338035073773947550237167141330041879985706663975671411606265404764401055491939553565105755943917581461262323010934286591
e = 257
c = 1032307400372525030420319173259503709384961767939821142794251896087430140750696054688678035256705431662987859651860033467060026426212901209540363

m = (c - 1) // e
print(long_to_bytes(m).decode())

TSGLIVE{g0od_Mult1plic4t10N-Algor1thm_6y_ru55iAn_Pea5ants}

2問目: RSA debug??

問題のソースコード
problem.py
def my_pow(a, n, m):
    result = 1
    while n > 0:
        if n % 2 != 0:
            result = (result * a) % m
        a = (a + a) % m # oops!
        n = n // 2
    return result

from Crypto.Util.number import getPrime, bytes_to_long

p = getPrime(512)
q = getPrime(512)
N = p * q
phi = (p - 1) * (q - 1)
e = 0x101
d = my_pow(e, -1, phi)

with open('flag.txt', 'rb') as f:
    flag = bytes_to_long(f.read())

assert flag.bit_length() <= 400

c = my_pow(flag, e, N)

print(f'N = {N}')
print(f'e = {e}')
print(f'c = {c}')

if my_pow(c, d, N) != flag:
    print('there is a bug i guess lol')
出力
output.txt
N = 161158216253038255124492156151962399187548922270772103599266892572221327481080333694151491753952386387865153735917628775435896449548933903421087242431342475272954753478257425320498033392103209016100073542891497164623755193739116081982087416601688042791555293758187880072012603318037132783685510192234882270727
e = 257
c = 35670804975997119135517974550619182851023199117712172481981302698858610501172231787573382627176449105648892197879980333661081777520179757444468521044149805726225887861984296836753557996580478318594607972377600
there is a bug i guess lol

1問目と同様、自作の累乗関数で RSA を行っている。公開鍵 $N, e$ と暗号文 $c$ が与えられる。
二分累乗法にバグがあり、掛け算にすべきところ2箇所のうち片方が足し算になっている。
本番では、味方の競プロつよつよの人が解いてくれそうだったので次に行った2

1問目より予測がしづらいが、同様にして、$\mathrm{my\_pow}(i, e, N)$ を $i = 1, 2, \ldots, 10$ で出力してみると、$256, 1024, \ldots, 25600$ となる。$e - 1$ の倍数か？と思い、$e - 1$ で割った値を出力すると、$1, 4, \ldots, 100$ となるので、$\mathrm{my\_pow}(i, e, N) = (e - 1)\cdot i^2 \pmod N$ とわかる。よって、$c = (e - 1)\cdot \mathrm{flag}^2 \pmod N$ である。ここで、また1問目と同様に $N$ に比べて $c$ が小さいことから、単純に $\mathrm{flag} = \sqrt{\dfrac{c}{e - 1}}$ とできる。

コードと実行結果
solve.py
from sympy.core.power import integer_nthroot
from Crypto.Util.number import long_to_bytes


N = 161158216253038255124492156151962399187548922270772103599266892572221327481080333694151491753952386387865153735917628775435896449548933903421087242431342475272954753478257425320498033392103209016100073542891497164623755193739116081982087416601688042791555293758187880072012603318037132783685510192234882270727
e = 257
c = 35670804975997119135517974550619182851023199117712172481981302698858610501172231787573382627176449105648892197879980333661081777520179757444468521044149805726225887861984296836753557996580478318594607972377600

m, is_square = integer_nthroot(c // (e - 1), 2)
assert is_square == True
print(long_to_bytes(m).decode())

TSGLIVE{Th1ng5_cOmE_1n_thr33s..._but_H0w?}

3問目: Ta-Shi-Ma-Ku-Ri SAturday!

問題のソースコード
problem.py
from Crypto.Util.number import getPrime, bytes_to_long
from random import randint

p = getPrime(2048)
q = getPrime(2048)
N = p * q
e = 65537

with open('flag.txt', 'rb') as f:
    flag = bytes_to_long(f.read())

c = []

for x in range(3):
    m = 0
    for i in range(x // 2):
        m += flag
    for i in range(randint(1, 100)):
        m += p
    for i in range(randint(1, 100)):
        m += q
    c.append(pow(m, e, N))

print(f'N = {N}')
print(f'e = {e}')
print(f'c = {c}')
出力
output.txt
N = 825649642553946328490267023836964711129572425420611735966058683161869803283215266043480304824845111624861250510300789897618528373725236423187676275540723601517461477863617597011363813283912432725667966766365026775315273032389820659978567288706991615780840356377692023530302256488843866125445518514159949151341302906334427920162274058604910216851679502301606913882631899848196176184869193139522404440309942910091771387682701129390460352864424830348225562562360798114543519040072738973589496238169574712021125951918581191319660444131208154266965880763605102083738906048618836339364123455800563079686550795320715569070950383562791508039623249322653728302368039046435890273004852830380582259381379374039796805699684302425495704593736270681712039539888533167142142765955179751586182812597170124069636258732736256419964214220827795321240503521422326812202618089257462126043183583634654484130648706105306514678814826193407457179729443893215111314101986450773258647089878553484580160898905112473766432621689270421724705692314938092837187623229862232768861414241149888300579583906809606951755783656480333567845708998833428922469617739876313360808161540844790197840546900526733781250294563399708876853695183965156611592433321609232870013953529
e = 65537
c = [216949660113004296009259668300534993020105821221318058006221263360670206317854729377127498966972283960212373873547330855440142797545309741889850780082659137610701979875179586873874443387642727752002855684656612531771726640719619633438582181273632591174743374976090502725516525885649093905605104721563399232764370559319686543630287774695705426870288054780805886884491921016573316007837455531795089815940128261459926314061675936701853891694922813812049198405143262252257099312547195727842816568803642048524919788798727173501410164791200503759725852008322788468585177000946058954376320775607144975455532111394214266917076512741107919519690887365375813957064331707593146348692088975009680548447367069108122365861954880530389519192499912982109549734460942531549235319024383325646695977422842496129015105711419168291387289261442326876780828831973504626810114390393171510701043844459613441935866520624226443174255547675337272814485789089748704744611293531866397945075923707673405674255016158945416605425851541327230247596998795502825198541655593403244820709102630950288980468577818885363399136518273886482465020899520020602341105920756064956597718878275469302368240891713678237060859367758977108111107933911057364648831809616527933975723117, 51583635406618955557208798031147624649359706997894321317425067509557409512116347444691971717840825321762282106897546008753785164833165735283131541939787240317392863610293060744566401835537980790207397157473353459308465185310448343425023613481948457654298839653100624447942381541884995059659699037522150612679044514348858020667919011125524446639504563302142532251867486178285416293476451790876580998880606417421785230210127509623702346941936296746981361883286562134843938677366992051966798245452706267605585603343692317978016819231715857307068735137934491366772647205384911936853453614749551699730791191018566008379106281994472029692350910797889644569036546867294655273181462430377208614429223739315777635835706958649013243072661344976013622590769802411067495079611595519804951450278527673197146382744932947590521139592026885731486460586150261233447784465288806771380038058117150486428800081185435164931180958432508924403148226070068773739680914512869613605557080705887688517559644591799816707690740284686627022035112212121219985723834634142605435210358762666042844405511596009472018561856867143612554070064099007428461203339190177160487413537345360150848245438645956990549355115875764873560054219211605254611269626825489483842640018, 201429502572151907207669413393863256280229442301921016587875714023960062912920341109831247721910975613770542202242828341965723835386146006841058216933291783114002288320053664098945142941318519156136200671061933895553300458663647271233281358522594778147710061134740616893573333089485531127539828500315987612459716568044141593023609004381408588936566801447929202427928080539601272897572851547054648712652438083012901997959628627639447385055239583448692217462802742260141473445025292327701724092933587996835353444734828088406533758866626444792039437356890938357847006239458250704575446629903482282367142704404629013815989561413016107285061372224468791463151049756647566264554193099293900691587775208639431879674668031555020647808771495691526926027418625263124211207957569211422342040847487759542574428706594890204245691023052514898033003324502930414363660846197386147753305529070262094540601294948100028557945063651035028338388259335341372029755993700224771762797479049478003774997264464877472363393002255610570285454693913941545714976481242299334313588763209368721195406033440335039795584023965856836025833576402742426185229823778500705694210974341563890810533129792322808736449424911515758040914277186872685831237496952261824168758033]

RSA 暗号の公開鍵 $N, e$ と

c_1 := (r_{11}p + r_{12}q)^e \pmod N\\
c_2 := (r_{21}p + r_{22}q)^e \pmod N\\
c_3 := (\mathrm{flag} + r_{31}p + r_{32}q)^e \pmod N\\

が与えられる。$r_{ij}$は1~100の乱数。

$N = pq$ に注意して $c_1, c_2$ の右辺を展開すると、

c_1 = (r_{11}p)^e + (r_{12}q)^e \pmod N\\
c_2 = (r_{21}p)^e + (r_{22}q)^e \pmod N\\

となるので、$C := {r_{22}}^ec_1 - {r_{12}}^ec_2$ は $p$ の倍数になるはず。
よって、$r_{12}, r_{22}$ を全探索して、$\mathrm{gcd}(C, N) > 1$ となるものを見つけ、$p = \mathrm{gcd}(C, N)$ が求まる。
本番はここまでしか(なぜか)わからなかった...ので味方の競プロつよつよの人に投げた。(あとは復号するだけなのに...)
$N$ が素因数分解できたので、秘密鍵 $d = e^{-1} (\mathrm{mod\ \phi(\mathit{N})})$ が求まる。
よって、$m_3 := {c_3}^d = \mathrm{flag} + r_{31}p + r_{32}q \pmod N$ が求まるので、$r_{31}, r_{32}$ を全探索して、$m_3 - r_{31}p - r_{32}q$ を文字列に直した際に "TSG" が含まれるものを取ってきて flag が得られる。

コードと実行結果
solve.py
from math import gcd
from Crypto.Util.number import long_to_bytes


N = 825649642553946328490267023836964711129572425420611735966058683161869803283215266043480304824845111624861250510300789897618528373725236423187676275540723601517461477863617597011363813283912432725667966766365026775315273032389820659978567288706991615780840356377692023530302256488843866125445518514159949151341302906334427920162274058604910216851679502301606913882631899848196176184869193139522404440309942910091771387682701129390460352864424830348225562562360798114543519040072738973589496238169574712021125951918581191319660444131208154266965880763605102083738906048618836339364123455800563079686550795320715569070950383562791508039623249322653728302368039046435890273004852830380582259381379374039796805699684302425495704593736270681712039539888533167142142765955179751586182812597170124069636258732736256419964214220827795321240503521422326812202618089257462126043183583634654484130648706105306514678814826193407457179729443893215111314101986450773258647089878553484580160898905112473766432621689270421724705692314938092837187623229862232768861414241149888300579583906809606951755783656480333567845708998833428922469617739876313360808161540844790197840546900526733781250294563399708876853695183965156611592433321609232870013953529
e = 65537
c = [216949660113004296009259668300534993020105821221318058006221263360670206317854729377127498966972283960212373873547330855440142797545309741889850780082659137610701979875179586873874443387642727752002855684656612531771726640719619633438582181273632591174743374976090502725516525885649093905605104721563399232764370559319686543630287774695705426870288054780805886884491921016573316007837455531795089815940128261459926314061675936701853891694922813812049198405143262252257099312547195727842816568803642048524919788798727173501410164791200503759725852008322788468585177000946058954376320775607144975455532111394214266917076512741107919519690887365375813957064331707593146348692088975009680548447367069108122365861954880530389519192499912982109549734460942531549235319024383325646695977422842496129015105711419168291387289261442326876780828831973504626810114390393171510701043844459613441935866520624226443174255547675337272814485789089748704744611293531866397945075923707673405674255016158945416605425851541327230247596998795502825198541655593403244820709102630950288980468577818885363399136518273886482465020899520020602341105920756064956597718878275469302368240891713678237060859367758977108111107933911057364648831809616527933975723117, 51583635406618955557208798031147624649359706997894321317425067509557409512116347444691971717840825321762282106897546008753785164833165735283131541939787240317392863610293060744566401835537980790207397157473353459308465185310448343425023613481948457654298839653100624447942381541884995059659699037522150612679044514348858020667919011125524446639504563302142532251867486178285416293476451790876580998880606417421785230210127509623702346941936296746981361883286562134843938677366992051966798245452706267605585603343692317978016819231715857307068735137934491366772647205384911936853453614749551699730791191018566008379106281994472029692350910797889644569036546867294655273181462430377208614429223739315777635835706958649013243072661344976013622590769802411067495079611595519804951450278527673197146382744932947590521139592026885731486460586150261233447784465288806771380038058117150486428800081185435164931180958432508924403148226070068773739680914512869613605557080705887688517559644591799816707690740284686627022035112212121219985723834634142605435210358762666042844405511596009472018561856867143612554070064099007428461203339190177160487413537345360150848245438645956990549355115875764873560054219211605254611269626825489483842640018, 201429502572151907207669413393863256280229442301921016587875714023960062912920341109831247721910975613770542202242828341965723835386146006841058216933291783114002288320053664098945142941318519156136200671061933895553300458663647271233281358522594778147710061134740616893573333089485531127539828500315987612459716568044141593023609004381408588936566801447929202427928080539601272897572851547054648712652438083012901997959628627639447385055239583448692217462802742260141473445025292327701724092933587996835353444734828088406533758866626444792039437356890938357847006239458250704575446629903482282367142704404629013815989561413016107285061372224468791463151049756647566264554193099293900691587775208639431879674668031555020647808771495691526926027418625263124211207957569211422342040847487759542574428706594890204245691023052514898033003324502930414363660846197386147753305529070262094540601294948100028557945063651035028338388259335341372029755993700224771762797479049478003774997264464877472363393002255610570285454693913941545714976481242299334313588763209368721195406033440335039795584023965856836025833576402742426185229823778500705694210974341563890810533129792322808736449424911515758040914277186872685831237496952261824168758033]

p = 0
q = 0
found = False
for r12 in range(1, 101):
    if found: break
    for r22 in range(1, 101):
        if found: break
        C = (pow(r22, e, N)*c[0] - pow(r12, e, N)*c[1]) % N
        if gcd(C, N) != 1:
            p = gcd(C, N)
            found = True

q = N // p
assert N == p * q

d = pow(e, -1, (p - 1)*(q - 1))
m3 = pow(c[2], d, N)

for r31 in range(1, 101):
    for r32 in range(1, 101):
        m = m3 - r31*p - r32*q
        if m <= 0: continue
        flag = long_to_bytes(m)
        if b'TSG' in flag:
            print(flag.decode())
            exit()

TSGLIVE{p_and_Q_Mu5t_6e_1nFiN1Tesim41_nUmb3Rs_Becau53_pq_acts_Lik3_a_zer0}
0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0