1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
| from Crypto.Util.number import inverse, long_to_bytes
q = 1062782236711649143256943253688230795248096679 c = 983161176381023293496701819911713412403621435996600357077248212597051984952060369492776116 R = [10, 20, 56, 116, 250, 604, 1785, 3764, 10420, 26174, 64277, 142686, 339271, 784925, 1774483, 4513554, 12574060, 32149722, 93361078, 202517682, 588442152, 1230453555, 3254020661, 8727469271, 20147071892, 54640104343, 151442207183, 445000053230, 914606176446, 2691450122023, 6025302022648, 15075433850288, 30214089829275, 65227232043565, 139778140650563, 369925682275512, 949714768473427, 2105904592390310, 4914427026380821, 10757449211501496, 23050018815822428, 56999175100749523, 119259915665772416, 293870286338851372, 770246244388062705, 1647923648343663480, 3808869578215042579, 9793878830950371419, 21763428671462086959, 45757034778249840595, 112968528111764693855, 240029343597222349804, 560678930857967344758, 1298162275703915199010, 3823036799197030061860, 8145352084725391184437, 20097317476701585458448, 57857034617384501902995, 167861822547393570172762, 372858814139306344735385, 1087295870157428349383513, 2640148234440084242960844, 6622875296243574520689384, 18570945225061795740099215, 44017906828655608052158550, 97317100505226367855489455, 202155504476126598272882135, 585679554604127986464879340, 1664545898441459275075390046, 3604762580887702181791945097, 9081583430545692984723398552, 26947586381003574921231698326, 61728122735600023624840846162, 155056868560214515089169378260, 397837421070719439621972784221, 1044263092263086773196885199567, 2842164485700169740560864540292, 6158888459112137420571470200973, 13332707741922654309118551782506, 28861201051441325698302866955486, 82032082040065450739476296843608, 217889479575329002869914223263923, 555945102084646653454108307375752, 1548682791834377332871031584311291, 3757860013368899814716211525805218, 7877350828703609247361685132098268, 16552674199222773396227321803632717, 49310968705673838114822412496087919, 119896848947801472882210821743659192, 246840756958386193725893543708486956, 550954993699753149382877043839683648, 1212879093285682674613228786282450230, 2516234147199103678704149631306001942, 5122044009168632148386809983975370904, 14749557498439515099629706789721285673, 32146803210745019766197032394376999848, 83267801178922620546613211942145456468, 220275723095364783936447627339002044695, 493414367960715117911791606612069534963, 1392221083150439458092715171406886216820, 3183942306979020264632411284534770729988, 9244760653244976919670674765917154154433, 19088421242697289011450114796569680495410, 40416628293425853465050792794855131155767, 102116633306198170357170067423508110575976, 227277032457742340336612735110719095672694, 619907260835641293381831580578615001558978, 1512778870037106477781340650274547330127117, 4043168404086154151861279795071865355441883, 10330704486609131315313732978036754163805081, 24529644187712561554033802847438821250621404, 53014176633918398409677359044329945740792107, 123467132049736217121207166203674755383724045, 322851607642471091487630766914774844693522137, 710830373760058207081889256711298798748104158, 1423897802215838505778009877234711247758811844, 3690210274392987745770258964442206250442129893, 9775541687048334546465030877846487194534319303, 24051879376871745352502813841331588227141616666, 59512015711961402263690402829989865262082942201, 168586256483711850114158105226125923731322865485, 339000720658343273716234989743921896249537996525, 815792665280689101372017973380211965687154108739, 1819683947681841711925085824750249487582034645028, 3753817468108207702879116405206977073924527001678, 10140303468902625836203104297663006421652353644791, 27589302363964253128263531817988442778796823545503, 66595246178324235504040809010077291044678101018321, 171169778993933758462354186734144919918938111903087, 448684299677297225260676523985058038365651161887526, 901112792634281977113529440543337701631368200707245, 1880632683706461197915265008125417460621679621489042, 5632823388986948279095935644540059675128326956026545, 13660545163895218636949966532272293026396221070923701, 37023886509875418406806450165875176360850044050625045, 100355433598829041760850479110561847843652622482526713, 283871853948489945344372858536768007918630015880390584, 620279993363251981967903968442622022653950722280940957, 1827182154519631057787495772932009755904080027464326502, 4502141834345370318696832880478693010721568515354038809, 9641587412952464112793315092379538014320918115965729694, 25206363653216482184115175991586414198392785849271926044, 66430427009675817187960040784708373625578269100430229079, 147996824987971424210362707800724888653196426277715815491, 338630792112184884689171982291910991251345007800173341986, 861659819343535690253504207338242088841891705792525397367, 2160574116696290836636610705193868120099363331710642458358, 4694790313099040730607720285766854284869683176151164709112, 10624668885969654258748574456709749409979114479719657272356, 22396164555821525784673028261747345078110653875353255510399] S = 1152869203189708302662513064730278529733889476442489893777042 A = 739143501457751145971738620631 B = 61338711994428897029768502345417660825850307334052861593436
res = S * inverse(A, B) % B plist = []
for i in reversed(R): plist.append(int(res >= i)) res -= i * plist[-1]
p = int(''.join(map(str, reversed(plist))), 2) n = p * q mp = pow(c, (p + 1) // 4, p) mq = pow(c, (q + 1) // 4, q)
for kp in (-1, 1): for kq in (-1, 1): m = (kp * mp * q * inverse(q, p) + kq * mq * p * inverse(p, q)) % n if b'flag{' in long_to_bytes(m): print(long_to_bytes(m))
|