Zenn
🐣

TMUCTF 2021 Writeup

2021/09/10に公開
#
CTF
tech

はじめに

9/8-9/10で開催されていたTMUCTF 2021にソロで参加したので、解いた問題のWriteupを書きます。初心者＋残り数時間での参加だったので、まともに解けたのは3問だけです。

Common Factor (52 solves)

challenge.py
from Crypto.Util.number import *
from functools import reduce


def encrypt(msg, n):
    enc = pow(bytes_to_long(msg), e, n)
    return enc


e = 65537

primes = [getPrime(2048) for i in range(5)]
n = reduce(lambda a, x: a * x, primes, 1)
print(n)

x1 = primes[1] ** 2
x2 = primes[2] ** 2
x3 = primes[1] * primes[2]
y1 = x1 * primes[2] + x2 * primes[1]
y2 = x2 * (primes[3] + 1) - 1
y3 = x3 * (primes[3] + 1) - 1
print(x2 + x3 + y1)
print(y2 + y3)

with open('flag', 'rb') as f:
    flag = f.read()
    print(encrypt(flag, n))
output.txt
2870378965838324591930716372043943202857808446139955114178972466357197191646555386310681233993639582571871810351336802365212612829432807326876330070965674249357286034347008657883629500396346167749508691814871533203247809103597516756034759095100637453841622270471713637175966387708675681650825362129940918643196769504213592200456774778948694877618977617011530883570013644245183319361244368215398610979149060320165814554577615652211730789657513270358973557241707978338139984414979470166202562114202380919071164176972055791789476453657467515306951139381362369978138151345609568127199377878026652554062731521632501476705069316208464363846111869669167682507916421047852441782552255491492824812854004513204360809331798274954243569021433963906972169417423418831314860109084130511234616069241809687828168649890352090249712449906176079861456197001597695071378819897916782564243557316380779536239285819430145429214343617897807321057453881231873109668847371444981597545948164776111805671836878974593063507806022594658899187647227705150195530817678931698098259376629125579883657290675365061062988342506737677539253213873486072882314916722654639439974767729667348308089822272618812141734747518190918131475394008358752485820114352585363697943409142405397187811488425763607870435598703473283558863875082511735753198985761770194691897333996772347209579690094484306582887604607085834235579991339081114877411129747659636913741732353593602493602935647498099959376575507080043282822039059772712513621914435714472997174303938650778721067511657786410145042462581432379653230157438512241441297394613009093982995995721488753402291657942043365728675978004538612865075473060797997060824242663659400972803009150895091065010288979279208343727383126907536910816233381252213949988179391769784859432462536001028414576853626404313552019318821609411415846740546897494827049963081729773556670009694396655902808674253954003664489541274216766985514320658655385155404804471285629385163182065527325960787883285164384400671878810956747078706832300082761043350763868511932582950753204256098035119847645083342729287063167616495769840389702639642784779646124394274187760742667519368210034941587941073935227051959905320338654629277413407444919186684576561532634097854731829455621571431402040561443044139818425476711378475625762558700335148767065032908314020963523681108498054768101383636397920349166462138683843364568104852099786972138269207828354678771871957631305996408564918629611147162610100969994085549017653854895147761379806516965159036735885697873629236958604838297316909096866364056640064200671318939446575088736134834054178902097259981395846912668763412552618135586399374878369079393695944896480784503275721233694160817424918386850099538763638119036532611566641652505437494379272489263685110137046574303306123483008690943610001403933721637756187395490525025216826398321326468190996213618276820580272764947465497924136451423383678199000687060571477421196675667167891260178408652655959836575935636974063946514718181746525031519883430143656783652516536859306736796341726896446635046579279623124614077795247335483809777
12189833951051730908370223331850919218243946952509718500560332838832804241963905158328421240593088009803147267463017892895712859666255758374859924227795693977692365712139787589267299790301022569583587926463070427550028215313969101326713297706315888193599192042874908901003626554054277955414415385731879026734954423731345798786722561845058120971545040892322209486011914785265062492920550158388814114563652053556586072198675716423094480300266767587890740892336081818352390563087579428787330255230317293748493589325405374600751428190100372051406745392483110379355174892921101536441200795867134576643519454074015675127266952070892796128379921598800605300182483946129377809823776730697790309647647190307296418381398693697240748290194721934318854836676911877413259621512269954316351093519057413607079769428640924051837599266617014518297183874986708528679104069884291849234025193207298171674607085234765320663128701647504631036578515249726222498212335082588627266250272379931767054363936707282364911659508871646177814796817889070190457673852047527357122774587607849820636184925240369923701314690600711989307878295308586902537853388274176578719581752448488589031302166298788451585838083076238353895213222535414766363665801955518856592943846521495707362179018672726109435436743723238172556767198562368516144637629110267835795311939660130673691902395560229758574266655957155862216872908603510940031334166746559195296408939506394470132257044581183533463281253397503463926598923844457702097679565967501579961386522021817780961888842972793029114864422478835769322906292819387383748603289494044561725080616097794190650081867485792883883943744138857860775053197775476414639386004107927910470986208356664914803636501181816689051948285860692212458532201937837589900582214489550639269506433713180672869129866286880957012266595540883727015907677897402607614096813204000
10685466258462426438601930063854796559353071021872734112422666943995273083147678402485604005469990666166510724614508657976179169486278649913444601773228981194010779012945440827279478889951033722845969569487499109114807920422465585370352647531485228491726069752258604141544095143726497561287074963919306162501333879324320431815063767836881722714585596416818455332140968159290951800146179728839649549885714902391429304093259377977040947324691472037003260741076844850530123289350979761389302226559515709663477520315215796685387805223395013156063533568746725754875786890572455450963004254041206457627272694223378868063657567852741748730175173641019445706089775572094353061394171203735646557579595881047090069929263278434116703002648581646489410683234908239597741887334283851760107425225954878508549100715448112116790430791154066542690753466803004681805878269979001221299212426591974298670638899337600244969172572955344326969720268282445856163235666525453179028071857247486445419793906307197739042430106158187925914823345884448535360673122213977744765084269696399126350806729338388901052234851028732099724640679744428962810579433414095277730427540297789173682400086721025827804724736734372677509987948167038979141434755652392244734118982644329505761227780128318076798321983092557417882569724665849318066642854479540185619304472196160849810402529549850401440730174222018187759986936759639741288629098555521157461858554745777119186003733147607872641752914478401134544544581877108606144844955497062864711396338329584713840695858914573229254445387595034317081334732222156791041901660170883047145528155203729023944309061959449827690809614300474069217485344927501901373264278607167662413547572497683805087479857076246143962932587232903893219862365333270757997373558132982228573327073639550742090562057353483860863787775987229835303262050707215194078693398663198
1295564702637495685309272079895645034267002212576577351176786924725825901033456751565363132227845395192636014504044948379030468685845611242265523726539023437126669783303765124723915472786629678436713048730755297486348344599742142845784560313837239832937917360379066282667491918054529416764918515780567145928364634646722930481542026187360739697820492335622597715014255829089436910724972509085963133800806856075152036053630879580926838241308921405124424958500485001162000846198656477271924822124768722799190195854806533587717469450248664509344104461703840455934612539385694033634268205463024167234754553081069919678171898669570723347606172526826003367647892759191360901723076962059024693433937573808414595918813154817183122218324304727720231993955442001953029300266308755291774280607633683770298830407751731984235360718897231362141728129903067324174378760053260419744395257753779565716943029464080442902252184316484343234160161564121269883788523966796266675498603214422442299610994620373055814615356464754724264668947373104292350153322562799134518201535870142301501474217531998628211638040128486684200215958700680344308113382908656637378359217107811764695801417920230331446471475336055801665419851805385433677261916024902543165187462517860936690178095112472342793009281361928879367602088695738746822374043544415398979893735410561210643701354068887205774369902436302903034048756740583183966251194450689131063910079690811851244607443172434856486129471747053074648343069627212505795579741010868965206480675568896896528625130571758075102146302306655426190892962618128161759734724982773347245232038629926619247273436934947196867813659364951484832193239178102156204300353342841972762595259292048840326449938071520689839586933982775979336248771535685895403976612898604059800532915376510948151614460338199157528220842025853852584958511622657382701623309639101678362821929006062524756352592131742510350318470015268920615837821556797760508924258618057921324240995910743034414956163701330735308503014893515707188853735706296571253748889626515245648558769422283608966241496382223293119306642490794180175154686106323945765280777140420938641267467633112805720348438191023736935327334544026698324629536721807051447503613438954736205208639453193587326470160505597834244792859179593877840449441035962707113092034561698560285482507381177956117498938436596192528337690808299050972992206796450167499247505347105318901580848542927515381051973057219542622235114029773502036331075236848879130640275120244541018979621405480997745366565533911987665660584132852855158311718515145400486762846976972483867689062569575052791463761762637757579908921446285546575036947648139847182684615282524513693899858284291993167395096893612172061860682116974864364966362118833708791957224527084022917788839602167742342150067548893185747653708657029597051779997866982601553339504636518951723213334104705177572536156329378433835224612846933662252315126902599937489337158843870992464520248466088492159756466651557918397098886626028193224320040156124777562920457488126430654110240828124538167742484933802988652725530546987842196376

