Combinatorial Properties of Basic Encryption Operations

The basic ingredients of modern fast software block encryption schemes are computer instructions like SHIFT, ADD, XOR etc. We analyze the algebraic structure of different combinations of those cryptographic primitives from a purely combinatorial point of view. Different subsets of such operations will yield an interesting variety of different permutation groups, e.g. semidirect products, affine linear groups, wreath products, and symmetric groups. As we will show, a simple pair of a SHIFT and an ADD operation is already powerful enough to generate every possible encryption function on its set of input blocks. On the other hand, any possible combination of SHIFT and XOR operations can only produce a subset of at most n2n functions within the symmetric group of order n!. The present results are useful in theory at first. Their cryptographic applications can be found in providing practical tools for the analysis of the algebraic structure of new block encryption schemes and evaluation of their subroutines.