Caesar Groups

Consider the ciphertext \(\text{ABCDEFGHIJK}\). Suppose it was encrypted with a Vigenère key of length \(3\), written \(\alpha \beta \gamma\). Starting with the first character, every third character was encrypted using the Caesar key \(\alpha\). Similarly, every third character starting with the second was encrypted with \(\beta\), and every third character starting with the third was encrypted with \(\gamma\).

\[\begin{split} \begin{array}{rccccccccccc} \texttt{ciphertext:} & \text{A} & \text{B} & \text{C} & \text{D} & \text{E} & \text{F} & \text{G} & \text{H} & \text{I} & \text{J} & \text{K} \\ \texttt{Caesar key:} & \alpha & \beta & \gamma & \alpha & \beta & \gamma & \alpha & \beta & \gamma & \alpha & \beta \end{array} \end{split}\]

Call the ciphertext characters encrypted using the same position in the repeating Vigenère key a Caesar group. Each group uses a single Caesar key, even if that key also appears in another position of the Vigenère key. In the example above, there are three Caesar groups:

  • The Caesar group corresponding to \(\alpha\) is \(\text{ADGJ}\).

  • The Caesar group corresponding to \(\beta\) is \(\text{BEHK}\).

  • The Caesar group corresponding to \(\gamma\) is \(\text{CFI}\).

If the Vigenère key instead had length \(4\), there would be four Caesar groups.

\[\begin{split} \begin{array}{rccccccccccc} \texttt{ciphertext:} & \text{A} & \text{B} & \text{C} & \text{D} & \text{E} & \text{F} & \text{G} & \text{H} & \text{I} & \text{J} & \text{K} \\ \texttt{Caesar key:} & \alpha & \beta & \gamma & \delta & \alpha & \beta & \gamma & \delta & \alpha & \beta & \gamma \end{array} \end{split}\]

  • The Caesar group corresponding to \(\alpha\) is \(\text{AEI}\).

  • The Caesar group corresponding to \(\beta\) is \(\text{BFJ}\).

  • The Caesar group corresponding to \(\gamma\) is \(\text{CGK}\).

  • The Caesar group corresponding to \(\delta\) is \(\text{DH}\).

Problem 1

Write a function named caesar_groups() that accepts a ciphertext string and a positive integer \(K\) (the length of the Vigenère key used to encrypt the ciphertext). Return a list of the \(K\) Caesar groups, each represented as a single string, in the order of their corresponding key positions.

Test Cases

print(caesar_groups("ABCDEFGHIJK", 2))
print(caesar_groups("ABCDEFGHIJK", 3))
print(caesar_groups("ABCDEFGHIJK", 4))

['ACEGIK', 'BDFHJ']
['ADGJ', 'BEHK', 'CFI']
['AEI', 'BFJ', 'CGK', 'DH']

Each Caesar group was encrypted with a single Caesar key, its key can be found by trying all 26 possibilities, \(\text{A}\)–\(\text{Z}\). Unlike an ordinary Caesar cipher, though, a correctly decrypted Caesar group generally does not form readable text: decrypting the group \(\text{AEI}\) above with the correct key yields only the first, fifth, and ninth letters of the plaintext. However, these letters are still a sample of English text. For a sufficiently large group, the correct decryption should have letter frequencies that resemble those of general English, while decrypting it with an incorrect key should not.

Problem 2

Write a function named letter_frequency() that accepts a string representing a decrypted Caesar group (perhaps with the correct key, perhaps not). Return a NumPy array of length 26 whose entry at index \(i\) is the fraction of characters in the string that equal the letter at index \(i\) of the alphabet (index 0 for A, index 1 for B, and so on).

Reminder: s.count(sub) returns the number of times the substring sub occurs in the string s.

Test Cases

print(letter_frequency("AB"))
print(letter_frequency("AAAAAAABZZ"))
print(letter_frequency("THEQUICKBROWNFOXJUMPSOVERTHELAZYDOG"))

[0.5 0.5 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.
 0.  0.  0.  0.  0.  0.  0.  0. ]
[0.7 0.1 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.
 0.  0.  0.  0.  0.  0.  0.  0.2]
[0.02857143 0.02857143 0.02857143 0.02857143 0.08571429 0.02857143
 0.02857143 0.05714286 0.02857143 0.02857143 0.02857143 0.02857143
 0.02857143 0.02857143 0.11428571 0.02857143 0.02857143 0.05714286
 0.02857143 0.05714286 0.05714286 0.02857143 0.02857143 0.02857143
 0.02857143 0.02857143]