import random
from sympy import isprime

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

def modinv(a, m):
    m0, x0, x1 = m, 0, 1
    if m == 1:
        return 0
    while a > 1:
        q = a // m
        m, a = a % m, m
        x0, x1 = x1 - q * x0, x0
    if x1 < 0:
        x1 += m0
    return x1

def generate_prime_candidate(length):
    p = random.getrandbits(length)
    # Apply a mask to set MSB and LSB to 1 to ensure a proper length prime
    p |= (1 << length - 1) | 1
    return p

def generate_large_prime(length=1024):
    p = 4
    while not isprime(p):
        p = generate_prime_candidate(length)
    return p

def generate_keypair(keysize):
    p = generate_large_prime(keysize)
    q = generate_large_prime(keysize)
    n = p * q
    phi = (p - 1) * (q - 1)

    # Choose e
    e = random.randrange(2, phi)
    g = gcd(e, phi)
    while g != 1:
        e = random.randrange(2, phi)
        g = gcd(e, phi)

    # Generate d
    d = modinv(e, phi)

    return ((n, e), (n, d))

def decrypt(private_key, ciphertext):
    n, d = private_key
    # Decrypt each character
    plain = [chr((char ** d) % n) for char in ciphertext]
    return ''.join(plain)

# RSA Key Generation
keysize = 8  # Small size for demonstration; use 1024 or 2048 for real applications
public_key, private_key = generate_keypair(keysize)

print(f"Public Key: {public_key}")
print(f"Private Key: {private_key}")

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