Given a RNG algorithm and a series of numbers is it possible to determine what seed would produce the series?

Question

The code is in Objective C but it should be understandable if you look it over even if you don't know Objective C. Basically its a RNG object, you instantiate a new instance, set the seed if you want and start grabbing random numbers.

So is it possible to backtrack a given series of numbers to determine the seed used to generate the numbers? I'm guessing any given algorithm can't generate just any random set of numbers though, or can it?

Say I do the following:

rng.seed = 1024;
for (int i=1; i<11; i++)
    DLog(@"%lu", [rng randomBetween:0 and:10]);

Which gives me the sequence 10, 10, 8, 10, 2, 10, 9, 9, 7, 4. Is there some method or algorithm I could use, given the sequence, to get the number 1024? I know thats the valid sequence for the seen 1024, but what is I just make up a sequence... 10, 1, 9, 6, 3, 9, 10, 3, 5, 2. Is there a way to know if that is a valid sequence for this algorithm and if so what the seed is?

RNG.h:

@interface RNG : NSObject
@property (assign) unsigned long seed;
- (unsigned long)random;
- (long)randomBetween: (long)min and: (long)max;
@end

RNG.m:

#define A 16807         /* a relatively prime number -- also M div Q */
#define M 2147483647L   /* 0xFFFFFFFF / 2 */
#define Q 127773L       /* M div A */
#define R 2836          /* M mod A */

@implementation RNG
@synthesize seed = _seed;

- (id)init {
    self = [super init];
    if (self) {
        self.seed = 0;
    }
    return self;
}


- (unsigned long)random {
    self.seed = A * (self.seed % Q) - R * (self.seed / Q);
    if (self.seed > M)
        return (self.seed -= M);
    else if (self.seed)
        return (self.seed);
    else
        return (self.seed = 1L);
}


- (long)randomBetween: (long)min and: (long)max {
    return ([self random] % (max - min + 1) + min);
}


- (void)seed: (unsigned long)new_seed {
    if (new_seed == 0)
        new_seed = 1;
    while (new_seed > M)
        new_seed -= M;

    self.seed = new_seed;
}
@end

What is the seed's range? How long is the series you have? From [pigeonhole principle](http://en.wikipedia.org/wiki/Pigeonhole_principle), if you have 2^32 possible seeds, if you have less then ~9 numbers in your array, it is guaranteed to have "collisions" (Simple example: A list of size 1 of numbers in range [0,9], if you have 9 possible seeds, there are 2 seeds at least that gives the same "list") — amit, Aug 16 '12 at 08:23
@amit - The range is a an `unsigned long`... a lot of possibilities. I'm not worried about collisions at all, if there are two or more seeds that fit the sequence, I just need the 1st one found. — Justin808, Aug 16 '12 at 08:26

score 3 · Answer 1 · answered Aug 16 '12 at 08:57

3

This looks like a "Linear congruential generator", see http://en.wikipedia.org/wiki/Linear_congruential_generator" ?

These offer no good cryptographic security, so yes, it should be possible to compute a seed that produces the sequence.

answered Aug 16 '12 at 08:57

mgaert

2,338
21
27

andrew cooke · Answer 2 · 2012-08-16T20:27:47.757

the code you post is basically the same as the openbsd srandom - it's a linear congruential generator that is implemented to avoid rounding (which is why it contains Q).

here is a paper on how to crack such a generator, but it expects the full output (not the "between" value) to be available.

i guess you should be able to extend the approach in the paper to work with "between" using arithmetic modulo the range (presumably you would need more samples).

score 0 · Answer 3 · answered Aug 16 '12 at 19:38

0

Your best bet is probably to create an array (or disk file) that has the first value returned by your chosen algorithm for each seed. Then just crank through the ones that match the first value looking for a longer match. In fact, a database table would be great - gdbm or bsddb or sqlite come to mind.

This sounds to me like one of those "It's computable, but..." problems. IOW, it can be done, but it's not especially pretty.

answered Aug 16 '12 at 19:38

user1277476

2,871
12
10

I'm hoping to get an algorithm I can turn in to a function to add to my class so databases are out. Brute force through each seed *would* work but that would be exceeding slow to the point of useless. – Justin808 Aug 16 '12 at 22:55

Given a RNG algorithm and a series of numbers is it possible to determine what seed would produce the series?

3 Answers3

Linked