Ciphers

Also known as 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.

Key Space

The key space is the set of all permitted secret keys. Its size sets the work of an exhaustive key search. A uniformly selected $b$-bit key gives $2^b$ possible keys and requires $2^{b-1}$ trials on average to find.

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.

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.

Keyless Cipher

A cipher with no key. Its encryption and decryption transformations are fixed and public.

It provides no secrecy once the transformation is known.

Classical Cipher

Also known as historical cipher. The ciphers used in the pre-computer era.

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 different substitution rules at different plaintext positions. Each rule maps every plaintext letter to a ciphertext letter.

If each rule can be any permutation of the 26 letters, there are $26!$ choices for one rule. Choosing $n$ rules independently gives $(26!)^n$ possible keys. A key written as $n$ substitution alphabets takes $26n$ characters, with each alphabet listing the 26 ciphertext letters in order. This count applies only when each rule can be any permutation.

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.

Examples:

• Playfair cipher
• Hill cipher

Transposition Cipher

Scrambles the positions of the plaintext characters without changing the characters themselves.

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.

Examples:

• Permutation cipher