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)))))