#!/usr/bin/python

import base64
import hashlib
from Crypto import Random
from Crypto.Cipher import AES

def linear_diophantine_equation(a, b):
    if b > a:
        return linear_diophantine_equation(b, a)

    if b == 0:
        return a, 1, 0

    d, x, y = linear_diophantine_equation(b, a % b)
    return (d, y, x - (a // b) * y)

a = 17577019968135092891915317246036083578063875217491307011102321322815719709605741738459191569497548099944025771002530369133716621942963853230082186943938164591230020725702755002287589522851172217336150522367152517270250629688405924844750026155547199020780202996200555426652190631837288299999083335649923708175859594750237448640513280683859296367607523542293538555215282798100455110266565881599829107971869244773384413618546118850868579583095489023778055976570366853411496753062216229293710557686212314300848121614558806328788578096144576605248971916454783615989429937555579437307320472405217413938048149254574677430624

b = 15228628318558071728245462802366236848375416102820239825350329247148900182647243994904519787528142824353837070194785550898962097219309344881183948914850354340893035399529028331238911753358245357848436203268982345430735846016484221944423499956958406189854969330305125479065873712331269870135028162018087451460656203085824963123310757985362748654204595136594184636862693563510767025800252822776154986386637346156842972134635578534633722315375292616298410141343725683471387328655106920310236007034951004329720717533666052625540760911360823548318810161367913281234234193760867208897459774865037319252137821553407707977377

g = 3
p = 0x00e1a540d72bb311db26ea6e58b7dc207cf55d0c3a90d7c1f74e7fcb67c7af097d99c73e002c9266e70cbdf735ebd864ea279a0a4d41dd6537837bfc07d84943a376d163ec20a51dd6073dbfc34cbdce9d88ad22a9bb72f5bb143b5c9e531ab100590b9f97d1e9c7a3dfe7961fd6e86078ad43918b47816925803db47862e5f69c90078c6dc287fc6cf7742a9f1717d828a610fe469c92f34783351b21ac1ec988eae0e16ff4ef89c1a19ccd7e3b5cb0c14e0424dfde338789923013aeb7791e19ba378cb2e0e0b318f46865d438ac53999f69f0ae8045d2ff40821b5fdcb0a3b9942f29a0cd8e55febd0ee9006d936d51335a2e63b6affbed6175e1228a53d6a9

message = "jqMYIn4fzSqzIXArwJm/kPitNhf4lwhL0yPRKpF+NYXyPmhoEwNG/k2L5vCZqFWNPvTzisnu93/8uK/PZnnCGg=="
messageDecoded = base64.b64decode(message)

def test_x(x):
    return (g * x) % p == a

# (g * x) % p = a
# (g * x) - (k * p) = a

x = linear_diophantine_equation(g, p)[2] * a
key = str((b * x) % p)
iv = key[0:16]

# Decrypt
key = bytes(hashlib.md5(bytes(key, "utf-8")).hexdigest(), "utf-8")
cipher = AES.new(key, AES.MODE_CBC, iv=bytes(iv, "utf-8"))
plain_text_bytes = cipher.decrypt(messageDecoded)
plain_text = plain_text_bytes.decode("utf-8")
print(plain_text)