Classical Ciphers

Introduction to Cryptography: Classical CiphersWolfram U · Caesar, Vigenère, substitution and transposition ciphers, 7 minCaesar Cipher (Part 2)Neso Academy · shift (Caesar) cipher with worked examples, 10 minPlayfair Cipher (Part 1)Neso Academy · Playfair key matrix and digraphs, 13 minPlayfair Cipher (Part 2)Neso Academy · Playfair encryption rules with examples, 11 min

Symmetric encryptionSearch on YouTubeBookmarkSaved

Basic ideaSearch on YouTubeBookmarkSaved

Symmetric encryption is also called conventional, private-key, or single-key encryption. The sender and the recipient share a common key.

• All classical encryption algorithms are private-key.
• Symmetric encryption was the only type before the invention of public-key cryptography in the 1970s.
• It is by far the most widely used type.

TerminologySearch on YouTubeBookmarkSaved

Symmetric cipher modelSearch on YouTubeBookmarkSaved

The slide figure shows this flow:

1. The plaintext input goes into the encryption algorithm (for example, DES).
2. The transmitted ciphertext goes to the recipient.
3. The decryption algorithm (the reverse of the encryption algorithm) gives the plaintext output.

Both algorithms use the secret key shared by sender and recipient.

There are two requirements for secure use of symmetric encryption:

1. A strong encryption algorithm.
2. A secret key known only to sender and receiver.

Mathematically:

The slides assume that the encryption algorithm is known. Thus security depends on the secrecy of the key. This implies a secure channel to distribute the key.

Classifying cryptosystemsSearch on YouTubeBookmarkSaved

Three properties characterize a cryptographic system:

CryptanalysisSearch on YouTubeBookmarkSaved

Two approachesSearch on YouTubeBookmarkSaved

The objective of cryptanalysis is to recover the key, not only the message. There are two general approaches:

• Cryptanalytic attack: uses the structure of the algorithm and properties of the plaintext.
• Brute-force attack: tries every possible key.

Attack typesSearch on YouTubeBookmarkSaved

Security levelsSearch on YouTubeBookmarkSaved

Brute force searchSearch on YouTubeBookmarkSaved

• It is always possible to try every key.
• It is the most basic attack. The work is proportional to the key size.
• The attacker must know or recognize the plaintext.

b-bit key: number of keys = 2^b
On average, the attacker tries half the keys: 2^(b-1)

Substitution ciphersSearch on YouTubeBookmarkSaved

Substitution principleSearch on YouTubeBookmarkSaved

A substitution cipher replaces the letters of plaintext with other letters, numbers, or symbols. If the plaintext is a sequence of bits, substitution replaces plaintext bit patterns with ciphertext bit patterns.

Caesar cipherSearch on YouTubeBookmarkSaved

The Caesar cipher is the earliest known substitution cipher. Julius Caesar used it. It is the first attested use of a cipher in military affairs. It replaces each letter by the letter three places down the alphabet.

plain:  meet me after the toga party
cipher: PHHW PH DIWHU WKH WRJD SDUWB

Give each letter a number: $a=0$, $b=1$, ..., $z=25$. Then:

The Caesar cipher uses $k=3$. Modulo arithmetic wraps around the alphabet: $1 = 27 \bmod 26$ and $3 = 29 \bmod 26$.

Breaking the Caesar cipherSearch on YouTubeBookmarkSaved

There are only 26 possible keys: shifts $K = 0, 1, 2, \ldots, 25$. The attack is a brute-force search. Try all shifts on the ciphertext. The attacker must recognize the plaintext when it appears.

Slide test: break olssv ovd hyl fvb. The key is $k=7$. Shift each letter back by 7 to get hello how are you.

Monoalphabetic cipherSearch on YouTubeBookmarkSaved

Shuffle (jumble) the letters arbitrarily instead of shifting the alphabet. Each plaintext letter maps to a different random ciphertext letter. Thus the key is 26 letters long.

Slide example: plaintext ifwewishtoreplaceletters encrypts to WIRFRWAJUHYFTSDVFSFUUFYA.

