zer0pts CTF 2023 Elliptic Ring RSA solver

solve_zmod.sage

import re

p = 211
q = 192
a = 201
b = 102
e = 13
Fp = GF(p)
Zq = Zmod(q)
E = EllipticCurve(Fp, [a, b])
G = E.gens()[0]


class EllipticRingElement:
    point = None

    def __init__(self, point):
        self.point = point

    def __add__(self, other):
        if self.point == dict():
            return other
        if other.point == dict():
            return self
        res = self.point.copy()
        for k in other.point.keys():
            if k in res:
                res[k] += other.point[k]
                if res[k] == 0:
                    res.pop(k)
            else:
                res[k] = other.point[k]
                if res[k] == 0:
                    res.pop(k)
        return EllipticRingElement(res)

    def __mul__(self, other):
        if self.point == dict() or other.point == dict():
            return self.point()
        res = dict()
        for k1 in other.point.keys():
            for k2 in self.point.keys():
                E = k1 + k2
                k = other.point[k1] * self.point[k2]
                if E in res:
                    res[E] += k
                    if res[E] == 0:
                        res.pop(E)
                else:
                    res[E] = k
                    if res[E] == 0:
                        res.pop(E)
        return EllipticRingElement(res)

    def __repr__(self):
        st = ""
        for k in self.point.keys():
            st += f"Fp({self.point[k]})*Zq({k}) + "
        return st[:-3]


class EllipticRing:
    E = None
    Base = None

    def __init__(self, E):
        self.E = E
        self.Base = E.base()

    def __call__(self, pt):
        for P in pt:
            pt[P] = self.Base(pt[P])
        return EllipticRingElement(pt)

    def zero(self):
        return EllipticRingElement(dict())

    def one(self):
        return EllipticRingElement({Zq(0): self.Base(1)})

    def pow(self, x, n):
        res = self.one()
        while n:
            if n & 1:
                res = res * x
            x = x * x
            n >>= 1
        return res


C_str = "C: 182*(91, 45) + 147*(3, 164) + 85*(62, 60) + 53*(77, 59) + 99*(77, 152) + 18*(137, 59) + 106*(169, 101) + 147*(127, 127) + 154*(152, 163) + 121*(43, 73) + 155*(110, 160) + 202*(116, 45) + 195*(1, 84) + 106*(71, 162) + 33*(209, 122) + 112*(134, 164) + 186*(1, 127) + 72*(183, 116) + 141*(141, 39) + 72*(83, 127) + 157*(197, 175) + 6*(178, 24) + 106*(71, 49) + 114*(57, 201) + 95*(181, 58) + 1*(174, 44) + 193*(202, 27) + 182*(121, 95) + 52*(167, 179) + 109*(184, 177) + 110*(21, 162) + 101*(126, 170) + 208*(47, 102) + 168*(129, 105) + 209*(179, 123) + 210*(160, 70) + 10*(13, 103) + 159*(76, 55) + 165*(31, 26) + 31*(44, 119) + 47*(6, 70) + 150*(74, 47) + 117*(30, 65) + 3*(108, 69) + 61*(43, 138) + 151*(72, 209) + 122*(110, 51) + 127*(44, 92) + 64*(191, 113) + 61*(45, 70) + 155*(91, 166) + 175*(95, 194) + 97*(21, 49) + 210*(66, 191) + 129*(129, 106) + 210*(80, 7) + 157*(174, 167) + 45*(141, 172) + 189*(155, 78) + 160*(194, 1) + 209*(82, 28) + 142*(164, 136) + 135*(199, 155) + 166*(118, 95) + 100*(123, 14) + 203*(121, 116) + 22*(36, 20) + 33*(65, 58) + 196*(189, 60) + 75*(137, 152) + 22*(125, 4) + 45*(119, 162) + 59*(47, 109) + 102*(177, 157) + 196*(109, 20) + 112*(192, 94) + 97*(209, 89) + 67*(95, 17) + 129*(75, 55) + 34*(134, 47) + 156*(60, 156) + 135*(127, 84) + 11*(148, 147) + 194*(202, 184) + 27*(45, 141) + 131*(4, 166) + 166*(148, 64) + 183*(164, 75) + 177*(130, 145) + 128*(107, 8) + 204*(156, 40) + 131*(17, 25) + 99*(177, 54) + 122*(82, 183) + 52*(178, 187) + 130*(168, 19) + 14*(150, 150) + 173*(167, 32) + 82*(184, 34) + 172*(72, 2) + 144*(169, 110) + 7*(118, 116) + 96*(181, 153) + 34*(133, 5) + 97*(207, 17) + 24*(78, 161) + 54*(57, 10) + 90*(143, 188) + 172*(130, 66) + 179*(146, 65) + 38*(55, 202) + 170*(63, 31) + 99*(35, 65) + 162*(150, 61) + 56*(74, 164) + 146*(144, 85) + 196*(133, 206) + 164*(152, 48) + 139*(176, 153) + 92*(125, 207) + 124*(31, 185) + 136*(0, 1) + 118*(107, 203) + 28*(24, 56) + 66*(171, 151) + 127*(76, 156) + 63*(208, 59) + 187*(146, 146) + 138*(85, 0) + 195*(19, 190) + 115*(60, 55) + 87*(171, 60) + 194*(17, 186) + 79*(75, 156) + 181*(27, 37) + 38*(192, 117) + 168*(13, 108) + 41*(143, 23) + 167*(199, 56) + 177*(86, 71) + 160*(35, 146) + 165*(189, 151) + 130*(32, 30) + 39*(108, 142) + 197*(36, 191) + 176*(120, 17) + 180*(194, 210) + 204*(19, 21) + 160*(6, 141) + 195*(109, 191) + 194*(155, 133) + 62*(65, 153) + 6*(138, 107) + 12*(201, 62) + 43*(180, 43) + 178*(208, 152) + 86*(180, 168) + 135*(55, 9) + 5*(138, 104) + 118*(207, 194) + 58*(160, 141) + 173*(66, 20) + 16*(179, 88) + 181*(61, 131) + 3*(80, 204) + 137*(119, 49) + 106*(126, 41) + 127*(176, 58) + 64*(144, 126) + 96*(30, 146) + 165*(168, 192) + 104*(27, 174) + 64*(63, 180) + 35*(123, 197) + 111*(86, 140) + 141*(197, 36) + 83*(116, 166) + 159*(4, 45) + 165*(62, 151) + 94*(183, 95) + 133*(3, 47) + 58*(83, 84) + 149*(201, 149) + 96*(20, 112) + 141*(191, 98) + 113*(24, 155) + 139*(61, 80) + 73*(120, 194) + 116*(78, 50) + 68*(156, 171) + 31*(32, 181)"
point = {}
for i, j, k in re.findall(r"(\d*)\*\((\d*), (\d*)\)", C_str):
    if j == '0' and k == '1':
        point[Zq(0)] = Fp(i)
    else:
        point[Zq(G.discrete_log(E(j, k)))] = Fp(i)
C = EllipticRingElement(point)
ER = EllipticRing(E)

d = pow(e, -1, (p**q-1)//13)
P = ER.pow(C, d)

point = {}
for key in P.point:
    point[G * Zq(key)] = P.point[key]
points = sorted(point.keys())
print("".join([chr(point[p]) for p in points]))