Introduction To Codes, Ciphers, & Codebreaking
by Greg Goebel

1.2] SIMPLE SUBSTITUTION CIPHERS
* A simple substitution cipher in which the same cipher letter is always exchanged for the same plaintext letter is known as a "monoalphabetic substitution cipher". For example, we could define a cipher alphabet as follows:

plaintext alphabet: abcdefghijklmnopqrstuvwxyz
ciphertext alphabet: TDNUCBZROHLGYVFPWIXSEKAMQJ

Given the plaintext:
erase the tapes

-- and the cipher alphabet above, we get:
CITXC SRC STPCX

Note that in this example plaintext is printed in lowercase, while ciphertext is printed in uppercase. This convention will be followed in the rest of this document.
Monoalphabetic substitution ciphers go back to at least the fourth century BC. The Hindu text for the instruction of women known as the KAMA-SUTRA written at the time describes ciphers as one of the 64 arts that a woman should know, for arranging discreet meetings with a lover. Use of ciphers for military purposes goes back at least to Julius Ceasar, who was skilled in their use. One of the simplest monoalphabetic substitution ciphers, known as a "Ceasar shift", involves shifting letters by a number of positions, say three:

plaintext alphabet: abcdefghijklmnopqrstuvwxyz
cipher alphabet: XYZABCDEFGHIJKLMNOPQRSTUVW

Using this cipher alphabet, Alice can convert the plaintext:
beware the ides of march

-- into the ciphertext:
YBTXOB QEB FABP LC JXOZE

This can be made even more cryptic by removing the spaces:
YBTXOBQEBFABPLCJXOZE

-- and it still remains more or less readable when translated back to plaintext:
bewaretheidesofmarch

With 26 letters in the English alphabet, there are of course 25 different possible Ceasar shift cipher alphabets. All Bob needs to read the cipher is a number from 1 to 25 to define the shift. This number can be thought of as a "key" associated with the Ceasar shift enciphering "algorithm".

top>

 

A Ceasar shift cipher is ridiculously easy to crack. All Holmes has to do is try all 25 Ceasar shift cipher alphabets until one works. Interestingly, however, it is still in use, in the form of the "rot13" scheme used on Internet newsgroups. This is a simple 13-place Ceasar-shift cipher implemented by the newsgroup reader software, with the user performing encryption and decryption with the press of a button.

Since anyone could crack a Ceasar shift cipher, this scheme is not used for security. It is often used as a means of posting dirty jokes or similar materials that could cause offense, prefaced with a plaintext disclaimer stating that the contents may be offensive. It is also sometimes used to conceal punchlines and the answers to puzzles and riddles so the reader will not see the answer immediately.

* A more secure way to build a substitution cipher is to completely mix up the mappings between the plaintext and ciphertext alphabets. The number of possible ways to rearrange the 26 letters of the alphabet is:

26 * 25 * 24 * ... * 2 * 1 = 26! = 4.03E26

That is, there are 26 possibilities for the selection of the first letter, and for each of these 26 possibilities there are 25 possibilities for the second letter, then 24 possibilities for the third, and so on in an expanding tree of possibilities. If you're not familiar with a term of the form "26!", it just means 26 multiplied times all the integer numbers less than it down to one, and is called a "factorial".
This large number of possible monoalphabetic substitution cipher alphabets means that if such a "mixed cipher alphabet" is used, cracking it with a brute-force attack is very difficult.

One way to come up with a mixed cipher alphabet is for Alice to take a key phrase consisting of, say, a name, such as RICHARD MILHAUS NIXON, write it down while eliminating any redundant letters, and then complete the cipher by writing down the remaining letters of the alphabet in alphabetical order:

plaintext alphabet: abcdefghijklmnopqrstuvwxyz
cipher alphabet: RICHADMLUSNXOBEFGJKPQTVWYZ

This is a simple cipher algorithm, but even if a codebreaker knows that this general scheme was used, the message still cannot be read without the key, and a brute-force approach to cracking it is very difficult. This is a fundamental principle of cryptography, stated by a 19th-century Dutch linguist & cryptographer, Auguste Kerckhoffs von Niewenhof (1835:1903), and known as "Kerckhoffs' Principle": The security of a cipher should not depend on an enemy's ignorance of the enciphering algorithm, only the enemy's ignorance of the key. In fact, codebreaking is often focused on discovering keys, since the cipher scheme may be well understood.

1 2 3 4 5 6 next>