Character Ciphers and Block Ciphers

A cipher takes a message (the plaintext) and encodes it --- puts it in a form (the ciphertext) where the information in the message is not obvious upon inspection. The recipient of the message takes the ciphertext and decodes it --- performs an operation which recovers the plaintext from the ciphertext.

Example. (A shift cipher) This is also known as a Caesar cipher, since it was supposedly used by Julius Caesar.

The letters of the alphabet will be represented by the numbers 0, ..., 25:

$A = 0, B = 1, C = 2, \ldots, Z = 25.$

If x is a letter, I'll encode it using

$y = x + 11 \mod{26}.$

(I could use any nonzero number from 1 to 25 in place of 11.) The formula above replaces each letter with another letter; in effect, the alphabet gets "shifted" 11 places to the left.

The translation table for this cipher is:

$\matrix{\hbox{A} & \hbox{B} & \hbox{C} & \hbox{D} & \hbox{E} & \hbox{F} & \hbox{G} & \hbox{H} & \hbox{I} & \hbox{J} & \hbox{K} & \hbox{L} & \hbox{M} & \hbox{N} & \hbox{O} & \hbox{P} & \hbox{Q} & \hbox{R} & \hbox{S} & \hbox{T} & \hbox{U} & \hbox{V} & \hbox{W} & \hbox{X} & \hbox{Y} & \hbox{Z} \cr \hbox{L} & \hbox{M} & \hbox{N} & \hbox{O} & \hbox{P} & \hbox{Q} & \hbox{R} & \hbox{S} & \hbox{T} & \hbox{U} & \hbox{V} & \hbox{W} & \hbox{X} & \hbox{Y} & \hbox{Z} & \hbox{A} & \hbox{B} & \hbox{C} & \hbox{D} & \hbox{E} & \hbox{F} & \hbox{G} & \hbox{H} & \hbox{I} & \hbox{J} & \hbox{K} \cr}$

(a) Use this cipher to encrypt the message

$\hbox{I WAS ASLEEP AT THE TIME}$

(b) Find the decoding transformation for this cipher.

"I" is replaced by "T", "W" by "H", and so on. I get the ciphertext

$\hbox{T HLD LWDPPA LE ESP ETXP}$

I'll group the letters into 5-letter words to hide the original word groupings:

$\hbox{THLDL DWPPA LEESP ETXPZ}$

I've thrown in an extra "Z" at the end to make the last group come out evenly. If you decode the message, you'd get

$\hbox{IWASA SLEEP ATTHE TIMEO}$

You can see that the 5-letters grouping and the extra "Z" did no harm, since it's evident what the plaintext was.

(a) Solve the equation $y = x + 11 \mod{26}$ x:

$x = y + 15 \mod{26}.$

This equation is the decoding transformation; it's equivalent to reading the translation table backward.

Example. Consider the shift cipher

$y = x + 19 \mod{26}.$

Use it to encrypt the message "I MUST HAVE FOOD".

The encrypted message is "B\ FNLM\ ATOX\ YHHW".

I wrote a computer program to do this. There are only 26 possible shifts, so if you wanted to decode this by brute force, you could feed the ciphertext through 26 shift programs and see which one produced a sensible message. Shift ciphers are not of much use when it comes to protecting secrets!

The next thing to try is an affine transformation:

$y = a x + b \mod{26}, \quad\hbox{where}\quad (a, 26) = 1.$

I need the last condition in order to ensure that I can decode messages. This is equivalent to being able to invert the transformation. Now if , then a is invertible mod 26, so

$x = a^{-1} (y - b) \mod{26}.$

This equation can be used to decode messages.

Example. Consider the transformation $y = 5 x + 14 \mod{26}$ .

(a) Encrypt the plaintext "WHEN WILL I BECOME A FISH".

(b) Find the decoding transformation.

(a) Here's the translation table:

$\matrix{\hbox{A} & \hbox{B} & \hbox{C} & \hbox{D} & \hbox{E} & \hbox{F} & \hbox{G} & \hbox{H} & \hbox{I} & \hbox{J} & \hbox{K} & \hbox{L} & \hbox{M} & \hbox{N} & \hbox{O} & \hbox{P} & \hbox{Q} & \hbox{R} & \hbox{S} & \hbox{T} & \hbox{U} & \hbox{V} & \hbox{W} & \hbox{X} & \hbox{Y} & \hbox{Z} \cr \hbox{O} & \hbox{T} & \hbox{Y} & \hbox{D} & \hbox{I} & \hbox{N} & \hbox{S} & \hbox{X} & \hbox{C} & \hbox{H} & \hbox{M} & \hbox{R} & \hbox{W} & \hbox{B} & \hbox{G} & \hbox{L} & \hbox{Q} & \hbox{V} & \hbox{A} & \hbox{F} & \hbox{K} & \hbox{P} & \hbox{U} & \hbox{Z} & \hbox{E} & \hbox{J} \cr}$

The ciphertext is "UXIB\ UCRR\ C\ TIYGWI\ O\ NCAX".

(b) Solve for x in terms of y:

$\eqalign{ y & = 5 x + 14 \mod{26} \cr y + 12 & = 5 x \mod{26} \cr 21(y + 12) & = 21 \cdot 5 x \mod{26} \cr 21 y + 18 & = x \mod{26} \cr} \quad\halmos$

