ASIS CTF 2018 Quals: OPEC Solver

solve.py

from roputils import Proc
from scryptos import *
import proofofwork
import string

'''
proc = Proc(host='37.139.22.174', port=12432, display=True)
proc.read_until('Submit a printable string X, such that sha256(X)[-6:] = ')
crib = proc.readline().strip()
x = proofofwork.sha256('?' * (64 - len(crib)) + crib, alphabet=string.ascii_letters)
print '[+] PoW:', x
proc.writeline(x)


def doit(opt, _input=None):
  global proc
  proc.read_until('Send your Options:')
  proc.writeline(opt)
  if _input is not None:
    proc.writeline(_input)
  return proc.read_until('\n\n')

print doit('k')
print doit('c')
print doit('p')
print doit('e')
'''

n = 17736169692098530424325904693867064558539042880481444125570328286674112770740170302153094663238442170154604255677017393301256050032393786770214796227538838730959262950701932624848801316210941550592853906182602856397767153621534450709243306946410334815523590479056269801522380602028524277644381397950111479469778954777017243068008768047045983690040072845424822774879211461017478434873717993041439368323079508906968286789147572446306329450569257063684393360615409078178679430526760253002037281100511438562120188282161997054006128571125488136123838242499278881627382969239530840682330855478118934256432785616156431978178987764257871439478290298090003285583157291495083393146343321929077113020698441792272781536400376238732839159225287925411439496405787000373493010823536896142389905251253438855539953402702200114173428138574065334273416105608605912698704160263612258177166700747764643435080658108403017925704020733209100792252073493993919181803786067768282769794355405096603456600650017436910353744174770165997221954252064452683046476834912705903610539506934703113439600200156699001625462147572053790106635394490213459303609431765992243619251855893734629269839137700326453824555026656919418770790785908781262241916404388017112376345479605803550440028493492626211564100997901983611419332130256285953274857025333524704530549110969773358938996576591087810888208652027771555951167627619429918583411840639683672302976248310368537358675593641758679505864964079306401307778941934042763218074661520847628839907475509603128756218206686607231804969160737927971733653167578489085012332121997805659525925284090017985421302905794708527166142834909133155204639278590735672484170429952041815175658985784625821179404936334286349557106493189682445229043327644234960014817249331724931175078618719473476426287838928917813443351219607255940685288419802476735619521928124309
g = 17134180470013505342338308157600137268749738887430749700373341020503151490907417389961286845616988793689175918617763410847484602792529992044164975012866003388590289715428291685270884744589787197103532015288608956297908469635959525901336544728656213272506992197453136788289248354640323107753484106413330713880134963035131490794795800473015237587843117074986074530320656116689338937585138008570585743952822801750485517053982016778422711479041417985267704901184345922971896913490041155892712233149187753428582859784263598907899529840839842268470604602880750379913616398594459546283450105970979556938365784072963322873973711787676122059239502598470713115787696195936872415360580174798276158980338569027369584284443672168301328461775774617621638349823783756447497327984324268577654354280306957860815640471062947519695437014944053558815794290078637067458961920848464171449000693006675333498180521187094271028035358325443603056671882450941925905724332403070119364991347613284275865656152394564585758427678400647800716392796276928980687115139921259297423912517838701588128796100517692819801269183898774784321659789202470867600589925160036983199436493564981560499756651778808607512551110340531484341333553538793644853201532244098691207126825457817675266736070005658846922654740850532853041704128738118123072715609196610128584343893156442002651228088561165588021185135226854161032245282537967176143794707660411270341485032899003684117357742482590508400973618850408790060189675991767823901032235277429074291873820157815273069641259330146012977295847759611569178657695840573847729426082860048601704423690220416599055551939128191752509380247975078656102468871623628608376825750138091808783297962080110126154687098364064657252264242983010025156362122944303911148558787678515537502819427694495509791914622853712759549904202126730117600960419196022678178165896296508
h = 10026191389155614058220057704183323195262775898268115906492760726853116652561053633334757263656629280751787540051263292052322120144287932126196575035762405652306738858402119926509811700090993499031966120708765977124542373900757621409147437916157040342090736564497841413546601114062057784505558610135548596835236589796475397725657505597260491572917237578379554992068502769647961345623499152454734414736013549387772911732678857605482977089435234315407829302678168527993860282998858867246531397114171943996928937475692147184836602390303150423470586195080893581765457035199222582877124149011760319881618289373965101795195940526026067074684605844894081257349527920224145714988111361299214772645775668301908807115807206186279451353603664709739009824900346437172557484459378991481010875968242427045560930863661633595757337821500059057293148782433470227510287301052300537248233345854421196189236386029291180524360965802137998661311713895873416307640026367561391757963524283594311892455517555330681402370381279670562339678846576421818676878053985340438545033644649827714653754405763444770106078191707901073051816633835546139330941384241040932985244285196452088609976730516599411243892033275259497418031321434202813946231926663569262815563422646229439805873833581969550811543722624657915278633200949251787137706225351118554084527673661919309163631377890134570254767290051313059782520721062681147611492841986943121039571849259264167963953644476858991759844722739368913886511883806466173362048159071297883839711465613770499151525216017395505694915288311846257942251336396443439072143500671937101924025626683727816094895737536955224461273842046101254939454574673736947890648346687713728309893686211721514136227458483810837223386637761523762929587836862133524890100434684382846416306364317503471297169802844800532006649489655192708488818969083285715155699840962102L

