HITCON QUALS 2016 - RSA (Crypto 400)

rsa_collect.py

'''
http://www.chesworkshop.org/ches2011/presentations/Session%204/CHES2011_Session4_3.pdf
First part - collecting CRT values.
'''
import subprocess
from sock import Sock
from libnum import gcd, solve_crt

def getHashes(p):
    return subprocess.check_output(["./sha1", p]).split()[0]

E = 0x10001
N = 0x29a13122556c6d6eda2cf270bc162385d391a27820f5b06b1c76f30120b24091078ae2ac8afe206f442d91334ba2447a35fd35b60940ecc93bde02eda7aa0079ab7c5b009ab37cf348f67d6690d1c5f9b993c6e2f0d5de919d50376f480fb821d3c7d32d5177c9118a37358ebff2aa5fa11a09b4113a35bc3ba0676d082dc559f36f6f7b17929c713e159532d10ea3a2a7bc505cfb6c2e9c461b11e0176696c82ad5022abb41add8d2cb6724699b6e85780478eeb2cea01f88bec7c1c90eaad40e89a0d1a9cfea7e5e543d03693eaf042b86b21d18274c98ce412d3399ee4d6c49b1b1b7dcca5bc574dca980a4f91b1aeb2009d2bfc565599fb4f36201688b265

for num in xrange(2, 10):
    correct_sig = None
    sigs = []
    for itr in xrange(20):
        while 1:
            f = Sock("52.198.13.246 51415")
            prefix = f.read_until_re(r"prefix: (\S+)").decode("base64")
            if "\x00" not in prefix:
                break
        sol1 = getHashes(prefix)
        f.send_line(str(sol1.encode("base64").strip()))
        f.read_until("n =")
        f.read_until("\n")

        f.send_line(str(num))

        sig = int(f.read_line().strip())
        if pow(sig, E, N) == num:
            correct_sig = sig
        else:
            sigs.append(sig)

    t = gcd(*[sig - correct_sig for sig in sigs])
    crt = None
    for sig in sigs:
        mod = correct_sig + t * N - sig
        assert mod % t == 0
        mod //= t
        new_crt = solve_crt([correct_sig, sig], [N, mod])
        if crt is None:
            crt = new_crt
            print crt, ",", "#", num
        else:
            assert crt == new_crt

rsa_solve.py

'''
http://www.chesworkshop.org/ches2011/presentations/Session%204/CHES2011_Session4_3.pdf
Second part - factoring N using obtained CRT values using lattices.
'''
from sage.all import *

E = 0x10001