prime[1], prime[2], prime[3] をそれぞれ p, q, r とすると、

\begin{align*} x_1 &= p^2\\ x_2 &= q^2\\ x_3 &= pq\\ y_1 &= x_1 q + x_2 p\\ y_2 &= x_2 (r+1) - 1\\ y_3 &= x_3 (r+1) - 1\\ \end{align*}

となる。そして、出力される値を z_1, z_2 とすると、

\begin{align*} z_1 &= x_2 + x_3 + y_1\\ z_2 &= y_2 + y_3 \end{align*}

となる。これらを整理すると、

\begin{align*} z_1 &= q(p+1)(p+q) \\ z_2 &= q(r+1)(p+q) - 2 \end{align*}

であるから、

g = \gcd (z_1, z_2 + 2) = q(p+q) \cdot \gcd (p+1, r+1)

が成り立つ。ここで、p, r は素数なので、k = \gcd (p+1, r+1) \ne 1 であり、この値は未知である。しかし、試してみるとわかるが、k の値は小さいので総当たりで求められる。

z_1 を g で割ると、

\begin{align*} \frac{z_1}{g} &= \frac{p+1}{k} \\ p &= \frac{z_1 k}{g} - 1 \end{align*}

となり、p が求まる。そして、p は 2048ビットであるから、平文の復号には p で十分であることが予想できる。仮に足りなかったとしても、q, r を計算すればよい。

solve.py
from Crypto.Util.number import long_to_bytes, GCD, isPrime