enc = 12510691729385597711175410608198670556662216294576484194795381062418887498602632998822082510192110221022394516261773534005531662490559291085242902159408645921966241721203567111334623511179736714861264361483313049643975739918071278984732414193274471033960171693768030530982101672800413187221007416311480688840925670211906072556372457364298364201557556693308195602817591625054299838019188315275721021033976316038993785296383031895681584027178222794308827952632895188018288153824105469507880435935838396836807891323746206069075660643900925614155582891809766448350628757112937802926115782520952089666171227242155315038594025066060855744462890843659556712745641316686550043994425020179076244406626884985285506717702843021690528702024392434949881785005233780488716774678429974656160782253276344886436332933519373195131602996240318299939494361913133630797600303617661489112945706944026597691411135278259879058806302263138283215135422158160523420605765130672170955057886471302038868664074868720515975331193910146606259558475636326560979154841429944489025215300862923656829346826362922381164173201872043123089163984548335540229374402038212770140530512364941788573914051521837721150740609508844777373657429311679277815652042216699286458192072707083136032217223649274116580352324268328223585795789951832150413276073972251023886292670124089272077354176949823518623598115978325061282596983598637839319002151859341959608962592996643808884036541238272335737011267128831949871703514054837755234198126347306707223266129431547189270890054814418460689789982023536938460108546110191155000640574547869314585684083542845048032534843237400436187079688150391390591948548325345149710599370790076617848311551797650820785082314105331772784847862657817678417308673693608804623760990141713053284605126962021594568521992415549885115880679040614356422063145690631529860007013515207

p = nth_root(n, 3)

assert p**3 == n
assert is_prime(p)

print p

L = lambda x: (x-1)/p
print [long_to_bytes((L(pow(enc, p-1, p**2)) * modinv(L(pow(g, p-1, p**2)), p)) % p)]

"""
26078740433699851665380749216735875887095254075774227367695072772381828136949979108600692882199640243971862443227347280719995114033522766117819657819567010759110675742040090417900278724586791829925719930745530739214635206644330970776397272518300064419070248910292782753904753970713819709387202472808476047637475132259102649659614892184556101011954329019006023874143222530301866368157394736915059616139923905408794748079268679407890806129894656461896641965917265998021215458477083067981668266731878720834896716031470750363043633024069778017417632609656943334177817121125424840472019000620519232208942627125531562982669
=> ["ASIS{OPEC_IZ_EP0C_L1k3_Effic1ent_Probabilis7ic_Public-K3y_3ncryption_with_S4me_Prim3s!!!}\x1b\x90\x92\xdb \x9dZM\xdb\xcaF$\xc7\xa6,\xa0\x15\xc2\xa47\x9c\xc6\xd8\x12\xd1\x8f\x05\xc3\x80\x17Abr\x15}\x14\x8a^\x00/\n/\x97\x01\xf8\x93/r\x82j\x0f\x85\xa2\x7f\xc9\xf8\x82\xfe\r9\x1cW7$\x1a\x18\xf9\x00\xce,\xe8\x10\xa5\xfd{\xec\xf1|1\xdfS\x83\x0chk_\xaa\xfaxg\x0c\xe2R\x10\x85\x03\xb0\xd1O\xc1\x96{\xf8\x8f\x01\xb6'\t\xee`\x92H\x1c"]
"""