Efficient RSA Encryption and Decryption Operations

This section describes an efficient way of carrying out RSA encryption and decryption operations provided by authors of RSA algorithm.

One efficient way to carry out the RSA encryption operation of "C = M**e mod n" is to use the following algorithm provided by authors of RSA as:

```Step 1. Represent e in binary format and
store it binary digits in array e[0], e[1], ..., e[k]
Step 2. Set the variable C to 1
Step 3. For each i from 0 to k, repeat steps 3a and 3b
Step 3a. C is reset to C*C mod n
Step 3b. If e[i] = 1, C is reset to C*M mod n
```

The RSA decryption operation of "M = C**d mod n" can also be carried out using the same algorithm:

```Step 1. Represent d in binary format and
store it binary digits in array d[0], d[1], ..., d[k]
Step 2. Set the variable M to 1
Step 3. For each i from 0 to k, repeat steps 3a and 3b
Step 3a. M is reset to M**2 mod n
Step 3b. If d[i] = 1, M is reset to M*C mod n
```

Let's use an example presented in the previous tutorial to validate the algorithm:

```Given C = 62, d = 65, and n = 133
Calculate M = C**d mod n = 62**65 mod 133

Step 1. Represent d, 65, in binary format in array d[]
d[] = {1,0,0,0,0,0,1}, k = 6

Step 2. Set the variable M to 1
M = 1

Step 3. For each i from 0 to 6, repeat steps 3a and 3b
i = 0, d[0] = 1
M = 1*1 mod 133 = 1       (1)
M = 1*62 mod 133 = 62     (2)

i = 1, d[1] = 0
M = 62**2 mod 133 = 120   (3)

i = 1, d[2] = 0
M = 120**2 mod 133 = 36   (4)

i = 1, d[3] = 0
M = 36**2 mod 133 = 99    (5)

i = 1, d[4] = 0
M = 99**2 mod 133 = 92    (6)

i = 1, d[5] = 0
M = 92**2 mod 133 = 85    (7)

i = 1, d[6] = 1
M = 85**2 mod 133 = 43    (8)
M = 43*62 mod 133 = 6     (9)
```

Looks good. It matches the result presented in the previous tutorial.

If we start with the last calculation (9) and combine backward other calculations, we can see why this algorithm works:

```M = 43*62 mod 133                              # start with (9)
= 85**2 *62 mod 133                          # combine (8)
= (92**2)**2 *62 mod 133                     # combine (7)
= ((99**2)**2)**2 *62 mod 133                # combine (6)
= (((36**2)**2)**2)**2 *62 mod 133           # combine (5)
= ((((120**2)**2)**2)**2)**2 *62 mod 133     # combine (4)
= (((((62**2)**2)**2)**2)**2)**2 *62 mod 133 # combine (3), (2), (1)
= 62**64 *62 mod 133                         # consolidate exp.
= 62**65 mod 133
```