Friday, January 05, 2007

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 ≡ PE(mod n)
and
P ≡ CD(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.
KE = (41,527)
KD = (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)))))

4 comments:

ryanbyrd said...

here are my encryption notes along with an example: http://www.ryanbyrd.net/encrypt.php

Anonymous said...

"Now we need to find D, the multiplicative inverse of E modulo φ(n)."

I think what you mean is 'Modular multiplicative inverse'. After I figured that out, it helped a lot. Thanks!

Spat said...

I did not really get how you calculated the inverse. Please can you explain more detailed please

Unknown said...

I am still confused while learning this algorithm. This one is so complex and difficult to understand. Can you please give me some reference links which I can use to learn about it in more simple and easy way.
digital signature