Ciphers

Aka. encryption algorithm. A function that ($e$) transforms a plaintext ($m$) into a ciphertext ($c$) under the control of a secret key ($k$). A cipher may have a fixed-sized input.

The reverse process, decryption ($d$) or decipherment, recovers the plaintext:

Encryption and decryption algorithms ($e$ and $d$) are public. Only the key is secret, and the ciphertext ($c$) is assumed to be easily, that is publicly, accessible.

Secret Key

The secrecy of plaintext $m$ is totally dependent on the secrecy of the key $k$. The key space must be large enough to make an exhaustive key search infeasible.

Algorithms with this property are called symmetric cryptosystems or secret key cryptosystems. Both parties to a secret communication must know $k$ and keep it secret.

Security also depends on Kerckhoffs’s principle for what a cryptosystem may safely assume is public.

Encryption Scheme

A cipher is the core keyed primitive, a fixed function $e_k$ with a defined input size. An encryption scheme is a complete construction that encrypts messages of arbitrary length, built from a cipher by supplying whatever the cipher lacks.

• Arbitrary length
  Handling a message that is not exactly one cipher input, through padding or a keystream.
• Randomisation
  Equal plaintexts under the same key $k$ must give different ciphertexts.

Initialization Vector

A non-secret, fixed-size input to a scheme that randomises encryption, so encrypting the same message twice under the same key $k$ gives different ciphertexts.

Sent alongside the ciphertext. Never reused under the same key. Sometimes required to be unpredictable rather than merely unique.

This uniqueness requirement is specific to randomising encryption. Some authentication modes fix the IV to zero instead, since they need a deterministic tag rather than randomised ciphertext.

Categorization

Ciphers are classified along several axes, not mutually exclusive. A modern cipher often falls into multiple categories at once.

Classical Cipher

Aka. historical cipher. The ciphers used in the pre-computer.

Historical ciphers used plaintext linked to:

• A particular language.
• The alphabet of symbols or characters used.
• The peculiar statistical characteristics of the language.

For English:

• A 26 character alphabet (A to Z).
• Higher usage of characters e, t, a, o, i.
• Higher appearance of bigrams (th, he, an, in) and trigrams (the, ing, and, her, ere).

Mono-Alphabetic Cipher

A plaintext character is replaced with a ciphertext character according to a fixed rule.

Preserves the language’s statistical characteristics in the ciphertext.

Examples:

• Shift cipher
• Substitution cipher

Poly-Alphabetic Cipher

Uses multiple substitution alphabets, e.g. one alphabet for odd-numbered positions and a different one for even-numbered positions, flattening the character frequency graph.

Using $n$ alphabets in a poly-alphabetic cipher gives a key space of $(26!)^n$ at the cost of remembering a key of length $26n$ characters.

Examples:

• Vigenère cipher
• Beaufort cipher
• Running-key cipher
• Vernam cipher and the one-time pad
• Enigma machine

Polygraphic Cipher

One fixed substitution is applied, but over groups of letters rather than single letters. A bigraphic cipher substitutes bigrams.

Effects:

• Single-letter frequencies are partly flattened.
• Bigram frequencies are preserved.

A polygraphic cipher is not poly-alphabetic. The substitution is fixed and does not change with position. A poly-alphabetic cipher keeps single-letter substitution but varies the alphabet by position.

Examples:

• Playfair cipher
• Hill cipher

Transposition Cipher

Also called a permutation cipher, as a category. Scrambles the positions of the plaintext characters without changing the characters themselves.

One specific cipher in this category is also named the permutation cipher.

The key defines the permutation applied to character positions. Decryption applies the inverse permutation.

Every single-letter frequency is preserved unchanged. Bigram and trigram frequencies are disturbed, since adjacent plaintext letters are pulled apart. This exposes it to anagramming attacks, where the analyst rearranges ciphertext fragments to recover valid plaintext.

A transposition and a substitution can be composed in one cipher. Modern block ciphers use both.