The RSA Cryptosystem

• Premise
• What is RSA?
• The inner workings of RSA
  • Key generation
  • Encryption
  • Decryption
  • Proof
• Computational complexity
• Afterword

Premise

Trustworthy communication between untrustworthy channels will always be a necessity due to the nature of confidentiality. When we transmit our credit card information for a transaction on eBay, we expect that information cannot be revealed to prying eyes other than eBay. The internet, being a best-effort model, does not provide any security guarantees about the data we send. Should we transmit our credit card data unencrypted, it is possible for bad actors to intercept our messages and directly steal our credit card information as it will be stored in plaintext. As developers, it is up to us to implement protocols (TLS, SSL, etc) such that our information remains secure when we transmit it over an untrustworthy channel. A keystone in these protocol implementations is an algorithm known as RSA.

What is RSA?

RSA (short for Ron Rivest, Adi Shamir, Leonard Adleman) is a number theoretic algorithm that plays an integral role in data encryption over the internet.

When we send a packet over the internet, we expect that whether or not the packet is intercepted, the data is not readable any time between leaving the source and arriving at the destination. This implies that there must exist some way such that only the receiver can decode the encrypted data sent over the packet. One such way to accomplish this is with asymmetry in encryption. That is, two keys are actually utilized in the cryptosystem: one to encrypt and another to decrypt. A message is encrypted before sent over the internet, making it unreadable during its journey to the receiver. When the receiver gets the message, the receiver can use the decryption key to recover the original message.

In RSA, the encryption key is known as a public key and the decryption key is known as the private key. The public key can be known to anyone, and anyone can use it to encrypt the data which is sent back to the receiver. The receiver is the only one that holds the private key, and hence is the only one who can decrypt the encrypted data (note that it is the obligation of the receiver to make sure this private key is never shared!). Thus, even if someone knows the public key, they can only use that information to encrypt data. A public key cannot be used to decipher a message that is intended for the receiver.

Still confused? For reference, there will be two examples below. The first will be a symmetric key encryption scheme for binary messages using the XOR function. The second will be an asymmetric key encryption scheme using RSA.

# Our basic key
xor_key = 0b10101010
 
# Our message, possibly a string, encoded as binary
message = 0b00110011
 
# bitwise XOR the key and the message to encrypt
message_encrypted = XOR_ENCRYPT(message, xor_key)
message_encrypted = 0b10011001
 
# bitwise XOR the key and the message to decrypt
# The key is symmetric, so anyone encrypting with 
# the key will also know how to decrypt it
message_decrypted = XOR_DECRYPT(message, xor_key)
message_decrypted = 0b00110011
message_decrypted = message

Above is a symmetric key cryptosystem using XOR. See how we use the same key (xor_key) to encrypt and decrypt? RSA does NOT do that.

To reiterate, RSA utilizes two keys, a public and private key. The public key, as the name suggests, is public and can be known by anyone. The private key should only be known to those who need to decrypt the message. These keys are linked in such a way that the public key can be used to encrypt a message and the private key can be used to decrypt the encrypted message.

# Public and private key created by an 
# asymmetric key generation algorithm
public_key, private_key = RSA_KEYGEN()
 
# Our message, again possibly a string, encoded as binary
message = 0b00110011
 
# Encrypt using the public key
# This key is public so it can be shared to anyone who wants 
# to send a cryptographically secure message to the receiver
message_encrypted = RSA_ENCRYPT(message, public_key)
 
# Decrypt using the private key
# Only the receiver has this key, so only they can decrypt the 
# encrypted message!
message_decrypted = RSA_DECRYPT(message_encrypted, private_key)
message_decrypted = message

Notice how the RSA pseudocode uses two keys (public_key and private_key) instead of a single key, unlike XOR encryption. If someone wants to send a message to me, then I can send them my public key and they can encrypt their message using it. They can send their encrypted message back to me over an untrustworthy communication channel, but even if a malicious h4x0rz intercepted my message, they would not be able to read it as it would be encrypted. When I receive the encrypted message on my end, I can simply use my private key to decrypt it. This public key encryption with private key decryption scheme works because the private key never leaves my computer. No one can know of my private key so no one else can possibly read my data as long as it is encrypted by my public key (in theory, at least—we will discuss this later).

The inner workings of RSA

Ok, now that we get the gist of RSA and how it can be used, let's discuss the hard part: the math. The RSA algorithm is a mathematical piece of art. It works because of some devious modular arithmetic properties. Unfortunately, this means that the design isn't all too intuitive to those who don't fully understand modular arithmetic. That being said, the algorithm is not a black box. We can break up the algorithm into three key components—key generation, encryption, and decryption—to get a better understanding of it. Below will be three sections describing each part of RSA.

Key generation

In order to use RSA, we need a public key and a private key. How do we get these keys? Well, let's begin by randomly selecting two large prime numbers $p$ and $q$. The two values $p$ and $q$ must be so large that modern prime checking algorithms must have difficulty determining if they are prime or not. From $p$ and $q$, we calculate their product, $n$ and the totient of $n$, known as $\phi(n)$.

