import binascii
import random
import math
import sys

p = 2147483647
q = 98764321261

def extended_euclid(a,b):
    if b==0:
        return (a, 1, 0)
    (d, x, y) = extended_euclid(b, a % b)
    return (d, y, x - (a // b)*y)

def multiplicative_inverse(a, n):
    (d, x, y) = extended_euclid(a, n)
    if d == 1:
        return x % n
    return 0

def generisi_kljuceve(p, q):
    n = p*q
    fi_n = (p-1)*(q-1)
    e = 65537
    d = multiplicative_inverse(e, fi_n)
    P = (e, n)
    S = (d, n)
    return (P, S)

def enkripcija(M, P):
    (e, n) = P
    return pow(M, e, n)

def dekripcija(C, S):
    (d, n) = S
    return pow(C, d, n)

(PA, SA) = generisi_kljuceve(p, q)
print(PA, SA)

poruka = 'KiAA je najbolji kurs!'
print('Poruka za slanje:', poruka)
hex_data = binascii.hexlify(poruka.encode())
text = int(hex_data, 16)

sifrat = enkripcija(text, PA)

print('Enkriptovana poruka: ', sifrat)

desifrovan_text = dekripcija(sifrat, SA)

dobijena_poruka = binascii.unhexlify(hex(desifrovan_text)[2:]).decode()

print('Dekriptovana poruka: ', dobijena_poruka)