Home N1CTF 2022 - Crypto
Post
Cancel

N1CTF 2022 - Crypto

Posted Nov 5, 2022 Updated Feb 26, 2023
By vnc1106
8 min read

ezdlp

Challenge overview

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

from Crypto.Util.number import *
from math import prod
from secret import flag

def keygen(pbits,kbits,k):
    p = getPrime(pbits)
    x = [getPrime(kbits + 1) for i in range(k)]
    y = prod(x)
    while 1:
        r = getPrime(pbits - kbits * k)
        q = 2 * y * r + 1
        if isPrime(q):
            return p*q, (p, q, r, x)

def encrypt(key, message):
    return pow(0x10001, message, key)

key = keygen(512, 24, 20)
flag = bytes_to_long(flag)
messages = [getPrime(flag.bit_length()) for i in range(47)] + [flag]
enc = [encrypt(key[0], message) for message in messages]

print(messages[:-1])
print(enc)

1
2

[12663746096003602034805550137868194720916906489657622295298194239094517182776571415625767646380772563193, 14132419026281300247821055412800131398930894216489258113904728404581538907301679419214447815004356250213, 11655428754671560771921463003911904370642761461141746853172776137663446218950185460123311583744244576651, 14437678697063990859655299315506460156072449476596814455497580042773427427201191616010438921219697566207, 15002874749915800226497487675982756978120590555038984559176137265082604998701016560366851521550375289619, 12200429000300054982769822088303708088147776935798495143123101000414999518256814919436691701219929977443, 12022028158932066252554600210953428074479648616693562203622365444081153755664547825203072727322619340391, 15326141484175696149121655412465633104078151316690977231668152920998359592830509503478074055112999574981, 14056771497651385035371546931678946327225541945352605439360765820739927703122904981469057904317776921263, 13627527116278874003582695444496282221231787451158428826309766728816516675463929802270425585235619637873, 9532386535492144267147831028913273489858437724880203373826043347568852523770420241749859385487406483979, 12105119318974808780726286054732236125970820406031457561069902254615102811695780762128818161404504498571, 17375473832716984207301483561766127121416492000960248004847175097439386482194277684885433842142485766979, 16554810021656773269015172383701694656984382699786774223957939352351900556944802452753429128313990996737, 15176915452575891079550629883578986339427556051613114385723386598491455091420380698285277882392147506173, 11806010168620746459109864194771894332952141161819393026586030536903429301218820465075218508304178337693, 10301071899683854933212873261118138833852167112586044571755364655196343466043810121544973678672008613803, 14166775554072964505385268662634177869100699819638306431597407356342551153097479752104518536035399939371, 10149638549982466694759374439977996929610044260455135782295224680189567726832086180314113209468279041757, 11781584892220250690574681563680940126762935519793655192784959502937368059247206358504250608454259891727, 15038928305561471041226064029963106243541545002574865065995806409790534237748546487849249858106550078231, 9580888622178339972260574652417101092469152244093773478970996513098265707736420799213172454323127622633, 16832519731577306391043658360018784702605792203422700389327004686532539689734917760321648488230888187721, 10867599307636425749899548870300113988038540052791923844000360343405148990662095113016671010590469235521, 17467115681041482108467932296242227024623105030257775065640719199713712198126072518920191142637850906683, 9273417146144052655615407700694821772909515142773572691972830367235325718875094311189518007289192669189, 16632824238934881411171218388021828930721084481281881679074243665187528749774173422168476107286651950721, 10581883242475329842566787060887333718055756499659396478793112531016759279124005692583324120011287554937, 17915505401279990026021751220853729828697276123216111805478995734037531915469950842915053859630212282669, 10782951127933994337893639031146049444366465583233074369169440143266558605440864932670063972448118770053, 10176756020954218340342729294765357250100532131670575581012530671423202386081022361061175199978931328671, 13658827352593547554221598195357688731028052333550989106789568768190119263114463407419978955533304562429, 14891712870731238492263819443444939062051933851768953568786715305574300162320426370160524102148144647341, 10385921231223717361217489427301590556224642053715247311910689044243066369482114225234839934781933387317, 17013409655721508165863397312465280020898749311014596585552718375774263478496723317784119730976514130473, 16986882920113484087693092000585103501548559643718025617656633308381676660630862412036186585506899774161, 11453352651216365241578914867406398737971509207465133323955060019598413539108767754962077278598322864301, 16755633786275870614857653299503803951700995626343095443892626619957330702430787078783721161855813805163, 15448657521962024971112157922187306191950692633208198318716657601508105720490330518613598428258399393999, 13445442344820784802664041567908665004819931321301423637095302391845536651285135635627140656111561505441, 9557468167801329362767525412300043569009743279963873824012642650395198714316574006341471079208144585967, 17098254197749431716632768896312100035386578636133269314483367740073947526081776782262947168490582199483, 16835407022333577513897329377457949073175792779993839585759661291470395273625057511614988721879320902427, 16306999806399827080235326712427101893348438406069647763492946439224757958791811990717080643111227201807, 13580334016425716627812690149777819923090303265405445549999854984914558569659989887973025065946663385157, 13110792710299272609698528958861611699151645629852258616789302701448426819110564884922775851490202636881, 14165423701777249263816463401081760426834162610596319073642833757104030978264487767967134870804656476289]
[57232608914198175109785709371300232177693855726597984936053900368555183181147336312895836187534080073427080654999615527778639368550840082346447311859780241331567239734555580467938250447225626069106101196513103259622377455430858622976701082331136388721125159472447812785142939993215201079156381454179231774978621, 119018622019252168934355440063416070353601068126795157593996773179308331829090813617846715074323709342886276077497762149186679801528162789221386514455479512683730420488200545921618210431980938300089161291644469992260008163539403051482736189309308446661006179700799915857633850683598284957540073230007864001007687, 6122163628062914171517341768803876718204225239795039176674815707292832652022824779820529176787981304153138541719456878186186204622264727458463951667567490266297270999694085051562030232607306260099357571419311953711317201937945632812425299150895404339807975311146159116266980933520593480837401136212447204108049, 28540414123410824174116871648980258694595184814510554181081596920388496284279412323405941240185964737191832645783356008854524037236288389256214745517114972018198837498973693612698538462787963569692770376251970527324079472545283749882989761108810944657299270896094407238648710873736756511689128494479553996569980, 67278930120416218881331446326848251697009804802460482086707926724916142606112769752677376855224039704540779071775615502924601665778596652537347982371095563171698757196325528893745482251006926923517931248138004165768769736874237648555305584043598268309988084995366843540992183241120300859132869831366331600710558, 100441125745454072827180775943684938314832119776801393398707172733554934663150253857204265229489246969289062535749135436558322252067664012937043065312761808726865341867434868750714642040389825289571661397788319344833736025265091503110460610697145217047563412817555970653508368515813966481892006317185835016451596, 15216117530042455399400804489826720273427315418739000010460816009280452996314747501422962977476242525449009860773153042079850388424528150860792687843182357662143003598943761328772890589193531750128029534007416927554961470396996998968754712117453852091512966620492890336420903174876176537738798246079795219745854, 118541309065015685856335846391033886567572688280488418106011358526392112399337378946425518000792132290816624302062971705513928029491812938656625783759873895027943910919262567277145905349608195128462056469713961540517667447151625332802836450303814775982440575824290593573150355925407077920563410787306702533205463, 128389881064636709419836763141515677495188380000146888480597348696945592678282670905925791343389121784046644286523689339199763106802825872989267651350937875209973619149021581029505933792860832895657339679214599201637317323656626462814144544301491824556559035411714532843566344523217819358896371943350639942459949, 34093856775781856551191147692508868666336509269856011110737357636215480841525445733330940087981829545127700802659540443440189524089943638275810382531930541835422545115011751274985231327701498777770819771076207589931619915169066258894847224146756480054695482898013102816123551733159333649898586559428557971850701, 81300851339401181812622971818456807765918449363627764350395250541212488081576716833807248879650649362171107666776341430534661723935291947760015791546044469452363961895420142561758463985262985214902182739623920284210707167192767526178841138011634179210631980347705048905526562571093675029106563005606342950051013, 81184744346790924098390626343061862533926196813436264423392782313183788824888005366960636464932666991679250036623225102844077245305279615789985297028151686367395487188181416047313913708495129221758772076767595640173439548175714389499004700598291317543926421962858976817846596643104360539905688568401039734718483, 26434131154005660208202418251350553299645786233494766029878297162082886997824532111995385786035751557354362898428335530451272701789617149071688592843246870280783453272275136306294400300985731992703683476375688305074195262278872080404088938102904111143101067942664642550110639626664123760598968951181617689902541, 20583461169361164936012239952506086042941935876382559469522600586017850800344765779998955301922686194592613728117977392668857817500652927316170071259763189098650100319355732975236340932783385931830714959967369110831948835561327035695862957210809046317597465402541788054523440985447601668375174517972307420752222, 99534127272271736561819944763606095922497555550678291381059549633615143166598789208945263137876687923783077645427746546609553288013773320686523582406074630183160062915395771686193917033832627369751874816677354435908597099043633357467600006811423136496389263128632570405208493745830930161893550082268510553243436, 118512116206510628620173620535467344051381976286214661348788449888449951031872461765117206926632677694087945546315408145619615151832782942014233116281935093137585570386446879683134361566600024471557481076162998555307020705103001626351022137545564104344410566269738892608918426693130348185415804993793721209609921, 39696874135154683267112097021680040753243138159093000082671302585498437603319904894403312138376713524983452218540365741436497014252623022059517764732201708697832675412789710043016297658647765241931376357562085304351217443979514385699767267553378445677211510486519988739144271419362000197607483106320082211157894, 25615713579794183863442485192387430658723428296464586587898591117935830443598276803565696400498331135396182162761634590925312795732761646132215168836455602406883764926399157309533193399134550418083687077959980816090474500772169035534758695041065067455682003512957204985608587710672977761801979298600719822016047, 23793209649566114665504267496369174053459786578228840738712746160813356913085291840670926485938467021921249748937163453045493268190727694834746331675450612307162991196358494672951680343821853030212625697896822806418811182729559057694617576595345840050914186351202035936407830993232414495830287089643357113630503, 84900868031750701719170495739268701340448411132522906627713496129145064055990332922002486194735907569742410314242506161002441004555229668928980128799296166340146123428623689620142768423244946548591211248837198305592226407665478362906541272913507633212921149441249303673799120352922183629944134036918567534983647, 64854743778344461573875505197765202610602120089852481429093133918839065327096609472074901493597943717665732351345476707313576146260579823636441977310462506242356225915419035285099759708938797787590056266006186272630085683224747473152107252181715962546230577202193544842264175396407294764016400072051626879823666, 43786460809814877850055135457752884384516501548292829314979687937607951889102449353983106504856286698338120117264846883578454109760559338097644845777254246143813247771973297517920813642987087609503855062297041188130113307877018724419913492364040334823999299826485220355118533227105208525871102164850743592197880, 18410848816279000082865665087967308434683881846057587302207644885782121929540614117218622845465184222863920784374706231486900135399669880462420214078693028046048021435260904923927365018413834214333078986702654848677487103752777924965608975606985449643730404332158705821979821026927627232457593514769409557857794, 37528795642427381026743303290555251064602380591515328584173853460474597557188114837322912676348557014234144738972886931444325218088188023630647534035725264163124845482521689580289083806870704489342225504049591490404844227836527733261384542641712205218746355586140270679557466938414940696629906671790333847339100, 120184174837129922978041761049752494349805405363915733328766090037154677842877770589616516870003359227784292556831725911705007653205940334469000068369577478846709121385821095258347556939153698007282502763909940256677799743506174272974157274102970394457871359832172736455842603413137518696350897940124898715264328, 85114042547376870094991062686681561109370712951526036710890642223255504371925133357863720777505794177722019923294054968209724320983289575941774562335331869126256931667309246608290713579479837728662330515334593645923196813941733211556279847804080648269475904763815679632829504041349748084243435407170116086099571, 85664036841997000249918266611625095874187200068219663599240259437252325179648759068399867768105884800411762830251668911635511387529518068874630535460984056737847815294298413093595113435496939074803361947656093885514112089591812880957906107416384430811199239381641849560512236254320481734660943314397466382518670, 19868151443713684033326315419488805314642951421071058037081518185917142386124119384204580739191353408815653188976676798334838959292276152979270636624021744528913109029922119160800340250667168104047373320086805282333539262671835560171422052545510197952709359772287020357635465074316209873689272267323257955153323, 51029267901687836725907965568430647221250571180244643611425953900542586039831128405596005089082767047574164924899010105416329727934881100139413736187064637473224707121868210639131044204973756282046850557215004436827715093816988545799405346151923231447395532258095016482637754870243670358652069698049268883589124, 88034211107477606037608516993038006849109216205386189419249337698181850592850024345069840216575652166713813867810010665618768531718281563277119288198903566342692567184172362056718934854721638856943432002177665039289279569277329521972446746782839371702287518786028884532536089431813622499739059673650919651503327, 34290724215292206898895850910853573969604203610446796482457188079779084234166755672139575160998526644200788650835348904310076192206731369137747137479474593487141698098918402805229456473832106349331555085747621113162720499571078980178142378770306917802125052880993548469701984751330079122660792309621426541588076, 90927188279218437043454554956642015346713372562371359261616779706538939681408456355974513604735454447880695728673117860551338566945192506092751947158505621256166944871575026077958544804376039892815849827345907923264667687859857788352006910436664478067757651891635634923727530789609690792776873591562573033390634, 53732343203006760442398433872134781295830656980276609591138146207626163562517843649120913243776843334107106691749493938619111007479062412456809500791493383632196471953312152159801577623906430605844235078132185853920208052494745920119335711435221738446984963476234515199656235009292715443135922168345909287531773, 49031927534145883184926164295828977811711469424781078012610739070444671584077746477613031478660697183975633421868019649807499312667206591889141783516733744766298933391910692474266962004086039942805103040216748384407579306341588913664371259037264104088526364892368819697446167356277559716864693012958967681100260, 30963093465814372302516642776466055177417508152527408097213764844911320991146439597064292750638894222728431395063768524250417428928630674742251008274743494898189847494654965058948152674638339661926080272873883532044920176841760857878305035802233007949695617087173051988751329551256926898662442540254844991028514, 38910112932907768300302033715233195117875021511365865825041254667079681402773472898691511153844674335901286966993706447991762641623427579348204449246293604501210799161052618900641298875451688446687090763591699182741091728011538059864656433159402170621985800117954635372431554313743158156450491482836596392698540, 38443585562211316355274911393358256761473644112925764889560030180611756915515144544478860742103854890487528907562890898220560352513541741776265949250582845223992532020273016857208957223972389401808992966177007678770950599391794859006751879990019132124290539952279226068978275232584696063868776228658398019508687, 68550545600754879458876198377420845829320975904563551687242682944061564106671329644108261571744526116101799247679080797784186089149212343674697695440503566377158992929812917026042984952900100484829086299001655020193931835567043420882168129444729139288226492289343177679790267321958684637995637195757642488407276, 14035877123755570541439737876187097058990065301274722507585166336666626066786310262014548146436251719506889507596006387639929786023894491544460425397241776709067116382427351107782288254085502357976399257409284873091313992760783124271797334837519629008018411961593376262210281164953819570277107742944093278192891, 84973935660270819758814233083142240710785309884502607538970282884173754299778363893310221726403783947387743415857505995412132704938765096035328014089802283590788326117498458965239857137170690424984064818395940808347999385981549657227261498421032954560304304123396784276562818279812166711176719165057986653655269, 127652767021260495264466818414737386226807627335092643140999814315165072776677100093295944121947491864703175075802550400479697578962892452948470076586765670039963843210663006398013035858021917292520141025024089841431675871893235220229330118710120234682740731230605781585933497507868222142730438320650171223860410, 10820660907713821060756049660148560389325280624093461093810612541407581846537858936018021071684134263919140572079037344255372562710590250975822332043248751602294057721687638216684660439386848864418110118512208174355768432871226086246312894904364514743506427898091247247420131030953043354451982106624371303476576, 22509117536200148044923857446175408893075911404191032333097026503103010276105955757884180889706600230561199133331513880035633926105853975206764813984995520499767942092693844323122983122419315389669151529120786805203317761028263320034762418835415040762546573582987418970210522622738218431543314964785802667587831, 17110527541362531877473330877601602495160188646106725957393956572731745660242627602027036247078158084197564066866793058830963123952529593790431750896935886096261794752083336388036458068396262377010283577634659205378999555399253008352426584270580993143755095742288863170042056511437561276980640231653447089696471, 61348969566002296992170896072625129282323865986171588065667375012252011568769255349045185267959292869829157950934447113661709763529293480980845035985257633760151897807384916925942496992692306256026272824777993338140456567783548738678972934778493803536774329693410845609652017903413643751788619405927638767324811, 22510200266842330474614868643482821984644884364293177816481436665684674092037143647321900145327127043489514908412852947132346581389833878070779594530084319995806315545603004624097888294152486960640012202384261073555560735843725251439470919050946837207965392746584707716070872006144735413123120629275998839207636, 50720056568644721066647792700132746371519628076501379437908002312608804539261649596142852235153482308383208999791237037363767518135800305446886547979409480500284980037243584682485311702605225147297356529617446995741990013066746514569978566927909505486404585512297997162119969692237951781374377056093090642010097, 91561944814950778736488535643520052714900101756544637483800925876319855838327993556442983654484996766433049736153189800056457912285338408230393372558184963346036063617106521919740962726456954911219888157214487326900658606650604294547947205051640436119495039170478782141363198165616660075024383933961325219072058]

