Increase the reliability of random numbers

Question:

I have a function that generates pseudo-random numbers with rand that has a seed that is a publicly known time. Changing the seed is not an option.

The application needs a finer degree of randomness, as it orders a sequence of elements in a list and such a list cannot, in any way, be reconstructed. Since the seed and the random list are public, this way the reconstruction of the initial list is possible. The result of an ordered list may or may not be unique.

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

Answer:

You need a hash function.

If I understand correctly, its 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 to be discovered Li just from both public information presented. Right? In that case, all you need to do is make the function f not invertible (ie given its result – your image – you discover your inputs – your pre-image ).

It is not known whether or not there are one-way functions , but to date nobody knows how to efficiently invert certain hash functions. So they are a good candidate for solving 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 byte) 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 a hexadecimal string, usually) into a usable number.

The fact that I have 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 every time you ask for a new random number it will calculate the hash of a single value, unpredictable without Li knowledge. And the output of a good hash function is often indistinguishable from a truly random value.

PS This solution may not be the fastest of all, but it preserves the desired property. At first I thought of simply seeding the rand with the value of the hash, but then I remembered that it is possible to retrieve the seed from the hash by looking at a relatively small number of generated values… So it doesn't serve the purpose. Another alternative that came to my mind now is to use a CSPRNG seeded the same way as in my example (a combination of the original and its seed list ), I don't know which there are even good implementations of them in C, but if you have access to a performance will certainly be better than my ad-hoc solution…

Scroll to Top