rsa.py

# RSA Encryption Implementation

# This script provides an implementation of the RSA encryption algorithm in Python. 

# RSA (Rivest–Shamir–Adleman) is one of the most widely used public-key encryption algorithms, used for secure communication and digital signatures.
# The script includes functions for generating RSA key pairs, encrypting messages, and decrypting ciphertexts. 
# It utilizes the Miller-Rabin primality test for generating large prime numbers and the extended Euclidean algorithm for finding modular inverses.
# This implementation allows users to create RSA objects with custom prime numbers (p and q) or generate random prime numbers within a specified limit. 
# It provides methods for encrypting and decrypting messages using the RSA public and private keys.

import random

# Function for modular exponentiation (a^b mod m)
def mod_pow(a, b, m):
    """
    Calculates a^b mod m using the binary exponentiation method.
    
    Args:
    - a: Base
    - b: Exponent
    - m: Modulus
    
    Returns:
    - Result of a^b mod m
    """
    a %= m
    result = 1
    while b > 0:
        if b % 2 == 1:
            result = (result * a) % m
        a = (a * a) % m
        b //= 2
    return result

# Extended Euclidean algorithm to find modular inverse
def extended_gcd(a, b):
    """
    Extended Euclidean algorithm to find the greatest common divisor (GCD) of two numbers
    and the coefficients x and y such that ax + by = gcd(a, b).
    
    Args:
    - a: First integer
    - b: Second integer
    
    Returns:
    - Tuple containing (gcd(a, b), x, y)
    """
    if b == 0:
        return (a, 1, 0)
    gcd, x, y = extended_gcd(b, a % b)
    return gcd, y, x - (a // b) * y

# Function to calculate modular inverse
def mod_inv(a, m):
    """
    Calculates the modular multiplicative inverse of a modulo m.
    
    Args:
    - a: Integer
    - m: Modulus
    
    Returns:
    - Modular inverse of a modulo m
    """
    gcd, x, _ = extended_gcd(a, m)
    if gcd != 1:
        raise ValueError("Modular inverse does not exist")
    return x % m

# Miller-Rabin primality test
def miller_rabin(n, k):
    """
    Miller-Rabin primality test to determine if a given number is prime.
    
    Args:
    - n: Number to be tested
    - k: Number of iterations
    
    Returns:
    - True if n is likely to be prime, False otherwise
    """
    if n <= 3:
        return n == 2 or n == 3
    d = n - 1
    r = 0
    while d % 2 == 0:
        r += 1
        d //= 2
    for _ in range(k):
        a = random.randrange(2, n - 1)
        x = mod_pow(a, d, n)
        
        if x == 1 or x == n - 1:
            continue
        
        witness = True
        
        for _ in range(r - 1):
            x = mod_pow(x, 2, n)
            if x == 1:
                return False
            if x == n - 1:
                witness = False
                break
        if witness:
            return False
    return True

# Function to generate a prime number using Miller-Rabin test
def generate_prime(bits, k=20):
    """
    Generates a prime number with a specified number of bits using the Miller-Rabin primality test.
    
    Args:
    - bits: Number of bits for the prime number
    - k: Number of iterations for the Miller-Rabin test
    
    Returns:
    - Prime number with the specified number of bits
    """
    while True:
        n = random.randrange(bits)
        if miller_rabin(n, k):
            return n

class RSA:
    def __init__(self, p, q):
        """
        Initializes the RSA encryption system with given prime numbers p and q.
        Generates public and private keys.
        
        Args:
        - p: First prime number
        - q: Second prime number
        """
        self.p = p
        self.q = q
        self.n = self.p * self.q  # Modulus
        self.phi = (self.p - 1) * (self.q - 1)  # Euler's totient function
        
        # Choose a public exponent e coprime with phi
        while True:
            e = random.randrange(2, self.phi - 1)
            gcd, m, n = extended_gcd(e, self.phi)
            if gcd == 1:
                self.e = e
                break
        
        # Calculate private exponent d
        self.d = mod_inv(self.e, self.phi)
    
    # Encrypts a message using public key
    def encrypt(self, message, e):
        """
        Encrypts a message using the public key.
        
        Args:
        - message: Message to be encrypted
        
        Returns:
        - Encrypted message
        """
        return mod_pow(message, e, self.n)
    
    # Decrypts a message using private key
    def decrypt(self, ciphertext):
        """
        Decrypts a ciphertext using the private key.
        
        Args:
        - ciphertext: Ciphertext to be decrypted
        
        Returns:
        - Decrypted message
        """
        return mod_pow(ciphertext, self.d, self.n)

def main():
    # Generate prime numbers p and q
    p = generate_prime(256)
    q = generate_prime(256)
    
    # Initialize RSA instances with prime numbers
    rsa_A = RSA(p, q)
    rsa_B = RSA(p, q)
    
    # Example message
    message = 207
    
    # Encrypt message using public key of B
    encrypted_message = rsa_A.encrypt(message, rsa_B.e)
    # Decrypt encrypted message using private key of B
    decrypted_message = rsa_B.decrypt(encrypted_message)
    
    # Print results
    print("Message:", message)
    print("Encrypted:", encrypted_message)
    print("Decrypted:", decrypted_message)

if __name__ == "__main__":
    main()