RSA

I will look at one solution to this problem of finding suitable functions $S_A()$ and $P_A()$ that is used by a system called the Rivest-Shamir-Adleman (RSA) System. RSA, and several other public/private key systems, are supported by PGP.

The problem clearly revolves around finding a `one way' function. A function that is easy to calculate yet it's inverse is not easy to calcualate.

Given any two numbers, we may by a simple and infallible process obtain their product, but it is quite another matter when a large number is given to determine it's factors. Can the reader say what two numbers multiplied together will produce the number 8616460799?
I think it is unlikely that anyone but myself will ever know.
W. S. Jevons, `The Principles of Science', Macmillan, 1874.

It doesn't take much time for a Pentium III to tell us that the two numbers Jevons spoke about are 96079 and 89681. However it is also true that we don't have any algorithms that are much better at calculating factors of $n$ than one that simply tries every (prime) number up to $\sqrt{n}$. I've put `prime' in brackets because it is often quicker to test to see if a number is a factor of $n$ than it is to check if it is a prime. If we choose a large $n$, say 100 digits then it will clearly take even a computer a long time to find it's factors. Let's assume we check every prime number up to $\sqrt{10^{100}}$, and that we can check 1 billion numbers a second. We'll ignore the fact that finding the complete list of primes less than $n$ is also non-trivial!

We refer to the prime number theorem that suggests that the number of primes less than $x$ is approximately $x / \mathrm{ln} x$.

$\sqrt{10^{100}} = 10^{50}$
Apply prime number theorem
$8.69*10^{47}$
Assuming 1 billion a second
$8.69*10^{38}$ seconds
$2.41*10^{35}$ hours
$1.01*10^{34}$ days
$2.75*10^{31}$ years
Which is around 100 billion billion times the expected lifetime of the universe!

So it would appear that a suitable one way function is the multiplication of two large prime numbers. It is easy to multiply such large numbers together, but clearly very hard to factor their product if that is the only information that we are given.

It will now come as no surprise that this is the function that RSA relies on. The procedure is as follows:

1.

Find two large prime numbers $p$ and $q$. These should be around 100 digits in length. Define $n$n by $n = pq$.

2.

Find a large random integer $d$ that is relatively prime to $(p - 1)(q - 1)$.

3.

Computer $e$ (where $1 \leq e \leq (p-1)(q-1)$) from the formula $ed = 1 (\mathrm{mod}\ (p-1)(q-1))$

4.

Publish the pair $P = (e, n)$ as your public key.
Keep $S = (d, n)$ as your secret key.

We can now encrypt $M$ using the function

$$C = M^e (\mathrm{mod}\ n)$$

and we can decrypte $C$ using the function

$$D = C^d (\mathrm{mod}\ n)$$

Lets consider encrypting the string 'Why broccoli?' In ASCII this is represented by the following numbers.

87,104,121,32,98,114,111,99,99,111,108,105,63

Now suppose we chose prime $p=47$ and $q=59$. $n = pq = 2773$. A $d$ coprime to $(p-1)(q-1)$ could be $d=157$ which gives us $e = 17$. Now lets encrypt our string.

$87^{17} = 652 \ (\mathrm{mod}\ 2773)$
$104^{17} = 193 \ (\mathrm{mod}\ 2773)$
$121^{17} = 196 \ (\mathrm{mod}\ 2773)$
...

If we continue like this we get an encrypted string of:

652,193,196,2227,1860,1684,131,2576,2576,131,169,1020,2092,2073

This clearly isn't great because our key was short and by encrypting one letter at a time we're not doing much better than a simple letter substitution code - but it shows the basic principle. Now to show that we really can decrypt the string:

$652^{157} = 87 \ (\mathrm{mod}\ 2773)$
$193^{157} = 104 \ (\mathrm{mod}\ 2773)$
$196^{157} = 121 \ (\mathrm{mod}\ 2773)$
...

Which matches our origional data, and so we are happy. Except that one example that works hardly constitutes a complete proof. In order to show that RSA works we must prove that $M = D$ in the general case. Recall

$$C = M^e \ (\mathrm{mod}\ n) \equiv C = M^e - sn \ (\mathrm{mod}\ n)$$

( $s \in Z, s \geq 0$). Now consider substituting this into the decrypted message.

$$D = C^d \ (\mathrm{mod}\ n)$$

to give

$$D = (M^e - sn)^d \ (\mathrm{mod}\ n)$$

which (by expanding by the binomial theorem) is

$$D = M^{ed} \ (\mathrm{mod}\ n)$$

By definition $ed = 1 (\mathrm{mod}\ (p-1)(q-1))$ so, for some non-negative integer $k$ we get

$$M^{ed} = M^{1+k(p-1)(q-1)}$$

$$M^{ed} = M*(M^{p-1})^{k(q-1)}$$

By Fermat's Theorem since $p$ is prime if $a^{p-1} \equiv 1 \ (\mathrm{mod}\ p)$ and if $M \neq 0 \ (\mathrm{mod}\ p)$ we get

$$M^{ed} = M* 1^{k(q-1)} \ (\mathrm{mod}\ p)$$

thus

$$M^{ed} = M \ (\mathrm{mod}\ p)$$

(the case $M = 0 \ (\mathrm{mod}\ p)$ is trivial)

We can similary show

$$M^{ed} = M \ (\mathrm{mod}\ q)$$

So (by a simple lemma not written out here)

$$M^{ed} = M \ (\mathrm{mod}\ n)$$

which means we now have

$$D = M \ (\mathrm{mod}\ n)$$

and we are done.