Cryptographic algorithms can be categorized into two major branches: transposition and substitution. In transposition, the letters of the plaintext are rearranged to create the ciphertext. In substitution, each letter or symbol in the plaintext is systematically replaced, or substituted by, another letters in the ciphertext alaphbet.
As you can see in the example above, transposition is not very secure for short words, because there aren't very many ways to rearrange a 4 letter word. For example, the word math can only be rearranged 24 ways:
MATH, MAHT, MHAT, MHTA, MTAH, MTHA, AHMT, AHTM, AMHT, AMTH, ATHM, ATMH, TAHM, TAMH, THAM, THMA, TMAH, TMHA, HAMT, HATM, HMAT, HMTA, HTAM, HTMA
all of which look a lot like the ciphertext word
MATH. For short messages, transposing the letters does not provide much security since the plaintext can easily be guessed from the ciphertext. In fact there are many puzzle games, sucha as word jumbles, that essentially ask the player to break simple ciphertexts that were created using a transposition cipher.
However, as we increase the number of letters in our message, the possible rearrangements grows incredibly quickly. For example, consider this short sentence. It has 35 letters, and therefore $35! = 10,333,147,966,386,144,929,666,651,337,523,200,000,000$ rearrangements of them, of which over $50,000,000,000,000,000,000,000,000,000,000$ are unique. If one person could check one arrangement per second, and if all the people in the world worked non-stop, it would take more than a thousand times the lifetime of the universe to check all the possibilities. What we can learn from this is that while transposition can be incredibly powerful at hiding your secret from enemy eavesdroppers, but without a simple procedure for the recipient to follow, it makes it incredibly difficult to decipher.
There are many ways to rearrange the letters in message, some easy and some difficult, and we'll explore more of them in the next chapter.
In transposition each letter keeps its identity (e.g. an
a remains an
a), but changes its position. In substitution, each letter can change its identity but retains its position. The warm-up activity in this module is an example of a substitution cipher, where each letter of the plaintext was exchanged for a different letter.
The first documented use of a substitution cipher for military purposes appear in Julius Caesar's Gallic Wars. When choosing how to assign each letter in the plaintext to a letter in the ciphertext, Caesar did not do so at random, but instead replaced each letter in the plaintext with the letter a set number of places further down the alphabet.
plain alphabet: a b c d e f g h i j k l m n o p q r s t u v w x y z cipher alphabet D E F G H I J K L M N O P Q R S T U V W X Y Z A B C
When placed alongside each other, it is easy to see that the cipher alphabet is simply the plain alphabet shifted 3 places down. When there is not a letter 3 places down the way, for example plaintext letter
x, you wrap back around to the beginning to find the letter
A. In this example, the key is the value 3, as it tells the sender and recipient all the needed information to encipher and decipher the message, as long as they both already know the Caesar Shift method will be used.
An example of this method being used:
key: 3 plaintext: be yourself; everyone else is already taken. ciphertext: EHBRX UVHOI HYHUB RQHHO VHLVD OUHDG BWDNHQ
There are many other ways to determine the mapping between plaintext letters and ciphertext letters, some more mathematical than others, which will be explored in a future chapter.
Regardless of which type of encryption you use, either transposition, substitution, or other types not yet discussed, it is only considered to be valid method if it satisfies the following properties:
- It should be easy to encrypt the message
- It should be easy to transmit the message
- It should be easy to decode the message
- It must be possible to communicate and remember the key without using written notes
- The method need not be secret to guarantee security (no security through obscurity)
- If someone intercepts the message, it should be very hard for them to decipher it
and once we've learned about more modern encryption methods, we should add:
- The source of the message must be easily verifiable so a third party can't replace the intended message with one of their own
These guidelines are adapations of Kerckhoff's Principles, which were developed in the late 19th century as mathematical encryption became more prevalent in military application.