RSA algorithm implementation in Python 3

Question

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")

Answer 1

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

Answer 2

You can use math.gcd:

from math import gcd

One must not compare variables with None using equality operator

Comparisons to singletons like None should always be done with is or is not, never the equality operators.

modinv for prime mod may be implemented like this:

def prime_mod_inv(x, mod):
    return pow(x, mod - 2, mod)

You can use print with multiple arguments.

No:

print("Choosen primes:\np=" + str(p) + ", q=" + str(q) + "\n")

Yes:

print("Choosen primes:")
print("p =", p, ", q =", q)

No:

print("Euler's function (totient) [phi(n)]: " + str(phi) + "\n")

Yes:

print("Euler's function (totient) [phi(n)]:", phi)

No:

print(str(coprimes(phi)) + "\n")

Yes:

print(coprimes(phi), "\n")

You can replace this

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)

With list comprehension

l = [x for x in range(2, a) 
     if gcd(a, x) == 1 
        and modinv(x, phi) is not None
        and modinv(x, phi) != x]

Answer 3

Rather than using Euler's Totient formula to compute d, it's recommended to use the Carmichael Lambda Function instead. The Carmichael Lambda(CML) divides the Totient. The CML provides the smallest possible secure private key.

Luckily, if your primes are truly primes, one can EASILY compute the CML. It's the lcm of p-1, q-1. Then use the same Modular inverse (definitely use the extended GCD ) algorithm for the modular inverse, a beauty of an algorithm.

Answer 4

Instead of choosing an e, you can randomize it

z = coprimes(phi)
e = random.choice(z)