[Cryptography] Mapping numbers to permutations

[Ray Dillinger]

Lately I've been working with permutations, because they are at the core
of a family of deterministic pseudorandom bit generators I've been
studying.

One of the things I used was a bijective numbering scheme that
identifies each permutation with a unique integer.  It's pretty
straightforward.  Say you've got a number between 0 and 720, and you
want to map it to a permutation of six objects.  You load the number
into a register, then proceed.

Your first choice is among 6, so you take the register mod 6 to get the
choice, subtract the choice from the register, then divide the register
by six.  (and you get a choice 0..5)

The second choice is among the 5 remaining, so you take the register mod
5 to get the choice, subtract the choice from the register, then divide
the register by 5. (and you get a choice 0..4)

The third choice is among the 4 remaining, so you take the register mod
4 to get the choice, subtract the choice from the register, then divide
the register by 4.  (and you get a choice 0..3)

And so on. I've applied this technique in reverse before to create
permutations for S-boxes based on pseudorandom numbers in an
experimental block/stream Feistel cipher that uses different
pseudorandom S-boxes for each block.  (That cipher is very secure, but
VERY slow, so not competitive).

What the numbering scheme means for analyzing permutation based RNG's is
that a set of a permutations can be mapped to a state machine, with the
states numbered by the above scheme and transformations of those
permutations (such as the swaps in RC4 or the newer Spritz generator)
becoming edges in the state graph. Then if you can prove things aboout
the state graph you can make meaningful statements about the generators.

This procedure is very much like the procedure for converting bases.
You have this number, and you are taking the number modulo some value,
subtracting whatever you get from the number, and dividing by the same
value. Repeated getting a digit modulo ten then dividing by ten is the
classic machine-code way to get a base-ten representation, one digit at
a time, out of a base-2 register.  The only difference here is that the
base changes each digit.

Now here is an insight new to me, though someone else has probably
already had it.  This is also a bijective way to convert bases in the
output of nonbinary deterministic PRNG's to binary.  Let's say you have
a deterministic bit generator based on a permutation of 5 elements which
produces output (0..4) each iteration, and you want to transform the
sequence of pseudoentropy from that base-5 stream into an unbiased
binary pseudoentropy stream with a 1-to-1 mapping from the base-5 stream
to the base-2 stream.

That's fairly easy.  You fill a pseudoentropy register by repeatedly
multiplying by 5 and adding the generator output.

Then you can take binary output by taking the low bit of the
pseudoentropy register and shifting right to divide by 2 (taking base-2
digits from the integer).

Whenever the pseudoentropy register gets to be small enough to hold
another base-5 digit, you multiply it by 5 and add the output of the
generator (essentially you'd be 'replacing' the base-5 digit you most
recently took, had you been taking digits in base-5 rather than base-2).

What is interesting about it is this: Most conversion schemes for base-n
pseudoentropy to binary pseudoentropy have one of two problems: either
there can be multiple input streams that produce identical output, or
there is bias in the output stream because some inputs count for more or
less pseudoentropy than they're worth.  This scheme introduces no bias,
but preserves  the property that there is a one-to-one mapping from
input streams to output streams.  And this is desirable when trying to
show that there are no 'aliased keys' that produce or converge on the
same keystream.

Anyway, this isn't interesting for  streams of real entropy, because if
you're working with real entropy, then repeatability and one-to-one
mappings aren't important.  But if working with pseudoentropy - mostly
keystreams emitted from deterministic generators - it's interesting.

Just a little math I thought it would be interesting to write up and
pass along....


Bear

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 819 bytes
Desc: OpenPGP digital signature
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20141203/f43ecd5d/attachment.sig>