Đầu tiên đề generate $1024-bits$ modulo $N$ dùng nó để encrypt message $m$ bất kỳ như sau

\[c = 65537^{m} \pmod{N}\]

Ở đây đề không cho ta biết $N$, thay vào đó là $47$ cặp $(m_{i}, c_{i}), i=\overline{1, 47}$ và giá trị $c$ (là encrypted của flag)

Recover N

Đầu tiên ta cần tìm các khôi phục $N$, rõ ràng

\[N = \gcd\left(c_{i} - 65537^{m_{i}}, c_{j} - 65537^{m_{j}}\right), \text{ với } i \neq j\]

Nhưng vì các giá trị $m_{i}$ khá lớn nên không thể tính chính xác lũy thừa được (giả sử việc tính $65537^{e}$ là “khả thi” khi $e \sim 20$ bits). Mà đề lại cho ta “tận” $47$ cặp giá trị nên ta thử nghĩ cách sử dụng hết giả thuyết xem sao

Mọi người còn nhớ RSA Common Modulus Attack chứ?

\[\begin{cases} m^{e_{1}} = c_{1} \pmod{n} \\ m^{e_{2}} = c_{2} \pmod{n} \end{cases} \quad \xrightarrow{\text{xgcd}} \quad m = m^{ue_{1} + ve_{1}} = \left(c_{1}\right)^{u} \times \left(c_{2}\right)^{v} \pmod{n}\]

