Caesar Cipher

The Caesar Cipher (CC) is a classic symmetric key algorithm dating back to the time of Julius Caesar. If you are new to cryptography, the Caesar Cipher is a great first crypto algorithm to learn. This post will walk through the details of implementing a CC encrypt/decrypt function. You’ll then get a look at the internals of a CC code cracker.

Algorithm Description

There are four key ingredients to a Caesar Cipher:

alphabet: The set of characters that may form an encrypted/decrypted message.
plaintext: The secret message you’d like to transmit.
ciphertext: The encrypted plaintext message.
key: An integral shift applied to the characters in the plaintext message.

An example best illustrates how each of these components come together.

Suppose you want to send a secret message composed of only the lowercase English letters. You decide to use a Caesar Cipher to encrypt the plaintext “hello” using the key 14. To perform the encryption you map each character in the alphabet to an integer:

┌──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┐
│ 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│
├──┼──┼──┼──┼──┼──┼──┼──┼──┼──┼──┼──┼──┼──┼──┼──┼──┼──┼──┼──┼──┼──┼──┼──┼──┼──┤
│ 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│
└──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┘

To perform the encryption, add the key to each characters’ integer representation modulo the size of the alphabet. For example, the letter “o” encrypts to \((14 + 14) \mod 26 = 2\) which according to the table is the letter “c.” The table below shows the encrypted form of “hello”:

┌──┬──┬──┬──┬──┐
│ h│ e│ l│ l│ o│
├──┼──┼──┼──┼──┤
│ v│ s│ z│ z│ c│
└──┴──┴──┴──┴──┘

“vszzc” is the ciphertext that you send to all your friends along with the key. To decrypt the message, your friends apply the same shifting process but in reverse. For example, the letter “c” in the ciphertext decrypts to \((2 - 14) \mod 26 = 14\) which maps to the letter “o.”

In general, the encryption and decryption formulas are:

\[E_{n}(x) = (x + n) \mod |\Sigma|\]

\[D_{n}(x) = (x - n) \mod |\Sigma|\]

where \(x\) is the integer mapping of the encrypt/decrypt letter, \(n\) is the key, and \(|\Sigma|\) is the size of the alphabet.

Coding the Cipher

You can apply the CC encryption/decryption algorithm to any character set as long as you map each character to a unique integral value. In the world of computers and text, the ASCII character set is a perfect CC candidate. ASCII includes 128 characters each mapped to an integer in the range \([0, 127]\). The table below defines the ASCII character set. Only 95 out of 128 characters are printable.

Below is a C++ CC implementation that works with the ASCII alphabet:

RetCode AsciiCaesarCipher(std::istream &is, std::ostream &os, int shift) {
  if (!is) {
    return RetCode::kBadInputStream;
  }
  if (!os) {
    return RetCode::kBadOutputStream;
  }

  char curr = '\0';
  while (is.get(curr)) {
    curr = (static_cast<int>(curr) + shift) % kAsciiAlphabetSize;
    os << curr;
  }
  os.flush(); /* Flush the output stream just to be safe. */

  return RetCode::kSuccess;
}

Lets dissect this function starting with the function signature. AsciiCaesarCipher() takes three parameters: an input stream, an output stream, and a CC shift/key value. The input stream can be an open file (think std::ifstream), std::cin, or any other std::istream derived type. Similar to the input stream, the output stream can be an open file, std::cout, or some other std::ostream derived type. AsciiCaesarCipher() will output the result of the cipher to os. shift is the CC key as described in the previous section. AsciiCaesarCipher() returns a RetCode enum type:

enum class RetCode {
  kSuccess,
  kBadInputStream,
  kBadOutputStream,
};

The RetCode types are self explanatory.

AsciiCaesarCipher() reads characters out of the is stream one at a time. Each character has the CC shift applied. The shifted character gets output to os. The os.flush() call guarantees buffered data gets written to the recording medium. The same AsciiCaesarCipher() function can encrypt and decrypt ASCII text depending on the contents of is and the value of shift.

