Python RSA Encrypt Decrypt Example

Let’s do an RSA Algorithm Encrypt/Decrypt Example with Python. We will be using Python 3.8.10. Let’s go!🔥🔥

RSA is a public/private key based system of cryptography developed in the 1970s. The term RSA is an acronym for Rivest–Shamir–Adleman, which are the surnames of its creators. AES encryption, alternatively, is a block cipher.

In this system of encryption there are two keys: a public key and a private key. Recall that a key is basically a string of characters used within an encryption algorithm.

Someone using RSA encryption would have to create and publish a public key based on two large prime numbers. The prime numbers are usually kept secret. Messages or data can be encrypted by anyone using the public key, but can only be decrypted by someone who knows the specific prime numbers.

Following is a simple implementation of the RSA algorithm. Let’s write some code:

import random
import sympy

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

def multiplicative_inverse(e, phi):
    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 generate_keypair(p, q):
    n = p*q
    phi = ((p-1)*(q-1))

    e = random.randrange(1, phi)

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

    d = multiplicative_inverse(e, phi) 

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


def encrypt(pk, plaintext):
    key, n = pk
    cipher = [(ord(char) ** key) % n for char in plaintext]
    return cipher


def decrypt(pk, ciphertext):
    key, n = pk
    plain = [chr((char ** key) % n) for char in ciphertext]
    return ''.join(plain)


p = sympy.randprime(1, 100)
q = sympy.randprime(1, 100)

public, private = generate_keypair(p, q)

message = input("Type message: ")

encrypted_msg = encrypt(public, message)

print(f"{encrypted_msg}")

print (f"Decrypted Message is : {decrypt(private,encrypted_msg)}")

Let’s explain what is happening here, step by step:

1. First we import our modules: random and sympy.
2. We define our function gcd() which will take two integers: a and b. Recall that the GCD in Math is short for Greatest Common Divisor and is also called the Highest Common Factor or HCF. This is the largest positive integer that would divide both numbers without leaving a fraction. This function simply takes two integers a and b and returns the GCD.
3. The multplicative_inverse() function is used to calculate the Multiplicative Inverse which is part of our private key. The Multiplicative Inverse is defined as a number which when multiplied by the original number gives the product as 1. Find out more HERE.
4. The generate_keypair() function does just that: generate our public and private keys. It is the core component of the RSA algorithm. Here’s a rough outline of how this is done:
   • The function accepts two random prime integers p and q. These numbers have to be prime and are kept secret.
   • The product of p and q is calculated as n. Value n is the modulus of both the public and private key and is also used as the key length. Also, as you can see from the return value of the generate_keypair() function, it is disclosed as part of the public key.
   • We calculate phi which is the totient function of n, specifically the Euler’s totient function. This is the function that counts how many integers below a given integer are coprime to it. Recall that coprime refers to two or more positive integers having no positive integer factors in common aside from 1. Value phi is also kept private.
   • We derive the random integer e such that, e and phi are coprime. This is what the loop is doing.
   • Calculate d, which is the multiplicative inverse of e and phi. Recall that we defined this function earlier. Variable d is kept as the private key exponent.
   • The function will return a pair of tuples, one for our public key and one for our private key.
   • The above steps are all of the usual steps of the RSA algorithm.
5. The encrypt() function will accept the tuple pk (which is our public key) and the plaintext to be encrypted. Recall that the public key was generated in generate_keypair() and contains both integer e (used also as the key) and integer n (the modulus). Specifically, we encrypt the plaintext one character at a time using the formula ord(char)^key mod n. Recall that function ord() returns an integer representing a unicode character. This function will return our ciphertext cipher which is the encrypted plaintext.
6. The decrypt() function will accept the tuple pk (which is our private key) and the encrypted ciphertext. Recall that our private key tuple contains the private key exponent d and the modulus integer n. It will do the reverse of the encrypt() function, decrypting the ciphertext one character at a time and returning the plaintext which is our original string.
7. We will generate our two random primes p and q, both between 1 and 100, at runtime. These values will passed to generate_keypair() and will generate and return our public and private key, as previously described.
   • We are prompted to type a text message as input.
   • The message will be encrypted with the public key and then it will be decrypted with the private key according to the RSA algorithm.

Not too bad right? When this code executes, and all goes well, we will get the following output, or something close to it:

#output
# Type message: Code Everyday!
# [69, 1429, 584, 3210, 2182, 1862, 1925, 3210, 378, 1304, 584, 1940, 1304, 144]
# Decrypted Message is : Code Everyday!

It will print the original message input by the user, the ciphertext which will be a tuple and the decrypted plaintext. In testing, I found that the encryption/decryption may not produce the desired results on random occasions. Keep trying and it will work. Remember this is a simple implementation of RSA. In practice it will get far more complex that this.

Use this code at your own risk! The keys used here are easy to figure out and should not be used to secure sensitive real world data. This is only an example.

We hope this helped. Find out more about the RSA Algorithm HERE and HERE. Good luck! 👌👌👌