Ở bài này ta cũng sẽ thực hiện “tương tự” kỹ thuật trên, bằng cách, giả sử, ta tìm ra 2 bộ

\[\left(x_{i}\right)_{i=1}^{47} < 2^{20} \text{ và } \left(y_{i}\right)_{i=1}^{47} < 2^{20}\]

sao cho

\[\sum_{n=1}^{47} x_{i} \times m_{i} = X < 2^{20} \text{ và } \sum_{n=1}^{47} y_{i} \times m_{i} = Y < 2^{20}\]

khi đó việc tính các giá trị lũy thừa mũ $x_{i}, y_{i}, X, Y$ sẽ trở nên “khả thi” và lúc này $N$ được tính bằng

\[N || \gcd\left(65537^{X} - \prod_{n=1}^{47} c_{i}^{x_{i}}, 65537^{Y} - \prod_{n=1}^{47} c_{i}^{y_{i}}\right)\]

tìm càng nhiều bộ thì tính $gcd$ sẽ cho kết quá càng đúng với $N$ (dừng khi kết quả $gcd$ là $1024-bits$) Vấn đề là làm sao tính các bộ \(\left(x_{i}\right)_{i=1}^{47}, \left(y_{i}\right)_{i=1}^{47}\) đây??? Lattice hoy ~~