AsciiCaesarCipher() has a time complexity of \(\mathcal{O}(N)\) where \(N\) is the number of characters in the input stream. The space complexity is \(\mathcal{O}(1)\). In reality, std::istream and std::ostream objects buffer data to reduce read/write overhead. The size of these buffers is implementation dependent though likely a small, constant size.

Cracking the Code

The Caesar Cipher isn’t immune to attack. Due to the small key space, one could perform a ciphertext only, brute force attack to recover the secret message. That would be tedious to do by hand. With the right algorithm, the computer can do the dirty work for you. Lets explore two attack techniques: a dictionary attack and a frequency analysis attack.

Dictionary Attack

A CC dictionary attack has you applying every possible shift to the ciphertext. The shift that produces the largest number of valid “words” is most likely the decryption key. To perform this attack, you need a dictionary of valid words.

Below is a C++ implementation of a CC dictionary attack. The algorithm assumes you’re working with the ASCII character set and that the message decrypts to regular English.

using WordSet = std::unordered_set<std::string>;
using KeyScoreMap = std::unordered_map<int, int>;

KeyScoreMap AsciiDictionaryAttack(std::istream& is, std::istream& dict_is) {
  WordSet dictionary = LoadDictionary(dict_is);
  KeyScoreMap scores;
  char curr = '\0';
  char tmp = '\0';
  std::string words[cipher::kAsciiAlphabetSize];
  while (is.get(curr)) {
    for (int shift = 0; shift < cipher::kAsciiAlphabetSize; ++shift) {
      /* Perform the Caesar Cipher shift. */
      tmp = (static_cast<int>(curr) + shift) % cipher::kAsciiAlphabetSize;

      if (std::isalnum(tmp)) { /* Add a char to the word at this shift. */
        words[shift] += std::tolower(tmp);
      } else if (!words[shift].empty() &&
                 std::isspace(tmp)) { /* Found complete word. */
        if (dictionary.count(words[shift])) {
          scores[shift]++;
        }
        words[shift].clear();
      }
    }
  }

  /* Check for the trailing words. */
  for (int shift = 0; shift < cipher::kAsciiAlphabetSize; ++shift) {
    if (dictionary.count(words[shift])) {
      scores[shift]++;
    }
  }
  return scores;
}

There’s a lot to talk about here. Lets start with the types WordSet and KeyScoreMap. WordSet is a set of strings representing the most popular English words in lowercase form. Why a set? Using a set, you can determine whether a string is an English word with an average time complexity of \(\mathcal{O}(1)\).

KeyScoreMap is a map data structure. The map’s keys are CC shift/key values in the range \([0, 127]\). The map’s values are a tally of the number of English words seen when applying the corresponding shift key to the input stream.

AsciiDictionaryAttack() processes the input stream character by character. You apply each shift to the current input character. If following a shift the character is alphanumeric, then that character gets buffered in a string representing a candidate word. Otherwise, when a shift results in whitespace, the algorithm assumes a complete word proceeded the whitespace. In this case, if the word at the current shift value is an English word, the shift’s English word tally in scores gets incremented.

The output of AsciiDictionaryAttack() is a map with shift/key values and their scores. The key value with the highest score is the one you use to decrypt the ciphertext. It’s possible that two or more keys have the same score. In this case, apply all keys to find which makes most sense. The longer the input ciphertext is, the more likely you are to get an exact key match.

Frequency Analysis Attack

The frequency analysis attack depends on knowledge of the distribution of the ASCII characters in the English language. You take the ciphertext and apply all possible shifts to it. You then take a tally of the frequency of the characters in each translation as a percent value. The shift that produces the distribution closest to the expected distribution is the decryption key.

How do you know the distribution of ASCII characters in English? Someone has already done the hard part. The linked project analyzes the Reuters-21578 corpus to produce a table of ASCII frequencies. Note, some characters aren’t included in the table. You can assume the missing ASCII characters have a frequency of 0.

