RSA in Python

rsa.py

import math

def ExtendedEuclid(m, b, verbose=False):
    a1, a2, a3 = 1, 0, m
    b1, b2, b3 = 0, 1, b
    
    if(verbose):
        print("Q\tA1\tA2\tA3\tB1\tB2\tB3")
    q = None

    while(True):

        if(verbose):
            print("%s\t%s\t%s\t%s\t%s\t%s\t%s" % (q, a1, a2, a3, b1, b2, b3))

        if b3 == 0:
            return a3, None

        if b3 == 1:
            if b2 < 0:
                b2 = b2 + b
            return b3, b2

        q = math.floor(a3/b3)

        t1, t2, t3 = a1 - q*b1, a2 - q*b2, a3 - q*b3
        a1, a2, a3 = b1, b2, b3
        b1, b2, b3 = t1, t2, t3


def FastModularExp(a, b, n):
    c = 0
    f = 1
    i = math.floor(math.log2(b))

    while i >= 0:
        bi = (b & (1 << i)) >> i
        
        c = 2*c
        f = (f*f)%n

        if bi == 1:
            c = c + 1
            f = (f*a)%n
        i = i -1

    return f

def RSA_KeyGen(p, q, e):
    n = p * q

    phi_n = (p - 1) * (q - 1)
    
    t = ExtendedEuclid(e, phi_n)
    assert(e > 1 and e < phi_n and t[0] == 1)

    d = math.ceil(t[1]/e)

    public_key = (e,n)
    private_key = (d,n)

    return {'private':private_key, 'public':public_key}

def RSA_encrypt(key, M):
    c = FastModularExp(M, key[0], key[1])
    return c

def RSA_decrypt(key, C):
    m = FastModularExp(C, key[0], key[1])
    return m

if __name__ == "__main__":

    a = int(input("Enter a:"))
    b = int(input("Enter b:"))

    f = ExtendedEuclid(a, b, True)
    print("GCD(%s, %s) = %s\nMultiplicative inverse = %s" % (a, b, f[0], f[1]))

    a = int(input("Enter a:"))
    b = int(input("Enter b:"))
    n = int(input("Enter n:"))

    f = FastModularExp(a, b, n)
    print("%s^%s mod %s = %s" % (a,b,n,f))

    p = int(input("Enter prime p: "))
    q = int(input("Enter prime q: "))
    e = int(input("Enter e, 1 < e < phi(pq), relatively prime to phi(pq): "))

    keys = RSA_KeyGen(p, q, e)
    print("Private key: " + str(keys['private']));
    print("Public key: " + str(keys['public']))

    P = int(input("\nEnter plaintext: "))
    print("Cipher using private key is %s" % RSA_encrypt(keys['private'], P))

    C = int(input("\nEnter cipher: "))
    print("Plaintext using public key is %s" % RSA_decrypt(keys['public'], C))