Xét ma trận cơ sở:

\[B = \begin{bmatrix} &m_{1} &1 &0 &\cdots &0 \\ &m_{2} &0 &1 &\cdots &0 \\ &\cdots &\cdots &\cdots &\cdots &\cdots \\ &m_{47} &0 &0 &\cdots &1 \end{bmatrix}\]

Áp dụng LLL Algorithm vào ma trận $B$ ta tìm được ma trận rút gọn $L$ mà ở đó, mỗi dòng chính là các giá trị

\[\left[X, x_{1}, \cdots, x_{47}\right]\]

cần tìm

Factorize N

Để ý hàm genkey

1
2
3
4
5
6
7
8
9

def keygen(pbits,kbits,k):
    p = getPrime(pbits)
    x = [getPrime(kbits + 1) for i in range(k)]
    y = prod(x)
    while 1:
        r = getPrime(pbits - kbits * k)
        q = 2 * y * r + 1
        if isPrime(q):
            return p*q, (p, q, r, x)

ta thấy $N$ là tích $2$ số nguyên tố, trong đó có $1$ số, giả sử là $p$, mà $p - 1$ smooth, tức là các ước của $p - 1$ là nhỏ (ở đây làm tầm $25 - bits$). Theo lý thuyết có thể dùng Pollard’s p - 1 algorithm nhưng vì $2^{25}$ cũng khá lớn nên mình dùng tool ecm nó dùng thuật toán semi-smooth chạy khá nhanh.

