2024-05-25 (en_US)

Implementation of classical RSA encryption, sort of a "prep" for Shor's Algorithm.

                    
# RSA encryption/decryption

import random

def is_prime(n):
    if n <= 1:
        return False
    elif n <= 3:
        return True
    elif 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):
    while b != 0:
        a, b = b, a % b
    return a

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

def generate_keypair(p, q):
    if not (is_prime(p) and is_prime(q)):
        raise ValueError("Both numbers must be prime.")
    elif p == q:
        raise ValueError("p and q cannot be equal.")
    n = p * q
    phi = (p - 1) * (q - 1)
    e = 65537  # Commonly used prime for e
    if gcd(e, phi) != 1:
        raise ValueError("e and phi are not coprime. Choose different primes.")
    d = mod_inverse(e, phi)
    return ((e, n), (d, n))

def encrypt(public_key, plaintext):
    e, n = public_key
    if plaintext >= n:
        raise ValueError("The plaintext is too large for the key size.")
    cipher = pow(plaintext, e, n)
    return cipher

def decrypt(private_key, ciphertext):
    d, n = private_key
    plain = pow(ciphertext, d, n)
    return plain

# Example usage:
p = 61
q = 53

public_key, private_key = generate_keypair(p, q)
print("Public key:", public_key)
print("Private key:", private_key)

message = 42  # Must be less than n
print("Original message:", message)

encrypted_msg = encrypt(public_key, message)
print("Encrypted message:", encrypted_msg)

decrypted_msg = decrypt(private_key, encrypted_msg)
print("Decrypted message:", decrypted_msg)