e = 65537
n = 2870378965838324591930716372043943202857808446139955114178972466357197191646555386310681233993639582571871810351336802365212612829432807326876330070965674249357286034347008657883629500396346167749508691814871533203247809103597516756034759095100637453841622270471713637175966387708675681650825362129940918643196769504213592200456774778948694877618977617011530883570013644245183319361244368215398610979149060320165814554577615652211730789657513270358973557241707978338139984414979470166202562114202380919071164176972055791789476453657467515306951139381362369978138151345609568127199377878026652554062731521632501476705069316208464363846111869669167682507916421047852441782552255491492824812854004513204360809331798274954243569021433963906972169417423418831314860109084130511234616069241809687828168649890352090249712449906176079861456197001597695071378819897916782564243557316380779536239285819430145429214343617897807321057453881231873109668847371444981597545948164776111805671836878974593063507806022594658899187647227705150195530817678931698098259376629125579883657290675365061062988342506737677539253213873486072882314916722654639439974767729667348308089822272618812141734747518190918131475394008358752485820114352585363697943409142405397187811488425763607870435598703473283558863875082511735753198985761770194691897333996772347209579690094484306582887604607085834235579991339081114877411129747659636913741732353593602493602935647498099959376575507080043282822039059772712513621914435714472997174303938650778721067511657786410145042462581432379653230157438512241441297394613009093982995995721488753402291657942043365728675978004538612865075473060797997060824242663659400972803009150895091065010288979279208343727383126907536910816233381252213949988179391769784859432462536001028414576853626404313552019318821609411415846740546897494827049963081729773556670009694396655902808674253954003664489541274216766985514320658655385155404804471285629385163182065527325960787883285164384400671878810956747078706832300082761043350763868511932582950753204256098035119847645083342729287063167616495769840389702639642784779646124394274187760742667519368210034941587941073935227051959905320338654629277413407444919186684576561532634097854731829455621571431402040561443044139818425476711378475625762558700335148767065032908314020963523681108498054768101383636397920349166462138683843364568104852099786972138269207828354678771871957631305996408564918629611147162610100969994085549017653854895147761379806516965159036735885697873629236958604838297316909096866364056640064200671318939446575088736134834054178902097259981395846912668763412552618135586399374878369079393695944896480784503275721233694160817424918386850099538763638119036532611566641652505437494379272489263685110137046574303306123483008690943610001403933721637756187395490525025216826398321326468190996213618276820580272764947465497924136451423383678199000687060571477421196675667167891260178408652655959836575935636974063946514718181746525031519883430143656783652516536859306736796341726896446635046579279623124614077795247335483809777
z1 = 12189833951051730908370223331850919218243946952509718500560332838832804241963905158328421240593088009803147267463017892895712859666255758374859924227795693977692365712139787589267299790301022569583587926463070427550028215313969101326713297706315888193599192042874908901003626554054277955414415385731879026734954423731345798786722561845058120971545040892322209486011914785265062492920550158388814114563652053556586072198675716423094480300266767587890740892336081818352390563087579428787330255230317293748493589325405374600751428190100372051406745392483110379355174892921101536441200795867134576643519454074015675127266952070892796128379921598800605300182483946129377809823776730697790309647647190307296418381398693697240748290194721934318854836676911877413259621512269954316351093519057413607079769428640924051837599266617014518297183874986708528679104069884291849234025193207298171674607085234765320663128701647504631036578515249726222498212335082588627266250272379931767054363936707282364911659508871646177814796817889070190457673852047527357122774587607849820636184925240369923701314690600711989307878295308586902537853388274176578719581752448488589031302166298788451585838083076238353895213222535414766363665801955518856592943846521495707362179018672726109435436743723238172556767198562368516144637629110267835795311939660130673691902395560229758574266655957155862216872908603510940031334166746559195296408939506394470132257044581183533463281253397503463926598923844457702097679565967501579961386522021817780961888842972793029114864422478835769322906292819387383748603289494044561725080616097794190650081867485792883883943744138857860775053197775476414639386004107927910470986208356664914803636501181816689051948285860692212458532201937837589900582214489550639269506433713180672869129866286880957012266595540883727015907677897402607614096813204000
z2 = 10685466258462426438601930063854796559353071021872734112422666943995273083147678402485604005469990666166510724614508657976179169486278649913444601773228981194010779012945440827279478889951033722845969569487499109114807920422465585370352647531485228491726069752258604141544095143726497561287074963919306162501333879324320431815063767836881722714585596416818455332140968159290951800146179728839649549885714902391429304093259377977040947324691472037003260741076844850530123289350979761389302226559515709663477520315215796685387805223395013156063533568746725754875786890572455450963004254041206457627272694223378868063657567852741748730175173641019445706089775572094353061394171203735646557579595881047090069929263278434116703002648581646489410683234908239597741887334283851760107425225954878508549100715448112116790430791154066542690753466803004681805878269979001221299212426591974298670638899337600244969172572955344326969720268282445856163235666525453179028071857247486445419793906307197739042430106158187925914823345884448535360673122213977744765084269696399126350806729338388901052234851028732099724640679744428962810579433414095277730427540297789173682400086721025827804724736734372677509987948167038979141434755652392244734118982644329505761227780128318076798321983092557417882569724665849318066642854479540185619304472196160849810402529549850401440730174222018187759986936759639741288629098555521157461858554745777119186003733147607872641752914478401134544544581877108606144844955497062864711396338329584713840695858914573229254445387595034317081334732222156791041901660170883047145528155203729023944309061959449827690809614300474069217485344927501901373264278607167662413547572497683805087479857076246143962932587232903893219862365333270757997373558132982228573327073639550742090562057353483860863787775987229835303262050707215194078693398663198
c = 1295564702637495685309272079895645034267002212576577351176786924725825901033456751565363132227845395192636014504044948379030468685845611242265523726539023437126669783303765124723915472786629678436713048730755297486348344599742142845784560313837239832937917360379066282667491918054529416764918515780567145928364634646722930481542026187360739697820492335622597715014255829089436910724972509085963133800806856075152036053630879580926838241308921405124424958500485001162000846198656477271924822124768722799190195854806533587717469450248664509344104461703840455934612539385694033634268205463024167234754553081069919678171898669570723347606172526826003367647892759191360901723076962059024693433937573808414595918813154817183122218324304727720231993955442001953029300266308755291774280607633683770298830407751731984235360718897231362141728129903067324174378760053260419744395257753779565716943029464080442902252184316484343234160161564121269883788523966796266675498603214422442299610994620373055814615356464754724264668947373104292350153322562799134518201535870142301501474217531998628211638040128486684200215958700680344308113382908656637378359217107811764695801417920230331446471475336055801665419851805385433677261916024902543165187462517860936690178095112472342793009281361928879367602088695738746822374043544415398979893735410561210643701354068887205774369902436302903034048756740583183966251194450689131063910079690811851244607443172434856486129471747053074648343069627212505795579741010868965206480675568896896528625130571758075102146302306655426190892962618128161759734724982773347245232038629926619247273436934947196867813659364951484832193239178102156204300353342841972762595259292048840326449938071520689839586933982775979336248771535685895403976612898604059800532915376510948151614460338199157528220842025853852584958511622657382701623309639101678362821929006062524756352592131742510350318470015268920615837821556797760508924258618057921324240995910743034414956163701330735308503014893515707188853735706296571253748889626515245648558769422283608966241496382223293119306642490794180175154686106323945765280777140420938641267467633112805720348438191023736935327334544026698324629536721807051447503613438954736205208639453193587326470160505597834244792859179593877840449441035962707113092034561698560285482507381177956117498938436596192528337690808299050972992206796450167499247505347105318901580848542927515381051973057219542622235114029773502036331075236848879130640275120244541018979621405480997745366565533911987665660584132852855158311718515145400486762846976972483867689062569575052791463761762637757579908921446285546575036947648139847182684615282524513693899858284291993167395096893612172061860682116974864364966362118833708791957224527084022917788839602167742342150067548893185747653708657029597051779997866982601553339504636518951723213334104705177572536156329378433835224612846933662252315126902599937489337158843870992464520248466088492159756466651557918397098886626028193224320040156124777562920457488126430654110240828124538167742484933802988652725530546987842196376

