4.4. Relating Modular Arithmetic to the Caesar Cipher

Returning to our task of enciphering the letter x with a key of $5$, we now know that $23+5\equiv 2(\mathrm{mod}26)$. It’s worth mentioning that $23+5\equiv 54(\mathrm{mod}26)$ and infinitely more values besides $54$, however, there will only ever be one value that falls between $0$ and $n-1$, or in this case, $25$. This is the range of values that correspond to letters in the English alphabet. This fact ensures that we will have a unique encryption and decryption process. Notice that $28\equiv x(\mathrm{mod}26)$ has infintely many solutions for $x$, but $28\text{ MOD }26=x$ has only one.

So, how do we find this unique number between $0$ and $25$ that is congruent to the new position value computed? Put another way, how do we reduce the newly computed position value modulo $26$? Doing so by hand isn’t difficult, but it may be a bit tedious.

• If your computed value is greater than $25$, repeatedly subtract $26$ from the value until it falls between $0$ and $25$.

• If your computed value is less than $0$, repeatedly add $26$ until it falls between $0$ and $25$.

Performing this algorithm is equivalent to determining $m\text{ MOD }26=?$, where $m$ represents the numerical value of the current letter in the message being enciphered. We’ll see a bit later that most computer programming languages have a built in operation that performs the $\text{MOD}$ calculation for you, making this process very quick.

Revisiting the Caesar Cipher

We could update the encipher algorithm for the Caesar Cipher as follows:

1. Convert plaintext letter to a numerical value, $P$

2. Add the key value, $k$, to the plaintext value.

3. Determine $(P+k)\text{ MOD }26$.

4. Use this value to determine the ciphertext letter.

5. Repeat until all plaintext letters have been converted to ciphertext letters.

Notice that Step 3 is valid even if $P+k$ does not exceed $25$. As such, we’ve reduced the complexity of our algorithm. The same 5 steps will be performed each time without making a choice that is conditional on the value of $P+k$.

The deciphering algorithm is now almost identical to the encipher algorithm, with the only difference being how the key is used:

1. Convert ciphertext letter to a numerical value, $C$

2. Subtract the key value, $k$, from the ciphertext value.

3. Determine $(C-k)\text{ MOD }26$.

4. Use this value to determine the plaintext letter.

5. Repeat until all ciphertext letters have been converted to plaintext letters.

Implementing the Refined Algorithm by Hand

Let’s practice the new algorithm using the plaintext message zebras eat grass and key = $15$

 plaintext    z   e   b   r   a   s   ...
         P    25  4   1   17  0   18  ...
     P + k    40  19  16  32  15  33  ...
P+k MOD 26    14  19  16  8   15  7   ...
ciphertext    O   T   Q   I   P   H   ...

And now, the deciphering algorithm on the ciphertext messsage BARFZ N... and key = $13$.

ciphertext    B   A   R   F   Z   N   ...
         C    1   0   17  5   25  13  ...
     C - k   -12 -13  4  -8   12  0  ...
C-k MOD 26    14  13  4   18  12  0   ...
 plaintext    o   n   e   s   m   a   ...