1
2
3
4
5
6
7
8
9
10
11
12

> vnc1106@DESKTOP-ISQ360E:~$ ecm -pm1 33554432
GMP-ECM 7.0.4 [configured with GMP 6.2.1, --enable-asm-redc] [P-1]
131158523227880830085100826212925738665356578827561846263073537503153187073136528966506785633847097997799377037969243883439723340886038624250936927221630287086602285835045356221763554989140952262353930420392663280482277832613695689454662506372252641564106136178637816827646124189347219273164844809807934422046441
Input number is 131158523227880830085100826212925738665356578827561846263073537503153187073136528966506785633847097997799377037969243883439723340886038624250936927221630287086602285835045356221763554989140952262353930420392663280482277832613695689454662506372252641564106136178637816827646124189347219273164844809807934422046441 (312 digits)
Using B1=33554432, B2=756274683742, polynomial x^1, x0=865343170
Step 1 took 14147ms
Step 2 took 4665ms
********** Factor found in step 2: 12980311456459934558628309999285260982188754011593109633858685687007370476504059552729490523256867881534711749584157463076269599380216374688443704196597025947
Found prime factor of 158 digits: 12980311456459934558628309999285260982188754011593109633858685687007370476504059552729490523256867881534711749584157463076269599380216374688443704196597025947
Prime cofactor 10104420349837363561278745998119091841853342383118385156657416134976061697027571349895988817770681767227605656666215380267313369652920490697343475330713803 has 155 digits
Report your potential champion to Paul Zimmermann <zimmerma@loria.fr>
(see http://www.loria.fr/~zimmerma/records/Pminus1.html)

Solution

Full solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

from sage.all import *
from Crypto.Util.number import *
from factordb.factordb import *

def calckN(MSGs, ENCs, iters=20):
    # build basis
    n = len(MSGs)
    M = matrix(n, 1, MSGs).augment(identity_matrix(n))
    L = M.LLL()

    kN = []
    for _ in range(iters):
        row = L[_]
        X, xs = row[0], row[1:]

        # 65537**X = PROD(ci^xi)
        if X < 0:
            lhs, rhs = 1, pow(65537, -X)
        else:
            lhs, rhs = pow(65537, X), 1

        for x, c in zip(xs, ENCs):
            if x < 0: lhs *= pow(c, -x)
            else: rhs *= pow(c, x)
        
        kN.append(lhs - rhs)
    
    return kN

if __name__ == '__main__':
    with open('output.txt', 'r') as f:
        lines = f.readlines()
        MSGs = [int(num) for num in lines[0][1:-2].split(', ')]
        ENCs = [int(num) for num in lines[1][1:-1].split(', ')]

    kN = calckN(MSGs, ENCs[:-1])

    # remove trivial factor
    f = FactorDB(gcd(kN)); f.connect()
    N = f.get_factor_list()[-1]
    # print(N)
    # 131158523227880830085100826212925738665356578827561846263073537503153187073136528966506785633847097997799377037969243883439723340886038624250936927221630287086602285835045356221763554989140952262353930420392663280482277832613695689454662506372252641564106136178637816827646124189347219273164844809807934422046441

    # using ecm factor
    p = 12980311456459934558628309999285260982188754011593109633858685687007370476504059552729490523256867881534711749584157463076269599380216374688443704196597025947
    q = N//p
    assert isPrime(p) and isPrime(q)

    c = ENCs[-1]
    F = GF(p)
    m = discrete_log(F(c), F(65537))
    print(long_to_bytes(int(m)))

Flag:
n1ctf{1f1b18f9-8523-4584-a8eb-c8b5c9c9433d}

babyecc

Challenge overview

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

from Crypto.Util.number import *
from secret import flag

m = Integer(int.from_bytes(flag, 'big'))

for _ in range(7):
    p = getPrime(512)
    q = getPrime(512)
    n = p * q
    while 1:
        try:
            a = randint(0,n)
            b = randint(0,n)
            Ep = EllipticCurve(GF(p), [a,b])
            Gp = Ep.lift_x(m) * 2
            Eq = EllipticCurve(GF(q), [a,b])
            Gq = Eq.lift_x(m) * 2
            y = crt([int(Gp[1]),int(Gq[1])],[p,q])
            break
        except Exception as err:
            pass
    print(n, a, b, y)

1
2
3
4
5
6
7

172294871449219734798107561390050953188521804048922822821089133469311203282838373380377875439026704763161795744755842077098168865000919622849058673563093367982208461406754463061486548381031910500664522644112851433538900220678158500614358889303283424512500613989230182706150280378108198120547975067586971516137 96364198848848705158285537079110423277195642567952259110364340716064235491391751428297894031158531380770390132279773351908864500464136898214435682124920058680787844361038830281655403525413688733800204992965035715298006768830075744486662160034641936095862260725417156381782604284050422013822430528431227361197 159671991296677830056301471254363341009296510275785264872785778012113694456980363802313449256308519721141732376201460773400245993593482589976204166133901861729668851862460623196007194950257183079347864250025089670843915918257755173390253034175544519724905752818035812997127673241875836037243219829705927834235 12488950718303582218034044014469231718831962762275496002247643231013156969740771432142283441219754679322796472657777272189002660471344265360278317729760143808888761286079001687689905847842340334026140684913862478238950679283842053262939984135114755914484999538131508882930756717834516619580846526035684240079
68223999778327454147340278776103578457271553299042143933393545815264609973076698756926443268448068478170652356574414692081569784751387548589991131379073395697581788909441130777261041802381911726085217610218552072019955091687392945670505312431379412346500975722411035854097380678429943612541679085918327184211 17770738203348676394013528065573927253738684355484382993047842078725009503696773096846474265836623641852326745278003624730438619552362071702422399552544609521188676816688215350418290389310564969049643786010837155281593524360805215661135722530433990410365868360692605842180028752038342347560333735922237369889 51098779961961751158122915158869440252746637314825788279336277128573162559246638101764647720433607480890890353266404408862366250798238531789338353122957455620883022785518154730850781795813200407904530871476660815008994170944440212300679621717029986782069464962522083711578039350861054405841275173019925642093 66166716533207612504484627791108393201158937155973610986551130733271280578971089095120371889664007733286220189256643852916722857958108530989447774212301117302384387307543583321894175828438280849870887046734108846642477438172082973113653660108354098554353657568190553303062608249271483295596847725316287446947
69746411945288680494756625186262685100915769718266292828317232438356233082561457717802913380129463210508761458218383450347346543878887508111863823958801568318184343480949172473544777648327814945820830887234292193752526478863127665281603760310028685488010810374501002997654985226277837410385612336235789850487 35863433752003593718423506765770617029528142232119703360783695175632253222988642577448933602236360173888236658825392990787632391883856639629797550839027484460834276938254229716767734096212580735483050576113358898294845949901713373921320977266743302353193505619551975822052525104591593619094885194563759053232 61506888586914853748952584136999168853842713393989804770066310267385965404827751126077340386083884094392293257188958096424196079983180753698925334131753282172406136172626322186930421581433234090454842658630759776836012464473239198489670974246600345527623012180678219362862337775047849600595500703273175382703 23074173610330067975119318094549104916729459916683840171011959880097244030586124074672098644510552431454003148712810460842866906744010629559390690271268680358736511730336715376566599109974114862237643003353529058235474898207867615210853332379567542323247567216796697852808056755511484166810776261406177054777
141780415980139617437215295846801567101402173619252056827987183835073254193657239443065408850513736462591151306400635298582358011825422183971334048391966413113755453698068836508230018713283240471925059428429812726435729369274579669831159812818547912726106821393226089324568082296082476059592963374588189677903 138746424736113892630456472492513519297466193136237748713651792342224061188757613931171106142936354280921317637536324608330692729231708881940151586955111567707002290198592160272885704125491274615556183787626484145861344784010051348839767532854926101536139055358860932766313079790639566311374298333660022416019 51726115599556454603920201657250521837735902629404616832316825062102322966835183071269936236690928753491837133603376577256803231041384630057026503126306733001505942744679790303330123718230247169888465167921020819210505089269412155033260560735554086852090518639465729269946494965164436190741639956526409236643 109654409762022740069514851260972908347716034747536569205325610944369939818174396230317316392277341065510361034050535743153611162427943916414124861678979771914963184421776448698855312979564147449272690263825911213298037101520123605413049352651130798112394668303713018564867048267647962314886530354112656660927
134695529317631291539146989750080778456288116909537330643076226015019499585100645219201149819193483942761047608937632376000045678037096949063251694636264176978864350498001325274216745015187611426633155307352514688833306265311483797036137536737138146820693626589997367590775993967122039778179174477656098285151 5739321199968321627369946084893217618156071099515645889496757563432120794798492968096997315087609783917559636235489259519655394193193715753364023338741839200775528051686566670968651457520145892918236829346679247967821973265175306801170339421046331421835781903320059400232340368113764816537593043564619129091 19673160600783884558420797494268753813890359647736289572838063131711269874000492472573124412257756881986515876284947639879236228461164246881762817017531477201318279812271247605969526804283198993102225186731231831294213792057134691470071907311239898997202853181993775441584378767147396666275272938837258357423 16897173108120076789922861933836017988034034913979337434078332952051799507194042012051980050429727113676699771772883294665409080790164523153924333774353032403848045609407735317482100956730663470698029136912240237112767052198706217408124644467054727063902614284435035076029952831418531957452256906889271788660
108631997335203066432695467871764765359535346338288176017618709868611883736328359105943651466896885704753893021031355220198313022607240746637026558990572053372001779938093596718948899761553876823305187704800253652009189892280549587130446638129290899670752310731109594745013563422110453795138476510927065537819 53186625650395498513439276601148324935331371411190607911833993964075202667438243234505710009859940105805328184291501428682891944699728069011511208448749132382024172290085402121472873185791975075398049469908097240414598661986593060452061227701643807521128142747260925759613091495839896971643248717676885197644 52709509084184104167650277788945043330126097533959255658173397630643774367938336071212214281041856314502929120225540280940224731284318314188334401609349175298441766962844025460361899368481713758076026229654035313132750449381123295594073954550981806651354410007449428669257683889916088487170632832744327614463 100260604505216418319923489428146996468156773172005794829064325549637959539041791314163531463726947409321908377241081956519122122262033227578640846072409813184989637914837945813897560451295053865278594114754492413312832734981399784589146893658856979887630033309457853967429746353718137461785133619446282493126
107338361645955025621587108367500347348984102219339572552748381028739611029946302714920823684765311935547487453509535204574142858361737866739285841603885839441733030101476343149903190982542554096941815202891147725076023628145124709929620451309674856615713933442851718371615889591966077523086598769484929332367 100872379615239890056528793994805290254429184626178615179949021889055871474237228059318594996850343091819482928969268211528584474928620075395005093777657472616646086984808630643337673511907312828907027299569420774094158785966357193601409625830742669863851550399504009908003166662860318527135193218238780676800 52637469044026090728662077516653409825725186092147185410215323273449329656983845536711234923756687817513771235055035977388966611329613167758082577958758423429648769821507972676781188078791048118663252233256924489724994317727922287107822238963194994782575166160292521918653409858431855957865223409101119244152 57971958593516466763891620734062821771076712450708456876484562483981622035231519724366540336500884101001407519929342324257929081898526022577405465205118192907601214300359691638071300661277784420068767639904239138656962018735555155063349452232501292852176876546222413194770858197241287367089881969293760207489

Đề cho ta giá trị tham số của $7$ curve có dạng

\[(E_{i}): y^{2} = x^{3} + a_{i}x + b_{i}, \quad \forall (x, y) \in \mathbb{Z}_{n_{i}}^{2}\]

ngoài ra ta được biết thêm tọa độ $y_{i}$ là giá trị

\[\left(2 \times G_{i}\right).y \text{ với } G_{i} = E_{i}.\text{lift_x(m)}\]

trong đó $m$ là flag cần tìm. Như vậy với mỗi bộ $(n_{i}, a_{i}, b_{i}, y_{i})$ ta sẽ thiết lặp 1 đẳng thức liên hệ với $m$ như sau, giả sử $G_{i} = E_{i}.\text{lift_x(m)} = \left(m, t_{i}\right)$ và $2 \times G_{i} = \left(x_{i}, y_{i}\right)$ khi đó theo công thức nhân đôi thì

\[\begin{cases} x_{i} = \lambda^{2} - 2m \\ y_{i} = \lambda(m - x_{i}) - t_{i} \end{cases} \tag{1}\]

với $\lambda = \dfrac{3m^{2} + a_{i}}{2t_{i}}$ và $t_{i}^{2} = m^{3} + a_{i}m + b_{i}$ ta thay vào $(1)$, được

\[x_{i} = \lambda^{2} - 2m = \left(\dfrac{3m^{2} + a_{i}}{2t_{i}}\right)^{2} -2m = \dfrac{\left(3m^{2} + a_{i}\right)^{2}}{4(m^{3} + a_{i}m + b_{i})} - 2m\]

như vậy ta đã biểu diễn được $x_{i}$ theo m, việc còn lại là thế vào phương trình

\[y_{i}^{2} = x_{i}^{3} + a_{i}x_{i} + b_{i}\]

cuối cùng ta thu được đa thức nhận $m$ là nghiệm:

\[f_{i}(m) = \left(v_{i} - 2mu_{i}\right)^{3} + a_{i}\left(u_{i}^{2}v_{i} - 2mu_{i}^{3}\right) + b_{i}u_{i}^{3} - u_{i}^{3}y_{i}^{2}\]

trong đó

\[\begin{cases} u_{i} = 4\left(m^{3} + a_{i}m + b_{i}\right) \\ v_{i} = \left(3m^{2} + a_{i}\right)^{2} \end{cases}\]

Như vậy từ $7$ bộ output $(n_{i}, a_{i}, b_{i}, y_{i})$ của đề cho, ta thu được $7$ đa thức \(f_{i} \in \mathbb{Z}_{n_{i}}\) nhận $m$ làm nghiệm. Câu hỏi đặt ra lúc này là làm sao tìm được $m$ từ $7$ phương trình trên? Liệu $1$ là đủ để tìm $m$?

Quan sát thật kĩ ta thấy các đa thức ở đây đều có bậc là $12$ (khá bé) nên ta nghĩ tới việc dùng coppersmith tuy nhiên nếu cứ dùng riêng lẽ cho từng đa thức như thế thì không ổn, cần phải tìm tìm $1$ đa thức tổng quát, “bao trùm” cả $7$ thằng $f_{i}$ luôn, tức là tìm $F(m)$ sao cho

\[\begin{cases} F(m) &\equiv f_{1}(m) \pmod{n_{1}} \\ F(m) &\equiv f_{2}(m) \pmod{n_{2}} \\ &\vdots \\ F(m) &\equiv f_{7}(m) \pmod{n_{7}} \end{cases}\]

Đọc tới đây chắc mọi người hiểu ý đồ của mình rồi chứ, CRT =))

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

