Caesar Cipher Revisted

# 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:

1. Convert plaintext letter to a numerical value, $P$
2. Add the key value, $k$, to the plaintext value.
3. Determine $\left(P + k\right) \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 $\left(C - k\right) \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   ...

## 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') )

0
15


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) )

25
4
1
17
0
18
4
0
19
6
17
0
18
18


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.

### 2. Add the Key Value to the plaintext value

Instead of printing each numerical representation, let's instead print out the numerical representation after we've added the key to it. Only one small modification of the code will do this for us:

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

32
11
8
24
7
25
11
7
26
13
24
7
25
25


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.

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

Remember, in Python % is equivalent to $\text{ MOD }$. In order to $\text{ MOD }$ LETTERS.find(character) + key by $26$, put that value in parenthesis to ensure you are modding after addition of the two values:

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

6
11
8
24
7
25
11
7
0
13
24
7
25
25


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] )

H
P


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 ] )

G
L
I
Y
H
Z
L
H
A
N
Y
H
Z
Z


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)

GLIYHZLHANYHZZ


## Everything Together

All of the code in a single cell would look like:

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)

GLIYHZLHANYHZZ


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.