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}