crt.py

#!/usr/bin/env python3

class BroadcastAttack:
    
    t = []
    messsage = 0

    '''
    Takes in public key, an array of moduli, an array of ciphertexts
    '''
    def __init__(self, e, N, C):
        self.e = e
        self.N = N
        self.C = C

    def calculate_partials(self):
        for i in range(self.e):
            mod_product = 1
            for j in range(self.e):
                if i != j:
                    mod_product *= self.N[j]
            t_i = self.C[i]*mod_product*ModUtil.modinv(mod_product, self.N[i])
            self.t.append(t_i)

    def solve_congruence(self):
        partial_total = 0
        mod_product = 1
        for i in range(self.e):
            partial_total += self.t[i]
            mod_product *= self.N[i]

        self.message = ModUtil.isqrt(partial_total % mod_product, self.e)

    def attack(self):
        self.calculate_partials()
        self.solve_congruence()
        return self.message


class ModUtil:
    '''
    Solves x, y for equation: ax + by = gcd(a, b)
    Return gcd, x, y
    '''
    @staticmethod
    def egcd(a, b):
        if a == 0:
            return (b, 0, 1)
        else:
            gcd, x_old, y_old = ModUtil.egcd(b % a, a)
            return (gcd, y_old - (b // a) * x_old, x_old)


    '''
    Finds modinv of a in mod m
    '''
    @staticmethod
    def modinv(a, m):
        gcd, x, y = ModUtil.egcd(a, m)
        if gcd != 1:
            raise Exception('Mod Inv Undefined')
        else:
            return x % m

    '''
    Newton's method of finding integer square roots
    '''
    @staticmethod
    def isqrt(n, k):
        u, s = n, n+1
        while u < s:
            s = u
            t = (k - 1) * s + n // pow(s, k-1)
            u = t // k
        return s

def main():
    # e = 3
    # N = [377, 391, 589]
    # C = [330, 34, 419]

    e = 3
    N = [
            79608037716527910392060670707842954224114341083822168077002144855358998405023007345791355970838437273653492726857398313047195654933011803740498167538754807659255275632647165202835846338059572102420992692073303341392512490988413552501419357400503232190597741120726276250753866130679586474440949586692852365179,
            58002222048141232855465758799795991260844167004589249261667816662245991955274977287082142794911572989261856156040536668553365838145271642812811609687362700843661481653274617983708937827484947856793885821586285570844274545385852401777678956217807768608457322329935290042362221502367207511491516411517438589637,
            95136786745520478217269528603148282473715660891325372806774750455600642337159386952455144391867750492077191823630711097423473530235172124790951314315271310542765846789908387211336846556241994561268538528319743374290789112373774893547676601690882211706889553455962720218486395519200617695951617114702861810811 
        ]
    C = [
            34217065803425349356447652842993191079705593197469002356250751196039765990549766822180265723173964726087016890980051189787233837925650902081362222218365748633591895514369317316450142279676583079298758397507023942377316646300547978234729578678310028626408502085957725408232168284955403531891866121828640919987,
            48038542572368143315928949857213341349144690234757944150458420344577988496364306227393161112939226347074838727793761695978722074486902525121712796142366962172291716190060386128524977245133260307337691820789978610313893799675837391244062170879810270336080741790927340336486568319993335039457684586195656124176,
            55139001168534905791033093049281485849516290567638780139733282880064346293967470884523842813679361232423330290836063248352131025995684341143337417237119663347561882637003640064860966432102780676449991773140407055863369179692136108534952624411669691799286623699981636439331427079183234388844722074263884842748
        ]

    '''
    e = 17
    N = [
            251559944022254679004304829001443144957715256598544080120488999043966203555150146043116263094153115472538042750401390874321576775343902155779833858301139, 
            631581599817143355156637815368764057658729289426274567229081161401407573910817004096164621816934750379077023142487623527372230291005270787501970017670987, 
            451381041628596207326124081847940960204166538374999085445020285355420988175857579947954685967059608480198930175024682169886737536774933511971321927181339, 
            2810080766910410898922315256010730829834423469065612431962688838569789977116969883469166187790411316781012615563933424570518754568668336570076042023779681, 
            446685455261965759338825728487836285198457527965892425767628294965465635246969157914867391130795513750539766493419405309005382199851613849363013158953691, 
            1449223703625585683740136998075582971053522878623045092070617017781310815387706989074022011548189322773120698155391017740562517346728461858796742408761389, 
            327488298747791910045437528760951291555540774829528247141994445273173947580240428348253364606637977002133296896787675528886161450353825519043823765120369, 
            1597691768098933773496481611425100592870964326552745355854892225663156425799651076791969716194328396929308112494145918596226701211623370541602468474650331, 
            1395730640782854766154240764234913390415872823018378261705953410389934243662091977279578181587809697411186641524257504717272156210021038185669810603347787, 
            1488607647947728424464438700210978450383450729842524331635093786523478974423296630345002603746593497989368601990775242413987517987535125799111536153170173, 
            50656727440476468171888941993634887271515616888811861473258039628044969588300477435075034365621752874655704122564050482595365540419441544001434175482017, 
            287176819672594844781958031405201508811356684015756114993309016653226449482842513895889301051505180878369501836114806572682391016183490385031130148015283, 
            34036882947607786865667129132001292916086289396752095625526361976897840587049175623517760204228449661504836602860498571183464739492889931956079877250727, 
            2046701690432665142790156680114681032013684894574470829624680624984286529258542129452921199689751440366731616805462386884969984985931467839178183517989807, 
            598878710489504643239033157748499957030013089639254678210803134402960416981870109179699249665920826177879965705807684230725468714310554812320925622972343, 
            236278452047823882787496844093106493923855169632993173019560391310531822284440769593196680390628346481290558565015294758431765338844780486085871318656129, 
            1092825720273053976787743821580700220172229172206406980369918650087278234299847917818478183245959820015526685321293529920577132675663235759957638425332857
        ]
    #C = [
            215492783610722563811496188447113198122781186623250997520917994482090133125373628915170193042836195774103129559535221635050102763181639813391010910824657, 
            81452299795693396126222378600474473324054380938196981922856469282697871522235393303627675011112851674112760571773023424161142901063177521397719017723393, 
            218110885245486460545371697186868533738443507665208483371644807724413746935180724463052057315158749422399534554738490586829233910774549299477922189864290, 
            151850182738229693294101618607402527134127733002118437671473000484528075375533885150789898593117865356169769110989714811632157961798034239063495197576983, 
            268477950801349995696075413478555708788626418984391112179186873611829196939862746793509203446108625837681243036327312007633078037513838159106589487996757, 
            1022335198231307194499432064970453217258900041226106469178783611308382482747215247521243000531174736847441008250678803686072572015782476538268717998266544, 
            59902961409592067071435126882213575807450827606790285923959794742393037199798721033385860054001519405570267911458936699762690685365580412123016525818731, 
            182696016297718555621733497627867089576272130072966847194288310576357174187246377149573466509005595286939727009347878596863383045989272977226277514729813, 
            920961603922113229767027066627467477977679519119223934281272362311084385943512757177311241920313174654602618477469654139076968371542273065363174593163687, 
            1233495000134979547123979845498878996982544254636867127395727019489149976734443287636917750605404457030123822602310156912167133273836956476763585084168521, 
            12363335015269844917440631677315113944091684713089849238656284341012608619646411799971561592630336831876593626249886413660979660654735380460858886155577, 
            210802618360209293362536800131035672366286946520704515008362464914410600933784914766887061486031360852494314834607533905303642555583427921031920316384781, 
            4956001545825789738767293325723212698195993940262299983891736340371632661647055510910294040877547937266939325804102478392833885699841634085309445245774, 
            1936482650484169560079249718184008723686671933149866841439543739956535921351591509900843516237492775746156200826377533045798624330089969622568257503581260, 
            450068987198209467635850209459613980855996009887702978817248687092079547910466030117130750072322365760378826487358914105523097349850391753294712755819207, 
            43649194762409534648824876132766633724040642844165159353616740164921136905229015661392666292275097666064877538271824146864881008724804705267469351105991, 
            73765244205135415898591713515397409225909605924633802683783653409666521260715675356284178299874949055673680153281418270647798814777381334427183819247307
        ]  
    '''

    attack = BroadcastAttack(e, N, C)
    print(attack.attack())

if __name__ == '__main__':
    main()