# Cameron Lonsdale

Automating security and making it more accessible

# Cryptanalysis of Classical Ciphers with Multiple Encryption

Have you ever wondered how multiple encryption affects the security of the famous classical ciphers, Caesar, Substitution and Vigenère? Does encrypting plaintext multiple times improve, weaken or not affect the overall Cipher strength? The conclusion, unsurprisingly, is that multiple rounds of encryption are equivalent to encrypting the plaintext once. Here’s why.

# Caesar Cipher

The Caesar Cipher is a shift cipher where letters are replaced by those k along in the alphabet. When shifting our plaintext `EXAMPLE` by 5 we get `JCFRUQJ`. Shifting this ciphertext by 3 results in `MFIUXTM`. With the help of lantern this ciphertext can be decrypted.

The plaintext was successfully found by brute forcing keys between 0 and 25. The encryption key for this text was 8. Relating this back to our initial two encryption keys, 3 and 5, it is clear that 8 is the result of combining the two shifts together. No matter how many times the text is shifted it will always stay within the bounds of the alphabet and the resulting shift can be represented by a single value. Hence, multiple encryption of the Caesar Cipher is equivalent to a single encryption, meaning it can be broken using standard methods.

# Substitution Cipher

The Substitution Cipher extends the Caesar Cipher by allowing arbitrary letter replacements instead of shifting. Single encryption can be easily broken using letter frequency and dependencies.

Encrypt using the key: `VORJLFYIDUMQTNHGEWAXBCPSZK`

Encrypt again using key: `SAEYOCBPRNZKVGJQFXMILDTWUH`

Since the frequency of symbols does not change with multiple encryption, we should be able to decrypt double enciphered text easily.

The plaintext was found, our prediction was correct. Since only the symbols change and not their frequency, multiple rounds of encryption is equivalent to a single round with a different key. The final key can be determined by encrypting the key from the previous round using the key of the current round and continuing until completion. In our example above, `VORJLFYIDUMQTNHGEWAXBCPSZK` encrypted using `SAEYOCBPRNZKVGJQFXMILDTWUH` results in `DJXNKCURYLVFIGPBOTSWAEQMHZ`, our final key.

# Vigenère Cipher

The Vigenère Cipher is a periodic polyalphabetic substitution cipher, or in other words, it uses p many values to shift the plaintext, the same shift repeated every p letters. Since the frequency of symbols change with encryption it makes the ciphertext slightly harder to decrypt than Substitution. Once the period is known however, it is simply a matter of solving p many Caesar Ciphers. With multiple encryption there can be two variants, where all keys have the same period, and where the periods differ.

## Same Period

Encrypt using the key: `VXUH`

Encrypt again using key: `VTPM`

lantern successfully decrypted the multiple encrypted ciphertext with two keys of the same period. The period was found using standard methods and the entire text could be decrypted by solving p many Caesar Shifts. The final shift, represented by `BLSO` is the result of combing the shifts of `VXUH` and `VTPM`. This is intuitive to see using our understanding of how multiple encryption affects the key of a Caesar Cipher.

## Different Periods

As with the same period, different period multiple encryption is equivalent to encrypting the plaintext once. The keys are combined in the same way, the period of the final key however will vary.

The periods of the keys can have common factors or they can be Relatively prime (numbers where the only positive common factor is 1). Either way, the resulting period of the final encryption key is determined by the least common multiple of all the key periods.

When encrypting using `DMZU` then `XG` results in the key `AWSA`. This is easy to see as `XG` can become `XGXG` without changing the encryption, we then have a multiple encryption with the same period. The least common multiple of 4 and 2 is 4, which is the length of our final key. `AWSA` can be determined by encrypting `DMZU` with the key `XGXG`.

When encrypting with `HJC` then `SLOZ` the final key is `ZUQGBNVIUSXB`. The least common multiple of 3 and 4 is 12. This can be understood visually if you imagine the keys `HJC` and `SLOZ` overlapping as they encrypt a piece of text. `SLOZ` is not a multiple of 3, hence multiple repetitions of the key are needed until we reach a length where both keys start again from the same letter. When they start again, we have a repeating pattern that represents the key that can express the multiple encryption as a single encryption.

```| H   J   C | H   J   C | H   J   C | H   J   C |
| S   L   O   Z | S   L   O   Z | S   L   O   Z |
```

This pattern will repeat every 12 letters, hence the encryption from plaintext to final ciphertext can be represented by a single encryption using a key of period 12. The resultant key `ZUQGBNVIUSXB` is found by encrypting `HJCHJCHJCHJC` with the key `SLOZSLOZSLOZ`.