Re: Update of my old idea on random number generation



On 2010-03-20, Mok-Kong Shen <mok-kong.shen@xxxxxxxxxxx> wrote:

Quite a time ago I had the humble idea of building a compound PRNG
consisting of a number of constituent PRNGs. I have recently updated
it in some details and would like very much to subject it again to
comments and critiques from the group. The scheme can be briefly
described in terms of four levels.

The 1st level is a PRNG, which we choose to be a higher degree
permutation polynomial mod 2^32 (assuming 32 bit words). More exactly,
it is to be one with full cycle in [0,2^32-1]. The coefficients of the
polynomial and the starting value (seed of PRNG) shall come from a
correspondingly long master key together with some time-varying
informations such as time and message number, so that the resulting
PRNG (termed master-PRNG below) is unique for each message that uses
our scheme.

The 2nd level uses the output of the master-PRNG to generate a pool of
PRNGs that are lower degree (e.g. 2nd degree) permutation polynomials
together with their seeds. Each such PRNG has an associated
pseudo-randomly determined constant value b in the range [0,31].

The 3rd level activates the PRNGs in the pool in a pseudo-random order
as follows: Each PRNG, when it gets activated, outputs a number R.
Using a bit mask, one obtains from R a value p as the index of the next
PRNG in the pool to be activated. R is subsequently cyclically shifted
by b bits to become R' for further treatment in the 4th level.

The 4th level consists of a single PRNG G(x), again a lower degree
permutation polynomial. It takes each R' from the 3rd level and outputs
G(R') as the external output of our scheme. (Currently I tend to think
that the 4th level may be unnecessary and thus left out or be optional.)

The purpose of all this is what? It is certainly not a fast prng. What
do you want to use it for?

You could just use your first prng to create say 5 bytes as the date for
the new york times, and then the next five bytes as the number of the
letter to take out of that issue for the next byte in teh PRNG. Now you
may have to wait a few centuries for the output, but since speed is not
of any concern to you....
Actually that output is liable to be biased, but you get the idea.


Thanks,

M. K. Shen
.



Relevant Pages

  • Update of my old idea on random number generation
    ... Quite a time ago I had the humble idea of building a compound PRNG ... consisting of a number of constituent PRNGs. ... PRNGs that are lower degree permutation polynomials ... The 3rd level activates the PRNGs in the pool in a pseudo-random order ...
    (sci.crypt)
  • Re: new /dev/random
    ... I took a look in the random.c code (2.6.6 kernel) and found that both ... and urandom_read extracts entropy from the secondary ... pool, sec_random_state (also, get_random_bytes extracts from that pool ... It is more a hybrid between a PRNG and a RNG, ...
    (sci.crypt)