This post is a work in progress: I am rewriting this entire post, this page is essentially the last page in the series of post. For each part the RSA Algorithm I will write a post that corresponds to it. Essentially this post will consist of a bunch of little post, but collectively they are all as one post.

Me and my friend started talking about primes and how they can be used. One of my favorite areas is cryptography, I love old cipher techniques. So I started checking my library of books for such techniques. One of the more popular ones that came to mind was the RSA algorithm. I had to flip through a couple of books to see which one had an easier definition I could explain. I have a few books on number theory,but the one I like to use more predominantly is "A friendly Introduction To Number Theory" by Joseph H. Silverman. I like this book more because it has questions that deal with more "number crunching" than "proof writing".

That being said and done, there are some definitions we need to go over if we are to understand the basic concept. You might be thinking "ewww" because I mentioned definitions. But for our purpose "ewww" is a necessary evil if we wish to be better master spies...I mean mathematicians. Should you wish to catch a straight flight to the example of **RSA**, skip to the **very end**, otherwise our path looks like this:

Divisibility, greatest common divisor, relative prime, congruence, modular, Euler's Phi function, The Kth Roots Modulo m Algorithm, successive squaring, and finally the actual RSA algorithm.

Reading these definitions will be frustrating for most advanced readers in the subject area, I assumed nothing when explaining these definitions. So naturally, if your reading my definitions, you will find that their are extremely 'step by step'. If you know nothing of math, but have the fortitude to endure against great detail, then you should be fine....relatively. There is a slight chance you will hate math even more.

So we have traveled far and wide to reach our goal of what is RSA. RSA is a public key crypto-system named after its inventors, Ron **R**ivest, Adi **S**hamir, and Leonard **A**dleman. The power of this public key crypto-system lays in the fact that the decoding method remains a secrete while the key is publicly known. It sounds a little weird, who leaves their keys in public? But this cipher method is huge compared to its predecessors, a lot more complex than just changing letters into numbers. Do note, a cipher is different from a code. This is true when you are talking about it in cryptography, there are cases where cipher and code can mean the same thing. But back to our work, I will list out the steps as we move along:

- [
**Step 1**] Now we can began our cipher building, first we need to make our English alphabet into a string of numbers.

, , , , , , , , , , , , , , , , , , , , , , , , ,

- For the example let use "RSA CIPHER ALGORITHM" , then it would become:

- [
**Step 2**] Each number has a number that represents it below, so our cipher looks like this: (note we don't represent spaces when we translate the message into strings of numbers).

- Our message became the string of digits "2829111319261815281122172528193023", so far our word is encoded but with little protection. Our next step is choose two large prime numbers, as big as the computer lets you store in its memory.

- [
**Step 3**] For the sake of demonstration and because I don't want to crash my computer, we will choose small primes. - Let

and

- [
**Step 4**] Next we multiply these two together to get our*modulus*'m', m = (p)(q):

- [
**Step 5**] Now we need to calculate phi of m:

- [
**Step 6**] Now lets choose some random k value that is relative prime to our phi(m). I literally picked the random numbers until I found one that gave me a gcd(k,phi(m)) = 1:

, so

- [
**Step 7**] Lets look at all our information:

,

- [
**Step 8**] The length of our encoded word is 34 digits long (2829111319261815281122172528193023) and 'm' is 6 digits long (407839). We can break up the message into 5 digit numbers. You should break up your string of numbers into a length less than or equal to the length of your 'm'. - It is ok to have one stack of numbers only 4 digits long. This is normal when attempting something like this. I took the first 5 numbers, then the next 5 numbers and so on. We should have six 5 digit long numbers and one 4 digit long number.

28291, 11319, 26181, 52811, 22172, 52819, 3023

- [
**Step 9**] Next we take each 5 digit number and raise to our kth power modulo m, but first we have to do some grease monkey work. We essentially have to solve:

- So I took my first string of 5 digit numbers and raised it to the 'k' power, then I need to calculate the results modular m.
- Well shiitake mushrooms, I don't have a calculator that can handle this kind of crunching. We would have to use a computer for something like this, although it is possible to do by hand. This is where the method of successive squaring comes into play. If you decide to try and program a solution then you might want to try the
*method of successive squaring*. So I calculated the rest for us, I literally plugged in the numbers into my python code from the method of successive squaring:

- The result is the number on the right side of the equivalent sign, record these results.
- [
**Step 10**] The encoded message is the list of numbers that was just calculated: 268999, 304266, 217909, 77242, 366806, 239952, 211676. Put these numbers together.

- So now our message can looks like this: 26899930426621790977242366806239952211676
- Notice there are no spaces, and we did not encode any numbers to represent spaces. You can do this if you so choose, but thats entirely up to you. Also if you send your message as one long string, make sure you also let the other person know how to split up the string.

- [
**Step 11**] Success! We have finally finished encoding our message, but how in the world are we suppose to change it back? This is a little more complicated than just switching backwards. We need two important pieces of information, our 'm' and 'k'. So we break up our long list of digits into groups of 5 and one group of 4. Then we begin to tackle each set of numbers. - So our first number is 268999, our problem looks like this:

- First lets recap what we already know:

- You have to use The Kth Roots Modulo m Algorithm to solve this problem, if you did not read all those earlier definitions than this may seem confusing. If you did read all those definitions, then following the steps will not be so cumbersome. You keep solving each problem by hand until you have finished all of them. The two main techniques are the Euclidean algorithm and successive squaring. The Chinese Remainder Theorem would speed this process up immensely because it can solve all of these problems in less computation.
- We should be getting our numbers back, record what 'x' is:

- As you can see we get back our string of encoded letters, each calculation gets us part of our original string back. The numbers are just separated :

28291, 11319, 26181, 52811, 22172, 52819, 3023

- Now we string it together to get 2829111319261815281122172528193023 and look at our table of letters:

, , , , , , , , , , , , , , , , , , , , , , , , ,

Our message reads "RSACIPHERALGORITHM" which if we pick out spaces, it would look "RSA CIPHER ALGORITHM". We have come full circle again. There is lot you can do with the RSA algorithm if you know how to program, even a little. You could even program a "space" character to fit into your message, so your message would be easier to read when decoded. But who would want an easy message to read?, really?

Reference:

- Silverman, Joseph H.
*A Friendly Introduction To Number Theory*. 3rd ed. Upper Saddle River, New Jersey: Pearson Education, Inc., 2006. 117-121. Print. - "Cipher."
*Wikipedia, the free encyclopedia*. N.p., n.d. Web. 6 Jan. 2013. <http://en.wikipedia.org>. Path: http://en.wikipedia.org/wiki/Cipher. - "Cryptography."
*Wikipedia, the free encyclopedia*. N.p., n.d. Web. 6 Jan. 2013. <http://en.wikipedia.org>. Path: http://en.wikipedia.org/wiki/Cryptography.