Recently in my discrete mathematics class we had the assignment to leave a message to the class and decrypt and respond in RSA to our peers as well. As you may be aware this type of work would be tedious to do by hand. While learning RSA is important this seemed like busywork and I didn’t want to do it. I also caught up on other coursework and took my final exam so I was pretty tired already. So like any good student instead of spending hours doing the math by hand, I spent thirty minutes scripting the entire assignment instead. I’m happy with the results and this post explains my thought process behind the program.

What tasks does my program need to do to be functional?

I want to do the bare minimum for this program to be practical. The first step was determining what the program does (user stories). I determined it needs to do the following:

  • It needs a method to encode text into a number.
  • It needs a method to decode a number into text.
  • It needs a method to decrypt a number.
  • And finally it needs a method to decrypt a number.

In practice, the only methods the user will usually use is the encrypt and decrypt text methods which use the encoder methods internally.

Encoding and Decoding Text

RSA only works on integers not text. So to solve this problem there needs to be a number that represents each letter and symbol. In the real world you would use an encoding scheme such as ASCII or UTF-8. My professor asked the class to use the numbers 01 through 26 to represent each letter of the alphabet, 32 to represent a space, and 27-31 to represent any symbols. I came up with the following dictionaries to encode and decode text. This does not support capitalization. The real the letters A through I exist at the top with the numbers 1 through 9 instead of 01 through 09 is because when decoding text the extra 0s are lost. This simplifies the lookup logic at the cost of a slightly larger dictionary. We are working with small messages and tiny prime numbers so it does not matter too much!

encoder_table = {
    
    'A': '1',
    'B': '2',
    'C': '3',
    'D': '4',
    'E': '5',
    'F': '6',
    'G': '7',
    'H': '8',
    'I': '9',

    'a': '01',
    'b': '02',
    'c': '03',
    'd': '04',
    'e': '05',
    'f': '06',
    'g': '07',
    'h': '08',
    'i': '09',
    'j': '10',
    'k': '11',
    'l': '12',
    'm': '13',
    'n': '14',
    'o': '15',
    'p': '16',
    'q': '17',
    'r': '18',
    's': '19',
    't': '20',
    'u': '21',
    'v': '22',
    'w': '23',
    'x': '24',
    'y': '25',
    'z': '26',
    '.': '27',
    ',': '28',
    '!': '29',
    '\'': '30',
    '(': '31',
    ' ': '32',
    ')': '33',
}

decoder_table = dict([(value, key) for key, value in encoder_table.items()])

How RSA Works

RSA is an encryption algorithm which has separate keys for encryption and decryption. These keys are called the public key and the private key. This is useful because anyone can encrypt a message but only someone with the secret key can decrypt it. It is similar to a hashing algorithm except reversible by anyone who knows the private key.

Key generation works by taking two prime numbers to generate a public and private key, these prime numbers should be kept a secret.

To encrypt text take the number you want to encrypt to the power of E, divide it by N (N is P times Q), and take the remainder as your encrypted number.

To decrypt take the number you want to decrypt to the power of D, divide it by N (N is P times Q), and take the remainder as your decrypted number. D is the modular inverse of E and ϕ(pq) (Totient).

How to generate Public and Private Keys

As explained above, in RSA you need to find a number called E and D. At a very basic level (E, N) is your public key and (D, N) is your private key. Your public key consists of E which is a prime number which is relatively prime to ϕ(pq) commonly called the Totient, and N which is P times Q. Your private key consists of D which is the modular inverse of E and the Totient and N which is P times Q. To calculate find the modular inverse you must use the Extended Euclidean Algorithm.

How to pick P and Q

This is the easiest part. You have to choose two unique prime numbers. These numbers are a base pair which are used to calculate your public and private keys.

How to calculate your Public Key

Your public key E is a number relatively prime to ϕ(pq) (totient), greater than 1 and less than the totient. It takes an euler function (totient). Our friends at StackOverflow did the work for us and wrote a method to calculate this in Python. While I don’t calculate E in my program as it’s just for encrypting and decrypting text I included the function for anyone who wants to play around with it. Currently the user must know P, Q, and E to decrypt or encrypt text which my assignment provided those numbers for us so it was no big deal.

# https://stackoverflow.com/a/55554571
def find_public_key_exponent(euler_function):
    """
    find_public_key_exponent(euler_function)

    Finds public key exponent needed for encrypting.
    Needs specific number in order to work properly.

    :param euler_function: the result of euler function for two primes.
    :return:               public key exponent, the element of public key.
    """

    e = 3

    while e <= 65537:
        a = euler_function
        b = e

        while b:
            a, b = b, a % b

        if a == 1:
            return e
        else:
            e += 2

    raise Exception("Cant find e!")

