Why does the encryption/decryption in my RSA code not work?

Question

I'm currently coding a simplified RSA algorithm for a project at school but can't get it to work.

I've based the code off of the formulae c = m^e(mod N) and (c^d)mod N. The encryption function works to produce what looks like a feasible output but when I put it into the decryption function it either doesn't return the message correctly or gives me this error:

ValueError: chr() arg not in range(0x110000)

My code:

import random
import math

def is_prime(x):
    for i in range(2,int(math.sqrt(x))+1):
        if x % i == 0:
            return False
            break
    return  True

def gcd(a, b):
    if (b == 0):
        return a
    else:
        return gcd(b, a % b)

def generate_p_and_q(p,q):
    p_and_q = []
    p_and_q.append(p)
    p_and_q.append(q)
    return p_and_q

def generate_phi(p,q):
    p_and_q = generate_p_and_q(p,q)
    phi = (p_and_q[0] - 1)*(p_and_q[1] - 1)
    return phi

def generate_N(p,q):
    p_and_q = generate_p_and_q(p,q)
    N = (p_and_q[0])*(p_and_q[1])
    return N

def generate_e(p,q):
    phi = generate_phi(p,q)
    with open('First500Primes.txt') as f:
        lines = f.read().splitlines()
    for i in lines:
        if int(i) > 1 and int(i)< phi:
                if gcd(int(i), phi) == 1:
                    e = int(i)
                    break
    return e

def encrypt_RSA():
    encrypted = []
    message = input("Enter a message to encrypt:")
    message.lower()
    with open('First500Primes.txt') as f:
        lines = f.read().splitlines()
    valid = False
    choice = input("Do you want to: \nA: enter a key \nB: use a random key?\n")
    if choice.lower() == 'a':
        p = int(input("Enter a key - this must be a prime number between 0 and 500:"))
        q = int(input("Enter a key - this must be a prime number between 0 and 500:\n"))
        while valid != True:
            valid = is_prime(p) and is_prime(q)
            if valid == False:
                print("Your numbers were not prime!")
                p = int(input("Enter a key - this must be a prime number between 0 and 500:"))
                q = int(input("Enter a key - this must be a prime number between 0 and 500:\n"))
    else:
        x = random.randint(0, 499)
        y = random.randint(0, 499)
        p = int(lines[x])
        q = int(lines[y])
    generate_p_and_q(p,q)
    e = generate_e(p,q)
    N = generate_N(p,q)
    for char in message:
        encrypted.append((ord(char) ** e) % N)
    result = ''
    for i in encrypted:
        result = result + str(i)
    print("encrypted message: " + result)
    info = [encrypted, N, e]
    return (info)
encrypt_RSA()


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 calculate_d(a,m):
    g,x,y = egcd(a,m)
    if g != 1:
        return None
    else:
        return x%m

def calculate_phi(N):
    with open('First500Primes.txt') as f:
        lines = f.read().splitlines()
    for num in lines:
        if N%int(num) == 0:
            p = int(num)
            q = N/int(num)
    phi = (p-1)*(q-1)
    return int(phi)

def decrypt_RSA():
    encrypted = encrypt_RSA()
    encrypted_message, N, e = encrypted[0], encrypted[1], encrypted[2]
    print(N)
    phi = calculate_phi(N)
    d = calculate_d(phi,e)
    print("D: " + str(d))
    message = []
    encrypted_message = (encrypted[0])
    for c in encrypted_message:
        m = (c**d) % N
        print(m)
        message.append(chr(m))
    print(message)


decrypt_RSA()

I need the code to firstly encrypt the message with the encrypt function then decrypt it with the decrypt function, so the encrypted and original message should be displayed.

