In std.random, is the "isUniformRNG" intended to determine whether the given type is *some* RNG or just a *specific* form of RNG? Because I don't see any "isRNG" that's more general.

More importantly, should a crypto RNG count as "isUniformRNG"?

On 04/05/14 04:03, Nick Sabalausky via Digitalmars-d wrote:
> In std.random, is the "isUniformRNG" intended to determine whether the given
> type is *some* RNG or just a *specific* form of RNG? Because I don't see any
> "isRNG" that's more general.

Yes, it is meant to denote that the type is a _uniform_ random number generator, that is, it's an input range whose elements are numbers drawn from a uniform distribution.  One could even be more strict as per the C++11 standard and specify that it's a range whose elements are unsigned integral types uniformly distributed in the closed interval [min, max].

Personally speaking, I have spent quite a lot of time being uncertain about whether the constraint to only unsigned integral types is entirely appropriate (e.g. Boost::Random contains RNGs whose underlying type is floating-point), but it _does_ greatly simplify many design factors.  For example, the fact that you're given a guarantee about bounds makes things much simpler when you move on to (say) random distributions, such as the uniform distribution, where you want to control precisely the upper and lower bound behaviour (closed or open).

About a more general "isRNG" template: can you be more precise about what you are interested in achieving with this?  Generally speaking I would find it rather dangerous to go passing around sources of randomness without having some understanding of their properties :-)

I should also add: the C++11 standard distinguishes between uniform random number generators (the aforementioned uniformly-distributed-unsigned-integers-in-[min, max]) and uniform _distributions_, which take the output of a uniform RNG and transform it into random values drawn from other distributions.  Again, here we can see the importance of C++11's strict definition of a uniform RNG: suppose we take a uniform _distribution_ of floating-point numbers in the half-open range [0, 1) and use it as the _source_ of randomness for a uniform distribution in the closed interval [0, 1].  It won't work, because the assumptions about bounds won't work.

> More importantly, should a crypto RNG count as "isUniformRNG"?

If it's producing unsigned integral types uniformly distributed in a closed interval [min, max], why not?

On 5/4/2014 3:47 AM, Joseph Rushton Wakeling via Digitalmars-d wrote:
>
> About a more general "isRNG" template: can you be more precise about
> what you are interested in achieving with this?  Generally speaking I
> would find it rather dangerous to go passing around sources of
> randomness without having some understanding of their properties :-)
>

Fair enough point, I'll explain my situation:

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.

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.

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.

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.

From a design point of view, it's helpful to distinguish between code that acts as a fundamental source of (usually pseudo-) randomness, versus stuff that transforms the output of those random sources into other forms (say, uniformly-distributed floating point numbers, or rolls of a 6-sided die, or permutations of an array, or whatever else).

In other words, it's helpful to distinguish between _generators_ of randomness, versus _users_ of randomness.

Now, in principle, there are many different kinds of random generator available, not all of them drawing from a uniform distribution.  But again, from a design point of view, it's helpful to constrain the range of functionality assumed, and uniformly-distributed random numbers are a very good foundation from which to build, because they can reliably be used to generate numbers drawn from any other probability distribution.

On top of that, it's useful to have the constraint of a distribution on a closed interval that has explicitly included minimum and maximum values, because that greatly simplifies the checks and assumptions one has to make in writing functions that make use of the random generator.

Hence you come to this definition of a "uniform random number generator", which is the fundamental building block of all other random-number functionality.
What the isUniformRNG template is _really_ asking is, "Is this going to give me a valid source of randomness to plug in to all the other random-number-generation functions, so that they'll do what I expect?"

Simple example of how that can be important: suppose you have a random generator that gives you uniform numbers in the half-open interval [min, max).  Now run that through std.random.uniform!"[]"().  You will not in fact get random numbers drawn from the closed interval you have specified.

> 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?

> 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?

   * Are these numbers uniformly distributed?

   * 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?

Can you clarify?

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?

On 04/05/14 19:42, Nick Sabalausky via Digitalmars-d wrote:
> Just a string of random bits. Effectively unsigned integers.

Ahh, OK.  So in practice you can probably template it on an unsigned integral type (which could include bool) and it'll just take the appropriate number of bits from the stream, no ... ?  Cf. what I did with /dev/urandom etc.:
https://github.com/WebDrake/std.random2/blob/master/std/random2/device.d#L122

> 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.

Yea, sounds right to me.

> 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?

Probably :-)  Let's put it this way: if you think in terms of the individual bits being generated, there obviously has to be, from the point of view of the user of the algorithm, no way to decide which bit value is more likely, which corresponds to a uniform distribution of individual bit values.  And that in turn will map to a uniform distribution of bit sequences of any length.

On 04/05/14 20:10, Joseph Rushton Wakeling via Digitalmars-d wrote:
> Probably :-)  Let's put it this way:

... we can always empirically verify the uniformity of the distribution :-)

On 5/4/2014 2:10 PM, Joseph Rushton Wakeling via Digitalmars-d wrote:
> On 04/05/14 19:42, Nick Sabalausky via Digitalmars-d wrote:
>> Just a string of random bits. Effectively unsigned integers.
>
> Ahh, OK.  So in practice you can probably template it on an unsigned
> integral type (which could include bool) and it'll just take the
> appropriate number of bits from the stream, no ... ?  Cf. what I did
> with /dev/urandom etc.:
> https://github.com/WebDrake/std.random2/blob/master/std/random2/device.d#L122
>

Well, Hash_DRBG isn't really a normal stream since, based on my reading of its spec, it sounds like (for example) requesting one byte four times will give a different result than requesting four bytes all at once (assuming you're starting from the same internal state and there's no reseeding).

But aside from that minor detail, yes, that's essentially correct. And much like /dev/(u)random, you could even make the number of bytes/bits requested a per-call runtime parameter (although that would diverge from the existing std.random interfaces and would require either allocating or taking an output sink, so I don't know whether I'll bother).

>>
>> 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?
>
> Probably :-)  Let's put it this way: if you think in terms of the
> individual bits being generated, there obviously has to be, from the
> point of view of the user of the algorithm, no way to decide which bit
> value is more likely, which corresponds to a uniform distribution of
> individual bit values.  And that in turn will map to a uniform
> distribution of bit sequences of any length.

Yea. Plus, this doc about testing these crypto PRNGs...

http://csrc.nist.gov/groups/ST/toolkit/rng/documents/SP800-22rev1a.pdf

...does mention the importance of "uniformity".

So I think it's probably safe to figure this is a uniform distribution unless some expert chimes in and says otherwise.

Thanks for the help.

On 04/05/14 20:56, Nick Sabalausky via Digitalmars-d wrote:
> So I think it's probably safe to figure this is a uniform distribution unless
> some expert chimes in and says otherwise.
>
> Thanks for the help.

You're very welcome.  Keep me posted on how things go with your implementation! :-)

On 5/4/2014 3:26 PM, Joseph Rushton Wakeling via Digitalmars-d wrote:
> On 04/05/14 20:56, Nick Sabalausky via Digitalmars-d wrote:
>> So I think it's probably safe to figure this is a uniform distribution
>> unless
>> some expert chimes in and says otherwise.
>>
>> Thanks for the help.
>
> You're very welcome.  Keep me posted on how things go with your
> implementation! :-)
>

Will do. Speaking of, this algo uses SHA-1 and SHA-2 (depending on the desired crypto strength of the psuedo-randomness). SHA-1 of course has been in Phobos for awhile. I've recently expanded it to support SHA-2, pending sufficient Phobos pull code reviews:

https://github.com/D-Programming-Language/phobos/pull/2129