After this calculation, an integer $e$ such that $e$ is co-prime to $\phi(n)$ must be selected (this number need not be selected randomly—a common value used is the number $2^{16} + 1 = 65537$). From here, the public key $P$ is comprised of the pair of integers $(e, n)$.

Given $e$, we must also calculate $d$, the multiplicative inverse of $e \pmod{\phi(n)}$. The private key $S$ is comprised of the pair of values $(d, n)$.

In the end, we have the following keys $P$ and $S$ representing the public and private keys respectively.

As of now, it's not clear why we generate our keys in this way. We will cover this later in the proof. Just make sure to understand how we are creating these keys at face value.

Encryption

Most data sent over the internet is in the form of human language which can be interpreted as strings. Because RSA works with integer values, to encrypt our data, we must first translate the data to its numerical form. For example, if the data we want to transmit is a string containing a password, then we can convert it into its integer representation by turning it into a byte array. If the data we are transmitting is a complex object with a defined structure, we may serialize it to a string and then do the same. Whatever the data is, as long as there exists a way to transform the information to numbers and a way to transform the information back, we can use it over RSA.

We call this numerical representation of the data the message $M$. If we have a public key $P = (e, n)$ and a message $M$, we can encrypt it like so.

We call the result of the public key encryption on $M$ the ciphertext, also known as $C$ or $P(M)$.

Decryption

To decrypt a ciphertext $C$, we require the private key $S = (d, n)$. We can then perform a similar operation as encryption using $d$.

This should yield the original message $S(C) = M$. The numeric version message $M$ can be then transformed back into whatever data type it was prior to encryption.

Proof

Why does RSA work? A keen observer may notice that the public key and private key encryptions are inverses of each other as they both produce $M$. From here, it follows that want to know if the following statement is true.

Let's start with the values of $S(P(M))$ and $P(S(M))$.

By the properties of modular arimethic, these two quantities are equivalent. Now, if we can show that $M = M^{ed} \pmod{n}$, then the encrypt and decrypt functions are inverses. With this in mind, let us try to prove

Now is where the mystery totient function mentioned before comes into play. Remember how we selected $d$ such that it is a multiplicative inverse to $e \pmod{\phi(n)}$?

We can use the fact that $e$ and $d$ are multiplicative inverses to exponentiate $M^{ed}$.

It turns out that the totient function gives the quantity of $M^{ed} \pmod{n}$ a special property. Let's see what happens when we try to simplify $M^{ed} \pmod{p}$ and $M^{ed} \pmod{q}$.

We are able to factor out an $M$, but after distributing the exponents, we are a bit stuck. To progress, we need the help of Fermat's little theorem.

Theorem (Fermat's Little Theorem) If we have a prime number $p$ and any integer $n$

If $n$ is not divisible by $p$, then

This theorem is important because we can directly use it to clean up our equation. We just need to manipulate our equation a little to utilize Fermat's little theorem.

Substituting Fermat's little theorem allows us to remove the entire second term.

Thus, $M^{ed} \equiv M \pmod{p}$ in which the same can be done to show that $M^{ed} \equiv M \pmod{q}$. Do you see the special mathematical property that the totient creates? It causes $M^{ed}$ to be in the same equivalence class as $M$ whenever the modulus is a factor of $n$. Since we know that $M^{ed} \equiv M$ for both moduli $p$ and $q$, we can conclude

This does not complete our proof, however. Take a look at the equivalence. We have only shown $M \equiv M^{ed} \pmod{n}$, not $M = M^{ed} \pmod{n}$. This can be easily remedied with the assumption $n > M$ (this is why we choose such large primes for $p$ and $q$!). As long as $M$ is smaller than $n$, $M$ will not be divided into a remainder, so we retain the original message. Thus, we have completed our proof. As a recap

Given $n > M$,

which allows us to conclude

Complexity of breaking RSA

Let's say we are given an encrypted message. Can we determine the contents? Assuming we are handling the keys correctly, the only information an attacker has access to is the public key $P = (e, n)$. To get the private key which can decode the message, we must recreate the value $d$. This implies we must factor $n$ into $p$ and $q$ in order to decode the message. Since integer factorization is a problem that exists between NP and coNP, finding the giant primes that were used to create $n$ is a nontrivial task, even with sufficient compute! Furthermore, if we somehow reach a point where we can factor 1024 to 4096 bit keys, we can always increase the length to make the problem exponentially harder!

You may have noticed by now: RSA works because it is a trapdoor function. It is easy to compute in one direction but extremely difficult to do in reverse. As we do not have the computational power right now to decode an RSA encrypted message in feasible time, we claim that RSA is cryptographically secure.

Afterword

Congrats! You've finished reading my notes about the RSA cryptosystem! RSA is an algorithm that I've learned and unlearned many times since high school. After understanding it better in my discrete math and algorithms courses, I wanted to write about it to solidify the topic in my head. All credit for the math goes to CLRS which is my favorite algorithms book of all time (fun fact: the R in CLRS is the same R as RSA!). I hope my writing wasn't too mediocre and thanks for reading!