Is DES a group? No.
Don Coppersmith
Let E(k) be the permutation on message space gotten by DES-encrypting
each message under the key k. Consider the subgroup of the
symmetric group on 2^64 elements (message space) generated by the
2^56 permutations E(k), for the various values of k.
Could this be a small subgroup?
Kaliski et al raised this question at Crypto 85 (1).
Later, at the same conference (2), I suggested a means of showing a
lower bound on the size of this subgroup: start with a message x:
alternately encipher under the key of all 0's and the key of all 1's,
and wait for it to cycle. The cycle length for these particular
keys is relatively small (about 2^32), so the experiment is feasible.
Also the cycle length divides the order of the subgroup in question.
Now repeat the experiment several times, and the least common multiple
of the various cycle lengths divides the order of the subgroup, thus
puts a lower bound on the size of the subgroup.
I have run that experiment on ten cycles, finding ten random-looking
integers between 4.4E8 and 6.5E9, whose least common multiple is
about 2.5E88. That is, the size of the group generated by DES
encryptions is at least 2*10^88.
Earlier work by Coppersmith and Grossman (3) gives reason to believe
that the subgroup is the whole alternating group on 2^64 elements.
So, no, DES does not generate a small subgroup.
Don Coppersmith, IBM Research
(1) B. S. Kaliski Jr., R. L. Rivest, and A. T. Sherman,
"Is DES a pure cipher?
(Results of more cycling experiments on DES),"
Advances in Cryptology -- CRYPTO '85, pp 212-226.
(2) D. Coppersmith,
"The real reason for Rivest's phenomenon,"
Advances in Cryptology -- CRYPTO '85, pp 535-536.
(3) D. Coppersmith and E. Grossman,
"Generators for certain alternating groups with applications
to cryptology," SIAM Journal on Applied Mathematics,
vol 29 (1975), pp 624-627.