RSA Buffet

[tiwanari]

Here's 5 encrypted files, and 10 RSA keys that they might have been encrypted with. (See encrypter.py for details of the encryption format.) Decrypt any 3 files, and recover the key from the secret share!

rsa-buffet.tar.bz2

[tiwanari]

入ってるkeyはパブリックキー🔑

[uedadaiki]

generate-plaintexts.py

# pip install secretsharing
# https://github.com/blockstack/secret-sharing
from secretsharing import PlaintextToHexSecretSharer as SS

with open('message1.txt', 'r') as f:
  PLAINTEXTS = [f.read()] * 5

for i in range(2, 6):
  with open('message' + str(i) + '.txt', 'r') as f:
    msg = f.read()
  shares = SS.split_secret(msg, i, 5)
  for j in range(5):
    PLAINTEXTS[j] += shares[j] + '\n'

for j in range(5):
  with open('plaintext-' + str(j+1) + '.txt', 'w') as f:
    f.write(PLAINTEXTS[j])

massage1.txtから各行をPLAINTEXTSに読み込み massage2.txt〜massage5.txtを秘密分散法によって分散させて、それぞれをPLAINTEXTSの後ろにくっつけてplaintext-1.txt〜plaintext-5に書き込み

秘密分散法について http://ohta-lab.jp/users/mitsugu/research/SSS/main.html

問題文から、5個中3個復号できればいいみたいなのでk=3, n=5

[cks-coil]

key-3.pemだけおかしい 他とファイルサイズ違うし、opensslコマンドで中身見たときのexponentが過剰にでかい(ほかはよくある65537) Wiener's Attackなるものが使えるらしいぞい!

https://www.slideshare.net/sonickun/rsa-n-ssmjp

[cks-coil]

"RSA Buffet" という名前から考えるに、10個のpubキーに3つ脆弱性のある奴が含まれていて、それぞれ明らかにすれば解ける的な奴ではないでしょうか?

[tiwanari]

その方針で攻めて見ますか〜 5個中3個解けばいいというのは優しさなのか意地悪なのか疑い始めてる笑

[tiwanari]

@cks-coil さんの言うことに従って，この記事参考に http://elliptic-shiho.hatenablog.com/entry/2015/12/18/205804

[tiwanari]

[ tatsuya@tatsuyas-MBP ] rsa_buffet# python key3.py
e: 228667357288918039245378693853585657521675864952652022596906774862933762099300789254749604425410946822615083373857144528433260602296227303503891476899519658402024054958055003935382417495158976039669297102085384069060239103495133686397751308534862740272246002793830176686556622100583797028989159199545629609021240950860918369384255679720982737996963877876422696229673990362117541638946439467137750365479594663480748942805548680674029992842755607231111749435902398183446860414264511210472086370327093252168733191324465379223167108867795127182838092986436559312004954839317032041477453391803727162991479936070518984824373880381139279500094875244634092093215146125326800209962084766610206048422344237134106891516381979347888453395909395872511361844386280383251556028219600028715738105327585286564058975370316649206938752448895524147428799966328319661372247669163998623995646371176483786757036960204837994662752770358964913870689131473714797550537422931003343433377469029232185552979648755665051117443571002017829146470221483652014417043043920340602378994630507647460734411326405049128160906832664174206633659153486878241903912874200129515570971220983561054906106575556061388168231915057339795246395626504771079756241685975773086049021119
n: 625370676793301609007636145380331611237919351425496690404114180302249419719867435237342547950459491394834137179033102621573611784738388518952362848787237787440594300323769334356435131992521522997795029079251912507591819194229112877831181987001350385569134107880067429777572352378951587000987749447829255561035861423897841083194636994924140527822677164175006590642236546332030533920247393734145161727026178314748349757632676858997648848951518713836001935694487214337663667186794458714595706552931844195313593265852623091839910783970211228963728395962479544383117833611165858148867888664339695901377282163112482988096747232893295750676690941568494463290730116247822838421828649339437010788165430710512903632914670529270528098439859718986580569781164710102583602429563649626238817198851752150256839194761250249327990903746851390967504209752042479527523791824857674302720147951681393130861129469956962513163744166621211214770096232423058352324863327706013479610785632814580681502127018494520155709115651059545236646813027941576086510607434365502848385373510684649855795155224752033959337914546058251330474025320961186763814554194220596151399428277009154211720727770696506865214610059620204055226083684833160528072571967096188932684068843
Hacked!
d: 9420364147446085639274379387786973162152074307922801332015153785267117724595265070646876503524212628628959579565360669628828274045000595263801870978909279
./rsa-buffet/ciphertext-4.bin =>
Congratulations, you decrypted a ciphertext!  One down, two to go :)
4-4a87367d053c533fd995032ed1e651487cb5dc1e0b1cb70a7662b152c73650f039a60f391a52f2413f43bd54eb7b12c41b42f31ac557edd4bfe46a396a8cdbe19dc9d8121924f43be51c976d
4-abbbcee71f140198ff8c50f51069465075979c31d32b052e7ae82ec7f6783aef7b41a597f9504d3340967b8d70cbe5a3
4-35fbbe40058e20463547b363d1f164c0bbbb97cfd9ffe7619bce31a59392f0e9625a2cd035276e09c4df3c0932f22bd322f16e375c7c7fd88da0f972832707eb549ff1e776db37649019ebce
4-12b466934911986bda845d8d26710a12250d210546f46716c78d7a17b1f2c893b95b934c8c7beafcf81a3123eb2ea05ca89101b23349e455794a8d56608c8ee49dd

