writeup draft

signit.py

import socket
import operator
from termcolor import colored
from sympy.ntheory import primefactors
from functools import reduce

SIGNER   = ('cry1.chal.mmactf.link', 44815)
VERIFIER = ('cry1.chal.mmactf.link', 44816)

S_PROMPT = colored('s', 'blue')
V_PROMPT = colored('v', 'red')

class FriendlySocket(object):

    def __init__(self, addr, prompt):
        self.addr = addr
        self.prompt = prompt
        self.sock = socket.socket()

    def __enter__(self):
        self.sock.connect(self.addr)
        self.file = self.sock.makefile('r')
        return self

    def __exit__(self, *args, **kwargs):
        self.sock.close()

    def readline(self):
        line = self.file.readline().strip()
        print(self.prompt, '>', line)
        return line

    def readlines(self):
        while True:
            line = self.readline()
            if not line:
                break

    def writeline(self, line):
        print(self.prompt, '<', line)
        if not isinstance(line, str):
            line = str(line)
        if not line.endswith('\n'):
            line += '\n'
        self.sock.send(line.encode())

with FriendlySocket(VERIFIER, V_PROMPT) as v:
    n = int(v.readline().split()[-1])
    e = int(v.readline().split()[-1])
    v.readline() # 'Sign it!'
    m = int(v.readline())
    c = 1
    factors = primefactors(m, limit=1000)
    factors.append(m // reduce(operator.mul, factors, 1))
    for factor in reversed(factors):
        with FriendlySocket(SIGNER, S_PROMPT) as s:
            s.writeline(factor)
            c *= int(s.readline())
    c %= n
    v.writeline(c)
    v.readlines()

# $ python3 signit.py
# v > n = 167891001700388890587843249700549749388526432049480469518286617353920544258774519927209158925778143308323065254691520342763823691453238628056767074647261280532853686188135635704146982794597383205258532849509382400026732518927013916395873932058316105952437693180982367272310066869071042063581536335953290566509
# v > e = 65537
# v > Sign it!
# v > 418390847269507996686465575344871372367557094726377971689399180151475362338423220070846018040790345652250910646411337945639636908768688491651439022471874918654958510189673376429921595748174949369686551678042
# m = 418390847269507996686465575344871372367557094726377971689399180151475362338423220070846018040790345652250910646411337945639636908768688491651439022471874918654958510189673376429921595748174949369686551678042
# s < 9961686839750190397296799412973127913513264160151856468795218575035127674724362382639190905733103467910735967771698522515229450208778297420272357677901783777499012147373175629283847517813689270706822659001
# s > 104354442179217921693940381702883055554025845174587765838943073941882380934618789386361064532714649771473916380909141462508644257738450535137581081287720010242522724899688182861320959541488634228202315311011449100486440317280702881284474065223877692328314368867669471778456567673811458734516723733076468458960
# s < 7
# s > 109443784410169219796497821135482318524319182154293578341064055228306126909897304708174067963450742430421801004926930524292459065185139180108902331380171484658845305467252587932448803167031301162937090966929547171530975532585844616078354060092537551696119658864297719677839621692999165482485428976828440493683
# s < 3
# s > 51074812641158507123662234203483008196251247549432740397588863668876424934341825346967796865748609343008283261606654770777972986103404009582048439415936246163014731018892182522907990982015965488887718138666222340321317400689754438875142195914636482686211663185453293837209151192072293697957275070120202705294
# s < 2
# s > 45079099838985725562852606238717200427051379007624461327902168505601211187218876469734461321234449872036659707405487725511293056518165755448751892780025070359086690571912728851484390191469176434804920520148004120893601096389983117747368657326741086665038698187413495968534490174851162613343138684260784792820
# v < 141305515576619248200456586568006622636043846643972525867804800752885561688177676938146805098656872925388041612058592369952501774410447050245460897712760419291869412510226308426657907136687812777443262180056914118075800306372691194265464301105499813997919938952404312030768421609547118958549038674788810664374
# v > MMA{homomorphic_challengers}
# v >

# v > n = 167891001700388890587843249700549749388526432049480469518286617353920544258774519927209158925778143308323065254691520342763823691453238628056767074647261280532853686188135635704146982794597383205258532849509382400026732518927013916395873932058316105952437693180982367272310066869071042063581536335953290566509
# v > e = 65537
# v > Sign it!
# v > 20628261412735107768707348632263326158411747119694953588133102081919591830964973605878304778385695576863916055514212115640653025861405724694041745084792824851682316204137240716
# 20628261412735107768707348632263326158411747119694953588133102081919591830964973605878304778385695576863916055514212115640653025861405724694041745084792824851682316204137240716 [2, 3, 3438043568789184628117891438710554359735291186615825598022183680319931971827495600979717463064282596143986009252368685940108837643567620782340290847465470808613719367356206786]
# s < 3438043568789184628117891438710554359735291186615825598022183680319931971827495600979717463064282596143986009252368685940108837643567620782340290847465470808613719367356206786
# s > 148473585231236210757623682055006204403542179232131075561469069361957041952976210371547377717460675554274968014810153673652706813709944524262062847494899271491823340518862153235063728999239268377587530199027318712127345312324198688029614164455484768083532478148300732952128902539110737734792778596936175686152
# s < 3
# s > 51074812641158507123662234203483008196251247549432740397588863668876424934341825346967796865748609343008283261606654770777972986103404009582048439415936246163014731018892182522907990982015965488887718138666222340321317400689754438875142195914636482686211663185453293837209151192072293697957275070120202705294
# s < 2
# s > 45079099838985725562852606238717200427051379007624461327902168505601211187218876469734461321234449872036659707405487725511293056518165755448751892780025070359086690571912728851484390191469176434804920520148004120893601096389983117747368657326741086665038698187413495968534490174851162613343138684260784792820
# v < 70361889272415791874634307443989703269019677157434341244771565680221822850582396088498211923105952152926343379085468633755977909224703151194073384412748651779829467116710375844210513903938772196077198054326440696215604905334993492276211510864726388636914127887399115080367784954385574987033207462164851394268
# v > MMA{homomorphic_challengers}
# v >

# v > n = 167891001700388890587843249700549749388526432049480469518286617353920544258774519927209158925778143308323065254691520342763823691453238628056767074647261280532853686188135635704146982794597383205258532849509382400026732518927013916395873932058316105952437693180982367272310066869071042063581536335953290566509
# v > e = 65537
# v > Sign it!
# v > 8485974541701587025413725513399823384373711644923412023674433813294576019954842107670964026132189432395839437126685617832977369928473166891666917444210706376282796644129196833262954848614136933309047824649842584957526279915864862609468201
# 8485974541701587025413725513399823384373711644923412023674433813294576019954842107670964026132189432395839437126685617832977369928473166891666917444210706376282796644129196833262954848614136933309047824649842584957526279915864862609468201 [7, 11, 272879, 103048079, 3919232107366706813985461664315435186779149789996344062994364323398653706191465346161870584234100506774282294902364584930091212660440644718165342596830313079409409982525912472815462641583850110539767221481411457642999871693]
# s < 3919232107366706813985461664315435186779149789996344062994364323398653706191465346161870584234100506774282294902364584930091212660440644718165342596830313079409409982525912472815462641583850110539767221481411457642999871693
# s > 54732613847790906582069014999900014703361431217917804055470711686274112328362174669823786960353562241133454251082431263276190957577467099856419330957034344190119188609275560581111574676465407966514977728909942836191544210277858158307399859251572666799566030892121596799556988427162191888161251805366343403355
# s < 103048079
# s > 150694451259141730322505670230943977524542985258240975717217541874494125885950579533832097973849617594995767869258669412309245428146256839415113240524440678800416396741734362265460434516513289244271480616715750175820486210356875456518272725229896903637332765850020269187259688090637006678044995799368736315651
# s < 272879
# s > 6753792632675589133236142639664726022798729206267054385589952190394199478359736884588025881000344723963420875217787050992254504736126176790355252804596055087940207266053663513552546492888476149685361271352776416729994122876862818900133387829921820179048529762118971042378565177629305797347826049278912574994
# s < 11
# s > 48237525830983757304299608861520261493435023660072369941828892548333787199946801639520944944313591768894284175208670754001966601119023444161702879218310805963448950227515007442551928242459260656699925640453728459398888905184418527247764364921457252212645000081375034827388123458135004177216483382912095058661
# s < 7
# s > 109443784410169219796497821135482318524319182154293578341064055228306126909897304708174067963450742430421801004926930524292459065185139180108902331380171484658845305467252587932448803167031301162937090966929547171530975532585844616078354060092537551696119658864297719677839621692999165482485428976828440493683
# v < 19741711226677813185861841031732316601705695749874025743494958783055249688420907683960827787304698996538064218092258254010323985087306477473717914090591536237747486797009617395722464276201903519113051003150679122788688208367769260272246880477345871763718803611031292805668230614848740812036143051086906354693
# v > MMA{homomorphic_challengers}
# v >

# v > n = 167891001700388890587843249700549749388526432049480469518286617353920544258774519927209158925778143308323065254691520342763823691453238628056767074647261280532853686188135635704146982794597383205258532849509382400026732518927013916395873932058316105952437693180982367272310066869071042063581536335953290566509
# v > e = 65537
# v > Sign it!
# v > 80579146159220778693144591745113460074576304650845983300271022546846976438164520687185230578916498360175370621169946659962413063588728622206546316174788134464147594246572898
# 80579146159220778693144591745113460074576304650845983300271022546846976438164520687185230578916498360175370621169946659962413063588728622206546316174788134464147594246572898 [80579146159220778693144591745113460074576304650845983300271022546846976438164520687185230578916498360175370621169946659962413063588728622206546316174788134464147594246572898]
# s < 80579146159220778693144591745113460074576304650845983300271022546846976438164520687185230578916498360175370621169946659962413063588728622206546316174788134464147594246572898
# s > By the way, I'm looking forward to the PIDs subsystem of cgroups.

# v > n = 167891001700388890587843249700549749388526432049480469518286617353920544258774519927209158925778143308323065254691520342763823691453238628056767074647261280532853686188135635704146982794597383205258532849509382400026732518927013916395873932058316105952437693180982367272310066869071042063581536335953290566509
# v > e = 65537
# v > Sign it!
# v > 142371027881351037745404629677158364993263400074471705407458975748224738116188682352720032581337630835709920369169604398169862160447123057441129985739980860799904996094082014914220778375661672997382721269007351251279822081979484144112255193252824
# s < 23728504646891839624234104946193060832210566679078617567909829291370789686031447058786672096889605139284986728194934066361643693407853842906854997623330143466650832682347002485703463062610278832897120211501225208546637013663247357352042532208804
# s > 93233402663979216959220459510396991551477690888535287399866764915041160398952681463768107315644421072238667220093381698407067116750053625313864023390468316299137304172537959893726953048759538581800920128900977361662918389941931626430906972572628708257776572717355634601401965002583593854698067571722100713023
# s < 3
# s > 51074812641158507123662234203483008196251247549432740397588863668876424934341825346967796865748609343008283261606654770777972986103404009582048439415936246163014731018892182522907990982015965488887718138666222340321317400689754438875142195914636482686211663185453293837209151192072293697957275070120202705294
# s < 2
# s > 45079099838985725562852606238717200427051379007624461327902168505601211187218876469734461321234449872036659707405487725511293056518165755448751892780025070359086690571912728851484390191469176434804920520148004120893601096389983117747368657326741086665038698187413495968534490174851162613343138684260784792820
# v < 143631039001241163754375700256264497559884011109346481313043502133848492772716183195258103915535046421668446518808099577414239246987980195871362736701910999437091681491694367728710846750970808669977118149102996361291085064491964026817093316358397508632025500413684767241087470196588458004222074481729980572958
# v > MMA{homomorphic_challengers}
# v >

# Public key: n and e
# Private key: d
# Digital signature:
# c = md mod n (signing)
# m = ce mod n (verification)