Substitution Ciphers

Substitution (Cipher)

Substitution: each element in plaintext is mapped into another

Link to original

Some simple ciphers include:

• ROT13: shift each letter by $k$ places
• Alphanumeric: substitute numbers for letters

Caeser cipher

Caeser Cipher

Caesar cipher: each plaintext character is replaced by character $3$ to the right modulo $26$ Equivalent to ROT13 with key of $3$.

Brute-force cryptanalysis is possible as:

1. the encryption and decryption algorithms are known
2. only 25 keys to try
3. language of plaintext is known and easily recognisable

Link to original

Mono-alphabetic substitution ciphers

Mono-alphabetic substitution cipher

A mono-alphabetic cipher (aka simple substitution cipher) is a substitution cipher where each letter of the plain text is replaced with another letter of the alphabet.

Link to original

Strength of mono-alphabetic substitution ciphers

The key idea is to generalise the Caeser cipher by allowing an arbitrary substitution. If the “cipher” line of a Caesar cipher can be any permutation of the 26 alphabetic characters, then there are $26!$ possible keys. However, this is still easy to crack using frequency analysis (letters, digram, etc).

Link to original

Definition of mono-alphabetic substitution ciphers

Mathematical definition of mono-alphabetic substitution ciphers

• Let $\mathcal{K}$ be the set of all permutations of the alphabet $\mathcal{A}$. Define for each $e\in \mathcal{K}$ an encryption transformation $E_e$ on strings $m=m_1{m}_2\dots m_n\in \mathcal{M}$ as $E_e(m)=e(m_1)e(m_2)\dots e(m_n)=c_1{c}_2\dots c_n=c$
• To decrypt $c$, compute the inverse permutation $d=e^{-1}$ and $D_d(c)=d(c_1)d(c_2)\dots d(c_n)=m$
• $E_e$ is a mono-alphabetic substitution cipher

Link to original

Homophonic substitution ciphers

Homophonic substitution cipher

Mono-alphabetic ciphers are easy to break because they reflect frequency data of the original alphabet. In homophobic substitution ciphers, we instead provide multiple substitutes (homophones) for a single letter to make frequency analysis more difficult.

Link to original

Definition of homophobic substitution cipher

Mathematical definition of homophonic substitution ciphers

• To each $a\in \mathcal{A}$ associate a set $H(a)$ of strings of $t$ symbols, where $H(a)$, $a\in \mathcal{A}$ are pairwise disjoint.
• Replace each $a$ with a randomly chosen string from $H(a)$. To decrypt a string $c$ of $t$ symbols, one must determine an $a\in \mathcal{A}$ such that $c\in H(a)$.
• The key for the cipher is the sets $H(a)$.

Link to original

Strength of homophonic substitution ciphers

For example, given $\mathcal{A}=\{x,y\}$, $H(x)=\{00,10\}$, and $H(y)=\{01,11\}$. The plaintext $xy$ would encrypt to one of $0001,0011,1001,1011$.

However in this cipher, multiple-letter patterns still survive in the ciphertext as each element of plaintext affects only one element of ciphertext. We look at two methods to lessen extent to which the structure survives in the ciphertext: Playfair cipher and Vigenère cipher.

Link to original

Playfair cipher

Playfair cipher

In the Playfair cipher, we encrypt multiple letters of the plaintext. We use a 5x5 matrix of letters constructed using a keyword.

1. Construct matrix by filling it with the letters of the keyword (minus the duplicates) from left to right and top to bottom. Then fill remaining letters in alphabetic order, where I and J count as one letter.
2. Plaintext is encrypted two letters at a time:
   • If a pair is a repeated letter, we insert a filler character. “BALLOON” $⇝$ “BA LX LO ON”
   • If both letters fall in the same row, replace each letter with letter to right, wrapping back to start from end. (“AR” is encrypted as “RM”)
   • If both letters fall in the same column, replace each with letter below it, wrapping to top from bottom. (“MU” is encrypted as “CM”)
   • Otherwise, each letter is replaced by the letter in the same row and in the column of the other letter of the pair. (“HS” => “BP”, “EA” => “IM”/“JM”)
3. To decrypt, use inverse of rules 2 and 3, and using 1st and 4th rules as-is.

Link to original

Polyalphabetic substitution ciphers (Vigenère cipher)

Polyalphabetic substitution cipher

In a Polyalphabetic substitution cipher, we use different mono-alphabetic substitutions as one proceeds through the plaintext message. Two general features common to all such ciphers are:

• A set of related mono-alphabetic substitution rules is used.
• A key determines which particular rule is chosen for a given transformation.

Link to original

Vigenère cipher

A well-known polyalphabetic substitution cipher is the Vigenère cipher.

• Set of related mono-alphabetic substitution rules consists of the 26 Caeser ciphers with shifts of $0$ through $25$.
• Each cipher is denoted by a key letter, which is the ciphertext letter that substitutes for the plaintext letter $A$.

Link to original

Definition of Vigenère cipher

Mathematical definition of Vigenère cipher

Assume a sequence of plaintext letters $P=p_0,p_1,p_2,\dots ,p_{n-1}$ and a key consisting of the sequence of letters $K=k_0,k1,k_2,\dots ,k_{m-1}$. Where $m$ typically is smaller than $n$.

A sequence of ciphertext letters:

$$\begin{array}{rl}C& =C_0,C_1,C_2,\dots ,C_{n-1}\\ & =E(K,P)\\ & =E((k_0,k_1,k_2,\dots ,k_{m-1}),(p_0,p_1,p_2,\dots ,p_{n-1}))\\ & =(p_0+k_0)\text{ mod }26,(p_1+k_1)\text{ mod }26,\dots \\ & \\ C_i& =(p_i+k_{i\text{ mod }m})\text{ mod }26\end{array}$$

For decryption, $p_i=(C_i-k_{i\text{ mod }m})\text{ mod }26$.

Link to original

Strength of polyalphabetic substitution ciphers

The caveat is that we do need a key as long as the message (so we usually just repeat a keyword). In terms of strength, we have multiple ciphertext letters for each plaintext letter, one for each unique letter of the keyword so letter frequency information is obscured. However, not all knowledge of plaintext structure is lost.

Link to original

Vernam cipher

Vernam cipher

The Vernam cipher is a system where the keyword is as long as the plaintext and has no statistical relationship to it. We work on binary data (bits) rather than letters using XOR:

$$\begin{array}{rl}0\oplus 0& =0\\ 0\oplus 1& =1\\ 1\oplus 0& =1\\ 1\oplus 1& =0\end{array}$$

XOR can be used as a poly-alphabetic cipher:

$$\begin{array}{rl}P\oplus K& =C\\ C\oplus K& =P\end{array}$$

This is the basis of the idea of the Vernam cipher, we use a long running loop of tape that eventually repeats the key (very long but repeating keyword). Ciphertext is generated by bitwise XOR of plaintext and key, decryption is the same bitwise operation.

$$\begin{array}{rl}{c}_i& =p_i\oplus k_i\\ p_i& =c_i\oplus k_i\\ & \\ \text{where }{p}_i/c_i/k_i& =i^{\text{th}}\text{ binary digit of plaintext/ciphertext/key}\end{array}$$

Link to original

One-time pad

One-time Pad

One-time pad: given any plaintext, the key is a string of equal length to the message. We use a self-inverting function such as XOR, $C$ transforms each $s_i$ into $s_i\oplus k_i$. Capable of perfect secrecy but requires a large amount of key material and key distribution is a big problem.

One-time pad is an improvement to the Vernam cipher except:

• we use a truly random key that is as long as the message, so the key need not be repeated
• we use the key to encrypt and decrypt a single message, then we discard it

Each new message $P$ requires a new key of the same length as $P$. Produces random output with no statistical relation to plaintext.

It is unbreakable: $C$ contains no information whatsoever about $P$. This is the only cryptosystem that exhibits perfect secrecy.

Link to original

Strength of one-time pad

There are two fundamental practical problems:

• Large quantities of random keys
• Key distribution and protection, where for every message to be sent, a key of equal length is needed by both sender and receiver

This means this has limited utility and is usually only useful for low-bandwidth channels which require very high security.

Link to original

Transposition Ciphers

Transposition (Cipher)

Transposition: elements in plaintext are rearranged (some permutation is performed)

Link to original

Mathematical formalisation of transposition ciphers

Formally:

• For block length $t$, let $\mathcal{K}$ be the set of permutations on $\{1,\dots ,t\}$. For each $e\in \mathcal{K}$ and $m\in \mathcal{M}$: $$E_e(m)=m_{e(1)}{m}_{e(2)}\dots m_{e(t)}$$
• The set of all such transformations is called a transposition cipher.
• To decrypt $c=c_1{c}_2\dots c_t$ compute $D_d(c)=c_{d(1)}{c}_{d(2)}\dots c_{d(t)}$, where $d$ is inverse permutation.
• Letters unchanged so one can exploit frequency analysis for dipthongs, tripthongs, words, etc.

Link to original

Rail fence cipher

Rail fence cipher

The rail fence cipher is where we write down plaintext as a sequence of diagonals and then read off as a sequence of rows.

Example

To decrypt: reconstruct the diagonal grid used to encrypt the message

• Start by making a grid with as many rows as the key is, and as many columns as the length of the ciphertext
• Place the first letter in the the top left square, and dashes diagonally downwards where the letters will be
• When we get back to the top row, we place the next letter in the ciphertext
• Continue like this across the row, and start the next row when you reach the end

Link to original

Rotating (turning) grilles

16th century Cardano grille

Use a mask (“grille”) with precut holes. The encoder writes plaintext in holes, removes mask, fills remainder with blind text, retaining appearance of an innocuous message. To decrypt, the recipient must posses an identical mask or know the spacing that created it.

Essentially, skipping letters within an otherwise plausible ciphertext.

This is an example of steganography, but provides a basis for transposition.

Grille

Grille: a sheet with a grid of squares, some of which are cut out. We can use it to write plaintext into a grid by rotating the grille and writing left to right until all cells have been filled, then we can read the ciphertext from the grid without the grille.

Link to original

Example

Multiple-stage columnar transposition cipher

Columnar transposition cipher

In a columnar transposition cipher, we write a message in a rectangle, row by row, and read message off, column by column, but permute the order of the columns. The order of the columns is the key to the algorithm.

Link to original

A pure transposition cipher is easily recognised and attacked: ciphertext has same letter frequencies as original plaintext.

Multiple-stage columnar transposition cipher

A transposition cipher (columnar or not) can be made significantly more secure by performing more than one stage of transposition, i.e. a multiple-stage columnar transposition cipher. Which results in a more complex permutation that is not easily reconstructed.

Link to original

Example: Multiple-stage Columnar Transposition Cipher