Alice wants to send a secure message to Bob where the message is converted from a plaintext to an integer \(m\) which can be done by ASCII codes: A is 065, B is 066,..., Z is 090, full stop is 046, space is 032, 0 is 048, 1 is 049,..., 9 is 057 etc.

1. Key Generation: Bob has a public key \((n,e)\) where \(n>m\) is a product of two large primes (only known to Bob) and \(e\) is in \((1,\phi(n))\) and relatively prime to \(\phi(n)\). Bob also has a private key \(d\) (only known to Bob) in \((1,\phi(n))\) which satisfies \(ed\equiv 1 \:\left(\mathrm{mod}\:\phi(n)\right)\).
   
   
2. Encryption: Alice uses Bob's public key \((n,e)\) and calculates the ciphertext \(c\equiv m^e \:\left(\mathrm{mod}\: n \right)\). Alice sends \(c\) to Bob.
   
   
3. Decryption: Using \(c\) and his private key \(d\), Bob calculates \(c^d \:\left(\mathrm{mod}\: n \right)\) which turns out to be \(m\equiv m^{ed}\equiv c^d \:\left(\mathrm{mod}\: n \right)\), the original message (why?).

Theorem. Let \(n=pq\) where \(p\) and \(q\) are distinct primes. Suppose \(e\) and \(d\) are integers in \((1,\phi(n))\) such that \(ed\equiv 1 \:\left(\mathrm{mod}\: \phi(n)\right)\). Then for any positive integers \(m < n\) relatively prime to \(n\), we have \(m^{ed}\equiv m \:\left(\mathrm{mod}\: n \right)\).

In case \(m\) is not relatively prime to \(n=pq\), \(m\) is one of \(n-1-\phi(n)=p+q-2\) integers in \([1,n)\). The probability of choosing such \(m\) is \(\displaystyle\frac{p+q-2}{pq}= \frac{1}{p}+\frac{1}{q}-\frac{2}{pq}\) which is very small.

To find \(d\) in \((1,\phi(n))\) satisfying \(ed\equiv 1 \:\left(\mathrm{mod}\:\phi(n) \right)\), note that \(xe+y\phi(n)=\gcd(e,\phi(n))=1\), i.e., \(xe\equiv 1 \:\left(\mathrm{mod}\: \phi(n)\right)\). We find the unique solution \(x=d\) by the extended Euclidean algorithm.

Example. Alice converts the plaintext "NO" to \(m=078\;079\). Bob has public key \((n,e)=(295927,\; 1081)\). Alice uses Bob's public key \((n,e)\) and calculates the ciphertext \(c\equiv m^e \:\left(\mathrm{mod}\: n \right)\), i.e., \((078\;079)^{1081}\equiv 120818 \:\left(\mathrm{mod}\: 295927 \right)\). Alice sends \(c=120,818\) to Bob. Now Bob has produced his public key \((n,e)\) with this secret calculation: \[ n=pq \text{ for } p=541 \text{ and } q=547 \text{ where } e=1+2*(p-1)=1081.\] Now Bob calculates his private key \(d=160921\) for which \(ed\equiv 1 \:\left(\mathrm{mod}\: \phi(n) \right)\). To decrypt Alice's ciphertext, Bob calculates \(c^d \:\left(\mathrm{mod}\: n \right)\), i.e., \((120,818)^{160921}\equiv 78079 \:\left(\mathrm{mod}\: 295927 \right)\). Note that \(e=1081\) is known to be relatively prime to \(\phi(n)=294,840\). But it is hard to calculate Bob's private key \(d\) for which \(ed\equiv 1 \:\left(\mathrm{mod}\: \phi(n) \right)\).

Why is it a good cryptosystem?
Suppose that some third party gains access to the number \(c\). In order to recover the number \(m\) he has to extract the \(e\)th root of \(c\) modulo \(n\). There seems to be no other feasible method for this than to find the number \(d\), and for that he need to know \(\phi(n)\), and for that he has to factor the number \(n\). But factorization of integers with 1000 binary digits seems to be beyond the reach of most of today's algorithms and computers.

Last edited