I was recently tasked with implementing RSA encryption through python. 

While I could have used an encryption library that was already written (and tested and verified to be secure..), the assignment was for the fun of it and not protecting any real world communication so I thought it would be fun to roll my own RSA encryption scheme and see how it shakes out.

If you, like me, feel as though the best way to understand something is to code it, then this post is for you.

Assumptions I make about you as the reader:

• You already know and understand the basics of asymmetric encryption
• You are familiar with object oriented programming
• You can read and follow python code

If the first point doesn’t apply, you should check out this article and then come back and check out my coding solution.

Let’s Begin

In general, I usually start out by building out a scaffolding for my objects.  No real meat on anything.  Just a quick, blueprint of the things I know I will need to make my object work.

class RSA:
    def __init__(self, desired_entropy):
        self.entropy = desired_entropy

    def create_key_pair(self):
        pass

    def encrypt(self, plaintext):
        pass
    
    def decrypt(self, ciphertext):
        pass

At this point, I know I need an RSA class that will encrypt and decrypt data.  The desired_entropy instance parameter will allow anyone using the object to dictate how many bits of entropy are used while setting up the keys: which will be the focus of the next snippet.

from random import randrange

class RSA:
    ---snipped--
    def create_key_pair(self):
        n = 10000
        sieve = set(range(2, n+1))
        primes = []
        while sieve:
            prime = min(sieve)
            primes.append(prime)
            sieve -= set(range(prime, n+1, prime))

        p = primes[randrange(len(primes))]
        q = primes[randrange(len(primes))]
        phi = (p - 1) * (q - 1)
        
        n = p * q
        e = self.get_e(phi)
        d = self.get_d(phi)

        self.public_key = (n, e)
        self.private_key = (n, d)

    def get_e(self, phi):
        pass

    def get_d(self, phi):
        pass
    ---snipped--

This provides us a basic start to our key generation.  Arguably, this is a naive approach and will not scale to the size of primes we will need to use but we can circle back and make it more robust at a later time.

Now, we have to fill in our get_d and get_e methods. Let’s start with selecting our e.

from math import gcd
---snipped--
def get_e(self, phi):
    k = 16
    e = 2 ** k + 1
    while e < phi:
        _gcd = gcd(e, phi)
        if _gcd == 1:
            return e
        else:
            k += 1
            e = 2 ** k + 1
---snipped--

This starts at 65537 and checks that our e selection has 1 as the greatest common denominator with phi.

Now that we have e, we need to calculate d.  Because the formula for calculating d requires calculating the modular multiplicative inverse of e, the best way that to calculate d is with the extended euclidean algorithm. So, we’ll rename get_d to get_inverse and calculate d from there.

def create_key_pair(self):
    ---snipped---
    extended_euclidean = self.get_inverse(e, phi)
    d = extended_euclidean[1]
    if d < 0:
        d += phi
    ---snipped---

def get_inverse(self, a, b): 
    if a == 0 : 
        return b, 0, 1    
    gcd, n, m = self.get_inverse(b % a, a) 
    x = m - (b // a) * n 
    y = n 
    return gcd, x, y

Notice that get_inverse can also be used to retrieve the greatest common denominator for two numbers as well.  We’ll include that in our get_e function when we begin to refactor.

Also, d has the potential to be a negative number when being returned by the EEA algorithm.  But, because we are using modular mathematics, we can easily maintain a valid solution while changing it to a positive number by adding our mod value: in this case phi.

Now that we have our basic building blocks for the algorithm, Let’s go ahead and use them in the encrypt and decrypt methods.

def encrypt(self, plaintext):
    n = self.public_key[0]
    e = self.public_key[1]

    return "".join([hex(pow(ord(c), e, n)) for c in plaintext])


def decrypt(self, ciphertext):
    from re import split
    n = self.private_key[0]
    d = self.private_key[1]

    ciphertext = [int(i, 16) for i in split(r"0x", ciphertext) if i]
    return "".join([chr(pow(c, d, n)) for c in ciphertext])

This should be easy enough to understand.  Encryption returns a string of hex representing the encrypted data.  Decryption converts the hex into integers and uses that to calculate the string.

Last up, we need some code to actually test out the new class.

if __name__ == "__main__":
    rsa = RSA(0)
    rsa.create_key_pair()
    user_input = input("input to encrypt:\n>> ")
    encrypted = rsa.encrypt(user_input)
    print(encrypted)
    decrypted = rsa.decrypt(encrypted)
    print(decrypted)
    assert decrypted == user_input

Putting it all together and running the program should greet you with an input prompt that allows you to type in some data to be encrypted and decrypted.  In this version, we initialize the RSA object with a desired entropy of 0.  This can be any value whatsoever because the code does not yet use the desired_entropy variable.

The program as it stands offers little more than any other naive implementation of RSA.  While it may be a decent place to start if you are just barely getting your feet under you, it needs work if we want it to be able to handle the size of numbers required for real world RSA usage.

Thus, refactoring this base program and adding in the ability to work with much larger numbers will be the subject of the next post.  Hope to see you there.

References:

RSA Algorithm: Theory and Implementation in Python