[tiwanari]

とりあえず 1 つ目〜

[tiwanari]

まとめ: key-3.pem => ciphertext-4.bin の対応で，

4-4a87367d053c533fd995032ed1e651487cb5dc1e0b1cb70a7662b152c73650f039a60f391a52f2413f43bd54eb7b12c41b42f31ac557edd4bfe46a396a8cdbe19dc9d8121924f43be51c976d
4-abbbcee71f140198ff8c50f51069465075979c31d32b052e7ae82ec7f6783aef7b41a597f9504d3340967b8d70cbe5a3
4-35fbbe40058e20463547b363d1f164c0bbbb97cfd9ffe7619bce31a59392f0e9625a2cd035276e09c4df3c0932f22bd322f16e375c7c7fd88da0f972832707eb549ff1e776db37649019ebce
4-12b466934911986bda845d8d26710a12250d210546f46716c78d7a17b1f2c893b95b934c8c7beafcf81a3123eb2ea05ca89101b23349e455794a8d56608c8ee49dd

[tiwanari]

心の目で見ると何かわかる(?)

----- key 0 -----
n: 879915449270461710485190695384984333346108808238163100635589622985858681174840077891791908299778396399761712011997011746463613908680308851346753645211864161697422478686970556327768137361234129772891278276357122727947947950244829806055158881016642817199313982712486191412897962236823871269648420736534924423486406548812730734126326674748473583138652251560681262492811924913496720278164857004639526764284643238839653952620488132689109774675909664582253141977855536278849104478716737830183823218243357824262208874640011261393661502090701835779701622110255634550577381315794398401099288190684976087038357375439896657810260507762688383926068495576680257990550715767191269347630617636238617346854357508261801349618172932911727280032490944086446846201447378546844207137105811675361827084844211756092591937052615042095862729647068769829375686485423039379493711843213227723084973490186764653471416174456924874481547963600275748770741484515078249187279735372230164334982815930799440541523328018129242237204214842553638367339912643041927393196022387262262204652591800895390943699817163674861716528082374689844511331037929096168076500795597504227135991135809164087623928304090411617142569812170269488375850421090620593124327092827212833845984937
----- key 1 -----
n: 803678453359654678294908849796070879683957150793334760331914564560436346246318146972037345532196144846302396231568208129578229658427016137015812294767829769526183110361155218973534132637868629878697276885010621667798340990722479232206539737134630022679611384856651457676742503181552612577723889148480371814427003519911887820259995809138224880985974019240787368063863785676352901706320933005866320209971047564687269855667449125006030388570791745025604012995932967808845626861494067477576269553063188942863345823904401993114875063039172398942273922006919297914636076165764724319820975790354316178447072264025710629612792744623493832043468536056092942850806682235592789516752472672702894552294332079944336742847297657777111820207270697743634301201554591025634597867621179900279341273373266922969077784989097180467385359637467960548625099446206714449802133881666168001526050626012123346093003692879254719481099405181507957042513412777445437991143507101426673368439550927862534716776799293748523014679560356204884432499174326668666155331266289275676407763431338435327338882392875844836751881757226026820173509270505776422652436206224746614491397668247316050974170122064912373180229234431227192655345960223082314479121823620163578746247313
----- key 2 -----
n: 549100898763808112064590568096509639806005267015788479836998648112330729762142760306265813195181231930171220686827142359040315653020182064933039077953579528749272321744478656324986362155106653831095037724728643255316641716947998245610175805278242802144980117927688674393383290354985820646326870614197414534217177211618710501438340081867982883181358830449072661742417246835970022211465130756382481343160426921258769780282358703413114522476037306476452786236456339806564839822630841425055758411765631749632457527073092742671445828538125416154242015006557099276782924659662805070769995499831691512789480191593818008294274869515824359702140052678892212293539574359134092465336347101950176544334845468112561615253963771393076343090247719105323352711194948081670662350809687853687199699436636944300210595489981211181100443706510898137733979941302306471697516217631493070094434891637922047009630278889176140288479340611479190580909389486067761958499091506601085734094801729179308537628951345012578144960250844126260353636619225347430788141190654302935255862518781845236444151680147886477815759103864509989480675169631226254252762579781553994364555800120817100328166428687776427164098803076677481602221304265962340500651339469391627432175447
----- key 4 -----
n: 693029274887353228407241634151666394848735790190615012301892319642252043063441848065716981473964772442758740370147046907610931634092918165021079036177362202111606191956418667584361908276118660423367531586528459110446538285556884064171765200923553991719010617219127236546574523638048350982056281625504368802910163823494559412837552527875343392553408538829400672258371166335106950477308076204615614002674078815990333298949792313414447948554863231405126552767821926863542808760806617307175797842493616569408376748813625064500486610855810346855210287339165197986553654602677812521680748485202471044713053183325655849850997212737083080466361085135767845684389568237981315538711572490435547358716105872380307864256754216659697090488815080191668745091862519968395816165962906971976332747183909682018887880730856165892484276277315514729408134825829435787368836101082383777555602109552666946636274769705939102192515512772214165267762974326870938422311435887780687375502822263104262793144084464266516328466921283433546722681655409668160240996661786900031559973837193865566010853663246854051817155542757612318538142879371196485283181654007531624894102938084847401272297968117074664980694267271434859758912794604099694079778856636033918615329139
----- key 5 -----
n: 558648506818474261267926047815663564748461840589382794341879898045098955763377286011667977696237182735822338560444489236573716372544780763605058551497478421716695344033790440922077026632959955153636731271279530879698494369588461643355919436273660662159076752508148851041536971067982979226147537361176787716029952139870201713878877243032756910168897737917616572847826633244329952012102367416741268778934218199568064941081826566443189208251171186979473599344539318984264322522232685526823205535961297363403448343924661327298106111649831891708199941928427214309187101550517524055435481742017905815136802698323157353546126780284827134167563307825000360329981837590299960910817295539277452762627317845829666639427884767086690783733059159124150824416125937870140463622427876694849937911497503756067589073583336959038335208291257532551330243155516181339811318004840305586236286443238140235018884985545095377560037625784549759454267069524818501442321838507902367554708929358105208842619264547469164614046722155870893273726762337125054030229277549499202475208465532220431433529448716325851822414527832136466295720413026664365817577803620995791798155374498287030048333500284317171445315596658550078267456708319243685452572756019788684443452711
----- key 6 -----
n: 767185100488428919016632170568302864430595686111633853865853178271740753807631107438469636874149151975213091797469800231881024440218931836348027417405438325824297104749723127225412009768596670293358224481910117990221965588027812122211776093837448747674231104831266261442032627678816332117512253254417902273087090526668802909231100189062059172214484966826827211424626065276059613985574544412609131190663177251147222337439529271810128210037468960468152611646862922563271251560265472129891502660301505695797093180509246596535280995459316546041298821485677298673720375230145667734470085748234479066650224747956677855856599512299156493819425327975989659334858931601551091941865956355246897792662048547218085830897307455941801348993015738325478197038027303177775403199123814405059965177746759645789493365730861927684438829511689481413687211445070334362680691231035336073760204340782163790243228692508230246815979346673469404207207020959641247494823624451087045877926954318590208564006401609051341418752333546705485665209085221084705978680432756976392471120062576376133959869719109290112050140002435438961179172972247159977728102448723565655241549851208603332382646287005177858241486292754465516995791462277418258182436844243511176521576921
----- key 7 -----
n: 749979763679702614552923001102413222598420327055143366592884454475830616928153389158723443794333509816979393672100126717920960210564132627851501187838900945477140456950347483843086517732539089731363223782588144422490875489986245422507159712938060384936636765688054831684734295961422977675645176192427969220210138514400434077185110417766208052910853299757473785274820964871707502282045685992531448579207544507573959531187195524332421055358738466072315312103928920705607161331344398533417361927657409654496308410048463098960494159384221458472398370268191814997553476176826297381609008035867257348143961323573881680269182736030354970098065304954899262171615088731040878595857748046076662910562652037040735713693406561517350044251964371621498301968727571734228987882429973816153566073349404359830016504639125814307759178088582512780451606737543597544214564914980448467778865632280695665940703831017727134198910142429699156370038983796624625699467555234765460907600172513773056738183411343287267146311797403783987608080344344526106774676468531548285487006033499861509640444447244310628025251530293022040337306263504088064080037277524093221594120941548257761209774320384071949036794557132062962674951078611663278430157158712939121970921113
----- key 8 -----
n: 835616225780375984701766992018195440249708700761062279226368883423330817740067311011371031574823236066898536448592328455588369111013270126439333604791769046655994647578719751004885933568624247530698552462689033948009609948401003188555251922416737741160959890066540234136928996095330520460487178029735809913389739642643307192009178003681974456724707874346235581445822348080982542153948150175947977827625107399399404137706619562203919538411620968260947192617562882768983155735648249707329065345740732438510607932587281032430527452485102478068730597804099509609386304374173844493625045208747040715265866203916348208234022808032278220978629730526040706180758525181342305106995282032560326864582714407170764923307697425764487618156805456836529215999898063305153294981350849108733408031114131884345075412562921452068215024008134705342645030066326669695424971554510803678458457036167449139154994000309186060082853042638968401724806794693376494500466086213637588274765627870304453406172905055818196916744019902451982837257936918262069594689557850115795676221205505915237991585296817690648755049673155965874712222034397529672530846503585894788294896787046867269515061285075776698076392557233361560671512770339641171900703718653311229660390871
----- key 9 -----
n: 724054120237284707178069918392128048662616769974262468389016601557851230388749290126440611602406823051130056933383189776262483480010806353696794569691649303299980961177195685032202211743884060761484355784366288120982858879048366043725473826802989218059838646021224513133386480538288812668832303787192860457714642579545808474868820933939248687999171629222849837805691627647726081290411436102763476885001076704474507233352230947009264845842937377063916055504431117377754580474917843912463556067506821753343387796034840843268990483839673727354941747157411057445335959837212510605033993227000315227139888093938586216807809445532823645274968167405702070444307046713676713448875018164311093863816425051507509580213743097762014062799306737867670932417925143146686154121315127206424666074293929380570699940692435435269078835320195201030206360604780560043835466354259252320426727422087372145555881623847780317911079051025008496326448008782373514350194641351329260507934761075274338182542572948220775833355166001432487783357791838466298380139231580903156564108118830289424647861780730965532355437475268050798502803444227139167539864749651850391386784308304704933567116979955857915922311779265210289886027026257587252275023071594299473744327429