Could someone tell me whats wrong with my code (since I'm still in school, it may need to be simplified), any additional feedback would be greatly appreciated.

Answer 1

After a bit of debugging, the problem is that the function calculate_d() does not seem to calculate the right number. It is solved when we invert the params of one of your function. Change this line

d = calculate_d(phi, e)

to this:

d = calculate_d(e, phi)

That got it working for me.

---

Also, since you asked for suggestions to improve your code, I made a few (a lot) improvements. Some ideas:

1. I replaced the parts that read the prime number file with a prime number generator, but that is just because I didn't have the file at hand. Choose whichever you like best.
2. Invoke the main functions inside a if __name__ == '__main__':. Read about it here.
3. I moved the input prompts outside of the encryption code. Implement those parts as needed (random or prompting user for input) and just pass the result to the function for encryption.

My version:

def generate_primes():
    """
    Generate an infinite sequence of prime numbers.

    Sieve of Eratosthenes
    Code by David Eppstein, UC Irvine, 28 Feb 2002
    http://code.activestate.com/recipes/117119/
    https://stackoverflow.com/a/568618/9225671
    """
    # Maps composites to primes witnessing their compositeness.
    # This is memory efficient, as the sieve is not "run forward"
    # indefinitely, but only as long as required by the current
    # number being tested.
    D = {}

    # The running integer that's checked for primeness
    q = 2

    while True:
        if q not in D:
            # q is a new prime.
            # Yield it and mark its first multiple that isn't
            # already marked in previous iterations
            yield q
            D[q * q] = [q]
        else:
            # q is composite. D[q] is the list of primes that
            # divide it. Since we've reached q, we no longer
            # need it in the map, but we'll mark the next
            # multiples of its witnesses to prepare for larger
            # numbers
            for p in D[q]:
                D.setdefault(p + q, []).append(p)
            del D[q]

        q += 1

def choose_p_and_q():
    p_i = random.randint(0, 100)
    q_i = random.randint(0, 100)
    p = 0
    q = 0
    for i, n in enumerate(generate_primes()):
        if i <= p_i:
            p = n
        if i <= q_i:
            q = n

        if i > p_i and i > q_i:
            break

    return p, q

def generate_n(p, q):
    return p * q

def generate_phi(p, q):
    return (p - 1) * (q - 1)

def generate_e(phi):
    e = None

    for n in generate_primes():
        if math.gcd(n, phi) == 1:
            e = n

        if n >= phi:
            if e is None:
                raise ValueError('no suitable prime number found; reached {}'.format(n))

            # return the highest prime number found
            return e

def find_p_and_q_from_n(n):
    for i in generate_primes():
        if n % i == 0:
            p = i
            q, remainder = divmod(n, p)
            if remainder == 0:
                return p, q

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 calculate_d(phi, e):
    g, x, _ = egcd(phi, e)
    if g == 1:
        return x % e

    raise ValueError('no modular multiplicative inverse found')

def encrypt_rsa(msg):
    p, q = choose_p_and_q()
    n = generate_n(p, q)
    phi = generate_phi(p, q)
    e = generate_e(phi)
    print()
    print('ENCRYPT')
    print('p   ', p)
    print('q   ', q)
    print('n   ', n)
    print('phi ', phi)
    print('e   ', e)

    encrypted_list = []
    for char in msg:
        m = (ord(char) ** e) % n
        encrypted_list.append(m)

    print('msg           ', list(msg))
    print('encrypted_list', encrypted_list)

    return encrypted_list, n, e

def decrypt_rsa(encrypted_list, n, e):
    p, q = find_p_and_q_from_n(n)
    phi = generate_phi(p, q)
    d = calculate_d(e, phi)
    print()
    print('DECRYPT')
    print('p   ', p)
    print('q   ', q)
    print('n   ', n)
    print('phi ', phi)
    print('e   ', e)
    print('d   ', d)

    decrypted_list = []
    for elem in encrypted_list:
        m = (elem**d) % n
        decrypted_list.append(chr(m))

    print('decrypted_list', decrypted_list)

if __name__ == '__main__':
    msg = input('Enter a message to encrypt:').strip()

    data = encrypt_rsa(msg)
    decrypt_rsa(*data)