VNPT Secathon 2018

modulus.py

# Took from SO
def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    g, y, x = egcd(b%a,a)
    return (g, x - (b//a) * y, y)

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('No modular inverse')
    return x%m

enc = [ord(i) for i in 'e491a9c1d86d1925fa246b1783538f54d75f543b0c6b17545fd7a783b30c54d70054178f4754bf9b8f2fe2'.decode('hex')]
flag = [ord(i) for i in 'SECATHON{']
mod = 251
y0, x0 = enc[0], flag[0]
y1, x1 = enc[1], flag[1]
a = ((y0-y1)*modinv(x0-x1,mod)) % mod
b = (y0 - a*x0) % mod
while len(flag) < len(enc):
	flag += [((enc[len(flag)] - b) * modinv(a,mod) % mod)]
print ''.join([chr(i) for i in flag])