[cks-coil]

多分解けた(ちょっとまってて)

[tiwanari]

おぉ，全力待機ｗ

[cks-coil]

key-0.pemとkey-6.pemで共通の素数を使っているぞい

[tiwanari]

おぉ！上げていただいたスライド の公約数使う方法で一気に？

[cks-coil]

% ruby common_prime.rb (git)-[master] find! 0 6 p = 28796899277235049975421947378568428888005019408631005870725337759187744546493409470582705210790627097597656481534493716225301660663533212040068163723937803169735485217437722947354732420098585958967033073629288721874028940705969141716032409906092583043329293532612601200186754187377338924379443611709918885185638934712580040042904995838353611699081350712817357237035507539201368300463060034856220488010509411264244138417348439340955309300128758040513940379009974696105387107481999359705587790254117489020540714253505694682552102843028243384677060490696214834957049391213864664165843655260698241682369402177091178720927 q1 = 30555909537318327326226067108345484260972616392831008890345613182167918843881096961410781393695029449357707848545288220880122374798556583885387343041975279297622137379354808942799947266338126600859247945486391385249259848502175234010967289831554894776077704571261457595823825245669052206379832284446373088109050246642453540203667448240894956074979263603360448779126929364191229791046048600648158120404404766763070327940029813826415327745664993191485439444296109763969948631755535163926384703087422857642736153852582820056661551903549876616627900530084158172809851351898663554970528201875223815554349604138636668040631 q2 = 26641239846781539174997613915486416003684568556746576609279663468469031683562139918289710191916575980269872103186803161203776420494840845869372424906386190919487401478921545410628828040240934885968480468559124463233908052442280478139872489261920279274813374296134128578293855845928227225795788061940296913771355415137193729864318300987109915105382195425114525826138321815629366884757211418011082865207792823895128910178064295532964692290697547400111032047363746813247658976480566291220338236760240639947583180060309174234225896967104503916386813098322083010876516252218060276731781117933746509243898480864478441202823

