格子基底簡約でCrypto問題を解く

この記事はCTF Advent Calendar 2020の23日目の記事です。1つ前の記事はakiko_pusuさんのfreeCodeCampからpicoCTF。ちょっとは進んでる？でした。

最近のCrypto問題ではLLL(というか格子基底簡約)を使って解く問題が増えている気がします。今年の晩夏, 秋ぐらいまで全く触れてなかったのですが、最近その出現頻度を見てやる気が出たので目についた問題を数問取り上げて解きました。というわけでWriteupを書きます。

扱うのは次の3問です。

• NITAC miniCTF 3rd - knapsack
• HITCON CTF 2019 Quals - not so hard RSA
• pbctf 2020 - LeaK

※フラグが出るソルバを記載していますが、説明等に誤りがありましたら@Xornet_までお願いします。

Prerequisite §

記事が長くなる都合上、以下の事項は既知として本稿では深く立ち入りません。

• 以下のCryptosystemや署名に対する理解(鍵生成, 暗号化/復号, 署名/検証が分かれば問題ありません)

  • RSA
  • Merkle–Hellman knapsack cryptosystem
  • 楕円曲線DSA

• 格子とLLLに対する初歩的な理解(格子に関しては定義とSVP, LLLについては求められる基底の大きさがわかっていれば問題ありません)

なお、以下の問題では列ベクトルを基底として並べたものを格子として扱います(行ベクトル派もいるらしいです)。

NITAC miniCTF 3rd - knapsack §

• 問題リポジトリ: https://github.com/nitaclt/nitac-minictf-3rd

問題名と添付ファイル(暗号文と公開鍵のみ、スクリプトは無いらしい)からしてMerkle-Hellman Knapsack暗号と推測。この方式に対しては低密度時(平文のbit数/暗号文の平均bit数が0.94未満)に有効なCROS法と呼ばれる攻撃手法が確立されているのでこれを適用する。

以下、平文を $M = \{m_0, m_1, \dots, m_{n-1}\}$, 公開鍵を$V = \{v_0, v_1, \dots, v_{n-1}\}$, 暗号文を $c$ とおく。

この攻撃方法を簡単に説明する。次のような格子を用意する。

$$ L = \left( \begin{array}{cccccc} v_0 & v_1 & v_2 & \cdots & v_{n-1} & -c \cr 2 & 0 & 0 & \cdots & 0 & -1 \cr 0 & 2 & 0 & \cdots & 0 & -1 \cr 0 & 0 & 2 & \cdots & 0 & -1 \cr &&& \ddots && \cr 0 & 0 & 0 & \cdots & 2 & -1 \end{array} \right) $$

ここで暗号化は次のように行われている

$$ c = \sum_{i=0}^{n-1} m_iv_i $$

よってこの格子に右から$A := (M, 1)^{\mathrm{T}}$を掛けるとその結果$B := LA$の第0成分は0になるはずである。

また$M$の各成分は0か1であるため$2m_i - 1 = \pm 1$となる。よって$B$の第0成分以外の各成分は$\pm 1$からなるので$B$の大きさは高々$\sqrt n$になる。

これは先程の格子に含まれる基底と比べるとかなり小さい為LLLで格子を縮小すると基底の1つに$B$が現れてくれる可能性がある。

もし、現れたならその成分が1であるなら平文も1に対応し、-1であるなら平文は0に対応することになるのでこの条件を満たす基底を$L$にLLLを施した後の格子から探して復号する。

使用コード(SageMath)は次の通り

from Crypto.Util.number import long_to_bytes


def is_valid_vector(b):
    if b[0] != 0:
        return False
    for i, x in enumerate(b):
        if i != 0 and abs(x) != 1:
            return False

    return True