if 0:
    # local test
    N = 21386700774958815655535521896772139917665116848975521134746842248858195217539550963570797874909573671107366650936364194514357263446118092127549276462867307291946375107818919840491892450434822357350513978545610195131592402908084471887957548326898155518018674229188152732671144688998697220833201252812099669066883273726644522661242401969935248604685379563255769692828094128513917172816215155105193288305566970209759306795313033179852760599204727359584032034656640080780696345394621390793105944794644242474395426066526256964374346822530599727182077104409960379284732539712341970385499911565061671439146465434558105824947
    vals = vector(ZZ, [
        #local test
        2943957009530043904086751306634794051817542723487486986382125607495298294746610748493087432335699321617182685555586811709675237511766495987533629615128631504850579996269778575379905627073230237911785968050661770220755833624849648356018496598687643450772931062646021234294917601905566044688211346604786303853499859757107537567529831497907913492739868955809768474869789669076889863694584456382677559374351996587427150415863761203963921501289224156005986506757798891140646767160468596293310349760878416736517452480701907767497161714056786127530342014014683606282783530194510746778699882001546814097112503114304366554796273601048786428601923722756949682499567973004671830507337161181891634132780429679918796176122536882605137779217342854297247840624123742439251193347326268531067325213987437804511963200769017028508006139557994447024104981794138280249416885650138570548862989906176516193038438285355005360706194943382286473320957 , # 2
        1798911674605363842908624596171416687574343239841363498308478261309226862184434518228849571898421666923977382643158036684363927036569468294410360053382744282115051573442865637230624091949727772710488059870106232821984735489607772151567252322093893362105091477613141210496449242943089826422643387779884554336674334717027428959978443946810646540860718692916384601722816317167396250491308048210565403375064814223323085455168776500277567823516306731312397717173873034977531842833285428148253821899104580951920599187807795739149604163986760264582680982206240451577541472988339271407771180590710951851161757261619462192848290725730316307640525446536861329320841476364676535072747207292660399069379810501169914225441158032279541811345096421847798694382222794752009306071863629036479745658252815433207308360655051902790550529783001132711980715413005032938046294631206696949909318293870019703230372607352049610728172200099686875635944 , # 3
        1568683856174833874266723224759441465132997100984094832305656019656606810090008906799718435847266893164586805367089813330104124850280265486795042544722390958870451441795296496527609411512276846762350065123435422027235555016245812993727609608152479825007617217196607610071256487373962172918499703441220382786183681843999544615576655519138604564978469789249479000781876157592857255727072731255766822688616206418332742948187627285688057839422296509170170720593379587925139602667202982964568197185226951738639872516643895178017610525761998577804438975602676467817189047574257588730944238308180316046740851181903099356843823094202031213546111575913664185683560791458382959426008008340792748927676962623546000966190531139152373932443918670249552958208918671375592317511525167779011207982294020561355425360763500721349567879788094219017717363960018879301265602220820959046882443345346656545201479130700457833069976318118541741279850 , # 4
        739296367148373429932995801604230387747604479849687739695582079952751473574761236436700581688488449088874577671769594324508784061429225301000287386695848228004292317075979897103391130939310719906248866593891551296242265490945913773477205203164253791193282610483962463811769311627373836281669408692758469786017017275326322341256410403470855812448724326916748116887821679474705204560933487527019892140320122234565923736266151008597740710895712511429908242383544555134198642342283011596215197346549667735821611832036942321095442392707691083141977114075198417595529855694616495008314905383547785748342310386122869036815784254634331013765137757463894512090053750754018433210440294292976162650625865629698031067805118266751604240278670962515973838691705913736885304706966521398841048012688561644052994976140528542289348614985838581027027520707857004355276453134577888486298960670854143068628067473768594265484307915719908258010789 , # 5
        412167521368551119174933910248776084476382751871318722715127043544068557196569997727620563690481169704699977482844389993960782414590539999299154205268980986096771030381327684534587454757896992540251477989543524343850083898480502551614613371440539434071944805970844779618228441481351784885037273974334219501149548720408270064459949553377673226435160985242542847839004767962088088093775703457873812437010654792062885325840858024597333668896759632782509413914244009905049547113387656183808096239601693223946798711331029427808758862739634571646131599791690545570509256462934494177769411591265364365491244077632229041223556967522886496435548731251171966467190313543106017297190922502594645581097486717288828916787468039072957085357660362513918579095215710084343226036180228323325927106549549204392183986349022741617417553113531085252252288988844157903562399929162307106385369656927532982480905457486083651621455527580053925434452 , # 6
        2435471286611385232632084862189785577578070651285921405791985746264575951286385294068292484625197907933449324699006687807670511597728601382863943127955932459107949352975028327860692738419435739461333268694832197998323014244053721378433462162202503610984205526759457129168177025324954017159428090348475888303206182712778176843277732161639942476639078619077681293962274238773596368904936891940872100002272634514015965099062112652164218638137461597792335311988408778427834374152327031658626895578481637628241455170109775087444659131562937342680915434235718153597922139301268326123514475007672372517695009750889306253225252160575126856300946286643628917762659718904437683156690555084451188139820309989618454074102328691582778010954464577434527906697898694571500658223428164458533135960447693995772794837156452009547466813294032120878918995000603947641591820185733549468107820378925882326668107703428735565365731315028455889596079 , # 7
    ])
