Code Breaking

Background

In classic cryptography there are two primary types of ciphers: substitution ciphers and transposition ciphers.

Substitution ciphers change, or substitute, characters within the message while transposition ciphers rearrange the characters in a message.

For example, a caesar cipher is a substitution cipher while reversing a message is a type of transposition cipher.

Given a sufficiently long encrypted text, we can determine whether the text was encrypted via a substitution or transposition cipher by using frequency analysis.

English letters are not uniformly distributed in text, some letters, such as $\text{'}$e$\text{'},$ occur more frequently than others, such as $\text{'}$z$\text{'}.$

The distribution below is the typical frequency of characters in English texts.

If an encrypted text has approximately this distribution, then it is more likely to have been encrypted using a transposition cipher than a substitution cipher, as transposition ciphers preserve the letter frequency.

Task

You have been given an implementation of a substitution cipher $($SubstitutionCipher$)$ and a transposition cipher $($TranspositionCipher$),$ you know that all messages were encrypted with one of these ciphers.

You must implement the getCipher and solve method of CodeBreaking. It must use frequency analysis to determine which cipher was used to encrypt the message.

Determine the number of times each lowercase letter $($excluding spaces and other punctuation$)$ occurs in the encrypted message.

Order the letters by their frequency and compare it with the reference frequency of "etaoinshrdlcumwfgypbvkkxqz".

If at least $5$ letters are in the same position as the reference frequency, decrypt using a transposition cipher, otherwise use a substitution cipher.

Example

$.$seicneuqerf thgir eht htiw txet elpmis a

Take the following string as our example: $.$seicneuqerf thgir eht htiw txet elpmis a

The letter frequency of this message is:

a: $1$

b: $0$

c: $1$

d: $0$

e: $6$

f: $1$

g: $1$

h: $3$

i: $4$

j: $0$

k: $0$

l: $1$

m: $1$

n: $1$

o: $0$

p: $1$

q: $1$

r: $2$

s: $2$

t: $5$

u: $1$

v: $0$

w: $1$

x: $1$

y: $0$

z: $0$

If we order the lower$-$case letters by the number of times they occur, we have "etihrsacfglmnpquwxbdjkovyz".

Comparing with the reference frequency of "etaoinshrdlcumwfgypbvkkxqz".

etihrsacfglmnpquwxbdjkovyz

etaoinshrdlcumwfgypbvkkxqz

$11000000001000000000010001$

We can see that $5$ characters are in the correct positions, so we would use a transposition cipher to decode the text.

d#vlpsoh#wh$\{$w#zlwk#wkh#uljkw#iuhtxhqflhv

Taking now the message d#vlpsoh#wh$\{$w#zlwk#wkh#uljkw#iuhtxhqflhv as our example.

If we perform a frequency analysis we will see that h occurs most frequently. It has the ordered frequency of "hwlkuvdfijopqstxzabcegmnry". This order has no characters in the correct position according to the reference frequency, so we use a substitution cipher to decode.

Hints

When constructing the ordered frequency of the message, ensure that all lower$-$case letters are represented. If two letters have the same frequency, sort alphabetically.

You may find the entrySet followed by a stream to sort useful.