4.2. Caesar Cipher#

One way to avoid having to memorize the order of \(26\) letters is to use a mathematical function to help determine the mapping based on a simpler key value. The Caesar Shift is a well known cipher that can be classified as an additive cipher. It earns this classification because the method requires that you convert each plaintext letter into an integer based on its position in the alphabet, then the the key value is added to the position value to determine the corresponding letter in the ciphertext. In this course, the first letter in the plaintext alphabet will be represented with the number 0, since many programming languages (Python included) starts counting with the number 0. Using a key value of 3 would yield the following mappings for sample letters a and j:

\[a \rightarrow 0 \xrightarrow{+3} 3 \rightarrow D \text{ and } j \rightarrow 9 \xrightarrow{+3} 12 \rightarrow M\]

Completing this for each letter in the plaintext alphabet results in the following correspondance:

        0  1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
plain   a  b  c  d  e  f  g  h  i  j  k  l  m  n  o  p  q  r  s  t  u  v  w  x  y  z
cipher  D  E  F  G  H  I  J  K  L  M  N  O  P  Q  R  S  T  U  V  W  X  Y  Z  A  B  C

Since writing the ciphertext alphabet under the plaintext alphabet has the visual appearance of rotating the top row a few spaces, this type of cipher is also known as a rotation cipher, or ROT-cipher. Using a key of \(3\) is known as ROT-3.

Since you can only rotate the ciphertext so many spots before you start to get repeated mappings, there are far fewer keys in the Caesar Shift system. If you count a key of \(0\) as valid (although not very practical) there are only \(26\) keys in this system. We have a reduction in security when compared to a general substitution cipher, but a much greater ease of use since you only need to remember one number for the key instead of the complete mapping. This give and take of security and ease of use will be a common theme throughout the course.

Let’s get into the details on how this cipher works, and attempt to find a mathematical representation of this cipher.

Enciphering a Message#

Suppose we wanted to encipher the plaintext message unicorn to transmit to a friend, and we’ve previously agreed on a key value of 15. We can start by creating the mapping of plaintext to ciphertext letters.

It starts out easy enough,

\[a \rightarrow 0 \xrightarrow{+15} 15 \rightarrow P\]
\[\text{ then }\]
\[b \rightarrow 1 \xrightarrow{+15} 16 \rightarrow Q\]

But when we get to the letters l and m (and all letters after them) we see that this additive cipher needs a bit of clarification to be implemented correctly.

\[l \rightarrow 11 \xrightarrow{+15} 26 \rightarrow ? \text{ and } m \rightarrow 12 \xrightarrow{+15} 27 \rightarrow ?\]

Since there is no letter in the plaintext row with a position equal to or greater than \(26\), we need to determine how to compute the correct position value when values exceed \(25\).

        0  1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
plain   a  b  c  d  e  f  g  h  i  j  k  l  m  n  o  p  q  r  s  t  u  v  w  x  y  z
cipher  P  Q  R  S  T  U  V  W  X  Y  Z  ?  ?  ?  ?  ?  ?  ?  ?  ?  ?  ?  ?  ?  ?  ?

The letter l should be mapped to ciphertext letter A, since we’ve seen previously that the ciphertext row has the same order as the plaintext row, just rotated by the key value, which causes the alphabet to wrap around to the start. Completing the mapping results in

        0  1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
plain   a  b  c  d  e  f  g  h  i  j  k  l  m  n  o  p  q  r  s  t  u  v  w  x  y  z
cipher  P  Q  R  S  T  U  V  W  X  Y  Z  A  B  C  D  E  F  G  H  I  J  K  L  M  N  O

What is left to be determined is a mathematical operation that results in the correct mapping, even when our initial computed position value is greater than 25. We’ll save that for the next section. For now, let’s encipher our message, unicorn, and if we compute an invalid position number, we’ll just use the rotation/wrapping method to determine the correct ciphertext letter.

plain:  u   n   i   c   o   r   n
        20  13  8   2   14  17  13
        35  28  23  17  29  32  28
        ?   ?   X   R   ?   ?   ?
cipher: J   C   X   R   D   G   C

Enciphering Algorithm#

If we had to reduce our method down a to set of step-by-step instructions, it may look like this:

  1. Convert plaintext letter to a numerical value, \(P\)

  2. Add the key value, \(k\), to the plaintext value

  3. If \(0 \leq P + k \leq 25\), convert to a ciphertext letter.

  4. If \(P+k \lt 0\) or \(P+k \gt 25\), use the wrapping method to determine the ciphertext letter.

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

Steps 1-3 and 5 are very straight-forward and easy to describe, but Step 4 is a bit more complex in nature. Additionally, a choice needs to be made in this algorithm: perform Step 3 or Step 4 depending on the value of \(P + k\). In general, if we want a computer to eventually carry out these tasks for us, we prefer to use algorithms that are simple and straight-forward and can be executed the same way each time, as these types of algorithms are easier to program and typically more efficent to execute.

Deciphering a Message#

In order for an encrypted message to be readable by the recipient, whatever encryption method that was used to generate the ciphertext needs to be completely reversible. Mathematically, we can call deciphering the inverse of the enciphering function. Mathematical notation is often helpful in determining this inverse process.

The enciphering process for the Caesar shift written in function notation is: $\(C = P + k\)$

where \(C\) is the ciphertext letter’s position, \(P\) is the plaintext letter’s position, and \(k\) is the key value. We can take this relationship and solve for \(P\) to determine the series of operations that would result in computing the plaintext letter from the ciphertext letter.

\[ C - k = P\]
\[\text{or}\]
\[ P = C - k\]

We can see that for the Caesar Shift, the plaintext letter can be computed by taking the ciphertext letter, converting it to it’s position value, and subtracting the key value. This should hopefully make sense since addition and subtraction are inverse operations.

Taking our ciphertext of JCXRD GC from above, we could go letter by letter to determine the corresponding plaintext letter by subtracting the key value of \(15\) from each position value. We see very quickly we run into the same issue as with enciphering: we’ll compute position values that do not directly correspond to a plaintext letter. For example,

\[J \rightarrow 9 \xrightarrow{-15} -6 \rightarrow ?\]

We’ll use the wrapping method again to determine that \(J \rightarrow u\) and do the same for any invalid position numbers.

ciphertext: J    C    X    R    D    G    C
            9    2    23   17   3    6    2
           -6  -13    8    2  -12   -9  -13
            ?    ?    i    c    ?    ?    ?
 plaintext: u    n    i    c    o    r    n

Deciphering Algorithm#

We can see that the algorithm for deciphering a message is very similar to the algorithm for enciphering:

  1. Convert ciphertext letter to a numerical value

  2. Subtract the key value to the plaintext value

  3. If the new value is between 0 and 25, convert to a plaintext letter.

  4. If the new value is not between 0 and 25, use the wrapping method to determine the plaintext letter.

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

Again, step 4 is the complex step in the procedure, and it would be very helpful if we had an easier to define strategy to compute a valid position value between 0 and 25.