ct = 108626400913505494913878082528649269813547051639528738082068097882991894509714826830979207940511368887159035096807862888322993459860630949181293637015196082
pubkey = [893158977278552804943765886777164372444051968180180407171839308201464609390243776255048939865212054659422832974884079639263468332458967855189817629653429, 481172923134902324436811797332865283411582763523220509717368613837760454784853714744490805689579386936075663484449251299040966176699712052115411310510395, 207560606973755531789573123665698583137340676598781836788693758422168900538390959701798014541840157638185481982043268876455392062821368747123014974102083, 761055558903770283228434786774228138170249147528866734891877114214619301974100185573259386653413911340013433934158652547003104230345018739451054905040971, 220101246189197864078341755214090892106189270761196941280361048344703486423958391273949594174030747850280659876650106527208519942355295511809509490346611, 1292391038900441936820321110300662657457226287701747662575914887742518100301223626606356510871755659124469808997035254449056581925180437850312444280529478, 285726248763951092252746836470742019142198099140898702302886495537893984514344627440646403706132873417575328249659188313986180626404551983148320548607926, 300121927945339909563926219671781435050581096006052357565103658540365750018247239383241977024980272905464207175856840099370026374798806179414727781778844, 1046438174779553035035028673474502965233036523588669325120034682810182167357102361599913090531789415431280868347139967416401767607896903763718782999074994, 901023777688521807901515523407890239810081803747889361156220622158238999306363328757781290786246366481058366427776197469448237010388642837882362999599191, 824257197327800098094923058362288471143383271530096035606573900974698450319995989995248888290604322997102147271247390689358768336944959328783394583089677, 259638601545361895208720172740128723986784739572719248760995443028691513813398933374710332316100780004663342714787511557808624015507529468537521492097878, 350998134356467754359799795015294853138862339574462663204847217419432502379694874394180808237301637863066120768441494978685072627632586042168463321926478, 972243991726579017644693411094366283785858106505601581729984708178319430992801077078161045747209326265146277389211156063318050222539434479892695227303390, 1297760524812545909492188623877069326940196096565836624357658241256716776540168535048187840674377103068217425561886901368271845961089187792404171778717614, 916499591090762060398322164745632359241850048447697921257212156566111242965775645617986032265107561039299619707004444620210244436658943513732110943380224, 195696598755342053308305563665793975310314571342852237675970183884317595061735626724222979567562432260905104423800287023082230472201840732451538980263390, 930819829059074396205368112594205348610786777325248508978007360757541057457494425047451060027614818140136941001579529032258235215225810749388478984609899, 291349624903158796152431403035809419184751377588830068917483045629138280106126426318053506488231384952384108588826072832436583685431487133615113554803553, 145272793400170317461059230465621045734413892723997805424722140012667172378722660773508105732764168707968040489969238828359655595665084812607239961125940, 228733174106225572884553241220681666385676521723071391486803762322744862641343700232291603400814012036735834107896475947447499257180409669103144236856699, 1144153711241618455587909944379124162681030454342205292053210624007965351650069885383288995331315204221368177964577254334593848489978770416942835062849617, 980171268943985652576716736077007646979753646057989508957562358832140727732269982881041759262678301200876492187496411219664672212070796962680723167141752, 587472969930823661358862483768478639763782077941557755875961169472540605727555833250439594848355762853487719243862174074877655965167183731643609694624159, 1283332223222103592009151591905530696749810039583004694100678804893758862357220186998507634555952702870367270602467140691941290162501679860287923465348158, 281637491175610487778556852673047713812139086642235994206040418150553675464408911965244186207111971218166894420604942210565796355332505694224900125561584, 333791873128635365812941350309732979772800609722809183943431775497742771305701351447450285207396156850708230837741314709101728021109866215624490983283481, 82328039981556300286768070031598590119786901676764400851909869167220802384808552648089078854312958573067537244783579755475577904747773330842691082956089, 669351210921922287670008132622988826111253129968318778572310215121287833472193668165660941030634639335650428549207062225733756102883607312017326058906236, 582614982698193083376305459695318020816946572053630112086435610370675568714018274806549963895087831793143678101590834157771736781809377975277087133909245, 628942654147935138918563584133749644526954325903833349753517333092489873436194918146110807927741688664511415855362883222944707628519575820891482544013694, 1232558196351821633546271028791386800564610530497028530513791293511601287692514719847589540795975651970255858053927831271885893107255588745559167678726143, 1137861345607066613959022770571112542715349620167328179634469442706543609182006095096042814301901946935133795823021028022324607926919832987134448874724320, 157810399766113871786415067883233172519823253489811410598089444954246911975544233428498016666083331979517277931790950475985510645594423925066528190259391, 904517925863760058914171053662287018924645423877764873549744939617667958650145414703717719245348396395173721967419070576934654992600413756515089943954445, 740435665605550147498521507252382240877195125443864653973128725048689569558461657290923505726983734356652313965082285844039676059407226358725049988658322, 100278328959468123177145149143197029777463347150988170306631476408457953785111092749369776252905600738085529880596096116320419706530681588186171129457983, 956375016282105557453906976881650525522182452670744026949299543959438967852148064212294766273600654946521932831596634059013995835026925975461331652827290, 440088936558521485130864118504750924144253568354398452449161932867460234438460580098921664783304944974303707734866673806639472368129348807055144794726508, 415918708091386230067457783538195740153859851756607273999062944040460735244219157649874190270615785368839083290182367807165607998101804405460357597093805, 1297705030954911971785270223042597188781480519530454125749622986758323075030008123282876196615238578363978247711576503400064679510066717435954865589571504, 1157432174821854227764542022050317744541246495437817075502867892967603693794247333203553790219501437495382224301041982252824270823277808571182280038568809, 30374306705695293429695099047059089665720203983747283747387945943310266432141380629152483271455534925307178795927469523838512809499717498046043220936401, 904146791201843307679613573694271503700599439255820834424657134431595330396413065148130807778660013184657670671837087564288110719318891354634291511278467, 547546795689650307943560779028432638876122009238892003869297996481752657328964054522317053826751379431160333263164543418787718383525458865990988679621929, 892434539480236285877151852865359064789885640216240196787745976950854090028504759246430083140090010581139261973900502217997036043708283671764600058196287, 1268298639055935871972153854992679395320180610688495769642112613011863112950414540497335790060320862897287228659833858258620320205539161606296983523774597, 1116168951723728750873600758963693758155540482405422226133866365647296792020496551835043769755911464119816829906800750974572255801614620005914492692261514, 375187033015959581880450314911881990363481578638490052746704597169641660763714055068727648876744527534606332649122423420434876156761672105581178781997090, 1036436084222285059585188390641750179939225355800140115491795647573796262571907073944895488120280889470414898740795786278328530058888557765968642963069062, 694769896042368076061475810854276082637824331886394817226498480188200154289136974766397790166259183150214157563027168296057330463861462376419871042898083, 1076181496217824043622404669091949388079124186288133768754999065681791998261171978109244460523420682788112662406238154968323807715292810961097668750680213, 1088475702795938587475987584383620199130607327001648349279976413676042519580319653549607554082509859041587551462478657088143225223348495463292179298919180, 411934028764433743855326130563376356470252572064974325983148122204382581758228254278561773778234193083879289769202000415722733531958152589105218380296438, 157305040579807472014487736339254703195817673575524187896658494087976644740040988310007334225265189190192578392538779512941853356347256553426879967753249, 648784923011223748084348424637636143866609953017417254614610214568594884056231532261051967539665793813174135360488072412295726635361704396219400111108536, 989861735447579224833260487501458939978737790984001149299975708564578776181925442259321809750094707205745854173935506365259245980162833987064654531034490, 230588076601028481003664012913765420168481687596119624206517441684477721292658303399320021088186767550310450560394083042105942973012610146907545942327825, 17242907899695608584907080369738432700978236279970737345627911010596090933739814224064873584446049464428814466203377741996159876581597480420698813501368, 503423030684043769350142826342289009002531328747952247594358432101748713313157783038704553972647805310765600378925011914742506646658818253060444078956366, 498365218872777244291204873105588690932711288354090924586992904516239387020285763210695803006767098965452525102070420074618749929999993860195374490836422, 288939758356895530940392914872637725213754402469180602705884068075726115110769225816676242895669872018711038907980621433072584265123679288303782250324422, 577338008097228619926311013972480745376538915689293916433290358130887329214847982824048486018743343443985210006651808640739089939670760445320094936508523, 166071934718789873885401848159308963872948151853956971239537394475864980365853297512279124803001762671715450750557317657669139668367474253932071683373102, 576606141151421354561689305211933629113795698933802963267239291575652844690916020314721630243253438647297681751331360310303257047808997069623842900695303, 311231878674331501203553286841452728444953325581547082209093072494400882981251433523927554808585842022234933996078205865721606016306741972188987330816410, 514471472717114916986954724667010449166517712833838622869066919676246908116857949182317081598781581145030869437998762002948867228738872313404691493011765, 338780335459645266415903784396870465836295830946002804319990590863527612722259403234123754482293365868378313868636025814886533146706743884263189544630869, 541041425341630173872286196755207223703306366712870178799607209929210923020772172939596252259759700252678925441970612782143843458477681295214656783388240, 1020756233480797450446888487437334385245488675155994242331009361059128303232015965205282356660047848505669548523566538762906632516270046572756411361157883, 362884076905706389821085967896696223412994457302614070387237411099510320937842356162041230483779303556113135987472285531318028368533881729113783126124611, 1227010474265152475230749977306961997748808538063953882040241648524594331286920728806662551657107635162756331641449514372018638421223854799263118129252655, 1015212207959759145026414882349449907866253793446720526777734316387943184158581057161982168831490500323709153398876657521207392176035487883741855168895209, 107306483387070121916401958716748361833207106692278447276974489614949558858338253814074810945278988088191571031465490364462272549747750278177784985625968, 685688247251483712756979265955372142206821468473826387063479126954633924128346818154881906349994181452915699628442012643865799699668518343038516239788696, 370120663608664900435178205186900176376348973126963127529087036173847892795165067452114744481695134555513814458262804869207932801872873226042972691098979, 200923527689386540198157428090528385072988271573204688036067037031655767872621351493848352753481228110094346770630248712621453561788093675597145472823912, 595259180921644628113903799718348500247844671305984271058318214246642098345227232744751248947040666143557661644958001903891317910804254876724344471820687, 614417579613830998204232988138945052334097886289139573376041802700511000531420978415076297473595865960703314255808709168105704844752331146495508630468563, 527151378804294582478680705420712613065618128301151082851023111786907610807628784738792822165982325772322670886483271657412655868975590947500155871090427, 387902553833709209984439461027695962809730528571548465406545268142664715308634941047045243252860343952329054583574846172675491870819948308085027211786910, 893855156159053059742212534980830134906908448109856181545411468589481921696420695251225411342581309860485354377252006888559685241771336456786066491641319, 1221650770429472436868900699214293941328238385133441487842628860652314148948389153662953215550077863283958588489538103286097872929304117819850781495443164, 543003583797349888689802842984449992272316714219081361525485689931675106385358091669340953674920062809013605630517535281616978975303271592246440790586260, 265980601800031171656667084703701606798652326206473752956955990432702494152158457028261802271623033896160911703486514104935722156576182711407790819385867, 349107811074810343889230927729230775791500872230816342989427275255156320028767634373591287072480625824450021576343829280043066517446478405778957049983116, 526485350491706412205414745643750773728645598333374838996577458468024501772512022309926516470449985693600848942315793745837477504095844778315018208038273, 12594736991213396198615439557221885582549750872516148265636118971351639705756400731007680823169684608633083252728480398913906500101574215096103686727215, 714397361772997373867673733518545708676209906283844114783166803814900524465278954678581857583929998875823324687513472446508996592170715301852806262679025, 1195851764189736997849474781814579888537987498285345248868020699626166213106591894962512356534052912607588707952306376562024210837541843662190282727761620, 436823086017135715304884007319330009428142496110871186777353629848699959163058551115568827686074924912733053480924773879399180247230708877345932588628862, 1162150590401980319136575647946836086684703973815447711139605732637464398646616672445011648323003400081037900182885691840167739915783508430803953912812152, 589840958143934452942408460615187076114657743626804365879009010735064827711302481255826352745821945991288721841328475579900518431650483950771811025678310, 805523148973288055394550526986262213431028796424411513198954225034241570977326143916027762037415900141210695479638513873999158600975895379600653594045759, 719144113275358171188557744127804696745759989431048898928705643783245027157090662085974377534372508279070019073459554837055624815377375145960846788102820, 1026060426417393484747021119809708326898052924650430312226084203940416798175957514334157530396073604076636404770362044314908852671063005618918400612036564, 259207377464389282488408555321753893876574232227793541707223518505105411301506914327933183877940596660202599042079696526274903686638310092621153339978675, 191649123790899251987088355324960181467643640043161118628393795248624603377477275426804690879670755229949682405185844729559996512758570117342231834767332, 530248368271482004580046933816234733931739194719242565988805757594663375959563223903971722511027786597746170324282449087477325831621491062455008223301521, 383754173188818176448244654328326900463809260577718148805310900536751011815682664781358327361160333963556401094480196003276311565402063395488170194173165, 809428608785887369607391303630376551856134749754963690614911335104111137268341576650153255841076557631980189246397623725808790224086095020011019515465634, 1052607801309409836412349954947438711599947499317379670150538838785349274207391777708836556932668383795640938562786075284090652844741993656958896114379408, 196208111574811466286059208052581897228233464962484821037428750527493125102933136568677408285713269819775280358037514255782917480230833877038699416986310, 244010252376745693008855551537900962879447760212632514606661702840425678051469027046286524876105558562294898021814481582264420458582734641663116451880175, 838502228026852273284808056522405705924689851851169416807994460316222043233455386744348665181100297215310143093321064140699086971704875264890818931203529, 8188605695598247633258564849614750456990383429491032617618609660456627866105806279682745271642345349624317743724688263290263852096330916957169719153653, 339052941012694691734840293161928620364270221093726499967838995581721901086779914524017224069511272025980257173493147586347884348834733551329676184737892, 923116506430036404781831913251341792766669590958243311272436441166083473437658170255128391864989759746786661760975417504349188077248744649604701704443384, 1054377577736952967266034481868386677062007015925582224742596207389833112752556177948271345760412722205259844138988495814636930940731006316929065993697864, 1189387506060271349245396105365460118888947410494333716074019769362937119183841045056552214950217316346225087611898465931434346017047189567621818562480404, 561953634515378118179841655533691232219059615881645948177390541020633569528749123789854945534818649446102660610544582768668882494053440306492789651240255, 1056860164893748354571668782553690655217434622159496760659763789608148861052132276716255129585490152902553198740134887122241702287536777799795604355105071, 473107178233967891723351256518166702499025880752245746284150201944999237491221706476276502744847649057773383903669126026958759787158993051423465332020543, 1230814869990923850065764539751847014872136772252486447396477228529808946540903195790524900590759337759513453891342923950330953934171093918653653238249522, 826604721743919282947732675054814741622385005161814898837332576389460337243191052312590409910832329458736587371907638121437949774507436531157184695730859, 648182019388129654553628395950615354434989437473717602362811950476527945625190952291794772045779801294870161916883599836409067557295675402349448593430865, 1082939267394675286478609022481022267928028306606902398937143691663889973377243741074485456039583725640194866895456110103557831402966688306486862979518841, 1451399538087237156350555416164911021753184956867259198301502746304427725732653886575994765854422469323046975355929595832016629105037227408245189272910, 79940244594877389490820519502976384241578454908533806751324678268630177799595562318435217867476280866404908862896380529114836146993493805133504935037653, 746265881240521219225886966617579057140537361474803744943549965075231309248144015198199045301623741249536595463350014210951860976763360328064207570457460, 435557864963374629144762430334388184813510139942023544046766193015765153735122337521644293845125082869591906906898267842685409360253081178545750578306004, 53690231897796035821041275226503818999004507622815007304274689152158963426143272987655787812210561986462086868928913007267042866465404722090428676815118, 102845827355668467266903738877579450243958512394905219401598255432432213977160416351948993154503368313988830847381632410641216851055780098122649943954957, 422148520825060922240972875613179639393402590908762797387617688396988783064483992863409634485094267805857102821410824325448991346866960548266809386782608, 117544953302912741175921700661020286418080142539127347283579516318561782604042707872348751121834092930357132512276086772925418624309264630871739135153845, 448604575546262934647750438163331847077192558324859251246933424085169279757808621350535991597260705339898476424099979857104290881728719992798046992546530, 285795100672236536587885703595733478276900549156127383395007652023913537390773735855452557827004118047843711060037979492628592791826022996431320302215466, 196753127806465100231141366971303408716478486111175828895780856788378647315348628763363048531768458980413061669209574123988955731079533467617804806357804, 1038146162106499911600025362643581841527740809662910760279236190325271435132199293823219711026982674410248214909998170347051571838681740110418269793528549, 267771635786635121554701861903230183402136041135614403711990936406125649373804255254206655558383727232050618628926653253411011893643229499102976675530247, 780011995030089698430577201028027777771437146761424277951414783891681694922386333690266012360425377602094842306927631133965211254309723354247623113659314, 1243103407639622054687088241520756839266967255511472132319966708593533776422027791652556044375210075175819383846655429467170663109724822056098132842894305, 1137636230131047946644132340459893622660214469807283671386549417027893404444665614607673496757508414059881274531276665524916025941041070590047471815083130, 848645316524794187073715765825700518068176319792978015962630104671654882266931492701819971327263099061453285308794659448394305552475538484201539100467096, 448526029835018249616074267956260033699296850501603129428089382371979863739358056935840550670828254339883106579761627605629588843039869193255518250189873, 1113407723482886579654050424602133269233363451752859986563627922578698862572989370117362282764200334390283953739550694875757283146239447546363657789304171, 801609501589684052556484981085839391678136972127316782111724097728399172155979184024869314687583263711615893108524398849101055456211051780538477531030497, 500052606228432320656181519741016894325864783253621489301140789412200516095583300223657269235567955798860194749582324124100217768534965346629773141614194, 449186404143236578764096379794957282625408173440763078309196224342452526075808703066932782485087219267184210838020769531276433143756973797953554628795651, 799542619254704334278356023465389984413129640378009642873458215205836313077228623631503794772708262378728772867661924563989172988946454369344947300785033, 1013176021605868749562868800926740191565715872652790730692119372180724373881063144683329745474437149437414740272138233431219498446273558255975304229272999, 179974133662275197492349579941950119042478512030352114759112601535939341545952687813366572957520344426564467642477409881077290468421485511037150180282818, 1119736155025659752338083774044287794838890840429124654448636256463686210615213098146043236441994296448239784886112226528808118195263060658119834455267365, 1031442653327876239112938947291790569461327265524830533323278271771731950828579911242435335643767421960191270830117892725962620246142738834990280598350347, 111513264890357246300378281193607259826778814318892902915104911163648307478761196376928363609257031379017765166219940564051613388112133296712443119886811, 164892278413853518876118721940947067439185670709645064493131385446833113082498361494769709332236854715864316752585999586821862474728504544093958802981549, 1117260728698611435060339500645870879368237550432655643732823073341474330743583118524872847183979484726406413237300775820428787467616592587315524916451520, 1204218743267732032600640414526757714391916738755343934470549419260306810083570720919615823472650974733118372753153262073366048857072982463575539478187763, 908390112805571776695134531115619760585277791257603471212387372209177407917021892408607056320520005065089337495647259734733426760553481729990365697902269, 327864085891054668127015585822520586512743590770975783920320202637288675247448238709353032179839792969909787474079991853006022100722148908251673749769832, 431016084166965905113081219509668810263395303854712089513086375704814581570615382190854614648485391362940746874458221471814885524670385228456549025964921, 494540005062854484548667952655825346025179182461770437277953109595556554031200442297890301093777552383216853934977830321922164247557088875264479491839594, 1221179076062816769597295083334045455252850812384652106974234259867339371932550378511845515839744597613680395857756335273540734673796866396138674824387816, 178490822311449417512862498963141700655404582287866723223903559783713983843049879772578821670357201206026322833918431189319908522017927007022324933954891, 134114026343792032959693102386785177869779764564879847520800436403623254586918922508452246906260040528213742055546480189455622694433246970942962946361078, 813951820265387730878852644885552998035594221700360029098744675528645251054075979598963275504855660162297010020942161673282858588399682163983795924516985, 1095722273303679777971741312050422340514970596343263946765605136279963548024357055240957621464604703778747723839786767407580031419417127982847561749385763, 46056142548612451618911813356700709231449741451319218548366015683679410050337633865260589172469850332410631281689980986654119201827555332981009863708258, 972942374078031560631120415339240083080787707469963825741460744356250586204309135473924544908602075528540527324948212519067771405588525375744878747146410, 1091730295863871575561797815330699901237282049571518278387056717428560156867701083555027578710294309557175981869333486281526954363308768938540238987687150, 742900592998255737906042987118332820212500289705950251845513709623466607902144171777404404226767675688152630473790390409005066327294807650142444982619544, 577975373965984685816761014483625783485889833326830142891489643404028498603549119316044372165457280644775373170915562854907493366633403727659328986872637, 211689744864503844051330179633937527123211018974317667404940973218136210729862099663275745257387924533002911630034870028553551540417049902815803694014429, 793490127249578190817621247276720207773208680590371164840165603054981405404213682198606694813869921785253917139011447161474266309170256759784491120865584, 722804063293907345436065619604383928423699093875190833901636116318477013187479915551304213661634403770772625776440350923300338144378002619123213280136901, 603793540738830236928360961843944935795144943854908018632663429025694387617321908553213847139047277435824235884725625320967557834049412643517185453721078, 183829029137531658828841123387818451804426346377649333840523699592766387270592570217470182350808996029617093723302334687723587219887800048530602756114592, 738480324809199639008000328480881101616771762987357657913890026258350696909762523436457093332781927286290095003188087210499914997614707987513920455980254, 356272617500129972170235823926240627753616383570773804640824020143371222402227065113951269391349347049108396194194467184384851014529511618868959373802086, 1158079601099115899184750873600012517933912152242797071772142011538722436742096136353957278602305490545321309088633996954906352374366222352184543736333150, 61249592681907520315053399384807299853938432064633113510635705624655723372100149801814706348209664500040193037183931319228612933013754572619698737469902, 755467136196135514688548129490638821492999892541990084237748915093380190657144590414953134639343231820032282295458253813118744306578954978258282989008416, 404365694294468751353634162890615391258351204105960045199945600048223912439255613612056916072588894904460151011836476987084392285834848252885830054770466, 1071694537541371390939289916801427641532906383970011347652717200462959142028217136361242299338203244115142464826904845292924418260137634442756957307009187, 314596227394170290744622711455372416217073291880546102375949813660190660485125119052564169522200180665402562432518294977712253624639831576173469005103566, 766875469040806048771258707111194884447890189583311622374890971285527295957722317097490446671240390067292181809776738305895630250906626666556083514181764, 199353141452948321149281804703376449163033967411458430653735812857758885895175267743481757331842835731153469221195761802814904896790779333118265234370890, 547559883812180272239376427031332830540035876116725124526509717059198800035307839164146927591755635265372095397178785003163098090507225041287266232116496, 525662463316103021619263408111784628793409824445077394111424584955914653556719532189653681115510908562996528619756872409636104308060425609615029656349815, 929920224165285094003294722751105964014421595328445295324871771657104149068961644914637814237570200627513037525758702667222560708907224304815216431024231, 378281139001041365065442366742293110959367936015184457923644080013115341199275314737146150500068880276085996345802111356379412054495201349346915615116337, 274027488646702167541730817365958918686275137774938722246006733630823021901514383716496327047191487754093102686056005262652078862007001341380282078226902, 28233215847820665704696542286059241972363506601015647012455960216516197581875131787128532781163760389312311386962492779450168525395074871792858762309537, 430852728887653712786589618471862573869245902049985790670347881545666539158886411010877884145667585642180607990176925431892874818448217701028821255163856, 1272558522777073538063945112252162999071356342636006913667643141298105119180650520744772327079366135150952882857926370759604731035921259491352865567834440, 829890508796075866160258270918373019459376279197633868153795554804817684394115995567278607498598381124491264239347173229352341781738594127042881405158896, 1004990634403940974738796434328163819261501274871454646669520982181988224880154928400134349736495679943319219178978503713834006331880616195265038225066119, 90495104667364598984197352711602632445155311517490848688824541453844063264115731719136756792363526484646116192591836151854358485412256119816605719784949, 1120640027768897035372341286108438931156920185553325071715710889602288009767547186355305004412892659340373718054598102567612057549596716452247011152470149, 876264266701047699200539283887097544535133781517524289169910613129322890167361451452330234676977303414292511954390349130884942220825038314928123517721719, 513873642352853917840031254189994306011293763404934876758133260038958305286031491205496512893235608486776947259881703747864768894235942616255620914245800, 994205951968928259254513315006570259834394425999931355048452890796830509086829079189829796925419050181444306919524930326728732746372177199232465931938316, 319255017492722593459301735422389985642405533403898632314537253808825872011491808116492317385940578342406761263589162590320735730288626446628997695191022, 1208583846068048502056501245986493215588353698228840567466565022644930900905388937385630320253262008072039639492358223579839209854226777833776164467633106, 715518166174402029743496569639673209233142816256817122781050572005706704768368298906263920298248254272785371247844664702113542167464718145840699373186936, 178532173295568442363592971523901679238861938742248200828672404622662120812702882081279982562764323517039107175663361488972410190665091929887104563067494, 373622793979737362274971230968499177960672759982322045045790944453452892445419968207001574954178910450092576319817922349669260890434290286504138236648775, 1140109957300127414983822173591954939359014745134816315713292843173948117368568931603532753060803563276942497902366353812591079445199940596018115389555655, 841841767482467396194786367752226815432570060741944217200242133823457695961451108900841359163187153431713410400640202630307527510246923539922429371547086, 704294451278792982588056407281675716750513823047331580120204231304874341455431659438343960923084750074735292860954876779029564431072908809416304697062830, 18350601235628764597251373089679681654793335780227771152461393551665384178145786284365671954460075948082458566711794903814444687168123739701297356571283, 845283312751549269407275961553580390699215075177915066352323143878053044874220915177377126056926469947044980974860522471404735506469006616447139494005251, 244173338651241445017821069216375674354415983330061193525615774495414113299694463499683393119715020772011135923105229995259015278133334133824673190223624, 933865138892191123883512182222808963278047264201878581894298671701042680173680902087092953002088055558857095389870115273502556939643691920745992691363996, 751064108508489805493262056617129134220949888611793744238643077745043479112929790938853687663564594498824594447903593266450903214157329933845671883362531, 117718458469703119422836364497421038148898232938308579379783972302268017661563452774606123726800039667244037878884497786374245333539354478480606345816332, 511779555502738884812314369805834434656594126068836811758323823604884649245053821462845558517109061518527372155667189012193483474490799706884290611623819, 1180330026952279708794678495070721666485792473778371907658248949098435772434255381550674552503890132671957940429107289764213787404220637470053402498595773, 82729493086426326680768858262302820296890273884095734678869906783100869972702984972969284714054868027113674154117602264141028873019241689478142627339359, 264247687452642188803766456230232647493944843551961291711553906623985978855919398227818251463022048919830525546075529162426613035890699105508002620640931, 340123425630055493741870152626368521463690405212738250952800408504826059115108483031915007545688747196331110182491372830987044105853307454843403820838616, 297940636037009763075386128081637502601181747109522130880299867525442873339699997762821589953810537059917877972091800652464715174655544004958857377429421, 1137127199140303742405831961992948445498999858289246070547565175517077712940053790719678745619335525333761444662533051579547268132250303667437262076351779, 377268567633320127721200081996895888578772709527074706955680435030874288586192183734003979180162122603482607271257328268217491231234503382757303224458894, 233114031554077410364617110604941329577491879604101253566745563892294020789002237597662175212125725381729408168192484929635532468430055746949897281544748, 404192936203461326055825261693276431231728802323992139730317013589991435085152549828893710151179308553093002350394857920161228073202936889996951454796409, 783012076688372724666313477153990267270080833296410784545079347764524155100812124574295432686420482625051273230138268042687885025417379852471652238685407, 796341245875724241129850019376488780047373806358816683750705651119193091340988755275668467726209653860277818190255771300313986614661631761598486390964381, 1251417168039327898729448876247951023252560563267482258900477012468417028420566241561224754522850874772973968540821299697643505598299915116819077888074679, 688023570278415922049674178867515370162657490562244422504506237034899141192034255039152454696018611261692720010759982785199948980522485951876529744741268, 214807237036848449175661511958814104048898392910745579315986535605608455490730715305165473621705167790295335725074938561264389236746973803046578265230331, 1025396888439817880464577338716025978671977916562324829940892939217792052793270428422059554326426586071532194974077099012963148892067980028313372982767716, 1021171970216721629062503494406793884981694757971956593766978100223189860107818050242528695088355261407243128568082548630465501054648877216353723336473395, 429106845245346579023604749905051724089618191194274473993526448130913169103173803042330052949218541190979288371656418955958797525085625427195385602536460, 1087194183445728221502047169936523323231093590401623973660572933981004110917997756127704109835803197775777304899463449356827195729235215805382012439479778, 947680580434239458821694661722909923886539928687678169176703623435738298420756989395185001477672679596497941091566674660284071357062325792363602209331600, 1285804406821299431148975301667929787484944616340945732884181960899951174038193895844534283722103389185266535835546440233637878195106299212171402588492643, 1294651217994607354368168903638998895143259781381407323357999024928768985436081588732946904841901641839008140526579760795538011555978442604188965017765096, 1076353560067215477106858591208237288953785957551379121665266418805465626743312105175086449757013541167020778004134198472597213609363942014996342358812951, 193604995576143050765687643255282893659559583277922220029678711579066667653998002772903396757982101311188336037993133219294786121398988510565397631827875, 1166762121031190068067462278992286311497403259071759792609908455403438924012626729188269796793417039993907764184523782644464113982258065175096431478637942, 1219560219924240771938456202740263397139599704200644945115834956253190076104426926962965228859977499568914403205697137181188549095177569568343459583481818, 273235099927995759181591990668880050684178601454440517287569264795482632355107986685542226298914614097681122089993513287661816209361538177906767223251970, 90764610640044923522856968055021290646930793196420829024661641987930964444481159002351045459106830699412872248318058054104470844184581866303774788887265, 802010503809555799146088709768242241479188390810253213919907468994582219633370762786756101756212545003435458681599242503234907347765672987153021424770545, 373843860379374263441476976600247979111376729925995772554520713945747395452194518602372878001197748998953125140710255122357865629569357096294326964220189, 261645406863251036989292671593583739575288604212102039814350271439139547006283127153709909939784781239225517020626327958515312533209487032375044237458329, 391297728787301033942407712508928207064881352225595298788893969589633950295193114348610406315084395050366849934651887431644699239662129590400708297170493, 696541811201090277951731236829810612634341232647427089643374714369385682844153631136273446897777926961022779203356580076437788727969429128330248807807219, 1292737965362143748900948986445346360694468668789187924894053538336796877279955112980564155411591063715202998219471187308498868960932077149084898562648773, 609186116847418857903832563640740688622956225380660996505177660123460737582381286322400891167548677606100473439184539461180973384905319802514981629927637, 214349231153020359956629190055728475786896067968481707143109972659973205692074485800586779473604513195447723011084150217079895463021931689740705639957975, 1248524742036350939863824997737761068276115491605762654453711394614849525767148601123793729442048040494109671727892663245078609006301512060492173380620319, 1134633701565421201319045343534237523619801450661651745151554767126026916644942537151139909833336052914007995647243670027686823459502059623499722622084791, 90468508685128526644088962979372423871585736458909365184858318174778040498858979685825987229002001579715434974544917075201870085651350495273594629071718, 75407424842295919675209183002305602089334232326421101382685315305683026055805958261754618209960037200696687182876926954837662024021737114388432839370421, 240161004445097086166843957875590652511350130237441108920856329906526823929801845206621964077464845485255766015447853063655130584421186527565220141093827, 133639209608560972706207138622299270508763451463454851080910302906546978759522274683993508731305295261295369016046983678108785609012429667916143067768205, 877209646645048734159058188981773719300541800630150346378015524865376877103340513472612923987604816761661562410373164898975922116654287553427566828790381, 714980983921519520680063308540477735089817148678048907510862074968678611223771347787367951226341180633367287945746093085020752928799824963070359910794713, 769439540726124884599051325667959198053885765008296136721706485358513407801745966424300678587602585960376907875674546288736768456376387647908899082235442, 345908886560088440117107162076274029976158012112837943379900511711388670007553215523835739323498937207667774731257514636545984088897675460943508774826385, 1153748153870121766283574580098946620037319857343111658807596163857695352934833261830202627852898672567139336154083943301635891888788653212019143135382091, 332387277348703919279779877091927259088870318702544763401900774476778964581999878031528929485169832192040487726935638772969840756178576061625995499131622, 835083392897313649366083087370522916639385727791509773822533648570453676898745895039631367680124293030112035855008635274516207362948902130067514115281295, 227472885052449244529813911375836809589580376609420548748903337085202228793349314422760766064040446516516246082302854830566187651131729652003428608441552, 250782972703831375232901126346132343476778595423390200837817452799068130961616615898666603804970327586878714813566006344177740720697177768962187005025471, 1181909425308432270207564461226780339302748154256993016209064743774364257332813077805935715893855434830208229752331148851901514390966883642647998712267422, 1238677513115042544308248035660079298927801868293987908216299244165790610099720275796869035682015107057939895429396137658865894494082473762939601195090161, 621090293115490355227699804713299209017759390032691709893302966230594896494831073779153487351774386969229861927989663514835766519341905786212575879334535, 1171717305088695557322672638672029638054786461963756951066186593276468721484839412634782174198383930777624388693160623244736959963111964873860210498198936, 482763249819407066596602511607128400674079826653897090335881483129099180084094154431683499714220220023681762290701475928622931633895490520967725541626360, 253312684104727959320318674514072159576960955671018816548339103117384555830003804156772621583737163907907358836059300272907083269158969795308018068687933, 1216188785233659379029074118649047510996085850497253982111588019526821391868415504892951775851182431167549516092675988478826412222958823358484788944862340, 20353762867664994177805159761765425743508093166010009880250352427977963963997123037993008654789395049021568293757634267479838757203360828064425346778839, 462335237585197107765593366891630292577851700173476815131733637565730056242873856555986708683158140607884412066736363698812748358844367658394620719335604, 804474536876100867834745674575243114210814653711654497813985903247889746499568688764078824315546588332764213807857282136229395984785525923634805383344226, 698314112821812146659249232425724044396871885897501423553145774351429064650891626583358647458135121868946442100991651330932931365557374614209127976669310, 1180180708618936478688986014903023005716706635374663025100827270488893076948560020685942723629840241961390958739373434180855369449707707364613744724870659, 1021601109896056303592638639462647605691039887862151595079882610203264071202239785427837576461970197999814739528670377425396248521679442816634805588503973, 1283327753777984330705886154782572521168021438620677930681715635248302202620711897365670486765639789842964894104979916951980578559768192997424082693725172, 964004925089450540328784705630317797118420397332503496417684152881264449852581788680857200625564805245766593017360198244348171736320869291411229783416976, 224435385201234214003554754226396040740270674951972527774074770452334626386919710320449609372091082017513463378972258208365807698183032776716294098141493, 8870284415110900721713975117509779145742199420017582977167772177730668993550693066441656732749129142375127893867680379670445427414548603500465466644738, 1065691968318573945293087634725350108451707973449940571852048274345984990289654660465376253904078618933694305783207803871566486884878811188254641801172185, 1125598354239245836250633064875113765860129539536664835199283408529432370317216171503335704778392124410088420613465399825545937115729448417953257171417251, 24265929006314442104063373445136889668522475453115645401665439689002613151670010821430999820059543527854587128092512125629491393048213202497393881159575, 1132034204415705653139792244858879852104557192010422585806732042902844828378399308637266597611891510213859006410105910103093004623858790278948584343698328, 745707095149844970422841018282738537115756873172590024402358834592181940487372124479832197810436667465573519149869555552586011448654902422443231324105418, 1076636563754077048800767627878758449224030811690719817043031782948030762506626433591004567732116255541067419623684714944959490665886025034467697993013813, 891232865885094485985232292040019447327397003310668266112735236570334636607806885224260317478271243542147247880942977551672328409368323919512678722690811, 652304236146164431820474248024583671282365406444841070609306435964029138435628943380156019258531133823188888602751619703624382538791978120432072380192700, 1260803314236826492840093125669072167669255709019621893901382393774309040819265592435333114400668759857073201812013401735604416939958663676806932739347367, 502273704510601253022549118216642514811690457130971961362627350017220421591267985265519777993258486778330447105716512390075183869009935954873691067559395, 1062842602901912631751378030676784969096652235924325321470808923588895002685920430107686645711718616479941681163117904629228420797717205194800903277021874, 541776617049227144440963998052265260513760305436751522139510591532338261715469382265817347546795877535602165180523586192037785330417725495039963418244260, 277410239999397498506110339913828003533025580223368155357088771278320246591706241454683018386081342305611482774622308260464242284766708771626158974375907, 125952723097960746372888769857399869561210358393163126406463563580481670659039649519961572182477541652135369356393965268863337783652496752906916558378155, 1004313080025706386795865670067778345544471494296867020727583507107987709958690532455232502971247632873995208703671645542706021765651416084047420318635808, 244471330257949191253627228452781346984412532594237288517590714031913589484717267189702856299209532068617669835971280424638198497392060686196262080638722, 688440697140048322281755314072114129386001372473256157842471153093213675861614522561074351549420614715935644755552176724431389240783245715380678981077675, 405194295148354782318206044400460286078216248923585727248769131215451357509508798858842459779068130556758962038354055105058695365309912430770404683681073, 378763873792243619333134782110502608241024251889333286228949589436750629193242672118605387899463239880484868273124468283058131531467205456981004759685147, 1142337993193974681048836519542609182083125453672772035057091283811925322757729862361585773196466880611688968415954007767719630845890614143902571290500089, 1123000351317868108349180239581507562149120738051238205041764395916962440163019171115491479048193025563196671966602975519593112316775815530073478420443588, 775766126838054561642310300600782901768943784697737509327405379298600830704949822505793629074424194439235684727850178750786400997867175024242169263367748, 77227106212252490259534734900265510987445355478152850736250928643680990126602032260951309818682893347716121074661320373508509267513356472985983469595988, 1190066001305643097779368483002643923003051226349198650741900422434956360040290144552052103736294234682086843244052210837061938127214285789294360636807886, 544689713251088268767326372470274776419715413920654840233098800355956039215462881431963870614931879612995047751338775089644251198383534340580259254542353, 1290888351007234035356592340204069056131885509496610154205560867841041294826108445598490104684749661277051287108317211447301683991139747191617986790751556, 37071152229930021565988782957839991985880782389920864930902301047134244455897415584917404519022231395891635498792395744820838028178530687802717090936386, 962859040866493574018018939086440949964491923411380192284062336800673957992211392187914637252826830949069483172283583015967528061233963370618697002683697, 933514320515775302560217774123191998531789660311780359093665240834768892798753175235081072965270999424369366260046176587678008068569385463639645195231851, 758388462192655501953034422942591749890911489708822446309687209735784561546659435950734846573505469246381402694799853724411245236753547228310559510391296, 658093548664897456886011323635929057721127311683039706145902215361376820830193968028465172641615666588110476049572228700349399130300388536734842664563021, 751395188531297992223109566300398496086282199053706447496450718579374966715065565806873088712723845275036809264261001965769487029341972661338260828314756, 60917395180959672893096705032002950756985240664618406829978665827150194241796982618171583770175240518158041923566342786905091884643183263658610220087069, 1300185273931987928628595648399541598560531370924147431805766728102727738146014751444467941576444620755352437750856853096051008662652542793258717618181919, 1046663483259403826493328176970230152190391143979663994970045295660652571437475241250394743285562822894744525052368978141903633059665864519916686957761181, 909699553418192322528373662735870393103441517794473260119558697059262540949029507659633038069378522849630120931283644497751127850553271076206050387499307, 153369141375040804605328016348177421343294837704646603054992979857891100879874914199247399861929686730742793636748311570447091960560088235159425524921071, 592862407648213199091991772415606709601505405333429637209170760195630022572983843276527168193609816682145975394556501946527144349707020457433786993034067, 1188041563910221887175956078625885727313704135872463918601449365673929682775155700383948540474381414655901499968860221175481156587577729937034364914355501, 292863972818248323376444552196980190913410766284130121846528221383028255754692795522216210147974308757953455767522231871210681364447388654832382527064895, 938765707587698521440569197645427015656285851871433015306180954283961246645998172227102947303974548943350467849292153257083997108238371916035459394722369, 527868383475124691066635100939010783601665826580600691073307804178304136745331441167389460332847811151296399373142636226352627883562536300885732395368020, 129750341237983016022040701173216833569769431803005060151264307235616875443113006567598272681567098699696914177498752442849179896172622122297189927548837, 760585107411566576292763186517452129957281821905558230733381170579827146053914901351555000111988870051152177746253877358152786229869313536049437555818154, 938763292836724866539021013228365697112352829803299753210331740180236792748742264631755161530673253657950090694713081283849687736631148497830167337486643, 682689221189351038630027039183790750260422214071006310455681297898010722252757554143855688467063007308265257553366528907174872993981625138746823436793095, 1067837436564114828125093331777694734816692248253050887654028470070465592651907962273131972426560328570467580451256501322193533150672588043171188714472302, 1110633200727957030248409035549257335659331280947696872324589355766591756889569682100812348188893076039970166048988359993860887820600381113301292538566786, 1173907280223539160400802625821627215373044711695157102469731432215701678067679892855525991893513749045679886627126808665012442294597020925556959149042443, 335945183939746725135519689801586727674205841122398495771976598606538258814624602858825469615556921118393981574794641476274487653854678191063642603172777, 375918382692404768417870260379617367529573556996789927099845815978831328454063120488176162671177026745178321007198423259307663386232922047912084089550930, 1190356905928617882322563642176112761817776987592410038672173821614635909098818506251592357304295882438483469942484118726592309666992333329150690501148576, 850777261566073551195150404119977629651473843210422854543422971502053042687972256440478567116089451739471813467517764292634277825979759183776937621129110, 1092353805077078639997885476868211623162947498837658062360637710104962103102028856522895420441123367485545136629351256588248095438711842058174054449159076]

