Re: Constructing a random permutation on the fly


"Paul Rubin" <http://phr.cx@xxxxxxxxxxxxxx> wrote in message
news:7x4ouodra3.fsf@xxxxxxxxxxxxxxxxxxxxxx
Ilmari Karonen <usenet2@xxxxxxxxxxxxxx> writes:
Seriously, this was the answer I was going to post. To expand a
little on it, the "Hasty Pudding trick" is to start with a number in
the desired range and iterate the encryption function until you get a
result that is also in the range. The fact that a block cipher is a
permutation guarantees that this procedure will terminate,

The process is actually not guaranteed to terminate, since the
permutation can have cycles.

No, it will always terminate, because all members of a (finite) permutation
are a part of a cycle. That is, if you start with a value x_0, and have
x_{i+1} = perm( x_i ), then there will always be a value n s.t. x_n = x_0.
Hence, if x_0 is in range, then there will be a value x_m that will be in
range for m > 0, because even if x_i is not for 0<i<n, then it will be for
i=n.

--
poncho


.

Relevant Pages

  • Re: Constructing a random permutation on the fly
    ... the desired range and iterate the encryption function until you get a ... permutation guarantees that this procedure will terminate, ... The process is actually not guaranteed to terminate, ...
    (sci.crypt)
  • Re: VMPC Stream Cipher - ideas on potential weaknesses?
    ... > terabytes of bytes and digraphs through our ... It would be interesting to know about the possible short cycles. ... My geuss is that the algorithm mixes the permutation well enough to avoid ...
    (sci.crypt)
  • Re: Permutations: a tail of two representations
    ... A permutation is a 1-to-1 mapping of a finite set ... an explicit representation of the domain (as n will ... a "product" of disjoint cycles. ... of the singleton cycles is not suppressed. ...
    (comp.lang.prolog)
  • Re: More help requested on permutation code.
    ... The sort assumes numerical permutation elements. ... sub permutation_multiply ... # Read in the cycles, ... my $class = shift; ...
    (comp.lang.perl.misc)
  • Re: ANNOUNCE: New "Leopard6" CSPRNG !
    ... and it always reports s]. ... also a permutation of 0..255. ... same set of cycles, except any cycles of even length in the internal ... Voila, the internal state. ...
    (sci.crypt)