The number of keys is $26! = 4 \times 10^{26}$. With so many keys, the cipher seems secure. This is wrong. The problem is language characteristics.

Language redundancySearch on YouTubeBookmarkSaved

Human languages are redundant. For example, th lrd s m shphrd shll nt wnt is readable without its vowels. Letters are not equally common:

• In English, E is by far the most common letter, followed by T, R, N, I, O, A, S.
• Z, J, K, Q, X are fairly rare.
• Tables of single, double, and triple letter frequencies exist for various languages.

The slide bar chart gives these English relative frequencies (%):

Key concept: monoalphabetic substitution ciphers do not change relative letter frequencies. Calculate the letter frequencies of the ciphertext. Then compare the counts or plots against the known values.

Worked cryptanalysisSearch on YouTubeBookmarkSaved

Ciphertext from the slide:

UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZ
VUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSX
EPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ

1. Count the relative letter frequencies.
2. Guess that P and Z are e and t.
3. Guess that ZW is th, so ZWP is the.
4. Continue with trial and error.

The final plaintext:

it was disclosed yesterday that several informal but
direct contacts have been made with political
representatives of the viet cong in moscow

Monoalphabetic quizSearch on YouTubeBookmarkSaved

The key maps the plain alphabet to the reversed alphabet:

Encrypt attack at noon. The letters map as $a \to z$, $t \to g$, $c \to x$, $k \to p$, $n \to m$, $o \to l$. The result is zggzxp zg mllm, so the correct option is C.

Playfair cipherSearch on YouTubeBookmarkSaved

BackgroundSearch on YouTubeBookmarkSaved

Even the large number of keys in a monoalphabetic cipher gives no security. One way to improve security is to encrypt multiple letters. The Playfair cipher is an example. Charles Wheatstone invented it in 1854, but it is named after his friend Baron Playfair.

Key matrixSearch on YouTubeBookmarkSaved

The key is a 5 × 5 matrix of letters based on a keyword:

• Fill in the letters of the keyword, without duplicates.
• Fill the rest of the matrix with the other letters.
• I and J share one cell.

Keyword MONARCHY:

Encryption rulesSearch on YouTubeBookmarkSaved

Encrypt the plaintext two letters at a time:

1. Repeated letter in a pair: insert a filler such as X. balloon becomes ba lx lo on.
2. Same row: replace each letter with the letter to its right. Wrap from the end back to the start. ar encrypts as RM.
3. Same column: replace each letter with the letter below it. Wrap from the bottom to the top. mu encrypts to CM.
4. Otherwise: replace each letter with the letter in its own row and in the column of the other letter. hs encrypts to BP. ea encrypts to IM or JM.

GUARDIAN quizSearch on YouTubeBookmarkSaved

The slide gives this Playfair square for keyword guardian:

Plaintext postponed attack becomes the pairs po st po ne da tx ta ck. The filler x separates the repeated t.

Ciphertext: QPTOQPBIGRQZQDBL. This is option B.

Security of PlayfairSearch on YouTubeBookmarkSaved

Polyalphabetic ciphersSearch on YouTubeBookmarkSaved

PrincipleSearch on YouTubeBookmarkSaved

Polyalphabetic substitution ciphers use multiple cipher alphabets. More alphabets make cryptanalysis harder and give a flatter frequency distribution. A key selects the alphabet for each letter of the message:

• Use each alphabet in turn.
• Repeat from the start after the end of the key.

Vigenère cipherSearch on YouTubeBookmarkSaved

The Vigenère cipher is the simplest polyalphabetic substitution cipher. It is effectively multiple Caesar ciphers. The key has $d$ letters: $K = k_1 k_2 \ldots k_d$. The $i$-th key letter specifies the $i$-th alphabet. After $d$ letters, the key repeats. Decryption works in reverse.

Here $k_i$ is the key letter above $p_i$ in the repeated key. The slide also shows the 26 × 26 Vigenère tableau. Row = key letter, column = plaintext letter.

To encrypt:

