** Next:** Countability
** Up:** Euler's Phi Function
** Previous:** Euler's Phi Function
** Contents**

Private key cryptosystems rely on keeping the encoding key secret. Once
it is known the code is not difficult to break. Public key cryptography
is different. The encoding keys are public knowledge but decoding remains
``impossible'' except to legitimate users. It is usually based of the immense
difficulty of factorising sufficiently large numbers. At present
150 - 200 digit numbers cannot be factorised in a lifetime.
We will study the RSA system of Rivest, Shamir and Adleson. The user
(for Alice) takes two large primes and with digits.
She obtains
and chooses at random such that
. We can ensure that and have
few factors. Now publishes the pair and .
By some agreed method (for Bob) codes his message for Alice as a sequence
of numbers . Then sends the number
.
When Alice wants to decode the message she chooses such that
. Then
since
. No-one else can decode
messages to Alice since they would need to factorise to obtain
.
If Alice and Bob want to be sure who is sending them messages, then
Bob could send Alice
and Alice could apply
to get the message -- if it's from Bob.

** Next:** Countability
** Up:** Euler's Phi Function
** Previous:** Euler's Phi Function
** Contents**
root
2002-06-10