g = GCD(z1, z2 + 2)
k = 1
while True:
    p = z1 * k // g - 1
    if isPrime(p) and n % p == 0:
        break
    k += 1

d_p = pow(e, -1, p - 1)
m_p = pow(c, d_p, p)

print(long_to_bytes(m_p).decode())


$ python3 solve.py
TMUCTF{Y35!!!__M4Y_N0t_4lW4y5_N33d_4ll_p21M3_f4c70R5}

TMUCTF{Y35!!!__M4Y_N0t_4lW4y5_N33d_4ll_p21M3_f4c70R5}

435! (45 solves)

challenge.py
import binascii
import hashlib
import sys
from Crypto.Cipher import AES

key = b'*XhN2*8d%8Slp3*v'
key_len = len(key)


def pad(message):
    padding = bytes((key_len - len(message) % key_len) * chr(key_len - len(message) % key_len), encoding='utf-8')
    return message + padding


def encrypt(message, key, iv):
    aes = AES.new(key, AES.MODE_CBC, iv)
    return aes.encrypt(message)


h = hashlib.sha256(key).hexdigest()
hidden = binascii.unhexlify(h)[:10]
message = b'CBC (Cipher Blocker Chaining) is an advanced form of block cipher encryption' + hidden

with open('flag', 'rb') as f:
    IV = f.read().strip(b'TMUCTF{').strip(b'}')
    print(binascii.hexlify(encrypt(pad(message), key, IV)))
output.txt
9**********b4381646*****01********************8b9***0485******************************0**ab3a*cc5e**********18a********5383e7f**************1b3*******9f43fd66341f3ef3fab2bbfc838b9ef71867c3bcbb

IVがフラグになっているAES-CBCの問題。まずは、keyの隠されている部分を特定する。最後の暗号ブロックをkeyで復号すると、前の暗号ブロックと対応する平文ブロックとのXORが求まるので、それを用いるとkeyを特定できる。

後は最後の暗号ブロックから順番に暗号ブロックを計算していくと、IVが出てくる。

solve.py
import binascii
import hashlib
from Crypto.Cipher import AES
import itertools
import string


enc = "9**********b4381646*****01********************8b9***0485******************************0**ab3a*cc5e**********18a********5383e7f**************1b3*******9f43fd66341f3ef3fab2bbfc838b9ef71867c3bcbb"
key_len = 16


def xor(a: bytes, b: bytes) -> bytes:
    return bytes(a_i ^ b_i for a_i, b_i in zip(a, b))


def pad(message):
    padding = bytes((key_len - len(message) % key_len) * chr(key_len - len(message) % key_len), encoding='utf-8')
    return message + padding


for i, j, k in itertools.permutations(string.printable, 3):
    key = i.encode() + b"XhN2" + j.encode() + b"8d%8Slp3" + k.encode() + b"v"
    h = hashlib.sha256(key).hexdigest()
    hidden = binascii.unhexlify(h)[:10]

    message = b'CBC (Cipher Blocker Chaining) is an advanced form of block cipher encryption' + hidden
    message = pad(message)
    aes = AES.new(key, AES.MODE_ECB)
    dec = aes.decrypt(binascii.unhexlify(enc[-32:]))
    if xor(dec[-5:], binascii.unhexlify(enc[-42:-32])) == message[-5:]:
        break

enc_full = binascii.unhexlify(enc[-32:])
while message:
    dec = aes.decrypt(enc_full[:16])
    enc_full = xor(message[-16:], dec) + enc_full
    message = message[:-16]

flag = "TMUCTF{" + enc_full[:16].decode() + "}"
print(flag)


$ python3 solve.py
TMUCTF{Y0U_D3CrYP73D_17}

TMUCTF{Y0U_D3CrYP73D_17}

Broken RSA (21 solves)

challenge.py
from Crypto.Util.number import *

e = 65537

with open('n', 'rb') as f:
    n = int(f.read())

with open('secret', 'rb') as f:
    secret_msg = f.read()

pads = [b'\x04', b'\x02', b'\x00', b'\x01', b'\x03']

with open('out.txt', 'w') as f:
    for i in range(len(pads)):
        for j in range(len(pads)):
            msg = pads[j] * (i + 1) + b'TMUCTF' + pads[len(pads) - j - 1] * (i + 1)
            enc = pow(bytes_to_long(msg), e, n)
            f.write(str(enc) + '\n')

    enc = pow(bytes_to_long(secret_msg), e, n)
    f.write(str(enc))
