Given a RNG algorithm and a series of numbers is i

问题:

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

回答1:

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.

回答2:

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).

回答3:

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.