TSGCTF 2023 参戦記（+upsolve1問）

1. はじめに

　2023/11/4（土）16:00 JST ～ 11/5（日）16:00 JST に開催された「TSG CTF 2023」にチーム「N30Z30N」*1で参加しました。

　久しぶりに開始からほぼフルタイムで稼働し*2、最終結果は Warmup + Survey を除き 3問 を解いて 452pts（73rd / 500 teams）でした。

　順位が素数なのでヨシ！

　ちなみに、この CTF では難易度区分が示されますが、個人的には以下のように訳して解釈しています。

• beginner ＝ 「CTF経験不問（簡単とは言っていない）」

• easy = 「難しい」

• easy-med = 「超難しい」

• med = 「激難しい」

• med-hard = 「鬼難しい」

• hard = 「MAX鬼難しい」

2. 参戦準備（脳内作戦会議）

　タイムゾーン表記を見逃し「7:00からなのか、早っ」と思っていて、気づいたのが前日というところからしてポンコツ全開でした。

　ともかく猶予期間を得たものと前向きに捉え、競技に臨むことに。験担ぎは某スーパーの「メンチカツ」＋高級ソース。

　加えて今回は、暗号つよつよな方のニックネームにあやかった菓子を準備し、食しながら競技に臨むこととしました。

　OS の Update は前日までに済ませていて、少なくとも形としては万全の体勢です。

　目標はいつものとおり「Crypto 全完、できれば他分野も 1 完以上」です。

　作戦は某私鉄の「逝っとけ」ダイヤ。とにかく解けるものから解く、問題を解くためには何でもアリ、というヤツです。

3. 参戦状況

• 11/4 16:00(JST) 頃　競技開始

• 11/4 16:02(JST) 頃　「Sanity Check」フラグゲット。

• 11/4 16:27(JST) 頃　「Complicated Function」フラグゲット。

• 11/4 18:00(JST) 頃　名探偵コナン視聴（プレイは続行）

• 11/4 18:55(JST) 頃　「Unique Flag」フラグゲット。

• 11/4 19:00(JST) 頃　夕食

• 11/4 22:05(JST) 頃　「Streamer」フラグゲット。

• ＜＜以降、ひたすら虚無の世界をさまようＰａｒｔ１＞＞

• 11/5 03:00(JST) 頃　寝る

• 11/5 08:00(JST) 頃　起きる

• 11/5 08:30(JST)頃　朝食

• ＜＜以降、ひたすら虚無の世界をさまようＰａｒｔ２＞＞

• 11/5 12:30(JST)頃　昼食

• ＜＜以降、ひたすら虚無の世界をさまようＰａｒｔ３＞＞

• 11/5 15:55(JST) 頃　「Survey」フラグゲット。

• 11/5 16:00(JST) 頃　競技終了

というわけで、点数になる活動をしたのは実質 6 時間、あとはひたすら食う・寝る・虚無るのいずれかでした。

4. 感想（お気持ち）

　戦果は散々でしたが、久しぶりに CTF を楽しむことができました。

　また upsolve を通じて CTF へのモチベーションを取り戻すことができました（これが一番大きかったです）。

　開催してくださった TSG の皆様と、当日対戦してくださった各チーム及びプレイヤーの皆様に、この場を借りて御礼申し上げます。

5. Writeup

　どの問題も全く「エレガント」には解けていない気がするのですが、簡単に「採用した考え方」や「ソルバ」を紹介します。 　

5.1. Complicated Function（117pts, 70 solved）

設問

　Beginner 問で、CTF 初心者向けにフラグゲットまでの流れがガイドされています。ガイドされているのはあくまで「CTFer なら誰でも知っているであろう、フラグゲットへの一般的な歩み方」であって、問題のそのものの難易度を下げるものではありません*3。

　提供されたスクリプト等は以下です。なお、pycryptodome が必要である旨のメモも同梱されていました（確かにビギナーフレンドリーではありますね）。

「challenge.py」

from Crypto.Util.number import isPrime, getStrongPrime
from math import isqrt, sin, ceil
from secrets import flag


def f(p):
    return isqrt(p**2 + p * (2**512-6) + ceil(isqrt(p)*sin(p))) + 2**1023


while True:
    p = getStrongPrime(1024)
    if p < 2**1023:
        continue
    q = f(p)
    if isPrime(q):
        break

N = p * q
e = 0x10001
m = int.from_bytes(flag, 'big')
c = pow(m, e, N)

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

「output.txt」

N = 36517404305297844159564250986998364545749151568667732337564141796428285198409567155495468780386611544242689580089026301007867731616501462571857014948329304677585682534513311931280592743677919741211277066420279973665839898693462080087384474270473468411814863104608060945012301810206919347219744349831947632420533489933798065496290612931089442978868423837068735855183319271953531607892676482508704408482509645764820088854762889436761417245871075875762331247987854763068633058894469255779600684845456979405817748289218533715177711802661303055514957438072072036882111277967476497338901040854808789173453802590826788192053
c = 10955441460830702971387335888341162305090757526159743008807609823673521696863955454033040842132899414049783504960968117620860408142538216669369693386110678382112863315608217382774969191050306778748875856817288367369848881561750362221050586276876239956129985854245190619132772579774800480316624847309710595491090120189333272498817039509311650265968036568364234815921263181086438290844976279974023236010641698308664245573159698211860696725554580817928576304048869309097043078452170158082597167199813821750238244173483019805092246803337196768846732908994751887507198151471659940647272634351206676375579258509003076141110

検討

　N、e、c が与えられてた、よくある RSA 問の体裁をしています。p は 1024 bitの Strong Prime なので、q の作り方に着目するのがよさそうです。

解法

　q = isqrt(p**2 + p * (2**512-6) + ceil(isqrt(p)*sin(p))) + 2**1023 の形をしています。最初の isqrt は何回か計算を試行すると p + (2**512-6)//2 - 1 であることが推測できます。

　実際このことは、M := (2**512-6)//2 - 1 とすると、(p + M)**2 < p**2 + p * (2**512-6) + ceil(isqrt(p)*sin(p)) < (p + M + 1)**2 であることから裏付けられます。

　果たして、q = p + M + 2**1023 と表すことができることから、N = p*q から導かれる 2 次方程式を解くことで p を算出できてしまいます。

ソルバ

import gmpy2
from Crypto.Util.number import *

N = 36517404305297844159564250986998364545749151568667732337564141796428285198409567155495468780386611544242689580089026301007867731616501462571857014948329304677585682534513311931280592743677919741211277066420279973665839898693462080087384474270473468411814863104608060945012301810206919347219744349831947632420533489933798065496290612931089442978868423837068735855183319271953531607892676482508704408482509645764820088854762889436761417245871075875762331247987854763068633058894469255779600684845456979405817748289218533715177711802661303055514957438072072036882111277967476497338901040854808789173453802590826788192053
c = 10955441460830702971387335888341162305090757526159743008807609823673521696863955454033040842132899414049783504960968117620860408142538216669369693386110678382112863315608217382774969191050306778748875856817288367369848881561750362221050586276876239956129985854245190619132772579774800480316624847309710595491090120189333272498817039509311650265968036568364234815921263181086438290844976279974023236010641698308664245573159698211860696725554580817928576304048869309097043078452170158082597167199813821750238244173483019805092246803337196768846732908994751887507198151471659940647272634351206676375579258509003076141110
e = 0x10001

M = (2**512-6)//2 - 1
# isqrt(p**2 + p * (2**512-6) + ceil(isqrt(p)*sin(p))) == p + M
# N = p*q => p * (p + M + 2**1023) - N = 0

D = (M + 2**1023)**2 + 4*N
sqrt_d = gmpy2.isqrt(D)

p = (-(M + 2**1023)+sqrt_d)//2
q = N // p
phi = (p-1)*(q-1)
d = inverse(e, phi)

m = pow(c,d,N)
print(long_to_bytes(m))

フラグ

TSGCTF{From which angle did you solve this, binary search or convergence of f(p)-p?}

二分探索でも解けるようですが、思考（指向）が「競プロ寄り」か「数学寄り」かで分かれるのかもしれません。

5.2. Unique Flag（109 pts, 82 solved）

設問

　easy（難しい）問題で、提供されたスクリプト等は以下です。

「encrypt.py」

from Crypto.Util.number import getPrime

p = getPrime(1024)
q = getPrime(1024)
N = p * q
e = 0x10001

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

assert len(flag) == 33
    
flag_header = flag[:7] # TSGCTF{
flag_content = flag[7:-1]
flag_footer = flag[-1:] # }

assert len(flag_content) == len({byte for byte in flag_content}) # flag_content is unique

c_list = [pow(byte, e, N) for byte in flag]
clues = [x * y % N for x, y in zip(c_list[:-1], c_list[1:])]
clues.sort()

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

「output.txt」

