Block Cipher

There are symmetric and asymmetric block cipher algorithms. Only the symmetric kind will be dealt with here.

As the name suggests, block ciphers traffic in message blocks. These blocks have a size which is typically 64 bits or greater.

A block cipher encryption function uses a key K to map a n-bit plaintext block P into a n-bit ciphertext block C. We can write this as ENCK(P)=C. The decryption function reverses this mapping. For this we can write DECK(C)=P. So, DECK(ENCK(P))=P.

For this scheme to work, ENCK must be a bijection, that is it must be a permutation on the set of all n-bit messages, M (|M|=2n). The key K is an index into the set of all permutations of which there are 2n! which is equal to 2(n-1)2n by Stirling's approximation. If the key size is k bits then we have 2k different keys and looking at the ratio of permutations to the number of keys (2(n-1)2n / 2k) we see that we either want a really large key size k to enable us to select from many possible permutations, or we want a randomly chosen key K to look like it chooses a random permutation to make it seem like all permutations were equally likely.

References

L. R. Knudsen, M. J. B. Robshaw, The Block Cipher Companion. Springer, 2011.
A. Menzes, P. van Oorschot, and S. Vanstone, Handbook of Applied Cryptography. CRC Press, 1996.