On 5/4/2014 11:38 AM, Joseph Rushton Wakeling via Digitalmars-d wrote:
On 04/05/14 16:28, Nick Sabalausky via Digitalmars-d wrote:
On a general level, I'm trying to grok the whole intent of
isUniformRNG and see
whether or not anything else may ever be needed in addition to
isUniformRNG. I'm
not trying to push an "isRNG", just trying to understand std.random's
current
intentions and reasoning, so I know how to work with it appropriately.
Yea, it's a good question. I think I would answer it as follows.
[...]
Ok, I see. Thanks.
But more immediately, since Phobos lacks a crypto-secure RNG, I'm
implementing
NIST's Hash_DRBG (backed by the OS-provided
RtlGenRandom/CryptGenRandom and
"/dev/random" as entropy sources). Hopefully I can get it into a
Phobos-acceptable state.
That's great -- I really look forward to seeing your work :-) Can you
give me some links to the spec?
The spec for Hash_DRBG is in "NIST Special Publication 800-90A" which
also includes a few other crypto RNGs (including, unfortunately, the one
with a known NSA backdoor, Dual_EC_DRBG, but it's easy enough to just
not bother implementing that one):
http://csrc.nist.gov/publications/nistpubs/800-90A/SP800-90A.pdf
That paper is linked to from here (seems to be down right now though):
http://csrc.nist.gov/groups/ST/toolkit/random_number.html
Which I found from here:
http://en.wikipedia.org/wiki/Cryptographically_secure_pseudorandom_number_generator#Standards
Now, I can follow the spec for the Hash_DRBG algorithm well enough,
but I'm not
really solid on random-number theory, so I can't be certain whether or
not
isUniformRNG is appropriate for this. I would assume "yes", but I
don't want to
assume. Hence my inquiries.
I don't know that this necessarily needs too much in the way of
random-number theory, but there are 3 questions that really need
answering here:
* What's the type of number that this algorithm produces?
Just a string of random bits. Effectively unsigned integers.
* What's the min and max values produced, and are these
inclusive bounds, i.e. are the random numbers drawn
from the closed [min, max] interval?
It's all based on SHA hashes (of seeds, internal state, and some other
stuff) and it doesn't explicitly exclude any output values. So if SHA is
working as expected, then yea, I'd imagine it should be a closed
interval over [0, 2^numBitsRequested - 1] where "numBitsRequested" is
permitted by the spec to be any positive integer.
* Are these numbers uniformly distributed?
This is the part I've been a little unclear on, although maybe I'm just
being paranoid about it. Doesn't a uniform distribution carry certain
reliable statistical properties? I don't know whether that could be used
to improve the likelihood of guessing future values. If so, then maybe
the algorithm is designed to avoid that?
Then again, wouldn't the only alternative to uniform distribution be a
weighted distribution? I can't imagine an RNG intended for crypto would
be deliberately weighted (unless maybe there were some randomness to the
weights...if that even makes any sense at all).
Maybe I'm just overthinking it?
