# An Introduction to Public Key Cryptosystems with RSA

In the past few years alone, the world has seen many massive data breaches. Most recently, Marriott Hotels . It is named after Leonhard Euler (1707). Note that if n is prime, then ϕ(n) = (n-1) as all numbers less than n are relatively prime to n.

(4) The final key concept comes from Euler as well. Euler’s Theorem (also known as the Fermat-Euler Theorem) underlies the success of the RSA algorithm. The theorem is stated below. The proof contains a little too much number theory for this article. But for those interested in the proof, see here.

### The RSA Algorithm

Alright! Now we have all the tools we need to discuss the RSA algorithm. Let’s say Alice wants to send a message to Bob. We’ll call this message m.

We can translate m to a number using ASCII values. For example, the message “Hello” in hexadecimal ASCII is “48 65 6C 6C 6F “. We can then convert from hexadecimal (0x48656C6C6F) to base 10 (310939249775). Now our message m is 310939249775. Once we have a valid message, Bob has to do a little work before Alice can send Bob a message. The RSA algorithm is outlined below.

How do we know that last step will return the original message? We rely on Euler’s Theorem as shown below. For our purposes, we can assume gcd(m, n) = 1 as the only factors of n are p and q. The odds m = p or m = q are very small.

### An Implementation of RSA Using Python

The following code uses RSA to allow for the encryption and decryption of a given message m (so long as m, when converted to an integer, is less than n). This code is certainly not robust and is meant only as an example. It should not be used as a means of secure communication. For those looking to edit the codebase, the GitHub repository is here.

We’ll first need two methods — one to convert words to integers and one to convert integers to words i.e. “ Hello” ⇆ 310939249775. These two functions are below.

The next step is to handle the setup. We’ll need to define n and ϕ(n). This function takes a parameter num_digits, which represents the number of digits in our primes p and q. The code below uses 50 digit primes. This implies n is approximately 100 digits long. Real RSA encryption uses an n with ~600 digits.

Bob is almost there! All he needs to do is define e and d, which is done in the below methods. The generation of d requires modular inverses. Rosetta Code has a great implementation that we use. We use an e with 25 digits, which should be sufficient for our purposes.

And we’re all set. We can now encrypt and decrypt a message m using the two methods below.

We implement a main() method below to drive our code and we’re all set.

And we see it works! 