Proof of RSA Encryption Operation Algorithm

Cryptography Tutorials - Herong's Tutorial Examples

∟Proof of RSA Encryption Operation Algorithm

This section discusses how to prove the RSA encryption operation algorithm.

We can also prove the encryption operation algorithm presented in the previous section in the following way:

Given integers M, e, and n
Express e as a binary expression:
   e = e[0]*2**k + e[1]*2**(k-1) + ... + e[k-1]*2**1 + e[k]*2**0

Given C = M**e mod n 

Replace e with the binary expression:
   C = M**(e[0]*2**k + e[1]*2**(k-1) + ... + e[k-1]*2**1 
       + M**e[k]*2**0) mod n

Split and simply the e[k] term:
   C = M**(e[0]*2**k + e[1]*2**(k-1) + ... ) * M**e[k] mod n
     
Factor remaining terms:
   C = (M**(e[0]*2**(k-1) + e[1]*2**(k-2) + ... + e[k-1]*2**0))**2
       * M**e[k] mod n

Split and simply the e[k-1] term:
   C = (M**(e[0]*2**(k-1) + e[1]*2**(k-2) + ...) * M**e[k-1])**2 
       * M**e[k] mod n

Repeat last two steps for e[k-2], ... e[0] terms:
   C = ((...((M**e[0])**2 * M**e[1])**2 * ...)**2 * M**e[k-1])**2
       * M**e[k] mod n
       
Move "mod n" into each team:
   C = ((...((M**e[0] mod n)**2 * M**e[1] mod n)**2 * ...)**2 
       * M**e[k-1] mod n)**2 
       * M**e[k] mod n

As you can see from the last expression, the "(...)**2 * M**e[i] mod n" is a repeating pattern. This leads us to the following algorithm to calculate "C = M**e mod n":

Given integers M, e, and n

Calculcate "C = M**e mod n":
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 step 3a
Step 3a. C is reset to "C**2 * M**e[i] mod n"