block ciphers,stream ciphers,Substitution ciphers,transposition ciphers,Vernam cipher

The encryption scheme is said to be symmetric-key if for each associated encryption/ decryption key pair (e; d), it is computationally "easy" to determine d knowing only e, and to determine e from d. Consider an encryption scheme consisting of the sets of encryption and decryption transformations {Ee : e 2 K} and {Dd : d 2 K}, respectively, where K is the key space.

There are two classes of symmetric-key encryption schemes which are commonly distinguished: block ciphers and stream ciphers.

A block cipher is an encryption scheme which breaks up the plaintext messages to be transmitted into strings (called blocks) of a fixed length t over an alphabet A, and encrypts one block at a time. Most well-known symmetric-key encryption techniques are block ciphers. Two important classes of block ciphers are substitution ciphers and transposition ciphers. Product ciphers combine these.

Substitution ciphers and transposition ciphers

Substitution ciphers are block ciphers which replace symbols (or groups of symbols) by other symbols or groups of symbols.

Simple substitution ciphers

Let A be an alphabet of q symbols and M be the set of all strings of length t over A. Let K be the set of all permutations on the set A. Define for each e 2 K an encryption transformation Ee as:

where m = (m1m2 …mt) 2 M. In other words, for each symbol in a t-tuple, replace (substitute) it by another symbol fromAaccording to some fixed permutation e. To decrypt c = (c1c2 … ct) compute the inverse permutation d = e?1 and

Homophonic substitution ciphers

To each symbol a 2 A, associate a set H(a) of strings of t symbols, with the restriction that the sets H(a), a 2 A, be pairwise disjoint. A homophonic substitution cipher replaces each symbol a in a plaintext message block with a randomly chosen string from H(a). To decrypt a string c of t symbols, one must determine an a 2 A such that c 2 H(a). The key for the cipher consists of the sets H(a).

Polyalphabetic substitution ciphers

A polyalphabetic substitution cipher is a block cipher with block length t over an alphabet A having the following properties:

(i) the key space K consists of all ordered sets of t permutations (p1; p2; : : : ; pt), where each permutation pi is defined on the set A.

(ii) encryption of the message m = (m1m2 …mt) under the key e = (p1; p2; : : : ; pt) is given by Ee(m) = (p1(m1)p2(m2) … pt(mt)).

Transposition ciphers

Another class of symmetric-key ciphers is the simple transposition cipher, which simply permutes the symbols in a block.

Consider a symmetric-key block encryption scheme with block length t. Let K be the set of all permutations on the set {1, 2; : : : ; t}. For each e 2 K define the encryption function

where m = (m1m2 …mt)2M, the message space. The set of all such transformations is called a simple transposition cipher. The decryption key corresponding to e is the inverse permutation d = e?1. To decrypt c = (c1c2 … ct), computeDd(c) = (cd(1)cd(2) … cd(t)).

A simple transposition cipher preserves the number of symbols of a given type within a block, and thus is easily cryptanalyzed.

Product ciphers

Simple substitution and transposition ciphers individually do not provide a very high level of security. However, by combining these transformations it is possible to obtain strong ciphers. Some of the most practical and effective symmetric-key systems are product ciphers. One example of a product cipher is a composition of t >= 2 transformations Ek1Ek2 …Ekt where each Eki , 1 <= i <= t, is either a substitution or a transposition cipher. For the purpose of this introduction, let the composition of a substitution and a transposition be called a round.

A substitution in a round is said to add confusion to the encryption process whereas a transposition is said to add diffusion.

Stream ciphers

Stream ciphers form an important class of symmetric-key encryption schemes. They are, in one sense, very simple block ciphers having block length equal to one. What makes them useful is the fact that the encryption transformation can change for each symbol of plaintext being encrypted. In situations where transmission errors are highly probable, stream ciphers are advantageous because they have no error propagation. They can also be used when the datamust be processed one symbol at a time.

Let K be the key space for a set of encryption transformations. A sequence of symbols e1e2e3 … ei 2 K, is called a keystream.

Let A be an alphabet of q symbols and let Ee be a simple substitution cipher with block length 1 where e 2 K. Letm1m2m3 … be a plaintext string and let e1e2e3… be a keystream fromK. Astream cipher takes the plaintext string and produces a ciphertext string c1c2c3 … where ci = Eei (mi). If di denotes the inverse of ei, then Ddi(ci) = mi decrypts the ciphertext string.

A stream cipher applies simple encryption transformations according to the keystream being used. The keystream could be generated at random, or by an algorithm which generates the keystream from an initial small keystream (called a seed), or from a seed and previous ciphertext symbols. Such an algorithm is called a keystream generator.

The Vernam cipher

A motivating factor for the Vernam cipher was its simplicity and ease of implementation. The Vernam Cipher is a stream cipher defined on the alphabet A = {0,1}. A binary message m1m2 … mt is operated on by a binary key string k1k2 … kt of the same length to produce a ciphertext string c1c2 … ct where

If the key string is randomly chosen and never used again, the Vernam cipher is called a one-time system or a one-time pad.

The one-time pad can be shown to be theoretically unbreakable. That is, if a cryptanalyst has a ciphertext string c1c2 … ct encrypted using a random key string which has been used only once, the cryptanalyst can do no better than guess at the plaintext being any binary string of length t (i.e., t-bit binary strings are equally likely as plaintext). It has been proven that to realize an unbreakable system requires a random key of the same length as the message. This reduces the practicality of the system in all but a few specialized situations.

The key space

The size of the key space is the number of encryption / decryption key pairs that are available in the cipher system. A key is typically a compact way to specify the encryption transformation (from the set of all encryption transformations) to be used. Each can be simply described by a permutation which is called the key. It is a great temptation to relate the security of the encryption scheme to the size of the key space.

Better to know some

... than all

Symmetric-key encryption