---

import random
from sympy import randprime, mod_inverse
from math import gcd

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

# Генерация ключей
def generate_keys(bits=16):
    p = randprime(2**(bits-1), 2**bits)
    q = randprime(2**(bits-1), 2**bits)
    n = p * q
    phi = (p - 1) * (q - 1)

    e = 65537
    if not are_coprime(e, phi):
        e = randprime(3, phi)

    d = mod_inverse(e, 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

# Основная программа
public_key, private_key = generate_keys(bits=16)
print("Открытый ключ:", public_key)
print("Закрытый ключ:", private_key)

message = "Пример длинного сообщения RSA, больше чем 2n символов!"
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)