output.txt
33480933532879680420013037333629574829314700463453212301292088807465041684485642819768171537612502467080592874497863977520306632073215503336862835498929070856066546827292940854157192853965661835148467015242404752362804661784536894149439883124031247082525264859525384281030677267417046959613808985748040661929196970664183344590360405601820460383565335474474302395314798633836584632339380265159168935679176127803539371528429126259135855320491319272360546001362538183765105540254124819511972057206510318028298156893997042020482391155264875521102213522189253183676882478735599903364794939666397166127596057949720363950050742654860566199778530661015732940660678554626724807448907845182675199584525421806385323078502567874752217610398698658458825610595774008525886399158949020656198924831967933514871014089242423903436047649066652515664774341393936791573390214256978089364634321001958139672365416543522037505418967123103349730306319697708805488384946401606585131415373340642379140628236062366241623065179154
58825738112673638541667590486829317365097583278128766788573623796274477065733795750057850674128771347640731697507095632291986339489373426773754394386977080640903293774450291113986906470105575533516638863112279315247814047975331507424534319816729226154380112241767046245186164336121391131496804620599520952904290649765926550748678572243766388535917900936255457372545075304082941788833951161098888098373358110522441965378687700329799154403163991609318025746082472284784762364478218987529989248660326638415529500027022409554111019739273037027522481461033491684086628901300111995837303106445214100259074396034809643007028455937163217525142044467192913997715650310680986185521042246391865220053238099226197397057694458196633088110193794779767343479193840132350077321010075512691636130596846913480707079198612031977658807231198075364260900618999210784184696101117532874802848640921847234888157082230744420993422613907980358370465345008822171008029672956597479007397264012529118714438069287586783713923662684
38294995141363656877559436188173251418412691100197256393140460308638550794787818744112258583071336294126349175652937685739135357977138397953176497271990297767710542030794806398990554023682078366911017277132913507751558185664635139569788255417043307025993876712483137550304628463892408528989328338637340992672940717254257361166225386487663916798266053084008606550692911925841142228439929420532161810642604669629382934228394956128406912756886949389147160683794554907865869696323211393177967701903261281784572805974924500562725656953872964810319767573063545083240742668949436980464759657463719337298805344813080835521511369688259879107912684260305354707675843624100268265733513370526723846038560186219876428110243911908628330398759197743234592524657695539684581843303494548908564079793200201288169288394460094077561741813262173165439646165583707235577451270415204994942251172966812727410501723125243542695610865544437241860888488542242547532559144457484672728209876599165987900768477477696271024789692221
173691501533359188516191078878110524565620409105195170575054122895742986149100056990824330105602744271426077166635439589222003103879578418621627866885520075444096076993941065051299509781874486214148303515564723733002758964912610627747414925896727665302690447242325061846370395598332895933468032768284728303321023713920812030489008235806716587149675738790843841879346625788695017235865254537678632356985562137500433999093280727591839557144579964589266003831813037586690205319758908936045419321672749733778573385245845768397178855164481310728790057347473684160355869425653628535271350103180838067630293785227299713472587141351344460935290909445217950189380262234653652973964796599718193068724396700669058264856285645695316093061045170185266622023094154307046350208529794422946498765632757830692047818447572572526174558128194822236381673452579725775354687774236087331804610336052378454397199432286428722387772064396026224298923357439066184580505521955595145233227927227265676445738018037704077591852168483
55604138432621575190245084432225437740107338683949123513741012241143565577094084079820162408487108514184626607684897503559793964803525931181817078099166135471365894498715551982739807484084230252080755209008517117769543016187070970920758379785818347419138118637580274993796413246691750598447061182621333086231389416565774640910653106695372589063597258516611375772236848818139213421182420546866667980473793303245916905195900880904446829562511102213175394897425442513143509174775556266868584748986551160405710140509748401298884604334095746804881957102189568167661695179661066772582451996689023561957859997262612931361457932317584603105371339525267340424166164007101537184540981834298701337743948784013117395657958272795055447176282586457592697247379209314150581919240357909047580742996075127182956980718437645391096369177275397537202863800671195819351549263693670058258862448096633956575635881105229818878813606568174258715816659828787222644762697931308472612491024644779370010123373899966766044232750627
151076799617660584048707988001988649520425103837142302746293017421239791386626968019741698920726908342381648339968998973714680876609987442565901423162636486525342831444776527344607855861374752363391946804989069844527317474778371630528773938857804576514177517874234468874321810824023211354697375116696870482551988156916764318988566628892748362854891740954467135313379417832090252073605106190772817529822912815219483685309543662768557478107467456844791338033618895850231616904775833015561078329826674806804664558611947927426876682821100475974294591969826824983506940169263701362594080100780280988248806269449903571618898914220227793511259308751791734589576487940756673208239632114366408115544121474989143950670083319220275727555246777893443184426055866161823065710817673775009156920555217112765268366210728872687919739689906698029808738693347671904795757739462993804103748075439719946086044982724286684647666307504258246337374230339263928897815763121372617066645419993204557831109671052735799958681311569
79486173823486161688354643441031583347037024469965306440854478505231336729232740698906052866489054399267589634783970379219249084336317426540009802830737495181064439146833928067181047214730940839457074183681953931068973213985767602077491214668875224228350499756231685320043416792806581575089276874763230873356828178401208036703483327480136937157486985590559503847588218301908210767212026452299492775996738375185751062400870059844962194794173706569101486709575712871355125538895782115683429590856983162267068368885523871102779403797765807746409347525601056308559793418318920629536554435222886289672714112218795722867279503640145641167441486047669554867745260549534478110085504567314377555652967288787461915619875586966339316858691650733873596952922166877082619636616041334937956073110692024723428734779866953847810837279414652212124704497135412424824963544287787748535690888352342447618011930636667084996361630602147557567298878251079177225839564543499879666398437330702132670987734498598498828064843331
81062734829272769756784085051551855094771303675961426783580748839187245328044392943566230821255051024729061110902563202492020943737028125291618434444020798218306225569528486175801082995781186098817409366129362852891557070576329438514704128632925085572631950077480675559133299996133771300714669014471912009452378343702698696154176909288644403165239337885885002907495182025084290849291405265977592010829322637907607105073057381614563188354010683971861368638644516235992116497544432397235893046568273968374949248764196873825691279793446938375996707540094791717698283256050784339023011246224381604523918421844631047945372750019220797156767131765869457140205016817917033111993468229305752213024881146163937006919793604750302411310080067132089167659687457548488410876766275198690767875408118392457932449201882999461984112158951775355040385118007292558948829628171219493174768354054929377347514941840645653244609034529638302879947171462115440500759405256807206641647248833685159363595676811726013210811925021
88475559865497062001086656159718700594462826784603119984695344660108350116801835833462580567239000564518254010093294158245653600547018612948019281093559189861158094090851443005443047378647033710559790434326486479481504212244190732334511623630748851841704508650917318715405612263256023297711199507737854467096303242542727006798987925016125532917667329623422520721286994365204542627959253183711168836575243810422030343654020542297270006490679731407091993313932004626715106373660914993836865407042160829087366908852673039008781504719519281603026552033862119985215319615795613921175202097314446105130219288048959099836965607581244151379124286682542024757167447992356582802653424620058924642839250668974946916549890226108835004494742129084145425276518221882322868802433640936581836054056721249116322287691236908062622643613689220273271636565566420911027580614220277647960267326014106655954762175075027053407639756046240291693897081144961524165742606620301006957519842737444531578709931938467689462622952193
11748770534166235689208537627662266370646767440152040143053285354750982035688521242675283858175019701933223130251011489858500862186155362964717721684682586320343770940619823637278709423190149643870856615871910044364054677743916297768607750739404025769903861604447479979852120135605410768527270739159007898741047617893785613770853854201680714629670440053629076904322813072033483911306805118873407260913115917550900310831750184637396906311543775396182920048490042549112025241158977573373060752148329758224785400773608372599553304567144407388347478786683619559710636761393265144134566102959753680564293536900436480509761638221971709725591792899188571273354725459694009445166127385498800107923652634627742524197256293883245900597165077917041148501713018614942682099308478811749461241322017353054585633185043323514220107385148847857344097187208245785773210236395497031175698788025099647220871430129211943522785941398591934154142374775398039530054089795479499666683922381961801426661598676106675745081109663
84277365233685133952696317768832611087704454158775423231223322531034780385145030267308511330460662036810999047402471359027959651836839545754453707993904514972355329422973225078029515394538264765172232958997139249363262964525987632657767621169230058327418871476198746550472038382340355687167785040965558757658502890605824045870205117081608641591104892172968374669771196271122009244100182486110928155723712999647891796658906637100434893576106948801063996049635515045759048291235656533942091332480365057366811524560640096994559488902217930960759152281755778236149438588700323672098764998485589676034149324047455212823766388339501900645239158710272718187118881895047574763298742241274383198788803494717915260029876679955594785706356038477035220158466146801352367408830963985475904988050624209516554581183886437401872671152726437833197452479126341700639893037261651985928003559804921341101033040752651069460047103310517877105286845946145438656440240286863408415986279045704598872155923069457994151849594647
155379385428893365963326604459547521274838408722295691783124662555408484603620456054849266426982222726575968089119901296299085832070742826533746239360327308973648971131360079360094371628241419231800575831066064780372808000718397872680074651218657059085944511318285710174098832708012220565180354553862153680189202037872752271389802784313894116990845005171480692471290790295594239739993712848979253159329020349914322861358003660191550744186336158193956345912107546721297486312910827657577354683167514166091505845259846633120386487987226497749314160215910774507479401088794996248186965333238453163361304040800501796610324120213129084670136511474327812320540861520507836175880827125346725569287832969321789237896140133577696534465657473673679397794700611893222926796875584408634467548450210001763158357967384810178299194562915283474999432821777213629461962211246589022404426460182990194832740242827503807804981621380614734755266710922503763035090046574629561302415271219669851064791857105558578061245731700
53561197482217010005623348391239199695061937361374139018667414538197571081742797585179892422621553909632857733432881006431701969334109404589752984733099604838994509393640095834979608631827422515057529914398890986875790264694846687991206497840122617996317330098552471136286161519590784061567486959591107898420732440096037985856510941859049799603800755943778147049340413784799339755429213541759758374338426738356195042764759140159145162976375703863513698339307874958562274327019643696290032024621233241981407549487646934356163048455649593346046652225615497161295265375866594142899099870380303814983682769649578988149839609234113531164593849700092133888792233824368020290891277375771089030841541313465858941835074628781541173333915616627391797312917359557017998675842982233826326890580904024024925977741857533701212299966990705611291784372328425541925281779490896588889688367127789123313384316810345418261589768135183171535714022138274628974547197475211624060536773722868536315605054803515458682823760935
5574519895540419195749329879898766947690039159178633786717404170066556713113376145827588775801429759338411027091950792409042931247670323606595760124379145354049055103161958215052638038796141021963183261659060775048566407392699055558533891865488415172169855616780461143312811256057682673998972172354597659893264720241892658852284384453054494363839433984984199379980692045531888414787356524301835382484506316379144426045962791198584694181463636011701980867470687716917177039843445711725730912283747891283809801114627278587336983218029543300938525847246694765530035868837022226984527457428924926546736021881396033835691390561758976327291018240793665602258036974494483960912177708791142296231387498654629443734448817416822583092383896524066600936979654896467495814185209222368817176816443246540193808940428883698007184279612126425402374222207866143717134844785623021979365530618089451906515375032494592534662034791754270581973190360401706478008214800453492580177337314548366786885036689297512793215647281
31574261458973885676081159392958098475105612203141018254398076279104476848412478360140731776571423196260957856787619629325157242264424812625571723998078467187625522995605420649589671577134506372692601491342234347102961102713115751391553868327060899257622580278751019342098675597507216759941959088191068049971321730180296831187595573067240723086314588773599051013241351898171372592277424366361297101008967152123596834344635816095972813913112469664768110294043468775618258415069582346455604515403847862146554547227838957676266696397729926070513521013753940903936614685363216040563566638815121541994613320639186118606988442619160704738144899069278133585948362909688322106583278096101787705804893710191597880107501716454073172855825838507201905403375373386081710055159377797266934289566614260205610670096021980030710191046982852153270153031878121471094344699825117571128064163856994673555500581041493259673618364382330505640828700770941832380808810939094281097522299489819029808639103779897413992481892519
50408875882458045103817216930783090617623480940906905314851308915457266725528613760426403379617337740669103758160713267123596421491719891142023181297911437205410768314670754147903374140243795615950973941490253427067573033051926964915832517219443016328076895172929742919851242675654781220191021121525110908419127971538152763293609014499716208861673268521188514144734120130588319559586512700804057698762596817772987955470631295592485318459061139401326755442988605609225563033064034134584526776144081460599378178579357394784530825556498611889197782680348802518506832905334777656133689603865896022716086847761416473628472300826609774563546374404903047270525390087168872850683646384881179840707754726694092591056514628864734465784003072359221771322132928041521828522215388664020502424248853925847880932629844185110438612474719599462698231905546544504479218150157314135436051216834418632312866446593846685489508352084126004374423097995519675608971311696254126270565610861338139778796674625338183520660467380
166733535903189579762807819350298444047543177445226889750925091320785236706750493833222830230810031992769917884309471083065566990870165884908308166463884317909632643847352838655947344719459515742352424873593403264457741479226274897836469241327301640175509634896730509453407547717716396100779234556364480609047001366048752254355843673824410650095664928351153397253317157013216261330709152712246762486347819303786965916404299559823813938528441574558354593444820141636224546271767104308038037038383523079508750876467737895580128244128095770952009107292716204293341781156066812084808726877808320947364926224286325302060881825481736548246678311984357544108808434131720094443414550355241253665349847888745738564966823496365782586304025638896920497498278735391558508728021040304940346534397673983855962096216896540274827882484034512585667998161117387409805018005824655155088484198486085795046386997259248425643480841041507912606712702887070117187629222529450131286479809373798807333912208904702571847799937937
62857993454947830442851028390215795271696411262128758528864716913850178461515878923436803889426424151873907331027676498441069310159226573070562981227066923829328227697683938810509756046575798638471134203734345422314485169468487652742824955038659549851347326242890405133406393469670168829773249505597831957730482926313518836260188517341668059681824776931425935279217672194479413878023310642269046150126183915008987248812965850652722945964123794826750115731078774981856677019691194946203916007967928614848186102809699648751713664304758611097115980522897862739372876006676755548757267074601807273310067538993798856203908851749729628057443153779195135406982167608832925329240254585673524502875740528936800390123296129041594265172510784711137039363006392879100220956907606967008444253742332045639629655313353753102777831168895340896331400976113016947437422400529622830013955850528331739624064097329102753393214666695312537011240077943761268334870961739654617921133545574518458702291556983563372364364689241
164578009970097626818293194593172511235482840879944446743095212337903557155415175620893433056291764958459929029486159346124683425816012209326173652084238846771269195267127444080122781503561251682105736769817200103510032528562115237037377253971155106867799621498137279670134933167874051404612460876748313175894634353371044338345564890812498990279937157576061457444871984497157568380644460189360535536530784379740143597331727155555124032955080503008415991152265113428278553452027834760650179840130884434682635355201878988503315297456405771050232662573549725509982375901424933653642046694370633364202307823335648998300575718191839815323806870747496845989872684824806544890705209715148197317097118266240152205644577160362854855204577793629910199848446806226915698774488669321357719318256326106166121286697783461753387453531003622765254855220836629153819215674781633320721751118715641002363411461157053739199751353526966381165397021148299775738116161560562441502842544535131182023755172823265145803172961180
37971663503262251285187689458768908652661881104915596791267756217204230481467635483239068246366750519856089317853028342513127018452478735621413092213392640453125598883167741758636272034150261566578194420466288312417248854419310324485894795393748725124911891549925748411839904167716260539146301148697529132369988229601781292361661656550934122945470959669341244311173041190025646491618845009676907219067258889715413224751525213289752193270357134053272484903310405454206061433192172754753966117847167728454700560871743624551562462598770165792674210044996535665348291582634503025519560295752373761931797077239639195776865400214886262623668295230661067255225729180605560586374954761443599511313130549524046051577892371139447445294177319391955339235526841873304477851758176786261246446827585568611355740717893869570886546557475499289489811118115735026696908745092019716498293858939616962843618554005126981614101557366213295953356958639135910021232484807486680673350687475715235593759400668027755398399323666
174848114391736155852252885333211879174365603630245681364345612727055792975158033669278647400283199430844441062400892699381712038313924569148971351813115700916131995157602889165186967449848696108984766952621730200893839037890214313151005226936967372041191385056270594491989240060036410304560991968913924934778307728472708357546196066809742530979361238695340106590176435154209933658091701425163440908109020837434082343128372166333242934105673720256204173008798261733672125134855655087876789017185467576554355775739129838550658826183352031958928193970649450198083477228871991936496897596241827851406221771922812724908455761694902469012901224296690662300454920308670741532692119080094569923196808908397867719122033043140129354266760260724989897677862208556141709109404577865163015830049298234036002495070665530079605789898613776234509143585661869686956798556842278164890997100947711155273830275653079389638148575589209760039615831050829669959620202265212681771448031791896389429106933206264681847920764968
31860922950694590388011152775486713357920071848631912245267674543915083864696644636685640718664379860416997787340261773203112216791478457897444661845404365609383103168423051668467331476840410194148722734184246923625588641040651576106951029039398154290491552435211845075381926472316509128747348309295552106074166292396345000101109079348419891627487835759160753225512963050767014231610550573376772937227462295850720961091106574764275488350158562721655207020059625733028420978215441210847238747393142725423892835695712515500580147447006043006021641263108301357498289139009132803124471015158322717798432399116293231728527509129954002341478624900453613463035557376077084211984958102334325094950532562098519914126919417004772472039187412206945327305943795819636419929965524659952042938032020226712893920906356681564782379148315180533417888680220999650499886736503144902704641256389877959902874263129097252880230698781951775823715160995407603215189264659040261561958467230995602142806469969212739782968333259
160911992858044510275641001863247334238868278133557452124440291095475385420447271835920647995097889937007639363357365780183310162392580745085183465451922234808042790100978875091463653869707281689133197316051271899648179104073812620113447857577698585517074237650613608158332630905381349965748753986133401850103472842164273897633806408949679908167129267207829315016636828978301044648508456763883473204657790206433585621630394509024149092324627498442305780531991409743804624291604534796140888294623891575720841595230942742967414987520512872630981629955786430876292260950515660880392049757572015192540007474922895335090910080059335200888054457417264276334242235166788058104454455713925033180551023295180588635533451106163107235526221606641776898471627071933091916198876076302609488560306437430598869084384990995101790073997392475961898025863473693990376555890012403068099864545380408280544798602000795298758322760813029785933799442306105034318871977997471367516896052245844064991044480400403149644145979528
27439334796339758412932042376733008509397754835895898460017196805611240900625360186472531540330359399144712554390485396313365474561420637264131876036756621967840959911281268218864874825688422767139286874211939224899798144095713875119392674561852803363433198868371868398210297287297893754674238289945195015147650728921299128360362549400213937786457590423529915392791911535065288670324268005342442496856611373177104868543377183203678383205063567636943656272441942408170018322057571969763359378951328292746611129471690506424477295905380346589216178667630098659930229628262152496641042110612959017362021638868041375404966981702166783336281778724195791552763693653902535593720999311883373481530602340235243543886374971408148600705472230165676817907861160979795052694099300224355773483013414024622079586941402514833054513566074185251430625167078807842701957339671351808522966114441019807136348428266072521305448718828452918467829807902258131610148679531633684371043476554416117337076108769943295520697077952
72354973082951720237881165772546061722042805193056095765653700302193372681645946142363166910436296275230874070292866820816768192082121984400062258356577536824396834879044737124177979268787352023518626456787028117762059673251121802149427622955122061404740378042424007706857044905408970183257498767359706653851972628320656369672719756710238629508988713479713652539745587208046508510668442586625623804051455905938921420516448319599813403131721200365370271688353700296129503439006261839071422062489103062018663965615554143506670433755144839679096872165481374884280660503901401850953074398855070800795577224301796245562935866981513090392233762232267499054206826951629173104453912249492604344021052406936751350628903999568036325637009118276619882994831613096207599195875156290361863694404637114152952111324016841840134629932897805150496423510161958570790984803976399543804640900025396060130433507329065144515192186560202803937006422520531422650348290509861988881334730119635064501663366714191728466450914537
169235297774742940942021355333816189156217093916866514144397222804106429142499680470202043202652961249057752119231483256629168048425903149871720842919274749143433559443816121809467646900540312246725232604149468633394699211739535774896817819681466703923989721793718210279433158794060422093865412638349201961893401514274768496061998599751372218959654738654228225676485441020849693690523287113360413891431372347718365404340785109535031213242576203242694909345390195057769451445093026949757687563029228696555287901138694025434761487733300661288043927272826415036660006265820235396466013905747282043563400279979810078217832910919157418093634005790579208324336651322282087238793407151461185663804335409840280410175579785942240883772413508571787457304889015222348403115386573285290728676573270716882126059828740082864243212786906812229478671752965405601311231500833299787749197735267510562487374501314292496053407340415795083155332014895563809824401057461031038610125336390709278567186529319346744727431697949

