import random
from time import perf_counter

def generate_prime(n):
  """Generates a random prime number of n bits."""
  while True:
    p = random.randrange(2**(n-1) + 1, 2**n)
    if is_prime(p):
      return p

def is_prime(n):
  """Checks if a number is prime using a simple primality test."""
  if n <= 1:
    return False
  if n <= 3:
    return True
  if n % 2 == 0 or n % 3 == 0:
    return False
  i = 5
  while i * i <= n:
    if n % i == 0 or n % (i + 2) == 0:
      return False
    i += 6
  return True

def gcd(a, b):
  """Calculates the greatest common divisor (GCD) of two numbers."""
  while b:
    a, b = b, a % b
  return a

def generate_keys(p, q):
  """Generates RSA public and private keys with CRT components."""
  n = p * q
  phi = (p - 1) * (q - 1)
  e = random.randrange(1, phi)
  while gcd(e, phi) != 1:
    e = random.randrange(1, phi)
  d = pow(e, -1, phi)
  dp = d % (p - 1)
  dq = d % (q - 1)
  qInv = pow(q, -1, p)  # Modular inverse of q (mod p)
  return ((e, n), (dp, dq, qInv, n))  # Public, Private keys with CRT components

def encrypt(message, public_key):
  """Encrypts a message using the public key."""
  e, n = public_key
  m = int(message.encode('utf-8').hex(), 16)
  start_time = perf_counter()
  c = pow(m, e, n)
  encrypt_time = (perf_counter() - start_time) * 1000  # Convert to milliseconds
  return c, encrypt_time

def decrypt_crt(ciphertext, private_key):
  """Decrypts a message using the private key with CRT."""
  dp, dq, qInv, n = private_key
  start_time = perf_counter()
  m1 = pow(ciphertext, dp, p)
  m2 = pow(ciphertext, dq, q)
  h = (m1 - m2) * qInv % p
  m = m2 + h * q
  decrypt_time = (perf_counter() - start_time) * 1000  # Convert to milliseconds
  return bytes.fromhex(hex(m)[2:]).decode('utf-8'), decrypt_time

if __name__ == '__main__':
  message = "This is a secret message!"
  
  # Generate large primes (adjust bit size as needed)
  p = generate_prime(512)
  q = generate_prime(512)

  # Generate public and private keys with CRT components
  public_key, private_key = generate_keys(p, q)

  # Encrypt the message
  ciphertext, encrypt_time = encrypt(message, public_key)
  print("Encrypted message:", ciphertext)
  print("Encryption time:", encrypt_time, "milliseconds")

  # Decrypt the message using CRT
  decrypted_message, decrypt_time = decrypt_crt(ciphertext, private_key)
  print("Decrypted message:", decrypted_message)
  print("Decryption time:", decrypt_time, "milliseconds")