四月尾声
[羊城杯 2021]Easy_Rsa
pollard_Rho(p-1和q-1有较大公因子)
from gmpy2 import *
from Crypto.Util.number import *
n = 84236796025318186855187782611491334781897277899439717384242559751095347166978304126358295609924321812851255222430530001043539925782811895605398187299748256080526691975084042025794113521587064616352833904856626744098904922117855866813505228134381046907659080078950018430266048447119221001098505107823645953039
e = 58337
c = 13646200911032594651110040891135783560995665642049282201695300382255436792102048169200570930229947213493204600006876822744757042959653203573780257603577712302687497959686258542388622714078571068849217323703865310256200818493894194213812410547780002879351619924848073893321472704218227047519748394961963394668
f = lambda x,n: (pow(x, n - 1, n) + 3) % n
def phllard_rho(n):
i = 1
while True:
a = getRandomRange(2, n)
b = f(a, n)
j = 1
while True:
p = GCD(abs(a - b), n)
if p == n:
break
elif p > 1:
return (p, n // p)
else:
a = f(a, n)
b = f(f(b, n), n)
j += 1
i += 1
p,q = phllard_rho(n)
phi = (p-1)*(q-1)
d = invert(e,phi)
m = powmod(c,d,n)
flag = long_to_bytes(m)
print(flag)[NCTF 2019]easyRSA
AMM
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).decode('utf-8')
if 'NCTF' in a:
print(a)
return True
else:
return False
except:
return False
if __name__ == '__main__':
c = 10562302690541901187975815594605242014385201583329309191736952454310803387032252007244962585846519762051885640856082157060593829013572592812958261432327975138581784360302599265408134332094134880789013207382277849503344042487389850373487656200657856862096900860792273206447552132458430989534820256156021128891296387414689693952047302604774923411425863612316726417214819110981605912408620996068520823370069362751149060142640529571400977787330956486849449005402750224992048562898004309319577192693315658275912449198365737965570035264841782399978307388920681068646219895287752359564029778568376881425070363592696751183359
e = 0x1337
p = 199138677823743837339927520157607820029746574557746549094921488292877226509198315016018919385259781238148402833316033634968163276198999279327827901879426429664674358844084491830543271625147280950273934405879341438429171453002453838897458102128836690385604150324972907981960626767679153125735677417397078196059
q = 112213695905472142415221444515326532320352429478341683352811183503269676555434601229013679319423878238944956830244386653674413411658696751173844443394608246716053086226910581400528167848306119179879115809778793093611381764939789057524575349501163689452810148280625226541609383166347879832134495444706697124741
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)[强网杯 2022]ASR
n = 8250871280281573979365095715711359115372504458973444367083195431861307534563246537364248104106494598081988216584432003199198805753721448450911308558041115465900179230798939615583517756265557814710419157462721793864532239042758808298575522666358352726060578194045804198551989679722201244547561044646931280001
e = 3
c = 945272793717722090962030960824180726576357481511799904903841312265308706852971155205003971821843069272938250385935597609059700446530436381124650731751982419593070224310399320617914955227288662661442416421725698368791013785074809691867988444306279231013360024747585261790352627234450209996422862329513284149
p = 218566259296037866647273372633238739089
q = 223213222467584072959434495118689164399
r = 225933944608558304529179430753170813347
s = 260594583349478633632570848336184053653
PR.<x> = PolynomialRing(Zmod(p))
f = (x)^e - c
f = f.monic()
result1 = f.roots()
PR.<x> = PolynomialRing(Zmod(q))
f = (x)^e - c
f = f.monic()
result2 = f.roots()
PR.<x> = PolynomialRing(Zmod(r))
f = (x)^e - c
f = f.monic()
result3 = f.roots()
PR.<x> = PolynomialRing(Zmod(s))
f = (x)^e - c
f = f.monic()
result4 = f.roots()
def check(m):
h = m.hex()
if len(h) & 1:
return False
if b'flag' in bytes.fromhex(h):
print(bytes.fromhex(h))
return True
else:
return False
for i in result1:
for j in result2:
for l in result3:
for k in result4:
list1 = [int(i[0]),int(j[0]),int(l[0]),int(k[0])]
list2 = [p,q,r,s]
solution = CRT_list(list1, list2)
if check(solution):
print(solution)[羊城杯 2020]INVITATIONS
# sage
from gmpy2 import *
from Crypto.Util.number import *
from functools import reduce
Invitation1 = 2726880165485794753015221799903015469859604350960070462389832770775190258204902795671085685627736110579803076064313238826997962227132535666379117171603278182417820587346210511971127809627876548907651538393737303011542136469304569045407566630840981287558726831003180186144633381044057099863505591978316576331
Invitation2 = 52844103418322232725177561034428083147725292376614668718220523666259095447694889972949103379829470432332480992707892007073319952276490981511612735696207090391646476749895265951654074573797235607971038590694835782189124391368712277613425337912212240432011011071881837734857743183367019103096901117395938690572
Invitation3 = 129274519334082165644106292383763271862424981496822335330342328217347928093592453953990448827969549377883054831490973006383371688359344675312001881631556371220779971357039899721241880304156884612458373310254854821837978876725801047977081900824202659636258168216028784656056334358157381820784576207338479493823
Invitation4 = 56852637683122735164568970875066131746509133403072354742812890131597805562226047560392266004050592533316793038372256396537829143627478792510526346644756590135871716813976819138793368813440386409129373327577756689416990858633825538766694242123021009535005392002648416127869437948525458000795891155650312894218
Invitation5 = 24933581882539143383805596779774030477763512752520375486982562296903063067503747125713029403793101373585417342942950790457235350083784905974251188305010098928244056980941419687746319300184530161551239060873604405554973757867815783641391659818219177575212360602858057667033472530286856616676363511656764861866
Invitation6 = 7491476722927235473944826192371870577426352529433316210668760004930228302472920679959949471665143237333356259221787618020560963460668303766902416340056446225333025453011937952801159044781738493694911250765543392959285625650198325627539546777165439291150376527665779894748453633305704694635029402487576286720
Invitation7 = 46994515206702516116723205176259615067102717099690856936455392000070823814544052445278146449282379251128163008476565339875497253781717590664182753552262233895322322657625202522815172174432182181682631558679857615390973133346476079858014623412440411395083299226947371458955797627789607079672039131280242758091
Invitation8 = 8140023566779187828652447593867705813386781164538611122714708931585587727699213769519135028841126072130625547328311301696554048174772606261707345115571968105138543476580875347239912760797035694220505996377127309341770427102697008350472060971360460756799310951343070384766137332401117333917901167639276168214
Invitation9 = 8385766476371753553977800353128766303065572190592509929058486984964439147256960481698015327599879810752997804957814193113184978479627127131318723231581432235920975812354556190022727375961505764199831794239507708621401077801662954349957627630157786326057704380977697746043041515978455150985893713987598581167
Invitation10 = 25434511525127530194830986592289179576070740435049947678930286998924519588985583799757299734846614343604661534391991096353170465467791358514448923161460366596251448937540153262731348684727026598527904328268639060306102090278287818149679940661579357649191023269947102746200467430583428889484549034314463114080
Invitation11 = 9435583236354598287661880148272717764447540972316605192855157484524753847806158586224733743434644389385148450722945845355791145016665856388503878165725148745517696840251674049929524448078129458846254866804153080766917319923905682824180976106679633180818527967145571143203594244851742143986040226240019541346
Invitation12 = 42653412322252936189967169320174001935456500265020295381235749570735595316912049949245536609634786767873783560657460914097412643705264107040560389003526999720357122717443215007182355846769697457076620951388839672721527406861414375682603373503445636748304326212654026233985520038237509837611802457243967916967
Invitation13 = 50163996128508874413636370533324079468893191391677157815578286348174669089976633631417431754505804284298354381223186985949160012660340790440711469708712479223582014168361667639570586425626182863344576254691662799762136734638820942002509860333817967414572002225418810272184173820322912928927789061077468994953
Invitation14 = 55181712049788569218094734913693030675622116883683701002270524678292896232044695586872582672159854063365203462010143885417632291300773699604618481578372258936513301821561273604986211363808846581429372811764533701610119228124866223770584249909429743735157839245622925997548481946831963456454939343358587988983
[e1,N1]= [5,90361246179367799606636863352077187566064794796456461177972505143929614628873639223638940051613378291778175724735519020067052934403115774679961661481160141872257338930620863078688082915958381094674423803586734810828570206667419458295735288184697613296663226516640069281835035704453280781694226293902395215269]
[e2,N2]= [5,83202136479583179143205059354864808364257451670037867814548678142629716115373207061455185843132942837300718212806534861585785041547496145915392175827479376792813058845422044909477892978293495048968520853100992244672416436363272286740068846609018921112995562647093952700070707124842514243806528982910520604851]
[e3,N3]= [3,146694460234280339612721415368435987068740712812770728817136582256341063038147863645902264969297892447333024201649306207442798919845916187823646745721109151386096190207317810424580842120750075213595282979568495342617919336417068886973047979116994072272482630372638964064972815256237040541007947708358680368391]
[e4,N4]= [7,145212137982314671207105886550619275956842416412937060552686822638155412950680057688522218990023473104787006548449644240065948769143660097622695125682017688804838701293738298008178105057147539522368965730223561911750657089352591376219016726977232279206451303896573325330139830440927228125810665303608828462177]
[e5,N5]= [5,69335368232766044823545542187513771534967902179150417021053554241638095909666122935053210964003511014870892979205875153115719406287728162111662254890513324436473313860142126335197489227724691042286796058111753972895113145188906829975189506125997319609609974126645475084944238417929532560409919420929255247813]
[e6,N6]= [5,93889543065608951579836429313520485233295158467296710329997599807630401722519056218864031741675898621375735347229494633577571323057785261271373295860331130588582231771193563731092603614818963592931492474988532068227153492022582339704874613690044001529412669510094771064646843676765163737757104643318364446839]
[e7,N7]= [7,66174700839404221060785862467924299511645570336361033287335855493589093141782896451863402373425798838446538369142584932156150350565382116869446083154097803842190010954019565857767923584979615770650706675094209251111816761431713779074557571353022624477001770694207393369796369620048999514683357963227119554487]
[e8,N8]= [3,65031485534704406281490718325237831433086480239135617407356760819741796565231283220528137697949585150709734732370203390254643835828984376427852793969716489016520923272675090536677771074867975287284694860155903327351119710765174437247599498342292671117884858621418276613385329637307269711179183430246951756029]
[e9,N9]=[5,72454311940971803130612024751128556938725737742029062979349607787083978826668706819793864356790325653817555839762732164812521831864626411495002267399139766907846534945632792910468487287154661692733986224962564621615361536373173705359255153606552352581704159462310354407361311378558150604159961029937052901709]
[e10,N10]= [3,126172075578367446151297289668746433680600889845504078949758568698284471307000358407453139846282095477016675769468273204536898117467559575203458221600341760844973676129445394999861380625435418853474246813202182316736885441120197888145039130477114127079444939102267586634051045795627433724810346460217871661901]
[e11,N11]= [3,75691424835079457343374072990750986689075078863640186724151061449621926239051140991748483370587430224317778303489124525034113533087612981452189061743589227565099659070008017454957304620495920813121234552401715857719372861565651204968408267740732475458128601061676264465241188491988485848198323410127587280471]
[e12,N12]= [7,88063052818271125442049408332053226451497067720511502513828848476569985821115735898897947439175727789641390104005400308936768495751619165683456550165811034670341697022370415202614387373196086237042577737857259724530596416810462125219296930758592032765843338961894697491961439584875235274163072466474940670589]
[e13,N13]= [5,86478932133708863968749977073639049451666195461247968321317885106346907736572028122496476049748246757185316498949163898915427948597498506162230927380667345132742891001640364064647368394822175742973968167028656790729030556005407153405955458636780270673780720333871959638216946584461925553782697695137132507853]
[e14,N14] =[7,137641493263428303662262187582231235637921833879366309318941383348412296182252654397496377642861646991438721153462001357875169325595544056465299787575422581289053630686684843044593163904089201855371863459503176022957832807726507152235818181000484878683030989944063049622694810207054366378176225221479695833371]
# crt(模数 ，余数)
n = [N3,N8,N10,N11]
c = [Invitation3,Invitation8,Invitation10,Invitation11]
# crt(,)
def CRT(mi, ai):
M = reduce(lambda x, y: x * y, mi)
ai_ti_Mi = [a * (M // m) * invert(M // m, m) for (m, a) in zip(mi, ai)]
return reduce(lambda x, y: x + y, ai_ti_Mi) % M
c = [eval('[Invitation{},e{},N{} , {}]'.format(i+1,i+1,i+1 , i+1)) for i in range(14)]
# tmp = [c,e,n , s]
tmp = []
for i in c:
if i[1] == 3:
tmp.append(i)
n = [ i[2] for i in tmp]
c = [ i[0] for i in tmp]
s = [ i[3] for i in tmp]
tN = reduce(lambda x , y:x*y , n)
Zx.<x> = PolynomialRing(Zmod(tN))
f = 0
for i in range(len(tmp)):
tmpf = (s[i]*pow(3,431) + x)^3 - c[i]
tmpf.monic()
temp = [1 if k == i else 0 for k in range(len(tmp))] ### 还不懂 懂的踢我
T = CRT(n , temp)
f += tmpf * T
roots = f.small_roots(X = 2^(431 * 2) ,beta = 1)
print(roots)
m = iroot(mpz(roots[0]),2)[0]
flag = long_to_bytes(m)
print(flag)[CISCN 2021华南]small
#二元coppersmith
from Crypto.Util.number import *
import itertools
import hashlib
def small_roots(f, bounds, m=1, d=None):
if not d:
d = f.degree()
R = f.base_ring()
N = R.cardinality()
f /= f.coefficients().pop(0)
f = f.change_ring(ZZ)
G = Sequence([], f.parent())
for i in range(m + 1):
base = N ^ (m - i) * f ^ i
for shifts in itertools.product(range(d), repeat=f.nvariables()):
g = base * prod(map(power, f.variables(), shifts))
G.append(g)
B, monomials = G.coefficient_matrix()
monomials = vector(monomials)
factors = [monomial(*bounds) for monomial in monomials]
for i, factor in enumerate(factors):
B.rescale_col(i, factor)
B = B.dense_matrix().LLL()
B = B.change_ring(QQ)
for i, factor in enumerate(factors):
B.rescale_col(i, 1 / factor)
H = Sequence([], f.parent().change_ring(QQ))
for h in filter(None, B * monomials):
H.append(h)
I = H.ideal()
if I.dimension() == -1:
H.pop()
elif I.dimension() == 0:
roots = []
for root in I.variety(ring=ZZ):
root = tuple(R(root[var]) for var in f.variables())
roots.append(root)
return roots
return []
p = 8813834626918693034209829623386418111935369643440896703895290043343199520112218432639643684400534953548489779045914955504743423765099014797611981422650409
a = 2817275225516767613658440250260394873529274896419346861054126128919212362519165468003171950475070788320195398302803745633617864408366174315471102773073469
b = 1763620527779958060718182646420541623477856799630691559360944374374235694750950917040727594731391703184965719358552775151767735359739899063298735788999711
c = 2298790980294663527827702586525963981886518365072523836572440106026473419042192180086308154346777239817235315513418426401278994450805667292449334757693881
R.<x,y> = Zmod(p)[]
f = ( 1 + a * x * y ** 2 + b * x ** 2 * y ) - c
#f = f.monic()
x,y = small_roots(f,bounds = [2^71,2^71])[0]
print(x,y)
m = str(x) + str(y)
h = hashlib.sha256()
h.update(m.encode())
print(h.hexdigest())
print('flag{'+h.hexdigest()+'}')[楚慧杯2023]RollingBase
import base64
import string
enc = 'ly9tl+gDcvc9Zyc/kvdtYfNtafw+ZfYCYCQAZPUDZicEZvgBk/hwVfpQ'
str1 = string.ascii_uppercase + string.ascii_lowercase + string.digits + '+/'
for i in range(64):
bytes1 = str1.encode()
bytes2 = bytes1[i:] + bytes1[:i]
trans = bytes.maketrans(bytes2,bytes1)
destr = base64.b64decode(enc.translate(trans))
if b'flag' in destr:
print(destr)
breakDASCTF Apr.2023 X SU战队2023开局之战
【简单】sign1n
\(WHATF = d^{3} + 3 \pmod{phi}\)
\(\Rightarrow e^{3}*(WHATF-3) = 1\pmod{phi}\)
\(\Rightarrow e^{3}*(WHATF-3) = 1 + k*phi\)
\(e^{3} \ 49bits \ Whatf \ 2046bits \ phi和n的位数差不多2048bits\)
\(\Rightarrow (e^{3}*(WHATF-3)-1)/n = k*phi/n \approx k\)
from Crypto.Util.number import *
from gmpy2 import *
e = 65537
n = 17501785470905115084530641937586010443633001681612179692218171935474388105810758340844015368385708349722992595891293984847291588862799310921139505076364559140770828784719022502905431468825797666445114531707625227170492272392144861677408547696040355055483067831733807927267488677560035243230884564063878855983123740667214237638766779250729115967995715398679183680360515620300448887396447013941026492557540060990171678742387611013736894406804530109193638867704765955683067309269778890269186100476308998155078252336943147988308936856121869803970807195714727873626949774272831321358988667427984601788595656519292763705699
WHATF = 7550872408895903340469549867088737779221735042983487867888690747510707575208917229455135563614675077641314504029666714424242441219246566431788414277587183624484845351111624500646035107614221756706581150918776828118482092241867365644233950852801286481603893259029733993572417125002284605243126366683373762688802313288572798197775563793405251353957529601737375987762230223965539018597115373258092875512799931693493522478726661976059512568029782074142871019609980899851702029278565972205831732184397965899892253392769838212803823816067145737697311648549879049613081017925387808738647333178075446683195899683981412014732
sign = 12029865785359077271888851642408932941748698222400692402967271078485911077035193062225857653592806498565936667868784327397659271889359852555292426797695393591842279629975530499882434299824406229989496470187187565025826834367095435441393901750671657454855301104151016192695436071059013094114929109806658331209302942624722867961155156665675500638029626815869590842939369327466155186891537025880396861428410389552502395963071259114101340089657190695306100646728391832337848064478382298002033457224425654731106858054291015385823564302151351406917158392454536296555530524352049490745470215338669859669599380477470525863815
k = ( e**3*(WHATF - 3 ) - 1 ) // n
phi = ( e**3*(WHATF - 3 ) - 1 ) // (k + 1)
d = inverse(e,phi)
# m = flag * pow(r,e**2+d**2,n) % n
# sign = pow(m,d,n)
m = pow(sign,e,n)
flag = m * inverse(pow(2,( e**2+d**2 )%phi,n),n) % n
flag = long_to_bytes(flag)
print(flag)[D^3CTF 2022] d3factor
from Crypto.Util.number import *
from gmpy2 import *
from libnum import *
from hashlib import *
c = 2420624631315473673388732074340410215657378096737020976722603529598864338532404224879219059105950005655100728361198499550862405660043591919681568611707967
N = 1476751427633071977599571983301151063258376731102955975364111147037204614220376883752032253407881568290520059515340434632858734689439268479399482315506043425541162646523388437842149125178447800616137044219916586942207838674001004007237861470176454543718752182312318068466051713087927370670177514666860822341380494154077020472814706123209865769048722380888175401791873273850281384147394075054950169002165357490796510950852631287689747360436384163758289159710264469722036320819123313773301072777844457895388797742631541101152819089150281489897683508400098693808473542212963868834485233858128220055727804326451310080791
e1 = 425735006018518321920113858371691046233291394270779139216531379266829453665704656868245884309574741300746121946724344532456337490492263690989727904837374279175606623404025598533405400677329916633307585813849635071097268989906426771864410852556381279117588496262787146588414873723983855041415476840445850171457530977221981125006107741100779529209163446405585696682186452013669643507275620439492021019544922913941472624874102604249376990616323884331293660116156782891935217575308895791623826306100692059131945495084654854521834016181452508329430102813663713333608459898915361745215871305547069325129687311358338082029
e2 = 1004512650658647383814190582513307789549094672255033373245432814519573537648997991452158231923692387604945039180687417026069655569594454408690445879849410118502279459189421806132654131287284719070037134752526923855821229397612868419416851456578505341237256609343187666849045678291935806441844686439591365338539029504178066823886051731466788474438373839803448380498800384597878814991008672054436093542513518012957106825842251155935855375353004898840663429274565622024673235081082222394015174831078190299524112112571718817712276118850981261489528540025810396786605197437842655180663611669918785635193552649262904644919
e = 0x10001
PR.<x> = PolynomialRing(Zmod(N))
f = e1*e2*x - e1 + e2
f = f.monic()
pp = f.small_roots(X=2^1000, beta=0.44)
h = pp[0]
p_6 = gcd(ZZ(e1*e2*h - e1 + e2 ), N)
p = iroot(p_6,6)[0]
q = N//(p^7)
n = p*q
d = invert(e,(p-1)*(q-1))
m = pow(c,d,n)
flag = n2s(int(m))
print(flag)
flag = 'd3ctf{'+md5(flag).hexdigest()+'}'
print(flag)[RSA3]P10
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
b"NSSCTF{827152d9-4ac6-4dd2-8f33-c6a28a1433d2}"
六月中旬
双人成行
from Crypto.Util.number import *
from gmpy2 import *
from libnum import *
e = 183183094232895496570030296666322746922054965594187733500344545328263827233
n = 126930298936285661712486297662920895162569606037310367763354747221281175771655642407136326621695910623038808779778530112406355314071209370688157872928010633181351390724545013677593062556323119308457918805555312069055604237211117650220178416298165021603211366843640334616217695418858036626587483782452105122653
c = 113627841667808982839757084973426219545127121566516056267404541633803040730885409234473068650543791446730694746311695177758797711077000091232969424826171863685060090359260225102836081852105845748467870581394884564134418376982186965340367386781824886506478939204791426457255483148486730526127180397268053506840
h1 = 87021607670080656750728189202811647321664825322085967432146885995538140004901574830625347954724344331514731852873721100175299656618161173874818773415684739773055620673258848991693719847569489515642296650035465632567910004553054397894647697286044465567405142149926303968235362573821060105908856127568162452912
h2 = 70528801000055618659638315463133504198238507722722570127215098017082205934290867816695737682738831717228470799826957490782948760796844881508632060312080331264474968266753069687287034453036854258618280625776346633340081217397502423530180647548747144401922660710323623212890923488339464759360304751017490144695
p = gcd(h1-h2,n)
q = n//p
e = e//21
phi = (p-1)*(q-1)
d = invert(e,phi)
c = pow(c,d,n)
P.<a>=PolynomialRing(Zmod(p),implementation='NTL')
f = a^21 - c
mps = f.monic().roots()
P.<a>=PolynomialRing(Zmod(q),implementation='NTL')
f = a^21 - c
mqs = f.monic().roots()
for mpp in mps :
x = mpp[0]
for mqq in mqs :
y = mqq[0]
res = CRT_list([ZZ(x),ZZ(y)],[p,q])
m = long_to_bytes(res)
if b'flag' in m:
print(m)
# flag{5a6814eb-8848-11ed-aee3-d812656dd8d8}
