Shift Cipher | Sahithyan's Notes

Encryption replaces each letter in the alphabet by a letter located at a specific fixed distance from that letter.

c = m + k \mod 26

Here:

$m$ : plaintext letter, encoded as an integer 0 (a) to 25 (z)
$k$ : the shift value, the secret key

Viewed as a stream cipher, a stream of plaintext characters $m_i$ and a stream of keys $k_i$ are input to $c_i = m_i + k_i \mod 26$ , producing a stream of ciphertext characters $c_i$ . The shift cipher’s keystream is a repeating sequence of just one key value $k$ .

Breaking the Shift Cipher

The shift cipher has only 26 possible keys, so an attacker can try each in turn until the correct plaintext is recognized. This is called an exhaustive key search attack.

Character frequency analysis computes the frequency of characters in the ciphertext and matches it against the standard character frequency table of the language.

Replace the highest frequency ciphertext characters with the corresponding plaintext characters by frequency rank.
The 6 most frequent English characters account for approximately 44.4% of characters in a block of text, so the correct key is usually found quickly.
Trial and error over different orderings of characters may be needed to find the correct key.

A more rigorous technique computes the statistical distance between the standard character frequency distribution and the ciphertext’s frequency distribution, for each candidate shift $k$ .

\Delta[X, Y_k] = \frac{1}{2}\sum_{u \in V} \left| \Pr_{X \leftarrow D_{\text{standard}}}[X = u] - \Pr_{Y_k \leftarrow D_k}[Y_k = u] \right|

Here:

$X$ : random variable distributed according to the standard character frequency
$Y_k$ : random variable distributed according to the shift $k$
$V$ : the set of values which can occur for $X$ or $Y_k$ with non-zero probability

Computing $\Delta[X, Y_k]$ for each of the 26 values of $k$ and taking the smallest value gives the secret key.