1.2. Types of Cryptography#

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.

figure01

Transposition#

Transposition is not very secure for short words. Short words have few ways to rearrange their letters. 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 the rearrangements look similar to the 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, such as word jumbles, that ask the player to break simple transposition ciphertexts.

As you increase the number of letters in a 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 you can learn from this is that while transposition can be incredibly powerful at hiding your secret from enemy eavesdroppers, without a simple procedure for the recipient to follow, it makes a message 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.

Substitution#

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.

Valid Encryption Schemes#

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.