Cryptography
 Computer Science Computer Catlog Cryptography Catlog

 Caesar Cipher Digital Signature Public key cryptography Symmetric vs. public-key Key Management Stream Ciphers Self-Synchronizing Ciphers Feedback Shift Registers Modes of Operation Multiple Encryption Transposition Ciphers Substitution Ciphers Poly-alpha Substitutions Poly-alpha Cipher Machine Cryptanalysis Ciphers Data Encryption Standard DES Algorithm IDEA Algorithm RC5 Algorithm RSA Encryption Rabin Encryption ElGamal Encryption MD4 & MD5 Secure Hash Algorithm Kerberos Authentication Diffie-Hellman protocols Key Management Life Cycle

## Symmetric-key encryption

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.

A message

m = ABCDEFGHIJKLMNOPQRSTUVWXYZ

is encrypted to

c = Ee(m) = DEFGHIJKLMNOPQRSTUVWXYZABC

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:

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 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

Dd(c) = (d(c1)d(c2)  d(ct)) = (m1m2 mt) = m:

Ee is called a simple substitution cipher or a mono-alphabetic substitution cipher.

### 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

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 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

ci = mi XOR ki; 1 <= i<= t:

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.