RSA in plain English

I'm a computer science student, I'm not a mathematician, I don't know anything about number or group theory.

I'm looking at RSA, and I want to understand it. I know what Fermats's little theorem and Euler's totient function are, and this is what I've got:

• $p, q$ primes, $n=pq$.
• $d$ relatively prime to of $\varphi(n)=(p-1)(q-1)$.
• $e$ so that $ed \pmod{\varphi(n)}= 1$.
• Hence $x^{ed} \pmod{n} = x$.

For encryption I have to use $c=w^e \pmod n$, and for decryption $w=c^d \pmod n$. But I don't understand what has happened beyond, and how those formulas are linked.

Solution 1:

Since you ask for "plain English", let me discuss a bit of what the issue is and how RSA hopes to address it.

As I mentioned in an earlier answer the underlying problem is this: you want to communicate securely with someone. There are two standard techniques: one is steganography, which consists of trying to hide the very existence of the communication; that's not usually very mathematical, and it is difficult to do. The other is cryptography, which consists of obscuring the message so that even if the message is overheard, the people overhearing it will not understand it. A method for doing this is called a "cryptosystem."

Cryptosystems usually rely on a key, a way for the speaker to encrypt his message, and a way for the listener to decrypt it (figure out what the message says). Historically, most cryptosystems used what are called "symmetric keys": the piece of information that was needed to encrypt was the same as the piece of information that was needed to decrypt (or at least, knowing one was "equivalent" to knowing the other). Both sides needed to know the key. This leads to a difficulty: how do we agree on a key? If we cannot communicate without being overheard, then we cannot agree on a key without everyone finding out what the key is, which makes the system useless. And if we can communicate without being overheard, then there's no point in the whole song and dance, we can just talk using that communication.

There were a number of ways of solving this issues: traditionally, you had a secure way of communication with limited bandwidth (only small amounts of information could be exchanged through it, and only at certain times), so that they key could be exchanged but communication was too difficult (diplomatic bags, spies, etc).

But there is another type of cryptosystems that were discovered in the 70s (it's known that the UK's GCHQ knew about them before, and there are always rumors that the NSA knew about them before they were "publically discovered" as well), which are not symmetric, in the following sense: knowing the encryption key does not give you enough information to find the decryption key. They are called "public key cryptosystems", because you can tell the entire world how to encrypt messages for you, but knowing this information does not give them a way to decrypt messages sent to you. That requires the "decryption key", which you only know.

