import random
from random import randint

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

def coprime(a, b):
    return gcd(a, b) == 1

def primes(N):
    primes = []

    for target_num in range(2, N):
        is_prime = True
        for i in range(2, target_num):
            if target_num % i == 0:
                is_prime = False
        if is_prime:
            primes.append(target_num)
    return primes


list = primes(100)
p, q = 0, 0
while p == q:
    p = random.choice(list)
    q = random.choice(list)
N = p * q
F = (p - 1)*(q - 1)
while True:
    e = randint(2, F-1)
    if coprime(e,F):
        break
d = 0
while True:
    d+=1
    if ((d*e)%F == 1) and (d != e):
        break
Message = input('Введите сообщение: ')

enc_Set = []

for i in Message:
    enc_Set.append(ord(i))

# Шифрование
rsa_enc = []
rsa_enc_text = []
for i in enc_Set:
    rsa_enc.append((i**e)%N)
for i in rsa_enc:
    rsa_enc_text.append(chr(i))
print('Зашифрованное сообщение: ', "".join(rsa_enc_text))

# Дешифрование
decryption = []
for i in rsa_enc:
    decryption.append((i**d)%N)
decryption_Set = []
for i in decryption:
    decryption_Set.append(chr(i))
print('Расшифрованное сообщение: ', "".join(decryption_Set))