Implementing (Textbook) RSA in Python

6 min readMar 12, 2021

How RSA works and how you can make your own basic implementation

What is RSA?

RSA is a commonly used public-key cryptosystem, which means that when two users want to exchange a message using RSA, they do encryption with the opposite party’s public key, and decryption with their own private key (in a bit I’ll cover how these keys are calculated, and how to do this in Python). Public-key cryptosystems rely on one-way functions, which basically means that the operation to encrypt a message is fast, but decrypting the message without knowing the private key is very slow and difficult (not in polynomial time).

Quick note: If you need an implementation of RSA for the security of some project you are building, don’t use your own implementation! This is just textbook RSA, which has known vulnerabilities

What are we coding?

First, here is a basic overview of what we want to do if a user “Bob” wants to send a message to “Alice”.

Step 1) Create a class for our people

In order to demonstrate RSA and represent two parties that want to exchange a message, we will create a “Person” class.

Step 2) Generating public and private keys

A public key consists of two values, commonly labeled as “n” and “e”.

n = p*q where p and q are two different, large prime numbers. I use the function “getPrime()” from PyCrypto to get my values (to use this, run “pip install pycryptodome” in your directory and include “from Crypto.Util.number import getPrime” at the top of your Python file)

e must be some integer that is not a factor of n, and 1 < e < Φ(n), where Φ(n)=(p-1)(q-1). I use e=65537, which is a common value to chose for this. Later on for encryption, we will take a value to the power of our e, and the fact that the binary representation of 65537 (10000000000000001) includes only two “1”s is computationally beneficial. For a more detailed explanation, see here.

A private key consists of the same “n” as well as a value “d”. Now this is where the interesting math begins. “d” is calculated as a modular multiplicative inverse using the extended Euclidean algorithm:

ed = 1 mod Φ(n)

I highly recommend the following video to learn how to solve for the modular multiplicative inverse:

Here is how I translated the process of the extended Euclidean algorithm into Python (more efficient solutions exist, such as this one here, but personally I found it easier to understand the below):

What I am trying to do here is recreate the process done by hand as shown in the YouTube video.

Using my “eqList” variable, I store a list of all the equations we generated in each step of the extended Euclidean algorithm. If you look at the video at time 0:36, he shows the following process that he worked through using the extended Euclidean algorithm:

3000 = 15(197) + 45

197 = 4(45) + 17

45 = 2(17) + 11

17 = 1(11) + 6

11 = 1(6) + 5

6 = 1(5) + 1

What I do in lines 106 to 110 is generate each one of these equations recursively. I represent them with the following class:

So, for example, for the first step in the algorithm he has:

3000 = 15(197) + 45

My variables would be:

thetaN = 3000 (labeled thetaN because initially, this contains our RSA Φ(n) value)

mult = 15 (mult means multiply. This is how much we could multiply e by and still be less than or equal to thetaN)

e = 197 (labeled e because initially, this contains our RSA e value)

r = 45 (r stands for remainder, and is the difference between thetaN and mult*e)

The base case is met when after going through the extended Euclidean algorithm and generating all of these equations into eqList, two numbers with a GCD of 1 are found. If this occurs, I backtrack through all my equations so that I can express 1 as a difference between multiples of “e” and “Φ(n)”. Refer to the tutorial video at 1:49 for this part of the process.

To follow his process we need to programmatically store each part of his backtracking process where he gets these values:

1 = 6-1(5) so we start with 1 represented as multiples of 6 and 5

1 = 6–(11–1(6)) = 2(6)-1(11) from our equation list, we know the value of 5 in terms of 11 and 6, so we replace 5 here.

1 = 2(17–1(11))-1(11) = 2(17)-3(11) from our equation list, we know the value of 6 in terms of 17 and 11, so replace it.

etc…

Notice that we are moving up our equation list developed in the first step of the algorithm, looking at what multiples of two values can represent our value ‘r’, and replacing that in with our backtracking equation. I keep a table like the following in my ‘backtrace’ variable which updates like this:

Step 1:

Step 2:

Step 3:

etc…

Final step:

After using my table technique, we know what multiple values of 197 and 3000 are needed to get a difference of 1. (197 times 533, and 3000 times 35). Notice this is the multiplicative modular inverse because 197*533 = 105001, and 105001 modulo 3000 = 1.

Step 3) Encryption time

It’s time to encrypt!

To encrypt a message, a person needs to use the public key of the person they would like to send a message to. The algorithm for the encryption is:

([plain text message]^[“e” from the public key]) % [“n” from the public key]

Since we will be taking the modulus of a very large number, we can’t use the ordinary power operation followed by a modulo. Instead, so we don’t lose number accuracy, we need to use something called “modular exponentiation”. Here is the function I wrote for this: