Next: Digital Signatures Up: PGP Previous: Public/Private Key Cryptography

RSA

I will look at one solution to this problem of finding suitable functions and 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 than one that simply tries every (prime) number up to . I've put `prime' in brackets because it is often quicker to test to see if a number is a factor of than it is to check if it is a prime. If we choose a large , 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 , and that we can check 1 billion numbers a second. We'll ignore the fact that finding the complete list of primes less than is also non-trivial!

We refer to the prime number theorem that suggests that the number of primes less than is approximately .

Apply prime number theorem

Assuming 1 billion a second
seconds
hours
days
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 and . These should be around 100 digits in length. Define n by .

2.
Find a large random integer that is relatively prime to .

3.
Computer (where ) from the formula

4.
Publish the pair as your public key.

We can now encrypt using the function

and we can decrypte using the function

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 and . . A coprime to could be which gives us . Now lets encrypt our string.

...

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:

...

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 in the general case. Recall

( ). Now consider substituting this into the decrypted message.

to give

which (by expanding by the binomial theorem) is

By definition so, for some non-negative integer we get

By Fermat's Theorem since is prime if and if we get

thus

(the case is trivial)

We can similary show

So (by a simple lemma not written out here)

which means we now have

and we are done.

Next: Digital Signatures Up: PGP Previous: Public/Private Key Cryptography
Stephen White
2000-03-28