import binascii


class RSA:
    def __init__(self, p, q, e=None):
        self.p = p
        self.q = q
        self.N = self.p * self.q
        self.phi = (self.p - 1) * (self.q - 1)
        if not e:
            e = 3
        self.e = e
        self.d = self.modinv(e, self.phi)

    def public_key(self):
        return self.e, self.N

    def public_key_str(self):
        return "e = {}; N = {}".format(*self.public_key())

    def egcd(self, a, b):
        if a == 0:
            return b, 0, 1
        else:
            g, y, x = self.egcd(b % a, a)
            return g, x - (b // a) * y, y

    def modinv(self, a, m):
        g, x, y = self.egcd(a, m)
        if g != 1:
            raise Exception('modular inverse does not exist')
        else:
            return x % m

    # Это мы (как сервер) шифруем сообщение закрытым ключом
    def encrypt(self, m):
        m_hex = binascii.hexlify(m.encode())
        m_int = int(m_hex, 16)
        if m_int >= self.N:
            raise Exception('Message should be smaller than N')
        return str(pow(m_int, self.d, self.N))

    # Расшифрока сообщения, которое адресовано нам!
    # m: результат функции encrypt_public - строка - десятичное число
    def decrypt(self, m):
        m = m.encode()
        m_int = int(m, 10)
        if m_int >= self.N:
            raise Exception('Message should be smaller than N')
        m_int = pow(m_int, self.d, self.N)
        m_hex = hex(m_int)[2:]
        return str(binascii.unhexlify(m_hex))


# Шифрует сообщение M открытым ключом e и N
def encrypt_public(e, N, m):
    m_hex = binascii.hexlify(m.encode())
    m_int = int(m_hex, 16)
    if m_int >= N:
        raise Exception('Message should be smaller than N')
    return str(pow(m_int, e, N))


# Расшифрока сообщения m, которое зашифрованно приватным ключом
def decrypt_public(e, N, m):
    m = m.encode()
    m_int = int(m, 10)
    if m_int >= N:
        raise Exception('Message should be smaller than N')
    m_int = pow(m_int, e, N)
    m_hex = hex(m_int)[2:]
    return binascii.unhexlify(m_hex)