Shift Cipher | Sahithyan's Notes

A classical cipher, mono-alphabetic cipher. Every letter is shifted by the same amount, so plaintext letter frequencies are preserved in the ciphertext.

You can find an implementation of the shift cipher in sahithyandev/ciphers.

Encryption

Each letter in the alphabet is replaced by a letter located at a fixed distance from it.

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$ .

Decryption

Each letter is shifted back by the same key $k$ .

m = c - k \mod 26

Attacking

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.

Worked Example

Plaintext bazinga under $k = 3$ , with $a = 0$ to $z = 25$ .

Each letter adds $3$ modulo $26$ .

$b (1) + 3 = 4 = e$
$a (0) + 3 = 3 = d$
$z (25) + 3 = 2 = c$
$i (8) + 3 = 11 = l$

Ciphertext is edclqjd.

Decryption subtracts $3$ modulo $26$ .

$e (4) - 3 = 1 = b$
$d (3) - 3 = 0 = a$

Plaintext is bazinga.

The exhaustive attack tries the 26 keys in turn against edclqjd.

$k = 1$ gives dcbkpic, not language.
$k = 2$ gives cbajohb, not language.
$k = 3$ gives bazinga, recognised as language. Key is $3$ .