RSA algorithm implementation in Python 3
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