import math
def gcd(a, h):
    temp = 0
    while(1):
        temp = a % h
        if (temp == 0):
            return h
        a = h
        h = temp
p = int(input("Enter Number P : "))
q = int(input("Enter Number Q : "))
n = p*q
e = 2
phi = (p-1)*(q-1)
while (e < phi):
    if(gcd(e, phi) == 1):
        break
    else:
        e = e+1
k = 2
d = (1 + (k*phi))/e
msg = 12.0
print("Message data = ", msg)
c = pow(msg, e)
c = math.fmod(c, n)
print("Encrypted data = ", c)
m = pow(c, d)
m = math.fmod(m, n)
print("Original Message Sent = ", m)

#Digital Signature using RSA

def euclid(m, n):
    if n == 0:
        return m
    else:
        r = m % n
        return euclid(n, r)

def exteuclid(a, b):
    r1 = a
    r2 = b
    s1 = int(1)
    s2 = int(0)
    t1 = int(0)
    t2 = int(1)

    while r2 > 0:
        q = r1//r2
        r = r1-q * r2
        r1 = r2
        r2 = r
        s = s1-q * s2
        s1 = s2
        s2 = s
        t = t1-q * t2
        t1 = t2
        t2 = t
    if t1 < 0:
        t1 = t1 % a
    return (r1, t1)
p = int(input("Enter value of P : "))
q = int(input("Enter value of Q : "))
n = p * q
Pn = (p-1)*(q-1)
key = []
for i in range(2, Pn):
    gcd = euclid(Pn, i)
    if gcd == 1:
        key.append(i)
e = int(313)
r, d = exteuclid(Pn, e)
if r == 1:
    d = int(d)
else:
    print("Multiplicative inverse for\
the given encryption key does not \
exist. Choose a different encryption key ")
M = int(input("Enter value of M : "))
S = (M**d) % n
M1 = (S**e) % n
print("decryption key is: ", d)
if M == M1:
    print("As M = M1, Accept the\
message ")
else:
    print("As M not equal to M1,\
Do not accept the message\
")