N = 23270433480920204754247611545325351123344837487480637119344134402239723224072753511766733288907047277110318616688410345451695008290697208699431350412549980332693080979894504737640802849242656337537061128034361792156302502329044951868719492095983428863678764573927362740207756141512536958600798465368672826288270218390845725069636496528488276905161318078890887808033722334376853632300178257589009018165644740844747444214979597702959381078126401914809713991087656801656368079319383579542103855944156160231935875884314630699684359910296730669798237991501134339113682532446997472722560474195749179320370386661938616345489
e = 65537
clues = [790128007826920672966041424911766354167695121053219604283198146207007061791691778597663178563455647947105718896263099495348666331968821896627253287975936857535926164644548223394731131868459847861503995994130787209417795249554290922334587840664276128893082715626698208421033163870050616673531495044580102830036983208043090136212931697438690030675611301000171270559392107484305007589373493054650247495594665847524590737367285135216109196557363472975056201832374767680569696302197844301099024043070258479146726214414688459938129079248125143388403636784068208501745074616490491553776387248926153964494371491351883633209, 2603711767185838325352475153597847161854130118046369285623915043550612314176250745686994158628404520769025735077328213489305045750703593138538988340789187229888984902266067604215108157628606721779126603704209046389682027226116051092595210765409544706918465385789940134172311788347486915924020739666375005469879097995622537311532236494537245411805276338873499191960938465585934543775755531517716535416304391622644348521922876999587501073379321712481689748053619310595304248483018790236975241904276396525088600521271478581198340688684196813199138458166434400373640927130152301112142288723416868406008752554068971897796, 3555341764263168489859556591176672830061219988177503466050405264336799992429135972104282899942353497557907652603350792489036502274605405291660887915416806360972250779650137925049172948193768071600510818240408613776868308398496542674893829543607137246662897358746317583492470427929271497748068342690213991707491115445413140859740482959186024227616377454531805749180736700863648663258910520198205760375727899867937645622163083304815955402598214976712655286175624671893539673068172120613290880503614440004957010458255469774287344198988168780496350286219383906192401923310489444670837618343011413316177831554304813263293, 4392082234365429459669635522490994995545586622061892472817657701654688511628534821883962531710455275948798581412337865098670688087280709878221953558349740960329160083052847343991585094759562763366071177122979453158141777809615757029472963694552128931278267696610442930805576661385112057944278069707887638239490706210686333113376066401571156753733092557168107224196049486567238631166786676598900544251407195743615657256591953956049341610070209608544320990612354876845027617374094455067062785749092329211594227845595088640923695318792943759161256049917608399044564463672780212345061033003580514031008070984006394521668, 6978684590718573243656949612105542758488203443423350685382013479128441571089892176317290844763856663774755922991003851926082052833399193817638062111399819008457173066656968710933915780345439852889885256407111306528134824030362697685736295137459712033151836378581847902384300946884645175079050691372299609133912373238921511680524246835804911263766704418407215767692780171673688161098855454535667470100406268512578658298590762764201801122154299700156455886608231139966939989436753650901587246230468663005258431711603830727021655440551309738459469083116564621458459773745615809415945961545341435040532110184451588706909, 7730262380985917599887572033422177147289651970502093448402835145164830024426315228806715285722659089566236129886746480764786215693984588815504124791891393731400575988135841499609611797069840377647924075117377822033352586269608104804125510707845643611710455554838427560803831147423159767827522768368918988345993436576494036323665588754259053163989171434047082195256858849152960407740290442654588260794482691958589991068313525613320625439489177141737508702594419202694397478381467839720929129426927668998377854144326405841432095191488744613115154408572282654135532074279295245338650730047025690759623846022642571071963, 7870428672617888994422906853248211446366754259733482277745650556132131582761503165723404791505714110195629648744360328326420176714096715656418558504951970022788814322102278336415722851826552839236483969562821649541794780657722003849928232610560989749085154296910943580468121448389230575504988958640111467569744601441342152829070870718010034108398733578934054919041551400855436743799387390257957855545880360755020395022783083503166714335601095744185285348725860445725936407700491229265197561539811624147428412389726767719262845468067268220408467424614068704646047656505819137603600314223155281334867541677294657269390, 8609510284694803043189705088389821843021038300248628370429317978814889304430328856895995414830838739620301124621301721537775180909783646308710312015748757692570074444146048063288330338241388649181127306992151615819806150752330593447168414624657327459419994792062262566992856822874586796213398413460564073159223988672183437164224830058703931407420751347450506434382840960774130788709586835237024062653074786060686562890430445063234694495435768852328222652802008741192860317680389695015771978657721235243624844185665810736779862719888645610567314465422364407861744887985325045151347091814327252867102598023702123634893, 8764012548720665713701201793155399309870111965369993371803350036539422185650799931107265721471961540862241262644925810817557287987388612113771424453413029690339343352048592343900357225140896471551985699215620154773850213962677651930062137448251705285861554850231313763242085813951196025573454108680549038776926779092562595635561865377427363791539907677647388233742883434894879173415977599370552750513325217529346778748301898211759441267178121774471269812805873578379664777277726959180923972945741326150250571072096537087980515856259481465906892196132539685345329249252030441836333228304113901123751209313594774048411, 9008821235404534774894891840865644757418002303365121156019461336283705824480673407281784353738233629927976889096625448460073180574899056351401937861566897823469165990311234532903677780258240301012377511917098868850017485389860900161403497054524629055763134706771541438200372479388084747248076874591357294592908214804614821614134453271058041821309928429492064920317496131336615880002176651354627658576705156794615097981712459554762647700173303841240037417204812844860127520500295842333216976016883771600927798062138428278165410002807841897458765380987909422855298376904935944755071636375020175879303691494691648729571, 10474911617314344093035296274381234749101583500527437860041431188313938156453438490783669910408601907840231565111467423937905944246300919566807077410926355571241589514754269643137702018163430659263615177391720920777071669679112457463342818217687533446232740783283032619985290522536451057260694049911207086850829161304525815898322999460249349418001236987856485233784175562194872850068860587367749350367692115642230663276488474831786206392289391683584796316038243477608620299442818925558267755743944966965590254288900990166554824598295411812423812057962439493264058570961162833692763593404011287652460274292011178704229, 13110381638342217700044116835482318354178640599253721255902105118218292921908590875402841920977595295587154969905468217393514029780192254567805167189561981288346541104187097786158686610182752582262736216900889630694589441983532956902475092397149348354578876977278601897135958677041840489787116994835677415918526784950587842308692695028053266428000179056540851210672916239382320991277325978720399398297894385691874713065477018336173537483516990191924630941831467023912809007439219185416637094870113459693399267881245563091987656247602891135995257754370121186475874895953059792350690971513600960862888017703690554083459, 13722721572470236588898440206865856389152421592146331372623620761105236258642769428613680530235913336412231001256536483370539801648315256149288975606335360634006014491805081550253603688595254959670129531815820738880819515467443628589419885739357776607879281030305390788462268201177519696379582421075205825223506882790846127395851423387355250518925599458496527319759716961190269475043488198823985171705163502605280956855529982181144980535693738091067309543085139412462069952512044802852746114286283887473219768202644823684600027741551806766726373880658547387314450097217066672915328591025976805608015523890515132426387, 13907378143102130732902591528175452184668250175669078564922722729277532332899307298492183863825002170085267037120966710137296520632659066245811450863381591820314104559304716576579947768421047268607544985860210956387427521210211129755935598531328869037393608408989674670981088938567613781468335811260237492104595950519517518617578677677787025453461327336960623845610621752404588399599991001699803056576669100638249157172825774364065063815561453951010729993716989597143669677725856650954155213710311820417545885775510044222220541796461890558861039133971629201524057880779170401640703503019641132712790726669921828415791, 14120400860385637396632607286135661793958438285062218101343811442329217898129411032002000350977425825996409346097620544352258144601308497322065150782257038383914436998782920142187156177557396917159637452504378331382141301919552487290646033095326670250741650299062291668092793457098216953317991446828793222200503107261585592188754090447817955186450059917734158228634856449513892854663100410202968587025379391901260869884847048181290904241170031050049608323224619595992013998760176044527640260560226425674718522654115796289752023951046001416701610705547940854507383323162061543349749057955527154808438878655873381924405, 14698896348088063156187270997421588677714399061222880874144618906068645039117367567961854550911710929776929577319055009436987940195644271595440197688498312761277731697978188128431643248470794438585436719216257105191878641049129049923301277529851691883566500423292922218796681106904405477311127758973402766359242062810538614875409810216565025132923823792242500786728482925652318681058145996956719422754840265487588886384210435421642534141346623264992306879009731648539475819770296162993354959588928869246795665015356541113141789547198151388517967205114998707046242427529782450631008568205068970921337432050960660682459, 15029884228277986489199399805546744756384194842114602643592034471387136929994797445880809477875738231285145593249223445053535965293809750894912475666388265290853063554307747052471064827789230626431100261538591961826419047326217130106954938564102444946805966835435441345928820303084749906070834370292328693504130454703539813471516484793230944669747561760610824827040233316834137947013336066206964971490936063361717836670055655255008278013748443661849914080655007167036195301285165244039723352500939219835986599194370637835048745016392523067465483063368927290961796554522196264881536578834490630583213917304029865939161, 15309200221723806616467815527508949449508016308667619503475045946652621652525992305168651560887284176353924931956269939787077811973514566176608684620809151397625885719537402839920369797647002257990605085738377504988859240254084164590957509486682488178961349129559926308115898888408809018423909717677181884526722126502322318455704911203649111381107113783748969172970323298774692322646329004904087523994990271905442581272126396627211570936941571392711592683960657204560162191971440131508850959242922017207256661353383453193118931908674343390887637124979355811285785638033429254835197971636826274879249886842048918432736, 15724182462935088662707915446655107878278152894209881300967803307334781347515606304746531472463196270125945780931765849147216669235630418637875694444778675771594247113061143844136107527843426140240070502431201960657331892635213118991405460668666027672294906783791441223090507736721265283630015340939375871798311963795515181453223204337362840111547002251197009848653679561190486710064616795228154486847718903419257804283649208020835219877286500226549440463845774258811597945314325403472598511132833259835975605936073505765246811661546643859844350550681749257518136665405784760339373876106842193544962035364141936283753, 16010598613006269242394494415481073404802885743759056303920374396389364406805008152009154054902831052653758678196829556029416363334310779301534650601102392985616360749664385284718557734612612334579643566581651102242306222193227111260448228193714693240481130347390382116855512299873569881326939972343314570039547897580924071328599722614389921295511670529095683738107704146361532800780429539031159556496976109863114080778133301779747597407525649360836980458868113543694436862963884485475906909931191611405995601484367864575876650055986787526037062685039522257827670426684466191523819658566267710796063797508503673575508, 16176225157815061780398885654620420828395273758161309313595904684794782916031471005382323856662285262373051339479066795020066992972796748770489374700029745240899106774349950323621974876991346899532267757945372794675963763211677154442477490480764334758589065403101041835380412036155680032278713692380636751799800174173937468277604554776759076686957635653867348211328058462563934841255845438021673179325752005903202195307236777237380608739528664802974483747876242106584283139484518385093456386588108230286642702223901374448669968747735244954159162896226605024555185352576619896951345620018917148886974802087005061112135, 16681188269653223654724315030136682210774552752554458086958468278548783168739866695726975896035811383412108751120213372631892032120642218357242947180926422406518062384144340315186804028028673285952917556435047990619394575021747680589947318197008430952647870055239411272055715760414079469566525762018667573302151696340104245475784099738670745323261117058044792751584716381734074389247651104965039208100878784761184187575420884985536037251587193757974760803271209026578181938823090178086385927565035063194430696540320842560908821318551920518079959829776767797371769064772564881430027427764161144068312324251665729488780, 17829658117323428808747868598742075440062137591346852189083905589271168845051505272630777599191830286419880652433509964145788364929611644511812576526573426916933568982874857304389571078641719134887390902234897633109911630620064342448365833021501305097046535685687516423128015236731938861706627775842928316810722656485753731575710818024516292222339926273882441860157758675960292785969030577768637311050941129992914285935037973635612973287046435622821551354639344767359753011162290622995439092970304336429989082391680592785895499607898534896211918901223135266662562647266007027360588113757029416715494934165222739616683, 18142530606909716062376251786389643324197492525662369626779351589827519710596398063341881492070698478957535529402981903035193439593816123316087575219925977686245766113691521350584328679759502382807285523704968935762596078425008178057360086647386696939735982650179504583840710564525731340265745482252714541820058727354731450644763797071558334414897585733667272516453556559972684675125516239673811780523512745567106915629379361310179451294037943334450423100411431081620714967277818090200519889910181746783471882899674667241036338987708997780333893361059800622713833148966642131905197255377905810743498001951198125311059, 18916874915493297936079891268802075451235734846035427583955430843324283662366324633202233385782932817340850020378986785716061936989209245162032573305936283861299211919092036584752926046345006676182392365941514696661367329055550272171753927543111392356350737216020653037731493630053105987250335352958368913760588484193482490045930904427197949983588313643868410274754829287237363788001109161904345279546393663787324578514084534019735002594130069819170331383328434044289905874038021158845855747798172165049208337121421852611456896877370705022828767867961460247191792131749388018583310316369606660652603473617620362220776, 19761531445789644550941649188821673088534370105097262343329866705687995865103813168376859916409080934942621503804632853819460640556129955518535485874638416201423297931706690054251711146751875933841075798086049232897482741510517534219163312537149829346821694199026849981873391746409094894635786418504655918594084378562506966684113615145069297495931332254115518216812302704944162971621215874347240778158691664956918543903100361085291794226778736356304744575442579466683011144983985184446648189753472950753969800901371318514176099102941183927711143295688852105189853285767981704534129685617787251540530767915253022947490, 20256094547551427361159536964089120192470579547856867798123148497076148597338094007239708853868154430044018965669548800520357708625488500840886524107263842898564620995651088843299156623903379275911887021467406220229809304913979273339544306605180744927202065302617395980949445708701034751035277692178613703611237789111970396029694552402613307432231659723290421165555788483472386785358943811922285121036435102796254087074468046006584551405865525781432291674627713381806461231003764884384009047079053403228562795215671383412031358781402019097452515349062662042796744413040430120541108838183559554461277378419187930920413, 20363523683403754850477941996268145873307803894978921710228462628146999736940222671129222862265160379946415684464747917659662321205107403115837157035374067466188228334375906081151411079001619437896818940656122691708169785711806055272700179185892964477917806030204206763229340531579796772278526520943763997401381029845705999036446407497831084737277684996161128395539244139220962069262836778956401801008041186706885436332324336681638085145485728737526432916392575653655187967807139187810035548902309557063161478464221501395056289134752409225031789805569864167180786090815982754846720197089740299363472750121282729340973, 20814912434079654358712994986655938285672355659172554521972448981339195273278087029468453535698010595236459533086499060463317723686547000241667857244712653564557545738168820338242942485233926997951781862259839493112100996378583435254659260667047548564231904421776634552680502559175487802626042304303449745827230709927179704869112666087937034760280611168221409540432787302943151703739428105219869226885922197133645265907625314478690899327851652074282189138427005746519010639537824886929608878348016360424645895051778822009871610495121610883214100573360743476671172464995366677557757239376079084722813893096016326823606, 20978978782083985514808414763592752188297832781732994978611517153950737776001188808668923478821417090172961435355822072526474663371493271175072308071960227368747274906534977118068778902399152185246696702689800010100729290250592141361416806610123159371068751278126481137723149743960233299432386251076215253444110113219693470037719585135531616598037376091905011497168565184564212550608338331996940342482386974738408168008861574665395721197042150006344988032346900944468633093984681022454475106597004968263850271320396630355903399323458669065574677651201990075334529713587085951400864385000308137999968746200082025015416, 21510393992991434219771555281382073811886457282216421285690979093137458508475954568419056773565332788894486275426908163637126421408657102596322971185031241956913463507854888295227362444328359266706872420059719619657069662925599952624262906407162386789979523361641558714567193670965811155805593371330497659154542639258412356476199441487088405118103359273682288473187622391831093531374603531951020860755898239699034003278466710154923269181470911166256665818879112416320538492976301262952831443514831107346725637206419870968005748691921100981160236843650083592044728031025798498262451919405184577923803192873012465402408, 21702370286383142896382980896421981414971906140748132749535149467159561579953330771029906461700411301795811236217402115596536451372996903939804016345835732303546870765245612262653631530944318690150045446899350265189274003884240988723566380751519278171721537440720211256644999794264781281823566708722358903968738834874217357352233640572984862487562571610283183746852625175244503706166323292070046358158579157876780137070957640130723554973407811810584917266738218587446647624045843454142231125439581659799761005303756629310091897520981148547565077534090671712715361212723249781422387730181374938558849132220687101010195]

検討

　スクリプトの先頭を見ると一瞬だけ RSA っぽく見えるのですが、1 文字ずつ暗号化した際の暗号文を並べ替えて出力しているので解読手法は「対 RSA 用」ではなさそうです。

　 暗号化の方法は、隣の文字（の文字コード）と掛け算をした結果を e 乗（mod N）する、ということですので、平文の文字セットが 0x20～0x7f の高々 95 種類と仮定すれば暗号文に出てくる数値は 95*95 = 9025 通りしかありあせん。

　ですので、探索＆辞書照合系のアプローチが有効です。

解法

　判明分をもとに、次の 1 文字の候補を決め、候補があれば正しいと仮定して次を探索、候補なしならNG・・・を進めてゆき、最後までたどり着いたものが正解となります。

　昔の探索系 RSA 問で使ったプログラムを改造して実装しましたが、この実装が良いとは思えないのでウマい人のを見て再履修したいと思っています。

ソルバ

import copy

