Skip to content
TheChatArchiveThe Chat Archive
GeminiGemini 3 Pro Preview· googleHugging Face Frontier Reasoning Traces

Write Python code to encrypt and decrypt messages using RSA encryption without external…

  1. User

    Write Python code to encrypt and decrypt messages using RSA encryption without external libraries.

  2. Gemini Assistant

    Analyzing RSA Implementation

    I've been drilling into the core concepts of RSA encryption and decryption. My focus is now shifting to the practical application of number theory. I'm visualizing the modular arithmetic and exponentiation needed. I'm starting to sketch out the fundamental algorithms.

    Focusing On Implementation Details

    \n\n

    I'm now diving deep into the practical implementation of RSA, specifically keeping in mind the constraint of avoiding external libraries. I'm actively working on translating the theoretical steps of key generation, encryption, and decryption into functional Python code. Currently, my focus is on ensuring the core modular exponentiation and inverse calculations are correct, with emphasis on managing large numbers efficiently within the built-in data types.

    Building Prime Number Tools

    \n\n

    My current effort is on robustifying the prime number-related components. I've successfully implemented the GCD function, crucial for later steps. I'm actively working through the modular inverse calculation, which presents a significant challenge. I'm leaning toward using the Extended Euclidean Algorithm. Also, I'm considering integrating a simple random prime generator. I want to balance usability with security, even in a simplified "toy" example, and I want user input of prime numbers.

    Evaluating Inverse Calculations

    \n\n

    My primary focus is now on crafting a robust and understandable implementation of the modular multiplicative inverse, directly linked to RSA's core mechanics. I've chosen to include the Extended Euclidean Algorithm implementation, which allows for teaching purposes. I'm also considering highlighting how Python's built-in pow(e, -1, phi) can achieve the same result elegantly. I'm aiming for clarity in showcasing how the inverse is determined for beginners, even if using an optimized built-in for practical use. The goal is a balance of educational value and efficient code.

    Developing Key Generation Logic

    \n\n

    I'm now implementing the core key generation logic. The Extended Euclidean Algorithm for modular inverses remains central to this. I've now added a generate_prime() function. I'm focusing on crafting a helper function for primality testing. I'm choosing a basic trial division for now, to ensure broad compatibility and clarity. The core generate_keypair() function is taking shape, and I'm using random values for e and calculating the public/private keys. My current focus is on guaranteeing the coprimality of e and phi for the public key.

    Constructing Encryption Methods

    \n\n

    My current implementation is firmly focused on the encryption and decryption logic. I've designed the encryption method to accept a public key and plaintext, converting each character to its numerical equivalent, raising it to the power of the public key's exponent, and applying modular arithmetic. The process mirrors the core RSA formula. Similarly, the decryption process takes the private key and ciphertext, calculates the inverse process, and reconstructs the original message from the decrypted numerical values. I'm focusing on preserving the essential RSA logic, keeping it clear and understandable, albeit at the cost of production-level security.

    Implementing Modular Exponentiation

    \n\n

    My primary focus is now on optimizing the encryption and decryption methods using Python's built-in pow() for modular exponentiation, significantly improving speed. I'm replacing the naive implementation, now including a final check and correction, as the modular inverse, while correct, can occasionally result in a negative private key. I'm finalizing the structure of the main() function to simulate user interaction, incorporating all preceding components and adding detailed comments to clarify the RSA core. I am now checking the constraints.

    Adding Educational Disclaimers

    I'm now integrating a critical security disclaimer, emphasizing this RSA implementation is for learning, not production use, due to lack of padding and small prime values. I've completed the basic encryption/decryption functions using the pow() function, but now I'm working on refactoring with the iterative Extended Euclidean algorithm for modular inverse. I'm focusing on providing the final code with detailed docstrings, the main function as example and a final warning about security concerns.

    Finalizing Key Handling

    \n\n

    I'm now integrating the iterative Extended Euclidean Algorithm for modular inverse directly into the key generation phase. The mod_inverse() function appears robust, and I've ensured it's correctly calculating the private key d for decryption. I'm focusing on handling potential edge cases and making the code more readable with detailed documentation. The entire process now ensures that a modular multiplicative inverse exists for the public exponent, so that the RSA system functions. I am now refining the generate_keypair() method.

    Here is a complete Python implementation of RSA encryption and decryption.

    This code uses no external libraries (like cryptography or pycryptodome). It uses Python's built-in random module to generate keys and standard math functions to perform the Modular Exponentiation.

    The Python Code

    import random
    
    # --- Helper Mathematics Functions ---
    
    def gcd(a, b):
        """Euclidean algorithm to calculate Greatest Common Divisor."""
        while b != 0:
            a, b = b, a % b
        return a
    
    def mod_inverse(e, phi):
        """
        Extended Euclidean Algorithm to find the modular multiplicative inverse.
        Finds 'd' such that (d * e) % phi == 1.
        """
        d = 0
        x1 = 0
        x2 = 1
        y1 = 1
        temp_phi = phi
        
        while e > 0:
            temp1 = temp_phi // e
            temp2 = temp_phi - temp1 * e
            temp_phi = e
            e = temp2
            
            x = x2 - temp1 * x1
            y = d - temp1 * y1
            
            x2 = x1
            x1 = x
            d = y1
            y1 = y
        
        if temp_phi == 1:
            return d + phi
    
    def is_prime(num):
        """Simple check to see if a number is prime."""
        if num < 2:
            return False
        for i in range(2, int(num ** 0.5) + 1):
            if num % i == 0:
                return False
        return True
    
    def generate_random_prime(min_val, max_val):
        """Generates a random prime number within a range."""
        prime = random.randint(min_val, max_val)
        while not is_prime(prime):
            prime = random.randint(min_val, max_val)
        return prime
    
    # --- RSA Core Functions ---
    
    def generate_keypair(p, q):
        """
        Generates the public and private keys based on primes p and q.
        Returns ((e, n), (d, n)) -> ((public_key), (private_key))
        """
        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 the same.")
    
        # 1. Calculate n
        n = p * q
    
        # 2. Calculate phi(n) (Totient)
        phi = (p - 1) * (q - 1)
    
        # 3. Choose an integer e such that 1 < e < phi and gcd(e, phi) = 1
        e = random.randrange(1, phi)
        # Use Euclidean algorithm to verify that e and phi are coprime
        while gcd(e, phi) != 1:
            e = random.randrange(1, phi)
    
        # 4. Calculate d such that (d * e) % phi = 1
        d = mod_inverse(e, phi)
        
        # Return Public Key (e, n) and Private Key (d, n)
        return ((e, n), (d, n))
    
    def encrypt(public_key, plaintext):
        """
        Encrypts a message using the public key.
        Format: c = m^e % n
        """
        e, n = public_key
        
        # Convert each character to its integer code point
        # and raise it to power 'e' mod 'n'
        cipher = [pow(ord(char), e, n) for char in plaintext]
        return cipher
    
    def decrypt(private_key, ciphertext):
        """
        Decrypts a message using the private key.
        Format: m = c^d % n
        """
        d, n = private_key
        
        # Raise each number in the cipher list to power 'd' mod 'n'
        # and convert back to character
        try:
            plain = [chr(pow(char, d, n)) for char in ciphertext]
            return ''.join(plain)
        except TypeError:
            return "Error decoding message." # Handles cases where decryption generates non-char ints
    
    # --- Main Execution ---
    
    if __name__ == '__main__':
        print("=== RSA Encryption/Decryption (No Libraries) ===")
        
        # 1. Generate Primes
        # In real-world scenarios, these numbers are massive (1024+ bits).
        # We use smaller primes here for speed and demonstration.
        print("Generating prime numbers...")
        p = generate_random_prime(100, 300)
        q = generate_random_prime(100, 300)
        
        print(f"Primes generated: p={p}, q={q}")
    
        # 2. Generate Keys
        print("Generating keypair...")
        public, private = generate_keypair(p, q)
        
        print(f"Public Key: {public}")
        print(f"Private Key: {private}")
        
        # 3. Message to Encrypt
        message = "Hello, World! This is RSA."
        print(f"\nOriginal Message: {message}")
        
        # 4. Encrypt
        encrypted_msg = encrypt(public, message)
        print(f"Encrypted Message (Int List): {encrypted_msg}")
        
        # 5. Decrypt
        decrypted_msg = decrypt(private, encrypted_msg)
        print(f"Decrypted Message: {decrypted_msg}")
    
        # Verification
        if message == decrypted_msg:
            print("\nSUCCESS: The decrypted message matches the original!")
        else:
            print("\nFAILURE: Something went wrong.")
    

    How it works

    1. Key Generation:
      • It picks two prime numbers pp and qq.
      • It calculates the modulus n=p×qn = p \times q.
      • It calculates the totient ϕ(n)=(p−1)(q−1)\phi(n) = (p-1)(q-1).
      • It selects a public exponent ee that is co-prime to ϕ(n)\phi(n).
      • It calculates the private exponent dd using the Modular Multiplicative Inverse (Euclidean algorithm).
    2. Encryption (pow(m, e, n)):
      • The script takes a string and converts every character into its ASCII integer value (ord()).
      • It performs the calculation c=me(modn)c = m^e \pmod n on every character.
      • The result is a list of large integers.
    3. Decryption (pow(c, d, n)):
      • It takes the list of integers.
      • It performs the calculation m=cd(modn)m = c^d \pmod n.
      • It converts the resulting integer back to a character (chr()).

    ⚠️ Security Warning

    This code is for educational purposes only.

    1. Small Primes: The generate_random_prime function here uses very small numbers (between 100 and 300). Real RSA requires primes that are hundreds of digits long.
    2. Textbook RSA: This is "Textbook RSA." It encrypts character-by-character. This is vulnerable to frequency analysis (e.g., if the letter 'A' encrypts to 12345, an attacker seeing 12345 knows it is 'A'). Production RSA uses Padding Schemes (like OAEP) to randomize the input before encryption so that encoding "Hello" twice results in different ciphertexts.
    3. Efficiency: This iterates over every character. Real implementations treat the message as a byte block and convert the whole block into one giant integer for calculation.

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.