# 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

- Prev by Date:
**Re: Constructing a random permutation on the fly** - Next by Date:
**Re: Sharing my 256-bit 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):