## DyingLoveGrape.## Introducting Computer Cryptography, Part1: RSA Encryption Primer.## Introduction.Here's a problem: you want to create a chat program which will allow you to talk to your friend in a In general, it seems reasonable that we should want (at least) two properties for an encryption scheme; this was best summarized by Auguste Kerckhoffs in his six principles (the first two of which are considered the most important): - The system should be unbreakable
*in practice*. - The design of the system should not require secrecy. If the system should be compromised by an enemy, it should not inconvenience the correspondents.
- The key should be memorable without notes and should be easily changeable.
- The cryptograms should be transmittable by telegraph.
- The system should be portable and able to be operated by a single person.
- The system should be
*easy*to use.
For some of these, I've paraphrased. The first and second (sometimes called The first principle here is important because of the vague nature of The second point is perhaps the most mystifying one to those starting out in cryptography: how could the enemy know the keys and, yet, not be able to translate the message? This feels strange to us since The main point of this post will be to show that such a system exists by detailing the For prereqs, you should know the basics of modular arithmetic and the basics of the $\phi$-function, though this last part is not required since we will explicitly compute the values below (so don't worry if you don't know much about it). ## The RSA Algorithm.There's five steps to the RSA algorithm, but most of them are fairly easy. The first one is the most important, and we'll talk about this a bit later. Let's call our message reciever **Player 1 chooses two primes, $p$, $q$.**- Usually, these primes will be 'big primes', but any two primes will work; smaller ones will just be easier for an outsider to crack the system.
**Player 1 finds $n = pq$.**- This will be used as a modulus; we'll see what this means in the following steps.
**Player 1 computes $\phi(n) = (p-1)(q-1)$.**- This value will always be $(p-1)(q-1)$, so ignore the $\phi$ part if you don't like it.
**Player 1 chooses some integer $e$ where $1 \lt e \lt \phi(n)$ and $e$ is relatively prime to $\phi(n)$ (it has no common prime factors).**- This $e$ will be the base for the exponent. There are some ways to maximize security by choosing a small (but not too small) $e$, but we won't worry about this.
**Player 1 finds $d$ such that $d\cdot e \equiv 1 \mod(\phi(n))$.**- This is, perhaps, the hardest step to do by hand. Luckily, computers make this step nearly trivial. We'll explore one method to find this value later.
At this point Player 1 has the values $p, q, n, \phi(n), e$, and $d$. This is quite a lot. We're going to define two things now, using these values:
To sum up everything so far, here's what the players and everyone else knows: \[\begin{array}{|l|c|}\hline \mbox{Player 1} & n,d,e\\ \mbox{Player 2} & n,e\\ \mbox{Everyone} & n,e\\\hline \end{array}\]## Encrypting the Message (if the message is an integer...).At this point, it's easy to finish the algorithm; but, we require the message to be sent to be an
The method of The method of ## A (Very) Easy Example.First, let's do a simple example so that you'll at least believe that such a thing could work. Let's let \[p = 11, q = 17\] so that \[n = pq = 187.\] Hence, \[\phi(n) = (11-1)(17-1) = (10)(16) = 160.\] We now need to pick some $e$ with $1\lt e\lt 160$ which is relatively prime to $\phi(n)$; let's pick $e = 7$. From this, we need to solve for $d$ with \[de = 7d \equiv 1\mod 160\] which, in this case, we can do by hand: it turns out that $d = 23$ gives $ed = 161$ which is equivalent to $1\mod 160$. Neat. So far, we have the following: \[\begin{array}{|c|c|}\hline p & 11\\ q & 17\\ n & 187\\ \phi(n) & 160\\ e & 7\\ d & 23\\ \mbox{Public Key} & [n = 187, e = 7]\\ \mbox{Private Key} & [n = 187, d = 23]\\\hline \end{array}\] Now, let's say Player 2 has the message $M = 19$; we want to choose the message such that the integer value is less than $n$ (we'll show why after this example). Player 2 first encrypts the message:
\[M_{E} = 19^{7}\mod 160 = 59.\]
Player 2 now tells Player 1 (publicly) that $M_{E} = 59$. At this point we stop to ask: could anyone decode this? There seems no "reasonable" way (if this was encoding real words instead of an integer, one could test a lot of primes and see if anything reasonable is spit out). On the other hand, Player 1 has the value $d$ (kept a secret) and ## How does this work?This section will detail a little bit as to why this algorithm works. If you're not comfortable with the idea of relatively prime things, you may want to skip this section. It should be somewhat clear that if someone did not know $d$, it would be difficult to decrypt the message. Note that it is not Let's suppose that we have a message $M$, and $p,q,e,d, \phi(n)$ as above. When we encrypt $M$, this gives us \[M_{E} = M^{e}\mod(pq)\] We have that $0\leq M_{E} \lt n$ in this case. Recall that $e$ is relatively prime to $\phi(n)$; in other words, there exists $a,b$ integers such that \[ae + b(\phi(n)) = 1\] or, in other words, \[ae = 1 - b(p-1)(q-1)\] Note here that \[ae \equiv 1 \mod((p-1)(q-1)) = 1\mod(\phi(n))\] and, hence, we must have that $a = d$, as we've defined $d$ in exactly this way (is $d$ unique? is $d$ unique modulo $\phi(n)$?). Hence, we note that \[\begin{align*} (M_{E})^{d}\mod(n) &= (M^{e})^{d}\mod(n)\\ &= M^{ed}\mod(n)\\ &= M^{1 - b(\phi(n))}\mod(n)\\ &= M\cdot M^{-b(\phi(n))}\mod(n)\\ &= M\cdot(M^{-b(\phi(n))}\mod(n))\mod(n)\\ &= M(1^{-b}\mod(n))\mod(n)\\ &= M\mod(n) \end{align*}\] which is equal to $M$, so long as $M \lt n$ (which we'll talk about in a second. Note that we've used some properties of modular multiplication on the third line here, and we've made use of Euler's Theorem in the next-to-last line. Hence, decrypting in this way will give us back $M$. Note that we've needed to do two things for this to work: first, we required $M$ to be an integer; second, we required $M \lt n$. We'll talk about the first assumption in the next part. For the second assumption, it generally is not a huge problem to make $M\lt n$ since the primes $p,q$ that we work with are quite large. So long as we do not encode our message in a silly way that purposely makes it a large number, things will be fine. This will segue us into the next topic... ## Messages with Letters.There are a number of ways to take a message and create an integer which represents this string. We'll talk about a popular (though, perhaps not totally efficient) scheme here; note, though, that there are other ways to do this! The idea behind the method we'll talk about is as follows. A message is input, the message is broken up into same-size pieces (called For example, we can make up a silly example like this: - Break text into blocks containing 4 letters.
- Starting with $a = 10, b = 11, \dots$, change the letters to numbers and simply concatinate the numbers together. We can let spaces be equal to the number $99$, and if we need to pad anything at the end to complete a block (so that we don't have blocks that aren't less than four letters) we will let this be equal to $88$ (see below).
- Send the blocks through RSA in order.
This method would work (ignoring that we have not encoded numbers, non-alphabetic symbols, etc.). For example, the message
\[\mbox{hi mom im home}\]
would be broken up into:
\[\begin{array}{l}
\mbox{hi m}\\
\mbox{om i}\\
\mbox{m ho}\\
\mbox{me}
\end{array}\]
We can then translate the first three lines into numbers, but the last line doesn't have four letters so we need to Note again that this is just As practice, you may want to create your own method, then attempt to encrypt and decrypt your message. Note that in many programming languages, modular exponentation is built in and is |