DASCTF2024 夏季赛
参与了一下DASCTF，发现自己还是太菜了QAQ
complex_enc
题目：
宁静祥和的一天里，半空中突然出现一道光门，我们怎么进去呢？
On a peaceful and serene day, a portal of light suddenly appeared in mid-air. How do we get inside?
from Crypto.Util.number import *
import random
from secret import flag
def GET_KEY(n):
sum=2
key=[1]
for i in range(n):
r=random.randint(0,1)
x=sum+random.randint(0,n)*r
key.append(x)
sum+=x
return key
def enc(m,k):
cipher_list = []
for i in range(len(m)):
if m[i] == 1:
cipher_list.append(m[i] * k[i])
cipher = sum(cipher_list)
return cipher
m=bytes_to_long(flag)
m = [int(bit) for byte in flag for bit in format(byte, '08b')]
key=GET_KEY(len(m))
c=enc(m,key)
with open('output.txt', 'w') as f:
f.write(str(c))
f.write(str(key))
#287687761937146187597379915545639385740275457170939564210821293233370716878150576
#[1, 2, 87, 99, 190, 380, 760, 1702, 3350, 6712, 13302, 26669, 53257, 106512, 213212, 426262, 852583, 1705083, 3410164, 6820581, 13640909, 27281818, 54563749, 109127508, 218254958, 436509851, 873019897, 1746039768, 3492079367, 6984158992, 13968317822, 27936635563, 55873271257, 111746542368, 223493084736, 446986169472, 893972338944, 1787944677888, 3575889355776, 7151778711750, 14303557423366, 28607114846668, 57214229693336, 114428459386792, 228856918773559, 457713837547023, 915427675094046, 1830855350188252, 3661710700376344, 7323421400752912, 14646842801505675, 29293685603011275, 58587371206022773, 117174742412045483, 234349484824090806, 468698969648181659, 937397939296363271, 1874795878592726601, 3749591757185453143, 7499183514370906547, 14998367028741812852, 29996734057483625898, 59993468114967251756, 119986936229934503501, 239973872459869007099, 479947744919738013939, 959895489839476027878, 1919790979678952055983, 3839581959357904111739, 7679163918715808223719, 15358327837431616447319, 30716655674863232894717, 61433311349726465789458, 122866622699452931578804, 245733245398905863157495, 491466490797811726314990, 982932981595623452629980, 1965865963191246905260222, 3931731926382493810520182, 7863463852764987621040623, 15726927705529975242080987, 31453855411059950484161974, 62907710822119900968323970, 125815421644239801936647918, 251630843288479603873295836, 503261686576959207746591710, 1006523373153918415493183613, 2013046746307836830986367190, 4026093492615673661972734253, 8052186985231347323945468456, 16104373970462694647890936894, 32208747940925389295781874025, 64417495881850778591563748059, 128834991763701557183127495888, 257669983527403114366254991760, 515339967054806228732509983520, 1030679934109612457465019967093, 2061359868219224914930039934133, 4122719736438449829860079868450, 8245439472876899659720159736935, 16490878945753799319440319473651, 32981757891507598638880638947330, 65963515783015197277761277894728, 131927031566030394555522555789579, 263854063132060789111045111579109, 527708126264121578222090223158048, 1055416252528243156444180446316096, 2110832505056486312888360892632193, 4221665010112972625776721785264450, 8443330020225945251553443570528835, 16886660040451890503106887141057670, 33773320080903781006213774282115477, 67546640161807562012427548564230882, 135093280323615124024855097128461699, 270186560647230248049710194256923398, 540373121294460496099420388513846796, 1080746242588920992198840777027693592, 2161492485177841984397681554055387246, 4322984970355683968795363108110774528, 8645969940711367937590726216221549105, 17291939881422735875181452432443098117, 34583879762845471750362904864886196180, 69167759525690943500725809729772392360, 138335519051381887001451619459544784838, 276671038102763774002903238919089569616, 553342076205527548005806477838179139174, 1106684152411055096011612955676358278348, 2213368304822110192023225911352716556750, 4426736609644220384046451822705433113446, 8853473219288440768092903645410866226907, 17706946438576881536185807290821732453830, 35413892877153763072371614581643464907890, 70827785754307526144743229163286929815519, 141655571508615052289486458326573859631099, 283311143017230104578972916653147719262229, 566622286034460209157945833306295438524626, 1133244572068920418315891666612590877049074, 2266489144137840836631783333225181754098066, 4532978288275681673263566666450363508196132, 9065956576551363346527133332900727016392264, 18131913153102726693054266665801454032784553, 36263826306205453386108533331602908065569081, 72527652612410906772217066663205816131138180, 145055305224821813544434133326411632262276342, 290110610449643627088868266652823264524552684, 580221220899287254177736533305646529049105368, 1160442441798574508355473066611293058098210736, 2320884883597149016710946133222586116196421472, 4641769767194298033421892266445172232392842944, 9283539534388596066843784532890344464785686063, 18567079068777192133687569065780688929571371951, 37134158137554384267375138131561377859142743902, 74268316275108768534750276263122755718285487804, 148536632550217537069500552526245511436570975608, 297073265100435074139001105052491022873141951360, 594146530200870148278002210104982045746283902576, 1188293060401740296556004420209964091492567805360, 2376586120803480593112008840419928182985135610512, 4753172241606961186224017680839856365970271221024, 9506344483213922372448035361679712731940542442048, 19012688966427844744896070723359425463881084884096, 38025377932855689489792141446718850927762169768220, 76050755865711378979584282893437701855524339536412, 152101511731422757959168565786875403711048679072824, 304203023462845515918337131573750807422097358145648, 608406046925691031836674263147501614844194716291296, 1216812093851382063673348526295003229688389432582797, 2433624187702764127346697052590006459376778865165617, 4867248375405528254693394105180012918753557730331006, 9734496750811056509386788210360025837507115460662129, 19468993501622113018773576420720051675014230921324265, 38937987003244226037547152841440103350028461842648406, 77875974006488452075094305682880206700056923685296910, 155751948012976904150188611365760413400113847370593722, 311503896025953808300377222731520826800227694741187444, 623007792051907616600754445463041653600455389482374933, 1246015584103815233201508890926083307200910778964749821, 2492031168207630466403017781852166614401821557929499642, 4984062336415260932806035563704333228803643115858999284, 9968124672830521865612071127408666457607286231717998666, 19936249345661043731224142254817332915214572463435997301, 39872498691322087462448284509634665830429144926871994535, 79744997382644174924896569019269331660858289853743989190, 159489994765288349849793138038538663321716579707487978260, 318979989530576699699586276077077326643433159414975956596, 637959979061153399399172552154154653286866318829951913129, 1275919958122306798798345104308309306573732637659903826311, 2551839916244613597596690208616618613147465275319807652591, 5103679832489227195193380417233237226294930550639615305147, 10207359664978454390386760834466474452589861101279230610294, 20414719329956908780773521668932948905179722202558461220588, 40829438659913817561547043337865897810359444405116922441176, 81658877319827635123094086675731795620718888810233844882508, 163317754639655270246188173351463591241437777620467689764860, 326635509279310540492376346702927182482875555240935379529854, 653271018558621080984752693405854364965751110481870759059704, 1306542037117242161969505386811708729931502220963741518119363, 2613084074234484323939010773623417459863004441927483036238705, 5226168148468968647878021547246834919726008883854966072477346, 10452336296937937295756043094493669839452017767709932144954692, 20904672593875874591512086188987339678904035535419864289909384, 41809345187751749183024172377974679357808071070839728579818768, 83618690375503498366048344755949358715616142141679457159637536, 167237380751006996732096689511898717431232284283358914319275072, 334474761502013993464193379023797434862464568566717828638550144, 668949523004027986928386758047594869724929137133435657277100288, 1337899046008055973856773516095189739449858274266871314554200576, 2675798092016111947713547032190379478899716548533742629108401375, 5351596184032223895427094064380758957799433097067485258216802527, 10703192368064447790854188128761517915598866194134970516433605054, 21406384736128895581708376257523035831197732388269941032867210108, 42812769472257791163416752515046071662395464776539882065734420216, 85625538944515582326833505030092143324790929553079764131468840607, 171251077889031164653667010060184286649581859106159528262937681073, 342502155778062329307334020120368573299163718212319056525875362112, 685004311556124658614668040240737146598327436424638113051750724224, 1370008623112249317229336080481474293196654872849276226103501448448, 2740017246224498634458672160962948586393309745698552452207002896896, 5480034492448997268917344321925897172786619491397104904414005793914, 10960068984897994537834688643851794345573238982794209808828011587706, 21920137969795989075669377287703588691146477965588419617656023175412, 43840275939591978151338754575407177382292955931176839235312046350824, 87680551879183956302677509150814354764585911862353678470624092701691, 175361103758367912605355018301628709529171823724707356941248185403485, 350722207516735825210710036603257419058343647449414713882496370806824, 701444415033471650421420073206514838116687294898829427764992741613648, 1402888830066943300842840146413029676233374589797658855529985483227499, 2805777660133886601685680292826059352466749179595317711059970966454839, 5611555320267773203371360585652118704933498359190635422119941932909634, 11223110640535546406742721171304237409866996718381270844239883865819325, 22446221281071092813485442342608474819733993436762541688479767731638735, 44892442562142185626970884685216949639467986873525083376959535463277328, 89784885124284371253941769370433899278935973747050166753919070926554729, 179569770248568742507883538740867798557871947494100333507838141853109648, 359139540497137485015767077481735597115743894988200667015676283706219166, 718279080994274970031534154963471194231487789976401334031352567412438331, 1436558161988549940063068309926942388462975579952802668062705134824876530, 2873116323977099880126136619853884776925951159905605336125410269649753060, 5746232647954199760252273239707769553851902319811210672250820539299506381, 11492465295908399520504546479415539107703804639622421344501641078599012695, 22984930591816799041009092958831078215407609279244842689003282157198025444, 45969861183633598082018185917662156430815218558489685378006564314396050678, 91939722367267196164036371835324312861630437116979370756013128628792101318, 183879444734534392328072743670648625723260874233958741512026257257584202636, 367758889469068784656145487341297251446521748467917483024052514515168405272, 735517778938137569312290974682594502893043496935834966048105029030336810544, 1471035557876275138624581949365189005786086993871669932096210058060673621088, 2942071115752550277249163898730378011572173987743339864192420116121347242216, 5884142231505100554498327797460756023144347975486679728384840232242694484649, 11768284463010201108996655594921512046288695950973359456769680464485388969041, 23536568926020402217993311189843024092577391901946718913539360928970777938082, 47073137852040804435986622379686048185154783803893437827078721857941555876305, 94146275704081608871973244759372096370309567607786875654157443715883111752579, 188292551408163217743946489518744192740619135215573751308314887431766223505070, 376585102816326435487892979037488385481238270431147502616629774863532447010118, 753170205632652870975785958074976770962476540862295005233259549727064894020344, 1506340411265305741951571916149953541924953081724590010466519099454129788040580, 3012680822530611483903143832299907083849906163449180020933038198908259576081160, 6025361645061222967806287664599814167699812326898360041866076397816519152162452, 12050723290122445935612575329199628335399624653796720083732152795633038304324883, 24101446580244891871225150658399256670799249307593440167464305591266076608649853, 48202893160489783742450301316798513341598498615186880334928611182532153217299508, 96405786320979567484900602633597026683196997230373760669857222365064306434599262, 192811572641959134969801205267194053366393994460747521339714444730128612869198530, 385623145283918269939602410534388106732787988921495042679428889460257225738396863]做题流程：
根据GET_KEY的流程很容易发现是个超递增的背包，所以我们只需要直接暴力尝试就可以解出。
from Crypto.Util.number import *
from gmpy2 import *
from sys import exit
c = 287687761937146187597379915545639385740275457170939564210821293233370716878150576
key = [1, 2, 87, 99, 190, 380, 760, 1702, 3350, 6712, 13302, 26669, 53257, 106512, 213212, 426262, 852583, 1705083, 3410164, 6820581, 13640909, 27281818, 54563749, 109127508, 218254958, 436509851, 873019897, 1746039768, 3492079367, 6984158992, 13968317822, 27936635563, 55873271257, 111746542368, 223493084736, 446986169472, 893972338944, 1787944677888, 3575889355776, 7151778711750, 14303557423366, 28607114846668, 57214229693336, 114428459386792, 228856918773559, 457713837547023, 915427675094046, 1830855350188252, 3661710700376344, 7323421400752912, 14646842801505675, 29293685603011275, 58587371206022773, 117174742412045483, 234349484824090806, 468698969648181659, 937397939296363271, 1874795878592726601, 3749591757185453143, 7499183514370906547, 14998367028741812852, 29996734057483625898, 59993468114967251756, 119986936229934503501, 239973872459869007099, 479947744919738013939, 959895489839476027878, 1919790979678952055983, 3839581959357904111739, 7679163918715808223719, 15358327837431616447319, 30716655674863232894717, 61433311349726465789458, 122866622699452931578804, 245733245398905863157495, 491466490797811726314990, 982932981595623452629980, 1965865963191246905260222, 3931731926382493810520182, 7863463852764987621040623, 15726927705529975242080987, 31453855411059950484161974, 62907710822119900968323970, 125815421644239801936647918, 251630843288479603873295836, 503261686576959207746591710, 1006523373153918415493183613, 2013046746307836830986367190, 4026093492615673661972734253, 8052186985231347323945468456, 16104373970462694647890936894, 32208747940925389295781874025, 64417495881850778591563748059, 128834991763701557183127495888, 257669983527403114366254991760, 515339967054806228732509983520, 1030679934109612457465019967093, 2061359868219224914930039934133, 4122719736438449829860079868450, 8245439472876899659720159736935, 16490878945753799319440319473651, 32981757891507598638880638947330, 65963515783015197277761277894728, 131927031566030394555522555789579, 263854063132060789111045111579109, 527708126264121578222090223158048, 1055416252528243156444180446316096, 2110832505056486312888360892632193, 4221665010112972625776721785264450, 8443330020225945251553443570528835, 16886660040451890503106887141057670, 33773320080903781006213774282115477, 67546640161807562012427548564230882, 135093280323615124024855097128461699, 270186560647230248049710194256923398, 540373121294460496099420388513846796, 1080746242588920992198840777027693592, 2161492485177841984397681554055387246, 4322984970355683968795363108110774528, 8645969940711367937590726216221549105, 17291939881422735875181452432443098117, 34583879762845471750362904864886196180, 69167759525690943500725809729772392360, 138335519051381887001451619459544784838, 276671038102763774002903238919089569616, 553342076205527548005806477838179139174, 1106684152411055096011612955676358278348, 2213368304822110192023225911352716556750, 4426736609644220384046451822705433113446, 8853473219288440768092903645410866226907, 17706946438576881536185807290821732453830, 35413892877153763072371614581643464907890, 70827785754307526144743229163286929815519, 141655571508615052289486458326573859631099, 283311143017230104578972916653147719262229, 566622286034460209157945833306295438524626, 1133244572068920418315891666612590877049074, 2266489144137840836631783333225181754098066, 4532978288275681673263566666450363508196132, 9065956576551363346527133332900727016392264, 18131913153102726693054266665801454032784553, 36263826306205453386108533331602908065569081, 72527652612410906772217066663205816131138180, 145055305224821813544434133326411632262276342, 290110610449643627088868266652823264524552684, 580221220899287254177736533305646529049105368, 1160442441798574508355473066611293058098210736, 2320884883597149016710946133222586116196421472, 4641769767194298033421892266445172232392842944, 9283539534388596066843784532890344464785686063, 18567079068777192133687569065780688929571371951, 37134158137554384267375138131561377859142743902, 74268316275108768534750276263122755718285487804, 148536632550217537069500552526245511436570975608, 297073265100435074139001105052491022873141951360, 594146530200870148278002210104982045746283902576, 1188293060401740296556004420209964091492567805360, 2376586120803480593112008840419928182985135610512, 4753172241606961186224017680839856365970271221024, 9506344483213922372448035361679712731940542442048, 19012688966427844744896070723359425463881084884096, 38025377932855689489792141446718850927762169768220, 76050755865711378979584282893437701855524339536412, 152101511731422757959168565786875403711048679072824, 304203023462845515918337131573750807422097358145648, 608406046925691031836674263147501614844194716291296, 1216812093851382063673348526295003229688389432582797, 2433624187702764127346697052590006459376778865165617, 4867248375405528254693394105180012918753557730331006, 9734496750811056509386788210360025837507115460662129, 19468993501622113018773576420720051675014230921324265, 38937987003244226037547152841440103350028461842648406, 77875974006488452075094305682880206700056923685296910, 155751948012976904150188611365760413400113847370593722, 311503896025953808300377222731520826800227694741187444, 623007792051907616600754445463041653600455389482374933, 1246015584103815233201508890926083307200910778964749821, 2492031168207630466403017781852166614401821557929499642, 4984062336415260932806035563704333228803643115858999284, 9968124672830521865612071127408666457607286231717998666, 19936249345661043731224142254817332915214572463435997301, 39872498691322087462448284509634665830429144926871994535, 79744997382644174924896569019269331660858289853743989190, 159489994765288349849793138038538663321716579707487978260, 318979989530576699699586276077077326643433159414975956596, 637959979061153399399172552154154653286866318829951913129, 1275919958122306798798345104308309306573732637659903826311, 2551839916244613597596690208616618613147465275319807652591, 5103679832489227195193380417233237226294930550639615305147, 10207359664978454390386760834466474452589861101279230610294, 20414719329956908780773521668932948905179722202558461220588, 40829438659913817561547043337865897810359444405116922441176, 81658877319827635123094086675731795620718888810233844882508, 163317754639655270246188173351463591241437777620467689764860, 326635509279310540492376346702927182482875555240935379529854, 653271018558621080984752693405854364965751110481870759059704, 1306542037117242161969505386811708729931502220963741518119363, 2613084074234484323939010773623417459863004441927483036238705, 5226168148468968647878021547246834919726008883854966072477346, 10452336296937937295756043094493669839452017767709932144954692, 20904672593875874591512086188987339678904035535419864289909384, 41809345187751749183024172377974679357808071070839728579818768, 83618690375503498366048344755949358715616142141679457159637536, 167237380751006996732096689511898717431232284283358914319275072, 334474761502013993464193379023797434862464568566717828638550144, 668949523004027986928386758047594869724929137133435657277100288, 1337899046008055973856773516095189739449858274266871314554200576, 2675798092016111947713547032190379478899716548533742629108401375, 5351596184032223895427094064380758957799433097067485258216802527, 10703192368064447790854188128761517915598866194134970516433605054, 21406384736128895581708376257523035831197732388269941032867210108, 42812769472257791163416752515046071662395464776539882065734420216, 85625538944515582326833505030092143324790929553079764131468840607, 171251077889031164653667010060184286649581859106159528262937681073, 342502155778062329307334020120368573299163718212319056525875362112, 685004311556124658614668040240737146598327436424638113051750724224, 1370008623112249317229336080481474293196654872849276226103501448448, 2740017246224498634458672160962948586393309745698552452207002896896, 5480034492448997268917344321925897172786619491397104904414005793914, 10960068984897994537834688643851794345573238982794209808828011587706, 21920137969795989075669377287703588691146477965588419617656023175412, 43840275939591978151338754575407177382292955931176839235312046350824, 87680551879183956302677509150814354764585911862353678470624092701691, 175361103758367912605355018301628709529171823724707356941248185403485, 350722207516735825210710036603257419058343647449414713882496370806824, 701444415033471650421420073206514838116687294898829427764992741613648, 1402888830066943300842840146413029676233374589797658855529985483227499, 2805777660133886601685680292826059352466749179595317711059970966454839, 5611555320267773203371360585652118704933498359190635422119941932909634, 11223110640535546406742721171304237409866996718381270844239883865819325, 22446221281071092813485442342608474819733993436762541688479767731638735, 44892442562142185626970884685216949639467986873525083376959535463277328, 89784885124284371253941769370433899278935973747050166753919070926554729, 179569770248568742507883538740867798557871947494100333507838141853109648, 359139540497137485015767077481735597115743894988200667015676283706219166, 718279080994274970031534154963471194231487789976401334031352567412438331, 1436558161988549940063068309926942388462975579952802668062705134824876530, 2873116323977099880126136619853884776925951159905605336125410269649753060, 5746232647954199760252273239707769553851902319811210672250820539299506381, 11492465295908399520504546479415539107703804639622421344501641078599012695, 22984930591816799041009092958831078215407609279244842689003282157198025444, 45969861183633598082018185917662156430815218558489685378006564314396050678, 91939722367267196164036371835324312861630437116979370756013128628792101318, 183879444734534392328072743670648625723260874233958741512026257257584202636, 367758889469068784656145487341297251446521748467917483024052514515168405272, 735517778938137569312290974682594502893043496935834966048105029030336810544, 1471035557876275138624581949365189005786086993871669932096210058060673621088, 2942071115752550277249163898730378011572173987743339864192420116121347242216, 5884142231505100554498327797460756023144347975486679728384840232242694484649, 11768284463010201108996655594921512046288695950973359456769680464485388969041, 23536568926020402217993311189843024092577391901946718913539360928970777938082, 47073137852040804435986622379686048185154783803893437827078721857941555876305, 94146275704081608871973244759372096370309567607786875654157443715883111752579, 188292551408163217743946489518744192740619135215573751308314887431766223505070, 376585102816326435487892979037488385481238270431147502616629774863532447010118, 753170205632652870975785958074976770962476540862295005233259549727064894020344, 1506340411265305741951571916149953541924953081724590010466519099454129788040580, 3012680822530611483903143832299907083849906163449180020933038198908259576081160, 6025361645061222967806287664599814167699812326898360041866076397816519152162452, 12050723290122445935612575329199628335399624653796720083732152795633038304324883, 24101446580244891871225150658399256670799249307593440167464305591266076608649853, 48202893160489783742450301316798513341598498615186880334928611182532153217299508, 96405786320979567484900602633597026683196997230373760669857222365064306434599262, 192811572641959134969801205267194053366393994460747521339714444730128612869198530, 385623145283918269939602410534388106732787988921495042679428889460257225738396863]
key = key[::-1]
def bits_to_bytes(bits):
byte_list = []
for i in range(0, len(bits), 8):
byte_list.append(int(''.join(map(str, bits[i:i+8])), 2))
return bytes(byte_list)
def dfs(sum, cur, res):
if sum > c:
return
if sum == c:
res = res.zfill(len(key))
m = list([int(x) for x in res])
flag = bits_to_bytes(m)
print(flag)
exit(0)
if cur >len(key):
return
dfs(sum + key[cur], cur + 1, '1' + res)
dfs(sum, cur + 1, '0' + res)
res = ''
dfs(0, 0, res)
#b'DASCTF{you_kn0w_b@ckpack_Crypt0?}\x00'EZshamir
题目描述
import os
from random import getrandbits
from hashlib import sha256, md5
from Crypto.Util.number import *
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from secret import flag
class Shamir:
def __init__(self, pbits, noise_bit, n, m):
self.pbits = pbits
self.noise_bit = noise_bit
self.n = n
self.m = m
self.p = getPrime(pbits)
P.<x> = PolynomialRing(Zmod(self.p))
self.poly = P([bytes_to_long(sha256(os.urandom(32)).digest()) for i in range(self.n)])
def sample(self):
t = getrandbits(self.pbits)
y = int(self.poly(t))
noise = getrandbits(noise_bit)
return (t, y | noise)
def get_msg(self):
res = []
for i in range(self.m):
res.append(self.sample())
return res
pbits = 400
noise_bit = 32
n = 100
m = 75
shamir = Shamir(pbits, noise_bit, n, m)
coefficient = shamir.poly()
key = "".join([str(i) for i in list(coefficient)[1:]])
key = md5(key.encode()).digest()
aes = AES.new(key = key, mode = AES.MODE_ECB)
ct = aes.encrypt(pad(flag, 16))
with open("data.txt", "w") as f:
f.write(str(shamir.p)+'\n')
f.write(str(shamir.get_msg())+'\n')
f.write(str(bytes_to_long(ct))+'\n')做题流程：
已知为
$$poly(x)=\sum_{i=0}^{99} a_ix^i\pmod{p}$$
给出的有75组$$(t,poly(t) | noise)$$
待求的是系数$a$
$$(a_0,a_1,\cdots,a_{99})\left[\begin{matrix} 1&1&1&\cdots&1\\ t_1&t_2& {t_3}& \cdots&{t_{75}}\\ {t_1}^2&{t_2}^2&{t_3}^2&\cdots&{t_{75}}^2\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ {t_1}^{99}&{t_2}^{99}&{t_3}^{99}&\cdots&{t_{75}}^{99}\\ \end{matrix}\right]+(noise_1,noise_2,\cdots,noise_{75})=(res_1,res_2,\cdots,res_{75})$$
其实就是$A_{1\times 100}X_{100\times 75}+noise_{1\times 75}=res_{1\times 75}\pmod{p}$
发现p为400位，a为256位，noise为32位，a和noise相对较小，用LWE
可以构造：
$$(a_0,a_1,\cdots,a_{99},1,k_1,k_2,\cdots,k_{75})L=(a_0,a_1,\cdots,a_{99},1,noise_1,noise_2,\cdots,noise_{75})$$
$$L=\begin{pmatrix} 1&&&&&&1&1&\cdots&1\\ &1&&&&&t_1&t_2&\cdots&t_{75}\\ &&1&&&&{t_1}^2&{t_2}^2&\cdots&{t_{75}}^{2}\\ &&&\ddots&&&\vdots&\vdots&\ddots&\vdots\\ &&&&&&{t_1}^{99}&{t_2}^{99}&\cdots&{t_{75}}^{99}\\ &&&&&1&-res_1&-res_2&\cdots&-res_{75}\\ &&&&&&p\\ &&&&&&&p\\ &&&&&&&&\ddots\\ &&&&&&&&&p \end{pmatrix}$$
配平后规约即可（需要flatter加速）
from Crypto.Util.number import *
from Crypto.Cipher import AES
from hashlib import *
from subprocess import check_output
from hashlib import sha256, md5
from sage.all import *
import os
def flatter(M):
# compile https://github.com/keeganryan/flatter and put it in $PATH
z = "[[" + "]\n[".join(" ".join(map(str, row)) for row in M) + "]]"
ret = check_output(["flatter"], input=z.encode())
from re import findall
return matrix(M.nrows(), M.ncols(), map(int, findall(b"-?\\d+", ret)))
pbits = 400
noise_bit = 32
n = 100
m = 75
with open('2024DAS/data.txt','r') as file:
f = file.read().split('\n')
p = int(f[0])
t, res = [i[0] for i in eval(f[1])], [i[1] for i in eval(f[1])]
cipher = int(f[2])
A = matrix([vector([1] * m)])
for i in range(1, n):
A = A.stack(vector([pow(x, i, p) for x in t]))
L = block_matrix(
[
[matrix.identity(n + 1), A.stack(matrix([-x for x in res]))],
[matrix.zero(m, n + 1), matrix.identity(m) * p]
]
)
temp = diagonal_matrix([1] * n + [2 ** 256] + [2 ** (256 - noise_bit)] * m)
L *= temp
L = flatter(L)
L /= temp
a = None
for index in L:
if (index[n] == 1):
a = vector(GF(p), index[:n])
break
if (index[n] == -1):
a = -vector(GF(p), index[:n])
break
key = "".join([str(i) for i in list(a)[1:]])
key = md5(key.encode()).digest()
aes = AES.new(key = key, mode = AES.MODE_ECB)
flag = aes.decrypt(long_to_bytes(cipher))
print(flag)
#DASCTF{3617af36-7869-6939-3a09-bb8038aea171}1z_RSA
题目描述：
from Crypto.Util.number import *
from sympy import *
import os
from secrets import flag
nbit =130
e = 3
l = getPrime(505)
m = bytes_to_long(flag + os.urandom(64))
assert len(flag) == 29
while True:
p, q = getPrime(nbit), getPrime(nbit)
PQ = int(str(p<<120)+str(q))
QP = int(str(q<<120)+str(p))
if isPrime(PQ) and isPrime(QP):
break
n = PQ * QP
PP = nextprime((PQ >> 190) * (QP & (2 ** 190 - 1)))
QQ = nextprime((QP >> 190) * (PQ & (2 ** 190 - 1)))
N = PP * QQ
M = pow(m,1,l)
c = pow(m,e,N)
print('n =', n)
print('M =', M)
print('l =', l)
print('c =', c)
'''
n = 18339446336492672809908730785358232636383625709800392830207979464962269419140428722248172110017576390002616004691759163126532392634394976712779777822451878822759056304050545622761060245812934467784888422790178920804822224673755691
M = 36208281423355218604990190624029584747447986456188203264389519699277658026754156377638444926063784368328407938562964768329134840563331354924365667733322
l = 56911058350450672322326236658556745353275014753768458552003425206272938093282425278193278997347671093622024933189270932102361261551908054703317369295189
c = 720286366572443009268610917990845759123049408295363966717060100862857351750759651979922104897091176824666482923148635058966589592286465060161271579501861264957611980854954664798904862706450723639237791023808177615189976108231923
'''做题流程：
$$PQ=p*2^{120}*10^{40}+q\\ QP=q*{2^{120}}*10^{40}+p\\ n=PQ*QP=(pq+2pq*2^{120}*10^{40}+pq*2^{240}*10^{80})\\ pq\approx260bit$$
根据实测，可以发现已经把$pq$的高250位，和低160位泄露，这不随便解$pq$。
仅有260位，扔进yafu，即可解出$p$,$q$
然后就可以求出$PP,QQ$,算出$N$
发现经典$e,\varphi(N)$不互素，nth_root直接秒了
from Crypto.Util.number import *
from sympy import *
import sympy.ntheory.modular as sp
import os
from sage.all import *
n = 18339446336492672809908730785358232636383625709800392830207979464962269419140428722248172110017576390002616004691759163126532392634394976712779777822451878822759056304050545622761060245812934467784888422790178920804822224673755691
c = 720286366572443009268610917990845759123049408295363966717060100862857351750759651979922104897091176824666482923148635058966589592286465060161271579501861264957611980854954664798904862706450723639237791023808177615189976108231923
choice = [78, 79, 80]
pq_low = n & (2 ** 157 - 1)
t = (bin(pq_low)[2:])
qes = t[:100]
pq_high = None
for len_choice in choice:
pq_high = n // 10 ** len_choice
if qes in bin(pq_high)[2:240]:
break
pq_high = bin(pq_high)[2:240]
pos = pq_high.find(qes)
print(int(pq_high[:pos] + t, 2)) #p*q
p = 855604426214387476576649090490109822073
q = 1213149261930568621267125437333569321667
PQ = int(str(p<<120)+str(q))
QP = int(str(q<<120)+str(p))
assert isPrime(PQ) and isPrime(QP)
PP = nextprime((PQ >> 190) * (QP & (2 ** 190 - 1)))
QQ = nextprime((QP >> 190) * (PQ & (2 ** 190 - 1)))
N = PP * QQ
F1 = Zmod(PP)
res1 = F1(c % PP).nth_root(3, all = True)
F2 = Zmod(QQ)
res2 = F2(c % QQ).nth_root(3, all = True)
for i in res1:
for j in res2:
N = [PP, QQ]
c = [int(i), int(j)]
m = sp.crt(N, c)[0]
flag = long_to_bytes(m)
if b'{' in flag:
print(flag)
#DASCTF{Ar3_Y0u_Su93_Abt139??}found
题目描述：
你现在来到了提瓦特大陆，能不能发现宝藏呢？
You have now arrived on the continent of Teyvat. Can you discover any treasures?
from Crypto.Util.number import *
from random import *
from secret import flag
from sympy import *
bits = 1024
l = 138833858362699289505402947409766595473722379891580589518174731439613184249727659678966809301611194545239974736175752769503863392697421092435438747741790652435801956708356186578269272819715592752821497122516109657809748674185639254430403157877064556216401002688452227124543508128414591884297632663910714681207
assert isPrime(l)
def generate_prime(bits):
return randprime(2**(bits-1), 2**bits)
def fun(data,y,n):
return sum([data[i] * pow(y,i,n) for i in range(len(data))]) % n
def gen(x, y, z, w, n):
data = [randint(n // 4, n) for _ in range(10)]
leak1 = pow(x + pow(y, z, n), w, n)
leak2 = fun(data, y, n)
return data, leak1, leak2
def encrypt(l,m,n):
mm = bin(m)[2:].zfill((m.bit_length() // 8 + 1) * 8)
length = len(mm)
c = []
s = []
for i in range(length):
a = randint(1, n)
s.append(pow(a, length, n))
for j in range(length):
c.append(pow(l,int(mm[j]),n) * s[j] % n)
return c
p, q = [generate_prime(bits) for _ in range(2)]
r = generate_prime(bits // 4)
n = p ** 2 * q * r
e1 = generate_prime(128)
e2 = generate_prime(128)
phi1 = p * (p - 1) * (q - 1) * (r - 1)
phi2 = (p - 1) * (p - 2) * (q - 2) * (r - 2)
d1 = inverse(e1, phi1)
d2 = inverse(e2, phi2)
t = getRandomRange(n // 4, n)
data, leak1, leak2 = gen(r, t, e1, d1, n)
m = bytes_to_long(flag)
c = encrypt(l, m, n)
with open('output.txt','w') as f:
f.write(f'n = {n}\n')
f.write(f'e1 = {e1}\n')
f.write(f'ed = {e2 * d2}\n')
f.write(f'data = {data}\n')
f.write(f'leak1 = {leak1}\n')
f.write(f'leak2 = {leak2}\n')
f.write(f'c = {c}')做题流程：
列个条件先
$$l\approx2^{1024}\\ p,q\approx2^{1024}\\ r\approx2^{256}\\ n=p^2qr\\ e_1,e_2\approx2^{128} \varphi(n_1)=p(p-1)(q-1)(r-1)\\ \varphi(n_2)=(p-1)(p-2)(q-2)(r-2)\\ e_1d_1\equiv1\pmod{\varphi(n_1)}\\ e_2d_2\equiv1\pmod{\varphi(n_2)}\\ {n\over 4}$$
给出了有$n,e_1,e_2d_2,data,leak_1,leak_2$
不难想到可以有：
$e_2d_2-1=k\varphi(n_2)=k'(p-1)$
那么根据欧拉定理可以推得：
$a^{k'(p-1)}\equiv1\pmod{p}\rightarrow a^{k'(p-1)}-1=k''p$
所以再用此和$n$进行GCD，即可求出$p$
再看到题目的加密部分，可以发现它的加密流程如下：
- 把m转为二进制字符串
- 生成一个元素形如$a^{len(m)}$的列表
- 对于每一比特位，如果当前比特位为0，则密文为${a_i}^{len(m)}$，否则为$l{a_i}^{len(m)}$
然后我们会发现$({l\over p})=-1$，$l$为$p$的二次非剩余；又因为$len(m)$为偶数，显然有${a_i^{len(m)}}^{(p-1)\over 2}={a_i}^{k(p-1)}\equiv 1\pmod{p}$，所以${a_i}^{len(m)}$为$p$的二次剩余。
所以我们根据此得知$l{a_i}^{len(m)}$为$p$的二次非剩余，${a_i}^{len(m)}$为$p$的二次剩余。所以能够轻松的分辨出比特位
from Crypto.Util.number import *
from gmpy2 import *
from sage.all import *
n = 214189098485907407681203562477141616514627803973812423866137712061520397412283304756125615530911730190509122275581663270324067756428063773995710185422014937638013530995658678484408224195008950739065869752467503449898424403807629035201754909341605483646512086652631108980705938767234014655512244203488129210213088484751842078315616338034946509581920246058635374657554442252420460618886159118637553788160140879059706396460523335509806462257352635091258764319929220939182156189941663585022210802535804264016891744621140144859992731921592420695928759275864955373537480452694672023754214092487216273962896544919015905264313446548396379618341043583032673900608611135254563997519445284222602183035105369017270389887769617942348731416370092842162632579589494341854993600540689280924183073089475208340685636482246115054414077320832052204722015428500812923185709772796221129375539131726373252482799298746655947376656143301849009181701495003174228813534439192414768762803822975277797520157025175837722175072241107
ed = 8238783462304466047370608758999664260116370123313022088538091162770601739116628806460542503654403361322931229200817491683096695046254053538710523477982774850621979868926682997393573131262930645387042545807254462907502249936746101134745335780459335767976492133149192198880107516742633966664923533160167069625322094242414191994000927842976472080411237834215691897822371792754587587715760051582955795834883174474583440371035173351136370107484245425758954400434828144460697864191261513214008084848001467959369934964428291290009392620134215667173457413630882523557102057539902909381706460767916715499306316003286608457624713509816056636249181986636842368337873445101552453774405927824096616431732124001038586048766823358751593885500314021939046991953062562270782883182855487098328026196086288533138907969729187779739950764344200364360079479047132746676799216491472345637845220255139152063453462176656553357596450484408472263570570448409671724853674399060252094955913831086556844240273178815236110565265190938731402297513542863173575371193878977
c =
p = GCD(pow(2, ed - 1, n) - 1, n)
flag = ''.join(['0' if ZZ(i).jacobi(p) == 1 else '1' for i in c])
print(long_to_bytes(int(flag, 2)))
#DASCTF{c764ba09-b2aa-12ed-ab17-9408ad39ce84}