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!
This article was only meant as an introduction to public key cryptosystems and RSA. But there is certainly much more to cover! There are restrictions and standard protocols for choosing the values of p, q, e, d, and m. There are efficient ways of performing the above calculations. For those interested in learning and exploring more, I recommend Introduction To Cryptography (2nd Edition).
While building RSA is certainly interesting, breaking RSA is even more interesting. The strength of RSA lies in our inability to factor numbers that are a product of two large, distinct primes. The two methods that attempt to do this are the Quadratic Sieve and the General Number Field Sieve. These are fascinating methods and we’ll hopefully have an article on them soon.
An Introduction to Public Key Cryptosystems with RSA was originally published in Hacker Noon on Medium, where people are continuing the conversation by highlighting and responding to this story.