Decimal codes too large in RSA

Question

I'm trying to implement RSA algorithm in python, but sometimes when I execute the code the result of the maths are too large for decimal codes and when I try to decrypt the cipher context the result is not the original string. I don't have ideia what is going wrong, please answer me if the code is wrong or there is one way to tranform the large decimal codes to lower.

This is the code:

import random

def primes(min, max):
    for i in range(min, max):
        if i % 2 == 0 or i % 3 == 0 or i % 5 == 0 or i % 7 == 0:
            pass
        else:
            yield i
            # print(i)

def gdc(n1, n2):
    while n2:
        n2, n1 = n1 % n2, n2
    return n1

def private_keys(n, phi):
    for i in range(2, phi):
        if gdc(n, i) == 1 and gdc(phi, i) == 1:
            yield i

def public_keys(phi, private_key, maximum):
    for i in range(phi + 1, phi + maximum):
        if i * private_key % phi == 1:
            yield i

def encrypt_string(key, n, string):
    cipher_context = ''
    for word in string:
        word_ascii = ord(word)
        encrypted_word_ascii = word_ascii ** key % n
        print(f'{word_ascii} {encrypted_word_ascii}')
        cipher_context += chr(encrypted_word_ascii)
    return cipher_context

def decrypt_string(key, n, cipher_context):
    plain_text = '' 
    for encrypted_word in cipher_context:
        encrypted_ascii_word = ord(encrypted_word)
        ascii_word = encrypted_ascii_word ** key % n
        print(f'{encrypted_ascii_word} {ascii_word}')
        plain_text += chr(ascii_word)
    return plain_text

minimum = 10
maximum = 200

generated_primes = [i for i in primes(minimum, maximum)]

prime1 = random.choice(generated_primes)
generated_primes.remove(prime1)
prime2 = random.choice(generated_primes)

print(f'Primo 1 (p): {prime1}')
print(f'Primo 2 (q): {prime2}')

n = prime1 * prime2
print(f'n: {n}')

phi = (prime1 - 1) * (prime2 - 1)
print(f'phi: {phi}')

generated_private_keys = [i for i in private_keys(n, phi)]
# print(generated_private_keys)
private_key = random.choice(generated_private_keys)
print(f'Chave privada: {private_key}')

maximum_pub = 100000
generated_public_keys = []
while generated_public_keys == []:
    generated_public_keys = [i for i in public_keys(phi, private_key, maximum_pub)]
    maximum_pub *= 10
#print(generated_public_keys)
public_key = random.choice(generated_public_keys)
print(f'Chave publica: {public_key}')

text = 'Testando exemplo de criptografia RSA'
print(text)

cipher_context = encrypt_string(public_key, n, text)
print(frase_criptografada.encode('utf-16', 'surrogatepass'))

print()

plain_text = decrypt_string(private_key, n, cipher_context)
print(plain_text)

Exemple of strange output:

Primo 1 (p): 169
Primo 2 (q): 89
n: 15041
phi: 14784
Chave privada: 2557
Chave publica: 71509
Testando exemplo de criptografia RSA
84 2294
101 12893
115 10294
116 8826
97 6974
110 2528
100 8836
111 3010
32 981
101 12893
120 12756
101 12893
109 10392
112 6807
108 5035
111 3010
32 981
100 8836
101 12893
32 981
99 8549
114 10813
105 6683
112 6807
116 8826
111 3010
103 13610
114 10813
97 6974
102 9670
105 6683
97 6974
32 981
82 9195
83 9482
65 9971
b'\xff\xfe\xf6\x08]26(z">\x1b\xe0\t\x84"\xc2\x0b\xd5\x03]2\xd41]2\x98(\x97\x1a\xab\x13\xc2\x0b\xd5\x03\x84"]2\xd5\x03e!=*\x1b\x1a\x97\x1az"\xc2\x0b*5=*>\x1b\xc6%\x1b\x1a>\x1b\xd5\x03\xeb#\n%\xf3&'

2294 9340
12893 8200
10294 12842
8826 4744
6974 8196
2528 7052
8836 8199
3010 3582
981 13916
12893 8200
12756 2434
12893 8200
10392 11679
6807 13996
5035 3579
3010 3582
981 13916
8836 8199
12893 8200
981 13916
8549 99
10813 7056
6683 5890
6807 13996
8826 4744
3010 3582
13610 5888
10813 7056
6974 8196
9670 13986
6683 5890
6974 8196
981 13916
9195 5867
9482 13967
9971 10478
⑼ ㈪ኈ ᮌ ෾㙜 ং ⶟㚬෻෾㙜  㙜cᮐᜂ㚬ኈ෾ᜀᮐ 㚢ᜂ 㙜᛫㚏⣮

Answer 1

There are several problems here.

1. Your prime number generator is broken. In the example you gave, 169 is equal to 13², so this value of p is of no use.

2. Conventionally, the public exponent (e) is a fixed small number like 257 or 65537. There's no need to choose a number that's larger than phi, and having a value of e (71509) that's greater than n (15041) makes no sense whatsoever.

3. You should calculate the private exponent (d) by using the extended Euclidean algorithm. I'm not convinced that the method you're using will give reliable results. (Strictly speaking, you should be using Carmichael's totient function in any case.)

4. Obviously encrypting individual characters provides no security. To work with larger values of p and q, you'll need to use modular exponentiation. Fortunately, this is built in to Python: (c ** d) % n can be replaced with pow(c, d, n), which is much faster and won't crash for large values of d. The sympy Python library has a lot of functions that you might find useful, including randprime() and gcdex() (extended Euclidean algorithm). Just type in pip install sympy at the command line to install it, if it isn't already available.