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


.