1. Write the plaintext out.
2. Write the keyword repeated above it.
3. Use each key letter as a Caesar key for the plaintext letter below it.

Slide example, keyword deceptive ($d = 9$):

key:        deceptivedeceptivedeceptive
plaintext:  wearediscoveredsaveyourself
ciphertext: ZICVTWQNGRZGVTWAVZHCQYGLMGJ

Vigenère securitySearch on YouTubeBookmarkSaved

• Each plaintext letter has multiple ciphertext letters, so the letter frequencies are obscured but not totally lost.
• Start with the letter frequencies. See if the text looks monoalphabetic or not.
• If not, find the number of alphabets $d$. Then attack each alphabet separately.

Autokey cipherSearch on YouTubeBookmarkSaved

Ideally, the key is as long as the message. Vigenère proposed the autokey cipher. The keyword is prefixed to the message to make the key.

key:        deceptivewearediscoveredsav
plaintext:  wearediscoveredsaveyourself
ciphertext: ZICVTWQNGKZEIIGASXSTSLVVWLA

The keyword recovers the first few letters. The recovered letters then decrypt the rest of the message. But the frequency characteristics remain for an attack.

One-time padSearch on YouTubeBookmarkSaved

If a truly random key as long as the message is used, the cipher is secure. This is the one-time pad.

Transposition ciphersSearch on YouTubeBookmarkSaved

PrincipleSearch on YouTubeBookmarkSaved

Classical transposition (permutation) ciphers hide the message by rearranging the letter order. They do not change the letters. Thus the ciphertext has the same frequency distribution as the original text, and this identifies a transposition cipher.

Rail fence cipherSearch on YouTubeBookmarkSaved

Write the message letters diagonally over a number of rows. Then read off the cipher row by row. Slide example with 2 rows:

m e m a t r h t g p r y
 e t e f e t e o a a t

Ciphertext: MEMATRHTGPRYETEFETEOAAT.

The plaintext meetmeafterthetogaparty has 23 letters. The top row holds the 12 odd-position letters. The bottom row holds the 11 even-position letters.

Row transposition cipherSearch on YouTubeBookmarkSaved

This is a more complex transposition:

1. Write the message in rows over a specified number of columns.
2. Reorder the columns according to a key.
3. Read off the columns in key order.

Slide example, key 4 3 1 2 5 6 7. The padding is xyz.

Read the column with label 1 first, then label 2, and so on:

Ciphertext: TTNAAPTMTSUOAODWCOIXKNLYPETZ.

Product and rotor ciphersSearch on YouTubeBookmarkSaved

Product ciphersSearch on YouTubeBookmarkSaved

Ciphers that use substitutions or transpositions are not secure because of language characteristics. So use several ciphers in succession:

• Two substitutions make a more complex substitution.
• Two transpositions make a more complex transposition.
• A substitution followed by a transposition makes a new, much harder cipher.

This is the bridge from classical to modern ciphers.

Rotor machinesSearch on YouTubeBookmarkSaved

Before modern ciphers, rotor machines were the most common complex ciphers in use. They were widely used in WW2: the German Enigma, the Allied Hagelin, and the Japanese Purple.

• A rotor machine implements a very complex, varying substitution cipher.
• It uses a series of cylinders. Each cylinder gives one substitution.
• The cylinders rotate and change after each letter is encrypted.

The slides show a photo of a Hagelin rotor machine. They also show Figure 2.8, "Three-Rotor Machine With Wiring Represented by Numbered Contacts". The figure has a fast rotor, a medium rotor, and a slow rotor. Part (a) shows the initial setting. Part (b) shows the setting after one keystroke.

SteganographySearch on YouTubeBookmarkSaved

Basic techniquesSearch on YouTubeBookmarkSaved

Steganography is an alternative to encryption. It hides the existence of the message:

• Use only a subset of the letters or words of a longer message, marked in some way.
• Use invisible ink.
• Hide data in the LSB of a graphic image or sound file.

The drawback: high overhead to hide relatively few information bits.

Other techniquesSearch on YouTubeBookmarkSaved

Quick self-testSearch on YouTubeBookmarkSaved