# 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 \pmod{26}$. It's worth mentioning that $23 + 5 \equiv 54 \pmod{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 \pmod{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:

- Convert plaintext letter to a numerical value, $P$
- Add the key value, $k$, to the plaintext value.
- Determine $\left(P + k\right) \text{ MOD } 26$.
- Use this value to determine the ciphertext letter.
- 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:

- Convert ciphertext letter to a numerical value, $C$
*Subtract*the key value, $k$, from the ciphertext value.- Determine $\left(C - k\right) \text{ MOD } 26$.
- Use this value to determine the plaintext letter.
- 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 ...
```

## Programming the Caesar Cipher

Now that we have a good feel for the algorithm that we'll want to implement, let's figure out how to use Python to do it for us. Let's go step by step through the algorithm to see how Python can help. To get started let's take in our plaintext message, `zebras eat grass`

, and store it using upper-case letters and without spaces (we'll see why that will be helpful very soon). We'll use a key value of `7`

stored to the variable `key`

. Lastly, let's create an empty string called `ciphertext`

that we can store our enciphered message to when we're done.

```
plaintext = 'zebras eat grass'
plaintext = plaintext.upper().replace(' ', '')
key = 7
ciphertext = ''
```

### 1. Convert the plaintext letter to a numerical value

We need a quick and easy way to take our string of plaintext, and convert it character by character to numerical representations. There are several ways that a computer can think of a letter as a number (binary, ascii, etc), but let's try to create a method that's the same as what we've been using (`A = 0, B = 1, C = 2, ...`

etc).

The following code should do the trick:

```
LETTERS = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
```

Having the string `LETTERS = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'`

combined with the `find()`

method allows Python to find a single character in the string `LETTERS`

and return the index where it's found. Because `LETTERS`

contains all the letters of the alphabet in order, this `find()`

operation is the same as converting the character to its numerical representation, provided the character is in `LETTERS`

.

For example:

```
print( LETTERS.find('A') )
print( LETTERS.find('P') )
```

We even could use a loop to print out each letter in the plaintexts numerical representation if we wanted:

```
for character in plaintext:
print( LETTERS.find(character) )
```

This is why making sure the plaintext is converted to upper-case letters is important. Since the string `LETTERS`

only contains the upper-case version of each letter and the `find()`

method is case-sensitive, attempting to find a lower-case letter or space from the plaintext string would return a value of `-1`

, which is not a correct numerical representation of the letter.

```
for character in plaintext:
print( LETTERS.find(character) + key )
```

You can see that since `LETTERS.find(character)`

is an integer, we can add the integer `key`

to it before printing. Now some of these numbers are bigger than `25`

, so we'll need to do something about that.

```
for character in plaintext:
print( (LETTERS.find(character) + key) % 26 )
```

All of these numbers are in the proper range of values, `0 - 25`

. Now we just need to convert them back to letters.

### 4. Use this value to determine the plaintext letter.

To convert these new numbers back to letters, we can utilize the `LETTERS`

string again. Instead of using it with the `find()`

method, which takes in a string or character, we'll use the index feature of strings to determine which character is found at a particular index. For example, if we had the numerical values of 7 and 15, we could use `LETTERS`

to determine they correspond to `H`

and `P`

by:

```
print( LETTERS[7] )
print( LETTERS[15] )
```

We could then do this for each numerical value we determined by including it as part of the loop. It's getting a bit messy, but using `(LETTERS.find(character) + key) % 26`

as the index value:

```
for character in plaintext:
print( LETTERS[ (LETTERS.find(character) + key) % 26 ] )
```

We now have a loop that iterates through each character of the string `plaintext`

and performs a Caesar Cipher to determine the corresponding letter in the `ciphertext`

. The last thing we'll want to do is store each letter to a new string instead of printing them out one at a time. Let's store each character to the string `ciphertext`

and then print once we've stored the entire message.

```
for character in plaintext:
ciphertext = ciphertext + LETTERS[ (LETTERS.find(character) + key) % 26 ]
print(ciphertext)
```

```
plaintext = 'zebras eat grass'
plaintext = plaintext.upper().replace(' ', '')
key = 7
ciphertext = ''
LETTERS = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
for character in plaintext:
ciphertext = ciphertext + LETTERS[ (LETTERS.find(character) + key) % 26 ]
print(ciphertext)
```

This Code Vizualization.replace('+',+'')%0Akey+%3D+7%0Aciphertext+%3D+''%0ALETTERS+%3D+'ABCDEFGHIJKLMNOPQRSTUVWXYZ'%0A%0Afor+character+in+plaintext%3A%0A++++ciphertext+%3D+ciphertext+%2B+LETTERS%5B+(LETTERS.find(character)+%2B+key)+%25+26+%5D%0A++++%0Aprint(ciphertext)&mode=display&raw_input=&curInstr=0) illustrates how we're building the ciphertext string one character at a time.

### Exercise for the Reader

Can you write a similar function for deciphering a ciphertext generated by a Caesar Shift?