Sunday, January 13, 2013

A Quick High-level look at RSA

Todays post is my attempt at reproducing my understanding of how the Math in RSA works.

I've mentioned references at the bottom of the email -- hopefully those links will help you dig deeper and provide you the clarity this post might not be able to provide.

Well, lets get started. I'm going to assume that the reader already know what PKI is, and that public keys and private keys are used to encrypt and decrypt respectively and that private keys are used for signing.

Most tutorials start off with a little bit of Math, and this is for good reason, I assure you. Also, whenever a theorem is mentioned I strongly urge you to play around with Sage, and check if the theorem does hold true(which is probably the next best thing to reading the proof of the theorem itself).

The Modulus operation

As computer programmers we all know what the following does :-

                       a = b % c;

=> From this point onward "=" refers to the "congruence operator" and not the "equality operator".

When we talk about Modular arithmetic in Math, we would write the above statement as :-

                        b = a (mod c)

Primes and Relatively-Prime numbers

We all know what primes are, so I'm not even going to bother with it. Relatively Prime numbers are the ones that have a gcd of 1.

gcd (a, b) = 1, iff a and b are relatively prime.

If you give it a bit of thought you realize that 1 is relatively prime to every number out there.

Extended Euclidean Theorem

Again you've probably heard of this, but I'll just mention it anyhow. With Extended Euclidean Theorem, you can calculate values x and y such that,

ax + by = 1,

when gcd(a, b) = 1

It isn't hard to do this on pen and paper for small values -- I also urge you to check out the sage function "xgcd" which performs this computation for you.

The notation "Zn" and "Zn*"

Zn has different meanings in different contexts -- however in the context of Cryptography, Zn is the set of all numbers from 0 to n-1.

Zn* is the a subset of Zn in which all the numbers are relatively prime to n

So far, so good huh?

When I say....

Later in this post I will say stuff like "is 1 in Zn".

What I mean when I say that is :-

a = 1 mod n "

Fermat's Theorem

Fermat came up with a ton of theorems -- one of them stated the following :-

" For any x in Zp* such that p is prime, the value x^(p-1) is 1 in Zp ".

In other words,

x ^ (p-1) = 1 mod p "

Why this is relevant will hopefully become more clear in the next part.

Euler Totient Function

Simply put, its the size of Zn*.

In other words, it is the count of the numbers in the range 0 to n-1 that are relatively prime to n.

Euler's Theorem

About a hundred years later, Euler came with an extension of Fermat's theorem. Fermat's theorem only applied to primes, but Euler extended it to composite numbers too.

" For a number x in Zn*, the value x^(phi(n)) is 1 in Zn "

In other words,

x ^ (phi(n)) = 1 mod n "

Even better, the theorem suggests a way to compute phi(n) for certain values of n.

If n = p * q such that and are primes, you can compute n as :-

phi(n) = phi(p) * phi(q) = (p-1)(q-1)"

Please note that if n is sufficiently huge and if its prime factorization cannot be computed, phi(n) also cant be computed.

Steps of RSA

About time, huh?

Step 1. Choose two primes p and and compute n = p * q
Step 2. Choose a value e in Zn*
Step 3. Using Euler's Theorem, compute d such that 

" de = 1 ( mod phi(n) ) "

At this point, our public key is (n, e) and our private key is (p, q, d).

Step 4. Encryption is done as 

c = m^e (mod n) "

Step 5. Decryption is done as

d = c^d (mod n) "

A short note on Step 3

At step 3 we have the equation :-

" de = 1 ( mod phi(n) ) "

Please note that this can be re-written as :-

d.e - k.phi(n) = 1

At this point, the value of d is solved using the Extended Euclidean Theorem.

References :-
- "Number Theory and the RSA Cryptosystem" - Minh Van Nguyen
- Stanford Coursera course on Cryptography(10-1, 10-2) - Dan Boneh

No comments:

Post a Comment