Permutation-Based Cryptography

The translation of text from clear form to an encrypted form and back is a common problem in computing.  One simple technique for encrypting text is based on the mathematical notion of a permutation.  A permutation of the integers 0 through N-1 is simply a one-to one function whose domain and range are both the set of integers {0, 1, 2, . . . , N-1}.  In other words, a permutation transforms each integer in the set {0, 1, 2, . . . , N-1} into another integer in the same set, with no two integers being transformed into the same result.  For example, here is a permutation of {0, 1, 2, 3, 4}.

This permutation can be used to encrypt a sequence of five characters by moving each character from its original position to the position defined by the permutation.  For example, the sequence "APPLE" would be translated into the string "PLEAP":

Note that we number positions starting at zero just as in C++ arrays — that’s a hint of things to come.  What about decrypting the text above?  Well, each permutation has an inverse, another permutation that does the exact opposite of the original permutation.  For the permutation given above, the inverse permutation is:

Apply the inverse permutation to the scrambled sequence "PLEAP"; you should get back the original sequence "APPLE".  That’s the key point about encryption/decryption using a permutation, apply the permutation, and then apply its inverse, and you get back where you started.

Data Encryption Standard (DES)

DES is the archetypal block cipher — an algorithm that takes a fixed-length string of plaintext bits and transforms it through a series of complicated operations into another ciphertext bitstring of the same length. In the case of DES, the block size is 64 bits. DES also uses a key to customize the transformation, so that decryption can supposedly only be performed by those who know the particular key used to encrypt. The key ostensibly consists of 64 bits; however, only 56 of these are actually used by the algorithm. Eight bits are used solely for checking parity, and are thereafter discarded. Hence the effective key length is 56 bits, and it is always quoted as such.The key is nominally stored or transmitted as 8 bytes, each with odd parity. According to ANSI X3.92-1981, section 3.5: One bit in each 8-bit byte of the KEY may be utilized for error detection in key generation, distribution, and storage. Bits 8, 16,..., 64 are for use in ensuring that each byte is of odd parity.