Write Python code to encrypt and decrypt messages using RSA encryption without external…
- User
Write Python code to encrypt and decrypt messages using RSA encryption without external libraries.
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 coregenerate_keypair()function is taking shape, and I'm using random values foreand calculating the public/private keys. My current focus is on guaranteeing the coprimality ofeand 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 themain()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 keydfor 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 thegenerate_keypair()method.Here is a complete Python implementation of RSA encryption and decryption.
This code uses no external libraries (like
cryptographyorpycryptodome). It uses Python's built-inrandommodule 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
- Key Generation:
- It picks two prime numbers and .
- It calculates the modulus .
- It calculates the totient .
- It selects a public exponent that is co-prime to .
- It calculates the private exponent using the Modular Multiplicative Inverse (Euclidean algorithm).
- Encryption (
pow(m, e, n)):- The script takes a string and converts every character into its ASCII integer value (
ord()). - It performs the calculation on every character.
- The result is a list of large integers.
- The script takes a string and converts every character into its ASCII integer value (
- Decryption (
pow(c, d, n)):- It takes the list of integers.
- It performs the calculation .
- It converts the resulting integer back to a character (
chr()).
⚠️ Security Warning
This code is for educational purposes only.
- Small Primes: The
generate_random_primefunction here uses very small numbers (between 100 and 300). Real RSA requires primes that are hundreds of digits long. - 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 seeing12345knows 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. - 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.
- Key Generation:
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.