Crypto系列--RSA(三)
[RSA3]P1
扩展欧几里得
裴蜀定理：对于整数域中的不定方程\(a*x + b*y = m\)，其有解的充要条件为\(gcd(a,b) \ | \ m\)
\(a*x_{1}+b*y_{1}=gcd(a,b)\)
\(b*x_{2}+(a \% b)*y_{2}=gcd(b,(a\%b))\)
我们知道\(a\%b=a-(a/b)*b\)
\(\Rightarrow gcd(a,b) = b*x_{2}+(a-(a/b)*b)*y_{2}\)
\(\Rightarrow gcd(a,b) = a*y_{2}+b*(x_{2}-(a/b)*y_{2})\)
对应相等一下
\(x_{1} = y_{2}\)
\(y_{1}=x_{2}-(a/b)*y_{2}\)
def extgcd(a, b):
if b == 0:
return a, 1, 0
g, x, y = extgcd(b, a%b)
return g, y, x - (a//b)*y\((x+k*b,y+k*a)\)依然是方程的解
for i in range(10):
mh = long_to_bytes(result[1] + i*b)
if b'NSSCTF' in mh:
ml = long_to_bytes(-result[2] + i*a)
print(mh + ml)
break完整代码
from Crypto.Util.number import *
from gmpy2 import *
import itertools
import hashlib
x = 18608629446895353521310408885845687520013234781800558
y = 14258810472138345414555137649316815272478951117940067
def extgcd(a, b):
if b == 0:
return a, 1, 0
g, x, y = extgcd(b, a % b)
return g, y, x - (a // b) * y
a = 18608629446895353521310408885845687520013234781800558
b = 14258810472138345414555137649316815272478951117940067
result = extgcd(a, b)
print(result)
print(a * result[1] + b * result[2])
# mh = long_to_bytes(result[1] + 2 * b)
# ml = long_to_bytes(-result[2] + 2 * a)
# print(long_to_bytes(result[1] + 2 * b))
# print(long_to_bytes(-result[2] + 2 * a))
# print(mh + ml)
for i in range(10):
mh = long_to_bytes(result[1] + i*b)
if b'NSSCTF' in mh:
ml = long_to_bytes(-result[2] + i*a)
print(mh + ml)
break[RSA3]P2
高次Rabin
from Crypto.Util.number import *
from gmpy2 import *
p = 59146104467364373868799971411233588834178779836823785905639649355194168174467
q = 78458230412463183024731868185916348923227701568297699614451375213784918571587
e = 4
c = 1203393285445255679455330581174083350744414151272999693874069337386260499408999133487149585390696161509841251500970131235102423165932460197848215104528310
n = p*q
cs = [c]
def rabin_decrypt(c,p,q):
mp = pow(c, (p + 1) // 4, p)
mq = pow(c, (q + 1) // 4, q)
yp = inverse(p,q)
yq = inverse(q,p)
r = (yp * p * mq + yq * q * mp) % n
r_ = n - r
s = (yp * p * mq - yq * q * mp) % n
s_ = n - s
return r,r_,s,s_
for i in range(2):
ps = []
for c2 in cs:
r,r_,s,s_ = rabin_decrypt(c2,p,q)
if r not in ps:
ps.append(r)
if r_ not in ps:
ps.append(r_)
if s not in ps:
ps.append(s)
if s_ not in ps:
ps.append(s_)
# print(ps)
cs = ps
for i in range(len(cs)):
print(long_to_bytes(cs[i]))[RSA3]P3
连分数利用
from gmpy2 import iroot,invert
from Crypto.Util.number import *
import hashlib
from hashlib import md5,sha256,sha384
from Crypto.Util.number import long_to_bytes,isPrime,inverse,bytes_to_long
from sympy import prevprime,nextprime
def continuedFra(x,y):
cf = []
while y != 0:
cf.append(x // y)
x,y = y,x % y
return cf
# print(continuedFra(45,38))
def exp(x,y):
cf = continuedFra(x,y)
fz = [cf[0],cf[0] * cf[1] + 1]
fm = [1,cf[1]]
for i in range(2,len(cf)):
z = fz[i - 1] * cf[i] + fz[i - 2]
m = fm[i - 1] * cf[i] + fm[i - 2]
fz.append(z)
fm.append(m)
return fz,fm
# print(exp(45,38))
def get_p_q(x,y):
tem1,tem2 = exp(x,y)
for i in range(2, len(p)):
x_ = p[i]
y_ = q[i]
if (x % x_ == 0 & y % y_ == 0 & x != x_ & y != y_):
return x_, y_
n1 = 45965238261145848306223556876775641787109249067253988455950651872774381183888979035386577960806305813634216583223483001245996467366520071511779063266315692543617195166613592991812117446772937889819643718423377609566597230873623011099295202599905646652692946273375405832062164263711151844949794774229886016858313299259387152937467743637367261734624060321171598033647661809876890249035267180368762739600552966699295210431508056693524383116052539072065535970720901196322942269916455391238409489616842687658335666652878840458263998780783865062993401055465701207886230787204008073260653659510197069116237460322442433331870944968133645513020531983926180514313028320422449103156746225574626841023639595418255472716267486241462968101152032898749
e1 = 279586443815379026299414729432860797623
c1 = 11515318475856179010858377918435934663304239594599788732135470038988222237790835017056954077794506499559722814863240838882673078330335616745578747265404229105473136943188301293198548838105990504750972653445744347121859396823995101611868191609259910876207038154174100742978387355304521374228562928260479446249263909934393657537918407756957032700052269827171045167752168509783885071211516601218892308228572735545579606908430615218499620619028799140945676768341492724044499209913045110359935325510223652935426973411960865908064824205626343685369866932545651037748553442488682593143020861196339307665638704485958986411837014559504992818255506454051842453553265179370878637153602580071152915165775491633322055360737581203750897698007951117808
n2 = 25459365600568360055376316722846535809281537088824978187355135247184417413329012865221456308642116409716822227032113740366024809533942721286337697830775221199570509665320400376959076685728357107457862901087218522281771857981155239522807950207375964963527837592797198372303427082343684305143238075402697262610809363109748984974325271762535573995993132076293275456692621516174749076897962348000698039074721998780555541905706268579496243099763776676950336105074846695227221690550755501320117554250942600626927600558489780841103863110357615957088709321079080707735028039675102383525496673233697130053936053431067133520717494376952763684807635780416860233261892013531534059267366382617635000415723745274490604551078385404286689447761642713963
e2 = 249615977162294580923494787210301891647
c2 = 24544357952213952357056140974408354173440635791397720610932999473703241918398814255275362994811954064820912468224131892551724930677715676493892869921426790840199600798807085779112854131346378899855545138289836687048918660685766286852276199524789699567994154833159365800848535248059731927121269157841084905465048764152977389352561685340108834453730139893330210765986258703154334901509553990091592209268471594519326651914685843021165854654380119091009831071244459145750976193183411590207529489774630266528538380011000213950174694472355034075543687572037516433204151217601537869823709241020510051494619335852686100897182065588340025334679570763716458250649152257797833022586793526594784648938165537701256313728194521212887453997160504204832
p,q = exp(n1,n2)
q1,q2 = get_p_q(n1,n2)
p1 = iroot(n1//q1,2)[0]
p2 = iroot(n2//q2,2)[0]
def solve(p,q,e,c,n):
phi = p*(p-1)*(q-1)
d = inverse(e,phi)
m = pow(c,d,n)
flag = long_to_bytes(m)
return m,flag
flag = b''
flag += solve(p1,q1,e1,c1,n1)[1]
flag += solve(p2,q2,e2,c2,n2)[1]
print(flag)[RSA3]P4
连分数
from Crypto.Util.number import *
import gmpy2
a = 79047880584807269054505204752966875903807058486141783766561521134845058071995038638934174701175782152417081883728635655442964823110171015637136681101856684888576194849310180873104729087883030291173114003115983405311162152717385429179852150760696213217464522070759438318396222163013306629318041233934326478247
p = 90596199661954314748094754376367411728681431234103196427120607507149461190520498120433570647077910673128371876546100672985278698226714483847201363857703757534255187784953078548908192496602029047268538065300238964884068500561488409356401505220814317044301436585177722826939067622852763442884505234084274439591
def continuedFra(x, y):
cF = []
while y:
cF += [x // y]
x, y = y, x % y
return cF
def Simplify(ctnf):
numerator = 0
denominator = 1
for x in ctnf[::-1]:
numerator, denominator = denominator, x * denominator + numerator
return (numerator, denominator)
def getit(c):
cf = []
for i in range(1, len(c)):
cf.append(Simplify(c[:i]))
return cf
cf = continuedFra(e, n)
for (r, k) in getit(cf):
if r == 0:
continue
y = abs(a*r - k*p)
flag = long_to_bytes(y)
if b'NSS' in flag:
print(flag)用格来解
\(a = r^{-1}*m \pmod{p}\)
\(\Rightarrow a*r = m + k*p\) \[ \left[ \begin{matrix} r & k \end{matrix} \right] \left[ \begin{matrix} 1 & a \\ 0 & p \end{matrix} \right] = \left[ \begin{matrix} r & m \end{matrix} \right] \]
from Crypto.Util.number import *
from gmpy2 import *
a = 79047880584807269054505204752966875903807058486141783766561521134845058071995038638934174701175782152417081883728635655442964823110171015637136681101856684888576194849310180873104729087883030291173114003115983405311162152717385429179852150760696213217464522070759438318396222163013306629318041233934326478247
p = 90596199661954314748094754376367411728681431234103196427120607507149461190520498120433570647077910673128371876546100672985278698226714483847201363857703757534255187784953078548908192496602029047268538065300238964884068500561488409356401505220814317044301436585177722826939067622852763442884505234084274439591
# a*r = flag + k*p
M = matrix(ZZ,[[1,a],[0,p]])
r,m = M.LLL()[0]
print(r,m)
flag = long_to_bytes(abs(m))
print(flag)[RSA3]P5
python脚本
from sympy.ntheory.modular import crt
# sympy原来有crt
from Crypto.Util.number import *
from gmpy2 import *
from sympy.ntheory.modular import crt
n = [48900330639594979739701067783234903348599405413588466525574910520196852415104874636276388006189258357683981763, 52184798260918956005878710130354843122927544013692595240956998112200987084814453592388074200951779840156511, 57591305346419909943538345276263585821186563609432856462492112562586368230163591993342956384688555395772999, 1391052858660682537388264601016075339528373211889618359237336378385137832855656756800539626220549334300176727, 8401669052993451281764489325068020625937224410830694438332016050030698435746929661939302694116817188225591, 66809775375777747860816961274643428927028556487820183599747024350362932190079439298182707730302976119988715497, 41209230281867957743385705727577318625405890894626062454495908709761427062490881938652489884059847194603237277, 31140089821370202352241944402736292072447365626312703496944186462246895695650729682254970622208848300946861]
c = [26617913696414745819584063604277199673357890677059949687794606743781436349829925794253672010780125661705587071, 6332739614121961923948917957498597962902897015582697635859365080803944882904908423983706426654363433337197, 46154051334276357655176765655327305918368830821288083739892570534253190653909520953027859629573215723954424, 2800905135165447908315158053695706832127646195243072751493365013371469263897970241141686022109978485359114, 3597083928897756955519089479028751799504001377334447013725903377254761160933418420625119547713455139382114, 17032086144873551648611964054579542303630306316746409528107026138674853298939194425805809444921339677455174485, 36111201824253386572496248461433786832561483450731317363761227351689971628309683994429845284904292821369745345, 28548175317543234723297895187238113463350377151401226415566179373530461612253257137535830491771909906093171]
h = crt(n,c)
h = mpz(str(h[0]))
m = iroot(h,7)[0]
print(long_to_bytes(m))sage脚本
from Crypto.Util.number import *
from gmpy2 import *
n = [48900330639594979739701067783234903348599405413588466525574910520196852415104874636276388006189258357683981763, 52184798260918956005878710130354843122927544013692595240956998112200987084814453592388074200951779840156511, 57591305346419909943538345276263585821186563609432856462492112562586368230163591993342956384688555395772999, 1391052858660682537388264601016075339528373211889618359237336378385137832855656756800539626220549334300176727, 8401669052993451281764489325068020625937224410830694438332016050030698435746929661939302694116817188225591, 66809775375777747860816961274643428927028556487820183599747024350362932190079439298182707730302976119988715497, 41209230281867957743385705727577318625405890894626062454495908709761427062490881938652489884059847194603237277, 31140089821370202352241944402736292072447365626312703496944186462246895695650729682254970622208848300946861]
c = [26617913696414745819584063604277199673357890677059949687794606743781436349829925794253672010780125661705587071, 6332739614121961923948917957498597962902897015582697635859365080803944882904908423983706426654363433337197, 46154051334276357655176765655327305918368830821288083739892570534253190653909520953027859629573215723954424, 2800905135165447908315158053695706832127646195243072751493365013371469263897970241141686022109978485359114, 3597083928897756955519089479028751799504001377334447013725903377254761160933418420625119547713455139382114, 17032086144873551648611964054579542303630306316746409528107026138674853298939194425805809444921339677455174485, 36111201824253386572496248461433786832561483450731317363761227351689971628309683994429845284904292821369745345, 28548175317543234723297895187238113463350377151401226415566179373530461612253257137535830491771909906093171]
h = crt(c,n)
m = iroot(h,7)[0]
print(long_to_bytes(m))[RSA3]P6
限定范围的p-1
from Crypto.Util.number import *
from gmpy2 import *
from libnum import *
n = 210488679270475701976181947365152313699517734264122394812492020724654505220623065289117447808270300405893088216711827935540458944042230307295703758023289811232234667671779565383964487868833609515040373751117785890923111021052281871560758159098018301948230396406718130378740957192704249130990473406094468375190967933383609736557
c = 136071043914570532351840574748667342595827512223368889758030473691165475344493240895540489846178990095609930878050872170334417124306746585253763197947342333489768575699470163018093386136808345465103492262428343569799463896437045282842447134475696863670001725029430508792000363373891006638520238615750531296612676072986388618657
primes = [12817836240916621099, 9796955111076276721, 14260192631353157767, 11331104417992923271, 9514036759383573643, 12830010251405547647, 13614319430115788837, 13292666469666083977, 14743386631123002553, 14117202746451676457, 13269748845129713117, 12168813134511397211, 17228879457544885133, 11476468574713278067, 11946685680111967199, 18345865007923209077, 18303664985620995833, 9822277703479114283, 15178066358256569473, 17098068971695098757, 13618686975649185601, 11744366650084293437, 14752193726031278261, 17843527472060726393, 12389668794044063273, 10376034649713785869, 12238540175552034637, 17132154884907233137, 11734611387998570581, 17011805096670339443, 11625121908845289409, 10757305216406425577, 12462221960790002209, 16018515046461158299, 13961897238779389541, 11607654254039926417, 14764422702778633637, 15889835560738915411, 13067226817787067883, 15887483815693916443, 17641812946382237687, 17751437011380057229, 18384735831631526519, 16918144377393116651, 14150464978154164637, 13178350295174895967, 17995769690138536847, 16340079015339247603, 9398681247575712871, 13634353827184119163, 9611544156521225383, 13453176756459641471, 11303353946688525031, 18109038864474076559, 15045485267231590583, 10972199753934977179, 17574722479092926033, 18278068689901766303, 16948848653119121327, 11758909188247026433, 15665449198029497387, 10901691956952449753, 10584519935735226743, 16912467675047183959, 14327261172669596407, 15097367563320670549, 12297273221784672769, 15947284817142437047, 16781387148892629007, 15881303895526705733, 13045061948663850751, 18436681745005029761, 9233724300944854859, 13047527195762392259, 14723757760242013169, 11741005205965231159, 16408614260735211923, 13814776270447837021, 15906163142517891569, 14423435831173412623, 14612928719996598469, 10885120118770555303, 13368686720584342981, 14068267570818591737, 9868356740416745089, 12406920698251977319, 9286022127447238097, 18023608417081960717, 14923516882492986133, 13823678708930659963, 12857551861722029083, 13230742121296437271, 12729591066572154191, 15849174322092304703, 11085431171727680393, 14068906847806320077, 13851658642377888133, 12875459865393464869, 16373459542443249833, 15042636961965421789, 17804579165451279653, 13220312902184268113, 15150287797243551839, 12346428755895098357, 17020549628614536703, 16886745404527188301, 18375430790398618129, 13224710597451808487, 13359444437510262103, 11873826262101064243, 11965351035977107903, 11235458928878258717, 12997583502966109111, 13789872877795337753, 9410284081150637203, 18303250922016774599, 12282563435683491241, 14305213835649582409, 11918623460221018469, 10943597593864147127, 13038337723454095519, 15455421326799165353, 14062369863925079513, 18367836708310870171, 10613492300802961321, 14459256689604923461, 11706673732895890387, 14382736049526145057, 16655509777788355597, 14000284683606298529, 11290821241077537707, 12847958971987427681, 13809253826547615959, 14684126452952111143, 11855586041954042173, 12714825000812576869, 9459493996196289107, 9842932973342874239, 10570590695078468843, 14410685183194015117, 16898517162308994587, 15220517599820119309, 17333608782273432163, 10377521770815190027, 13122631859485901471, 11571227468583314827, 11817889822931972323, 14228001997887128497, 14456085940081475863, 10270130489745680131, 17517555821987735831, 15429383763760026979, 11108995892538667811, 17911418867778656821, 17139731172232986937, 13426013319525942679, 14562642807139379233, 14531693252415486269, 15631238547467725579, 10320658119201020257, 11575894205699157263, 15384475741355621261, 10764073960673003609, 11153595693401172317, 14790585109191523507, 10690672323080867881, 10357625576156190589, 16431064857205643717, 12130023867007235381, 13564898535871926389, 16337575470726771133, 9618083378800557767, 17232134619106506173, 16342365536104729669, 17290061582737251799, 16670033868010116101, 16394458575620757607, 13679014824205066283, 17991831450196114597, 12317978714944305947, 11632115207816943743, 15797700688884441463, 11075555837128820431, 14881723251235989661, 10010880757411909987, 18270144545531928449, 9465870609311716069, 12582412206542381803, 14662660113361450837, 16112922901618122901, 15363650898935547023, 12533640949094063143, 9470733380298789667, 10096457749634891777, 14406227249889370421, 12890530725415748549, 17792709587851953943, 10409603150957944463, 16280446889224274527, 11347835861520223063, 17984512079289457829, 13366696032094869983, 15399033257453518289, 12925451097314982419, 10778713773001593313, 17284945985665888051, 13402816621446294619, 15528594004221819047, 15809192880967976213, 13251703483278993869, 12208007531464953347, 14651975501449610809, 10384298003710994317, 15330372718569145519, 17248847366496290681, 11854891655415812011, 17751134388906831949, 10124732408491652509, 13625466395305938587, 18200378429690571427, 17452972356845950849, 14900945233126132883, 11436315090796776343, 16581798874532357771, 15111242773400135623, 17641315625748809411, 10450595023153090573, 13264757738530097911, 14485829224324514741, 13330871005549345411, 17136650784851341057, 14910153824569971467, 11210011057574992181, 11177037566749571093, 11567028438251098903, 13198253645284080859, 9785835301058295319, 11870911273186997459, 17086899150352287461, 12688798468940186353, 12829816797037704869, 13850020717472465033, 13962611682980549657, 11101821698837041481, 11707465921615682923, 12959209007506476811, 16644144509323715441, 10367003935119200813, 15453978273858403009, 15167350154202134803, 9368800879722378161, 11455175913776290139, 12851750838491254999, 17944785619839501011, 15794784996188333269, 11020878345656646503, 12895215750829198793, 16875096766698669563, 14118851151285954833, 14838789173869952831, 13751766063230858977, 17320191755949110401, 12060022464165785371, 16746856058764394767, 11340262053390390623, 18063813798829005593, 17301743539019024441, 14582876446851166253, 13522319333542791731, 17645483968819162681, 9674664037282811197, 15042492503708901197, 13403260615183814477, 15357650346222449437, 13587415537998132773, 17790598348568475959, 14937073879575692303, 16946217240852764177, 16406234190000264941, 11235987239543284367, 12490317539195443457, 10442876360637230507, 16417744334203076861, 12058149621525280003, 13299492327856068067, 11314451949936901933, 12580137629414492233, 17187303597929461189, 11472019543632605501, 10358023847683468963, 17655020163619780043, 9551405925019296407, 12313496295674301209, 10693093530328277813, 13024645634541678097, 9897976814256674623, 12205181340503455921, 11417228617170103249, 12826004690606531803, 13639934695225511677, 14590472153531475251, 17909159724817643663, 15533310761093773937, 14386571855319704297, 9316892936362161067, 17993944869296641759, 14759692394249822753, 18270460879245227951, 11182120139434421927, 16177012907245614719, 18028663420331019887, 18139576777474000879, 11213134310805448589, 17936183694734803343, 17975442509209584199, 15559262723302226837, 10180836740719706297, 18197598310364802337, 16827523931763080353, 18214986373700605081, 17585494217763004861, 11448026570948864933, 10900056287904330073, 17166645406697902543, 17570484141533117293, 12398389280142315301, 14630567076893376083, 10833999841227994577, 13299004526654333801, 10244054538116403871, 12907824831930739939, 16885467716977238273, 13880284027516293029, 10887546467303319323, 18068389832047177387, 10450635565653187523, 14726030363122148237, 16768133481946424951, 10301298929545489007, 15415018517648901401, 16206238099391413103, 16263750958615351591, 10054000098803084741, 17081860428453965453, 17951459452539869287, 11892815832324644093, 13775418173952588841, 11507176664859257743, 12436316449453831829, 11373445294062449503, 12707349516508026313, 17304366121752246923, 15088976801734008287, 14882686898562658859, 13312883733509401117, 11175338376664870423, 14995241990449050829, 13984129139378165623, 18263293614524334931, 10991047462031450617, 12865816467095731189, 12198009780829783649, 16748296422094146653, 17904593640666707729, 13792268569149446983, 13853849612423089637, 11546534301480400423, 17137023443158040753, 17905444488998063857, 11980813095592929253, 17915972690674748693, 12451065502875272893, 15286203704429102609, 15961659110687401169, 16879684083254701141, 11466389710715075681, 9862223709098321893, 13427540762341339663, 17120171216590076191, 11328200399967258851, 10181508980912484023, 15114850231267812229, 13401368952119603083, 17310327686592116461, 10812290766823212593, 13321530124771363837, 16916384745420105733, 13158876505531892249, 12781125756513915947, 11177172300491135033, 15192519949009579177, 11107570709578280603, 15790871007179692423, 14673525326882261659, 16625393027047576363, 12208173252153948521, 18151011223033756559, 14150927812081733711, 9962724536266278113, 13883267417298402779, 12239907647067385063, 17851351494511502753, 16218780803683512137, 9231060907590526171, 12561800952561489217, 13912140573946770893, 13149132600571773931, 18113853656519618927, 18288722620221293333, 16238398234781792947, 15646176443969341973, 11480617125273259589, 14298265531428974159, 18152443754281945309, 15382191810022993691, 13677302948532689779, 13044467560942628911, 14180490201042674161, 17699382878024999029, 17295445764705446263, 16639917043083590129, 18119370341032732567, 12154128334903051433, 13164685890717792107, 16936772055385035967, 15096483065553525473, 13471209141541779203, 17378837190351254407, 17426974534141344883, 17959141780827119891, 15016498199784708659, 14421160967688875941, 16740532654485547157, 14936157018002326123, 13256118391055166017, 18174072117119534467, 12090575013064577347, 13006876700311968451, 9238945670292014191, 14213473652368499983, 14243331673872027131, 15857539045385929681, 13412686116627591491, 11592325887070165747, 15608925272834295691, 14666236964631839891, 13540685243058340663, 18270373973909961613, 13828282470103450277, 17892440011286210501, 16870901545940692091, 12413729884613628023, 9266844013399220221, 9745512147631925389, 16387537652784438451, 16570045942363855537, 10568791466436873997, 10182396317953610903, 12853823905502858353, 11851841417409724277, 14115519128426356727, 12881420948009143253, 13130088098325861749, 11721786782351310083, 11236214958267547553, 16702899637167067903, 13501762358014708543, 17462031538915936859, 17276389012007923211, 10644899384346664337, 14027005255127061913, 13530526660154644807, 9844415966928882743, 11249128120835910791, 16777866679514313817, 14453045993106743699, 10996863066540575321, 12283642992171368333, 11404591589887867667, 13677761664265732687, 13110578735652791741, 16010046184639114171, 12753941270332721647, 15772567772565704131, 11831712320633880293, 13319727865432694257, 10771551848090338763, 13480980853991727469, 14248794265347244051, 10664170815864253153, 18371374206685581661, 16482126216840379091, 15311554751751063719, 11347740685464268973, 11911625562195859271, 15948182894664837227, 15833902828630883027, 10628744258695587949, 12242229966886189549, 15729900088141513717, 10331962319086103687, 17739760722083508421, 12122206963635673601, 13444533154829926777, 16919840780438603417, 14181132415499287453, 15832764916978218089, 11107329810687234827, 12537867916219452571, 15179335658283523219, 18157750076527384319, 11335208638879830449, 12778309804903027751, 12331094589527085751, 16517169709337458391, 16074354330760224817, 11121010187417970569, 17541225150843770231, 13072072021644732583, 10683918634042372291, 17818396544323153021, 18097213311786551693, 17377696366492674853, 17840289332463757343, 12300868091354913911, 12110148694323274373, 18183424490112093451, 14470426956322731539, 11537900791630973609, 12288308024287816769, 9416608386548247127, 16142185824626408983, 15319391474385481709, 17427093242388654611, 15757681760350596491, 9375203980011408289, 15281050099968592837, 13962807632993334377, 15641960043003280541, 15857385507932475607, 11328494963300401669, 18165773294104417547, 14012380629632910359, 15541214952410221769, 17008189780920470053, 14632891822044772337, 12404052309147249313, 17208994155033269833, 10635749760511488169, 12320122505182031957, 14796692998214399561, 9673910288177915309, 10047903793961297059, 11326483999844129969, 14635083490823091097, 18071773072169124043, 11341815024873111347, 9438792655485507689, 10008152749575925909, 17567654747849893279, 17061517364811209911, 17221503802511195443, 16695681584397997897, 13081948422266488091, 14625725701559358637, 17169462066133068869, 15709579351595465593, 12209792348258846639, 12122275607677157911, 13807547725741290973, 15583160659433004293, 13396260775506371641, 18217020689915921843, 15619329053256302987, 14146270775635402231, 16863952377303204673, 14548776148506068719, 14529188722082059457, 17265380804141201681, 9776286763289778197, 12466859136109077443, 9772744223809808053, 14470786313269634927, 14607320696711471221, 12455737005988354019, 16637246382861080953, 15133708215096275683, 14847081677445301901, 10332654304000904033, 11159603116014973271, 15931004335130864743, 11477160443275710217, 9535586193995849951, 11293175983668556793, 9923153586904495507, 11933006027142853931, 11128574253134634017, 11076766797263201329, 13515870030341559941, 14622814541338434853, 17463892929742334407, 12615007904997547229, 18206100766716434933, 11455838674150852697, 17479338037013854559, 13360281258747049621, 10995035322560010517, 10928474912163737647, 17726175981976035227, 11704404121506907637, 17619146892908914121, 17704564527305769329, 11812175367635269621, 13416429352943032249, 12131563217847962351, 12183503097530938127, 13981143659247294641, 10634933508011331559, 11562423714401189239, 17688490613654951281, 16861173019672178969, 11053050244878979411, 14086304443079658787, 10578453109792325141, 11682151227114266497, 17000674853229930419, 12598355342131798913, 18392805884632295521, 18431468816652818879, 10874622447515914201, 9872938674493987793, 9744625343948785841, 11255274706725187783, 13530191079590038457, 16173365083190310629, 13224430590784162699, 15969778943599937653, 14043089726984416741, 13781348214896464493, 17182476995296609963, 12896436977884956841, 15077836731319621141, 10080593144973733229, 15891293339878516513, 16043377959654964921, 12784208144845810363, 11543219604826483837, 12024729597387644591, 9777324062326177771, 11527333015686779569, 11474993589954273647, 10182859812157362677, 11376680767502967977, 13996225568082222469, 15977867067599549579, 13655821277773358029, 13297113872058771941, 9897159622397740493, 10013043069023436713, 11531819115816693283, 13710715432898401733, 15195815565078492053, 15452255999389129147, 13604937934214924243, 10904911638935266651, 17580607694180244349, 10376618524272533669, 9571446041130564469, 9825683462733434701, 14468571684404171527, 12770922639680720219, 18167455477803076531, 11465084556247891097, 12746847720200807209, 12775769479808373047, 16393448046945064087, 11652620391412172563, 11478574931730042203, 12270257063042073917, 18023307951026693759, 13974408232745028701, 17780249113700985763, 11355073357007701631, 14471311142350516427, 17473300039363624031, 9777054399339418903, 17919523597873134539, 18378677639427969179, 16777121138942295433, 10168805248401432883, 12641872323183817099, 10116977178009093853, 12176766460209633133, 10318924588276162217, 15546400482337419701, 11832021544471242827, 11215298551637042363, 13865628369013960619, 11129154280835514367, 16222330145886628943, 10818887859000996101, 12468152598968308903, 13676585842283059039, 12921766523283173867, 12089564821140624607, 10225474175631159121, 15819547992851766347, 10182914408006996497, 17167878424092859061, 11514181842204916613, 18287116051767400657, 13272824243652359389, 16648019410746154129, 11920726101309487981, 12649244363524402771, 10550622175590275827, 16618529989972308329, 17515407948374854423, 14391969260138111129, 14759186383646463271, 10919403521211062401, 12185965786265832247, 12116710629039649439, 18433362234939139601, 15965694148547533529, 12974211820712657803, 13353321620267206573, 17096739903159443939, 16696518371292656759, 14462358883896548437, 11367744283307543293, 15323226004742755391, 11746436008806326197, 10920871861266559943, 11587724236478293867, 14992265004480347113, 15708312669494860931, 17916196036842304759, 12922134467647572521, 10454128140476511371, 16430520042575406421, 17076469495651100089, 17772189207011073799, 13384875880146838373, 13935012923273198147, 15240883815131987791, 9420660305133379817, 18240375964640868173, 14678307842794601773, 15288259585116606757, 16610633684634874867, 16486217839536541813, 11661546558365415463, 12152118203599876189, 11800253185351909913, 14374602260090605153, 10449913208502792287, 10009143259393434427, 13307738699651704159, 10654277669677635361, 15407444571115834129, 16834689677973985291, 15066169839778509209, 15475733561257809121, 16380412207874211983, 17194107447716508143, 12192621570297038107, 12240237512637106837, 10441056377505748681, 17495542058396571671, 18293106931869404749, 13865897548876531381, 14113466667785343973, 17525437199295255289, 17422068598489386241, 17287527045122701379, 9455908640325923213, 17335751448105539767, 13590715372748461303, 13209806666168836589, 10261162812051097369, 17733334183472849531, 13246213547584426837, 17766000084271444483, 14150582008333438807, 16133690731517495399, 14641711413776366441, 13022351466394992461, 9226681052162486651, 12760195383928077577, 17567872876849046111, 12340487597227543063, 15563748447258497573, 15318459465935920571, 14255243227091610833, 17062529558035843303, 16176535147083208321, 15827087675880312413, 17271698018463248329, 14142147620294354209, 13914535203046847609, 11613211706825082407, 12959862789560256293, 14016596084494475893, 11293492671321492157, 18421116955007051749, 16404448288688945063, 10841598730147032461, 10668072389421742417, 11551364596378565711, 13850029337813227861, 11516141636470693969, 15920496765925322419, 14276274249919823203, 9237568470631580119, 18381932334031688533, 17659877642674983931, 11159795358572892799, 18206258071410742637, 12280903436314972243, 16038761168382463333, 12461628152852020297, 12599866901700933119, 9503462554473103217, 11481782370632833811, 15766095164814323669, 13079723298271643593, 9272657104293910643, 14060047426801456841, 13335454529166743357, 15841992693734542661, 17764709418538501487, 12160915899913859321, 14713689640122062573, 13337663648949716537, 18211158405283472779, 15158622942577374571, 11407833997760128867, 10508929620338632321, 15961989193725497063, 10501876330362297371, 12364784867218660099, 10131314553714497933, 14441100812606959489, 14721325750202554117, 13167419766289684193, 11981676591145933817, 17913851093510662607, 11835488665953985127, 16780953686692778041, 15608609099671724267, 15664551105384515119, 12802145189741653877, 16805549931391100567, 18445301756468541301, 17655249735232734959, 9689891077025566237, 14840484494159775929, 10723334034602592439, 18386904850027413517, 12096629257610342447, 13067964115598968019, 12252109817674770679, 17369822671514623363, 13509155615162956807, 16855863641920860103, 14465746296157191683, 13544016597391911559, 12971969005041850273, 12280334067500075587, 15752570905864769503, 12113525236215732611, 11664013792437359831, 10228837640437031773, 12109791131521690777, 13624111940052646099, 12777090183758952047, 12426963274674728939, 11441470375408996129, 9257227171899364921, 10191312647768104939, 11865326812561002887, 13522604753854591261, 10249599313373359463, 16159615612202096369, 9836233098999799211, 14799557554105507697, 14042255386918619699, 16477871730966758129, 16642525196644416059, 12423008258752432981, 17273875260714952171, 9470913631654644977, 11887078253521363603, 16706376900014360707, 10304459396140054031, 17693305758580051121, 17214391436952288473, 13618743595320511073, 13169249530153192079, 12035858011919909029, 12860667847247804537, 13990854606273162281, 17035861733161781977, 14770109568091276793, 17949815755824751961, 12390337922014329203, 9595001010493198999, 14690160353746242721, 16314094344794415149, 15483233288782887491, 13061397420799425431, 12076045453514601679, 15407273036788472813, 11365402888927879361, 16668884373589636511, 13828335850402659011, 13284203923815359527, 17300809842931614721, 16947803187487136093, 18225750745362866369, 9284672876803885567, 14597852340551274989, 16473939500074387811, 14300584548546758897, 10466932272724101787, 14229473210374543483, 13248150377350757731, 9598039034657163599, 12586816162498814623, 11159150798363316113, 16077108181795072301, 11161401146827356863, 17852976451365316379, 16386970647736403383, 16568117397633516523, 17674878979814499799, 14520861146176965691, 10340053725357332591, 9799386102480704957, 16097477422918098601, 13239453234793950397, 17567007567243212159, 14136045876498729691, 11732340248501116493, 10470310463829179399, 12703325772051719383, 13035241397098055021, 17395156339749341267, 9668529469335994589, 14249010465960845651, 16914660786225731381, 12310520468883701851, 16246592021694289649, 13480017886196771549, 14219082481229344661, 11647439617192501739, 12765954006551032897, 10460413869136300141, 13716846676298104453, 14503448822338349359, 11041742165867028397, 11701704236558588467, 17606212925100148273, 12342707180459270959, 15360511526093354189, 11298030030747659447, 12872763047261841389, 18232938457364630449, 14660255297113325941, 11890851251611038169, 16792857595881777097, 11852378876588707279, 15357599751372293533, 17780342512970330669, 14195457757956580333, 10658400270468681989, 15387143294376736159, 10267219662942666551, 11046696135185833781, 13885088134451378279, 10645311967978806011, 17659494527222079353, 12862971250844658743, 15093229194999614917, 16241065349609244691, 17076182031924555031, 10410526641699080551, 14619036188529238943, 16435691426252481919, 17757270819329871647, 9244265187799778663, 18317093359569022523, 11159244222937462369, 12404088147132662621, 12503445554528532469, 11834507189075821319, 16399491741674305727, 17314200642630424609, 12461073769029981829]
e = 65537
def pollard(N):
a = 2
n = 2
for p in primes:
a = powmod(a, p, N)
p = gcd(a-1, N)
if p != 1 and p != N:
return p
p = pollard(n)
q = n // p
phi = (p-1)*(q-1)
d = invert(e,phi)
m = pow(c,d,n)
flag = n2s(int(m))
print(flag)[RSA3]P7
限定范围的p+1
from Crypto.Util.number import *
from gmpy2 import *
from libnum import *
from itertools import count
n = 345799778173748173773868120733939877012606206055022173086869626920649670201345540822551954372166638650313660302429331346299033954403991966160361903811355684857744142271007451931591141051285664283723609717718163872529480367508508005122335725499745970420634995317589843507796161899995004285340611933981932785753209168028330041659
c = 246232608531423461212845855125527519175008303736088113629990791124779986502745272419907699490375796645611551466345965328844415806242069890639077695943105766009969737068824735226917926112338655266209848386322013506145057902662138167248624945138207215690482597144303445656882230801297916736896978224496017358461492736283036138486
primes = [11400500846732211437, 15663612686729436797, 16146509422571674241, 10365633794353033223, 17764432204956231427, 10770086682509726701, 9363619846718624519, 9499148531156874869, 11870308229801920153, 9493684235948177053, 13439889213792762493, 13543824553169466691, 16784144744729574109, 10473345639906795589, 11686628555687269949, 13438006849184657287, 10304115634530565157, 14523860318465391989, 9647953497087513131, 14024608681547907539, 14323731752105690329, 9995822499706628503, 17263798266448817081, 17412342258647700379, 17552446328775319979, 18182174233675599269, 10926506070008989781, 11287875928373292151, 13031874421918467239, 12826862978863344077, 14427019901941927789, 10764280028896236377, 15204422422736985733, 18013581759315499403, 16196860580398627489, 12409133067619366927, 16982209362087366071, 13552847891288053379, 13321664796445708301, 13503601532891509847, 15213413154033638143, 15789125900714604107, 9661259098414185323, 10097901158936073103, 12492567105127893229, 9803017918077701719, 14959766528145744073, 16380271870181847503, 12379170631770822511, 11203599319503847699, 11697577879391178041, 14830577847345979507, 15161718518020147133, 9449134020600011261, 13590570970475252977, 14435422638900288329, 12478310842333840183, 17177994464705553637, 15072278791274696881, 15805713015714544379, 18298117834725348649, 16592677662893953627, 10360712314766543039, 12350365014973219109, 10487476039094034247, 9303193137466554371, 14317509909121736027, 10069727352579607261, 15672913494263557921, 12645137927662029131, 12577294286343986777, 17990217715164074353, 11770491954898217693, 16352325276206313631, 14742366552931089511, 17904845678435279687, 14896783599885913301, 11640348097370069257, 10229197144755015913, 16348769379755789849, 14815902973349076617, 15808546541834061079, 16180999769759067937, 11333835834203173919, 14349619526753022311, 10887563403726040387, 14696465704976418401, 16612699690876026649, 9242002307438002549, 13294711665781655819, 17316060056875475509, 16264270500305765159, 10143806453587312567, 10156382001678762061, 13424697447914832193, 9533479368240114361, 17607602236552058431, 9513935785246155433, 9348999429693542821, 10687833447600343907, 13029642955293734383, 12352583868905249059, 10578933735997257233, 14807418828818185841, 12723999174902787061, 11812631981548150111, 9469570721445804379, 10407923494920638191, 10559989029436270817, 12477140185116458017, 16418595676222668931, 18284009827664751383, 16879482079149887887, 10274017234103862649, 11495861205598434163, 13574496359130781637, 16347895315217629291, 11184342831473200427, 15117572072516544349, 11962165465299205687, 12593274795450046759, 10576401623272055507, 14871424922307314839, 9683965597938835439, 15649192958998385653, 14136512522186754793, 16189574870468706193, 10432462783789785083, 9882402816632001041, 17467673636368162091, 17812738031541243181, 16444195776814377667, 14458128171493667993, 10068762164183818769, 16785805107381133639, 14471872315245024047, 15256999419456872801, 11245045254273493879, 12432915941937754661, 16779879208564650527, 13527359679120520799, 13609212316987142881, 12048851866296673223, 9700737321821517313, 14378798305839284857, 9611124475271266561, 13852359141963480583, 11482735530462856063, 15354806409837420893, 13941285484258063727, 14725649345415301957, 14540375648816209781, 15268062151789994279, 10710080489577786817, 15918894791610440369, 13679067272608182587, 12130148919788574667, 14787273033558048851, 16823039346693535453, 9786912554506032653, 12271391359749298573, 10338204530215094879, 17031700055987188007, 13892013056459801951, 16466462551586874361, 15509765092722859157, 17798707991935554641, 16724399949431954029, 13950635476447170409, 11844033699047785357, 14747361128582919509, 14667470964266641091, 12896901039793154849, 15536822808734549341, 12385771205898361763, 12265293491880919333, 9519013453753799311, 10399041997001597659, 16593843155091891947, 12731251001624534627, 15446540709384042589, 9977945635496326949, 16022582598611495171, 11602170089144567501, 14556919126878807737, 13325795480553101047, 12141291839761394549, 11056079849427396533, 9319147679594339663, 14076618445093460089, 13279302183770932003, 15969822774426507863, 15634577535247166641, 18134435225679362561, 13580840906683365127, 16932745671449749507, 13861858882551833521, 17059312054729866107, 16159631686544375273, 13252534105662820201, 12853863943245116791, 15045628398991754593, 16867564338626531897, 15053346821310993907, 15424243202794355417, 12169322810803770263, 17562408967112815189, 14696130091108860479, 16353873170264652727, 18137634119608386217, 13853870828606368123, 12138232181730621971, 17695562390286922187, 11482149834977336341, 11263040235574897391, 17516386258426598267, 11729599409349513977, 16344325675031393033, 9487998624331072613, 15548753174223167923, 16246946533494280441, 15168068556360396767, 10988949668785042289, 16578604258551502499, 14921063374278681199, 17959209918307585553, 13403422202954306417, 11008060381939288823, 11996269609545097451, 14304683665387573597, 15127244416475972951, 14638939931196152921, 13736677778855498231, 17587444419861411713, 9712574859471189721, 11754669647509862399, 13808458314511168667, 14076346964677125061, 14296229481633724123, 10546969810734077257, 13806516637777666997, 11595089909651297627, 15383693545718169527, 11899557291952040539, 11892231220794860827, 18090056242513773299, 16535424213022634657, 13429292459383177121, 10938466758053648591, 13247568010483593953, 14353179575611187827, 17247884385077903059, 15492418843846011163, 13991533281715009171, 10648224887308767149, 13434464420280213799, 18308741750842750223, 16958163859863247583, 17331583790580132911, 16594103882668531169, 15654309992707438321, 12143487125851071209, 13917462550122657373, 14300594316387726833, 11038403267265055433, 11668215065573927149, 16522831969819412009, 15574426807839180587, 9521082951973994111, 11184051603632666453, 17420808937992910057, 12911596655426162347, 14013571659883359853, 9255799220881949201, 10863148313680771943, 15125487406888857311, 10787391261037964801, 11181016652346500041, 12375758200228628333, 11096658214489080743, 14127930959020578487, 11097748121705255807, 9576959296273172197, 10329268625923900369, 12989481583199396267, 11221816342693962053, 11682824873199396701, 9726906501816888893, 14262866113962178411, 9585657969091757713, 11560990155825686603, 15431631822377633897, 9693653500895246153, 18052885089925870411, 12230353179628084643, 11140231161527021251, 11692996241065359677, 17325167313903580247, 13625405742824607707, 9700735722329114107, 17772484003012329121, 14710477009444476553, 11461459386714361369, 9710381370263165737, 14182228639237393261, 15344135038819224257, 13747712780102897047, 18043450369219899473, 10108489789901066423, 18323581078801222739, 11709502836760188211, 14510120896876508611, 10099898624211195287, 17361096065683222901, 15111530145788039651, 16726669802715322249, 15303048960860878433, 12918404780084443421, 10395837535719074069, 14881964221907324279, 14275096296552385127, 16767210669789926149, 16926825798156482309, 12118163891694788129, 9527147805191785667, 15014015486557066933, 16813575270918372811, 9593601949025443639, 13896995817956105537, 13741986219854107753, 11144899659720022073, 18238128043240764319, 12779733553193717153, 12771981722317523603, 17736020578173685219, 9340904375029821481, 17592111347118520843, 13580882292330428401, 15018369925699389031, 17809424700118883129, 11613026101864549847, 17286309683170750757, 15302812145728958509, 15391566078527070121, 9974325230682765697, 11551570786966900967, 11351003337990798203, 11120412046865048101, 9696688946725965169, 15093528920040797497, 18065996667394084837, 13292251568744035337, 11101213198305556951, 17531999985277474517, 15966406176658019221, 10691542704039725009, 14297474600370306949, 13621179047848909531, 12859649057819536667, 15917449527351930353, 9605987875906658413, 14998884139877113397, 9303906426219476507, 9871680222005313013, 18053630596736423699, 18214702298732770603, 15217549802969404841, 17230806139959259801, 9756053496476979851, 13493983446716093807, 15872062367640353111, 10830618212258286257, 13343744885931835489, 15379338915986533049, 16664848187297516537, 15913611403024361401, 16957002785994856157, 16999268043777708043, 15924602242524984389, 11470115363514206713, 17780900375430786271, 17219602318975762861, 15562078753739245099, 14429908225005981979, 16785776318383823977, 9345347283569848891, 9826037803806928201, 14757441108506302691, 16843056852903557147, 12089182103754698633, 13071844903007200927, 13309532659259919281, 12185211383730425707, 17671246663671372547, 15827919662605196687, 13921392459246207437, 14214028972975886279, 10666188887784923113, 15026095328389680481, 14070638370052382317, 11515225275289974647, 12733768797899627857, 15232090050353579959, 9605577513419872349, 11774332933083185117, 13015628182391854561, 12452018187207611071, 10613040759167447969, 16395318189590579111, 9650312608310268509, 16507662966772496023, 9745403684063805119, 15429094458205621159, 13907939611582114601, 14350669162433050921, 12444630576676286983, 12382608458977480781, 13701560178384085519, 14561536331132891843, 17870839403342285053, 17726305914129360941, 18120422155613702203, 11458486193501014487, 15652084560104054171, 16016407186905293131, 12896826502049676533, 13137573987547216019, 11993148289033574989, 12553485329707332011, 9407004537495583253, 16551197209131499807, 12188240888329030727, 13138059982433827393, 9447792088431441973, 13898552597307352607, 13086125839706222777, 11253297961067347699, 12473509293771699973, 12025629766486534463, 9246425606391056513, 10978614475595947261, 15328005120420669143, 15005188618611818149, 14681521764654667837, 18222824871931463471, 13727103721842925123, 11056314452399736701, 14190514709890056683, 16071925700301971681, 14114206274338698617, 11354892818254049171, 15558048570303377969, 9548803747853081857, 17588526935062502339, 10932175915126889777, 14848760934877079473, 16531929394433046437, 11059255418387621143, 15419998777650574619, 18133329784854851773, 9376742948363866007, 10267333769360440369, 10455930081787849081, 11749403554374261673, 12289480767522531263, 9355881077811916589, 16377906719131687771, 12636537540548202157, 15473661167864858659, 12939130785963130559, 10331428178834892869, 18403302396935375239, 12457052115957020359, 16728650241949106683, 15673023018343436269, 14566008317650142029, 10428852531127223779, 12989287388538384809, 10023218474904646751, 10216986934332559607, 11200524499033897849, 17374818422359302449, 11795887296034843123, 16260134950019402467, 15545049906898796849, 13905976122896835137, 18192952532376915133, 15245754103999312679, 14336092681672892797, 16711051263995536291, 10268633000776041389, 16298601116274769289, 12526591346109970043, 11057407454514514777, 17316528792225617197, 18057651102128098207, 16192203874370581303, 10293184135563422201, 9723556212482431513, 18054422790317350181, 17756547295472446751, 11552860515549111289, 13432033735566726419, 12179716429669289003, 14947157147090126191, 16335353494729459423, 15184076846117432761, 14777743253109667273, 13625241580579004263, 10998645430939015469, 13534322946405781903, 11327079738013968217, 17487263803711590509, 13189162879894145159, 13784538619743485863, 17064328079090046263, 9685004881707057761, 16079690295682955971, 13294545125605834661, 10648658009947462261, 18415164681671251511, 10641837226629144139, 15777331516260137267, 11795948058583766659, 15535152465440663291, 17216667014436648943, 9653047732094860031, 11131348011090342127, 16886193462362116063, 15612491590607382593, 10835879650784394071, 13279435351244340899, 16168298479453780489, 16083456466830550283, 11380553957000451991, 15128521211355953573, 10826365584345090827, 11931387899927297363, 16091037230044064021, 16855367086926162211, 11170558557176459503, 9886757544769944653, 11450033604282275011, 11929757603936817763, 17420827560223252171, 10870631368466407877, 13834307981276745037, 10230994628690765197, 14461440966371289941, 14513569082524554649, 15609519179461790747, 12452462947852628413, 11697783772313307211, 10077360532646539567, 15668479810095426521, 14100390060574107281, 16039433251746746399, 11594255700072389497, 11335433960775286819, 17135850578547822607, 17715472259313599723, 9872560666658691277, 13426738927194861001, 9559405911145488401, 9560643982657333219, 11125735716442543571, 14348305982295065537, 17334821829789014189, 12062975303975394341, 17675818288232614691, 12456667873905594329, 11330845594517002613, 16817880606791218753, 9524369250258419267, 14531988631115581537, 9721408134124289899, 16662586589444720647, 11325110890618816411, 10051647873079811617, 14536021166978233733, 12224386731517653097, 17640459671249984461, 16543114235733129481, 12834813684653021713, 13050693286566514921, 16072783334843947421, 16824355675011368569, 9665639317029622411, 15966237013384955239, 14787243991682533471, 14167620861073328777, 16552060845197660033, 14426640096605498107, 11250797705828570411, 12830939822208389821, 15292466542716343963, 9917855814946199189, 10442126201651355433, 12042544592582006819, 13742543708854176911, 12519797425611830609, 12305049189690830747, 13048815356624492777, 17928797470734483373, 9345743880343852493, 17394449011144997203, 14027454725211775843, 15325951436202259889, 14089580406354666877, 14985891805973997229, 15815861666300600207, 13010491061439139729, 17474295865525658119, 10856321689902733963, 15719997391332198931, 11798694284977436299, 11131916950543733651, 14728548632909038181, 15869387205433439081, 10635187834937273627, 14844816583829681107, 10707745831589845607, 16061495585562724741, 13860352348388954479, 13839169685364641087, 10246021025120950757, 17909700734377694141, 11494364438621610881, 16304619707693032889, 13720492814063169997, 12550911015312791057, 18076672670188884121, 10384906691343925679, 16486782778290044783, 12644175422114478653, 14955139942049789357, 16026396184113858703, 10524600442649861959, 11001050498566874027, 9979271448704886613, 13030132484834300659, 15230981971792316689, 15374177218176283253, 14195651389624938953, 10455638721836517437, 15149204128873840301, 12500463654517686493, 13475842347378678719, 12974353406746765043, 18081547614319419917, 13613920396906170893, 18201655698843944801, 9908359973067294049, 12259133230997142013, 13435886340259808407, 17657174880994459697, 13940231287221357463, 16592426911225206653, 13749631155096260533, 13579552974478309459, 9836712372149870281, 17218778541380165767, 10464000360382809991, 16777832929341727297, 15972158110380610507, 15350561171111592953, 9938731346590575421, 17912262447858075839, 16137701207062825711, 15626368583424185491, 10499152290055372079, 9382357912889286797, 14085852927258985099, 18393486728568017383, 10652476457160311261, 10527374223100330091, 17264120882113825487, 10885171609551829193, 16296935971967210533, 17039844827041640479, 16608078020248577041, 9554142078243712343, 12151602751600242503, 18333639542063204713, 12302756704018880831, 11612577899799494441, 13180093129135727227, 15533144054803240961, 17221156035305318801, 11685681018084321637, 13339338584418108371, 16764312293446072699, 9609715328254190099, 12015164966002919969, 17640110779197465353, 16460183428670473871, 13819867905621355469, 11784001662482246243, 10882776393768075541, 12284523803945957717, 11453117866254103187, 10672997245980076939, 9837424460088812963, 9456987736164381311, 16476068953424599633, 10714497365388454843, 11566321267685570027, 12258500729803839241, 13565509018611395453, 9837508107087665041, 10883021385911688053, 13236085185545218621, 12903549664178814119, 9277313810593502131, 15325552562767494059, 15737855390072711723, 12902145372862611967, 16617731535068412919, 16192918114406845313, 13329973263696065593, 15118904191983404627, 9421694107495493981, 14757389355512560711, 11755446033555771161, 11174113824848691089, 9931655160887834537, 13952179663695071047, 14628647895265937389, 13965103496050821571, 12334188065189399611, 15026324919476931311, 13737352569679199609, 17292288948395152463, 9747700181588759561, 13039199615231288567, 15048237407823618463, 11672237438639568239, 10302962861342428331, 12445128229021135679, 14463159840208815601, 13915082057723091419, 17505306824019415949, 12290525908208358407, 18446406381021364073, 11883272894488841837, 13151315617170041119, 9986202098577177283, 11376286496724079633, 17072429507581144597, 11601908054173197833, 12769100713651410277, 11578625980850143169, 15395413375327895911, 13942489248348359849, 16149741548915905429, 13745316489572365673, 9342391586010481007, 13460580618329867983, 15049385889346014431, 13567657641395719637, 9610206585474156637, 18361259735535581597, 16345044279841976141, 10386175636785013831, 10339319734960152623, 17118190675556320687, 10005962451642889201, 14773420480883046503, 11178361855707216889, 17257848339780864089, 17226047946161423507, 16460175468823544401, 15971530319487090739, 14842029296369602163, 15224121827462937979, 9275527308938870173, 17041103378156856689, 13801145680164940003, 10285279638830544209, 13671894824963549641, 16032778609020511861, 9851225257145555347, 9375022299108554971, 14826523109553586027, 17124217400159528447, 10713407734688191177, 12691625640419643317, 15981484460492567717, 9786795565103681819, 12556711015687803709, 11148645018758728049, 13265323147276427401, 13967986650812662373, 17848752154332550457, 9981768723976662007, 14998022968536079123, 12174071201870356879, 11520148746512983013, 12705359135922834167, 16031947192061029513, 12785255613650486969, 17794207197348321059, 16590130444003836701, 13051020119617841899, 18329540394916509391, 17016883109643488021, 12739110953512934191, 17294655201856917067, 11058626020237830707, 9462906708710154961, 14623360900124309369, 11254845081678452897, 14264002816761276253, 13102001758655038643, 12108869081174715287, 17010826574740201271, 14037017483914942313, 13985137272262919353, 9633084395035385983, 17241078172401921151, 16214027901908512283, 16093436048900321317, 14391957124445034917, 12359483645035302161, 10438778853819832753, 10567110128884566343, 10292970247351191901, 16822209722672159149, 13496565983843091859, 11841500670757876693, 11147505811854389987, 14065276166663767481, 15145625093242694749, 14413829172406893583, 16503017312704021103, 11981873548328345323, 11909212497608981689, 10679989447819664377, 12423178332387828413, 14358836553490758151, 10237468755767323591, 9735039457556049641, 9478522344708755909, 17979691433619404903, 17873209010991434147, 9550618472816953163, 13347619619192035741, 14530641313417809089, 13994703746676143779, 9559733892621448897, 10382805841803379711, 11843672223274874071, 16815833185277434981, 12381223102021820597, 15258305081721389239, 15136515056658706363, 18126727588656279323, 10697455619860328677, 9352124924523425581, 17295005245325754503, 14177782902523557389, 16249970306053067029, 17425431521899489447, 9366637040493563183, 14547545849198299667, 16839246487745686313, 10125673509176340733, 16315331794598305291, 18287303257171869707, 14082462954685803851, 15710924897106988277, 9846789987736297901, 12850810892277384811, 9503762183847119159, 12035363414252005649, 12548445170155094227, 9987078241115445023, 11170994807091443339, 11647765960869059809, 10834387862974757999, 9838865006047239157, 12019744644188767517, 14761339868466177863, 10956244424237933677, 10577167950528154373, 18401121224902652879, 17235712984492843111, 18429975080980393459, 16975328717308835227, 16212745888436855227, 15748060839664004279, 10802710007407091591, 18005654473259312323, 17728864727324757541, 9476823236759120071, 15715719744380211089, 11317957584932242129, 14263043570269209481, 11885161440852975761, 12759119296561192847, 16837757861450897923, 11387051211693970223, 12990690679215047009, 15370437666068796491, 9661293882813929899, 16671594122227576891, 12760716047967713053, 15836846371629855617, 15372573498823277741, 13037801868101928847, 9227832155694778921, 12305150816980735891, 15210658418843137207, 16788466837458690557, 9762486133521181153, 13371940588733082221, 10152546759088309507, 10848887643327358249, 17205964303284825847, 12583799778495365419, 9672644823779940799, 16479122731650726673, 11829095825108299229, 16856643509258471717, 17729801070393904861, 12446898694377908053, 15647792035238488259, 15262980088834134317, 14842714080641230361, 11892658365659114837, 15543608752847397577, 18134628238866132559, 17281754915383504451, 14880763471671790447, 18365273826942699029, 10593576240664735397, 13738012363336486327, 10585528712941671061, 15236197766771889647, 12962016451203849439, 10115648256105130097, 18284391657729233963, 10065785450550899873, 14857920561664507949, 16030693837709372611, 13900562821391763329, 12228162083162590063, 11182799187528291871, 10214055412817190283, 15460696099737060427, 12382626153236584387, 15465251424009421147, 16965031217756582281, 14126243176626361657, 18080871035396853247, 12890579554268090071, 12213352895923847441, 11657388029153192717, 10594146346641284267, 10061199141387371213, 11654321642876196877, 9824908207222632341, 9667965027898668031, 15337259287380080431, 11343809882060699179, 14165912342048965513, 11858958254391153371, 14644267317090978181, 15243216027706161023, 12709086352105620721, 12699306874452850307, 9623280468372066131, 12147185253639241291, 16601705326867205539, 10344891266561865029, 9295392664898294891, 11337442576012179707, 12437074606171059809, 16257047214863286941, 15963251223708366749, 9796716955285549447, 15639176349316312987, 9957650134111703227, 13427963685313160311, 14969656757466500147, 15214704302669139497, 16883998205231447767, 9582306718565802677, 18213300288961503953, 10133964032925729329, 13921564103985671879, 18189260807943763691, 15990390439904555291, 13338552747826262603, 10004697650349190067, 14464165999372352189, 9264423096518569807, 16223738667762317267, 12581099710736152931, 16783603748986153523]
e = 0x10001
def mlucas(v, a, n):
""" Helper function for williams_pp1(). Multiplies along a Lucas sequence modulo n. """
v1, v2 = v, (v ** 2 - 2) % n
for bit in bin(a)[3:]: v1, v2 = ((v1 ** 2 - 2) % n, (v1 * v2 - v) % n) if bit == "0" else (
(v1 * v2 - v) % n, (v2 ** 2 - 2) % n)
return v1
def ilog(x, b): # greatest integer l such that b**l <= x.
l = 0
while x >= b:
x /= b
l += 1
return l
def williams(n):
for v in count(1):
for p in primes:
e = ilog(isqrt(n), p)
if e == 0:
break
for _ in range(e):
v = mlucas(v, p, n)
g = gcd(v - 2, n)
if 1 < g < n:
return int(g), int(n // g) # g|n
if g == n:
break
p,q = williams(n)
phi = (p-1)*(q-1)
d = invert(e,phi)
m = pow(c,d,n)
flag = n2s(int(m))
print(flag)[RSA3]P8
from Crypto.Util.number import *
from gmpy2 import *
from libnum import *
from itertools import count
n = 17258060066893213074755453373218306582162826137762311133274776357570753221703880922246758313805944651653670388312409120584883194670296622866672717977722186711567375015117429341498055534372807872455441738225834253639068425012163751145785603722177526607324435641434593514768226599401862097301050185867830575469303960864978407638846270971263106481892520999227504152184478241946941685206875783621912245612463394268401327595737
e1 = 159897
e2 = 192273
c1 = 4595717262826082372249114022806610849627020753616385658397281529962210282956290111008418210778140550163959636029533312923781864970753502714169965973507425352493857361069899079130259227540344021591878554631845093918021212295485108865566378903346061480239406752062655328184620669486561050933167981474236084817766063901438798437061213111422401822238367462990085699301757131570089105471117732589635966783817714928153442984943
c2 = 6930904879823636264189052321687613173304614320999504775391013591790100775422558030373964338538540537224825701022993433544854997668153296576460906623734663341340853498020227553815076511099480950225109778895193096753014911735040516576988675988526232648772153671745762684830032445024652478629766700037603250123679920127263565322009118867116958069937438887437206234970465675161823446396025302570020058273271974621280101050077
e1 = e1//3
e2 = e2//3
g,x,y = gcdext(e1,e2)
m = pow(c1,x,n)*pow(c2,y,n)%n
m = iroot(m,3)[0]
print(long_to_bytes(m))[RSA3]P9
# sagemath
from gmpy2 import *
from Crypto.Util.number import *
import random
import math
def onemod(e, q):
p = random.randint(1, q-1)
while(powmod(p, (q-1)//e, q) == 1): # (r,s)=1
p = random.randint(1, q)
return p
def AMM_rth(o, r, q): # r|(q-1)
"""
x^r % q = o
:param o:
:param r:
:param q:
:return:
"""
assert((q-1) % r == 0)
p = onemod(r, q)
t = 0
s = q-1
while(s % r == 0):
s = s//r
t += 1
k = 1
while((s*k+1) % r != 0):
k += 1
alp = (s*k+1)//r
a = powmod(p, r**(t-1)*s, q)
b = powmod(o, r*a-1, q)
c = powmod(p, s, q)
h = 1
for i in range(1, t-1):
d = powmod(int(b), r**(t-1-i), q)
if d == 1:
j = 0
else:
j = (-int(math.log(d, a))) % r
b = (b*(c**(r*j))) % q
h = (h*c**j) % q
c = (c*r) % q
result = (powmod(o, alp, q)*h)
return result
def ALL_Solution(m, q, rt, cq, e):
mp = []
for pr in rt:
r = (pr*m) % q
# assert(pow(r, e, q) == cq)
mp.append(r)
return mp
def ALL_ROOT2(r, q): # use function set() and .add() ensure that the generated elements are not repeated
li = set()
while(len(li) < r):
p = powmod(random.randint(1, q-1), (q-1)//r, q)
li.add(p)
return li
def attack(p, q, e, check=None):
cp = c % p
cq = c % q
mp = AMM_rth(cp, e, p)
mq = AMM_rth(cq, e, q)
rt1 = ALL_ROOT2(e, p)
rt2 = ALL_ROOT2(e, q)
amp = ALL_Solution(mp, p, rt1, cp, e)
amq = ALL_Solution(mq, q, rt2, cq, e)
if check is not None:
j = 1
t1 = invert(q, p)
t2 = invert(p, q)
for mp1 in amp:
for mq1 in amq:
j += 1
if j % 1000000 == 0:
print(j)
ans = (mp1 * t1 * q + mq1 * t2 * p) % (p * q)
if check(ans):
return ans
return amp, amq
def calc(mp, mq, e, p, q):
i = 1
j = 1
t1 = invert(q, p)
t2 = invert(p, q)
for mp1 in mp:
for mq1 in mq:
j += 1
if j % 1000000 == 0:
print(j)
ans = (mp1*t1*q+mq1*t2*p) % (p*q)
if check(ans):
return
return
def check(m):
try:
a = long_to_bytes(m)
if b'NSSCTF' in a:
print(a)
return True
else:
return False
except:
return False
if __name__ == '__main__':
e = 1009
n = 38041020633815871156456469733983765765506895617311762629687651104582466286930269704125415948922860928755218376007606985275046819516740493733602776653724917044661666016759231716059415706703608364873041098478331738686843910748962386378250780017056206432910543374411668835255040201640020726710967482627384460424737495938659004753604600674521079949545966815918391090355556787926276553281009472950401599151788863393804355849499551329
c = 2252456587771662978440183865248648532442503596913181525329434089345680311102588580009450289493044848004270703980243056178363045412903946651952904162045861994915982599488021388197891419171012611795147125799759947942753772847866647801312816514803861011346523945623870123406891646751226481676463538137263366023714001998348605629756519894600802504515051642140147685496526829541501501664072723281466792594858474882239889529245732945
p = 5220649501756432310453173296020153841505609640978826669340282938895377093244978215488158231209243571089268416199675077647719021740691293187913372884975853901554910056350739745148711689601574920977808625399309470283
q = 7286645200183879820325990521698389973072307061827784645416472106180161656047009812712987400850001340478084529480635891468153462119149259083604029658605921695587836792877281924620444742434168448594010024363257554563
cp = c % p
cq = c % q
mp = AMM_rth(cp, e, p)
mq = AMM_rth(cq, e, q)
rt1 = ALL_ROOT2(e, p)
rt2 = ALL_ROOT2(e, q)
amp = ALL_Solution(mp, p, rt1, cp, e)
amq = ALL_Solution(mq, q, rt2, cq, e)
calc(amp, amq, e, p, q)
[RSA3]P10
- 此题目是AMM进阶
from gmpy2 import *
from Crypto.Util.number import *
import random
import math
n = 98950849420612859614279452190318782153029931966597217314273823358984928689736597943774367572478091193816498014404387458350141854427041188032441028722132300155987022405432547244436252627801235200799719531840755071562539171489733346246951714886747673950900290905148318965065773167290984966067642777528454814019184856012497536781760044965489668142694134954466581148235162435617572891367282110999553789319439912296241889469226304877
c = 22561646796929363815984273658718096881828574147472740106912668949512978818367595303883956088667384207835022579136977262135029404640598574466248596921339941958216824486529066880854722372158998556902335323841170236300423638675072077074005797219260622119718558697081430219981494670569821476853158740209737420919480047033900157150865588466910802691118334480300332681763467974691587834295938999022060676767513865584039532912503921584
p = 33918986475509072603988274492338254523919682179700323084167169617716245684540055969194500298976880885466534900490327133434356902533524212744941101469238500990334546197257933040365697281122571898438913033813040027859
q = 2917270228344219924472221188897798789902618263281810355113281879157575741497356945522168552316357276417700368971563177551494320723579146612010452353273237547587402941227901795977981691403950826343318848831462080703
e = 1009*7
def onemod(e, q):
p = random.randint(1, q-1)
while(powmod(p, (q-1)//e, q) == 1): # (r,s)=1
p = random.randint(1, q)
return p
def AMM_rth(o, r, q): # r|(q-1
assert((q-1) % r == 0)
p = onemod(r, q)
t = 0
s = q-1
while(s % r == 0):
s = s//r
t += 1
k = 1
while((s*k+1) % r != 0):
k += 1
alp = (s*k+1)//r
a = powmod(p, r**(t-1)*s, q)
b = powmod(o, r*a-1, q)
c = powmod(p, s, q)
h = 1
for i in range(1, t-1):
d = powmod(int(b), r**(t-1-i), q)
if d == 1:
j = 0
else:
j = (-math.log(d, a)) % r
b = (b*(c**(r*j))) % q
h = (h*c**j) % q
c = (c*r) % q
result = (powmod(o, alp, q)*h)
return result
def ALL_Solution(m, q, rt, cq, e):
mp = []
for pr in rt:
r = (pr*m) % q
# assert(pow(r, e, q) == cq)
mp.append(r)
return mp
def calc(mp, mq, e, p, q):
i = 1
j = 1
t1 = invert(q, p)
t2 = invert(p, q)
for mp1 in mp:
for mq1 in mq:
j += 1
if j % 100000 == 0:
print(j)
ans = (mp1*t1*q+mq1*t2*p) % (p*q)
if check(ans):
return
return
def check(m):
try:
a = long_to_bytes(m)
if b'NSSCTF' in a:
print(a)
return True
else:
return False
except:
return False
def ALL_ROOT2(r, q): # use function set() and .add() ensure that the generated elements are not repeated
li = set()
while(len(li) < r):
p = powmod(random.randint(1, q-1), (q-1)//r, q)
li.add(p)
return li
cp = c % p
cq = c % q
mp = AMM_rth(cp, e, p)
mq = AMM_rth(cq, 1009, q)
rt1 = ALL_ROOT2(e, p)
rt2 = ALL_ROOT2(1009, q)
amp = ALL_Solution(mp, p, rt1, cp, e)
amq = ALL_Solution(mq, q, rt2, cq, 1009)
d = invert(7, q-1)
mqs = []
for mq in amq:
mqs.append(pow(mq, d, q))
amq = mqs
calc(amp, amq, e, p, q)
# 6600000
# NSSCTF{827152d9-4ac6-4dd2-8f33-c6a28a1433d2}[RSA3]P11
数字证书
from Crypto.Util.number import *
from Crypto.PublicKey import RSA
f = open('key.pem', 'r')
public_key = RSA.import_key(f.read())
print(public_key)
n = public_key.n
d = public_key.d
c = 0x51712F71286FF89B8D785E2C99ED89FA623FE37A52142566CBCFFA0E73CA22B45077119CC228E4BB5C1B9ED2A5CD24A9E4EBB5EF1B26B9750C4DAC79693A02CD1D405D54D4E4CFA919DF9E69417415618FDD2C1F86B5A28787551FC91F60BC6E3530DD062CA3A7B1E504777C5A7FADC26EFEE711AB6CAFB448F27885B844A0E7
m = pow(c,d,n)
print(long_to_bytes(m))[RSA3]P12
证书修复
# RSA证书格式
标识头 30
总长度 82 025b
版本信息 0201 00
n 028180 70647879fa43aee8a5d3785754b7988d12b14b98cf39be21b5d90f3e3264e316cf99c3058b89480f2b46a0eda9bee6b4d753199671ef17bab4ec257aabe45e7eb6f668146597a0c9a05d0523e7511e8852a76eaa92e81d16afac7af522423aa00983110ce2d65099d37c748cc2aea0e2a9f4b0613fd8a30a8cbd89187db47f85
e 0203 010001
d 028180 2f2e7e44f682a352970a876261f610dc6814759fd89e6ceac9e42d39f6fdd337283f6c574f9479e3a44f2a0f9b4ac09efa25b0802fa4275a01c9809256c6afc4032ffd486f9e029681a3de126f607603559c7837fc17589d91750ebd4ff791dff06f0fe02d92f26bc582145e12519c74f534e832a4960c4248e24375ee953901
p 0241 009bfd4a17d26da30d2b7d4e920f4b488ef014babb8a2151979917bd228bb180771c028736557afd92f54d5da3837ef27fd322d9fd06c790155dbc22ff579ff51d
q 0241 00b873912447c540c3c96a78f2f00a40898ac5ca0043aa3d914e8920822159d8fb9278920899892df7aec916c2c6002011d52a25d2cbee4d76f5a4e7531e622f89
dp 0240 6264dbe6b8e255564a57694732847f494261210488f5c95cc1c1ba98dedae138c09f4ba0d73c9454ad8cd682fcc007c0df727d646071630e4729143e528c6075
dq 0240 6dc8a347c3cbfcdb4b63aaef75bdb461e90e064817fe18bd06d0895fcab7ee74f5ddfb9550c51c6e02433fdfd7f7b51ec8105908d94652270ed802b32f2f6379
inv(q,p) 0241 009951931fa0d4df28338c2b5d978ff6761a27487704a2f08558666e0aa063604c3a2066009693a2bff04808c5eb381b1d775fb88fa9f579dc474861fdab8028ba\(c^{d_{p}} \pmod{p} = c^{d + k*(p-1)} \pmod{p} = c^{d} \pmod{p}\)
当m< p时
\(m = c^{d}\pmod{p}\)
from base64 import *
from binascii import *
from Crypto.Util.number import *
'''
Oh17ELp/n2Urnqg/gaFbKWHgDNYzdPNGqNePgdrRtpfzq+js7QAiYNifLRK8k5XC
MwErb3RKOA0dCu14yftSoo2V+FjGML07Fk6Fe0BvVBMRQm1k1fC24NECgYEAvv/5
kH91u3rVYRMbXHauE3vWeuDjK5D5K5l7BEJ3yrPf64TyVROBJ+Gk5TdRpo23Q6AO
2KzFjzMQf+NdtrSBO8BI20i9UwvLNfukNNu3DifXiu3i3g1HRd81okVBe4x0oxp7
Vad9tF69btHcSz3KpDWnnb9yQNlndTcuZLWLCAMCgYB3pVRhTBEbUd6pA6joIivn
lbRZSIBfxvXqZ+YK1JPxF7MDPqLuhNh8CimofqOJCKk+MT4I/oPckbqGlbqWnUDy
Q63f9iDuQL2oVi/1OJZh79i51ZdrrPK8mhz8VNdwTHCYRBseclN2D8fbzvekFwgu
dJLo4ICPNNgwx3LoAHFPQQKBgBwQBf3qDEVAdetuYD3Eniz0q/2f3yC+iy2RvlZQ
4cLhjMvQ274OQJK4f37CEvgSqFOCR8wkDl7M1ObFZDZ87OP3i3zUgiSaff/veh/e
DFZDGlMqQoP3lXo5omq2HDnn2BdCw85A7qI6rUCECwbvDD/2NitiPooypxW8xs87
MTM7AoGBAISI776nLpq6x/cQhbhukHG+zhcPjJKjh669zIn4kVwzc5YJpzys1VWb
Olb9WQgu0xG6tJ9C6gumvl4lNFPbD8i1tqq0WBY7igExIf1cVU3MUdgcV+YPWdnX
+PTUX6skNl2gOe2PtUAc+v8Miq4hka6L10I1HREDT/Dwwy+wWGgQ
'''
c = 2329206064672111950904450292941421573350591294207157652026787098178545948258554492347649016030892000747909819064473414536692222493030122267884839986067073054508582403564557167583565364976046083954888777809177108315052118912603290095925912298584322873410379937455462434313487981715516761071523410121549134193124709612876311518391130974466069686830456036397449773159386026998482557500868323733155606973727191287617806211911722356975478414165867941665666556476756617951672736466672410799762479373101996896644454778482896784598378016390592459460753042458284030795009957030383305268628413551730442224404807955926606496353
a = b''
with open('a.txt','rb')as f:
for i in f.readlines():
a += i
s = b64decode(a)
s = hexlify(s)
print(s)
a = s.split(b'02')
for i in a:
print(i)
# n
# e
# d
# p = 数据不足
q = 0x00befff9907f75bb7ad561131b5c76ae137bd67ae0e32b90f92b997b044277cab3dfeb84f255138127e1a4e53751a68db743a00ed8acc58f33107fe35db6b4813bc048db48bd530bcb35fba434dbb70e27d78aede2de0d4745df35a245417b8c74a31a7b55a77db45ebd6ed1dc4b3dcaa435a79dbf7240d96775372e64b58b0803
dp = 0x77a554614c111b51dea903a8e8222be795b45948805fc6f5ea67e60ad493f117b3033ea2ee84d87c0a29a87ea38908a93e313e08fe83dc91ba8695ba969d40f243addff620ee40bda8562ff5389661efd8b9d5976bacf2bc9a1cfc54d7704c7098441b1e7253760fc7dbcef7a417082e7492e8e0808f34d830c772e800714f41
dq = 0x1c1005fdea0c454075eb6e603dc49e2cf4abfd9fdf20be8b2d91be5650e1c2e18ccbd0dbbe0e4092b87f7ec212f812a8538247cc240e5eccd4e6c564367cece3f78b7cd482249a7dffef7a1fde0c56431a532a4283f7957a39a26ab61c39e7d81742c3ce40eea23aad40840b06ef0c3ff6362b623e8a32a715bcc6cf3b31333b
inv_q_p = 0x008488efbea72e9abac7f71085b86e9071bece170f8c92a387aebdcc89f8915c33739609a73cacd5559b3a56fd59082ed311bab49f42ea0ba6be5e253453db0fc8b5b6aab458163b8a013121fd5c554dcc51d81c57e60f59d9d7f8f4d45fab24365da039ed8fb5401cfaff0c8aae2191ae8bd742351d11034ff0f0c32fb0586810
m = pow(c,dq,q)
flag = long_to_bytes(m)
print(flag)
