from Crypto.Util.number import getPrime, bytes_to_long
import gmpy2
from secret import hint,flag

assert len(hint)==28

p, q = getPrime(1024), getPrime(1024)
N = p * q
# N = 11362908138024680512494651920670930172006642364977453551347508583720046729923059210477255995765930128997884185445222247037671722011346241568484108034602877404922435918667739689190172355712877482552951801474300926126155896877540946087907505382444873519748719644128462787559572243761361558843236106109608860970832167988540726855477768502254218271226114412879112366025071343705902623639652873799895652590762273341109780450925657743057729129740599546845207461155711179625285597411799649428708382006929740203837916726272864447470896036994298096564050369694261322533222501772360352706350572703100757603024124832399837049431
lam = gmpy2.lcm(p-1, q-1)
d1, d2 = getPrime(700), getPrime(700)
e1, e2 = gmpy2.invert(d1, lam), gmpy2.invert(d2, lam)
# e1 = 4839173053065958086898272374606620755704936705456851575329901764771867880477683188021928241410890169960528703930800765045712431175486962206578373325261524125016121573530927390865379213320510482253020285558530905221476341758018608774618282203635751153456820487569652089241272625864705522634119323428029943224228511033950138074565751637805109016188607099521847197744969699146035652373211596621481692930183939200490826817579079887691002269491416910796829004012584738376330920266732832400132014748389577368780485155389738399469732453318975266588059793473370942577771371983311204449234911259718724633957992414751649857569
# e2 = 5412323375311837649012270803430037271340687051837761790260043808312077247004596915812735571194861523692771983765947952188292447999895456469022511399181374348862200558479774885510219329077198018469561120669432187271608778737100226633765932038993029981359843629901549554970592593375187638327331029499379937939789403235573546897316260218925024500190572605418771913311756734669258886581990276910267328336648111325966535428632489121879465019457231737936239437069533286381733865608521985986587438209033273451581990708332188308681757353334416353215953232763602404385464074822661444679521177727701037210506792100664592956373
m = bytes_to_long(flag)
c = pow(m, 65537, N)
# c = 478337024445733444942094701977724012807617374459403550213702729058734180526366918568847333600046339021891701698613635937877841855780240127439786181483447744251570012429793815868229345386139346527506863590813284086503183665531324729088625454448836598200714957295739952587643840065024229712961364872960661328061127447027533255731477198327409403518807801133442923935007520944288299542202243037260478457875251478942039718959848020035458327656572687678304788928651689800469444607672428878806222837958250108192687642280014803376892972872892753191995668154562142754473932302199917910684740749822432449197156176928281460058



#p1, q1 = getPrime(1024), getPrime(1024)
#N1 = p1 * q1
#p0 = p1 ^ (bytes_to_long(hint)<<444)
#assert N1==22752894188316360092540975721906836497991847739424447868959786578153887300450204451741779348632585992639813683087014583667437383610183725778340014971884694702424840759289252997193997614461702362265455177683286566007629947557111478254578643051667900283702126832059297887141543875571396701604215946728406574474496523342528156416445367009267837915658813685925782997542357007012092288854590169727090121416037455857985211971777796742820802720844285182550822546485833511721384166383556717318973404935286135274368441649494487024480611465888320197131493458343887388661805459986546580104914535886977559349182684565216141697843L
#assert p0==165268930359949857026074503377557908247892339573941373503738312676595180929705525120390798235341002232499096629250002305840384250879180463692771724228098578839654230711801010511101603925719055251331144950208399022480638167824839670035053131870941541955431984347563680229468562579668449565647313503239028017367L