- Reed Nelson
- 10 Jun, 2022
Encryption is all about encoding information with the end of limiting (meaningful) access to it. Usually when we’re talking about encryption/decryption, it’s in the context of an outgoing/incoming message. You use encryption dozens or hundreds of times a day without ever having to think about it. Every credit card swipe, every iMessage, every HTTPS visit, and every packet sent to your wireless headphones is encrypted. Anyone intercepting your data while it’s in motion is only reading garbage (so long as they can’t decrypt it).
RSA is an encryption algorithm developed at MIT in the 70’s1 by researchers Rivest, Shamir, and Adleman (hence, RSA). It’s simple enough to understand, but it’s very secure. Despite its age, RSA remains one of the most widely used public-key encryption schemes. “Public-key” isn’t some throwaway phrase, it’s integral to the description of RSA, and it describes a very significant class of ciphersystems in Cryptography. To build context for this concept and for RSA, we’ll first look at a more traditional class of systems.
A Bit About Modular Arithmetic
The modulus operator returns the remainder of an integer division. For example, . Equivalently, we say , “five is congruent to two, mod three”. denotes the set of integers, and denotes the set of integers modulo , i.e. .
Traditional Cipher Systems
A cipher system is defined with the following components:
a set of plaintexts a set of ciphertexts a set of keys an encryption function a decryption function
The role of all these pieces will be apparent with a simple example:
The Shift Cipher
What this means is we’re working with a character alphabet (i.e. ), where each character is mapped to a number (i.e. ). Then if we choose the key to be , we have . So all we’ve done is shifted (rotated) each character in our message by characters. can be any integer from through (). When specifically, this is called the Caesar cipher.
RSA is a public key ciphersystem, which means that everyone can know how to encrypt a message, but the encryption key is not sufficient to decrypt the message. So the encryption function is still invertible (otherwise there would be no way to decrypt), but it is hard to find the inverse of the encryption function. A function like this is called a one-way function2, or a trapdoor function. By “hard” to decrypt, we mean something like “a modern computer could run until the universe burns out and still have almost no chance of decrypting”.
RSA leverages this fact to create its one-way functions: it is relatively easy to compute very large prime numbers, but very difficult to find the prime factors of large numbers.
Let and be two large primes, and . Then take and in , such that . That is, and are inverses in . At this point we can throw out everything but , , and . we no longer need them and their discovery would break the security of our scheme. Now we can share publicly, and must keep secret. The encryption for a message is , and the decryption is . It’s as simple as that.
It’s not obvious at all that when , but this fact is essential for RSA to work as it does. I’ll prove this statement below in case you’re interested.
I’ve already mentioned that RSA is widely used today, but in particular many RSA systems use a bit (~ digit) ”” value, and an ”” value of precisely . If you like your powers of two, you may recognize this as 3. For a sense of scale, the number of atoms in the universe has about digits. The numbers we’re working with here are truly massive, so this may raise a couple concerns for you.
First, isn’t it difficult to find prime numbers that large to use for and ?
Prime numbers aren’t as scarce for in our ballpark as you may think. By the Prime Number Theorem, there are approximately primes in the first natural numbers. So in pratice, it’s reasonable to iteratively take numbers in some ballpark and do a primality test. Naively, all you’d have to do is check if any prime between and divides . So clearly this can be done much faster than finding the prime factors in general (which we said earlier was hard).
Second, isn’t it difficult to reduce such huge exponents to encrypt and decrypt messages?
Not really! Since we’re doing modular exponentiation, we can be super efficient. Let’s do an example. Say we want to encrypt the letter “X” ( letter) with the key in . We want to know . Computing directly gives . But that took a ton of sub-operations, and we have to do a ton more to find this value mod . By leveraging the fact we’re working in , we can reduce this to order operations. . . . Now we have . Almost there! , and of course to any power is . So . TLDR: by finding modular equivalences in intermediate steps, we’re able to keep the size of our multiplications in a reasonable range.
So that is RSA, and why it works. This is truly an awesome system. There’s some interesting history here with RSA and the Diffie-Hellman Key Exchange and their treatment by certain global superpowers, but I will save the culture for another post.
Fermat’s Little Theorem4: if is prime, then . By construction, , so is a multiple of . That is, . Then . By Fermat’s Little Theorem, , so . By symmetry, . So we have .
An equivalent system was developed secretly and used by the British government years before Rivest, Shamir, and Adleman devised RSA! ↩
The existence of one-way functions is actually only a conjecture! To prove OWFs exist is to prove . That is to say, RSA’s security depends on a very big (but probably safe) assumption. ↩
The second coolest theorem with a name of the form “Fermat’s L___ Theorem”. ↩