[Sorry, we'll have to throw some math in now, but you had to expect it.] These systems rely on what are called trapdoor functions. The idea of a trapdoor function is that you have a function $f$ that encrypts, but for which it is difficult to find the inverse, $f^{-1}$ (which decrypts); so that even if you know exactly what $f$ is, and you know that the output of $f$ was, say, $D$, it is still very hard to find $f^{-1}(D)$ (which would be the message being sent). However, if you happen to know an extra piece of information, $k$, then from $f$, $D$, and $k$ you can easily find $f^{-1}(D)$ (think of $k$ as the lever that "opens the trapdoor" and lets the inverse fall through). So the idea of these public key systems is to tell everyone what $f$ is, but keep $k$ secret. Nobody needs to know $k$ in order to compute $f(M)$, which they can do in secret. Then they can yell $f(M)$ at you; it doesn't matter if people overhear $f(M)$, because it's very hard to find $M=f^{-1}(f(M))$ (very hard to decrypt). But since you know the secret piece of information $k$, when you hear $f(M)$, you can use $k$ to find $M$, and voilá!, you know the secret message but nobody else does.

RSA is one of these systems. In RSA, the messages are numbers (it is straightforward to convert text into a number). I want to communicate a number to you secretly, even though everyone can hear me talking.

The way RSA work is by using modular exponentiation. You select a big number $n$, and two numbers, $e$ and $d$, such that $ed\equiv 1\pmod{\varphi(n)}$ (Euler's $\varphi$ function). You tell everyone what $n$ is, and you tell everyone what $e$ is; these are the public keys, but you keep $d$ secret. If I want to send you a message $M$, I first make sure that $\gcd(M,n) = 1$ and $1\lt M\lt n$ (if not, I modify the message a bit so that it is, or I break it up into pieces if it is too big). Then I compute $R=M^e \bmod n$, which is easy to do with computers, and I tell everyone that I'm sending you the message $R$. When you receive $R$, you can figure out what the original message $M$ was, simply by computing $R^d \bmod n$ (which again is easy to do computationally). The reason this will tell you what $M$ was is due to Euler's Theorem.

Euler's Theorem. If $n$ is a positive integer, and $\gcd(a,n)=1$, then $a^{\varphi(n)} \equiv 1 \pmod{n}$.

This is a generalization of Fermat's Little Theorem (in Fermat's Little Theorem, you have $n=p$ a prime, so $\varphi(n)=\varphi(p)=n-1$, and the equation tells you that $a^{p-1}\equiv 1\pmod{p}$ if $\gcd(a,p)=1$).

Since $ed\equiv 1 \pmod{\varphi(n)}$, we can write $ed = k\varphi(n)+1$ for some integer $k$. Then we have: $$ R^d \equiv (M^e)^d \equiv M^{ed} \equiv M^{k\varphi(n)+1} = (M^{\varphi(n)})^kM \equiv 1^kM = M \pmod{n}$$ (by using the rules of exponentiation, and because $M^{\varphi(n)}\equiv 1\pmod{n}$).

Now, this means that you can figure out $M$, because you know $d$. Can other people figure out $M$ without knowing $d$?

If you can figure out $\varphi(n)$, then it turns out to be very easy to figure out $d$ from knowing $e$: because you know that $\gcd(e,\varphi(n))=1$, then using the Euclidean Algorithm you can find integers $x$ and $y$ such that $ex+\varphi(n)y = 1$; and then $d\equiv x\pmod{\varphi(n)}$, and all of this can be done easily. So you want to make sure that computing $\varphi(n)$ is not easy, even if you know $n$.

If you can factor $n$ into primes, though, then $\varphi(n)$ is very easy to find. So you want $n$ to not be a prime, but to have very few prime factors (because every time you find a prime factor, you divide it out, and you have a smaller problem left). So ideally, we want $n$ to just be a product of two really big primes, $n=pq$.

So, the way this works is: you first find two really big primes secretly (there are ways of doing this), $p$ and $q$. Then you compute $n=pq$. Since you know $p$ and $q$, you also know that $\varphi(n) = (p-1)(q-1)$, so $\varphi(n)$ is easy for you. Then you pick an $e$, and since you know $\varphi(n)$, you can find $d$ easily (there are "bad choices" of $e$ that will make finding $d$ not too hard, but they are known; you avoid them; there are also bad choices of $p$ and $q$, so you avoid them too, don't worry too much about this).

So, now you know $p$, $q$, $d$ and $e$. You tell everyone $pq$ and $e$, but you keep $d$, $p$, and $q$ secret.

If I want to send you message $M$, $1\lt M \lt pq$, I don't tell anyone what $M$ is, I compute $M^e\bmod n$, and I tell everyone $M^e$. You can figure out $M$ because you know $d$, so as above, $(M^e)^d = M^{ed} \equiv M\pmod{n}$ by Euler's Theorem.

The hope is that just from knowing $n$, $d$, and $M^d \bmod{n}$, it is hard to figure out $M$.

The RSA Problem is precisely that problem: if you know $n$ (and you know that $n$ is the product of two primes, but you don't know which primes ahead of time), you know $d$, and you know $M^d\bmod{n}$, can you figure out $M$? The security of the RSA cryptosystem depends on how hard the RSA Problem is to solve.

If I can factor $n$, then I can solve the RSA Problem: I can find $\varphi(n)$, then I can use $\varphi(n)$ and $d$ to find $e$, and once I have $e$ and $M^d$, I just figure out $(M^d)^e \equiv M \pmod{n}$. So the RSA Problem is no harder than the problem of factoring a product of two primes. Luckily, in so far as we know the problem of factoring a product of two large primes is pretty hard.

It is not known, however, if there might be a different way of solving the RSA problem that may not rely on factoring $n$. Maybe, maybe not.

I hope this helps.

Solution 2:

You are almost there. The only math that you and Yuval didn't mention is that because $ed = 1 \pmod{\varphi(n)}$, $(w^e)^d \pmod n=w^{ed} \pmod n = w$ so the encryption/decryption works and this is from Fermat's little theorem.

Solution 3:

The RSA cryptosystem is composed of three steps:

• Key generation: Each user $u$ generates two primes $p,q$, calculates $n = pq$ and $\varphi(n) = (p-1)(q-1)$, picks a random $e$ (which must be relatively prime to $\varphi(n)$) and calculates $d = e^{-1} \pmod{\varphi(n)}$. The user publishes the public key $pub_u = (n,e)$ and keeps for herself the private key $pri_u = d$.
• Encryption: If you want send $u$ a (short) message $m$ so that only she can understand it, you send $c=m^e \pmod{n}$; you can do that since $(n,e)$ are public.
• Decryption: Upon receipt of $c$, user $u$ can restore the original message $m$ by calculating $m=c^d \pmod{n}$ (this only works if $m < n$).

People hope that it's very difficult to break the cryptosystem, that is to decrypt messages unless you're $u$. However, that depends on how you use the system - you can use it wrongly. For example, if $m$ is small and an attacker knows that, he can recover $m$; other attacks are more sophisticated.