matrix_size = len(pubkey) + 1
m_list = [
    [0 for _ in range(matrix_size)] for _ in range(matrix_size)
]

for i in range(matrix_size - 1):
    m_list[i][0] = pubkey[i]
    m_list[i][i+1] = 2
    m_list[matrix_size - 1][i+1] = -1

m_list[matrix_size - 1][0] = -ct

print("[+] matrix is created.")

llled = Matrix(ZZ, m_list).LLL()
print("[+] LLL is completed.")

flag_vecs = []
for basis in llled:
    if is_valid_vector(basis):
        print("[+] found!!")
        flag_vecs.append(basis)

print(len(flag_vecs))

for v in flag_vecs:
    flag = ""
    for _bit in reversed(v[1:]):
        c = ("1" if _bit == 1 else "0")
        flag = c + flag

    print(flag)
    print(long_to_bytes(int(flag, 2)))

• Flag: NITAC{Ra1ph_Merk1e&Martin_Edward_He11man}

HITCON CTF 2019 Quals - not so hard RSA §

暗号化スクリプトは次の通り。

from Crypto.Util.number import *
from secrets import d, flag
from os import urandom

T = 10
def encrypt(data):
    num = bytes_to_long(data)
    p = getPrime(512)
    q = getPrime(512)
    n = p*q
    assert num < n
    phi = (p-1)*(q-1)
    e = inverse(d,phi)
    a = pow(num,e,n)
    enc = hex(a)
    return (n,e,enc)