else:
    # challenge
    N = 0x29a13122556c6d6eda2cf270bc162385d391a27820f5b06b1c76f30120b24091078ae2ac8afe206f442d91334ba2447a35fd35b60940ecc93bde02eda7aa0079ab7c5b009ab37cf348f67d6690d1c5f9b993c6e2f0d5de919d50376f480fb821d3c7d32d5177c9118a37358ebff2aa5fa11a09b4113a35bc3ba0676d082dc559f36f6f7b17929c713e159532d10ea3a2a7bc505cfb6c2e9c461b11e0176696c82ad5022abb41add8d2cb6724699b6e85780478eeb2cea01f88bec7c1c90eaad40e89a0d1a9cfea7e5e543d03693eaf042b86b21d18274c98ce412d3399ee4d6c49b1b1b7dcca5bc574dca980a4f91b1aeb2009d2bfc565599fb4f36201688b265
    vals = vector(ZZ, [
        13055492904502341131588024100908592043729147135346096808892447834102375345939047327738507161472726590471789136587461299899120076030228753979228273055512985364496018881353327913129575682250564103534578365066913190278292249342468704111386669280707954706700327957427028070428992970070168372162238115438909146414174605847655210956682796245676647996035697121188619336982710509987651309047245122568287314830370231629378279157064393343669663745024334095811906155464673731720900539938549874978280210095517236310506456529786099511967926000050345964511082296300530433483042011084632430158656156432007111756509309489644479582678111497828801684945609114286127602000266570494520503719676125737352874723633154942379910855838160594302861922067910630847312180186811894773064696826806429064352737168262649582511481603846217098637589566594808651142363495988304069504391425143336362540984664342254567008325388872908686444545585554452943662886734 , # 2
        18454850279437893332957352835628174778345426381868047674023584219692205759196331183205670771033827991250923526595439953485204363237863959730517439280403535900152266548103485273354920455247525573333000235203572070397597119662474671192094308781511309829408483402914759152565052547903301991611028180876352436381030323684102455507135340366299172876867868146616121756169662900297122541466430145271612110251712357600758001979687802346825542868436654059470231282065133632537033791857009049983928530399821358997107025368777191267027991077993221304720948321671375148735446220254436303210304308221873575539512089218340461841980043316390796764937083063437512247634475709444574288582904098157962424745780935447724847737275520870664025944578981397754233654012838550704355980639807209344622983572344264972131230758878706501917327397766355831366351730387401264257991399467630871923996194755961122126298419765496243995887968482575918145014389 , # 3
        4769372576546978001176238351381976930622454715477458501974414004185237824287540644626860334353783359811489427392075257255093120389749803789561013818725183155512308025926047632252065037755711460183024281165033380678954711116023365226712772696215732523698837653100090302866752986356270901574929023486565747629369790267736348357079533333840834601287243213039268933313882224649245072978194922344525304857523632176079260593272671650188754855510828625965588763596248500700550388171603338083964584737226776217547464567479968097185082670854038291969834426210065569663338394217406060415758016299065881223601841954265990763173908802896357050497208012439418570604128682547607927639658134387051709570716878543861769617412669527752824092820591454264206272540208640380643808673461013336017122787910403303271748246040075907583436027086978342967890712868880895133117871215256825386119247264122736961305531316735123725930547221547268457215774 , # 4
        18570509834800674811856326655502744031202299672112489601587621084830841201865366714966209184870878084304454987258869137765127155795554430172150054820277498629107031750438963751462732931915350547150224168884886553970705869252717776144663856358996208745578183952475107870578459470688177070487476604658120562625602537859321809847381347262638550159608317185626621818000799895016770744921719676272171650483386233420277554442276537994116450041252856763909627713914698257724071402187189680369029794093412206223557126762012605240985911723045476206335350849831832779357200755561106713973957700460462035586790916093338007337385840600846554222758897818004378180382218306758900531819675490848415150594077362064888829127077993435558854850160027855564946542017185392775467973864288237366291770720416205587854519778819725443981655482955678193117915942694814104256030079768061134035324069664850798993342656797846977952809171399953616934679177 , # 5
        5098062670117871547140885121734301349805205453744612192931897705968935009935996241278311843870226518674139419190087056828958691527492673646944029795330360816629484275759395726460538122033535647132449458528385643013987926045237965241474199066469061276044702375288271022722078552877708568659267674193718613643636779814126001018939974337988791151531839068185388392751519323002956033215291087118930019956241582724990781804450706600357154443692261251812735780489041224426900279581397512476861910272949227589375008669210441998246732145885957879840637627496868109666514700005082136906101356200530212088704136213195047434827135653566342154001384808767278730413935430035198934364546549475409485981029620782288772080768170817001575088358533177858594627555191851352090344628217783886898154408524632235842024753134002389144640430806573382707075644665181366295900354795961754567017890962133040917682087659583424125976767924858908766330523 , # 6
        18859129046172794580324068703526514289980311271171636004404405503592873448316714175430286336552471272010574688480156209042646575310279574350471422911692526109931797065738744589708939097015714008884833714542045831753893275556238617785626417547434582609216779118317239014507847195782953436799743537042831226155591950194681769631762252471628103720243351596842204567281026340130788869037385536961977468164302958258992498202222216645428022404616886433745569849651276742871181749047666315942413707506508530816481330329784623217848975395322782944244456240507515269485675798549194931575845159803961264660098317919447588661929041463202902883566760405154778764255314722633612190763512601217024768623423550896285783557743366098917719422928721799744798130878519097629339650160481406407291362520360064441182053263947697842961148221898936805546406738838727103444502420179303151264012050423536412351538706748672288794071282487759805916908042 , # 7
        12490645677922335301656881400658944971148005500027710645585221372452600044047032493476581202338447844342818239975081683076952248681626712105706572345929931109290801743549427474023177573992587543227049283947380434812290275299390466417087609698928760527865815733224448706016640777285295267365291399691256132735913570372762253186423736383550477152730167692613466093025797699275040732851979472484951735226025711616472354059159768104919477254562085026486062699996020559354591256873631317475471833293383523194417915496585259555162898272050258102554193531953482269867790090813172148326388558132413319396472509525527901577967467553726225559953762230741644002674199321794049287537952688402731313027901532130595967696732445990992400366374870916371501237829250456409621518934202549114619249476793638422350149764693411713060095120371909800409211126405072325948583252363415721377429834658698354998614013747646955832901789381163397871565958 , # 8
        # 39548783189381851033176067366800959643743184548941742763283622787963390670668101250506107978171207794500478288287027959515764897088044330582961300747471014752635002826433482355361046442651507770217309585491330186967569179340057597457363187691003068035493414406406849669966464356139015130442195666042506152840157856844154521133510821665800972452454892653751804605901619910275125286100657673566743505474553773655167503530678568460485258140164946373492556552732097906989471930395862439968350975154154913140560225652401166622846587292600715550792285258171629532293374905837156489573254712437744963070322551164731678335259181994328285707498205994149626121700293224738286679482438585493396598792287291364386901618443660200617439559855721494686255184154204276373516416390354644396638018145374740149248175222828377216530634701328996997388053299088027545679495222280219534987553784060124611218774288294150779136624127301643284664177456 , # 9
        15347711217158291180278004402710668977986392885982265687112839261376515677726242985136235814214398873191832169937637610867304112426720579640973796208115429264252220622246521306837743275193414076284132381548246852960309688160326448679936443051534186433795548507048513098941587310396741564299527099846595045361429855124898552020502414524130139339874450551312560040891281661326769078436689526949328407122649210006202508045727901158936436910510648190729236997507383843268363060705627268598087827283634593715734129983256141060464255034340613084488977384783300889987404446413070212531366056716577150089075257635430795420787291010163325823718873674079211207553658501594354971748233263735422254546138402944242710910387701289874032853723776829499697882500946120464274291773955265498756163362610770460324486994317924555838758862009127455252807383408533282902147860399530732206806823265928837080876386230670807714701049983358720733188380 , # 10
        7426968508212422809076725393907552719887516419183221539390045837875693923078123592971869034258663595448499719431687199262691922530688873789451567419397157379720275372526014169882314169200159674969276477731730494718466732379368650569428702764357526554788237333131883280495611669541675891917457525630500834618118988961094365490592151036946935908051319756380844565514160106334203544015337125716944561335480822606946157348525273484930883077064473298743974045127971210142370906142563558632446402586576357034619689011839025675572163569891010082707897247277550689507422889767032889738492287883306380219440123697521165489747303628543070222619204708328505580265191865708458314872858767378207788626590240697864851540896925908369130995521056791402570825710735155416047130131352043999100212855355791113672370299067469677870159707377757706359268585752200195393607567046227266326332119567759721609813751866564132626215121707328405558266410 , # 11
        8330303582074804888858569167170681045710091501189714436715008869256718315897532114345386968201130678185065007852693979263935478974789790465667677481924232874629279437026750732951640378056075636421729900602574285974710248287612548497753395247329272984686174935395879913509184776328965760735519205244605744312241349177148894362484605037345108880884313665391606215519660481913347350388913860692896794830057828841075800717928496136922098060716510585374016532067242632049443347245270862036596463845639930433028115867577799036275361167352056598041757368346110941880768659806384971809198199512668828321538046301488712881673938570133562616874354230669145214340337839718308600786331780055858693803442292888414613795728376286297540499366092565342894445683466335261400184799951317970076158900554179908634143247822833789270945877210041784279412388281478176181485084368686015245044578831570781845418408827104865900983322715790931962088794 , # 12
        16609233503664838350229300826417968137434069417902926526025797734418692122100144589013458008279872016722846666494657155424450398712685548632166609912828537126006807904798263421812097796486029404588599609556791802963234248856654069506944151954357147418416428290508965358947029021887173648552491917232338512634037819689375579593855135163002164658045797704667553089368331365362141339876612522821344527963046753018460770286235701789539738865268017913736928350095045826197452252739617749397640419847062428880749684361926319077417405948661805283865688851751956022522464188340544199800563476109019430409479248003748920577105587888966925224691673271518417562030706133488288990839807581826487620825588978066251717863203814517844182590219098613580357219744801025128760145818426851217079901627232434690270507248960754315247675208008773355191599872662520284221396162879581280139700664247191846548363390784481609575268458197138345664607912 , # 13
        # 30726903694117702208645145573936999406397228585577401006174394526349227086331305975715858461262478258708140985418626268946780287276023234759686167378803121923012703614585519824067242779960015974521889772064159185870059560483808710155182203507314516859769798329327278181024696787614408479345582606488561103134262090288089149000660457289047323607793342811944038457898953429081661941560374161059101661960022860918030453701838604406716136825800359441237580790722938309075221141410116466840731667120486546559027095742959603794541359070965795873914671166167243428247086159153015652387539911867101356421658976129695160791288408759946765927739905645782525986317894183183813079657980594071173664818199590420655714573585068457270472324470750914838173570755274257666738153107096759731944424802362690668153456112616024254457133975248261000935760451718377872892398815851166999238136515697584763121223808936023573288900032454212732866961180 , # 14
        4974759448302220929432992432163554559707635850129496183618350944498545176387254472140278893193709136834964347005932471439640445763152444226267852042952291765233579666180656354642113388262934269089865473385798275243166487938639950865177488242493138118743464452943116251204994894301791554521115686227830230777822754997788037273012315983242996589356894606615084343580027384939046007698273820459329320697525355605536760362081085293485837592672423790818068341230635455143867555654689754130187346418334377151890146236046997461352256029722204123245956302241182777272106742919138801790941907540209033734701857923738190135668757104161255287346876202050114540877568483206502660240621902179481871385744898573945551677238861724690385317955194220521213805099617556589822378603339511692422966929503858677441033795877870337327870304497269155080883719965561678367429453675182405045694989866698358890238375406743683833644086735324461231659366 , # 15
        2056500086231198568710126592945087305265246584561215277379236306813586160613823460966835403322139605994735709610651694873975126623853828696988086539136866512764769993225411058175682925959717560445137924709892281121222001830966900804792919952922523826740987823010381113775921080999629818266666202720831269173680309840757343268629877021414868094400789625694374524441937406785634366239306559062272489867007125969769230572021646930566678571184701394435808101367112782325498548578460875724157914873557193315932460393626121065094855907581880265043923756808084283098430831723741379375882131438441741468018911299750568499982773882795114901621857369331336178670428725197086799735243984152509306456184680017371055262584096605936335510473227705962683973009393285339574018645590380468526091317242078681951330744670111656888097408920924725399770547057596557534041149880759247453194406077127798707909622225074351940849245241106870173584810 , # 16
        13792062154675508621670926678323269256813393848690104563066764425770499605937110512819471666005378979564376447087781356949854240102813228372861363775197333770516397862168229710943225285381509908937087725322204475627994708377170895070466322032922151840107357967883402111843022008769934386973604027786204474086014202102683823748577591511881392874843909020764042293497202903447794039066497787195346585360197622206896844133316714897300411120320847204646364926968509580144592820644755065944194685560014844523456976242402223275501984417693214609469426062403182455755833419463651928882308605084624901546881331712473048165821284716742034381994011317390141416371702623751157213291417342558189377574572715268647750038080741744060262996511324311158720581042364917062874543081366856718692567451690898953045327959336509148026153764573526111626876827468668921189185179897560142358875802710297743474175185765057337921211583358923358401628884 , # 17
        9230387172181520154154413574836513852783484195114527141898051119684539365064848396384385921939684543850753932365827484422305456624568891044045210378600031454040595200559770657473628855490409191215422500226565713672078532237223353197780952245673136944920315405191352612413116274767407419168763421442786141131948893397232600903463587172836482561045214165179740409313869097380217944900300496861981411565571786626806999546748193986561814188530403721530787162283098404926931239086878246757604553856973054295654112300740417332755187739902051649353972857911824555783545018169451769379941133265829257859251378029825969082170981537697910286773530648335874485317625680029632523852247118380459471044485341777022578843049404275016933901502790232777501461457614595773411372963887037474467840671934861833049693438351661081153928216314632612140001025516344971180822296906769280056206258902498444122719337096110063051476319697618955699756365 , # 18
        # 41483627943671713052423168274765028194764933023418727339241696261417285355902617098330318612276572668989800036508021640104300431529831229550540108840251245966446862717715839525860322535568851173529659293483232011736199992682823896631757874454084206260487841032664589016461948472379539075364035448065422050484115703234431647780634890898066243769714090642903257349551112815636869759230112699019201809971585703292216163157025064859525231901096724949957441030944824348423745798159959612529478782997511339405785987894239093859806314727657080526001682357567133811758687874341901943916773077271211138364187533046447556688792887071542289098793974432904809337490966802741377367257562567567766124299844326886008932154959725243117092373862043486101271712841991072745558877917299070219228372488235504457108903737193166470327543112760788881103252013989747067553273977098273869294119886548048197474874687030658506171075178958184255268770251 , # 19
    ])
    # the commented values are wront CRTs, due to small number of signatures obtained
    # anyway, 5 values are enough
    vals = vals[:5]


