Encryption - Part 2 RSA Cryptosystem

This is part 2 of the encryption series. Part 1 can be found here.

The RSA cryptosystem is a encryption scheme that is widely used and has been the de-facto encryption scheme for quite a while. Like we discussed in the previous post, the security level of RSA is less than that of the OTP, but the upside is that messages can be sent on demand, with no preshared secret keys. The security level is called computational because the claim is that RSA is secure if the adversary does not have “too much” computational power, and is resonable (We will discuss what these abstract words mean). The OTP, on the other hand, is unconditional and information-theoretic.

Unerlying the entire system is a difficult problem called prime factorization. Yes, the straightforward idea of splitting a number into a product of primes is what most of the security of the world relies on. Let’s first look at a little bit of math and come back to how factorization is right at the heart of the problem.

RSA comes under the umbrella of asymmetric/public-key encryption schemes – there are two different keys involved in encryption and decryption called the public key $\operatorname{PK}$ and private key $\operatorname{SK}$. Every person who wants to use the scheme has their own key pair. The private key is known only by the owner of thr key and the public key is publicly known. Say Alice wants to send a message $M$ to Bob. To do so, she uses Bob’s public key $\operatorname{PK}_B$ to encode her message. Then, this encoded message is sent to Bob through an insecure channel. Bob takes this encoded message and uses his private key $\operatorname{SK}_B$ to decode it. Mathematically, for the example above,

So far so good, this seems to make sense. But what are the underlying assumptions that we haven’t spoken about? What about the adversary? Consider a really bad example where the encoding and decoding does nothing, i.e.,

Technically, these two functions satisfy the goal above, but I’m sure it’s clear why this is really bad. It’s because this “encoded” message when sent through the insecure channel, is immediately seen by any adversary Eve, who now has the message. So we need to impose some conditions on the encoding and decoding functions. What are some realistic conditions we can impose? One could be that the system works if everyone behaves properly, i.e., if Alice encodes with Bob’s public key, Bob should always be able to decode correctly with his secret key. This is written mathematically as

\(\forall M, \operatorname{Decode}(\operatorname{Encode}(M, \operatorname{PK}_B), \operatorname{SK}_B) = M,\) where the first symbol $\forall$ means for all. This equation says for all possible messages, encoding and decoding with someone’s key pair always returns the correct message. This is a very reasonable and sort of basic assumption we need. What else? If you are worried about an adversary (which we always are), we would like the adversary to have a hard time figuring out the message without Bob’s secret key! In other words, even with the public key and the encoded message, Eve cannot figure out what the actual message $M$ was easily.

The above equation is read as “Probability that Eve guesses M when given Bob’s public key and the encoded message is approximately the same as randomly trying to guess the message $M$ from the set of all possible messages. An important note is that this also enforces that the private key cannot be derived from the public key easily, because if it was derivable, Eve could take Bob’s public key and derive his secret key, and use it to decode. Congrats! We’ve created the template for a public-key encryption scheme!

Now, we need to actually look at an example of a public-key encryption scheme. Enter stage right RSA! Let’s first look at the entire algorithm and then break it down. The setup steps are as follows:

1. Pick two large prime numbers $p$ and $q$ and define $n = p*q$.
2. Calculate $\phi = (p-1)(q-1)$ and pick a number $e$ which is co-prime with $\phi$.
3. Calculate $d$ such that $de = 1 (\operatorname{mod} \phi)$. $d$ is called the modular inverse of $e$.
4. The public key is then $(n, e)$ and the private key is $(n, d)$.

Suppose Bob does the above steps and publishes his public key $(n, e)$. Now, Alice want to send a message to Bob.

1. Convert message to a number $M$, usually using some decimal encoding or ASCII encoding.
2. Encode $M$ into $M_e = m^e (\operatorname{mod} n)$.
3. Send $M_e$ to the recepient using the insecure channel.
4. The recepient decodes the message $(M_e)^d = m (\operatorname{mod} n)$.

Okay. This was a lot of information and it came flying at your out of nowhere. Let’s actually look at a full example from the setup to each transmission. Pick

Let’s use the same message as before $1857$. Since the message is larger than $n$, we need to split it into two pieces. In this example, we’ll encode $m = 18$, and the procedure remains the same for $57$. So for $m=18$, the sender uses the recepient’s public key $e=7$ to compute the encoded message $M_e = (18^7) \operatorname{mod} 221 = 86$. Now, the recepient takes this encoded message and using their secret key $d = 55$, computes $(86^{55}) \operatorname{mod} 221 = 18$! The recepient has recovered the original message!

The example above isn’t really a proof that the RSA system works. The proof is mathematically involved, so we’re going to sidestep it altogether. But the real fun is to try playing the adversary and seeing if we can break the system. So what does an adversary see? The public key $(221, 7)$ and the encoded message $86$. The adversary also knows the exact encoding method! This is an important principle in cryptography. We always assume adversaries know the encode and decode functions we use. The secrecy should come from the key values only. Let’s see if we can figure out what the secret key $d$ is.

Since we know that $n = 221$, a simple thing we can do is to prime factorize it. Searching for factors, we find that $221 = 13 * 17$. So, we pick $p=13$ and $q=17$, and using this compute $phi$ and $d$, which is the secret key! Now with $d$, we can decode the message and find out all the secrets ourselves! So what’s the point of all of this? All we had to do was prime factorization, which is something kids are taught in elementary school?

Actually, yes :D The key to it all is that prime factorization is actually very hard. For $221$, we could easily break it down into $13$ and $17$ in a fraction of a second on your laptop. But what about $14613728558971$ The security of RSA comes from the fact that multiplying $3326489$ and $4393139$ to get $14613728558971$ takes almost no time, whereas splitting it takes a much much longer time. For example, if we pick $p$ and $q$ to be 250 bit numbers, the best algorithm we have is estimated to take 2,700 years! And it turns out without the factorization of $n$, breaking RSA is impossible.

Okay, let’s go back to the beginning. We were looking for an encryption scheme that doesn’t need a long key, or preshared secret keys. We began by claiming that “RSA is secure if the adversary does not have too much computational power”. Now we know exactly what that means! As long as the adversary cannot compute the prime factorization of a large number (something we strongly believe to be very hard), then our secret is secure.