How to calculate your Private Key

To calculate your private key you need to take your public key E and ϕ(pq) (totient) and find it’s modular inverse. To do this you must use the Extended Euclidean Algorithm.

The Extended Euclidean Algorithm is a recursive function which takes two numbers and returns the largest common divisor. From there to find the modular inverse take the largest common divisor divide it by the totient, and take the remainder (D).

I was not sure how to do this in Python worsed by the fact it was 1AM when I coded this so I was over tired. Luckily someone did it for me and posted the code on StackOverflow so I didn’t have to figure it out.

# https://stackoverflow.com/a/55554571
def extended_euclidean_algorithm(a, b):
    """
    extended_euclidean_algorithm(a, b)

    The result is the largest common divisor for a and b.

    :param a: integer number
    :param b: integer number
    :return:  the largest common divisor for a and b
    """

    if a == 0:
        return b, 0, 1
    else:
        g, y, x = extended_euclidean_algorithm(b % a, a)
        return g, x - (b // a) * y, y


def modular_inverse(e, t):
    """
    modular_inverse(e, t)

    Counts modular multiplicative inverse for e and t.

    :param e: in this case e is a public key exponent
    :param t: and t is an Euler function
    :return:  the result of modular multiplicative inverse for e and t
    """

    g, x, y = extended_euclidean_algorithm(e, t)

    if g != 1:
        raise Exception('Modular inverse does not exist')
    else:
        return x % t

How to encrypt a number with RSA?

To encrypt a number take it to the power of E, divide it by N (N is P times Q), and take the remainder as your encrypted number.

How to decrypt a number with RSA?

To decrypt a number take it to the power of D, divide it by N (N is P times Q), and take the remainder as your decrypted number.

How my program has to work in practice

Now that the math has been explained let’s look at how the encrypt and decrypt methods work.

Let’s say we want to encrypt the text “Hello, World!” we would call our method like encrypt_text("Hello, World!", 3, 11, 3) where it needs our text then P, Q, and E. From there the method works letter by letter. I implemented it in code as you can see below. It takes loops over the string of text letter by letter. It uses the encode text method to get a number for each character and runs RSA encryption on it. Because of requirements for the assignment when X is between 1 and 9 it has to be written as 01 through 09. I used a simple if, elif, else statement to do this for me.

def encrypt_text(text, p, q, e):
    encrypted_text = ""
    keys = easy_rsa_keys(p, q, e)
    for c in text:
        x = str(int(encode_text(c))**e % keys["N"])

        if x == '1':
            encrypted_text += '01'
        elif x == '2':
            encrypted_text += '02'
        elif x == '3':
            encrypted_text += '03'
        elif x == '4':
            encrypted_text += '04'
        elif x == '5':
            encrypted_text += '05'
        elif x == '6':
            encrypted_text += '06'
        elif x == '7':
            encrypted_text += '07'
        elif x == '8':
            encrypted_text += '08'
        elif x == '9':
            encrypted_text += '09'
        else:
            encrypted_text += x
        
        encrypted_text += " "
    
    return encrypted_text

For decrypting text it works in a similar way. Let’s say I have the string 17 26 12 12 09 07 32 23 09 24 12 31 02 (Hello, World!). To decrypt it I have to take each number and run it through RSA decryption. This works as a loop over the string, I am careful to handle each part separately and split on the space. I run RSA decryption on each letter, run it through the decode text function and append the result to the decrypted text string. Lastly I do ensure the string is all lower case because my program does not support uppercase letters due to the assignment’s requirements to use a unique numbering scheme chosen by the professor.

def decrypt_text(text, p, q, e):
    decrypted_text = ""
    keys = easy_rsa_keys(p, q, e)

    for c in str(text).split(" "):
        decrypted_text += decode_text(int(c)**keys["D"] % keys["N"])

    return decrypted_text.lower()

Do not use this in production it’s not cryptographically secure!

I have to reiterate that this is not cryptographically secure as it is a simplified version of RSA which uses much smaller prime numbers. Please do not try to use this code to secure your data as it lacks many of the enhancements and security requirements used by real world implementations of RSA. Computers are very fast and will find your prime numbers P and Q very quickly.

Conclusion

Implementing my own RSA parser in Python was a fun project which saved time in one of my classes. I hope this insightful read and you have a greater understanding of the math behind RSA.