Increase the reliability of random numbers

Asked

Viewed 149 times

3

I have a function that generates pseudo-random numbers with rand who has a Seed which is a publicly known time. Change the Seed is not an option.

The application needs a more accurate degree of randomness, as it sorts a sequence of elements in a list and such a list cannot be reconstructed at all. For the Seed and the random list are public, so rebuilding the initial list is possible. The result of an ordered list may or may not be unique.

The list sorted "randomly" is also public. The application environment is Linux. I would like to know how to accomplish this with some other function.

c random-numbers
  • 1

    srand should be called only on startup of the generator. Which operating system? If it is Linux, use the /dev/random or /dev/urandom provided by the OS. Or use the Mersenne-Twister algorithm.

  • 1

    What do you mean by "higher degree of randomness"? Is there any randomness test that the function rand is not passing? Or maybe the period function is too short? Please specify exactly what you are looking for. The use of /dev/urandom or some CSPRNG (if applicable) or maybe some mixing process might be a good idea, or not, depends a lot on where you want to get...

  • I tried to be very generalist and ended up making the question vague.

  • It has improved, but it explains better what it means by "such a list cannot in any way be reconstructed". Does it mean that after repeated draws you don’t want to go back to the same list? Or did I get it wrong? In addition, it is important to you that the program is repeatable, i.e. that given the same Seed if the same draw comes? If the answer is "no", then /dev/urandom is a good call (but maybe not enough for your requirements, please clarify the point above and maybe I can answer something).

  • You can use the Mersenne Twister with improved boot.

1 answer

2


You need a hash function.

If I understand correctly, your final list is Li and its seed s, and the final list Lf is given by Lf = f(s, Li). Lf and s are public, and you don’t want Li only from both public information presented. Right? In that case, all you need to do is with that function f not be invertible (i.e. given its result - its image - you discover your entries - your pre-image).

It is not known whether there are non-invertible functions (one-way functions), but to this day no one knows how to efficiently reverse certain hash functions. So they are a good candidate to solve your problem. If you have access to any of them, say SHA-256, you can use it to generate a sequence of pseudo-random numbers:

semear(Li, s) {
    sufixo = SHA-256(str(Li) + SHA-256(s))
    indice = 0
}

próximo número aleatório() {
    return SHA-256((indice++) + sufixo);
}

Pseudo-code: str(Li) is a string (or bytes) representation of your list, and + in this case represents the concatenation. It is also necessary to transform the output of the SHA-256 function (which will come in bytes or hexadecimal string, normally) into a usable number.

The fact that I called SHA-256 several times this way is to avoid length Extension Attacks, It may be an exaggeration, but I prefer to err on the side of caution... The fact is that each time you ask for a new random number it will calculate the hash of a unique, unpredictable value without the knowledge of Li. And the output of a good hash function is usually indistinguishable from a really random value.

P.S. This solution may not be the fastest of all, but it preserves the desired property. At first I thought of simply sowing the rand with the hash value, but then I remembered that it is possible to recover the hash seed by observing a relatively small number of generated values... So it doesn’t serve the purpose. Another alternative that came to mind right now is to use a CSPRNG sown in the same way as in my example (a combination of the original list and your Seed), I do not know what are there or good implementations of them in C, but if you have access to a performance will certainly be better than this my solution ad-hoc...

Browser other questions tagged c random-numbers

You are not signed in. Login or sign up in order to post.