[cks-coil]

誰か、p,qからrsa鍵作ってくれるやつ知りませんかね

[tiwanari]

https://github.com/tiwanari/boston-key-party_2017/blob/master/rsa_buffet/key3.py#L52

new_key = RSA.construct((n,e,d))

というのがありますよ

[cks-coil]

key-0とkey-6が対応するんだけど、key-6でヒットしない...

[cks-coil]

key-1.pem felmat法で解けます

[cks-coil]

% ./key1.py (git)-[master] p = 28349223152666012309896421767725787316124897111416473420803849019741154117582482568645254183215552986563114855665416593397403745371086355268654763921803558654340155902194948080056226592560917521612824589013349044205989541259468856602228462903448721105774109966325479530181197156476502473067978072053273437369680433495259118953717909524799086692640103084287064091489681162498101607280822202773532998098050880803631144514377948079277690787622279940743498439084904702494445241729763146426258407468147831250550239995285695193105630324823153678214290802694619958991541957383815098042054239547145549933872335482492225099839 q = 28349223152666012309896421767725787316124897111416473420803849019741154117582482568645254183215552986563114855665416593397403745371086355268654763921803558654340155902194948080056226592560917521612824589013349044205989541259468856602228462903448721105774109966325479530181197156476502473067978072053273437369680433495259118953717909524799086692640103084287064091489681162498108275295255082627807077949841602061428289272700263987438087045434043977981316071156426134695316796020506076336851840708593720052204359360366058549157961154869248835793804817253083037277453771408544063058190126149127240681909811943783388977967 105167255382644895571312972761205179733122000170951354267154421253189833306505095265761207795353985354866554008909912765602070548707906837222448483145839878289463148365919513525444080771203463232062923944731237185453081043325693606594798126030587104605037570174567693074686722115522456100623465726801160698239559061091663486985210248549207570980296827578451751964778610951987464867684030722466844105172829148645162675774051966004725828347088057209508827310574501913860263606270856503771824888033781045424661699281385347100922662627583540493598137771508306741473045595581095804916073185804638838310604570491241502655886359339236897876949613528096999331438300999697708890299457985911979849627712851924641477438819469128446227689597941291781062576314559706276978573964820852140872917686416671222571779079770092655409824631889898330085107957931952535103249730281354110146652618132315412533254982323032844101070334909207844326088015459725977566927881155952603824904793104799539283271748779039140727801683586005058013040278503739527750712067713109869489272754182635571360822835367404551020717132523980303574951279666353404286050161901053718140662127383907417324478531803286952584000534157988329219321166046552980660094722243468500414445057 ./rsa-buffet/ciphertext-5.bin => Congratulations, you decrypted a ciphertext! One down, two to go :) 5-7d29041c468b680fcff93c16011a2869f17de75b929b787503b412becde0321ec72fe1e499f2150a1dacb9a5f701c0b37470049dd560cef5163543469817971f50782f763f0b05ab7088f7ae 5-a7a1e271cf263279cece532b540545fa539b0f3650e2929163b02ee5459debdc53c1e07149eb2153015bb5c88e6270e8 5-149480c5c75cbe320564adfa432ac8ea241e048ed39c8bc6be14ca80c392487f43a7882075d785d62cb314ea6c89a6b5f28adfa56ec481e124567b88241de2a6cabcc7ec9de3acac8be5375b 5-7285289084282d559573f68eef10191091d76d6670014202670651f867cd2bc8640a86eef1c1e482affc7ae801fa446956c2186972fb6b7bac88c91d050c9d3cca

[cks-coil]

FLAG{ndQzjRpnSP60NgWET6jX}

[tiwanari]

すごい！(´◔౪◔)۶