[Cryptography] Mapping numbers to permutations

[Ray Dillinger]

On 12/03/2014 11:07 PM, Viktor Dukhovni wrote:
> On Thu, Dec 04, 2014 at 07:28:25AM +0100, Andreas Briese wrote:
> 
>> Don't get it.  
>> If the output of the generator is random then its binary notation is random too. 
>> Why don't you use this directly, if you need a binary stream?
> 
> A uniformly random stream of integers selected from [0, n-1] does
> not directly yield an unbiased stream of bits.

Eggs Ackley.  A random number between 0 and some power of 2
yields that many random binary bits, but a random number
between 0 and some power of 5 yields that many random binary
bits only if it is also between 0 and a power of 2 less than
the power of 5.

And the usual solution is....

> Whenever a forbidden state is reached, you throw
> away your $k$ inputs and try another $k$.

To throw away any base-5 number you get that isn't also in the
range of the highest binary power that's less than the quintenary
power. But that throws away those base-5 digits, and the result
is that you get a mapping from input stream to output stream which
is a many-to-one mapping, ie, it's not invertible, so there are
a bunch of useful operations that don't work with it as a keystream
or a couple of other things.

The technique I posted about was a way to get an unbiased stream
of binary bits that has a one-to-one mapping to the input stream,
ie, there is only a single sequence of base-5 digits that could
result in a particular binary stream.

				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/20141204/1e03c084/attachment.sig>