print(d.bit_length())
for _ in range(T):
    data = flag + urandom(40)
    print(encrypt(data))

事前に用意されたdに対してRSAの公開鍵eを生成する。その後にランダムな40バイトのパディングをケツにつけて暗号化する。これを同一dで10回繰り返す。

くれるパラメータは暗号文と公開鍵N, eの組(計10個), そしてdのbit長である。これによればdのbit長は465bitである。なお、この値は結構小さいのだが(N, eは共に1024bit)Wiener's AttackやBoneh-Durfee Attackが通用する程小さくはない。

さて、この問題もLLLを使っていい感じに基底を簡約し、その1つの成分に秘密鍵の倍数が含まれるものを降らせるのだが、独特の近似が必要になる。10組与えられるe, nの組$e_i, n_i$と$d$に対して次のような近似を行う。

$$ e_id \equiv 1 \bmod \phi(n_i) $$

であるから、$n_i=p_iq_i$と素因数分解すると

$$ e_i d = k_i\phi(n_i) + 1 = k_i(p_i-1)(q_i-1) + 1 $$

となる整数$k_i$が存在する。ここで$\sqrt{n_i} \simeq p_i, q_i$ とし、小さいの1の項を落とすという近似を行うと

$$ e_id \simeq k_i(n_i - 2\sqrt{n_i} + 1) $$