N = 23270433480920204754247611545325351123344837487480637119344134402239723224072753511766733288907047277110318616688410345451695008290697208699431350412549980332693080979894504737640802849242656337537061128034361792156302502329044951868719492095983428863678764573927362740207756141512536958600798465368672826288270218390845725069636496528488276905161318078890887808033722334376853632300178257589009018165644740844747444214979597702959381078126401914809713991087656801656368079319383579542103855944156160231935875884314630699684359910296730669798237991501134339113682532446997472722560474195749179320370386661938616345489
e = 65537
clues = [790128007826920672966041424911766354167695121053219604283198146207007061791691778597663178563455647947105718896263099495348666331968821896627253287975936857535926164644548223394731131868459847861503995994130787209417795249554290922334587840664276128893082715626698208421033163870050616673531495044580102830036983208043090136212931697438690030675611301000171270559392107484305007589373493054650247495594665847524590737367285135216109196557363472975056201832374767680569696302197844301099024043070258479146726214414688459938129079248125143388403636784068208501745074616490491553776387248926153964494371491351883633209, 2603711767185838325352475153597847161854130118046369285623915043550612314176250745686994158628404520769025735077328213489305045750703593138538988340789187229888984902266067604215108157628606721779126603704209046389682027226116051092595210765409544706918465385789940134172311788347486915924020739666375005469879097995622537311532236494537245411805276338873499191960938465585934543775755531517716535416304391622644348521922876999587501073379321712481689748053619310595304248483018790236975241904276396525088600521271478581198340688684196813199138458166434400373640927130152301112142288723416868406008752554068971897796, 3555341764263168489859556591176672830061219988177503466050405264336799992429135972104282899942353497557907652603350792489036502274605405291660887915416806360972250779650137925049172948193768071600510818240408613776868308398496542674893829543607137246662897358746317583492470427929271497748068342690213991707491115445413140859740482959186024227616377454531805749180736700863648663258910520198205760375727899867937645622163083304815955402598214976712655286175624671893539673068172120613290880503614440004957010458255469774287344198988168780496350286219383906192401923310489444670837618343011413316177831554304813263293, 4392082234365429459669635522490994995545586622061892472817657701654688511628534821883962531710455275948798581412337865098670688087280709878221953558349740960329160083052847343991585094759562763366071177122979453158141777809615757029472963694552128931278267696610442930805576661385112057944278069707887638239490706210686333113376066401571156753733092557168107224196049486567238631166786676598900544251407195743615657256591953956049341610070209608544320990612354876845027617374094455067062785749092329211594227845595088640923695318792943759161256049917608399044564463672780212345061033003580514031008070984006394521668, 6978684590718573243656949612105542758488203443423350685382013479128441571089892176317290844763856663774755922991003851926082052833399193817638062111399819008457173066656968710933915780345439852889885256407111306528134824030362697685736295137459712033151836378581847902384300946884645175079050691372299609133912373238921511680524246835804911263766704418407215767692780171673688161098855454535667470100406268512578658298590762764201801122154299700156455886608231139966939989436753650901587246230468663005258431711603830727021655440551309738459469083116564621458459773745615809415945961545341435040532110184451588706909, 7730262380985917599887572033422177147289651970502093448402835145164830024426315228806715285722659089566236129886746480764786215693984588815504124791891393731400575988135841499609611797069840377647924075117377822033352586269608104804125510707845643611710455554838427560803831147423159767827522768368918988345993436576494036323665588754259053163989171434047082195256858849152960407740290442654588260794482691958589991068313525613320625439489177141737508702594419202694397478381467839720929129426927668998377854144326405841432095191488744613115154408572282654135532074279295245338650730047025690759623846022642571071963, 7870428672617888994422906853248211446366754259733482277745650556132131582761503165723404791505714110195629648744360328326420176714096715656418558504951970022788814322102278336415722851826552839236483969562821649541794780657722003849928232610560989749085154296910943580468121448389230575504988958640111467569744601441342152829070870718010034108398733578934054919041551400855436743799387390257957855545880360755020395022783083503166714335601095744185285348725860445725936407700491229265197561539811624147428412389726767719262845468067268220408467424614068704646047656505819137603600314223155281334867541677294657269390, 8609510284694803043189705088389821843021038300248628370429317978814889304430328856895995414830838739620301124621301721537775180909783646308710312015748757692570074444146048063288330338241388649181127306992151615819806150752330593447168414624657327459419994792062262566992856822874586796213398413460564073159223988672183437164224830058703931407420751347450506434382840960774130788709586835237024062653074786060686562890430445063234694495435768852328222652802008741192860317680389695015771978657721235243624844185665810736779862719888645610567314465422364407861744887985325045151347091814327252867102598023702123634893, 8764012548720665713701201793155399309870111965369993371803350036539422185650799931107265721471961540862241262644925810817557287987388612113771424453413029690339343352048592343900357225140896471551985699215620154773850213962677651930062137448251705285861554850231313763242085813951196025573454108680549038776926779092562595635561865377427363791539907677647388233742883434894879173415977599370552750513325217529346778748301898211759441267178121774471269812805873578379664777277726959180923972945741326150250571072096537087980515856259481465906892196132539685345329249252030441836333228304113901123751209313594774048411, 9008821235404534774894891840865644757418002303365121156019461336283705824480673407281784353738233629927976889096625448460073180574899056351401937861566897823469165990311234532903677780258240301012377511917098868850017485389860900161403497054524629055763134706771541438200372479388084747248076874591357294592908214804614821614134453271058041821309928429492064920317496131336615880002176651354627658576705156794615097981712459554762647700173303841240037417204812844860127520500295842333216976016883771600927798062138428278165410002807841897458765380987909422855298376904935944755071636375020175879303691494691648729571, 10474911617314344093035296274381234749101583500527437860041431188313938156453438490783669910408601907840231565111467423937905944246300919566807077410926355571241589514754269643137702018163430659263615177391720920777071669679112457463342818217687533446232740783283032619985290522536451057260694049911207086850829161304525815898322999460249349418001236987856485233784175562194872850068860587367749350367692115642230663276488474831786206392289391683584796316038243477608620299442818925558267755743944966965590254288900990166554824598295411812423812057962439493264058570961162833692763593404011287652460274292011178704229, 13110381638342217700044116835482318354178640599253721255902105118218292921908590875402841920977595295587154969905468217393514029780192254567805167189561981288346541104187097786158686610182752582262736216900889630694589441983532956902475092397149348354578876977278601897135958677041840489787116994835677415918526784950587842308692695028053266428000179056540851210672916239382320991277325978720399398297894385691874713065477018336173537483516990191924630941831467023912809007439219185416637094870113459693399267881245563091987656247602891135995257754370121186475874895953059792350690971513600960862888017703690554083459, 13722721572470236588898440206865856389152421592146331372623620761105236258642769428613680530235913336412231001256536483370539801648315256149288975606335360634006014491805081550253603688595254959670129531815820738880819515467443628589419885739357776607879281030305390788462268201177519696379582421075205825223506882790846127395851423387355250518925599458496527319759716961190269475043488198823985171705163502605280956855529982181144980535693738091067309543085139412462069952512044802852746114286283887473219768202644823684600027741551806766726373880658547387314450097217066672915328591025976805608015523890515132426387, 13907378143102130732902591528175452184668250175669078564922722729277532332899307298492183863825002170085267037120966710137296520632659066245811450863381591820314104559304716576579947768421047268607544985860210956387427521210211129755935598531328869037393608408989674670981088938567613781468335811260237492104595950519517518617578677677787025453461327336960623845610621752404588399599991001699803056576669100638249157172825774364065063815561453951010729993716989597143669677725856650954155213710311820417545885775510044222220541796461890558861039133971629201524057880779170401640703503019641132712790726669921828415791, 14120400860385637396632607286135661793958438285062218101343811442329217898129411032002000350977425825996409346097620544352258144601308497322065150782257038383914436998782920142187156177557396917159637452504378331382141301919552487290646033095326670250741650299062291668092793457098216953317991446828793222200503107261585592188754090447817955186450059917734158228634856449513892854663100410202968587025379391901260869884847048181290904241170031050049608323224619595992013998760176044527640260560226425674718522654115796289752023951046001416701610705547940854507383323162061543349749057955527154808438878655873381924405, 14698896348088063156187270997421588677714399061222880874144618906068645039117367567961854550911710929776929577319055009436987940195644271595440197688498312761277731697978188128431643248470794438585436719216257105191878641049129049923301277529851691883566500423292922218796681106904405477311127758973402766359242062810538614875409810216565025132923823792242500786728482925652318681058145996956719422754840265487588886384210435421642534141346623264992306879009731648539475819770296162993354959588928869246795665015356541113141789547198151388517967205114998707046242427529782450631008568205068970921337432050960660682459, 15029884228277986489199399805546744756384194842114602643592034471387136929994797445880809477875738231285145593249223445053535965293809750894912475666388265290853063554307747052471064827789230626431100261538591961826419047326217130106954938564102444946805966835435441345928820303084749906070834370292328693504130454703539813471516484793230944669747561760610824827040233316834137947013336066206964971490936063361717836670055655255008278013748443661849914080655007167036195301285165244039723352500939219835986599194370637835048745016392523067465483063368927290961796554522196264881536578834490630583213917304029865939161, 15309200221723806616467815527508949449508016308667619503475045946652621652525992305168651560887284176353924931956269939787077811973514566176608684620809151397625885719537402839920369797647002257990605085738377504988859240254084164590957509486682488178961349129559926308115898888408809018423909717677181884526722126502322318455704911203649111381107113783748969172970323298774692322646329004904087523994990271905442581272126396627211570936941571392711592683960657204560162191971440131508850959242922017207256661353383453193118931908674343390887637124979355811285785638033429254835197971636826274879249886842048918432736, 15724182462935088662707915446655107878278152894209881300967803307334781347515606304746531472463196270125945780931765849147216669235630418637875694444778675771594247113061143844136107527843426140240070502431201960657331892635213118991405460668666027672294906783791441223090507736721265283630015340939375871798311963795515181453223204337362840111547002251197009848653679561190486710064616795228154486847718903419257804283649208020835219877286500226549440463845774258811597945314325403472598511132833259835975605936073505765246811661546643859844350550681749257518136665405784760339373876106842193544962035364141936283753, 16010598613006269242394494415481073404802885743759056303920374396389364406805008152009154054902831052653758678196829556029416363334310779301534650601102392985616360749664385284718557734612612334579643566581651102242306222193227111260448228193714693240481130347390382116855512299873569881326939972343314570039547897580924071328599722614389921295511670529095683738107704146361532800780429539031159556496976109863114080778133301779747597407525649360836980458868113543694436862963884485475906909931191611405995601484367864575876650055986787526037062685039522257827670426684466191523819658566267710796063797508503673575508, 16176225157815061780398885654620420828395273758161309313595904684794782916031471005382323856662285262373051339479066795020066992972796748770489374700029745240899106774349950323621974876991346899532267757945372794675963763211677154442477490480764334758589065403101041835380412036155680032278713692380636751799800174173937468277604554776759076686957635653867348211328058462563934841255845438021673179325752005903202195307236777237380608739528664802974483747876242106584283139484518385093456386588108230286642702223901374448669968747735244954159162896226605024555185352576619896951345620018917148886974802087005061112135, 16681188269653223654724315030136682210774552752554458086958468278548783168739866695726975896035811383412108751120213372631892032120642218357242947180926422406518062384144340315186804028028673285952917556435047990619394575021747680589947318197008430952647870055239411272055715760414079469566525762018667573302151696340104245475784099738670745323261117058044792751584716381734074389247651104965039208100878784761184187575420884985536037251587193757974760803271209026578181938823090178086385927565035063194430696540320842560908821318551920518079959829776767797371769064772564881430027427764161144068312324251665729488780, 17829658117323428808747868598742075440062137591346852189083905589271168845051505272630777599191830286419880652433509964145788364929611644511812576526573426916933568982874857304389571078641719134887390902234897633109911630620064342448365833021501305097046535685687516423128015236731938861706627775842928316810722656485753731575710818024516292222339926273882441860157758675960292785969030577768637311050941129992914285935037973635612973287046435622821551354639344767359753011162290622995439092970304336429989082391680592785895499607898534896211918901223135266662562647266007027360588113757029416715494934165222739616683, 18142530606909716062376251786389643324197492525662369626779351589827519710596398063341881492070698478957535529402981903035193439593816123316087575219925977686245766113691521350584328679759502382807285523704968935762596078425008178057360086647386696939735982650179504583840710564525731340265745482252714541820058727354731450644763797071558334414897585733667272516453556559972684675125516239673811780523512745567106915629379361310179451294037943334450423100411431081620714967277818090200519889910181746783471882899674667241036338987708997780333893361059800622713833148966642131905197255377905810743498001951198125311059, 18916874915493297936079891268802075451235734846035427583955430843324283662366324633202233385782932817340850020378986785716061936989209245162032573305936283861299211919092036584752926046345006676182392365941514696661367329055550272171753927543111392356350737216020653037731493630053105987250335352958368913760588484193482490045930904427197949983588313643868410274754829287237363788001109161904345279546393663787324578514084534019735002594130069819170331383328434044289905874038021158845855747798172165049208337121421852611456896877370705022828767867961460247191792131749388018583310316369606660652603473617620362220776, 19761531445789644550941649188821673088534370105097262343329866705687995865103813168376859916409080934942621503804632853819460640556129955518535485874638416201423297931706690054251711146751875933841075798086049232897482741510517534219163312537149829346821694199026849981873391746409094894635786418504655918594084378562506966684113615145069297495931332254115518216812302704944162971621215874347240778158691664956918543903100361085291794226778736356304744575442579466683011144983985184446648189753472950753969800901371318514176099102941183927711143295688852105189853285767981704534129685617787251540530767915253022947490, 20256094547551427361159536964089120192470579547856867798123148497076148597338094007239708853868154430044018965669548800520357708625488500840886524107263842898564620995651088843299156623903379275911887021467406220229809304913979273339544306605180744927202065302617395980949445708701034751035277692178613703611237789111970396029694552402613307432231659723290421165555788483472386785358943811922285121036435102796254087074468046006584551405865525781432291674627713381806461231003764884384009047079053403228562795215671383412031358781402019097452515349062662042796744413040430120541108838183559554461277378419187930920413, 20363523683403754850477941996268145873307803894978921710228462628146999736940222671129222862265160379946415684464747917659662321205107403115837157035374067466188228334375906081151411079001619437896818940656122691708169785711806055272700179185892964477917806030204206763229340531579796772278526520943763997401381029845705999036446407497831084737277684996161128395539244139220962069262836778956401801008041186706885436332324336681638085145485728737526432916392575653655187967807139187810035548902309557063161478464221501395056289134752409225031789805569864167180786090815982754846720197089740299363472750121282729340973, 20814912434079654358712994986655938285672355659172554521972448981339195273278087029468453535698010595236459533086499060463317723686547000241667857244712653564557545738168820338242942485233926997951781862259839493112100996378583435254659260667047548564231904421776634552680502559175487802626042304303449745827230709927179704869112666087937034760280611168221409540432787302943151703739428105219869226885922197133645265907625314478690899327851652074282189138427005746519010639537824886929608878348016360424645895051778822009871610495121610883214100573360743476671172464995366677557757239376079084722813893096016326823606, 20978978782083985514808414763592752188297832781732994978611517153950737776001188808668923478821417090172961435355822072526474663371493271175072308071960227368747274906534977118068778902399152185246696702689800010100729290250592141361416806610123159371068751278126481137723149743960233299432386251076215253444110113219693470037719585135531616598037376091905011497168565184564212550608338331996940342482386974738408168008861574665395721197042150006344988032346900944468633093984681022454475106597004968263850271320396630355903399323458669065574677651201990075334529713587085951400864385000308137999968746200082025015416, 21510393992991434219771555281382073811886457282216421285690979093137458508475954568419056773565332788894486275426908163637126421408657102596322971185031241956913463507854888295227362444328359266706872420059719619657069662925599952624262906407162386789979523361641558714567193670965811155805593371330497659154542639258412356476199441487088405118103359273682288473187622391831093531374603531951020860755898239699034003278466710154923269181470911166256665818879112416320538492976301262952831443514831107346725637206419870968005748691921100981160236843650083592044728031025798498262451919405184577923803192873012465402408, 21702370286383142896382980896421981414971906140748132749535149467159561579953330771029906461700411301795811236217402115596536451372996903939804016345835732303546870765245612262653631530944318690150045446899350265189274003884240988723566380751519278171721537440720211256644999794264781281823566708722358903968738834874217357352233640572984862487562571610283183746852625175244503706166323292070046358158579157876780137070957640130723554973407811810584917266738218587446647624045843454142231125439581659799761005303756629310091897520981148547565077534090671712715361212723249781422387730181374938558849132220687101010195]

