import math
import random

def is_prime(num):
    """Verifică dacă un număr este prim."""
    if num <= 1:
        return False
    if num <= 3:
        return True
    if num % 2 == 0 or num % 3 == 0:
        return False
    i = 5
    while i * i <= num:
        if num % i == 0 or num % (i + 2) == 0:
            return False
        i += 6
    return True

def generate_prime(min_val=100, max_val=1000):
    """Generează un număr prim într-un interval specificat."""
    prime = random.randint(min_val, max_val)
    while not is_prime(prime):
        prime = random.randint(min_val, max_val)
    return prime

def extended_gcd(a, b):
    """Calculează inversul modular folosind algoritmul Euclid extins."""
    if a == 0:
        return b, 0, 1
    gcd, x1, y1 = extended_gcd(b % a, a)
    x = y1 - (b // a) * x1
    y = x1
    return gcd, x, y

def mod_inverse(a, m):
    """Returnează inversul modular al lui a modulo m."""
    gcd, x, _ = extended_gcd(a, m)
    if gcd != 1:
        raise ValueError("Inverse does not exist")
    else:
        return x % m

def generate_keys():
    """Generează perechea de chei publică și privată pentru RSA."""
    # Generează doi numere prime distincte
    p = generate_prime()
    q = generate_prime()
    while q == p:
        q = generate_prime()

    # Calculează n
    n = p * q

    # Calculează funcția Euler φ(n)
    phi_n = (p - 1) * (q - 1)

    # Alege un număr întreg e astfel încât 1 < e < φ(n) și e este coprime cu φ(n)
    e = random.randrange(2, phi_n)
    while math.gcd(e, phi_n) != 1:
        e = random.randrange(2, phi_n)

    # Calculează d ca inversul modular al lui e modulo φ(n)
    d = mod_inverse(e, phi_n)

    # Returnează perechea de chei (publică și privată)
    return (e, n), (d, n)

def encrypt(message, public_key):
    """Criptează mesajul folosind cheia publică."""
    e, n = public_key
    encrypted_message = [pow(ord(char), e, n) for char in message]
    return encrypted_message

def decrypt(encrypted_message, private_key):
    """Decriptează mesajul folosind cheia privată."""
    d, n = private_key
    decrypted_message = ''.join([chr(pow(char, d, n)) for char in encrypted_message])
    return decrypted_message

def main():
    try:
        # Generează perechea de chei
        public_key, private_key = generate_keys()
        print(f"Cheia publică: {public_key}")
        print(f"Cheia privată: {private_key}")

        # Mesajul original
        message = input("Introduceți mesajul pentru criptare: ")
        print(f"Mesaj original: {message}")

        # Criptează mesajul
        encrypted_message = encrypt(message, public_key)
        print(f"Mesaj criptat: {encrypted_message}")

        # Decriptează mesajul
        decrypted_message = decrypt(encrypted_message, private_key)
        print(f"Mesaj decriptat: {decrypted_message}")

    except Exception as e:
        print(f"Eroare: {e}")

if __name__ == "__main__":
    main()