n が未知のRSA暗号。まずは、どんな平文が暗号化されているかを確認する。

0x4544d5543544603
0x2544d5543544601
0x544d5543544600
0x1544d5543544602
0x3544d5543544604
0x404544d554354460303
0x202544d554354460101
0x544d554354460000
0x101544d554354460202
0x303544d554354460404
0x40404544d55435446030303
0x20202544d55435446010101
0x544d55435446000000
0x10101544d55435446020202
0x30303544d55435446040404
0x4040404544d5543544603030303
0x2020202544d5543544601010101
0x544d5543544600000000
0x1010101544d5543544602020202
0x3030303544d5543544604040404
0x404040404544d554354460303030303
0x202020202544d554354460101010101
0x544d554354460000000000
0x101010101544d554354460202020202
0x303030303544d554354460404040404

よく見てみると、256倍ずつになっている平文がある。

0x544d5543544600
0x544d554354460000
0x544d55435446000000
0x544d5543544600000000
0x544d554354460000000000

RSA暗号には乗法準同型性があるので、

\text{Enc} (256a) = (\text{Enc} (256) \cdot \text{Enc} (a)) \bmod{n}

が成立する。\text{Enc} (256) は未知であるから、代わりに 256^e を用いると、

\begin{align*} \text{Enc} (256a) &= (256^e - nk) \cdot \text{Enc} (a) - nk' \\ n (k \cdot \text{Enc} (a) + k') &= 256^e \cdot \text{Enc} (a) - \text{Enc} (256a) \end{align*}