How do you compare distributions? There are a number of ways. One method is to treat the frequency distribution as a vector. In this case, the vector has 128 dimensions (one per ASCII character) where each dimension is a frequency represented as a percent value. You can compute the Manhattan Distance between to vectors to get a measure of how similar they are. The formula looks like this:

\[D = \sum_{i=0}^{127} |e_i - a_i|\]

Where \(e_i\) is the expected percent frequency of the ASCII character corresponding to \(i\) in the English language. \(a_i\) is the actual frequency of the character as measured in the ciphertext. The shift that produces the smallest distance value is the decryption key.

Lets look at the code:

using CharFrequencies = std::array<double, cipher::kAsciiAlphabetSize>;
using CharFrequencyArray =
    std::array<CharFrequencies, cipher::kAsciiAlphabetSize>;

KeyScoreMap AsciiFrequencyAnalysisAttack(std::istream& is) {
  CharFrequencyArray freqs;
  char curr = '\0';
  int tmp = 0;
  double num_chars = 0;
  while (is.get(curr)) {
    for (int shift = 0; shift < cipher::kAsciiAlphabetSize; ++shift) {
      /* Perform the Caesar Cipher shift. */
      tmp = (static_cast<int>(curr) + shift) % cipher::kAsciiAlphabetSize;

      /* Tally the shifted char. */
      freqs[shift][tmp]++;
    }
    num_chars++;
  }

  /* Calculate the percent frequency of each char. */
  for (auto& table : freqs) {
    for (double& val : table) {
      val /= num_chars;
    }
  }

  return FindMinDistShifts(freqs);
}

AsciiFrequencyAnalysisAttack() uses the CharFrequencyArray type to store the frequency distribution of each shift. The algorithm loops over the characters in the input stream and applies the CC to each character. The shifted character gets tallied in the corresponding frequency table. num_chars tracks the total number of characters in the ciphertext. num_chars comes into play in the final loop where the frequency counts get converted to a percentage.

FindMinDistShifts() finds the distribution with the smallest distance from the expected distribution using the Manhattan Distance metric previously described. The resulting KeyScoreMap will only have one shift key with a value set to one. The shift key with a value of one is the decryption key.

Lets look at an example. Suppose you encrypted this article using the key 42. Running the ciphertext through AsciiFrequencyAnalysisAttack() will return a KeyScoreMap with the following contents:

┌─────┬─────┐
│Key  │ Val │
├─────┼─────┤
│ 0   │ 0   │
├─────┼─────┤
│ ... │ 0   │
├─────┼─────┤
│ 86  │ 1   │
├─────┼─────┤
│ ... │ 0   │
├─────┼─────┤
│ 127 │ 0   │
└─────┴─────┘

The results of AsciiFrequencyAnalysisAttack() suggests the decryption key is 86. The plot below shows the expected ASCII frequency distribution versus the frequency distribution of the ciphertext post decryption using the key 86.

Frequency Plot

The distributions match up well. If you were to decrypt using the key 86, you would indeed get the correct plaintext! Why is the decryption key 86 and not 42? Recall that to decrypt you take the negative of the encryption key modulo the size of the alphabet. In this case, \(-42 \mod 128 = 86\).

Conclusion

The Caesar Cipher is a classic symmetric key crypto algorithm. The CC worked well in ancient times but doesn’t hold up so well in the age of computers. You can crack any CC code using a dictionary or frequency analysis attack. Neither attack is trivial. In the case of the dictionary attack, you need a valid dictionary to perform look ups on. The frequency analysis attack depends on knowledge of the expected distribution of alphabet characters. Regardless of its utility, the Caesar Cipher remains a fun algorithm to explore.

The complete project source with build instructions, usage, etc. is available on GitHub under caesar_cipher.

Algorithm Description#

Coding the Cipher#

Cracking the Code#

Dictionary Attack#

Frequency Analysis Attack#

Conclusion#