---

from math import gcd

# Проверка взаимной простоты
def are_coprime(a, b):
    return gcd(a, b) == 1

# Генерация ключей с заданными p, q, e
def generate_keys(p, q, e):
    n = p * q
    phi = (p - 1) * (q - 1)

    if not are_coprime(e, phi):
        raise ValueError("e и φ(n) не взаимно просты!")

    # Находим d — обратное по модулю
    d = pow(e, -1, phi)
    return (e, n), (d, n)

# Шифрование
def encrypt(message, public_key):
    e, n = public_key
    blocks = [ord(ch) for ch in message]
    cipher = [pow(m, e, n) for m in blocks]
    return cipher

# Дешифровка
def decrypt(cipher, private_key):
    d, n = private_key
    blocks = [pow(c, d, n) for c in cipher]
    message = ''.join(chr(m) for m in blocks)
    return message

# Задаем числа вручную
p, q, e = 61, 53, 17
public_key, private_key = generate_keys(p, q, e)

print("Открытый ключ:", public_key)
print("Закрытый ключ:", private_key)

message = "RSA пример с заданными числами!"
print("Исходное сообщение:", message)

cipher = encrypt(message, public_key)
with open("cipher.txt", "w", encoding="utf-8") as f:
    f.write(' '.join(map(str, cipher)))

print("Зашифрованный текст сохранен в cipher.txt")

decrypted = decrypt(cipher, private_key)
print("Расшифрованное сообщение:", decrypted)