L = 33

def calc(o1, o2):
  return pow(o1,e,N) * pow(o2,e,N) % N

def challenge(flag, pos, next_char, current_clues):
  if pos == L-2 and next_char=="}":
    if current_clues[0] == calc(ord(flag[-2]), ord("}")):
      print("".join(flag))
      return True
    else:
      return False
  else:
    cand = calc(ord(flag[pos]), ord(next_char))
    if cand in current_clues:
      _flag = copy.copy(flag)
      _flag[pos+1] = next_char
      _clues = copy.copy(current_clues)
      _clues.remove(cand)
      res = False
      for x in range(0x20,0x7f):
        _res = challenge(_flag, pos+1, chr(x), _clues)
        res = res or _res
      if res:
        return True
      return False
    else:
      return False
  return False

flag = list("TSGCTF{" + ("\x00"*(L-8)) + "}")
assert len(flag) == 33

for i in range(6):
  clues.remove(calc(ord(flag[i]), ord(flag[i+1])))

for x in range(0x20,0x7f):
  if challenge(flag, 6, chr(x), clues):
    break

フラグ

TSGCTF{OK,IsTHi5A_un1qUe-flag?XD}

途中、なぜか「TSGCTF{OK,IsTHi5A_un1qUe-」で探索が失敗してしまい、ゴニョゴニョしながら時間を溶かしていました。競技中の生成物は捨ててしまっていて、なぜ治ったのかは謎です。

5.3. Streamer（125 pts, 60 solved）

設問

　同じく easy（難しい）問題で、提供されたスクリプト等は以下です。

「encrypt.py」

import secrets
import hashlib
import base64
import re

pattern = re.compile("[a-zA-Z0-9!-/:-?\[-`|~]+")
flag_content = b"@@REDUCTED@@"
assert pattern.fullmatch(flag_content.decode())

flag_hash = hashlib.md5(flag_content).digest()
flag = b"TSGCTF{"+flag_content+b"@"+base64.b64encode(flag_hash)+b"}"

key_stream = list(secrets.token_bytes(16))
encrypted_flags = [flag[i]^key_stream[i%16] for i in range(len(flag))]

print("cipher =",encrypted_flags)
print("flag_length =",len(flag))

「output.txt」

cipher = [163, 227, 86, 67, 200, 14, 176, 188, 101, 214, 117, 82, 99, 71, 199, 117, 139, 130, 78, 43, 224, 101, 183, 219, 82, 213, 70, 95, 101, 118, 133, 46, 146, 239, 98, 97, 250, 123, 183, 218, 82, 218, 1, 97, 62, 29, 145, 105, 168, 136, 116, 95, 253, 59, 148, 132, 98, 207, 118, 66, 52, 118, 197, 98, 168, 201, 126, 117, 195, 61, 184, 141, 82, 210, 86, 98, 47, 118, 144, 58, 221, 192, 99, 48, 224, 98, 185, 129, 108, 152, 25, 97, 96, 85, 173, 58, 148, 194, 104, 124, 182, 99, 162, 216, 99, 157, 117, 106, 59, 64, 213, 25, 148, 217, 109, 42, 224, 101, 183, 219, 127, 236, 67, 26, 12, 29, 174, 118, 153, 213, 78, 43, 245, 52, 151, 199, 113, 214, 117, 66, 121, 72, 141, 111, 168, 194, 112, 43, 244, 123, 183, 218, 82, 199, 86, 19, 47, 29, 141, 26, 139, 239, 112, 95, 239, 99, 185, 141, 57, 222, 117, 22, 58, 89, 153, 117, 133, 156, 78, 98, 233, 60, 148, 129, 121, 236, 67, 26, 12, 64, 159, 53, 196, 152, 100, 124, 174, 45, 148, 138, 104, 155, 75, 75, 32, 76, 174, 47, 131, 239, 100, 115, 175, 59, 148, 156, 101, 214, 117, 26, 103, 85, 173, 105, 139, 213, 78, 114, 168, 38, 175, 135, 96, 236, 68, 75, 62, 17, 194, 52, 211, 239, 99, 101, 224, 98, 248, 220, 38, 128, 86, 23, 63, 80, 223, 25, 146, 222, 123, 111, 229, 23, 163, 137, 101, 210, 66, 95, 12, 19, 220, 111, 218, 138, 56, 45, 166, 97, 139, 188, 90, 195, 28, 77, 2, 113, 152, 34, 165, 252, 88, 67, 250, 44, 163, 167, 64, 234, 1, 119, 18, 20, 204, 59]
flag_length = 304

検討

　16 バイトの key stream が判明すれば復号できます。

　フラグの形式から 8 バイトは自明なので、残り 8 バイトをどう得るかを考えます*4。

解法

　不明の key stream について、そのまま総当たりするのは厳しいので、各々候補を絞って出た候補を総当たりします。

　具体的には、暗号文が pattern から外れるようなものを候補から除外してゆくと計算可能な程度にまで候補が絞れます。

ソルバ

「solve.py」

import re
import copy
import itertools
import hashlib
import base64

pattern = re.compile("[a-zA-Z0-9!-/:-?\[-`|~]+")
pattern2 = re.compile("[0-9a-zA-Z+/]*={0,2}")
cipher = [163, 227, 86, 67, 200, 14, 176, 188, 101, 214, 117, 82, 99, 71, 199, 117, 139, 130, 78, 43, 224, 101, 183, 219, 82, 213, 70, 95, 101, 118, 133, 46, 146, 239, 98, 97, 250, 123, 183, 218, 82, 218, 1, 97, 62, 29, 145, 105, 168, 136, 116, 95, 253, 59, 148, 132, 98, 207, 118, 66, 52, 118, 197, 98, 168, 201, 126, 117, 195, 61, 184, 141, 82, 210, 86, 98, 47, 118, 144, 58, 221, 192, 99, 48, 224, 98, 185, 129, 108, 152, 25, 97, 96, 85, 173, 58, 148, 194, 104, 124, 182, 99, 162, 216, 99, 157, 117, 106, 59, 64, 213, 25, 148, 217, 109, 42, 224, 101, 183, 219, 127, 236, 67, 26, 12, 29, 174, 118, 153, 213, 78, 43, 245, 52, 151, 199, 113, 214, 117, 66, 121, 72, 141, 111, 168, 194, 112, 43, 244, 123, 183, 218, 82, 199, 86, 19, 47, 29, 141, 26, 139, 239, 112, 95, 239, 99, 185, 141, 57, 222, 117, 22, 58, 89, 153, 117, 133, 156, 78, 98, 233, 60, 148, 129, 121, 236, 67, 26, 12, 64, 159, 53, 196, 152, 100, 124, 174, 45, 148, 138, 104, 155, 75, 75, 32, 76, 174, 47, 131, 239, 100, 115, 175, 59, 148, 156, 101, 214, 117, 26, 103, 85, 173, 105, 139, 213, 78, 114, 168, 38, 175, 135, 96, 236, 68, 75, 62, 17, 194, 52, 211, 239, 99, 101, 224, 98, 248, 220, 38, 128, 86, 23, 63, 80, 223, 25, 146, 222, 123, 111, 229, 23, 163, 137, 101, 210, 66, 95, 12, 19, 220, 111, 218, 138, 56, 45, 166, 97, 139, 188, 90, 195, 28, 77, 2, 113, 152, 34, 165, 252, 88, 67, 250, 44, 163, 167, 64, 234, 1, 119, 18, 20, 204, 59]
flag_length = 304

assert len(cipher) == flag_length

def xor(lst_k, lst_v):
  res = ""
  Lk = len(lst_k)
  Lv = len(lst_v)
  for i in range(Lv):
    if lst_k[i%Lk] == -1:
      res += "*"
    else:
      res += chr(lst_k[i%Lk]^lst_v[i])
  return res

flag_head = "TSGCTF{"
_keystream = []
#[247, 176, 17, 0, 156, 72, 203, -1, -1, -1, -1, -1, -1, -1, -1, 70]
#TSGCTF{********3|2_+|-|********he_saf3|********/_8e_as_********$_you_us********|*pr0|*r********|cry|*+i********_ci|*|-|********0ne_+i|\********)_ra+h3|********\|_a_s+r********3r,_but_********s3(u|2e_********it_us3s_********/|e_r4nd********r$_re|*3********_enjoy_h********)-:)-:)@********dRLICfdh********}
for i,c in enumerate(flag_head):
  _keystream += [ord(c)^cipher[i]]

for _ in range(8):
  _keystream += [-1]

_keystream += [cipher[flag_length-1]^ord("}")]

kscands = []
for i in range(8):
  ks_cand = []
  __keystream = copy.copy(_keystream)
  for j in range(256):
    __keystream[i+7] = j
    result = xor(__keystream, cipher)
    if pattern.fullmatch(result[7:-26].replace("*","")) and pattern2.fullmatch(result[-25:-1].replace("*","")):
      ks_cand.append(j)
  kscands.append(ks_cand)


combinations = list(itertools.product(*kscands))
for combination in combinations:
  keystream = _keystream[0:7] + list(combination) + _keystream[15:]
  result = xor(keystream, cipher)
  flag_content = result[7:-26].encode()
  flag_hash = hashlib.md5(flag_content).digest()
  flag = b"TSGCTF{"+flag_content+b"@"+base64.b64encode(flag_hash)+b"}"
  if flag == result.encode():
    print(keystream)
    print(flag)
    exit()

フラグ

TSGCTF{The_l0n63|2_+|-|3_fla6_the_saf3|2_i+_m4`/_8e_as_lo|\|g_4$_you_use_a|\|_a|*pr0|*ria+3_3|\|cry|*+i0n._Thi$_ci|*|-|3r_i$_4_0ne_+i|\/|e_|*a|)_ra+h3|2_t|-|4|\|_a_s+re4m_(iph3r,_but_it_i$_ins3(u|2e_be(ause_it_us3s_the_$4|\/|e_r4ndom_num83r$_re|*34+3|)ly._enjoy_hahaha_:-)-:)-:)@TWp6sQXidRLICfdhOMY+IA==}

ちなみに、keystreamは [247, 176, 17, 0, 156, 72, 203, 232, 13, 179, 42, 62, 83, 41, 241, 70] でした。

6. upsolve：Delta Force

設問

　楕円曲線（っぽい）問題で、難易度は med-hard（鬼難しい）です。

　問題のスクリプトは SageMath なのに、点のスカラー倍を計算するコードが自前で提供されているということは「欠陥が仕込まれている」か「特異３次曲線」のいずれか、という guess をした後は虚無ってしまい競技中は解けず、でした。

　提供されたデータは以下です。

「problem.sage」

from secret import flag, p, q
from random import SystemRandom
from elliptic_curve import EC

randgen = SystemRandom()
flag += randgen.randbytes(4000 // 8 - len(flag))

f = int.from_bytes(flag, 'big')

assert is_prime(p) and is_prime(q)
N = p * q

R = IntegerModRing(N)
a1 = 3444824117328398332287263145797436732251806993106742790395834211847964497185277822582276657225459760388222788879721727159251866924984494193150653447997603422024763484501407319338008268962141938450376210742802690040775147155751979207058246773645433214949878635670705292205381078390234806850698450436295039666701444937613310617521432088399287665787963949201472844240626719755639541622668049779611715534511220207225102143578882951630506067975785576764801948143058724733822144338788356792891770883002340632245863711872613052190283826616336575324956755899252734899170625497650729243855116042931056447582929301386147920258970755559531421290327063656641559627787073648816453940473655239389908124156165660612689742708373129625588902351602100066924000586976472002309478648159182392535906994995800868902052484891895077235974622067641022944028349866339918120322601296386357756768384853576175451997137719762217320524852380281306558568086807531481968542709466317624453868591793889254468119495169851711195495759784642140806249730424816684480869755835873209370137831042713895026824607183567837804652629953877811080875706500232620906814427668853420025632618707903884500390164422694087209611134445691988003327081785238633702578226975041727958225979248
a2 = 4220657222012863331324022021142115292430597859080918473466273569402786623644966310284686263413321809614975935231589489145653176283755430651257679731781262317639561791314044939921047444940366477586782714676520254598940573251619654210976091118990997406140690658178297711641467793763708001463760191631954449349373914543810395796693214118750609853712197438805175066472570862155591695398007261950273250419125590885574184123001650088433861794755115025331664101776274304102152026455526993460636375440860820326183280743695950579713987688972720640809806839932354448804340284231962944525194259756907531717198723001750563548268505211429663171672155787847084254266041562202569381862742321261337515852288555029875114541634885657856133098628215411753502113867694678392848794557484127610549206348398062803815886751442822499835138675419957858172635972565996494066738623225918806510140877651509362663492336907193615683425402286293202044753906775875048228709714069705104761393891056850481333000346334315445516137338415611089281223529138332726805624561300099605623576433557163093276115663323973176583225088838201896098818427080076586531335010187255421257962154369044435187402303275044435710879669190744621547057417343865042642742729067785757980481708859
a3 = 558053328032569214424924749545080533443204882028700727482902138363914391087914135627507971718720092171365715176468371521485896504111397460977870822260356387271441953304205921733941102285137843514136574063019959717801987678942331305387691085139598494776572670276131522348754285564338055692053988854672468173283148136803799971745169459014171760554786948833430079164649604597281764343627794445260768624935380114208794996054926094746197686261155891021796742555943693683944342826702912295474954080037614961638746950712216471978826697133699862893226784981265765142815822633931592954799220290654691131583229398813285377913420963860081950349348483037678920450399593707900050487766675868613974940533801078648072478704480320992819463523521796820516675896346804256470328012501588846038478735042417434318823499002305595773925357668467999973946928610673937683220558175159559156997545114017452579732447461296275895921770517350210742318724221387478901570280816476239783222112611595977063375839821604111374772017365123591082565390414268391105301111128872682556523124017007950528192427992576438666158999223964016832132347716369554217989660103488591183333215808683339519953259563788055147227130961325434300468212866224123613198733255438000371632201922
a4 = 2409686375529009789062931255151047632553317432871776325977708342575413199868316454516429658254297349908818913648555980905703570378332587211687821833449657319227648023632420349187191203817874908900476265222298630491560124293474130368070578796806092666424986915614853373703916476738812448576677939067552273549664051607033578697950875075526433604321513839183621143953874375023537101509580661583818118731853042627460126855311689628082748074373313182940270826734960431153626135619589835441991890840853823329308534081784864288751938169059434234048947117786007806754996810687735558766333300269431436238258613338745620540366591367671960393239014177679790515185719633955796780366907613116424879434375841785615553717631204945754610331568039531504256955328591989055229298718736414870488253515207480047458000235126179100545819505116852001595203600550936946736697235151062411659082614156384876100227239703938652351269150744501265963390460907632240209469881951684654686080310235283814858158697321466052098007166972602271670115754787224397477919994078767466888020504989901616066772072069140729395181856385314368564511799911756649356907893283650510564887020660017016305620069469798431462964593287090869656274770620420259560247021263773251031107077438
a6 = 3470078186850975739936630083585896206711668380019576458144812382551000399461688662828677551712010444136267839539406491436511536191302115255607338126938721757383820709517878001719275207381244220611138211706395289668473890524220737794043932299829801331641728237036572688318923881312268142947916987785394869895788825813684029625439890374199544512146238573470714240061775578066493778177577497298263101431584499987449107860867974717092406776136120389083101744667140157701396393579936132771094350025878985948459504771054936108295811485497516064375315362547356890406207151247645039645122690527467942787823829138406220130486124334447966832679079367832094353016955534024520702689217787284596726932360141615033646357533622370473604448340917687731406312733759882955505680683319971990286000213361326741481930432680541754817125379558827748942025713721383525941123614481097102581692748593322507617409022332312218948944026657739136377028053975532295249075420561511608283484307148039184136388494407661178023614238682702894250591567479031985618265675418397712856074006023785411792521236472702522327496551883792053117847879265359876050067289453559871911346351148700042996957200697205104421637140069904198053600305602065464319177142877679781718358115411

x = 3187380289473628229166076722741605522066106734974330968029363462853994178034889323396549034418774714004310597327299938638132972121767717298791108552121182926252120215568543440680511528729320460150972551785766528743150693345444523026329817473750107100977751329156774721144063214517285726358018274335181425122425497682910915355289941993635789204613409760838922069179423532756084124424087369187079085568561566146028731452307769275341282229672567986555625437613270131401345164990913073456655478295677780849952336452819811133154540184923229453881172046434709663594257091451745029926858800906234840424320289294896839680690069966831649763526212416442961133572796128363987883784263178284726172207323075552538055360106875136163073733438818095552239514221846774992407935815625138205772383894721080363344299257591334491217283076801413291378680281026191916099741354829618889407157244425285493750026510597867261891663671051439047441921123676903663738851276574650416199443198000844605048534594681961771316401603946312451699473847875708346024353289399679978116606272338553246201412764667063871923809515939019235129599135013826180754092409070369916743385338966842753295793028555461533907357857077718994569945179301205081583517722938903924076665161044
y = 3098509628622199032118889410483498131367153585346875063187101858846530923677876883688759300004198379875832388354339483427258628984564188587177660880817830979516874750329732607401997056978414818886317043638783781007690534739021969383875639013225069704552442992187754882339991182056369690510439789934317089638780423707333159124535609705606295588910501964436737250259915950704729890743964057623145716533126214373974194784113312896436317252284869588214466286181124050804480953801866558673847704787898982600498747562456653841097050232470321543436789172232099599127971642034835964697711543521559007789014820299180115236028167277348348032904641115578872979829671579406457760784565977595271755930086750953607663935048590611365120577239940466584901735242180094939957609545245177604315541505004948250587350636338636915644227983529643209843144781082102080871034333050105691539153291831079893973988409961640177613779257702061258595947270721984862788409947895289380176754001635912693165856017623626949014494500443988487409429044235792054307487109200214875223031796045288551137200587375732192809300189009239330821740285801646366723787253158915642748289216793582895026761306175028926426159594779782097763953591584903850004456396580915118506266981337

P = (x, y)

ec = EC(R, (a1, a2, a3, a4, a6))
assert ec.iszeropoint(P) == True

print(N)
print(ec.scalar(f, P))

「output.txt」

4861176438018509277765150221122126870541685654379801604114760532814287581153000210004207389443213309449018955338869863741674740447811975915078711903955681567092381171537713559560343153877511977292098222368485399204912122010227229078270969924905169787592189375418475308051129528888568681568734206072034666373423912365236817972608366602899547226744432299234711173306225399948633496091891925021506066051269505274591577497904167584767303718241171649947539664809546498443661211509926990737931523544728384428153032760216353730801234655930548104422024130570816728659653538260845032772371478140823258876790879087834215578099103687121280145961921389449249461303695127426477060016215875089488915916633794518511956116049451487462341914580430836466289069310852902452441670591766542607475566151856004189541762250121764347455770924195541519142036527843854325635334990763891612540761801228294679227675034333748671488131374369328481523920448620362794582130982555488343842058198241325525060402667145213028907534526536473479495813172523174608010901013909785818541505226347899760377967331689016937903306728695776347712900417640623152047417427405267791933202247836823133253708561331399337585694285673510222776175851823031760492810621651225757782530492371
(2940137648302822135887768405733428618361214020026143318586301618329372655276898009551187352450543631241584953409424998458467844898870748818109962017628692856154502911778246629019987248210711081379384038506544899037017094206431000794646201463294660352565581410940316447059413267990280103085282255573960006012422254599380011885107374758617951885988212493389139714778955997592191645456603116305632632160041751363247794842614094023112577912814096859442106924317927245381355215404305882813647647808165973585096785363719791485657642484540219214405059891658285454539795978892636754583882973657007442901458945664345488978832970375753192565978853522306244584220151446267601777829062885902539106413866798108556472482002577646588557387807715633128913787076005721277459341934855424070398364463323364862109833382659277887541400854089319386644417923424987803584644908821750251870682987388817038606082810492054657719015315239443896190699718636785628585029435696899067125128349522932992790811417433696577333575752911124735242072095229457254742656832308956471177564651299639347093754244273997643353109038338400428109043737885400764768339281104454669195785957709561673360000645367092746262324437783858934652428309563075654233156559693135917215127084839, 4309188751202413994756093118871339651868155545296257835957631283548458290549834043239999619160131639470537688107285148019375428000337112432317175093336043210190860875690929878131126549041446002208047334350876371320870374521378167548031473971584407464547121329256935748386784077512111069027529070091090512274046019879131201709340032343094129650445987190535015392973173123256087780783994874319281164700525019310387007282075836894663864145318825896934077504337916357614201204461113478545772364849985793786972947231991982415597625212515186739391531585821996127328710500026236144903951637427245223426748300366460373759173484339176020599231393473092295681626107718784321631623410699469438511433557396045657573993803277529816220655895923559584651137391079923579080103751692260916441921214236122141145982485958870445890303087859026075184149723430563928025165528170894575097071775485154541104075542976068077112038847635378050578747036715486956987048325200527662369726957499097289967832182678228473153601275262332757733205093157880270604049046032523006585325029448952623263419851474313757519250802143143825231591931300564658633698464656605919184597056629222214865044578470955523959024153014386918508244536074045249645182811691608730763212420747)

「elliptic_curve.py」

# We don't think you need to worry too much about this file.

class EC:
    O = (0, 1, 0)

    def __init__(self, k, a):
        a1, a2, a3, a4, a6 = map(k, a)
        self.f = lambda x, y: y**2 + a1*x*y + a3*y - x**3 - a2*x**2 - a4*x - a6
        self.dfdx = lambda x, y: a1*y - 3*x**2 - 2*a2*x - a4
        self.dfdy = lambda x, y: 2*y + a1*x + a3
        self.a1 = a1
        self.a2 = a2
        self.a3 = a3
        self.a4 = a4
        self.a6 = a6
        self.k = k

    def iszeropoint(self, p):
        if p == EC.O:
            return True
        x, y = p
        assert not (self.dfdx(x, y) == 0 and self.dfdy(x, y) == 0)
        return self.f(x, y) == self.k(0)

    def negate(self, p):
        if p == EC.O:
            return EC.O
        x, y = p
        return (x, -y - self.a1*x - self.a3)

    def add(self, p1, p2):
        assert (self.iszeropoint(p1) and self.iszeropoint(p2))
        if p1 == EC.O:
            return p2
        if p2 == EC.O:
            return p1
        if self.negate(p1) == p2:
            return EC.O
        if p1 == p2:
            x, y = p1
            x1, x2, y1, y2 = x, x, y, y
            l = (3*x**2 + 2*self.a2*x + self.a4 - self.a1*y) / \
                (2*y + self.a1*x + self.a3)
            n = (-x**3 + self.a4*x + 2*self.a6 - self.a3*y) / \
                (2*y + self.a1*x + self.a3)
        else:
            x1, y1 = p1
            x2, y2 = p2
            l = (y2 - y1) / (x2 - x1)
            n = (y1*x2 - y2*x1) / (x2 - x1)
        x3 = l**2 + self.a1*l - self.a2 - x1 - x2
        y3 = -(l + self.a1) * x3 - n - self.a3
        assert (self.iszeropoint((x3, y3)))
        return (x3, y3)

    def scalar(self, a, p):
        ret = EC.O
        i = 1
        tmp = p
        while i <= a:
            if (i & a) != 0:
                ret = self.add(ret, tmp)
            tmp = self.add(tmp, tmp)
            i <<= 1
        return ret

検討

「欠陥が仕込まれている」ようには見えなかったので、「特異３次曲線」を疑います。

SageMathで、E = EllipticCurve(R,[a1,a2,a3,a4,a6]) としてみると Singular Curve だと言って怒られるので、後者確定です。

しかし判別式を計算してみても 0 になりませんでした*5。おかしいなぁ、ということで競技が終わりました。

解法（競技後に実施したこと）

　チョコラスクさん（@nuo_chocorusk）の Twitter*6での簡易 Write up によると「式変形を進めると p をリークできて、mod.pでcusp、mod.qでnode。さらにq+1はsmooth。」とのことでした。

　このヒントをもとに、解読を進めることにします。なお、以下のサイトが非常に参考になりました。

zenn.dev

STEP 0：ec が特異３次曲線であることのチェック

判別式を計算すると 0 になることを確認しました。

from Crypto.Util.number import *

N = 4861176438018509277765150221122126870541685654379801604114760532814287581153000210004207389443213309449018955338869863741674740447811975915078711903955681567092381171537713559560343153877511977292098222368485399204912122010227229078270969924905169787592189375418475308051129528888568681568734206072034666373423912365236817972608366602899547226744432299234711173306225399948633496091891925021506066051269505274591577497904167584767303718241171649947539664809546498443661211509926990737931523544728384428153032760216353730801234655930548104422024130570816728659653538260845032772371478140823258876790879087834215578099103687121280145961921389449249461303695127426477060016215875089488915916633794518511956116049451487462341914580430836466289069310852902452441670591766542607475566151856004189541762250121764347455770924195541519142036527843854325635334990763891612540761801228294679227675034333748671488131374369328481523920448620362794582130982555488343842058198241325525060402667145213028907534526536473479495813172523174608010901013909785818541505226347899760377967331689016937903306728695776347712900417640623152047417427405267791933202247836823133253708561331399337585694285673510222776175851823031760492810621651225757782530492371
R = IntegerModRing(N)

P = (3187380289473628229166076722741605522066106734974330968029363462853994178034889323396549034418774714004310597327299938638132972121767717298791108552121182926252120215568543440680511528729320460150972551785766528743150693345444523026329817473750107100977751329156774721144063214517285726358018274335181425122425497682910915355289941993635789204613409760838922069179423532756084124424087369187079085568561566146028731452307769275341282229672567986555625437613270131401345164990913073456655478295677780849952336452819811133154540184923229453881172046434709663594257091451745029926858800906234840424320289294896839680690069966831649763526212416442961133572796128363987883784263178284726172207323075552538055360106875136163073733438818095552239514221846774992407935815625138205772383894721080363344299257591334491217283076801413291378680281026191916099741354829618889407157244425285493750026510597867261891663671051439047441921123676903663738851276574650416199443198000844605048534594681961771316401603946312451699473847875708346024353289399679978116606272338553246201412764667063871923809515939019235129599135013826180754092409070369916743385338966842753295793028555461533907357857077718994569945179301205081583517722938903924076665161044, 3098509628622199032118889410483498131367153585346875063187101858846530923677876883688759300004198379875832388354339483427258628984564188587177660880817830979516874750329732607401997056978414818886317043638783781007690534739021969383875639013225069704552442992187754882339991182056369690510439789934317089638780423707333159124535609705606295588910501964436737250259915950704729890743964057623145716533126214373974194784113312896436317252284869588214466286181124050804480953801866558673847704787898982600498747562456653841097050232470321543436789172232099599127971642034835964697711543521559007789014820299180115236028167277348348032904641115578872979829671579406457760784565977595271755930086750953607663935048590611365120577239940466584901735242180094939957609545245177604315541505004948250587350636338636915644227983529643209843144781082102080871034333050105691539153291831079893973988409961640177613779257702061258595947270721984862788409947895289380176754001635912693165856017623626949014494500443988487409429044235792054307487109200214875223031796045288551137200587375732192809300189009239330821740285801646366723787253158915642748289216793582895026761306175028926426159594779782097763953591584903850004456396580915118506266981337)
Q = (2940137648302822135887768405733428618361214020026143318586301618329372655276898009551187352450543631241584953409424998458467844898870748818109962017628692856154502911778246629019987248210711081379384038506544899037017094206431000794646201463294660352565581410940316447059413267990280103085282255573960006012422254599380011885107374758617951885988212493389139714778955997592191645456603116305632632160041751363247794842614094023112577912814096859442106924317927245381355215404305882813647647808165973585096785363719791485657642484540219214405059891658285454539795978892636754583882973657007442901458945664345488978832970375753192565978853522306244584220151446267601777829062885902539106413866798108556472482002577646588557387807715633128913787076005721277459341934855424070398364463323364862109833382659277887541400854089319386644417923424987803584644908821750251870682987388817038606082810492054657719015315239443896190699718636785628585029435696899067125128349522932992790811417433696577333575752911124735242072095229457254742656832308956471177564651299639347093754244273997643353109038338400428109043737885400764768339281104454669195785957709561673360000645367092746262324437783858934652428309563075654233156559693135917215127084839, 4309188751202413994756093118871339651868155545296257835957631283548458290549834043239999619160131639470537688107285148019375428000337112432317175093336043210190860875690929878131126549041446002208047334350876371320870374521378167548031473971584407464547121329256935748386784077512111069027529070091090512274046019879131201709340032343094129650445987190535015392973173123256087780783994874319281164700525019310387007282075836894663864145318825896934077504337916357614201204461113478545772364849985793786972947231991982415597625212515186739391531585821996127328710500026236144903951637427245223426748300366460373759173484339176020599231393473092295681626107718784321631623410699469438511433557396045657573993803277529816220655895923559584651137391079923579080103751692260916441921214236122141145982485958870445890303087859026075184149723430563928025165528170894575097071775485154541104075542976068077112038847635378050578747036715486956987048325200527662369726957499097289967832182678228473153601275262332757733205093157880270604049046032523006585325029448952623263419851474313757519250802143143825231591931300564658633698464656605919184597056629222214865044578470955523959024153014386918508244536074045249645182811691608730763212420747)

a1 = R(3444824117328398332287263145797436732251806993106742790395834211847964497185277822582276657225459760388222788879721727159251866924984494193150653447997603422024763484501407319338008268962141938450376210742802690040775147155751979207058246773645433214949878635670705292205381078390234806850698450436295039666701444937613310617521432088399287665787963949201472844240626719755639541622668049779611715534511220207225102143578882951630506067975785576764801948143058724733822144338788356792891770883002340632245863711872613052190283826616336575324956755899252734899170625497650729243855116042931056447582929301386147920258970755559531421290327063656641559627787073648816453940473655239389908124156165660612689742708373129625588902351602100066924000586976472002309478648159182392535906994995800868902052484891895077235974622067641022944028349866339918120322601296386357756768384853576175451997137719762217320524852380281306558568086807531481968542709466317624453868591793889254468119495169851711195495759784642140806249730424816684480869755835873209370137831042713895026824607183567837804652629953877811080875706500232620906814427668853420025632618707903884500390164422694087209611134445691988003327081785238633702578226975041727958225979248)
a2 = R(4220657222012863331324022021142115292430597859080918473466273569402786623644966310284686263413321809614975935231589489145653176283755430651257679731781262317639561791314044939921047444940366477586782714676520254598940573251619654210976091118990997406140690658178297711641467793763708001463760191631954449349373914543810395796693214118750609853712197438805175066472570862155591695398007261950273250419125590885574184123001650088433861794755115025331664101776274304102152026455526993460636375440860820326183280743695950579713987688972720640809806839932354448804340284231962944525194259756907531717198723001750563548268505211429663171672155787847084254266041562202569381862742321261337515852288555029875114541634885657856133098628215411753502113867694678392848794557484127610549206348398062803815886751442822499835138675419957858172635972565996494066738623225918806510140877651509362663492336907193615683425402286293202044753906775875048228709714069705104761393891056850481333000346334315445516137338415611089281223529138332726805624561300099605623576433557163093276115663323973176583225088838201896098818427080076586531335010187255421257962154369044435187402303275044435710879669190744621547057417343865042642742729067785757980481708859)
a3 = R(558053328032569214424924749545080533443204882028700727482902138363914391087914135627507971718720092171365715176468371521485896504111397460977870822260356387271441953304205921733941102285137843514136574063019959717801987678942331305387691085139598494776572670276131522348754285564338055692053988854672468173283148136803799971745169459014171760554786948833430079164649604597281764343627794445260768624935380114208794996054926094746197686261155891021796742555943693683944342826702912295474954080037614961638746950712216471978826697133699862893226784981265765142815822633931592954799220290654691131583229398813285377913420963860081950349348483037678920450399593707900050487766675868613974940533801078648072478704480320992819463523521796820516675896346804256470328012501588846038478735042417434318823499002305595773925357668467999973946928610673937683220558175159559156997545114017452579732447461296275895921770517350210742318724221387478901570280816476239783222112611595977063375839821604111374772017365123591082565390414268391105301111128872682556523124017007950528192427992576438666158999223964016832132347716369554217989660103488591183333215808683339519953259563788055147227130961325434300468212866224123613198733255438000371632201922)
a4 = R(2409686375529009789062931255151047632553317432871776325977708342575413199868316454516429658254297349908818913648555980905703570378332587211687821833449657319227648023632420349187191203817874908900476265222298630491560124293474130368070578796806092666424986915614853373703916476738812448576677939067552273549664051607033578697950875075526433604321513839183621143953874375023537101509580661583818118731853042627460126855311689628082748074373313182940270826734960431153626135619589835441991890840853823329308534081784864288751938169059434234048947117786007806754996810687735558766333300269431436238258613338745620540366591367671960393239014177679790515185719633955796780366907613116424879434375841785615553717631204945754610331568039531504256955328591989055229298718736414870488253515207480047458000235126179100545819505116852001595203600550936946736697235151062411659082614156384876100227239703938652351269150744501265963390460907632240209469881951684654686080310235283814858158697321466052098007166972602271670115754787224397477919994078767466888020504989901616066772072069140729395181856385314368564511799911756649356907893283650510564887020660017016305620069469798431462964593287090869656274770620420259560247021263773251031107077438)
a6 = R(3470078186850975739936630083585896206711668380019576458144812382551000399461688662828677551712010444136267839539406491436511536191302115255607338126938721757383820709517878001719275207381244220611138211706395289668473890524220737794043932299829801331641728237036572688318923881312268142947916987785394869895788825813684029625439890374199544512146238573470714240061775578066493778177577497298263101431584499987449107860867974717092406776136120389083101744667140157701396393579936132771094350025878985948459504771054936108295811485497516064375315362547356890406207151247645039645122690527467942787823829138406220130486124334447966832679079367832094353016955534024520702689217787284596726932360141615033646357533622370473604448340917687731406312733759882955505680683319971990286000213361326741481930432680541754817125379558827748942025713721383525941123614481097102581692748593322507617409022332312218948944026657739136377028053975532295249075420561511608283484307148039184136388494407661178023614238682702894250591567479031985618265675418397712856074006023785411792521236472702522327496551883792053117847879265359876050067289453559871911346351148700042996957200697205104421637140069904198053600305602065464319177142877679781718358115411)

######### check ##########
# ec = EllipticCurve(R,[a1,a2,a3,a4,a6])
# ... defines a singular curve
b2 = a1^2 + 4*a2
b4 = 2*a4 + a1*a3
b6 = a3^2 + 4*a6
b8 = a1^2*a6 + 4*a2*a6 - a1*a3*a4 + a2*a3^2-a4^2
Delta = -b2^2*b8 - 8*b4^3 - 27*b6^2 + 9*b2*b4*b6
assert Delta == 0 #Singular Curve

STEP 1：シンプルな標準系に変換する

今のままでは係数が 5 個あって分かりづらいので、Y² = X³+a*X+b への変形を考えます。

######### Analyze ##########
PR0.<x,y,X,Y> = PolynomialRing(R)
f0 = y^2 + a1*y*x + a3*y - x^3 - a2*x^2 - a4*x - a6
assert f0(x=P[0], y=P[1]) == 0
assert f0(x=Q[0], y=Q[1]) == 0

# y => Y - (a1*x + a3)//2
f1 = f0.subs(y = Y - (a1*x + a3)/2)
b = f1.coefficient(x^2)
f2 = f1.subs(x = X + b/3)

PR1.<X,Y> = PolynomialRing(R)
f3 = PR1(f2)

計算の結果、この問題の曲線は、

Y^2  = X^3 -1782772986077906947398161154611262672698085996750415656787400197232301329141096392638841718848841461045696748130475932349922740877072798358262467426166990744859814521978436212570218735011383887386070573099691328397240050983505893877272788360039317308749263137795783185473725098032243805116314925678934143651960544434889710387271335918163319115893968197594791128474522351755847230249626878480035493253857780366178948242046227798187142511146214143836797352425755112851057706884728240686537812505737844206256796940202705934889434138156532821366289539535204650510598356053533888371591103954462027601414064132462121594952778819632518227450677913374854400103815440143327770819384109592373707544368119311956717858706923131086243980325128525985363828797451066888033025440264642999659477879076592281675898977112498795935200696311845294162691874849919740793646751137986567414169481384755779128369009038255025874614556046404072103973656812997823968952181042835900299402955339574842852746713968635794035772942274834154510828807541518296692998595854650601336274907820832654163617862793353382430338377859401426673041601517320951508701089743829494989851735642119599455902996313321975256640189038465961553824517793299086380262755811311111044312523697*X - 460255453040082609039062173909877472458592648513160488464891038020917420358090689174483182851647864306239488481565009929181987804440820459854836413549708603659153341000337745470562319739417631129934291462101981943712282128616213213360422088600908238898356609909435591446349931086020564395395033010746911919519190300730284557407330783350408157891639261783941551668541358349835527455266094595253598336852853791968860878415006266571207638735692435326462662153000603126317884961295182239142006860789297560377587886685644292791627551059979746706812269560002683614945130106478663421105517840479631187475491315937820212138497411432423500637238469838542234377123469538854541390614645228151486679064055140837255892143576743703354233121355236520534254247450986181370138965260769645727235019221709898689995215812577795135718741429934899665541533494953911002481459437461763730089974393341691226020287403568067975252738070825411069288325187314548015732692436715643526933390477985534488670496582659603645683184289840900151735282668256472272260179219819977863593858768005839962810375782735690829181635308848496793436491862436102411169777090093975153011171646469538419410920026326677730436104787915013598607999463380156553612494895732048200795751268

と表せることがわかります。

STEP 2：p、q のリーク*7

もし前ステップで得た曲線が cusp なら右辺を x³ の形に変形でき、nodeなら x³+k*x² の形に変形できるはずです。

ここで、いささか天下り的ではあるのですが、mod.p や mod.q での cusp の可能性を考えて、係数と N の GCD をとってみます。

（ここさえクリアできれば、あとはどうにか解けます。）

######### Leak p and q ##########
for c in f3.coefficients():
  if GCD(int(c), int(N))>1:
     p = GCD(int(c),int(N))
     break
q = int(N // p)

これで、

p = 19966952433773622647280963975099603139887593811319990392386894015754446652166446583126433891381570960655713132784650529099582626057886843845523086233188406269001276634158864443217174272472344936896651588970524709312501309698998984063721586210726769606009586215682950765028731638344224398860877069687796137644867440403571014084723477843620793678398876055430128756284754677588405484857364333795470643784083101380058253039735957367939149090758564175640488705079822217679316031716853338402912047783502678971112202058508589384041927358507109319566814540113223437922507783585905695518188920379272309405106729442789658373543

q = 243461111761649993207760947168400804284506306341364302214804755342576984247538465504320804181821117732296445218442722698044016495591355224588160790051125271634950950583507948393226492011352077815035445968846776970268783772849695094433790503876703921214802543382520171552286215155198920398561695803081334247520368425036727612588452045666710947993842012648371635039538156053017069542703517491519451818168781094985349793723987927135325283707772252693501877136194933452282923455736306827546620604423399356092100856126588466821433682033880010011027969816147027236415931807322312109176103897969140571047988318244965072490997

N の素因数分解ができました。

STEP 3：mod.p における DLP

STEP 1 の式を mod.p すると、Y² - X³ = 0 となり mod.p で cusp であることがわかります。

cusp の場合は P(x,y) => GF(p)(x)/GF(p)(y) で GF(p)の加法群に埋め込めるので、GF(p)の割り算で DLP が計算できてしまいます。

######### p-part ##########
Fp = GF(p)
PRp.<X,Y> = PolynomialRing(Fp)
fp = PRp(f3)

pPx = int((R(P[0]) - b/3)) % p
pPy = int((R(P[1]) + (a1*R(P[0]) + a3)/2)) % p
assert fp(X=pPx, Y=pPy) == 0

pQx = int((R(Q[0]) - b/3)) % p
pQy = int((R(Q[1]) + (a1*R(Q[0]) + a3)/2)) % p
assert fp(X=pQx, Y=pQy) == 0

pP = Fp(pPx) / Fp(pPy)
pQ = Fp(pQx) / Fp(pQy)

dp = int(pQ / pP)
#7025039839405611704428712111958349759207458322311670522833450294594383611305677315165985633952030664650635786258165673555465765114643315329353732069777461611751401761914674544356002960784308336509117984388967658384064369100257087912674883067185727519262450590830292550941825022956963193945281389835126338245274010394538063535825061487884323562882347566231815838974746812315006801569379361882901876123000638009135938363380696236844415141937838559729033137284794041322092847877250621506154367893945827762951215514669043938383586688710447277597985025968563205006521697153748676370588892777468314258711170654206087750994

STEP 4：mod.q における DLP

STEP 1 の式を mod.q して変形すると、Y² - X³ = 0 の形にはならず、node であることがわかります。

nodeの場合、Y² = X³ + k*X²の形に変形できるので、まずはその計算を行います。

######### q-part ##########
Fq = GF(q)
PRq.<X,Y> = PolynomialRing(Zmod(q))
fq = PRq(f3)

_qPx = int((R(P[0]) - b/3)) % q
qPy = int((R(P[1]) + (a1*R(P[0]) + a3)/2)) % q
assert fq(X=_qPx, Y=qPy) == 0

_qQx = int((R(Q[0]) - b/3)) % q
qQy = int((R(Q[1]) + (a1*R(Q[0]) + a3)/2)) % q
assert fq(X=_qQx, Y=qQy) == 0

g = fq.subs(Y=0)
PRq1.<X> = PolynomialRing(Zmod(q))
g = PRq1(g)
g = g.monic()
gfs = g.factor()
for gf in gfs:
  if gf[1] == 2:
    t = gf[0].coefficients()[0] * (-1)
    break

#t = -220245088672960781103079450441569380123504516861586630449711395366387206780610484939221421188906153372683673506059911580546567384505353717412806357593230478001104993520292577846240999112167805726361323732962842065785296446355459236089194685765154359364711405630154143070398847547382044206182648549134289295137156095173663548105329485798390603122316915595789064390123686094266685907138664310799482653570001038381776419919948790739594392256805807766318813932833956215538589896017765298795682383685684703878099310275290181834050748659153544107542770069457223232619173173527584835994066130729007055918581967404028607366508
g2 = g.subs(X = X+t)
g2 = PRq1(g2)
k = g2.coefficients()[0]
k = Fq(k)

しかし、この問題には一つ罠があって、おそらくそれが「med-hard」の所以かと思うのですが、この k は Fqの平方数ではありません。ですので、g(z):=z² - k の最小分解体で議論をする必要があります。

PR2.<z> = PolynomialRing(Fq)
g = z^2 - k

_Fq.<a> = g.splitting_field()
k = _Fq(k)

sk = k.sqrt()
#162232900175888562003325744668525554624415021281425098396272737914535345383960144272343369193548483796506627212985596786523381831296976903064692267590904419812297991258323146654806459790940475563943858373167116325897204220438957546054005865399846837641733441609696205280240170577344585723326274832653912316075198709383688233726074856590594508498072029870880133672151971662261760998366130513145750019965563154108087932191319634492837517693437225424931642335866758148457035829406659694863762700729835385077559096890896806281042792138778480938544450159805455489179568634479653568649514424006907004748846687489558879691382*a + 81116450087944281001662872334262777312207510640712549198136368957267672691980072136171684596774241898253313606492798393261690915648488451532346133795452209906148995629161573327403229895470237781971929186583558162948602110219478773027002932699923418820866720804848102640120085288672292861663137416326956158037599354691844116863037428295297254249036014935440066836075985831130880499183065256572875009982781577054043966095659817246418758846718612712465821167933379074228517914703329847431881350364917692538779548445448403140521396069389240469272225079902727744589784317239826784324757212003453502374423343744779439845691

_fq = fq.subs(X=X+t)
qPx = _qPx - t
qQx = _qQx - t
assert _fq(X=qPx, Y=qPy) == 0
assert _fq(X=qQx, Y=qQy) == 0

_P = _Fq(qPy + sk*qPx) / _Fq(qPy - sk*qPx) 
_Q = _Fq(qQy + sk*qQx) / _Fq(qQy - sk*qQx) 

あとは、上で求めた _P、_Q を _Fq の乗法群に埋め込んで DLPすることになります。

_P の乗法位数は q²-1 の約数ですが、計算してみると _P^q+1 = 1 となるので乗法位数は q+1（の約数）であることが分かります。

幸いにして q+1 は非常に smooth なので、DLP の計算が出来てしまいます。

#factors of q+1: order of _P
assert pow(_P,q+1) == 1
orderof_P = q + 1 
factors, exponents = zip(*factor(orderof_P))
primes = [factors[i] ^ exponents[i] for i in range(len(factors))]
dlogs = []

for fac in primes:
  t = int(orderof_P) // int(fac)
  dlog = discrete_log(pow(_Q,t),pow(_P,t), fac)
  dlogs += [dlog]
  print("factor: "+str(fac)+", Discrete Log: "+str(dlog))

dq = crt(dlogs, primes)
#154075924574486175347562707909961851402473727702317014643095837103684216209007400449603645038526706544810274253183915272469230486051463763376281249086241018042323557902517109795258549187502855001546939039636627742750565210192130958634960554514582139821851491012805037749372205891490027899780633462385372566211372295338704317555889404525927560364933196695956191547549400570151698776808151665849614088600216427777499739843872660202818084555597128524362080176403087726056343256360787083367650029121152781001815493814784689811694461739837548360105812995919537253775141056337613175724504154405630673812583838536950403083982

STEP 5：mod.N における DLP

STEP3、STEP4 の結果を合わせて、mod.N での DLP を計算します。 このとき、STEP3 の計算は GF(p)の加法群（order=p）への埋め込みであったことに注意します。

######### join ##########
m = int(crt([dp, dq],[int(p),int(q+1)]))
print(long_to_bytes(int(m)))

これでフラグをゲットできます。

ソルバ（前記解法をまとめたもの）

「solve.sage」

from Crypto.Util.number import *

N = 4861176438018509277765150221122126870541685654379801604114760532814287581153000210004207389443213309449018955338869863741674740447811975915078711903955681567092381171537713559560343153877511977292098222368485399204912122010227229078270969924905169787592189375418475308051129528888568681568734206072034666373423912365236817972608366602899547226744432299234711173306225399948633496091891925021506066051269505274591577497904167584767303718241171649947539664809546498443661211509926990737931523544728384428153032760216353730801234655930548104422024130570816728659653538260845032772371478140823258876790879087834215578099103687121280145961921389449249461303695127426477060016215875089488915916633794518511956116049451487462341914580430836466289069310852902452441670591766542607475566151856004189541762250121764347455770924195541519142036527843854325635334990763891612540761801228294679227675034333748671488131374369328481523920448620362794582130982555488343842058198241325525060402667145213028907534526536473479495813172523174608010901013909785818541505226347899760377967331689016937903306728695776347712900417640623152047417427405267791933202247836823133253708561331399337585694285673510222776175851823031760492810621651225757782530492371
R = IntegerModRing(N)

P = (3187380289473628229166076722741605522066106734974330968029363462853994178034889323396549034418774714004310597327299938638132972121767717298791108552121182926252120215568543440680511528729320460150972551785766528743150693345444523026329817473750107100977751329156774721144063214517285726358018274335181425122425497682910915355289941993635789204613409760838922069179423532756084124424087369187079085568561566146028731452307769275341282229672567986555625437613270131401345164990913073456655478295677780849952336452819811133154540184923229453881172046434709663594257091451745029926858800906234840424320289294896839680690069966831649763526212416442961133572796128363987883784263178284726172207323075552538055360106875136163073733438818095552239514221846774992407935815625138205772383894721080363344299257591334491217283076801413291378680281026191916099741354829618889407157244425285493750026510597867261891663671051439047441921123676903663738851276574650416199443198000844605048534594681961771316401603946312451699473847875708346024353289399679978116606272338553246201412764667063871923809515939019235129599135013826180754092409070369916743385338966842753295793028555461533907357857077718994569945179301205081583517722938903924076665161044, 3098509628622199032118889410483498131367153585346875063187101858846530923677876883688759300004198379875832388354339483427258628984564188587177660880817830979516874750329732607401997056978414818886317043638783781007690534739021969383875639013225069704552442992187754882339991182056369690510439789934317089638780423707333159124535609705606295588910501964436737250259915950704729890743964057623145716533126214373974194784113312896436317252284869588214466286181124050804480953801866558673847704787898982600498747562456653841097050232470321543436789172232099599127971642034835964697711543521559007789014820299180115236028167277348348032904641115578872979829671579406457760784565977595271755930086750953607663935048590611365120577239940466584901735242180094939957609545245177604315541505004948250587350636338636915644227983529643209843144781082102080871034333050105691539153291831079893973988409961640177613779257702061258595947270721984862788409947895289380176754001635912693165856017623626949014494500443988487409429044235792054307487109200214875223031796045288551137200587375732192809300189009239330821740285801646366723787253158915642748289216793582895026761306175028926426159594779782097763953591584903850004456396580915118506266981337)
Q = (2940137648302822135887768405733428618361214020026143318586301618329372655276898009551187352450543631241584953409424998458467844898870748818109962017628692856154502911778246629019987248210711081379384038506544899037017094206431000794646201463294660352565581410940316447059413267990280103085282255573960006012422254599380011885107374758617951885988212493389139714778955997592191645456603116305632632160041751363247794842614094023112577912814096859442106924317927245381355215404305882813647647808165973585096785363719791485657642484540219214405059891658285454539795978892636754583882973657007442901458945664345488978832970375753192565978853522306244584220151446267601777829062885902539106413866798108556472482002577646588557387807715633128913787076005721277459341934855424070398364463323364862109833382659277887541400854089319386644417923424987803584644908821750251870682987388817038606082810492054657719015315239443896190699718636785628585029435696899067125128349522932992790811417433696577333575752911124735242072095229457254742656832308956471177564651299639347093754244273997643353109038338400428109043737885400764768339281104454669195785957709561673360000645367092746262324437783858934652428309563075654233156559693135917215127084839, 4309188751202413994756093118871339651868155545296257835957631283548458290549834043239999619160131639470537688107285148019375428000337112432317175093336043210190860875690929878131126549041446002208047334350876371320870374521378167548031473971584407464547121329256935748386784077512111069027529070091090512274046019879131201709340032343094129650445987190535015392973173123256087780783994874319281164700525019310387007282075836894663864145318825896934077504337916357614201204461113478545772364849985793786972947231991982415597625212515186739391531585821996127328710500026236144903951637427245223426748300366460373759173484339176020599231393473092295681626107718784321631623410699469438511433557396045657573993803277529816220655895923559584651137391079923579080103751692260916441921214236122141145982485958870445890303087859026075184149723430563928025165528170894575097071775485154541104075542976068077112038847635378050578747036715486956987048325200527662369726957499097289967832182678228473153601275262332757733205093157880270604049046032523006585325029448952623263419851474313757519250802143143825231591931300564658633698464656605919184597056629222214865044578470955523959024153014386918508244536074045249645182811691608730763212420747)

a1 = R(3444824117328398332287263145797436732251806993106742790395834211847964497185277822582276657225459760388222788879721727159251866924984494193150653447997603422024763484501407319338008268962141938450376210742802690040775147155751979207058246773645433214949878635670705292205381078390234806850698450436295039666701444937613310617521432088399287665787963949201472844240626719755639541622668049779611715534511220207225102143578882951630506067975785576764801948143058724733822144338788356792891770883002340632245863711872613052190283826616336575324956755899252734899170625497650729243855116042931056447582929301386147920258970755559531421290327063656641559627787073648816453940473655239389908124156165660612689742708373129625588902351602100066924000586976472002309478648159182392535906994995800868902052484891895077235974622067641022944028349866339918120322601296386357756768384853576175451997137719762217320524852380281306558568086807531481968542709466317624453868591793889254468119495169851711195495759784642140806249730424816684480869755835873209370137831042713895026824607183567837804652629953877811080875706500232620906814427668853420025632618707903884500390164422694087209611134445691988003327081785238633702578226975041727958225979248)
a2 = R(4220657222012863331324022021142115292430597859080918473466273569402786623644966310284686263413321809614975935231589489145653176283755430651257679731781262317639561791314044939921047444940366477586782714676520254598940573251619654210976091118990997406140690658178297711641467793763708001463760191631954449349373914543810395796693214118750609853712197438805175066472570862155591695398007261950273250419125590885574184123001650088433861794755115025331664101776274304102152026455526993460636375440860820326183280743695950579713987688972720640809806839932354448804340284231962944525194259756907531717198723001750563548268505211429663171672155787847084254266041562202569381862742321261337515852288555029875114541634885657856133098628215411753502113867694678392848794557484127610549206348398062803815886751442822499835138675419957858172635972565996494066738623225918806510140877651509362663492336907193615683425402286293202044753906775875048228709714069705104761393891056850481333000346334315445516137338415611089281223529138332726805624561300099605623576433557163093276115663323973176583225088838201896098818427080076586531335010187255421257962154369044435187402303275044435710879669190744621547057417343865042642742729067785757980481708859)
a3 = R(558053328032569214424924749545080533443204882028700727482902138363914391087914135627507971718720092171365715176468371521485896504111397460977870822260356387271441953304205921733941102285137843514136574063019959717801987678942331305387691085139598494776572670276131522348754285564338055692053988854672468173283148136803799971745169459014171760554786948833430079164649604597281764343627794445260768624935380114208794996054926094746197686261155891021796742555943693683944342826702912295474954080037614961638746950712216471978826697133699862893226784981265765142815822633931592954799220290654691131583229398813285377913420963860081950349348483037678920450399593707900050487766675868613974940533801078648072478704480320992819463523521796820516675896346804256470328012501588846038478735042417434318823499002305595773925357668467999973946928610673937683220558175159559156997545114017452579732447461296275895921770517350210742318724221387478901570280816476239783222112611595977063375839821604111374772017365123591082565390414268391105301111128872682556523124017007950528192427992576438666158999223964016832132347716369554217989660103488591183333215808683339519953259563788055147227130961325434300468212866224123613198733255438000371632201922)
a4 = R(2409686375529009789062931255151047632553317432871776325977708342575413199868316454516429658254297349908818913648555980905703570378332587211687821833449657319227648023632420349187191203817874908900476265222298630491560124293474130368070578796806092666424986915614853373703916476738812448576677939067552273549664051607033578697950875075526433604321513839183621143953874375023537101509580661583818118731853042627460126855311689628082748074373313182940270826734960431153626135619589835441991890840853823329308534081784864288751938169059434234048947117786007806754996810687735558766333300269431436238258613338745620540366591367671960393239014177679790515185719633955796780366907613116424879434375841785615553717631204945754610331568039531504256955328591989055229298718736414870488253515207480047458000235126179100545819505116852001595203600550936946736697235151062411659082614156384876100227239703938652351269150744501265963390460907632240209469881951684654686080310235283814858158697321466052098007166972602271670115754787224397477919994078767466888020504989901616066772072069140729395181856385314368564511799911756649356907893283650510564887020660017016305620069469798431462964593287090869656274770620420259560247021263773251031107077438)
a6 = R(3470078186850975739936630083585896206711668380019576458144812382551000399461688662828677551712010444136267839539406491436511536191302115255607338126938721757383820709517878001719275207381244220611138211706395289668473890524220737794043932299829801331641728237036572688318923881312268142947916987785394869895788825813684029625439890374199544512146238573470714240061775578066493778177577497298263101431584499987449107860867974717092406776136120389083101744667140157701396393579936132771094350025878985948459504771054936108295811485497516064375315362547356890406207151247645039645122690527467942787823829138406220130486124334447966832679079367832094353016955534024520702689217787284596726932360141615033646357533622370473604448340917687731406312733759882955505680683319971990286000213361326741481930432680541754817125379558827748942025713721383525941123614481097102581692748593322507617409022332312218948944026657739136377028053975532295249075420561511608283484307148039184136388494407661178023614238682702894250591567479031985618265675418397712856074006023785411792521236472702522327496551883792053117847879265359876050067289453559871911346351148700042996957200697205104421637140069904198053600305602065464319177142877679781718358115411)

######### check ##########
# ec = EllipticCurve(R,[a1,a2,a3,a4,a6])
# ... defines a singular curve
b2 = a1^2 + 4*a2
b4 = 2*a4 + a1*a3
b6 = a3^2 + 4*a6
b8 = a1^2*a6 + 4*a2*a6 - a1*a3*a4 + a2*a3^2-a4^2
Delta = -b2^2*b8 - 8*b4^3 - 27*b6^2 + 9*b2*b4*b6
assert Delta == 0 #Singular Curve

######### Analyze ##########
PR0.<x,y,X,Y> = PolynomialRing(R)
f0 = y^2 + a1*y*x + a3*y - x^3 - a2*x^2 - a4*x - a6
assert f0(x=P[0], y=P[1]) == 0
assert f0(x=Q[0], y=Q[1]) == 0

# y => Y - (a1*x + a3)//2
f1 = f0.subs(y = Y - (a1*x + a3)/2)
b = f1.coefficient(x^2)
f2 = f1.subs(x = X + b/3)

PR1.<X,Y> = PolynomialRing(R)
f3 = PR1(f2)
# Y^2  = X^3 -1782772986077906947398161154611262672698085996750415656787400197232301329141096392638841718848841461045696748130475932349922740877072798358262467426166990744859814521978436212570218735011383887386070573099691328397240050983505893877272788360039317308749263137795783185473725098032243805116314925678934143651960544434889710387271335918163319115893968197594791128474522351755847230249626878480035493253857780366178948242046227798187142511146214143836797352425755112851057706884728240686537812505737844206256796940202705934889434138156532821366289539535204650510598356053533888371591103954462027601414064132462121594952778819632518227450677913374854400103815440143327770819384109592373707544368119311956717858706923131086243980325128525985363828797451066888033025440264642999659477879076592281675898977112498795935200696311845294162691874849919740793646751137986567414169481384755779128369009038255025874614556046404072103973656812997823968952181042835900299402955339574842852746713968635794035772942274834154510828807541518296692998595854650601336274907820832654163617862793353382430338377859401426673041601517320951508701089743829494989851735642119599455902996313321975256640189038465961553824517793299086380262755811311111044312523697*X - 460255453040082609039062173909877472458592648513160488464891038020917420358090689174483182851647864306239488481565009929181987804440820459854836413549708603659153341000337745470562319739417631129934291462101981943712282128616213213360422088600908238898356609909435591446349931086020564395395033010746911919519190300730284557407330783350408157891639261783941551668541358349835527455266094595253598336852853791968860878415006266571207638735692435326462662153000603126317884961295182239142006860789297560377587886685644292791627551059979746706812269560002683614945130106478663421105517840479631187475491315937820212138497411432423500637238469838542234377123469538854541390614645228151486679064055140837255892143576743703354233121355236520534254247450986181370138965260769645727235019221709898689995215812577795135718741429934899665541533494953911002481459437461763730089974393341691226020287403568067975252738070825411069288325187314548015732692436715643526933390477985534488670496582659603645683184289840900151735282668256472272260179219819977863593858768005839962810375782735690829181635308848496793436491862436102411169777090093975153011171646469538419410920026326677730436104787915013598607999463380156553612494895732048200795751268

######### Leak p and q ##########
for c in f3.coefficients():
  if GCD(int(c), int(N))>1:
     p = GCD(int(c),int(N))
     break
q = int(N // p)

assert isPrime(p)
assert isPrime(q)
#p = 19966952433773622647280963975099603139887593811319990392386894015754446652166446583126433891381570960655713132784650529099582626057886843845523086233188406269001276634158864443217174272472344936896651588970524709312501309698998984063721586210726769606009586215682950765028731638344224398860877069687796137644867440403571014084723477843620793678398876055430128756284754677588405484857364333795470643784083101380058253039735957367939149090758564175640488705079822217679316031716853338402912047783502678971112202058508589384041927358507109319566814540113223437922507783585905695518188920379272309405106729442789658373543
#q = 243461111761649993207760947168400804284506306341364302214804755342576984247538465504320804181821117732296445218442722698044016495591355224588160790051125271634950950583507948393226492011352077815035445968846776970268783772849695094433790503876703921214802543382520171552286215155198920398561695803081334247520368425036727612588452045666710947993842012648371635039538156053017069542703517491519451818168781094985349793723987927135325283707772252693501877136194933452282923455736306827546620604423399356092100856126588466821433682033880010011027969816147027236415931807322312109176103897969140571047988318244965072490997

######### p-part ##########
Fp = GF(p)
PRp.<X,Y> = PolynomialRing(Fp)
fp = PRp(f3)

pPx = int((R(P[0]) - b/3)) % p
pPy = int((R(P[1]) + (a1*R(P[0]) + a3)/2)) % p
assert fp(X=pPx, Y=pPy) == 0

pQx = int((R(Q[0]) - b/3)) % p
pQy = int((R(Q[1]) + (a1*R(Q[0]) + a3)/2)) % p
assert fp(X=pQx, Y=pQy) == 0

pP = Fp(pPx) / Fp(pPy)
pQ = Fp(pQx) / Fp(pQy)

dp = int(pQ / pP)
#7025039839405611704428712111958349759207458322311670522833450294594383611305677315165985633952030664650635786258165673555465765114643315329353732069777461611751401761914674544356002960784308336509117984388967658384064369100257087912674883067185727519262450590830292550941825022956963193945281389835126338245274010394538063535825061487884323562882347566231815838974746812315006801569379361882901876123000638009135938363380696236844415141937838559729033137284794041322092847877250621506154367893945827762951215514669043938383586688710447277597985025968563205006521697153748676370588892777468314258711170654206087750994

######### q-part ##########
Fq = GF(q)
PRq.<X,Y> = PolynomialRing(Zmod(q))
fq = PRq(f3)

_qPx = int((R(P[0]) - b/3)) % q
qPy = int((R(P[1]) + (a1*R(P[0]) + a3)/2)) % q
assert fq(X=_qPx, Y=qPy) == 0

_qQx = int((R(Q[0]) - b/3)) % q
qQy = int((R(Q[1]) + (a1*R(Q[0]) + a3)/2)) % q
assert fq(X=_qQx, Y=qQy) == 0

g = fq.subs(Y=0)
PRq1.<X> = PolynomialRing(Zmod(q))
g = PRq1(g)
g = g.monic()
gfs = g.factor()
for gf in gfs:
  if gf[1] == 2:
    t = gf[0].coefficients()[0] * (-1)
    break

#t = -220245088672960781103079450441569380123504516861586630449711395366387206780610484939221421188906153372683673506059911580546567384505353717412806357593230478001104993520292577846240999112167805726361323732962842065785296446355459236089194685765154359364711405630154143070398847547382044206182648549134289295137156095173663548105329485798390603122316915595789064390123686094266685907138664310799482653570001038381776419919948790739594392256805807766318813932833956215538589896017765298795682383685684703878099310275290181834050748659153544107542770069457223232619173173527584835994066130729007055918581967404028607366508
g2 = g.subs(X = X+t)
g2 = PRq1(g2)
k = g2.coefficients()[0]
k = Fq(k)

PR2.<z> = PolynomialRing(Fq)
g = z^2 - k

_Fq.<a> = g.splitting_field()
k = _Fq(k)
sk = k.sqrt()
#162232900175888562003325744668525554624415021281425098396272737914535345383960144272343369193548483796506627212985596786523381831296976903064692267590904419812297991258323146654806459790940475563943858373167116325897204220438957546054005865399846837641733441609696205280240170577344585723326274832653912316075198709383688233726074856590594508498072029870880133672151971662261760998366130513145750019965563154108087932191319634492837517693437225424931642335866758148457035829406659694863762700729835385077559096890896806281042792138778480938544450159805455489179568634479653568649514424006907004748846687489558879691382*a + 81116450087944281001662872334262777312207510640712549198136368957267672691980072136171684596774241898253313606492798393261690915648488451532346133795452209906148995629161573327403229895470237781971929186583558162948602110219478773027002932699923418820866720804848102640120085288672292861663137416326956158037599354691844116863037428295297254249036014935440066836075985831130880499183065256572875009982781577054043966095659817246418758846718612712465821167933379074228517914703329847431881350364917692538779548445448403140521396069389240469272225079902727744589784317239826784324757212003453502374423343744779439845691

_fq = fq.subs(X=X+t)
qPx = _qPx - t
qQx = _qQx - t
assert _fq(X=qPx, Y=qPy) == 0
assert _fq(X=qQx, Y=qQy) == 0

_P = _Fq(qPy + sk*qPx) / _Fq(qPy - sk*qPx) 
_Q = _Fq(qQy + sk*qQx) / _Fq(qQy - sk*qQx) 

#factors of q+1: order of _P
assert pow(_P,q+1) == 1
orderof_P = q + 1 
factors, exponents = zip(*factor(orderof_P))
primes = [factors[i] ^ exponents[i] for i in range(len(factors))]
dlogs = []

for fac in primes:
  t = int(orderof_P) // int(fac)
  dlog = discrete_log(pow(_Q,t),pow(_P,t), fac)
  dlogs += [dlog]
  print("factor: "+str(fac)+", Discrete Log: "+str(dlog))

dq = crt(dlogs, primes)
#154075924574486175347562707909961851402473727702317014643095837103684216209007400449603645038526706544810274253183915272469230486051463763376281249086241018042323557902517109795258549187502855001546939039636627742750565210192130958634960554514582139821851491012805037749372205891490027899780633462385372566211372295338704317555889404525927560364933196695956191547549400570151698776808151665849614088600216427777499739843872660202818084555597128524362080176403087726056343256360787083367650029121152781001815493814784689811694461739837548360105812995919537253775141056337613175724504154405630673812583838536950403083982

######### join ##########
m = int(crt([dp, dq],[int(p),int(q+1)]))
print(long_to_bytes(int(m)))

フラグ

TSGCTF{@l1_y0u_n3Ed_IS_ReaDiNG_5ilvErman_ThE_@r1thmetic_of_e11iPtiC_cURVe5}

*1:総帥兼プレイヤー "Edwow Math" からなるソロチームです。

*2:いつもどおり、虚無っていた時間を多々含みます。

*3:いつものとおりです。

*4:md5の結果をbase64すると末尾は必ず「==」になるので、実はあと2バイト判明させることができたのですが、競技中は全く気づきませんでした。

*5:後に、計算ミスであることが判明。

*6:あえて「X」とは呼びません！都営荒川線・東武野田線も同じ。

*7:もちろん、設問のp、qとは入れ替わっているかもしれません。