Computer Security and Cryptography

9.7 IS DES A RANDOM MAPPING?

In Section 10 of Chapter 8 the mappings of the set were described.

        Proposition 9.1: If F is a randomly chosen one-to-one mapping of and Z is a randomly chosen element of , then

9.1a	The probability that Z belongs to an n-cycle in and
9.1b	The average length of the cycle containing Z is (m + 1)/2.

        Proof: First an explanation of what is meant by “random”; there are m! permutations of the elements of . By the phrase “choose a mapping F randomly”, we mean that the permutation F is selected with probability 1/m!. Similarly, by the phrase “choose randomly”, we mean that a particular is selected with probability 1/m.

Let L denote the length of the cycle of F containing Z. As Z is to be any of m values, there are (m − 1)! permutations of the ...