であるので、$k_i$を右辺に残すと次のようになる。

$$ e_id + k_i(2\sqrt{n_i} - n_i) \simeq k_i $$

左辺は何らかの行列積として表せそうな形をしているので既知数を成分として格子を組む。以下のような格子を用意した($M$はスケーリングの為に後で決定する)。

$$ L := \left( \begin{array}{cccccc} e_0 & 2\sqrt n_0 - n_0 & 0 & 0 & \cdots & 0\cr e_1 & 0 & 2 \sqrt n_1 - n_1 & 0 & \cdots & 0 \cr e_2 & 0 & 0 & 2\sqrt n_2 - n_2 & \cdots & 0 \cr \vdots & & & & \ddots & \vdots \cr e_9 & 0 & \cdots & & & 2\sqrt n_9 - n_9 \cr M & 0 & \cdots & & & 0 \end{array} \right) $$

この格子に右から$A := (d, k_0, k_1, \dots, k_9)^{\mathrm{T}}$を掛ける。すると$B := LA \simeq (k_0, k_1, \dots, Md)^{\mathrm{T}}$となるようなベクトルが得られる。

ここで得られるベクトルが$L$の縮小基底の1つとして得られた場合、第10成分は$M$の積(0を含む)になるため、$A$の第0成分が$d$であるなら$M$で割る事で$d$を抽出することが出来る。これを目標にする。

この格子の行列式を計算すると次のようになる($n_i$は1024bitである事を用いる)。

$$ |\det L|^{1/11} = \left\{M \prod_{i=0}^9 (2\sqrt{n_i} - n_i)\right\}^{1/11} \simeq 2^{930 + |M|/11} $$

一方、$B \simeq (k_0, k_1, \dots, Md)^{\mathrm{T}}$のbit数は$k_i, d$が共に465bitである事を利用するとだいたい$\max(465, |Md|) = \max(465, |M| + 465) = |M| + 465$になる。

LLLで求められる"最小"基底の大きさの上界は基底の数を$N$とおくと、$2^{(N-1)/4} (\det L)^{1/N}$になる($L$が正方行列の場合、そうでない場合も転置した行列との積の行列式の平方根になる)。今回は $N=11$なので、これを用いて出現させたい基底とのbit数を比較すると次のような関係が成り立つことになる。

$$ |M| + 465 \leq 10/4 + 930 + |M|/11 $$

よってこの不等式が成立する$M$の大きさの範囲は$|M| \leq 512$のようになる。

というわけでこの範囲で$M$を設定し、片っ端からLLLを試し、現れた基底の第10成分を$M$で割った結果が秘密鍵として適切なら$d$が求まったことになる。

使用コード(SageMath)は次の通り

data = [
(61608417975397048843788515638593839325111098880518441270527767841153782846066445099077365303960932518098100778959123136871039627996767023258612684873083420234538156646585282154245553305607644427220207313162116929585370583379703086997585339296145409828300576290109728682441066135201997295424597733433471586151, 60032368056605168202792776655067640210910930719068898740685488293392455428589220656480049668823171895161714617099267690524276842795335016835073541061601545456195765907623303970146386500563913899580929779870429659650425339185233299118860275385880359287380867251468679962048998842668813298548390941601249105855, 0x1e4433543ad3eab1d5a5490e33ee98c34785945c7b69dd0fd0a371c28e5ff45f6627ad0559d9837fd6439367543ff5670f4df4fd36cbee75950db62e51811f98e3f34db66b07196a5dfbd9867952d8e6d67c43becf086087181e5f78582e98945e5c8c08d754b998ef01e836729f9620cdcd2cc8aae9cb4bf3d8e4beec3ca8fd),
(52084595054768217522676979342755393306305099169414947960508049057119329537162079071100773540172780699842974838973453517862170568297372572652378982794735495836797191260523386985555538123219596180065060457770169661533302156160201909218943628670173938802399175928847179180982290051008255643478089280887936398779, 15937444970326662770243305998311639639802081677519521519037892156989918335411343952028567001158781869582357356721336548356177945486289103616332672857562241745733313956089488246637981047367689313876169403573606972534488436195086998111247112950511965259280728899941655052549135516189815880662766290132607874671, 0x15dbeced76ab710b84982e67a839846cfe38cfccce4dacc585df0e38d695e1c84eac7281d8c83b3c6eebfae7c27d91496b19de120374d08cbccc251a464c2f7bb10fb9d1c1f13b78f1fbfe0ce37d01350978dcb192c92db43560a9cd81481aa2e2d41a8c5b3c67d3e3ae4be50ddf37a5a0193da6f4befe71d5348bd7820f1b0a),
(121675354261226402523384817752122501670754379029920951567545832861118347020889141951034949457467042630795199347469665294677977729959566390358589470405088739543312116123816666440234661644847943610733959265939955886506334607329368744886743083353218982597246897307234102346047327550059519916639261619453107169923, 1958149621008109700386193021020256359555810444022322757777842537494487439895477039590251808463946583928481366538370998263830913239177109491659797444270949612728937519312683847609162235917948298810271512469482956117395111528004250206351805086758526770795159863075378020975086922955262230095667701740508170151, 0x5b445089b4578b115b0293cc1922f5fdb784701fd533eec7ec9bd7fdad995baefb051b9793ff3dadc24ff8d5b52c89f9565f65409c58506c7e79dd787f8e388f019497461fa3db0eac5284d398f9e6a1b81c59ba74677cc01c38ddd6461df029e1179f3ee63ccce20f3090835b7bd7b4de25c38ccddf2ec622cd41fafb49d68f),
(70820434096887624688036248070441718528107270792728727307197623356369639890276828895683705436125317302252834211775910545775001651922925694194466935425170969939539346172633115232030274859268960310846965871663926227518137713901150141826470260092611613639370170779217268337906342955347156686598981918675591938393, 6264211827826908864953215815104077572906230669747226774603059704547415338199956437981145121700015020477626176620200121575740530313039227764537541481272011717745292622796843631960318813842515397395192806936521180850750841260559451018598913158548097304919304754876270597286947644956943158352022152801127867879, 0x4f56516d8e197a8fd6ed76433a836635dd5ad1247be9ccbb5a88ea940f5746221b4bb5b60ef925019a11d36fbe8f1d948e9afb4305937d7e017148b8ba324682d60ed6fb7f3de80031432023bbef81a96d0c1bd26c3a728bc6fdebbd48bf86b93325584c1a1386e26374c9747754b858a01b73996cea8fe4edd2a8130504e63e),
(82396665631738285668995082087133930047188890932442133336046256534530991902128696466596278088102928917626464109384091264437455382690583003229076491363732222934817133536320704449557698925700841043105303694696203472531025908797520768019280257689521302427077849286757365739653728248123114986191011560571298134089, 77541341309162852568860774868359137598587882474829780783306540898574011860779494674673722444562346968736216806881154962981695851598965376893425170303668270087989094501452417979429678869102952038600630142304872749698942475289176861137563927160985001506014089253274664444041660282426708388957971134224538326179, 0x6b35dffadd327c0999efc909a3c1d1482c6a286808801095eec5ea88224467881b4081c1aef02c273cc5dc4d3505dc50fcf4ce60052b6a5a9dc005faad4709fbcca254c6fc1c552d51c8e15fbd8fc404b0136758e1ba57f6c04b1049e303a43ae60c1eb0b671289f6689d1cd104c407549c1bcfc081a28a3f3324a1611e81555),
(64885222129962661919689742957615146346855998523264787345799887210230045803423356080820154546050540728264000944692170729880161760807788699983366314269171423680987673788784023826885067996007133127166699735414920427997399513922777341273346196540175237091469555617281522541592407225697228219483666768990986901207, 47625666889348051674457306461777570860477708163951567694477110559722255361844497439523737482859577232793119885759760321686098657292699849459852343686370029321619072315457562131610624443702007471950020751311592439673932509558946203816066868221203483167079506399876187240483994566182748627389022243608934595071, 0x0f79419a86361d668ced50fbcfa521c5117f7b2f72c3cc248dba4b2b1c9e7dc3a32fa500f5167a0360aeefcb8daa973bc67b0537d641617c2d96d98ee27179de1644b480c120b2d14054db032b42af33b23f8182f72cc8e752d6f89d556800f637bc492bd8eb2fb294eee61bc3c55677066b6962c4d2a1f1896703d446d903f3),
(130307595686638523389042871138355252466828093625912424932382409748014813151912412889866698513547588105179569464359905871041351306187955332098310075195714887141180801001191398677311128761953690562878908997464309620384635922453765468745206262477334243233099872249671186622159533482223573972729351847574480258349, 15517881429792452627724339825487038872077384939873021432131971858090290889497162855962736652640866521963165312583164013911162455865793567436833813352448640307756786561236246631146444590597902995591016928432988304077340670079503467394770901559567924809126517090243024890436892801283564005789256977822007581731, 0x69a8e0bb49427f3465c9f3a41a22e047bd348c886cdb07264a321f8b890bb48cd7a878e43c1eb4b2f496dafb50677b3eea032c8f7f2ee59695398c56cc3b183bb6e2f1ab2d5d633461a6592ca0c98c0f2dae4100d6aaaf0d1166bdd46beb68b07d9c9cf6c5a92ef7db019dc065b3a8300ca25b50cba51a3294d954c178bf3770),
(65386448419573832864151040666988491321490532636782967162806795276671017479566436411594017000387653366263378617189553041765586083217125727980734225153709370447270596363822524978426540069479632490507360491377612488876553715272119578498102854909764339676652952568021321118127618560269626549257296451954041925283, 62417639911670877600600895776941278119707067464948560335387709799367122896567813566638216057171867961437006927011778910808189676129022776796728833211435603542364704330783289218396426543693678813151580911213239650850603907199690825764030369692366216968117035006819175280930722880390482701178418013436415892711, 0x2231e71788fe0fec78ada4f24a58bbaa5b1a0fb48dc94b18bf7409637dbcfd8e2755d80b5e4b309e20a69474a6e2eb245e40c1b3f81c6151dbf7e6871e90a9616a32f4a8443d30bfaaff5d711be39bc8f38c13234af9fd867f508b8a6b097a49fb07a1392ec08c38f0939620cf644ec6631f7566b6bc7a1f1d01a9c736eceda4),
(131618812326147470215836136712095159211663684841466199972335887950664101678748935713203393931245541362772506324940879455504378545672259298894346211770983161798960234145317156224604949365110464634198678301644727985645228605590810190481288852412139519629077007437022950591320600450976104529132138396249413028099, 14318453997383587408499979509282945054981178882287936277795320451723285671391694914929520724692059461777785480850364952738183846512279857119933447174333240691522012746191524101263192457454032837995702952840654708026147079321112397181981380295129696518148352311994008219805602114421675331461920408832158576071, 0x71a370974f020d338071e2b0480f38f2d5b488252f5eb206636d6dcd3c93ea586a507c29d2e611a9a8d5d0f849b913116b37e69345d6eae71cf87cdb6b74e75bccdb374c372562777a727f07e4272a5ff17b451d582074b565879453d028c5e9b91cb67ae923f0f09492e508422e65c1daada0564d91a9feec094af77ab190fa),
(99041226655569332839951771030354960649881033648844611842019981984694036670092050113949713459076512100815903654289240773362239468428010238444408944822516190193861719380849620966232652503444079295871086550223067647300451354087943235559953597249075277760677450645744584993036921709483731953822197438848939991653, 45917328654051873455626365238806652384056265616606200025887647202756379007355041189714541493038574645714670682101129613041399879280497291675656671383417575172090283625761438606371062142083212903854592596935358334738253893062615061401134834123551055465985828525720791523020773994634134135284036947641526947783, 0x336e810e66eeac255f1714b290187773de92ec044b654a4cc0eef2070e9d8d86fa37d424b2e4b71fd135e634034e06dbc31e77bd13d470aa5d3e5dcc5e689b565178a4a445d4560f5569967315a0bbe163ef83063429ec8d1fbba1a8dbd9e30a2a67e17793f8b19e7b184c3b989dadc85b7f060e3daefb66ff803c98bda8862f),
]

