Re: OT: RFC, PRNG
- From: "cr88192" <cr88192@xxxxxxxxxxxxxxxxxx>
- Date: Mon, 28 May 2007 17:12:35 +1000
"Ben Rudiak-Gould" <br276deleteme@xxxxxxxxx> wrote in message
news:f3d8ju$ddk$1@xxxxxxxxxxxxxxxxxxxxxxx
cr88192 wrote:
for a project of mine, I have needed a fairly special PRNG. the point
is to have a sufficiently large amount of entropy that it generates
hopefully-unique strings.
There's nothing special about that -- any PRNG worthy of the name
satisfies that criterion, if you ask it for enough bits (and no PRNG can
possibly satisfy it if you don't ask for enough).
yes, but the internal entropy of the PRNG limits how unique of a string one
can get.
for example, it would be useless to ask for a 96-bit value from a typical
rand implementation (it only having a 64-bit internal state).
PRNGs have been extensively studied, and some good ones are known, and
some of those have public domain C implementations. You should use one of
them. You shouldn't try to design your own, because it's very hard.
(Actually, your requirements are weak enough that even a weak PRNG /might/
satisfy them, but there's still no reason not to use a good one.)
yes, a weak one will work.
intuitively, it should be good enough.
also, the core is derived from algos that have worked fairly well for me in
practice.
I don't have access to '/dev/urandom', because in part, I am currently
running on windows.
The Windows equivalent is CryptGenRandom(). You should probably use it,
because it's probably the most easily obtainable source of good seed
randomness on Windows, and you need that no matter which PRNG you use.
possible, but I like keeping anything OS dependent stuff hidden away.
luckily, this lib does have an os-dependent section, so I could probably put
it there...
I am mostly just hoping that the probability of clashes is sufficiently
low that they are unlikely in practice (anything much beyond 1.0/2^32
would probably be fine).
With any decent PRNG, you'll need to generate around 2^48 96-bit numbers
before you get a clash (birthday paradox). In certain situations you can
guarantee 2^96 distinct numbers (in a pseudorandom order) before a repeat,
but that won't work if you have many installations running in parallel.
yes.
You also need at least 96 bits of /good/ entropy to seed your generator,
or else that will be the limiting factor. The entropy you get from timing
tricks is not very good.
yes, that is a problem.
that is why I had hoped that the combination of loading/rehashing/and
storing, each time adding a little more entropy, would hopefully cause the
internal entropy to become ever larger.
they are for compiler-generated names, aka a gensym mechanism.
in the past, I had used a special prefix and sequential numbers, but this
wont work if the files are stored externally.
It will if the prefix is random. At program startup get some random bits
from CryptGenRandom, and then simply append increasing natural numbers to
the end. This will work just as well for avoiding collisions, and you
won't need a PRNG at all.
possible thought, dunno though (could allow shorter names, such as instead
using a 64-bit prefix).
the current scheme will probably work ok though.
actually, elsewhere at one point a scheme I had used was to use 'time()' to
get an integer to be used as a prefix, and sequentially generated indices on
the end of this.
-- Ben
.
- References:
- OT: RFC, PRNG
- From: cr88192
- Re: OT: RFC, PRNG
- From: Josiah Carlson
- Re: OT: RFC, PRNG
- From: cr88192
- Re: OT: RFC, PRNG
- From: Ben Rudiak-Gould
- OT: RFC, PRNG
- Prev by Date: Re: OT: RFC, PRNG
- Next by Date: Re: OT: RFC, PRNG
- Previous by thread: Re: OT: RFC, PRNG
- Next by thread: Re: OT: RFC, PRNG
- Index(es):
Relevant Pages
|
|
