Better to know some... than all 


Symmetrickey encryptionThe encryption scheme is said to be symmetrickey 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. A message m = ABCDEFGHIJKLMNOPQRSTUVWXYZ is encrypted to c = Ee(m) = DEFGHIJKLMNOPQRSTUVWXYZABC There are two classes of symmetrickey 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 wellknown symmetrickey 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 ciphersSubstitution ciphers are block ciphers which replace symbols (or groups of symbols) by other symbols or groups of symbols. Simple substitution ciphersLet 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: Ee(m) = (e(m1)e(m2) e(mt)) = (c1c2 ct) = c; where m = (m1m2 mt) 2 M. In other words, for each symbol in a ttuple, 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 Dd(c) = (d(c1)d(c2) d(ct)) = (m1m2 mt) = m: Ee is called a simple substitution cipher or a monoalphabetic substitution cipher. Homophonic substitution ciphersTo 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 ciphersA 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 ciphersAnother class of symmetrickey ciphers is the simple transposition cipher, which simply permutes the symbols in a block. Consider a symmetrickey 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 Ee(m) = (me(1)me(2) me(t)) 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 ciphersSimple 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 symmetrickey 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 ciphersStream ciphers form an important class of symmetrickey 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 cipherA 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 ci = mi XOR ki; 1 <= i<= t: If the key string is randomly chosen and never used again, the Vernam cipher is called a onetime system or a onetime pad. The onetime 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., tbit 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 spaceThe 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. 