Increase the reliability of random numbers

3

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

The application needs a more accurate degree of randomness because it sorts a sequence of elements into a list and such a list can not be reconstructed in any way. Because seed and the random list are public, rebuilding the initial list is possible. The result of an ordered list may or may not be unique.

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

    
asked by anonymous 02.10.2015 / 02:46

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 do not want to find Li only from both public information displayed. Right? In this case, all you have to do is make the f function not invertible (ie given its result - your image - you discover your entries - in> pre-image ).

One-way functions

a>), but to this day no one knows how to effectively 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 pseudorandom 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 representation (or bytes) 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 into hexadecimal string, usually) into a usable number.

The fact that I called SHA-256 several times in this way is to avoid length extension attacks , it may be exaggerated, but I'd rather sin over caution ... The fact is that every 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 often indistinguishable from a really random value.

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

    
02.10.2015 / 17:59