def lattice_orthogonal(vs):
    """http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.55.3471&rep=rep1&type=pdf"""
    n = len(vs[0])
    d = len(vs)
    c = 2**( (n-1)//2 + (n-d)*(n-d-1)//4 )
    for v in vs:
        c *= ceil(v.norm())
    c = ceil(c)
    mat = c * matrix(ZZ, d, n, vs).transpose()
    mat = mat.augment(identity_matrix(ZZ, n, n))
    ml = mat.LLL()
    res = [row[-n:] for row in ml.rows()]
    # the orthogonal lattice has dimension n-d
    res = res[:n-d]
    # sanity check
    for r in res:
        assert all(r*v == 0 for v in vs)
    return res

l = len(vals)

bs = lattice_orthogonal([vals])
assert len(bs) == l - 1

vecs = lattice_orthogonal(bs[:l-2])
assert len(vecs) == 2

x, y = vecs

for a in xrange(-50, 50):
    if int( (a*x).norm()**2 ) >= l*N:
        continue
    for b in xrange(-50, 50):
        z = a*x + b*y
        if int(z.norm()**2) >= l*N:
            continue

        print "good norm", a, b
        for c in (vals - z):
            g = gcd(c, N)
            if 1 < g < N:
                print "FACTOR", g
                print N % g == 0
                quit()