from sage.all import *
from Crypto.Util.number import *

def getPols(params):
    Pols = []
    for [n, a, b, y] in params:
        Px = PolynomialRing(Zmod(n), "x"); x = Px.gen()
        u = 4*(x**3 + a*x + b)
        v = (3*x**2+a)**2
        f =  (v - 2*x*u)**3 + a*(u**2*v - 2*x*u**3) + b*u**3 - u**3*y**2
        Pols.append(f.monic().change_ring(ZZ))
    
    return Pols

if __name__ == '__main__':
    params = []
    with open("output.txt", "r") as f:
        for line in f.readlines():
            n, a, b, y = [ZZ(num) for num in line.strip().split(" ")]
            params.append([n, a, b, y])
    
    Pols = getPols(params)
    Ns = [param[0] for param in params]
    Fm = crt(Pols, Ns).change_ring(Zmod(prod(Ns)))

    m = Fm.small_roots(X = 2**400, epsilon = 1/40,beta = 4/7)[0]
    flag = long_to_bytes(int(m))
    print(flag)

Flag:
n1ctf{7140f171-5fb5-484d-92f4-9f7ba02c33d0}

CTF WriteUps, Crypto
Lattice Factorization EllipticCurve PolyCRT Coppersmith
This post is licensed under CC BY 4.0 by the author.
Recently Updated
Contents