next up previous contents
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 $ A$ (for Alice) takes two large primes $ p_A$ and $ q_A$ with $ > 100$ digits. She obtains $ N_A = p_A q_A$ and chooses at random $ \rho_A$ such that $ (\rho_A, \phi(N_A)) = 1$. We can ensure that $ p_A - 1$ and $ q_A - 1$ have few factors. Now $ A$ publishes the pair $ N_A$ and $ \rho_A$. By some agreed method $ B$ (for Bob) codes his message for Alice as a sequence of numbers $ M < N_A$. Then $ B$ sends $ A$ the number $ M^{\rho_A} \pmod{N_A}$. When Alice wants to decode the message she chooses $ d_A$ such that $ d_A \rho_A \equiv 1 \pmod \phi(N_A)$. Then $ M^{\rho_A d_A} \equiv M
\pmod{N_A}$ since $ M^{\phi(N_A)} \equiv 1$. No-one else can decode messages to Alice since they would need to factorise $ N_A$ to obtain $ \phi(N_A)$. If Alice and Bob want to be sure who is sending them messages, then Bob could send Alice $ E_A(D_B(M))$ and Alice could apply $ E_B D_A$ to get the message -- if it's from Bob.
next up previous contents
Next: Countability Up: Euler's Phi Function Previous: Euler's Phi Function   Contents
root 2002-06-10