と書ける（k, k' は自然数）。このような組み合わせは4組あるので、それらのGCDを計算すると n を求めることができる。

後は n を素因数分解するぐらいしか方法がなさそうだが、YAFUやfactordbを用いても素因数分解ができなかった。ここで、何となく n を2進数表示してみると不自然な並びをしていた。

0b100001111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111101111000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000100110010101111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111101100110101

これは 2^n - 1 の形で表せるメルセンヌ素数の積ではないかと考え、実際に試してみると素因数分解ができた。ここまで来たら、後は復号するだけでフラグが出てくる。

solve.py
from Crypto.Util.number import *
from functools import reduce


def factoring_mersenne(n):
    x = 2
    while True:
        p = 2 ** x - 1
        if n % p == 0:
            return p, n // p
        x += 1


with open("output.txt", "r") as f:
    output = f.readlines()
enc = [int(o.strip()) for o in output]

pads = [b'\x04', b'\x02', b'\x00', b'\x01', b'\x03']
M = []
for i in range(len(pads)):
    for j in range(len(pads)):
        msg = pads[j] * (i + 1) + b'TMUCTF' + pads[len(pads) - j - 1] * (i + 1)
        M.append(bytes_to_long(msg))

M256 = []
for m1 in M:
    for m2 in M:
        if m1 * 256 == m2:
            M256.append((m1, m2))

E256 = [(enc[M.index(m[0])], enc[M.index(m[1])]) for m in M256]

e = 65537
t = 256 ** e
n = reduce(lambda x, y: GCD(x, y), [t * ee[0] - ee[1] for ee in E256])

p, q = factoring_mersenne(n)
phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)
flag = long_to_bytes(pow(enc[-1], d, n))
print(flag.decode())


$ python3 solve.py
Public key cryptography. RSA was first publicly described in 1977 by Ron Rivest, Adi Shamir and Leonard Adleman of the Massachusetts Institute of Technology. TMUCTF{Ju57_4n07h3r_R54_ch4ll3n63!_C0u1d_y0u_50lv3_17?!?}

TMUCTF{Ju57_4n07h3r_R54_ch4ll3n63!_C0u1d_y0u_50lv3_17?!?}

Discussion