The Rules

So, we have some ground-rules before we start off on this venture. I’ll qualify them out below.

• I’m a computer scientist, not a strict mathematician. Yes, what I’m versed in is math, but I’m not a mathematician in the strict sense.
• As a non-mathematician, I will attempt to clear up the algorithm in the most human way I can.
• As a non-mathematician, I will not attempt to prove the theorem regarding the algorithm. That can come later, but for now, take my word for it,
• If you disagree with what I’ve set up, please ( PLEASE ) tell me. Assume ignorance over malice. Corrections welcome. Just don’t be a dick.

Loving Acknowledgements

I’d like to thank Dr. Shick, at John Carroll University. He’s one incredible teacher. All of this blog post is digested material from him. Thanks!

The Overview

The RSA algorithm is a public-key algorithm, which uses prime numbers and some crafty math to send data, encoded. The trick is to use very ( very very ) large prime numbers, to work in a way that makes the prime number decomposition of these wicked-large numbers ultra-hard to compute.

Needless to say, I’ll be using tiny little numbers.

Some Basics

Firstly, we need to establish Fermat’s little theorem. I’m not going to prove it here, since I really would not do it justice.

Now, Fermat’s little theorem is simply:

Or, following the rules that we call math, we can arrive on this “tweak” that we can use for personal gain and mass trickery.

Great. More on this later. I’m also no longer going to use the triple bar equals sign, so nit-pickers beware!

Now, let’s also set up some more easy tidbits.

Down the rabbit hole

So, now that we have the background down, we can move on to the real stuff. Let’s start off with exponents.

Let’s start off with something huge ( Let’s say, 2 to the 103 ( mod 143 )).

Let’s pretend computers can’t compute this number ( I know they can, stop arguing, play along, or I’ll actually use huge numbers ).

Let’s move forward by going back. Let’s take a look at powers of two, mod 143.

Bear in mind, the stupid simple re-phrase. It’s in there just to get you to think of stuff as squares, and not just these silly one-off numbers, and let us use the following “cheat”:

Great. I now claim that you can work out 2 to the 103 ( mod 143 ).

which wolfram alpha confirms. Fantastic.

The RSA Algorithm

Now that we have the basics out of the way, let’s move on to the actual RSA algorithm!

So, we need some primes to start out. Let’s call them p and q. Both p and q must be distinct primes. When we actually do this ( for realsies ) we need to pick re-he-he-he-he-he-he-he-he-he-he-he-he-he-he-he-ly large primes.

Now. We will also need to create a secret number N, which is relatively prime to (p-1) and (q-1).

We then need to work out the key, the public half. We find it by working out some math ( while using a bit of Fermat’s little theorem ).

MN = 1 (mod((p-1)(q-1)))

Fancy. Now, let’s work out our M.

Now, let’s work out encryption. To encode, we use the following two equations.

Let’s encode the message “CAT” to our fellow hackers.

Starting at A=0, we can translate “CAT” to [ 2, 0, 19 ].

I’ll now be phrasing it as:

X = [ 2, 0, 19 ]

Wait, shit. We can’t encode cat! Why do you ask?

Since T translates to 19, it gets chopped from the modulo operation, since it’s maxed at 15. Since 19 = 4 (mod 15), the T would translate to D, giving us the brilliant clear-text ( after a decode ) of “CAD”. Doh! After all, in modulo 15, D is equivalent to T. Let’s just go on with “CAT”, knowing that it’s going to output “CAD”.

P.S. this won’t usually happen, since both p and q are stupid huge primes.

So, let’s take X to the M, and mod it by our pq ( 15 ).

X is 2, M[0] is 7 – and 2 to the 7th is 128. 128 mod 15 is 8, so our Y[0] is 8.

Next, we have 0, and 0 to the anything-th, we get 0. 0 mod 15 is 0, so our Y[1] is 0.

Lastly, we have 19 ( A.K.A: 4 ). 4 to the 7th (mod 15) results in a Y[2] = 4.

Y = [ 8, 0, 4 ] ( HAD )

where:

X = [ 2, 0, [4|19] ] ( CA[D|T] )

And to decrypt:

Y to the N (mod pq) reduces to X. Let’s run through.

8 to the 7th (mod 15) is 2

0 to the 7th (mod 15) is 0

and 4 to the 7th (mod 15) is 4.

Huzzah!!!

This gives us our X back, without giving out p, q or N.

That’s it for part one, I’ll expand on some of this later on.