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

## Public Key Cryptography

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