I finally get RSA

Over the last week or so I've been trying to figure out how RSA encryption works. I've been reading books like In Code, and Number Theory.

Today I can say that I properly understand how to do RSA style encryption.

It all starts with finally understanding congruences...

C ≡ P^E(mod n)
and
P ≡ C^D(mod n)
where P = plain text and C = Cipher text

For the readers at home this is read as:
C is congruent to P raised to the E power modulo n
This means that if you divide C by n, or P raised to the E by n you will get the same remainder. In the case of cryptography you are seeking C which IS the remainder.

To make life easier I'll write it in a more friendly programming notation:
C = (P^E)%n

Once I understood this much the next part was figuring out how to come up with valid values of n, E, and D. What follows is how you come up with an RSA key.

Before we can find n we need to mind our p's and q's.
p and q are primes.

For the sake of this exercise we will select 31 and 17 as our primes.
p = 31
q = 17
n = p * q = 527
φ(n) = (p-1) * (q-1) = 480

The last one: φ(n) gives us the modulous we need as a base for finding D and E.

We need to find a number that is relatively prime to φ(n) (no common factors). We can use the euclidian algorithm to determine the greatest common divisor. I'll post code at the end.

Let's try 41 for E.
gcd(480,41) = 1
E=41

Now we need to find D, the multiplicative inverse of E modulo φ(n).
41*D ≡ 1(mod 480)

This part took me 3 days to figure out. It finally came together when I read about the Extended Euclidean algorithm on wikipedia. I wrote a function that returns the multiplicative inverse based on the modulous.

In this case D = 281.

We have generated a bunch of numbers:
p = 31
q = 17
n = 527
φ(n) = 480
E = 41
D = 281

Now we need to discard p, q, and φ(n).

In RSA encryption p and q are large prime numbers (100+ digits). The reason why it is secure is you need to know p and q to get D from E. When n is the product of large primes it becomes very time consuming to factor back to those primes.

Finally, this leaves us with our key pair.
K_E = (41,527)
K_D = (281,527)

Now for the code of the gcd function and the multiplicative inverse modulo base function:
(Forgive the indentation, I know no good way of doing this with blogger)

(defun eu-gcd (base num)
(let ((remainder (mod base num)))
(if (eq remainder 0)
num
(eu-gcd num remainder))))

(defun inverse-modulo (base num &optional (b1 0) (b2 1) orig-base)
(let* ((di (mod base num))
(k (- 0 (/ (- di base) num)))
(bi (- b1 (* k b2))))
(if (eq di 1)
(mod bi orig-base)
(inverse-modulo num di b2 bi (if orig-base orig-base base)))))

How political thinking in utah works

This morning I was thinking about it and realized that my car was hit right under my Pete Ashdown sticker.

I began channeling the standard utah-party-politics-religion paranoia and was thus led to the conclusion that an Orrin Hatch supporter was subliminally led to drive poorly in the Dan's parking lot!

That's it! Republicans don't think democrats should drive decent looking cars!

I'll show them. I'll support legislation that bans business owners from writing off those nice cars they lease. We all know that ALL republicans are business owners so I'll be able to stop them from having nice cars too!

The only trouble is that it won't stop there...

Next week when I get an oil change I'm going to have to make sure that it's a good democrat that does it. If I let a republican do it who knows what they'll sabotage on my car!

You see, those republican business owners want me to do my part in saving the economy by buying things I don't need. Like say, a new car.

The really devious part of it all is that you know the major car companies are run by republicans. That's the real reason they want me to buy a new car. It's all about selling their wares!

Retarded isn't it?

You can't have a reasonable discussion if you're competing with thinking that is on this level. If you don't believe me just wander around the conventions of both political parties and listen in on a few conversations.

If you're not with us you're a heretic.

Who suffers from this? The citizens.
Can you participate in the parties without getting sucked into it? Not really.

The wonders of Costco

Tonight I called Andy and we went to costco for dinner. It was a pretty ordinary trip. I picked up some bacon and some other food. We paid and decided to get some pizza.

While we were eating, a couple of employees were taking apart some tables. Andy and I overheard how they were trying to figure out how to throw them away.

I knew I had to act fast.

I inquired whether or not I could take one if they were throwing them away. They asked their supervisor and I got myself one free table.


I'm going to have to say that this is the coolest free table I've ever gotten.

Hit & Run

As far as I'm concerned there are only two types of hit & run.

There's the fun type:


And the not fun type:


Some call me a crazy driver, but to my credit I have yet to damage someone elses car while driving.

Huzzah! for no clichés

I was going through my RSS reader and found this blog post on coding horror: On the Use of Clichés.

I cut the text of my last post and pasted it into the cliché finder that was referenced. I felt special when it found nothing.

Now to keep up the not quite bad writing...