CRT.py

import random

# Generate two large prime numbers p and q
def generate_primes():
    primes = []
    while len(primes) < 2:
        p = random.randint(100, 1000)
        if all(p % i != 0 for i in range(2, int(p ** 0.5) + 1)):
            primes.append(p)
    return primes

# Generate public and private keys
def generate_keys():
    p, q = generate_primes()
    n = p * q
    phi = (p - 1) * (q - 1)

    e = random.randint(1, phi)
    while gcd(e, phi) != 1:
        e = random.randint(1, phi)

    d = mod_inverse(e, phi)

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

# Encrypt a message using the public key
def encrypt(message, public_key):
    e, n = public_key
    ciphertext = [pow(ord(char), e, n) for char in message]
    return ciphertext

# Decrypt a message using the private key and Chinese Remainder Theorem
def decrypt(ciphertext, private_key, p, q):
    d, n = private_key
    dp = d % (p - 1)
    dq = d % (q - 1)
    q_inv = mod_inverse(q, p)
    plaintext = []
    for c in ciphertext:
        mp = pow(c, dp, p)
        mq = pow(c, dq, q)
        h = (q_inv * (mp - mq)) % p
        m = mq + h * q
        plaintext.append(chr(m))
    return ''.join(plaintext)

# Extended Euclidean algorithm to calculate gcd and modular inverse
def extended_euclid(a, b):
    if b == 0:
        return (a, 1, 0)
    else:
        gcd, x, y = extended_euclid(b, a % b)
        return (gcd, y, x - (a // b) * y)

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

def mod_inverse(a, n):
    gcd, x, y = extended_euclid(a, n)
    if gcd != 1:
        return None
    else:
        return x % n

# Test the RSA algorithm with Chinese Remainder Theorem
public_key, private_key = generate_keys()
message = 'hello world'
print(f"Original Message: {message}")
ciphertext = encrypt(message, public_key)
print(f"Encrypted Message: {ciphertext}")
p, q = generate_primes()
plaintext = decrypt(ciphertext, private_key, p, q)
print(f"Decrypted Message: {plaintext}")

This is an Implementation of Chinese Theorem in RSA algorithm