permutation mappings

From: duffman (samarthsanghavi_at_gmail.com)
Date: 09/28/04 

Date: 27 Sep 2004 20:17:00 -0700

Let PI be a permutation of the integers 0,1,2,3...2^(n-1), such that
PI(m) gives the permuted value of m, 0 <= m < 2^n. Put another way,
PI maps the set of n-bit integers into itself and no two integers map
into the same integer. DES (Data Encryption Standard, for those who
don't know a really popular way of encrypting data in a block-cipher
fashion) is such a permutation for 64 bit integers. We say that PI
has a fixed point at m if PI (m) = m. That is, if PI is an encryption
mapping, then a fixed point comes points to a message that encrypts to
itself. We are interested in the probability that PI has no fixed
points. Show the somewhat unexpected result that over 60% of mappings
will have at least one fixed point.

any ideas?

thanks,

Relevant Pages

  • Re: permutation mappings
    ... > PI maps the set of n-bit integers into itself and no two integers map ... DES (Data Encryption Standard, for those who ... > fashion) is such a permutation for 64 bit integers. ... > mapping, then a fixed point comes points to a message that encrypts to ...
    (sci.crypt)
  • File encryption idea
    ... The motivation is the encryption of files. ... block cipher like AES, or 3DES etc. and add a superstructure to it. ... The basic idea is to shuffle the bytes. ... needed for the permutation generation. ...
    (sci.crypt)
  • Re: commuting?/non-group cipher?
    ... the property that a double encryption under two keys is ... I can only think of three ciphers which have the property - Caesar, ... permutations ...
    (sci.math)
  • Re: commuting?/non-group cipher?
    ... the property that a double encryption under two keys is ... I can only think of three ciphers which have the property - Caesar, ... permutations ...
    (sci.crypt)
  • Re: OTP and message integrity.
    ... Is there a method to defeat such attacks ... Alice and Bob have previously agreed over a secure ... > changes at least 1/8 outputs, and the inverse permutation also has ... > encryption. ...
    (sci.crypt)