Some Complete Examples

So the arithmetic is easy to follow, we use small primes $p$ and $q$ and encrypt the single letter ``X'' using the RSA cryptosystem.

1. Choose $p$ and $q$ : Let $p=17$ , $q=19$ , so $n=pq = 323$ .
2. Compute $\varphi (n)$ :

   $$\varphi (n) = \varphi (p\cdot q) =\varphi (p)\cdot\varphi (q) = (p-1)(q-1)$$

   $$= pq-p-q+1 = 323-17-19+1 = 288.$$

   
   

3. Randomly choose an $e<288$ : We choose $e=95$ .
4. Solve
   $$95x \equiv 1\pmod{288}.$$
   Using the GCD algorithm, we find that $d=191$ solves the equation.

The public key is $(323,95)$ , so the encryption function is

$$E(x) = x^{95},$$

and the decryption function is $D(x) = x^{191}$ .

Next, we encrypt the letter ``X''. It is encoded as the number $24$ , since X is the $24$ th letter of the alphabet. We have

$$E(24) = 24^{95} = 294 \in \mathbb{Z}/323\mathbb{Z}{}.$$

To decrypt, we compute $E^{-1}$ :

$$E^{-1}(294) = 294^{191} = 24 \in \mathbb{Z}/323\mathbb{Z}{}.$$

This next example illustrates RSA but with bigger numbers. Let

$$p=738873402423833494183027176953, q=3787776806865662882378273.$$

Then

$$n=p\cdot q = 2798687536910915970127263606347911460948554197853542169$$

and

$$\varphi (n) =(p-1)(q-1)$$

$$= 2798687536910915970127262867470721260308194351943986944.$$

Using a pseudo-random number generator on a computer, the author randomly chose the integer

$$e=1483959194866204179348536010284716655442139024915720699.$$

Then

$$d = 2113367928496305469541348387088632973457802358781610803$$

Since $\log_{27}(n) \approx 38.04$ , we can encode then encrypt single blocks of up to 38 letters. Let's encrypt ``RUN NIKITA'', which encodes as $m=143338425831991$ . We have

$$E(m) = m^e$$

$$= 1504554432996568133393088878600948101773726800878873990.$$

Remark 3.2   In practice one usually choses $e$ to be small, since that does not seem to reduce the security of RSA, and makes the key size smaller. For example, in the OpenSSL documentation (see http://www.openssl.org/) about their implementation of RSA it states that ``The exponent is an odd number, typically 3, 17 or 65537.''