Re: Constructing a random permutation on the fly
 From: "Scott Fluhrer" <sfluhrer@xxxxxxxxxxxxx>
 Date: Wed, 10 Jun 2009 12:31:37 0400
"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
.
 References:
 Constructing a random permutation on the fly
 From: Tom Anderson
 Re: Constructing a random permutation on the fly
 From: Paul Rubin
 Re: Constructing a random permutation on the fly
 From: Ilmari Karonen
 Re: Constructing a random permutation on the fly
 From: Paul Rubin
 Constructing a random permutation on the fly
 Prev by Date: Re: Constructing a random permutation on the fly
 Next by Date: Re: Sharing my 256bit ECC library
 Previous by thread: Re: Constructing a random permutation on the fly
 Next by thread: Re: Constructing a random permutation on the fly
 Index(es):
Relevant Pages