from binascii import unhexlify
def long_to_bytes(n):
    return unhexlify(hex(n)[2:])

def apply_lll(scale):
    scaling = 2**scale
    M = [
        [0 for _ in range(11)] for _ in range(11)
    ]

    for i, d in enumerate(data):
        n, e = d[0], d[1]
        assert e < n
        M[0][i] = e
        M[i + 1][i] = 2 * int(sqrt(n)) - n
    M[0][10] = scaling

    M = Matrix(ZZ, M)

    for b in M.LLL():
        if b[10] % scaling == 0:
            d = abs(b[10] // scaling)
            if pow(2, data[0][1]*d, data[0][0]) == 2:
                print(d)
                pt = pow(data[0][2], d, data[0][0])
                return pt

    return None

for scale in range(450, 520):
    print("[+] attempting ->", scale)
    res = apply_lll(scale)
    if res is not None:
        print(long_to_bytes(res))
        break

• Flag: hitcon{recover_everything_by_amazing_LLL_algorithm!!}

pbctf 2020 - LeaK §

• 問題のリポジトリ: https://github.com/perfectblue/pbctf-2020-challs

SECCON 2020 Online CTF - sharsableでも先程と似たような近似をするRSA問題が出ており、LLLはRSA用みたいなイメージがありましたが、実は楕円曲線DSAにも応用出来ます。という問題がこれです。

暗号化スクリプトは次の通り

#!/usr/bin/env python3

from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
from ecdsa import SECP256k1
from ecdsa.ecdsa import Public_key, Private_key
from flag import flag
import hashlib
import random

g = SECP256k1.generator
order = int(SECP256k1.order)
secret = random.randrange(2, order - 1)
pubkey = Public_key(g, g * secret)
privkey = Private_key(pubkey, secret)

arr = []
for i in range(30):
    h = random.randrange(2, order - 1)
    k = random.randrange(2, order - 1)
    sig = privkey.sign(h, k)
    
    lea_k = int("0x" + "{:064x}".format(k)[10:-10], 16)

    arr.append((h, lea_k, int(sig.r), int(sig.s)))

print(arr)

sha256 = hashlib.sha256()
sha256.update(str(secret).encode())
key = sha256.digest()

aes = AES.new(key, mode=AES.MODE_ECB)
print(aes.encrypt(pad(flag, 16)).hex())

SECP256曲線を用いて30回、ECDSAでランダムに生成されたメッセージを署名している。ECDSAで用いるパラメータの内、秘密である$d, k$の$k$は各署名毎に中央176bitは判明する(頭とケツが40bitずつ削がれている)。

というわけで各署名の$k$を$k_i$とおいて、$k_i := x_i\times 2^{216} + k_i' \times 2^{40} + y_i$とおく(未知数は$x_i, y_i$)。

上記$k_i$に対応する署名を$r_i, s_i$とおき、この時のメッセージも$h_i$とおく。するとECDSAの構成より次のような関係が現れる。

$$ k_i = x_i\times 2^{216} + k_i' \times 2^{40} + y_i \equiv \frac{h_i + r_i d}{s_i} \bmod p $$

ここから合同式を外すと

$$ x_i\times 2^{216} + k_i' \times 2^{40} + y_i - \frac{h_i + r_i d}{s_i} = l_ip $$

となるのでここから$y_i$について解くと次のようになる。

$$ y_i = l_ip - x_i \times 2^{216} + \frac {r_i}{s_i}d + \frac{h_i}{s_i} - k_i' \times 2^{40} $$

という事でLLLでこいつを解けるような格子を構成する。スケーリング項$c_1, c_2, c_3$は後で決定するとして、次のような格子を用意する。

$$ L = \left( \begin{array}{cccccccccc} p & & & & -2^{216} & & & & \frac{r_0}{s_0} & \frac{h_0}{s_0} - k_0'\times 2^{40} \cr & p & & & & -2^{216} & & & \frac{r_1}{s_1} & \frac{h_1}{s_1} - k_1'\times 2^{40} \cr & & \ddots & & & & \ddots & & \vdots & \vdots \cr & & & p & & & & -2^{216} & \frac{r_{29}}{s_{29}} & \frac{h_{29}}{s_{29}} - k_{29}'\times 2^{40} \cr & & & & c_1 & & & & \cr & & & & & \ddots & & & \cr & & & & & & \ddots & & \cr & & & & & & & \ddots & \cr & & & & & & & & c_2 \cr & & & & & & & & & c_3 \cr \end{array} \right) $$

これに右から$A := (l_0, l_1, \dots, l_{29}, x_0. x_1, \dots, x_{29}, d, 1)^\mathrm{T}$を掛けると$B := LA = (y_0, y_1, \dots, y_{29}, c_1x_0, c_1x_1, \dots, c_1x_{29}, c_2d, c_3)$が現れる。

ではここからスケーリング項を決定するのだが、下記参考文献8では$B$の各成分の大きさを揃えるようなスケーリングをしている。これに倣って$x_i, y_i$は共に40bitなので$c_1x_i, c_2d, c_3$も40bitとなるように揃えてみると$c_1=1, c_2=2^{-216}, c_3=2^{40}$のようになる。ということは$B$の大きさは格子に含まれる基底に比べて非常に小さい為、LLLを実行するとその内の1つとして現れてくれることが期待できる。

現れた基底から$k_i$が復元出来、そこから$d$も復元出来る。よってこれを問題スクリプト同様にハッシュ関数にかけて鍵としてから与えられた暗号化されたフラグを復号し、pbctfが現れたらフラグが手に入ったことになる。

使用コード(SageMath)は次の通り

from Crypto.Cipher import AES
from Crypto.Util.number import long_to_bytes
import hashlib

p = 115792089237316195423570985008687907852837564279074904382605163141518161494337
sigs = [(73065259012986296172162600130509405474599075774327589596631188252611047316256, 33964300656368154908463421837005045114399560232738270, 82894354853519526232501734941523543465298626001572857848389304352505207427358, 36490061653005810562190081674168818228310589341963072490906079554169628568132), (30450984996954733791275597605491959526178885437275695501338341866523152633242, 71568795634286892105266740773117872305535663191433771, 30985572706467560535112208834986984525636076513540240199425453868889258718450, 22238336351858085353416040603272761010093785389912572730851373350463009177628), (36084299200833245160393815975668328381407935272700375595862751546268827850829, 90859339930476824816842975847539531351051633452940689, 95547691511932121475627743581846468183885440858023135751833077945915641665631, 106784506093122510181756427206737444451711888563351340360918984868765245224208), (621098717605866262055918940389126162192373933559410590896029103951194315686, 90959741323167907970339487873680991954115408563713225, 47865767068052365663328012166131606247938494812814168713834240375581510798141, 95899257283617795472346335143395960787201083922346604297719466447725025727723), (23606807773889185445551103499556850104978872671315635705508770906133649548348, 80441849940943062379384198806057882393330312124894873, 30934286008406006805187351525685268775266129612075537851490061653267980149863, 18457869929997595150435420811845170056680184766025627789509641879837682367160), (98454794375350670595588849848057841865654971388372303588330235124144313103034, 89890952879853698931425725502522124397244157054214652, 20957328509201369071764760746870031958706880275321867060322960723932528369333, 97912953962792888186538778652110028604731904319179746324840803927069934482248), (51509207120043028671658865683292192724987352158121610133591380170240759119595, 16833776589947632047999214010376137597219689085947240, 107145097135548149185108964798489156467951168013921456346264474140317197092291, 55766346247571022448902172419803626728747674760431840493990470149567906232473), (103388801103569320986057884695057028090388551305845034951980645083633776914221, 8301609756476135573170894455535567268232755475081715, 27874805311401534725386615110141832708981904162564101791326720084348749595216, 30990954125298888694052606635120902068992842107926982005326331652941974051643), (89969906957551946190633208800435926364801247190517764020362518874767845656246, 23316424784406523354907715932426471686035048782704409, 34981000689589527386524994558560604061759398569358325614712300196463703828858, 64108285981327865598725846211969948621446559790883007851604255072933006064862), (94387273459074347891424603573020924337777473587784031038568934177662278518163, 9066766732451191877946507476794538466093754135000831, 66891009849667040416504885684829379150568470034680414805140167733119292783803, 40939167499570752898735779568308978575102723457215746444736678126721356483917), (57255081785909877342311739858734144826564985167769418191770546100734178139022, 53717449398528184622369868753147780090454102083993492, 23659719841501329876943589795816046643165260024769432571607657398569644362093, 88368391722619744751660978995088693026047920931061667212749700509709731806199), (56663610680482008999832994127234443638389308185320278376227503172066712674026, 33412015081086711978604497030640222040045491708429777, 95308989005824755055425653879149406689647055982618927887789915528032557834016, 63466029487375389854942398021214772301863180900287057363659629810789302818161), (114109529930916226703095551553907190499331288821964853761112518989058248602227, 38688671937840268787478633863623034311330321303970160, 52415231581599283624796514437189671957836282704449807127396473709424760852239, 105848503929909160925121515750643171097102455122322448650515375087599193839627), (90309767283035851448314644176853407540275900153267515421450785374634833628858, 628321260634938982869025703429495475937484114686788, 67849984289605760977782817332586119886568960506249272733571405131409810358215, 80950993081512785914457196057546884825245583602274183701072639842479110115862), (61698596178679285122774907794734807972374000798775328353769422083285523873799, 1874850590340991676459707511151802504359796969955275, 12775779784340538280076184178778270335749410912051815649824539859649825690679, 11797288785207402035695342032210105289212974959200350810411027879141016496785), (61175964046404140043744416250714734061239872817418520995802455925173097602961, 22280716493522848976884076524261751314938198898148664, 97595909250775255935001516851006785816904214893451723381768451843513994249190, 109856457889349054325255130798038934162450693223870741069934429180984672450223), (47583855623223403290231638707289034881302812538657963378589737943843171441222, 43336442770012144299701827826767247193588238756989129, 95216458311536147994912406899287046290084869095499470086808389609610316100125, 92158540177813221944796482313251046163839073953583354341315686014417452691694), (75821074355965797604707054317476085586097157847267624943052837179333854045146, 42382578071877693489582387579886645664683122606029482, 15896410419620072355833970195357751807570701743799192519697031680558227231592, 68436023768648562516393622605170591178793843463802515122757184868479701169323), (93242430370968816337352624601826520191832478111425916853187937088588994304339, 63404219404345899072849591579618837925519891325288823, 36632517119456647033689792567964980792455139594292669001928969261149008158013, 9233415740859971239903514380410794529482996649309752216895700430267957150444), (114786936617980481194888012221858456163069609158379084902784589263304531791970, 2441379599780606792828068074369263317158840158086801, 8129340069472228581180175780198439268953400478117681179354433751863313504265, 79245836416071401164965959341494079159308247904342258343346054020663466268071), (77231591304252624429602509814437318018450989823767330948780306016760575918762, 30654443197091307944610864864294964533714109922079810, 67435612005563993370976744529162645985911724706055989609439136050680668987547, 45016154848487611592791611851821164153072606305503515349522764594104651005980), (37168183938515207195844376881021329709786540364271177960152474236408320789806, 5727565226352645909078519569821885286501563268347064, 67567337363042970746704245026303526061525198070949995128820188364411793196498, 37451986484301130845230379144988635777710070523765117823998156584143312613037), (68744739571987943977059840733366279639241921586447921588122203196587422744479, 21884620392678970447000022316224131928083007078267113, 45313549972944389560668061495416924394416382850077847247870377141875772267932, 93984967667631675553348458892833490683029954862079710443775858205270832143034), (21567774806957561725348961030455963996102739685072029640566867090687159740982, 48254503747103162768204345113072081691978893516061096, 51064507652182282793406500663329898239217305212305371317877469783456124305850, 40703086445774146575310976468370592710178239241355447388964097717865436215486), (4386370650317256964520331403757743198955025947564820509709462387236358888577, 70118890361264615250155242967808047626173172621765834, 15356553499210396632653252920783493820610541877882024657094013208595205567883, 55432337341302613580005075110551735850006077620939708549067551024732319389730), (105106631798438768406878418094329923074127733718064752474192209978465350269594, 44091529476659479944279068059877901801096172689767404, 78630252818742034872205823216998432607805248240171478373562437245494057626030, 93543279563619667417028771759367384340964823371510091211447674941706510086181), (37255514724827821640824306661403264620990142415607134033290137584367472423588, 5606923573068800564277772224070017263219904410078407, 92788076500336458734532816880849256945908260088042017052624552546206537899122, 60529036117080717912863055636984175576620311435086776790037938074854124458865), (22094520557837757428395820988106108511507651628840273196967929961692424854753, 73320844185855509278555351797771299275864173236423832, 90832072698116709176457507514455021189271776664719728271816258226210210676857, 65599930576650258351968138842026193056897866302130904871544694218954643006164), (44482976894320088173116513040730978942148506438640633002057290913628820741309, 33870199936741270291969120798649736292740080283683599, 55256324162439108227286409622085880453794538850614132365712186312434999048275, 37681615923422697020735753444438840422573578716872622150261209194582296318182), (41842068659515038936230020254814883309195821555594877503924997633306963967868, 94974264925784794571875977018755772829460556811069683, 9806218081808205855066374609875168464792314919147905913932538092706803955249, 687552341529367481203688114250117212424656667729490846453893193584974998922)]
enced = "8d47217b47714708b39befc5bef252e621d3c10fdb1d8d6168c62c4f7b981c185b44a907c9db378b1bfd3b984262ad157ead801493286eb877e7c774978c3f4d"
ct = bytes.fromhex(enced)

m_size = len(sigs) * 2 + 2  # 62 at this challenge
m_list = [
    [0 for _ in range(m_size)] for _ in range(m_size)
]

c_1 = 1
c_2 = pow(2, -216)
c_3 = 1<<40

m_list[60][60] = c_2
m_list[61][61] = c_3

for i, sig in enumerate(sigs):
    h, k_0, r, s = sig
    inv_s = inverse_mod(s, p)
    m_list[i][i] = p
    m_list[i+30][i+30] = c_1
    m_list[i+30][i] = -1 << 216
    m_list[60][i] = r*inv_s % p
    m_list[61][i] = (h*inv_s - (k_0 << 40)) % p

m = Matrix(m_list)
llled = m.LLL()

for b in llled:
    for i, sig in enumerate(sigs):
        x_1 = abs(b[i])
        x_0 = abs(b[i+30])
        h, k_0, r, s = sigs[i]
        k = (x_0 << 216) + (k_0 << 40) + x_1
        d = (k*s - h) * inverse_mod(r, p) % p

        sha256 = hashlib.sha256()
        sha256.update(str(d).encode())
        key = sha256.digest()

        aes = AES.new(key, mode=AES.MODE_ECB)
        pt = aes.decrypt(ct)

        if b"pbctf" in pt:
            print(pt)

• Flag: pbctf{!!!_https://eprint.iacr.org/2019/023.pdf_$$$}

フラグが論文リンクになってますが、私は逆で、CTF終了後に人のWriteup読んでこのフラグを見つけてアクセスしてから参考にして解きました。また、CTFを運営していたperfect blueが公式リポジトリを出していたのでそこに同梱されていたソルバも参考にしました。

載せなかった/解けなかった問題の紹介 §

LLLの練習問題にどうぞ

• Plaid CTF 2015 - Crypto180 Lazy: knapsackそのまんま、ソルバのテストに
• SECCON Online CTF 2020 - sharsable: この問題をきっかけにLLLの勉強を始めました
  • link: https://github.com/SECCON/SECCON2020_online_CTF/tree/main/crypto/sharsable
• redpwnCTF 2020 - newcrypt: 未答、他人のWriteupを読む限りLLLを使うという事だけ知っている
  • link: https://github.com/redpwn/redpwnctf-2020-challenges/tree/master/crypto/newcrypt

結び §

LeaKや(紹介しかしていませんが)sharsableは当日挑んで解けなくて悔しかったので他人のWriteupを読んだりして力を入れて復習しました。まだCTF本番でLLLを上手く使えた試しが無いので駄目ですが、近い内に本番でも解けるようになれたら嬉しいです。

また、未だにLLLを利用して合同方程式を解くCoppersmith's AttackやBoneh-Durfee Attackが裏側で何してるかわからないのに格子基底縮小に関する記事を書いてしまって良いのか?、という気持ちはありますが、今回挙げたような問題は他人のWriteupを解読出来るぐらいにはなれたので良かったです。LLLを含めて今年の後半はCTF漬けでCryptoで使う知識も増えて楽しかったです。

明日の担当はPOSIXさんで、「Writing wp for hxp CTF 2020 web challenges at Christmas eve」との事です。hxp CTF 2020は難しい問題が多かったので楽しみです。

ここまで読んで頂きありがとうございました。一足早いですが良いお年をお過ごし下さい。

参考文献 §

この記事を解くに当たって下記の記事や文献を参考にしました。

格子とLLLについて §

1. LLLを理解するぞ - みつみつみつですか？: 格子関連の用語はここがわかりやすいです
2. Lenstra–Lenstra–Lovász lattice basis reduction algorithm - Wikipedia
3. LLLで殴る【yoshi-camp 2020 Spring備忘録】- CTFするぞ: not so hard RSAはここからネタを仕入れました
4. [English] How to use lattice in CTF? - SECCON 2020 sharsable writeup by Kurenaif - YouTube: 別の格子の問題の解説(英語ですが日本人作だと現状1番わかりやすいです)

Knapsack暗号について §

5. katagaitai workshop #7 crypto ナップサック暗号と低密度攻撃 - slideshare: 長いですがknapsack暗号を扱う日本語の記事では(私が知る限り)最も分かりやすいです
6. Merkle-Hellman knapsack cryptosystem - Wikipedia

biased nonce attackについて §

7. pbCTF 2020 (Leak) - Github: 公式リポジトリ
8. Biased Nonce Sense: Lattice Attacks against Weak ECDSA Signatures in Cryptocurrencies: フラグにも書かれていた論文