Mechanism to get 10 pseudo-random positive numbers up to maximum from a seed (32-byte hash)?

Question

I have learned new crypto words, so I rewrote the question:

I have quite random 32-byte hash which I want to use as a seed for generation of 10 pseudo-random positive numbers up to some maximum number, the generation must be reproducible. I would prefer, if those 10 numbers would differ from each other.

There is an example:

hash=Pkq5skE7tp=j#{y"+R$6~mg!z"4g/Utwand I need to reproducibly generate count=10 pseudo-random positive numbers up to say max=500.

So approaches that came to my mind:
1) I can take first 8 bytes Pkq5skE7 and cast them to 64-bit integer, then use modulo 500 on the result and have first number, then take other 8 bytes starting 1 byte right kq5skE7t, cast it, modulo it and get second number and I can get all 10 number like that.
Would those numbers seem pretty random or would they have some pattern?
There is not preferable effect of having 2 numbers the same.
2) I can take first 8 bytes Pkq5skE7 and cast them to 64-bit integer, then use modulo 500 on the result and have first number, then calculate other numbers with adding 500/10=50 to the result. So if the result of the cast would be 475, then other numbers would be 25, 75, .., 425.
I know that there is randomness only for the first number, but that would be good enough if method 1) would have some inconvinient pattern problem (like numbers distributed close to each other or something).
Compared to 1), numbers would be unique and that is an advantage.
3) If methods 1) and 2) won't be very good, I can again cast some bytes to 64-bit integer, do modulo, get number and take 9 numbers from following positions.
But that loses the random-like factor and I would prefer if the 10 numbers' would seem random and not much related to each other, the same problem can be said for 2), but it's preferable to have the numbers distributed over the whole spectrum.
4) Some other approach?

Basically I prefer 1), but maybe there is something better that can't yield the same number twice, maybe numbers from 1) can have a lot in common, because it's just shifting 1 byte right, I don't know.

I can tell it's used for something like drawing in a lottery. It is preferable that the numbers don't have relationship between each other, but I am not sure, if it's possible and maybe it's ok for those numbers to just look like pseudo-random and only the first being pseudo-random and other having not-obvious relationship to it.

Suggestions?

Answer 1

The best way to do this would probably be through an iterative hash, where you use that seed as an input, and from each iteration you extract a certain amount of bits for conversion to a number. A 32-bit extraction allows numbers up to around 4 billion.

I would do it as follows:

A = Hash(Seed)
Extract1 = lower 32-bits of A
Number1 = Extract1 mod (MaxVal)
B = Hash(A)
Extract2 = lower 32-bits of B
Number2 = Extract2 mod (MaxVal)
... and so on

This will prevent the numbers from having any special relationship with eachother, other than the fact they use the same seed, your suggested example means that the next number directly depends on half the previous number plus an additional 8-bits of unknown information. For a lottery that would be bad. This method means the output depends pseudorandomly on an additional 224-bits of information (assuming the hash is 256-bits).

The iterative sequence is deterministic and will always produce the same values from a given seed, and can generate both enormous numbers as well as enormous quantities of numbers, if needed.

If you want to be able to publish proof of the seed PRIOR to the lottery draw, you can post a digital signature of the seed, that way players would be assured you are not going to manipulate the seed after players are selected in order to generate winning values for a specific player. Just makes sure the signature uses a different hash function.

Answer 2

If you're always getting the same numbers, then they are not "random" in the usual sense. If you want pseudorandom numbers, then if your hash is cryptographically secure, then simply taking the hash of ten different numbers, such as 0-9, will suffice.

Answer 3

You can use a programming language's big-integer construct to implement a practically uniform random sampling algorithm that requires relatively little work. Steps are as follows:

1. Generate a random 32 bytes. (256 bits of output from a secure hash function qualifies.)
2. Convert a 32 byte array to big-integer n.
   • Whether a library uses big-endian or little-endian order does not matter because (uniform) random bytes in reverse order are still (uniform) random.
   • But if you want the result to be platform independent and implementation independent, then just pick one and require every implementation use that byte order convention.
   • Make sure the big-integer is positive. Taking the absolute value function works. Or setting the most significant bit of the most significant byte to zero. Or do a bitwise-AND with the positive quantity $2^{8 \times 32} - 1$.
3. Repeat ten times:
   1. Divide n by 500.
   2. Output the remainder of that division
   3. Set the new value of n to the quotient

The remainder of a non-negative integer divided by a positive integer $m$ will yield an integer between zero (inclusive) and m (exclusive.) ie. the range $[0, m)$. If you have a random uniform variable in a range $[0, k \cdot m)$ (the size of such a range divides $m$ evenly by integer $k$) then this method is unbiased.

The simplest way to get a uniform sample in range $[0, x)$ from a larger uniform distribution on the range $[0, y)$, $y > x$, is to generate a value $v$, $0 \le v < y$, and reject $v$ (repeat the loop) if $v \ge x$ or accept $v$ (exit the loop and return $v$) if $v < x$. This repeats as long as necesssary and requires many iterations if $y$ is much greater than $x$.

Most PRNGs can provide raw uniforms that fit in a 32 bit or 64 bit number. Only powers of two divide such numbers. (Note that another naive method v = (int)(randomDouble() * x); is also biased.) For non-powers of two $x$ you need a rejection algorithm.

The slightly more complicated "standard" method is to generate a $v$ that whose upper (exclusive) bound $x'$ is the largest possible multiple of $x$ that fits in a signed or unsigned 32 bit (not byte) int. Then after using the above simple rejection algorithm returning $v$ mod $x'$.

However if you use all 32 bytes (possibiy one bit less depedning on how you make the big-int positive) then dividing by a "small" number like $500^{10}$ is safe. I say you can skip the rejection algorithm because your bias is so small. (But it won't be safe in general.)

The number of possible 32 byte values is $2^{32 \times 8}$. Dividing by 500 ten times is like dividing by $500^{10}$ once. The difference between $2^{32 \times 8}$ and the largest multiple of $500^{10}$ not exceeding $2^{32 \times 8}$ is $2^{32 \times 8} \text{ mod } 500^{10} = 915601957584007913129639936$. That accounts for $915601957584007913129639936 / 2^{8 \times 32} \approx 7.9 \times 10^{-51} \approx 2^{-166}$.

Cryptographers agree that statistical bias smaller than $2^{-128}$ isn't practically detectable. (And probably never will be). That's why it is safe to ignore the naive-mod-method bias even though it isn't safe to ignore for a smaller number of bits.

Note: As a sanity check on that $2^{-166}$ number I perform the following calculation:

• Number of bits in $500^{10} = 10 * log_2 500 \approx 89.7$
• $2^{90}$ divides $2^{256}$ about $256 - 90 = 166$ times.
• The proportion of values the over-represented as the result of the naive-mod method is approximately one in $2^{166}$.

---

If you have an easy to use big integer library then this isn't too difficult of an algorithm. It's not a fast one though. It is actually better to use the "standard" unbiased method on 32 bit chunks because it is slow computing remainders. 32 bit or 64 bit dividend division/remainder calculation is still slow, but the rejection algorithm may be faster overall.

You will need to be able to generate new random data because the algorithm may use more than 32 bytes. This could be done deterministically from the given hash using repeated hashing, repeated block encryption, keying a stream cipher with the 32 byte value, or using a CSPRNG with the 32 bytes.

But if the PRNG isn't "secure" then the output of that RNG can be predicted regardless of whether the seed is unpredictable or not.

There simply aren't many implementations of that type of RNG. ISAAC based implementations don't qualify. (We don't know enough about ISAAC to say that it's a secure cipher algorithm either.) PCG definitely does not qualify despite what you may have heard.