Sign in to follow this  
godmodder

Calculating seed from random numbers

Recommended Posts

Hello, I was just wondering: given a set of random numbers, would it be possible to calculate the random seed that was used to generate them? Suppose I have this serie of numbers between 0 and 10: "5, 1, 6, 8, 4" and I know that the rand() function (or some other algorithm) was used to generate them. Is it possible to know what seed was used from the numbers it generates? I don't know much about random number algorithms, so don't laugh when this sounds absolutely crazy ;) Jeroen

Share this post


Link to post
Share on other sites
Quote:
Original post by godmodder
I was just wondering: given a set of random numbers, would it be possible to calculate the random seed that was used to generate them?


Yes, this is possible for any random number generator with a finite number of states, given that your sequence is big enough. Simply test all possible seeds and select the one which works.

Of course, this will take a long time if the algorithm is cryptographically secure. For classic unsafe generators such as LCG or Mersenne, you should be able to deduce the seed in polynomial time.

Quote:
the rand() function (or some other algorithm) was used to generate them.


The rand() function is not an algorithm. However, every platform will use an algorithm (possibly a different one) to implement it.


Share this post


Link to post
Share on other sites
An easy way is to pre-calculate a dictionary of first few elements of a every possible sequence, then match your input against that. Since rand is quite fast, this might not bring any benefits, unless some property exists that could be used in the dictionary.

Depending on the algorithm, you might not be able to recover exact seed, only one that generates same N elements.

The reasoning behind this comes from information theory. n-bit seed can only define 2^n unique sequences. This is also the reason why checksum collision occur, and why they can be, in many cases, trivially exploited.

For seeds larger than 32 bits, it may not be viable without some degree of algorithmic optimization.

One problem however is that for many algorithms, every member of sequence is used as seed for next one. As such, finding the original seed might be impossible.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this