Chapter 2
Symmetric Encryption Algorithms
February 15, 2010

2
The term “symmetric” means that the same key used to encrypt is used decrypt. In the widest sense all pre-PKC encryption algorithms are symmetric, although their keys may be very different in form. For example:
Caesar’s algorithm; a one character key:
Vigen`ere and Beaufort algorithms; a string of characters sequentially repeated form the key.
Wheatstone, Jefferson and even the Enigma machines;the key is a selection of discs (labelled or with electrical connections) which may be periodically changed.
But with the advent of the computer as a normal component of storage and transmission systems, the key is now a string of bits. Originally this might be 64 bits. Nowadays 128, 192 or 256 bits are considered safer. The string should be pseudo-random, and its length m such as to make “try all the 2m keys” or “brute force” attacks infeasible. (Such an attack tries to encrypt known or guessed plain-text and see if some key produces observed cypher-text; or to decrypt known cypher-text and see if plausible plain-text results.) The algorithms to which such keys apply are typically block cypher: or algorithms which, under key control, map n bits of input into n bits of output.
They are, of course, reversible - for decryption. Typically n is 64, 128, 192 or 256 bits. A good algorithm provides confusion and diffusion.
Confusion messes up the input bit pattern, typically by substituting one bit pattern by another, or permuting bits - always in a reversible manner.
Diffusion causes a change in one part of the input plain-text or key to spread out and make changes throughout the output cypher-text. Changing
1

a single key bit or plain-text bit should change 50% of all cypher-text bits in a “random” fashion.
Knowledge of c or p, without knowing k, should reveal nothing about p or c respectively. Knowledge of p and c should reveal nothing about k.
The basic symmetric scheme is:

We write this C = E(k; p) p = D(k; c) with E=Encryption, D=Decryption
(E −1 sometimes is used).

2.1 DES The Data Encryption Standard (Algorithm)
DES, introduced in the 1970’s, is the most widely used encryption algorithm, although it is no longer safe. (Theoretically the key, if unchanged, can be found if one has enough - a very large number - of plain-text cypher-text pairs. In practice this is seldom a practical method of attack.)

2

The full DES specification is an American National Standard and can be found at: http://www.ii.uib.no/ osvik/des/fips46-3.pdf
A summary only is presented here:
DES has a 64-bit key, of which only 56 bits are used. DES has 64 input bits (plain-text) and 64 output bits (cypher-text). It has sixteen stages or
“rounds” and uses a Feistel network, in which the 64 bits af data are split into two 32-bit blocks, left (L) and right (R). In round n we have, with n = 1 to 16. See figure 2.1.
Ln = Rn−1

Rn = Ln−1 ⊕ f (kn , Rn−1 )

This process is reversible: Knowing Ln , Rn and kn we can find Ln−1 and
Rn−1 . The round sub-key kn is derived from the basic key k by a simple keygeneration procedure. The function f () is the core of DES. It is as follows, see figure 2.2:
The 32-bit input (Rn−1 ) is expanded to 48 bits. This is XORed with the round key kn . The result is split into eight 6-bit blocks presented to eight
S-boxes (substitution boxes).
Each S-box produces a 4-bit output so that we are back to 32-bits, which are then permuted by a fixed function P . The S-boxes are non-linear S(x ⊕
y) = S(x) ⊕ S(y) where x, y are possible 6-bit inputs; but are uniform in the sense that each 4-bit output pattern appears four times to account for the 64 6-bit input patterns. (But the S-boxes are differentially non-uniform, see module 1).
There is a 64-bit input permutation, IP , before the data enter the Feistel network, and IP −1 is applied to the final network output - to ensure correct decryption. The following is one of 16 stages. (Figure 2.1):

3

4

2.2 Modes for Block Cyphers