RSA algorithm implementation in Python 3 First, a reminder of the RSA algorithm and what my program implements:


Take two distinct, large primes p and q


Ideally these have a similar byte-length

Multiply p and q and store the result in n
Find the totient for n using the formula $$\varphi(n)=(p-1)(q-1)$$
Take an e coprime that is greater, than 1 and less than n
Find d using the formula $$d\cdot e\equiv1\mod\varphi(n)$$


At this point, the pair (e, n) is the public key and the private key (d, n) is the private key.

Conception:


Implement the RSA algorithm
Ask the user for necessary data (primes, coprime greater than 1 and less than n, string)
Encrypt and decrypt the given string by the user using the RSA algorithm


What do you think about my Python 3 implementation of the RSA algorithm? What's the performance of this program?

try:
   input = raw_input
except NameError:
   pass
try:
   chr = unichr
except NameError:
   pass
p=int(input('Enter prime p: '))
q=int(input('Enter prime q: '))
print("Choosen primes:\np=" + str(p) + ", q=" + str(q) + "\n")
n=p*q
print("n = p * q = " + str(n) + "\n")
phi=(p-1)*(q-1)
print("Euler's function (totient) [phi(n)]: " + str(phi) + "\n")
def gcd(a, b):
    while b != 0:
        c = a % b
        a = b
        b = c
    return a
def modinv(a, m):
    for x in range(1, m):
        if (a * x) % m == 1:
            return x
    return None
def coprimes(a):
    l = []
    for x in range(2, a):
        if gcd(a, x) == 1 and modinv(x,phi) != None:
            l.append(x)
    for x in l:
        if x == modinv(x,phi):
            l.remove(x)
    return l
print("Choose an e from a below coprimes array:\n")
print(str(coprimes(phi)) + "\n")
e=int(input())
d=modinv(e,phi)
print("\nYour public key is a pair of numbers (e=" + str(e) + ", n=" + str(n) + ").\n")
print("Your private key is a pair of numbers (d=" + str(d) + ", n=" + str(n) + ").\n")
def encrypt_block(m):
    c = modinv(m**e, n)
    if c == None: print('No modular multiplicative inverse for block ' + str(m) + '.')
    return c
def decrypt_block(c):
    m = modinv(c**d, n)
    if m == None: print('No modular multiplicative inverse for block ' + str(c) + '.')
    return m
def encrypt_string(s):
    return ''.join([chr(encrypt_block(ord(x))) for x in list(s)])
def decrypt_string(s):
    return ''.join([chr(decrypt_block(ord(x))) for x in list(s)])
s = input("Enter a message to encrypt: ")
print("\nPlain message: " + s + "\n")
enc = encrypt_string(s)
print("Encrypted message: " + enc + "\n")
dec = decrypt_string(enc)
print("Decrypted message: " + dec + "\n")
I think your Modular Inverse implementation is slow. We can apply this Extended GCD algorithm recursive implementation which shows quite a dramatic speed improvement (at least on my machine):

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


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


Here is a simple benchmark for some a and m which have a modular inverse of 16013:

In [24]: a = 108 ** 151

In [25]: m = 22499

In [26]: %timeit modinv_OP(a, m)
100 loops, best of 3: 11.2 ms per loop

In [27]: %timeit modinv_new(a, m)
100000 loops, best of 3: 5.62 µs per loop


I also wonder if adding an LRU cache via functools.lru_cache() would make an impact - probably not, but please experiment with that.



Some other improvements:


you can avoid converting s to a list in order to iterate character by character:

''.join(str(chr(encrypt_block(ord(x)))) for x in s)


I've also switched to a "lazy" join when joined from a generator.
if on Python 3.6+, you can use f-strings for your print messages