RSA is a common encryption algorithm that I wanted to understand. Bruce Schneier's excellent Applied Cryptography gives a good explanation but I found a few steps missing. Building on his derivation, I am going flesh it out.

**What you need to know**__Vocabulary__

- Relatively prime (or mutually prime or coprime): two integers are relatively prime when their only common divisor is 1.
- Congruent: if two integers are have the same value when mod-ed with a third integer, they are congruent.

__Notation__

There is a lot of modulus arithmetic in cryptography and the notation looks like this:

a ≡ b (mod c)

This should not be read in the fashion of a programmer, like a = b mod c (or a = b % c in most languages). Rather, the mod applies to the whole equation so you should read it more like:

(a ≡ b) (mod c)

__Modulus Arithmetic Formulas__

You also need to know some formulas.

[f1] a

^{p - 1 }≡ 1 (mod p) iff p is prime

This is Fermat's little theorem and the best proof I found is here.

__General Maths Formulas__

As any school child can tell you:

[f2] a

^{bc}= (a

^{b})

^{c}

and:

[f3] a

^{b + c}= a

^{b}a

^{c}

Also, the result of a mod is just the remainder of a division so it should be obvious:

[f4] a mod b = c ⇔ a = kb + c

where k is just some integer.

__The Derivation__Choose two large prime numbers, p and q. Let n be the product of the two.

[d1] n = pq

Why they must be prime will become apparent but it involves [f1] above.

Choose any integer e that is relatively prime to n.

Then, calculate d such that:

(d2) ed ≡ 1 (mod ((p-1)(q-1)))

And that's it. Numbers n an e make the public key and d is the private key.

Now, let's take a message, m. If it's too big, we can break it down and if it's too small we can pad it. But that's not of interest at the moment, so let's just say m is a number we want to encrypt.

Encryption looks like this:

[d3] c ≡ m

^{e }(mod n)

where c is the encrypted result.

Decryption looks like this:

[d4] m ≡ c

^{d}(mod n)

Easy, right?

__Yes, but why does it work?__

Why is equation [d4] true?

Ok, substitute c in [d4] with c in [d3] and use [f2] to trivially simplify:

[d5] m ≡ m

^{ed}(mod n)

now substitute [d1] into this:

[d6] m ≡ m

^{ed}(mod pq)

Now, re-express [d2] in the format of [f4]:

[d7] ed = k ((p-1)(q-1) + 1

and substitute [d7] for ed in [d6]:

[d8] m ≡ m

^{(k(p-1)(q-1) + 1)}(mod pq)

Using [f3], this is the same as:

[d9] m ≡ m . m

^{k(p-1)(q-1)}(mod pq)

which, because of f3 is the same as:

[d10] m ≡ m . m

^{k(p-1)}m

^{(q-1)}(mod pq)

Now, let's invoke [f1] for (q-1):

[d11] m ≡ m . (m

^{q-1})

^{k }m

^{(p-1)}(mod pq)

≡ m . 1

^{k}m

^{(p-1)}(mod pq)

≡ m . m

^{(p-1)}(mod pq)

and again for (p-1):

[d12] m ≡ m (mod pq)

which is obviously true, so what we started with [d4] must also be true.

## No comments:

## Post a Comment