Example. Consider the following affine cipher:

$y = 8 x + 7 \mod{26}.$

Find two plaintexts (input letters) that produce the same ciphertext (output letter).

I can produce two inputs that give the same output by finding two inputs that make " " equal to 0 mod 26. One such value is 0; I can produce another by using 13, since $8 \cdot 13 = 104 = 0 \mod{26}$ .

$8 \cdot 0 + 7 = 7 \mod{26}, \quad 8 \cdot 13 + 7 = 7 \mod{26}.$

The inputs are (which is "A") and (which is "N").

This isn't a very good affine cipher, since you can't construct a decoding transformation.

Shift ciphers and affine transformation ciphers are called substitution or character ciphers because each letter is replaced by another letter. They're simple to use, but relatively easy to crack. For example, with any reasonably large message you can count the letters in the ciphertext and guess the substitution using frequency tables for letters in the English language.

As a partial remedy to frequency analysis, you might think of enciphering blocks of k letters at a time. To do this, encode letters as number from 0 to 25 in the usual way. Consider a block of k letters $a_1 a_2 \ldots a_k$ . As the cipher key, choose a $k \times k$ matrix M which is invertible mod 26. (M will be invertible mod 26 if $\det M$ is relatively prime to 26.) Then the cipher transformation is $\vec c = M \vec a \mod{26}$ , i.e.

$\left[\matrix{c_1 \cr c_2 \cr \vdots \cr c_k \cr}\right] = M \left[\matrix{a_1 \cr a_2 \cr \vdots \cr a_k \cr}\right] \mod{26}.$

You can decipher messages using $\vec a = M^{-1} \vec c \mod{26}$ .

Example. (a digraphic cipher) Consider the cipher

$\left[\matrix{c_1 \cr c_2 \cr}\right] = \left[\matrix{5 & 3 \cr 2 & 3 \cr}\right] \left[\matrix{p_1 \cr p_2 \cr}\right] \mod{26}.$

(a) Encode the message "SPICY MEATBALLS".

(b) Find the decoding transformation.

(a) Break the message up into two-letter groups and convert them to 2-dimensional vectors:

$\matrix{\hbox{SP} & \hbox{IC} & \hbox{YM} & \hbox{EA} & \hbox{TB} & \hbox{AL} & \hbox{LS} \cr (18, 15) & (8, 2) & (24, 12) & (4, 0) & (19, 1) & (0, 11) & (11, 18) \cr}$

Finally, use M to encode each vector. For example,

$\left[\matrix{5 & 3 \cr 2 & 3 \cr}\right] \left[\matrix{18 \cr 15 \cr}\right] = \left[\matrix{5 \cr 3 \cr}\right] \mod{26}.$

$(5, 3) = \hbox{FD}$ , so the first two letters of the ciphertext are "FD".

Continuing in this way, you obtain the ciphertext

$\hbox{FD UW AG UI UP HH FY}\quad\halmos$

(b) Let

$M = \left[\matrix{5 & 3 \cr 2 & 3 \cr}\right].$

Since $\det M = 9$ and , M is invertible mod 26. In fact,

$M^{-1} = 9^{-1} \left[\matrix{3 & -3 \cr -2 & 5 \cr}\right] = 3 \cdot \left[\matrix{3 & 23 \cr 24 & 5 \cr}\right] = \left[\matrix{9 & 17 \cr 20 & 15 \cr}\right].$

(Note that $\dfrac{1}{9} = 9^{-1} = 3$ , because $3 \cdot 9 = 1 \mod{26}$ .)

The decoding transformation is

$\left[\matrix{p_1 \cr p_2 \cr}\right] = \left[\matrix{9 & 17 \cr 20 & 15 \cr}\right] \left[\matrix{c_1 \cr c_2 \cr}\right] \mod{26}.\quad\halmos$

Example. Consider the following block cipher:

$\left[\matrix{x \cr y \cr}\right] = \left[\matrix{5 & 7 \cr 3 & 5 \cr}\right] \left[\matrix{u \cr v \cr}\right] \mod{26}.$

Find two different inputs and which produce the same output.

I'll find two different inputs which produce the same output . One such input is .

To find another, do the matrix multiplication and write out the two equations:

$\eqalign{ 5 u + 7 v & = 0 \cr 3 u + 5 v & = 0 \cr}$

I can get a (nonzero) solution to the first equation by "switching and negating":

$5 \cdot 7 + 7 \cdot (-5) = 0 \mod{26}, \quad\hbox{or}\quad 5 \cdot 7 + 7 \cdot 21 = 0 \mod{26}.$

I try in the second equation:

$3 \cdot 7 + 5 \cdot 21 = 126 = 22 \mod{26}.$

I didn't get 0, but since 22 has a factor of 2, I can get 0 by multiplying everything by 13:

$13 \cdot (7, 21) = (91, 273) = (13, 13) \mod{26}.$

This still satisfies $5 u + 7 v = 0 \mod{26}$ .

Thus, and are two inputs which give the same output. This shows that this block cipher is a poor cipher, since you won't be able to construct a decoding transformation.

Contact information

Bruce Ikenaga's Home Page